[thirdparty/gcc.git] / gcc / tree-ssa-dse.c

/* Dead store elimination
   Copyright (C) 2004-2015 Free Software Foundation, Inc.

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/>.  */

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "rtl.h"
#include "tree.h"
#include "gimple.h"
#include "tree-pass.h"
#include "tm_p.h"
#include "ssa.h"
#include "expmed.h"
#include "insn-config.h"
#include "emit-rtl.h"
#include "gimple-pretty-print.h"
#include "alias.h"
#include "fold-const.h"
#include "internal-fn.h"
#include "gimple-iterator.h"
#include "tree-cfg.h"
#include "flags.h"
#include "dojump.h"
#include "explow.h"
#include "calls.h"
#include "varasm.h"
#include "stmt.h"
#include "expr.h"
#include "tree-dfa.h"
#include "domwalk.h"
#include "langhooks.h"
#include "tree-cfgcleanup.h"

/* This file implements dead store elimination.

   A dead store is a store into a memory location which will later be
   overwritten by another store without any intervening loads.  In this
   case the earlier store can be deleted.

   In our SSA + virtual operand world we use immediate uses of virtual
   operands to detect dead stores.  If a store's virtual definition
   is used precisely once by a later store to the same location which
   post dominates the first store, then the first store is dead.

   The single use of the store's virtual definition ensures that
   there are no intervening aliased loads and the requirement that
   the second load post dominate the first ensures that if the earlier
   store executes, then the later stores will execute before the function
   exits.

   It may help to think of this as first moving the earlier store to
   the point immediately before the later store.  Again, the single
   use of the virtual definition and the post-dominance relationship
   ensure that such movement would be safe.  Clearly if there are
   back to back stores, then the second is redundant.

   Reviewing section 10.7.2 in Morgan's "Building an Optimizing Compiler"
   may also help in understanding this code since it discusses the
   relationship between dead store and redundant load elimination.  In
   fact, they are the same transformation applied to different views of
   the CFG.  */


/* Bitmap of blocks that have had EH statements cleaned.  We should
   remove their dead edges eventually.  */
static bitmap need_eh_cleanup;


/* A helper of dse_optimize_stmt.
   Given a GIMPLE_ASSIGN in STMT that writes to REF, find a candidate
   statement *USE_STMT that may prove STMT to be dead.
   Return TRUE if the above conditions are met, otherwise FALSE.  */

static bool
dse_possible_dead_store_p (ao_ref *ref, gimple *stmt, gimple **use_stmt)
{
  gimple *temp;
  unsigned cnt = 0;

  *use_stmt = NULL;

  /* Find the first dominated statement that clobbers (part of) the
     memory stmt stores to with no intermediate statement that may use
     part of the memory stmt stores.  That is, find a store that may
     prove stmt to be a dead store.  */
  temp = stmt;
  do
    {
      gimple *use_stmt, *defvar_def;
      imm_use_iterator ui;
      bool fail = false;
      tree defvar;

      /* Limit stmt walking to be linear in the number of possibly
         dead stores.  */
      if (++cnt > 256)
	return false;

      if (gimple_code (temp) == GIMPLE_PHI)
	defvar = PHI_RESULT (temp);
      else
	defvar = gimple_vdef (temp);
      defvar_def = temp;
      temp = NULL;
      FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar)
	{
	  cnt++;

	  /* If we ever reach our DSE candidate stmt again fail.  We
	     cannot handle dead stores in loops.  */
	  if (use_stmt == stmt)
	    {
	      fail = true;
	      BREAK_FROM_IMM_USE_STMT (ui);
	    }
	  /* 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 (temp
		  /* Make sure we are not in a loop latch block.  */
		  || gimple_bb (stmt) == gimple_bb (use_stmt)
		  || dominated_by_p (CDI_DOMINATORS,
				     gimple_bb (stmt), gimple_bb (use_stmt))
		  /* We can look through PHIs to regions post-dominating
		     the DSE candidate stmt.  */
		  || !dominated_by_p (CDI_POST_DOMINATORS,
				      gimple_bb (stmt), gimple_bb (use_stmt)))
		{
		  fail = true;
		  BREAK_FROM_IMM_USE_STMT (ui);
		}
	      /* Do not consider the PHI as use if it dominates the 
	         stmt defining the virtual operand we are processing,
		 we have processed it already in this case.  */
	      if (gimple_bb (defvar_def) != gimple_bb (use_stmt)
		  && !dominated_by_p (CDI_DOMINATORS,
				      gimple_bb (defvar_def),
				      gimple_bb (use_stmt)))
		temp = use_stmt;
	    }
	  /* If the statement is a use the store is not dead.  */
	  else if (ref_maybe_used_by_stmt_p (use_stmt, ref))
	    {
	      fail = true;
	      BREAK_FROM_IMM_USE_STMT (ui);
	    }
	  /* If this is a store, remember it or bail out if we have
	     multiple ones (the will be in different CFG parts then).  */
	  else if (gimple_vdef (use_stmt))
	    {
	      if (temp)
		{
		  fail = true;
		  BREAK_FROM_IMM_USE_STMT (ui);
		}
	      temp = use_stmt;
	    }
	}

      if (fail)
	return false;

      /* If we didn't find any definition this means the store is dead
         if it isn't a store to global reachable memory.  In this case
	 just pretend the stmt makes itself dead.  Otherwise fail.  */
      if (!temp)
	{
	  if (ref_may_alias_global_p (ref))
	    return false;

	  temp = stmt;
	  break;
	}
    }
  /* Continue walking until we reach a kill.  */
  while (!stmt_kills_ref_p (temp, ref));

  *use_stmt = temp;

  return true;
}


