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 22848237 : remove_fallthru_edge (vec<edge, va_gc> *ev)
66 : {
67 22848237 : edge_iterator ei;
68 22848237 : edge e;
69 :
70 25505675 : FOR_EACH_EDGE (e, ei, ev)
71 2688937 : if ((e->flags & EDGE_FALLTHRU) != 0)
72 : {
73 31499 : if (e->flags & EDGE_COMPLEX)
74 0 : e->flags &= ~EDGE_FALLTHRU;
75 : else
76 31499 : remove_edge_and_dominated_blocks (e);
77 31499 : 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 735808 : convert_single_case_switch (gswitch *swtch, gimple_stmt_iterator &gsi)
87 : {
88 735808 : if (gimple_switch_num_labels (swtch) != 2)
89 : return false;
90 :
91 11875 : tree index = gimple_switch_index (swtch);
92 11875 : tree label = gimple_switch_label (swtch, 1);
93 11875 : tree low = CASE_LOW (label);
94 11875 : tree high = CASE_HIGH (label);
95 :
96 11875 : basic_block default_bb = gimple_switch_default_bb (cfun, swtch);
97 11875 : basic_block case_bb = label_to_block (cfun, CASE_LABEL (label));
98 :
99 11875 : basic_block bb = gimple_bb (swtch);
100 11875 : gcond *cond;
101 :
102 : /* Replace switch statement with condition statement. */
103 11875 : if (high)
104 : {
105 1026 : tree lhs, rhs;
106 1026 : if (range_check_type (TREE_TYPE (index)) == NULL_TREE)
107 0 : return false;
108 1026 : generate_range_test (bb, index, low, high, &lhs, &rhs);
109 1026 : cond = gimple_build_cond (LE_EXPR, lhs, rhs, NULL_TREE, NULL_TREE);
110 : }
111 : else
112 10849 : cond = gimple_build_cond (EQ_EXPR, index,
113 10849 : fold_convert (TREE_TYPE (index), low),
114 : NULL_TREE, NULL_TREE);
115 :
116 11875 : gsi_replace (&gsi, cond, true);
117 :
118 : /* Update edges. */
119 11875 : edge case_edge = find_edge (bb, case_bb);
120 11875 : edge default_edge = find_edge (bb, default_bb);
121 :
122 11875 : case_edge->flags |= EDGE_TRUE_VALUE;
123 11875 : default_edge->flags |= EDGE_FALSE_VALUE;
124 11875 : 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 178897566 : canonicalize_bool_cond (gcond *stmt, basic_block bb)
131 : {
132 178897566 : tree rhs1 = gimple_cond_lhs (stmt);
133 178897566 : tree rhs2 = gimple_cond_rhs (stmt);
134 178897566 : enum tree_code code = gimple_cond_code (stmt);
135 178897566 : if (code != EQ_EXPR && code != NE_EXPR)
136 : return false;
137 134456344 : if (TREE_CODE (TREE_TYPE (rhs1)) != BOOLEAN_TYPE
138 134456344 : && (!INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
139 77386958 : || TYPE_PRECISION (TREE_TYPE (rhs1)) != 1))
140 : return false;
141 :
142 : /* Canonicalize _Bool == 0 and _Bool != 1 to _Bool != 0 by swapping edges. */
143 23638209 : if (code == EQ_EXPR && !integer_zerop (rhs2))
144 : return false;
145 23491914 : if (code == NE_EXPR && !integer_onep (rhs2))
146 : return false;
147 :
148 132293 : gimple_cond_set_code (stmt, NE_EXPR);
149 132293 : gimple_cond_set_rhs (stmt, build_zero_cst (TREE_TYPE (rhs1)));
150 132293 : EDGE_SUCC (bb, 0)->flags ^= (EDGE_TRUE_VALUE|EDGE_FALSE_VALUE);
151 132293 : EDGE_SUCC (bb, 1)->flags ^= (EDGE_TRUE_VALUE|EDGE_FALSE_VALUE);
152 :
153 132293 : 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 160621477 : cleanup_control_expr_graph (basic_block bb, gimple_stmt_iterator gsi)
167 : {
168 160621477 : edge taken_edge;
169 160621477 : bool retval = false;
170 160621477 : gimple *stmt = gsi_stmt (gsi);
171 :
172 160621477 : if (!single_succ_p (bb))
173 : {
174 160615251 : edge e;
175 160615251 : edge_iterator ei;
176 160615251 : bool warned;
177 160615251 : tree val = NULL_TREE;
178 :
179 : /* Try to convert a switch with just a single non-default case to
180 : GIMPLE condition. */
181 160615251 : if (gimple_code (stmt) == GIMPLE_SWITCH
182 160615251 : && convert_single_case_switch (as_a<gswitch *> (stmt), gsi))
183 11875 : stmt = gsi_stmt (gsi);
184 :
185 160615251 : if (gimple_code (stmt) == GIMPLE_COND)
186 159891318 : canonicalize_bool_cond (as_a<gcond*> (stmt), bb);
187 :
188 160615251 : fold_defer_overflow_warnings ();
189 160615251 : switch (gimple_code (stmt))
190 : {
191 159891318 : case GIMPLE_COND:
192 159891318 : {
193 159891318 : gimple_match_op res_op;
194 159891318 : if (gimple_simplify (stmt, &res_op, NULL, no_follow_ssa_edges,
195 : no_follow_ssa_edges)
196 159891318 : && res_op.code == INTEGER_CST)
197 2671161 : val = res_op.ops[0];
198 : }
199 159891318 : break;
200 :
201 723933 : case GIMPLE_SWITCH:
202 723933 : val = gimple_switch_index (as_a <gswitch *> (stmt));
203 723933 : break;
204 :
205 160615251 : default:
206 160615251 : ;
207 : }
208 160615251 : taken_edge = find_taken_edge (bb, val);
209 160615251 : if (!taken_edge)
210 : {
211 157933159 : fold_undefer_and_ignore_overflow_warnings ();
212 157933159 : return false;
213 : }
214 :
215 : /* Remove all the edges except the one that is always executed. */
216 2682092 : warned = false;
217 8074765 : for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
218 : {
219 5392673 : if (e != taken_edge)
220 : {
221 2710581 : if (!warned)
222 : {
223 2682092 : fold_undefer_overflow_warnings
224 2682092 : (true, stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
225 2682092 : warned = true;
226 : }
227 :
228 2710581 : taken_edge->probability += e->probability;
229 2710581 : remove_edge_and_dominated_blocks (e);
230 2710581 : retval = true;
231 : }
232 : else
233 2682092 : ei_next (&ei);
234 : }
235 2682092 : if (!warned)
236 0 : fold_undefer_and_ignore_overflow_warnings ();
237 : }
238 : else
239 6226 : taken_edge = single_succ_edge (bb);
240 :
241 2688318 : bitmap_set_bit (cfgcleanup_altered_bbs, bb->index);
242 2688318 : gsi_remove (&gsi, true);
243 2688318 : taken_edge->flags &= ~(EDGE_TRUE_VALUE|EDGE_FALSE_VALUE);
244 2688318 : taken_edge->flags |= EDGE_FALLTHRU;
245 :
246 2688318 : return retval;
247 : }
248 :
249 : /* Cleanup the GF_CALL_CTRL_ALTERING flag according to
250 : to updated gimple_call_flags. */
251 :
252 : static void
253 360083250 : cleanup_call_ctrl_altering_flag (basic_block bb, gimple *bb_end)
254 : {
255 360083250 : if (!is_gimple_call (bb_end)
256 68353018 : || !gimple_call_ctrl_altering_p (bb_end)
257 383397357 : || (/* IFN_UNIQUE should be the last insn, to make checking for it
258 : as cheap as possible. */
259 23314107 : gimple_call_internal_p (bb_end)
260 438831 : && gimple_call_internal_unique_p (bb_end)))
261 : return;
262 :
263 22901225 : int flags = gimple_call_flags (bb_end);
264 22901225 : if (!(flags & ECF_NORETURN)
265 84900 : && (((flags & (ECF_CONST | ECF_PURE))
266 1910 : && !(flags & ECF_LOOPING_CONST_OR_PURE))
267 84730 : || (flags & ECF_LEAF)))
268 170 : gimple_call_set_ctrl_altering (bb_end, false);
269 : else
270 : {
271 22901055 : edge_iterator ei;
272 22901055 : edge e;
273 22901055 : bool found = false;
274 25631008 : FOR_EACH_EDGE (e, ei, bb->succs)
275 2848450 : if (e->flags & EDGE_FALLTHRU)
276 : found = true;
277 2737500 : else if (e->flags & EDGE_ABNORMAL)
278 : {
279 : found = false;
280 : break;
281 : }
282 : /* If there's no abnormal edge and a fallthru edge the call
283 : isn't control-altering anymore. */
284 22901055 : if (found)
285 28695 : gimple_call_set_ctrl_altering (bb_end, false);
286 : }
287 : }
288 :
289 : /* Try to remove superfluous control structures in basic block BB. Returns
290 : true if anything changes. */
291 :
292 : static bool
293 400176781 : cleanup_control_flow_bb (basic_block bb)
294 : {
295 400176781 : gimple_stmt_iterator gsi;
296 400176781 : bool retval = false;
297 400176781 : gimple *stmt;
298 :
299 : /* If the last statement of the block could throw and now cannot,
300 : we need to prune cfg. */
301 400176781 : retval |= gimple_purge_dead_eh_edges (bb);
302 :
303 400176781 : gsi = gsi_last_nondebug_bb (bb);
304 400176781 : if (gsi_end_p (gsi))
305 : return retval;
306 :
307 360083250 : stmt = gsi_stmt (gsi);
308 :
309 : /* Try to cleanup ctrl altering flag for call which ends bb. */
310 360083250 : cleanup_call_ctrl_altering_flag (bb, stmt);
311 :
312 360083250 : if (gimple_code (stmt) == GIMPLE_COND
313 360083250 : || gimple_code (stmt) == GIMPLE_SWITCH)
314 : {
315 321242954 : gcc_checking_assert (gsi_stmt (gsi_last_bb (bb)) == stmt);
316 160621477 : retval |= cleanup_control_expr_graph (bb, gsi);
317 : }
318 199461773 : else if (gimple_code (stmt) == GIMPLE_GOTO
319 6246 : && TREE_CODE (gimple_goto_dest (stmt)) == ADDR_EXPR
320 199462146 : && (TREE_CODE (TREE_OPERAND (gimple_goto_dest (stmt), 0))
321 : == LABEL_DECL))
322 : {
323 : /* If we had a computed goto which has a compile-time determinable
324 : destination, then we can eliminate the goto. */
325 171 : edge e;
326 171 : tree label;
327 171 : edge_iterator ei;
328 171 : basic_block target_block;
329 :
330 342 : gcc_checking_assert (gsi_stmt (gsi_last_bb (bb)) == stmt);
331 : /* First look at all the outgoing edges. Delete any outgoing
332 : edges which do not go to the right block. For the one
333 : edge which goes to the right block, fix up its flags. */
334 171 : label = TREE_OPERAND (gimple_goto_dest (stmt), 0);
335 171 : if (DECL_CONTEXT (label) != cfun->decl)
336 8 : return retval;
337 163 : target_block = label_to_block (cfun, label);
338 411 : for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
339 : {
340 248 : if (e->dest != target_block)
341 91 : remove_edge_and_dominated_blocks (e);
342 : else
343 : {
344 : /* Turn off the EDGE_ABNORMAL flag. */
345 157 : e->flags &= ~EDGE_ABNORMAL;
346 :
347 : /* And set EDGE_FALLTHRU. */
348 157 : e->flags |= EDGE_FALLTHRU;
349 157 : ei_next (&ei);
350 : }
351 : }
352 :
353 163 : bitmap_set_bit (cfgcleanup_altered_bbs, bb->index);
354 163 : bitmap_set_bit (cfgcleanup_altered_bbs, target_block->index);
355 :
356 : /* Remove the GOTO_EXPR as it is not needed. The CFG has all the
357 : relevant information we need. */
358 163 : gsi_remove (&gsi, true);
359 163 : retval = true;
360 : }
361 :
362 : /* Check for indirect calls that have been turned into
363 : noreturn calls. */
364 199461602 : else if (is_gimple_call (stmt)
365 199461602 : && gimple_call_noreturn_p (stmt))
366 : {
367 : /* If there are debug stmts after the noreturn call, remove them
368 : now, they should be all unreachable anyway. */
369 22848414 : for (gsi_next (&gsi); !gsi_end_p (gsi); )
370 177 : gsi_remove (&gsi, true);
371 22848237 : if (remove_fallthru_edge (bb->succs))
372 31499 : retval = true;
373 22848237 : tree lhs = gimple_call_lhs (stmt);
374 22848237 : if (!lhs
375 22848237 : || !should_remove_lhs_p (lhs))
376 22848218 : gimple_call_set_ctrl_altering (stmt, true);
377 : }
378 :
379 : return retval;
380 : }
381 :
382 : /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
383 : those alternatives are equal in each of the PHI nodes, then return
384 : true, else return false. */
385 :
386 : bool
387 3918695 : phi_alternatives_equal (basic_block dest, edge e1, edge e2)
388 : {
389 3918695 : int n1 = e1->dest_idx;
390 3918695 : int n2 = e2->dest_idx;
391 3918695 : gphi_iterator gsi;
392 :
393 4261569 : for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
394 : {
395 4210339 : gphi *phi = gsi.phi ();
396 4210339 : tree val1 = gimple_phi_arg_def (phi, n1);
397 4210339 : tree val2 = gimple_phi_arg_def (phi, n2);
398 :
399 4210339 : gcc_assert (val1 != NULL_TREE);
400 4210339 : gcc_assert (val2 != NULL_TREE);
401 :
402 4210339 : if (!operand_equal_for_phi_arg_p (val1, val2))
403 : return false;
404 : }
405 :
406 : return true;
407 : }
408 :
409 : /* Move debug stmts from the forwarder block SRC to DEST or PRED. */
410 :
411 : static void
412 27759847 : move_debug_stmts_from_forwarder (basic_block src,
413 : basic_block dest, bool dest_single_pred_p,
414 : basic_block pred, bool pred_single_succ_p)
415 : {
416 27759847 : if (!MAY_HAVE_DEBUG_STMTS)
417 9844488 : return;
418 :
419 : /* If we cannot move to the destination but to the predecessor do that. */
420 17989286 : if (!dest_single_pred_p && pred_single_succ_p)
421 : {
422 73932 : gimple_stmt_iterator gsi_to = gsi_last_bb (pred);
423 73932 : if (gsi_end_p (gsi_to) || !stmt_ends_bb_p (gsi_stmt (gsi_to)))
424 : {
425 73927 : for (gimple_stmt_iterator gsi = gsi_after_labels (src);
426 252971 : !gsi_end_p (gsi);)
427 : {
428 179044 : gimple *debug = gsi_stmt (gsi);
429 179044 : gcc_assert (is_gimple_debug (debug));
430 179044 : gsi_move_after (&gsi, &gsi_to);
431 : }
432 73927 : return;
433 : }
434 : }
435 :
436 : /* Else move to DEST or drop/reset them. */
437 17915359 : gimple_stmt_iterator gsi_to = gsi_after_labels (dest);
438 33344782 : for (gimple_stmt_iterator gsi = gsi_after_labels (src); !gsi_end_p (gsi);)
439 : {
440 15429423 : gimple *debug = gsi_stmt (gsi);
441 15429423 : gcc_assert (is_gimple_debug (debug));
442 : /* Move debug binds anyway, but not anything else like begin-stmt
443 : markers unless they are always valid at the destination. */
444 15429423 : if (dest_single_pred_p
445 15429423 : || gimple_debug_bind_p (debug))
446 : {
447 14447183 : gsi_move_before (&gsi, &gsi_to);
448 : /* Reset debug-binds that are not always valid at the destination.
449 : Simply dropping them can cause earlier values to become live,
450 : generating wrong debug information.
451 : ??? There are several things we could improve here. For
452 : one we might be able to move stmts to the predecessor.
453 : For anther, if the debug stmt is immediately followed by a
454 : (debug) definition in the destination (on a post-dominated path?)
455 : we can elide it without any bad effects. */
456 14447183 : if (!dest_single_pred_p)
457 : {
458 6150336 : gimple_debug_bind_reset_value (debug);
459 6150336 : update_stmt (debug);
460 : }
461 : }
462 : else
463 982240 : gsi_next (&gsi);
464 : }
465 : }
466 :
467 : /* Returns true if a phi of the basic block BB has an
468 : use of a ssa name that is used in an abnormal edge. */
469 :
470 : static bool
471 19330909 : bb_phis_references_abnormal_uses (basic_block bb)
472 : {
473 19330909 : auto phis = phi_nodes (bb);
474 19330909 : gimple_stmt_iterator i;
475 52392792 : for (i = gsi_start (phis); !gsi_end_p (i); gsi_next (&i))
476 : {
477 33069173 : gphi *phi = as_a<gphi*>(*i);
478 108565378 : for (unsigned indx = 0; indx < gimple_phi_num_args (phi); indx++)
479 : {
480 75503495 : tree value = gimple_phi_arg_def (phi, indx);
481 75503495 : if (TREE_CODE (value) == SSA_NAME
482 75503495 : && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (value))
483 : return true;
484 : }
485 : }
486 : return false;
487 : }
488 :
489 : /* Return true if basic block BB does nothing except pass control
490 : flow to another block and that we can safely insert a label at
491 : the start of the successor block and was removed.
492 :
493 : As a precondition, we require that BB be not equal to
494 : the entry block.
495 : If CAN_SPLIT is true, we can split the edge to have
496 : another bb with with the phi. */
497 :
498 : static bool
499 426368692 : maybe_remove_forwarder_block (basic_block bb, bool can_split = false)
500 : {
501 426368692 : gimple_stmt_iterator gsi;
502 426368692 : location_t locus;
503 :
504 : /* BB must have a single outgoing edge. */
505 812359426 : if (!single_succ_p (bb)
506 : /* BB may not be a predecessor of the exit block. */
507 198737866 : || single_succ (bb) == EXIT_BLOCK_PTR_FOR_FN (cfun)
508 : /* Nor should this be an infinite loop. */
509 166582984 : || single_succ (bb) == bb
510 : /* BB may not have an abnormal outgoing edge. */
511 580233224 : || (single_succ_edge (bb)->flags & EDGE_ABNORMAL))
512 : return false;
513 :
514 166444581 : gcc_checking_assert (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun));
515 :
516 166444581 : locus = single_succ_edge (bb)->goto_locus;
517 :
518 : /* There should not be an edge coming from entry, or an EH edge. */
519 166444581 : {
520 166444581 : edge_iterator ei;
521 166444581 : edge e;
522 :
523 345934134 : FOR_EACH_EDGE (e, ei, bb->preds)
524 202322462 : if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun) || (e->flags & EDGE_EH))
525 22832909 : return false;
526 : /* If goto_locus of any of the edges differs, prevent removing
527 : the forwarder block when not optimizing. */
528 180893198 : else if (!optimize
529 5266644 : && (LOCATION_LOCUS (e->goto_locus) != UNKNOWN_LOCATION
530 4788283 : || LOCATION_LOCUS (locus) != UNKNOWN_LOCATION)
531 182296982 : && e->goto_locus != locus)
532 : return false;
533 : }
534 :
535 : /* If this bb has a single predecessor and that predecssor
536 : has a single successor, this bb will be merged with the
537 : predecessor so ignore it for removing of the forwarder block. */
538 143611672 : if (single_pred_p (bb)
539 143611672 : && single_succ_p (single_pred_edge (bb)->src))
540 : return false;
541 :
542 135169200 : bool has_phi = !gimple_seq_empty_p (phi_nodes (bb));
543 135169200 : basic_block dest = single_succ_edge (bb)->dest;
544 :
545 : /* If the destination block consists of a nonlocal label or is a
546 : EH landing pad, do not merge it. */
547 135169200 : if (glabel *label_stmt = safe_dyn_cast <glabel *> (first_stmt (dest)))
548 8287074 : if (DECL_NONLOCAL (gimple_label_label (label_stmt))
549 8287074 : || EH_LANDING_PAD_NR (gimple_label_label (label_stmt)))
550 : return false;
551 :
552 : /* If there is an abnormal edge to basic block BB, but not into
553 : dest, problems might occur during removal of the phi node at out
554 : of ssa due to overlapping live ranges of registers.
555 :
556 : If there is an abnormal edge in DEST, the problems would occur
557 : anyway since cleanup_dead_labels would then merge the labels for
558 : two different eh regions, and rest of exception handling code
559 : does not like it.
560 :
561 : So if there is an abnormal edge to BB, proceed only if there is
562 : no abnormal edge to DEST and there are no phi nodes in DEST.
563 : If the BB has phi, we don't want to deal with abnormal edges either. */
564 131773119 : if (bb_has_abnormal_pred (bb)
565 131773119 : && (bb_has_abnormal_pred (dest)
566 60711 : || !gimple_seq_empty_p (phi_nodes (dest))
567 53634 : || has_phi))
568 : return false;
569 :
570 : /* When we have a phi, we have to feed into another
571 : basic block with PHI nodes. */
572 131762106 : if (has_phi && gimple_seq_empty_p (phi_nodes (dest)))
573 : return false;
574 :
575 : /* When we have phi, make sure the phi does not have any uses of
576 : names used in abnormal phis. */
577 128336121 : if (has_phi && bb_phis_references_abnormal_uses (bb))
578 : return false;
579 :
580 : /* Now walk through the statements backward. We can ignore labels,
581 : anything else means this is not a forwarder block. */
582 535417168 : for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
583 : {
584 231893942 : gimple *stmt = gsi_stmt (gsi);
585 :
586 231893942 : switch (gimple_code (stmt))
587 : {
588 871719 : case GIMPLE_LABEL:
589 871719 : if (DECL_NONLOCAL (gimple_label_label (as_a <glabel *> (stmt)))
590 871719 : || EH_LANDING_PAD_NR (gimple_label_label (as_a <glabel *> (stmt))))
591 : return false;
592 871412 : if (!optimize
593 29654 : && (gimple_has_location (stmt)
594 2185 : || LOCATION_LOCUS (locus) != UNKNOWN_LOCATION)
595 898881 : && gimple_location (stmt) != locus)
596 : return false;
597 : break;
598 :
599 : /* ??? For now, hope there's a corresponding debug
600 : assignment at the destination. */
601 : case GIMPLE_DEBUG:
602 : break;
603 :
604 : default:
605 : return false;
606 : }
607 : }
608 : /* If BB has PHIs and does not dominate DEST,
609 : then the PHI nodes at DEST must be the only
610 : users of the results of the PHI nodes at BB.
611 : So only check when BB dominates dest. */
612 35814642 : if (has_phi
613 35814642 : && dominated_by_p (CDI_DOMINATORS, dest, bb))
614 : {
615 2282287 : gphi_iterator gsi;
616 2282287 : unsigned int dest_idx = single_succ_edge (bb)->dest_idx;
617 :
618 : /* BB dominates DEST. There may be many users of the PHI
619 : nodes in BB. However, there is still a trivial case we
620 : can handle. If the result of every PHI in BB is used
621 : only by a PHI in DEST, then we can trivially merge the
622 : PHI nodes from BB into DEST. */
623 4688836 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
624 2406549 : gsi_next (&gsi))
625 : {
626 3218230 : gphi *phi = gsi.phi ();
627 3218230 : tree result = gimple_phi_result (phi);
628 3218230 : use_operand_p imm_use;
629 3218230 : gimple *use_stmt;
630 :
631 : /* If the PHI's result is never used, then we can just
632 : ignore it an. */
633 3218230 : if (has_zero_uses (result))
634 71977 : continue;
635 :
636 : /* Get the single use of the result of this PHI node. */
637 3146253 : if (!single_imm_use (result, &imm_use, &use_stmt)
638 2683048 : || gimple_code (use_stmt) != GIMPLE_PHI
639 2407973 : || gimple_bb (use_stmt) != dest
640 5482041 : || gimple_phi_arg_def (use_stmt, dest_idx) != result)
641 811681 : return false;
642 : }
643 : }
644 :
645 35002961 : if (current_loops)
646 : {
647 : /* Protect loop headers. */
648 34107473 : if (bb_loop_header_p (bb))
649 : return false;
650 :
651 : /* Protect loop preheaders and latches if requested. */
652 33949964 : if (dest->loop_father->header == dest)
653 : {
654 12336827 : if (bb->loop_father == dest->loop_father)
655 : {
656 7379680 : if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES))
657 : return false;
658 : /* If bb doesn't have a single predecessor we'd make this
659 : loop have multiple latches. Don't do that if that
660 : would in turn require disambiguating them over again. */
661 404205945 : if (!single_pred_p (bb))
662 : return false;
663 : }
664 : /* cleanup_tree_cfg_noloop just created the loop preheader, don't
665 : remove it if it has phis. */
666 4957147 : else if (bb->loop_father == loop_outer (dest->loop_father)
667 4944878 : && !has_phi
668 8787609 : && !loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS))
669 : ;
670 : else
671 : /* Always preserve other edges into loop headers that are
672 : not simple latches or preheaders. */
673 : return false;
674 : }
675 : }
676 :
677 31516203 : edge succ = single_succ_edge (bb), e, s;
678 31516203 : gimple *stmt;
679 31516203 : gimple_stmt_iterator gsi_to;
680 :
681 : /* If there are phi nodes in DEST, and some of the blocks that are
682 : predecessors of BB are also predecessors of DEST, check that the
683 : phi node arguments match.
684 : Otherwise we have to split the edge and that becomes
685 : a "forwarder" again. */
686 31516203 : if ((!can_split || !has_phi)
687 31516203 : && !gimple_seq_empty_p (phi_nodes (dest)))
688 : {
689 25717895 : edge_iterator ei;
690 50222082 : FOR_EACH_EDGE (e, ei, bb->preds)
691 : {
692 28260543 : s = find_edge (e->src, dest);
693 28260543 : if (!s)
694 24453468 : continue;
695 :
696 3807075 : if (!phi_alternatives_equal (dest, succ, s))
697 3756356 : return false;
698 : }
699 : }
700 :
701 27759847 : basic_block pred = NULL;
702 27759847 : if (single_pred_p (bb))
703 26168585 : pred = single_pred (bb);
704 27759847 : bool dest_single_pred_p = single_pred_p (dest);
705 :
706 : /* Redirect the edges. */
707 58130594 : for (edge_iterator ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
708 : {
709 30370747 : if (cfgcleanup_altered_bbs)
710 30140134 : bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
711 30370747 : s = find_edge (e->src, dest);
712 :
713 : /* See if we can split the edge if we already have an edge from src to dest. */
714 30370747 : if (can_split && has_phi)
715 : /* PHI arguments are different. Create a forwarder block by
716 : splitting E so that we can merge PHI arguments on E to
717 : DEST. */
718 44143 : if (s && !phi_alternatives_equal (dest, s, succ))
719 16540 : e = single_succ_edge (split_edge (e));
720 :
721 30370747 : if (e->flags & EDGE_ABNORMAL)
722 : {
723 : /* If there is an abnormal edge, redirect it anyway, and
724 : move the labels to the new block to make it legal. */
725 183 : s = redirect_edge_succ_nodup (e, dest);
726 : }
727 : else
728 30370564 : s = redirect_edge_and_branch (e, dest);
729 :
730 30370747 : if (s == e)
731 : {
732 : /* If we merge the forwarder with phis into a loop header
733 : verify if we are creating another loop latch edge.
734 : If so, reset number of iteration information of the loop. */
735 30252536 : if (has_phi
736 2804532 : && dest->loop_father
737 2804532 : && dest->loop_father->header == dest
738 30276277 : && dominated_by_p (CDI_DOMINATORS, e->src, dest))
739 : {
740 23741 : dest->loop_father->any_upper_bound = false;
741 23741 : dest->loop_father->any_likely_upper_bound = false;
742 23741 : free_numbers_of_iterations_estimates (dest->loop_father);
743 : }
744 : /* Copy arguments for the phi nodes, since the edge was not
745 : here before. */
746 30252536 : copy_phi_arg_into_existing_phi (succ, s, has_phi);
747 : }
748 : else
749 118211 : redirect_edge_var_map_clear (s);
750 : }
751 :
752 : /* Move nonlocal labels and computed goto targets as well as user
753 : defined labels and labels with an EH landing pad number to the
754 : new block, so that the redirection of the abnormal edges works,
755 : jump targets end up in a sane place and debug information for
756 : labels is retained. */
757 27759847 : gsi_to = gsi_start_bb (dest);
758 55781689 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
759 : {
760 2947336 : stmt = gsi_stmt (gsi);
761 2947336 : if (is_gimple_debug (stmt))
762 : break;
763 :
764 : /* Forwarder blocks can only contain labels and debug stmts, and
765 : labels must come first, so if we get to this point, we know
766 : we're looking at a label. */
767 261995 : tree decl = gimple_label_label (as_a <glabel *> (stmt));
768 261995 : if (EH_LANDING_PAD_NR (decl) != 0
769 261995 : || DECL_NONLOCAL (decl)
770 261995 : || FORCED_LABEL (decl)
771 517337 : || !DECL_ARTIFICIAL (decl))
772 30794 : gsi_move_before (&gsi, &gsi_to);
773 : else
774 231201 : gsi_next (&gsi);
775 : }
776 :
777 : /* Move debug statements. Reset them if the destination does not
778 : have a single predecessor. */
779 55519694 : move_debug_stmts_from_forwarder (bb, dest, dest_single_pred_p,
780 81580325 : pred, pred && single_succ_p (pred));
781 :
782 27759847 : if (cfgcleanup_altered_bbs)
783 27556354 : bitmap_set_bit (cfgcleanup_altered_bbs, dest->index);
784 :
785 : /* Update the dominators. */
786 27759847 : basic_block dom, dombb, domdest;
787 :
788 27759847 : dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
789 27759847 : domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
790 27759847 : if (domdest == bb)
791 : {
792 : /* Shortcut to avoid calling (relatively expensive)
793 : nearest_common_dominator unless necessary. */
794 : dom = dombb;
795 : }
796 : else
797 20753199 : dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
798 :
799 27759847 : set_immediate_dominator (CDI_DOMINATORS, dest, dom);
800 :
801 : /* Adjust latch infomation of BB's parent loop as otherwise
802 : the cfg hook has a hard time not to kill the loop. */
803 27759847 : if (current_loops && bb->loop_father->latch == bb)
804 5590033 : bb->loop_father->latch = pred;
805 :
806 : /* And kill the forwarder block. */
807 27759847 : delete_basic_block (bb);
808 :
809 27759847 : return true;
810 : }
811 :
812 : /* STMT is a call that has been discovered noreturn. Split the
813 : block to prepare fixing up the CFG and remove LHS.
814 : Return true if cleanup-cfg needs to run. */
815 :
816 : bool
817 6381963 : fixup_noreturn_call (gimple *stmt)
818 : {
819 6381963 : basic_block bb = gimple_bb (stmt);
820 6381963 : bool changed = false;
821 :
822 6381963 : if (gimple_call_builtin_p (stmt, BUILT_IN_RETURN))
823 : return false;
824 :
825 : /* First split basic block if stmt is not last. */
826 12760166 : if (stmt != gsi_stmt (gsi_last_bb (bb)))
827 : {
828 42987 : if (stmt == gsi_stmt (gsi_last_nondebug_bb (bb)))
829 : {
830 : /* Don't split if there are only debug stmts
831 : after stmt, that can result in -fcompare-debug
832 : failures. Remove the debug stmts instead,
833 : they should be all unreachable anyway. */
834 6252 : gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
835 54286 : for (gsi_next (&gsi); !gsi_end_p (gsi); )
836 48034 : gsi_remove (&gsi, true);
837 : }
838 : else
839 : {
840 36735 : split_block (bb, stmt);
841 36735 : changed = true;
842 : }
843 : }
844 :
845 : /* If there is an LHS, remove it, but only if its type has fixed size.
846 : The LHS will need to be recreated during RTL expansion and creating
847 : temporaries of variable-sized types is not supported. Also don't
848 : do this with TREE_ADDRESSABLE types, as assign_temp will abort.
849 : Drop LHS regardless of TREE_ADDRESSABLE, if the function call
850 : has been changed into a call that does not return a value, like
851 : __builtin_unreachable or __cxa_pure_virtual. */
852 6380083 : tree lhs = gimple_call_lhs (stmt);
853 6380083 : if (lhs
854 6380083 : && (should_remove_lhs_p (lhs)
855 406 : || VOID_TYPE_P (TREE_TYPE (gimple_call_fntype (stmt)))))
856 : {
857 4128 : gimple_call_set_lhs (stmt, NULL_TREE);
858 :
859 : /* We need to fix up the SSA name to avoid checking errors. */
860 4128 : if (TREE_CODE (lhs) == SSA_NAME)
861 : {
862 3927 : tree new_var = create_tmp_reg (TREE_TYPE (lhs));
863 3927 : SET_SSA_NAME_VAR_OR_IDENTIFIER (lhs, new_var);
864 3927 : SSA_NAME_DEF_STMT (lhs) = gimple_build_nop ();
865 3927 : set_ssa_default_def (cfun, new_var, lhs);
866 : }
867 :
868 4128 : update_stmt (stmt);
869 : }
870 :
871 : /* Mark the call as altering control flow. */
872 6380083 : if (!gimple_call_ctrl_altering_p (stmt))
873 : {
874 86335 : gimple_call_set_ctrl_altering (stmt, true);
875 86335 : changed = true;
876 : }
877 :
878 : return changed;
879 : }
880 :
881 : /* Return true if we want to merge BB1 and BB2 into a single block. */
882 :
883 : static bool
884 412661206 : want_merge_blocks_p (basic_block bb1, basic_block bb2)
885 : {
886 412661206 : if (!can_merge_blocks_p (bb1, bb2))
887 : return false;
888 28903788 : gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb1);
889 28903788 : if (gsi_end_p (gsi) || !stmt_can_terminate_bb_p (gsi_stmt (gsi)))
890 25675617 : return true;
891 3228171 : return bb1->count.ok_for_merging (bb2->count);
892 : }
893 :
894 :
895 : /* Tries to cleanup cfg in basic block BB by merging blocks. Returns
896 : true if anything changes. */
897 :
898 : static bool
899 392771052 : cleanup_tree_cfg_bb (basic_block bb)
900 : {
901 392771052 : if (maybe_remove_forwarder_block (bb))
902 : return true;
903 :
904 : /* If there is a merge opportunity with the predecessor
905 : do nothing now but wait until we process the predecessor.
906 : This happens when we visit BBs in a non-optimal order and
907 : avoids quadratic behavior with adjusting stmts BB pointer. */
908 365214698 : if (single_pred_p (bb)
909 630510664 : && want_merge_blocks_p (single_pred (bb), bb))
910 : /* But make sure we _do_ visit it. When we remove unreachable paths
911 : ending in a backedge we fail to mark the destinations predecessors
912 : as changed. */
913 11857255 : bitmap_set_bit (cfgcleanup_altered_bbs, single_pred (bb)->index);
914 :
915 : /* Merging the blocks may create new opportunities for folding
916 : conditional branches (due to the elimination of single-valued PHI
917 : nodes). */
918 353357443 : else if (single_succ_p (bb)
919 489704475 : && want_merge_blocks_p (bb, single_succ (bb)))
920 : {
921 17046469 : merge_blocks (bb, single_succ (bb));
922 17046469 : return true;
923 : }
924 :
925 : return false;
926 : }
927 :
928 : /* Return true if E is an EDGE_ABNORMAL edge for returns_twice calls,
929 : i.e. one going from .ABNORMAL_DISPATCHER to basic block which doesn't
930 : start with a forced or nonlocal label. Calls which return twice can return
931 : the second time only if they are called normally the first time, so basic
932 : blocks which can be only entered through these abnormal edges but not
933 : normally are effectively unreachable as well. Additionally ignore
934 : __builtin_setjmp_receiver starting blocks, which have one FORCED_LABEL
935 : and which are always only reachable through EDGE_ABNORMAL edge. They are
936 : handled in cleanup_control_flow_pre. */
937 :
938 : static bool
939 346866374 : maybe_dead_abnormal_edge_p (edge e)
940 : {
941 346866374 : if ((e->flags & (EDGE_ABNORMAL | EDGE_EH)) != EDGE_ABNORMAL)
942 : return false;
943 :
944 148096 : gimple_stmt_iterator gsi = gsi_start_nondebug_after_labels_bb (e->src);
945 148096 : gimple *g = gsi_stmt (gsi);
946 148096 : if (!g || !gimple_call_internal_p (g, IFN_ABNORMAL_DISPATCHER))
947 : return false;
948 :
949 19821 : tree target = NULL_TREE;
950 51713 : for (gsi = gsi_start_bb (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
951 31885 : if (glabel *label_stmt = dyn_cast <glabel *> (gsi_stmt (gsi)))
952 : {
953 17998 : tree this_target = gimple_label_label (label_stmt);
954 17998 : if (DECL_NONLOCAL (this_target))
955 : return false;
956 12071 : if (FORCED_LABEL (this_target))
957 : {
958 12071 : if (target)
959 : return false;
960 : target = this_target;
961 : }
962 : }
963 : else
964 : break;
965 :
966 13894 : if (target)
967 : {
968 : /* If there was a single FORCED_LABEL, check for
969 : __builtin_setjmp_receiver with address of that label. */
970 12071 : if (!gsi_end_p (gsi) && is_gimple_debug (gsi_stmt (gsi)))
971 0 : gsi_next_nondebug (&gsi);
972 12071 : if (gsi_end_p (gsi))
973 : return false;
974 12071 : if (!gimple_call_builtin_p (gsi_stmt (gsi), BUILT_IN_SETJMP_RECEIVER))
975 : return false;
976 :
977 12071 : tree arg = gimple_call_arg (gsi_stmt (gsi), 0);
978 12071 : if (TREE_CODE (arg) != ADDR_EXPR || TREE_OPERAND (arg, 0) != target)
979 : return false;
980 : }
981 : return true;
982 : }
983 :
984 : /* If BB is a basic block ending with __builtin_setjmp_setup, return edge
985 : from .ABNORMAL_DISPATCHER basic block to corresponding
986 : __builtin_setjmp_receiver basic block, otherwise return NULL. */
987 : static edge
988 346864527 : builtin_setjmp_setup_bb (basic_block bb)
989 : {
990 346864527 : if (EDGE_COUNT (bb->succs) != 2
991 335906478 : || ((EDGE_SUCC (bb, 0)->flags
992 153637773 : & (EDGE_ABNORMAL | EDGE_EH)) != EDGE_ABNORMAL
993 153542205 : && (EDGE_SUCC (bb, 1)->flags
994 153542205 : & (EDGE_ABNORMAL | EDGE_EH)) != EDGE_ABNORMAL))
995 : return NULL;
996 :
997 168131 : gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
998 168131 : if (gsi_end_p (gsi)
999 168131 : || !gimple_call_builtin_p (gsi_stmt (gsi), BUILT_IN_SETJMP_SETUP))
1000 156084 : return NULL;
1001 :
1002 12047 : tree arg = gimple_call_arg (gsi_stmt (gsi), 1);
1003 12047 : if (TREE_CODE (arg) != ADDR_EXPR
1004 12047 : || TREE_CODE (TREE_OPERAND (arg, 0)) != LABEL_DECL)
1005 : return NULL;
1006 :
1007 12047 : basic_block recv_bb = label_to_block (cfun, TREE_OPERAND (arg, 0));
1008 346864527 : if (EDGE_COUNT (recv_bb->preds) != 1
1009 12047 : || (EDGE_PRED (recv_bb, 0)->flags
1010 12047 : & (EDGE_ABNORMAL | EDGE_EH)) != EDGE_ABNORMAL
1011 24094 : || (EDGE_SUCC (bb, 0)->dest != EDGE_PRED (recv_bb, 0)->src
1012 12047 : && EDGE_SUCC (bb, 1)->dest != EDGE_PRED (recv_bb, 0)->src))
1013 : return NULL;
1014 :
1015 : /* EDGE_PRED (recv_bb, 0)->src should be the .ABNORMAL_DISPATCHER bb. */
1016 : return EDGE_PRED (recv_bb, 0);
1017 : }
1018 :
1019 : /* Do cleanup_control_flow_bb in PRE order. */
1020 :
1021 : static bool
1022 25294045 : cleanup_control_flow_pre ()
1023 : {
1024 25294045 : bool retval = false;
1025 :
1026 : /* We want remove_edge_and_dominated_blocks to only remove edges,
1027 : not dominated blocks which it does when dom info isn't available.
1028 : Pretend so. */
1029 25294045 : dom_state saved_state = dom_info_state (CDI_DOMINATORS);
1030 25294045 : set_dom_info_availability (CDI_DOMINATORS, DOM_NONE);
1031 :
1032 25294045 : auto_vec<edge_iterator, 20> stack (n_basic_blocks_for_fn (cfun) + 2);
1033 25294045 : auto_sbitmap visited (last_basic_block_for_fn (cfun));
1034 25294045 : bitmap_clear (visited);
1035 :
1036 25294045 : vec<edge, va_gc> *setjmp_vec = NULL;
1037 25294045 : auto_vec<basic_block, 4> abnormal_dispatchers;
1038 :
1039 25294045 : stack.quick_push (ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs));
1040 :
1041 877805266 : while (! stack.is_empty ())
1042 : {
1043 : /* Look at the edge on the top of the stack. */
1044 852511221 : edge_iterator ei = stack.last ();
1045 852511221 : basic_block dest = ei_edge (ei)->dest;
1046 :
1047 852511221 : if (dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
1048 827607629 : && !bitmap_bit_p (visited, dest->index)
1049 1199389642 : && (ei_container (ei) == setjmp_vec
1050 346866374 : || !maybe_dead_abnormal_edge_p (ei_edge (ei))))
1051 : {
1052 346864527 : bitmap_set_bit (visited, dest->index);
1053 : /* We only possibly remove edges from DEST here, leaving
1054 : possibly unreachable code in the IL. */
1055 346864527 : retval |= cleanup_control_flow_bb (dest);
1056 :
1057 : /* Check for __builtin_setjmp_setup. Edges from .ABNORMAL_DISPATCH
1058 : to __builtin_setjmp_receiver will be normally ignored by
1059 : maybe_dead_abnormal_edge_p. If DEST is a visited
1060 : __builtin_setjmp_setup, queue edge from .ABNORMAL_DISPATCH
1061 : to __builtin_setjmp_receiver, so that it will be visited too. */
1062 346864527 : if (edge e = builtin_setjmp_setup_bb (dest))
1063 : {
1064 12047 : vec_safe_push (setjmp_vec, e);
1065 12047 : if (vec_safe_length (setjmp_vec) == 1)
1066 6396 : stack.quick_push (ei_start (setjmp_vec));
1067 : }
1068 :
1069 346864527 : if ((ei_edge (ei)->flags
1070 346864527 : & (EDGE_ABNORMAL | EDGE_EH)) == EDGE_ABNORMAL)
1071 : {
1072 146249 : gimple_stmt_iterator gsi
1073 146249 : = gsi_start_nondebug_after_labels_bb (dest);
1074 146249 : gimple *g = gsi_stmt (gsi);
1075 146249 : if (g && gimple_call_internal_p (g, IFN_ABNORMAL_DISPATCHER))
1076 25860 : abnormal_dispatchers.safe_push (dest);
1077 : }
1078 :
1079 1199375748 : if (EDGE_COUNT (dest->succs) > 0)
1080 323879661 : stack.quick_push (ei_start (dest->succs));
1081 : }
1082 : else
1083 : {
1084 505646694 : if (!ei_one_before_end_p (ei))
1085 156466592 : ei_next (&stack.last ());
1086 : else
1087 : {
1088 349180102 : if (ei_container (ei) == setjmp_vec)
1089 6396 : vec_safe_truncate (setjmp_vec, 0);
1090 349180102 : stack.pop ();
1091 : }
1092 : }
1093 : }
1094 :
1095 25294045 : vec_free (setjmp_vec);
1096 :
1097 : /* If we've marked .ABNORMAL_DISPATCHER basic block(s) as visited
1098 : above, but haven't marked any of their successors as visited,
1099 : unmark them now, so that they can be removed as useless. */
1100 75907995 : for (basic_block dispatcher_bb : abnormal_dispatchers)
1101 : {
1102 25860 : edge e;
1103 25860 : edge_iterator ei;
1104 25951 : FOR_EACH_EDGE (e, ei, dispatcher_bb->succs)
1105 25860 : if (bitmap_bit_p (visited, e->dest->index))
1106 : break;
1107 25860 : if (e == NULL)
1108 91 : bitmap_clear_bit (visited, dispatcher_bb->index);
1109 : }
1110 :
1111 25294045 : set_dom_info_availability (CDI_DOMINATORS, saved_state);
1112 :
1113 : /* We are deleting BBs in non-reverse dominator order, make sure
1114 : insert_debug_temps_for_defs is prepared for that. */
1115 25294045 : if (retval)
1116 875077 : free_dominance_info (CDI_DOMINATORS);
1117 :
1118 : /* Remove all now (and previously) unreachable blocks. */
1119 395692842 : for (int i = NUM_FIXED_BLOCKS; i < last_basic_block_for_fn (cfun); ++i)
1120 : {
1121 370398797 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
1122 370398797 : if (bb && !bitmap_bit_p (visited, bb->index))
1123 : {
1124 4665168 : if (!retval)
1125 737501 : free_dominance_info (CDI_DOMINATORS);
1126 4665168 : delete_basic_block (bb);
1127 4665168 : retval = true;
1128 : }
1129 : }
1130 :
1131 25294045 : return retval;
1132 25294045 : }
1133 :
1134 : /* Callback function for make_forwarder_block which returns
1135 : true when E is not a latch. */
1136 :
1137 : static bool
1138 151188 : mfb_keep_latches (edge e, void*)
1139 : {
1140 151188 : return !((dom_info_available_p (CDI_DOMINATORS)
1141 23436 : && dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
1142 143884 : || (e->flags & EDGE_DFS_BACK));
1143 : }
1144 :
1145 : /* Remove unreachable blocks and other miscellaneous clean up work.
1146 : Return true if the flowgraph was modified, false otherwise. */
1147 :
1148 : static bool
1149 25294045 : cleanup_tree_cfg_noloop (unsigned ssa_update_flags)
1150 : {
1151 25294045 : timevar_push (TV_TREE_CLEANUP_CFG);
1152 :
1153 : /* Ensure that we have single entries into loop headers. Otherwise
1154 : if one of the entries is becoming a latch due to CFG cleanup
1155 : (from formerly being part of an irreducible region) then we mess
1156 : up loop fixup and associate the old loop with a different region
1157 : which makes niter upper bounds invalid. See for example PR80549.
1158 : This needs to be done before we remove trivially dead edges as
1159 : we need to capture the dominance state before the pending transform. */
1160 25294045 : if (current_loops)
1161 : {
1162 : /* This needs backedges or dominators. */
1163 22394191 : if (!dom_info_available_p (CDI_DOMINATORS))
1164 6787532 : mark_dfs_back_edges ();
1165 :
1166 93109945 : for (loop_p loop : *get_loops (cfun))
1167 48321563 : if (loop && loop->header)
1168 : {
1169 41228877 : basic_block bb = loop->header;
1170 41228877 : edge_iterator ei;
1171 41228877 : edge e;
1172 41228877 : bool found_latch = false;
1173 41228877 : bool any_abnormal = false;
1174 41228877 : unsigned n = 0;
1175 : /* We are only interested in preserving existing loops, but
1176 : we need to check whether they are still real and of course
1177 : if we need to add a preheader at all. */
1178 79053719 : FOR_EACH_EDGE (e, ei, bb->preds)
1179 : {
1180 37824842 : if (e->flags & EDGE_ABNORMAL)
1181 : {
1182 : any_abnormal = true;
1183 : break;
1184 : }
1185 37824842 : if ((dom_info_available_p (CDI_DOMINATORS)
1186 27608653 : && dominated_by_p (CDI_DOMINATORS, e->src, bb))
1187 51614264 : || (e->flags & EDGE_DFS_BACK))
1188 : {
1189 18935208 : found_latch = true;
1190 18935208 : continue;
1191 : }
1192 18889634 : n++;
1193 : }
1194 : /* If we have more than one entry to the loop header
1195 : create a forwarder. */
1196 41228877 : if (found_latch && ! any_abnormal && n > 1)
1197 : {
1198 46768 : edge fallthru = make_forwarder_block (bb, mfb_keep_latches, NULL);
1199 46768 : loop->header = fallthru->dest;
1200 46768 : if (! loops_state_satisfies_p (LOOPS_NEED_FIXUP))
1201 : {
1202 : /* The loop updating from the CFG hook is incomplete
1203 : when we have multiple latches, fixup manually. */
1204 26422 : remove_bb_from_loops (fallthru->src);
1205 26422 : loop_p cloop = loop;
1206 82896 : FOR_EACH_EDGE (e, ei, fallthru->src->preds)
1207 56474 : cloop = find_common_loop (cloop, e->src->loop_father);
1208 26422 : add_bb_to_loop (fallthru->src, cloop);
1209 : }
1210 : }
1211 : }
1212 : }
1213 :
1214 : /* Prepare the worklists of altered blocks. */
1215 25294045 : cfgcleanup_altered_bbs = BITMAP_ALLOC (NULL);
1216 :
1217 : /* Start by iterating over all basic blocks in PRE order looking for
1218 : edge removal opportunities. Do this first because incoming SSA form
1219 : may be invalid and we want to avoid performing SSA related tasks such
1220 : as propgating out a PHI node during BB merging in that state. This
1221 : also gets rid of unreachable blocks. */
1222 25294045 : bool changed = cleanup_control_flow_pre ();
1223 :
1224 : /* After doing the above SSA form should be valid (or an update SSA
1225 : should be required). */
1226 25294045 : if (ssa_update_flags)
1227 : {
1228 16571405 : timevar_pop (TV_TREE_CLEANUP_CFG);
1229 16571405 : update_ssa (ssa_update_flags);
1230 16571405 : timevar_push (TV_TREE_CLEANUP_CFG);
1231 : }
1232 :
1233 : /* Compute dominator info which we need for the iterative process below.
1234 : Avoid computing the fast query DFS numbers since any block merging
1235 : done will invalidate them anyway. */
1236 25294045 : if (!dom_info_available_p (CDI_DOMINATORS))
1237 8575264 : calculate_dominance_info (CDI_DOMINATORS, false);
1238 : else
1239 16718781 : checking_verify_dominators (CDI_DOMINATORS);
1240 :
1241 : /* During forwarder block cleanup, we may redirect edges out of
1242 : SWITCH_EXPRs, which can get expensive. So we want to enable
1243 : recording of edge to CASE_LABEL_EXPR. */
1244 25294045 : start_recording_case_labels ();
1245 :
1246 : /* Continue by iterating over all basic blocks looking for BB merging
1247 : opportunities. We cannot use FOR_EACH_BB_FN for the BB iteration
1248 : since the basic blocks may get removed. */
1249 25294045 : unsigned n = last_basic_block_for_fn (cfun);
1250 395692842 : for (unsigned i = NUM_FIXED_BLOCKS; i < n; i++)
1251 : {
1252 370398797 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
1253 370398797 : if (bb)
1254 339458798 : changed |= cleanup_tree_cfg_bb (bb);
1255 : }
1256 :
1257 : /* Now process the altered blocks, as long as any are available. */
1258 86840187 : while (!bitmap_empty_p (cfgcleanup_altered_bbs))
1259 : {
1260 61546142 : unsigned i = bitmap_clear_first_set_bit (cfgcleanup_altered_bbs);
1261 61546142 : if (i < NUM_FIXED_BLOCKS)
1262 0 : continue;
1263 :
1264 61546142 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
1265 61546142 : if (!bb)
1266 8233888 : continue;
1267 :
1268 : /* BB merging done by cleanup_tree_cfg_bb can end up propagating
1269 : out single-argument PHIs which in turn can expose
1270 : cleanup_control_flow_bb opportunities so we have to repeat
1271 : that here. */
1272 53312254 : changed |= cleanup_control_flow_bb (bb);
1273 53312254 : changed |= cleanup_tree_cfg_bb (bb);
1274 : }
1275 :
1276 25294045 : end_recording_case_labels ();
1277 25294045 : BITMAP_FREE (cfgcleanup_altered_bbs);
1278 :
1279 25294045 : gcc_assert (dom_info_available_p (CDI_DOMINATORS));
1280 :
1281 : /* Do not renumber blocks if the SCEV cache is active, it is indexed by
1282 : basic-block numbers. */
1283 25294045 : if (! scev_initialized_p ())
1284 24987195 : compact_blocks ();
1285 :
1286 25294045 : checking_verify_flow_info ();
1287 :
1288 25294045 : timevar_pop (TV_TREE_CLEANUP_CFG);
1289 :
1290 25294045 : if (changed && current_loops)
1291 : {
1292 : /* Removing edges and/or blocks may make recorded bounds refer
1293 : to stale GIMPLE stmts now, so clear them. */
1294 6056148 : free_numbers_of_iterations_estimates (cfun);
1295 6056148 : loops_state_set (LOOPS_NEED_FIXUP);
1296 : }
1297 :
1298 25294045 : return changed;
1299 : }
1300 :
1301 : /* Repairs loop structures. */
1302 :
1303 : static void
1304 7741769 : repair_loop_structures (void)
1305 : {
1306 7741769 : bitmap changed_bbs;
1307 7741769 : unsigned n_new_or_deleted_loops;
1308 :
1309 7741769 : calculate_dominance_info (CDI_DOMINATORS);
1310 :
1311 7741769 : timevar_push (TV_REPAIR_LOOPS);
1312 7741769 : changed_bbs = BITMAP_ALLOC (NULL);
1313 7741769 : n_new_or_deleted_loops = fix_loop_structure (changed_bbs);
1314 :
1315 : /* This usually does nothing. But sometimes parts of cfg that originally
1316 : were inside a loop get out of it due to edge removal (since they
1317 : become unreachable by back edges from latch). Also a former
1318 : irreducible loop can become reducible - in this case force a full
1319 : rewrite into loop-closed SSA form. */
1320 7741769 : if (loops_state_satisfies_p (LOOP_CLOSED_SSA)
1321 7741769 : && (!bitmap_empty_p (changed_bbs) || n_new_or_deleted_loops))
1322 25336 : rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1323 :
1324 7741769 : BITMAP_FREE (changed_bbs);
1325 :
1326 7741769 : checking_verify_loop_structure ();
1327 7741769 : scev_reset ();
1328 :
1329 7741769 : timevar_pop (TV_REPAIR_LOOPS);
1330 7741769 : }
1331 :
1332 : /* Cleanup cfg and repair loop structures. */
1333 :
1334 : bool
1335 25294045 : cleanup_tree_cfg (unsigned ssa_update_flags)
1336 : {
1337 25294045 : bool changed = cleanup_tree_cfg_noloop (ssa_update_flags);
1338 :
1339 25294045 : if (current_loops != NULL
1340 25294045 : && loops_state_satisfies_p (LOOPS_NEED_FIXUP))
1341 7741769 : repair_loop_structures ();
1342 :
1343 25294045 : return changed;
1344 : }
1345 :
1346 : /* This pass merges PHI nodes if one feeds into another. For example,
1347 : suppose we have the following:
1348 :
1349 : goto <bb 9> (<L9>);
1350 :
1351 : <L8>:;
1352 : tem_17 = foo ();
1353 :
1354 : # tem_6 = PHI <tem_17(8), tem_23(7)>;
1355 : <L9>:;
1356 :
1357 : # tem_3 = PHI <tem_6(9), tem_2(5)>;
1358 : <L10>:;
1359 :
1360 : Then we merge the first PHI node into the second one like so:
1361 :
1362 : goto <bb 9> (<L10>);
1363 :
1364 : <L8>:;
1365 : tem_17 = foo ();
1366 :
1367 : # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
1368 : <L10>:;
1369 : */
1370 :
1371 : namespace {
1372 :
1373 : const pass_data pass_data_merge_phi =
1374 : {
1375 : GIMPLE_PASS, /* type */
1376 : "mergephi", /* name */
1377 : OPTGROUP_NONE, /* optinfo_flags */
1378 : TV_TREE_MERGE_PHI, /* tv_id */
1379 : ( PROP_cfg | PROP_ssa ), /* properties_required */
1380 : 0, /* properties_provided */
1381 : 0, /* properties_destroyed */
1382 : 0, /* todo_flags_start */
1383 : 0, /* todo_flags_finish */
1384 : };
1385 :
1386 : class pass_merge_phi : public gimple_opt_pass
1387 : {
1388 : public:
1389 866301 : pass_merge_phi (gcc::context *ctxt)
1390 1732602 : : gimple_opt_pass (pass_data_merge_phi, ctxt)
1391 : {}
1392 :
1393 : /* opt_pass methods: */
1394 577534 : opt_pass * clone () final override { return new pass_merge_phi (m_ctxt); }
1395 : unsigned int execute (function *) final override;
1396 :
1397 : }; // class pass_merge_phi
1398 :
1399 : unsigned int
1400 4523704 : pass_merge_phi::execute (function *fun)
1401 : {
1402 4523704 : int forwarder_removed = 0;
1403 4523704 : calculate_dominance_info (CDI_DOMINATORS);
1404 :
1405 : /* Find all PHI nodes that we may be able to merge. */
1406 4523704 : unsigned n = last_basic_block_for_fn (fun);
1407 38193070 : for (unsigned i = NUM_FIXED_BLOCKS; i < n; i++)
1408 : {
1409 33669366 : basic_block bb = BASIC_BLOCK_FOR_FN (fun, i);
1410 33669366 : if (!bb)
1411 71726 : continue;
1412 :
1413 : /* Look for a forwarder block with PHI nodes. */
1414 33597640 : if (maybe_remove_forwarder_block (bb, true))
1415 203493 : forwarder_removed++;
1416 : }
1417 :
1418 : /* Removing forwarder blocks can cause formerly irreducible loops
1419 : to become reducible if we merged two entry blocks. */
1420 4523704 : if (forwarder_removed != 0
1421 87434 : && current_loops)
1422 87434 : loops_state_set (LOOPS_NEED_FIXUP);
1423 :
1424 4523704 : statistics_counter_event (fun, "Forwarder blocks removed",
1425 : forwarder_removed);
1426 4523704 : return 0;
1427 : }
1428 :
1429 : } // anon namespace
1430 :
1431 : gimple_opt_pass *
1432 288767 : make_pass_merge_phi (gcc::context *ctxt)
1433 : {
1434 288767 : return new pass_merge_phi (ctxt);
1435 : }
1436 :
1437 : /* Pass: cleanup the CFG just before expanding trees to RTL.
1438 : This is just a round of label cleanups and case node grouping
1439 : because after the tree optimizers have run such cleanups may
1440 : be necessary. */
1441 :
1442 : static unsigned int
1443 1482258 : execute_cleanup_cfg_post_optimizing (void)
1444 : {
1445 1482258 : unsigned int todo = execute_fixup_cfg ();
1446 1482258 : if (cleanup_tree_cfg ())
1447 396970 : todo |= TODO_update_ssa;
1448 1482258 : maybe_remove_unreachable_handlers ();
1449 1482258 : cleanup_dead_labels ();
1450 1482258 : if (group_case_labels () && cleanup_tree_cfg ())
1451 0 : todo |= TODO_update_ssa;
1452 :
1453 : /* When optimizing undo the merging of forwarder blocks
1454 : that phis for better out of ssa expansion. */
1455 1482258 : if (optimize)
1456 1046612 : make_forwarders_with_degenerate_phis (cfun, true);
1457 :
1458 : /* Make sure todo does not have cleanup cfg as we don't want
1459 : remove the forwarder blocks we just created. cleanup cfg
1460 : has already happened. */
1461 1482258 : todo &= ~TODO_cleanup_cfg;
1462 :
1463 1482258 : basic_block bb = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
1464 1482258 : gimple_stmt_iterator gsi = gsi_start_nondebug_after_labels_bb (bb);
1465 : /* If the first (and only) bb and the only non debug
1466 : statement is __builtin_unreachable call, then replace it with a trap
1467 : so the function is at least one instruction in size. */
1468 1482258 : if (!gsi_end_p (gsi)
1469 1482258 : && gimple_call_builtin_p (gsi_stmt (gsi), BUILT_IN_UNREACHABLE))
1470 : {
1471 348 : if (targetm.have_trap ())
1472 : {
1473 696 : gimple_call_set_fndecl (gsi_stmt (gsi), builtin_decl_implicit (BUILT_IN_UNREACHABLE_TRAP));
1474 348 : update_stmt (gsi_stmt (gsi));
1475 : }
1476 : /* If the target does not have a trap, convert it into an infinite loop. */
1477 : else
1478 : {
1479 0 : gsi_remove (&gsi, true);
1480 0 : make_single_succ_edge (bb, bb, EDGE_FALLTHRU);
1481 0 : fix_loop_structure (NULL);
1482 : }
1483 : }
1484 :
1485 1482258 : if ((flag_compare_debug_opt || flag_compare_debug)
1486 3894 : && flag_dump_final_insns)
1487 : {
1488 3894 : FILE *final_output = fopen (flag_dump_final_insns, "a");
1489 :
1490 3894 : if (!final_output)
1491 : {
1492 0 : error ("could not open final insn dump file %qs: %m",
1493 : flag_dump_final_insns);
1494 0 : flag_dump_final_insns = NULL;
1495 : }
1496 : else
1497 : {
1498 3894 : int save_unnumbered = flag_dump_unnumbered;
1499 3894 : int save_noaddr = flag_dump_noaddr;
1500 :
1501 3894 : flag_dump_noaddr = flag_dump_unnumbered = 1;
1502 3894 : fprintf (final_output, "\n");
1503 3894 : dump_enumerated_decls (final_output,
1504 : dump_flags | TDF_SLIM | TDF_NOUID);
1505 3894 : flag_dump_noaddr = save_noaddr;
1506 3894 : flag_dump_unnumbered = save_unnumbered;
1507 3894 : if (fclose (final_output))
1508 : {
1509 0 : error ("could not close final insn dump file %qs: %m",
1510 : flag_dump_final_insns);
1511 0 : flag_dump_final_insns = NULL;
1512 : }
1513 : }
1514 : }
1515 1482258 : return todo;
1516 : }
1517 :
1518 : namespace {
1519 :
1520 : const pass_data pass_data_cleanup_cfg_post_optimizing =
1521 : {
1522 : GIMPLE_PASS, /* type */
1523 : "optimized", /* name */
1524 : OPTGROUP_NONE, /* optinfo_flags */
1525 : TV_TREE_CLEANUP_CFG, /* tv_id */
1526 : PROP_cfg, /* properties_required */
1527 : 0, /* properties_provided */
1528 : 0, /* properties_destroyed */
1529 : 0, /* todo_flags_start */
1530 : TODO_remove_unused_locals, /* todo_flags_finish */
1531 : };
1532 :
1533 : class pass_cleanup_cfg_post_optimizing : public gimple_opt_pass
1534 : {
1535 : public:
1536 288767 : pass_cleanup_cfg_post_optimizing (gcc::context *ctxt)
1537 577534 : : gimple_opt_pass (pass_data_cleanup_cfg_post_optimizing, ctxt)
1538 : {}
1539 :
1540 : /* opt_pass methods: */
1541 1482258 : unsigned int execute (function *) final override
1542 : {
1543 1482258 : return execute_cleanup_cfg_post_optimizing ();
1544 : }
1545 :
1546 : }; // class pass_cleanup_cfg_post_optimizing
1547 :
1548 : } // anon namespace
1549 :
1550 : gimple_opt_pass *
1551 288767 : make_pass_cleanup_cfg_post_optimizing (gcc::context *ctxt)
1552 : {
1553 288767 : return new pass_cleanup_cfg_post_optimizing (ctxt);
1554 : }
1555 :
1556 :
1557 : /* Delete all unreachable basic blocks and update callgraph.
1558 : Doing so is somewhat nontrivial because we need to update all clones and
1559 : remove inline function that become unreachable. */
1560 :
1561 : bool
1562 1588267 : delete_unreachable_blocks_update_callgraph (cgraph_node *dst_node,
1563 : bool update_clones)
1564 : {
1565 1588267 : bool changed = false;
1566 1588267 : basic_block b, next_bb;
1567 :
1568 1588267 : find_unreachable_blocks ();
1569 :
1570 : /* Delete all unreachable basic blocks. */
1571 :
1572 1588267 : for (b = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; b
1573 30556036 : != EXIT_BLOCK_PTR_FOR_FN (cfun); b = next_bb)
1574 : {
1575 28967769 : next_bb = b->next_bb;
1576 :
1577 28967769 : if (!(b->flags & BB_REACHABLE))
1578 : {
1579 38678 : gimple_stmt_iterator bsi;
1580 :
1581 152347 : for (bsi = gsi_start_bb (b); !gsi_end_p (bsi); gsi_next (&bsi))
1582 : {
1583 74991 : struct cgraph_edge *e;
1584 74991 : struct cgraph_node *node;
1585 :
1586 74991 : dst_node->remove_stmt_references (gsi_stmt (bsi));
1587 :
1588 74991 : if (gimple_code (gsi_stmt (bsi)) == GIMPLE_CALL
1589 74991 : &&(e = dst_node->get_edge (gsi_stmt (bsi))) != NULL)
1590 : {
1591 888 : if (!e->inline_failed)
1592 0 : e->callee->remove_symbol_and_inline_clones (dst_node);
1593 : else
1594 888 : cgraph_edge::remove (e);
1595 : }
1596 74991 : if (update_clones && dst_node->clones)
1597 0 : for (node = dst_node->clones; node != dst_node;)
1598 : {
1599 0 : node->remove_stmt_references (gsi_stmt (bsi));
1600 0 : if (gimple_code (gsi_stmt (bsi)) == GIMPLE_CALL
1601 0 : && (e = node->get_edge (gsi_stmt (bsi))) != NULL)
1602 : {
1603 0 : if (!e->inline_failed)
1604 0 : e->callee->remove_symbol_and_inline_clones (dst_node);
1605 : else
1606 0 : cgraph_edge::remove (e);
1607 : }
1608 :
1609 0 : if (node->clones)
1610 : node = node->clones;
1611 0 : else if (node->next_sibling_clone)
1612 : node = node->next_sibling_clone;
1613 : else
1614 : {
1615 0 : while (node != dst_node && !node->next_sibling_clone)
1616 0 : node = node->clone_of;
1617 0 : if (node != dst_node)
1618 0 : node = node->next_sibling_clone;
1619 : }
1620 : }
1621 : }
1622 38678 : delete_basic_block (b);
1623 38678 : changed = true;
1624 : }
1625 : }
1626 :
1627 1588267 : return changed;
1628 : }
1629 :
|
