[v2] c++: Fix compile-time-hog in cp_fold_immediate_r [PR111660]

  On Thu, Oct 12, 2023 at 09:41:43PM -0400, Jason Merrill wrote:
> On 10/12/23 17:04, Marek Polacek wrote:
> > Bootstrapped/regtested on x86_64-pc-linux-gnu, ok for trunk?
> > 
> > -- >8 --
> > My recent patch introducing cp_fold_immediate_r caused exponential
> > compile time with nested COND_EXPRs.  The problem is that the COND_EXPR
> > case recursively walks the arms of a COND_EXPR, but after processing
> > both arms it doesn't end the walk; it proceeds to walk the
> > sub-expressions of the outermost COND_EXPR, triggering again walking
> > the arms of the nested COND_EXPR, and so on.  This patch brings the
> > compile time down to about 0m0.033s.
> > 
> > I've added some debug prints to make sure that the rest of cp_fold_r
> > is still performed as before.
> > 
> >          PR c++/111660
> > 
> > gcc/cp/ChangeLog:
> > 
> >          * cp-gimplify.cc (cp_fold_immediate_r) <case COND_EXPR>: Return
> >          integer_zero_node instead of break;.
> >          (cp_fold_immediate): Return true if cp_fold_immediate_r returned
> >          error_mark_node.
> > 
> > gcc/testsuite/ChangeLog:
> > 
> >          * g++.dg/cpp0x/hog1.C: New test.
> > ---
> >   gcc/cp/cp-gimplify.cc             |  9 ++--
> >   gcc/testsuite/g++.dg/cpp0x/hog1.C | 77 +++++++++++++++++++++++++++++++
> >   2 files changed, 82 insertions(+), 4 deletions(-)
> >   create mode 100644 gcc/testsuite/g++.dg/cpp0x/hog1.C
> > 
> > diff --git a/gcc/cp/cp-gimplify.cc b/gcc/cp/cp-gimplify.cc
> > index bdf6e5f98ff..ca622ca169a 100644
> > --- a/gcc/cp/cp-gimplify.cc
> > +++ b/gcc/cp/cp-gimplify.cc
> > @@ -1063,16 +1063,16 @@ cp_fold_immediate_r (tree *stmt_p, int *walk_subtrees, void *data_)
> >   	break;
> >         if (TREE_OPERAND (stmt, 1)
> >   	  && cp_walk_tree (&TREE_OPERAND (stmt, 1), cp_fold_immediate_r, data,
> > -			   nullptr))
> > +			   nullptr) == error_mark_node)
> >   	return error_mark_node;
> >         if (TREE_OPERAND (stmt, 2)
> >   	  && cp_walk_tree (&TREE_OPERAND (stmt, 2), cp_fold_immediate_r, data,
> > -			   nullptr))
> > +			   nullptr) == error_mark_node)
> >   	return error_mark_node;
> >         /* We're done here.  Don't clear *walk_subtrees here though: we're called
> >   	 from cp_fold_r and we must let it recurse on the expression with
> >   	 cp_fold.  */
> > -      break;
> > +      return integer_zero_node;
> 
> I'm concerned this will end up missing something like
> 
> 1 ? 1 : ((1 ? 1 : 1), immediate())
> 
> as the integer_zero_node from the inner ?: will prevent walk_tree from
> looking any farther.

You are right.  The line above works as expected, but

  1 ? 1 : ((1 ? 1 : id (42)), id (i));

