Patchwork fix for PR53986 - missing vrp on bit-mask test, LSHIFT_EXPR not handled

login
register
mail settings
Submitter Tom de Vries
Date Aug. 26, 2012, 2:28 p.m.
Message ID <503A3285.6060202@mentor.com>
Download mbox | patch
Permalink /patch/180057/
State New
Headers show

Comments

Tom de Vries - Aug. 26, 2012, 2:28 p.m.
Richard,

this patch fixes PR53986.

The patch calculates the range of an LSHIFT_EXPR in case both operands are
constants ranges, and the operation is guaranteed not to overflow.

F.i., it evaluates [1, 2] << [1, 8] to [2, 512].

Bootstrapped and reg-tested (ada inclusive) on x86_64.

Ok for trunk?

Thanks,
- Tom

2012-08-25  Tom de Vries  <tom@codesourcery.com>

	PR tree-optimization/53986
	* tree-vrp.c (extract_range_from_multiplicative_op_1): Allow
	LSHIFT_EXPR.
	(extract_range_from_binary_expr_1): Handle LSHIFT with constant range as
	shift amount.

	* gcc.dg/tree-ssa/vrp80.c: New test.
	* gcc.dg/tree-ssa/vrp80-2.c: Same.
Richard Guenther - Sept. 3, 2012, 11:25 a.m.
On Sun, Aug 26, 2012 at 4:28 PM, Tom de Vries <Tom_deVries@mentor.com> wrote:
> Richard,
>
> this patch fixes PR53986.
>
> The patch calculates the range of an LSHIFT_EXPR in case both operands are
> constants ranges, and the operation is guaranteed not to overflow.
>
> F.i., it evaluates [1, 2] << [1, 8] to [2, 512].
>
> Bootstrapped and reg-tested (ada inclusive) on x86_64.
>
> Ok for trunk?

Ok.

Thanks,
Richard.

> Thanks,
> - Tom
>
> 2012-08-25  Tom de Vries  <tom@codesourcery.com>
>
>         PR tree-optimization/53986
>         * tree-vrp.c (extract_range_from_multiplicative_op_1): Allow
>         LSHIFT_EXPR.
>         (extract_range_from_binary_expr_1): Handle LSHIFT with constant range as
>         shift amount.
>
>         * gcc.dg/tree-ssa/vrp80.c: New test.
>         * gcc.dg/tree-ssa/vrp80-2.c: Same.

Patch

Index: gcc/tree-vrp.c
===================================================================
--- gcc/tree-vrp.c (revision 190553)
+++ gcc/tree-vrp.c (working copy)
@@ -2068,7 +2068,8 @@  extract_range_from_multiplicative_op_1 (
 	      || code == CEIL_DIV_EXPR
 	      || code == EXACT_DIV_EXPR
 	      || code == ROUND_DIV_EXPR
-	      || code == RSHIFT_EXPR);
+	      || code == RSHIFT_EXPR
+	      || code == LSHIFT_EXPR);
   gcc_assert ((vr0->type == VR_RANGE
 	       || (code == MULT_EXPR && vr0->type == VR_ANTI_RANGE))
 	      && vr0->type == vr1->type);
@@ -2767,6 +2768,27 @@  extract_range_from_binary_expr_1 (value_
 	      flag_wrapv = saved_flag_wrapv;
 	      return;
 	    }
+	  else if (code == LSHIFT_EXPR
+		   && range_int_cst_p (&vr0))
+	    {
+	      int overflow_pos = TYPE_PRECISION (expr_type);
+	      int bound_shift;
+	      double_int bound;
+
+	      if (!TYPE_UNSIGNED (expr_type))
+		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))
+		{
+		  /* In the absense of overflow, (a << b) is equivalent
+		     to (a * 2^b).  */
+		  extract_range_from_multiplicative_op_1 (vr, code, &vr0, &vr1);
+		  return;
+		}
+	    }
 	}
       set_value_range_to_varying (vr);
       return;
Index: gcc/testsuite/gcc.dg/tree-ssa/vrp80.c
===================================================================
--- /dev/null (new file)
+++ gcc/testsuite/gcc.dg/tree-ssa/vrp80.c (revision 0)
@@ -0,0 +1,33 @@ 
+/* { dg-do link } */
+/* { dg-options "-O2 -fno-tree-switch-conversion" } */
+
+extern void link_error (void);
+
+/* Test <<.  */
+
+void
+f3 (int s, int b)
+{
+  if (s >> 3 == -2)
+    /* s in range [-16, -9].  */
+    {
+      s += 17;
+      /* s in range [1, 8].  */
+      b = (b & 1) + 1;
+      /* b in range [1, 2].  */
+      b =  b << s;
+      /* b in range [bmin << smin, bmax << smax],
+                    == [1 << 1, 2 << 8]
+                    == [2, 512].  */
+      if (b == 1 || b == 513)
+	link_error ();
+    }
+}
+
+int
+main ()
+{
+  return 0;
+}
+
+
Index: gcc/testsuite/gcc.dg/tree-ssa/vrp80-2.c
===================================================================
--- /dev/null (new file)
+++ gcc/testsuite/gcc.dg/tree-ssa/vrp80-2.c (revision 0)
@@ -0,0 +1,38 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fno-tree-switch-conversion -fdump-tree-vrp1" } */
+
+extern void vrp_keep (void);
+
+/* Test <<.  */
+
+void
+f3 (int s, int b)
+{
+  if (s >> 3 == -2)
+    /* s in range [-16, -9].  */
+    {
+      s += 17;
+      /* s in range [1, 8].  */
+      b = (b & 1) + 1;
+      /* b in range [1, 2].  */
+      b =  b << s;
+      /* b in range [bmin << smin, bmax << smax],
+                    == [1 << 1, 2 << 8]
+                    == [2, 512].  */
+      if (b == 2)
+	vrp_keep ();
+      if (b == 512)
+	vrp_keep ();
+    }
+}
+
+int
+main ()
+{
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump-times "vrp_keep \\(" 2 "vrp1"} } */
+/* { dg-final { cleanup-tree-dump "vrp1" } } */
+
+