Re: [PATCH 2/3] Implement CALL_EXPR_MUST_TAIL_CALL

Re: [PATCH 2/3] Implement CALL_EXPR_MUST_TAIL_CALL

[Andreas Schwab]

David Malcolm <dmalcolm@redhat.com> writes:

> 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..c5504f8
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c
> @@ -0,0 +1,58 @@
> +/* Allow nested functions.  */
> +/* { dg-options "-Wno-pedantic" } */
> +
> +struct box { char field[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: callee returns a structure" } */
> +}
> +
> +int __attribute__((noinline,noclone))
> +test_2_callee (int i, struct box b)
> +{
> +  if (b.field[0])
> +    return 5;
> +  return i * i;
> +}
> +
> +int __attribute__((noinline,noclone))
> +test_2_caller (int i)
> +{
> +  struct box b;
> +  return test_2_callee (i + 1, b); /* { dg-error "cannot tail-call: callee required more stack slots than the caller" } */
> +}
> +
> +extern void setjmp (void);
> +void
> +test_3 (void)
> +{
> +  setjmp (); /* { dg-error "cannot tail-call: callee returns twice" } */
> +}
> +
> +void
> +test_4 (void)
> +{
> +  void nested (void)
> +  {
> +  }
> +  nested (); /* { dg-error "cannot tail-call: nested function" } */
> +}
> +
> +typedef void (fn_ptr_t) (void);
> +volatile fn_ptr_t fn_ptr;
> +
> +void
> +test_5 (void)
> +{
> +  fn_ptr (); /* { dg-error "cannot tail-call: callee does not return" } */
> +}

On ia64:

FAIL: gcc.dg/plugin/must-tail-call-2.c -fplugin=./must_tail_call_plugin.so  (test for errors, line 39)
FAIL: gcc.dg/plugin/must-tail-call-2.c -fplugin=./must_tail_call_plugin.so  (test for errors, line 57)
FAIL: gcc.dg/plugin/must-tail-call-2.c -fplugin=./must_tail_call_plugin.so (test for excess errors)
Excess errors:
gcc.dg/plugin/must-tail-call-2.c:39:3: error: cannot tail-call: target is not able to optimize the call into a sibling call
gcc.dg/plugin/must-tail-call-2.c:57:3: error: cannot tail-call: target is not able to optimize the call into a sibling call

On m68k:

FAIL: gcc.dg/plugin/must-tail-call-2.c -fplugin=./must_tail_call_plugin.so  (test for errors, line 48)
FAIL: gcc.dg/plugin/must-tail-call-2.c -fplugin=./must_tail_call_plugin.so (test for excess errors)
Excess errors:
gcc.dg/plugin/must-tail-call-2.c:48:3: error: cannot tail-call: target is not able to optimize the call into a sibling call

Andreas.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Re: [PATCH 0/3] Support for mandatory tail calls

[Richard Biener]

On Thu, May 19, 2016 at 3:19 PM, Jason Merrill <jason@redhat.com> wrote:
> On Thu, May 19, 2016 at 12:30 AM, Basile Starynkevitch
> <basile@starynkevitch.net> wrote:
>> On 05/19/2016 12:12 AM, Jeff Law wrote:
>>>
>>> On 05/17/2016 04:01 PM, David Malcolm wrote:
>>>>
>>>> There have been requests [1] for libgccjit to better support
>>>> functional programming by supporting the contination-passing style,
>>>> in which every function "returns" by calling a "continuation"
>>>> function pointer.
>>>>
>>>> These calls must be guaranteed to be implemented as a jump,
>>>> otherwise the program could consume an arbitrary amount of stack
>>>> space as it executed.
>>>>
>>>> This patch kit implements this.
>>>>
>>>> Patch 1 is a preliminary tweak to calls.c
>>>>
>>>> Patch 2 implements a new flag in tree.h: CALL_EXPR_MUST_TAIL_CALL,
>>>> which makes calls.c try harder to implement a flagged call as a
>>>> tail-call/sibling call, and makes it issue an error if
>>>> the optimization is impossible.  It doesn't implement any
>>>> frontend support for setting the flag (instead using a plugin
>>>> to test it).  We had some discussion on the jit list about possibly
>>>> introducing a new builtin for this, but the patch punts on this
>>>> issue.
>>>
>>> I wonder if we should have an attribute so that the flag can be set for
>>> C/C++ code.  I've seen requests for forcing tail calls in C/C++ code several
>>> times in the past, precisely to support continuations.
>>
>> Why an attribute? Attributes are on declarations. I think it should better
>> be some pragma like _Pragma(GCC tail cail, foo(x,y)) or some builtin (or
>> else some syntax extension like goto return foo(x,y); ...) because what we
>> really want is to annotate a particular call to be tail-recursive.
>
> C++11 attributes can apply to expression-statements as well, e.g.
>
> [[gnu::tail_call]] fn();
>
> though not to sub-expressions.

That's nice.  Can they apply to things like loops?

 [[gnu::no_unroll]] for (int i=0; i<4; ++i)
   a[i] = 0;

Richard.

> Jason

[PATCH 1/3] Introduce can_implement_as_sibling_call_p

[David Malcolm]

This patch moves part of the logic for determining if tail
call optimizations are possible to a new helper function.

There are no functional changes.

expand_call is 1300 lines long, so there's arguably a
case for doing this on its own, but this change also
enables the followup patch.

The patch changes the logic from a big "if" with joined
|| clauses:

  if (first_problem ()
      ||second_problem ()
      /* ...etc... */
      ||final_problem ())
     try_tail_call = 0;

to a series of separate tests:

  if (first_problem ())
    return false;
  if (second_problem ())
    return false;
  /* ...etc... */
  if (final_problem ())
    return false;

I think the latter form has several advantages over the former:
- IMHO it's easier to read
- it makes it easy to put breakpoints on individual causes of failure
- it makes it easy to put specific error messages on individual causes
  of failure (as done in the followup patch).

Successfully bootstrapped&regrtested on x86_64-pc-linux-gnu.

OK for trunk?

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

Re: [PATCH 3/3] jit: implement gcc_jit_rvalue_set_bool_require_tail_call

[Trevor Saunders]

On Tue, May 17, 2016 at 06:01:32PM -0400, David Malcolm wrote:
> This implements the libgccjit support for must-tail-call via
> a new:
>   gcc_jit_rvalue_set_bool_require_tail_call
> API entrypoint.

It seems to me like that's not a great name, the rvalue and bool parts
are just about the argument types, not what the function does.  Wouldn't
gcc_jit_set_call_requires_tail_call be better?

Trev

Re: [PATCH] Fixes to must-tail-call tests

[Thomas Preudhomme]

Hi Rainer,

On Wednesday 25 May 2016 11:31:12 Rainer Orth wrote:
> David Malcolm <dmalcolm@redhat.com> writes:
> > The following fixes the known failures of the must-tail-call tests.
> > 
> > Tested with --target=
> > * aarch64-unknown-linux-gnu
> > * ia64-unknown-linux-gnu
> > * m68k-unknown-linux-gnu
> > * x86_64-pc-linux-gnu
> 
> Even with this patch, there are still failures on sparc-sun-solaris2.12:
> 
> FAIL: gcc.dg/plugin/must-tail-call-1.c -fplugin=./must_tail_call_plugin.so
> (test for excess errors)
> 
> Excess errors:
> /vol/gcc/src/hg/trunk/local/gcc/testsuite/gcc.dg/plugin/must-tail-call-1.c:1
> 2:10: error: cannot tail-call: target is not able to optimize the call into
> a sibling call
> 
> FAIL: gcc.dg/plugin/must-tail-call-2.c -fplugin=./must_tail_call_plugin.so
> (test for excess errors)
> 
> Excess errors:
> /vol/gcc/src/hg/trunk/local/gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c:3
> 2:10: error: cannot tail-call: target is not able to optimize the call into
> a sibling call

Now that the logic is in place, you probably want to add sparc-sun-solaris in 
plugin.exp to the the list of architecture where tail call plugin tests should 
be skipped, alongside Thumb-1 ARM targets.

Best regards,

Thomas

Re: [PATCH 1/3] Introduce can_implement_as_sibling_call_p

[Jeff Law]

On 05/17/2016 04:01 PM, David Malcolm wrote:
> This patch moves part of the logic for determining if tail
> call optimizations are possible to a new helper function.
>
> There are no functional changes.
>
> expand_call is 1300 lines long, so there's arguably a
> case for doing this on its own, but this change also
> enables the followup patch.
>
> The patch changes the logic from a big "if" with joined
> || clauses:
>
>   if (first_problem ()
>       ||second_problem ()
>       /* ...etc... */
>       ||final_problem ())
>      try_tail_call = 0;
>
> to a series of separate tests:
>
>   if (first_problem ())
>     return false;
>   if (second_problem ())
>     return false;
>   /* ...etc... */
>   if (final_problem ())
>     return false;
>
> I think the latter form has several advantages over the former:
> - IMHO it's easier to read
> - it makes it easy to put breakpoints on individual causes of failure
> - it makes it easy to put specific error messages on individual causes
>   of failure (as done in the followup patch).
>
> Successfully bootstrapped&regrtested on x86_64-pc-linux-gnu.
>
> OK for trunk?
>
> 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.
This is good in and of itself as a refactoring/cleanup change.  That 
code has grown quite a list of "don't tailcall when ..." cases.

OK for the trunk.

jeff

Re: [PATCH 0/3] Support for mandatory tail calls

[Jeff Law]

On 05/17/2016 04:01 PM, David Malcolm wrote:
> There have been requests [1] for libgccjit to better support
> functional programming by supporting the contination-passing style,
> in which every function "returns" by calling a "continuation"
> function pointer.
>
> These calls must be guaranteed to be implemented as a jump,
> otherwise the program could consume an arbitrary amount of stack
> space as it executed.
>
> This patch kit implements this.
>
> Patch 1 is a preliminary tweak to calls.c
>
> Patch 2 implements a new flag in tree.h: CALL_EXPR_MUST_TAIL_CALL,
> which makes calls.c try harder to implement a flagged call as a
> tail-call/sibling call, and makes it issue an error if
> the optimization is impossible.  It doesn't implement any
> frontend support for setting the flag (instead using a plugin
> to test it).  We had some discussion on the jit list about possibly
> introducing a new builtin for this, but the patch punts on this
> issue.
I wonder if we should have an attribute so that the flag can be set for 
C/C++ code.  I've seen requests for forcing tail calls in C/C++ code 
several times in the past, precisely to support continuations.

Jeff

[PATCH 3/3] jit: implement gcc_jit_rvalue_set_bool_require_tail_call

[David Malcolm]

This implements the libgccjit support for must-tail-call via
a new:
  gcc_jit_rvalue_set_bool_require_tail_call
API entrypoint.

(I didn't implement a wrapper for this within the C++ bindings)

Successfully bootstrapped&regrtested on x86_64-pc-linux-gnu.

gcc/jit/ChangeLog:
	* docs/topics/compatibility.rst: Add LIBGCCJIT_ABI_6.
	* docs/topics/expressions.rst (Function calls): Add documentation
	of gcc_jit_rvalue_set_bool_require_tail_call.
	* docs/_build/texinfo/libgccjit.texi: Regenerate.
	* jit-common.h (gcc::jit::recording::base_call): Add forward decl.
	* jit-playback.c: Within namespace gcc::jit::playback...
	(context::build_call) Add "require_tail_call" param and use it
	to set CALL_EXPR_MUST_TAIL_CALL.
	(context::new_call): Add "require_tail_call" param.
	(context::new_call_through_ptr): Likewise.
	* jit-playback.h: Within namespace gcc::jit::playback...
	(context::new_call: Add "require_tail_call" param.
	(context::new_call_through_ptr): Likewise.
	(context::build_call): Likewise.
	* jit-recording.c: Within namespace gcc::jit::recording...
	(base_call::base_call): New constructor.
	(base_call::write_reproducer_tail_call): New method.
	(call::call): Update for inheritance from base_call.
	(call::replay_into): Provide m_require_tail_call to call
	to new_call.
	(call::write_reproducer): Call write_reproducer_tail_call.
	(call_through_ptr::call_through_ptr): Update for inheritance from
	base_call.
	(call_through_ptr::replay_into): Provide m_require_tail_call to call
	to new_call_through_ptr.
	(recording::call_through_ptr::write_reproducer): Call
	write_reproducer_tail_call.
	* jit-recording.h: Within namespace gcc::jit::recording...
	(rvalue::dyn_cast_base_call): New virtual function.
	(class base_call): New subclass of class rvalue.
	(class call): Inherit from base_call rather than directly from
	rvalue, moving get_precedence and m_args to base_call.
	(class call_through_ptr): Likewise.
	* libgccjit.c (gcc_jit_rvalue_set_bool_require_tail_call): New
	function.
	* libgccjit.h
	(LIBGCCJIT_HAVE_gcc_jit_rvalue_set_bool_require_tail_call): New
	macro.
	(gcc_jit_rvalue_set_bool_require_tail_call): New function.
	* libgccjit.map (LIBGCCJIT_ABI_6): New.
	(gcc_jit_rvalue_set_bool_require_tail_call): Add.

gcc/testsuite/ChangeLog:
	* jit.dg/all-non-failing-tests.h: Add
	test-factorial-must-tail-call.c.
	* jit.dg/test-error-impossible-must-tail-call.c: New test case.
	* jit.dg/test-factorial-must-tail-call.c: New test case.
---
 gcc/jit/docs/topics/compatibility.rst              |   7 ++
 gcc/jit/docs/topics/expressions.rst                |  24 +++++
 gcc/jit/jit-common.h                               |   1 +
 gcc/jit/jit-playback.c                             |  23 +++--
 gcc/jit/jit-playback.h                             |   9 +-
 gcc/jit/jit-recording.c                            |  60 +++++++++---
 gcc/jit/jit-recording.h                            |  46 ++++++---
 gcc/jit/libgccjit.c                                |  20 ++++
 gcc/jit/libgccjit.h                                |  13 +++
 gcc/jit/libgccjit.map                              |   5 +
 gcc/testsuite/jit.dg/all-non-failing-tests.h       |  10 ++
 .../jit.dg/test-error-impossible-must-tail-call.c  |  93 ++++++++++++++++++
 .../jit.dg/test-factorial-must-tail-call.c         | 109 +++++++++++++++++++++
 13 files changed, 382 insertions(+), 38 deletions(-)
 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

diff --git a/gcc/jit/docs/topics/compatibility.rst b/gcc/jit/docs/topics/compatibility.rst
index d9eacf2..7abd050 100644
--- a/gcc/jit/docs/topics/compatibility.rst
+++ b/gcc/jit/docs/topics/compatibility.rst
@@ -135,3 +135,10 @@ entrypoints:
 -------------------
 ``LIBGCCJIT_ABI_5`` covers the addition of
 :func:`gcc_jit_context_set_bool_use_external_driver`
+
+.. _LIBGCCJIT_ABI_6:
+
+``LIBGCCJIT_ABI_6``
+-------------------
+``LIBGCCJIT_ABI_6`` covers the addition of
+:func:`gcc_jit_rvalue_set_bool_require_tail_call`
diff --git a/gcc/jit/docs/topics/expressions.rst b/gcc/jit/docs/topics/expressions.rst
index 0445332..261483c 100644
--- a/gcc/jit/docs/topics/expressions.rst
+++ b/gcc/jit/docs/topics/expressions.rst
@@ -424,6 +424,30 @@ Function calls
 
       The same caveat as for :c:func:`gcc_jit_context_new_call` applies.
 
+.. function:: void\
+              gcc_jit_rvalue_set_bool_require_tail_call (gcc_jit_rvalue *call,\
+                                                         int require_tail_call)
+
+   Given an :c:type:`gcc_jit_rvalue *` for a call created through
+   :c:func:`gcc_jit_context_new_call` or
+   :c:func:`gcc_jit_context_new_call_through_ptr`, mark/clear the
+   call as needing tail-call optimization.  The optimizer will
+   attempt to optimize the call into a jump instruction; if it is
+   unable to do do, an error will be emitted.
+
+   This may be useful when implementing functions that use the
+   continuation-passing style (e.g. for functional programming
+   languages), in which every function "returns" by calling a
+   "continuation" function pointer.  This call must be
+   guaranteed to be implemented as a jump, otherwise the program
+   could consume an arbitrary amount of stack space as it executed.
+
+   This entrypoint was added in :ref:`LIBGCCJIT_ABI_6`; you can test for
+   its presence using
+
+   .. code-block:: c
+
+      #ifdef LIBGCCJIT_HAVE_gcc_jit_rvalue_set_bool_require_tail_call
 
 Type-coercion
 *************
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 156448d..c9f4084 100644
--- a/gcc/jit/jit-playback.c
+++ b/gcc/jit/jit-playback.c
@@ -854,7 +854,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 ());
@@ -868,9 +869,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
@@ -890,7 +895,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;
 
@@ -902,7 +908,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
@@ -912,12 +918,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 8f7a43d..c00c258 100644
--- a/gcc/jit/jit-playback.h
+++ b/gcc/jit/jit-playback.h
@@ -133,12 +133,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,
@@ -236,7 +238,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..9376342 100644
--- a/gcc/jit/jit-recording.c
+++ b/gcc/jit/jit-recording.c
@@ -4681,6 +4681,39 @@ 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]);
+}
+
+/* Subroutine for use by call and call_though_ptr's write_reproducer
+   methods.  */
+
+void
+recording::base_call::write_reproducer_tail_call (reproducer &r,
+						  const char *id)
+{
+  if (m_require_tail_call)
+    {
+      r.write ("  gcc_jit_rvalue_set_bool_require_tail_call (%s,  /* gcc_jit_rvalue *call*/\n"
+	       "                                             %i); /* int require_tail_call*/\n",
+	       id,
+	       1);
+    }
+}
+
 /* The implementation of class gcc::jit::recording::call.  */
 
 /* The constructor for gcc::jit::recording::call.  */
