diff options
| -rw-r--r-- | gcc/ChangeLog | 37 | ||||
| -rw-r--r-- | gcc/tree-flow.h | 2 | ||||
| -rw-r--r-- | gcc/tree-ssa-propagate.c | 4 | ||||
| -rw-r--r-- | gcc/tree-vrp.c | 950 |
4 files changed, 789 insertions, 204 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 0bc6279..0976767 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,40 @@ +2007-03-03 Ian Lance Taylor <iant@google.com> + + Used signed infinities in VRP. + * tree-vrp.c (uses_overflow_infinity): New static function. + (supports_overflow_infinity): New static function. + (make_overflow_infinity): New static function. + (negative_overflow_infinity): New static function. + (positive_overflow_infinity): New static function. + (is_negative_overflow_infinity): New static function. + (is_positive_overflow_infinity): New static function. + (is_overflow_infinity): New static function. + (overflow_infinity_range_p): New static function. + (compare_values_warnv): New function split out of compare_values. + (compare_value): Call it. + (set_value_range_to_nonnegative): Add overflow_infinity + parameter. Change caller. + (vrp_expr_computes_nonnegative): Add strict_overflow_p parameter. + Change callers. + (vrp_expr_computes_nonzero): Likewise. + (compare_ranges, compare_range_with_value): Likewise. + (compare_name_with_value, compare_names): Likewise. + (vrp_evaluate_conditional): Likewise. + (set_value_range): Handle infinity + (vrp_operand_equal_p, operand_less_p): Likewise. + (extract_range_from_assert): Likewise. + (vrp_int_const_binop): Likewise. + (extract_range_from_binary_expr): Likewise. + (extract_range_from_unary_expr): Likewise. + (extract_range_from_comparison): Likewise. + (extract_range_from_expr): Likewise. + (dump_value_range): Likewise. + (vrp_visit_cond_stmt, vrp_visit_phi_node): Likewise. + (test_for_singularity): Likewise. + (vrp_int_const_binop): Remove inline qualifier. + (adjust_range_with_scev): Add comment. + * tree-flow.h (vrp_evaluate_conditional): Update declaration. + 2007-03-02 Diego Novillo <dnovillo@redhat.com> * tree-ssa-structalias.c (could_have_pointers): Tidy. diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h index 2d661f5..87b655b 100644 --- a/gcc/tree-flow.h +++ b/gcc/tree-flow.h @@ -776,7 +776,7 @@ bool fold_stmt_inplace (tree); tree widen_bitfield (tree, tree, tree); /* In tree-vrp.c */ -tree vrp_evaluate_conditional (tree, bool); +tree vrp_evaluate_conditional (tree, bool, bool *); void simplify_stmt_using_ranges (tree); /* In tree-ssa-dom.c */ diff --git a/gcc/tree-ssa-propagate.c b/gcc/tree-ssa-propagate.c index 1bfb56c..3cc3239 100644 --- a/gcc/tree-ssa-propagate.c +++ b/gcc/tree-ssa-propagate.c @@ -1100,6 +1100,7 @@ fold_predicate_in (tree stmt) tree *pred_p = NULL; bool modify_stmt_p = false; tree val; + bool sop; if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT && COMPARISON_CLASS_P (GIMPLE_STMT_OPERAND (stmt, 1))) @@ -1112,7 +1113,8 @@ fold_predicate_in (tree stmt) else return false; - val = vrp_evaluate_conditional (*pred_p, true); + sop = false; + val = vrp_evaluate_conditional (*pred_p, true, &sop); if (val) { if (modify_stmt_p) diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index b3223a5..d3785a4 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -44,6 +44,7 @@ static sbitmap found_in_subgraph; /* Local functions. */ static int compare_values (tree val1, tree val2); +static int compare_values_warnv (tree val1, tree val2, bool *); static void vrp_meet (value_range_t *, value_range_t *); /* Location information for ASSERT_EXPRs. Each instance of this @@ -93,6 +94,107 @@ static sbitmap blocks_visited; static value_range_t **vr_value; +/* Return whether TYPE should use an overflow infinity distinct from + TYPE_{MIN,MAX}_VALUE. We use an overflow infinity value to + represent a signed overflow during VRP computations. An infinity + is distinct from a half-range, which will go from some number to + TYPE_{MIN,MAX}_VALUE. */ + +static inline bool +needs_overflow_infinity (tree type) +{ + return INTEGRAL_TYPE_P (type) && !TYPE_OVERFLOW_WRAPS (type); +} + +/* Return whether TYPE can support our overflow infinity + representation: we use the TREE_OVERFLOW flag, which only exists + for constants. If TYPE doesn't support this, we don't optimize + cases which would require signed overflow--we drop them to + VARYING. */ + +static inline bool +supports_overflow_infinity (tree type) +{ +#ifdef ENABLE_CHECKING + gcc_assert (needs_overflow_infinity (type)); +#endif + return (TYPE_MIN_VALUE (type) != NULL_TREE + && CONSTANT_CLASS_P (TYPE_MIN_VALUE (type)) + && TYPE_MAX_VALUE (type) != NULL_TREE + && CONSTANT_CLASS_P (TYPE_MAX_VALUE (type))); +} + +/* VAL is the maximum or minimum value of a type. Return a + corresponding overflow infinity. */ + +static inline tree +make_overflow_infinity (tree val) +{ +#ifdef ENABLE_CHECKING + gcc_assert (val != NULL_TREE && CONSTANT_CLASS_P (val)); +#endif + val = copy_node (val); + TREE_OVERFLOW (val) = 1; + return val; +} + +/* Return a negative overflow infinity for TYPE. */ + +static inline tree +negative_overflow_infinity (tree type) +{ +#ifdef ENABLE_CHECKING + gcc_assert (supports_overflow_infinity (type)); +#endif + return make_overflow_infinity (TYPE_MIN_VALUE (type)); +} + +/* Return a positive overflow infinity for TYPE. */ + +static inline tree +positive_overflow_infinity (tree type) +{ +#ifdef ENABLE_CHECKING + gcc_assert (supports_overflow_infinity (type)); +#endif + return make_overflow_infinity (TYPE_MAX_VALUE (type)); +} + +/* Return whether VAL is a negative overflow infinity. */ + +static inline bool +is_negative_overflow_infinity (tree val) +{ + return (needs_overflow_infinity (TREE_TYPE (val)) + && CONSTANT_CLASS_P (val) + && TREE_OVERFLOW (val) + && operand_equal_p (val, TYPE_MIN_VALUE (TREE_TYPE (val)), 0)); +} + +/* Return whether VAL is a positive overflow infinity. */ + +static inline bool +is_positive_overflow_infinity (tree val) +{ + return (needs_overflow_infinity (TREE_TYPE (val)) + && CONSTANT_CLASS_P (val) + && TREE_OVERFLOW (val) + && operand_equal_p (val, TYPE_MAX_VALUE (TREE_TYPE (val)), 0)); +} + +/* Return whether VAL is a positive or negative overflow infinity. */ + +static inline bool +is_overflow_infinity (tree val) +{ + return (needs_overflow_infinity (TREE_TYPE (val)) + && CONSTANT_CLASS_P (val) + && TREE_OVERFLOW (val) + && (operand_equal_p (val, TYPE_MAX_VALUE (TREE_TYPE (val)), 0) + || operand_equal_p (val, TYPE_MIN_VALUE (TREE_TYPE (val)), 0))); +} + + /* Return true if ARG is marked with the nonnull attribute in the current function signature. */ @@ -156,8 +258,10 @@ set_value_range (value_range_t *vr, enum value_range_type t, tree min, gcc_assert (min && max); if (INTEGRAL_TYPE_P (TREE_TYPE (min)) && t == VR_ANTI_RANGE) - gcc_assert (min != TYPE_MIN_VALUE (TREE_TYPE (min)) - || max != TYPE_MAX_VALUE (TREE_TYPE (max))); + gcc_assert ((min != TYPE_MIN_VALUE (TREE_TYPE (min)) + && !is_negative_overflow_infinity (min)) + || (max != TYPE_MAX_VALUE (TREE_TYPE (max)) + && !is_positive_overflow_infinity (max))); cmp = compare_values (min, max); gcc_assert (cmp == 0 || cmp == -1 || cmp == -2); @@ -197,13 +301,42 @@ 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 VR to a non-negative range of type TYPE. */ + +/* Set value range VR to VR_VARYING. */ static inline void -set_value_range_to_nonnegative (value_range_t *vr, tree type) +set_value_range_to_varying (value_range_t *vr) { - tree zero = build_int_cst (type, 0); - set_value_range (vr, VR_RANGE, zero, TYPE_MAX_VALUE (type), vr->equiv); + vr->type = VR_VARYING; + vr->min = vr->max = NULL_TREE; + if (vr->equiv) + bitmap_clear (vr->equiv); +} + +/* Set value range VR to a non-negative range of type TYPE. + OVERFLOW_INFINITY indicates whether to use a overflow infinity + rather than TYPE_MAX_VALUE; this should be true if we determine + that the range is nonnegative based on the assumption that signed + overflow does not occur. */ + +static inline void +set_value_range_to_nonnegative (value_range_t *vr, tree type, + bool overflow_infinity) +{ + tree zero; + + if (overflow_infinity && !supports_overflow_infinity (type)) + { + set_value_range_to_varying (vr); + return; + } + + zero = build_int_cst (type, 0); + set_value_range (vr, VR_RANGE, zero, + (overflow_infinity + ? positive_overflow_infinity (type) + : TYPE_MAX_VALUE (type)), + vr->equiv); } /* Set value range VR to a non-NULL range of type TYPE. */ @@ -226,18 +359,6 @@ set_value_range_to_null (value_range_t *vr, tree type) } -/* Set value range VR to VR_VARYING. */ - -static inline void -set_value_range_to_varying (value_range_t *vr) -{ - vr->type = VR_VARYING; - vr->min = vr->max = NULL_TREE; - if (vr->equiv) - bitmap_clear (vr->equiv); -} - - /* Set value range VR to a range of a truthvalue of type TYPE. */ static inline void @@ -314,9 +435,13 @@ get_value_range (tree var) static inline bool vrp_operand_equal_p (tree val1, tree val2) { - return (val1 == val2 - || (val1 && val2 - && operand_equal_p (val1, val2, 0))); + if (val1 == val2) + return true; + if (!val1 || !val2 || !operand_equal_p (val1, val2, 0)) + return false; + if (is_overflow_infinity (val1)) + return is_overflow_infinity (val2); + return true; } /* Return true, if the bitmaps B1 and B2 are equal. */ @@ -408,28 +533,32 @@ symbolic_range_p (value_range_t *vr) || !is_gimple_min_invariant (vr->max)); } -/* Like tree_expr_nonnegative_p, but this function uses value ranges - obtained so far. */ +/* Return true if value range VR uses a overflow infinity. */ -static bool -vrp_expr_computes_nonnegative (tree expr) +static inline bool +overflow_infinity_range_p (value_range_t *vr) { - bool ovf; + return (vr->type == VR_RANGE + && (is_overflow_infinity (vr->min) + || is_overflow_infinity (vr->max))); +} - /* FIXME: May need to record overflow information here. */ - return tree_expr_nonnegative_warnv_p (expr, &ovf); +/* Like tree_expr_nonnegative_warnv_p, but this function uses value + ranges obtained so far. */ + +static bool +vrp_expr_computes_nonnegative (tree expr, bool *strict_overflow_p) +{ + return tree_expr_nonnegative_warnv_p (expr, strict_overflow_p); } -/* Like tree_expr_nonzero_p, but this function uses value ranges +/* Like tree_expr_nonzero_warnv_p, but this function uses value ranges obtained so far. */ static bool -vrp_expr_computes_nonzero (tree expr) +vrp_expr_computes_nonzero (tree expr, bool *strict_overflow_p) { - bool ovf; - - /* FIXME: May need to record overflow information here. */ - if (tree_expr_nonzero_warnv_p (expr, &ovf)) + if (tree_expr_nonzero_warnv_p (expr, strict_overflow_p)) return true; /* If we have an expression of the form &X->a, then the expression @@ -475,20 +604,36 @@ valid_value_p (tree expr) static inline int operand_less_p (tree val, tree val2) { - tree tcmp; /* LT is folded faster than GE and others. Inline the common case. */ if (TREE_CODE (val) == INTEGER_CST && TREE_CODE (val2) == INTEGER_CST) { if (TYPE_UNSIGNED (TREE_TYPE (val))) return INT_CST_LT_UNSIGNED (val, val2); else - return INT_CST_LT (val, val2); + { + if (INT_CST_LT (val, val2)) + return 1; + } } else - tcmp = fold_binary_to_constant (LT_EXPR, boolean_type_node, val, val2); - if (!tcmp) - return -2; - return !integer_zerop (tcmp); + { + tree tcmp; + + tcmp = fold_binary_to_constant (LT_EXPR, boolean_type_node, val, val2); + if (!tcmp) + return -2; + + if (!integer_zerop (tcmp)) + return 1; + } + + /* val >= val2, not considering overflow infinity. */ + if (is_negative_overflow_infinity (val)) + return is_negative_overflow_infinity (val2) ? 0 : 1; + else if (is_positive_overflow_infinity (val2)) + return is_positive_overflow_infinity (val) ? 0 : 1; + + return 0; } /* Compare two values VAL1 and VAL2. Return @@ -500,10 +645,14 @@ operand_less_p (tree val, tree val2) +2 if VAL1 != VAL2 This is similar to tree_int_cst_compare but supports pointer values - and values that cannot be compared at compile time. */ + and values that cannot be compared at compile time. + + If STRICT_OVERFLOW_P is not NULL, then set *STRICT_OVERFLOW_P to + true if the return value is only valid if we assume that signed + overflow is undefined. */ static int -compare_values (tree val1, tree val2) +compare_values_warnv (tree val1, tree val2, bool *strict_overflow_p) { if (val1 == val2) return 0; @@ -539,6 +688,8 @@ compare_values (tree val1, tree val2) c1 = TREE_OPERAND (val1, 1); if (tree_int_cst_sgn (c1) == -1) { + if (is_negative_overflow_infinity (c1)) + return -2; c1 = fold_unary_to_constant (NEGATE_EXPR, TREE_TYPE (c1), c1); if (!c1) return -2; @@ -559,6 +710,8 @@ compare_values (tree val1, tree val2) c2 = TREE_OPERAND (val2, 1); if (tree_int_cst_sgn (c2) == -1) { + if (is_negative_overflow_infinity (c2)) + return -2; c2 = fold_unary_to_constant (NEGATE_EXPR, TREE_TYPE (c2), c2); if (!c2) return -2; @@ -579,6 +732,9 @@ compare_values (tree val1, tree val2) if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (val1))) return -2; + if (strict_overflow_p != NULL) + *strict_overflow_p = true; + if (code1 == SSA_NAME) { if (code2 == PLUS_EXPR) @@ -595,7 +751,7 @@ compare_values (tree val1, tree val2) return 1; else if (code2 == PLUS_EXPR) /* NAME + CST1 > NAME + CST2, if CST1 > CST2 */ - return compare_values (c1, c2); + return compare_values_warnv (c1, c2, strict_overflow_p); else if (code2 == MINUS_EXPR) /* NAME + CST1 > NAME - CST2 */ return 1; @@ -611,7 +767,7 @@ compare_values (tree val1, tree val2) else if (code2 == MINUS_EXPR) /* NAME - CST1 > NAME - CST2, if CST1 < CST2. Notice that C1 and C2 are swapped in the call to compare_values. */ - return compare_values (c2, c1); + return compare_values_warnv (c2, c1, strict_overflow_p); } gcc_unreachable (); @@ -623,9 +779,23 @@ compare_values (tree val1, tree val2) if (!POINTER_TYPE_P (TREE_TYPE (val1))) { - /* We cannot compare overflowed values. */ + /* We cannot compare overflowed values, except for overflow + infinities. */ if (TREE_OVERFLOW (val1) || TREE_OVERFLOW (val2)) - return -2; + { + if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (val1))) + return -2; + + if (is_negative_overflow_infinity (val1)) + return is_negative_overflow_infinity (val2) ? 0 : -1; + else if (is_negative_overflow_infinity (val2)) + return 1; + else if (is_positive_overflow_infinity (val1)) + return is_positive_overflow_infinity (val2) ? 0 : 1; + else if (is_positive_overflow_infinity (val2)) + return -1; + return -2; + } return tree_int_cst_compare (val1, val2); } @@ -661,6 +831,22 @@ compare_values (tree val1, tree val2) } } +/* Compare values like compare_values_warnv, but treat comparisons + which rely on undefined overflow as incomparable. */ + +static int +compare_values (tree val1, tree val2) +{ + bool sop; + int ret; + + sop = false; + ret = compare_values_warnv (val1, val2, &sop); + if (sop) + ret = -2; + return ret; +} + /* Return 1 if VAL is inside value range VR (VR->MIN <= VAL <= VR->MAX), 0 if VAL is not inside VR, @@ -926,8 +1112,10 @@ extract_range_from_assert (value_range_t *vr_p, tree expr) /* If MIN and MAX cover the whole range for their type, then just use the original LIMIT. */ if (INTEGRAL_TYPE_P (type) - && min == TYPE_MIN_VALUE (type) - && max == TYPE_MAX_VALUE (type)) + && (min == TYPE_MIN_VALUE (type) + || is_negative_overflow_infinity (min)) + && (max == TYPE_MAX_VALUE (type) + || is_positive_overflow_infinity (max))) min = max = limit; set_value_range (vr_p, VR_ANTI_RANGE, min, max, vr_p->equiv); @@ -954,7 +1142,8 @@ extract_range_from_assert (value_range_t *vr_p, tree expr) else { /* For LT_EXPR, we create the range [MIN, MAX - 1]. */ - if (cond_code == LT_EXPR) + if (cond_code == LT_EXPR + && !is_positive_overflow_infinity (max)) { tree one = build_int_cst (type, 1); max = fold_build2 (MINUS_EXPR, type, max, one); @@ -985,7 +1174,8 @@ extract_range_from_assert (value_range_t *vr_p, tree expr) else { /* For GT_EXPR, we create the range [MIN + 1, MAX]. */ - if (cond_code == GT_EXPR) + if (cond_code == GT_EXPR + && !is_negative_overflow_infinity (min)) { tree one = build_int_cst (type, 1); min = fold_build2 (PLUS_EXPR, type, min, one); @@ -1156,9 +1346,21 @@ extract_range_from_assert (value_range_t *vr_p, tree expr) || cmp == 0) && compare_values (anti_max, real_max) == -1) { - min = fold_build2 (PLUS_EXPR, TREE_TYPE (var_vr->min), - anti_max, - build_int_cst (TREE_TYPE (var_vr->min), 1)); + gcc_assert (!is_positive_overflow_infinity (anti_max)); + if (needs_overflow_infinity (TREE_TYPE (anti_max)) + && anti_max == TYPE_MAX_VALUE (TREE_TYPE (anti_max))) + { + if (!supports_overflow_infinity (TREE_TYPE (var_vr->min))) + { + set_value_range_to_varying (vr_p); + return; + } + min = positive_overflow_infinity (TREE_TYPE (var_vr->min)); + } + else + min = fold_build2 (PLUS_EXPR, TREE_TYPE (var_vr->min), + anti_max, + build_int_cst (TREE_TYPE (var_vr->min), 1)); max = real_max; set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv); } @@ -1169,9 +1371,21 @@ extract_range_from_assert (value_range_t *vr_p, tree expr) && ((cmp = compare_values (anti_min, real_max)) == -1 || cmp == 0)) { - max = fold_build2 (MINUS_EXPR, TREE_TYPE (var_vr->min), - anti_min, - build_int_cst (TREE_TYPE (var_vr->min), 1)); + gcc_assert (!is_negative_overflow_infinity (anti_min)); + if (needs_overflow_infinity (TREE_TYPE (anti_min)) + && anti_min == TYPE_MIN_VALUE (TREE_TYPE (anti_min))) + { + if (!supports_overflow_infinity (TREE_TYPE (var_vr->min))) + { + set_value_range_to_varying (vr_p); + return; + } + max = negative_overflow_infinity (TREE_TYPE (var_vr->min)); + } + else + max = fold_build2 (MINUS_EXPR, TREE_TYPE (var_vr->min), + anti_min, + build_int_cst (TREE_TYPE (var_vr->min), 1)); min = real_min; set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv); } @@ -1209,9 +1423,11 @@ extract_range_from_ssa_name (value_range_t *vr, tree 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. */ + -INF or +INF depending on CODE, VAL1 and VAL2. This can return + NULL_TREE if we need to use an overflow infinity representation but + the type does not support it. */ -static inline tree +static tree vrp_int_const_binop (enum tree_code code, tree val1, tree val2) { tree res; @@ -1257,9 +1473,11 @@ vrp_int_const_binop (enum tree_code code, tree val1, tree val2) } } - else if (TREE_OVERFLOW (res) - && !TREE_OVERFLOW (val1) - && !TREE_OVERFLOW (val2)) + else if ((TREE_OVERFLOW (res) + && !TREE_OVERFLOW (val1) + && !TREE_OVERFLOW (val2)) + || is_overflow_infinity (val1) + || is_overflow_infinity (val2)) { /* If the operation overflowed but neither VAL1 nor VAL2 are overflown, return -INF or +INF depending on the operation @@ -1267,6 +1485,19 @@ vrp_int_const_binop (enum tree_code code, tree val1, tree val2) int sgn1 = tree_int_cst_sgn (val1); int sgn2 = tree_int_cst_sgn (val2); + if (needs_overflow_infinity (TREE_TYPE (res)) + && !supports_overflow_infinity (TREE_TYPE (res))) + return NULL_TREE; + + /* We have to punt on subtracting infinities of the same sign, + since we can't tell what the sign of the result should + be. */ + if (code == MINUS_EXPR + && sgn1 == sgn2 + && is_overflow_infinity (val1) + && is_overflow_infinity (val2)) + return NULL_TREE; + /* Notice that we only need to handle the restricted set of operations handled by extract_range_from_binary_expr. Among them, only multiplication, addition and subtraction @@ -1282,22 +1513,30 @@ vrp_int_const_binop (enum tree_code code, tree val1, tree val2) to yield an overflow. Its sign is therefore that of one of the operands, for example the first. */ || (code == PLUS_EXPR && sgn1 > 0) - /* For subtraction, the operands must be of different - signs to yield an overflow. Its sign is therefore - that of the first operand or the opposite of that - of the second operand. A first operand of 0 counts - as positive here, for the corner case 0 - (-INF), - which overflows, but must yield +INF. */ - || (code == MINUS_EXPR && sgn1 >= 0) + /* For subtraction, non-infinite operands must be of + different signs to yield an overflow. Its sign is + therefore that of the first operand or the opposite of + that of the second operand. A first operand of 0 counts + as positive here, for the corner case 0 - (-INF), which + overflows, but must yield +INF. For infinite operands 0 + - INF is negative, not positive. */ + || (code == MINUS_EXPR + && (sgn1 >= 0 + ? !is_positive_overflow_infinity (val2) + : is_negative_overflow_infinity (val2))) /* For division, the only case is -INF / -1 = +INF. */ || code == TRUNC_DIV_EXPR || code == FLOOR_DIV_EXPR || code == CEIL_DIV_EXPR || code == EXACT_DIV_EXPR || code == ROUND_DIV_EXPR) - return TYPE_MAX_VALUE (TREE_TYPE (res)); + return (needs_overflow_infinity (TREE_TYPE (res)) + ? positive_overflow_infinity (TREE_TYPE (res)) + : TYPE_MAX_VALUE (TREE_TYPE (res))); else - return TYPE_MIN_VALUE (TREE_TYPE (res)); + return (needs_overflow_infinity (TREE_TYPE (res)) + ? negative_overflow_infinity (TREE_TYPE (res)) + : TYPE_MIN_VALUE (TREE_TYPE (res))); } return res; @@ -1451,7 +1690,9 @@ extract_range_from_binary_expr (value_range_t *vr, tree expr) && vr1.type != VR_VARYING && vr0.type == vr1.type && !symbolic_range_p (&vr0) - && !symbolic_range_p (&vr1)) + && !overflow_infinity_range_p (&vr0) + && !symbolic_range_p (&vr1) + && !overflow_infinity_range_p (&vr1)) { /* Boolean expressions cannot be folded with int_const_binop. */ min = fold_binary (code, TREE_TYPE (expr), vr0.min, vr1.min); @@ -1496,6 +1737,7 @@ extract_range_from_binary_expr (value_range_t *vr, tree expr) { tree val[4]; size_t i; + bool sop; /* If we have an unsigned MULT_EXPR with two VR_ANTI_RANGEs, drop to VR_VARYING. It would take more effort to compute a @@ -1535,19 +1777,43 @@ extract_range_from_binary_expr (value_range_t *vr, tree expr) } /* Compute the 4 cross operations. */ + sop = false; val[0] = vrp_int_const_binop (code, vr0.min, vr1.min); + if (val[0] == NULL_TREE) + sop = true; + + if (vr1.max == vr1.min) + val[1] = NULL_TREE; + else + { + val[1] = vrp_int_const_binop (code, vr0.min, vr1.max); + if (val[1] == NULL_TREE) + sop = true; + } - val[1] = (vr1.max != vr1.min) - ? vrp_int_const_binop (code, vr0.min, vr1.max) - : NULL_TREE; + if (vr0.max == vr0.min) + val[2] = NULL_TREE; + else + { + val[2] = vrp_int_const_binop (code, vr0.max, vr1.min); + if (val[2] == NULL_TREE) + sop = true; + } - val[2] = (vr0.max != vr0.min) - ? vrp_int_const_binop (code, vr0.max, vr1.min) - : NULL_TREE; + 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); + if (val[3] == NULL_TREE) + sop = true; + } - val[3] = (vr0.min != vr0.max && vr1.min != vr1.max) - ? vrp_int_const_binop (code, vr0.max, vr1.max) - : NULL_TREE; + if (sop) + { + set_value_range_to_varying (vr); + return; + } /* Set MIN to the minimum of VAL[i] and MAX to the maximum of VAL[i]. */ @@ -1555,13 +1821,17 @@ extract_range_from_binary_expr (value_range_t *vr, tree expr) max = val[0]; for (i = 1; i < 4; i++) { - if (!is_gimple_min_invariant (min) || TREE_OVERFLOW (min) - || !is_gimple_min_invariant (max) || TREE_OVERFLOW (max)) + if (!is_gimple_min_invariant (min) + || (TREE_OVERFLOW (min) && !is_overflow_infinity (min)) + || !is_gimple_min_invariant (max) + || (TREE_OVERFLOW (max) && !is_overflow_infinity (max))) break; if (val[i]) { - if (!is_gimple_min_invariant (val[i]) || TREE_OVERFLOW (val[i])) + if (!is_gimple_min_invariant (val[i]) + || (TREE_OVERFLOW (val[i]) + && !is_overflow_infinity (val[i]))) { /* If we found an overflowed value, set MIN and MAX to it so that we set the resulting range to @@ -1602,16 +1872,18 @@ extract_range_from_binary_expr (value_range_t *vr, tree expr) { if (vr0.type == VR_RANGE && vr0.min == vr0.max - && tree_expr_nonnegative_p (vr0.max) - && TREE_CODE (vr0.max) == INTEGER_CST) + && TREE_CODE (vr0.max) == INTEGER_CST + && !TREE_OVERFLOW (vr0.max) + && tree_int_cst_sgn (vr0.max) >= 0) { min = build_int_cst (TREE_TYPE (expr), 0); max = vr0.max; } else if (vr1.type == VR_RANGE - && vr1.min == vr1.max - && tree_expr_nonnegative_p (vr1.max) - && TREE_CODE (vr1.max) == INTEGER_CST) + && vr1.min == vr1.max + && TREE_CODE (vr1.max) == INTEGER_CST + && !TREE_OVERFLOW (vr1.max) + && tree_int_cst_sgn (vr1.max) >= 0) { type = VR_RANGE; min = build_int_cst (TREE_TYPE (expr), 0); @@ -1627,9 +1899,23 @@ extract_range_from_binary_expr (value_range_t *vr, tree expr) gcc_unreachable (); /* If either MIN or MAX overflowed, then set the resulting range to - VARYING. */ - if (!is_gimple_min_invariant (min) || TREE_OVERFLOW (min) - || !is_gimple_min_invariant (max) || TREE_OVERFLOW (max)) + VARYING. But we do accept an overflow infinity + representation. */ + if (min == NULL_TREE + || !is_gimple_min_invariant (min) + || (TREE_OVERFLOW (min) && !is_overflow_infinity (min)) + || max == NULL_TREE + || !is_gimple_min_invariant (max) + || (TREE_OVERFLOW (max) && !is_overflow_infinity (max))) + { + set_value_range_to_varying (vr); + return; + } + + if ((min == TYPE_MIN_VALUE (TREE_TYPE (min)) + || is_negative_overflow_infinity (min)) + && (max == TYPE_MAX_VALUE (TREE_TYPE (max)) + || is_positive_overflow_infinity (max))) { set_value_range_to_varying (vr); return; @@ -1703,10 +1989,12 @@ extract_range_from_unary_expr (value_range_t *vr, tree expr) determining if it evaluates to NULL [0, 0] or non-NULL (~[0, 0]). */ if (POINTER_TYPE_P (TREE_TYPE (expr)) || POINTER_TYPE_P (TREE_TYPE (op0))) { - bool ovf; + bool sop; - /* FIXME: May need to record overflow information here. */ - if (range_is_nonnull (&vr0) || tree_expr_nonzero_warnv_p (expr, &ovf)) + sop = false; + if (range_is_nonnull (&vr0) + || (tree_expr_nonzero_warnv_p (expr, &sop) + && !sop)) set_value_range_to_nonnull (vr, TREE_TYPE (expr)); else if (range_is_null (&vr0)) set_value_range_to_null (vr, TREE_TYPE (expr)); @@ -1729,7 +2017,8 @@ extract_range_from_unary_expr (value_range_t *vr, tree expr) or equal to the new max, then we can safely use the newly computed range for EXPR. This allows us to compute accurate ranges through many casts. */ - if (vr0.type == VR_RANGE + if ((vr0.type == VR_RANGE + && !overflow_infinity_range_p (&vr0)) || (vr0.type == VR_VARYING && TYPE_PRECISION (outer_type) > TYPE_PRECISION (inner_type))) { @@ -1797,22 +2086,44 @@ extract_range_from_unary_expr (value_range_t *vr, tree expr) && !TYPE_UNSIGNED (TREE_TYPE (expr))) { /* NEGATE_EXPR flips the range around. We need to treat - TYPE_MIN_VALUE specially dependent on wrapping, range type - and if it was used as minimum or maximum value: - -~[MIN, MIN] == ~[MIN, MIN] - -[MIN, 0] == [0, MAX] for -fno-wrapv - -[MIN, 0] == [0, MIN] for -fwrapv (will be set to varying later) */ - min = vr0.max == TYPE_MIN_VALUE (TREE_TYPE (expr)) - ? TYPE_MIN_VALUE (TREE_TYPE (expr)) - : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max); - - max = (vr0.min == TYPE_MIN_VALUE (TREE_TYPE (expr)) - ? ((vr0.type == VR_ANTI_RANGE - || TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr))) - ? TYPE_MIN_VALUE (TREE_TYPE (expr)) - : TYPE_MAX_VALUE (TREE_TYPE (expr))) - : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min)); - + TYPE_MIN_VALUE specially. */ + if (is_positive_overflow_infinity (vr0.max)) + min = negative_overflow_infinity (TREE_TYPE (expr)); + else if (is_negative_overflow_infinity (vr0.max)) + min = positive_overflow_infinity (TREE_TYPE (expr)); + else if (vr0.max != TYPE_MIN_VALUE (TREE_TYPE (expr))) + min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max); + else if (needs_overflow_infinity (TREE_TYPE (expr))) + { + if (supports_overflow_infinity (TREE_TYPE (expr))) + min = positive_overflow_infinity (TREE_TYPE (expr)); + else + { + set_value_range_to_varying (vr); + return; + } + } + else + min = TYPE_MIN_VALUE (TREE_TYPE (expr)); + + if (is_positive_overflow_infinity (vr0.min)) + max = negative_overflow_infinity (TREE_TYPE (expr)); + else if (is_negative_overflow_infinity (vr0.min)) + max = positive_overflow_infinity (TREE_TYPE (expr)); + else if (vr0.min != TYPE_MIN_VALUE (TREE_TYPE (expr))) + max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min); + else if (needs_overflow_infinity (TREE_TYPE (expr))) + { + if (supports_overflow_infinity (TREE_TYPE (expr))) + max = positive_overflow_infinity (TREE_TYPE (expr)); + else + { + set_value_range_to_varying (vr); + return; + } + } + else + max = TYPE_MIN_VALUE (TREE_TYPE (expr)); } else if (code == NEGATE_EXPR && TYPE_UNSIGNED (TREE_TYPE (expr))) @@ -1849,11 +2160,33 @@ extract_range_from_unary_expr (value_range_t *vr, tree expr) /* ABS_EXPR may flip the range around, if the original range included negative values. */ - min = (vr0.min == TYPE_MIN_VALUE (TREE_TYPE (expr))) - ? TYPE_MAX_VALUE (TREE_TYPE (expr)) - : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min); + if (is_overflow_infinity (vr0.min)) + min = positive_overflow_infinity (TREE_TYPE (expr)); + else if (vr0.min != TYPE_MIN_VALUE (TREE_TYPE (expr))) + min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min); + else if (!needs_overflow_infinity (TREE_TYPE (expr))) + min = TYPE_MAX_VALUE (TREE_TYPE (expr)); + else if (supports_overflow_infinity (TREE_TYPE (expr))) + min = positive_overflow_infinity (TREE_TYPE (expr)); + else + { + set_value_range_to_varying (vr); + return; + } - max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max); + if (is_overflow_infinity (vr0.max)) + max = positive_overflow_infinity (TREE_TYPE (expr)); + else if (vr0.max != TYPE_MIN_VALUE (TREE_TYPE (expr))) + max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max); + else if (!needs_overflow_infinity (TREE_TYPE (expr))) + max = TYPE_MAX_VALUE (TREE_TYPE (expr)); + else if (supports_overflow_infinity (TREE_TYPE (expr))) + max = positive_overflow_infinity (TREE_TYPE (expr)); + else + { + set_value_range_to_varying (vr); + return; + } cmp = compare_values (min, max); @@ -1863,8 +2196,6 @@ extract_range_from_unary_expr (value_range_t *vr, tree expr) { if (range_includes_zero_p (&vr0)) { - tree type_min_value = TYPE_MIN_VALUE (TREE_TYPE (expr)); - /* Take the lower of the two values. */ if (cmp != 1) max = min; @@ -1873,12 +2204,22 @@ extract_range_from_unary_expr (value_range_t *vr, tree expr) or ~[-INF + 1, min (abs(MIN), abs(MAX))] when flag_wrapv is set and the original anti-range doesn't include TYPE_MIN_VALUE, remember -TYPE_MIN_VALUE = TYPE_MIN_VALUE. */ - min = ((TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr)) - && vr0.min != type_min_value) - ? int_const_binop (PLUS_EXPR, - type_min_value, - integer_one_node, 0) - : type_min_value); + if (TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr))) + { + tree type_min_value = TYPE_MIN_VALUE (TREE_TYPE (expr)); + + min = (vr0.min != type_min_value + ? int_const_binop (PLUS_EXPR, type_min_value, + integer_one_node, 0) + : type_min_value); + } + else + { + if (overflow_infinity_range_p (&vr0)) + min = negative_overflow_infinity (TREE_TYPE (expr)); + else + min = TYPE_MIN_VALUE (TREE_TYPE (expr)); + } } else { @@ -1887,7 +2228,18 @@ extract_range_from_unary_expr (value_range_t *vr, tree expr) anti-range. */ vr0.type = VR_RANGE; min = build_int_cst (TREE_TYPE (expr), 0); - max = TYPE_MAX_VALUE (TREE_TYPE (expr)); + if (needs_overflow_infinity (TREE_TYPE (expr))) + { + if (supports_overflow_infinity (TREE_TYPE (expr))) + max = positive_overflow_infinity (TREE_TYPE (expr)); + else + { + set_value_range_to_varying (vr); + return; + } + } + else + max = TYPE_MAX_VALUE (TREE_TYPE (expr)); } } @@ -1915,6 +2267,40 @@ extract_range_from_unary_expr (value_range_t *vr, tree expr) /* Otherwise, operate on each end of the range. */ min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min); max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max); + + if (needs_overflow_infinity (TREE_TYPE (expr))) + { + gcc_assert (code != NEGATE_EXPR && code != ABS_EXPR); + if (is_overflow_infinity (vr0.min)) + min = vr0.min; + else if (TREE_OVERFLOW (min)) + { + if (supports_overflow_infinity (TREE_TYPE (expr))) + min = (tree_int_cst_sgn (min) >= 0 + ? positive_overflow_infinity (TREE_TYPE (min)) + : negative_overflow_infinity (TREE_TYPE (min))); + else + { + set_value_range_to_varying (vr); + return; + } + } + + if (is_overflow_infinity (vr0.max)) + max = vr0.max; + else if (TREE_OVERFLOW (max)) + { + if (supports_overflow_infinity (TREE_TYPE (expr))) + max = (tree_int_cst_sgn (max) >= 0 + ? positive_overflow_infinity (TREE_TYPE (max)) + : negative_overflow_infinity (TREE_TYPE (max))); + else + { + set_value_range_to_varying (vr); + return; + } + } + } } cmp = compare_values (min, max); @@ -1970,8 +2356,15 @@ extract_range_from_cond_expr (value_range_t *vr, tree expr) static void extract_range_from_comparison (value_range_t *vr, tree expr) { - tree val = vrp_evaluate_conditional (expr, false); - if (val) + bool sop = false; + tree val = vrp_evaluate_conditional (expr, false, &sop); + + /* A disadvantage of using a special infinity as an overflow + representation is that we lose the ability to record overflow + when we don't have an infinity. So we have to ignore a result + which relies on overflow. */ + + if (val && !is_overflow_infinity (val) && !sop) { /* Since this expression was found on the RHS of an assignment, its type may be different from _Bool. Convert VAL to EXPR's @@ -2021,10 +2414,14 @@ extract_range_from_expr (value_range_t *vr, tree expr) with range data. */ if (vr->type == VR_VARYING) { + bool sop = false; + if (INTEGRAL_TYPE_P (TREE_TYPE (expr)) - && vrp_expr_computes_nonnegative (expr)) - set_value_range_to_nonnegative (vr, TREE_TYPE (expr)); - else if (vrp_expr_computes_nonzero (expr)) + && vrp_expr_computes_nonnegative (expr, &sop)) + set_value_range_to_nonnegative (vr, TREE_TYPE (expr), + sop || is_overflow_infinity (expr)); + else if (vrp_expr_computes_nonzero (expr, &sop) + && !sop) set_value_range_to_nonnull (vr, TREE_TYPE (expr)); } } @@ -2070,6 +2467,11 @@ adjust_range_with_scev (value_range_t *vr, struct loop *loop, tree stmt, true)) return; + /* We use TYPE_MIN_VALUE and TYPE_MAX_VALUE here instead of + negative_overflow_infinity and positive_overflow_infinity, + because we have concluded that the loop probably does not + wrap. */ + type = TREE_TYPE (var); if (POINTER_TYPE_P (type) || !TYPE_MIN_VALUE (type)) tmin = lower_bound_in_type (type, type); @@ -2149,11 +2551,15 @@ adjust_range_with_scev (value_range_t *vr, struct loop *loop, tree stmt, - Return BOOLEAN_FALSE_NODE if the comparison always returns false. - Return NULL_TREE if it is not always possible to determine the - value of the comparison. */ + value of the comparison. + + Also set *STRICT_OVERFLOW_P to indicate whether a range with an + overflow infinity was used in the test. */ static tree -compare_ranges (enum tree_code comp, value_range_t *vr0, value_range_t *vr1) +compare_ranges (enum tree_code comp, value_range_t *vr0, value_range_t *vr1, + bool *strict_overflow_p) { /* VARYING or UNDEFINED ranges cannot be compared. */ if (vr0->type == VR_VARYING @@ -2189,8 +2595,8 @@ compare_ranges (enum tree_code comp, value_range_t *vr0, value_range_t *vr1) gcc_assert (comp == NE_EXPR || comp == EQ_EXPR); - if (compare_values (vr0->min, vr1->min) == 0 - && compare_values (vr0->max, vr1->max) == 0) + if (compare_values_warnv (vr0->min, vr1->min, strict_overflow_p) == 0 + && compare_values_warnv (vr0->max, vr1->max, strict_overflow_p) == 0) return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node; return NULL_TREE; @@ -2211,19 +2617,23 @@ compare_ranges (enum tree_code comp, value_range_t *vr0, value_range_t *vr1) { /* Equality may only be computed if both ranges represent exactly one value. */ - if (compare_values (vr0->min, vr0->max) == 0 - && compare_values (vr1->min, vr1->max) == 0) + if (compare_values_warnv (vr0->min, vr0->max, strict_overflow_p) == 0 + && compare_values_warnv (vr1->min, vr1->max, strict_overflow_p) == 0) { - int cmp_min = compare_values (vr0->min, vr1->min); - int cmp_max = compare_values (vr0->max, vr1->max); + int cmp_min = compare_values_warnv (vr0->min, vr1->min, + strict_overflow_p); + int cmp_max = compare_values_warnv (vr0->max, vr1->max, + strict_overflow_p); if (cmp_min == 0 && cmp_max == 0) return boolean_true_node; else if (cmp_min != -2 && cmp_max != -2) return boolean_false_node; } /* If [V0_MIN, V1_MAX] < [V1_MIN, V1_MAX] then V0 != V1. */ - else if (compare_values (vr0->min, vr1->max) == 1 - || compare_values (vr1->min, vr0->max) == 1) + else if (compare_values_warnv (vr0->min, vr1->max, + strict_overflow_p) == 1 + || compare_values_warnv (vr1->min, vr0->max, + strict_overflow_p) == 1) return boolean_false_node; return NULL_TREE; @@ -2237,17 +2647,21 @@ compare_ranges (enum tree_code comp, value_range_t *vr0, value_range_t *vr1) make sure that both comparisons yield similar results to avoid comparing values that cannot be compared at compile-time. */ - cmp1 = compare_values (vr0->max, vr1->min); - cmp2 = compare_values (vr0->min, vr1->max); + cmp1 = compare_values_warnv (vr0->max, vr1->min, strict_overflow_p); + cmp2 = compare_values_warnv (vr0->min, vr1->max, strict_overflow_p); if ((cmp1 == -1 && cmp2 == -1) || (cmp1 == 1 && cmp2 == 1)) return boolean_true_node; /* If VR0 and VR1 represent a single value and are identical, return false. */ - else if (compare_values (vr0->min, vr0->max) == 0 - && compare_values (vr1->min, vr1->max) == 0 - && compare_values (vr0->min, vr1->min) == 0 - && compare_values (vr0->max, vr1->max) == 0) + else if (compare_values_warnv (vr0->min, vr0->max, + strict_overflow_p) == 0 + && compare_values_warnv (vr1->min, vr1->max, + strict_overflow_p) == 0 + && compare_values_warnv (vr0->min, vr1->min, + strict_overflow_p) == 0 + && compare_values_warnv (vr0->max, vr1->max, + strict_overflow_p) == 0) return boolean_false_node; /* Otherwise, they may or may not be different. */ @@ -2259,16 +2673,26 @@ compare_ranges (enum tree_code comp, value_range_t *vr0, value_range_t *vr1) int tst; /* If VR0 is to the left of VR1, return true. */ - tst = compare_values (vr0->max, vr1->min); + tst = compare_values_warnv (vr0->max, vr1->min, strict_overflow_p); if ((comp == LT_EXPR && tst == -1) || (comp == LE_EXPR && (tst == -1 || tst == 0))) - return boolean_true_node; + { + if (overflow_infinity_range_p (vr0) + || overflow_infinity_range_p (vr1)) + *strict_overflow_p = true; + return boolean_true_node; + } /* If VR0 is to the right of VR1, return false. */ - tst = compare_values (vr0->min, vr1->max); + tst = compare_values_warnv (vr0->min, vr1->max, strict_overflow_p); if ((comp == LT_EXPR && (tst == 0 || tst == 1)) || (comp == LE_EXPR && tst == 1)) - return boolean_false_node; + { + if (overflow_infinity_range_p (vr0) + || overflow_infinity_range_p (vr1)) + *strict_overflow_p = true; + return boolean_false_node; + } /* Otherwise, we don't know. */ return NULL_TREE; @@ -2282,10 +2706,13 @@ compare_ranges (enum tree_code comp, value_range_t *vr0, value_range_t *vr1) BOOLEAN_TRUE_NODE if VR COMP VAL always returns true for all the values in VR. Return BOOLEAN_FALSE_NODE if the comparison always returns false. Return NULL_TREE if it is not always - possible to determine the value of the comparison. */ + possible to determine the value of the comparison. Also set + *STRICT_OVERFLOW_P to indicate whether a range with an overflow + infinity was used in the test. */ static tree -compare_range_with_value (enum tree_code comp, value_range_t *vr, tree val) +compare_range_with_value (enum tree_code comp, value_range_t *vr, tree val, + bool *strict_overflow_p) { if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED) return NULL_TREE; @@ -2312,16 +2739,16 @@ compare_range_with_value (enum tree_code comp, value_range_t *vr, tree val) { /* EQ_EXPR may only be computed if VR represents exactly one value. */ - if (compare_values (vr->min, vr->max) == 0) + if (compare_values_warnv (vr->min, vr->max, strict_overflow_p) == 0) { - int cmp = compare_values (vr->min, val); + int cmp = compare_values_warnv (vr->min, val, strict_overflow_p); if (cmp == 0) return boolean_true_node; else if (cmp == -1 || cmp == 1 || cmp == 2) return boolean_false_node; } - else if (compare_values (val, vr->min) == -1 - || compare_values (vr->max, val) == -1) + else if (compare_values_warnv (val, vr->min, strict_overflow_p) == -1 + || compare_values_warnv (vr->max, val, strict_overflow_p) == -1) return boolean_false_node; return NULL_TREE; @@ -2329,14 +2756,14 @@ compare_range_with_value (enum tree_code comp, value_range_t *vr, tree val) else if (comp == NE_EXPR) { /* If VAL is not inside VR, then they are always different. */ - if (compare_values (vr->max, val) == -1 - || compare_values (vr->min, val) == 1) + if (compare_values_warnv (vr->max, val, strict_overflow_p) == -1 + || compare_values_warnv (vr->min, val, strict_overflow_p) == 1) return boolean_true_node; /* If VR represents exactly one value equal to VAL, then return false. */ - if (compare_values (vr->min, vr->max) == 0 - && compare_values (vr->min, val) == 0) + if (compare_values_warnv (vr->min, vr->max, strict_overflow_p) == 0 + && compare_values_warnv (vr->min, val, strict_overflow_p) == 0) return boolean_false_node; /* Otherwise, they may or may not be different. */ @@ -2347,16 +2774,24 @@ compare_range_with_value (enum tree_code comp, value_range_t *vr, tree val) int tst; /* If VR is to the left of VAL, return true. */ - tst = compare_values (vr->max, val); + tst = compare_values_warnv (vr->max, val, strict_overflow_p); if ((comp == LT_EXPR && tst == -1) || (comp == LE_EXPR && (tst == -1 || tst == 0))) - return boolean_true_node; + { + if (overflow_infinity_range_p (vr)) + *strict_overflow_p = true; + return boolean_true_node; + } /* If VR is to the right of VAL, return false. */ - tst = compare_values (vr->min, val); + tst = compare_values_warnv (vr->min, val, strict_overflow_p); if ((comp == LT_EXPR && (tst == 0 || tst == 1)) || (comp == LE_EXPR && tst == 1)) - return boolean_false_node; + { + if (overflow_infinity_range_p (vr)) + *strict_overflow_p = true; + return boolean_false_node; + } /* Otherwise, we don't know. */ return NULL_TREE; @@ -2366,16 +2801,24 @@ compare_range_with_value (enum tree_code comp, value_range_t *vr, tree val) int tst; /* If VR is to the right of VAL, return true. */ - tst = compare_values (vr->min, val); + tst = compare_values_warnv (vr->min, val, strict_overflow_p); if ((comp == GT_EXPR && tst == 1) || (comp == GE_EXPR && (tst == 0 || tst == 1))) - return boolean_true_node; + { + if (overflow_infinity_range_p (vr)) + *strict_overflow_p = true; + return boolean_true_node; + } /* If VR is to the left of VAL, return false. */ - tst = compare_values (vr->max, val); + tst = compare_values_warnv (vr->max, val, strict_overflow_p); if ((comp == GT_EXPR && (tst == -1 || tst == 0)) || (comp == GE_EXPR && tst == -1)) - return boolean_false_node; + { + if (overflow_infinity_range_p (vr)) + *strict_overflow_p = true; + return boolean_false_node; + } /* Otherwise, we don't know. */ return NULL_TREE; @@ -2414,6 +2857,9 @@ dump_value_range (FILE *file, value_range_t *vr) && !TYPE_UNSIGNED (type) && vr->min == TYPE_MIN_VALUE (type)) fprintf (file, "-INF"); + else if (needs_overflow_infinity (type) + && is_negative_overflow_infinity (vr->min)) + fprintf (file, "-INF(OVF)"); else print_generic_expr (file, vr->min, 0); @@ -2422,6 +2868,9 @@ dump_value_range (FILE *file, value_range_t *vr) if (INTEGRAL_TYPE_P (type) && vr->max == TYPE_MAX_VALUE (type)) fprintf (file, "+INF"); + else if (needs_overflow_infinity (type) + && is_positive_overflow_infinity (vr->max)) + fprintf (file, "+INF(OVF)"); else print_generic_expr (file, vr->max, 0); @@ -3871,15 +4320,18 @@ vrp_visit_assignment (tree stmt, tree *output_p) /* Compare all the value ranges for names equivalent to VAR with VAL using comparison code COMP. Return the same value returned by - compare_range_with_value. */ + compare_range_with_value, including the setting of + *STRICT_OVERFLOW_P. */ static tree -compare_name_with_value (enum tree_code comp, tree var, tree val) +compare_name_with_value (enum tree_code comp, tree var, tree val, + bool *strict_overflow_p) { bitmap_iterator bi; unsigned i; bitmap e; tree retval, t; + int used_strict_overflow; t = retval = NULL_TREE; @@ -3891,8 +4343,14 @@ compare_name_with_value (enum tree_code comp, tree var, tree val) the body of the loop just to check VAR's value range). */ bitmap_set_bit (e, SSA_NAME_VERSION (var)); + /* Start at -1. Set it to 0 if we do a comparison without relying + on overflow, or 1 if all comparisons rely on overflow. */ + used_strict_overflow = -1; + EXECUTE_IF_SET_IN_BITMAP (e, 0, i, bi) { + bool sop; + value_range_t equiv_vr = *(vr_value[i]); /* If name N_i does not have a valid range, use N_i as its own @@ -3905,7 +4363,8 @@ compare_name_with_value (enum tree_code comp, tree var, tree val) equiv_vr.max = ssa_name (i); } - t = compare_range_with_value (comp, &equiv_vr, val); + sop = false; + t = compare_range_with_value (comp, &equiv_vr, val, &sop); if (t) { /* If we get different answers from different members @@ -3919,6 +4378,11 @@ compare_name_with_value (enum tree_code comp, tree var, tree val) break; } retval = t; + + if (!sop) + used_strict_overflow = 0; + else if (used_strict_overflow < 0) + used_strict_overflow = 1; } } @@ -3926,7 +4390,11 @@ compare_name_with_value (enum tree_code comp, tree var, tree val) bitmap_clear_bit (e, SSA_NAME_VERSION (var)); if (retval) - return retval; + { + if (used_strict_overflow > 0) + *strict_overflow_p = true; + return retval; + } /* We couldn't find a non-NULL value for the predicate. */ return NULL_TREE; @@ -3936,15 +4404,19 @@ compare_name_with_value (enum tree_code comp, tree var, tree val) /* Given a comparison code COMP and names N1 and N2, compare all the ranges equivalent to N1 against all the ranges equivalent to N2 to determine the value of N1 COMP N2. Return the same value - returned by compare_ranges. */ + returned by compare_ranges. Set *STRICT_OVERFLOW_P to indicate + whether we relied on an overflow infinity in the comparison. */ + static tree -compare_names (enum tree_code comp, tree n1, tree n2) +compare_names (enum tree_code comp, tree n1, tree n2, + bool *strict_overflow_p) { tree t, retval; bitmap e1, e2; bitmap_iterator bi1, bi2; unsigned i1, i2; + int used_strict_overflow; /* Compare the ranges of every name equivalent to N1 against the ranges of every name equivalent to N2. */ @@ -3969,6 +4441,10 @@ compare_names (enum tree_code comp, tree n1, tree n2) : boolean_false_node; } + /* Start at -1. Set it to 0 if we do a comparison without relying + on overflow, or 1 if all comparisons rely on overflow. */ + used_strict_overflow = -1; + /* Otherwise, compare all the equivalent ranges. First, add N1 and N2 to their own set of equivalences to avoid duplicating the body of the loop just to check N1 and N2 ranges. */ @@ -3987,6 +4463,8 @@ compare_names (enum tree_code comp, tree n1, tree n2) t = retval = NULL_TREE; EXECUTE_IF_SET_IN_BITMAP (e2, 0, i2, bi2) { + bool sop; + value_range_t vr2 = *(vr_value[i2]); if (vr2.type == VR_VARYING || vr2.type == VR_UNDEFINED) @@ -3996,7 +4474,7 @@ compare_names (enum tree_code comp, tree n1, tree n2) vr2.max = ssa_name (i2); } - t = compare_ranges (comp, &vr1, &vr2); + t = compare_ranges (comp, &vr1, &vr2, &sop); if (t) { /* If we get different answers from different members @@ -4011,6 +4489,11 @@ compare_names (enum tree_code comp, tree n1, tree n2) return NULL_TREE; } retval = t; + + if (!sop) + used_strict_overflow = 0; + else if (used_strict_overflow < 0) + used_strict_overflow = 1; } } @@ -4018,6 +4501,8 @@ compare_names (enum tree_code comp, tree n1, tree n2) { bitmap_clear_bit (e1, SSA_NAME_VERSION (n1)); bitmap_clear_bit (e2, SSA_NAME_VERSION (n2)); + if (used_strict_overflow > 0) + *strict_overflow_p = true; return retval; } } @@ -4039,10 +4524,13 @@ compare_names (enum tree_code comp, tree n1, tree n2) If USE_EQUIV_P is true, the ranges of all the names equivalent with the operands in COND are used when trying to compute its value. This is only used during final substitution. During propagation, - we only check the range of each variable and not its equivalents. */ + we only check the range of each variable and not its equivalents. + + Set *STRICT_OVERFLOW_P to indicate whether we relied on an overflow + infinity to produce the result. */ tree -vrp_evaluate_conditional (tree cond, bool use_equiv_p) +vrp_evaluate_conditional (tree cond, bool use_equiv_p, bool *strict_overflow_p) { gcc_assert (TREE_CODE (cond) == SSA_NAME || TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison); @@ -4053,11 +4541,13 @@ vrp_evaluate_conditional (tree cond, bool use_equiv_p) tree retval; if (use_equiv_p) - retval = compare_name_with_value (NE_EXPR, cond, boolean_false_node); + retval = compare_name_with_value (NE_EXPR, cond, boolean_false_node, + strict_overflow_p); else { value_range_t *vr = get_value_range (cond); - retval = compare_range_with_value (NE_EXPR, vr, boolean_false_node); + retval = compare_range_with_value (NE_EXPR, vr, boolean_false_node, + strict_overflow_p); } /* If COND has a known boolean range, return it. */ @@ -4083,12 +4573,15 @@ vrp_evaluate_conditional (tree cond, bool use_equiv_p) if (use_equiv_p) { if (TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME) - return compare_names (TREE_CODE (cond), op0, op1); + return compare_names (TREE_CODE (cond), op0, op1, + strict_overflow_p); else if (TREE_CODE (op0) == SSA_NAME) - return compare_name_with_value (TREE_CODE (cond), op0, op1); + return compare_name_with_value (TREE_CODE (cond), op0, op1, + strict_overflow_p); else if (TREE_CODE (op1) == SSA_NAME) - return compare_name_with_value ( - swap_tree_comparison (TREE_CODE (cond)), op1, op0); + return (compare_name_with_value + (swap_tree_comparison (TREE_CODE (cond)), op1, op0, + strict_overflow_p)); } else { @@ -4098,12 +4591,15 @@ vrp_evaluate_conditional (tree cond, bool use_equiv_p) vr1 = (TREE_CODE (op1) == SSA_NAME) ? get_value_range (op1) : NULL; if (vr0 && vr1) - return compare_ranges (TREE_CODE (cond), vr0, vr1); + return compare_ranges (TREE_CODE (cond), vr0, vr1, + strict_overflow_p); else if (vr0 && vr1 == NULL) - return compare_range_with_value (TREE_CODE (cond), vr0, op1); + return compare_range_with_value (TREE_CODE (cond), vr0, op1, + strict_overflow_p); else if (vr0 == NULL && vr1) - return compare_range_with_value ( - swap_tree_comparison (TREE_CODE (cond)), vr1, op0); + return (compare_range_with_value + (swap_tree_comparison (TREE_CODE (cond)), vr1, op0, + strict_overflow_p)); } } @@ -4121,6 +4617,7 @@ static enum ssa_prop_result vrp_visit_cond_stmt (tree stmt, edge *taken_edge_p) { tree cond, val; + bool sop; *taken_edge_p = NULL; @@ -4193,9 +4690,21 @@ vrp_visit_cond_stmt (tree stmt, edge *taken_edge_p) additional checking. Testing on several code bases (GCC, DLV, MICO, TRAMP3D and SPEC2000) showed that doing this results in 4 more predicates folded in SPEC. */ - val = vrp_evaluate_conditional (cond, false); + sop = false; + val = vrp_evaluate_conditional (cond, false, &sop); if (val) - *taken_edge_p = find_taken_edge (bb_for_stmt (stmt), val); + { + if (!sop) + *taken_edge_p = find_taken_edge (bb_for_stmt (stmt), val); + else + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, + "\nIgnoring predicate evaluation because " + "it assumes that signed overflow is undefined"); + val = NULL_TREE; + } + } if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -4487,18 +4996,42 @@ vrp_visit_phi_node (tree phi) other case to avoid infinite bouncing between different minimums. */ if (cmp_min > 0 || cmp_min < 0) - vr_result.min = TYPE_MIN_VALUE (TREE_TYPE (vr_result.min)); + { + /* If we will end up with a (-INF, +INF) range, set it + to VARYING. */ + if (is_positive_overflow_infinity (vr_result.max) + || (vr_result.max + == TYPE_MAX_VALUE (TREE_TYPE (vr_result.max)))) + goto varying; + + if (!needs_overflow_infinity (TREE_TYPE (vr_result.min))) + vr_result.min = TYPE_MIN_VALUE (TREE_TYPE (vr_result.min)); + else if (supports_overflow_infinity (TREE_TYPE (vr_result.min))) + vr_result.min = + negative_overflow_infinity (TREE_TYPE (vr_result.min)); + else + goto varying; + } /* Similarly, if the new maximum is smaller or larger than the previous one, go all the way to +INF. */ if (cmp_max < 0 || cmp_max > 0) - vr_result.max = TYPE_MAX_VALUE (TREE_TYPE (vr_result.max)); - - /* If we ended up with a (-INF, +INF) range, set it to - VARYING. */ - if (vr_result.min == TYPE_MIN_VALUE (TREE_TYPE (vr_result.min)) - && vr_result.max == TYPE_MAX_VALUE (TREE_TYPE (vr_result.max))) - goto varying; + { + /* If we will end up with a (-INF, +INF) range, set it + to VARYING. */ + if (is_negative_overflow_infinity (vr_result.min) + || (vr_result.min + == TYPE_MIN_VALUE (TREE_TYPE (vr_result.min)))) + goto varying; + + if (!needs_overflow_infinity (TREE_TYPE (vr_result.max))) + vr_result.max = TYPE_MAX_VALUE (TREE_TYPE (vr_result.max)); + else if (supports_overflow_infinity (TREE_TYPE (vr_result.max))) + vr_result.max = + positive_overflow_infinity (TREE_TYPE (vr_result.max)); + else + goto varying; + } } } @@ -4533,7 +5066,9 @@ simplify_div_or_mod_using_ranges (tree stmt, tree rhs, enum tree_code rhs_code) } else { - val = compare_range_with_value (GT_EXPR, vr, integer_zero_node); + bool sop = false; + + val = compare_range_with_value (GT_EXPR, vr, integer_zero_node, &sop); } if (val && integer_onep (val)) @@ -4578,10 +5113,14 @@ simplify_abs_using_ranges (tree stmt, tree rhs) } else if (vr) { - val = compare_range_with_value (LE_EXPR, vr, integer_zero_node); + bool sop = false; + + val = compare_range_with_value (LE_EXPR, vr, integer_zero_node, &sop); if (!val) { - val = compare_range_with_value (GE_EXPR, vr, integer_zero_node); + sop = false; + val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, + &sop); if (val) { @@ -4625,10 +5164,12 @@ test_for_singularity (enum tree_code cond_code, tree op0, the conditional as it was written. */ if (cond_code == LE_EXPR || cond_code == LT_EXPR) { + /* This should not be negative infinity; there is no overflow + here. */ min = TYPE_MIN_VALUE (TREE_TYPE (op0)); max = op1; - if (cond_code == LT_EXPR) + if (cond_code == LT_EXPR && !is_overflow_infinity (max)) { tree one = build_int_cst (TREE_TYPE (op0), 1); max = fold_build2 (MINUS_EXPR, TREE_TYPE (op0), max, one); @@ -4636,10 +5177,12 @@ test_for_singularity (enum tree_code cond_code, tree op0, } else if (cond_code == GE_EXPR || cond_code == GT_EXPR) { + /* This should not be positive infinity; there is no overflow + here. */ max = TYPE_MAX_VALUE (TREE_TYPE (op0)); min = op1; - if (cond_code == GT_EXPR) + if (cond_code == GT_EXPR && !is_overflow_infinity (min)) { tree one = build_int_cst (TREE_TYPE (op0), 1); min = fold_build2 (PLUS_EXPR, TREE_TYPE (op0), min, one); @@ -4790,13 +5333,16 @@ static VEC(tree,heap) *stack; static tree simplify_stmt_for_jump_threading (tree stmt) { + bool sop; + /* We only use VRP information to simplify conditionals. This is overly conservative, but it's unclear if doing more would be worth the compile time cost. */ if (TREE_CODE (stmt) != COND_EXPR) return NULL; - return vrp_evaluate_conditional (COND_EXPR_COND (stmt), true); + sop = false; + return vrp_evaluate_conditional (COND_EXPR_COND (stmt), true, &sop); } /* Blocks which have more than one predecessor and more than |