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 <rguent...@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" } } */
