2019-02-01 Richard Biener <rguenther@suse.de>

	PR middle-end/88597
	* tree-scalar-evolution.c (analyze_scalar_evolution): Set up
	the instantiate cache.
	(instantiate_scev_binary): Elide second operand procesing
	if equal to the first.
	* tree-chrec.c (chrec_contains_symbols): Add visited set.
	(chrec_contains_undetermined): Likewise.
	(tree_contains_chrecs): Likewise.

	* gcc.dg/torture/pr88597.c: New testcase.


git-svn-id: https://gcc.gnu.org/svn/gcc/trunk@268449 138bc75d-0d04-0410-961f-82ee72b054a4

5 files changed, 128 insertions, 42 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 37ff9535aca..64d312471e6 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,14 @@
+2019-02-01  Richard Biener  <rguenther@suse.de>
+
+	PR middle-end/88597
+	* tree-scalar-evolution.c (analyze_scalar_evolution): Set up
+	the instantiate cache.
+	(instantiate_scev_binary): Elide second operand procesing
+	if equal to the first.
+	* tree-chrec.c (chrec_contains_symbols): Add visited set.
+	(chrec_contains_undetermined): Likewise.
+	(tree_contains_chrecs): Likewise.
+
 2019-02-01  Jan Hubicka  <hubicka@ucw.cz>
 
 	* parms.def (MAX_INLINE_INSNS_SINGLE): Reduce from 400 to 200.
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index ac31d7d551b..cfcd4ce19bc 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,5 +1,10 @@
 2019-02-01  Richard Biener  <rguenther@suse.de>
 
+	PR middle-end/88597
+	* gcc.dg/torture/pr88597.c: New testcase.
+
+2019-02-01  Richard Biener  <rguenther@suse.de>
+
 	PR tree-optimization/85497
 	* gcc.dg/graphite/pr85497.c: New testcase.
 
diff --git a/gcc/testsuite/gcc.dg/torture/pr88597.c b/gcc/testsuite/gcc.dg/torture/pr88597.c
new file mode 100644
index 00000000000..63ae7b5d6a9
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/pr88597.c
@@ -0,0 +1,19 @@
+/* { dg-do compile } */
+/* { dg-additional-options "-fpeel-loops --param max-completely-peel-times=30" } */
+
+int
+un (int dd)
+{
+  int nz, q8;
+
+  for (nz = 0; nz < 3; ++nz)
+    {
+      int s2;
+
+      q8 = dd;
+      for (s2 = 0; s2 < 28; ++s2)
+	q8 *= q8;
+    }
+
+  return q8;
+}
diff --git a/gcc/tree-chrec.c b/gcc/tree-chrec.c
index a200d973dad..3987041ac19 100644
--- a/gcc/tree-chrec.c
+++ b/gcc/tree-chrec.c
@@ -934,8 +934,8 @@ is_multivariate_chrec (const_tree chrec)
 
 /* Determines whether the chrec contains symbolic names or not.  */
 
-bool
-chrec_contains_symbols (const_tree chrec)
+static bool
+chrec_contains_symbols (const_tree chrec, hash_set<const_tree> &visited)
 {
   int i, n;
 
@@ -954,15 +954,22 @@ chrec_contains_symbols (const_tree chrec)
 
   n = TREE_OPERAND_LENGTH (chrec);
   for (i = 0; i < n; i++)
-    if (chrec_contains_symbols (TREE_OPERAND (chrec, i)))
+    if (chrec_contains_symbols (TREE_OPERAND (chrec, i), visited))
       return true;
   return false;
 }
 
+bool
+chrec_contains_symbols (const_tree chrec)
+{
+  hash_set<const_tree> visited;
+  return chrec_contains_symbols (chrec, visited);
+}
+
 /* Determines whether the chrec contains undetermined coefficients.  */
 
-bool
-chrec_contains_undetermined (const_tree chrec)
+static bool
+chrec_contains_undetermined (const_tree chrec, hash_set<const_tree> &visited)
 {
   int i, n;
 
@@ -972,19 +979,29 @@ chrec_contains_undetermined (const_tree chrec)
   if (chrec == NULL_TREE)
     return false;
 
+  if (visited.add (chrec))
+    return false;
+
   n = TREE_OPERAND_LENGTH (chrec);
   for (i = 0; i < n; i++)
-    if (chrec_contains_undetermined (TREE_OPERAND (chrec, i)))
+    if (chrec_contains_undetermined (TREE_OPERAND (chrec, i), visited))
       return true;
   return false;
 }
 
+bool
+chrec_contains_undetermined (const_tree chrec)
+{
+  hash_set<const_tree> visited;
+  return chrec_contains_undetermined (chrec, visited);
+}
+
 /* Determines whether the tree EXPR contains chrecs, and increment
    SIZE if it is not a NULL pointer by an estimation of the depth of
    the tree.  */
 
