[gcc] GCC 4.5.0=>4.5.1

gcc/gcc/tree-ssa-dce.c

Index: gcc/gcc/tree-ssa-dce.c
diff --git a/gcc/gcc/tree-ssa-dce.c b/gcc/gcc/tree-ssa-dce.c
index 3c7504696826f9411e0426469cb790a0b01e2882..f54511c5741b3b6470a717860c07962f15268f24 100644
--- a/gcc/gcc/tree-ssa-dce.c
+++ b/gcc/gcc/tree-ssa-dce.c
@@ -1,22 +1,22 @@
 /* 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, 2010
    Free Software Foundation, Inc.
    Contributed by Ben Elliston <bje@redhat.com>
    and Andrew MacLeod <amacleod@redhat.com>
    Adapted to use control dependence by Steven Bosscher, SUSE Labs.
- 
+
 This file is part of GCC.
-   
+
 GCC is free software; you can redistribute it and/or modify it
 under the terms of the GNU General Public License as published by the
 Free Software Foundation; either version 3, or (at your option) any
 later version.
-   
+
 GCC is distributed in the hope that it will be useful, but WITHOUT
 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 for more details.
-   
+
 You should have received a copy of the GNU General Public License
 along with GCC; see the file COPYING3.  If not see
 <http://www.gnu.org/licenses/>.  */
@@ -87,6 +87,9 @@ static sbitmap processed;
    marked as necessary.  */
 static sbitmap last_stmt_necessary;
 
+/* Vector indicating that BB contains statements that are live.  */
+static sbitmap bb_contains_live_stmts;
+
 /* Before we can determine whether a control branch is dead, we need to
    compute which blocks are control dependent on which edges.
 
@@ -218,6 +221,8 @@ 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 && !is_gimple_debug (stmt))
+    SET_BIT (bb_contains_live_stmts, gimple_bb (stmt)->index);
 }
 
 
@@ -233,7 +238,12 @@ mark_operand_necessary (tree op)
 
   ver = SSA_NAME_VERSION (op);
   if (TEST_BIT (processed, ver))
-    return;
+    {
+      stmt = SSA_NAME_DEF_STMT (op);
+      gcc_assert (gimple_nop_p (stmt)
+		  || gimple_plf (stmt, STMT_NECESSARY));
+      return;
+    }
   SET_BIT (processed, ver);
 
   stmt = SSA_NAME_DEF_STMT (op);
@@ -242,7 +252,17 @@ mark_operand_necessary (tree op)
   if (gimple_plf (stmt, STMT_NECESSARY) || gimple_nop_p (stmt))
     return;
 
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "marking necessary through ");
+      print_generic_expr (dump_file, op, 0);
+      fprintf (dump_file, " stmt ");
+      print_gimple_stmt (dump_file, stmt, 0, 0);
+    }
+
   gimple_set_plf (stmt, STMT_NECESSARY, true);
+  if (bb_contains_live_stmts)
+    SET_BIT (bb_contains_live_stmts, gimple_bb (stmt)->index);
   VEC_safe_push (gimple, heap, worklist, stmt);
 }
 
@@ -282,7 +302,6 @@ mark_stmt_if_obviously_necessary (gimple stmt, bool aggressive)
     case GIMPLE_ASM:
     case GIMPLE_RESX:
     case GIMPLE_RETURN:
-    case GIMPLE_CHANGE_DYNAMIC_TYPE:
       mark_stmt_necessary (stmt, true);
       return;
 
@@ -303,17 +322,18 @@ mark_stmt_if_obviously_necessary (gimple stmt, bool aggressive)
     case GIMPLE_ASSIGN:
       if (!lhs)
         lhs = gimple_assign_lhs (stmt);
-      /* These values are mildly magic bits of the EH runtime.  We can't
-	 see the entire lifetime of these values until landing pads are
-	 generated.  */
-      if (TREE_CODE (lhs) == EXC_PTR_EXPR
-	  || TREE_CODE (lhs) == FILTER_EXPR)
-	{
-	  mark_stmt_necessary (stmt, true);
-	  return;
-	}
       break;
 
