1 /* Dead store elimination
2 Copyright (C) 2004, 2005 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
)
140 FOR_EACH_EDGE (e
, ei
, PHI_BB (phi
)->preds
)
141 if (e
->flags
& EDGE_ABNORMAL
)
144 get_stmt_operands (stmt
);
146 FOR_EACH_SSA_MAYDEF_OPERAND (def_p
, use_p
, stmt
, iter
)
148 tree v_may_def
= DEF_FROM_PTR (def_p
);
149 tree v_may_use
= USE_FROM_PTR (use_p
);
151 /* Find any uses in the PHI which match V_MAY_DEF and replace
152 them with the appropriate V_MAY_DEF_OP. */
153 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
154 if (v_may_def
== PHI_ARG_DEF (phi
, i
))
156 SET_PHI_ARG_DEF (phi
, i
, v_may_use
);
157 /* Update if the new phi argument is an abnormal phi. */
159 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (v_may_use
) = 1;
164 /* Replace the V_MAY_DEF_OPs in STMT1 which match V_MAY_DEF_RESULTs
165 in STMT2 with the appropriate V_MAY_DEF_OPs from STMT2. */
168 fix_stmt_v_may_defs (tree stmt1
, tree stmt2
)
173 use_operand_p use1_p
, use2_p
;
174 def_operand_p def1_p
, def2_p
;
176 get_stmt_operands (stmt1
);
177 get_stmt_operands (stmt2
);
179 /* Walk each V_MAY_DEF_OP in stmt1. */
180 FOR_EACH_SSA_MAYDEF_OPERAND (def1_p
, use1_p
, stmt1
, iter1
)
182 tree use
= USE_FROM_PTR (use1_p
);
184 /* Find the appropriate V_MAY_DEF_RESULT in STMT2. */
185 FOR_EACH_SSA_MAYDEF_OPERAND (def2_p
, use2_p
, stmt2
, iter2
)
187 tree def
= DEF_FROM_PTR (def2_p
);
191 SET_USE (use1_p
, USE_FROM_PTR (use2_p
));
197 /* If we did not find a corresponding V_MAY_DEF_RESULT,
198 then something has gone terribly wrong. */
204 /* Set bit UID in bitmaps GLOBAL and *LOCAL, creating *LOCAL as needed. */
206 record_voperand_set (bitmap global
, bitmap
*local
, unsigned int uid
)
208 /* Lazily allocate the bitmap. Note that we do not get a notification
209 when the block local data structures die, so we allocate the local
210 bitmap backed by the GC system. */
212 *local
= BITMAP_GGC_ALLOC ();
214 /* Set the bit in the local and global bitmaps. */
215 bitmap_set_bit (*local
, uid
);
216 bitmap_set_bit (global
, uid
);
218 /* Initialize block local data structures. */
221 dse_initialize_block_local_data (struct dom_walk_data
*walk_data
,
222 basic_block bb ATTRIBUTE_UNUSED
,
225 struct dse_block_local_data
*bd
226 = VARRAY_TOP_GENERIC_PTR (walk_data
->block_data_stack
);
228 /* If we are given a recycled block local data structure, ensure any
229 bitmap associated with the block is cleared. */
233 bitmap_clear (bd
->stores
);
237 /* Attempt to eliminate dead stores in the statement referenced by BSI.
239 A dead store is a store into a memory location which will later be
240 overwritten by another store without any intervening loads. In this
241 case the earlier store can be deleted.
243 In our SSA + virtual operand world we use immediate uses of virtual
244 operands to detect dead stores. If a store's virtual definition
245 is used precisely once by a later store to the same location which
246 post dominates the first store, then the first store is dead. */
249 dse_optimize_stmt (struct dom_walk_data
*walk_data
,
250 basic_block bb ATTRIBUTE_UNUSED
,
251 block_stmt_iterator bsi
)
253 struct dse_block_local_data
*bd
254 = VARRAY_TOP_GENERIC_PTR (walk_data
->block_data_stack
);
255 struct dse_global_data
*dse_gd
= walk_data
->global_data
;
256 tree stmt
= bsi_stmt (bsi
);
257 stmt_ann_t ann
= stmt_ann (stmt
);
258 v_may_def_optype v_may_defs
;
260 get_stmt_operands (stmt
);
261 v_may_defs
= V_MAY_DEF_OPS (ann
);
263 /* If this statement has no virtual uses, then there is nothing
265 if (NUM_V_MAY_DEFS (v_may_defs
) == 0)
268 /* We know we have virtual definitions. If this is a MODIFY_EXPR that's
269 not also a function call, then record it into our table. */
270 if (get_call_expr_in (stmt
))
273 if (ann
->has_volatile_ops
)
276 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
278 dataflow_t df
= get_immediate_uses (stmt
);
279 unsigned int num_uses
= num_immediate_uses (df
);
283 /* If there are no uses then there is nothing left to do. */
286 record_voperand_set (dse_gd
->stores
, &bd
->stores
, ann
->uid
);
290 use
= immediate_use (df
, 0);
293 /* Skip through any PHI nodes we have already seen if the PHI
294 represents the only use of this store.
296 Note this does not handle the case where the store has
297 multiple V_MAY_DEFs which all reach a set of PHI nodes in the
300 && TREE_CODE (use
) == PHI_NODE
301 && bitmap_bit_p (dse_gd
->stores
, get_stmt_uid (use
)))
303 /* Record the first PHI we skip so that we can fix its
304 uses if we find that STMT is a dead store. */
308 /* Skip past this PHI and loop again in case we had a PHI
310 df
= get_immediate_uses (use
);
311 num_uses
= num_immediate_uses (df
);
312 use
= immediate_use (df
, 0);
315 /* If we have precisely one immediate use at this point, then we may
316 have found redundant store. */
318 && bitmap_bit_p (dse_gd
->stores
, get_stmt_uid (use
))
319 && operand_equal_p (TREE_OPERAND (stmt
, 0),
320 TREE_OPERAND (use
, 0), 0))
322 /* We need to fix the operands if either the first PHI we
323 skipped, or the store which we are not deleting if we did
324 not skip any PHIs. */
326 fix_phi_uses (skipped_phi
, stmt
);
328 fix_stmt_v_may_defs (use
, stmt
);
330 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
332 fprintf (dump_file
, " Deleted dead store '");
333 print_generic_expr (dump_file
, bsi_stmt (bsi
), dump_flags
);
334 fprintf (dump_file
, "'\n");
337 /* Any immediate uses which reference STMT need to instead
338 reference the new consumer, either SKIPPED_PHI or USE.
339 This allows us to cascade dead stores. */
340 redirect_immediate_uses (stmt
, skipped_phi
? skipped_phi
: use
);
342 /* Be sure to remove any dataflow information attached to
344 free_df_for_stmt (stmt
);
346 /* And release any SSA_NAMEs set in this statement back to the
350 /* Finally remove the dead store. */
354 record_voperand_set (dse_gd
->stores
, &bd
->stores
, ann
->uid
);
358 /* Record that we have seen the PHIs at the start of BB which correspond
359 to virtual operands. */
361 dse_record_phis (struct dom_walk_data
*walk_data
, basic_block bb
)
363 struct dse_block_local_data
*bd
364 = VARRAY_TOP_GENERIC_PTR (walk_data
->block_data_stack
);
365 struct dse_global_data
*dse_gd
= walk_data
->global_data
;
368 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
369 if (need_imm_uses_for (PHI_RESULT (phi
)))
370 record_voperand_set (dse_gd
->stores
,
376 dse_finalize_block (struct dom_walk_data
*walk_data
,
377 basic_block bb ATTRIBUTE_UNUSED
)
379 struct dse_block_local_data
*bd
380 = VARRAY_TOP_GENERIC_PTR (walk_data
->block_data_stack
);
381 struct dse_global_data
*dse_gd
= walk_data
->global_data
;
382 bitmap stores
= dse_gd
->stores
;
386 /* Unwind the stores noted in this basic block. */
388 EXECUTE_IF_SET_IN_BITMAP (bd
->stores
, 0, i
, bi
)
390 bitmap_clear_bit (stores
, i
);
397 struct dom_walk_data walk_data
;
398 struct dse_global_data dse_gd
;
401 /* Create a UID for each statement in the function. Ordering of the
402 UIDs is not important for this pass. */
406 block_stmt_iterator bsi
;
408 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
409 stmt_ann (bsi_stmt (bsi
))->uid
= max_stmt_uid
++;
412 /* We might consider making this a property of each pass so that it
413 can be [re]computed on an as-needed basis. Particularly since
414 this pass could be seen as an extension of DCE which needs post
416 calculate_dominance_info (CDI_POST_DOMINATORS
);
418 /* We also need immediate use information for virtual operands. */
419 compute_immediate_uses (TDFA_USE_VOPS
, need_imm_uses_for
);
421 /* Dead store elimination is fundamentally a walk of the post-dominator
422 tree and a backwards walk of statements within each block. */
423 walk_data
.walk_stmts_backward
= true;
424 walk_data
.dom_direction
= CDI_POST_DOMINATORS
;
425 walk_data
.initialize_block_local_data
= dse_initialize_block_local_data
;
426 walk_data
.before_dom_children_before_stmts
= NULL
;
427 walk_data
.before_dom_children_walk_stmts
= dse_optimize_stmt
;
428 walk_data
.before_dom_children_after_stmts
= dse_record_phis
;
429 walk_data
.after_dom_children_before_stmts
= NULL
;
430 walk_data
.after_dom_children_walk_stmts
= NULL
;
431 walk_data
.after_dom_children_after_stmts
= dse_finalize_block
;
433 walk_data
.block_local_data_size
= sizeof (struct dse_block_local_data
);
435 /* This is the main hash table for the dead store elimination pass. */
436 dse_gd
.stores
= BITMAP_ALLOC (NULL
);
437 walk_data
.global_data
= &dse_gd
;
439 /* Initialize the dominator walker. */
440 init_walk_dominator_tree (&walk_data
);
442 /* Recursively walk the dominator tree. */
443 walk_dominator_tree (&walk_data
, EXIT_BLOCK_PTR
);
445 /* Finalize the dominator walker. */
446 fini_walk_dominator_tree (&walk_data
);
448 /* Release the main bitmap. */
449 BITMAP_FREE (dse_gd
.stores
);
451 /* Free dataflow information. It's probably out of date now anyway. */
454 /* For now, just wipe the post-dominator information. */
455 free_dominance_info (CDI_POST_DOMINATORS
);
461 return flag_tree_dse
!= 0;
464 struct tree_opt_pass pass_dse
= {
467 tree_ssa_dse
, /* execute */
470 0, /* static_pass_number */
471 TV_TREE_DSE
, /* tv_id */
473 | PROP_alias
, /* properties_required */
474 0, /* properties_provided */
475 0, /* properties_destroyed */
476 0, /* todo_flags_start */
477 TODO_dump_func
| TODO_ggc_collect
/* todo_flags_finish */