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

[Aldy Hernandez <aldyh at redhat dot com>]

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

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