tree-ssa-threadedge.c (simplify_control_stmt_condition): Split out into ...

2016-04-29  Patrick Palka  <ppalka@gcc.gnu.org>

	* tree-ssa-threadedge.c (simplify_control_stmt_condition): Split
	out into ...
	(simplify_control_stmt_condition_1): ... here.  Recurse into
	BIT_AND_EXPRs and BIT_IOR_EXPRs.

	* gcc.dg/tree-ssa/ssa-thread-14.c: New test.
	* gcc.dg/tree-ssa/ssa-thread-11.c: Update expected output.

From-SVN: r235653

5 files changed, 297 insertions, 46 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 1b06c04..e3458cc 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,10 @@
+2016-04-29  Patrick Palka  <ppalka@gcc.gnu.org>
+
+	* tree-ssa-threadedge.c (simplify_control_stmt_condition): Split
+	out into ...
+	(simplify_control_stmt_condition_1): ... here.  Recurse into
+	BIT_AND_EXPRs and BIT_IOR_EXPRs.
+
 2016-04-29  David Edelsohn  <dje.gcc@gmail.com>
 
 	PR target/69810
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index addef50..0d0f252 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,8 @@
+2016-04-29  Patrick Palka  <ppalka@gcc.gnu.org>
+
+	* gcc.dg/tree-ssa/ssa-thread-14.c: New test.
+	* gcc.dg/tree-ssa/ssa-thread-11.c: Update expected output.
+
 2016-04-29  Cesar Philippidis  <cesar@codesourcery.com>
 
 	PR middle-end/70626
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-11.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-11.c
index a729f56..d28a0eb 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-11.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-11.c
@@ -1,7 +1,6 @@
 /* { dg-do compile { target { ! { logical_op_short_circuit || { m68k*-*-* mep*-*-* bfin*-*-* v850*-*-* moxie*-*-* m32c*-*-* fr30*-*-* mcore*-*-* frv-*-* h8300-*-* m32r-*-* mn10300-*-* msp430-*-* pdp11-*-* rl78-*-* rx-*-* vax-*-*} } } } } */
 /* { dg-options "-O2 -fdump-tree-vrp2-details" } */
 /* { dg-final { scan-tree-dump-not "IRREDUCIBLE_LOOP" "vrp2" } } */
-/* { dg-final { scan-tree-dump "FSM" "vrp2" } } */
 
 void abort (void);
 typedef struct bitmap_head_def *bitmap;
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-14.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-14.c
new file mode 100644
index 0000000..db9ed3b
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-14.c
@@ -0,0 +1,81 @@
+/* { dg-do compile }  */
+/* { dg-additional-options "-O2 -fdump-tree-vrp" }  */
+/* { dg-final { scan-tree-dump-times "Threaded jump" 8 "vrp1" } }  */
+
+void foo (void);
+void bar (void);
+void blah (void);
+
+/* One jump threaded here.  */
+
+void
+baz_1 (int a, int b, int c)
+{
+  if (a && b)
+    foo ();
+  if (!b && c)
+    bar ();
+}
+
+/* One jump threaded here.  */
+
+void
+baz_2 (int a, int b, int c)
+{
+  if (a && b)
+    foo ();
+  if (b || c)
+    bar ();
+}
+
+/* One jump threaded here.  */
+
+void
+baz_3 (int a, int b, int c)
+{
+  if (a && b > 10)
+    foo ();
+  if (b < 5 && c)
+    bar ();
+}
+
+/* Two jumps threaded here.  */
+
+void
+baz_4 (int a, int b, int c)
+{
+  if (a && b)
+    {
+      foo ();
+      if (c)
+        bar ();
+    }
+  if (b && c)
+    blah ();
+}
+
+/* Two jumps threaded here.  */
+
+void
+baz_5 (int a, int b, int c)
+{
+  if (a && b)
+    {
+      foo ();
+      if (c)
+        bar ();
+    }
+  if (!b || !c)
+    blah ();
+}
+
+/* One jump threaded here.  */
+
+void
+baz_6 (int a, int b, int c)
+{
+  if (a == 39 && b == 41)
+    foo ();
+  if (c == 12 || b == 41)
+    bar ();
+}
diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c
index f60be38..eca3812 100644
--- a/gcc/tree-ssa-threadedge.c
+++ b/gcc/tree-ssa-threadedge.c
@@ -376,6 +376,12 @@ record_temporary_equivalences_from_stmts_at_dest (edge e,
   return stmt;
 }
 
