diff options
author | Diego Novillo <dnovillo@gcc.gnu.org> | 2004-05-13 02:41:07 -0400 |
---|---|---|
committer | Diego Novillo <dnovillo@gcc.gnu.org> | 2004-05-13 02:41:07 -0400 |
commit | 6de9cd9a886ea695aa892c3c7c07818a7b7e9e6f (patch) | |
tree | a2568888a519c077427b133de9ece5879a8484a5 /gcc/tree-ssa-dse.c | |
parent | ac1a20aec53364d77f3bdff94a2a0a06840e0fe9 (diff) | |
download | gcc-6de9cd9a886ea695aa892c3c7c07818a7b7e9e6f.zip gcc-6de9cd9a886ea695aa892c3c7c07818a7b7e9e6f.tar.gz gcc-6de9cd9a886ea695aa892c3c7c07818a7b7e9e6f.tar.bz2 |
Merge tree-ssa-20020619-branch into mainline.
From-SVN: r81764
Diffstat (limited to 'gcc/tree-ssa-dse.c')
-rw-r--r-- | gcc/tree-ssa-dse.c | 445 |
1 files changed, 445 insertions, 0 deletions
diff --git a/gcc/tree-ssa-dse.c b/gcc/tree-ssa-dse.c new file mode 100644 index 0000000..fca08ac --- /dev/null +++ b/gcc/tree-ssa-dse.c @@ -0,0 +1,445 @@ +/* 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 defintion 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_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); +} + + +/* 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) +{ + 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); + } +} + +/* 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 + + } +} + + +/* 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); + vdef_optype vdefs; + + get_stmt_operands (stmt); + vdefs = VDEF_OPS (ann); + + /* If this statement has no virtual uses, then there is nothing + to do. */ + if (NUM_VDEFS (vdefs) == 0) + 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) + { + 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 VDEFs 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_vdefs (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 = TREE_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 = TREE_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, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_dump_func | TODO_ggc_collect /* todo_flags_finish */ + | TODO_verify_ssa +}; |