* Re: GCCJIT and proper tail calls
2016-01-01 0:00 ` David Malcolm
@ 2016-01-01 0:00 ` Basile Starynkevitch
0 siblings, 0 replies; 6+ messages in thread
From: Basile Starynkevitch @ 2016-01-01 0:00 UTC (permalink / raw)
To: David Malcolm, Marc Nieper-Wißkirchen, jit
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} ***
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: GCCJIT and proper tail calls
2016-01-01 0:00 ` Marc Nieper-Wißkirchen
@ 2016-01-01 0:00 ` David Malcolm
2016-01-01 0:00 ` Basile Starynkevitch
0 siblings, 1 reply; 6+ messages in thread
From: David Malcolm @ 2016-01-01 0:00 UTC (permalink / raw)
To: Marc Nieper-Wißkirchen, Basile Starynkevitch, jit
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.
> >
^ permalink raw reply [flat|nested] 6+ messages in thread
* GCCJIT and proper tail calls
@ 2016-01-01 0:00 Marc Nieper-Wißkirchen
2016-01-01 0:00 ` David Malcolm
0 siblings, 1 reply; 6+ messages in thread
From: Marc Nieper-Wißkirchen @ 2016-01-01 0:00 UTC (permalink / raw)
To: jit
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
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: GCCJIT and proper tail calls
2016-01-01 0:00 GCCJIT and proper tail calls Marc Nieper-Wißkirchen
@ 2016-01-01 0:00 ` David Malcolm
2016-01-01 0:00 ` Basile Starynkevitch
0 siblings, 1 reply; 6+ messages in thread
From: David Malcolm @ 2016-01-01 0:00 UTC (permalink / raw)
To: Marc Nieper-Wißkirchen, jit
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
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: GCCJIT and proper tail calls
2016-01-01 0:00 ` David Malcolm
@ 2016-01-01 0:00 ` Basile Starynkevitch
2016-01-01 0:00 ` Marc Nieper-Wißkirchen
0 siblings, 1 reply; 6+ messages in thread
From: Basile Starynkevitch @ 2016-01-01 0:00 UTC (permalink / raw)
To: David Malcolm, Marc Nieper-Wißkirchen, jit
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} ***
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: GCCJIT and proper tail calls
2016-01-01 0:00 ` Basile Starynkevitch
@ 2016-01-01 0:00 ` Marc Nieper-Wißkirchen
2016-01-01 0:00 ` David Malcolm
0 siblings, 1 reply; 6+ messages in thread
From: Marc Nieper-Wißkirchen @ 2016-01-01 0:00 UTC (permalink / raw)
To: Basile Starynkevitch, David Malcolm, jit
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.
>
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2016-05-13 13:59 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2016-01-01 0:00 GCCJIT and proper tail calls Marc Nieper-Wißkirchen
2016-01-01 0:00 ` David Malcolm
2016-01-01 0:00 ` Basile Starynkevitch
2016-01-01 0:00 ` Marc Nieper-Wißkirchen
2016-01-01 0:00 ` David Malcolm
2016-01-01 0:00 ` Basile Starynkevitch
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).