tree-if-conv.c (add_to_predicate_list): Check unconditionally that bb is always executed to early exit.

gcc/

	* tree-if-conv.c (add_to_predicate_list): Check unconditionally
	that bb is always executed to early exit. Use predicate of
	cd-equivalent block for join blocks if it exists.
	(if_convertible_loop_p_1): Recompute POST_DOMINATOR tree.
	(tree_if_conversion): Free post-dominance information.

gcc/testsuite/

	* gcc.dg/tree-ssa/ifc-cd.c: New test.

From-SVN: r217277

4 files changed, 70 insertions, 8 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 4677ae5..d3f061e 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,11 @@
+2014-11-10  Yuri Rumyantsev  <ysrumyan@gmail.com>
+
+	* tree-if-conv.c (add_to_predicate_list): Check unconditionally
+	that bb is always executed to early exit. Use predicate of
+	cd-equivalent block for join blocks if it exists.
+	(if_convertible_loop_p_1): Recompute POST_DOMINATOR tree.
+	(tree_if_conversion): Free post-dominance information.
+
 2014-11-09  Jason Merrill  <jason@redhat.com>
 
 	* config/i386/avx512vldqintrin.h (_mm256_broadcast_f32x2): __mmask8.
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 2c58186..cd04981 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,7 @@
+2014-11-10  Yuri Rumyantsev  <ysrumyan@gmail.com>
+
+	* gcc.dg/tree-ssa/ifc-cd.c: New test.
+
 2014-11-09  H.J. Lu  <hongjiu.lu@intel.com>
 
 	PR testsuite/63305
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ifc-cd.c b/gcc/testsuite/gcc.dg/tree-ssa/ifc-cd.c
new file mode 100644
index 0000000..8d45bba
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ifc-cd.c
@@ -0,0 +1,29 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -fdump-tree-ifcvt-details -ftree-loop-if-convert-stores" } */
+
+void foo (int *x1, int *x2, int *x3, int *x4, int *y)
+{
+  int i;
+  int a1, a2, a3, b1, b2;
+
+  for (i=0; i<128; i++)
+    {
+      a1 = x1[i];
+      a2 = x2[i];
+      a3 = x3[i];
+      y[i] = 0;
+      if (x4[i] == 0)
+	{
+	  b1 = a1 + 1;
+	  if (a2 > 0)
+	    b1++;
+	  a1++;
+	  if (a3 < 0)
+	    b1--;
+	  y[i] = b1;
+	}
+    }
+}
+
+/* { dg-final { scan-tree-dump-times "Use predicate of bb" 8 "ifcvt" } } */
+/* { dg-final { cleanup-tree-dump "ifcvt" } } */
diff --git a/gcc/tree-if-conv.c b/gcc/tree-if-conv.c
index d7e9b07..0e7a144 100644
--- a/gcc/tree-if-conv.c
+++ b/gcc/tree-if-conv.c
@@ -407,25 +407,44 @@ fold_build_cond_expr (tree type, tree cond, tree rhs, tree lhs)
 }
 
 /* Add condition NC to the predicate list of basic block BB.  LOOP is
-   the loop to be if-converted.  */
+   the loop to be if-converted. Use predicate of cd-equivalent block
+   for join bb if it exists: we call basic blocks bb1 and bb2 
+   cd-equivalent if they are executed under the same condition.  */
 
 static inline void
 add_to_predicate_list (struct loop *loop, basic_block bb, tree nc)
 {
   tree bc, *tp;
+  basic_block dom_bb;
 
   if (is_true_predicate (nc))
     return;
 
-  if (!is_predicated (bb))
-    {
-      /* If dominance tells us this basic block is always executed, don't
-	 record any predicates for it.  */
-      if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
-	return;
+  /* If dominance tells us this basic block is always executed,
+     don't record any predicates for it.  */
+  if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
+    return;
 
-      bc = nc;
+  dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
+  /* We use notion of cd equivalence to get simpler predicate for
+     join block, e.g. if join block has 2 predecessors with predicates
+     p1 & p2 and p1 & !p2, we'd like to get p1 for it instead of
+     p1 & p2 | p1 & !p2.  */
+  if (dom_bb != loop->header
+      && get_immediate_dominator (CDI_POST_DOMINATORS, dom_bb) == bb)
+    {
+      gcc_assert (flow_bb_inside_loop_p (loop, dom_bb));
+      bc = bb_predicate (dom_bb);
+      gcc_assert (!is_true_predicate (bc));
+      set_bb_predicate (bb, bc);
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "Use predicate of bb#%d for bb#%d\n",
+		 dom_bb->index, bb->index);
+      return;
     }
+
+  if (!is_predicated (bb))
+    bc = nc;
   else
     {
       bc = bb_predicate (bb);
@@ -1187,6 +1206,7 @@ if_convertible_loop_p_1 (struct loop *loop,
     return false;
 
   calculate_dominance_info (CDI_DOMINATORS);
+  calculate_dominance_info (CDI_POST_DOMINATORS);
 
   /* Allow statements that can be handled during if-conversion.  */
   ifc_bbs = get_loop_body_in_if_conv_order (loop);
@@ -2159,6 +2179,7 @@ tree_if_conversion (struct loop *loop)
       free (ifc_bbs);
       ifc_bbs = NULL;
     }
+  free_dominance_info (CDI_POST_DOMINATORS);
 
   return todo;
 }