+    case GIMPLE_DEBUG:
+      /* Debug temps without a value are not useful.  ??? If we could
+	 easily locate the debug temp bind stmt for a use thereof,
+	 would could refrain from marking all debug temps here, and
+	 mark them only if they're used.  */
+      if (gimple_debug_bind_has_value_p (stmt)
+	  || TREE_CODE (gimple_debug_bind_get_var (stmt)) != DEBUG_EXPR_DECL)
+	mark_stmt_necessary (stmt, false);
+      return;
+
     case GIMPLE_GOTO:
       gcc_assert (!simple_goto_p (stmt));
       mark_stmt_necessary (stmt, true);
@@ -373,6 +393,7 @@ mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el)
       if (TEST_BIT (last_stmt_necessary, cd_bb->index))
 	continue;
       SET_BIT (last_stmt_necessary, cd_bb->index);
+      SET_BIT (bb_contains_live_stmts, cd_bb->index);
 
       stmt = last_stmt (cd_bb);
       if (stmt && is_ctrl_stmt (stmt))
@@ -414,25 +435,192 @@ find_obviously_necessary_stmts (struct edge_list *el)
 	}
     }
 
+  /* Pure and const functions are finite and thus have no infinite loops in
+     them.  */
+  if ((TREE_READONLY (current_function_decl)
+       || DECL_PURE_P (current_function_decl))
+      && !DECL_LOOPING_CONST_OR_PURE_P (current_function_decl))
+    return;
+
+  /* Prevent the empty possibly infinite loops from being removed.  */
   if (el)
     {
-      /* Prevent the loops from being removed.  We must keep the infinite loops,
-	 and we currently do not have a means to recognize the finite ones.  */
-      FOR_EACH_BB (bb)
+      loop_iterator li;
+      struct loop *loop;
+      scev_initialize ();
+      if (mark_irreducible_loops ())
+	FOR_EACH_BB (bb)
+	  {
+	    edge_iterator ei;
+	    FOR_EACH_EDGE (e, ei, bb->succs)
+	      if ((e->flags & EDGE_DFS_BACK)
+		  && (e->flags & EDGE_IRREDUCIBLE_LOOP))
+		{
+	          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);
+		}
+	  }
+
+      FOR_EACH_LOOP (li, loop, 0)
+	if (!finite_loop_p (loop))
+	  {
+	    if (dump_file)
+	      fprintf (dump_file, "can not prove finiteness of loop %i\n", loop->num);
+	    mark_control_dependent_edges_necessary (loop->latch, el);
+	  }
+      scev_finalize ();
+    }
+}
+
+
+/* Return true if REF is based on an aliased base, otherwise false.  */
+
+static bool
+ref_may_be_aliased (tree ref)
+{
+  while (handled_component_p (ref))
+    ref = TREE_OPERAND (ref, 0);
+  return !(DECL_P (ref)
+	   && !may_be_aliased (ref));
+}
+
+static bitmap visited = NULL;
+static unsigned int longest_chain = 0;
+static unsigned int total_chain = 0;
+static unsigned int nr_walks = 0;
+static bool chain_ovfl = false;
+
+/* Worker for the walker that marks reaching definitions of REF,
+   which is based on a non-aliased decl, necessary.  It returns
+   true whenever the defining statement of the current VDEF is
+   a kill for REF, as no dominating may-defs are necessary for REF
+   anymore.  DATA points to the basic-block that contains the
+   stmt that refers to REF.  */
+
+static bool
+mark_aliased_reaching_defs_necessary_1 (ao_ref *ref, tree vdef, void *data)
+{
+  gimple def_stmt = SSA_NAME_DEF_STMT (vdef);
+
+  /* All stmts we visit are necessary.  */
+  mark_operand_necessary (vdef);
+
+  /* If the stmt lhs kills ref, then we can stop walking.  */
+  if (gimple_has_lhs (def_stmt)
+      && TREE_CODE (gimple_get_lhs (def_stmt)) != SSA_NAME)
+    {
+      tree base, lhs = gimple_get_lhs (def_stmt);
+      HOST_WIDE_INT size, offset, max_size;
+      ao_ref_base (ref);
+      base = get_ref_base_and_extent (lhs, &offset, &size, &max_size);
+      /* We can get MEM[symbol: sZ, index: D.8862_1] here,
+	 so base == refd->base does not always hold.  */
+      if (base == ref->base)
 	{
-	  edge_iterator ei;
-	  FOR_EACH_EDGE (e, ei, bb->succs)
-	    if (e->flags & EDGE_DFS_BACK)
-	      mark_control_dependent_edges_necessary (e->dest, el);
+	  /* For a must-alias check we need to be able to constrain
+	     the accesses properly.  */
+	  if (size != -1 && size == max_size
+	      && ref->max_size != -1)
+	    {
+	      if (offset <= ref->offset
+		  && offset + size >= ref->offset + ref->max_size)
+		return true;
+	    }
+	  /* Or they need to be exactly the same.  */
+	  else if (ref->ref
+		   /* Make sure there is no induction variable involved
+		      in the references (gcc.c-torture/execute/pr42142.c).
+		      The simplest way is to check if the kill dominates
+		      the use.  */
+		   && dominated_by_p (CDI_DOMINATORS, (basic_block) data,
+				      gimple_bb (def_stmt))
+		   && operand_equal_p (ref->ref, lhs, 0))
+	    return true;
 	}
     }
+
+  /* Otherwise keep walking.  */
+  return false;
 }
 
