GCC的尾部呼叫优化有多“聪明”?

我刚刚讨论了以下两个C代码的讨论:

for循环:

#include  #define n (196607) int main() { long loop; int count=0; for (loop=0;loop<n;loop++) { count++; } printf("Result = %d\n",count); return 0; } 

递归:

 #include  #define n (196607) long recursive(long loop) { return (loop>0) ? recursive(loop-1)+1: 0; } int main() { long result; result = recursive(n); printf("Result = %d\n",result); return 0; } 

在看到这段代码时,我看到了recursive(loop-1)+1并认为“啊,这不是尾调用递归”,因为它在完成对recursive的调用之后还有工作要做; 它需要增加返回值。

果然,没有优化,递归代码会触发堆栈溢出,正如您所期望的那样。

然而,使用-O2标志,不会遇到堆栈溢出,我认为这意味着堆栈被重用,而不是越来越多地推入堆栈 – 这就是tco。

GCC显然可以检测到这个简单的情况(+1返回值)并对其进行优化,但它会走多远?

当递归调用不是最后要执行的操作时,gcc可以用tco优化的限制是什么?

附录:我写了一个完全尾递归return function(); 代码的版本。 将上面的内容包含在9999999次迭代的循环中,我想出了以下时间:

 $ for f in *.exe; do time ./$f > results; done + for f in '*.exe' + ./forLoop.c.exe real 0m3.650s user 0m3.588s sys 0m0.061s + for f in '*.exe' + ./recursive.c.exe real 0m3.682s user 0m3.588s sys 0m0.093s + for f in '*.exe' + ./tail_recursive.c.exe real 0m3.697s user 0m3.588s sys 0m0.077s 

所以一个(不可否认的简单而不是非常严格)的基准测试表明,它确实看起来确实处于相同的时间顺序。

只需反汇编代码,看看发生了什么。 没有优化,我得到这个:

 0x0040150B cmpl $0x0,0x10(%rbp) 0x0040150F jle 0x401523  0x00401511 mov 0x10(%rbp),%eax 0x00401514 sub $0x1,%eax 0x00401517 mov %eax,%ecx 0x00401519 callq 0x401500  

但是使用-O1,-O2或-O3我得到这个:

 0x00402D09 mov $0x2ffff,%edx 

这与尾部优化没有任何关系,而是更激进的优化。 编译器只是简单地内联整个函数并预先计算结果。

这可能是您在所有不同的基准测试案例中得出相同结果的原因。