1 /* Dead store elimination
2 Copyright (C) 2004 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GCC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
23 #include "coretypes.h"
30 #include "basic-block.h"
32 #include "diagnostic.h"
33 #include "tree-flow.h"
34 #include "tree-pass.h"
35 #include "tree-dump.h"
39 /* This file implements dead store elimination.
41 A dead store is a store into a memory location which will later be
42 overwritten by another store without any intervening loads. In this
43 case the earlier store can be deleted.
45 In our SSA + virtual operand world we use immediate uses of virtual
46 operands to detect dead stores. If a store's virtual definition
47 is used precisely once by a later store to the same location which
48 post dominates the first store, then the first store is dead.
50 The single use of the store's virtual definition ensures that
51 there are no intervening aliased loads and the requirement that
52 the second load post dominate the first ensures that if the earlier
53 store executes, then the later stores will execute before the function
56 It may help to think of this as first moving the earlier store to
57 the point immediately before the later store. Again, the single
58 use of the virtual definition and the post-dominance relationship
59 ensure that such movement would be safe. Clearly if there are
60 back to back stores, then the second is redundant.
62 Reviewing section 10.7.2 in Morgan's "Building an Optimizing Compiler"
63 may also help in understanding this code since it discusses the
64 relationship between dead store and redundant load elimination. In
65 fact, they are the same transformation applied to different views of
69 struct dse_global_data
71 /* This is the global bitmap for store statements.
73 Each statement has a unique ID. When we encounter a store statement
74 that we want to record, set the bit corresponding to the statement's
75 unique ID in this bitmap. */
79 /* We allocate a bitmap-per-block for stores which are encountered
80 during the scan of that block. This allows us to restore the
81 global bitmap of stores when we finish processing a block. */
82 struct dse_block_local_data
87 static bool gate_dse (void);
88 static void tree_ssa_dse (void);
89 static void dse_initialize_block_local_data (struct dom_walk_data *,
92 static void dse_optimize_stmt (struct dom_walk_data *,
95 static void dse_record_phis (struct dom_walk_data *, basic_block);
96 static void dse_finalize_block (struct dom_walk_data *, basic_block);
97 static void fix_phi_uses (tree, tree);
98 static void fix_stmt_v_may_defs (tree, tree);
99 static void record_voperand_set (bitmap, bitmap *, unsigned int);
101 static unsigned max_stmt_uid; /* Maximal uid of a statement. Uids to phi
102 nodes are assigned using the versions of
103 ssa names they define. */
105 /* Returns uid of statement STMT. */
108 get_stmt_uid (tree stmt)
110 if (TREE_CODE (stmt) == PHI_NODE)
111 return SSA_NAME_VERSION (PHI_RESULT (stmt)) + max_stmt_uid;
113 return stmt_ann (stmt)->uid;
116 /* Function indicating whether we ought to include information for 'var'
117 when calculating immediate uses. For this pass we only want use
118 information for virtual variables. */
121 need_imm_uses_for (tree var)
123 return !is_gimple_reg (var);
127 /* Replace uses in PHI which match V_MAY_DEF_RESULTs in STMT with the
128 corresponding V_MAY_DEF_OP in STMT. */
131 fix_phi_uses (tree phi, tree stmt)
133 stmt_ann_t ann = stmt_ann (stmt);
134 v_may_def_optype v_may_defs;
138 get_stmt_operands (stmt);
139 v_may_defs = V_MAY_DEF_OPS (ann);
141 /* Walk each V_MAY_DEF in STMT. */
142 for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
144 tree v_may_def = V_MAY_DEF_RESULT (v_may_defs, i);
146 /* Find any uses in the PHI which match V_MAY_DEF and replace
147 them with the appropriate V_MAY_DEF_OP. */
148 for (j = 0; j < PHI_NUM_ARGS (phi); j++)
149 if (v_may_def == PHI_ARG_DEF (phi, j))
150 SET_PHI_ARG_DEF (phi, j, V_MAY_DEF_OP (v_may_defs, i));
154 /* Replace the V_MAY_DEF_OPs in STMT1 which match V_MAY_DEF_RESULTs
155 in STMT2 with the appropriate V_MAY_DEF_OPs from STMT2. */
158 fix_stmt_v_may_defs (tree stmt1, tree stmt2)
160 stmt_ann_t ann1 = stmt_ann (stmt1);
161 stmt_ann_t ann2 = stmt_ann (stmt2);
162 v_may_def_optype v_may_defs1;
163 v_may_def_optype v_may_defs2;
166 get_stmt_operands (stmt1);
167 get_stmt_operands (stmt2);
168 v_may_defs1 = V_MAY_DEF_OPS (ann1);
169 v_may_defs2 = V_MAY_DEF_OPS (ann2);
171 /* Walk each V_MAY_DEF_OP in stmt1. */
172 for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs1); i++)
174 tree v_may_def1 = V_MAY_DEF_OP (v_may_defs1, i);
176 /* Find the appropriate V_MAY_DEF_RESULT in STMT2. */
177 for (j = 0; j < NUM_V_MAY_DEFS (v_may_defs2); j++)
179 if (v_may_def1 == V_MAY_DEF_RESULT (v_may_defs2, j))
182 SET_V_MAY_DEF_OP (v_may_defs1, i, V_MAY_DEF_OP (v_may_defs2, j));
187 /* If we did not find a corresponding V_MAY_DEF_RESULT, then something
188 has gone terribly wrong. */
189 gcc_assert (j != NUM_V_MAY_DEFS (v_may_defs2));
194 /* Set bit UID in bitmaps GLOBAL and *LOCAL, creating *LOCAL as needed. */
196 record_voperand_set (bitmap global, bitmap *local, unsigned int uid)
198 /* Lazily allocate the bitmap. Note that we do not get a notification
199 when the block local data structures die, so we allocate the local
200 bitmap backed by the GC system. */
202 *local = BITMAP_GGC_ALLOC ();
204 /* Set the bit in the local and global bitmaps. */
205 bitmap_set_bit (*local, uid);
206 bitmap_set_bit (global, uid);
208 /* Initialize block local data structures. */
211 dse_initialize_block_local_data (struct dom_walk_data *walk_data,
212 basic_block bb ATTRIBUTE_UNUSED,
215 struct dse_block_local_data *bd
216 = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
218 /* If we are given a recycled block local data structure, ensure any
219 bitmap associated with the block is cleared. */
223 bitmap_clear (bd->stores);
227 /* Attempt to eliminate dead stores in the statement referenced by BSI.
229 A dead store is a store into a memory location which will later be
230 overwritten by another store without any intervening loads. In this
231 case the earlier store can be deleted.
233 In our SSA + virtual operand world we use immediate uses of virtual
234 operands to detect dead stores. If a store's virtual definition
235 is used precisely once by a later store to the same location which
236 post dominates the first store, then the first store is dead. */
239 dse_optimize_stmt (struct dom_walk_data *walk_data,
240 basic_block bb ATTRIBUTE_UNUSED,
241 block_stmt_iterator bsi)
243 struct dse_block_local_data *bd
244 = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
245 struct dse_global_data *dse_gd = walk_data->global_data;
246 tree stmt = bsi_stmt (bsi);
247 stmt_ann_t ann = stmt_ann (stmt);
248 v_may_def_optype v_may_defs;
250 get_stmt_operands (stmt);
251 v_may_defs = V_MAY_DEF_OPS (ann);
253 /* If this statement has no virtual uses, then there is nothing
255 if (NUM_V_MAY_DEFS (v_may_defs) == 0)
258 /* We know we have virtual definitions. If this is a MODIFY_EXPR that's
259 not also a function call, then record it into our table. */
260 if (get_call_expr_in (stmt))
262 if (TREE_CODE (stmt) == MODIFY_EXPR)
264 dataflow_t df = get_immediate_uses (stmt);
265 unsigned int num_uses = num_immediate_uses (df);
270 /* If there are no uses then there is nothing left to do. */
273 record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
277 use = immediate_use (df, 0);
280 /* Skip through any PHI nodes we have already seen if the PHI
281 represents the only use of this store.
283 Note this does not handle the case where the store has
284 multiple V_MAY_DEFs which all reach a set of PHI nodes in the
287 && TREE_CODE (use) == PHI_NODE
288 && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use)))
290 /* Record the first PHI we skip so that we can fix its
291 uses if we find that STMT is a dead store. */
295 /* Skip past this PHI and loop again in case we had a PHI
297 df = get_immediate_uses (use);
298 num_uses = num_immediate_uses (df);
299 use = immediate_use (df, 0);
302 /* If we have precisely one immediate use at this point, then we may
303 have found redundant store. */
305 && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use))
306 && operand_equal_p (TREE_OPERAND (stmt, 0),
307 TREE_OPERAND (use, 0), 0))
309 /* We need to fix the operands if either the first PHI we
310 skipped, or the store which we are not deleting if we did
311 not skip any PHIs. */
313 fix_phi_uses (skipped_phi, stmt);
315 fix_stmt_v_may_defs (use, stmt);
317 if (dump_file && (dump_flags & TDF_DETAILS))
319 fprintf (dump_file, " Deleted dead store '");
320 print_generic_expr (dump_file, bsi_stmt (bsi), dump_flags);
321 fprintf (dump_file, "'\n");
324 /* Any immediate uses which reference STMT need to instead
325 reference the new consumer, either SKIPPED_PHI or USE.
326 This allows us to cascade dead stores. */
327 redirect_immediate_uses (stmt, skipped_phi ? skipped_phi : use);
329 /* Be sure to remove any dataflow information attached to
331 free_df_for_stmt (stmt);
333 /* And release any SSA_NAMEs set in this statement back to the
337 /* Finally remove the dead store. */
341 record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
345 /* Record that we have seen the PHIs at the start of BB which correspond
346 to virtual operands. */
348 dse_record_phis (struct dom_walk_data *walk_data, basic_block bb)
350 struct dse_block_local_data *bd
351 = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
352 struct dse_global_data *dse_gd = walk_data->global_data;
355 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
356 if (need_imm_uses_for (PHI_RESULT (phi)))
357 record_voperand_set (dse_gd->stores,
363 dse_finalize_block (struct dom_walk_data *walk_data,
364 basic_block bb ATTRIBUTE_UNUSED)
366 struct dse_block_local_data *bd
367 = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
368 struct dse_global_data *dse_gd = walk_data->global_data;
369 bitmap stores = dse_gd->stores;
372 /* Unwind the stores noted in this basic block. */
374 EXECUTE_IF_SET_IN_BITMAP (bd->stores, 0, i, bitmap_clear_bit (stores, i););
380 struct dom_walk_data walk_data;
381 struct dse_global_data dse_gd;
384 /* Create a UID for each statement in the function. Ordering of the
385 UIDs is not important for this pass. */
389 block_stmt_iterator bsi;
391 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
392 stmt_ann (bsi_stmt (bsi))->uid = max_stmt_uid++;
395 /* We might consider making this a property of each pass so that it
396 can be [re]computed on an as-needed basis. Particularly since
397 this pass could be seen as an extension of DCE which needs post
399 calculate_dominance_info (CDI_POST_DOMINATORS);
401 /* We also need immediate use information for virtual operands. */
402 compute_immediate_uses (TDFA_USE_VOPS, need_imm_uses_for);
404 /* Dead store elimination is fundamentally a walk of the post-dominator
405 tree and a backwards walk of statements within each block. */
406 walk_data.walk_stmts_backward = true;
407 walk_data.dom_direction = CDI_POST_DOMINATORS;
408 walk_data.initialize_block_local_data = dse_initialize_block_local_data;
409 walk_data.before_dom_children_before_stmts = NULL;
410 walk_data.before_dom_children_walk_stmts = dse_optimize_stmt;
411 walk_data.before_dom_children_after_stmts = dse_record_phis;
412 walk_data.after_dom_children_before_stmts = NULL;
413 walk_data.after_dom_children_walk_stmts = NULL;
414 walk_data.after_dom_children_after_stmts = dse_finalize_block;
416 walk_data.block_local_data_size = sizeof (struct dse_block_local_data);
418 /* This is the main hash table for the dead store elimination pass. */
419 dse_gd.stores = BITMAP_XMALLOC ();
420 walk_data.global_data = &dse_gd;
422 /* Initialize the dominator walker. */
423 init_walk_dominator_tree (&walk_data);
425 /* Recursively walk the dominator tree. */
426 walk_dominator_tree (&walk_data, EXIT_BLOCK_PTR);
428 /* Finalize the dominator walker. */
429 fini_walk_dominator_tree (&walk_data);
431 /* Release the main bitmap. */
432 BITMAP_XFREE (dse_gd.stores);
434 /* Free dataflow information. It's probably out of date now anyway. */
437 /* For now, just wipe the post-dominator information. */
438 free_dominance_info (CDI_POST_DOMINATORS);
444 return flag_tree_dse != 0;
447 struct tree_opt_pass pass_dse = {
450 tree_ssa_dse, /* execute */
453 0, /* static_pass_number */
454 TV_TREE_DSE, /* tv_id */
456 | PROP_alias, /* properties_required */
457 0, /* properties_provided */
458 0, /* properties_destroyed */
459 0, /* todo_flags_start */
460 TODO_dump_func | TODO_ggc_collect /* todo_flags_finish */