GCCJIT and proper tail calls

GCCJIT and proper tail calls

[Marc Nieper-Wißkirchen]

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

Re: GCCJIT and proper tail calls

[David Malcolm]

On Wed, 2016-05-11 at 09:38 +0200, Marc Nieper-Wißkirchen wrote:
> Last year there was a discussion on the gccjit mailing list whether
> it 
> is possible to guarantee the elimination of proper tail calls.

For reference, here's the archive for that discussion:
https://gcc.gnu.org/ml/jit/2015-q3/msg00065.html

I didn't understand the significance at the time; sorry.

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

Thanks for the explanation.  I think I understand now.

I did some investigation; some notes:

gcc can do tail-call optimization both at the gimple level, and at the
RTL level.

For the gimple level an example is here:
  https://gcc.gnu.org/onlinedocs/gcc-6.1.0/jit/intro/tutorial04.html#el
imination-of-tail-recursion
It's in "tailr", a gimple pass; it optimizes tail-recursion into
iteration (gcc/tree-tailall.c).  This pass also sets up some flags for
sibling-call optimization at the RTL level.

Relevant gimple flags:
enum gf_mask
  There's a GF_CALL_TAILCALL
  and there's room for more GF_CALL_ flags

GF_CALL_TAILCALL is:
  * set/cleared by gimple_call_set_tail
  * queried by gimple_call_tail_p

cfgexpand.c has:
  CALL_EXPR_TAILCALL (exp) = gimple_call_tail_p (stmt);

which then gets used in calls.c:expand_call for turning a CALL_EXPR
rtx_insn into lower-level insns.

However there are various ways in which gcc can decide not to do TCO,
e.g. these comment from calls.c:

  /* Tail calls can make things harder to debug, and we've traditionally
     pushed these optimizations into -O2.  Don't try if we're already
     expanding a call, as that means we're an argument.  Don't try if
     there's cleanups, as we know there's code to follow the call.  */

and the code below here in calls.c.

  /*  Rest of purposes for tail call optimizations to fail.  */


So it sounds like implementing this would require the following:

(a) internally we'd need another flag e.g.:

  GF_CALL_MUSTTAILCALL

or somesuch, and presumably a CALL_EXPR_MUSTTAILCALL

(b) exposing some way of setting the flag from the libgccjit.h API.

Currently to construct a tail call in libgccjit you need to do
something like:

  gcc_jit_rvalue *return_val = gcc_jit_context_new_call (/* args */);
  gcc_jit_block_end_with_return (block, loc, return_val);

There are two ways to construct a call:
  gcc_jit_context_new_call
  gcc_jit_context_new_call_through_ptr
and two ways to build a return:
  gcc_jit_block_end_with_return
  gcc_jit_block_end_with_void_return

Perhaps the API entrypoint would be to mark the call rvalue, with
something like:

  extern void
  gcc_jit_rvalue_set_tail_call (gcc_jit_rvalue *rvalue,
                                int is_tail_call);

to avoid having to add another flag to the new_call API entrypoints.

(c) to extend gcc/calls.c to support this flag.  This could well be non
-trivial - the function in question (expand_call) is over 1000 lines
long, and there's various platform specific logic in the relevant code.
 Would it be acceptable to issue an error if one of the issues arises?
This function turns calls into lower-level RTL instructions; it first
attempts to generate the insns for a sibling call, but if that fails it
falls back to making the insns for a "normal" call.  Presumably we want
to make sure that flagged calls use the sibling-call form of the RTL.

(d) test cases, docs, etc.

I'm a bit nervous about having a jit-specific backend feature; I wonder
if this is something we could expose in the C/C++ frontends somehow
(attributes, pragmas, a command-line flag, etc?).  Do any Scheme
implementations auto-generate C?

Dave

Re: GCCJIT and proper tail calls

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

-- 
Basile STARYNKEVITCH         http://starynkevitch.net/Basile/
email: basile<at>starynkevitch<dot>net mobile: +33 6 8501 2359
8, rue de la Faiencerie, 92340 Bourg La Reine, France
*** opinions {are only mine, sont seulement les miennes} ***

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

Re: GCCJIT and proper tail calls

[David Malcolm]

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

Re: GCCJIT and proper tail calls

[Basile Starynkevitch]

On 05/13/2016 03:29 PM, David Malcolm wrote:
> 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.
I believe that would be a really good idea.


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

If pushing into GCC trunk some pragma (for C only, not for C++), perhaps

    #pragma GCC expect_tail_call
    /* warn if the following call to foobar is not a tail-recursive call */
    foobar(x,y)

is not too hard, I believe it is the way to go. Because such a pragma 
would be extremely useful
to the many compiler writers which are emitting C code. Of course the 
syntax of such pragma could be improved (and maybe discussed with 
Clang/LLVM folks, to agree on a common syntax).
But my belief is that many compilers which are emitting C code would be 
very happy with such a pragma (and perhaps even some low-level system or 
application coders).

My point is that tail recursion is really important. A lot of languages 
(Scheme, Ocaml) are requiring it
in the language specification. So implementations won't emit C code and 
pray that GCC is doing the
right thing. They need to be "sure" of that.

Of course, if adding such a pragma is too hard, that is a different 
story. If it is simpler to make it some builtin, that is ok. Or it might 
be some syntax extension, perhaps goto return foobar(x,y);

Cheers.

-- 
Basile STARYNKEVITCH         http://starynkevitch.net/Basile/
email: basile<at>starynkevitch<dot>net mobile: +33 6 8501 2359
8, rue de la Faiencerie, 92340 Bourg La Reine, France
*** opinions {are only mine, sont seulement les miennes} ***