On Wed, 9 Dec 2020, Richard Sandiford wrote: > PR98069 is about a case in which split_constant_offset miscategorises > an expression of the form: > > int foo; > … > POINTER_PLUS_EXPR<base, (sizetype)(INT_MIN - foo) * size> > > as: > > base: base > offset: (sizetype) (-foo) * size > init: INT_MIN * size > > “-foo” overflows when “foo” is INT_MIN, whereas the original expression > didn't overflow in that case. > > As discussed in the PR trail, we could simply ignore the fact that > int overflow is undefined and treat it as a wrapping type, but that > is likely to pessimise quite a few cases. > > This patch instead reworks split_constant_offset so that: > > - it treats integer operations as having an implicit cast to sizetype > - for integer operations, the returned VAR has type sizetype > > In other words, the problem becomes to express: > > (sizetype) (OP0 CODE OP1) > > as: > > VAR:sizetype + (sizetype) OFF:ssizetype > > The top-level integer split_constant_offset will (usually) be a sizetype > POINTER_PLUS operand, so the extra cast to sizetype disappears. But adding > the cast allows the conversion handling to defer a lot of the difficult > cases to the recursive split_constant_offset call, which can detect > overflow on individual operations. > > The net effect is to analyse the access above as: > > base: base > offset: -(sizetype) foo * size > init: INT_MIN * size > > See the comments in the patch for more details. > > Tested on aarch64-linux-gnu so far (with and without SVE), but will > test more widely overnight.
Nice - thanks for refactoring it this way. I've one small question at the very end ... > Thanks, > Richard > > > gcc/ > PR tree-optimization/98069 > * tree-data-ref.c (compute_distributive_range): New function. > (nop_conversion_for_offset_p): Likewise. > (split_constant_offset): In the internal overload, treat integer > expressions as having an implicit cast to sizetype and express > them accordingly. Pass back the range of the original (uncast) > expression in a new range parameter. > (split_constant_offset_1): Likewise. Rework the handling of > conversions to account for the implicit sizetype casts. > --- > gcc/testsuite/gcc.dg/vect/pr98069.c | 22 ++ > gcc/tree-data-ref.c | 427 +++++++++++++++++++++------- > 2 files changed, 352 insertions(+), 97 deletions(-) > create mode 100644 gcc/testsuite/gcc.dg/vect/pr98069.c > > diff --git a/gcc/testsuite/gcc.dg/vect/pr98069.c > b/gcc/testsuite/gcc.dg/vect/pr98069.c > new file mode 100644 > index 00000000000..e60549fb30a > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/vect/pr98069.c > @@ -0,0 +1,22 @@ > +long long int var_3 = -166416893043554447LL; > +short var_8 = (short)27092; > +unsigned int var_17 = 75036300U; > +short arr_165[23]; > + > +static long c(long e, long f) { return f ? e : f; } > +void __attribute((noipa)) test() > +{ > + for (int b = 0; b < 19; b = var_17) > + for (int d = (int)(~c(-2147483647 - 1, var_3)) - 2147483647; d < 22; d++) > + arr_165[d] = var_8; > +} > + > +int main() > +{ > + for (unsigned i_3 = 0; i_3 < 23; ++i_3) > + arr_165[i_3] = (short)-8885; > + test(); > + if (arr_165[0] != 27092) > + __builtin_abort (); > + return 0; > +} > diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c > index e8308ce8250..926553b5cac 100644 > --- a/gcc/tree-data-ref.c > +++ b/gcc/tree-data-ref.c > @@ -97,6 +97,8 @@ along with GCC; see the file COPYING3. If not see > #include "tree-eh.h" > #include "ssa.h" > #include "internal-fn.h" > +#include "range-op.h" > +#include "vr-values.h" > > static struct datadep_stats > { > @@ -581,26 +583,196 @@ debug_ddrs (vec<ddr_p> ddrs) > dump_ddrs (stderr, ddrs); > } > > +/* If RESULT_RANGE is nonnull, set *RESULT_RANGE to the range of > + OP0 CODE OP1, where: > + > + - OP0 CODE OP1 has integral type TYPE > + - the range of OP0 is given by OP0_RANGE and > + - the range of OP1 is given by OP1_RANGE. > + > + Independently of RESULT_RANGE, try to compute: > + > + DELTA = ((sizetype) OP0 CODE (sizetype) OP1) > + - (sizetype) (OP0 CODE OP1) > + > + as a constant and subtract DELTA from the ssizetype constant in *OFF. > + Return true on success, or false if DELTA is not known at compile time. > + > + Truncation and sign changes are known to distribute over CODE, i.e. > + > + (itype) (A CODE B) == (itype) A CODE (itype) B > + > + for any integral type ITYPE whose precision is no greater than the > + precision of A and B. */ > + > +static bool > +compute_distributive_range (tree type, value_range &op0_range, > + tree_code code, value_range &op1_range, > + tree *off, value_range *result_range) > +{ > + gcc_assert (INTEGRAL_TYPE_P (type) && !TYPE_OVERFLOW_TRAPS (type)); > + if (result_range) > + { > + range_operator *op = range_op_handler (code, type); > + op->fold_range (*result_range, type, op0_range, op1_range); > + } > + > + /* The distributive property guarantees that if TYPE is no narrower > + than SIZETYPE, > + > + (sizetype) (OP0 CODE OP1) == (sizetype) OP0 CODE (sizetype) OP1 > + > + and so we can treat DELTA as zero. */ > + if (TYPE_PRECISION (type) >= TYPE_PRECISION (sizetype)) > + return true; > + > + /* If overflow is undefined, we can assume that: > + > + X == (ssizetype) OP0 CODE (ssizetype) OP1 > + > + is within the range of TYPE, i.e.: > + > + X == (ssizetype) (TYPE) X > + > + Distributing the (TYPE) truncation over X gives: > + > + X == (ssizetype) (OP0 CODE OP1) > + > + Casting both sides to sizetype and distributing the sizetype cast > + over X gives: > + > + (sizetype) OP0 CODE (sizetype) OP1 == (sizetype) (OP0 CODE OP1) > + > + and so we can treat DELTA as zero. */ > + if (TYPE_OVERFLOW_UNDEFINED (type)) > + return true; > + > + /* Compute the range of: > + > + (ssizetype) OP0 CODE (ssizetype) OP1 > + > + The distributive property guarantees that this has the same bitpattern > as: > + > + (sizetype) OP0 CODE (sizetype) OP1 > + > + but its range is more conducive to analysis. */ > + range_cast (op0_range, ssizetype); > + range_cast (op1_range, ssizetype); > + value_range wide_range; > + range_operator *op = range_op_handler (code, ssizetype); > + bool saved_flag_wrapv = flag_wrapv; > + flag_wrapv = 1; > + op->fold_range (wide_range, ssizetype, op0_range, op1_range); > + flag_wrapv = saved_flag_wrapv; > + if (wide_range.num_pairs () != 1 || !range_int_cst_p (&wide_range)) > + return false; > + > + wide_int lb = wide_range.lower_bound (); > + wide_int ub = wide_range.upper_bound (); > + > + /* Calculate the number of times that each end of the range overflows or > + underflows TYPE. We can only calculate DELTA if the numbers match. */ > + unsigned int precision = TYPE_PRECISION (type); > + if (!TYPE_UNSIGNED (type)) > + { > + wide_int type_min = wi::mask (precision - 1, true, lb.get_precision > ()); > + lb -= type_min; > + ub -= type_min; > + } > + wide_int upper_bits = wi::mask (precision, true, lb.get_precision ()); > + lb &= upper_bits; > + ub &= upper_bits; > + if (lb != ub) > + return false; > + > + /* OP0 CODE OP1 overflows exactly arshift (LB, PRECISION) times, with > + negative values indicating underflow. The low PRECISION bits of LB > + are clear, so DELTA is therefore LB (== UB). */ > + *off = wide_int_to_tree (ssizetype, wi::to_wide (*off) - lb); > + return true; > +} > + > +/* Return true if (sizetype) OP == (sizetype) (TO_TYPE) OP, > + given that OP has type FROM_TYPE and range RANGE. Both TO_TYPE and > + FROM_TYPE are integral types. */ > + > +static bool > +nop_conversion_for_offset_p (tree to_type, tree from_type, value_range > &range) > +{ > + gcc_assert (INTEGRAL_TYPE_P (to_type) > + && INTEGRAL_TYPE_P (from_type) > + && !TYPE_OVERFLOW_TRAPS (to_type) > + && !TYPE_OVERFLOW_TRAPS (from_type)); > + > + /* Converting to something no narrower than sizetype and then to sizetype > + is equivalent to converting directly to sizetype. */ > + if (TYPE_PRECISION (to_type) >= TYPE_PRECISION (sizetype)) > + return true; > + > + /* Check whether TO_TYPE can represent all values that FROM_TYPE can. */ > + if (TYPE_PRECISION (from_type) < TYPE_PRECISION (to_type) > + && (TYPE_UNSIGNED (from_type) || !TYPE_UNSIGNED (to_type))) > + return true; > + > + /* For narrowing conversions, we could in principle test whether > + the bits in FROM_TYPE but not in TO_TYPE have a fixed value > + and apply a constant adjustment. > + > + For other conversions (which involve a sign change) we could > + check that the signs are always equal, and apply a constant > + adjustment if the signs are negative. > + > + However, both cases should be rare. */ > + return range_fits_type_p (&range, TYPE_PRECISION (to_type), > + TYPE_SIGN (to_type)); > +} > + > static void > -split_constant_offset (tree exp, tree *var, tree *off, > +split_constant_offset (tree type, tree *var, tree *off, > + value_range *result_range, > hash_map<tree, std::pair<tree, tree> > &cache, > unsigned *limit); > > -/* Helper function for split_constant_offset. Expresses OP0 CODE OP1 > - (the type of the result is TYPE) as VAR + OFF, where OFF is a nonzero > - constant of type ssizetype, and returns true. If we cannot do this > - with OFF nonzero, OFF and VAR are set to NULL_TREE instead and false > - is returned. */ > +/* Helper function for split_constant_offset. If TYPE is a pointer type, > + try to express OP0 CODE OP1 as: > + > + POINTER_PLUS <*VAR, (sizetype) *OFF> > + > + where: > + > + - *VAR has type TYPE > + - *OFF is a constant of type ssizetype. > + > + If TYPE is an integral type, try to express (sizetype) (OP0 CODE OP1) as: > + > + *VAR + (sizetype) *OFF > + > + where: > + > + - *VAR has type sizetype > + - *OFF is a constant of type ssizetype. > + > + In both cases, OP0 CODE OP1 has type TYPE. > + > + Return true on success. A false return value indicates that we can't > + do better than set *OFF to zero. > + > + When returning true, set RESULT_RANGE to the range of OP0 CODE OP1, > + if RESULT_RANGE is nonnull and if we can do better than assume VR_VARYING. > + > + CACHE caches {*VAR, *OFF} pairs for SSA names that we've previously > + visited. LIMIT counts down the number of SSA names that we are > + allowed to process before giving up. */ > > static bool > split_constant_offset_1 (tree type, tree op0, enum tree_code code, tree op1, > - tree *var, tree *off, > + tree *var, tree *off, value_range *result_range, > hash_map<tree, std::pair<tree, tree> > &cache, > unsigned *limit) > { > tree var0, var1; > tree off0, off1; > - enum tree_code ocode = code; > + value_range op0_range, op1_range; > > *var = NULL_TREE; > *off = NULL_TREE; > @@ -608,35 +780,42 @@ split_constant_offset_1 (tree type, tree op0, enum > tree_code code, tree op1, > switch (code) > { > case INTEGER_CST: > - *var = build_int_cst (type, 0); > + *var = size_int (0); > *off = fold_convert (ssizetype, op0); > + if (result_range) > + result_range->set (op0, op0); > return true; > > case POINTER_PLUS_EXPR: > - ocode = PLUS_EXPR; > - /* FALLTHROUGH */ > + split_constant_offset (op0, &var0, &off0, nullptr, cache, limit); > + split_constant_offset (op1, &var1, &off1, nullptr, cache, limit); > + *var = fold_build2 (POINTER_PLUS_EXPR, type, var0, var1); > + *off = size_binop (PLUS_EXPR, off0, off1); > + return true; > + > case PLUS_EXPR: > case MINUS_EXPR: > - if (TREE_CODE (op1) == INTEGER_CST) > - { > - split_constant_offset (op0, &var0, &off0, cache, limit); > - *var = var0; > - *off = size_binop (ocode, off0, fold_convert (ssizetype, op1)); > - return true; > - } > - split_constant_offset (op0, &var0, &off0, cache, limit); > - split_constant_offset (op1, &var1, &off1, cache, limit); > - *var = fold_build2 (code, type, var0, var1); > - *off = size_binop (ocode, off0, off1); > + split_constant_offset (op0, &var0, &off0, &op0_range, cache, limit); > + split_constant_offset (op1, &var1, &off1, &op1_range, cache, limit); > + *off = size_binop (code, off0, off1); > + if (!compute_distributive_range (type, op0_range, code, op1_range, > + off, result_range)) > + return false; > + *var = fold_build2 (code, sizetype, var0, var1); > return true; > > case MULT_EXPR: > if (TREE_CODE (op1) != INTEGER_CST) > return false; > > - split_constant_offset (op0, &var0, &off0, cache, limit); > - *var = fold_build2 (MULT_EXPR, type, var0, op1); > + split_constant_offset (op0, &var0, &off0, &op0_range, cache, limit); > + op1_range.set (op1, op1); > *off = size_binop (MULT_EXPR, off0, fold_convert (ssizetype, op1)); > + if (!compute_distributive_range (type, op0_range, code, op1_range, > + off, result_range)) > + return false; > + *var = fold_build2 (MULT_EXPR, sizetype, var0, > + fold_convert (sizetype, op1)); > return true; > > case ADDR_EXPR: > @@ -658,13 +837,10 @@ split_constant_offset_1 (tree type, tree op0, enum > tree_code code, tree op1, > > if (poffset) > { > - split_constant_offset (poffset, &poffset, &off1, cache, limit); > + split_constant_offset (poffset, &poffset, &off1, nullptr, > + cache, limit); > off0 = size_binop (PLUS_EXPR, off0, off1); > - if (POINTER_TYPE_P (TREE_TYPE (base))) > - base = fold_build_pointer_plus (base, poffset); > - else > - base = fold_build2 (PLUS_EXPR, TREE_TYPE (base), base, > - fold_convert (TREE_TYPE (base), poffset)); > + base = fold_build_pointer_plus (base, poffset); > } > > var0 = fold_convert (type, base); > @@ -723,6 +899,7 @@ split_constant_offset_1 (tree type, tree op0, enum > tree_code code, tree op1, > return false; > *var = e.first; > *off = e.second; > + /* The caller sets the range in this case. */ > return true; > } > e = std::make_pair (op0, ssize_int (0)); > @@ -736,72 +913,80 @@ split_constant_offset_1 (tree type, tree op0, enum > tree_code code, tree op1, > var1 = gimple_assign_rhs2 (def_stmt); > > bool res = split_constant_offset_1 (type, var0, subcode, var1, > - var, off, cache, limit); > + var, off, nullptr, cache, limit); > if (res && use_cache) > *cache.get (op0) = std::make_pair (*var, *off); > + /* The caller sets the range in this case. */ > return res; > } > CASE_CONVERT: > { > - /* We must not introduce undefined overflow, and we must not change > - the value. Hence we're okay if the inner type doesn't overflow > - to start with (pointer or signed), the outer type also is an > - integer or pointer and the outer precision is at least as large > - as the inner. */ > + /* We can only handle the following conversions: > + > + - Conversions from one pointer type to another pointer type. > + > + - Conversions from one non-trapping integral type to another > + non-trapping integral type. In this case, the recursive > + call makes sure that: > + > + (sizetype) OP0 > + > + can be expressed as a sizetype operation involving VAR and OFF, > + and all we need to do is check whether: > + > + (sizetype) OP0 == (sizetype) (TYPE) OP0 > + > + - Conversions from a non-trapping sizetype-size integral type to > + a like-sized pointer type. In this case, the recursive call > + makes sure that: > + > + (sizetype) OP0 == *VAR + (sizetype) *OFF > + > + and we can convert that to: > + > + POINTER_PLUS <(TYPE) *VAR, (sizetype) *OFF> > + > + - Conversions from a sizetype-sized pointer type to a like-sized > + non-trapping integral type. In this case, the recursive call > + makes sure that: > + > + OP0 == POINTER_PLUS <*VAR, (sizetype) *OFF> > + > + where the POINTER_PLUS and *VAR have the same precision as > + TYPE (and the same precision as sizetype). Then: > + > + (sizetype) (TYPE) OP0 == (sizetype) *VAR + (sizetype) *OFF. */ > tree itype = TREE_TYPE (op0); > if ((POINTER_TYPE_P (itype) > || (INTEGRAL_TYPE_P (itype) && !TYPE_OVERFLOW_TRAPS (itype))) > - && TYPE_PRECISION (type) >= TYPE_PRECISION (itype) > - && (POINTER_TYPE_P (type) || INTEGRAL_TYPE_P (type))) > + && (POINTER_TYPE_P (type) > + || (INTEGRAL_TYPE_P (type) && !TYPE_OVERFLOW_TRAPS (type))) > + && (POINTER_TYPE_P (type) == POINTER_TYPE_P (itype) > + || (TYPE_PRECISION (type) == TYPE_PRECISION (sizetype) > + && TYPE_PRECISION (itype) == TYPE_PRECISION (sizetype)))) > { > - if (INTEGRAL_TYPE_P (itype) && TYPE_OVERFLOW_WRAPS (itype) > - && (TYPE_PRECISION (type) > TYPE_PRECISION (itype) > - || TYPE_UNSIGNED (itype) != TYPE_UNSIGNED (type))) > + if (POINTER_TYPE_P (type)) > + { > + split_constant_offset (op0, var, off, nullptr, cache, limit); > + *var = fold_convert (type, *var); > + } > + else if (POINTER_TYPE_P (itype)) > + { > + split_constant_offset (op0, var, off, nullptr, cache, limit); > + *var = fold_convert (sizetype, *var); > + } > + else > { > - /* Split the unconverted operand and try to prove that > - wrapping isn't a problem. */ > - tree tmp_var, tmp_off; > - split_constant_offset (op0, &tmp_var, &tmp_off, cache, limit); > - > - /* See whether we have an known range [A, B] for tmp_var. */ > - wide_int var_min, var_max; > - signop sgn = TYPE_SIGN (itype); > - if (TREE_CODE (tmp_var) == SSA_NAME) > + split_constant_offset (op0, var, off, &op0_range, > + cache, limit); > + if (!nop_conversion_for_offset_p (type, itype, op0_range)) > + return false; > + if (result_range) > { > - value_range_kind vr_type > - = get_range_info (tmp_var, &var_min, &var_max); > - wide_int var_nonzero = get_nonzero_bits (tmp_var); > - if (intersect_range_with_nonzero_bits (vr_type, &var_min, > - &var_max, > - var_nonzero, > - sgn) != VR_RANGE) > - return false; > + *result_range = op0_range; > + range_cast (*result_range, type); > } > - else if (determine_value_range (tmp_var, &var_min, &var_max) > - != VR_RANGE) > - return false; > - > - /* See whether the range of OP0 (i.e. TMP_VAR + TMP_OFF) > - is known to be [A + TMP_OFF, B + TMP_OFF], with all > - operations done in ITYPE. The addition must overflow > - at both ends of the range or at neither. */ > - wi::overflow_type overflow[2]; > - unsigned int prec = TYPE_PRECISION (itype); > - wide_int woff = wi::to_wide (tmp_off, prec); > - wide_int op0_min = wi::add (var_min, woff, sgn, &overflow[0]); > - wi::add (var_max, woff, sgn, &overflow[1]); > - if ((overflow[0] != wi::OVF_NONE) != (overflow[1] != > wi::OVF_NONE)) > - return false; > - > - /* Calculate (ssizetype) OP0 - (ssizetype) TMP_VAR. */ > - widest_int diff = (widest_int::from (op0_min, sgn) > - - widest_int::from (var_min, sgn)); > - var0 = tmp_var; > - *off = wide_int_to_tree (ssizetype, diff); > } > - else > - split_constant_offset (op0, &var0, off, cache, limit); > - *var = fold_convert (type, var0); > return true; > } > return false; > @@ -812,33 +997,80 @@ split_constant_offset_1 (tree type, tree op0, enum > tree_code code, tree op1, > } > } > > -/* Expresses EXP as VAR + OFF, where off is a constant. The type of OFF > - will be ssizetype. */ > +/* If EXP has pointer type, try to express it as: > + > + POINTER_PLUS <*VAR, (sizetype) *OFF> > + > + where: > + > + - *VAR has the same type as EXP > + - *OFF is a constant of type ssizetype. > + > + If EXP has an integral type, try to express (sizetype) EXP as: > + > + *VAR + (sizetype) *OFF > + > + where: > + > + - *VAR has type sizetype > + - *OFF is a constant of type ssizetype. > + > + If EXP_RANGE is nonnull, set it to the range of EXP. > + > + CACHE caches {*VAR, *OFF} pairs for SSA names that we've previously > + visited. LIMIT counts down the number of SSA names that we are > + allowed to process before giving up. */ > > static void > -split_constant_offset (tree exp, tree *var, tree *off, > +split_constant_offset (tree exp, tree *var, tree *off, value_range > *exp_range, > hash_map<tree, std::pair<tree, tree> > &cache, > unsigned *limit) > { > - tree type = TREE_TYPE (exp), op0, op1, e, o; > + tree type = TREE_TYPE (exp), op0, op1; > enum tree_code code; > > - *var = exp; > - *off = ssize_int (0); > + code = TREE_CODE (exp); > + if (exp_range) > + { > + *exp_range = type; > + if (code == SSA_NAME) > + { > + wide_int var_min, var_max; > + value_range_kind vr_kind = get_range_info (exp, &var_min, &var_max); > + wide_int var_nonzero = get_nonzero_bits (exp); > + vr_kind = intersect_range_with_nonzero_bits (vr_kind, > + &var_min, &var_max, > + var_nonzero, > + TYPE_SIGN (type)); > + if (vr_kind == VR_RANGE) > + *exp_range = value_range (type, var_min, var_max); > + } > + } > > - if (tree_is_chrec (exp) > - || get_gimple_rhs_class (TREE_CODE (exp)) == GIMPLE_TERNARY_RHS) > - return; > + if (!tree_is_chrec (exp) > + && get_gimple_rhs_class (TREE_CODE (exp)) != GIMPLE_TERNARY_RHS) > + { > + extract_ops_from_tree (exp, &code, &op0, &op1); > + if (split_constant_offset_1 (type, op0, code, op1, var, off, > + exp_range, cache, limit)) > + return; > + } > > - code = TREE_CODE (exp); > - extract_ops_from_tree (exp, &code, &op0, &op1); > - if (split_constant_offset_1 (type, op0, code, op1, &e, &o, cache, limit)) > + *var = exp; > + if (INTEGRAL_TYPE_P (type)) > + *var = fold_convert (sizetype, *var); > + *off = ssize_int (0); > + if (exp_range && code != SSA_NAME) > { > - *var = e; > - *off = o; > + wide_int var_min, var_max; > + if (determine_value_range (exp, &var_min, &var_max) == VR_RANGE) > + *exp_range = value_range (type, var_min, var_max); So this call is only for the case the recursion failed, otherwise we build exp_range during the recursive call, correct? The patch is OK. Thanks again for tackling this. Richard. > } > } > > +/* Expresses EXP as VAR + OFF, where OFF is a constant. VAR has the same > + type as EXP while OFF has type ssizetype. */ > + > void > split_constant_offset (tree exp, tree *var, tree *off) > { > @@ -846,7 +1078,8 @@ split_constant_offset (tree exp, tree *var, tree *off) > static hash_map<tree, std::pair<tree, tree> > *cache; > if (!cache) > cache = new hash_map<tree, std::pair<tree, tree> > (37); > - split_constant_offset (exp, var, off, *cache, &limit); > + split_constant_offset (exp, var, off, nullptr, *cache, &limit); > + *var = fold_convert (TREE_TYPE (exp), *var); > cache->empty (); > } >