+static void
+mark_aliased_reaching_defs_necessary (gimple stmt, tree ref)
+{
+  unsigned int chain;
+  ao_ref refd;
+  gcc_assert (!chain_ovfl);
+  ao_ref_init (&refd, ref);
+  chain = walk_aliased_vdefs (&refd, gimple_vuse (stmt),
+			      mark_aliased_reaching_defs_necessary_1,
+			      gimple_bb (stmt), NULL);
+  if (chain > longest_chain)
+    longest_chain = chain;
+  total_chain += chain;
+  nr_walks++;
+}
+
+/* Worker for the walker that marks reaching definitions of REF, which
+   is not based on a non-aliased decl.  For simplicity we need to end
+   up marking all may-defs necessary that are not based on a non-aliased
+   decl.  The only job of this walker is to skip may-defs based on
+   a non-aliased decl.  */
+
+static bool
+mark_all_reaching_defs_necessary_1 (ao_ref *ref ATTRIBUTE_UNUSED,
+				    tree vdef, void *data ATTRIBUTE_UNUSED)
+{
+  gimple def_stmt = SSA_NAME_DEF_STMT (vdef);
+
+  /* We have to skip already visited (and thus necessary) statements
+     to make the chaining work after we dropped back to simple mode.  */
+  if (chain_ovfl
+      && TEST_BIT (processed, SSA_NAME_VERSION (vdef)))
+    {
+      gcc_assert (gimple_nop_p (def_stmt)
+		  || gimple_plf (def_stmt, STMT_NECESSARY));
+      return false;
+    }
+
+  /* We want to skip stores to non-aliased variables.  */
+  if (!chain_ovfl
+      && gimple_assign_single_p (def_stmt))
+    {
+      tree lhs = gimple_assign_lhs (def_stmt);
+      if (!ref_may_be_aliased (lhs))
+	return false;
+    }
+
+  mark_operand_necessary (vdef);
+
+  return false;
+}
+
+static void
+mark_all_reaching_defs_necessary (gimple stmt)
+{
+  walk_aliased_vdefs (NULL, gimple_vuse (stmt),
+		      mark_all_reaching_defs_necessary_1, NULL, &visited);
+}
+
+/* Return true for PHI nodes with one or identical arguments
+   can be removed.  */
+static bool
+degenerate_phi_p (gimple phi)
+{
+  unsigned int i;
+  tree op = gimple_phi_arg_def (phi, 0);
+  for (i = 1; i < gimple_phi_num_args (phi); i++)
+    if (gimple_phi_arg_def (phi, i) != op)
+      return false;
+  return true;
+}
 
 /* Propagate necessity using the operands of necessary statements.
    Process the uses on each statement in the worklist, and add all
    feeding statements which contribute to the calculation of this
-   value to the worklist. 
+   value to the worklist.
 
    In conservative mode, EL is NULL.  */
 
