[PATCH 0/6] jit: Work-in-progress implementation of must-tail-call

[PATCH 0/6] jit: Work-in-progress implementation of must-tail-call

[David Malcolm]

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

[PATCH 5/6] FIXME: initial support for gcc diagnostics as jit errors

[David Malcolm]

Currently libgccjit ignores errors and other diagnostics emitted
within the core of gcc, and treates the compile of a gcc_jit_context
as having succeeded.

This patch ensures that if any diagnostics are emitted, they
are visible from the libgccjit API, and mark the context as
having failed.

TODO:
  - ChangeLog
  - better blurb
  - testing
  - what to do about non-error diagnostics (warnings etc)
---
 gcc/jit/dummy-frontend.c | 36 ++++++++++++++++++++++++++++++++++++
 1 file changed, 36 insertions(+)

diff --git a/gcc/jit/dummy-frontend.c b/gcc/jit/dummy-frontend.c
index 7194ba6..5830ff1 100644
--- a/gcc/jit/dummy-frontend.c
+++ b/gcc/jit/dummy-frontend.c
@@ -25,6 +25,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "debug.h"
 #include "langhooks.h"
 #include "langhooks-def.h"
+#include "diagnostic.h"
 
 
 #include <mpfr.h>
@@ -90,6 +91,37 @@ struct ggc_root_tab jit_root_tab[] =
     LAST_GGC_ROOT_TAB
   };
 
+
+/* JIT-specific implementation of diagnostic callbacks.  */
+
+/* FIXME.  */
+
+static void
+jit_begin_diagnostic (diagnostic_context */*context*/,
+		      diagnostic_info */*diagnostic*/)
+{
+  gcc_assert (gcc::jit::active_playback_ctxt);
+  JIT_LOG_SCOPE (gcc::jit::active_playback_ctxt->get_logger ());
+  /* TODO: report diagnostic; propagate errors.  */
+}
+
+/* FIXME.  */
+
+static void
+jit_end_diagnostic (diagnostic_context *context,
+		    diagnostic_info */*diagnostic*/)
+{
+  gcc_assert (gcc::jit::active_playback_ctxt);
+  JIT_LOG_SCOPE (gcc::jit::active_playback_ctxt->get_logger ());
+  /* TODO: report diagnostic; propagate errors.  */
+  pretty_printer *pp = context->printer;
+  //pp_clear_state (pp);
+  const char *text = pp_formatted_text (pp);
+  gcc::jit::active_playback_ctxt->add_error (NULL, "%s", text);
+  /* FIXME: what if it isn't an error?  */
+  pp_clear_output_area (pp);
+}
+
 /* Language hooks.  */
 
 static bool
@@ -105,6 +137,10 @@ jit_langhook_init (void)
       registered_root_tab = true;
     }
 
+  gcc_assert (global_dc);
+  global_dc->begin_diagnostic = jit_begin_diagnostic;
+  global_dc->end_diagnostic = jit_end_diagnostic;
+
   build_common_tree_nodes (false);
 
   /* I don't know why this has to be done explicitly.  */
-- 
1.8.5.3

[PATCH 4/6] FIXME: non-working scanasm test

[David Malcolm]

---
 gcc/testsuite/gcc.dg/plugin/must-tail-call-3.c | 14 ++++++++++++++
 gcc/testsuite/gcc.dg/plugin/plugin.exp         |  3 ++-
 2 files changed, 16 insertions(+), 1 deletion(-)
 create mode 100644 gcc/testsuite/gcc.dg/plugin/must-tail-call-3.c