/* Attempt to eliminate dead stores in the statement referenced by BSI.

   A dead store is a store into a memory location which will later be
   overwritten by another store without any intervening loads.  In this
   case the earlier store can be deleted.

   In our SSA + virtual operand world we use immediate uses of virtual
   operands to detect dead stores.  If a store's virtual definition
   is used precisely once by a later store to the same location which
   post dominates the first store, then the first store is dead.  */

static void
dse_optimize_stmt (gimple_stmt_iterator *gsi)
{
  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)
	  || TREE_CODE (gimple_assign_lhs (stmt)) != MEM_REF))
    return;

  /* We know we have virtual definitions.  We can handle assignments and
     some builtin calls.  */
  if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
    {
      switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt)))
	{
	  case BUILT_IN_MEMCPY:
	  case BUILT_IN_MEMMOVE:
	  case BUILT_IN_MEMSET:
	    {
	      gimple *use_stmt;
	      ao_ref ref;
	      tree size = NULL_TREE;
	      if (gimple_call_num_args (stmt) == 3)
		size = gimple_call_arg (stmt, 2);
	      tree ptr = gimple_call_arg (stmt, 0);
	      ao_ref_init_from_ptr_and_size (&ref, ptr, size);
	      if (!dse_possible_dead_store_p (&ref, stmt, &use_stmt))
		return;

	      if (dump_file && (dump_flags & TDF_DETAILS))
		{
		  fprintf (dump_file, "  Deleted dead call '");
		  print_gimple_stmt (dump_file, gsi_stmt (*gsi), dump_flags, 0);
		  fprintf (dump_file, "'\n");
		}

	      tree lhs = gimple_call_lhs (stmt);
	      if (lhs)
		{
		  gimple *new_stmt = gimple_build_assign (lhs, ptr);
		  unlink_stmt_vdef (stmt);
		  if (gsi_replace (gsi, new_stmt, true))
		    bitmap_set_bit (need_eh_cleanup, gimple_bb (stmt)->index);
		}
	      else
		{
		  /* Then we need to fix the operand of the consuming stmt.  */
		  unlink_stmt_vdef (stmt);

		  /* Remove the dead store.  */
		  if (gsi_remove (gsi, true))
		    bitmap_set_bit (need_eh_cleanup, gimple_bb (stmt)->index);
		  release_defs (stmt);
		}
	      break;
	    }
	  default:
	    return;
	}
    }

  if (is_gimple_assign (stmt))
    {
      gimple *use_stmt;

      /* Self-assignments are zombies.  */
      if (operand_equal_p (gimple_assign_rhs1 (stmt),
			   gimple_assign_lhs (stmt), 0))
	use_stmt = stmt;
      else
	{
	  ao_ref ref;
	  ao_ref_init (&ref, gimple_assign_lhs (stmt));
  	  if (!dse_possible_dead_store_p (&ref, stmt, &use_stmt))
	    return;
	}

      /* Now we know that use_stmt kills the LHS of stmt.  */

      /* But only remove *this_2(D) ={v} {CLOBBER} if killed by
	 another clobber stmt.  */
      if (gimple_clobber_p (stmt)
	  && !gimple_clobber_p (use_stmt))
	return;

      if (dump_file && (dump_flags & TDF_DETAILS))
	{
	  fprintf (dump_file, "  Deleted dead store '");
	  print_gimple_stmt (dump_file, gsi_stmt (*gsi), dump_flags, 0);
	  fprintf (dump_file, "'\n");
	}

      /* Then we need to fix the operand of the consuming stmt.  */
      unlink_stmt_vdef (stmt);

      /* Remove the dead store.  */
      basic_block bb = gimple_bb (stmt);
      if (gsi_remove (gsi, true))
	bitmap_set_bit (need_eh_cleanup, bb->index);

      /* And release any SSA_NAMEs set in this statement back to the
	 SSA_NAME manager.  */
      release_defs (stmt);
    }
}

