Patchwork VRP PLUS/MINUS_EXPR

login
register
mail settings
Submitter Marc Glisse
Date July 25, 2012, 10:21 a.m.
Message ID <alpine.DEB.2.02.1207251151150.30469@stedding.saclay.inria.fr>
Download mbox | patch
Permalink /patch/173134/
State New
Headers show

Comments

Marc Glisse - July 25, 2012, 10:21 a.m.
Hello,

here is a slight improvement to VRP for sum and difference of intervals. 
There are some things I left because I didn't understand them enough:

* range_int_cst_p (&vr0): I thought it was always true by that time, but 
it isn't obvious

* TYPE_PRECISION (expr_type) <= HOST_BITS_PER_DOUBLE_INT: the __int256 
patch scared me (though I would love to have larger types, especially with 
a proper range analysis to use only 2 or 3 of the 4 64-bit integers that 
make up an __int256 when it is enough, see PR 53100 for the __int128 
version)

* when is the value range of a type smaller than the one given by its 
precision? Is it for enum?


2012-07-25  Marc Glisse  <marc.glisse@inria.fr>

 	PR tree-optimization/30318
 	* tree-vrp.c (extract_range_from_binary_expr_1) [PLUS_EXPR]:
 	Handle __int128.
 	[MINUS_EXPR] merge with PLUS_EXPR.

bootstrapped just c and c++ and ran the testsuite with no new regression.
Richard Guenther - July 25, 2012, 1:37 p.m.
On Wed, Jul 25, 2012 at 12:21 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
> Hello,
>
> here is a slight improvement to VRP for sum and difference of intervals.
> There are some things I left because I didn't understand them enough:
>
> * range_int_cst_p (&vr0): I thought it was always true by that time, but it
> isn't obvious

Possibly, though I wouldn't exclude [&a, &a] ranges for example.

> * TYPE_PRECISION (expr_type) <= HOST_BITS_PER_DOUBLE_INT: the __int256 patch
> scared me (though I would love to have larger types, especially with a
> proper range analysis to use only 2 or 3 of the 4 64-bit integers that make
> up an __int256 when it is enough, see PR 53100 for the __int128 version)

Yeah ...

> * when is the value range of a type smaller than the one given by its
> precision? Is it for enum?

That's the historical case.  I'd love to get rid of this though as the
middle-end treats a int-precision enum semantically the same as an int.

The patch is ok, if properly bootstrapped/tested.

Thanks for working on this!
Richard.

>
> 2012-07-25  Marc Glisse  <marc.glisse@inria.fr>
>
>         PR tree-optimization/30318
>         * tree-vrp.c (extract_range_from_binary_expr_1) [PLUS_EXPR]:
>         Handle __int128.
>         [MINUS_EXPR] merge with PLUS_EXPR.
>
> bootstrapped just c and c++ and ran the testsuite with no new regression.
>
> --
> Marc Glisse

Patch

Index: tree-vrp.c

===================================================================
--- tree-vrp.c	(revision 189779)

+++ tree-vrp.c	(working copy)

@@ -2345,157 +2345,194 @@  extract_range_from_binary_expr_1 (value_

 	    set_value_range_to_varying (vr);
 	}
       else
 	set_value_range_to_varying (vr);
 
       return;
     }
 
   /* For integer ranges, apply the operation to each end of the
      range and see what we end up with.  */
-  if (code == PLUS_EXPR)

