Re: Tail call elimination

[Per Bothner <per at bothner dot com>]

Jeffrey A Law <law@cygnus.com> writes:
> That implementation is mostly useless.  It has to be handled *much* earlier
> in the compiler.  But the net result is something that is orders of magnitude
> cleaner and more portable.

Detecting that something is a tail-call should probably be done
at the tree-level.  However, the actual hard part of mucking about
with the stack presumably needs to be done at a rather low level?

One problem is that standard C calling conventions (designed to
handle varargs, thus the *caller* pops the arguments) is
fundamentally unfriendly to tail-call elimination (which works
best if the *callee* pops the arguments).

The fully general case gets pretty ugly.  It is relatively simple
if the target function has the same parameter types as the
caller (just evaluate the arguments into their proper outgoing
parameter locations, and jump to the target's address).  However,
it can get quite hairly if the parameter types are different,
as you may have to do some nasty stack adjustment and copying.

Supporting just the "same-parameter-types" tail-call would be
very valuable in itself, though, as it would provide a cleaner
solution for those people who want to compile certain languages
(Scheme, ML, ...) into C.
-- 
	--Per Bothner
bothner@pacbell.net  per@bothner.com   http://www.bothner.com/~per/