Thu, 28 Jan 2010 07:29:09 +0000 (UTC)

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

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.