+  if (code == PLUS_EXPR || code == MINUS_EXPR)

     {
       /* If we have a PLUS_EXPR with two VR_RANGE integer constant
          ranges compute the precise range for such case if possible.  */
       if (range_int_cst_p (&vr0)
 	  && range_int_cst_p (&vr1)
-	  /* We attempt to do infinite precision signed integer arithmetic,

-	     thus we need two more bits than the possibly unsigned inputs.  */

-	  && TYPE_PRECISION (expr_type) < HOST_BITS_PER_DOUBLE_INT - 1)

+	  /* We need as many bits as the possibly unsigned inputs.  */

+	  && TYPE_PRECISION (expr_type) <= HOST_BITS_PER_DOUBLE_INT)

 	{
 	  double_int min0 = tree_to_double_int (vr0.min);
 	  double_int max0 = tree_to_double_int (vr0.max);
 	  double_int min1 = tree_to_double_int (vr1.min);
 	  double_int max1 = tree_to_double_int (vr1.max);
 	  bool uns = TYPE_UNSIGNED (expr_type);
 	  double_int type_min
 	    = double_int_min_value (TYPE_PRECISION (expr_type), uns);
 	  double_int type_max
 	    = double_int_max_value (TYPE_PRECISION (expr_type), uns);
 	  double_int dmin, dmax;
+	  int min_ovf = 0;

+	  int max_ovf = 0;

 
-	  dmin = double_int_add (min0, min1);

-	  dmax = double_int_add (max0, max1);

+	  if (code == PLUS_EXPR)

+	    {

+	      dmin = double_int_add (min0, min1);

+	      dmax = double_int_add (max0, max1);

+

+	      /* Check for overflow in double_int.  */

+	      if (double_int_cmp (min1, double_int_zero, uns)

+		  != double_int_cmp (dmin, min0, uns))

+		min_ovf = double_int_cmp (min0, dmin, uns);

+	      if (double_int_cmp (max1, double_int_zero, uns)

+		  != double_int_cmp (dmax, max0, uns))

+		max_ovf = double_int_cmp (max0, dmax, uns);

+	    }

+	  else /* if (code == MINUS_EXPR) */

+	    {

+	      dmin = double_int_sub (min0, max1);

+	      dmax = double_int_sub (max0, min1);

+

+	      if (double_int_cmp (double_int_zero, max1, uns)

+		  != double_int_cmp (dmin, min0, uns))

+		min_ovf = double_int_cmp (min0, max1, uns);

+	      if (double_int_cmp (double_int_zero, min1, uns)

+		  != double_int_cmp (dmax, max0, uns))

+		max_ovf = double_int_cmp (max0, min1, uns);

+	    }

+

+	  /* For non-wrapping arithmetic look at possibly smaller

+	     value-ranges of the type.  */

+	  if (!TYPE_OVERFLOW_WRAPS (expr_type))

+	    {

+	      if (vrp_val_min (expr_type))

+		type_min = tree_to_double_int (vrp_val_min (expr_type));

+	      if (vrp_val_max (expr_type))

+		type_max = tree_to_double_int (vrp_val_max (expr_type));

+	    }

+

+	  /* Check for type overflow.  */

+	  if (min_ovf == 0)

+	    {

+	      if (double_int_cmp (dmin, type_min, uns) == -1)

+		min_ovf = -1;

+	      else if (double_int_cmp (dmin, type_max, uns) == 1)

+		min_ovf = 1;

+	    }

+	  if (max_ovf == 0)

+	    {

+	      if (double_int_cmp (dmax, type_min, uns) == -1)

+		max_ovf = -1;

+	      else if (double_int_cmp (dmax, type_max, uns) == 1)

+		max_ovf = 1;

+	    }

 
 	  if (TYPE_OVERFLOW_WRAPS (expr_type))
 	    {
 	      /* If overflow wraps, truncate the values and adjust the
 		 range kind and bounds appropriately.  */
 	      double_int tmin
 		= double_int_ext (dmin, TYPE_PRECISION (expr_type), uns);
 	      double_int tmax
 		= double_int_ext (dmax, TYPE_PRECISION (expr_type), uns);
-	      gcc_assert (double_int_scmp (dmin, dmax) <= 0);

-	      if ((double_int_scmp (dmin, type_min) == -1

-		   && double_int_scmp (dmax, type_min) == -1)

-		  || (double_int_scmp (dmin, type_max) == 1

-		      && double_int_scmp (dmax, type_max) == 1)

-		  || (double_int_scmp (type_min, dmin) <= 0

-		      && double_int_scmp (dmax, type_max) <= 0))

+	      if (min_ovf == max_ovf)

 		{
 		  /* No overflow or both overflow or underflow.  The
 		     range kind stays VR_RANGE.  */
 		  min = double_int_to_tree (expr_type, tmin);
 		  max = double_int_to_tree (expr_type, tmax);
 		}
-	      else if (double_int_scmp (dmin, type_min) == -1

-		       && double_int_scmp (dmax, type_max) == 1)

+	      else if (min_ovf == -1

+		       && max_ovf == 1)

 		{
 		  /* Underflow and overflow, drop to VR_VARYING.  */
 		  set_value_range_to_varying (vr);
 		  return;
 		}
 	      else
 		{
 		  /* Min underflow or max overflow.  The range kind
 		     changes to VR_ANTI_RANGE.  */
 		  double_int tem = tmin;
-		  gcc_assert ((double_int_scmp (dmin, type_min) == -1

-			       && double_int_scmp (dmax, type_min) >= 0

-			       && double_int_scmp (dmax, type_max) <= 0)

-			      || (double_int_scmp (dmax, type_max) == 1

-				  && double_int_scmp (dmin, type_min) >= 0

-				  && double_int_scmp (dmin, type_max) <= 0));

+		  gcc_assert ((min_ovf == -1 && max_ovf == 0)

+			      || (max_ovf == 1 && min_ovf == 0));

 		  type = VR_ANTI_RANGE;
 		  tmin = double_int_add (tmax, double_int_one);
 		  tmax = double_int_add (tem, double_int_minus_one);
 		  /* If the anti-range would cover nothing, drop to varying.
 		     Likewise if the anti-range bounds are outside of the
 		     types values.  */
 		  if (double_int_cmp (tmin, tmax, uns) > 0
 		      || double_int_cmp (tmin, type_min, uns) < 0
 		      || double_int_cmp (tmax, type_max, uns) > 0)
 		    {
 		      set_value_range_to_varying (vr);
 		      return;
 		    }
 		  min = double_int_to_tree (expr_type, tmin);
 		  max = double_int_to_tree (expr_type, tmax);
 		}
 	    }
 	  else
 	    {
-	      /* For non-wrapping arithmetic look at possibly smaller

-		 value-ranges of the type.  */

-	      if (vrp_val_min (expr_type))

-		type_min = tree_to_double_int (vrp_val_min (expr_type));

-	      if (vrp_val_max (expr_type))

-		type_max = tree_to_double_int (vrp_val_max (expr_type));

-

 	      /* If overflow does not wrap, saturate to the types min/max
 	         value.  */
-	      if (double_int_scmp (dmin, type_min) == -1)

+	      if (min_ovf == -1)

 		{
 		  if (needs_overflow_infinity (expr_type)
 		      && supports_overflow_infinity (expr_type))
 		    min = negative_overflow_infinity (expr_type);
 		  else
 		    min = double_int_to_tree (expr_type, type_min);
 		}
-	      else if (double_int_scmp (dmin, type_max) == 1)

+	      else if (min_ovf == 1)

 		{
 		  if (needs_overflow_infinity (expr_type)
 		      && supports_overflow_infinity (expr_type))
 		    min = positive_overflow_infinity (expr_type);
 		  else
 		    min = double_int_to_tree (expr_type, type_max);
 		}
 	      else
 		min = double_int_to_tree (expr_type, dmin);
 
-	      if (double_int_scmp (dmax, type_min) == -1)

+	      if (max_ovf == -1)

 		{
 		  if (needs_overflow_infinity (expr_type)
 		      && supports_overflow_infinity (expr_type))
 		    max = negative_overflow_infinity (expr_type);
 		  else
 		    max = double_int_to_tree (expr_type, type_min);
 		}
-	      else if (double_int_scmp (dmax, type_max) == 1)

+	      else if (max_ovf == 1)

 		{
 		  if (needs_overflow_infinity (expr_type)
 		      && supports_overflow_infinity (expr_type))
 		    max = positive_overflow_infinity (expr_type);
 		  else
 		    max = double_int_to_tree (expr_type, type_max);
 		}
 	      else
 		max = double_int_to_tree (expr_type, dmax);
 	    }
 	  if (needs_overflow_infinity (expr_type)
 	      && supports_overflow_infinity (expr_type))
 	    {
 	      if (is_negative_overflow_infinity (vr0.min)
-		  || is_negative_overflow_infinity (vr1.min))

+		  || (code == PLUS_EXPR

+		      ? is_negative_overflow_infinity (vr1.min)

+		      : is_positive_overflow_infinity (vr1.max)))

 		min = negative_overflow_infinity (expr_type);
 	      if (is_positive_overflow_infinity (vr0.max)
-		  || is_positive_overflow_infinity (vr1.max))

+		  || (code == PLUS_EXPR

+		      ? is_positive_overflow_infinity (vr1.max)

+		      : is_negative_overflow_infinity (vr1.min)))

 		max = positive_overflow_infinity (expr_type);
 	    }
 	}
       else
 	{
 	  /* For other cases, for example if we have a PLUS_EXPR with two
 	     VR_ANTI_RANGEs, drop to VR_VARYING.  It would take more effort
 	     to compute a precise range for such a case.
 	     ???  General even mixed range kind operations can be expressed
 	     by for example transforming ~[3, 5] + [1, 2] to range-only
@@ -2710,40 +2747,20 @@  extract_range_from_binary_expr_1 (value_

 	max = vr1.max;
       max = int_const_binop (MINUS_EXPR, max, integer_one_node);
       /* If the dividend is non-negative the modulus will be
 	 non-negative as well.  */
       if (TYPE_UNSIGNED (expr_type)
 	  || value_range_nonnegative_p (&vr0))
 	min = build_int_cst (TREE_TYPE (max), 0);
       else
 	min = fold_unary_to_constant (NEGATE_EXPR, expr_type, max);
     }
