VRP: rewrite the division code (to handle corner cases including 0)
diff mbox series

Message ID e87874aa-bcbe-15bf-2a30-7dc694361850@redhat.com
State New
Headers show
Series
  • VRP: rewrite the division code (to handle corner cases including 0)
Related show

Commit Message

Aldy Hernandez Aug. 15, 2018, 1:33 a.m. UTC
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.

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.

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.

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.

(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?

Aldy

Comments

Richard Biener Aug. 21, 2018, 9:46 a.m. UTC | #1
On Wed, Aug 15, 2018 at 3:33 AM Aldy Hernandez <aldyh@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.

> 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).

+  /* 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.

> 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...

>
> 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
Jeff Law Aug. 21, 2018, 2:17 p.m. UTC | #2
On 08/21/2018 03:46 AM, Richard Biener wrote:
> 
> +  /* 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.
No strong opinions here, just a couple notes.

If we set the result for this to VR_UNDEFINED, then it'll naturally be
handled optimistically at PHI nodes, COND_EXPRs, etc.

We'd normally get that effect via path isolation when we turn the x / 0
into a trap and simplify the CFG appropriately.

However, using VR_UNDEFINED for division by zero in VRP captures the
effect earlier which is generally a good thing.

Jeff
Aldy Hernandez Aug. 21, 2018, 5:35 p.m. UTC | #3
On 08/21/2018 05:46 AM, Richard Biener wrote:
> On Wed, Aug 15, 2018 at 3:33 AM Aldy Hernandez <aldyh@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 &dividend_min, const wide_int &dividend_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 &dividend_min,
+				const wide_int &dividend_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 */
Richard Biener Aug. 23, 2018, 12:51 p.m. UTC | #4
On Tue, Aug 21, 2018 at 7:35 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>
>
>
> On 08/21/2018 05:46 AM, Richard Biener wrote:
> > On Wed, Aug 15, 2018 at 3:33 AM Aldy Hernandez <aldyh@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...

Good ;)

> >
> >> 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)?

Yes, overflow_wraps == !overflow_undefined (well, OK, not exactly - there's
also TYPE_OVERFLOW_TRAPS, but not for pointers).

Let's sort this out as a followup.  It somewhat felt odd / inconsistent.

I think the wide-int routines want to know whether the operation may
overflow or not and if it may then it simply assumes wrapping behavior.
When overflow is undefined or if it traps the overflow isn't observed
in the result ...

