This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH][RFC] Rework int_const_binop, fix PR30318, VRP not creating anti-ranges for overflowing +/-
- From: "Richard Guenther" <richard dot guenther at gmail dot com>
- To: "Gcc Patch List" <gcc-patches at gcc dot gnu dot org>
- Date: Sun, 7 Jan 2007 20:12:12 +0100
- Subject: [PATCH][RFC] Rework int_const_binop, fix PR30318, VRP not creating anti-ranges for overflowing +/-
This addresses PR30318 that is about VRP not creating anti-ranges out
of overflowing PLUS/MINUS_EXPR. Fixing this PR can possibly make removing
undefined signed overflow assumptions from VRP less harmful.
In order to do so this patch enhances certain parts of VRP to handle
anti-ranges better and canonicalizes certain anti-ranges back to ranges.
In the quest to tackle this PR I have started to re-work int_const_binop to
get rid of the vrp_int_const_binop wrapper in VRP. What this patch does is
expose the new proposed interface under a different name and not touch
the old one (to keep patch size down).
The new interface get's rid of the nearly unused "notrunc" argument
(and so always force_fits_type), adds a type argument and a second
output, a boolean whether the operation overflowed (regardless of
definedness or undefinedness). This avoids creating a new node just
to set the overflow flag and also allows tracking overflow for unsigned
types just as vrp_int_const_binop tried to do. A new force_fit_type_1
was added to allow tracking of unsigned overflow here.
We can implement both old interfaces, int_const_binop and force_fit_type
using the new helpers, but I didn't yet change those to keep the patch small.
Suggestions for a better name for int_const_binop_1 welcome ;)
Note that I will split out the fold-const.c parts into a separate patch
if the general idea is ok - I just included them with the VRP patch to
make the intended use visible.
Bootstrapped and tested on x86_64-unknown-linux-gnu.
Note this patch relies on wrapping types wrapping in two's complement
way. I have no idea how for example Ada types with range [1, 11] is
supposed to "wrap" -- with the patch we assume that adding 5 to a
range [10,10] will result in [15, 15] as it wraps according to TYPE_PRECISION,
not TYPE_MIN/MAX_VALUE. So this part of the VRP patch needs to
be guarded appropriately - I'm just wondering about the Ada semantics here.
Comments?
Thanks,
Richard.
2007-01-07 Richard Guenther <rguenther@suse.de>
PR tree-optimization/30318
* tree.h (int_const_binop_1): Export.
* fold-const.c (force_fit_type_1): New static function.
(int_const_binop_1): New function.
* tree-vrp.c (set_value_range): Canonicalize anti-ranges
to ranges where possible.
(extract_range_from_assert): Merge anti-ranges if possible.
(vrp_int_const_binop): Remove.
(extract_range_from_binary_expr): Separate MIN_EXPR and MAX_EXPR
cases, merge PLUS_EXPR and MINUS_EXPR cases. Handle cases
where PLUS_EXPR and MINUS_EXPR create an anti-range. Replace
uses of vrp_int_const_binop by int_const_binop_1.
(compare_range_with_value): Handle anti-range with no valid
value.
* gcc.dg/tree-ssa/vrp31.c: New testcase.
2007-01-07 Richard Guenther <rguenther@suse.de>
PR tree-optimization/30318
* tree.h (int_const_binop_1): Export.
* fold-const.c (force_fit_type_1): New static function.
(int_const_binop_1): New function.
* tree-vrp.c (set_value_range): Canonicalize anti-ranges
to ranges where possible.
(extract_range_from_assert): Merge anti-ranges if possible.
(vrp_int_const_binop): Remove.
(extract_range_from_binary_expr): Separate MIN_EXPR and MAX_EXPR
cases, merge PLUS_EXPR and MINUS_EXPR cases. Handle cases
where PLUS_EXPR and MINUS_EXPR create an anti-range. Replace
uses of vrp_int_const_binop by int_const_binop_1.
(compare_range_with_value): Handle anti-range with no valid
value.
* gcc.dg/tree-ssa/vrp31.c: New testcase.
Index: tree.h
===================================================================
*** tree.h (revision 120546)
--- tree.h (working copy)
*************** extern tree fold_unary_to_constant (enum
*** 4370,4375 ****
--- 4370,4376 ----
extern tree fold_binary_to_constant (enum tree_code, tree, tree, tree);
extern tree fold_read_from_constant_string (tree);
extern tree int_const_binop (enum tree_code, tree, tree, int);
+ extern tree int_const_binop_1 (enum tree_code, tree, tree, tree, bool*);
extern tree build_fold_addr_expr (tree);
extern tree fold_build_cleanup_point_expr (tree type, tree expr);
extern tree fold_strip_sign_ops (tree);
Index: fold-const.c
===================================================================
*** fold-const.c (revision 120546)
--- fold-const.c (working copy)
*************** force_fit_type (tree t, int overflowable
*** 293,298 ****
--- 293,374 ----
return t;
}
+
+ static tree
+ force_fit_type_1 (tree type, unsigned HOST_WIDE_INT low0, HOST_WIDE_INT high0,
+ bool *overflow_p)
+ {
+ unsigned HOST_WIDE_INT low = low0;
+ HOST_WIDE_INT high = high0;
+ unsigned int prec;
+ int sign_extended_type;
+ bool overflow = false;
+
+ if (POINTER_TYPE_P (type)
+ || TREE_CODE (type) == OFFSET_TYPE)
+ prec = POINTER_SIZE;
+ else
+ prec = TYPE_PRECISION (type);
+ /* Size types *are* sign extended. */
+ sign_extended_type = (!TYPE_UNSIGNED (type)
+ || (TREE_CODE (type) == INTEGER_TYPE
+ && TYPE_IS_SIZETYPE (type)));
+
+ /* First clear all bits that are beyond the type's precision. */
+
+ if (prec >= 2 * HOST_BITS_PER_WIDE_INT)
+ ;
+ else if (prec > HOST_BITS_PER_WIDE_INT)
+ {
+ overflow = (high & ((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT))) != 0;
+ high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
+ }
+ else
+ {
+ overflow = high != 0;
+ high = 0;
+ if (prec < HOST_BITS_PER_WIDE_INT)
+ {
+ overflow |= (low & ((HOST_WIDE_INT) (-1) << prec)) != 0;
+ low &= ~((HOST_WIDE_INT) (-1) << prec);
+ }
+ }
+
+ if (!sign_extended_type)
+ /* No sign extension */;
+ else if (prec >= 2 * HOST_BITS_PER_WIDE_INT)
+ /* Correct width already. */;
+ else if (prec > HOST_BITS_PER_WIDE_INT)
+ {
+ /* Sign extend top half? */
+ if (high & ((unsigned HOST_WIDE_INT)1
+ << (prec - HOST_BITS_PER_WIDE_INT - 1)))
+ high |= (HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT);
+ }
+ else if (prec == HOST_BITS_PER_WIDE_INT)
+ {
+ if ((HOST_WIDE_INT)low < 0)
+ high = -1;
+ }
+ else
+ {
+ /* Sign extend bottom half? */
+ if (low & ((unsigned HOST_WIDE_INT)1 << (prec - 1)))
+ {
+ high = -1;
+ low |= (HOST_WIDE_INT)(-1) << prec;
+ }
+ }
+
+ /* If the value didn't fit, set the overflow flag. */
+ if (overflow_p
+ && (low != low0 || high != high0)
+ && (overflow || sign_extended_type))
+ *overflow_p |= true;
+
+ return build_int_cst_wide (type, low, high);
+ }
+
/* Add two doubleword integers with doubleword result.
Return nonzero if the operation overflows according to UNSIGNED_P.
*************** int_binop_types_match_p (enum tree_code
*** 1419,1424 ****
--- 1495,1654 ----
}
+ tree
+ int_const_binop_1 (enum tree_code code, tree type, tree arg1, tree arg2,
+ bool *overflow_p)
+ {
+ unsigned HOST_WIDE_INT int1l, int2l;
+ HOST_WIDE_INT int1h, int2h;
+ unsigned HOST_WIDE_INT low;
+ HOST_WIDE_INT hi;
+ unsigned HOST_WIDE_INT garbagel;
+ HOST_WIDE_INT garbageh;
+ int uns = TYPE_UNSIGNED (type);
+ tree t;
+ int overflow = 0;
+
+ int1l = TREE_INT_CST_LOW (arg1);
+ int1h = TREE_INT_CST_HIGH (arg1);
+ int2l = TREE_INT_CST_LOW (arg2);
+ int2h = TREE_INT_CST_HIGH (arg2);
+
+ switch (code)
+ {
+ case BIT_IOR_EXPR:
+ low = int1l | int2l, hi = int1h | int2h;
+ break;
+
+ case BIT_XOR_EXPR:
+ low = int1l ^ int2l, hi = int1h ^ int2h;
+ break;
+
+ case BIT_AND_EXPR:
+ low = int1l & int2l, hi = int1h & int2h;
+ break;
+
+ case RSHIFT_EXPR:
+ int2l = -int2l;
+ case LSHIFT_EXPR:
+ /* It's unclear from the C standard whether shifts can overflow.
+ The following code ignores overflow; perhaps a C standard
+ interpretation ruling is needed. */
+ lshift_double (int1l, int1h, int2l, TYPE_PRECISION (type),
+ &low, &hi, !uns);
+ break;
+
+ case RROTATE_EXPR:
+ int2l = - int2l;
+ case LROTATE_EXPR:
+ lrotate_double (int1l, int1h, int2l, TYPE_PRECISION (type),
+ &low, &hi);
+ break;
+
+ case PLUS_EXPR:
+ overflow = add_double (int1l, int1h, int2l, int2h, &low, &hi);
+ break;
+
+ case MINUS_EXPR:
+ neg_double (int2l, int2h, &low, &hi);
+ add_double (int1l, int1h, low, hi, &low, &hi);
+ overflow = OVERFLOW_SUM_SIGN (hi, int2h, int1h);
+ break;
+
+ case MULT_EXPR:
+ overflow = mul_double (int1l, int1h, int2l, int2h, &low, &hi);
+ break;
+
+ case TRUNC_DIV_EXPR:
+ case FLOOR_DIV_EXPR: case CEIL_DIV_EXPR:
+ case EXACT_DIV_EXPR:
+ /* This is a shortcut for a common special case. */
+ if (int2h == 0 && (HOST_WIDE_INT) int2l > 0
+ && ! TREE_CONSTANT_OVERFLOW (arg1)
+ && ! TREE_CONSTANT_OVERFLOW (arg2)
+ && int1h == 0 && (HOST_WIDE_INT) int1l >= 0)
+ {
+ if (code == CEIL_DIV_EXPR)
+ int1l += int2l - 1;
+
+ low = int1l / int2l, hi = 0;
+ break;
+ }
+
+ /* ... fall through ... */
+
+ case ROUND_DIV_EXPR:
+ if (int2h == 0 && int2l == 0)
+ return NULL_TREE;
+ if (int2h == 0 && int2l == 1)
+ {
+ low = int1l, hi = int1h;
+ break;
+ }
+ if (int1l == int2l && int1h == int2h
+ && ! (int1l == 0 && int1h == 0))
+ {
+ low = 1, hi = 0;
+ break;
+ }
+ overflow = div_and_round_double (code, uns, int1l, int1h, int2l, int2h,
+ &low, &hi, &garbagel, &garbageh);
+ break;
+
+ case TRUNC_MOD_EXPR:
+ case FLOOR_MOD_EXPR: case CEIL_MOD_EXPR:
+ /* This is a shortcut for a common special case. */
+ if (int2h == 0 && (HOST_WIDE_INT) int2l > 0
+ && ! TREE_CONSTANT_OVERFLOW (arg1)
+ && ! TREE_CONSTANT_OVERFLOW (arg2)
+ && int1h == 0 && (HOST_WIDE_INT) int1l >= 0)
+ {
+ if (code == CEIL_MOD_EXPR)
+ int1l += int2l - 1;
+ low = int1l % int2l, hi = 0;
+ break;
+ }
+
+ /* ... fall through ... */
+
+ case ROUND_MOD_EXPR:
+ if (int2h == 0 && int2l == 0)
+ return NULL_TREE;
+ overflow = div_and_round_double (code, uns,
+ int1l, int1h, int2l, int2h,
+ &garbagel, &garbageh, &low, &hi);
+ break;
+
+ case MIN_EXPR:
+ case MAX_EXPR:
+ if (uns)
+ low = (((unsigned HOST_WIDE_INT) int1h
+ < (unsigned HOST_WIDE_INT) int2h)
+ || (((unsigned HOST_WIDE_INT) int1h
+ == (unsigned HOST_WIDE_INT) int2h)
+ && int1l < int2l));
+ else
+ low = (int1h < int2h
+ || (int1h == int2h && int1l < int2l));
+
+ if (low == (code == MIN_EXPR))
+ low = int1l, hi = int1h;
+ else
+ low = int2l, hi = int2h;
+ break;
+
+ default:
+ return NULL_TREE;
+ }
+
+ if (overflow_p)
+ *overflow_p = overflow;
+
+ t = force_fit_type_1 (type, low, hi, overflow_p);
+
+ return t;
+ }
+
/* Combine two integer constants ARG1 and ARG2 under operation CODE
to produce a new constant. Return NULL_TREE if we don't know how
to evaluate CODE at compile-time.
Index: testsuite/gcc.dg/tree-ssa/vrp31.c
===================================================================
*** testsuite/gcc.dg/tree-ssa/vrp31.c (revision 0)
--- testsuite/gcc.dg/tree-ssa/vrp31.c (revision 0)
***************
*** 0 ****
--- 1,43 ----
+ /* { dg-do link } */
+ /* { dg-options "-O -ftree-vrp" } */
+
+ extern void link_error(void);
+
+ #define RANGE(name, min, max) if (name < min) return; if (name > max) return;
+ #define ANTI_RANGE(name, min, max) if (name >= min) if (name <= max) return;
+ #define CHECK_RANGE(expr, min, max) ({ __typeof__ (expr) v = (expr); if (v < min) link_error(); if (v > max) link_error(); })
+ #define CHECK_ANTI_RANGE(expr, min, max) ({ __typeof__ (expr) v = (expr); if (v >= min) if (v <= max) link_error(); })
+
+ void test1(int i, int j)
+ {
+ RANGE(i, 1, 5);
+ RANGE(j, 7, 10);
+ CHECK_RANGE(i + j, 8, 15);
+ }
+
+ #define UINT_MAX 2*(unsigned)__INT_MAX__ + 1
+ void test2(unsigned int i)
+ {
+ RANGE(i, UINT_MAX - 0x4, UINT_MAX - 0x1);
+ CHECK_ANTI_RANGE(i + 0x2, 0x1, UINT_MAX - 0x3);
+ }
+ void test3(unsigned int i)
+ {
+ RANGE(i, UINT_MAX - 0x4, UINT_MAX - 0x1);
+ CHECK_RANGE(i + 0x5, 0x0, 0x3);
+ }
+ void test4(unsigned int i)
+ {
+ RANGE(i, 2, 4);
+ CHECK_ANTI_RANGE(i - 4, 1, UINT_MAX - 2);
+ }
+ void test5(unsigned int i)
+ {
+ RANGE(i, 2, 4);
+ CHECK_RANGE(i - 8, UINT_MAX - 5, UINT_MAX - 3);
+ }
+
+ int main()
+ {
+ }
+
Index: tree-vrp.c
===================================================================
*** tree-vrp.c (revision 120547)
--- tree-vrp.c (working copy)
*************** set_value_range (value_range_t *vr, enum
*** 168,173 ****
--- 168,198 ----
gcc_assert (equiv == NULL || bitmap_empty_p (equiv));
#endif
+ /* Canonicalize anti-ranges that start or end at TYPE_MIN_VALUE
+ or TYPE_MAX_VALUE to the appropriate range instead. This avoids
+ special casing them in compare_range_with_value.
+ Make sure to preserve ~[a, a] and ~[-INF, +INF] though. */
+ if (t == VR_ANTI_RANGE
+ && !POINTER_TYPE_P (TREE_TYPE (min))
+ && min != max
+ && ((min == TYPE_MIN_VALUE (TREE_TYPE (min)))
+ != (max == TYPE_MAX_VALUE (TREE_TYPE (max)))))
+ {
+ t = VR_RANGE;
+ if (min == TYPE_MIN_VALUE (TREE_TYPE (min)))
+ {
+ min = int_const_binop (PLUS_EXPR, max,
+ build_int_cst (TREE_TYPE (max), 1), 0);
+ max = TYPE_MAX_VALUE (TREE_TYPE (max));
+ }
+ else
+ {
+ max = int_const_binop (MINUS_EXPR, min,
+ build_int_cst (TREE_TYPE (min), 1), 0);
+ min = TYPE_MIN_VALUE (TREE_TYPE (min));
+ }
+ }
+
vr->type = t;
vr->min = min;
vr->max = max;
*************** extract_range_from_assert (value_range_t
*** 1053,1058 ****
--- 1078,1121 ----
set_value_range_to_varying (vr_p);
}
}
+ else if (var_vr->type == VR_ANTI_RANGE && vr_p->type == VR_ANTI_RANGE)
+ {
+ tree type = TREE_TYPE (var_vr->max);
+ tree tmp;
+ bool ovfl;
+
+ /* If the two anti-ranges touch each other, we can merge them.
+ Since the assert expression creates an equivalency and asserts
+ a predicate, we can take the union of the two ranges to get
+ better precision. */
+ if (value_ranges_intersect_p (var_vr, vr_p)
+ || (INTEGRAL_TYPE_P (TREE_TYPE (var_vr->max))
+ && (tmp = int_const_binop_1 (PLUS_EXPR, type, var_vr->max,
+ build_int_cst (type, 1), &ovfl))
+ && !ovfl
+ && value_inside_range (tmp, vr_p))
+ || (INTEGRAL_TYPE_P (TREE_TYPE (vr_p->max))
+ && (tmp = int_const_binop_1 (PLUS_EXPR, type, vr_p->max,
+ build_int_cst (type, 1), &ovfl))
+ && !ovfl
+ && value_inside_range (tmp, var_vr)))
+ {
+ /* Use the smaller of the two minimums. */
+ if (compare_values (vr_p->min, var_vr->min) == -1)
+ min = vr_p->min;
+ else
+ min = var_vr->min;
+
+ /* Use the bigger of the two maximums. */
+ if (compare_values (vr_p->max, var_vr->max) == 1)
+ max = vr_p->max;
+ else
+ max = var_vr->max;
+
+ set_value_range (vr_p, vr_p->type, min, max, vr_p->equiv);
+ }
+ /* Else we can just use one of both, choose vr_p. */
+ }
else if ((var_vr->type == VR_RANGE && vr_p->type == VR_ANTI_RANGE)
|| (var_vr->type == VR_ANTI_RANGE && vr_p->type == VR_RANGE))
{
*************** extract_range_from_ssa_name (value_range
*** 1186,1289 ****
}
- /* 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. */
-
- static inline tree
- vrp_int_const_binop (enum tree_code code, tree val1, tree val2)
- {
- tree res;
-
- res = int_const_binop (code, val1, val2, 0);
-
- /* If we are not using wrapping arithmetic, operate symbolically
- on -INF and +INF. */
- if (TYPE_UNSIGNED (TREE_TYPE (val1))
- || flag_wrapv)
- {
- int checkz = compare_values (res, val1);
- bool overflow = false;
-
- /* Ensure that res = val1 [+*] val2 >= val1
- or that res = val1 - val2 <= val1. */
- if ((code == PLUS_EXPR
- && !(checkz == 1 || checkz == 0))
- || (code == MINUS_EXPR
- && !(checkz == 0 || checkz == -1)))
- {
- overflow = true;
- }
- /* Checking for multiplication overflow is done by dividing the
- output of the multiplication by the first input of the
- multiplication. If the result of that division operation is
- not equal to the second input of the multiplication, then the
- multiplication overflowed. */
- else if (code == MULT_EXPR && !integer_zerop (val1))
- {
- tree tmp = int_const_binop (TRUNC_DIV_EXPR,
- res,
- val1, 0);
- int check = compare_values (tmp, val2);
-
- if (check != 0)
- overflow = true;
- }
-
- if (overflow)
- {
- res = copy_node (res);
- TREE_OVERFLOW (res) = 1;
- }
-
- }
- else if (TREE_OVERFLOW (res)
- && !TREE_OVERFLOW (val1)
- && !TREE_OVERFLOW (val2))
- {
- /* If the operation overflowed but neither VAL1 nor VAL2 are
- overflown, return -INF or +INF depending on the operation
- and the combination of signs of the operands. */
- int sgn1 = tree_int_cst_sgn (val1);
- int sgn2 = tree_int_cst_sgn (val2);
-
- /* 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
- can yield overflow without overflown operands because we
- are working with integral types only... except in the
- case VAL1 = -INF and VAL2 = -1 which overflows to +INF
- for division too. */
-
- /* For multiplication, the sign of the overflow is given
- by the comparison of the signs of the operands. */
- if ((code == MULT_EXPR && sgn1 == sgn2)
- /* For addition, the operands must be of the same sign
- 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 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));
- else
- return TYPE_MIN_VALUE (TREE_TYPE (res));
- }
-
- return res;
- }
-
-
/* Extract range information from a binary expression EXPR based on
the ranges of each of its operands and the expression code. */
--- 1249,1254 ----
*************** extract_range_from_binary_expr (value_ra
*** 1324,1330 ****
op0 = TREE_OPERAND (expr, 0);
if (TREE_CODE (op0) == SSA_NAME)
vr0 = *(get_value_range (op0));
! else if (is_gimple_min_invariant (op0))
set_value_range (&vr0, VR_RANGE, op0, op0, NULL);
else
set_value_range_to_varying (&vr0);
--- 1289,1296 ----
op0 = TREE_OPERAND (expr, 0);
if (TREE_CODE (op0) == SSA_NAME)
vr0 = *(get_value_range (op0));
! else if (is_gimple_min_invariant (op0)
! && TREE_CODE (op0) != ADDR_EXPR)
set_value_range (&vr0, VR_RANGE, op0, op0, NULL);
else
set_value_range_to_varying (&vr0);
*************** extract_range_from_binary_expr (value_ra
*** 1332,1338 ****
op1 = TREE_OPERAND (expr, 1);
if (TREE_CODE (op1) == SSA_NAME)
vr1 = *(get_value_range (op1));
! else if (is_gimple_min_invariant (op1))
set_value_range (&vr1, VR_RANGE, op1, op1, NULL);
else
set_value_range_to_varying (&vr1);
--- 1298,1305 ----
op1 = TREE_OPERAND (expr, 1);
if (TREE_CODE (op1) == SSA_NAME)
vr1 = *(get_value_range (op1));
! else if (is_gimple_min_invariant (op1)
! && TREE_CODE (op1) != ADDR_EXPR)
set_value_range (&vr1, VR_RANGE, op1, op1, NULL);
else
set_value_range_to_varying (&vr1);
*************** extract_range_from_binary_expr (value_ra
*** 1443,1470 ****
return;
}
}
! else if (code == PLUS_EXPR
! || code == MIN_EXPR
|| code == MAX_EXPR)
{
! /* If we have a PLUS_EXPR with two VR_ANTI_RANGEs, drop to
! VR_VARYING. It would take more effort to compute a precise
range for such a case. For example, if we have op0 == 1 and
op1 == -1 with their ranges both being ~[0,0], we would have
op0 + op1 == 0, so we cannot claim that the sum is in ~[0,0].
Note that we are guaranteed to have vr0.type == vr1.type at
this point. */
! if (code == PLUS_EXPR && vr0.type == VR_ANTI_RANGE)
{
set_value_range_to_varying (vr);
return;
}
! /* For operations that make the resulting range directly
! proportional to the original ranges, apply the operation to
! the same end of each range. */
! min = vrp_int_const_binop (code, vr0.min, vr1.min);
! max = vrp_int_const_binop (code, vr0.max, vr1.max);
}
else if (code == MULT_EXPR
|| code == TRUNC_DIV_EXPR
--- 1410,1496 ----
return;
}
}
! else if (code == MIN_EXPR
|| code == MAX_EXPR)
{
! /* For min and max we can just apply the operation to the same
! end of each range. */
! min = int_const_binop (code, vr0.min, vr1.min, 0);
! max = int_const_binop (code, vr0.max, vr1.max, 0);
! }
! else if (code == PLUS_EXPR
! || code == MINUS_EXPR)
! {
! bool omin, omax;
!
! /* If we have a PLUS_EXPR or MINUS_EXPR with two VR_ANTI_RANGEs, drop
! to VR_VARYING. It would take more effort to compute a precise
range for such a case. For example, if we have op0 == 1 and
op1 == -1 with their ranges both being ~[0,0], we would have
op0 + op1 == 0, so we cannot claim that the sum is in ~[0,0].
Note that we are guaranteed to have vr0.type == vr1.type at
this point. */
! if (vr0.type == VR_ANTI_RANGE)
{
set_value_range_to_varying (vr);
return;
}
! /* For PLUS_EXPR apply the operation to the same end of each range. */
! if (code == PLUS_EXPR)
! {
! min = int_const_binop_1 (code, TREE_TYPE (vr0.min),
! vr0.min, vr1.min, &omin);
! max = int_const_binop_1 (code, TREE_TYPE (vr0.max),
! vr0.max, vr1.max, &omax);
! }
!
! /* For MINUS_EXPR, apply the operation to the opposite ends of
! each range. */
! if (code == MINUS_EXPR)
! {
! min = int_const_binop_1 (code, TREE_TYPE (vr0.min),
! vr0.min, vr1.max, &omin);
! max = int_const_binop_1 (code, TREE_TYPE (vr0.max),
! vr0.max, vr1.min, &omax);
! }
!
! /* Overflow is handled by creating an anti-range if necessary for
! wrapping overflow or by saturating to TYPE_MIN_VALUE or
! TYPE_MAX_VALUE if overflow is undefined. */
! if (TYPE_UNSIGNED (TREE_TYPE (vr0.min))
! || flag_wrapv)
! {
! /* If overflow behavior for both a + c and b + d are the same
! the result is a valid range again. If only max overflowed,
! create a proper anti-range for the result by swapping
! min and max and adjusting them by one. */
! if (omin != omax)
! {
! tree one = build_int_cst (TREE_TYPE (max), 1);
! tree tmp = min;
! type = VR_ANTI_RANGE;
! min = int_const_binop_1 (PLUS_EXPR, TREE_TYPE (max),
! max, one, &omin);
! max = int_const_binop_1 (MINUS_EXPR, TREE_TYPE (tmp),
! tmp, one, &omax);
! /* We can wrap again in transforming to an ANTI_RANGE, bail
! out in this case. */
! if (omin || omax)
! {
! set_value_range_to_varying (vr);
! return;
! }
! }
! }
! else
! {
! /* If overflow is undefined treat overflow as -INF/+INF. */
! if (omin)
! min = TYPE_MIN_VALUE (TREE_TYPE (min));
! if (omax)
! max = TYPE_MAX_VALUE (TREE_TYPE (max));
! }
}
else if (code == MULT_EXPR
|| code == TRUNC_DIV_EXPR
*************** extract_range_from_binary_expr (value_ra
*** 1475,1480 ****
--- 1501,1507 ----
{
tree val[4];
size_t i;
+ bool ovfl;
/* If we have an unsigned MULT_EXPR with two VR_ANTI_RANGEs,
drop to VR_VARYING. It would take more effort to compute a
*************** extract_range_from_binary_expr (value_ra
*** 1501,1508 ****
However, this involves several calls to compare_values and it
is pretty convoluted. It's simpler to do the 4 operations
! (MIN0 OP MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP
! MAX1) and then figure the smallest and largest values to form
the new range. */
/* Divisions by zero result in a VARYING value. */
--- 1528,1535 ----
However, this involves several calls to compare_values and it
is pretty convoluted. It's simpler to do the 4 operations
! (MIN0 OP MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX1)
! and then figure the smallest and largest values to form
the new range. */
/* Divisions by zero result in a VARYING value. */
*************** extract_range_from_binary_expr (value_ra
*** 1514,1554 ****
}
/* Compute the 4 cross operations. */
! val[0] = vrp_int_const_binop (code, vr0.min, vr1.min);
! 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;
/* Set MIN to the minimum of VAL[i] and MAX to the maximum
of VAL[i]. */
min = val[0];
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))
- break;
-
if (val[i])
{
- if (!is_gimple_min_invariant (val[i]) || TREE_OVERFLOW (val[i]))
- {
- /* If we found an overflowed value, set MIN and MAX
- to it so that we set the resulting range to
- VARYING. */
- min = max = val[i];
- break;
- }
-
if (compare_values (val[i], min) == -1)
min = val[i];
--- 1541,1579 ----
}
/* Compute the 4 cross operations. */
! val[0] = int_const_binop_1 (code, TREE_TYPE (vr0.min),
! vr0.min, vr1.min, &ovfl);
! val[1] = (vr1.max != vr1.min && !ovfl)
! ? int_const_binop_1 (code, TREE_TYPE (vr0.min),
! vr0.min, vr1.max, &ovfl)
: NULL_TREE;
! val[2] = (vr0.max != vr0.min && !ovfl)
! ? int_const_binop_1 (code, TREE_TYPE (vr0.max),
! vr0.max, vr1.min, &ovfl)
: NULL_TREE;
! val[3] = (vr0.min != vr0.max && vr1.min != vr1.max && !ovfl)
! ? int_const_binop_1 (code, TREE_TYPE (vr0.max),
! vr0.max, vr1.max, &ovfl)
: NULL_TREE;
+ /* If any overflow occured drop to varying. */
+ if (ovfl)
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
+
/* Set MIN to the minimum of VAL[i] and MAX to the maximum
of VAL[i]. */
min = val[0];
max = val[0];
for (i = 1; i < 4; i++)
{
if (val[i])
{
if (compare_values (val[i], min) == -1)
min = val[i];
*************** extract_range_from_binary_expr (value_ra
*** 1557,1582 ****
}
}
}
- else if (code == MINUS_EXPR)
- {
- /* If we have a MINUS_EXPR with two VR_ANTI_RANGEs, drop to
- VR_VARYING. It would take more effort to compute a precise
- range for such a case. For example, if we have op0 == 1 and
- op1 == 1 with their ranges both being ~[0,0], we would have
- op0 - op1 == 0, so we cannot claim that the difference is in
- ~[0,0]. Note that we are guaranteed to have
- vr0.type == vr1.type at this point. */
- if (vr0.type == VR_ANTI_RANGE)
- {
- set_value_range_to_varying (vr);
- return;
- }
-
- /* For MINUS_EXPR, apply the operation to the opposite ends of
- each range. */
- min = vrp_int_const_binop (code, vr0.min, vr1.max);
- max = vrp_int_const_binop (code, vr0.max, vr1.min);
- }
else if (code == BIT_AND_EXPR)
{
if (vr0.type == VR_RANGE
--- 1582,1587 ----
*************** compare_range_with_value (enum tree_code
*** 2230,2235 ****
--- 2237,2249 ----
/* Anti-ranges need to be handled separately. */
if (vr->type == VR_ANTI_RANGE)
{
+ /* Comparing with the special anti-range ~[-INF, +INF] yields
+ arbitrary result. It can occur on dead parts of the CFG. */
+ if (!POINTER_TYPE_P (TREE_TYPE (vr->min))
+ && vr->min == TYPE_MIN_VALUE (TREE_TYPE (vr->min))
+ && vr->max == TYPE_MAX_VALUE (TREE_TYPE (vr->max)))
+ return boolean_false_node;
+
/* For anti-ranges, the only predicates that we can compute at
compile time are equality and inequality. */
if (comp == GT_EXPR