Branch data Line data Source code
1 : : /* Dead code elimination pass for the GNU compiler.
2 : : Copyright (C) 2002-2024 Free Software Foundation, Inc.
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.
6 : :
7 : : This file is part of GCC.
8 : :
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
11 : : Free Software Foundation; either version 3, or (at your option) any
12 : : later version.
13 : :
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.
18 : :
19 : : You should have received a copy of the GNU General Public License
20 : : along with GCC; see the file COPYING3. If not see
21 : : <http://www.gnu.org/licenses/>. */
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"
48 : : #include "backend.h"
49 : : #include "rtl.h"
50 : : #include "tree.h"
51 : : #include "gimple.h"
52 : : #include "cfghooks.h"
53 : : #include "tree-pass.h"
54 : : #include "ssa.h"
55 : : #include "gimple-pretty-print.h"
56 : : #include "fold-const.h"
57 : : #include "calls.h"
58 : : #include "cfganal.h"
59 : : #include "tree-eh.h"
60 : : #include "gimplify.h"
61 : : #include "gimple-iterator.h"
62 : : #include "tree-cfg.h"
63 : : #include "tree-ssa-loop-niter.h"
64 : : #include "tree-into-ssa.h"
65 : : #include "tree-dfa.h"
66 : : #include "cfgloop.h"
67 : : #include "tree-scalar-evolution.h"
68 : : #include "tree-ssa-propagate.h"
69 : : #include "gimple-fold.h"
70 : : #include "tree-ssa.h"
71 : : #include "ipa-modref-tree.h"
72 : : #include "ipa-modref.h"
73 : :
74 : : static struct stmt_stats
75 : : {
76 : : int total;
77 : : int total_phis;
78 : : int removed;
79 : : int removed_phis;
80 : : } stats;
81 : :
82 : : #define STMT_NECESSARY GF_PLF_1
83 : :
84 : : static vec<gimple *> worklist;
85 : :
86 : : /* Vector indicating an SSA name has already been processed and marked
87 : : as necessary. */
88 : : static sbitmap processed;
89 : :
90 : : /* Vector indicating that the last statement of a basic block has already
91 : : been marked as necessary. */
92 : : static sbitmap last_stmt_necessary;
93 : :
94 : : /* Vector indicating that BB contains statements that are live. */
95 : : static sbitmap bb_contains_live_stmts;
96 : :
97 : : /* Before we can determine whether a control branch is dead, we need to
98 : : compute which blocks are control dependent on which edges.
99 : :
100 : : We expect each block to be control dependent on very few edges so we
101 : : use a bitmap for each block recording its edges. An array holds the
102 : : bitmap. The Ith bit in the bitmap is set if that block is dependent
103 : : on the Ith edge. */
104 : : static control_dependences *cd;
105 : :
106 : : /* Vector indicating that a basic block has already had all the edges
107 : : processed that it is control dependent on. */
108 : : static sbitmap visited_control_parents;
109 : :
110 : : /* TRUE if this pass alters the CFG (by removing control statements).
111 : : FALSE otherwise.
112 : :
113 : : If this pass alters the CFG, then it will arrange for the dominators
114 : : to be recomputed. */
115 : : static bool cfg_altered;
116 : :
117 : : /* When non-NULL holds map from basic block index into the postorder. */
118 : : static int *bb_postorder;
119 : :
120 : :
121 : : /* True if we should treat any stmt with a vdef as necessary. */
122 : :
123 : : static inline bool
124 : 252925381 : keep_all_vdefs_p ()
125 : : {
126 : 252925381 : return optimize_debug;
127 : : }
128 : :
129 : : /* 1 if CALLEE is the function __cxa_atexit.
130 : : 2 if CALLEE is the function __aeabi_atexit.
131 : : 0 otherwise. */
132 : :
133 : : static inline int
134 : 81100495 : is_cxa_atexit (const_tree callee)
135 : : {
136 : 81100495 : if (callee != NULL_TREE
137 : 81100495 : && strcmp (IDENTIFIER_POINTER (DECL_NAME (callee)), "__cxa_atexit") == 0)
138 : : return 1;
139 : 81006457 : if (callee != NULL_TREE
140 : 81006457 : && strcmp (IDENTIFIER_POINTER (DECL_NAME (callee)), "__aeabi_atexit") == 0)
141 : 0 : return 2;
142 : : return 0;
143 : : }
144 : :
145 : : /* True if STMT is a call to __cxa_atexit (or __aeabi_atexit)
146 : : and the function argument to that call is a const or pure
147 : : non-looping function decl. */
148 : :
149 : : static inline bool
150 : 81100495 : is_removable_cxa_atexit_call (gimple *stmt)
151 : : {
152 : 81100495 : tree callee = gimple_call_fndecl (stmt);
153 : 81100495 : int functype = is_cxa_atexit (callee);
154 : 81100495 : if (!functype)
155 : : return false;
156 : 94038 : if (gimple_call_num_args (stmt) != 3)
157 : : return false;
158 : :
159 : : /* The function argument is the 1st argument for __cxa_atexit
160 : : or the 2nd argument for __eabi_atexit. */
161 : 188076 : tree arg = gimple_call_arg (stmt, functype == 2 ? 1 : 0);
162 : 94038 : if (TREE_CODE (arg) != ADDR_EXPR)
163 : : return false;
164 : 94038 : arg = TREE_OPERAND (arg, 0);
165 : 94038 : if (TREE_CODE (arg) != FUNCTION_DECL)
166 : : return false;
167 : 94038 : int flags = flags_from_decl_or_type (arg);
168 : :
169 : : /* If the function is noreturn then it cannot be removed. */
170 : 94038 : if (flags & ECF_NORETURN)
171 : : return false;
172 : :
173 : : /* The function needs to be const or pure and non looping. */
174 : 93880 : return (flags & (ECF_CONST|ECF_PURE))
175 : 93880 : && !(flags & ECF_LOOPING_CONST_OR_PURE);
176 : : }
177 : :
178 : : /* If STMT is not already marked necessary, mark it, and add it to the
179 : : worklist if ADD_TO_WORKLIST is true. */
180 : :
181 : : static inline void
182 : 392128309 : mark_stmt_necessary (gimple *stmt, bool add_to_worklist)
183 : : {
184 : 392128309 : gcc_assert (stmt);
185 : :
186 : 392128309 : if (gimple_plf (stmt, STMT_NECESSARY))
187 : : return;
188 : :
189 : 392128121 : if (dump_file && (dump_flags & TDF_DETAILS))
190 : : {
191 : 850 : fprintf (dump_file, "Marking useful stmt: ");
192 : 850 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
193 : 850 : fprintf (dump_file, "\n");
194 : : }
195 : :
196 : 392128121 : gimple_set_plf (stmt, STMT_NECESSARY, true);
197 : 392128121 : if (add_to_worklist)
198 : 99300332 : worklist.safe_push (stmt);
199 : 99300332 : if (add_to_worklist && bb_contains_live_stmts && !is_gimple_debug (stmt))
200 : 34426583 : bitmap_set_bit (bb_contains_live_stmts, gimple_bb (stmt)->index);
201 : : }
202 : :
203 : :
204 : : /* Mark the statement defining operand OP as necessary. */
205 : :
206 : : static inline void
207 : 311949043 : mark_operand_necessary (tree op)
208 : : {
209 : 311949043 : gimple *stmt;
210 : 311949043 : int ver;
211 : :
212 : 311949043 : gcc_assert (op);
213 : :
214 : 311949043 : ver = SSA_NAME_VERSION (op);
215 : 311949043 : if (bitmap_bit_p (processed, ver))
216 : : {
217 : 111837002 : stmt = SSA_NAME_DEF_STMT (op);
218 : 111837002 : gcc_assert (gimple_nop_p (stmt)
219 : : || gimple_plf (stmt, STMT_NECESSARY));
220 : 168807668 : return;
221 : : }
222 : 200112041 : bitmap_set_bit (processed, ver);
223 : :
224 : 200112041 : stmt = SSA_NAME_DEF_STMT (op);
225 : 200112041 : gcc_assert (stmt);
226 : :
227 : 200112041 : if (gimple_plf (stmt, STMT_NECESSARY) || gimple_nop_p (stmt))
228 : : return;
229 : :
230 : 143141375 : if (dump_file && (dump_flags & TDF_DETAILS))
231 : : {
232 : 262 : fprintf (dump_file, "marking necessary through ");
233 : 262 : print_generic_expr (dump_file, op);
234 : 262 : fprintf (dump_file, " stmt ");
235 : 262 : print_gimple_stmt (dump_file, stmt, 0);
236 : : }
237 : :
238 : 143141375 : gimple_set_plf (stmt, STMT_NECESSARY, true);
239 : 143141375 : if (bb_contains_live_stmts)
240 : 49119912 : bitmap_set_bit (bb_contains_live_stmts, gimple_bb (stmt)->index);
241 : 143141375 : worklist.safe_push (stmt);
242 : : }
243 : :
244 : : /* Return true if STMT is a call to allocation function that can be
245 : : optimized out if the memory block is never used for anything else
246 : : then NULL pointer check or free.
247 : : If NON_NULL_CHECK is false, we can furhter assume that return value
248 : : is never checked to be non-NULL. */
249 : :
250 : : static bool
251 : 33740543 : is_removable_allocation_p (gcall *stmt, bool non_null_check)
252 : : {
253 : 33740543 : tree callee = gimple_call_fndecl (stmt);
254 : 33740543 : if (callee != NULL_TREE
255 : 33740543 : && fndecl_built_in_p (callee, BUILT_IN_NORMAL))
256 : 8593873 : switch (DECL_FUNCTION_CODE (callee))
257 : : {
258 : 602194 : case BUILT_IN_MALLOC:
259 : 602194 : case BUILT_IN_ALIGNED_ALLOC:
260 : 602194 : case BUILT_IN_CALLOC:
261 : 602194 : CASE_BUILT_IN_ALLOCA:
262 : 602194 : case BUILT_IN_STRDUP:
263 : 602194 : case BUILT_IN_STRNDUP:
264 : 602194 : return non_null_check ? flag_malloc_dce > 1 : flag_malloc_dce;
265 : :
266 : : case BUILT_IN_GOMP_ALLOC:
267 : : return true;
268 : :
269 : : default:;
270 : : }
271 : :
272 : 33133332 : if (callee != NULL_TREE
273 : 31209976 : && flag_allocation_dce
274 : 31206782 : && gimple_call_from_new_or_delete (stmt)
275 : 34108938 : && DECL_IS_REPLACEABLE_OPERATOR_NEW_P (callee))
276 : 238595 : return true;
277 : : return false;
278 : : }
279 : :
280 : : /* Return true if STMT is a conditional
281 : : if (ptr != NULL)
282 : : where ptr was returned by a removable allocation function. */
283 : :
284 : : static bool
285 : 224181766 : checks_return_value_of_removable_allocation_p (gimple *stmt)
286 : : {
287 : 224181766 : gcall *def_stmt;
288 : 224181766 : return gimple_code (stmt) == GIMPLE_COND
289 : 28510331 : && (gimple_cond_code (stmt) == EQ_EXPR
290 : 20030188 : || gimple_cond_code (stmt) == NE_EXPR)
291 : 21911959 : && integer_zerop (gimple_cond_rhs (stmt))
292 : 12322345 : && TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME
293 : : && (def_stmt = dyn_cast <gcall *>
294 : 12319862 : (SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt))))
295 : 227345801 : && is_removable_allocation_p (def_stmt, true);
296 : : }
297 : :
298 : :
299 : : /* Mark STMT as necessary if it obviously is. Add it to the worklist if
300 : : it can make other statements necessary.
301 : :
302 : : If AGGRESSIVE is false, control statements are conservatively marked as
303 : : necessary. */
304 : :
305 : : static void
306 : 519692798 : mark_stmt_if_obviously_necessary (gimple *stmt, bool aggressive)
307 : : {
308 : : /* Statements that are implicitly live. Most function calls, asm
309 : : and return statements are required. Labels and GIMPLE_BIND nodes
310 : : are kept because they are control flow, and we have no way of
311 : : knowing whether they can be removed. DCE can eliminate all the
312 : : other statements in a block, and CFG can then remove the block
313 : : and labels. */
314 : 519692798 : switch (gimple_code (stmt))
315 : : {
316 : 6544095 : case GIMPLE_PREDICT:
317 : 6544095 : case GIMPLE_LABEL:
318 : 6544095 : mark_stmt_necessary (stmt, false);
319 : 6544095 : return;
320 : :
321 : 9470553 : case GIMPLE_ASM:
322 : 9470553 : case GIMPLE_RESX:
323 : 9470553 : case GIMPLE_RETURN:
324 : 9470553 : mark_stmt_necessary (stmt, true);
325 : 9470553 : return;
326 : :
327 : 35000383 : case GIMPLE_CALL:
328 : 35000383 : {
329 : 35000383 : gcall *call = as_a <gcall *> (stmt);
330 : :
331 : : /* Never elide a noreturn call we pruned control-flow for. */
332 : 35000383 : if ((gimple_call_flags (call) & ECF_NORETURN)
333 : 35000383 : && gimple_call_ctrl_altering_p (call))
334 : : {
335 : 4680335 : mark_stmt_necessary (call, true);
336 : 4680335 : return;
337 : : }
338 : :
339 : :
340 : 30320048 : if (is_removable_allocation_p (call, false))
341 : : return;
342 : :
343 : :
344 : : /* For __cxa_atexit calls, don't mark as necessary right away. */
345 : 29725784 : if (is_removable_cxa_atexit_call (call))
346 : : return;
347 : :
348 : : /* IFN_GOACC_LOOP calls are necessary in that they are used to
349 : : represent parameter (i.e. step, bound) of a lowered OpenACC
350 : : partitioned loop. But this kind of partitioned loop might not
351 : : survive from aggressive loop removal for it has loop exit and
352 : : is assumed to be finite. Therefore, we need to explicitly mark
353 : : these calls. (An example is libgomp.oacc-c-c++-common/pr84955.c) */
354 : 29725378 : if (gimple_call_internal_p (call, IFN_GOACC_LOOP))
355 : : {
356 : 25330 : mark_stmt_necessary (call, true);
357 : 25330 : return;
358 : : }
359 : : break;
360 : : }
361 : :
362 : 286528121 : case GIMPLE_DEBUG:
363 : : /* Debug temps without a value are not useful. ??? If we could
364 : : easily locate the debug temp bind stmt for a use thereof,
365 : : would could refrain from marking all debug temps here, and
366 : : mark them only if they're used. */
367 : 286528121 : if (gimple_debug_nonbind_marker_p (stmt)
368 : 216747787 : || !gimple_debug_bind_p (stmt)
369 : 216021618 : || gimple_debug_bind_has_value_p (stmt)
370 : 381418141 : || TREE_CODE (gimple_debug_bind_get_var (stmt)) != DEBUG_EXPR_DECL)
371 : 286283694 : mark_stmt_necessary (stmt, false);
372 : : return;
373 : :
374 : 1869 : case GIMPLE_GOTO:
375 : 1869 : gcc_assert (!simple_goto_p (stmt));
376 : 1869 : mark_stmt_necessary (stmt, true);
377 : 1869 : return;
378 : :
379 : 28540348 : case GIMPLE_COND:
380 : 28540348 : gcc_assert (EDGE_COUNT (gimple_bb (stmt)->succs) == 2);
381 : : /* Fall through. */
382 : :
383 : 28686625 : case GIMPLE_SWITCH:
384 : 28686625 : if (! aggressive)
385 : 19018952 : mark_stmt_necessary (stmt, true);
386 : : break;
387 : :
388 : 153419581 : case GIMPLE_ASSIGN:
389 : : /* Mark indirect CLOBBERs to be lazily removed if their SSA operands
390 : : do not prevail. That also makes control flow leading to them
391 : : not necessary in aggressive mode. */
392 : 163768601 : if (gimple_clobber_p (stmt) && !zero_ssa_operands (stmt, SSA_OP_USE))
393 : : return;
394 : : break;
395 : :
396 : : default:
397 : : break;
398 : : }
399 : :
400 : : /* If the statement has volatile operands, it needs to be preserved.
401 : : Same for statements that can alter control flow in unpredictable
402 : : ways. */
403 : 210610807 : if (gimple_has_side_effects (stmt) || is_ctrl_altering_stmt (stmt))
404 : : {
405 : 39207121 : mark_stmt_necessary (stmt, true);
406 : 39207121 : return;
407 : : }
408 : :
409 : : /* If a statement could throw, it can be deemed necessary unless we
410 : : are allowed to remove dead EH. Test this after checking for
411 : : new/delete operators since we always elide their EH. */
412 : 171403686 : if (!cfun->can_delete_dead_exceptions
413 : 171403686 : && stmt_could_throw_p (cfun, stmt))
414 : : {
415 : 5379844 : mark_stmt_necessary (stmt, true);
416 : 5379844 : return;
417 : : }
418 : :
419 : 206898108 : if ((gimple_vdef (stmt) && keep_all_vdefs_p ())
420 : 206879146 : || stmt_may_clobber_global_p (stmt, false))
421 : : {
422 : 11881559 : mark_stmt_necessary (stmt, true);
423 : 11881559 : return;
424 : : }
425 : :
426 : : return;
427 : : }
428 : :
429 : :
430 : : /* Mark the last statement of BB as necessary. */
431 : :
432 : : static bool
433 : 40012932 : mark_last_stmt_necessary (basic_block bb)
434 : : {
435 : 40012932 : if (!bitmap_set_bit (last_stmt_necessary, bb->index))
436 : : return true;
437 : :
438 : 15683216 : bitmap_set_bit (bb_contains_live_stmts, bb->index);
439 : :
440 : : /* We actually mark the statement only if it is a control statement. */
441 : 15683216 : gimple *stmt = *gsi_last_bb (bb);
442 : 15683216 : if (stmt && is_ctrl_stmt (stmt))
443 : : {
444 : 9634957 : mark_stmt_necessary (stmt, true);
445 : 9634957 : return true;
446 : : }
447 : : return false;
448 : : }
449 : :
450 : :
451 : : /* Mark control dependent edges of BB as necessary. We have to do this only
452 : : once for each basic block so we set the appropriate bit after we're done.
453 : :
454 : : When IGNORE_SELF is true, ignore BB in the list of control dependences. */
455 : :
456 : : static void
457 : 29461055 : mark_control_dependent_edges_necessary (basic_block bb, bool ignore_self)
458 : : {
459 : 29461055 : bitmap_iterator bi;
460 : 29461055 : unsigned edge_number;
461 : 29461055 : bool skipped = false;
462 : :
463 : 29461055 : gcc_assert (bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
464 : :
465 : 29461055 : if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
466 : 3273104 : return;
467 : :
468 : 64881322 : EXECUTE_IF_SET_IN_BITMAP (cd->get_edges_dependent_on (bb->index),
469 : : 0, edge_number, bi)
470 : : {
471 : 38693371 : basic_block cd_bb = cd->get_edge_src (edge_number);
472 : :
473 : 38693371 : if (ignore_self && cd_bb == bb)
474 : : {
475 : 64338 : skipped = true;
476 : 64338 : continue;
477 : : }
478 : :
479 : 38629033 : if (!mark_last_stmt_necessary (cd_bb))
480 : 6046019 : mark_control_dependent_edges_necessary (cd_bb, false);
481 : : }
482 : :
483 : 26187951 : if (!skipped)
484 : 26123613 : bitmap_set_bit (visited_control_parents, bb->index);
485 : : }
486 : :
487 : :
488 : : /* Find obviously necessary statements. These are things like most function
489 : : calls, and stores to file level variables.
490 : :
491 : : If EL is NULL, control statements are conservatively marked as
492 : : necessary. Otherwise it contains the list of edges used by control
493 : : dependence analysis. */
494 : :
495 : : static void
496 : 7642351 : find_obviously_necessary_stmts (bool aggressive)
497 : : {
498 : 7642351 : basic_block bb;
499 : 7642351 : gimple_stmt_iterator gsi;
500 : 7642351 : edge e;
501 : 7642351 : gimple *phi, *stmt;
502 : 7642351 : int flags;
503 : :
504 : 84331334 : FOR_EACH_BB_FN (bb, cfun)
505 : : {
506 : : /* PHI nodes are never inherently necessary. */
507 : 110601399 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
508 : : {
509 : 33912416 : phi = gsi_stmt (gsi);
510 : 33912416 : gimple_set_plf (phi, STMT_NECESSARY, false);
511 : : }
512 : :
513 : : /* Check all statements in the block. */
514 : 673070764 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
515 : : {
516 : 519692798 : stmt = gsi_stmt (gsi);
517 : 519692798 : gimple_set_plf (stmt, STMT_NECESSARY, false);
518 : 519692798 : mark_stmt_if_obviously_necessary (stmt, aggressive);
519 : : }
520 : : }
521 : :
522 : : /* Pure and const functions are finite and thus have no infinite loops in
523 : : them. */
524 : 7642351 : flags = flags_from_decl_or_type (current_function_decl);
525 : 7642351 : if ((flags & (ECF_CONST|ECF_PURE)) && !(flags & ECF_LOOPING_CONST_OR_PURE))
526 : 909310 : return;
527 : :
528 : : /* Prevent the empty possibly infinite loops from being removed. This is
529 : : needed to make the logic in remove_dead_stmt work to identify the
530 : : correct edge to keep when removing a controlling condition. */
531 : 6733041 : if (aggressive)
532 : : {
533 : 3093789 : if (mark_irreducible_loops ())
534 : 234577 : FOR_EACH_BB_FN (bb, cfun)
535 : : {
536 : 229589 : edge_iterator ei;
537 : 577177 : FOR_EACH_EDGE (e, ei, bb->succs)
538 : 347588 : if ((e->flags & EDGE_DFS_BACK)
539 : 347588 : && (e->flags & EDGE_IRREDUCIBLE_LOOP))
540 : : {
541 : 8900 : if (dump_file)
542 : 0 : fprintf (dump_file, "Marking back edge of irreducible "
543 : 0 : "loop %i->%i\n", e->src->index, e->dest->index);
544 : 8900 : mark_control_dependent_edges_necessary (e->dest, false);
545 : : }
546 : : }
547 : :
548 : 10938849 : for (auto loop : loops_list (cfun, 0))
549 : : /* For loops without an exit do not mark any condition. */
550 : 1657482 : if (loop->exits->next->e && !finite_loop_p (loop))
551 : : {
552 : 272308 : if (dump_file)
553 : 1 : fprintf (dump_file, "cannot prove finiteness of loop %i\n",
554 : : loop->num);
555 : 272308 : mark_control_dependent_edges_necessary (loop->latch, false);
556 : 3093789 : }
557 : : }
558 : : }
559 : :
560 : :
561 : : /* Return true if REF is based on an aliased base, otherwise false. */
562 : :
563 : : static bool
564 : 91356226 : ref_may_be_aliased (tree ref)
565 : : {
566 : 91356226 : if (TREE_CODE (ref) == WITH_SIZE_EXPR)
567 : 0 : ref = TREE_OPERAND (ref, 0);
568 : 167689754 : while (handled_component_p (ref))
569 : 76333528 : ref = TREE_OPERAND (ref, 0);
570 : 91356226 : if ((TREE_CODE (ref) == MEM_REF || TREE_CODE (ref) == TARGET_MEM_REF)
571 : 91356226 : && TREE_CODE (TREE_OPERAND (ref, 0)) == ADDR_EXPR)
572 : 13072655 : ref = TREE_OPERAND (TREE_OPERAND (ref, 0), 0);
573 : 91356226 : return !(DECL_P (ref)
574 : 61879403 : && !may_be_aliased (ref));
575 : : }
576 : :
577 : : static bitmap visited = NULL;
578 : : static unsigned int longest_chain = 0;
579 : : static unsigned int total_chain = 0;
580 : : static unsigned int nr_walks = 0;
581 : : static bool chain_ovfl = false;
582 : :
583 : : /* Worker for the walker that marks reaching definitions of REF,
584 : : which is based on a non-aliased decl, necessary. It returns
585 : : true whenever the defining statement of the current VDEF is
586 : : a kill for REF, as no dominating may-defs are necessary for REF
587 : : anymore. DATA points to the basic-block that contains the
588 : : stmt that refers to REF. */
589 : :
590 : : static bool
591 : 37126069 : mark_aliased_reaching_defs_necessary_1 (ao_ref *ref, tree vdef, void *data)
592 : : {
593 : 37126069 : gimple *def_stmt = SSA_NAME_DEF_STMT (vdef);
594 : :
595 : : /* All stmts we visit are necessary. */
596 : 37126069 : if (! gimple_clobber_p (def_stmt))
597 : 36842338 : mark_operand_necessary (vdef);
598 : :
599 : : /* If the stmt lhs kills ref, then we can stop walking. */
600 : 37126069 : if (gimple_has_lhs (def_stmt)
601 : 27305874 : && TREE_CODE (gimple_get_lhs (def_stmt)) != SSA_NAME
602 : : /* The assignment is not necessarily carried out if it can throw
603 : : and we can catch it in the current function where we could inspect
604 : : the previous value.
605 : : ??? We only need to care about the RHS throwing. For aggregate
606 : : assignments or similar calls and non-call exceptions the LHS
607 : : might throw as well. */
608 : 35391918 : && !stmt_can_throw_internal (cfun, def_stmt))
609 : : {
610 : 23350189 : tree base, lhs = gimple_get_lhs (def_stmt);
611 : 23350189 : poly_int64 size, offset, max_size;
612 : 23350189 : bool reverse;
613 : 23350189 : ao_ref_base (ref);
614 : 23350189 : base
615 : 23350189 : = get_ref_base_and_extent (lhs, &offset, &size, &max_size, &reverse);
616 : : /* We can get MEM[symbol: sZ, index: D.8862_1] here,
617 : : so base == refd->base does not always hold. */
618 : 23350189 : if (base == ref->base)
619 : : {
620 : : /* For a must-alias check we need to be able to constrain
621 : : the accesses properly. */
622 : 21386627 : if (known_eq (size, max_size)
623 : 21386627 : && known_subrange_p (ref->offset, ref->max_size, offset, size))
624 : 8196498 : return true;
625 : : /* Or they need to be exactly the same. */
626 : 13191082 : else if (ref->ref
627 : : /* Make sure there is no induction variable involved
628 : : in the references (gcc.c-torture/execute/pr42142.c).
629 : : The simplest way is to check if the kill dominates
630 : : the use. */
631 : : /* But when both are in the same block we cannot
632 : : easily tell whether we came from a backedge
633 : : unless we decide to compute stmt UIDs
634 : : (see PR58246). */
635 : 13191082 : && (basic_block) data != gimple_bb (def_stmt)
636 : 5667220 : && dominated_by_p (CDI_DOMINATORS, (basic_block) data,
637 : 5667220 : gimple_bb (def_stmt))
638 : 16292834 : && operand_equal_p (ref->ref, lhs, 0))
639 : : return true;
640 : : }
641 : : }
642 : :
643 : : /* Otherwise keep walking. */
644 : : return false;
645 : : }
646 : :
647 : : static void
648 : 13274315 : mark_aliased_reaching_defs_necessary (gimple *stmt, tree ref)
649 : : {
650 : : /* Should have been caught before calling this function. */
651 : 13274315 : gcc_checking_assert (!keep_all_vdefs_p ());
652 : :
653 : 13274315 : unsigned int chain;
654 : 13274315 : ao_ref refd;
655 : 13274315 : gcc_assert (!chain_ovfl);
656 : 13274315 : ao_ref_init (&refd, ref);
657 : 26548630 : chain = walk_aliased_vdefs (&refd, gimple_vuse (stmt),
658 : : mark_aliased_reaching_defs_necessary_1,
659 : 13274315 : gimple_bb (stmt), NULL);
660 : 13274315 : if (chain > longest_chain)
661 : 2069481 : longest_chain = chain;
662 : 13274315 : total_chain += chain;
663 : 13274315 : nr_walks++;
664 : 13274315 : }
665 : :
666 : : /* Worker for the walker that marks reaching definitions of REF, which
667 : : is not based on a non-aliased decl. For simplicity we need to end
668 : : up marking all may-defs necessary that are not based on a non-aliased
669 : : decl. The only job of this walker is to skip may-defs based on
670 : : a non-aliased decl. */
671 : :
672 : : static bool
673 : 70595988 : mark_all_reaching_defs_necessary_1 (ao_ref *ref ATTRIBUTE_UNUSED,
674 : : tree vdef, void *data ATTRIBUTE_UNUSED)
675 : : {
676 : 70595988 : gimple *def_stmt = SSA_NAME_DEF_STMT (vdef);
677 : :
678 : : /* We have to skip already visited (and thus necessary) statements
679 : : to make the chaining work after we dropped back to simple mode. */
680 : 70595988 : if (chain_ovfl
681 : 70595988 : && bitmap_bit_p (processed, SSA_NAME_VERSION (vdef)))
682 : : {
683 : 2567384 : gcc_assert (gimple_nop_p (def_stmt)
684 : : || gimple_plf (def_stmt, STMT_NECESSARY));
685 : : return false;
686 : : }
687 : :
688 : : /* We want to skip stores to non-aliased variables. */
689 : 68028604 : if (!chain_ovfl
690 : 68028604 : && gimple_assign_single_p (def_stmt))
691 : : {
692 : 45374650 : tree lhs = gimple_assign_lhs (def_stmt);
693 : 45374650 : if (!ref_may_be_aliased (lhs))
694 : : return false;
695 : : }
696 : :
697 : : /* We want to skip statments that do not constitute stores but have
698 : : a virtual definition. */
699 : 56571520 : if (gcall *call = dyn_cast <gcall *> (def_stmt))
700 : : {
701 : 21783825 : tree callee = gimple_call_fndecl (call);
702 : 21783825 : if (callee != NULL_TREE
703 : 21783825 : && fndecl_built_in_p (callee, BUILT_IN_NORMAL))
704 : 3640630 : switch (DECL_FUNCTION_CODE (callee))
705 : : {
706 : : case BUILT_IN_MALLOC:
707 : : case BUILT_IN_ALIGNED_ALLOC:
708 : : case BUILT_IN_CALLOC:
709 : : CASE_BUILT_IN_ALLOCA:
710 : : case BUILT_IN_STRDUP:
711 : : case BUILT_IN_STRNDUP:
712 : : case BUILT_IN_FREE:
713 : : case BUILT_IN_GOMP_ALLOC:
714 : : case BUILT_IN_GOMP_FREE:
715 : : return false;
716 : :
717 : : default:;
718 : : }
719 : :
720 : 21207358 : if (callee != NULL_TREE
721 : 20149185 : && (DECL_IS_REPLACEABLE_OPERATOR_NEW_P (callee)
722 : 19960836 : || DECL_IS_OPERATOR_DELETE_P (callee))
723 : 21909708 : && gimple_call_from_new_or_delete (call))
724 : : return false;
725 : 20515514 : if (is_removable_cxa_atexit_call (call))
726 : : return false;
727 : : }
728 : :
729 : 55303021 : if (! gimple_clobber_p (def_stmt))
730 : 49758908 : mark_operand_necessary (vdef);
731 : :
732 : : return false;
733 : : }
734 : :
735 : : static void
736 : 66082289 : mark_all_reaching_defs_necessary (gimple *stmt)
737 : : {
738 : : /* Should have been caught before calling this function. */
739 : 66082289 : gcc_checking_assert (!keep_all_vdefs_p ());
740 : 132164578 : walk_aliased_vdefs (NULL, gimple_vuse (stmt),
741 : : mark_all_reaching_defs_necessary_1, NULL, &visited);
742 : 66082289 : }
743 : :
744 : : /* Return true for PHI nodes with one or identical arguments
745 : : can be removed. */
746 : : static bool
747 : 18366738 : degenerate_phi_p (gimple *phi)
748 : : {
749 : 18366738 : unsigned int i;
750 : 18366738 : tree op = gimple_phi_arg_def (phi, 0);
751 : 19331406 : for (i = 1; i < gimple_phi_num_args (phi); i++)
752 : 16652692 : if (gimple_phi_arg_def (phi, i) != op)
753 : : return false;
754 : : return true;
755 : : }
756 : :
757 : : /* Return that NEW_CALL and DELETE_CALL are a valid pair of new
758 : : and delete operators. */
759 : :
760 : : static bool
761 : 38518 : valid_new_delete_pair_p (gimple *new_call, gimple *delete_call)
762 : : {
763 : 38518 : tree new_asm = DECL_ASSEMBLER_NAME (gimple_call_fndecl (new_call));
764 : 38518 : tree delete_asm = DECL_ASSEMBLER_NAME (gimple_call_fndecl (delete_call));
765 : 38518 : return valid_new_delete_pair_p (new_asm, delete_asm);
766 : : }
767 : :
768 : : /* Propagate necessity using the operands of necessary statements.
769 : : Process the uses on each statement in the worklist, and add all
770 : : feeding statements which contribute to the calculation of this
771 : : value to the worklist.
772 : :
773 : : In conservative mode, EL is NULL. */
774 : :
775 : : static void
776 : 7642351 : propagate_necessity (bool aggressive)
777 : : {
778 : 7642351 : gimple *stmt;
779 : :
780 : 7642351 : if (dump_file && (dump_flags & TDF_DETAILS))
781 : 207 : fprintf (dump_file, "\nProcessing worklist:\n");
782 : :
783 : 250084058 : while (worklist.length () > 0)
784 : : {
785 : : /* Take STMT from worklist. */
786 : 242441707 : stmt = worklist.pop ();
787 : :
788 : 242441707 : if (dump_file && (dump_flags & TDF_DETAILS))
789 : : {
790 : 1093 : fprintf (dump_file, "processing: ");
791 : 1093 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
792 : 1093 : fprintf (dump_file, "\n");
793 : : }
794 : :
795 : 242441707 : if (aggressive)
796 : : {
797 : : /* Mark the last statement of the basic blocks on which the block
798 : : containing STMT is control dependent, but only if we haven't
799 : : already done so. */
800 : 83546495 : basic_block bb = gimple_bb (stmt);
801 : 83546495 : if (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
802 : 83546495 : && !bitmap_bit_p (visited_control_parents, bb->index))
803 : 17261327 : mark_control_dependent_edges_necessary (bb, false);
804 : : }
805 : :
806 : 242441707 : if (gimple_code (stmt) == GIMPLE_PHI
807 : : /* We do not process virtual PHI nodes nor do we track their
808 : : necessity. */
809 : 278663457 : && !virtual_operand_p (gimple_phi_result (stmt)))
810 : : {
811 : : /* PHI nodes are somewhat special in that each PHI alternative has
812 : : data and control dependencies. All the statements feeding the
813 : : PHI node's arguments are always necessary. In aggressive mode,
814 : : we also consider the control dependent edges leading to the
815 : : predecessor block associated with each PHI alternative as
816 : : necessary. */
817 : 18110875 : gphi *phi = as_a <gphi *> (stmt);
818 : 18110875 : size_t k;
819 : :
820 : 59159071 : for (k = 0; k < gimple_phi_num_args (stmt); k++)
821 : : {
822 : 41048196 : tree arg = PHI_ARG_DEF (stmt, k);
823 : 41048196 : if (TREE_CODE (arg) == SSA_NAME)
824 : 30362781 : mark_operand_necessary (arg);
825 : : }
826 : :
827 : : /* For PHI operands it matters from where the control flow arrives
828 : : to the BB. Consider the following example:
829 : :
830 : : a=exp1;
831 : : b=exp2;
832 : : if (test)
833 : : ;
834 : : else
835 : : ;
836 : : c=PHI(a,b)
837 : :
838 : : We need to mark control dependence of the empty basic blocks, since they
839 : : contains computation of PHI operands.
840 : :
841 : : Doing so is too restrictive in the case the predecestor block is in
842 : : the loop. Consider:
843 : :
844 : : if (b)
845 : : {
846 : : int i;
847 : : for (i = 0; i<1000; ++i)
848 : : ;
849 : : j = 0;
850 : : }
851 : : return j;
852 : :
853 : : There is PHI for J in the BB containing return statement.
854 : : In this case the control dependence of predecestor block (that is
855 : : within the empty loop) also contains the block determining number
856 : : of iterations of the block that would prevent removing of empty
857 : : loop in this case.
858 : :
859 : : This scenario can be avoided by splitting critical edges.
860 : : To save the critical edge splitting pass we identify how the control
861 : : dependence would look like if the edge was split.
862 : :
863 : : Consider the modified CFG created from current CFG by splitting
864 : : edge B->C. In the postdominance tree of modified CFG, C' is
865 : : always child of C. There are two cases how chlids of C' can look
866 : : like:
867 : :
868 : : 1) C' is leaf
869 : :
870 : : In this case the only basic block C' is control dependent on is B.
871 : :
872 : : 2) C' has single child that is B
873 : :
874 : : In this case control dependence of C' is same as control
875 : : dependence of B in original CFG except for block B itself.
876 : : (since C' postdominate B in modified CFG)
877 : :
878 : : Now how to decide what case happens? There are two basic options:
879 : :
880 : : a) C postdominate B. Then C immediately postdominate B and
881 : : case 2 happens iff there is no other way from B to C except
882 : : the edge B->C.
883 : :
884 : : There is other way from B to C iff there is succesor of B that
885 : : is not postdominated by B. Testing this condition is somewhat
886 : : expensive, because we need to iterate all succesors of B.
887 : : We are safe to assume that this does not happen: we will mark B
888 : : as needed when processing the other path from B to C that is
889 : : conrol dependent on B and marking control dependencies of B
890 : : itself is harmless because they will be processed anyway after
891 : : processing control statement in B.
892 : :
893 : : b) C does not postdominate B. Always case 1 happens since there is
894 : : path from C to exit that does not go through B and thus also C'. */
895 : :
896 : 30570061 : if (aggressive && !degenerate_phi_p (stmt))
897 : : {
898 : 18773108 : for (k = 0; k < gimple_phi_num_args (stmt); k++)
899 : : {
900 : 13121419 : basic_block arg_bb = gimple_phi_arg_edge (phi, k)->src;
901 : :
902 : 13121419 : if (gimple_bb (stmt)
903 : 13121419 : != get_immediate_dominator (CDI_POST_DOMINATORS, arg_bb))
904 : : {
905 : 1383899 : if (!mark_last_stmt_necessary (arg_bb))
906 : 2240 : mark_control_dependent_edges_necessary (arg_bb, false);
907 : : }
908 : 11737520 : else if (arg_bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
909 : 11737520 : && !bitmap_bit_p (visited_control_parents,
910 : : arg_bb->index))
911 : 5870261 : mark_control_dependent_edges_necessary (arg_bb, true);
912 : : }
913 : : }
914 : : }
915 : : else
916 : : {
917 : : /* Propagate through the operands. Examine all the USE, VUSE and
918 : : VDEF operands in this statement. Mark all the statements
919 : : which feed this statement's uses as necessary. */
920 : 224330832 : ssa_op_iter iter;
921 : 224330832 : tree use;
922 : :
923 : : /* If this is a call to free which is directly fed by an
924 : : allocation function do not mark that necessary through
925 : : processing the argument. */
926 : 224330832 : bool is_delete_operator
927 : 224330832 : = (is_gimple_call (stmt)
928 : 34972199 : && gimple_call_from_new_or_delete (as_a <gcall *> (stmt))
929 : 225266428 : && gimple_call_operator_delete_p (as_a <gcall *> (stmt)));
930 : 223594236 : if (is_delete_operator
931 : 223594236 : || gimple_call_builtin_p (stmt, BUILT_IN_FREE)
932 : 223322722 : || gimple_call_builtin_p (stmt, BUILT_IN_GOMP_FREE))
933 : : {
934 : 1008110 : tree ptr = gimple_call_arg (stmt, 0);
935 : 1008110 : gcall *def_stmt;
936 : : /* If the pointer we free is defined by an allocation
937 : : function do not add the call to the worklist. */
938 : 1008110 : if (TREE_CODE (ptr) == SSA_NAME
939 : 1007600 : && (def_stmt = dyn_cast <gcall *> (SSA_NAME_DEF_STMT (ptr)))
940 : 1179561 : && is_removable_allocation_p (def_stmt, false))
941 : : {
942 : 151936 : if (is_delete_operator
943 : 151936 : && !valid_new_delete_pair_p (def_stmt, stmt))
944 : 124 : mark_operand_necessary (gimple_call_arg (stmt, 0));
945 : :
946 : : /* Delete operators can have alignment and (or) size
947 : : as next arguments. When being a SSA_NAME, they
948 : : must be marked as necessary. Similarly GOMP_free. */
949 : 151936 : if (gimple_call_num_args (stmt) >= 2)
950 : 62811 : for (unsigned i = 1; i < gimple_call_num_args (stmt);
951 : : i++)
952 : : {
953 : 31414 : tree arg = gimple_call_arg (stmt, i);
954 : 31414 : if (TREE_CODE (arg) == SSA_NAME)
955 : 6637 : mark_operand_necessary (arg);
956 : : }
957 : :
958 : 97362688 : continue;
959 : 151936 : }
960 : : }
961 : :
962 : 224178896 : if (checks_return_value_of_removable_allocation_p (stmt))
963 : 95254 : continue;
964 : :
965 : 419061897 : FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
966 : 194978255 : mark_operand_necessary (use);
967 : :
968 : 224083642 : use = gimple_vuse (stmt);
969 : 194044723 : if (!use)
970 : 91389131 : continue;
971 : :
972 : : /* No need to search for vdefs if we intrinsicly keep them all. */
973 : 132694511 : if (keep_all_vdefs_p ())
974 : 69853 : continue;
975 : :
976 : : /* If we dropped to simple mode make all immediately
977 : : reachable definitions necessary. */
978 : 132624658 : if (chain_ovfl)
979 : : {
980 : 3763569 : mark_all_reaching_defs_necessary (stmt);
981 : 3763569 : continue;
982 : : }
983 : :
984 : : /* For statements that may load from memory (have a VUSE) we
985 : : have to mark all reaching (may-)definitions as necessary.
986 : : We partition this task into two cases:
987 : : 1) explicit loads based on decls that are not aliased
988 : : 2) implicit loads (like calls) and explicit loads not
989 : : based on decls that are not aliased (like indirect
990 : : references or loads from globals)
991 : : For 1) we mark all reaching may-defs as necessary, stopping
992 : : at dominating kills. For 2) we want to mark all dominating
993 : : references necessary, but non-aliased ones which we handle
994 : : in 1). By keeping a global visited bitmap for references
995 : : we walk for 2) we avoid quadratic behavior for those. */
996 : :
997 : 128861089 : if (gcall *call = dyn_cast <gcall *> (stmt))
998 : : {
999 : 31753880 : tree callee = gimple_call_fndecl (call);
1000 : 31753880 : unsigned i;
1001 : :
1002 : 32648563 : if (callee != NULL_TREE
1003 : 30417950 : && (DECL_IS_REPLACEABLE_OPERATOR_NEW_P (callee)
1004 : 30213427 : || DECL_IS_OPERATOR_DELETE_P (callee))
1005 : 32664430 : && gimple_call_from_new_or_delete (call))
1006 : 894683 : continue;
1007 : :
1008 : 30859197 : if (is_removable_cxa_atexit_call (call))
1009 : 0 : continue;
1010 : :
1011 : : bool all_refs = false;
1012 : : /* Calls implicitly load from memory, their arguments
1013 : : in addition may explicitly perform memory loads. */
1014 : 94605778 : for (i = 0; i < gimple_call_num_args (call); ++i)
1015 : : {
1016 : 63746581 : tree arg = gimple_call_arg (call, i);
1017 : 123563037 : if (TREE_CODE (arg) == SSA_NAME
1018 : 63746581 : || is_gimple_min_invariant (arg))
1019 : 59816456 : continue;
1020 : 3930125 : if (TREE_CODE (arg) == WITH_SIZE_EXPR)
1021 : 660 : arg = TREE_OPERAND (arg, 0);
1022 : 3930125 : if (!ref_may_be_aliased (arg))
1023 : 3568352 : mark_aliased_reaching_defs_necessary (call, arg);
1024 : : else
1025 : : all_refs = true;
1026 : : }
1027 : :
1028 : 30859197 : if (!all_refs && ipa_modref_callee_reads_no_memory_p (call))
1029 : 998262 : continue;
1030 : 29860935 : mark_all_reaching_defs_necessary (call);
1031 : : }
1032 : 97107209 : else if (gimple_assign_single_p (stmt))
1033 : : {
1034 : 89486016 : tree rhs;
1035 : : /* If this is a load mark things necessary. */
1036 : 89486016 : rhs = gimple_assign_rhs1 (stmt);
1037 : 89486016 : if (TREE_CODE (rhs) != SSA_NAME
1038 : 72669283 : && !is_gimple_min_invariant (rhs)
1039 : 140544014 : && TREE_CODE (rhs) != CONSTRUCTOR)
1040 : : {
1041 : 41366929 : if (!ref_may_be_aliased (rhs))
1042 : 9068276 : mark_aliased_reaching_defs_necessary (stmt, rhs);
1043 : : else
1044 : 32298653 : mark_all_reaching_defs_necessary (stmt);
1045 : : }
1046 : : }
1047 : 7621193 : else if (greturn *return_stmt = dyn_cast <greturn *> (stmt))
1048 : : {
1049 : 7478052 : tree rhs = gimple_return_retval (return_stmt);
1050 : : /* A return statement may perform a load. */
1051 : 7478052 : if (rhs
1052 : 4157563 : && TREE_CODE (rhs) != SSA_NAME
1053 : 1343912 : && !is_gimple_min_invariant (rhs)
1054 : 8126191 : && TREE_CODE (rhs) != CONSTRUCTOR)
1055 : : {
1056 : 648139 : if (!ref_may_be_aliased (rhs))
1057 : 632148 : mark_aliased_reaching_defs_necessary (stmt, rhs);
1058 : : else
1059 : 15991 : mark_all_reaching_defs_necessary (stmt);
1060 : : }
1061 : : }
1062 : 143141 : else if (gasm *asm_stmt = dyn_cast <gasm *> (stmt))
1063 : : {
1064 : 141957 : unsigned i;
1065 : 141957 : mark_all_reaching_defs_necessary (stmt);
1066 : : /* Inputs may perform loads. */
1067 : 253715 : for (i = 0; i < gimple_asm_ninputs (asm_stmt); ++i)
1068 : : {
1069 : 111758 : tree op = TREE_VALUE (gimple_asm_input_op (asm_stmt, i));
1070 : 111758 : if (TREE_CODE (op) != SSA_NAME
1071 : 73424 : && !is_gimple_min_invariant (op)
1072 : 36383 : && TREE_CODE (op) != CONSTRUCTOR
1073 : 148141 : && !ref_may_be_aliased (op))
1074 : 5539 : mark_aliased_reaching_defs_necessary (stmt, op);
1075 : : }
1076 : : }
1077 : 1184 : else if (gimple_code (stmt) == GIMPLE_TRANSACTION)
1078 : : {
1079 : : /* The beginning of a transaction is a memory barrier. */
1080 : : /* ??? If we were really cool, we'd only be a barrier
1081 : : for the memories touched within the transaction. */
1082 : 1184 : mark_all_reaching_defs_necessary (stmt);
1083 : : }
1084 : : else
1085 : 0 : gcc_unreachable ();
1086 : :
1087 : : /* If we over-used our alias oracle budget drop to simple
1088 : : mode. The cost metric allows quadratic behavior
1089 : : (number of uses times number of may-defs queries) up to
1090 : : a constant maximal number of queries and after that falls back to
1091 : : super-linear complexity. */
1092 : 126968144 : if (/* Constant but quadratic for small functions. */
1093 : 126968144 : total_chain > 128 * 128
1094 : : /* Linear in the number of may-defs. */
1095 : 1101819 : && total_chain > 32 * longest_chain
1096 : : /* Linear in the number of uses. */
1097 : 4737 : && total_chain > nr_walks * 32)
1098 : : {
1099 : 4576 : chain_ovfl = true;
1100 : 4576 : if (visited)
1101 : 4576 : bitmap_clear (visited);
1102 : : }
1103 : : }
1104 : : }
1105 : 7642351 : }
1106 : :
1107 : : /* Remove dead PHI nodes from block BB. */
1108 : :
1109 : : static bool
1110 : 76689020 : remove_dead_phis (basic_block bb)
1111 : : {
1112 : 76689020 : bool something_changed = false;
1113 : 76689020 : gphi *phi;
1114 : 76689020 : gphi_iterator gsi;
1115 : :
1116 : 110601436 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);)
1117 : : {
1118 : 33912416 : stats.total_phis++;
1119 : 33912416 : phi = gsi.phi ();
1120 : :
1121 : : /* We do not track necessity of virtual PHI nodes. Instead do
1122 : : very simple dead PHI removal here. */
1123 : 67824832 : if (virtual_operand_p (gimple_phi_result (phi)))
1124 : : {
1125 : : /* Virtual PHI nodes with one or identical arguments
1126 : : can be removed. */
1127 : 15505752 : if (!loops_state_satisfies_p (LOOP_CLOSED_SSA)
1128 : 15505752 : && degenerate_phi_p (phi))
1129 : : {
1130 : 1814466 : tree vdef = gimple_phi_result (phi);
1131 : 1814466 : tree vuse = gimple_phi_arg_def (phi, 0);
1132 : :
1133 : 1814466 : use_operand_p use_p;
1134 : 1814466 : imm_use_iterator iter;
1135 : 1814466 : gimple *use_stmt;
1136 : 4688289 : FOR_EACH_IMM_USE_STMT (use_stmt, iter, vdef)
1137 : 8719329 : FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
1138 : 4737219 : SET_USE (use_p, vuse);
1139 : 1814466 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vdef)
1140 : 1814466 : && TREE_CODE (vuse) == SSA_NAME)
1141 : 463 : SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vuse) = 1;
1142 : : }
1143 : : else
1144 : 13691286 : gimple_set_plf (phi, STMT_NECESSARY, true);
1145 : : }
1146 : :
1147 : 33912416 : if (!gimple_plf (phi, STMT_NECESSARY))
1148 : : {
1149 : 2110255 : something_changed = true;
1150 : 2110255 : if (dump_file && (dump_flags & TDF_DETAILS))
1151 : : {
1152 : 15 : fprintf (dump_file, "Deleting : ");
1153 : 15 : print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
1154 : 15 : fprintf (dump_file, "\n");
1155 : : }
1156 : :
1157 : 2110255 : remove_phi_node (&gsi, true);
1158 : 2110255 : stats.removed_phis++;
1159 : 2110255 : continue;
1160 : : }
1161 : :
1162 : 31802161 : gsi_next (&gsi);
1163 : : }
1164 : 76689020 : return something_changed;
1165 : : }
1166 : :
1167 : :
1168 : : /* Remove dead statement pointed to by iterator I. Receives the basic block BB
1169 : : containing I so that we don't have to look it up. */
1170 : :
1171 : : static void
1172 : 6028953 : remove_dead_stmt (gimple_stmt_iterator *i, basic_block bb,
1173 : : vec<edge> &to_remove_edges)
1174 : : {
1175 : 6028953 : gimple *stmt = gsi_stmt (*i);
1176 : :
1177 : 6028953 : if (dump_file && (dump_flags & TDF_DETAILS))
1178 : : {
1179 : 108 : fprintf (dump_file, "Deleting : ");
1180 : 108 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1181 : 108 : fprintf (dump_file, "\n");
1182 : : }
1183 : :
1184 : 6028953 : stats.removed++;
1185 : :
1186 : : /* If we have determined that a conditional branch statement contributes
1187 : : nothing to the program, then we not only remove it, but we need to update
1188 : : the CFG. We can chose any of edges out of BB as long as we are sure to not
1189 : : close infinite loops. This is done by always choosing the edge closer to
1190 : : exit in inverted_rev_post_order_compute order. */
1191 : 6028953 : if (is_ctrl_stmt (stmt))
1192 : : {
1193 : 32904 : edge_iterator ei;
1194 : 32904 : edge e = NULL, e2;
1195 : :
1196 : : /* See if there is only one non-abnormal edge. */
1197 : 32904 : if (single_succ_p (bb))
1198 : 3 : e = single_succ_edge (bb);
1199 : : /* Otherwise chose one that is closer to bb with live statement in it.
1200 : : To be able to chose one, we compute inverted post order starting from
1201 : : all BBs with live statements. */
1202 : 3 : if (!e)
1203 : : {
1204 : 32901 : if (!bb_postorder)
1205 : : {
1206 : 18362 : int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
1207 : 18362 : int n = inverted_rev_post_order_compute (cfun, rpo,
1208 : : &bb_contains_live_stmts);
1209 : 18362 : bb_postorder = XNEWVEC (int, last_basic_block_for_fn (cfun));
1210 : 684853 : for (int i = 0; i < n; ++i)
1211 : 666491 : bb_postorder[rpo[i]] = i;
1212 : 18362 : free (rpo);
1213 : : }
1214 : 98709 : FOR_EACH_EDGE (e2, ei, bb->succs)
1215 : 65808 : if (!e || e2->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
1216 : 32907 : || bb_postorder [e->dest->index]
1217 : 32907 : >= bb_postorder [e2->dest->index])
1218 : 51627 : e = e2;
1219 : : }
1220 : 32901 : gcc_assert (e);
1221 : 32904 : e->probability = profile_probability::always ();
1222 : :
1223 : : /* The edge is no longer associated with a conditional, so it does
1224 : : not have TRUE/FALSE flags.
1225 : : We are also safe to drop EH/ABNORMAL flags and turn them into
1226 : : normal control flow, because we know that all the destinations (including
1227 : : those odd edges) are equivalent for program execution. */
1228 : 32904 : e->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE | EDGE_EH | EDGE_ABNORMAL);
1229 : :
1230 : : /* The lone outgoing edge from BB will be a fallthru edge. */
1231 : 32904 : e->flags |= EDGE_FALLTHRU;
1232 : :
1233 : : /* Remove the remaining outgoing edges. */
1234 : 98715 : FOR_EACH_EDGE (e2, ei, bb->succs)
1235 : 65811 : if (e != e2)
1236 : : {
1237 : : /* If we made a BB unconditionally exit a loop or removed
1238 : : an entry into an irreducible region, then this transform
1239 : : alters the set of BBs in the loop. Schedule a fixup. */
1240 : 32907 : if (loop_exit_edge_p (bb->loop_father, e)
1241 : 32907 : || (e2->dest->flags & BB_IRREDUCIBLE_LOOP))
1242 : 18390 : loops_state_set (LOOPS_NEED_FIXUP);
1243 : 32907 : to_remove_edges.safe_push (e2);
1244 : : }
1245 : : }
1246 : :
1247 : : /* If this is a store into a variable that is being optimized away,
1248 : : add a debug bind stmt if possible. */
1249 : 6028953 : if (MAY_HAVE_DEBUG_BIND_STMTS
1250 : 5474339 : && gimple_assign_single_p (stmt)
1251 : 6237594 : && is_gimple_val (gimple_assign_rhs1 (stmt)))
1252 : : {
1253 : 100442 : tree lhs = gimple_assign_lhs (stmt);
1254 : 88427 : if ((VAR_P (lhs) || TREE_CODE (lhs) == PARM_DECL)
1255 : 12080 : && !DECL_IGNORED_P (lhs)
1256 : 3202 : && is_gimple_reg_type (TREE_TYPE (lhs))
1257 : 57 : && !is_global_var (lhs)
1258 : 100499 : && !DECL_HAS_VALUE_EXPR_P (lhs))
1259 : : {
1260 : 57 : tree rhs = gimple_assign_rhs1 (stmt);
1261 : 57 : gdebug *note
1262 : 57 : = gimple_build_debug_bind (lhs, unshare_expr (rhs), stmt);
1263 : 57 : gsi_insert_after (i, note, GSI_SAME_STMT);
1264 : : }
1265 : : }
1266 : :
1267 : 6028953 : unlink_stmt_vdef (stmt);
1268 : 6028953 : gsi_remove (i, true);
1269 : 6028953 : release_defs (stmt);
1270 : 6028953 : }
1271 : :
1272 : : /* Helper for maybe_optimize_arith_overflow. Find in *TP if there are any
1273 : : uses of data (SSA_NAME) other than REALPART_EXPR referencing it. */
1274 : :
1275 : : static tree
1276 : 40 : find_non_realpart_uses (tree *tp, int *walk_subtrees, void *data)
1277 : : {
1278 : 40 : if (TYPE_P (*tp) || TREE_CODE (*tp) == REALPART_EXPR)
1279 : 0 : *walk_subtrees = 0;
1280 : 40 : if (*tp == (tree) data)
1281 : 20 : return *tp;
1282 : : return NULL_TREE;
1283 : : }
1284 : :
1285 : : /* If the IMAGPART_EXPR of the {ADD,SUB,MUL}_OVERFLOW result is never used,
1286 : : but REALPART_EXPR is, optimize the {ADD,SUB,MUL}_OVERFLOW internal calls
1287 : : into plain unsigned {PLUS,MINUS,MULT}_EXPR, and if needed reset debug
1288 : : uses. */
1289 : :
1290 : : static void
1291 : 282887 : maybe_optimize_arith_overflow (gimple_stmt_iterator *gsi,
1292 : : enum tree_code subcode)
1293 : : {
1294 : 282887 : gimple *stmt = gsi_stmt (*gsi);
1295 : 282887 : tree lhs = gimple_call_lhs (stmt);
1296 : :
1297 : 282887 : if (lhs == NULL || TREE_CODE (lhs) != SSA_NAME)
1298 : 282743 : return;
1299 : :
1300 : 282887 : imm_use_iterator imm_iter;
1301 : 282887 : use_operand_p use_p;
1302 : 282887 : bool has_debug_uses = false;
1303 : 282887 : bool has_realpart_uses = false;
1304 : 282887 : bool has_other_uses = false;
1305 : 291156 : FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
1306 : : {
1307 : 291012 : gimple *use_stmt = USE_STMT (use_p);
1308 : 291012 : if (is_gimple_debug (use_stmt))
1309 : : has_debug_uses = true;
1310 : 287115 : else if (is_gimple_assign (use_stmt)
1311 : 287009 : && gimple_assign_rhs_code (use_stmt) == REALPART_EXPR
1312 : 291487 : && TREE_OPERAND (gimple_assign_rhs1 (use_stmt), 0) == lhs)
1313 : : has_realpart_uses = true;
1314 : : else
1315 : : {
1316 : : has_other_uses = true;
1317 : : break;
1318 : : }
1319 : : }
1320 : :
1321 : 282887 : if (!has_realpart_uses || has_other_uses)
1322 : : return;
1323 : :
1324 : 144 : tree arg0 = gimple_call_arg (stmt, 0);
1325 : 144 : tree arg1 = gimple_call_arg (stmt, 1);
1326 : 144 : location_t loc = gimple_location (stmt);
1327 : 144 : tree type = TREE_TYPE (TREE_TYPE (lhs));
1328 : 144 : tree utype = unsigned_type_for (type);
1329 : 144 : tree result = fold_build2_loc (loc, subcode, utype,
1330 : : fold_convert_loc (loc, utype, arg0),
1331 : : fold_convert_loc (loc, utype, arg1));
1332 : 144 : result = fold_convert_loc (loc, type, result);
1333 : :
1334 : 144 : if (has_debug_uses)
1335 : : {
1336 : 20 : gimple *use_stmt;
1337 : 60 : FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, lhs)
1338 : : {
1339 : 40 : if (!gimple_debug_bind_p (use_stmt))
1340 : 20 : continue;
1341 : 20 : tree v = gimple_debug_bind_get_value (use_stmt);
1342 : 20 : if (walk_tree (&v, find_non_realpart_uses, lhs, NULL))
1343 : : {
1344 : 20 : gimple_debug_bind_reset_value (use_stmt);
1345 : 20 : update_stmt (use_stmt);
1346 : : }
1347 : 20 : }
1348 : : }
1349 : :
1350 : 144 : if (TREE_CODE (result) == INTEGER_CST && TREE_OVERFLOW (result))
1351 : 0 : result = drop_tree_overflow (result);
1352 : 144 : tree overflow = build_zero_cst (type);
1353 : 144 : tree ctype = build_complex_type (type);
1354 : 144 : if (TREE_CODE (result) == INTEGER_CST)
1355 : 0 : result = build_complex (ctype, result, overflow);
1356 : : else
1357 : 144 : result = build2_loc (gimple_location (stmt), COMPLEX_EXPR,
1358 : : ctype, result, overflow);
1359 : :
1360 : 144 : if (dump_file && (dump_flags & TDF_DETAILS))
1361 : : {
1362 : 0 : fprintf (dump_file, "Transforming call: ");
1363 : 0 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1364 : 0 : fprintf (dump_file, "because the overflow result is never used into: ");
1365 : 0 : print_generic_stmt (dump_file, result, TDF_SLIM);
1366 : 0 : fprintf (dump_file, "\n");
1367 : : }
1368 : :
1369 : 144 : gimplify_and_update_call_from_tree (gsi, result);
1370 : : }
1371 : :
1372 : : /* Returns whether the control parents of BB are preserved. */
1373 : :
1374 : : static bool
1375 : 605326 : control_parents_preserved_p (basic_block bb)
1376 : : {
1377 : : /* If we marked the control parents from BB they are preserved. */
1378 : 605326 : if (bitmap_bit_p (visited_control_parents, bb->index))
1379 : : return true;
1380 : :
1381 : : /* But they can also end up being marked from elsewhere. */
1382 : 5703 : bitmap_iterator bi;
1383 : 5703 : unsigned edge_number;
1384 : 9009 : EXECUTE_IF_SET_IN_BITMAP (cd->get_edges_dependent_on (bb->index),
1385 : : 0, edge_number, bi)
1386 : : {
1387 : 5790 : basic_block cd_bb = cd->get_edge_src (edge_number);
1388 : 5790 : if (cd_bb != bb
1389 : 5790 : && !bitmap_bit_p (last_stmt_necessary, cd_bb->index))
1390 : : return false;
1391 : : }
1392 : : /* And cache the result. */
1393 : 3219 : bitmap_set_bit (visited_control_parents, bb->index);
1394 : 3219 : return true;
1395 : : }
1396 : :
1397 : : /* Eliminate unnecessary statements. Any instruction not marked as necessary
1398 : : contributes nothing to the program, and can be deleted. */
1399 : :
1400 : : static bool
1401 : 7642351 : eliminate_unnecessary_stmts (bool aggressive)
1402 : : {
1403 : 7642351 : bool something_changed = false;
1404 : 7642351 : basic_block bb;
1405 : 7642351 : gimple_stmt_iterator gsi, psi;
1406 : 7642351 : gimple *stmt;
1407 : 7642351 : auto_vec<edge> to_remove_edges;
1408 : :
1409 : 7642351 : if (dump_file && (dump_flags & TDF_DETAILS))
1410 : 207 : fprintf (dump_file, "\nEliminating unnecessary statements:\n");
1411 : :
1412 : 7642351 : bool had_setjmp = cfun->calls_setjmp;
1413 : 7642351 : clear_special_calls ();
1414 : :
1415 : : /* Walking basic blocks and statements in reverse order avoids
1416 : : releasing SSA names before any other DEFs that refer to them are
1417 : : released. This helps avoid loss of debug information, as we get
1418 : : a chance to propagate all RHSs of removed SSAs into debug uses,
1419 : : rather than only the latest ones. E.g., consider:
1420 : :
1421 : : x_3 = y_1 + z_2;
1422 : : a_5 = x_3 - b_4;
1423 : : # DEBUG a => a_5
1424 : :
1425 : : If we were to release x_3 before a_5, when we reached a_5 and
1426 : : tried to substitute it into the debug stmt, we'd see x_3 there,
1427 : : but x_3's DEF, type, etc would have already been disconnected.
1428 : : By going backwards, the debug stmt first changes to:
1429 : :
1430 : : # DEBUG a => x_3 - b_4
1431 : :
1432 : : and then to:
1433 : :
1434 : : # DEBUG a => y_1 + z_2 - b_4
1435 : :
1436 : : as desired. */
1437 : 7642351 : gcc_assert (dom_info_available_p (CDI_DOMINATORS));
1438 : 7642351 : auto_vec<basic_block> h;
1439 : 7642351 : h = get_all_dominated_blocks (CDI_DOMINATORS,
1440 : 15284702 : single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
1441 : :
1442 : 84331371 : while (h.length ())
1443 : : {
1444 : 76689020 : bb = h.pop ();
1445 : :
1446 : : /* Remove dead statements. */
1447 : 76689020 : auto_bitmap debug_seen;
1448 : 673070838 : for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi = psi)
1449 : : {
1450 : 519692798 : stmt = gsi_stmt (gsi);
1451 : :
1452 : 519692798 : psi = gsi;
1453 : 519692798 : gsi_prev (&psi);
1454 : :
1455 : 519692798 : stats.total++;
1456 : :
1457 : : /* We can mark a call to free as not necessary if the
1458 : : defining statement of its argument is not necessary
1459 : : (and thus is getting removed). */
1460 : 519692798 : if (gimple_plf (stmt, STMT_NECESSARY)
1461 : 519692798 : && (gimple_call_builtin_p (stmt, BUILT_IN_FREE)
1462 : 516887107 : || (is_gimple_call (stmt)
1463 : 34700685 : && gimple_call_from_new_or_delete (as_a <gcall *> (stmt))
1464 : 935596 : && gimple_call_operator_delete_p (as_a <gcall *> (stmt)))))
1465 : : {
1466 : 1008110 : tree ptr = gimple_call_arg (stmt, 0);
1467 : 1008110 : if (TREE_CODE (ptr) == SSA_NAME)
1468 : : {
1469 : 1007600 : gimple *def_stmt = SSA_NAME_DEF_STMT (ptr);
1470 : 1007600 : if (!gimple_nop_p (def_stmt)
1471 : 1007600 : && !gimple_plf (def_stmt, STMT_NECESSARY))
1472 : 5367 : gimple_set_plf (stmt, STMT_NECESSARY, false);
1473 : : }
1474 : : }
1475 : : /* Conditional checking that return value of allocation is non-NULL
1476 : : can be turned to constant if the allocation itself
1477 : : is unnecesary. */
1478 : 519692798 : if (gimple_plf (stmt, STMT_NECESSARY)
1479 : 517153254 : && gimple_code (stmt) == GIMPLE_COND
1480 : 548200259 : && TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME)
1481 : : {
1482 : 28037955 : gimple *def_stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt));
1483 : 28037955 : if (!gimple_nop_p (def_stmt)
1484 : 28037955 : && !gimple_plf (def_stmt, STMT_NECESSARY))
1485 : : {
1486 : 2870 : gcc_checking_assert
1487 : : (checks_return_value_of_removable_allocation_p (stmt));
1488 : 2870 : gimple_cond_set_lhs (as_a <gcond *>(stmt),
1489 : : build_one_cst
1490 : 2870 : (TREE_TYPE (gimple_cond_rhs (stmt))));
1491 : 2870 : update_stmt (stmt);
1492 : : }
1493 : : }
1494 : :
1495 : : /* If GSI is not necessary then remove it. */
1496 : 519692798 : if (!gimple_plf (stmt, STMT_NECESSARY))
1497 : : {
1498 : : /* Keep clobbers that we can keep live live. */
1499 : 2539544 : if (gimple_clobber_p (stmt))
1500 : : {
1501 : 1237018 : ssa_op_iter iter;
1502 : 1237018 : use_operand_p use_p;
1503 : 1237018 : bool dead = false;
1504 : 2471998 : FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1505 : : {
1506 : 1237018 : tree name = USE_FROM_PTR (use_p);
1507 : 1237018 : if (!SSA_NAME_IS_DEFAULT_DEF (name)
1508 : 1237018 : && !bitmap_bit_p (processed, SSA_NAME_VERSION (name)))
1509 : : {
1510 : : dead = true;
1511 : : break;
1512 : : }
1513 : : }
1514 : 2469514 : if (!dead
1515 : : /* When doing CD-DCE we have to ensure all controls
1516 : : of the stmt are still live. */
1517 : 1237018 : && (!aggressive || control_parents_preserved_p (bb)))
1518 : : {
1519 : 1232496 : bitmap_clear (debug_seen);
1520 : 1232496 : continue;
1521 : : }
1522 : : }
1523 : 1307048 : if (!is_gimple_debug (stmt))
1524 : 1062621 : something_changed = true;
1525 : 1307048 : remove_dead_stmt (&gsi, bb, to_remove_edges);
1526 : 1307048 : continue;
1527 : 1307048 : }
1528 : 517153254 : else if (gcall *call_stmt = dyn_cast <gcall *> (stmt))
1529 : : {
1530 : 34966832 : tree name = gimple_call_lhs (call_stmt);
1531 : :
1532 : 34966832 : notice_special_calls (call_stmt);
1533 : :
1534 : : /* When LHS of var = call (); is dead, simplify it into
1535 : : call (); saving one operand. */
1536 : 34966832 : if (name
1537 : 13708655 : && TREE_CODE (name) == SSA_NAME
1538 : 11482491 : && !bitmap_bit_p (processed, SSA_NAME_VERSION (name))
1539 : : /* Avoid doing so for allocation calls which we
1540 : : did not mark as necessary, it will confuse the
1541 : : special logic we apply to malloc/free pair removal. */
1542 : 35051841 : && !is_removable_allocation_p (call_stmt, false))
1543 : : {
1544 : 83764 : something_changed = true;
1545 : 83764 : if (dump_file && (dump_flags & TDF_DETAILS))
1546 : : {
1547 : 0 : fprintf (dump_file, "Deleting LHS of call: ");
1548 : 0 : print_gimple_stmt (dump_file, call_stmt, 0, TDF_SLIM);
1549 : 0 : fprintf (dump_file, "\n");
1550 : : }
1551 : :
1552 : 83764 : gimple_call_set_lhs (call_stmt, NULL_TREE);
1553 : 83764 : maybe_clean_or_replace_eh_stmt (call_stmt, call_stmt);
1554 : 83764 : update_stmt (call_stmt);
1555 : 83764 : release_ssa_name (name);
1556 : :
1557 : : /* GOMP_SIMD_LANE (unless three argument) or ASAN_POISON
1558 : : without lhs is not needed. */
1559 : 83764 : if (gimple_call_internal_p (call_stmt))
1560 : 7665 : switch (gimple_call_internal_fn (call_stmt))
1561 : : {
1562 : 758 : case IFN_GOMP_SIMD_LANE:
1563 : 758 : if (gimple_call_num_args (call_stmt) >= 3
1564 : 796 : && !integer_nonzerop
1565 : 38 : (gimple_call_arg (call_stmt, 2)))
1566 : : break;
1567 : : /* FALLTHRU */
1568 : 859 : case IFN_ASAN_POISON:
1569 : 859 : remove_dead_stmt (&gsi, bb, to_remove_edges);
1570 : 859 : break;
1571 : : default:
1572 : : break;
1573 : : }
1574 : : }
1575 : 34883068 : else if (gimple_call_internal_p (call_stmt))
1576 : 803261 : switch (gimple_call_internal_fn (call_stmt))
1577 : : {
1578 : 86564 : case IFN_ADD_OVERFLOW:
1579 : 86564 : maybe_optimize_arith_overflow (&gsi, PLUS_EXPR);
1580 : 86564 : break;
1581 : 95182 : case IFN_SUB_OVERFLOW:
1582 : 95182 : maybe_optimize_arith_overflow (&gsi, MINUS_EXPR);
1583 : 95182 : break;
1584 : 96767 : case IFN_MUL_OVERFLOW:
1585 : 96767 : maybe_optimize_arith_overflow (&gsi, MULT_EXPR);
1586 : 96767 : break;
1587 : 24160 : case IFN_UADDC:
1588 : 24160 : if (integer_zerop (gimple_call_arg (call_stmt, 2)))
1589 : 2396 : maybe_optimize_arith_overflow (&gsi, PLUS_EXPR);
1590 : : break;
1591 : 13765 : case IFN_USUBC:
1592 : 13765 : if (integer_zerop (gimple_call_arg (call_stmt, 2)))
1593 : 1978 : maybe_optimize_arith_overflow (&gsi, MINUS_EXPR);
1594 : : break;
1595 : : default:
1596 : : break;
1597 : : }
1598 : : }
1599 : 482186422 : else if (gimple_debug_bind_p (stmt))
1600 : : {
1601 : : /* We are only keeping the last debug-bind of a
1602 : : non-DEBUG_EXPR_DECL variable in a series of
1603 : : debug-bind stmts. */
1604 : 215777191 : tree var = gimple_debug_bind_get_var (stmt);
1605 : 215777191 : if (TREE_CODE (var) != DEBUG_EXPR_DECL
1606 : 215777191 : && !bitmap_set_bit (debug_seen, DECL_UID (var)))
1607 : 4721046 : remove_dead_stmt (&gsi, bb, to_remove_edges);
1608 : 215777191 : continue;
1609 : 215777191 : }
1610 : 301376063 : bitmap_clear (debug_seen);
1611 : : }
1612 : :
1613 : : /* Remove dead PHI nodes. */
1614 : 76689020 : something_changed |= remove_dead_phis (bb);
1615 : 76689020 : }
1616 : :
1617 : : /* First remove queued edges. */
1618 : 7642351 : if (!to_remove_edges.is_empty ())
1619 : : {
1620 : : /* Remove edges. We've delayed this to not get bogus debug stmts
1621 : : during PHI node removal. */
1622 : 51269 : for (unsigned i = 0; i < to_remove_edges.length (); ++i)
1623 : 32907 : remove_edge (to_remove_edges[i]);
1624 : 18362 : cfg_altered = true;
1625 : : }
1626 : : /* When we cleared calls_setjmp we can purge all abnormal edges. Do so.
1627 : : ??? We'd like to assert that setjmp calls do not pop out of nothing
1628 : : but we currently lack a per-stmt way of noting whether a call was
1629 : : recognized as returns-twice (or rather receives-control). */
1630 : 7642351 : if (!cfun->calls_setjmp && had_setjmp)
1631 : : {
1632 : : /* Make sure we only remove the edges, not dominated blocks. Using
1633 : : gimple_purge_dead_abnormal_call_edges would do that and we
1634 : : cannot free dominators yet. */
1635 : 3686 : FOR_EACH_BB_FN (bb, cfun)
1636 : 9470 : if (gcall *stmt = safe_dyn_cast <gcall *> (*gsi_last_bb (bb)))
1637 : 2082 : if (!stmt_can_make_abnormal_goto (stmt))
1638 : : {
1639 : 737 : edge_iterator ei;
1640 : 737 : edge e;
1641 : 996 : for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
1642 : : {
1643 : 259 : if (e->flags & EDGE_ABNORMAL)
1644 : : {
1645 : 112 : if (e->flags & EDGE_FALLTHRU)
1646 : 0 : e->flags &= ~EDGE_ABNORMAL;
1647 : : else
1648 : 112 : remove_edge (e);
1649 : 112 : cfg_altered = true;
1650 : : }
1651 : : else
1652 : 147 : ei_next (&ei);
1653 : : }
1654 : : }
1655 : : }
1656 : :
1657 : : /* Now remove the unreachable blocks. */
1658 : 7642351 : if (cfg_altered)
1659 : : {
1660 : 18403 : basic_block prev_bb;
1661 : :
1662 : 18403 : find_unreachable_blocks ();
1663 : :
1664 : : /* Delete all unreachable basic blocks in reverse dominator order. */
1665 : 18403 : for (bb = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb;
1666 : 647214 : bb != ENTRY_BLOCK_PTR_FOR_FN (cfun); bb = prev_bb)
1667 : : {
1668 : 628811 : prev_bb = bb->prev_bb;
1669 : :
1670 : 628811 : if ((bb_contains_live_stmts
1671 : 628765 : && !bitmap_bit_p (bb_contains_live_stmts, bb->index))
1672 : 1093989 : || !(bb->flags & BB_REACHABLE))
1673 : : {
1674 : : /* Since we don't track liveness of virtual PHI nodes, it is
1675 : : possible that we rendered some PHI nodes unreachable while
1676 : : they are still in use. Mark them for renaming. */
1677 : 183395 : for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1678 : 19761 : gsi_next (&gsi))
1679 : 59281 : if (virtual_operand_p (gimple_phi_result (gsi.phi ())))
1680 : : {
1681 : 19759 : bool found = false;
1682 : 19759 : imm_use_iterator iter;
1683 : :
1684 : 19943 : FOR_EACH_IMM_USE_STMT (stmt, iter,
1685 : : gimple_phi_result (gsi.phi ()))
1686 : : {
1687 : 19335 : if (!(gimple_bb (stmt)->flags & BB_REACHABLE))
1688 : 161 : continue;
1689 : 19174 : if (gimple_code (stmt) == GIMPLE_PHI
1690 : 19174 : || gimple_plf (stmt, STMT_NECESSARY))
1691 : : {
1692 : : found = true;
1693 : : break;
1694 : : }
1695 : 19759 : }
1696 : 19759 : if (found)
1697 : 19151 : mark_virtual_phi_result_for_renaming (gsi.phi ());
1698 : : }
1699 : :
1700 : 163634 : if (!(bb->flags & BB_REACHABLE))
1701 : : {
1702 : : /* Speed up the removal of blocks that don't
1703 : : dominate others. Walking backwards, this should
1704 : : be the common case. ??? Do we need to recompute
1705 : : dominators because of cfg_altered? */
1706 : 35880 : if (!first_dom_son (CDI_DOMINATORS, bb))
1707 : 35389 : delete_basic_block (bb);
1708 : : else
1709 : : {
1710 : 491 : h = get_all_dominated_blocks (CDI_DOMINATORS, bb);
1711 : :
1712 : 2143 : while (h.length ())
1713 : : {
1714 : 1652 : bb = h.pop ();
1715 : 1652 : prev_bb = bb->prev_bb;
1716 : : /* Rearrangements to the CFG may have failed
1717 : : to update the dominators tree, so that
1718 : : formerly-dominated blocks are now
1719 : : otherwise reachable. */
1720 : 1652 : if (!!(bb->flags & BB_REACHABLE))
1721 : 0 : continue;
1722 : 1652 : delete_basic_block (bb);
1723 : : }
1724 : :
1725 : 491 : h.release ();
1726 : : }
1727 : : }
1728 : : }
1729 : : }
1730 : : }
1731 : :
1732 : 7642351 : if (bb_postorder)
1733 : 18362 : free (bb_postorder);
1734 : 7642351 : bb_postorder = NULL;
1735 : :
1736 : 7642351 : return something_changed;
1737 : 7642351 : }
1738 : :
1739 : :
1740 : : /* Print out removed statement statistics. */
1741 : :
1742 : : static void
1743 : 213 : print_stats (void)
1744 : : {
1745 : 213 : float percg;
1746 : :
1747 : 213 : percg = ((float) stats.removed / (float) stats.total) * 100;
1748 : 213 : fprintf (dump_file, "Removed %d of %d statements (%d%%)\n",
1749 : : stats.removed, stats.total, (int) percg);
1750 : :
1751 : 213 : if (stats.total_phis == 0)
1752 : : percg = 0;
1753 : : else
1754 : 38 : percg = ((float) stats.removed_phis / (float) stats.total_phis) * 100;
1755 : :
1756 : 213 : fprintf (dump_file, "Removed %d of %d PHI nodes (%d%%)\n",
1757 : : stats.removed_phis, stats.total_phis, (int) percg);
1758 : 213 : }
1759 : :
1760 : : /* Initialization for this pass. Set up the used data structures. */
1761 : :
1762 : : static void
1763 : 7642351 : tree_dce_init (bool aggressive)
1764 : : {
1765 : 7642351 : memset ((void *) &stats, 0, sizeof (stats));
1766 : :
1767 : 7642351 : if (aggressive)
1768 : : {
1769 : 3274513 : last_stmt_necessary = sbitmap_alloc (last_basic_block_for_fn (cfun));
1770 : 3274513 : bitmap_clear (last_stmt_necessary);
1771 : 3274513 : bb_contains_live_stmts = sbitmap_alloc (last_basic_block_for_fn (cfun));
1772 : 3274513 : bitmap_clear (bb_contains_live_stmts);
1773 : : }
1774 : :
1775 : 15284702 : processed = sbitmap_alloc (num_ssa_names + 1);
1776 : 7642351 : bitmap_clear (processed);
1777 : :
1778 : 7642351 : worklist.create (64);
1779 : 7642351 : cfg_altered = false;
1780 : 7642351 : }
1781 : :
1782 : : /* Cleanup after this pass. */
1783 : :
1784 : : static void
1785 : 7642351 : tree_dce_done (bool aggressive)
1786 : : {
1787 : 7642351 : if (aggressive)
1788 : : {
1789 : 3274513 : delete cd;
1790 : 3274513 : sbitmap_free (visited_control_parents);
1791 : 3274513 : sbitmap_free (last_stmt_necessary);
1792 : 3274513 : sbitmap_free (bb_contains_live_stmts);
1793 : 3274513 : bb_contains_live_stmts = NULL;
1794 : : }
1795 : :
1796 : 7642351 : sbitmap_free (processed);
1797 : :
1798 : 7642351 : worklist.release ();
1799 : 7642351 : }
1800 : :
1801 : : /* Sort PHI argument values for make_forwarders_with_degenerate_phis. */
1802 : :
1803 : : static int
1804 : 26844728 : sort_phi_args (const void *a_, const void *b_)
1805 : : {
1806 : 26844728 : auto *a = (const std::pair<edge, hashval_t> *) a_;
1807 : 26844728 : auto *b = (const std::pair<edge, hashval_t> *) b_;
1808 : 26844728 : hashval_t ha = a->second;
1809 : 26844728 : hashval_t hb = b->second;
1810 : 26844728 : if (ha < hb)
1811 : : return -1;
1812 : 16688964 : else if (ha > hb)
1813 : : return 1;
1814 : 8097510 : else if (a->first->dest_idx < b->first->dest_idx)
1815 : : return -1;
1816 : 4246448 : else if (a->first->dest_idx > b->first->dest_idx)
1817 : : return 1;
1818 : : else
1819 : 0 : return 0;
1820 : : }
1821 : :
1822 : : /* Look for a non-virtual PHIs and make a forwarder block when all PHIs
1823 : : have the same argument on a set of edges. This is to not consider
1824 : : control dependences of individual edges for same values but only for
1825 : : the common set. */
1826 : :
1827 : : static unsigned
1828 : 3274513 : make_forwarders_with_degenerate_phis (function *fn)
1829 : : {
1830 : 3274513 : unsigned todo = 0;
1831 : :
1832 : 3274513 : basic_block bb;
1833 : 31146151 : FOR_EACH_BB_FN (bb, fn)
1834 : : {
1835 : : /* Only PHIs with three or more arguments have opportunities. */
1836 : 27871638 : if (EDGE_COUNT (bb->preds) < 3)
1837 : 27591197 : continue;
1838 : : /* Do not touch loop headers or blocks with abnormal predecessors.
1839 : : ??? This is to avoid creating valid loops here, see PR103458.
1840 : : We might want to improve things to either explicitely add those
1841 : : loops or at least consider blocks with no backedges. */
1842 : 1153219 : if (bb->loop_father->header == bb
1843 : 1151393 : || bb_has_abnormal_pred (bb))
1844 : 1826 : continue;
1845 : :
1846 : : /* Take one PHI node as template to look for identical
1847 : : arguments. Build a vector of candidates forming sets
1848 : : of argument edges with equal values. Note optimality
1849 : : depends on the particular choice of the template PHI
1850 : : since equal arguments are unordered leaving other PHIs
1851 : : with more than one set of equal arguments within this
1852 : : argument range unsorted. We'd have to break ties by
1853 : : looking at other PHI nodes. */
1854 : 1149567 : gphi_iterator gsi = gsi_start_nonvirtual_phis (bb);
1855 : 1149567 : if (gsi_end_p (gsi))
1856 : 697605 : continue;
1857 : 451962 : gphi *phi = gsi.phi ();
1858 : 451962 : auto_vec<std::pair<edge, hashval_t>, 8> args;
1859 : 451962 : bool need_resort = false;
1860 : 2657986 : for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
1861 : : {
1862 : 2206024 : edge e = gimple_phi_arg_edge (phi, i);
1863 : : /* Skip abnormal edges since we cannot redirect them. */
1864 : 2206024 : if (e->flags & EDGE_ABNORMAL)
1865 : 2206024 : continue;
1866 : : /* Skip loop exit edges when we are in loop-closed SSA form
1867 : : since the forwarder we'd create does not have a PHI node. */
1868 : 2206024 : if (loops_state_satisfies_p (LOOP_CLOSED_SSA)
1869 : 2206024 : && loop_exit_edge_p (e->src->loop_father, e))
1870 : 16359 : continue;
1871 : :
1872 : 2189665 : tree arg = gimple_phi_arg_def (phi, i);
1873 : 2189665 : if (!CONSTANT_CLASS_P (arg) && TREE_CODE (arg) != SSA_NAME)
1874 : 2189665 : need_resort = true;
1875 : 2189665 : args.safe_push (std::make_pair (e, iterative_hash_expr (arg, 0)));
1876 : : }
1877 : 451962 : if (args.length () < 2)
1878 : 3713 : continue;
1879 : 448249 : args.qsort (sort_phi_args);
1880 : : /* The above sorting can be different between -g and -g0, as e.g. decls
1881 : : can have different uids (-g could have bigger gaps in between them).
1882 : : So, only use that to determine which args are equal, then change
1883 : : second from hash value to smallest dest_idx of the edges which have
1884 : : equal argument and sort again. If all the phi arguments are
1885 : : constants or SSA_NAME, there is no need for the second sort, the hash
1886 : : values are stable in that case. */
1887 : 448249 : hashval_t hash = args[0].second;
1888 : 448249 : args[0].second = args[0].first->dest_idx;
1889 : 448249 : bool any_equal = false;
1890 : 2187351 : for (unsigned i = 1; i < args.length (); ++i)
1891 : 1739102 : if (hash == args[i].second
1892 : 2426382 : && operand_equal_p (PHI_ARG_DEF_FROM_EDGE (phi, args[i - 1].first),
1893 : 687280 : PHI_ARG_DEF_FROM_EDGE (phi, args[i].first)))
1894 : : {
1895 : 686896 : args[i].second = args[i - 1].second;
1896 : 686896 : any_equal = true;
1897 : : }
1898 : : else
1899 : : {
1900 : 1052206 : hash = args[i].second;
1901 : 1052206 : args[i].second = args[i].first->dest_idx;
1902 : : }
1903 : 448249 : if (!any_equal)
1904 : 167808 : continue;
1905 : 280441 : if (need_resort)
1906 : 12308 : args.qsort (sort_phi_args);
1907 : :
1908 : : /* From the candidates vector now verify true candidates for
1909 : : forwarders and create them. */
1910 : 280441 : gphi *vphi = get_virtual_phi (bb);
1911 : 280441 : unsigned start = 0;
1912 : 2246877 : while (start < args.length () - 1)
1913 : : {
1914 : 707852 : unsigned i;
1915 : 2134636 : for (i = start + 1; i < args.length (); ++i)
1916 : 1980162 : if (args[start].second != args[i].second)
1917 : : break;
1918 : : /* args[start]..args[i-1] are equal. */
1919 : 707852 : if (start != i - 1)
1920 : : {
1921 : : /* Check all PHI nodes for argument equality. */
1922 : 414728 : bool equal = true;
1923 : 414728 : gphi_iterator gsi2 = gsi;
1924 : 414728 : gsi_next (&gsi2);
1925 : 881615 : for (; !gsi_end_p (gsi2); gsi_next (&gsi2))
1926 : : {
1927 : 620840 : gphi *phi2 = gsi2.phi ();
1928 : 1241680 : if (virtual_operand_p (gimple_phi_result (phi2)))
1929 : 153237 : continue;
1930 : 467603 : tree start_arg
1931 : 467603 : = PHI_ARG_DEF_FROM_EDGE (phi2, args[start].first);
1932 : 2171556 : for (unsigned j = start + 1; j < i; ++j)
1933 : : {
1934 : 3777766 : if (!operand_equal_p (start_arg,
1935 : 1888883 : PHI_ARG_DEF_FROM_EDGE
1936 : : (phi2, args[j].first)))
1937 : : {
1938 : : /* Another PHI might have a shorter set of
1939 : : equivalent args. Go for that. */
1940 : 184930 : i = j;
1941 : 184930 : if (j == start + 1)
1942 : : equal = false;
1943 : : break;
1944 : : }
1945 : : }
1946 : : if (!equal)
1947 : : break;
1948 : : }
1949 : 414728 : if (equal)
1950 : : {
1951 : : /* If we are asked to forward all edges the block
1952 : : has all degenerate PHIs. Do nothing in that case. */
1953 : 260775 : if (start == 0
1954 : 131195 : && i == args.length ()
1955 : 266000 : && args.length () == gimple_phi_num_args (phi))
1956 : : break;
1957 : : /* Instead of using make_forwarder_block we are
1958 : : rolling our own variant knowing that the forwarder
1959 : : does not need PHI nodes apart from eventually
1960 : : a virtual one. */
1961 : 255700 : auto_vec<tree, 8> vphi_args;
1962 : 255700 : if (vphi)
1963 : : {
1964 : 160734 : vphi_args.reserve_exact (i - start);
1965 : 635181 : for (unsigned j = start; j < i; ++j)
1966 : 474447 : vphi_args.quick_push
1967 : 474447 : (PHI_ARG_DEF_FROM_EDGE (vphi, args[j].first));
1968 : : }
1969 : 255700 : free_dominance_info (fn, CDI_DOMINATORS);
1970 : 255700 : basic_block forwarder = split_edge (args[start].first);
1971 : 255700 : profile_count count = profile_count::zero ();
1972 : 769281 : for (unsigned j = start + 1; j < i; ++j)
1973 : : {
1974 : 513581 : edge e = args[j].first;
1975 : 513581 : redirect_edge_and_branch_force (e, forwarder);
1976 : 513581 : redirect_edge_var_map_clear (e);
1977 : 513581 : count += e->count ();
1978 : : }
1979 : 255700 : forwarder->count = count;
1980 : 255700 : if (vphi)
1981 : : {
1982 : 160734 : tree def = copy_ssa_name (vphi_args[0]);
1983 : 160734 : gphi *vphi_copy = create_phi_node (def, forwarder);
1984 : 635181 : for (unsigned j = start; j < i; ++j)
1985 : 948894 : add_phi_arg (vphi_copy, vphi_args[j - start],
1986 : 474447 : args[j].first, UNKNOWN_LOCATION);
1987 : 160734 : SET_PHI_ARG_DEF
1988 : : (vphi, single_succ_edge (forwarder)->dest_idx, def);
1989 : : }
1990 : 255700 : todo |= TODO_cleanup_cfg;
1991 : 255700 : }
1992 : : }
1993 : : /* Continue searching for more opportunities. */
1994 : : start = i;
1995 : : }
1996 : 451962 : }
1997 : 3274513 : return todo;
1998 : : }
1999 : :
2000 : : /* Main routine to eliminate dead code.
2001 : :
2002 : : AGGRESSIVE controls the aggressiveness of the algorithm.
2003 : : In conservative mode, we ignore control dependence and simply declare
2004 : : all but the most trivially dead branches necessary. This mode is fast.
2005 : : In aggressive mode, control dependences are taken into account, which
2006 : : results in more dead code elimination, but at the cost of some time. */
2007 : :
2008 : : static unsigned int
2009 : 7642351 : perform_tree_ssa_dce (bool aggressive)
2010 : : {
2011 : 7642351 : bool something_changed = 0;
2012 : 7642351 : unsigned todo = 0;
2013 : :
2014 : : /* Preheaders are needed for SCEV to work.
2015 : : Simple lateches and recorded exits improve chances that loop will
2016 : : proved to be finite in testcases such as in loop-15.c and loop-24.c */
2017 : 7642351 : bool in_loop_pipeline = scev_initialized_p ();
2018 : 7642351 : if (aggressive && ! in_loop_pipeline)
2019 : : {
2020 : 3063673 : loop_optimizer_init (LOOPS_NORMAL
2021 : : | LOOPS_HAVE_RECORDED_EXITS);
2022 : 3063673 : scev_initialize ();
2023 : : }
2024 : :
2025 : 7642351 : if (aggressive)
2026 : 3274513 : todo |= make_forwarders_with_degenerate_phis (cfun);
2027 : :
2028 : 7642351 : calculate_dominance_info (CDI_DOMINATORS);
2029 : :
2030 : 7642351 : tree_dce_init (aggressive);
2031 : :
2032 : 7642351 : if (aggressive)
2033 : : {
2034 : : /* Compute control dependence. */
2035 : 3274513 : calculate_dominance_info (CDI_POST_DOMINATORS);
2036 : 3274513 : cd = new control_dependences ();
2037 : :
2038 : 6549026 : visited_control_parents =
2039 : 3274513 : sbitmap_alloc (last_basic_block_for_fn (cfun));
2040 : 3274513 : bitmap_clear (visited_control_parents);
2041 : :
2042 : 3274513 : mark_dfs_back_edges ();
2043 : : }
2044 : :
2045 : 7642351 : find_obviously_necessary_stmts (aggressive);
2046 : :
2047 : 7642351 : if (aggressive && ! in_loop_pipeline)
2048 : : {
2049 : 3063673 : scev_finalize ();
2050 : 3063673 : loop_optimizer_finalize ();
2051 : : }
2052 : :
2053 : 7642351 : longest_chain = 0;
2054 : 7642351 : total_chain = 0;
2055 : 7642351 : nr_walks = 0;
2056 : 7642351 : chain_ovfl = false;
2057 : 7642351 : visited = BITMAP_ALLOC (NULL);
2058 : 7642351 : propagate_necessity (aggressive);
2059 : 7642351 : BITMAP_FREE (visited);
2060 : :
2061 : 7642351 : something_changed |= eliminate_unnecessary_stmts (aggressive);
2062 : 7642351 : something_changed |= cfg_altered;
2063 : :
2064 : : /* We do not update postdominators, so free them unconditionally. */
2065 : 7642351 : free_dominance_info (CDI_POST_DOMINATORS);
2066 : :
2067 : : /* If we removed paths in the CFG, then we need to update
2068 : : dominators as well. I haven't investigated the possibility
2069 : : of incrementally updating dominators. */
2070 : 7642351 : if (cfg_altered)
2071 : 18403 : free_dominance_info (CDI_DOMINATORS);
2072 : :
2073 : 7642351 : statistics_counter_event (cfun, "Statements deleted", stats.removed);
2074 : 7642351 : statistics_counter_event (cfun, "PHI nodes deleted", stats.removed_phis);
2075 : :
2076 : : /* Debugging dumps. */
2077 : 7642351 : if (dump_file && (dump_flags & (TDF_STATS|TDF_DETAILS)))
2078 : 213 : print_stats ();
2079 : :
2080 : 7642351 : tree_dce_done (aggressive);
2081 : :
2082 : 7642351 : if (something_changed)
2083 : : {
2084 : 777242 : free_numbers_of_iterations_estimates (cfun);
2085 : 777242 : if (in_loop_pipeline)
2086 : 59218 : scev_reset ();
2087 : : todo |= TODO_update_ssa | TODO_cleanup_cfg;
2088 : : }
2089 : 7642351 : return todo;
2090 : : }
2091 : :
2092 : : namespace {
2093 : :
2094 : : const pass_data pass_data_dce =
2095 : : {
2096 : : GIMPLE_PASS, /* type */
2097 : : "dce", /* name */
2098 : : OPTGROUP_NONE, /* optinfo_flags */
2099 : : TV_TREE_DCE, /* tv_id */
2100 : : ( PROP_cfg | PROP_ssa ), /* properties_required */
2101 : : 0, /* properties_provided */
2102 : : 0, /* properties_destroyed */
2103 : : 0, /* todo_flags_start */
2104 : : 0, /* todo_flags_finish */
2105 : : };
2106 : :
2107 : : class pass_dce_base : public gimple_opt_pass
2108 : : {
2109 : : public:
2110 : : /* opt_pass methods: */
2111 : 7645367 : bool gate (function *) final override { return flag_tree_dce != 0; }
2112 : 2801140 : void set_pass_param (unsigned n, bool param) final override
2113 : : {
2114 : 2801140 : gcc_assert (n == 0 || n == 1);
2115 : 2801140 : if (n == 0)
2116 : 1680684 : update_address_taken_p = param;
2117 : 1120456 : else if (n == 1)
2118 : 1120456 : remove_unused_locals_p = param;
2119 : 2801140 : }
2120 : :
2121 : : protected:
2122 : 3081254 : pass_dce_base (const pass_data &data, gcc::context *ctxt)
2123 : 6162508 : : gimple_opt_pass (data, ctxt)
2124 : : {}
2125 : 7642351 : unsigned int execute_dce (function *, bool aggressive)
2126 : : {
2127 : 7642351 : return (perform_tree_ssa_dce (aggressive)
2128 : 7642351 : | (remove_unused_locals_p ? TODO_remove_unused_locals : 0)
2129 : 7642351 : | (update_address_taken_p ? TODO_update_address_taken : 0));
2130 : : }
2131 : :
2132 : : private:
2133 : : bool update_address_taken_p = false;
2134 : : bool remove_unused_locals_p = false;
2135 : : }; // class pass_dce_base
2136 : :
2137 : :
2138 : : class pass_dce : public pass_dce_base
2139 : : {
2140 : : public:
2141 : 2240912 : pass_dce (gcc::context *ctxt)
2142 : 4481824 : : pass_dce_base (pass_data_dce, ctxt)
2143 : : {}
2144 : :
2145 : : /* opt_pass methods: */
2146 : 1960798 : opt_pass * clone () final override { return new pass_dce (m_ctxt); }
2147 : 4182401 : unsigned int execute (function *func) final override
2148 : : {
2149 : 4182401 : return execute_dce (func, /*aggressive=*/false);
2150 : : }
2151 : :
2152 : : }; // class pass_dce
2153 : :
2154 : : } // anon namespace
2155 : :
2156 : : gimple_opt_pass *
2157 : 280114 : make_pass_dce (gcc::context *ctxt)
2158 : : {
2159 : 280114 : return new pass_dce (ctxt);
2160 : : }
2161 : :
2162 : : namespace {
2163 : :
2164 : : const pass_data pass_data_cd_dce =
2165 : : {
2166 : : GIMPLE_PASS, /* type */
2167 : : "cddce", /* name */
2168 : : OPTGROUP_NONE, /* optinfo_flags */
2169 : : TV_TREE_CD_DCE, /* tv_id */
2170 : : ( PROP_cfg | PROP_ssa ), /* properties_required */
2171 : : 0, /* properties_provided */
2172 : : 0, /* properties_destroyed */
2173 : : 0, /* todo_flags_start */
2174 : : 0, /* todo_flags_finish */
2175 : : };
2176 : :
2177 : : class pass_cd_dce : public pass_dce_base
2178 : : {
2179 : : public:
2180 : 840342 : pass_cd_dce (gcc::context *ctxt)
2181 : 1680684 : : pass_dce_base (pass_data_cd_dce, ctxt)
2182 : : {}
2183 : :
2184 : : /* opt_pass methods: */
2185 : 560228 : opt_pass * clone () final override { return new pass_cd_dce (m_ctxt); }
2186 : 3459950 : unsigned int execute (function *func) final override
2187 : : {
2188 : 3459950 : return execute_dce (func, /*aggressive=*/optimize >= 2);
2189 : : }
2190 : :
2191 : : }; // class pass_cd_dce
2192 : :
2193 : : } // anon namespace
2194 : :
2195 : : gimple_opt_pass *
2196 : 280114 : make_pass_cd_dce (gcc::context *ctxt)
2197 : : {
2198 : 280114 : return new pass_cd_dce (ctxt);
2199 : : }
2200 : :
2201 : :
2202 : : /* A cheap DCE interface. WORKLIST is a list of possibly dead stmts and
2203 : : is consumed by this function. The function has linear complexity in
2204 : : the number of dead stmts with a constant factor like the average SSA
2205 : : use operands number. */
2206 : :
2207 : : void
2208 : 35576036 : simple_dce_from_worklist (bitmap worklist, bitmap need_eh_cleanup)
2209 : : {
2210 : 35576036 : int phiremoved = 0;
2211 : 35576036 : int stmtremoved = 0;
2212 : 69367123 : while (! bitmap_empty_p (worklist))
2213 : : {
2214 : : /* Pop item. */
2215 : 33791087 : unsigned i = bitmap_clear_first_set_bit (worklist);
2216 : :
2217 : 33791087 : tree def = ssa_name (i);
2218 : : /* Removed by somebody else or still in use.
2219 : : Note use in itself for a phi node is not counted as still in use. */
2220 : 33791087 : if (!def)
2221 : 15282119 : continue;
2222 : 33653319 : if (!has_zero_uses (def))
2223 : : {
2224 : 15104441 : gimple *def_stmt = SSA_NAME_DEF_STMT (def);
2225 : :
2226 : 15104441 : if (gimple_code (def_stmt) != GIMPLE_PHI)
2227 : 15100527 : continue;
2228 : :
2229 : 2809602 : gimple *use_stmt;
2230 : 2809602 : imm_use_iterator use_iter;
2231 : 2809602 : bool canremove = true;
2232 : :
2233 : 2900478 : FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, def)
2234 : : {
2235 : : /* Ignore debug statements. */
2236 : 2896564 : if (is_gimple_debug (use_stmt))
2237 : 83302 : continue;
2238 : 2813262 : if (use_stmt != def_stmt)
2239 : : {
2240 : : canremove = false;
2241 : : break;
2242 : : }
2243 : 2809602 : }
2244 : 2809602 : if (!canremove)
2245 : 2805688 : continue;
2246 : : }
2247 : :
2248 : 18552792 : gimple *t = SSA_NAME_DEF_STMT (def);
2249 : 18552792 : if (gimple_has_side_effects (t))
2250 : 35352 : continue;
2251 : :
2252 : : /* The defining statement needs to be defining only this name.
2253 : : ASM is the only statement that can define more than one
2254 : : name. */
2255 : 18517440 : if (is_a<gasm *>(t)
2256 : 18517440 : && !single_ssa_def_operand (t, SSA_OP_ALL_DEFS))
2257 : 15 : continue;
2258 : :
2259 : : /* Don't remove statements that are needed for non-call
2260 : : eh to work. */
2261 : 18517425 : if (stmt_unremovable_because_of_non_call_eh_p (cfun, t))
2262 : 8457 : continue;
2263 : :
2264 : : /* Tell the caller that we removed a statement that might
2265 : : throw so it could cleanup the cfg for that block. */
2266 : 18508968 : if (need_eh_cleanup && stmt_could_throw_p (cfun, t))
2267 : 278 : bitmap_set_bit (need_eh_cleanup, gimple_bb (t)->index);
2268 : :
2269 : : /* Add uses to the worklist. */
2270 : 18508968 : ssa_op_iter iter;
2271 : 18508968 : use_operand_p use_p;
2272 : 52430725 : FOR_EACH_PHI_OR_STMT_USE (use_p, t, iter, SSA_OP_USE)
2273 : : {
2274 : 15412789 : tree use = USE_FROM_PTR (use_p);
2275 : 15412789 : if (TREE_CODE (use) == SSA_NAME
2276 : 15412789 : && ! SSA_NAME_IS_DEFAULT_DEF (use))
2277 : 13745794 : bitmap_set_bit (worklist, SSA_NAME_VERSION (use));
2278 : : }
2279 : :
2280 : : /* Remove stmt. */
2281 : 18508968 : if (dump_file && (dump_flags & TDF_DETAILS))
2282 : : {
2283 : 272 : fprintf (dump_file, "Removing dead stmt:");
2284 : 272 : print_gimple_stmt (dump_file, t, 0);
2285 : : }
2286 : 18508968 : gimple_stmt_iterator gsi = gsi_for_stmt (t);
2287 : 18508968 : if (gimple_code (t) == GIMPLE_PHI)
2288 : : {
2289 : 2564012 : remove_phi_node (&gsi, true);
2290 : 2564012 : phiremoved++;
2291 : : }
2292 : : else
2293 : : {
2294 : 15944956 : unlink_stmt_vdef (t);
2295 : 15944956 : gsi_remove (&gsi, true);
2296 : 15944956 : release_defs (t);
2297 : 15944956 : stmtremoved++;
2298 : : }
2299 : : }
2300 : 35576036 : statistics_counter_event (cfun, "PHIs removed",
2301 : : phiremoved);
2302 : 35576036 : statistics_counter_event (cfun, "Statements removed",
2303 : : stmtremoved);
2304 : 35576036 : }
|
