Re: PR middle-end 42906 (empty loops not removed when leaved via critical edge with PHI node attached)

[Jan Hubicka <hubicka at ucw dot cz>]

Hi,
this is vairant I comitted.  It updates comment to be less confusing about
critical edges and fixes typo in the testcase.

Index: ChangeLog
===================================================================
--- ChangeLog	(revision 158003)
+++ ChangeLog	(working copy)
@@ -1,3 +1,13 @@
+2010-04-06  Jan Hubicka  <jh@suse.czpli
+
+	PR tree-optimization/42906
+
+	* tree-ssa-dce.c (mark_control_dependent_edges_necessary): Add IGNORE_SELF
+	argument; set visited_control_parents for fully processed BBs.
+	(find_obviously_necessary_stmts): Update call of
+	mark_control_dependent_edges_necessary.
+	(propagate_necessity): Likewise; handle PHI edges more curefully.
+
 2010-04-06  Uros Bizjak  <ubizjak@gmail.com>
 
 	* config/i386/i386.md: Remove comment about 'e' and 'E'
Index: testsuite/gcc.dg/tree-ssa/dce-1.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/dce-1.c	(revision 0)
+++ testsuite/gcc.dg/tree-ssa/dce-1.c	(revision 0)
@@ -0,0 +1,19 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-cddce1" } */
+int foo (int b, int j)
+{
+  if (b)
+    {
+      int i;
+      for (i = 0; i<1000; ++i)
+        ;
+      j = 0;
+    }
+  return j;
+}
+/* Check that empty loop is eliminated in this case.  We should no longer have
+   the exit condition after the loop.  */
+/* { dg-final { scan-tree-dump-not "999" "cddce1"} } */
+/* { dg-final { scan-tree-dump-not "1000" "cddce1"} } */
+/* { dg-final { cleanup-tree-dump "cddce1" } } */
+
Index: testsuite/ChangeLog
===================================================================
--- testsuite/ChangeLog	(revision 158003)
+++ testsuite/ChangeLog	(working copy)
@@ -1,3 +1,7 @@
+2010-04-06  Jan Hubicka  <jh@suse.czpli
+
+	PR tree-optimization/42906
+	* gcc.dg/tree-ssa/dce-1.c: New testcase.
 2010-04-06  Tobias Burnus  <burnus@net-b.de>
 
 	PR fortran/43178
Index: tree-ssa-dce.c
===================================================================
--- tree-ssa-dce.c	(revision 158003)
+++ tree-ssa-dce.c	(working copy)
@@ -373,12 +373,15 @@ mark_stmt_if_obviously_necessary (gimple
 
 /* Make corresponding control dependent edges necessary.  We only
    have to do this once for each basic block, so we clear the bitmap
-   after we're done.  */
+   after we're done.
+
+   When IGNORE_SELF it true, ignore BB from the list of control dependences.  */
 static void
-mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el)
+mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el, bool ignore_self)
 {
   bitmap_iterator bi;
   unsigned edge_number;
+  bool skipped = false;
 
   gcc_assert (bb != EXIT_BLOCK_PTR);
 
@@ -390,6 +393,12 @@ mark_control_dependent_edges_necessary (
       gimple stmt;
       basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number);
 
+      if (ignore_self && cd_bb == bb)
+	{
+	  skipped = true;
+	  continue;
+	}
+
       if (TEST_BIT (last_stmt_necessary, cd_bb->index))
 	continue;
       SET_BIT (last_stmt_necessary, cd_bb->index);
@@ -399,6 +408,8 @@ mark_control_dependent_edges_necessary (
       if (stmt && is_ctrl_stmt (stmt))
 	mark_stmt_necessary (stmt, true);
     }
+  if (!skipped)
+    SET_BIT (visited_control_parents, bb->index);
 }
 
 
@@ -459,7 +470,7 @@ find_obviously_necessary_stmts (struct e
 	          if (dump_file)
 	            fprintf (dump_file, "Marking back edge of irreducible loop %i->%i\n",
 		    	     e->src->index, e->dest->index);
-		  mark_control_dependent_edges_necessary (e->dest, el);
+		  mark_control_dependent_edges_necessary (e->dest, el, false);
 		}
 	  }
 
@@ -468,7 +479,7 @@ find_obviously_necessary_stmts (struct e
 	  {
 	    if (dump_file)
 	      fprintf (dump_file, "can not prove finiteness of loop %i\n", loop->num);
-	    mark_control_dependent_edges_necessary (loop->latch, el);
+	    mark_control_dependent_edges_necessary (loop->latch, el, false);
 	  }
       scev_finalize ();
     }