-bool
-tree_contains_chrecs (const_tree expr, int *size)
+static bool
+tree_contains_chrecs (const_tree expr, int *size, hash_set<const_tree> &visited)
 {
   int i, n;
 
@@ -999,11 +1016,19 @@ tree_contains_chrecs (const_tree expr, int *size)
 
   n = TREE_OPERAND_LENGTH (expr);
   for (i = 0; i < n; i++)
-    if (tree_contains_chrecs (TREE_OPERAND (expr, i), size))
+    if (tree_contains_chrecs (TREE_OPERAND (expr, i), size, visited))
       return true;
   return false;
 }
 
+bool
+tree_contains_chrecs (const_tree expr, int *size)
+{
+  hash_set<const_tree> visited;
+  return tree_contains_chrecs (expr, size, visited);
+}
+
+
 /* Recursive helper function.  */
 
 static bool
diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c
index de20d278e55..16debb0b34d 100644
--- a/gcc/tree-scalar-evolution.c
+++ b/gcc/tree-scalar-evolution.c
@@ -380,6 +380,37 @@ find_var_scev_info (basic_block instantiated_below, tree var)
   return &res->chrec;
 }
 
+
+/* Hashtable helpers for a temporary hash-table used when
+   analyzing a scalar evolution, instantiating a CHREC or
+   resolving mixers.  */
+
+struct instantiate_cache_type
+{
+  htab_t map;
+  vec<scev_info_str> entries;
+
+  instantiate_cache_type () : map (NULL), entries (vNULL) {}
+  ~instantiate_cache_type ();
+  tree get (unsigned slot) { return entries[slot].chrec; }
+  void set (unsigned slot, tree chrec) { entries[slot].chrec = chrec; }
+};
+
+instantiate_cache_type::~instantiate_cache_type ()
+{
+  if (map != NULL)
+    {
+      htab_delete (map);
+      entries.release ();
+    }
+}
+
+/* Cache to avoid infinite recursion when instantiating an SSA name.
+   Live during the outermost analyze_scalar_evolution, instantiate_scev
+   or resolve_mixers call.  */
+static instantiate_cache_type *global_cache;
+
+
 /* Return true when CHREC contains symbolic names defined in
    LOOP_NB.  */
 
@@ -2117,7 +2148,22 @@ analyze_scalar_evolution (struct loop *loop, tree var)
 
   res = get_scalar_evolution (block_before_loop (loop), var);
   if (res == chrec_not_analyzed_yet)
-    res = analyze_scalar_evolution_1 (loop, var);
+    {
+      /* We'll recurse into instantiate_scev, avoid tearing down the
+         instantiate cache repeatedly and keep it live from here.  */
+      bool destr = false;
+      if (!global_cache)
+	{
+	  global_cache = new instantiate_cache_type;
+	  destr = true;
+	}
+      res = analyze_scalar_evolution_1 (loop, var);
+      if (destr)
+	{
+	  delete global_cache;
+	  global_cache = NULL;
+	}
+    }
 
   if (dump_file && (dump_flags & TDF_SCEV))
     fprintf (dump_file, ")\n");
@@ -2231,34 +2277,6 @@ analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
 }
 
 
-/* Hashtable helpers for a temporary hash-table used when
-   instantiating a CHREC or resolving mixers.  For this use
-   instantiated_below is always the same.  */
-
-struct instantiate_cache_type
-{
-  htab_t map;
-  vec<scev_info_str> entries;
-
-  instantiate_cache_type () : map (NULL), entries (vNULL) {}
-  ~instantiate_cache_type ();
-  tree get (unsigned slot) { return entries[slot].chrec; }
-  void set (unsigned slot, tree chrec) { entries[slot].chrec = chrec; }
-};
-
-instantiate_cache_type::~instantiate_cache_type ()
-{
-  if (map != NULL)
-    {
-      htab_delete (map);
-      entries.release ();
-    }
-}
-
-/* Cache to avoid infinite recursion when instantiating an SSA name.
-   Live during the outermost instantiate_scev or resolve_mixers call.  */
-static instantiate_cache_type *global_cache;
-
 /* Computes a hash function for database element ELT.  */
 
 static inline hashval_t
@@ -2562,10 +2580,18 @@ instantiate_scev_binary (edge instantiate_below,
   if (op0 == chrec_dont_know)
     return chrec_dont_know;
 
-  op1 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop,
-			    c1, fold_conversions, size_expr);
-  if (op1 == chrec_dont_know)
-    return chrec_dont_know;
+  /* While we eventually compute the same op1 if c0 == c1 the process
+     of doing this is expensive so the following short-cut prevents
+     exponential compile-time behavior.  */
+  if (c0 != c1)
+    {
+      op1 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop,
+				c1, fold_conversions, size_expr);
+      if (op1 == chrec_dont_know)
+	return chrec_dont_know;
+    }
+  else
+    op1 = op0;
 
   if (c0 != op0
       || c1 != op1)