]>
Commit | Line | Data |
---|---|---|
6de9cd9a | 1 | /* Dead store elimination |
9dcd6f09 | 2 | Copyright (C) 2004, 2005, 2006, 2007 Free Software Foundation, Inc. |
6de9cd9a DN |
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 | |
9dcd6f09 | 8 | the Free Software Foundation; either version 3, or (at your option) |
6de9cd9a DN |
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 | |
9dcd6f09 NC |
17 | along with GCC; see the file COPYING3. If not see |
18 | <http://www.gnu.org/licenses/>. */ | |
6de9cd9a DN |
19 | |
20 | #include "config.h" | |
21 | #include "system.h" | |
22 | #include "coretypes.h" | |
23 | #include "tm.h" | |
6de9cd9a DN |
24 | #include "ggc.h" |
25 | #include "tree.h" | |
26 | #include "rtl.h" | |
27 | #include "tm_p.h" | |
28 | #include "basic-block.h" | |
29 | #include "timevar.h" | |
30 | #include "diagnostic.h" | |
31 | #include "tree-flow.h" | |
32 | #include "tree-pass.h" | |
33 | #include "tree-dump.h" | |
34 | #include "domwalk.h" | |
35 | #include "flags.h" | |
38635499 DN |
36 | #include "hashtab.h" |
37 | #include "sbitmap.h" | |
6de9cd9a DN |
38 | |
39 | /* This file implements dead store elimination. | |
40 | ||
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. | |
44 | ||
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. | |
49 | ||
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 | |
54 | exits. | |
55 | ||
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 | |
61ada8ae | 58 | use of the virtual definition and the post-dominance relationship |
6de9cd9a DN |
59 | ensure that such movement would be safe. Clearly if there are |
60 | back to back stores, then the second is redundant. | |
61 | ||
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 | |
66 | the CFG. */ | |
67 | ||
68 | ||
38635499 DN |
69 | /* Given an aggregate, this records the parts of it which have been |
70 | stored into. */ | |
71 | struct aggregate_vardecl_d | |
72 | { | |
73 | /* The aggregate. */ | |
74 | tree decl; | |
75 | ||
76 | /* Some aggregates are too big for us to handle or never get stored | |
77 | to as a whole. If this field is TRUE, we don't care about this | |
78 | aggregate. */ | |
79 | bool ignore; | |
80 | ||
81 | /* Number of parts in the whole. */ | |
82 | unsigned nparts; | |
83 | ||
84 | /* A bitmap of parts of the aggregate that have been set. If part N | |
85 | of an aggregate has been stored to, bit N should be on. */ | |
86 | sbitmap parts_set; | |
87 | }; | |
88 | ||
6de9cd9a DN |
89 | struct dse_global_data |
90 | { | |
91 | /* This is the global bitmap for store statements. | |
92 | ||
93 | Each statement has a unique ID. When we encounter a store statement | |
94 | that we want to record, set the bit corresponding to the statement's | |
95 | unique ID in this bitmap. */ | |
96 | bitmap stores; | |
38635499 DN |
97 | |
98 | /* A hash table containing the parts of an aggregate which have been | |
99 | stored to. */ | |
100 | htab_t aggregate_vardecl; | |
6de9cd9a DN |
101 | }; |
102 | ||
103 | /* We allocate a bitmap-per-block for stores which are encountered | |
104 | during the scan of that block. This allows us to restore the | |
105 | global bitmap of stores when we finish processing a block. */ | |
106 | struct dse_block_local_data | |
107 | { | |
108 | bitmap stores; | |
109 | }; | |
110 | ||
6c14b137 DJ |
111 | /* Basic blocks of the potentially dead store and the following |
112 | store, for memory_address_same. */ | |
113 | struct address_walk_data | |
114 | { | |
115 | basic_block store1_bb, store2_bb; | |
116 | }; | |
117 | ||
6de9cd9a | 118 | static bool gate_dse (void); |
c2924966 | 119 | static unsigned int tree_ssa_dse (void); |
6de9cd9a DN |
120 | static void dse_initialize_block_local_data (struct dom_walk_data *, |
121 | basic_block, | |
122 | bool); | |
123 | static void dse_optimize_stmt (struct dom_walk_data *, | |
124 | basic_block, | |
125 | block_stmt_iterator); | |
126 | static void dse_record_phis (struct dom_walk_data *, basic_block); | |
127 | static void dse_finalize_block (struct dom_walk_data *, basic_block); | |
6de9cd9a | 128 | static void record_voperand_set (bitmap, bitmap *, unsigned int); |
38635499 | 129 | static void dse_record_partial_aggregate_store (tree, struct dse_global_data *); |
6de9cd9a | 130 | |
30d396e3 ZD |
131 | static unsigned max_stmt_uid; /* Maximal uid of a statement. Uids to phi |
132 | nodes are assigned using the versions of | |
133 | ssa names they define. */ | |
134 | ||
135 | /* Returns uid of statement STMT. */ | |
136 | ||
137 | static unsigned | |
138 | get_stmt_uid (tree stmt) | |
139 | { | |
140 | if (TREE_CODE (stmt) == PHI_NODE) | |
141 | return SSA_NAME_VERSION (PHI_RESULT (stmt)) + max_stmt_uid; | |
142 | ||
143 | return stmt_ann (stmt)->uid; | |
144 | } | |
145 | ||
6de9cd9a | 146 | /* Set bit UID in bitmaps GLOBAL and *LOCAL, creating *LOCAL as needed. */ |
db30731a | 147 | |
6de9cd9a DN |
148 | static void |
149 | record_voperand_set (bitmap global, bitmap *local, unsigned int uid) | |
150 | { | |
151 | /* Lazily allocate the bitmap. Note that we do not get a notification | |
152 | when the block local data structures die, so we allocate the local | |
153 | bitmap backed by the GC system. */ | |
154 | if (*local == NULL) | |
155 | *local = BITMAP_GGC_ALLOC (); | |
156 | ||
157 | /* Set the bit in the local and global bitmaps. */ | |
158 | bitmap_set_bit (*local, uid); | |
159 | bitmap_set_bit (global, uid); | |
160 | } | |
db30731a | 161 | |
6de9cd9a DN |
162 | /* Initialize block local data structures. */ |
163 | ||
164 | static void | |
165 | dse_initialize_block_local_data (struct dom_walk_data *walk_data, | |
166 | basic_block bb ATTRIBUTE_UNUSED, | |
167 | bool recycled) | |
168 | { | |
169 | struct dse_block_local_data *bd | |
c22940cd TN |
170 | = (struct dse_block_local_data *) |
171 | VEC_last (void_p, walk_data->block_data_stack); | |
6de9cd9a DN |
172 | |
173 | /* If we are given a recycled block local data structure, ensure any | |
174 | bitmap associated with the block is cleared. */ | |
175 | if (recycled) | |
176 | { | |
177 | if (bd->stores) | |
178 | bitmap_clear (bd->stores); | |
179 | } | |
180 | } | |
181 | ||
6c14b137 DJ |
182 | /* Helper function for memory_address_same via walk_tree. Returns |
183 | non-NULL if it finds an SSA_NAME which is part of the address, | |
184 | such that the definition of the SSA_NAME post-dominates the store | |
185 | we want to delete but not the store that we believe makes it | |
186 | redundant. This indicates that the address may change between | |
187 | the two stores. */ | |
188 | ||
189 | static tree | |
190 | memory_ssa_name_same (tree *expr_p, int *walk_subtrees ATTRIBUTE_UNUSED, | |
191 | void *data) | |
192 | { | |
c22940cd | 193 | struct address_walk_data *walk_data = (struct address_walk_data *) data; |
6c14b137 DJ |
194 | tree expr = *expr_p; |
195 | tree def_stmt; | |
196 | basic_block def_bb; | |
197 | ||
198 | if (TREE_CODE (expr) != SSA_NAME) | |
199 | return NULL_TREE; | |
200 | ||
201 | /* If we've found a default definition, then there's no problem. Both | |
202 | stores will post-dominate it. And def_bb will be NULL. */ | |
38635499 | 203 | if (SSA_NAME_IS_DEFAULT_DEF (expr)) |
6c14b137 DJ |
204 | return NULL_TREE; |
205 | ||
206 | def_stmt = SSA_NAME_DEF_STMT (expr); | |
207 | def_bb = bb_for_stmt (def_stmt); | |
208 | ||
209 | /* DEF_STMT must dominate both stores. So if it is in the same | |
210 | basic block as one, it does not post-dominate that store. */ | |
211 | if (walk_data->store1_bb != def_bb | |
212 | && dominated_by_p (CDI_POST_DOMINATORS, walk_data->store1_bb, def_bb)) | |
213 | { | |
214 | if (walk_data->store2_bb == def_bb | |
215 | || !dominated_by_p (CDI_POST_DOMINATORS, walk_data->store2_bb, | |
216 | def_bb)) | |
217 | /* Return non-NULL to stop the walk. */ | |
218 | return def_stmt; | |
219 | } | |
220 | ||
221 | return NULL_TREE; | |
222 | } | |
223 | ||
224 | /* Return TRUE if the destination memory address in STORE1 and STORE2 | |
225 | might be modified after STORE1, before control reaches STORE2. */ | |
226 | ||
227 | static bool | |
228 | memory_address_same (tree store1, tree store2) | |
229 | { | |
230 | struct address_walk_data walk_data; | |
231 | ||
232 | walk_data.store1_bb = bb_for_stmt (store1); | |
233 | walk_data.store2_bb = bb_for_stmt (store2); | |
234 | ||
07beea0d | 235 | return (walk_tree (&GIMPLE_STMT_OPERAND (store1, 0), memory_ssa_name_same, |
6c14b137 DJ |
236 | &walk_data, NULL) |
237 | == NULL); | |
238 | } | |
239 | ||
8a8b05f4 RE |
240 | /* Return the use stmt for the lhs of STMT following the virtual |
241 | def-use chains. Returns the MODIFY_EXPR stmt which lhs is equal to | |
242 | the lhs of STMT or NULL_TREE if no such stmt can be found. */ | |
243 | static tree | |
244 | get_use_of_stmt_lhs (tree stmt, | |
245 | use_operand_p * first_use_p, | |
246 | use_operand_p * use_p, tree * use_stmt) | |
247 | { | |
248 | tree usevar, lhs; | |
249 | def_operand_p def_p; | |
250 | ||
251 | if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT) | |
252 | return NULL_TREE; | |
253 | ||
254 | lhs = GIMPLE_STMT_OPERAND (stmt, 0); | |
255 | ||
256 | /* The stmt must have a single VDEF. */ | |
257 | def_p = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_VDEF); | |
258 | if (def_p == NULL_DEF_OPERAND_P) | |
259 | return NULL_TREE; | |
260 | ||
261 | if (!has_single_use (DEF_FROM_PTR (def_p))) | |
262 | return NULL_TREE; | |
263 | /* Get the immediate use of the def. */ | |
264 | single_imm_use (DEF_FROM_PTR (def_p), use_p, use_stmt); | |
265 | gcc_assert (*use_p != NULL_USE_OPERAND_P); | |
266 | first_use_p = use_p; | |
267 | if (TREE_CODE (*use_stmt) != GIMPLE_MODIFY_STMT) | |
268 | return NULL_TREE; | |
269 | ||
270 | do | |
271 | { | |
272 | /* Look at the use stmt and see if it's LHS matches | |
273 | stmt's lhs SSA_NAME. */ | |
274 | def_p = SINGLE_SSA_DEF_OPERAND (*use_stmt, SSA_OP_VDEF); | |
275 | if (def_p == NULL_DEF_OPERAND_P) | |
276 | return NULL_TREE; | |
277 | ||
278 | usevar = GIMPLE_STMT_OPERAND (*use_stmt, 0); | |
279 | if (operand_equal_p (usevar, lhs, 0)) | |
280 | return *use_stmt; | |
281 | ||
282 | if (!has_single_use (DEF_FROM_PTR (def_p))) | |
283 | return NULL_TREE; | |
284 | single_imm_use (DEF_FROM_PTR (def_p), use_p, use_stmt); | |
285 | gcc_assert (*use_p != NULL_USE_OPERAND_P); | |
286 | if (TREE_CODE (*use_stmt) != GIMPLE_MODIFY_STMT) | |
287 | return NULL_TREE; | |
288 | } | |
289 | while (1); | |
290 | ||
291 | return NULL_TREE; | |
292 | } | |
38635499 DN |
293 | |
294 | /* A helper of dse_optimize_stmt. | |
295 | Given a GIMPLE_MODIFY_STMT in STMT, check that each VDEF has one | |
296 | use, and that one use is another VDEF clobbering the first one. | |
297 | ||
298 | Return TRUE if the above conditions are met, otherwise FALSE. */ | |
299 | ||
300 | static bool | |
301 | dse_possible_dead_store_p (tree stmt, | |
302 | use_operand_p *first_use_p, | |
303 | use_operand_p *use_p, | |
304 | tree *use_stmt, | |
305 | struct dse_global_data *dse_gd, | |
306 | struct dse_block_local_data *bd) | |
307 | { | |
308 | ssa_op_iter op_iter; | |
309 | bool fail = false; | |
310 | def_operand_p var1; | |
311 | vuse_vec_p vv; | |
312 | tree defvar = NULL_TREE, temp; | |
313 | tree prev_defvar = NULL_TREE; | |
314 | stmt_ann_t ann = stmt_ann (stmt); | |
315 | ||
316 | /* We want to verify that each virtual definition in STMT has | |
317 | precisely one use and that all the virtual definitions are | |
318 | used by the same single statement. When complete, we | |
319 | want USE_STMT to refer to the one statement which uses | |
320 | all of the virtual definitions from STMT. */ | |
321 | *use_stmt = NULL; | |
322 | FOR_EACH_SSA_VDEF_OPERAND (var1, vv, stmt, op_iter) | |
323 | { | |
324 | defvar = DEF_FROM_PTR (var1); | |
325 | ||
326 | /* If this virtual def does not have precisely one use, then | |
327 | we will not be able to eliminate STMT. */ | |
328 | if (!has_single_use (defvar)) | |
329 | { | |
330 | fail = true; | |
331 | break; | |
332 | } | |
333 | ||
334 | /* Get the one and only immediate use of DEFVAR. */ | |
335 | single_imm_use (defvar, use_p, &temp); | |
336 | gcc_assert (*use_p != NULL_USE_OPERAND_P); | |
337 | *first_use_p = *use_p; | |
338 | ||
0f84b066 AH |
339 | /* In the case of memory partitions, we may get: |
340 | ||
341 | # MPT.764_162 = VDEF <MPT.764_161(D)> | |
342 | x = {}; | |
343 | # MPT.764_167 = VDEF <MPT.764_162> | |
344 | y = {}; | |
345 | ||
346 | So we must make sure we're talking about the same LHS. | |
347 | */ | |
348 | if (TREE_CODE (temp) == GIMPLE_MODIFY_STMT) | |
349 | { | |
350 | tree base1 = get_base_address (GIMPLE_STMT_OPERAND (stmt, 0)); | |
351 | tree base2 = get_base_address (GIMPLE_STMT_OPERAND (temp, 0)); | |
352 | ||
353 | while (base1 && INDIRECT_REF_P (base1)) | |
354 | base1 = TREE_OPERAND (base1, 0); | |
355 | while (base2 && INDIRECT_REF_P (base2)) | |
356 | base2 = TREE_OPERAND (base2, 0); | |
357 | ||
358 | if (base1 != base2) | |
359 | { | |
360 | fail = true; | |
361 | break; | |
362 | } | |
363 | } | |
364 | ||
38635499 DN |
365 | /* If the immediate use of DEF_VAR is not the same as the |
366 | previously find immediate uses, then we will not be able | |
367 | to eliminate STMT. */ | |
368 | if (*use_stmt == NULL) | |
369 | { | |
370 | *use_stmt = temp; | |
371 | prev_defvar = defvar; | |
372 | } | |
373 | else if (temp != *use_stmt) | |
374 | { | |
375 | /* The immediate use and the previously found immediate use | |
376 | must be the same, except... if they're uses of different | |
377 | parts of the whole. */ | |
378 | if (TREE_CODE (defvar) == SSA_NAME | |
379 | && TREE_CODE (SSA_NAME_VAR (defvar)) == STRUCT_FIELD_TAG | |
380 | && TREE_CODE (prev_defvar) == SSA_NAME | |
381 | && TREE_CODE (SSA_NAME_VAR (prev_defvar)) == STRUCT_FIELD_TAG | |
382 | && (SFT_PARENT_VAR (SSA_NAME_VAR (defvar)) | |
383 | == SFT_PARENT_VAR (SSA_NAME_VAR (prev_defvar)))) | |
384 | ; | |
385 | else | |
386 | { | |
387 | fail = true; | |
388 | break; | |
389 | } | |
390 | } | |
391 | } | |
392 | ||
393 | if (fail) | |
394 | { | |
395 | record_voperand_set (dse_gd->stores, &bd->stores, ann->uid); | |
396 | dse_record_partial_aggregate_store (stmt, dse_gd); | |
397 | return false; | |
398 | } | |
399 | ||
400 | /* Skip through any PHI nodes we have already seen if the PHI | |
401 | represents the only use of this store. | |
402 | ||
403 | Note this does not handle the case where the store has | |
404 | multiple VDEFs which all reach a set of PHI nodes in the same block. */ | |
405 | while (*use_p != NULL_USE_OPERAND_P | |
406 | && TREE_CODE (*use_stmt) == PHI_NODE | |
407 | && bitmap_bit_p (dse_gd->stores, get_stmt_uid (*use_stmt))) | |
408 | { | |
409 | /* A PHI node can both define and use the same SSA_NAME if | |
410 | the PHI is at the top of a loop and the PHI_RESULT is | |
411 | a loop invariant and copies have not been fully propagated. | |
412 | ||
413 | The safe thing to do is exit assuming no optimization is | |
414 | possible. */ | |
415 | if (SSA_NAME_DEF_STMT (PHI_RESULT (*use_stmt)) == *use_stmt) | |
416 | return false; | |
417 | ||
418 | /* Skip past this PHI and loop again in case we had a PHI | |
419 | chain. */ | |
420 | single_imm_use (PHI_RESULT (*use_stmt), use_p, use_stmt); | |
421 | } | |
422 | ||
423 | return true; | |
424 | } | |
425 | ||
426 | ||
427 | /* Given a DECL, return its AGGREGATE_VARDECL_D entry. If no entry is | |
428 | found and INSERT is TRUE, add a new entry. */ | |
429 | ||
430 | static struct aggregate_vardecl_d * | |
431 | get_aggregate_vardecl (tree decl, struct dse_global_data *dse_gd, bool insert) | |
432 | { | |
433 | struct aggregate_vardecl_d av, *av_p; | |
434 | void **slot; | |
435 | ||
436 | av.decl = decl; | |
437 | slot = htab_find_slot (dse_gd->aggregate_vardecl, &av, insert ? INSERT : NO_INSERT); | |
438 | ||
439 | ||
440 | /* Not found, and we don't want to insert. */ | |
441 | if (slot == NULL) | |
442 | return NULL; | |
443 | ||
444 | /* Create new entry. */ | |
445 | if (*slot == NULL) | |
446 | { | |
447 | av_p = XNEW (struct aggregate_vardecl_d); | |
448 | av_p->decl = decl; | |
449 | ||
450 | /* Record how many parts the whole has. */ | |
451 | if (TREE_CODE (TREE_TYPE (decl)) == COMPLEX_TYPE) | |
452 | av_p->nparts = 2; | |
453 | else if (TREE_CODE (TREE_TYPE (decl)) == RECORD_TYPE) | |
454 | { | |
455 | tree fields; | |
456 | ||
457 | /* Count the number of fields. */ | |
458 | fields = TYPE_FIELDS (TREE_TYPE (decl)); | |
459 | av_p->nparts = 0; | |
460 | while (fields) | |
461 | { | |
462 | av_p->nparts++; | |
463 | fields = TREE_CHAIN (fields); | |
464 | } | |
465 | } | |
466 | else | |
467 | abort (); | |
468 | ||
469 | av_p->ignore = true; | |
470 | av_p->parts_set = sbitmap_alloc (HOST_BITS_PER_LONG); | |
471 | sbitmap_zero (av_p->parts_set); | |
472 | *slot = av_p; | |
473 | } | |
474 | else | |
475 | av_p = (struct aggregate_vardecl_d *) *slot; | |
476 | ||
477 | return av_p; | |
478 | } | |
479 | ||
480 | ||
481 | /* If STMT is a partial store into an aggregate, record which part got set. */ | |
482 | ||
483 | static void | |
484 | dse_record_partial_aggregate_store (tree stmt, struct dse_global_data *dse_gd) | |
485 | { | |
486 | tree lhs, decl; | |
487 | enum tree_code code; | |
488 | struct aggregate_vardecl_d *av_p; | |
489 | int part; | |
490 | ||
491 | gcc_assert (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT); | |
492 | ||
493 | lhs = GIMPLE_STMT_OPERAND (stmt, 0); | |
494 | code = TREE_CODE (lhs); | |
495 | if (code != IMAGPART_EXPR | |
496 | && code != REALPART_EXPR | |
497 | && code != COMPONENT_REF) | |
498 | return; | |
499 | decl = TREE_OPERAND (lhs, 0); | |
500 | /* Early bail on things like nested COMPONENT_REFs. */ | |
501 | if (TREE_CODE (decl) != VAR_DECL) | |
502 | return; | |
503 | /* Early bail on unions. */ | |
504 | if (code == COMPONENT_REF | |
505 | && TREE_CODE (TREE_TYPE (TREE_OPERAND (lhs, 0))) != RECORD_TYPE) | |
506 | return; | |
507 | ||
508 | av_p = get_aggregate_vardecl (decl, dse_gd, /*insert=*/false); | |
509 | /* Run away, this isn't an aggregate we care about. */ | |
510 | if (!av_p || av_p->ignore) | |
511 | return; | |
512 | ||
513 | switch (code) | |
514 | { | |
515 | case IMAGPART_EXPR: | |
516 | part = 0; | |
517 | break; | |
518 | case REALPART_EXPR: | |
519 | part = 1; | |
520 | break; | |
521 | case COMPONENT_REF: | |
522 | { | |
523 | tree orig_field, fields; | |
524 | tree record_type = TREE_TYPE (TREE_OPERAND (lhs, 0)); | |
525 | ||
526 | /* Get FIELD_DECL. */ | |
527 | orig_field = TREE_OPERAND (lhs, 1); | |
528 | ||
529 | /* FIXME: Eeech, do this more efficiently. Perhaps | |
530 | calculate bit/byte offsets. */ | |
531 | part = -1; | |
532 | fields = TYPE_FIELDS (record_type); | |
533 | while (fields) | |
534 | { | |
535 | ++part; | |
536 | if (fields == orig_field) | |
537 | break; | |
538 | fields = TREE_CHAIN (fields); | |
539 | } | |
540 | gcc_assert (part >= 0); | |
541 | } | |
542 | break; | |
543 | default: | |
544 | return; | |
545 | } | |
546 | ||
547 | /* Record which part was set. */ | |
548 | SET_BIT (av_p->parts_set, part); | |
549 | } | |
550 | ||
551 | ||
552 | /* Return TRUE if all parts in an AGGREGATE_VARDECL have been set. */ | |
553 | ||
554 | static inline bool | |
555 | dse_whole_aggregate_clobbered_p (struct aggregate_vardecl_d *av_p) | |
556 | { | |
557 | unsigned int i; | |
558 | sbitmap_iterator sbi; | |
559 | int nbits_set = 0; | |
560 | ||
561 | /* Count the number of partial stores (bits set). */ | |
562 | EXECUTE_IF_SET_IN_SBITMAP (av_p->parts_set, 0, i, sbi) | |
563 | nbits_set++; | |
564 | return ((unsigned) nbits_set == av_p->nparts); | |
565 | } | |
566 | ||
567 | ||
568 | /* Return TRUE if STMT is a store into a whole aggregate whose parts we | |
569 | have already seen and recorded. */ | |
570 | ||
571 | static bool | |
572 | dse_partial_kill_p (tree stmt, struct dse_global_data *dse_gd) | |
573 | { | |
574 | tree decl; | |
575 | struct aggregate_vardecl_d *av_p; | |
576 | ||
577 | /* Make sure this is a store into the whole. */ | |
578 | if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT) | |
579 | { | |
580 | enum tree_code code; | |
581 | ||
582 | decl = GIMPLE_STMT_OPERAND (stmt, 0); | |
583 | code = TREE_CODE (TREE_TYPE (decl)); | |
584 | ||
585 | if (code != COMPLEX_TYPE && code != RECORD_TYPE) | |
586 | return false; | |
587 | ||
588 | if (TREE_CODE (decl) != VAR_DECL) | |
589 | return false; | |
590 | } | |
591 | else | |
592 | return false; | |
593 | ||
594 | av_p = get_aggregate_vardecl (decl, dse_gd, /*insert=*/false); | |
595 | gcc_assert (av_p != NULL); | |
596 | ||
597 | return dse_whole_aggregate_clobbered_p (av_p); | |
598 | } | |
599 | ||
600 | ||
6de9cd9a DN |
601 | /* Attempt to eliminate dead stores in the statement referenced by BSI. |
602 | ||
603 | A dead store is a store into a memory location which will later be | |
604 | overwritten by another store without any intervening loads. In this | |
605 | case the earlier store can be deleted. | |
606 | ||
607 | In our SSA + virtual operand world we use immediate uses of virtual | |
608 | operands to detect dead stores. If a store's virtual definition | |
609 | is used precisely once by a later store to the same location which | |
610 | post dominates the first store, then the first store is dead. */ | |
611 | ||
612 | static void | |
613 | dse_optimize_stmt (struct dom_walk_data *walk_data, | |
614 | basic_block bb ATTRIBUTE_UNUSED, | |
615 | block_stmt_iterator bsi) | |
616 | { | |
617 | struct dse_block_local_data *bd | |
c22940cd TN |
618 | = (struct dse_block_local_data *) |
619 | VEC_last (void_p, walk_data->block_data_stack); | |
620 | struct dse_global_data *dse_gd | |
621 | = (struct dse_global_data *) walk_data->global_data; | |
6de9cd9a DN |
622 | tree stmt = bsi_stmt (bsi); |
623 | stmt_ann_t ann = stmt_ann (stmt); | |
6de9cd9a | 624 | |
773168c7 | 625 | /* If this statement has no virtual defs, then there is nothing |
6de9cd9a | 626 | to do. */ |
38635499 | 627 | if (ZERO_SSA_OPERANDS (stmt, SSA_OP_VDEF)) |
6de9cd9a DN |
628 | return; |
629 | ||
07beea0d AH |
630 | /* We know we have virtual definitions. If this is a GIMPLE_MODIFY_STMT |
631 | that's not also a function call, then record it into our table. */ | |
cd709752 RH |
632 | if (get_call_expr_in (stmt)) |
633 | return; | |
e79b60a7 DN |
634 | |
635 | if (ann->has_volatile_ops) | |
636 | return; | |
637 | ||
07beea0d | 638 | if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT) |
6de9cd9a | 639 | { |
f430bae8 | 640 | use_operand_p first_use_p = NULL_USE_OPERAND_P; |
db30731a | 641 | use_operand_p use_p = NULL; |
38635499 | 642 | tree use_stmt; |
6de9cd9a | 643 | |
38635499 DN |
644 | if (!dse_possible_dead_store_p (stmt, &first_use_p, &use_p, &use_stmt, |
645 | dse_gd, bd)) | |
646 | return; | |
db30731a | 647 | |
38635499 DN |
648 | /* If this is a partial store into an aggregate, record it. */ |
649 | dse_record_partial_aggregate_store (stmt, dse_gd); | |
6de9cd9a | 650 | |
8a8b05f4 RE |
651 | if (use_p != NULL_USE_OPERAND_P |
652 | && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt)) | |
653 | && (!operand_equal_p (GIMPLE_STMT_OPERAND (stmt, 0), | |
654 | GIMPLE_STMT_OPERAND (use_stmt, 0), 0) | |
655 | && !dse_partial_kill_p (stmt, dse_gd)) | |
656 | && memory_address_same (stmt, use_stmt)) | |
657 | { | |
658 | /* If we have precisely one immediate use at this point, but | |
659 | the stores are not to the same memory location then walk the | |
660 | virtual def-use chain to get the stmt which stores to that same | |
661 | memory location. */ | |
662 | if (get_use_of_stmt_lhs (stmt, &first_use_p, &use_p, &use_stmt) == | |
663 | NULL_TREE) | |
664 | { | |
665 | record_voperand_set (dse_gd->stores, &bd->stores, ann->uid); | |
666 | return; | |
667 | } | |
668 | } | |
669 | ||
670 | /* If we have precisely one immediate use at this point and the | |
671 | stores are to the same memory location or there is a chain of | |
672 | virtual uses from stmt and the stmt which stores to that same | |
673 | memory location, then we may have found redundant store. */ | |
f430bae8 AM |
674 | if (use_p != NULL_USE_OPERAND_P |
675 | && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt)) | |
38635499 DN |
676 | && (operand_equal_p (GIMPLE_STMT_OPERAND (stmt, 0), |
677 | GIMPLE_STMT_OPERAND (use_stmt, 0), 0) | |
678 | || dse_partial_kill_p (stmt, dse_gd)) | |
6c14b137 | 679 | && memory_address_same (stmt, use_stmt)) |
6de9cd9a | 680 | { |
38635499 DN |
681 | ssa_op_iter op_iter; |
682 | def_operand_p var1; | |
683 | vuse_vec_p vv; | |
684 | tree stmt_lhs; | |
6de9cd9a DN |
685 | |
686 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
687 | { | |
688 | fprintf (dump_file, " Deleted dead store '"); | |
689 | print_generic_expr (dump_file, bsi_stmt (bsi), dump_flags); | |
690 | fprintf (dump_file, "'\n"); | |
691 | } | |
38635499 | 692 | |
8d099498 | 693 | /* Then we need to fix the operand of the consuming stmt. */ |
38635499 DN |
694 | stmt_lhs = USE_FROM_PTR (first_use_p); |
695 | FOR_EACH_SSA_VDEF_OPERAND (var1, vv, stmt, op_iter) | |
8d099498 | 696 | { |
38635499 DN |
697 | tree usevar, temp; |
698 | ||
8d099498 | 699 | single_imm_use (DEF_FROM_PTR (var1), &use_p, &temp); |
38635499 DN |
700 | gcc_assert (VUSE_VECT_NUM_ELEM (*vv) == 1); |
701 | usevar = VUSE_ELEMENT_VAR (*vv, 0); | |
702 | SET_USE (use_p, usevar); | |
703 | ||
704 | /* Make sure we propagate the ABNORMAL bit setting. */ | |
705 | if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (stmt_lhs)) | |
706 | SSA_NAME_OCCURS_IN_ABNORMAL_PHI (usevar) = 1; | |
8d099498 | 707 | } |
38635499 | 708 | |
f430bae8 | 709 | /* Remove the dead store. */ |
736432ee | 710 | bsi_remove (&bsi, true); |
a5c965c1 JL |
711 | |
712 | /* And release any SSA_NAMEs set in this statement back to the | |
713 | SSA_NAME manager. */ | |
714 | release_defs (stmt); | |
6de9cd9a DN |
715 | } |
716 | ||
717 | record_voperand_set (dse_gd->stores, &bd->stores, ann->uid); | |
718 | } | |
719 | } | |
720 | ||
721 | /* Record that we have seen the PHIs at the start of BB which correspond | |
722 | to virtual operands. */ | |
723 | static void | |
724 | dse_record_phis (struct dom_walk_data *walk_data, basic_block bb) | |
725 | { | |
726 | struct dse_block_local_data *bd | |
c22940cd TN |
727 | = (struct dse_block_local_data *) |
728 | VEC_last (void_p, walk_data->block_data_stack); | |
729 | struct dse_global_data *dse_gd | |
730 | = (struct dse_global_data *) walk_data->global_data; | |
6de9cd9a DN |
731 | tree phi; |
732 | ||
17192884 | 733 | for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) |
db30731a | 734 | if (!is_gimple_reg (PHI_RESULT (phi))) |
6de9cd9a DN |
735 | record_voperand_set (dse_gd->stores, |
736 | &bd->stores, | |
30d396e3 | 737 | get_stmt_uid (phi)); |
6de9cd9a DN |
738 | } |
739 | ||
740 | static void | |
741 | dse_finalize_block (struct dom_walk_data *walk_data, | |
742 | basic_block bb ATTRIBUTE_UNUSED) | |
743 | { | |
744 | struct dse_block_local_data *bd | |
c22940cd TN |
745 | = (struct dse_block_local_data *) |
746 | VEC_last (void_p, walk_data->block_data_stack); | |
747 | struct dse_global_data *dse_gd | |
748 | = (struct dse_global_data *) walk_data->global_data; | |
6de9cd9a DN |
749 | bitmap stores = dse_gd->stores; |
750 | unsigned int i; | |
87c476a2 | 751 | bitmap_iterator bi; |
6de9cd9a DN |
752 | |
753 | /* Unwind the stores noted in this basic block. */ | |
754 | if (bd->stores) | |
87c476a2 ZD |
755 | EXECUTE_IF_SET_IN_BITMAP (bd->stores, 0, i, bi) |
756 | { | |
757 | bitmap_clear_bit (stores, i); | |
758 | } | |
6de9cd9a DN |
759 | } |
760 | ||
38635499 DN |
761 | |
762 | /* Hashing and equality functions for AGGREGATE_VARDECL. */ | |
763 | ||
764 | static hashval_t | |
765 | aggregate_vardecl_hash (const void *p) | |
766 | { | |
767 | return htab_hash_pointer | |
768 | ((const void *)((const struct aggregate_vardecl_d *)p)->decl); | |
769 | } | |
770 | ||
771 | static int | |
772 | aggregate_vardecl_eq (const void *p1, const void *p2) | |
773 | { | |
774 | return ((const struct aggregate_vardecl_d *)p1)->decl | |
775 | == ((const struct aggregate_vardecl_d *)p2)->decl; | |
776 | } | |
777 | ||
778 | ||
779 | /* Free memory allocated by one entry in AGGREGATE_VARDECL. */ | |
780 | ||
781 | static void | |
782 | aggregate_vardecl_free (void *p) | |
783 | { | |
784 | struct aggregate_vardecl_d *entry = (struct aggregate_vardecl_d *) p; | |
785 | sbitmap_free (entry->parts_set); | |
786 | free (entry); | |
787 | } | |
788 | ||
789 | ||
790 | /* Return true if STMT is a store into an entire aggregate. */ | |
791 | ||
792 | static bool | |
793 | aggregate_whole_store_p (tree stmt) | |
794 | { | |
795 | if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT) | |
796 | { | |
797 | tree lhs = GIMPLE_STMT_OPERAND (stmt, 0); | |
798 | enum tree_code code = TREE_CODE (TREE_TYPE (lhs)); | |
799 | ||
800 | if (code == COMPLEX_TYPE || code == RECORD_TYPE) | |
801 | return true; | |
802 | } | |
803 | return false; | |
804 | } | |
805 | ||
806 | ||
807 | /* Main entry point. */ | |
808 | ||
c2924966 | 809 | static unsigned int |
6de9cd9a DN |
810 | tree_ssa_dse (void) |
811 | { | |
812 | struct dom_walk_data walk_data; | |
813 | struct dse_global_data dse_gd; | |
6de9cd9a DN |
814 | basic_block bb; |
815 | ||
38635499 DN |
816 | dse_gd.aggregate_vardecl = |
817 | htab_create (37, aggregate_vardecl_hash, | |
818 | aggregate_vardecl_eq, aggregate_vardecl_free); | |
819 | ||
30d396e3 | 820 | max_stmt_uid = 0; |
6de9cd9a DN |
821 | FOR_EACH_BB (bb) |
822 | { | |
823 | block_stmt_iterator bsi; | |
6de9cd9a DN |
824 | |
825 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) | |
38635499 DN |
826 | { |
827 | tree stmt = bsi_stmt (bsi); | |
828 | ||
829 | /* Record aggregates which have been stored into as a whole. */ | |
830 | if (aggregate_whole_store_p (stmt)) | |
831 | { | |
832 | tree lhs = GIMPLE_STMT_OPERAND (stmt, 0); | |
833 | if (TREE_CODE (lhs) == VAR_DECL) | |
834 | { | |
835 | struct aggregate_vardecl_d *av_p; | |
836 | ||
837 | av_p = get_aggregate_vardecl (lhs, &dse_gd, /*insert=*/true); | |
838 | av_p->ignore = false; | |
839 | ||
840 | /* Ignore aggregates with too many parts. */ | |
841 | if (av_p->nparts > HOST_BITS_PER_LONG) | |
842 | av_p->ignore = true; | |
843 | } | |
844 | } | |
845 | ||
846 | /* Create a UID for each statement in the function. | |
847 | Ordering of the UIDs is not important for this pass. */ | |
848 | stmt_ann (stmt)->uid = max_stmt_uid++; | |
849 | } | |
6de9cd9a DN |
850 | } |
851 | ||
852 | /* We might consider making this a property of each pass so that it | |
853 | can be [re]computed on an as-needed basis. Particularly since | |
854 | this pass could be seen as an extension of DCE which needs post | |
855 | dominators. */ | |
856 | calculate_dominance_info (CDI_POST_DOMINATORS); | |
857 | ||
6de9cd9a DN |
858 | /* Dead store elimination is fundamentally a walk of the post-dominator |
859 | tree and a backwards walk of statements within each block. */ | |
860 | walk_data.walk_stmts_backward = true; | |
861 | walk_data.dom_direction = CDI_POST_DOMINATORS; | |
862 | walk_data.initialize_block_local_data = dse_initialize_block_local_data; | |
863 | walk_data.before_dom_children_before_stmts = NULL; | |
864 | walk_data.before_dom_children_walk_stmts = dse_optimize_stmt; | |
865 | walk_data.before_dom_children_after_stmts = dse_record_phis; | |
866 | walk_data.after_dom_children_before_stmts = NULL; | |
867 | walk_data.after_dom_children_walk_stmts = NULL; | |
868 | walk_data.after_dom_children_after_stmts = dse_finalize_block; | |
0bca51f0 | 869 | walk_data.interesting_blocks = NULL; |
6de9cd9a DN |
870 | |
871 | walk_data.block_local_data_size = sizeof (struct dse_block_local_data); | |
872 | ||
873 | /* This is the main hash table for the dead store elimination pass. */ | |
8bdbfff5 | 874 | dse_gd.stores = BITMAP_ALLOC (NULL); |
38635499 | 875 | |
6de9cd9a DN |
876 | walk_data.global_data = &dse_gd; |
877 | ||
878 | /* Initialize the dominator walker. */ | |
879 | init_walk_dominator_tree (&walk_data); | |
880 | ||
881 | /* Recursively walk the dominator tree. */ | |
882 | walk_dominator_tree (&walk_data, EXIT_BLOCK_PTR); | |
883 | ||
884 | /* Finalize the dominator walker. */ | |
885 | fini_walk_dominator_tree (&walk_data); | |
886 | ||
38635499 | 887 | /* Release unneeded data. */ |
8bdbfff5 | 888 | BITMAP_FREE (dse_gd.stores); |
38635499 | 889 | htab_delete (dse_gd.aggregate_vardecl); |
6de9cd9a | 890 | |
6de9cd9a DN |
891 | /* For now, just wipe the post-dominator information. */ |
892 | free_dominance_info (CDI_POST_DOMINATORS); | |
c2924966 | 893 | return 0; |
6de9cd9a DN |
894 | } |
895 | ||
896 | static bool | |
897 | gate_dse (void) | |
898 | { | |
899 | return flag_tree_dse != 0; | |
900 | } | |
901 | ||
902 | struct tree_opt_pass pass_dse = { | |
903 | "dse", /* name */ | |
904 | gate_dse, /* gate */ | |
905 | tree_ssa_dse, /* execute */ | |
906 | NULL, /* sub */ | |
907 | NULL, /* next */ | |
908 | 0, /* static_pass_number */ | |
909 | TV_TREE_DSE, /* tv_id */ | |
0bca51f0 DN |
910 | PROP_cfg |
911 | | PROP_ssa | |
c1b763fa | 912 | | PROP_alias, /* properties_required */ |
6de9cd9a DN |
913 | 0, /* properties_provided */ |
914 | 0, /* properties_destroyed */ | |
915 | 0, /* todo_flags_start */ | |
0bca51f0 DN |
916 | TODO_dump_func |
917 | | TODO_ggc_collect | |
0bca51f0 DN |
918 | | TODO_verify_ssa, /* todo_flags_finish */ |
919 | 0 /* letter */ | |
6de9cd9a | 920 | }; |