@@ -653,10 +664,7 @@ propagate_necessity (struct edge_list *e
 	  basic_block bb = gimple_bb (stmt);
 	  if (bb != ENTRY_BLOCK_PTR
 	      && ! TEST_BIT (visited_control_parents, bb->index))
-	    {
-	      SET_BIT (visited_control_parents, bb->index);
-	      mark_control_dependent_edges_necessary (bb, el);
-	    }
+	    mark_control_dependent_edges_necessary (bb, el, false);
 	}
 
       if (gimple_code (stmt) == GIMPLE_PHI
@@ -679,17 +687,98 @@ propagate_necessity (struct edge_list *e
 		mark_operand_necessary (arg);
 	    }
 
+	  /* For PHI operands it matters from where the control flow arrives
+	     to the BB.  Consider the following example:
+
+	     a=exp1;
+	     b=exp2;
+	     if (test)
+		;
+	     else
+		;
+	     c=PHI(a,b)
+
+	     We need to mark control dependence of the empty basic blocks, since they
+	     contains computation of PHI operands.
+
+	     Doing so is too restrictive in the case the predecessor block is in
+	     the loop. Consider:
+
+	      if (b)
+		{
+		  int i;
+		  for (i = 0; i<1000; ++i)
+		    ;
+		  j = 0;
+		}
+	      return j;
+
+	     There is PHI for J in the BB containing return statement.
+	     In this case the control dependence of predecessor block (that is
+	     within the empty loop) also contains the block determining number
+	     of iterations of the block that would prevent removing of empty
+	     loop in this case.
+
+	     This scenario can be avoided by splitting critical edges.
+	     To save the critical edge splitting pass we identify how the control
+	     dependence would look like if the edge was split.
+
+	     Consider the modified CFG created from current CFG by splitting
+	     edge B->C.  In the postdominance tree of modified CFG, C' is
+	     always child of C.  There are two cases how chlids of C' can look
+	     like:
+
+		1) C' is leaf
+
+		   In this case the only basic block C' is control dependent on is B.
+
+		2) C' has single child that is B
+
+		   In this case control dependence of C' is same as control
+		   dependence of B in original CFG except for block B itself.
+		   (since C' postdominate B in modified CFG)
+
+	     Now how to decide what case happens?  There are two basic options:
+
+		a) C postdominate B.  Then C immediately postdominate B and
+		   case 2 happens iff there is no other way from B to C except
+		   the edge B->C.
+
+		   There is other way from B to C iff there is succesor of B that
+		   is not postdominated by B.  Testing this condition is somewhat
+		   expensive, because we need to iterate all succesors of B.
+		   We are safe to assume that this does not happen: we will mark B
+		   as needed when processing the other path from B to C that is
+		   conrol dependent on B and marking control dependencies of B
+		   itself is harmless because they will be processed anyway after
+		   processing control statement in B.
+
+		b) C does not postdominate B.  Always case 1 happens since there is
+		   path from C to exit that does not go through B and thus also C'.  */
+
 	  if (aggressive && !degenerate_phi_p (stmt))
 	    {
 	      for (k = 0; k < gimple_phi_num_args (stmt); k++)
 		{
 		  basic_block arg_bb = gimple_phi_arg_edge (stmt, k)->src;
-		  if (arg_bb != ENTRY_BLOCK_PTR
-		      && ! TEST_BIT (visited_control_parents, arg_bb->index))
+
+		  if (gimple_bb (stmt)
+		      != get_immediate_dominator (CDI_POST_DOMINATORS, arg_bb))
 		    {
-		      SET_BIT (visited_control_parents, arg_bb->index);
-		      mark_control_dependent_edges_necessary (arg_bb, el);
+		      if (!TEST_BIT (last_stmt_necessary, arg_bb->index))
+			{
+			  gimple stmt2;
+			  SET_BIT (last_stmt_necessary, arg_bb->index);
+			  SET_BIT (bb_contains_live_stmts, arg_bb->index);
+
+			  stmt2 = last_stmt (arg_bb);
+			  if (stmt2 && is_ctrl_stmt (stmt2))
+			    mark_stmt_necessary (stmt2, true);
+			}
 		    }
+		  else if (arg_bb != ENTRY_BLOCK_PTR
+		           && ! TEST_BIT (visited_control_parents, arg_bb->index))
+		    mark_control_dependent_edges_necessary (arg_bb, el, true);
 		}
 	    }
 	}