class dse_dom_walker : public dom_walker
{
public:
  dse_dom_walker (cdi_direction direction) : dom_walker (direction) {}

  virtual void before_dom_children (basic_block);
};

void
dse_dom_walker::before_dom_children (basic_block bb)
{
  gimple_stmt_iterator gsi;

  for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
    {
      dse_optimize_stmt (&gsi);
      if (gsi_end_p (gsi))
	gsi = gsi_last_bb (bb);
      else
	gsi_prev (&gsi);
    }
}

namespace {

const pass_data pass_data_dse =
{
  GIMPLE_PASS, /* type */
  "dse", /* name */
  OPTGROUP_NONE, /* optinfo_flags */
  TV_TREE_DSE, /* tv_id */
  ( PROP_cfg | PROP_ssa ), /* properties_required */
  0, /* properties_provided */
  0, /* properties_destroyed */
  0, /* todo_flags_start */
  0, /* todo_flags_finish */
};

class pass_dse : public gimple_opt_pass
{
public:
  pass_dse (gcc::context *ctxt)
    : gimple_opt_pass (pass_data_dse, ctxt)
  {}

  /* opt_pass methods: */
  opt_pass * clone () { return new pass_dse (m_ctxt); }
  virtual bool gate (function *) { return flag_tree_dse != 0; }
  virtual unsigned int execute (function *);

}; // class pass_dse

unsigned int
pass_dse::execute (function *fun)
{
  need_eh_cleanup = BITMAP_ALLOC (NULL);

  renumber_gimple_stmt_uids ();

  /* 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);

  /* 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 ();
    }

  BITMAP_FREE (need_eh_cleanup);
    
  /* For now, just wipe the post-dominator information.  */
  free_dominance_info (CDI_POST_DOMINATORS);
  return 0;
}

} // anon namespace

gimple_opt_pass *
make_pass_dse (gcc::context *ctxt)
{
  return new pass_dse (ctxt);
}
Commit	Line	Data
4ee9c684	1	/* Dead store elimination
d353bf18	2	Copyright (C) 2004-2015 Free Software Foundation, Inc.
4ee9c684	3
	4	This file is part of GCC.
	5
	6	GCC is free software; you can redistribute it and/or modify
	7	it under the terms of the GNU General Public License as published by
8c4c00c1	8	the Free Software Foundation; either version 3, or (at your option)
4ee9c684	9	any later version.
	10
	11	GCC is distributed in the hope that it will be useful,
	12	but WITHOUT ANY WARRANTY; without even the implied warranty of
	13	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	14	GNU General Public License for more details.
	15
	16	You should have received a copy of the GNU General Public License
8c4c00c1	17	along with GCC; see the file COPYING3. If not see
8c4c00c1	18	<http://www.gnu.org/licenses/>. */
4ee9c684	19
	20	#include "config.h"
	21	#include "system.h"
	22	#include "coretypes.h"