diff --git a/gcc/testsuite/gcc.dg/plugin/must-tail-call-3.c b/gcc/testsuite/gcc.dg/plugin/must-tail-call-3.c
new file mode 100644
index 0000000..b3d129d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/plugin/must-tail-call-3.c
@@ -0,0 +1,14 @@
+/* { dg-do compile } */
+
+extern int callee (int i);
+
+int __attribute__((noinline,noclone))
+caller (int i)
+{
+  return callee (i + 1);
+}
+
+/* FIXME: this is showing up as UNRESOLVED, with "output file does not exist"
+   scanasm.exp erroneously uses "must_tail_call_plugin" as the root name
+   of the test case, and hence "must_tail_call_plugin.s" as the $output_file.  */
+/* { dg-final { scan-assembler-not "ret" } } */
diff --git a/gcc/testsuite/gcc.dg/plugin/plugin.exp b/gcc/testsuite/gcc.dg/plugin/plugin.exp
index 62f6797..688d59a 100644
--- a/gcc/testsuite/gcc.dg/plugin/plugin.exp
+++ b/gcc/testsuite/gcc.dg/plugin/plugin.exp
@@ -76,7 +76,8 @@ set plugin_test_list [list \
 	  location-overflow-test-2.c } \
     { must_tail_call_plugin.c \
 	  must-tail-call-1.c \
-	  must-tail-call-2.c } \
+	  must-tail-call-2.c \
+	  must-tail-call-3.c } \
 ]
 
 foreach plugin_test $plugin_test_list {
-- 
1.8.5.3

[PATCH 3/6] FIXME: WIP on jit part of must-tail-call

[David Malcolm]

This implements (most of) the libgccjit support for must-tail-call.

DONE:
  - C API
  - test coverage:
    - gcc/testsuite/jit.dg/all-non-failing-tests.h

TODO:
  - ChangeLog
  - blurb
  - C++ bindings support
  - test coverage:
    - example of failing TCO (implemented in a later patch)
  - feature macro in libgccjit.h
  - support for gcc_jit_context_dump_reproducer_to_file()
  - documentation for the new C entrypoints
  - documentation for the new C++ entrypoints
  - documentation for the new ABI tag (see topics/compatibility.rst).
  - regenerated texinfo
---
 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/testsuite/jit.dg/all-non-failing-tests.h       |   7 ++
 .../jit.dg/test-factorial-must-tail-call.c         | 109 +++++++++++++++++++++
 10 files changed, 224 insertions(+), 38 deletions(-)
 create mode 100644 gcc/testsuite/jit.dg/test-factorial-must-tail-call.c

diff --git a/gcc/jit/jit-common.h b/gcc/jit/jit-common.h
index 8a6cd74..b48ea0d 100644
--- a/gcc/jit/jit-common.h
+++ b/gcc/jit/jit-common.h
@@ -126,6 +126,7 @@ namespace recording {
         class local;
 	class global;
         class param;
+      class base_call;
     class statement;
     class case_;
 
diff --git a/gcc/jit/jit-playback.c b/gcc/jit/jit-playback.c
index 579230d..0d51a97 100644
--- a/gcc/jit/jit-playback.c
+++ b/gcc/jit/jit-playback.c
@@ -853,7 +853,8 @@ playback::rvalue *
 playback::context::
 build_call (location *loc,
 	    tree fn_ptr,
-	    const auto_vec<rvalue *> *args)
+	    const auto_vec<rvalue *> *args,
+	    bool require_tail_call)
 {
   vec<tree, va_gc> *tree_args;
   vec_alloc (tree_args, args->length ());
@@ -867,9 +868,13 @@ build_call (location *loc,
   tree fn_type = TREE_TYPE (fn);
   tree return_type = TREE_TYPE (fn_type);
 
-  return new rvalue (this,
-		     build_call_vec (return_type,
-				     fn_ptr, tree_args));
+  tree call = build_call_vec (return_type,
+			      fn_ptr, tree_args);
+
+  if (require_tail_call)
+    CALL_EXPR_MUST_TAIL_CALL (call) = 1;
+
+  return new rvalue (this, call);
 
   /* see c-typeck.c: build_function_call
      which calls build_function_call_vec
@@ -889,7 +894,8 @@ playback::rvalue *
 playback::context::
 new_call (location *loc,
 	  function *func,
-	  const auto_vec<rvalue *> *args)
+	  const auto_vec<rvalue *> *args,
+	  bool require_tail_call)
 {
   tree fndecl;
 
@@ -901,7 +907,7 @@ new_call (location *loc,
 
   tree fn = build1 (ADDR_EXPR, build_pointer_type (fntype), fndecl);
 
-  return build_call (loc, fn, args);
+  return build_call (loc, fn, args, require_tail_call);
 }
 
 /* Construct a playback::rvalue instance (wrapping a tree) for a
@@ -911,12 +917,13 @@ playback::rvalue *
 playback::context::
 new_call_through_ptr (location *loc,
 		      rvalue *fn_ptr,
-		      const auto_vec<rvalue *> *args)
+		      const auto_vec<rvalue *> *args,
+		      bool require_tail_call)
 {
   gcc_assert (fn_ptr);
   tree t_fn_ptr = fn_ptr->as_tree ();
 
-  return build_call (loc, t_fn_ptr, args);
+  return build_call (loc, t_fn_ptr, args, require_tail_call);
 }
 
 /* Construct a tree for a cast.  */
diff --git a/gcc/jit/jit-playback.h b/gcc/jit/jit-playback.h
index 905747c..669f3b8 100644
--- a/gcc/jit/jit-playback.h
+++ b/gcc/jit/jit-playback.h
@@ -130,12 +130,14 @@ public:
   rvalue *
   new_call (location *loc,
 	    function *func,
-	    const auto_vec<rvalue *> *args);
+	    const auto_vec<rvalue *> *args,
+	    bool require_tail_call);
 
   rvalue *
   new_call_through_ptr (location *loc,
 			rvalue *fn_ptr,
-			const auto_vec<rvalue *> *args);
+			const auto_vec<rvalue *> *args,
+			bool require_tail_call);
 
   rvalue *
   new_cast (location *loc,
@@ -229,7 +231,8 @@ private:
   rvalue *
   build_call (location *loc,
 	      tree fn_ptr,
-	      const auto_vec<rvalue *> *args);
+	      const auto_vec<rvalue *> *args,
+	      bool require_tail_call);
 
   tree
   build_cast (location *loc,
diff --git a/gcc/jit/jit-recording.c b/gcc/jit/jit-recording.c
index 8f5f914..e60c0a0 100644
--- a/gcc/jit/jit-recording.c
+++ b/gcc/jit/jit-recording.c
@@ -4681,6 +4681,23 @@ recording::cast::write_reproducer (reproducer &r)
 	   r.get_identifier_as_type (get_type ()));
 }
 
+/* The implementation of class gcc::jit::recording::base_call.  */
+
+/* The constructor for gcc::jit::recording::base_call.  */
+
+recording::base_call::base_call (context *ctxt,
+				 location *loc,
+				 type *type_,
+				 int numargs,
+				 rvalue **args)
+: rvalue (ctxt, loc, type_),
+  m_args (),
+  m_require_tail_call (0)
+{
+  for (int i = 0; i< numargs; i++)
+    m_args.safe_push (args[i]);
+}
+
 /* The implementation of class gcc::jit::recording::call.  */
 
 /* The constructor for gcc::jit::recording::call.  */
@@ -4690,12 +4707,9 @@ recording::call::call (recording::context *ctxt,
 		       recording::function *func,
 		       int numargs,
 		       rvalue **args)
-: rvalue (ctxt, loc, func->get_return_type ()),
-  m_func (func),
-  m_args ()
+: base_call (ctxt, loc, func->get_return_type (), numargs, args),
+  m_func (func)
 {
-  for (int i = 0; i< numargs; i++)
-    m_args.safe_push (args[i]);
 }
 
 /* Implementation of pure virtual hook recording::memento::replay_into
@@ -4711,7 +4725,8 @@ recording::call::replay_into (replayer *r)
 
   set_playback_obj (r->new_call (playback_location (r, m_loc),
 				 m_func->playback_function (),
-				 &playback_args));
+				 &playback_args,
+				 m_require_tail_call));
 }
 
 /* Implementation of pure virtual hook recording::rvalue::visit_children
@@ -4801,14 +4816,12 @@ recording::call_through_ptr::call_through_ptr (recording::context *ctxt,
 					       recording::rvalue *fn_ptr,
 					       int numargs,
 					       rvalue **args)
-: rvalue (ctxt, loc,
-	  fn_ptr->get_type ()->dereference ()
-	    ->as_a_function_type ()->get_return_type ()),
-  m_fn_ptr (fn_ptr),
-  m_args ()
+: base_call (ctxt, loc,
+	     fn_ptr->get_type ()->dereference ()
+	       ->as_a_function_type ()->get_return_type (),
+	     numargs, args),
+  m_fn_ptr (fn_ptr)
 {
-  for (int i = 0; i< numargs; i++)
-    m_args.safe_push (args[i]);
 }
 
 /* Implementation of pure virtual hook recording::memento::replay_into
@@ -4824,7 +4837,8 @@ recording::call_through_ptr::replay_into (replayer *r)
 
   set_playback_obj (r->new_call_through_ptr (playback_location (r, m_loc),
 					     m_fn_ptr->playback_rvalue (),
-					     &playback_args));
+					     &playback_args,
+					     m_require_tail_call));
 }
 
 /* Implementation of pure virtual hook recording::rvalue::visit_children
diff --git a/gcc/jit/jit-recording.h b/gcc/jit/jit-recording.h
index 1c3e763..4b46a08 100644
--- a/gcc/jit/jit-recording.h
+++ b/gcc/jit/jit-recording.h
@@ -960,8 +960,9 @@ public:
   void set_scope (function *scope);
   function *get_scope () const { return m_scope; }
 
-  /* Dynamic cast.  */
+  /* Dynamic casts.  */
   virtual param *dyn_cast_param () { return NULL; }
