Re: Detailed algorithms on inline optimization

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


I guess that is


return (n < 2) ? n + accum : __fib_helper(n - 2, __fib_helper(n - 1, accum));
                                                                                                                                      ^^^^^^^


Also, looking at the code generated by gcc, I guess it made the
following transformation instead:


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


What gcc generates for that is already close to what it generates for
the original fib, but the recursive call is to fib (without passing an
accumulator), so that's not quite it. Let's have another try:


return (n < 2) ? n + accum : __fib_helper(n - 1, fib(n - 2)+accum);


If I don't have fib() in the same compilation unit, the inner loop of
__fib_helper is exactly the same, but there is no inlining going on;
well, at least the tail-call elimination works. If I have fib() in
the same compilation unit, fib() is inlined and the resulting code
looks a little different.


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


Yes, but I think that these patterns occur very rarely in any of the
languages that are implemented by gcc, except in the Fibonacci
benchmark. Especially given that the transformation used is somewhat
different from the classical accumulator transformation.


One interesting property of this transformation is that while the
original version was very parallelizable (with the longest dependence
chain being O(n)), the accumulator version is totally sequential: all
the O(fib(n)) additions are in one chain, because they all add to the
accumulator. The gcc-transformed version looks pretty parallelisable
again (all the fib(n-2) calls are independent of each other), but I
think it's a little less than the original). I don't see any
immediate use for this observation, though.


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