tail call optimizations

[Richard Henderson <rth at cygnus dot com>]

The following is primarily the work of Jeff Law, though there
are several other Cygnoids that have laid hands on.  My role
has been limited to trying to clean this up so that it applies
to the current fsf development tree.

This has NOT yet been committed. 

The handling of lexical blocks has changed too much in recent
weeks, and the bits of this patch that touch them require external
review.  It was quite a struggle to get things to bootstrap with
debugging enabled, and I'm not sure about some of the new assumptions
that are made or not made as the case may be.

Also, there are C++ frontend tweeks that need to be reviewed.

The theory of operation is quite simple: for each eligible call, 
generate three instruction sequences -- one for a "normal" call,
one for a "sibling" call, and one for tail recursion.  These
are packed into a CALL_PLACEHOLDER pattern and pass relatively
unchanged through inlining.  As one of the first optimization
passes, we build and simplify the CFG for the function.  Calls
that appear at the end of a block that's a predecessor for exit
get replaced by one of the saved tail-call sequences.  All other
calls get replaced by the saved normal call sequence.

There is much room for improvement.  Jeff did the original work for
PA and MIPS; code generation for Alpha must be slightly different,
because functions returning a value are not identified as possible
tail-call sites.  The code that should have noticed is diked out
with a "needs bullet-proofing" comment.  But calls to void functions
are properly transformed, so one can at least experiment.

The patch is much larger than it appears to be due to re-indention
of large sections of calls.c and integrate.c. 

I've just pulled out the Alpha machine-specific portions so far. 
Bits for MIPS and PA exist, and I'll pull them out soon.  I'll
shortly write bits for everyone's favourite platform (x86) so that
the patch can more easily be evaluated.


r~

d-sibcall-1.bz2