@@ -440,7 +628,7 @@ static void
 propagate_necessity (struct edge_list *el)
 {
   gimple stmt;
-  bool aggressive = (el ? true : false); 
+  bool aggressive = (el ? true : false);
 
   if (dump_file && (dump_flags & TDF_DETAILS))
     fprintf (dump_file, "\nProcessing worklist:\n");
@@ -471,7 +659,10 @@ propagate_necessity (struct edge_list *el)
 	    }
 	}
 
-      if (gimple_code (stmt) == GIMPLE_PHI)
+      if (gimple_code (stmt) == GIMPLE_PHI
+	  /* We do not process virtual PHI nodes nor do we track their
+	     necessity.  */
+	  && is_gimple_reg (gimple_phi_result (stmt)))
 	{
 	  /* PHI nodes are somewhat special in that each PHI alternative has
 	     data and control dependencies.  All the statements feeding the
@@ -488,7 +679,7 @@ propagate_necessity (struct edge_list *el)
 		mark_operand_necessary (arg);
 	    }
 
-	  if (aggressive)
+	  if (aggressive && !degenerate_phi_p (stmt))
 	    {
 	      for (k = 0; k < gimple_phi_num_args (stmt); k++)
 		{
@@ -505,21 +696,165 @@ propagate_necessity (struct edge_list *el)
       else
 	{
 	  /* Propagate through the operands.  Examine all the USE, VUSE and
-	     VDEF operands in this statement.  Mark all the statements 
-	     which feed this statement's uses as necessary.  The
-	     operands of VDEF expressions are also needed as they
-	     represent potential definitions that may reach this
-	     statement (VDEF operands allow us to follow def-def
-	     links).  */
+	     VDEF operands in this statement.  Mark all the statements
+	     which feed this statement's uses as necessary.  */
 	  ssa_op_iter iter;
 	  tree use;
 
-	  FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_ALL_USES)
+	  FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
 	    mark_operand_necessary (use);
