Re: GCCJIT and proper tail calls

[David Malcolm <dmalcolm@redhat.com>]

On Fri, 2016-05-13 at 08:23 +0200, Marc Nieper-Wißkirchen wrote:
> 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.


Thanks Marc and Basile.  I've been experimenting with this; I have a
patch which adds a new libgccjit entrypoint:

extern void
gcc_jit_rvalue_set_bool_require_tail_call (gcc_jit_rvalue *call,
					   int require_tail_call);

and this successfully sets a new flag on the CALL_EXPR (in gcc's "tree"
representation), but the flag doesn't yet do anything in the RTL
expansion phase.

My planned next step is to do it for some C code to easily exercise the
code generator.  I'm thinking of using a compiler plugin to manually
set the flag on the calls (to avoid needing any C syntax for this).

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