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后还有工作要做；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

因此，（诚然简单且不是很严格）基准测试表明，它确实似乎与所用时间的顺序相同。

Answer 1

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

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

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

0x00402D09  mov    $0x2ffff,%edx

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

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