Move all wide_int_range* functions into wide-int-range.[ch]
diff mbox series

Message ID 40b06768-c570-78e4-63c5-b63c46a0e393@redhat.com
State New
Headers show
Series
  • Move all wide_int_range* functions into wide-int-range.[ch]
Related show

Commit Message

Aldy Hernandez Aug. 1, 2018, 7:39 p.m. UTC
This is actually an obvious patch, but I'm not committing it just in 
case you'd prefer another name for the files.

OK pending bootstrap?

Aldy

Comments

David Malcolm Aug. 1, 2018, 9:19 p.m. UTC | #1
On Wed, 2018-08-01 at 15:39 -0400, Aldy Hernandez wrote:
> This is actually an obvious patch, but I'm not committing it just in 
> case you'd prefer another name for the files.

BTW, is it our policy that new gcc C++ source files should have a .cc
extension?

> OK pending bootstrap?
> 
> Aldy
Jeff Law Aug. 2, 2018, 6:07 p.m. UTC | #2
On 08/01/2018 03:19 PM, David Malcolm wrote:
> On Wed, 2018-08-01 at 15:39 -0400, Aldy Hernandez wrote:
>> This is actually an obvious patch, but I'm not committing it just in 
>> case you'd prefer another name for the files.
> 
> BTW, is it our policy that new gcc C++ source files should have a .cc
> extension?
I believe so.
jeff
Aldy Hernandez Aug. 2, 2018, 6:23 p.m. UTC | #3
On 08/02/2018 02:07 PM, Jeff Law wrote:
> On 08/01/2018 03:19 PM, David Malcolm wrote:
>> On Wed, 2018-08-01 at 15:39 -0400, Aldy Hernandez wrote:
>>> This is actually an obvious patch, but I'm not committing it just in
>>> case you'd prefer another name for the files.
>>
>> BTW, is it our policy that new gcc C++ source files should have a .cc
>> extension?
> I believe so.
> jeff
> 

I did not know that.  I'm happy to rename it to .cc.

OK with that change ;-)?

Aldy
Aldy Hernandez Aug. 2, 2018, 6:50 p.m. UTC | #4
On 08/02/2018 02:23 PM, Aldy Hernandez wrote:
> 
> 
> On 08/02/2018 02:07 PM, Jeff Law wrote:
>> On 08/01/2018 03:19 PM, David Malcolm wrote:
>>> On Wed, 2018-08-01 at 15:39 -0400, Aldy Hernandez wrote:
>>>> This is actually an obvious patch, but I'm not committing it just in
>>>> case you'd prefer another name for the files.
>>>
>>> BTW, is it our policy that new gcc C++ source files should have a .cc
>>> extension?
>> I believe so.
>> jeff
>>
> 
> I did not know that.  I'm happy to rename it to .cc.
> 
> OK with that change ;-)?

Like this, btw.

As promised, I also moved wide_int_range_shift_undefined_p() into an 
inlined function in the header file.

Aldy
gcc/

	* Makefile.in (wide-int-range.o): New.
	* tree-vrp.c: Move all the wide_int_* functions to...
	* wide-int-range.cc: ...here.
	* tree-vrp.h: Move all the wide_int_* prototypes to...
	* wide-int-range.h: ...here.

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index b8716406533..e7d818d174c 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1601,6 +1601,7 @@ OBJS = \
 	web.o \
 	wide-int.o \
 	wide-int-print.o \
+	wide-int-range.o \
 	xcoffout.o \
 	$(out_object_file) \
 	$(EXTRA_OBJS) \
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index d18c72d0a02..e1875d8d46e 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -67,6 +67,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "attribs.h"
 #include "vr-values.h"
 #include "builtins.h"
+#include "wide-int-range.h"
 
 /* Set of SSA names found live during the RPO traversal of the function
    for still active basic-blocks.  */
@@ -956,98 +957,7 @@ value_range_constant_singleton (value_range *vr)
   return NULL_TREE;
 }
 