+
+	  use = gimple_vuse (stmt);
+	  if (!use)
+	    continue;
+
+	  /* If we dropped to simple mode make all immediately
+	     reachable definitions necessary.  */
+	  if (chain_ovfl)
+	    {
+	      mark_all_reaching_defs_necessary (stmt);
+	      continue;
+	    }
+
+	  /* For statements that may load from memory (have a VUSE) we
+	     have to mark all reaching (may-)definitions as necessary.
+	     We partition this task into two cases:
+	      1) explicit loads based on decls that are not aliased
+	      2) implicit loads (like calls) and explicit loads not
+	         based on decls that are not aliased (like indirect
+		 references or loads from globals)
+	     For 1) we mark all reaching may-defs as necessary, stopping
+	     at dominating kills.  For 2) we want to mark all dominating
+	     references necessary, but non-aliased ones which we handle
+	     in 1).  By keeping a global visited bitmap for references
+	     we walk for 2) we avoid quadratic behavior for those.  */
+
+	  if (is_gimple_call (stmt))
+	    {
+	      tree callee = gimple_call_fndecl (stmt);
+	      unsigned i;
+
+	      /* Calls to functions that are merely acting as barriers
+		 or that only store to memory do not make any previous
+		 stores necessary.  */
+	      if (callee != NULL_TREE
+		  && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL
+		  && (DECL_FUNCTION_CODE (callee) == BUILT_IN_MEMSET
+		      || DECL_FUNCTION_CODE (callee) == BUILT_IN_MALLOC
+		      || DECL_FUNCTION_CODE (callee) == BUILT_IN_FREE))
+		continue;
+
+	      /* Calls implicitly load from memory, their arguments
+	         in addition may explicitly perform memory loads.  */
+	      mark_all_reaching_defs_necessary (stmt);
+	      for (i = 0; i < gimple_call_num_args (stmt); ++i)
+		{
+		  tree arg = gimple_call_arg (stmt, i);
+		  if (TREE_CODE (arg) == SSA_NAME
+		      || is_gimple_min_invariant (arg))
+		    continue;
+		  if (!ref_may_be_aliased (arg))
+		    mark_aliased_reaching_defs_necessary (stmt, arg);
+		}
+	    }
+	  else if (gimple_assign_single_p (stmt))
+	    {
+	      tree rhs;
+	      bool rhs_aliased = false;
+	      /* If this is a load mark things necessary.  */
+	      rhs = gimple_assign_rhs1 (stmt);
+	      if (TREE_CODE (rhs) != SSA_NAME
+		  && !is_gimple_min_invariant (rhs))
+		{
+		  if (!ref_may_be_aliased (rhs))
+		    mark_aliased_reaching_defs_necessary (stmt, rhs);
+		  else
+		    rhs_aliased = true;
+		}
+	      if (rhs_aliased)
+		mark_all_reaching_defs_necessary (stmt);
+	    }
+	  else if (gimple_code (stmt) == GIMPLE_RETURN)
+	    {
+	      tree rhs = gimple_return_retval (stmt);
+	      /* A return statement may perform a load.  */
+	      if (TREE_CODE (rhs) != SSA_NAME
+		  && !is_gimple_min_invariant (rhs))
+		{
+		  if (!ref_may_be_aliased (rhs))
+		    mark_aliased_reaching_defs_necessary (stmt, rhs);
+		  else
+		    mark_all_reaching_defs_necessary (stmt);
+		}
+	    }
+	  else if (gimple_code (stmt) == GIMPLE_ASM)
+	    {
+	      unsigned i;
+	      mark_all_reaching_defs_necessary (stmt);
+	      /* Inputs may perform loads.  */
+	      for (i = 0; i < gimple_asm_ninputs (stmt); ++i)
+		{
+		  tree op = TREE_VALUE (gimple_asm_input_op (stmt, i));
+		  if (TREE_CODE (op) != SSA_NAME
+		      && !is_gimple_min_invariant (op)
+		      && !ref_may_be_aliased (op))
+		    mark_aliased_reaching_defs_necessary (stmt, op);
+		}
+	    }
+	  else
+	    gcc_unreachable ();
+
+	  /* If we over-used our alias oracle budget drop to simple
+	     mode.  The cost metric allows quadratic behavior
+	     (number of uses times number of may-defs queries) up to
+	     a constant maximal number of queries and after that falls back to
+	     super-linear complexity.  */
+	  if (/* Constant but quadratic for small functions.  */
+	      total_chain > 128 * 128
+	      /* Linear in the number of may-defs.  */
+	      && total_chain > 32 * longest_chain
+	      /* Linear in the number of uses.  */
+	      && total_chain > nr_walks * 32)
+	    {
+	      chain_ovfl = true;
+	      if (visited)
+		bitmap_clear (visited);
+	    }
 	}
     }
 }
 
+/* Replace all uses of result of PHI by underlying variable and mark it
+   for renaming.  */
+
+void
+mark_virtual_phi_result_for_renaming (gimple phi)
+{
+  bool used = false;
+  imm_use_iterator iter;
+  use_operand_p use_p;
+  gimple stmt;
+  tree result_ssa, result_var;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Marking result for renaming : ");
+      print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
+      fprintf (dump_file, "\n");
+    }
+
+  result_ssa = gimple_phi_result (phi);
+  result_var = SSA_NAME_VAR (result_ssa);
+  FOR_EACH_IMM_USE_STMT (stmt, iter, result_ssa)
+    {
+      FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
+        SET_USE (use_p, result_var);
+      update_stmt (stmt);
+      used = true;
+    }
+  if (used)
+    mark_sym_for_renaming (result_var);
+}
 
 /* Remove dead PHI nodes from block BB.  */
 
@@ -537,6 +872,31 @@ remove_dead_phis (basic_block bb)
       stats.total_phis++;
       phi = gsi_stmt (gsi);
 