9ef16211	23	#include "backend.h"
7c29e30e	24	#include "rtl.h"
4ee9c684	25	#include "tree.h"
9ef16211	26	#include "gimple.h"
7c29e30e	27	#include "tree-pass.h"
7c29e30e	28	#include "tm_p.h"
9ef16211	29	#include "ssa.h"
7c29e30e	30	#include "expmed.h"
	31	#include "insn-config.h"
	32	#include "emit-rtl.h"
	33	#include "gimple-pretty-print.h"
9ef16211	34	#include "alias.h"
b20a8bb4	35	#include "fold-const.h"
bc61cadb	36	#include "internal-fn.h"
dcf1a1ec	37	#include "gimple-iterator.h"
073c1fd5	38	#include "tree-cfg.h"
d53441c8	39	#include "flags.h"
d53441c8	40	#include "dojump.h"
	41	#include "explow.h"
	42	#include "calls.h"
d53441c8	43	#include "varasm.h"
d53441c8	44	#include "stmt.h"
9ed99284	45	#include "expr.h"
073c1fd5	46	#include "tree-dfa.h"
4ee9c684	47	#include "domwalk.h"
f0e4d727	48	#include "langhooks.h"
424a4a92	49	#include "tree-cfgcleanup.h"
4ee9c684	50
	51	/* This file implements dead store elimination.
	52
	53	A dead store is a store into a memory location which will later be
	54	overwritten by another store without any intervening loads. In this
	55	case the earlier store can be deleted.
	56
	57	In our SSA + virtual operand world we use immediate uses of virtual
	58	operands to detect dead stores. If a store's virtual definition
	59	is used precisely once by a later store to the same location which
48e1416a	60	post dominates the first store, then the first store is dead.
4ee9c684	61
	62	The single use of the store's virtual definition ensures that
	63	there are no intervening aliased loads and the requirement that
	64	the second load post dominate the first ensures that if the earlier
	65	store executes, then the later stores will execute before the function
	66	exits.
	67
	68	It may help to think of this as first moving the earlier store to
	69	the point immediately before the later store. Again, the single
2c763ed4	70	use of the virtual definition and the post-dominance relationship
48e1416a	71	ensure that such movement would be safe. Clearly if there are
4ee9c684	72	back to back stores, then the second is redundant.
	73
	74	Reviewing section 10.7.2 in Morgan's "Building an Optimizing Compiler"
	75	may also help in understanding this code since it discusses the
	76	relationship between dead store and redundant load elimination. In
	77	fact, they are the same transformation applied to different views of
	78	the CFG. */
75a70cf9	79
4ee9c684	80
d02c8339	81	/* Bitmap of blocks that have had EH statements cleaned. We should
	82	remove their dead edges eventually. */
	83	static bitmap need_eh_cleanup;
	84
4ee9c684	85
4fb5e5ca	86	/* A helper of dse_optimize_stmt.
258bd648	87	Given a GIMPLE_ASSIGN in STMT that writes to REF, find a candidate
258bd648	88	statement *USE_STMT that may prove STMT to be dead.
4fb5e5ca	89	Return TRUE if the above conditions are met, otherwise FALSE. */
	90
	91	static bool
