re PR tree-optimization/15911 (VRP/DOM does not like TRUTH_AND_EXPR)

2006-10-22  Jeff Law  <law@redhat.com>
	Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/15911
	* tree-vrp.c (extract_code_and_val_from_cond): New function.
	(register_edge_assert_for_1): Likewise.
	(register_edge_assert_for): Handle &&/&/||/| in conditionals.
	(find_conditional_asserts): Adjust for new function signature.
	(find_assert_locations): Likewise.

	* gcc.dg/tree-ssa/vrp30.c: New testcase.

Co-Authored-By: Richard Guenther <rguenther@suse.de>

From-SVN: r117960

4 files changed, 289 insertions, 81 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index bbe1878..85fde5d 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,13 @@
+2006-10-22  Jeff Law  <law@redhat.com>
+	Richard Guenther  <rguenther@suse.de>
+
+	PR tree-optimization/15911
+	* tree-vrp.c (extract_code_and_val_from_cond): New function.
+	(register_edge_assert_for_1): Likewise.
+	(register_edge_assert_for): Handle &&/&/||/| in conditionals.
+	(find_conditional_asserts): Adjust for new function signature.
+	(find_assert_locations): Likewise.
+
 2006-10-22  H.J. Lu  <hongjiu.lu@intel.com>
 
 	* config/i386/tmmintrin.h: Remove the duplicated content.
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 1d6b02b..860107e 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,9 @@
+2006-10-22  Jeff Law  <law@redhat.com>
+	Richard Guenther  <rguenther@suse.de>
+
+	PR tree-optimization/15911
+	* gcc.dg/tree-ssa/vrp30.c: New testcase.
+
 2006-10-22  Nathan Sidwell  <nathan@codesourcery.com>
 
 	PR c++/20647
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp30.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp30.c
new file mode 100644
index 0000000..245dcfb
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp30.c
@@ -0,0 +1,30 @@
+/* { dg-do link } */
+/* { dg-options "-O2" } */
+
+extern int link_error (int);
+
+int tst2 (int x, int y)
+{
+  /* VRP should be able to extract range information for
+     x and y out of this TRUTH_AND_EXPR.  */
+  if ((x > 5555) && (y < 6666))
+    {
+      if (x > 5555)
+        if (y < 6666)
+          return 1111;
+        else
+          return link_error (2222);
+      else
+        if (y < 6666)
+          return link_error (3333);
+        else
+          return link_error (4444);
+    }
+  else
+    return 0;
+}
+
+int main()
+{
+  return 0;
+}
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 8e67e8a..6d220fb 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -2688,127 +2688,288 @@ register_new_assert_for (tree name,
   bitmap_set_bit (need_assert_for, SSA_NAME_VERSION (name));
 }
 
+/* COND is a predicate which uses NAME.  Extract a suitable test code
+   and value and store them into *CODE_P and *VAL_P so the predicate
+   is normalized to NAME *CODE_P *VAL_P.
 
-/* Try to register an edge assertion for SSA name NAME on edge E for
-   the conditional jump pointed to by SI.  Return true if an assertion
-   for NAME could be registered.  */
+   If no extraction was possible, return FALSE, otherwise return TRUE.
+
+   If INVERT is true, then we invert the result stored into *CODE_P.  */
 
 static bool
-register_edge_assert_for (tree name, edge e, block_stmt_iterator si)
+extract_code_and_val_from_cond (tree name, tree cond, bool invert,
+				enum tree_code *code_p, tree *val_p)
 {
-  tree val, stmt;
   enum tree_code comp_code;
+  tree val;
+
+  /* Predicates may be a single SSA name or NAME OP VAL.  */
+  if (cond == name)
+    {
+      /* If the predicate is a name, it must be NAME, in which
+	 case we create the predicate NAME == true or
+	 NAME == false accordingly.  */
+      comp_code = EQ_EXPR;
+      val = invert ? boolean_false_node : boolean_true_node;
+    }
+  else
+    {
+      /* Otherwise, we have a comparison of the form NAME COMP VAL
+         or VAL COMP NAME.  */
+      if (name == TREE_OPERAND (cond, 1))
+        {
+	  /* If the predicate is of the form VAL COMP NAME, flip
+	     COMP around because we need to register NAME as the
+	     first operand in the predicate.  */
+	  comp_code = swap_tree_comparison (TREE_CODE (cond));
+	  val = TREE_OPERAND (cond, 0);
+	}
+      else
+	{
+	  /* The comparison is of the form NAME COMP VAL, so the
+	     comparison code remains unchanged.  */
+	  comp_code = TREE_CODE (cond);
+	  val = TREE_OPERAND (cond, 1);
+	}
+
+      /* Invert the comparison code as necessary.  */
+      if (invert)
+	comp_code = invert_tree_comparison (comp_code, 0);
+
+      /* VRP does not handle float types.  */
+      if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (val)))
+	return false;
+
+      /* Do not register always-false predicates.
+	 FIXME:  this works around a limitation in fold() when dealing with
+	 enumerations.  Given 'enum { N1, N2 } x;', fold will not
+	 fold 'if (x > N2)' to 'if (0)'.  */
+      if ((comp_code == GT_EXPR || comp_code == LT_EXPR)
+	  && INTEGRAL_TYPE_P (TREE_TYPE (val)))
+	{
+	  tree min = TYPE_MIN_VALUE (TREE_TYPE (val));
+	  tree max = TYPE_MAX_VALUE (TREE_TYPE (val));
+
+	  if (comp_code == GT_EXPR
+	      && (!max
+	          || compare_values (val, max) == 0))
+	    return false;
+
+	  if (comp_code == LT_EXPR
+	      && (!min
+	          || compare_values (val, min) == 0))
+	    return false;
+	}
+    }
+  *code_p = comp_code;
+  *val_p = val;
+  return true;
+}
 
