Merge from trunk revision 104c05c5284b7822d770ee51a7d91946c7e56d50.

1 files changed, 156 insertions, 109 deletions

diff --git a/gcc/tree-ssa-dse.c b/gcc/tree-ssa-dse.c
index 4967a5a..98daa8a 100644
--- a/gcc/tree-ssa-dse.c
+++ b/gcc/tree-ssa-dse.c
@@ -31,7 +31,6 @@ along with GCC; see the file COPYING3.  If not see
 #include "gimple-iterator.h"
 #include "tree-cfg.h"
 #include "tree-dfa.h"
-#include "domwalk.h"
 #include "tree-cfgcleanup.h"
 #include "alias.h"
 #include "tree-ssa-loop.h"
@@ -39,6 +38,8 @@ along with GCC; see the file COPYING3.  If not see
 #include "builtins.h"
 #include "gimple-fold.h"
 #include "gimplify.h"
+#include "tree-eh.h"
+#include "cfganal.h"
 
 /* This file implements dead store elimination.
 
@@ -139,10 +140,13 @@ initialize_ao_ref_for_dse (gimple *stmt, ao_ref *write)
 	  break;
 	}
     }
-  else if (is_gimple_assign (stmt))
+  else if (tree lhs = gimple_get_lhs (stmt))
     {
-      ao_ref_init (write, gimple_assign_lhs (stmt));
-      return true;
+      if (TREE_CODE (lhs) != SSA_NAME)
+	{
+	  ao_ref_init (write, lhs);
+	  return true;
+	}
     }
   return false;
 }
@@ -798,7 +802,8 @@ dse_classify_store (ao_ref *ref, gimple *stmt,
 	return DSE_STORE_LIVE;
 
       auto_vec<gimple *, 10> defs;
-      gimple *phi_def = NULL;
+      gimple *first_phi_def = NULL;
+      gimple *last_phi_def = NULL;
       FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar)
 	{
 	  /* Limit stmt walking.  */
@@ -808,15 +813,11 @@ dse_classify_store (ao_ref *ref, gimple *stmt,
 	      break;
 	    }
 
-	  /* We have visited ourselves already so ignore STMT for the
-	     purpose of chaining.  */
-	  if (use_stmt == stmt)
-	    ;
 	  /* In simple cases we can look through PHI nodes, but we
 	     have to be careful with loops and with memory references
 	     containing operands that are also operands of PHI nodes.
 	     See gcc.c-torture/execute/20051110-*.c.  */
-	  else if (gimple_code (use_stmt) == GIMPLE_PHI)
+	  if (gimple_code (use_stmt) == GIMPLE_PHI)
 	    {
 	      /* If we already visited this PHI ignore it for further
 		 processing.  */
@@ -824,7 +825,9 @@ dse_classify_store (ao_ref *ref, gimple *stmt,
 				 SSA_NAME_VERSION (PHI_RESULT (use_stmt))))
 		{
 		  defs.safe_push (use_stmt);
-		  phi_def = use_stmt;
+		  if (!first_phi_def)
+		    first_phi_def = use_stmt;
+		  last_phi_def = use_stmt;
 		}
 	    }
 	  /* If the statement is a use the store is not dead.  */
@@ -854,6 +857,10 @@ dse_classify_store (ao_ref *ref, gimple *stmt,
 	      fail = true;
 	      break;
 	    }
+	  /* We have visited ourselves already so ignore STMT for the
+	     purpose of chaining.  */
+	  else if (use_stmt == stmt)
+	    ;
 	  /* If this is a store, remember it as we possibly need to walk the
 	     defs uses.  */
 	  else if (gimple_vdef (use_stmt))
