diff --git a/gcc/builtins.c b/gcc/builtins.c index 9263777..02e97f1 100644 --- a/gcc/builtins.c +++ b/gcc/builtins.c @@ -3158,7 +3158,7 @@ determine_block_size (tree len, rtx len_rtx, *probable_max_size = *max_size = GET_MODE_MASK (GET_MODE (len_rtx)); if (TREE_CODE (len) == SSA_NAME) - range_type = get_range_info (len, &min, &max); + range_type = get_range_info (len, &min, &max, NULL); if (range_type == VR_RANGE) { if (wi::fits_uhwi_p (min) && *min_size < min.to_uhwi ()) diff --git a/gcc/gimple-pretty-print.c b/gcc/gimple-pretty-print.c index 2f9671f..0a5c4da 100644 --- a/gcc/gimple-pretty-print.c +++ b/gcc/gimple-pretty-print.c @@ -1847,13 +1847,15 @@ dump_ssaname_info (pretty_printer *buffer, tree node, int spc) && SSA_NAME_RANGE_INFO (node)) { wide_int min, max, nonzero_bits; - value_range_type range_type = get_range_info (node, &min, &max); + bool wrapped; + value_range_type range_type = get_range_info (node, &min, &max, &wrapped); if (range_type == VR_VARYING) pp_printf (buffer, "# RANGE VR_VARYING"); else if (range_type == VR_RANGE || range_type == VR_ANTI_RANGE) { pp_printf (buffer, "# RANGE "); + pp_printf (buffer, "WRAPPED = %s ", wrapped ? "true" : "false"); pp_printf (buffer, "%s[", range_type == VR_RANGE ? "" : "~"); pp_wide_int (buffer, min, TYPE_SIGN (TREE_TYPE (node))); pp_printf (buffer, ", "); diff --git a/gcc/internal-fn.c b/gcc/internal-fn.c index 0053ed9..9b10eaa 100644 --- a/gcc/internal-fn.c +++ b/gcc/internal-fn.c @@ -282,7 +282,7 @@ get_range_pos_neg (tree arg) if (TREE_CODE (arg) != SSA_NAME) return 3; wide_int arg_min, arg_max; - while (get_range_info (arg, &arg_min, &arg_max) != VR_RANGE) + while (get_range_info (arg, &arg_min, &arg_max, NULL) != VR_RANGE) { gimple g = SSA_NAME_DEF_STMT (arg); if (is_gimple_assign (g) @@ -364,7 +364,7 @@ get_min_precision (tree arg, signop sign) if (TREE_CODE (arg) != SSA_NAME) return prec + (orig_sign != sign); wide_int arg_min, arg_max; - while (get_range_info (arg, &arg_min, &arg_max) != VR_RANGE) + while (get_range_info (arg, &arg_min, &arg_max, NULL) != VR_RANGE) { gimple g = SSA_NAME_DEF_STMT (arg); if (is_gimple_assign (g) diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp92.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp92.c index a84ba8e..0c05ead 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/vrp92.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp92.c @@ -18,6 +18,6 @@ int foo (int i, int j) return j; } -/* { dg-final { scan-tree-dump "res_.: \\\[1, 1\\\]" "vrp1" } } */ +/* { dg-final { scan-tree-dump "res_.: NOWRAP \\\[1, 1\\\]" "vrp1" } } */ /* { dg-final { scan-tree-dump-not "Threaded" "vrp1" } } */ /* { dg-final { cleanup-tree-dump "vrp1" } } */ diff --git a/gcc/tree-ssa-copy.c b/gcc/tree-ssa-copy.c index 5ae8e6c..963c5a7 100644 --- a/gcc/tree-ssa-copy.c +++ b/gcc/tree-ssa-copy.c @@ -574,8 +574,8 @@ fini_copy_prop (void) && !SSA_NAME_RANGE_INFO (copy_of[i].value) && var_bb == copy_of_bb) duplicate_ssa_name_range_info (copy_of[i].value, - SSA_NAME_RANGE_TYPE (var), - SSA_NAME_RANGE_INFO (var)); + SSA_NAME_RANGE_INFO (var), + SSA_NAME_RANGE_WRAP_P (var)); } } diff --git a/gcc/tree-ssa-loop-im.c b/gcc/tree-ssa-loop-im.c index 11fc699..987add1 100644 --- a/gcc/tree-ssa-loop-im.c +++ b/gcc/tree-ssa-loop-im.c @@ -1245,7 +1245,6 @@ move_computations_dom_walker::before_dom_children (basic_block bb) { tree lhs = gimple_assign_lhs (new_stmt); SSA_NAME_RANGE_INFO (lhs) = NULL; - SSA_NAME_ANTI_RANGE_P (lhs) = 0; } gsi_insert_on_edge (loop_preheader_edge (level), new_stmt); remove_phi_node (&bsi, false); @@ -1315,7 +1314,6 @@ move_computations_dom_walker::before_dom_children (basic_block bb) { tree lhs = gimple_get_lhs (stmt); SSA_NAME_RANGE_INFO (lhs) = NULL; - SSA_NAME_ANTI_RANGE_P (lhs) = 0; } /* In case this is a stmt that is not unconditionally executed when the target loop header is executed and the stmt may diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c index fc63825..1a32a8f 100644 --- a/gcc/tree-ssa-loop-niter.c +++ b/gcc/tree-ssa-loop-niter.c @@ -176,7 +176,7 @@ determine_value_range (struct loop *loop, tree type, tree var, mpz_t off, gphi_iterator gsi; /* Either for VAR itself... */ - rtype = get_range_info (var, &minv, &maxv); + rtype = get_range_info (var, &minv, &maxv, NULL); /* Or for PHI results in loop->header where VAR is used as PHI argument from the loop preheader edge. */ for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi)) @@ -184,7 +184,7 @@ determine_value_range (struct loop *loop, tree type, tree var, mpz_t off, gphi *phi = gsi.phi (); wide_int minc, maxc; if (PHI_ARG_DEF_FROM_EDGE (phi, e) == var - && (get_range_info (gimple_phi_result (phi), &minc, &maxc) + && (get_range_info (gimple_phi_result (phi), &minc, &maxc, NULL) == VR_RANGE)) { if (rtype != VR_RANGE) @@ -203,7 +203,7 @@ determine_value_range (struct loop *loop, tree type, tree var, mpz_t off, involved. */ if (wi::gt_p (minv, maxv, sgn)) { - rtype = get_range_info (var, &minv, &maxv); + rtype = get_range_info (var, &minv, &maxv, NULL); break; } } @@ -2785,7 +2785,7 @@ record_nonwrapping_iv (struct loop *loop, tree base, tree step, gimple stmt, if (TREE_CODE (orig_base) == SSA_NAME && TREE_CODE (high) == INTEGER_CST && INTEGRAL_TYPE_P (TREE_TYPE (orig_base)) - && get_range_info (orig_base, &min, &max) == VR_RANGE + && get_range_info (orig_base, &min, &max, NULL) == VR_RANGE && wi::gts_p (high, max)) base = wide_int_to_tree (unsigned_type, max); else if (TREE_CODE (base) != INTEGER_CST) @@ -2800,7 +2800,7 @@ record_nonwrapping_iv (struct loop *loop, tree base, tree step, gimple stmt, if (TREE_CODE (orig_base) == SSA_NAME && TREE_CODE (low) == INTEGER_CST && INTEGRAL_TYPE_P (TREE_TYPE (orig_base)) - && get_range_info (orig_base, &min, &max) == VR_RANGE + && get_range_info (orig_base, &min, &max, NULL) == VR_RANGE && wi::gts_p (min, low)) base = wide_int_to_tree (unsigned_type, min); else if (TREE_CODE (base) != INTEGER_CST) diff --git a/gcc/tree-ssa-phiopt.c b/gcc/tree-ssa-phiopt.c index 7c846c2..b6f4e10 100644 --- a/gcc/tree-ssa-phiopt.c +++ b/gcc/tree-ssa-phiopt.c @@ -911,14 +911,14 @@ value_replacement (basic_block cond_bb, basic_block middle_bb, : # u_3 = PHI */ SSA_NAME_RANGE_INFO (lhs) = NULL; - SSA_NAME_ANTI_RANGE_P (lhs) = 0; /* If available, we can use VR of phi result at least. */ tree phires = gimple_phi_result (phi); struct range_info_def *phires_range_info = SSA_NAME_RANGE_INFO (phires); if (phires_range_info) - duplicate_ssa_name_range_info (lhs, SSA_NAME_RANGE_TYPE (phires), - phires_range_info); + duplicate_ssa_name_range_info (lhs, + phires_range_info, + SSA_NAME_RANGE_WRAP_P (phires)); } gimple_stmt_iterator gsi_from = gsi_for_stmt (assign); gsi_move_before (&gsi_from, &gsi); diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c index 67e5351..b5e2e87 100644 --- a/gcc/tree-ssa-pre.c +++ b/gcc/tree-ssa-pre.c @@ -3200,7 +3200,7 @@ insert_into_preds_of_block (basic_block block, unsigned int exprnum, && SSA_NAME_RANGE_INFO (expr->u.nary->op[0])) { wide_int min, max; - if (get_range_info (expr->u.nary->op[0], &min, &max) == VR_RANGE + if (get_range_info (expr->u.nary->op[0], &min, &max, NULL) == VR_RANGE && !wi::neg_p (min, SIGNED) && !wi::neg_p (max, SIGNED)) /* Just handle extension and sign-changes of all-positive ranges. */ @@ -3208,7 +3208,8 @@ insert_into_preds_of_block (basic_block block, unsigned int exprnum, wide_int_storage::from (min, TYPE_PRECISION (type), TYPE_SIGN (type)), wide_int_storage::from (max, TYPE_PRECISION (type), - TYPE_SIGN (type))); + TYPE_SIGN (type)), + false); } if (dump_file && (dump_flags & TDF_DETAILS)) @@ -4146,8 +4147,8 @@ eliminate_dom_walker::before_dom_children (basic_block b) && !SSA_NAME_RANGE_INFO (sprime) && b == sprime_b) duplicate_ssa_name_range_info (sprime, - SSA_NAME_RANGE_TYPE (lhs), - SSA_NAME_RANGE_INFO (lhs)); + SSA_NAME_RANGE_INFO (lhs), + SSA_NAME_RANGE_WRAP_P (lhs)); } /* Inhibit the use of an inserted PHI on a loop header when diff --git a/gcc/tree-ssanames.c b/gcc/tree-ssanames.c index 744dc43..4b0e232 100644 --- a/gcc/tree-ssanames.c +++ b/gcc/tree-ssanames.c @@ -201,7 +201,7 @@ make_ssa_name_fn (struct function *fn, tree var, gimple stmt) void set_range_info (tree name, - const wide_int_ref &min, const wide_int_ref &max) + const wide_int_ref &min, const wide_int_ref &max, bool wrap_p) { gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name))); range_info_def *ri = SSA_NAME_RANGE_INFO (name); @@ -221,6 +221,7 @@ set_range_info (tree name, /* Set the values. */ ri->set_min (min); ri->set_max (max); + SSA_NAME_RANGE_WRAP_P (name) = wrap_p; /* If it is a range, try to improve nonzero_bits from the min/max. */ if (wi::cmp (min, max, TYPE_SIGN (TREE_TYPE (name))) < 0) @@ -238,7 +239,7 @@ set_range_info (tree name, is used to determine if MIN and MAX are valid values. */ enum value_range_type -get_range_info (const_tree name, wide_int *min, wide_int *max) +get_range_info (const_tree name, wide_int *min, wide_int *max, bool *wrap_p) { gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name))); gcc_assert (min && max); @@ -266,6 +267,8 @@ get_range_info (const_tree name, wide_int *min, wide_int *max) *min = ri->get_min (); *max = ri->get_max (); } + if (wrap_p) + *wrap_p = SSA_NAME_RANGE_WRAP_P (name); return range_type; } @@ -278,7 +281,8 @@ set_nonzero_bits (tree name, const wide_int_ref &mask) if (SSA_NAME_RANGE_INFO (name) == NULL) set_range_info (name, TYPE_MIN_VALUE (TREE_TYPE (name)), - TYPE_MAX_VALUE (TREE_TYPE (name))); + TYPE_MAX_VALUE (TREE_TYPE (name)), + false); range_info_def *ri = SSA_NAME_RANGE_INFO (name); ri->set_nonzero_bits (mask); } @@ -505,14 +509,13 @@ duplicate_ssa_name_ptr_info (tree name, struct ptr_info_def *ptr_info) RANGE_TYPE for use by the SSA name NAME. */ void duplicate_ssa_name_range_info (tree name, - enum value_range_type range_type ATTRIBUTE_UNUSED, - struct range_info_def *range_info) + struct range_info_def *range_info, + bool wrap_p) { struct range_info_def *new_range_info; gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name))); gcc_assert (!SSA_NAME_RANGE_INFO (name)); - gcc_assert (!SSA_NAME_ANTI_RANGE_P (name)); if (!range_info) return; @@ -523,6 +526,7 @@ duplicate_ssa_name_range_info (tree name, new_range_info = static_cast (ggc_internal_alloc (size)); memcpy (new_range_info, range_info, size); + SSA_NAME_RANGE_WRAP_P (name) = wrap_p; SSA_NAME_RANGE_INFO (name) = new_range_info; } @@ -547,8 +551,9 @@ duplicate_ssa_name_fn (struct function *fn, tree name, gimple stmt) struct range_info_def *old_range_info = SSA_NAME_RANGE_INFO (name); if (old_range_info) - duplicate_ssa_name_range_info (new_name, SSA_NAME_RANGE_TYPE (name), - old_range_info); + duplicate_ssa_name_range_info (new_name, + old_range_info, + SSA_NAME_RANGE_WRAP_P (name)); } return new_name; diff --git a/gcc/tree-ssanames.h b/gcc/tree-ssanames.h index 0d4b212..7bb33db 100644 --- a/gcc/tree-ssanames.h +++ b/gcc/tree-ssanames.h @@ -69,10 +69,10 @@ enum value_range_type { VR_UNDEFINED, VR_RANGE, VR_ANTI_RANGE, VR_VARYING }; /* Sets the value range to SSA. */ extern void set_range_info (tree, const wide_int_ref &, - const wide_int_ref &); + const wide_int_ref &, bool); /* Gets the value range from SSA. */ extern enum value_range_type get_range_info (const_tree, wide_int *, - wide_int *); + wide_int *, bool *); extern void set_nonzero_bits (tree, const wide_int_ref &); extern wide_int get_nonzero_bits (const_tree); extern void init_ssanames (struct function *, int); @@ -92,8 +92,9 @@ extern struct ptr_info_def *get_ptr_info (tree); extern tree copy_ssa_name_fn (struct function *, tree, gimple); extern void duplicate_ssa_name_ptr_info (tree, struct ptr_info_def *); extern tree duplicate_ssa_name_fn (struct function *, tree, gimple); -extern void duplicate_ssa_name_range_info (tree, enum value_range_type, - struct range_info_def *); +extern void duplicate_ssa_name_range_info (tree, + struct range_info_def *, + bool); extern void release_defs (gimple); extern void replace_ssa_name_symbol (tree, tree); diff --git a/gcc/tree-vect-patterns.c b/gcc/tree-vect-patterns.c index 86d2447..fc22f53 100644 --- a/gcc/tree-vect-patterns.c +++ b/gcc/tree-vect-patterns.c @@ -2563,7 +2563,7 @@ vect_recog_divmod_pattern (vec *stmts, wide_int oprnd0_min, oprnd0_max; int msb = 1; - if (get_range_info (oprnd0, &oprnd0_min, &oprnd0_max) == VR_RANGE) + if (get_range_info (oprnd0, &oprnd0_min, &oprnd0_max, NULL) == VR_RANGE) { if (!wi::neg_p (oprnd0_min, TYPE_SIGN (itype))) msb = 0; diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index d823be9..a988aaf 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -114,6 +114,34 @@ struct value_range_d tree min; tree max; + /* Set to true if the values in this range might have been wrapped + during the operation that computed it. + + This is mainly used in zero/sign-extension elimination where value ranges + computed are for the type of SSA_NAME and computation is ultimately done + in PROMOTE_MODE. Therefore, the value ranges has to be correct upto + PROMOTE_MODE precision. If the operation can WRAP, higher bits in + PROMOTE_MODE can be unpredictable and cannot be used in zero/sign extension + elimination; additional wrap_p attribute is needed to show this. + + For example: + on alpha where PROMOTE_MODE is 64 bit and _344 is a 32 bit unsigned + variable, + _343 = ivtmp.179_52 + 2147483645; [0x80000004, 0x800000043] + + the value range VRP will compute is: + + _344 = _343 * 2; [0x8, 0x86] + _345 = (integer(kind=4)) _344; [0x8, 0x86] + + In PROMOTE_MODE, there will be garbage above the type width. In places + like this, attribute wrap_p will be true. + + wrap_p in range union operation will be true if either of the value range + has wrap_p set. In intersect operation, true when both the value ranges + have wrap_p set. */ + bool wrap_p; + /* Set of SSA names whose value ranges are equivalent to this one. This set is only valid when TYPE is VR_RANGE or VR_ANTI_RANGE. */ bitmap equiv; @@ -121,7 +149,7 @@ struct value_range_d typedef struct value_range_d value_range_t; -#define VR_INITIALIZER { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL } +#define VR_INITIALIZER { VR_UNDEFINED, NULL_TREE, NULL_TREE, false, NULL } /* Set of SSA names found live during the RPO traversal of the function for still active basic-blocks. */ @@ -469,7 +497,7 @@ set_value_range_to_varying (value_range_t *vr) static void set_value_range (value_range_t *vr, enum value_range_type t, tree min, - tree max, bitmap equiv) + tree max, bool wrap_p, bitmap equiv) { #if defined ENABLE_CHECKING /* Check the validity of the range. */ @@ -503,6 +531,7 @@ set_value_range (value_range_t *vr, enum value_range_type t, tree min, vr->type = t; vr->min = min; vr->max = max; + vr->wrap_p = wrap_p; /* Since updating the equivalence set involves deep copying the bitmaps, only do it if absolutely necessary. */ @@ -531,7 +560,7 @@ set_value_range (value_range_t *vr, enum value_range_type t, tree min, static void set_and_canonicalize_value_range (value_range_t *vr, enum value_range_type t, - tree min, tree max, bitmap equiv) + tree min, tree max, bool wrap_p, bitmap equiv) { /* Use the canonical setters for VR_UNDEFINED and VR_VARYING. */ if (t == VR_UNDEFINED) @@ -549,7 +578,7 @@ set_and_canonicalize_value_range (value_range_t *vr, enum value_range_type t, if (TREE_CODE (min) != INTEGER_CST || TREE_CODE (max) != INTEGER_CST) { - set_value_range (vr, t, min, max, equiv); + set_value_range (vr, t, min, max, wrap_p, equiv); return; } @@ -637,7 +666,7 @@ set_and_canonicalize_value_range (value_range_t *vr, enum value_range_type t, return; } - set_value_range (vr, t, min, max, equiv); + set_value_range (vr, t, min, max, wrap_p, equiv); } /* Copy value range FROM into value range TO. */ @@ -645,7 +674,8 @@ set_and_canonicalize_value_range (value_range_t *vr, enum value_range_type t, static inline void copy_value_range (value_range_t *to, value_range_t *from) { - set_value_range (to, from->type, from->min, from->max, from->equiv); + set_value_range (to, from->type, from->min, from->max, + from->wrap_p, from->equiv); } /* Set value range VR to a single value. This function is only called @@ -659,7 +689,7 @@ set_value_range_to_value (value_range_t *vr, tree val, bitmap equiv) gcc_assert (is_gimple_min_invariant (val)); if (TREE_OVERFLOW_P (val)) val = drop_tree_overflow (val); - set_value_range (vr, VR_RANGE, val, val, equiv); + set_value_range (vr, VR_RANGE, val, val, false, equiv); } /* Set value range VR to a non-negative range of type TYPE. @@ -685,6 +715,7 @@ set_value_range_to_nonnegative (value_range_t *vr, tree type, (overflow_infinity ? positive_overflow_infinity (type) : TYPE_MAX_VALUE (type)), + false, vr->equiv); } @@ -694,7 +725,7 @@ static inline void set_value_range_to_nonnull (value_range_t *vr, tree type) { tree zero = build_int_cst (type, 0); - set_value_range (vr, VR_ANTI_RANGE, zero, zero, vr->equiv); + set_value_range (vr, VR_ANTI_RANGE, zero, zero, false, vr->equiv); } @@ -717,6 +748,7 @@ set_value_range_to_truthvalue (value_range_t *vr, tree type) else set_value_range (vr, VR_RANGE, build_int_cst (type, 0), build_int_cst (type, 1), + false, vr->equiv); } @@ -753,7 +785,7 @@ abs_extent_range (value_range_t *vr, tree min, tree max) set_value_range_to_varying (vr); return; } - set_and_canonicalize_value_range (vr, VR_RANGE, min, max, NULL); + set_and_canonicalize_value_range (vr, VR_RANGE, min, max, false, NULL); } @@ -766,7 +798,7 @@ static value_range_t * get_value_range (const_tree var) { static const struct value_range_d vr_const_varying - = { VR_VARYING, NULL_TREE, NULL_TREE, NULL }; + = { VR_VARYING, NULL_TREE, NULL_TREE, false, NULL }; value_range_t *vr; tree sym; unsigned ver = SSA_NAME_VERSION (var); @@ -864,13 +896,15 @@ update_value_range (const_tree var, value_range_t *new_vr) if (INTEGRAL_TYPE_P (TREE_TYPE (var))) { wide_int min, max; - value_range_type rtype = get_range_info (var, &min, &max); + bool wrap_p = false; + value_range_type rtype = get_range_info (var, &min, &max, &wrap_p); if (rtype == VR_RANGE || rtype == VR_ANTI_RANGE) { value_range_d nr; nr.type = rtype; nr.min = wide_int_to_tree (TREE_TYPE (var), min); nr.max = wide_int_to_tree (TREE_TYPE (var), max); + nr.wrap_p = wrap_p; nr.equiv = NULL; vrp_intersect_ranges (new_vr, &nr); } @@ -895,6 +929,7 @@ update_value_range (const_tree var, value_range_t *new_vr) set_value_range_to_varying (old_vr); else set_value_range (old_vr, new_vr->type, new_vr->min, new_vr->max, + new_vr->wrap_p, new_vr->equiv); } @@ -1788,10 +1823,10 @@ extract_range_from_assert (value_range_t *vr_p, tree expr) this for us. */ if (cond_code == LE_EXPR) set_and_canonicalize_value_range (vr_p, VR_RANGE, - min, max, vr_p->equiv); + min, max, false, vr_p->equiv); else if (cond_code == GT_EXPR) set_and_canonicalize_value_range (vr_p, VR_ANTI_RANGE, - min, max, vr_p->equiv); + min, max, false, vr_p->equiv); else gcc_unreachable (); } @@ -1812,7 +1847,7 @@ extract_range_from_assert (value_range_t *vr_p, tree expr) max = limit; } - set_value_range (vr_p, range_type, min, max, vr_p->equiv); + set_value_range (vr_p, range_type, min, max, false, vr_p->equiv); /* When asserting the equality VAR == LIMIT and LIMIT is another SSA name, the new range will also inherit the equivalence set @@ -1864,7 +1899,7 @@ extract_range_from_assert (value_range_t *vr_p, tree expr) min = max = limit; set_and_canonicalize_value_range (vr_p, VR_ANTI_RANGE, - min, max, vr_p->equiv); + min, max, false, vr_p->equiv); } else if (cond_code == LE_EXPR || cond_code == LT_EXPR) { @@ -1903,7 +1938,7 @@ extract_range_from_assert (value_range_t *vr_p, tree expr) TREE_NO_WARNING (max) = 1; } - set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv); + set_value_range (vr_p, VR_RANGE, min, max, false, vr_p->equiv); } } else if (cond_code == GE_EXPR || cond_code == GT_EXPR) @@ -1943,7 +1978,7 @@ extract_range_from_assert (value_range_t *vr_p, tree expr) TREE_NO_WARNING (min) = 1; } - set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv); + set_value_range (vr_p, VR_RANGE, min, max, false, vr_p->equiv); } } else @@ -1975,12 +2010,11 @@ extract_range_from_ssa_name (value_range_t *vr, tree var) if (var_vr->type != VR_VARYING) copy_value_range (vr, var_vr); else - set_value_range (vr, VR_RANGE, var, var, NULL); + set_value_range (vr, VR_RANGE, var, var, false, NULL); add_equivalence (&vr->equiv, var); } - /* Wrapper around int_const_binop. If the operation overflows and we are not using wrapping arithmetic, then adjust the result to be -INF or +INF depending on CODE, VAL1 and VAL2. This can return @@ -1988,11 +2022,13 @@ extract_range_from_ssa_name (value_range_t *vr, tree var) the type does not support it. */ static tree -vrp_int_const_binop (enum tree_code code, tree val1, tree val2) +vrp_int_const_binop (enum tree_code code, tree val1, tree val2, bool *wrap_p) { tree res; res = int_const_binop (code, val1, val2); + if (wrap_p) + *wrap_p = false; /* If we are using unsigned arithmetic, operate symbolically on -INF and +INF as int_const_binop only handles signed overflow. */ @@ -2036,7 +2072,10 @@ vrp_int_const_binop (enum tree_code code, tree val1, tree val2) else if (TYPE_OVERFLOW_WRAPS (TREE_TYPE (val1))) /* If the singed operation wraps then int_const_binop has done everything we want. */ - ; + { + if (wrap_p) + *wrap_p = true; + } /* Signed division of -1/0 overflows and by the time it gets here returns NULL_TREE. */ else if (!res) @@ -2200,12 +2239,14 @@ ranges_from_anti_range (value_range_t *ar, vr0->type = VR_RANGE; vr0->min = vrp_val_min (type); vr0->max = wide_int_to_tree (type, wi::sub (ar->min, 1)); + vr0->wrap_p = ar->wrap_p; } if (!vrp_val_is_max (ar->max)) { vr1->type = VR_RANGE; vr1->min = wide_int_to_tree (type, wi::add (ar->max, 1)); vr1->max = vrp_val_max (type); + vr1->wrap_p = ar->wrap_p; } if (vr0->type == VR_UNDEFINED) { @@ -2230,6 +2271,8 @@ extract_range_from_multiplicative_op_1 (value_range_t *vr, tree min, max; bool sop; int cmp; + bool wrap_p = false; + bool t_wrap_p = false; /* Multiplications, divisions and shifts are a bit tricky to handle, depending on the mix of signs we have in the two ranges, we @@ -2259,35 +2302,43 @@ extract_range_from_multiplicative_op_1 (value_range_t *vr, /* Compute the 4 cross operations. */ sop = false; - val[0] = vrp_int_const_binop (code, vr0->min, vr1->min); + val[0] = vrp_int_const_binop (code, vr0->min, vr1->min, &t_wrap_p); if (val[0] == NULL_TREE) sop = true; + if (t_wrap_p) + wrap_p = true; if (vr1->max == vr1->min) val[1] = NULL_TREE; else { - val[1] = vrp_int_const_binop (code, vr0->min, vr1->max); + val[1] = vrp_int_const_binop (code, vr0->min, vr1->max, &t_wrap_p); if (val[1] == NULL_TREE) sop = true; + if (t_wrap_p) + wrap_p = true; } if (vr0->max == vr0->min) val[2] = NULL_TREE; else { - val[2] = vrp_int_const_binop (code, vr0->max, vr1->min); + val[2] = vrp_int_const_binop (code, vr0->max, vr1->min, &t_wrap_p); if (val[2] == NULL_TREE) sop = true; + if (t_wrap_p) + wrap_p = true; } if (vr0->min == vr0->max || vr1->min == vr1->max) val[3] = NULL_TREE; else { - val[3] = vrp_int_const_binop (code, vr0->max, vr1->max); + val[3] = vrp_int_const_binop (code, vr0->max, vr1->max, &t_wrap_p); if (val[3] == NULL_TREE) sop = true; + if (t_wrap_p) + wrap_p = true; } if (sop) @@ -2367,7 +2418,7 @@ extract_range_from_multiplicative_op_1 (value_range_t *vr, set_value_range_to_varying (vr); } else - set_value_range (vr, type, min, max, NULL); + set_value_range (vr, type, min, max, wrap_p, NULL); } /* Extract range information from a binary operation CODE based on @@ -2384,6 +2435,7 @@ extract_range_from_binary_expr_1 (value_range_t *vr, enum value_range_type type; tree min = NULL_TREE, max = NULL_TREE; int cmp; + bool vr_wrap_p = false; if (!INTEGRAL_TYPE_P (expr_type) && !POINTER_TYPE_P (expr_type)) @@ -2683,6 +2735,13 @@ extract_range_from_binary_expr_1 (value_range_t *vr, range kind and bounds appropriately. */ wide_int tmin = wide_int::from (wmin, prec, sgn); wide_int tmax = wide_int::from (wmax, prec, sgn); + + if (wi::cmp (wmin, type_min, sgn) == -1 + || wi::cmp (wmin, type_max, sgn) == 1 + || wi::cmp (wmax, type_min, sgn) == -1 + || wi::cmp (wmax, type_max, sgn) == 1) + vr_wrap_p = true; + if (min_ovf == max_ovf) { /* No overflow or both overflow or underflow. The @@ -2835,8 +2894,8 @@ extract_range_from_binary_expr_1 (value_range_t *vr, /* For operations that make the resulting range directly proportional to the original ranges, apply the operation to the same end of each range. */ - min = vrp_int_const_binop (code, vr0.min, vr1.min); - max = vrp_int_const_binop (code, vr0.max, vr1.max); + min = vrp_int_const_binop (code, vr0.min, vr1.min, NULL); + max = vrp_int_const_binop (code, vr0.max, vr1.max, NULL); } else if (code == MIN_EXPR) { @@ -2960,9 +3019,10 @@ extract_range_from_binary_expr_1 (value_range_t *vr, /* The following should handle the wrapping and selecting VR_ANTI_RANGE for us. */ + vr_wrap_p = true; min = wide_int_to_tree (expr_type, prod0); max = wide_int_to_tree (expr_type, prod3); - set_and_canonicalize_value_range (vr, VR_RANGE, min, max, NULL); + set_and_canonicalize_value_range (vr, VR_RANGE, min, max, vr_wrap_p, NULL); return; } @@ -3330,7 +3390,7 @@ extract_range_from_binary_expr_1 (value_range_t *vr, set_value_range_to_varying (vr); } else - set_value_range (vr, type, min, max, NULL); + set_value_range (vr, type, min, max, vr_wrap_p, NULL); } /* Extract range information from a binary expression OP0 CODE OP1 based on @@ -3379,15 +3439,15 @@ extract_range_from_binary_expr (value_range_t *vr, /* Try with VR0 and [-INF, OP1]. */ if (is_gimple_min_invariant (minus_p ? vr0.max : vr0.min)) - set_value_range (&n_vr1, VR_RANGE, vrp_val_min (expr_type), op1, NULL); + set_value_range (&n_vr1, VR_RANGE, vrp_val_min (expr_type), op1, false, NULL); /* Try with VR0 and [OP1, +INF]. */ else if (is_gimple_min_invariant (minus_p ? vr0.min : vr0.max)) - set_value_range (&n_vr1, VR_RANGE, op1, vrp_val_max (expr_type), NULL); + set_value_range (&n_vr1, VR_RANGE, op1, vrp_val_max (expr_type), false, NULL); /* Try with VR0 and [OP1, OP1]. */ else - set_value_range (&n_vr1, VR_RANGE, op1, op1, NULL); + set_value_range (&n_vr1, VR_RANGE, op1, op1, false, NULL); extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &n_vr1); } @@ -3403,15 +3463,15 @@ extract_range_from_binary_expr (value_range_t *vr, /* Try with [-INF, OP0] and VR1. */ if (is_gimple_min_invariant (minus_p ? vr1.max : vr1.min)) - set_value_range (&n_vr0, VR_RANGE, vrp_val_min (expr_type), op0, NULL); + set_value_range (&n_vr0, VR_RANGE, vrp_val_min (expr_type), op0, false, NULL); /* Try with [OP0, +INF] and VR1. */ else if (is_gimple_min_invariant (minus_p ? vr1.min : vr1.max)) - set_value_range (&n_vr0, VR_RANGE, op0, vrp_val_max (expr_type), NULL); + set_value_range (&n_vr0, VR_RANGE, op0, vrp_val_max (expr_type), false, NULL); /* Try with [OP0, OP0] and VR1. */ else - set_value_range (&n_vr0, VR_RANGE, op0, op0, NULL); + set_value_range (&n_vr0, VR_RANGE, op0, op0, false, NULL); extract_range_from_binary_expr_1 (vr, code, expr_type, &n_vr0, &vr1); } @@ -3544,18 +3604,27 @@ extract_range_from_unary_expr_1 (value_range_t *vr, size_int (TYPE_PRECISION (outer_type))))))) { tree new_min, new_max; + bool wrap_p = vr0.wrap_p; if (is_overflow_infinity (vr0.min)) new_min = negative_overflow_infinity (outer_type); else - new_min = force_fit_type (outer_type, wi::to_widest (vr0.min), - 0, false); + { + if (!int_fits_type_p (vr0.max, outer_type)) + wrap_p = true; + new_min = force_fit_type (outer_type, wi::to_widest (vr0.min), + 0, false); + } if (is_overflow_infinity (vr0.max)) new_max = positive_overflow_infinity (outer_type); else - new_max = force_fit_type (outer_type, wi::to_widest (vr0.max), - 0, false); + { + if (!int_fits_type_p (vr0.max, outer_type)) + wrap_p = true; + new_max = force_fit_type (outer_type, wi::to_widest (vr0.max), + 0, false); + } set_and_canonicalize_value_range (vr, vr0.type, - new_min, new_max, NULL); + new_min, new_max, wrap_p, NULL); return; } @@ -3712,7 +3781,7 @@ extract_range_from_unary_expr_1 (value_range_t *vr, set_value_range_to_varying (vr); } else - set_value_range (vr, vr0.type, min, max, NULL); + set_value_range (vr, vr0.type, min, max, false, NULL); return; } @@ -3806,7 +3875,7 @@ extract_range_from_comparison (value_range_t *vr, enum tree_code code, if (is_gimple_min_invariant (val)) set_value_range_to_value (vr, val, vr->equiv); else - set_value_range (vr, VR_RANGE, val, val, vr->equiv); + set_value_range (vr, VR_RANGE, val, val, false, vr->equiv); } else /* The result of a comparison is always true or false. */ @@ -4103,7 +4172,7 @@ extract_range_basic (value_range_t *vr, gimple stmt) goto bitop_builtin; bitop_builtin: set_value_range (vr, VR_RANGE, build_int_cst (type, mini), - build_int_cst (type, maxi), NULL); + build_int_cst (type, maxi), false, NULL); return; default: break; @@ -4193,7 +4262,7 @@ extract_range_basic (value_range_t *vr, gimple stmt) NULL); else set_value_range (vr, VR_RANGE, build_int_cst (type, 0), - build_int_cst (type, 1), NULL); + build_int_cst (type, 1), false, NULL); } else if (types_compatible_p (type, TREE_TYPE (op0)) && types_compatible_p (type, TREE_TYPE (op1))) @@ -4287,6 +4356,7 @@ adjust_range_with_scev (value_range_t *vr, struct loop *loop, { tree init, step, chrec, tmin, tmax, min, max, type, tem; enum ev_direction dir; + bool t_wrap_p = false, wrap_p = false; /* TODO. Don't adjust anti-ranges. An anti-range may provide better opportunities than a regular range, but I'm not sure. */ @@ -4382,6 +4452,7 @@ adjust_range_with_scev (value_range_t *vr, struct loop *loop, /* Likewise if the addition did. */ if (maxvr.type == VR_RANGE) { + t_wrap_p = maxvr.wrap_p; tmin = maxvr.min; tmax = maxvr.max; } @@ -4393,6 +4464,7 @@ adjust_range_with_scev (value_range_t *vr, struct loop *loop, { min = tmin; max = tmax; + wrap_p = t_wrap_p; /* For VARYING or UNDEFINED ranges, just about anything we get from scalar evolutions should be better. */ @@ -4446,7 +4518,7 @@ adjust_range_with_scev (value_range_t *vr, struct loop *loop, && is_positive_overflow_infinity (max))) return; - set_value_range (vr, VR_RANGE, min, max, vr->equiv); + set_value_range (vr, VR_RANGE, min, max, wrap_p, vr->equiv); } @@ -4765,7 +4837,8 @@ dump_value_range (FILE *file, value_range_t *vr) { tree type = TREE_TYPE (vr->min); - fprintf (file, "%s[", (vr->type == VR_ANTI_RANGE) ? "~" : ""); + fprintf (file, "%s %s[", vr->wrap_p ? "WRAP" : "NOWRAP", + (vr->type == VR_ANTI_RANGE) ? "~" : ""); if (is_negative_overflow_infinity (vr->min)) fprintf (file, "-INF(OVF)"); @@ -6936,7 +7009,8 @@ remove_range_assertions (void) { set_range_info (var, SSA_NAME_RANGE_INFO (lhs)->get_min (), - SSA_NAME_RANGE_INFO (lhs)->get_max ()); + SSA_NAME_RANGE_INFO (lhs)->get_max (), + SSA_NAME_RANGE_WRAP_P (lhs)); maybe_set_nonzero_bits (bb, var); } } @@ -8604,7 +8678,9 @@ vrp_intersect_ranges_1 (value_range_t *vr0, value_range_t *vr1) /* Make sure to canonicalize the result though as the inversion of a VR_RANGE can still be a VR_RANGE. */ set_and_canonicalize_value_range (vr0, vr0->type, - vr0->min, vr0->max, vr0->equiv); + vr0->min, vr0->max, + vr0->wrap_p && vr1->wrap_p, + vr0->equiv); /* If that failed, use the saved original VR0. */ if (vr0->type == VR_VARYING) { @@ -8655,7 +8731,8 @@ vrp_meet_1 (value_range_t *vr0, value_range_t *vr1) if (vr0->type == VR_UNDEFINED) { - set_value_range (vr0, vr1->type, vr1->min, vr1->max, vr1->equiv); + set_value_range (vr0, vr1->type, vr1->min, vr1->max, + vr1->wrap_p, vr1->equiv); return; } @@ -8709,6 +8786,7 @@ vrp_meet_1 (value_range_t *vr0, value_range_t *vr1) return; } set_and_canonicalize_value_range (vr0, vr0->type, vr0->min, vr0->max, + vr0->wrap_p || vr1->wrap_p, vr0->equiv); if (vr0->type == VR_VARYING) return; @@ -8812,6 +8890,7 @@ vrp_visit_phi_node (gphi *phi) vr_arg.type = VR_RANGE; vr_arg.min = arg; vr_arg.max = arg; + vr_arg.wrap_p = false; vr_arg.equiv = NULL; } } @@ -8824,6 +8903,7 @@ vrp_visit_phi_node (gphi *phi) vr_arg.type = VR_RANGE; vr_arg.min = arg; vr_arg.max = arg; + vr_arg.wrap_p = false; vr_arg.equiv = NULL; } @@ -10264,7 +10344,9 @@ vrp_finalize (void) || vr_value[i]->type == VR_ANTI_RANGE)) { if (vr_value[i]->type == VR_RANGE) - set_range_info (name, vr_value[i]->min, vr_value[i]->max); + set_range_info (name, vr_value[i]->min, + vr_value[i]->max, + vr_value[i]->wrap_p); else if (vr_value[i]->type == VR_ANTI_RANGE) { /* VR_ANTI_RANGE @@ -10279,11 +10361,13 @@ vrp_finalize (void) /* ~[0,0] anti-range is represented as range. */ set_range_info (name, build_int_cst (TREE_TYPE (name), 1), - TYPE_MAXVAL (TREE_TYPE (name))); + TYPE_MAXVAL (TREE_TYPE (name)), + vr_value[i]->wrap_p); else set_range_info (name, wi::add (vr_value[i]->max, 1), - wi::sub (vr_value[i]->min, 1)); + wi::sub (vr_value[i]->min, 1), + vr_value[i]->wrap_p); } } diff --git a/gcc/tree.h b/gcc/tree.h index bedf103..cc147bb 100644 --- a/gcc/tree.h +++ b/gcc/tree.h @@ -1542,14 +1542,11 @@ extern void protected_set_expr_location (tree, location_t); #define SSA_NAME_PTR_INFO(N) \ SSA_NAME_CHECK (N)->ssa_name.info.ptr_info -/* True if SSA_NAME_RANGE_INFO describes an anti-range. */ -#define SSA_NAME_ANTI_RANGE_P(N) \ +/* True if SSA_NAME_RANGE_INFO may have wrapped during the operation that + calculated it. */ +#define SSA_NAME_RANGE_WRAP_P(N) \ SSA_NAME_CHECK (N)->base.static_flag -/* The type of range described by SSA_NAME_RANGE_INFO. */ -#define SSA_NAME_RANGE_TYPE(N) \ - (SSA_NAME_ANTI_RANGE_P (N) ? VR_ANTI_RANGE : VR_RANGE) - /* Value range info attributes for SSA_NAMEs of non pointer-type variables. */ #define SSA_NAME_RANGE_INFO(N) \ SSA_NAME_CHECK (N)->ssa_name.info.range_info