From b24d94207914fb8695bd7307187a5a0bfcddc8c2 Mon Sep 17 00:00:00 2001 From: Bin Cheng Date: Thu, 21 Jul 2016 10:52:13 +0000 Subject: [PATCH] tree-chrec.c (convert_affine_scev): New parameter. * tree-chrec.c (convert_affine_scev): New parameter. Pass new arg. (chrec_convert_1, chrec_convert): Ditto. * tree-chrec.h (chrec_convert, convert_affine_scev): New parameter. * tree-scalar-evolution.c (interpret_rhs_expr): Pass new arg. * tree-vrp.c (adjust_range_with_scev): Ditto. * tree-ssa-loop-niter.c (idx_infer_loop_bounds): Ditto. (scev_var_range_cant_overflow): New function. (scev_probably_wraps_p): New parameter. Call above function. * tree-ssa-loop-niter.h (scev_probably_wraps_p): New parameter. gcc/testsuite * gcc.dg/tree-ssa/scev-15.c: New. From-SVN: r238586 --- gcc/ChangeLog | 12 +++ gcc/testsuite/ChangeLog | 4 + gcc/testsuite/gcc.dg/tree-ssa/scev-15.c | 18 ++++ gcc/tree-chrec.c | 40 +++++---- gcc/tree-chrec.h | 4 +- gcc/tree-scalar-evolution.c | 2 +- gcc/tree-ssa-loop-niter.c | 113 +++++++++++++++++++++++- gcc/tree-ssa-loop-niter.h | 3 +- gcc/tree-vrp.c | 4 +- 9 files changed, 174 insertions(+), 26 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/scev-15.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 1082405fdff..be5662a3a5e 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,15 @@ +2016-07-21 Bin Cheng + + * tree-chrec.c (convert_affine_scev): New parameter. Pass new arg. + (chrec_convert_1, chrec_convert): Ditto. + * tree-chrec.h (chrec_convert, convert_affine_scev): New parameter. + * tree-scalar-evolution.c (interpret_rhs_expr): Pass new arg. + * tree-vrp.c (adjust_range_with_scev): Ditto. + * tree-ssa-loop-niter.c (idx_infer_loop_bounds): Ditto. + (scev_var_range_cant_overflow): New function. + (scev_probably_wraps_p): New parameter. Call above function. + * tree-ssa-loop-niter.h (scev_probably_wraps_p): New parameter. + 2016-07-21 Bin Cheng * tree-ssa-loop-niter.c (number_of_iterations_lt_to_ne): Clean up diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 23303fe7e52..61b6fa90051 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,7 @@ +2016-07-21 Bin Cheng + + * gcc.dg/tree-ssa/scev-15.c: New. + 2016-07-21 Bin Cheng * gcc.dg/vect/vect-mask-store-move-1.c: XFAIL. diff --git a/gcc/testsuite/gcc.dg/tree-ssa/scev-15.c b/gcc/testsuite/gcc.dg/tree-ssa/scev-15.c new file mode 100644 index 00000000000..a0d2e595e98 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/scev-15.c @@ -0,0 +1,18 @@ +/* { dg-do compile } */ +/* { dg-options "-O3 -fdump-tree-ldist" } */ + +void +foo (int *p) +{ + unsigned short i, j; + + for (i = 0; i < 100; i++) + for (j = 1; j < 101; j++) + { + unsigned int index = 100 * i + j; + p[index-1] = 0; + } +} + +/* Loop can be transformed into builtin memset since &p[...] is SCEV. */ +/* { dg-final { scan-tree-dump "builtin_memset" "ldist" } } */ diff --git a/gcc/tree-chrec.c b/gcc/tree-chrec.c index ee789a2436f..707a3aa988e 100644 --- a/gcc/tree-chrec.c +++ b/gcc/tree-chrec.c @@ -1162,16 +1162,17 @@ nb_vars_in_chrec (tree chrec) /* Converts BASE and STEP of affine scev to TYPE. LOOP is the loop whose iv the scev corresponds to. AT_STMT is the statement at that the scev is - evaluated. USE_OVERFLOW_SEMANTICS is true if this function should assume that - the rules for overflow of the given language apply (e.g., that signed - arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary - tests, but also to enforce that the result follows them. Returns true if the - conversion succeeded, false otherwise. */ + evaluated. USE_OVERFLOW_SEMANTICS is true if this function should assume + that the rules for overflow of the given language apply (e.g., that signed + arithmetics in C does not overflow) -- i.e., to use them to avoid + unnecessary tests, but also to enforce that the result follows them. + FROM is the source variable converted if it's not NULL. Returns true if + the conversion succeeded, false otherwise. */ bool convert_affine_scev (struct loop *loop, tree type, tree *base, tree *step, gimple *at_stmt, - bool use_overflow_semantics) + bool use_overflow_semantics, tree from) { tree ct = TREE_TYPE (*step); bool enforce_overflow_semantics; @@ -1230,7 +1231,7 @@ convert_affine_scev (struct loop *loop, tree type, must_check_rslt_overflow = false; if (must_check_src_overflow - && scev_probably_wraps_p (*base, *step, at_stmt, loop, + && scev_probably_wraps_p (from, *base, *step, at_stmt, loop, use_overflow_semantics)) return false; @@ -1258,7 +1259,8 @@ convert_affine_scev (struct loop *loop, tree type, if (must_check_rslt_overflow /* Note that in this case we cannot use the fact that signed variables do not overflow, as this is what we are verifying for the new iv. */ - && scev_probably_wraps_p (new_base, new_step, at_stmt, loop, false)) + && scev_probably_wraps_p (NULL_TREE, new_base, new_step, + at_stmt, loop, false)) return false; *base = new_base; @@ -1288,12 +1290,14 @@ chrec_convert_rhs (tree type, tree chrec, gimple *at_stmt) USE_OVERFLOW_SEMANTICS is true if this function should assume that the rules for overflow of the given language apply (e.g., that signed - arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary - tests, but also to enforce that the result follows them. */ + arithmetics in C does not overflow) -- i.e., to use them to avoid + unnecessary tests, but also to enforce that the result follows them. + + FROM is the source variable converted if it's not NULL. */ static tree chrec_convert_1 (tree type, tree chrec, gimple *at_stmt, - bool use_overflow_semantics) + bool use_overflow_semantics, tree from) { tree ct, res; tree base, step; @@ -1314,7 +1318,7 @@ chrec_convert_1 (tree type, tree chrec, gimple *at_stmt, step = CHREC_RIGHT (chrec); if (convert_affine_scev (loop, type, &base, &step, at_stmt, - use_overflow_semantics)) + use_overflow_semantics, from)) return build_polynomial_chrec (loop->num, base, step); /* If we cannot propagate the cast inside the chrec, just keep the cast. */ @@ -1347,7 +1351,7 @@ keep_cast: CHREC_LEFT (chrec)), fold_convert (utype, CHREC_RIGHT (chrec))); - res = chrec_convert_1 (type, res, at_stmt, use_overflow_semantics); + res = chrec_convert_1 (type, res, at_stmt, use_overflow_semantics, from); } else res = fold_convert (type, chrec); @@ -1395,14 +1399,16 @@ keep_cast: USE_OVERFLOW_SEMANTICS is true if this function should assume that the rules for overflow of the given language apply (e.g., that signed - arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary - tests, but also to enforce that the result follows them. */ + arithmetics in C does not overflow) -- i.e., to use them to avoid + unnecessary tests, but also to enforce that the result follows them. + + FROM is the source variable converted if it's not NULL. */ tree chrec_convert (tree type, tree chrec, gimple *at_stmt, - bool use_overflow_semantics) + bool use_overflow_semantics, tree from) { - return chrec_convert_1 (type, chrec, at_stmt, use_overflow_semantics); + return chrec_convert_1 (type, chrec, at_stmt, use_overflow_semantics, from); } /* Convert CHREC to TYPE, without regard to signed overflows. Returns the new diff --git a/gcc/tree-chrec.h b/gcc/tree-chrec.h index 383271ca116..877330e92d4 100644 --- a/gcc/tree-chrec.h +++ b/gcc/tree-chrec.h @@ -59,7 +59,7 @@ enum ev_direction scev_direction (const_tree); extern tree chrec_fold_plus (tree, tree, tree); extern tree chrec_fold_minus (tree, tree, tree); extern tree chrec_fold_multiply (tree, tree, tree); -extern tree chrec_convert (tree, tree, gimple *, bool = true); +extern tree chrec_convert (tree, tree, gimple *, bool = true, tree = NULL); extern tree chrec_convert_rhs (tree, tree, gimple *); extern tree chrec_convert_aggressive (tree, tree, bool *); @@ -75,7 +75,7 @@ extern tree reset_evolution_in_loop (unsigned, tree, tree); extern tree chrec_merge (tree, tree); extern void for_each_scev_op (tree *, bool (*) (tree *, void *), void *); extern bool convert_affine_scev (struct loop *, tree, tree *, tree *, gimple *, - bool); + bool, tree = NULL); /* Observers. */ extern bool eq_evolutions_p (const_tree, const_tree); diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index d8ed84af495..7c5cefde068 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -1933,7 +1933,7 @@ interpret_rhs_expr (struct loop *loop, gimple *at_stmt, } else chrec1 = analyze_scalar_evolution (loop, rhs1); - res = chrec_convert (type, chrec1, at_stmt); + res = chrec_convert (type, chrec1, at_stmt, true, rhs1); break; case BIT_AND_EXPR: diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c index 1102c8a921c..3b4d4f31502 100644 --- a/gcc/tree-ssa-loop-niter.c +++ b/gcc/tree-ssa-loop-niter.c @@ -3128,7 +3128,8 @@ idx_infer_loop_bounds (tree base, tree *idx, void *dta) /* If access is not executed on every iteration, we must ensure that overlow may not make the access valid later. */ if (!dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (data->stmt)) - && scev_probably_wraps_p (initial_condition_in_loop_num (ev, loop->num), + && scev_probably_wraps_p (NULL_TREE, + initial_condition_in_loop_num (ev, loop->num), step, data->stmt, loop, true)) upper = false; @@ -4191,6 +4192,104 @@ loop_exits_before_overflow (tree base, tree step, return false; } +/* VAR is scev variable whose evolution part is constant STEP, this function + proves that VAR can't overflow by using value range info. If VAR's value + range is [MIN, MAX], it can be proven by: + MAX + step doesn't overflow ; if step > 0 + or + MIN + step doesn't underflow ; if step < 0. + + We can only do this if var is computed in every loop iteration, i.e, var's + definition has to dominate loop latch. Consider below example: + + { + unsigned int i; + + : + + : + # RANGE [0, 4294967294] NONZERO 65535 + # i_21 = PHI <0(3), i_18(9)> + if (i_21 != 0) + goto ; + else + goto ; + + : + # RANGE [0, 65533] NONZERO 65535 + _6 = i_21 + 4294967295; + # RANGE [0, 65533] NONZERO 65535 + _7 = (long unsigned int) _6; + # RANGE [0, 524264] NONZERO 524280 + _8 = _7 * 8; + # PT = nonlocal escaped + _9 = a_14 + _8; + *_9 = 0; + + : + # RANGE [1, 65535] NONZERO 65535 + i_18 = i_21 + 1; + if (i_18 >= 65535) + goto ; + else + goto ; + + : + goto ; + + : + return; + } + + VAR _6 doesn't overflow only with pre-condition (i_21 != 0), here we + can't use _6 to prove no-overlfow for _7. In fact, var _7 takes value + sequence (4294967295, 0, 1, ..., 65533) in loop life time, rather than + (4294967295, 4294967296, ...). */ + +static bool +scev_var_range_cant_overflow (tree var, tree step, struct loop *loop) +{ + tree type; + wide_int minv, maxv, diff, step_wi; + enum value_range_type rtype; + + if (TREE_CODE (step) != INTEGER_CST || !INTEGRAL_TYPE_P (TREE_TYPE (var))) + return false; + + /* Check if VAR evaluates in every loop iteration. It's not the case + if VAR is default definition or does not dominate loop's latch. */ + basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (var)); + if (!def_bb || !dominated_by_p (CDI_DOMINATORS, loop->latch, def_bb)) + return false; + + rtype = get_range_info (var, &minv, &maxv); + if (rtype != VR_RANGE) + return false; + + /* VAR is a scev whose evolution part is STEP and value range info + is [MIN, MAX], we can prove its no-overflowness by conditions: + + type_MAX - MAX >= step ; if step > 0 + MIN - type_MIN >= |step| ; if step < 0. + + Or VAR must take value outside of value range, which is not true. */ + step_wi = step; + type = TREE_TYPE (var); + if (tree_int_cst_sign_bit (step)) + { + diff = lower_bound_in_type (type, type); + diff = minv - diff; + step_wi = - step_wi; + } + else + { + diff = upper_bound_in_type (type, type); + diff = diff - maxv; + } + + return (wi::geu_p (diff, step_wi)); +} + /* Return false only when the induction variable BASE + STEP * I is known to not overflow: i.e. when the number of iterations is small enough with respect to the step and initial condition in order to @@ -4199,10 +4298,13 @@ loop_exits_before_overflow (tree base, tree step, USE_OVERFLOW_SEMANTICS is true if this function should assume that the rules for overflow of the given language apply (e.g., that signed - arithmetics in C does not overflow). */ + arithmetics in C does not overflow). + + If VAR is a ssa variable, this function also returns false if VAR can + be proven not overflow with value range info. */ bool -scev_probably_wraps_p (tree base, tree step, +scev_probably_wraps_p (tree var, tree base, tree step, gimple *at_stmt, struct loop *loop, bool use_overflow_semantics) { @@ -4239,6 +4341,11 @@ scev_probably_wraps_p (tree base, tree step, if (TREE_CODE (step) != INTEGER_CST) return true; + /* Check if var can be proven not overflow with value range info. */ + if (var && TREE_CODE (var) == SSA_NAME + && scev_var_range_cant_overflow (var, step, loop)) + return false; + if (loop_exits_before_overflow (base, step, at_stmt, loop)) return false; diff --git a/gcc/tree-ssa-loop-niter.h b/gcc/tree-ssa-loop-niter.h index 1aea5801d00..97400cb6884 100644 --- a/gcc/tree-ssa-loop-niter.h +++ b/gcc/tree-ssa-loop-niter.h @@ -49,7 +49,8 @@ extern bool estimated_stmt_executions (struct loop *, widest_int *); extern void estimate_numbers_of_iterations (void); extern bool stmt_dominates_stmt_p (gimple *, gimple *); extern bool nowrap_type_p (tree); -extern bool scev_probably_wraps_p (tree, tree, gimple *, struct loop *, bool); +extern bool scev_probably_wraps_p (tree, tree, tree, gimple *, + struct loop *, bool); extern void free_loop_control_ivs (struct loop *); extern void free_numbers_of_iterations_estimates_loop (struct loop *); extern void free_numbers_of_iterations_estimates (function *); diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index 4333d60672f..b9ccb73ff79 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -4156,8 +4156,8 @@ adjust_range_with_scev (value_range *vr, struct loop *loop, or decreases, ... */ dir == EV_DIR_UNKNOWN /* ... or if it may wrap. */ - || scev_probably_wraps_p (init, step, stmt, get_chrec_loop (chrec), - true)) + || scev_probably_wraps_p (NULL_TREE, init, step, stmt, + get_chrec_loop (chrec), true)) return; /* We use TYPE_MIN_VALUE and TYPE_MAX_VALUE here instead of -- 2.30.2