@@ -888,6 +895,8 @@ dse_classify_store (ao_ref *ref, gimple *stmt,
 	  gimple *def = defs[i];
 	  gimple *use_stmt;
 	  use_operand_p use_p;
+	  tree vdef = (gimple_code (def) == GIMPLE_PHI
+		       ? gimple_phi_result (def) : gimple_vdef (def));
 	  /* If the path to check starts with a kill we do not need to
 	     process it further.
 	     ???  With byte tracking we need only kill the bytes currently
@@ -900,8 +909,7 @@ dse_classify_store (ao_ref *ref, gimple *stmt,
 	    }
 	  /* If the path ends here we do not need to process it further.
 	     This for example happens with calls to noreturn functions.  */
-	  else if (gimple_code (def) != GIMPLE_PHI
-		   && has_zero_uses (gimple_vdef (def)))
+	  else if (has_zero_uses (vdef))
 	    {
 	      /* But if the store is to global memory it is definitely
 		 not dead.  */
@@ -911,12 +919,13 @@ dse_classify_store (ao_ref *ref, gimple *stmt,
 	    }
 	  /* In addition to kills we can remove defs whose only use
 	     is another def in defs.  That can only ever be PHIs of which
-	     we track a single for simplicity reasons (we fail for multiple
-	     PHIs anyways).  We can also ignore defs that feed only into
+	     we track two for simplicity reasons, the first and last in
+	     {first,last}_phi_def (we fail for multiple PHIs anyways).
+	     We can also ignore defs that feed only into
 	     already visited PHIs.  */
-	  else if (gimple_code (def) != GIMPLE_PHI
-		   && single_imm_use (gimple_vdef (def), &use_p, &use_stmt)
-		   && (use_stmt == phi_def
+	  else if (single_imm_use (vdef, &use_p, &use_stmt)
+		   && (use_stmt == first_phi_def
+		       || use_stmt == last_phi_def
 		       || (gimple_code (use_stmt) == GIMPLE_PHI
 			   && bitmap_bit_p (visited,
 					    SSA_NAME_VERSION
@@ -957,22 +966,6 @@ dse_classify_store (ao_ref *ref, gimple *stmt,
 }
 
 
-class dse_dom_walker : public dom_walker
-{
-public:
-  dse_dom_walker (cdi_direction direction)
-    : dom_walker (direction),
-    m_live_bytes (param_dse_max_object_size),
-    m_byte_tracking_enabled (false) {}
-
-  virtual edge before_dom_children (basic_block);
-
-private:
-  auto_sbitmap m_live_bytes;
-  bool m_byte_tracking_enabled;
-  void dse_optimize_stmt (gimple_stmt_iterator *);
-};
-
 /* Delete a dead call at GSI, which is mem* call of some kind.  */
 static void
 delete_dead_or_redundant_call (gimple_stmt_iterator *gsi, const char *type)
@@ -1044,16 +1037,11 @@ delete_dead_or_redundant_assignment (gimple_stmt_iterator *gsi, const char *type
    is used precisely once by a later store to the same location which
    post dominates the first store, then the first store is dead.  */
 
-void
-dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator *gsi)
+static void
+dse_optimize_stmt (function *fun, gimple_stmt_iterator *gsi, sbitmap live_bytes)
 {
   gimple *stmt = gsi_stmt (*gsi);
 
-  /* If this statement has no virtual defs, then there is nothing
-     to do.  */
-  if (!gimple_vdef (stmt))
-    return;
-
   /* Don't return early on *this_2(D) ={v} {CLOBBER}.  */
   if (gimple_has_volatile_ops (stmt)
       && (!gimple_clobber_p (stmt)
@@ -1099,17 +1087,17 @@ dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator *gsi)
 	      dse_optimize_redundant_stores (stmt);
 
 	    enum dse_store_status store_status;
-	    m_byte_tracking_enabled
-	      = setup_live_bytes_from_ref (&ref, m_live_bytes);
+	    bool byte_tracking_enabled
+	      = setup_live_bytes_from_ref (&ref, live_bytes);
 	    store_status = dse_classify_store (&ref, stmt,
-					       m_byte_tracking_enabled,
-					       m_live_bytes);
+					       byte_tracking_enabled,
+					       live_bytes);
 	    if (store_status == DSE_STORE_LIVE)
 	      return;
 
 	    if (store_status == DSE_STORE_MAYBE_PARTIAL_DEAD)
 	      {
-		maybe_trim_memstar_call (&ref, m_live_bytes, stmt);
+		maybe_trim_memstar_call (&ref, live_bytes, stmt);
 		return;
 	      }
 
@@ -1128,65 +1116,69 @@ dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator *gsi)
 	}
     }
 
-  if (is_gimple_assign (stmt))
-    {
-      bool by_clobber_p = false;
-
-      /* Check if this statement stores zero to a memory location,
-	 and if there is a subsequent store of zero to the same
-	 memory location.  If so, remove the subsequent store.  */
-      if (gimple_assign_single_p (stmt)
-	  && initializer_zerop (gimple_assign_rhs1 (stmt)))
-	dse_optimize_redundant_stores (stmt);
-
-      /* Self-assignments are zombies.  */
-      if (operand_equal_p (gimple_assign_rhs1 (stmt),
-			   gimple_assign_lhs (stmt), 0))
-	;
-      else
-	{
-	  m_byte_tracking_enabled
-	    = setup_live_bytes_from_ref (&ref, m_live_bytes);
-	  enum dse_store_status store_status;
-	  store_status = dse_classify_store (&ref, stmt,
-					     m_byte_tracking_enabled,
-					     m_live_bytes, &by_clobber_p);
-	  if (store_status == DSE_STORE_LIVE)
-	    return;
-
-	  if (store_status == DSE_STORE_MAYBE_PARTIAL_DEAD)
-	    {
-	      maybe_trim_partially_dead_store (&ref, m_live_bytes, stmt);
-	      return;
-	    }
-	}
+  bool by_clobber_p = false;
 
-      /* Now we know that use_stmt kills the LHS of stmt.  */
+  /* Check if this statement stores zero to a memory location,
+     and if there is a subsequent store of zero to the same
+     memory location.  If so, remove the subsequent store.  */
+  if (gimple_assign_single_p (stmt)
+      && initializer_zerop (gimple_assign_rhs1 (stmt)))
+    dse_optimize_redundant_stores (stmt);
 
-      /* But only remove *this_2(D) ={v} {CLOBBER} if killed by
-	 another clobber stmt.  */
-      if (gimple_clobber_p (stmt)
-	  && !by_clobber_p)
+  /* Self-assignments are zombies.  */
+  if (is_gimple_assign (stmt)
+      && operand_equal_p (gimple_assign_rhs1 (stmt),
+			  gimple_assign_lhs (stmt), 0))
+    ;
+  else
+    {
+      bool byte_tracking_enabled
+	  = setup_live_bytes_from_ref (&ref, live_bytes);
+      enum dse_store_status store_status;
+      store_status = dse_classify_store (&ref, stmt,
+					 byte_tracking_enabled,
+					 live_bytes, &by_clobber_p);
+      if (store_status == DSE_STORE_LIVE)
 	return;
 
-      delete_dead_or_redundant_assignment (gsi, "dead", need_eh_cleanup);
+      if (store_status == DSE_STORE_MAYBE_PARTIAL_DEAD)
+	{
+	  maybe_trim_partially_dead_store (&ref, live_bytes, stmt);
+	  return;
+	}
     }
-}
 
-edge
-dse_dom_walker::before_dom_children (basic_block bb)
-{
-  gimple_stmt_iterator gsi;
+  /* Now we know that use_stmt kills the LHS of stmt.  */
 
-  for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
+  /* But only remove *this_2(D) ={v} {CLOBBER} if killed by
+     another clobber stmt.  */
+  if (gimple_clobber_p (stmt)
+      && !by_clobber_p)
+    return;
+
+  if (is_gimple_call (stmt)
+      && (gimple_has_side_effects (stmt)
+	  || (stmt_could_throw_p (fun, stmt)
+	      && !fun->can_delete_dead_exceptions)))
     {
-      dse_optimize_stmt (&gsi);
-      if (gsi_end_p (gsi))
-	gsi = gsi_last_bb (bb);
-      else
-	gsi_prev (&gsi);
+      /* Make sure we do not remove a return slot we cannot reconstruct
+	 later.  */
+      if (gimple_call_return_slot_opt_p (as_a <gcall *>(stmt))
+	  && (TREE_ADDRESSABLE (TREE_TYPE (gimple_call_fntype (stmt)))
+	      || !poly_int_tree_p
+		    (TYPE_SIZE (TREE_TYPE (gimple_call_fntype (stmt))))))
+	return;
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file, "  Deleted dead store in call LHS: ");
+	  print_gimple_stmt (dump_file, stmt, 0, dump_flags);
+	  fprintf (dump_file, "\n");
+	}
+      gimple_call_set_lhs (stmt, NULL_TREE);
+      update_stmt (stmt);
     }
-  return NULL;
+  else
+    delete_dead_or_redundant_assignment (gsi, "dead", need_eh_cleanup);
 }
 
 namespace {
@@ -1221,34 +1213,89 @@ public:
 unsigned int
 pass_dse::execute (function *fun)
 {
+  unsigned todo = 0;
   need_eh_cleanup = BITMAP_ALLOC (NULL);
+  auto_sbitmap live_bytes (param_dse_max_object_size);
 
-  renumber_gimple_stmt_uids (cfun);
+  renumber_gimple_stmt_uids (fun);
 
-  /* We might consider making this a property of each pass so that it
-     can be [re]computed on an as-needed basis.  Particularly since
-     this pass could be seen as an extension of DCE which needs post
-     dominators.  */
-  calculate_dominance_info (CDI_POST_DOMINATORS);
   calculate_dominance_info (CDI_DOMINATORS);
 
-  /* Dead store elimination is fundamentally a walk of the post-dominator
-     tree and a backwards walk of statements within each block.  */
-  dse_dom_walker (CDI_POST_DOMINATORS).walk (fun->cfg->x_exit_block_ptr);
+  /* Dead store elimination is fundamentally a reverse program order walk.  */
+  int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (fun) - NUM_FIXED_BLOCKS);
+  int n = pre_and_rev_post_order_compute_fn (fun, NULL, rpo, false);
+  for (int i = n; i != 0; --i)
+    {
+      basic_block bb = BASIC_BLOCK_FOR_FN (fun, rpo[i-1]);
+      gimple_stmt_iterator gsi;
+
+      for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
+	{
+	  gimple *stmt = gsi_stmt (gsi);
+
+	  if (gimple_vdef (stmt))
+	    dse_optimize_stmt (fun, &gsi, live_bytes);
+	  else if (def_operand_p
+		     def_p = single_ssa_def_operand (stmt, SSA_OP_DEF))
+	    {
+	      /* When we remove dead stores make sure to also delete trivially
+		 dead SSA defs.  */
+	      if (has_zero_uses (DEF_FROM_PTR (def_p))
+		  && !gimple_has_side_effects (stmt)
+		  && !is_ctrl_altering_stmt (stmt)
+		  && (!stmt_could_throw_p (fun, stmt)
+		      || fun->can_delete_dead_exceptions))
+		{
+		  if (dump_file && (dump_flags & TDF_DETAILS))
+		    {
+		      fprintf (dump_file, "  Deleted trivially dead stmt: ");
+		      print_gimple_stmt (dump_file, stmt, 0, dump_flags);
+		      fprintf (dump_file, "\n");
+		    }
+		  if (gsi_remove (&gsi, true) && need_eh_cleanup)
+		    bitmap_set_bit (need_eh_cleanup, bb->index);
+		  release_defs (stmt);
+		}
+	    }
+	  if (gsi_end_p (gsi))
+	    gsi = gsi_last_bb (bb);
+	  else
+	    gsi_prev (&gsi);
+	}
+      bool removed_phi = false;
+      for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si);)
+	{
+	  gphi *phi = si.phi ();
+	  if (has_zero_uses (gimple_phi_result (phi)))
+	    {
+	      if (dump_file && (dump_flags & TDF_DETAILS))
+		{
+		  fprintf (dump_file, "  Deleted trivially dead PHI: ");
+		  print_gimple_stmt (dump_file, phi, 0, dump_flags);
+		  fprintf (dump_file, "\n");
+		}
+	      remove_phi_node (&si, true);
+	      removed_phi = true;
+	    }
+	  else
+	    gsi_next (&si);
+	}
+      if (removed_phi && gimple_seq_empty_p (phi_nodes (bb)))
+	todo |= TODO_cleanup_cfg;
+    }
+  free (rpo);
 
   /* Removal of stores may make some EH edges dead.  Purge such edges from
      the CFG as needed.  */
   if (!bitmap_empty_p (need_eh_cleanup))
     {
       gimple_purge_all_dead_eh_edges (need_eh_cleanup);
-      cleanup_tree_cfg ();
+      todo |= TODO_cleanup_cfg;
     }
 
   BITMAP_FREE (need_eh_cleanup);
 
-  /* For now, just wipe the post-dominator information.  */
-  free_dominance_info (CDI_POST_DOMINATORS);
-  return 0;
+  return todo;
 }
 
 } // anon namespace