>
> >
> > +  /* 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;
>         }

... which means even for non-call-exceptions the actual _result_ of
a division by zero is UNDEFINED.  When an exception is thrown
we're just not reaching any consumer of the result.

> >
> >> 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 ;-).

;)

The patch is OK unchanged or with the division-by-zero changed to
VR_UNDEFINED unconditionally (you can also do/test that as followup,
but make sure to enable Ada for testing).

Thanks,
Richard.

> 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
Aldy Hernandez Aug. 23, 2018, 1:18 p.m. UTC | #5
On 08/23/2018 08:51 AM, Richard Biener wrote:
> On Tue, Aug 21, 2018 at 7:35 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>>
>>
>>
>> On 08/21/2018 05:46 AM, Richard Biener wrote:
>>> On Wed, Aug 15, 2018 at 3:33 AM Aldy Hernandez <aldyh@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...
> 
> Good ;)
> 
>>>
>>>> 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)?
> 
> Yes, overflow_wraps == !overflow_undefined (well, OK, not exactly - there's
> also TYPE_OVERFLOW_TRAPS, but not for pointers).
> 
> Let's sort this out as a followup.  It somewhat felt odd / inconsistent.

Ok, I'm drowning myself in changes here.  I've put this on my short-term 
todo list, and will revisit once the dust settles-- hopefully in a week.

> 
> I think the wide-int routines want to know whether the operation may
> overflow or not and if it may then it simply assumes wrapping behavior.
> When overflow is undefined or if it traps the overflow isn't observed
> in the result ...
> 
>>
>>>
>>> +  /* 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;
>>          }
> 
> ... which means even for non-call-exceptions the actual _result_ of
> a division by zero is UNDEFINED.  When an exception is thrown
> we're just not reaching any consumer of the result.
> 
>>>
>>>> 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 ;-).
> 
> ;)
> 
> The patch is OK unchanged or with the division-by-zero changed to
> VR_UNDEFINED unconditionally (you can also do/test that as followup,
> but make sure to enable Ada for testing).

Likewise.  I've added this to my list, and will revisit shortly.

Ada?  What's that?  Is that what I test right before I merge a branch 
with tons of changes into mainline? *hides in shame*

I'm committing as is.  Thanks.
Aldy
Aldy Hernandez Oct. 17, 2018, 10:20 a.m. UTC | #6
On 8/23/18 8:51 AM, Richard Biener wrote:
> On Tue, Aug 21, 2018 at 7:35 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>>
>>
>>
>> On 08/21/2018 05:46 AM, Richard Biener wrote:
>>> On Wed, Aug 15, 2018 at 3:33 AM Aldy Hernandez <aldyh@redhat.com> wrote:

>>> 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)?
> 
> Yes, overflow_wraps == !overflow_undefined (well, OK, not exactly - there's
> also TYPE_OVERFLOW_TRAPS, but not for pointers).
> 
> Let's sort this out as a followup.  It somewhat felt odd / inconsistent.
> 
> I think the wide-int routines want to know whether the operation may
> overflow or not and if it may then it simply assumes wrapping behavior.
> When overflow is undefined or if it traps the overflow isn't observed
> in the result ...

As promised, here is a patch merging the TYPE_OVERFLOW_UNDEFINED and 
TYPE_OVERFLOW_WRAPS flags in the wide_int_range* routines.

OK pending tests?

Aldy
commit dca640a3b3a018e42a852006ccaf09da3b0acaff
Author: Aldy Hernandez <aldyh@redhat.com>
Date:   Wed Oct 17 11:46:57 2018 +0200

            * tree-vrp.c (extract_range_from_multiplicative_op): Remove
            overflow wraps argument.
            (extract_range_from_binary_expr_1): Do not pass overflow wraps to
            wide_int_range_multiplicative_op.
            * wide-int-range.cc (wide_int_range_mult_wrapping): Remove
            overflow wraps argument.
            (wide_int_range_multiplicative_op): Same.
            (wide_int_range_lshift): Same.
            (wide_int_range_div): Same.
            * wide-int-range.h (wide_int_range_multiplicative_op): Same.
            (wide_int_range_lshift): Same.
            (wide_int_range_div): Same.

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 4768b9635f8..6cfaac1690d 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,18 @@
+2018-10-17  Aldy Hernandez  <aldyh@redhat.com>
+
+        * tree-vrp.c (extract_range_from_multiplicative_op): Remove
+	overflow wraps argument.
+        (extract_range_from_binary_expr_1): Do not pass overflow wraps to
+	wide_int_range_multiplicative_op.
+        * wide-int-range.cc (wide_int_range_mult_wrapping): Remove
+	overflow wraps argument.
+        (wide_int_range_multiplicative_op): Same.
+        (wide_int_range_lshift): Same.
+        (wide_int_range_div): Same.
+        * wide-int-range.h (wide_int_range_multiplicative_op): Same.
+        (wide_int_range_lshift): Same.
+        (wide_int_range_div): Same.
+
 2018-10-17  Aldy Hernandez  <aldyh@redhat.com>
 
 	* wide-int-range.h (wide_int_range_shift_undefined_p): Adjust to
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index c519613bb28..0a42da7005e 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -1003,13 +1003,12 @@ extract_range_from_multiplicative_op (value_range *vr,
   wide_int vr1_lb = wi::to_wide (vr1->min);
   wide_int vr1_ub = wi::to_wide (vr1->max);
   bool overflow_undefined = TYPE_OVERFLOW_UNDEFINED (type);
-  bool overflow_wraps = TYPE_OVERFLOW_WRAPS (type);
   unsigned prec = TYPE_PRECISION (type);
 
   if (wide_int_range_multiplicative_op (res_lb, res_ub,
-					 code, TYPE_SIGN (type), prec,
-					 vr0_lb, vr0_ub, vr1_lb, vr1_ub,
-					 overflow_undefined, overflow_wraps))
+					code, TYPE_SIGN (type), prec,
+					vr0_lb, vr0_ub, vr1_lb, vr1_ub,
+					overflow_undefined))
     set_and_canonicalize_value_range (vr, VR_RANGE,
 				      wide_int_to_tree (type, res_lb),
 				      wide_int_to_tree (type, res_ub), NULL);
@@ -1549,8 +1548,7 @@ extract_range_from_binary_expr_1 (value_range *vr,
 					 wi::to_wide (vr0.max),
 					 wi::to_wide (vr1.min),
 					 wi::to_wide (vr1.max),
-					 TYPE_OVERFLOW_UNDEFINED (expr_type),
-					 TYPE_OVERFLOW_WRAPS (expr_type)))
+					 TYPE_OVERFLOW_UNDEFINED (expr_type)))
 		{
 		  min = wide_int_to_tree (expr_type, res_lb);
 		  max = wide_int_to_tree (expr_type, res_ub);
@@ -1595,7 +1593,6 @@ extract_range_from_binary_expr_1 (value_range *vr,
 			       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);
diff --git a/gcc/wide-int-range.cc b/gcc/wide-int-range.cc
index a85fe9f9ad7..8978b5aecfd 100644
--- a/gcc/wide-int-range.cc
+++ b/gcc/wide-int-range.cc
@@ -268,7 +268,7 @@ wide_int_range_mult_wrapping (wide_int &res_lb,
 
    Return TRUE if we were able to perform the operation.
 
-   NOTE: If code is MULT_EXPR and TYPE_OVERFLOW_WRAPS, the resulting
+   NOTE: If code is MULT_EXPR and !TYPE_OVERFLOW_UNDEFINED, the resulting
    range must be canonicalized by the caller because its components
    may be swapped.  */
 
