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