GCCJIT and proper tail calls

[David Malcolm]

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