This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
PATCH RFC: Use explicit representation of infinity in VRP
- From: Ian Lance Taylor <iant at google dot com>
- To: gcc-patches at gcc dot gnu dot org
- Cc: dnovillo at redhat dot com
- Date: 27 Feb 2007 07:50:35 -0800
- Subject: PATCH RFC: Use explicit representation of infinity in VRP
This patch is a lengthy prelude to adding full support for
-fstrict-overflow and -Wstrict-overflow to tree-vrp.c. It changes VRP
to use an explicit representation of signed infinity when there is a
signed overflow. Fortunately most of the changes are fairly
mechanical, though some attention must be paid to arithmetic on
infinities. This patch changes several of the functions to indicate
whether they relied on the assumption that signed overflow does not
occur; these indications are only used in a couple of places. They
will be used more extensively in a follow-on patch to add support for
-Wstrict-overflow to VRP (hopefully the last of the signed overflow
patches for mainline).
This patch changes VRP handling of signed overflow in several subtle
ways, and in a couple of blatant ways. Changes to compare_values meen
that vrp_meet will now merge ranges which include an overflowed value
(e.g., [0, INF] meets [0, INF]). Previously vrp_meet would flush
overflowed ranges to VARYING. More seriously, vrp_visit_cond_stmt
will now discard results which are based on the assumption that signed
overflow does not occur. This is because there is no clean way to
record whether that information is used in a subsequent optimization,
and thus no clean way to handle -Wstrict-overflow.
To evaluate the effects of these changes, I compiled the cc1-i files
with -O2 with and without the patch and compared the resulting
assembly files. Four files changed. None of the changes had any
performance impact; they were just rearrangements of code and of data
layout on the stack. I believe that in practice the change to
vrp_visit_cond_stmt is being hidden by the fact that fold_predicate_in
in tree-ssa-propagate.c will still rely on the assumption that signed
overflow does not occur when simplifying a COND_EXPR. (A later patch
will add support for -Wstrict-overflow to that function.)
I would like to hear comments on this patch and this general approach.
Ian
2007-02-27 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.
Index: gcc/tree-vrp.c
===================================================================
--- gcc/tree-vrp.c (revision 122188)
+++ gcc/tree-vrp.c (working copy)
@@ -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
+uses_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 consteants. 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 (uses_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 (uses_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 (uses_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 (uses_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
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, val
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 *
}
-/* 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)));
+}
+
+/* Like tree_expr_nonnegative_warnv_p, but this function uses value
+ ranges obtained so far. */
- /* FIXME: May need to record overflow information here. */
- return tree_expr_nonnegative_warnv_p (expr, &ovf);
+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
/* 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
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
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
|| 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 (uses_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
&& ((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 (uses_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
/* 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
}
}
- 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
int sgn1 = tree_int_cst_sgn (val1);
int sgn2 = tree_int_cst_sgn (val2);
+ if (uses_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
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 (uses_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 (uses_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_ra
&& 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_ra
{
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_ra
}
/* 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;
+ }
+
+ 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;
+ }
+
+ 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[1] = (vr1.max != vr1.min)
- ? vrp_int_const_binop (code, vr0.min, vr1.max)
- : NULL_TREE;
-
- val[2] = (vr0.max != vr0.min)
- ? vrp_int_const_binop (code, vr0.max, vr1.min)
- : NULL_TREE;
-
- 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_ra
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_ra
{
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_ra
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_ran
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_ran
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_ran
&& !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 (uses_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 (uses_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_ran
/* 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 (!uses_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 (!uses_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_ran
{
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_ran
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_ran
anti-range. */
vr0.type = VR_RANGE;
min = build_int_cst (TREE_TYPE (expr), 0);
- max = TYPE_MAX_VALUE (TREE_TYPE (expr));
+ if (uses_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_ran
/* 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 (uses_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_rang
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 *
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 *v
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 *v
- 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, val
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, val
{
/* 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, val
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, val
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, val
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
{
/* 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
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
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
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;
@@ -2412,7 +2855,9 @@ dump_value_range (FILE *file, value_rang
if (INTEGRAL_TYPE_P (type)
&& !TYPE_UNSIGNED (type)
- && vr->min == TYPE_MIN_VALUE (type))
+ && (uses_overflow_infinity (type)
+ ? is_negative_overflow_infinity (vr->min)
+ : vr->min == TYPE_MIN_VALUE (type)))
fprintf (file, "-INF");
else
print_generic_expr (file, vr->min, 0);
@@ -2420,7 +2865,9 @@ dump_value_range (FILE *file, value_rang
fprintf (file, ", ");
if (INTEGRAL_TYPE_P (type)
- && vr->max == TYPE_MAX_VALUE (type))
+ && (uses_overflow_infinity (type)
+ ? is_positive_overflow_infinity (vr->max)
+ : vr->max == TYPE_MAX_VALUE (type)))
fprintf (file, "+INF");
else
print_generic_expr (file, vr->max, 0);
@@ -3871,15 +4318,18 @@ vrp_visit_assignment (tree stmt, tree *o
/* 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 +4341,14 @@ compare_name_with_value (enum tree_code
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 +4361,8 @@ compare_name_with_value (enum tree_code
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 +4376,11 @@ compare_name_with_value (enum tree_code
break;
}
retval = t;
+
+ if (!sop)
+ used_strict_overflow = 0;
+ else if (used_strict_overflow < 0)
+ used_strict_overflow = 1;
}
}
@@ -3926,7 +4388,11 @@ compare_name_with_value (enum tree_code
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 +4402,19 @@ compare_name_with_value (enum tree_code
/* 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 +4439,10 @@ compare_names (enum tree_code comp, tree
: 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 +4461,8 @@ compare_names (enum tree_code comp, tree
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 +4472,7 @@ compare_names (enum tree_code comp, tree
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 +4487,11 @@ compare_names (enum tree_code comp, tree
return NULL_TREE;
}
retval = t;
+
+ if (!sop)
+ used_strict_overflow = 0;
+ else if (used_strict_overflow < 0)
+ used_strict_overflow = 1;
}
}
@@ -4018,6 +4499,8 @@ compare_names (enum tree_code comp, tree
{
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 +4522,13 @@ compare_names (enum tree_code comp, tree
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 +4539,13 @@ vrp_evaluate_conditional (tree cond, boo
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 +4571,15 @@ vrp_evaluate_conditional (tree cond, boo
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 +4589,15 @@ vrp_evaluate_conditional (tree cond, boo
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 +4615,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 +4688,21 @@ vrp_visit_cond_stmt (tree stmt, edge *ta
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 +4994,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 (!uses_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 (!uses_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 +5064,9 @@ simplify_div_or_mod_using_ranges (tree s
}
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 +5111,14 @@ simplify_abs_using_ranges (tree stmt, tr
}
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 +5162,12 @@ test_for_singularity (enum tree_code con
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 +5175,12 @@ test_for_singularity (enum tree_code con
}
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 +5331,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
Index: gcc/tree-ssa-propagate.c
===================================================================
--- gcc/tree-ssa-propagate.c (revision 122188)
+++ gcc/tree-ssa-propagate.c (working copy)
@@ -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)
Index: gcc/tree-flow.h
===================================================================
--- gcc/tree-flow.h (revision 122188)
+++ gcc/tree-flow.h (working copy)
@@ -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 */