LLVM尾调用优化

Question

这是我对事物的理解:

当调用自身是最后一个动作时,函数"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只对递归函数执行优化(如果可用)？

Answer 1

这里有两件事不同：

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

听起来你想要前者。

Answer 2

显然答案是肯定的。你必须改变 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）。