cleanup cross product code in VRP

[Aldy Hernandez <aldyh at redhat dot com>]

Howdy!

I've abstracted out the cross product calculations into its own 
function, and have adapted it to deal with wide ints so it's more 
reusable.  It required some shuffling around, and implementing things a 
bit different, but things should be behave as before.

I also renamed vrp_int_const_binop to make its intent clearer, 
especially now that it's really just a wrapper to wide_int_binop that 
deals with overflow.

(If wide_int_binop_overflow is generally useful, perhaps we could merge 
it with wide_int_overflow.)

Tested on x86-64 Linux.

OK?

commit eb55ab7557efb23bc6dc34d00eadabf2a73a4995
Author: Aldy Hernandez <aldyh@redhat.com>
Date:   Mon Jul 16 14:15:37 2018 +0200

            * tree-vrp.c (wide_int_binop_overflow): Rename from
            vrp_int_const_binop.
            Rewrite to work on trees.
            (extract_range_from_multiplicative_op_1): Abstract code to...
            (wide_int_range_min_max): ...here.
            (wide_int_range_cross_product): ...and here.
            * tree-vrp.h (wide_int_range_cross_product): New.

diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 2e1ee86a161..36349228c10 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -968,64 +968,43 @@ value_range_constant_singleton (value_range *vr)
    indeterminate.  */
 
 static bool
-vrp_int_const_binop (enum tree_code code, tree val1, tree val2, wide_int *res)
+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 = wi::OVF_NONE;
-  signop sign = TYPE_SIGN (TREE_TYPE (val1));
-  wide_int w1 = wi::to_wide (val1);
-  wide_int w2 = wi::to_wide (val2);
-
-  switch (code)
-    {
-    case RSHIFT_EXPR:
-    case LSHIFT_EXPR:
-      w2 = wi::to_wide (val2, TYPE_PRECISION (TREE_TYPE (val1)));
-      /* FALLTHRU */
-    case MULT_EXPR:
-    case TRUNC_DIV_EXPR:
-    case EXACT_DIV_EXPR:
-    case FLOOR_DIV_EXPR:
-    case CEIL_DIV_EXPR:
-    case ROUND_DIV_EXPR:
-      if (!wide_int_binop (*res, code, w1, w2, sign, &overflow))
-	return false;
-      break;
-
-    default:
-      gcc_unreachable ();
-    }
+  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
-      && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (val1)))
-    {
-      int sign1 = tree_int_cst_sgn (val1);
-      int sign2 = tree_int_cst_sgn (val2);
-
-      /* Notice that we only need to handle the restricted set of
-	 operations handled by extract_range_from_binary_expr.
-	 Among them, only multiplication, addition and subtraction
-	 can yield overflow without overflown operands because we
-	 are working with integral types only... except in the
-	 case VAL1 = -INF and VAL2 = -1 which overflows to +INF
-	 for division too.  */
-
-      /* For multiplication, the sign of the overflow is given
-	 by the comparison of the signs of the operands.  */
-      if ((code == MULT_EXPR && sign1 == sign2)
+  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.  */
-	  || code == TRUNC_DIV_EXPR
-	  || code == FLOOR_DIV_EXPR
-	  || code == CEIL_DIV_EXPR
-	  || code == EXACT_DIV_EXPR
-	  || code == ROUND_DIV_EXPR)
-	*res = wi::max_value (TYPE_PRECISION (TREE_TYPE (val1)), sign);
-      else
-	*res = wi::min_value (TYPE_PRECISION (TREE_TYPE (val1)), sign);
-      return true;
-    }
+	  res = wi::max_value (w0.get_precision (), sign);
+	  return true;
 
+	default:
+	  gcc_unreachable ();
+	}
+    }
   return !overflow;
 }
 
@@ -1127,6 +1106,72 @@ 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;
+}
+
 /* Helper to extract a value-range *VR for a multiplicative operation
    *VR0 CODE *VR1.  */
 
