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 void 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, 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 use = USE_FROM_PTR (use_p);
283
284 /* If the immediate use of DEF_VAR is not the same as the
285 previously find immediate uses, then we will not be able
286 to eliminate STMT. */
287 if (use_stmt == NULL)
288 use_stmt = temp;
289 else if (temp != use_stmt)
290 {
291 fail = true;
292 break;
293 }
294 }
295
296 if (fail)
297 {
298 record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
299 return;
300 }
301
302 /* Skip through any PHI nodes we have already seen if the PHI
303 represents the only use of this store.
304
305 Note this does not handle the case where the store has
306 multiple V_{MAY,MUST}_DEFs which all reach a set of PHI nodes in the
307 same block. */
308 while (use_p != NULL_USE_OPERAND_P
309 && TREE_CODE (use_stmt) == PHI_NODE
310 && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt)))
311 {
312 /* A PHI node can both define and use the same SSA_NAME if
313 the PHI is at the top of a loop and the PHI_RESULT is
314 a loop invariant and copies have not been fully propagated.
315
316 The safe thing to do is exit assuming no optimization is
317 possible. */
318 if (SSA_NAME_DEF_STMT (PHI_RESULT (use_stmt)) == use_stmt)
319 return;
320
321 /* Skip past this PHI and loop again in case we had a PHI
322 chain. */
323 if (single_imm_use (PHI_RESULT (use_stmt), &use_p, &use_stmt))
324 use = USE_FROM_PTR (use_p);
325 }
326
327 /* If we have precisely one immediate use at this point, then we may
328 have found redundant store. Make sure that the stores are to
329 the same memory location. This includes checking that any
330 SSA-form variables in the address will have the same values. */
331 if (use_p != NULL_USE_OPERAND_P
332 && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt))
333 && operand_equal_p (TREE_OPERAND (stmt, 0),
334 TREE_OPERAND (use_stmt, 0), 0)
335 && memory_address_same (stmt, use_stmt))
336 {
337 /* Make sure we propagate the ABNORMAL bit setting. */
338 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (first_use_p)))
339 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (usevar) = 1;
340
341 if (dump_file && (dump_flags & TDF_DETAILS))
342 {
343 fprintf (dump_file, " Deleted dead store '");
344 print_generic_expr (dump_file, bsi_stmt (bsi), dump_flags);
345 fprintf (dump_file, "'\n");
346 }
347 /* Then we need to fix the operand of the consuming stmt. */
348 FOR_EACH_SSA_MUST_AND_MAY_DEF_OPERAND (var1, var2, stmt, op_iter)
349 {
350 single_imm_use (DEF_FROM_PTR (var1), &use_p, &temp);
351 SET_USE (use_p, USE_FROM_PTR (var2));
352 }
353 /* Remove the dead store. */
354 bsi_remove (&bsi);
355
356 /* And release any SSA_NAMEs set in this statement back to the
357 SSA_NAME manager. */
358 release_defs (stmt);
359 }
360
361 record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
362 }
363 }
364
365 /* Record that we have seen the PHIs at the start of BB which correspond
366 to virtual operands. */
367 static void
dse_record_phis(struct dom_walk_data * walk_data,basic_block bb)368 dse_record_phis (struct dom_walk_data *walk_data, basic_block bb)
369 {
370 struct dse_block_local_data *bd
371 = VEC_last (void_p, walk_data->block_data_stack);
372 struct dse_global_data *dse_gd = walk_data->global_data;
373 tree phi;
374
375 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
376 if (!is_gimple_reg (PHI_RESULT (phi)))
377 record_voperand_set (dse_gd->stores,
378 &bd->stores,
379 get_stmt_uid (phi));
380 }
381
382 static void
dse_finalize_block(struct dom_walk_data * walk_data,basic_block bb ATTRIBUTE_UNUSED)383 dse_finalize_block (struct dom_walk_data *walk_data,
384 basic_block bb ATTRIBUTE_UNUSED)
385 {
386 struct dse_block_local_data *bd
387 = VEC_last (void_p, walk_data->block_data_stack);
388 struct dse_global_data *dse_gd = walk_data->global_data;
389 bitmap stores = dse_gd->stores;
390 unsigned int i;
391 bitmap_iterator bi;
392
393 /* Unwind the stores noted in this basic block. */
394 if (bd->stores)
395 EXECUTE_IF_SET_IN_BITMAP (bd->stores, 0, i, bi)
396 {
397 bitmap_clear_bit (stores, i);
398 }
399 }
400
401 static void
tree_ssa_dse(void)402 tree_ssa_dse (void)
403 {
404 struct dom_walk_data walk_data;
405 struct dse_global_data dse_gd;
406 basic_block bb;
407
408 /* Create a UID for each statement in the function. Ordering of the
409 UIDs is not important for this pass. */
410 max_stmt_uid = 0;
411 FOR_EACH_BB (bb)
412 {
413 block_stmt_iterator bsi;
414
415 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
416 stmt_ann (bsi_stmt (bsi))->uid = max_stmt_uid++;
417 }
418
419 /* We might consider making this a property of each pass so that it
420 can be [re]computed on an as-needed basis. Particularly since
421 this pass could be seen as an extension of DCE which needs post
422 dominators. */
423 calculate_dominance_info (CDI_POST_DOMINATORS);
424
425 /* Dead store elimination is fundamentally a walk of the post-dominator
426 tree and a backwards walk of statements within each block. */
427 walk_data.walk_stmts_backward = true;
428 walk_data.dom_direction = CDI_POST_DOMINATORS;
429 walk_data.initialize_block_local_data = dse_initialize_block_local_data;
430 walk_data.before_dom_children_before_stmts = NULL;
431 walk_data.before_dom_children_walk_stmts = dse_optimize_stmt;
432 walk_data.before_dom_children_after_stmts = dse_record_phis;
433 walk_data.after_dom_children_before_stmts = NULL;
434 walk_data.after_dom_children_walk_stmts = NULL;
435 walk_data.after_dom_children_after_stmts = dse_finalize_block;
436 walk_data.interesting_blocks = NULL;
437
438 walk_data.block_local_data_size = sizeof (struct dse_block_local_data);
439
440 /* This is the main hash table for the dead store elimination pass. */
441 dse_gd.stores = BITMAP_ALLOC (NULL);
442 walk_data.global_data = &dse_gd;
443
444 /* Initialize the dominator walker. */
445 init_walk_dominator_tree (&walk_data);
446
447 /* Recursively walk the dominator tree. */
448 walk_dominator_tree (&walk_data, EXIT_BLOCK_PTR);
449
450 /* Finalize the dominator walker. */
451 fini_walk_dominator_tree (&walk_data);
452
453 /* Release the main bitmap. */
454 BITMAP_FREE (dse_gd.stores);
455
456 /* For now, just wipe the post-dominator information. */
457 free_dominance_info (CDI_POST_DOMINATORS);
458 }
459
460 static bool
gate_dse(void)461 gate_dse (void)
462 {
463 return flag_tree_dse != 0;
464 }
465
466 struct tree_opt_pass pass_dse = {
467 "dse", /* name */
468 gate_dse, /* gate */
469 tree_ssa_dse, /* execute */
470 NULL, /* sub */
471 NULL, /* next */
472 0, /* static_pass_number */
473 TV_TREE_DSE, /* tv_id */
474 PROP_cfg
475 | PROP_ssa
476 | PROP_alias, /* properties_required */
477 0, /* properties_provided */
478 0, /* properties_destroyed */
479 0, /* todo_flags_start */
480 TODO_dump_func
481 | TODO_ggc_collect
482 | TODO_verify_ssa, /* todo_flags_finish */
483 0 /* letter */
484 };
485