[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, 59 Temple Place - Suite 330,
Boston, MA 02111-1307, USA.  */

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "errors.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;
}

/* Function indicating whether we ought to include information for 'var'
   when calculating immediate uses.  For this pass we only want use
   information for virtual variables.  */

static bool
need_imm_uses_for (tree var)
{
  return !is_gimple_reg (var);
}


/* 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
    = VARRAY_TOP_GENERIC_PTR (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
    = VARRAY_TOP_GENERIC_PTR (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);
  v_may_def_optype v_may_defs;

  get_stmt_operands (stmt);
  v_may_defs = V_MAY_DEF_OPS (ann);

  /* If this statement has no virtual uses, then there is nothing
     to do.  */
  if (NUM_V_MAY_DEFS (v_may_defs) == 0)
    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)
    {
      unsigned int num_uses = 0, count = 0;
      use_operand_p first_use_p = NULL_USE_OPERAND_P;
      use_operand_p use_p;
      tree use, use_stmt;
      tree defvar = NULL_TREE, usevar = NULL_TREE;
      use_operand_p var2;
      def_operand_p var1;
      ssa_op_iter op_iter;

      FOR_EACH_SSA_MAYDEF_OPERAND (var1, var2, stmt, op_iter)
        {
	  defvar = DEF_FROM_PTR (var1);
	  usevar = USE_FROM_PTR (var2);
	  num_uses += num_imm_uses (defvar);
	  count++;
	  if (num_uses > 1 || count > 1)
	    break;
	}

      if (count == 1 && num_uses == 1)
        {
	  single_imm_use (defvar, &use_p, &use_stmt);
	  gcc_assert (use_p != NULL_USE_OPERAND_P);
	  first_use_p = use_p;
	  use = USE_FROM_PTR (use_p);
	}
      else
	{
	  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_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))
	{
	  /* 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);

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