+  virtual base_call *dyn_cast_base_call () { return NULL; }
 
   virtual const char *access_as_rvalue (reproducer &r);
 
@@ -1418,7 +1419,33 @@ private:
   rvalue *m_rvalue;
 };
 
-class call : public rvalue
+class base_call : public rvalue
+{
+ public:
+  base_call (context *ctxt,
+	     location *loc,
+	     type *type_,
+	     int numargs,
+	     rvalue **args);
+
+  enum precedence get_precedence () const FINAL OVERRIDE
+  {
+    return PRECEDENCE_POSTFIX;
+  }
+
+  base_call *dyn_cast_base_call () FINAL OVERRIDE { return this; }
+
+  void set_require_tail_call (bool require_tail_call)
+  {
+    m_require_tail_call = require_tail_call;
+  }
+
+ protected:
+  auto_vec<rvalue *> m_args;
+  bool m_require_tail_call;
+};
+
+class call : public base_call
 {
 public:
   call (context *ctxt,
@@ -1434,17 +1461,12 @@ public:
 private:
   string * make_debug_string () FINAL OVERRIDE;
   void write_reproducer (reproducer &r) FINAL OVERRIDE;
-  enum precedence get_precedence () const FINAL OVERRIDE
-  {
-    return PRECEDENCE_POSTFIX;
-  }
 
 private:
   function *m_func;
-  auto_vec<rvalue *> m_args;
 };
 
-class call_through_ptr : public rvalue
+class call_through_ptr : public base_call
 {
 public:
   call_through_ptr (context *ctxt,
@@ -1460,14 +1482,9 @@ public:
 private:
   string * make_debug_string () FINAL OVERRIDE;
   void write_reproducer (reproducer &r) FINAL OVERRIDE;
-  enum precedence get_precedence () const FINAL OVERRIDE
-  {
-    return PRECEDENCE_POSTFIX;
-  }
 
 private:
   rvalue *m_fn_ptr;
-  auto_vec<rvalue *> m_args;
 };
 
 class array_access : public lvalue
diff --git a/gcc/jit/libgccjit.c b/gcc/jit/libgccjit.c
index 02ff50c..c577b3a 100644
--- a/gcc/jit/libgccjit.c
+++ b/gcc/jit/libgccjit.c
@@ -2950,3 +2950,21 @@ gcc_jit_timer_print (gcc_jit_timer *timer,
   timer->start (TV_TOTAL);
   timer->push (TV_JIT_CLIENT_CODE);
 }
+
+/* FIXME.  */
+
+void
+gcc_jit_rvalue_set_bool_require_tail_call (gcc_jit_rvalue *rvalue,
+					   int require_tail_call)
+{
+  RETURN_IF_FAIL (rvalue, NULL, NULL, "NULL call");
+  JIT_LOG_FUNC (rvalue->get_context ()->get_logger ());
+
+  /* Verify that it's a call.  */
+  gcc::jit::recording::base_call *call = rvalue->dyn_cast_base_call ();
+  RETURN_IF_FAIL_PRINTF1 (call, NULL, NULL, "not a call: %s",
+			  rvalue->get_debug_string ());
+
+  call->set_require_tail_call (require_tail_call);
+  // TODO: do something with the flag
+}
diff --git a/gcc/jit/libgccjit.h b/gcc/jit/libgccjit.h
index a8b9f55..c0ba4c1 100644
--- a/gcc/jit/libgccjit.h
+++ b/gcc/jit/libgccjit.h
@@ -1374,6 +1374,11 @@ extern void
 gcc_jit_timer_print (gcc_jit_timer *timer,
 		     FILE *f_out);
 
+/* FIXME.  */
+extern void
+gcc_jit_rvalue_set_bool_require_tail_call (gcc_jit_rvalue *call,
+					   int require_tail_call);
+
 #ifdef __cplusplus
 }
 #endif /* __cplusplus */
diff --git a/gcc/jit/libgccjit.map b/gcc/jit/libgccjit.map
index 65f3166..545b192 100644
--- a/gcc/jit/libgccjit.map
+++ b/gcc/jit/libgccjit.map
@@ -145,3 +145,8 @@ LIBGCCJIT_ABI_5 {
   global:
     gcc_jit_context_set_bool_use_external_driver;
 } LIBGCCJIT_ABI_4;
+
+LIBGCCJIT_ABI_6 {
+  global:
+    gcc_jit_rvalue_set_bool_require_tail_call;
+} LIBGCCJIT_ABI_5;
diff --git a/gcc/testsuite/jit.dg/all-non-failing-tests.h b/gcc/testsuite/jit.dg/all-non-failing-tests.h
index 463eefb..3fe5bc1 100644
--- a/gcc/testsuite/jit.dg/all-non-failing-tests.h
+++ b/gcc/testsuite/jit.dg/all-non-failing-tests.h
@@ -105,6 +105,13 @@
 #undef create_code
 #undef verify_code
 
+/* test-factorial-must-tail-call.c */
+#define create_code create_code_factorial_must_tail_call
+#define verify_code verify_code_factorial_must_tail_call
+#include "test-factorial-must-tail-call.c"
+#undef create_code
+#undef verify_code
+
 /* test-fibonacci.c */
 #define create_code create_code_fibonacci
 #define verify_code verify_code_fibonacci
diff --git a/gcc/testsuite/jit.dg/test-factorial-must-tail-call.c b/gcc/testsuite/jit.dg/test-factorial-must-tail-call.c
new file mode 100644
index 0000000..c862611
--- /dev/null
+++ b/gcc/testsuite/jit.dg/test-factorial-must-tail-call.c
@@ -0,0 +1,109 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+
+#include "libgccjit.h"
+
+#include "harness.h"
+
+void
+create_code (gcc_jit_context *ctxt, void *user_data)
+{
+  /* Let's try to inject the equivalent of:
+
+      int
+      my_factorial_must_tail_call (int x)
+      {
+        if (x < 2)
+          return x;
+        else
+          return x * my_factorial_must_tail_call (x - 1);
+      }
+
+     and mark the call as requiring tail-call-optimization.
+   */
+  gcc_jit_type *the_type =
+    gcc_jit_context_get_type (ctxt, GCC_JIT_TYPE_INT);
+  gcc_jit_type *return_type = the_type;
+
+  gcc_jit_param *x =
+    gcc_jit_context_new_param (ctxt, NULL, the_type, "x");
+  gcc_jit_param *params[1] = {x};
+  gcc_jit_function *func =
+    gcc_jit_context_new_function (ctxt, NULL,
+				  GCC_JIT_FUNCTION_EXPORTED,
+				  return_type,
+				  "my_factorial_must_tail_call",
+				  1, params, 0);
+
+  gcc_jit_block *initial =
+    gcc_jit_function_new_block (func, "initial");
+  gcc_jit_block *on_true =
+    gcc_jit_function_new_block (func, "on_true");
+  gcc_jit_block *on_false =
+    gcc_jit_function_new_block (func, "on_false");
+
+ /* if (x < 2) */
+  gcc_jit_block_end_with_conditional (
+    initial, NULL,
+    gcc_jit_context_new_comparison (
+      ctxt, NULL,
+      GCC_JIT_COMPARISON_LT,
+      gcc_jit_param_as_rvalue (x),
+      gcc_jit_context_new_rvalue_from_int (
+	ctxt,
+	the_type,
+	2)),
+    on_true,
+    on_false);
+
+  /* true branch: */
+  /* return x */
+  gcc_jit_block_end_with_return (
+    on_true,
+    NULL,
+    gcc_jit_param_as_rvalue (x));
+
+  /* false branch: */
+  gcc_jit_rvalue *x_minus_1 =
+    gcc_jit_context_new_binary_op (
+      ctxt, NULL,
+      GCC_JIT_BINARY_OP_MINUS, the_type,
+      gcc_jit_param_as_rvalue (x),
+      gcc_jit_context_new_rvalue_from_int (
+	ctxt,
+	the_type,
+	1));
+  /* my_factorial_must_tail_call (x - 1) */
+  gcc_jit_rvalue *call =
+      gcc_jit_context_new_call (
+        ctxt, NULL,
+        func,
+        1, &x_minus_1);
+
+  /* Mark the call as requiring tail-call optimization.  */
+  gcc_jit_rvalue_set_bool_require_tail_call (call, 1);
+
+  gcc_jit_block_end_with_return (
+    on_false,
+    NULL,
+    gcc_jit_context_new_binary_op (
+      ctxt, NULL,
+      GCC_JIT_BINARY_OP_MULT, the_type,
+      gcc_jit_param_as_rvalue (x),
+      call));
+}
+
+void
+verify_code (gcc_jit_context *ctxt, gcc_jit_result *result)
+{
+  typedef int (*my_factorial_fn_type) (int);
+  CHECK_NON_NULL (result);
+  my_factorial_fn_type my_factorial_must_tail_call =
+    (my_factorial_fn_type)gcc_jit_result_get_code (result, "my_factorial_must_tail_call");
+  CHECK_NON_NULL (my_factorial_must_tail_call);
+  int val = my_factorial_must_tail_call (10);
+  note ("my_factorial_must_tail_call returned: %d", val);
+  CHECK_VALUE (val, 3628800);
+}
+
-- 
1.8.5.3

[PATCH 2/6] FIXME: WIP on non-jit part of must-tail-call

[David Malcolm]

This patch implements support for marking CALL_EXPRs
as being mandatory for tail-call-optimization.

Currently this flag isn't accessible from any frontend,
so the patch uses a plugin for testing the functionality.

TODO:
- lots of FIXMEs
- lots more test coverage
- needs better blurb
- needs ChangeLog
- needs bootstrap&regrtest
---
 gcc/calls.c                                        | 97 ++++++++++++++++++----
 gcc/cfgexpand.c                                    |  1 +
 gcc/gimple-pretty-print.c                          |  2 +
 gcc/gimple.c                                       |  1 +
 gcc/gimple.h                                       | 19 +++++
 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.dg/plugin/must_tail_call_plugin.c          | 76 +++++++++++++++++
 gcc/testsuite/gcc.dg/plugin/plugin.exp             |  3 +
 gcc/tree-core.h                                    |  3 +
 gcc/tree.h                                         |  4 +
 12 files changed, 229 insertions(+), 16 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_plugin.c

diff --git a/gcc/calls.c b/gcc/calls.c
index ac8092c..c7c3260 100644
--- a/gcc/calls.c
+++ b/gcc/calls.c
@@ -1102,6 +1102,19 @@ store_unaligned_arguments_into_pseudos (struct arg_data *args, int num_actuals)
       }
 }
 
