Re: forcing tail/sibling call optimization

[hjstein at bfr dot co dot il (Harvey J. Stein)]

Jeffrey A Law <law@redhat.com> writes:

 > In message <20001127164400.0929334D80@nile.gnat.com>you write:
 > > 
 > > I think this misses the point, this is not just an optimization,
 > > it is a fundamental functional capability, in other words, we
 > > would want the compiler to do this EVEN IF it slowed down
 > > execution.
 >
 > I don't care if slows down or speeds up execution -- dependence on
 > this kind of transformation in languages such as C is terribly bad.
 > C code which relies on this transformation is broken.

It would be a nice thing to have for Scheme implementations.  Lots of
Scheme implementations these days translate to C & then use the C
compiler.  Those that translate Scheme fcns to C fcns are the simplest
to build and understand (not to mention allowing reasonably clean use
of the debugger on the compiled code), but are not properly tail
recursive, as the Scheme standards require.  Those that are properly
tail recursive translate to one big ugly C function and implement
calling conventions themselves.  This is more work, isn't so great for
readability of the C code, strains the C compiler, and has problems
with C<->Scheme interoperability.

Trying to make C properly tail recursive is probably impossible.  In
C, the caller is responsible for pushing and popping arguments onto
and off of the stack, making tail recursion elimination a global
optimization problem instead of a local problem.

However, it becomes trivial with different calling conventions.  If
the caller was responsible for pushing arguments onto the stack and
the callee was responsible for popping the arguments, the callee would
be in a position to rewrite the stack whenever it's jumping to another
function instead of calling it.  That's all that's required for proper
tail recursion, namely rewriting the stack and jumping instead of
pushing the stack and calling whenever the function is going to return
what the callee returns.

This modified calling convention may also require telling the callee
how much stack space the caller used to call the callee, which
probably requires an additional argument or a register dedicated to
such.  This might only be needed, however, for variable argument
functions.

If one were to add support for this alternate calling convention (say
with a command line switch), then Scheme implementers (and anyone else
who needs proper tail recursion) would at least be able to compile
self contained Scheme programs by doing straight Scheme fcn -> C fcn
translation and wouldn't lose proper tail recursion.

If one were to add support for this directly into the language
supported by gcc (for example, with function attributes), then it
could be used to preserve proper tail recursion while still supporting 
standard calling conventions, thus enabling proper tail recursion as
well as utilization of all the standard libraries.

There're also some precedents for doing both of these.  For one thing,
you see it in MSDOS with the PASCAL vs C calling conventions.  For
that matter, GCC already has -mrtd as well as the __stdcall__
attribute, and aside from telling the callee the amount of stack space
the caller used, these are basically all that's needed wrt to calling
convention changes.

Of course, in addition to supporting this calling convention, GCC has
to take advantage of it.  To get proper tail recursion with these
calling conventions, all GCC would have to do is when it's compiling a
function (call it F) which uses this alternate calling convention, and
F calls a function (call it G) which also uses this alternate calling
convention, and F is merely calling G and returning whatever G
returns, then instead of pushing G's args, calling G, poping G's args
& returning what G returned, it should pop F's args, push G's args &
jump to G.  It can jump to G directly because G is going to pop its
own args.  It can rewrite the stack because in this calling
convention, F is responsible for cleaning up the stack, instead of the
caller of F being responsible.

In fact, for the implementers of properly tail recursive languages,
all that would be needed would be that GCC do the above for code of
the form return(g(....)).

Given that GCC is already so close to being able to do this, why not
just take the last step?

-- 
Harvey Stein
Bloomberg LP
hjstein@bfr.co.il