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

/* Dead store elimination
   Copyright (C) 2004 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 fix_phi_uses (tree, tree);
static void fix_stmt_v_may_defs (tree, tree);
static void record_voperand_set (bitmap, bitmap *, unsigned int);

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


/* Replace uses in PHI which match V_MAY_DEF_RESULTs in STMT with the 
   corresponding V_MAY_DEF_OP in STMT.  */

static void
fix_phi_uses (tree phi, tree stmt)
{
  stmt_ann_t ann = stmt_ann (stmt);
  v_may_def_optype v_may_defs;
  unsigned int i;
  int j;

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

  /* Walk each V_MAY_DEF in STMT.  */
  for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
    {
      tree v_may_def = V_MAY_DEF_RESULT (v_may_defs, i);

      /* Find any uses in the PHI which match V_MAY_DEF and replace
	 them with the appropriate V_MAY_DEF_OP.  */
      for (j = 0; j < PHI_NUM_ARGS (phi); j++)
	if (v_may_def == PHI_ARG_DEF (phi, j))
	  SET_PHI_ARG_DEF (phi, j, V_MAY_DEF_OP (v_may_defs, i));
    }
}

/* Replace the V_MAY_DEF_OPs in STMT1 which match V_MAY_DEF_RESULTs 
   in STMT2 with the appropriate V_MAY_DEF_OPs from STMT2.  */

static void
fix_stmt_v_may_defs (tree stmt1, tree stmt2)
{
  stmt_ann_t ann1 = stmt_ann (stmt1);
  stmt_ann_t ann2 = stmt_ann (stmt2);
  v_may_def_optype v_may_defs1;
  v_may_def_optype v_may_defs2;
  unsigned int i, j;

  get_stmt_operands (stmt1);
  get_stmt_operands (stmt2);
  v_may_defs1 = V_MAY_DEF_OPS (ann1);
  v_may_defs2 = V_MAY_DEF_OPS (ann2);

  /* Walk each V_MAY_DEF_OP in stmt1.  */
  for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs1); i++)
    {
      tree v_may_def1 = V_MAY_DEF_OP (v_may_defs1, i);

      /* Find the appropriate V_MAY_DEF_RESULT in STMT2.  */
      for (j = 0; j < NUM_V_MAY_DEFS (v_may_defs2); j++)
	{
	  if (v_may_def1 == V_MAY_DEF_RESULT (v_may_defs2, j))
	    {
	      /* Update.  */
	      SET_V_MAY_DEF_OP (v_may_defs1, i, V_MAY_DEF_OP (v_may_defs2, j));
	      break;
	    }
	}

#ifdef ENABLE_CHECKING
      /* If we did not find a corresponding V_MAY_DEF_RESULT, then something
	 has gone terribly wrong.  */
      if (j == NUM_V_MAY_DEFS (v_may_defs2))
	abort ();
#endif

    }
}


/* 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 (TREE_CODE (stmt) == MODIFY_EXPR)
    {
      dataflow_t df = get_immediate_uses (stmt);
      unsigned int num_uses = num_immediate_uses (df);
      tree use;
      tree skipped_phi;


      /* If there are no uses then there is nothing left to do.  */
      if (num_uses == 0)
	{
	  record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
	  return;
	}

      use = immediate_use (df, 0);
      skipped_phi = NULL;

      /* 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 (num_uses == 1
	     && TREE_CODE (use) == PHI_NODE
	     && bitmap_bit_p (dse_gd->stores, stmt_ann (use)->uid))
	{
	  /* Record the first PHI we skip so that we can fix its
	     uses if we find that STMT is a dead store.  */
	  if (!skipped_phi)
	    skipped_phi = use;

	  /* Skip past this PHI and loop again in case we had a PHI
	     chain.  */
	  df = get_immediate_uses (use);
	  num_uses = num_immediate_uses (df);
	  use = immediate_use (df, 0);
	}

      /* If we have precisely one immediate use at this point, then we may
	 have found redundant store.  */
      if (num_uses == 1
	  && bitmap_bit_p (dse_gd->stores, stmt_ann (use)->uid)
	  && operand_equal_p (TREE_OPERAND (stmt, 0),
			      TREE_OPERAND (use, 0), 0))
	{
	  /* We need to fix the operands if either the first PHI we
	     skipped, or the store which we are not deleting if we did
	     not skip any PHIs.  */
	  if (skipped_phi)
	    fix_phi_uses (skipped_phi, stmt);
	  else
	    fix_stmt_v_may_defs (use, stmt);

	  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");
            }

	  /* Any immediate uses which reference STMT need to instead
	     reference the new consumer, either SKIPPED_PHI or USE.  
	     This allows us to cascade dead stores.  */
	  redirect_immediate_uses (stmt, skipped_phi ? skipped_phi : use);

	  /* Finally remove the dead store.  */
	  bsi_remove (&bsi);
	}

      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_ann (phi)->uid);
}

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;

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

