如何检查gcc是否执行尾部
我该如何判断gcc（更具体地说是g ++）是否正在优化特定函数中的尾递归？ （因为它出现了几次：我不想测试gcc是否可以优化尾部递归，我想知道它是否优化了我的尾部递归函数。）
如果你的答案是“查看生成的汇编程序”，我想知道我正在寻找什么，以及我是否可以编写一个简单的程序来检查汇编程序以查看是否存在优化。
PS。 我知道这是问题的一部分，如果有的话，C ++编译器会进行尾递归优化吗？ 从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
编译器对此函数执行了尾部优化。 我们可以看出，因为该代码中没有call指令，而原始的C代码显然具有函数调用。 此外，我们可以看到jne L5指令，它在函数中向后跳转，指示C代码中没有明显循环时的循环。 如果您在优化关闭的情况下重新编译，您会看到一行表示call _atoi的行，并且您也看不到任何向后跳转。
你是否可以自动化这是另一回事。 汇编代码的细节将取决于您正在编译的代码。
我想，你可以通过程序来发现它。 使函数打印出堆栈指针的当前值（在x86上注册ESP）。 如果该函数为第一次调用打印的值与递归调用的值相同，则编译器执行了尾部调用优化。 这个想法需要修改你希望观察的功能，这可能会影响编译器选择优化函数的方式。 如果测试成功（两次输出相同的ESP值），那么我认为可以合理地假设优化也将在没有使用仪器的情况下执行，但如果测试失败，我们将不知道失败是由于仪器代码的添加。
编辑我原来的帖子也阻止了海湾合作委员会实际上做尾部呼叫淘汰。 我在下面添加了一些额外的技巧，愚弄GCC无论如何都要进行尾呼叫清除。
在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;
}
在非递归调用函数时，传入0检查参数。 否则传入oracle。 如果应该消除的尾递归调用不是，那么你会在运行时被通知。
在进行测试时，它看起来像我的GCC版本没有优化第一个尾部呼叫，但其余的尾部呼叫进行了优化。 有趣。
查看生成的汇编代码，看看它是否使用call或jmp指令进行x86上的递归调用（对于其他体系结构，请查找相应的指示信息）。 你可以使用nm和objdump来获得与你的函数相对应的程序集。 考虑以下功能：
int fact(int n)
{
return n <= 1 ? 1 : n * fact(n-1);
}
编译为
gcc fact.c -c -o fact.o -O2
然后，测试它是否使用尾递归：
# 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
当运行上述函数时，该脚本输出“事实是尾递归”。 当使用-O3而不是-O2编译时，这会奇怪地打印出“事实不是尾递归”。
请注意，这可能会产生误报，正如Ehemient在他的评论中指出的那样。 该脚本将只得到正确的答案，如果函数包含本身没有递归调用可言，也没有检测到同级递归（例如在A()调用B()它调用A() 目前我无法想到更强大的方法，不需要人为地查看生成的程序集，但至少可以使用此脚本轻松获取与对象文件中特定函数相对应的程序集。