@@ -281,8 +281,7 @@ wide_int_range_multiplicative_op (wide_int &res_lb, wide_int &res_ub,
 				  const wide_int &vr0_ub,
 				  const wide_int &vr1_lb,
 				  const wide_int &vr1_ub,
-				  bool overflow_undefined,
-				  bool overflow_wraps)
+				  bool overflow_undefined)
 {
   /* Multiplications, divisions and shifts are a bit tricky to handle,
      depending on the mix of signs we have in the two ranges, we
@@ -296,7 +295,7 @@ wide_int_range_multiplicative_op (wide_int &res_lb, wide_int &res_ub,
      (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.  */
-  if (code == MULT_EXPR && overflow_wraps)
+  if (code == MULT_EXPR && !overflow_undefined)
     return wide_int_range_mult_wrapping (res_lb, res_ub,
 					 sign, prec,
 					 vr0_lb, vr0_ub, vr1_lb, vr1_ub);
@@ -320,7 +319,7 @@ wide_int_range_lshift (wide_int &res_lb, wide_int &res_ub,
 		       signop sign, unsigned prec,
 		       const wide_int &vr0_lb, const wide_int &vr0_ub,
 		       const wide_int &vr1_lb, const wide_int &vr1_ub,
-		       bool overflow_undefined, bool overflow_wraps)
+		       bool overflow_undefined)
 {
   /* Transform left shifts by constants into multiplies.  */
   if (wi::eq_p (vr1_lb, vr1_ub))
@@ -330,8 +329,7 @@ wide_int_range_lshift (wide_int &res_lb, wide_int &res_ub,
       return wide_int_range_multiplicative_op (res_lb, res_ub,
 					       MULT_EXPR, sign, prec,
 					       vr0_lb, vr0_ub, tmp, tmp,
-					       overflow_undefined,
-					       /*overflow_wraps=*/true);
+					       /*overflow_undefined=*/false);
     }
 
   int overflow_pos = prec;
@@ -387,8 +385,7 @@ wide_int_range_lshift (wide_int &res_lb, wide_int &res_ub,
 					     LSHIFT_EXPR, sign, prec,
 					     vr0_lb, vr0_ub,
 					     vr1_lb, vr1_ub,
-					     overflow_undefined,
-					     overflow_wraps);
+					     overflow_undefined);
   return false;
 }
 
