[PATCH] Extend VRP BIT_IOR_EXPR to handle sign-bit

[PATCH] Extend VRP BIT_IOR_EXPR to handle sign-bit

[Richard Guenther]

This removes one weakness in BIT_IOR_EXPR handling which gives
up even if we can compute a fully negative range.  The following
thus extends zero_nonzero_bits_from_vr to extract sign-bit
information (I believe that's the only bit we know sth about
when both vr.min and vr.max are negative).  It also adjusts
BIT_IOR_EXPR handling to not give up for the min < max < 0 case.

Boostrapped on x86_64-unknown-linux-gnu, testing in progress.

I guess BIT_AND_EXPR handling will show a similar weakness but
a similar testcase (as added below) already passes.  So I suppose
we have to obfuscate it a bit more ;)

Richard.

2011-08-05  Richard Guenther  <rguenther@suse.de>

	* tree-vrp.c (zero_nonzero_bits_from_vr): Pass in a type.
	For ranges with negative values return information about the
	sign-bit.
	(extract_range_from_binary_expr_1): Adjust BIT_IOR_EXPR handling
	to handle sign-bit information for ranges with negative values.
	(simplify_bit_ops_using_ranges): Adjust.

	* gcc.dg/tree-ssa/vrp60.c: New testcase.

Index: gcc/tree-vrp.c
===================================================================
*** gcc/tree-vrp.c	(revision 177425)
--- gcc/tree-vrp.c	(working copy)
*************** vrp_int_const_binop (enum tree_code code
*** 2138,2144 ****
     the bit is 1, otherwise it might be 0 or 1.  */
  
  static bool
! zero_nonzero_bits_from_vr (value_range_t *vr, double_int *may_be_nonzero,
  			   double_int *must_be_nonzero)
  {
    may_be_nonzero->low = ALL_ONES;
--- 2138,2145 ----
     the bit is 1, otherwise it might be 0 or 1.  */
  
  static bool
! zero_nonzero_bits_from_vr (value_range_t *vr, tree type,
! 			   double_int *may_be_nonzero,
  			   double_int *must_be_nonzero)
  {
    may_be_nonzero->low = ALL_ONES;
*************** zero_nonzero_bits_from_vr (value_range_t
*** 2178,2183 ****
--- 2179,2192 ----
  	      must_be_nonzero->low &= ~mask;
  	    }
  	}
+       else if (tree_int_cst_sgn (vr->max) < 0)
+ 	{
+ 	  /* The only thing we know when the range covers only negative
+ 	     values is that the sign bit must be set.  */
+ 	  *may_be_nonzero = double_int_minus_one;
+ 	  *must_be_nonzero
+ 	    = double_int_setbit (double_int_zero, TYPE_PRECISION (type) - 1);
+ 	}
        return true;
      }
    return false;
*************** extract_range_from_binary_expr_1 (value_
*** 2642,2650 ****
        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);
  
        type = VR_RANGE;
--- 2651,2661 ----
        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, expr_type,
! 						  &may_be_nonzero0,
  						  &must_be_nonzero0);
!       int_cst_range1 = zero_nonzero_bits_from_vr (&vr1, expr_type,
! 						  &may_be_nonzero1,
  						  &must_be_nonzero1);
  
        type = VR_RANGE;
