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 Mon, 2008-08-04 at 14:26 +0200, Richard Guenther wrote:
> On Mon, Aug 4, 2008 at 2:02 PM, Denys Vlasenko <dvlasenk@redhat.com> wrote:
> > This is a patch for bug 28632 "VRP should understand bitwise OR and AND"
> > http://gcc.gnu.org/bugzilla/show_bug.cgi?id=28632
> >
> > This patch is bootstrapping successfully on current gcc svn.
> >
> > bug28632_instrumented.patch is an instrumented version of the patch.
> > Set $VDA_DEBUG to the name of a file and gcc will append debug printouts to it
> > showing how it deduced value ranges for (a | b) and (a & b).
> >
> > // extract_range_from_binary_expr(OR)[u32]
> > // a integer_nonnegative_range(unsigned int __bid_IDEC_glbflags.40_536)=0
> > // b integer_nonnegative_range(_IDEC_flags[u32],[16,16])=1
> > if (a | b) < (16) || (a | b) > (4294967295)) err();
> >
> > [gcc inferred that since b = 16, (a | b) is always >= 16,
> > despite the fact we do not know value range of a]
> >
> > // extract_range_from_binary_expr(AND)[u32]
> > // a integer_nonnegative_range(unsigned int[u32],[0,4294967295])=1
> > // b integer_nonnegative_range(_IDEC_round[u32],[1,1])=1
> > // bits_always_set(0,4294967295)=[u32]0
> > // bits_always_set(1,1)=[u32]1
> > // bits_maybe_set(0,4294967295)=[u32]4294967295
> > // bits_maybe_set(1,1)=[u32]1
> > if (a & b) < 0 || (a & b) > 1 err();
> >
> > [a case where both operands had known positive range]
...
...
> In extract_range_from_binary_expr it looks like the cases for
> BIT_AND_EXPR and BIT_IOR_EXPR can share most (if not all) of
> the code if you use the expression code instead of constant codes.
>
> In bits_always_set and bits_maybe_set it is better to use double_ints
> (see double_int.h) for intermediate calculations, as they do not involve
> allocating new tree constants.
The updated patch is attached (with instrumentation code present but
#defined out).
> integer_nonnegative_range needs a comment.
Fixed.
Please review attached patch.
--
vda
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 13:56:19.000000000 +0200
@@ -1995,6 +1995,179 @@ vrp_int_const_binop (enum tree_code code
return res;
}
+#define VDA_DEBUG 0
+
+#if VDA_DEBUG
+static FILE *vda_file;
+#endif
+
+/* 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);
+ }
+#if VDA_DEBUG
+ if (vda_file)
+ {
+ fprintf (vda_file, "// %s(%016lx, %016lx)=%016lx\n", "bits_always_set", min_di.low, max_di.low, result_di.low);
+ }
+#endif
+ 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;
+#if VDA_DEBUG
+ if (vda_file)
+ {
+ fprintf (vda_file, "// %s(%016lx, %016lx)=%016lx @a [%016lx:%d]\n", "bits_maybe_set", min_di.low, max_di.low, result_di.low, xored_di.low, bitpos);
+ }
+#endif
+ }
+ else if (xored_di.low & (ALL_ONES - 1))
+ {
+ bitpos = floor_log2 (xored_di.low);
+ result_di.low |= ((unsigned HOST_WIDE_INT)1 << bitpos) - 1;
+#if VDA_DEBUG
+ if (vda_file)
+ {
+ fprintf (vda_file, "// %s(%016lx, %016lx)=%016lx @b [%016lx:%d]\n", "bits_maybe_set", min_di.low, max_di.low, result_di.low, xored_di.low, bitpos);
+ }
+#endif
+ }
+#if VDA_DEBUG
+ else if (vda_file)
+ {
+ fprintf (vda_file, "// %s(%016lx, %016lx)=%016lx @c\n", "bits_maybe_set", min_di.low, max_di.low, result_di.low);
+ }
+#endif
+ return result_di;
+}
+
+/* Are both ends of this range known, are integers, and >= 0? */
+
+#if !VDA_DEBUG
+/* Only vr is used if not debugging. */
+#define integer_nonnegative_range(vr, val, vall) integer_nonnegative_range(vr)
+#endif
+static int
+integer_nonnegative_range (value_range_t *vr, tree val, char vall)
+{
+ 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 VDA_DEBUG
+ if (vda_file)
+ { /* 'if ((uNN)a >= 0 && (uNN)a <= 27030)" */
+ tree val_type = TREE_TYPE (val);
+ fprintf (vda_file, "if ((%c%ld)%c >= ",
+ TYPE_UNSIGNED (val_type) ? 'u' : 's',
+ tree_to_double_int (TYPE_SIZE (val_type)).low,
+ vall
+ );
+ print_generic_expr (vda_file, vr->min, 0);
+ fprintf (vda_file, " && (%c%ld)%c <= ",
+ TYPE_UNSIGNED (val_type) ? 'u' : 's',
+ tree_to_double_int (TYPE_SIZE (val_type)).low,
+ vall
+ );
+ print_generic_expr (vda_file, vr->max, 0);
+ fprintf (vda_file, ")\n");
+ }
+#endif
+ /* 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))
+ {
+#if VDA_DEBUG
+ if (vda_file) fprintf (vda_file, "// integer_nonnegative_range: BAIL OUT high\n");
+#endif
+ return 0;
+ }
+ }
+ width--;
+ if (di.high || (di.low & (ALL_ONES << width)))
+ {
+#if VDA_DEBUG
+ if (vda_file) fprintf (vda_file, "// integer_nonnegative_range: BAIL OUT low\n");
+#endif
+ return 0;
+ }
+ return 1;
+ }
+#if VDA_DEBUG
+ if (vda_file)
+ {
+ fprintf (vda_file, "// %c %s(", vall, "integer_nonnegative_range");
+ print_generic_expr (vda_file, TREE_TYPE (val), 0);
+ fprintf (vda_file, " ");
+ print_generic_expr (vda_file, val, 0);
+ fprintf (vda_file, ")=0\n");
+ }
+#endif
+ return 0;
+}
/* Extract range information from a binary expression EXPR based on
the ranges of each of its operands and the expression code. */
@@ -2010,6 +2183,17 @@ extract_range_from_binary_expr (value_ra
value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
+#if VDA_DEBUG
+ char typebuf[16];
+ static int inited;
+ if (!inited)
+ {
+ if (getenv ("VDA_DEBUG"))
+ vda_file = fopen (getenv ("VDA_DEBUG"), "a");
+ inited = 1;
+ }
+#endif
+
/* Not all binary expressions can be applied to ranges in a
meaningful way. Handle only arithmetic operations. */
if (code != PLUS_EXPR
@@ -2025,6 +2209,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)
{
@@ -2032,6 +2217,19 @@ extract_range_from_binary_expr (value_ra
return;
}
+#if VDA_DEBUG
+ if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR)
+ if (vda_file)
+ {
+ sprintf (typebuf, "%c%ld",
+ TYPE_UNSIGNED (expr_type) ? 'u' : 's',
+ tree_to_double_int (TYPE_SIZE (expr_type)).low);
+ fprintf (vda_file, "// %s(%s)[%s]\n",
+ "extract_range_from_binary_expr",
+ code == BIT_AND_EXPR ? "AND" : "OR", typebuf);
+ }
+#endif
+
/* Get value ranges for each operand. For constant operands, create
a new value range with the operand to simplify processing. */
if (TREE_CODE (op0) == SSA_NAME)
@@ -2048,6 +2246,156 @@ 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 VDA_DEBUG
+ char opc = (code == BIT_AND_EXPR ? '&' : '|');
+#endif
+
+ if (integer_nonnegative_range (&vr0, op0, 'a'))
+ {
+ if (integer_nonnegative_range (&vr1, op1, 'b'))
+ {
+ 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);
+#if VDA_DEBUG
+ if (vda_file)
+ { /* "if ((a & b) < 0x0000000000000000 || (a & b) > 0x0000000000000001) err();" */
+ fprintf (vda_file, " if ((%s)(a %c b) < 0x%016lx || (%s)(a %c b) > 0x%016lx) err();\n",
+ typebuf, opc, tree_to_double_int (min).low,
+ typebuf, opc, tree_to_double_int (max).low);
+ }
+#endif
+ 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);
+#if VDA_DEBUG
+ if (vda_file)
+ {
+ fprintf (vda_file, " if ((%s)(a %c b) < 0x%016lx || (%s)(a %c b) > 0x%016lx) err();\n",
+ typebuf, opc, tree_to_double_int (min).low,
+ typebuf, opc, tree_to_double_int (max).low);
+ }
+#endif
+ 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);
+#if VDA_DEBUG
+ if (vda_file)
+ {
+ fprintf (vda_file, " if ((%s)(a %c b) < 0x%016lx || (%s)(a %c b) > 0x%016lx) err();\n",
+ typebuf, opc, tree_to_double_int (min).low,
+ typebuf, opc, tree_to_double_int (max).low);
+ }
+#endif
+ return;
+ }
+#if VDA_DEBUG
+ if (vda_file)
+ fprintf (vda_file, " (void)0; // %c: op0 >= 0, type is signed\n", opc);
+#endif
+ set_value_range_to_varying (vr);
+ return;
+ }
+ if (integer_nonnegative_range (&vr1, op1, 'b'))
+ {
+ /* Only op1 has nonnegative range. */
+ if (code == BIT_AND_EXPR)
+ {
+ max = vr1.max;
+ min = build_int_cst (expr_type, 0);
+#if VDA_DEBUG
+ if (vda_file)
+ {
+ fprintf (vda_file, " if ((%s)(a %c b) < 0x%016lx || (%s)(a %c b) > 0x%016lx) err();\n",
+ typebuf, opc, tree_to_double_int (min).low,
+ typebuf, opc, tree_to_double_int (max).low);
+ }
+#endif
+ set_value_range (vr, VR_RANGE, min, max, NULL);
+ return;
+ }
+ if (TYPE_UNSIGNED (expr_type))
+ {
+ min = vr1.min;
+ max = TYPE_MAX_VALUE (expr_type);
+#if VDA_DEBUG
+ if (vda_file)
+ {
+ fprintf (vda_file, " if ((%s)(a %c b) < 0x%016lx || (%s)(a %c b) > 0x%016lx) err();\n",
+ typebuf, opc, tree_to_double_int (min).low,
+ typebuf, opc, tree_to_double_int (max).low);
+ }
+#endif
+ set_value_range (vr, VR_RANGE, min, max, NULL);
+ return;
+ }
+#if VDA_DEBUG
+ if (vda_file)
+ fprintf (vda_file, " (void)0; // %c: op1 >= 0, type is signed\n", opc);
+ set_value_range_to_varying (vr);
+ return;
+#endif
+ }
+#if VDA_DEBUG
+ if (vda_file)
+ fprintf (vda_file, " (void)0; // %c: none is >= 0\n", opc);
+#endif
+ 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 +2407,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 +2686,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 ();