]>
Commit | Line | Data |
---|---|---|
6de9cd9a | 1 | /* Dead store elimination |
d1e082c2 | 2 | Copyright (C) 2004-2013 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" | |
6de9cd9a DN |
26 | #include "tm_p.h" |
27 | #include "basic-block.h" | |
cf835838 | 28 | #include "gimple-pretty-print.h" |
442b4905 AM |
29 | #include "bitmap.h" |
30 | #include "gimple.h" | |
5be5c238 | 31 | #include "gimple-iterator.h" |
442b4905 AM |
32 | #include "gimple-ssa.h" |
33 | #include "tree-cfg.h" | |
34 | #include "tree-phinodes.h" | |
35 | #include "ssa-iterators.h" | |
36 | #include "tree-ssanames.h" | |
37 | #include "tree-dfa.h" | |
6de9cd9a | 38 | #include "tree-pass.h" |
6de9cd9a DN |
39 | #include "domwalk.h" |
40 | #include "flags.h" | |
dc874b53 | 41 | #include "langhooks.h" |
4484a35a | 42 | #include "tree-cfgcleanup.h" |
6de9cd9a DN |
43 | |
44 | /* This file implements dead store elimination. | |
45 | ||
46 | A dead store is a store into a memory location which will later be | |
47 | overwritten by another store without any intervening loads. In this | |
48 | case the earlier store can be deleted. | |
49 | ||
50 | In our SSA + virtual operand world we use immediate uses of virtual | |
51 | operands to detect dead stores. If a store's virtual definition | |
52 | is used precisely once by a later store to the same location which | |
b8698a0f | 53 | post dominates the first store, then the first store is dead. |
6de9cd9a DN |
54 | |
55 | The single use of the store's virtual definition ensures that | |
56 | there are no intervening aliased loads and the requirement that | |
57 | the second load post dominate the first ensures that if the earlier | |
58 | store executes, then the later stores will execute before the function | |
59 | exits. | |
60 | ||
61 | It may help to think of this as first moving the earlier store to | |
62 | the point immediately before the later store. Again, the single | |
61ada8ae | 63 | use of the virtual definition and the post-dominance relationship |
b8698a0f | 64 | ensure that such movement would be safe. Clearly if there are |
6de9cd9a DN |
65 | back to back stores, then the second is redundant. |
66 | ||
67 | Reviewing section 10.7.2 in Morgan's "Building an Optimizing Compiler" | |
68 | may also help in understanding this code since it discusses the | |
69 | relationship between dead store and redundant load elimination. In | |
70 | fact, they are the same transformation applied to different views of | |
71 | the CFG. */ | |
726a989a | 72 | |
6de9cd9a | 73 | |
caaf13d3 JL |
74 | /* Bitmap of blocks that have had EH statements cleaned. We should |
75 | remove their dead edges eventually. */ | |
76 | static bitmap need_eh_cleanup; | |
77 | ||
6de9cd9a | 78 | static bool gate_dse (void); |
c2924966 | 79 | static unsigned int tree_ssa_dse (void); |
6de9cd9a | 80 | |
6de9cd9a | 81 | |
38635499 | 82 | /* A helper of dse_optimize_stmt. |
5006671f RG |
83 | Given a GIMPLE_ASSIGN in STMT, find a candidate statement *USE_STMT that |
84 | may prove STMT to be dead. | |
38635499 DN |
85 | Return TRUE if the above conditions are met, otherwise FALSE. */ |
86 | ||
87 | static bool | |
5006671f | 88 | dse_possible_dead_store_p (gimple stmt, gimple *use_stmt) |
38635499 | 89 | { |
726a989a | 90 | gimple temp; |
5006671f | 91 | unsigned cnt = 0; |
38635499 | 92 | |
38635499 | 93 | *use_stmt = NULL; |
38635499 | 94 | |
1951f101 MG |
95 | /* Self-assignments are zombies. */ |
96 | if (operand_equal_p (gimple_assign_rhs1 (stmt), gimple_assign_lhs (stmt), 0)) | |
97 | { | |
98 | *use_stmt = stmt; | |
99 | return true; | |
100 | } | |
101 | ||
5006671f RG |
102 | /* Find the first dominated statement that clobbers (part of) the |
103 | memory stmt stores to with no intermediate statement that may use | |
104 | part of the memory stmt stores. That is, find a store that may | |
105 | prove stmt to be a dead store. */ | |
106 | temp = stmt; | |
107 | do | |
108 | { | |
6c9df5a0 | 109 | gimple use_stmt, defvar_def; |
5006671f RG |
110 | imm_use_iterator ui; |
111 | bool fail = false; | |
112 | tree defvar; | |
113 | ||
114 | /* Limit stmt walking to be linear in the number of possibly | |
115 | dead stores. */ | |
116 | if (++cnt > 256) | |
117 | return false; | |
38635499 | 118 | |
726a989a | 119 | if (gimple_code (temp) == GIMPLE_PHI) |
5006671f RG |
120 | defvar = PHI_RESULT (temp); |
121 | else | |
122 | defvar = gimple_vdef (temp); | |
6c9df5a0 | 123 | defvar_def = temp; |
5006671f RG |
124 | temp = NULL; |
125 | FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar) | |
f403a4a2 | 126 | { |
5006671f | 127 | cnt++; |
0f84b066 | 128 | |
cc788fcc RG |
129 | /* If we ever reach our DSE candidate stmt again fail. We |
130 | cannot handle dead stores in loops. */ | |
131 | if (use_stmt == stmt) | |
132 | { | |
133 | fail = true; | |
134 | BREAK_FROM_IMM_USE_STMT (ui); | |
135 | } | |
5006671f RG |
136 | /* In simple cases we can look through PHI nodes, but we |
137 | have to be careful with loops and with memory references | |
138 | containing operands that are also operands of PHI nodes. | |
139 | See gcc.c-torture/execute/20051110-*.c. */ | |
cc788fcc | 140 | else if (gimple_code (use_stmt) == GIMPLE_PHI) |
5006671f RG |
141 | { |
142 | if (temp | |
cc788fcc RG |
143 | /* Make sure we are not in a loop latch block. */ |
144 | || gimple_bb (stmt) == gimple_bb (use_stmt) | |
5006671f | 145 | || dominated_by_p (CDI_DOMINATORS, |
cc788fcc RG |
146 | gimple_bb (stmt), gimple_bb (use_stmt)) |
147 | /* We can look through PHIs to regions post-dominating | |
148 | the DSE candidate stmt. */ | |
149 | || !dominated_by_p (CDI_POST_DOMINATORS, | |
150 | gimple_bb (stmt), gimple_bb (use_stmt))) | |
5006671f RG |
151 | { |
152 | fail = true; | |
153 | BREAK_FROM_IMM_USE_STMT (ui); | |
154 | } | |
6c9df5a0 RG |
155 | /* Do not consider the PHI as use if it dominates the |
156 | stmt defining the virtual operand we are processing, | |
157 | we have processed it already in this case. */ | |
158 | if (gimple_bb (defvar_def) != gimple_bb (use_stmt) | |
159 | && !dominated_by_p (CDI_DOMINATORS, | |
160 | gimple_bb (defvar_def), | |
161 | gimple_bb (use_stmt))) | |
162 | temp = use_stmt; | |
5006671f RG |
163 | } |
164 | /* If the statement is a use the store is not dead. */ | |
165 | else if (ref_maybe_used_by_stmt_p (use_stmt, | |
166 | gimple_assign_lhs (stmt))) | |
0f84b066 AH |
167 | { |
168 | fail = true; | |
5006671f RG |
169 | BREAK_FROM_IMM_USE_STMT (ui); |
170 | } | |
171 | /* If this is a store, remember it or bail out if we have | |
172 | multiple ones (the will be in different CFG parts then). */ | |
173 | else if (gimple_vdef (use_stmt)) | |
174 | { | |
175 | if (temp) | |
176 | { | |
177 | fail = true; | |
178 | BREAK_FROM_IMM_USE_STMT (ui); | |
179 | } | |
180 | temp = use_stmt; | |
0f84b066 AH |
181 | } |
182 | } | |
183 | ||
5006671f RG |
184 | if (fail) |
185 | return false; | |
186 | ||
187 | /* If we didn't find any definition this means the store is dead | |
188 | if it isn't a store to global reachable memory. In this case | |
189 | just pretend the stmt makes itself dead. Otherwise fail. */ | |
190 | if (!temp) | |
38635499 | 191 | { |
209be553 | 192 | if (stmt_may_clobber_global_p (stmt)) |
5006671f RG |
193 | return false; |
194 | ||
195 | temp = stmt; | |
15caa2ab | 196 | break; |
38635499 DN |
197 | } |
198 | } | |
5006671f RG |
199 | /* We deliberately stop on clobbering statements and not only on |
200 | killing ones to make walking cheaper. Otherwise we can just | |
201 | continue walking until both stores have equal reference trees. */ | |
202 | while (!stmt_may_clobber_ref_p (temp, gimple_assign_lhs (stmt))); | |
38635499 | 203 | |
5006671f | 204 | *use_stmt = temp; |
38635499 | 205 | |
38635499 DN |
206 | return true; |
207 | } | |
208 | ||
209 | ||
6de9cd9a DN |
210 | /* Attempt to eliminate dead stores in the statement referenced by BSI. |
211 | ||
212 | A dead store is a store into a memory location which will later be | |
213 | overwritten by another store without any intervening loads. In this | |
214 | case the earlier store can be deleted. | |
215 | ||
216 | In our SSA + virtual operand world we use immediate uses of virtual | |
217 | operands to detect dead stores. If a store's virtual definition | |
218 | is used precisely once by a later store to the same location which | |
219 | post dominates the first store, then the first store is dead. */ | |
220 | ||
221 | static void | |
0285a18e | 222 | dse_optimize_stmt (gimple_stmt_iterator *gsi) |
6de9cd9a | 223 | { |
0285a18e | 224 | gimple stmt = gsi_stmt (*gsi); |
6de9cd9a | 225 | |
773168c7 | 226 | /* If this statement has no virtual defs, then there is nothing |
6de9cd9a | 227 | to do. */ |
5006671f | 228 | if (!gimple_vdef (stmt)) |
6de9cd9a DN |
229 | return; |
230 | ||
726a989a | 231 | /* We know we have virtual definitions. If this is a GIMPLE_ASSIGN |
07beea0d | 232 | that's not also a function call, then record it into our table. */ |
726a989a | 233 | if (is_gimple_call (stmt) && gimple_call_fndecl (stmt)) |
cd709752 | 234 | return; |
e79b60a7 | 235 | |
5d751b0c JJ |
236 | /* Don't return early on *this_2(D) ={v} {CLOBBER}. */ |
237 | if (gimple_has_volatile_ops (stmt) | |
238 | && (!gimple_clobber_p (stmt) | |
239 | || TREE_CODE (gimple_assign_lhs (stmt)) != MEM_REF)) | |
e79b60a7 DN |
240 | return; |
241 | ||
726a989a | 242 | if (is_gimple_assign (stmt)) |
6de9cd9a | 243 | { |
726a989a | 244 | gimple use_stmt; |
6de9cd9a | 245 | |
5006671f RG |
246 | if (!dse_possible_dead_store_p (stmt, &use_stmt)) |
247 | return; | |
8a8b05f4 | 248 | |
5d751b0c JJ |
249 | /* But only remove *this_2(D) ={v} {CLOBBER} if killed by |
250 | another clobber stmt. */ | |
251 | if (gimple_clobber_p (stmt) | |
252 | && !gimple_clobber_p (use_stmt)) | |
253 | return; | |
254 | ||
8a8b05f4 RE |
255 | /* If we have precisely one immediate use at this point and the |
256 | stores are to the same memory location or there is a chain of | |
257 | virtual uses from stmt and the stmt which stores to that same | |
258 | memory location, then we may have found redundant store. */ | |
4a5ba3ed RG |
259 | if ((gimple_has_lhs (use_stmt) |
260 | && (operand_equal_p (gimple_assign_lhs (stmt), | |
261 | gimple_get_lhs (use_stmt), 0))) | |
262 | || stmt_kills_ref_p (use_stmt, gimple_assign_lhs (stmt))) | |
6de9cd9a | 263 | { |
eaf6ca18 RG |
264 | basic_block bb; |
265 | ||
1bdcf037 RG |
266 | /* If use_stmt is or might be a nop assignment, e.g. for |
267 | struct { ... } S a, b, *p; ... | |
268 | b = a; b = b; | |
269 | or | |
270 | b = a; b = *p; where p might be &b, | |
271 | or | |
272 | *p = a; *p = b; where p might be &b, | |
273 | or | |
274 | *p = *u; *p = *v; where p might be v, then USE_STMT | |
275 | acts as a use as well as definition, so store in STMT | |
276 | is not dead. */ | |
5006671f | 277 | if (stmt != use_stmt |
4a5ba3ed | 278 | && ref_maybe_used_by_stmt_p (use_stmt, gimple_assign_lhs (stmt))) |
5006671f | 279 | return; |
3ec1a737 | 280 | |
6de9cd9a DN |
281 | if (dump_file && (dump_flags & TDF_DETAILS)) |
282 | { | |
283 | fprintf (dump_file, " Deleted dead store '"); | |
0285a18e | 284 | print_gimple_stmt (dump_file, gsi_stmt (*gsi), dump_flags, 0); |
6de9cd9a DN |
285 | fprintf (dump_file, "'\n"); |
286 | } | |
38635499 | 287 | |
8d099498 | 288 | /* Then we need to fix the operand of the consuming stmt. */ |
5006671f | 289 | unlink_stmt_vdef (stmt); |
38635499 | 290 | |
f430bae8 | 291 | /* Remove the dead store. */ |
eaf6ca18 | 292 | bb = gimple_bb (stmt); |
0285a18e | 293 | if (gsi_remove (gsi, true)) |
eaf6ca18 | 294 | bitmap_set_bit (need_eh_cleanup, bb->index); |
a5c965c1 JL |
295 | |
296 | /* And release any SSA_NAMEs set in this statement back to the | |
297 | SSA_NAME manager. */ | |
298 | release_defs (stmt); | |
6de9cd9a | 299 | } |
6de9cd9a DN |
300 | } |
301 | } | |
302 | ||
4d9192b5 TS |
303 | class dse_dom_walker : public dom_walker |
304 | { | |
305 | public: | |
306 | dse_dom_walker (cdi_direction direction) : dom_walker (direction) {} | |
307 | ||
308 | virtual void before_dom_children (basic_block); | |
309 | }; | |
310 | ||
311 | void | |
312 | dse_dom_walker::before_dom_children (basic_block bb) | |
6de9cd9a | 313 | { |
726a989a | 314 | gimple_stmt_iterator gsi; |
6de9cd9a | 315 | |
0285a18e MM |
316 | for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);) |
317 | { | |
318 | dse_optimize_stmt (&gsi); | |
319 | if (gsi_end_p (gsi)) | |
320 | gsi = gsi_last_bb (bb); | |
321 | else | |
322 | gsi_prev (&gsi); | |
323 | } | |
6de9cd9a DN |
324 | } |
325 | ||
38635499 DN |
326 | /* Main entry point. */ |
327 | ||
c2924966 | 328 | static unsigned int |
6de9cd9a DN |
329 | tree_ssa_dse (void) |
330 | { | |
caaf13d3 JL |
331 | need_eh_cleanup = BITMAP_ALLOC (NULL); |
332 | ||
908ff6a3 | 333 | renumber_gimple_stmt_uids (); |
6de9cd9a DN |
334 | |
335 | /* We might consider making this a property of each pass so that it | |
336 | can be [re]computed on an as-needed basis. Particularly since | |
337 | this pass could be seen as an extension of DCE which needs post | |
338 | dominators. */ | |
339 | calculate_dominance_info (CDI_POST_DOMINATORS); | |
5006671f | 340 | calculate_dominance_info (CDI_DOMINATORS); |
6de9cd9a | 341 | |
6de9cd9a DN |
342 | /* Dead store elimination is fundamentally a walk of the post-dominator |
343 | tree and a backwards walk of statements within each block. */ | |
4d9192b5 | 344 | dse_dom_walker (CDI_POST_DOMINATORS).walk (cfun->cfg->x_exit_block_ptr); |
6de9cd9a | 345 | |
caaf13d3 JL |
346 | /* Removal of stores may make some EH edges dead. Purge such edges from |
347 | the CFG as needed. */ | |
348 | if (!bitmap_empty_p (need_eh_cleanup)) | |
349 | { | |
350 | gimple_purge_all_dead_eh_edges (need_eh_cleanup); | |
351 | cleanup_tree_cfg (); | |
352 | } | |
353 | ||
354 | BITMAP_FREE (need_eh_cleanup); | |
355 | ||
6de9cd9a DN |
356 | /* For now, just wipe the post-dominator information. */ |
357 | free_dominance_info (CDI_POST_DOMINATORS); | |
c2924966 | 358 | return 0; |
6de9cd9a DN |
359 | } |
360 | ||
361 | static bool | |
362 | gate_dse (void) | |
363 | { | |
364 | return flag_tree_dse != 0; | |
365 | } | |
366 | ||
27a4cd48 DM |
367 | namespace { |
368 | ||
369 | const pass_data pass_data_dse = | |
8ddbbcae | 370 | { |
27a4cd48 DM |
371 | GIMPLE_PASS, /* type */ |
372 | "dse", /* name */ | |
373 | OPTGROUP_NONE, /* optinfo_flags */ | |
374 | true, /* has_gate */ | |
375 | true, /* has_execute */ | |
376 | TV_TREE_DSE, /* tv_id */ | |
377 | ( PROP_cfg | PROP_ssa ), /* properties_required */ | |
378 | 0, /* properties_provided */ | |
379 | 0, /* properties_destroyed */ | |
380 | 0, /* todo_flags_start */ | |
381 | TODO_verify_ssa, /* todo_flags_finish */ | |
6de9cd9a | 382 | }; |
27a4cd48 DM |
383 | |
384 | class pass_dse : public gimple_opt_pass | |
385 | { | |
386 | public: | |
c3284718 RS |
387 | pass_dse (gcc::context *ctxt) |
388 | : gimple_opt_pass (pass_data_dse, ctxt) | |
27a4cd48 DM |
389 | {} |
390 | ||
391 | /* opt_pass methods: */ | |
65d3284b | 392 | opt_pass * clone () { return new pass_dse (m_ctxt); } |
27a4cd48 DM |
393 | bool gate () { return gate_dse (); } |
394 | unsigned int execute () { return tree_ssa_dse (); } | |
395 | ||
396 | }; // class pass_dse | |
397 | ||
398 | } // anon namespace | |
399 | ||
400 | gimple_opt_pass * | |
401 | make_pass_dse (gcc::context *ctxt) | |
402 | { | |
403 | return new pass_dse (ctxt); | |
404 | } |