[gcc r14-4693] c++: Fix compile-time-hog in cp_fold_immediate_r [PR111660]

[gcc r14-4693] c++: Fix compile-time-hog in cp_fold_immediate_r [PR111660]

[Marek Polacek]

https://gcc.gnu.org/g:765c3b8f82d50961008c214ac2113f35e7532aa9

commit r14-4693-g765c3b8f82d50961008c214ac2113f35e7532aa9
Author: Marek Polacek <polacek@redhat.com>
Date:   Thu Oct 12 15:58:05 2023 -0400

    c++: Fix compile-time-hog in cp_fold_immediate_r [PR111660]
    
    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.

Diff:
---
 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(-)

diff --git a/gcc/cp/cp-gimplify.cc b/gcc/cp/cp-gimplify.cc
index bdf6e5f98ff4..a282c3930a37 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 000000000000..105a2e912c42
--- /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 000000000000..9c470e4b7d75
--- /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" }
+}