-  stmt = bsi_stmt (si);
+/* OP is an operand of a truth value expression which is known to have
+   a particular value.  Register any asserts for OP and for any
+   operands in OP's defining statement. 
+
+   If CODE is EQ_EXPR, then we want to register OP is zero (false),
+   if CODE is NE_EXPR, then we want to register OP is nonzero (true).   */
+
+static bool
+register_edge_assert_for_1 (tree op, enum tree_code code,
+			    edge e, block_stmt_iterator bsi)
+{
+  bool invert, retval = false;
+  tree op_def, rhs, val;
+
+  /* We only care about SSA_NAMEs.  */
+  if (TREE_CODE (op) != SSA_NAME)
+    return false;
+
+  /* We know that OP will have a zero or nonzero value.  If OP is used
+     more than once go ahead and register an assert for OP. 
+
+     The FOUND_IN_SUBGRAPH support is not helpful in this situation as
+     it will always be set for OP (because OP is used in a COND_EXPR in
+     the subgraph).  */
+  if (!has_single_use (op))
+    {
+      val = build_int_cst (TREE_TYPE (op), 0);
+      register_new_assert_for (op, code, val, NULL, e, bsi);
+      retval = true;
+    }
+
+  /* Now look at how OP is set.  If it's set from a comparison,
+     a truth operation or some bit operations, then we may be able
+     to register information about the operands of that assignment.  */
+  op_def = SSA_NAME_DEF_STMT (op);
+  if (TREE_CODE (op_def) != MODIFY_EXPR)
+    return retval;
+
+  invert = (code == EQ_EXPR ? true : false);
+  rhs = TREE_OPERAND (op_def, 1);
+
+  if (COMPARISON_CLASS_P (rhs))
+    {
+      tree op0 = TREE_OPERAND (rhs, 0);
+      tree op1 = TREE_OPERAND (rhs, 1);
+
+      /* Conditionally register an assert for each SSA_NAME in the
+	 comparison.  */
+      if (TREE_CODE (op0) == SSA_NAME
+	  && !has_single_use (op0)
+	  && extract_code_and_val_from_cond (op0, rhs,
+					     invert, &code, &val))
+	{
+	  register_new_assert_for (op0, code, val, NULL, e, bsi);
+	  retval = true;
+	}
+
+      /* Similarly for the second operand of the comparison.  */
+      if (TREE_CODE (op1) == SSA_NAME
+	  && !has_single_use (op1)
+	  && extract_code_and_val_from_cond (op1, rhs,
+					     invert, &code, &val))
+	{
+	  register_new_assert_for (op1, code, val, NULL, e, bsi);
+	  retval = true;
+	}
+    }
+  else if ((code == NE_EXPR
+	    && (TREE_CODE (rhs) == TRUTH_AND_EXPR
+		|| TREE_CODE (rhs) == BIT_AND_EXPR))
+	   || (code == EQ_EXPR
+	       && (TREE_CODE (rhs) == TRUTH_OR_EXPR
+		   || TREE_CODE (rhs) == BIT_IOR_EXPR)))
+    {
+      /* Recurse on each operand.  */
+      retval |= register_edge_assert_for_1 (TREE_OPERAND (rhs, 0),
+					    code, e, bsi);
+      retval |= register_edge_assert_for_1 (TREE_OPERAND (rhs, 1),
+					    code, e, bsi);
+    }
+  else if (TREE_CODE (rhs) == TRUTH_NOT_EXPR)
+    {
+      invert = !invert;
+      /* Recurse, flipping the tense of INVERT.  */
+      retval |= register_edge_assert_for_1 (TREE_OPERAND (rhs, 0),
+					    invert, e, bsi);
+    }
+  else if (TREE_CODE (rhs) == SSA_NAME)
+    {
+      /* Recurse through the copy, the tense of INVERT remains
+	 unchanged.  */
+      retval |= register_edge_assert_for_1 (rhs, code, e, bsi);
+    }
+  else if (TREE_CODE (rhs) == NOP_EXPR
+	   || TREE_CODE (rhs) == CONVERT_EXPR
+	   || TREE_CODE (rhs) == VIEW_CONVERT_EXPR
+	   || TREE_CODE (rhs) == NON_LVALUE_EXPR)
+    { 
+      /* Recurse through the type conversion, the tense of INVERT 
+	 remains unchanged.  */
+      retval |= register_edge_assert_for_1 (TREE_OPERAND (rhs, 0),
+					    code, e, bsi);
+    }
+
+  return retval;
+}
+
+/* Try to register an edge assertion for SSA name NAME on edge E for
+   the condition COND contributing to the conditional jump pointed to by SI.
+   Return true if an assertion for NAME could be registered.  */
+
+static bool
+register_edge_assert_for (tree name, edge e, block_stmt_iterator si, tree cond)
+{
+  tree val;
+  enum tree_code comp_code;
+  bool retval = false;
+  bool is_else_edge = (e->flags & EDGE_FALSE_VALUE) != 0;
 
   /* Do not attempt to infer anything in names that flow through
      abnormal edges.  */
   if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
     return false;
 
-  /* If NAME was not found in the sub-graph reachable from E, then
-     there's nothing to do.  */
-  if (!TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name)))
+  if (!extract_code_and_val_from_cond (name, cond, is_else_edge,
+				       &comp_code, &val))
     return false;
 
