PR tree-optimization/51721

	* tree-vrp.c (register_edge_assert_for_2): If comparing
	lhs of right shift by constant with an integer constant,
	add ASSERT_EXPRs for the rhs1 of the right shift.

	* gcc.dg/tree-ssa/vrp63.c: New test.
	* gcc.dg/pr51721.c: New test.


git-svn-id: https://gcc.gnu.org/svn/gcc/trunk@184927 138bc75d-0d04-0410-961f-82ee72b054a4

5 files changed, 475 insertions, 1 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 3d22178d040..565ca5b105e 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,10 @@
 2012-03-05  Jakub Jelinek  <jakub@redhat.com>
 
+	PR tree-optimization/51721
+	* tree-vrp.c (register_edge_assert_for_2): If comparing
+	lhs of right shift by constant with an integer constant,
+	add ASSERT_EXPRs for the rhs1 of the right shift.
+
 	* cfgrtl.c (cfg_layout_merge_blocks): Cleanup.
 
 2012-03-05  Richard Guenther  <rguenther@suse.de>
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index fc4158423c4..85a44107ce3 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,9 @@
+2012-03-05  Jakub Jelinek  <jakub@redhat.com>
+
+	PR tree-optimization/51721
+	* gcc.dg/tree-ssa/vrp63.c: New test.
+	* gcc.dg/pr51721.c: New test.
+
 2012-03-04  Mikael Morin  <mikael@gcc.gnu.org>
 
 	PR fortran/50981
