--- a/gcc/tree-ssa-dce.c	Fri Feb 12 23:41:23 2010 +0900
+++ b/gcc/tree-ssa-dce.c	Mon May 24 12:47:05 2010 +0900
@@ -1,5 +1,5 @@
 /* Dead code elimination pass for the GNU compiler.
-   Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
+   Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
    Free Software Foundation, Inc.
    Contributed by Ben Elliston <bje@redhat.com>
    and Andrew MacLeod <amacleod@redhat.com>
@@ -47,17 +47,12 @@
 #include "system.h"
 #include "coretypes.h"
 #include "tm.h"
-#include "ggc.h"
-
-/* These RTL headers are needed for basic-block.h.  */
-#include "rtl.h"
-#include "tm_p.h"
-#include "hard-reg-set.h"
-#include "obstack.h"
-#include "basic-block.h"
 
 #include "tree.h"
 #include "diagnostic.h"
+#include "tree-pretty-print.h"
+#include "gimple-pretty-print.h"
+#include "basic-block.h"
 #include "tree-flow.h"
 #include "gimple.h"
 #include "tree-dump.h"
@@ -373,12 +368,15 @@
 
 /* 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 +388,12 @@
       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 +403,8 @@
       if (stmt && is_ctrl_stmt (stmt))
 	mark_stmt_necessary (stmt, true);
     }
+  if (!skipped)
+    SET_BIT (visited_control_parents, bb->index);
 }
 
 
@@ -459,7 +465,7 @@
 	          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 +474,7 @@
 	  {
 	    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 +659,7 @@
 	  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 +682,98 @@
 		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 predecestor 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 predecestor 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);
 		}
 	    }
 	}
@@ -917,27 +1001,6 @@
   return something_changed;
 }
 
-/* Find first live post dominator of BB.  */
-
-static basic_block
-get_live_post_dom (basic_block bb)
-{
-  basic_block post_dom_bb;
-
-
-  /* The post dominance info has to be up-to-date.  */
-  gcc_assert (dom_info_state (CDI_POST_DOMINATORS) == DOM_OK);
-
-  /* Get the immediate post dominator of bb.  */
-  post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
-  /* And look for first live one.  */
-  while (post_dom_bb != EXIT_BLOCK_PTR
-	 && !TEST_BIT (bb_contains_live_stmts, post_dom_bb->index))
-    post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, post_dom_bb);
-
-  return post_dom_bb;
-}
-
 /* Forward edge E to respective POST_DOM_BB and update PHIs.  */
 
 static edge
@@ -958,13 +1021,12 @@
   if (e2 != e)
     return e2;
 
-  if (phi_nodes (post_dom_bb))
+  if (!gimple_seq_empty_p (phi_nodes (post_dom_bb)))
     {
       /* We are sure that for every live PHI we are seeing control dependent BB.
-         This means that we can look up the end of control dependent path leading
-         to the PHI itself.  */
+         This means that we can pick any edge to duplicate PHI args from.  */
       FOR_EACH_EDGE (e2, ei, post_dom_bb->preds)
-	if (e2 != e && dominated_by_p (CDI_POST_DOMINATORS, e->src, e2->src))
+	if (e2 != e)
 	  break;
       for (gsi = gsi_start_phis (post_dom_bb); !gsi_end_p (gsi);)
 	{
@@ -972,40 +1034,27 @@
 	  tree op;
 	  source_location locus;
 
-	  /* Dead PHI do not imply control dependency.  */
-          if (!gimple_plf (phi, STMT_NECESSARY)
-	      && is_gimple_reg (gimple_phi_result (phi)))
-	    {
-	      gsi_next (&gsi);
-	      continue;
-	    }
-	  if (gimple_phi_arg_def (phi, e->dest_idx))
-	    {
-	      gsi_next (&gsi);
-	      continue;
-	    }
-
-	  /* We didn't find edge to update.  This can happen for PHIs on virtuals
-	     since there is no control dependency relation on them.  We are lost
-	     here and must force renaming of the symbol.  */
+	  /* PHIs for virtuals have no control dependency relation on them.
+	     We are lost here and must force renaming of the symbol.  */
 	  if (!is_gimple_reg (gimple_phi_result (phi)))
 	    {
 	      mark_virtual_phi_result_for_renaming (phi);
 	      remove_phi_node (&gsi, true);
 	      continue;
 	    }
-	  if (!e2)
+
+	  /* Dead PHI do not imply control dependency.  */
+          if (!gimple_plf (phi, STMT_NECESSARY))
 	    {
-	      op = gimple_phi_arg_def (phi, e->dest_idx == 0 ? 1 : 0);
-	      locus = gimple_phi_arg_location (phi, e->dest_idx == 0 ? 1 : 0);
+	      gsi_next (&gsi);
+	      continue;
 	    }
-	  else
-	    {
-	      op = gimple_phi_arg_def (phi, e2->dest_idx);
-	      locus = gimple_phi_arg_location (phi, e2->dest_idx);
-	    }
+
+	  op = gimple_phi_arg_def (phi, e2->dest_idx);
+	  locus = gimple_phi_arg_location (phi, e2->dest_idx);
 	  add_phi_arg (phi, op, e, locus);
-	  gcc_assert (e2 || degenerate_phi_p (phi));
+	  /* The resulting PHI if not dead can only be degenerate.  */
+	  gcc_assert (degenerate_phi_p (phi));
 	  gsi_next (&gsi);
 	}
     }
@@ -1041,7 +1090,7 @@
       edge e, e2;
       edge_iterator ei;
 
-      post_dom_bb = get_live_post_dom (bb);
+      post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
 
       e = find_edge (bb, post_dom_bb);