*************** extract_range_from_binary_expr_1 (value_
*** 2683,2699 ****
  	  max = double_int_to_tree (expr_type,
  				    double_int_ior (may_be_nonzero0,
  						    may_be_nonzero1));
- 	  if (tree_int_cst_sgn (max) < 0)
- 	    max = NULL_TREE;
  	  if (int_cst_range0)
! 	    {
! 	      if (tree_int_cst_sgn (min) < 0)
! 		min = vr0.min;
! 	      else
! 		min = vrp_int_const_binop (MAX_EXPR, min, vr0.min);
! 	    }
  	  if (int_cst_range1)
  	    min = vrp_int_const_binop (MAX_EXPR, min, vr1.min);
  	}
        else if (code == BIT_XOR_EXPR)
  	{
--- 2694,2709 ----
  	  max = double_int_to_tree (expr_type,
  				    double_int_ior (may_be_nonzero0,
  						    may_be_nonzero1));
  	  if (int_cst_range0)
! 	    min = vrp_int_const_binop (MAX_EXPR, min, vr0.min);
  	  if (int_cst_range1)
  	    min = vrp_int_const_binop (MAX_EXPR, min, vr1.min);
+ 	  if (tree_int_cst_sgn (min) < 0)
+ 	    ;
+ 	  else if (tree_int_cst_sgn (max) >= 0)
+ 	    ;
+ 	  else
+ 	    min = max = NULL_TREE;
  	}
        else if (code == BIT_XOR_EXPR)
  	{
*************** simplify_bit_ops_using_ranges (gimple_st
*** 6984,6992 ****
    else
      return false;
  
!   if (!zero_nonzero_bits_from_vr (&vr0, &may_be_nonzero0, &must_be_nonzero0))
      return false;
!   if (!zero_nonzero_bits_from_vr (&vr1, &may_be_nonzero1, &must_be_nonzero1))
      return false;
  
    switch (gimple_assign_rhs_code (stmt))
--- 6994,7004 ----
    else
      return false;
  
!   if (!zero_nonzero_bits_from_vr (&vr0, TREE_TYPE (op0),
! 				  &may_be_nonzero0, &must_be_nonzero0))
      return false;
!   if (!zero_nonzero_bits_from_vr (&vr1, TREE_TYPE (op1),
! 				  &may_be_nonzero1, &must_be_nonzero1))
      return false;
  
    switch (gimple_assign_rhs_code (stmt))
Index: gcc/testsuite/gcc.dg/tree-ssa/vrp60.c
===================================================================
*** gcc/testsuite/gcc.dg/tree-ssa/vrp60.c	(revision 0)
--- gcc/testsuite/gcc.dg/tree-ssa/vrp60.c	(revision 0)
***************
*** 0 ****
--- 1,31 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fno-tree-ccp -fno-tree-dominator-opts -fdump-tree-vrp1" } */
+ 
+ int foo (int x, int b)
+ {
+   int cst;
+   if (b)
+     cst = -__INT_MAX__ - 1;
+   else
+     cst = -__INT_MAX__;
+   x = x | cst;
+   if (x >= 0)
+     return 12345;
+   return x;
+ }
+ 
+ int bar (int x, int b)
+ {
+   int cst;
+   if (b)
+     cst = __INT_MAX__;
+   else
+     cst = __INT_MAX__ - 1;
+   x = x & cst;
+   if (x < 0)
+     return 12345;
+   return x;
+ }
+ 
+ /* { dg-final { scan-tree-dump-not "12345" "vrp1" } } */
+ /* { dg-final { cleanup-tree-dump "vrp1" } } */

Re: [PATCH] Extend VRP BIT_IOR_EXPR to handle sign-bit

[Paolo Bonzini]

On 08/05/2011 01:04 PM, Richard Guenther wrote:
> (I believe that's the only bit we know sth about
> when both vr.min and vr.max are negative).

Depends, if the value is between -2^16 and -1, we know something about 
all the bits to the left of bit 15.  I think a better mask is:

* MUST_BE_NONZERO = vr->min with all bits zero after the leftmost zero 
bit.  Or, the leftmost clz(~vr->min) bits are one.
* MAY_BE_NONZERO = all ones.

But something similar to xor_mask can likely be done with negative 
numbers too.  For example, if the value is between -32769 and -32768, 
you know that bits 1 to 14 are zero, and bits starting at 15 are one.

Paolo

Re: [PATCH] Extend VRP BIT_IOR_EXPR to handle sign-bit

[Richard Guenther]

On Fri, 5 Aug 2011, Paolo Bonzini wrote:

> On 08/05/2011 01:04 PM, Richard Guenther wrote:
> > (I believe that's the only bit we know sth about
> > when both vr.min and vr.max are negative).
> 
> Depends, if the value is between -2^16 and -1, we know something about all the
> bits to the left of bit 15.  I think a better mask is:
> 
> * MUST_BE_NONZERO = vr->min with all bits zero after the leftmost zero bit.
> Or, the leftmost clz(~vr->min) bits are one.
> * MAY_BE_NONZERO = all ones.
> 
> But something similar to xor_mask can likely be done with negative numbers
> too.  For example, if the value is between -32769 and -32768, you know that
> bits 1 to 14 are zero, and bits starting at 15 are one.

I have convinced myself that the current code handling ranges with
all positive values also works for ranges with all negative values.
Thus the patch even simplifies.  I've also adjusted the BIT_AND_EXPR
handling similar to the BIT_IOR_EXPR handling - now they at least
look symmetrical.

Boostrap and regtest running on x86_64-unknown-linux-gnu.

Comments & double-checks welcome,
Richard.

2011-08-08  Richard Guenther  <rguenther@suse.de>

	* tree-vrp.c (zero_nonzero_bits_from_vr): Also return precise
	information for with only negative values.
	(extract_range_from_binary_expr_1): Adjust BIT_IOR_EXPR and
	BIT_AND_EXPR handling to handle ranges with negative values.

	* gcc.dg/tree-ssa/vrp60.c: New testcase.
	* gcc.dg/tree-ssa/vrp61.c: Likewise.

Index: gcc/tree-vrp.c
===================================================================
*** gcc/tree-vrp.c.orig	2011-08-08 13:41:57.000000000 +0200
--- gcc/tree-vrp.c	2011-08-08 14:17:16.000000000 +0200
*************** vrp_int_const_binop (enum tree_code code
*** 2138,2186 ****
     the bit is 1, otherwise it might be 0 or 1.  */
  
  static bool
! zero_nonzero_bits_from_vr (value_range_t *vr, double_int *may_be_nonzero,
  			   double_int *must_be_nonzero)
  {
!   may_be_nonzero->low = ALL_ONES;
!   may_be_nonzero->high = ALL_ONES;
!   must_be_nonzero->low = 0;
!   must_be_nonzero->high = 0;
!   if (range_int_cst_p (vr))
!     {
!       if (range_int_cst_singleton_p (vr))
! 	{
! 	  *may_be_nonzero = tree_to_double_int (vr->min);
! 	  *must_be_nonzero = *may_be_nonzero;
! 	}
!       else if (tree_int_cst_sgn (vr->min) >= 0)
! 	{
! 	  double_int dmin = tree_to_double_int (vr->min);
! 	  double_int dmax = tree_to_double_int (vr->max);
! 	  double_int xor_mask = double_int_xor (dmin, dmax);
! 	  *may_be_nonzero = double_int_ior (dmin, dmax);
! 	  *must_be_nonzero = double_int_and (dmin, dmax);
! 	  if (xor_mask.high != 0)
! 	    {
! 	      unsigned HOST_WIDE_INT mask
! 		= ((unsigned HOST_WIDE_INT) 1
! 		   << floor_log2 (xor_mask.high)) - 1;
! 	      may_be_nonzero->low = ALL_ONES;
! 	      may_be_nonzero->high |= mask;
! 	      must_be_nonzero->low = 0;
! 	      must_be_nonzero->high &= ~mask;
! 	    }
! 	  else if (xor_mask.low != 0)
! 	    {
! 	      unsigned HOST_WIDE_INT mask
! 		= ((unsigned HOST_WIDE_INT) 1
! 		   << floor_log2 (xor_mask.low)) - 1;
! 	      may_be_nonzero->low |= mask;
! 	      must_be_nonzero->low &= ~mask;
! 	    }
  	}
-       return true;
      }
!   return false;
  }
  
  
--- 2138,2186 ----
     the bit is 1, otherwise it might be 0 or 1.  */
  
  static bool
! zero_nonzero_bits_from_vr (value_range_t *vr,
! 			   double_int *may_be_nonzero,
  			   double_int *must_be_nonzero)
  {
!   *may_be_nonzero = double_int_minus_one;
!   *must_be_nonzero = double_int_zero;
!   if (!range_int_cst_p (vr))
!     return false;
! 
!   if (range_int_cst_singleton_p (vr))
!     {
!       *may_be_nonzero = tree_to_double_int (vr->min);
!       *must_be_nonzero = *may_be_nonzero;
!     }
!   else if (tree_int_cst_sgn (vr->min) >= 0
! 	   || tree_int_cst_sgn (vr->max) < 0)
!     {
!       double_int dmin = tree_to_double_int (vr->min);
!       double_int dmax = tree_to_double_int (vr->max);
!       double_int xor_mask = double_int_xor (dmin, dmax);
!       *may_be_nonzero = double_int_ior (dmin, dmax);
!       *must_be_nonzero = double_int_and (dmin, dmax);
!       if (xor_mask.high != 0)
! 	{
! 	  unsigned HOST_WIDE_INT mask
! 	      = ((unsigned HOST_WIDE_INT) 1
! 		 << floor_log2 (xor_mask.high)) - 1;
! 	  may_be_nonzero->low = ALL_ONES;
! 	  may_be_nonzero->high |= mask;
! 	  must_be_nonzero->low = 0;
! 	  must_be_nonzero->high &= ~mask;
! 	}
!       else if (xor_mask.low != 0)
! 	{
! 	  unsigned HOST_WIDE_INT mask
! 	      = ((unsigned HOST_WIDE_INT) 1
! 		 << floor_log2 (xor_mask.low)) - 1;
! 	  may_be_nonzero->low |= mask;
! 	  must_be_nonzero->low &= ~mask;
  	}
      }
! 
!   return true;
  }
  
  
*************** extract_range_from_binary_expr_1 (value_
*** 2656,2679 ****
  	  max = double_int_to_tree (expr_type,
  				    double_int_and (may_be_nonzero0,
  						    may_be_nonzero1));
  	  if (tree_int_cst_sgn (min) < 0)
! 	    min = NULL_TREE;
! 	  if (tree_int_cst_sgn (max) < 0)
! 	    max = NULL_TREE;
! 	  if (int_cst_range0 && tree_int_cst_sgn (vr0.min) >= 0)
! 	    {
! 	      if (min == NULL_TREE)
! 		min = build_int_cst (expr_type, 0);
! 	      if (max == NULL_TREE || tree_int_cst_lt (vr0.max, max))
! 		max = vr0.max;
! 	    }
! 	  if (int_cst_range1 && tree_int_cst_sgn (vr1.min) >= 0)
! 	    {
! 	      if (min == NULL_TREE)
! 		min = build_int_cst (expr_type, 0);
! 	      if (max == NULL_TREE || tree_int_cst_lt (vr1.max, max))
! 		max = vr1.max;
! 	    }
  	}
        else if (code == BIT_IOR_EXPR)
  	{
--- 2656,2672 ----
  	  max = double_int_to_tree (expr_type,
  				    double_int_and (may_be_nonzero0,
  						    may_be_nonzero1));
+ 	  if (int_cst_range0)
+ 	    max = vrp_int_const_binop (MIN_EXPR, max, vr0.max);
+ 	  if (int_cst_range1)
+ 	    max = vrp_int_const_binop (MIN_EXPR, max, vr1.max);
  	  if (tree_int_cst_sgn (min) < 0)
! 	    /* The range is bound by an upper value of -1.  */;
! 	  else if (tree_int_cst_sgn (max) >= 0)
! 	    /* The range is bound by a lower value of 0.  */;
! 	  else
! 	    /* We don't know whether the sign bit is set or not.  */
! 	    min = max = NULL_TREE;
  	}
        else if (code == BIT_IOR_EXPR)
  	{
*************** extract_range_from_binary_expr_1 (value_
*** 2683,2699 ****
  	  max = double_int_to_tree (expr_type,
  				    double_int_ior (may_be_nonzero0,
  						    may_be_nonzero1));
- 	  if (tree_int_cst_sgn (max) < 0)
- 	    max = NULL_TREE;
  	  if (int_cst_range0)
! 	    {
! 	      if (tree_int_cst_sgn (min) < 0)
! 		min = vr0.min;
! 	      else
! 		min = vrp_int_const_binop (MAX_EXPR, min, vr0.min);
! 	    }
  	  if (int_cst_range1)
  	    min = vrp_int_const_binop (MAX_EXPR, min, vr1.min);
  	}
        else if (code == BIT_XOR_EXPR)
  	{
--- 2676,2692 ----
  	  max = double_int_to_tree (expr_type,
  				    double_int_ior (may_be_nonzero0,
  						    may_be_nonzero1));
  	  if (int_cst_range0)
! 	    min = vrp_int_const_binop (MAX_EXPR, min, vr0.min);
  	  if (int_cst_range1)
  	    min = vrp_int_const_binop (MAX_EXPR, min, vr1.min);
+ 	  if (tree_int_cst_sgn (min) < 0)
+ 	    /* The range is bound by an upper value of -1.  */;
+ 	  else if (tree_int_cst_sgn (max) >= 0)
+ 	    /* The range is bound by a lower value of 0.  */;
+ 	  else
+ 	    /* We don't know whether the sign bit is set or not.  */
+ 	    min = max = NULL_TREE;
  	}
        else if (code == BIT_XOR_EXPR)
  	{
Index: gcc/testsuite/gcc.dg/tree-ssa/vrp60.c
===================================================================
*** /dev/null	1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/tree-ssa/vrp60.c	2011-08-08 13:43:09.000000000 +0200
***************
*** 0 ****
--- 1,31 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fno-tree-ccp -fno-tree-dominator-opts -fdump-tree-vrp1" } */
+ 
+ int foo (int x, int b)
+ {
+   int cst;
+   if (b)
+     cst = -__INT_MAX__ - 1;
+   else
+     cst = -__INT_MAX__;
+   x = x | cst;
+   if (x >= 0)
+     return 12345;
+   return x;
+ }
+ 
+ int bar (int x, int b)
+ {
+   int cst;
+   if (b)
+     cst = __INT_MAX__;
+   else
+     cst = __INT_MAX__ - 1;
+   x = x & cst;
+   if (x < 0)
+     return 12345;
+   return x;
+ }
+ 
+ /* { dg-final { scan-tree-dump-not "12345" "vrp1" } } */
+ /* { dg-final { cleanup-tree-dump "vrp1" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/vrp61.c
===================================================================
*** /dev/null	1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/tree-ssa/vrp61.c	2011-08-08 13:58:44.000000000 +0200
***************
*** 0 ****
--- 1,16 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fdump-tree-vrp1" } */
+ 
+ int f (int x, int y)
+ {
+   if (x > -1024 && x < 0 && y > -1024 && y < 0)
+     {
+       x = x ^ y;
+       if (x < 0 || x > 1023)
+ 	return 1234;
+     }
+   return x;
+ }
+ 
+ /* { dg-final { scan-tree-dump-not "1234" "vrp1" } } */
+ /* { dg-final { cleanup-tree-dump "vrp1" } } */

Re: [PATCH] Extend VRP BIT_IOR_EXPR to handle sign-bit

[Richard Guenther]

On Mon, 8 Aug 2011, Richard Guenther wrote:

> On Fri, 5 Aug 2011, Paolo Bonzini wrote:
> 
> > On 08/05/2011 01:04 PM, Richard Guenther wrote:
> > > (I believe that's the only bit we know sth about
> > > when both vr.min and vr.max are negative).
> > 
> > Depends, if the value is between -2^16 and -1, we know something about all the
> > bits to the left of bit 15.  I think a better mask is:
> > 
> > * MUST_BE_NONZERO = vr->min with all bits zero after the leftmost zero bit.
> > Or, the leftmost clz(~vr->min) bits are one.
> > * MAY_BE_NONZERO = all ones.
> > 
> > But something similar to xor_mask can likely be done with negative numbers
> > too.  For example, if the value is between -32769 and -32768, you know that
> > bits 1 to 14 are zero, and bits starting at 15 are one.
> 
> I have convinced myself that the current code handling ranges with
> all positive values also works for ranges with all negative values.
> Thus the patch even simplifies.  I've also adjusted the BIT_AND_EXPR
> handling similar to the BIT_IOR_EXPR handling - now they at least
> look symmetrical.

Actually we should adjust the ranges only if it's either all positive
or negative values from the start and the adjustment keeps us on
the same side of zero.

Bootstrap & regtest running.

Richard.

2011-08-08  Richard Guenther  <rguenther@suse.de>

	* tree-vrp.c (zero_nonzero_bits_from_vr): Also return precise
	information for with only negative values.
	(extract_range_from_binary_expr_1): Adjust BIT_IOR_EXPR and
	BIT_AND_EXPR handling to handle ranges with negative values.

	* gcc.dg/tree-ssa/vrp57.c: Disable CCP.
	* gcc.dg/tree-ssa/vrp60.c: New testcase.
	* gcc.dg/tree-ssa/vrp61.c: Likewise.

Index: gcc/tree-vrp.c
===================================================================
*** gcc/tree-vrp.c.orig	2011-08-08 13:41:57.000000000 +0200
--- gcc/tree-vrp.c	2011-08-08 14:47:22.000000000 +0200
*************** vrp_int_const_binop (enum tree_code code
*** 2138,2186 ****
     the bit is 1, otherwise it might be 0 or 1.  */
  
  static bool
! zero_nonzero_bits_from_vr (value_range_t *vr, double_int *may_be_nonzero,
  			   double_int *must_be_nonzero)
  {
!   may_be_nonzero->low = ALL_ONES;
!   may_be_nonzero->high = ALL_ONES;
!   must_be_nonzero->low = 0;
!   must_be_nonzero->high = 0;
!   if (range_int_cst_p (vr))
!     {
!       if (range_int_cst_singleton_p (vr))
! 	{
! 	  *may_be_nonzero = tree_to_double_int (vr->min);
! 	  *must_be_nonzero = *may_be_nonzero;
! 	}
!       else if (tree_int_cst_sgn (vr->min) >= 0)
! 	{
! 	  double_int dmin = tree_to_double_int (vr->min);
! 	  double_int dmax = tree_to_double_int (vr->max);
! 	  double_int xor_mask = double_int_xor (dmin, dmax);
! 	  *may_be_nonzero = double_int_ior (dmin, dmax);
! 	  *must_be_nonzero = double_int_and (dmin, dmax);
! 	  if (xor_mask.high != 0)
! 	    {
! 	      unsigned HOST_WIDE_INT mask
! 		= ((unsigned HOST_WIDE_INT) 1
! 		   << floor_log2 (xor_mask.high)) - 1;
! 	      may_be_nonzero->low = ALL_ONES;
! 	      may_be_nonzero->high |= mask;
! 	      must_be_nonzero->low = 0;
! 	      must_be_nonzero->high &= ~mask;
! 	    }
! 	  else if (xor_mask.low != 0)
! 	    {
! 	      unsigned HOST_WIDE_INT mask
! 		= ((unsigned HOST_WIDE_INT) 1
! 		   << floor_log2 (xor_mask.low)) - 1;
! 	      may_be_nonzero->low |= mask;
! 	      must_be_nonzero->low &= ~mask;
! 	    }
  	}
-       return true;
      }
!   return false;
  }
  
  
--- 2138,2186 ----
     the bit is 1, otherwise it might be 0 or 1.  */
  
  static bool
! zero_nonzero_bits_from_vr (value_range_t *vr,
! 			   double_int *may_be_nonzero,
  			   double_int *must_be_nonzero)
  {
!   *may_be_nonzero = double_int_minus_one;
!   *must_be_nonzero = double_int_zero;
!   if (!range_int_cst_p (vr))
!     return false;
! 
!   if (range_int_cst_singleton_p (vr))
!     {
!       *may_be_nonzero = tree_to_double_int (vr->min);
!       *must_be_nonzero = *may_be_nonzero;
!     }
!   else if (tree_int_cst_sgn (vr->min) >= 0
! 	   || tree_int_cst_sgn (vr->max) < 0)
!     {
!       double_int dmin = tree_to_double_int (vr->min);
!       double_int dmax = tree_to_double_int (vr->max);
!       double_int xor_mask = double_int_xor (dmin, dmax);
!       *may_be_nonzero = double_int_ior (dmin, dmax);
!       *must_be_nonzero = double_int_and (dmin, dmax);
!       if (xor_mask.high != 0)
! 	{
! 	  unsigned HOST_WIDE_INT mask
! 	      = ((unsigned HOST_WIDE_INT) 1
! 		 << floor_log2 (xor_mask.high)) - 1;
! 	  may_be_nonzero->low = ALL_ONES;
! 	  may_be_nonzero->high |= mask;
! 	  must_be_nonzero->low = 0;
! 	  must_be_nonzero->high &= ~mask;
! 	}
!       else if (xor_mask.low != 0)
! 	{
! 	  unsigned HOST_WIDE_INT mask
! 	      = ((unsigned HOST_WIDE_INT) 1
! 		 << floor_log2 (xor_mask.low)) - 1;
! 	  may_be_nonzero->low |= mask;
! 	  must_be_nonzero->low &= ~mask;
  	}
      }
! 
!   return true;
  }
  
  
*************** extract_range_from_binary_expr_1 (value_
*** 2656,2679 ****
  	  max = double_int_to_tree (expr_type,
  				    double_int_and (may_be_nonzero0,
  						    may_be_nonzero1));
! 	  if (tree_int_cst_sgn (min) < 0)
! 	    min = NULL_TREE;
! 	  if (tree_int_cst_sgn (max) < 0)
! 	    max = NULL_TREE;
! 	  if (int_cst_range0 && tree_int_cst_sgn (vr0.min) >= 0)
! 	    {
! 	      if (min == NULL_TREE)
! 		min = build_int_cst (expr_type, 0);
! 	      if (max == NULL_TREE || tree_int_cst_lt (vr0.max, max))
! 		max = vr0.max;
! 	    }
! 	  if (int_cst_range1 && tree_int_cst_sgn (vr1.min) >= 0)
! 	    {
! 	      if (min == NULL_TREE)
! 		min = build_int_cst (expr_type, 0);
! 	      if (max == NULL_TREE || tree_int_cst_lt (vr1.max, max))
! 		max = vr1.max;
  	    }
  	}
        else if (code == BIT_IOR_EXPR)
  	{
--- 2656,2676 ----
  	  max = double_int_to_tree (expr_type,
  				    double_int_and (may_be_nonzero0,
  						    may_be_nonzero1));
! 	  /* If the range has all positive or all negative values the
! 	     result is better than VARYING and we can perform a
! 	     final adjustment.  */
! 	  if (tree_int_cst_sgn (min) < 0
! 	      || tree_int_cst_sgn (max) >= 0)
! 	    {
! 	      if (int_cst_range0
! 		  && tree_int_cst_sgn (max) == tree_int_cst_sgn (vr0.max))
! 		max = vrp_int_const_binop (MIN_EXPR, max, vr0.max);
! 	      if (int_cst_range1
! 		  && tree_int_cst_sgn (max) == tree_int_cst_sgn (vr1.max))
! 		max = vrp_int_const_binop (MIN_EXPR, max, vr1.max);
  	    }
+ 	  else
+ 	    min = max = NULL_TREE;
  	}
        else if (code == BIT_IOR_EXPR)
  	{
*************** extract_range_from_binary_expr_1 (value_
*** 2683,2699 ****
  	  max = double_int_to_tree (expr_type,
  				    double_int_ior (may_be_nonzero0,
  						    may_be_nonzero1));
! 	  if (tree_int_cst_sgn (max) < 0)
! 	    max = NULL_TREE;
! 	  if (int_cst_range0)
  	    {
! 	      if (tree_int_cst_sgn (min) < 0)
! 		min = vr0.min;
! 	      else
  		min = vrp_int_const_binop (MAX_EXPR, min, vr0.min);
  	    }
! 	  if (int_cst_range1)
! 	    min = vrp_int_const_binop (MAX_EXPR, min, vr1.min);
  	}
        else if (code == BIT_XOR_EXPR)
  	{
--- 2680,2701 ----
  	  max = double_int_to_tree (expr_type,
  				    double_int_ior (may_be_nonzero0,
  						    may_be_nonzero1));
! 	  /* If the range has all positive or all negative values the
! 	     result is better than VARYING and we can perform a
! 	     final adjustment.  */
! 	  if (tree_int_cst_sgn (min) < 0
! 	      || tree_int_cst_sgn (max) >= 0)
  	    {
! 	      if (int_cst_range0
! 		  && tree_int_cst_sgn (min) == tree_int_cst_sgn (vr0.min))
  		min = vrp_int_const_binop (MAX_EXPR, min, vr0.min);
+ 	      if (int_cst_range1
+ 		  && tree_int_cst_sgn (min) == tree_int_cst_sgn (vr1.min))
+ 		min = vrp_int_const_binop (MAX_EXPR, min, vr1.min);
  	    }
! 	  else
! 	    /* We don't know whether the sign bit is set or not.  */
! 	    min = max = NULL_TREE;
  	}
        else if (code == BIT_XOR_EXPR)
  	{
*************** extract_range_from_binary_expr_1 (value_
*** 2714,2727 ****
  	  max = double_int_to_tree (expr_type,
  				    double_int_not (result_zero_bits));
  	  min = double_int_to_tree (expr_type, result_one_bits);
! 	  /* Return a [min, max] range if we know the
! 	     result range is either positive or negative.  */
! 	  if (tree_int_cst_sgn (max) >= 0)
! 	    /* The range is bound by a lower value of 0.  */;
! 	  else if (tree_int_cst_sgn (min) < 0)
! 	    /* The range is bound by an upper value of -1.  */;
  	  else
- 	    /* We don't know whether the sign bit is set or not.  */
  	    max = min = NULL_TREE;
  	}
        else
--- 2716,2727 ----
  	  max = double_int_to_tree (expr_type,
  				    double_int_not (result_zero_bits));
  	  min = double_int_to_tree (expr_type, result_one_bits);
! 	  /* If the range has all positive or all negative values the
! 	     result is better than VARYING.  */
! 	  if (tree_int_cst_sgn (min) < 0
! 	      || tree_int_cst_sgn (max) >= 0)
! 	    ;
  	  else
  	    max = min = NULL_TREE;
  	}
        else
Index: gcc/testsuite/gcc.dg/tree-ssa/vrp60.c
===================================================================
*** /dev/null	1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/tree-ssa/vrp60.c	2011-08-08 13:43:09.000000000 +0200
***************
*** 0 ****
--- 1,31 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fno-tree-ccp -fno-tree-dominator-opts -fdump-tree-vrp1" } */
+ 
+ int foo (int x, int b)
+ {
+   int cst;
+   if (b)
+     cst = -__INT_MAX__ - 1;
+   else
+     cst = -__INT_MAX__;
+   x = x | cst;
+   if (x >= 0)
+     return 12345;
+   return x;
+ }
+ 
+ int bar (int x, int b)
+ {
+   int cst;
+   if (b)
+     cst = __INT_MAX__;
+   else
+     cst = __INT_MAX__ - 1;
+   x = x & cst;
+   if (x < 0)
+     return 12345;
+   return x;
+ }
+ 
+ /* { dg-final { scan-tree-dump-not "12345" "vrp1" } } */
+ /* { dg-final { cleanup-tree-dump "vrp1" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/vrp61.c
===================================================================
*** /dev/null	1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/tree-ssa/vrp61.c	2011-08-08 13:58:44.000000000 +0200
***************
*** 0 ****
--- 1,16 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fdump-tree-vrp1" } */
+ 
+ int f (int x, int y)
+ {
+   if (x > -1024 && x < 0 && y > -1024 && y < 0)
+     {
+       x = x ^ y;
+       if (x < 0 || x > 1023)
+ 	return 1234;
+     }
+   return x;
+ }
+ 
+ /* { dg-final { scan-tree-dump-not "1234" "vrp1" } } */
+ /* { dg-final { cleanup-tree-dump "vrp1" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/vrp57.c
===================================================================
*** gcc/testsuite/gcc.dg/tree-ssa/vrp57.c.orig	2011-04-28 11:47:33.000000000 +0200
--- gcc/testsuite/gcc.dg/tree-ssa/vrp57.c	2011-08-08 14:36:35.000000000 +0200
***************
*** 1,6 ****
  /* PR40052 */
  /* { dg-do compile } */
! /* { dg-options "-O -ftree-vrp -fdump-tree-optimized" } */
  
  int foo(_Bool b)
  {
--- 1,6 ----
  /* PR40052 */
  /* { dg-do compile } */
! /* { dg-options "-O -ftree-vrp -fno-tree-ccp -fdump-tree-optimized" } */
  
  int foo(_Bool b)
  {

Re: [PATCH] Extend VRP BIT_IOR_EXPR to handle sign-bit

[Richard Guenther]

On Mon, 8 Aug 2011, Richard Guenther wrote:

> On Mon, 8 Aug 2011, Richard Guenther wrote:
> 
> > On Fri, 5 Aug 2011, Paolo Bonzini wrote:
> > 
> > > On 08/05/2011 01:04 PM, Richard Guenther wrote:
> > > > (I believe that's the only bit we know sth about
> > > > when both vr.min and vr.max are negative).
> > > 
> > > Depends, if the value is between -2^16 and -1, we know something about all the
> > > bits to the left of bit 15.  I think a better mask is:
> > > 
> > > * MUST_BE_NONZERO = vr->min with all bits zero after the leftmost zero bit.
> > > Or, the leftmost clz(~vr->min) bits are one.
> > > * MAY_BE_NONZERO = all ones.
> > > 
> > > But something similar to xor_mask can likely be done with negative numbers
> > > too.  For example, if the value is between -32769 and -32768, you know that
> > > bits 1 to 14 are zero, and bits starting at 15 are one.
> > 
> > I have convinced myself that the current code handling ranges with
> > all positive values also works for ranges with all negative values.
> > Thus the patch even simplifies.  I've also adjusted the BIT_AND_EXPR
> > handling similar to the BIT_IOR_EXPR handling - now they at least
> > look symmetrical.
> 
> Actually we should adjust the ranges only if it's either all positive
> or negative values from the start and the adjustment keeps us on
> the same side of zero.

So we kept discussing this to death somewhat.  Which eventually resulted
in me doing some exhaustive testing and thinking again - which makes
me end up with the following, which passed bootstrap on 
x86_64-unknown-linux-gnu and is now in testing.

Richard.

2011-08-08  Richard Guenther  <rguenther@suse.de>

	* tree-vrp.c (zero_nonzero_bits_from_vr): Also return precise
	information for with only negative values.
	(extract_range_from_binary_expr_1): Adjust BIT_IOR_EXPR and
	BIT_AND_EXPR handling to handle ranges with negative values.

	* gcc.dg/tree-ssa/vrp57.c: Disable CCP.
	* gcc.dg/tree-ssa/vrp60.c: New testcase.
	* gcc.dg/tree-ssa/vrp61.c: Likewise.

Index: gcc/tree-vrp.c
===================================================================
*** gcc/tree-vrp.c.orig	2011-08-08 13:41:57.000000000 +0200
--- gcc/tree-vrp.c	2011-08-09 13:50:11.000000000 +0200
*************** vrp_int_const_binop (enum tree_code code
*** 2138,2186 ****
     the bit is 1, otherwise it might be 0 or 1.  */
  
  static bool
! zero_nonzero_bits_from_vr (value_range_t *vr, double_int *may_be_nonzero,
  			   double_int *must_be_nonzero)
  {
!   may_be_nonzero->low = ALL_ONES;
!   may_be_nonzero->high = ALL_ONES;
!   must_be_nonzero->low = 0;
!   must_be_nonzero->high = 0;
!   if (range_int_cst_p (vr))
!     {
!       if (range_int_cst_singleton_p (vr))
! 	{
! 	  *may_be_nonzero = tree_to_double_int (vr->min);
! 	  *must_be_nonzero = *may_be_nonzero;
! 	}
!       else if (tree_int_cst_sgn (vr->min) >= 0)
! 	{
! 	  double_int dmin = tree_to_double_int (vr->min);
! 	  double_int dmax = tree_to_double_int (vr->max);
! 	  double_int xor_mask = double_int_xor (dmin, dmax);
! 	  *may_be_nonzero = double_int_ior (dmin, dmax);
! 	  *must_be_nonzero = double_int_and (dmin, dmax);
! 	  if (xor_mask.high != 0)
! 	    {
! 	      unsigned HOST_WIDE_INT mask
! 		= ((unsigned HOST_WIDE_INT) 1
! 		   << floor_log2 (xor_mask.high)) - 1;
! 	      may_be_nonzero->low = ALL_ONES;
! 	      may_be_nonzero->high |= mask;
! 	      must_be_nonzero->low = 0;
! 	      must_be_nonzero->high &= ~mask;
! 	    }
! 	  else if (xor_mask.low != 0)
! 	    {
! 	      unsigned HOST_WIDE_INT mask
! 		= ((unsigned HOST_WIDE_INT) 1
! 		   << floor_log2 (xor_mask.low)) - 1;
! 	      may_be_nonzero->low |= mask;
! 	      must_be_nonzero->low &= ~mask;
! 	    }
  	}
-       return true;
      }
!   return false;
  }
  
  
--- 2138,2186 ----
     the bit is 1, otherwise it might be 0 or 1.  */
  
  static bool
! zero_nonzero_bits_from_vr (value_range_t *vr,
! 			   double_int *may_be_nonzero,
  			   double_int *must_be_nonzero)
  {
!   *may_be_nonzero = double_int_minus_one;
!   *must_be_nonzero = double_int_zero;
!   if (!range_int_cst_p (vr))
!     return false;
! 
!   if (range_int_cst_singleton_p (vr))
!     {
!       *may_be_nonzero = tree_to_double_int (vr->min);
!       *must_be_nonzero = *may_be_nonzero;
!     }
!   else if (tree_int_cst_sgn (vr->min) >= 0
! 	   || tree_int_cst_sgn (vr->max) < 0)
!     {
!       double_int dmin = tree_to_double_int (vr->min);
!       double_int dmax = tree_to_double_int (vr->max);
!       double_int xor_mask = double_int_xor (dmin, dmax);
!       *may_be_nonzero = double_int_ior (dmin, dmax);
!       *must_be_nonzero = double_int_and (dmin, dmax);
!       if (xor_mask.high != 0)
! 	{
! 	  unsigned HOST_WIDE_INT mask
! 	      = ((unsigned HOST_WIDE_INT) 1
! 		 << floor_log2 (xor_mask.high)) - 1;
! 	  may_be_nonzero->low = ALL_ONES;
! 	  may_be_nonzero->high |= mask;
! 	  must_be_nonzero->low = 0;
! 	  must_be_nonzero->high &= ~mask;
! 	}
!       else if (xor_mask.low != 0)
! 	{
! 	  unsigned HOST_WIDE_INT mask
! 	      = ((unsigned HOST_WIDE_INT) 1
! 		 << floor_log2 (xor_mask.low)) - 1;
! 	  may_be_nonzero->low |= mask;
! 	  must_be_nonzero->low &= ~mask;
  	}
      }
! 
!   return true;
  }
  
  
*************** extract_range_from_binary_expr_1 (value_
*** 2650,2699 ****
        type = VR_RANGE;
        if (code == BIT_AND_EXPR)
  	{
  	  min = double_int_to_tree (expr_type,
  				    double_int_and (must_be_nonzero0,
  						    must_be_nonzero1));
! 	  max = double_int_to_tree (expr_type,
! 				    double_int_and (may_be_nonzero0,
! 						    may_be_nonzero1));
! 	  if (tree_int_cst_sgn (min) < 0)
! 	    min = NULL_TREE;
! 	  if (tree_int_cst_sgn (max) < 0)
! 	    max = NULL_TREE;
  	  if (int_cst_range0 && tree_int_cst_sgn (vr0.min) >= 0)
! 	    {
! 	      if (min == NULL_TREE)
! 		min = build_int_cst (expr_type, 0);
! 	      if (max == NULL_TREE || tree_int_cst_lt (vr0.max, max))
! 		max = vr0.max;
! 	    }
  	  if (int_cst_range1 && tree_int_cst_sgn (vr1.min) >= 0)
! 	    {
! 	      if (min == NULL_TREE)
! 		min = build_int_cst (expr_type, 0);
! 	      if (max == NULL_TREE || tree_int_cst_lt (vr1.max, max))
! 		max = vr1.max;
! 	    }
  	}
        else if (code == BIT_IOR_EXPR)
  	{
! 	  min = double_int_to_tree (expr_type,
! 				    double_int_ior (must_be_nonzero0,
! 						    must_be_nonzero1));
  	  max = double_int_to_tree (expr_type,
  				    double_int_ior (may_be_nonzero0,
  						    may_be_nonzero1));
! 	  if (tree_int_cst_sgn (max) < 0)
! 	    max = NULL_TREE;
! 	  if (int_cst_range0)
! 	    {
! 	      if (tree_int_cst_sgn (min) < 0)
! 		min = vr0.min;
! 	      else
! 		min = vrp_int_const_binop (MAX_EXPR, min, vr0.min);
! 	    }
! 	  if (int_cst_range1)
! 	    min = vrp_int_const_binop (MAX_EXPR, min, vr1.min);
  	}
        else if (code == BIT_XOR_EXPR)
  	{
--- 2650,2712 ----
        type = VR_RANGE;
        if (code == BIT_AND_EXPR)
  	{
+ 	  double_int dmax;
  	  min = double_int_to_tree (expr_type,
  				    double_int_and (must_be_nonzero0,
  						    must_be_nonzero1));
! 	  dmax = double_int_and (may_be_nonzero0, may_be_nonzero1);
! 	  /* If both input ranges contain only negative values we can
! 	     truncate the result range maximum to the minimum of the
! 	     input range maxima.  */
! 	  if (int_cst_range0 && int_cst_range1
! 	      && tree_int_cst_sgn (vr0.max) < 0
! 	      && tree_int_cst_sgn (vr1.max) < 0)
! 	    {
! 	      dmax = double_int_min (dmax, tree_to_double_int (vr0.max),
! 				     TYPE_UNSIGNED (expr_type));
! 	      dmax = double_int_min (dmax, tree_to_double_int (vr1.max),
! 				     TYPE_UNSIGNED (expr_type));
! 	    }
! 	  /* If either input range contains only non-negative values
! 	     we can truncate the result range maximum to the respective
! 	     maximum of the input range.  */
  	  if (int_cst_range0 && tree_int_cst_sgn (vr0.min) >= 0)
! 	    dmax = double_int_min (dmax, tree_to_double_int (vr0.max),
! 				   TYPE_UNSIGNED (expr_type));
  	  if (int_cst_range1 && tree_int_cst_sgn (vr1.min) >= 0)
! 	    dmax = double_int_min (dmax, tree_to_double_int (vr1.max),
! 				   TYPE_UNSIGNED (expr_type));
! 	  max = double_int_to_tree (expr_type, dmax);
  	}
        else if (code == BIT_IOR_EXPR)
  	{
! 	  double_int dmin;
  	  max = double_int_to_tree (expr_type,
  				    double_int_ior (may_be_nonzero0,
  						    may_be_nonzero1));
! 	  dmin = double_int_ior (must_be_nonzero0, must_be_nonzero1);
! 	  /* If the input ranges contain only positive values we can
! 	     truncate the minimum of the result range to the maximum
! 	     of the input range minima.  */
! 	  if (int_cst_range0 && int_cst_range1
! 	      && tree_int_cst_sgn (vr0.min) >= 0
! 	      && tree_int_cst_sgn (vr1.min) >= 0)
! 	    {
! 	      dmin = double_int_max (dmin, tree_to_double_int (vr0.min),
! 				     TYPE_UNSIGNED (expr_type));
! 	      dmin = double_int_max (dmin, tree_to_double_int (vr1.min),
! 				     TYPE_UNSIGNED (expr_type));
! 	    }
! 	  /* If either input range contains only negative values
! 	     we can truncate the minimum of the result range to the
! 	     respective minimum range.  */
! 	  if (int_cst_range0 && tree_int_cst_sgn (vr0.max) < 0)
! 	    dmin = double_int_max (dmin, tree_to_double_int (vr0.min),
! 				   TYPE_UNSIGNED (expr_type));
! 	  if (int_cst_range1 && tree_int_cst_sgn (vr1.max) < 0)
! 	    dmin = double_int_max (dmin, tree_to_double_int (vr1.min),
! 				   TYPE_UNSIGNED (expr_type));
! 	  min = double_int_to_tree (expr_type, dmin);
  	}
        else if (code == BIT_XOR_EXPR)
  	{
*************** extract_range_from_binary_expr_1 (value_
*** 2714,2727 ****
  	  max = double_int_to_tree (expr_type,
  				    double_int_not (result_zero_bits));
  	  min = double_int_to_tree (expr_type, result_one_bits);
! 	  /* Return a [min, max] range if we know the
! 	     result range is either positive or negative.  */
! 	  if (tree_int_cst_sgn (max) >= 0)
! 	    /* The range is bound by a lower value of 0.  */;
! 	  else if (tree_int_cst_sgn (min) < 0)
! 	    /* The range is bound by an upper value of -1.  */;
  	  else
- 	    /* We don't know whether the sign bit is set or not.  */
  	    max = min = NULL_TREE;
  	}
        else
--- 2727,2738 ----
  	  max = double_int_to_tree (expr_type,
  				    double_int_not (result_zero_bits));
  	  min = double_int_to_tree (expr_type, result_one_bits);
! 	  /* If the range has all positive or all negative values the
! 	     result is better than VARYING.  */
! 	  if (tree_int_cst_sgn (min) < 0
! 	      || tree_int_cst_sgn (max) >= 0)
! 	    ;
  	  else
  	    max = min = NULL_TREE;
  	}
        else
Index: gcc/testsuite/gcc.dg/tree-ssa/vrp60.c
===================================================================
*** /dev/null	1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/tree-ssa/vrp60.c	2011-08-08 13:43:09.000000000 +0200
***************
*** 0 ****
--- 1,31 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fno-tree-ccp -fno-tree-dominator-opts -fdump-tree-vrp1" } */
+ 
+ int foo (int x, int b)
+ {
+   int cst;
+   if (b)
+     cst = -__INT_MAX__ - 1;
+   else
+     cst = -__INT_MAX__;
+   x = x | cst;
+   if (x >= 0)
+     return 12345;
+   return x;
+ }
+ 
+ int bar (int x, int b)
+ {
+   int cst;
+   if (b)
+     cst = __INT_MAX__;
+   else
+     cst = __INT_MAX__ - 1;
+   x = x & cst;
+   if (x < 0)
+     return 12345;
+   return x;
+ }
+ 
+ /* { dg-final { scan-tree-dump-not "12345" "vrp1" } } */
+ /* { dg-final { cleanup-tree-dump "vrp1" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/vrp61.c
===================================================================
*** /dev/null	1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/tree-ssa/vrp61.c	2011-08-08 13:58:44.000000000 +0200
***************
*** 0 ****
--- 1,16 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fdump-tree-vrp1" } */
+ 
+ int f (int x, int y)
+ {
+   if (x > -1024 && x < 0 && y > -1024 && y < 0)
+     {
+       x = x ^ y;
+       if (x < 0 || x > 1023)
+ 	return 1234;
+     }
+   return x;
+ }
+ 
+ /* { dg-final { scan-tree-dump-not "1234" "vrp1" } } */
+ /* { dg-final { cleanup-tree-dump "vrp1" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/vrp57.c
===================================================================
*** gcc/testsuite/gcc.dg/tree-ssa/vrp57.c.orig	2011-04-28 11:47:33.000000000 +0200
--- gcc/testsuite/gcc.dg/tree-ssa/vrp57.c	2011-08-08 14:36:35.000000000 +0200
***************
*** 1,6 ****
  /* PR40052 */
  /* { dg-do compile } */
! /* { dg-options "-O -ftree-vrp -fdump-tree-optimized" } */
  
  int foo(_Bool b)
  {
--- 1,6 ----
  /* PR40052 */
  /* { dg-do compile } */
! /* { dg-options "-O -ftree-vrp -fno-tree-ccp -fdump-tree-optimized" } */
  
  int foo(_Bool b)
  {
Index: gcc/testsuite/gcc.dg/tree-ssa/vrp62.c
===================================================================
*** /dev/null	1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/tree-ssa/vrp62.c	2011-08-09 13:27:05.000000000 +0200
***************
*** 0 ****
--- 1,110 ----
+ /* { dg-do run } */
+ /* { dg-options "-O2 -fno-tree-ccp -fno-tree-dominator-opts" } */
+ 
+ /* Tests generated via  */
+ 
+ #if 0
+ #include <stdio.h>
+ int main(int argc, char **argv)
+ {
+   int amin, amax, bmin, bmax, a, b;
+   int testno = 0;
+   int min = atoi (argv[1]);
+   int max = atoi (argv[2]);
+   char op = argv[3][0];
+   printf ("/* Testing range [%d, %d] with operator %c.  */\n", min, max, op);
+   printf ("extern void abort (void);\n");
+   for (amin = min; amin <= max; ++amin)
+     for (amax = amin; amax <= max; ++amax)
+       for (bmin = min; bmin <= max; ++bmin)
+ 	for (bmax = bmin; bmax <= max; ++bmax)
+ 	  {
+ 	    ++testno;
+ 	    printf ("int test%d (int a, int b)\n"
+ 		    "{\n"
+ 		    "  if (a >= %d && a <= %d && b >= %d && b <= %d)\n"
+ 		    "   {\n"
+ 		    "      int x = a %c b;\n"
+ 		    "      if (0\n", testno, amin, amax, bmin, bmax, op);
+ 	    for (a = amin; a <= amax; ++a)
+ 	      for (b = bmin; b <= bmax; ++b)
+ 		printf ("|| x == (%d %c %d)\n", a, op, b);
+ 	    printf ("         ) return 0;\n"
+ 		    "      abort ();\n"
+ 		    "   }\n"
+ 		    "  return 0;\n"
+ 		    "}\n");
+ 	  }
+   printf ("int main()\n"
+ 	  "{\n"
+ 	  "  int a, b;\n"
+ 	  "  for (a = %d; a <= %d; ++a)\n"
+ 	  "    for (b = %d; b <= %d; ++b)\n"
+ 	  "      {\n", min, max, min, max);
+   for (; testno > 0; --testno)
+     printf ("      test%d (a, b);\n", testno);
+   printf ("      }\n"
+ 	  "  return 0;\n"
+ 	  "}\n");
+   return 0;
+ }
+ #endif
+ 
+ extern void abort (void);
+ 
+ int test381 (int a, int b)
+ {
+   if (a >= -3 && a <= -1 && b >= -2 && b <= 3)
+     {
+       int x = a | b;
+       if (x == (-3 | -2)
+ 	  || x == (-3 | -1)
+ 	  || x == (-3 | 0)
+ 	  || x == (-3 | 1)
+ 	  || x == (-3 | 2)
+ 	  || x == (-3 | 3)
+ 	  || x == (-2 | -2)
+ 	  || x == (-2 | -1)
+ 	  || x == (-2 | 0)
+ 	  || x == (-2 | 1)
+ 	  || x == (-2 | 2)
+ 	  || x == (-2 | 3)
+ 	  || x == (-1 | -2)
+ 	  || x == (-1 | -1)
+ 	  || x == (-1 | 0)
+ 	  || x == (-1 | 1)
+ 	  || x == (-1 | 2)
+ 	  || x == (-1 | 3))
+ 	return 0;
+       abort ();
+     }
+   return 0;
+ }
+ 
+ int test900 (int a, int b)
+ {
+   if (a >= -1 && a <= 2 && b >= 3 && b <= 3)
+     {
+       int x = a & b;
+       if (x == (-1 & 3)
+ 	  || x == (0 & 3)
+ 	  || x == (1 & 3)
+ 	  || x == (2 & 3))
+ 	return 0;
+       abort ();
+     }
+   return 0;
+ }
+ 
+ int main()
+ {
+   int a, b;
+   for (a = -4; a < 4; ++a)
+     for (b = -4; b < 4; ++b)
+       {
+ 	test381 (a, b);
+ 	test900 (a, b);
+       }
+ 
+   return 0;
+ }

Re: [PATCH] Extend VRP BIT_IOR_EXPR to handle sign-bit

[Jay Foad]

On 9 August 2011 13:23, Richard Guenther <rguenther@suse.de> wrote:
> 2011-08-08  Richard Guenther  <rguenther@suse.de>
>
>        * tree-vrp.c (zero_nonzero_bits_from_vr): Also return precise
>        information for with only negative values.

"for *ranges* with" ?

Jay.

Re: [PATCH] Extend VRP BIT_IOR_EXPR to handle sign-bit

[Michael Matz]

Hi,

On Tue, 9 Aug 2011, Richard Guenther wrote:

> > Actually we should adjust the ranges only if it's either all positive 
> > or negative values from the start and the adjustment keeps us on the 
> > same side of zero.
> 
> So we kept discussing this to death somewhat.  Which eventually resulted 
> in me doing some exhaustive testing and thinking again - which makes me 
> end up with the following, which passed bootstrap on 
> x86_64-unknown-linux-gnu and is now in testing.

Sigh.  So the strange asymmetry with the [0,1] & [-2] example that itched 
me really pointed to a problem, we just couldn't pinpoint it.  We'll 
have to upgrade our white-board-calculating skills ;)


Ciao,
Michael.