[PATCH] Improve VR computation for [x, y] & z or [x, y] | z (PR tree-optimization/80558)

[PATCH] Improve VR computation for [x, y] & z or [x, y] | z (PR tree-optimization/80558)

[Jakub Jelinek]

Hi!

This patch improves value range computation of BIT_{AND,IOR}_EXPR
with one singleton range and one range_int_cst_p, where the singleton
range has n clear least significant bits, then m set bits and either
that is all it has (i.e. negation of a power of 2), or the bits above
those two sets of bits are the same for all values in the range (i.e.
min and max range have those bits identical).
During x86_64-linux and i686-linux bootstraps together this triggers
214000 times, though I have not actually gathered statistics on whether
the range computed without this patch would be wider in all cases.

Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

2017-05-04  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/80558
	* tree-vrp.c (extract_range_from_binary_expr_1): Optimize
	[x, y] op z into [x op, y op z] for op & or | if conditions
	are met.

	* gcc.dg/tree-ssa/vrp115.c: New test.

--- gcc/tree-vrp.c.jj	2017-04-29 18:13:50.000000000 +0200
+++ gcc/tree-vrp.c	2017-05-03 16:08:44.525256483 +0200
@@ -3162,8 +3162,59 @@ extract_range_from_binary_expr_1 (value_
 						  &may_be_nonzero1,
 						  &must_be_nonzero1);
 
+      if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR)
+	{
+	  value_range *vr0p = NULL, *vr1p = NULL;
+	  if (range_int_cst_singleton_p (&vr1))
+	    {
+	      vr0p = &vr0;
+	      vr1p = &vr1;
+	    }
+	  else if (range_int_cst_singleton_p (&vr0))
+	    {
+	      vr0p = &vr1;
+	      vr1p = &vr0;
+	    }
+	  /* For op & or | attempt to optimize:
+	     [x, y] op z into [x op z, y op z]
+	     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.  */
+	  if (vr0p && range_int_cst_p (vr0p))
+	    {
+	      wide_int w = vr1p->min;
+	      int m = 0, n = 0;
+	      if (code == BIT_IOR_EXPR)
+		w = ~w;
+	      if (wi::eq_p (w, 0))
+		n = TYPE_PRECISION (expr_type);
+	      else
+		{
+		  n = wi::ctz (w);
+		  w = ~(w | wi::mask (n, false, w.get_precision ()));
+		  if (wi::eq_p (w, 0))
+		    m = TYPE_PRECISION (expr_type) - n;
+		  else
+		    m = wi::ctz (w) - n;
+		}
+	      wide_int mask = wi::mask (m + n, true, w.get_precision ());
+	      if (wi::eq_p (mask & vr0p->min, mask & vr0p->max))
+		{
+		  min = int_const_binop (code, vr0p->min, vr1p->min);
+		  max = int_const_binop (code, vr0p->max, vr1p->min);
+		}
+	    }
+	}
+
       type = VR_RANGE;