-  /* We found a use of NAME in the sub-graph rooted at E->DEST.
-     Register an assertion for NAME according to the value that NAME
-     takes on edge E.  */
-  if (TREE_CODE (stmt) == COND_EXPR)
+  /* Only register an ASSERT_EXPR if NAME was found in the sub-graph
+     reachable from E.  */
+  if (TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name)))
     {
-      /* If BB ends in a COND_EXPR then NAME then we should insert
-	 the original predicate on EDGE_TRUE_VALUE and the
-	 opposite predicate on EDGE_FALSE_VALUE.  */
-      tree cond = COND_EXPR_COND (stmt);
-      bool is_else_edge = (e->flags & EDGE_FALSE_VALUE) != 0;
-
-      /* Predicates may be a single SSA name or NAME OP VAL.  */
-      if (cond == name)
-	{
-	  /* If the predicate is a name, it must be NAME, in which
-	     case we create the predicate NAME == true or
-	     NAME == false accordingly.  */
-	  comp_code = EQ_EXPR;
-	  val = (is_else_edge) ? boolean_false_node : boolean_true_node;
-	}
-      else
-	{
-	  /* Otherwise, we have a comparison of the form NAME COMP VAL
-	     or VAL COMP NAME.  */
-	  if (name == TREE_OPERAND (cond, 1))
-	    {
-	      /* If the predicate is of the form VAL COMP NAME, flip
-		 COMP around because we need to register NAME as the
-		 first operand in the predicate.  */
-	      comp_code = swap_tree_comparison (TREE_CODE (cond));
-	      val = TREE_OPERAND (cond, 0);
-	    }
-	  else
-	    {
-	      /* The comparison is of the form NAME COMP VAL, so the
-		 comparison code remains unchanged.  */
-	      comp_code = TREE_CODE (cond);
-	      val = TREE_OPERAND (cond, 1);
-	    }
+      register_new_assert_for (name, comp_code, val, NULL, e, si);
+      retval = true;
+    }
 
-	  /* If we are inserting the assertion on the ELSE edge, we
-	     need to invert the sign comparison.  */
-	  if (is_else_edge)
-	    comp_code = invert_tree_comparison (comp_code, 0);
-
-	  /* Do not register always-false predicates.  FIXME, this
-	     works around a limitation in fold() when dealing with
-	     enumerations.  Given 'enum { N1, N2 } x;', fold will not
-	     fold 'if (x > N2)' to 'if (0)'.  */
-	  if ((comp_code == GT_EXPR || comp_code == LT_EXPR)
-	      && (INTEGRAL_TYPE_P (TREE_TYPE (val))
-		  || SCALAR_FLOAT_TYPE_P (TREE_TYPE (val))))
-	    {
-	      tree min = TYPE_MIN_VALUE (TREE_TYPE (val));
-	      tree max = TYPE_MAX_VALUE (TREE_TYPE (val));
+  /* If COND is effectively an equality test of an SSA_NAME against
+     the value zero or one, then we may be able to assert values
+     for SSA_NAMEs which flow into COND.  */
 
-	      if (comp_code == GT_EXPR && compare_values (val, max) == 0)
-		return false;
+  /* In the case of NAME == 1 or NAME != 0, for TRUTH_AND_EXPR defining
+     statement of NAME we can assert both operands of the TRUTH_AND_EXPR
+     have non-zero value.  */
+  if (((comp_code == EQ_EXPR && integer_onep (val))
+       || (comp_code == NE_EXPR && integer_zerop (val))))
+    {
+      tree def_stmt = SSA_NAME_DEF_STMT (name);
 
-	      if (comp_code == LT_EXPR && compare_values (val, min) == 0)
-		return false;
-	    }
+      if (TREE_CODE (def_stmt) == MODIFY_EXPR
+	  && (TREE_CODE (TREE_OPERAND (def_stmt, 1)) == TRUTH_AND_EXPR
+	      || TREE_CODE (TREE_OPERAND (def_stmt, 1)) == BIT_AND_EXPR))
+	{
+	  tree op0 = TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0);
+	  tree op1 = TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 1);
+	  retval |= register_edge_assert_for_1 (op0, NE_EXPR, e, si);
+	  retval |= register_edge_assert_for_1 (op1, NE_EXPR, e, si);
 	}
     }
