Re: proper tail recursion for gcc

[Jakub Jelinek <jakub at redhat dot com>]

On Wed, Jul 19, 2000 at 11:33:08PM -0700, Zack Weinberg wrote:
> On Wed, Jul 19, 2000 at 11:06:08PM -0700, Geoff Keating wrote:
> > 
> > Mark Probst <schani@mips.complang.tuwien.ac.at> writes:
> > 
> > > i want to implement proper tail recursion for a much broader set of
> > > cases than is currently implemented.
> > ...
> > 
> > I think you'll find this has already been done in the development gcc.
> > It's the 'sibling call' optimisation.
> 
> It's not as complete as a Scheme compiler is required to implement.
> The Scheme standard requires sibcall optimization for *every* function
> call followed immediately by a return from the current function.  We

There must be exceptions, like if you take an address of some local variable and pass
it to some other functions...

> 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.
> [Perhaps this is the sort of thing that would be handled by the
> "better tree-based sibcall optimizer" coming RSN?]

I believe the problem here is not if we use tree-based or
expand_call/rtl-based sibcall optimizer, the issues are backend related.
Basically, if the incoming arguments stack area of the tail function is
larger than of tail callee, then you have to allocate some area immediately
below virtual-incoming-args-rtx to compensate it and in a machine specific
way copy machine dependent stuff down (or up, depending on stack growth),
e.g. on Intel the return address stored on the stack.
It is IMHO worth implementing, but under a separate -f switch not enabled by
default from -O options, because I don't think it will be a win for random C
code.
(BTW: The above example will be optimized on SPARC (if there are less than 6
word size arguments in both prototypes)).

	Jakub