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

/* Dead store elimination
   Copyright (C) 2004, 2005 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 2, 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 COPYING.  If not, write to
the Free Software Foundation, 51 Franklin Street, Fifth Floor,
Boston, MA 02110-1301, USA.  */

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "ggc.h"
#include "tree.h"
#include "rtl.h"
#include "tm_p.h"
#include "basic-block.h"
#include "timevar.h"
#include "diagnostic.h"
#include "tree-flow.h"
#include "tree-pass.h"
#include "tree-dump.h"
#include "domwalk.h"
#include "flags.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.  */
   

struct dse_global_data
{
  /* This is the global bitmap for store statements.

     Each statement has a unique ID.  When we encounter a store statement
     that we want to record, set the bit corresponding to the statement's
     unique ID in this bitmap.  */
  bitmap stores;
};

/* We allocate a bitmap-per-block for stores which are encountered
   during the scan of that block.  This allows us to restore the 
   global bitmap of stores when we finish processing a block.  */
struct dse_block_local_data
{
  bitmap stores;
};

static bool gate_dse (void);
static void tree_ssa_dse (void);
static void dse_initialize_block_local_data (struct dom_walk_data *,
					     basic_block,
					     bool);
static void dse_optimize_stmt (struct dom_walk_data *,
			       basic_block,
			       block_stmt_iterator);
static void dse_record_phis (struct dom_walk_data *, basic_block);
static void dse_finalize_block (struct dom_walk_data *, basic_block);
static void record_voperand_set (bitmap, bitmap *, unsigned int);

static unsigned max_stmt_uid;	/* Maximal uid of a statement.  Uids to phi
				   nodes are assigned using the versions of
				   ssa names they define.  */

/* Returns uid of statement STMT.  */

static unsigned
get_stmt_uid (tree stmt)
{
  if (TREE_CODE (stmt) == PHI_NODE)
    return SSA_NAME_VERSION (PHI_RESULT (stmt)) + max_stmt_uid;

  return stmt_ann (stmt)->uid;
}

/* Set bit UID in bitmaps GLOBAL and *LOCAL, creating *LOCAL as needed.  */

static void
record_voperand_set (bitmap global, bitmap *local, unsigned int uid)
{
  /* Lazily allocate the bitmap.  Note that we do not get a notification
     when the block local data structures die, so we allocate the local
     bitmap backed by the GC system.  */
  if (*local == NULL)
    *local = BITMAP_GGC_ALLOC ();

  /* Set the bit in the local and global bitmaps.  */
  bitmap_set_bit (*local, uid);
  bitmap_set_bit (global, uid);
}

/* Initialize block local data structures.  */

static void
dse_initialize_block_local_data (struct dom_walk_data *walk_data,
				 basic_block bb ATTRIBUTE_UNUSED,
				 bool recycled)
{
  struct dse_block_local_data *bd
    = VEC_last (void_p, walk_data->block_data_stack);

  /* If we are given a recycled block local data structure, ensure any
     bitmap associated with the block is cleared.  */
  if (recycled)
    {
      if (bd->stores)
	bitmap_clear (bd->stores);
    }
}