-/* Wrapper around wide_int_binop that adjusts for overflow.
-
-   Return true if we can compute the result; i.e. if the operation
-   doesn't overflow or if the overflow is undefined.  In the latter
-   case (if the operation overflows and overflow is undefined), then
-   adjust the result to be -INF or +INF depending on CODE, VAL1 and
-   VAL2.  Return the value in *RES.
-
-   Return false for division by zero, for which the result is
-   indeterminate.  */
-
-static bool
-wide_int_binop_overflow (wide_int &res,
-			 enum tree_code code,
-			 const wide_int &w0, const wide_int &w1,
-			 signop sign, bool overflow_undefined)
-{
-  wi::overflow_type overflow;
-  if (!wide_int_binop (res, code, w0, w1, sign, &overflow))
-    return false;
-
-  /* If the operation overflowed return -INF or +INF depending on the
-     operation and the combination of signs of the operands.  */
-  if (overflow && overflow_undefined)
-    {
-      switch (code)
-	{
-	case MULT_EXPR:
-	  /* For multiplication, the sign of the overflow is given
-	     by the comparison of the signs of the operands.  */
-	  if (sign == UNSIGNED || w0.sign_mask () == w1.sign_mask ())
-	    res = wi::max_value (w0.get_precision (), sign);
-	  else
-	    res = wi::min_value (w0.get_precision (), sign);
-	  return true;
-
-	case TRUNC_DIV_EXPR:
-	case FLOOR_DIV_EXPR:
-	case CEIL_DIV_EXPR:
-	case EXACT_DIV_EXPR:
-	case ROUND_DIV_EXPR:
-	  /* For division, the only case is -INF / -1 = +INF.  */
-	  res = wi::max_value (w0.get_precision (), sign);
-	  return true;
-
-	default:
-	  gcc_unreachable ();
-	}
-    }
-  return !overflow;
-}
-
-/* For range [LB, UB] compute two wide_int bit masks.
-
-   In the MAY_BE_NONZERO bit mask, if some bit is unset, it means that
-   for all numbers in the range the bit is 0, otherwise it might be 0
-   or 1.
-
-   In the MUST_BE_NONZERO bit mask, if some bit is set, it means that
-   for all numbers in the range the bit is 1, otherwise it might be 0
-   or 1.  */
-
-void
-wide_int_set_zero_nonzero_bits (signop sign,
-				const wide_int &lb, const wide_int &ub,
-				wide_int &may_be_nonzero,
-				wide_int &must_be_nonzero)
-{
-  may_be_nonzero = wi::minus_one (lb.get_precision ());
-  must_be_nonzero = wi::zero (lb.get_precision ());
-
-  if (wi::eq_p (lb, ub))
-    {
-      may_be_nonzero = lb;
-      must_be_nonzero = may_be_nonzero;
-    }
-  else if (wi::ge_p (lb, 0, sign) || wi::lt_p (ub, 0, sign))
-    {
-      wide_int xor_mask = lb ^ ub;
-      may_be_nonzero = lb | ub;
-      must_be_nonzero = lb & ub;
-      if (xor_mask != 0)
-	{
-	  wide_int mask = wi::mask (wi::floor_log2 (xor_mask), false,
-				    may_be_nonzero.get_precision ());
-	  may_be_nonzero = may_be_nonzero | mask;
-	  must_be_nonzero = wi::bit_and_not (must_be_nonzero, mask);
-	}
-    }
-}
-
-/* Value range wrapper for wide_int_set_zero_nonzero_bits.
+/* Value range wrapper for wide_int_range_set_zero_nonzero_bits.
 
    Compute MAY_BE_NONZERO and MUST_BE_NONZERO bit masks for range in VR.
 
@@ -1066,9 +976,10 @@ vrp_set_zero_nonzero_bits (const tree expr_type,
       *must_be_nonzero = wi::zero (TYPE_PRECISION (expr_type));
       return false;
     }
-  wide_int_set_zero_nonzero_bits (TYPE_SIGN (expr_type),
-				 wi::to_wide (vr->min), wi::to_wide (vr->max),
-				 *may_be_nonzero, *must_be_nonzero);
+  wide_int_range_set_zero_nonzero_bits (TYPE_SIGN (expr_type),
+					wi::to_wide (vr->min),
+					wi::to_wide (vr->max),
+					*may_be_nonzero, *must_be_nonzero);
   return true;
 }
 
@@ -1114,516 +1025,6 @@ ranges_from_anti_range (value_range *ar,
   return vr0->type != VR_UNDEFINED;
 }
 
-/* Order 2 sets of wide int ranges (w0/w1, w2/w3) and set MIN/MAX
-   accordingly.  */
-
-static void
-wide_int_range_min_max (wide_int &min, wide_int &max,
-			wide_int &w0, wide_int &w1, wide_int &w2, wide_int &w3,
-			signop sign)
-{
-  /* Order pairs w0,w1 and w2,w3.  */
-  if (wi::gt_p (w0, w1, sign))
-    std::swap (w0, w1);
-  if (wi::gt_p (w2, w3, sign))
-    std::swap (w2, w3);
-
-  /* Choose min and max from the ordered pairs.  */
-  min = wi::min (w0, w2, sign);
-  max = wi::max (w1, w3, sign);
-}
-
-/* Calculate the cross product of two sets of ranges (VR0 and VR1) and
-   store the result in [RES_LB, RES_UB].
-
-   CODE is the operation to perform with sign SIGN.
-
-   OVERFLOW_UNDEFINED is set if overflow is undefined for the operation type.
-
-   Return TRUE if we were able to calculate the cross product.  */
-
-bool
-wide_int_range_cross_product (wide_int &res_lb, wide_int &res_ub,
-			      enum tree_code code, signop sign,
-			      const wide_int &vr0_lb, const wide_int &vr0_ub,
-			      const wide_int &vr1_lb, const wide_int &vr1_ub,
-			      bool overflow_undefined)
-{
-  wide_int cp1, cp2, cp3, cp4;
-
-  /* Compute the 4 cross operations, bailing if we get an overflow we
-     can't handle.  */
-
-  if (!wide_int_binop_overflow (cp1, code, vr0_lb, vr1_lb, sign,
-				overflow_undefined))
-    return false;
-
-  if (wi::eq_p (vr0_lb, vr0_ub))
-    cp3 = cp1;
-  else if (!wide_int_binop_overflow (cp3, code, vr0_ub, vr1_lb, sign,
-				     overflow_undefined))
-    return false;
-
-  if (wi::eq_p (vr1_lb, vr1_ub))
-    cp2 = cp1;
-  else if (!wide_int_binop_overflow (cp2, code, vr0_lb, vr1_ub, sign,
-				     overflow_undefined))
-    return false;
-
-  if (wi::eq_p (vr0_lb, vr0_ub))
-    cp4 = cp2;
-  else if (!wide_int_binop_overflow (cp4, code, vr0_ub, vr1_ub, sign,
-				     overflow_undefined))
-    return false;
-
-  wide_int_range_min_max (res_lb, res_ub, cp1, cp2, cp3, cp4, sign);
-  return true;
-}
-
-/* Multiply two ranges when TYPE_OVERFLOW_WRAPS:
-
-     [RES_LB, RES_UB] = [MIN0, MAX0] * [MIN1, MAX1]
-
-   This is basically fancy code so we don't drop to varying with an
-   unsigned [-3,-1]*[-3,-1].
-
-   Return TRUE if we were able to perform the operation.  */
-
-bool
-wide_int_range_mult_wrapping (wide_int &res_lb,
-			      wide_int &res_ub,
-			      signop sign,
-			      unsigned prec,
-			      const wide_int &min0_,
-			      const wide_int &max0_,
-			      const wide_int &min1_,
-			      const wide_int &max1_)
-{
-  /* This test requires 2*prec bits if both operands are signed and
-     2*prec + 2 bits if either is not.  Therefore, extend the values
-     using the sign of the result to PREC2.  From here on out,
-     everthing is just signed math no matter what the input types
-     were.  */
-  widest2_int min0 = widest2_int::from (min0_, sign);
-  widest2_int max0 = widest2_int::from (max0_, sign);
-  widest2_int min1 = widest2_int::from (min1_, sign);
-  widest2_int max1 = widest2_int::from (max1_, sign);
-  widest2_int sizem1 = wi::mask <widest2_int> (prec, false);
-  widest2_int size = sizem1 + 1;
-
-  /* Canonicalize the intervals.  */
-  if (sign == UNSIGNED)
-    {
-      if (wi::ltu_p (size, min0 + max0))
-	{
-	  min0 -= size;
-	  max0 -= size;
-	}
-
-      if (wi::ltu_p (size, min1 + max1))
-	{
-	  min1 -= size;
-	  max1 -= size;
-	}
-    }
-
-  widest2_int prod0 = min0 * min1;
-  widest2_int prod1 = min0 * max1;
-  widest2_int prod2 = max0 * min1;
-  widest2_int prod3 = max0 * max1;
-
-  /* Sort the 4 products so that min is in prod0 and max is in
-     prod3.  */
-  /* min0min1 > max0max1 */
-  if (prod0 > prod3)
-    std::swap (prod0, prod3);
-
-  /* min0max1 > max0min1 */
-  if (prod1 > prod2)
-    std::swap (prod1, prod2);
-
-  if (prod0 > prod1)
-    std::swap (prod0, prod1);
-
-  if (prod2 > prod3)
-    std::swap (prod2, prod3);
-
-  /* diff = max - min.  */
-  prod2 = prod3 - prod0;
-  if (wi::geu_p (prod2, sizem1))
-    /* The range covers all values.  */
-    return false;
-
-  res_lb = wide_int::from (prod0, prec, sign);
-  res_ub = wide_int::from (prod3, prec, sign);
-  return true;
-}
-
-/* Perform multiplicative operation CODE on two ranges:
-
-     [RES_LB, RES_UB] = [VR0_LB, VR0_UB] .CODE. [VR1_LB, VR1_LB]
-
-   Return TRUE if we were able to perform the operation.
-
-   NOTE: If code is MULT_EXPR and TYPE_OVERFLOW_WRAPS, the resulting
-   range must be canonicalized by the caller because its components
-   may be swapped.  */
-
-bool
-wide_int_range_multiplicative_op (wide_int &res_lb, wide_int &res_ub,
-				  enum tree_code code,
-				  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)
-{
-  /* Multiplications, divisions and shifts are a bit tricky to handle,
-     depending on the mix of signs we have in the two ranges, we
-     need to operate on different values to get the minimum and
-     maximum values for the new range.  One approach is to figure
-     out all the variations of range combinations and do the
-     operations.
-
-     However, this involves several calls to compare_values and it
-     is pretty convoluted.  It's simpler to do the 4 operations
-     (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)
-    return wide_int_range_mult_wrapping (res_lb, res_ub,
-					 sign, prec,
-					 vr0_lb, vr0_ub, vr1_lb, vr1_ub);
-  return wide_int_range_cross_product (res_lb, res_ub,
-				       code, sign,
-				       vr0_lb, vr0_ub, vr1_lb, vr1_ub,
-				       overflow_undefined);
-}
-
-/* Perform a left shift operation on two ranges:
-
-     [RES_LB, RES_UB] = [VR0_LB, VR0_UB] << [VR1_LB, VR1_LB]
-
-   Return TRUE if we were able to perform the operation.
-
-   NOTE: The resulting range must be canonicalized by the caller
-   because its contents components may be swapped.  */
-
-bool
-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)
-{
-  /* Transform left shifts by constants into multiplies.  */
-  if (wi::eq_p (vr1_lb, vr1_ub))
-    {
-      int shift = wi::extract_uhwi (vr1_ub, 0, vr1_ub.get_precision ());
-      wide_int tmp = wi::set_bit_in_zero (shift, prec);
-      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);
-    }
-
-  int overflow_pos = prec;
-  if (sign == SIGNED)
-    overflow_pos -= 1;
-  int bound_shift = overflow_pos - vr1_ub.to_shwi ();
-  /* If bound_shift == HOST_BITS_PER_WIDE_INT, the llshift can
-     overflow.  However, for that to happen, vr1.max needs to be
-     zero, which means vr1 is a singleton range of zero, which
-     means it should be handled by the previous LSHIFT_EXPR
-     if-clause.  */
-  wide_int bound = wi::set_bit_in_zero (bound_shift, prec);
-  wide_int complement = ~(bound - 1);
-  wide_int low_bound, high_bound;
-  bool in_bounds = false;
-  if (sign == UNSIGNED)
-    {
-      low_bound = bound;
-      high_bound = complement;
-      if (wi::ltu_p (vr0_ub, low_bound))
-	{
-	  /* [5, 6] << [1, 2] == [10, 24].  */
-	  /* We're shifting out only zeroes, the value increases
-	     monotonically.  */
-	  in_bounds = true;
-	}
-      else if (wi::ltu_p (high_bound, vr0_lb))
-	{
-	  /* [0xffffff00, 0xffffffff] << [1, 2]
-	     == [0xfffffc00, 0xfffffffe].  */
-	  /* We're shifting out only ones, the value decreases
-	     monotonically.  */
-	  in_bounds = true;
-	}
-    }
-  else
-    {
-      /* [-1, 1] << [1, 2] == [-4, 4].  */
-      low_bound = complement;
-      high_bound = bound;
-      if (wi::lts_p (vr0_ub, high_bound)
-	  && wi::lts_p (low_bound, vr0_lb))
-	{
-	  /* For non-negative numbers, we're shifting out only
-	     zeroes, the value increases monotonically.
-	     For negative numbers, we're shifting out only ones, the
-	     value decreases monotomically.  */
-	  in_bounds = true;
-	}
-    }
-  if (in_bounds)
-    return wide_int_range_multiplicative_op (res_lb, res_ub,
-					     LSHIFT_EXPR, sign, prec,
-					     vr0_lb, vr0_ub,
-					     vr1_lb, vr1_ub,
-					     overflow_undefined,
-					     overflow_wraps);
-  return false;
-}
-
-/* Return TRUE if a bit operation on two ranges can be easily
-   optimized in terms of a mask.
-
-   Basically, for BIT_AND_EXPR or BIT_IOR_EXPR see if we can optimize:
-
-	[LB, UB] op Z
-   into:
-	[LB op Z, UB op Z]
-
-   It is up to the caller to perform the actual folding above.  */
-
-bool
-wide_int_range_can_optimize_bit_op (tree_code code,
-				    const wide_int &lb, const wide_int &ub,
-				    const wide_int &mask)
-
-{
-  if (code != BIT_AND_EXPR && code != BIT_IOR_EXPR)
-    return false;
-  /* If Z is a constant which (for op | its bitwise not) has n
-     consecutive least significant bits cleared followed by m 1
-     consecutive bits set immediately above it and either
-     m + n == precision, or (x >> (m + n)) == (y >> (m + n)).
-
-     The least significant n bits of all the values in the range are
-     cleared or set, the m bits above it are preserved and any bits
-     above these are required to be the same for all values in the
-     range.  */
-
-  wide_int w = mask;
-  int m = 0, n = 0;
-  if (code == BIT_IOR_EXPR)
-    w = ~w;
-  if (wi::eq_p (w, 0))
-    n = w.get_precision ();
-  else
-    {
-      n = wi::ctz (w);
-      w = ~(w | wi::mask (n, false, w.get_precision ()));
-      if (wi::eq_p (w, 0))
-	m = w.get_precision () - n;
-      else
-	m = wi::ctz (w) - n;
-    }
-  wide_int new_mask = wi::mask (m + n, true, w.get_precision ());
-  if ((new_mask & lb) == (new_mask & ub))
-    return true;
-
-  return false;
-}
-
-/* Return TRUE if shifting by range [MIN, MAX] is undefined behavior.
-
-   FIXME: Make this inline when it moves outside of tree-vrp.  */
-
-bool
-wide_int_range_shift_undefined_p (signop sign, unsigned prec,
-				  const wide_int &min, const wide_int &max)
-{
-  /* ?? Note: The original comment said this only applied to
-     RSHIFT_EXPR, but it was being applied to both left and right
-     shifts.  Is this OK?  */
-
-  /* Shifting by any values outside [0..prec-1], gets undefined
-     behavior from the shift operation.  We cannot even trust
-     SHIFT_COUNT_TRUNCATED at this stage, because that applies to rtl
-     shifts, and the operation at the tree level may be widened.  */
-  return wi::lt_p (min, 0, sign) || wi::ge_p (max, prec, sign);
-}
-
-/* Calculate the XOR of two ranges and store the result in [WMIN,WMAX].
-   The two input ranges are described by their MUST_BE_NONZERO and
-   MAY_BE_NONZERO bit masks.
-
-   Return TRUE if we were able to successfully calculate the new range.  */
-
-bool
-wide_int_range_bit_xor (wide_int &wmin, wide_int &wmax,
-			signop sign,
-			unsigned prec,
-			const wide_int &must_be_nonzero0,
-			const wide_int &may_be_nonzero0,
-			const wide_int &must_be_nonzero1,
-			const wide_int &may_be_nonzero1)
-{
-  wide_int result_zero_bits = ((must_be_nonzero0 & must_be_nonzero1)
-			       | ~(may_be_nonzero0 | may_be_nonzero1));
-  wide_int result_one_bits
-    = (wi::bit_and_not (must_be_nonzero0, may_be_nonzero1)
-       | wi::bit_and_not (must_be_nonzero1, may_be_nonzero0));
-  wmax = ~result_zero_bits;
-  wmin = result_one_bits;
-  /* If the range has all positive or all negative values, the result
-     is better than VARYING.  */
-  if (wi::lt_p (wmin, 0, sign) || wi::ge_p (wmax, 0, sign))
-    return true;
-  wmin = wi::min_value (prec, sign);
-  wmax = wi::max_value (prec, sign);
-  return false;
-}
-
-/* Calculate the IOR of two ranges and store the result in [WMIN,WMAX].
-   Return TRUE if we were able to successfully calculate the new range.  */
-
-bool
-wide_int_range_bit_ior (wide_int &wmin, wide_int &wmax,
-			signop sign,
-			const wide_int &vr0_min,
-			const wide_int &vr0_max,
-			const wide_int &vr1_min,
-			const wide_int &vr1_max,
-			const wide_int &must_be_nonzero0,
-			const wide_int &may_be_nonzero0,
-			const wide_int &must_be_nonzero1,
-			const wide_int &may_be_nonzero1)
-{
-  wmin = must_be_nonzero0 | must_be_nonzero1;
-  wmax = may_be_nonzero0 | may_be_nonzero1;
-  /* If the input ranges contain only positive values we can
-     truncate the minimum of the result range to the maximum
-     of the input range minima.  */
-  if (wi::ge_p (vr0_min, 0, sign)
-      && wi::ge_p (vr1_min, 0, sign))
-    {
-      wmin = wi::max (wmin, vr0_min, sign);
-      wmin = wi::max (wmin, vr1_min, sign);
-    }
-  /* If either input range contains only negative values
-     we can truncate the minimum of the result range to the
-     respective minimum range.  */
-  if (wi::lt_p (vr0_max, 0, sign))
-    wmin = wi::max (wmin, vr0_min, sign);
-  if (wi::lt_p (vr1_max, 0, sign))
-    wmin = wi::max (wmin, vr1_min, sign);
-  /* If the limits got swapped around, indicate error so we can adjust
-     the range to VARYING.  */
-  if (wi::gt_p (wmin, wmax,sign))
-    return false;
-  return true;
-}
-
-/* Calculate the bitwise AND of two ranges and store the result in [WMIN,WMAX].
-   Return TRUE if we were able to successfully calculate the new range.  */
-
-bool
-wide_int_range_bit_and (wide_int &wmin, wide_int &wmax,
-			signop sign,
-			unsigned prec,
-			const wide_int &vr0_min,
-			const wide_int &vr0_max,
-			const wide_int &vr1_min,
-			const wide_int &vr1_max,
-			const wide_int &must_be_nonzero0,
-			const wide_int &may_be_nonzero0,
-			const wide_int &must_be_nonzero1,
-			const wide_int &may_be_nonzero1)
-{
-  wmin = must_be_nonzero0 & must_be_nonzero1;
-  wmax = may_be_nonzero0 & may_be_nonzero1;
-  /* If both input ranges contain only negative values we can
-     truncate the result range maximum to the minimum of the
-     input range maxima.  */
-  if (wi::lt_p (vr0_max, 0, sign) && wi::lt_p (vr1_max, 0, sign))
-    {
-      wmax = wi::min (wmax, vr0_max, sign);
-      wmax = wi::min (wmax, vr1_max, sign);
-    }
-  /* If either input range contains only non-negative values
-     we can truncate the result range maximum to the respective
-     maximum of the input range.  */
-  if (wi::ge_p (vr0_min, 0, sign))
-    wmax = wi::min (wmax, vr0_max, sign);
-  if (wi::ge_p (vr1_min, 0, sign))
-    wmax = wi::min (wmax, vr1_max, sign);
-  /* PR68217: In case of signed & sign-bit-CST should
-     result in [-INF, 0] instead of [-INF, INF].  */
-  if (wi::gt_p (wmin, wmax, sign))
-    {
-      wide_int sign_bit = wi::set_bit_in_zero (prec - 1, prec);
-      if (sign == SIGNED
-	  && ((wi::eq_p (vr0_min, vr0_max)
-	       && !wi::cmps (vr0_min, sign_bit))
-	      || (wi::eq_p (vr1_min, vr1_max)
-		  && !wi::cmps (vr1_min, sign_bit))))
-	{
-	  wmin = wi::min_value (prec, sign);
-	  wmax = wi::zero (prec);
-	}
-    }
-  /* If the limits got swapped around, indicate error so we can adjust
-     the range to VARYING.  */
-  if (wi::gt_p (wmin, wmax,sign))
-    return false;
-  return true;
-}
-
-/* Calculate TRUNC_MOD_EXPR on two ranges and store the result in
-   [WMIN,WMAX].  */
-
-void
-wide_int_range_trunc_mod (wide_int &wmin, wide_int &wmax,
-			  signop sign,
-			  unsigned prec,
-			  const wide_int &vr0_min,
-			  const wide_int &vr0_max,
-			  const wide_int &vr1_min,
-			  const wide_int &vr1_max)
-{
-  wide_int tmp;
-
-  /* ABS (A % B) < ABS (B) and either
-     0 <= A % B <= A or A <= A % B <= 0.  */
-  wmax = vr1_max - 1;
-  if (sign == SIGNED)
-    {
-      tmp = -1 - vr1_min;
-      wmax = wi::smax (wmax, tmp);
-    }
-
-  if (sign == UNSIGNED)
-    wmin = wi::zero (prec);
-  else
-    {
-      wmin = -wmax;
-      tmp = vr0_min;
-      if (wi::gts_p (tmp, 0))
-	tmp = wi::zero (prec);
-      wmin = wi::smax (wmin, tmp);
-    }
-  tmp = vr0_max;
-  if (sign == SIGNED && wi::neg_p (tmp))
-    tmp = wi::zero (prec);
-  wmax = wi::min (wmax, tmp, sign);
-}
-
 /* Extract the components of a value range into a pair of wide ints in
    [WMIN, WMAX].
 
diff --git a/gcc/tree-vrp.h b/gcc/tree-vrp.h
index 8cac7daada7..0c1fb3637cf 100644
--- a/gcc/tree-vrp.h
+++ b/gcc/tree-vrp.h
@@ -105,83 +105,6 @@ extern bool vrp_val_is_min (const_tree);
 extern bool vrp_val_is_max (const_tree);
 extern void copy_value_range (value_range *, value_range *);
 extern void set_value_range_to_value (value_range *, tree, bitmap);
-extern bool wide_int_range_cross_product (wide_int &res_lb, wide_int &res_ub,
-					  enum tree_code code, signop sign,
-					  const wide_int &, const wide_int &,
-					  const wide_int &, const wide_int &,
-					  bool overflow_undefined);
-extern bool wide_int_range_mult_wrapping (wide_int &res_lb,
-					  wide_int &res_ub,
-					  signop sign,
-					  unsigned prec,
-					  const wide_int &min0_,
-					  const wide_int &max0_,
-					  const wide_int &min1_,
-					  const wide_int &max1_);
-extern bool wide_int_range_multiplicative_op (wide_int &res_lb,
-					      wide_int &res_ub,
-					      enum tree_code code,
-					      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);
-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);
-extern bool wide_int_range_shift_undefined_p (signop sign, unsigned prec,
-					      const wide_int &min,
-					      const wide_int &max);
-extern void wide_int_set_zero_nonzero_bits (signop,
-					    const wide_int &lb,
-					    const wide_int &ub,
-					    wide_int &may_be_nonzero,
-					    wide_int &must_be_nonzero);
-extern bool wide_int_range_can_optimize_bit_op (tree_code,
-						const wide_int &lb,
-						const wide_int &ub,
-						const wide_int &mask);
-extern bool wide_int_range_bit_xor (wide_int &wmin, wide_int &wmax,
-				    signop sign,
-				    unsigned prec,
-				    const wide_int &must_be_nonzero0,
-				    const wide_int &may_be_nonzero0,
-				    const wide_int &must_be_nonzero1,
-				    const wide_int &may_be_nonzero1);
-extern bool wide_int_range_bit_ior (wide_int &wmin, wide_int &wmax,
-				    signop sign,
-				    const wide_int &vr0_min,
-				    const wide_int &vr0_max,
-				    const wide_int &vr1_min,
-				    const wide_int &vr1_max,
-				    const wide_int &must_be_nonzero0,
-				    const wide_int &may_be_nonzero0,
-				    const wide_int &must_be_nonzero1,
-				    const wide_int &may_be_nonzero1);
-extern bool wide_int_range_bit_and (wide_int &wmin, wide_int &wmax,
-				    signop sign,
-				    unsigned prec,
-				    const wide_int &vr0_min,
-				    const wide_int &vr0_max,
-				    const wide_int &vr1_min,
-				    const wide_int &vr1_max,
-				    const wide_int &must_be_nonzero0,
-				    const wide_int &may_be_nonzero0,
-				    const wide_int &must_be_nonzero1,
-				    const wide_int &may_be_nonzero1);
-extern void wide_int_range_trunc_mod (wide_int &wmin, wide_int &wmax,
-				      signop sign,
-				      unsigned prec,
-				      const wide_int &vr0_min,
-				      const wide_int &vr0_max,
-				      const wide_int &vr1_min,
-				      const wide_int &vr1_max);
 extern void extract_range_from_binary_expr_1 (value_range *, enum tree_code,
 					      tree, value_range *,
 					      value_range *);
diff --git a/gcc/wide-int-range.cc b/gcc/wide-int-range.cc
new file mode 100644
index 00000000000..3491d89664d
--- /dev/null
+++ b/gcc/wide-int-range.cc
@@ -0,0 +1,607 @@
+/* Support routines for range operations on wide ints.
+   Copyright (C) 2018 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 3, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tree.h"
+#include "fold-const.h"
+#include "wide-int-range.h"
+
+/* Wrapper around wide_int_binop that adjusts for overflow.
+
+   Return true if we can compute the result; i.e. if the operation
+   doesn't overflow or if the overflow is undefined.  In the latter
+   case (if the operation overflows and overflow is undefined), then
+   adjust the result to be -INF or +INF depending on CODE, VAL1 and
+   VAL2.  Return the value in *RES.
+
+   Return false for division by zero, for which the result is
+   indeterminate.  */
+
+static bool
+wide_int_binop_overflow (wide_int &res,
+			 enum tree_code code,
+			 const wide_int &w0, const wide_int &w1,
+			 signop sign, bool overflow_undefined)
+{
+  wi::overflow_type overflow;
+  if (!wide_int_binop (res, code, w0, w1, sign, &overflow))
+    return false;
+
+  /* If the operation overflowed return -INF or +INF depending on the
+     operation and the combination of signs of the operands.  */
+  if (overflow && overflow_undefined)
+    {
+      switch (code)
+	{
+	case MULT_EXPR:
+	  /* For multiplication, the sign of the overflow is given
+	     by the comparison of the signs of the operands.  */
+	  if (sign == UNSIGNED || w0.sign_mask () == w1.sign_mask ())
+	    res = wi::max_value (w0.get_precision (), sign);
+	  else
+	    res = wi::min_value (w0.get_precision (), sign);
+	  return true;
+
+	case TRUNC_DIV_EXPR:
+	case FLOOR_DIV_EXPR:
+	case CEIL_DIV_EXPR:
+	case EXACT_DIV_EXPR:
+	case ROUND_DIV_EXPR:
+	  /* For division, the only case is -INF / -1 = +INF.  */
+	  res = wi::max_value (w0.get_precision (), sign);
+	  return true;
+
+	default:
+	  gcc_unreachable ();
+	}
+    }
+  return !overflow;
+}
+
+/* For range [LB, UB] compute two wide_int bit masks.
+
+   In the MAY_BE_NONZERO bit mask, if some bit is unset, it means that
+   for all numbers in the range the bit is 0, otherwise it might be 0
+   or 1.
+
+   In the MUST_BE_NONZERO bit mask, if some bit is set, it means that
+   for all numbers in the range the bit is 1, otherwise it might be 0
+   or 1.  */
+
+void
+wide_int_range_set_zero_nonzero_bits (signop sign,
+				      const wide_int &lb, const wide_int &ub,
+				      wide_int &may_be_nonzero,
+				      wide_int &must_be_nonzero)
+{
+  may_be_nonzero = wi::minus_one (lb.get_precision ());
+  must_be_nonzero = wi::zero (lb.get_precision ());
+
+  if (wi::eq_p (lb, ub))
+    {
+      may_be_nonzero = lb;
+      must_be_nonzero = may_be_nonzero;
+    }
+  else if (wi::ge_p (lb, 0, sign) || wi::lt_p (ub, 0, sign))
+    {
+      wide_int xor_mask = lb ^ ub;
+      may_be_nonzero = lb | ub;
+      must_be_nonzero = lb & ub;
+      if (xor_mask != 0)
+	{
+	  wide_int mask = wi::mask (wi::floor_log2 (xor_mask), false,
+				    may_be_nonzero.get_precision ());
+	  may_be_nonzero = may_be_nonzero | mask;
+	  must_be_nonzero = wi::bit_and_not (must_be_nonzero, mask);
+	}
+    }
+}
+
+/* Order 2 sets of wide int ranges (w0/w1, w2/w3) and set MIN/MAX
+   accordingly.  */
+
+static void
+wide_int_range_min_max (wide_int &min, wide_int &max,
+			wide_int &w0, wide_int &w1, wide_int &w2, wide_int &w3,
+			signop sign)
+{
+  /* Order pairs w0,w1 and w2,w3.  */
+  if (wi::gt_p (w0, w1, sign))
+    std::swap (w0, w1);
+  if (wi::gt_p (w2, w3, sign))
+    std::swap (w2, w3);
+
+  /* Choose min and max from the ordered pairs.  */
+  min = wi::min (w0, w2, sign);
+  max = wi::max (w1, w3, sign);
+}
+
+/* Calculate the cross product of two sets of ranges (VR0 and VR1) and
+   store the result in [RES_LB, RES_UB].
+
+   CODE is the operation to perform with sign SIGN.
+
+   OVERFLOW_UNDEFINED is set if overflow is undefined for the operation type.
+
+   Return TRUE if we were able to calculate the cross product.  */
+
+bool
+wide_int_range_cross_product (wide_int &res_lb, wide_int &res_ub,
+			      enum tree_code code, signop sign,
+			      const wide_int &vr0_lb, const wide_int &vr0_ub,
+			      const wide_int &vr1_lb, const wide_int &vr1_ub,
+			      bool overflow_undefined)
+{
+  wide_int cp1, cp2, cp3, cp4;
+
+  /* Compute the 4 cross operations, bailing if we get an overflow we
+     can't handle.  */
+
+  if (!wide_int_binop_overflow (cp1, code, vr0_lb, vr1_lb, sign,
+				overflow_undefined))
+    return false;
+
+  if (wi::eq_p (vr0_lb, vr0_ub))
+    cp3 = cp1;
+  else if (!wide_int_binop_overflow (cp3, code, vr0_ub, vr1_lb, sign,
+				     overflow_undefined))
+    return false;
+
+  if (wi::eq_p (vr1_lb, vr1_ub))
+    cp2 = cp1;
+  else if (!wide_int_binop_overflow (cp2, code, vr0_lb, vr1_ub, sign,
+				     overflow_undefined))
+    return false;
+
+  if (wi::eq_p (vr0_lb, vr0_ub))
+    cp4 = cp2;
+  else if (!wide_int_binop_overflow (cp4, code, vr0_ub, vr1_ub, sign,
+				     overflow_undefined))
+    return false;
+
+  wide_int_range_min_max (res_lb, res_ub, cp1, cp2, cp3, cp4, sign);
+  return true;
+}
+
+/* Multiply two ranges when TYPE_OVERFLOW_WRAPS:
+
+     [RES_LB, RES_UB] = [MIN0, MAX0] * [MIN1, MAX1]
+
+   This is basically fancy code so we don't drop to varying with an
+   unsigned [-3,-1]*[-3,-1].
+
+   Return TRUE if we were able to perform the operation.  */
+
+bool
+wide_int_range_mult_wrapping (wide_int &res_lb,
+			      wide_int &res_ub,
+			      signop sign,
+			      unsigned prec,
+			      const wide_int &min0_,
+			      const wide_int &max0_,
+			      const wide_int &min1_,
+			      const wide_int &max1_)
+{
+  /* This test requires 2*prec bits if both operands are signed and
+     2*prec + 2 bits if either is not.  Therefore, extend the values
+     using the sign of the result to PREC2.  From here on out,
+     everthing is just signed math no matter what the input types
+     were.  */
+  widest2_int min0 = widest2_int::from (min0_, sign);
+  widest2_int max0 = widest2_int::from (max0_, sign);
+  widest2_int min1 = widest2_int::from (min1_, sign);
+  widest2_int max1 = widest2_int::from (max1_, sign);
+  widest2_int sizem1 = wi::mask <widest2_int> (prec, false);
+  widest2_int size = sizem1 + 1;
+
+  /* Canonicalize the intervals.  */
+  if (sign == UNSIGNED)
+    {
+      if (wi::ltu_p (size, min0 + max0))
+	{
+	  min0 -= size;
+	  max0 -= size;
+	}
+
+      if (wi::ltu_p (size, min1 + max1))
+	{
+	  min1 -= size;
+	  max1 -= size;
+	}
+    }
+
+  widest2_int prod0 = min0 * min1;
+  widest2_int prod1 = min0 * max1;
+  widest2_int prod2 = max0 * min1;
+  widest2_int prod3 = max0 * max1;
+
+  /* Sort the 4 products so that min is in prod0 and max is in
+     prod3.  */
+  /* min0min1 > max0max1 */
+  if (prod0 > prod3)
+    std::swap (prod0, prod3);
+
+  /* min0max1 > max0min1 */
+  if (prod1 > prod2)
+    std::swap (prod1, prod2);
+
+  if (prod0 > prod1)
+    std::swap (prod0, prod1);
+
+  if (prod2 > prod3)
+    std::swap (prod2, prod3);
+
+  /* diff = max - min.  */
+  prod2 = prod3 - prod0;
+  if (wi::geu_p (prod2, sizem1))
+    /* The range covers all values.  */
+    return false;
+
+  res_lb = wide_int::from (prod0, prec, sign);
+  res_ub = wide_int::from (prod3, prec, sign);
+  return true;
+}
+
+/* Perform multiplicative operation CODE on two ranges:
+
+     [RES_LB, RES_UB] = [VR0_LB, VR0_UB] .CODE. [VR1_LB, VR1_LB]
+
+   Return TRUE if we were able to perform the operation.
+
+   NOTE: If code is MULT_EXPR and TYPE_OVERFLOW_WRAPS, the resulting
+   range must be canonicalized by the caller because its components
+   may be swapped.  */
+
+bool
+wide_int_range_multiplicative_op (wide_int &res_lb, wide_int &res_ub,
+				  enum tree_code code,
+				  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)
+{
+  /* Multiplications, divisions and shifts are a bit tricky to handle,
+     depending on the mix of signs we have in the two ranges, we
+     need to operate on different values to get the minimum and
+     maximum values for the new range.  One approach is to figure
+     out all the variations of range combinations and do the
+     operations.
+
+     However, this involves several calls to compare_values and it
+     is pretty convoluted.  It's simpler to do the 4 operations
+     (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)
+    return wide_int_range_mult_wrapping (res_lb, res_ub,
+					 sign, prec,
+					 vr0_lb, vr0_ub, vr1_lb, vr1_ub);
+  return wide_int_range_cross_product (res_lb, res_ub,
+				       code, sign,
+				       vr0_lb, vr0_ub, vr1_lb, vr1_ub,
+				       overflow_undefined);
+}
+
+/* Perform a left shift operation on two ranges:
+
+     [RES_LB, RES_UB] = [VR0_LB, VR0_UB] << [VR1_LB, VR1_LB]
+
+   Return TRUE if we were able to perform the operation.
+
+   NOTE: The resulting range must be canonicalized by the caller
+   because its contents components may be swapped.  */
+
+bool
+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)
+{
+  /* Transform left shifts by constants into multiplies.  */
+  if (wi::eq_p (vr1_lb, vr1_ub))
+    {
+      int shift = wi::extract_uhwi (vr1_ub, 0, vr1_ub.get_precision ());
+      wide_int tmp = wi::set_bit_in_zero (shift, prec);
+      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);
+    }
+
+  int overflow_pos = prec;
+  if (sign == SIGNED)
+    overflow_pos -= 1;
+  int bound_shift = overflow_pos - vr1_ub.to_shwi ();
+  /* If bound_shift == HOST_BITS_PER_WIDE_INT, the llshift can
+     overflow.  However, for that to happen, vr1.max needs to be
+     zero, which means vr1 is a singleton range of zero, which
+     means it should be handled by the previous LSHIFT_EXPR
+     if-clause.  */
+  wide_int bound = wi::set_bit_in_zero (bound_shift, prec);
+  wide_int complement = ~(bound - 1);
+  wide_int low_bound, high_bound;
+  bool in_bounds = false;
+  if (sign == UNSIGNED)
+    {
+      low_bound = bound;
+      high_bound = complement;
+      if (wi::ltu_p (vr0_ub, low_bound))
+	{
+	  /* [5, 6] << [1, 2] == [10, 24].  */
+	  /* We're shifting out only zeroes, the value increases
+	     monotonically.  */
+	  in_bounds = true;
+	}
+      else if (wi::ltu_p (high_bound, vr0_lb))
+	{
+	  /* [0xffffff00, 0xffffffff] << [1, 2]
+	     == [0xfffffc00, 0xfffffffe].  */
+	  /* We're shifting out only ones, the value decreases
+	     monotonically.  */
+	  in_bounds = true;
+	}
+    }
+  else
+    {
+      /* [-1, 1] << [1, 2] == [-4, 4].  */
+      low_bound = complement;
+      high_bound = bound;
+      if (wi::lts_p (vr0_ub, high_bound)
+	  && wi::lts_p (low_bound, vr0_lb))
+	{
+	  /* For non-negative numbers, we're shifting out only
+	     zeroes, the value increases monotonically.
+	     For negative numbers, we're shifting out only ones, the
+	     value decreases monotomically.  */
+	  in_bounds = true;
+	}
+    }
+  if (in_bounds)
+    return wide_int_range_multiplicative_op (res_lb, res_ub,
+					     LSHIFT_EXPR, sign, prec,
+					     vr0_lb, vr0_ub,
+					     vr1_lb, vr1_ub,
+					     overflow_undefined,
+					     overflow_wraps);
+  return false;
+}
+
+/* Return TRUE if a bit operation on two ranges can be easily
+   optimized in terms of a mask.
+
+   Basically, for BIT_AND_EXPR or BIT_IOR_EXPR see if we can optimize:
+
+	[LB, UB] op Z
+   into:
+	[LB op Z, UB op Z]
+
+   It is up to the caller to perform the actual folding above.  */
+
+bool
+wide_int_range_can_optimize_bit_op (tree_code code,
+				    const wide_int &lb, const wide_int &ub,
+				    const wide_int &mask)
+
+{
+  if (code != BIT_AND_EXPR && code != BIT_IOR_EXPR)
+    return false;
+  /* If Z is a constant which (for op | its bitwise not) has n
+     consecutive least significant bits cleared followed by m 1
+     consecutive bits set immediately above it and either
+     m + n == precision, or (x >> (m + n)) == (y >> (m + n)).
+
+     The least significant n bits of all the values in the range are
+     cleared or set, the m bits above it are preserved and any bits
+     above these are required to be the same for all values in the
+     range.  */
+
+  wide_int w = mask;
+  int m = 0, n = 0;
+  if (code == BIT_IOR_EXPR)
+    w = ~w;
+  if (wi::eq_p (w, 0))
+    n = w.get_precision ();
+  else
+    {
+      n = wi::ctz (w);
+      w = ~(w | wi::mask (n, false, w.get_precision ()));
+      if (wi::eq_p (w, 0))
+	m = w.get_precision () - n;
+      else
+	m = wi::ctz (w) - n;
+    }
+  wide_int new_mask = wi::mask (m + n, true, w.get_precision ());
+  if ((new_mask & lb) == (new_mask & ub))
+    return true;
+
+  return false;
+}
+
+/* Calculate the XOR of two ranges and store the result in [WMIN,WMAX].
+   The two input ranges are described by their MUST_BE_NONZERO and
+   MAY_BE_NONZERO bit masks.
+
+   Return TRUE if we were able to successfully calculate the new range.  */
+
+bool
+wide_int_range_bit_xor (wide_int &wmin, wide_int &wmax,
+			signop sign,
+			unsigned prec,
+			const wide_int &must_be_nonzero0,
+			const wide_int &may_be_nonzero0,
+			const wide_int &must_be_nonzero1,
+			const wide_int &may_be_nonzero1)
+{
+  wide_int result_zero_bits = ((must_be_nonzero0 & must_be_nonzero1)
+			       | ~(may_be_nonzero0 | may_be_nonzero1));
+  wide_int result_one_bits
+    = (wi::bit_and_not (must_be_nonzero0, may_be_nonzero1)
+       | wi::bit_and_not (must_be_nonzero1, may_be_nonzero0));
+  wmax = ~result_zero_bits;
+  wmin = result_one_bits;
+  /* If the range has all positive or all negative values, the result
+     is better than VARYING.  */
+  if (wi::lt_p (wmin, 0, sign) || wi::ge_p (wmax, 0, sign))
+    return true;
+  wmin = wi::min_value (prec, sign);
+  wmax = wi::max_value (prec, sign);
+  return false;
+}
+
+/* Calculate the IOR of two ranges and store the result in [WMIN,WMAX].
+   Return TRUE if we were able to successfully calculate the new range.  */
+
+bool
+wide_int_range_bit_ior (wide_int &wmin, wide_int &wmax,
+			signop sign,
+			const wide_int &vr0_min,
+			const wide_int &vr0_max,
+			const wide_int &vr1_min,
+			const wide_int &vr1_max,
+			const wide_int &must_be_nonzero0,
+			const wide_int &may_be_nonzero0,
+			const wide_int &must_be_nonzero1,
+			const wide_int &may_be_nonzero1)
+{
+  wmin = must_be_nonzero0 | must_be_nonzero1;
+  wmax = may_be_nonzero0 | may_be_nonzero1;
+  /* If the input ranges contain only positive values we can
+     truncate the minimum of the result range to the maximum
+     of the input range minima.  */
+  if (wi::ge_p (vr0_min, 0, sign)
+      && wi::ge_p (vr1_min, 0, sign))
+    {
+      wmin = wi::max (wmin, vr0_min, sign);
+      wmin = wi::max (wmin, vr1_min, sign);
+    }
+  /* If either input range contains only negative values
+     we can truncate the minimum of the result range to the
+     respective minimum range.  */
+  if (wi::lt_p (vr0_max, 0, sign))
+    wmin = wi::max (wmin, vr0_min, sign);
+  if (wi::lt_p (vr1_max, 0, sign))
+    wmin = wi::max (wmin, vr1_min, sign);
+  /* If the limits got swapped around, indicate error so we can adjust
+     the range to VARYING.  */
+  if (wi::gt_p (wmin, wmax,sign))
+    return false;
+  return true;
+}
+
+/* Calculate the bitwise AND of two ranges and store the result in [WMIN,WMAX].
+   Return TRUE if we were able to successfully calculate the new range.  */
+
+bool
+wide_int_range_bit_and (wide_int &wmin, wide_int &wmax,
+			signop sign,
+			unsigned prec,
+			const wide_int &vr0_min,
+			const wide_int &vr0_max,
+			const wide_int &vr1_min,
+			const wide_int &vr1_max,
+			const wide_int &must_be_nonzero0,
+			const wide_int &may_be_nonzero0,
+			const wide_int &must_be_nonzero1,
+			const wide_int &may_be_nonzero1)
+{
+  wmin = must_be_nonzero0 & must_be_nonzero1;
+  wmax = may_be_nonzero0 & may_be_nonzero1;
+  /* If both input ranges contain only negative values we can
+     truncate the result range maximum to the minimum of the
+     input range maxima.  */
+  if (wi::lt_p (vr0_max, 0, sign) && wi::lt_p (vr1_max, 0, sign))
+    {
+      wmax = wi::min (wmax, vr0_max, sign);
+      wmax = wi::min (wmax, vr1_max, sign);
+    }
+  /* If either input range contains only non-negative values
+     we can truncate the result range maximum to the respective
+     maximum of the input range.  */
+  if (wi::ge_p (vr0_min, 0, sign))
+    wmax = wi::min (wmax, vr0_max, sign);
+  if (wi::ge_p (vr1_min, 0, sign))
+    wmax = wi::min (wmax, vr1_max, sign);
+  /* PR68217: In case of signed & sign-bit-CST should
+     result in [-INF, 0] instead of [-INF, INF].  */
+  if (wi::gt_p (wmin, wmax, sign))
+    {
+      wide_int sign_bit = wi::set_bit_in_zero (prec - 1, prec);
+      if (sign == SIGNED
+	  && ((wi::eq_p (vr0_min, vr0_max)
+	       && !wi::cmps (vr0_min, sign_bit))
+	      || (wi::eq_p (vr1_min, vr1_max)
+		  && !wi::cmps (vr1_min, sign_bit))))
+	{
+	  wmin = wi::min_value (prec, sign);
+	  wmax = wi::zero (prec);
+	}
+    }
+  /* If the limits got swapped around, indicate error so we can adjust
+     the range to VARYING.  */
+  if (wi::gt_p (wmin, wmax,sign))
+    return false;
+  return true;
+}
+
+/* Calculate TRUNC_MOD_EXPR on two ranges and store the result in
+   [WMIN,WMAX].  */
+
+void
+wide_int_range_trunc_mod (wide_int &wmin, wide_int &wmax,
+			  signop sign,
+			  unsigned prec,
+			  const wide_int &vr0_min,
+			  const wide_int &vr0_max,
+			  const wide_int &vr1_min,
+			  const wide_int &vr1_max)
+{
+  wide_int tmp;
+
+  /* ABS (A % B) < ABS (B) and either
+     0 <= A % B <= A or A <= A % B <= 0.  */
+  wmax = vr1_max - 1;
+  if (sign == SIGNED)
+    {
+      tmp = -1 - vr1_min;
+      wmax = wi::smax (wmax, tmp);
+    }
+
+  if (sign == UNSIGNED)
+    wmin = wi::zero (prec);
+  else
+    {
+      wmin = -wmax;
+      tmp = vr0_min;
+      if (wi::gts_p (tmp, 0))
+	tmp = wi::zero (prec);
+      wmin = wi::smax (wmin, tmp);
+    }
+  tmp = vr0_max;
+  if (sign == SIGNED && wi::neg_p (tmp))
+    tmp = wi::zero (prec);
+  wmax = wi::min (wmax, tmp, sign);
+}
diff --git a/gcc/wide-int-range.h b/gcc/wide-int-range.h
new file mode 100644
index 00000000000..4421bc8aeca
--- /dev/null
+++ b/gcc/wide-int-range.h
@@ -0,0 +1,115 @@
+/* Support routines for range operations on wide ints.
+   Copyright (C) 2018 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 3, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#ifndef GCC_WIDE_INT_RANGE_H
+#define GCC_WIDE_INT_RANGE_H
+
+extern bool wide_int_range_cross_product (wide_int &res_lb, wide_int &res_ub,
+					  enum tree_code code, signop sign,
+					  const wide_int &, const wide_int &,
+					  const wide_int &, const wide_int &,
+					  bool overflow_undefined);
+extern bool wide_int_range_mult_wrapping (wide_int &res_lb,
+					  wide_int &res_ub,
+					  signop sign,
+					  unsigned prec,
+					  const wide_int &min0_,
+					  const wide_int &max0_,
+					  const wide_int &min1_,
+					  const wide_int &max1_);
+extern bool wide_int_range_multiplicative_op (wide_int &res_lb,
+					      wide_int &res_ub,
+					      enum tree_code code,
+					      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);
+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);
+extern void wide_int_range_set_zero_nonzero_bits (signop,
+						  const wide_int &lb,
+						  const wide_int &ub,
+						  wide_int &may_be_nonzero,
+						  wide_int &must_be_nonzero);
+extern bool wide_int_range_can_optimize_bit_op (tree_code,
+						const wide_int &lb,
+						const wide_int &ub,
+						const wide_int &mask);
+extern bool wide_int_range_bit_xor (wide_int &wmin, wide_int &wmax,
+				    signop sign,
+				    unsigned prec,
+				    const wide_int &must_be_nonzero0,
+				    const wide_int &may_be_nonzero0,
+				    const wide_int &must_be_nonzero1,
+				    const wide_int &may_be_nonzero1);
+extern bool wide_int_range_bit_ior (wide_int &wmin, wide_int &wmax,
+				    signop sign,
+				    const wide_int &vr0_min,
+				    const wide_int &vr0_max,
+				    const wide_int &vr1_min,
+				    const wide_int &vr1_max,
+				    const wide_int &must_be_nonzero0,
+				    const wide_int &may_be_nonzero0,
+				    const wide_int &must_be_nonzero1,
+				    const wide_int &may_be_nonzero1);
+extern bool wide_int_range_bit_and (wide_int &wmin, wide_int &wmax,
+				    signop sign,
+				    unsigned prec,
+				    const wide_int &vr0_min,
+				    const wide_int &vr0_max,
+				    const wide_int &vr1_min,
+				    const wide_int &vr1_max,
+				    const wide_int &must_be_nonzero0,
+				    const wide_int &may_be_nonzero0,
+				    const wide_int &must_be_nonzero1,
+				    const wide_int &may_be_nonzero1);
+extern void wide_int_range_trunc_mod (wide_int &wmin, wide_int &wmax,
+				      signop sign,
+				      unsigned prec,
+				      const wide_int &vr0_min,
+				      const wide_int &vr0_max,
+				      const wide_int &vr1_min,
+				      const wide_int &vr1_max);
+
+/* Return TRUE if shifting by range [MIN, MAX] is undefined behavior.  */
+
+inline bool
+wide_int_range_shift_undefined_p (signop sign, unsigned prec,
+				  const wide_int &min, const wide_int &max)
+{
+  /* ?? Note: The original comment said this only applied to
+     RSHIFT_EXPR, but it was being applied to both left and right
+     shifts.  */
+
+  /* Shifting by any values outside [0..prec-1], gets undefined
+     behavior from the shift operation.  We cannot even trust
+     SHIFT_COUNT_TRUNCATED at this stage, because that applies to rtl
+     shifts, and the operation at the tree level may be widened.  */
+  return wi::lt_p (min, 0, sign) || wi::ge_p (max, prec, sign);
+}
+
+#endif /* GCC_WIDE_INT_RANGE_H */
Jeff Law Aug. 2, 2018, 6:50 p.m. UTC | #5
On 08/02/2018 12:23 PM, Aldy Hernandez wrote:
> 
> 
> On 08/02/2018 02:07 PM, Jeff Law wrote:
>> On 08/01/2018 03:19 PM, David Malcolm wrote:
>>> On Wed, 2018-08-01 at 15:39 -0400, Aldy Hernandez wrote:
>>>> This is actually an obvious patch, but I'm not committing it just in
>>>> case you'd prefer another name for the files.
>>>
>>> BTW, is it our policy that new gcc C++ source files should have a .cc
>>> extension?
>> I believe so.
>> jeff
>>
> 
> I did not know that.  I'm happy to rename it to .cc.
> 
> OK with that change ;-)?
If it's just moving code around, yes, OK.

