Branch data Line data Source code
1 : : /* Dead code elimination pass for the GNU compiler.
2 : : Copyright (C) 2002-2025 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 : 270878791 : keep_all_vdefs_p ()
125 : : {
126 : 270878791 : 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 : 85757332 : is_cxa_atexit (const_tree callee)
135 : : {
136 : 85757332 : if (callee != NULL_TREE
137 : 85757332 : && strcmp (IDENTIFIER_POINTER (DECL_NAME (callee)), "__cxa_atexit") == 0)
138 : : return 1;
139 : 85643914 : if (callee != NULL_TREE
140 : 85643914 : && 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 : 85757332 : is_removable_cxa_atexit_call (gimple *stmt)
151 : : {
152 : 85757332 : tree callee = gimple_call_fndecl (stmt);
153 : 85757332 : int functype = is_cxa_atexit (callee);
154 : 85757332 : if (!functype)
155 : : return false;
156 : 113418 : 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 : 226836 : tree arg = gimple_call_arg (stmt, functype == 2 ? 1 : 0);
162 : 113418 : if (TREE_CODE (arg) != ADDR_EXPR)
163 : : return false;
164 : 113418 : arg = TREE_OPERAND (arg, 0);
165 : 113418 : if (TREE_CODE (arg) != FUNCTION_DECL)
166 : : return false;
167 : 113418 : int flags = flags_from_decl_or_type (arg);
168 : :
169 : : /* If the function is noreturn then it cannot be removed. */
170 : 113418 : if (flags & ECF_NORETURN)
171 : : return false;
172 : :
173 : : /* The function needs to be const or pure and non looping. */
174 : 113260 : return (flags & (ECF_CONST|ECF_PURE))
175 : 113260 : && !(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 : 459441791 : mark_stmt_necessary (gimple *stmt, bool add_to_worklist)
183 : : {
184 : 459441791 : gcc_assert (stmt);
185 : :
186 : 459441791 : if (gimple_plf (stmt, STMT_NECESSARY))
187 : : return;
188 : :
189 : 459441603 : if (dump_file && (dump_flags & TDF_DETAILS))
190 : : {
191 : 856 : fprintf (dump_file, "Marking useful stmt: ");
192 : 856 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
193 : 856 : fprintf (dump_file, "\n");
194 : : }
195 : :
196 : 459441603 : gimple_set_plf (stmt, STMT_NECESSARY, true);
197 : 459441603 : if (add_to_worklist)
198 : 106683201 : worklist.safe_push (stmt);
199 : 106683201 : if (add_to_worklist && bb_contains_live_stmts && !is_gimple_debug (stmt))
200 : 37258432 : 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 : 337794215 : mark_operand_necessary (tree op)
208 : : {
209 : 337794215 : gimple *stmt;
210 : 337794215 : int ver;
211 : :
212 : 337794215 : gcc_assert (op);
213 : :
214 : 337794215 : ver = SSA_NAME_VERSION (op);
215 : 337794215 : if (bitmap_bit_p (processed, ver))
216 : : {
217 : 122783665 : stmt = SSA_NAME_DEF_STMT (op);
218 : 122783665 : gcc_assert (gimple_nop_p (stmt)
219 : : || gimple_plf (stmt, STMT_NECESSARY));
220 : 183140690 : return;
221 : : }
222 : 215010550 : bitmap_set_bit (processed, ver);
223 : :
224 : 215010550 : stmt = SSA_NAME_DEF_STMT (op);
225 : 215010550 : gcc_assert (stmt);
226 : :
227 : 215010550 : if (gimple_plf (stmt, STMT_NECESSARY) || gimple_nop_p (stmt))
228 : : return;
229 : :
230 : 154653525 : if (dump_file && (dump_flags & TDF_DETAILS))
231 : : {
232 : 270 : fprintf (dump_file, "marking necessary through ");
233 : 270 : print_generic_expr (dump_file, op);
234 : 270 : fprintf (dump_file, " stmt ");
235 : 270 : print_gimple_stmt (dump_file, stmt, 0);
236 : : }
237 : :
238 : 154653525 : gimple_set_plf (stmt, STMT_NECESSARY, true);
239 : 154653525 : if (bb_contains_live_stmts)
240 : 52916316 : bitmap_set_bit (bb_contains_live_stmts, gimple_bb (stmt)->index);
241 : 154653525 : 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 : : than NULL pointer check or free.
247 : : If NON_NULL_CHECK is false, we can further assume that return value
248 : : is never checked to be non-NULL.
249 : : Don't return true if it is called with constant size (or sizes for calloc)
250 : : and the size is excessively large (larger than PTRDIFF_MAX, for calloc
251 : : either argument larger than PTRDIFF_MAX or both constant and their product
252 : : larger than PTRDIFF_MAX). */
253 : :
254 : : static bool
255 : 35531241 : is_removable_allocation_p (gcall *stmt, bool non_null_check)
256 : : {
257 : 35531241 : int arg = -1;
258 : 35531241 : tree callee = gimple_call_fndecl (stmt), a1, a2;
259 : 35531241 : if (callee != NULL_TREE
260 : 35531241 : && fndecl_built_in_p (callee, BUILT_IN_NORMAL))
261 : 8905036 : switch (DECL_FUNCTION_CODE (callee))
262 : : {
263 : 520153 : case BUILT_IN_MALLOC:
264 : 520153 : arg = 1;
265 : 520153 : goto do_malloc;
266 : 150 : case BUILT_IN_ALIGNED_ALLOC:
267 : 150 : arg = 2;
268 : 150 : goto do_malloc;
269 : 5287 : case BUILT_IN_CALLOC:
270 : 5287 : arg = 3;
271 : 5287 : goto do_malloc;
272 : 127199 : CASE_BUILT_IN_ALLOCA:
273 : 127199 : arg = 1;
274 : 127199 : goto do_malloc;
275 : : case BUILT_IN_STRDUP:
276 : : case BUILT_IN_STRNDUP:
277 : : arg = 0;
278 : : /* FALLTHRU */
279 : 656986 : do_malloc:
280 : 656986 : if (non_null_check)
281 : : {
282 : 101929 : if (flag_malloc_dce <= 1)
283 : : return false;
284 : : }
285 : 555057 : else if (!flag_malloc_dce)
286 : : return false;
287 : : break;
288 : :
289 : : case BUILT_IN_GOMP_ALLOC:
290 : 35531004 : arg = 2;
291 : : break;
292 : :
293 : : default:;
294 : : }
295 : :
296 : 35531004 : if (arg == -1
297 : 35531004 : && callee != NULL_TREE
298 : 32648600 : && flag_allocation_dce
299 : 32645176 : && gimple_call_from_new_or_delete (stmt)
300 : 36642856 : && DECL_IS_REPLACEABLE_OPERATOR_NEW_P (callee))
301 : : arg = 1;
302 : :
303 : 35251835 : switch (arg)
304 : : {
305 : : case -1:
306 : : return false;
307 : : case 0:
308 : : return true;
309 : 931493 : case 1:
310 : 931493 : case 2:
311 : 931493 : if (gimple_call_num_args (stmt) < (unsigned) arg)
312 : : return false;
313 : 931487 : a1 = gimple_call_arg (stmt, arg - 1);
314 : 931487 : if (tree_fits_uhwi_p (a1)
315 : 931487 : && (tree_to_uhwi (a1)
316 : 524228 : > tree_to_uhwi (TYPE_MAX_VALUE (ptrdiff_type_node))))
317 : : return false;
318 : : return true;
319 : 5287 : case 3:
320 : 5287 : if (gimple_call_num_args (stmt) < 2)
321 : : return false;
322 : 5287 : a1 = gimple_call_arg (stmt, 0);
323 : 5287 : a2 = gimple_call_arg (stmt, 1);
324 : 5287 : if (tree_fits_uhwi_p (a1)
325 : 5287 : && (tree_to_uhwi (a1)
326 : 4311 : > tree_to_uhwi (TYPE_MAX_VALUE (ptrdiff_type_node))))
327 : : return false;
328 : 5265 : if (tree_fits_uhwi_p (a2)
329 : 5265 : && (tree_to_uhwi (a2)
330 : 4460 : > tree_to_uhwi (TYPE_MAX_VALUE (ptrdiff_type_node))))
331 : : return false;
332 : 10486 : if (TREE_CODE (a1) == INTEGER_CST
333 : 4279 : && TREE_CODE (a2) == INTEGER_CST
334 : 12817 : && (wi::to_widest (a1) * wi::to_widest (a2)
335 : 12817 : > tree_to_uhwi (TYPE_MAX_VALUE (ptrdiff_type_node))))
336 : : return false;
337 : : return true;
338 : : default:
339 : : gcc_unreachable ();
340 : : }
341 : : }
342 : :
343 : : /* Return true if STMT is a conditional
344 : : if (ptr != NULL)
345 : : where ptr was returned by a removable allocation function. */
346 : :
347 : : static bool
348 : 241066719 : checks_return_value_of_removable_allocation_p (gimple *stmt)
349 : : {
350 : 241066719 : gcall *def_stmt;
351 : 241066719 : return gimple_code (stmt) == GIMPLE_COND
352 : 31339647 : && (gimple_cond_code (stmt) == EQ_EXPR
353 : 21792946 : || gimple_cond_code (stmt) == NE_EXPR)
354 : 23950343 : && integer_zerop (gimple_cond_rhs (stmt))
355 : 13133745 : && TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME
356 : : && (def_stmt = dyn_cast <gcall *>
357 : 13130872 : (SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt))))
358 : 244308182 : && is_removable_allocation_p (def_stmt, true);
359 : : }
360 : :
361 : :
362 : : /* Mark STMT as necessary if it obviously is. Add it to the worklist if
363 : : it can make other statements necessary.
364 : :
365 : : If AGGRESSIVE is false, control statements are conservatively marked as
366 : : necessary. */
367 : :
368 : : static void
369 : 596415883 : mark_stmt_if_obviously_necessary (gimple *stmt, bool aggressive)
370 : : {
371 : : /* Statements that are implicitly live. Most function calls, asm
372 : : and return statements are required. Labels and GIMPLE_BIND nodes
373 : : are kept because they are control flow, and we have no way of
374 : : knowing whether they can be removed. DCE can eliminate all the
375 : : other statements in a block, and CFG can then remove the block
376 : : and labels. */
377 : 596415883 : switch (gimple_code (stmt))
378 : : {
379 : 7160013 : case GIMPLE_PREDICT:
380 : 7160013 : case GIMPLE_LABEL:
381 : 7160013 : mark_stmt_necessary (stmt, false);
382 : 7160013 : return;
383 : :
384 : 10108627 : case GIMPLE_ASM:
385 : 10108627 : case GIMPLE_RESX:
386 : 10108627 : case GIMPLE_RETURN:
387 : 10108627 : mark_stmt_necessary (stmt, true);
388 : 10108627 : return;
389 : :
390 : 37187308 : case GIMPLE_CALL:
391 : 37187308 : {
392 : 37187308 : gcall *call = as_a <gcall *> (stmt);
393 : :
394 : : /* Never elide a noreturn call we pruned control-flow for.
395 : : Same for statements that can alter control flow in unpredictable
396 : : ways. */
397 : 37187308 : if (gimple_call_ctrl_altering_p (call))
398 : : {
399 : 5180284 : mark_stmt_necessary (call, true);
400 : 5180284 : return;
401 : : }
402 : :
403 : 32007024 : if (is_removable_allocation_p (call, false))
404 : : return;
405 : :
406 : :
407 : : /* For __cxa_atexit calls, don't mark as necessary right away. */
408 : 31341822 : if (is_removable_cxa_atexit_call (call))
409 : : return;
410 : :
411 : : /* IFN_GOACC_LOOP calls are necessary in that they are used to
412 : : represent parameter (i.e. step, bound) of a lowered OpenACC
413 : : partitioned loop. But this kind of partitioned loop might not
414 : : survive from aggressive loop removal for it has loop exit and
415 : : is assumed to be finite. Therefore, we need to explicitly mark
416 : : these calls. (An example is libgomp.oacc-c-c++-common/pr84955.c) */
417 : 31341415 : if (gimple_call_internal_p (call, IFN_GOACC_LOOP))
418 : : {
419 : 27029 : mark_stmt_necessary (call, true);
420 : 27029 : return;
421 : : }
422 : : break;
423 : : }
424 : :
425 : 345903187 : case GIMPLE_DEBUG:
426 : : /* Debug temps without a value are not useful. ??? If we could
427 : : easily locate the debug temp bind stmt for a use thereof,
428 : : would could refrain from marking all debug temps here, and
429 : : mark them only if they're used. */
430 : 345903187 : if (gimple_debug_nonbind_marker_p (stmt)
431 : 265815356 : || !gimple_debug_bind_p (stmt)
432 : 264908737 : || gimple_debug_bind_has_value_p (stmt)
433 : 464584183 : || TREE_CODE (gimple_debug_bind_get_var (stmt)) != DEBUG_EXPR_DECL)
434 : 345598389 : mark_stmt_necessary (stmt, false);
435 : : return;
436 : :
437 : 1875 : case GIMPLE_GOTO:
438 : 1875 : gcc_assert (!simple_goto_p (stmt));
439 : 1875 : mark_stmt_necessary (stmt, true);
440 : 1875 : return;
441 : :
442 : 31378836 : case GIMPLE_COND:
443 : 31378836 : gcc_assert (EDGE_COUNT (gimple_bb (stmt)->succs) == 2);
444 : : /* Fall through. */
445 : :
446 : 31559044 : case GIMPLE_SWITCH:
447 : 31559044 : if (! aggressive)
448 : 20976443 : mark_stmt_necessary (stmt, true);
449 : : break;
450 : :
451 : 164457834 : case GIMPLE_ASSIGN:
452 : : /* Mark indirect CLOBBERs to be lazily removed if their SSA operands
453 : : do not prevail. That also makes control flow leading to them
454 : : not necessary in aggressive mode. */
455 : 174779947 : if (gimple_clobber_p (stmt) && !zero_ssa_operands (stmt, SSA_OP_USE))
456 : : return;
457 : : break;
458 : :
459 : : default:
460 : : break;
461 : : }
462 : :
463 : : /* If the statement has volatile operands, it needs to be preserved.
464 : : Same for statements that can alter control flow in unpredictable
465 : : ways. */
466 : 226504540 : if (gimple_has_side_effects (stmt) || is_ctrl_altering_stmt (stmt))
467 : : {
468 : 40810997 : mark_stmt_necessary (stmt, true);
469 : 40810997 : return;
470 : : }
471 : :
472 : : /* If a statement could throw, it can be deemed necessary unless we
473 : : are allowed to remove dead EH. Test this after checking for
474 : : new/delete operators since we always elide their EH. */
475 : 185693543 : if (!cfun->can_delete_dead_exceptions
476 : 185693543 : && stmt_could_throw_p (cfun, stmt))
477 : : {
478 : 5602665 : mark_stmt_necessary (stmt, true);
479 : 5602665 : return;
480 : : }
481 : :
482 : 224614643 : if ((gimple_vdef (stmt) && keep_all_vdefs_p ())
483 : 224595300 : || stmt_may_clobber_global_p (stmt, false))
484 : : {
485 : 13434985 : mark_stmt_necessary (stmt, true);
486 : 13434985 : return;
487 : : }
488 : :
489 : : return;
490 : : }
491 : :
492 : :
493 : : /* Mark the last statement of BB as necessary. */
494 : :
495 : : static bool
496 : 43495046 : mark_last_stmt_necessary (basic_block bb)
497 : : {
498 : 43495046 : if (!bitmap_set_bit (last_stmt_necessary, bb->index))
499 : : return true;
500 : :
501 : 16991843 : bitmap_set_bit (bb_contains_live_stmts, bb->index);
502 : :
503 : : /* We actually mark the statement only if it is a control statement. */
504 : 16991843 : gimple *stmt = *gsi_last_bb (bb);
505 : 16991843 : if (stmt && is_ctrl_stmt (stmt))
506 : : {
507 : 10540484 : mark_stmt_necessary (stmt, true);
508 : 10540484 : return true;
509 : : }
510 : : return false;
511 : : }
512 : :
513 : :
514 : : /* Mark control dependent edges of BB as necessary. We have to do this only
515 : : once for each basic block so we set the appropriate bit after we're done.
516 : :
517 : : When IGNORE_SELF is true, ignore BB in the list of control dependences. */
518 : :
519 : : static void
520 : 32073222 : mark_control_dependent_edges_necessary (basic_block bb, bool ignore_self)
521 : : {
522 : 32073222 : bitmap_iterator bi;
523 : 32073222 : unsigned edge_number;
524 : 32073222 : bool skipped = false;
525 : :
526 : 32073222 : gcc_assert (bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
527 : :
528 : 32073222 : if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
529 : 3543521 : return;
530 : :
531 : 70486107 : EXECUTE_IF_SET_IN_BITMAP (cd->get_edges_dependent_on (bb->index),
532 : : 0, edge_number, bi)
533 : : {
534 : 41956406 : basic_block cd_bb = cd->get_edge_src (edge_number);
535 : :
536 : 41956406 : if (ignore_self && cd_bb == bb)
537 : : {
538 : 68080 : skipped = true;
539 : 68080 : continue;
540 : : }
541 : :
542 : 41888326 : if (!mark_last_stmt_necessary (cd_bb))
543 : 6449019 : mark_control_dependent_edges_necessary (cd_bb, false);
544 : : }
545 : :
546 : 28529701 : if (!skipped)
547 : 28461621 : bitmap_set_bit (visited_control_parents, bb->index);
548 : : }
549 : :
550 : :
551 : : /* Find obviously necessary statements. These are things like most function
552 : : calls, and stores to file level variables.
553 : :
554 : : If EL is NULL, control statements are conservatively marked as
555 : : necessary. Otherwise it contains the list of edges used by control
556 : : dependence analysis. */
557 : :
558 : : static void
559 : 8096455 : find_obviously_necessary_stmts (bool aggressive)
560 : : {
561 : 8096455 : basic_block bb;
562 : 8096455 : gimple_stmt_iterator gsi;
563 : 8096455 : edge e;
564 : 8096455 : gimple *phi, *stmt;
565 : 8096455 : int flags;
566 : :
567 : 91870753 : FOR_EACH_BB_FN (bb, cfun)
568 : : {
569 : : /* PHI nodes are never inherently necessary. */
570 : 121215403 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
571 : : {
572 : 37441105 : phi = gsi_stmt (gsi);
573 : 37441105 : gimple_set_plf (phi, STMT_NECESSARY, false);
574 : : }
575 : :
576 : : /* Check all statements in the block. */
577 : 763964479 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
578 : : {
579 : 596415883 : stmt = gsi_stmt (gsi);
580 : 596415883 : gimple_set_plf (stmt, STMT_NECESSARY, false);
581 : 596415883 : mark_stmt_if_obviously_necessary (stmt, aggressive);
582 : : }
583 : : }
584 : :
585 : : /* Pure and const functions are finite and thus have no infinite loops in
586 : : them. */
587 : 8096455 : flags = flags_from_decl_or_type (current_function_decl);
588 : 8096455 : if ((flags & (ECF_CONST|ECF_PURE)) && !(flags & ECF_LOOPING_CONST_OR_PURE))
589 : 934067 : return;
590 : :
591 : : /* Prevent the empty possibly infinite loops from being removed. This is
592 : : needed to make the logic in remove_dead_stmt work to identify the
593 : : correct edge to keep when removing a controlling condition. */
594 : 7162388 : if (aggressive)
595 : : {
596 : 3358923 : if (mark_irreducible_loops ())
597 : 289314 : FOR_EACH_BB_FN (bb, cfun)
598 : : {
599 : 283709 : edge_iterator ei;
600 : 715071 : FOR_EACH_EDGE (e, ei, bb->succs)
601 : 431362 : if ((e->flags & EDGE_DFS_BACK)
602 : 28002 : && (e->flags & EDGE_IRREDUCIBLE_LOOP))
603 : : {
604 : 10924 : if (dump_file)
605 : 0 : fprintf (dump_file, "Marking back edge of irreducible "
606 : 0 : "loop %i->%i\n", e->src->index, e->dest->index);
607 : 10924 : mark_control_dependent_edges_necessary (e->dest, false);
608 : : }
609 : : }
610 : :
611 : 11871466 : for (auto loop : loops_list (cfun, 0))
612 : : /* For loops without an exit do not mark any condition. */
613 : 1794697 : if (loop->exits->next->e && !finite_loop_p (loop))
614 : : {
615 : 283676 : if (dump_file)
616 : 1 : fprintf (dump_file, "cannot prove finiteness of loop %i\n",
617 : : loop->num);
618 : 283676 : mark_control_dependent_edges_necessary (loop->latch, false);
619 : 3358923 : }
620 : : }
621 : : }
622 : :
623 : :
624 : : /* Return true if REF is based on an aliased base, otherwise false. */
625 : :
626 : : static bool
627 : 97846285 : ref_may_be_aliased (tree ref)
628 : : {
629 : 97846285 : if (TREE_CODE (ref) == WITH_SIZE_EXPR)
630 : 0 : ref = TREE_OPERAND (ref, 0);
631 : 175472593 : while (handled_component_p (ref))
632 : 77626308 : ref = TREE_OPERAND (ref, 0);
633 : 97846285 : if ((TREE_CODE (ref) == MEM_REF || TREE_CODE (ref) == TARGET_MEM_REF)
634 : 97846285 : && TREE_CODE (TREE_OPERAND (ref, 0)) == ADDR_EXPR)
635 : 15609418 : ref = TREE_OPERAND (TREE_OPERAND (ref, 0), 0);
636 : 97846285 : return !(DECL_P (ref)
637 : 65562879 : && !may_be_aliased (ref));
638 : : }
639 : :
640 : : static bitmap visited = NULL;
641 : : static unsigned int longest_chain = 0;
642 : : static unsigned int total_chain = 0;
643 : : static unsigned int nr_walks = 0;
644 : : static bool chain_ovfl = false;
645 : :
646 : : /* Worker for the walker that marks reaching definitions of REF,
647 : : which is based on a non-aliased decl, necessary. It returns
648 : : true whenever the defining statement of the current VDEF is
649 : : a kill for REF, as no dominating may-defs are necessary for REF
650 : : anymore. DATA points to the basic-block that contains the
651 : : stmt that refers to REF. */
652 : :
653 : : static bool
654 : 39804274 : mark_aliased_reaching_defs_necessary_1 (ao_ref *ref, tree vdef, void *data)
655 : : {
656 : 39804274 : gimple *def_stmt = SSA_NAME_DEF_STMT (vdef);
657 : :
658 : : /* All stmts we visit are necessary. */
659 : 39804274 : if (! gimple_clobber_p (def_stmt))
660 : 39608110 : mark_operand_necessary (vdef);
661 : :
662 : : /* If the stmt lhs kills ref, then we can stop walking. */
663 : 39804274 : if (gimple_has_lhs (def_stmt)
664 : 29442689 : && TREE_CODE (gimple_get_lhs (def_stmt)) != SSA_NAME
665 : : /* The assignment is not necessarily carried out if it can throw
666 : : and we can catch it in the current function where we could inspect
667 : : the previous value.
668 : : ??? We only need to care about the RHS throwing. For aggregate
669 : : assignments or similar calls and non-call exceptions the LHS
670 : : might throw as well. */
671 : 37932600 : && !stmt_can_throw_internal (cfun, def_stmt))
672 : : {
673 : 25206633 : tree base, lhs = gimple_get_lhs (def_stmt);
674 : 25206633 : poly_int64 size, offset, max_size;
675 : 25206633 : bool reverse;
676 : 25206633 : ao_ref_base (ref);
677 : 25206633 : base
678 : 25206633 : = get_ref_base_and_extent (lhs, &offset, &size, &max_size, &reverse);
679 : : /* We can get MEM[symbol: sZ, index: D.8862_1] here,
680 : : so base == refd->base does not always hold. */
681 : 25206633 : if (base == ref->base)
682 : : {
683 : : /* For a must-alias check we need to be able to constrain
684 : : the accesses properly. */
685 : 23218236 : if (known_eq (size, max_size)
686 : 23218236 : && known_subrange_p (ref->offset, ref->max_size, offset, size))
687 : 8780984 : return true;
688 : : /* Or they need to be exactly the same. */
689 : 14438207 : else if (ref->ref
690 : : /* Make sure there is no induction variable involved
691 : : in the references (gcc.c-torture/execute/pr42142.c).
692 : : The simplest way is to check if the kill dominates
693 : : the use. */
694 : : /* But when both are in the same block we cannot
695 : : easily tell whether we came from a backedge
696 : : unless we decide to compute stmt UIDs
697 : : (see PR58246). */
698 : 14438207 : && (basic_block) data != gimple_bb (def_stmt)
699 : 6830250 : && dominated_by_p (CDI_DOMINATORS, (basic_block) data,
700 : 6830250 : gimple_bb (def_stmt))
701 : 18624277 : && operand_equal_p (ref->ref, lhs, 0))
702 : : return true;
703 : : }
704 : : }
705 : :
706 : : /* Otherwise keep walking. */
707 : : return false;
708 : : }
709 : :
710 : : static void
711 : 13780622 : mark_aliased_reaching_defs_necessary (gimple *stmt, tree ref)
712 : : {
713 : : /* Should have been caught before calling this function. */
714 : 13780622 : gcc_checking_assert (!keep_all_vdefs_p ());
715 : :
716 : 13780622 : unsigned int chain;
717 : 13780622 : ao_ref refd;
718 : 13780622 : gcc_assert (!chain_ovfl);
719 : 13780622 : ao_ref_init (&refd, ref);
720 : 27561244 : chain = walk_aliased_vdefs (&refd, gimple_vuse (stmt),
721 : : mark_aliased_reaching_defs_necessary_1,
722 : 13780622 : gimple_bb (stmt), NULL);
723 : 13780622 : if (chain > longest_chain)
724 : 2305968 : longest_chain = chain;
725 : 13780622 : total_chain += chain;
726 : 13780622 : nr_walks++;
727 : 13780622 : }
728 : :
729 : : /* Worker for the walker that marks reaching definitions of REF, which
730 : : is not based on a non-aliased decl. For simplicity we need to end
731 : : up marking all may-defs necessary that are not based on a non-aliased
732 : : decl. The only job of this walker is to skip may-defs based on
733 : : a non-aliased decl. */
734 : :
735 : : static bool
736 : 75021353 : mark_all_reaching_defs_necessary_1 (ao_ref *ref ATTRIBUTE_UNUSED,
737 : : tree vdef, void *data ATTRIBUTE_UNUSED)
738 : : {
739 : 75021353 : gimple *def_stmt = SSA_NAME_DEF_STMT (vdef);
740 : :
741 : : /* We have to skip already visited (and thus necessary) statements
742 : : to make the chaining work after we dropped back to simple mode. */
743 : 75021353 : if (chain_ovfl
744 : 75021353 : && bitmap_bit_p (processed, SSA_NAME_VERSION (vdef)))
745 : : {
746 : 2681582 : gcc_assert (gimple_nop_p (def_stmt)
747 : : || gimple_plf (def_stmt, STMT_NECESSARY));
748 : : return false;
749 : : }
750 : :
751 : : /* We want to skip stores to non-aliased variables. */
752 : 72339771 : if (!chain_ovfl
753 : 72339771 : && gimple_assign_single_p (def_stmt))
754 : : {
755 : 48404684 : tree lhs = gimple_assign_lhs (def_stmt);
756 : 48404684 : if (!ref_may_be_aliased (lhs))
757 : : return false;
758 : : }
759 : :
760 : : /* We want to skip statments that do not constitute stores but have
761 : : a virtual definition. */
762 : 59990814 : if (gcall *call = dyn_cast <gcall *> (def_stmt))
763 : : {
764 : 23091909 : tree callee = gimple_call_fndecl (call);
765 : 23091909 : if (callee != NULL_TREE
766 : 23091909 : && fndecl_built_in_p (callee, BUILT_IN_NORMAL))
767 : 3999914 : switch (DECL_FUNCTION_CODE (callee))
768 : : {
769 : : case BUILT_IN_MALLOC:
770 : : case BUILT_IN_ALIGNED_ALLOC:
771 : : case BUILT_IN_CALLOC:
772 : : CASE_BUILT_IN_ALLOCA:
773 : : case BUILT_IN_STRDUP:
774 : : case BUILT_IN_STRNDUP:
775 : : case BUILT_IN_FREE:
776 : : case BUILT_IN_GOMP_ALLOC:
777 : : case BUILT_IN_GOMP_FREE:
778 : : return false;
779 : :
780 : : default:;
781 : : }
782 : :
783 : 22460844 : if (callee != NULL_TREE
784 : 21121301 : && (DECL_IS_REPLACEABLE_OPERATOR_NEW_P (callee)
785 : 20903419 : || DECL_IS_OPERATOR_DELETE_P (callee))
786 : 23237207 : && gimple_call_from_new_or_delete (call))
787 : : return false;
788 : 21696458 : if (is_removable_cxa_atexit_call (call))
789 : : return false;
790 : : }
791 : :
792 : 58595175 : if (! gimple_clobber_p (def_stmt))
793 : 53745757 : mark_operand_necessary (vdef);
794 : :
795 : : return false;
796 : : }
797 : :
798 : : static void
799 : 70569237 : mark_all_reaching_defs_necessary (gimple *stmt)
800 : : {
801 : : /* Should have been caught before calling this function. */
802 : 70569237 : gcc_checking_assert (!keep_all_vdefs_p ());
803 : 141138474 : walk_aliased_vdefs (NULL, gimple_vuse (stmt),
804 : : mark_all_reaching_defs_necessary_1, NULL, &visited);
805 : 70569237 : }
806 : :
807 : : /* Return true for PHI nodes with one or identical arguments
808 : : can be removed. */
809 : : static bool
810 : 20192963 : degenerate_phi_p (gimple *phi)
811 : : {
812 : 20192963 : unsigned int i;
813 : 20192963 : tree op = gimple_phi_arg_def (phi, 0);
814 : 21266636 : for (i = 1; i < gimple_phi_num_args (phi); i++)
815 : 18372777 : if (gimple_phi_arg_def (phi, i) != op)
816 : : return false;
817 : : return true;
818 : : }
819 : :
820 : : /* Return that NEW_CALL and DELETE_CALL are a valid pair of new
821 : : and delete operators. */
822 : :
823 : : static bool
824 : 49032 : valid_new_delete_pair_p (gimple *new_call, gimple *delete_call)
825 : : {
826 : 49032 : tree new_asm = DECL_ASSEMBLER_NAME (gimple_call_fndecl (new_call));
827 : 49032 : tree delete_asm = DECL_ASSEMBLER_NAME (gimple_call_fndecl (delete_call));
828 : 49032 : return valid_new_delete_pair_p (new_asm, delete_asm);
829 : : }
830 : :
831 : : /* Propagate necessity using the operands of necessary statements.
832 : : Process the uses on each statement in the worklist, and add all
833 : : feeding statements which contribute to the calculation of this
834 : : value to the worklist.
835 : :
836 : : In conservative mode, EL is NULL. */
837 : :
838 : : static void
839 : 8096455 : propagate_necessity (bool aggressive)
840 : : {
841 : 8096455 : gimple *stmt;
842 : :
843 : 8096455 : if (dump_file && (dump_flags & TDF_DETAILS))
844 : 209 : fprintf (dump_file, "\nProcessing worklist:\n");
845 : :
846 : 269433181 : while (worklist.length () > 0)
847 : : {
848 : : /* Take STMT from worklist. */
849 : 261336726 : stmt = worklist.pop ();
850 : :
851 : 261336726 : if (dump_file && (dump_flags & TDF_DETAILS))
852 : : {
853 : 1107 : fprintf (dump_file, "processing: ");
854 : 1107 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
855 : 1107 : fprintf (dump_file, "\n");
856 : : }
857 : :
858 : 261336726 : if (aggressive)
859 : : {
860 : : /* Mark the last statement of the basic blocks on which the block
861 : : containing STMT is control dependent, but only if we haven't
862 : : already done so. */
863 : 90174748 : basic_block bb = gimple_bb (stmt);
864 : 90174748 : if (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
865 : 90174748 : && !bitmap_bit_p (visited_control_parents, bb->index))
866 : 18863358 : mark_control_dependent_edges_necessary (bb, false);
867 : : }
868 : :
869 : 261336726 : if (gimple_code (stmt) == GIMPLE_PHI
870 : : /* We do not process virtual PHI nodes nor do we track their
871 : : necessity. */
872 : 301543418 : && !virtual_operand_p (gimple_phi_result (stmt)))
873 : : {
874 : : /* PHI nodes are somewhat special in that each PHI alternative has
875 : : data and control dependencies. All the statements feeding the
876 : : PHI node's arguments are always necessary. In aggressive mode,
877 : : we also consider the control dependent edges leading to the
878 : : predecessor block associated with each PHI alternative as
879 : : necessary. */
880 : 20103346 : gphi *phi = as_a <gphi *> (stmt);
881 : 20103346 : size_t k;
882 : :
883 : 65598972 : for (k = 0; k < gimple_phi_num_args (stmt); k++)
884 : : {
885 : 45495626 : tree arg = PHI_ARG_DEF (stmt, k);
886 : 45495626 : if (TREE_CODE (arg) == SSA_NAME)
887 : 33761311 : mark_operand_necessary (arg);
888 : : }
889 : :
890 : : /* For PHI operands it matters from where the control flow arrives
891 : : to the BB. Consider the following example:
892 : :
893 : : a=exp1;
894 : : b=exp2;
895 : : if (test)
896 : : ;
897 : : else
898 : : ;
899 : : c=PHI(a,b)
900 : :
901 : : We need to mark control dependence of the empty basic blocks, since they
902 : : contains computation of PHI operands.
903 : :
904 : : Doing so is too restrictive in the case the predecestor block is in
905 : : the loop. Consider:
906 : :
907 : : if (b)
908 : : {
909 : : int i;
910 : : for (i = 0; i<1000; ++i)
911 : : ;
912 : : j = 0;
913 : : }
914 : : return j;
915 : :
916 : : There is PHI for J in the BB containing return statement.
917 : : In this case the control dependence of predecestor block (that is
918 : : within the empty loop) also contains the block determining number
919 : : of iterations of the block that would prevent removing of empty
920 : : loop in this case.
921 : :
922 : : This scenario can be avoided by splitting critical edges.
923 : : To save the critical edge splitting pass we identify how the control
924 : : dependence would look like if the edge was split.
925 : :
926 : : Consider the modified CFG created from current CFG by splitting
927 : : edge B->C. In the postdominance tree of modified CFG, C' is
928 : : always child of C. There are two cases how chlids of C' can look
929 : : like:
930 : :
931 : : 1) C' is leaf
932 : :
933 : : In this case the only basic block C' is control dependent on is B.
934 : :
935 : : 2) C' has single child that is B
936 : :
937 : : In this case control dependence of C' is same as control
938 : : dependence of B in original CFG except for block B itself.
939 : : (since C' postdominate B in modified CFG)
940 : :
941 : : Now how to decide what case happens? There are two basic options:
942 : :
943 : : a) C postdominate B. Then C immediately postdominate B and
944 : : case 2 happens iff there is no other way from B to C except
945 : : the edge B->C.
946 : :
947 : : There is other way from B to C iff there is succesor of B that
948 : : is not postdominated by B. Testing this condition is somewhat
949 : : expensive, because we need to iterate all succesors of B.
950 : : We are safe to assume that this does not happen: we will mark B
951 : : as needed when processing the other path from B to C that is
952 : : conrol dependent on B and marking control dependencies of B
953 : : itself is harmless because they will be processed anyway after
954 : : processing control statement in B.
955 : :
956 : : b) C does not postdominate B. Always case 1 happens since there is
957 : : path from C to exit that does not go through B and thus also C'. */
958 : :
959 : 33963511 : if (aggressive && !degenerate_phi_p (stmt))
960 : : {
961 : 20728833 : for (k = 0; k < gimple_phi_num_args (stmt); k++)
962 : : {
963 : 14485652 : basic_block arg_bb = gimple_phi_arg_edge (phi, k)->src;
964 : :
965 : 14485652 : if (gimple_bb (stmt)
966 : 14485652 : != get_immediate_dominator (CDI_POST_DOMINATORS, arg_bb))
967 : : {
968 : 1606720 : if (!mark_last_stmt_necessary (arg_bb))
969 : 2340 : mark_control_dependent_edges_necessary (arg_bb, false);
970 : : }
971 : 12878932 : else if (arg_bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
972 : 12878932 : && !bitmap_bit_p (visited_control_parents,
973 : : arg_bb->index))
974 : 6463905 : mark_control_dependent_edges_necessary (arg_bb, true);
975 : : }
976 : : }
977 : : }
978 : : else
979 : : {
980 : : /* Propagate through the operands. Examine all the USE, VUSE and
981 : : VDEF operands in this statement. Mark all the statements
982 : : which feed this statement's uses as necessary. */
983 : 241233380 : ssa_op_iter iter;
984 : 241233380 : tree use;
985 : :
986 : : /* If this is a call to free which is directly fed by an
987 : : allocation function do not mark that necessary through
988 : : processing the argument. */
989 : 241233380 : bool is_delete_operator
990 : 241233380 : = (is_gimple_call (stmt)
991 : 37152215 : && gimple_call_from_new_or_delete (as_a <gcall *> (stmt))
992 : 242294431 : && gimple_call_operator_delete_p (as_a <gcall *> (stmt)));
993 : 240401109 : if (is_delete_operator
994 : 240401109 : || gimple_call_builtin_p (stmt, BUILT_IN_FREE)
995 : 240109242 : || gimple_call_builtin_p (stmt, BUILT_IN_GOMP_FREE))
996 : : {
997 : 1124138 : tree ptr = gimple_call_arg (stmt, 0);
998 : 1124138 : gcall *def_stmt;
999 : : /* If the pointer we free is defined by an allocation
1000 : : function do not add the call to the worklist. */
1001 : 1124138 : if (TREE_CODE (ptr) == SSA_NAME
1002 : 1123628 : && (def_stmt = dyn_cast <gcall *> (SSA_NAME_DEF_STMT (ptr)))
1003 : 1315102 : && is_removable_allocation_p (def_stmt, false))
1004 : : {
1005 : 169754 : if (is_delete_operator
1006 : 169754 : && !valid_new_delete_pair_p (def_stmt, stmt))
1007 : 125 : mark_operand_necessary (gimple_call_arg (stmt, 0));
1008 : :
1009 : : /* Delete operators can have alignment and (or) size
1010 : : as next arguments. When being a SSA_NAME, they
1011 : : must be marked as necessary. Similarly GOMP_free. */
1012 : 169754 : if (gimple_call_num_args (stmt) >= 2)
1013 : 83613 : for (unsigned i = 1; i < gimple_call_num_args (stmt);
1014 : : i++)
1015 : : {
1016 : 41815 : tree arg = gimple_call_arg (stmt, i);
1017 : 41815 : if (TREE_CODE (arg) == SSA_NAME)
1018 : 7546 : mark_operand_necessary (arg);
1019 : : }
1020 : :
1021 : 105329286 : continue;
1022 : 169754 : }
1023 : : }
1024 : :
1025 : 241063626 : if (checks_return_value_of_removable_allocation_p (stmt))
1026 : 99857 : continue;
1027 : :
1028 : 451635135 : FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
1029 : 210671366 : mark_operand_necessary (use);
1030 : :
1031 : 240963769 : use = gimple_vuse (stmt);
1032 : 207878502 : if (!use)
1033 : 98958602 : continue;
1034 : :
1035 : : /* No need to search for vdefs if we intrinsicly keep them all. */
1036 : 142005167 : if (keep_all_vdefs_p ())
1037 : 70224 : continue;
1038 : :
1039 : : /* If we dropped to simple mode make all immediately
1040 : : reachable definitions necessary. */
1041 : 141934943 : if (chain_ovfl)
1042 : : {
1043 : 3752126 : mark_all_reaching_defs_necessary (stmt);
1044 : 3752126 : continue;
1045 : : }
1046 : :
1047 : : /* For statements that may load from memory (have a VUSE) we
1048 : : have to mark all reaching (may-)definitions as necessary.
1049 : : We partition this task into two cases:
1050 : : 1) explicit loads based on decls that are not aliased
1051 : : 2) implicit loads (like calls) and explicit loads not
1052 : : based on decls that are not aliased (like indirect
1053 : : references or loads from globals)
1054 : : For 1) we mark all reaching may-defs as necessary, stopping
1055 : : at dominating kills. For 2) we want to mark all dominating
1056 : : references necessary, but non-aliased ones which we handle
1057 : : in 1). By keeping a global visited bitmap for references
1058 : : we walk for 2) we avoid quadratic behavior for those. */
1059 : :
1060 : 138182817 : if (gcall *call = dyn_cast <gcall *> (stmt))
1061 : : {
1062 : 33729938 : tree callee = gimple_call_fndecl (call);
1063 : 33729938 : unsigned i;
1064 : :
1065 : 34740824 : if (callee != NULL_TREE
1066 : 32091011 : && (DECL_IS_REPLACEABLE_OPERATOR_NEW_P (callee)
1067 : 31855813 : || DECL_IS_OPERATOR_DELETE_P (callee))
1068 : 34759290 : && gimple_call_from_new_or_delete (call))
1069 : 1010886 : continue;
1070 : :
1071 : 32719052 : if (is_removable_cxa_atexit_call (call))
1072 : 0 : continue;
1073 : :
1074 : : bool all_refs = false;
1075 : : /* Calls implicitly load from memory, their arguments
1076 : : in addition may explicitly perform memory loads. */
1077 : 100705204 : for (i = 0; i < gimple_call_num_args (call); ++i)
1078 : : {
1079 : 67986152 : tree arg = gimple_call_arg (call, i);
1080 : 131778604 : if (TREE_CODE (arg) == SSA_NAME
1081 : 67986152 : || is_gimple_min_invariant (arg))
1082 : 63792452 : continue;
1083 : 4193700 : if (TREE_CODE (arg) == WITH_SIZE_EXPR)
1084 : 660 : arg = TREE_OPERAND (arg, 0);
1085 : 4193700 : if (!ref_may_be_aliased (arg))
1086 : 3782701 : mark_aliased_reaching_defs_necessary (call, arg);
1087 : : else
1088 : : all_refs = true;
1089 : : }
1090 : :
1091 : 32719052 : if (!all_refs && ipa_modref_callee_reads_no_memory_p (call))
1092 : 1267837 : continue;
1093 : 31451215 : mark_all_reaching_defs_necessary (call);
1094 : : }
1095 : 104452879 : else if (gimple_assign_single_p (stmt))
1096 : : {
1097 : 96384557 : tree rhs;
1098 : : /* If this is a load mark things necessary. */
1099 : 96384557 : rhs = gimple_assign_rhs1 (stmt);
1100 : 96384557 : if (TREE_CODE (rhs) != SSA_NAME
1101 : 78322877 : && !is_gimple_min_invariant (rhs)
1102 : 151026897 : && TREE_CODE (rhs) != CONSTRUCTOR)
1103 : : {
1104 : 44504105 : if (!ref_may_be_aliased (rhs))
1105 : 9312108 : mark_aliased_reaching_defs_necessary (stmt, rhs);
1106 : : else
1107 : 35191997 : mark_all_reaching_defs_necessary (stmt);
1108 : : }
1109 : : }
1110 : 8068322 : else if (greturn *return_stmt = dyn_cast <greturn *> (stmt))
1111 : : {
1112 : 7916954 : tree rhs = gimple_return_retval (return_stmt);
1113 : : /* A return statement may perform a load. */
1114 : 7916954 : if (rhs
1115 : 4389405 : && TREE_CODE (rhs) != SSA_NAME
1116 : 1439397 : && !is_gimple_min_invariant (rhs)
1117 : 8619720 : && TREE_CODE (rhs) != CONSTRUCTOR)
1118 : : {
1119 : 702766 : if (!ref_may_be_aliased (rhs))
1120 : 680235 : mark_aliased_reaching_defs_necessary (stmt, rhs);
1121 : : else
1122 : 22531 : mark_all_reaching_defs_necessary (stmt);
1123 : : }
1124 : : }
1125 : 151368 : else if (gasm *asm_stmt = dyn_cast <gasm *> (stmt))
1126 : : {
1127 : 150184 : unsigned i;
1128 : 150184 : mark_all_reaching_defs_necessary (stmt);
1129 : : /* Inputs may perform loads. */
1130 : 268835 : for (i = 0; i < gimple_asm_ninputs (asm_stmt); ++i)
1131 : : {
1132 : 118651 : tree op = TREE_VALUE (gimple_asm_input_op (asm_stmt, i));
1133 : 118651 : if (TREE_CODE (op) != SSA_NAME
1134 : 79077 : && !is_gimple_min_invariant (op)
1135 : 41030 : && TREE_CODE (op) != CONSTRUCTOR
1136 : 159681 : && !ref_may_be_aliased (op))
1137 : 5578 : mark_aliased_reaching_defs_necessary (stmt, op);
1138 : : }
1139 : : }
1140 : 1184 : else if (gimple_code (stmt) == GIMPLE_TRANSACTION)
1141 : : {
1142 : : /* The beginning of a transaction is a memory barrier. */
1143 : : /* ??? If we were really cool, we'd only be a barrier
1144 : : for the memories touched within the transaction. */
1145 : 1184 : mark_all_reaching_defs_necessary (stmt);
1146 : : }
1147 : : else
1148 : 0 : gcc_unreachable ();
1149 : :
1150 : : /* If we over-used our alias oracle budget drop to simple
1151 : : mode. The cost metric allows quadratic behavior
1152 : : (number of uses times number of may-defs queries) up to
1153 : : a constant maximal number of queries and after that falls back to
1154 : : super-linear complexity. */
1155 : 135904094 : if (/* Constant but quadratic for small functions. */
1156 : 135904094 : total_chain > 128 * 128
1157 : : /* Linear in the number of may-defs. */
1158 : 1164118 : && total_chain > 32 * longest_chain
1159 : : /* Linear in the number of uses. */
1160 : 4818 : && total_chain > nr_walks * 32)
1161 : : {
1162 : 4657 : chain_ovfl = true;
1163 : 4657 : if (visited)
1164 : 4657 : bitmap_clear (visited);
1165 : : }
1166 : : }
1167 : : }
1168 : 8096455 : }
1169 : :
1170 : : /* Remove dead PHI nodes from block BB. */
1171 : :
1172 : : static bool
1173 : 83774369 : remove_dead_phis (basic_block bb)
1174 : : {
1175 : 83774369 : bool something_changed = false;
1176 : 83774369 : gphi *phi;
1177 : 83774369 : gphi_iterator gsi;
1178 : :
1179 : 121215474 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);)
1180 : : {
1181 : 37441105 : stats.total_phis++;
1182 : 37441105 : phi = gsi.phi ();
1183 : :
1184 : : /* We do not track necessity of virtual PHI nodes. Instead do
1185 : : very simple dead PHI removal here. */
1186 : 74882210 : if (virtual_operand_p (gimple_phi_result (phi)))
1187 : : {
1188 : : /* Virtual PHI nodes with one or identical arguments
1189 : : can be removed. */
1190 : 17006916 : if (!loops_state_satisfies_p (LOOP_CLOSED_SSA)
1191 : 17006916 : && degenerate_phi_p (phi))
1192 : : {
1193 : 1966399 : tree vdef = gimple_phi_result (phi);
1194 : 1966399 : tree vuse = gimple_phi_arg_def (phi, 0);
1195 : :
1196 : 1966399 : use_operand_p use_p;
1197 : 1966399 : imm_use_iterator iter;
1198 : 1966399 : gimple *use_stmt;
1199 : 5091895 : FOR_EACH_IMM_USE_STMT (use_stmt, iter, vdef)
1200 : 9482886 : FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
1201 : 5145094 : SET_USE (use_p, vuse);
1202 : 1966399 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vdef)
1203 : 1966399 : && TREE_CODE (vuse) == SSA_NAME)
1204 : 467 : SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vuse) = 1;
1205 : : }
1206 : : else
1207 : 15040517 : gimple_set_plf (phi, STMT_NECESSARY, true);
1208 : : }
1209 : :
1210 : 37441105 : if (!gimple_plf (phi, STMT_NECESSARY))
1211 : : {
1212 : 2297242 : something_changed = true;
1213 : 2297242 : if (dump_file && (dump_flags & TDF_DETAILS))
1214 : : {
1215 : 20 : fprintf (dump_file, "Deleting : ");
1216 : 20 : print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
1217 : 20 : fprintf (dump_file, "\n");
1218 : : }
1219 : :
1220 : 2297242 : remove_phi_node (&gsi, true);
1221 : 2297242 : stats.removed_phis++;
1222 : 2297242 : continue;
1223 : : }
1224 : :
1225 : 35143863 : gsi_next (&gsi);
1226 : : }
1227 : 83774369 : return something_changed;
1228 : : }
1229 : :
1230 : :
1231 : : /* Remove dead statement pointed to by iterator I. Receives the basic block BB
1232 : : containing I so that we don't have to look it up. */
1233 : :
1234 : : static void
1235 : 7629187 : remove_dead_stmt (gimple_stmt_iterator *i, basic_block bb,
1236 : : vec<edge> &to_remove_edges)
1237 : : {
1238 : 7629187 : gimple *stmt = gsi_stmt (*i);
1239 : :
1240 : 7629187 : if (dump_file && (dump_flags & TDF_DETAILS))
1241 : : {
1242 : 129 : fprintf (dump_file, "Deleting : ");
1243 : 129 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1244 : 129 : fprintf (dump_file, "\n");
1245 : : }
1246 : :
1247 : 7629187 : stats.removed++;
1248 : :
1249 : : /* If we have determined that a conditional branch statement contributes
1250 : : nothing to the program, then we not only remove it, but we need to update
1251 : : the CFG. We can chose any of edges out of BB as long as we are sure to not
1252 : : close infinite loops. This is done by always choosing the edge closer to
1253 : : exit in inverted_rev_post_order_compute order. */
1254 : 7629187 : if (is_ctrl_stmt (stmt))
1255 : : {
1256 : 42305 : edge_iterator ei;
1257 : 42305 : edge e = NULL, e2;
1258 : :
1259 : : /* See if there is only one non-abnormal edge. */
1260 : 42305 : if (single_succ_p (bb))
1261 : 3 : e = single_succ_edge (bb);
1262 : : /* Otherwise chose one that is closer to bb with live statement in it.
1263 : : To be able to chose one, we compute inverted post order starting from
1264 : : all BBs with live statements. */
1265 : 3 : if (!e)
1266 : : {
1267 : 42302 : if (!bb_postorder)
1268 : : {
1269 : 20079 : int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
1270 : 20079 : int n = inverted_rev_post_order_compute (cfun, rpo,
1271 : : &bb_contains_live_stmts);
1272 : 20079 : bb_postorder = XNEWVEC (int, last_basic_block_for_fn (cfun));
1273 : 849584 : for (int i = 0; i < n; ++i)
1274 : 829505 : bb_postorder[rpo[i]] = i;
1275 : 20079 : free (rpo);
1276 : : }
1277 : 126920 : FOR_EACH_EDGE (e2, ei, bb->succs)
1278 : 84618 : if (!e || e2->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
1279 : 42316 : || bb_postorder [e->dest->index]
1280 : 42316 : >= bb_postorder [e2->dest->index])
1281 : 67026 : e = e2;
1282 : : }
1283 : 42302 : gcc_assert (e);
1284 : 42305 : e->probability = profile_probability::always ();
1285 : :
1286 : : /* The edge is no longer associated with a conditional, so it does
1287 : : not have TRUE/FALSE flags.
1288 : : We are also safe to drop EH/ABNORMAL flags and turn them into
1289 : : normal control flow, because we know that all the destinations (including
1290 : : those odd edges) are equivalent for program execution. */
1291 : 42305 : e->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE | EDGE_EH | EDGE_ABNORMAL);
1292 : :
1293 : : /* The lone outgoing edge from BB will be a fallthru edge. */
1294 : 42305 : e->flags |= EDGE_FALLTHRU;
1295 : :
1296 : : /* Remove the remaining outgoing edges. */
1297 : 126926 : FOR_EACH_EDGE (e2, ei, bb->succs)
1298 : 84621 : if (e != e2)
1299 : : {
1300 : : /* If we made a BB unconditionally exit a loop or removed
1301 : : an entry into an irreducible region, then this transform
1302 : : alters the set of BBs in the loop. Schedule a fixup. */
1303 : 42316 : if (loop_exit_edge_p (bb->loop_father, e)
1304 : 42316 : || (e2->dest->flags & BB_IRREDUCIBLE_LOOP))
1305 : 26465 : loops_state_set (LOOPS_NEED_FIXUP);
1306 : 42316 : to_remove_edges.safe_push (e2);
1307 : : }
1308 : : }
1309 : :
1310 : : /* If this is a store into a variable that is being optimized away,
1311 : : add a debug bind stmt if possible. */
1312 : 7629187 : if (MAY_HAVE_DEBUG_BIND_STMTS
1313 : 7018516 : && gimple_assign_single_p (stmt)
1314 : 7938571 : && is_gimple_val (gimple_assign_rhs1 (stmt)))
1315 : : {
1316 : 166744 : tree lhs = gimple_assign_lhs (stmt);
1317 : 144811 : if ((VAR_P (lhs) || TREE_CODE (lhs) == PARM_DECL)
1318 : 21979 : && !DECL_IGNORED_P (lhs)
1319 : 5980 : && is_gimple_reg_type (TREE_TYPE (lhs))
1320 : 54 : && !is_global_var (lhs)
1321 : 166798 : && !DECL_HAS_VALUE_EXPR_P (lhs))
1322 : : {
1323 : 54 : tree rhs = gimple_assign_rhs1 (stmt);
1324 : 54 : gdebug *note
1325 : 54 : = gimple_build_debug_bind (lhs, unshare_expr (rhs), stmt);
1326 : 54 : gsi_insert_after (i, note, GSI_SAME_STMT);
1327 : : }
1328 : : }
1329 : :
1330 : 7629187 : unlink_stmt_vdef (stmt);
1331 : 7629187 : gsi_remove (i, true);
1332 : 7629187 : release_defs (stmt);
1333 : 7629187 : }
1334 : :
1335 : : /* Helper for maybe_optimize_arith_overflow. Find in *TP if there are any
1336 : : uses of data (SSA_NAME) other than REALPART_EXPR referencing it. */
1337 : :
1338 : : static tree
1339 : 26 : find_non_realpart_uses (tree *tp, int *walk_subtrees, void *data)
1340 : : {
1341 : 26 : if (TYPE_P (*tp) || TREE_CODE (*tp) == REALPART_EXPR)
1342 : 0 : *walk_subtrees = 0;
1343 : 26 : if (*tp == (tree) data)
1344 : 13 : return *tp;
1345 : : return NULL_TREE;
1346 : : }
1347 : :
1348 : : /* If the IMAGPART_EXPR of the {ADD,SUB,MUL}_OVERFLOW result is never used,
1349 : : but REALPART_EXPR is, optimize the {ADD,SUB,MUL}_OVERFLOW internal calls
1350 : : into plain unsigned {PLUS,MINUS,MULT}_EXPR, and if needed reset debug
1351 : : uses. */
1352 : :
1353 : : static void
1354 : 289827 : maybe_optimize_arith_overflow (gimple_stmt_iterator *gsi,
1355 : : enum tree_code subcode)
1356 : : {
1357 : 289827 : gimple *stmt = gsi_stmt (*gsi);
1358 : 289827 : tree lhs = gimple_call_lhs (stmt);
1359 : :
1360 : 289827 : if (lhs == NULL || TREE_CODE (lhs) != SSA_NAME)
1361 : 289669 : return;
1362 : :
1363 : 289827 : imm_use_iterator imm_iter;
1364 : 289827 : use_operand_p use_p;
1365 : 289827 : bool has_debug_uses = false;
1366 : 289827 : bool has_realpart_uses = false;
1367 : 289827 : bool has_other_uses = false;
1368 : 298980 : FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
1369 : : {
1370 : 298822 : gimple *use_stmt = USE_STMT (use_p);
1371 : 298822 : if (is_gimple_debug (use_stmt))
1372 : : has_debug_uses = true;
1373 : 294126 : else if (is_gimple_assign (use_stmt)
1374 : 293141 : && gimple_assign_rhs_code (use_stmt) == REALPART_EXPR
1375 : 298583 : && TREE_OPERAND (gimple_assign_rhs1 (use_stmt), 0) == lhs)
1376 : : has_realpart_uses = true;
1377 : : else
1378 : : {
1379 : : has_other_uses = true;
1380 : : break;
1381 : : }
1382 : : }
1383 : :
1384 : 289827 : if (!has_realpart_uses || has_other_uses)
1385 : : return;
1386 : :
1387 : 158 : tree arg0 = gimple_call_arg (stmt, 0);
1388 : 158 : tree arg1 = gimple_call_arg (stmt, 1);
1389 : 158 : location_t loc = gimple_location (stmt);
1390 : 158 : tree type = TREE_TYPE (TREE_TYPE (lhs));
1391 : 158 : tree utype = unsigned_type_for (type);
1392 : 158 : tree result = fold_build2_loc (loc, subcode, utype,
1393 : : fold_convert_loc (loc, utype, arg0),
1394 : : fold_convert_loc (loc, utype, arg1));
1395 : 158 : result = fold_convert_loc (loc, type, result);
1396 : :
1397 : 158 : if (has_debug_uses)
1398 : : {
1399 : 13 : gimple *use_stmt;
1400 : 39 : FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, lhs)
1401 : : {
1402 : 26 : if (!gimple_debug_bind_p (use_stmt))
1403 : 13 : continue;
1404 : 13 : tree v = gimple_debug_bind_get_value (use_stmt);
1405 : 13 : if (walk_tree (&v, find_non_realpart_uses, lhs, NULL))
1406 : : {
1407 : 13 : gimple_debug_bind_reset_value (use_stmt);
1408 : 13 : update_stmt (use_stmt);
1409 : : }
1410 : 13 : }
1411 : : }
1412 : :
1413 : 158 : if (TREE_CODE (result) == INTEGER_CST && TREE_OVERFLOW (result))
1414 : 0 : result = drop_tree_overflow (result);
1415 : 158 : tree overflow = build_zero_cst (type);
1416 : 158 : tree ctype = build_complex_type (type);
1417 : 158 : if (TREE_CODE (result) == INTEGER_CST)
1418 : 0 : result = build_complex (ctype, result, overflow);
1419 : : else
1420 : 158 : result = build2_loc (gimple_location (stmt), COMPLEX_EXPR,
1421 : : ctype, result, overflow);
1422 : :
1423 : 158 : if (dump_file && (dump_flags & TDF_DETAILS))
1424 : : {
1425 : 0 : fprintf (dump_file, "Transforming call: ");
1426 : 0 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1427 : 0 : fprintf (dump_file, "because the overflow result is never used into: ");
1428 : 0 : print_generic_stmt (dump_file, result, TDF_SLIM);
1429 : 0 : fprintf (dump_file, "\n");
1430 : : }
1431 : :
1432 : 158 : gimplify_and_update_call_from_tree (gsi, result);
1433 : : }
1434 : :
1435 : : /* Returns whether the control parents of BB are preserved. */
1436 : :
1437 : : static bool
1438 : 359159 : control_parents_preserved_p (basic_block bb)
1439 : : {
1440 : : /* If we marked the control parents from BB they are preserved. */
1441 : 359159 : if (bitmap_bit_p (visited_control_parents, bb->index))
1442 : : return true;
1443 : :
1444 : : /* But they can also end up being marked from elsewhere. */
1445 : 7135 : bitmap_iterator bi;
1446 : 7135 : unsigned edge_number;
1447 : 11281 : EXECUTE_IF_SET_IN_BITMAP (cd->get_edges_dependent_on (bb->index),
1448 : : 0, edge_number, bi)
1449 : : {
1450 : 7243 : basic_block cd_bb = cd->get_edge_src (edge_number);
1451 : 7243 : if (cd_bb != bb
1452 : 7243 : && !bitmap_bit_p (last_stmt_necessary, cd_bb->index))
1453 : : return false;
1454 : : }
1455 : : /* And cache the result. */
1456 : 4038 : bitmap_set_bit (visited_control_parents, bb->index);
1457 : 4038 : return true;
1458 : : }
1459 : :
1460 : : /* If basic block is empty, we can remove conditionals that controls
1461 : : its execution. However in some cases the empty BB can stay live
1462 : : (such as when it was a header of empty loop). In this case we
1463 : : need to update its count. Since regions of dead BBs are acyclic
1464 : : we simply propagate counts forward from live BBs to dead ones. */
1465 : :
1466 : : static void
1467 : 20112 : propagate_counts ()
1468 : : {
1469 : 20112 : basic_block bb;
1470 : 20112 : auto_vec<basic_block, 16> queue;
1471 : 20112 : hash_map <basic_block, int> cnt;
1472 : :
1473 : 762712 : FOR_EACH_BB_FN (bb, cfun)
1474 : 742600 : if (!bitmap_bit_p (bb_contains_live_stmts, bb->index))
1475 : : {
1476 : 168606 : int n = 0;
1477 : 708999 : for (edge e : bb->preds)
1478 : 203181 : if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
1479 : 203181 : && !bitmap_bit_p (bb_contains_live_stmts, e->src->index))
1480 : 36603 : n++;
1481 : 168606 : if (!n)
1482 : 136303 : queue.safe_push (bb);
1483 : 168606 : cnt.put (bb, n);
1484 : : }
1485 : 206468 : while (!queue.is_empty ())
1486 : : {
1487 : 166244 : basic_block bb = queue.pop ();
1488 : 166244 : profile_count sum = profile_count::zero ();
1489 : :
1490 : 532209 : for (edge e : bb->preds)
1491 : : {
1492 : 199721 : sum += e->count ();
1493 : 199721 : gcc_checking_assert (!cnt.get (e->src));
1494 : : }
1495 : : /* If we have partial profile and some counts of incomming edges are
1496 : : unknown, it is probably better to keep the existing count.
1497 : : We could also propagate bi-directionally. */
1498 : 166244 : if (sum.initialized_p () && !(sum == bb->count))
1499 : : {
1500 : 28260 : if (dump_file && (dump_flags & TDF_DETAILS))
1501 : : {
1502 : 5 : fprintf (dump_file, "Updating count of empty bb %i from ",
1503 : : bb->index);
1504 : 5 : bb->count.dump (dump_file);
1505 : 5 : fprintf (dump_file, " to ");
1506 : 5 : sum.dump (dump_file);
1507 : 5 : fprintf (dump_file, "\n");
1508 : : }
1509 : 28260 : bb->count = sum;
1510 : : }
1511 : 166244 : cnt.remove (bb);
1512 : 664976 : for (edge e : bb->succs)
1513 : 166244 : if (int *n = cnt.get (e->dest))
1514 : : {
1515 : 34241 : (*n)--;
1516 : 34241 : if (!*n)
1517 : 29941 : queue.safe_push (e->dest);
1518 : : }
1519 : : }
1520 : : /* Do not check that all blocks has been processed, since for
1521 : : empty infinite loops this is not the case. */
1522 : 20112 : }
1523 : :
1524 : : /* Eliminate unnecessary statements. Any instruction not marked as necessary
1525 : : contributes nothing to the program, and can be deleted. */
1526 : :
1527 : : static bool
1528 : 8096455 : eliminate_unnecessary_stmts (bool aggressive)
1529 : : {
1530 : 8096455 : bool something_changed = false;
1531 : 8096455 : basic_block bb;
1532 : 8096455 : gimple_stmt_iterator gsi, psi;
1533 : 8096455 : gimple *stmt;
1534 : 8096455 : auto_vec<edge> to_remove_edges;
1535 : :
1536 : 8096455 : if (dump_file && (dump_flags & TDF_DETAILS))
1537 : 209 : fprintf (dump_file, "\nEliminating unnecessary statements:\n");
1538 : :
1539 : 8096455 : bool had_setjmp = cfun->calls_setjmp;
1540 : 8096455 : clear_special_calls ();
1541 : :
1542 : : /* Walking basic blocks and statements in reverse order avoids
1543 : : releasing SSA names before any other DEFs that refer to them are
1544 : : released. This helps avoid loss of debug information, as we get
1545 : : a chance to propagate all RHSs of removed SSAs into debug uses,
1546 : : rather than only the latest ones. E.g., consider:
1547 : :
1548 : : x_3 = y_1 + z_2;
1549 : : a_5 = x_3 - b_4;
1550 : : # DEBUG a => a_5
1551 : :
1552 : : If we were to release x_3 before a_5, when we reached a_5 and
1553 : : tried to substitute it into the debug stmt, we'd see x_3 there,
1554 : : but x_3's DEF, type, etc would have already been disconnected.
1555 : : By going backwards, the debug stmt first changes to:
1556 : :
1557 : : # DEBUG a => x_3 - b_4
1558 : :
1559 : : and then to:
1560 : :
1561 : : # DEBUG a => y_1 + z_2 - b_4
1562 : :
1563 : : as desired. */
1564 : 8096455 : gcc_assert (dom_info_available_p (CDI_DOMINATORS));
1565 : 8096455 : auto_vec<basic_block> h;
1566 : 8096455 : h = get_all_dominated_blocks (CDI_DOMINATORS,
1567 : 16192910 : single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
1568 : :
1569 : 91870824 : while (h.length ())
1570 : : {
1571 : 83774369 : bb = h.pop ();
1572 : :
1573 : : /* Remove dead statements. */
1574 : 83774369 : auto_bitmap debug_seen;
1575 : 83774369 : hash_set<int_hash <location_t, 0>> locs_seen;
1576 : 763964621 : for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi = psi)
1577 : : {
1578 : 596415883 : stmt = gsi_stmt (gsi);
1579 : :
1580 : 596415883 : psi = gsi;
1581 : 596415883 : gsi_prev (&psi);
1582 : :
1583 : 596415883 : stats.total++;
1584 : :
1585 : : /* We can mark a call to free as not necessary if the
1586 : : defining statement of its argument is not necessary
1587 : : (and thus is getting removed). */
1588 : 596415883 : if (gimple_plf (stmt, STMT_NECESSARY)
1589 : 596415883 : && (gimple_call_builtin_p (stmt, BUILT_IN_FREE)
1590 : 593699915 : || (is_gimple_call (stmt)
1591 : 36860348 : && gimple_call_from_new_or_delete (as_a <gcall *> (stmt))
1592 : 1061051 : && gimple_call_operator_delete_p (as_a <gcall *> (stmt)))))
1593 : : {
1594 : 1124138 : tree ptr = gimple_call_arg (stmt, 0);
1595 : 1124138 : if (TREE_CODE (ptr) == SSA_NAME)
1596 : : {
1597 : 1123628 : gimple *def_stmt = SSA_NAME_DEF_STMT (ptr);
1598 : 1123628 : if (!gimple_nop_p (def_stmt)
1599 : 1123628 : && !gimple_plf (def_stmt, STMT_NECESSARY))
1600 : 6132 : gimple_set_plf (stmt, STMT_NECESSARY, false);
1601 : : }
1602 : : }
1603 : : /* Conditional checking that return value of allocation is non-NULL
1604 : : can be turned to constant if the allocation itself
1605 : : is unnecesary. */
1606 : 596415883 : if (gimple_plf (stmt, STMT_NECESSARY)
1607 : 593985650 : && gimple_code (stmt) == GIMPLE_COND
1608 : 627752437 : && TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME)
1609 : : {
1610 : 31332545 : gimple *def_stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt));
1611 : 31332545 : if (!gimple_nop_p (def_stmt)
1612 : 31332545 : && !gimple_plf (def_stmt, STMT_NECESSARY))
1613 : : {
1614 : 3093 : gcc_checking_assert
1615 : : (checks_return_value_of_removable_allocation_p (stmt));
1616 : 3093 : gimple_cond_set_lhs (as_a <gcond *>(stmt),
1617 : : build_one_cst
1618 : 3093 : (TREE_TYPE (gimple_cond_rhs (stmt))));
1619 : 3093 : update_stmt (stmt);
1620 : : }
1621 : : }
1622 : :
1623 : : /* If GSI is not necessary then remove it. */
1624 : 596415883 : if (!gimple_plf (stmt, STMT_NECESSARY))
1625 : : {
1626 : : /* Keep clobbers that we can keep live live. */
1627 : 2430233 : if (gimple_clobber_p (stmt))
1628 : : {
1629 : 864719 : ssa_op_iter iter;
1630 : 864719 : use_operand_p use_p;
1631 : 864719 : bool dead = false;
1632 : 1727095 : FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1633 : : {
1634 : 864719 : tree name = USE_FROM_PTR (use_p);
1635 : 864719 : if (!SSA_NAME_IS_DEFAULT_DEF (name)
1636 : 864719 : && !bitmap_bit_p (processed, SSA_NAME_VERSION (name)))
1637 : : {
1638 : : dead = true;
1639 : : break;
1640 : : }
1641 : : }
1642 : 1723998 : if (!dead
1643 : : /* When doing CD-DCE we have to ensure all controls
1644 : : of the stmt are still live. */
1645 : 864719 : && (!aggressive || control_parents_preserved_p (bb)))
1646 : : {
1647 : 859279 : bitmap_clear (debug_seen);
1648 : 859279 : continue;
1649 : : }
1650 : : }
1651 : 1570954 : if (!is_gimple_debug (stmt))
1652 : 1266156 : something_changed = true;
1653 : 1570954 : remove_dead_stmt (&gsi, bb, to_remove_edges);
1654 : 1570954 : continue;
1655 : 1570954 : }
1656 : 593985650 : else if (gcall *call_stmt = dyn_cast <gcall *> (stmt))
1657 : : {
1658 : 37146083 : tree name = gimple_call_lhs (call_stmt);
1659 : :
1660 : 37146083 : notice_special_calls (call_stmt);
1661 : :
1662 : : /* When LHS of var = call (); is dead, simplify it into
1663 : : call (); saving one operand. */
1664 : 37146083 : if (name
1665 : 14496445 : && TREE_CODE (name) == SSA_NAME
1666 : 11993271 : && !bitmap_bit_p (processed, SSA_NAME_VERSION (name))
1667 : : /* Avoid doing so for allocation calls which we
1668 : : did not mark as necessary, it will confuse the
1669 : : special logic we apply to malloc/free pair removal. */
1670 : 37237873 : && !is_removable_allocation_p (call_stmt, false))
1671 : : {
1672 : 89002 : something_changed = true;
1673 : 89002 : if (dump_file && (dump_flags & TDF_DETAILS))
1674 : : {
1675 : 1 : fprintf (dump_file, "Deleting LHS of call: ");
1676 : 1 : print_gimple_stmt (dump_file, call_stmt, 0, TDF_SLIM);
1677 : 1 : fprintf (dump_file, "\n");
1678 : : }
1679 : :
1680 : 89002 : gimple_call_set_lhs (call_stmt, NULL_TREE);
1681 : 89002 : maybe_clean_or_replace_eh_stmt (call_stmt, call_stmt);
1682 : 89002 : update_stmt (call_stmt);
1683 : 89002 : release_ssa_name (name);
1684 : :
1685 : : /* __builtin_stack_save without lhs is not needed. */
1686 : 89002 : if (gimple_call_builtin_p (call_stmt, BUILT_IN_STACK_SAVE))
1687 : 37 : remove_dead_stmt (&gsi, bb, to_remove_edges);
1688 : : /* GOMP_SIMD_LANE (unless three argument) or ASAN_POISON
1689 : : without lhs is not needed. */
1690 : 88965 : else if (gimple_call_internal_p (call_stmt))
1691 : 8169 : switch (gimple_call_internal_fn (call_stmt))
1692 : : {
1693 : 760 : case IFN_GOMP_SIMD_LANE:
1694 : 760 : if (gimple_call_num_args (call_stmt) >= 3
1695 : 798 : && !integer_nonzerop
1696 : 38 : (gimple_call_arg (call_stmt, 2)))
1697 : : break;
1698 : : /* FALLTHRU */
1699 : 862 : case IFN_ASAN_POISON:
1700 : 862 : remove_dead_stmt (&gsi, bb, to_remove_edges);
1701 : 862 : break;
1702 : : default:
1703 : : break;
1704 : : }
1705 : : }
1706 : 37057081 : else if (gimple_call_internal_p (call_stmt))
1707 : 1054620 : switch (gimple_call_internal_fn (call_stmt))
1708 : : {
1709 : 90221 : case IFN_ADD_OVERFLOW:
1710 : 90221 : maybe_optimize_arith_overflow (&gsi, PLUS_EXPR);
1711 : 90221 : break;
1712 : 95384 : case IFN_SUB_OVERFLOW:
1713 : 95384 : maybe_optimize_arith_overflow (&gsi, MINUS_EXPR);
1714 : 95384 : break;
1715 : 99746 : case IFN_MUL_OVERFLOW:
1716 : 99746 : maybe_optimize_arith_overflow (&gsi, MULT_EXPR);
1717 : 99746 : break;
1718 : 24861 : case IFN_UADDC:
1719 : 24861 : if (integer_zerop (gimple_call_arg (call_stmt, 2)))
1720 : 2474 : maybe_optimize_arith_overflow (&gsi, PLUS_EXPR);
1721 : : break;
1722 : 13939 : case IFN_USUBC:
1723 : 13939 : if (integer_zerop (gimple_call_arg (call_stmt, 2)))
1724 : 2002 : maybe_optimize_arith_overflow (&gsi, MINUS_EXPR);
1725 : : break;
1726 : : default:
1727 : : break;
1728 : : }
1729 : : }
1730 : 556839567 : else if (gimple_debug_bind_p (stmt))
1731 : : {
1732 : : /* We are only keeping the last debug-bind of a
1733 : : non-DEBUG_EXPR_DECL variable in a series of
1734 : : debug-bind stmts. */
1735 : 264603939 : tree var = gimple_debug_bind_get_var (stmt);
1736 : 264603939 : if (TREE_CODE (var) != DEBUG_EXPR_DECL
1737 : 264603939 : && !bitmap_set_bit (debug_seen, DECL_UID (var)))
1738 : 6036715 : remove_dead_stmt (&gsi, bb, to_remove_edges);
1739 : 264603939 : continue;
1740 : 264603939 : }
1741 : 292235628 : else if (gimple_debug_begin_stmt_p (stmt))
1742 : : {
1743 : : /* We are only keeping the last debug-begin in a series of
1744 : : debug-begin stmts. */
1745 : 26745644 : if (locs_seen.add (gimple_location (stmt)))
1746 : 20619 : remove_dead_stmt (&gsi, bb, to_remove_edges);
1747 : 26745644 : continue;
1748 : : }
1749 : 302636067 : locs_seen.empty ();
1750 : 302636067 : bitmap_clear (debug_seen);
1751 : : }
1752 : :
1753 : : /* Remove dead PHI nodes. */
1754 : 83774369 : something_changed |= remove_dead_phis (bb);
1755 : 83774369 : }
1756 : :
1757 : : /* First remove queued edges. */
1758 : 8096455 : if (!to_remove_edges.is_empty ())
1759 : : {
1760 : : /* Remove edges. We've delayed this to not get bogus debug stmts
1761 : : during PHI node removal. */
1762 : 62395 : for (unsigned i = 0; i < to_remove_edges.length (); ++i)
1763 : 42316 : remove_edge (to_remove_edges[i]);
1764 : 20079 : cfg_altered = true;
1765 : : }
1766 : : /* When we cleared calls_setjmp we can purge all abnormal edges. Do so.
1767 : : ??? We'd like to assert that setjmp calls do not pop out of nothing
1768 : : but we currently lack a per-stmt way of noting whether a call was
1769 : : recognized as returns-twice (or rather receives-control). */
1770 : 8096455 : if (!cfun->calls_setjmp && had_setjmp)
1771 : : {
1772 : : /* Make sure we only remove the edges, not dominated blocks. Using
1773 : : gimple_purge_dead_abnormal_call_edges would do that and we
1774 : : cannot free dominators yet. */
1775 : 3750 : FOR_EACH_BB_FN (bb, cfun)
1776 : 9662 : if (gcall *stmt = safe_dyn_cast <gcall *> (*gsi_last_bb (bb)))
1777 : 2082 : if (!stmt_can_make_abnormal_goto (stmt))
1778 : : {
1779 : 737 : edge_iterator ei;
1780 : 737 : edge e;
1781 : 996 : for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
1782 : : {
1783 : 259 : if (e->flags & EDGE_ABNORMAL)
1784 : : {
1785 : 112 : if (e->flags & EDGE_FALLTHRU)
1786 : 0 : e->flags &= ~EDGE_ABNORMAL;
1787 : : else
1788 : 112 : remove_edge (e);
1789 : 112 : cfg_altered = true;
1790 : : }
1791 : : else
1792 : 147 : ei_next (&ei);
1793 : : }
1794 : : }
1795 : : }
1796 : :
1797 : : /* Now remove the unreachable blocks. */
1798 : 8096455 : if (cfg_altered)
1799 : : {
1800 : 20120 : basic_block prev_bb;
1801 : :
1802 : 20120 : find_unreachable_blocks ();
1803 : :
1804 : : /* Delete all unreachable basic blocks in reverse dominator order. */
1805 : 20120 : for (bb = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb;
1806 : 808432 : bb != ENTRY_BLOCK_PTR_FOR_FN (cfun); bb = prev_bb)
1807 : : {
1808 : 788312 : prev_bb = bb->prev_bb;
1809 : :
1810 : 788312 : if ((bb_contains_live_stmts
1811 : 788266 : && !bitmap_bit_p (bb_contains_live_stmts, bb->index))
1812 : 1362345 : || !(bb->flags & BB_REACHABLE))
1813 : : {
1814 : : /* Since we don't track liveness of virtual PHI nodes, it is
1815 : : possible that we rendered some PHI nodes unreachable while
1816 : : they are still in use. Mark them for renaming. */
1817 : 238834 : for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1818 : 24554 : gsi_next (&gsi))
1819 : 73660 : if (virtual_operand_p (gimple_phi_result (gsi.phi ())))
1820 : : {
1821 : 24552 : bool found = false;
1822 : 24552 : imm_use_iterator iter;
1823 : :
1824 : 24743 : FOR_EACH_IMM_USE_STMT (stmt, iter,
1825 : : gimple_phi_result (gsi.phi ()))
1826 : : {
1827 : 23977 : if (!(gimple_bb (stmt)->flags & BB_REACHABLE))
1828 : 163 : continue;
1829 : 23814 : if (gimple_code (stmt) == GIMPLE_PHI
1830 : 23814 : || gimple_plf (stmt, STMT_NECESSARY))
1831 : : {
1832 : : found = true;
1833 : : break;
1834 : : }
1835 : 24552 : }
1836 : 24552 : if (found)
1837 : 23786 : mark_virtual_phi_result_for_renaming (gsi.phi ());
1838 : : }
1839 : :
1840 : 214280 : if (!(bb->flags & BB_REACHABLE))
1841 : : {
1842 : : /* Speed up the removal of blocks that don't
1843 : : dominate others. Walking backwards, this should
1844 : : be the common case. ??? Do we need to recompute
1845 : : dominators because of cfg_altered? */
1846 : 45674 : if (!first_dom_son (CDI_DOMINATORS, bb))
1847 : 45135 : delete_basic_block (bb);
1848 : : else
1849 : : {
1850 : 539 : h = get_all_dominated_blocks (CDI_DOMINATORS, bb);
1851 : :
1852 : 2318 : while (h.length ())
1853 : : {
1854 : 1779 : bb = h.pop ();
1855 : 1779 : prev_bb = bb->prev_bb;
1856 : : /* Rearrangements to the CFG may have failed
1857 : : to update the dominators tree, so that
1858 : : formerly-dominated blocks are now
1859 : : otherwise reachable. */
1860 : 1779 : if (!!(bb->flags & BB_REACHABLE))
1861 : 0 : continue;
1862 : 1779 : delete_basic_block (bb);
1863 : : }
1864 : :
1865 : 539 : h.release ();
1866 : : }
1867 : : }
1868 : : }
1869 : : }
1870 : 20120 : if (bb_contains_live_stmts)
1871 : 20112 : propagate_counts ();
1872 : : }
1873 : :
1874 : 8096455 : if (bb_postorder)
1875 : 20079 : free (bb_postorder);
1876 : 8096455 : bb_postorder = NULL;
1877 : :
1878 : 8096455 : return something_changed;
1879 : 8096455 : }
1880 : :
1881 : :
1882 : : /* Print out removed statement statistics. */
1883 : :
1884 : : static void
1885 : 215 : print_stats (void)
1886 : : {
1887 : 215 : float percg;
1888 : :
1889 : 215 : percg = ((float) stats.removed / (float) stats.total) * 100;
1890 : 215 : fprintf (dump_file, "Removed %d of %d statements (%d%%)\n",
1891 : : stats.removed, stats.total, (int) percg);
1892 : :
1893 : 215 : if (stats.total_phis == 0)
1894 : : percg = 0;
1895 : : else
1896 : 42 : percg = ((float) stats.removed_phis / (float) stats.total_phis) * 100;
1897 : :
1898 : 215 : fprintf (dump_file, "Removed %d of %d PHI nodes (%d%%)\n",
1899 : : stats.removed_phis, stats.total_phis, (int) percg);
1900 : 215 : }
1901 : :
1902 : : /* Initialization for this pass. Set up the used data structures. */
1903 : :
1904 : : static void
1905 : 8096455 : tree_dce_init (bool aggressive)
1906 : : {
1907 : 8096455 : memset ((void *) &stats, 0, sizeof (stats));
1908 : :
1909 : 8096455 : if (aggressive)
1910 : : {
1911 : 3544994 : last_stmt_necessary = sbitmap_alloc (last_basic_block_for_fn (cfun));
1912 : 3544994 : bitmap_clear (last_stmt_necessary);
1913 : 3544994 : bb_contains_live_stmts = sbitmap_alloc (last_basic_block_for_fn (cfun));
1914 : 3544994 : bitmap_clear (bb_contains_live_stmts);
1915 : : }
1916 : :
1917 : 16192910 : processed = sbitmap_alloc (num_ssa_names + 1);
1918 : 8096455 : bitmap_clear (processed);
1919 : :
1920 : 8096455 : worklist.create (64);
1921 : 8096455 : cfg_altered = false;
1922 : 8096455 : }
1923 : :
1924 : : /* Cleanup after this pass. */
1925 : :
1926 : : static void
1927 : 8096455 : tree_dce_done (bool aggressive)
1928 : : {
1929 : 8096455 : if (aggressive)
1930 : : {
1931 : 3544994 : delete cd;
1932 : 3544994 : sbitmap_free (visited_control_parents);
1933 : 3544994 : sbitmap_free (last_stmt_necessary);
1934 : 3544994 : sbitmap_free (bb_contains_live_stmts);
1935 : 3544994 : bb_contains_live_stmts = NULL;
1936 : : }
1937 : :
1938 : 8096455 : sbitmap_free (processed);
1939 : :
1940 : 8096455 : worklist.release ();
1941 : 8096455 : }
1942 : :
1943 : : /* Sort PHI argument values for make_forwarders_with_degenerate_phis. */
1944 : :
1945 : : static int
1946 : 28298383 : sort_phi_args (const void *a_, const void *b_)
1947 : : {
1948 : 28298383 : auto *a = (const std::pair<edge, hashval_t> *) a_;
1949 : 28298383 : auto *b = (const std::pair<edge, hashval_t> *) b_;
1950 : 28298383 : hashval_t ha = a->second;
1951 : 28298383 : hashval_t hb = b->second;
1952 : 28298383 : if (ha < hb)
1953 : : return -1;
1954 : 17582651 : else if (ha > hb)
1955 : : return 1;
1956 : 8582115 : else if (a->first->dest_idx < b->first->dest_idx)
1957 : : return -1;
1958 : 4495574 : else if (a->first->dest_idx > b->first->dest_idx)
1959 : : return 1;
1960 : : else
1961 : 0 : return 0;
1962 : : }
1963 : :
1964 : : /* Look for a non-virtual PHIs and make a forwarder block when all PHIs
1965 : : have the same argument on a set of edges. This is to not consider
1966 : : control dependences of individual edges for same values but only for
1967 : : the common set. */
1968 : :
1969 : : static unsigned
1970 : 3544994 : make_forwarders_with_degenerate_phis (function *fn)
1971 : : {
1972 : 3544994 : unsigned todo = 0;
1973 : :
1974 : 3544994 : basic_block bb;
1975 : 33903305 : FOR_EACH_BB_FN (bb, fn)
1976 : : {
1977 : : /* Only PHIs with three or more arguments have opportunities. */
1978 : 30358311 : if (EDGE_COUNT (bb->preds) < 3)
1979 : 30042539 : continue;
1980 : : /* Do not touch loop headers or blocks with abnormal predecessors.
1981 : : ??? This is to avoid creating valid loops here, see PR103458.
1982 : : We might want to improve things to either explicitely add those
1983 : : loops or at least consider blocks with no backedges. */
1984 : 1278059 : if (bb->loop_father->header == bb
1985 : 1276183 : || bb_has_abnormal_pred (bb))
1986 : 1876 : continue;
1987 : :
1988 : : /* Take one PHI node as template to look for identical
1989 : : arguments. Build a vector of candidates forming sets
1990 : : of argument edges with equal values. Note optimality
1991 : : depends on the particular choice of the template PHI
1992 : : since equal arguments are unordered leaving other PHIs
1993 : : with more than one set of equal arguments within this
1994 : : argument range unsorted. We'd have to break ties by
1995 : : looking at other PHI nodes. */
1996 : 1274307 : gphi_iterator gsi = gsi_start_nonvirtual_phis (bb);
1997 : 1274307 : if (gsi_end_p (gsi))
1998 : 754253 : continue;
1999 : 520054 : gphi *phi = gsi.phi ();
2000 : 520054 : auto_vec<std::pair<edge, hashval_t>, 8> args;
2001 : 520054 : bool need_resort = false;
2002 : 2976492 : for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
2003 : : {
2004 : 2456438 : edge e = gimple_phi_arg_edge (phi, i);
2005 : : /* Skip abnormal edges since we cannot redirect them. */
2006 : 2456438 : if (e->flags & EDGE_ABNORMAL)
2007 : 2456438 : continue;
2008 : : /* Skip loop exit edges when we are in loop-closed SSA form
2009 : : since the forwarder we'd create does not have a PHI node. */
2010 : 2456438 : if (loops_state_satisfies_p (LOOP_CLOSED_SSA)
2011 : 2456438 : && loop_exit_edge_p (e->src->loop_father, e))
2012 : 17887 : continue;
2013 : :
2014 : 2438551 : tree arg = gimple_phi_arg_def (phi, i);
2015 : 2438551 : if (!CONSTANT_CLASS_P (arg) && TREE_CODE (arg) != SSA_NAME)
2016 : 2438551 : need_resort = true;
2017 : 2438551 : args.safe_push (std::make_pair (e, iterative_hash_expr (arg, 0)));
2018 : : }
2019 : 520054 : if (args.length () < 2)
2020 : 4073 : continue;
2021 : 515981 : args.qsort (sort_phi_args);
2022 : : /* The above sorting can be different between -g and -g0, as e.g. decls
2023 : : can have different uids (-g could have bigger gaps in between them).
2024 : : So, only use that to determine which args are equal, then change
2025 : : second from hash value to smallest dest_idx of the edges which have
2026 : : equal argument and sort again. If all the phi arguments are
2027 : : constants or SSA_NAME, there is no need for the second sort, the hash
2028 : : values are stable in that case. */
2029 : 515981 : hashval_t hash = args[0].second;
2030 : 515981 : args[0].second = args[0].first->dest_idx;
2031 : 515981 : bool any_equal = false;
2032 : 2436021 : for (unsigned i = 1; i < args.length (); ++i)
2033 : 1920040 : if (hash == args[i].second
2034 : 2661911 : && operand_equal_p (PHI_ARG_DEF_FROM_EDGE (phi, args[i - 1].first),
2035 : 741871 : PHI_ARG_DEF_FROM_EDGE (phi, args[i].first)))
2036 : : {
2037 : 741379 : args[i].second = args[i - 1].second;
2038 : 741379 : any_equal = true;
2039 : : }
2040 : : else
2041 : : {
2042 : 1178661 : hash = args[i].second;
2043 : 1178661 : args[i].second = args[i].first->dest_idx;
2044 : : }
2045 : 515981 : if (!any_equal)
2046 : 200209 : continue;
2047 : 315772 : if (need_resort)
2048 : 15431 : args.qsort (sort_phi_args);
2049 : :
2050 : : /* From the candidates vector now verify true candidates for
2051 : : forwarders and create them. */
2052 : 315772 : gphi *vphi = get_virtual_phi (bb);
2053 : 315772 : unsigned start = 0;
2054 : 2513774 : while (start < args.length () - 1)
2055 : : {
2056 : 788622 : unsigned i;
2057 : 2395202 : for (i = start + 1; i < args.length (); ++i)
2058 : 2214594 : if (args[start].second != args[i].second)
2059 : : break;
2060 : : /* args[start]..args[i-1] are equal. */
2061 : 788622 : if (start != i - 1)
2062 : : {
2063 : : /* Check all PHI nodes for argument equality. */
2064 : 462979 : bool equal = true;
2065 : 462979 : gphi_iterator gsi2 = gsi;
2066 : 462979 : gsi_next (&gsi2);
2067 : 996619 : for (; !gsi_end_p (gsi2); gsi_next (&gsi2))
2068 : : {
2069 : 705571 : gphi *phi2 = gsi2.phi ();
2070 : 1411142 : if (virtual_operand_p (gimple_phi_result (phi2)))
2071 : 184063 : continue;
2072 : 521508 : tree start_arg
2073 : 521508 : = PHI_ARG_DEF_FROM_EDGE (phi2, args[start].first);
2074 : 2342480 : for (unsigned j = start + 1; j < i; ++j)
2075 : : {
2076 : 4059012 : if (!operand_equal_p (start_arg,
2077 : 2029506 : PHI_ARG_DEF_FROM_EDGE
2078 : : (phi2, args[j].first)))
2079 : : {
2080 : : /* Another PHI might have a shorter set of
2081 : : equivalent args. Go for that. */
2082 : 208534 : i = j;
2083 : 208534 : if (j == start + 1)
2084 : : equal = false;
2085 : : break;
2086 : : }
2087 : : }
2088 : : if (!equal)
2089 : : break;
2090 : : }
2091 : 462979 : if (equal)
2092 : : {
2093 : : /* If we are asked to forward all edges the block
2094 : : has all degenerate PHIs. Do nothing in that case. */
2095 : 291048 : if (start == 0
2096 : 146045 : && i == args.length ()
2097 : 296600 : && args.length () == gimple_phi_num_args (phi))
2098 : : break;
2099 : : /* Instead of using make_forwarder_block we are
2100 : : rolling our own variant knowing that the forwarder
2101 : : does not need PHI nodes apart from eventually
2102 : : a virtual one. */
2103 : 285655 : auto_vec<tree, 8> vphi_args;
2104 : 285655 : if (vphi)
2105 : : {
2106 : 180121 : vphi_args.reserve_exact (i - start);
2107 : 694209 : for (unsigned j = start; j < i; ++j)
2108 : 514088 : vphi_args.quick_push
2109 : 514088 : (PHI_ARG_DEF_FROM_EDGE (vphi, args[j].first));
2110 : : }
2111 : 285655 : free_dominance_info (fn, CDI_DOMINATORS);
2112 : 285655 : basic_block forwarder = split_edge (args[start].first);
2113 : 285655 : profile_count count = profile_count::zero ();
2114 : 285655 : bool irr = false;
2115 : 834774 : for (unsigned j = start + 1; j < i; ++j)
2116 : : {
2117 : 549119 : edge e = args[j].first;
2118 : 549119 : if (e->flags & EDGE_IRREDUCIBLE_LOOP)
2119 : 1464 : irr = true;
2120 : 549119 : redirect_edge_and_branch_force (e, forwarder);
2121 : 549119 : redirect_edge_var_map_clear (e);
2122 : 549119 : count += e->count ();
2123 : : }
2124 : 285655 : forwarder->count = count;
2125 : 285655 : if (irr)
2126 : : {
2127 : 1202 : forwarder->flags |= BB_IRREDUCIBLE_LOOP;
2128 : 1202 : single_succ_edge (forwarder)->flags
2129 : 1202 : |= EDGE_IRREDUCIBLE_LOOP;
2130 : : }
2131 : :
2132 : 285655 : if (vphi)
2133 : : {
2134 : 180121 : tree def = copy_ssa_name (vphi_args[0]);
2135 : 180121 : gphi *vphi_copy = create_phi_node (def, forwarder);
2136 : 694209 : for (unsigned j = start; j < i; ++j)
2137 : 1028176 : add_phi_arg (vphi_copy, vphi_args[j - start],
2138 : 514088 : args[j].first, UNKNOWN_LOCATION);
2139 : 180121 : SET_PHI_ARG_DEF
2140 : : (vphi, single_succ_edge (forwarder)->dest_idx, def);
2141 : : }
2142 : 285655 : todo |= TODO_cleanup_cfg;
2143 : 285655 : }
2144 : : }
2145 : : /* Continue searching for more opportunities. */
2146 : : start = i;
2147 : : }
2148 : 520054 : }
2149 : 3544994 : return todo;
2150 : : }
2151 : :
2152 : : /* Main routine to eliminate dead code.
2153 : :
2154 : : AGGRESSIVE controls the aggressiveness of the algorithm.
2155 : : In conservative mode, we ignore control dependence and simply declare
2156 : : all but the most trivially dead branches necessary. This mode is fast.
2157 : : In aggressive mode, control dependences are taken into account, which
2158 : : results in more dead code elimination, but at the cost of some time. */
2159 : :
2160 : : static unsigned int
2161 : 8096455 : perform_tree_ssa_dce (bool aggressive)
2162 : : {
2163 : 8096455 : bool something_changed = 0;
2164 : 8096455 : unsigned todo = 0;
2165 : :
2166 : : /* Preheaders are needed for SCEV to work.
2167 : : Simple lateches and recorded exits improve chances that loop will
2168 : : proved to be finite in testcases such as in loop-15.c and loop-24.c */
2169 : 8096455 : bool in_loop_pipeline = scev_initialized_p ();
2170 : 8096455 : if (aggressive && ! in_loop_pipeline)
2171 : : {
2172 : 3320481 : loop_optimizer_init (LOOPS_NORMAL
2173 : : | LOOPS_HAVE_RECORDED_EXITS);
2174 : 3320481 : scev_initialize ();
2175 : : }
2176 : :
2177 : 8096455 : if (aggressive)
2178 : 3544994 : todo |= make_forwarders_with_degenerate_phis (cfun);
2179 : :
2180 : 8096455 : calculate_dominance_info (CDI_DOMINATORS);
2181 : :
2182 : 8096455 : tree_dce_init (aggressive);
2183 : :
2184 : 8096455 : if (aggressive)
2185 : : {
2186 : : /* Compute control dependence. */
2187 : 3544994 : calculate_dominance_info (CDI_POST_DOMINATORS);
2188 : 3544994 : cd = new control_dependences ();
2189 : :
2190 : 7089988 : visited_control_parents =
2191 : 3544994 : sbitmap_alloc (last_basic_block_for_fn (cfun));
2192 : 3544994 : bitmap_clear (visited_control_parents);
2193 : :
2194 : 3544994 : mark_dfs_back_edges ();
2195 : : }
2196 : :
2197 : 8096455 : find_obviously_necessary_stmts (aggressive);
2198 : :
2199 : 8096455 : if (aggressive && ! in_loop_pipeline)
2200 : : {
2201 : 3320481 : scev_finalize ();
2202 : 3320481 : loop_optimizer_finalize ();
2203 : : }
2204 : :
2205 : 8096455 : longest_chain = 0;
2206 : 8096455 : total_chain = 0;
2207 : 8096455 : nr_walks = 0;
2208 : 8096455 : chain_ovfl = false;
2209 : 8096455 : visited = BITMAP_ALLOC (NULL);
2210 : 8096455 : propagate_necessity (aggressive);
2211 : 8096455 : BITMAP_FREE (visited);
2212 : :
2213 : 8096455 : something_changed |= eliminate_unnecessary_stmts (aggressive);
2214 : 8096455 : something_changed |= cfg_altered;
2215 : :
2216 : : /* We do not update postdominators, so free them unconditionally. */
2217 : 8096455 : free_dominance_info (CDI_POST_DOMINATORS);
2218 : :
2219 : : /* If we removed paths in the CFG, then we need to update
2220 : : dominators as well. I haven't investigated the possibility
2221 : : of incrementally updating dominators. */
2222 : 8096455 : if (cfg_altered)
2223 : 20120 : free_dominance_info (CDI_DOMINATORS);
2224 : :
2225 : 8096455 : statistics_counter_event (cfun, "Statements deleted", stats.removed);
2226 : 8096455 : statistics_counter_event (cfun, "PHI nodes deleted", stats.removed_phis);
2227 : :
2228 : : /* Debugging dumps. */
2229 : 8096455 : if (dump_file && (dump_flags & (TDF_STATS|TDF_DETAILS)))
2230 : 215 : print_stats ();
2231 : :
2232 : 8096455 : tree_dce_done (aggressive);
2233 : :
2234 : 8096455 : if (something_changed)
2235 : : {
2236 : 841794 : free_numbers_of_iterations_estimates (cfun);
2237 : 841794 : if (in_loop_pipeline)
2238 : 62826 : scev_reset ();
2239 : : todo |= TODO_update_ssa | TODO_cleanup_cfg;
2240 : : }
2241 : 8096455 : return todo;
2242 : : }
2243 : :
2244 : : namespace {
2245 : :
2246 : : const pass_data pass_data_dce =
2247 : : {
2248 : : GIMPLE_PASS, /* type */
2249 : : "dce", /* name */
2250 : : OPTGROUP_NONE, /* optinfo_flags */
2251 : : TV_TREE_DCE, /* tv_id */
2252 : : ( PROP_cfg | PROP_ssa ), /* properties_required */
2253 : : 0, /* properties_provided */
2254 : : 0, /* properties_destroyed */
2255 : : 0, /* todo_flags_start */
2256 : : 0, /* todo_flags_finish */
2257 : : };
2258 : :
2259 : : class pass_dce_base : public gimple_opt_pass
2260 : : {
2261 : : public:
2262 : : /* opt_pass methods: */
2263 : 8099750 : bool gate (function *) final override { return flag_tree_dce != 0; }
2264 : 2890800 : void set_pass_param (unsigned n, bool param) final override
2265 : : {
2266 : 2890800 : gcc_assert (n == 0 || n == 1);
2267 : 2890800 : if (n == 0)
2268 : 1734480 : update_address_taken_p = param;
2269 : 1156320 : else if (n == 1)
2270 : 1156320 : remove_unused_locals_p = param;
2271 : 2890800 : }
2272 : :
2273 : : protected:
2274 : 3179880 : pass_dce_base (const pass_data &data, gcc::context *ctxt)
2275 : 6359760 : : gimple_opt_pass (data, ctxt)
2276 : : {}
2277 : 8096455 : unsigned int execute_dce (function *, bool aggressive)
2278 : : {
2279 : 8096455 : return (perform_tree_ssa_dce (aggressive)
2280 : 8096455 : | (remove_unused_locals_p ? TODO_remove_unused_locals : 0)
2281 : 8096455 : | (update_address_taken_p ? TODO_update_address_taken : 0));
2282 : : }
2283 : :
2284 : : private:
2285 : : bool update_address_taken_p = false;
2286 : : bool remove_unused_locals_p = false;
2287 : : }; // class pass_dce_base
2288 : :
2289 : :
2290 : : class pass_dce : public pass_dce_base
2291 : : {
2292 : : public:
2293 : 2312640 : pass_dce (gcc::context *ctxt)
2294 : 4625280 : : pass_dce_base (pass_data_dce, ctxt)
2295 : : {}
2296 : :
2297 : : /* opt_pass methods: */
2298 : 2023560 : opt_pass * clone () final override { return new pass_dce (m_ctxt); }
2299 : 4354570 : unsigned int execute (function *func) final override
2300 : : {
2301 : 4354570 : return execute_dce (func, /*aggressive=*/false);
2302 : : }
2303 : :
2304 : : }; // class pass_dce
2305 : :
2306 : : } // anon namespace
2307 : :
2308 : : gimple_opt_pass *
2309 : 289080 : make_pass_dce (gcc::context *ctxt)
2310 : : {
2311 : 289080 : return new pass_dce (ctxt);
2312 : : }
2313 : :
2314 : : namespace {
2315 : :
2316 : : const pass_data pass_data_cd_dce =
2317 : : {
2318 : : GIMPLE_PASS, /* type */
2319 : : "cddce", /* name */
2320 : : OPTGROUP_NONE, /* optinfo_flags */
2321 : : TV_TREE_CD_DCE, /* tv_id */
2322 : : ( PROP_cfg | PROP_ssa ), /* properties_required */
2323 : : 0, /* properties_provided */
2324 : : 0, /* properties_destroyed */
2325 : : 0, /* todo_flags_start */
2326 : : 0, /* todo_flags_finish */
2327 : : };
2328 : :
2329 : : class pass_cd_dce : public pass_dce_base
2330 : : {
2331 : : public:
2332 : 867240 : pass_cd_dce (gcc::context *ctxt)
2333 : 1734480 : : pass_dce_base (pass_data_cd_dce, ctxt)
2334 : : {}
2335 : :
2336 : : /* opt_pass methods: */
2337 : 578160 : opt_pass * clone () final override { return new pass_cd_dce (m_ctxt); }
2338 : 3741885 : unsigned int execute (function *func) final override
2339 : : {
2340 : 3741885 : return execute_dce (func, /*aggressive=*/optimize >= 2);
2341 : : }
2342 : :
2343 : : }; // class pass_cd_dce
2344 : :
2345 : : } // anon namespace
2346 : :
2347 : : gimple_opt_pass *
2348 : 289080 : make_pass_cd_dce (gcc::context *ctxt)
2349 : : {
2350 : 289080 : return new pass_cd_dce (ctxt);
2351 : : }
2352 : :
2353 : :
2354 : : /* A cheap DCE interface. WORKLIST is a list of possibly dead stmts and
2355 : : is consumed by this function. The function has linear complexity in
2356 : : the number of dead stmts with a constant factor like the average SSA
2357 : : use operands number. */
2358 : :
2359 : : void
2360 : 38024339 : simple_dce_from_worklist (bitmap worklist, bitmap need_eh_cleanup)
2361 : : {
2362 : 38024339 : int phiremoved = 0;
2363 : 38024339 : int stmtremoved = 0;
2364 : 73399976 : while (! bitmap_empty_p (worklist))
2365 : : {
2366 : : /* Pop item. */
2367 : 35375637 : unsigned i = bitmap_clear_first_set_bit (worklist);
2368 : :
2369 : 35375637 : tree def = ssa_name (i);
2370 : : /* Removed by somebody else or still in use.
2371 : : Note use in itself for a phi node is not counted as still in use. */
2372 : 35375637 : if (!def)
2373 : 14967072 : continue;
2374 : 35210671 : if (!has_zero_uses (def))
2375 : : {
2376 : 14763826 : gimple *def_stmt = SSA_NAME_DEF_STMT (def);
2377 : :
2378 : 14763826 : if (gimple_code (def_stmt) != GIMPLE_PHI)
2379 : 14759914 : continue;
2380 : :
2381 : 2863845 : gimple *use_stmt;
2382 : 2863845 : imm_use_iterator use_iter;
2383 : 2863845 : bool canremove = true;
2384 : :
2385 : 2965847 : FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, def)
2386 : : {
2387 : : /* Ignore debug statements. */
2388 : 2961935 : if (is_gimple_debug (use_stmt))
2389 : 96116 : continue;
2390 : 2865819 : if (use_stmt != def_stmt)
2391 : : {
2392 : : canremove = false;
2393 : : break;
2394 : : }
2395 : 2863845 : }
2396 : 2863845 : if (!canremove)
2397 : 2859933 : continue;
2398 : : }
2399 : :
2400 : 20450757 : gimple *t = SSA_NAME_DEF_STMT (def);
2401 : 20450757 : if (gimple_has_side_effects (t))
2402 : 39704 : continue;
2403 : :
2404 : : /* The defining statement needs to be defining only this name.
2405 : : ASM is the only statement that can define more than one
2406 : : name. */
2407 : 20411053 : if (is_a<gasm *>(t)
2408 : 20411053 : && !single_ssa_def_operand (t, SSA_OP_ALL_DEFS))
2409 : 15 : continue;
2410 : :
2411 : : /* Don't remove statements that are needed for non-call
2412 : : eh to work. */
2413 : 20411038 : if (stmt_unremovable_because_of_non_call_eh_p (cfun, t))
2414 : 2473 : continue;
2415 : :
2416 : : /* Tell the caller that we removed a statement that might
2417 : : throw so it could cleanup the cfg for that block. */
2418 : 20408565 : if (need_eh_cleanup && stmt_could_throw_p (cfun, t))
2419 : 137 : bitmap_set_bit (need_eh_cleanup, gimple_bb (t)->index);
2420 : :
2421 : : /* Add uses to the worklist. */
2422 : 20408565 : ssa_op_iter iter;
2423 : 20408565 : use_operand_p use_p;
2424 : 57875413 : FOR_EACH_PHI_OR_STMT_USE (use_p, t, iter, SSA_OP_USE)
2425 : : {
2426 : 17058283 : tree use = USE_FROM_PTR (use_p);
2427 : 17058283 : if (TREE_CODE (use) == SSA_NAME
2428 : 17058283 : && ! SSA_NAME_IS_DEFAULT_DEF (use))
2429 : 15146986 : bitmap_set_bit (worklist, SSA_NAME_VERSION (use));
2430 : : }
2431 : :
2432 : : /* Remove stmt. */
2433 : 20408565 : if (dump_file && (dump_flags & TDF_DETAILS))
2434 : : {
2435 : 290 : fprintf (dump_file, "Removing dead stmt:");
2436 : 290 : print_gimple_stmt (dump_file, t, 0);
2437 : : }
2438 : 20408565 : gimple_stmt_iterator gsi = gsi_for_stmt (t);
2439 : 20408565 : if (gimple_code (t) == GIMPLE_PHI)
2440 : : {
2441 : 2946372 : remove_phi_node (&gsi, true);
2442 : 2946372 : phiremoved++;
2443 : : }
2444 : : else
2445 : : {
2446 : 17462193 : unlink_stmt_vdef (t);
2447 : 17462193 : gsi_remove (&gsi, true);
2448 : 17462193 : release_defs (t);
2449 : 17462193 : stmtremoved++;
2450 : : }
2451 : : }
2452 : 38024339 : statistics_counter_event (cfun, "PHIs removed",
2453 : : phiremoved);
2454 : 38024339 : statistics_counter_event (cfun, "Statements removed",
2455 : : stmtremoved);
2456 : 38024339 : }
|