/* 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 (struct dom_walk_data *walk_data,
		   basic_block bb ATTRIBUTE_UNUSED,
		   block_stmt_iterator bsi)
{
  struct dse_block_local_data *bd
    = VEC_last (void_p, walk_data->block_data_stack);
  struct dse_global_data *dse_gd = walk_data->global_data;
  tree stmt = bsi_stmt (bsi);
  stmt_ann_t ann = stmt_ann (stmt);

  /* If this statement has no virtual defs, then there is nothing
     to do.  */
  if (ZERO_SSA_OPERANDS (stmt, (SSA_OP_VMAYDEF|SSA_OP_VMUSTDEF)))
    return;

  /* We know we have virtual definitions.  If this is a MODIFY_EXPR that's
     not also a function call, then record it into our table.  */
  if (get_call_expr_in (stmt))
    return;

  if (ann->has_volatile_ops)
    return;

  if (TREE_CODE (stmt) == MODIFY_EXPR)
    {
      use_operand_p first_use_p = NULL_USE_OPERAND_P;
      use_operand_p use_p = NULL;
      tree use, use_stmt, temp;
      tree defvar = NULL_TREE, usevar = NULL_TREE;
      bool fail = false;
      use_operand_p var2;
      def_operand_p var1;
      ssa_op_iter op_iter;

      /* We want to verify that each virtual definition in STMT has
	 precisely one use and that all the virtual definitions are
	 used by the same single statement.  When complete, we
	 want USE_STMT to refer to the one statement which uses
	 all of the virtual definitions from STMT.  */
      use_stmt = NULL;
      FOR_EACH_SSA_MUST_AND_MAY_DEF_OPERAND (var1, var2, stmt, op_iter)
	{
	  defvar = DEF_FROM_PTR (var1);
	  usevar = USE_FROM_PTR (var2);

	  /* If this virtual def does not have precisely one use, then
	     we will not be able to eliminate STMT.  */
	  if (num_imm_uses (defvar) != 1)
	    {
	      fail = true;
	      break;
	    }

	  /* Get the one and only immediate use of DEFVAR.  */
	  single_imm_use (defvar, &use_p, &temp);
	  gcc_assert (use_p != NULL_USE_OPERAND_P);
	  first_use_p = use_p;
	  use = USE_FROM_PTR (use_p);

	  /* If the immediate use of DEF_VAR is not the same as the
	     previously find immediate uses, then we will not be able
	     to eliminate STMT.  */
	  if (use_stmt == NULL)
	    use_stmt = temp;
	  else if (temp != use_stmt)
	    {
	      fail = true;
	      break;
	    }
	}

      if (fail)
	{
	  record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
	  return;
	}

      /* Skip through any PHI nodes we have already seen if the PHI
	 represents the only use of this store.

	 Note this does not handle the case where the store has
	 multiple V_{MAY,MUST}_DEFs which all reach a set of PHI nodes in the
	 same block.  */
      while (use_p != NULL_USE_OPERAND_P
	     && TREE_CODE (use_stmt) == PHI_NODE
	     && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt)))
	{
	  /* Skip past this PHI and loop again in case we had a PHI
	     chain.  */
	  if (single_imm_use (PHI_RESULT (use_stmt), &use_p, &use_stmt))
	    use = USE_FROM_PTR (use_p);
	}

      /* If we have precisely one immediate use at this point, then we may
	 have found redundant store.  */
      if (use_p != NULL_USE_OPERAND_P
	  && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt))
	  && operand_equal_p (TREE_OPERAND (stmt, 0),
			      TREE_OPERAND (use_stmt, 0), 0))
	{
	  tree def;
	  ssa_op_iter iter;

	  /* Make sure we propagate the ABNORMAL bit setting.  */
	  if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (first_use_p)))
	    SSA_NAME_OCCURS_IN_ABNORMAL_PHI (usevar) = 1;
	  /* Then we need to fix the operand of the consuming stmt.  */
	  SET_USE (first_use_p, usevar);

	  if (dump_file && (dump_flags & TDF_DETAILS))
            {
              fprintf (dump_file, "  Deleted dead store '");
              print_generic_expr (dump_file, bsi_stmt (bsi), dump_flags);
              fprintf (dump_file, "'\n");
            }

	  /* Remove the dead store.  */
	  bsi_remove (&bsi);

	  /* The virtual defs for the dead statement will need to be
	     updated.  Since these names are going to disappear,
	     FUD chains for uses downstream need to be updated.  */
	  FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_VIRTUAL_DEFS)
	    mark_sym_for_renaming (SSA_NAME_VAR (def));

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

      record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
    }
}

/* Record that we have seen the PHIs at the start of BB which correspond
   to virtual operands.  */
static void
dse_record_phis (struct dom_walk_data *walk_data, basic_block bb)
{
  struct dse_block_local_data *bd
    = VEC_last (void_p, walk_data->block_data_stack);
  struct dse_global_data *dse_gd = walk_data->global_data;
  tree phi;

  for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
    if (!is_gimple_reg (PHI_RESULT (phi)))
      record_voperand_set (dse_gd->stores,
			   &bd->stores,
			   get_stmt_uid (phi));
}