-      if (code == BIT_AND_EXPR)
+      if (min && max)
+	/* Optimized above already.  */;
+      else if (code == BIT_AND_EXPR)
 	{
 	  min = wide_int_to_tree (expr_type,
 				  must_be_nonzero0 & must_be_nonzero1);
--- gcc/testsuite/gcc.dg/tree-ssa/vrp115.c.jj	2017-05-03 16:12:55.514087451 +0200
+++ gcc/testsuite/gcc.dg/tree-ssa/vrp115.c	2017-05-03 16:11:35.000000000 +0200
@@ -0,0 +1,50 @@
+/* PR tree-optimization/80558 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-evrp" } */
+/* { dg-final { scan-tree-dump-not "link_error" "evrp" } } */
+
+void link_error (void);
+
+void
+f1 (int x)
+{
+  if (x >= 5 && x <= 19)
+    {
+      x &= -2;
+      if (x < 4 || x > 18)
+	link_error ();
+    }
+}
+
+void
+f2 (int x)
+{
+  if (x >= 5 && x <= 19)
+    {
+      x |= 7;
+      if (x < 7 || x > 23)
+	link_error ();
+    }
+}
+
+void
+f3 (int x)
+{
+  if (x >= -18 && x <= 19)
+    {
+      x |= 7;
+      if (x < -17 || x > 23)
+	link_error ();
+    }
+}
+
+void
+f4 (int x)
+{
+  if (x >= 1603 && x <= 2015)
+    {
+      x &= 496;
+      if (x < 64 || x > 464)
+	link_error ();
+    }
+}

	Jakub

Re: [PATCH] Improve VR computation for [x, y] & z or [x, y] | z (PR tree-optimization/80558)

[Richard Biener]

On Thu, 4 May 2017, Jakub Jelinek wrote:

> Hi!
> 
> This patch improves value range computation of BIT_{AND,IOR}_EXPR
> with one singleton range and one range_int_cst_p, where the singleton
> range has n clear least significant bits, then m set bits and either
> that is all it has (i.e. negation of a power of 2), or the bits above
> those two sets of bits are the same for all values in the range (i.e.
> min and max range have those bits identical).
> During x86_64-linux and i686-linux bootstraps together this triggers
> 214000 times, though I have not actually gathered statistics on whether
> the range computed without this patch would be wider in all cases.

You could try to intersect the ranges produced and assert the
result is equal to the new one.

> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

Ok.

Thanks,
Richard.

> 2017-05-04  Jakub Jelinek  <jakub@redhat.com>
> 
> 	PR tree-optimization/80558
> 	* tree-vrp.c (extract_range_from_binary_expr_1): Optimize
> 	[x, y] op z into [x op, y op z] for op & or | if conditions
> 	are met.
> 
> 	* gcc.dg/tree-ssa/vrp115.c: New test.
> 
> --- gcc/tree-vrp.c.jj	2017-04-29 18:13:50.000000000 +0200
> +++ gcc/tree-vrp.c	2017-05-03 16:08:44.525256483 +0200
> @@ -3162,8 +3162,59 @@ extract_range_from_binary_expr_1 (value_
>  						  &may_be_nonzero1,
>  						  &must_be_nonzero1);
>  
> +      if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR)
> +	{
> +	  value_range *vr0p = NULL, *vr1p = NULL;
> +	  if (range_int_cst_singleton_p (&vr1))
> +	    {
> +	      vr0p = &vr0;
> +	      vr1p = &vr1;
> +	    }
> +	  else if (range_int_cst_singleton_p (&vr0))
> +	    {
> +	      vr0p = &vr1;
> +	      vr1p = &vr0;
> +	    }
> +	  /* For op & or | attempt to optimize:
> +	     [x, y] op z into [x op z, y op z]
> +	     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.  */
> +	  if (vr0p && range_int_cst_p (vr0p))
> +	    {
> +	      wide_int w = vr1p->min;
> +	      int m = 0, n = 0;
> +	      if (code == BIT_IOR_EXPR)
> +		w = ~w;
> +	      if (wi::eq_p (w, 0))
> +		n = TYPE_PRECISION (expr_type);
> +	      else
> +		{
> +		  n = wi::ctz (w);
> +		  w = ~(w | wi::mask (n, false, w.get_precision ()));
> +		  if (wi::eq_p (w, 0))
> +		    m = TYPE_PRECISION (expr_type) - n;
> +		  else
> +		    m = wi::ctz (w) - n;
> +		}
> +	      wide_int mask = wi::mask (m + n, true, w.get_precision ());
> +	      if (wi::eq_p (mask & vr0p->min, mask & vr0p->max))
> +		{
> +		  min = int_const_binop (code, vr0p->min, vr1p->min);
> +		  max = int_const_binop (code, vr0p->max, vr1p->min);
> +		}
> +	    }
> +	}
> +
>        type = VR_RANGE;
> -      if (code == BIT_AND_EXPR)
> +      if (min && max)
> +	/* Optimized above already.  */;
> +      else if (code == BIT_AND_EXPR)
>  	{
>  	  min = wide_int_to_tree (expr_type,
>  				  must_be_nonzero0 & must_be_nonzero1);
> --- gcc/testsuite/gcc.dg/tree-ssa/vrp115.c.jj	2017-05-03 16:12:55.514087451 +0200
> +++ gcc/testsuite/gcc.dg/tree-ssa/vrp115.c	2017-05-03 16:11:35.000000000 +0200
> @@ -0,0 +1,50 @@
> +/* PR tree-optimization/80558 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-evrp" } */
> +/* { dg-final { scan-tree-dump-not "link_error" "evrp" } } */
> +
> +void link_error (void);
> +
> +void
> +f1 (int x)
> +{
> +  if (x >= 5 && x <= 19)
> +    {
> +      x &= -2;
> +      if (x < 4 || x > 18)
> +	link_error ();
> +    }
> +}
> +
> +void
> +f2 (int x)
> +{
> +  if (x >= 5 && x <= 19)
> +    {
> +      x |= 7;
> +      if (x < 7 || x > 23)
> +	link_error ();
> +    }
> +}
> +
> +void
> +f3 (int x)
> +{
> +  if (x >= -18 && x <= 19)
> +    {
> +      x |= 7;
> +      if (x < -17 || x > 23)
> +	link_error ();
> +    }
> +}
> +
> +void
> +f4 (int x)
> +{
> +  if (x >= 1603 && x <= 2015)
> +    {
> +      x &= 496;
> +      if (x < 64 || x > 464)
> +	link_error ();
> +    }
> +}
> 
> 	Jakub
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)