@@ -785,7 +782,6 @@ wide_int_range_div (wide_int &wmin, wide_int &wmax,
 		    const wide_int &dividend_min, const wide_int &dividend_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)
 {
@@ -796,8 +792,7 @@ wide_int_range_div (wide_int &wmin, wide_int &wmax,
     return wide_int_range_multiplicative_op (wmin, wmax, code, sign, prec,
 					     dividend_min, dividend_max,
 					     divisor_min, divisor_max,
-					     overflow_undefined,
-					     overflow_wraps);
+					     overflow_undefined);
 
   /* If flag_non_call_exceptions, we must not eliminate a division
      by zero.  */
@@ -818,8 +813,7 @@ wide_int_range_div (wide_int &wmin, wide_int &wmax,
 					     code, sign, prec,
 					     dividend_min, dividend_max,
 					     divisor_min, wi::minus_one (prec),
-					     overflow_undefined,
-					     overflow_wraps))
+					     overflow_undefined))
 	return false;
       extra_range_p = true;
     }
@@ -831,8 +825,7 @@ wide_int_range_div (wide_int &wmin, wide_int &wmax,
 					     code, sign, prec,
 					     dividend_min, dividend_max,
 					     wi::one (prec), divisor_max,
-					     overflow_undefined,
-					     overflow_wraps))
+					     overflow_undefined))
 	return false;
     }
   else
diff --git a/gcc/wide-int-range.h b/gcc/wide-int-range.h
index 589fdea4df6..f8b7e7f47a2 100644
--- a/gcc/wide-int-range.h
+++ b/gcc/wide-int-range.h
@@ -42,14 +42,12 @@ extern bool wide_int_range_multiplicative_op (wide_int &res_lb,
 					      const wide_int &vr0_ub,
 					      const wide_int &vr1_lb,
 					      const wide_int &vr1_ub,
-					      bool overflow_undefined,
-					      bool overflow_wraps);
+					      bool overflow_undefined);
 extern bool wide_int_range_lshift (wide_int &res_lb, wide_int &res_ub,
 				   signop sign, unsigned prec,
 				   const wide_int &, const wide_int &,
 				   const wide_int &, const wide_int &,
-				   bool overflow_undefined,
-				   bool overflow_wraps);
+				   bool overflow_undefined);
 extern void wide_int_range_set_zero_nonzero_bits (signop,
 						  const wide_int &lb,
 						  const wide_int &ub,
@@ -124,7 +122,6 @@ extern bool wide_int_range_div (wide_int &wmin, wide_int &wmax,
 				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);
Richard Biener Oct. 17, 2018, 10:51 a.m. UTC | #7
On Wed, Oct 17, 2018 at 12:20 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>
>
>
> On 8/23/18 8:51 AM, Richard Biener wrote:
> > On Tue, Aug 21, 2018 at 7:35 PM Aldy Hernandez <aldyh@redhat.com> wrote:
> >>
> >>
> >>
> >> On 08/21/2018 05:46 AM, Richard Biener wrote:
> >>> On Wed, Aug 15, 2018 at 3:33 AM Aldy Hernandez <aldyh@redhat.com> wrote:
>
> >>> 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)?
> >
> > Yes, overflow_wraps == !overflow_undefined (well, OK, not exactly - there's
> > also TYPE_OVERFLOW_TRAPS, but not for pointers).
> >
> > Let's sort this out as a followup.  It somewhat felt odd / inconsistent.
> >
> > I think the wide-int routines want to know whether the operation may
> > overflow or not and if it may then it simply assumes wrapping behavior.
> > When overflow is undefined or if it traps the overflow isn't observed
> > in the result ...
>
> As promised, here is a patch merging the TYPE_OVERFLOW_UNDEFINED and
> TYPE_OVERFLOW_WRAPS flags in the wide_int_range* routines.
>
> OK pending tests?

OK.

Richard.

> Aldy

Patch
diff mbox series

gcc/

	* tree-vrp.c (abs_extent_range): Remove.
	(range_includes_zero_p): Move further up in file.
	(range_is_nonnull): Make it return true if VR does not contain 0,
	not just if VR is ~[0,0].
	(extract_range_into_wide_ints): Pass wide ints by reference.
	(extract_range_from_binary_expr_1): Handle the case where
	POINTER_PLUS_EXPR's pointer is known to be non-zero.
	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 d553a254878..adfdc01f2d1 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
@@ -538,14 +502,34 @@  vrp_bitmap_equal_p (const_bitmap b1, const_bitmap b2)
 	      && bitmap_equal_p (b1, b2)));
 }
 