diff --git a/gcc/testsuite/gcc.dg/pr51721.c b/gcc/testsuite/gcc.dg/pr51721.c
new file mode 100644
index 00000000000..b39adfb50c2
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr51721.c
@@ -0,0 +1,31 @@
+/* PR tree-optimization/51721 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -Warray-bounds" } */
+
+static int a[10], b[10], c[10], d[10];
+
+unsigned int
+f (unsigned int v)
+{
+  return v == 17 ? 11 : v;
+}
+
+unsigned int
+g (unsigned int v)
+{
+  return v == 17 ? 17 : v;
+}
+
+void
+t (unsigned int s)
+{
+  if (s >> 1 == 0)
+    {
+      a[f (s)] = 0;	/* { dg-bogus "array subscript is above array bounds" } */
+      a[f (s)] = 0;	/* { dg-bogus "array subscript is above array bounds" } */
+      b[f (s)] = 0;	/* { dg-bogus "array subscript is above array bounds" } */
+      c[g (s)] = 0;	/* { dg-bogus "array subscript is above array bounds" } */
+      c[g (s)] = 0;	/* { dg-bogus "array subscript is above array bounds" } */
+      d[f (s)] = 0;	/* { dg-bogus "array subscript is above array bounds" } */
+    }
+}
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp63.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp63.c
new file mode 100644
index 00000000000..9116847de53
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp63.c
@@ -0,0 +1,345 @@
+/* PR tree-optimization/51721 */
+/* { dg-do link } */
+/* { dg-options "-O2" } */
+
+extern void link_error (void);
+
+#define BITSM1 (sizeof (int) * __CHAR_BIT__ - 1)
+
+void
+f1 (unsigned int s)
+{
+  if (s >> 1 == 0)
+    {
+      if (s == 2 || s == -1U)
+	link_error ();
+    }
+  else
+    {
+      if (s == 0 || s == 1)
+	link_error ();
+    }
+}
+
+void
+f2 (unsigned int s)
+{
+  if (s >> 4 != 3)
+    {
+      if (s == 48 || s == 57 || s == 63)
+	link_error ();
+    }
+  else
+    {
+      if (s == 47 || s == 64 || s == 0 || s == -1U)
+	link_error ();
+    }
+}
+
+void
+f3 (int s)
+{
+  if (s >> 3 == -2)
+    {
+      if (s == -17 || s == -8 || s == 0
+	  || s == -__INT_MAX__ - 1 || s == __INT_MAX__)
+	link_error ();
+    }
+  else
+    {
+      if (s == -16 || s == -12 || s == -9)
+	link_error ();
+    }
+}
+
+void
+f4 (unsigned int s)
+{
+  if (s >> 2 < 4)
+    {
+      if (s == 16 || s == 20 || s == -1U)
+	link_error ();
+    }
+  else
+    {
+      if (s == 0 || s == 2 || s == 14 || s == 15)
+	link_error ();
+    }
+}
+
+void
+f5 (unsigned int s)
+{
+  if (s >> 3 <= 7)
+    {
+      if (s == 64 || s == 68 || s == -1U)
+	link_error ();
+    }
+  else
+    {
+      if (s == 0 || s == 1 || s == 62 || s == 63)
+	link_error ();
+    }
+}
+
+void
+f6 (unsigned int s)
+{
+  if (s >> 1 > 2)
+    {
+      if (s == 0 || s == 3 || s == 5)
+	link_error ();
+    }
+  else
+    {
+      if (s == 6 || s == 8 || s == -1U)
+	link_error ();
+    }
+}
+
+void
+f7 (unsigned int s)
+{
+  if (s >> 5 >= 7)
+    {
+      if (s == 0 || s == 2 || s == 221 || s == 223)
+	link_error ();
+    }
+  else
+    {
+      if (s == 224 || s == 256 || s == 258 || s == -1U)
+	link_error ();
+    }
+}
+
+void
+f8 (int s)
+{
+  if (s >> 2 < -3)
+    {
+      if (s == -12 || s == -10 || s == 0 || s == __INT_MAX__)
+	link_error ();
+    }
+  else
+    {
+      if (s == -13 || s == -16 || s == -__INT_MAX__ - 1)
+	link_error ();
+    }
+}
+
+void
+f9 (int s)
+{
+  if (s >> 3 <= -2)
+    {
+      if (s == -8 || s == -6 || s == 0 || s == __INT_MAX__)
+	link_error ();
+    }
+  else
+    {
+      if (s == -9 || s == -11 || s == -__INT_MAX__ - 1)
+	link_error ();
+    }
+}
+
+void
+f10 (int s)
+{
+  if (s >> 1 > -4)
+    {
+      if (s == -7 || s == -9 || s == -__INT_MAX__ - 1)
+	link_error ();
+    }
+  else
+    {
+      if (s == -6 || s == -4 || s == 0 || s == __INT_MAX__)
+	link_error ();
+    }
+}
+
+void
+f11 (int s)
+{
+  if (s >> 3 >= -6)
+    {
+      if (s == -49 || s == -51 || s == -__INT_MAX__ - 1)
+	link_error ();
+    }
+  else
+    {
+      if (s == -48 || s == -46 || s == 0 || s == __INT_MAX__)
+	link_error ();
+    }
+}
+
+void
+f12 (int s)
+{
+  if (s >> 2 < 4)
+    {
+      if (s == 16 || s == 20 || s == __INT_MAX__)
+	link_error ();
+    }
+  else
+    {
+      if (s == 0 || s == 2 || s == 14 || s == 15
+	  || s == -2 || s == -__INT_MAX__ - 1)
+	link_error ();
+    }
+}
+
+void
+f13 (int s)
+{
+  if (s >> 3 <= 7)
+    {
+      if (s == 64 || s == 68 || s == __INT_MAX__)
+	link_error ();
+    }
+  else
+    {
+      if (s == 0 || s == 1 || s == 62 || s == 63
+	  || s == -2 || s == -__INT_MAX__ - 1)
+	link_error ();
+    }
+}
+
+void
+f14 (int s)
+{
+  if (s >> 1 > 2)
+    {
+      if (s == 0 || s == 3 || s == 5
+	  || s == -2 || s == -__INT_MAX__ - 1)
+	link_error ();
+    }
+  else
+    {
+      if (s == 6 || s == 8 || s == __INT_MAX__)
+	link_error ();
+    }
+}
+
+void
+f15 (int s)
+{
+  if (s >> 5 >= 7)
+    {
+      if (s == 0 || s == 2 || s == 221 || s == 223
+	  || s == -2 || s == -__INT_MAX__ - 1)
+	link_error ();
+    }
+  else
+    {
+      if (s == 224 || s == 256 || s == 258 || s == __INT_MAX__)
+	link_error ();
+    }
+}
+
+unsigned int
+f16 (unsigned int s)
+{
+  unsigned int t = s >> BITSM1;
+  if (t != 0)
+    {
+      if (s == 0 || s == 5 || s == __INT_MAX__)
+	link_error ();
+    }
+  else
+    {
+      if (s == 1U + __INT_MAX__ || s == 6U + __INT_MAX__ || s == -1U)
+	link_error ();
+    }
+  return t;
+}
+
+int
+f17 (int s)
+{
+  int t = s >> BITSM1;
+  if (t == 0)
+    {
+      if (s == -1 || s == -5 || s == -__INT_MAX__ - 1)
+	link_error ();
+    }
+  else
+    {
+      if (s == 0 || s == 5 || s == __INT_MAX__)
+	link_error ();
+    }
+  return t;
+}
+
+unsigned int
+f18 (unsigned int s)
+{
+  unsigned int t = s >> BITSM1;
+  if (t >= 1)
+    {
+      if (s == 0 || s == 5 || s == __INT_MAX__)
+	link_error ();
+    }
+  else
+    {
+      if (s == 1U + __INT_MAX__ || s == 6U + __INT_MAX__ || s == -1U)
+	link_error ();
+    }
+  return t;
+}
+
+int
+f19 (int s)
+{
+  int t = s >> BITSM1;
+  if (t >= 0)
+    {
+      if (s == -1 || s == -5 || s == -__INT_MAX__ - 1)
+	link_error ();
+    }
+  else
+    {
+      if (s == 0 || s == 5 || s == __INT_MAX__)
+	link_error ();
+    }
+  return t;
+}
+
+unsigned int
+f20 (unsigned int s)
+{
+  unsigned int t = s >> BITSM1;
+  if (t < 1)
+    {
+      if (s == 1U + __INT_MAX__ || s == 6U + __INT_MAX__ || s == -1U)
+	link_error ();
+    }
+  else
+    {
+      if (s == 0 || s == 5 || s == __INT_MAX__)
+	link_error ();
+    }
+  return t;
+}
+
+int
+f21 (int s)
+{
+  int t = s >> BITSM1;
+  if (t < 0)
+    {
+      if (s == 0 || s == 5 || s == __INT_MAX__)
+	link_error ();
+    }
+  else
+    {
+      if (s == -1 || s == -5 || s == -__INT_MAX__ - 1)
+	link_error ();
+    }
+  return t;
+}
+
+int
+main ()
+{
+  return 0;
+}
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 4a018f73c17..d3922db038a 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -1,5 +1,5 @@
 /* Support routines for Value Range Propagation (VRP).
-   Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011
+   Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
    Free Software Foundation, Inc.
    Contributed by Diego Novillo <dnovillo@redhat.com>.
 
@@ -4462,6 +4462,93 @@ register_edge_assert_for_2 (tree name, edge e, gimple_stmt_iterator bsi,
 	}
     }
 
+  /* Similarly add asserts for NAME == CST and NAME being defined as
+     NAME = NAME2 >> CST2.  */
+  if (TREE_CODE_CLASS (comp_code) == tcc_comparison
+      && TREE_CODE (val) == INTEGER_CST)
+    {
+      gimple def_stmt = SSA_NAME_DEF_STMT (name);
+      tree name2 = NULL_TREE, cst2 = NULL_TREE;
+      tree val2 = NULL_TREE;
+      unsigned HOST_WIDE_INT mask[2] = { 0, 0 };
+
+      /* Extract CST2 from the right shift.  */
+      if (is_gimple_assign (def_stmt)
+	  && gimple_assign_rhs_code (def_stmt) == RSHIFT_EXPR)
+	{
+	  name2 = gimple_assign_rhs1 (def_stmt);
+	  cst2 = gimple_assign_rhs2 (def_stmt);
+	  if (TREE_CODE (name2) == SSA_NAME
+	      && host_integerp (cst2, 1)
+	      && (unsigned HOST_WIDE_INT) tree_low_cst (cst2, 1)
+		 < 2 * HOST_BITS_PER_WIDE_INT
+	      && INTEGRAL_TYPE_P (TREE_TYPE (name2))
+	      && live_on_edge (e, name2)
+	      && !has_single_use (name2))
+	    {
+	      if ((unsigned HOST_WIDE_INT) tree_low_cst (cst2, 1)
+		  < HOST_BITS_PER_WIDE_INT)
+		mask[0] = ((unsigned HOST_WIDE_INT) 1
+			   << tree_low_cst (cst2, 1)) - 1;
+	      else
+		{
+		  mask[1] = ((unsigned HOST_WIDE_INT) 1
+			     << (tree_low_cst (cst2, 1)
+				 - HOST_BITS_PER_WIDE_INT)) - 1;
+		  mask[0] = -1;
+		}
+	      val2 = fold_binary (LSHIFT_EXPR, TREE_TYPE (val), val, cst2);
+	    }
+	}
+
+      if (val2 != NULL_TREE
+	  && TREE_CODE (val2) == INTEGER_CST
+	  && simple_cst_equal (fold_build2 (RSHIFT_EXPR,
+					    TREE_TYPE (val),
+					    val2, cst2), val))
+	{
+	  enum tree_code new_comp_code = comp_code;
+	  tree tmp, new_val;
+
+	  tmp = name2;
+	  if (comp_code == EQ_EXPR || comp_code == NE_EXPR)
+	    {
+	      if (!TYPE_UNSIGNED (TREE_TYPE (val)))
+		{
+		  unsigned int prec = TYPE_PRECISION (TREE_TYPE (val));
+		  tree type = build_nonstandard_integer_type (prec, 1);
+		  tmp = build1 (NOP_EXPR, type, name2);
+		  val2 = fold_convert (type, val2);
+		}
+	      tmp = fold_build2 (MINUS_EXPR, TREE_TYPE (tmp), tmp, val2);
+	      new_val = build_int_cst_wide (TREE_TYPE (tmp), mask[0], mask[1]);
+	      new_comp_code = comp_code == EQ_EXPR ? LE_EXPR : GT_EXPR;
+	    }
+	  else if (comp_code == LT_EXPR || comp_code == GE_EXPR)
+	    new_val = val2;
+	  else
+	    {
+	      new_val = build_int_cst_wide (TREE_TYPE (val2),
+					    mask[0], mask[1]);
+	      new_val = fold_binary (BIT_IOR_EXPR, TREE_TYPE (val2),
+				     val2, new_val);
+	    }
+
+	  if (dump_file)
+	    {
+	      fprintf (dump_file, "Adding assert for ");
+	      print_generic_expr (dump_file, name2, 0);
+	      fprintf (dump_file, " from ");
+	      print_generic_expr (dump_file, tmp, 0);
+	      fprintf (dump_file, "\n");
+	    }
+
+	  register_new_assert_for (name2, tmp, new_comp_code, new_val,
+				   NULL, e, bsi);
+	  retval = true;
+	}
+    }
+
   return retval;
 }