diff options
-rw-r--r-- | gcc/ChangeLog | 11 | ||||
-rw-r--r-- | gcc/testsuite/ChangeLog | 5 | ||||
-rw-r--r-- | gcc/testsuite/gcc.dg/torture/pr88597.c | 19 | ||||
-rw-r--r-- | gcc/tree-chrec.c | 43 | ||||
-rw-r--r-- | gcc/tree-scalar-evolution.c | 92 |
5 files changed, 128 insertions, 42 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 37ff953..64d3124 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 ac31d7d..cfcd4ce 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 0000000..63ae7b5 --- /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 a200d97..3987041 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 de20d27..16debb0 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) |