1 /* Dead store elimination
2 Copyright (C) 2004, 2005 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
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)
9 any later version.
10
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.
15
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, 51 Franklin Street, Fifth Floor,
19 Boston, MA 02110-1301, USA. */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "ggc.h"
26 #include "tree.h"
27 #include "rtl.h"
28 #include "tm_p.h"
29 #include "basic-block.h"
30 #include "timevar.h"
31 #include "diagnostic.h"
32 #include "tree-flow.h"
33 #include "tree-pass.h"
34 #include "tree-dump.h"
35 #include "domwalk.h"
36 #include "flags.h"
37
38 /* This file implements dead store elimination.
39
40 A dead store is a store into a memory location which will later be
41 overwritten by another store without any intervening loads. In this
42 case the earlier store can be deleted.
43
44 In our SSA + virtual operand world we use immediate uses of virtual
45 operands to detect dead stores. If a store's virtual definition
46 is used precisely once by a later store to the same location which
47 post dominates the first store, then the first store is dead.
48
49 The single use of the store's virtual definition ensures that
50 there are no intervening aliased loads and the requirement that
51 the second load post dominate the first ensures that if the earlier
52 store executes, then the later stores will execute before the function
53 exits.
54
55 It may help to think of this as first moving the earlier store to
56 the point immediately before the later store. Again, the single
57 use of the virtual definition and the post-dominance relationship
58 ensure that such movement would be safe. Clearly if there are
59 back to back stores, then the second is redundant.
60
61 Reviewing section 10.7.2 in Morgan's "Building an Optimizing Compiler"
62 may also help in understanding this code since it discusses the
63 relationship between dead store and redundant load elimination. In
64 fact, they are the same transformation applied to different views of
65 the CFG. */
66
67
68 struct dse_global_data
69 {
70 /* This is the global bitmap for store statements.
71
72 Each statement has a unique ID. When we encounter a store statement
73 that we want to record, set the bit corresponding to the statement's
74 unique ID in this bitmap. */
75 bitmap stores;
76 };
77
78 /* We allocate a bitmap-per-block for stores which are encountered
79 during the scan of that block. This allows us to restore the
80 global bitmap of stores when we finish processing a block. */
81 struct dse_block_local_data
82 {
83 bitmap stores;
84 };
85
86 /* Basic blocks of the potentially dead store and the following
87 store, for memory_address_same. */
88 struct address_walk_data
89 {
90 basic_block store1_bb, store2_bb;
91 };
92
93 static bool gate_dse (void);
94 static unsigned int tree_ssa_dse (void);
95 static void dse_initialize_block_local_data (struct dom_walk_data *,
96 basic_block,
97 bool);
98 static void dse_optimize_stmt (struct dom_walk_data *,
99 basic_block,
100 block_stmt_iterator);
101 static void dse_record_phis (struct dom_walk_data *, basic_block);
102 static void dse_finalize_block (struct dom_walk_data *, basic_block);
103 static void record_voperand_set (bitmap, bitmap *, unsigned int);
104
105 static unsigned max_stmt_uid; /* Maximal uid of a statement. Uids to phi
106 nodes are assigned using the versions of
107 ssa names they define. */
108
109 /* Returns uid of statement STMT. */
110
111 static unsigned
get_stmt_uid(tree stmt)112 get_stmt_uid (tree stmt)
113 {
114 if (TREE_CODE (stmt) == PHI_NODE)
115 return SSA_NAME_VERSION (PHI_RESULT (stmt)) + max_stmt_uid;
116
117 return stmt_ann (stmt)->uid;
118 }
119
120 /* Set bit UID in bitmaps GLOBAL and *LOCAL, creating *LOCAL as needed. */
121
122 static void
record_voperand_set(bitmap global,bitmap * local,unsigned int uid)123 record_voperand_set (bitmap global, bitmap *local, unsigned int uid)
124 {
125 /* Lazily allocate the bitmap. Note that we do not get a notification
126 when the block local data structures die, so we allocate the local
127 bitmap backed by the GC system. */
128 if (*local == NULL)
129 *local = BITMAP_GGC_ALLOC ();
130
131 /* Set the bit in the local and global bitmaps. */
132 bitmap_set_bit (*local, uid);
133 bitmap_set_bit (global, uid);
134 }
135
136 /* Initialize block local data structures. */
137
138 static void
dse_initialize_block_local_data(struct dom_walk_data * walk_data,basic_block bb ATTRIBUTE_UNUSED,bool recycled)139 dse_initialize_block_local_data (struct dom_walk_data *walk_data,
140 basic_block bb ATTRIBUTE_UNUSED,
141 bool recycled)
142 {
143 struct dse_block_local_data *bd
144 = VEC_last (void_p, walk_data->block_data_stack);
145
146 /* If we are given a recycled block local data structure, ensure any
147 bitmap associated with the block is cleared. */
148 if (recycled)
149 {
150 if (bd->stores)
151 bitmap_clear (bd->stores);
152 }
153 }
154
155 /* Helper function for memory_address_same via walk_tree. Returns
156 non-NULL if it finds an SSA_NAME which is part of the address,
157 such that the definition of the SSA_NAME post-dominates the store
158 we want to delete but not the store that we believe makes it
159 redundant. This indicates that the address may change between
160 the two stores. */
161
162 static tree
memory_ssa_name_same(tree * expr_p,int * walk_subtrees ATTRIBUTE_UNUSED,void * data)163 memory_ssa_name_same (tree *expr_p, int *walk_subtrees ATTRIBUTE_UNUSED,
164 void *data)
165 {
166 struct address_walk_data *walk_data = data;
167 tree expr = *expr_p;
168 tree def_stmt;
169 basic_block def_bb;
170
171 if (TREE_CODE (expr) != SSA_NAME)
172 return NULL_TREE;
173
174 /* If we've found a default definition, then there's no problem. Both
175 stores will post-dominate it. And def_bb will be NULL. */
176 if (expr == default_def (SSA_NAME_VAR (expr)))
177 return NULL_TREE;
178
179 def_stmt = SSA_NAME_DEF_STMT (expr);
180 def_bb = bb_for_stmt (def_stmt);
181
182 /* DEF_STMT must dominate both stores. So if it is in the same
183 basic block as one, it does not post-dominate that store. */
184 if (walk_data->store1_bb != def_bb
185 && dominated_by_p (CDI_POST_DOMINATORS, walk_data->store1_bb, def_bb))
186 {
187 if (walk_data->store2_bb == def_bb
188 || !dominated_by_p (CDI_POST_DOMINATORS, walk_data->store2_bb,
189 def_bb))
190 /* Return non-NULL to stop the walk. */
191 return def_stmt;
192 }
193
194 return NULL_TREE;
195 }
196
197 /* Return TRUE if the destination memory address in STORE1 and STORE2
198 might be modified after STORE1, before control reaches STORE2. */
199
200 static bool
memory_address_same(tree store1,tree store2)201 memory_address_same (tree store1, tree store2)
202 {
203 struct address_walk_data walk_data;
204
205 walk_data.store1_bb = bb_for_stmt (store1);
206 walk_data.store2_bb = bb_for_stmt (store2);
207
208 return (walk_tree (&TREE_OPERAND (store1, 0), memory_ssa_name_same,
209 &walk_data, NULL)
210 == NULL);
211 }
212
213 /* Attempt to eliminate dead stores in the statement referenced by BSI.
214
215 A dead store is a store into a memory location which will later be
216 overwritten by another store without any intervening loads. In this
217 case the earlier store can be deleted.
218
219 In our SSA + virtual operand world we use immediate uses of virtual
220 operands to detect dead stores. If a store's virtual definition
221 is used precisely once by a later store to the same location which
222 post dominates the first store, then the first store is dead. */
223
224 static void
dse_optimize_stmt(struct dom_walk_data * walk_data,basic_block bb ATTRIBUTE_UNUSED,block_stmt_iterator bsi)225 dse_optimize_stmt (struct dom_walk_data *walk_data,
226 basic_block bb ATTRIBUTE_UNUSED,
227 block_stmt_iterator bsi)
228 {
229 struct dse_block_local_data *bd
230 = VEC_last (void_p, walk_data->block_data_stack);
231 struct dse_global_data *dse_gd = walk_data->global_data;
232 tree stmt = bsi_stmt (bsi);
233 stmt_ann_t ann = stmt_ann (stmt);
234
235 /* If this statement has no virtual defs, then there is nothing
236 to do. */
237 if (ZERO_SSA_OPERANDS (stmt, (SSA_OP_VMAYDEF|SSA_OP_VMUSTDEF)))
238 return;
239
240 /* We know we have virtual definitions. If this is a MODIFY_EXPR that's
241 not also a function call, then record it into our table. */
242 if (get_call_expr_in (stmt))
243 return;
244
245 if (ann->has_volatile_ops)
246 return;
247
248 if (TREE_CODE (stmt) == MODIFY_EXPR)
249 {
250 use_operand_p first_use_p = NULL_USE_OPERAND_P;
251 use_operand_p use_p = NULL;
252 tree use_stmt, temp;
253 tree defvar = NULL_TREE, usevar = NULL_TREE;
254 bool fail = false;
255 use_operand_p var2;
256 def_operand_p var1;
257 ssa_op_iter op_iter;
258
259 /* We want to verify that each virtual definition in STMT has
260 precisely one use and that all the virtual definitions are
261 used by the same single statement. When complete, we
262 want USE_STMT to refer to the one statement which uses
263 all of the virtual definitions from STMT. */
264 use_stmt = NULL;
265 FOR_EACH_SSA_MUST_AND_MAY_DEF_OPERAND (var1, var2, stmt, op_iter)
266 {
267 defvar = DEF_FROM_PTR (var1);
268 usevar = USE_FROM_PTR (var2);
269
270 /* If this virtual def does not have precisely one use, then
271 we will not be able to eliminate STMT. */
272 if (! has_single_use (defvar))
273 {
274 fail = true;
275 break;
276 }
277
278 /* Get the one and only immediate use of DEFVAR. */
279 single_imm_use (defvar, &use_p, &temp);
280 gcc_assert (use_p != NULL_USE_OPERAND_P);
281 first_use_p = use_p;
282
283 /* If the immediate use of DEF_VAR is not the same as the
284 previously find immediate uses, then we will not be able
285 to eliminate STMT. */
286 if (use_stmt == NULL)
287 use_stmt = temp;
288 else if (temp != use_stmt)
289 {
290 fail = true;
291 break;
292 }
293 }
294
295 if (fail)
296 {
297 record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
298 return;
299 }
300
301 /* Skip through any PHI nodes we have already seen if the PHI
302 represents the only use of this store.
303
304 Note this does not handle the case where the store has
305 multiple V_{MAY,MUST}_DEFs which all reach a set of PHI nodes in the
306 same block. */
307 while (use_p != NULL_USE_OPERAND_P
308 && TREE_CODE (use_stmt) == PHI_NODE
309 && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt)))
310 {
311 /* A PHI node can both define and use the same SSA_NAME if
312 the PHI is at the top of a loop and the PHI_RESULT is
313 a loop invariant and copies have not been fully propagated.
314
315 The safe thing to do is exit assuming no optimization is
316 possible. */
317 if (SSA_NAME_DEF_STMT (PHI_RESULT (use_stmt)) == use_stmt)
318 return;
319
320 /* Skip past this PHI and loop again in case we had a PHI
321 chain. */
322 single_imm_use (PHI_RESULT (use_stmt), &use_p, &use_stmt);
323 }
324
325 /* If we have precisely one immediate use at this point, then we may
326 have found redundant store. Make sure that the stores are to
327 the same memory location. This includes checking that any
328 SSA-form variables in the address will have the same values. */
329 if (use_p != NULL_USE_OPERAND_P
330 && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt))
331 && operand_equal_p (TREE_OPERAND (stmt, 0),
332 TREE_OPERAND (use_stmt, 0), 0)
333 && memory_address_same (stmt, use_stmt))
334 {
335 /* Make sure we propagate the ABNORMAL bit setting. */
336 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (first_use_p)))
337 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (usevar) = 1;
338
339 if (dump_file && (dump_flags & TDF_DETAILS))
340 {
341 fprintf (dump_file, " Deleted dead store '");
342 print_generic_expr (dump_file, bsi_stmt (bsi), dump_flags);
343 fprintf (dump_file, "'\n");
344 }
345 /* Then we need to fix the operand of the consuming stmt. */
346 FOR_EACH_SSA_MUST_AND_MAY_DEF_OPERAND (var1, var2, stmt, op_iter)
347 {
348 single_imm_use (DEF_FROM_PTR (var1), &use_p, &temp);
349 SET_USE (use_p, USE_FROM_PTR (var2));
350 }
351 /* Remove the dead store. */
352 bsi_remove (&bsi, true);
353
354 /* And release any SSA_NAMEs set in this statement back to the
355 SSA_NAME manager. */
356 release_defs (stmt);
357 }
358
359 record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
360 }
361 }
362
363 /* Record that we have seen the PHIs at the start of BB which correspond
364 to virtual operands. */
365 static void
dse_record_phis(struct dom_walk_data * walk_data,basic_block bb)366 dse_record_phis (struct dom_walk_data *walk_data, basic_block bb)
367 {
368 struct dse_block_local_data *bd
369 = VEC_last (void_p, walk_data->block_data_stack);
370 struct dse_global_data *dse_gd = walk_data->global_data;
371 tree phi;
372
373 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
374 if (!is_gimple_reg (PHI_RESULT (phi)))
375 record_voperand_set (dse_gd->stores,
376 &bd->stores,
377 get_stmt_uid (phi));
378 }
379
380 static void
dse_finalize_block(struct dom_walk_data * walk_data,basic_block bb ATTRIBUTE_UNUSED)381 dse_finalize_block (struct dom_walk_data *walk_data,
382 basic_block bb ATTRIBUTE_UNUSED)
383 {
384 struct dse_block_local_data *bd
385 = VEC_last (void_p, walk_data->block_data_stack);
386 struct dse_global_data *dse_gd = walk_data->global_data;
387 bitmap stores = dse_gd->stores;
388 unsigned int i;
389 bitmap_iterator bi;
390
391 /* Unwind the stores noted in this basic block. */
392 if (bd->stores)
393 EXECUTE_IF_SET_IN_BITMAP (bd->stores, 0, i, bi)
394 {
395 bitmap_clear_bit (stores, i);
396 }
397 }
398
399 static unsigned int
tree_ssa_dse(void)400 tree_ssa_dse (void)
401 {
402 struct dom_walk_data walk_data;
403 struct dse_global_data dse_gd;
404 basic_block bb;
405
406 /* Create a UID for each statement in the function. Ordering of the
407 UIDs is not important for this pass. */
408 max_stmt_uid = 0;
409 FOR_EACH_BB (bb)
410 {
411 block_stmt_iterator bsi;
412
413 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
414 stmt_ann (bsi_stmt (bsi))->uid = max_stmt_uid++;
415 }
416
417 /* We might consider making this a property of each pass so that it
418 can be [re]computed on an as-needed basis. Particularly since
419 this pass could be seen as an extension of DCE which needs post
420 dominators. */
421 calculate_dominance_info (CDI_POST_DOMINATORS);
422
423 /* Dead store elimination is fundamentally a walk of the post-dominator
424 tree and a backwards walk of statements within each block. */
425 walk_data.walk_stmts_backward = true;
426 walk_data.dom_direction = CDI_POST_DOMINATORS;
427 walk_data.initialize_block_local_data = dse_initialize_block_local_data;
428 walk_data.before_dom_children_before_stmts = NULL;
429 walk_data.before_dom_children_walk_stmts = dse_optimize_stmt;
430 walk_data.before_dom_children_after_stmts = dse_record_phis;
431 walk_data.after_dom_children_before_stmts = NULL;
432 walk_data.after_dom_children_walk_stmts = NULL;
433 walk_data.after_dom_children_after_stmts = dse_finalize_block;
434 walk_data.interesting_blocks = NULL;
435
436 walk_data.block_local_data_size = sizeof (struct dse_block_local_data);
437
438 /* This is the main hash table for the dead store elimination pass. */
439 dse_gd.stores = BITMAP_ALLOC (NULL);
440 walk_data.global_data = &dse_gd;
441
442 /* Initialize the dominator walker. */
443 init_walk_dominator_tree (&walk_data);
444
445 /* Recursively walk the dominator tree. */
446 walk_dominator_tree (&walk_data, EXIT_BLOCK_PTR);
447
448 /* Finalize the dominator walker. */
449 fini_walk_dominator_tree (&walk_data);
450
451 /* Release the main bitmap. */
452 BITMAP_FREE (dse_gd.stores);
453
454 /* For now, just wipe the post-dominator information. */
455 free_dominance_info (CDI_POST_DOMINATORS);
456 return 0;
457 }
458
459 static bool
gate_dse(void)460 gate_dse (void)
461 {
462 return flag_tree_dse != 0;
463 }
464
465 struct tree_opt_pass pass_dse = {
466 "dse", /* name */
467 gate_dse, /* gate */
468 tree_ssa_dse, /* execute */
469 NULL, /* sub */
470 NULL, /* next */
471 0, /* static_pass_number */
472 TV_TREE_DSE, /* tv_id */
473 PROP_cfg
474 | PROP_ssa
475 | PROP_alias, /* properties_required */
476 0, /* properties_provided */
477 0, /* properties_destroyed */
478 0, /* todo_flags_start */
479 TODO_dump_func
480 | TODO_ggc_collect
481 | TODO_verify_ssa, /* todo_flags_finish */
482 0 /* letter */
483 };
484