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 <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/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;
+ }
