[v3,2/5] C++: Support clang compatible [[musttail]] (PR83324)

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.

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

On Tue, Jan 30, 2024 at 06:17:15PM -0800, Andi Kleen wrote:
> 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

FWIW, it's not clear to me we should do this.  I don't see a precedent.

> 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.
> 
> Passes bootstrap and full test

I don't see a ChangeLog entry.

> ---
>  gcc/cp/cp-tree.h    |  4 ++--
>  gcc/cp/parser.cc    | 28 +++++++++++++++++++++++-----
>  gcc/cp/semantics.cc |  6 +++---
>  gcc/cp/typeck.cc    | 20 ++++++++++++++++++--
>  4 files changed, 46 insertions(+), 12 deletions(-)
> 
> 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);
> +	      }

Doing lookup_attribute unconditionally twice seems like a lot.
You could do just lookup_attribute ("musttail", std_attrs) and then
check get_attribute_namespace() == nullptr/gnu_identifier?

It's not pretty that you have to remove_attribute but I guess we emit
warnings otherwise?

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

Two spaces after a '.'.

>  
>     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)
> +	{

This won't handle [[gnu::musttail]] return (1, foo ()); which I guess is fine
since clang++ doesn't accept that either, but musttail-invalid.c doesn't check
the case (and it's C only).

> +	  error_at (loc, "cannot tail-call: return value must be a call");
> +	  return error_mark_node;
> +	}
> +      else
> +	CALL_EXPR_MUST_TAIL_CALL (retval) = 1;
> +    }

IMHO nicer it would be to do

      tree t = retval;
      if (TREE_CODE (t) == TARGET_EXPR)
        t = TARGET_EXPR_INITIAL (t);
      if (TREE_CODE (t) == CALL_EXPR)
        CALL_EXPR_MUST_TAIL_CALL (t) = true;
      else
        {
          error_at (loc, "cannot tail-call: return value must be a call");
          return error_mark_node;
        }

so that you can set CALL_EXPR_MUST_TAIL_CALL in one place.

Marek

> > For compatibility it also detects clang::musttail
> 
> FWIW, it's not clear to me we should do this.  I don't see a precedent.

It would make existing code just work (as long as they don't use ifdef)

> 
> > 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.
> > 
> > Passes bootstrap and full test
> 
> I don't see a ChangeLog entry.

I have them, but will add them to the next post.
> >  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);
> > +	      }
> 
> Doing lookup_attribute unconditionally twice seems like a lot.
> You could do just lookup_attribute ("musttail", std_attrs) and then
> check get_attribute_namespace() == nullptr/gnu_identifier?

Actually the common case is 0 and very rarely 1 attribute, and in that it is both 
very cheap. If people ever write code with lots of attributes
per line we can worry about optimizations, but at this point it would
see premature.


> 
> It's not pretty that you have to remove_attribute but I guess we emit
> warnings otherwise?

Yes. 


-Andi

On Wed, Jan 31, 2024 at 12:21:38PM -0800, Andi Kleen wrote:
> > > +	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);
> > > +	      }

Using "" looks wrong to me, that is for standard attributes which
are also gnu attributes, say [[noreturn]]/[[gnu::noreturn]].
That is not the case here.  Even the __attribute__((musttail)) form will have
gnu namespace.

> > > +	    // support this for compatibility
> > > +	    if (lookup_attribute ("clang", "musttail", std_attrs))
> > > +	      {
> > > +		musttail_p = true;
> > > +		std_attrs = remove_attribute ("clang", "musttail", std_attrs);
> > > +	      }
> > 
> > Doing lookup_attribute unconditionally twice seems like a lot.
> > You could do just lookup_attribute ("musttail", std_attrs) and then
> > check get_attribute_namespace() == nullptr/gnu_identifier?

I agree with Marek here.  The fact that it is most often NULL std_attrs is
indeed already optimized by lookup_attribute, but people write all kinds of
code.  The remove_attribute can be done separately of course.

Though, I'd also prefer not to add clang attributes, just add gnu ones.

	Jakub

On Wed, 31 Jan 2024, Jakub Jelinek wrote:

> On Wed, Jan 31, 2024 at 12:21:38PM -0800, Andi Kleen wrote:
> > > > +	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);
> > > > +	      }
> 
> Using "" looks wrong to me, that is for standard attributes which
> are also gnu attributes, say [[noreturn]]/[[gnu::noreturn]].
> That is not the case here.  Even the __attribute__((musttail)) form will have
> gnu namespace.

And it's incorrect to use [[musttail]] (C23 syntax, no namespace) in any 
circumstances, at least for C, as it's not a standard attribute - so tests 
should verify that [[musttail]] is diagnosed as ignored even in contexts 
where [[gnu::musttail]] is valid.  (It can't be standardized as 
[[musttail]] because of the rule that standard attributes must be 
ignorable; the proposed syntax for a TS and possible future 
standardization after that is "return goto".)