Re: proper tail recursion for gcc

[Andreas Schwab <schwab at suse dot de>]

Per Bothner <per@bothner.com> writes:

|> Richard Henderson <rth@cygnus.com> writes:
|> 
|> > On Wed, Jul 19, 2000 at 11:33:08PM -0700, Zack Weinberg wrote:
|> > > We only seem to do the optimization when the argument lists and return
|> > > types are identical.
|> > > 
|> > > Consider, for instance:
|> > > 
|> > > foo(a, b)
|> > > {
|> > >   c = calculate_bar(a, b);
|> > >   foo_with_bar(a, b, c);
|> > > }
|> > > 
|> > > foo_with_bar(a, b, c)
|> > > {
|> > >   ...
|> > > }
|> > > 
|> > > We don't sibcall optimize this, but we could and probably should.
|> > 
|> > No, we can't.  Foo knows that it has room on the stack for
|> > two arguments, since that's what it was given.  Foo_with_bar
|> > requires three arguments, so there's no enough room to 
|> > perform the tail call without changing the caller to pop more
|> > from the stack frame.
|> 
|> It is possible though ugly.  You can adjust the stack frame to
|> make room for the extra argument.  I.e. you change:
|>         a, b, return_pc, fp, locals ...
|> to:
|>         a, b, c, return_pc
|> and then jump to foo_with_bar.
|> When foo_with_bar returns, it will return to foo's caller, which
|> will pop off b and c.  a remains on the stack, but does no harm.
|> When foo's caller returns, a will get popped, just as if a had
|> been alocated with alloca.

This means that the stack grows without bounds if foo's caller never
returns and calls foo in an infinite loop, e.g:

toplevel()
{
  for (;;)
    foo(a,b);
}

Andreas.

-- 
Andreas Schwab                                  "And now for something
SuSE Labs                                        completely different."
Andreas.Schwab@suse.de
SuSE GmbH, Schanzäckerstr. 10, D-90443 Nürnberg