/* Dead store elimination
- Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010
- Free Software Foundation, Inc.
+ Copyright (C) 2004-2014 Free Software Foundation, Inc.
This file is part of GCC.
#include "system.h"
#include "coretypes.h"
#include "tm.h"
-#include "ggc.h"
#include "tree.h"
#include "tm_p.h"
+#include "predict.h"
+#include "vec.h"
+#include "hashtab.h"
+#include "hash-set.h"
+#include "machmode.h"
+#include "hard-reg-set.h"
+#include "input.h"
+#include "function.h"
+#include "dominance.h"
+#include "cfg.h"
#include "basic-block.h"
-#include "timevar.h"
-#include "diagnostic.h"
#include "gimple-pretty-print.h"
-#include "tree-flow.h"
+#include "bitmap.h"
+#include "tree-ssa-alias.h"
+#include "internal-fn.h"
+#include "gimple-expr.h"
+#include "is-a.h"
+#include "gimple.h"
+#include "gimple-iterator.h"
+#include "gimple-ssa.h"
+#include "tree-cfg.h"
+#include "tree-phinodes.h"
+#include "ssa-iterators.h"
+#include "stringpool.h"
+#include "tree-ssanames.h"
+#include "expr.h"
+#include "tree-dfa.h"
#include "tree-pass.h"
-#include "tree-dump.h"
#include "domwalk.h"
#include "flags.h"
#include "langhooks.h"
+#include "tree-cfgcleanup.h"
/* This file implements dead store elimination.
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 unsigned int tree_ssa_dse (void);
-static void dse_initialize_block_local_data (struct dom_walk_data *,
- basic_block,
- bool);
-static void dse_enter_block (struct dom_walk_data *, basic_block);
-static void dse_leave_block (struct dom_walk_data *, basic_block);
-static void record_voperand_set (bitmap, bitmap *, unsigned int);
-
-/* Returns uid of statement STMT. */
-
-static unsigned
-get_stmt_uid (gimple stmt)
-{
- if (gimple_code (stmt) == GIMPLE_PHI)
- return SSA_NAME_VERSION (gimple_phi_result (stmt))
- + gimple_stmt_max_uid (cfun);
-
- return gimple_uid (stmt);
-}
-
-/* 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
- = (struct dse_block_local_data *)
- VEC_last (void_p, walk_data->block_data_stack);
+/* Bitmap of blocks that have had EH statements cleaned. We should
+ remove their dead edges eventually. */
+static bitmap need_eh_cleanup;
- /* 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);
- }
-}
/* A helper of dse_optimize_stmt.
- Given a GIMPLE_ASSIGN in STMT, find a candidate statement *USE_STMT that
- may prove STMT to be dead.
+ Given a GIMPLE_ASSIGN in STMT that writes to REF, find a candidate
+ statement *USE_STMT that may prove STMT to be dead.
Return TRUE if the above conditions are met, otherwise FALSE. */
static bool
-dse_possible_dead_store_p (gimple stmt, gimple *use_stmt)
+dse_possible_dead_store_p (ao_ref *ref, gimple stmt, gimple *use_stmt)
{
gimple temp;
unsigned cnt = 0;
temp = stmt;
do
{
- gimple use_stmt;
+ gimple use_stmt, defvar_def;
imm_use_iterator ui;
bool fail = false;
tree defvar;
defvar = PHI_RESULT (temp);
else
defvar = gimple_vdef (temp);
+ defvar_def = temp;
temp = NULL;
FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar)
{
fail = true;
BREAK_FROM_IMM_USE_STMT (ui);
}
- temp = use_stmt;
+ /* Do not consider the PHI as use if it dominates the
+ stmt defining the virtual operand we are processing,
+ we have processed it already in this case. */
+ if (gimple_bb (defvar_def) != gimple_bb (use_stmt)
+ && !dominated_by_p (CDI_DOMINATORS,
+ gimple_bb (defvar_def),
+ gimple_bb (use_stmt)))
+ temp = use_stmt;
}
/* If the statement is a use the store is not dead. */
- else if (ref_maybe_used_by_stmt_p (use_stmt,
- gimple_assign_lhs (stmt)))
+ else if (ref_maybe_used_by_stmt_p (use_stmt, ref))
{
fail = true;
BREAK_FROM_IMM_USE_STMT (ui);
just pretend the stmt makes itself dead. Otherwise fail. */
if (!temp)
{
- if (is_hidden_global_store (stmt))
+ if (ref_may_alias_global_p (ref))
return false;
temp = stmt;
break;
}
}
- /* We deliberately stop on clobbering statements and not only on
- killing ones to make walking cheaper. Otherwise we can just
- continue walking until both stores have equal reference trees. */
- while (!stmt_may_clobber_ref_p (temp, gimple_assign_lhs (stmt)));
-
- if (!is_gimple_assign (temp))
- return false;
+ /* Continue walking until we reach a kill. */
+ while (!stmt_kills_ref_p (temp, ref));
*use_stmt = temp;
post dominates the first store, then the first store is dead. */
static void
-dse_optimize_stmt (struct dse_global_data *dse_gd,
- struct dse_block_local_data *bd,
- gimple_stmt_iterator gsi)
+dse_optimize_stmt (gimple_stmt_iterator *gsi)
{
- gimple stmt = gsi_stmt (gsi);
+ gimple stmt = gsi_stmt (*gsi);
/* If this statement has no virtual defs, then there is nothing
to do. */
if (!gimple_vdef (stmt))
return;
- /* We know we have virtual definitions. If this is a GIMPLE_ASSIGN
- that's not also a function call, then record it into our table. */
- if (is_gimple_call (stmt) && gimple_call_fndecl (stmt))
+ /* Don't return early on *this_2(D) ={v} {CLOBBER}. */
+ if (gimple_has_volatile_ops (stmt)
+ && (!gimple_clobber_p (stmt)
+ || TREE_CODE (gimple_assign_lhs (stmt)) != MEM_REF))
return;
- if (gimple_has_volatile_ops (stmt))
- return;
+ /* We know we have virtual definitions. We can handle assignments and
+ some builtin calls. */
+ if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
+ {
+ switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt)))
+ {
+ case BUILT_IN_MEMCPY:
+ case BUILT_IN_MEMMOVE:
+ case BUILT_IN_MEMSET:
+ {
+ gimple use_stmt;
+ ao_ref ref;
+ tree size = NULL_TREE;
+ if (gimple_call_num_args (stmt) == 3)
+ size = gimple_call_arg (stmt, 2);
+ tree ptr = gimple_call_arg (stmt, 0);
+ ao_ref_init_from_ptr_and_size (&ref, ptr, size);
+ if (!dse_possible_dead_store_p (&ref, stmt, &use_stmt))
+ return;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, " Deleted dead call '");
+ print_gimple_stmt (dump_file, gsi_stmt (*gsi), dump_flags, 0);
+ fprintf (dump_file, "'\n");
+ }
+
+ tree lhs = gimple_call_lhs (stmt);
+ if (lhs)
+ {
+ gimple new_stmt = gimple_build_assign (lhs, ptr);
+ unlink_stmt_vdef (stmt);
+ if (gsi_replace (gsi, new_stmt, true))
+ bitmap_set_bit (need_eh_cleanup, gimple_bb (stmt)->index);
+ }
+ else
+ {
+ /* Then we need to fix the operand of the consuming stmt. */
+ unlink_stmt_vdef (stmt);
+
+ /* Remove the dead store. */
+ if (gsi_remove (gsi, true))
+ bitmap_set_bit (need_eh_cleanup, gimple_bb (stmt)->index);
+ }
+ break;
+ }
+ default:
+ return;
+ }
+ }
if (is_gimple_assign (stmt))
{
gimple use_stmt;
- record_voperand_set (dse_gd->stores, &bd->stores, gimple_uid (stmt));
+ /* Self-assignments are zombies. */
+ if (operand_equal_p (gimple_assign_rhs1 (stmt),
+ gimple_assign_lhs (stmt), 0))
+ use_stmt = stmt;
+ else
+ {
+ ao_ref ref;
+ ao_ref_init (&ref, gimple_assign_lhs (stmt));
+ if (!dse_possible_dead_store_p (&ref, stmt, &use_stmt))
+ return;
+ }
+
+ /* Now we know that use_stmt kills the LHS of stmt. */
- if (!dse_possible_dead_store_p (stmt, &use_stmt))
+ /* But only remove *this_2(D) ={v} {CLOBBER} if killed by
+ another clobber stmt. */
+ if (gimple_clobber_p (stmt)
+ && !gimple_clobber_p (use_stmt))
return;
- /* If we have precisely one immediate use at this point and the
- stores are to the same memory location or there is a chain of
- virtual uses from stmt and the stmt which stores to that same
- memory location, then we may have found redundant store. */
- if (bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt))
- && operand_equal_p (gimple_assign_lhs (stmt),
- gimple_assign_lhs (use_stmt), 0))
+ if (dump_file && (dump_flags & TDF_DETAILS))
{
- /* If use_stmt is or might be a nop assignment, e.g. for
- struct { ... } S a, b, *p; ...
- b = a; b = b;
- or
- b = a; b = *p; where p might be &b,
- or
- *p = a; *p = b; where p might be &b,
- or
- *p = *u; *p = *v; where p might be v, then USE_STMT
- acts as a use as well as definition, so store in STMT
- is not dead. */
- if (stmt != use_stmt
- && !is_gimple_reg (gimple_assign_rhs1 (use_stmt))
- && !is_gimple_min_invariant (gimple_assign_rhs1 (use_stmt))
- /* ??? Should {} be invariant? */
- && gimple_assign_rhs_code (use_stmt) != CONSTRUCTOR
- && refs_may_alias_p (gimple_assign_lhs (use_stmt),
- gimple_assign_rhs1 (use_stmt)))
- return;
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, " Deleted dead store '");
- print_gimple_stmt (dump_file, gsi_stmt (gsi), dump_flags, 0);
- fprintf (dump_file, "'\n");
- }
+ fprintf (dump_file, " Deleted dead store '");
+ print_gimple_stmt (dump_file, gsi_stmt (*gsi), dump_flags, 0);
+ fprintf (dump_file, "'\n");
+ }
- /* Then we need to fix the operand of the consuming stmt. */
- unlink_stmt_vdef (stmt);
+ /* Then we need to fix the operand of the consuming stmt. */
+ unlink_stmt_vdef (stmt);
- /* Remove the dead store. */
- gsi_remove (&gsi, true);
+ /* Remove the dead store. */
+ basic_block bb = gimple_bb (stmt);
+ if (gsi_remove (gsi, true))
+ bitmap_set_bit (need_eh_cleanup, bb->index);
- /* And release any SSA_NAMEs set in this statement back to the
- SSA_NAME manager. */
- release_defs (stmt);
- }
+ /* And release any SSA_NAMEs set in this statement back to the
+ SSA_NAME manager. */
+ release_defs (stmt);
}
}
-/* Record that we have seen the PHIs at the start of BB which correspond
- to virtual operands. */
-static void
-dse_record_phi (struct dse_global_data *dse_gd,
- struct dse_block_local_data *bd,
- gimple phi)
+class dse_dom_walker : public dom_walker
{
- if (!is_gimple_reg (gimple_phi_result (phi)))
- record_voperand_set (dse_gd->stores, &bd->stores, get_stmt_uid (phi));
-}
+public:
+ dse_dom_walker (cdi_direction direction) : dom_walker (direction) {}
-static void
-dse_enter_block (struct dom_walk_data *walk_data, basic_block bb)
+ virtual void before_dom_children (basic_block);
+};
+
+void
+dse_dom_walker::before_dom_children (basic_block bb)
{
- struct dse_block_local_data *bd
- = (struct dse_block_local_data *)
- VEC_last (void_p, walk_data->block_data_stack);
- struct dse_global_data *dse_gd
- = (struct dse_global_data *) walk_data->global_data;
gimple_stmt_iterator gsi;
- for (gsi = gsi_last (bb_seq (bb)); !gsi_end_p (gsi); gsi_prev (&gsi))
- dse_optimize_stmt (dse_gd, bd, gsi);
- for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
- dse_record_phi (dse_gd, bd, gsi_stmt (gsi));
+ for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
+ {
+ dse_optimize_stmt (&gsi);
+ if (gsi_end_p (gsi))
+ gsi = gsi_last_bb (bb);
+ else
+ gsi_prev (&gsi);
+ }
}
-static void
-dse_leave_block (struct dom_walk_data *walk_data,
- basic_block bb ATTRIBUTE_UNUSED)
+namespace {
+
+const pass_data pass_data_dse =
{
- struct dse_block_local_data *bd
- = (struct dse_block_local_data *)
- VEC_last (void_p, walk_data->block_data_stack);
- struct dse_global_data *dse_gd
- = (struct dse_global_data *) 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);
- }
-}
+ GIMPLE_PASS, /* type */
+ "dse", /* name */
+ OPTGROUP_NONE, /* optinfo_flags */
+ TV_TREE_DSE, /* tv_id */
+ ( PROP_cfg | PROP_ssa ), /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ 0, /* todo_flags_finish */
+};
+
+class pass_dse : public gimple_opt_pass
+{
+public:
+ pass_dse (gcc::context *ctxt)
+ : gimple_opt_pass (pass_data_dse, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ opt_pass * clone () { return new pass_dse (m_ctxt); }
+ virtual bool gate (function *) { return flag_tree_dse != 0; }
+ virtual unsigned int execute (function *);
-/* Main entry point. */
+}; // class pass_dse
-static unsigned int
-tree_ssa_dse (void)
+unsigned int
+pass_dse::execute (function *fun)
{
- struct dom_walk_data walk_data;
- struct dse_global_data dse_gd;
+ need_eh_cleanup = BITMAP_ALLOC (NULL);
renumber_gimple_stmt_uids ();
/* Dead store elimination is fundamentally a walk of the post-dominator
tree and a backwards walk of statements within each block. */
- walk_data.dom_direction = CDI_POST_DOMINATORS;
- walk_data.initialize_block_local_data = dse_initialize_block_local_data;
- walk_data.before_dom_children = dse_enter_block;
- walk_data.after_dom_children = dse_leave_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);
+ dse_dom_walker (CDI_POST_DOMINATORS).walk (fun->cfg->x_exit_block_ptr);
- /* 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);
+ /* Removal of stores may make some EH edges dead. Purge such edges from
+ the CFG as needed. */
+ if (!bitmap_empty_p (need_eh_cleanup))
+ {
+ gimple_purge_all_dead_eh_edges (need_eh_cleanup);
+ cleanup_tree_cfg ();
+ }
+ BITMAP_FREE (need_eh_cleanup);
+
/* For now, just wipe the post-dominator information. */
free_dominance_info (CDI_POST_DOMINATORS);
return 0;
}
-static bool
-gate_dse (void)
-{
- return flag_tree_dse != 0;
-}
+} // anon namespace
-struct gimple_opt_pass pass_dse =
+gimple_opt_pass *
+make_pass_dse (gcc::context *ctxt)
{
- {
- GIMPLE_PASS,
- "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, /* properties_required */
- 0, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- TODO_dump_func
- | TODO_ggc_collect
- | TODO_verify_ssa /* todo_flags_finish */
- }
-};
-
+ return new pass_dse (ctxt);
+}