* [RFA] [PATCH] Make VRP understand bitwise OR and AND (better than now)
@ 2008-08-04 12:03 Denys Vlasenko
2008-08-04 12:27 ` Richard Guenther
0 siblings, 1 reply; 13+ messages in thread
From: Denys Vlasenko @ 2008-08-04 12:03 UTC (permalink / raw)
To: gcc-patches
[-- Attachment #1: Type: text/plain, Size: 2411 bytes --]
Hello,
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.
code_diff_example.fold.c is an example program which is compiled
differently with this patch.
The difference is here:
movl (%edx), %eax #,
call bb_simple_perror_msg #
.L40:
- orl $1, 12(%esp) #, errs
+ movl $1, 12(%esp) #, errs
.L19:
addl $4, 24(%esp) #, argv.78
movl 24(%esp), %eax # argv.78,
With improved VRP on (a | b), gcc now can deduce that in this program,
errs |= 1 is always equivalent to errs = 1.
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]
pr28632.c is a testcase to be added to testsuite.
It is artificially made to not compile if VRP fails
to predict a range:
if (a < 0x1000) return;
if (a > 0x1000) return;
if (b < 0x0110) return;
if (!__builtin_constant_p ((a|b) >= 0x01000))
asm("the.bug.is.here");
Before this patch, gcc will fail to see that (a|b) >= 0x01000 is known at
compile time, after it it will see that.
I don't know how to conditionally check for -O (not -O2 or -Os, just -O).
#if defined __OPTIMIZE__ means "-O<anything>", I need to check for
"-O<anything> but not bare -O". Help.
Because of this, currently gcc -O -c pr28632.c fails (-O level is not high
enough to trigger VRP). gcc -c pr28632.c, gcc -O2 -c pr28632.c, gcc -Os -c pr28632.c
work.
Please apply.
--
vda
[-- Attachment #2: bug28632.patch --]
[-- Type: text/x-diff, Size: 8485 bytes --]
diff -d -urpN gcc-4.4.svn.0/gcc/tree-vrp.c gcc-4.4.svn.1/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.1/gcc/tree-vrp.c 2008-08-04 12:30:54.000000000 +0200
@@ -1995,6 +1995,80 @@ 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 tree
+bits_always_set (tree min, tree max)
+{
+ tree xored, shift, result;
+ int xor_hi;
+
+ result = int_const_binop (BIT_AND_EXPR, min, max, 0);
+
+ /* Result may have lower common bits set, need to clear those. */
+ /* Find bit position of highest differing bit. */
+ xored = int_const_binop (BIT_XOR_EXPR, min, max, 0);
+ xor_hi = tree_floor_log2 (xored);
+ /* Is there such bit? */
+ if (xor_hi >= 0)
+ {
+ shift = build_int_cst (NULL_TREE, xor_hi + 1);
+ /* Shift right, then left, clearing this bit and all lower bits too. */
+ result = int_const_binop (RSHIFT_EXPR, result, shift, 0);
+ result = int_const_binop (LSHIFT_EXPR, result, shift, 0);
+ }
+ return result;
+}
+
+/* Combines MIN and MAX as follows:
+ MAX = 01010010101001010010
+ MIN = 01010010100000010010
+ result: 01010010101111111111.
+ Zeros tell us which bits are always 0 for any X in [MIN, MAX].
+ Conversely, ones show which bits can be set. */
+
+static tree
+bits_maybe_set (tree min, tree max)
+{
+ tree xored, shift, result, one, mask;
+ int xor_hi;
+
+ result = int_const_binop (BIT_IOR_EXPR, min, max, 0);
+ /* Find bit position of highest differing bit. */
+ xored = int_const_binop (BIT_XOR_EXPR, min, max, 0);
+ xor_hi = tree_floor_log2 (xored);
+ /* Is there such bit and it's not bit 0? */
+ if (xor_hi > 0)
+ {
+ /* Build a 0000001111 mask. */
+ shift = build_int_cst (NULL_TREE, xor_hi);
+ one = build_int_cst (TREE_TYPE (max), 1);
+ mask = int_const_binop (LSHIFT_EXPR, one, shift, 0);
+ mask = int_const_binop (MINUS_EXPR, mask, one, 0);
+ /* OR it to the result. */
+ result = int_const_binop (BIT_IOR_EXPR, result, mask, 0);
+ }
+ return result;
+}
+
+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))
+ {
+ 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. */
@@ -2007,6 +2081,8 @@ extract_range_from_binary_expr (value_ra
enum value_range_type type;
tree min, max;
int cmp;
+ tree always_set0, always_set1;
+ tree maybe_set0, maybe_set1;
value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
@@ -2025,6 +2101,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 +2125,104 @@ 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)
+ {
+ if (integer_nonnegative_range (&vr0))
+ {
+ if (integer_nonnegative_range (&vr1))
+ {
+ /* In always_setX, ones indicate "always set" bits. */
+ always_set0 = bits_always_set (vr0.min, vr0.max);
+ always_set1 = bits_always_set (vr1.min, vr1.max);
+ /* In maybe_setX, ZEROES indicate "always unset" bits,
+ ones indicate bits which are "maybe set". */
+ maybe_set0 = bits_maybe_set (vr0.min, vr0.max);
+ maybe_set1 = bits_maybe_set (vr1.min, vr1.max);
+ /* If bit is always set in a AND in b,
+ it will be set in (a & b). */
+ min = int_const_binop (BIT_AND_EXPR,
+ always_set0, always_set1, 0);
+ /* 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 = int_const_binop (BIT_AND_EXPR, maybe_set0, maybe_set1, 0);
+ set_value_range (vr, VR_RANGE, min, max, NULL);
+ return;
+ }
+ /* Only op0 has nonnegative range.
+ We positively sure that result of (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 (integer_nonnegative_range (&vr1))
+ {
+ /* Only op1 has nonnegative range. */
+ max = vr1.max;
+ min = build_int_cst (expr_type, 0);
+ set_value_range (vr, VR_RANGE, min, max, NULL);
+ return;
+ }
+ set_value_range_to_varying (vr);
+ return;
+ }
+
+ if (code == BIT_IOR_EXPR)
+ {
+ if (integer_nonnegative_range (&vr0))
+ {
+ if (integer_nonnegative_range (&vr1))
+ {
+ always_set0 = bits_always_set (vr0.min, vr0.max);
+ always_set1 = bits_always_set (vr1.min, vr1.max);
+ maybe_set0 = bits_maybe_set (vr0.min, vr0.max);
+ maybe_set1 = bits_maybe_set (vr1.min, vr1.max);
+ /* If bit is always set in a OR in b,
+ it will be set in (a | b). */
+ min = int_const_binop (BIT_IOR_EXPR,
+ always_set0, always_set1, 0);
+ /* If bit is maybe set in a OR in b,
+ it may be set in (a | b).
+ Example: max(101x | 01xx) = 1111. */
+ max = int_const_binop (BIT_IOR_EXPR, maybe_set0, maybe_set1, 0);
+ set_value_range (vr, VR_RANGE, min, max, NULL);
+ return;
+ }
+ /* Only op0 has nonnegative range. If result is unsigned,
+ we still can derive that (op0|op1) >= op0.min. */
+ if (TYPE_UNSIGNED (expr_type))
+ {
+ min = vr0.min;
+ max = TYPE_MAX_VALUE (expr_type);
+ set_value_range (vr, VR_RANGE, min, max, NULL);
+ set_value_range (vr, VR_RANGE, min, max, NULL);
+ return;
+ }
+ /* TODO: signed type has antirange because (op0|op1) never falls
+ into [0..vr0.min-1]. antirange is [-inf,-1]..[vr0.min,+inf]. */
+ set_value_range_to_varying (vr);
+ return;
+ }
+ if (integer_nonnegative_range (&vr1))
+ {
+ /* Only op1 has nonnegative range. */
+ 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 +2234,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 +2513,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 ();
[-- Attachment #3: bug28632_instrumented.patch --]
[-- Type: text/x-diff, Size: 13580 bytes --]
diff -d -urpN gcc-4.4.svn.0/gcc/tree-vrp.c gcc-4.4.svn.1/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.1/gcc/tree-vrp.c 2008-08-03 02:46:29.000000000 +0200
@@ -1995,6 +1995,143 @@ vrp_int_const_binop (enum tree_code code
return res;
}
+#define VDA_DEBUG 1
+
+#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 tree
+bits_always_set (tree min, tree max)
+{
+ tree xored, shift, result;
+ int xor_hi;
+
+ result = int_const_binop (BIT_AND_EXPR, min, max, 0);
+
+ /* Result may have lower common bits set, need to clear those. */
+ /* Find bit position of highest differing bit. */
+ xored = int_const_binop (BIT_XOR_EXPR, min, max, 0);
+ xor_hi = tree_floor_log2 (xored);
+ /* Is there such bit? */
+ if (xor_hi >= 0)
+ {
+ shift = build_int_cst (NULL_TREE, xor_hi + 1);
+ /* Shift right, then left, clearing this bit and all lower bits too. */
+ result = int_const_binop (RSHIFT_EXPR, result, shift, 0);
+ result = int_const_binop (LSHIFT_EXPR, result, shift, 0);
+ }
+#if VDA_DEBUG
+ if (vda_file)
+ {
+ tree res_type = TREE_TYPE (result);
+ fprintf (vda_file, "// %s(", "bits_always_set");
+ print_generic_expr (vda_file, min, 0);
+ fprintf (vda_file, ",");
+ print_generic_expr (vda_file, max, 0);
+ fprintf (vda_file, ")=[%c%ld]", TYPE_UNSIGNED (res_type) ? 'u' : 's',
+ tree_to_double_int (TYPE_SIZE (res_type)).low);
+ print_generic_expr (vda_file, result, 0);
+ fprintf (vda_file, "\n");
+ }
+#endif
+ return result;
+}
+
+/* Combines MIN and MAX as follows:
+ MAX = 01010010101001010010
+ MIN = 01010010100000010010
+ result: 01010010101111111111.
+ Zeros tell us which bits are always 0 for any X in [MIN, MAX].
+ Conversely, ones show which bits can be set. */
+
+static tree
+bits_maybe_set (tree min, tree max)
+{
+ tree xored, shift, result, one, mask;
+ int xor_hi;
+
+ result = int_const_binop (BIT_IOR_EXPR, min, max, 0);
+ /* Find bit position of highest differing bit. */
+ xored = int_const_binop (BIT_XOR_EXPR, min, max, 0);
+ xor_hi = tree_floor_log2 (xored);
+ /* Is there such bit and it's not bit 0? */
+ if (xor_hi > 0)
+ {
+ /* Build a 0000001111 mask. */
+ shift = build_int_cst (NULL_TREE, xor_hi);
+ one = build_int_cst (TREE_TYPE (max), 1);
+ mask = int_const_binop (LSHIFT_EXPR, one, shift, 0);
+ mask = int_const_binop (MINUS_EXPR, mask, one, 0);
+ /* OR it to the result. */
+ result = int_const_binop (BIT_IOR_EXPR, result, mask, 0);
+ }
+#if VDA_DEBUG
+ if (vda_file)
+ {
+ tree res_type = TREE_TYPE (result);
+ fprintf (vda_file, "// %s(", "bits_maybe_set");
+ print_generic_expr (vda_file, min, 0);
+ fprintf (vda_file, ",");
+ print_generic_expr (vda_file, max, 0);
+ fprintf (vda_file, ")=[%c%ld]", TYPE_UNSIGNED (res_type) ? 'u' : 's',
+ tree_to_double_int (TYPE_SIZE (res_type)).low);
+ print_generic_expr (vda_file, result, 0);
+ fprintf (vda_file, "\n");
+ }
+#endif
+ return result;
+}
+
+#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))
+ {
+#if VDA_DEBUG
+ if (vda_file)
+ {
+ tree val_type = TREE_TYPE (val);
+ fprintf (vda_file, "// %c %s(", vall, "integer_nonnegative_range");
+ print_generic_expr (vda_file, val_type, 0);
+ fprintf (vda_file, "[%c%ld],[",
+ TYPE_UNSIGNED (val_type) ? 'u' : 's',
+ tree_to_double_int (TYPE_SIZE (val_type)).low);
+ print_generic_expr (vda_file, vr->min, 0);
+ fprintf (vda_file, ",");
+ print_generic_expr (vda_file, vr->max, 0);
+ fprintf (vda_file, "])=1\n");
+ }
+#endif
+ 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. */
@@ -2007,9 +2144,21 @@ extract_range_from_binary_expr (value_ra
enum value_range_type type;
tree min, max;
int cmp;
+ tree always_set0, always_set1;
+ tree maybe_set0, maybe_set1;
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
+ 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 +2174,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 +2182,16 @@ extract_range_from_binary_expr (value_ra
return;
}
+#if VDA_DEBUG
+ if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR)
+ if (vda_file)
+ fprintf (vda_file, "// %s(%s)[%c%ld]\n",
+ "extract_range_from_binary_expr",
+ code == BIT_AND_EXPR ? "AND" : "OR",
+ TYPE_UNSIGNED (expr_type) ? 'u' : 's',
+ tree_to_double_int (TYPE_SIZE (expr_type)).low);
+#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 +2208,182 @@ 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)
+ {
+ if (integer_nonnegative_range (&vr0, op0, 'a'))
+ {
+ if (integer_nonnegative_range (&vr1, op1, 'b'))
+ {
+ /* In always_setX, ones indicate "always set" bits. */
+ always_set0 = bits_always_set (vr0.min, vr0.max);
+ always_set1 = bits_always_set (vr1.min, vr1.max);
+ /* In maybe_setX, ZEROES indicate "always unset" bits,
+ ones indicate bits which are "maybe set". */
+ maybe_set0 = bits_maybe_set (vr0.min, vr0.max);
+ maybe_set1 = bits_maybe_set (vr1.min, vr1.max);
+ /* If bit is always set in a AND in b,
+ it will be set in (a & b). */
+ min = int_const_binop (BIT_AND_EXPR,
+ always_set0, always_set1, 0);
+ /* 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 = int_const_binop (BIT_AND_EXPR, maybe_set0, maybe_set1, 0);
+#if VDA_DEBUG
+ if (vda_file)
+ {
+ fprintf (vda_file, " if (a & b) < ");
+ print_generic_expr (vda_file, min, 0);
+ fprintf (vda_file, " || (a & b) > ");
+ print_generic_expr (vda_file, max, 0);
+ fprintf (vda_file, " err();\n");
+ }
+#endif
+ set_value_range (vr, VR_RANGE, min, max, NULL);
+ return;
+ }
+ /* Only op0 has nonnegative range.
+ We positively sure that result of (op0 & op1) can't be
+ larger than vr0.max. */
+ max = vr0.max;
+ min = build_int_cst (expr_type, 0);
+#if VDA_DEBUG
+ if (vda_file)
+ {
+ fprintf (vda_file, " if (a & b) < ");
+ print_generic_expr (vda_file, min, 0);
+ fprintf (vda_file, " || (a & b) > ");
+ print_generic_expr (vda_file, max, 0);
+ fprintf (vda_file, " err();\n");
+ }
+#endif
+ set_value_range (vr, VR_RANGE, min, max, NULL);
+ return;
+ }
+ if (integer_nonnegative_range (&vr1, op1, 'b'))
+ {
+ /* Only op1 has nonnegative range. */
+ max = vr1.max;
+ min = build_int_cst (expr_type, 0);
+#if VDA_DEBUG
+ if (vda_file)
+ {
+ fprintf (vda_file, " if (a & b) < ");
+ print_generic_expr (vda_file, min, 0);
+ fprintf (vda_file, " || (a & b) > ");
+ print_generic_expr (vda_file, max, 0);
+ fprintf (vda_file, " err();\n");
+ }
+#endif
+ set_value_range (vr, VR_RANGE, min, max, NULL);
+ return;
+ }
+#if VDA_DEBUG
+ if (vda_file)
+ fprintf (vda_file, " # AND: none is >= 0\n");
+#endif
+ set_value_range_to_varying (vr);
+ return;
+ }
+
+ if (code == BIT_IOR_EXPR)
+ {
+ if (integer_nonnegative_range (&vr0, op0, 'a'))
+ {
+ if (integer_nonnegative_range (&vr1, op1, 'b'))
+ {
+ always_set0 = bits_always_set (vr0.min, vr0.max);
+ always_set1 = bits_always_set (vr1.min, vr1.max);
+ maybe_set0 = bits_maybe_set (vr0.min, vr0.max);
+ maybe_set1 = bits_maybe_set (vr1.min, vr1.max);
+ /* If bit is always set in a OR in b,
+ it will be set in (a | b). */
+ min = int_const_binop (BIT_IOR_EXPR,
+ always_set0, always_set1, 0);
+ /* If bit is maybe set in a OR in b,
+ it may be set in (a | b).
+ Example: max(101x | 01xx) = 1111. */
+ max = int_const_binop (BIT_IOR_EXPR, maybe_set0, maybe_set1, 0);
+#if VDA_DEBUG
+ if (vda_file)
+ {
+ fprintf (vda_file, " if (a | b) < ");
+ print_generic_expr (vda_file, min, 0);
+ fprintf (vda_file, " || (a | b) > ");
+ print_generic_expr (vda_file, max, 0);
+ fprintf (vda_file, " err();\n");
+ }
+#endif
+ set_value_range (vr, VR_RANGE, min, max, NULL);
+ return;
+ }
+ /* Only op0 has nonnegative range. If result is unsigned,
+ we still can derive that (op0|op1) >= op0.min. */
+ if (TYPE_UNSIGNED (expr_type))
+ {
+ 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 (a | b) < ");
+ print_generic_expr (vda_file, min, 0);
+ fprintf (vda_file, " || (a | b) > ");
+ print_generic_expr (vda_file, max, 0);
+ fprintf (vda_file, " err();\n");
+ }
+#endif
+ set_value_range (vr, VR_RANGE, min, max, NULL);
+ return;
+ }
+ /* TODO: signed type has antirange because (op0|op1) never falls
+ into [0..vr0.min-1]. antirange is [-inf,-1]..[vr0.min,+inf]. */
+#if VDA_DEBUG
+ if (vda_file)
+ fprintf (vda_file, " # OR: op0 >= 0, type is signed\n");
+#endif
+ set_value_range_to_varying (vr);
+ return;
+ }
+ if (integer_nonnegative_range (&vr1, op1, 'b'))
+ {
+ /* Only op1 has nonnegative range. */
+ if (TYPE_UNSIGNED (expr_type))
+ {
+ min = vr1.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 (a | b) < ");
+ print_generic_expr (vda_file, min, 0);
+ fprintf (vda_file, " || (a | b) > ");
+ print_generic_expr (vda_file, max, 0);
+ fprintf (vda_file, " err();\n");
+ }
+#endif
+ return;
+ }
+#if VDA_DEBUG
+ if (vda_file)
+ fprintf (vda_file, " # OR: op1 >= 0, type is signed\n");
+ set_value_range_to_varying (vr);
+ return;
+#endif
+ }
+#if VDA_DEBUG
+ if (vda_file)
+ fprintf (vda_file, " # OR: none is >= 0\n");
+#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 +2395,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 +2674,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 ();
[-- Attachment #4: code_diff_example.fold.c --]
[-- Type: text/x-csrc, Size: 3815 bytes --]
/* vi: set sw=4 ts=4: */
/* fold -- wrap each input line to fit in specified width.
Written by David MacKenzie, djm@gnu.ai.mit.edu.
Copyright (C) 91, 1995-2002 Free Software Foundation, Inc.
Modified for busybox based on coreutils v 5.0
Copyright (C) 2003 Glenn McGrath
Licensed under the GPL v2 or later, see the file LICENSE in this tarball.
*/
#include "libbb.h"
/* Must match getopt32 call */
#define FLAG_COUNT_BYTES 1
#define FLAG_BREAK_SPACES 2
#define FLAG_WIDTH 4
/* Assuming the current column is COLUMN, return the column that
printing C will move the cursor to.
The first column is 0. */
static int adjust_column(int column, char c)
{
if (!(option_mask32 & FLAG_COUNT_BYTES)) {
if (c == '\b') {
if (column > 0)
column--;
} else if (c == '\r')
column = 0;
else if (c == '\t')
column = column + 8 - column % 8;
else /* if (isprint (c)) */
column++;
} else
column++;
return column;
}
int fold_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE;
int fold_main(int argc, char **argv)
{
char *line_out = NULL;
int allocated_out = 0;
char *w_opt;
int width = 80;
int i;
int errs = 0;
if (ENABLE_INCLUDE_SUSv2) {
/* Turn any numeric options into -w options. */
for (i = 1; i < argc; i++) {
char const *a = argv[i];
if (*a++ == '-') {
if (*a == '-' && !a[1]) /* "--" */
break;
if (isdigit(*a))
argv[i] = xasprintf("-w%s", a);
}
}
}
getopt32(argv, "bsw:", &w_opt);
if (option_mask32 & FLAG_WIDTH)
width = xatoul_range(w_opt, 1, 10000);
argv += optind;
if (!*argv)
*--argv = (char*)"-";
do {
FILE *istream = fopen_or_warn_stdin(*argv);
int c;
int column = 0; /* Screen column where next char will go. */
int offset_out = 0; /* Index in 'line_out' for next char. */
if (istream == NULL) {
errs |= EXIT_FAILURE;
continue;
}
while ((c = getc(istream)) != EOF) {
if (offset_out + 1 >= allocated_out) {
allocated_out += 1024;
line_out = xrealloc(line_out, allocated_out);
}
if (c == '\n') {
line_out[offset_out++] = c;
fwrite(line_out, sizeof(char), (size_t) offset_out, stdout);
column = offset_out = 0;
continue;
}
rescan:
column = adjust_column(column, c);
if (column > width) {
/* This character would make the line too long.
Print the line plus a newline, and make this character
start the next line. */
if (option_mask32 & FLAG_BREAK_SPACES) {
/* Look for the last blank. */
int logical_end;
for (logical_end = offset_out - 1; logical_end >= 0; logical_end--) {
if (isblank(line_out[logical_end])) {
break;
}
}
if (logical_end >= 0) {
/* Found a blank. Don't output the part after it. */
logical_end++;
fwrite(line_out, sizeof(char), (size_t) logical_end, stdout);
bb_putchar('\n');
/* Move the remainder to the beginning of the next line.
The areas being copied here might overlap. */
memmove(line_out, line_out + logical_end, offset_out - logical_end);
offset_out -= logical_end;
for (column = i = 0; i < offset_out; i++) {
column = adjust_column(column, line_out[i]);
}
goto rescan;
}
} else {
if (offset_out == 0) {
line_out[offset_out++] = c;
continue;
}
}
line_out[offset_out++] = '\n';
fwrite(line_out, sizeof(char), (size_t) offset_out, stdout);
column = offset_out = 0;
goto rescan;
}
line_out[offset_out++] = c;
}
if (offset_out) {
fwrite(line_out, sizeof(char), (size_t) offset_out, stdout);
}
if (fclose_if_not_stdin(istream)) {
bb_simple_perror_msg(*argv); /* Avoid multibyte problems. */
errs |= EXIT_FAILURE;
}
} while (*++argv);
fflush_stdout_and_exit(errs);
}
[-- Attachment #5: code_diff_example.diff --]
[-- Type: text/x-diff, Size: 731 bytes --]
--- busybox.t70/coreutils/fold.s 2008-08-03 00:27:42.000000000 +0200
+++ busybox.t71/coreutils/fold.s 2008-08-03 00:27:29.000000000 +0200
@@ -42,7 +42,7 @@
# -malign-stringops -mfancy-math-387 -mfp-ret-in-387 -mfused-madd -mieee-fp
# -mno-red-zone -mno-sse4 -mpush-args -msahf -mtls-direct-seg-refs -muclibc
-# Compiler executable checksum: 58263647c1ff7efef9217c4404b9c8f6
+# Compiler executable checksum: 883aa5ca025bc2b2e1e1882e6d43df5d
.section .text.adjust_column,"ax",@progbits
.type adjust_column, @function
@@ -302,7 +302,7 @@
movl (%edx), %eax #,
call bb_simple_perror_msg #
.L40:
- orl $1, 12(%esp) #, errs
+ movl $1, 12(%esp) #, errs
.L19:
addl $4, 24(%esp) #, argv.78
movl 24(%esp), %eax # argv.78,
[-- Attachment #6: pr28632.c --]
[-- Type: text/x-csrc, Size: 1266 bytes --]
void v4 (unsigned a, unsigned b)
{
if (a < 0x1000) return;
if (a > 0x1000) return;
if (b < 0x0110) return;
#if defined __OPTIMIZE__
/* 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");
#endif
}
void u4 (unsigned n)
{
if (n > 0x10111) return;
if (n < 0x10101) return;
#if defined __OPTIMIZE__
/* 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. */
#endif
}
void v5 (int a, int b)
{
if (a < 0x1000) return;
if (a > 0x1000) return;
if (b < 0x0110) return;
#if defined __OPTIMIZE__
/* 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");
#endif
}
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [RFA] [PATCH] Make VRP understand bitwise OR and AND (better than now)
2008-08-04 12:03 [RFA] [PATCH] Make VRP understand bitwise OR and AND (better than now) Denys Vlasenko
@ 2008-08-04 12:27 ` Richard Guenther
2008-08-04 13:28 ` Denys Vlasenko
2008-08-11 12:33 ` Denys Vlasenko
0 siblings, 2 replies; 13+ messages in thread
From: Richard Guenther @ 2008-08-04 12:27 UTC (permalink / raw)
To: Denys Vlasenko; +Cc: gcc-patches
On Mon, Aug 4, 2008 at 2:02 PM, Denys Vlasenko <dvlasenk@redhat.com> wrote:
> Hello,
>
> 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.
>
> code_diff_example.fold.c is an example program which is compiled
> differently with this patch.
>
> The difference is here:
>
> movl (%edx), %eax #,
> call bb_simple_perror_msg #
> .L40:
> - orl $1, 12(%esp) #, errs
> + movl $1, 12(%esp) #, errs
> .L19:
> addl $4, 24(%esp) #, argv.78
> movl 24(%esp), %eax # argv.78,
>
> With improved VRP on (a | b), gcc now can deduce that in this program,
> errs |= 1 is always equivalent to errs = 1.
>
>
> 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]
>
>
> pr28632.c is a testcase to be added to testsuite.
> It is artificially made to not compile if VRP fails
> to predict a range:
>
> if (a < 0x1000) return;
> if (a > 0x1000) return;
> if (b < 0x0110) return;
> if (!__builtin_constant_p ((a|b) >= 0x01000))
> asm("the.bug.is.here");
>
> Before this patch, gcc will fail to see that (a|b) >= 0x01000 is known at
> compile time, after it it will see that.
>
> I don't know how to conditionally check for -O (not -O2 or -Os, just -O).
> #if defined __OPTIMIZE__ means "-O<anything>", I need to check for
> "-O<anything> but not bare -O". Help.
> Because of this, currently gcc -O -c pr28632.c fails (-O level is not high
> enough to trigger VRP). gcc -c pr28632.c, gcc -O2 -c pr28632.c, gcc -Os -c pr28632.c
> work.
>
> Please apply.
You didnt' specify if and how this passed testing.
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.
integer_nonnegative_range needs a comment.
Thanks,
Richard.
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [RFA] [PATCH] Make VRP understand bitwise OR and AND (better than now)
2008-08-04 12:27 ` Richard Guenther
@ 2008-08-04 13:28 ` Denys Vlasenko
2008-08-11 12:33 ` Denys Vlasenko
1 sibling, 0 replies; 13+ messages in thread
From: Denys Vlasenko @ 2008-08-04 13:28 UTC (permalink / raw)
To: Richard Guenther; +Cc: gcc-patches
On Monday 04 August 2008 02:26:57 pm Richard Guenther wrote:
> > pr28632.c is a testcase to be added to testsuite.
> > It is artificially made to not compile if VRP fails
> > to predict a range:
> >
> > if (a < 0x1000) return;
> > if (a > 0x1000) return;
> > if (b < 0x0110) return;
> > if (!__builtin_constant_p ((a|b) >= 0x01000))
> > asm("the.bug.is.here");
> >
> > Before this patch, gcc will fail to see that (a|b) >= 0x01000 is known at
> > compile time, after it it will see that.
> >
> > I don't know how to conditionally check for -O (not -O2 or -Os, just -O).
> > #if defined __OPTIMIZE__ means "-O<anything>", I need to check for
> > "-O<anything> but not bare -O". Help.
> > Because of this, currently gcc -O -c pr28632.c fails (-O level is not high
> > enough to trigger VRP). gcc -c pr28632.c, gcc -O2 -c pr28632.c, gcc -Os -c pr28632.c
> > work.
> >
> > Please apply.
>
> You didnt' specify if and how this passed testing.
It passed full bootstrap. Actually, it was failing bootstrap
until I found a small error in my thinking, which makes me think
that bootstrap is actually triggering this code, it's not
just passing by chance.
The bug hunt also prompted me to add instrumentation,
and by the looks of instrumentation output, gcc infers new
VRs correctly.
> 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.
Yes, I'll fold it.
> 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.
Will take a look.
Thanks.
--
vda
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [RFA] [PATCH] Make VRP understand bitwise OR and AND (better than now)
2008-08-04 12:27 ` Richard Guenther
2008-08-04 13:28 ` Denys Vlasenko
@ 2008-08-11 12:33 ` Denys Vlasenko
2008-08-11 13:30 ` Richard Guenther
1 sibling, 1 reply; 13+ messages in thread
From: Denys Vlasenko @ 2008-08-11 12:33 UTC (permalink / raw)
To: Richard Guenther; +Cc: gcc-patches
[-- Attachment #1: Type: text/plain, Size: 1950 bytes --]
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
[-- Attachment #2: bug28632_v2_instrumented.patch --]
[-- Type: text/x-patch, Size: 13948 bytes --]
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 ();
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [RFA] [PATCH] Make VRP understand bitwise OR and AND (better than now)
2008-08-11 12:33 ` Denys Vlasenko
@ 2008-08-11 13:30 ` Richard Guenther
2008-08-11 22:34 ` Denys Vlasenko
0 siblings, 1 reply; 13+ messages in thread
From: Richard Guenther @ 2008-08-11 13:30 UTC (permalink / raw)
To: Denys Vlasenko; +Cc: gcc-patches
On Mon, Aug 11, 2008 at 2:14 PM, Denys Vlasenko <dvlasenk@redhat.com> wrote:
> 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).
Uh, please remove the instrumentation code - it makes the code hard
to follow.
>> integer_nonnegative_range needs a comment.
>
> Fixed.
>
> Please review attached patch.
This looks much better (with the instrumentation code removed). Please
add a testcase or two, write a proper ChangeLog and specify where
you bootstrapped and tested the patch.
Thanks,
Richard.
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [RFA] [PATCH] Make VRP understand bitwise OR and AND (better than now)
2008-08-11 13:30 ` Richard Guenther
@ 2008-08-11 22:34 ` Denys Vlasenko
2008-08-12 8:21 ` Richard Guenther
0 siblings, 1 reply; 13+ messages in thread
From: Denys Vlasenko @ 2008-08-11 22:34 UTC (permalink / raw)
To: Richard Guenther; +Cc: gcc-patches
[-- Attachment #1: Type: text/plain, Size: 1169 bytes --]
On Mon, 2008-08-11 at 14:40 +0200, Richard Guenther wrote:
> On Mon, Aug 11, 2008 at 2:14 PM, Denys Vlasenko <dvlasenk@redhat.com> wrote:
> >> 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).
>
> Uh, please remove the instrumentation code - it makes the code hard
> to follow.
>
> >> integer_nonnegative_range needs a comment.
> >
> > Fixed.
> >
> > Please review attached patch.
>
> This looks much better (with the instrumentation code removed). Please
> add a testcase or two, write a proper ChangeLog and specify where
> you bootstrapped and tested the patch.
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).
--
vda
[-- Attachment #2: bug28632_v2.patch --]
[-- Type: text/x-patch, Size: 10854 bytes --]
diff -d -urpN gcc-4.4.svn.0/gcc/ChangeLog gcc-4.4.svn.2/gcc/ChangeLog
--- gcc-4.4.svn.0/gcc/ChangeLog 2008-08-01 15:47:26.000000000 +0200
+++ gcc-4.4.svn.2/gcc/ChangeLog 2008-08-11 21:43:31.000000000 +0200
@@ -1,3 +1,9 @@
+2008-08-11 Denys Vlsenko <dvlasenk@redhat.com>
+
+ PR tree-optimization/28632
+ * tree-vrp.c: Improve value range propagation through
+ bitwise AND and OR.
+
2008-08-01 Richard Guenther <rguenther@suse.de>
PR middle-end/36997
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 ();
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [RFA] [PATCH] Make VRP understand bitwise OR and AND (better than now)
2008-08-11 22:34 ` Denys Vlasenko
@ 2008-08-12 8:21 ` Richard Guenther
2008-08-12 8:47 ` Jakub Jelinek
0 siblings, 1 reply; 13+ messages in thread
From: Richard Guenther @ 2008-08-12 8:21 UTC (permalink / raw)
To: Denys Vlasenko; +Cc: gcc-patches
On Mon, Aug 11, 2008 at 10:19 PM, Denys Vlasenko <dvlasenk@redhat.com> wrote:
> On Mon, 2008-08-11 at 14:40 +0200, Richard Guenther wrote:
>> On Mon, Aug 11, 2008 at 2:14 PM, Denys Vlasenko <dvlasenk@redhat.com> wrote:
>> >> 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).
>>
>> Uh, please remove the instrumentation code - it makes the code hard
>> to follow.
>>
>> >> integer_nonnegative_range needs a comment.
>> >
>> > Fixed.
>> >
>> > Please review attached patch.
>>
>> This looks much better (with the instrumentation code removed). Please
>> add a testcase or two, write a proper ChangeLog and specify where
>> you bootstrapped and tested the patch.
>
> 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.
Thanks,
Richard.
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [RFA] [PATCH] Make VRP understand bitwise OR and AND (better than now)
2008-08-12 8:21 ` Richard Guenther
@ 2008-08-12 8:47 ` Jakub Jelinek
2008-08-12 13:50 ` Denys Vlasenko
0 siblings, 1 reply; 13+ messages in thread
From: Jakub Jelinek @ 2008-08-12 8:47 UTC (permalink / raw)
To: Richard Guenther; +Cc: Denys Vlasenko, gcc-patches
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.
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
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [RFA] [PATCH] Make VRP understand bitwise OR and AND (better than now)
2008-08-12 8:47 ` Jakub Jelinek
@ 2008-08-12 13:50 ` Denys Vlasenko
2008-08-13 21:08 ` Jakub Jelinek
0 siblings, 1 reply; 13+ messages in thread
From: Denys Vlasenko @ 2008-08-12 13:50 UTC (permalink / raw)
To: Jakub Jelinek; +Cc: Richard Guenther, gcc-patches
[-- Attachment #1: Type: text/plain, Size: 1610 bytes --]
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
[-- Attachment #2: bug28632_v2.patch --]
[-- Type: text/x-patch, Size: 10397 bytes --]
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 ();
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [RFA] [PATCH] Make VRP understand bitwise OR and AND (better than now)
2008-08-12 13:50 ` Denys Vlasenko
@ 2008-08-13 21:08 ` Jakub Jelinek
2008-08-14 9:52 ` Denys Vlasenko
0 siblings, 1 reply; 13+ messages in thread
From: Jakub Jelinek @ 2008-08-13 21:08 UTC (permalink / raw)
To: Denys Vlasenko; +Cc: Richard Guenther, gcc-patches
On Tue, Aug 12, 2008 at 02:47:28PM +0200, Denys Vlasenko wrote:
> 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.
It doesn't bootstrap on x86_64-linux.
../../gcc/reload1.c: In function `reload':
../../gcc/reload1.c:702: internal compiler error: in set_value_range, at tree-vrp.c:392
Please submit a full bug report,
with preprocessed source if appropriate.
See <http://gcc.gnu.org/bugs.html> for instructions.
make[3]: *** [reload1.o] Error 1
This needs to be fixed before this is committed.
> 2008-08-12 Denys Vlasenko <dvlasenk@redhat.com>
>
> PR tree-optimization/28632
> * gcc.dg/pr28632.c: New test.
Newly added testcases should be always tested both with the patch that they
pass and without the rest of patch that they fail. You can use
make check-gcc RUNTESTFLAGS=dg.exp=pr28632.c
syntax to test just one testcase. The problem with the testcase is that
it is a dg-do compile test and in case of failure it just adds some invalid
assembly to it. But compile tests just compile into assembly, so no errors
are reported. You either need to add
/* { dg-final { scan-assembler-not "the.bug.is.here" } } */
to the end of testcase, or add some main and make it dg-do link.
IMHO the former is better here.
Jakub
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [RFA] [PATCH] Make VRP understand bitwise OR and AND (better than now)
2008-08-14 9:52 ` Denys Vlasenko
@ 2008-08-14 9:52 ` Jakub Jelinek
2008-08-14 11:46 ` Denys Vlasenko
0 siblings, 1 reply; 13+ messages in thread
From: Jakub Jelinek @ 2008-08-14 9:52 UTC (permalink / raw)
To: Denys Vlasenko; +Cc: Richard Guenther, gcc-patches
On Thu, Aug 14, 2008 at 11:24:35AM +0200, Denys Vlasenko wrote:
> Mine is also x86-64. Might be triggered by different configute and
> CFLAGS. Can you post options you used?
Just
../configure --enable-languages=c,c++,fortran,java,objc,obj-c++
make -j6
Jakub
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [RFA] [PATCH] Make VRP understand bitwise OR and AND (better than now)
2008-08-13 21:08 ` Jakub Jelinek
@ 2008-08-14 9:52 ` Denys Vlasenko
2008-08-14 9:52 ` Jakub Jelinek
0 siblings, 1 reply; 13+ messages in thread
From: Denys Vlasenko @ 2008-08-14 9:52 UTC (permalink / raw)
To: Jakub Jelinek; +Cc: Richard Guenther, gcc-patches
On Wed, 2008-08-13 at 16:15 -0400, Jakub Jelinek wrote:
> On Tue, Aug 12, 2008 at 02:47:28PM +0200, Denys Vlasenko wrote:
> > 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.
>
> It doesn't bootstrap on x86_64-linux.
Mine is also x86-64. Might be triggered by different configute and
CFLAGS. Can you post options you used?
Meanwhile I am retesting bootstrap with different options.
> ../../gcc/reload1.c: In function `reload':
> ../../gcc/reload1.c:702: internal compiler error: in set_value_range, at tree-vrp.c:392
> Please submit a full bug report,
> with preprocessed source if appropriate.
> See <http://gcc.gnu.org/bugs.html> for instructions.
> make[3]: *** [reload1.o] Error 1
I was seeing these things until I added the code which avoids doing this
optimization when msb bit is set.
> This needs to be fixed before this is committed.
No question about that.
--
vda
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [RFA] [PATCH] Make VRP understand bitwise OR and AND (better than now)
2008-08-14 9:52 ` Jakub Jelinek
@ 2008-08-14 11:46 ` Denys Vlasenko
0 siblings, 0 replies; 13+ messages in thread
From: Denys Vlasenko @ 2008-08-14 11:46 UTC (permalink / raw)
To: Jakub Jelinek; +Cc: Richard Guenther, gcc-patches
On Thu, 2008-08-14 at 05:32 -0400, Jakub Jelinek wrote:
> On Thu, Aug 14, 2008 at 11:24:35AM +0200, Denys Vlasenko wrote:
> > Mine is also x86-64. Might be triggered by different configute and
> > CFLAGS. Can you post options you used?
>
> Just
> ../configure --enable-languages=c,c++,fortran,java,objc,obj-c++
> make -j6
Thanks, trying to reproduce.
--
vda
^ permalink raw reply [flat|nested] 13+ messages in thread
end of thread, other threads:[~2008-08-14 9:52 UTC | newest]
Thread overview: 13+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2008-08-04 12:03 [RFA] [PATCH] Make VRP understand bitwise OR and AND (better than now) Denys Vlasenko
2008-08-04 12:27 ` Richard Guenther
2008-08-04 13:28 ` Denys Vlasenko
2008-08-11 12:33 ` Denys Vlasenko
2008-08-11 13:30 ` Richard Guenther
2008-08-11 22:34 ` Denys Vlasenko
2008-08-12 8:21 ` Richard Guenther
2008-08-12 8:47 ` Jakub Jelinek
2008-08-12 13:50 ` Denys Vlasenko
2008-08-13 21:08 ` Jakub Jelinek
2008-08-14 9:52 ` Denys Vlasenko
2008-08-14 9:52 ` Jakub Jelinek
2008-08-14 11:46 ` Denys Vlasenko
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).