gcc/ChangeLog:

[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-dce.c

diff --git a/gcc/tree-ssa-dce.c b/gcc/tree-ssa-dce.c
index 2eec314..99a039f 100644 (file)
--- 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);
+                   }
+               }
            }
        }
     }