This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] add VRP for bitwise OR and AND: v3
- From: Denis Vlasenko <vda dot linux at googlemail dot com>
- To: Daniel Berlin <dannyb at google dot com>, Håkan Hjort <hakan at jasper-da dot com>, "Richard Guenther" <richard dot guenther at gmail dot com>, gcc-patches at gcc dot gnu dot org
- Date: Sat, 12 Aug 2006 15:29:04 +0200
- Subject: [PATCH] add VRP for bitwise OR and AND: v3
* tree-vrp.c (extract_range_from_binary_expr):
add value range propagation for bitwise AND/OR
Patch is against gcc-4.2-20060805.
Since unmodified gcc-4.2-20060805 snapshot does not bootstrap
for me, I only verified that "make all-gcc" build
of gcc-4.2-20060805 on i386-pc-linux-gnu
with this patch succeeds.
However, I successfully bootstrapped gcc-4.1.1 with this patch.
--
vda
diff -urpN gcc-4.2-20060805.org/gcc/tree-vrp.c gcc-4.2-20060805/gcc/tree-vrp.c
--- gcc-4.2-20060805.org/gcc/tree-vrp.c 2006-08-01 02:47:49.000000000 +0200
+++ gcc-4.2-20060805/gcc/tree-vrp.c 2006-08-12 15:16:18.000000000 +0200
@@ -1321,6 +1321,64 @@ vrp_int_const_binop (enum tree_code code
return res;
}
+/* Combines MIN and MAX as follows:
+ MIN = 01010010101001010010
+ MAX = 01010010100000010010
+ result: 01010010100000000000. */
+
+static tree
+find_common_set_bits (tree min, tree max)
+{
+ tree xored, shift, result;
+ int xor_hi;
+
+ result = vrp_int_const_binop (BIT_AND_EXPR, min, max);
+ xored = vrp_int_const_binop (BIT_XOR_EXPR, min, max);
+ xor_hi = tree_floor_log2 (xored);
+ /* if min!=max */
+ if (xor_hi >= 0)
+ {
+ shift = build_int_cst (NULL_TREE, xor_hi+1);
+ result = vrp_int_const_binop (RSHIFT_EXPR, result, shift);
+ result = vrp_int_const_binop (LSHIFT_EXPR, result, shift);
+ }
+ return result;
+}
+
+/* Combines MIN and MAX as follows:
+ MAX = 01010010101001010010
+ MIN = 01010010100000010010
+ result: 01010010101111111111. */
+
+static tree
+find_common_unset_bits (tree min, tree max)
+{
+ tree xored, shift, result, one, mask;
+ int xor_hi;
+
+ result = vrp_int_const_binop (BIT_IOR_EXPR, min, max);
+ xored = vrp_int_const_binop (BIT_XOR_EXPR, min, max);
+ xor_hi = tree_floor_log2 (xored);
+ /* if min!=max and difference is not in lowest bit only */
+ if (xor_hi > 0)
+ {
+ shift = build_int_cst (NULL_TREE, xor_hi);
+ one = build_int_cst (TREE_TYPE (max), 1);
+ mask = vrp_int_const_binop (LSHIFT_EXPR, one, shift);
+ mask = vrp_int_const_binop (MINUS_EXPR, mask, one);
+ result = vrp_int_const_binop (BIT_IOR_EXPR, result, mask);
+ }
+ return result;
+}
+
+static int
+integer_nonnegative_range (value_range_t *vr)
+{
+ return (vr->type == VR_RANGE
+ && TREE_CODE (vr->min) == INTEGER_CST
+ && tree_expr_nonnegative_p (vr->min)
+ && TREE_CODE (vr->max) == INTEGER_CST);
+}
/* Extract range information from a binary expression EXPR based on
the ranges of each of its operands and the expression code. */
@@ -1332,6 +1390,8 @@ extract_range_from_binary_expr (value_ra
enum value_range_type type;
tree op0, op1, min, max;
int cmp;
+ tree common_set0, common_set1;
+ tree common_unset0, common_unset1;
value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
@@ -1348,6 +1408,7 @@ extract_range_from_binary_expr (value_ra
&& code != MIN_EXPR
&& code != MAX_EXPR
&& code != BIT_AND_EXPR
+ && code != BIT_IOR_EXPR
&& code != TRUTH_ANDIF_EXPR
&& code != TRUTH_ORIF_EXPR
&& code != TRUTH_AND_EXPR
@@ -1375,6 +1436,89 @@ 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))
+ {
+ common_set0 = find_common_set_bits (vr0.max, vr0.min);
+ common_set1 = find_common_set_bits (vr1.max, vr1.min);
+ common_unset0 = find_common_unset_bits (vr0.max, vr0.min);
+ common_unset1 = find_common_unset_bits (vr1.max, vr1.min);
+ min = vrp_int_const_binop (BIT_AND_EXPR,
+ common_set0, common_set1);
+ /* For example, max(010x & 10xx) = 0001 */
+ max = vrp_int_const_binop (BIT_AND_EXPR,
+ common_unset0, common_unset1);
+ set_value_range (vr, VR_RANGE, min, max, NULL);
+ return;
+ }
+ else
+ {
+ min = build_int_cst (TREE_TYPE (op0), 0);
+ /* We positively sure that result of (op0 & op1) can't be
+ larger than vr0.max. */
+ max = vr0.max;
+ set_value_range (vr, VR_RANGE, min, max, NULL);
+ return;
+ }
+ }
+ if (integer_nonnegative_range (&vr1))
+ {
+ min = build_int_cst (TREE_TYPE (op1), 0);
+ max = vr1.max;
+ 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))
+ {
+ common_set0 = find_common_set_bits (vr0.max, vr0.min);
+ common_set1 = find_common_set_bits (vr1.max, vr1.min);
+ common_unset0 = find_common_unset_bits (vr0.max, vr0.min);
+ common_unset1 = find_common_unset_bits (vr1.max, vr1.min);
+ /* For example, min(101x | 01xx) = 1110 */
+ min = vrp_int_const_binop (BIT_IOR_EXPR,
+ common_set0, common_set1);
+ max = vrp_int_const_binop (BIT_IOR_EXPR,
+ common_unset0, common_unset1);
+ set_value_range (vr, VR_RANGE, min, max, NULL);
+ return;
+ }
+ if (TYPE_UNSIGNED (TREE_TYPE (op1)))
+ {
+ min = vr0.min;
+ max = TYPE_MAX_VALUE (TREE_TYPE (op1));
+ 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 [MIN,-1]..[vr0.min,+MAX]. */
+ set_value_range_to_varying (vr);
+ return;
+ }
+ if (integer_nonnegative_range (&vr1)
+ && TYPE_UNSIGNED (TREE_TYPE (op0)))
+ {
+ min = vr1.min;
+ max = TYPE_MAX_VALUE (TREE_TYPE (op0));
+ set_value_range (vr, VR_RANGE, min, max, NULL);
+ return;
+ }
+ /* TODO: signed type has antirange. */
+ 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)
{
@@ -1386,16 +1530,12 @@ 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. TODO, we may be able to derive anti-ranges
+ in some cases. */
+ if (code != TRUTH_AND_EXPR
&& code != TRUTH_OR_EXPR
- && (vr0.type == VR_VARYING
- || vr1.type == VR_VARYING
- || vr0.type != vr1.type
+ && (vr0.type != vr1.type
+ || vr0.type == VR_VARYING
|| symbolic_range_p (&vr0)
|| symbolic_range_p (&vr1)))
{
@@ -1615,31 +1755,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_expr_nonnegative_p (vr0.max)
- && TREE_CODE (vr0.max) == INTEGER_CST)
- {
- min = build_int_cst (TREE_TYPE (expr), 0);
- max = vr0.max;
- }
- else if (vr1.type == VR_RANGE
- && vr1.min == vr1.max
- && tree_expr_nonnegative_p (vr1.max)
- && TREE_CODE (vr1.max) == INTEGER_CST)
- {
- type = VR_RANGE;
- min = build_int_cst (TREE_TYPE (expr), 0);
- max = vr1.max;
- }
- else
- {
- set_value_range_to_varying (vr);
- return;
- }
- }
else
gcc_unreachable ();