proper tail recursion for gcc

[Richard Henderson]

On Wed, Jul 19, 2000 at 11:33:08PM -0700, Zack Weinberg wrote:
> 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.

Indeed.  And such complete tail call optimizations are impossible
with a stack-based call frame, such as is used for C and so forth.
For Scheme one must put call frames in the heap and garbage collect them.

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

I believe you will find that this example does get transformed 
to a tail call on Sparc, since in this case all arguments will 
be in registers.

> [Perhaps this is the sort of thing that would be handled by the
> "better tree-based sibcall optimizer" coming RSN?]

No, the tree-based sibcall optimizer just makes the analysis 
easier and the code cleaner.  It does not change the calling
convention dependant restrictions placed on the optimization.



r~