Sun, 31 Jan 2010 16:18:14 GMT

Related articles |
---|

[11 earlier articles] |

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

From: | anton@mips.complang.tuwien.ac.at (Anton Ertl) |

Newsgroups: | comp.compilers |

Date: | Sun, 31 Jan 2010 16:18:14 GMT |

Organization: | Institut fuer Computersprachen, Technische Universitaet Wien |

References: | 10-01-058 10-01-061 10-01-079 10-01-085 10-01-092 |

Keywords: | optimize |

Posted-Date: | 01 Feb 2010 18:24:35 EST |

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/

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.