@@ -4690,12 +4723,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 +4741,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
@@ -4790,6 +4821,7 @@ recording::call::write_reproducer (reproducer &r)
 	   r.get_identifier (m_func),
 	   m_args.length (),
 	   args_id);
+  write_reproducer_tail_call (r, id);
 }
 
 /* The implementation of class gcc::jit::recording::call_through_ptr.  */
@@ -4801,14 +4833,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 +4854,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
@@ -4907,6 +4938,7 @@ recording::call_through_ptr::write_reproducer (reproducer &r)
 	   r.get_identifier_as_rvalue (m_fn_ptr),
 	   m_args.length (),
 	   args_id);
+  write_reproducer_tail_call (r, id);
 }
 
 /* The implementation of class gcc::jit::recording::array_access.  */
diff --git a/gcc/jit/jit-recording.h b/gcc/jit/jit-recording.h
index 1c3e763..0e3511c 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,36 @@ 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:
+  void write_reproducer_tail_call (reproducer &r, const char *id);
+
+ protected:
+  auto_vec<rvalue *> m_args;
+  bool m_require_tail_call;
+};
+
+class call : public base_call
 {
 public:
   call (context *ctxt,
@@ -1434,17 +1464,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 +1485,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..c2c6aeb 100644
--- a/gcc/jit/libgccjit.c
+++ b/gcc/jit/libgccjit.c
@@ -2950,3 +2950,23 @@ gcc_jit_timer_print (gcc_jit_timer *timer,
   timer->start (TV_TOTAL);
   timer->push (TV_JIT_CLIENT_CODE);
 }
+
+/* Public entrypoint.  See description in libgccjit.h.
+
+   After error-checking, the real work is effectively done by the
+   gcc::jit::base_call::set_require_tail_call setter in jit-recording.h.  */
+
+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);
+}
diff --git a/gcc/jit/libgccjit.h b/gcc/jit/libgccjit.h
index a8b9f55..175cc16c 100644
--- a/gcc/jit/libgccjit.h
+++ b/gcc/jit/libgccjit.h
@@ -1374,6 +1374,19 @@ extern void
 gcc_jit_timer_print (gcc_jit_timer *timer,
 		     FILE *f_out);
 
