Re: Detailed algorithms on inline optimization

Chris Dodd <cdodd@acm.org> writes:
>unsigned fib(unsigned n) { return n < 2 ? n : fib(n-2) + fib(n-1); }
>
>Gcc 4.3 with -O3 will turn this into a loop via tail-recursion elimination of
>one of the recursive calls


But this is not a tail-recursive function, so turning it into a loop
with only one recursive call needs more than just tail-call
elimination. The inner loop (on AMD64) is:


.L30:
                leal -2(%rbx), %edi
                subl $1, %ebx
                call fib
                addl %eax, %ebp
                cmpl $1, %ebx
                ja .L30


So the compiler has converted the function above to:


do {
    x += fib(n-2);
    n--;
} while (n>1);


plus some stuff around it.


I wonder if this kind of transformation is applicable to functions
occuring in practical programs, or if it is just some Fibonacci
special. If it is the latter, why not transform the function into the
linear non-recursive version?


- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/

Return to the comp.compilers page.
Search the comp.compilers archives again.