+/* Issue an error if CALL_EXPR was flagged as requiring
+   tall-call optimization.  */
+
+static void
+cannot_tail_call (tree call_expr, const char *reason)
+{
+  gcc_assert (TREE_CODE (call_expr) == CALL_EXPR);
+  if (!CALL_EXPR_MUST_TAIL_CALL (call_expr))
+    return;
+
+  error_at (EXPR_LOCATION (call_expr), "cannot tail-call: %s", reason);
+}
+
 /* Fill in ARGS_SIZE and ARGS array based on the parameters found in
    CALL_EXPR EXP.
 
@@ -1343,7 +1356,10 @@ initialize_argument_information (int num_actuals ATTRIBUTE_UNUSED,
 	      /* We can't use sibcalls if a callee-copied argument is
 		 stored in the current function's frame.  */
 	      if (!call_from_thunk_p && DECL_P (base) && !TREE_STATIC (base))
-		*may_tailcall = false;
+		{
+		  *may_tailcall = false;
+		  cannot_tail_call (exp, "FIXME 1");
+		}
 
 	      args[i].tree_value = build_fold_addr_expr_loc (loc,
 							 args[i].tree_value);
@@ -1406,6 +1422,7 @@ initialize_argument_information (int num_actuals ATTRIBUTE_UNUSED,
 		= build_fold_addr_expr_loc (loc, make_tree (type, copy));
 	      type = TREE_TYPE (args[i].tree_value);
 	      *may_tailcall = false;
+	      cannot_tail_call (exp, "FIXME 2");
 	    }
 	}
 
