Line data Source code
1 : /* CFG cleanup for trees.
2 : Copyright (C) 2001-2026 Free Software Foundation, Inc.
3 :
4 : This file is part of GCC.
5 :
6 : GCC is free software; you can redistribute it and/or modify
7 : it under the terms of the GNU General Public License as published by
8 : the Free Software Foundation; either version 3, or (at your option)
9 : any later version.
10 :
11 : GCC is distributed in the hope that it will be useful,
12 : but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 : GNU General Public License for more details.
15 :
16 : You should have received a copy of the GNU General Public License
17 : along with GCC; see the file COPYING3. If not see
18 : <http://www.gnu.org/licenses/>. */
19 :
20 : #include "config.h"
21 : #include "system.h"
22 : #include "coretypes.h"
23 : #include "backend.h"
24 : #include "rtl.h"
25 : #include "tree.h"
26 : #include "gimple.h"
27 : #include "cfghooks.h"
28 : #include "tree-pass.h"
29 : #include "ssa.h"
30 : #include "diagnostic-core.h"
31 : #include "fold-const.h"
32 : #include "cfganal.h"
33 : #include "cfgcleanup.h"
34 : #include "tree-eh.h"
35 : #include "gimplify.h"
36 : #include "gimple-iterator.h"
37 : #include "tree-cfg.h"
38 : #include "tree-ssa-loop-manip.h"
39 : #include "tree-dfa.h"
40 : #include "tree-ssa.h"
41 : #include "cfgloop.h"
42 : #include "tree-scalar-evolution.h"
43 : #include "gimple-match.h"
44 : #include "gimple-fold.h"
45 : #include "tree-ssa-loop-niter.h"
46 : #include "cgraph.h"
47 : #include "tree-into-ssa.h"
48 : #include "tree-cfgcleanup.h"
49 : #include "gimple-pretty-print.h"
50 : #include "target.h"
51 :
52 :
53 : /* The set of blocks in that at least one of the following changes happened:
54 : -- the statement at the end of the block was changed
55 : -- the block was newly created
56 : -- the set of the predecessors of the block changed
57 : -- the set of the successors of the block changed
58 : ??? Maybe we could track these changes separately, since they determine
59 : what cleanups it makes sense to try on the block. */
60 : bitmap cfgcleanup_altered_bbs;
61 :
62 : /* Remove any fallthru edge from EV. Return true if an edge was removed. */
63 :
64 : static bool
65 22502171 : remove_fallthru_edge (vec<edge, va_gc> *ev)
66 : {
67 22502171 : edge_iterator ei;
68 22502171 : edge e;
69 :
70 25146521 : FOR_EACH_EDGE (e, ei, ev)
71 2675438 : if ((e->flags & EDGE_FALLTHRU) != 0)
72 : {
73 31088 : if (e->flags & EDGE_COMPLEX)
74 0 : e->flags &= ~EDGE_FALLTHRU;
75 : else
76 31088 : remove_edge_and_dominated_blocks (e);
77 31088 : return true;
78 : }
79 : return false;
80 : }
81 :
82 : /* Convert a SWTCH with single non-default case to gcond and replace it
83 : at GSI. */
84 :
85 : static bool
86 778886 : convert_single_case_switch (gswitch *swtch, gimple_stmt_iterator &gsi)
87 : {
88 778886 : if (gimple_switch_num_labels (swtch) != 2)
89 : return false;
90 :
91 11896 : tree index = gimple_switch_index (swtch);
92 11896 : tree label = gimple_switch_label (swtch, 1);
93 11896 : tree low = CASE_LOW (label);
94 11896 : tree high = CASE_HIGH (label);
95 :
96 11896 : basic_block default_bb = gimple_switch_default_bb (cfun, swtch);
97 11896 : basic_block case_bb = label_to_block (cfun, CASE_LABEL (label));
98 :
99 11896 : basic_block bb = gimple_bb (swtch);
100 11896 : gcond *cond;
101 :
102 : /* Replace switch statement with condition statement. */
103 11896 : if (high)
104 : {
105 1071 : tree lhs, rhs;
106 1071 : if (range_check_type (TREE_TYPE (index)) == NULL_TREE)
107 0 : return false;
108 1071 : generate_range_test (bb, index, low, high, &lhs, &rhs);
109 1071 : cond = gimple_build_cond (LE_EXPR, lhs, rhs, NULL_TREE, NULL_TREE);
110 : }
111 : else
112 10825 : cond = gimple_build_cond (EQ_EXPR, index,
113 10825 : fold_convert (TREE_TYPE (index), low),
114 : NULL_TREE, NULL_TREE);
115 :
116 11896 : gsi_replace (&gsi, cond, true);
117 :
118 : /* Update edges. */
119 11896 : edge case_edge = find_edge (bb, case_bb);
120 11896 : edge default_edge = find_edge (bb, default_bb);
121 :
122 11896 : case_edge->flags |= EDGE_TRUE_VALUE;
123 11896 : default_edge->flags |= EDGE_FALSE_VALUE;
124 11896 : return true;
125 : }
126 :
127 : /* Canonicalize _Bool == 0 and _Bool != 1 to _Bool != 0 of STMT in BB by
128 : swapping edges of the BB. */
129 : bool
130 177046649 : canonicalize_bool_cond (gcond *stmt, basic_block bb)
131 : {
132 177046649 : tree rhs1 = gimple_cond_lhs (stmt);
133 177046649 : tree rhs2 = gimple_cond_rhs (stmt);
134 177046649 : enum tree_code code = gimple_cond_code (stmt);
135 177046649 : if (code != EQ_EXPR && code != NE_EXPR)
136 : return false;
137 133290429 : if (TREE_CODE (TREE_TYPE (rhs1)) != BOOLEAN_TYPE
138 133290429 : && (!INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
139 77009876 : || TYPE_PRECISION (TREE_TYPE (rhs1)) != 1))
140 : return false;
141 :
142 : /* Canonicalize _Bool == 0 and _Bool != 1 to _Bool != 0 by swapping edges. */
143 23533689 : if (code == EQ_EXPR && !integer_zerop (rhs2))
144 : return false;
145 23386526 : if (code == NE_EXPR && !integer_onep (rhs2))
146 : return false;
147 :
148 131306 : gimple_cond_set_code (stmt, NE_EXPR);
149 131306 : gimple_cond_set_rhs (stmt, build_zero_cst (TREE_TYPE (rhs1)));
150 131306 : EDGE_SUCC (bb, 0)->flags ^= (EDGE_TRUE_VALUE|EDGE_FALSE_VALUE);
151 131306 : EDGE_SUCC (bb, 1)->flags ^= (EDGE_TRUE_VALUE|EDGE_FALSE_VALUE);
152 :
153 131306 : if (dump_file)
154 : {
155 1 : fprintf (dump_file, " Swapped '");
156 1 : print_gimple_expr (dump_file, stmt, 0);
157 1 : fprintf (dump_file, "'\n");
158 : }
159 : return true;
160 : }
161 :
162 : /* Disconnect an unreachable block in the control expression starting
163 : at block BB. */
164 :
165 : static bool
166 158982628 : cleanup_control_expr_graph (basic_block bb, gimple_stmt_iterator gsi)
167 : {
168 158982628 : edge taken_edge;
169 158982628 : bool retval = false;
170 158982628 : gimple *stmt = gsi_stmt (gsi);
171 :
172 158982628 : if (!single_succ_p (bb))
173 : {
174 158976359 : edge e;
175 158976359 : edge_iterator ei;
176 158976359 : tree val = NULL_TREE;
177 :
178 : /* Try to convert a switch with just a single non-default case to
179 : GIMPLE condition. */
180 158976359 : if (gimple_code (stmt) == GIMPLE_SWITCH
181 158976359 : && convert_single_case_switch (as_a<gswitch *> (stmt), gsi))
182 11896 : stmt = gsi_stmt (gsi);
183 :
184 158976359 : if (gimple_code (stmt) == GIMPLE_COND)
185 158209369 : canonicalize_bool_cond (as_a<gcond*> (stmt), bb);
186 :
187 158976359 : switch (gimple_code (stmt))
188 : {
189 158209369 : case GIMPLE_COND:
190 158209369 : {
191 158209369 : gimple_match_op res_op;
192 158209369 : if (gimple_simplify (stmt, &res_op, NULL, no_follow_ssa_edges,
193 : no_follow_ssa_edges)
194 158209369 : && res_op.code == INTEGER_CST)
195 2622204 : val = res_op.ops[0];
196 : }
197 158209369 : break;
198 :
199 766990 : case GIMPLE_SWITCH:
200 766990 : val = gimple_switch_index (as_a <gswitch *> (stmt));
201 766990 : break;
202 :
203 158976359 : default:
204 158976359 : ;
205 : }
206 158976359 : taken_edge = find_taken_edge (bb, val);
207 158976359 : if (!taken_edge)
208 156343111 : return false;
209 :
210 : /* Remove all the edges except the one that is always executed. */
211 7928522 : for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
212 : {
213 5295274 : if (e != taken_edge)
214 : {
215 2662026 : taken_edge->probability += e->probability;
216 2662026 : remove_edge_and_dominated_blocks (e);
217 2662026 : retval = true;
218 : }
219 : else
220 2633248 : ei_next (&ei);
221 : }
222 : }
223 : else
224 6269 : taken_edge = single_succ_edge (bb);
225 :
226 2639517 : bitmap_set_bit (cfgcleanup_altered_bbs, bb->index);
227 2639517 : gsi_remove (&gsi, true);
228 2639517 : taken_edge->flags &= ~(EDGE_TRUE_VALUE|EDGE_FALSE_VALUE);
229 2639517 : taken_edge->flags |= EDGE_FALLTHRU;
230 :
231 2639517 : return retval;
232 : }
233 :
234 : /* Cleanup the GF_CALL_CTRL_ALTERING flag according to
235 : to updated gimple_call_flags. */
236 :
237 : static void
238 356528965 : cleanup_call_ctrl_altering_flag (basic_block bb, gimple *bb_end)
239 : {
240 356528965 : if (!is_gimple_call (bb_end)
241 67321816 : || !gimple_call_ctrl_altering_p (bb_end)
242 379517054 : || (/* IFN_UNIQUE should be the last insn, to make checking for it
243 : as cheap as possible. */
244 22988089 : gimple_call_internal_p (bb_end)
245 459899 : && gimple_call_internal_unique_p (bb_end)))
246 : return;
247 :
248 22554398 : int flags = gimple_call_flags (bb_end);
249 22554398 : if (!(flags & ECF_NORETURN)
250 85400 : && (((flags & (ECF_CONST | ECF_PURE))
251 1910 : && !(flags & ECF_LOOPING_CONST_OR_PURE))
252 85230 : || (flags & ECF_LEAF)))
253 170 : gimple_call_set_ctrl_altering (bb_end, false);
254 : else
255 : {
256 22554228 : edge_iterator ei;
257 22554228 : edge e;
258 22554228 : bool found = false;
259 25270911 : FOR_EACH_EDGE (e, ei, bb->succs)
260 2835958 : if (e->flags & EDGE_FALLTHRU)
261 : found = true;
262 2724930 : else if (e->flags & EDGE_ABNORMAL)
263 : {
264 : found = false;
265 : break;
266 : }
267 : /* If there's no abnormal edge and a fallthru edge the call
268 : isn't control-altering anymore. */
269 22554228 : if (found)
270 28262 : gimple_call_set_ctrl_altering (bb_end, false);
271 : }
272 : }
273 :
274 : /* Try to remove superfluous control structures in basic block BB. Returns
275 : true if anything changes. */
276 :
277 : static bool
278 396092469 : cleanup_control_flow_bb (basic_block bb)
279 : {
280 396092469 : gimple_stmt_iterator gsi;
281 396092469 : bool retval = false;
282 396092469 : gimple *stmt;
283 :
284 : /* If the last statement of the block could throw and now cannot,
285 : we need to prune cfg. */
286 396092469 : retval |= gimple_purge_dead_eh_edges (bb);
287 :
288 396092469 : gsi = gsi_last_nondebug_bb (bb);
289 396092469 : if (gsi_end_p (gsi))
290 : return retval;
291 :
292 356528965 : stmt = gsi_stmt (gsi);
293 :
294 : /* Try to cleanup ctrl altering flag for call which ends bb. */
295 356528965 : cleanup_call_ctrl_altering_flag (bb, stmt);
296 :
297 356528965 : if (gimple_code (stmt) == GIMPLE_COND
298 356528965 : || gimple_code (stmt) == GIMPLE_SWITCH)
299 : {
300 317965256 : gcc_checking_assert (gsi_stmt (gsi_last_bb (bb)) == stmt);
301 158982628 : retval |= cleanup_control_expr_graph (bb, gsi);
302 : }
303 197546337 : else if (gimple_code (stmt) == GIMPLE_GOTO
304 6380 : && TREE_CODE (gimple_goto_dest (stmt)) == ADDR_EXPR
305 197546710 : && (TREE_CODE (TREE_OPERAND (gimple_goto_dest (stmt), 0))
306 : == LABEL_DECL))
307 : {
308 : /* If we had a computed goto which has a compile-time determinable
309 : destination, then we can eliminate the goto. */
310 171 : edge e;
311 171 : tree label;
312 171 : edge_iterator ei;
313 171 : basic_block target_block;
314 :
315 342 : gcc_checking_assert (gsi_stmt (gsi_last_bb (bb)) == stmt);
316 : /* First look at all the outgoing edges. Delete any outgoing
317 : edges which do not go to the right block. For the one
318 : edge which goes to the right block, fix up its flags. */
319 171 : label = TREE_OPERAND (gimple_goto_dest (stmt), 0);
320 171 : if (DECL_CONTEXT (label) != cfun->decl)
321 8 : return retval;
322 163 : target_block = label_to_block (cfun, label);
323 411 : for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
324 : {
325 248 : if (e->dest != target_block)
326 91 : remove_edge_and_dominated_blocks (e);
327 : else
328 : {
329 : /* Turn off the EDGE_ABNORMAL flag. */
330 157 : e->flags &= ~EDGE_ABNORMAL;
331 :
332 : /* And set EDGE_FALLTHRU. */
333 157 : e->flags |= EDGE_FALLTHRU;
334 157 : ei_next (&ei);
335 : }
336 : }
337 :
338 163 : bitmap_set_bit (cfgcleanup_altered_bbs, bb->index);
339 163 : bitmap_set_bit (cfgcleanup_altered_bbs, target_block->index);
340 :
341 : /* Remove the GOTO_EXPR as it is not needed. The CFG has all the
342 : relevant information we need. */
343 163 : gsi_remove (&gsi, true);
344 163 : retval = true;
345 : }
346 :
347 : /* Check for indirect calls that have been turned into
348 : noreturn calls. */
349 197546166 : else if (is_gimple_call (stmt)
350 197546166 : && gimple_call_noreturn_p (stmt))
351 : {
352 : /* If there are debug stmts after the noreturn call, remove them
353 : now, they should be all unreachable anyway. */
354 22502348 : for (gsi_next (&gsi); !gsi_end_p (gsi); )
355 177 : gsi_remove (&gsi, true);
356 22502171 : if (remove_fallthru_edge (bb->succs))
357 31088 : retval = true;
358 22502171 : tree lhs = gimple_call_lhs (stmt);
359 22502171 : if (!lhs
360 22502171 : || !should_remove_lhs_p (lhs))
361 22502152 : gimple_call_set_ctrl_altering (stmt, true);
362 : }
363 :
364 : return retval;
365 : }
366 :
367 : /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
368 : those alternatives are equal in each of the PHI nodes, then return
369 : true, else return false. */
370 :
371 : bool
372 4333864 : phi_alternatives_equal (basic_block dest, edge e1, edge e2)
373 : {
374 4333864 : int n1 = e1->dest_idx;
375 4333864 : int n2 = e2->dest_idx;
376 4333864 : gphi_iterator gsi;
377 :
378 4678384 : for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
379 : {
380 4627250 : gphi *phi = gsi.phi ();
381 4627250 : tree val1 = gimple_phi_arg_def (phi, n1);
382 4627250 : tree val2 = gimple_phi_arg_def (phi, n2);
383 :
384 4627250 : gcc_assert (val1 != NULL_TREE);
385 4627250 : gcc_assert (val2 != NULL_TREE);
386 :
387 4627250 : if (!operand_equal_for_phi_arg_p (val1, val2))
388 : return false;
389 : }
390 :
391 : return true;
392 : }
393 :
394 : /* Move debug stmts from the forwarder block SRC to DEST or PRED. */
395 :
396 : static void
397 27379656 : move_debug_stmts_from_forwarder (basic_block src,
398 : basic_block dest, bool dest_single_pred_p,
399 : basic_block pred, bool pred_single_succ_p)
400 : {
401 27379656 : if (!MAY_HAVE_DEBUG_STMTS)
402 9783554 : return;
403 :
404 : /* If we cannot move to the destination but to the predecessor do that. */
405 17669274 : if (!dest_single_pred_p && pred_single_succ_p)
406 : {
407 73177 : gimple_stmt_iterator gsi_to = gsi_last_bb (pred);
408 73177 : if (gsi_end_p (gsi_to) || !stmt_ends_bb_p (gsi_stmt (gsi_to)))
409 : {
410 73172 : for (gimple_stmt_iterator gsi = gsi_after_labels (src);
411 262255 : !gsi_end_p (gsi);)
412 : {
413 189083 : gimple *debug = gsi_stmt (gsi);
414 189083 : gcc_assert (is_gimple_debug (debug));
415 189083 : gsi_move_after (&gsi, &gsi_to);
416 : }
417 73172 : return;
418 : }
419 : }
420 :
421 : /* Else move to DEST or drop/reset them. */
422 17596102 : gimple_stmt_iterator gsi_to = gsi_after_labels (dest);
423 32579948 : for (gimple_stmt_iterator gsi = gsi_after_labels (src); !gsi_end_p (gsi);)
424 : {
425 14983846 : gimple *debug = gsi_stmt (gsi);
426 14983846 : gcc_assert (is_gimple_debug (debug));
427 : /* Move debug binds anyway, but not anything else like begin-stmt
428 : markers unless they are always valid at the destination. */
429 14983846 : if (dest_single_pred_p
430 14983846 : || gimple_debug_bind_p (debug))
431 : {
432 14012781 : gsi_move_before (&gsi, &gsi_to);
433 : /* Reset debug-binds that are not always valid at the destination.
434 : Simply dropping them can cause earlier values to become live,
435 : generating wrong debug information.
436 : ??? There are several things we could improve here. For
437 : one we might be able to move stmts to the predecessor.
438 : For anther, if the debug stmt is immediately followed by a
439 : (debug) definition in the destination (on a post-dominated path?)
440 : we can elide it without any bad effects. */
441 14012781 : if (!dest_single_pred_p)
442 : {
443 6009653 : gimple_debug_bind_reset_value (debug);
444 6009653 : update_stmt (debug);
445 : }
446 : }
447 : else
448 971065 : gsi_next (&gsi);
449 : }
450 : }
451 :
452 : /* Returns true if a phi of the basic block BB has an
453 : use of a ssa name that is used in an abnormal edge. */
454 :
455 : static bool
456 18802739 : bb_phis_references_abnormal_uses (basic_block bb)
457 : {
458 18802739 : auto phis = phi_nodes (bb);
459 18802739 : gimple_stmt_iterator i;
460 51042371 : for (i = gsi_start (phis); !gsi_end_p (i); gsi_next (&i))
461 : {
462 32246938 : gphi *phi = as_a<gphi*>(*i);
463 106737011 : for (unsigned indx = 0; indx < gimple_phi_num_args (phi); indx++)
464 : {
465 74497379 : tree value = gimple_phi_arg_def (phi, indx);
466 74497379 : if (TREE_CODE (value) == SSA_NAME
467 74497379 : && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (value))
468 : return true;
469 : }
470 : }
471 : return false;
472 : }
473 :
474 : /* Return true if basic block BB does nothing except pass control
475 : flow to another block and that we can safely insert a label at
476 : the start of the successor block and was removed.
477 :
478 : As a precondition, we require that BB be not equal to
479 : the entry block.
480 : If CAN_SPLIT is true, we can split the edge to have
481 : another bb with with the phi. */
482 :
483 : static bool
484 422015978 : maybe_remove_forwarder_block (basic_block bb, bool can_split = false)
485 : {
486 422015978 : gimple_stmt_iterator gsi;
487 422015978 : location_t locus;
488 :
489 : /* BB must have a single outgoing edge. */
490 804172356 : if (!single_succ_p (bb)
491 : /* BB may not be a predecessor of the exit block. */
492 196683917 : || single_succ (bb) == EXIT_BLOCK_PTR_FOR_FN (cfun)
493 : /* Nor should this be an infinite loop. */
494 164780128 : || single_succ (bb) == bb
495 : /* BB may not have an abnormal outgoing edge. */
496 574215533 : || (single_succ_edge (bb)->flags & EDGE_ABNORMAL))
497 : return false;
498 :
499 164641124 : gcc_checking_assert (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun));
500 :
501 164641124 : locus = single_succ_edge (bb)->goto_locus;
502 :
503 : /* There should not be an edge coming from entry, or an EH edge. */
504 164641124 : {
505 164641124 : edge_iterator ei;
506 164641124 : edge e;
507 :
508 342385254 : FOR_EACH_EDGE (e, ei, bb->preds)
509 200237390 : if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun) || (e->flags & EDGE_EH))
510 22493260 : return false;
511 : /* If goto_locus of any of the edges differs, prevent removing
512 : the forwarder block when not optimizing. */
513 179177000 : else if (!optimize
514 5314935 : && (LOCATION_LOCUS (e->goto_locus) != UNKNOWN_LOCATION
515 4825658 : || LOCATION_LOCUS (locus) != UNKNOWN_LOCATION)
516 180610009 : && e->goto_locus != locus)
517 : return false;
518 : }
519 :
520 : /* If this bb has a single predecessor and that predecssor
521 : has a single successor, this bb will be merged with the
522 : predecessor so ignore it for removing of the forwarder block. */
523 142147864 : if (single_pred_p (bb)
524 142147864 : && single_succ_p (single_pred_edge (bb)->src))
525 : return false;
526 :
527 133898579 : bool has_phi = !gimple_seq_empty_p (phi_nodes (bb));
528 133898579 : basic_block dest = single_succ_edge (bb)->dest;
529 :
530 : /* If the destination block consists of a nonlocal label or is a
531 : EH landing pad, do not merge it. */
532 133898579 : if (glabel *label_stmt = safe_dyn_cast <glabel *> (first_stmt (dest)))
533 8631591 : if (DECL_NONLOCAL (gimple_label_label (label_stmt))
534 8631591 : || EH_LANDING_PAD_NR (gimple_label_label (label_stmt)))
535 : return false;
536 :
537 : /* If there is an abnormal edge to basic block BB, but not into
538 : dest, problems might occur during removal of the phi node at out
539 : of ssa due to overlapping live ranges of registers.
540 :
541 : If there is an abnormal edge in DEST, the problems would occur
542 : anyway since cleanup_dead_labels would then merge the labels for
543 : two different eh regions, and rest of exception handling code
544 : does not like it.
545 :
546 : So if there is an abnormal edge to BB, proceed only if there is
547 : no abnormal edge to DEST and there are no phi nodes in DEST.
548 : If the BB has phi, we don't want to deal with abnormal edges either. */
549 130534728 : if (bb_has_abnormal_pred (bb)
550 130534728 : && (bb_has_abnormal_pred (dest)
551 60991 : || !gimple_seq_empty_p (phi_nodes (dest))
552 53651 : || has_phi))
553 : return false;
554 :
555 : /* When we have a phi, we have to feed into another
556 : basic block with PHI nodes. */
557 130523452 : if (has_phi && gimple_seq_empty_p (phi_nodes (dest)))
558 : return false;
559 :
560 : /* When we have phi, make sure the phi does not have any uses of
561 : names used in abnormal phis. */
562 127225422 : if (has_phi && bb_phis_references_abnormal_uses (bb))
563 : return false;
564 :
565 : /* Now walk through the statements backward. We can ignore labels,
566 : anything else means this is not a forwarder block. */
567 526613430 : for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
568 : {
569 227583949 : gimple *stmt = gsi_stmt (gsi);
570 :
571 227583949 : switch (gimple_code (stmt))
572 : {
573 1228067 : case GIMPLE_LABEL:
574 1228067 : if (DECL_NONLOCAL (gimple_label_label (as_a <glabel *> (stmt)))
575 1228067 : || EH_LANDING_PAD_NR (gimple_label_label (as_a <glabel *> (stmt))))
576 : return false;
577 1227760 : if (!optimize
578 29656 : && (gimple_has_location (stmt)
579 2185 : || LOCATION_LOCUS (locus) != UNKNOWN_LOCATION)
580 1255231 : && gimple_location (stmt) != locus)
581 : return false;
582 : break;
583 :
584 : /* ??? For now, hope there's a corresponding debug
585 : assignment at the destination. */
586 : case GIMPLE_DEBUG:
587 : break;
588 :
589 : default:
590 : return false;
591 : }
592 : }
593 : /* If BB has PHIs and does not dominate DEST,
594 : then the PHI nodes at DEST must be the only
595 : users of the results of the PHI nodes at BB.
596 : So only check when BB dominates dest. */
597 35722766 : if (has_phi
598 35722766 : && dominated_by_p (CDI_DOMINATORS, dest, bb))
599 : {
600 2194601 : gphi_iterator gsi;
601 2194601 : unsigned int dest_idx = single_succ_edge (bb)->dest_idx;
602 :
603 : /* BB dominates DEST. There may be many users of the PHI
604 : nodes in BB. However, there is still a trivial case we
605 : can handle. If the result of every PHI in BB is used
606 : only by a PHI in DEST, then we can trivially merge the
607 : PHI nodes from BB into DEST. */
608 4531069 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
609 2336468 : gsi_next (&gsi))
610 : {
611 3103918 : gphi *phi = gsi.phi ();
612 3103918 : tree result = gimple_phi_result (phi);
613 3103918 : use_operand_p imm_use;
614 3103918 : gimple *use_stmt;
615 :
616 : /* If the PHI's result is never used, then we can just
617 : ignore it an. */
618 3103918 : if (has_zero_uses (result))
619 71571 : continue;
620 :
621 : /* Get the single use of the result of this PHI node. */
622 3032347 : if (!single_imm_use (result, &imm_use, &use_stmt)
623 2583520 : || gimple_code (use_stmt) != GIMPLE_PHI
624 2334449 : || gimple_bb (use_stmt) != dest
625 5298332 : || gimple_phi_arg_def (use_stmt, dest_idx) != result)
626 767450 : return false;
627 : }
628 : }
629 :
630 34955316 : if (current_loops)
631 : {
632 : /* Protect loop headers. */
633 34062261 : if (bb_loop_header_p (bb))
634 : return false;
635 :
636 : /* Protect loop preheaders and latches if requested. */
637 33908525 : if (dest->loop_father->header == dest)
638 : {
639 12165097 : if (bb->loop_father == dest->loop_father)
640 : {
641 7318854 : if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES))
642 : return false;
643 : /* If bb doesn't have a single predecessor we'd make this
644 : loop have multiple latches. Don't do that if that
645 : would in turn require disambiguating them over again. */
646 400178087 : if (!single_pred_p (bb))
647 : return false;
648 : }
649 : /* cleanup_tree_cfg_noloop just created the loop preheader, don't
650 : remove it if it has phis. */
651 4846243 : else if (bb->loop_father == loop_outer (dest->loop_father)
652 4834077 : && !has_phi
653 8604261 : && !loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS))
654 : ;
655 : else
656 : /* Always preserve other edges into loop headers that are
657 : not simple latches or preheaders. */
658 : return false;
659 : }
660 : }
661 :
662 31518252 : edge succ = single_succ_edge (bb), e, s;
663 31518252 : gimple *stmt;
664 31518252 : gimple_stmt_iterator gsi_to;
665 :
666 : /* If there are phi nodes in DEST, and some of the blocks that are
667 : predecessors of BB are also predecessors of DEST, check that the
668 : phi node arguments match.
669 : Otherwise we have to split the edge and that becomes
670 : a "forwarder" again. */
671 31518252 : if ((!can_split || !has_phi)
672 31518252 : && !gimple_seq_empty_p (phi_nodes (dest)))
673 : {
674 25826449 : edge_iterator ei;
675 50035668 : FOR_EACH_EDGE (e, ei, bb->preds)
676 : {
677 28347815 : s = find_edge (e->src, dest);
678 28347815 : if (!s)
679 24158581 : continue;
680 :
681 4189234 : if (!phi_alternatives_equal (dest, succ, s))
682 4138596 : return false;
683 : }
684 : }
685 :
686 27379656 : basic_block pred = NULL;
687 27379656 : if (single_pred_p (bb))
688 25809658 : pred = single_pred (bb);
689 27379656 : bool dest_single_pred_p = single_pred_p (dest);
690 :
691 : /* Redirect the edges. */
692 57335032 : for (edge_iterator ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
693 : {
694 29955376 : if (cfgcleanup_altered_bbs)
695 29735133 : bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
696 29955376 : s = find_edge (e->src, dest);
697 :
698 : /* See if we can split the edge if we already have an edge from src to dest. */
699 29955376 : if (can_split && has_phi)
700 : /* PHI arguments are different. Create a forwarder block by
701 : splitting E so that we can merge PHI arguments on E to
702 : DEST. */
703 34264 : if (s && !phi_alternatives_equal (dest, s, succ))
704 10736 : e = single_succ_edge (split_edge (e));
705 :
706 29955376 : if (e->flags & EDGE_ABNORMAL)
707 : {
708 : /* If there is an abnormal edge, redirect it anyway, and
709 : move the labels to the new block to make it legal. */
710 183 : s = redirect_edge_succ_nodup (e, dest);
711 : }
712 : else
713 29955193 : s = redirect_edge_and_branch (e, dest);
714 :
715 29955376 : if (s == e)
716 : {
717 : /* If we merge the forwarder with phis into a loop header
718 : verify if we are creating another loop latch edge.
719 : If so, reset number of iteration information of the loop. */
720 29837555 : if (has_phi
721 2745420 : && dest->loop_father
722 2745420 : && dest->loop_father->header == dest
723 29861090 : && dominated_by_p (CDI_DOMINATORS, e->src, dest))
724 : {
725 23535 : dest->loop_father->any_upper_bound = false;
726 23535 : dest->loop_father->any_likely_upper_bound = false;
727 23535 : free_numbers_of_iterations_estimates (dest->loop_father);
728 : }
729 : /* Copy arguments for the phi nodes, since the edge was not
730 : here before. */
731 29837555 : copy_phi_arg_into_existing_phi (succ, s, has_phi);
732 : }
733 : else
734 117821 : redirect_edge_var_map_clear (s);
735 : }
736 :
737 : /* Move nonlocal labels and computed goto targets as well as user
738 : defined labels and labels with an EH landing pad number to the
739 : new block, so that the redirection of the abnormal edges works,
740 : jump targets end up in a sane place and debug information for
741 : labels is retained. */
742 27379656 : gsi_to = gsi_start_bb (dest);
743 55024253 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
744 : {
745 2859144 : stmt = gsi_stmt (gsi);
746 2859144 : if (is_gimple_debug (stmt))
747 : break;
748 :
749 : /* Forwarder blocks can only contain labels and debug stmts, and
750 : labels must come first, so if we get to this point, we know
751 : we're looking at a label. */
752 264941 : tree decl = gimple_label_label (as_a <glabel *> (stmt));
753 264941 : if (EH_LANDING_PAD_NR (decl) != 0
754 264941 : || DECL_NONLOCAL (decl)
755 264941 : || FORCED_LABEL (decl)
756 523199 : || !DECL_ARTIFICIAL (decl))
757 31074 : gsi_move_before (&gsi, &gsi_to);
758 : else
759 233867 : gsi_next (&gsi);
760 : }
761 :
762 : /* Move debug statements. Reset them if the destination does not
763 : have a single predecessor. */
764 54759312 : move_debug_stmts_from_forwarder (bb, dest, dest_single_pred_p,
765 80461401 : pred, pred && single_succ_p (pred));
766 :
767 27379656 : if (cfgcleanup_altered_bbs)
768 27181786 : bitmap_set_bit (cfgcleanup_altered_bbs, dest->index);
769 :
770 : /* Update the dominators. */
771 27379656 : basic_block dom, dombb, domdest;
772 :
773 27379656 : dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
774 27379656 : domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
775 27379656 : if (domdest == bb)
776 : {
777 : /* Shortcut to avoid calling (relatively expensive)
778 : nearest_common_dominator unless necessary. */
779 : dom = dombb;
780 : }
781 : else
782 20515139 : dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
783 :
784 27379656 : set_immediate_dominator (CDI_DOMINATORS, dest, dom);
785 :
786 : /* Adjust latch information of BB's parent loop as otherwise
787 : the cfg hook has a hard time not to kill the loop. */
788 27379656 : if (current_loops && bb->loop_father->latch == bb)
789 5534704 : bb->loop_father->latch = pred;
790 :
791 : /* And kill the forwarder block. */
792 27379656 : delete_basic_block (bb);
793 :
794 27379656 : return true;
795 : }
796 :
797 : /* STMT is a call that has been discovered noreturn. Split the
798 : block to prepare fixing up the CFG and remove LHS.
799 : Return true if cleanup-cfg needs to run. */
800 :
801 : bool
802 6312831 : fixup_noreturn_call (gimple *stmt)
803 : {
804 6312831 : basic_block bb = gimple_bb (stmt);
805 6312831 : bool changed = false;
806 :
807 6312831 : if (gimple_call_builtin_p (stmt, BUILT_IN_RETURN))
808 : return false;
809 :
810 : /* First split basic block if stmt is not last. */
811 12621902 : if (stmt != gsi_stmt (gsi_last_bb (bb)))
812 : {
813 43219 : if (stmt == gsi_stmt (gsi_last_nondebug_bb (bb)))
814 : {
815 : /* Don't split if there are only debug stmts
816 : after stmt, that can result in -fcompare-debug
817 : failures. Remove the debug stmts instead,
818 : they should be all unreachable anyway. */
819 6268 : gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
820 54378 : for (gsi_next (&gsi); !gsi_end_p (gsi); )
821 48110 : gsi_remove (&gsi, true);
822 : }
823 : else
824 : {
825 36951 : split_block (bb, stmt);
826 36951 : changed = true;
827 : }
828 : }
829 :
830 : /* If there is an LHS, remove it, but only if its type has fixed size.
831 : The LHS will need to be recreated during RTL expansion and creating
832 : temporaries of variable-sized types is not supported. Also don't
833 : do this with TREE_ADDRESSABLE types, as assign_temp will abort.
834 : Drop LHS regardless of TREE_ADDRESSABLE, if the function call
835 : has been changed into a call that does not return a value, like
836 : __builtin_unreachable or __cxa_pure_virtual. */
837 6310951 : tree lhs = gimple_call_lhs (stmt);
838 6310951 : if (lhs
839 6310951 : && (should_remove_lhs_p (lhs)
840 406 : || VOID_TYPE_P (TREE_TYPE (gimple_call_fntype (stmt)))))
841 : {
842 4136 : gimple_call_set_lhs (stmt, NULL_TREE);
843 :
844 : /* We need to fix up the SSA name to avoid checking errors. */
845 4136 : if (TREE_CODE (lhs) == SSA_NAME)
846 : {
847 3935 : tree new_var = create_tmp_reg (TREE_TYPE (lhs));
848 3935 : SET_SSA_NAME_VAR_OR_IDENTIFIER (lhs, new_var);
849 3935 : SSA_NAME_DEF_STMT (lhs) = gimple_build_nop ();
850 3935 : set_ssa_default_def (cfun, new_var, lhs);
851 : }
852 :
853 4136 : update_stmt (stmt);
854 : }
855 :
856 : /* Mark the call as altering control flow. */
857 6310951 : if (!gimple_call_ctrl_altering_p (stmt))
858 : {
859 85044 : gimple_call_set_ctrl_altering (stmt, true);
860 85044 : changed = true;
861 : }
862 :
863 : return changed;
864 : }
865 :
866 : /* Return true if we want to merge BB1 and BB2 into a single block. */
867 :
868 : static bool
869 408730223 : want_merge_blocks_p (basic_block bb1, basic_block bb2)
870 : {
871 408730223 : if (!can_merge_blocks_p (bb1, bb2))
872 : return false;
873 28304454 : gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb1);
874 28304454 : if (gsi_end_p (gsi) || !stmt_can_terminate_bb_p (gsi_stmt (gsi)))
875 25080330 : return true;
876 3224124 : return bb1->count.ok_for_merging (bb2->count);
877 : }
878 :
879 :
880 : /* Tries to cleanup cfg in basic block BB by merging blocks. Returns
881 : true if anything changes. */
882 :
883 : static bool
884 388773103 : cleanup_tree_cfg_bb (basic_block bb)
885 : {
886 388773103 : if (maybe_remove_forwarder_block (bb))
887 : return true;
888 :
889 : /* If there is a merge opportunity with the predecessor
890 : do nothing now but wait until we process the predecessor.
891 : This happens when we visit BBs in a non-optimal order and
892 : avoids quadratic behavior with adjusting stmts BB pointer. */
893 361591317 : if (single_pred_p (bb)
894 624249330 : && want_merge_blocks_p (single_pred (bb), bb))
895 : /* But make sure we _do_ visit it. When we remove unreachable paths
896 : ending in a backedge we fail to mark the destinations predecessors
897 : as changed. */
898 11562800 : bitmap_set_bit (cfgcleanup_altered_bbs, single_pred (bb)->index);
899 :
900 : /* Merging the blocks may create new opportunities for folding
901 : conditional branches (due to the elimination of single-valued PHI
902 : nodes). */
903 350028517 : else if (single_succ_p (bb)
904 485203358 : && want_merge_blocks_p (bb, single_succ (bb)))
905 : {
906 16741590 : merge_blocks (bb, single_succ (bb));
907 16741590 : return true;
908 : }
909 :
910 : return false;
911 : }
912 :
913 : /* Return true if E is an EDGE_ABNORMAL edge for returns_twice calls,
914 : i.e. one going from .ABNORMAL_DISPATCHER to basic block which doesn't
915 : start with a forced or nonlocal label. Calls which return twice can return
916 : the second time only if they are called normally the first time, so basic
917 : blocks which can be only entered through these abnormal edges but not
918 : normally are effectively unreachable as well. Additionally ignore
919 : __builtin_setjmp_receiver starting blocks, which have one FORCED_LABEL
920 : and which are always only reachable through EDGE_ABNORMAL edge. They are
921 : handled in cleanup_control_flow_pre. */
922 :
923 : static bool
924 343666179 : maybe_dead_abnormal_edge_p (edge e)
925 : {
926 343666179 : if ((e->flags & (EDGE_ABNORMAL | EDGE_EH)) != EDGE_ABNORMAL)
927 : return false;
928 :
929 148721 : gimple_stmt_iterator gsi = gsi_start_nondebug_after_labels_bb (e->src);
930 148721 : gimple *g = gsi_stmt (gsi);
931 148721 : if (!g || !gimple_call_internal_p (g, IFN_ABNORMAL_DISPATCHER))
932 : return false;
933 :
934 19841 : tree target = NULL_TREE;
935 51765 : for (gsi = gsi_start_bb (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
936 31917 : if (glabel *label_stmt = dyn_cast <glabel *> (gsi_stmt (gsi)))
937 : {
938 18010 : tree this_target = gimple_label_label (label_stmt);
939 18010 : if (DECL_NONLOCAL (this_target))
940 : return false;
941 12083 : if (FORCED_LABEL (this_target))
942 : {
943 12083 : if (target)
944 : return false;
945 : target = this_target;
946 : }
947 : }
948 : else
949 : break;
950 :
951 13914 : if (target)
952 : {
953 : /* If there was a single FORCED_LABEL, check for
954 : __builtin_setjmp_receiver with address of that label. */
955 12083 : if (!gsi_end_p (gsi) && is_gimple_debug (gsi_stmt (gsi)))
956 0 : gsi_next_nondebug (&gsi);
957 12083 : if (gsi_end_p (gsi))
958 : return false;
959 12083 : if (!gimple_call_builtin_p (gsi_stmt (gsi), BUILT_IN_SETJMP_RECEIVER))
960 : return false;
961 :
962 12083 : tree arg = gimple_call_arg (gsi_stmt (gsi), 0);
963 12083 : if (TREE_CODE (arg) != ADDR_EXPR || TREE_OPERAND (arg, 0) != target)
964 : return false;
965 : }
966 : return true;
967 : }
968 :
969 : /* If BB is a basic block ending with __builtin_setjmp_setup, return edge
970 : from .ABNORMAL_DISPATCHER basic block to corresponding
971 : __builtin_setjmp_receiver basic block, otherwise return NULL. */
972 : static edge
973 343664324 : builtin_setjmp_setup_bb (basic_block bb)
974 : {
975 343664324 : if (EDGE_COUNT (bb->succs) != 2
976 332826455 : || ((EDGE_SUCC (bb, 0)->flags
977 152429343 : & (EDGE_ABNORMAL | EDGE_EH)) != EDGE_ABNORMAL
978 152333782 : && (EDGE_SUCC (bb, 1)->flags
979 152333782 : & (EDGE_ABNORMAL | EDGE_EH)) != EDGE_ABNORMAL))
980 : return NULL;
981 :
982 168549 : gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
983 168549 : if (gsi_end_p (gsi)
984 168549 : || !gimple_call_builtin_p (gsi_stmt (gsi), BUILT_IN_SETJMP_SETUP))
985 156490 : return NULL;
986 :
987 12059 : tree arg = gimple_call_arg (gsi_stmt (gsi), 1);
988 12059 : if (TREE_CODE (arg) != ADDR_EXPR
989 12059 : || TREE_CODE (TREE_OPERAND (arg, 0)) != LABEL_DECL)
990 : return NULL;
991 :
992 12059 : basic_block recv_bb = label_to_block (cfun, TREE_OPERAND (arg, 0));
993 343664324 : if (EDGE_COUNT (recv_bb->preds) != 1
994 12059 : || (EDGE_PRED (recv_bb, 0)->flags
995 12059 : & (EDGE_ABNORMAL | EDGE_EH)) != EDGE_ABNORMAL
996 24118 : || (EDGE_SUCC (bb, 0)->dest != EDGE_PRED (recv_bb, 0)->src
997 12059 : && EDGE_SUCC (bb, 1)->dest != EDGE_PRED (recv_bb, 0)->src))
998 : return NULL;
999 :
1000 : /* EDGE_PRED (recv_bb, 0)->src should be the .ABNORMAL_DISPATCHER bb. */
1001 : return EDGE_PRED (recv_bb, 0);
1002 : }
1003 :
1004 : /* Do cleanup_control_flow_bb in PRE order. */
1005 :
1006 : static bool
1007 25116070 : cleanup_control_flow_pre ()
1008 : {
1009 25116070 : bool retval = false;
1010 :
1011 : /* We want remove_edge_and_dominated_blocks to only remove edges,
1012 : not dominated blocks which it does when dom info isn't available.
1013 : Pretend so. */
1014 25116070 : dom_state saved_state = dom_info_state (CDI_DOMINATORS);
1015 25116070 : set_dom_info_availability (CDI_DOMINATORS, DOM_NONE);
1016 :
1017 25116070 : auto_vec<edge_iterator, 20> stack (n_basic_blocks_for_fn (cfun) + 2);
1018 25116070 : auto_sbitmap visited (last_basic_block_for_fn (cfun));
1019 25116070 : bitmap_clear (visited);
1020 :
1021 25116070 : vec<edge, va_gc> *setjmp_vec = NULL;
1022 25116070 : auto_vec<basic_block, 4> abnormal_dispatchers;
1023 :
1024 25116070 : stack.quick_push (ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs));
1025 :
1026 870596405 : while (! stack.is_empty ())
1027 : {
1028 : /* Look at the edge on the top of the stack. */
1029 845480335 : edge_iterator ei = stack.last ();
1030 845480335 : basic_block dest = ei_edge (ei)->dest;
1031 :
1032 845480335 : if (dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
1033 820754372 : && !bitmap_bit_p (visited, dest->index)
1034 1189158573 : && (ei_container (ei) == setjmp_vec
1035 343666179 : || !maybe_dead_abnormal_edge_p (ei_edge (ei))))
1036 : {
1037 343664324 : bitmap_set_bit (visited, dest->index);
1038 : /* We only possibly remove edges from DEST here, leaving
1039 : possibly unreachable code in the IL. */
1040 343664324 : retval |= cleanup_control_flow_bb (dest);
1041 :
1042 : /* Check for __builtin_setjmp_setup. Edges from .ABNORMAL_DISPATCH
1043 : to __builtin_setjmp_receiver will be normally ignored by
1044 : maybe_dead_abnormal_edge_p. If DEST is a visited
1045 : __builtin_setjmp_setup, queue edge from .ABNORMAL_DISPATCH
1046 : to __builtin_setjmp_receiver, so that it will be visited too. */
1047 343664324 : if (edge e = builtin_setjmp_setup_bb (dest))
1048 : {
1049 12059 : vec_safe_push (setjmp_vec, e);
1050 12059 : if (vec_safe_length (setjmp_vec) == 1)
1051 6408 : stack.quick_push (ei_start (setjmp_vec));
1052 : }
1053 :
1054 343664324 : if ((ei_edge (ei)->flags
1055 343664324 : & (EDGE_ABNORMAL | EDGE_EH)) == EDGE_ABNORMAL)
1056 : {
1057 146866 : gimple_stmt_iterator gsi
1058 146866 : = gsi_start_nondebug_after_labels_bb (dest);
1059 146866 : gimple *g = gsi_stmt (gsi);
1060 146866 : if (g && gimple_call_internal_p (g, IFN_ABNORMAL_DISPATCHER))
1061 26119 : abnormal_dispatchers.safe_push (dest);
1062 : }
1063 :
1064 1189144659 : if (EDGE_COUNT (dest->succs) > 0)
1065 321099179 : stack.quick_push (ei_start (dest->succs));
1066 : }
1067 : else
1068 : {
1069 501816011 : if (!ei_one_before_end_p (ei))
1070 155594354 : ei_next (&stack.last ());
1071 : else
1072 : {
1073 346221657 : if (ei_container (ei) == setjmp_vec)
1074 6408 : vec_safe_truncate (setjmp_vec, 0);
1075 346221657 : stack.pop ();
1076 : }
1077 : }
1078 : }
1079 :
1080 25116070 : vec_free (setjmp_vec);
1081 :
1082 : /* If we've marked .ABNORMAL_DISPATCHER basic block(s) as visited
1083 : above, but haven't marked any of their successors as visited,
1084 : unmark them now, so that they can be removed as useless. */
1085 75374329 : for (basic_block dispatcher_bb : abnormal_dispatchers)
1086 : {
1087 26119 : edge e;
1088 26119 : edge_iterator ei;
1089 26210 : FOR_EACH_EDGE (e, ei, dispatcher_bb->succs)
1090 26119 : if (bitmap_bit_p (visited, e->dest->index))
1091 : break;
1092 26119 : if (e == NULL)
1093 91 : bitmap_clear_bit (visited, dispatcher_bb->index);
1094 : }
1095 :
1096 25116070 : set_dom_info_availability (CDI_DOMINATORS, saved_state);
1097 :
1098 : /* We are deleting BBs in non-reverse dominator order, make sure
1099 : insert_debug_temps_for_defs is prepared for that. */
1100 25116070 : if (retval)
1101 866778 : free_dominance_info (CDI_DOMINATORS);
1102 :
1103 : /* Remove all now (and previously) unreachable blocks. */
1104 392182812 : for (int i = NUM_FIXED_BLOCKS; i < last_basic_block_for_fn (cfun); ++i)
1105 : {
1106 367066742 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
1107 367066742 : if (bb && !bitmap_bit_p (visited, bb->index))
1108 : {
1109 4595708 : if (!retval)
1110 730204 : free_dominance_info (CDI_DOMINATORS);
1111 4595708 : delete_basic_block (bb);
1112 4595708 : retval = true;
1113 : }
1114 : }
1115 :
1116 25116070 : return retval;
1117 25116070 : }
1118 :
1119 : /* Callback function for make_forwarder_block which returns
1120 : true when E is not a latch. */
1121 :
1122 : static bool
1123 148038 : mfb_keep_latches (edge e, void*)
1124 : {
1125 148038 : return !((dom_info_available_p (CDI_DOMINATORS)
1126 21569 : && dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
1127 141351 : || (e->flags & EDGE_DFS_BACK));
1128 : }
1129 :
1130 : /* Remove unreachable blocks and other miscellaneous clean up work.
1131 : Return true if the flowgraph was modified, false otherwise. */
1132 :
1133 : static bool
1134 25116070 : cleanup_tree_cfg_noloop (unsigned ssa_update_flags)
1135 : {
1136 25116070 : timevar_push (TV_TREE_CLEANUP_CFG);
1137 :
1138 : /* Ensure that we have single entries into loop headers. Otherwise
1139 : if one of the entries is becoming a latch due to CFG cleanup
1140 : (from formerly being part of an irreducible region) then we mess
1141 : up loop fixup and associate the old loop with a different region
1142 : which makes niter upper bounds invalid. See for example PR80549.
1143 : This needs to be done before we remove trivially dead edges as
1144 : we need to capture the dominance state before the pending transform. */
1145 25116070 : if (current_loops)
1146 : {
1147 : /* This needs backedges or dominators. */
1148 22235860 : if (!dom_info_available_p (CDI_DOMINATORS))
1149 6742966 : mark_dfs_back_edges ();
1150 :
1151 92506925 : for (loop_p loop : *get_loops (cfun))
1152 48035205 : if (loop && loop->header)
1153 : {
1154 40921820 : basic_block bb = loop->header;
1155 40921820 : edge_iterator ei;
1156 40921820 : edge e;
1157 40921820 : bool found_latch = false;
1158 40921820 : bool any_abnormal = false;
1159 40921820 : unsigned n = 0;
1160 : /* We are only interested in preserving existing loops, but
1161 : we need to check whether they are still real and of course
1162 : if we need to add a preheader at all. */
1163 78448345 : FOR_EACH_EDGE (e, ei, bb->preds)
1164 : {
1165 37526525 : if (e->flags & EDGE_ABNORMAL)
1166 : {
1167 : any_abnormal = true;
1168 : break;
1169 : }
1170 37526525 : if ((dom_info_available_p (CDI_DOMINATORS)
1171 27345719 : && dominated_by_p (CDI_DOMINATORS, e->src, bb))
1172 51184194 : || (e->flags & EDGE_DFS_BACK))
1173 : {
1174 18786800 : found_latch = true;
1175 18786800 : continue;
1176 : }
1177 18739725 : n++;
1178 : }
1179 : /* If we have more than one entry to the loop header
1180 : create a forwarder. */
1181 40921820 : if (found_latch && ! any_abnormal && n > 1)
1182 : {
1183 45748 : edge fallthru = make_forwarder_block (bb, mfb_keep_latches, NULL);
1184 45748 : loop->header = fallthru->dest;
1185 45748 : if (! loops_state_satisfies_p (LOOPS_NEED_FIXUP))
1186 : {
1187 : /* The loop updating from the CFG hook is incomplete
1188 : when we have multiple latches, fixup manually. */
1189 25861 : remove_bb_from_loops (fallthru->src);
1190 25861 : loop_p cloop = loop;
1191 81199 : FOR_EACH_EDGE (e, ei, fallthru->src->preds)
1192 55338 : cloop = find_common_loop (cloop, e->src->loop_father);
1193 25861 : add_bb_to_loop (fallthru->src, cloop);
1194 : }
1195 : }
1196 : }
1197 : }
1198 :
1199 : /* Prepare the worklists of altered blocks. */
1200 25116070 : cfgcleanup_altered_bbs = BITMAP_ALLOC (NULL);
1201 :
1202 : /* Start by iterating over all basic blocks in PRE order looking for
1203 : edge removal opportunities. Do this first because incoming SSA form
1204 : may be invalid and we want to avoid performing SSA related tasks such
1205 : as propagating out a PHI node during BB merging in that state. This
1206 : also gets rid of unreachable blocks. */
1207 25116070 : bool changed = cleanup_control_flow_pre ();
1208 :
1209 : /* After doing the above SSA form should be valid (or an update SSA
1210 : should be required). */
1211 25116070 : if (ssa_update_flags)
1212 : {
1213 16226167 : timevar_pop (TV_TREE_CLEANUP_CFG);
1214 16226167 : update_ssa (ssa_update_flags);
1215 16226167 : timevar_push (TV_TREE_CLEANUP_CFG);
1216 : }
1217 :
1218 : /* Compute dominator info which we need for the iterative process below.
1219 : Avoid computing the fast query DFS numbers since any block merging
1220 : done will invalidate them anyway. */
1221 25116070 : if (!dom_info_available_p (CDI_DOMINATORS))
1222 8526684 : calculate_dominance_info (CDI_DOMINATORS, false);
1223 : else
1224 16589386 : checking_verify_dominators (CDI_DOMINATORS);
1225 :
1226 : /* During forwarder block cleanup, we may redirect edges out of
1227 : SWITCH_EXPRs, which can get expensive. So we want to enable
1228 : recording of edge to CASE_LABEL_EXPR. */
1229 25116070 : start_recording_case_labels ();
1230 :
1231 : /* Continue by iterating over all basic blocks looking for BB merging
1232 : opportunities. We cannot use FOR_EACH_BB_FN for the BB iteration
1233 : since the basic blocks may get removed. */
1234 25116070 : unsigned n = last_basic_block_for_fn (cfun);
1235 392182812 : for (unsigned i = NUM_FIXED_BLOCKS; i < n; i++)
1236 : {
1237 367066742 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
1238 367066742 : if (bb)
1239 336344958 : changed |= cleanup_tree_cfg_bb (bb);
1240 : }
1241 :
1242 : /* Now process the altered blocks, as long as any are available. */
1243 85624846 : while (!bitmap_empty_p (cfgcleanup_altered_bbs))
1244 : {
1245 60508776 : unsigned i = bitmap_clear_first_set_bit (cfgcleanup_altered_bbs);
1246 60508776 : if (i < NUM_FIXED_BLOCKS)
1247 0 : continue;
1248 :
1249 60508776 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
1250 60508776 : if (!bb)
1251 8080631 : continue;
1252 :
1253 : /* BB merging done by cleanup_tree_cfg_bb can end up propagating
1254 : out single-argument PHIs which in turn can expose
1255 : cleanup_control_flow_bb opportunities so we have to repeat
1256 : that here. */
1257 52428145 : changed |= cleanup_control_flow_bb (bb);
1258 52428145 : changed |= cleanup_tree_cfg_bb (bb);
1259 : }
1260 :
1261 25116070 : end_recording_case_labels ();
1262 25116070 : BITMAP_FREE (cfgcleanup_altered_bbs);
1263 :
1264 25116070 : gcc_assert (dom_info_available_p (CDI_DOMINATORS));
1265 :
1266 : /* Do not renumber blocks if the SCEV cache is active, it is indexed by
1267 : basic-block numbers. */
1268 25116070 : if (! scev_initialized_p ())
1269 24809227 : compact_blocks ();
1270 :
1271 25116070 : checking_verify_flow_info ();
1272 :
1273 25116070 : timevar_pop (TV_TREE_CLEANUP_CFG);
1274 :
1275 25116070 : if (changed && current_loops)
1276 : {
1277 : /* Removing edges and/or blocks may make recorded bounds refer
1278 : to stale GIMPLE stmts now, so clear them. */
1279 5980135 : free_numbers_of_iterations_estimates (cfun);
1280 5980135 : loops_state_set (LOOPS_NEED_FIXUP);
1281 : }
1282 :
1283 25116070 : return changed;
1284 : }
1285 :
1286 : /* Repairs loop structures. */
1287 :
1288 : static void
1289 7641351 : repair_loop_structures (void)
1290 : {
1291 7641351 : bitmap changed_bbs;
1292 7641351 : unsigned n_new_or_deleted_loops;
1293 :
1294 7641351 : calculate_dominance_info (CDI_DOMINATORS);
1295 :
1296 7641351 : timevar_push (TV_REPAIR_LOOPS);
1297 7641351 : changed_bbs = BITMAP_ALLOC (NULL);
1298 7641351 : n_new_or_deleted_loops = fix_loop_structure (changed_bbs);
1299 :
1300 : /* This usually does nothing. But sometimes parts of cfg that originally
1301 : were inside a loop get out of it due to edge removal (since they
1302 : become unreachable by back edges from latch). Also a former
1303 : irreducible loop can become reducible - in this case force a full
1304 : rewrite into loop-closed SSA form. */
1305 7641351 : if (loops_state_satisfies_p (LOOP_CLOSED_SSA)
1306 7641351 : && (!bitmap_empty_p (changed_bbs) || n_new_or_deleted_loops))
1307 25524 : rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1308 :
1309 7641351 : BITMAP_FREE (changed_bbs);
1310 :
1311 7641351 : checking_verify_loop_structure ();
1312 7641351 : scev_reset ();
1313 :
1314 7641351 : timevar_pop (TV_REPAIR_LOOPS);
1315 7641351 : }
1316 :
1317 : /* Cleanup cfg and repair loop structures. */
1318 :
1319 : bool
1320 25116070 : cleanup_tree_cfg (unsigned ssa_update_flags)
1321 : {
1322 25116070 : bool changed = cleanup_tree_cfg_noloop (ssa_update_flags);
1323 :
1324 25116070 : if (current_loops != NULL
1325 25116070 : && loops_state_satisfies_p (LOOPS_NEED_FIXUP))
1326 7641351 : repair_loop_structures ();
1327 :
1328 25116070 : return changed;
1329 : }
1330 :
1331 : /* This pass merges PHI nodes if one feeds into another. For example,
1332 : suppose we have the following:
1333 :
1334 : goto <bb 9> (<L9>);
1335 :
1336 : <L8>:;
1337 : tem_17 = foo ();
1338 :
1339 : # tem_6 = PHI <tem_17(8), tem_23(7)>;
1340 : <L9>:;
1341 :
1342 : # tem_3 = PHI <tem_6(9), tem_2(5)>;
1343 : <L10>:;
1344 :
1345 : Then we merge the first PHI node into the second one like so:
1346 :
1347 : goto <bb 9> (<L10>);
1348 :
1349 : <L8>:;
1350 : tem_17 = foo ();
1351 :
1352 : # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
1353 : <L10>:;
1354 : */
1355 :
1356 : namespace {
1357 :
1358 : const pass_data pass_data_merge_phi =
1359 : {
1360 : GIMPLE_PASS, /* type */
1361 : "mergephi", /* name */
1362 : OPTGROUP_NONE, /* optinfo_flags */
1363 : TV_TREE_MERGE_PHI, /* tv_id */
1364 : ( PROP_cfg | PROP_ssa ), /* properties_required */
1365 : 0, /* properties_provided */
1366 : 0, /* properties_destroyed */
1367 : 0, /* todo_flags_start */
1368 : 0, /* todo_flags_finish */
1369 : };
1370 :
1371 : class pass_merge_phi : public gimple_opt_pass
1372 : {
1373 : public:
1374 896484 : pass_merge_phi (gcc::context *ctxt)
1375 1792968 : : gimple_opt_pass (pass_data_merge_phi, ctxt)
1376 : {}
1377 :
1378 : /* opt_pass methods: */
1379 597656 : opt_pass * clone () final override { return new pass_merge_phi (m_ctxt); }
1380 : unsigned int execute (function *) final override;
1381 :
1382 : }; // class pass_merge_phi
1383 :
1384 : unsigned int
1385 4482539 : pass_merge_phi::execute (function *fun)
1386 : {
1387 4482539 : int forwarder_removed = 0;
1388 4482539 : calculate_dominance_info (CDI_DOMINATORS);
1389 :
1390 : /* Find all PHI nodes that we may be able to merge. */
1391 4482539 : unsigned n = last_basic_block_for_fn (fun);
1392 37796981 : for (unsigned i = NUM_FIXED_BLOCKS; i < n; i++)
1393 : {
1394 33314442 : basic_block bb = BASIC_BLOCK_FOR_FN (fun, i);
1395 33314442 : if (!bb)
1396 71567 : continue;
1397 :
1398 : /* Look for a forwarder block with PHI nodes. */
1399 33242875 : if (maybe_remove_forwarder_block (bb, true))
1400 197870 : forwarder_removed++;
1401 : }
1402 :
1403 : /* Removing forwarder blocks can cause formerly irreducible loops
1404 : to become reducible if we merged two entry blocks. */
1405 4482539 : if (forwarder_removed != 0
1406 82273 : && current_loops)
1407 82273 : loops_state_set (LOOPS_NEED_FIXUP);
1408 :
1409 4482539 : statistics_counter_event (fun, "Forwarder blocks removed",
1410 : forwarder_removed);
1411 4482539 : return 0;
1412 : }
1413 :
1414 : } // anon namespace
1415 :
1416 : gimple_opt_pass *
1417 298828 : make_pass_merge_phi (gcc::context *ctxt)
1418 : {
1419 298828 : return new pass_merge_phi (ctxt);
1420 : }
1421 :
1422 : /* Pass: cleanup the CFG just before expanding trees to RTL.
1423 : This is just a round of label cleanups and case node grouping
1424 : because after the tree optimizers have run such cleanups may
1425 : be necessary. */
1426 :
1427 : static unsigned int
1428 1489144 : execute_cleanup_cfg_post_optimizing (void)
1429 : {
1430 1489144 : unsigned int todo = execute_fixup_cfg ();
1431 1489144 : if (cleanup_tree_cfg ())
1432 395110 : todo |= TODO_update_ssa;
1433 1489144 : maybe_remove_unreachable_handlers ();
1434 1489144 : cleanup_dead_labels ();
1435 1489144 : if (group_case_labels () && cleanup_tree_cfg ())
1436 0 : todo |= TODO_update_ssa;
1437 :
1438 : /* When optimizing undo the merging of forwarder blocks
1439 : that phis for better out of ssa expansion. */
1440 1489144 : if (optimize)
1441 1042104 : make_forwarders_with_degenerate_phis (cfun, true);
1442 :
1443 : /* Make sure todo does not have cleanup cfg as we don't want
1444 : remove the forwarder blocks we just created. cleanup cfg
1445 : has already happened. */
1446 1489144 : todo &= ~TODO_cleanup_cfg;
1447 :
1448 1489144 : basic_block bb = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
1449 1489144 : gimple_stmt_iterator gsi = gsi_start_nondebug_after_labels_bb (bb);
1450 : /* If the first (and only) bb and the only non debug
1451 : statement is __builtin_unreachable call, then replace it with a trap
1452 : so the function is at least one instruction in size. */
1453 1489144 : if (!gsi_end_p (gsi)
1454 1489144 : && gimple_call_builtin_p (gsi_stmt (gsi), BUILT_IN_UNREACHABLE))
1455 : {
1456 349 : if (targetm.have_trap ())
1457 : {
1458 698 : gimple_call_set_fndecl (gsi_stmt (gsi), builtin_decl_implicit (BUILT_IN_UNREACHABLE_TRAP));
1459 349 : update_stmt (gsi_stmt (gsi));
1460 : }
1461 : /* If the target does not have a trap, convert it into an infinite loop. */
1462 : else
1463 : {
1464 0 : gsi_remove (&gsi, true);
1465 0 : make_single_succ_edge (bb, bb, EDGE_FALLTHRU);
1466 0 : fix_loop_structure (NULL);
1467 : }
1468 : }
1469 :
1470 1489144 : if ((flag_compare_debug_opt || flag_compare_debug)
1471 3922 : && flag_dump_final_insns)
1472 : {
1473 3922 : FILE *final_output = fopen (flag_dump_final_insns, "a");
1474 :
1475 3922 : if (!final_output)
1476 : {
1477 0 : error ("could not open final insn dump file %qs: %m",
1478 : flag_dump_final_insns);
1479 0 : flag_dump_final_insns = NULL;
1480 : }
1481 : else
1482 : {
1483 3922 : int save_unnumbered = flag_dump_unnumbered;
1484 3922 : int save_noaddr = flag_dump_noaddr;
1485 :
1486 3922 : flag_dump_noaddr = flag_dump_unnumbered = 1;
1487 3922 : fprintf (final_output, "\n");
1488 3922 : dump_enumerated_decls (final_output,
1489 : dump_flags | TDF_SLIM | TDF_NOUID);
1490 3922 : flag_dump_noaddr = save_noaddr;
1491 3922 : flag_dump_unnumbered = save_unnumbered;
1492 3922 : if (fclose (final_output))
1493 : {
1494 0 : error ("could not close final insn dump file %qs: %m",
1495 : flag_dump_final_insns);
1496 0 : flag_dump_final_insns = NULL;
1497 : }
1498 : }
1499 : }
1500 1489144 : return todo;
1501 : }
1502 :
1503 : namespace {
1504 :
1505 : const pass_data pass_data_cleanup_cfg_post_optimizing =
1506 : {
1507 : GIMPLE_PASS, /* type */
1508 : "optimized", /* name */
1509 : OPTGROUP_NONE, /* optinfo_flags */
1510 : TV_TREE_CLEANUP_CFG, /* tv_id */
1511 : PROP_cfg, /* properties_required */
1512 : 0, /* properties_provided */
1513 : 0, /* properties_destroyed */
1514 : 0, /* todo_flags_start */
1515 : TODO_remove_unused_locals, /* todo_flags_finish */
1516 : };
1517 :
1518 : class pass_cleanup_cfg_post_optimizing : public gimple_opt_pass
1519 : {
1520 : public:
1521 298828 : pass_cleanup_cfg_post_optimizing (gcc::context *ctxt)
1522 597656 : : gimple_opt_pass (pass_data_cleanup_cfg_post_optimizing, ctxt)
1523 : {}
1524 :
1525 : /* opt_pass methods: */
1526 1489144 : unsigned int execute (function *) final override
1527 : {
1528 1489144 : return execute_cleanup_cfg_post_optimizing ();
1529 : }
1530 :
1531 : }; // class pass_cleanup_cfg_post_optimizing
1532 :
1533 : } // anon namespace
1534 :
1535 : gimple_opt_pass *
1536 298828 : make_pass_cleanup_cfg_post_optimizing (gcc::context *ctxt)
1537 : {
1538 298828 : return new pass_cleanup_cfg_post_optimizing (ctxt);
1539 : }
1540 :
1541 :
1542 : /* Delete all unreachable basic blocks and update callgraph.
1543 : Doing so is somewhat nontrivial because we need to update all clones and
1544 : remove inline function that become unreachable. */
1545 :
1546 : bool
1547 1564811 : delete_unreachable_blocks_update_callgraph (cgraph_node *dst_node,
1548 : bool update_clones)
1549 : {
1550 1564811 : bool changed = false;
1551 1564811 : basic_block b, next_bb;
1552 :
1553 1564811 : find_unreachable_blocks ();
1554 :
1555 : /* Delete all unreachable basic blocks. */
1556 :
1557 1564811 : for (b = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; b
1558 29894182 : != EXIT_BLOCK_PTR_FOR_FN (cfun); b = next_bb)
1559 : {
1560 28329371 : next_bb = b->next_bb;
1561 :
1562 28329371 : if (!(b->flags & BB_REACHABLE))
1563 : {
1564 38698 : gimple_stmt_iterator bsi;
1565 :
1566 152196 : for (bsi = gsi_start_bb (b); !gsi_end_p (bsi); gsi_next (&bsi))
1567 : {
1568 74800 : struct cgraph_edge *e;
1569 74800 : struct cgraph_node *node;
1570 :
1571 74800 : dst_node->remove_stmt_references (gsi_stmt (bsi));
1572 :
1573 74800 : if (gimple_code (gsi_stmt (bsi)) == GIMPLE_CALL
1574 74800 : &&(e = dst_node->get_edge (gsi_stmt (bsi))) != NULL)
1575 : {
1576 894 : if (!e->inline_failed)
1577 0 : e->callee->remove_symbol_and_inline_clones (dst_node);
1578 : else
1579 894 : cgraph_edge::remove (e);
1580 : }
1581 74800 : if (update_clones && dst_node->clones)
1582 0 : for (node = dst_node->clones; node != dst_node;)
1583 : {
1584 0 : node->remove_stmt_references (gsi_stmt (bsi));
1585 0 : if (gimple_code (gsi_stmt (bsi)) == GIMPLE_CALL
1586 0 : && (e = node->get_edge (gsi_stmt (bsi))) != NULL)
1587 : {
1588 0 : if (!e->inline_failed)
1589 0 : e->callee->remove_symbol_and_inline_clones (dst_node);
1590 : else
1591 0 : cgraph_edge::remove (e);
1592 : }
1593 :
1594 0 : if (node->clones)
1595 : node = node->clones;
1596 0 : else if (node->next_sibling_clone)
1597 : node = node->next_sibling_clone;
1598 : else
1599 : {
1600 0 : while (node != dst_node && !node->next_sibling_clone)
1601 0 : node = node->clone_of;
1602 0 : if (node != dst_node)
1603 0 : node = node->next_sibling_clone;
1604 : }
1605 : }
1606 : }
1607 38698 : delete_basic_block (b);
1608 38698 : changed = true;
1609 : }
1610 : }
1611 :
1612 1564811 : return changed;
1613 : }
1614 :
|