+      /* We do not track necessity of virtual PHI nodes.  Instead do
+         very simple dead PHI removal here.  */
+      if (!is_gimple_reg (gimple_phi_result (phi)))
+	{
+	  /* Virtual PHI nodes with one or identical arguments
+	     can be removed.  */
+	  if (degenerate_phi_p (phi))
+	    {
+	      tree vdef = gimple_phi_result (phi);
+	      tree vuse = gimple_phi_arg_def (phi, 0);
+
+	      use_operand_p use_p;
+	      imm_use_iterator iter;
+	      gimple use_stmt;
+	      FOR_EACH_IMM_USE_STMT (use_stmt, iter, vdef)
+		FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
+		  SET_USE (use_p, vuse);
+	      if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vdef)
+	          && TREE_CODE (vuse) == SSA_NAME)
+		SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vuse) = 1;
+	    }
+	  else
+	    gimple_set_plf (phi, STMT_NECESSARY, true);
+	}
+
       if (!gimple_plf (phi, STMT_NECESSARY))
 	{
 	  something_changed = true;
@@ -549,15 +909,73 @@ remove_dead_phis (basic_block bb)
 
 	  remove_phi_node (&gsi, true);
 	  stats.removed_phis++;
+	  continue;
 	}
-      else
-	{
-          gsi_next (&gsi);
-	}
+
+      gsi_next (&gsi);
     }
   return something_changed;
 }
 
+/* Forward edge E to respective POST_DOM_BB and update PHIs.  */
+
+static edge
+forward_edge_to_pdom (edge e, basic_block post_dom_bb)
+{
+  gimple_stmt_iterator gsi;
+  edge e2 = NULL;
+  edge_iterator ei;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "Redirecting edge %i->%i to %i\n", e->src->index,
+	     e->dest->index, post_dom_bb->index);
+
+  e2 = redirect_edge_and_branch (e, post_dom_bb);
+  cfg_altered = true;
+
+  /* If edge was already around, no updating is neccesary.  */
+  if (e2 != e)
+    return e2;
+
+  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 pick any edge to duplicate PHI args from.  */
+      FOR_EACH_EDGE (e2, ei, post_dom_bb->preds)
+	if (e2 != e)
+	  break;
+      for (gsi = gsi_start_phis (post_dom_bb); !gsi_end_p (gsi);)
+	{
+	  gimple phi = gsi_stmt (gsi);
+	  tree op;
+	  source_location locus;
+
+	  /* 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;
+	    }
+
+	  /* Dead PHI do not imply control dependency.  */
+          if (!gimple_plf (phi, STMT_NECESSARY))
+	    {
+	      gsi_next (&gsi);
+	      continue;
+	    }
+
+	  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);
+	  /* The resulting PHI if not dead can only be degenerate.  */
+	  gcc_assert (degenerate_phi_p (phi));
+	  gsi_next (&gsi);
+	}
+    }
+  return e;
+}
 
 /* Remove dead statement pointed to by iterator I.  Receives the basic block BB
    containing I so that we don't have to look it up.  */
