[v1,2/4] C++: Support clang compatible [[musttail]]

This patch implements a clang compatible [[musttail]] attribute for
returns.

musttail is useful as an alternative to computed goto for interpreters.
With computed goto the interpreter function usually ends up very big
which causes problems with register allocation and other per function
optimizations not scaling. With musttail the interpreter can be instead
written as a sequence of smaller functions that call each other. To
avoid unbounded stack growth this requires forcing a sibling call, which
this attribute does. It guarantees an error if the call cannot be tail
called which allows the programmer to fix it instead of risking a stack
overflow. Unlike computed goto it is also type-safe.

It turns out that David Malcolm had already implemented middle/backend
support for a musttail attribute back in 2016, but it wasn't exposed
to any frontend other than a special plugin.

This patch adds a [[gnu::musttail]] attribute for C++ that can be added
to return statements. The return statement must be a direct call
(it does not follow dependencies), which is similar to what clang
implements. It then uses the existing must tail infrastructure.

For compatibility it also detects clang::musttail

One problem is that tree-tailcall usually fails when optimization
is disabled, which implies the attribute only really works with
optimization on. But that seems to be a reasonable limitation.

The attribute is only supported for C++, since the C-parser
has no support for statement attributes for non empty statements.
It could be added there with __attribute__ too but would need
some minor grammar adjustments.

Passes bootstrap and full test
---
 gcc/c-family/c-attribs.cc | 25 +++++++++++++++++++++++++
 gcc/cp/cp-tree.h          |  4 ++--
 gcc/cp/parser.cc          | 28 +++++++++++++++++++++++-----
 gcc/cp/semantics.cc       |  6 +++---
 gcc/cp/typeck.cc          | 20 ++++++++++++++++++--
 5 files changed, 71 insertions(+), 12 deletions(-)

Andi Kleen <ak@linux.intel.com> writes:

> This patch implements a clang compatible [[musttail]] attribute for
> returns.

This is PR83324. See also PR52067 and PR110899.

>
> musttail is useful as an alternative to computed goto for interpreters.
> With computed goto the interpreter function usually ends up very big
> which causes problems with register allocation and other per function
> optimizations not scaling. With musttail the interpreter can be instead
> written as a sequence of smaller functions that call each other. To
> avoid unbounded stack growth this requires forcing a sibling call, which
> this attribute does. It guarantees an error if the call cannot be tail
> called which allows the programmer to fix it instead of risking a stack
> overflow. Unlike computed goto it is also type-safe.
>

Yeah, CPython is going to require this for its new JIT.

> The attribute is only supported for C++, since the C-parser
> has no support for statement attributes for non empty statements.
> It could be added there with __attribute__ too but would need
> some minor grammar adjustments.

... although it'll need C there.

Thanks for doing this.  I'm not qualified to review the patch properly,
but was just curious...

