X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Ftree-ssa-dse.c;h=1be41275d111a85f746be439e1474488f31f3881;hb=909dc3030762da210a8341e9d299af1448d83a21;hp=e2d063f03ffb057b6f670d6d33e81c919e206e83;hpb=0c304c96a918159ce8b5f2f07c98a8815d9e4643;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/tree-ssa-dse.c b/gcc/tree-ssa-dse.c index e2d063f03ff..1be41275d11 100644 --- a/gcc/tree-ssa-dse.c +++ b/gcc/tree-ssa-dse.c @@ -1,5 +1,5 @@ /* 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. @@ -15,14 +15,13 @@ 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. */ +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" @@ -35,6 +34,8 @@ Boston, MA 02111-1307, USA. */ #include "tree-dump.h" #include "domwalk.h" #include "flags.h" +#include "hashtab.h" +#include "sbitmap.h" /* This file implements dead store elimination. @@ -66,6 +67,26 @@ Boston, MA 02111-1307, USA. */ 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. @@ -74,6 +95,10 @@ struct dse_global_data 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 @@ -84,8 +109,15 @@ struct dse_block_local_data 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); @@ -95,6 +127,7 @@ static void dse_optimize_stmt (struct dom_walk_data *, 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 @@ -135,7 +168,8 @@ dse_initialize_block_local_data (struct dom_walk_data *walk_data, bool recycled) { struct dse_block_local_data *bd - = VEC_last (void_p, 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. */ @@ -146,6 +180,425 @@ dse_initialize_block_local_data (struct dom_walk_data *walk_data, } } +/* 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 + x = {}; + # MPT.764_167 = VDEF + 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 @@ -163,109 +616,73 @@ dse_optimize_stmt (struct dom_walk_data *walk_data, block_stmt_iterator bsi) { struct dse_block_local_data *bd - = VEC_last (void_p, 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); /* If this statement has no virtual defs, then there is nothing to do. */ - if (ZERO_SSA_OPERANDS (stmt, (SSA_OP_VMAYDEF|SSA_OP_VMUSTDEF))) + 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) { 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; - } - } + tree use_stmt; - if (fail) - { - 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,MUST}_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)) { @@ -274,14 +691,24 @@ dse_optimize_stmt (struct dom_walk_data *walk_data, 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; - /* 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)); + 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); + + /* 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. */ @@ -298,8 +725,10 @@ static void dse_record_phis (struct dom_walk_data *walk_data, basic_block bb) { struct dse_block_local_data *bd - = VEC_last (void_p, 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)) @@ -314,8 +743,10 @@ dse_finalize_block (struct dom_walk_data *walk_data, basic_block bb ATTRIBUTE_UNUSED) { struct dse_block_local_data *bd - = VEC_last (void_p, 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; @@ -328,22 +759,95 @@ dse_finalize_block (struct dom_walk_data *walk_data, } } + +/* 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 @@ -369,6 +873,7 @@ tree_ssa_dse (void) /* 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. */ @@ -380,11 +885,13 @@ tree_ssa_dse (void) /* 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 @@ -409,7 +916,6 @@ struct tree_opt_pass pass_dse = { 0, /* todo_flags_start */ TODO_dump_func | TODO_ggc_collect - | TODO_update_ssa | TODO_verify_ssa, /* todo_flags_finish */ 0 /* letter */ };