[Bug c++/70847] [6/7 Regression] exponential time in cp_fold for chained virtual function calls

jakub at gcc dot gnu.org gcc-bugzilla@gcc.gnu.org
Fri Jun 3 13:17:00 GMT 2016


https://gcc.gnu.org/bugzilla/show_bug.cgi?id=70847

--- Comment #12 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
I had in mind:
--- cp-gimplify.c.jj1   2016-06-02 18:35:18.000000000 +0200
+++ cp-gimplify.c       2016-06-03 15:06:04.465913964 +0200
@@ -941,13 +941,25 @@ cp_fold_r (tree *stmt_p, int *walk_subtr
   *stmt_p = stmt = cp_fold (*stmt_p);

   code = TREE_CODE (stmt);
-  if (code == OMP_FOR || code == OMP_SIMD || code == OMP_DISTRIBUTE
-      || code == OMP_TASKLOOP || code == CILK_FOR || code == CILK_SIMD
-      || code == OACC_LOOP)
+  switch (code)
     {
       tree x;
       int i, n;

+    case SAVE_EXPR:
+    case TARGET_EXPR:
+      /* For SAVE_EXPR and TARGET_EXPR, only work subtrees once,
+        otherwise the walking can be exponential.  */
+      if (((hash_set<tree> *) data)->add (stmt))
+       *walk_subtrees = 0;
+      break;
+    case OMP_FOR:
+    case OMP_SIMD:
+    case OMP_DISTRIBUTE:
+    case OMP_TASKLOOP:
+    case CILK_FOR:
+    case CILK_SIMD:
+    case OACC_LOOP:
       cp_walk_tree (&OMP_FOR_BODY (stmt), cp_fold_r, data, NULL);
       cp_walk_tree (&OMP_FOR_CLAUSES (stmt), cp_fold_r, data, NULL);
       cp_walk_tree (&OMP_FOR_INIT (stmt), cp_fold_r, data, NULL);
@@ -986,6 +998,9 @@ cp_fold_r (tree *stmt_p, int *walk_subtr
        }
       cp_walk_tree (&OMP_FOR_PRE_BODY (stmt), cp_fold_r, data, NULL);
       *walk_subtrees = 0;
+      break;
+    default:
+      break;
     }

   return NULL;
@@ -997,7 +1012,8 @@ cp_fold_r (tree *stmt_p, int *walk_subtr
 void
 cp_fold_function (tree fndecl)
 {
-  cp_walk_tree (&DECL_SAVED_TREE (fndecl), cp_fold_r, NULL, NULL);
+  hash_set<tree> pset;
+  cp_walk_tree (&DECL_SAVED_TREE (fndecl), cp_fold_r, &pset, NULL);
 }

 /* Perform any pre-gimplification lowering of C++ front end trees to

which also fixes the testcases.
But, you're right, unless something clears the fold cache from within inside
cp_fold_function, it should be fine.
There is also the question whether we couldn't just use the fold_cache instead
of a separate pset; but if it is possible cp_fold has been called before on
some subtrees, some tree might be in the cache even when its subtrees weren't
walked yet.


More information about the Gcc-bugs mailing list