Hi again!
Well, since this hasn't been reviewed and I'm about to overhaul the
TYPE_OVERFLOW_WRAPS code anyhow, might as well lump it all in one patch.
On 07/16/2018 09:19 AM, Aldy Hernandez wrote:
Howdy!
I've abstracted out the cross product calculations into its own
function, and have adapted it to deal with wide ints so it's more
reusable. It required some shuffling around, and implementing things a
bit different, but things should be behave as before.
I also renamed vrp_int_const_binop to make its intent clearer,
especially now that it's really just a wrapper to wide_int_binop that
deals with overflow.
(If wide_int_binop_overflow is generally useful, perhaps we could merge
it with wide_int_overflow.)
This is the same as the previous patch, plus I'm abstracting the
TYPE_OVERFLOW_WRAPS code as well. With this, the code dealing with
MULT_EXPR in vrp gets reduced to handling value_range specific stuff.
Yay code re-use!
A few notes:
This is dead code. I've removed it:
- /* 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
- op0 == 65536 and op1 == 65536 with their ranges both being
- ~[0,0] on a 32-bit machine, we would have op0 * op1 == 0, so
- 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;
- }
Also, the vrp_int typedef has a weird name, especially when we have
widest2_int in gimple-fold.c that does the exact thing. I've moved the
common code to wide-int.h and tree.h so we can all share :).
At some point we could move the wide_int_range* and wide_int_binop* code
into its own file.
Tested on x86-64 Linux.
OK?
gcc/
* wide-int.h (widest2_int): New.
* gimple-fold.c (arith_overflowed_p): Use it.
* tree.h (widest2_int_cst): New.
* tree-vrp.c (wide_int_binop_overflow): Rename from
vrp_int_const_binop.
Rewrite to work on trees.
(extract_range_from_multiplicative_op_1): Abstract code to...
(wide_int_range_min_max): ...here.
(wide_int_range_cross_product): ...and here.
(extract_range_from_binary_expr_1): Abstract overflow code to...
(wide_int_range_cross_product_wrapping): ...here.
* tree-vrp.h (wide_int_range_cross_product): New.
(wide_int_range_cross_product_wrapping): New.
diff --git a/gcc/gimple-fold.c b/gcc/gimple-fold.c
index a6b42834d32..027ca4da97c 100644
--- a/gcc/gimple-fold.c
+++ b/gcc/gimple-fold.c
@@ -3986,9 +3986,6 @@ bool
arith_overflowed_p (enum tree_code code, const_tree type,
const_tree arg0, const_tree arg1)
{
- typedef FIXED_WIDE_INT (WIDE_INT_MAX_PRECISION * 2) widest2_int;
- typedef generic_wide_int <wi::extended_tree <WIDE_INT_MAX_PRECISION * 2> >
- widest2_int_cst;
widest2_int warg0 = widest2_int_cst (arg0);
widest2_int warg1 = widest2_int_cst (arg1);
widest2_int wres;
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 2e1ee86a161..41274b3898c 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -968,64 +968,43 @@ value_range_constant_singleton (value_range *vr)
indeterminate. */
static bool
-vrp_int_const_binop (enum tree_code code, tree val1, tree val2, wide_int *res)
+wide_int_binop_overflow (wide_int &res,
+ enum tree_code code,
+ const wide_int &w0, const wide_int &w1,
+ signop sign, bool overflow_undefined)
{
- wi::overflow_type overflow = wi::OVF_NONE;
- signop sign = TYPE_SIGN (TREE_TYPE (val1));
- wide_int w1 = wi::to_wide (val1);
- wide_int w2 = wi::to_wide (val2);
-
- switch (code)
- {
- case RSHIFT_EXPR:
- case LSHIFT_EXPR:
- w2 = wi::to_wide (val2, TYPE_PRECISION (TREE_TYPE (val1)));
- /* FALLTHRU */
- case MULT_EXPR:
- case TRUNC_DIV_EXPR:
- case EXACT_DIV_EXPR:
- case FLOOR_DIV_EXPR:
- case CEIL_DIV_EXPR:
- case ROUND_DIV_EXPR:
- if (!wide_int_binop (*res, code, w1, w2, sign, &overflow))
- return false;
- break;
-
- default:
- gcc_unreachable ();
- }
+ wi::overflow_type overflow;
+ if (!wide_int_binop (res, code, w0, w1, sign, &overflow))
+ return false;
/* If the operation overflowed return -INF or +INF depending on the
operation and the combination of signs of the operands. */
- if (overflow
- && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (val1)))
- {
- int sign1 = tree_int_cst_sgn (val1);
- int sign2 = 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 && sign1 == sign2)
+ if (overflow && overflow_undefined)
+ {
+ switch (code)
+ {
+ case MULT_EXPR:
+ /* For multiplication, the sign of the overflow is given
+ by the comparison of the signs of the operands. */
+ if (sign == UNSIGNED || w0.sign_mask () == w1.sign_mask ())
+ res = wi::max_value (w0.get_precision (), sign);
+ else
+ res = wi::min_value (w0.get_precision (), sign);
+ return true;
+
+ case TRUNC_DIV_EXPR:
+ case FLOOR_DIV_EXPR:
+ case CEIL_DIV_EXPR:
+ case EXACT_DIV_EXPR:
+ case ROUND_DIV_EXPR:
/* 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)
- *res = wi::max_value (TYPE_PRECISION (TREE_TYPE (val1)), sign);
- else
- *res = wi::min_value (TYPE_PRECISION (TREE_TYPE (val1)), sign);
- return true;
- }
+ res = wi::max_value (w0.get_precision (), sign);
+ return true;
+ default:
+ gcc_unreachable ();
+ }
+ }
return !overflow;
}
@@ -1127,6 +1106,149 @@ ranges_from_anti_range (value_range *ar,
return vr0->type != VR_UNDEFINED;
}
+/* Order 2 sets of wide int ranges (w0/w1, w2/w3) and set MIN/MAX
+ accordingly. */
+
+static void
+wide_int_range_min_max (wide_int &min, wide_int &max,
+ wide_int &w0, wide_int &w1, wide_int &w2, wide_int &w3,
+ signop sign)
+{
+ /* Order pairs w0,w1 and w2,w3. */
+ if (wi::gt_p (w0, w1, sign))
+ std::swap (w0, w1);
+ if (wi::gt_p (w2, w3, sign))
+ std::swap (w2, w3);
+
+ /* Choose min and max from the ordered pairs. */
+ min = wi::min (w0, w2, sign);
+ max = wi::max (w1, w3, sign);
+}
+
+/* Calculate the cross product of two sets of ranges (VR0 and VR1) and
+ store the result in [RES_LB, RES_UB].
+
+ CODE is the operation to perform with sign SIGN.
+
+ OVERFLOW_UNDEFINED is set if overflow is undefined for the operation type.
+
+ Return TRUE if we were able to calculate the cross product. */
+
+bool
+wide_int_range_cross_product (wide_int &res_lb, wide_int &res_ub,
+ enum tree_code code, signop sign,
+ const wide_int &vr0_lb, const wide_int &vr0_ub,
+ const wide_int &vr1_lb, const wide_int &vr1_ub,
+ bool overflow_undefined)
+{
+ wide_int cp1, cp2, cp3, cp4;
+
+ /* Compute the 4 cross operations, bailing if we get an overflow we
+ can't handle. */
+
+ if (!wide_int_binop_overflow (cp1, code, vr0_lb, vr1_lb, sign,
+ overflow_undefined))
+ return false;
+
+ if (wi::eq_p (vr0_lb, vr0_ub))
+ cp3 = cp1;
+ else if (!wide_int_binop_overflow (cp3, code, vr0_ub, vr1_lb, sign,
+ overflow_undefined))
+ return false;
+
+ if (wi::eq_p (vr1_lb, vr1_ub))
+ cp2 = cp1;
+ else if (!wide_int_binop_overflow (cp2, code, vr0_lb, vr1_ub, sign,
+ overflow_undefined))
+ return false;
+
+ if (wi::eq_p (vr0_lb, vr0_ub))
+ cp4 = cp2;
+ else if (!wide_int_binop_overflow (cp4, code, vr0_ub, vr1_ub, sign,
+ overflow_undefined))
+ return false;
+
+ wide_int_range_min_max (res_lb, res_ub, cp1, cp2, cp3, cp4, sign);
+ return true;
+}
+
+/* Multiply two ranges when TYPE_OVERFLOW_WRAPS:
+
+ [RES_LB, RES_UB] = [MIN0, MAX0] * [MIN1, MAX1]
+
+ This is basically fancy code so we don't drop to varying with an
+ unsigned [-3,-1]*[-3,-1]. */
+
+bool
+wide_int_range_cross_product_wrapping (wide_int &res_lb,
+ wide_int &res_ub,
+ signop sign,
+ unsigned prec,
+ const wide_int &min0_,
+ const wide_int &max0_,
+ const wide_int &min1_,
+ const wide_int &max1_)
+{
+ /* This test requires 2*prec bits if both operands are signed and
+ 2*prec + 2 bits if either is not. Therefore, extend the values
+ using the sign of the result to PREC2. From here on out,
+ everthing is just signed math no matter what the input types
+ were. */
+ widest2_int min0 = widest2_int::from (min0_, sign);
+ widest2_int max0 = widest2_int::from (max0_, sign);
+ widest2_int min1 = widest2_int::from (min1_, sign);
+ widest2_int max1 = widest2_int::from (max1_, sign);
+ widest2_int sizem1 = wi::mask <widest2_int> (prec, false);
+ widest2_int size = sizem1 + 1;
+
+ /* Canonicalize the intervals. */
+ if (sign == UNSIGNED)
+ {
+ if (wi::ltu_p (size, min0 + max0))
+ {
+ min0 -= size;
+ max0 -= size;
+ }
+
+ if (wi::ltu_p (size, min1 + max1))
+ {
+ min1 -= size;
+ max1 -= size;
+ }
+ }
+
+ widest2_int prod0 = min0 * min1;
+ widest2_int prod1 = min0 * max1;
+ widest2_int prod2 = max0 * min1;
+ widest2_int prod3 = max0 * max1;
+
+ /* Sort the 4 products so that min is in prod0 and max is in
+ prod3. */
+ /* min0min1 > max0max1 */
+ if (prod0 > prod3)
+ std::swap (prod0, prod3);
+
+ /* min0max1 > max0min1 */
+ if (prod1 > prod2)
+ std::swap (prod1, prod2);
+
+ if (prod0 > prod1)
+ std::swap (prod0, prod1);
+
+ if (prod2 > prod3)
+ std::swap (prod2, prod3);
+
+ /* diff = max - min. */
+ prod2 = prod3 - prod0;
+ if (wi::geu_p (prod2, sizem1))
+ /* The range covers all values. */
+ return false;
+
+ res_lb = wide_int::from (prod0, prec, sign);
+ res_ub = wide_int::from (prod3, prec, sign);
+ return true;
+}
+
/* Helper to extract a value-range *VR for a multiplicative operation
*VR0 CODE *VR1. */
@@ -1135,10 +1257,6 @@ extract_range_from_multiplicative_op_1 (value_range *vr,
enum tree_code code,
value_range *vr0, value_range *vr1)
{
- enum value_range_type rtype;
- wide_int val, min, max;
- tree type;
-
/* 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
@@ -1162,79 +1280,25 @@ extract_range_from_multiplicative_op_1 (value_range *vr,
gcc_assert (vr0->type == VR_RANGE
&& vr0->type == vr1->type);
- rtype = vr0->type;
- type = TREE_TYPE (vr0->min);
- signop sgn = TYPE_SIGN (type);
+ tree type = TREE_TYPE (vr0->min);
+ wide_int res_lb, res_ub;
+ wide_int vr0_lb = wi::to_wide (vr0->min);
+ wide_int vr0_ub = wi::to_wide (vr0->max);
+ wide_int vr1_lb = wi::to_wide (vr1->min);
+ wide_int vr1_ub = wi::to_wide (vr1->max);
+ bool overflow_undefined = TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (vr0->min));
- /* Compute the 4 cross operations and their minimum and maximum value. */
- if (!vrp_int_const_binop (code, vr0->min, vr1->min, &val))
+ if (!wide_int_range_cross_product (res_lb, res_ub,
+ code, TYPE_SIGN (type),
+ vr0_lb, vr0_ub, vr1_lb, vr1_ub,
+ overflow_undefined))
{
set_value_range_to_varying (vr);
return;
}
- min = max = val;
-
- if (vr1->max != vr1->min)
- {
- if (!vrp_int_const_binop (code, vr0->min, vr1->max, &val))
- {
- set_value_range_to_varying (vr);
- return;
- }
- if (wi::lt_p (val, min, sgn))
- min = val;
- else if (wi::gt_p (val, max, sgn))
- max = val;
- }
-
- if (vr0->max != vr0->min)
- {
- if (!vrp_int_const_binop (code, vr0->max, vr1->min, &val))
- {
- set_value_range_to_varying (vr);
- return;
- }
- if (wi::lt_p (val, min, sgn))
- min = val;
- else if (wi::gt_p (val, max, sgn))
- max = val;
- }
-
- if (vr0->min != vr0->max && vr1->min != vr1->max)
- {
- if (!vrp_int_const_binop (code, vr0->max, vr1->max, &val))
- {
- set_value_range_to_varying (vr);
- return;
- }
- if (wi::lt_p (val, min, sgn))
- min = val;
- else if (wi::gt_p (val, max, sgn))
- max = val;
- }
-
- /* 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. */
- if (wi::gt_p (min, max, sgn))
- {
- set_value_range_to_varying (vr);
- return;
- }
-
- /* We punt for [-INF, +INF].
- We learn nothing when we have INF on both sides.
- Note that we do accept [-INF, -INF] and [+INF, +INF]. */
- if (wi::eq_p (min, wi::min_value (TYPE_PRECISION (type), sgn))
- && wi::eq_p (max, wi::max_value (TYPE_PRECISION (type), sgn)))
- {
- set_value_range_to_varying (vr);
- return;
- }
-
- set_value_range (vr, rtype,
- wide_int_to_tree (type, min),
- wide_int_to_tree (type, max), NULL);
+ set_value_range (vr, VR_RANGE,
+ wide_int_to_tree (type, res_lb),
+ wide_int_to_tree (type, res_ub), NULL);
}
/* For op & or | attempt to optimize:
@@ -1775,104 +1839,32 @@ extract_range_from_binary_expr_1 (value_range *vr,
}
else if (code == MULT_EXPR)
{
- /* Fancy code so that with unsigned, [-3,-1]*[-3,-1] does not
- drop to varying. This test requires 2*prec bits if both
- operands are signed and 2*prec + 2 bits if either is not. */
-
- signop sign = TYPE_SIGN (expr_type);
- unsigned int prec = TYPE_PRECISION (expr_type);
-
if (!range_int_cst_p (&vr0)
|| !range_int_cst_p (&vr1))
{
set_value_range_to_varying (vr);
return;
}
-
if (TYPE_OVERFLOW_WRAPS (expr_type))
{
- typedef FIXED_WIDE_INT (WIDE_INT_MAX_PRECISION * 2) vrp_int;
- typedef generic_wide_int
- <wi::extended_tree <WIDE_INT_MAX_PRECISION * 2> > vrp_int_cst;
- vrp_int sizem1 = wi::mask <vrp_int> (prec, false);
- vrp_int size = sizem1 + 1;
-
- /* Extend the values using the sign of the result to PREC2.
- From here on out, everthing is just signed math no matter
- what the input types were. */
- vrp_int min0 = vrp_int_cst (vr0.min);
- vrp_int max0 = vrp_int_cst (vr0.max);
- vrp_int min1 = vrp_int_cst (vr1.min);
- vrp_int max1 = vrp_int_cst (vr1.max);
- /* Canonicalize the intervals. */
- if (sign == UNSIGNED)
- {
- if (wi::ltu_p (size, min0 + max0))
- {
- min0 -= size;
- max0 -= size;
- }
-
- if (wi::ltu_p (size, min1 + max1))
- {
- min1 -= size;
- max1 -= size;
- }
- }
-
- vrp_int prod0 = min0 * min1;
- vrp_int prod1 = min0 * max1;
- vrp_int prod2 = max0 * min1;
- vrp_int prod3 = max0 * max1;
-
- /* Sort the 4 products so that min is in prod0 and max is in
- prod3. */
- /* min0min1 > max0max1 */
- if (prod0 > prod3)
- std::swap (prod0, prod3);
-
- /* min0max1 > max0min1 */
- if (prod1 > prod2)
- std::swap (prod1, prod2);
-
- if (prod0 > prod1)
- std::swap (prod0, prod1);
-
- if (prod2 > prod3)
- std::swap (prod2, prod3);
-
- /* diff = max - min. */
- prod2 = prod3 - prod0;
- if (wi::geu_p (prod2, sizem1))
+ signop sign = TYPE_SIGN (expr_type);
+ unsigned int prec = TYPE_PRECISION (expr_type);
+ wide_int res_lb, res_ub;
+ if (!wide_int_range_cross_product_wrapping (res_lb, res_ub,
+ sign, prec,
+ wi::to_wide (vr0.min),
+ wi::to_wide (vr0.max),
+ wi::to_wide (vr1.min),
+ wi::to_wide (vr1.max)))
{
- /* the range covers all values. */
set_value_range_to_varying (vr);
return;
}
-
- /* The following should handle the wrapping and selecting
- VR_ANTI_RANGE for us. */
- min = wide_int_to_tree (expr_type, prod0);
- max = wide_int_to_tree (expr_type, prod3);
+ min = wide_int_to_tree (expr_type, res_lb);
+ max = wide_int_to_tree (expr_type, res_ub);
set_and_canonicalize_value_range (vr, VR_RANGE, min, max, NULL);
return;
}
-
- /* 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
- op0 == 65536 and op1 == 65536 with their ranges both being
- ~[0,0] on a 32-bit machine, we would have op0 * op1 == 0, so
- 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;
}
diff --git a/gcc/tree-vrp.h b/gcc/tree-vrp.h
index 946e26e29b4..a48482680fe 100644
--- a/gcc/tree-vrp.h
+++ b/gcc/tree-vrp.h
@@ -102,6 +102,19 @@ extern bool vrp_val_is_min (const_tree);
extern bool vrp_val_is_max (const_tree);
extern void copy_value_range (value_range *, value_range *);
extern void set_value_range_to_value (value_range *, tree, bitmap);
+extern bool wide_int_range_cross_product (wide_int &res_lb, wide_int &res_ub,
+ enum tree_code code, signop sign,
+ const wide_int &, const wide_int &,
+ const wide_int &, const wide_int &,
+ bool overflow_undefined);
+extern bool wide_int_range_cross_product_wrapping (wide_int &res_lb,
+ wide_int &res_ub,
+ signop sign,
+ unsigned prec,
+ const wide_int &min0_,
+ const wide_int &max0_,
+ const wide_int &min1_,
+ const wide_int &max1_);
extern void extract_range_from_binary_expr_1 (value_range *, enum tree_code,
tree, value_range *,
value_range *);
diff --git a/gcc/tree.h b/gcc/tree.h
index 79b675025d9..d15f117b513 100644
--- a/gcc/tree.h
+++ b/gcc/tree.h
@@ -5416,6 +5416,11 @@ namespace wi
};
}
+/* Used to convert a tree to a widest2_int like this:
+ widest2_int foo = widest2_int_cst (some_tree). */
+typedef generic_wide_int <wi::extended_tree <WIDE_INT_MAX_PRECISION * 2> >
+ widest2_int_cst;
+
/* Refer to INTEGER_CST T as though it were a widest_int.
This function gives T's actual numerical value, influenced by the
diff --git a/gcc/wide-int.h b/gcc/wide-int.h
index cb5f9abffe2..9e0535b6be5 100644
--- a/gcc/wide-int.h
+++ b/gcc/wide-int.h
@@ -322,6 +322,9 @@ class wide_int_storage;
typedef generic_wide_int <wide_int_storage> wide_int;
typedef FIXED_WIDE_INT (ADDR_MAX_PRECISION) offset_int;
typedef FIXED_WIDE_INT (WIDE_INT_MAX_PRECISION) widest_int;
+/* Spelled out explicitly (rather than through FIXED_WIDE_INT)
+ so as not to confuse gengtype. */
+typedef generic_wide_int < fixed_wide_int_storage <WIDE_INT_MAX_PRECISION * 2> > widest2_int;
/* wi::storage_ref can be a reference to a primitive type,
so this is the conservatively-correct setting. */