+
+#define LIBGCCJIT_HAVE_gcc_jit_rvalue_set_bool_require_tail_call
+
+/* Mark/clear a call as needing tail-call optimization.
+
+   This API entrypoint was added in LIBGCCJIT_ABI_6; you can test for its
+   presence using
+     #ifdef LIBGCCJIT_HAVE_gcc_jit_rvalue_set_bool_require_tail_call
+*/
+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..3e2b3b9 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
@@ -272,6 +279,9 @@ const struct testcase testcases[] = {
   {"factorial",
    create_code_factorial,
    verify_code_factorial},
+  {"factorial_must_tail_call",
+   create_code_factorial_must_tail_call,
+   verify_code_factorial_must_tail_call},
   {"fibonacci",
    create_code_fibonacci,
    verify_code_fibonacci},
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..8848d30
--- /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: callee returns a structure");
+}
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

Re: [PATCH 2/3] Implement CALL_EXPR_MUST_TAIL_CALL

[Andreas Schwab]

David Malcolm <dmalcolm@redhat.com> writes:

> 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..c5504f8
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c
> @@ -0,0 +1,58 @@
> +/* Allow nested functions.  */
> +/* { dg-options "-Wno-pedantic" } */
> +
> +struct box { char field[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: callee returns a structure" } */
> +}
> +
> +int __attribute__((noinline,noclone))
> +test_2_callee (int i, struct box b)
> +{
> +  if (b.field[0])
> +    return 5;
> +  return i * i;
> +}
> +
> +int __attribute__((noinline,noclone))
> +test_2_caller (int i)
> +{
> +  struct box b;
> +  return test_2_callee (i + 1, b); /* { dg-error "cannot tail-call: callee required more stack slots than the caller" } */
> +}
> +
> +extern void setjmp (void);
> +void
> +test_3 (void)
> +{
> +  setjmp (); /* { dg-error "cannot tail-call: callee returns twice" } */
> +}
> +
> +void
> +test_4 (void)
> +{
> +  void nested (void)
> +  {
> +  }
> +  nested (); /* { dg-error "cannot tail-call: nested function" } */
> +}
> +
> +typedef void (fn_ptr_t) (void);
> +volatile fn_ptr_t fn_ptr;
> +
> +void
> +test_5 (void)
> +{
> +  fn_ptr (); /* { dg-error "cannot tail-call: callee does not return" } */
> +}

On aarch64:

FAIL: gcc.dg/plugin/must-tail-call-2.c -fplugin=./must_tail_call_plugin.so  (test for errors, line 32)
FAIL: gcc.dg/plugin/must-tail-call-2.c -fplugin=./must_tail_call_plugin.so (test for excess errors)
Excess errors:
gcc.dg/plugin/must-tail-call-2.c:32:10: error: cannot tail-call: argument must be passed by copying

Andreas.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Re: [PATCH 0/3] Support for mandatory tail calls

[Jason Merrill]

On Thu, May 19, 2016 at 9:28 AM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Thu, May 19, 2016 at 3:19 PM, Jason Merrill <jason@redhat.com> wrote:
>> On Thu, May 19, 2016 at 12:30 AM, Basile Starynkevitch
>> <basile@starynkevitch.net> wrote:
>>> On 05/19/2016 12:12 AM, Jeff Law wrote:
>>>>
>>>> On 05/17/2016 04:01 PM, David Malcolm wrote:
>>>>>
>>>>> There have been requests [1] for libgccjit to better support
>>>>> functional programming by supporting the contination-passing style,
>>>>> in which every function "returns" by calling a "continuation"
>>>>> function pointer.
>>>>>
>>>>> These calls must be guaranteed to be implemented as a jump,
>>>>> otherwise the program could consume an arbitrary amount of stack
>>>>> space as it executed.
>>>>>
>>>>> This patch kit implements this.
>>>>>
>>>>> Patch 1 is a preliminary tweak to calls.c
>>>>>
>>>>> Patch 2 implements a new flag in tree.h: CALL_EXPR_MUST_TAIL_CALL,
>>>>> which makes calls.c try harder to implement a flagged call as a
>>>>> tail-call/sibling call, and makes it issue an error if
>>>>> the optimization is impossible.  It doesn't implement any
>>>>> frontend support for setting the flag (instead using a plugin
>>>>> to test it).  We had some discussion on the jit list about possibly
>>>>> introducing a new builtin for this, but the patch punts on this
>>>>> issue.
>>>>
>>>> I wonder if we should have an attribute so that the flag can be set for
>>>> C/C++ code.  I've seen requests for forcing tail calls in C/C++ code several
>>>> times in the past, precisely to support continuations.
>>>
>>> Why an attribute? Attributes are on declarations. I think it should better
>>> be some pragma like _Pragma(GCC tail cail, foo(x,y)) or some builtin (or
>>> else some syntax extension like goto return foo(x,y); ...) because what we
>>> really want is to annotate a particular call to be tail-recursive.
>>
>> C++11 attributes can apply to expression-statements as well, e.g.
>>
>> [[gnu::tail_call]] fn();
>>
>> though not to sub-expressions.
>
> That's nice.  Can they apply to things like loops?
>
>  [[gnu::no_unroll]] for (int i=0; i<4; ++i)
>    a[i] = 0;

Yes, to any statement.

Jason

Re: [PATCH] Fixes to must-tail-call tests

[Jeff Law]

On 05/27/2016 11:44 AM, David Malcolm wrote:
> On Fri, 2016-05-27 at 13:29 +0100, Thomas Preudhomme wrote:
>> Hi Rainer,
>>
>> On Wednesday 25 May 2016 11:31:12 Rainer Orth wrote:
>>> David Malcolm <dmalcolm@redhat.com> writes:
>>>> The following fixes the known failures of the must-tail-call
>>>> tests.
>>>>
>>>> Tested with --target=
>>>> * aarch64-unknown-linux-gnu
>>>> * ia64-unknown-linux-gnu
>>>> * m68k-unknown-linux-gnu
>>>> * x86_64-pc-linux-gnu
>>>
>>> Even with this patch, there are still failures on sparc-sun
>>> -solaris2.12:
>>>
>>> FAIL: gcc.dg/plugin/must-tail-call-1.c
>>> -fplugin=./must_tail_call_plugin.so
>>> (test for excess errors)
>>>
>>> Excess errors:
>>> /vol/gcc/src/hg/trunk/local/gcc/testsuite/gcc.dg/plugin/must-tail
>>> -call-1.c:1
>>> 2:10: error: cannot tail-call: target is not able to optimize the
>>> call into
>>> a sibling call
>>>
>>> FAIL: gcc.dg/plugin/must-tail-call-2.c
>>> -fplugin=./must_tail_call_plugin.so
>>> (test for excess errors)
>>>
>>> Excess errors:
>>> /vol/gcc/src/hg/trunk/local/gcc/testsuite/gcc.dg/plugin/must-tail
>>> -call-2.c:3
>>> 2:10: error: cannot tail-call: target is not able to optimize the
>>> call into
>>> a sibling call
>
>
> My aim with these tests was to try to cover the various ways in which
> mandatory tail-call optimization can fail.
>
> However, this is very target-dependent, and, as written, the test over
> -specifies the output.
>
> Sorry about this.
>
> I've run the test on all of the configurations in contrib/config
> -list.mk (using the patch kit in
>   https://gcc.gnu.org/ml/gcc-patches/2016-05/msg02100.html )
>
> Collated output can be seen here:
>   https://dmalcolm.fedorapeople.org/gcc/2016-05-27/must-tail-call-logs.txt
> showing all the different error messages across every configuration.
>
> It's not clear to me what the best way forward here is.
> We could simply check for
>    error: cannot tail-call:
> and leave the precise messages we're checking for unspecified.
>
> If we care about checking for the precise messages, one of more
> duplicate copy(s) of the test could be provided, filtering by target to
> specify precise targets, giving more precise output, where this is
> known.
>
> I'm attaching a patch (sans ChangeLog) which strips the precise
> messages in the manner described above.  Retesting on all targets with
> this patch, the only remaining failures are of the form:
>   must-tail-call-1.c:12:10: error: cannot tail-call: machine
> description does not have a sibcall_epilogue instruction pattern
> on targets lacking the pattern.
>
> Thoughts?
I probably should have caught this -- there's all kinds of oddball 
reasons why we might not be able to optimize a tail call, some of which 
are target dependent.

I think trying to give highly precise messages is doomed to long term 
maintenance headaches because they're going to be target dependent.

So I'd go with just stripping the precise messages like you've done.

jeff

Re: [PATCH 1/3] Introduce can_implement_as_sibling_call_p

[Kyrill Tkachov]

Hi David,

On 17/05/16 23:01, David Malcolm wrote:
> This patch moves part of the logic for determining if tail
> call optimizations are possible to a new helper function.
>
> There are no functional changes.
>
> expand_call is 1300 lines long, so there's arguably a
> case for doing this on its own, but this change also
> enables the followup patch.
>
> The patch changes the logic from a big "if" with joined
> || clauses:
>
>    if (first_problem ()
>        ||second_problem ()
>        /* ...etc... */
>        ||final_problem ())
>       try_tail_call = 0;
>
> to a series of separate tests:
>
>    if (first_problem ())
>      return false;
>    if (second_problem ())
>      return false;
>    /* ...etc... */
>    if (final_problem ())
>      return false;
>
> I think the latter form has several advantages over the former:
> - IMHO it's easier to read
> - it makes it easy to put breakpoints on individual causes of failure
> - it makes it easy to put specific error messages on individual causes
>    of failure (as done in the followup patch).
>
> Successfully bootstrapped&regrtested on x86_64-pc-linux-gnu.
>
> OK for trunk?
>
> 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
> +

REG_PARM_STACK_SPACE is not defined on arm, which makes reg_parm_stack_space
unused in this function and so breaks bootstrap on arm.
Can you please add an ATTRIBUTE_UNUSED to reg_parm_stack_space?

Thanks,
Kyrill

> +  /* 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.  */

[PATCH] calls.c: fix warning on targets without REG_PARM_STACK_SPACE

[David Malcolm]

On Fri, 2016-05-20 at 18:03 +0100, Kyrill Tkachov wrote:
[...snip...]
> REG_PARM_STACK_SPACE is not defined on arm, which makes
> reg_parm_stack_space
> unused in this function and so breaks bootstrap on arm.
> Can you please add an ATTRIBUTE_UNUSED to reg_parm_stack_space?
> 
> Thanks,
> Kyrill
[...snip...]

Sorry about the breakage.

I manually verified that the following fixes the warning with
--target=arm-linux-gnueabi.

Successfully bootstrapped&regrtested on x86_64-pc-linux-gnu.

Committed to trunk as r236527.

gcc/ChangeLog:
	* calls.c (can_implement_as_sibling_call_p): Mark param
	reg_parm_stack_space with ATTRIBUTE_UNUSED.
---
 gcc/calls.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/gcc/calls.c b/gcc/calls.c
index 1b12eca..587969f 100644
--- a/gcc/calls.c
+++ b/gcc/calls.c
@@ -2373,7 +2373,7 @@ static bool
 can_implement_as_sibling_call_p (tree exp,
 				 rtx structure_value_addr,
 				 tree funtype,
-				 int reg_parm_stack_space,
+				 int reg_parm_stack_space ATTRIBUTE_UNUSED,
 				 tree fndecl,
 				 int flags,
 				 tree addr,
-- 
1.8.5.3

Re: [PATCH 3/3] jit: implement gcc_jit_rvalue_set_bool_require_tail_call

[David Malcolm]

On Tue, 2016-05-17 at 18:49 -0400, Trevor Saunders wrote:
> On Tue, May 17, 2016 at 06:01:32PM -0400, David Malcolm wrote:
> > This implements the libgccjit support for must-tail-call via
> > a new:
> >   gcc_jit_rvalue_set_bool_require_tail_call
> > API entrypoint.
> 
> It seems to me like that's not a great name, the rvalue and bool
> parts
> are just about the argument types, not what the function does. 
>  Wouldn't
> gcc_jit_set_call_requires_tail_call be better?

Maybe.  I was thinking of it from the point of view of methods; it's
effectively a method on gcc_jit_rvalue.  The "set_bool" is for
consistency with various gcc_jit_context_ entrypoints.

FWIW, I've committed the patch as-is; all of the must-tail-call patches
are now in trunk, as of r236531.

Re: [PATCH] Fixes to must-tail-call tests

[Rainer Orth]

David Malcolm <dmalcolm@redhat.com> writes:

> The following fixes the known failures of the must-tail-call tests.
>
> Tested with --target=
> * aarch64-unknown-linux-gnu
> * ia64-unknown-linux-gnu
> * m68k-unknown-linux-gnu
> * x86_64-pc-linux-gnu

Even with this patch, there are still failures on sparc-sun-solaris2.12:

FAIL: gcc.dg/plugin/must-tail-call-1.c -fplugin=./must_tail_call_plugin.so (test for excess errors)

Excess errors:
/vol/gcc/src/hg/trunk/local/gcc/testsuite/gcc.dg/plugin/must-tail-call-1.c:12:10: error: cannot tail-call: target is not able to optimize the call into a sibling call

FAIL: gcc.dg/plugin/must-tail-call-2.c -fplugin=./must_tail_call_plugin.so (test for excess errors)

Excess errors:
/vol/gcc/src/hg/trunk/local/gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c:32:10: error: cannot tail-call: target is not able to optimize the call into a sibling call

	Rainer

-- 
-----------------------------------------------------------------------------
Rainer Orth, Center for Biotechnology, Bielefeld University

Re: [PATCH 0/3] Support for mandatory tail calls

[Basile Starynkevitch]

On 05/19/2016 12:12 AM, Jeff Law wrote:
> On 05/17/2016 04:01 PM, David Malcolm wrote:
>> There have been requests [1] for libgccjit to better support
>> functional programming by supporting the contination-passing style,
>> in which every function "returns" by calling a "continuation"
>> function pointer.
>>
>> These calls must be guaranteed to be implemented as a jump,
>> otherwise the program could consume an arbitrary amount of stack
>> space as it executed.
>>
>> This patch kit implements this.
>>
>> Patch 1 is a preliminary tweak to calls.c
>>
>> Patch 2 implements a new flag in tree.h: CALL_EXPR_MUST_TAIL_CALL,
>> which makes calls.c try harder to implement a flagged call as a
>> tail-call/sibling call, and makes it issue an error if
>> the optimization is impossible.  It doesn't implement any
>> frontend support for setting the flag (instead using a plugin
>> to test it).  We had some discussion on the jit list about possibly
>> introducing a new builtin for this, but the patch punts on this
>> issue.
> I wonder if we should have an attribute so that the flag can be set 
> for C/C++ code.  I've seen requests for forcing tail calls in C/C++ 
> code several times in the past, precisely to support continuations.

Why an attribute? Attributes are on declarations. I think it should 
better be some pragma like _Pragma(GCC tail cail, foo(x,y)) or some 
builtin (or else some syntax extension like goto return foo(x,y); ...) 
because what we really want is to annotate a particular call to be 
tail-recursive.

Cheers

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

[PATCH] Fixes to must-tail-call tests

[David Malcolm]

The following fixes the known failures of the must-tail-call tests.

Tested with --target=
* aarch64-unknown-linux-gnu
* ia64-unknown-linux-gnu
* m68k-unknown-linux-gnu
* x86_64-pc-linux-gnu
 
OK for trunk?

gcc/testsuite/ChangeLog:
	* gcc.dg/plugin/must-tail-call-2.c (test_2_caller): Generalize
	expected error message to allow "argument must by passed by
	copying".
	(test_3): Generalize expected error message to allow for failure
	of targetm.function_ok_for_sibcall.
	(test_4): Likewise.
	(test_5): Likewise.
---
 gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

diff --git a/gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c b/gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c
index c5504f8..ca81b35 100644
--- a/gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c
+++ b/gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c
@@ -29,14 +29,14 @@ int __attribute__((noinline,noclone))
 test_2_caller (int i)
 {
   struct box b;
-  return test_2_callee (i + 1, b); /* { dg-error "cannot tail-call: callee required more stack slots than the caller" } */
+  return test_2_callee (i + 1, b); /* { dg-error "cannot tail-call: callee required more stack slots than the caller|argument must be passed by copying" } */
 }
 
 extern void setjmp (void);
 void
 test_3 (void)
 {
-  setjmp (); /* { dg-error "cannot tail-call: callee returns twice" } */
+  setjmp (); /* { dg-error "cannot tail-call: callee returns twice|target is not able to optimize the call into a sibling call" } */
 }
 
 void
@@ -45,7 +45,7 @@ test_4 (void)
   void nested (void)
   {
   }
-  nested (); /* { dg-error "cannot tail-call: nested function" } */
+  nested (); /* { dg-error "cannot tail-call: nested function|target is not able to optimize the call into a sibling call" } */
 }
 
 typedef void (fn_ptr_t) (void);
@@ -54,5 +54,5 @@ volatile fn_ptr_t fn_ptr;
 void
 test_5 (void)
 {
-  fn_ptr (); /* { dg-error "cannot tail-call: callee does not return" } */
+  fn_ptr (); /* { dg-error "cannot tail-call: callee does not return|target is not able to optimize the call into a sibling call" } */
 }
-- 
1.8.5.3

[PATCH 0/3] Support for mandatory tail calls

[David Malcolm]

There have been requests [1] for libgccjit to better support
functional programming by supporting the contination-passing style,
in which every function "returns" by calling a "continuation"
function pointer.

These calls must be guaranteed to be implemented as a jump,
otherwise the program could consume an arbitrary amount of stack
space as it executed.

This patch kit implements this.

Patch 1 is a preliminary tweak to calls.c

Patch 2 implements a new flag in tree.h: CALL_EXPR_MUST_TAIL_CALL,
which makes calls.c try harder to implement a flagged call as a
tail-call/sibling call, and makes it issue an error if
the optimization is impossible.  It doesn't implement any
frontend support for setting the flag (instead using a plugin
to test it).  We had some discussion on the jit list about possibly
introducing a new builtin for this, but the patch punts on this
issue.

Patch 3 implements the libgccjit.h API support to allow client
code to set the flag.

[1] https://gcc.gnu.org/ml/jit/2016-q2/msg00010.html

David Malcolm (3):
  Introduce can_implement_as_sibling_call_p
  Implement CALL_EXPR_MUST_TAIL_CALL
  jit: implement gcc_jit_rvalue_set_bool_require_tail_call

 gcc/calls.c                                        | 211 +++++++++++++++++----
 gcc/cfgexpand.c                                    |   1 +
 gcc/gimple-pretty-print.c                          |   2 +
 gcc/gimple.c                                       |   1 +
 gcc/gimple.h                                       |  20 ++
 gcc/jit/docs/topics/compatibility.rst              |   7 +
 gcc/jit/docs/topics/expressions.rst                |  24 +++
 gcc/jit/jit-common.h                               |   1 +
 gcc/jit/jit-playback.c                             |  23 ++-
 gcc/jit/jit-playback.h                             |   9 +-
 gcc/jit/jit-recording.c                            |  60 ++++--
 gcc/jit/jit-recording.h                            |  46 +++--
 gcc/jit/libgccjit.c                                |  20 ++
 gcc/jit/libgccjit.h                                |  13 ++
 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     |  58 ++++++
 .../gcc.dg/plugin/must_tail_call_plugin.c          |  76 ++++++++
 gcc/testsuite/gcc.dg/plugin/plugin.exp             |   3 +
 gcc/testsuite/jit.dg/all-non-failing-tests.h       |  10 +
 .../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                                         |   5 +
 25 files changed, 744 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_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

Re: [PATCH 0/3] Support for mandatory tail calls

[Jason Merrill]

On Thu, May 19, 2016 at 12:30 AM, Basile Starynkevitch
<basile@starynkevitch.net> wrote:
> On 05/19/2016 12:12 AM, Jeff Law wrote:
>>
>> On 05/17/2016 04:01 PM, David Malcolm wrote:
>>>
>>> There have been requests [1] for libgccjit to better support
>>> functional programming by supporting the contination-passing style,
>>> in which every function "returns" by calling a "continuation"
>>> function pointer.
>>>
>>> These calls must be guaranteed to be implemented as a jump,
>>> otherwise the program could consume an arbitrary amount of stack
>>> space as it executed.
>>>
>>> This patch kit implements this.
>>>
>>> Patch 1 is a preliminary tweak to calls.c
>>>
>>> Patch 2 implements a new flag in tree.h: CALL_EXPR_MUST_TAIL_CALL,
>>> which makes calls.c try harder to implement a flagged call as a
>>> tail-call/sibling call, and makes it issue an error if
>>> the optimization is impossible.  It doesn't implement any
>>> frontend support for setting the flag (instead using a plugin
>>> to test it).  We had some discussion on the jit list about possibly
>>> introducing a new builtin for this, but the patch punts on this
>>> issue.
>>
>> I wonder if we should have an attribute so that the flag can be set for
>> C/C++ code.  I've seen requests for forcing tail calls in C/C++ code several
>> times in the past, precisely to support continuations.
>
> Why an attribute? Attributes are on declarations. I think it should better
> be some pragma like _Pragma(GCC tail cail, foo(x,y)) or some builtin (or
> else some syntax extension like goto return foo(x,y); ...) because what we
> really want is to annotate a particular call to be tail-recursive.

C++11 attributes can apply to expression-statements as well, e.g.

[[gnu::tail_call]] fn();

though not to sub-expressions.

Jason

Re: [PATCH 2/3] Implement CALL_EXPR_MUST_TAIL_CALL

[Jeff Law]

On 05/17/2016 04:01 PM, David Malcolm wrote:
> This patch implements support for marking CALL_EXPRs
> as being mandatory for tail-call-optimization. expand_call
> tries harder to perform the optimization on such CALL_EXPRs,
> and issues an error if it fails.
>
> Currently this flag isn't accessible from any frontend,
> so the patch uses a plugin for testing the functionality.
>
> Successfully bootstrapped&regrtested on x86_64-pc-linux-gnu;
> adds 8 PASS results to gcc.sum.
>
> OK for trunk?
>
> gcc/ChangeLog:
> 	* calls.c (maybe_complain_about_tail_call): New function.
> 	(initialize_argument_information): Call
> 	maybe_complain_about_tail_call when clearing *may_tailcall.
> 	(can_implement_as_sibling_call_p): Call
> 	maybe_complain_about_tail_call when returning false.
> 	(expand_call): Read CALL_EXPR_MUST_TAIL_CALL and, if set,
> 	ensure try_tail_call is set.  Call maybe_complain_about_tail_call
> 	if tail-call optimization fails.
> 	* cfgexpand.c (expand_call_stmt): Initialize
> 	CALL_EXPR_MUST_TAIL_CALL from gimple_call_must_tail_p.
> 	* gimple-pretty-print.c (dump_gimple_call): Dump
> 	gimple_call_must_tail_p.
> 	* gimple.c (gimple_build_call_from_tree): Call
> 	gimple_call_set_must_tail with the value of
> 	CALL_EXPR_MUST_TAIL_CALL.
> 	* gimple.h (enum gf_mask): Add GF_CALL_MUST_TAIL_CALL.
> 	(gimple_call_set_must_tail): New function.
> 	(gimple_call_must_tail_p): New function.
> 	* print-tree.c (print_node): Update printing of TREE_STATIC
> 	to reflect its use for CALL_EXPR_MUST_TAIL_CALL.
> 	* tree-core.h (struct tree_base): Add MUST_TAIL_CALL to the
> 	trailing comment listing applicable flags.
> 	* tree.h (CALL_EXPR_MUST_TAIL_CALL): New macro.
It's actually simpler than it looks -- most of the changes are just 
getting better diagnostics when tail call fails, which I wholeheartedly 
support.

OK for the trunk.


Thanks,
Jeff

Re: [PATCH] Fixes to must-tail-call tests

[David Malcolm]

[-- Attachment #1: Type: text/plain, Size: 2757 bytes --]

On Fri, 2016-05-27 at 13:29 +0100, Thomas Preudhomme wrote:
> Hi Rainer,
> 
> On Wednesday 25 May 2016 11:31:12 Rainer Orth wrote:
> > David Malcolm <dmalcolm@redhat.com> writes:
> > > The following fixes the known failures of the must-tail-call
> > > tests.
> > > 
> > > Tested with --target=
> > > * aarch64-unknown-linux-gnu
> > > * ia64-unknown-linux-gnu
> > > * m68k-unknown-linux-gnu
> > > * x86_64-pc-linux-gnu
> > 
> > Even with this patch, there are still failures on sparc-sun
> > -solaris2.12:
> > 
> > FAIL: gcc.dg/plugin/must-tail-call-1.c 
> > -fplugin=./must_tail_call_plugin.so
> > (test for excess errors)
> > 
> > Excess errors:
> > /vol/gcc/src/hg/trunk/local/gcc/testsuite/gcc.dg/plugin/must-tail
> > -call-1.c:1
> > 2:10: error: cannot tail-call: target is not able to optimize the
> > call into
> > a sibling call
> > 
> > FAIL: gcc.dg/plugin/must-tail-call-2.c 
> > -fplugin=./must_tail_call_plugin.so
> > (test for excess errors)
> > 
> > Excess errors:
> > /vol/gcc/src/hg/trunk/local/gcc/testsuite/gcc.dg/plugin/must-tail
> > -call-2.c:3
> > 2:10: error: cannot tail-call: target is not able to optimize the
> > call into
> > a sibling call


My aim with these tests was to try to cover the various ways in which
mandatory tail-call optimization can fail.

However, this is very target-dependent, and, as written, the test over
-specifies the output.

Sorry about this.

I've run the test on all of the configurations in contrib/config
-list.mk (using the patch kit in
  https://gcc.gnu.org/ml/gcc-patches/2016-05/msg02100.html )

Collated output can be seen here:
  https://dmalcolm.fedorapeople.org/gcc/2016-05-27/must-tail-call-logs.txt
showing all the different error messages across every configuration.

It's not clear to me what the best way forward here is.
We could simply check for
   error: cannot tail-call:
and leave the precise messages we're checking for unspecified.

If we care about checking for the precise messages, one of more
duplicate copy(s) of the test could be provided, filtering by target to
specify precise targets, giving more precise output, where this is
known.

I'm attaching a patch (sans ChangeLog) which strips the precise
messages in the manner described above.  Retesting on all targets with
this patch, the only remaining failures are of the form:
  must-tail-call-1.c:12:10: error: cannot tail-call: machine
description does not have a sibcall_epilogue instruction pattern
on targets lacking the pattern.

Thoughts?

Sorry again about the breakage

Dave


> Now that the logic is in place, you probably want to add sparc-sun
> -solaris in 
> plugin.exp to the the list of architecture where tail call plugin
> tests should 
> be skipped, alongside Thumb-1 ARM targets.
> 
> Best regards,
> 

[-- Attachment #2: generic-error-message.patch --]
[-- Type: text/x-patch, Size: 1489 bytes --]

diff --git a/gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c b/gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c
index c5504f8..c6dfecd 100644
--- a/gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c
+++ b/gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c
@@ -14,7 +14,7 @@ returns_struct (int i)
 int __attribute__((noinline,noclone))
 test_1 (int i)
 {
-  return returns_struct (i * 5).i; /* { dg-error "cannot tail-call: callee returns a structure" } */
+  return returns_struct (i * 5).i; /* { dg-error "cannot tail-call: " } */
 }
 
 int __attribute__((noinline,noclone))
@@ -29,14 +29,14 @@ int __attribute__((noinline,noclone))
 test_2_caller (int i)
 {
   struct box b;
-  return test_2_callee (i + 1, b); /* { dg-error "cannot tail-call: callee required more stack slots than the caller" } */
+  return test_2_callee (i + 1, b); /* { dg-error "cannot tail-call: " } */
 }
 
 extern void setjmp (void);
 void
 test_3 (void)
 {
-  setjmp (); /* { dg-error "cannot tail-call: callee returns twice" } */
+  setjmp (); /* { dg-error "cannot tail-call: " } */
 }
 
 void
@@ -45,7 +45,7 @@ test_4 (void)
   void nested (void)
   {
   }
-  nested (); /* { dg-error "cannot tail-call: nested function" } */
+  nested (); /* { dg-error "cannot tail-call: " } */
 }
 
 typedef void (fn_ptr_t) (void);
@@ -54,5 +54,5 @@ volatile fn_ptr_t fn_ptr;
 void
 test_5 (void)
 {
-  fn_ptr (); /* { dg-error "cannot tail-call: callee does not return" } */
+  fn_ptr (); /* { dg-error "cannot tail-call: " } */
 }

[PATCH 2/3] Implement CALL_EXPR_MUST_TAIL_CALL

[David Malcolm]

This patch implements support for marking CALL_EXPRs
as being mandatory for tail-call-optimization. expand_call
tries harder to perform the optimization on such CALL_EXPRs,
and issues an error if it fails.

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

Successfully bootstrapped&regrtested on x86_64-pc-linux-gnu;
adds 8 PASS results to gcc.sum.

OK for trunk?

gcc/ChangeLog:
	* calls.c (maybe_complain_about_tail_call): New function.
	(initialize_argument_information): Call
	maybe_complain_about_tail_call when clearing *may_tailcall.
	(can_implement_as_sibling_call_p): Call
	maybe_complain_about_tail_call when returning false.
	(expand_call): Read CALL_EXPR_MUST_TAIL_CALL and, if set,
	ensure try_tail_call is set.  Call maybe_complain_about_tail_call
	if tail-call optimization fails.
	* cfgexpand.c (expand_call_stmt): Initialize
	CALL_EXPR_MUST_TAIL_CALL from gimple_call_must_tail_p.
	* gimple-pretty-print.c (dump_gimple_call): Dump
	gimple_call_must_tail_p.
	* gimple.c (gimple_build_call_from_tree): Call
	gimple_call_set_must_tail with the value of
	CALL_EXPR_MUST_TAIL_CALL.
	* gimple.h (enum gf_mask): Add GF_CALL_MUST_TAIL_CALL.
	(gimple_call_set_must_tail): New function.
	(gimple_call_must_tail_p): New function.
	* print-tree.c (print_node): Update printing of TREE_STATIC
	to reflect its use for CALL_EXPR_MUST_TAIL_CALL.
	* tree-core.h (struct tree_base): Add MUST_TAIL_CALL to the
	trailing comment listing applicable flags.
	* tree.h (CALL_EXPR_MUST_TAIL_CALL): New macro.

gcc/testsuite/ChangeLog:
	* gcc.dg/plugin/must-tail-call-1.c: New test case.
	* gcc.dg/plugin/must-tail-call-2.c: New test case.
	* gcc.dg/plugin/must_tail_call_plugin.c: New file.
	* gcc.dg/plugin/plugin.exp (plugin_test_list): Add the above.
---
 gcc/calls.c                                        | 123 ++++++++++++++++++---
 gcc/cfgexpand.c                                    |   1 +
 gcc/gimple-pretty-print.c                          |   2 +
 gcc/gimple.c                                       |   1 +
 gcc/gimple.h                                       |  20 ++++
 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     |  58 ++++++++++
 .../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                                         |   5 +
 12 files changed, 299 insertions(+), 17 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..1b12eca 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
+maybe_complain_about_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,13 @@ 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;
+		  maybe_complain_about_tail_call (exp,
+						  "a callee-copied argument is"
+						  " stored in the current "
+						  " function's frame");
+		}
 
 	      args[i].tree_value = build_fold_addr_expr_loc (loc,
 							 args[i].tree_value);
@@ -1406,6 +1425,9 @@ 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;
+	      maybe_complain_about_tail_call (exp,
+					      "argument must be passed"
+					      " by copying");
 	    }
 	}
 
@@ -2358,48 +2380,87 @@ can_implement_as_sibling_call_p (tree exp,
 				 const args_size &args_size)
 {
   if (!targetm.have_sibcall_epilogue ())
-    return false;
+    {
+      maybe_complain_about_tail_call
+	(exp,
+	 "machine description does not have"
+	 " a sibcall_epilogue instruction pattern");
+      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;
+    {
+      maybe_complain_about_tail_call (exp, "callee returns a structure");
+      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;
+    {
+      maybe_complain_about_tail_call (exp,
+				      "inconsistent size of stack space"
+				      " allocated for arguments which are"
+				      " passed in registers");
+      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;
+    {
+      maybe_complain_about_tail_call (exp,
+				      "target is not able to optimize the"
+				      " call into a sibling call");
+      return false;
+    }
 
   /* Functions that do not return exactly once may not be sibcall
      optimized.  */
-  if (flags & (ECF_RETURNS_TWICE | ECF_NORETURN))
-    return false;
+  if (flags & ECF_RETURNS_TWICE)
+    {
+      maybe_complain_about_tail_call (exp, "callee returns twice");
+      return false;
+    }
+  if (flags & ECF_NORETURN)
+    {
+      maybe_complain_about_tail_call (exp, "callee does not return");
+      return false;
+    }
 
   if (TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (addr))))
-    return false;
+    {
+      maybe_complain_about_tail_call (exp, "volatile function type");
+      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;
+    {
+      maybe_complain_about_tail_call (exp, "nested function");
+      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;
+    {
+      maybe_complain_about_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 +2468,19 @@ 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;
+    {
+      maybe_complain_about_tail_call (exp,
+				      "inconsistent number of"
+				      " popped arguments");
+      return false;
+    }
 
   if (!lang_hooks.decls.ok_for_sibcall (fndecl))
-    return false;
+    {
+      maybe_complain_about_tail_call (exp, "frontend does not support"
+					    " sibling call");
+      return false;
+    }
 
   /* All checks passed.  */
   return true;
@@ -2444,6 +2514,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 +2882,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 +2924,13 @@ 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;
+	  maybe_complain_about_tail_call (exp,
+					  "caller and callee disagree in"
+					  " promotion of function"
+					  " return value");
+	}
     }
 
   /* Ensure current function's preferred stack boundary is at least
@@ -3743,7 +3828,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.  */
+	maybe_complain_about_tail_call (exp, "tail call production failed");
+    }
 
   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..063e29d 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,25 @@ gimple_call_tail_p (gcall *s)
   return (s->subcode & GF_CALL_TAILCALL) != 0;
 }
 
+/* Mark (or clear) call statement S as requiring tail call optimization.  */
+
+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;
+}
+
+/* Return true if call statement has been marked as requiring
+   tail call optimization.  */
+
+static inline bool
+gimple_call_must_tail_p (const 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..c5504f8
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c
@@ -0,0 +1,58 @@
+/* Allow nested functions.  */
+/* { dg-options "-Wno-pedantic" } */
+
+struct box { char field[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: callee returns a structure" } */
+}
+
+int __attribute__((noinline,noclone))
+test_2_callee (int i, struct box b)
+{
+  if (b.field[0])
+    return 5;
+  return i * i;
+}
+
+int __attribute__((noinline,noclone))
+test_2_caller (int i)
+{
+  struct box b;
+  return test_2_callee (i + 1, b); /* { dg-error "cannot tail-call: callee required more stack slots than the caller" } */
+}
+
+extern void setjmp (void);
+void
+test_3 (void)
+{
+  setjmp (); /* { dg-error "cannot tail-call: callee returns twice" } */
+}
+
+void
+test_4 (void)
+{
+  void nested (void)
+  {
+  }
+  nested (); /* { dg-error "cannot tail-call: nested function" } */
+}
+
+typedef void (fn_ptr_t) (void);
+volatile fn_ptr_t fn_ptr;
+
+void
+test_5 (void)
+{
+  fn_ptr (); /* { dg-error "cannot tail-call: callee does not return" } */
+}
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..2510d16 100644
--- a/gcc/tree.h
+++ b/gcc/tree.h
@@ -661,6 +661,11 @@ extern void omp_clause_range_check_failed (const_tree, const char *, int,
 #define CALL_EXPR_TAILCALL(NODE) \
   (CALL_EXPR_CHECK (NODE)->base.addressable_flag)
 
+/* Set on a CALL_EXPR if the call has been marked as requiring tail call
+   optimization for correctness.  */
+#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