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

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

[Marek Polacek]

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;
     case PTRMEM_CST:
       if (TREE_CODE (PTRMEM_CST_MEMBER (stmt)) == FUNCTION_DECL
 	  && DECL_IMMEDIATE_FUNCTION_P (PTRMEM_CST_MEMBER (stmt)))
@@ -1145,7 +1145,8 @@ cp_fold_immediate (tree *tp, mce_value manifestly_const_eval)
     flags |= ff_mce_false;
 
   cp_fold_data data (flags);
-  return !!cp_walk_tree_without_duplicates (tp, cp_fold_immediate_r, &data);
+  tree r = cp_walk_tree_without_duplicates (tp, cp_fold_immediate_r, &data);
+  return r == error_mark_node;
 }
 
 /* Perform any pre-gimplification folding of C++ front end trees to
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() {}

base-commit: 8bd11fa4ffcf8bceb6511a9d6918c90a34b705b5
-- 
2.41.0

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

[Jason Merrill]

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.

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

Jason

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

[Marek Polacek]

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

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
-- 
2.41.0

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

[Jason Merrill]

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

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

[Marek Polacek]

On Sat, Oct 14, 2023 at 01:13:22AM -0400, Jason Merrill wrote:
> 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?

It is.  I ran time(1) a few more times and the results were 0m0.033s - 0m0.035s.
That said, ... 

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

...this is accurate.  I should have addressed the redundant folding in v2
even though the compilation is pretty much immediate.
 
> 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.

I agree I should do better here.  How's this, then?  I've added
debug_generic_expr to cp_fold_immediate_r to see if it gets the same
expr multiple times and it doesn't seem to.

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.030s.

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.  Maybe at_eof
can be used instead and then we can remove ff_fold_immediate.

        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                    | 52 +++++++++-------
 gcc/testsuite/g++.dg/cpp0x/hog1.C        | 77 ++++++++++++++++++++++++
 gcc/testsuite/g++.dg/cpp2a/consteval36.C | 22 +++++++
 3 files changed, 128 insertions(+), 23 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..a282c3930a3 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)))
@@ -1162,8 +1141,35 @@ cp_fold_r (tree *stmt_p, int *walk_subtrees, void *data_)
   tree stmt = *stmt_p;
   enum tree_code code = TREE_CODE (stmt);
 
-  if (cxx_dialect > cxx17)
-    cp_fold_immediate_r (stmt_p, walk_subtrees, data);
+  if (cxx_dialect >= cxx20)
+    {
+      /* 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)
+	{
+	  auto then_fn = cp_fold_r, else_fn = cp_fold_r;
+	  /* See if we can figure out if either of the branches is dead.  If it
+	     is, we don't need to do everything that cp_fold_r does.  */
+	  tree cond = maybe_constant_value (TREE_OPERAND (stmt, 0));
+	  if (integer_zerop (cond))
+	    then_fn = cp_fold_immediate_r;
+	  else if (TREE_CODE (cond) == INTEGER_CST)
+	    else_fn = cp_fold_immediate_r;
+
+	  cp_walk_tree (&TREE_OPERAND (stmt, 0), cp_fold_r, data, nullptr);
+	  if (TREE_OPERAND (stmt, 1))
+	    cp_walk_tree (&TREE_OPERAND (stmt, 1), then_fn, data,
+			  nullptr);
+	  if (TREE_OPERAND (stmt, 2))
+	    cp_walk_tree (&TREE_OPERAND (stmt, 2), else_fn, data,
+			  nullptr);
+	  *walk_subtrees = 0;
+	  /* Don't return yet, still need the cp_fold below.  */
+	}
+      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..9c470e4b7d7
--- /dev/null
+++ b/gcc/testsuite/g++.dg/cpp2a/consteval36.C
@@ -0,0 +1,22 @@
+// 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" }
+  id (i) ? 1 : ((1 ? 1 : 1), id (i)); // { dg-error "'i' is not a constant expression" }
+  1 ? 1 : ((1 ? 1 : id (i)), id (i)); // { dg-error "'i' is not a constant expression" }
+  1 ? id (i) : ((1 ? 1 : id (i)), id (i)); // { dg-error "'i' is not a constant expression" }
+  1 ? 1 : ((id (i) ? 1 : 1), id (i)); // { dg-error "'i' is not a constant expression" }
+}

base-commit: 328745607c5d403a1c7b6bc2ecaa1574ee42122f
-- 
2.41.0

Re: [PATCH v3] c++: Fix compile-time-hog in cp_fold_immediate_r [PR111660]

[Jason Merrill]

On 10/16/23 20:39, Marek Polacek wrote:
> On Sat, Oct 14, 2023 at 01:13:22AM -0400, Jason Merrill wrote:
>> 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?
> 
> It is.  I ran time(1) a few more times and the results were 0m0.033s - 0m0.035s.
> That said, ...
> 
>> 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.
> 
> ...this is accurate.  I should have addressed the redundant folding in v2
> even though the compilation is pretty much immediate.
>   
>> 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.
> 
> I agree I should do better here.  How's this, then?  I've added
> debug_generic_expr to cp_fold_immediate_r to see if it gets the same
> expr multiple times and it doesn't seem to.
> 
> 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.030s.
> 
> 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.  Maybe at_eof
> can be used instead and then we can remove ff_fold_immediate.
> 
>          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                    | 52 +++++++++-------
>   gcc/testsuite/g++.dg/cpp0x/hog1.C        | 77 ++++++++++++++++++++++++
>   gcc/testsuite/g++.dg/cpp2a/consteval36.C | 22 +++++++
>   3 files changed, 128 insertions(+), 23 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..a282c3930a3 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)))
> @@ -1162,8 +1141,35 @@ cp_fold_r (tree *stmt_p, int *walk_subtrees, void *data_)
>     tree stmt = *stmt_p;
>     enum tree_code code = TREE_CODE (stmt);
>   
> -  if (cxx_dialect > cxx17)
> -    cp_fold_immediate_r (stmt_p, walk_subtrees, data);
> +  if (cxx_dialect >= cxx20)
> +    {
> +      /* 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)
> +	{
> +	  auto then_fn = cp_fold_r, else_fn = cp_fold_r;
> +	  /* See if we can figure out if either of the branches is dead.  If it
> +	     is, we don't need to do everything that cp_fold_r does.  */
> +	  tree cond = maybe_constant_value (TREE_OPERAND (stmt, 0));
> +	  if (integer_zerop (cond))
> +	    then_fn = cp_fold_immediate_r;
> +	  else if (TREE_CODE (cond) == INTEGER_CST)
> +	    else_fn = cp_fold_immediate_r;
> +
> +	  cp_walk_tree (&TREE_OPERAND (stmt, 0), cp_fold_r, data, nullptr);

I wonder about doing this before maybe_constant_value, to hopefully 
reduce the redundant calculations?  OK either way.

> +	  if (TREE_OPERAND (stmt, 1))
> +	    cp_walk_tree (&TREE_OPERAND (stmt, 1), then_fn, data,
> +			  nullptr);
> +	  if (TREE_OPERAND (stmt, 2))
> +	    cp_walk_tree (&TREE_OPERAND (stmt, 2), else_fn, data,
> +			  nullptr);
> +	  *walk_subtrees = 0;
> +	  /* Don't return yet, still need the cp_fold below.  */
> +	}
> +      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..9c470e4b7d7
> --- /dev/null
> +++ b/gcc/testsuite/g++.dg/cpp2a/consteval36.C
> @@ -0,0 +1,22 @@
> +// 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" }
> +  id (i) ? 1 : ((1 ? 1 : 1), id (i)); // { dg-error "'i' is not a constant expression" }
> +  1 ? 1 : ((1 ? 1 : id (i)), id (i)); // { dg-error "'i' is not a constant expression" }
> +  1 ? id (i) : ((1 ? 1 : id (i)), id (i)); // { dg-error "'i' is not a constant expression" }
> +  1 ? 1 : ((id (i) ? 1 : 1), id (i)); // { dg-error "'i' is not a constant expression" }
> +}
> 
> base-commit: 328745607c5d403a1c7b6bc2ecaa1574ee42122f

Re: [PATCH v3] c++: Fix compile-time-hog in cp_fold_immediate_r [PR111660]

[Marek Polacek]

