GCCJIT and tail-recursive calls

GCCJIT and tail-recursive calls

[Basile Starynkevitch]

Hello all,

It is well known that GCC is sometimes able to optimize some calls to 
tail-recursive calls (or tail calls
https://en.wikipedia.org/wiki/Tail_call ...) which do not consume any stack.

can a GCCJIT application issues such tail calls? I'm not talking of 
letting GCC decide entirely by itself (GCCJIT is probably doing that 
already). I was thinking of adding a construct where the GCCJIT client knows
for sure that the call should be tail-rec (and if GCCJIT was not able to 
make a tailcall, that would be an error).
Also, even without optimization (i.e. at -O0) that should remain a 
tailcall...

Perhaps adding a gcc_jit_block_end_with_tail_call function?

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 tail-recursive calls

[David Malcolm]

On Fri, 2015-07-10 at 00:30 +0200, Basile Starynkevitch wrote:
> Hello all,
> 
> It is well known that GCC is sometimes able to optimize some calls to 
> tail-recursive calls (or tail calls
> https://en.wikipedia.org/wiki/Tail_call ...) which do not consume any stack.
> 
> can a GCCJIT application issues such tail calls? I'm not talking of 
> letting GCC decide entirely by itself (GCCJIT is probably doing that 
> already).  

gcc (and thus libgccjit) can already decide by itself if a call is a
tail-call, and optimize accordingly.

See:
https://gcc.gnu.org/onlinedocs/jit/intro/tutorial04.html#behind-the-curtain-how-does-our-code-get-optimized
and in particular:
https://gcc.gnu.org/onlinedocs/jit/intro/tutorial04.html#elimination-of-tail-recursion


This is done by:
  gcc/tree-tailcall.c
controlled by:
  -foptimize-sibling-calls

which is on by default at -02 and above.


Normally you'd do something like:

   gcc_jit_block_end_with_return (...
     gcc_jit_context_new_call (...));

or

   gcc_jit_block_add_eval (...
     gcc_jit_context_new_call (...));

   gcc_jit_block_end_with_void return (...);


The tailcall is obvious in both of these cases.

> I was thinking of adding a construct where the GCCJIT client knows
> for sure that the call should be tail-rec (and if GCCJIT was not able to 
> make a tailcall, that would be an error).

It's not clear to me why that would be useful.  Am I missing something?

> Also, even without optimization (i.e. at -O0) that should remain a 
> tailcall...

Can't you simply turn on -foptimize-sibling-calls at -O0?

> Perhaps adding a gcc_jit_block_end_with_tail_call function?

I can see a way of implementing it for tail-recursion (via a goto),
though it would complicate the implementation (and hence I'm not keen);
I can't see way of doing it for the more general case of tail calls.

Re: GCCJIT and tail-recursive calls

[Basile Starynkevitch]

On 07/10/2015 03:31 AM, David Malcolm wrote:
> On Fri, 2015-07-10 at 00:30 +0200, Basile Starynkevitch wrote:
>> Hello all,
>>
>> It is well known that GCC is sometimes able to optimize some calls to
>> tail-recursive calls (or tail calls
>> https://en.wikipedia.org/wiki/Tail_call ...) which do not consume any stack.
>>
>> can a GCCJIT application issues such tail calls? I'm not talking of
>> letting GCC decide entirely by itself (GCCJIT is probably doing that
>> already).
> gcc (and thus libgccjit) can already decide by itself if a call is a
> tail-call, and optimize accordingly.
>
> See:
> https://gcc.gnu.org/onlinedocs/jit/intro/tutorial04.html#behind-the-curtain-how-does-our-code-get-optimized
> and in particular:
> https://gcc.gnu.org/onlinedocs/jit/intro/tutorial04.html#elimination-of-tail-recursion
>
>
> This is done by:
>    gcc/tree-tailcall.c
> controlled by:
>    -foptimize-sibling-calls
>
> which is on by default at -02 and above.
>
>
> Normally you'd do something like:
>
>     gcc_jit_block_end_with_return (...
>       gcc_jit_context_new_call (...));
>
> or
>
>     gcc_jit_block_add_eval (...
>       gcc_jit_context_new_call (...));
>
>     gcc_jit_block_end_with_void return (...);
>
>
> The tailcall is obvious in both of these cases.
>
>> I was thinking of adding a construct where the GCCJIT client knows
>> for sure that the call should be tail-rec (and if GCCJIT was not able to
>> make a tailcall, that would be an error).
> It's not clear to me why that would be useful.  Am I missing something?


You are coding a JIT for your implementation of Scheme.
Scheme requires that tailcails are effectively ilmplemented as such.
So your Scheme implementation has to detect tailcalls and want to be 
sure that GCCJIT
is implementing them as needed.

How would you ensure that?

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 tail-recursive calls

[David Malcolm]

On Fri, 2015-07-10 at 06:51 +0200, Basile Starynkevitch wrote:
> On 07/10/2015 03:31 AM, David Malcolm wrote:
> > On Fri, 2015-07-10 at 00:30 +0200, Basile Starynkevitch wrote:
> >> Hello all,
> >>
> >> It is well known that GCC is sometimes able to optimize some calls to
> >> tail-recursive calls (or tail calls
> >> https://en.wikipedia.org/wiki/Tail_call ...) which do not consume any stack.
> >>
> >> can a GCCJIT application issues such tail calls? I'm not talking of
> >> letting GCC decide entirely by itself (GCCJIT is probably doing that
> >> already).
> > gcc (and thus libgccjit) can already decide by itself if a call is a
> > tail-call, and optimize accordingly.
> >
> > See:
> > https://gcc.gnu.org/onlinedocs/jit/intro/tutorial04.html#behind-the-curtain-how-does-our-code-get-optimized
> > and in particular:
> > https://gcc.gnu.org/onlinedocs/jit/intro/tutorial04.html#elimination-of-tail-recursion
> >
> >
> > This is done by:
> >    gcc/tree-tailcall.c
> > controlled by:
> >    -foptimize-sibling-calls
> >
> > which is on by default at -02 and above.
> >
> >
> > Normally you'd do something like:
> >
> >     gcc_jit_block_end_with_return (...
> >       gcc_jit_context_new_call (...));
> >
> > or
> >
> >     gcc_jit_block_add_eval (...
> >       gcc_jit_context_new_call (...));
> >
> >     gcc_jit_block_end_with_void return (...);
> >
> >
> > The tailcall is obvious in both of these cases.
> >
> >> I was thinking of adding a construct where the GCCJIT client knows
> >> for sure that the call should be tail-rec (and if GCCJIT was not able to
> >> make a tailcall, that would be an error).
> > It's not clear to me why that would be useful.  Am I missing something?
> 
> 
> You are coding a JIT for your implementation of Scheme.
> Scheme requires that tailcails are effectively ilmplemented as such.

What do you mean by the word "requires" here?

  performance? that if enough tailcalls aren't optimized, then things
will be painfully slow?

  legal? that if every tailcall isn't optimized, then some trademark
owner will send a Cease-and-Desist letter?

etc

> So your Scheme implementation has to detect tailcalls and want to be 
> sure that GCCJIT
> is implementing them as needed.

Can't you just trust the optimizer?

> How would you ensure that?

From a testing perspective, I suppose you could pass in:
 -fdump-tree-tailr1-details -fdump-tree-tailr2-details
and then use:
https://gcc.gnu.org/onlinedocs/jit/topics/contexts.html#gcc_jit_context_enable_dump

to capture these dumpfiles in memory and somehow analyze them.  I use
this approach in one of the jit testcase to verify that an optimization
does take place (similar to how many of gcc's DejaGnu testcases work).

Another approach might be to add an attribute to the call, saying "must
be handled as a tail call", and have that pass issue an error if it
can't do it.  Maybe via a builtin that can wrap calls and tags them as
such?  That would require some work from the gcc side.

Dave

Re: GCCJIT and tail-recursive calls

[Basile Starynkevitch]

On 07/10/2015 04:41 PM, David Malcolm wrote:

> This is done by: gcc/tree-tailcall.c controlled by: 
> -foptimize-sibling-calls which is on by default at -02 and above. 
> Normally you'd do something like: gcc_jit_block_end_with_return (... 
> gcc_jit_context_new_call (...)); or gcc_jit_block_add_eval (... 
> gcc_jit_context_new_call (...)); gcc_jit_block_end_with_void return 
> (...); The tailcall is obvious in both of these cases.
>>>> I was thinking of adding a construct where the GCCJIT client knows
>>>> for sure that the call should be tail-rec (and if GCCJIT was not able to
>>>> make a tailcall, that would be an error).
>>> It's not clear to me why that would be useful.  Am I missing something?
>>
>> You are coding a JIT for your implementation of Scheme.
>> Scheme requires that tailcails are effectively ilmplemented as such.
> What do you mean by the word "requires" here?
>
>    performance? that if enough tailcalls aren't optimized, then things
> will be painfully slow?
>
>    legal? that if every tailcall isn't optimized, then some trademark
> owner will send a Cease-and-Desist letter?


No, technically only.

IIRC, Scheme specification has words that don't allow a stack overflow
for a very deep tail-recursive function call.
>> So your Scheme implementation has to detect tailcalls and want to be
>> sure that GCCJIT
>> is implementing them as needed.
> Can't you just trust the optimizer?
>
>> How would you ensure that?
> >From a testing perspective, I suppose you could pass in:
>   -fdump-tree-tailr1-details -fdump-tree-tailr2-details
> and then use:
> https://gcc.gnu.org/onlinedocs/jit/topics/contexts.html#gcc_jit_context_enable_dump
>
> to capture these dumpfiles in memory and somehow analyze them.  I use
> this approach in one of the jit testcase to verify that an optimization
> does take place (similar to how many of gcc's DejaGnu testcases work).

Ok.


> Another approach might be to add an attribute to the call, saying "must
> be handled as a tail call", and have that pass issue an error if it
> can't do it.  Maybe via a builtin that can wrap calls and tags them as
> such?  That would require some work from the gcc side.



Yes, I was thinking of something similar...


Thanks!

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