'聪明'是GCC的尾巴呼叫优化？

我只是在那里正在讨论的C代码以下两个peices讨论：'聪明'是GCC的尾巴呼叫优化？

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返回值），并优化它，但多远它去？

什么都可以用TCO优化什么GCC的限制，当递归调用是不被执行的最后一个操作？

附录：我写了一个完全尾递归的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

所以（当然简单，并没有很严格）基准测试表明，它确实似乎是在相同的顺序所用的时间。

来源

2017-02-10 Baldrickk

编译器可能只是内联函数而不是使用尾递归。使用'-S'标志编译程序并查看汇编代码的外观。 –

我同意@squeamishossifrage。不要启用优化，然后假设编译器做了什么。你可能会感到惊讶，这是毫无意义的。 – unwind

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

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

这不会有任何与尾部的优化，但更激进的优化。编译器简单地将整个函数内联并预先计算出结果。

为什么你最终得到相同的结果在基准的所有不同的情况下，这是可能的。

来源

2017-02-10 14:03:45 Lundin

'聪明'是GCC的尾巴呼叫优化？

回答

相关问题