2009-09-03 Basile Starynkevitch <basile@starynkevitch.net>

	MELT branch merged with trunk rev 151367



git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/branches/melt-branch@151369 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 85 insertions, 13 deletions

diff --git a/gcc/tree-ssa-dce.c b/gcc/tree-ssa-dce.c
index 2eec3147886..99a039fffee 100644
--- a/gcc/tree-ssa-dce.c
+++ b/gcc/tree-ssa-dce.c
@@ -1,5 +1,5 @@
 /* Dead code elimination pass for the GNU compiler.
-   Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008
+   Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
    Free Software Foundation, Inc.
    Contributed by Ben Elliston <bje@redhat.com>
    and Andrew MacLeod <amacleod@redhat.com>
@@ -221,7 +221,7 @@ mark_stmt_necessary (gimple stmt, bool add_to_worklist)
   gimple_set_plf (stmt, STMT_NECESSARY, true);
   if (add_to_worklist)
     VEC_safe_push (gimple, heap, worklist, stmt);
-  if (bb_contains_live_stmts)
+  if (bb_contains_live_stmts && !is_gimple_debug (stmt))
     SET_BIT (bb_contains_live_stmts, gimple_bb (stmt)->index);
 }
 
@@ -333,6 +333,10 @@ mark_stmt_if_obviously_necessary (gimple stmt, bool aggressive)
 	}
       break;
 
+    case GIMPLE_DEBUG:
+      mark_stmt_necessary (stmt, false);
+      return;
+
     case GIMPLE_GOTO:
       gcc_assert (!simple_goto_p (stmt));
       mark_stmt_necessary (stmt, true);
@@ -1063,7 +1067,6 @@ remove_dead_stmt (gimple_stmt_iterator *i, basic_block bb)
   release_defs (stmt); 
 }
 
-
 /* Eliminate unnecessary statements. Any instruction not marked as necessary
    contributes nothing to the program, and can be deleted.  */
 
@@ -1075,16 +1078,44 @@ eliminate_unnecessary_stmts (void)
   gimple_stmt_iterator gsi;
   gimple stmt;
   tree call;
+  VEC (basic_block, heap) *h;
 
   if (dump_file && (dump_flags & TDF_DETAILS))
     fprintf (dump_file, "\nEliminating unnecessary statements:\n");
 
   clear_special_calls ();
 
-  FOR_EACH_BB (bb)
+  /* Walking basic blocks and statements in reverse order avoids
+     releasing SSA names before any other DEFs that refer to them are
+     released.  This helps avoid loss of debug information, as we get
+     a chance to propagate all RHSs of removed SSAs into debug uses,
+     rather than only the latest ones.  E.g., consider:
+
+     x_3 = y_1 + z_2;
+     a_5 = x_3 - b_4;
+     # DEBUG a => a_5
+
+     If we were to release x_3 before a_5, when we reached a_5 and
+     tried to substitute it into the debug stmt, we'd see x_3 there,
+     but x_3's DEF, type, etc would have already been disconnected.
+     By going backwards, the debug stmt first changes to:
+
+     # DEBUG a => x_3 - b_4
+
+     and then to:
+
+     # DEBUG a => y_1 + z_2 - b_4
+
+     as desired.  */
+  gcc_assert (dom_info_available_p (CDI_DOMINATORS));
+  h = get_all_dominated_blocks (CDI_DOMINATORS, single_succ (ENTRY_BLOCK_PTR));
+
+  while (VEC_length (basic_block, h))
     {
+      bb = VEC_pop (basic_block, h);
+
       /* Remove dead statements.  */
-      for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
+      for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
 	{
 	  stmt = gsi_stmt (gsi);
 
@@ -1095,6 +1126,14 @@ eliminate_unnecessary_stmts (void)
 	    {
 	      remove_dead_stmt (&gsi, bb);
 	      something_changed = true;
+
+	      /* If stmt was the last stmt in the block, we want to
+		 move gsi to the stmt that became the last stmt, but
+		 gsi_prev would crash.  */
+	      if (gsi_end_p (gsi))
+		gsi = gsi_last_bb (bb);
+	      else
+		gsi_prev (&gsi);
 	    }
 	  else if (is_gimple_call (stmt))
 	    {
@@ -1124,24 +1163,29 @@ eliminate_unnecessary_stmts (void)
 		    }
 		  notice_special_calls (stmt);
 		}
-	      gsi_next (&gsi);
+	      gsi_prev (&gsi);
 	    }
 	  else
-	    {
-	      gsi_next (&gsi);
-	    }
+	    gsi_prev (&gsi);
 	}
     }
+
+  VEC_free (basic_block, heap, h);
+
   /* Since we don't track liveness of virtual PHI nodes, it is possible that we
      rendered some PHI nodes unreachable while they are still in use.
      Mark them for renaming.  */
   if (cfg_altered)
     {
-      basic_block next_bb;
+      basic_block prev_bb;
+
       find_unreachable_blocks ();
-      for (bb = ENTRY_BLOCK_PTR->next_bb; bb != EXIT_BLOCK_PTR; bb = next_bb)
+
+      /* Delete all unreachable basic blocks in reverse dominator order.  */
+      for (bb = EXIT_BLOCK_PTR->prev_bb; bb != ENTRY_BLOCK_PTR; bb = prev_bb)
 	{
-	  next_bb = bb->next_bb;
+	  prev_bb = bb->prev_bb;
+
 	  if (!TEST_BIT (bb_contains_live_stmts, bb->index)
 	      || !(bb->flags & BB_REACHABLE))
 	    {
@@ -1165,8 +1209,36 @@ eliminate_unnecessary_stmts (void)
 		    if (found)
 		      mark_virtual_phi_result_for_renaming (gsi_stmt (gsi));
 		  }
+
 	      if (!(bb->flags & BB_REACHABLE))
-	        delete_basic_block (bb);
+		{
+		  /* Speed up the removal of blocks that don't
+		     dominate others.  Walking backwards, this should
+		     be the common case.  ??? Do we need to recompute
+		     dominators because of cfg_altered?  */
+		  if (!MAY_HAVE_DEBUG_STMTS
+		      || !first_dom_son (CDI_DOMINATORS, bb))
+		    delete_basic_block (bb);
+		  else
+		    {
+		      h = get_all_dominated_blocks (CDI_DOMINATORS, bb);
+
+		      while (VEC_length (basic_block, h))
+			{
+			  bb = VEC_pop (basic_block, h);
+			  prev_bb = bb->prev_bb;
+			  /* Rearrangements to the CFG may have failed
+			     to update the dominators tree, so that
+			     formerly-dominated blocks are now
+			     otherwise reachable.  */
+			  if (!!(bb->flags & BB_REACHABLE))
+			    continue;
+			  delete_basic_block (bb);
+			}
+
+		      VEC_free (basic_block, heap, h);
+		    }
+		}
 	    }
 	}
     }