static void
tree_ssa_dse (void)
{
  struct dom_walk_data walk_data;
  struct dse_global_data dse_gd;
  unsigned int uid = 0;
  basic_block bb;

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

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

      for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
	stmt_ann (phi)->uid = 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);

  /* We also need immediate use information for virtual operands.  */
  compute_immediate_uses (TDFA_USE_VOPS, need_imm_uses_for);

  /* 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_XMALLOC ();
  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_XFREE (dse_gd.stores);

  /* Free dataflow information.  It's probably out of date now anyway.  */
  free_df ();

  /* 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
6de9cd9a DN	1	/* Dead store elimination
	2	Copyright (C) 2004 Free Software Foundation, Inc.
	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
61ada8ae	58	use of the virtual definition and the post-dominance relationship
6de9cd9a DN	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);
	97	static void fix_phi_uses (tree, tree);
a32b97a2	98	static void fix_stmt_v_may_defs (tree, tree);
6de9cd9a DN	99	static void record_voperand_set (bitmap, bitmap *, unsigned int);
	100
	101	/* Function indicating whether we ought to include information for 'var'
	102	when calculating immediate uses. For this pass we only want use
	103	information for virtual variables. */
	104
	105	static bool
	106	need_imm_uses_for (tree var)
	107	{
	108	return !is_gimple_reg (var);
	109	}
	110
	111
a32b97a2 BB	112	/* Replace uses in PHI which match V_MAY_DEF_RESULTs in STMT with the
a32b97a2 BB	113	corresponding V_MAY_DEF_OP in STMT. */
6de9cd9a DN	114
	115	static void
	116	fix_phi_uses (tree phi, tree stmt)
	117	{
	118	stmt_ann_t ann = stmt_ann (stmt);
a32b97a2	119	v_may_def_optype v_may_defs;
6de9cd9a DN	120	unsigned int i;
	121	int j;
	122
	123	get_stmt_operands (stmt);
a32b97a2	124	v_may_defs = V_MAY_DEF_OPS (ann);
6de9cd9a	125
a32b97a2 BB	126	/* Walk each V_MAY_DEF in STMT. */
a32b97a2 BB	127	for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
6de9cd9a	128	{
a32b97a2	129	tree v_may_def = V_MAY_DEF_RESULT (v_may_defs, i);
6de9cd9a	130
a32b97a2 BB	131	/* Find any uses in the PHI which match V_MAY_DEF and replace
a32b97a2 BB	132	them with the appropriate V_MAY_DEF_OP. */
6de9cd9a	133	for (j = 0; j < PHI_NUM_ARGS (phi); j++)
a32b97a2	134	if (v_may_def == PHI_ARG_DEF (phi, j))
d00ad49b	135	SET_PHI_ARG_DEF (phi, j, V_MAY_DEF_OP (v_may_defs, i));
6de9cd9a DN	136	}
	137	}
	138
