Hello,
here is a slight improvement to VRP for sum and difference of intervals.
There are some things I left because I didn't understand them enough:
* range_int_cst_p (&vr0): I thought it was always true by that time, but
it isn't obvious
* TYPE_PRECISION (expr_type) <= HOST_BITS_PER_DOUBLE_INT: the __int256
patch scared me (though I would love to have larger types, especially with
a proper range analysis to use only 2 or 3 of the 4 64-bit integers that
make up an __int256 when it is enough, see PR 53100 for the __int128
version)
* when is the value range of a type smaller than the one given by its
precision? Is it for enum?
2012-07-25 Marc Glisse <marc.gli...@inria.fr>
PR tree-optimization/30318
* tree-vrp.c (extract_range_from_binary_expr_1) [PLUS_EXPR]:
Handle __int128.
[MINUS_EXPR] merge with PLUS_EXPR.
bootstrapped just c and c++ and ran the testsuite with no new regression.
--
Marc GlisseIndex: tree-vrp.c
===================================================================
--- tree-vrp.c (revision 189779)
+++ tree-vrp.c (working copy)
@@ -2345,157 +2345,194 @@ extract_range_from_binary_expr_1 (value_
set_value_range_to_varying (vr);
}
else
set_value_range_to_varying (vr);
return;
}
/* For integer ranges, apply the operation to each end of the
range and see what we end up with. */
- if (code == PLUS_EXPR)
+ if (code == PLUS_EXPR || code == MINUS_EXPR)
{
/* If we have a PLUS_EXPR with two VR_RANGE integer constant
ranges compute the precise range for such case if possible. */
if (range_int_cst_p (&vr0)
&& range_int_cst_p (&vr1)
- /* We attempt to do infinite precision signed integer arithmetic,
- thus we need two more bits than the possibly unsigned inputs. */
- && TYPE_PRECISION (expr_type) < HOST_BITS_PER_DOUBLE_INT - 1)
+ /* We need as many bits as the possibly unsigned inputs. */
+ && TYPE_PRECISION (expr_type) <= HOST_BITS_PER_DOUBLE_INT)
{
double_int min0 = tree_to_double_int (vr0.min);
double_int max0 = tree_to_double_int (vr0.max);
double_int min1 = tree_to_double_int (vr1.min);
double_int max1 = tree_to_double_int (vr1.max);
bool uns = TYPE_UNSIGNED (expr_type);
double_int type_min
= double_int_min_value (TYPE_PRECISION (expr_type), uns);
double_int type_max
= double_int_max_value (TYPE_PRECISION (expr_type), uns);
double_int dmin, dmax;
+ int min_ovf = 0;
+ int max_ovf = 0;
- dmin = double_int_add (min0, min1);
- dmax = double_int_add (max0, max1);
+ if (code == PLUS_EXPR)
+ {
+ dmin = double_int_add (min0, min1);
+ dmax = double_int_add (max0, max1);
+
+ /* Check for overflow in double_int. */
+ if (double_int_cmp (min1, double_int_zero, uns)
+ != double_int_cmp (dmin, min0, uns))
+ min_ovf = double_int_cmp (min0, dmin, uns);
+ if (double_int_cmp (max1, double_int_zero, uns)
+ != double_int_cmp (dmax, max0, uns))
+ max_ovf = double_int_cmp (max0, dmax, uns);
+ }
+ else /* if (code == MINUS_EXPR) */
+ {
+ dmin = double_int_sub (min0, max1);
+ dmax = double_int_sub (max0, min1);
+
+ if (double_int_cmp (double_int_zero, max1, uns)
+ != double_int_cmp (dmin, min0, uns))
+ min_ovf = double_int_cmp (min0, max1, uns);
+ if (double_int_cmp (double_int_zero, min1, uns)
+ != double_int_cmp (dmax, max0, uns))
+ max_ovf = double_int_cmp (max0, min1, uns);
+ }
+
+ /* For non-wrapping arithmetic look at possibly smaller
+ value-ranges of the type. */
+ if (!TYPE_OVERFLOW_WRAPS (expr_type))
+ {
+ if (vrp_val_min (expr_type))
+ type_min = tree_to_double_int (vrp_val_min (expr_type));
+ if (vrp_val_max (expr_type))
+ type_max = tree_to_double_int (vrp_val_max (expr_type));
+ }
+
+ /* Check for type overflow. */
+ if (min_ovf == 0)
+ {
+ if (double_int_cmp (dmin, type_min, uns) == -1)
+ min_ovf = -1;
+ else if (double_int_cmp (dmin, type_max, uns) == 1)
+ min_ovf = 1;
+ }
+ if (max_ovf == 0)
+ {
+ if (double_int_cmp (dmax, type_min, uns) == -1)
+ max_ovf = -1;
+ else if (double_int_cmp (dmax, type_max, uns) == 1)
+ max_ovf = 1;
+ }
if (TYPE_OVERFLOW_WRAPS (expr_type))
{
/* If overflow wraps, truncate the values and adjust the
range kind and bounds appropriately. */
double_int tmin
= double_int_ext (dmin, TYPE_PRECISION (expr_type), uns);
double_int tmax
= double_int_ext (dmax, TYPE_PRECISION (expr_type), uns);
- gcc_assert (double_int_scmp (dmin, dmax) <= 0);
- if ((double_int_scmp (dmin, type_min) == -1
- && double_int_scmp (dmax, type_min) == -1)
- || (double_int_scmp (dmin, type_max) == 1
- && double_int_scmp (dmax, type_max) == 1)
- || (double_int_scmp (type_min, dmin) <= 0
- && double_int_scmp (dmax, type_max) <= 0))
+ if (min_ovf == max_ovf)
{
/* No overflow or both overflow or underflow. The
range kind stays VR_RANGE. */
min = double_int_to_tree (expr_type, tmin);
max = double_int_to_tree (expr_type, tmax);
}
- else if (double_int_scmp (dmin, type_min) == -1
- && double_int_scmp (dmax, type_max) == 1)
+ else if (min_ovf == -1
+ && max_ovf == 1)
{
/* Underflow and overflow, drop to VR_VARYING. */
set_value_range_to_varying (vr);
return;
}
else
{
/* Min underflow or max overflow. The range kind
changes to VR_ANTI_RANGE. */
double_int tem = tmin;
- gcc_assert ((double_int_scmp (dmin, type_min) == -1
- && double_int_scmp (dmax, type_min) >= 0
- && double_int_scmp (dmax, type_max) <= 0)
- || (double_int_scmp (dmax, type_max) == 1
- && double_int_scmp (dmin, type_min) >= 0
- && double_int_scmp (dmin, type_max) <= 0));
+ gcc_assert ((min_ovf == -1 && max_ovf == 0)
+ || (max_ovf == 1 && min_ovf == 0));
type = VR_ANTI_RANGE;
tmin = double_int_add (tmax, double_int_one);
tmax = double_int_add (tem, double_int_minus_one);
/* If the anti-range would cover nothing, drop to varying.
Likewise if the anti-range bounds are outside of the
types values. */
if (double_int_cmp (tmin, tmax, uns) > 0
|| double_int_cmp (tmin, type_min, uns) < 0
|| double_int_cmp (tmax, type_max, uns) > 0)
{
set_value_range_to_varying (vr);
return;
}
min = double_int_to_tree (expr_type, tmin);
max = double_int_to_tree (expr_type, tmax);
}
}
else
{
- /* For non-wrapping arithmetic look at possibly smaller
- value-ranges of the type. */
- if (vrp_val_min (expr_type))
- type_min = tree_to_double_int (vrp_val_min (expr_type));
- if (vrp_val_max (expr_type))
- type_max = tree_to_double_int (vrp_val_max (expr_type));
-
/* If overflow does not wrap, saturate to the types min/max
value. */
- if (double_int_scmp (dmin, type_min) == -1)
+ if (min_ovf == -1)
{
if (needs_overflow_infinity (expr_type)
&& supports_overflow_infinity (expr_type))
min = negative_overflow_infinity (expr_type);
else
min = double_int_to_tree (expr_type, type_min);
}
- else if (double_int_scmp (dmin, type_max) == 1)
+ else if (min_ovf == 1)
{
if (needs_overflow_infinity (expr_type)
&& supports_overflow_infinity (expr_type))
min = positive_overflow_infinity (expr_type);
else
min = double_int_to_tree (expr_type, type_max);
}
else
min = double_int_to_tree (expr_type, dmin);
- if (double_int_scmp (dmax, type_min) == -1)
+ if (max_ovf == -1)
{
if (needs_overflow_infinity (expr_type)
&& supports_overflow_infinity (expr_type))
max = negative_overflow_infinity (expr_type);
else
max = double_int_to_tree (expr_type, type_min);
}
- else if (double_int_scmp (dmax, type_max) == 1)
+ else if (max_ovf == 1)
{
if (needs_overflow_infinity (expr_type)
&& supports_overflow_infinity (expr_type))
max = positive_overflow_infinity (expr_type);
else
max = double_int_to_tree (expr_type, type_max);
}
else
max = double_int_to_tree (expr_type, dmax);
}
if (needs_overflow_infinity (expr_type)
&& supports_overflow_infinity (expr_type))
{
if (is_negative_overflow_infinity (vr0.min)
- || is_negative_overflow_infinity (vr1.min))
+ || (code == PLUS_EXPR
+ ? is_negative_overflow_infinity (vr1.min)
+ : is_positive_overflow_infinity (vr1.max)))
min = negative_overflow_infinity (expr_type);
if (is_positive_overflow_infinity (vr0.max)
- || is_positive_overflow_infinity (vr1.max))
+ || (code == PLUS_EXPR
+ ? is_positive_overflow_infinity (vr1.max)
+ : is_negative_overflow_infinity (vr1.min)))
max = positive_overflow_infinity (expr_type);
}
}
else
{
/* For other cases, for example 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.
??? General even mixed range kind operations can be expressed
by for example transforming ~[3, 5] + [1, 2] to range-only
@@ -2710,40 +2747,20 @@ extract_range_from_binary_expr_1 (value_
max = vr1.max;
max = int_const_binop (MINUS_EXPR, max, integer_one_node);
/* If the dividend is non-negative the modulus will be
non-negative as well. */
if (TYPE_UNSIGNED (expr_type)
|| value_range_nonnegative_p (&vr0))
min = build_int_cst (TREE_TYPE (max), 0);
else
min = fold_unary_to_constant (NEGATE_EXPR, expr_type, max);
}
- 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 || code == BIT_IOR_EXPR || code ==
BIT_XOR_EXPR)
{
bool int_cst_range0, int_cst_range1;
double_int may_be_nonzero0, may_be_nonzero1;
double_int must_be_nonzero0, must_be_nonzero1;
int_cst_range0 = zero_nonzero_bits_from_vr (&vr0, &may_be_nonzero0,
&must_be_nonzero0);
int_cst_range1 = zero_nonzero_bits_from_vr (&vr1, &may_be_nonzero1,
&must_be_nonzero1);
