diff options
Diffstat (limited to 'gcc')
| -rw-r--r-- | gcc/ChangeLog | 14 | ||||
| -rw-r--r-- | gcc/testsuite/ChangeLog | 6 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/loop-bound-2.c | 23 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/loop-bound-4.c | 23 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/loop-bound-6.c | 23 | ||||
| -rw-r--r-- | gcc/tree-scalar-evolution.c | 82 | ||||
| -rw-r--r-- | gcc/tree-ssa-loop-niter.c | 195 | ||||
| -rw-r--r-- | gcc/tree-ssa-loop-niter.h | 2 |
8 files changed, 234 insertions, 134 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 376b642..435e279 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,17 @@ +2015-09-17 Bin Cheng <bin.cheng@arm.com> + + * tree-ssa-loop-niter.c (tree_simplify_using_condition_1): New + parameter. + (tree_simplify_using_condition): Ditto. + (simplify_using_initial_conditions): Ditto. + (loop_exits_before_overflow): Pass new argument to function + simplify_using_initial_conditions. Remove case for type conversions + simplification. + * tree-ssa-loop-niter.h (simplify_using_initial_conditions): New + parameter. + * tree-scalar-evolution.c (simple_iv): Simplify type conversions + in iv base using loop initial conditions. + 2015-09-16 Jeff Law <law@redhat.com> PR tree-optimization/47679 diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 14ca461..bea9258 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,9 @@ +2015-09-17 Bin Cheng <bin.cheng@arm.com> + + * gcc.dg/tree-ssa/loop-bound-2.c: New test. + * gcc.dg/tree-ssa/loop-bound-4.c: New test. + * gcc.dg/tree-ssa/loop-bound-6.c: New test. + 2015-09-16 John Marino <gnugcc@marino.st> * gfortran.dg/read_dir.f90: XFAIL this testcase on DragonFly. diff --git a/gcc/testsuite/gcc.dg/tree-ssa/loop-bound-2.c b/gcc/testsuite/gcc.dg/tree-ssa/loop-bound-2.c new file mode 100644 index 0000000..802dd29 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/loop-bound-2.c @@ -0,0 +1,23 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-ivopts-details" } */ + +int *a; + +int +foo (signed char s, signed char l) +{ + signed char i; + int sum = 0; + + for (i = s; i < l; i++) + { + sum += a[i]; + } + + return sum; +} + +/* Check loop niter bound information. */ +/* { dg-final { scan-tree-dump "bounded by 254" "ivopts" } } */ +/* { dg-final { scan-tree-dump-not "bounded by 255" "ivopts" } } */ +/* { dg-final { scan-tree-dump-not "zero if " "ivopts" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/loop-bound-4.c b/gcc/testsuite/gcc.dg/tree-ssa/loop-bound-4.c new file mode 100644 index 0000000..b9d7d41 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/loop-bound-4.c @@ -0,0 +1,23 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-ivopts-details" } */ + +int *a; + +int +foo (signed char s, signed char l) +{ + signed char i; + int sum = 0; + + for (i = s; i > l; i--) + { + sum += a[i]; + } + + return sum; +} + +/* Check loop niter bound information. */ +/* { dg-final { scan-tree-dump "bounded by 254" "ivopts" } } */ +/* { dg-final { scan-tree-dump-not "bounded by 255" "ivopts" } } */ +/* { dg-final { scan-tree-dump-not "zero if " "ivopts" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/loop-bound-6.c b/gcc/testsuite/gcc.dg/tree-ssa/loop-bound-6.c new file mode 100644 index 0000000..8319434 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/loop-bound-6.c @@ -0,0 +1,23 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-ivopts-details" } */ + +int *a; + +int +foo (signed char s) +{ + signed char i; + int sum = 0; + + for (i = s; i > 0; i--) + { + sum += a[i]; + } + + return sum; +} + +/* Check loop niter bound information. */ +/* { dg-final { scan-tree-dump "bounded by 126" "ivopts" } } */ +/* { dg-final { scan-tree-dump-not "bounded by 127" "ivopts" } } */ +/* { dg-final { scan-tree-dump-not "zero if " "ivopts" } } */ diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index 54fe223..328846b 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -3234,8 +3234,10 @@ bool simple_iv (struct loop *wrto_loop, struct loop *use_loop, tree op, affine_iv *iv, bool allow_nonconstant_step) { - tree type, ev; - bool folded_casts; + enum tree_code code; + tree type, ev, base, e, stop; + wide_int extreme; + bool folded_casts, overflow; iv->base = NULL_TREE; iv->step = NULL_TREE; @@ -3276,6 +3278,82 @@ simple_iv (struct loop *wrto_loop, struct loop *use_loop, tree op, iv->no_overflow = (!folded_casts && ANY_INTEGRAL_TYPE_P (type) && TYPE_OVERFLOW_UNDEFINED (type)); + /* Try to simplify iv base: + + (signed T) ((unsigned T)base + step) ;; TREE_TYPE (base) == signed T + == (signed T)(unsigned T)base + step + == base + step + + If we can prove operation (base + step) doesn't overflow or underflow. + Specifically, we try to prove below conditions are satisfied: + + base <= UPPER_BOUND (type) - step ;;step > 0 + base >= LOWER_BOUND (type) - step ;;step < 0 + + This is done by proving the reverse conditions are false using loop's + initial conditions. + + The is necessary to make loop niter, or iv overflow analysis easier + for below example: + + int foo (int *a, signed char s, signed char l) + { + signed char i; + for (i = s; i < l; i++) + a[i] = 0; + return 0; + } + + Note variable I is firstly converted to type unsigned char, incremented, + then converted back to type signed char. */ + + if (wrto_loop->num != use_loop->num) + return true; + + if (!CONVERT_EXPR_P (iv->base) || TREE_CODE (iv->step) != INTEGER_CST) + return true; + + type = TREE_TYPE (iv->base); + e = TREE_OPERAND (iv->base, 0); + if (TREE_CODE (e) != PLUS_EXPR + || TREE_CODE (TREE_OPERAND (e, 1)) != INTEGER_CST + || !tree_int_cst_equal (iv->step, + fold_convert (type, TREE_OPERAND (e, 1)))) + return true; + e = TREE_OPERAND (e, 0); + if (!CONVERT_EXPR_P (e)) + return true; + base = TREE_OPERAND (e, 0); + if (!useless_type_conversion_p (type, TREE_TYPE (base))) + return true; + + if (tree_int_cst_sign_bit (iv->step)) + { + code = LT_EXPR; + extreme = wi::min_value (type); + } + else + { + code = GT_EXPR; + extreme = wi::max_value (type); + } + overflow = false; + extreme = wi::sub (extreme, iv->step, TYPE_SIGN (type), &overflow); + if (overflow) + return true; + e = fold_build2 (code, boolean_type_node, base, + wide_int_to_tree (type, extreme)); + stop = (TREE_CODE (base) == SSA_NAME) ? base : NULL; + e = simplify_using_initial_conditions (use_loop, e, stop); + if (!integer_zerop (e)) + return true; + + if (POINTER_TYPE_P (TREE_TYPE (base))) + code = POINTER_PLUS_EXPR; + else + code = PLUS_EXPR; + + iv->base = fold_build2 (code, TREE_TYPE (base), base, iv->step); return true; } diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c index 39d6807..0309f4a 100644 --- a/gcc/tree-ssa-loop-niter.c +++ b/gcc/tree-ssa-loop-niter.c @@ -1926,7 +1926,7 @@ expand_simple_operations (tree expr, tree stop) expression (or EXPR unchanged, if no simplification was possible). */ static tree -tree_simplify_using_condition_1 (tree cond, tree expr) +tree_simplify_using_condition_1 (tree cond, tree expr, tree stop) { bool changed; tree e, te, e0, e1, e2, notcond; @@ -1941,17 +1941,17 @@ tree_simplify_using_condition_1 (tree cond, tree expr) { changed = false; - e0 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 0)); + e0 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 0), stop); if (TREE_OPERAND (expr, 0) != e0) changed = true; - e1 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 1)); + e1 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 1), stop); if (TREE_OPERAND (expr, 1) != e1) changed = true; if (code == COND_EXPR) { - e2 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 2)); + e2 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 2), stop); if (TREE_OPERAND (expr, 2) != e2) changed = true; } @@ -2014,7 +2014,7 @@ tree_simplify_using_condition_1 (tree cond, tree expr) return boolean_true_node; } - te = expand_simple_operations (expr); + te = expand_simple_operations (expr, stop); /* Check whether COND ==> EXPR. */ notcond = invert_truthvalue (cond); @@ -2038,19 +2038,19 @@ tree_simplify_using_condition_1 (tree cond, tree expr) the loop do not cause us to fail. */ static tree -tree_simplify_using_condition (tree cond, tree expr) +tree_simplify_using_condition (tree cond, tree expr, tree stop) { - cond = expand_simple_operations (cond); + cond = expand_simple_operations (cond, stop); - return tree_simplify_using_condition_1 (cond, expr); + return tree_simplify_using_condition_1 (cond, expr, stop); } /* Tries to simplify EXPR using the conditions on entry to LOOP. Returns the simplified expression (or EXPR unchanged, if no - simplification was possible).*/ + simplification was possible). */ -static tree -simplify_using_initial_conditions (struct loop *loop, tree expr) +tree +simplify_using_initial_conditions (struct loop *loop, tree expr, tree stop) { edge e; basic_block bb; @@ -2082,7 +2082,7 @@ simplify_using_initial_conditions (struct loop *loop, tree expr) gimple_cond_rhs (stmt)); if (e->flags & EDGE_FALSE_VALUE) cond = invert_truthvalue (cond); - expr = tree_simplify_using_condition (cond, expr); + expr = tree_simplify_using_condition (cond, expr, stop); /* Break if EXPR is simplified to const values. */ if (expr && (integer_zerop (expr) || integer_nonzerop (expr))) break; @@ -4114,137 +4114,68 @@ loop_exits_before_overflow (tree base, tree step, help of analyzed loop control IV. This is done only for IVs with constant step because otherwise we don't have the information. */ if (TREE_CODE (step) == INTEGER_CST) - for (civ = loop->control_ivs; civ; civ = civ->next) - { - enum tree_code code; - tree stepped, extreme, civ_type = TREE_TYPE (civ->step); - - /* Have to consider type difference because operand_equal_p ignores - that for constants. */ - if (TYPE_UNSIGNED (type) != TYPE_UNSIGNED (civ_type) - || element_precision (type) != element_precision (civ_type)) - continue; - - /* Only consider control IV with same step. */ - if (!operand_equal_p (step, civ->step, 0)) - continue; - - /* Done proving if this is a no-overflow control IV. */ - if (operand_equal_p (base, civ->base, 0)) - return true; - - /* If this is a before stepping control IV, in other words, we have - - {civ_base, step} = {base + step, step} - - Because civ {base + step, step} doesn't overflow during loop - iterations, {base, step} will not overflow if we can prove the - operation "base + step" does not overflow. Specifically, we try - to prove below conditions are satisfied: - - base <= UPPER_BOUND (type) - step ;;step > 0 - base >= LOWER_BOUND (type) - step ;;step < 0 - - by proving the reverse conditions are false using loop's initial - condition. */ - if (POINTER_TYPE_P (TREE_TYPE (base))) - code = POINTER_PLUS_EXPR; - else - code = PLUS_EXPR; + { + tree stop = (TREE_CODE (base) == SSA_NAME) ? base : NULL; - stepped = fold_build2 (code, TREE_TYPE (base), base, step); - if (operand_equal_p (stepped, civ->base, 0)) - { - if (tree_int_cst_sign_bit (step)) - { - code = LT_EXPR; - extreme = lower_bound_in_type (type, type); - } - else - { - code = GT_EXPR; - extreme = upper_bound_in_type (type, type); - } - extreme = fold_build2 (MINUS_EXPR, type, extreme, step); - e = fold_build2 (code, boolean_type_node, base, extreme); - e = simplify_using_initial_conditions (loop, e); - if (integer_zerop (e)) - return true; + for (civ = loop->control_ivs; civ; civ = civ->next) + { + enum tree_code code; + tree stepped, extreme, civ_type = TREE_TYPE (civ->step); + /* Have to consider type difference because operand_equal_p ignores + that for constants. */ + if (TYPE_UNSIGNED (type) != TYPE_UNSIGNED (civ_type) + || element_precision (type) != element_precision (civ_type)) continue; - } - - /* Similar to above, only in this case we have: - - {civ_base, step} = {(signed T)((unsigned T)base + step), step} - && TREE_TYPE (civ_base) = signed T. - - We prove that below condition is satisfied: - - (signed T)((unsigned T)base + step) - == (signed T)(unsigned T)base + step - == base + step - because of exact the same reason as above. This also proves - there is no overflow in the operation "base + step", thus the - induction variable {base, step} during loop iterations. + /* Only consider control IV with same step. */ + if (!operand_equal_p (step, civ->step, 0)) + continue; - This is necessary to handle cases as below: + /* Done proving if this is a no-overflow control IV. */ + if (operand_equal_p (base, civ->base, 0)) + return true; - int foo (int *a, signed char s, signed char l) - { - signed char i; - for (i = s; i < l; i++) - a[i] = 0; - return 0; - } + /* If this is a before stepping control IV, in other words, we have - The variable I is firstly converted to type unsigned char, - incremented, then converted back to type signed char. */ - if (!CONVERT_EXPR_P (civ->base) || TREE_TYPE (civ->base) != type) - continue; - e = TREE_OPERAND (civ->base, 0); - if (TREE_CODE (e) != PLUS_EXPR - || TREE_CODE (TREE_OPERAND (e, 1)) != INTEGER_CST - || !operand_equal_p (step, - fold_convert (type, - TREE_OPERAND (e, 1)), 0)) - continue; - e = TREE_OPERAND (e, 0); - if (!CONVERT_EXPR_P (e) || !operand_equal_p (e, unsigned_base, 0)) - continue; - e = TREE_OPERAND (e, 0); - /* It may still be possible to prove no overflow even if condition - "operand_equal_p (e, base, 0)" isn't satisfied here, like below - example: + {civ_base, step} = {base + step, step} - e : ssa_var ; unsigned long type - base : (int) ssa_var - unsigned_base : (unsigned int) ssa_var + Because civ {base + step, step} doesn't overflow during loop + iterations, {base, step} will not overflow if we can prove the + operation "base + step" does not overflow. Specifically, we try + to prove below conditions are satisfied: - Unfortunately this is a rare case observed during GCC profiled - bootstrap. See PR66638 for more information. + base <= UPPER_BOUND (type) - step ;;step > 0 + base >= LOWER_BOUND (type) - step ;;step < 0 - For now, we just skip the possibility. */ - if (!operand_equal_p (e, base, 0)) - continue; + by proving the reverse conditions are false using loop's initial + condition. */ + if (POINTER_TYPE_P (TREE_TYPE (base))) + code = POINTER_PLUS_EXPR; + else + code = PLUS_EXPR; - if (tree_int_cst_sign_bit (step)) - { - code = LT_EXPR; - extreme = lower_bound_in_type (type, type); - } - else - { - code = GT_EXPR; - extreme = upper_bound_in_type (type, type); - } - extreme = fold_build2 (MINUS_EXPR, type, extreme, step); - e = fold_build2 (code, boolean_type_node, base, extreme); - e = simplify_using_initial_conditions (loop, e); - if (integer_zerop (e)) - return true; - } + stepped = fold_build2 (code, TREE_TYPE (base), base, step); + if (operand_equal_p (stepped, civ->base, 0)) + { + if (tree_int_cst_sign_bit (step)) + { + code = LT_EXPR; + extreme = lower_bound_in_type (type, type); + } + else + { + code = GT_EXPR; + extreme = upper_bound_in_type (type, type); + } + extreme = fold_build2 (MINUS_EXPR, type, extreme, step); + e = fold_build2 (code, boolean_type_node, base, extreme); + e = simplify_using_initial_conditions (loop, e, stop); + if (integer_zerop (e)) + return true; + } + } + } return false; } diff --git a/gcc/tree-ssa-loop-niter.h b/gcc/tree-ssa-loop-niter.h index 8d4f799..1442fe9 100644 --- a/gcc/tree-ssa-loop-niter.h +++ b/gcc/tree-ssa-loop-niter.h @@ -21,6 +21,8 @@ along with GCC; see the file COPYING3. If not see #define GCC_TREE_SSA_LOOP_NITER_H extern tree expand_simple_operations (tree, tree = NULL); +extern tree simplify_using_initial_conditions (struct loop *, + tree, tree = NULL); extern bool loop_only_exit_p (const struct loop *, const_edge); extern bool number_of_iterations_exit (struct loop *, edge, struct tree_niter_desc *niter, bool, |