LLVM尾部呼叫优化 [英] LLVM tail call optimization

问题描述

这是我对事物的理解:

函数"f"在调用自身是其最后一个动作时是尾部递归的. 通过形成循环而不是再次调用该函数，可以显着优化尾递归.该函数的参数将在适当位置更新，然后再次运行主体.这称为递归尾部调用优化.

A function "f" is tail recursive when calling itself is its last action. Tail-recursion can be significantly optimized by forming a loop instead of calling the function again; the function's parameters are updated in place, and the body is ran again. This is called recursive tail call optimization.

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

LLVM implements recursive tail call optimization when using fastcc, GHC, or the HiPE calling convention. http://llvm.org/docs/CodeGenerator.html#tail-call-optimization

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

I have some questions: Let's consider the silly example:

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

1)在他们的示例中，关键字"tail"位于呼叫前面.在其他地方，我读到这个关键字是可选的.假设上面的功能被适当地转换为LLVM，是否需要最后几行

1) In their example, the keyword "tail" preceeds call. Elsewhere I read that this keyword is optional. Suppose the function above is translated to LLVM appropriately, do the last few lines need to be

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

2)示例中的inreg选项是什么意思?

2) What is the meaning of the inreg option in their example?

3)我不想只在递归函数上到处执行尾部调用优化.有没有办法让LLVM仅对递归函数执行优化(如果可用)?

3) I would not want to perform tail call optimizations all over the place, only for recursive functions. Is there a way I can get LLVM to only perform the optimization (when available) for recursive functions?

推荐答案

显然，答案是肯定的.您必须更改h的定义才能看到此信息(因为优化器太好了！它确定h是标识或返回0).

Apparently the answer is yes. You have to change the definition of h to see this (because the optimizer is too good! It figures out that h is either the identity or returns 0).

考虑

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

使用clang -S -emit-llvm进行编译，因此不执行优化.有人看到没有直接指定任何调用约定，这意味着默认调用约定足以支持尾部递归优化(通常它是否支持尾部调用是另一回事了，这很有趣，但是我想这确实是一个不同的问题.

Compiled with clang -S -emit-llvm, so that no optimization is performed. One sees that no calling conventions are directly specified, which means that the default calling convention is enough to support tail recursion optimization (whether or not it supports tail calling in general is a different story -- it would be interesting to know, but I guess that is really a different question).

由clang -S -emit-llvm发出的文件是main.s(假设阶乘定义在main.c中).如果您运行

The file emitted by clang -S -emit-llvm is main.s (assuming the factorial definition is in main.c). If you run

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

然后您可以看到消除了尾部递归.有一个称为tailcallelim的优化，可以将其打开为-O3.很难说，因为帮助文件opt --help仅表示-O3与gcc -O3相似.

then you can see that the tail recursion is eliminated. There is an optimization called tailcallelim which may be turned on as -O3. It's hard to tell because the help file, opt --help, says only that -O3 is similar to gcc -O3.

要点是，我们可以看到不需要为此指定调用约定.也许不需要fastcc，或者它是默认设置?因此(1)得到部分回答；但是，我仍然不知道(2)或(3).

The point is that we can see that the calling convention does not need to specified for this. Maybe fastcc is not needed, or maybe it is default? So (1) is partially answered; however, I still do not know (2) or (3).

这篇关于LLVM尾部呼叫优化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！