[PATCH v2 2/5] scev: Add nowrap bound.
Robin Dapp <[email protected]>
| Newsgroups | gmane.comp.gcc.patches |
|---|---|
| Message-ID | <[email protected]> |
From: Robin Dapp <[email protected]> This patch adds a path for scev to continue when encountering wrapping behavior instead of giving up. If scev_probably_wraps_p is passed a nonzero nowrap_bound tree it will use the type bound of the current step as upper bound for wrapping and store it. In order for the nowrap_bound parameter to reach scev_probably_wraps_p, the patch adds parameters to many of the internal scev functions. Most of them just forward the parameter. Initially, I attempted a global variable that was supposed to store the bound. None of my tries resulted in comprehensible code or correct results, however, and I found myself running into corner case after corner case. Thus, I arrived at the mostly mechanical "brute-force" solution. The idea is to build a topmost/final assumption when walking back up the chrec tree, merging child assumptions at parent nodes. Child chrecs only have the local bound necessary at their level. For bounds merging the patch introduces a helper scev_combine_nowrap_bound that combines two bounds by building a MIN of each so that we'd get a condition like IV <= MIN (dr1.bound, dr2.bound, ...). Nowrap queries go to a separate hash table that reuses scev_info_str. The latter gets a new field nowrap_bound which is always NULL in the regular hash table and potentially non-null in the nowrap table. affine_iv also gets a nowrap_bound field which allows passing the nowrap bounds to dataref analysis. gcc/ChangeLog: * tree-chrec.cc (convert_affine_scev): Add nowrap_bound param. (chrec_convert_rhs): Ditto. (chrec_convert_1): Ditto. (chrec_convert): Ditto. * tree-chrec.h (chrec_convert): Ditto. (chrec_convert_rhs): Ditto. (convert_affine_scev): Ditto. * tree-scalar-evolution.cc (analyze_scalar_evolution_1): Ditto. (analyze_scalar_evolution_for_address_of): Ditto. (struct scev_info_str): Add nowrap_assumed. (new_scev_info_str): Ditto. (scev_info_hasher::hash): Ditto. (scev_info_hasher::equal): Ditto. (find_var_scev_info): Ditto. (scev_combine_nowrap_bound): New function to accumulate bounds. (set_scalar_evolution): Add nowrap_bound param. (get_scalar_evolution): Ditto. (simplify_peeled_chrec): Ditto. (analyze_evolution_in_loop): Ditto. (interpret_loop_phi): Ditto. (interpret_condition_phi): Ditto. (interpret_rhs_expr): Ditto. (interpret_expr): Ditto. (interpret_gimple_assign): Ditto. (analyze_scalar_evolution): Ditto. (analyze_scalar_evolution_in_loop): Ditto. (simple_iv_with_niters): Add allow_wrapping. (simple_iv): Ditto. * tree-scalar-evolution.h (analyze_scalar_evolution): Add new param. (simple_iv_with_niters): Ditto. (scev_combine_nowrap_bound): Declare. * tree-ssa-loop-niter.cc (scev_probably_wraps_p): Build no-wrap bound. * tree-ssa-loop-niter.h (scev_probably_wraps_p): Add param. * tree-ssa-loop.h (struct affine_iv): Add nowrap_bound. --- gcc/tree-chrec.cc | 51 ++++-- gcc/tree-chrec.h | 7 +- gcc/tree-scalar-evolution.cc | 340 +++++++++++++++++++++++------------ gcc/tree-scalar-evolution.h | 9 +- gcc/tree-ssa-loop-niter.cc | 16 +- gcc/tree-ssa-loop-niter.h | 2 +- gcc/tree-ssa-loop.h | 4 + 7 files changed, 292 insertions(+), 137 deletions(-) diff --git a/gcc/tree-chrec.cc b/gcc/tree-chrec.cc index 9869389a7b9..2b1659eab76 100644 --- a/gcc/tree-chrec.cc +++ b/gcc/tree-chrec.cc @@ -1421,13 +1421,18 @@ nb_vars_in_chrec (tree chrec) 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. */ + FROM is the source variable converted if it's not NULL. + If NOWRAP_BOUND is nonzero, pass it on to scev_probably_wraps_p etc. + to have them determine the bound below which no wrapping occurs. + Most other functions just forward NOWRAP_BOUND, therefore it is not + documented everywhere. + The function returns true if the conversion succeeded, false otherwise. */ bool convert_affine_scev (class loop *loop, tree type, tree *base, tree *step, gimple *at_stmt, - bool use_overflow_semantics, tree from) + bool use_overflow_semantics, tree from, + tree *nowrap_bound) { tree ct = TREE_TYPE (*step); bool enforce_overflow_semantics; @@ -1452,6 +1457,11 @@ convert_affine_scev (class loop *loop, tree type, happen. */ must_check_src_overflow = TYPE_PRECISION (ct) < TYPE_PRECISION (type); + /* MUST_CHECK_SRC_OVERFLOW implies chrec_convert_aggressive later + which can prove "no wrap" without assumptions. */ + if (!must_check_src_overflow) + nowrap_bound = NULL; + enforce_overflow_semantics = (use_overflow_semantics && nowrap_type_p (type)); if (enforce_overflow_semantics) @@ -1487,10 +1497,11 @@ convert_affine_scev (class loop *loop, tree type, if (must_check_src_overflow && scev_probably_wraps_p (from, *base, *step, at_stmt, loop, - use_overflow_semantics)) + use_overflow_semantics, nowrap_bound)) return false; - new_base = chrec_convert (type, *base, at_stmt, use_overflow_semantics); + new_base = chrec_convert (type, *base, at_stmt, nowrap_bound, + use_overflow_semantics); /* The step must be sign extended, regardless of the signedness of CT and TYPE. This only needs to be handled specially when CT is unsigned -- to avoid e.g. unsigned char [100, +, 255] @@ -1501,10 +1512,10 @@ convert_affine_scev (class loop *loop, tree type, if (TYPE_PRECISION (step_type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct)) { tree signed_ct = signed_type_for (ct); - new_step = chrec_convert (signed_ct, new_step, at_stmt, + new_step = chrec_convert (signed_ct, new_step, at_stmt, nowrap_bound, use_overflow_semantics); } - new_step = chrec_convert (step_type, new_step, at_stmt, + new_step = chrec_convert (step_type, new_step, at_stmt, nowrap_bound, use_overflow_semantics); if (automatically_generated_chrec_p (new_base) @@ -1515,7 +1526,7 @@ convert_affine_scev (class loop *loop, tree type, /* 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 (NULL_TREE, new_base, new_step, - at_stmt, loop, false)) + at_stmt, loop, false, nowrap_bound)) return false; *base = new_base; @@ -1528,12 +1539,12 @@ convert_affine_scev (class loop *loop, tree type, The increment for a pointer type is always sizetype. */ tree -chrec_convert_rhs (tree type, tree chrec, gimple *at_stmt) +chrec_convert_rhs (tree type, tree chrec, gimple *at_stmt, tree *nowrap_bound) { if (POINTER_TYPE_P (type)) type = sizetype; - return chrec_convert (type, chrec, at_stmt); + return chrec_convert (type, chrec, at_stmt, nowrap_bound); } /* Convert CHREC to TYPE. When the analyzer knows the context in @@ -1552,7 +1563,7 @@ chrec_convert_rhs (tree type, tree chrec, gimple *at_stmt) static tree chrec_convert_1 (tree type, tree chrec, gimple *at_stmt, - bool use_overflow_semantics, tree from) + tree *nowrap_bound, bool use_overflow_semantics, tree from) { tree ct, res; tree base, step; @@ -1573,7 +1584,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, from)) + use_overflow_semantics, from, nowrap_bound)) return build_polynomial_chrec (loop->num, base, step); /* If we cannot propagate the cast inside the chrec, just keep the cast. */ @@ -1606,7 +1617,8 @@ keep_cast: CHREC_LEFT (chrec)), fold_convert (utype, CHREC_RIGHT (chrec))); - res = chrec_convert_1 (type, res, at_stmt, use_overflow_semantics, from); + res = chrec_convert_1 (type, res, at_stmt, nowrap_bound, + use_overflow_semantics, from); } /* Similar perform the trick that (unsigned T)(base + step) can be folded to ((unsigned T)x + (unsigned T)step). */ @@ -1631,7 +1643,8 @@ keep_cast: CHREC_LEFT (chrec)), fold_convert (type, CHREC_RIGHT (chrec))); - res = chrec_convert_1 (type, res, at_stmt, use_overflow_semantics, from); + res = chrec_convert_1 (type, res, at_stmt, nowrap_bound, + use_overflow_semantics, from); } else res = fold_convert (type, chrec); @@ -1677,6 +1690,11 @@ keep_cast: {(uint) 0, +, (uint) 260} + If NOWRAP_BOUND is nonzero it is used to store the bound below which + no wrapping occurs. Here as well as in many other similar functions, + it is just passed through to other functions and thus not documented + everywhere. + 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 @@ -1686,9 +1704,10 @@ keep_cast: tree chrec_convert (tree type, tree chrec, gimple *at_stmt, - bool use_overflow_semantics, tree from) + tree *nowrap_bound, bool use_overflow_semantics, tree from) { - return chrec_convert_1 (type, chrec, at_stmt, use_overflow_semantics, from); + return chrec_convert_1 (type, chrec, at_stmt, nowrap_bound, + 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 7777ff50942..9fdfaac0e15 100644 --- a/gcc/tree-chrec.h +++ b/gcc/tree-chrec.h @@ -62,8 +62,9 @@ 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, tree = NULL); -extern tree chrec_convert_rhs (tree, tree, gimple * = NULL); +extern tree chrec_convert (tree, tree, gimple *, tree * = nullptr, + bool = true, tree = NULL); +extern tree chrec_convert_rhs (tree, tree, gimple * = NULL, tree * = nullptr); extern tree chrec_convert_aggressive (tree, tree, bool *); /* Operations. */ @@ -78,7 +79,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 (class loop *, tree, tree *, tree *, gimple *, - bool, tree = NULL); + bool, tree = NULL, tree * = nullptr); /* Observers. */ extern bool eq_evolutions_p (const_tree, const_tree); diff --git a/gcc/tree-scalar-evolution.cc b/gcc/tree-scalar-evolution.cc index 80f24ec86a5..91e6aa376aa 100644 --- a/gcc/tree-scalar-evolution.cc +++ b/gcc/tree-scalar-evolution.cc @@ -286,18 +286,22 @@ along with GCC; see the file COPYING3. If not see #include "case-cfn-macros.h" #include "tree-eh.h" -static tree analyze_scalar_evolution_1 (class loop *, tree); +static tree analyze_scalar_evolution_1 (class loop *, tree, tree * = nullptr); static tree analyze_scalar_evolution_for_address_of (class loop *loop, - tree var); + tree var, + tree * = nullptr); /* The cached information about an SSA name with version NAME_VERSION, claiming that below basic block with index INSTANTIATED_BELOW, the - value of the SSA name can be expressed as CHREC. */ + value of the SSA name can be expressed as CHREC. + NOWRAP_BOUND can store an assumption to guarantee that the SSA name + doesn't wrap. */ struct GTY((for_user)) scev_info_str { unsigned int name_version; int instantiated_below; tree chrec; + tree nowrap_bound; }; /* Counters for the scev database. */ @@ -310,7 +314,10 @@ struct scev_info_hasher : ggc_ptr_hash<scev_info_str> static bool equal (const scev_info_str *a, const scev_info_str *b); }; +/* Keep regular hash entries and entries that have nowrap assumptions separate + by using two hash tables. */ static GTY (()) hash_table<scev_info_hasher> *scalar_evolution_info; +static GTY (()) hash_table<scev_info_hasher> *scalar_evolution_nowrap_info; /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */ @@ -322,8 +329,9 @@ new_scev_info_str (basic_block instantiated_below, tree var) res = ggc_alloc<scev_info_str> (); res->name_version = SSA_NAME_VERSION (var); - res->chrec = chrec_not_analyzed_yet; res->instantiated_below = instantiated_below->index; + res->chrec = chrec_not_analyzed_yet; + res->nowrap_bound = NULL_TREE; return res; } @@ -333,7 +341,7 @@ new_scev_info_str (basic_block instantiated_below, tree var) hashval_t scev_info_hasher::hash (scev_info_str *elt) { - return elt->name_version ^ elt->instantiated_below; + return (elt->name_version ^ elt->instantiated_below); } /* Compares database elements E1 and E2. */ @@ -348,21 +356,24 @@ scev_info_hasher::equal (const scev_info_str *elt1, const scev_info_str *elt2) /* Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block. A first query on VAR returns chrec_not_analyzed_yet. */ -static tree * -find_var_scev_info (basic_block instantiated_below, tree var) +static scev_info_str * +find_var_scev_info (basic_block instantiated_below, tree var, + bool nowrap_assumption_p) { - struct scev_info_str *res; struct scev_info_str tmp; tmp.name_version = SSA_NAME_VERSION (var); tmp.instantiated_below = instantiated_below->index; - scev_info_str **slot = scalar_evolution_info->find_slot (&tmp, INSERT); + scev_info_str **slot; + if (!nowrap_assumption_p) + slot = scalar_evolution_info->find_slot (&tmp, INSERT); + else + slot = scalar_evolution_nowrap_info->find_slot (&tmp, INSERT); if (!*slot) *slot = new_scev_info_str (instantiated_below, var); - res = *slot; - return &res->chrec; + return *slot; } @@ -396,6 +407,27 @@ instantiate_cache_type::~instantiate_cache_type () or resolve_mixers call. */ static instantiate_cache_type *global_cache; +/* Build a combined bound from BASE and BOUND by taking the minimum + of both. The result is stored in BASE. */ + +void +scev_combine_nowrap_bounds (tree *base, tree bound) +{ + if (!base || !bound) + return; + if (!*base) + { + *base = bound; + return; + } + + tree t1 = TREE_TYPE (*base); + tree t2 = TREE_TYPE (bound); + tree wide_type = TYPE_PRECISION (t1) >= TYPE_PRECISION (t2) ? t1 : t2; + *base = fold_build2 (MIN_EXPR, wide_type, + fold_convert (wide_type, *base), + fold_convert (wide_type, bound)); +} /* Return true when PHI is a loop-phi-node. */ @@ -493,14 +525,16 @@ compute_overall_effect_of_inner_loop (class loop *loop, tree evolution_fn) /* Associate CHREC to SCALAR. */ static void -set_scalar_evolution (basic_block instantiated_below, tree scalar, tree chrec) +set_scalar_evolution (basic_block instantiated_below, tree scalar, tree chrec, + tree *nowrap_bound) { - tree *scalar_info; + scev_info_str *scalar_info; if (TREE_CODE (scalar) != SSA_NAME) return; - scalar_info = find_var_scev_info (instantiated_below, scalar); + scalar_info = find_var_scev_info (instantiated_below, scalar, + nowrap_bound != nullptr); if (dump_file) { @@ -519,14 +553,17 @@ set_scalar_evolution (basic_block instantiated_below, tree scalar, tree chrec) nb_set_scev++; } - *scalar_info = chrec; + scalar_info->chrec = chrec; + if (nowrap_bound) + scalar_info->nowrap_bound = *nowrap_bound; } /* Retrieve the chrec associated to SCALAR instantiated below INSTANTIATED_BELOW block. */ static tree -get_scalar_evolution (basic_block instantiated_below, tree scalar) +get_scalar_evolution (basic_block instantiated_below, tree scalar, + tree *nowrap_bound) { tree res; @@ -551,10 +588,18 @@ get_scalar_evolution (basic_block instantiated_below, tree scalar) switch (TREE_CODE (scalar)) { case SSA_NAME: - if (SSA_NAME_IS_DEFAULT_DEF (scalar)) + if (SSA_NAME_IS_DEFAULT_DEF (scalar)) res = scalar; else - res = *find_var_scev_info (instantiated_below, scalar); + { + scev_info_str *info + = find_var_scev_info (instantiated_below, scalar, + nowrap_bound != nullptr); + res = info->chrec; + if (info->nowrap_bound + && res != chrec_not_analyzed_yet) + scev_combine_nowrap_bounds (nowrap_bound, info->nowrap_bound); + } break; case REAL_CST: @@ -1369,12 +1414,18 @@ get_loop_exit_condition (const_edge exit_edge) See PR41488. */ static tree -simplify_peeled_chrec (class loop *loop, tree arg, tree init_cond) +simplify_peeled_chrec (class loop *loop, tree arg, tree init_cond, + tree *nowrap_bound = nullptr) { aff_tree aff1, aff2; tree ev, left, right, type, step_val; hash_map<tree, name_expansion *> *peeled_chrec_map = NULL; + tree local_nowrap_bound = NULL_TREE; + tree *bound = nullptr; + if (nowrap_bound) + bound = &local_nowrap_bound; + ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, arg)); if (ev == NULL_TREE) return chrec_dont_know; @@ -1398,7 +1449,7 @@ simplify_peeled_chrec (class loop *loop, tree arg, tree init_cond) if (TREE_CODE (left_before) == INTEGER_CST && wi::to_widest (init_cond) == wi::to_widest (left_before) && !scev_probably_wraps_p (NULL_TREE, left_before, right, NULL, - loop, false)) + loop, false, bound)) { tree tp = TREE_TYPE (right); @@ -1407,10 +1458,11 @@ simplify_peeled_chrec (class loop *loop, tree arg, tree init_cond) if (TYPE_UNSIGNED (tp)) right = fold_convert (signed_type_for (tp), right); - return build_polynomial_chrec (loop->num, init_cond, - chrec_convert (TREE_TYPE (ev), - right, NULL, - false, NULL_TREE)); + scev_combine_nowrap_bounds (nowrap_bound, local_nowrap_bound); + return build_polynomial_chrec + (loop->num, init_cond, chrec_convert (TREE_TYPE (ev), right, NULL, + nullptr, false, + NULL_TREE)); } return chrec_dont_know; } @@ -1430,6 +1482,7 @@ simplify_peeled_chrec (class loop *loop, tree arg, tree init_cond) if (dump_file && (dump_flags & TDF_SCEV)) fprintf (dump_file, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n"); + scev_combine_nowrap_bounds (nowrap_bound, local_nowrap_bound); return build_polynomial_chrec (loop->num, init_cond, right); } @@ -1452,6 +1505,7 @@ simplify_peeled_chrec (class loop *loop, tree arg, tree init_cond) if (dump_file && (dump_flags & TDF_SCEV)) fprintf (dump_file, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n"); + scev_combine_nowrap_bounds (nowrap_bound, local_nowrap_bound); return build_polynomial_chrec (loop->num, init_cond, right); } return chrec_dont_know; @@ -1462,7 +1516,8 @@ simplify_peeled_chrec (class loop *loop, tree arg, tree init_cond) static tree analyze_evolution_in_loop (gphi *loop_phi_node, - tree init_cond) + tree init_cond, + tree *nowrap_bound = nullptr) { int i, n = gimple_phi_num_args (loop_phi_node); tree evolution_function = chrec_not_analyzed_yet; @@ -1525,7 +1580,8 @@ analyze_evolution_in_loop (gphi *loop_phi_node, if (simplify_peeled_chrec_p && TREE_CODE (arg) == SSA_NAME) { simplify_peeled_chrec_p = false; - ev_fn = simplify_peeled_chrec (loop, arg, init_cond); + ev_fn = simplify_peeled_chrec + (loop, arg, init_cond, nowrap_bound); simplify_peeled_chrec_p = true; } } @@ -1648,7 +1704,8 @@ analyze_initial_condition (gphi *loop_phi_node) /* Analyze the scalar evolution for LOOP_PHI_NODE. */ static tree -interpret_loop_phi (class loop *loop, gphi *loop_phi_node) +interpret_loop_phi (class loop *loop, gphi *loop_phi_node, + tree *nowrap_bound = nullptr) { class loop *phi_loop = loop_containing_stmt (loop_phi_node); tree init_cond; @@ -1657,7 +1714,7 @@ interpret_loop_phi (class loop *loop, gphi *loop_phi_node) /* Otherwise really interpret the loop phi. */ init_cond = analyze_initial_condition (loop_phi_node); - return analyze_evolution_in_loop (loop_phi_node, init_cond); + return analyze_evolution_in_loop (loop_phi_node, init_cond, nowrap_bound); } /* This function merges the branches of a condition-phi-node, @@ -1665,7 +1722,8 @@ interpret_loop_phi (class loop *loop, gphi *loop_phi_node) analyzed. */ static tree -interpret_condition_phi (class loop *loop, gphi *condition_phi) +interpret_condition_phi (class loop *loop, gphi *condition_phi, + tree *nowrap_bound) { int i, n = gimple_phi_num_args (condition_phi); tree res = chrec_not_analyzed_yet; @@ -1681,7 +1739,7 @@ interpret_condition_phi (class loop *loop, gphi *condition_phi) } branch_chrec = analyze_scalar_evolution - (loop, PHI_ARG_DEF (condition_phi, i)); + (loop, PHI_ARG_DEF (condition_phi, i), nowrap_bound); res = chrec_merge (res, branch_chrec); if (res == chrec_dont_know) @@ -1700,7 +1758,8 @@ interpret_condition_phi (class loop *loop, gphi *condition_phi) static tree interpret_rhs_expr (class loop *loop, gimple *at_stmt, - tree type, tree rhs1, enum tree_code code, tree rhs2) + tree type, tree rhs1, enum tree_code code, tree rhs2, + tree *nowrap_bound = nullptr) { tree res, chrec1, chrec2, ctype; gimple *def; @@ -1711,8 +1770,10 @@ interpret_rhs_expr (class loop *loop, gimple *at_stmt, return chrec_convert (type, rhs1, at_stmt); if (code == SSA_NAME) - return chrec_convert (type, analyze_scalar_evolution (loop, rhs1), - at_stmt); + return chrec_convert (type, + analyze_scalar_evolution (loop, rhs1, + nowrap_bound), + at_stmt, nowrap_bound); } switch (code) @@ -1738,25 +1799,28 @@ interpret_rhs_expr (class loop *loop, gimple *at_stmt, rhs2 = TREE_OPERAND (base, 1); rhs1 = TREE_OPERAND (base, 0); - chrec1 = analyze_scalar_evolution (loop, rhs1); - chrec2 = analyze_scalar_evolution (loop, rhs2); - chrec1 = chrec_convert (type, chrec1, at_stmt); - chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt); + chrec1 = analyze_scalar_evolution (loop, rhs1, nowrap_bound); + chrec2 = analyze_scalar_evolution (loop, rhs2, nowrap_bound); + chrec1 = chrec_convert (type, chrec1, at_stmt, nowrap_bound); + chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt, + nowrap_bound); chrec1 = instantiate_parameters (loop, chrec1); chrec2 = instantiate_parameters (loop, chrec2); res = chrec_fold_plus (type, chrec1, chrec2); } else { - chrec1 = analyze_scalar_evolution_for_address_of (loop, base); - chrec1 = chrec_convert (type, chrec1, at_stmt); + chrec1 = analyze_scalar_evolution_for_address_of (loop, base, + nowrap_bound); + chrec1 = chrec_convert (type, chrec1, at_stmt, nowrap_bound); res = chrec1; } if (offset != NULL_TREE) { - chrec2 = analyze_scalar_evolution (loop, offset); - chrec2 = chrec_convert (TREE_TYPE (offset), chrec2, at_stmt); + chrec2 = analyze_scalar_evolution (loop, offset, nowrap_bound); + chrec2 = chrec_convert (TREE_TYPE (offset), chrec2, at_stmt, + nowrap_bound); chrec2 = instantiate_parameters (loop, chrec2); res = chrec_fold_plus (type, res, chrec2); } @@ -1764,8 +1828,9 @@ interpret_rhs_expr (class loop *loop, gimple *at_stmt, if (maybe_ne (bitpos, 0)) { unitpos = size_int (exact_div (bitpos, BITS_PER_UNIT)); - chrec3 = analyze_scalar_evolution (loop, unitpos); - chrec3 = chrec_convert (TREE_TYPE (unitpos), chrec3, at_stmt); + chrec3 = analyze_scalar_evolution (loop, unitpos, nowrap_bound); + chrec3 = chrec_convert (TREE_TYPE (unitpos), chrec3, at_stmt, + nowrap_bound); chrec3 = instantiate_parameters (loop, chrec3); res = chrec_fold_plus (type, res, chrec3); } @@ -1775,10 +1840,11 @@ interpret_rhs_expr (class loop *loop, gimple *at_stmt, break; case POINTER_PLUS_EXPR: - chrec1 = analyze_scalar_evolution (loop, rhs1); - chrec2 = analyze_scalar_evolution (loop, rhs2); - chrec1 = chrec_convert (type, chrec1, at_stmt); - chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt); + chrec1 = analyze_scalar_evolution (loop, rhs1, nowrap_bound); + chrec2 = analyze_scalar_evolution (loop, rhs2, nowrap_bound); + chrec1 = chrec_convert (type, chrec1, at_stmt, nowrap_bound); + chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt, + nowrap_bound); chrec1 = instantiate_parameters (loop, chrec1); chrec2 = instantiate_parameters (loop, chrec2); res = chrec_fold_plus (type, chrec1, chrec2); @@ -1787,20 +1853,20 @@ interpret_rhs_expr (class loop *loop, gimple *at_stmt, case POINTER_DIFF_EXPR: { tree utype = unsigned_type_for (type); - chrec1 = analyze_scalar_evolution (loop, rhs1); - chrec2 = analyze_scalar_evolution (loop, rhs2); - chrec1 = chrec_convert (utype, chrec1, at_stmt); - chrec2 = chrec_convert (utype, chrec2, at_stmt); + chrec1 = analyze_scalar_evolution (loop, rhs1, nowrap_bound); + chrec2 = analyze_scalar_evolution (loop, rhs2, nowrap_bound); + chrec1 = chrec_convert (utype, chrec1, at_stmt, nowrap_bound); + chrec2 = chrec_convert (utype, chrec2, at_stmt, nowrap_bound); chrec1 = instantiate_parameters (loop, chrec1); chrec2 = instantiate_parameters (loop, chrec2); res = chrec_fold_minus (utype, chrec1, chrec2); - res = chrec_convert (type, res, at_stmt); + res = chrec_convert (type, res, at_stmt, nowrap_bound); break; } case PLUS_EXPR: - chrec1 = analyze_scalar_evolution (loop, rhs1); - chrec2 = analyze_scalar_evolution (loop, rhs2); + chrec1 = analyze_scalar_evolution (loop, rhs1, nowrap_bound); + chrec2 = analyze_scalar_evolution (loop, rhs2, nowrap_bound); ctype = type; /* When the stmt is conditionally executed re-write the CHREC into a form that has well-defined behavior on overflow. */ @@ -1810,18 +1876,18 @@ interpret_rhs_expr (class loop *loop, gimple *at_stmt, && ! dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (at_stmt))) ctype = unsigned_type_for (type); - chrec1 = chrec_convert (ctype, chrec1, at_stmt); - chrec2 = chrec_convert (ctype, chrec2, at_stmt); + chrec1 = chrec_convert (ctype, chrec1, at_stmt, nowrap_bound); + chrec2 = chrec_convert (ctype, chrec2, at_stmt, nowrap_bound); chrec1 = instantiate_parameters (loop, chrec1); chrec2 = instantiate_parameters (loop, chrec2); res = chrec_fold_plus (ctype, chrec1, chrec2); if (type != ctype) - res = chrec_convert (type, res, at_stmt); + res = chrec_convert (type, res, at_stmt, nowrap_bound); break; case MINUS_EXPR: - chrec1 = analyze_scalar_evolution (loop, rhs1); - chrec2 = analyze_scalar_evolution (loop, rhs2); + chrec1 = analyze_scalar_evolution (loop, rhs1, nowrap_bound); + chrec2 = analyze_scalar_evolution (loop, rhs2, nowrap_bound); ctype = type; /* When the stmt is conditionally executed re-write the CHREC into a form that has well-defined behavior on overflow. */ @@ -1831,17 +1897,17 @@ interpret_rhs_expr (class loop *loop, gimple *at_stmt, && ! dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (at_stmt))) ctype = unsigned_type_for (type); - chrec1 = chrec_convert (ctype, chrec1, at_stmt); - chrec2 = chrec_convert (ctype, chrec2, at_stmt); + chrec1 = chrec_convert (ctype, chrec1, at_stmt, nowrap_bound); + chrec2 = chrec_convert (ctype, chrec2, at_stmt, nowrap_bound); chrec1 = instantiate_parameters (loop, chrec1); chrec2 = instantiate_parameters (loop, chrec2); res = chrec_fold_minus (ctype, chrec1, chrec2); if (type != ctype) - res = chrec_convert (type, res, at_stmt); + res = chrec_convert (type, res, at_stmt, nowrap_bound); break; case NEGATE_EXPR: - chrec1 = analyze_scalar_evolution (loop, rhs1); + chrec1 = analyze_scalar_evolution (loop, rhs1, nowrap_bound); ctype = type; /* When the stmt is conditionally executed re-write the CHREC into a form that has well-defined behavior on overflow. */ @@ -1851,19 +1917,19 @@ interpret_rhs_expr (class loop *loop, gimple *at_stmt, && ! dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (at_stmt))) ctype = unsigned_type_for (type); - chrec1 = chrec_convert (ctype, chrec1, at_stmt); + chrec1 = chrec_convert (ctype, chrec1, at_stmt, nowrap_bound); /* TYPE may be integer, real or complex, so use fold_convert. */ chrec1 = instantiate_parameters (loop, chrec1); res = chrec_fold_multiply (ctype, chrec1, fold_convert (ctype, integer_minus_one_node)); if (type != ctype) - res = chrec_convert (type, res, at_stmt); + res = chrec_convert (type, res, at_stmt, nowrap_bound); break; case BIT_NOT_EXPR: /* Handle ~X as -1 - X. */ - chrec1 = analyze_scalar_evolution (loop, rhs1); - chrec1 = chrec_convert (type, chrec1, at_stmt); + chrec1 = analyze_scalar_evolution (loop, rhs1, nowrap_bound); + chrec1 = chrec_convert (type, chrec1, at_stmt, nowrap_bound); chrec1 = instantiate_parameters (loop, chrec1); res = chrec_fold_minus (type, fold_convert (type, integer_minus_one_node), @@ -1871,8 +1937,8 @@ interpret_rhs_expr (class loop *loop, gimple *at_stmt, break; case MULT_EXPR: - chrec1 = analyze_scalar_evolution (loop, rhs1); - chrec2 = analyze_scalar_evolution (loop, rhs2); + chrec1 = analyze_scalar_evolution (loop, rhs1, nowrap_bound); + chrec2 = analyze_scalar_evolution (loop, rhs2, nowrap_bound); ctype = type; /* When the stmt is conditionally executed re-write the CHREC into a form that has well-defined behavior on overflow. */ @@ -1882,29 +1948,29 @@ interpret_rhs_expr (class loop *loop, gimple *at_stmt, && ! dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (at_stmt))) ctype = unsigned_type_for (type); - chrec1 = chrec_convert (ctype, chrec1, at_stmt); - chrec2 = chrec_convert (ctype, chrec2, at_stmt); + chrec1 = chrec_convert (ctype, chrec1, at_stmt, nowrap_bound); + chrec2 = chrec_convert (ctype, chrec2, at_stmt, nowrap_bound); chrec1 = instantiate_parameters (loop, chrec1); chrec2 = instantiate_parameters (loop, chrec2); res = chrec_fold_multiply (ctype, chrec1, chrec2); if (type != ctype) - res = chrec_convert (type, res, at_stmt); + res = chrec_convert (type, res, at_stmt, nowrap_bound); break; case LSHIFT_EXPR: { /* Handle A<<B as A * (1<<B). */ tree uns = unsigned_type_for (type); - chrec1 = analyze_scalar_evolution (loop, rhs1); - chrec2 = analyze_scalar_evolution (loop, rhs2); - chrec1 = chrec_convert (uns, chrec1, at_stmt); + chrec1 = analyze_scalar_evolution (loop, rhs1, nowrap_bound); + chrec2 = analyze_scalar_evolution (loop, rhs2, nowrap_bound); + chrec1 = chrec_convert (uns, chrec1, at_stmt, nowrap_bound); chrec1 = instantiate_parameters (loop, chrec1); chrec2 = instantiate_parameters (loop, chrec2); tree one = build_int_cst (uns, 1); chrec2 = fold_build2 (LSHIFT_EXPR, uns, one, chrec2); res = chrec_fold_multiply (uns, chrec1, chrec2); - res = chrec_convert (type, res, at_stmt); + res = chrec_convert (type, res, at_stmt, nowrap_bound); } break; @@ -1928,11 +1994,12 @@ interpret_rhs_expr (class loop *loop, gimple *at_stmt, chrec1 = interpret_rhs_expr (loop, at_stmt, utype, gimple_assign_rhs1 (def), gimple_assign_rhs_code (def), - gimple_assign_rhs2 (def)); + gimple_assign_rhs2 (def), + nowrap_bound); } else - chrec1 = analyze_scalar_evolution (loop, rhs1); - res = chrec_convert (type, chrec1, at_stmt, true, rhs1); + chrec1 = analyze_scalar_evolution (loop, rhs1, nowrap_bound); + res = chrec_convert (type, chrec1, at_stmt, nowrap_bound, true, rhs1); break; case BIT_AND_EXPR: @@ -1957,9 +2024,11 @@ interpret_rhs_expr (class loop *loop, gimple *at_stmt, if (TYPE_PRECISION (utype) < TYPE_PRECISION (TREE_TYPE (rhs1))) { - chrec1 = analyze_scalar_evolution (loop, rhs1); - chrec1 = chrec_convert (utype, chrec1, at_stmt); - res = chrec_convert (TREE_TYPE (rhs1), chrec1, at_stmt); + chrec1 = analyze_scalar_evolution (loop, rhs1, nowrap_bound); + chrec1 = chrec_convert (utype, chrec1, at_stmt, + nowrap_bound); + res = chrec_convert (TREE_TYPE (rhs1), chrec1, at_stmt, + nowrap_bound); } } } @@ -1976,7 +2045,8 @@ interpret_rhs_expr (class loop *loop, gimple *at_stmt, /* Interpret the expression EXPR. */ static tree -interpret_expr (class loop *loop, gimple *at_stmt, tree expr) +interpret_expr (class loop *loop, gimple *at_stmt, tree expr, + tree *nowrap_bound) { enum tree_code code; tree type = TREE_TYPE (expr), op0, op1; @@ -1992,20 +2062,20 @@ interpret_expr (class loop *loop, gimple *at_stmt, tree expr) extract_ops_from_tree (expr, &code, &op0, &op1); return interpret_rhs_expr (loop, at_stmt, type, - op0, code, op1); + op0, code, op1, nowrap_bound); } /* Interpret the rhs of the assignment STMT. */ static tree -interpret_gimple_assign (class loop *loop, gimple *stmt) +interpret_gimple_assign (class loop *loop, gimple *stmt, tree *nowrap_bound) { tree type = TREE_TYPE (gimple_assign_lhs (stmt)); enum tree_code code = gimple_assign_rhs_code (stmt); return interpret_rhs_expr (loop, stmt, type, gimple_assign_rhs1 (stmt), code, - gimple_assign_rhs2 (stmt)); + gimple_assign_rhs2 (stmt), nowrap_bound); } @@ -2019,7 +2089,7 @@ interpret_gimple_assign (class loop *loop, gimple *stmt) /* Helper recursive function. */ static tree -analyze_scalar_evolution_1 (class loop *loop, tree var) +analyze_scalar_evolution_1 (class loop *loop, tree var, tree *nowrap_bound) { gimple *def; basic_block bb; @@ -2027,7 +2097,12 @@ analyze_scalar_evolution_1 (class loop *loop, tree var) tree res; if (TREE_CODE (var) != SSA_NAME) - return interpret_expr (loop, NULL, var); + return interpret_expr (loop, NULL, var, nowrap_bound); + + tree local_nowrap_bound = NULL_TREE; + tree *bound = nullptr; + if (nowrap_bound) + bound = &local_nowrap_bound; def = SSA_NAME_DEF_STMT (var); bb = gimple_bb (def); @@ -2042,26 +2117,26 @@ analyze_scalar_evolution_1 (class loop *loop, tree var) if (loop != def_loop) { - res = analyze_scalar_evolution_1 (def_loop, var); + res = analyze_scalar_evolution_1 (def_loop, var, bound); class loop *loop_to_skip = superloop_at_depth (def_loop, loop_depth (loop) + 1); res = compute_overall_effect_of_inner_loop (loop_to_skip, res); if (chrec_contains_symbols_defined_in_loop (res, loop->num)) - res = analyze_scalar_evolution_1 (loop, res); + res = analyze_scalar_evolution_1 (loop, res, bound); goto set_and_end; } switch (gimple_code (def)) { case GIMPLE_ASSIGN: - res = interpret_gimple_assign (loop, def); + res = interpret_gimple_assign (loop, def, bound); break; case GIMPLE_PHI: if (loop_phi_node_p (def)) - res = interpret_loop_phi (loop, as_a <gphi *> (def)); + res = interpret_loop_phi (loop, as_a <gphi *> (def), bound); else - res = interpret_condition_phi (loop, as_a <gphi *> (def)); + res = interpret_condition_phi (loop, as_a <gphi *> (def), bound); break; default: @@ -2076,7 +2151,9 @@ analyze_scalar_evolution_1 (class loop *loop, tree var) res = var; if (loop == def_loop) - set_scalar_evolution (block_before_loop (loop), var, res); + set_scalar_evolution (block_before_loop (loop), var, res, bound); + + scev_combine_nowrap_bounds (nowrap_bound, local_nowrap_bound); return res; } @@ -2095,7 +2172,7 @@ analyze_scalar_evolution_1 (class loop *loop, tree var) */ tree -analyze_scalar_evolution (class loop *loop, tree var) +analyze_scalar_evolution (class loop *loop, tree var, tree *nowrap_bound) { tree res; @@ -2112,7 +2189,7 @@ analyze_scalar_evolution (class loop *loop, tree var) fprintf (dump_file, ")\n"); } - res = get_scalar_evolution (block_before_loop (loop), var); + res = get_scalar_evolution (block_before_loop (loop), var, nowrap_bound); if (res == chrec_not_analyzed_yet) { /* We'll recurse into instantiate_scev, avoid tearing down the @@ -2123,7 +2200,7 @@ analyze_scalar_evolution (class loop *loop, tree var) global_cache = new instantiate_cache_type; destr = true; } - res = analyze_scalar_evolution_1 (loop, var); + res = analyze_scalar_evolution_1 (loop, var, nowrap_bound); if (destr) { delete global_cache; @@ -2164,9 +2241,11 @@ bool nonwrapping_chrec_p (tree chrec) /* Analyzes and returns the scalar evolution of VAR address in LOOP. */ static tree -analyze_scalar_evolution_for_address_of (class loop *loop, tree var) +analyze_scalar_evolution_for_address_of (class loop *loop, tree var, + tree *nowrap_bound) { - return analyze_scalar_evolution (loop, build_fold_addr_expr (var)); + return analyze_scalar_evolution (loop, build_fold_addr_expr (var), + nowrap_bound); } /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to @@ -2221,7 +2300,8 @@ analyze_scalar_evolution_for_address_of (class loop *loop, tree var) static tree analyze_scalar_evolution_in_loop (class loop *wrto_loop, class loop *use_loop, - tree version, bool *folded_casts) + tree version, bool *folded_casts, + tree *nowrap_bound = nullptr) { bool val = false; tree ev = version, tmp; @@ -2249,7 +2329,7 @@ analyze_scalar_evolution_in_loop (class loop *wrto_loop, class loop *use_loop, *folded_casts = false; while (1) { - tmp = analyze_scalar_evolution (use_loop, ev); + tmp = analyze_scalar_evolution (use_loop, ev, nowrap_bound); ev = resolve_mixers (use_loop, tmp, folded_casts); if (use_loop == wrto_loop) @@ -2997,6 +3077,8 @@ dump_chrecs_stats (FILE *file, struct chrec_stats *stats) fprintf (file, "-----------------------------------------\n"); fprintf (file, "%d\tchrecs in the scev database\n", (int) scalar_evolution_info->elements ()); + fprintf (file, "%d\tchrecs in the nowrap scev database\n", + (int) scalar_evolution_nowrap_info->elements ()); fprintf (file, "%d\tsets in the scev database\n", nb_set_scev); fprintf (file, "%d\tgets in the scev database\n", nb_get_scev); fprintf (file, "-----------------------------------------\n"); @@ -3079,6 +3161,9 @@ gather_stats_on_scev_database (void) FOR_EACH_HASH_TABLE_ELEMENT (*scalar_evolution_info, elt, scev_info_str *, iter) gather_chrec_stats (elt->chrec, &stats); + FOR_EACH_HASH_TABLE_ELEMENT (*scalar_evolution_nowrap_info, elt, + scev_info_str *, iter) + gather_chrec_stats (elt->chrec, &stats); dump_chrecs_stats (dump_file, &stats); } @@ -3093,6 +3178,7 @@ scev_initialize (void) && loops_state_satisfies_p (cfun, LOOPS_NORMAL)); scalar_evolution_info = hash_table<scev_info_hasher>::create_ggc (100); + scalar_evolution_nowrap_info = hash_table<scev_info_hasher>::create_ggc (100); for (auto loop : loops_list (cfun, 0)) loop->nb_iterations = NULL_TREE; @@ -3103,7 +3189,7 @@ scev_initialize (void) bool scev_initialized_p (void) { - return scalar_evolution_info != NULL; + return scalar_evolution_info != NULL && scalar_evolution_nowrap_info != NULL; } /* Cleans up the information cached by the scalar evolutions analysis @@ -3112,10 +3198,13 @@ scev_initialized_p (void) void scev_reset_htab (void) { - if (!scalar_evolution_info) + if (!scalar_evolution_info && !scalar_evolution_nowrap_info) return; - scalar_evolution_info->empty (); + if (scalar_evolution_info) + scalar_evolution_info->empty (); + if (scalar_evolution_nowrap_info) + scalar_evolution_nowrap_info->empty (); } /* Cleans up the information cached by the scalar evolutions analysis @@ -3288,12 +3377,17 @@ derive_simple_iv_with_niters (tree ev, tree *niters) The derived condition normally is the maximum number the inner iv can iterate, and will be stored in IV_NITERS. This is useful in loop niter analysis, to derive break conditions when a loop must terminate, when is - infinite. */ + infinite. + + If ALLOW_WRAPPING is true, let scev analysis continue rather than stop if + an IV might wrap. Store the bound under which no wrapping occurs in IV's + nowrap_bound. */ bool simple_iv_with_niters (class loop *wrto_loop, class loop *use_loop, tree op, affine_iv *iv, tree *iv_niters, - bool allow_nonconstant_step) + bool allow_nonconstant_step, + bool allow_wrapping) { enum tree_code code; tree type, ev, base, e; @@ -3303,14 +3397,23 @@ simple_iv_with_niters (class loop *wrto_loop, class loop *use_loop, iv->base = NULL_TREE; iv->step = NULL_TREE; iv->no_overflow = false; + iv->nowrap_bound = NULL_TREE; type = TREE_TYPE (op); if (!POINTER_TYPE_P (type) && !INTEGRAL_TYPE_P (type)) return false; + tree nowrap_bound = NULL_TREE; ev = analyze_scalar_evolution_in_loop (wrto_loop, use_loop, op, - &folded_casts); + &folded_casts, + allow_wrapping ? &nowrap_bound + : nullptr); + + /* If there was a nontrivial nowrap bound, add it to the IV. */ + if (allow_wrapping && nowrap_bound) + iv->nowrap_bound = nowrap_bound; + if (chrec_contains_undetermined (ev) || chrec_contains_symbols_defined_in_loop (ev, wrto_loop->num)) return false; @@ -3437,10 +3540,12 @@ simple_iv_with_niters (class loop *wrto_loop, class loop *use_loop, bool simple_iv (class loop *wrto_loop, class loop *use_loop, tree op, - affine_iv *iv, bool allow_nonconstant_step) + affine_iv *iv, bool allow_nonconstant_step, + bool allow_wrapping) { return simple_iv_with_niters (wrto_loop, use_loop, op, iv, - NULL, allow_nonconstant_step); + NULL, allow_nonconstant_step, + allow_wrapping); } /* Finalize the scalar evolution analysis. */ @@ -3448,10 +3553,21 @@ simple_iv (class loop *wrto_loop, class loop *use_loop, tree op, void scev_finalize (void) { - if (!scalar_evolution_info) + if (!scalar_evolution_info && !scalar_evolution_nowrap_info) return; - scalar_evolution_info->empty (); - scalar_evolution_info = NULL; + + if (scalar_evolution_info) + { + scalar_evolution_info->empty (); + scalar_evolution_info = NULL; + } + + if (scalar_evolution_nowrap_info) + { + scalar_evolution_nowrap_info->empty (); + scalar_evolution_nowrap_info = NULL; + } + free_numbers_of_iterations_estimates (cfun); } diff --git a/gcc/tree-scalar-evolution.h b/gcc/tree-scalar-evolution.h index 0c15956de3f..7aa15c7f46c 100644 --- a/gcc/tree-scalar-evolution.h +++ b/gcc/tree-scalar-evolution.h @@ -30,7 +30,7 @@ extern bool scev_initialized_p (void); extern void scev_reset (void); extern void scev_reset_htab (void); extern void scev_finalize (void); -extern tree analyze_scalar_evolution (class loop *, tree); +extern tree analyze_scalar_evolution (class loop *, tree, tree * = nullptr); extern tree instantiate_scev (edge, class loop *, tree); extern tree resolve_mixers (class loop *, tree, bool *); extern void gather_stats_on_scev_database (void); @@ -38,14 +38,17 @@ extern bool final_value_replacement_loop (class loop *); extern unsigned int scev_const_prop (void); extern bool expression_expensive_p (tree, bool *); extern bool simple_iv_with_niters (class loop *, class loop *, tree, - struct affine_iv *, tree *, bool); + struct affine_iv *, tree *, bool, + bool = false); extern bool simple_iv (class loop *, class loop *, tree, struct affine_iv *, - bool); + bool, bool = false); extern bool iv_can_overflow_p (class loop *, tree, tree, tree); extern tree compute_overall_effect_of_inner_loop (class loop *, tree); extern void record_nonwrapping_chrec (tree); extern bool nonwrapping_chrec_p (tree); +extern void scev_combine_nowrap_bounds (tree *, tree); + /* Returns the basic block preceding LOOP, or the CFG entry block when the loop is function's body. */ diff --git a/gcc/tree-ssa-loop-niter.cc b/gcc/tree-ssa-loop-niter.cc index fe179b69b05..c297b12d1c1 100644 --- a/gcc/tree-ssa-loop-niter.cc +++ b/gcc/tree-ssa-loop-niter.cc @@ -5604,12 +5604,16 @@ scev_var_range_cant_overflow (tree var, tree step, class loop *loop) 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. */ + be proven not overflow with value range info. + + If NOWRAP_BOUND is nonzero and we can't prove it differently, get + STEP's type bound, build a bound MIN (NOWRAP_BOUND, STEP_TYPE_BOUND) + and store it in NOWRAP_BOUND. */ bool scev_probably_wraps_p (tree var, tree base, tree step, gimple *at_stmt, class loop *loop, - bool use_overflow_semantics) + bool use_overflow_semantics, tree *nowrap_bound) { /* FIXME: We really need something like http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html. @@ -5657,6 +5661,14 @@ scev_probably_wraps_p (tree var, tree base, tree step, if (var && nonwrapping_chrec_p (analyze_scalar_evolution (loop, var))) return false; + /* If we can use a bound to guarantee no wrapping, save it. */ + if (nowrap_bound) + { + tree b = get_niter_type_bound (TREE_TYPE (step), base, step); + scev_combine_nowrap_bounds (nowrap_bound, b); + return false; + } + /* At this point we still don't have a proof that the iv does not overflow: give up. */ return true; diff --git a/gcc/tree-ssa-loop-niter.h b/gcc/tree-ssa-loop-niter.h index 24e458f08db..c789ec524f9 100644 --- a/gcc/tree-ssa-loop-niter.h +++ b/gcc/tree-ssa-loop-niter.h @@ -54,7 +54,7 @@ extern bool stmt_dominates_stmt_p (gimple *, gimple *); extern bool nowrap_type_p (tree); extern tree get_niter_type_bound (tree, tree, tree); extern bool scev_probably_wraps_p (tree, tree, tree, gimple *, - class loop *, bool); + class loop *, bool, tree * = nullptr); extern void free_numbers_of_iterations_estimates (class loop *); extern void free_numbers_of_iterations_estimates (function *); extern tree simplify_replace_tree (tree, tree, diff --git a/gcc/tree-ssa-loop.h b/gcc/tree-ssa-loop.h index 73796a2732b..de8f9c69dac 100644 --- a/gcc/tree-ssa-loop.h +++ b/gcc/tree-ssa-loop.h @@ -30,6 +30,10 @@ struct affine_iv /* True if this iv does not overflow. */ bool no_overflow; + + /* Upper bound for the number of loop iterations for which this IV + does not wrap. */ + tree nowrap_bound; }; /* Description of number of iterations of a loop. All the expressions inside -- 2.54.0