Re: Detailed algorithms on inline optimization

anton@mips.complang.tuwien.ac.at (Anton Ertl)
Mon, 25 Jan 2010 10:05:36 GMT

          From comp.compilers

Related articles
[7 earlier articles]
Re: Detailed algorithms on inline optimization jeremy.wright@microfocus.com (Jeremy Wright) (2010-01-20)
Re: Detailed algorithms on inline optimization dot@dotat.at (Tony Finch) (2010-01-21)
Re: Detailed algorithms on inline optimization bear@sonic.net (Ray) (2010-01-21)
Re: Detailed algorithms on inline optimization bobduff@shell01.TheWorld.com (Robert A Duff) (2010-01-21)
Re: Detailed algorithms on inline optimization cdodd@acm.org (Chris Dodd) (2010-01-23)
Re: Detailed algorithms on inline optimization mcrodgers@gmail.com (Martin Rodgers) (2010-01-24)
Re: Detailed algorithms on inline optimization anton@mips.complang.tuwien.ac.at (2010-01-25)
Re: Detailed algorithms on inline optimization monnier@iro.umontreal.ca (Stefan Monnier) (2010-01-25)
Re: Detailed algorithms on inline optimization kkylheku@gmail.com (Kaz Kylheku) (2010-01-28)
Re: Detailed algorithms on inline optimization martin@gkc.org.uk (Martin Ward) (2010-01-28)
Re: Detailed algorithms on inline optimization anton@mips.complang.tuwien.ac.at (2010-01-31)
Re: Detailed algorithms on inline optimization dot@dotat.at (Tony Finch) (2010-02-02)
Re: Detailed algorithms on inline optimization anton@mips.complang.tuwien.ac.at (2010-02-02)
| List of all articles for this month |

From: anton@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups: comp.compilers
Date: Mon, 25 Jan 2010 10:05:36 GMT
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
References: 10-01-058 10-01-061 10-01-079
Keywords: optimize
Posted-Date: 28 Jan 2010 01:17:01 EST

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/



Post a followup to this message

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