tree-vrp.c (abs_extent_range): Remove.

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

From-SVN: r263813

1 files changed, 54 insertions, 141 deletions

diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index ead19f1..735b364 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,