This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

Re: forcing tail/sibling call optimization


On 26-Nov-2000, Robert Dewar <dewar@gnat.com> wrote:
> How about two steps here. First the clear specification, then the decision
> as to whether this extension makes sense (I have trouble seeing what this
> clear specification would look like).

OK.  Here's a specification.  I've followed it with some less formal
explanatory material of the kind that might be suitable for the gcc
manual.

*******************************************************************************
MATERIAL FOR LANGUAGE STANDARD
*******************************************************************************

Syntax:
	Add a new statement production:

		/* tail call statement */
		statement --> GOTO primary "(" exprlist ")" ";"

Static semantics:
	The <primary> expression denotes the address of the callee function.
	It shall have a type which is convertable to function pointer type.
	The <exprlist> denotes the arguments which will be passed to
	the callee function.  They shall have types which are convertible
	to the callee's parameter types.  The callee's return type
	shall exactly match the return type of the containing function.
	[NOTE: Alternatively, that restriction could be relaxed slightly,
	e.g. to say that they shall match modulo `const', `volatile',
	and `restrict' qualifiers.]

	The compiler shall report an error if any of these requirements
	are violated.

Dynamic semantics:
	The dynamic semantics of a tail call statement statement are exactly
	the same as the semantics of the corresponding `return'
	statement, i.e. `return <primary> ( <exprlist> ) ;',
	except that the lifetime of the parameters and local variables
	of the calling function ends sooner.
	In particular, it ends after evaluation of the callee address
	(the <primary> expression) and the <exprlist> arguments,
	before execution transfers to the callee.

	Evaluation of a tail call statement thus proceeds in the following
	steps:
	1. The <primary> expression and the arguments in the <exprlist> are
	   evaluated.  (The order of evaluation is unspecified.)
	2. After they have been evaluated, the lifetime of the calling
	   function's parameters and local variables ends.
	3. Execution transfers to the callee function, whose address was
	   computed by evaluating the <primary> expression in step 1.
	   The parameters of that function are initialized with the
	   values for the arguments computed in step 1.
	4. When the callee function returns, execution will return to
	   the caller's caller.  The value returned from the callee
	   function (if any) will be returned to the caller's caller.

	If the program references the parameters or the local variables
	of the calling function after their lifetime has ended,
	the behaviour is undefined.

Implementation Advice:
	Implementations should implement tail call statements in such
	a way that all storage for the invocation of the calling
	function is reclaimed by the time execution transfers to the
	callee function.

Implementation Requirements:
	Implementations shall issue a warning if there are any tail call
	statements for which the implementation is unable to follow
	the implementation advice.

*******************************************************************************
MATERIAL FOR USER MANUAL
*******************************************************************************

Tail Calls
----------

When the very last thing that a function does is calling another
function (or calling itself recursively), the compiler can sometimes
perform "tail call optimization", whereby it deallocates the storage
used for the caller function's parameters and local variables
*before* calling the callee function.

However, this can only be done if the compiler can prove that
there will be no references to the caller's parameters and
local variables while executing the callee function.
If for instance you take the address of a local variable or
parameter and pass it to a (non-inline) extern function
before the last call, e.g.

	typedef struct { ... } S;
	extern void bar(S *, S *);
	extern void baz(S *);

	void foo(S x) {
		S y;
		bar(&x, &y);
		baz(y);
	}

then the compiler won't be able to perform tail call optimization
on the last call, since it can't be sure that the callee won't
access the caller's local variables or parameters.

GNU C provides an extension called "tail call statements" which lets
you help the compiler do tail call optimization in such circumstances.
A tail call statement has the syntax

	goto <expression> ;

The semantics are the same as

	return <expression> ;

except for the following differences:

	- <expression> must be a function-call expression
	- the return type of the callee must exactly match
	  the return type of the caller
	- the lifetime of the parameters and local variables
	  ends just before execution transfers to the callee
	  (but after the callee function's address and argument
	  values have evaluated)

Using a tail call statement is a strong hint to the compiler that it
should try to perform tail call optimization for this call.  Note
however that in the current implementation, there are some cases where
the compiler will still not be able to perform the optimization.  The
compiler will issue a warning if it can't do tail call optimization
for a tail call statement.

-- 
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
                                    |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]