re PR c++/70847 (exponential time in cp_fold for chained virtual function calls)

	PR c++/70847
	PR c++/71330
	PR c++/71393
	* cp-gimplify.c (cp_fold_r): Set *walk_subtrees = 0 and return NULL
	right after cp_fold call if cp_fold has returned the same stmt
	already in some earlier cp_fold_r call.
	(cp_fold_function): Add pset automatic variable, pass its address
	to cp_walk_tree.

	* g++.dg/opt/pr70847.C: New test.
	* g++.dg/ubsan/pr70847.C: New test.
	* g++.dg/ubsan/pr71393.C: New test.

Co-Authored-By: Patrick Palka <ppalka@gcc.gnu.org>

From-SVN: r237151

6 files changed, 71 insertions, 1 deletions

diff --git a/gcc/cp/ChangeLog b/gcc/cp/ChangeLog
index b6c0c98..86dddd2 100644
--- a/gcc/cp/ChangeLog
+++ b/gcc/cp/ChangeLog
@@ -1,3 +1,15 @@
+2016-06-06  Jakub Jelinek  <jakub@redhat.com>
+	    Patrick Palka  <ppalka@gcc.gnu.org>
+
+	PR c++/70847
+	PR c++/71330
+	PR c++/71393
+	* cp-gimplify.c (cp_fold_r): Set *walk_subtrees = 0 and return NULL
+	right after cp_fold call if cp_fold has returned the same stmt
+	already in some earlier cp_fold_r call.
+	(cp_fold_function): Add pset automatic variable, pass its address
+	to cp_walk_tree.
+
 2016-06-04  Paolo Carlini  <paolo.carlini@oracle.com>
 
 	PR c++/70202
diff --git a/gcc/cp/cp-gimplify.c b/gcc/cp/cp-gimplify.c
index 72ba50e..dcb0fa6 100644
--- a/gcc/cp/cp-gimplify.c
+++ b/gcc/cp/cp-gimplify.c
@@ -940,6 +940,17 @@ cp_fold_r (tree *stmt_p, int *walk_subtrees, void *data)
 
   *stmt_p = stmt = cp_fold (*stmt_p);
 
+  if (((hash_set<tree> *) data)->add (stmt))
+    {
+      /* Don't walk subtrees of stmts we've already walked once, otherwise
+	 we can have exponential complexity with e.g. lots of nested
+	 SAVE_EXPRs or TARGET_EXPRs.  cp_fold uses a cache and will return
+	 always the same tree, which the first time cp_fold_r has been
+	 called on it had the subtrees walked.  */
+      *walk_subtrees = 0;
+      return NULL;
+    }
+
   code = TREE_CODE (stmt);
   if (code == OMP_FOR || code == OMP_SIMD || code == OMP_DISTRIBUTE
       || code == OMP_TASKLOOP || code == CILK_FOR || code == CILK_SIMD
@@ -997,7 +1008,8 @@ cp_fold_r (tree *stmt_p, int *walk_subtrees, void *data)
 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
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index fa5d700..29f5150 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,4 +1,14 @@
 2016-06-06  Jakub Jelinek  <jakub@redhat.com>
+	    Patrick Palka  <ppalka@gcc.gnu.org>
+
+	PR c++/70847
+	PR c++/71330
+	PR c++/71393
+	* g++.dg/opt/pr70847.C: New test.
+	* g++.dg/ubsan/pr70847.C: New test.
+	* g++.dg/ubsan/pr71393.C: New test.
+
+2016-06-06  Jakub Jelinek  <jakub@redhat.com>
 
 	PR tree-optimization/71259
 	* gcc.dg/vect/pr71259.c: New test.
diff --git a/gcc/testsuite/g++.dg/opt/pr70847.C b/gcc/testsuite/g++.dg/opt/pr70847.C
new file mode 100644
index 0000000..2b54353
--- /dev/null
+++ b/gcc/testsuite/g++.dg/opt/pr70847.C
@@ -0,0 +1,11 @@
+// PR c++/70847
+// { dg-do compile }
+
+struct D { virtual D& f(); };
+
+void
+g()
+{
+  D d;
+  d.f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f();
+}
diff --git a/gcc/testsuite/g++.dg/ubsan/pr70847.C b/gcc/testsuite/g++.dg/ubsan/pr70847.C
new file mode 100644
index 0000000..2b54353
--- /dev/null
+++ b/gcc/testsuite/g++.dg/ubsan/pr70847.C
@@ -0,0 +1,11 @@
+// PR c++/70847
+// { dg-do compile }
+
+struct D { virtual D& f(); };
+
+void
+g()
+{
+  D d;
+  d.f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f().f();
+}
diff --git a/gcc/testsuite/g++.dg/ubsan/pr71393.C b/gcc/testsuite/g++.dg/ubsan/pr71393.C
new file mode 100644
index 0000000..6011e3a
--- /dev/null
+++ b/gcc/testsuite/g++.dg/ubsan/pr71393.C
@@ -0,0 +1,14 @@
+// PR c++/71393
+// { dg-do compile }
+// { dg-options "-fsanitize=undefined" }
+
+struct B { B &operator << (long); };
+struct A { A (); long a, b, c, d, e, f; };
+
+A::A ()
+{
+  B q;
+  q << 0 << a << 0 << b << 0 << (b / a) << 0 << c << 0 << (c / a) << 0
+    << d << 0 << (d / a) << 0 << e << 0 << (e / a) << 0 << f << 0
+    << (f / a) << 0;
+}