42acab1c	92	dse_possible_dead_store_p (ao_ref ref, gimple stmt, gimple **use_stmt)
4fb5e5ca	93	{
42acab1c	94	gimple *temp;
dd277d48	95	unsigned cnt = 0;
4fb5e5ca	96
4fb5e5ca	97	*use_stmt = NULL;
4fb5e5ca	98
dd277d48	99	/* Find the first dominated statement that clobbers (part of) the
	100	memory stmt stores to with no intermediate statement that may use
	101	part of the memory stmt stores. That is, find a store that may
	102	prove stmt to be a dead store. */
	103	temp = stmt;
	104	do
	105	{
42acab1c	106	gimple use_stmt, defvar_def;
dd277d48	107	imm_use_iterator ui;
	108	bool fail = false;
	109	tree defvar;
	110
	111	/* Limit stmt walking to be linear in the number of possibly
	112	dead stores. */
	113	if (++cnt > 256)
	114	return false;
4fb5e5ca	115
75a70cf9	116	if (gimple_code (temp) == GIMPLE_PHI)
dd277d48	117	defvar = PHI_RESULT (temp);
	118	else
	119	defvar = gimple_vdef (temp);
48089971	120	defvar_def = temp;
dd277d48	121	temp = NULL;
dd277d48	122	FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar)
77ad2905	123	{
dd277d48	124	cnt++;
161fe168	125
43e2b34d	126	/* If we ever reach our DSE candidate stmt again fail. We
	127	cannot handle dead stores in loops. */
	128	if (use_stmt == stmt)
	129	{
	130	fail = true;
	131	BREAK_FROM_IMM_USE_STMT (ui);
	132	}
dd277d48	133	/* In simple cases we can look through PHI nodes, but we
	134	have to be careful with loops and with memory references
	135	containing operands that are also operands of PHI nodes.
	136	See gcc.c-torture/execute/20051110-.c. /
43e2b34d	137	else if (gimple_code (use_stmt) == GIMPLE_PHI)
dd277d48	138	{
dd277d48	139	if (temp
43e2b34d	140	/* Make sure we are not in a loop latch block. */
43e2b34d	141	\|\| gimple_bb (stmt) == gimple_bb (use_stmt)
dd277d48	142	\|\| dominated_by_p (CDI_DOMINATORS,
43e2b34d	143	gimple_bb (stmt), gimple_bb (use_stmt))
	144	/* We can look through PHIs to regions post-dominating
	145	the DSE candidate stmt. */
	146	\|\| !dominated_by_p (CDI_POST_DOMINATORS,
	147	gimple_bb (stmt), gimple_bb (use_stmt)))
dd277d48	148	{
	149	fail = true;
	150	BREAK_FROM_IMM_USE_STMT (ui);
	151	}
48089971	152	/* Do not consider the PHI as use if it dominates the
	153	stmt defining the virtual operand we are processing,
	154	we have processed it already in this case. */
	155	if (gimple_bb (defvar_def) != gimple_bb (use_stmt)
	156	&& !dominated_by_p (CDI_DOMINATORS,
	157	gimple_bb (defvar_def),
	158	gimple_bb (use_stmt)))
	159	temp = use_stmt;
dd277d48	160	}
dd277d48	161	/* If the statement is a use the store is not dead. */
258bd648	162	else if (ref_maybe_used_by_stmt_p (use_stmt, ref))
161fe168	163	{
161fe168	164	fail = true;
dd277d48	165	BREAK_FROM_IMM_USE_STMT (ui);
	166	}
	167	/* If this is a store, remember it or bail out if we have
	168	multiple ones (the will be in different CFG parts then). */
	169	else if (gimple_vdef (use_stmt))
	170	{
	171	if (temp)
	172	{
	173	fail = true;
	174	BREAK_FROM_IMM_USE_STMT (ui);
	175	}
	176	temp = use_stmt;
161fe168	177	}
	178	}
	179
dd277d48	180	if (fail)
	181	return false;
	182
	183	/* If we didn't find any definition this means the store is dead
	184	if it isn't a store to global reachable memory. In this case
	185	just pretend the stmt makes itself dead. Otherwise fail. */
	186	if (!temp)
4fb5e5ca	187	{
258bd648	188	if (ref_may_alias_global_p (ref))
dd277d48	189	return false;
	190
	191	temp = stmt;
789aa951	192	break;
4fb5e5ca	193	}
4fb5e5ca	194	}
88114c9f	195	/* Continue walking until we reach a kill. */
258bd648	196	while (!stmt_kills_ref_p (temp, ref));
4fb5e5ca	197
dd277d48	198	*use_stmt = temp;
4fb5e5ca	199
4fb5e5ca	200	return true;
	201	}
	202
	203
4ee9c684	204	/* Attempt to eliminate dead stores in the statement referenced by BSI.
	205
	206	A dead store is a store into a memory location which will later be
	207	overwritten by another store without any intervening loads. In this
	208	case the earlier store can be deleted.
	209
	210	In our SSA + virtual operand world we use immediate uses of virtual
	211	operands to detect dead stores. If a store's virtual definition
	212	is used precisely once by a later store to the same location which
	213	post dominates the first store, then the first store is dead. */
	214
	215	static void
