This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [RFA] [PATCH] Make VRP understand bitwise OR and AND (better than now)
On Tue, 2008-08-12 at 04:20 -0400, Jakub Jelinek wrote:
> On Tue, Aug 12, 2008 at 10:09:13AM +0200, Richard Guenther wrote:
> > > Please find it attached. I did run testsuite, twice, once with
> > > deliberately broken test and one with test as it is in the patch.
> > > (Boy, that was SLOW).
> >
> > The patch is ok for mainline if it passed a bootstrap as well.
It passed bootstrap on my machine.
> But the ChangeLog entry needs fixing up. Should be something like:
>
> 2008-08-12 Denys Vlasenko <dvlasenk@redhat.com>
>
> PR tree-optimization/28632
> * tree-vrp.c (bits_always_set, bits_maybe_set,
> integer_nonnegative_range): New functions.
> (extract_range_from_binary_expr): Improve value range propagation
> through bitwise AND and OR.
>
> and you also need
>
> 2008-08-12 Denys Vlasenko <dvlasenk@redhat.com>
>
> PR tree-optimization/28632
> * gcc.dg/pr28632.c: New test.
>
> in testsuite/ChangeLog (and it should be sent in cleartext with the
> patch, rather than as part of the patch - the ChangeLog changes many times
> a day, so patches don't apply cleanly when committing).
>
> Jakub
Updated patch (with changelog entry removed) is attached.
gcc/ChangeLog:
2008-08-12 Denys Vlasenko <dvlasenk@redhat.com>
PR tree-optimization/28632
* tree-vrp.c (bits_always_set, bits_maybe_set,
integer_nonnegative_range): New functions.
(extract_range_from_binary_expr): Improve value range
propagation through bitwise AND and OR.
gcc/testsuite/ChangeLog:
2008-08-12 Denys Vlasenko <dvlasenk@redhat.com>
PR tree-optimization/28632
* gcc.dg/pr28632.c: New test.
--
vda
diff -d -urpN gcc-4.4.svn.0/gcc/testsuite/gcc.dg/pr28632.c gcc-4.4.svn.2/gcc/testsuite/gcc.dg/pr28632.c
--- gcc-4.4.svn.0/gcc/testsuite/gcc.dg/pr28632.c 1970-01-01 01:00:00.000000000 +0100
+++ gcc-4.4.svn.2/gcc/testsuite/gcc.dg/pr28632.c 2008-08-11 21:32:15.000000000 +0200
@@ -0,0 +1,42 @@
+/* { dg-do compile } */
+/* { dg-options "-O2" } */
+
+void v4 (unsigned a, unsigned b)
+{
+ if (a < 0x1000) return;
+ if (a > 0x1000) return;
+ if (b < 0x0110) return;
+ /* VRP must figure out that this is always true. */
+ if (!__builtin_constant_p ((a|b) >= 0x01000))
+ asm("the.bug.is.here");
+ /* VRP must not think that this is always true. */
+ if (__builtin_constant_p ((a|b) >= 0x10000))
+ asm("the.bug.is.here");
+}
+
+void u4 (unsigned n)
+{
+ if (n > 0x10111) return;
+ if (n < 0x10101) return;
+ /* VRP must figure out that this is always true. */
+ if (!__builtin_constant_p (n & 0x00100))
+ asm("the.bug.is.here");
+ /* VRP must not think that this is always true. */
+ if (__builtin_constant_p (n & 0x00001))
+ asm("the.bug.is.here");
+ /* Another case to test:
+ (n & 0x01000) is never true, but we can't figure it out yet. */
+}
+
+void v5 (int a, int b)
+{
+ if (a < 0x1000) return;
+ if (a > 0x1000) return;
+ if (b < 0x0110) return;
+ /* VRP must figure out that this is always true. */
+ if (!__builtin_constant_p ((a|b) >= 0x01000))
+ asm("the.bug.is.here");
+ /* VRP must not think that this is always true. */
+ if (__builtin_constant_p ((a|b) >= 0x10000))
+ asm("the.bug.is.here");
+}
diff -d -urpN gcc-4.4.svn.0/gcc/tree-vrp.c gcc-4.4.svn.2/gcc/tree-vrp.c
--- gcc-4.4.svn.0/gcc/tree-vrp.c 2008-08-01 15:47:26.000000000 +0200
+++ gcc-4.4.svn.2/gcc/tree-vrp.c 2008-08-11 17:51:14.000000000 +0200
@@ -1995,6 +1995,110 @@ vrp_int_const_binop (enum tree_code code
return res;
}
+/* Combines MIN and MAX as follows:
+ MIN = 01010010101001010010
+ MAX = 01010010100000010010
+ result: 01010010100000000000
+ This tells us which bits are always 1 for any X in [MIN, MAX]. */
+
+static double_int
+bits_always_set (double_int min_di, double_int max_di)
+{
+ double_int xored_di, result_di;
+ int bitpos;
+
+ result_di.low = min_di.low & max_di.low;
+ result_di.high = min_di.high & max_di.high;
+
+ /* Result may have lower common bits set, need to clear those. */
+ /* Find bit position of highest differing bit. */
+ xored_di.low = min_di.low ^ max_di.low;
+ xored_di.high = min_di.high ^ max_di.high;
+ /* Is there such bit? */
+ if (xored_di.high)
+ {
+ /* Clear all bits below it (the bit itself is already 0). */
+ bitpos = floor_log2 (xored_di.high);
+ result_di.low = 0;
+ result_di.high &= ~(((unsigned HOST_WIDE_INT)1 << bitpos) - 1);
+ }
+ else if (xored_di.low)
+ {
+ bitpos = floor_log2 (xored_di.low);
+ result_di.low &= ~(((unsigned HOST_WIDE_INT)1 << bitpos) - 1);
+ }
+ return result_di;
+}
+
+/* Combines MIN and MAX as follows:
+ MAX = 01010010101001010010
+ MIN = 01010010100000010010
+ result: 01010010101111111111.
+ Zeros are bits which are always 0 for any X in [MIN, MAX].
+ Conversely, ones are bits can be set. */
+
+static double_int
+bits_maybe_set (double_int min_di, double_int max_di)
+{
+ double_int xored_di, result_di;
+ int bitpos;
+
+ result_di.low = min_di.low | max_di.low;
+ result_di.high = min_di.high | max_di.high;
+
+ /* Find bit position of highest differing bit. */
+ xored_di.low = min_di.low ^ max_di.low;
+ xored_di.high = min_di.high ^ max_di.high;
+ if (xored_di.high)
+ {
+ bitpos = floor_log2 (xored_di.high);
+ /* Build a 0000001111 mask, OR it to the result. */
+ result_di.low = ALL_ONES;
+ result_di.high |= ((unsigned HOST_WIDE_INT)1 << bitpos) - 1;
+ }
+ else if (xored_di.low & (ALL_ONES - 1))
+ {
+ bitpos = floor_log2 (xored_di.low);
+ result_di.low |= ((unsigned HOST_WIDE_INT)1 << bitpos) - 1;
+ }
+ return result_di;
+}
+
+/* Are both ends of this range known, are integers, and >= 0? */
+
+static int
+integer_nonnegative_range (value_range_t *vr)
+{
+ if (vr->type == VR_RANGE
+ && TREE_CODE (vr->min) == INTEGER_CST
+ && TREE_CODE (vr->max) == INTEGER_CST
+ && tree_int_cst_sgn (vr->min) >= 0
+ && tree_int_cst_sgn (vr->max) >= 0
+ && !TREE_OVERFLOW (vr->max))
+ {
+ double_int di = tree_to_double_int (vr->max);
+ int width = tree_to_double_int (TYPE_SIZE (TREE_TYPE (vr->max))).low;
+ /* If high-order bit is set, even for unsigned ints, it is unsafe
+ to infer ranges. As a signed int, it can be negative.
+ I'm not sure that we do not just hit a latent bug elsewhere,
+ originally I expected that this would not be needed. */
+ if (width > HOST_BITS_PER_WIDE_INT)
+ {
+ width -= (HOST_BITS_PER_WIDE_INT + 1);
+ if (di.high & (ALL_ONES << width))
+ {
+ return 0;
+ }
+ }
+ width--;
+ if (di.high || (di.low & (ALL_ONES << width)))
+ {
+ return 0;
+ }
+ return 1;
+ }
+ return 0;
+}
/* Extract range information from a binary expression EXPR based on
the ranges of each of its operands and the expression code. */
@@ -2025,6 +2129,7 @@ extract_range_from_binary_expr (value_ra
&& code != MIN_EXPR
&& code != MAX_EXPR
&& code != BIT_AND_EXPR
+ && code != BIT_IOR_EXPR
&& code != TRUTH_AND_EXPR
&& code != TRUTH_OR_EXPR)
{
@@ -2048,6 +2153,98 @@ extract_range_from_binary_expr (value_ra
else
set_value_range_to_varying (&vr1);
+ /* Bitwise ops. */
+ /* Width and signedness of operands is always the same here. */
+ if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR)
+ {
+ if (integer_nonnegative_range (&vr0))
+ {
+ if (integer_nonnegative_range (&vr1))
+ {
+ double_int always_set0, always_set1;
+ double_int maybe_set0, maybe_set1;
+ double_int min_di, max_di;
+
+ /* In always_setX, ones indicate "always set" bits. */
+ /* In maybe_setX, ZEROES indicate "always unset" bits,
+ ones indicate bits which are "maybe set". */
+ min_di = tree_to_double_int (vr0.min);
+ max_di = tree_to_double_int (vr0.max);
+ always_set0 = bits_always_set (min_di, max_di);
+ maybe_set0 = bits_maybe_set (min_di, max_di);
+ min_di = tree_to_double_int (vr1.min);
+ max_di = tree_to_double_int (vr1.max);
+ always_set1 = bits_always_set (min_di, max_di);
+ maybe_set1 = bits_maybe_set (min_di, max_di);
+ if (code == BIT_AND_EXPR)
+ {
+ /* If bit is always set in a AND in b,
+ it will be set in (a & b). */
+ min_di.low = always_set0.low & always_set1.low;
+ min_di.high = always_set0.high & always_set1.high;
+ /* If bit is maybe set in a AND in b,
+ it may be set in (a & b).
+ Example: max(010x & 10xx) = 0001
+ (maybe_set0 = 0101, maybe_set1 = 1011). */
+ max_di.low = maybe_set0.low & maybe_set1.low;
+ max_di.high = maybe_set0.high & maybe_set1.high;
+ }
+ else
+ {
+ min_di.low = always_set0.low | always_set1.low;
+ min_di.high = always_set0.high | always_set1.high;
+ max_di.low = maybe_set0.low | maybe_set1.low;
+ max_di.high = maybe_set0.high | maybe_set1.high;
+ }
+ min = double_int_to_tree (expr_type, min_di);
+ max = double_int_to_tree (expr_type, max_di);
+ set_value_range (vr, VR_RANGE, min, max, NULL);
+ return;
+ }
+ /* Only op0 has nonnegative range. */
+ if (code == BIT_AND_EXPR)
+ {
+ /* We positively sure that (op0 & op1) can't be
+ larger than vr0.max. */
+ max = vr0.max;
+ min = build_int_cst (expr_type, 0);
+ set_value_range (vr, VR_RANGE, min, max, NULL);
+ return;
+ }
+ if (TYPE_UNSIGNED (expr_type))
+ {
+ /* If result is unsigned,
+ we still can derive that (op0 | op1) >= op0.min. */
+ min = vr0.min;
+ max = TYPE_MAX_VALUE (expr_type);
+ set_value_range (vr, VR_RANGE, min, max, NULL);
+ return;
+ }
+ set_value_range_to_varying (vr);
+ return;
+ }
+ if (integer_nonnegative_range (&vr1))
+ {
+ /* Only op1 has nonnegative range. */
+ if (code == BIT_AND_EXPR)
+ {
+ max = vr1.max;
+ min = build_int_cst (expr_type, 0);
+ set_value_range (vr, VR_RANGE, min, max, NULL);
+ return;
+ }
+ if (TYPE_UNSIGNED (expr_type))
+ {
+ min = vr1.min;
+ max = TYPE_MAX_VALUE (expr_type);
+ set_value_range (vr, VR_RANGE, min, max, NULL);
+ return;
+ }
+ }
+ set_value_range_to_varying (vr);
+ return;
+ }
+
/* If either range is UNDEFINED, so is the result. */
if (vr0.type == VR_UNDEFINED || vr1.type == VR_UNDEFINED)
{
@@ -2059,12 +2256,8 @@ extract_range_from_binary_expr (value_ra
type = vr0.type;
/* Refuse to operate on VARYING ranges, ranges of different kinds
- and symbolic ranges. As an exception, we allow BIT_AND_EXPR
- because we may be able to derive a useful range even if one of
- the operands is VR_VARYING or symbolic range. TODO, we may be
- able to derive anti-ranges in some cases. */
- if (code != BIT_AND_EXPR
- && code != TRUTH_AND_EXPR
+ and symbolic ranges. */
+ if (code != TRUTH_AND_EXPR
&& code != TRUTH_OR_EXPR
&& (vr0.type == VR_VARYING
|| vr1.type == VR_VARYING
@@ -2342,33 +2535,6 @@ extract_range_from_binary_expr (value_ra
min = vrp_int_const_binop (code, vr0.min, vr1.max);
max = vrp_int_const_binop (code, vr0.max, vr1.min);
}
- else if (code == BIT_AND_EXPR)
- {
- if (vr0.type == VR_RANGE
- && vr0.min == vr0.max
- && TREE_CODE (vr0.max) == INTEGER_CST
- && !TREE_OVERFLOW (vr0.max)
- && tree_int_cst_sgn (vr0.max) >= 0)
- {
- min = build_int_cst (expr_type, 0);
- max = vr0.max;
- }
- else if (vr1.type == VR_RANGE
- && vr1.min == vr1.max
- && TREE_CODE (vr1.max) == INTEGER_CST
- && !TREE_OVERFLOW (vr1.max)
- && tree_int_cst_sgn (vr1.max) >= 0)
- {
- type = VR_RANGE;
- min = build_int_cst (expr_type, 0);
- max = vr1.max;
- }
- else
- {
- set_value_range_to_varying (vr);
- return;
- }
- }
else
gcc_unreachable ();