This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: Recursion Optimization
- To: Kevin Atkinson <kevinatk at home dot com>
- Subject: Re: Recursion Optimization
- From: Andreas Schwab <schwab at suse dot de>
- Date: 16 Aug 1999 18:26:50 +0200
- Cc: gcc at gcc dot gnu dot org
- References: <Pine.GSO.4.10.9908161213250.4524-100000@sun00epsl.wam.umd.edu>
Kevin Atkinson <kevinatk@home.com> writes:
|> On 16 Aug 1999, Andreas Schwab wrote:
|>
|> > Kevin Atkinson <kevinatk@home.com> writes:
|> >
|> > |> Does gcc optimize in any way to minimize the cost of recursive functions
|> > |> calls. In particular:
|> > |>
|> > |> ONE:
|> > |>
|> > |> Does gcc optimize tail recursive functions into simple loops?
|>
|> You never answered this question.
Because I don't know the answer. I do not know everything.
|> > |> TWO:
|> > |>
|> > |> In a function call like this:
|> > |>
|> > |> int sum(int i, int stop) {
|> > |> }
|> >
|> > This is not a tail recursive function.
|>
|> I know.
|>
|> > |> Will gcc recognize that the value of the second parameter never changes
|> > |> so that it can avoid allocating multiple copies of it on the stack.
|> >
|> > This cannot be avoided.
|>
|> What do you mean, cannot.
How can you provide a contiguous argument list on the stack for the
recursive call without the copy?
|> Gcc can handel nested functions, so with a smart enough optimization
|> technoligy it out to be able to rewrite it as
|>
|> int sum (int i, int stop) {
|> int sumh(int i) {
|> if (i == stop) return i;
|> else return sum(i+1, stop) + i;
|> }
|> return sumh(i);
|> }
In which way is this different from the previous version? You still have
the same call to sum which requires a contiguous argument list on the stack.
--
Andreas Schwab "And now for something
schwab@suse.de completely different."
SuSE GmbH, Schanzäckerstr. 10, D-90443 Nürnberg