[v5,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

	PR83324

gcc/cp/ChangeLog:

	* cp-tree.h (finish_return_stmt): Add musttail_p.
	(check_return_expr): Dito.
	* parser.cc (cp_parser_statement): Handle [[musttail]].
	(cp_parser_std_attribute): Dito.
	(cp_parser_init_statement): Dito.
	(cp_parser_jump_statement): Dito.
	* semantics.cc (finish_return_stmt): Dito.
	* typeck.cc (check_return_expr): Handle musttail_p flag.
---
 gcc/cp/cp-tree.h    |  4 ++--
 gcc/cp/parser.cc    | 30 ++++++++++++++++++++++++------
 gcc/cp/semantics.cc |  6 +++---
 gcc/cp/typeck.cc    | 20 ++++++++++++++++++--
 4 files changed, 47 insertions(+), 13 deletions(-)

On 5/5/24 14:14, Andi Kleen wrote:
> This patch implements a clang compatible [[musttail]] attribute for
> returns.

Thanks.

> 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
> 
> 	PR83324
> 
> gcc/cp/ChangeLog:
> 
> 	* cp-tree.h (finish_return_stmt): Add musttail_p.
> 	(check_return_expr): Dito.
> 	* parser.cc (cp_parser_statement): Handle [[musttail]].
> 	(cp_parser_std_attribute): Dito.
> 	(cp_parser_init_statement): Dito.
> 	(cp_parser_jump_statement): Dito.
> 	* semantics.cc (finish_return_stmt): Dito.
> 	* typeck.cc (check_return_expr): Handle musttail_p flag.
> ---
>   gcc/cp/cp-tree.h    |  4 ++--
>   gcc/cp/parser.cc    | 30 ++++++++++++++++++++++++------
>   gcc/cp/semantics.cc |  6 +++---
>   gcc/cp/typeck.cc    | 20 ++++++++++++++++++--
>   4 files changed, 47 insertions(+), 13 deletions(-)
> 
> @@ -12734,9 +12734,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 ("gnu", "musttail", std_attrs))
> +	      {
> +		musttail_p = true;
> +		std_attrs = remove_attribute ("gnu", "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);

It seems to me that if we were to pass &std_attrs to 
cp_parser_jump_statement, we could handle this entirely in that function 
rather than adding a flag to finish_return_stmt and check_return_stmt.

> @@ -30189,7 +30207,7 @@ cp_parser_std_attribute (cp_parser *parser, tree attr_ns)
>       /* Maybe we don't expect to see any arguments for this attribute.  */
>       const attribute_spec *as
>         = lookup_attribute_spec (TREE_PURPOSE (attribute));
> -    if (as && as->max_length == 0)
> +    if ((as && as->max_length == 0) || is_attribute_p ("musttail", attr_id))

I'd prefer to add an attribute to the table, rather than special-case it 
here; apart from consistency, it seems likely that someone will later 
want to apply it to a function.

You need a template testcase; I expect it doesn't work in templates with 
the current patch.  It's probably enough to copy it in tsubst_expr where 
we currently propagate CALL_EXPR_OPERATOR_SYNTAX.

You also need a testcase where the function returns a class; in that 
case the call will often appear as AGGR_INIT_EXPR rather than CALL_EXPR, 
so you'll need to handle that as well.  And see the places that copy 
flags like CALL_EXPR_OPERATOR_SYNTAX between CALL_EXPR and AGGR_INIT_EXPR.

Jason

Hi Jason,

On Mon, May 06, 2024 at 11:02:20PM -0400, Jason Merrill wrote:
> > @@ -30189,7 +30207,7 @@ cp_parser_std_attribute (cp_parser *parser, tree attr_ns)
> >       /* Maybe we don't expect to see any arguments for this attribute.  */
> >       const attribute_spec *as
> >         = lookup_attribute_spec (TREE_PURPOSE (attribute));
> > -    if (as && as->max_length == 0)
> > +    if ((as && as->max_length == 0) || is_attribute_p ("musttail", attr_id))
> 
> I'd prefer to add an attribute to the table, rather than special-case it
> here; apart from consistency, it seems likely that someone will later want
> to apply it to a function.

Just to clarify. I can add it to the table, but it would be a nop there
for now because the table is not used for statement attributes by
the current parser.

> 
> You need a template testcase; I expect it doesn't work in templates with the
> current patch.  It's probably enough to copy it in tsubst_expr where we
> currently propagate CALL_EXPR_OPERATOR_SYNTAX.

I tried it with the appended test case, everything seems to work without
changes.

Does it cover the cases you were concerned about?


> 
> You also need a testcase where the function returns a class; in that case
> the call will often appear as AGGR_INIT_EXPR rather than CALL_EXPR, so
> you'll need to handle that as well.  And see the places that copy flags like
> CALL_EXPR_OPERATOR_SYNTAX between CALL_EXPR and AGGR_INIT_EXPR.

Dito.

-Andi


/* { dg-do compile { target { tail_call } } } */
/* { dg-options "-O2" } */
/* { dg-additional-options "-fdelayed-branch" { target sparc*-*-* } } */

class Foo {
public:
  int a, b;
  Foo(int a, int b) : a(a), b(b) {}
};

Foo __attribute__((noinline,noclone,noipa))
callee (int i)
{
  return Foo(i, i+1);
}

Foo __attribute__((noinline,noclone,noipa))
caller (int i)
{
  [[gnu::musttail]] return callee (i + 1);
}

template<typename T>
T __attribute__((noinline,noclone,noipa)) foo (T i)
{
  return i + 1;
}

int
caller2 (int k)
{
  [[gnu::musttail]] return foo<int>(1);
}

template<typename T>
T caller3 (T v)
{
  [[gnu::musttail]] return foo<T>(v);
}

int call3(int i)
{
  [[gnu::musttail]] return caller3<int>(i + 1);
}

class Bar {
  int a;
public:
  Bar(int a) : a(a) {}
  Bar operator+(Bar o) { return Bar(a + o.a); } 
};

Bar
caller3 (Bar k)
{
  [[gnu::musttail]] return caller3<Bar>(Bar(99));
}

On 5/14/24 13:24, Andi Kleen wrote:
> Hi Jason,
> 
> On Mon, May 06, 2024 at 11:02:20PM -0400, Jason Merrill wrote:
>>> @@ -30189,7 +30207,7 @@ cp_parser_std_attribute (cp_parser *parser, tree attr_ns)
>>>        /* Maybe we don't expect to see any arguments for this attribute.  */
>>>        const attribute_spec *as
>>>          = lookup_attribute_spec (TREE_PURPOSE (attribute));
>>> -    if (as && as->max_length == 0)
>>> +    if ((as && as->max_length == 0) || is_attribute_p ("musttail", attr_id))
>>
>> I'd prefer to add an attribute to the table, rather than special-case it
>> here; apart from consistency, it seems likely that someone will later want
>> to apply it to a function.
> 
> Just to clarify. I can add it to the table, but it would be a nop there
> for now because the table is not used for statement attributes by
> the current parser.

Agreed.

>> You need a template testcase; I expect it doesn't work in templates with the
>> current patch.  It's probably enough to copy it in tsubst_expr where we
>> currently propagate CALL_EXPR_OPERATOR_SYNTAX.
> 
> I tried it with the appended test case, everything seems to work without
> changes.
> 
> Does it cover the cases you were concerned about?

Not fully; this testcase doesn't seem to check for errors if tail-call 
fails, only whether the syntax is accepted.  So it would pass if the 
attribute were simply ignored.

Did you also see this comment?

> It seems to me that if we were to pass &std_attrs to cp_parser_jump_statement, we could handle this entirely in that function rather than adding a flag to finish_return_stmt and check_return_stmt. 

Jason

> > > You need a template testcase; I expect it doesn't work in templates with the
> > > current patch.  It's probably enough to copy it in tsubst_expr where we
> > > currently propagate CALL_EXPR_OPERATOR_SYNTAX.
> > 
> > I tried it with the appended test case, everything seems to work without
> > changes.
> > 
> > Does it cover the cases you were concerned about?
> 
> Not fully; this testcase doesn't seem to check for errors if tail-call
> fails, only whether the syntax is accepted.  So it would pass if the
> attribute were simply ignored.

Okay I'm not clear how I would do that. Pattern match the assembler 
in a target specific test case? From looking at the assembler output
everything got tail converted.

> 
> Did you also see this comment?
> 
> > It seems to me that if we were to pass &std_attrs to
> > cp_parser_jump_statement, we could handle this entirely in that function
> > rather than adding a flag to finish_return_stmt and check_return_stmt.

Yes. I did that change.

-Andi

On 5/14/24 19:23, Andi Kleen wrote:
>>>> You need a template testcase; I expect it doesn't work in templates with the
>>>> current patch.  It's probably enough to copy it in tsubst_expr where we
>>>> currently propagate CALL_EXPR_OPERATOR_SYNTAX.
>>>
>>> I tried it with the appended test case, everything seems to work without
>>> changes.
>>>
>>> Does it cover the cases you were concerned about?
>>
>> Not fully; this testcase doesn't seem to check for errors if tail-call
>> fails, only whether the syntax is accepted.  So it would pass if the
>> attribute were simply ignored.
> 
> Okay I'm not clear how I would do that. Pattern match the assembler
> in a target specific test case? From looking at the assembler output
> everything got tail converted.

Write a testcase where the tail-call optimization can't happen, perhaps 
because the caller and callee disagree on return type:

int f();

double h() { [[gnu::musttail]] return f(); } // error

template <class T>
T g() { [[gnu::musttail]] return f(); }

int main()
{
   g<int>();
   g<double>(); // should error, but doesn't with v6 patch set
}

Jason