如何检查gcc是否执行尾recursion优化？
我该如何判断gcc（更具体地说，g ++）是否正在优化特定函数中的尾recursion？ （因为它出现了几次：我不想testinggcc是否可以优化尾recursion，我想知道它是否优化了我的尾recursion函数。）
如果你的答案是“看看生成的汇编程序”，我想知道我正在寻找什么，以及我是否可以编写一个简单的程序来检查汇编程序，看是否有优化。
PS。 我知道这是问题的一部分，如果有的话，C ++编译器做尾recursion优化？ 从5个月前。 不过，我不觉得这问题的答案令人满意。 （答案是“最简单的方法来检查编译器是否进行了优化（我知道的）是执行调用，否则会导致堆栈溢出 – 或者查看程序集输出。”）
让我们使用另一个问题的示例代码 。 编译它，但是告诉gcc不要组装：
gcc -std = c99 -S -O2 test.c
现在让我们看一下生成的test.s文件中的_atoi函数（Mac OS 10.5上的gcc 4.0.1）：
.text .align 4,0x90 _atoi: pushl %ebp testl %eax, %eax movl %esp, %ebp movl %eax, %ecx je L3 .align 4,0x90 L5: movzbl (%ecx), %eax testb %al, %al je L3 leal (%edx,%edx,4), %edx movsbl %al,%eax incl %ecx leal -48(%eax,%edx,2), %edx jne L5 .align 4,0x90 L3: leave movl %edx, %eax ret
编译器已经对这个函数进行了tail-call优化。 我们可以看出，因为在那个代码中没有call指令，而原来的C代码显然有一个函数调用。 此外，我们可以看到jne L5指令，它在函数中向后跳转，表示C代码中没有循环的时候表示一个循环。 如果您在优化closures的情况下重新编译，您将会看到一行表示call _atoi ，而且您也不会看到任何后退跳转。
你是否可以自动化这是另一回事。 汇编代码的细节取决于你正在编译的代码。
我想你可以通过编程来发现它。 使函数打印出堆栈指针的当前值（在x86上注册ESP）。 如果该函数为第一次调用打印与recursion调用相同的值，则编译器执行了尾部调用优化。 这个想法需要修改你希望观察的函数，这可能会影响编译器select优化函数的方式。 如果testing成功（两次打印相同的ESP值），那么我认为可以合理地假设优化也将在没有您的工具的情况下执行，但是如果testing失败，我们将不知道失败是由于仪器代码的添加。
编辑我原来的post也阻止了海湾合作委员会实际上做尾部呼叫淘汰。 我已经添加了一些额外的技巧，愚弄海湾合作委员会无论如何做尾巴消除。
扩展Steven的答案，你可以通过编程来检查你是否有相同的堆栈框架：
#include <stdio.h> // We need to get a reference to the stack without spooking GCC into turning // off tail-call elimination int oracle2(void) { char oracle; int oracle2 = (int)&oracle; return oracle2; } void myCoolFunction(params, ..., int tailRecursionCheck) { int oracle = oracle2(); if( tailRecursionCheck && tailRecursionCheck != oracle ) { printf("GCC did not optimize this call.\n"); } // ... more code ... // The return is significant... GCC won't eliminate the call otherwise return myCoolFunction( ..., oracle); } int main(int argc, char *argv[]) { myCoolFunction(..., 0); return 0; }
在非recursion调用函数时，传入0的检查参数。 否则传入oracle。 如果一个应该被淘汰的尾recursion调用不是，那么你会在运行时被通知。
在进行testing时，看起来像我的GCC版本没有优化第一个尾部呼叫，但其余尾部呼叫进行了优化。 有趣。
查看生成的汇编代码，看看它是否使用call或jmp指令进行x86上的recursion调用（对于其他体系结构，请查看相应的指令）。 您可以使用nm和objdump来获得与您的函数相对应的程序集。 考虑以下function：
int fact(int n) { return n <= 1 ? 1 : n * fact(n-1); }
编译为
gcc fact.c -c -o fact.o -O2
然后，testing它是否使用尾recursion：
# get starting address and size of function fact from nm ADDR=$(nm --print-size --radix=d fact.o | grep ' fact$' | cut -d ' ' -f 1,2) # strip leading 0's to avoid being interpreted by objdump as octal addresses STARTADDR=$(echo $ADDR | cut -d ' ' -f 1 | sed 's/^0*\(.\)/\1/') SIZE=$(echo $ADDR | cut -d ' ' -f 2 | sed 's/^0*//') STOPADDR=$(( $STARTADDR + $SIZE )) # now disassemble the function and look for an instruction of the form # call addr <fact+offset> if objdump --disassemble fact.o --start-address=$STARTADDR --stop-address=$STOPADDR | \ grep -qE 'call +[0-9a-f]+ <fact\+' then echo "fact is NOT tail recursive" else echo "fact is tail recursive" fi
当运行上面的函数时，这个脚本打印出“事实是尾recursion的”。 当用-O3代替-O2编译时，这个好奇地打印出“事实不是尾recursion的”。
请注意，这可能会产生错误的否定，正如Ehemient在他的评论中指出的那样。 如果函数根本不包含recursion调用，而且它也不检测同级recursion（例如， A()调用调用A() B() ，那么这个脚本只会产生正确的答案。 现在我不能想到一个更健壮的方法，不需要人工看待生成的程序集，但是至less可以使用这个脚本轻松获取对象文件中与特定函数相对应的程序集。
在PolyThinker的回答中，有一个具体的例子。
int foo(int a, int b) { if (a && b) return foo(a - 1, b - 1); return a + b; }
i686-pc-linux-gnu-gcc-4.3.2 -Os -fno-optimize-sibling-calls输出：
00000000 <foo>：
0：55推％ebp
1：89 e5 mov％esp，％ebp
3：8b 55 08 mov 0x8（％ebp），％edx
6：8b 45 0c mov 0xc（％ebp），％eax
9：85 d2 test％edx，％edx
b：74 16 je 23 <foo + 0x23>
d：85 c0 test％eax，％eax
f：74 12 je 23 <foo + 0x23>
11：51推％ecx
12：48 dec％eax
13：51推％ecx
14：50推％eax
15：8d 42ff lea -0x1（％edx），％eax
18：50推％eax
19：e8 fc如果调用1a <foo + 0x1a>
1e：83 c4 10 add $ 0x10，％esp
21：eb 02 jmp 25 <foo + 0x25>
23：01 d0 add％edx，％eax
25：c9离开
26：c3 ret
i686-pc-linux-gnu-gcc-4.3.2 -Os输出：
00000000 <foo>：
0：55推％ebp
1：89 e5 mov％esp，％ebp
3：8b 55 08 mov 0x8（％ebp），％edx
6：8b 45 0c mov 0xc（％ebp），％eax
9：85 d2 test％edx，％edx
b：74 08 je 15 <foo + 0x15>
d：85 c0 test％eax，％eax
f：74 04 je 15 <foo + 0x15>
11：48分贝％eax
12：4a dec％edx
13：eb f4 jmp 9 <foo + 0x9>
15：5d pop％ebp
16：01 d0 add％edx，％eax
18：c3 ret
在第一种情况下， <foo+0x11>-<foo+0x1d>为函数调用推送参数，而在第二种情况下， <foo+0x11>-<foo+0x14>修改variables和jmp到相同的函数，在序言之后的某处。 这就是你想要的。
我不认为你可以通过编程来完成这个任务。 有太多可能的变化。 函数的“肉”可能更接近或更远离开始，并且您不能将jmp从循环或条件中区分开来，而不必查看它。 这可能是一个条件跳转，而不是一个jmp 。 gcc可能会留下一些call ，但将兄弟电话优化应用于其他情况。
仅供参考，海湾合作委员会的“兄弟调用”比尾recursion调用稍微普遍 – 有效地，任何函数调用重新使用相同的堆栈框架是好的可能是兄弟的调用。
[编辑]
作为一个例子，当只是寻找一个自我recursion的call会误导你，
int bar(int n) { if (n == 0) return bar(bar(1)); if (n % 2) return n; return bar(n / 2); }
海湾合作委员会将适用于三个bar电话中的两个兄弟电话优化。 我仍然把它称为tail-call-optimized，因为那个单一的未优化的调用永远不会超过一个单独的级别，即使你会在生成的程序集中find一个call <bar+..> 。
我懒得去看拆卸。 尝试这个：
void so(long l) { ++l; so(l); } int main(int argc, char ** argv) { so(0); return 0; }
编译并运行这个程序。 如果它永远运行，tail-recursion被优化了。 如果它吹到堆栈，它不是。
编辑：对不起，读得太快了，OP想知道他的特定函数是否将其尾recursion优化了。 好…
…原理是一样的 – 如果tail-recursion正在被优化掉，那么栈帧将保持不变。 您应该能够使用回溯function从您的函数中捕获堆栈帧，并确定它们是否正在增长。 如果尾recursion正在被优化，你将只有一个返回指针在缓冲区中 。
另一种方法我检查这是：
- 用'gcc -O2'编译你的代码
- 开始'gdb'
- 在你希望被尾recursion优化/消除的函数中放置一个断点
- 运行你的代码
- 如果已经尾巴消除，那么断点只会被击中一次，或者从不会。 欲了解更多，请参阅此
一个简单的方法：构build一个简单的尾recursion程序，编译它，并将其解开，看它是否被优化。
刚刚意识到你已经有了你的问题。 如果你知道如何阅读程序集，那很容易。 recursion函数会从函数体内调用自己（带有“调用标签”），循环将只是“jmp label”。
你可以制作input数据，这会导致堆栈溢出，因为如果没有优化，那么函数调用的recursion太深，看看是否发生。 当然，这不是微不足道的，有时足够大的input会使function运行很长的一段时间。
