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 ();