===================================================================
@@ -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;
}
===================================================================
@@ -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" } } */
===================================================================
@@ -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;
+}
===================================================================
@@ -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" } } */