From 5fd8a9cb5b0e95af7f833f8dfe62ce5b9d435846 Mon Sep 17 00:00:00 2001 From: Richard Biener Date: Tue, 4 Jun 2019 09:05:10 +0000 Subject: [PATCH] re PR middle-end/90726 (exponential behavior on SCEV results everywhere) 2019-06-04 Richard Biener PR middle-end/90726 * tree-chrec.c (chrec_contains_symbols): Add to visited. (tree_contains_chrecs): Likewise. (chrec_contains_symbols_defined_in_loop): Move here and avoid exponential behaivor from ... * tree-scalar-evolution.c (chrec_contains_symbols_defined_in_loop): ... here. (expression_expensive_p): Avoid exponential behavior and compute expanded size, rejecting any expansion. * tree-ssa-loop-ivopts.c (abnormal_ssa_name_p): Remove. (idx_contains_abnormal_ssa_name_p): Likewise. (contains_abnormal_ssa_name_p_1): New helper for walk_tree. (contains_abnormal_ssa_name_p): Simplify and use walk_tree_without_duplicates. * gcc.dg/pr90726.c: New testcase. From-SVN: r271903 --- gcc/ChangeLog | 17 +++++ gcc/testsuite/ChangeLog | 5 ++ gcc/testsuite/gcc.dg/pr90726.c | 56 +++++++++++++++++ gcc/tree-chrec.c | 65 +++++++++++++++++++ gcc/tree-scalar-evolution.c | 110 ++++++++++++++++----------------- gcc/tree-ssa-loop-ivopts.c | 92 ++++----------------------- 6 files changed, 206 insertions(+), 139 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/pr90726.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 80d01ad526d..d4d020b7fe8 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,20 @@ +2019-06-04 Richard Biener + + PR middle-end/90726 + * tree-chrec.c (chrec_contains_symbols): Add to visited. + (tree_contains_chrecs): Likewise. + (chrec_contains_symbols_defined_in_loop): Move here and avoid + exponential behaivor from ... + * tree-scalar-evolution.c (chrec_contains_symbols_defined_in_loop): + ... here. + (expression_expensive_p): Avoid exponential behavior and compute + expanded size, rejecting any expansion. + * tree-ssa-loop-ivopts.c (abnormal_ssa_name_p): Remove. + (idx_contains_abnormal_ssa_name_p): Likewise. + (contains_abnormal_ssa_name_p_1): New helper for walk_tree. + (contains_abnormal_ssa_name_p): Simplify and use + walk_tree_without_duplicates. + 2019-06-04 Richard Biener PR tree-optimization/90738 diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 554bd22a66e..8b3e36066da 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,8 @@ +2019-06-04 Richard Biener + + PR middle-end/90726 + * gcc.dg/pr90726.c: New testcase. + 2019-06-04 Richard Biener PR tree-optimization/90738 diff --git a/gcc/testsuite/gcc.dg/pr90726.c b/gcc/testsuite/gcc.dg/pr90726.c new file mode 100644 index 00000000000..acdb0fe7efc --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr90726.c @@ -0,0 +1,56 @@ +/* { dg-do compile } */ +/* { dg-options "-fgimple -O2 -fno-ivopts" } */ + +int __GIMPLE (ssa,guessed_local(12348030),startwith("fix_loops")) +un (int dd) +{ + int s2; + int q8; + int nz; + + __BB(2,guessed_local(12348030)): + goto __BB3(guessed(134217728)); + + __BB(3,loop_header(1),guessed_local(37044096)): + nz_7 = __PHI (__BB2: 0, __BB5: nz_10); + q8_13 = dd_9(D) * dd_9(D); + q8_17 = q8_13 * q8_13; + q8_21 = q8_17 * q8_17; + q8_25 = q8_21 * q8_21; + q8_29 = q8_25 * q8_25; + q8_33 = q8_29 * q8_29; + q8_37 = q8_33 * q8_33; + q8_41 = q8_37 * q8_37; + q8_45 = q8_41 * q8_41; + q8_49 = q8_45 * q8_45; + q8_53 = q8_49 * q8_49; + q8_57 = q8_53 * q8_53; + q8_61 = q8_57 * q8_57; + q8_65 = q8_61 * q8_61; + q8_69 = q8_65 * q8_65; + q8_73 = q8_69 * q8_69; + q8_77 = q8_73 * q8_73; + q8_81 = q8_77 * q8_77; + q8_85 = q8_81 * q8_81; + q8_89 = q8_85 * q8_85; + q8_93 = q8_89 * q8_89; + q8_97 = q8_93 * q8_93; + q8_101 = q8_97 * q8_97; + q8_105 = q8_101 * q8_101; + q8_109 = q8_105 * q8_105; + q8_113 = q8_109 * q8_109; + q8_117 = q8_113 * q8_113; + q8_121 = q8_117 * q8_117; + nz_10 = nz_7 + 1; + if (nz_10 != 3) + goto __BB5(guessed(89478485)); + else + goto __BB4(guessed(44739243)); + + __BB(5,guessed_local(24696064)): + goto __BB3(precise(134217728)); + + __BB(4,guessed_local(12348031)): + return q8_121; + +} diff --git a/gcc/tree-chrec.c b/gcc/tree-chrec.c index 813b87fd00b..f50fd2012e1 100644 --- a/gcc/tree-chrec.c +++ b/gcc/tree-chrec.c @@ -35,6 +35,8 @@ along with GCC; see the file COPYING3. If not see #include "tree-ssa-loop-ivopts.h" #include "tree-ssa-loop-niter.h" #include "tree-chrec.h" +#include "gimple.h" +#include "tree-ssa-loop.h" #include "dumpfile.h" #include "params.h" #include "tree-scalar-evolution.h" @@ -959,6 +961,9 @@ chrec_contains_symbols (const_tree chrec, hash_set &visited, && flow_loop_nested_p (get_chrec_loop (chrec), loop)) return true; + if (visited.add (chrec)) + return false; + n = TREE_OPERAND_LENGTH (chrec); for (i = 0; i < n; i++) if (chrec_contains_symbols (TREE_OPERAND (chrec, i), visited, loop)) @@ -978,6 +983,63 @@ chrec_contains_symbols (const_tree chrec, struct loop* loop) return chrec_contains_symbols (chrec, visited, loop); } +/* Return true when CHREC contains symbolic names defined in + LOOP_NB. */ + +static bool +chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb, + hash_set &visited) +{ + int i, n; + + if (chrec == NULL_TREE) + return false; + + if (is_gimple_min_invariant (chrec)) + return false; + + if (TREE_CODE (chrec) == SSA_NAME) + { + gimple *def; + loop_p def_loop, loop; + + if (SSA_NAME_IS_DEFAULT_DEF (chrec)) + return false; + + def = SSA_NAME_DEF_STMT (chrec); + def_loop = loop_containing_stmt (def); + loop = get_loop (cfun, loop_nb); + + if (def_loop == NULL) + return false; + + if (loop == def_loop || flow_loop_nested_p (loop, def_loop)) + return true; + + return false; + } + + if (visited.add (chrec)) + return false; + + n = TREE_OPERAND_LENGTH (chrec); + for (i = 0; i < n; i++) + if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i), + loop_nb, visited)) + return true; + return false; +} + +/* Return true when CHREC contains symbolic names defined in + LOOP_NB. */ + +bool +chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb) +{ + hash_set visited; + return chrec_contains_symbols_defined_in_loop (chrec, loop_nb, visited); +} + /* Determines whether the chrec contains undetermined coefficients. */ static bool @@ -1026,6 +1088,9 @@ tree_contains_chrecs (const_tree expr, int *size, hash_set &visited) if (tree_is_chrec (expr)) return true; + if (visited.add (expr)) + return false; + n = TREE_OPERAND_LENGTH (expr); for (i = 0; i < n; i++) if (tree_contains_chrecs (TREE_OPERAND (expr, i), size, visited)) diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index c814437c239..0bda94ab325 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -411,49 +411,6 @@ instantiate_cache_type::~instantiate_cache_type () static instantiate_cache_type *global_cache; -/* Return true when CHREC contains symbolic names defined in - LOOP_NB. */ - -bool -chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb) -{ - int i, n; - - if (chrec == NULL_TREE) - return false; - - if (is_gimple_min_invariant (chrec)) - return false; - - if (TREE_CODE (chrec) == SSA_NAME) - { - gimple *def; - loop_p def_loop, loop; - - if (SSA_NAME_IS_DEFAULT_DEF (chrec)) - return false; - - def = SSA_NAME_DEF_STMT (chrec); - def_loop = loop_containing_stmt (def); - loop = get_loop (cfun, loop_nb); - - if (def_loop == NULL) - return false; - - if (loop == def_loop || flow_loop_nested_p (loop, def_loop)) - return true; - - return false; - } - - n = TREE_OPERAND_LENGTH (chrec); - for (i = 0; i < n; i++) - if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i), - loop_nb)) - return true; - return false; -} - /* Return true when PHI is a loop-phi-node. */ static bool @@ -3505,8 +3462,9 @@ scev_finalize (void) /* Returns true if the expression EXPR is considered to be too expensive for scev_const_prop. */ -bool -expression_expensive_p (tree expr) +static bool +expression_expensive_p (tree expr, hash_map &cache, + uint64_t &cost) { enum tree_code code; @@ -3530,6 +3488,19 @@ expression_expensive_p (tree expr) return true; } + bool visited_p; + uint64_t &local_cost = cache.get_or_insert (expr, &visited_p); + if (visited_p) + { + uint64_t tem = cost + local_cost; + if (tem < cost) + return true; + cost = tem; + return false; + } + local_cost = 1; + + uint64_t op_cost = 0; if (code == CALL_EXPR) { tree arg; @@ -3568,39 +3539,62 @@ expression_expensive_p (tree expr) if (!is_inexpensive_builtin (get_callee_fndecl (expr))) return true; FOR_EACH_CALL_EXPR_ARG (arg, iter, expr) - if (expression_expensive_p (arg)) + if (expression_expensive_p (arg, cache, op_cost)) return true; + *cache.get (expr) += op_cost; + cost += op_cost + 1; return false; } if (code == COND_EXPR) - return (expression_expensive_p (TREE_OPERAND (expr, 0)) - || (EXPR_P (TREE_OPERAND (expr, 1)) - && EXPR_P (TREE_OPERAND (expr, 2))) - /* If either branch has side effects or could trap. */ - || TREE_SIDE_EFFECTS (TREE_OPERAND (expr, 1)) - || generic_expr_could_trap_p (TREE_OPERAND (expr, 1)) - || TREE_SIDE_EFFECTS (TREE_OPERAND (expr, 0)) - || generic_expr_could_trap_p (TREE_OPERAND (expr, 0)) - || expression_expensive_p (TREE_OPERAND (expr, 1)) - || expression_expensive_p (TREE_OPERAND (expr, 2))); + { + if (expression_expensive_p (TREE_OPERAND (expr, 0), cache, op_cost) + || (EXPR_P (TREE_OPERAND (expr, 1)) + && EXPR_P (TREE_OPERAND (expr, 2))) + /* If either branch has side effects or could trap. */ + || TREE_SIDE_EFFECTS (TREE_OPERAND (expr, 1)) + || generic_expr_could_trap_p (TREE_OPERAND (expr, 1)) + || TREE_SIDE_EFFECTS (TREE_OPERAND (expr, 0)) + || generic_expr_could_trap_p (TREE_OPERAND (expr, 0)) + || expression_expensive_p (TREE_OPERAND (expr, 1), + cache, op_cost) + || expression_expensive_p (TREE_OPERAND (expr, 2), + cache, op_cost)) + return true; + *cache.get (expr) += op_cost; + cost += op_cost + 1; + return false; + } switch (TREE_CODE_CLASS (code)) { case tcc_binary: case tcc_comparison: - if (expression_expensive_p (TREE_OPERAND (expr, 1))) + if (expression_expensive_p (TREE_OPERAND (expr, 1), cache, op_cost)) return true; /* Fallthru. */ case tcc_unary: - return expression_expensive_p (TREE_OPERAND (expr, 0)); + if (expression_expensive_p (TREE_OPERAND (expr, 0), cache, op_cost)) + return true; + *cache.get (expr) += op_cost; + cost += op_cost + 1; + return false; default: return true; } } +bool +expression_expensive_p (tree expr) +{ + hash_map cache; + uint64_t expanded_size = 0; + return (expression_expensive_p (expr, cache, expanded_size) + || expanded_size > cache.elements ()); +} + /* Do final value replacement for LOOP, return true if we did anything. */ bool diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c index 9864b59ccfc..890f9b788b4 100644 --- a/gcc/tree-ssa-loop-ivopts.c +++ b/gcc/tree-ssa-loop-ivopts.c @@ -944,36 +944,19 @@ stmt_after_increment (struct loop *loop, struct iv_cand *cand, gimple *stmt) } } -/* Returns true if EXP is a ssa name that occurs in an abnormal phi node. */ +/* walk_tree callback for contains_abnormal_ssa_name_p. */ -static bool -abnormal_ssa_name_p (tree exp) +static tree +contains_abnormal_ssa_name_p_1 (tree *tp, int *walk_subtrees, void *) { - if (!exp) - return false; - - if (TREE_CODE (exp) != SSA_NAME) - return false; - - return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp) != 0; -} + if (TREE_CODE (*tp) == SSA_NAME + && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (*tp)) + return *tp; -/* Returns false if BASE or INDEX contains a ssa name that occurs in an - abnormal phi node. Callback for for_each_index. */ + if (!EXPR_P (*tp)) + *walk_subtrees = 0; -static bool -idx_contains_abnormal_ssa_name_p (tree base, tree *index, - void *data ATTRIBUTE_UNUSED) -{ - if (TREE_CODE (base) == ARRAY_REF || TREE_CODE (base) == ARRAY_RANGE_REF) - { - if (abnormal_ssa_name_p (TREE_OPERAND (base, 2))) - return false; - if (abnormal_ssa_name_p (TREE_OPERAND (base, 3))) - return false; - } - - return !abnormal_ssa_name_p (*index); + return NULL_TREE; } /* Returns true if EXPR contains a ssa name that occurs in an @@ -982,61 +965,8 @@ idx_contains_abnormal_ssa_name_p (tree base, tree *index, bool contains_abnormal_ssa_name_p (tree expr) { - enum tree_code code; - enum tree_code_class codeclass; - - if (!expr) - return false; - - code = TREE_CODE (expr); - codeclass = TREE_CODE_CLASS (code); - - if (code == CALL_EXPR) - { - tree arg; - call_expr_arg_iterator iter; - FOR_EACH_CALL_EXPR_ARG (arg, iter, expr) - if (contains_abnormal_ssa_name_p (arg)) - return true; - return false; - } - - if (code == SSA_NAME) - return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (expr) != 0; - - if (code == INTEGER_CST - || is_gimple_min_invariant (expr)) - return false; - - if (code == ADDR_EXPR) - return !for_each_index (&TREE_OPERAND (expr, 0), - idx_contains_abnormal_ssa_name_p, - NULL); - - if (code == COND_EXPR) - return contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 0)) - || contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 1)) - || contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 2)); - - switch (codeclass) - { - case tcc_binary: - case tcc_comparison: - if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 1))) - return true; - - /* Fallthru. */ - case tcc_unary: - if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 0))) - return true; - - break; - - default: - gcc_unreachable (); - } - - return false; + return walk_tree_without_duplicates + (&expr, contains_abnormal_ssa_name_p_1, NULL) != NULL_TREE; } /* Returns the structure describing number of iterations determined from -- 2.30.2