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 22419164 : remove_fallthru_edge (vec<edge, va_gc> *ev)
66 : {
67 22419164 : edge_iterator ei;
68 22419164 : edge e;
69 :
70 25082368 : FOR_EACH_EDGE (e, ei, ev)
71 2697051 : if ((e->flags & EDGE_FALLTHRU) != 0)
72 : {
73 33847 : if (e->flags & EDGE_COMPLEX)
74 0 : e->flags &= ~EDGE_FALLTHRU;
75 : else
76 33847 : remove_edge_and_dominated_blocks (e);
77 33847 : 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 732280 : convert_single_case_switch (gswitch *swtch, gimple_stmt_iterator &gsi)
87 : {
88 732280 : if (gimple_switch_num_labels (swtch) != 2)
89 : return false;
90 :
91 11777 : tree index = gimple_switch_index (swtch);
92 11777 : tree label = gimple_switch_label (swtch, 1);
93 11777 : tree low = CASE_LOW (label);
94 11777 : tree high = CASE_HIGH (label);
95 :
96 11777 : basic_block default_bb = gimple_switch_default_bb (cfun, swtch);
97 11777 : basic_block case_bb = label_to_block (cfun, CASE_LABEL (label));
98 :
99 11777 : basic_block bb = gimple_bb (swtch);
100 11777 : gcond *cond;
101 :
102 : /* Replace switch statement with condition statement. */
103 11777 : if (high)
104 : {
105 1020 : tree lhs, rhs;
106 1020 : if (range_check_type (TREE_TYPE (index)) == NULL_TREE)
107 0 : return false;
108 1020 : generate_range_test (bb, index, low, high, &lhs, &rhs);
109 1020 : cond = gimple_build_cond (LE_EXPR, lhs, rhs, NULL_TREE, NULL_TREE);
110 : }
111 : else
112 10757 : cond = gimple_build_cond (EQ_EXPR, index,
113 10757 : fold_convert (TREE_TYPE (index), low),
114 : NULL_TREE, NULL_TREE);
115 :
116 11777 : gsi_replace (&gsi, cond, true);
117 :
118 : /* Update edges. */
119 11777 : edge case_edge = find_edge (bb, case_bb);
120 11777 : edge default_edge = find_edge (bb, default_bb);
121 :
122 11777 : case_edge->flags |= EDGE_TRUE_VALUE;
123 11777 : default_edge->flags |= EDGE_FALSE_VALUE;
124 11777 : 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 177202723 : canonicalize_bool_cond (gcond *stmt, basic_block bb)
131 : {
132 177202723 : tree rhs1 = gimple_cond_lhs (stmt);
133 177202723 : tree rhs2 = gimple_cond_rhs (stmt);
134 177202723 : enum tree_code code = gimple_cond_code (stmt);
135 177202723 : if (code != EQ_EXPR && code != NE_EXPR)
136 : return false;
137 133111115 : if (TREE_CODE (TREE_TYPE (rhs1)) != BOOLEAN_TYPE
138 133111115 : && (!INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
139 76860906 : || TYPE_PRECISION (TREE_TYPE (rhs1)) != 1))
140 : return false;
141 :
142 : /* Canonicalize _Bool == 0 and _Bool != 1 to _Bool != 0 by swapping edges. */
143 23469107 : if (code == EQ_EXPR && !integer_zerop (rhs2))
144 : return false;
145 23322993 : if (code == NE_EXPR && !integer_onep (rhs2))
146 : return false;
147 :
148 131143 : gimple_cond_set_code (stmt, NE_EXPR);
149 131143 : gimple_cond_set_rhs (stmt, build_zero_cst (TREE_TYPE (rhs1)));
150 131143 : EDGE_SUCC (bb, 0)->flags ^= (EDGE_TRUE_VALUE|EDGE_FALSE_VALUE);
151 131143 : EDGE_SUCC (bb, 1)->flags ^= (EDGE_TRUE_VALUE|EDGE_FALSE_VALUE);
152 :
153 131143 : 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 159089216 : cleanup_control_expr_graph (basic_block bb, gimple_stmt_iterator gsi)
167 : {
168 159089216 : edge taken_edge;
169 159089216 : bool retval = false;
170 159089216 : gimple *stmt = gsi_stmt (gsi);
171 :
172 159089216 : if (!single_succ_p (bb))
173 : {
174 159083029 : edge e;
175 159083029 : edge_iterator ei;
176 159083029 : bool warned;
177 159083029 : tree val = NULL_TREE;
178 :
179 : /* Try to convert a switch with just a single non-default case to
180 : GIMPLE condition. */
181 159083029 : if (gimple_code (stmt) == GIMPLE_SWITCH
182 159083029 : && convert_single_case_switch (as_a<gswitch *> (stmt), gsi))
183 11777 : stmt = gsi_stmt (gsi);
184 :
185 159083029 : if (gimple_code (stmt) == GIMPLE_COND)
186 158362526 : canonicalize_bool_cond (as_a<gcond*> (stmt), bb);
187 :
188 159083029 : fold_defer_overflow_warnings ();
189 159083029 : switch (gimple_code (stmt))
190 : {
191 158362526 : case GIMPLE_COND:
192 158362526 : {
193 158362526 : gimple_match_op res_op;
194 158362526 : if (gimple_simplify (stmt, &res_op, NULL, no_follow_ssa_edges,
195 : no_follow_ssa_edges)
196 158362526 : && res_op.code == INTEGER_CST)
197 2623485 : val = res_op.ops[0];
198 : }
199 158362526 : break;
200 :
201 720503 : case GIMPLE_SWITCH:
202 720503 : val = gimple_switch_index (as_a <gswitch *> (stmt));
203 720503 : break;
204 :
205 159083029 : default:
206 159083029 : ;
207 : }
208 159083029 : taken_edge = find_taken_edge (bb, val);
209 159083029 : if (!taken_edge)
210 : {
211 156448629 : fold_undefer_and_ignore_overflow_warnings ();
212 156448629 : return false;
213 : }
214 :
215 : /* Remove all the edges except the one that is always executed. */
216 2634400 : warned = false;
217 7931671 : for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
218 : {
219 5297271 : if (e != taken_edge)
220 : {
221 2662871 : if (!warned)
222 : {
223 2634400 : fold_undefer_overflow_warnings
224 2634400 : (true, stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
225 2634400 : warned = true;
226 : }
227 :
228 2662871 : taken_edge->probability += e->probability;
229 2662871 : remove_edge_and_dominated_blocks (e);
230 2662871 : retval = true;
231 : }
232 : else
233 2634400 : ei_next (&ei);
234 : }
235 2634400 : if (!warned)
236 0 : fold_undefer_and_ignore_overflow_warnings ();
237 : }
238 : else
239 6187 : taken_edge = single_succ_edge (bb);
240 :
241 2640587 : bitmap_set_bit (cfgcleanup_altered_bbs, bb->index);
242 2640587 : gsi_remove (&gsi, true);
243 2640587 : taken_edge->flags &= ~(EDGE_TRUE_VALUE|EDGE_FALSE_VALUE);
244 2640587 : taken_edge->flags |= EDGE_FALLTHRU;
245 :
246 2640587 : 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 355139920 : cleanup_call_ctrl_altering_flag (basic_block bb, gimple *bb_end)
254 : {
255 355139920 : if (!is_gimple_call (bb_end)
256 66866196 : || !gimple_call_ctrl_altering_p (bb_end)
257 378025047 : || (/* IFN_UNIQUE should be the last insn, to make checking for it
258 : as cheap as possible. */
259 22885127 : gimple_call_internal_p (bb_end)
260 438417 : && gimple_call_internal_unique_p (bb_end)))
261 : return;
262 :
263 22472245 : int flags = gimple_call_flags (bb_end);
264 22472245 : if (!(flags & ECF_NORETURN)
265 84333 : && (((flags & (ECF_CONST | ECF_PURE))
266 1940 : && !(flags & ECF_LOOPING_CONST_OR_PURE))
267 84163 : || (flags & ECF_LEAF)))
268 170 : gimple_call_set_ctrl_altering (bb_end, false);
269 : else
270 : {
271 22472075 : edge_iterator ei;
272 22472075 : edge e;
273 22472075 : bool found = false;
274 25210366 : FOR_EACH_EDGE (e, ei, bb->succs)
275 2855564 : if (e->flags & EDGE_FALLTHRU)
276 : found = true;
277 2742852 : 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 22472075 : if (found)
285 31061 : 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 394725959 : cleanup_control_flow_bb (basic_block bb)
294 : {
295 394725959 : gimple_stmt_iterator gsi;
296 394725959 : bool retval = false;
297 394725959 : gimple *stmt;
298 :
299 : /* If the last statement of the block could throw and now cannot,
300 : we need to prune cfg. */
301 394725959 : retval |= gimple_purge_dead_eh_edges (bb);
302 :
303 394725959 : gsi = gsi_last_nondebug_bb (bb);
304 394725959 : if (gsi_end_p (gsi))
305 : return retval;
306 :
307 355139920 : stmt = gsi_stmt (gsi);
308 :
309 : /* Try to cleanup ctrl altering flag for call which ends bb. */
310 355139920 : cleanup_call_ctrl_altering_flag (bb, stmt);
311 :
312 355139920 : if (gimple_code (stmt) == GIMPLE_COND
313 355139920 : || gimple_code (stmt) == GIMPLE_SWITCH)
314 : {
315 318178432 : gcc_checking_assert (gsi_stmt (gsi_last_bb (bb)) == stmt);
316 159089216 : retval |= cleanup_control_expr_graph (bb, gsi);
317 : }
318 196050704 : else if (gimple_code (stmt) == GIMPLE_GOTO
319 6248 : && TREE_CODE (gimple_goto_dest (stmt)) == ADDR_EXPR
320 196051077 : && (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 196050533 : else if (is_gimple_call (stmt)
365 196050533 : && 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 22419341 : for (gsi_next (&gsi); !gsi_end_p (gsi); )
370 177 : gsi_remove (&gsi, true);
371 22419164 : if (remove_fallthru_edge (bb->succs))
372 33847 : retval = true;
373 22419164 : tree lhs = gimple_call_lhs (stmt);
374 22419164 : if (!lhs
375 22419164 : || !should_remove_lhs_p (lhs))
376 22419145 : 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 3868343 : phi_alternatives_equal (basic_block dest, edge e1, edge e2)
388 : {
389 3868343 : int n1 = e1->dest_idx;
390 3868343 : int n2 = e2->dest_idx;
391 3868343 : gphi_iterator gsi;
392 :
393 4236194 : for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
394 : {
395 4177296 : gphi *phi = gsi.phi ();
396 4177296 : tree val1 = gimple_phi_arg_def (phi, n1);
397 4177296 : tree val2 = gimple_phi_arg_def (phi, n2);
398 :
399 4177296 : gcc_assert (val1 != NULL_TREE);
400 4177296 : gcc_assert (val2 != NULL_TREE);
401 :
402 4177296 : 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 27582774 : 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 27582774 : if (!MAY_HAVE_DEBUG_STMTS)
417 9841641 : return;
418 :
419 : /* If we cannot move to the destination but to the predecessor do that. */
420 17813583 : if (!dest_single_pred_p && pred_single_succ_p)
421 : {
422 72455 : gimple_stmt_iterator gsi_to = gsi_last_bb (pred);
423 72455 : if (gsi_end_p (gsi_to) || !stmt_ends_bb_p (gsi_stmt (gsi_to)))
424 : {
425 72450 : for (gimple_stmt_iterator gsi = gsi_after_labels (src);
426 249047 : !gsi_end_p (gsi);)
427 : {
428 176597 : gimple *debug = gsi_stmt (gsi);
429 176597 : gcc_assert (is_gimple_debug (debug));
430 176597 : gsi_move_after (&gsi, &gsi_to);
431 : }
432 72450 : return;
433 : }
434 : }
435 :
436 : /* Else move to DEST or drop/reset them. */
437 17741133 : gimple_stmt_iterator gsi_to = gsi_after_labels (dest);
438 33387115 : for (gimple_stmt_iterator gsi = gsi_after_labels (src); !gsi_end_p (gsi);)
439 : {
440 15645982 : gimple *debug = gsi_stmt (gsi);
441 15645982 : 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 15645982 : if (dest_single_pred_p
445 15645982 : || gimple_debug_bind_p (debug))
446 : {
447 14602172 : 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 14602172 : if (!dest_single_pred_p)
457 : {
458 6147569 : gimple_debug_bind_reset_value (debug);
459 6147569 : update_stmt (debug);
460 : }
461 : }
462 : else
463 1043810 : gsi_next (&gsi);
464 : }
465 : }
466 :
467 : /* Return true if basic block BB does nothing except pass control
468 : flow to another block and that we can safely insert a label at
469 : the start of the successor block and was removed.
470 :
471 : As a precondition, we require that BB be not equal to
472 : the entry block.
473 : If CAN_SPLIT is true, we can split the edge to have
474 : another bb with with the phi. */
475 :
476 : static bool
477 420694165 : maybe_remove_forwarder_block (basic_block bb, bool can_split = false)
478 : {
479 420694165 : gimple_stmt_iterator gsi;
480 420694165 : location_t locus;
481 :
482 : /* BB must have a single outgoing edge. */
483 801658427 : if (!single_succ_p (bb)
484 : /* BB may not be a predecessor of the exit block. */
485 196063852 : || single_succ (bb) == EXIT_BLOCK_PTR_FOR_FN (cfun)
486 : /* Nor should this be an infinite loop. */
487 164367858 : || single_succ (bb) == bb
488 : /* BB may not have an abnormal outgoing edge. */
489 572814516 : || (single_succ_edge (bb)->flags & EDGE_ABNORMAL))
490 : return false;
491 :
492 164229944 : gcc_checking_assert (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun));
493 :
494 164229944 : locus = single_succ_edge (bb)->goto_locus;
495 :
496 : /* There should not be an edge coming from entry, or an EH edge. */
497 164229944 : {
498 164229944 : edge_iterator ei;
499 164229944 : edge e;
500 :
501 341569104 : FOR_EACH_EDGE (e, ei, bb->preds)
502 199654728 : if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun) || (e->flags & EDGE_EH))
503 22315568 : return false;
504 : /* If goto_locus of any of the edges differs, prevent removing
505 : the forwarder block when not optimizing. */
506 178728527 : else if (!optimize
507 5241959 : && (LOCATION_LOCUS (e->goto_locus) != UNKNOWN_LOCATION
508 4771307 : || LOCATION_LOCUS (locus) != UNKNOWN_LOCATION)
509 180118033 : && e->goto_locus != locus)
510 : return false;
511 : }
512 :
513 : /* If this bb has a single predecessor and that predecssor
514 : has a single successor, this bb will be merged with the
515 : predecessor so ignore it for removing of the forwarder block. */
516 141914376 : if (single_pred_p (bb)
517 141914376 : && single_succ_p (single_pred_edge (bb)->src))
518 : return false;
519 :
520 133725387 : bool has_phi = !gimple_seq_empty_p (phi_nodes (bb));
521 133725387 : basic_block dest = single_succ_edge (bb)->dest;
522 :
523 : /* If the destination block consists of a nonlocal label or is a
524 : EH landing pad, do not merge it. */
525 133725387 : if (glabel *label_stmt = safe_dyn_cast <glabel *> (first_stmt (dest)))
526 8270313 : if (DECL_NONLOCAL (gimple_label_label (label_stmt))
527 8270313 : || EH_LANDING_PAD_NR (gimple_label_label (label_stmt)))
528 : return false;
529 :
530 : /* If there is an abnormal edge to basic block BB, but not into
531 : dest, problems might occur during removal of the phi node at out
532 : of ssa due to overlapping live ranges of registers.
533 :
534 : If there is an abnormal edge in DEST, the problems would occur
535 : anyway since cleanup_dead_labels would then merge the labels for
536 : two different eh regions, and rest of exception handling code
537 : does not like it.
538 :
539 : So if there is an abnormal edge to BB, proceed only if there is
540 : no abnormal edge to DEST and there are no phi nodes in DEST.
541 : If the BB has phi, we don't want to deal with abnormal edges either. */
542 130337603 : if (bb_has_abnormal_pred (bb)
543 130337603 : && (bb_has_abnormal_pred (dest)
544 60728 : || !gimple_seq_empty_p (phi_nodes (dest))
545 53634 : || has_phi))
546 : return false;
547 :
548 : /* When we have a phi, we have to feed into another
549 : basic block with PHI nodes. */
550 130326571 : if (has_phi && gimple_seq_empty_p (phi_nodes (dest)))
551 : return false;
552 :
553 : /* Now walk through the statements backward. We can ignore labels,
554 : anything else means this is not a forwarder block. */
555 529834964 : for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
556 : {
557 229350203 : gimple *stmt = gsi_stmt (gsi);
558 :
559 229350203 : switch (gimple_code (stmt))
560 : {
561 871314 : case GIMPLE_LABEL:
562 871314 : if (DECL_NONLOCAL (gimple_label_label (as_a <glabel *> (stmt)))
563 871314 : || EH_LANDING_PAD_NR (gimple_label_label (as_a <glabel *> (stmt))))
564 : return false;
565 871007 : if (!optimize
566 29651 : && (gimple_has_location (stmt)
567 2184 : || LOCATION_LOCUS (locus) != UNKNOWN_LOCATION)
568 898474 : && gimple_location (stmt) != locus)
569 : return false;
570 : break;
571 :
572 : /* ??? For now, hope there's a corresponding debug
573 : assignment at the destination. */
574 : case GIMPLE_DEBUG:
575 : break;
576 :
577 : default:
578 : return false;
579 : }
580 : }
581 : /* If BB has PHIs and does not dominate DEST,
582 : then the PHI nodes at DEST must be the only
583 : users of the results of the PHI nodes at BB.
584 : So only check when BB dominates dest. */
585 35567279 : if (has_phi
586 35567279 : && dominated_by_p (CDI_DOMINATORS, dest, bb))
587 : {
588 2272881 : gphi_iterator gsi;
589 2272881 : unsigned int dest_idx = single_succ_edge (bb)->dest_idx;
590 :
591 : /* BB dominates DEST. There may be many users of the PHI
592 : nodes in BB. However, there is still a trivial case we
593 : can handle. If the result of every PHI in BB is used
594 : only by a PHI in DEST, then we can trivially merge the
595 : PHI nodes from BB into DEST. */
596 4667124 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
597 2394243 : gsi_next (&gsi))
598 : {
599 3201922 : gphi *phi = gsi.phi ();
600 3201922 : tree result = gimple_phi_result (phi);
601 3201922 : use_operand_p imm_use;
602 3201922 : gimple *use_stmt;
603 :
604 : /* If the PHI's result is never used, then we can just
605 : ignore it an. */
606 3201922 : if (has_zero_uses (result))
607 71205 : continue;
608 :
609 : /* Get the single use of the result of this PHI node. */
610 3130717 : if (!single_imm_use (result, &imm_use, &use_stmt)
611 2668044 : || gimple_code (use_stmt) != GIMPLE_PHI
612 2394088 : || gimple_bb (use_stmt) != dest
613 5454971 : || gimple_phi_arg_def (use_stmt, dest_idx) != result)
614 807679 : return false;
615 : }
616 : }
617 :
618 34759600 : if (current_loops)
619 : {
620 : /* Protect loop headers. */
621 33867657 : if (bb_loop_header_p (bb))
622 : return false;
623 :
624 : /* Protect loop preheaders and latches if requested. */
625 33710144 : if (dest->loop_father->header == dest)
626 : {
627 12286499 : if (bb->loop_father == dest->loop_father)
628 : {
629 7342498 : if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES))
630 : return false;
631 : /* If bb doesn't have a single predecessor we'd make this
632 : loop have multiple latches. Don't do that if that
633 : would in turn require disambiguating them over again. */
634 398678503 : if (!single_pred_p (bb))
635 : return false;
636 : }
637 : /* cleanup_tree_cfg_noloop just created the loop preheader, don't
638 : remove it if it has phis. */
639 4944001 : else if (bb->loop_father == loop_outer (dest->loop_father)
640 4931726 : && !has_phi
641 8762583 : && !loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS))
642 : ;
643 : else
644 : /* Always preserve other edges into loop headers that are
645 : not simple latches or preheaders. */
646 : return false;
647 : }
648 : }
649 :
650 31281582 : edge succ = single_succ_edge (bb), e, s;
651 31281582 : gimple *stmt;
652 31281582 : gimple_stmt_iterator gsi_to;
653 :
654 : /* If there are phi nodes in DEST, and some of the blocks that are
655 : predecessors of BB are also predecessors of DEST, check that the
656 : phi node arguments match.
657 : Otherwise we have to split the edge and that becomes
658 : a "forwarder" again. */
659 31281582 : if ((!can_split || !has_phi)
660 31281582 : && !gimple_seq_empty_p (phi_nodes (dest)))
661 : {
662 25527764 : edge_iterator ei;
663 49854503 : FOR_EACH_EDGE (e, ei, bb->preds)
664 : {
665 28025547 : s = find_edge (e->src, dest);
666 28025547 : if (!s)
667 24268352 : continue;
668 :
669 3757195 : if (!phi_alternatives_equal (dest, succ, s))
670 3698808 : return false;
671 : }
672 : }
673 :
674 27582774 : basic_block pred = NULL;
675 27582774 : if (single_pred_p (bb))
676 26000331 : pred = single_pred (bb);
677 27582774 : bool dest_single_pred_p = single_pred_p (dest);
678 :
679 : /* Redirect the edges. */
680 57751414 : for (edge_iterator ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
681 : {
682 30168640 : if (cfgcleanup_altered_bbs)
683 29939074 : bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
684 30168640 : s = find_edge (e->src, dest);
685 :
686 : /* See if we can split the edge if we already have an edge from src to dest. */
687 30168640 : if (can_split && has_phi)
688 : /* PHI arguments are different. Create a forwarder block by
689 : splitting E so that we can merge PHI arguments on E to
690 : DEST. */
691 44070 : if (s && !phi_alternatives_equal (dest, s, succ))
692 16257 : e = single_succ_edge (split_edge (e));
693 :
694 30168640 : if (e->flags & EDGE_ABNORMAL)
695 : {
696 : /* If there is an abnormal edge, redirect it anyway, and
697 : move the labels to the new block to make it legal. */
698 183 : s = redirect_edge_succ_nodup (e, dest);
699 : }
700 : else
701 30168457 : s = redirect_edge_and_branch (e, dest);
702 :
703 30168640 : if (s == e)
704 : {
705 : /* If we merge the forwarder with phis into a loop header
706 : verify if we are creating another loop latch edge.
707 : If so, reset number of iteration information of the loop. */
708 30051941 : if (has_phi
709 2781758 : && dest->loop_father
710 2781758 : && dest->loop_father->header == dest
711 30075652 : && dominated_by_p (CDI_DOMINATORS, e->src, dest))
712 : {
713 23711 : dest->loop_father->any_upper_bound = false;
714 23711 : dest->loop_father->any_likely_upper_bound = false;
715 23711 : free_numbers_of_iterations_estimates (dest->loop_father);
716 : }
717 : /* Copy arguments for the phi nodes, since the edge was not
718 : here before. */
719 30051941 : copy_phi_arg_into_existing_phi (succ, s, has_phi);
720 : }
721 : else
722 116699 : redirect_edge_var_map_clear (s);
723 : }
724 :
725 : /* Move nonlocal labels and computed goto targets as well as user
726 : defined labels and labels with an EH landing pad number to the
727 : new block, so that the redirection of the abnormal edges works,
728 : jump targets end up in a sane place and debug information for
729 : labels is retained. */
730 27582774 : gsi_to = gsi_start_bb (dest);
731 55427391 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
732 : {
733 2922184 : stmt = gsi_stmt (gsi);
734 2922184 : if (is_gimple_debug (stmt))
735 : break;
736 :
737 : /* Forwarder blocks can only contain labels and debug stmts, and
738 : labels must come first, so if we get to this point, we know
739 : we're looking at a label. */
740 261843 : tree decl = gimple_label_label (as_a <glabel *> (stmt));
741 261843 : if (EH_LANDING_PAD_NR (decl) != 0
742 261843 : || DECL_NONLOCAL (decl)
743 261843 : || FORCED_LABEL (decl)
744 517153 : || !DECL_ARTIFICIAL (decl))
745 31088 : gsi_move_before (&gsi, &gsi_to);
746 : else
747 230755 : gsi_next (&gsi);
748 : }
749 :
750 : /* Move debug statements. Reset them if the destination does not
751 : have a single predecessor. */
752 55165548 : move_debug_stmts_from_forwarder (bb, dest, dest_single_pred_p,
753 81059420 : pred, pred && single_succ_p (pred));
754 :
755 27582774 : if (cfgcleanup_altered_bbs)
756 27380273 : bitmap_set_bit (cfgcleanup_altered_bbs, dest->index);
757 :
758 : /* Update the dominators. */
759 27582774 : basic_block dom, dombb, domdest;
760 :
761 27582774 : dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
762 27582774 : domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
763 27582774 : if (domdest == bb)
764 : {
765 : /* Shortcut to avoid calling (relatively expensive)
766 : nearest_common_dominator unless necessary. */
767 : dom = dombb;
768 : }
769 : else
770 20603300 : dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
771 :
772 27582774 : set_immediate_dominator (CDI_DOMINATORS, dest, dom);
773 :
774 : /* Adjust latch infomation of BB's parent loop as otherwise
775 : the cfg hook has a hard time not to kill the loop. */
776 27582774 : if (current_loops && bb->loop_father->latch == bb)
777 5560055 : bb->loop_father->latch = pred;
778 :
779 : /* And kill the forwarder block. */
780 27582774 : delete_basic_block (bb);
781 :
782 27582774 : return true;
783 : }
784 :
785 : /* STMT is a call that has been discovered noreturn. Split the
786 : block to prepare fixing up the CFG and remove LHS.
787 : Return true if cleanup-cfg needs to run. */
788 :
789 : bool
790 6319348 : fixup_noreturn_call (gimple *stmt)
791 : {
792 6319348 : basic_block bb = gimple_bb (stmt);
793 6319348 : bool changed = false;
794 :
795 6319348 : if (gimple_call_builtin_p (stmt, BUILT_IN_RETURN))
796 : return false;
797 :
798 : /* First split basic block if stmt is not last. */
799 12634936 : if (stmt != gsi_stmt (gsi_last_bb (bb)))
800 : {
801 45866 : if (stmt == gsi_stmt (gsi_last_nondebug_bb (bb)))
802 : {
803 : /* Don't split if there are only debug stmts
804 : after stmt, that can result in -fcompare-debug
805 : failures. Remove the debug stmts instead,
806 : they should be all unreachable anyway. */
807 6732 : gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
808 59147 : for (gsi_next (&gsi); !gsi_end_p (gsi); )
809 52415 : gsi_remove (&gsi, true);
810 : }
811 : else
812 : {
813 39134 : split_block (bb, stmt);
814 39134 : changed = true;
815 : }
816 : }
817 :
818 : /* If there is an LHS, remove it, but only if its type has fixed size.
819 : The LHS will need to be recreated during RTL expansion and creating
820 : temporaries of variable-sized types is not supported. Also don't
821 : do this with TREE_ADDRESSABLE types, as assign_temp will abort.
822 : Drop LHS regardless of TREE_ADDRESSABLE, if the function call
823 : has been changed into a call that does not return a value, like
824 : __builtin_unreachable or __cxa_pure_virtual. */
825 6317468 : tree lhs = gimple_call_lhs (stmt);
826 6317468 : if (lhs
827 6317468 : && (should_remove_lhs_p (lhs)
828 406 : || VOID_TYPE_P (TREE_TYPE (gimple_call_fntype (stmt)))))
829 : {
830 4128 : gimple_call_set_lhs (stmt, NULL_TREE);
831 :
832 : /* We need to fix up the SSA name to avoid checking errors. */
833 4128 : if (TREE_CODE (lhs) == SSA_NAME)
834 : {
835 3927 : tree new_var = create_tmp_reg (TREE_TYPE (lhs));
836 3927 : SET_SSA_NAME_VAR_OR_IDENTIFIER (lhs, new_var);
837 3927 : SSA_NAME_DEF_STMT (lhs) = gimple_build_nop ();
838 3927 : set_ssa_default_def (cfun, new_var, lhs);
839 : }
840 :
841 4128 : update_stmt (stmt);
842 : }
843 :
844 : /* Mark the call as altering control flow. */
845 6317468 : if (!gimple_call_ctrl_altering_p (stmt))
846 : {
847 86917 : gimple_call_set_ctrl_altering (stmt, true);
848 86917 : changed = true;
849 : }
850 :
851 : return changed;
852 : }
853 :
854 : /* Return true if we want to merge BB1 and BB2 into a single block. */
855 :
856 : static bool
857 406732404 : want_merge_blocks_p (basic_block bb1, basic_block bb2)
858 : {
859 406732404 : if (!can_merge_blocks_p (bb1, bb2))
860 : return false;
861 28051807 : gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb1);
862 28051807 : if (gsi_end_p (gsi) || !stmt_can_terminate_bb_p (gsi_stmt (gsi)))
863 24875476 : return true;
864 3176331 : return bb1->count.ok_for_merging (bb2->count);
865 : }
866 :
867 :
868 : /* Tries to cleanup cfg in basic block BB by merging blocks. Returns
869 : true if anything changes. */
870 :
871 : static bool
872 387502982 : cleanup_tree_cfg_bb (basic_block bb)
873 : {
874 387502982 : if (maybe_remove_forwarder_block (bb))
875 : return true;
876 :
877 : /* If there is a merge opportunity with the predecessor
878 : do nothing now but wait until we process the predecessor.
879 : This happens when we visit BBs in a non-optimal order and
880 : avoids quadratic behavior with adjusting stmts BB pointer. */
881 360122709 : if (single_pred_p (bb)
882 621542504 : && want_merge_blocks_p (single_pred (bb), bb))
883 : /* But make sure we _do_ visit it. When we remove unreachable paths
884 : ending in a backedge we fail to mark the destinations predecessors
885 : as changed. */
886 11483219 : bitmap_set_bit (cfgcleanup_altered_bbs, single_pred (bb)->index);
887 :
888 : /* Merging the blocks may create new opportunities for folding
889 : conditional branches (due to the elimination of single-valued PHI
890 : nodes). */
891 348639490 : else if (single_succ_p (bb)
892 483328316 : && want_merge_blocks_p (bb, single_succ (bb)))
893 : {
894 16568524 : merge_blocks (bb, single_succ (bb));
895 16568524 : return true;
896 : }
897 :
898 : return false;
899 : }
900 :
901 : /* Return true if E is an EDGE_ABNORMAL edge for returns_twice calls,
902 : i.e. one going from .ABNORMAL_DISPATCHER to basic block which doesn't
903 : start with a forced or nonlocal label. Calls which return twice can return
904 : the second time only if they are called normally the first time, so basic
905 : blocks which can be only entered through these abnormal edges but not
906 : normally are effectively unreachable as well. Additionally ignore
907 : __builtin_setjmp_receiver starting blocks, which have one FORCED_LABEL
908 : and which are always only reachable through EDGE_ABNORMAL edge. They are
909 : handled in cleanup_control_flow_pre. */
910 :
911 : static bool
912 342210101 : maybe_dead_abnormal_edge_p (edge e)
913 : {
914 342210101 : if ((e->flags & (EDGE_ABNORMAL | EDGE_EH)) != EDGE_ABNORMAL)
915 : return false;
916 :
917 147448 : gimple_stmt_iterator gsi = gsi_start_nondebug_after_labels_bb (e->src);
918 147448 : gimple *g = gsi_stmt (gsi);
919 147448 : if (!g || !gimple_call_internal_p (g, IFN_ABNORMAL_DISPATCHER))
920 : return false;
921 :
922 19565 : tree target = NULL_TREE;
923 51123 : for (gsi = gsi_start_bb (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
924 31551 : if (glabel *label_stmt = dyn_cast <glabel *> (gsi_stmt (gsi)))
925 : {
926 17904 : tree this_target = gimple_label_label (label_stmt);
927 17904 : if (DECL_NONLOCAL (this_target))
928 : return false;
929 11993 : if (FORCED_LABEL (this_target))
930 : {
931 11993 : if (target)
932 : return false;
933 : target = this_target;
934 : }
935 : }
936 : else
937 : break;
938 :
939 13654 : if (target)
940 : {
941 : /* If there was a single FORCED_LABEL, check for
942 : __builtin_setjmp_receiver with address of that label. */
943 11993 : if (!gsi_end_p (gsi) && is_gimple_debug (gsi_stmt (gsi)))
944 0 : gsi_next_nondebug (&gsi);
945 11993 : if (gsi_end_p (gsi))
946 : return false;
947 11993 : if (!gimple_call_builtin_p (gsi_stmt (gsi), BUILT_IN_SETJMP_RECEIVER))
948 : return false;
949 :
950 11993 : tree arg = gimple_call_arg (gsi_stmt (gsi), 0);
951 11993 : if (TREE_CODE (arg) != ADDR_EXPR || TREE_OPERAND (arg, 0) != target)
952 : return false;
953 : }
954 : return true;
955 : }
956 :
957 : /* If BB is a basic block ending with __builtin_setjmp_setup, return edge
958 : from .ABNORMAL_DISPATCHER basic block to corresponding
959 : __builtin_setjmp_receiver basic block, otherwise return NULL. */
960 : static edge
961 342208416 : builtin_setjmp_setup_bb (basic_block bb)
962 : {
963 342208416 : if (EDGE_COUNT (bb->succs) != 2
964 331643604 : || ((EDGE_SUCC (bb, 0)->flags
965 151807020 : & (EDGE_ABNORMAL | EDGE_EH)) != EDGE_ABNORMAL
966 151711605 : && (EDGE_SUCC (bb, 1)->flags
967 151711605 : & (EDGE_ABNORMAL | EDGE_EH)) != EDGE_ABNORMAL))
968 : return NULL;
969 :
970 167244 : gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
971 167244 : if (gsi_end_p (gsi)
972 167244 : || !gimple_call_builtin_p (gsi_stmt (gsi), BUILT_IN_SETJMP_SETUP))
973 155275 : return NULL;
974 :
975 11969 : tree arg = gimple_call_arg (gsi_stmt (gsi), 1);
976 11969 : if (TREE_CODE (arg) != ADDR_EXPR
977 11969 : || TREE_CODE (TREE_OPERAND (arg, 0)) != LABEL_DECL)
978 : return NULL;
979 :
980 11969 : basic_block recv_bb = label_to_block (cfun, TREE_OPERAND (arg, 0));
981 342208416 : if (EDGE_COUNT (recv_bb->preds) != 1
982 11969 : || (EDGE_PRED (recv_bb, 0)->flags
983 11969 : & (EDGE_ABNORMAL | EDGE_EH)) != EDGE_ABNORMAL
984 23938 : || (EDGE_SUCC (bb, 0)->dest != EDGE_PRED (recv_bb, 0)->src
985 11969 : && EDGE_SUCC (bb, 1)->dest != EDGE_PRED (recv_bb, 0)->src))
986 : return NULL;
987 :
988 : /* EDGE_PRED (recv_bb, 0)->src should be the .ABNORMAL_DISPATCHER bb. */
989 : return EDGE_PRED (recv_bb, 0);
990 : }
991 :
992 : /* Do cleanup_control_flow_bb in PRE order. */
993 :
994 : static bool
995 24949199 : cleanup_control_flow_pre ()
996 : {
997 24949199 : bool retval = false;
998 :
999 : /* We want remove_edge_and_dominated_blocks to only remove edges,
1000 : not dominated blocks which it does when dom info isn't available.
1001 : Pretend so. */
1002 24949199 : dom_state saved_state = dom_info_state (CDI_DOMINATORS);
1003 24949199 : set_dom_info_availability (CDI_DOMINATORS, DOM_NONE);
1004 :
1005 24949199 : auto_vec<edge_iterator, 20> stack (n_basic_blocks_for_fn (cfun) + 2);
1006 24949199 : auto_sbitmap visited (last_basic_block_for_fn (cfun));
1007 24949199 : bitmap_clear (visited);
1008 :
1009 24949199 : vec<edge, va_gc> *setjmp_vec = NULL;
1010 24949199 : auto_vec<basic_block, 4> abnormal_dispatchers;
1011 :
1012 24949199 : stack.quick_push (ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs));
1013 :
1014 866587211 : while (! stack.is_empty ())
1015 : {
1016 : /* Look at the edge on the top of the stack. */
1017 841638012 : edge_iterator ei = stack.last ();
1018 841638012 : basic_block dest = ei_edge (ei)->dest;
1019 :
1020 841638012 : if (dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
1021 817077509 : && !bitmap_bit_p (visited, dest->index)
1022 1183860082 : && (ei_container (ei) == setjmp_vec
1023 342210101 : || !maybe_dead_abnormal_edge_p (ei_edge (ei))))
1024 : {
1025 342208416 : bitmap_set_bit (visited, dest->index);
1026 : /* We only possibly remove edges from DEST here, leaving
1027 : possibly unreachable code in the IL. */
1028 342208416 : retval |= cleanup_control_flow_bb (dest);
1029 :
1030 : /* Check for __builtin_setjmp_setup. Edges from .ABNORMAL_DISPATCH
1031 : to __builtin_setjmp_receiver will be normally ignored by
1032 : maybe_dead_abnormal_edge_p. If DEST is a visited
1033 : __builtin_setjmp_setup, queue edge from .ABNORMAL_DISPATCH
1034 : to __builtin_setjmp_receiver, so that it will be visited too. */
1035 342208416 : if (edge e = builtin_setjmp_setup_bb (dest))
1036 : {
1037 11969 : vec_safe_push (setjmp_vec, e);
1038 11969 : if (vec_safe_length (setjmp_vec) == 1)
1039 6318 : stack.quick_push (ei_start (setjmp_vec));
1040 : }
1041 :
1042 342208416 : if ((ei_edge (ei)->flags
1043 342208416 : & (EDGE_ABNORMAL | EDGE_EH)) == EDGE_ABNORMAL)
1044 : {
1045 145763 : gimple_stmt_iterator gsi
1046 145763 : = gsi_start_nondebug_after_labels_bb (dest);
1047 145763 : gimple *g = gsi_stmt (gsi);
1048 145763 : if (g && gimple_call_internal_p (g, IFN_ABNORMAL_DISPATCHER))
1049 25446 : abnormal_dispatchers.safe_push (dest);
1050 : }
1051 :
1052 1183846428 : if (EDGE_COUNT (dest->succs) > 0)
1053 319848713 : stack.quick_push (ei_start (dest->succs));
1054 : }
1055 : else
1056 : {
1057 499429596 : if (!ei_one_before_end_p (ei))
1058 154625366 : ei_next (&stack.last ());
1059 : else
1060 : {
1061 344804230 : if (ei_container (ei) == setjmp_vec)
1062 6318 : vec_safe_truncate (setjmp_vec, 0);
1063 344804230 : stack.pop ();
1064 : }
1065 : }
1066 : }
1067 :
1068 24949199 : vec_free (setjmp_vec);
1069 :
1070 : /* If we've marked .ABNORMAL_DISPATCHER basic block(s) as visited
1071 : above, but haven't marked any of their successors as visited,
1072 : unmark them now, so that they can be removed as useless. */
1073 74873043 : for (basic_block dispatcher_bb : abnormal_dispatchers)
1074 : {
1075 25446 : edge e;
1076 25446 : edge_iterator ei;
1077 25537 : FOR_EACH_EDGE (e, ei, dispatcher_bb->succs)
1078 25446 : if (bitmap_bit_p (visited, e->dest->index))
1079 : break;
1080 25446 : if (e == NULL)
1081 91 : bitmap_clear_bit (visited, dispatcher_bb->index);
1082 : }
1083 :
1084 24949199 : set_dom_info_availability (CDI_DOMINATORS, saved_state);
1085 :
1086 : /* We are deleting BBs in non-reverse dominator order, make sure
1087 : insert_debug_temps_for_defs is prepared for that. */
1088 24949199 : if (retval)
1089 864392 : free_dominance_info (CDI_DOMINATORS);
1090 :
1091 : /* Remove all now (and previously) unreachable blocks. */
1092 390626745 : for (int i = NUM_FIXED_BLOCKS; i < last_basic_block_for_fn (cfun); ++i)
1093 : {
1094 365677546 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
1095 365677546 : if (bb && !bitmap_bit_p (visited, bb->index))
1096 : {
1097 4714831 : if (!retval)
1098 745240 : free_dominance_info (CDI_DOMINATORS);
1099 4714831 : delete_basic_block (bb);
1100 4714831 : retval = true;
1101 : }
1102 : }
1103 :
1104 24949199 : return retval;
1105 24949199 : }
1106 :
1107 : /* Callback function for make_forwarder_block which returns
1108 : true when E is not a latch. */
1109 :
1110 : static bool
1111 151191 : mfb_keep_latches (edge e, void*)
1112 : {
1113 151191 : return !((dom_info_available_p (CDI_DOMINATORS)
1114 23551 : && dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
1115 143878 : || (e->flags & EDGE_DFS_BACK));
1116 : }
1117 :
1118 : /* Remove unreachable blocks and other miscellaneous clean up work.
1119 : Return true if the flowgraph was modified, false otherwise. */
1120 :
1121 : static bool
1122 24949199 : cleanup_tree_cfg_noloop (unsigned ssa_update_flags)
1123 : {
1124 24949199 : timevar_push (TV_TREE_CLEANUP_CFG);
1125 :
1126 : /* Ensure that we have single entries into loop headers. Otherwise
1127 : if one of the entries is becoming a latch due to CFG cleanup
1128 : (from formerly being part of an irreducible region) then we mess
1129 : up loop fixup and associate the old loop with a different region
1130 : which makes niter upper bounds invalid. See for example PR80549.
1131 : This needs to be done before we remove trivially dead edges as
1132 : we need to capture the dominance state before the pending transform. */
1133 24949199 : if (current_loops)
1134 : {
1135 : /* This needs backedges or dominators. */
1136 22096596 : if (!dom_info_available_p (CDI_DOMINATORS))
1137 6686294 : mark_dfs_back_edges ();
1138 :
1139 92112010 : for (loop_p loop : *get_loops (cfun))
1140 47918818 : if (loop && loop->header)
1141 : {
1142 40837241 : basic_block bb = loop->header;
1143 40837241 : edge_iterator ei;
1144 40837241 : edge e;
1145 40837241 : bool found_latch = false;
1146 40837241 : bool any_abnormal = false;
1147 40837241 : unsigned n = 0;
1148 : /* We are only interested in preserving existing loops, but
1149 : we need to check whether they are still real and of course
1150 : if we need to add a preheader at all. */
1151 78473251 : FOR_EACH_EDGE (e, ei, bb->preds)
1152 : {
1153 37636010 : if (e->flags & EDGE_ABNORMAL)
1154 : {
1155 : any_abnormal = true;
1156 : break;
1157 : }
1158 37636010 : if ((dom_info_available_p (CDI_DOMINATORS)
1159 27476941 : && dominated_by_p (CDI_DOMINATORS, e->src, bb))
1160 51359687 : || (e->flags & EDGE_DFS_BACK))
1161 : {
1162 18840354 : found_latch = true;
1163 18840354 : continue;
1164 : }
1165 18795656 : n++;
1166 : }
1167 : /* If we have more than one entry to the loop header
1168 : create a forwarder. */
1169 40837241 : if (found_latch && ! any_abnormal && n > 1)
1170 : {
1171 46748 : edge fallthru = make_forwarder_block (bb, mfb_keep_latches, NULL);
1172 46748 : loop->header = fallthru->dest;
1173 46748 : if (! loops_state_satisfies_p (LOOPS_NEED_FIXUP))
1174 : {
1175 : /* The loop updating from the CFG hook is incomplete
1176 : when we have multiple latches, fixup manually. */
1177 26455 : remove_bb_from_loops (fallthru->src);
1178 26455 : loop_p cloop = loop;
1179 83083 : FOR_EACH_EDGE (e, ei, fallthru->src->preds)
1180 56628 : cloop = find_common_loop (cloop, e->src->loop_father);
1181 26455 : add_bb_to_loop (fallthru->src, cloop);
1182 : }
1183 : }
1184 : }
1185 : }
1186 :
1187 : /* Prepare the worklists of altered blocks. */
1188 24949199 : cfgcleanup_altered_bbs = BITMAP_ALLOC (NULL);
1189 :
1190 : /* Start by iterating over all basic blocks in PRE order looking for
1191 : edge removal opportunities. Do this first because incoming SSA form
1192 : may be invalid and we want to avoid performing SSA related tasks such
1193 : as propgating out a PHI node during BB merging in that state. This
1194 : also gets rid of unreachable blocks. */
1195 24949199 : bool changed = cleanup_control_flow_pre ();
1196 :
1197 : /* After doing the above SSA form should be valid (or an update SSA
1198 : should be required). */
1199 24949199 : if (ssa_update_flags)
1200 : {
1201 16343054 : timevar_pop (TV_TREE_CLEANUP_CFG);
1202 16343054 : update_ssa (ssa_update_flags);
1203 16343054 : timevar_push (TV_TREE_CLEANUP_CFG);
1204 : }
1205 :
1206 : /* Compute dominator info which we need for the iterative process below.
1207 : Avoid computing the fast query DFS numbers since any block merging
1208 : done will invalidate them anyway. */
1209 24949199 : if (!dom_info_available_p (CDI_DOMINATORS))
1210 8445260 : calculate_dominance_info (CDI_DOMINATORS, false);
1211 : else
1212 16503939 : checking_verify_dominators (CDI_DOMINATORS);
1213 :
1214 : /* During forwarder block cleanup, we may redirect edges out of
1215 : SWITCH_EXPRs, which can get expensive. So we want to enable
1216 : recording of edge to CASE_LABEL_EXPR. */
1217 24949199 : start_recording_case_labels ();
1218 :
1219 : /* Continue by iterating over all basic blocks looking for BB merging
1220 : opportunities. We cannot use FOR_EACH_BB_FN for the BB iteration
1221 : since the basic blocks may get removed. */
1222 24949199 : unsigned n = last_basic_block_for_fn (cfun);
1223 390626745 : for (unsigned i = NUM_FIXED_BLOCKS; i < n; i++)
1224 : {
1225 365677546 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
1226 365677546 : if (bb)
1227 334985439 : changed |= cleanup_tree_cfg_bb (bb);
1228 : }
1229 :
1230 : /* Now process the altered blocks, as long as any are available. */
1231 85569954 : while (!bitmap_empty_p (cfgcleanup_altered_bbs))
1232 : {
1233 60620755 : unsigned i = bitmap_clear_first_set_bit (cfgcleanup_altered_bbs);
1234 60620755 : if (i < NUM_FIXED_BLOCKS)
1235 0 : continue;
1236 :
1237 60620755 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
1238 60620755 : if (!bb)
1239 8103212 : continue;
1240 :
1241 : /* BB merging done by cleanup_tree_cfg_bb can end up propagating
1242 : out single-argument PHIs which in turn can expose
1243 : cleanup_control_flow_bb opportunities so we have to repeat
1244 : that here. */
1245 52517543 : changed |= cleanup_control_flow_bb (bb);
1246 52517543 : changed |= cleanup_tree_cfg_bb (bb);
1247 : }
1248 :
1249 24949199 : end_recording_case_labels ();
1250 24949199 : BITMAP_FREE (cfgcleanup_altered_bbs);
1251 :
1252 24949199 : gcc_assert (dom_info_available_p (CDI_DOMINATORS));
1253 :
1254 : /* Do not renumber blocks if the SCEV cache is active, it is indexed by
1255 : basic-block numbers. */
1256 24949199 : if (! scev_initialized_p ())
1257 24644124 : compact_blocks ();
1258 :
1259 24949199 : checking_verify_flow_info ();
1260 :
1261 24949199 : timevar_pop (TV_TREE_CLEANUP_CFG);
1262 :
1263 24949199 : if (changed && current_loops)
1264 : {
1265 : /* Removing edges and/or blocks may make recorded bounds refer
1266 : to stale GIMPLE stmts now, so clear them. */
1267 5966526 : free_numbers_of_iterations_estimates (cfun);
1268 5966526 : loops_state_set (LOOPS_NEED_FIXUP);
1269 : }
1270 :
1271 24949199 : return changed;
1272 : }
1273 :
1274 : /* Repairs loop structures. */
1275 :
1276 : static void
1277 7618878 : repair_loop_structures (void)
1278 : {
1279 7618878 : bitmap changed_bbs;
1280 7618878 : unsigned n_new_or_deleted_loops;
1281 :
1282 7618878 : calculate_dominance_info (CDI_DOMINATORS);
1283 :
1284 7618878 : timevar_push (TV_REPAIR_LOOPS);
1285 7618878 : changed_bbs = BITMAP_ALLOC (NULL);
1286 7618878 : n_new_or_deleted_loops = fix_loop_structure (changed_bbs);
1287 :
1288 : /* This usually does nothing. But sometimes parts of cfg that originally
1289 : were inside a loop get out of it due to edge removal (since they
1290 : become unreachable by back edges from latch). Also a former
1291 : irreducible loop can become reducible - in this case force a full
1292 : rewrite into loop-closed SSA form. */
1293 7618878 : if (loops_state_satisfies_p (LOOP_CLOSED_SSA)
1294 7618878 : && (!bitmap_empty_p (changed_bbs) || n_new_or_deleted_loops))
1295 25285 : rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1296 :
1297 7618878 : BITMAP_FREE (changed_bbs);
1298 :
1299 7618878 : checking_verify_loop_structure ();
1300 7618878 : scev_reset ();
1301 :
1302 7618878 : timevar_pop (TV_REPAIR_LOOPS);
1303 7618878 : }
1304 :
1305 : /* Cleanup cfg and repair loop structures. */
1306 :
1307 : bool
1308 24949199 : cleanup_tree_cfg (unsigned ssa_update_flags)
1309 : {
1310 24949199 : bool changed = cleanup_tree_cfg_noloop (ssa_update_flags);
1311 :
1312 24949199 : if (current_loops != NULL
1313 24949199 : && loops_state_satisfies_p (LOOPS_NEED_FIXUP))
1314 7618878 : repair_loop_structures ();
1315 :
1316 24949199 : return changed;
1317 : }
1318 :
1319 : /* This pass merges PHI nodes if one feeds into another. For example,
1320 : suppose we have the following:
1321 :
1322 : goto <bb 9> (<L9>);
1323 :
1324 : <L8>:;
1325 : tem_17 = foo ();
1326 :
1327 : # tem_6 = PHI <tem_17(8), tem_23(7)>;
1328 : <L9>:;
1329 :
1330 : # tem_3 = PHI <tem_6(9), tem_2(5)>;
1331 : <L10>:;
1332 :
1333 : Then we merge the first PHI node into the second one like so:
1334 :
1335 : goto <bb 9> (<L10>);
1336 :
1337 : <L8>:;
1338 : tem_17 = foo ();
1339 :
1340 : # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
1341 : <L10>:;
1342 : */
1343 :
1344 : namespace {
1345 :
1346 : const pass_data pass_data_merge_phi =
1347 : {
1348 : GIMPLE_PASS, /* type */
1349 : "mergephi", /* name */
1350 : OPTGROUP_NONE, /* optinfo_flags */
1351 : TV_TREE_MERGE_PHI, /* tv_id */
1352 : ( PROP_cfg | PROP_ssa ), /* properties_required */
1353 : 0, /* properties_provided */
1354 : 0, /* properties_destroyed */
1355 : 0, /* todo_flags_start */
1356 : 0, /* todo_flags_finish */
1357 : };
1358 :
1359 : class pass_merge_phi : public gimple_opt_pass
1360 : {
1361 : public:
1362 861972 : pass_merge_phi (gcc::context *ctxt)
1363 1723944 : : gimple_opt_pass (pass_data_merge_phi, ctxt)
1364 : {}
1365 :
1366 : /* opt_pass methods: */
1367 574648 : opt_pass * clone () final override { return new pass_merge_phi (m_ctxt); }
1368 : unsigned int execute (function *) final override;
1369 :
1370 : }; // class pass_merge_phi
1371 :
1372 : unsigned int
1373 4464692 : pass_merge_phi::execute (function *fun)
1374 : {
1375 4464692 : int forwarder_removed = 0;
1376 4464692 : calculate_dominance_info (CDI_DOMINATORS);
1377 :
1378 : /* Find all PHI nodes that we may be able to merge. */
1379 4464692 : unsigned n = last_basic_block_for_fn (fun);
1380 37727372 : for (unsigned i = NUM_FIXED_BLOCKS; i < n; i++)
1381 : {
1382 33262680 : basic_block bb = BASIC_BLOCK_FOR_FN (fun, i);
1383 33262680 : if (!bb)
1384 71497 : continue;
1385 :
1386 : /* Look for a forwarder block with PHI nodes. */
1387 33191183 : if (maybe_remove_forwarder_block (bb, true))
1388 202501 : forwarder_removed++;
1389 : }
1390 :
1391 : /* Removing forwarder blocks can cause formerly irreducible loops
1392 : to become reducible if we merged two entry blocks. */
1393 4464692 : if (forwarder_removed != 0
1394 86763 : && current_loops)
1395 86763 : loops_state_set (LOOPS_NEED_FIXUP);
1396 :
1397 4464692 : statistics_counter_event (fun, "Forwarder blocks removed",
1398 : forwarder_removed);
1399 4464692 : return 0;
1400 : }
1401 :
1402 : } // anon namespace
1403 :
1404 : gimple_opt_pass *
1405 287324 : make_pass_merge_phi (gcc::context *ctxt)
1406 : {
1407 287324 : return new pass_merge_phi (ctxt);
1408 : }
1409 :
1410 : /* Pass: cleanup the CFG just before expanding trees to RTL.
1411 : This is just a round of label cleanups and case node grouping
1412 : because after the tree optimizers have run such cleanups may
1413 : be necessary. */
1414 :
1415 : static unsigned int
1416 1469626 : execute_cleanup_cfg_post_optimizing (void)
1417 : {
1418 1469626 : unsigned int todo = execute_fixup_cfg ();
1419 1469626 : if (cleanup_tree_cfg ())
1420 393607 : todo |= TODO_update_ssa;
1421 1469626 : maybe_remove_unreachable_handlers ();
1422 1469626 : cleanup_dead_labels ();
1423 1469626 : if (group_case_labels () && cleanup_tree_cfg ())
1424 0 : todo |= TODO_update_ssa;
1425 :
1426 : /* When optimizing undo the merging of forwarder blocks
1427 : that phis for better out of ssa expansion. */
1428 1469626 : if (optimize)
1429 1038138 : make_forwarders_with_degenerate_phis (cfun, true);
1430 :
1431 : /* Make sure todo does not have cleanup cfg as we don't want
1432 : remove the forwarder blocks we just created. cleanup cfg
1433 : has already happened. */
1434 1469626 : todo &= ~TODO_cleanup_cfg;
1435 :
1436 1469626 : basic_block bb = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
1437 1469626 : gimple_stmt_iterator gsi = gsi_start_nondebug_after_labels_bb (bb);
1438 : /* If the first (and only) bb and the only non debug
1439 : statement is __builtin_unreachable call, then replace it with a trap
1440 : so the function is at least one instruction in size. */
1441 1469626 : if (!gsi_end_p (gsi)
1442 1469626 : && gimple_call_builtin_p (gsi_stmt (gsi), BUILT_IN_UNREACHABLE))
1443 : {
1444 348 : if (targetm.have_trap ())
1445 : {
1446 696 : gimple_call_set_fndecl (gsi_stmt (gsi), builtin_decl_implicit (BUILT_IN_UNREACHABLE_TRAP));
1447 348 : update_stmt (gsi_stmt (gsi));
1448 : }
1449 : /* If the target does not have a trap, convert it into an infinite loop. */
1450 : else
1451 : {
1452 0 : gsi_remove (&gsi, true);
1453 0 : make_single_succ_edge (bb, bb, EDGE_FALLTHRU);
1454 0 : fix_loop_structure (NULL);
1455 : }
1456 : }
1457 :
1458 1469626 : if ((flag_compare_debug_opt || flag_compare_debug)
1459 3912 : && flag_dump_final_insns)
1460 : {
1461 3912 : FILE *final_output = fopen (flag_dump_final_insns, "a");
1462 :
1463 3912 : if (!final_output)
1464 : {
1465 0 : error ("could not open final insn dump file %qs: %m",
1466 : flag_dump_final_insns);
1467 0 : flag_dump_final_insns = NULL;
1468 : }
1469 : else
1470 : {
1471 3912 : int save_unnumbered = flag_dump_unnumbered;
1472 3912 : int save_noaddr = flag_dump_noaddr;
1473 :
1474 3912 : flag_dump_noaddr = flag_dump_unnumbered = 1;
1475 3912 : fprintf (final_output, "\n");
1476 3912 : dump_enumerated_decls (final_output,
1477 : dump_flags | TDF_SLIM | TDF_NOUID);
1478 3912 : flag_dump_noaddr = save_noaddr;
1479 3912 : flag_dump_unnumbered = save_unnumbered;
1480 3912 : if (fclose (final_output))
1481 : {
1482 0 : error ("could not close final insn dump file %qs: %m",
1483 : flag_dump_final_insns);
1484 0 : flag_dump_final_insns = NULL;
1485 : }
1486 : }
1487 : }
1488 1469626 : return todo;
1489 : }
1490 :
1491 : namespace {
1492 :
1493 : const pass_data pass_data_cleanup_cfg_post_optimizing =
1494 : {
1495 : GIMPLE_PASS, /* type */
1496 : "optimized", /* name */
1497 : OPTGROUP_NONE, /* optinfo_flags */
1498 : TV_TREE_CLEANUP_CFG, /* tv_id */
1499 : PROP_cfg, /* properties_required */
1500 : 0, /* properties_provided */
1501 : 0, /* properties_destroyed */
1502 : 0, /* todo_flags_start */
1503 : TODO_remove_unused_locals, /* todo_flags_finish */
1504 : };
1505 :
1506 : class pass_cleanup_cfg_post_optimizing : public gimple_opt_pass
1507 : {
1508 : public:
1509 287324 : pass_cleanup_cfg_post_optimizing (gcc::context *ctxt)
1510 574648 : : gimple_opt_pass (pass_data_cleanup_cfg_post_optimizing, ctxt)
1511 : {}
1512 :
1513 : /* opt_pass methods: */
1514 1469626 : unsigned int execute (function *) final override
1515 : {
1516 1469626 : return execute_cleanup_cfg_post_optimizing ();
1517 : }
1518 :
1519 : }; // class pass_cleanup_cfg_post_optimizing
1520 :
1521 : } // anon namespace
1522 :
1523 : gimple_opt_pass *
1524 287324 : make_pass_cleanup_cfg_post_optimizing (gcc::context *ctxt)
1525 : {
1526 287324 : return new pass_cleanup_cfg_post_optimizing (ctxt);
1527 : }
1528 :
1529 :
1530 : /* Delete all unreachable basic blocks and update callgraph.
1531 : Doing so is somewhat nontrivial because we need to update all clones and
1532 : remove inline function that become unreachable. */
1533 :
1534 : bool
1535 1549270 : delete_unreachable_blocks_update_callgraph (cgraph_node *dst_node,
1536 : bool update_clones)
1537 : {
1538 1549270 : bool changed = false;
1539 1549270 : basic_block b, next_bb;
1540 :
1541 1549270 : find_unreachable_blocks ();
1542 :
1543 : /* Delete all unreachable basic blocks. */
1544 :
1545 1549270 : for (b = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; b
1546 29796593 : != EXIT_BLOCK_PTR_FOR_FN (cfun); b = next_bb)
1547 : {
1548 28247323 : next_bb = b->next_bb;
1549 :
1550 28247323 : if (!(b->flags & BB_REACHABLE))
1551 : {
1552 37738 : gimple_stmt_iterator bsi;
1553 :
1554 146548 : for (bsi = gsi_start_bb (b); !gsi_end_p (bsi); gsi_next (&bsi))
1555 : {
1556 71072 : struct cgraph_edge *e;
1557 71072 : struct cgraph_node *node;
1558 :
1559 71072 : dst_node->remove_stmt_references (gsi_stmt (bsi));
1560 :
1561 71072 : if (gimple_code (gsi_stmt (bsi)) == GIMPLE_CALL
1562 71072 : &&(e = dst_node->get_edge (gsi_stmt (bsi))) != NULL)
1563 : {
1564 892 : if (!e->inline_failed)
1565 0 : e->callee->remove_symbol_and_inline_clones (dst_node);
1566 : else
1567 892 : cgraph_edge::remove (e);
1568 : }
1569 71072 : if (update_clones && dst_node->clones)
1570 0 : for (node = dst_node->clones; node != dst_node;)
1571 : {
1572 0 : node->remove_stmt_references (gsi_stmt (bsi));
1573 0 : if (gimple_code (gsi_stmt (bsi)) == GIMPLE_CALL
1574 0 : && (e = node->get_edge (gsi_stmt (bsi))) != NULL)
1575 : {
1576 0 : if (!e->inline_failed)
1577 0 : e->callee->remove_symbol_and_inline_clones (dst_node);
1578 : else
1579 0 : cgraph_edge::remove (e);
1580 : }
1581 :
1582 0 : if (node->clones)
1583 : node = node->clones;
1584 0 : else if (node->next_sibling_clone)
1585 : node = node->next_sibling_clone;
1586 : else
1587 : {
1588 0 : while (node != dst_node && !node->next_sibling_clone)
1589 0 : node = node->clone_of;
1590 0 : if (node != dst_node)
1591 0 : node = node->next_sibling_clone;
1592 : }
1593 : }
1594 : }
1595 37738 : delete_basic_block (b);
1596 37738 : changed = true;
1597 : }
1598 : }
1599 :
1600 1549270 : return changed;
1601 : }
1602 :
|
