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):
testl %eax, %eax
movl %esp, %ebp
movl %eax, %ecx
movzbl (%ecx), %eax
testb %al, %al
leal (%edx,%edx,4), %edx
leal -48(%eax,%edx,2), %edx
movl %edx, %eax
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.