forcing tail/sibling call optimization

[Fergus Henderson <fjh at cs dot mu dot oz dot au>]

Hi,

I would like to propose an extension to GNU C.  I'm willing to
implement it, but first I'd like to test the waters here to see
the reaction.

The basic idea is to provide a way for the programmer to tell
the C compiler that a particular call should be treated as
a sibling call or tail call, even if the compiler can't prove
that the storage for the locals is no longer live.

For example, for code such as

	extern void bar(int *, int *);
	extern void baz(int);

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

the compiler won't be able to perform sibling call optimization, since
it can't be sure that bar() doesn't save the addresses of x and y in
some storage that is accessible to baz().  I would like some way to
tell the compiler to go ahead and perform the sibling call
optimization anyway.

This feature is important for compilers of high-level functional and
logic programming languages that target C.  For such languages,
recursion is the primary form of iteration, and it is important that
sibling calls be optimized.  Often the high-level language compiler
has more information about when it is safe to do tail calls than gcc
has, but currently there is no way for the high-level language
compiler to communicate that to gcc.

The language C-- (see <www.cminusminus.org>), which is designed to be
ideal as a target language, provides this feature.  I would like
GNU C to provide it too.

So, any comments?  If I were to provide a clean patch that implements
this feature, together with documentation giving a clear specification,
would you be happy to have this change included in future versions of
GNU C?

I'm not sure what the best syntax for the extension would be.
One possibility is to insert a new keyword `__tailcall' before
such calls:

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

Another alternative is to reuse the `goto' keyword

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

-- 
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.