The following fixes the compile-time explosion for the PR88597
testcase. The fix isn't really "complete" but as usual I'd like
to see testcases for other cases. I've queued a more complete
fix for GCC 10. The issue is exponential work done by
SCEV instantiation which eventually hits "cached" but needs to
dive down the whole GENERIC tree it is fed. So the new short-cut
in instantiate_scev_binary is the weak part of the fix.
The chrec_contains_undetermined fix is required to not blow up
there since CHRECs happily (and luckily!) exploit tree sharing
to limit their size but these simple recursive functions do
not expect to be fed a graph. (there's some more functions
with the same issue not fixed with this patch)
Bootstrap & regtest running on x86_64-unknown-linux-gnu.
Richard.
2019-02-01 Richard Biener <rguent...@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.
Index: gcc/tree-scalar-evolution.c
===================================================================
--- gcc/tree-scalar-evolution.c (revision 268446)
+++ gcc/tree-scalar-evolution.c (working copy)
@@ -380,6 +380,37 @@ find_var_scev_info (basic_block instanti
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 *l
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
}
-/* 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 instantiat
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)
Index: gcc/tree-chrec.c
===================================================================
--- gcc/tree-chrec.c (revision 268446)
+++ gcc/tree-chrec.c (working copy)
@@ -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
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, i
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
Index: gcc/testsuite/gcc.dg/torture/pr88597.c
===================================================================
--- gcc/testsuite/gcc.dg/torture/pr88597.c (nonexistent)
+++ gcc/testsuite/gcc.dg/torture/pr88597.c (working copy)
@@ -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;
+}