Jeff
Aldy Hernandez Aug. 2, 2018, 7:02 p.m. UTC | #6
On 08/02/2018 02:50 PM, Jeff Law wrote:
> On 08/02/2018 12:23 PM, Aldy Hernandez wrote:
>>
>>
>> On 08/02/2018 02:07 PM, Jeff Law wrote:
>>> On 08/01/2018 03:19 PM, David Malcolm wrote:
>>>> On Wed, 2018-08-01 at 15:39 -0400, Aldy Hernandez wrote:
>>>>> This is actually an obvious patch, but I'm not committing it just in
>>>>> case you'd prefer another name for the files.
>>>>
>>>> BTW, is it our policy that new gcc C++ source files should have a .cc
>>>> extension?
>>> I believe so.
>>> jeff
>>>
>>
>> I did not know that.  I'm happy to rename it to .cc.
>>
>> OK with that change ;-)?
> If it's just moving code around, yes, OK.

Yes it is.

Will commit after another bootstrap after my header change, just in case.

Thanks.
Aldy

Patch
diff mbox series

gcc/

	* Makefile.in (wide-int-range.o): New.
	* tree-vrp.c: Move all the wide_int_* functions to...
	* wide-int-range.c: ...here.
	* tree-vrp.h: Move all the wide_int_* prototypes to...
	* wide-int-range.h: ...here.

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index b8716406533..e7d818d174c 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1601,6 +1601,7 @@  OBJS = \
 	web.o \
 	wide-int.o \
 	wide-int-print.o \
