如何检查 gcc 是否正在执行尾递归优化? [英] How do I check if gcc is performing tail-recursion optimization?

问题描述

我如何判断 gcc(更具体地说，g++)是否正在优化特定函数中的尾递归?(因为出现了几次:我不想测试gcc是否可以优化尾递归.我想知道它是否优化了我的尾递归函数.)

如果您的回答是查看生成的汇编程序"，我想确切地知道我在寻找什么，以及我是否可以编写一个简单的程序来检查汇编程序以查看是否有优化.

附注.我知道这作为问题的一部分出现如果有的话，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测试 %eax, %eaxmovl %esp, %ebpmovl %eax, %ecxje L3.align 4,0x90L5:movzbl (%ecx), %eax测试b %al, %alje L3leal (%edx,%edx,4), %edxmovsbl %al,%eax包括 %ecxleal -48(%eax,%edx,2), %edxL5.align 4,0x90L3:离开movl %edx, %eax退

编译器对这个函数进行了尾调用优化.我们可以看出，因为在该代码中没有 call 指令，而原始 C 代码显然有一个函数调用.此外，我们可以看到jne L5指令，它在函数中向后跳转，在C代码中明显没有循环时表示循环.如果您在关闭优化的情况下重新编译，您将看到一行 call _atoi，并且您也不会看到任何向后跳转.

是否可以自动化这是另一回事.汇编代码的细节将取决于您正在编译的代码.

我认为您可以通过编程方式发现它.使函数打印出堆栈指针的当前值(x86 上的寄存器 ESP).如果函数在第一次调用时打印出与递归调用相同的值，则编译器已经执行了尾调用优化.但是，这个想法需要修改您希望观察的函数，这可能会影响编译器选择优化函数的方式.如果测试成功(两次打印相同的 ESP 值)，那么我认为可以合理地假设优化也将在没有您的检测的情况下执行，但如果测试失败，我们将不知道失败是否是由于添加检测代码.

How do I tell if gcc (more specifically, g++) is optimizing tail recursion in a particular function? (Because it's come up a few times: I don't want to test if gcc can optimize tail recursion in general. I want to know if it optimizes my tail recursive function.)

If your answer is "look at the generated assembler", I'd like to know exactly what I'm looking for, and whether or not I could write a simple program that examines the assembler to see if there's optimization.

PS. I know this appears as part of the question Which, if any, C++ compilers do tail-recursion optimization? from 5 months ago. However, I don't think this part of that question was answered satisfactorily. (The answer there was "The easiest way to check if the compiler did the optimization (that I know of) is perform a call that would otherwise result in a stack overflow – or looking at the assembly output.")

解决方案

Let's use the example code from the other question. Compile it, but tell gcc not to assemble:

gcc -std=c99 -S -O2 test.c

Now let's look at the _atoi function in the resultant test.s file (gcc 4.0.1 on Mac OS 10.5):

        .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

The compiler has performed tail-call optimization on this function. We can tell because there is no call instruction in that code whereas the original C code clearly had a function call. Furthermore, we can see the jne L5 instruction, which jumps backward in the function, indicating a loop when there was clearly no loop in the C code. If you recompile with optimization turned off, you'll see a line that says call _atoi, and you also won't see any backward jumps.

Whether you can automate this is another matter. The specifics of the assembler code will depend on the code you're compiling.

You could discover it programmatically, I think. Make the function print out the current value of the stack pointer (register ESP on x86). If the function prints the same value for the first call as it does for the recursive call, then the compiler has performed the tail-call optimization. This idea requires modifying the function you hope to observe, though, and that might affect how the compiler chooses to optimize the function. If the test succeeds (prints the same ESP value both times), then I think it's reasonable to assume that the optimization would also be performed without your instrumentation, but if the test fails, we won't know whether the failure was due to the addition of the instrumentation code.

这篇关于如何检查 gcc 是否正在执行尾递归优化?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！