Re: [PATCH] Improve VR computation for [x, y] & z or [x, y] | z (PR tree-optimization/80558)

[Jakub Jelinek]

On Fri, May 05, 2017 at 01:59:17PM +0200, Richard Biener wrote:
> On Thu, 4 May 2017, Jakub Jelinek wrote:
> 
> > Hi!
> > 
> > This patch improves value range computation of BIT_{AND,IOR}_EXPR
> > with one singleton range and one range_int_cst_p, where the singleton
> > range has n clear least significant bits, then m set bits and either
> > that is all it has (i.e. negation of a power of 2), or the bits above
> > those two sets of bits are the same for all values in the range (i.e.
> > min and max range have those bits identical).
> > During x86_64-linux and i686-linux bootstraps together this triggers
> > 214000 times, though I have not actually gathered statistics on whether
> > the range computed without this patch would be wider in all cases.
> 
> You could try to intersect the ranges produced and assert the
> result is equal to the new one.

I've done the following statistics incremental patch, and on x86_64-linux
and i686-linux bootstraps/regtests it gave (first column is number of
occurrences of those 2 numbers):
   6877 -4 -4 # Range where previously we'd end up VARYING
  15430 -1 1 # Bigger minimum and smaller maximum than before
  17767 -1 0 # Same maximum, with the patch bigger minimum than before
  20014 0 1 # Same minimum, with the patch smaller maximum than before
 153948 0 0 # These are cases where we return the same range as before
So there are no cases where we'd give wider range than before.

Committing the patch now (of course not the following one).

--- gcc/tree-vrp.c.jj	2017-05-05 15:08:36.000000000 +0200
+++ gcc/tree-vrp.c	2017-05-05 15:33:35.094546653 +0200
@@ -2857,6 +2857,7 @@ extract_range_from_binary_expr_1 (value_
       bool int_cst_range0, int_cst_range1;
       wide_int may_be_nonzero0, may_be_nonzero1;
       wide_int must_be_nonzero0, must_be_nonzero1;
+      tree minxx = NULL_TREE, maxxx = NULL_TREE;
 
       int_cst_range0 = zero_nonzero_bits_from_vr (expr_type, &vr0,
 						  &may_be_nonzero0,
@@ -2908,8 +2909,8 @@ extract_range_from_binary_expr_1 (value_
 	      wide_int mask = wi::mask (m + n, true, w.get_precision ());
 	      if (wi::eq_p (mask & vr0p->min, mask & vr0p->max))
 		{
-		  min = int_const_binop (code, vr0p->min, vr1p->min);
-		  max = int_const_binop (code, vr0p->max, vr1p->min);
+		  minxx = int_const_binop (code, vr0p->min, vr1p->min);
+		  maxxx = int_const_binop (code, vr0p->max, vr1p->min);
 		}
 	    }
 	}
@@ -3000,6 +3001,33 @@ extract_range_from_binary_expr_1 (value_
 	  else
 	    max = min = NULL_TREE;
 	}
+      if (minxx && maxxx)
+	{
+	  int z1, z2;
+	  if (min && !TREE_OVERFLOW (min))
+	    z1 = compare_values (min, minxx);
+	  else
+	    z1 = -3;
+	  if (max && !TREE_OVERFLOW (max))
+	    z2 = compare_values (max, maxxx);
+	  else
+	    z2 = -3;
+          if (min && max)
+	    {
+	      int z3 = compare_values (min, max);
+	      if (z3 == -2 || z3 == 1)
+		{
+		  z1 = -4;
+		  z2 = -4;
+	        }
+	    }
+
+	  FILE *f = fopen ("/tmp/vrpz", "a");
+	  fprintf (f, "%d %d %d %s %s\n", z1, z2, (int) BITS_PER_WORD, main_input_filename ? main_input_filename : "-", current_function_name ());
+	  fclose (f);
+	  min = minxx;
+	  max = maxxx;
+	}
     }
   else
     gcc_unreachable ();


	Jakub