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

login
register
mail settings
Submitter Tom de Vries
Date Sept. 14, 2012, 7:27 a.m.
Message ID <5052DC5F.4060204@mentor.com>
Download mbox | patch
Permalink /patch/183817/
State New
Headers show

Comments

Tom de Vries - Sept. 14, 2012, 7:27 a.m.
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.
Jakub Jelinek - Sept. 14, 2012, 7:38 a.m.
On Fri, Sep 14, 2012 at 09:27:27AM +0200, Tom de Vries wrote:
> 	* gcc.dg/tree-ssa/vrp81.c: New test.
> 	* gcc.dg/tree-ssa/vrp81-2.c: Same.
> 	* gcc.dg/tree-ssa/vrp82.c: Same.

Why not vrp82.c, vrp83.c and vrp84.c (and rename the recently added
vrp80-2.c test to vrp81.c)?

	Jakub
Tom de Vries - Sept. 14, 2012, 7:51 a.m.
On 14/09/12 09:38, Jakub Jelinek wrote:
> On Fri, Sep 14, 2012 at 09:27:27AM +0200, Tom de Vries wrote:
>> 	* gcc.dg/tree-ssa/vrp81.c: New test.
>> 	* gcc.dg/tree-ssa/vrp81-2.c: Same.
>> 	* gcc.dg/tree-ssa/vrp82.c: Same.
> 
> Why not vrp82.c, vrp83.c and vrp84.c (and rename the recently added
> vrp80-2.c test to vrp81.c)?
> 

My thinking behind this was the following: vrp80.c and vrp80-2.c are 2 versions
of more or less the same code. In one version, we test whether the inclusive
bounds of the range are folded. In the other version we test whether the
exclusive bounds of the range are not folded.

Given that rationale, should I leave the names like this or rename them?

Thanks,
- Tom

> 	Jakub
>
Jakub Jelinek - Sept. 14, 2012, 7:59 a.m.
On Fri, Sep 14, 2012 at 09:51:48AM +0200, Tom de Vries wrote:
> On 14/09/12 09:38, Jakub Jelinek wrote:
> > On Fri, Sep 14, 2012 at 09:27:27AM +0200, Tom de Vries wrote:
> >> 	* gcc.dg/tree-ssa/vrp81.c: New test.
> >> 	* gcc.dg/tree-ssa/vrp81-2.c: Same.
> >> 	* gcc.dg/tree-ssa/vrp82.c: Same.
> > 
> > Why not vrp82.c, vrp83.c and vrp84.c (and rename the recently added
> > vrp80-2.c test to vrp81.c)?
> > 
> 
> My thinking behind this was the following: vrp80.c and vrp80-2.c are 2 versions
> of more or less the same code. In one version, we test whether the inclusive
> bounds of the range are folded. In the other version we test whether the
> exclusive bounds of the range are not folded.

IMHO it is enough to give them consecutive numbers, there are many cases
where multiple vrpNN.c tests have been added for more or less the same code,
but I don't care that much, will leave that decision to Richard as the
probable reviewer.

	Jakub
Richard Guenther - Sept. 14, 2012, 10:04 a.m.
On Fri, Sep 14, 2012 at 9:59 AM, Jakub Jelinek <jakub@redhat.com> wrote:
> On Fri, Sep 14, 2012 at 09:51:48AM +0200, Tom de Vries wrote:
>> On 14/09/12 09:38, Jakub Jelinek wrote:
>> > On Fri, Sep 14, 2012 at 09:27:27AM +0200, Tom de Vries wrote:
>> >>    * gcc.dg/tree-ssa/vrp81.c: New test.
>> >>    * gcc.dg/tree-ssa/vrp81-2.c: Same.
>> >>    * gcc.dg/tree-ssa/vrp82.c: Same.
>> >
>> > Why not vrp82.c, vrp83.c and vrp84.c (and rename the recently added
>> > vrp80-2.c test to vrp81.c)?
>> >
>>
>> My thinking behind this was the following: vrp80.c and vrp80-2.c are 2 versions
>> of more or less the same code. In one version, we test whether the inclusive
>> bounds of the range are folded. In the other version we test whether the
>> exclusive bounds of the range are not folded.
>
> IMHO it is enough to give them consecutive numbers, there are many cases
> where multiple vrpNN.c tests have been added for more or less the same code,
> but I don't care that much, will leave that decision to Richard as the
> probable reviewer.

I agree with Jakub - the patch is ok with adjusting the testcase names.

Thanks,
Richard.

>         Jakub

Patch

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