shows the problem (when the expression isn't used as an initializer).

> Maybe we want to handle COND_EXPR in cp_fold_r instead of here?

I hope this version is better.

Bootstrapped/regtested on x86_64-pc-linux-gnu, ok for trunk?

-- >8 --
My recent patch introducing cp_fold_immediate_r caused exponential
compile time with nested COND_EXPRs.  The problem is that the COND_EXPR
case recursively walks the arms of a COND_EXPR, but after processing
both arms it doesn't end the walk; it proceeds to walk the
sub-expressions of the outermost COND_EXPR, triggering again walking
the arms of the nested COND_EXPR, and so on.  This patch brings the
compile time down to about 0m0.033s.

The ff_fold_immediate flag is unused after this patch but since I'm
using it in the P2564 patch, I'm not removing it now.

        PR c++/111660

gcc/cp/ChangeLog:

        * cp-gimplify.cc (cp_fold_immediate_r) <case COND_EXPR>: Don't
	handle it here.
        (cp_fold_r): Handle COND_EXPR here.

gcc/testsuite/ChangeLog:

        * g++.dg/cpp0x/hog1.C: New test.
	* g++.dg/cpp2a/consteval36.C: New test.
---
 gcc/cp/cp-gimplify.cc                    | 38 +++++-------
 gcc/testsuite/g++.dg/cpp0x/hog1.C        | 77 ++++++++++++++++++++++++
 gcc/testsuite/g++.dg/cpp2a/consteval36.C | 18 ++++++
 3 files changed, 111 insertions(+), 22 deletions(-)
 create mode 100644 gcc/testsuite/g++.dg/cpp0x/hog1.C
 create mode 100644 gcc/testsuite/g++.dg/cpp2a/consteval36.C


base-commit: 8be20f3b0bded7f9b690b27cbee58b283dbe827b
  

On 10/13/23 14:53, Marek Polacek wrote:
> On Thu, Oct 12, 2023 at 09:41:43PM -0400, Jason Merrill wrote:
>> On 10/12/23 17:04, Marek Polacek wrote:
>>> Bootstrapped/regtested on x86_64-pc-linux-gnu, ok for trunk?
>>>
>>> -- >8 --
>>> My recent patch introducing cp_fold_immediate_r caused exponential
>>> compile time with nested COND_EXPRs.  The problem is that the COND_EXPR
>>> case recursively walks the arms of a COND_EXPR, but after processing
>>> both arms it doesn't end the walk; it proceeds to walk the
>>> sub-expressions of the outermost COND_EXPR, triggering again walking
>>> the arms of the nested COND_EXPR, and so on.  This patch brings the
>>> compile time down to about 0m0.033s.
>>>
>>> I've added some debug prints to make sure that the rest of cp_fold_r
>>> is still performed as before.
>>>
>>>           PR c++/111660
>>>
>>> gcc/cp/ChangeLog:
>>>
>>>           * cp-gimplify.cc (cp_fold_immediate_r) <case COND_EXPR>: Return
>>>           integer_zero_node instead of break;.
>>>           (cp_fold_immediate): Return true if cp_fold_immediate_r returned
>>>           error_mark_node.
>>>
>>> gcc/testsuite/ChangeLog:
>>>
>>>           * g++.dg/cpp0x/hog1.C: New test.
>>> ---
>>>    gcc/cp/cp-gimplify.cc             |  9 ++--
>>>    gcc/testsuite/g++.dg/cpp0x/hog1.C | 77 +++++++++++++++++++++++++++++++
>>>    2 files changed, 82 insertions(+), 4 deletions(-)
>>>    create mode 100644 gcc/testsuite/g++.dg/cpp0x/hog1.C
>>>
>>> diff --git a/gcc/cp/cp-gimplify.cc b/gcc/cp/cp-gimplify.cc
>>> index bdf6e5f98ff..ca622ca169a 100644
>>> --- a/gcc/cp/cp-gimplify.cc
>>> +++ b/gcc/cp/cp-gimplify.cc
>>> @@ -1063,16 +1063,16 @@ cp_fold_immediate_r (tree *stmt_p, int *walk_subtrees, void *data_)
>>>    	break;
>>>          if (TREE_OPERAND (stmt, 1)
>>>    	  && cp_walk_tree (&TREE_OPERAND (stmt, 1), cp_fold_immediate_r, data,
>>> -			   nullptr))
>>> +			   nullptr) == error_mark_node)
>>>    	return error_mark_node;
>>>          if (TREE_OPERAND (stmt, 2)
>>>    	  && cp_walk_tree (&TREE_OPERAND (stmt, 2), cp_fold_immediate_r, data,
>>> -			   nullptr))
>>> +			   nullptr) == error_mark_node)
>>>    	return error_mark_node;
>>>          /* We're done here.  Don't clear *walk_subtrees here though: we're called
>>>    	 from cp_fold_r and we must let it recurse on the expression with
>>>    	 cp_fold.  */
>>> -      break;
>>> +      return integer_zero_node;
>>
>> I'm concerned this will end up missing something like
>>
>> 1 ? 1 : ((1 ? 1 : 1), immediate())
>>
>> as the integer_zero_node from the inner ?: will prevent walk_tree from
>> looking any farther.
> 
> You are right.  The line above works as expected, but
> 
>    1 ? 1 : ((1 ? 1 : id (42)), id (i));
> 
> shows the problem (when the expression isn't used as an initializer).
> 
>> Maybe we want to handle COND_EXPR in cp_fold_r instead of here?
> 
> I hope this version is better.
> 
> Bootstrapped/regtested on x86_64-pc-linux-gnu, ok for trunk?
> 
> -- >8 --
> My recent patch introducing cp_fold_immediate_r caused exponential
> compile time with nested COND_EXPRs.  The problem is that the COND_EXPR
> case recursively walks the arms of a COND_EXPR, but after processing
> both arms it doesn't end the walk; it proceeds to walk the
> sub-expressions of the outermost COND_EXPR, triggering again walking
> the arms of the nested COND_EXPR, and so on.  This patch brings the
> compile time down to about 0m0.033s.

Is this number still accurate for this version?

This change seems algorithmically better than the current code, but 
still problematic: if we have nested COND_EXPR A/B/C/D/E, it looks like 
we will end up cp_fold_immediate_r walking the arms of E five times, 
once for each COND_EXPR.

What I was thinking by handling COND_EXPR in cp_fold_r was to cp_fold_r 
walk its subtrees (or cp_fold_immediate_r if it's clear from op0 that 
the branch isn't taken) so we can clear *walk_subtrees and we don't 
fold_imm walk a node more than once.

> The ff_fold_immediate flag is unused after this patch but since I'm
> using it in the P2564 patch, I'm not removing it now.
> 
>          PR c++/111660
> 
> gcc/cp/ChangeLog:
> 
>          * cp-gimplify.cc (cp_fold_immediate_r) <case COND_EXPR>: Don't
> 	handle it here.
>          (cp_fold_r): Handle COND_EXPR here.
> 
> gcc/testsuite/ChangeLog:
> 
>          * g++.dg/cpp0x/hog1.C: New test.
> 	* g++.dg/cpp2a/consteval36.C: New test.
> ---
>   gcc/cp/cp-gimplify.cc                    | 38 +++++-------
>   gcc/testsuite/g++.dg/cpp0x/hog1.C        | 77 ++++++++++++++++++++++++
>   gcc/testsuite/g++.dg/cpp2a/consteval36.C | 18 ++++++
>   3 files changed, 111 insertions(+), 22 deletions(-)
>   create mode 100644 gcc/testsuite/g++.dg/cpp0x/hog1.C
>   create mode 100644 gcc/testsuite/g++.dg/cpp2a/consteval36.C
> 
> diff --git a/gcc/cp/cp-gimplify.cc b/gcc/cp/cp-gimplify.cc
> index bdf6e5f98ff..801cba141cb 100644
> --- a/gcc/cp/cp-gimplify.cc
> +++ b/gcc/cp/cp-gimplify.cc
> @@ -1052,27 +1052,6 @@ cp_fold_immediate_r (tree *stmt_p, int *walk_subtrees, void *data_)
>   
>     switch (TREE_CODE (stmt))
>       {
> -    /* Unfortunately we must handle code like
> -	 false ? bar () : 42
> -       where we have to check bar too.  The cp_fold call in cp_fold_r could
> -       fold the ?: into a constant before we see it here.  */
> -    case COND_EXPR:
> -      /* If we are called from cp_fold_immediate, we don't need to worry about
> -	 cp_fold folding away the COND_EXPR.  */
> -      if (data->flags & ff_fold_immediate)
> -	break;
> -      if (TREE_OPERAND (stmt, 1)
> -	  && cp_walk_tree (&TREE_OPERAND (stmt, 1), cp_fold_immediate_r, data,
> -			   nullptr))
> -	return error_mark_node;
> -      if (TREE_OPERAND (stmt, 2)
> -	  && cp_walk_tree (&TREE_OPERAND (stmt, 2), cp_fold_immediate_r, data,
> -			   nullptr))
> -	return error_mark_node;
> -      /* We're done here.  Don't clear *walk_subtrees here though: we're called
> -	 from cp_fold_r and we must let it recurse on the expression with
> -	 cp_fold.  */
> -      break;
>       case PTRMEM_CST:
>         if (TREE_CODE (PTRMEM_CST_MEMBER (stmt)) == FUNCTION_DECL
>   	  && DECL_IMMEDIATE_FUNCTION_P (PTRMEM_CST_MEMBER (stmt)))
> @@ -1163,7 +1142,22 @@ cp_fold_r (tree *stmt_p, int *walk_subtrees, void *data_)
>     enum tree_code code = TREE_CODE (stmt);
>   
>     if (cxx_dialect > cxx17)
> -    cp_fold_immediate_r (stmt_p, walk_subtrees, data);
> +    {
> +      /* Unfortunately we must handle code like
> +	   false ? bar () : 42
> +	 where we have to check bar too.  The cp_fold call below could
> +	 fold the ?: into a constant before we've checked it.  */
> +      if (code == COND_EXPR)
> +	{
> +	  if (TREE_OPERAND (stmt, 1))
> +	    cp_walk_tree (&TREE_OPERAND (stmt, 1), cp_fold_immediate_r, data,
> +			  nullptr);
> +	  if (TREE_OPERAND (stmt, 2))
> +	    cp_walk_tree (&TREE_OPERAND (stmt, 2), cp_fold_immediate_r, data,
> +			  nullptr);
> +	}
> +      cp_fold_immediate_r (stmt_p, walk_subtrees, data);
> +    }
>   
>     *stmt_p = stmt = cp_fold (*stmt_p, data->flags);
>   
> diff --git a/gcc/testsuite/g++.dg/cpp0x/hog1.C b/gcc/testsuite/g++.dg/cpp0x/hog1.C
> new file mode 100644
> index 00000000000..105a2e912c4
> --- /dev/null
> +++ b/gcc/testsuite/g++.dg/cpp0x/hog1.C
> @@ -0,0 +1,77 @@
> +// PR c++/111660
> +// { dg-do compile { target c++11 } }
> +
> +enum Value {
> +  LPAREN,
> +  RPAREN,
> +  LBRACE,
> +  RBRACE,
> +  LBRACK,
> +  RBRACK,
> +  CONDITIONAL,
> +  COLON,
> +  SEMICOLON,
> +  COMMA,
> +  PERIOD,
> +  BIT_OR,
> +  BIT_AND,
> +  BIT_XOR,
> +  BIT_NOT,
> +  NOT,
> +  LT,
> +  GT,
> +  MOD,
> +  ASSIGN,
> +  ADD,
> +  SUB,
> +  MUL,
> +  DIV,
> +  PRIVATE_NAME,
> +  STRING,
> +  TEMPLATE_SPAN,
> +  IDENTIFIER,
> +  WHITESPACE,
> +  ILLEGAL,
> +};
> +
> +constexpr Value GetOneCharToken(char c) {
> +  return
> +      c == '(' ? LPAREN :
> +      c == ')' ? RPAREN :
> +      c == '{' ? LBRACE :
> +      c == '}' ? RBRACE :
> +      c == '[' ? LBRACK :
> +      c == ']' ? RBRACK :
> +      c == '?' ? CONDITIONAL :
> +      c == ':' ? COLON :
> +      c == ';' ? SEMICOLON :
> +      c == ',' ? COMMA :
> +      c == '.' ? PERIOD :
> +      c == '|' ? BIT_OR :
> +      c == '&' ? BIT_AND :
> +      c == '^' ? BIT_XOR :
> +      c == '~' ? BIT_NOT :
> +      c == '!' ? NOT :
> +      c == '<' ? LT :
> +      c == '>' ? GT :
> +      c == '%' ? MOD :
> +      c == '=' ? ASSIGN :
> +      c == '+' ? ADD :
> +      c == '-' ? SUB :
> +      c == '*' ? MUL :
> +      c == '/' ? DIV :
> +      c == '#' ? PRIVATE_NAME :
> +      c == '"' ? STRING :
> +      c == '\'' ? STRING :
> +      c == '`' ? TEMPLATE_SPAN :
> +      c == '\\' ? IDENTIFIER :
> +      c == ' ' ? WHITESPACE :
> +      c == '\t' ? WHITESPACE :
> +      c == '\v' ? WHITESPACE :
> +      c == '\f' ? WHITESPACE :
> +      c == '\r' ? WHITESPACE :
> +      c == '\n' ? WHITESPACE :
> +      ILLEGAL;
> +}
> +
> +int main() {}
> diff --git a/gcc/testsuite/g++.dg/cpp2a/consteval36.C b/gcc/testsuite/g++.dg/cpp2a/consteval36.C
> new file mode 100644
> index 00000000000..d6aea214d61
> --- /dev/null
> +++ b/gcc/testsuite/g++.dg/cpp2a/consteval36.C
> @@ -0,0 +1,18 @@
> +// PR c++/111660
> +// { dg-do compile { target c++20 } }
> +
> +consteval int id (int i) { return i; }
> +
> +void
> +g (int i)
> +{
> +  1 ? 1 : ((1 ? 1 : 1), id (i)); // { dg-error "'i' is not a constant expression" }
> +  1 ? 1 : ((1 ? 1 : 1), id (i), 1); // { dg-error "'i' is not a constant expression" }
> +  1 ? 1 : ((i ? 1 : 1), id (i), 1); // { dg-error "'i' is not a constant expression" }
> +  1 ? 1 : ((1 ? i : 1), id (i), 1); // { dg-error "'i' is not a constant expression" }
> +  1 ? 1 : ((1 ? 1 : i), id (i), 1); // { dg-error "'i' is not a constant expression" }
> +  1 ? 1 : ((i ? -i : i), id (i), 1); // { dg-error "'i' is not a constant expression" }
> +  1 ? 1 : ((1 ? 1 : id (i)), id (42), 1); // { dg-error "'i' is not a constant expression" }
> +  1 ? 1 : ((1 ? 1 : id (42)), id (i)); // { dg-error "'i' is not a constant expression" }
> +  1 ? 1 : ((1 ? 1 : id (42)), id (i), 1); // { dg-error "'i' is not a constant expression" }
> +}
> 
> base-commit: 8be20f3b0bded7f9b690b27cbee58b283dbe827b