-  else
+
+  /* In the case of NAME == 0 or NAME != 1, for TRUTH_OR_EXPR defining
+     statement of NAME we can assert both operands of the TRUTH_OR_EXPR
+     have zero value.  */
+  if (((comp_code == EQ_EXPR && integer_zerop (val))
+       || (comp_code == NE_EXPR && integer_onep (val))))
     {
-      /* FIXME.  Handle SWITCH_EXPR.  */
-      gcc_unreachable ();
+      tree def_stmt = SSA_NAME_DEF_STMT (name);
+
+      if (TREE_CODE (def_stmt) == MODIFY_EXPR
+	  && (TREE_CODE (TREE_OPERAND (def_stmt, 1)) == TRUTH_OR_EXPR
+	      || TREE_CODE (TREE_OPERAND (def_stmt, 1)) == BIT_IOR_EXPR))
+	{
+	  tree op0 = TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0);
+	  tree op1 = TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 1);
+	  retval |= register_edge_assert_for_1 (op0, EQ_EXPR, e, si);
+	  retval |= register_edge_assert_for_1 (op1, EQ_EXPR, e, si);
+	}
     }
 
-  register_new_assert_for (name, comp_code, val, NULL, e, si);
-  return true;
+  return retval;
 }
 
 
 static bool find_assert_locations (basic_block bb);
 
 /* Determine whether the outgoing edges of BB should receive an
-   ASSERT_EXPR for each of the operands of BB's last statement.  The
-   last statement of BB must be a COND_EXPR or a SWITCH_EXPR.
+   ASSERT_EXPR for each of the operands of BB's LAST statement.
+   The last statement of BB must be a COND_EXPR or a SWITCH_EXPR.
 
    If any of the sub-graphs rooted at BB have an interesting use of
    the predicate operands, an assert location node is added to the
    list of assertions for the corresponding operands.  */
 
 static bool
-find_conditional_asserts (basic_block bb)
+find_conditional_asserts (basic_block bb, tree last)
 {
   bool need_assert;
-  block_stmt_iterator last_si;
-  tree op, last;
+  block_stmt_iterator bsi;
+  tree op;
   edge_iterator ei;
   edge e;
   ssa_op_iter iter;
 
   need_assert = false;
-  last_si = bsi_last (bb);
-  last = bsi_stmt (last_si);
+  bsi = bsi_for_stmt (last);
 
   /* Look for uses of the operands in each of the sub-graphs
      rooted at BB.  We need to check each of the outgoing edges
@@ -2852,7 +3013,8 @@ find_conditional_asserts (basic_block bb)
       /* Register the necessary assertions for each operand in the
 	 conditional predicate.  */
       FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
-	need_assert |= register_edge_assert_for (op, e, last_si);
+	need_assert |= register_edge_assert_for (op, e, bsi,
+						 COND_EXPR_COND (last));
     }
 
   /* Finally, indicate that we have found the operands in the
@@ -3042,7 +3204,7 @@ find_assert_locations (basic_block bb)
       && TREE_CODE (last) == COND_EXPR
       && !fp_predicate (COND_EXPR_COND (last))
       && !ZERO_SSA_OPERANDS (last, SSA_OP_USE))
-    need_assert |= find_conditional_asserts (bb);
+    need_assert |= find_conditional_asserts (bb, last);
 
   /* Recurse into the dominator children of BB.  */
   for (son = first_dom_son (CDI_DOMINATORS, bb);