static void
dse_finalize_block (struct dom_walk_data *walk_data,
		    basic_block bb ATTRIBUTE_UNUSED)
{
  struct dse_block_local_data *bd
    = VEC_last (void_p, walk_data->block_data_stack);
  struct dse_global_data *dse_gd = walk_data->global_data;
  bitmap stores = dse_gd->stores;
  unsigned int i;
  bitmap_iterator bi;

  /* Unwind the stores noted in this basic block.  */
  if (bd->stores)
    EXECUTE_IF_SET_IN_BITMAP (bd->stores, 0, i, bi)
      {
	bitmap_clear_bit (stores, i);
      }
}

static void
tree_ssa_dse (void)
{
  struct dom_walk_data walk_data;
  struct dse_global_data dse_gd;
  basic_block bb;

  /* Create a UID for each statement in the function.  Ordering of the
     UIDs is not important for this pass.  */
  max_stmt_uid = 0;
  FOR_EACH_BB (bb)
    {
      block_stmt_iterator bsi;

      for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
	stmt_ann (bsi_stmt (bsi))->uid = max_stmt_uid++;
    }

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

  /* Dead store elimination is fundamentally a walk of the post-dominator
     tree and a backwards walk of statements within each block.  */
  walk_data.walk_stmts_backward = true;
  walk_data.dom_direction = CDI_POST_DOMINATORS;
  walk_data.initialize_block_local_data = dse_initialize_block_local_data;
  walk_data.before_dom_children_before_stmts = NULL;
  walk_data.before_dom_children_walk_stmts = dse_optimize_stmt;
  walk_data.before_dom_children_after_stmts = dse_record_phis;
  walk_data.after_dom_children_before_stmts = NULL;
  walk_data.after_dom_children_walk_stmts = NULL;
  walk_data.after_dom_children_after_stmts = dse_finalize_block;
  walk_data.interesting_blocks = NULL;

  walk_data.block_local_data_size = sizeof (struct dse_block_local_data);

  /* This is the main hash table for the dead store elimination pass.  */
  dse_gd.stores = BITMAP_ALLOC (NULL);
  walk_data.global_data = &dse_gd;

  /* Initialize the dominator walker.  */
  init_walk_dominator_tree (&walk_data);

  /* Recursively walk the dominator tree.  */
  walk_dominator_tree (&walk_data, EXIT_BLOCK_PTR);

  /* Finalize the dominator walker.  */
  fini_walk_dominator_tree (&walk_data);

  /* Release the main bitmap.  */
  BITMAP_FREE (dse_gd.stores);

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

static bool
gate_dse (void)
{
  return flag_tree_dse != 0;
}

struct tree_opt_pass pass_dse = {
  "dse",			/* name */
  gate_dse,			/* gate */
  tree_ssa_dse,			/* execute */
  NULL,				/* sub */
  NULL,				/* next */
  0,				/* static_pass_number */
  TV_TREE_DSE,			/* tv_id */
  PROP_cfg
    | PROP_ssa
    | PROP_alias,		/* properties_required */
  0,				/* properties_provided */
  0,				/* properties_destroyed */
  0,				/* todo_flags_start */
  TODO_dump_func
    | TODO_ggc_collect
    | TODO_update_ssa
    | TODO_verify_ssa,		/* todo_flags_finish */
  0				/* letter */
};
Commit	Line	Data
6de9cd9a	1	/* Dead store elimination
ad616de1	2	Copyright (C) 2004, 2005 Free Software Foundation, Inc.
6de9cd9a DN	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
	8	the Free Software Foundation; either version 2, or (at your option)
	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
	17	along with GCC; see the file COPYING. If not, write to
366ccddb KC	18	the Free Software Foundation, 51 Franklin Street, Fifth Floor,
366ccddb KC	19	Boston, MA 02110-1301, USA. */
6de9cd9a DN	20
	21	#include "config.h"
	22	#include "system.h"
	23	#include "coretypes.h"
	24	#include "tm.h"
6de9cd9a DN	25	#include "ggc.h"
	26	#include "tree.h"
	27	#include "rtl.h"
	28	#include "tm_p.h"
	29	#include "basic-block.h"
	30	#include "timevar.h"
	31	#include "diagnostic.h"
	32	#include "tree-flow.h"
	33	#include "tree-pass.h"
	34	#include "tree-dump.h"
	35	#include "domwalk.h"
	36	#include "flags.h"
	37
	38	/* This file implements dead store elimination.
	39
	40	A dead store is a store into a memory location which will later be
	41	overwritten by another store without any intervening loads. In this
	42	case the earlier store can be deleted.
	43
	44	In our SSA + virtual operand world we use immediate uses of virtual
	45	operands to detect dead stores. If a store's virtual definition
	46	is used precisely once by a later store to the same location which
	47	post dominates the first store, then the first store is dead.
	48
	49	The single use of the store's virtual definition ensures that
	50	there are no intervening aliased loads and the requirement that
	51	the second load post dominate the first ensures that if the earlier
	52	store executes, then the later stores will execute before the function
	53	exits.
	54
	55	It may help to think of this as first moving the earlier store to
	56	the point immediately before the later store. Again, the single
61ada8ae	57	use of the virtual definition and the post-dominance relationship
6de9cd9a DN	58	ensure that such movement would be safe. Clearly if there are
	59	back to back stores, then the second is redundant.
	60
	61	Reviewing section 10.7.2 in Morgan's "Building an Optimizing Compiler"
	62	may also help in understanding this code since it discusses the
	63	relationship between dead store and redundant load elimination. In
	64	fact, they are the same transformation applied to different views of
	65	the CFG. */
	66
	67
	68	struct dse_global_data
	69	{
	70	/* This is the global bitmap for store statements.
	71
	72	Each statement has a unique ID. When we encounter a store statement
	73	that we want to record, set the bit corresponding to the statement's
	74	unique ID in this bitmap. */
	75	bitmap stores;
	76	};
	77
	78	/* We allocate a bitmap-per-block for stores which are encountered
	79	during the scan of that block. This allows us to restore the
	80	global bitmap of stores when we finish processing a block. */
	81	struct dse_block_local_data
	82	{
	83	bitmap stores;
	84	};
	85
	86	static bool gate_dse (void);
	87	static void tree_ssa_dse (void);
	88	static void dse_initialize_block_local_data (struct dom_walk_data *,
	89	basic_block,
	90	bool);
	91	static void dse_optimize_stmt (struct dom_walk_data *,
	92	basic_block,
	93	block_stmt_iterator);
	94	static void dse_record_phis (struct dom_walk_data *, basic_block);
	95	static void dse_finalize_block (struct dom_walk_data *, basic_block);
6de9cd9a DN	96	static void record_voperand_set (bitmap, bitmap *, unsigned int);
6de9cd9a DN	97
30d396e3 ZD	98	static unsigned max_stmt_uid; /* Maximal uid of a statement. Uids to phi
	99	nodes are assigned using the versions of
	100	ssa names they define. */
	101
	102	/* Returns uid of statement STMT. */
	103
	104	static unsigned
	105	get_stmt_uid (tree stmt)
	106	{
	107	if (TREE_CODE (stmt) == PHI_NODE)
	108	return SSA_NAME_VERSION (PHI_RESULT (stmt)) + max_stmt_uid;
	109
	110	return stmt_ann (stmt)->uid;
	111	}
	112
6de9cd9a	113	/* Set bit UID in bitmaps GLOBAL and LOCAL, creating LOCAL as needed. */
db30731a	114
6de9cd9a DN	115	static void
	116	record_voperand_set (bitmap global, bitmap *local, unsigned int uid)
	117	{
	118	/* Lazily allocate the bitmap. Note that we do not get a notification
	119	when the block local data structures die, so we allocate the local
	120	bitmap backed by the GC system. */
	121	if (*local == NULL)
	122	*local = BITMAP_GGC_ALLOC ();
	123
	124	/* Set the bit in the local and global bitmaps. */
	125	bitmap_set_bit (*local, uid);
	126	bitmap_set_bit (global, uid);
	127	}
db30731a	128
6de9cd9a DN	129	/* Initialize block local data structures. */
	130
	131	static void
	132	dse_initialize_block_local_data (struct dom_walk_data *walk_data,
	133	basic_block bb ATTRIBUTE_UNUSED,
	134	bool recycled)
	135	{
	136	struct dse_block_local_data *bd
ea497bb8	137	= VEC_last (void_p, walk_data->block_data_stack);
6de9cd9a DN	138
	139	/* If we are given a recycled block local data structure, ensure any
	140	bitmap associated with the block is cleared. */
	141	if (recycled)
	142	{
	143	if (bd->stores)
	144	bitmap_clear (bd->stores);
	145	}
	146	}
	147
	148	/* Attempt to eliminate dead stores in the statement referenced by BSI.
	149
	150	A dead store is a store into a memory location which will later be
	151	overwritten by another store without any intervening loads. In this
	152	case the earlier store can be deleted.
	153
	154	In our SSA + virtual operand world we use immediate uses of virtual
	155	operands to detect dead stores. If a store's virtual definition
	156	is used precisely once by a later store to the same location which
	157	post dominates the first store, then the first store is dead. */
	158
	159	static void
	160	dse_optimize_stmt (struct dom_walk_data *walk_data,
	161	basic_block bb ATTRIBUTE_UNUSED,
	162	block_stmt_iterator bsi)
	163	{
	164	struct dse_block_local_data *bd
ea497bb8	165	= VEC_last (void_p, walk_data->block_data_stack);
6de9cd9a DN	166	struct dse_global_data *dse_gd = walk_data->global_data;
	167	tree stmt = bsi_stmt (bsi);
	168	stmt_ann_t ann = stmt_ann (stmt);
6de9cd9a	169
773168c7	170	/* If this statement has no virtual defs, then there is nothing
6de9cd9a	171	to do. */
f47c96aa	172	if (ZERO_SSA_OPERANDS (stmt, (SSA_OP_VMAYDEF\|SSA_OP_VMUSTDEF)))
6de9cd9a DN	173	return;
6de9cd9a DN	174
cd709752 RH	175	/* We know we have virtual definitions. If this is a MODIFY_EXPR that's
	176	not also a function call, then record it into our table. */
	177	if (get_call_expr_in (stmt))
	178	return;
e79b60a7 DN	179
	180	if (ann->has_volatile_ops)
	181	return;
	182
cd709752	183	if (TREE_CODE (stmt) == MODIFY_EXPR)
6de9cd9a	184	{
f430bae8	185	use_operand_p first_use_p = NULL_USE_OPERAND_P;
db30731a JL	186	use_operand_p use_p = NULL;
db30731a JL	187	tree use, use_stmt, temp;
f430bae8	188	tree defvar = NULL_TREE, usevar = NULL_TREE;
db30731a	189	bool fail = false;
f430bae8 AM	190	use_operand_p var2;
	191	def_operand_p var1;
	192	ssa_op_iter op_iter;
	193
db30731a JL	194	/* We want to verify that each virtual definition in STMT has
	195	precisely one use and that all the virtual definitions are
	196	used by the same single statement. When complete, we
0fa2e4df	197	want USE_STMT to refer to the one statement which uses
db30731a JL	198	all of the virtual definitions from STMT. */
	199	use_stmt = NULL;
	200	FOR_EACH_SSA_MUST_AND_MAY_DEF_OPERAND (var1, var2, stmt, op_iter)
	201	{
f430bae8 AM	202	defvar = DEF_FROM_PTR (var1);
f430bae8 AM	203	usevar = USE_FROM_PTR (var2);
6de9cd9a	204
db30731a JL	205	/* If this virtual def does not have precisely one use, then
	206	we will not be able to eliminate STMT. */
	207	if (num_imm_uses (defvar) != 1)
	208	{
	209	fail = true;
	210	break;
	211	}
	212
	213	/* Get the one and only immediate use of DEFVAR. */
	214	single_imm_use (defvar, &use_p, &temp);
f430bae8 AM	215	gcc_assert (use_p != NULL_USE_OPERAND_P);
	216	first_use_p = use_p;
	217	use = USE_FROM_PTR (use_p);
db30731a JL	218
	219	/* If the immediate use of DEF_VAR is not the same as the
	220	previously find immediate uses, then we will not be able
	221	to eliminate STMT. */
	222	if (use_stmt == NULL)
	223	use_stmt = temp;
	224	else if (temp != use_stmt)
	225	{
	226	fail = true;
	227	break;
	228	}
f430bae8	229	}
db30731a JL	230
db30731a JL	231	if (fail)
6de9cd9a DN	232	{
	233	record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
	234	return;
	235	}
	236
6de9cd9a DN	237	/* Skip through any PHI nodes we have already seen if the PHI
	238	represents the only use of this store.
	239
	240	Note this does not handle the case where the store has
db30731a	241	multiple V_{MAY,MUST}_DEFs which all reach a set of PHI nodes in the
6de9cd9a	242	same block. */
f430bae8 AM	243	while (use_p != NULL_USE_OPERAND_P
	244	&& TREE_CODE (use_stmt) == PHI_NODE
	245	&& bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt)))
6de9cd9a	246	{
6de9cd9a DN	247	/* Skip past this PHI and loop again in case we had a PHI
6de9cd9a DN	248	chain. */
f430bae8 AM	249	if (single_imm_use (PHI_RESULT (use_stmt), &use_p, &use_stmt))
f430bae8 AM	250	use = USE_FROM_PTR (use_p);
6de9cd9a DN	251	}
	252
	253	/* If we have precisely one immediate use at this point, then we may
	254	have found redundant store. */
f430bae8 AM	255	if (use_p != NULL_USE_OPERAND_P
f430bae8 AM	256	&& bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt))
6de9cd9a	257	&& operand_equal_p (TREE_OPERAND (stmt, 0),
f430bae8	258	TREE_OPERAND (use_stmt, 0), 0))
6de9cd9a	259	{
0bca51f0 DN	260	tree def;
	261	ssa_op_iter iter;
	262
f430bae8 AM	263	/* Make sure we propagate the ABNORMAL bit setting. */
	264	if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (first_use_p)))
	265	SSA_NAME_OCCURS_IN_ABNORMAL_PHI (usevar) = 1;
	266	/* Then we need to fix the operand of the consuming stmt. */
	267	SET_USE (first_use_p, usevar);
