Re: Detailed algorithms on inline optimization

anton@mips.complang.tuwien.ac.at (Anton Ertl)
Tue, 02 Feb 2010 14:14:16 GMT

          From comp.compilers

Related articles
[13 earlier articles]
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: Tue, 02 Feb 2010 14:14:16 GMT
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
References: 10-01-058 10-01-061 10-01-079 10-01-085 10-01-092 10-02-006
Keywords: optimize
Posted-Date: 02 Feb 2010 23:09:50 EST

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>Kaz Kylheku <kkylheku@gmail.com> writes:
>>On 2010-01-25, Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>>> Chris Dodd <cdodd@acm.org> writes:
>>>>unsigned fib(unsigned n) { return n < 2 ? n : fib(n-2) + fib(n-1); }


[and the interesting code that gcc generates from that]


Here's another version:


unsigned fib(unsigned n)
{
    unsigned accum=0;
    for (; n>1; n--)
        accum += fib(n-2);
    return n+accum;
}


Apart from some differences in register and stack allocation, gcc
generates the same code for this as for the code above (including the
number of inlinings), so it's likely that gcc transforms the
doubly-recursive version above into something like this version.


I don't think that this can be expressed as a tail-recursive function
without helper function.


- 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.