/* Dead store elimination
- Copyright (C) 2004 Free Software Foundation, Inc.
+ Copyright (C) 2004, 2005 Free Software Foundation, Inc.
This file is part of GCC.
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 defintion and the post-dominance relationship
+ 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.
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_vdefs (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);
-}
+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. */
-/* Replace uses in PHI which match VDEF_RESULTs in STMT with the
- corresponding VDEF_OP in STMT. */
-
-static void
-fix_phi_uses (tree phi, tree stmt)
+static unsigned
+get_stmt_uid (tree stmt)
{
- stmt_ann_t ann = stmt_ann (stmt);
- vdef_optype vdefs;
- unsigned int i;
- int j;
-
- get_stmt_operands (stmt);
- vdefs = VDEF_OPS (ann);
-
- /* Walk each VDEF in STMT. */
- for (i = 0; i < NUM_VDEFS (vdefs); i++)
- {
- tree vdef = VDEF_RESULT (vdefs, i);
-
- /* Find any uses in the PHI which match VDEF and replace
- them with the appropriate VDEF_OP. */
- for (j = 0; j < PHI_NUM_ARGS (phi); j++)
- if (vdef == PHI_ARG_DEF (phi, j))
- PHI_ARG_DEF (phi, j) = VDEF_OP (vdefs, i);
- }
-}
+ if (TREE_CODE (stmt) == PHI_NODE)
+ return SSA_NAME_VERSION (PHI_RESULT (stmt)) + max_stmt_uid;
-/* Replace the VDEF_OPs in STMT1 which match VDEF_RESULTs in STMT2 with
- the appropriate VDEF_OPs from STMT2. */
-
-static void
-fix_stmt_vdefs (tree stmt1, tree stmt2)
-{
- stmt_ann_t ann1 = stmt_ann (stmt1);
- stmt_ann_t ann2 = stmt_ann (stmt2);
- vdef_optype vdefs1;
- vdef_optype vdefs2;
- unsigned int i, j;
-
- get_stmt_operands (stmt1);
- get_stmt_operands (stmt2);
- vdefs1 = VDEF_OPS (ann1);
- vdefs2 = VDEF_OPS (ann2);
-
- /* Walk each VDEF_OP in stmt1. */
- for (i = 0; i < NUM_VDEFS (vdefs1); i++)
- {
- tree vdef1 = VDEF_OP (vdefs1, i);
-
- /* Find the appropriate VDEF_RESULT in STMT2. */
- for (j = 0; j < NUM_VDEFS (vdefs2); j++)
- {
- if (vdef1 == VDEF_RESULT (vdefs2, j))
- {
- /* Update. */
- *VDEF_OP_PTR (vdefs1, i) = VDEF_OP (vdefs2, j);
- break;
- }
- }
-
-#ifdef ENABLE_CHECKING
- /* If we did not find a corresponding VDEF_RESULT, then something
- has gone terribly wrong. */
- if (j == NUM_VDEFS (vdefs2))
- abort ();
-#endif
-
- }
+ 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)
{
bitmap_set_bit (*local, uid);
bitmap_set_bit (global, uid);
}
+
/* Initialize block local data structures. */
static void
bool recycled)
{
struct dse_block_local_data *bd
- = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
+ = 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. */
block_stmt_iterator bsi)
{
struct dse_block_local_data *bd
- = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
+ = 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);
- vdef_optype vdefs;
-
- get_stmt_operands (stmt);
- vdefs = VDEF_OPS (ann);
- /* If this statement has no virtual uses, then there is nothing
+ /* If this statement has no virtual defs, then there is nothing
to do. */
- if (NUM_VDEFS (vdefs) == 0)
+ if (ZERO_SSA_OPERANDS (stmt, (SSA_OP_VMAYDEF|SSA_OP_VMUSTDEF)))
return;
- /* We know we have virtual definitions. If this is a MODIFY_EXPR, then
- record it into our table. */
- if (TREE_CODE (stmt) == MODIFY_EXPR
- && TREE_CODE (TREE_OPERAND (stmt, 1)) != CALL_EXPR)
+ /* 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)
{
- dataflow_t df = get_immediate_uses (stmt);
- unsigned int num_uses = num_immediate_uses (df);
- tree use;
- tree skipped_phi;
+ 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 there are no uses then there is nothing left to do. */
- if (num_uses == 0)
+ if (fail)
{
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 VDEFs which all reach a set of PHI nodes in the
+ multiple V_{MAY,MUST}_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))
+ while (use_p != NULL_USE_OPERAND_P
+ && TREE_CODE (use_stmt) == PHI_NODE
+ && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt)))
{
- /* 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 (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 (num_uses == 1
- && bitmap_bit_p (dse_gd->stores, stmt_ann (use)->uid)
+ 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, 0), 0))
+ TREE_OPERAND (use_stmt, 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_vdefs (use, stmt);
+ 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, "'\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. */
+ /* 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);
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);
+ = 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 = TREE_CHAIN (phi))
- if (need_imm_uses_for (PHI_RESULT (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_ann (phi)->uid);
+ get_stmt_uid (phi));
}
static void
basic_block bb ATTRIBUTE_UNUSED)
{
struct dse_block_local_data *bd
- = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
+ = 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, bitmap_clear_bit (stores, i););
+ EXECUTE_IF_SET_IN_BITMAP (bd->stores, 0, i, bi)
+ {
+ bitmap_clear_bit (stores, i);
+ }
}
static 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. */
+ max_stmt_uid = 0;
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 = TREE_CHAIN (phi))
- stmt_ann (phi)->uid = uid++;
+ stmt_ann (bsi_stmt (bsi))->uid = max_stmt_uid++;
}
/* We might consider making this a property of each pass so that it
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.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_XMALLOC ();
+ dse_gd.stores = BITMAP_ALLOC (NULL);
walk_data.global_data = &dse_gd;
/* Initialize 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 ();
+ BITMAP_FREE (dse_gd.stores);
/* For now, just wipe the post-dominator information. */
free_dominance_info (CDI_POST_DOMINATORS);
NULL, /* next */
0, /* static_pass_number */
TV_TREE_DSE, /* tv_id */
- PROP_cfg | PROP_ssa, /* properties_required */
+ 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
+ TODO_dump_func
+ | TODO_ggc_collect
+ | TODO_update_ssa
+ | TODO_verify_ssa, /* todo_flags_finish */
+ 0 /* letter */
};