tree-vrp.c (zero_nonzero_bits_from_vr): Also return precise information for ranges with only negative values.

2011-08-09  Richard Guenther  <rguenther@suse.de>

	* tree-vrp.c (zero_nonzero_bits_from_vr): Also return precise
	information for ranges with only negative values.
	(extract_range_from_binary_expr_1): Adjust BIT_IOR_EXPR and
	BIT_AND_EXPR handling to handle ranges with negative values.

	* gcc.dg/tree-ssa/vrp57.c: Disable CCP.
	* gcc.dg/tree-ssa/vrp60.c: New testcase.
	* gcc.dg/tree-ssa/vrp61.c: Likewise.
	* gcc.dg/tree-ssa/vrp62.c: Likewise.

From-SVN: r177597

7 files changed, 255 insertions, 73 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 1e2d311..6adde4a 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,10 @@
+2011-08-09  Richard Guenther  <rguenther@suse.de>
+
+	* tree-vrp.c (zero_nonzero_bits_from_vr): Also return precise
+	information for ranges with only negative values.
+	(extract_range_from_binary_expr_1): Adjust BIT_IOR_EXPR and
+	BIT_AND_EXPR handling to handle ranges with negative values.
+
 2011-08-09  Kirill Yukhin  <kirill.yukhin@intel.com>
 
        * config/i386/i386.c: Remove traling spaces.
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index d3e9419..ba43536 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,10 @@
+2011-08-09  Richard Guenther  <rguenther@suse.de>
+
+	* gcc.dg/tree-ssa/vrp57.c: Disable CCP.
+	* gcc.dg/tree-ssa/vrp60.c: New testcase.
+	* gcc.dg/tree-ssa/vrp61.c: Likewise.
+	* gcc.dg/tree-ssa/vrp62.c: Likewise.
+
 2011-08-09  Ulrich Weigand  <Ulrich.Weigand@de.ibm.com>
 
 	* gfortran.dg/scratch_1.f90: Skip on spu-*-*.
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp57.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp57.c
index c736adc..cac3783 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/vrp57.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp57.c
@@ -1,6 +1,6 @@
 /* PR40052 */
 /* { dg-do compile } */
