[PATCH] Simplify VRP vrp_int_const_binop

[PATCH] Simplify VRP vrp_int_const_binop

[Richard Biener]

The following avoids using trees with TREE_OVERFLOW in vrp_int_const_binop
which is GC memory heavy and simplifies vrp_int_const_binop by
using wide_ints (instead of implementing unsigned overflow detection
manually).

Bootstrapped and tested on x86_64-unknown-linux-gnu, applied to trunk.

Richard.

2017-05-09  Richard Biener  <rguenther@suse.de>

	* tree-vrp.c (vrp_int_const_binop): Use wide-ints and simplify.
	(extract_range_from_multiplicative_op_1): Adjust.
	(extract_range_from_binary_expr_1): Use int_const_binop.

Index: gcc/tree-vrp.c
===================================================================
--- gcc/tree-vrp.c	(revision 247733)
+++ gcc/tree-vrp.c	(working copy)
@@ -1617,66 +1613,91 @@ extract_range_from_ssa_name (value_range
 /* Wrapper around int_const_binop.  If the operation overflows and we
    are not using wrapping arithmetic, then adjust the result to be
    -INF or +INF depending on CODE, VAL1 and VAL2.  This can return
-   NULL_TREE if we need to use an overflow infinity representation but
-   the type does not support it.  */
+   NULL_TREE for division by zero.  */
 
-static tree
-vrp_int_const_binop (enum tree_code code, tree val1, tree val2)
+static wide_int
+vrp_int_const_binop (enum tree_code code, tree val1, tree val2,
+		     bool *overflow_p)
 {
-  tree res;
-
-  res = int_const_binop (code, val1, val2);
+  bool overflow = false;
+  signop sign = TYPE_SIGN (TREE_TYPE (val1));
+  wide_int res;
 
-  /* If we are using unsigned arithmetic, operate symbolically
-     on -INF and +INF as int_const_binop only handles signed overflow.  */
-  if (TYPE_UNSIGNED (TREE_TYPE (val1)))
+  switch (code)
     {
-      int checkz = compare_values (res, val1);
-      bool overflow = false;
+    case RSHIFT_EXPR:
+    case LSHIFT_EXPR:
+      {
+	wide_int wval2 = wi::to_wide (val2, TYPE_PRECISION (TREE_TYPE (val1)));
+	if (wi::neg_p (wval2))
+	  {
+	    wval2 = -wval2;
+	    if (code == RSHIFT_EXPR)
+	      code = LSHIFT_EXPR;
+	    else
+	      code = RSHIFT_EXPR;
+	  }
 
-      /* Ensure that res = val1 [+*] val2 >= val1
-         or that res = val1 - val2 <= val1.  */
-      if ((code == PLUS_EXPR
-	   && !(checkz == 1 || checkz == 0))
-          || (code == MINUS_EXPR
-	      && !(checkz == 0 || checkz == -1)))
+	if (code == RSHIFT_EXPR)
+	  /* It's unclear from the C standard whether shifts can overflow.
+	     The following code ignores overflow; perhaps a C standard
+	     interpretation ruling is needed.  */
+	  res = wi::rshift (val1, wval2, sign);
+	else
+	  res = wi::lshift (val1, wval2);
+	break;
+      }
+
+    case MULT_EXPR:
+      res = wi::mul (val1, val2, sign, &overflow);
+      break;
+
+    case TRUNC_DIV_EXPR:
+    case EXACT_DIV_EXPR:
+      if (val2 == 0)
 	{
-	  overflow = true;
+	  *overflow_p = true;
+	  return res;
 	}
-      /* Checking for multiplication overflow is done by dividing the
-	 output of the multiplication by the first input of the
-	 multiplication.  If the result of that division operation is
-	 not equal to the second input of the multiplication, then the
-	 multiplication overflowed.  */
-      else if (code == MULT_EXPR && !integer_zerop (val1))
+      else
+	res = wi::div_trunc (val1, val2, sign, &overflow);
+      break;
+
+    case FLOOR_DIV_EXPR:
+      if (val2 == 0)
 	{
-	  tree tmp = int_const_binop (TRUNC_DIV_EXPR,
-				      res,
-				      val1);
-	  int check = compare_values (tmp, val2);
+	  *overflow_p = true;
+	  return res;
+	}
+      res = wi::div_floor (val1, val2, sign, &overflow);
+      break;
 
-	  if (check != 0)
-	    overflow = true;
+    case CEIL_DIV_EXPR:
+      if (val2 == 0)
+	{
+	  *overflow_p = true;
+	  return res;
 	}
+      res = wi::div_ceil (val1, val2, sign, &overflow);
+      break;
 
-      if (overflow)
+    case ROUND_DIV_EXPR:
+      if (val2 == 0)
 	{
-	  res = copy_node (res);
-	  TREE_OVERFLOW (res) = 1;
+	  *overflow_p = 0;
+	  return res;
 	}
+      res = wi::div_round (val1, val2, sign, &overflow);
+      break;
 
+    default:
+      gcc_unreachable ();
     }
-  else if (TYPE_OVERFLOW_WRAPS (TREE_TYPE (val1)))
-    /* If the singed operation wraps then int_const_binop has done
-       everything we want.  */
-    ;
-  /* Signed division of -1/0 overflows and by the time it gets here
-     returns NULL_TREE.  */
-  else if (!res)
-    return NULL_TREE;
-  else if (TREE_OVERFLOW (res)
-	   && ! TREE_OVERFLOW (val1)
-	   && ! TREE_OVERFLOW (val2))
+
+  *overflow_p = overflow;
+
+  if (overflow
+      && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (val1)))
     {
       /* If the operation overflowed but neither VAL1 nor VAL2 are
 	 overflown, return -INF or +INF depending on the operation
@@ -1710,17 +1731,18 @@ vrp_int_const_binop (enum tree_code code
 	     overflow direction is the same as the sign of val1.
 	     Actually rshift does not overflow at all, but we only
 	     handle the case of shifting overflowed -INF and +INF.  */
-	  || (code == RSHIFT_EXPR
-	      && sgn1 >= 0)
+	  || (code == RSHIFT_EXPR && sgn1 >= 0)
 	  /* 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)
-	return TYPE_MAX_VALUE (TREE_TYPE (res));
+	return wi::max_value (TYPE_PRECISION (TREE_TYPE (val1)),
+			      TYPE_SIGN (TREE_TYPE (val1)));
       else
-	return TYPE_MIN_VALUE (TREE_TYPE (res));
+	return wi::min_value (TYPE_PRECISION (TREE_TYPE (val1)),
+			      TYPE_SIGN (TREE_TYPE (val1)));
     }
 
   return res;
@@ -1817,12 +1839,10 @@ extract_range_from_multiplicative_op_1 (
 					enum tree_code code,
 					value_range *vr0, value_range *vr1)
 {
-  enum value_range_type type;
-  tree val[4];
-  size_t i;
-  tree min, max;
+  enum value_range_type rtype;
+  wide_int val, min, max;
   bool sop;
-  int cmp;
+  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
@@ -1848,88 +1868,69 @@ extract_range_from_multiplicative_op_1 (
 	       || (code == MULT_EXPR && vr0->type == VR_ANTI_RANGE))
 	      && vr0->type == vr1->type);
 
-  type = vr0->type;
+  rtype = vr0->type;
+  type = TREE_TYPE (vr0->min);
+  signop sgn = TYPE_SIGN (type);
 
-  /* Compute the 4 cross operations.  */
+  /* Compute the 4 cross operations and their minimum and maximum value.  */
   sop = false;
-  val[0] = vrp_int_const_binop (code, vr0->min, vr1->min);
-  if (val[0] == NULL_TREE)
-    sop = true;
+  val = vrp_int_const_binop (code, vr0->min, vr1->min, &sop);
+  if (! sop)
+    min = max = val;
 
   if (vr1->max == vr1->min)
-    val[1] = NULL_TREE;
-  else
+    ;
+  else if (! sop)
     {
-      val[1] = vrp_int_const_binop (code, vr0->min, vr1->max);
-      if (val[1] == NULL_TREE)
-	sop = true;
+      val = vrp_int_const_binop (code, vr0->min, vr1->max, &sop);
+      if (! sop)
+	{
+	  if (wi::lt_p (val, min, sgn))
+	    min = val;
+	  else if (wi::gt_p (val, max, sgn))
+	    max = val;
+	}
     }
 
   if (vr0->max == vr0->min)
-    val[2] = NULL_TREE;
-  else
+    ;
+  else if (! sop)
     {
-      val[2] = vrp_int_const_binop (code, vr0->max, vr1->min);
-      if (val[2] == NULL_TREE)
-	sop = true;
+      val = vrp_int_const_binop (code, vr0->max, vr1->min, &sop);
+      if (! sop)
+	{
+	  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)
-    val[3] = NULL_TREE;
-  else
+    ;
+  else if (! sop)
     {
-      val[3] = vrp_int_const_binop (code, vr0->max, vr1->max);
-      if (val[3] == NULL_TREE)
-	sop = true;
+      val = vrp_int_const_binop (code, vr0->max, vr1->max, &sop);
+      if (! sop)
+	{
+	  if (wi::lt_p (val, min, sgn))
+	    min = val;
+	  else if (wi::gt_p (val, max, sgn))
+	    max = val;
+	}
     }
 
+  /* If either operation overflowed, drop to VARYING.  */
   if (sop)
     {
       set_value_range_to_varying (vr);
       return;
     }
 
-  /* Set MIN to the minimum of VAL[i] and MAX to the maximum
-     of VAL[i].  */
-  min = val[0];
-  max = val[0];
-  for (i = 1; i < 4; i++)
-    {
-      if (!is_gimple_min_invariant (min)
-	  || TREE_OVERFLOW (min)
-	  || !is_gimple_min_invariant (max)
-	  || TREE_OVERFLOW (max))
-	break;
-
-      if (val[i])
-	{
-	  if (!is_gimple_min_invariant (val[i])
-	      || TREE_OVERFLOW (val[i]))
-	    {
-	      /* If we found an overflowed value, set MIN and MAX
-		 to it so that we set the resulting range to
-		 VARYING.  */
-	      min = max = val[i];
-	      break;
-	    }
-
-	  if (compare_values (val[i], min) == -1)
-	    min = val[i];
-
-	  if (compare_values (val[i], max) == 1)
-	    max = val[i];
-	}
-    }
-
-  /* If either MIN or MAX overflowed, then set the resulting range to
-     VARYING.  But we do accept an overflow infinity
-     representation.  */
-  if (min == NULL_TREE
-      || !is_gimple_min_invariant (min)
-      || TREE_OVERFLOW (min)
-      || max == NULL_TREE
-      || !is_gimple_min_invariant (max)
-      || TREE_OVERFLOW (max))
+  /* 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))
     {
       set_value_range_to_varying (vr);
       return;
@@ -1938,23 +1939,16 @@ extract_range_from_multiplicative_op_1 (
   /* 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 (vrp_val_is_min (min)
-      && vrp_val_is_max (max))
+  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;
     }
 
-  cmp = compare_values (min, max);
-  if (cmp == -2 || cmp == 1)
-    {
-      /* 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.  */
-      set_value_range_to_varying (vr);
-    }
-  else
-    set_value_range (vr, type, min, max, NULL);
+  set_value_range (vr, rtype,
+		   wide_int_to_tree (type, min),
+		   wide_int_to_tree (type, max), NULL);
 }
 
 /* Extract range information from a binary operation CODE based on
@@ -2437,8 +2431,8 @@ extract_range_from_binary_expr_1 (value_
 	      /* For operations that make the resulting range directly
 		 proportional to the original ranges, apply the operation to
 		 the same end of each range.  */
-	      min = vrp_int_const_binop (code, vr0.min, vr1.min);
-	      max = vrp_int_const_binop (code, vr0.max, vr1.max);
+	      min = int_const_binop (code, vr0.min, vr1.min);
+	      max = int_const_binop (code, vr0.max, vr1.max);
 	    }
 	  else if (code == MIN_EXPR)
 	    {