a32b97a2 BB	139	/* Replace the V_MAY_DEF_OPs in STMT1 which match V_MAY_DEF_RESULTs
a32b97a2 BB	140	in STMT2 with the appropriate V_MAY_DEF_OPs from STMT2. */
6de9cd9a DN	141
6de9cd9a DN	142	static void
a32b97a2	143	fix_stmt_v_may_defs (tree stmt1, tree stmt2)
6de9cd9a DN	144	{
	145	stmt_ann_t ann1 = stmt_ann (stmt1);
	146	stmt_ann_t ann2 = stmt_ann (stmt2);
a32b97a2 BB	147	v_may_def_optype v_may_defs1;
a32b97a2 BB	148	v_may_def_optype v_may_defs2;
6de9cd9a DN	149	unsigned int i, j;
	150
	151	get_stmt_operands (stmt1);
	152	get_stmt_operands (stmt2);
a32b97a2 BB	153	v_may_defs1 = V_MAY_DEF_OPS (ann1);
a32b97a2 BB	154	v_may_defs2 = V_MAY_DEF_OPS (ann2);
6de9cd9a	155
a32b97a2 BB	156	/* Walk each V_MAY_DEF_OP in stmt1. */
a32b97a2 BB	157	for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs1); i++)
6de9cd9a	158	{
a32b97a2	159	tree v_may_def1 = V_MAY_DEF_OP (v_may_defs1, i);
6de9cd9a	160
a32b97a2 BB	161	/* Find the appropriate V_MAY_DEF_RESULT in STMT2. */
a32b97a2 BB	162	for (j = 0; j < NUM_V_MAY_DEFS (v_may_defs2); j++)
6de9cd9a	163	{
a32b97a2	164	if (v_may_def1 == V_MAY_DEF_RESULT (v_may_defs2, j))
6de9cd9a DN	165	{
6de9cd9a DN	166	/* Update. */
d00ad49b	167	SET_V_MAY_DEF_OP (v_may_defs1, i, V_MAY_DEF_OP (v_may_defs2, j));
6de9cd9a DN	168	break;
	169	}
	170	}
	171
	172	#ifdef ENABLE_CHECKING
a32b97a2	173	/* If we did not find a corresponding V_MAY_DEF_RESULT, then something
6de9cd9a	174	has gone terribly wrong. */
a32b97a2	175	if (j == NUM_V_MAY_DEFS (v_may_defs2))
6de9cd9a DN	176	abort ();
	177	#endif
	178
	179	}
	180	}
	181
	182
	183	/* Set bit UID in bitmaps GLOBAL and LOCAL, creating LOCAL as needed. */
	184	static void
	185	record_voperand_set (bitmap global, bitmap *local, unsigned int uid)
	186	{
	187	/* Lazily allocate the bitmap. Note that we do not get a notification
	188	when the block local data structures die, so we allocate the local
	189	bitmap backed by the GC system. */
	190	if (*local == NULL)
	191	*local = BITMAP_GGC_ALLOC ();
	192
	193	/* Set the bit in the local and global bitmaps. */
	194	bitmap_set_bit (*local, uid);
	195	bitmap_set_bit (global, uid);
	196	}
	197	/* Initialize block local data structures. */
	198
	199	static void
	200	dse_initialize_block_local_data (struct dom_walk_data *walk_data,
	201	basic_block bb ATTRIBUTE_UNUSED,
	202	bool recycled)
	203	{
	204	struct dse_block_local_data *bd
	205	= VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
	206
	207	/* If we are given a recycled block local data structure, ensure any
	208	bitmap associated with the block is cleared. */
	209	if (recycled)
	210	{
	211	if (bd->stores)
	212	bitmap_clear (bd->stores);
	213	}
	214	}
	215
	216	/* Attempt to eliminate dead stores in the statement referenced by BSI.
	217
	218	A dead store is a store into a memory location which will later be
	219	overwritten by another store without any intervening loads. In this
	220	case the earlier store can be deleted.
	221
	222	In our SSA + virtual operand world we use immediate uses of virtual
	223	operands to detect dead stores. If a store's virtual definition
	224	is used precisely once by a later store to the same location which
	225	post dominates the first store, then the first store is dead. */
	226
	227	static void
	228	dse_optimize_stmt (struct dom_walk_data *walk_data,
	229	basic_block bb ATTRIBUTE_UNUSED,
	230	block_stmt_iterator bsi)
	231	{
	232	struct dse_block_local_data *bd
	233	= VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
	234	struct dse_global_data *dse_gd = walk_data->global_data;
	235	tree stmt = bsi_stmt (bsi);
	236	stmt_ann_t ann = stmt_ann (stmt);
a32b97a2	237	v_may_def_optype v_may_defs;
6de9cd9a DN	238
6de9cd9a DN	239	get_stmt_operands (stmt);
a32b97a2	240	v_may_defs = V_MAY_DEF_OPS (ann);
6de9cd9a DN	241
	242	/* If this statement has no virtual uses, then there is nothing
	243	to do. */
a32b97a2	244	if (NUM_V_MAY_DEFS (v_may_defs) == 0)
6de9cd9a DN	245	return;
6de9cd9a DN	246
cd709752 RH	247	/* We know we have virtual definitions. If this is a MODIFY_EXPR that's
	248	not also a function call, then record it into our table. */
	249	if (get_call_expr_in (stmt))
	250	return;
	251	if (TREE_CODE (stmt) == MODIFY_EXPR)
6de9cd9a DN	252	{
	253	dataflow_t df = get_immediate_uses (stmt);
	254	unsigned int num_uses = num_immediate_uses (df);
	255	tree use;
	256	tree skipped_phi;
	257
	258
	259	/* If there are no uses then there is nothing left to do. */
	260	if (num_uses == 0)
	261	{
	262	record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
	263	return;
	264	}
	265
	266	use = immediate_use (df, 0);
	267	skipped_phi = NULL;
	268
	269	/* Skip through any PHI nodes we have already seen if the PHI
	270	represents the only use of this store.
	271
	272	Note this does not handle the case where the store has
a32b97a2	273	multiple V_MAY_DEFs which all reach a set of PHI nodes in the
6de9cd9a DN	274	same block. */
	275	while (num_uses == 1
	276	&& TREE_CODE (use) == PHI_NODE
	277	&& bitmap_bit_p (dse_gd->stores, stmt_ann (use)->uid))
	278	{
	279	/* Record the first PHI we skip so that we can fix its
	280	uses if we find that STMT is a dead store. */
	281	if (!skipped_phi)
	282	skipped_phi = use;
	283
	284	/* Skip past this PHI and loop again in case we had a PHI
	285	chain. */
	286	df = get_immediate_uses (use);
	287	num_uses = num_immediate_uses (df);
	288	use = immediate_use (df, 0);
	289	}
	290
	291	/* If we have precisely one immediate use at this point, then we may
	292	have found redundant store. */
	293	if (num_uses == 1
	294	&& bitmap_bit_p (dse_gd->stores, stmt_ann (use)->uid)
	295	&& operand_equal_p (TREE_OPERAND (stmt, 0),
	296	TREE_OPERAND (use, 0), 0))
	297	{
	298	/* We need to fix the operands if either the first PHI we
	299	skipped, or the store which we are not deleting if we did
	300	not skip any PHIs. */
	301	if (skipped_phi)
	302	fix_phi_uses (skipped_phi, stmt);
	303	else
a32b97a2	304	fix_stmt_v_may_defs (use, stmt);
6de9cd9a DN	305
	306	if (dump_file && (dump_flags & TDF_DETAILS))
	307	{
	308	fprintf (dump_file, " Deleted dead store '");
	309	print_generic_expr (dump_file, bsi_stmt (bsi), dump_flags);
	310	fprintf (dump_file, "'\n");
	311	}
	312
	313	/* Any immediate uses which reference STMT need to instead
	314	reference the new consumer, either SKIPPED_PHI or USE.
	315	This allows us to cascade dead stores. */
	316	redirect_immediate_uses (stmt, skipped_phi ? skipped_phi : use);
	317
	318	/* Finally remove the dead store. */
	319	bsi_remove (&bsi);
	320	}
	321
	322	record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
	323	}
	324	}
	325
	326	/* Record that we have seen the PHIs at the start of BB which correspond
	327	to virtual operands. */
	328	static void
	329	dse_record_phis (struct dom_walk_data *walk_data, basic_block bb)
	330	{
	331	struct dse_block_local_data *bd
	332	= VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
	333	struct dse_global_data *dse_gd = walk_data->global_data;
	334	tree phi;
	335
17192884	336	for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
6de9cd9a DN	337	if (need_imm_uses_for (PHI_RESULT (phi)))
	338	record_voperand_set (dse_gd->stores,
	339	&bd->stores,
	340	get_stmt_ann (phi)->uid);
	341	}
	342
	343	static void
	344	dse_finalize_block (struct dom_walk_data *walk_data,
	345	basic_block bb ATTRIBUTE_UNUSED)
	346	{
	347	struct dse_block_local_data *bd
	348	= VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
	349	struct dse_global_data *dse_gd = walk_data->global_data;
	350	bitmap stores = dse_gd->stores;
	351	unsigned int i;
	352
	353	/* Unwind the stores noted in this basic block. */
	354	if (bd->stores)
	355	EXECUTE_IF_SET_IN_BITMAP (bd->stores, 0, i, bitmap_clear_bit (stores, i););
	356	}
	357
	358	static void
	359	tree_ssa_dse (void)
	360	{
	361	struct dom_walk_data walk_data;
	362	struct dse_global_data dse_gd;
	363	unsigned int uid = 0;
	364	basic_block bb;
	365
	366	/* Create a UID for each statement in the function. Ordering of the
	367	UIDs is not important for this pass. */
	368	FOR_EACH_BB (bb)
	369	{
	370	block_stmt_iterator bsi;
	371	tree phi;
	372
	373	for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
	374	stmt_ann (bsi_stmt (bsi))->uid = uid++;
	375
17192884	376	for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
6de9cd9a DN	377	stmt_ann (phi)->uid = uid++;
	378	}
	379
	380	/* We might consider making this a property of each pass so that it
	381	can be [re]computed on an as-needed basis. Particularly since
	382	this pass could be seen as an extension of DCE which needs post
	383	dominators. */
	384	calculate_dominance_info (CDI_POST_DOMINATORS);
	385
	386	/* We also need immediate use information for virtual operands. */
	387	compute_immediate_uses (TDFA_USE_VOPS, need_imm_uses_for);
	388
	389	/* Dead store elimination is fundamentally a walk of the post-dominator
	390	tree and a backwards walk of statements within each block. */
	391	walk_data.walk_stmts_backward = true;
	392	walk_data.dom_direction = CDI_POST_DOMINATORS;
	393	walk_data.initialize_block_local_data = dse_initialize_block_local_data;
	394	walk_data.before_dom_children_before_stmts = NULL;
	395	walk_data.before_dom_children_walk_stmts = dse_optimize_stmt;
	396	walk_data.before_dom_children_after_stmts = dse_record_phis;
	397	walk_data.after_dom_children_before_stmts = NULL;
	398	walk_data.after_dom_children_walk_stmts = NULL;
	399	walk_data.after_dom_children_after_stmts = dse_finalize_block;
	400
	401	walk_data.block_local_data_size = sizeof (struct dse_block_local_data);
	402
	403	/* This is the main hash table for the dead store elimination pass. */
	404	dse_gd.stores = BITMAP_XMALLOC ();
	405	walk_data.global_data = &dse_gd;
	406
	407	/* Initialize the dominator walker. */
	408	init_walk_dominator_tree (&walk_data);
	409
	410	/* Recursively walk the dominator tree. */
	411	walk_dominator_tree (&walk_data, EXIT_BLOCK_PTR);
	412
	413	/* Finalize the dominator walker. */
	414	fini_walk_dominator_tree (&walk_data);
	415
	416	/* Release the main bitmap. */
	417	BITMAP_XFREE (dse_gd.stores);
	418
	419	/* Free dataflow information. It's probably out of date now anyway. */
	420	free_df ();
	421
	422	/* For now, just wipe the post-dominator information. */
	423	free_dominance_info (CDI_POST_DOMINATORS);
	424	}
	425
	426	static bool
	427	gate_dse (void)
	428	{
	429	return flag_tree_dse != 0;
	430	}
	431
	432	struct tree_opt_pass pass_dse = {
	433	"dse", /* name */
	434	gate_dse, /* gate */
	435	tree_ssa_dse, /* execute */
	436	NULL, /* sub */
	437	NULL, /* next */
	438	0, /* static_pass_number */
	439	TV_TREE_DSE, /* tv_id */
c1b763fa DN	440	PROP_cfg \| PROP_ssa
c1b763fa DN	441	\| PROP_alias, /* properties_required */
6de9cd9a DN	442	0, /* properties_provided */
	443	0, /* properties_destroyed */
	444	0, /* todo_flags_start */
	445	TODO_dump_func \| TODO_ggc_collect /* todo_flags_finish */
9f8628ba PB	446	\| TODO_verify_ssa,
9f8628ba PB	447	0 /* letter */
6de9cd9a	448	};