7

以下是我对事物的理解：

当调用自身是函数“f”的最后一个操作时，函数“f”是尾递归的。通过形成循环而不是再次调用函数可以显着优化尾递归；函数的参数被更新到位，并再次运行主体。这称为递归尾调用优化。

LLVM 在使用 fastcc、GHC 或 HiPE 调用约定时实现递归尾调用优化。 http://llvm.org/docs/CodeGenerator.html#tail-call-optimization

我有一些问题：让我们考虑这个愚蠢的例子：

int h(int x){
  if (x <= 0)
    return x;
  else
    h(x-1);
}

1）在他们的例子中，关键字“tail”在调用之前。在其他地方我读到这个关键字是可选的。假设上面的函数被适当地翻译成 LLVM，最后几行是否需要

%x' = load *i32 %x
%m = tail call fastcc i32 @h(i32 %x')
ret %m

2）在他们的例子中 inreg 选项的含义是什么？

3) 我不想到处执行尾调用优化，只针对递归函数。有没有办法让 LLVM 只对递归函数执行优化（如果可用）？

4

2 回答 2

4

显然答案是肯定的。您必须更改 h 的定义才能看到这一点（因为优化器太好了！它发现 h 要么是标识，要么返回 0）。

考虑

int factorial (int x, int y){
  if (x==0)
    return y;
  else
    return factorial(x-1,y*x);
}

使用 clang -S -emit-llvm 编译，因此不执行优化。有人看到没有直接指定调用约定，这意味着默认调用约定足以支持尾递归优化（它是否支持尾调用通常是另一回事 - 知道会很有趣，但我猜这真的是一个不同的问题）。

clang -S -emit-llvm 发出的文件是 main.s（假设阶乘定义在 main.c 中）。如果你跑

opt -O3 main.s -S -o mainOpt.s

然后你可以看到尾递归被消除了。有一个称为 tailcallelim 的优化，可以打开为 -O3。很难说，因为帮助文件 opt --help 只说 -O3 类似于 gcc -O3。

关键是我们可以看到调用约定不需要为此指定。也许不需要fastcc，或者它是默认的？所以（1）部分回答；但是，我仍然不知道（2）或（3）。

于 2013-09-04T16:34:53.217 回答
4

这里有两个不同的东西：

  1. 您可以将自递归尾调用优化为循环。LLVM 提供了一个优化通道来执行此操作。它不需要特定的调用约定。
  2. 您可以使用不同的调用约定来保证尾部位置的所有调用的尾部调用优化（即包括对其他函数的调用）。使用 LLVM，您需要在调用指令上指定函数的调用约定，并将调用标记为尾调用。

听起来你想要前者。

于 2017-09-26T07:08:55.593 回答