Tail Recursion Optimization, gcc, gdb

by Amit


Debugging or even throwing optimized code in a debugger is a stupid idea, when you are trying to debug the code, that is. Not so lame, when you are trying to learn whether the optimization has actually taken place ;-). I wanted to check whether Tail Call Optimisation (better yet, Tail Call Elimination) has taken place on a certain piece of code. Here’s how:

Consider the following C implementation of the factorial function:

/* factorial-tail.c */

#include <stdio.h>
unsigned long long factorial(unsigned long long fact_so_far, unsigned long long count, unsigned long long max_count){
if (max_count==0 || max_count==1 || count >= max_count)
return fact_so_far;
else
{
//	printf("%llu  %p \n", count, &factorial); /*
return factorial(fact_so_far * count, ++count, max_count);
}
}

int main(int argc, char **argv)
{
unsigned long long n;
scanf("%llu", &n);
printf("\n Factorial %llu \n",factorial(1,0,n));
return 0;

}

Consider the function, factorial. As required by the definition of tail call recursion, the last executed statement is the recursive call to itself. No operation is pending in the caller, once the callee finishes its task.

Compile the code using ‘gcc’:

gcc -O2 -fno-inline -o factorial-tail factorial-tail.c

Now, fire up ‘gdb’ with the object code obtained above:

$ gdb ./factorial-tail
(gdb) b factorial
Breakpoint 1 at 0x8048426
(gdb) run
Starting program: /home/amit/Documents/Writings/cs-essays/fact-codes/factorial-tail
5
Breakpoint 1, 0x08048426 in factorial ()
Current language: auto; currently asm
(gdb) c
Continuing.
Factorial 120
Program exited normally.

As you can see the breakpoint was hit just once, whereas clearly if the code was executed unoptimized, it should have been called 5 times.

A note on ‘-fno-inline’ flag: Explicitly mentioing the ‘-fno-inline’ flag prevents any inlining of the fuctions due to the ‘-O2’ flag. On my gcc/gdb combination, without the flag, inlining was being done, due to which the breakpoint wasn’t hit even once.

Now, compile the same code, without the -O2 and -fno-inline flags:

gcc -o factorial-tail factorial-tail.c

Fire up ‘gdb’ as above:


$ gdb ./factorial-tail.
(gdb) b factorial
Breakpoint 1 at 0x80483f8
(gdb) run
Starting program: /home/amit/Documents/Writings/cs-essays/fact-codes/factorial-tail
5
Breakpoint 1, 0x080483f8 in factorial ()
Current language: auto; currently asm
(gdb) c
Continuing.
Breakpoint 1, 0x080483f8 in factorial ()
(gdb) c
Continuing.
Breakpoint 1, 0x080483f8 in factorial ()
(gdb) c
Continuing.
Breakpoint 1, 0x080483f8 in factorial ()
(gdb) c
Continuing.
Breakpoint 1, 0x080483f8 in factorial ()
(gdb) c
Continuing.
Breakpoint 1, 0x080483f8 in factorial ()
(gdb) c
Continuing.
Factorial 120
Program exited normally.
(gdb)

Point taken?

Thanks to folks here and here

Some other further readings:

If you see any errors, I stand corrected. If you want to share any thoughts/findings on something related, please leave a comment.

Advertisements