Re: Detailed algorithms on inline optimization

Kaz Kylheku <kkylheku@gmail.com>
Thu, 28 Jan 2010 07:29:09 +0000 (UTC)

          From comp.compilers

Related articles
[9 earlier articles]
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: Kaz Kylheku <kkylheku@gmail.com>
Newsgroups: comp.compilers
Date: Thu, 28 Jan 2010 07:29:09 +0000 (UTC)
Organization: A noiseless patient Spider
References: 10-01-058 10-01-061 10-01-079 10-01-085
Keywords: optimize

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); }
>>
>>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


The function can be modified into one that is tail-recursive with
respect to one of the calls, by means of the accumulator-passing style:


unsigned __fib_helper(unsigned n, unsigned accum)
{
    return (n < 2) ? n + accum : __fib_helper(n - 2, __fib_helper(n - 1));
}


unsigned fib(unsigned n)
{
      return __fib_helper(n, 0);
}


My intuition is that this could be implemented by a pattern match that
applies to more than just this specific case.



Post a followup to this message

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