Re: Detailed algorithms on inline optimization

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.

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