-  else if (code == MINUS_EXPR)

-    {

-      /* If we have a MINUS_EXPR with two VR_ANTI_RANGEs, drop to

-	 VR_VARYING.  It would take more effort to compute a precise

-	 range for such a case.  For example, if we have op0 == 1 and

-	 op1 == 1 with their ranges both being ~[0,0], we would have

-	 op0 - op1 == 0, so we cannot claim that the difference is in

-	 ~[0,0].  Note that we are guaranteed to have

-	 vr0.type == vr1.type at this point.  */

-      if (vr0.type == VR_ANTI_RANGE)

-	{

-	  set_value_range_to_varying (vr);

-	  return;

-	}

-

-      /* For MINUS_EXPR, apply the operation to the opposite ends of

-	 each range.  */

-      min = vrp_int_const_binop (code, vr0.min, vr1.max);

-      max = vrp_int_const_binop (code, vr0.max, vr1.min);

-    }

   else if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR || code == BIT_XOR_EXPR)
     {
       bool int_cst_range0, int_cst_range1;
       double_int may_be_nonzero0, may_be_nonzero1;
       double_int must_be_nonzero0, must_be_nonzero1;
 
       int_cst_range0 = zero_nonzero_bits_from_vr (&vr0, &may_be_nonzero0,
 						  &must_be_nonzero0);
       int_cst_range1 = zero_nonzero_bits_from_vr (&vr1, &may_be_nonzero1,
 						  &must_be_nonzero1);