[PATCH] Extend VRP BIT_IOR_EXPR to handle sign-bit
Richard Guenther
rguenther@suse.de
Mon Aug 8 13:48:00 GMT 2011
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)
{
More information about the Gcc-patches
mailing list