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

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.


	Jakub

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
> 
>