-/* Return true if VR is ~[0, 0].  */
+
+/* Return 1 if [MIN, MAX] includes the value zero, 0 if it does not
+   include the value zero, -2 if we cannot tell.  */
+
+int
+range_includes_zero_p (tree min, tree max)
+{
+  tree zero = build_int_cst (TREE_TYPE (min), 0);
+  return value_inside_range (zero, min, max);
+}
+
+/* Return true if VR does not contain 0.  */
 
 bool
 range_is_nonnull (value_range *vr)
 {
-  return vr->type == VR_ANTI_RANGE
-	 && integer_zerop (vr->min)
-	 && integer_zerop (vr->max);
+  if (vr->type == VR_VARYING
+      || vr->type == VR_UNDEFINED
+      || TREE_CODE (vr->min) != INTEGER_CST
+      || TREE_CODE (vr->max) != INTEGER_CST)
+    return false;
+  if (vr->type == VR_RANGE)
+    return !range_includes_zero_p (vr->min, vr->max);
+  /* ~[0,0] is not the only non-null. We could also have ~[0,5].  */
+  else if (vr->type == VR_ANTI_RANGE)
+    return range_includes_zero_p (vr->min, vr->max);
+  else
+    gcc_unreachable ();
 }
 
 
@@ -915,17 +899,6 @@  value_ranges_intersect_p (value_range *vr0, value_range *vr1)
   return true;
 }
 
-
-/* Return 1 if [MIN, MAX] includes the value zero, 0 if it does not
-   include the value zero, -2 if we cannot tell.  */
-
-int
-range_includes_zero_p (tree min, tree max)
-{
-  tree zero = build_int_cst (TREE_TYPE (min), 0);
-  return value_inside_range (zero, min, max);
-}
-
 /* Return true if *VR is know to only contain nonnegative values.  */
 
 static inline bool
@@ -1034,17 +1007,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);
     }
 }
 
@@ -1439,7 +1412,10 @@  extract_range_from_binary_expr_1 (value_range *vr,
       && code != RSHIFT_EXPR
       && (vr0.type == VR_VARYING
 	  || vr1.type == VR_VARYING
-	  || vr0.type != vr1.type
+	  || (vr0.type != vr1.type
+	      /* We can handle POINTER_PLUS_EXPR(~[0,0], [x,y]) below,
+		 even though we have differing range kinds.  */
+	      && code != POINTER_PLUS_EXPR)
 	  || symbolic_range_p (&vr0)
 	  || symbolic_range_p (&vr1)))
     {
@@ -1694,109 +1670,38 @@  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))
-	{
-	  /* 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);
-	    }
-	  else
-	    {
-	      set_value_range_to_varying (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))
+      wide_int dividend_min, dividend_max, divisor_min, divisor_max;
+      wide_int wmin, wmax, extra_min, extra_max;
+      bool extra_range_p;
+      /* First, normalize ranges into constants we can handle.  Note
+	 that VR_ANTI_RANGE's of constants were already normalized
+	 before arriving here.  */
+      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)
     {
@@ -1807,8 +1712,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);
@@ -1829,8 +1734,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,
diff --git a/gcc/wide-int-range.cc b/gcc/wide-int-range.cc
index 3491d89664d..bfc574c42e7 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"
 
@@ -605,3 +606,75 @@  wide_int_range_trunc_mod (wide_int &wmin, wide_int &wmax,
     tmp = wi::zero (prec);
   wmax = wi::min (wmax, tmp, sign);
 }
+
+/* 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 &dividend_min, const wide_int &dividend_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 4421bc8aeca..541a73c6172 100644
--- a/gcc/wide-int-range.h
+++ b/gcc/wide-int-range.h
@@ -94,6 +94,17 @@  extern void wide_int_range_trunc_mod (wide_int &wmin, wide_int &wmax,
 				      const wide_int &vr0_max,
 				      const wide_int &vr1_min,
 				      const wide_int &vr1_max);
+extern bool wide_int_range_div (wide_int &wmin, wide_int &wmax,
+				enum tree_code code,
+				signop sign, unsigned prec,
+				const wide_int &dividend_min,
+				const wide_int &dividend_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.  */
 
@@ -112,4 +123,22 @@  wide_int_range_shift_undefined_p (signop sign, unsigned prec,
   return wi::lt_p (min, 0, sign) || wi::ge_p (max, prec, sign);
 }
 
+/* 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 */