===================================================================
@@ -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)
===================================================================
@@ -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
===================================================================
@@ -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;
+}