LWG 2975 ensure construct(pair<T,U>*, ...) used to construct pairs
[official-gcc.git] / gcc / tree-cfgcleanup.c
blobd5464fdc4e4abc18998ecb4d49d23054ab1ccf93
1 /* CFG cleanup for trees.
2 Copyright (C) 2001-2018 Free Software Foundation, Inc.
4 This file is part of GCC.
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.
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.
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/>. */
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"
48 /* The set of blocks in that at least one of the following changes happened:
49 -- the statement at the end of the block was changed
50 -- the block was newly created
51 -- the set of the predecessors of the block changed
52 -- the set of the successors of the block changed
53 ??? Maybe we could track these changes separately, since they determine
54 what cleanups it makes sense to try on the block. */
55 bitmap cfgcleanup_altered_bbs;
57 /* Remove any fallthru edge from EV. Return true if an edge was removed. */
59 static bool
60 remove_fallthru_edge (vec<edge, va_gc> *ev)
62 edge_iterator ei;
63 edge e;
65 FOR_EACH_EDGE (e, ei, ev)
66 if ((e->flags & EDGE_FALLTHRU) != 0)
68 if (e->flags & EDGE_COMPLEX)
69 e->flags &= ~EDGE_FALLTHRU;
70 else
71 remove_edge_and_dominated_blocks (e);
72 return true;
74 return false;
77 /* Convert a SWTCH with single non-default case to gcond and replace it
78 at GSI. */
80 static bool
81 convert_single_case_switch (gswitch *swtch, gimple_stmt_iterator &gsi)
83 if (gimple_switch_num_labels (swtch) != 2)
84 return false;
86 tree index = gimple_switch_index (swtch);
87 tree default_label = CASE_LABEL (gimple_switch_default_label (swtch));
88 tree label = gimple_switch_label (swtch, 1);
89 tree low = CASE_LOW (label);
90 tree high = CASE_HIGH (label);
92 basic_block default_bb = label_to_block_fn (cfun, default_label);
93 basic_block case_bb = label_to_block_fn (cfun, CASE_LABEL (label));
95 basic_block bb = gimple_bb (swtch);
96 gcond *cond;
98 /* Replace switch statement with condition statement. */
99 if (high)
101 tree lhs, rhs;
102 generate_range_test (bb, index, low, high, &lhs, &rhs);
103 cond = gimple_build_cond (LE_EXPR, lhs, rhs, NULL_TREE, NULL_TREE);
105 else
106 cond = gimple_build_cond (EQ_EXPR, index,
107 fold_convert (TREE_TYPE (index), low),
108 NULL_TREE, NULL_TREE);
110 gsi_replace (&gsi, cond, true);
112 /* Update edges. */
113 edge case_edge = find_edge (bb, case_bb);
114 edge default_edge = find_edge (bb, default_bb);
116 case_edge->flags |= EDGE_TRUE_VALUE;
117 default_edge->flags |= EDGE_FALSE_VALUE;
118 return true;
121 /* Disconnect an unreachable block in the control expression starting
122 at block BB. */
124 static bool
125 cleanup_control_expr_graph (basic_block bb, gimple_stmt_iterator gsi)
127 edge taken_edge;
128 bool retval = false;
129 gimple *stmt = gsi_stmt (gsi);
131 if (!single_succ_p (bb))
133 edge e;
134 edge_iterator ei;
135 bool warned;
136 tree val = NULL_TREE;
138 /* Try to convert a switch with just a single non-default case to
139 GIMPLE condition. */
140 if (gimple_code (stmt) == GIMPLE_SWITCH
141 && convert_single_case_switch (as_a<gswitch *> (stmt), gsi))
142 stmt = gsi_stmt (gsi);
144 fold_defer_overflow_warnings ();
145 switch (gimple_code (stmt))
147 case GIMPLE_COND:
149 gimple_match_op res_op;
150 if (gimple_simplify (stmt, &res_op, NULL, no_follow_ssa_edges,
151 no_follow_ssa_edges)
152 && res_op.code == INTEGER_CST)
153 val = res_op.ops[0];
155 break;
157 case GIMPLE_SWITCH:
158 val = gimple_switch_index (as_a <gswitch *> (stmt));
159 break;
161 default:
164 taken_edge = find_taken_edge (bb, val);
165 if (!taken_edge)
167 fold_undefer_and_ignore_overflow_warnings ();
168 return false;
171 /* Remove all the edges except the one that is always executed. */
172 warned = false;
173 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
175 if (e != taken_edge)
177 if (!warned)
179 fold_undefer_overflow_warnings
180 (true, stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
181 warned = true;
184 taken_edge->probability += e->probability;
185 remove_edge_and_dominated_blocks (e);
186 retval = true;
188 else
189 ei_next (&ei);
191 if (!warned)
192 fold_undefer_and_ignore_overflow_warnings ();
194 else
195 taken_edge = single_succ_edge (bb);
197 bitmap_set_bit (cfgcleanup_altered_bbs, bb->index);
198 gsi_remove (&gsi, true);
199 taken_edge->flags = EDGE_FALLTHRU;
201 return retval;
204 /* Cleanup the GF_CALL_CTRL_ALTERING flag according to
205 to updated gimple_call_flags. */
207 static void
208 cleanup_call_ctrl_altering_flag (gimple *bb_end)
210 if (!is_gimple_call (bb_end)
211 || !gimple_call_ctrl_altering_p (bb_end))
212 return;
214 int flags = gimple_call_flags (bb_end);
215 if (((flags & (ECF_CONST | ECF_PURE))
216 && !(flags & ECF_LOOPING_CONST_OR_PURE))
217 || (flags & ECF_LEAF))
218 gimple_call_set_ctrl_altering (bb_end, false);
221 /* Try to remove superfluous control structures in basic block BB. Returns
222 true if anything changes. */
224 static bool
225 cleanup_control_flow_bb (basic_block bb)
227 gimple_stmt_iterator gsi;
228 bool retval = false;
229 gimple *stmt;
231 /* If the last statement of the block could throw and now cannot,
232 we need to prune cfg. */
233 retval |= gimple_purge_dead_eh_edges (bb);
235 gsi = gsi_last_nondebug_bb (bb);
236 if (gsi_end_p (gsi))
237 return retval;
239 stmt = gsi_stmt (gsi);
241 /* Try to cleanup ctrl altering flag for call which ends bb. */
242 cleanup_call_ctrl_altering_flag (stmt);
244 if (gimple_code (stmt) == GIMPLE_COND
245 || gimple_code (stmt) == GIMPLE_SWITCH)
247 gcc_checking_assert (gsi_stmt (gsi_last_bb (bb)) == stmt);
248 retval |= cleanup_control_expr_graph (bb, gsi);
250 else if (gimple_code (stmt) == GIMPLE_GOTO
251 && TREE_CODE (gimple_goto_dest (stmt)) == ADDR_EXPR
252 && (TREE_CODE (TREE_OPERAND (gimple_goto_dest (stmt), 0))
253 == LABEL_DECL))
255 /* If we had a computed goto which has a compile-time determinable
256 destination, then we can eliminate the goto. */
257 edge e;
258 tree label;
259 edge_iterator ei;
260 basic_block target_block;
262 gcc_checking_assert (gsi_stmt (gsi_last_bb (bb)) == stmt);
263 /* First look at all the outgoing edges. Delete any outgoing
264 edges which do not go to the right block. For the one
265 edge which goes to the right block, fix up its flags. */
266 label = TREE_OPERAND (gimple_goto_dest (stmt), 0);
267 if (DECL_CONTEXT (label) != cfun->decl)
268 return retval;
269 target_block = label_to_block (label);
270 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
272 if (e->dest != target_block)
273 remove_edge_and_dominated_blocks (e);
274 else
276 /* Turn off the EDGE_ABNORMAL flag. */
277 e->flags &= ~EDGE_ABNORMAL;
279 /* And set EDGE_FALLTHRU. */
280 e->flags |= EDGE_FALLTHRU;
281 ei_next (&ei);
285 bitmap_set_bit (cfgcleanup_altered_bbs, bb->index);
286 bitmap_set_bit (cfgcleanup_altered_bbs, target_block->index);
288 /* Remove the GOTO_EXPR as it is not needed. The CFG has all the
289 relevant information we need. */
290 gsi_remove (&gsi, true);
291 retval = true;
294 /* Check for indirect calls that have been turned into
295 noreturn calls. */
296 else if (is_gimple_call (stmt)
297 && gimple_call_noreturn_p (stmt))
299 /* If there are debug stmts after the noreturn call, remove them
300 now, they should be all unreachable anyway. */
301 for (gsi_next (&gsi); !gsi_end_p (gsi); )
302 gsi_remove (&gsi, true);
303 if (remove_fallthru_edge (bb->succs))
304 retval = true;
307 return retval;
310 /* Return true if basic block BB does nothing except pass control
311 flow to another block and that we can safely insert a label at
312 the start of the successor block.
314 As a precondition, we require that BB be not equal to
315 the entry block. */
317 static bool
318 tree_forwarder_block_p (basic_block bb, bool phi_wanted)
320 gimple_stmt_iterator gsi;
321 location_t locus;
323 /* BB must have a single outgoing edge. */
324 if (single_succ_p (bb) != 1
325 /* If PHI_WANTED is false, BB must not have any PHI nodes.
326 Otherwise, BB must have PHI nodes. */
327 || gimple_seq_empty_p (phi_nodes (bb)) == phi_wanted
328 /* BB may not be a predecessor of the exit block. */
329 || single_succ (bb) == EXIT_BLOCK_PTR_FOR_FN (cfun)
330 /* Nor should this be an infinite loop. */
331 || single_succ (bb) == bb
332 /* BB may not have an abnormal outgoing edge. */
333 || (single_succ_edge (bb)->flags & EDGE_ABNORMAL))
334 return false;
336 gcc_checking_assert (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun));
338 locus = single_succ_edge (bb)->goto_locus;
340 /* There should not be an edge coming from entry, or an EH edge. */
342 edge_iterator ei;
343 edge e;
345 FOR_EACH_EDGE (e, ei, bb->preds)
346 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun) || (e->flags & EDGE_EH))
347 return false;
348 /* If goto_locus of any of the edges differs, prevent removing
349 the forwarder block for -O0. */
350 else if (optimize == 0 && e->goto_locus != locus)
351 return false;
354 /* Now walk through the statements backward. We can ignore labels,
355 anything else means this is not a forwarder block. */
356 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
358 gimple *stmt = gsi_stmt (gsi);
360 switch (gimple_code (stmt))
362 case GIMPLE_LABEL:
363 if (DECL_NONLOCAL (gimple_label_label (as_a <glabel *> (stmt))))
364 return false;
365 if (optimize == 0 && gimple_location (stmt) != locus)
366 return false;
367 break;
369 /* ??? For now, hope there's a corresponding debug
370 assignment at the destination. */
371 case GIMPLE_DEBUG:
372 break;
374 default:
375 return false;
379 if (current_loops)
381 basic_block dest;
382 /* Protect loop headers. */
383 if (bb_loop_header_p (bb))
384 return false;
386 dest = EDGE_SUCC (bb, 0)->dest;
387 /* Protect loop preheaders and latches if requested. */
388 if (dest->loop_father->header == dest)
390 if (bb->loop_father == dest->loop_father)
392 if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES))
393 return false;
394 /* If bb doesn't have a single predecessor we'd make this
395 loop have multiple latches. Don't do that if that
396 would in turn require disambiguating them. */
397 return (single_pred_p (bb)
398 || loops_state_satisfies_p
399 (LOOPS_MAY_HAVE_MULTIPLE_LATCHES));
401 else if (bb->loop_father == loop_outer (dest->loop_father))
402 return !loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS);
403 /* Always preserve other edges into loop headers that are
404 not simple latches or preheaders. */
405 return false;
409 return true;
412 /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
413 those alternatives are equal in each of the PHI nodes, then return
414 true, else return false. */
416 static bool
417 phi_alternatives_equal (basic_block dest, edge e1, edge e2)
419 int n1 = e1->dest_idx;
420 int n2 = e2->dest_idx;
421 gphi_iterator gsi;
423 for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
425 gphi *phi = gsi.phi ();
426 tree val1 = gimple_phi_arg_def (phi, n1);
427 tree val2 = gimple_phi_arg_def (phi, n2);
429 gcc_assert (val1 != NULL_TREE);
430 gcc_assert (val2 != NULL_TREE);
432 if (!operand_equal_for_phi_arg_p (val1, val2))
433 return false;
436 return true;
439 /* Removes forwarder block BB. Returns false if this failed. */
441 static bool
442 remove_forwarder_block (basic_block bb)
444 edge succ = single_succ_edge (bb), e, s;
445 basic_block dest = succ->dest;
446 gimple *stmt;
447 edge_iterator ei;
448 gimple_stmt_iterator gsi, gsi_to;
449 bool can_move_debug_stmts;
451 /* We check for infinite loops already in tree_forwarder_block_p.
452 However it may happen that the infinite loop is created
453 afterwards due to removal of forwarders. */
454 if (dest == bb)
455 return false;
457 /* If the destination block consists of a nonlocal label or is a
458 EH landing pad, do not merge it. */
459 stmt = first_stmt (dest);
460 if (stmt)
461 if (glabel *label_stmt = dyn_cast <glabel *> (stmt))
462 if (DECL_NONLOCAL (gimple_label_label (label_stmt))
463 || EH_LANDING_PAD_NR (gimple_label_label (label_stmt)) != 0)
464 return false;
466 /* If there is an abnormal edge to basic block BB, but not into
467 dest, problems might occur during removal of the phi node at out
468 of ssa due to overlapping live ranges of registers.
470 If there is an abnormal edge in DEST, the problems would occur
471 anyway since cleanup_dead_labels would then merge the labels for
472 two different eh regions, and rest of exception handling code
473 does not like it.
475 So if there is an abnormal edge to BB, proceed only if there is
476 no abnormal edge to DEST and there are no phi nodes in DEST. */
477 if (bb_has_abnormal_pred (bb)
478 && (bb_has_abnormal_pred (dest)
479 || !gimple_seq_empty_p (phi_nodes (dest))))
480 return false;
482 /* If there are phi nodes in DEST, and some of the blocks that are
483 predecessors of BB are also predecessors of DEST, check that the
484 phi node arguments match. */
485 if (!gimple_seq_empty_p (phi_nodes (dest)))
487 FOR_EACH_EDGE (e, ei, bb->preds)
489 s = find_edge (e->src, dest);
490 if (!s)
491 continue;
493 if (!phi_alternatives_equal (dest, succ, s))
494 return false;
498 can_move_debug_stmts = MAY_HAVE_DEBUG_STMTS && single_pred_p (dest);
500 basic_block pred = NULL;
501 if (single_pred_p (bb))
502 pred = single_pred (bb);
504 /* Redirect the edges. */
505 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
507 bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
509 if (e->flags & EDGE_ABNORMAL)
511 /* If there is an abnormal edge, redirect it anyway, and
512 move the labels to the new block to make it legal. */
513 s = redirect_edge_succ_nodup (e, dest);
515 else
516 s = redirect_edge_and_branch (e, dest);
518 if (s == e)
520 /* Create arguments for the phi nodes, since the edge was not
521 here before. */
522 for (gphi_iterator psi = gsi_start_phis (dest);
523 !gsi_end_p (psi);
524 gsi_next (&psi))
526 gphi *phi = psi.phi ();
527 source_location l = gimple_phi_arg_location_from_edge (phi, succ);
528 tree def = gimple_phi_arg_def (phi, succ->dest_idx);
529 add_phi_arg (phi, unshare_expr (def), s, l);
534 /* Move nonlocal labels and computed goto targets as well as user
535 defined labels and labels with an EH landing pad number to the
536 new block, so that the redirection of the abnormal edges works,
537 jump targets end up in a sane place and debug information for
538 labels is retained. */
539 gsi_to = gsi_start_bb (dest);
540 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
542 stmt = gsi_stmt (gsi);
543 if (is_gimple_debug (stmt))
544 break;
546 /* Forwarder blocks can only contain labels and debug stmts, and
547 labels must come first, so if we get to this point, we know
548 we're looking at a label. */
549 tree decl = gimple_label_label (as_a <glabel *> (stmt));
550 if (EH_LANDING_PAD_NR (decl) != 0
551 || DECL_NONLOCAL (decl)
552 || FORCED_LABEL (decl)
553 || !DECL_ARTIFICIAL (decl))
554 gsi_move_before (&gsi, &gsi_to);
555 else
556 gsi_next (&gsi);
559 /* Move debug statements if the destination has a single predecessor. */
560 if (can_move_debug_stmts && !gsi_end_p (gsi))
562 gsi_to = gsi_after_labels (dest);
565 gimple *debug = gsi_stmt (gsi);
566 gcc_assert (is_gimple_debug (debug));
567 gsi_move_before (&gsi, &gsi_to);
569 while (!gsi_end_p (gsi));
572 bitmap_set_bit (cfgcleanup_altered_bbs, dest->index);
574 /* Update the dominators. */
575 if (dom_info_available_p (CDI_DOMINATORS))
577 basic_block dom, dombb, domdest;
579 dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
580 domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
581 if (domdest == bb)
583 /* Shortcut to avoid calling (relatively expensive)
584 nearest_common_dominator unless necessary. */
585 dom = dombb;
587 else
588 dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
590 set_immediate_dominator (CDI_DOMINATORS, dest, dom);
593 /* Adjust latch infomation of BB's parent loop as otherwise
594 the cfg hook has a hard time not to kill the loop. */
595 if (current_loops && bb->loop_father->latch == bb)
596 bb->loop_father->latch = pred;
598 /* And kill the forwarder block. */
599 delete_basic_block (bb);
601 return true;
604 /* STMT is a call that has been discovered noreturn. Split the
605 block to prepare fixing up the CFG and remove LHS.
606 Return true if cleanup-cfg needs to run. */
608 bool
609 fixup_noreturn_call (gimple *stmt)
611 basic_block bb = gimple_bb (stmt);
612 bool changed = false;
614 if (gimple_call_builtin_p (stmt, BUILT_IN_RETURN))
615 return false;
617 /* First split basic block if stmt is not last. */
618 if (stmt != gsi_stmt (gsi_last_bb (bb)))
620 if (stmt == gsi_stmt (gsi_last_nondebug_bb (bb)))
622 /* Don't split if there are only debug stmts
623 after stmt, that can result in -fcompare-debug
624 failures. Remove the debug stmts instead,
625 they should be all unreachable anyway. */
626 gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
627 for (gsi_next (&gsi); !gsi_end_p (gsi); )
628 gsi_remove (&gsi, true);
630 else
632 split_block (bb, stmt);
633 changed = true;
637 /* If there is an LHS, remove it, but only if its type has fixed size.
638 The LHS will need to be recreated during RTL expansion and creating
639 temporaries of variable-sized types is not supported. Also don't
640 do this with TREE_ADDRESSABLE types, as assign_temp will abort.
641 Drop LHS regardless of TREE_ADDRESSABLE, if the function call
642 has been changed into a call that does not return a value, like
643 __builtin_unreachable or __cxa_pure_virtual. */
644 tree lhs = gimple_call_lhs (stmt);
645 if (lhs
646 && (should_remove_lhs_p (lhs)
647 || VOID_TYPE_P (TREE_TYPE (gimple_call_fntype (stmt)))))
649 gimple_call_set_lhs (stmt, NULL_TREE);
651 /* We need to fix up the SSA name to avoid checking errors. */
652 if (TREE_CODE (lhs) == SSA_NAME)
654 tree new_var = create_tmp_reg (TREE_TYPE (lhs));
655 SET_SSA_NAME_VAR_OR_IDENTIFIER (lhs, new_var);
656 SSA_NAME_DEF_STMT (lhs) = gimple_build_nop ();
657 set_ssa_default_def (cfun, new_var, lhs);
660 update_stmt (stmt);
663 /* Mark the call as altering control flow. */
664 if (!gimple_call_ctrl_altering_p (stmt))
666 gimple_call_set_ctrl_altering (stmt, true);
667 changed = true;
670 return changed;
673 /* Return true if we want to merge BB1 and BB2 into a single block. */
675 static bool
676 want_merge_blocks_p (basic_block bb1, basic_block bb2)
678 if (!can_merge_blocks_p (bb1, bb2))
679 return false;
680 gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb1);
681 if (gsi_end_p (gsi) || !stmt_can_terminate_bb_p (gsi_stmt (gsi)))
682 return true;
683 return bb1->count.ok_for_merging (bb2->count);
687 /* Tries to cleanup cfg in basic block BB by merging blocks. Returns
688 true if anything changes. */
690 static bool
691 cleanup_tree_cfg_bb (basic_block bb)
693 if (tree_forwarder_block_p (bb, false)
694 && remove_forwarder_block (bb))
695 return true;
697 /* If there is a merge opportunity with the predecessor
698 do nothing now but wait until we process the predecessor.
699 This happens when we visit BBs in a non-optimal order and
700 avoids quadratic behavior with adjusting stmts BB pointer. */
701 if (single_pred_p (bb)
702 && want_merge_blocks_p (single_pred (bb), bb))
703 /* But make sure we _do_ visit it. When we remove unreachable paths
704 ending in a backedge we fail to mark the destinations predecessors
705 as changed. */
706 bitmap_set_bit (cfgcleanup_altered_bbs, single_pred (bb)->index);
708 /* Merging the blocks may create new opportunities for folding
709 conditional branches (due to the elimination of single-valued PHI
710 nodes). */
711 else if (single_succ_p (bb)
712 && want_merge_blocks_p (bb, single_succ (bb)))
714 merge_blocks (bb, single_succ (bb));
715 return true;
718 return false;
721 /* Do cleanup_control_flow_bb in PRE order. */
723 static bool
724 cleanup_control_flow_pre ()
726 bool retval = false;
728 /* We want remove_edge_and_dominated_blocks to only remove edges,
729 not dominated blocks which it does when dom info isn't available.
730 Pretend so. */
731 dom_state saved_state = dom_info_state (CDI_DOMINATORS);
732 set_dom_info_availability (CDI_DOMINATORS, DOM_NONE);
734 auto_vec<edge_iterator, 20> stack (n_basic_blocks_for_fn (cfun) + 1);
735 auto_sbitmap visited (last_basic_block_for_fn (cfun));
736 bitmap_clear (visited);
738 stack.quick_push (ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs));
740 while (! stack.is_empty ())
742 /* Look at the edge on the top of the stack. */
743 edge_iterator ei = stack.last ();
744 basic_block dest = ei_edge (ei)->dest;
746 if (dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
747 && ! bitmap_bit_p (visited, dest->index))
749 bitmap_set_bit (visited, dest->index);
750 /* We only possibly remove edges from DEST here, leaving
751 possibly unreachable code in the IL. */
752 retval |= cleanup_control_flow_bb (dest);
753 if (EDGE_COUNT (dest->succs) > 0)
754 stack.quick_push (ei_start (dest->succs));
756 else
758 if (!ei_one_before_end_p (ei))
759 ei_next (&stack.last ());
760 else
761 stack.pop ();
765 set_dom_info_availability (CDI_DOMINATORS, saved_state);
767 /* We are deleting BBs in non-reverse dominator order, make sure
768 insert_debug_temps_for_defs is prepared for that. */
769 if (retval)
770 free_dominance_info (CDI_DOMINATORS);
772 /* Remove all now (and previously) unreachable blocks. */
773 for (int i = NUM_FIXED_BLOCKS; i < last_basic_block_for_fn (cfun); ++i)
775 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
776 if (bb && !bitmap_bit_p (visited, bb->index))
778 if (!retval)
779 free_dominance_info (CDI_DOMINATORS);
780 delete_basic_block (bb);
781 retval = true;
785 return retval;
788 static bool
789 mfb_keep_latches (edge e)
791 return !((dom_info_available_p (CDI_DOMINATORS)
792 && dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
793 || (e->flags & EDGE_DFS_BACK));
796 /* Remove unreachable blocks and other miscellaneous clean up work.
797 Return true if the flowgraph was modified, false otherwise. */
799 static bool
800 cleanup_tree_cfg_noloop (void)
802 timevar_push (TV_TREE_CLEANUP_CFG);
804 /* Ensure that we have single entries into loop headers. Otherwise
805 if one of the entries is becoming a latch due to CFG cleanup
806 (from formerly being part of an irreducible region) then we mess
807 up loop fixup and associate the old loop with a different region
808 which makes niter upper bounds invalid. See for example PR80549.
809 This needs to be done before we remove trivially dead edges as
810 we need to capture the dominance state before the pending transform. */
811 if (current_loops)
813 /* This needs backedges or dominators. */
814 if (!dom_info_available_p (CDI_DOMINATORS))
815 mark_dfs_back_edges ();
817 loop_p loop;
818 unsigned i;
819 FOR_EACH_VEC_ELT (*get_loops (cfun), i, loop)
820 if (loop && loop->header)
822 basic_block bb = loop->header;
823 edge_iterator ei;
824 edge e;
825 bool found_latch = false;
826 bool any_abnormal = false;
827 unsigned n = 0;
828 /* We are only interested in preserving existing loops, but
829 we need to check whether they are still real and of course
830 if we need to add a preheader at all. */
831 FOR_EACH_EDGE (e, ei, bb->preds)
833 if (e->flags & EDGE_ABNORMAL)
835 any_abnormal = true;
836 break;
838 if ((dom_info_available_p (CDI_DOMINATORS)
839 && dominated_by_p (CDI_DOMINATORS, e->src, bb))
840 || (e->flags & EDGE_DFS_BACK))
842 found_latch = true;
843 continue;
845 n++;
847 /* If we have more than one entry to the loop header
848 create a forwarder. */
849 if (found_latch && ! any_abnormal && n > 1)
851 edge fallthru = make_forwarder_block (bb, mfb_keep_latches,
852 NULL);
853 loop->header = fallthru->dest;
854 if (! loops_state_satisfies_p (LOOPS_NEED_FIXUP))
856 /* The loop updating from the CFG hook is incomplete
857 when we have multiple latches, fixup manually. */
858 remove_bb_from_loops (fallthru->src);
859 loop_p cloop = loop;
860 FOR_EACH_EDGE (e, ei, fallthru->src->preds)
861 cloop = find_common_loop (cloop, e->src->loop_father);
862 add_bb_to_loop (fallthru->src, cloop);
868 /* Prepare the worklists of altered blocks. */
869 cfgcleanup_altered_bbs = BITMAP_ALLOC (NULL);
871 /* Start by iterating over all basic blocks in PRE order looking for
872 edge removal opportunities. Do this first because incoming SSA form
873 may be invalid and we want to avoid performing SSA related tasks such
874 as propgating out a PHI node during BB merging in that state. This
875 also gets rid of unreachable blocks. */
876 bool changed = cleanup_control_flow_pre ();
878 /* After doing the above SSA form should be valid (or an update SSA
879 should be required). */
881 /* Compute dominator info which we need for the iterative process below. */
882 if (!dom_info_available_p (CDI_DOMINATORS))
883 calculate_dominance_info (CDI_DOMINATORS);
884 else
885 checking_verify_dominators (CDI_DOMINATORS);
887 /* During forwarder block cleanup, we may redirect edges out of
888 SWITCH_EXPRs, which can get expensive. So we want to enable
889 recording of edge to CASE_LABEL_EXPR. */
890 start_recording_case_labels ();
892 /* Continue by iterating over all basic blocks looking for BB merging
893 opportunities. We cannot use FOR_EACH_BB_FN for the BB iteration
894 since the basic blocks may get removed. */
895 unsigned n = last_basic_block_for_fn (cfun);
896 for (unsigned i = NUM_FIXED_BLOCKS; i < n; i++)
898 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
899 if (bb)
900 changed |= cleanup_tree_cfg_bb (bb);
903 /* Now process the altered blocks, as long as any are available. */
904 while (!bitmap_empty_p (cfgcleanup_altered_bbs))
906 unsigned i = bitmap_first_set_bit (cfgcleanup_altered_bbs);
907 bitmap_clear_bit (cfgcleanup_altered_bbs, i);
908 if (i < NUM_FIXED_BLOCKS)
909 continue;
911 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
912 if (!bb)
913 continue;
915 /* BB merging done by cleanup_tree_cfg_bb can end up propagating
916 out single-argument PHIs which in turn can expose
917 cleanup_control_flow_bb opportunities so we have to repeat
918 that here. */
919 changed |= cleanup_control_flow_bb (bb);
920 changed |= cleanup_tree_cfg_bb (bb);
923 end_recording_case_labels ();
924 BITMAP_FREE (cfgcleanup_altered_bbs);
926 gcc_assert (dom_info_available_p (CDI_DOMINATORS));
928 /* Do not renumber blocks if the SCEV cache is active, it is indexed by
929 basic-block numbers. */
930 if (! scev_initialized_p ())
931 compact_blocks ();
933 checking_verify_flow_info ();
935 timevar_pop (TV_TREE_CLEANUP_CFG);
937 if (changed && current_loops)
939 /* Removing edges and/or blocks may make recorded bounds refer
940 to stale GIMPLE stmts now, so clear them. */
941 free_numbers_of_iterations_estimates (cfun);
942 loops_state_set (LOOPS_NEED_FIXUP);
945 return changed;
948 /* Repairs loop structures. */
950 static void
951 repair_loop_structures (void)
953 bitmap changed_bbs;
954 unsigned n_new_loops;
956 calculate_dominance_info (CDI_DOMINATORS);
958 timevar_push (TV_REPAIR_LOOPS);
959 changed_bbs = BITMAP_ALLOC (NULL);
960 n_new_loops = fix_loop_structure (changed_bbs);
962 /* This usually does nothing. But sometimes parts of cfg that originally
963 were inside a loop get out of it due to edge removal (since they
964 become unreachable by back edges from latch). Also a former
965 irreducible loop can become reducible - in this case force a full
966 rewrite into loop-closed SSA form. */
967 if (loops_state_satisfies_p (LOOP_CLOSED_SSA))
968 rewrite_into_loop_closed_ssa (n_new_loops ? NULL : changed_bbs,
969 TODO_update_ssa);
971 BITMAP_FREE (changed_bbs);
973 checking_verify_loop_structure ();
974 scev_reset ();
976 timevar_pop (TV_REPAIR_LOOPS);
979 /* Cleanup cfg and repair loop structures. */
981 bool
982 cleanup_tree_cfg (void)
984 bool changed = cleanup_tree_cfg_noloop ();
986 if (current_loops != NULL
987 && loops_state_satisfies_p (LOOPS_NEED_FIXUP))
988 repair_loop_structures ();
990 return changed;
993 /* Tries to merge the PHI nodes at BB into those at BB's sole successor.
994 Returns true if successful. */
996 static bool
997 remove_forwarder_block_with_phi (basic_block bb)
999 edge succ = single_succ_edge (bb);
1000 basic_block dest = succ->dest;
1001 gimple *label;
1002 basic_block dombb, domdest, dom;
1004 /* We check for infinite loops already in tree_forwarder_block_p.
1005 However it may happen that the infinite loop is created
1006 afterwards due to removal of forwarders. */
1007 if (dest == bb)
1008 return false;
1010 /* Removal of forwarders may expose new natural loops and thus
1011 a block may turn into a loop header. */
1012 if (current_loops && bb_loop_header_p (bb))
1013 return false;
1015 /* If the destination block consists of a nonlocal label, do not
1016 merge it. */
1017 label = first_stmt (dest);
1018 if (label)
1019 if (glabel *label_stmt = dyn_cast <glabel *> (label))
1020 if (DECL_NONLOCAL (gimple_label_label (label_stmt)))
1021 return false;
1023 /* Record BB's single pred in case we need to update the father
1024 loop's latch information later. */
1025 basic_block pred = NULL;
1026 if (single_pred_p (bb))
1027 pred = single_pred (bb);
1029 /* Redirect each incoming edge to BB to DEST. */
1030 while (EDGE_COUNT (bb->preds) > 0)
1032 edge e = EDGE_PRED (bb, 0), s;
1033 gphi_iterator gsi;
1035 s = find_edge (e->src, dest);
1036 if (s)
1038 /* We already have an edge S from E->src to DEST. If S and
1039 E->dest's sole successor edge have the same PHI arguments
1040 at DEST, redirect S to DEST. */
1041 if (phi_alternatives_equal (dest, s, succ))
1043 e = redirect_edge_and_branch (e, dest);
1044 redirect_edge_var_map_clear (e);
1045 continue;
1048 /* PHI arguments are different. Create a forwarder block by
1049 splitting E so that we can merge PHI arguments on E to
1050 DEST. */
1051 e = single_succ_edge (split_edge (e));
1053 else
1055 /* If we merge the forwarder into a loop header verify if we
1056 are creating another loop latch edge. If so, reset
1057 number of iteration information of the loop. */
1058 if (dest->loop_father->header == dest
1059 && dominated_by_p (CDI_DOMINATORS, e->src, dest))
1061 dest->loop_father->any_upper_bound = false;
1062 dest->loop_father->any_likely_upper_bound = false;
1063 free_numbers_of_iterations_estimates (dest->loop_father);
1067 s = redirect_edge_and_branch (e, dest);
1069 /* redirect_edge_and_branch must not create a new edge. */
1070 gcc_assert (s == e);
1072 /* Add to the PHI nodes at DEST each PHI argument removed at the
1073 destination of E. */
1074 for (gsi = gsi_start_phis (dest);
1075 !gsi_end_p (gsi);
1076 gsi_next (&gsi))
1078 gphi *phi = gsi.phi ();
1079 tree def = gimple_phi_arg_def (phi, succ->dest_idx);
1080 source_location locus = gimple_phi_arg_location_from_edge (phi, succ);
1082 if (TREE_CODE (def) == SSA_NAME)
1084 /* If DEF is one of the results of PHI nodes removed during
1085 redirection, replace it with the PHI argument that used
1086 to be on E. */
1087 vec<edge_var_map> *head = redirect_edge_var_map_vector (e);
1088 size_t length = head ? head->length () : 0;
1089 for (size_t i = 0; i < length; i++)
1091 edge_var_map *vm = &(*head)[i];
1092 tree old_arg = redirect_edge_var_map_result (vm);
1093 tree new_arg = redirect_edge_var_map_def (vm);
1095 if (def == old_arg)
1097 def = new_arg;
1098 locus = redirect_edge_var_map_location (vm);
1099 break;
1104 add_phi_arg (phi, def, s, locus);
1107 redirect_edge_var_map_clear (e);
1110 /* Update the dominators. */
1111 dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
1112 domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
1113 if (domdest == bb)
1115 /* Shortcut to avoid calling (relatively expensive)
1116 nearest_common_dominator unless necessary. */
1117 dom = dombb;
1119 else
1120 dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
1122 set_immediate_dominator (CDI_DOMINATORS, dest, dom);
1124 /* Adjust latch infomation of BB's parent loop as otherwise
1125 the cfg hook has a hard time not to kill the loop. */
1126 if (current_loops && bb->loop_father->latch == bb)
1127 bb->loop_father->latch = pred;
1129 /* Remove BB since all of BB's incoming edges have been redirected
1130 to DEST. */
1131 delete_basic_block (bb);
1133 return true;
1136 /* This pass merges PHI nodes if one feeds into another. For example,
1137 suppose we have the following:
1139 goto <bb 9> (<L9>);
1141 <L8>:;
1142 tem_17 = foo ();
1144 # tem_6 = PHI <tem_17(8), tem_23(7)>;
1145 <L9>:;
1147 # tem_3 = PHI <tem_6(9), tem_2(5)>;
1148 <L10>:;
1150 Then we merge the first PHI node into the second one like so:
1152 goto <bb 9> (<L10>);
1154 <L8>:;
1155 tem_17 = foo ();
1157 # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
1158 <L10>:;
1161 namespace {
1163 const pass_data pass_data_merge_phi =
1165 GIMPLE_PASS, /* type */
1166 "mergephi", /* name */
1167 OPTGROUP_NONE, /* optinfo_flags */
1168 TV_TREE_MERGE_PHI, /* tv_id */
1169 ( PROP_cfg | PROP_ssa ), /* properties_required */
1170 0, /* properties_provided */
1171 0, /* properties_destroyed */
1172 0, /* todo_flags_start */
1173 0, /* todo_flags_finish */
1176 class pass_merge_phi : public gimple_opt_pass
1178 public:
1179 pass_merge_phi (gcc::context *ctxt)
1180 : gimple_opt_pass (pass_data_merge_phi, ctxt)
1183 /* opt_pass methods: */
1184 opt_pass * clone () { return new pass_merge_phi (m_ctxt); }
1185 virtual unsigned int execute (function *);
1187 }; // class pass_merge_phi
1189 unsigned int
1190 pass_merge_phi::execute (function *fun)
1192 basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
1193 basic_block *current = worklist;
1194 basic_block bb;
1196 calculate_dominance_info (CDI_DOMINATORS);
1198 /* Find all PHI nodes that we may be able to merge. */
1199 FOR_EACH_BB_FN (bb, fun)
1201 basic_block dest;
1203 /* Look for a forwarder block with PHI nodes. */
1204 if (!tree_forwarder_block_p (bb, true))
1205 continue;
1207 dest = single_succ (bb);
1209 /* We have to feed into another basic block with PHI
1210 nodes. */
1211 if (gimple_seq_empty_p (phi_nodes (dest))
1212 /* We don't want to deal with a basic block with
1213 abnormal edges. */
1214 || bb_has_abnormal_pred (bb))
1215 continue;
1217 if (!dominated_by_p (CDI_DOMINATORS, dest, bb))
1219 /* If BB does not dominate DEST, then the PHI nodes at
1220 DEST must be the only users of the results of the PHI
1221 nodes at BB. */
1222 *current++ = bb;
1224 else
1226 gphi_iterator gsi;
1227 unsigned int dest_idx = single_succ_edge (bb)->dest_idx;
1229 /* BB dominates DEST. There may be many users of the PHI
1230 nodes in BB. However, there is still a trivial case we
1231 can handle. If the result of every PHI in BB is used
1232 only by a PHI in DEST, then we can trivially merge the
1233 PHI nodes from BB into DEST. */
1234 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1235 gsi_next (&gsi))
1237 gphi *phi = gsi.phi ();
1238 tree result = gimple_phi_result (phi);
1239 use_operand_p imm_use;
1240 gimple *use_stmt;
1242 /* If the PHI's result is never used, then we can just
1243 ignore it. */
1244 if (has_zero_uses (result))
1245 continue;
1247 /* Get the single use of the result of this PHI node. */
1248 if (!single_imm_use (result, &imm_use, &use_stmt)
1249 || gimple_code (use_stmt) != GIMPLE_PHI
1250 || gimple_bb (use_stmt) != dest
1251 || gimple_phi_arg_def (use_stmt, dest_idx) != result)
1252 break;
1255 /* If the loop above iterated through all the PHI nodes
1256 in BB, then we can merge the PHIs from BB into DEST. */
1257 if (gsi_end_p (gsi))
1258 *current++ = bb;
1262 /* Now let's drain WORKLIST. */
1263 bool changed = false;
1264 while (current != worklist)
1266 bb = *--current;
1267 changed |= remove_forwarder_block_with_phi (bb);
1269 free (worklist);
1271 /* Removing forwarder blocks can cause formerly irreducible loops
1272 to become reducible if we merged two entry blocks. */
1273 if (changed
1274 && current_loops)
1275 loops_state_set (LOOPS_NEED_FIXUP);
1277 return 0;
1280 } // anon namespace
1282 gimple_opt_pass *
1283 make_pass_merge_phi (gcc::context *ctxt)
1285 return new pass_merge_phi (ctxt);
1288 /* Pass: cleanup the CFG just before expanding trees to RTL.
1289 This is just a round of label cleanups and case node grouping
1290 because after the tree optimizers have run such cleanups may
1291 be necessary. */
1293 static unsigned int
1294 execute_cleanup_cfg_post_optimizing (void)
1296 unsigned int todo = execute_fixup_cfg ();
1297 if (cleanup_tree_cfg ())
1299 todo &= ~TODO_cleanup_cfg;
1300 todo |= TODO_update_ssa;
1302 maybe_remove_unreachable_handlers ();
1303 cleanup_dead_labels ();
1304 if (group_case_labels ())
1305 todo |= TODO_cleanup_cfg;
1306 if ((flag_compare_debug_opt || flag_compare_debug)
1307 && flag_dump_final_insns)
1309 FILE *final_output = fopen (flag_dump_final_insns, "a");
1311 if (!final_output)
1313 error ("could not open final insn dump file %qs: %m",
1314 flag_dump_final_insns);
1315 flag_dump_final_insns = NULL;
1317 else
1319 int save_unnumbered = flag_dump_unnumbered;
1320 int save_noaddr = flag_dump_noaddr;
1322 flag_dump_noaddr = flag_dump_unnumbered = 1;
1323 fprintf (final_output, "\n");
1324 dump_enumerated_decls (final_output,
1325 dump_flags | TDF_SLIM | TDF_NOUID);
1326 flag_dump_noaddr = save_noaddr;
1327 flag_dump_unnumbered = save_unnumbered;
1328 if (fclose (final_output))
1330 error ("could not close final insn dump file %qs: %m",
1331 flag_dump_final_insns);
1332 flag_dump_final_insns = NULL;
1336 return todo;
1339 namespace {
1341 const pass_data pass_data_cleanup_cfg_post_optimizing =
1343 GIMPLE_PASS, /* type */
1344 "optimized", /* name */
1345 OPTGROUP_NONE, /* optinfo_flags */
1346 TV_TREE_CLEANUP_CFG, /* tv_id */
1347 PROP_cfg, /* properties_required */
1348 0, /* properties_provided */
1349 0, /* properties_destroyed */
1350 0, /* todo_flags_start */
1351 TODO_remove_unused_locals, /* todo_flags_finish */
1354 class pass_cleanup_cfg_post_optimizing : public gimple_opt_pass
1356 public:
1357 pass_cleanup_cfg_post_optimizing (gcc::context *ctxt)
1358 : gimple_opt_pass (pass_data_cleanup_cfg_post_optimizing, ctxt)
1361 /* opt_pass methods: */
1362 virtual unsigned int execute (function *)
1364 return execute_cleanup_cfg_post_optimizing ();
1367 }; // class pass_cleanup_cfg_post_optimizing
1369 } // anon namespace
1371 gimple_opt_pass *
1372 make_pass_cleanup_cfg_post_optimizing (gcc::context *ctxt)
1374 return new pass_cleanup_cfg_post_optimizing (ctxt);