Richard, I've tried to handle more LSHIFT_EXPR cases with a shift range in tree-vrp.
Currently we handle cases like this: - non-negative shifting out zeros [5, 6] << [1, 2] == [10, 24] This patch adds these cases: - unsigned shifting out ones [0xffffff00, 0xffffffff] << [1, 2] == [0xfffffc00, 0xfffffffe] - negative numbers [-1, 1] << [1, 2] == [-4, 4] My previous patch (for PR53986) contained a bug (test-case vrp82.c) which makes vrp evaluate: - [minint, 1] << [1, 2] == [0, 4] It should conservatively have checked for vr0.min >= 0, for the signed negative case. This patch fixes that bug as well. Bootstrapped and regtested (ada inclusive) on x86_64. OK for trunk? Thanks, - Tom 2012-09-10 Tom de Vries <t...@codesourcery.com> * tree-vrp.c (extract_range_from_binary_expr_1): Fix bug in handling of LSHIFT_EXPR with shift range. Handle more LSHIFT_EXPR cases with shift range. * gcc.dg/tree-ssa/vrp81.c: New test. * gcc.dg/tree-ssa/vrp81-2.c: Same. * gcc.dg/tree-ssa/vrp82.c: Same.
Index: gcc/tree-vrp.c =================================================================== --- gcc/tree-vrp.c (revision 191089) +++ gcc/tree-vrp.c (working copy) @@ -2766,20 +2766,63 @@ else if (code == LSHIFT_EXPR && range_int_cst_p (&vr0)) { - int overflow_pos = TYPE_PRECISION (expr_type); + int prec = TYPE_PRECISION (expr_type); + int overflow_pos = prec; int bound_shift; - double_int bound; + double_int bound, complement, low_bound, high_bound; + bool uns = TYPE_UNSIGNED (expr_type); + bool in_bounds = false; - if (!TYPE_UNSIGNED (expr_type)) + if (!uns) overflow_pos -= 1; bound_shift = overflow_pos - TREE_INT_CST_LOW (vr1.max); - bound = double_int_one.llshift (bound_shift, - TYPE_PRECISION (expr_type)); - if (tree_to_double_int (vr0.max).ult (bound)) + /* If bound_shift == HOST_BITS_PER_DOUBLE_INT, the llshift can + overflow. However, for that to happen, vr1.max needs to be + zero, which means vr1 is a singleton range of zero, which + means it should be handled by the previous LSHIFT_EXPR + if-clause. */ + bound = double_int_one.llshift (bound_shift, prec); + complement = ~(bound - double_int_one); + + if (uns) { - /* In the absense of overflow, (a << b) is equivalent - to (a * 2^b). */ + low_bound = bound; + high_bound = complement.zext (prec); + if (tree_to_double_int (vr0.max).ult (low_bound)) + { + /* [5, 6] << [1, 2] == [10, 24]. */ + /* We're shifting out only zeroes, the value increases + monotomically. */ + in_bounds = true; + } + else if (high_bound.ult (tree_to_double_int (vr0.min))) + { + /* [0xffffff00, 0xffffffff] << [1, 2] + == [0xfffffc00, 0xfffffffe]. */ + /* We're shifting out only ones, the value decreases + monotomically. */ + in_bounds = true; + } + } + else + { + /* [-1, 1] << [1, 2] == [-4, 4]. */ + low_bound = complement.sext (prec); + high_bound = bound; + if (tree_to_double_int (vr0.max).slt (high_bound) + && low_bound.slt (tree_to_double_int (vr0.min))) + { + /* For non-negative numbers, we're shifting out only + zeroes, the value increases monotomically. + For negative numbers, we're shifting out only ones, the + value decreases monotomically. */ + in_bounds = true; + } + } + + if (in_bounds) + { extract_range_from_multiplicative_op_1 (vr, code, &vr0, &vr1); return; } Index: gcc/testsuite/gcc.dg/tree-ssa/vrp81-2.c =================================================================== --- gcc/testsuite/gcc.dg/tree-ssa/vrp81-2.c (revision 0) +++ gcc/testsuite/gcc.dg/tree-ssa/vrp81-2.c (revision 0) @@ -0,0 +1,60 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-vrp1" } */ + +extern void vrp_keep (void); + +void +f2 (int c, int b) +{ + int s = 0; + if (c == 0) + s += 1; + else if (c < 1) + s -= 1; + /* s in [-1, 1]. */ + b = (b & 1) + 1; + /* b in range [1, 2]. */ + b = s << b; + /* b in range [-4, 4]. */ + if (b == -4) + vrp_keep (); + if (b == 4) + vrp_keep (); +} + +void +f3 (int s, int b) +{ + if (s >> 3 == -2) + { + /* s in range [-16, -9]. */ + b = (b & 1) + 1; + /* b in range [1, 2]. */ + b = s << b; + /* b in range [bmin << smax, bmax << smin], + == [-16 << 2, -9 << 1] + == [-64, -18]. */ + if (b == -64) + vrp_keep (); + if (b == -18) + vrp_keep (); + } +} + +void +f4 (unsigned int s, unsigned int b) +{ + s |= ~(0xffU); + /* s in [0xffffff00, 0xffffffff]. */ + b = (b & 1) + 1; + /* b in [1, 2]. */ + b = s << b; + /* s in [0xfffffc00, 0xfffffffe]. */ + if (b == ~0x3ffU) + vrp_keep (); + if (b == ~0x1U) + vrp_keep (); +} + +/* { dg-final { scan-tree-dump-times "vrp_keep \\(" 6 "vrp1"} } */ +/* { dg-final { cleanup-tree-dump "vrp1" } } */ Index: gcc/testsuite/gcc.dg/tree-ssa/vrp81.c =================================================================== --- gcc/testsuite/gcc.dg/tree-ssa/vrp81.c (revision 0) +++ gcc/testsuite/gcc.dg/tree-ssa/vrp81.c (revision 0) @@ -0,0 +1,57 @@ +/* { dg-do link } */ +/* { dg-options "-O2" } */ + +extern void link_error (void); + +void +f2 (int c, int b) +{ + int s = 0; + if (c == 0) + s += 1; + else if (c < 1) + s -= 1; + /* s in [-1, 1]. */ + b = (b & 1) + 1; + /* b in range [1, 2]. */ + b = s << b; + /* b in range [-4, 4]. */ + if (b == -5 || b == 5) + link_error (); +} + +void +f3 (int s, int b) +{ + if (s >> 3 == -2) + { + /* s in range [-16, -9]. */ + b = (b & 1) + 1; + /* b in range [1, 2]. */ + b = s << b; + /* b in range [bmin << smax, bmax << smin], + == [-16 << 2, -9 << 1] + == [-64, -18]. */ + if (b == -65 || b == -17) + link_error (); + } +} + +void +f4 (unsigned int s, unsigned int b) +{ + s |= ~0xffU; + /* s in [0xffffff00, 0xffffffff]. */ + b = (b & 1) + 1; + /* b in [1, 2]. */ + b = s << b; + /* s in [0xfffffc00, 0xfffffffe]. */ + if (b == ~0x3ffU - 1 || b == ~0x1U + 1) + link_error (); +} + +int +main () +{ + return 0; +} Index: gcc/testsuite/gcc.dg/tree-ssa/vrp82.c =================================================================== --- gcc/testsuite/gcc.dg/tree-ssa/vrp82.c (revision 0) +++ gcc/testsuite/gcc.dg/tree-ssa/vrp82.c (revision 0) @@ -0,0 +1,21 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-vrp1" } */ + +extern void vrp_keep (void); + +void +f2 (int s, int b) +{ + if (s > 1) + s = 1; + /* s in [minint, 1]. */ + b = (b & 1) + 1; + /* b in range [1, 2]. */ + b = s << b; + /* b in range [minint+4, maxint-3]. */ + if (b == -2) + vrp_keep (); +} + +/* { dg-final { scan-tree-dump-times "vrp_keep \\(" 1 "vrp1"} } */ +/* { dg-final { cleanup-tree-dump "vrp1" } } */