c - 'smart' 是如何进行 GCC 的 Tail-Call-Optimisation 的？

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

这与尾部优化无关，而是更激进的优化。编译器简单地内联整个函数并预先计算结果。

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