GCCJIT and proper tail calls

[Marc Nieper-WiÃkirchen <marc@nieper-wisskirchen.de>]

Last year there was a discussion on the gccjit mailing list whether it 
is possible to guarantee the elimination of proper tail calls.

Compiling Scheme code with gccjit was given as an example because the 
language demands proper tail call elimination (for example, loops are 
usually implemented by recursive function calls).

The point I would like to make that proper tail call elimination on 
gccjit's side remains crucial even if Scheme didn't ask for proper tail 
call elimination: Scheme allows programs to get hold of the current 
continuation of the program. One way to implement this is to globally 
rewrite the program into continuation-passing style. In other words, 
every call (outside of calling library functions) would become a proper 
tail call. If gccjit chose not to eliminate the calls in favour of 
jumps, the stack usage of the transformed program would be proportional 
to its running time.

LLVM has the `musttail' marker 
http://llvm.org/docs/LangRef.html#call-instruction 
<http://llvm.org/docs/LangRef.html#call-instruction> to guarantee proper 
tail call elimination independent of any optimization pass (or to signal 
an error in case the requirements for the elimination are not met).

Such a thing should be possible for gccjit as well (so that the 
aforementioned program in continuation-passing style would still work 
even without an optimization pass eliminating non-marked proper tail calls).

--

Marc