6de9cd9a DN	268
	269	if (dump_file && (dump_flags & TDF_DETAILS))
	270	{
	271	fprintf (dump_file, " Deleted dead store '");
	272	print_generic_expr (dump_file, bsi_stmt (bsi), dump_flags);
	273	fprintf (dump_file, "'\n");
	274	}
	275
f430bae8 AM	276	/* Remove the dead store. */
f430bae8 AM	277	bsi_remove (&bsi);
a5c965c1	278
0bca51f0 DN	279	/* The virtual defs for the dead statement will need to be
	280	updated. Since these names are going to disappear,
	281	FUD chains for uses downstream need to be updated. */
	282	FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_VIRTUAL_DEFS)
	283	mark_sym_for_renaming (SSA_NAME_VAR (def));
	284
a5c965c1 JL	285	/* And release any SSA_NAMEs set in this statement back to the
	286	SSA_NAME manager. */
	287	release_defs (stmt);
6de9cd9a DN	288	}
	289
	290	record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
	291	}
	292	}
	293
	294	/* Record that we have seen the PHIs at the start of BB which correspond
	295	to virtual operands. */
	296	static void
	297	dse_record_phis (struct dom_walk_data *walk_data, basic_block bb)
	298	{
	299	struct dse_block_local_data *bd
ea497bb8	300	= VEC_last (void_p, walk_data->block_data_stack);
6de9cd9a DN	301	struct dse_global_data *dse_gd = walk_data->global_data;
	302	tree phi;
	303
17192884	304	for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
db30731a	305	if (!is_gimple_reg (PHI_RESULT (phi)))
6de9cd9a DN	306	record_voperand_set (dse_gd->stores,
6de9cd9a DN	307	&bd->stores,
30d396e3	308	get_stmt_uid (phi));
6de9cd9a DN	309	}
	310
	311	static void
	312	dse_finalize_block (struct dom_walk_data *walk_data,
	313	basic_block bb ATTRIBUTE_UNUSED)
	314	{
	315	struct dse_block_local_data *bd
ea497bb8	316	= VEC_last (void_p, walk_data->block_data_stack);
6de9cd9a DN	317	struct dse_global_data *dse_gd = walk_data->global_data;
	318	bitmap stores = dse_gd->stores;
	319	unsigned int i;
87c476a2	320	bitmap_iterator bi;
6de9cd9a DN	321
	322	/* Unwind the stores noted in this basic block. */
	323	if (bd->stores)
87c476a2 ZD	324	EXECUTE_IF_SET_IN_BITMAP (bd->stores, 0, i, bi)
	325	{
	326	bitmap_clear_bit (stores, i);
	327	}
6de9cd9a DN	328	}
	329
	330	static void
	331	tree_ssa_dse (void)
	332	{
	333	struct dom_walk_data walk_data;
	334	struct dse_global_data dse_gd;
6de9cd9a DN	335	basic_block bb;
	336
	337	/* Create a UID for each statement in the function. Ordering of the
	338	UIDs is not important for this pass. */
30d396e3	339	max_stmt_uid = 0;
6de9cd9a DN	340	FOR_EACH_BB (bb)
	341	{
	342	block_stmt_iterator bsi;
6de9cd9a DN	343
6de9cd9a DN	344	for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
30d396e3	345	stmt_ann (bsi_stmt (bsi))->uid = max_stmt_uid++;
6de9cd9a DN	346	}
	347
	348	/* We might consider making this a property of each pass so that it
	349	can be [re]computed on an as-needed basis. Particularly since
	350	this pass could be seen as an extension of DCE which needs post
	351	dominators. */
	352	calculate_dominance_info (CDI_POST_DOMINATORS);
	353
6de9cd9a DN	354	/* Dead store elimination is fundamentally a walk of the post-dominator
	355	tree and a backwards walk of statements within each block. */
	356	walk_data.walk_stmts_backward = true;
	357	walk_data.dom_direction = CDI_POST_DOMINATORS;
	358	walk_data.initialize_block_local_data = dse_initialize_block_local_data;
	359	walk_data.before_dom_children_before_stmts = NULL;
	360	walk_data.before_dom_children_walk_stmts = dse_optimize_stmt;
	361	walk_data.before_dom_children_after_stmts = dse_record_phis;
	362	walk_data.after_dom_children_before_stmts = NULL;
	363	walk_data.after_dom_children_walk_stmts = NULL;
	364	walk_data.after_dom_children_after_stmts = dse_finalize_block;
0bca51f0	365	walk_data.interesting_blocks = NULL;
6de9cd9a DN	366
	367	walk_data.block_local_data_size = sizeof (struct dse_block_local_data);
	368
	369	/* This is the main hash table for the dead store elimination pass. */
8bdbfff5	370	dse_gd.stores = BITMAP_ALLOC (NULL);
6de9cd9a DN	371	walk_data.global_data = &dse_gd;
	372
	373	/* Initialize the dominator walker. */
	374	init_walk_dominator_tree (&walk_data);
	375
	376	/* Recursively walk the dominator tree. */
	377	walk_dominator_tree (&walk_data, EXIT_BLOCK_PTR);
	378
	379	/* Finalize the dominator walker. */
	380	fini_walk_dominator_tree (&walk_data);
	381
	382	/* Release the main bitmap. */
8bdbfff5	383	BITMAP_FREE (dse_gd.stores);
6de9cd9a	384
6de9cd9a DN	385	/* For now, just wipe the post-dominator information. */
	386	free_dominance_info (CDI_POST_DOMINATORS);
	387	}
	388
	389	static bool
	390	gate_dse (void)
	391	{
	392	return flag_tree_dse != 0;
	393	}
	394
	395	struct tree_opt_pass pass_dse = {
	396	"dse", /* name */
	397	gate_dse, /* gate */
	398	tree_ssa_dse, /* execute */
	399	NULL, /* sub */
	400	NULL, /* next */
	401	0, /* static_pass_number */
	402	TV_TREE_DSE, /* tv_id */
0bca51f0 DN	403	PROP_cfg
0bca51f0 DN	404	\| PROP_ssa
c1b763fa	405	\| PROP_alias, /* properties_required */
6de9cd9a DN	406	0, /* properties_provided */
	407	0, /* properties_destroyed */
	408	0, /* todo_flags_start */
0bca51f0 DN	409	TODO_dump_func
	410	\| TODO_ggc_collect
	411	\| TODO_update_ssa
	412	\| TODO_verify_ssa, /* todo_flags_finish */
	413	0 /* letter */
6de9cd9a	414	};