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} ***