@@ -2358,48 +2375,74 @@ can_implement_as_sibling_call_p (tree exp,
 				 const args_size &args_size)
 {
   if (!targetm.have_sibcall_epilogue ())
-    return false;
+    {
+      cannot_tail_call (exp, "FIXME: targetm.have_sibcall_epilogue");
+      return false;
+    }
 
   /* Doing sibling call optimization needs some work, since
      structure_value_addr can be allocated on the stack.
      It does not seem worth the effort since few optimizable
      sibling calls will return a structure.  */
   if (structure_value_addr != NULL_RTX)
-    return false;
+    {
+      cannot_tail_call (exp, "FIXME: structure_value_addr");
+      return false;
+    }
 
 #ifdef REG_PARM_STACK_SPACE
   /* If outgoing reg parm stack space changes, we can not do sibcall.  */
   if (OUTGOING_REG_PARM_STACK_SPACE (funtype)
       != OUTGOING_REG_PARM_STACK_SPACE (TREE_TYPE (current_function_decl))
       || (reg_parm_stack_space != REG_PARM_STACK_SPACE (current_function_decl)))
-    return false;
+    {
+      cannot_tail_call (exp, "FIXME: outgoing reg parm stack space changes");
+      return false;
+    }
 #endif
 
   /* Check whether the target is able to optimize the call
      into a sibcall.  */
   if (!targetm.function_ok_for_sibcall (fndecl, exp))
-    return false;
+    {
+      cannot_tail_call (exp, "FIXME: targetm.function_ok_for_sibcall");
+      return false;
+    }
 
   /* Functions that do not return exactly once may not be sibcall
      optimized.  */
   if (flags & (ECF_RETURNS_TWICE | ECF_NORETURN))
-    return false;
+    {
+      cannot_tail_call (exp, "FIXME: ECF_RETURNS_TWICE | ECF_NORETURN");
+      return false;
+    }
 
   if (TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (addr))))
-    return false;
+    {
+      cannot_tail_call (exp,
+			"FIXME: TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (addr))))");
+      return false;
+    }
 
   /* If the called function is nested in the current one, it might access
      some of the caller's arguments, but could clobber them beforehand if
      the argument areas are shared.  */
   if (fndecl && decl_function_context (fndecl) == current_function_decl)
-    return false;
+    {
+      cannot_tail_call (exp, "FIXME");
+      return false;
+    }
 
   /* If this function requires more stack slots than the current
      function, we cannot change it into a sibling call.
      crtl->args.pretend_args_size is not part of the
      stack allocated by our caller.  */
   if (args_size.constant > (crtl->args.size - crtl->args.pretend_args_size))
-    return false;
+    {
+      cannot_tail_call (exp,
+			"callee required more stack slots than the caller");
+      return false;
+    }
 
   /* If the callee pops its own arguments, then it must pop exactly
      the same number of arguments as the current function.  */
@@ -2407,10 +2450,16 @@ can_implement_as_sibling_call_p (tree exp,
       != targetm.calls.return_pops_args (current_function_decl,
 					 TREE_TYPE (current_function_decl),
 					 crtl->args.size))
-    return false;
+    {
+      cannot_tail_call (exp, "FIXME");
+      return false;
+    }
 
   if (!lang_hooks.decls.ok_for_sibcall (fndecl))
-    return false;
+    {
+      cannot_tail_call (exp, "lang_hooks.decls.ok_for_sibcall");
+      return false;
+    }
 
   /* All checks passed.  */
   return true;
@@ -2444,6 +2493,7 @@ expand_call (tree exp, rtx target, int ignore)
   /* The type of the function being called.  */
   tree fntype;
   bool try_tail_call = CALL_EXPR_TAILCALL (exp);
+  bool must_tail_call = CALL_EXPR_MUST_TAIL_CALL (exp);
   int pass;
 
   /* Register in which non-BLKmode value will be returned,
@@ -2811,10 +2861,18 @@ expand_call (tree exp, rtx target, int ignore)
       || dbg_cnt (tail_call) == false)
     try_tail_call = 0;
 
+  /* If the user has marked the function as requiring tail-call
+     optimization, attempt it.  */
+  if (must_tail_call)
+    try_tail_call = 1;
+
   /*  Rest of purposes for tail call optimizations to fail.  */
   if (try_tail_call)
-    try_tail_call = can_implement_as_sibling_call_p (exp, structure_value_addr, funtype,
-						     reg_parm_stack_space, fndecl,
+    try_tail_call = can_implement_as_sibling_call_p (exp,
+						     structure_value_addr,
+						     funtype,
+						     reg_parm_stack_space,
+						     fndecl,
 						     flags, addr, args_size);
 
   /* Check if caller and callee disagree in promotion of function
@@ -2845,7 +2903,10 @@ expand_call (tree exp, rtx target, int ignore)
 		  && (caller_unsignedp != callee_unsignedp
 		      || GET_MODE_BITSIZE (caller_mode)
 			 < GET_MODE_BITSIZE (callee_mode)))))
-	try_tail_call = 0;
+	{
+	  try_tail_call = 0;
+	  cannot_tail_call (exp, "FIXME 3");
+	}
     }
 
   /* Ensure current function's preferred stack boundary is at least
@@ -3743,7 +3804,13 @@ expand_call (tree exp, rtx target, int ignore)
       crtl->tail_call_emit = true;
     }
   else
-    emit_insn (normal_call_insns);
+    {
+      emit_insn (normal_call_insns);
+      if (try_tail_call)
+	/* Ideally we'd emit a message for all of the ways that it could
+	   have failed.  */
+	cannot_tail_call (exp, "FIXME");
+    }
 
   currently_expanding_call--;
 
diff --git a/gcc/cfgexpand.c b/gcc/cfgexpand.c
index 77a1964..2a27691 100644
--- a/gcc/cfgexpand.c
+++ b/gcc/cfgexpand.c
@@ -2626,6 +2626,7 @@ expand_call_stmt (gcall *stmt)
     TREE_NOTHROW (exp) = 1;
 
   CALL_EXPR_TAILCALL (exp) = gimple_call_tail_p (stmt);
