GCCJIT and proper tail calls

[Marc Nieper-Wißkirchen]

If GCC (and possibly a further ISO C dialect) included a way to express 
that a certain call should be compiled as a proper tail call (that is, 
as a jump), that would be awesome.

There is a proposal for the Rust language which uses the keyword 
`become' instead of `return' to express an explicit tail call. If the C 
front-end of GCC has a way to express explicit tail calls (and thus the 
middle- and back-ends include support for it), say `return __musttail__ 
f(x)', the contract could be that

(a) the call is in fact in tail position,
(b) the tail-called function has the same (or an equivalent) prototype 
as the caller, and
(c) no automatic variables of the caller are accessed anymore after the 
tail-call happened.

The point of (c) is that it solves the problem discussed here: 
http://www.drdobbs.com/tackling-c-tail-calls/184401756. The example code is:

int* global;
bar ()
{
   ...
   *global = 42;
}
foo ()
{
   ...
   global = &local;
   ...
   bar ();
}

(a) could be verified statically,
(b) could be either verified statically or (when violated) lead to 
undefined behaviour, and
(c) would lead to undefined behaviour if the contract was broken.

In case the current backends of GCC are not able to do proper tail calls 
even in case the restrictions (a) - (c) are fulfilled, one may have to 
add another part (d) to the contract to have reliable proper tail calls 
in a well-defined subject.

Tail recursion (a function tail-calls itself), while often being cited 
when trying to explain the benefits of proper tail call elimination, is 
less of a problem for language front-ends, because these kind of tail 
calls can be statically detected and rewritten by the front-end. The 
true power of proper tail call elimination comes from eliminating 
sibling tail calls because this is in some sense a global program 
transformation.

As a side note: The other JIT compiler of the GNU project, GNU 
lightning, does support proper tail call elimination (again in some 
restricted, but reliable form). They use the word trampoline for it: 
https://www.gnu.org/software/lightning/manual/lightning.html. While the 
use cases of GNU lightning are somewhat different from those of gccjit, 
it would be nice if the two JIT implementation would be on par in that 
regard.

--

Marc

Am 13.05.2016 um 06:19 schrieb Basile Starynkevitch:
> On 05/12/2016 09:59 PM, David Malcolm wrote:
>
>  > Do any Scheme implementations auto-generate C?
>
> Several of them do. Chicken Scheme https://www.call-cc.org/ and Bigloo
> https://www-sop.inria.fr/indes/fp/Bigloo/ notably.
>
> Also, Christian Queinnec wrote an excellent book: Lisp In Small Pieces
> https://pages.lip6.fr/Christian.Queinnec/WWW/LiSP.html which explain in
> great details several (interpreted & compiled) implementations of Lisp,
> including a Scheme translator to C.
>
> The common point is that none the Scheme to C compilers I know are
> expecting or building upon the ability of the C compiler to emit proper
> tail-recursive calls. So GCCJIT really needs support for that (and IMHO,
> GCC itself should have a pragma to check that and warn if a given call
> cannot be compiled as a tail-calll).
>
> Regards.
>