3222e348	216	dse_optimize_stmt (gimple_stmt_iterator *gsi)
4ee9c684	217	{
42acab1c	218	gimple stmt = gsi_stmt (gsi);
4ee9c684	219
e920115e	220	/* If this statement has no virtual defs, then there is nothing
4ee9c684	221	to do. */
dd277d48	222	if (!gimple_vdef (stmt))
4ee9c684	223	return;
4ee9c684	224
9f559b20	225	/* Don't return early on this_2(D) ={v} {CLOBBER}. /
	226	if (gimple_has_volatile_ops (stmt)
	227	&& (!gimple_clobber_p (stmt)
	228	\|\| TREE_CODE (gimple_assign_lhs (stmt)) != MEM_REF))
52c2a307	229	return;
52c2a307	230
258bd648	231	/* We know we have virtual definitions. We can handle assignments and
	232	some builtin calls. */
	233	if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
	234	{
	235	switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt)))
	236	{
	237	case BUILT_IN_MEMCPY:
	238	case BUILT_IN_MEMMOVE:
	239	case BUILT_IN_MEMSET:
	240	{
42acab1c	241	gimple *use_stmt;
258bd648	242	ao_ref ref;
	243	tree size = NULL_TREE;
	244	if (gimple_call_num_args (stmt) == 3)
	245	size = gimple_call_arg (stmt, 2);
	246	tree ptr = gimple_call_arg (stmt, 0);
	247	ao_ref_init_from_ptr_and_size (&ref, ptr, size);
	248	if (!dse_possible_dead_store_p (&ref, stmt, &use_stmt))
	249	return;
	250
	251	if (dump_file && (dump_flags & TDF_DETAILS))
	252	{
	253	fprintf (dump_file, " Deleted dead call '");
	254	print_gimple_stmt (dump_file, gsi_stmt (*gsi), dump_flags, 0);
	255	fprintf (dump_file, "'\n");
	256	}
	257
	258	tree lhs = gimple_call_lhs (stmt);
	259	if (lhs)
	260	{
42acab1c	261	gimple *new_stmt = gimple_build_assign (lhs, ptr);
258bd648	262	unlink_stmt_vdef (stmt);
	263	if (gsi_replace (gsi, new_stmt, true))
	264	bitmap_set_bit (need_eh_cleanup, gimple_bb (stmt)->index);
	265	}
	266	else
	267	{
	268	/* Then we need to fix the operand of the consuming stmt. */
	269	unlink_stmt_vdef (stmt);
	270
	271	/* Remove the dead store. */
	272	if (gsi_remove (gsi, true))
	273	bitmap_set_bit (need_eh_cleanup, gimple_bb (stmt)->index);
b3c8ca24	274	release_defs (stmt);
258bd648	275	}
	276	break;
	277	}
	278	default:
	279	return;
	280	}
	281	}
	282
75a70cf9	283	if (is_gimple_assign (stmt))
4ee9c684	284	{
42acab1c	285	gimple *use_stmt;
4ee9c684	286
258bd648	287	/* Self-assignments are zombies. */
	288	if (operand_equal_p (gimple_assign_rhs1 (stmt),
	289	gimple_assign_lhs (stmt), 0))
	290	use_stmt = stmt;
	291	else
	292	{
	293	ao_ref ref;
	294	ao_ref_init (&ref, gimple_assign_lhs (stmt));
	295	if (!dse_possible_dead_store_p (&ref, stmt, &use_stmt))
	296	return;
	297	}
2bf1fefd	298
88114c9f	299	/* Now we know that use_stmt kills the LHS of stmt. */
88114c9f	300
9f559b20	301	/* But only remove *this_2(D) ={v} {CLOBBER} if killed by
	302	another clobber stmt. */
	303	if (gimple_clobber_p (stmt)
	304	&& !gimple_clobber_p (use_stmt))
	305	return;
	306
88114c9f	307	if (dump_file && (dump_flags & TDF_DETAILS))
4ee9c684	308	{
88114c9f	309	fprintf (dump_file, " Deleted dead store '");
	310	print_gimple_stmt (dump_file, gsi_stmt (*gsi), dump_flags, 0);
	311	fprintf (dump_file, "'\n");
4ee9c684	312	}
88114c9f	313
	314	/* Then we need to fix the operand of the consuming stmt. */
	315	unlink_stmt_vdef (stmt);
	316
	317	/* Remove the dead store. */
258bd648	318	basic_block bb = gimple_bb (stmt);
88114c9f	319	if (gsi_remove (gsi, true))
	320	bitmap_set_bit (need_eh_cleanup, bb->index);
	321
	322	/* And release any SSA_NAMEs set in this statement back to the
	323	SSA_NAME manager. */
	324	release_defs (stmt);
4ee9c684	325	}
	326	}
	327
