'smart' GCC 的尾调用优化如何？

Question

我刚刚讨论了以下两段 C 代码：

For 循环：

#include <stdio.h>
#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 <stdio.h>
#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 并想到了 "ah, that's not tail call recursive"，因为在对 recursive 的调用完成后它还有工作要做；它需要增加 return 值。

果然，在没有优化的情况下，递归代码触发了堆栈溢出，如您所料。

然而，使用 -O2 标志，不会遇到堆栈溢出，我认为这意味着堆栈被重用，而不是将越来越多的内容压入堆栈 - 这就是 tco。

GCC 显然可以检测到这种简单情况（+1 到 return 值）并对其进行优化，但它能走多远？

当递归调用不是要执行的最后一个操作时，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

所以一个（诚然简单但不是很严格的）基准表明它确实看起来确实在相同的时间顺序。

Answer 1

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

0x0040150B  cmpl   [=10=]x0,0x10(%rbp)
0x0040150F  jle    0x401523 <recursive+35>
0x00401511  mov    0x10(%rbp),%eax
0x00401514  sub    [=10=]x1,%eax
0x00401517  mov    %eax,%ecx
0x00401519  callq  0x401500 <recursive>

但是使用 -O1、-O2 或 -O3 我得到这个：

0x00402D09  mov    [=11=]x2ffff,%edx

这与尾部优化没有任何关系，而是更激进的优化。编译器简单地内联了整个函数和 pre-calculated 结果。

这可能就是为什么您在所有不同的基准测试案例中最终得到相同结果的原因。

'smart' GCC 的尾调用优化如何？

How 'smart' is GCC's Tail-Call-Optimisation?

c

optimization

recursion

gcc

tail-call-optimization