/* Dead store elimination
- Copyright (C) 2004, 2005 Free Software Foundation, Inc.
+ Copyright (C) 2004, 2005, 2006 Free Software Foundation, Inc.
This file is part of GCC.
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. */
+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 "errors.h"
#include "ggc.h"
#include "tree.h"
#include "rtl.h"
#include "tree-dump.h"
#include "domwalk.h"
#include "flags.h"
+#include "hashtab.h"
+#include "sbitmap.h"
/* This file implements dead store elimination.
the CFG. */
+/* Given an aggregate, this records the parts of it which have been
+ stored into. */
+struct aggregate_vardecl_d
+{
+ /* The aggregate. */
+ tree decl;
+
+ /* Some aggregates are too big for us to handle or never get stored
+ to as a whole. If this field is TRUE, we don't care about this
+ aggregate. */
+ bool ignore;
+
+ /* Number of parts in the whole. */
+ unsigned nparts;
+
+ /* A bitmap of parts of the aggregate that have been set. If part N
+ of an aggregate has been stored to, bit N should be on. */
+ sbitmap parts_set;
+};
+
struct dse_global_data
{
/* This is the global bitmap for store statements.
that we want to record, set the bit corresponding to the statement's
unique ID in this bitmap. */
bitmap stores;
+
+ /* A hash table containing the parts of an aggregate which have been
+ stored to. */
+ htab_t aggregate_vardecl;
};
/* We allocate a bitmap-per-block for stores which are encountered
bitmap stores;
};
+/* Basic blocks of the potentially dead store and the following
+ store, for memory_address_same. */
+struct address_walk_data
+{
+ basic_block store1_bb, store2_bb;
+};
+
static bool gate_dse (void);
-static void tree_ssa_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_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 void dse_record_partial_aggregate_store (tree, struct dse_global_data *);
static unsigned max_stmt_uid; /* Maximal uid of a statement. Uids to phi
nodes are assigned using the versions of
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)
{
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);
+ = (struct dse_block_local_data *)
+ 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. */
}
}
+/* Helper function for memory_address_same via walk_tree. Returns
+ non-NULL if it finds an SSA_NAME which is part of the address,
+ such that the definition of the SSA_NAME post-dominates the store
+ we want to delete but not the store that we believe makes it
+ redundant. This indicates that the address may change between
+ the two stores. */
+
+static tree
+memory_ssa_name_same (tree *expr_p, int *walk_subtrees ATTRIBUTE_UNUSED,
+ void *data)
+{
+ struct address_walk_data *walk_data = (struct address_walk_data *) data;
+ tree expr = *expr_p;
+ tree def_stmt;
+ basic_block def_bb;
+
+ if (TREE_CODE (expr) != SSA_NAME)
+ return NULL_TREE;
+
+ /* If we've found a default definition, then there's no problem. Both
+ stores will post-dominate it. And def_bb will be NULL. */
+ if (SSA_NAME_IS_DEFAULT_DEF (expr))
+ return NULL_TREE;
+
+ def_stmt = SSA_NAME_DEF_STMT (expr);
+ def_bb = bb_for_stmt (def_stmt);
+
+ /* DEF_STMT must dominate both stores. So if it is in the same
+ basic block as one, it does not post-dominate that store. */
+ if (walk_data->store1_bb != def_bb
+ && dominated_by_p (CDI_POST_DOMINATORS, walk_data->store1_bb, def_bb))
+ {
+ if (walk_data->store2_bb == def_bb
+ || !dominated_by_p (CDI_POST_DOMINATORS, walk_data->store2_bb,
+ def_bb))
+ /* Return non-NULL to stop the walk. */
+ return def_stmt;
+ }
+
+ return NULL_TREE;
+}
+
+/* Return TRUE if the destination memory address in STORE1 and STORE2
+ might be modified after STORE1, before control reaches STORE2. */
+
+static bool
+memory_address_same (tree store1, tree store2)
+{
+ struct address_walk_data walk_data;
+
+ walk_data.store1_bb = bb_for_stmt (store1);
+ walk_data.store2_bb = bb_for_stmt (store2);
+
+ return (walk_tree (&GIMPLE_STMT_OPERAND (store1, 0), memory_ssa_name_same,
+ &walk_data, NULL)
+ == NULL);
+}
+
+/* Return the use stmt for the lhs of STMT following the virtual
+ def-use chains. Returns the MODIFY_EXPR stmt which lhs is equal to
+ the lhs of STMT or NULL_TREE if no such stmt can be found. */
+static tree
+get_use_of_stmt_lhs (tree stmt,
+ use_operand_p * first_use_p,
+ use_operand_p * use_p, tree * use_stmt)
+{
+ tree usevar, lhs;
+ def_operand_p def_p;
+
+ if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
+ return NULL_TREE;
+
+ lhs = GIMPLE_STMT_OPERAND (stmt, 0);
+
+ /* The stmt must have a single VDEF. */
+ def_p = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_VDEF);
+ if (def_p == NULL_DEF_OPERAND_P)
+ return NULL_TREE;
+
+ if (!has_single_use (DEF_FROM_PTR (def_p)))
+ return NULL_TREE;
+ /* Get the immediate use of the def. */
+ single_imm_use (DEF_FROM_PTR (def_p), use_p, use_stmt);
+ gcc_assert (*use_p != NULL_USE_OPERAND_P);
+ first_use_p = use_p;
+ if (TREE_CODE (*use_stmt) != GIMPLE_MODIFY_STMT)
+ return NULL_TREE;
+
+ do
+ {
+ /* Look at the use stmt and see if it's LHS matches
+ stmt's lhs SSA_NAME. */
+ def_p = SINGLE_SSA_DEF_OPERAND (*use_stmt, SSA_OP_VDEF);
+ if (def_p == NULL_DEF_OPERAND_P)
+ return NULL_TREE;
+
+ usevar = GIMPLE_STMT_OPERAND (*use_stmt, 0);
+ if (operand_equal_p (usevar, lhs, 0))
+ return *use_stmt;
+
+ if (!has_single_use (DEF_FROM_PTR (def_p)))
+ return NULL_TREE;
+ single_imm_use (DEF_FROM_PTR (def_p), use_p, use_stmt);
+ gcc_assert (*use_p != NULL_USE_OPERAND_P);
+ if (TREE_CODE (*use_stmt) != GIMPLE_MODIFY_STMT)
+ return NULL_TREE;
+ }
+ while (1);
+
+ return NULL_TREE;
+}
+
+/* A helper of dse_optimize_stmt.
+ Given a GIMPLE_MODIFY_STMT in STMT, check that each VDEF has one
+ use, and that one use is another VDEF clobbering the first one.
+
+ Return TRUE if the above conditions are met, otherwise FALSE. */
+
+static bool
+dse_possible_dead_store_p (tree stmt,
+ use_operand_p *first_use_p,
+ use_operand_p *use_p,
+ tree *use_stmt,
+ struct dse_global_data *dse_gd,
+ struct dse_block_local_data *bd)
+{
+ ssa_op_iter op_iter;
+ bool fail = false;
+ def_operand_p var1;
+ vuse_vec_p vv;
+ tree defvar = NULL_TREE, temp;
+ tree prev_defvar = NULL_TREE;
+ stmt_ann_t ann = stmt_ann (stmt);
+
+ /* 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_VDEF_OPERAND (var1, vv, stmt, op_iter)
+ {
+ defvar = DEF_FROM_PTR (var1);
+
+ /* If this virtual def does not have precisely one use, then
+ we will not be able to eliminate STMT. */
+ if (!has_single_use (defvar))
+ {
+ 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;
+
+ /* In the case of memory partitions, we may get:
+
+ # MPT.764_162 = VDEF <MPT.764_161(D)>
+ x = {};
+ # MPT.764_167 = VDEF <MPT.764_162>
+ y = {};
+
+ So we must make sure we're talking about the same LHS.
+ */
+ if (TREE_CODE (temp) == GIMPLE_MODIFY_STMT)
+ {
+ tree base1 = get_base_address (GIMPLE_STMT_OPERAND (stmt, 0));
+ tree base2 = get_base_address (GIMPLE_STMT_OPERAND (temp, 0));
+
+ while (base1 && INDIRECT_REF_P (base1))
+ base1 = TREE_OPERAND (base1, 0);
+ while (base2 && INDIRECT_REF_P (base2))
+ base2 = TREE_OPERAND (base2, 0);
+
+ if (base1 != base2)
+ {
+ fail = true;
+ break;
+ }
+ }
+
+ /* 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;
+ prev_defvar = defvar;
+ }
+ else if (temp != *use_stmt)
+ {
+ /* The immediate use and the previously found immediate use
+ must be the same, except... if they're uses of different
+ parts of the whole. */
+ if (TREE_CODE (defvar) == SSA_NAME
+ && TREE_CODE (SSA_NAME_VAR (defvar)) == STRUCT_FIELD_TAG
+ && TREE_CODE (prev_defvar) == SSA_NAME
+ && TREE_CODE (SSA_NAME_VAR (prev_defvar)) == STRUCT_FIELD_TAG
+ && (SFT_PARENT_VAR (SSA_NAME_VAR (defvar))
+ == SFT_PARENT_VAR (SSA_NAME_VAR (prev_defvar))))
+ ;
+ else
+ {
+ fail = true;
+ break;
+ }
+ }
+ }
+
+ if (fail)
+ {
+ record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
+ dse_record_partial_aggregate_store (stmt, dse_gd);
+ return false;
+ }
+
+ /* 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 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)))
+ {
+ /* A PHI node can both define and use the same SSA_NAME if
+ the PHI is at the top of a loop and the PHI_RESULT is
+ a loop invariant and copies have not been fully propagated.
+
+ The safe thing to do is exit assuming no optimization is
+ possible. */
+ if (SSA_NAME_DEF_STMT (PHI_RESULT (*use_stmt)) == *use_stmt)
+ return false;
+
+ /* Skip past this PHI and loop again in case we had a PHI
+ chain. */
+ single_imm_use (PHI_RESULT (*use_stmt), use_p, use_stmt);
+ }
+
+ return true;
+}
+
+
+/* Given a DECL, return its AGGREGATE_VARDECL_D entry. If no entry is
+ found and INSERT is TRUE, add a new entry. */
+
+static struct aggregate_vardecl_d *
+get_aggregate_vardecl (tree decl, struct dse_global_data *dse_gd, bool insert)
+{
+ struct aggregate_vardecl_d av, *av_p;
+ void **slot;
+
+ av.decl = decl;
+ slot = htab_find_slot (dse_gd->aggregate_vardecl, &av, insert ? INSERT : NO_INSERT);
+
+
+ /* Not found, and we don't want to insert. */
+ if (slot == NULL)
+ return NULL;
+
+ /* Create new entry. */
+ if (*slot == NULL)
+ {
+ av_p = XNEW (struct aggregate_vardecl_d);
+ av_p->decl = decl;
+
+ /* Record how many parts the whole has. */
+ if (TREE_CODE (TREE_TYPE (decl)) == COMPLEX_TYPE)
+ av_p->nparts = 2;
+ else if (TREE_CODE (TREE_TYPE (decl)) == RECORD_TYPE)
+ {
+ tree fields;
+
+ /* Count the number of fields. */
+ fields = TYPE_FIELDS (TREE_TYPE (decl));
+ av_p->nparts = 0;
+ while (fields)
+ {
+ av_p->nparts++;
+ fields = TREE_CHAIN (fields);
+ }
+ }
+ else
+ abort ();
+
+ av_p->ignore = true;
+ av_p->parts_set = sbitmap_alloc (HOST_BITS_PER_LONG);
+ sbitmap_zero (av_p->parts_set);
+ *slot = av_p;
+ }
+ else
+ av_p = (struct aggregate_vardecl_d *) *slot;
+
+ return av_p;
+}
+
+
+/* If STMT is a partial store into an aggregate, record which part got set. */
+
+static void
+dse_record_partial_aggregate_store (tree stmt, struct dse_global_data *dse_gd)
+{
+ tree lhs, decl;
+ enum tree_code code;
+ struct aggregate_vardecl_d *av_p;
+ int part;
+
+ gcc_assert (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT);
+
+ lhs = GIMPLE_STMT_OPERAND (stmt, 0);
+ code = TREE_CODE (lhs);
+ if (code != IMAGPART_EXPR
+ && code != REALPART_EXPR
+ && code != COMPONENT_REF)
+ return;
+ decl = TREE_OPERAND (lhs, 0);
+ /* Early bail on things like nested COMPONENT_REFs. */
+ if (TREE_CODE (decl) != VAR_DECL)
+ return;
+ /* Early bail on unions. */
+ if (code == COMPONENT_REF
+ && TREE_CODE (TREE_TYPE (TREE_OPERAND (lhs, 0))) != RECORD_TYPE)
+ return;
+
+ av_p = get_aggregate_vardecl (decl, dse_gd, /*insert=*/false);
+ /* Run away, this isn't an aggregate we care about. */
+ if (!av_p || av_p->ignore)
+ return;
+
+ switch (code)
+ {
+ case IMAGPART_EXPR:
+ part = 0;
+ break;
+ case REALPART_EXPR:
+ part = 1;
+ break;
+ case COMPONENT_REF:
+ {
+ tree orig_field, fields;
+ tree record_type = TREE_TYPE (TREE_OPERAND (lhs, 0));
+
+ /* Get FIELD_DECL. */
+ orig_field = TREE_OPERAND (lhs, 1);
+
+ /* FIXME: Eeech, do this more efficiently. Perhaps
+ calculate bit/byte offsets. */
+ part = -1;
+ fields = TYPE_FIELDS (record_type);
+ while (fields)
+ {
+ ++part;
+ if (fields == orig_field)
+ break;
+ fields = TREE_CHAIN (fields);
+ }
+ gcc_assert (part >= 0);
+ }
+ break;
+ default:
+ return;
+ }
+
+ /* Record which part was set. */
+ SET_BIT (av_p->parts_set, part);
+}
+
+
+/* Return TRUE if all parts in an AGGREGATE_VARDECL have been set. */
+
+static inline bool
+dse_whole_aggregate_clobbered_p (struct aggregate_vardecl_d *av_p)
+{
+ unsigned int i;
+ sbitmap_iterator sbi;
+ int nbits_set = 0;
+
+ /* Count the number of partial stores (bits set). */
+ EXECUTE_IF_SET_IN_SBITMAP (av_p->parts_set, 0, i, sbi)
+ nbits_set++;
+ return ((unsigned) nbits_set == av_p->nparts);
+}
+
+
+/* Return TRUE if STMT is a store into a whole aggregate whose parts we
+ have already seen and recorded. */
+
+static bool
+dse_partial_kill_p (tree stmt, struct dse_global_data *dse_gd)
+{
+ tree decl;
+ struct aggregate_vardecl_d *av_p;
+
+ /* Make sure this is a store into the whole. */
+ if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
+ {
+ enum tree_code code;
+
+ decl = GIMPLE_STMT_OPERAND (stmt, 0);
+ code = TREE_CODE (TREE_TYPE (decl));
+
+ if (code != COMPLEX_TYPE && code != RECORD_TYPE)
+ return false;
+
+ if (TREE_CODE (decl) != VAR_DECL)
+ return false;
+ }
+ else
+ return false;
+
+ av_p = get_aggregate_vardecl (decl, dse_gd, /*insert=*/false);
+ gcc_assert (av_p != NULL);
+
+ return dse_whole_aggregate_clobbered_p (av_p);
+}
+
+
/* 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
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;
+ = (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;
tree stmt = bsi_stmt (bsi);
stmt_ann_t ann = stmt_ann (stmt);
- v_may_def_optype v_may_defs;
-
- v_may_defs = V_MAY_DEF_OPS (ann);
/* If this statement has no virtual defs, then there is nothing
to do. */
- if (NUM_V_MAY_DEFS (v_may_defs) == 0)
+ if (ZERO_SSA_OPERANDS (stmt, SSA_OP_VDEF))
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. */
+ /* We know we have virtual definitions. If this is a GIMPLE_MODIFY_STMT
+ 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)
+ if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
{
- 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;
- }
+ use_operand_p use_p = NULL;
+ tree use_stmt;
- 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;
- }
+ if (!dse_possible_dead_store_p (stmt, &first_use_p, &use_p, &use_stmt,
+ dse_gd, bd))
+ return;
- /* Skip through any PHI nodes we have already seen if the PHI
- represents the only use of this store.
+ /* If this is a partial store into an aggregate, record it. */
+ dse_record_partial_aggregate_store (stmt, dse_gd);
- 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 (use_p != NULL_USE_OPERAND_P
+ && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt))
+ && (!operand_equal_p (GIMPLE_STMT_OPERAND (stmt, 0),
+ GIMPLE_STMT_OPERAND (use_stmt, 0), 0)
+ && !dse_partial_kill_p (stmt, dse_gd))
+ && memory_address_same (stmt, use_stmt))
+ {
+ /* If we have precisely one immediate use at this point, but
+ the stores are not to the same memory location then walk the
+ virtual def-use chain to get the stmt which stores to that same
+ memory location. */
+ if (get_use_of_stmt_lhs (stmt, &first_use_p, &use_p, &use_stmt) ==
+ NULL_TREE)
+ {
+ record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
+ return;
+ }
+ }
- /* If we have precisely one immediate use at this point, then we may
- have found redundant store. */
+ /* 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 (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))
+ && (operand_equal_p (GIMPLE_STMT_OPERAND (stmt, 0),
+ GIMPLE_STMT_OPERAND (use_stmt, 0), 0)
+ || dse_partial_kill_p (stmt, dse_gd))
+ && memory_address_same (stmt, 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);
+ ssa_op_iter op_iter;
+ def_operand_p var1;
+ vuse_vec_p vv;
+ tree stmt_lhs;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "'\n");
}
- /* Remove the dead store. */
- bsi_remove (&bsi);
+ /* Then we need to fix the operand of the consuming stmt. */
+ stmt_lhs = USE_FROM_PTR (first_use_p);
+ FOR_EACH_SSA_VDEF_OPERAND (var1, vv, stmt, op_iter)
+ {
+ tree usevar, temp;
+
+ single_imm_use (DEF_FROM_PTR (var1), &use_p, &temp);
+ gcc_assert (VUSE_VECT_NUM_ELEM (*vv) == 1);
+ usevar = VUSE_ELEMENT_VAR (*vv, 0);
+ SET_USE (use_p, usevar);
- /* 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));
+ /* Make sure we propagate the ABNORMAL bit setting. */
+ if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (stmt_lhs))
+ SSA_NAME_OCCURS_IN_ABNORMAL_PHI (usevar) = 1;
+ }
+
+ /* Remove the dead store. */
+ bsi_remove (&bsi, true);
/* And release any SSA_NAMEs set in this statement back to the
SSA_NAME manager. */
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;
+ = (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;
tree phi;
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
- if (need_imm_uses_for (PHI_RESULT (phi)))
+ if (!is_gimple_reg (PHI_RESULT (phi)))
record_voperand_set (dse_gd->stores,
&bd->stores,
get_stmt_uid (phi));
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;
+ = (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;
}
}
+
+/* Hashing and equality functions for AGGREGATE_VARDECL. */
+
+static hashval_t
+aggregate_vardecl_hash (const void *p)
+{
+ return htab_hash_pointer
+ ((const void *)((const struct aggregate_vardecl_d *)p)->decl);
+}
+
+static int
+aggregate_vardecl_eq (const void *p1, const void *p2)
+{
+ return ((const struct aggregate_vardecl_d *)p1)->decl
+ == ((const struct aggregate_vardecl_d *)p2)->decl;
+}
+
+
+/* Free memory allocated by one entry in AGGREGATE_VARDECL. */
+
static void
+aggregate_vardecl_free (void *p)
+{
+ struct aggregate_vardecl_d *entry = (struct aggregate_vardecl_d *) p;
+ sbitmap_free (entry->parts_set);
+ free (entry);
+}
+
+
+/* Return true if STMT is a store into an entire aggregate. */
+
+static bool
+aggregate_whole_store_p (tree stmt)
+{
+ if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
+ {
+ tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
+ enum tree_code code = TREE_CODE (TREE_TYPE (lhs));
+
+ if (code == COMPLEX_TYPE || code == RECORD_TYPE)
+ return true;
+ }
+ return false;
+}
+
+
+/* Main entry point. */
+
+static unsigned int
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. */
+ dse_gd.aggregate_vardecl =
+ htab_create (37, aggregate_vardecl_hash,
+ aggregate_vardecl_eq, aggregate_vardecl_free);
+
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++;
+ {
+ tree stmt = bsi_stmt (bsi);
+
+ /* Record aggregates which have been stored into as a whole. */
+ if (aggregate_whole_store_p (stmt))
+ {
+ tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
+ if (TREE_CODE (lhs) == VAR_DECL)
+ {
+ struct aggregate_vardecl_d *av_p;
+
+ av_p = get_aggregate_vardecl (lhs, &dse_gd, /*insert=*/true);
+ av_p->ignore = false;
+
+ /* Ignore aggregates with too many parts. */
+ if (av_p->nparts > HOST_BITS_PER_LONG)
+ av_p->ignore = true;
+ }
+ }
+
+ /* Create a UID for each statement in the function.
+ Ordering of the UIDs is not important for this pass. */
+ stmt_ann (stmt)->uid = max_stmt_uid++;
+ }
}
/* We might consider making this a property of each pass so that it
/* 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. */
/* Finalize the dominator walker. */
fini_walk_dominator_tree (&walk_data);
- /* Release the main bitmap. */
+ /* Release unneeded data. */
BITMAP_FREE (dse_gd.stores);
+ htab_delete (dse_gd.aggregate_vardecl);
/* For now, just wipe the post-dominator information. */
free_dominance_info (CDI_POST_DOMINATORS);
+ return 0;
}
static bool
0, /* todo_flags_start */
TODO_dump_func
| TODO_ggc_collect
- | TODO_update_ssa
| TODO_verify_ssa, /* todo_flags_finish */
0 /* letter */
};