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