From 577d65881ef0f90c790093a7e05cc28a14a45a26 Mon Sep 17 00:00:00 2001 From: Richard Biener Date: Fri, 1 Feb 2019 13:41:43 +0000 Subject: [PATCH] re PR tree-optimization/88597 (Compile time hog w/ -O1 -fpeel-loops) 2019-02-01 Richard Biener 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. From-SVN: r268449 --- gcc/ChangeLog | 11 +++ gcc/testsuite/ChangeLog | 5 ++ gcc/testsuite/gcc.dg/torture/pr88597.c | 19 ++++++ gcc/tree-chrec.c | 43 +++++++++--- gcc/tree-scalar-evolution.c | 92 +++++++++++++++++--------- 5 files changed, 128 insertions(+), 42 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/torture/pr88597.c 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 + + 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 * 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,3 +1,8 @@ +2019-02-01 Richard Biener + + PR middle-end/88597 + * gcc.dg/torture/pr88597.c: New testcase. + 2019-02-01 Richard Biener PR tree-optimization/85497 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 &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 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 &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 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 &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 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 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 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) -- 2.30.2