54c91640	328	class dse_dom_walker : public dom_walker
	329	{
	330	public:
	331	dse_dom_walker (cdi_direction direction) : dom_walker (direction) {}
	332
	333	virtual void before_dom_children (basic_block);
	334	};
	335
	336	void
	337	dse_dom_walker::before_dom_children (basic_block bb)
4ee9c684	338	{
75a70cf9	339	gimple_stmt_iterator gsi;
4ee9c684	340
3222e348	341	for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
	342	{
	343	dse_optimize_stmt (&gsi);
	344	if (gsi_end_p (gsi))
	345	gsi = gsi_last_bb (bb);
	346	else
	347	gsi_prev (&gsi);
	348	}
4ee9c684	349	}
4ee9c684	350
7620bc82	351	namespace {
	352
	353	const pass_data pass_data_dse =
65b0537f	354	{
	355	GIMPLE_PASS, /* type */
	356	"dse", /* name */
	357	OPTGROUP_NONE, /* optinfo_flags */
65b0537f	358	TV_TREE_DSE, /* tv_id */
	359	( PROP_cfg \| PROP_ssa ), /* properties_required */
	360	0, /* properties_provided */
	361	0, /* properties_destroyed */
	362	0, /* todo_flags_start */
8b88439e	363	0, /* todo_flags_finish */
65b0537f	364	};
65b0537f	365
7620bc82	366	class pass_dse : public gimple_opt_pass
65b0537f	367	{
	368	public:
	369	pass_dse (gcc::context *ctxt)
	370	: gimple_opt_pass (pass_data_dse, ctxt)
	371	{}
	372
	373	/* opt_pass methods: */
	374	opt_pass * clone () { return new pass_dse (m_ctxt); }
	375	virtual bool gate (function *) { return flag_tree_dse != 0; }
	376	virtual unsigned int execute (function *);
	377
	378	}; // class pass_dse
4fb5e5ca	379
65b0537f	380	unsigned int
65b0537f	381	pass_dse::execute (function *fun)
4ee9c684	382	{
d02c8339	383	need_eh_cleanup = BITMAP_ALLOC (NULL);
d02c8339	384
ec415c45	385	renumber_gimple_stmt_uids ();
4ee9c684	386
	387	/* We might consider making this a property of each pass so that it
	388	can be [re]computed on an as-needed basis. Particularly since
	389	this pass could be seen as an extension of DCE which needs post
	390	dominators. */
	391	calculate_dominance_info (CDI_POST_DOMINATORS);
dd277d48	392	calculate_dominance_info (CDI_DOMINATORS);
4ee9c684	393
4ee9c684	394	/* Dead store elimination is fundamentally a walk of the post-dominator
4ee9c684	395	tree and a backwards walk of statements within each block. */
65b0537f	396	dse_dom_walker (CDI_POST_DOMINATORS).walk (fun->cfg->x_exit_block_ptr);
4ee9c684	397
d02c8339	398	/* Removal of stores may make some EH edges dead. Purge such edges from
	399	the CFG as needed. */
	400	if (!bitmap_empty_p (need_eh_cleanup))
	401	{
	402	gimple_purge_all_dead_eh_edges (need_eh_cleanup);
	403	cleanup_tree_cfg ();
	404	}
	405
	406	BITMAP_FREE (need_eh_cleanup);
	407
4ee9c684	408	/* For now, just wipe the post-dominator information. */
4ee9c684	409	free_dominance_info (CDI_POST_DOMINATORS);
2a1990e9	410	return 0;
4ee9c684	411	}
4ee9c684	412
7620bc82	413	} // anon namespace
7620bc82	414
cbe8bda8	415	gimple_opt_pass *
	416	make_pass_dse (gcc::context *ctxt)
	417	{
	418	return new pass_dse (ctxt);
	419	}