-/* { dg-options "-O -ftree-vrp -fdump-tree-optimized" } */
+/* { dg-options "-O -ftree-vrp -fno-tree-ccp -fdump-tree-optimized" } */
 
 int foo(_Bool b)
 {
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp60.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp60.c
new file mode 100644
index 0000000..9b34e3d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp60.c
@@ -0,0 +1,31 @@
+/* { dg-do compile } */

+/* { dg-options "-O2 -fno-tree-ccp -fno-tree-dominator-opts -fdump-tree-vrp1" } */

+

+int foo (int x, int b)

+{

+  int cst;

+  if (b)

+    cst = -__INT_MAX__ - 1;

+  else

+    cst = -__INT_MAX__;

+  x = x | cst;

+  if (x >= 0)

+    return 12345;

+  return x;

+}

+

+int bar (int x, int b)

+{

+  int cst;

+  if (b)

+    cst = __INT_MAX__;

+  else

+    cst = __INT_MAX__ - 1;

+  x = x & cst;

+  if (x < 0)

+    return 12345;

+  return x;

+}

+

+/* { dg-final { scan-tree-dump-not "12345" "vrp1" } } */

+/* { dg-final { cleanup-tree-dump "vrp1" } } */

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp61.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp61.c
new file mode 100644
index 0000000..93bcbc9
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp61.c
@@ -0,0 +1,16 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-vrp1" } */
+
+int f (int x, int y)
+{
+  if (x > -1024 && x < 0 && y > -1024 && y < 0)
+    {
+      x = x ^ y;
+      if (x < 0 || x > 1023)
+	return 1234;
+    }
+  return x;
+}
+
+/* { dg-final { scan-tree-dump-not "1234" "vrp1" } } */
+/* { dg-final { cleanup-tree-dump "vrp1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp62.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp62.c
new file mode 100644
index 0000000..139195b
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp62.c
@@ -0,0 +1,110 @@
+/* { dg-do run } */
+/* { dg-options "-O2 -fno-tree-ccp -fno-tree-dominator-opts" } */
+
+/* Tests generated via  */
+
+#if 0
+#include <stdio.h>
+int main(int argc, char **argv)
+{
+  int amin, amax, bmin, bmax, a, b;
+  int testno = 0;
+  int min = atoi (argv[1]);
+  int max = atoi (argv[2]);
+  char op = argv[3][0];
+  printf ("/* Testing range [%d, %d] with operator %c.  */\n", min, max, op);
+  printf ("extern void abort (void);\n");
+  for (amin = min; amin <= max; ++amin)
+    for (amax = amin; amax <= max; ++amax)
+      for (bmin = min; bmin <= max; ++bmin)
+	for (bmax = bmin; bmax <= max; ++bmax)
+	  {
+	    ++testno;
+	    printf ("int test%d (int a, int b)\n"
+		    "{\n"
+		    "  if (a >= %d && a <= %d && b >= %d && b <= %d)\n"
+		    "   {\n"
+		    "      int x = a %c b;\n"
+		    "      if (0\n", testno, amin, amax, bmin, bmax, op);
+	    for (a = amin; a <= amax; ++a)
+	      for (b = bmin; b <= bmax; ++b)
+		printf ("|| x == (%d %c %d)\n", a, op, b);
+	    printf ("         ) return 0;\n"
+		    "      abort ();\n"
+		    "   }\n"
+		    "  return 0;\n"
+		    "}\n");
+	  }
+  printf ("int main()\n"
+	  "{\n"
+	  "  int a, b;\n"
+	  "  for (a = %d; a <= %d; ++a)\n"
+	  "    for (b = %d; b <= %d; ++b)\n"
+	  "      {\n", min, max, min, max);
+  for (; testno > 0; --testno)
+    printf ("      test%d (a, b);\n", testno);
+  printf ("      }\n"
+	  "  return 0;\n"
+	  "}\n");
+  return 0;
+}
+#endif
+
+extern void abort (void);
+
+int test381 (int a, int b)
+{
+  if (a >= -3 && a <= -1 && b >= -2 && b <= 3)
+    {
+      int x = a | b;
+      if (x == (-3 | -2)
+	  || x == (-3 | -1)
+	  || x == (-3 | 0)
+	  || x == (-3 | 1)
+	  || x == (-3 | 2)
+	  || x == (-3 | 3)
+	  || x == (-2 | -2)
+	  || x == (-2 | -1)
+	  || x == (-2 | 0)
+	  || x == (-2 | 1)
+	  || x == (-2 | 2)
+	  || x == (-2 | 3)
+	  || x == (-1 | -2)
+	  || x == (-1 | -1)
+	  || x == (-1 | 0)
+	  || x == (-1 | 1)
+	  || x == (-1 | 2)
+	  || x == (-1 | 3))
+	return 0;
+      abort ();
+    }
+  return 0;
+}
+
+int test900 (int a, int b)
+{
+  if (a >= -1 && a <= 2 && b >= 3 && b <= 3)
+    {
+      int x = a & b;
+      if (x == (-1 & 3)
+	  || x == (0 & 3)
+	  || x == (1 & 3)
+	  || x == (2 & 3))
+	return 0;
+      abort ();
+    }
+  return 0;
+}
+
+int main()
+{
+  int a, b;
+  for (a = -4; a < 4; ++a)
+    for (b = -4; b < 4; ++b)
+      {
+	test381 (a, b);
+	test900 (a, b);
+      }
+
+  return 0;
+}
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 2eeb379..0faf53a 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -2138,49 +2138,49 @@ vrp_int_const_binop (enum tree_code code, tree val1, tree val2)
    the bit is 1, otherwise it might be 0 or 1.  */
 
 static bool
-zero_nonzero_bits_from_vr (value_range_t *vr, double_int *may_be_nonzero,
+zero_nonzero_bits_from_vr (value_range_t *vr,
+			   double_int *may_be_nonzero,
 			   double_int *must_be_nonzero)
 {
-  may_be_nonzero->low = ALL_ONES;
-  may_be_nonzero->high = ALL_ONES;
-  must_be_nonzero->low = 0;
-  must_be_nonzero->high = 0;
-  if (range_int_cst_p (vr))
+  *may_be_nonzero = double_int_minus_one;
+  *must_be_nonzero = double_int_zero;
+  if (!range_int_cst_p (vr))
+    return false;
+
+  if (range_int_cst_singleton_p (vr))
+    {
+      *may_be_nonzero = tree_to_double_int (vr->min);
+      *must_be_nonzero = *may_be_nonzero;
+    }
+  else if (tree_int_cst_sgn (vr->min) >= 0
+	   || tree_int_cst_sgn (vr->max) < 0)
     {
-      if (range_int_cst_singleton_p (vr))
+      double_int dmin = tree_to_double_int (vr->min);
+      double_int dmax = tree_to_double_int (vr->max);
+      double_int xor_mask = double_int_xor (dmin, dmax);
+      *may_be_nonzero = double_int_ior (dmin, dmax);
+      *must_be_nonzero = double_int_and (dmin, dmax);
+      if (xor_mask.high != 0)
 	{
-	  *may_be_nonzero = tree_to_double_int (vr->min);
-	  *must_be_nonzero = *may_be_nonzero;
+	  unsigned HOST_WIDE_INT mask
+	      = ((unsigned HOST_WIDE_INT) 1
+		 << floor_log2 (xor_mask.high)) - 1;
+	  may_be_nonzero->low = ALL_ONES;
+	  may_be_nonzero->high |= mask;
+	  must_be_nonzero->low = 0;
+	  must_be_nonzero->high &= ~mask;
 	}
-      else if (tree_int_cst_sgn (vr->min) >= 0)
+      else if (xor_mask.low != 0)
 	{
-	  double_int dmin = tree_to_double_int (vr->min);
-	  double_int dmax = tree_to_double_int (vr->max);
-	  double_int xor_mask = double_int_xor (dmin, dmax);
-	  *may_be_nonzero = double_int_ior (dmin, dmax);
-	  *must_be_nonzero = double_int_and (dmin, dmax);
-	  if (xor_mask.high != 0)
-	    {
-	      unsigned HOST_WIDE_INT mask
-		= ((unsigned HOST_WIDE_INT) 1
-		   << floor_log2 (xor_mask.high)) - 1;
-	      may_be_nonzero->low = ALL_ONES;
-	      may_be_nonzero->high |= mask;
-	      must_be_nonzero->low = 0;
-	      must_be_nonzero->high &= ~mask;
-	    }
-	  else if (xor_mask.low != 0)
-	    {
-	      unsigned HOST_WIDE_INT mask
-		= ((unsigned HOST_WIDE_INT) 1
-		   << floor_log2 (xor_mask.low)) - 1;
-	      may_be_nonzero->low |= mask;
-	      must_be_nonzero->low &= ~mask;
-	    }
+	  unsigned HOST_WIDE_INT mask
+	      = ((unsigned HOST_WIDE_INT) 1
+		 << floor_log2 (xor_mask.low)) - 1;
+	  may_be_nonzero->low |= mask;
+	  must_be_nonzero->low &= ~mask;
 	}
-      return true;
     }
-  return false;
+
+  return true;
 }
 
 
@@ -2650,50 +2650,63 @@ extract_range_from_binary_expr_1 (value_range_t *vr,
       type = VR_RANGE;
       if (code == BIT_AND_EXPR)
 	{
+	  double_int dmax;
 	  min = double_int_to_tree (expr_type,
 				    double_int_and (must_be_nonzero0,
 						    must_be_nonzero1));
-	  max = double_int_to_tree (expr_type,
-				    double_int_and (may_be_nonzero0,
-						    may_be_nonzero1));
-	  if (tree_int_cst_sgn (min) < 0)
-	    min = NULL_TREE;
-	  if (tree_int_cst_sgn (max) < 0)
-	    max = NULL_TREE;
-	  if (int_cst_range0 && tree_int_cst_sgn (vr0.min) >= 0)
+	  dmax = double_int_and (may_be_nonzero0, may_be_nonzero1);
+	  /* If both input ranges contain only negative values we can
+	     truncate the result range maximum to the minimum of the
+	     input range maxima.  */
+	  if (int_cst_range0 && int_cst_range1
+	      && tree_int_cst_sgn (vr0.max) < 0
+	      && tree_int_cst_sgn (vr1.max) < 0)
 	    {
-	      if (min == NULL_TREE)
-		min = build_int_cst (expr_type, 0);
-	      if (max == NULL_TREE || tree_int_cst_lt (vr0.max, max))
-		max = vr0.max;
+	      dmax = double_int_min (dmax, tree_to_double_int (vr0.max),
+				     TYPE_UNSIGNED (expr_type));
+	      dmax = double_int_min (dmax, tree_to_double_int (vr1.max),
+				     TYPE_UNSIGNED (expr_type));
 	    }
+	  /* If either input range contains only non-negative values
+	     we can truncate the result range maximum to the respective
+	     maximum of the input range.  */
+	  if (int_cst_range0 && tree_int_cst_sgn (vr0.min) >= 0)
+	    dmax = double_int_min (dmax, tree_to_double_int (vr0.max),
+				   TYPE_UNSIGNED (expr_type));
 	  if (int_cst_range1 && tree_int_cst_sgn (vr1.min) >= 0)
-	    {
-	      if (min == NULL_TREE)
-		min = build_int_cst (expr_type, 0);
-	      if (max == NULL_TREE || tree_int_cst_lt (vr1.max, max))
-		max = vr1.max;
-	    }
+	    dmax = double_int_min (dmax, tree_to_double_int (vr1.max),
+				   TYPE_UNSIGNED (expr_type));
+	  max = double_int_to_tree (expr_type, dmax);
 	}
       else if (code == BIT_IOR_EXPR)
 	{
-	  min = double_int_to_tree (expr_type,
-				    double_int_ior (must_be_nonzero0,
-						    must_be_nonzero1));
+	  double_int dmin;
 	  max = double_int_to_tree (expr_type,
 				    double_int_ior (may_be_nonzero0,
 						    may_be_nonzero1));
-	  if (tree_int_cst_sgn (max) < 0)
-	    max = NULL_TREE;
-	  if (int_cst_range0)
+	  dmin = double_int_ior (must_be_nonzero0, must_be_nonzero1);
+	  /* If the input ranges contain only positive values we can
+	     truncate the minimum of the result range to the maximum
+	     of the input range minima.  */
+	  if (int_cst_range0 && int_cst_range1
+	      && tree_int_cst_sgn (vr0.min) >= 0
+	      && tree_int_cst_sgn (vr1.min) >= 0)
 	    {
-	      if (tree_int_cst_sgn (min) < 0)
-		min = vr0.min;
-	      else
-		min = vrp_int_const_binop (MAX_EXPR, min, vr0.min);
+	      dmin = double_int_max (dmin, tree_to_double_int (vr0.min),
+				     TYPE_UNSIGNED (expr_type));
+	      dmin = double_int_max (dmin, tree_to_double_int (vr1.min),
+				     TYPE_UNSIGNED (expr_type));
 	    }
-	  if (int_cst_range1)
-	    min = vrp_int_const_binop (MAX_EXPR, min, vr1.min);
+	  /* If either input range contains only negative values
+	     we can truncate the minimum of the result range to the
+	     respective minimum range.  */
+	  if (int_cst_range0 && tree_int_cst_sgn (vr0.max) < 0)
+	    dmin = double_int_max (dmin, tree_to_double_int (vr0.min),
+				   TYPE_UNSIGNED (expr_type));
+	  if (int_cst_range1 && tree_int_cst_sgn (vr1.max) < 0)
+	    dmin = double_int_max (dmin, tree_to_double_int (vr1.min),
+				   TYPE_UNSIGNED (expr_type));
+	  min = double_int_to_tree (expr_type, dmin);
 	}
       else if (code == BIT_XOR_EXPR)
 	{
@@ -2714,14 +2727,12 @@ extract_range_from_binary_expr_1 (value_range_t *vr,
 	  max = double_int_to_tree (expr_type,
 				    double_int_not (result_zero_bits));
 	  min = double_int_to_tree (expr_type, result_one_bits);
-	  /* Return a [min, max] range if we know the
-	     result range is either positive or negative.  */
-	  if (tree_int_cst_sgn (max) >= 0)
-	    /* The range is bound by a lower value of 0.  */;
-	  else if (tree_int_cst_sgn (min) < 0)
-	    /* The range is bound by an upper value of -1.  */;
+	  /* If the range has all positive or all negative values the
+	     result is better than VARYING.  */
+	  if (tree_int_cst_sgn (min) < 0
+	      || tree_int_cst_sgn (max) >= 0)
+	    ;
 	  else
-	    /* We don't know whether the sign bit is set or not.  */
 	    max = min = NULL_TREE;
 	}
       else