Andi Kleen <ak@linux.intel.com> writes:
> This patch implements a clang compatible [[musttail]] attribute for
> returns.
>
> musttail is useful as an alternative to computed goto for interpreters.
> With computed goto the interpreter function usually ends up very big
> which causes problems with register allocation and other per function
> optimizations not scaling. With musttail the interpreter can be instead
> written as a sequence of smaller functions that call each other. To
> avoid unbounded stack growth this requires forcing a sibling call, which
> this attribute does. It guarantees an error if the call cannot be tail
> called which allows the programmer to fix it instead of risking a stack
> overflow. Unlike computed goto it is also type-safe.
>
> It turns out that David Malcolm had already implemented middle/backend
> support for a musttail attribute back in 2016, but it wasn't exposed
> to any frontend other than a special plugin.
>
> This patch adds a [[gnu::musttail]] attribute for C++ that can be added
> to return statements. The return statement must be a direct call
> (it does not follow dependencies), which is similar to what clang
> implements. It then uses the existing must tail infrastructure.
>
> For compatibility it also detects clang::musttail
>
> One problem is that tree-tailcall usually fails when optimization
> is disabled, which implies the attribute only really works with
> optimization on. But that seems to be a reasonable limitation.
>
> The attribute is only supported for C++, since the C-parser
> has no support for statement attributes for non empty statements.
> It could be added there with __attribute__ too but would need
> some minor grammar adjustments.
>
> Passes bootstrap and full test
> ---
>  gcc/c-family/c-attribs.cc | 25 +++++++++++++++++++++++++
>  gcc/cp/cp-tree.h          |  4 ++--
>  gcc/cp/parser.cc          | 28 +++++++++++++++++++++++-----
>  gcc/cp/semantics.cc       |  6 +++---
>  gcc/cp/typeck.cc          | 20 ++++++++++++++++++--
>  5 files changed, 71 insertions(+), 12 deletions(-)
>
> diff --git a/gcc/c-family/c-attribs.cc b/gcc/c-family/c-attribs.cc
> index 40a0cf90295d..f31c62e76665 100644
> --- a/gcc/c-family/c-attribs.cc
> +++ b/gcc/c-family/c-attribs.cc
> @@ -54,6 +54,7 @@ static tree handle_nocommon_attribute (tree *, tree, tree, int, bool *);
>  static tree handle_common_attribute (tree *, tree, tree, int, bool *);
>  static tree handle_hot_attribute (tree *, tree, tree, int, bool *);
>  static tree handle_cold_attribute (tree *, tree, tree, int, bool *);
> +static tree handle_musttail_attribute (tree *, tree, tree, int, bool *);
>  static tree handle_no_sanitize_attribute (tree *, tree, tree, int, bool *);
>  static tree handle_no_sanitize_address_attribute (tree *, tree, tree,
>  						  int, bool *);
> @@ -499,6 +500,8 @@ const struct attribute_spec c_common_gnu_attributes[] =
>    { "hot",		      0, 0, false,  false, false, false,
>  			      handle_hot_attribute,
>  	                      attr_cold_hot_exclusions },
> +  { "musttail",		      0, 0, false,  false, false, false,
> +			      handle_musttail_attribute, NULL },
>    { "no_address_safety_analysis",
>  			      0, 0, true, false, false, false,
>  			      handle_no_address_safety_analysis_attribute,
> @@ -1290,6 +1293,28 @@ handle_hot_attribute (tree *node, tree name, tree ARG_UNUSED (args),
>    return NULL_TREE;
>  }
>  
> +/* Handle a "musttail" and attribute; arguments as in
> +   struct attribute_spec.handler.  */
> +
> +static tree
> +handle_musttail_attribute (tree *node, tree name, tree ARG_UNUSED (args),
> +		       int ARG_UNUSED (flags), bool *no_add_attrs)
> +{
> +  if (TREE_CODE (*node) == FUNCTION_DECL
> +      || TREE_CODE (*node) == LABEL_DECL)
> +    {
> +      /* Attribute musttail processing is done later with lookup_attribute.  */
> +    }
> +  else
> +    {
> +      warning (OPT_Wattributes, "%qE attribute ignored", name);
> +      *no_add_attrs = true;
> +    }
> +
> +  return NULL_TREE;
> +}
> +
> +

...are the three hunks above needed?  The reason for asking is that,
if they were needed, I'd have expected that we'd also need a table
entry for clang::musttail (which is possible to add).  But trying it
locally, the patch seemed to work without this.

Also, including the table entry and accepting FUNCTION_DECL means that:

[[gnu::musttail]] void f();
[[gnu::musttail]] void g() { return f(); }

is silently accepted but seems to have no effect.

Thanks,
Richard


>  /* Handle a "cold" and attribute; arguments as in
>     struct attribute_spec.handler.  */
>  
> diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
> index 60e6dafc5494..bed52e860a00 100644
> --- a/gcc/cp/cp-tree.h
> +++ b/gcc/cp/cp-tree.h
> @@ -7763,7 +7763,7 @@ extern void finish_while_stmt			(tree);
>  extern tree begin_do_stmt			(void);
>  extern void finish_do_body			(tree);
>  extern void finish_do_stmt		(tree, tree, bool, tree, bool);
> -extern tree finish_return_stmt			(tree);
> +extern tree finish_return_stmt			(tree, bool = false);
>  extern tree begin_for_scope			(tree *);
>  extern tree begin_for_stmt			(tree, tree);
>  extern void finish_init_stmt			(tree);
> @@ -8275,7 +8275,7 @@ extern tree composite_pointer_type		(const op_location_t &,
>  						 tsubst_flags_t);
>  extern tree merge_types				(tree, tree);
>  extern tree strip_array_domain			(tree);
> -extern tree check_return_expr			(tree, bool *, bool *);
> +extern tree check_return_expr			(tree, bool *, bool *, bool);
>  extern tree spaceship_type			(tree, tsubst_flags_t = tf_warning_or_error);
>  extern tree genericize_spaceship		(location_t, tree, tree, tree);
>  extern tree cp_build_binary_op                  (const op_location_t &,
> diff --git a/gcc/cp/parser.cc b/gcc/cp/parser.cc
> index 3748ccd49ff3..5a32804c0201 100644
> --- a/gcc/cp/parser.cc
> +++ b/gcc/cp/parser.cc
> @@ -2462,7 +2462,7 @@ static tree cp_parser_perform_range_for_lookup
>  static tree cp_parser_range_for_member_function
>    (tree, tree);
>  static tree cp_parser_jump_statement
> -  (cp_parser *);
> +  (cp_parser *, bool = false);
>  static void cp_parser_declaration_statement
>    (cp_parser *);
>  
> @@ -12719,9 +12719,27 @@ cp_parser_statement (cp_parser* parser, tree in_statement_expr,
>  						     NULL_TREE, false);
>  	  break;
>  
> +	case RID_RETURN:
> +	  {
> +	    bool musttail_p = false;
> +	    std_attrs = process_stmt_hotness_attribute (std_attrs, attrs_loc);
> +	    if (lookup_attribute ("", "musttail", std_attrs))
> +	      {
> +		musttail_p = true;
> +		std_attrs = remove_attribute ("", "musttail", std_attrs);
> +	      }
> +	    // support this for compatibility
> +	    if (lookup_attribute ("clang", "musttail", std_attrs))
> +	      {
> +		musttail_p = true;
> +		std_attrs = remove_attribute ("clang", "musttail", std_attrs);
> +	      }
> +	    statement = cp_parser_jump_statement (parser, musttail_p);
> +	  }
> +	  break;
> +
>  	case RID_BREAK:
>  	case RID_CONTINUE:
> -	case RID_RETURN:
>  	case RID_CO_RETURN:
>  	case RID_GOTO:
>  	  std_attrs = process_stmt_hotness_attribute (std_attrs, attrs_loc);
> @@ -14767,7 +14785,7 @@ cp_parser_init_statement (cp_parser *parser, tree *decl)
>    return false;
>  }
>  
> -/* Parse a jump-statement.
> +/* Parse a jump-statement. MUSTTAIL_P indicates a musttail attribute.
>  
>     jump-statement:
>       break ;
> @@ -14785,7 +14803,7 @@ cp_parser_init_statement (cp_parser *parser, tree *decl)
>     Returns the new BREAK_STMT, CONTINUE_STMT, RETURN_EXPR, or GOTO_EXPR.  */
>  
>  static tree
> -cp_parser_jump_statement (cp_parser* parser)
> +cp_parser_jump_statement (cp_parser* parser, bool musttail_p)
>  {
>    tree statement = error_mark_node;
>    cp_token *token;
> @@ -14869,7 +14887,7 @@ cp_parser_jump_statement (cp_parser* parser)
>  	else if (FNDECL_USED_AUTO (current_function_decl) && in_discarded_stmt)
>  	  /* Don't deduce from a discarded return statement.  */;
>  	else
> -	  statement = finish_return_stmt (expr);
> +	  statement = finish_return_stmt (expr, musttail_p);
>  	/* Look for the final `;'.  */
>  	cp_parser_require (parser, CPP_SEMICOLON, RT_SEMICOLON);
>        }
> diff --git a/gcc/cp/semantics.cc b/gcc/cp/semantics.cc
> index 3299e2704465..a277f70ea0fd 100644
> --- a/gcc/cp/semantics.cc
> +++ b/gcc/cp/semantics.cc
> @@ -1324,16 +1324,16 @@ finish_do_stmt (tree cond, tree do_stmt, bool ivdep, tree unroll,
>  }
>  
>  /* Finish a return-statement.  The EXPRESSION returned, if any, is as
> -   indicated.  */
> +   indicated.  MUSTTAIL_P indicates a mustcall attribute.  */
>  
>  tree
> -finish_return_stmt (tree expr)
> +finish_return_stmt (tree expr, bool musttail_p)
>  {
>    tree r;
>    bool no_warning;
>    bool dangling;
>  
> -  expr = check_return_expr (expr, &no_warning, &dangling);
> +  expr = check_return_expr (expr, &no_warning, &dangling, musttail_p);
>  
>    if (error_operand_p (expr)
>        || (flag_openmp && !check_omp_return ()))
> diff --git a/gcc/cp/typeck.cc b/gcc/cp/typeck.cc
> index a15eda3f5f8c..8c116e3b4f4c 100644
> --- a/gcc/cp/typeck.cc
> +++ b/gcc/cp/typeck.cc
> @@ -11028,10 +11028,12 @@ maybe_warn_pessimizing_move (tree expr, tree type, bool return_p)
>     the DECL_RESULT for the function.  Set *NO_WARNING to true if
>     code reaches end of non-void function warning shouldn't be issued
>     on this RETURN_EXPR.  Set *DANGLING to true if code returns the
> -   address of a local variable.  */
> +   address of a local variable.  MUSTTAIL_P indicates a musttail
> +   return.  */
>  
>  tree
> -check_return_expr (tree retval, bool *no_warning, bool *dangling)
> +check_return_expr (tree retval, bool *no_warning, bool *dangling,
> +		   bool musttail_p)
>  {
>    tree result;
>    /* The type actually returned by the function.  */
> @@ -11045,6 +11047,20 @@ check_return_expr (tree retval, bool *no_warning, bool *dangling)
>    *no_warning = false;
>    *dangling = false;
>  
> +  if (musttail_p)
> +    {
> +      if (TREE_CODE (retval) == TARGET_EXPR
> +	  && TREE_CODE (TARGET_EXPR_INITIAL (retval)) == CALL_EXPR)
> +	CALL_EXPR_MUST_TAIL_CALL (TARGET_EXPR_INITIAL (retval)) = 1;
> +      else if (TREE_CODE (retval) != CALL_EXPR)
> +	{
> +	  error_at (loc, "cannot tail-call: return value must be a call");
> +	  return error_mark_node;
> +	}
> +      else
> +	CALL_EXPR_MUST_TAIL_CALL (retval) = 1;
> +    }
> +
>    /* A `volatile' function is one that isn't supposed to return, ever.
>       (This is a G++ extension, used to get better code for functions
>       that call the `volatile' function.)  */

> ...are the three hunks above needed?  The reason for asking is that,
> if they were needed, I'd have expected that we'd also need a table
> entry for clang::musttail (which is possible to add).  But trying it
> locally, the patch seemed to work without this.

Interesting thanks. I think I copied this from likely/unlikely,

But I suppose it would be needed for the later C implementation,
unless we want this to only work with the C23 attribute syntax.
But I'll drop it for now. Perhaps it should be dropped for likely/unlikely too.


> Also, including the table entry and accepting FUNCTION_DECL means that:
> 
> [[gnu::musttail]] void f();
> [[gnu::musttail]] void g() { return f(); }
> 
> is silently accepted but seems to have no effect.

Yes that is indeed not intended.


-Andi

On Wed, Jan 24, 2024 at 11:13:44AM +0000, Sam James wrote:
> 
> Andi Kleen <ak@linux.intel.com> writes:
> 
> > This patch implements a clang compatible [[musttail]] attribute for
> > returns.
> 
> This is PR83324. See also PR52067 and PR110899.

Thanks for the references. I'll add it there.
> 
> > The attribute is only supported for C++, since the C-parser
> > has no support for statement attributes for non empty statements.
> > It could be added there with __attribute__ too but would need
> > some minor grammar adjustments.
> 
> ... although it'll need C there.

Okay I will look into it (although I suppose that file could be also
built as C++)

-Andi