+static tree simplify_control_stmt_condition_1 (edge, gimple *,
+					       class avail_exprs_stack *,
+					       tree, enum tree_code, tree,
+					       gcond *, pfn_simplify, bool,
+					       unsigned);
+
 /* Simplify the control statement at the end of the block E->dest.
 
    To avoid allocating memory unnecessarily, a scratch GIMPLE_COND
@@ -436,52 +442,14 @@ simplify_control_stmt_condition (edge e,
 	    }
 	}
 
-      if (handle_dominating_asserts)
-	{
-	  /* Now see if the operand was consumed by an ASSERT_EXPR
-	     which dominates E->src.  If so, we want to replace the
-	     operand with the LHS of the ASSERT_EXPR.  */
-	  if (TREE_CODE (op0) == SSA_NAME)
-	    op0 = lhs_of_dominating_assert (op0, e->src, stmt);
-
-	  if (TREE_CODE (op1) == SSA_NAME)
-	    op1 = lhs_of_dominating_assert (op1, e->src, stmt);
-	}
-
-      /* We may need to canonicalize the comparison.  For
-	 example, op0 might be a constant while op1 is an
-	 SSA_NAME.  Failure to canonicalize will cause us to
-	 miss threading opportunities.  */
-      if (tree_swap_operands_p (op0, op1, false))
-	{
-	  cond_code = swap_tree_comparison (cond_code);
-	  std::swap (op0, op1);
-	}
+      const unsigned recursion_limit = 4;
 