+	wide-int-range.o \
 	xcoffout.o \
 	$(out_object_file) \
 	$(EXTRA_OBJS) \
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index d18c72d0a02..e1875d8d46e 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -67,6 +67,7 @@  along with GCC; see the file COPYING3.  If not see
 #include "attribs.h"
 #include "vr-values.h"
 #include "builtins.h"
+#include "wide-int-range.h"
 
 /* Set of SSA names found live during the RPO traversal of the function
    for still active basic-blocks.  */
@@ -956,98 +957,7 @@  value_range_constant_singleton (value_range *vr)
   return NULL_TREE;
 }
 
-/* Wrapper around wide_int_binop that adjusts for overflow.
-
-   Return true if we can compute the result; i.e. if the operation
-   doesn't overflow or if the overflow is undefined.  In the latter
-   case (if the operation overflows and overflow is undefined), then
-   adjust the result to be -INF or +INF depending on CODE, VAL1 and
-   VAL2.  Return the value in *RES.
-
-   Return false for division by zero, for which the result is
-   indeterminate.  */
-
-static bool
-wide_int_binop_overflow (wide_int &res,
-			 enum tree_code code,
-			 const wide_int &w0, const wide_int &w1,
-			 signop sign, bool overflow_undefined)
-{
-  wi::overflow_type overflow;
-  if (!wide_int_binop (res, code, w0, w1, sign, &overflow))
-    return false;
-
-  /* If the operation overflowed return -INF or +INF depending on the
-     operation and the combination of signs of the operands.  */
-  if (overflow && overflow_undefined)
-    {
-      switch (code)
-	{
-	case MULT_EXPR:
-	  /* For multiplication, the sign of the overflow is given
-	     by the comparison of the signs of the operands.  */
-	  if (sign == UNSIGNED || w0.sign_mask () == w1.sign_mask ())
-	    res = wi::max_value (w0.get_precision (), sign);
-	  else
-	    res = wi::min_value (w0.get_precision (), sign);
-	  return true;
-
-	case TRUNC_DIV_EXPR:
-	case FLOOR_DIV_EXPR:
-	case CEIL_DIV_EXPR:
-	case EXACT_DIV_EXPR:
-	case ROUND_DIV_EXPR:
-	  /* For division, the only case is -INF / -1 = +INF.  */
-	  res = wi::max_value (w0.get_precision (), sign);
-	  return true;
-
-	default:
-	  gcc_unreachable ();
-	}
-    }
-  return !overflow;
-}
-
-/* For range [LB, UB] compute two wide_int bit masks.
-
-   In the MAY_BE_NONZERO bit mask, if some bit is unset, it means that
-   for all numbers in the range the bit is 0, otherwise it might be 0
-   or 1.
-
-   In the MUST_BE_NONZERO bit mask, if some bit is set, it means that
-   for all numbers in the range the bit is 1, otherwise it might be 0
-   or 1.  */
-
-void
-wide_int_set_zero_nonzero_bits (signop sign,
-				const wide_int &lb, const wide_int &ub,
-				wide_int &may_be_nonzero,
-				wide_int &must_be_nonzero)
-{
-  may_be_nonzero = wi::minus_one (lb.get_precision ());
-  must_be_nonzero = wi::zero (lb.get_precision ());
-
-  if (wi::eq_p (lb, ub))
-    {
-      may_be_nonzero = lb;
-      must_be_nonzero = may_be_nonzero;
-    }
-  else if (wi::ge_p (lb, 0, sign) || wi::lt_p (ub, 0, sign))
-    {
-      wide_int xor_mask = lb ^ ub;
-      may_be_nonzero = lb | ub;
-      must_be_nonzero = lb & ub;
-      if (xor_mask != 0)
-	{
-	  wide_int mask = wi::mask (wi::floor_log2 (xor_mask), false,
-				    may_be_nonzero.get_precision ());
-	  may_be_nonzero = may_be_nonzero | mask;
-	  must_be_nonzero = wi::bit_and_not (must_be_nonzero, mask);
-	}
-    }
-}
-
-/* Value range wrapper for wide_int_set_zero_nonzero_bits.
+/* Value range wrapper for wide_int_range_set_zero_nonzero_bits.
 
    Compute MAY_BE_NONZERO and MUST_BE_NONZERO bit masks for range in VR.
 
@@ -1066,9 +976,10 @@  vrp_set_zero_nonzero_bits (const tree expr_type,
       *must_be_nonzero = wi::zero (TYPE_PRECISION (expr_type));
       return false;
     }
-  wide_int_set_zero_nonzero_bits (TYPE_SIGN (expr_type),
-				 wi::to_wide (vr->min), wi::to_wide (vr->max),
-				 *may_be_nonzero, *must_be_nonzero);
+  wide_int_range_set_zero_nonzero_bits (TYPE_SIGN (expr_type),
+					wi::to_wide (vr->min),
+					wi::to_wide (vr->max),
+					*may_be_nonzero, *must_be_nonzero);
   return true;
 }
 
@@ -1114,516 +1025,6 @@  ranges_from_anti_range (value_range *ar,
   return vr0->type != VR_UNDEFINED;
 }
 
-/* Order 2 sets of wide int ranges (w0/w1, w2/w3) and set MIN/MAX
-   accordingly.  */
-
-static void
-wide_int_range_min_max (wide_int &min, wide_int &max,
-			wide_int &w0, wide_int &w1, wide_int &w2, wide_int &w3,
-			signop sign)
-{
-  /* Order pairs w0,w1 and w2,w3.  */
-  if (wi::gt_p (w0, w1, sign))
-    std::swap (w0, w1);
-  if (wi::gt_p (w2, w3, sign))
-    std::swap (w2, w3);
-
-  /* Choose min and max from the ordered pairs.  */
-  min = wi::min (w0, w2, sign);
-  max = wi::max (w1, w3, sign);
-}
-
-/* Calculate the cross product of two sets of ranges (VR0 and VR1) and
-   store the result in [RES_LB, RES_UB].
-
-   CODE is the operation to perform with sign SIGN.
-
-   OVERFLOW_UNDEFINED is set if overflow is undefined for the operation type.
-
-   Return TRUE if we were able to calculate the cross product.  */
-
-bool
-wide_int_range_cross_product (wide_int &res_lb, wide_int &res_ub,
-			      enum tree_code code, signop sign,
-			      const wide_int &vr0_lb, const wide_int &vr0_ub,
-			      const wide_int &vr1_lb, const wide_int &vr1_ub,
-			      bool overflow_undefined)
-{
-  wide_int cp1, cp2, cp3, cp4;
-
-  /* Compute the 4 cross operations, bailing if we get an overflow we
-     can't handle.  */
-
-  if (!wide_int_binop_overflow (cp1, code, vr0_lb, vr1_lb, sign,
-				overflow_undefined))
-    return false;
-
-  if (wi::eq_p (vr0_lb, vr0_ub))
-    cp3 = cp1;
-  else if (!wide_int_binop_overflow (cp3, code, vr0_ub, vr1_lb, sign,
-				     overflow_undefined))
-    return false;
-
-  if (wi::eq_p (vr1_lb, vr1_ub))
-    cp2 = cp1;
-  else if (!wide_int_binop_overflow (cp2, code, vr0_lb, vr1_ub, sign,
-				     overflow_undefined))
-    return false;
-
-  if (wi::eq_p (vr0_lb, vr0_ub))
-    cp4 = cp2;
-  else if (!wide_int_binop_overflow (cp4, code, vr0_ub, vr1_ub, sign,
-				     overflow_undefined))
-    return false;
-
-  wide_int_range_min_max (res_lb, res_ub, cp1, cp2, cp3, cp4, sign);
-  return true;
-}
-
-/* Multiply two ranges when TYPE_OVERFLOW_WRAPS:
-
-     [RES_LB, RES_UB] = [MIN0, MAX0] * [MIN1, MAX1]
-
-   This is basically fancy code so we don't drop to varying with an
-   unsigned [-3,-1]*[-3,-1].
-
-   Return TRUE if we were able to perform the operation.  */
-
-bool
-wide_int_range_mult_wrapping (wide_int &res_lb,
-			      wide_int &res_ub,
-			      signop sign,
-			      unsigned prec,
-			      const wide_int &min0_,
-			      const wide_int &max0_,
-			      const wide_int &min1_,
-			      const wide_int &max1_)
-{
-  /* This test requires 2*prec bits if both operands are signed and
-     2*prec + 2 bits if either is not.  Therefore, extend the values
-     using the sign of the result to PREC2.  From here on out,
-     everthing is just signed math no matter what the input types
-     were.  */
-  widest2_int min0 = widest2_int::from (min0_, sign);
-  widest2_int max0 = widest2_int::from (max0_, sign);
-  widest2_int min1 = widest2_int::from (min1_, sign);
-  widest2_int max1 = widest2_int::from (max1_, sign);
-  widest2_int sizem1 = wi::mask <widest2_int> (prec, false);
-  widest2_int size = sizem1 + 1;
-
-  /* Canonicalize the intervals.  */
-  if (sign == UNSIGNED)
-    {
-      if (wi::ltu_p (size, min0 + max0))
-	{
-	  min0 -= size;
-	  max0 -= size;
-	}
-
-      if (wi::ltu_p (size, min1 + max1))
-	{
-	  min1 -= size;
-	  max1 -= size;
-	}
-    }
-
-  widest2_int prod0 = min0 * min1;
-  widest2_int prod1 = min0 * max1;
-  widest2_int prod2 = max0 * min1;
-  widest2_int prod3 = max0 * max1;
-
-  /* Sort the 4 products so that min is in prod0 and max is in
-     prod3.  */
-  /* min0min1 > max0max1 */
-  if (prod0 > prod3)
-    std::swap (prod0, prod3);
-
-  /* min0max1 > max0min1 */
-  if (prod1 > prod2)
-    std::swap (prod1, prod2);
-
-  if (prod0 > prod1)
-    std::swap (prod0, prod1);
-
-  if (prod2 > prod3)
-    std::swap (prod2, prod3);
-
-  /* diff = max - min.  */
-  prod2 = prod3 - prod0;
-  if (wi::geu_p (prod2, sizem1))
-    /* The range covers all values.  */
-    return false;
-
-  res_lb = wide_int::from (prod0, prec, sign);
-  res_ub = wide_int::from (prod3, prec, sign);
-  return true;
-}
-
-/* Perform multiplicative operation CODE on two ranges:
-
-     [RES_LB, RES_UB] = [VR0_LB, VR0_UB] .CODE. [VR1_LB, VR1_LB]
-
-   Return TRUE if we were able to perform the operation.
-
-   NOTE: If code is MULT_EXPR and TYPE_OVERFLOW_WRAPS, the resulting
-   range must be canonicalized by the caller because its components
-   may be swapped.  */
-
-bool
-wide_int_range_multiplicative_op (wide_int &res_lb, wide_int &res_ub,
-				  enum tree_code code,
-				  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)
-{
-  /* Multiplications, divisions and shifts are a bit tricky to handle,
-     depending on the mix of signs we have in the two ranges, we
-     need to operate on different values to get the minimum and
-     maximum values for the new range.  One approach is to figure
-     out all the variations of range combinations and do the
-     operations.
-
-     However, this involves several calls to compare_values and it
-     is pretty convoluted.  It's simpler to do the 4 operations
-     (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)
-    return wide_int_range_mult_wrapping (res_lb, res_ub,
-					 sign, prec,
-					 vr0_lb, vr0_ub, vr1_lb, vr1_ub);
-  return wide_int_range_cross_product (res_lb, res_ub,
-				       code, sign,
-				       vr0_lb, vr0_ub, vr1_lb, vr1_ub,
-				       overflow_undefined);
-}
-
-/* Perform a left shift operation on two ranges:
-
-     [RES_LB, RES_UB] = [VR0_LB, VR0_UB] << [VR1_LB, VR1_LB]
-
-   Return TRUE if we were able to perform the operation.
-
-   NOTE: The resulting range must be canonicalized by the caller
-   because its contents components may be swapped.  */
-
-bool
-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)
-{
-  /* Transform left shifts by constants into multiplies.  */
-  if (wi::eq_p (vr1_lb, vr1_ub))
-    {
-      int shift = wi::extract_uhwi (vr1_ub, 0, vr1_ub.get_precision ());
-      wide_int tmp = wi::set_bit_in_zero (shift, prec);
-      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);
-    }
-
-  int overflow_pos = prec;
-  if (sign == SIGNED)
-    overflow_pos -= 1;
-  int bound_shift = overflow_pos - vr1_ub.to_shwi ();
-  /* If bound_shift == HOST_BITS_PER_WIDE_INT, the llshift can
-     overflow.  However, for that to happen, vr1.max needs to be
-     zero, which means vr1 is a singleton range of zero, which
-     means it should be handled by the previous LSHIFT_EXPR
-     if-clause.  */
-  wide_int bound = wi::set_bit_in_zero (bound_shift, prec);
-  wide_int complement = ~(bound - 1);
-  wide_int low_bound, high_bound;
-  bool in_bounds = false;
-  if (sign == UNSIGNED)
-    {
-      low_bound = bound;
-      high_bound = complement;
-      if (wi::ltu_p (vr0_ub, low_bound))
-	{
-	  /* [5, 6] << [1, 2] == [10, 24].  */
-	  /* We're shifting out only zeroes, the value increases
-	     monotonically.  */
-	  in_bounds = true;
-	}
-      else if (wi::ltu_p (high_bound, vr0_lb))
-	{
-	  /* [0xffffff00, 0xffffffff] << [1, 2]
-	     == [0xfffffc00, 0xfffffffe].  */
-	  /* We're shifting out only ones, the value decreases
-	     monotonically.  */
-	  in_bounds = true;
-	}
-    }
-  else
-    {
-      /* [-1, 1] << [1, 2] == [-4, 4].  */
-      low_bound = complement;
-      high_bound = bound;
-      if (wi::lts_p (vr0_ub, high_bound)
-	  && wi::lts_p (low_bound, vr0_lb))
-	{
-	  /* For non-negative numbers, we're shifting out only
-	     zeroes, the value increases monotonically.
-	     For negative numbers, we're shifting out only ones, the
-	     value decreases monotomically.  */
-	  in_bounds = true;
-	}
-    }
-  if (in_bounds)
-    return wide_int_range_multiplicative_op (res_lb, res_ub,
-					     LSHIFT_EXPR, sign, prec,
-					     vr0_lb, vr0_ub,
-					     vr1_lb, vr1_ub,
-					     overflow_undefined,
-					     overflow_wraps);
-  return false;
-}
-
-/* Return TRUE if a bit operation on two ranges can be easily
-   optimized in terms of a mask.
-
-   Basically, for BIT_AND_EXPR or BIT_IOR_EXPR see if we can optimize:
-
-	[LB, UB] op Z
-   into:
-	[LB op Z, UB op Z]
-
-   It is up to the caller to perform the actual folding above.  */
-
-bool
-wide_int_range_can_optimize_bit_op (tree_code code,
-				    const wide_int &lb, const wide_int &ub,
-				    const wide_int &mask)
-
-{
-  if (code != BIT_AND_EXPR && code != BIT_IOR_EXPR)
-    return false;
-  /* If Z is a constant which (for op | its bitwise not) has n
-     consecutive least significant bits cleared followed by m 1
-     consecutive bits set immediately above it and either
-     m + n == precision, or (x >> (m + n)) == (y >> (m + n)).
-
-     The least significant n bits of all the values in the range are
-     cleared or set, the m bits above it are preserved and any bits
-     above these are required to be the same for all values in the
-     range.  */
-
-  wide_int w = mask;
-  int m = 0, n = 0;
-  if (code == BIT_IOR_EXPR)
-    w = ~w;
-  if (wi::eq_p (w, 0))
-    n = w.get_precision ();
-  else
-    {
-      n = wi::ctz (w);
-      w = ~(w | wi::mask (n, false, w.get_precision ()));
-      if (wi::eq_p (w, 0))
-	m = w.get_precision () - n;
-      else
-	m = wi::ctz (w) - n;
-    }
-  wide_int new_mask = wi::mask (m + n, true, w.get_precision ());
-  if ((new_mask & lb) == (new_mask & ub))
-    return true;
-
-  return false;
-}
-
-/* Return TRUE if shifting by range [MIN, MAX] is undefined behavior.
-
-   FIXME: Make this inline when it moves outside of tree-vrp.  */
-
-bool
-wide_int_range_shift_undefined_p (signop sign, unsigned prec,
-				  const wide_int &min, const wide_int &max)
-{
-  /* ?? Note: The original comment said this only applied to
-     RSHIFT_EXPR, but it was being applied to both left and right
-     shifts.  Is this OK?  */
-
-  /* Shifting by any values outside [0..prec-1], gets undefined
-     behavior from the shift operation.  We cannot even trust
-     SHIFT_COUNT_TRUNCATED at this stage, because that applies to rtl
-     shifts, and the operation at the tree level may be widened.  */
-  return wi::lt_p (min, 0, sign) || wi::ge_p (max, prec, sign);
-}
-
-/* Calculate the XOR of two ranges and store the result in [WMIN,WMAX].
-   The two input ranges are described by their MUST_BE_NONZERO and
-   MAY_BE_NONZERO bit masks.
-
-   Return TRUE if we were able to successfully calculate the new range.  */
-
-bool
-wide_int_range_bit_xor (wide_int &wmin, wide_int &wmax,
-			signop sign,
-			unsigned prec,
-			const wide_int &must_be_nonzero0,
-			const wide_int &may_be_nonzero0,
-			const wide_int &must_be_nonzero1,
-			const wide_int &may_be_nonzero1)
-{
-  wide_int result_zero_bits = ((must_be_nonzero0 & must_be_nonzero1)
-			       | ~(may_be_nonzero0 | may_be_nonzero1));
-  wide_int result_one_bits
-    = (wi::bit_and_not (must_be_nonzero0, may_be_nonzero1)
-       | wi::bit_and_not (must_be_nonzero1, may_be_nonzero0));
-  wmax = ~result_zero_bits;
-  wmin = result_one_bits;
-  /* If the range has all positive or all negative values, the result
-     is better than VARYING.  */
-  if (wi::lt_p (wmin, 0, sign) || wi::ge_p (wmax, 0, sign))
-    return true;
-  wmin = wi::min_value (prec, sign);
-  wmax = wi::max_value (prec, sign);
-  return false;
-}
-
-/* Calculate the IOR of two ranges and store the result in [WMIN,WMAX].
-   Return TRUE if we were able to successfully calculate the new range.  */
-
-bool
-wide_int_range_bit_ior (wide_int &wmin, wide_int &wmax,
-			signop sign,
-			const wide_int &vr0_min,
-			const wide_int &vr0_max,
-			const wide_int &vr1_min,
-			const wide_int &vr1_max,
-			const wide_int &must_be_nonzero0,
-			const wide_int &may_be_nonzero0,
-			const wide_int &must_be_nonzero1,
-			const wide_int &may_be_nonzero1)
-{
-  wmin = must_be_nonzero0 | must_be_nonzero1;
-  wmax = may_be_nonzero0 | may_be_nonzero1;
-  /* If the input ranges contain only positive values we can
-     truncate the minimum of the result range to the maximum
-     of the input range minima.  */
-  if (wi::ge_p (vr0_min, 0, sign)
-      && wi::ge_p (vr1_min, 0, sign))
-    {
-      wmin = wi::max (wmin, vr0_min, sign);
-      wmin = wi::max (wmin, vr1_min, sign);
-    }
-  /* If either input range contains only negative values
-     we can truncate the minimum of the result range to the
-     respective minimum range.  */
-  if (wi::lt_p (vr0_max, 0, sign))
-    wmin = wi::max (wmin, vr0_min, sign);
-  if (wi::lt_p (vr1_max, 0, sign))
-    wmin = wi::max (wmin, vr1_min, sign);
-  /* If the limits got swapped around, indicate error so we can adjust
-     the range to VARYING.  */
-  if (wi::gt_p (wmin, wmax,sign))
-    return false;
-  return true;
-}
-
-/* Calculate the bitwise AND of two ranges and store the result in [WMIN,WMAX].
-   Return TRUE if we were able to successfully calculate the new range.  */
-
-bool
-wide_int_range_bit_and (wide_int &wmin, wide_int &wmax,
-			signop sign,
-			unsigned prec,
-			const wide_int &vr0_min,
-			const wide_int &vr0_max,
-			const wide_int &vr1_min,
-			const wide_int &vr1_max,
-			const wide_int &must_be_nonzero0,
-			const wide_int &may_be_nonzero0,
-			const wide_int &must_be_nonzero1,
-			const wide_int &may_be_nonzero1)
-{
-  wmin = must_be_nonzero0 & must_be_nonzero1;
-  wmax = may_be_nonzero0 & may_be_nonzero1;
-  /* If both input ranges contain only negative values we can
-     truncate the result range maximum to the minimum of the
-     input range maxima.  */
-  if (wi::lt_p (vr0_max, 0, sign) && wi::lt_p (vr1_max, 0, sign))
-    {
-      wmax = wi::min (wmax, vr0_max, sign);
-      wmax = wi::min (wmax, vr1_max, sign);
-    }
-  /* If either input range contains only non-negative values
-     we can truncate the result range maximum to the respective
-     maximum of the input range.  */
-  if (wi::ge_p (vr0_min, 0, sign))
-    wmax = wi::min (wmax, vr0_max, sign);
-  if (wi::ge_p (vr1_min, 0, sign))
-    wmax = wi::min (wmax, vr1_max, sign);
-  /* PR68217: In case of signed & sign-bit-CST should
-     result in [-INF, 0] instead of [-INF, INF].  */
-  if (wi::gt_p (wmin, wmax, sign))
-    {
-      wide_int sign_bit = wi::set_bit_in_zero (prec - 1, prec);
-      if (sign == SIGNED
-	  && ((wi::eq_p (vr0_min, vr0_max)
-	       && !wi::cmps (vr0_min, sign_bit))
-	      || (wi::eq_p (vr1_min, vr1_max)
-		  && !wi::cmps (vr1_min, sign_bit))))
-	{
-	  wmin = wi::min_value (prec, sign);
-	  wmax = wi::zero (prec);
-	}
-    }
-  /* If the limits got swapped around, indicate error so we can adjust
-     the range to VARYING.  */
-  if (wi::gt_p (wmin, wmax,sign))
-    return false;
-  return true;
-}
-
-/* Calculate TRUNC_MOD_EXPR on two ranges and store the result in
-   [WMIN,WMAX].  */
-
-void
-wide_int_range_trunc_mod (wide_int &wmin, wide_int &wmax,
-			  signop sign,
-			  unsigned prec,
-			  const wide_int &vr0_min,
-			  const wide_int &vr0_max,
-			  const wide_int &vr1_min,
-			  const wide_int &vr1_max)
-{
-  wide_int tmp;
-
-  /* ABS (A % B) < ABS (B) and either
-     0 <= A % B <= A or A <= A % B <= 0.  */
-  wmax = vr1_max - 1;
-  if (sign == SIGNED)
-    {
-      tmp = -1 - vr1_min;
-      wmax = wi::smax (wmax, tmp);
-    }
-
-  if (sign == UNSIGNED)
-    wmin = wi::zero (prec);
-  else
-    {
-      wmin = -wmax;
-      tmp = vr0_min;
-      if (wi::gts_p (tmp, 0))
-	tmp = wi::zero (prec);
-      wmin = wi::smax (wmin, tmp);
-    }
-  tmp = vr0_max;
-  if (sign == SIGNED && wi::neg_p (tmp))
-    tmp = wi::zero (prec);
-  wmax = wi::min (wmax, tmp, sign);
-}
-
 /* Extract the components of a value range into a pair of wide ints in
    [WMIN, WMAX].
 
diff --git a/gcc/tree-vrp.h b/gcc/tree-vrp.h
index 8cac7daada7..0c1fb3637cf 100644
--- a/gcc/tree-vrp.h
+++ b/gcc/tree-vrp.h
@@ -105,83 +105,6 @@  extern bool vrp_val_is_min (const_tree);
 extern bool vrp_val_is_max (const_tree);
 extern void copy_value_range (value_range *, value_range *);
 extern void set_value_range_to_value (value_range *, tree, bitmap);
-extern bool wide_int_range_cross_product (wide_int &res_lb, wide_int &res_ub,
-					  enum tree_code code, signop sign,
-					  const wide_int &, const wide_int &,
-					  const wide_int &, const wide_int &,
-					  bool overflow_undefined);
-extern bool wide_int_range_mult_wrapping (wide_int &res_lb,
-					  wide_int &res_ub,
-					  signop sign,
-					  unsigned prec,
-					  const wide_int &min0_,
-					  const wide_int &max0_,
-					  const wide_int &min1_,
-					  const wide_int &max1_);
-extern bool wide_int_range_multiplicative_op (wide_int &res_lb,
-					      wide_int &res_ub,
-					      enum tree_code code,
-					      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);
-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);
-extern bool wide_int_range_shift_undefined_p (signop sign, unsigned prec,
-					      const wide_int &min,
-					      const wide_int &max);
-extern void wide_int_set_zero_nonzero_bits (signop,
-					    const wide_int &lb,
-					    const wide_int &ub,
-					    wide_int &may_be_nonzero,
-					    wide_int &must_be_nonzero);
-extern bool wide_int_range_can_optimize_bit_op (tree_code,
-						const wide_int &lb,
-						const wide_int &ub,
-						const wide_int &mask);
-extern bool wide_int_range_bit_xor (wide_int &wmin, wide_int &wmax,
-				    signop sign,
-				    unsigned prec,
-				    const wide_int &must_be_nonzero0,
-				    const wide_int &may_be_nonzero0,
-				    const wide_int &must_be_nonzero1,
-				    const wide_int &may_be_nonzero1);
-extern bool wide_int_range_bit_ior (wide_int &wmin, wide_int &wmax,
-				    signop sign,
-				    const wide_int &vr0_min,
-				    const wide_int &vr0_max,
-				    const wide_int &vr1_min,
-				    const wide_int &vr1_max,
-				    const wide_int &must_be_nonzero0,
-				    const wide_int &may_be_nonzero0,
-				    const wide_int &must_be_nonzero1,
-				    const wide_int &may_be_nonzero1);
-extern bool wide_int_range_bit_and (wide_int &wmin, wide_int &wmax,
-				    signop sign,
-				    unsigned prec,
-				    const wide_int &vr0_min,
-				    const wide_int &vr0_max,
-				    const wide_int &vr1_min,
-				    const wide_int &vr1_max,
-				    const wide_int &must_be_nonzero0,
-				    const wide_int &may_be_nonzero0,
-				    const wide_int &must_be_nonzero1,
-				    const wide_int &may_be_nonzero1);
-extern void wide_int_range_trunc_mod (wide_int &wmin, wide_int &wmax,
-				      signop sign,
-				      unsigned prec,
-				      const wide_int &vr0_min,
-				      const wide_int &vr0_max,
-				      const wide_int &vr1_min,
-				      const wide_int &vr1_max);
 extern void extract_range_from_binary_expr_1 (value_range *, enum tree_code,
 					      tree, value_range *,
 					      value_range *);
diff --git a/gcc/wide-int-range.c b/gcc/wide-int-range.c
new file mode 100644
index 00000000000..5a8d9626d95
--- /dev/null
+++ b/gcc/wide-int-range.c
@@ -0,0 +1,626 @@ 
+/* Support routines for range operations on wide ints.
+   Copyright (C) 2018 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 3, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tree.h"
+#include "fold-const.h"
+#include "wide-int-range.h"
+
+/* Wrapper around wide_int_binop that adjusts for overflow.
+
+   Return true if we can compute the result; i.e. if the operation
+   doesn't overflow or if the overflow is undefined.  In the latter
+   case (if the operation overflows and overflow is undefined), then
+   adjust the result to be -INF or +INF depending on CODE, VAL1 and
+   VAL2.  Return the value in *RES.
+
+   Return false for division by zero, for which the result is
+   indeterminate.  */
+
+static bool
+wide_int_binop_overflow (wide_int &res,
+			 enum tree_code code,
+			 const wide_int &w0, const wide_int &w1,
+			 signop sign, bool overflow_undefined)
+{
+  wi::overflow_type overflow;
+  if (!wide_int_binop (res, code, w0, w1, sign, &overflow))
+    return false;
+
+  /* If the operation overflowed return -INF or +INF depending on the
+     operation and the combination of signs of the operands.  */
+  if (overflow && overflow_undefined)
+    {
+      switch (code)
+	{
+	case MULT_EXPR:
+	  /* For multiplication, the sign of the overflow is given
+	     by the comparison of the signs of the operands.  */
+	  if (sign == UNSIGNED || w0.sign_mask () == w1.sign_mask ())
+	    res = wi::max_value (w0.get_precision (), sign);
+	  else
+	    res = wi::min_value (w0.get_precision (), sign);
+	  return true;
+
+	case TRUNC_DIV_EXPR:
+	case FLOOR_DIV_EXPR:
+	case CEIL_DIV_EXPR:
+	case EXACT_DIV_EXPR:
+	case ROUND_DIV_EXPR:
+	  /* For division, the only case is -INF / -1 = +INF.  */
+	  res = wi::max_value (w0.get_precision (), sign);
+	  return true;
+
+	default:
+	  gcc_unreachable ();
+	}
+    }
+  return !overflow;
+}
+
+/* For range [LB, UB] compute two wide_int bit masks.
+
+   In the MAY_BE_NONZERO bit mask, if some bit is unset, it means that
+   for all numbers in the range the bit is 0, otherwise it might be 0
+   or 1.
+
+   In the MUST_BE_NONZERO bit mask, if some bit is set, it means that
+   for all numbers in the range the bit is 1, otherwise it might be 0
+   or 1.  */
+
+void
+wide_int_range_set_zero_nonzero_bits (signop sign,
+				      const wide_int &lb, const wide_int &ub,
+				      wide_int &may_be_nonzero,
+				      wide_int &must_be_nonzero)
+{
+  may_be_nonzero = wi::minus_one (lb.get_precision ());
+  must_be_nonzero = wi::zero (lb.get_precision ());
+
+  if (wi::eq_p (lb, ub))
+    {
+      may_be_nonzero = lb;
+      must_be_nonzero = may_be_nonzero;
+    }
+  else if (wi::ge_p (lb, 0, sign) || wi::lt_p (ub, 0, sign))
+    {
+      wide_int xor_mask = lb ^ ub;
+      may_be_nonzero = lb | ub;
+      must_be_nonzero = lb & ub;
+      if (xor_mask != 0)
+	{
+	  wide_int mask = wi::mask (wi::floor_log2 (xor_mask), false,
+				    may_be_nonzero.get_precision ());
+	  may_be_nonzero = may_be_nonzero | mask;
+	  must_be_nonzero = wi::bit_and_not (must_be_nonzero, mask);
+	}
+    }
+}
+
+/* Order 2 sets of wide int ranges (w0/w1, w2/w3) and set MIN/MAX
+   accordingly.  */
+
+static void
+wide_int_range_min_max (wide_int &min, wide_int &max,
+			wide_int &w0, wide_int &w1, wide_int &w2, wide_int &w3,
+			signop sign)
+{
+  /* Order pairs w0,w1 and w2,w3.  */
+  if (wi::gt_p (w0, w1, sign))
+    std::swap (w0, w1);
+  if (wi::gt_p (w2, w3, sign))
+    std::swap (w2, w3);
+
+  /* Choose min and max from the ordered pairs.  */
+  min = wi::min (w0, w2, sign);
+  max = wi::max (w1, w3, sign);
+}
+
+/* Calculate the cross product of two sets of ranges (VR0 and VR1) and
+   store the result in [RES_LB, RES_UB].
+
+   CODE is the operation to perform with sign SIGN.
+
+   OVERFLOW_UNDEFINED is set if overflow is undefined for the operation type.
+
+   Return TRUE if we were able to calculate the cross product.  */
+
+bool
+wide_int_range_cross_product (wide_int &res_lb, wide_int &res_ub,
+			      enum tree_code code, signop sign,
+			      const wide_int &vr0_lb, const wide_int &vr0_ub,
+			      const wide_int &vr1_lb, const wide_int &vr1_ub,
+			      bool overflow_undefined)
+{
+  wide_int cp1, cp2, cp3, cp4;
+
+  /* Compute the 4 cross operations, bailing if we get an overflow we
+     can't handle.  */
+
+  if (!wide_int_binop_overflow (cp1, code, vr0_lb, vr1_lb, sign,
+				overflow_undefined))
+    return false;
+
+  if (wi::eq_p (vr0_lb, vr0_ub))
+    cp3 = cp1;
+  else if (!wide_int_binop_overflow (cp3, code, vr0_ub, vr1_lb, sign,
+				     overflow_undefined))
+    return false;
+
+  if (wi::eq_p (vr1_lb, vr1_ub))
+    cp2 = cp1;
+  else if (!wide_int_binop_overflow (cp2, code, vr0_lb, vr1_ub, sign,
+				     overflow_undefined))
+    return false;
+
+  if (wi::eq_p (vr0_lb, vr0_ub))
+    cp4 = cp2;
+  else if (!wide_int_binop_overflow (cp4, code, vr0_ub, vr1_ub, sign,
+				     overflow_undefined))
+    return false;
+
+  wide_int_range_min_max (res_lb, res_ub, cp1, cp2, cp3, cp4, sign);
+  return true;
+}
+
+/* Multiply two ranges when TYPE_OVERFLOW_WRAPS:
+
+     [RES_LB, RES_UB] = [MIN0, MAX0] * [MIN1, MAX1]
+
+   This is basically fancy code so we don't drop to varying with an
+   unsigned [-3,-1]*[-3,-1].
+
+   Return TRUE if we were able to perform the operation.  */
+
+bool
+wide_int_range_mult_wrapping (wide_int &res_lb,
+			      wide_int &res_ub,
+			      signop sign,
+			      unsigned prec,
+			      const wide_int &min0_,
+			      const wide_int &max0_,
+			      const wide_int &min1_,
+			      const wide_int &max1_)
+{
+  /* This test requires 2*prec bits if both operands are signed and
+     2*prec + 2 bits if either is not.  Therefore, extend the values
+     using the sign of the result to PREC2.  From here on out,
+     everthing is just signed math no matter what the input types
+     were.  */
+  widest2_int min0 = widest2_int::from (min0_, sign);
+  widest2_int max0 = widest2_int::from (max0_, sign);
+  widest2_int min1 = widest2_int::from (min1_, sign);
+  widest2_int max1 = widest2_int::from (max1_, sign);
+  widest2_int sizem1 = wi::mask <widest2_int> (prec, false);
+  widest2_int size = sizem1 + 1;
+
+  /* Canonicalize the intervals.  */
+  if (sign == UNSIGNED)
+    {
+      if (wi::ltu_p (size, min0 + max0))
+	{
+	  min0 -= size;
+	  max0 -= size;
+	}
+
+      if (wi::ltu_p (size, min1 + max1))
+	{
+	  min1 -= size;
+	  max1 -= size;
+	}
+    }
+
+  widest2_int prod0 = min0 * min1;
+  widest2_int prod1 = min0 * max1;
+  widest2_int prod2 = max0 * min1;
+  widest2_int prod3 = max0 * max1;
+
+  /* Sort the 4 products so that min is in prod0 and max is in
+     prod3.  */
+  /* min0min1 > max0max1 */
+  if (prod0 > prod3)
+    std::swap (prod0, prod3);
+
+  /* min0max1 > max0min1 */
+  if (prod1 > prod2)
+    std::swap (prod1, prod2);
+
+  if (prod0 > prod1)
+    std::swap (prod0, prod1);
+
+  if (prod2 > prod3)
+    std::swap (prod2, prod3);
+
+  /* diff = max - min.  */
+  prod2 = prod3 - prod0;
+  if (wi::geu_p (prod2, sizem1))
+    /* The range covers all values.  */
+    return false;
+
+  res_lb = wide_int::from (prod0, prec, sign);
+  res_ub = wide_int::from (prod3, prec, sign);
+  return true;
+}
+
+/* Perform multiplicative operation CODE on two ranges:
+
+     [RES_LB, RES_UB] = [VR0_LB, VR0_UB] .CODE. [VR1_LB, VR1_LB]
+
+   Return TRUE if we were able to perform the operation.
+
+   NOTE: If code is MULT_EXPR and TYPE_OVERFLOW_WRAPS, the resulting
+   range must be canonicalized by the caller because its components
+   may be swapped.  */
+
+bool
+wide_int_range_multiplicative_op (wide_int &res_lb, wide_int &res_ub,
+				  enum tree_code code,
+				  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)
+{
+  /* Multiplications, divisions and shifts are a bit tricky to handle,
+     depending on the mix of signs we have in the two ranges, we
+     need to operate on different values to get the minimum and
+     maximum values for the new range.  One approach is to figure
+     out all the variations of range combinations and do the
+     operations.
+
+     However, this involves several calls to compare_values and it
+     is pretty convoluted.  It's simpler to do the 4 operations
+     (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)
+    return wide_int_range_mult_wrapping (res_lb, res_ub,
+					 sign, prec,
+					 vr0_lb, vr0_ub, vr1_lb, vr1_ub);
+  return wide_int_range_cross_product (res_lb, res_ub,
+				       code, sign,
+				       vr0_lb, vr0_ub, vr1_lb, vr1_ub,
+				       overflow_undefined);
+}
+
+/* Perform a left shift operation on two ranges:
+
+     [RES_LB, RES_UB] = [VR0_LB, VR0_UB] << [VR1_LB, VR1_LB]
+
+   Return TRUE if we were able to perform the operation.
+
+   NOTE: The resulting range must be canonicalized by the caller
+   because its contents components may be swapped.  */
+
+bool
+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)
+{
+  /* Transform left shifts by constants into multiplies.  */
+  if (wi::eq_p (vr1_lb, vr1_ub))
+    {
+      int shift = wi::extract_uhwi (vr1_ub, 0, vr1_ub.get_precision ());
+      wide_int tmp = wi::set_bit_in_zero (shift, prec);
+      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);
+    }
+
+  int overflow_pos = prec;
+  if (sign == SIGNED)
+    overflow_pos -= 1;
+  int bound_shift = overflow_pos - vr1_ub.to_shwi ();
+  /* If bound_shift == HOST_BITS_PER_WIDE_INT, the llshift can
+     overflow.  However, for that to happen, vr1.max needs to be
+     zero, which means vr1 is a singleton range of zero, which
+     means it should be handled by the previous LSHIFT_EXPR
+     if-clause.  */
+  wide_int bound = wi::set_bit_in_zero (bound_shift, prec);
+  wide_int complement = ~(bound - 1);
+  wide_int low_bound, high_bound;
+  bool in_bounds = false;
+  if (sign == UNSIGNED)
+    {
+      low_bound = bound;
+      high_bound = complement;
+      if (wi::ltu_p (vr0_ub, low_bound))
+	{
+	  /* [5, 6] << [1, 2] == [10, 24].  */
+	  /* We're shifting out only zeroes, the value increases
+	     monotonically.  */
+	  in_bounds = true;
+	}
+      else if (wi::ltu_p (high_bound, vr0_lb))
+	{
+	  /* [0xffffff00, 0xffffffff] << [1, 2]
+	     == [0xfffffc00, 0xfffffffe].  */
+	  /* We're shifting out only ones, the value decreases
+	     monotonically.  */
+	  in_bounds = true;
+	}
+    }
+  else
+    {
+      /* [-1, 1] << [1, 2] == [-4, 4].  */
+      low_bound = complement;
+      high_bound = bound;
+      if (wi::lts_p (vr0_ub, high_bound)
+	  && wi::lts_p (low_bound, vr0_lb))
+	{
+	  /* For non-negative numbers, we're shifting out only
+	     zeroes, the value increases monotonically.
+	     For negative numbers, we're shifting out only ones, the
+	     value decreases monotomically.  */
+	  in_bounds = true;
+	}
+    }
+  if (in_bounds)
+    return wide_int_range_multiplicative_op (res_lb, res_ub,
+					     LSHIFT_EXPR, sign, prec,
+					     vr0_lb, vr0_ub,
+					     vr1_lb, vr1_ub,
+					     overflow_undefined,
+					     overflow_wraps);
+  return false;
+}
+
+/* Return TRUE if a bit operation on two ranges can be easily
+   optimized in terms of a mask.
+
+   Basically, for BIT_AND_EXPR or BIT_IOR_EXPR see if we can optimize:
+
+	[LB, UB] op Z
+   into:
+	[LB op Z, UB op Z]
+
+   It is up to the caller to perform the actual folding above.  */
+
+bool
+wide_int_range_can_optimize_bit_op (tree_code code,
+				    const wide_int &lb, const wide_int &ub,
+				    const wide_int &mask)
+
+{
+  if (code != BIT_AND_EXPR && code != BIT_IOR_EXPR)
+    return false;
+  /* If Z is a constant which (for op | its bitwise not) has n
+     consecutive least significant bits cleared followed by m 1
+     consecutive bits set immediately above it and either
+     m + n == precision, or (x >> (m + n)) == (y >> (m + n)).
+
+     The least significant n bits of all the values in the range are
+     cleared or set, the m bits above it are preserved and any bits
+     above these are required to be the same for all values in the
+     range.  */
+
+  wide_int w = mask;
+  int m = 0, n = 0;
+  if (code == BIT_IOR_EXPR)
+    w = ~w;
+  if (wi::eq_p (w, 0))
+    n = w.get_precision ();
+  else
+    {
+      n = wi::ctz (w);
+      w = ~(w | wi::mask (n, false, w.get_precision ()));
+      if (wi::eq_p (w, 0))
+	m = w.get_precision () - n;
+      else
+	m = wi::ctz (w) - n;
+    }
+  wide_int new_mask = wi::mask (m + n, true, w.get_precision ());
+  if ((new_mask & lb) == (new_mask & ub))
+    return true;
+
+  return false;
+}
+
+/* Return TRUE if shifting by range [MIN, MAX] is undefined behavior.
+
+   FIXME: Make this inline when it moves outside of tree-vrp.  */
+
+bool
+wide_int_range_shift_undefined_p (signop sign, unsigned prec,
+				  const wide_int &min, const wide_int &max)
+{
+  /* ?? Note: The original comment said this only applied to
+     RSHIFT_EXPR, but it was being applied to both left and right
+     shifts.  Is this OK?  */
+
+  /* Shifting by any values outside [0..prec-1], gets undefined
+     behavior from the shift operation.  We cannot even trust
+     SHIFT_COUNT_TRUNCATED at this stage, because that applies to rtl
+     shifts, and the operation at the tree level may be widened.  */
+  return wi::lt_p (min, 0, sign) || wi::ge_p (max, prec, sign);
+}
+
+/* Calculate the XOR of two ranges and store the result in [WMIN,WMAX].
+   The two input ranges are described by their MUST_BE_NONZERO and
+   MAY_BE_NONZERO bit masks.
+
+   Return TRUE if we were able to successfully calculate the new range.  */
+
+bool
+wide_int_range_bit_xor (wide_int &wmin, wide_int &wmax,
+			signop sign,
+			unsigned prec,
+			const wide_int &must_be_nonzero0,
+			const wide_int &may_be_nonzero0,
+			const wide_int &must_be_nonzero1,
+			const wide_int &may_be_nonzero1)
+{
+  wide_int result_zero_bits = ((must_be_nonzero0 & must_be_nonzero1)
+			       | ~(may_be_nonzero0 | may_be_nonzero1));
+  wide_int result_one_bits
+    = (wi::bit_and_not (must_be_nonzero0, may_be_nonzero1)
+       | wi::bit_and_not (must_be_nonzero1, may_be_nonzero0));
+  wmax = ~result_zero_bits;
+  wmin = result_one_bits;
+  /* If the range has all positive or all negative values, the result
+     is better than VARYING.  */
+  if (wi::lt_p (wmin, 0, sign) || wi::ge_p (wmax, 0, sign))
+    return true;
+  wmin = wi::min_value (prec, sign);
+  wmax = wi::max_value (prec, sign);
+  return false;
+}
+
+/* Calculate the IOR of two ranges and store the result in [WMIN,WMAX].
+   Return TRUE if we were able to successfully calculate the new range.  */
+
+bool
+wide_int_range_bit_ior (wide_int &wmin, wide_int &wmax,
+			signop sign,
+			const wide_int &vr0_min,
+			const wide_int &vr0_max,
+			const wide_int &vr1_min,
+			const wide_int &vr1_max,
+			const wide_int &must_be_nonzero0,
+			const wide_int &may_be_nonzero0,
+			const wide_int &must_be_nonzero1,
+			const wide_int &may_be_nonzero1)
+{
+  wmin = must_be_nonzero0 | must_be_nonzero1;
+  wmax = may_be_nonzero0 | may_be_nonzero1;
+  /* If the input ranges contain only positive values we can
+     truncate the minimum of the result range to the maximum
+     of the input range minima.  */
+  if (wi::ge_p (vr0_min, 0, sign)
+      && wi::ge_p (vr1_min, 0, sign))
+    {
+      wmin = wi::max (wmin, vr0_min, sign);
+      wmin = wi::max (wmin, vr1_min, sign);
+    }
+  /* If either input range contains only negative values
+     we can truncate the minimum of the result range to the
+     respective minimum range.  */
+  if (wi::lt_p (vr0_max, 0, sign))
+    wmin = wi::max (wmin, vr0_min, sign);
+  if (wi::lt_p (vr1_max, 0, sign))
+    wmin = wi::max (wmin, vr1_min, sign);
+  /* If the limits got swapped around, indicate error so we can adjust
+     the range to VARYING.  */
+  if (wi::gt_p (wmin, wmax,sign))
+    return false;
+  return true;
+}
+
+/* Calculate the bitwise AND of two ranges and store the result in [WMIN,WMAX].
+   Return TRUE if we were able to successfully calculate the new range.  */
+
+bool
+wide_int_range_bit_and (wide_int &wmin, wide_int &wmax,
+			signop sign,
+			unsigned prec,
+			const wide_int &vr0_min,
+			const wide_int &vr0_max,
+			const wide_int &vr1_min,
+			const wide_int &vr1_max,
+			const wide_int &must_be_nonzero0,
+			const wide_int &may_be_nonzero0,
+			const wide_int &must_be_nonzero1,
+			const wide_int &may_be_nonzero1)
+{
+  wmin = must_be_nonzero0 & must_be_nonzero1;
+  wmax = may_be_nonzero0 & may_be_nonzero1;
+  /* If both input ranges contain only negative values we can
+     truncate the result range maximum to the minimum of the
+     input range maxima.  */
+  if (wi::lt_p (vr0_max, 0, sign) && wi::lt_p (vr1_max, 0, sign))
+    {
+      wmax = wi::min (wmax, vr0_max, sign);
+      wmax = wi::min (wmax, vr1_max, sign);
+    }
+  /* If either input range contains only non-negative values
+     we can truncate the result range maximum to the respective
+     maximum of the input range.  */
+  if (wi::ge_p (vr0_min, 0, sign))
+    wmax = wi::min (wmax, vr0_max, sign);
+  if (wi::ge_p (vr1_min, 0, sign))
+    wmax = wi::min (wmax, vr1_max, sign);
+  /* PR68217: In case of signed & sign-bit-CST should
+     result in [-INF, 0] instead of [-INF, INF].  */
+  if (wi::gt_p (wmin, wmax, sign))
+    {
+      wide_int sign_bit = wi::set_bit_in_zero (prec - 1, prec);
+      if (sign == SIGNED
+	  && ((wi::eq_p (vr0_min, vr0_max)
+	       && !wi::cmps (vr0_min, sign_bit))
+	      || (wi::eq_p (vr1_min, vr1_max)
+		  && !wi::cmps (vr1_min, sign_bit))))
+	{
+	  wmin = wi::min_value (prec, sign);
+	  wmax = wi::zero (prec);
+	}
+    }
+  /* If the limits got swapped around, indicate error so we can adjust
+     the range to VARYING.  */
+  if (wi::gt_p (wmin, wmax,sign))
+    return false;
+  return true;
+}
+
+/* Calculate TRUNC_MOD_EXPR on two ranges and store the result in
+   [WMIN,WMAX].  */
+
+void
+wide_int_range_trunc_mod (wide_int &wmin, wide_int &wmax,
+			  signop sign,
+			  unsigned prec,
+			  const wide_int &vr0_min,
+			  const wide_int &vr0_max,
+			  const wide_int &vr1_min,
+			  const wide_int &vr1_max)
+{
+  wide_int tmp;
+
+  /* ABS (A % B) < ABS (B) and either
+     0 <= A % B <= A or A <= A % B <= 0.  */
+  wmax = vr1_max - 1;
+  if (sign == SIGNED)
+    {
+      tmp = -1 - vr1_min;
+      wmax = wi::smax (wmax, tmp);
+    }
+
+  if (sign == UNSIGNED)
+    wmin = wi::zero (prec);
+  else
+    {
+      wmin = -wmax;
+      tmp = vr0_min;
+      if (wi::gts_p (tmp, 0))
+	tmp = wi::zero (prec);
+      wmin = wi::smax (wmin, tmp);
+    }
+  tmp = vr0_max;
+  if (sign == SIGNED && wi::neg_p (tmp))
+    tmp = wi::zero (prec);
+  wmax = wi::min (wmax, tmp, sign);
+}
diff --git a/gcc/wide-int-range.h b/gcc/wide-int-range.h
new file mode 100644
index 00000000000..6d8044aa8f5
--- /dev/null
+++ b/gcc/wide-int-range.h
@@ -0,0 +1,100 @@ 
+/* Support routines for range operations on wide ints.
+   Copyright (C) 2018 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 3, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#ifndef GCC_WIDE_INT_RANGE_H
+#define GCC_WIDE_INT_RANGE_H
+
+extern bool wide_int_range_cross_product (wide_int &res_lb, wide_int &res_ub,
+					  enum tree_code code, signop sign,
+					  const wide_int &, const wide_int &,
+					  const wide_int &, const wide_int &,
+					  bool overflow_undefined);
+extern bool wide_int_range_mult_wrapping (wide_int &res_lb,
+					  wide_int &res_ub,
+					  signop sign,
+					  unsigned prec,
+					  const wide_int &min0_,
+					  const wide_int &max0_,
+					  const wide_int &min1_,
+					  const wide_int &max1_);
+extern bool wide_int_range_multiplicative_op (wide_int &res_lb,
+					      wide_int &res_ub,
+					      enum tree_code code,
+					      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);
+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);
+extern bool wide_int_range_shift_undefined_p (signop sign, unsigned prec,
+					      const wide_int &min,
+					      const wide_int &max);
+extern void wide_int_range_set_zero_nonzero_bits (signop,
+						  const wide_int &lb,
+						  const wide_int &ub,
+						  wide_int &may_be_nonzero,
+						  wide_int &must_be_nonzero);
+extern bool wide_int_range_can_optimize_bit_op (tree_code,
+						const wide_int &lb,
+						const wide_int &ub,
+						const wide_int &mask);
+extern bool wide_int_range_bit_xor (wide_int &wmin, wide_int &wmax,
+				    signop sign,
+				    unsigned prec,
+				    const wide_int &must_be_nonzero0,
+				    const wide_int &may_be_nonzero0,
+				    const wide_int &must_be_nonzero1,
+				    const wide_int &may_be_nonzero1);
+extern bool wide_int_range_bit_ior (wide_int &wmin, wide_int &wmax,
+				    signop sign,
+				    const wide_int &vr0_min,
+				    const wide_int &vr0_max,
+				    const wide_int &vr1_min,
+				    const wide_int &vr1_max,
+				    const wide_int &must_be_nonzero0,
+				    const wide_int &may_be_nonzero0,
+				    const wide_int &must_be_nonzero1,
+				    const wide_int &may_be_nonzero1);
+extern bool wide_int_range_bit_and (wide_int &wmin, wide_int &wmax,
+				    signop sign,
+				    unsigned prec,
+				    const wide_int &vr0_min,
+				    const wide_int &vr0_max,
+				    const wide_int &vr1_min,
+				    const wide_int &vr1_max,
+				    const wide_int &must_be_nonzero0,
+				    const wide_int &may_be_nonzero0,
+				    const wide_int &must_be_nonzero1,
+				    const wide_int &may_be_nonzero1);
+extern void wide_int_range_trunc_mod (wide_int &wmin, wide_int &wmax,
+				      signop sign,
+				      unsigned prec,
+				      const wide_int &vr0_min,
+				      const wide_int &vr0_max,
+				      const wide_int &vr1_min,
+				      const wide_int &vr1_max);
+#endif /* GCC_WIDE_INT_RANGE_H */