* PATCH RFC: Use explicit representation of infinity in VRP
@ 2007-02-27 16:59 Ian Lance Taylor
2007-03-01 22:32 ` Diego Novillo
2007-03-02 20:10 ` Ian Lance Taylor
0 siblings, 2 replies; 11+ messages in thread
From: Ian Lance Taylor @ 2007-02-27 16:59 UTC (permalink / raw)
To: gcc-patches; +Cc: dnovillo
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 */
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: PATCH RFC: Use explicit representation of infinity in VRP
2007-02-27 16:59 PATCH RFC: Use explicit representation of infinity in VRP Ian Lance Taylor
@ 2007-03-01 22:32 ` Diego Novillo
2007-03-02 2:46 ` Ian Lance Taylor
2007-03-02 20:10 ` Ian Lance Taylor
1 sibling, 1 reply; 11+ messages in thread
From: Diego Novillo @ 2007-03-01 22:32 UTC (permalink / raw)
To: Ian Lance Taylor; +Cc: gcc-patches
Ian Lance Taylor wrote on 02/27/07 10:50:
> +/* 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
s/consteants/constants/
> @@ -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)))
I'm confused. If uses_overflow_infinity (TYPE) is true, why would support_overflow_infinity (TYPE) be false? (I'm going by the names of the
predicates, it may be an indication that they need to be renamed).
> + 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. */
> +
Sorry, I don't follow this one. You mean when the type does not have an
infinity value? Show me an example of this?
> @@ -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);
Here in dump_value_range we should distinguish INF from INF(OVF) (or some
other overflow indicator).
> + {
> + /* 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;
> + }
> }
Any compile time effects of this? Changing the probability of getting
VARYING values sometimes has a significant effect on simulation times.
> @@ -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);
I guess you plan to use this in the follow up patch?
I find it a bit unfortunate that we have to munge up an optimization so much just
to get better diagnostics. It's a slippery slope similar to the one we have
with -Wuninitialized. I would love to see all the warning machinery use a
totally separate and optimization-independent mechanism. But I realize that
we are not quite there yet, so I don't have a problem with this idea.
Test cases coming in with the actual warning patch, right?
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: PATCH RFC: Use explicit representation of infinity in VRP
2007-03-01 22:32 ` Diego Novillo
@ 2007-03-02 2:46 ` Ian Lance Taylor
2007-03-02 14:42 ` Diego Novillo
0 siblings, 1 reply; 11+ messages in thread
From: Ian Lance Taylor @ 2007-03-02 2:46 UTC (permalink / raw)
To: Diego Novillo; +Cc: gcc-patches
Diego Novillo <dnovillo@redhat.com> writes:
> Ian Lance Taylor wrote on 02/27/07 10:50:
>
> > +/* 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
>
> s/consteants/constants/
Thanks, fixed.
> > @@ -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)))
>
> I'm confused. If uses_overflow_infinity (TYPE) is true, why would
> support_overflow_infinity (TYPE) be false? (I'm going by the names of
> the predicates, it may be an indication that they need to be renamed).
Hmmm. The code is correct. uses_overflow_infinity means that TYPE is
an integer type which not wrap on overflow. It returns true if we
want to use a special infinity to indicate that we've overflowed.
supports_overflow_infinity means that our particular representation of
overflow works for TYPE. This is false for types for which
TYPE_{MIN,MAX}_VALUE is not a constant. The problem is that we use
TREE_OVERFLOW to indicate an overflow, and that flag only exists for
constants. So it is perfectly possible, even normal, to have types
which pass uses_overflow_infinity but not supports_overflow_infinity.
I originally used a more complex scheme with a hash table to handle
such types. However, they are unusual--in fact I believe they only
occur for Ada. So I have now opted for a simpler scheme in which we
just punt on signed overflow for that sort of type.
Any suggestions for better names for the two functions?
> > + 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. */
> > +
>
> Sorry, I don't follow this one. You mean when the type does not have
> an infinity value? Show me an example of this?
The problem is that we can only use our overflow indicator when one of
the bounds is INF. If neither bound is INF, then we have no way to
indicate that the result depends on the assumption that signed
overflow does not occur. So in that (unusual) case, we punt.
In this case we could track this reliably by adding a new field to
value_range_t. I opted against that because of the increased
complexity and the fact that it rarely matters in practice.
> > @@ -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);
>
> Here in dump_value_range we should distinguish INF from INF(OVF) (or some
> other overflow indicator).
Fixed.
> Any compile time effects of this? Changing the probability of getting
> VARYING values sometimes has a significant effect on simulation times.
No major compile time impact. The patched code does seem to run
faster on 20001226-1.c.
> > @@ -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);
>
> I guess you plan to use this in the follow up patch?
Yes.
> I find it a bit unfortunate that we have to munge up an optimization so much just
> to get better diagnostics. It's a slippery slope similar to the one we have
> with -Wuninitialized. I would love to see all the warning machinery use a
> totally separate and optimization-independent mechanism. But I realize that
> we are not quite there yet, so I don't have a problem with this idea.
Yes, it is a very tricky issue with warnings like -Wstrict-overflow
which are intended to warn about undefined behaviour. It's hard to
detect undefined behaviour. But I believe it's very important to warn
about cases where the compiler relies on the definition of undefined
behaviour, because otherwise our users, who do not in general
understand the language standard completely, start to disable
optimizations. As you may recall, this entire series of patches was
started in response to Paul Eggert's proposal to always compile with
-fwrapv. The only way to head that off is to insert warnings. And to
only way to make this sort of warning meaningful is to make it
dependent on the optimizers.
I agree that as a general rule our warnings should not depend on our
optimizations. And -Wuninitialized and -Wreturn-type should probably
change to be optimization independent. But for cases like
-Wstrict-overflow I believe that is impossible.
> Test cases coming in with the actual warning patch, right?
Yes. No test cases with this patch because there is no visible change
in functionality. In particular, all the existing VRP tests pass.
Ian
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: PATCH RFC: Use explicit representation of infinity in VRP
2007-03-02 2:46 ` Ian Lance Taylor
@ 2007-03-02 14:42 ` Diego Novillo
2007-03-02 15:14 ` Ian Lance Taylor
0 siblings, 1 reply; 11+ messages in thread
From: Diego Novillo @ 2007-03-02 14:42 UTC (permalink / raw)
To: Ian Lance Taylor; +Cc: gcc-patches
Ian Lance Taylor wrote on 03/01/07 21:43:
> Hmmm. The code is correct. uses_overflow_infinity means that TYPE is
> an integer type which not wrap on overflow. It returns true if we
> want to use a special infinity to indicate that we've overflowed.
> supports_overflow_infinity means that our particular representation of
> overflow works for TYPE. This is false for types for which
> TYPE_{MIN,MAX}_VALUE is not a constant. The problem is that we use
> TREE_OVERFLOW to indicate an overflow, and that flag only exists for
> constants. So it is perfectly possible, even normal, to have types
> which pass uses_overflow_infinity but not supports_overflow_infinity.
>
> I originally used a more complex scheme with a hash table to handle
> such types. However, they are unusual--in fact I believe they only
> occur for Ada. So I have now opted for a simpler scheme in which we
> just punt on signed overflow for that sort of type.
>
> Any suggestions for better names for the two functions?
How about changing uses_overflow_infinity to wraps_on_overflow_p? The
predicate has a different sign, so all the references to
uses_overflow_infinity would have to be changed to !wraps_on_overflow_p
But I'm not too attached to the name. I can learn to distinguish the
other too.
> The problem is that we can only use our overflow indicator when one of
> the bounds is INF. If neither bound is INF, then we have no way to
> indicate that the result depends on the assumption that signed
> overflow does not occur. So in that (unusual) case, we punt.
Ah, yes. Thanks.
> I agree that as a general rule our warnings should not depend on our
> optimizations. And -Wuninitialized and -Wreturn-type should probably
> change to be optimization independent. But for cases like
> -Wstrict-overflow I believe that is impossible.
Yes, in this case it would be pointless as well. The warning is only
meant to trigger when the compiler makes assumptions when optimizing,
after all.
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: PATCH RFC: Use explicit representation of infinity in VRP
2007-03-02 14:42 ` Diego Novillo
@ 2007-03-02 15:14 ` Ian Lance Taylor
2007-03-02 15:22 ` Diego Novillo
0 siblings, 1 reply; 11+ messages in thread
From: Ian Lance Taylor @ 2007-03-02 15:14 UTC (permalink / raw)
To: Diego Novillo; +Cc: gcc-patches
Diego Novillo <dnovillo@redhat.com> writes:
> Ian Lance Taylor wrote on 03/01/07 21:43:
>
> > Hmmm. The code is correct. uses_overflow_infinity means that TYPE is
> > an integer type which not wrap on overflow. It returns true if we
> > want to use a special infinity to indicate that we've overflowed.
> > supports_overflow_infinity means that our particular representation of
> > overflow works for TYPE. This is false for types for which
> > TYPE_{MIN,MAX}_VALUE is not a constant. The problem is that we use
> > TREE_OVERFLOW to indicate an overflow, and that flag only exists for
> > constants. So it is perfectly possible, even normal, to have types
> > which pass uses_overflow_infinity but not supports_overflow_infinity.
> > I originally used a more complex scheme with a hash table to handle
> > such types. However, they are unusual--in fact I believe they only
> > occur for Ada. So I have now opted for a simpler scheme in which we
> > just punt on signed overflow for that sort of type.
> > Any suggestions for better names for the two functions?
>
> How about changing uses_overflow_infinity to wraps_on_overflow_p? The
> predicate has a different sign, so all the references to
> uses_overflow_infinity would have to be changed to !wraps_on_overflow_p
No, wraps_on_overflow_p isn't right. Floating point types don't wrap
on overflow, but we don't want to use a special overflow indication
for them, since they already have one. To reverse the sense of
uses_overflow_infinity we would need to test for "not an integral
type" || "wraps on overflow". I don't see an easy name for that.
How about simply needs_overflow_infinity?
Ian
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: PATCH RFC: Use explicit representation of infinity in VRP
2007-03-02 15:14 ` Ian Lance Taylor
@ 2007-03-02 15:22 ` Diego Novillo
0 siblings, 0 replies; 11+ messages in thread
From: Diego Novillo @ 2007-03-02 15:22 UTC (permalink / raw)
To: Ian Lance Taylor; +Cc: gcc-patches
Ian Lance Taylor wrote on 03/02/07 10:14:
> No, wraps_on_overflow_p isn't right. Floating point types don't wrap
> on overflow, but we don't want to use a special overflow indication
> for them, since they already have one. To reverse the sense of
> uses_overflow_infinity we would need to test for "not an integral
> type" || "wraps on overflow". I don't see an easy name for that.
Gah, you're right.
> How about simply needs_overflow_infinity?
Sure.
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: PATCH RFC: Use explicit representation of infinity in VRP
2007-02-27 16:59 PATCH RFC: Use explicit representation of infinity in VRP Ian Lance Taylor
2007-03-01 22:32 ` Diego Novillo
@ 2007-03-02 20:10 ` Ian Lance Taylor
2007-03-11 13:42 ` Richard Guenther
1 sibling, 1 reply; 11+ messages in thread
From: Ian Lance Taylor @ 2007-03-02 20:10 UTC (permalink / raw)
To: gcc-patches; +Cc: dnovillo
Ian Lance Taylor <iant@google.com> writes:
> 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.
Committed as follows.
Ian
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.
Index: gcc/tree-vrp.c
===================================================================
--- gcc/tree-vrp.c (revision 122486)
+++ 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
+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
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 (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
&& ((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
/* 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 (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
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_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 (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_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 (!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_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 (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_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 (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_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;
@@ -2414,6 +2857,9 @@ dump_value_range (FILE *file, value_rang
&& !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_rang
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 *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 +4343,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 +4363,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 +4378,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 +4390,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 +4404,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 +4441,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 +4463,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 +4474,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 +4489,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 +4501,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 +4524,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 +4541,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 +4573,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 +4591,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 +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 *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 +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 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 +5113,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 +5164,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 +5177,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 +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
Index: gcc/tree-ssa-propagate.c
===================================================================
--- gcc/tree-ssa-propagate.c (revision 122486)
+++ 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 122486)
+++ 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 */
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: PATCH RFC: Use explicit representation of infinity in VRP
2007-03-02 20:10 ` Ian Lance Taylor
@ 2007-03-11 13:42 ` Richard Guenther
2007-03-11 16:48 ` Ian Lance Taylor
0 siblings, 1 reply; 11+ messages in thread
From: Richard Guenther @ 2007-03-11 13:42 UTC (permalink / raw)
To: Ian Lance Taylor; +Cc: gcc-patches, dnovillo
On 02 Mar 2007 12:09:43 -0800, Ian Lance Taylor <iant@google.com> wrote:
> Ian Lance Taylor <iant@google.com> writes:
>
> > 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.
>
> Committed as follows.
This patch causes optimization regressions because it preserves "overflow"
even if -fstrict-overflow is in effect or -Wstrict-overflow is not in effect.
See PR31130. I believe needs_overflow_infinity () should return false
for -fstrict-overflow.
Richard.
> Ian
>
>
> 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.
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: PATCH RFC: Use explicit representation of infinity in VRP
2007-03-11 13:42 ` Richard Guenther
@ 2007-03-11 16:48 ` Ian Lance Taylor
2007-03-11 17:26 ` Richard Guenther
0 siblings, 1 reply; 11+ messages in thread
From: Ian Lance Taylor @ 2007-03-11 16:48 UTC (permalink / raw)
To: Richard Guenther; +Cc: gcc-patches, dnovillo
"Richard Guenther" <richard.guenther@gmail.com> writes:
> On 02 Mar 2007 12:09:43 -0800, Ian Lance Taylor <iant@google.com> wrote:
> > Ian Lance Taylor <iant@google.com> writes:
> >
> > > 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.
> >
> > Committed as follows.
>
> This patch causes optimization regressions because it preserves "overflow"
> even if -fstrict-overflow is in effect or -Wstrict-overflow is not in effect.
> See PR31130. I believe needs_overflow_infinity () should return false
> for -fstrict-overflow.
That would not be the right fix. It would cause -Wstrict-overflow to
become ineffective for VRP, which would put us right back where we
were when I started the whole series of patches: user code would act
in unexpected ways with no warning. And simply adding
-Wstrict-overflow should not, of course, change code generation.
I know that some people are uneasy with the whole idea of this series
of patches. But the fact is, real users were prepared to turn on
-fwrapv for all code which uses autoconf, which is a good fraction of
uses of gcc. I think that my patch does considerably less harm than
that. I am always open to other suggestions, and I have asked for
them consistently during this series of patches.
I can actually produce a number of test cases in which VRP now acts
differently but the optimization in question happens anyhow. It would
be more interesting to find cases where the optimization no longer
happens.
That said, for this test case, we may be able to turn NEGATE_EXPR of
[-INF, X] into [-X, INF] rather than [-X, INF(OVF)].
Ian
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: PATCH RFC: Use explicit representation of infinity in VRP
2007-03-11 16:48 ` Ian Lance Taylor
@ 2007-03-11 17:26 ` Richard Guenther
2007-03-11 21:33 ` Ian Lance Taylor
0 siblings, 1 reply; 11+ messages in thread
From: Richard Guenther @ 2007-03-11 17:26 UTC (permalink / raw)
To: Ian Lance Taylor; +Cc: gcc-patches, dnovillo
On 11 Mar 2007 09:12:01 -0700, Ian Lance Taylor <iant@google.com> wrote:
> "Richard Guenther" <richard.guenther@gmail.com> writes:
>
> > On 02 Mar 2007 12:09:43 -0800, Ian Lance Taylor <iant@google.com> wrote:
> > > Ian Lance Taylor <iant@google.com> writes:
> > >
> > > > 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.
> > >
> > > Committed as follows.
> >
> > This patch causes optimization regressions because it preserves "overflow"
> > even if -fstrict-overflow is in effect or -Wstrict-overflow is not in effect.
> > See PR31130. I believe needs_overflow_infinity () should return false
> > for -fstrict-overflow.
>
> That would not be the right fix. It would cause -Wstrict-overflow to
> become ineffective for VRP, which would put us right back where we
> were when I started the whole series of patches: user code would act
> in unexpected ways with no warning. And simply adding
> -Wstrict-overflow should not, of course, change code generation.
>
> I know that some people are uneasy with the whole idea of this series
> of patches. But the fact is, real users were prepared to turn on
> -fwrapv for all code which uses autoconf, which is a good fraction of
> uses of gcc. I think that my patch does considerably less harm than
> that. I am always open to other suggestions, and I have asked for
> them consistently during this series of patches.
I don't want to re-start all the discussion, but I still believe that those
(few) people will still be unhappy that the "optimizations in question
happen anyhow". So my opinion is that we made gcc worse for the
sake of a few people that were loudly complaining and probably
still will turn on -fwrapv.
I do believe that -Wstrict-overflow is a good addition, but I didn't expect
the addition of a warning possibilty to affect the set of optimizations done.
That sounds as backward as generating different code of -Wstrict-overflow
is in effect.
Richard.
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: PATCH RFC: Use explicit representation of infinity in VRP
2007-03-11 17:26 ` Richard Guenther
@ 2007-03-11 21:33 ` Ian Lance Taylor
0 siblings, 0 replies; 11+ messages in thread
From: Ian Lance Taylor @ 2007-03-11 21:33 UTC (permalink / raw)
To: Richard Guenther; +Cc: gcc-patches, dnovillo
"Richard Guenther" <richard.guenther@gmail.com> writes:
> I do believe that -Wstrict-overflow is a good addition, but I didn't expect
> the addition of a warning possibilty to affect the set of optimizations done.
> That sounds as backward as generating different code of -Wstrict-overflow
> is in effect.
I agree that it is backward. The problem is that of keeping track of
when gcc relies on signed overflow. It is possible to make the patch
more invasive in order to keep better track.
In the approach I chose, I considered two things besides keeping the
patch as simple as I could. The first was that I could not find any
cases where an optimization actually did not occur: certainly VRP's
behaviour changed, but in my testing the changes were consistently
covered by other optimizations, and always led to only inconsequential
changes in the generated code. The second was that I believed that
the only cases in which optimization behaviour changed were cases were
gcc was relying on undefined signed overflow anyhow, and were
therefore cases of less interest.
You have found a counterexample to the second case. I'm going to look
into whether it is possible to handle that counterexample without
significantly changing the current structure of the code.
Ian
^ permalink raw reply [flat|nested] 11+ messages in thread
end of thread, other threads:[~2007-03-11 19:42 UTC | newest]
Thread overview: 11+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2007-02-27 16:59 PATCH RFC: Use explicit representation of infinity in VRP Ian Lance Taylor
2007-03-01 22:32 ` Diego Novillo
2007-03-02 2:46 ` Ian Lance Taylor
2007-03-02 14:42 ` Diego Novillo
2007-03-02 15:14 ` Ian Lance Taylor
2007-03-02 15:22 ` Diego Novillo
2007-03-02 20:10 ` Ian Lance Taylor
2007-03-11 13:42 ` Richard Guenther
2007-03-11 16:48 ` Ian Lance Taylor
2007-03-11 17:26 ` Richard Guenther
2007-03-11 21:33 ` Ian Lance Taylor
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).