Re: Tail sets

[Per Bothner <per at bothner dot com>]

On 03/15/2009 01:42 AM, Helmut Eller wrote:
> At least CMUCL recognizes that those three
> calls have the same continuation and compiles the calls as direct
> jumps.  It seems to me, that Kawa compiles them as ordinary calls (and
> presumably has to allocate a closure).  Would it be hard to teach the
> compiler to optimize situations like the above?

It shouldn't be that difficult.  If you look at the commented-out
pseudo-code in FindTailsCalls.walkLambdaExp that is what it tries to do.

Kawa will currently inline a procedure if there is just a single
call site, plus optional self-tail-recursion: Self-tail-recursion
is easy to implement as a jump to the start of the generated code,
and if there is a single non-self-tail-recursion call-site we can
just generate the bytecode at the location of that call-site.

Your example is a different case: A function 'fail' is called
multiple times, but all calls are tail-calls in the same
containing function.  That can be compiled as a block of code
which returns from the outer function, and then all of the calls
to 'fail' becomes jumps to that block of code.

That should be doable, but for it to be worthwhile I think
we want to generalize it to a set of functions that make
mutual tailcalls to each other.  This can support the
standard "state machine through tail-calls" idiom, which
would be nice.

The goal of the commented-out algorithm in FindTailsCalls.walkLambdaExp
is to find such "inline sets".  Once we have those inline sets code
generation should be easy,

So no, I don't think it would be hard to optimize this.
In fact I think it would be a very worthwhile project for someone
who wants to learn more of Kawa internals ...
--
	--Per Bothner
per@bothner.com   http://per.bothner.com/