]>
Commit | Line | Data |
---|---|---|
6de9cd9a | 1 | /* Dead code elimination pass for the GNU compiler. |
058dcc25 ILT |
2 | Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007 |
3 | Free Software Foundation, Inc. | |
6de9cd9a DN |
4 | Contributed by Ben Elliston <bje@redhat.com> |
5 | and Andrew MacLeod <amacleod@redhat.com> | |
6 | Adapted to use control dependence by Steven Bosscher, SUSE Labs. | |
7 | ||
8 | This file is part of GCC. | |
9 | ||
10 | GCC is free software; you can redistribute it and/or modify it | |
11 | under the terms of the GNU General Public License as published by the | |
12 | Free Software Foundation; either version 2, or (at your option) any | |
13 | later version. | |
14 | ||
15 | GCC is distributed in the hope that it will be useful, but WITHOUT | |
16 | ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
17 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
18 | for more details. | |
19 | ||
20 | You should have received a copy of the GNU General Public License | |
21 | along with GCC; see the file COPYING. If not, write to the Free | |
366ccddb KC |
22 | Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA |
23 | 02110-1301, USA. */ | |
6de9cd9a DN |
24 | |
25 | /* Dead code elimination. | |
26 | ||
27 | References: | |
28 | ||
29 | Building an Optimizing Compiler, | |
30 | Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9. | |
31 | ||
32 | Advanced Compiler Design and Implementation, | |
33 | Steven Muchnick, Morgan Kaufmann, 1997, Section 18.10. | |
34 | ||
35 | Dead-code elimination is the removal of statements which have no | |
36 | impact on the program's output. "Dead statements" have no impact | |
37 | on the program's output, while "necessary statements" may have | |
38 | impact on the output. | |
39 | ||
40 | The algorithm consists of three phases: | |
41 | 1. Marking as necessary all statements known to be necessary, | |
42 | e.g. most function calls, writing a value to memory, etc; | |
43 | 2. Propagating necessary statements, e.g., the statements | |
44 | giving values to operands in necessary statements; and | |
45 | 3. Removing dead statements. */ | |
46 | ||
47 | #include "config.h" | |
48 | #include "system.h" | |
49 | #include "coretypes.h" | |
50 | #include "tm.h" | |
6de9cd9a DN |
51 | #include "ggc.h" |
52 | ||
53 | /* These RTL headers are needed for basic-block.h. */ | |
54 | #include "rtl.h" | |
55 | #include "tm_p.h" | |
56 | #include "hard-reg-set.h" | |
7932a3db | 57 | #include "obstack.h" |
6de9cd9a DN |
58 | #include "basic-block.h" |
59 | ||
60 | #include "tree.h" | |
61 | #include "diagnostic.h" | |
62 | #include "tree-flow.h" | |
eadf906f | 63 | #include "tree-gimple.h" |
6de9cd9a DN |
64 | #include "tree-dump.h" |
65 | #include "tree-pass.h" | |
66 | #include "timevar.h" | |
67 | #include "flags.h" | |
49896738 | 68 | #include "cfgloop.h" |
a4176272 | 69 | #include "tree-scalar-evolution.h" |
6de9cd9a DN |
70 | \f |
71 | static struct stmt_stats | |
72 | { | |
73 | int total; | |
74 | int total_phis; | |
75 | int removed; | |
76 | int removed_phis; | |
77 | } stats; | |
78 | ||
906532aa | 79 | static VEC(tree,heap) *worklist; |
6de9cd9a DN |
80 | |
81 | /* Vector indicating an SSA name has already been processed and marked | |
82 | as necessary. */ | |
83 | static sbitmap processed; | |
84 | ||
85 | /* Vector indicating that last_stmt if a basic block has already been | |
86 | marked as necessary. */ | |
87 | static sbitmap last_stmt_necessary; | |
88 | ||
89 | /* Before we can determine whether a control branch is dead, we need to | |
90 | compute which blocks are control dependent on which edges. | |
91 | ||
92 | We expect each block to be control dependent on very few edges so we | |
93 | use a bitmap for each block recording its edges. An array holds the | |
94 | bitmap. The Ith bit in the bitmap is set if that block is dependent | |
95 | on the Ith edge. */ | |
8c80c4aa | 96 | static bitmap *control_dependence_map; |
6de9cd9a | 97 | |
a28fee03 SB |
98 | /* Vector indicating that a basic block has already had all the edges |
99 | processed that it is control dependent on. */ | |
8c80c4aa | 100 | static sbitmap visited_control_parents; |
a28fee03 | 101 | |
9da4058c JL |
102 | /* TRUE if this pass alters the CFG (by removing control statements). |
103 | FALSE otherwise. | |
104 | ||
105 | If this pass alters the CFG, then it will arrange for the dominators | |
106 | to be recomputed. */ | |
107 | static bool cfg_altered; | |
108 | ||
db490c39 KH |
109 | /* Execute code that follows the macro for each edge (given number |
110 | EDGE_NUMBER within the CODE) for which the block with index N is | |
111 | control dependent. */ | |
112 | #define EXECUTE_IF_CONTROL_DEPENDENT(BI, N, EDGE_NUMBER) \ | |
113 | EXECUTE_IF_SET_IN_BITMAP (control_dependence_map[(N)], 0, \ | |
114 | (EDGE_NUMBER), (BI)) | |
6de9cd9a | 115 | |
6de9cd9a | 116 | |
6de9cd9a DN |
117 | /* Indicate block BB is control dependent on an edge with index EDGE_INDEX. */ |
118 | static inline void | |
119 | set_control_dependence_map_bit (basic_block bb, int edge_index) | |
120 | { | |
121 | if (bb == ENTRY_BLOCK_PTR) | |
122 | return; | |
1e128c5f | 123 | gcc_assert (bb != EXIT_BLOCK_PTR); |
6de9cd9a DN |
124 | bitmap_set_bit (control_dependence_map[bb->index], edge_index); |
125 | } | |
126 | ||
127 | /* Clear all control dependences for block BB. */ | |
83f676b3 RS |
128 | static inline void |
129 | clear_control_dependence_bitmap (basic_block bb) | |
6de9cd9a DN |
130 | { |
131 | bitmap_clear (control_dependence_map[bb->index]); | |
132 | } | |
133 | ||
6de9cd9a | 134 | |
9b3b55a1 DN |
135 | /* Find the immediate postdominator PDOM of the specified basic block BLOCK. |
136 | This function is necessary because some blocks have negative numbers. */ | |
137 | ||
138 | static inline basic_block | |
139 | find_pdom (basic_block block) | |
6de9cd9a | 140 | { |
9b3b55a1 | 141 | gcc_assert (block != ENTRY_BLOCK_PTR); |
6de9cd9a | 142 | |
9b3b55a1 DN |
143 | if (block == EXIT_BLOCK_PTR) |
144 | return EXIT_BLOCK_PTR; | |
145 | else | |
146 | { | |
147 | basic_block bb = get_immediate_dominator (CDI_POST_DOMINATORS, block); | |
148 | if (! bb) | |
149 | return EXIT_BLOCK_PTR; | |
150 | return bb; | |
151 | } | |
6de9cd9a DN |
152 | } |
153 | ||
9b3b55a1 | 154 | |
6de9cd9a DN |
155 | /* Determine all blocks' control dependences on the given edge with edge_list |
156 | EL index EDGE_INDEX, ala Morgan, Section 3.6. */ | |
157 | ||
158 | static void | |
159 | find_control_dependence (struct edge_list *el, int edge_index) | |
160 | { | |
161 | basic_block current_block; | |
162 | basic_block ending_block; | |
163 | ||
1e128c5f | 164 | gcc_assert (INDEX_EDGE_PRED_BB (el, edge_index) != EXIT_BLOCK_PTR); |
6de9cd9a DN |
165 | |
166 | if (INDEX_EDGE_PRED_BB (el, edge_index) == ENTRY_BLOCK_PTR) | |
953ff289 | 167 | ending_block = single_succ (ENTRY_BLOCK_PTR); |
6de9cd9a DN |
168 | else |
169 | ending_block = find_pdom (INDEX_EDGE_PRED_BB (el, edge_index)); | |
170 | ||
171 | for (current_block = INDEX_EDGE_SUCC_BB (el, edge_index); | |
172 | current_block != ending_block && current_block != EXIT_BLOCK_PTR; | |
173 | current_block = find_pdom (current_block)) | |
174 | { | |
175 | edge e = INDEX_EDGE (el, edge_index); | |
176 | ||
177 | /* For abnormal edges, we don't make current_block control | |
178 | dependent because instructions that throw are always necessary | |
179 | anyway. */ | |
180 | if (e->flags & EDGE_ABNORMAL) | |
181 | continue; | |
182 | ||
183 | set_control_dependence_map_bit (current_block, edge_index); | |
184 | } | |
185 | } | |
186 | ||
6de9cd9a | 187 | |
9b3b55a1 DN |
188 | /* Record all blocks' control dependences on all edges in the edge |
189 | list EL, ala Morgan, Section 3.6. */ | |
190 | ||
191 | static void | |
192 | find_all_control_dependences (struct edge_list *el) | |
6de9cd9a | 193 | { |
9b3b55a1 | 194 | int i; |
1e128c5f | 195 | |
9b3b55a1 DN |
196 | for (i = 0; i < NUM_EDGES (el); ++i) |
197 | find_control_dependence (el, i); | |
6de9cd9a | 198 | } |
9b3b55a1 DN |
199 | |
200 | ||
07beea0d | 201 | #define NECESSARY(stmt) stmt->base.asm_written_flag |
6de9cd9a DN |
202 | |
203 | /* If STMT is not already marked necessary, mark it, and add it to the | |
204 | worklist if ADD_TO_WORKLIST is true. */ | |
205 | static inline void | |
206 | mark_stmt_necessary (tree stmt, bool add_to_worklist) | |
207 | { | |
1e128c5f | 208 | gcc_assert (stmt); |
1e128c5f | 209 | gcc_assert (!DECL_P (stmt)); |
6de9cd9a DN |
210 | |
211 | if (NECESSARY (stmt)) | |
212 | return; | |
213 | ||
214 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
215 | { | |
216 | fprintf (dump_file, "Marking useful stmt: "); | |
217 | print_generic_stmt (dump_file, stmt, TDF_SLIM); | |
218 | fprintf (dump_file, "\n"); | |
219 | } | |
220 | ||
221 | NECESSARY (stmt) = 1; | |
222 | if (add_to_worklist) | |
906532aa | 223 | VEC_safe_push (tree, heap, worklist, stmt); |
6de9cd9a DN |
224 | } |
225 | ||
38635499 DN |
226 | |
227 | /* Mark the statement defining operand OP as necessary. */ | |
6de9cd9a DN |
228 | |
229 | static inline void | |
38635499 | 230 | mark_operand_necessary (tree op) |
6de9cd9a DN |
231 | { |
232 | tree stmt; | |
233 | int ver; | |
234 | ||
1e128c5f | 235 | gcc_assert (op); |
6de9cd9a DN |
236 | |
237 | ver = SSA_NAME_VERSION (op); | |
238 | if (TEST_BIT (processed, ver)) | |
239 | return; | |
240 | SET_BIT (processed, ver); | |
241 | ||
242 | stmt = SSA_NAME_DEF_STMT (op); | |
1e128c5f | 243 | gcc_assert (stmt); |
6de9cd9a | 244 | |
38635499 | 245 | if (NECESSARY (stmt) || IS_EMPTY_STMT (stmt)) |
6de9cd9a DN |
246 | return; |
247 | ||
248 | NECESSARY (stmt) = 1; | |
906532aa | 249 | VEC_safe_push (tree, heap, worklist, stmt); |
6de9cd9a | 250 | } |
9b3b55a1 | 251 | |
6de9cd9a | 252 | |
adb35797 | 253 | /* Mark STMT as necessary if it obviously is. Add it to the worklist if |
6de9cd9a DN |
254 | it can make other statements necessary. |
255 | ||
256 | If AGGRESSIVE is false, control statements are conservatively marked as | |
257 | necessary. */ | |
258 | ||
259 | static void | |
260 | mark_stmt_if_obviously_necessary (tree stmt, bool aggressive) | |
261 | { | |
6de9cd9a | 262 | stmt_ann_t ann; |
b729952b | 263 | tree op; |
6de9cd9a | 264 | |
75b80166 SB |
265 | /* With non-call exceptions, we have to assume that all statements could |
266 | throw. If a statement may throw, it is inherently necessary. */ | |
267 | if (flag_non_call_exceptions | |
268 | && tree_could_throw_p (stmt)) | |
269 | { | |
270 | mark_stmt_necessary (stmt, true); | |
271 | return; | |
272 | } | |
273 | ||
6de9cd9a DN |
274 | /* Statements that are implicitly live. Most function calls, asm and return |
275 | statements are required. Labels and BIND_EXPR nodes are kept because | |
276 | they are control flow, and we have no way of knowing whether they can be | |
277 | removed. DCE can eliminate all the other statements in a block, and CFG | |
278 | can then remove the block and labels. */ | |
279 | switch (TREE_CODE (stmt)) | |
280 | { | |
281 | case BIND_EXPR: | |
282 | case LABEL_EXPR: | |
283 | case CASE_LABEL_EXPR: | |
284 | mark_stmt_necessary (stmt, false); | |
285 | return; | |
286 | ||
287 | case ASM_EXPR: | |
288 | case RESX_EXPR: | |
289 | case RETURN_EXPR: | |
058dcc25 | 290 | case CHANGE_DYNAMIC_TYPE_EXPR: |
6de9cd9a DN |
291 | mark_stmt_necessary (stmt, true); |
292 | return; | |
293 | ||
294 | case CALL_EXPR: | |
295 | /* Most, but not all function calls are required. Function calls that | |
296 | produce no result and have no side effects (i.e. const pure | |
297 | functions) are unnecessary. */ | |
298 | if (TREE_SIDE_EFFECTS (stmt)) | |
299 | mark_stmt_necessary (stmt, true); | |
300 | return; | |
301 | ||
07beea0d | 302 | case GIMPLE_MODIFY_STMT: |
cd709752 RH |
303 | op = get_call_expr_in (stmt); |
304 | if (op && TREE_SIDE_EFFECTS (op)) | |
6de9cd9a DN |
305 | { |
306 | mark_stmt_necessary (stmt, true); | |
307 | return; | |
308 | } | |
309 | ||
310 | /* These values are mildly magic bits of the EH runtime. We can't | |
311 | see the entire lifetime of these values until landing pads are | |
312 | generated. */ | |
07beea0d AH |
313 | if (TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) == EXC_PTR_EXPR |
314 | || TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) == FILTER_EXPR) | |
6de9cd9a DN |
315 | { |
316 | mark_stmt_necessary (stmt, true); | |
317 | return; | |
318 | } | |
319 | break; | |
320 | ||
321 | case GOTO_EXPR: | |
7f604986 KH |
322 | gcc_assert (!simple_goto_p (stmt)); |
323 | mark_stmt_necessary (stmt, true); | |
6de9cd9a DN |
324 | return; |
325 | ||
326 | case COND_EXPR: | |
269da1e9 | 327 | gcc_assert (EDGE_COUNT (bb_for_stmt (stmt)->succs) == 2); |
6de9cd9a DN |
328 | /* Fall through. */ |
329 | ||
330 | case SWITCH_EXPR: | |
331 | if (! aggressive) | |
332 | mark_stmt_necessary (stmt, true); | |
333 | break; | |
334 | ||
335 | default: | |
336 | break; | |
337 | } | |
338 | ||
339 | ann = stmt_ann (stmt); | |
c597ef4e DN |
340 | |
341 | /* If the statement has volatile operands, it needs to be preserved. | |
342 | Same for statements that can alter control flow in unpredictable | |
343 | ways. */ | |
344 | if (ann->has_volatile_ops || is_ctrl_altering_stmt (stmt)) | |
6de9cd9a DN |
345 | { |
346 | mark_stmt_necessary (stmt, true); | |
347 | return; | |
348 | } | |
349 | ||
fa555252 | 350 | if (is_hidden_global_store (stmt)) |
a32b97a2 | 351 | { |
fa555252 DB |
352 | mark_stmt_necessary (stmt, true); |
353 | return; | |
6de9cd9a DN |
354 | } |
355 | ||
356 | return; | |
357 | } | |
9b3b55a1 DN |
358 | |
359 | ||
360 | /* Make corresponding control dependent edges necessary. We only | |
361 | have to do this once for each basic block, so we clear the bitmap | |
362 | after we're done. */ | |
363 | static void | |
364 | mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el) | |
365 | { | |
366 | bitmap_iterator bi; | |
367 | unsigned edge_number; | |
368 | ||
369 | gcc_assert (bb != EXIT_BLOCK_PTR); | |
370 | ||
371 | if (bb == ENTRY_BLOCK_PTR) | |
372 | return; | |
373 | ||
374 | EXECUTE_IF_CONTROL_DEPENDENT (bi, bb->index, edge_number) | |
375 | { | |
376 | tree t; | |
377 | basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number); | |
378 | ||
379 | if (TEST_BIT (last_stmt_necessary, cd_bb->index)) | |
380 | continue; | |
381 | SET_BIT (last_stmt_necessary, cd_bb->index); | |
382 | ||
383 | t = last_stmt (cd_bb); | |
384 | if (t && is_ctrl_stmt (t)) | |
385 | mark_stmt_necessary (t, true); | |
386 | } | |
387 | } | |
388 | ||
389 | ||
6de9cd9a DN |
390 | /* Find obviously necessary statements. These are things like most function |
391 | calls, and stores to file level variables. | |
392 | ||
393 | If EL is NULL, control statements are conservatively marked as | |
394 | necessary. Otherwise it contains the list of edges used by control | |
395 | dependence analysis. */ | |
396 | ||
397 | static void | |
398 | find_obviously_necessary_stmts (struct edge_list *el) | |
399 | { | |
400 | basic_block bb; | |
401 | block_stmt_iterator i; | |
402 | edge e; | |
403 | ||
404 | FOR_EACH_BB (bb) | |
405 | { | |
406 | tree phi; | |
407 | ||
9b3b55a1 | 408 | /* PHI nodes are never inherently necessary. */ |
17192884 | 409 | for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) |
9b3b55a1 | 410 | NECESSARY (phi) = 0; |
6de9cd9a DN |
411 | |
412 | /* Check all statements in the block. */ | |
413 | for (i = bsi_start (bb); ! bsi_end_p (i); bsi_next (&i)) | |
414 | { | |
415 | tree stmt = bsi_stmt (i); | |
416 | NECESSARY (stmt) = 0; | |
417 | mark_stmt_if_obviously_necessary (stmt, el != NULL); | |
418 | } | |
6de9cd9a DN |
419 | } |
420 | ||
421 | if (el) | |
422 | { | |
423 | /* Prevent the loops from being removed. We must keep the infinite loops, | |
424 | and we currently do not have a means to recognize the finite ones. */ | |
425 | FOR_EACH_BB (bb) | |
426 | { | |
628f6a4e BE |
427 | edge_iterator ei; |
428 | FOR_EACH_EDGE (e, ei, bb->succs) | |
6de9cd9a DN |
429 | if (e->flags & EDGE_DFS_BACK) |
430 | mark_control_dependent_edges_necessary (e->dest, el); | |
431 | } | |
432 | } | |
433 | } | |
6de9cd9a | 434 | |
6de9cd9a | 435 | |
9b3b55a1 DN |
436 | /* Propagate necessity using the operands of necessary statements. |
437 | Process the uses on each statement in the worklist, and add all | |
438 | feeding statements which contribute to the calculation of this | |
439 | value to the worklist. | |
6de9cd9a DN |
440 | |
441 | In conservative mode, EL is NULL. */ | |
442 | ||
443 | static void | |
444 | propagate_necessity (struct edge_list *el) | |
445 | { | |
9b3b55a1 | 446 | tree stmt; |
6de9cd9a DN |
447 | bool aggressive = (el ? true : false); |
448 | ||
449 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
450 | fprintf (dump_file, "\nProcessing worklist:\n"); | |
451 | ||
906532aa | 452 | while (VEC_length (tree, worklist) > 0) |
6de9cd9a | 453 | { |
9b3b55a1 DN |
454 | /* Take STMT from worklist. */ |
455 | stmt = VEC_pop (tree, worklist); | |
6de9cd9a DN |
456 | |
457 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
458 | { | |
459 | fprintf (dump_file, "processing: "); | |
9b3b55a1 | 460 | print_generic_stmt (dump_file, stmt, TDF_SLIM); |
6de9cd9a DN |
461 | fprintf (dump_file, "\n"); |
462 | } | |
463 | ||
464 | if (aggressive) | |
465 | { | |
466 | /* Mark the last statements of the basic blocks that the block | |
9b3b55a1 | 467 | containing STMT is control dependent on, but only if we haven't |
6de9cd9a | 468 | already done so. */ |
9b3b55a1 | 469 | basic_block bb = bb_for_stmt (stmt); |
a28fee03 SB |
470 | if (bb != ENTRY_BLOCK_PTR |
471 | && ! TEST_BIT (visited_control_parents, bb->index)) | |
6de9cd9a | 472 | { |
a28fee03 | 473 | SET_BIT (visited_control_parents, bb->index); |
6de9cd9a DN |
474 | mark_control_dependent_edges_necessary (bb, el); |
475 | } | |
476 | } | |
477 | ||
9b3b55a1 | 478 | if (TREE_CODE (stmt) == PHI_NODE) |
6de9cd9a DN |
479 | { |
480 | /* PHI nodes are somewhat special in that each PHI alternative has | |
481 | data and control dependencies. All the statements feeding the | |
482 | PHI node's arguments are always necessary. In aggressive mode, | |
483 | we also consider the control dependent edges leading to the | |
484 | predecessor block associated with each PHI alternative as | |
485 | necessary. */ | |
486 | int k; | |
9b3b55a1 DN |
487 | |
488 | for (k = 0; k < PHI_NUM_ARGS (stmt); k++) | |
6de9cd9a | 489 | { |
9b3b55a1 | 490 | tree arg = PHI_ARG_DEF (stmt, k); |
6de9cd9a | 491 | if (TREE_CODE (arg) == SSA_NAME) |
38635499 | 492 | mark_operand_necessary (arg); |
6de9cd9a DN |
493 | } |
494 | ||
495 | if (aggressive) | |
496 | { | |
9b3b55a1 | 497 | for (k = 0; k < PHI_NUM_ARGS (stmt); k++) |
6de9cd9a | 498 | { |
9b3b55a1 | 499 | basic_block arg_bb = PHI_ARG_EDGE (stmt, k)->src; |
a28fee03 SB |
500 | if (arg_bb != ENTRY_BLOCK_PTR |
501 | && ! TEST_BIT (visited_control_parents, arg_bb->index)) | |
6de9cd9a | 502 | { |
a28fee03 | 503 | SET_BIT (visited_control_parents, arg_bb->index); |
6de9cd9a DN |
504 | mark_control_dependent_edges_necessary (arg_bb, el); |
505 | } | |
506 | } | |
507 | } | |
508 | } | |
509 | else | |
510 | { | |
511 | /* Propagate through the operands. Examine all the USE, VUSE and | |
38635499 DN |
512 | VDEF operands in this statement. Mark all the statements |
513 | which feed this statement's uses as necessary. The | |
514 | operands of VDEF expressions are also needed as they | |
6de9cd9a | 515 | represent potential definitions that may reach this |
38635499 | 516 | statement (VDEF operands allow us to follow def-def |
a32b97a2 | 517 | links). */ |
38635499 DN |
518 | ssa_op_iter iter; |
519 | tree use; | |
4c124b4c | 520 | |
9b3b55a1 | 521 | FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_ALL_USES) |
38635499 | 522 | mark_operand_necessary (use); |
6de9cd9a DN |
523 | } |
524 | } | |
525 | } | |
52328bf6 DB |
526 | |
527 | ||
6de9cd9a DN |
528 | /* Remove dead PHI nodes from block BB. */ |
529 | ||
7665f023 | 530 | static bool |
6de9cd9a DN |
531 | remove_dead_phis (basic_block bb) |
532 | { | |
533 | tree prev, phi; | |
7665f023 | 534 | bool something_changed = false; |
6de9cd9a DN |
535 | |
536 | prev = NULL_TREE; | |
537 | phi = phi_nodes (bb); | |
538 | while (phi) | |
539 | { | |
540 | stats.total_phis++; | |
541 | ||
542 | if (! NECESSARY (phi)) | |
543 | { | |
17192884 | 544 | tree next = PHI_CHAIN (phi); |
6de9cd9a | 545 | |
7665f023 | 546 | something_changed = true; |
6de9cd9a DN |
547 | if (dump_file && (dump_flags & TDF_DETAILS)) |
548 | { | |
549 | fprintf (dump_file, "Deleting : "); | |
550 | print_generic_stmt (dump_file, phi, TDF_SLIM); | |
551 | fprintf (dump_file, "\n"); | |
552 | } | |
553 | ||
9b3b55a1 | 554 | remove_phi_node (phi, prev, true); |
6de9cd9a DN |
555 | stats.removed_phis++; |
556 | phi = next; | |
557 | } | |
558 | else | |
559 | { | |
560 | prev = phi; | |
17192884 | 561 | phi = PHI_CHAIN (phi); |
6de9cd9a DN |
562 | } |
563 | } | |
7665f023 | 564 | return something_changed; |
6de9cd9a | 565 | } |
9b3b55a1 DN |
566 | |
567 | ||
206048bd | 568 | /* Remove dead statement pointed to by iterator I. Receives the basic block BB |
6de9cd9a DN |
569 | containing I so that we don't have to look it up. */ |
570 | ||
571 | static void | |
572 | remove_dead_stmt (block_stmt_iterator *i, basic_block bb) | |
573 | { | |
574 | tree t = bsi_stmt (*i); | |
575 | ||
576 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
577 | { | |
578 | fprintf (dump_file, "Deleting : "); | |
579 | print_generic_stmt (dump_file, t, TDF_SLIM); | |
580 | fprintf (dump_file, "\n"); | |
581 | } | |
582 | ||
583 | stats.removed++; | |
584 | ||
585 | /* If we have determined that a conditional branch statement contributes | |
586 | nothing to the program, then we not only remove it, but we also change | |
587 | the flow graph so that the current block will simply fall-thru to its | |
588 | immediate post-dominator. The blocks we are circumventing will be | |
6fc0bb99 | 589 | removed by cleanup_tree_cfg if this change in the flow graph makes them |
6de9cd9a DN |
590 | unreachable. */ |
591 | if (is_ctrl_stmt (t)) | |
592 | { | |
593 | basic_block post_dom_bb; | |
e18d4a19 | 594 | |
6de9cd9a | 595 | /* The post dominance info has to be up-to-date. */ |
2b28c07a | 596 | gcc_assert (dom_info_state (CDI_POST_DOMINATORS) == DOM_OK); |
6de9cd9a DN |
597 | /* Get the immediate post dominator of bb. */ |
598 | post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb); | |
6de9cd9a | 599 | |
0a180c0e JL |
600 | /* There are three particularly problematical cases. |
601 | ||
602 | 1. Blocks that do not have an immediate post dominator. This | |
603 | can happen with infinite loops. | |
604 | ||
605 | 2. Blocks that are only post dominated by the exit block. These | |
606 | can also happen for infinite loops as we create fake edges | |
607 | in the dominator tree. | |
608 | ||
609 | 3. If the post dominator has PHI nodes we may be able to compute | |
610 | the right PHI args for them. | |
611 | ||
0a180c0e JL |
612 | In each of these cases we must remove the control statement |
613 | as it may reference SSA_NAMEs which are going to be removed and | |
614 | we remove all but one outgoing edge from the block. */ | |
615 | if (! post_dom_bb | |
616 | || post_dom_bb == EXIT_BLOCK_PTR | |
617 | || phi_nodes (post_dom_bb)) | |
618 | ; | |
e18d4a19 AO |
619 | else |
620 | { | |
621 | /* Redirect the first edge out of BB to reach POST_DOM_BB. */ | |
622 | redirect_edge_and_branch (EDGE_SUCC (bb, 0), post_dom_bb); | |
623 | PENDING_STMT (EDGE_SUCC (bb, 0)) = NULL; | |
30251f7a ZD |
624 | |
625 | /* It is not sufficient to set cfg_altered below during edge | |
626 | removal, in case BB has two successors and one of them | |
627 | is POST_DOM_BB. */ | |
628 | cfg_altered = true; | |
e18d4a19 | 629 | } |
628f6a4e BE |
630 | EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE; |
631 | EDGE_SUCC (bb, 0)->count = bb->count; | |
6de9cd9a DN |
632 | |
633 | /* The edge is no longer associated with a conditional, so it does | |
634 | not have TRUE/FALSE flags. */ | |
628f6a4e | 635 | EDGE_SUCC (bb, 0)->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE); |
6de9cd9a | 636 | |
0a180c0e JL |
637 | /* The lone outgoing edge from BB will be a fallthru edge. */ |
638 | EDGE_SUCC (bb, 0)->flags |= EDGE_FALLTHRU; | |
6de9cd9a DN |
639 | |
640 | /* Remove the remaining the outgoing edges. */ | |
c5cbcccf | 641 | while (!single_succ_p (bb)) |
9da4058c JL |
642 | { |
643 | /* FIXME. When we remove the edge, we modify the CFG, which | |
644 | in turn modifies the dominator and post-dominator tree. | |
645 | Is it safe to postpone recomputing the dominator and | |
646 | post-dominator tree until the end of this pass given that | |
647 | the post-dominators are used above? */ | |
648 | cfg_altered = true; | |
649 | remove_edge (EDGE_SUCC (bb, 1)); | |
650 | } | |
6de9cd9a | 651 | } |
52328bf6 | 652 | |
736432ee | 653 | bsi_remove (i, true); |
52328bf6 | 654 | release_defs (t); |
6de9cd9a | 655 | } |
9b3b55a1 DN |
656 | |
657 | ||
658 | /* Eliminate unnecessary statements. Any instruction not marked as necessary | |
659 | contributes nothing to the program, and can be deleted. */ | |
660 | ||
7665f023 | 661 | static bool |
9b3b55a1 DN |
662 | eliminate_unnecessary_stmts (void) |
663 | { | |
7665f023 | 664 | bool something_changed = false; |
9b3b55a1 DN |
665 | basic_block bb; |
666 | block_stmt_iterator i; | |
667 | ||
668 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
669 | fprintf (dump_file, "\nEliminating unnecessary statements:\n"); | |
670 | ||
671 | clear_special_calls (); | |
672 | FOR_EACH_BB (bb) | |
673 | { | |
674 | /* Remove dead PHI nodes. */ | |
7665f023 | 675 | something_changed |= remove_dead_phis (bb); |
9b3b55a1 DN |
676 | } |
677 | ||
678 | FOR_EACH_BB (bb) | |
679 | { | |
680 | /* Remove dead statements. */ | |
681 | for (i = bsi_start (bb); ! bsi_end_p (i) ; ) | |
682 | { | |
683 | tree t = bsi_stmt (i); | |
684 | ||
685 | stats.total++; | |
686 | ||
687 | /* If `i' is not necessary then remove it. */ | |
688 | if (! NECESSARY (t)) | |
7665f023 JH |
689 | { |
690 | remove_dead_stmt (&i, bb); | |
691 | something_changed = true; | |
692 | } | |
9b3b55a1 DN |
693 | else |
694 | { | |
695 | tree call = get_call_expr_in (t); | |
696 | if (call) | |
cf227303 JH |
697 | { |
698 | tree name; | |
699 | ||
700 | /* When LHS of var = call (); is dead, simplify it into | |
701 | call (); saving one operand. */ | |
702 | if (TREE_CODE (t) == GIMPLE_MODIFY_STMT | |
703 | && (TREE_CODE ((name = GIMPLE_STMT_OPERAND (t, 0))) | |
704 | == SSA_NAME) | |
705 | && !TEST_BIT (processed, SSA_NAME_VERSION (name))) | |
706 | { | |
3659e0cd | 707 | tree oldlhs = GIMPLE_STMT_OPERAND (t, 0); |
cf227303 JH |
708 | something_changed = true; |
709 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
710 | { | |
711 | fprintf (dump_file, "Deleting LHS of call: "); | |
712 | print_generic_stmt (dump_file, t, TDF_SLIM); | |
713 | fprintf (dump_file, "\n"); | |
714 | } | |
715 | push_stmt_changes (bsi_stmt_ptr (i)); | |
716 | TREE_BLOCK (call) = TREE_BLOCK (t); | |
717 | bsi_replace (&i, call, false); | |
718 | maybe_clean_or_replace_eh_stmt (t, call); | |
719 | mark_symbols_for_renaming (call); | |
720 | pop_stmt_changes (bsi_stmt_ptr (i)); | |
3659e0cd | 721 | release_ssa_name (oldlhs); |
cf227303 JH |
722 | } |
723 | notice_special_calls (call); | |
724 | } | |
9b3b55a1 DN |
725 | bsi_next (&i); |
726 | } | |
727 | } | |
728 | } | |
30251f7a | 729 | |
7665f023 | 730 | return something_changed; |
9b3b55a1 DN |
731 | } |
732 | ||
733 | ||
6de9cd9a DN |
734 | /* Print out removed statement statistics. */ |
735 | ||
736 | static void | |
737 | print_stats (void) | |
738 | { | |
739 | if (dump_file && (dump_flags & (TDF_STATS|TDF_DETAILS))) | |
740 | { | |
741 | float percg; | |
742 | ||
743 | percg = ((float) stats.removed / (float) stats.total) * 100; | |
744 | fprintf (dump_file, "Removed %d of %d statements (%d%%)\n", | |
745 | stats.removed, stats.total, (int) percg); | |
746 | ||
747 | if (stats.total_phis == 0) | |
748 | percg = 0; | |
749 | else | |
750 | percg = ((float) stats.removed_phis / (float) stats.total_phis) * 100; | |
751 | ||
752 | fprintf (dump_file, "Removed %d of %d PHI nodes (%d%%)\n", | |
753 | stats.removed_phis, stats.total_phis, (int) percg); | |
754 | } | |
755 | } | |
756 | \f | |
757 | /* Initialization for this pass. Set up the used data structures. */ | |
758 | ||
759 | static void | |
760 | tree_dce_init (bool aggressive) | |
761 | { | |
762 | memset ((void *) &stats, 0, sizeof (stats)); | |
763 | ||
764 | if (aggressive) | |
765 | { | |
766 | int i; | |
767 | ||
e1111e8e | 768 | control_dependence_map = XNEWVEC (bitmap, last_basic_block); |
6de9cd9a | 769 | for (i = 0; i < last_basic_block; ++i) |
8bdbfff5 | 770 | control_dependence_map[i] = BITMAP_ALLOC (NULL); |
6de9cd9a DN |
771 | |
772 | last_stmt_necessary = sbitmap_alloc (last_basic_block); | |
773 | sbitmap_zero (last_stmt_necessary); | |
774 | } | |
775 | ||
95a3742c | 776 | processed = sbitmap_alloc (num_ssa_names + 1); |
6de9cd9a DN |
777 | sbitmap_zero (processed); |
778 | ||
906532aa | 779 | worklist = VEC_alloc (tree, heap, 64); |
9da4058c | 780 | cfg_altered = false; |
6de9cd9a DN |
781 | } |
782 | ||
783 | /* Cleanup after this pass. */ | |
784 | ||
785 | static void | |
786 | tree_dce_done (bool aggressive) | |
787 | { | |
788 | if (aggressive) | |
789 | { | |
790 | int i; | |
791 | ||
792 | for (i = 0; i < last_basic_block; ++i) | |
8bdbfff5 | 793 | BITMAP_FREE (control_dependence_map[i]); |
6de9cd9a DN |
794 | free (control_dependence_map); |
795 | ||
a28fee03 | 796 | sbitmap_free (visited_control_parents); |
6de9cd9a DN |
797 | sbitmap_free (last_stmt_necessary); |
798 | } | |
799 | ||
800 | sbitmap_free (processed); | |
906532aa KH |
801 | |
802 | VEC_free (tree, heap, worklist); | |
6de9cd9a DN |
803 | } |
804 | \f | |
805 | /* Main routine to eliminate dead code. | |
806 | ||
807 | AGGRESSIVE controls the aggressiveness of the algorithm. | |
808 | In conservative mode, we ignore control dependence and simply declare | |
809 | all but the most trivially dead branches necessary. This mode is fast. | |
810 | In aggressive mode, control dependences are taken into account, which | |
811 | results in more dead code elimination, but at the cost of some time. | |
812 | ||
813 | FIXME: Aggressive mode before PRE doesn't work currently because | |
814 | the dominance info is not invalidated after DCE1. This is | |
815 | not an issue right now because we only run aggressive DCE | |
816 | as the last tree SSA pass, but keep this in mind when you | |
817 | start experimenting with pass ordering. */ | |
818 | ||
7665f023 | 819 | static unsigned int |
6de9cd9a DN |
820 | perform_tree_ssa_dce (bool aggressive) |
821 | { | |
822 | struct edge_list *el = NULL; | |
7665f023 | 823 | bool something_changed = 0; |
6de9cd9a DN |
824 | |
825 | tree_dce_init (aggressive); | |
826 | ||
827 | if (aggressive) | |
828 | { | |
829 | /* Compute control dependence. */ | |
830 | timevar_push (TV_CONTROL_DEPENDENCES); | |
831 | calculate_dominance_info (CDI_POST_DOMINATORS); | |
832 | el = create_edge_list (); | |
833 | find_all_control_dependences (el); | |
834 | timevar_pop (TV_CONTROL_DEPENDENCES); | |
835 | ||
a28fee03 SB |
836 | visited_control_parents = sbitmap_alloc (last_basic_block); |
837 | sbitmap_zero (visited_control_parents); | |
838 | ||
6de9cd9a DN |
839 | mark_dfs_back_edges (); |
840 | } | |
841 | ||
842 | find_obviously_necessary_stmts (el); | |
843 | ||
844 | propagate_necessity (el); | |
845 | ||
7665f023 JH |
846 | something_changed |= eliminate_unnecessary_stmts (); |
847 | something_changed |= cfg_altered; | |
6de9cd9a | 848 | |
30251f7a ZD |
849 | /* We do not update postdominators, so free them unconditionally. */ |
850 | free_dominance_info (CDI_POST_DOMINATORS); | |
6de9cd9a | 851 | |
9da4058c JL |
852 | /* If we removed paths in the CFG, then we need to update |
853 | dominators as well. I haven't investigated the possibility | |
854 | of incrementally updating dominators. */ | |
855 | if (cfg_altered) | |
856 | free_dominance_info (CDI_DOMINATORS); | |
857 | ||
6de9cd9a DN |
858 | /* Debugging dumps. */ |
859 | if (dump_file) | |
88a40e67 | 860 | print_stats (); |
6de9cd9a DN |
861 | |
862 | tree_dce_done (aggressive); | |
960076d9 AP |
863 | |
864 | free_edge_list (el); | |
7665f023 JH |
865 | |
866 | if (something_changed) | |
867 | return (TODO_update_ssa | TODO_cleanup_cfg | TODO_ggc_collect | |
868 | | TODO_remove_unused_locals); | |
869 | else | |
870 | return 0; | |
6de9cd9a DN |
871 | } |
872 | ||
873 | /* Pass entry points. */ | |
c2924966 | 874 | static unsigned int |
6de9cd9a DN |
875 | tree_ssa_dce (void) |
876 | { | |
7665f023 | 877 | return perform_tree_ssa_dce (/*aggressive=*/false); |
6de9cd9a DN |
878 | } |
879 | ||
c2924966 | 880 | static unsigned int |
49896738 RH |
881 | tree_ssa_dce_loop (void) |
882 | { | |
7665f023 JH |
883 | unsigned int todo; |
884 | todo = perform_tree_ssa_dce (/*aggressive=*/false); | |
885 | if (todo) | |
886 | { | |
887 | free_numbers_of_iterations_estimates (); | |
888 | scev_reset (); | |
889 | } | |
890 | return todo; | |
49896738 RH |
891 | } |
892 | ||
c2924966 | 893 | static unsigned int |
6de9cd9a DN |
894 | tree_ssa_cd_dce (void) |
895 | { | |
7665f023 | 896 | return perform_tree_ssa_dce (/*aggressive=*/optimize >= 2); |
6de9cd9a DN |
897 | } |
898 | ||
899 | static bool | |
900 | gate_dce (void) | |
901 | { | |
902 | return flag_tree_dce != 0; | |
903 | } | |
904 | ||
905 | struct tree_opt_pass pass_dce = | |
906 | { | |
907 | "dce", /* name */ | |
908 | gate_dce, /* gate */ | |
909 | tree_ssa_dce, /* execute */ | |
910 | NULL, /* sub */ | |
911 | NULL, /* next */ | |
912 | 0, /* static_pass_number */ | |
913 | TV_TREE_DCE, /* tv_id */ | |
7faade0f | 914 | PROP_cfg | PROP_ssa, /* properties_required */ |
6de9cd9a DN |
915 | 0, /* properties_provided */ |
916 | 0, /* properties_destroyed */ | |
917 | 0, /* todo_flags_start */ | |
7665f023 | 918 | TODO_dump_func | TODO_verify_ssa, /* todo_flags_finish */ |
9f8628ba | 919 | 0 /* letter */ |
6de9cd9a DN |
920 | }; |
921 | ||
49896738 RH |
922 | struct tree_opt_pass pass_dce_loop = |
923 | { | |
924 | "dceloop", /* name */ | |
925 | gate_dce, /* gate */ | |
926 | tree_ssa_dce_loop, /* execute */ | |
927 | NULL, /* sub */ | |
928 | NULL, /* next */ | |
929 | 0, /* static_pass_number */ | |
930 | TV_TREE_DCE, /* tv_id */ | |
7faade0f | 931 | PROP_cfg | PROP_ssa, /* properties_required */ |
49896738 RH |
932 | 0, /* properties_provided */ |
933 | 0, /* properties_destroyed */ | |
934 | 0, /* todo_flags_start */ | |
7665f023 | 935 | TODO_dump_func | TODO_verify_ssa, /* todo_flags_finish */ |
49896738 RH |
936 | 0 /* letter */ |
937 | }; | |
938 | ||
6de9cd9a DN |
939 | struct tree_opt_pass pass_cd_dce = |
940 | { | |
941 | "cddce", /* name */ | |
942 | gate_dce, /* gate */ | |
943 | tree_ssa_cd_dce, /* execute */ | |
944 | NULL, /* sub */ | |
945 | NULL, /* next */ | |
946 | 0, /* static_pass_number */ | |
947 | TV_TREE_CD_DCE, /* tv_id */ | |
7faade0f | 948 | PROP_cfg | PROP_ssa, /* properties_required */ |
6de9cd9a DN |
949 | 0, /* properties_provided */ |
950 | 0, /* properties_destroyed */ | |
951 | 0, /* todo_flags_start */ | |
7665f023 JH |
952 | TODO_dump_func | TODO_verify_ssa |
953 | | TODO_verify_flow, /* todo_flags_finish */ | |
9f8628ba | 954 | 0 /* letter */ |
6de9cd9a | 955 | }; |