On 08/21/2018 05:46 AM, Richard Biener wrote:
On Wed, Aug 15, 2018 at 3:33 AM Aldy Hernandez <al...@redhat.com> wrote:
Howdy!
In auditing the *_DIV_EXPR code I noticed that we were really botching
some divisions where the divisor included 0.
Particularly interesting was that we were botching something as simple
as dividing by [0,0]. We were also incorrectly calculating things like
[-2,-2] / [0, 5555], where we should have removed the 0 from the divisor.
Also, the symbolic special casing could be handled by just treating
symbolic ranges as [-MIN, +MAX] and letting the common code handle then.
Similarly for anti ranges, which actually never happen except for the
constant case, since they've been normalized earlier.
Note we also have "mixed" symbolic (anti-)ranges like [0, a]. I don't think
we handled those before but extract_range_to_wide_ints may be improved
to handle them. Likewise ranges_from_anti_range, ~[0, a] -> [-INF,
-1] u [a+1, +INF]
though not sure if that helps any case in practice.
I have added comments for a future improvements. Perhaps after the dust
settles...
All in all, it was much easier to normalize all the symbolic ranges and
treat everything generically by performing the division in two chunks...
the negative numbers and the (non-zero) positive numbers. And finally,
unioning the results. This makes everything much simpler to read with
minimal special casing.
Yeah, nice work. Few comments:
+ TYPE_OVERFLOW_UNDEFINED (expr_type),
+ TYPE_OVERFLOW_WRAPS (expr_type),
we no longer have the third state !UNDEFINED && !WRAPS so I suggest
to eliminate one for the other (just pass TYPE_OVERFLOW_UNDEFINED).
I'm confused. Then what shall I pass to
wide_int_range_multiplicative_op within wide_int_range_div? Are you
expecting to pass overflow_undefined to both the overflow_undefined and
overflow_wraps arguments in multiplicative_op? Or are you saying I
should get rid of overflow_wraps in both wide_int_range_div and
wide_int_range_multiplicative_op (plus all other users of
w_i_r_multiplicative_op)?
+ /* If we're definitely dividing by zero, there's nothing to do. */
+ if (wide_int_range_zero_p (divisor_min, divisor_max, prec))
+ return false;
I know we didn't do this before but for x / 0 we should compute UNDEFINED
as range. With the current interfacing this special case would require handling
in the non-wide-int caller.
I've added the following, since I'm unsure whether we should return
undefined or varying for non_call_exceptions. What do you think?
/* Special case explicit division by zero as undefined. */
if (range_is_null (&vr1))
{
/* However, we must not eliminate a division by zero if
flag_non_call_exceptions. */
if (cfun->can_throw_non_call_exceptions)
set_value_range_to_varying (vr);
else
set_value_range_to_undefined (vr);
return;
}
Finally, my apologies for including a tiny change to the
POINTER_PLUS_EXPR handling code as well. It came about the same set of
auditing tests.
Bah, please split up things here ;) I've done a related change there
yesterday...
Ughh... Will do. I figured someone would complain ;-).
Aldy
It turns out we can handle POINTER_PLUS_EXPR(~[0,0], [X,Y]) without
bailing as VR_VARYING in extract_range_from_binary_expr_1. In doing so,
I also noticed that ~[0,0] is not the only non-null. We could also have
~[0,2] and still know that the pointer is not zero. I have adjusted
range_is_nonnull accordingly.
But there are other consumers and it would have been better to
change range_includes_zero_p to do the natural thing (get a VR) and
then remove range_is_nonnull as redundant if possible.
(Yes, we can get something like ~[0,2] for a pointer for things like the
following in libgcc:
if (segment_arg == (void *) (uintptr_type) 1)
...
else if (segment_arg == (void *) (uintptr_type) 2)
return NULL;
else if (segment_arg != NULL)
segment = (struct stack_segment *) segment_arg;
)
BTW, I am still not happy with the entire interface to wide-int-range.*,
and have another pending patchset that will simplify things even
further. I think everyone will be pleased ;-).
OK pending another round of tests?
The division related changes are OK, please split out & improve the nonnull
parts (and the POINTER_PLUS_EXPR check is already in as variant).
Richard.
Aldy
gcc/
* tree-vrp.c (abs_extent_range): Remove.
(extract_range_into_wide_ints): Pass wide ints by reference.
(extract_range_from_binary_expr_1): Rewrite the *DIV_EXPR code.
Pass wide ints by reference in all calls to
extract_range_into_wide_ints.
* wide-int-range.cc (wide_int_range_div): New.
* wide-int-range.h (wide_int_range_div): New.
(wide_int_range_includes_zero_p): New.
(wide_int_range_zero_p): New.
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 24e089b019b..c563ab1225a 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -478,42 +478,6 @@ set_value_range_to_null (value_range *vr, tree type)
set_value_range_to_value (vr, build_int_cst (type, 0), vr->equiv);
}
-
-/* If abs (min) < abs (max), set VR to [-max, max], if
- abs (min) >= abs (max), set VR to [-min, min]. */
-
-static void
-abs_extent_range (value_range *vr, tree min, tree max)
-{
- int cmp;
-
- gcc_assert (TREE_CODE (min) == INTEGER_CST);
- gcc_assert (TREE_CODE (max) == INTEGER_CST);
- gcc_assert (INTEGRAL_TYPE_P (TREE_TYPE (min)));
- gcc_assert (!TYPE_UNSIGNED (TREE_TYPE (min)));
- min = fold_unary (ABS_EXPR, TREE_TYPE (min), min);
- max = fold_unary (ABS_EXPR, TREE_TYPE (max), max);
- if (TREE_OVERFLOW (min) || TREE_OVERFLOW (max))
- {
- set_value_range_to_varying (vr);
- return;
- }
- cmp = compare_values (min, max);
- if (cmp == -1)
- min = fold_unary (NEGATE_EXPR, TREE_TYPE (min), max);
- else if (cmp == 0 || cmp == 1)
- {
- max = min;
- min = fold_unary (NEGATE_EXPR, TREE_TYPE (min), min);
- }
- else
- {
- set_value_range_to_varying (vr);
- return;
- }
- set_and_canonicalize_value_range (vr, VR_RANGE, min, max, NULL);
-}
-
/* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */
bool
@@ -997,6 +961,9 @@ ranges_from_anti_range (value_range *ar,
vr0->type = VR_UNDEFINED;
vr1->type = VR_UNDEFINED;
+ /* As a future improvement, we could handle ~[0, A] as: [-INF, -1] U
+ [A+1, +INF]. Not sure if this helps in practice, though. */
+
if (ar->type != VR_ANTI_RANGE
|| TREE_CODE (ar->min) != INTEGER_CST
|| TREE_CODE (ar->max) != INTEGER_CST
@@ -1034,17 +1001,17 @@ ranges_from_anti_range (value_range *ar,
static void inline
extract_range_into_wide_ints (value_range *vr,
signop sign, unsigned prec,
- wide_int *wmin, wide_int *wmax)
+ wide_int &wmin, wide_int &wmax)
{
if (range_int_cst_p (vr))
{
- *wmin = wi::to_wide (vr->min);
- *wmax = wi::to_wide (vr->max);
+ wmin = wi::to_wide (vr->min);
+ wmax = wi::to_wide (vr->max);
}
else
{
- *wmin = wi::min_value (prec, sign);
- *wmax = wi::max_value (prec, sign);
+ wmin = wi::min_value (prec, sign);
+ wmax = wi::max_value (prec, sign);
}
}
@@ -1597,8 +1564,8 @@ extract_range_from_binary_expr_1 (value_range *vr,
wide_int wmin, wmax;
wide_int vr0_min, vr0_max;
wide_int vr1_min, vr1_max;
- extract_range_into_wide_ints (&vr0, sign, prec, &vr0_min, &vr0_max);
- extract_range_into_wide_ints (&vr1, sign, prec, &vr1_min, &vr1_max);
+ extract_range_into_wide_ints (&vr0, sign, prec, vr0_min, vr0_max);
+ extract_range_into_wide_ints (&vr1, sign, prec, vr1_min, vr1_max);
if (wide_int_range_min_max (wmin, wmax, code, sign, prec,
vr0_min, vr0_max, vr1_min, vr1_max))
set_value_range (vr, VR_RANGE,
@@ -1668,109 +1635,55 @@ extract_range_from_binary_expr_1 (value_range *vr,
|| code == EXACT_DIV_EXPR
|| code == ROUND_DIV_EXPR)
{
- if (vr0.type != VR_RANGE || symbolic_range_p (&vr0))
+ wide_int dividend_min, dividend_max, divisor_min, divisor_max;
+ wide_int wmin, wmax, extra_min, extra_max;
+ bool extra_range_p;
+
+ /* Special case explicit division by zero as undefined. */
+ if (range_is_null (&vr1))
{
- /* For division, if op1 has VR_RANGE but op0 does not, something
- can be deduced just from that range. Say [min, max] / [4, max]
- gives [min / 4, max / 4] range. */
- if (vr1.type == VR_RANGE
- && !symbolic_range_p (&vr1)
- && range_includes_zero_p (vr1.min, vr1.max) == 0)
- {
- vr0.type = type = VR_RANGE;
- vr0.min = vrp_val_min (expr_type);
- vr0.max = vrp_val_max (expr_type);
- }
+ /* However, we must not eliminate a division by zero if
+ flag_non_call_exceptions. */
+ if (cfun->can_throw_non_call_exceptions)
+ set_value_range_to_varying (vr);
else
- {
- set_value_range_to_varying (vr);
- return;
- }
+ set_value_range_to_undefined (vr);
+ return;
}
- /* 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
- || range_includes_zero_p (vr1.min, vr1.max) != 0))
+ /* First, normalize ranges into constants we can handle. Note
+ that VR_ANTI_RANGE's of constants were already normalized
+ before arriving here.
+
+ NOTE: As a future improvement, we may be able to do better
+ with mixed symbolic (anti-)ranges like [0, A]. See note in
+ ranges_from_anti_range. */
+ extract_range_into_wide_ints (&vr0, sign, prec,
+ dividend_min, dividend_max);
+ extract_range_into_wide_ints (&vr1, sign, prec,
+ divisor_min, divisor_max);
+ if (!wide_int_range_div (wmin, wmax, code, sign, prec,
+ dividend_min, dividend_max,
+ divisor_min, divisor_max,
+ TYPE_OVERFLOW_UNDEFINED (expr_type),
+ TYPE_OVERFLOW_WRAPS (expr_type),
+ extra_range_p, extra_min, extra_max))
{
set_value_range_to_varying (vr);
return;
}
-
- /* 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
- || range_includes_zero_p (vr1.min, vr1.max) != 0))
- {
- tree zero = build_int_cst (TREE_TYPE (vr0.min), 0);
- int cmp;
-
- min = NULL_TREE;
- max = NULL_TREE;
- if (TYPE_UNSIGNED (expr_type)
- || value_range_nonnegative_p (&vr1))
- {
- /* For unsigned division or when divisor is known
- to be non-negative, the range has to cover
- all numbers from 0 to max for positive max
- and all numbers from min to 0 for negative min. */
- cmp = compare_values (vr0.max, zero);
- if (cmp == -1)
- {
- /* When vr0.max < 0, vr1.min != 0 and value
- ranges for dividend and divisor are available. */
- if (vr1.type == VR_RANGE
- && !symbolic_range_p (&vr0)
- && !symbolic_range_p (&vr1)
- && compare_values (vr1.min, zero) != 0)
- max = int_const_binop (code, vr0.max, vr1.min);
- else
- max = zero;
- }
- else if (cmp == 0 || cmp == 1)
- max = vr0.max;
- else
- type = VR_VARYING;
- cmp = compare_values (vr0.min, zero);
- if (cmp == 1)
- {
- /* For unsigned division when value ranges for dividend
- and divisor are available. */
- if (vr1.type == VR_RANGE
- && !symbolic_range_p (&vr0)
- && !symbolic_range_p (&vr1)
- && compare_values (vr1.max, zero) != 0)
- min = int_const_binop (code, vr0.min, vr1.max);
- else
- min = zero;
- }
- else if (cmp == 0 || cmp == -1)
- min = vr0.min;
- else
- type = VR_VARYING;
- }
- else
- {
- /* Otherwise the range is -max .. max or min .. -min
- depending on which bound is bigger in absolute value,
- as the division can change the sign. */
- abs_extent_range (vr, vr0.min, vr0.max);
- return;
- }
- if (type == VR_VARYING)
- {
- set_value_range_to_varying (vr);
- return;
- }
- }
- else if (range_int_cst_p (&vr0) && range_int_cst_p (&vr1))
+ set_value_range (vr, VR_RANGE,
+ wide_int_to_tree (expr_type, wmin),
+ wide_int_to_tree (expr_type, wmax), NULL);
+ if (extra_range_p)
{
- extract_range_from_multiplicative_op (vr, code, &vr0, &vr1);
- return;
+ value_range extra_range = VR_INITIALIZER;
+ set_value_range (&extra_range, VR_RANGE,
+ wide_int_to_tree (expr_type, extra_min),
+ wide_int_to_tree (expr_type, extra_max), NULL);
+ vrp_meet (vr, &extra_range);
}
+ return;
}
else if (code == TRUNC_MOD_EXPR)
{
@@ -1781,8 +1694,8 @@ extract_range_from_binary_expr_1 (value_range *vr,
}
wide_int wmin, wmax, tmp;
wide_int vr0_min, vr0_max, vr1_min, vr1_max;
- extract_range_into_wide_ints (&vr0, sign, prec, &vr0_min, &vr0_max);
- extract_range_into_wide_ints (&vr1, sign, prec, &vr1_min, &vr1_max);
+ extract_range_into_wide_ints (&vr0, sign, prec, vr0_min, vr0_max);
+ extract_range_into_wide_ints (&vr1, sign, prec, vr1_min, vr1_max);
wide_int_range_trunc_mod (wmin, wmax, sign, prec,
vr0_min, vr0_max, vr1_min, vr1_max);
min = wide_int_to_tree (expr_type, wmin);
@@ -1803,8 +1716,8 @@ extract_range_from_binary_expr_1 (value_range *vr,
&may_be_nonzero0, &must_be_nonzero0);
vrp_set_zero_nonzero_bits (expr_type, &vr1,
&may_be_nonzero1, &must_be_nonzero1);
- extract_range_into_wide_ints (&vr0, sign, prec, &vr0_min, &vr0_max);
- extract_range_into_wide_ints (&vr1, sign, prec, &vr1_min, &vr1_max);
+ extract_range_into_wide_ints (&vr0, sign, prec, vr0_min, vr0_max);
+ extract_range_into_wide_ints (&vr1, sign, prec, vr1_min, vr1_max);
if (code == BIT_AND_EXPR)
{
if (wide_int_range_bit_and (wmin, wmax, sign, prec,
@@ -2033,7 +1946,7 @@ extract_range_from_unary_expr (value_range *vr,
}
wide_int wmin, wmax;
wide_int vr0_min, vr0_max;
- extract_range_into_wide_ints (&vr0, sign, prec, &vr0_min, &vr0_max);
+ extract_range_into_wide_ints (&vr0, sign, prec, vr0_min, vr0_max);
if (wide_int_range_abs (wmin, wmax, sign, prec, vr0_min, vr0_max,
TYPE_OVERFLOW_UNDEFINED (type)))
set_value_range (vr, VR_RANGE,
diff --git a/gcc/wide-int-range.cc b/gcc/wide-int-range.cc
index a202b5fd503..cbc71c25cfe 100644
--- a/gcc/wide-int-range.cc
+++ b/gcc/wide-int-range.cc
@@ -21,6 +21,7 @@ along with GCC; see the file COPYING3. If not see
#include "system.h"
#include "coretypes.h"
#include "tree.h"
+#include "function.h"
#include "fold-const.h"
#include "wide-int-range.h"
@@ -663,3 +664,75 @@ wide_int_range_abs (wide_int &min, wide_int &max,
return false;
return true;
}
+
+/* Calculate a division operation on two ranges and store the result in
+ [WMIN, WMAX] U [EXTRA_MIN, EXTRA_MAX].
+
+ If EXTRA_RANGE_P is set upon return, EXTRA_MIN/EXTRA_MAX hold
+ meaningful information, otherwise they should be ignored.
+
+ Return TRUE if we were able to successfully calculate the new range. */
+
+bool
+wide_int_range_div (wide_int &wmin, wide_int &wmax,
+ tree_code code, signop sign, unsigned prec,
+ const wide_int ÷nd_min, const wide_int ÷nd_max,
+ const wide_int &divisor_min, const wide_int &divisor_max,
+ bool overflow_undefined,
+ bool overflow_wraps,
+ bool &extra_range_p,
+ wide_int &extra_min, wide_int &extra_max)
+{
+ extra_range_p = false;
+
+ /* If we know we won't divide by zero, just do the division. */
+ if (!wide_int_range_includes_zero_p (divisor_min, divisor_max, sign))
+ {
+ wide_int_range_multiplicative_op (wmin, wmax, code, sign, prec,
+ dividend_min, dividend_max,
+ divisor_min, divisor_max,
+ overflow_undefined,
+ overflow_wraps);
+ return true;
+ }
+
+ /* If flag_non_call_exceptions, we must not eliminate a division
+ by zero. */
+ if (cfun->can_throw_non_call_exceptions)
+ return false;
+
+ /* If we're definitely dividing by zero, there's nothing to do. */
+ if (wide_int_range_zero_p (divisor_min, divisor_max, prec))
+ return false;
+
+ /* Perform the division in 2 parts, [LB, -1] and [1, UB],
+ which will skip any division by zero.
+
+ First divide by the negative numbers, if any. */
+ if (wi::neg_p (divisor_min, sign))
+ {
+ if (!wide_int_range_multiplicative_op (wmin, wmax,
+ code, sign, prec,
+ dividend_min, dividend_max,
+ divisor_min, wi::minus_one (prec),
+ overflow_undefined,
+ overflow_wraps))
+ return false;
+ extra_range_p = true;
+ }
+ /* Then divide by the non-zero positive numbers, if any. */
+ if (wi::gt_p (divisor_max, wi::zero (prec), sign))
+ {
+ if (!wide_int_range_multiplicative_op (extra_range_p ? extra_min : wmin,
+ extra_range_p ? extra_max : wmax,
+ code, sign, prec,
+ dividend_min, dividend_max,
+ wi::one (prec), divisor_max,
+ overflow_undefined,
+ overflow_wraps))
+ return false;
+ }
+ else
+ extra_range_p = false;
+ return true;
+}
diff --git a/gcc/wide-int-range.h b/gcc/wide-int-range.h
index 41198e05b13..427ef34c6b4 100644
--- a/gcc/wide-int-range.h
+++ b/gcc/wide-int-range.h
@@ -99,6 +99,17 @@ extern bool wide_int_range_abs (wide_int &min, wide_int &max,
const wide_int &vr0_min,
const wide_int &vr0_max,
bool overflow_undefined);
+extern bool wide_int_range_div (wide_int &wmin, wide_int &wmax,
+ enum tree_code code,
+ signop sign, unsigned prec,
+ const wide_int ÷nd_min,
+ const wide_int ÷nd_max,
+ const wide_int &divisor_min,
+ const wide_int &divisor_max,
+ bool overflow_undefined,
+ bool overflow_wraps,
+ bool &extra_range_p,
+ wide_int &extra_min, wide_int &extra_max);
/* Return TRUE if shifting by range [MIN, MAX] is undefined behavior. */
@@ -137,4 +148,22 @@ wide_int_range_min_max (wide_int &min, wide_int &max,
return true;
}
+/* Return TRUE if 0 is within [WMIN, WMAX]. */
+
+inline bool
+wide_int_range_includes_zero_p (const wide_int &wmin, const wide_int &wmax,
+ signop sign)
+{
+ return wi::le_p (wmin, 0, sign) && wi::ge_p (wmax, 0, sign);
+}
+
+/* Return TRUE if [WMIN, WMAX] is the singleton 0. */
+
+inline bool
+wide_int_range_zero_p (const wide_int &wmin, const wide_int &wmax,
+ unsigned prec)
+{
+ return wmin == wmax && wi::eq_p (wmin, wi::zero (prec));
+}
+
#endif /* GCC_WIDE_INT_RANGE_H */
