From patchwork Thu Jul  8 17:07:56 2010
Content-Type: text/plain; charset="utf-8"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Subject: Improve VRP of BIT_AND_EXPR
Date: Thu, 08 Jul 2010 07:07:56 -0000
From: Jakub Jelinek <jakub@redhat.com>
X-Patchwork-Id: 58261
Message-Id: <20100708170756.GM20208@tyan-ft48-01.lab.bos.redhat.com>
To: gcc-patches@gcc.gnu.org

Hi!

Looking at PR44858, I was surprised VRP doesn't figure out
for
x = (a > b);
y = x & 2;
that y is 0.  Similarly say for x & y when
x is [1024, 1039] and y is [2048, 2063], we can count
on the result being [0, 15] (the 0x400 and 0x800 bits are both cleared),
etc.

The following patch improves handling of BIT_AND_EXPR.

Bootstrapped/regtested on x86_64-linux and i686-linux.  Ok for trunk?

In the testsuite slp-perm-4.c was the only failure, because in
for (i = 0; i < 16; i++)
  {
    i %= 256;
    if (i > 200)
      abort ();
    ...
  }
with the patch the conditional and abort is now optimized away - previously
i &= 255; was VARYING, now is [0, 15].

As next step, I guess VRP should be able to optimize that &= 255 away
completely, because the argument is known to be [0, 15], so doesn't need
any masking.

2010-07-08  Jakub Jelinek  <jakub@redhat.com>

	* tree-vrp.c (extract_range_from_binary_expr) <BIT_AND_EXPR>: If
	both ranges are range_int_cst_p with non-negative minimum,
	try harder to derive smaller range.

	* gcc.dg/tree-ssa/vrp50.c: New test.
	* gcc.dg/vect/slp-perm-4.c (main): Make sure loop isn't vectorized.



	Jakub


--- gcc/tree-vrp.c.jj	2010-07-05 12:37:01.000000000 +0200
+++ gcc/tree-vrp.c	2010-07-08 16:03:11.000000000 +0200
@@ -2577,6 +2577,58 @@ extract_range_from_binary_expr (value_ra
 
       if (vr0_int_cst_singleton_p && vr1_int_cst_singleton_p)
 	min = max = int_const_binop (code, vr0.max, vr1.max, 0);
+      else if (range_int_cst_p (&vr0)
+	       && range_int_cst_p (&vr1)
+	       && tree_int_cst_sgn (vr0.min) >= 0
+	       && tree_int_cst_sgn (vr1.min) >= 0)
+	{
+	  double_int vr0_mask = tree_to_double_int (vr0.min);
+	  double_int vr1_mask = tree_to_double_int (vr1.min);
+	  double_int maxd, diff;
+	  tree mask;
+
+	  min = build_int_cst (expr_type, 0);
+	  /* Compute non-zero bits mask from both ranges.  */
+	  if (!vr0_int_cst_singleton_p)
+	    {
+	      maxd = tree_to_double_int (vr0.max);
+	      diff = double_int_sub (maxd, vr0_mask);
+	      if (diff.high)
+		{
+		  diff.low = ~(unsigned HOST_WIDE_INT)0;
+		  diff.high = ((HOST_WIDE_INT) 2
+			       << floor_log2 (diff.high)) - 1;
+		}
+	      else
+		diff.low = ((HOST_WIDE_INT) 2 << floor_log2 (diff.low)) - 1;
+	      vr0_mask = double_int_ior (vr0_mask,
+					 double_int_ior (maxd, diff));
+	    }
+	  if (!vr1_int_cst_singleton_p)
+	    {
+	      maxd = tree_to_double_int (vr1.max);
+	      diff = double_int_sub (maxd, vr1_mask);
+	      if (diff.high)
+		{
+		  diff.low = ~(unsigned HOST_WIDE_INT)0;
+		  diff.high = ((HOST_WIDE_INT) 2
+			       << floor_log2 (diff.high)) - 1;
+		}
+	      else
+		diff.low = ((HOST_WIDE_INT) 2 << floor_log2 (diff.low)) - 1;
+	      vr1_mask = double_int_ior (vr1_mask,
+					 double_int_ior (maxd, diff));
+	    }
+	  mask = double_int_to_tree (expr_type,
+				     double_int_and (vr0_mask, vr1_mask));
+	  max = vr0.max;
+	  if (tree_int_cst_lt (vr1.max, max))
+	    max = vr1.max;
+	  if (!TREE_OVERFLOW (mask)
+	      && tree_int_cst_lt (mask, max)
+	      && tree_int_cst_sgn (mask) >= 0)
+	    max = mask;
+	}
       else if (vr0_int_cst_singleton_p
 	       && tree_int_cst_sgn (vr0.max) >= 0)
 	{
--- gcc/testsuite/gcc.dg/tree-ssa/vrp50.c.jj	2010-07-08 16:24:42.000000000 +0200
+++ gcc/testsuite/gcc.dg/tree-ssa/vrp50.c	2010-07-08 16:32:26.000000000 +0200
@@ -0,0 +1,36 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-vrp1" } */
+
+int
+foo (unsigned int i, unsigned int j)
+{
+  i &= 15;
+  j &= 15;
+  i += 1024;
+  j += 2048;
+  i &= j;
+  return i < 16;
+}
+
+int
+bar (int i)
+{
+  int c = 2;
+  c &= i > 6;
+  return c == 0;
+}
+
+int baz (int x, int y)
+{
+  x &= 15;
+  y &= 15;
+  x += 4;
+  y += 16;
+  x &= y;
+  return x < 20;
+}
+
+/* { dg-final { scan-tree-dump "Folding predicate i_\[^\n\r\]* to 1" "vrp1" } } */
+/* { dg-final { scan-tree-dump "Folding predicate c_\[^\n\r\]* to 1" "vrp1" } } */
+/* { dg-final { scan-tree-dump "Folding predicate x_\[^\n\r\]* to 1" "vrp1" } } */
+/* { dg-final { cleanup-tree-dump "vrp1" } } */
--- gcc/testsuite/gcc.dg/vect/slp-perm-4.c.jj	2010-06-11 11:00:46.000000000 +0200
+++ gcc/testsuite/gcc.dg/vect/slp-perm-4.c	2010-07-08 18:53:40.102558207 +0200
@@ -69,6 +69,7 @@ int main (int argc, const char* argv[])
       if (input[i] > 200)
         abort();
       output[i] = 0;
+      __asm__ volatile ("");
     }
 
   foo (input, output);