[PATCH 0/6] jit: Work-in-progress implementation of must-tail-call
Marc Nieper-Wißkirchen
marc@nieper-wisskirchen.de
Fri Jan 1 00:00:00 GMT 2016
David,
thank you a lot for seeing about the matter! Here is a bit more on the
problem with taking the address of locals of the tail caller:
Consider the following program:
#include <stdio.h>
void (*f) (int);
void g (int a)
{
int b;
a = scanf ("%i", &b);
return f(a);
}
Here, the compiler is not able to substitute the call to f with a jump
because I take the address of the local variable b and the compiler
cannot know whether scanf stores it in some unknown global or not. So it
has to keep b alive until the end of the function g.
Now if I wrote something like
#include <stdio.h>
void (*f) (int);
void g (int a)
{
int b;
a = scanf ("%i", &b);
return __musttail__ f(a);
},
I don't want the compiler to emit an error that a sibling tail jump is
not possible by the reasons above. What I want is that the compiler does
the jump while taking it for granted that the location of b won't be
accessed anymore when control enters the function f. (In some sense,
__musttail__ thus behaves like restrict. It is the programmers
responsibility that a certain contract is fulfilled.)
Marc
Am 13.05.2016 um 22:17 schrieb David Malcolm:
> On Fri, 2016-05-13 at 15:59 +0200, Basile Starynkevitch wrote:
>> 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.
> Here's a work-in-progress patchkit that implements the ideas we've
> been discussing.
>
> Does this look like what's needed? (albeit with lots of FIXMEs)
>
> (FWIW, this is on top of trunk's r236180, plus the FINAL/OVERRIDE patch
> from https://gcc.gnu.org/ml/gcc-patches/2016-05/msg00521.html )
>
> David Malcolm (6):
> FIXME: introduce can_implement_as_sibling_call_p
> FIXME: WIP on non-jit part of must-tail-call
> FIXME: WIP on jit part of must-tail-call
> FIXME: non-working scanasm test
> FIXME: initial support for gcc diagnostics as jit errors
> FIXME: jit: add test of failing must-TCO
>
> gcc/calls.c | 187 ++++++++++++++++-----
> gcc/cfgexpand.c | 1 +
> gcc/gimple-pretty-print.c | 2 +
> gcc/gimple.c | 1 +
> gcc/gimple.h | 19 +++
> gcc/jit/dummy-frontend.c | 36 ++++
> gcc/jit/jit-common.h | 1 +
> gcc/jit/jit-playback.c | 23 ++-
> gcc/jit/jit-playback.h | 9 +-
> gcc/jit/jit-recording.c | 42 +++--
> gcc/jit/jit-recording.h | 43 +++--
> gcc/jit/libgccjit.c | 18 ++
> gcc/jit/libgccjit.h | 5 +
> gcc/jit/libgccjit.map | 5 +
> gcc/print-tree.c | 2 +-
> gcc/testsuite/gcc.dg/plugin/must-tail-call-1.c | 22 +++
> gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c | 15 ++
> gcc/testsuite/gcc.dg/plugin/must-tail-call-3.c | 14 ++
> .../gcc.dg/plugin/must_tail_call_plugin.c | 76 +++++++++
> gcc/testsuite/gcc.dg/plugin/plugin.exp | 4 +
> gcc/testsuite/jit.dg/all-non-failing-tests.h | 7 +
> .../jit.dg/test-error-impossible-must-tail-call.c | 93 ++++++++++
> .../jit.dg/test-factorial-must-tail-call.c | 109 ++++++++++++
> gcc/tree-core.h | 3 +
> gcc/tree.h | 4 +
> 25 files changed, 661 insertions(+), 80 deletions(-)
> create mode 100644 gcc/testsuite/gcc.dg/plugin/must-tail-call-1.c
> create mode 100644 gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c
> create mode 100644 gcc/testsuite/gcc.dg/plugin/must-tail-call-3.c
> create mode 100644 gcc/testsuite/gcc.dg/plugin/must_tail_call_plugin.c
> create mode 100644 gcc/testsuite/jit.dg/test-error-impossible-must-tail-call.c
> create mode 100644 gcc/testsuite/jit.dg/test-factorial-must-tail-call.c
>
More information about the Jit
mailing list