[gclist] tail-calls in C/C++

[Bill Bill]

|   Sender: majordom@iecc.com (MajorDomo)
|   Date: Mon, 05 Aug 1996 17:55:02 -0400
|   From: Greg Morrisett <jgm@CS.Cornell.EDU>

|   Why hasn't someone hacked gcc to do full tail-call elimination?
|   With the Boehm-Weiser collector, this is really the only thing
|   that's keeping me from generating very good C code from ML and
|   Scheme.  

I too would like to see this, but in general it would have to be
enabled by a command-line option to the compiler because it
effectively violates C semantics.

The problem is the folloowing:

	Assume A calls B which in turn tail-calls C
	Either B uses ... or no prototype for B is visible at A.

Thus A can call B with more arguments (and hence locations on the
stack) than the number expected by B.

Since B (in general) does not know how many arguments it was passed,
it cannot in general pop its arguments from the stack.  That job is
left to A which does so (lazily in some compilers) on return from B.

Assume now that B calls C with more arguments than B thinks it got
(e.g. B names X formal parameters but passes X+1 arguments to C).  B
will have to "grow" the stack frame before calling C.

Now if B is "left on the stack" (i.e. no tail call elimination
perform), on return from C, B will pop the new frame, and by the time
control returns to A, only those words that A pushed will be on the
stack.

However, if B is eliminated, on eventual return from C to A, A will
pop the wrong number of words from the stack, and you will have a
broken program.

There are a lot of calling conventions that can be used to fix this
(e.g. passing an argument count and letting the callee pop), but
previously compiled code and code compiled with other compilers will
not observe these conventions, hence C compilers won't do it.

However, a C compiler could implement a more general partial tail call
elimination by observing that it is always legal to tail-call
procedures when you pass no more argument words than you yourself
declare (i.e. when the stack does not need to grow for the tail call).

In addition, when the calling convention passes some number of
arguments in registers that are not backed up by locations in memory
(common in RISC machines), the tail call can be done if all the
arguments fit in the calling-convention's argument registers.

Thus a C compiler could implement tail calls safely when the following
condition is satisfied:

	(   (number-of-arguments <= number-of-argument-registers)
	 or (number-of-arguments <= number-of-formals-of-caller))

Scheme and ML compilers could effectively restrict themselves to this
(e.g. by declaring dummy arguments) to guarantee correct tail-call
behavior.