@@ -585,69 +1003,49 @@ remove_dead_stmt (gimple_stmt_iterator *i, basic_block bb)
   if (is_ctrl_stmt (stmt))
     {
       basic_block post_dom_bb;
+      edge e, e2;
+      edge_iterator ei;
 
-      /* 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);
 
-      /* There are three particularly problematical cases.
-
-	 1. Blocks that do not have an immediate post dominator.  This
-	    can happen with infinite loops.
+      e = find_edge (bb, post_dom_bb);
 
-	 2. Blocks that are only post dominated by the exit block.  These
-	    can also happen for infinite loops as we create fake edges
-	    in the dominator tree.
-
-	 3. If the post dominator has PHI nodes we may be able to compute
-	    the right PHI args for them.
-
-	 In each of these cases we must remove the control statement
-	 as it may reference SSA_NAMEs which are going to be removed and
-	 we remove all but one outgoing edge from the block.  */
-      if (! post_dom_bb
-	  || post_dom_bb == EXIT_BLOCK_PTR
-	  || phi_nodes (post_dom_bb))
-	;
+      /* If edge is already there, try to use it.  This avoids need to update
+         PHI nodes.  Also watch for cases where post dominator does not exists
+	 or is exit block.  These can happen for infinite loops as we create
+	 fake edges in the dominator tree.  */
+      if (e)
+        ;
+      else if (! post_dom_bb || post_dom_bb == EXIT_BLOCK_PTR)
+	e = EDGE_SUCC (bb, 0);
       else
-	{
-	  /* Redirect the first edge out of BB to reach POST_DOM_BB.  */
-	  redirect_edge_and_branch (EDGE_SUCC (bb, 0), post_dom_bb);
-	  PENDING_STMT (EDGE_SUCC (bb, 0)) = NULL;
-
-	  /* It is not sufficient to set cfg_altered below during edge
-	     removal, in case BB has two successors and one of them
-	     is POST_DOM_BB.  */
-	  cfg_altered = true;
-	}
-      EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE;
-      EDGE_SUCC (bb, 0)->count = bb->count;
+        e = forward_edge_to_pdom (EDGE_SUCC (bb, 0), post_dom_bb);
+      gcc_assert (e);
+      e->probability = REG_BR_PROB_BASE;
+      e->count = bb->count;
 
       /* The edge is no longer associated with a conditional, so it does
 	 not have TRUE/FALSE flags.  */
-      EDGE_SUCC (bb, 0)->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
+      e->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
 
       /* The lone outgoing edge from BB will be a fallthru edge.  */
-      EDGE_SUCC (bb, 0)->flags |= EDGE_FALLTHRU;
-
-      /* Remove the remaining the outgoing edges.  */
-      while (!single_succ_p (bb))
-	{
-	  /* FIXME.  When we remove the edge, we modify the CFG, which
-	     in turn modifies the dominator and post-dominator tree.
-	     Is it safe to postpone recomputing the dominator and
-	     post-dominator tree until the end of this pass given that
-	     the post-dominators are used above?  */
-	  cfg_altered = true;
-          remove_edge (EDGE_SUCC (bb, 1));
-	}
+      e->flags |= EDGE_FALLTHRU;
+
+      /* Remove the remaining outgoing edges.  */
+      for (ei = ei_start (bb->succs); (e2 = ei_safe_edge (ei)); )
+	if (e != e2)
+	  {
+	    cfg_altered = true;
+            remove_edge (e2);
+	  }
+	else
+	  ei_next (&ei);
     }
-  
-  gsi_remove (i, true);  
-  release_defs (stmt); 
-}
 
+  unlink_stmt_vdef (stmt);
+  gsi_remove (i, true);
+  release_defs (stmt);
+}
 
 /* Eliminate unnecessary statements. Any instruction not marked as necessary
    contributes nothing to the program, and can be deleted.  */
@@ -657,34 +1055,61 @@ eliminate_unnecessary_stmts (void)
 {
   bool something_changed = false;
   basic_block bb;
-  gimple_stmt_iterator gsi;
+  gimple_stmt_iterator gsi, psi;
   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)
-    {
-      /* Remove dead PHI nodes.  */
-      something_changed |= remove_dead_phis (bb);
-    }
 
-  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); gsi = psi)
 	{
 	  stmt = gsi_stmt (gsi);
 
+	  psi = gsi;
+	  gsi_prev (&psi);
+
 	  stats.total++;
 
 	  /* If GSI is not necessary then remove it.  */
 	  if (!gimple_plf (stmt, STMT_NECESSARY))
 	    {
+	      if (!is_gimple_debug (stmt))
+		something_changed = true;
 	      remove_dead_stmt (&gsi, bb);
-	      something_changed = true;
 	    }
 	  else if (is_gimple_call (stmt))
 	    {
@@ -692,7 +1117,6 @@ eliminate_unnecessary_stmts (void)
 	      if (call)
 		{
 		  tree name;
-		  gimple g;
 
 		  /* When LHS of var = call (); is dead, simplify it into
 		     call (); saving one operand.  */
@@ -707,26 +1131,95 @@ eliminate_unnecessary_stmts (void)
 			  print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 			  fprintf (dump_file, "\n");
 			}
-		      
-		      push_stmt_changes (gsi_stmt_ptr (&gsi));
-		      g = gimple_copy (stmt);
-		      gimple_call_set_lhs (g, NULL_TREE);
-		      gsi_replace (&gsi, g, false);
-		      maybe_clean_or_replace_eh_stmt (stmt, g);
-		      mark_symbols_for_renaming (g);
-		      pop_stmt_changes (gsi_stmt_ptr (&gsi));
+
+		      gimple_call_set_lhs (stmt, NULL_TREE);
+		      maybe_clean_or_replace_eh_stmt (stmt, stmt);
+		      update_stmt (stmt);
 		      release_ssa_name (name);
 		    }
 		  notice_special_calls (stmt);
 		}
