This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: forcing tail/sibling call optimization
- To: dewar at gnat dot com (Robert Dewar)
- Subject: Re: forcing tail/sibling call optimization
- From: Fergus Henderson <fjh at cs dot mu dot oz dot au>
- Date: Mon, 27 Nov 2000 02:44:03 +1100
- Cc: gcc at gcc dot gnu dot org
- References: <20001126130053.4A71E34D81@nile.gnat.com>
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.