More VRP TLC, this restructures extract_range_from_binary_expr_1 a bit,
avoiding to glob unrelated tree codes to avoid some code duplication.
Instead factor out the common code.
Bootstrapped and tested on x86_64-unknown-linux-gnu, applied to trunk.
Richard.
2011-08-16 Richard Guenther <rguent...@suse.de>
* tree-vrp.c (extract_range_from_multiplicative_op_1): New
helper factored out from ...
(extract_range_from_binary_expr_1): ... here. Re-structure
to not glob handling too different tree codes.
Index: gcc/tree-vrp.c
===================================================================
*** gcc/tree-vrp.c (revision 177762)
--- gcc/tree-vrp.c (working copy)
*************** zero_nonzero_bits_from_vr (value_range_t
*** 2181,2186 ****
--- 2181,2338 ----
return true;
}
+ /* Helper to extract a value-range *VR for a multiplicative operation
+ *VR0 CODE *VR1. */
+
+ static void
+ extract_range_from_multiplicative_op_1 (value_range_t *vr,
+ enum tree_code code,
+ value_range_t *vr0, value_range_t *vr1)
+ {
+ enum value_range_type type;
+ tree val[4];
+ size_t i;
+ tree min, max;
+ bool sop;
+ int cmp;
+
+ /* Multiplications, divisions and shifts are a bit tricky to handle,
+ depending on the mix of signs we have in the two ranges, we
+ need to operate on different values to get the minimum and
+ maximum values for the new range. One approach is to figure
+ out all the variations of range combinations and do the
+ operations.
+
+ 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. */
+ gcc_assert (code == MULT_EXPR
+ || code == TRUNC_DIV_EXPR
+ || code == FLOOR_DIV_EXPR
+ || code == CEIL_DIV_EXPR
+ || code == EXACT_DIV_EXPR
+ || code == ROUND_DIV_EXPR
+ || code == RSHIFT_EXPR);
+ gcc_assert ((vr0->type == VR_RANGE
+ || (code == MULT_EXPR && vr0->type == VR_ANTI_RANGE))
+ && vr0->type == vr1->type);
+
+ type = vr0->type;
+
+ /* 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;
+ }
+
+ 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]. */
+ min = val[0];
+ max = val[0];
+ for (i = 1; i < 4; i++)
+ {
+ 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])
+ && !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
+ VARYING. */
+ min = max = val[i];
+ break;
+ }
+
+ if (compare_values (val[i], min) == -1)
+ min = val[i];
+
+ if (compare_values (val[i], max) == 1)
+ max = val[i];
+ }
+ }
+
+ /* If either MIN or MAX overflowed, then set the resulting range to
+ 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;
+ }
+
+ /* We punt if:
+ 1) [-INF, +INF]
+ 2) [-INF, +-INF(OVF)]
+ 3) [+-INF(OVF), +INF]
+ 4) [+-INF(OVF), +-INF(OVF)]
+ We learn nothing when we have INF and INF(OVF) on both sides.
+ Note that we do accept [-INF, -INF] and [+INF, +INF] without
+ overflow. */
+ if ((vrp_val_is_min (min) || is_overflow_infinity (min))
+ && (vrp_val_is_max (max) || is_overflow_infinity (max)))
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
+
+ cmp = compare_values (min, max);
+ if (cmp == -2 || cmp == 1)
+ {
+ /* If the new range has its limits swapped around (MIN > MAX),
+ then the operation caused one of them to wrap around, mark
+ the new range VARYING. */
+ set_value_range_to_varying (vr);
+ }
+ else
+ set_value_range (vr, type, min, max, NULL);
+ }
/* Extract range information from a binary operation CODE based on
the ranges of each of its operands, *VR0 and *VR1 with resulting
*************** extract_range_from_binary_expr_1 (value_
*** 2193,2201 ****
{
value_range_t vr0 = *vr0_, vr1 = *vr1_;
enum value_range_type type;
! tree min, max;
int cmp;
/* Not all binary expressions can be applied to ranges in a
meaningful way. Handle only arithmetic operations. */
if (code != PLUS_EXPR
--- 2345,2360 ----
{
value_range_t vr0 = *vr0_, vr1 = *vr1_;
enum value_range_type type;
! tree min = NULL_TREE, max = NULL_TREE;
int cmp;
+ if (!INTEGRAL_TYPE_P (expr_type)
+ && !POINTER_TYPE_P (expr_type))
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
+
/* Not all binary expressions can be applied to ranges in a
meaningful way. Handle only arithmetic operations. */
if (code != PLUS_EXPR
*************** extract_range_from_binary_expr_1 (value_
*** 2307,2315 ****
/* For integer ranges, apply the operation to each end of the
range and see what we end up with. */
! 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
--- 2466,2472 ----
/* For integer ranges, apply the operation to each end of the
range and see what we end up with. */
! if (code == PLUS_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
*************** extract_range_from_binary_expr_1 (value_
*** 2320,2351 ****
this point. */
if (vr0.type == VR_ANTI_RANGE)
{
! if (code == PLUS_EXPR)
! {
! set_value_range_to_varying (vr);
! return;
! }
! /* For MIN_EXPR and MAX_EXPR with two VR_ANTI_RANGEs,
! the resulting VR_ANTI_RANGE is the same - intersection
! of the two ranges. */
! min = vrp_int_const_binop (MAX_EXPR, vr0.min, vr1.min);
! max = vrp_int_const_binop (MIN_EXPR, vr0.max, vr1.max);
! }
! else
! {
! /* 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);
}
/* If both additions overflowed the range kind is still correct.
This happens regularly with subtracting something in unsigned
arithmetic.
??? See PR30318 for all the cases we do not handle. */
! if (code == PLUS_EXPR
! && (TREE_OVERFLOW (min) && !is_overflow_infinity (min))
&& (TREE_OVERFLOW (max) && !is_overflow_infinity (max)))
{
min = build_int_cst_wide (TREE_TYPE (min),
--- 2477,2497 ----
this point. */
if (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);
+
/* If both additions overflowed the range kind is still correct.
This happens regularly with subtracting something in unsigned
arithmetic.
??? See PR30318 for all the cases we do not handle. */
! if ((TREE_OVERFLOW (min) && !is_overflow_infinity (min))
&& (TREE_OVERFLOW (max) && !is_overflow_infinity (max)))
{
min = build_int_cst_wide (TREE_TYPE (min),
*************** extract_range_from_binary_expr_1 (value_
*** 2356,2373 ****
TREE_INT_CST_HIGH (max));
}
}
! else if (code == MULT_EXPR
! || code == TRUNC_DIV_EXPR
! || code == FLOOR_DIV_EXPR
! || code == CEIL_DIV_EXPR
! || code == EXACT_DIV_EXPR
! || code == ROUND_DIV_EXPR
! || code == RSHIFT_EXPR)
{
- tree val[4];
- size_t i;
- bool sop;
-
/* If we have an unsigned MULT_EXPR with two VR_ANTI_RANGEs,
drop to VR_VARYING. It would take more effort to compute a
precise range for such a case. For example, if we have
--- 2502,2529 ----
TREE_INT_CST_HIGH (max));
}
}
! else if (code == MIN_EXPR
! || code == MAX_EXPR)
! {
! if (vr0.type == VR_ANTI_RANGE)
! {
! /* For MIN_EXPR and MAX_EXPR with two VR_ANTI_RANGEs,
! the resulting VR_ANTI_RANGE is the same - intersection
! of the two ranges. */
! min = vrp_int_const_binop (MAX_EXPR, vr0.min, vr1.min);
! max = vrp_int_const_binop (MIN_EXPR, vr0.max, vr1.max);
! }
! else
! {
! /* 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)
{
/* If we have an unsigned MULT_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
*************** extract_range_from_binary_expr_1 (value_
*** 2376,2389 ****
we cannot claim that the product is in ~[0,0]. Note that we
are guaranteed to have vr0.type == vr1.type at this
point. */
! if (code == MULT_EXPR
! && vr0.type == VR_ANTI_RANGE
&& !TYPE_OVERFLOW_UNDEFINED (expr_type))
{
set_value_range_to_varying (vr);
return;
}
/* If we have a RSHIFT_EXPR with any shift values outside [0..prec-1],
then drop to VR_VARYING. Outside of this range we get undefined
behavior from the shift operation. We cannot even trust
--- 2532,2549 ----
we cannot claim that the product is in ~[0,0]. Note that we
are guaranteed to have vr0.type == vr1.type at this
point. */
! if (vr0.type == VR_ANTI_RANGE
&& !TYPE_OVERFLOW_UNDEFINED (expr_type))
{
set_value_range_to_varying (vr);
return;
}
+ extract_range_from_multiplicative_op_1 (vr, code, &vr0, &vr1);
+ return;
+ }
+ else if (code == RSHIFT_EXPR)
+ {
/* If we have a RSHIFT_EXPR with any shift values outside [0..prec-1],
then drop to VR_VARYING. Outside of this range we get undefined
behavior from the shift operation. We cannot even trust
*************** extract_range_from_binary_expr_1 (value_
*** 2402,2413 ****
}
}
! else if ((code == TRUNC_DIV_EXPR
! || code == FLOOR_DIV_EXPR
! || code == CEIL_DIV_EXPR
! || code == EXACT_DIV_EXPR
! || code == ROUND_DIV_EXPR)
! && (vr0.type != VR_RANGE || symbolic_range_p (&vr0)))
{
/* For division, if op1 has VR_RANGE but op0 does not, something
can be deduced just from that range. Say [min, max] / [4, max]
--- 2562,2577 ----
}
}
! extract_range_from_multiplicative_op_1 (vr, code, &vr0, &vr1);
! return;
! }
! else if (code == TRUNC_DIV_EXPR
! || code == FLOOR_DIV_EXPR
! || code == CEIL_DIV_EXPR
! || code == EXACT_DIV_EXPR
! || code == ROUND_DIV_EXPR)
! {
! if (vr0.type != VR_RANGE || symbolic_range_p (&vr0))
{
/* For division, if op1 has VR_RANGE but op0 does not, something
can be deduced just from that range. Say [min, max] / [4, max]
*************** extract_range_from_binary_expr_1 (value_
*** 2429,2440 ****
/* For divisions, if flag_non_call_exceptions is true, we must
not eliminate a division by zero. */
! if ((code == TRUNC_DIV_EXPR
! || code == FLOOR_DIV_EXPR
! || code == CEIL_DIV_EXPR
! || code == EXACT_DIV_EXPR
! || code == ROUND_DIV_EXPR)
! && cfun->can_throw_non_call_exceptions
&& (vr1.type != VR_RANGE
|| symbolic_range_p (&vr1)
|| range_includes_zero_p (&vr1)))
--- 2593,2599 ----
/* For divisions, if flag_non_call_exceptions is true, we must
not eliminate a division by zero. */
! if (cfun->can_throw_non_call_exceptions
&& (vr1.type != VR_RANGE
|| symbolic_range_p (&vr1)
|| range_includes_zero_p (&vr1)))
*************** extract_range_from_binary_expr_1 (value_
*** 2446,2457 ****
/* For divisions, if op0 is VR_RANGE, we can deduce a range
even if op1 is VR_VARYING, VR_ANTI_RANGE, symbolic or can
include 0. */
! if ((code == TRUNC_DIV_EXPR
! || code == FLOOR_DIV_EXPR
! || code == CEIL_DIV_EXPR
! || code == EXACT_DIV_EXPR
! || code == ROUND_DIV_EXPR)
! && vr0.type == VR_RANGE
&& (vr1.type != VR_RANGE
|| symbolic_range_p (&vr1)
|| range_includes_zero_p (&vr1)))
--- 2605,2611 ----
/* For divisions, if op0 is VR_RANGE, we can deduce a range
even if op1 is VR_VARYING, VR_ANTI_RANGE, symbolic or can
include 0. */
! if (vr0.type == VR_RANGE
&& (vr1.type != VR_RANGE
|| symbolic_range_p (&vr1)
|| range_includes_zero_p (&vr1)))
*************** extract_range_from_binary_expr_1 (value_
*** 2459,2465 ****
tree zero = build_int_cst (TREE_TYPE (vr0.min), 0);
int cmp;
- sop = false;
min = NULL_TREE;
max = NULL_TREE;
if (TYPE_UNSIGNED (expr_type)
--- 2613,2618 ----
*************** extract_range_from_binary_expr_1 (value_
*** 2498,2593 ****
return;
}
}
-
- /* Multiplications and divisions are a bit tricky to handle,
- depending on the mix of signs we have in the two ranges, we
- need to operate on different values to get the minimum and
- maximum values for the new range. One approach is to figure
- out all the variations of range combinations and do the
- operations.
-
- 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. */
else
{
! gcc_assert ((vr0.type == VR_RANGE
! || (code == MULT_EXPR && vr0.type == VR_ANTI_RANGE))
! && vr0.type == vr1.type);
!
! /* 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;
! }
!
! 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]. */
! min = val[0];
! max = val[0];
! for (i = 1; i < 4; i++)
! {
! 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])
! && !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
! VARYING. */
! min = max = val[i];
! break;
! }
!
! if (compare_values (val[i], min) == -1)
! min = val[i];
!
! if (compare_values (val[i], max) == 1)
! max = val[i];
! }
! }
}
}
else if (code == TRUNC_MOD_EXPR)
--- 2651,2660 ----
return;
}
}
else
{
! extract_range_from_multiplicative_op_1 (vr, code, &vr0, &vr1);
! return;
}
}
else if (code == TRUNC_MOD_EXPR)
*************** extract_range_from_binary_expr_1 (value_
*** 2733,2743 ****
else
max = min = NULL_TREE;
}
- else
- {
- set_value_range_to_varying (vr);
- return;
- }
}
else
gcc_unreachable ();
--- 2800,2805 ----