-	      gsi_next (&gsi);
 	    }
-	  else
+	}
+    }
+
+  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 prev_bb;
+
+      find_unreachable_blocks ();
+
+      /* Delete all unreachable basic blocks in reverse dominator order.  */
+      for (bb = EXIT_BLOCK_PTR->prev_bb; bb != ENTRY_BLOCK_PTR; bb = prev_bb)
+	{
+	  prev_bb = bb->prev_bb;
+
+	  if (!TEST_BIT (bb_contains_live_stmts, bb->index)
+	      || !(bb->flags & BB_REACHABLE))
 	    {
-	      gsi_next (&gsi);
+	      for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+		if (!is_gimple_reg (gimple_phi_result (gsi_stmt (gsi))))
+		  {
+		    bool found = false;
+		    imm_use_iterator iter;
+
+		    FOR_EACH_IMM_USE_STMT (stmt, iter, gimple_phi_result (gsi_stmt (gsi)))
+		      {
+			if (!(gimple_bb (stmt)->flags & BB_REACHABLE))
+			  continue;
+			if (gimple_code (stmt) == GIMPLE_PHI
+			    || gimple_plf (stmt, STMT_NECESSARY))
+			  {
+			    found = true;
+			    BREAK_FROM_IMM_USE_STMT (iter);
+			  }
+		      }
+		    if (found)
+		      mark_virtual_phi_result_for_renaming (gsi_stmt (gsi));
+		  }
+
+	      if (!(bb->flags & BB_REACHABLE))
+		{
+		  /* 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);
+		    }
+		}
 	    }
 	}
     }
+  FOR_EACH_BB (bb)
+    {
+      /* Remove dead PHI nodes.  */
+      something_changed |= remove_dead_phis (bb);
+    }
 
   return something_changed;
 }
@@ -769,6 +1262,8 @@ tree_dce_init (bool aggressive)
 
       last_stmt_necessary = sbitmap_alloc (last_basic_block);
       sbitmap_zero (last_stmt_necessary);
+      bb_contains_live_stmts = sbitmap_alloc (last_basic_block);
+      sbitmap_zero (bb_contains_live_stmts);
     }
 
   processed = sbitmap_alloc (num_ssa_names + 1);
@@ -793,6 +1288,8 @@ tree_dce_done (bool aggressive)
 
       sbitmap_free (visited_control_parents);
       sbitmap_free (last_stmt_necessary);
+      sbitmap_free (bb_contains_live_stmts);
+      bb_contains_live_stmts = NULL;
     }
 
   sbitmap_free (processed);
@@ -820,6 +1317,13 @@ perform_tree_ssa_dce (bool aggressive)
   struct edge_list *el = NULL;
   bool something_changed = 0;
 
+  /* Preheaders are needed for SCEV to work.
+     Simple lateches and recorded exits improve chances that loop will
+     proved to be finite in testcases such as in loop-15.c and loop-24.c  */
+  if (aggressive)
+    loop_optimizer_init (LOOPS_NORMAL
+			 | LOOPS_HAVE_RECORDED_EXITS);
+
   tree_dce_init (aggressive);
 
   if (aggressive)
@@ -839,7 +1343,16 @@ perform_tree_ssa_dce (bool aggressive)
 
   find_obviously_necessary_stmts (el);
 
+  if (aggressive)
+    loop_optimizer_finalize ();
+
+  longest_chain = 0;
+  total_chain = 0;
+  nr_walks = 0;
+  chain_ovfl = false;
+  visited = BITMAP_ALLOC (NULL);
   propagate_necessity (el);
+  BITMAP_FREE (visited);
 
   something_changed |= eliminate_unnecessary_stmts ();
   something_changed |= cfg_altered;
@@ -865,7 +1378,7 @@ perform_tree_ssa_dce (bool aggressive)
   free_edge_list (el);
 
   if (something_changed)
-    return (TODO_update_ssa | TODO_cleanup_cfg | TODO_ggc_collect 
+    return (TODO_update_ssa | TODO_cleanup_cfg | TODO_ggc_collect
 	    | TODO_remove_unused_locals);
   else
     return 0;