Re: forcing tail/sibling call optimization

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

On 27-Nov-2000, Jeffrey A Law <law@redhat.com> wrote:
> Instead of tagging the return itself, couldn't we use an attribute which
> would (in effect) tell the optimizer that any tail call in the function
> is safe to optimize?  Yes, we lose the ability to specify that a specific
> call site is safe to optimize, but we don't have to invent yet another
> GCC extension of dubious value.

I'd be happy to change the syntax to use "statement attributes"

	__attribute__((__tailcall__)) return func(args);

or "expression attributes"

	return __attribute__((__tailcall__)) func(args);

But putting the attribute on the caller function rather than on the
call is not a good idea, IMHO.  It's just not a good match for the
problem.  It would be harder for front-ends that target GNU C to
generate such an attribute, and the result would be less useful.
For languages that want guaranteed tail call optimization, it would
be much less useful, since putting the attribute on the caller function
means that if the caller contains any tail call which is not safely
optimizable then none of the tail calls will get optimized.

In the C code that the Mercury compiler generates, you can certainly
have functions that contain both tail calls that can safely be
optimized and tail calls that can't.

For example, Mercury code such as

	:- mode foo(in, in, out).
	foo(A, B, C) :-
		Z = quux(A),
		if Z > 0 then
			bar(A, B, C, _D)
		else
			baz(A, B, C).

	:- mode bar(in, in, out, out).
	:- mode baz(in, in, out).

will compile to something like

	foo(int a, int b, int *c) {
		int z = quux(a);
		if (z > 0) {
			int d;
			bar(a, b, c, &d);
		} else {
			baz(a, b, c);
		}
	}

and although it's safe to tailcall baz(), it's not safe to tailcall bar().

My guess is that the same is true of other compilers for function/logic 
languages which target C.

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