]>
Commit | Line | Data |
---|---|---|
4ee9c684 | 1 | /* Dead code elimination pass for the GNU compiler. |
fbd26352 | 2 | Copyright (C) 2002-2019 Free Software Foundation, Inc. |
4ee9c684 | 3 | Contributed by Ben Elliston <bje@redhat.com> |
4 | and Andrew MacLeod <amacleod@redhat.com> | |
5 | Adapted to use control dependence by Steven Bosscher, SUSE Labs. | |
48e1416a | 6 | |
4ee9c684 | 7 | This file is part of GCC. |
48e1416a | 8 | |
4ee9c684 | 9 | GCC is free software; you can redistribute it and/or modify it |
10 | under the terms of the GNU General Public License as published by the | |
8c4c00c1 | 11 | Free Software Foundation; either version 3, or (at your option) any |
4ee9c684 | 12 | later version. |
48e1416a | 13 | |
4ee9c684 | 14 | GCC is distributed in the hope that it will be useful, but WITHOUT |
15 | ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
16 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
17 | for more details. | |
48e1416a | 18 | |
4ee9c684 | 19 | You should have received a copy of the GNU General Public License |
8c4c00c1 | 20 | along with GCC; see the file COPYING3. If not see |
21 | <http://www.gnu.org/licenses/>. */ | |
4ee9c684 | 22 | |
23 | /* Dead code elimination. | |
24 | ||
25 | References: | |
26 | ||
27 | Building an Optimizing Compiler, | |
28 | Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9. | |
29 | ||
30 | Advanced Compiler Design and Implementation, | |
31 | Steven Muchnick, Morgan Kaufmann, 1997, Section 18.10. | |
32 | ||
33 | Dead-code elimination is the removal of statements which have no | |
34 | impact on the program's output. "Dead statements" have no impact | |
35 | on the program's output, while "necessary statements" may have | |
36 | impact on the output. | |
37 | ||
38 | The algorithm consists of three phases: | |
39 | 1. Marking as necessary all statements known to be necessary, | |
40 | e.g. most function calls, writing a value to memory, etc; | |
41 | 2. Propagating necessary statements, e.g., the statements | |
42 | giving values to operands in necessary statements; and | |
43 | 3. Removing dead statements. */ | |
44 | ||
45 | #include "config.h" | |
46 | #include "system.h" | |
47 | #include "coretypes.h" | |
9ef16211 | 48 | #include "backend.h" |
7c29e30e | 49 | #include "rtl.h" |
4ee9c684 | 50 | #include "tree.h" |
9ef16211 | 51 | #include "gimple.h" |
7c29e30e | 52 | #include "cfghooks.h" |
53 | #include "tree-pass.h" | |
9ef16211 | 54 | #include "ssa.h" |
7c29e30e | 55 | #include "gimple-pretty-print.h" |
b20a8bb4 | 56 | #include "fold-const.h" |
9ed99284 | 57 | #include "calls.h" |
94ea8568 | 58 | #include "cfganal.h" |
bc61cadb | 59 | #include "tree-eh.h" |
a8783bee | 60 | #include "gimplify.h" |
dcf1a1ec | 61 | #include "gimple-iterator.h" |
073c1fd5 | 62 | #include "tree-cfg.h" |
05d9c18a | 63 | #include "tree-ssa-loop-niter.h" |
073c1fd5 | 64 | #include "tree-into-ssa.h" |
65 | #include "tree-dfa.h" | |
78eb8231 | 66 | #include "cfgloop.h" |
a7f4a3ec | 67 | #include "tree-scalar-evolution.h" |
0c93c8a9 | 68 | #include "tree-ssa-propagate.h" |
69 | #include "gimple-fold.h" | |
75a70cf9 | 70 | |
4ee9c684 | 71 | static struct stmt_stats |
72 | { | |
73 | int total; | |
74 | int total_phis; | |
75 | int removed; | |
76 | int removed_phis; | |
77 | } stats; | |
78 | ||
75a70cf9 | 79 | #define STMT_NECESSARY GF_PLF_1 |
80 | ||
42acab1c | 81 | static vec<gimple *> worklist; |
4ee9c684 | 82 | |
83 | /* Vector indicating an SSA name has already been processed and marked | |
84 | as necessary. */ | |
85 | static sbitmap processed; | |
86 | ||
fce11f6d | 87 | /* Vector indicating that the last statement of a basic block has already |
88 | been marked as necessary. */ | |
4ee9c684 | 89 | static sbitmap last_stmt_necessary; |
90 | ||
a336775c | 91 | /* Vector indicating that BB contains statements that are live. */ |
92 | static sbitmap bb_contains_live_stmts; | |
93 | ||
4ee9c684 | 94 | /* Before we can determine whether a control branch is dead, we need to |
95 | compute which blocks are control dependent on which edges. | |
96 | ||
97 | We expect each block to be control dependent on very few edges so we | |
98 | use a bitmap for each block recording its edges. An array holds the | |
99 | bitmap. The Ith bit in the bitmap is set if that block is dependent | |
100 | on the Ith edge. */ | |
7ee4e8e8 | 101 | static control_dependences *cd; |
4ee9c684 | 102 | |
e0e865f0 | 103 | /* Vector indicating that a basic block has already had all the edges |
104 | processed that it is control dependent on. */ | |
b4699230 | 105 | static sbitmap visited_control_parents; |
e0e865f0 | 106 | |
ba8d9702 | 107 | /* TRUE if this pass alters the CFG (by removing control statements). |
108 | FALSE otherwise. | |
109 | ||
110 | If this pass alters the CFG, then it will arrange for the dominators | |
111 | to be recomputed. */ | |
112 | static bool cfg_altered; | |
113 | ||
e98da821 | 114 | /* When non-NULL holds map from basic block index into the postorder. */ |
115 | static int *bb_postorder; | |
116 | ||
17889f9d | 117 | |
4ee9c684 | 118 | /* If STMT is not already marked necessary, mark it, and add it to the |
119 | worklist if ADD_TO_WORKLIST is true. */ | |
fce11f6d | 120 | |
4ee9c684 | 121 | static inline void |
42acab1c | 122 | mark_stmt_necessary (gimple *stmt, bool add_to_worklist) |
4ee9c684 | 123 | { |
8c0963c4 | 124 | gcc_assert (stmt); |
4ee9c684 | 125 | |
75a70cf9 | 126 | if (gimple_plf (stmt, STMT_NECESSARY)) |
4ee9c684 | 127 | return; |
128 | ||
129 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
130 | { | |
131 | fprintf (dump_file, "Marking useful stmt: "); | |
75a70cf9 | 132 | print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); |
4ee9c684 | 133 | fprintf (dump_file, "\n"); |
134 | } | |
135 | ||
75a70cf9 | 136 | gimple_set_plf (stmt, STMT_NECESSARY, true); |
4ee9c684 | 137 | if (add_to_worklist) |
f1f41a6c | 138 | worklist.safe_push (stmt); |
e98da821 | 139 | if (add_to_worklist && bb_contains_live_stmts && !is_gimple_debug (stmt)) |
08b7917c | 140 | bitmap_set_bit (bb_contains_live_stmts, gimple_bb (stmt)->index); |
4ee9c684 | 141 | } |
142 | ||
4fb5e5ca | 143 | |
144 | /* Mark the statement defining operand OP as necessary. */ | |
4ee9c684 | 145 | |
146 | static inline void | |
4fb5e5ca | 147 | mark_operand_necessary (tree op) |
4ee9c684 | 148 | { |
42acab1c | 149 | gimple *stmt; |
4ee9c684 | 150 | int ver; |
151 | ||
8c0963c4 | 152 | gcc_assert (op); |
4ee9c684 | 153 | |
154 | ver = SSA_NAME_VERSION (op); | |
08b7917c | 155 | if (bitmap_bit_p (processed, ver)) |
dd277d48 | 156 | { |
157 | stmt = SSA_NAME_DEF_STMT (op); | |
158 | gcc_assert (gimple_nop_p (stmt) | |
159 | || gimple_plf (stmt, STMT_NECESSARY)); | |
160 | return; | |
161 | } | |
08b7917c | 162 | bitmap_set_bit (processed, ver); |
4ee9c684 | 163 | |
164 | stmt = SSA_NAME_DEF_STMT (op); | |
8c0963c4 | 165 | gcc_assert (stmt); |
4ee9c684 | 166 | |
75a70cf9 | 167 | if (gimple_plf (stmt, STMT_NECESSARY) || gimple_nop_p (stmt)) |
4ee9c684 | 168 | return; |
169 | ||
dd277d48 | 170 | if (dump_file && (dump_flags & TDF_DETAILS)) |
171 | { | |
172 | fprintf (dump_file, "marking necessary through "); | |
1ffa4346 | 173 | print_generic_expr (dump_file, op); |
dd277d48 | 174 | fprintf (dump_file, " stmt "); |
1ffa4346 | 175 | print_gimple_stmt (dump_file, stmt, 0); |
dd277d48 | 176 | } |
177 | ||
75a70cf9 | 178 | gimple_set_plf (stmt, STMT_NECESSARY, true); |
a336775c | 179 | if (bb_contains_live_stmts) |
08b7917c | 180 | bitmap_set_bit (bb_contains_live_stmts, gimple_bb (stmt)->index); |
f1f41a6c | 181 | worklist.safe_push (stmt); |
4ee9c684 | 182 | } |
17889f9d | 183 | |
4ee9c684 | 184 | |
a33d8949 | 185 | /* Mark STMT as necessary if it obviously is. Add it to the worklist if |
4ee9c684 | 186 | it can make other statements necessary. |
187 | ||
188 | If AGGRESSIVE is false, control statements are conservatively marked as | |
189 | necessary. */ | |
190 | ||
191 | static void | |
42acab1c | 192 | mark_stmt_if_obviously_necessary (gimple *stmt, bool aggressive) |
4ee9c684 | 193 | { |
fcb2e1ad | 194 | /* With non-call exceptions, we have to assume that all statements could |
bc0dfc8d | 195 | throw. If a statement could throw, it can be deemed necessary. */ |
196 | if (cfun->can_throw_non_call_exceptions | |
197 | && !cfun->can_delete_dead_exceptions | |
aac19106 | 198 | && stmt_could_throw_p (cfun, stmt)) |
fcb2e1ad | 199 | { |
200 | mark_stmt_necessary (stmt, true); | |
201 | return; | |
202 | } | |
203 | ||
75a70cf9 | 204 | /* Statements that are implicitly live. Most function calls, asm |
205 | and return statements are required. Labels and GIMPLE_BIND nodes | |
206 | are kept because they are control flow, and we have no way of | |
207 | knowing whether they can be removed. DCE can eliminate all the | |
208 | other statements in a block, and CFG can then remove the block | |
209 | and labels. */ | |
210 | switch (gimple_code (stmt)) | |
4ee9c684 | 211 | { |
75a70cf9 | 212 | case GIMPLE_PREDICT: |
213 | case GIMPLE_LABEL: | |
4ee9c684 | 214 | mark_stmt_necessary (stmt, false); |
215 | return; | |
216 | ||
75a70cf9 | 217 | case GIMPLE_ASM: |
218 | case GIMPLE_RESX: | |
219 | case GIMPLE_RETURN: | |
4ee9c684 | 220 | mark_stmt_necessary (stmt, true); |
221 | return; | |
222 | ||
75a70cf9 | 223 | case GIMPLE_CALL: |
a3084c6b | 224 | { |
225 | tree callee = gimple_call_fndecl (stmt); | |
226 | if (callee != NULL_TREE | |
a0e9bfbb | 227 | && fndecl_built_in_p (callee, BUILT_IN_NORMAL)) |
a3084c6b | 228 | switch (DECL_FUNCTION_CODE (callee)) |
229 | { | |
230 | case BUILT_IN_MALLOC: | |
060fc206 | 231 | case BUILT_IN_ALIGNED_ALLOC: |
a3084c6b | 232 | case BUILT_IN_CALLOC: |
2b34677f | 233 | CASE_BUILT_IN_ALLOCA: |
2c98f972 | 234 | case BUILT_IN_STRDUP: |
235 | case BUILT_IN_STRNDUP: | |
a3084c6b | 236 | return; |
cac1a11f | 237 | |
238 | default:; | |
a3084c6b | 239 | } |
240 | /* Most, but not all function calls are required. Function calls that | |
241 | produce no result and have no side effects (i.e. const pure | |
242 | functions) are unnecessary. */ | |
243 | if (gimple_has_side_effects (stmt)) | |
244 | { | |
245 | mark_stmt_necessary (stmt, true); | |
246 | return; | |
247 | } | |
3984c5cd | 248 | /* IFN_GOACC_LOOP calls are necessary in that they are used to |
249 | represent parameter (i.e. step, bound) of a lowered OpenACC | |
250 | partitioned loop. But this kind of partitioned loop might not | |
251 | survive from aggressive loop removal for it has loop exit and | |
252 | is assumed to be finite. Therefore, we need to explicitly mark | |
253 | these calls. (An example is libgomp.oacc-c-c++-common/pr84955.c) */ | |
254 | if (gimple_call_internal_p (stmt, IFN_GOACC_LOOP)) | |
255 | { | |
256 | mark_stmt_necessary (stmt, true); | |
257 | return; | |
258 | } | |
a3084c6b | 259 | if (!gimple_call_lhs (stmt)) |
4ee9c684 | 260 | return; |
a3084c6b | 261 | break; |
262 | } | |
4ee9c684 | 263 | |
9845d120 | 264 | case GIMPLE_DEBUG: |
688ff29b | 265 | /* Debug temps without a value are not useful. ??? If we could |
266 | easily locate the debug temp bind stmt for a use thereof, | |
267 | would could refrain from marking all debug temps here, and | |
268 | mark them only if they're used. */ | |
bce107d7 | 269 | if (gimple_debug_nonbind_marker_p (stmt) |
270 | || !gimple_debug_bind_p (stmt) | |
841424cc | 271 | || gimple_debug_bind_has_value_p (stmt) |
688ff29b | 272 | || TREE_CODE (gimple_debug_bind_get_var (stmt)) != DEBUG_EXPR_DECL) |
273 | mark_stmt_necessary (stmt, false); | |
9845d120 | 274 | return; |
275 | ||
75a70cf9 | 276 | case GIMPLE_GOTO: |
2fa2aa3c | 277 | gcc_assert (!simple_goto_p (stmt)); |
278 | mark_stmt_necessary (stmt, true); | |
4ee9c684 | 279 | return; |
280 | ||
75a70cf9 | 281 | case GIMPLE_COND: |
282 | gcc_assert (EDGE_COUNT (gimple_bb (stmt)->succs) == 2); | |
4ee9c684 | 283 | /* Fall through. */ |
284 | ||
75a70cf9 | 285 | case GIMPLE_SWITCH: |
4ee9c684 | 286 | if (! aggressive) |
287 | mark_stmt_necessary (stmt, true); | |
288 | break; | |
289 | ||
3c25489e | 290 | case GIMPLE_ASSIGN: |
75fa2041 | 291 | if (gimple_clobber_p (stmt)) |
3c25489e | 292 | return; |
293 | break; | |
294 | ||
4ee9c684 | 295 | default: |
296 | break; | |
297 | } | |
298 | ||
2ce91ad7 | 299 | /* If the statement has volatile operands, it needs to be preserved. |
300 | Same for statements that can alter control flow in unpredictable | |
301 | ways. */ | |
75a70cf9 | 302 | if (gimple_has_volatile_ops (stmt) || is_ctrl_altering_stmt (stmt)) |
4ee9c684 | 303 | { |
304 | mark_stmt_necessary (stmt, true); | |
305 | return; | |
306 | } | |
307 | ||
8763c223 | 308 | if (stmt_may_clobber_global_p (stmt)) |
2cf24776 | 309 | { |
5e733b02 | 310 | mark_stmt_necessary (stmt, true); |
311 | return; | |
4ee9c684 | 312 | } |
313 | ||
314 | return; | |
315 | } | |
17889f9d | 316 | |
317 | ||
fce11f6d | 318 | /* Mark the last statement of BB as necessary. */ |
319 | ||
320 | static void | |
321 | mark_last_stmt_necessary (basic_block bb) | |
322 | { | |
42acab1c | 323 | gimple *stmt = last_stmt (bb); |
fce11f6d | 324 | |
08b7917c | 325 | bitmap_set_bit (last_stmt_necessary, bb->index); |
326 | bitmap_set_bit (bb_contains_live_stmts, bb->index); | |
fce11f6d | 327 | |
328 | /* We actually mark the statement only if it is a control statement. */ | |
329 | if (stmt && is_ctrl_stmt (stmt)) | |
330 | mark_stmt_necessary (stmt, true); | |
331 | } | |
332 | ||
333 | ||
334 | /* Mark control dependent edges of BB as necessary. We have to do this only | |
335 | once for each basic block so we set the appropriate bit after we're done. | |
336 | ||
337 | When IGNORE_SELF is true, ignore BB in the list of control dependences. */ | |
9adc5680 | 338 | |
17889f9d | 339 | static void |
7ee4e8e8 | 340 | mark_control_dependent_edges_necessary (basic_block bb, bool ignore_self) |
17889f9d | 341 | { |
342 | bitmap_iterator bi; | |
343 | unsigned edge_number; | |
9adc5680 | 344 | bool skipped = false; |
17889f9d | 345 | |
34154e27 | 346 | gcc_assert (bb != EXIT_BLOCK_PTR_FOR_FN (cfun)); |
17889f9d | 347 | |
34154e27 | 348 | if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)) |
17889f9d | 349 | return; |
350 | ||
7ee4e8e8 | 351 | EXECUTE_IF_SET_IN_BITMAP (cd->get_edges_dependent_on (bb->index), |
352 | 0, edge_number, bi) | |
17889f9d | 353 | { |
ce143ff0 | 354 | basic_block cd_bb = cd->get_edge_src (edge_number); |
17889f9d | 355 | |
9adc5680 | 356 | if (ignore_self && cd_bb == bb) |
357 | { | |
358 | skipped = true; | |
359 | continue; | |
360 | } | |
361 | ||
08b7917c | 362 | if (!bitmap_bit_p (last_stmt_necessary, cd_bb->index)) |
fce11f6d | 363 | mark_last_stmt_necessary (cd_bb); |
17889f9d | 364 | } |
fce11f6d | 365 | |
9adc5680 | 366 | if (!skipped) |
08b7917c | 367 | bitmap_set_bit (visited_control_parents, bb->index); |
17889f9d | 368 | } |
369 | ||
370 | ||
4ee9c684 | 371 | /* Find obviously necessary statements. These are things like most function |
372 | calls, and stores to file level variables. | |
373 | ||
374 | If EL is NULL, control statements are conservatively marked as | |
375 | necessary. Otherwise it contains the list of edges used by control | |
376 | dependence analysis. */ | |
377 | ||
378 | static void | |
7ee4e8e8 | 379 | find_obviously_necessary_stmts (bool aggressive) |
4ee9c684 | 380 | { |
381 | basic_block bb; | |
75a70cf9 | 382 | gimple_stmt_iterator gsi; |
4ee9c684 | 383 | edge e; |
42acab1c | 384 | gimple *phi, *stmt; |
67fa4078 | 385 | int flags; |
4ee9c684 | 386 | |
fc00614f | 387 | FOR_EACH_BB_FN (bb, cfun) |
4ee9c684 | 388 | { |
17889f9d | 389 | /* PHI nodes are never inherently necessary. */ |
75a70cf9 | 390 | for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) |
391 | { | |
392 | phi = gsi_stmt (gsi); | |
393 | gimple_set_plf (phi, STMT_NECESSARY, false); | |
394 | } | |
4ee9c684 | 395 | |
396 | /* Check all statements in the block. */ | |
75a70cf9 | 397 | for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) |
4ee9c684 | 398 | { |
75a70cf9 | 399 | stmt = gsi_stmt (gsi); |
400 | gimple_set_plf (stmt, STMT_NECESSARY, false); | |
7ee4e8e8 | 401 | mark_stmt_if_obviously_necessary (stmt, aggressive); |
4ee9c684 | 402 | } |
4ee9c684 | 403 | } |
404 | ||
b1887855 | 405 | /* Pure and const functions are finite and thus have no infinite loops in |
406 | them. */ | |
67fa4078 | 407 | flags = flags_from_decl_or_type (current_function_decl); |
408 | if ((flags & (ECF_CONST|ECF_PURE)) && !(flags & ECF_LOOPING_CONST_OR_PURE)) | |
b1887855 | 409 | return; |
410 | ||
411 | /* Prevent the empty possibly infinite loops from being removed. */ | |
7ee4e8e8 | 412 | if (aggressive) |
4ee9c684 | 413 | { |
b1887855 | 414 | struct loop *loop; |
b1887855 | 415 | if (mark_irreducible_loops ()) |
fc00614f | 416 | FOR_EACH_BB_FN (bb, cfun) |
b1887855 | 417 | { |
418 | edge_iterator ei; | |
419 | FOR_EACH_EDGE (e, ei, bb->succs) | |
420 | if ((e->flags & EDGE_DFS_BACK) | |
421 | && (e->flags & EDGE_IRREDUCIBLE_LOOP)) | |
422 | { | |
423 | if (dump_file) | |
424 | fprintf (dump_file, "Marking back edge of irreducible loop %i->%i\n", | |
425 | e->src->index, e->dest->index); | |
7ee4e8e8 | 426 | mark_control_dependent_edges_necessary (e->dest, false); |
b1887855 | 427 | } |
428 | } | |
429 | ||
f21d4d00 | 430 | FOR_EACH_LOOP (loop, 0) |
b1887855 | 431 | if (!finite_loop_p (loop)) |
432 | { | |
433 | if (dump_file) | |
f4d3c071 | 434 | fprintf (dump_file, "cannot prove finiteness of loop %i\n", loop->num); |
7ee4e8e8 | 435 | mark_control_dependent_edges_necessary (loop->latch, false); |
b1887855 | 436 | } |
4ee9c684 | 437 | } |
438 | } | |
4ee9c684 | 439 | |
4ee9c684 | 440 | |
dd277d48 | 441 | /* Return true if REF is based on an aliased base, otherwise false. */ |
442 | ||
443 | static bool | |
444 | ref_may_be_aliased (tree ref) | |
445 | { | |
dfc8fda4 | 446 | gcc_assert (TREE_CODE (ref) != WITH_SIZE_EXPR); |
dd277d48 | 447 | while (handled_component_p (ref)) |
448 | ref = TREE_OPERAND (ref, 0); | |
182cf5a9 | 449 | if (TREE_CODE (ref) == MEM_REF |
450 | && TREE_CODE (TREE_OPERAND (ref, 0)) == ADDR_EXPR) | |
451 | ref = TREE_OPERAND (TREE_OPERAND (ref, 0), 0); | |
dd277d48 | 452 | return !(DECL_P (ref) |
453 | && !may_be_aliased (ref)); | |
454 | } | |
455 | ||
dd277d48 | 456 | static bitmap visited = NULL; |
457 | static unsigned int longest_chain = 0; | |
458 | static unsigned int total_chain = 0; | |
7729444a | 459 | static unsigned int nr_walks = 0; |
dd277d48 | 460 | static bool chain_ovfl = false; |
461 | ||
462 | /* Worker for the walker that marks reaching definitions of REF, | |
463 | which is based on a non-aliased decl, necessary. It returns | |
464 | true whenever the defining statement of the current VDEF is | |
465 | a kill for REF, as no dominating may-defs are necessary for REF | |
bd2f8bb1 | 466 | anymore. DATA points to the basic-block that contains the |
467 | stmt that refers to REF. */ | |
dd277d48 | 468 | |
469 | static bool | |
bd2f8bb1 | 470 | mark_aliased_reaching_defs_necessary_1 (ao_ref *ref, tree vdef, void *data) |
dd277d48 | 471 | { |
42acab1c | 472 | gimple *def_stmt = SSA_NAME_DEF_STMT (vdef); |
dd277d48 | 473 | |
474 | /* All stmts we visit are necessary. */ | |
b622ec25 | 475 | if (! gimple_clobber_p (def_stmt)) |
476 | mark_operand_necessary (vdef); | |
dd277d48 | 477 | |
478 | /* If the stmt lhs kills ref, then we can stop walking. */ | |
479 | if (gimple_has_lhs (def_stmt) | |
e54d36c4 | 480 | && TREE_CODE (gimple_get_lhs (def_stmt)) != SSA_NAME |
481 | /* The assignment is not necessarily carried out if it can throw | |
482 | and we can catch it in the current function where we could inspect | |
483 | the previous value. | |
484 | ??? We only need to care about the RHS throwing. For aggregate | |
485 | assignments or similar calls and non-call exceptions the LHS | |
486 | might throw as well. */ | |
aac19106 | 487 | && !stmt_can_throw_internal (cfun, def_stmt)) |
dd277d48 | 488 | { |
489 | tree base, lhs = gimple_get_lhs (def_stmt); | |
f3c2a387 | 490 | poly_int64 size, offset, max_size; |
292237f3 | 491 | bool reverse; |
1daead67 | 492 | ao_ref_base (ref); |
292237f3 | 493 | base |
494 | = get_ref_base_and_extent (lhs, &offset, &size, &max_size, &reverse); | |
dd277d48 | 495 | /* We can get MEM[symbol: sZ, index: D.8862_1] here, |
496 | so base == refd->base does not always hold. */ | |
1daead67 | 497 | if (base == ref->base) |
dd277d48 | 498 | { |
499 | /* For a must-alias check we need to be able to constrain | |
500 | the accesses properly. */ | |
f3c2a387 | 501 | if (known_eq (size, max_size) |
fe60c82c | 502 | && known_subrange_p (ref->offset, ref->max_size, offset, size)) |
503 | return true; | |
dd277d48 | 504 | /* Or they need to be exactly the same. */ |
1daead67 | 505 | else if (ref->ref |
bd2f8bb1 | 506 | /* Make sure there is no induction variable involved |
507 | in the references (gcc.c-torture/execute/pr42142.c). | |
508 | The simplest way is to check if the kill dominates | |
509 | the use. */ | |
a1d4a509 | 510 | /* But when both are in the same block we cannot |
511 | easily tell whether we came from a backedge | |
512 | unless we decide to compute stmt UIDs | |
513 | (see PR58246). */ | |
514 | && (basic_block) data != gimple_bb (def_stmt) | |
bd2f8bb1 | 515 | && dominated_by_p (CDI_DOMINATORS, (basic_block) data, |
516 | gimple_bb (def_stmt)) | |
1daead67 | 517 | && operand_equal_p (ref->ref, lhs, 0)) |
dd277d48 | 518 | return true; |
519 | } | |
520 | } | |
521 | ||
522 | /* Otherwise keep walking. */ | |
523 | return false; | |
524 | } | |
525 | ||
526 | static void | |
42acab1c | 527 | mark_aliased_reaching_defs_necessary (gimple *stmt, tree ref) |
dd277d48 | 528 | { |
dd277d48 | 529 | unsigned int chain; |
1daead67 | 530 | ao_ref refd; |
dd277d48 | 531 | gcc_assert (!chain_ovfl); |
1daead67 | 532 | ao_ref_init (&refd, ref); |
533 | chain = walk_aliased_vdefs (&refd, gimple_vuse (stmt), | |
dd277d48 | 534 | mark_aliased_reaching_defs_necessary_1, |
bd2f8bb1 | 535 | gimple_bb (stmt), NULL); |
dd277d48 | 536 | if (chain > longest_chain) |
537 | longest_chain = chain; | |
538 | total_chain += chain; | |
7729444a | 539 | nr_walks++; |
dd277d48 | 540 | } |
541 | ||
542 | /* Worker for the walker that marks reaching definitions of REF, which | |
543 | is not based on a non-aliased decl. For simplicity we need to end | |
544 | up marking all may-defs necessary that are not based on a non-aliased | |
545 | decl. The only job of this walker is to skip may-defs based on | |
546 | a non-aliased decl. */ | |
547 | ||
548 | static bool | |
1daead67 | 549 | mark_all_reaching_defs_necessary_1 (ao_ref *ref ATTRIBUTE_UNUSED, |
550 | tree vdef, void *data ATTRIBUTE_UNUSED) | |
dd277d48 | 551 | { |
42acab1c | 552 | gimple *def_stmt = SSA_NAME_DEF_STMT (vdef); |
dd277d48 | 553 | |
554 | /* We have to skip already visited (and thus necessary) statements | |
555 | to make the chaining work after we dropped back to simple mode. */ | |
556 | if (chain_ovfl | |
08b7917c | 557 | && bitmap_bit_p (processed, SSA_NAME_VERSION (vdef))) |
dd277d48 | 558 | { |
559 | gcc_assert (gimple_nop_p (def_stmt) | |
560 | || gimple_plf (def_stmt, STMT_NECESSARY)); | |
561 | return false; | |
562 | } | |
563 | ||
564 | /* We want to skip stores to non-aliased variables. */ | |
565 | if (!chain_ovfl | |
566 | && gimple_assign_single_p (def_stmt)) | |
567 | { | |
568 | tree lhs = gimple_assign_lhs (def_stmt); | |
569 | if (!ref_may_be_aliased (lhs)) | |
570 | return false; | |
571 | } | |
572 | ||
cac1a11f | 573 | /* We want to skip statments that do not constitute stores but have |
574 | a virtual definition. */ | |
575 | if (is_gimple_call (def_stmt)) | |
576 | { | |
577 | tree callee = gimple_call_fndecl (def_stmt); | |
578 | if (callee != NULL_TREE | |
a0e9bfbb | 579 | && fndecl_built_in_p (callee, BUILT_IN_NORMAL)) |
cac1a11f | 580 | switch (DECL_FUNCTION_CODE (callee)) |
581 | { | |
582 | case BUILT_IN_MALLOC: | |
060fc206 | 583 | case BUILT_IN_ALIGNED_ALLOC: |
cac1a11f | 584 | case BUILT_IN_CALLOC: |
2b34677f | 585 | CASE_BUILT_IN_ALLOCA: |
cac1a11f | 586 | case BUILT_IN_FREE: |
587 | return false; | |
588 | ||
589 | default:; | |
590 | } | |
591 | } | |
592 | ||
b622ec25 | 593 | if (! gimple_clobber_p (def_stmt)) |
594 | mark_operand_necessary (vdef); | |
4bb5d312 | 595 | |
596 | return false; | |
dd277d48 | 597 | } |
598 | ||
599 | static void | |
42acab1c | 600 | mark_all_reaching_defs_necessary (gimple *stmt) |
dd277d48 | 601 | { |
602 | walk_aliased_vdefs (NULL, gimple_vuse (stmt), | |
603 | mark_all_reaching_defs_necessary_1, NULL, &visited); | |
604 | } | |
605 | ||
b1887855 | 606 | /* Return true for PHI nodes with one or identical arguments |
607 | can be removed. */ | |
608 | static bool | |
42acab1c | 609 | degenerate_phi_p (gimple *phi) |
b1887855 | 610 | { |
611 | unsigned int i; | |
612 | tree op = gimple_phi_arg_def (phi, 0); | |
613 | for (i = 1; i < gimple_phi_num_args (phi); i++) | |
614 | if (gimple_phi_arg_def (phi, i) != op) | |
615 | return false; | |
616 | return true; | |
617 | } | |
618 | ||
17889f9d | 619 | /* Propagate necessity using the operands of necessary statements. |
620 | Process the uses on each statement in the worklist, and add all | |
621 | feeding statements which contribute to the calculation of this | |
48e1416a | 622 | value to the worklist. |
4ee9c684 | 623 | |
624 | In conservative mode, EL is NULL. */ | |
625 | ||
626 | static void | |
7ee4e8e8 | 627 | propagate_necessity (bool aggressive) |
4ee9c684 | 628 | { |
42acab1c | 629 | gimple *stmt; |
4ee9c684 | 630 | |
631 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
632 | fprintf (dump_file, "\nProcessing worklist:\n"); | |
633 | ||
f1f41a6c | 634 | while (worklist.length () > 0) |
4ee9c684 | 635 | { |
17889f9d | 636 | /* Take STMT from worklist. */ |
f1f41a6c | 637 | stmt = worklist.pop (); |
4ee9c684 | 638 | |
639 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
640 | { | |
641 | fprintf (dump_file, "processing: "); | |
75a70cf9 | 642 | print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); |
4ee9c684 | 643 | fprintf (dump_file, "\n"); |
644 | } | |
645 | ||
646 | if (aggressive) | |
647 | { | |
fce11f6d | 648 | /* Mark the last statement of the basic blocks on which the block |
649 | containing STMT is control dependent, but only if we haven't | |
4ee9c684 | 650 | already done so. */ |
75a70cf9 | 651 | basic_block bb = gimple_bb (stmt); |
34154e27 | 652 | if (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) |
08b7917c | 653 | && !bitmap_bit_p (visited_control_parents, bb->index)) |
7ee4e8e8 | 654 | mark_control_dependent_edges_necessary (bb, false); |
4ee9c684 | 655 | } |
656 | ||
dd277d48 | 657 | if (gimple_code (stmt) == GIMPLE_PHI |
658 | /* We do not process virtual PHI nodes nor do we track their | |
659 | necessity. */ | |
7c782c9b | 660 | && !virtual_operand_p (gimple_phi_result (stmt))) |
4ee9c684 | 661 | { |
662 | /* PHI nodes are somewhat special in that each PHI alternative has | |
663 | data and control dependencies. All the statements feeding the | |
664 | PHI node's arguments are always necessary. In aggressive mode, | |
665 | we also consider the control dependent edges leading to the | |
666 | predecessor block associated with each PHI alternative as | |
667 | necessary. */ | |
1a91d914 | 668 | gphi *phi = as_a <gphi *> (stmt); |
75a70cf9 | 669 | size_t k; |
17889f9d | 670 | |
75a70cf9 | 671 | for (k = 0; k < gimple_phi_num_args (stmt); k++) |
4ee9c684 | 672 | { |
17889f9d | 673 | tree arg = PHI_ARG_DEF (stmt, k); |
4ee9c684 | 674 | if (TREE_CODE (arg) == SSA_NAME) |
4fb5e5ca | 675 | mark_operand_necessary (arg); |
4ee9c684 | 676 | } |
677 | ||
9adc5680 | 678 | /* For PHI operands it matters from where the control flow arrives |
679 | to the BB. Consider the following example: | |
680 | ||
681 | a=exp1; | |
682 | b=exp2; | |
683 | if (test) | |
684 | ; | |
685 | else | |
686 | ; | |
687 | c=PHI(a,b) | |
688 | ||
689 | We need to mark control dependence of the empty basic blocks, since they | |
690 | contains computation of PHI operands. | |
691 | ||
692 | Doing so is too restrictive in the case the predecestor block is in | |
693 | the loop. Consider: | |
694 | ||
695 | if (b) | |
696 | { | |
697 | int i; | |
698 | for (i = 0; i<1000; ++i) | |
699 | ; | |
700 | j = 0; | |
701 | } | |
702 | return j; | |
703 | ||
704 | There is PHI for J in the BB containing return statement. | |
705 | In this case the control dependence of predecestor block (that is | |
706 | within the empty loop) also contains the block determining number | |
707 | of iterations of the block that would prevent removing of empty | |
708 | loop in this case. | |
709 | ||
710 | This scenario can be avoided by splitting critical edges. | |
711 | To save the critical edge splitting pass we identify how the control | |
712 | dependence would look like if the edge was split. | |
713 | ||
714 | Consider the modified CFG created from current CFG by splitting | |
715 | edge B->C. In the postdominance tree of modified CFG, C' is | |
716 | always child of C. There are two cases how chlids of C' can look | |
717 | like: | |
718 | ||
719 | 1) C' is leaf | |
720 | ||
721 | In this case the only basic block C' is control dependent on is B. | |
722 | ||
723 | 2) C' has single child that is B | |
724 | ||
725 | In this case control dependence of C' is same as control | |
726 | dependence of B in original CFG except for block B itself. | |
727 | (since C' postdominate B in modified CFG) | |
728 | ||
729 | Now how to decide what case happens? There are two basic options: | |
730 | ||
731 | a) C postdominate B. Then C immediately postdominate B and | |
732 | case 2 happens iff there is no other way from B to C except | |
733 | the edge B->C. | |
734 | ||
735 | There is other way from B to C iff there is succesor of B that | |
736 | is not postdominated by B. Testing this condition is somewhat | |
737 | expensive, because we need to iterate all succesors of B. | |
738 | We are safe to assume that this does not happen: we will mark B | |
739 | as needed when processing the other path from B to C that is | |
740 | conrol dependent on B and marking control dependencies of B | |
741 | itself is harmless because they will be processed anyway after | |
742 | processing control statement in B. | |
743 | ||
744 | b) C does not postdominate B. Always case 1 happens since there is | |
745 | path from C to exit that does not go through B and thus also C'. */ | |
746 | ||
b1887855 | 747 | if (aggressive && !degenerate_phi_p (stmt)) |
4ee9c684 | 748 | { |
75a70cf9 | 749 | for (k = 0; k < gimple_phi_num_args (stmt); k++) |
4ee9c684 | 750 | { |
1a91d914 | 751 | basic_block arg_bb = gimple_phi_arg_edge (phi, k)->src; |
9adc5680 | 752 | |
753 | if (gimple_bb (stmt) | |
754 | != get_immediate_dominator (CDI_POST_DOMINATORS, arg_bb)) | |
4ee9c684 | 755 | { |
08b7917c | 756 | if (!bitmap_bit_p (last_stmt_necessary, arg_bb->index)) |
fce11f6d | 757 | mark_last_stmt_necessary (arg_bb); |
4ee9c684 | 758 | } |
34154e27 | 759 | else if (arg_bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) |
08b7917c | 760 | && !bitmap_bit_p (visited_control_parents, |
fce11f6d | 761 | arg_bb->index)) |
7ee4e8e8 | 762 | mark_control_dependent_edges_necessary (arg_bb, true); |
4ee9c684 | 763 | } |
764 | } | |
765 | } | |
766 | else | |
767 | { | |
768 | /* Propagate through the operands. Examine all the USE, VUSE and | |
48e1416a | 769 | VDEF operands in this statement. Mark all the statements |
dd277d48 | 770 | which feed this statement's uses as necessary. */ |
4fb5e5ca | 771 | ssa_op_iter iter; |
772 | tree use; | |
43daa21e | 773 | |
cac1a11f | 774 | /* If this is a call to free which is directly fed by an |
775 | allocation function do not mark that necessary through | |
776 | processing the argument. */ | |
777 | if (gimple_call_builtin_p (stmt, BUILT_IN_FREE)) | |
778 | { | |
779 | tree ptr = gimple_call_arg (stmt, 0); | |
42acab1c | 780 | gimple *def_stmt; |
cac1a11f | 781 | tree def_callee; |
782 | /* If the pointer we free is defined by an allocation | |
783 | function do not add the call to the worklist. */ | |
784 | if (TREE_CODE (ptr) == SSA_NAME | |
785 | && is_gimple_call (def_stmt = SSA_NAME_DEF_STMT (ptr)) | |
786 | && (def_callee = gimple_call_fndecl (def_stmt)) | |
787 | && DECL_BUILT_IN_CLASS (def_callee) == BUILT_IN_NORMAL | |
060fc206 | 788 | && (DECL_FUNCTION_CODE (def_callee) == BUILT_IN_ALIGNED_ALLOC |
789 | || DECL_FUNCTION_CODE (def_callee) == BUILT_IN_MALLOC | |
da5cb894 | 790 | || DECL_FUNCTION_CODE (def_callee) == BUILT_IN_CALLOC)) |
1e42d5c6 | 791 | continue; |
cac1a11f | 792 | } |
793 | ||
dd277d48 | 794 | FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) |
4fb5e5ca | 795 | mark_operand_necessary (use); |
dd277d48 | 796 | |
797 | use = gimple_vuse (stmt); | |
798 | if (!use) | |
799 | continue; | |
800 | ||
801 | /* If we dropped to simple mode make all immediately | |
802 | reachable definitions necessary. */ | |
803 | if (chain_ovfl) | |
804 | { | |
805 | mark_all_reaching_defs_necessary (stmt); | |
806 | continue; | |
807 | } | |
808 | ||
809 | /* For statements that may load from memory (have a VUSE) we | |
810 | have to mark all reaching (may-)definitions as necessary. | |
811 | We partition this task into two cases: | |
812 | 1) explicit loads based on decls that are not aliased | |
813 | 2) implicit loads (like calls) and explicit loads not | |
814 | based on decls that are not aliased (like indirect | |
815 | references or loads from globals) | |
816 | For 1) we mark all reaching may-defs as necessary, stopping | |
817 | at dominating kills. For 2) we want to mark all dominating | |
818 | references necessary, but non-aliased ones which we handle | |
4bb5d312 | 819 | in 1). By keeping a global visited bitmap for references |
820 | we walk for 2) we avoid quadratic behavior for those. */ | |
dd277d48 | 821 | |
822 | if (is_gimple_call (stmt)) | |
823 | { | |
9df58cd1 | 824 | tree callee = gimple_call_fndecl (stmt); |
dd277d48 | 825 | unsigned i; |
826 | ||
9df58cd1 | 827 | /* Calls to functions that are merely acting as barriers |
828 | or that only store to memory do not make any previous | |
829 | stores necessary. */ | |
830 | if (callee != NULL_TREE | |
831 | && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL | |
832 | && (DECL_FUNCTION_CODE (callee) == BUILT_IN_MEMSET | |
939514e9 | 833 | || DECL_FUNCTION_CODE (callee) == BUILT_IN_MEMSET_CHK |
9df58cd1 | 834 | || DECL_FUNCTION_CODE (callee) == BUILT_IN_MALLOC |
060fc206 | 835 | || DECL_FUNCTION_CODE (callee) == BUILT_IN_ALIGNED_ALLOC |
939514e9 | 836 | || DECL_FUNCTION_CODE (callee) == BUILT_IN_CALLOC |
ca793672 | 837 | || DECL_FUNCTION_CODE (callee) == BUILT_IN_FREE |
9d17b4a8 | 838 | || DECL_FUNCTION_CODE (callee) == BUILT_IN_VA_END |
2b34677f | 839 | || ALLOCA_FUNCTION_CODE_P (DECL_FUNCTION_CODE (callee)) |
ca793672 | 840 | || DECL_FUNCTION_CODE (callee) == BUILT_IN_STACK_SAVE |
fca0886c | 841 | || DECL_FUNCTION_CODE (callee) == BUILT_IN_STACK_RESTORE |
842 | || DECL_FUNCTION_CODE (callee) == BUILT_IN_ASSUME_ALIGNED)) | |
9df58cd1 | 843 | continue; |
844 | ||
dd277d48 | 845 | /* Calls implicitly load from memory, their arguments |
4bb5d312 | 846 | in addition may explicitly perform memory loads. */ |
dd277d48 | 847 | mark_all_reaching_defs_necessary (stmt); |
848 | for (i = 0; i < gimple_call_num_args (stmt); ++i) | |
849 | { | |
850 | tree arg = gimple_call_arg (stmt, i); | |
851 | if (TREE_CODE (arg) == SSA_NAME | |
852 | || is_gimple_min_invariant (arg)) | |
853 | continue; | |
dfc8fda4 | 854 | if (TREE_CODE (arg) == WITH_SIZE_EXPR) |
855 | arg = TREE_OPERAND (arg, 0); | |
dd277d48 | 856 | if (!ref_may_be_aliased (arg)) |
857 | mark_aliased_reaching_defs_necessary (stmt, arg); | |
858 | } | |
859 | } | |
860 | else if (gimple_assign_single_p (stmt)) | |
861 | { | |
4bb5d312 | 862 | tree rhs; |
dd277d48 | 863 | /* If this is a load mark things necessary. */ |
864 | rhs = gimple_assign_rhs1 (stmt); | |
865 | if (TREE_CODE (rhs) != SSA_NAME | |
3c25489e | 866 | && !is_gimple_min_invariant (rhs) |
867 | && TREE_CODE (rhs) != CONSTRUCTOR) | |
dd277d48 | 868 | { |
869 | if (!ref_may_be_aliased (rhs)) | |
870 | mark_aliased_reaching_defs_necessary (stmt, rhs); | |
871 | else | |
3c25489e | 872 | mark_all_reaching_defs_necessary (stmt); |
dd277d48 | 873 | } |
dd277d48 | 874 | } |
1a91d914 | 875 | else if (greturn *return_stmt = dyn_cast <greturn *> (stmt)) |
dd277d48 | 876 | { |
1a91d914 | 877 | tree rhs = gimple_return_retval (return_stmt); |
dd277d48 | 878 | /* A return statement may perform a load. */ |
2109076a | 879 | if (rhs |
880 | && TREE_CODE (rhs) != SSA_NAME | |
3c25489e | 881 | && !is_gimple_min_invariant (rhs) |
882 | && TREE_CODE (rhs) != CONSTRUCTOR) | |
dd277d48 | 883 | { |
884 | if (!ref_may_be_aliased (rhs)) | |
885 | mark_aliased_reaching_defs_necessary (stmt, rhs); | |
886 | else | |
887 | mark_all_reaching_defs_necessary (stmt); | |
888 | } | |
889 | } | |
1a91d914 | 890 | else if (gasm *asm_stmt = dyn_cast <gasm *> (stmt)) |
dd277d48 | 891 | { |
892 | unsigned i; | |
893 | mark_all_reaching_defs_necessary (stmt); | |
894 | /* Inputs may perform loads. */ | |
1a91d914 | 895 | for (i = 0; i < gimple_asm_ninputs (asm_stmt); ++i) |
dd277d48 | 896 | { |
1a91d914 | 897 | tree op = TREE_VALUE (gimple_asm_input_op (asm_stmt, i)); |
dd277d48 | 898 | if (TREE_CODE (op) != SSA_NAME |
899 | && !is_gimple_min_invariant (op) | |
3c25489e | 900 | && TREE_CODE (op) != CONSTRUCTOR |
dd277d48 | 901 | && !ref_may_be_aliased (op)) |
902 | mark_aliased_reaching_defs_necessary (stmt, op); | |
903 | } | |
904 | } | |
b65fbe25 | 905 | else if (gimple_code (stmt) == GIMPLE_TRANSACTION) |
906 | { | |
907 | /* The beginning of a transaction is a memory barrier. */ | |
908 | /* ??? If we were really cool, we'd only be a barrier | |
909 | for the memories touched within the transaction. */ | |
910 | mark_all_reaching_defs_necessary (stmt); | |
911 | } | |
dd277d48 | 912 | else |
913 | gcc_unreachable (); | |
914 | ||
915 | /* If we over-used our alias oracle budget drop to simple | |
7729444a | 916 | mode. The cost metric allows quadratic behavior |
917 | (number of uses times number of may-defs queries) up to | |
918 | a constant maximal number of queries and after that falls back to | |
dd277d48 | 919 | super-linear complexity. */ |
7729444a | 920 | if (/* Constant but quadratic for small functions. */ |
921 | total_chain > 128 * 128 | |
922 | /* Linear in the number of may-defs. */ | |
923 | && total_chain > 32 * longest_chain | |
924 | /* Linear in the number of uses. */ | |
925 | && total_chain > nr_walks * 32) | |
dd277d48 | 926 | { |
927 | chain_ovfl = true; | |
928 | if (visited) | |
929 | bitmap_clear (visited); | |
930 | } | |
4ee9c684 | 931 | } |
932 | } | |
933 | } | |
1bd13ef1 | 934 | |
4ee9c684 | 935 | /* Remove dead PHI nodes from block BB. */ |
936 | ||
a6b3b25c | 937 | static bool |
4ee9c684 | 938 | remove_dead_phis (basic_block bb) |
939 | { | |
a6b3b25c | 940 | bool something_changed = false; |
1a91d914 | 941 | gphi *phi; |
942 | gphi_iterator gsi; | |
4ee9c684 | 943 | |
e3a19533 | 944 | for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);) |
4ee9c684 | 945 | { |
946 | stats.total_phis++; | |
1a91d914 | 947 | phi = gsi.phi (); |
4ee9c684 | 948 | |
dd277d48 | 949 | /* We do not track necessity of virtual PHI nodes. Instead do |
950 | very simple dead PHI removal here. */ | |
7c782c9b | 951 | if (virtual_operand_p (gimple_phi_result (phi))) |
dd277d48 | 952 | { |
dd277d48 | 953 | /* Virtual PHI nodes with one or identical arguments |
954 | can be removed. */ | |
b1887855 | 955 | if (degenerate_phi_p (phi)) |
dd277d48 | 956 | { |
957 | tree vdef = gimple_phi_result (phi); | |
b1887855 | 958 | tree vuse = gimple_phi_arg_def (phi, 0); |
959 | ||
dd277d48 | 960 | use_operand_p use_p; |
961 | imm_use_iterator iter; | |
42acab1c | 962 | gimple *use_stmt; |
dd277d48 | 963 | FOR_EACH_IMM_USE_STMT (use_stmt, iter, vdef) |
964 | FOR_EACH_IMM_USE_ON_STMT (use_p, iter) | |
965 | SET_USE (use_p, vuse); | |
c5269667 | 966 | if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vdef) |
967 | && TREE_CODE (vuse) == SSA_NAME) | |
dd277d48 | 968 | SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vuse) = 1; |
969 | } | |
970 | else | |
971 | gimple_set_plf (phi, STMT_NECESSARY, true); | |
972 | } | |
973 | ||
75a70cf9 | 974 | if (!gimple_plf (phi, STMT_NECESSARY)) |
4ee9c684 | 975 | { |
a6b3b25c | 976 | something_changed = true; |
4ee9c684 | 977 | if (dump_file && (dump_flags & TDF_DETAILS)) |
978 | { | |
979 | fprintf (dump_file, "Deleting : "); | |
75a70cf9 | 980 | print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); |
4ee9c684 | 981 | fprintf (dump_file, "\n"); |
982 | } | |
983 | ||
75a70cf9 | 984 | remove_phi_node (&gsi, true); |
4ee9c684 | 985 | stats.removed_phis++; |
dd277d48 | 986 | continue; |
4ee9c684 | 987 | } |
dd277d48 | 988 | |
989 | gsi_next (&gsi); | |
4ee9c684 | 990 | } |
a6b3b25c | 991 | return something_changed; |
4ee9c684 | 992 | } |
17889f9d | 993 | |
994 | ||
5206b159 | 995 | /* Remove dead statement pointed to by iterator I. Receives the basic block BB |
4ee9c684 | 996 | containing I so that we don't have to look it up. */ |
997 | ||
998 | static void | |
4a5df39c | 999 | remove_dead_stmt (gimple_stmt_iterator *i, basic_block bb, |
1000 | vec<edge> &to_remove_edges) | |
4ee9c684 | 1001 | { |
42acab1c | 1002 | gimple *stmt = gsi_stmt (*i); |
4ee9c684 | 1003 | |
1004 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1005 | { | |
1006 | fprintf (dump_file, "Deleting : "); | |
75a70cf9 | 1007 | print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); |
4ee9c684 | 1008 | fprintf (dump_file, "\n"); |
1009 | } | |
1010 | ||
1011 | stats.removed++; | |
1012 | ||
1013 | /* If we have determined that a conditional branch statement contributes | |
e98da821 | 1014 | nothing to the program, then we not only remove it, but we need to update |
1015 | the CFG. We can chose any of edges out of BB as long as we are sure to not | |
1016 | close infinite loops. This is done by always choosing the edge closer to | |
1017 | exit in inverted_post_order_compute order. */ | |
75a70cf9 | 1018 | if (is_ctrl_stmt (stmt)) |
4ee9c684 | 1019 | { |
a336775c | 1020 | edge_iterator ei; |
e98da821 | 1021 | edge e = NULL, e2; |
1022 | ||
1023 | /* See if there is only one non-abnormal edge. */ | |
1024 | if (single_succ_p (bb)) | |
1025 | e = single_succ_edge (bb); | |
1026 | /* Otherwise chose one that is closer to bb with live statement in it. | |
1027 | To be able to chose one, we compute inverted post order starting from | |
1028 | all BBs with live statements. */ | |
1029 | if (!e) | |
1030 | { | |
1031 | if (!bb_postorder) | |
1032 | { | |
a4421e7b | 1033 | auto_vec<int, 20> postorder; |
1034 | inverted_post_order_compute (&postorder, | |
1035 | &bb_contains_live_stmts); | |
e98da821 | 1036 | bb_postorder = XNEWVEC (int, last_basic_block_for_fn (cfun)); |
a4421e7b | 1037 | for (unsigned int i = 0; i < postorder.length (); ++i) |
e98da821 | 1038 | bb_postorder[postorder[i]] = i; |
e98da821 | 1039 | } |
1040 | FOR_EACH_EDGE (e2, ei, bb->succs) | |
1041 | if (!e || e2->dest == EXIT_BLOCK_PTR_FOR_FN (cfun) | |
1042 | || bb_postorder [e->dest->index] | |
1043 | < bb_postorder [e2->dest->index]) | |
1044 | e = e2; | |
1045 | } | |
a336775c | 1046 | gcc_assert (e); |
720cfc43 | 1047 | e->probability = profile_probability::always (); |
4ee9c684 | 1048 | |
1049 | /* The edge is no longer associated with a conditional, so it does | |
e98da821 | 1050 | not have TRUE/FALSE flags. |
1051 | We are also safe to drop EH/ABNORMAL flags and turn them into | |
1052 | normal control flow, because we know that all the destinations (including | |
1053 | those odd edges) are equivalent for program execution. */ | |
1054 | e->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE | EDGE_EH | EDGE_ABNORMAL); | |
4ee9c684 | 1055 | |
39cdc6b4 | 1056 | /* The lone outgoing edge from BB will be a fallthru edge. */ |
a336775c | 1057 | e->flags |= EDGE_FALLTHRU; |
1058 | ||
1059 | /* Remove the remaining outgoing edges. */ | |
4a5df39c | 1060 | FOR_EACH_EDGE (e2, ei, bb->succs) |
a336775c | 1061 | if (e != e2) |
1062 | { | |
f91b083b | 1063 | /* If we made a BB unconditionally exit a loop or removed |
1064 | an entry into an irreducible region, then this transform | |
1065 | alters the set of BBs in the loop. Schedule a fixup. */ | |
1066 | if (loop_exit_edge_p (bb->loop_father, e) | |
1067 | || (e2->dest->flags & BB_IRREDUCIBLE_LOOP)) | |
c1d1f6d2 | 1068 | loops_state_set (LOOPS_NEED_FIXUP); |
4a5df39c | 1069 | to_remove_edges.safe_push (e2); |
a336775c | 1070 | } |
9bae88bc | 1071 | } |
1072 | ||
1073 | /* If this is a store into a variable that is being optimized away, | |
1074 | add a debug bind stmt if possible. */ | |
c64f38bf | 1075 | if (MAY_HAVE_DEBUG_BIND_STMTS |
9bae88bc | 1076 | && gimple_assign_single_p (stmt) |
1077 | && is_gimple_val (gimple_assign_rhs1 (stmt))) | |
1078 | { | |
1079 | tree lhs = gimple_assign_lhs (stmt); | |
53e9c5c4 | 1080 | if ((VAR_P (lhs) || TREE_CODE (lhs) == PARM_DECL) |
9bae88bc | 1081 | && !DECL_IGNORED_P (lhs) |
1082 | && is_gimple_reg_type (TREE_TYPE (lhs)) | |
1083 | && !is_global_var (lhs) | |
1084 | && !DECL_HAS_VALUE_EXPR_P (lhs)) | |
1085 | { | |
1086 | tree rhs = gimple_assign_rhs1 (stmt); | |
1a91d914 | 1087 | gdebug *note |
9bae88bc | 1088 | = gimple_build_debug_bind (lhs, unshare_expr (rhs), stmt); |
1089 | gsi_insert_after (i, note, GSI_SAME_STMT); | |
1090 | } | |
4ee9c684 | 1091 | } |
dd277d48 | 1092 | |
1093 | unlink_stmt_vdef (stmt); | |
48e1416a | 1094 | gsi_remove (i, true); |
1095 | release_defs (stmt); | |
4ee9c684 | 1096 | } |
17889f9d | 1097 | |
0c93c8a9 | 1098 | /* Helper for maybe_optimize_arith_overflow. Find in *TP if there are any |
1099 | uses of data (SSA_NAME) other than REALPART_EXPR referencing it. */ | |
1100 | ||
1101 | static tree | |
1102 | find_non_realpart_uses (tree *tp, int *walk_subtrees, void *data) | |
1103 | { | |
1104 | if (TYPE_P (*tp) || TREE_CODE (*tp) == REALPART_EXPR) | |
1105 | *walk_subtrees = 0; | |
1106 | if (*tp == (tree) data) | |
1107 | return *tp; | |
1108 | return NULL_TREE; | |
1109 | } | |
1110 | ||
1111 | /* If the IMAGPART_EXPR of the {ADD,SUB,MUL}_OVERFLOW result is never used, | |
1112 | but REALPART_EXPR is, optimize the {ADD,SUB,MUL}_OVERFLOW internal calls | |
1113 | into plain unsigned {PLUS,MINUS,MULT}_EXPR, and if needed reset debug | |
1114 | uses. */ | |
1115 | ||
1116 | static void | |
1117 | maybe_optimize_arith_overflow (gimple_stmt_iterator *gsi, | |
1118 | enum tree_code subcode) | |
1119 | { | |
42acab1c | 1120 | gimple *stmt = gsi_stmt (*gsi); |
0c93c8a9 | 1121 | tree lhs = gimple_call_lhs (stmt); |
1122 | ||
1123 | if (lhs == NULL || TREE_CODE (lhs) != SSA_NAME) | |
1124 | return; | |
1125 | ||
1126 | imm_use_iterator imm_iter; | |
1127 | use_operand_p use_p; | |
1128 | bool has_debug_uses = false; | |
1129 | bool has_realpart_uses = false; | |
1130 | bool has_other_uses = false; | |
1131 | FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs) | |
1132 | { | |
42acab1c | 1133 | gimple *use_stmt = USE_STMT (use_p); |
0c93c8a9 | 1134 | if (is_gimple_debug (use_stmt)) |
1135 | has_debug_uses = true; | |
1136 | else if (is_gimple_assign (use_stmt) | |
1137 | && gimple_assign_rhs_code (use_stmt) == REALPART_EXPR | |
1138 | && TREE_OPERAND (gimple_assign_rhs1 (use_stmt), 0) == lhs) | |
1139 | has_realpart_uses = true; | |
1140 | else | |
1141 | { | |
1142 | has_other_uses = true; | |
1143 | break; | |
1144 | } | |
1145 | } | |
1146 | ||
1147 | if (!has_realpart_uses || has_other_uses) | |
1148 | return; | |
1149 | ||
1150 | tree arg0 = gimple_call_arg (stmt, 0); | |
1151 | tree arg1 = gimple_call_arg (stmt, 1); | |
1152 | location_t loc = gimple_location (stmt); | |
1153 | tree type = TREE_TYPE (TREE_TYPE (lhs)); | |
1154 | tree utype = type; | |
1155 | if (!TYPE_UNSIGNED (type)) | |
1156 | utype = build_nonstandard_integer_type (TYPE_PRECISION (type), 1); | |
1157 | tree result = fold_build2_loc (loc, subcode, utype, | |
1158 | fold_convert_loc (loc, utype, arg0), | |
1159 | fold_convert_loc (loc, utype, arg1)); | |
1160 | result = fold_convert_loc (loc, type, result); | |
1161 | ||
1162 | if (has_debug_uses) | |
1163 | { | |
42acab1c | 1164 | gimple *use_stmt; |
0c93c8a9 | 1165 | FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, lhs) |
1166 | { | |
1167 | if (!gimple_debug_bind_p (use_stmt)) | |
1168 | continue; | |
1169 | tree v = gimple_debug_bind_get_value (use_stmt); | |
1170 | if (walk_tree (&v, find_non_realpart_uses, lhs, NULL)) | |
1171 | { | |
1172 | gimple_debug_bind_reset_value (use_stmt); | |
1173 | update_stmt (use_stmt); | |
1174 | } | |
1175 | } | |
1176 | } | |
1177 | ||
1178 | if (TREE_CODE (result) == INTEGER_CST && TREE_OVERFLOW (result)) | |
1179 | result = drop_tree_overflow (result); | |
1180 | tree overflow = build_zero_cst (type); | |
1181 | tree ctype = build_complex_type (type); | |
1182 | if (TREE_CODE (result) == INTEGER_CST) | |
1183 | result = build_complex (ctype, result, overflow); | |
1184 | else | |
1185 | result = build2_loc (gimple_location (stmt), COMPLEX_EXPR, | |
1186 | ctype, result, overflow); | |
1187 | ||
1188 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1189 | { | |
1190 | fprintf (dump_file, "Transforming call: "); | |
1191 | print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
1192 | fprintf (dump_file, "because the overflow result is never used into: "); | |
1193 | print_generic_stmt (dump_file, result, TDF_SLIM); | |
1194 | fprintf (dump_file, "\n"); | |
1195 | } | |
1196 | ||
1197 | if (!update_call_from_tree (gsi, result)) | |
1198 | gimplify_and_update_call_from_tree (gsi, result); | |
1199 | } | |
1200 | ||
17889f9d | 1201 | /* Eliminate unnecessary statements. Any instruction not marked as necessary |
1202 | contributes nothing to the program, and can be deleted. */ | |
1203 | ||
a6b3b25c | 1204 | static bool |
17889f9d | 1205 | eliminate_unnecessary_stmts (void) |
1206 | { | |
a6b3b25c | 1207 | bool something_changed = false; |
17889f9d | 1208 | basic_block bb; |
688ff29b | 1209 | gimple_stmt_iterator gsi, psi; |
42acab1c | 1210 | gimple *stmt; |
75a70cf9 | 1211 | tree call; |
f1f41a6c | 1212 | vec<basic_block> h; |
4a5df39c | 1213 | auto_vec<edge> to_remove_edges; |
17889f9d | 1214 | |
1215 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1216 | fprintf (dump_file, "\nEliminating unnecessary statements:\n"); | |
1217 | ||
1218 | clear_special_calls (); | |
17889f9d | 1219 | |
9845d120 | 1220 | /* Walking basic blocks and statements in reverse order avoids |
1221 | releasing SSA names before any other DEFs that refer to them are | |
1222 | released. This helps avoid loss of debug information, as we get | |
1223 | a chance to propagate all RHSs of removed SSAs into debug uses, | |
1224 | rather than only the latest ones. E.g., consider: | |
1225 | ||
1226 | x_3 = y_1 + z_2; | |
1227 | a_5 = x_3 - b_4; | |
1228 | # DEBUG a => a_5 | |
1229 | ||
1230 | If we were to release x_3 before a_5, when we reached a_5 and | |
1231 | tried to substitute it into the debug stmt, we'd see x_3 there, | |
1232 | but x_3's DEF, type, etc would have already been disconnected. | |
1233 | By going backwards, the debug stmt first changes to: | |
1234 | ||
1235 | # DEBUG a => x_3 - b_4 | |
1236 | ||
1237 | and then to: | |
1238 | ||
1239 | # DEBUG a => y_1 + z_2 - b_4 | |
1240 | ||
1241 | as desired. */ | |
1242 | gcc_assert (dom_info_available_p (CDI_DOMINATORS)); | |
34154e27 | 1243 | h = get_all_dominated_blocks (CDI_DOMINATORS, |
1244 | single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun))); | |
9845d120 | 1245 | |
f1f41a6c | 1246 | while (h.length ()) |
17889f9d | 1247 | { |
f1f41a6c | 1248 | bb = h.pop (); |
9845d120 | 1249 | |
17889f9d | 1250 | /* Remove dead statements. */ |
8a349241 | 1251 | auto_bitmap debug_seen; |
688ff29b | 1252 | for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi = psi) |
17889f9d | 1253 | { |
75a70cf9 | 1254 | stmt = gsi_stmt (gsi); |
17889f9d | 1255 | |
688ff29b | 1256 | psi = gsi; |
1257 | gsi_prev (&psi); | |
1258 | ||
17889f9d | 1259 | stats.total++; |
1260 | ||
cac1a11f | 1261 | /* We can mark a call to free as not necessary if the |
9af9fab5 | 1262 | defining statement of its argument is not necessary |
1263 | (and thus is getting removed). */ | |
1264 | if (gimple_plf (stmt, STMT_NECESSARY) | |
1265 | && gimple_call_builtin_p (stmt, BUILT_IN_FREE)) | |
cac1a11f | 1266 | { |
1267 | tree ptr = gimple_call_arg (stmt, 0); | |
9af9fab5 | 1268 | if (TREE_CODE (ptr) == SSA_NAME) |
1269 | { | |
42acab1c | 1270 | gimple *def_stmt = SSA_NAME_DEF_STMT (ptr); |
f01ca8b3 | 1271 | if (!gimple_nop_p (def_stmt) |
1272 | && !gimple_plf (def_stmt, STMT_NECESSARY)) | |
9af9fab5 | 1273 | gimple_set_plf (stmt, STMT_NECESSARY, false); |
1274 | } | |
cac1a11f | 1275 | } |
1276 | ||
75a70cf9 | 1277 | /* If GSI is not necessary then remove it. */ |
1278 | if (!gimple_plf (stmt, STMT_NECESSARY)) | |
a6b3b25c | 1279 | { |
75fa2041 | 1280 | /* Keep clobbers that we can keep live live. */ |
1281 | if (gimple_clobber_p (stmt)) | |
1282 | { | |
1283 | ssa_op_iter iter; | |
1284 | use_operand_p use_p; | |
1285 | bool dead = false; | |
1286 | FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE) | |
1287 | { | |
1288 | tree name = USE_FROM_PTR (use_p); | |
1289 | if (!SSA_NAME_IS_DEFAULT_DEF (name) | |
1290 | && !bitmap_bit_p (processed, SSA_NAME_VERSION (name))) | |
1291 | { | |
1292 | dead = true; | |
1293 | break; | |
1294 | } | |
1295 | } | |
1296 | if (!dead) | |
8a349241 | 1297 | { |
1298 | bitmap_clear (debug_seen); | |
1299 | continue; | |
1300 | } | |
75fa2041 | 1301 | } |
da44a6ca | 1302 | if (!is_gimple_debug (stmt)) |
1303 | something_changed = true; | |
4a5df39c | 1304 | remove_dead_stmt (&gsi, bb, to_remove_edges); |
8a349241 | 1305 | continue; |
a6b3b25c | 1306 | } |
75a70cf9 | 1307 | else if (is_gimple_call (stmt)) |
17889f9d | 1308 | { |
af988fbc | 1309 | tree name = gimple_call_lhs (stmt); |
1310 | ||
1a91d914 | 1311 | notice_special_calls (as_a <gcall *> (stmt)); |
af988fbc | 1312 | |
1313 | /* When LHS of var = call (); is dead, simplify it into | |
1314 | call (); saving one operand. */ | |
1315 | if (name | |
1316 | && TREE_CODE (name) == SSA_NAME | |
08b7917c | 1317 | && !bitmap_bit_p (processed, SSA_NAME_VERSION (name)) |
af988fbc | 1318 | /* Avoid doing so for allocation calls which we |
1319 | did not mark as necessary, it will confuse the | |
1320 | special logic we apply to malloc/free pair removal. */ | |
1321 | && (!(call = gimple_call_fndecl (stmt)) | |
1322 | || DECL_BUILT_IN_CLASS (call) != BUILT_IN_NORMAL | |
060fc206 | 1323 | || (DECL_FUNCTION_CODE (call) != BUILT_IN_ALIGNED_ALLOC |
1324 | && DECL_FUNCTION_CODE (call) != BUILT_IN_MALLOC | |
af988fbc | 1325 | && DECL_FUNCTION_CODE (call) != BUILT_IN_CALLOC |
2b34677f | 1326 | && !ALLOCA_FUNCTION_CODE_P |
1e42d5c6 | 1327 | (DECL_FUNCTION_CODE (call))))) |
7f0432c3 | 1328 | { |
af988fbc | 1329 | something_changed = true; |
1330 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
7f0432c3 | 1331 | { |
af988fbc | 1332 | fprintf (dump_file, "Deleting LHS of call: "); |
1333 | print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
1334 | fprintf (dump_file, "\n"); | |
7f0432c3 | 1335 | } |
af988fbc | 1336 | |
1337 | gimple_call_set_lhs (stmt, NULL_TREE); | |
1338 | maybe_clean_or_replace_eh_stmt (stmt, stmt); | |
1339 | update_stmt (stmt); | |
1340 | release_ssa_name (name); | |
0c368492 | 1341 | |
da008d72 | 1342 | /* GOMP_SIMD_LANE (unless three argument) or ASAN_POISON |
1d86b8dc | 1343 | without lhs is not needed. */ |
ba39c1d4 | 1344 | if (gimple_call_internal_p (stmt)) |
1345 | switch (gimple_call_internal_fn (stmt)) | |
1346 | { | |
1347 | case IFN_GOMP_SIMD_LANE: | |
da008d72 | 1348 | if (gimple_call_num_args (stmt) >= 3 |
1349 | && !integer_nonzerop (gimple_call_arg (stmt, 2))) | |
1d86b8dc | 1350 | break; |
1351 | /* FALLTHRU */ | |
ba39c1d4 | 1352 | case IFN_ASAN_POISON: |
4a5df39c | 1353 | remove_dead_stmt (&gsi, bb, to_remove_edges); |
ba39c1d4 | 1354 | break; |
1355 | default: | |
1356 | break; | |
1357 | } | |
7f0432c3 | 1358 | } |
0c93c8a9 | 1359 | else if (gimple_call_internal_p (stmt)) |
1360 | switch (gimple_call_internal_fn (stmt)) | |
1361 | { | |
1362 | case IFN_ADD_OVERFLOW: | |
1363 | maybe_optimize_arith_overflow (&gsi, PLUS_EXPR); | |
1364 | break; | |
1365 | case IFN_SUB_OVERFLOW: | |
1366 | maybe_optimize_arith_overflow (&gsi, MINUS_EXPR); | |
1367 | break; | |
1368 | case IFN_MUL_OVERFLOW: | |
1369 | maybe_optimize_arith_overflow (&gsi, MULT_EXPR); | |
1370 | break; | |
1371 | default: | |
1372 | break; | |
1373 | } | |
75a70cf9 | 1374 | } |
8a349241 | 1375 | else if (gimple_debug_bind_p (stmt)) |
1376 | { | |
1377 | /* We are only keeping the last debug-bind of a | |
1378 | non-DEBUG_EXPR_DECL variable in a series of | |
1379 | debug-bind stmts. */ | |
1380 | tree var = gimple_debug_bind_get_var (stmt); | |
1381 | if (TREE_CODE (var) != DEBUG_EXPR_DECL | |
1382 | && !bitmap_set_bit (debug_seen, DECL_UID (var))) | |
1383 | remove_dead_stmt (&gsi, bb, to_remove_edges); | |
1384 | continue; | |
1385 | } | |
1386 | bitmap_clear (debug_seen); | |
17889f9d | 1387 | } |
4a5df39c | 1388 | |
1389 | /* Remove dead PHI nodes. */ | |
1390 | something_changed |= remove_dead_phis (bb); | |
17889f9d | 1391 | } |
9845d120 | 1392 | |
f1f41a6c | 1393 | h.release (); |
9845d120 | 1394 | |
b1887855 | 1395 | /* Since we don't track liveness of virtual PHI nodes, it is possible that we |
1396 | rendered some PHI nodes unreachable while they are still in use. | |
1397 | Mark them for renaming. */ | |
4a5df39c | 1398 | if (!to_remove_edges.is_empty ()) |
b1887855 | 1399 | { |
9845d120 | 1400 | basic_block prev_bb; |
1401 | ||
4a5df39c | 1402 | /* Remove edges. We've delayed this to not get bogus debug stmts |
1403 | during PHI node removal. */ | |
1404 | for (unsigned i = 0; i < to_remove_edges.length (); ++i) | |
1405 | remove_edge (to_remove_edges[i]); | |
1406 | cfg_altered = true; | |
1407 | ||
b1887855 | 1408 | find_unreachable_blocks (); |
9845d120 | 1409 | |
1410 | /* Delete all unreachable basic blocks in reverse dominator order. */ | |
34154e27 | 1411 | for (bb = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb; |
1412 | bb != ENTRY_BLOCK_PTR_FOR_FN (cfun); bb = prev_bb) | |
b1887855 | 1413 | { |
9845d120 | 1414 | prev_bb = bb->prev_bb; |
1415 | ||
08b7917c | 1416 | if (!bitmap_bit_p (bb_contains_live_stmts, bb->index) |
a5d536df | 1417 | || !(bb->flags & BB_REACHABLE)) |
b1887855 | 1418 | { |
1a91d914 | 1419 | for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi); |
1420 | gsi_next (&gsi)) | |
1421 | if (virtual_operand_p (gimple_phi_result (gsi.phi ()))) | |
b1887855 | 1422 | { |
1423 | bool found = false; | |
1424 | imm_use_iterator iter; | |
1425 | ||
1a91d914 | 1426 | FOR_EACH_IMM_USE_STMT (stmt, iter, |
1427 | gimple_phi_result (gsi.phi ())) | |
b1887855 | 1428 | { |
1429 | if (!(gimple_bb (stmt)->flags & BB_REACHABLE)) | |
1430 | continue; | |
1431 | if (gimple_code (stmt) == GIMPLE_PHI | |
1432 | || gimple_plf (stmt, STMT_NECESSARY)) | |
1433 | { | |
1434 | found = true; | |
1435 | BREAK_FROM_IMM_USE_STMT (iter); | |
1436 | } | |
1437 | } | |
1438 | if (found) | |
1a91d914 | 1439 | mark_virtual_phi_result_for_renaming (gsi.phi ()); |
b1887855 | 1440 | } |
9845d120 | 1441 | |
a5d536df | 1442 | if (!(bb->flags & BB_REACHABLE)) |
9845d120 | 1443 | { |
1444 | /* Speed up the removal of blocks that don't | |
1445 | dominate others. Walking backwards, this should | |
1446 | be the common case. ??? Do we need to recompute | |
1447 | dominators because of cfg_altered? */ | |
bce107d7 | 1448 | if (!first_dom_son (CDI_DOMINATORS, bb)) |
9845d120 | 1449 | delete_basic_block (bb); |
1450 | else | |
1451 | { | |
1452 | h = get_all_dominated_blocks (CDI_DOMINATORS, bb); | |
1453 | ||
f1f41a6c | 1454 | while (h.length ()) |
9845d120 | 1455 | { |
f1f41a6c | 1456 | bb = h.pop (); |
9845d120 | 1457 | prev_bb = bb->prev_bb; |
1458 | /* Rearrangements to the CFG may have failed | |
1459 | to update the dominators tree, so that | |
1460 | formerly-dominated blocks are now | |
1461 | otherwise reachable. */ | |
1462 | if (!!(bb->flags & BB_REACHABLE)) | |
1463 | continue; | |
1464 | delete_basic_block (bb); | |
1465 | } | |
1466 | ||
f1f41a6c | 1467 | h.release (); |
9845d120 | 1468 | } |
1469 | } | |
b1887855 | 1470 | } |
1471 | } | |
1472 | } | |
dd277d48 | 1473 | |
e98da821 | 1474 | if (bb_postorder) |
1475 | free (bb_postorder); | |
1476 | bb_postorder = NULL; | |
1477 | ||
a6b3b25c | 1478 | return something_changed; |
17889f9d | 1479 | } |
1480 | ||
1481 | ||
4ee9c684 | 1482 | /* Print out removed statement statistics. */ |
1483 | ||
1484 | static void | |
1485 | print_stats (void) | |
1486 | { | |
581f8050 | 1487 | float percg; |
4ee9c684 | 1488 | |
581f8050 | 1489 | percg = ((float) stats.removed / (float) stats.total) * 100; |
1490 | fprintf (dump_file, "Removed %d of %d statements (%d%%)\n", | |
1491 | stats.removed, stats.total, (int) percg); | |
4ee9c684 | 1492 | |
581f8050 | 1493 | if (stats.total_phis == 0) |
1494 | percg = 0; | |
1495 | else | |
1496 | percg = ((float) stats.removed_phis / (float) stats.total_phis) * 100; | |
4ee9c684 | 1497 | |
581f8050 | 1498 | fprintf (dump_file, "Removed %d of %d PHI nodes (%d%%)\n", |
1499 | stats.removed_phis, stats.total_phis, (int) percg); | |
4ee9c684 | 1500 | } |
75a70cf9 | 1501 | |
4ee9c684 | 1502 | /* Initialization for this pass. Set up the used data structures. */ |
1503 | ||
1504 | static void | |
1505 | tree_dce_init (bool aggressive) | |
1506 | { | |
1507 | memset ((void *) &stats, 0, sizeof (stats)); | |
1508 | ||
1509 | if (aggressive) | |
1510 | { | |
fe672ac0 | 1511 | last_stmt_necessary = sbitmap_alloc (last_basic_block_for_fn (cfun)); |
53c5d9d4 | 1512 | bitmap_clear (last_stmt_necessary); |
fe672ac0 | 1513 | bb_contains_live_stmts = sbitmap_alloc (last_basic_block_for_fn (cfun)); |
53c5d9d4 | 1514 | bitmap_clear (bb_contains_live_stmts); |
4ee9c684 | 1515 | } |
1516 | ||
c211d998 | 1517 | processed = sbitmap_alloc (num_ssa_names + 1); |
53c5d9d4 | 1518 | bitmap_clear (processed); |
4ee9c684 | 1519 | |
f1f41a6c | 1520 | worklist.create (64); |
ba8d9702 | 1521 | cfg_altered = false; |
4ee9c684 | 1522 | } |
1523 | ||
1524 | /* Cleanup after this pass. */ | |
1525 | ||
1526 | static void | |
1527 | tree_dce_done (bool aggressive) | |
1528 | { | |
1529 | if (aggressive) | |
1530 | { | |
7ee4e8e8 | 1531 | delete cd; |
e0e865f0 | 1532 | sbitmap_free (visited_control_parents); |
4ee9c684 | 1533 | sbitmap_free (last_stmt_necessary); |
a336775c | 1534 | sbitmap_free (bb_contains_live_stmts); |
1535 | bb_contains_live_stmts = NULL; | |
4ee9c684 | 1536 | } |
1537 | ||
1538 | sbitmap_free (processed); | |
9eee940b | 1539 | |
f1f41a6c | 1540 | worklist.release (); |
4ee9c684 | 1541 | } |
75a70cf9 | 1542 | |
4ee9c684 | 1543 | /* Main routine to eliminate dead code. |
1544 | ||
1545 | AGGRESSIVE controls the aggressiveness of the algorithm. | |
1546 | In conservative mode, we ignore control dependence and simply declare | |
1547 | all but the most trivially dead branches necessary. This mode is fast. | |
1548 | In aggressive mode, control dependences are taken into account, which | |
1549 | results in more dead code elimination, but at the cost of some time. | |
1550 | ||
1551 | FIXME: Aggressive mode before PRE doesn't work currently because | |
1552 | the dominance info is not invalidated after DCE1. This is | |
1553 | not an issue right now because we only run aggressive DCE | |
1554 | as the last tree SSA pass, but keep this in mind when you | |
1555 | start experimenting with pass ordering. */ | |
1556 | ||
a6b3b25c | 1557 | static unsigned int |
4ee9c684 | 1558 | perform_tree_ssa_dce (bool aggressive) |
1559 | { | |
a6b3b25c | 1560 | bool something_changed = 0; |
4ee9c684 | 1561 | |
01631cfb | 1562 | calculate_dominance_info (CDI_DOMINATORS); |
1563 | ||
b1887855 | 1564 | /* Preheaders are needed for SCEV to work. |
1565 | Simple lateches and recorded exits improve chances that loop will | |
1566 | proved to be finite in testcases such as in loop-15.c and loop-24.c */ | |
b1759f48 | 1567 | bool in_loop_pipeline = scev_initialized_p (); |
1568 | if (aggressive && ! in_loop_pipeline) | |
1569 | { | |
1570 | scev_initialize (); | |
1571 | loop_optimizer_init (LOOPS_NORMAL | |
1572 | | LOOPS_HAVE_RECORDED_EXITS); | |
1573 | } | |
b1887855 | 1574 | |
4ee9c684 | 1575 | tree_dce_init (aggressive); |
1576 | ||
1577 | if (aggressive) | |
1578 | { | |
1579 | /* Compute control dependence. */ | |
4ee9c684 | 1580 | calculate_dominance_info (CDI_POST_DOMINATORS); |
ce143ff0 | 1581 | cd = new control_dependences (); |
4ee9c684 | 1582 | |
fe672ac0 | 1583 | visited_control_parents = |
1584 | sbitmap_alloc (last_basic_block_for_fn (cfun)); | |
53c5d9d4 | 1585 | bitmap_clear (visited_control_parents); |
e0e865f0 | 1586 | |
4ee9c684 | 1587 | mark_dfs_back_edges (); |
1588 | } | |
1589 | ||
7ee4e8e8 | 1590 | find_obviously_necessary_stmts (aggressive); |
4ee9c684 | 1591 | |
b1759f48 | 1592 | if (aggressive && ! in_loop_pipeline) |
1593 | { | |
1594 | loop_optimizer_finalize (); | |
1595 | scev_finalize (); | |
1596 | } | |
b1887855 | 1597 | |
dd277d48 | 1598 | longest_chain = 0; |
1599 | total_chain = 0; | |
7729444a | 1600 | nr_walks = 0; |
dd277d48 | 1601 | chain_ovfl = false; |
a48041a4 | 1602 | visited = BITMAP_ALLOC (NULL); |
7ee4e8e8 | 1603 | propagate_necessity (aggressive); |
dd277d48 | 1604 | BITMAP_FREE (visited); |
63505f79 | 1605 | |
a6b3b25c | 1606 | something_changed |= eliminate_unnecessary_stmts (); |
1607 | something_changed |= cfg_altered; | |
4ee9c684 | 1608 | |
72e1a42b | 1609 | /* We do not update postdominators, so free them unconditionally. */ |
1610 | free_dominance_info (CDI_POST_DOMINATORS); | |
4ee9c684 | 1611 | |
ba8d9702 | 1612 | /* If we removed paths in the CFG, then we need to update |
1613 | dominators as well. I haven't investigated the possibility | |
1614 | of incrementally updating dominators. */ | |
1615 | if (cfg_altered) | |
1616 | free_dominance_info (CDI_DOMINATORS); | |
1617 | ||
581f8050 | 1618 | statistics_counter_event (cfun, "Statements deleted", stats.removed); |
1619 | statistics_counter_event (cfun, "PHI nodes deleted", stats.removed_phis); | |
1620 | ||
4ee9c684 | 1621 | /* Debugging dumps. */ |
581f8050 | 1622 | if (dump_file && (dump_flags & (TDF_STATS|TDF_DETAILS))) |
cbcbd868 | 1623 | print_stats (); |
4ee9c684 | 1624 | |
1625 | tree_dce_done (aggressive); | |
423e7698 | 1626 | |
a6b3b25c | 1627 | if (something_changed) |
c919e493 | 1628 | { |
d4f078b5 | 1629 | free_numbers_of_iterations_estimates (cfun); |
b1759f48 | 1630 | if (in_loop_pipeline) |
c919e493 | 1631 | scev_reset (); |
1632 | return TODO_update_ssa | TODO_cleanup_cfg; | |
1633 | } | |
560965e9 | 1634 | return 0; |
4ee9c684 | 1635 | } |
1636 | ||
1637 | /* Pass entry points. */ | |
2a1990e9 | 1638 | static unsigned int |
4ee9c684 | 1639 | tree_ssa_dce (void) |
1640 | { | |
a6b3b25c | 1641 | return perform_tree_ssa_dce (/*aggressive=*/false); |
4ee9c684 | 1642 | } |
1643 | ||
2a1990e9 | 1644 | static unsigned int |
4ee9c684 | 1645 | tree_ssa_cd_dce (void) |
1646 | { | |
a6b3b25c | 1647 | return perform_tree_ssa_dce (/*aggressive=*/optimize >= 2); |
4ee9c684 | 1648 | } |
1649 | ||
7620bc82 | 1650 | namespace { |
1651 | ||
1652 | const pass_data pass_data_dce = | |
4ee9c684 | 1653 | { |
cbe8bda8 | 1654 | GIMPLE_PASS, /* type */ |
1655 | "dce", /* name */ | |
1656 | OPTGROUP_NONE, /* optinfo_flags */ | |
cbe8bda8 | 1657 | TV_TREE_DCE, /* tv_id */ |
1658 | ( PROP_cfg | PROP_ssa ), /* properties_required */ | |
1659 | 0, /* properties_provided */ | |
1660 | 0, /* properties_destroyed */ | |
1661 | 0, /* todo_flags_start */ | |
8b88439e | 1662 | 0, /* todo_flags_finish */ |
4ee9c684 | 1663 | }; |
1664 | ||
7620bc82 | 1665 | class pass_dce : public gimple_opt_pass |
cbe8bda8 | 1666 | { |
1667 | public: | |
9af5ce0c | 1668 | pass_dce (gcc::context *ctxt) |
1669 | : gimple_opt_pass (pass_data_dce, ctxt) | |
cbe8bda8 | 1670 | {} |
1671 | ||
1672 | /* opt_pass methods: */ | |
ae84f584 | 1673 | opt_pass * clone () { return new pass_dce (m_ctxt); } |
31315c24 | 1674 | virtual bool gate (function *) { return flag_tree_dce != 0; } |
65b0537f | 1675 | virtual unsigned int execute (function *) { return tree_ssa_dce (); } |
cbe8bda8 | 1676 | |
1677 | }; // class pass_dce | |
1678 | ||
7620bc82 | 1679 | } // anon namespace |
1680 | ||
cbe8bda8 | 1681 | gimple_opt_pass * |
1682 | make_pass_dce (gcc::context *ctxt) | |
1683 | { | |
1684 | return new pass_dce (ctxt); | |
1685 | } | |
1686 | ||
7620bc82 | 1687 | namespace { |
1688 | ||
1689 | const pass_data pass_data_cd_dce = | |
cbe8bda8 | 1690 | { |
1691 | GIMPLE_PASS, /* type */ | |
1692 | "cddce", /* name */ | |
1693 | OPTGROUP_NONE, /* optinfo_flags */ | |
cbe8bda8 | 1694 | TV_TREE_CD_DCE, /* tv_id */ |
1695 | ( PROP_cfg | PROP_ssa ), /* properties_required */ | |
1696 | 0, /* properties_provided */ | |
1697 | 0, /* properties_destroyed */ | |
1698 | 0, /* todo_flags_start */ | |
8b88439e | 1699 | 0, /* todo_flags_finish */ |
4ee9c684 | 1700 | }; |
cbe8bda8 | 1701 | |
7620bc82 | 1702 | class pass_cd_dce : public gimple_opt_pass |
cbe8bda8 | 1703 | { |
1704 | public: | |
9af5ce0c | 1705 | pass_cd_dce (gcc::context *ctxt) |
1706 | : gimple_opt_pass (pass_data_cd_dce, ctxt) | |
cbe8bda8 | 1707 | {} |
1708 | ||
1709 | /* opt_pass methods: */ | |
ae84f584 | 1710 | opt_pass * clone () { return new pass_cd_dce (m_ctxt); } |
31315c24 | 1711 | virtual bool gate (function *) { return flag_tree_dce != 0; } |
65b0537f | 1712 | virtual unsigned int execute (function *) { return tree_ssa_cd_dce (); } |
cbe8bda8 | 1713 | |
1714 | }; // class pass_cd_dce | |
1715 | ||
7620bc82 | 1716 | } // anon namespace |
1717 | ||
cbe8bda8 | 1718 | gimple_opt_pass * |
1719 | make_pass_cd_dce (gcc::context *ctxt) | |
1720 | { | |
1721 | return new pass_cd_dce (ctxt); | |
1722 | } | |
321b7c23 | 1723 | |
1724 | ||
1725 | /* A cheap DCE interface. WORKLIST is a list of possibly dead stmts and | |
1726 | is consumed by this function. The function has linear complexity in | |
1727 | the number of dead stmts with a constant factor like the average SSA | |
1728 | use operands number. */ | |
1729 | ||
1730 | void | |
1731 | simple_dce_from_worklist (bitmap worklist) | |
1732 | { | |
1733 | while (! bitmap_empty_p (worklist)) | |
1734 | { | |
1735 | /* Pop item. */ | |
1736 | unsigned i = bitmap_first_set_bit (worklist); | |
1737 | bitmap_clear_bit (worklist, i); | |
1738 | ||
1739 | tree def = ssa_name (i); | |
1740 | /* Removed by somebody else or still in use. */ | |
1741 | if (! def || ! has_zero_uses (def)) | |
1742 | continue; | |
1743 | ||
1744 | gimple *t = SSA_NAME_DEF_STMT (def); | |
1745 | if (gimple_has_side_effects (t)) | |
1746 | continue; | |
1747 | ||
1748 | /* Add uses to the worklist. */ | |
1749 | ssa_op_iter iter; | |
1750 | use_operand_p use_p; | |
1751 | FOR_EACH_PHI_OR_STMT_USE (use_p, t, iter, SSA_OP_USE) | |
1752 | { | |
1753 | tree use = USE_FROM_PTR (use_p); | |
1754 | if (TREE_CODE (use) == SSA_NAME | |
1755 | && ! SSA_NAME_IS_DEFAULT_DEF (use)) | |
1756 | bitmap_set_bit (worklist, SSA_NAME_VERSION (use)); | |
1757 | } | |
1758 | ||
1759 | /* Remove stmt. */ | |
1760 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1761 | { | |
1762 | fprintf (dump_file, "Removing dead stmt:"); | |
1763 | print_gimple_stmt (dump_file, t, 0); | |
1764 | } | |
1765 | gimple_stmt_iterator gsi = gsi_for_stmt (t); | |
1766 | if (gimple_code (t) == GIMPLE_PHI) | |
1767 | remove_phi_node (&gsi, true); | |
1768 | else | |
1769 | { | |
1770 | gsi_remove (&gsi, true); | |
1771 | release_defs (t); | |
1772 | } | |
1773 | } | |
1774 | } |