public inbox for jit@gcc.gnu.org
 help / color / mirror / Atom feed
From: David Malcolm <dmalcolm@redhat.com>
To: "Basile Starynkevitch" <basile@starynkevitch.net>,
	"Marc Nieper-Wißkirchen" <marc@nieper-wisskirchen.de>,
	jit@gcc.gnu.org
Cc: David Malcolm <dmalcolm@redhat.com>
Subject: [PATCH 0/6] jit: Work-in-progress implementation of must-tail-call
Date: Fri, 01 Jan 2016 00:00:00 -0000	[thread overview]
Message-ID: <1463170652-13754-1-git-send-email-dmalcolm@redhat.com> (raw)

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

-- 
1.8.5.3

             reply	other threads:[~2016-05-13 19:52 UTC|newest]

Thread overview: 8+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2016-01-01  0:00 David Malcolm [this message]
2016-01-01  0:00 ` [PATCH 1/6] FIXME: introduce can_implement_as_sibling_call_p David Malcolm
2016-01-01  0:00   ` [PATCH 3/6] FIXME: WIP on jit part of must-tail-call David Malcolm
2016-01-01  0:00   ` [PATCH 4/6] FIXME: non-working scanasm test David Malcolm
2016-01-01  0:00   ` [PATCH 5/6] FIXME: initial support for gcc diagnostics as jit errors David Malcolm
2016-01-01  0:00   ` [PATCH 6/6] FIXME: jit: add test of failing must-TCO David Malcolm
2016-01-01  0:00   ` [PATCH 2/6] FIXME: WIP on non-jit part of must-tail-call David Malcolm
2016-01-01  0:00 ` [PATCH 0/6] jit: Work-in-progress implementation " Marc Nieper-Wißkirchen

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=1463170652-13754-1-git-send-email-dmalcolm@redhat.com \
    --to=dmalcolm@redhat.com \
    --cc=basile@starynkevitch.net \
    --cc=jit@gcc.gnu.org \
    --cc=marc@nieper-wisskirchen.de \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
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).