+  CALL_EXPR_MUST_TAIL_CALL (exp) = gimple_call_must_tail_p (stmt);
   CALL_EXPR_RETURN_SLOT_OPT (exp) = gimple_call_return_slot_opt_p (stmt);
   if (decl
       && DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL
diff --git a/gcc/gimple-pretty-print.c b/gcc/gimple-pretty-print.c
index 4b0dc7c..1806a8c 100644
--- a/gcc/gimple-pretty-print.c
+++ b/gcc/gimple-pretty-print.c
@@ -742,6 +742,8 @@ dump_gimple_call (pretty_printer *buffer, gcall *gs, int spc, int flags)
     pp_string (buffer, " [return slot optimization]");
   if (gimple_call_tail_p (gs))
     pp_string (buffer, " [tail call]");
+  if (gimple_call_must_tail_p (gs))
+    pp_string (buffer, " [must tail call]");
 
   if (fn == NULL)
     return;
diff --git a/gcc/gimple.c b/gcc/gimple.c
index 1a22e82..92f873b 100644
--- a/gcc/gimple.c
+++ b/gcc/gimple.c
@@ -359,6 +359,7 @@ gimple_build_call_from_tree (tree t)
   /* Carry all the CALL_EXPR flags to the new GIMPLE_CALL.  */
   gimple_call_set_chain (call, CALL_EXPR_STATIC_CHAIN (t));
   gimple_call_set_tail (call, CALL_EXPR_TAILCALL (t));
+  gimple_call_set_must_tail (call, CALL_EXPR_MUST_TAIL_CALL (t));
   gimple_call_set_return_slot_opt (call, CALL_EXPR_RETURN_SLOT_OPT (t));
   if (fndecl
       && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
diff --git a/gcc/gimple.h b/gcc/gimple.h
index 6d15dab..9855db1 100644
--- a/gcc/gimple.h
+++ b/gcc/gimple.h
@@ -145,6 +145,7 @@ enum gf_mask {
     GF_CALL_INTERNAL		= 1 << 6,
     GF_CALL_CTRL_ALTERING       = 1 << 7,
     GF_CALL_WITH_BOUNDS 	= 1 << 8,
+    GF_CALL_MUST_TAIL_CALL	= 1 << 9,
     GF_OMP_PARALLEL_COMBINED	= 1 << 0,
     GF_OMP_PARALLEL_GRID_PHONY = 1 << 1,
     GF_OMP_TASK_TASKLOOP	= 1 << 0,
@@ -3209,6 +3210,24 @@ gimple_call_tail_p (gcall *s)
   return (s->subcode & GF_CALL_TAILCALL) != 0;
 }
 
+/* FIXME.  */
+
+static inline void
+gimple_call_set_must_tail (gcall *s, bool must_tail_p)
+{
+  if (must_tail_p)
+    s->subcode |= GF_CALL_MUST_TAIL_CALL;
+  else
+    s->subcode &= ~GF_CALL_MUST_TAIL_CALL;
+}
+
+/* FIXME.  */
+
+static inline bool
+gimple_call_must_tail_p (gcall *s)
+{
+  return (s->subcode & GF_CALL_MUST_TAIL_CALL) != 0;
+}
 
 /* If RETURN_SLOT_OPT_P is true mark GIMPLE_CALL S as valid for return
    slot optimization.  This transformation uses the target of the call
diff --git a/gcc/print-tree.c b/gcc/print-tree.c
index aa6593f..58b6118 100644
--- a/gcc/print-tree.c
+++ b/gcc/print-tree.c
@@ -324,7 +324,7 @@ print_node (FILE *file, const char *prefix, tree node, int indent)
   if (TREE_PROTECTED (node))
     fputs (" protected", file);
   if (TREE_STATIC (node))
-    fputs (" static", file);
+    fputs (code == CALL_EXPR ? " must-tail-call" : " static", file);
   if (TREE_DEPRECATED (node))
     fputs (" deprecated", file);
   if (TREE_VISITED (node))
diff --git a/gcc/testsuite/gcc.dg/plugin/must-tail-call-1.c b/gcc/testsuite/gcc.dg/plugin/must-tail-call-1.c
new file mode 100644
index 0000000..6d74955
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/plugin/must-tail-call-1.c
@@ -0,0 +1,22 @@
+extern void abort (void);
+
+int __attribute__((noinline,noclone))
+callee (int i)
+{
+  return i * i;
+}
+
+int __attribute__((noinline,noclone))
+caller (int i)
+{
+  return callee (i + 1);
+}
+
+int
+main (int argc, const char **argv)
+{
+  int result = caller (5);
+  if (result != 36)
+    abort ();
+  return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c b/gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c
new file mode 100644
index 0000000..264a792
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c
@@ -0,0 +1,15 @@
+struct box { char dummy[64]; int i; };
+
+struct box __attribute__((noinline,noclone))
+returns_struct (int i)
+{
+  struct box b;
+  b.i = i * i;
+  return b;
+}
+
+int __attribute__((noinline,noclone))
+test_1 (int i)
+{
+  return returns_struct (i * 5).i; /* { dg-error "cannot tail-call: FIXME: structure_value_addr" } */
+}
diff --git a/gcc/testsuite/gcc.dg/plugin/must_tail_call_plugin.c b/gcc/testsuite/gcc.dg/plugin/must_tail_call_plugin.c
new file mode 100644
index 0000000..5294f28
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/plugin/must_tail_call_plugin.c
@@ -0,0 +1,76 @@
+/* { dg-options "-O" } */
+
+/* Mark all CALL_EXPRs not within "main" as requiring tail-call. */
+
+#include "gcc-plugin.h"
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "tree.h"
+#include "stringpool.h"
+#include "toplev.h"
+#include "basic-block.h"
+#include "hash-table.h"
+#include "vec.h"
+#include "ggc.h"
+#include "basic-block.h"
+#include "tree-ssa-alias.h"
+#include "internal-fn.h"
+#include "gimple-fold.h"
+#include "tree-eh.h"
+#include "gimple-expr.h"
+#include "is-a.h"
+#include "tree.h"
+#include "tree-pass.h"
+#include "intl.h"
+#include "plugin-version.h"
+
+int plugin_is_GPL_compatible;
+
+tree
+cb_walk_tree_fn (tree * tp, int * walk_subtrees,
+		 void * data ATTRIBUTE_UNUSED)
+{
+  if (TREE_CODE (*tp) != CALL_EXPR)
+    return NULL_TREE;
+
+  tree call_expr = *tp;
+
+  /* Forcibly mark the CALL_EXPR as requiring tail-call optimization.  */
+  CALL_EXPR_MUST_TAIL_CALL (call_expr) = 1;
+  
+  return NULL_TREE;
+}
+
+static void
+callback (void *gcc_data, void *user_data)
+{
+  tree fndecl = (tree)gcc_data;
+  gcc_assert (TREE_CODE (fndecl) == FUNCTION_DECL);
+
+  /* Don't mark calls inside "main".  */
+  tree decl_name = DECL_NAME (fndecl);
+  if (decl_name)
+    if (0 == strcmp (IDENTIFIER_POINTER (decl_name), "main"))
+      return;
+
+  walk_tree (&DECL_SAVED_TREE (fndecl), cb_walk_tree_fn, NULL, NULL);
+}
+
+int
+plugin_init (struct plugin_name_args *plugin_info,
+	     struct plugin_gcc_version *version)
+{
+  const char *plugin_name = plugin_info->base_name;
+
+  if (!plugin_default_version_check (version, &gcc_version))
+    return 1;
+
+  register_callback (plugin_name,
+		     PLUGIN_PRE_GENERICIZE,
+		     callback,
+		     NULL);
+
+  return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/plugin/plugin.exp b/gcc/testsuite/gcc.dg/plugin/plugin.exp
index fd1e98e..62f6797 100644
--- a/gcc/testsuite/gcc.dg/plugin/plugin.exp
+++ b/gcc/testsuite/gcc.dg/plugin/plugin.exp
@@ -74,6 +74,9 @@ set plugin_test_list [list \
     { location_overflow_plugin.c \
 	  location-overflow-test-1.c \
 	  location-overflow-test-2.c } \
+    { must_tail_call_plugin.c \
+	  must-tail-call-1.c \
+	  must-tail-call-2.c } \
 ]
 
 foreach plugin_test $plugin_test_list {
diff --git a/gcc/tree-core.h b/gcc/tree-core.h
index ea832fa..078e006 100644
--- a/gcc/tree-core.h
+++ b/gcc/tree-core.h
@@ -998,6 +998,9 @@ struct GTY(()) tree_base {
        SSA_NAME_ANTI_RANGE_P in
 	   SSA_NAME
 
+       MUST_TAIL_CALL in
+	   CALL_EXPR
+
    public_flag:
 
        TREE_OVERFLOW in
diff --git a/gcc/tree.h b/gcc/tree.h
index 37324bf..bfbb646 100644
--- a/gcc/tree.h
+++ b/gcc/tree.h
@@ -661,6 +661,10 @@ extern void omp_clause_range_check_failed (const_tree, const char *, int,
 #define CALL_EXPR_TAILCALL(NODE) \
   (CALL_EXPR_CHECK (NODE)->base.addressable_flag)
 
+/* FIXME.  */
+#define CALL_EXPR_MUST_TAIL_CALL(NODE) \
+  (CALL_EXPR_CHECK (NODE)->base.static_flag)
+
 /* Used as a temporary field on a CASE_LABEL_EXPR to indicate that the
    CASE_LOW operand has been processed.  */
 #define CASE_LOW_SEEN(NODE) \
-- 
1.8.5.3

Re: [PATCH 0/6] jit: Work-in-progress implementation of must-tail-call

[Marc Nieper-Wißkirchen]

David,

thank you a lot for seeing about the matter! Here is a bit more on the 
problem with taking the address of locals of the tail caller:

Consider the following program:

#include <stdio.h>

void (*f) (int);

void g (int a)
{
     int b;
     a = scanf ("%i", &b);
     return f(a);
}

Here, the compiler is not able to substitute the call to f with a jump 
because I take the address of the local variable b and the compiler 
cannot know whether scanf stores it in some unknown global or not. So it 
has to keep b alive until the end of the function g.

Now if I wrote something like

#include <stdio.h>

void (*f) (int);

void g (int a)
{
     int b;
     a = scanf ("%i", &b);
     return __musttail__ f(a);
},

I don't want the compiler to emit an error that a sibling tail jump is 
not possible by the reasons above. What I want is that the compiler does 
the jump while taking it for granted that the location of b won't be 
accessed anymore when control enters the function f. (In some sense, 
__musttail__ thus behaves like restrict. It is the programmers 
responsibility that a certain contract is fulfilled.)

Marc


Am 13.05.2016 um 22:17 schrieb David Malcolm:
> 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
>

[PATCH 6/6] FIXME: jit: add test of failing must-TCO

[David Malcolm]

Uses the jit diagnostic integration support from prior patch

TODO:
  - needs ChangeLog
  - blurb
---
 .../jit.dg/test-error-impossible-must-tail-call.c  | 93 ++++++++++++++++++++++
 1 file changed, 93 insertions(+)
 create mode 100644 gcc/testsuite/jit.dg/test-error-impossible-must-tail-call.c

diff --git a/gcc/testsuite/jit.dg/test-error-impossible-must-tail-call.c b/gcc/testsuite/jit.dg/test-error-impossible-must-tail-call.c
new file mode 100644
index 0000000..5bcfd59
--- /dev/null
+++ b/gcc/testsuite/jit.dg/test-error-impossible-must-tail-call.c
@@ -0,0 +1,93 @@
+#include <stdlib.h>
+#include <stdio.h>
+
+#include "libgccjit.h"
+
+#include "harness.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+  struct box { char dummy[64]; int i; };
+
+  extern struct box
+  returns_struct (int i);
+
+#ifdef __cplusplus
+}
+#endif
+
+void
+create_code (gcc_jit_context *ctxt, void *user_data)
+{
+  /* Let's try to inject the equivalent of:
+
+       int test (int i)
+       {
+         return [MUST TAIL CALL] returns_struct (i).i;
+       }
+
+     and verify that we get a sane error when the tail call
+     optimization can't be done.  */
+
+  gcc_jit_type *char_type =
+    gcc_jit_context_get_type (ctxt, GCC_JIT_TYPE_CHAR);
+  gcc_jit_type *int_type =
+    gcc_jit_context_get_type (ctxt, GCC_JIT_TYPE_INT);
+
+  /* Declare "struct box.  */
+  gcc_jit_type *array_type =
+    gcc_jit_context_new_array_type (ctxt, NULL, char_type, 64);
+  gcc_jit_field *field_dummy =
+    gcc_jit_context_new_field (ctxt, NULL, array_type, "dummy");
+  gcc_jit_field *field_i =
+    gcc_jit_context_new_field (ctxt, NULL, int_type, "i");
+  gcc_jit_field *fields[2] = {field_dummy, field_i};
+  gcc_jit_struct *struct_box =
+    gcc_jit_context_new_struct_type (ctxt, NULL, "box", 2, fields);
+
+  /* Declare the imported function.  */
+  gcc_jit_param *called_fn_param_i =
+    gcc_jit_context_new_param (ctxt, NULL, int_type, "i");
+  gcc_jit_function *called_fn =
+    gcc_jit_context_new_function (ctxt, NULL,
+                                  GCC_JIT_FUNCTION_IMPORTED,
+                                  gcc_jit_struct_as_type (struct_box),
+                                  "called_function",
+                                  1, &called_fn_param_i,
+                                  0);
+
+  /* Build the test_fn.  */
+  gcc_jit_param *caller_param_i =
+    gcc_jit_context_new_param (ctxt, NULL, int_type, "i");
+  gcc_jit_function *test_fn =
+    gcc_jit_context_new_function (ctxt, NULL,
+                                  GCC_JIT_FUNCTION_EXPORTED,
+                                  int_type,
+                                  "test_caller",
+                                  1, &caller_param_i,
+                                  0);
+  gcc_jit_rvalue *arg = gcc_jit_param_as_rvalue (caller_param_i);
+
+  gcc_jit_rvalue *call =
+    gcc_jit_context_new_call (ctxt, NULL,
+                              called_fn,
+                              1, &arg);
+
+  /* Mark the call as requiring tail-call optimization.  */
+  gcc_jit_rvalue_set_bool_require_tail_call (call, 1);
+
+  gcc_jit_block *block = gcc_jit_function_new_block (test_fn, NULL);
+  gcc_jit_block_end_with_return (block, NULL,
+    gcc_jit_rvalue_access_field (call, NULL, field_i));
+}
+
+void
+verify_code (gcc_jit_context *ctxt, gcc_jit_result *result)
+{
+  CHECK_VALUE (result, NULL);
+
+  CHECK_STRING_VALUE (gcc_jit_context_get_first_error (ctxt),
+		      "cannot tail-call: FIXME: structure_value_addr");
+}
-- 
1.8.5.3

[PATCH 1/6] FIXME: introduce can_implement_as_sibling_call_p

[David Malcolm]

TODO:
- needs blurb
- needs bootstrap&regrtest

gcc/ChangeLog:
	* calls.c (expand_call): Move "Rest of purposes for tail call
	optimizations to fail" to...
	(can_implement_as_sibling_call_p): ...this new function, and
	split into multiple "if" statements.
---
 gcc/calls.c | 114 ++++++++++++++++++++++++++++++++++++++++--------------------
 1 file changed, 76 insertions(+), 38 deletions(-)

diff --git a/gcc/calls.c b/gcc/calls.c
index 6cc1fc7..ac8092c 100644
--- a/gcc/calls.c
+++ b/gcc/calls.c
@@ -2344,6 +2344,78 @@ avoid_likely_spilled_reg (rtx x)
   return x;
 }
 
+/* Helper function for expand_call.
+   Return false is EXP is not implementable as a sibling call.  */
+
+static bool
+can_implement_as_sibling_call_p (tree exp,
+				 rtx structure_value_addr,
+				 tree funtype,
+				 int reg_parm_stack_space,
+				 tree fndecl,
+				 int flags,
+				 tree addr,
+				 const args_size &args_size)
+{
+  if (!targetm.have_sibcall_epilogue ())
+    return false;
+
+  /* Doing sibling call optimization needs some work, since
+     structure_value_addr can be allocated on the stack.
+     It does not seem worth the effort since few optimizable
+     sibling calls will return a structure.  */
+  if (structure_value_addr != NULL_RTX)
+    return false;
+
+#ifdef REG_PARM_STACK_SPACE
+  /* If outgoing reg parm stack space changes, we can not do sibcall.  */
+  if (OUTGOING_REG_PARM_STACK_SPACE (funtype)
+      != OUTGOING_REG_PARM_STACK_SPACE (TREE_TYPE (current_function_decl))
+      || (reg_parm_stack_space != REG_PARM_STACK_SPACE (current_function_decl)))
+    return false;
+#endif
+
+  /* Check whether the target is able to optimize the call
+     into a sibcall.  */
+  if (!targetm.function_ok_for_sibcall (fndecl, exp))
+    return false;
+
+  /* Functions that do not return exactly once may not be sibcall
+     optimized.  */
+  if (flags & (ECF_RETURNS_TWICE | ECF_NORETURN))
+    return false;
+
+  if (TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (addr))))
+    return false;
+
+  /* If the called function is nested in the current one, it might access
+     some of the caller's arguments, but could clobber them beforehand if
+     the argument areas are shared.  */
+  if (fndecl && decl_function_context (fndecl) == current_function_decl)
+    return false;
+
+  /* If this function requires more stack slots than the current
+     function, we cannot change it into a sibling call.
+     crtl->args.pretend_args_size is not part of the
+     stack allocated by our caller.  */
+  if (args_size.constant > (crtl->args.size - crtl->args.pretend_args_size))
+    return false;
+
+  /* If the callee pops its own arguments, then it must pop exactly
+     the same number of arguments as the current function.  */
+  if (targetm.calls.return_pops_args (fndecl, funtype, args_size.constant)
+      != targetm.calls.return_pops_args (current_function_decl,
+					 TREE_TYPE (current_function_decl),
+					 crtl->args.size))
+    return false;
+
+  if (!lang_hooks.decls.ok_for_sibcall (fndecl))
+    return false;
+
+  /* All checks passed.  */
+  return true;
+}
+
 /* Generate all the code for a CALL_EXPR exp
    and return an rtx for its value.
    Store the value in TARGET (specified as an rtx) if convenient.
@@ -2740,44 +2812,10 @@ expand_call (tree exp, rtx target, int ignore)
     try_tail_call = 0;
 
   /*  Rest of purposes for tail call optimizations to fail.  */
-  if (!try_tail_call
-      || !targetm.have_sibcall_epilogue ()
-      /* Doing sibling call optimization needs some work, since
-	 structure_value_addr can be allocated on the stack.
-	 It does not seem worth the effort since few optimizable
-	 sibling calls will return a structure.  */
-      || structure_value_addr != NULL_RTX
-#ifdef REG_PARM_STACK_SPACE
-      /* If outgoing reg parm stack space changes, we can not do sibcall.  */
-      || (OUTGOING_REG_PARM_STACK_SPACE (funtype)
-	  != OUTGOING_REG_PARM_STACK_SPACE (TREE_TYPE (current_function_decl)))
-      || (reg_parm_stack_space != REG_PARM_STACK_SPACE (current_function_decl))
-#endif
-      /* Check whether the target is able to optimize the call
-	 into a sibcall.  */
-      || !targetm.function_ok_for_sibcall (fndecl, exp)
-      /* Functions that do not return exactly once may not be sibcall
-	 optimized.  */
-      || (flags & (ECF_RETURNS_TWICE | ECF_NORETURN))
-      || TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (addr)))
-      /* If the called function is nested in the current one, it might access
-	 some of the caller's arguments, but could clobber them beforehand if
-	 the argument areas are shared.  */
-      || (fndecl && decl_function_context (fndecl) == current_function_decl)
-      /* If this function requires more stack slots than the current
-	 function, we cannot change it into a sibling call.
-	 crtl->args.pretend_args_size is not part of the
-	 stack allocated by our caller.  */
-      || args_size.constant > (crtl->args.size
-			       - crtl->args.pretend_args_size)
-      /* If the callee pops its own arguments, then it must pop exactly
-	 the same number of arguments as the current function.  */
-      || (targetm.calls.return_pops_args (fndecl, funtype, args_size.constant)
-	  != targetm.calls.return_pops_args (current_function_decl,
-					     TREE_TYPE (current_function_decl),
-					     crtl->args.size))
-      || !lang_hooks.decls.ok_for_sibcall (fndecl))
-    try_tail_call = 0;
+  if (try_tail_call)
+    try_tail_call = can_implement_as_sibling_call_p (exp, structure_value_addr, funtype,
+						     reg_parm_stack_space, fndecl,
+						     flags, addr, args_size);
 
   /* Check if caller and callee disagree in promotion of function
      return value.  */
-- 
1.8.5.3