On Tue, Oct 17, 2023 at 04:49:52PM -0400, Jason Merrill wrote:
> On 10/16/23 20:39, Marek Polacek wrote:
> > On Sat, Oct 14, 2023 at 01:13:22AM -0400, Jason Merrill wrote:
> > > 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?
> > 
> > It is.  I ran time(1) a few more times and the results were 0m0.033s - 0m0.035s.
> > That said, ...
> > 
> > > 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.
> > 
> > ...this is accurate.  I should have addressed the redundant folding in v2
> > even though the compilation is pretty much immediate.
> > > 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.
> > 
> > I agree I should do better here.  How's this, then?  I've added
> > debug_generic_expr to cp_fold_immediate_r to see if it gets the same
> > expr multiple times and it doesn't seem to.
> > 
> > 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.030s.
> > 
> > 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.  Maybe at_eof
> > can be used instead and then we can remove ff_fold_immediate.
> > 
> >          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                    | 52 +++++++++-------
> >   gcc/testsuite/g++.dg/cpp0x/hog1.C        | 77 ++++++++++++++++++++++++
> >   gcc/testsuite/g++.dg/cpp2a/consteval36.C | 22 +++++++
> >   3 files changed, 128 insertions(+), 23 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..a282c3930a3 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)))
> > @@ -1162,8 +1141,35 @@ cp_fold_r (tree *stmt_p, int *walk_subtrees, void *data_)
> >     tree stmt = *stmt_p;
> >     enum tree_code code = TREE_CODE (stmt);
> > -  if (cxx_dialect > cxx17)
> > -    cp_fold_immediate_r (stmt_p, walk_subtrees, data);
> > +  if (cxx_dialect >= cxx20)
> > +    {
> > +      /* 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)
> > +	{
> > +	  auto then_fn = cp_fold_r, else_fn = cp_fold_r;
> > +	  /* See if we can figure out if either of the branches is dead.  If it
> > +	     is, we don't need to do everything that cp_fold_r does.  */
> > +	  tree cond = maybe_constant_value (TREE_OPERAND (stmt, 0));
> > +	  if (integer_zerop (cond))
> > +	    then_fn = cp_fold_immediate_r;
> > +	  else if (TREE_CODE (cond) == INTEGER_CST)
> > +	    else_fn = cp_fold_immediate_r;
> > +
> > +	  cp_walk_tree (&TREE_OPERAND (stmt, 0), cp_fold_r, data, nullptr);
> 
> I wonder about doing this before maybe_constant_value, to hopefully reduce
> the redundant calculations?  OK either way.

Yeah, I was toying with that, I had

  foo() ? x : y

where foo was a constexpr function but the cp_fold_r on op0 didn't eval it
to a constant :(.

Thanks,

Marek

Re: [PATCH v3] c++: Fix compile-time-hog in cp_fold_immediate_r [PR111660]

[Patrick Palka]

On Tue, 17 Oct 2023, Marek Polacek wrote:

> On Tue, Oct 17, 2023 at 04:49:52PM -0400, Jason Merrill wrote:
> > On 10/16/23 20:39, Marek Polacek wrote:
> > > On Sat, Oct 14, 2023 at 01:13:22AM -0400, Jason Merrill wrote:
> > > > 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?
> > > 
> > > It is.  I ran time(1) a few more times and the results were 0m0.033s - 0m0.035s.
> > > That said, ...
> > > 
> > > > 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.
> > > 
> > > ...this is accurate.  I should have addressed the redundant folding in v2
> > > even though the compilation is pretty much immediate.
> > > > 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.
> > > 
> > > I agree I should do better here.  How's this, then?  I've added
> > > debug_generic_expr to cp_fold_immediate_r to see if it gets the same
> > > expr multiple times and it doesn't seem to.
> > > 
> > > 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.030s.
> > > 
> > > 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.  Maybe at_eof
> > > can be used instead and then we can remove ff_fold_immediate.
> > > 
> > >          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                    | 52 +++++++++-------
> > >   gcc/testsuite/g++.dg/cpp0x/hog1.C        | 77 ++++++++++++++++++++++++
> > >   gcc/testsuite/g++.dg/cpp2a/consteval36.C | 22 +++++++
> > >   3 files changed, 128 insertions(+), 23 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..a282c3930a3 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)))
> > > @@ -1162,8 +1141,35 @@ cp_fold_r (tree *stmt_p, int *walk_subtrees, void *data_)
> > >     tree stmt = *stmt_p;
> > >     enum tree_code code = TREE_CODE (stmt);
> > > -  if (cxx_dialect > cxx17)
> > > -    cp_fold_immediate_r (stmt_p, walk_subtrees, data);
> > > +  if (cxx_dialect >= cxx20)
> > > +    {
> > > +      /* 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)
> > > +	{
> > > +	  auto then_fn = cp_fold_r, else_fn = cp_fold_r;
> > > +	  /* See if we can figure out if either of the branches is dead.  If it
> > > +	     is, we don't need to do everything that cp_fold_r does.  */
> > > +	  tree cond = maybe_constant_value (TREE_OPERAND (stmt, 0));
> > > +	  if (integer_zerop (cond))
> > > +	    then_fn = cp_fold_immediate_r;
> > > +	  else if (TREE_CODE (cond) == INTEGER_CST)
> > > +	    else_fn = cp_fold_immediate_r;
> > > +
> > > +	  cp_walk_tree (&TREE_OPERAND (stmt, 0), cp_fold_r, data, nullptr);
> > 
> > I wonder about doing this before maybe_constant_value, to hopefully reduce
> > the redundant calculations?  OK either way.
> 
> Yeah, I was toying with that, I had
> 
>   foo() ? x : y
> 
> where foo was a constexpr function but the cp_fold_r on op0 didn't eval it
> to a constant :(.

IIUC that's because cp_fold evaluates constexpr calls only with -O, so
doing cp_fold_r before maybe_constant_value on the condition should
still be desirable in that case?

> 
> Thanks,
> 
> Marek
> 
> 

Re: [PATCH v3] c++: Fix compile-time-hog in cp_fold_immediate_r [PR111660]

[Jason Merrill]

On 10/19/23 09:39, Patrick Palka wrote:
> On Tue, 17 Oct 2023, Marek Polacek wrote:
> 
>> On Tue, Oct 17, 2023 at 04:49:52PM -0400, Jason Merrill wrote:
>>> On 10/16/23 20:39, Marek Polacek wrote:
>>>> On Sat, Oct 14, 2023 at 01:13:22AM -0400, Jason Merrill wrote:
>>>>> 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?
>>>>
>>>> It is.  I ran time(1) a few more times and the results were 0m0.033s - 0m0.035s.
>>>> That said, ...
>>>>
>>>>> 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.
>>>>
>>>> ...this is accurate.  I should have addressed the redundant folding in v2
>>>> even though the compilation is pretty much immediate.
>>>>> 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.
>>>>
>>>> I agree I should do better here.  How's this, then?  I've added
>>>> debug_generic_expr to cp_fold_immediate_r to see if it gets the same
>>>> expr multiple times and it doesn't seem to.
>>>>
>>>> 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.030s.
>>>>
>>>> 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.  Maybe at_eof
>>>> can be used instead and then we can remove ff_fold_immediate.
>>>>
>>>>           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                    | 52 +++++++++-------
>>>>    gcc/testsuite/g++.dg/cpp0x/hog1.C        | 77 ++++++++++++++++++++++++
>>>>    gcc/testsuite/g++.dg/cpp2a/consteval36.C | 22 +++++++
>>>>    3 files changed, 128 insertions(+), 23 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..a282c3930a3 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)))
>>>> @@ -1162,8 +1141,35 @@ cp_fold_r (tree *stmt_p, int *walk_subtrees, void *data_)
>>>>      tree stmt = *stmt_p;
>>>>      enum tree_code code = TREE_CODE (stmt);
>>>> -  if (cxx_dialect > cxx17)
>>>> -    cp_fold_immediate_r (stmt_p, walk_subtrees, data);
>>>> +  if (cxx_dialect >= cxx20)
>>>> +    {
>>>> +      /* 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)
>>>> +	{
>>>> +	  auto then_fn = cp_fold_r, else_fn = cp_fold_r;
>>>> +	  /* See if we can figure out if either of the branches is dead.  If it
>>>> +	     is, we don't need to do everything that cp_fold_r does.  */
>>>> +	  tree cond = maybe_constant_value (TREE_OPERAND (stmt, 0));
>>>> +	  if (integer_zerop (cond))
>>>> +	    then_fn = cp_fold_immediate_r;
>>>> +	  else if (TREE_CODE (cond) == INTEGER_CST)
>>>> +	    else_fn = cp_fold_immediate_r;
>>>> +
>>>> +	  cp_walk_tree (&TREE_OPERAND (stmt, 0), cp_fold_r, data, nullptr);
>>>
>>> I wonder about doing this before maybe_constant_value, to hopefully reduce
>>> the redundant calculations?  OK either way.
>>
>> Yeah, I was toying with that, I had
>>
>>    foo() ? x : y
>>
>> where foo was a constexpr function but the cp_fold_r on op0 didn't eval it
>> to a constant :(.
> 
> IIUC that's because cp_fold evaluates constexpr calls only with -O, so
> doing cp_fold_r before maybe_constant_value on the condition should
> still be desirable in that case?

Hmm, and if the cp_fold_r doesn't reduce the test to a constant, I would 
think that folding the COND_EXPR also won't discard the other branch, so 
we shouldn't need to work harder to get a constant here, so we don't 
need to call maybe_constant_value at all?

Jason

Re: [PATCH v3] c++: Fix compile-time-hog in cp_fold_immediate_r [PR111660]

[Marek Polacek]

On Thu, Oct 19, 2023 at 09:39:27AM -0400, Patrick Palka wrote:
> On Tue, 17 Oct 2023, Marek Polacek wrote:
> 
> > On Tue, Oct 17, 2023 at 04:49:52PM -0400, Jason Merrill wrote:
> > > On 10/16/23 20:39, Marek Polacek wrote:
> > > > -  if (cxx_dialect > cxx17)
> > > > -    cp_fold_immediate_r (stmt_p, walk_subtrees, data);
> > > > +  if (cxx_dialect >= cxx20)
> > > > +    {
> > > > +      /* 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)
> > > > +	{
> > > > +	  auto then_fn = cp_fold_r, else_fn = cp_fold_r;
> > > > +	  /* See if we can figure out if either of the branches is dead.  If it
> > > > +	     is, we don't need to do everything that cp_fold_r does.  */
> > > > +	  tree cond = maybe_constant_value (TREE_OPERAND (stmt, 0));
> > > > +	  if (integer_zerop (cond))
> > > > +	    then_fn = cp_fold_immediate_r;
> > > > +	  else if (TREE_CODE (cond) == INTEGER_CST)
> > > > +	    else_fn = cp_fold_immediate_r;
> > > > +
> > > > +	  cp_walk_tree (&TREE_OPERAND (stmt, 0), cp_fold_r, data, nullptr);
> > > 
> > > I wonder about doing this before maybe_constant_value, to hopefully reduce
> > > the redundant calculations?  OK either way.
> > 
> > Yeah, I was toying with that, I had
> > 
> >   foo() ? x : y
> > 
> > where foo was a constexpr function but the cp_fold_r on op0 didn't eval it
> > to a constant :(.
> 
> IIUC that's because cp_fold evaluates constexpr calls only with -O, so
> doing cp_fold_r before maybe_constant_value on the condition should
> still be desirable in that case?

Ah yeah, it depends on whether -fno-inline is on or off as described below.

OK if testing passes?  Thanks,

-- >8 --
This patch is an optimization tweak for cp_fold_r.  If we cp_fold_r the
COND_EXPR's op0 first, we may be able to evaluate it to a constant if -O,
saving some work.  cp_fold has:

3143         if (callee && DECL_DECLARED_CONSTEXPR_P (callee)
3144             && !flag_no_inline)
...
3151             r = maybe_constant_value (x, /*decl=*/NULL_TREE,

flag_no_inline is 1 for -O0:

1124   if (opts->x_optimize == 0)
1125     {
1126       /* Inlining does not work if not optimizing,
1127          so force it not to be done.  */
1128       opts->x_warn_inline = 0;
1129       opts->x_flag_no_inline = 1;
1130     }

but otherwise it's 0 and cp_fold will maybe_constant_value calls to
constexpr functions.

gcc/cp/ChangeLog:

	* cp-gimplify.cc (cp_fold_r): cp_fold_r the first operand of a COND_EXPR
	before calling maybe_constant_value.
---
 gcc/cp/cp-gimplify.cc | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)

diff --git a/gcc/cp/cp-gimplify.cc b/gcc/cp/cp-gimplify.cc
index a282c3930a3..746de86dfa6 100644
--- a/gcc/cp/cp-gimplify.cc
+++ b/gcc/cp/cp-gimplify.cc
@@ -1151,14 +1151,16 @@ cp_fold_r (tree *stmt_p, int *walk_subtrees, void *data_)
 	{
 	  auto then_fn = cp_fold_r, else_fn = cp_fold_r;
 	  /* See if we can figure out if either of the branches is dead.  If it
-	     is, we don't need to do everything that cp_fold_r does.  */
+	     is, we don't need to do everything that cp_fold_r does.  If we
+	     cp_fold_r first, there's a chance it will evaluate the condition to
+	     a constant so maybe_constant_value won't have a lot of work to do.  */
+	  cp_walk_tree (&TREE_OPERAND (stmt, 0), cp_fold_r, data, nullptr);
 	  tree cond = maybe_constant_value (TREE_OPERAND (stmt, 0));
 	  if (integer_zerop (cond))
 	    then_fn = cp_fold_immediate_r;
 	  else if (TREE_CODE (cond) == INTEGER_CST)
 	    else_fn = cp_fold_immediate_r;
 
-	  cp_walk_tree (&TREE_OPERAND (stmt, 0), cp_fold_r, data, nullptr);
 	  if (TREE_OPERAND (stmt, 1))
 	    cp_walk_tree (&TREE_OPERAND (stmt, 1), then_fn, data,
 			  nullptr);

base-commit: 19cc4b9d74940f29c961e2a5a8b1fa84992d3d30
-- 
2.41.0

Re: [PATCH v3] c++: Fix compile-time-hog in cp_fold_immediate_r [PR111660]

[Marek Polacek]

On Thu, Oct 19, 2023 at 10:06:01AM -0400, Jason Merrill wrote:
> On 10/19/23 09:39, Patrick Palka wrote:
> > On Tue, 17 Oct 2023, Marek Polacek wrote:
> > 
> > > On Tue, Oct 17, 2023 at 04:49:52PM -0400, Jason Merrill wrote:
> > > > On 10/16/23 20:39, Marek Polacek wrote:
> > > > > On Sat, Oct 14, 2023 at 01:13:22AM -0400, Jason Merrill wrote:
> > > > > > 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?
> > > > > 
> > > > > It is.  I ran time(1) a few more times and the results were 0m0.033s - 0m0.035s.
> > > > > That said, ...
> > > > > 
> > > > > > 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.
> > > > > 
> > > > > ...this is accurate.  I should have addressed the redundant folding in v2
> > > > > even though the compilation is pretty much immediate.
> > > > > > 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.
> > > > > 
> > > > > I agree I should do better here.  How's this, then?  I've added
> > > > > debug_generic_expr to cp_fold_immediate_r to see if it gets the same
> > > > > expr multiple times and it doesn't seem to.
> > > > > 
> > > > > 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.030s.
> > > > > 
> > > > > 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.  Maybe at_eof
> > > > > can be used instead and then we can remove ff_fold_immediate.
> > > > > 
> > > > >           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                    | 52 +++++++++-------
> > > > >    gcc/testsuite/g++.dg/cpp0x/hog1.C        | 77 ++++++++++++++++++++++++
> > > > >    gcc/testsuite/g++.dg/cpp2a/consteval36.C | 22 +++++++
> > > > >    3 files changed, 128 insertions(+), 23 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..a282c3930a3 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)))
> > > > > @@ -1162,8 +1141,35 @@ cp_fold_r (tree *stmt_p, int *walk_subtrees, void *data_)
> > > > >      tree stmt = *stmt_p;
> > > > >      enum tree_code code = TREE_CODE (stmt);
> > > > > -  if (cxx_dialect > cxx17)
> > > > > -    cp_fold_immediate_r (stmt_p, walk_subtrees, data);
> > > > > +  if (cxx_dialect >= cxx20)
> > > > > +    {
> > > > > +      /* 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)
> > > > > +	{
> > > > > +	  auto then_fn = cp_fold_r, else_fn = cp_fold_r;
> > > > > +	  /* See if we can figure out if either of the branches is dead.  If it
> > > > > +	     is, we don't need to do everything that cp_fold_r does.  */
> > > > > +	  tree cond = maybe_constant_value (TREE_OPERAND (stmt, 0));
> > > > > +	  if (integer_zerop (cond))
> > > > > +	    then_fn = cp_fold_immediate_r;
> > > > > +	  else if (TREE_CODE (cond) == INTEGER_CST)
> > > > > +	    else_fn = cp_fold_immediate_r;
> > > > > +
> > > > > +	  cp_walk_tree (&TREE_OPERAND (stmt, 0), cp_fold_r, data, nullptr);
> > > > 
> > > > I wonder about doing this before maybe_constant_value, to hopefully reduce
> > > > the redundant calculations?  OK either way.
> > > 
> > > Yeah, I was toying with that, I had
> > > 
> > >    foo() ? x : y
> > > 
> > > where foo was a constexpr function but the cp_fold_r on op0 didn't eval it
> > > to a constant :(.
> > 
> > IIUC that's because cp_fold evaluates constexpr calls only with -O, so
> > doing cp_fold_r before maybe_constant_value on the condition should
> > still be desirable in that case?
> 
> Hmm, and if the cp_fold_r doesn't reduce the test to a constant, I would
> think that folding the COND_EXPR also won't discard the other branch, so we
> shouldn't need to work harder to get a constant here, so we don't need to
> call maybe_constant_value at all?

Sorry, I hadn't seen this message when I posted the tweak.  But the
maybe_constant_value call on TREE_OPERAND (stmt, 0) should still make
sense because it can render a branch dead even on -O0.  Right?

Marek

Re: [PATCH v3] c++: Fix compile-time-hog in cp_fold_immediate_r [PR111660]

[Jason Merrill]

On 10/19/23 10:14, Marek Polacek wrote:
> On Thu, Oct 19, 2023 at 10:06:01AM -0400, Jason Merrill wrote:
>> On 10/19/23 09:39, Patrick Palka wrote:
>>> On Tue, 17 Oct 2023, Marek Polacek wrote:
>>>
>>>> On Tue, Oct 17, 2023 at 04:49:52PM -0400, Jason Merrill wrote:
>>>>> On 10/16/23 20:39, Marek Polacek wrote:
>>>>>> On Sat, Oct 14, 2023 at 01:13:22AM -0400, Jason Merrill wrote:
>>>>>>> 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?
>>>>>>
>>>>>> It is.  I ran time(1) a few more times and the results were 0m0.033s - 0m0.035s.
>>>>>> That said, ...
>>>>>>
>>>>>>> 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.
>>>>>>
>>>>>> ...this is accurate.  I should have addressed the redundant folding in v2
>>>>>> even though the compilation is pretty much immediate.
>>>>>>> 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.
>>>>>>
>>>>>> I agree I should do better here.  How's this, then?  I've added
>>>>>> debug_generic_expr to cp_fold_immediate_r to see if it gets the same
>>>>>> expr multiple times and it doesn't seem to.
>>>>>>
>>>>>> 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.030s.
>>>>>>
>>>>>> 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.  Maybe at_eof
>>>>>> can be used instead and then we can remove ff_fold_immediate.
>>>>>>
>>>>>>            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                    | 52 +++++++++-------
>>>>>>     gcc/testsuite/g++.dg/cpp0x/hog1.C        | 77 ++++++++++++++++++++++++
>>>>>>     gcc/testsuite/g++.dg/cpp2a/consteval36.C | 22 +++++++
>>>>>>     3 files changed, 128 insertions(+), 23 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..a282c3930a3 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)))
>>>>>> @@ -1162,8 +1141,35 @@ cp_fold_r (tree *stmt_p, int *walk_subtrees, void *data_)
>>>>>>       tree stmt = *stmt_p;
>>>>>>       enum tree_code code = TREE_CODE (stmt);
>>>>>> -  if (cxx_dialect > cxx17)
>>>>>> -    cp_fold_immediate_r (stmt_p, walk_subtrees, data);
>>>>>> +  if (cxx_dialect >= cxx20)
>>>>>> +    {
>>>>>> +      /* 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)
>>>>>> +	{
>>>>>> +	  auto then_fn = cp_fold_r, else_fn = cp_fold_r;
>>>>>> +	  /* See if we can figure out if either of the branches is dead.  If it
>>>>>> +	     is, we don't need to do everything that cp_fold_r does.  */
>>>>>> +	  tree cond = maybe_constant_value (TREE_OPERAND (stmt, 0));
>>>>>> +	  if (integer_zerop (cond))
>>>>>> +	    then_fn = cp_fold_immediate_r;
>>>>>> +	  else if (TREE_CODE (cond) == INTEGER_CST)
>>>>>> +	    else_fn = cp_fold_immediate_r;
>>>>>> +
>>>>>> +	  cp_walk_tree (&TREE_OPERAND (stmt, 0), cp_fold_r, data, nullptr);
>>>>>
>>>>> I wonder about doing this before maybe_constant_value, to hopefully reduce
>>>>> the redundant calculations?  OK either way.
>>>>
>>>> Yeah, I was toying with that, I had
>>>>
>>>>     foo() ? x : y
>>>>
>>>> where foo was a constexpr function but the cp_fold_r on op0 didn't eval it
>>>> to a constant :(.
>>>
>>> IIUC that's because cp_fold evaluates constexpr calls only with -O, so
>>> doing cp_fold_r before maybe_constant_value on the condition should
>>> still be desirable in that case?
>>
>> Hmm, and if the cp_fold_r doesn't reduce the test to a constant, I would
>> think that folding the COND_EXPR also won't discard the other branch, so we
>> shouldn't need to work harder to get a constant here, so we don't need to
>> call maybe_constant_value at all?
> 
> Sorry, I hadn't seen this message when I posted the tweak.  But the
> maybe_constant_value call on TREE_OPERAND (stmt, 0) should still make
> sense because it can render a branch dead even on -O0.  Right?

But if op0 isn't constant after cp_fold, folding the COND_EXPR won't 
discard the branch, so we don't need to do the extra work to find out 
that it's actually dead.

Jason

Re: [PATCH v3] c++: Fix compile-time-hog in cp_fold_immediate_r [PR111660]

[Marek Polacek]

On Thu, Oct 19, 2023 at 12:32:49PM -0400, Jason Merrill wrote:
> On 10/19/23 10:14, Marek Polacek wrote:
> > On Thu, Oct 19, 2023 at 10:06:01AM -0400, Jason Merrill wrote:
> > > On 10/19/23 09:39, Patrick Palka wrote:
> > > > On Tue, 17 Oct 2023, Marek Polacek wrote:
> > > > 
> > > > > On Tue, Oct 17, 2023 at 04:49:52PM -0400, Jason Merrill wrote:
> > > > > > On 10/16/23 20:39, Marek Polacek wrote:
> > > > > > > On Sat, Oct 14, 2023 at 01:13:22AM -0400, Jason Merrill wrote:
> > > > > > > > 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?
> > > > > > > 
> > > > > > > It is.  I ran time(1) a few more times and the results were 0m0.033s - 0m0.035s.
> > > > > > > That said, ...
> > > > > > > 
> > > > > > > > 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.
> > > > > > > 
> > > > > > > ...this is accurate.  I should have addressed the redundant folding in v2
> > > > > > > even though the compilation is pretty much immediate.
> > > > > > > > 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.
> > > > > > > 
> > > > > > > I agree I should do better here.  How's this, then?  I've added
> > > > > > > debug_generic_expr to cp_fold_immediate_r to see if it gets the same
> > > > > > > expr multiple times and it doesn't seem to.
> > > > > > > 
> > > > > > > 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.030s.
> > > > > > > 
> > > > > > > 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.  Maybe at_eof
> > > > > > > can be used instead and then we can remove ff_fold_immediate.
> > > > > > > 
> > > > > > >            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                    | 52 +++++++++-------
> > > > > > >     gcc/testsuite/g++.dg/cpp0x/hog1.C        | 77 ++++++++++++++++++++++++
> > > > > > >     gcc/testsuite/g++.dg/cpp2a/consteval36.C | 22 +++++++
> > > > > > >     3 files changed, 128 insertions(+), 23 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..a282c3930a3 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)))
> > > > > > > @@ -1162,8 +1141,35 @@ cp_fold_r (tree *stmt_p, int *walk_subtrees, void *data_)
> > > > > > >       tree stmt = *stmt_p;
> > > > > > >       enum tree_code code = TREE_CODE (stmt);
> > > > > > > -  if (cxx_dialect > cxx17)
> > > > > > > -    cp_fold_immediate_r (stmt_p, walk_subtrees, data);
> > > > > > > +  if (cxx_dialect >= cxx20)
> > > > > > > +    {
> > > > > > > +      /* 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)
> > > > > > > +	{
> > > > > > > +	  auto then_fn = cp_fold_r, else_fn = cp_fold_r;
> > > > > > > +	  /* See if we can figure out if either of the branches is dead.  If it
> > > > > > > +	     is, we don't need to do everything that cp_fold_r does.  */
> > > > > > > +	  tree cond = maybe_constant_value (TREE_OPERAND (stmt, 0));
> > > > > > > +	  if (integer_zerop (cond))
> > > > > > > +	    then_fn = cp_fold_immediate_r;
> > > > > > > +	  else if (TREE_CODE (cond) == INTEGER_CST)
> > > > > > > +	    else_fn = cp_fold_immediate_r;
> > > > > > > +
> > > > > > > +	  cp_walk_tree (&TREE_OPERAND (stmt, 0), cp_fold_r, data, nullptr);
> > > > > > 
> > > > > > I wonder about doing this before maybe_constant_value, to hopefully reduce
> > > > > > the redundant calculations?  OK either way.
> > > > > 
> > > > > Yeah, I was toying with that, I had
> > > > > 
> > > > >     foo() ? x : y
> > > > > 
> > > > > where foo was a constexpr function but the cp_fold_r on op0 didn't eval it
> > > > > to a constant :(.
> > > > 
> > > > IIUC that's because cp_fold evaluates constexpr calls only with -O, so
> > > > doing cp_fold_r before maybe_constant_value on the condition should
> > > > still be desirable in that case?
> > > 
> > > Hmm, and if the cp_fold_r doesn't reduce the test to a constant, I would
> > > think that folding the COND_EXPR also won't discard the other branch, so we
> > > shouldn't need to work harder to get a constant here, so we don't need to
> > > call maybe_constant_value at all?
> > 
> > Sorry, I hadn't seen this message when I posted the tweak.  But the
> > maybe_constant_value call on TREE_OPERAND (stmt, 0) should still make
> > sense because it can render a branch dead even on -O0.  Right?
> 
> But if op0 isn't constant after cp_fold, folding the COND_EXPR won't discard
> the branch, so we don't need to do the extra work to find out that it's
> actually dead.

Hmm, so how about this?  Thus far dg.exp passed.

-- >8 --
This patch is an optimization tweak for cp_fold_r.  If we cp_fold_r the
COND_EXPR's op0 first, we may be able to evaluate it to a constant if -O.
cp_fold has:

3143         if (callee && DECL_DECLARED_CONSTEXPR_P (callee)
3144             && !flag_no_inline)
...
3151             r = maybe_constant_value (x, /*decl=*/NULL_TREE,

flag_no_inline is 1 for -O0:

1124   if (opts->x_optimize == 0)
1125     {
1126       /* Inlining does not work if not optimizing,
1127          so force it not to be done.  */
1128       opts->x_warn_inline = 0;
1129       opts->x_flag_no_inline = 1;
1130     }

but otherwise it's 0 and cp_fold will maybe_constant_value calls to
constexpr functions.  And if it doesn't, then folding the COND_EXPR
will keep both arms, and we can avoid calling maybe_constant_value.

gcc/cp/ChangeLog:

	* cp-gimplify.cc (cp_fold_r): Don't call maybe_constant_value.
---
 gcc/cp/cp-gimplify.cc | 7 +++----
 1 file changed, 3 insertions(+), 4 deletions(-)

diff --git a/gcc/cp/cp-gimplify.cc b/gcc/cp/cp-gimplify.cc
index a282c3930a3..385042aeef2 100644
--- a/gcc/cp/cp-gimplify.cc
+++ b/gcc/cp/cp-gimplify.cc
@@ -1152,13 +1152,12 @@ cp_fold_r (tree *stmt_p, int *walk_subtrees, void *data_)
 	  auto then_fn = cp_fold_r, else_fn = cp_fold_r;
 	  /* See if we can figure out if either of the branches is dead.  If it
 	     is, we don't need to do everything that cp_fold_r does.  */
-	  tree cond = maybe_constant_value (TREE_OPERAND (stmt, 0));
-	  if (integer_zerop (cond))
+	  cp_walk_tree (&TREE_OPERAND (stmt, 0), cp_fold_r, data, nullptr);
+	  if (integer_zerop (TREE_OPERAND (stmt, 0)))
 	    then_fn = cp_fold_immediate_r;
-	  else if (TREE_CODE (cond) == INTEGER_CST)
+	  else if (TREE_CODE (TREE_OPERAND (stmt, 0)) == INTEGER_CST)
 	    else_fn = cp_fold_immediate_r;
 
-	  cp_walk_tree (&TREE_OPERAND (stmt, 0), cp_fold_r, data, nullptr);
 	  if (TREE_OPERAND (stmt, 1))
 	    cp_walk_tree (&TREE_OPERAND (stmt, 1), then_fn, data,
 			  nullptr);

base-commit: 00e7c49fa04a3766e4726322b427621a74b78c71
-- 
2.41.0

Re: [PATCH v3] c++: Fix compile-time-hog in cp_fold_immediate_r [PR111660]

[Jason Merrill]

On 10/19/23 12:55, Marek Polacek wrote:
> On Thu, Oct 19, 2023 at 12:32:49PM -0400, Jason Merrill wrote:
>> On 10/19/23 10:14, Marek Polacek wrote:
>>> On Thu, Oct 19, 2023 at 10:06:01AM -0400, Jason Merrill wrote:
>>>> On 10/19/23 09:39, Patrick Palka wrote:
>>>>> On Tue, 17 Oct 2023, Marek Polacek wrote:
>>>>>
>>>>>> On Tue, Oct 17, 2023 at 04:49:52PM -0400, Jason Merrill wrote:
>>>>>>> On 10/16/23 20:39, Marek Polacek wrote:
>>>>>>>> On Sat, Oct 14, 2023 at 01:13:22AM -0400, Jason Merrill wrote:
>>>>>>>>> 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?
>>>>>>>>
>>>>>>>> It is.  I ran time(1) a few more times and the results were 0m0.033s - 0m0.035s.
>>>>>>>> That said, ...
>>>>>>>>
>>>>>>>>> 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.
>>>>>>>>
>>>>>>>> ...this is accurate.  I should have addressed the redundant folding in v2
>>>>>>>> even though the compilation is pretty much immediate.
>>>>>>>>> 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.
>>>>>>>>
>>>>>>>> I agree I should do better here.  How's this, then?  I've added
>>>>>>>> debug_generic_expr to cp_fold_immediate_r to see if it gets the same
>>>>>>>> expr multiple times and it doesn't seem to.
>>>>>>>>
>>>>>>>> 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.030s.
>>>>>>>>
>>>>>>>> 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.  Maybe at_eof
>>>>>>>> can be used instead and then we can remove ff_fold_immediate.
>>>>>>>>
>>>>>>>>             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                    | 52 +++++++++-------
>>>>>>>>      gcc/testsuite/g++.dg/cpp0x/hog1.C        | 77 ++++++++++++++++++++++++
>>>>>>>>      gcc/testsuite/g++.dg/cpp2a/consteval36.C | 22 +++++++
>>>>>>>>      3 files changed, 128 insertions(+), 23 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..a282c3930a3 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)))
>>>>>>>> @@ -1162,8 +1141,35 @@ cp_fold_r (tree *stmt_p, int *walk_subtrees, void *data_)
>>>>>>>>        tree stmt = *stmt_p;
>>>>>>>>        enum tree_code code = TREE_CODE (stmt);
>>>>>>>> -  if (cxx_dialect > cxx17)
>>>>>>>> -    cp_fold_immediate_r (stmt_p, walk_subtrees, data);
>>>>>>>> +  if (cxx_dialect >= cxx20)
>>>>>>>> +    {
>>>>>>>> +      /* 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)
>>>>>>>> +	{
>>>>>>>> +	  auto then_fn = cp_fold_r, else_fn = cp_fold_r;
>>>>>>>> +	  /* See if we can figure out if either of the branches is dead.  If it
>>>>>>>> +	     is, we don't need to do everything that cp_fold_r does.  */
>>>>>>>> +	  tree cond = maybe_constant_value (TREE_OPERAND (stmt, 0));
>>>>>>>> +	  if (integer_zerop (cond))
>>>>>>>> +	    then_fn = cp_fold_immediate_r;
>>>>>>>> +	  else if (TREE_CODE (cond) == INTEGER_CST)
>>>>>>>> +	    else_fn = cp_fold_immediate_r;
>>>>>>>> +
>>>>>>>> +	  cp_walk_tree (&TREE_OPERAND (stmt, 0), cp_fold_r, data, nullptr);
>>>>>>>
>>>>>>> I wonder about doing this before maybe_constant_value, to hopefully reduce
>>>>>>> the redundant calculations?  OK either way.
>>>>>>
>>>>>> Yeah, I was toying with that, I had
>>>>>>
>>>>>>      foo() ? x : y
>>>>>>
>>>>>> where foo was a constexpr function but the cp_fold_r on op0 didn't eval it
>>>>>> to a constant :(.
>>>>>
>>>>> IIUC that's because cp_fold evaluates constexpr calls only with -O, so
>>>>> doing cp_fold_r before maybe_constant_value on the condition should
>>>>> still be desirable in that case?
>>>>
>>>> Hmm, and if the cp_fold_r doesn't reduce the test to a constant, I would
>>>> think that folding the COND_EXPR also won't discard the other branch, so we
>>>> shouldn't need to work harder to get a constant here, so we don't need to
>>>> call maybe_constant_value at all?
>>>
>>> Sorry, I hadn't seen this message when I posted the tweak.  But the
>>> maybe_constant_value call on TREE_OPERAND (stmt, 0) should still make
>>> sense because it can render a branch dead even on -O0.  Right?
>>
>> But if op0 isn't constant after cp_fold, folding the COND_EXPR won't discard
>> the branch, so we don't need to do the extra work to find out that it's
>> actually dead.
> 
> Hmm, so how about this?  Thus far dg.exp passed.
> 
> -- >8 --
> This patch is an optimization tweak for cp_fold_r.  If we cp_fold_r the
> COND_EXPR's op0 first, we may be able to evaluate it to a constant if -O.
> cp_fold has:
> 
> 3143         if (callee && DECL_DECLARED_CONSTEXPR_P (callee)
> 3144             && !flag_no_inline)
> ...
> 3151             r = maybe_constant_value (x, /*decl=*/NULL_TREE,
> 
> flag_no_inline is 1 for -O0:
> 
> 1124   if (opts->x_optimize == 0)
> 1125     {
> 1126       /* Inlining does not work if not optimizing,
> 1127          so force it not to be done.  */
> 1128       opts->x_warn_inline = 0;
> 1129       opts->x_flag_no_inline = 1;
> 1130     }
> 
> but otherwise it's 0 and cp_fold will maybe_constant_value calls to
> constexpr functions.  And if it doesn't, then folding the COND_EXPR
> will keep both arms, and we can avoid calling maybe_constant_value.
> 
> gcc/cp/ChangeLog:
> 
> 	* cp-gimplify.cc (cp_fold_r): Don't call maybe_constant_value.
> ---
>   gcc/cp/cp-gimplify.cc | 7 +++----
>   1 file changed, 3 insertions(+), 4 deletions(-)
> 
> diff --git a/gcc/cp/cp-gimplify.cc b/gcc/cp/cp-gimplify.cc
> index a282c3930a3..385042aeef2 100644
> --- a/gcc/cp/cp-gimplify.cc
> +++ b/gcc/cp/cp-gimplify.cc
> @@ -1152,13 +1152,12 @@ cp_fold_r (tree *stmt_p, int *walk_subtrees, void *data_)
>   	  auto then_fn = cp_fold_r, else_fn = cp_fold_r;
>   	  /* See if we can figure out if either of the branches is dead.  If it
>   	     is, we don't need to do everything that cp_fold_r does.  */
> -	  tree cond = maybe_constant_value (TREE_OPERAND (stmt, 0));
> -	  if (integer_zerop (cond))
> +	  cp_walk_tree (&TREE_OPERAND (stmt, 0), cp_fold_r, data, nullptr);
> +	  if (integer_zerop (TREE_OPERAND (stmt, 0)))
>   	    then_fn = cp_fold_immediate_r;
> -	  else if (TREE_CODE (cond) == INTEGER_CST)
> +	  else if (TREE_CODE (TREE_OPERAND (stmt, 0)) == INTEGER_CST)

You probably want to STRIP_NOPS before checking the TREE_CODE, like 
fold_ternary_loc and integer_zerop do.

Jason

Re: [PATCH v3] c++: Fix compile-time-hog in cp_fold_immediate_r [PR111660]

[Marek Polacek]

On Thu, Oct 19, 2023 at 01:02:33PM -0400, Jason Merrill wrote:
> On 10/19/23 12:55, Marek Polacek wrote:
> > On Thu, Oct 19, 2023 at 12:32:49PM -0400, Jason Merrill wrote:
> > > On 10/19/23 10:14, Marek Polacek wrote:
> > > > On Thu, Oct 19, 2023 at 10:06:01AM -0400, Jason Merrill wrote:
> > > > > On 10/19/23 09:39, Patrick Palka wrote:
> > > > > > On Tue, 17 Oct 2023, Marek Polacek wrote:
[...]
> > > > > > > > >          case PTRMEM_CST:
> > > > > > > > >            if (TREE_CODE (PTRMEM_CST_MEMBER (stmt)) == FUNCTION_DECL
> > > > > > > > >      	  && DECL_IMMEDIATE_FUNCTION_P (PTRMEM_CST_MEMBER (stmt)))
> > > > > > > > > @@ -1162,8 +1141,35 @@ cp_fold_r (tree *stmt_p, int *walk_subtrees, void *data_)
> > > > > > > > >        tree stmt = *stmt_p;
> > > > > > > > >        enum tree_code code = TREE_CODE (stmt);
> > > > > > > > > -  if (cxx_dialect > cxx17)
> > > > > > > > > -    cp_fold_immediate_r (stmt_p, walk_subtrees, data);
> > > > > > > > > +  if (cxx_dialect >= cxx20)
> > > > > > > > > +    {
> > > > > > > > > +      /* 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)
> > > > > > > > > +	{
> > > > > > > > > +	  auto then_fn = cp_fold_r, else_fn = cp_fold_r;
> > > > > > > > > +	  /* See if we can figure out if either of the branches is dead.  If it
> > > > > > > > > +	     is, we don't need to do everything that cp_fold_r does.  */
> > > > > > > > > +	  tree cond = maybe_constant_value (TREE_OPERAND (stmt, 0));
> > > > > > > > > +	  if (integer_zerop (cond))
> > > > > > > > > +	    then_fn = cp_fold_immediate_r;
> > > > > > > > > +	  else if (TREE_CODE (cond) == INTEGER_CST)
> > > > > > > > > +	    else_fn = cp_fold_immediate_r;
> > > > > > > > > +
> > > > > > > > > +	  cp_walk_tree (&TREE_OPERAND (stmt, 0), cp_fold_r, data, nullptr);
> > > > > > > > 
> > > > > > > > I wonder about doing this before maybe_constant_value, to hopefully reduce
> > > > > > > > the redundant calculations?  OK either way.
> > > > > > > 
> > > > > > > Yeah, I was toying with that, I had
> > > > > > > 
> > > > > > >      foo() ? x : y
> > > > > > > 
> > > > > > > where foo was a constexpr function but the cp_fold_r on op0 didn't eval it
> > > > > > > to a constant :(.
> > > > > > 
> > > > > > IIUC that's because cp_fold evaluates constexpr calls only with -O, so
> > > > > > doing cp_fold_r before maybe_constant_value on the condition should
> > > > > > still be desirable in that case?
> > > > > 
> > > > > Hmm, and if the cp_fold_r doesn't reduce the test to a constant, I would
> > > > > think that folding the COND_EXPR also won't discard the other branch, so we
> > > > > shouldn't need to work harder to get a constant here, so we don't need to
> > > > > call maybe_constant_value at all?
> > > > 
> > > > Sorry, I hadn't seen this message when I posted the tweak.  But the
> > > > maybe_constant_value call on TREE_OPERAND (stmt, 0) should still make
> > > > sense because it can render a branch dead even on -O0.  Right?
> > > 
> > > But if op0 isn't constant after cp_fold, folding the COND_EXPR won't discard
> > > the branch, so we don't need to do the extra work to find out that it's
> > > actually dead.
> > 
> > Hmm, so how about this?  Thus far dg.exp passed.
> > 
> > -- >8 --
> > This patch is an optimization tweak for cp_fold_r.  If we cp_fold_r the
> > COND_EXPR's op0 first, we may be able to evaluate it to a constant if -O.
> > cp_fold has:
> > 
> > 3143         if (callee && DECL_DECLARED_CONSTEXPR_P (callee)
> > 3144             && !flag_no_inline)
> > ...
> > 3151             r = maybe_constant_value (x, /*decl=*/NULL_TREE,
> > 
> > flag_no_inline is 1 for -O0:
> > 
> > 1124   if (opts->x_optimize == 0)
> > 1125     {
> > 1126       /* Inlining does not work if not optimizing,
> > 1127          so force it not to be done.  */
> > 1128       opts->x_warn_inline = 0;
> > 1129       opts->x_flag_no_inline = 1;
> > 1130     }
> > 
> > but otherwise it's 0 and cp_fold will maybe_constant_value calls to
> > constexpr functions.  And if it doesn't, then folding the COND_EXPR
> > will keep both arms, and we can avoid calling maybe_constant_value.
> > 
> > gcc/cp/ChangeLog:
> > 
> > 	* cp-gimplify.cc (cp_fold_r): Don't call maybe_constant_value.
> > ---
> >   gcc/cp/cp-gimplify.cc | 7 +++----
> >   1 file changed, 3 insertions(+), 4 deletions(-)
> > 
> > diff --git a/gcc/cp/cp-gimplify.cc b/gcc/cp/cp-gimplify.cc
> > index a282c3930a3..385042aeef2 100644
> > --- a/gcc/cp/cp-gimplify.cc
> > +++ b/gcc/cp/cp-gimplify.cc
> > @@ -1152,13 +1152,12 @@ cp_fold_r (tree *stmt_p, int *walk_subtrees, void *data_)
> >   	  auto then_fn = cp_fold_r, else_fn = cp_fold_r;
> >   	  /* See if we can figure out if either of the branches is dead.  If it
> >   	     is, we don't need to do everything that cp_fold_r does.  */
> > -	  tree cond = maybe_constant_value (TREE_OPERAND (stmt, 0));
> > -	  if (integer_zerop (cond))
> > +	  cp_walk_tree (&TREE_OPERAND (stmt, 0), cp_fold_r, data, nullptr);
> > +	  if (integer_zerop (TREE_OPERAND (stmt, 0)))
> >   	    then_fn = cp_fold_immediate_r;
> > -	  else if (TREE_CODE (cond) == INTEGER_CST)
> > +	  else if (TREE_CODE (TREE_OPERAND (stmt, 0)) == INTEGER_CST)
> 
> You probably want to STRIP_NOPS before checking the TREE_CODE, like
> fold_ternary_loc and integer_zerop do.

Ok, or use integer_nonzerop like Patrick suggested:

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

-- >8 --
This patch is an optimization tweak for cp_fold_r.  If we cp_fold_r the
COND_EXPR's op0 first, we may be able to evaluate it to a constant if -O.
cp_fold has:

3143         if (callee && DECL_DECLARED_CONSTEXPR_P (callee)
3144             && !flag_no_inline)
...
3151             r = maybe_constant_value (x, /*decl=*/NULL_TREE,

flag_no_inline is 1 for -O0:

1124   if (opts->x_optimize == 0)
1125     {
1126       /* Inlining does not work if not optimizing,
1127          so force it not to be done.  */
1128       opts->x_warn_inline = 0;
1129       opts->x_flag_no_inline = 1;
1130     }

but otherwise it's 0 and cp_fold will maybe_constant_value calls to
constexpr functions.  And if it doesn't, then folding the COND_EXPR
will keep both arms, and we can avoid calling maybe_constant_value.

gcc/cp/ChangeLog:

	* cp-gimplify.cc (cp_fold_r): Don't call maybe_constant_value.
---
 gcc/cp/cp-gimplify.cc | 7 +++----
 1 file changed, 3 insertions(+), 4 deletions(-)

diff --git a/gcc/cp/cp-gimplify.cc b/gcc/cp/cp-gimplify.cc
index a282c3930a3..33e9411f10c 100644
--- a/gcc/cp/cp-gimplify.cc
+++ b/gcc/cp/cp-gimplify.cc
@@ -1152,13 +1152,12 @@ cp_fold_r (tree *stmt_p, int *walk_subtrees, void *data_)
 	  auto then_fn = cp_fold_r, else_fn = cp_fold_r;
 	  /* See if we can figure out if either of the branches is dead.  If it
 	     is, we don't need to do everything that cp_fold_r does.  */
-	  tree cond = maybe_constant_value (TREE_OPERAND (stmt, 0));
-	  if (integer_zerop (cond))
+	  cp_walk_tree (&TREE_OPERAND (stmt, 0), cp_fold_r, data, nullptr);
+	  if (integer_zerop (TREE_OPERAND (stmt, 0)))
 	    then_fn = cp_fold_immediate_r;
-	  else if (TREE_CODE (cond) == INTEGER_CST)
+	  else if (integer_nonzerop (TREE_OPERAND (stmt, 0)))
 	    else_fn = cp_fold_immediate_r;
 
-	  cp_walk_tree (&TREE_OPERAND (stmt, 0), cp_fold_r, data, nullptr);
 	  if (TREE_OPERAND (stmt, 1))
 	    cp_walk_tree (&TREE_OPERAND (stmt, 1), then_fn, data,
 			  nullptr);

base-commit: d8e4e7def3338344a761d841010e98d017c58b0a
-- 
2.41.0

Re: [PATCH v3] c++: Fix compile-time-hog in cp_fold_immediate_r [PR111660]

[Jason Merrill]

On 10/19/23 14:45, Marek Polacek wrote:
> On Thu, Oct 19, 2023 at 01:02:33PM -0400, Jason Merrill wrote:
>> On 10/19/23 12:55, Marek Polacek wrote:
>>> On Thu, Oct 19, 2023 at 12:32:49PM -0400, Jason Merrill wrote:
>>>> On 10/19/23 10:14, Marek Polacek wrote:
>>>>> On Thu, Oct 19, 2023 at 10:06:01AM -0400, Jason Merrill wrote:
>>>>>> On 10/19/23 09:39, Patrick Palka wrote:
>>>>>>> On Tue, 17 Oct 2023, Marek Polacek wrote:
> [...]
>>>>>>>>>>           case PTRMEM_CST:
>>>>>>>>>>             if (TREE_CODE (PTRMEM_CST_MEMBER (stmt)) == FUNCTION_DECL
>>>>>>>>>>       	  && DECL_IMMEDIATE_FUNCTION_P (PTRMEM_CST_MEMBER (stmt)))
>>>>>>>>>> @@ -1162,8 +1141,35 @@ cp_fold_r (tree *stmt_p, int *walk_subtrees, void *data_)
>>>>>>>>>>         tree stmt = *stmt_p;
>>>>>>>>>>         enum tree_code code = TREE_CODE (stmt);
>>>>>>>>>> -  if (cxx_dialect > cxx17)
>>>>>>>>>> -    cp_fold_immediate_r (stmt_p, walk_subtrees, data);
>>>>>>>>>> +  if (cxx_dialect >= cxx20)
>>>>>>>>>> +    {
>>>>>>>>>> +      /* 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)
>>>>>>>>>> +	{
>>>>>>>>>> +	  auto then_fn = cp_fold_r, else_fn = cp_fold_r;
>>>>>>>>>> +	  /* See if we can figure out if either of the branches is dead.  If it
>>>>>>>>>> +	     is, we don't need to do everything that cp_fold_r does.  */
>>>>>>>>>> +	  tree cond = maybe_constant_value (TREE_OPERAND (stmt, 0));
>>>>>>>>>> +	  if (integer_zerop (cond))
>>>>>>>>>> +	    then_fn = cp_fold_immediate_r;
>>>>>>>>>> +	  else if (TREE_CODE (cond) == INTEGER_CST)
>>>>>>>>>> +	    else_fn = cp_fold_immediate_r;
>>>>>>>>>> +
>>>>>>>>>> +	  cp_walk_tree (&TREE_OPERAND (stmt, 0), cp_fold_r, data, nullptr);
>>>>>>>>>
>>>>>>>>> I wonder about doing this before maybe_constant_value, to hopefully reduce
>>>>>>>>> the redundant calculations?  OK either way.
>>>>>>>>
>>>>>>>> Yeah, I was toying with that, I had
>>>>>>>>
>>>>>>>>       foo() ? x : y
>>>>>>>>
>>>>>>>> where foo was a constexpr function but the cp_fold_r on op0 didn't eval it
>>>>>>>> to a constant :(.
>>>>>>>
>>>>>>> IIUC that's because cp_fold evaluates constexpr calls only with -O, so
>>>>>>> doing cp_fold_r before maybe_constant_value on the condition should
>>>>>>> still be desirable in that case?
>>>>>>
>>>>>> Hmm, and if the cp_fold_r doesn't reduce the test to a constant, I would
>>>>>> think that folding the COND_EXPR also won't discard the other branch, so we
>>>>>> shouldn't need to work harder to get a constant here, so we don't need to
>>>>>> call maybe_constant_value at all?
>>>>>
>>>>> Sorry, I hadn't seen this message when I posted the tweak.  But the
>>>>> maybe_constant_value call on TREE_OPERAND (stmt, 0) should still make
>>>>> sense because it can render a branch dead even on -O0.  Right?
>>>>
>>>> But if op0 isn't constant after cp_fold, folding the COND_EXPR won't discard
>>>> the branch, so we don't need to do the extra work to find out that it's
>>>> actually dead.
>>>
>>> Hmm, so how about this?  Thus far dg.exp passed.
>>>
>>> -- >8 --
>>> This patch is an optimization tweak for cp_fold_r.  If we cp_fold_r the
>>> COND_EXPR's op0 first, we may be able to evaluate it to a constant if -O.
>>> cp_fold has:
>>>
>>> 3143         if (callee && DECL_DECLARED_CONSTEXPR_P (callee)
>>> 3144             && !flag_no_inline)
>>> ...
>>> 3151             r = maybe_constant_value (x, /*decl=*/NULL_TREE,
>>>
>>> flag_no_inline is 1 for -O0:
>>>
>>> 1124   if (opts->x_optimize == 0)
>>> 1125     {
>>> 1126       /* Inlining does not work if not optimizing,
>>> 1127          so force it not to be done.  */
>>> 1128       opts->x_warn_inline = 0;
>>> 1129       opts->x_flag_no_inline = 1;
>>> 1130     }
>>>
>>> but otherwise it's 0 and cp_fold will maybe_constant_value calls to
>>> constexpr functions.  And if it doesn't, then folding the COND_EXPR
>>> will keep both arms, and we can avoid calling maybe_constant_value.
>>>
>>> gcc/cp/ChangeLog:
>>>
>>> 	* cp-gimplify.cc (cp_fold_r): Don't call maybe_constant_value.
>>> ---
>>>    gcc/cp/cp-gimplify.cc | 7 +++----
>>>    1 file changed, 3 insertions(+), 4 deletions(-)
>>>
>>> diff --git a/gcc/cp/cp-gimplify.cc b/gcc/cp/cp-gimplify.cc
>>> index a282c3930a3..385042aeef2 100644
>>> --- a/gcc/cp/cp-gimplify.cc
>>> +++ b/gcc/cp/cp-gimplify.cc
>>> @@ -1152,13 +1152,12 @@ cp_fold_r (tree *stmt_p, int *walk_subtrees, void *data_)
>>>    	  auto then_fn = cp_fold_r, else_fn = cp_fold_r;
>>>    	  /* See if we can figure out if either of the branches is dead.  If it
>>>    	     is, we don't need to do everything that cp_fold_r does.  */
>>> -	  tree cond = maybe_constant_value (TREE_OPERAND (stmt, 0));
>>> -	  if (integer_zerop (cond))
>>> +	  cp_walk_tree (&TREE_OPERAND (stmt, 0), cp_fold_r, data, nullptr);
>>> +	  if (integer_zerop (TREE_OPERAND (stmt, 0)))
>>>    	    then_fn = cp_fold_immediate_r;
>>> -	  else if (TREE_CODE (cond) == INTEGER_CST)
>>> +	  else if (TREE_CODE (TREE_OPERAND (stmt, 0)) == INTEGER_CST)
>>
>> You probably want to STRIP_NOPS before checking the TREE_CODE, like
>> fold_ternary_loc and integer_zerop do.
> 
> Ok, or use integer_nonzerop like Patrick suggested:
> 
> Bootstrapped/regtested on x86_64-pc-linux-gnu, ok for trunk?

OK.

> -- >8 --
> This patch is an optimization tweak for cp_fold_r.  If we cp_fold_r the
> COND_EXPR's op0 first, we may be able to evaluate it to a constant if -O.
> cp_fold has:
> 
> 3143         if (callee && DECL_DECLARED_CONSTEXPR_P (callee)
> 3144             && !flag_no_inline)
> ...
> 3151             r = maybe_constant_value (x, /*decl=*/NULL_TREE,
> 
> flag_no_inline is 1 for -O0:
> 
> 1124   if (opts->x_optimize == 0)
> 1125     {
> 1126       /* Inlining does not work if not optimizing,
> 1127          so force it not to be done.  */
> 1128       opts->x_warn_inline = 0;
> 1129       opts->x_flag_no_inline = 1;
> 1130     }
> 
> but otherwise it's 0 and cp_fold will maybe_constant_value calls to
> constexpr functions.  And if it doesn't, then folding the COND_EXPR
> will keep both arms, and we can avoid calling maybe_constant_value.
> 
> gcc/cp/ChangeLog:
> 
> 	* cp-gimplify.cc (cp_fold_r): Don't call maybe_constant_value.
> ---
>   gcc/cp/cp-gimplify.cc | 7 +++----
>   1 file changed, 3 insertions(+), 4 deletions(-)
> 
> diff --git a/gcc/cp/cp-gimplify.cc b/gcc/cp/cp-gimplify.cc
> index a282c3930a3..33e9411f10c 100644
> --- a/gcc/cp/cp-gimplify.cc
> +++ b/gcc/cp/cp-gimplify.cc
> @@ -1152,13 +1152,12 @@ cp_fold_r (tree *stmt_p, int *walk_subtrees, void *data_)
>   	  auto then_fn = cp_fold_r, else_fn = cp_fold_r;
>   	  /* See if we can figure out if either of the branches is dead.  If it
>   	     is, we don't need to do everything that cp_fold_r does.  */
> -	  tree cond = maybe_constant_value (TREE_OPERAND (stmt, 0));
> -	  if (integer_zerop (cond))
> +	  cp_walk_tree (&TREE_OPERAND (stmt, 0), cp_fold_r, data, nullptr);
> +	  if (integer_zerop (TREE_OPERAND (stmt, 0)))
>   	    then_fn = cp_fold_immediate_r;
> -	  else if (TREE_CODE (cond) == INTEGER_CST)
> +	  else if (integer_nonzerop (TREE_OPERAND (stmt, 0)))
>   	    else_fn = cp_fold_immediate_r;
>   
> -	  cp_walk_tree (&TREE_OPERAND (stmt, 0), cp_fold_r, data, nullptr);
>   	  if (TREE_OPERAND (stmt, 1))
>   	    cp_walk_tree (&TREE_OPERAND (stmt, 1), then_fn, data,
>   			  nullptr);
> 
> base-commit: d8e4e7def3338344a761d841010e98d017c58b0a