-      /* Stuff the operator and operands into our dummy conditional
-	 expression.  */
-      gimple_cond_set_code (dummy_cond, cond_code);
-      gimple_cond_set_lhs (dummy_cond, op0);
-      gimple_cond_set_rhs (dummy_cond, op1);
-
-      /* We absolutely do not care about any type conversions
-         we only care about a zero/nonzero value.  */
-      fold_defer_overflow_warnings ();
-
-      cached_lhs = fold_binary (cond_code, boolean_type_node, op0, op1);
-      if (cached_lhs)
-	while (CONVERT_EXPR_P (cached_lhs))
-          cached_lhs = TREE_OPERAND (cached_lhs, 0);
-
-      fold_undefer_overflow_warnings ((cached_lhs
-                                       && is_gimple_min_invariant (cached_lhs)),
-				      stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
-
-      /* If we have not simplified the condition down to an invariant,
-	 then use the pass specific callback to simplify the condition.  */
-      if (!cached_lhs
-          || !is_gimple_min_invariant (cached_lhs))
-        cached_lhs = (*simplify) (dummy_cond, stmt, avail_exprs_stack);
+      cached_lhs
+	= simplify_control_stmt_condition_1 (e, stmt, avail_exprs_stack,
+					     op0, cond_code, op1,
+					     dummy_cond, simplify,
+					     handle_dominating_asserts,
+					     recursion_limit);
 
       /* If we were testing an integer/pointer against a constant, then
 	 we can use the FSM code to trace the value of the SSA_NAME.  If
@@ -560,6 +528,197 @@ simplify_control_stmt_condition (edge e,
   return cached_lhs;
 }
 
+/* Recursive helper for simplify_control_stmt_condition.  */
+
+static tree
+simplify_control_stmt_condition_1 (edge e,
+				   gimple *stmt,
+				   class avail_exprs_stack *avail_exprs_stack,
+				   tree op0,
+				   enum tree_code cond_code,
+				   tree op1,
+				   gcond *dummy_cond,
+				   pfn_simplify simplify,
+				   bool handle_dominating_asserts,
+				   unsigned limit)
+{
+  if (limit == 0)
+    return NULL_TREE;
+
+  /* We may need to canonicalize the comparison.  For
+     example, op0 might be a constant while op1 is an
+     SSA_NAME.  Failure to canonicalize will cause us to
+     miss threading opportunities.  */
+  if (tree_swap_operands_p (op0, op1, false))
+    {
+      cond_code = swap_tree_comparison (cond_code);
+      std::swap (op0, op1);
+    }
+
+  /* If the condition has the form (A & B) CMP 0 or (A | B) CMP 0 then
+     recurse into the LHS to see if there is a dominating ASSERT_EXPR
+     of A or of B that makes this condition always true or always false
+     along the edge E.  */
+  if (handle_dominating_asserts
+      && (cond_code == EQ_EXPR || cond_code == NE_EXPR)
+      && TREE_CODE (op0) == SSA_NAME
+      && integer_zerop (op1))
+    {
+      gimple *def_stmt = SSA_NAME_DEF_STMT (op0);
+      if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
+        ;
+      else if (gimple_assign_rhs_code (def_stmt) == BIT_AND_EXPR
+	       || gimple_assign_rhs_code (def_stmt) == BIT_IOR_EXPR)
+	{
+	  enum tree_code rhs_code = gimple_assign_rhs_code (def_stmt);
+	  const tree rhs1 = gimple_assign_rhs1 (def_stmt);
+	  const tree rhs2 = gimple_assign_rhs2 (def_stmt);
+	  const tree zero_cst = build_zero_cst (TREE_TYPE (op0));
+	  const tree one_cst = build_one_cst (TREE_TYPE (op0));
+
+	  /* Is A != 0 ?  */
+	  const tree res1
+	    = simplify_control_stmt_condition_1 (e, def_stmt, avail_exprs_stack,
+						 rhs1, NE_EXPR, op1,
+						 dummy_cond, simplify,
+						 handle_dominating_asserts,
+						 limit - 1);
+	  if (res1 == NULL_TREE)
+	    ;
+	  else if (rhs_code == BIT_AND_EXPR && integer_zerop (res1))
+	    {
+	      /* If A == 0 then (A & B) != 0 is always false.  */
+	      if (cond_code == NE_EXPR)
+	        return zero_cst;
+	      /* If A == 0 then (A & B) == 0 is always true.  */
+	      if (cond_code == EQ_EXPR)
+		return one_cst;
+	    }
+	  else if (rhs_code == BIT_IOR_EXPR && integer_nonzerop (res1))
+	    {
+	      /* If A != 0 then (A | B) != 0 is always true.  */
+	      if (cond_code == NE_EXPR)
+		return one_cst;
+	      /* If A != 0 then (A | B) == 0 is always false.  */
+	      if (cond_code == EQ_EXPR)
+		return zero_cst;
+	    }
+
+	  /* Is B != 0 ?  */
+	  const tree res2
+	    = simplify_control_stmt_condition_1 (e, def_stmt, avail_exprs_stack,
+						 rhs2, NE_EXPR, op1,
+						 dummy_cond, simplify,
+						 handle_dominating_asserts,
+						 limit - 1);
+	  if (res2 == NULL_TREE)
+	    ;
+	  else if (rhs_code == BIT_AND_EXPR && integer_zerop (res2))
+	    {
+	      /* If B == 0 then (A & B) != 0 is always false.  */
+	      if (cond_code == NE_EXPR)
+	        return zero_cst;
+	      /* If B == 0 then (A & B) == 0 is always true.  */
+	      if (cond_code == EQ_EXPR)
+		return one_cst;
+	    }
+	  else if (rhs_code == BIT_IOR_EXPR && integer_nonzerop (res2))
+	    {
+	      /* If B != 0 then (A | B) != 0 is always true.  */
+	      if (cond_code == NE_EXPR)
+		return one_cst;
+	      /* If B != 0 then (A | B) == 0 is always false.  */
+	      if (cond_code == EQ_EXPR)
+		return zero_cst;
+	    }
+
+	  if (res1 != NULL_TREE && res2 != NULL_TREE)
+	    {
+	      if (rhs_code == BIT_AND_EXPR
+		  && TYPE_PRECISION (TREE_TYPE (op0)) == 1
+		  && integer_nonzerop (res1)
+		  && integer_nonzerop (res2))
+		{
+		  /* If A != 0 and B != 0 then (bool)(A & B) != 0 is true.  */
+		  if (cond_code == NE_EXPR)
+		    return one_cst;
+		  /* If A != 0 and B != 0 then (bool)(A & B) == 0 is false.  */
+		  if (cond_code == EQ_EXPR)
+		    return zero_cst;
+		}
+
+	      if (rhs_code == BIT_IOR_EXPR
+		  && integer_zerop (res1)
+		  && integer_zerop (res2))
+		{
+		  /* If A == 0 and B == 0 then (A | B) != 0 is false.  */
+		  if (cond_code == NE_EXPR)
+		    return zero_cst;
+		  /* If A == 0 and B == 0 then (A | B) == 0 is true.  */
+		  if (cond_code == EQ_EXPR)
+		    return one_cst;
+		}
+	    }
+	}
+      /* Handle (A CMP B) CMP 0.  */
+      else if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt))
+	       == tcc_comparison)
+	{
+	  tree rhs1 = gimple_assign_rhs1 (def_stmt);
+	  tree rhs2 = gimple_assign_rhs2 (def_stmt);
+
+	  tree_code new_cond = gimple_assign_rhs_code (def_stmt);
+	  if (cond_code == EQ_EXPR)
+	    new_cond = invert_tree_comparison (new_cond, false);
+
+	  tree res
+	    = simplify_control_stmt_condition_1 (e, def_stmt, avail_exprs_stack,
+						 rhs1, new_cond, rhs2,
+						 dummy_cond, simplify,
+						 handle_dominating_asserts,
+						 limit - 1);
+	  if (res != NULL_TREE && is_gimple_min_invariant (res))
+	    return res;
+	}
+    }
+
+  if (handle_dominating_asserts)
+    {
+      /* Now see if the operand was consumed by an ASSERT_EXPR
+	 which dominates E->src.  If so, we want to replace the
+	 operand with the LHS of the ASSERT_EXPR.  */
+      if (TREE_CODE (op0) == SSA_NAME)
+	op0 = lhs_of_dominating_assert (op0, e->src, stmt);
+
+      if (TREE_CODE (op1) == SSA_NAME)
+	op1 = lhs_of_dominating_assert (op1, e->src, stmt);
+    }
+
+  gimple_cond_set_code (dummy_cond, cond_code);
+  gimple_cond_set_lhs (dummy_cond, op0);
+  gimple_cond_set_rhs (dummy_cond, op1);
+
+  /* We absolutely do not care about any type conversions
+     we only care about a zero/nonzero value.  */
+  fold_defer_overflow_warnings ();
+
+  tree res = fold_binary (cond_code, boolean_type_node, op0, op1);
+  if (res)
+    while (CONVERT_EXPR_P (res))
+      res = TREE_OPERAND (res, 0);
+
+  fold_undefer_overflow_warnings ((res && is_gimple_min_invariant (res)),
+				  stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
+
+  /* If we have not simplified the condition down to an invariant,
+     then use the pass specific callback to simplify the condition.  */
+  if (!res
+      || !is_gimple_min_invariant (res))
+    res = (*simplify) (dummy_cond, stmt, avail_exprs_stack);
+
+  return res;
+}
+
 /* Copy debug stmts from DEST's chain of single predecessors up to
    SRC, so that we don't lose the bindings as PHI nodes are introduced
    when DEST gains new predecessors.  */