[PATCH] Bug fix in LSHIFT_EXPR case with a shift range in tree-vrp, handle more cases

[Tom de Vries <Tom_deVries at mentor dot com>]

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  <tom@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" } } */