How do I check if gcc is performing tail
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.
EDIT My original post also prevented GCC from actually doing tail call eliminations. I've added some additional trickiness below that fools GCC into doing tail call elimination anyways.
Expanding on Steven's answer, you can programmatically check to see if you have the same stack frame:
#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;
}
When calling the function non-recursively, pass in 0 the check parameter. Otherwise pass in oracle. If a tail recursive call that should've been eliminated was not, then you'll be informed at runtime.
When testing this out, it looks like my version of GCC does not optimize the first tail call, but the remaining tail calls are optimized. Interesting.
Look at the generated assembly code and see if it uses a call or jmp instruction for the recursive call on x86 (for other architectures, look up the corresponding instructions). You can use nm and objdump to get just the assembly corresponding to your function. Consider the following function:
int fact(int n)
{
return n <= 1 ? 1 : n * fact(n-1);
}
Compile as
gcc fact.c -c -o fact.o -O2
Then, to test if it's using tail 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
When ran on the above function, this script prints "fact is tail recursive". When instead compiled with -O3 instead of -O2 , this curiously prints "fact is NOT tail recursive".
Note that this might yield false negatives, as ehemient pointed out in his comment. This script will only yield the right answer if the function contains no recursive calls to itself at all, and it also doesn't detect sibling recursion (eg where A() calls B() which calls A() ). I can't think of a more robust method at the moment that doesn't involve having a human look at the generated assembly, but at least you can use this script to easily grab the assembly corresponding to a particular function within an object file.
上一篇: 如何检测到StackOverflowException？
下一篇: 如何检查gcc是否执行尾部