@@ -1135,10 +1180,6 @@ extract_range_from_multiplicative_op_1 (value_range *vr,
 					enum tree_code code,
 					value_range *vr0, value_range *vr1)
 {
-  enum value_range_type rtype;
-  wide_int val, min, max;
-  tree type;
-
   /* 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
@@ -1162,79 +1203,25 @@ extract_range_from_multiplicative_op_1 (value_range *vr,
   gcc_assert (vr0->type == VR_RANGE
 	      && vr0->type == vr1->type);
 
-  rtype = vr0->type;
-  type = TREE_TYPE (vr0->min);
-  signop sgn = TYPE_SIGN (type);
-
-  /* Compute the 4 cross operations and their minimum and maximum value.  */
-  if (!vrp_int_const_binop (code, vr0->min, vr1->min, &val))
-    {
-      set_value_range_to_varying (vr);
-      return;
-    }
-  min = max = val;
-
-  if (vr1->max != vr1->min)
-    {
-      if (!vrp_int_const_binop (code, vr0->min, vr1->max, &val))
-	{
-	  set_value_range_to_varying (vr);
-	  return;
-	}
-      if (wi::lt_p (val, min, sgn))
-	min = val;
-      else if (wi::gt_p (val, max, sgn))
-	max = val;
-    }
-
-  if (vr0->max != vr0->min)
-    {
-      if (!vrp_int_const_binop (code, vr0->max, vr1->min, &val))
-	{
-	  set_value_range_to_varying (vr);
-	  return;
-	}
-      if (wi::lt_p (val, min, sgn))
-	min = val;
-      else if (wi::gt_p (val, max, sgn))
-	max = val;
-    }
-
-  if (vr0->min != vr0->max && vr1->min != vr1->max)
-    {
-      if (!vrp_int_const_binop (code, vr0->max, vr1->max, &val))
-	{
-	  set_value_range_to_varying (vr);
-	  return;
-	}
-      if (wi::lt_p (val, min, sgn))
-	min = val;
-      else if (wi::gt_p (val, max, sgn))
-	max = val;
-    }
+  tree type = TREE_TYPE (vr0->min);
+  wide_int res_lb, res_ub;
+  wide_int vr0_lb = wi::to_wide (vr0->min);
+  wide_int vr0_ub = wi::to_wide (vr0->max);
+  wide_int vr1_lb = wi::to_wide (vr1->min);
+  wide_int vr1_ub = wi::to_wide (vr1->max);
+  bool overflow_undefined = TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (vr0->min));
 
-  /* If the new range has its limits swapped around (MIN > MAX),
-     then the operation caused one of them to wrap around, mark
-     the new range VARYING.  */
-  if (wi::gt_p (min, max, sgn))
+  if (!wide_int_range_cross_product (res_lb, res_ub,
+				     code, TYPE_SIGN (type),
+				     vr0_lb, vr0_ub, vr1_lb, vr1_ub,
+				     overflow_undefined))
     {
       set_value_range_to_varying (vr);
       return;
     }
-
-  /* We punt for [-INF, +INF].
-     We learn nothing when we have INF on both sides.
-     Note that we do accept [-INF, -INF] and [+INF, +INF].  */
-  if (wi::eq_p (min, wi::min_value (TYPE_PRECISION (type), sgn))
-      && wi::eq_p (max, wi::max_value (TYPE_PRECISION (type), sgn)))
-    {
-      set_value_range_to_varying (vr);
-      return;
-    }
-
-  set_value_range (vr, rtype,
-		   wide_int_to_tree (type, min),
-		   wide_int_to_tree (type, max), NULL);
+  set_value_range (vr, VR_RANGE,
+		   wide_int_to_tree (type, res_lb),
+		   wide_int_to_tree (type, res_ub), NULL);
 }
 
 /* For op & or | attempt to optimize:
diff --git a/gcc/tree-vrp.h b/gcc/tree-vrp.h
index 946e26e29b4..cd93e3af3b8 100644
--- a/gcc/tree-vrp.h
+++ b/gcc/tree-vrp.h
@@ -102,6 +102,11 @@ 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 void extract_range_from_binary_expr_1 (value_range *, enum tree_code,
 					      tree, value_range *,
 					      value_range *);