Split can_vec_perm_p into can_vec_perm_{var,const}_p
[official-gcc.git] / gcc / tree-cfgcleanup.c
blobbfcca03257d34008c8f1ebc052eebdd097d20759
1 /* CFG cleanup for trees.
2 Copyright (C) 2001-2017 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 code_helper rcode;
150 tree ops[3] = {};
151 if (gimple_simplify (stmt, &rcode, ops, NULL, no_follow_ssa_edges,
152 no_follow_ssa_edges)
153 && rcode == INTEGER_CST)
154 val = ops[0];
156 break;
158 case GIMPLE_SWITCH:
159 val = gimple_switch_index (as_a <gswitch *> (stmt));
160 break;
162 default:
165 taken_edge = find_taken_edge (bb, val);
166 if (!taken_edge)
168 fold_undefer_and_ignore_overflow_warnings ();
169 return false;
172 /* Remove all the edges except the one that is always executed. */
173 warned = false;
174 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
176 if (e != taken_edge)
178 if (!warned)
180 fold_undefer_overflow_warnings
181 (true, stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
182 warned = true;
185 taken_edge->probability += e->probability;
186 remove_edge_and_dominated_blocks (e);
187 retval = true;
189 else
190 ei_next (&ei);
192 if (!warned)
193 fold_undefer_and_ignore_overflow_warnings ();
195 else
196 taken_edge = single_succ_edge (bb);
198 bitmap_set_bit (cfgcleanup_altered_bbs, bb->index);
199 gsi_remove (&gsi, true);
200 taken_edge->flags = EDGE_FALLTHRU;
202 return retval;
205 /* Cleanup the GF_CALL_CTRL_ALTERING flag according to
206 to updated gimple_call_flags. */
208 static void
209 cleanup_call_ctrl_altering_flag (gimple *bb_end)
211 if (!is_gimple_call (bb_end)
212 || !gimple_call_ctrl_altering_p (bb_end))
213 return;
215 int flags = gimple_call_flags (bb_end);
216 if (((flags & (ECF_CONST | ECF_PURE))
217 && !(flags & ECF_LOOPING_CONST_OR_PURE))
218 || (flags & ECF_LEAF))
219 gimple_call_set_ctrl_altering (bb_end, false);
222 /* Try to remove superfluous control structures in basic block BB. Returns
223 true if anything changes. */
225 static bool
226 cleanup_control_flow_bb (basic_block bb)
228 gimple_stmt_iterator gsi;
229 bool retval = false;
230 gimple *stmt;
232 /* If the last statement of the block could throw and now cannot,
233 we need to prune cfg. */
234 retval |= gimple_purge_dead_eh_edges (bb);
236 gsi = gsi_last_nondebug_bb (bb);
237 if (gsi_end_p (gsi))
238 return retval;
240 stmt = gsi_stmt (gsi);
242 /* Try to cleanup ctrl altering flag for call which ends bb. */
243 cleanup_call_ctrl_altering_flag (stmt);
245 if (gimple_code (stmt) == GIMPLE_COND
246 || gimple_code (stmt) == GIMPLE_SWITCH)
248 gcc_checking_assert (gsi_stmt (gsi_last_bb (bb)) == stmt);
249 retval |= cleanup_control_expr_graph (bb, gsi);
251 else if (gimple_code (stmt) == GIMPLE_GOTO
252 && TREE_CODE (gimple_goto_dest (stmt)) == ADDR_EXPR
253 && (TREE_CODE (TREE_OPERAND (gimple_goto_dest (stmt), 0))
254 == LABEL_DECL))
256 /* If we had a computed goto which has a compile-time determinable
257 destination, then we can eliminate the goto. */
258 edge e;
259 tree label;
260 edge_iterator ei;
261 basic_block target_block;
263 gcc_checking_assert (gsi_stmt (gsi_last_bb (bb)) == stmt);
264 /* First look at all the outgoing edges. Delete any outgoing
265 edges which do not go to the right block. For the one
266 edge which goes to the right block, fix up its flags. */
267 label = TREE_OPERAND (gimple_goto_dest (stmt), 0);
268 if (DECL_CONTEXT (label) != cfun->decl)
269 return retval;
270 target_block = label_to_block (label);
271 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
273 if (e->dest != target_block)
274 remove_edge_and_dominated_blocks (e);
275 else
277 /* Turn off the EDGE_ABNORMAL flag. */
278 e->flags &= ~EDGE_ABNORMAL;
280 /* And set EDGE_FALLTHRU. */
281 e->flags |= EDGE_FALLTHRU;
282 ei_next (&ei);
286 bitmap_set_bit (cfgcleanup_altered_bbs, bb->index);
287 bitmap_set_bit (cfgcleanup_altered_bbs, target_block->index);
289 /* Remove the GOTO_EXPR as it is not needed. The CFG has all the
290 relevant information we need. */
291 gsi_remove (&gsi, true);
292 retval = true;
295 /* Check for indirect calls that have been turned into
296 noreturn calls. */
297 else if (is_gimple_call (stmt)
298 && gimple_call_noreturn_p (stmt))
300 /* If there are debug stmts after the noreturn call, remove them
301 now, they should be all unreachable anyway. */
302 for (gsi_next (&gsi); !gsi_end_p (gsi); )
303 gsi_remove (&gsi, true);
304 if (remove_fallthru_edge (bb->succs))
305 retval = true;
308 return retval;
311 /* Return true if basic block BB does nothing except pass control
312 flow to another block and that we can safely insert a label at
313 the start of the successor block.
315 As a precondition, we require that BB be not equal to
316 the entry block. */
318 static bool
319 tree_forwarder_block_p (basic_block bb, bool phi_wanted)
321 gimple_stmt_iterator gsi;
322 location_t locus;
324 /* BB must have a single outgoing edge. */
325 if (single_succ_p (bb) != 1
326 /* If PHI_WANTED is false, BB must not have any PHI nodes.
327 Otherwise, BB must have PHI nodes. */
328 || gimple_seq_empty_p (phi_nodes (bb)) == phi_wanted
329 /* BB may not be a predecessor of the exit block. */
330 || single_succ (bb) == EXIT_BLOCK_PTR_FOR_FN (cfun)
331 /* Nor should this be an infinite loop. */
332 || single_succ (bb) == bb
333 /* BB may not have an abnormal outgoing edge. */
334 || (single_succ_edge (bb)->flags & EDGE_ABNORMAL))
335 return false;
337 gcc_checking_assert (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun));
339 locus = single_succ_edge (bb)->goto_locus;
341 /* There should not be an edge coming from entry, or an EH edge. */
343 edge_iterator ei;
344 edge e;
346 FOR_EACH_EDGE (e, ei, bb->preds)
347 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun) || (e->flags & EDGE_EH))
348 return false;
349 /* If goto_locus of any of the edges differs, prevent removing
350 the forwarder block for -O0. */
351 else if (optimize == 0 && e->goto_locus != locus)
352 return false;
355 /* Now walk through the statements backward. We can ignore labels,
356 anything else means this is not a forwarder block. */
357 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
359 gimple *stmt = gsi_stmt (gsi);
361 switch (gimple_code (stmt))
363 case GIMPLE_LABEL:
364 if (DECL_NONLOCAL (gimple_label_label (as_a <glabel *> (stmt))))
365 return false;
366 if (optimize == 0 && gimple_location (stmt) != locus)
367 return false;
368 break;
370 /* ??? For now, hope there's a corresponding debug
371 assignment at the destination. */
372 case GIMPLE_DEBUG:
373 break;
375 default:
376 return false;
380 if (current_loops)
382 basic_block dest;
383 /* Protect loop headers. */
384 if (bb_loop_header_p (bb))
385 return false;
387 dest = EDGE_SUCC (bb, 0)->dest;
388 /* Protect loop preheaders and latches if requested. */
389 if (dest->loop_father->header == dest)
391 if (bb->loop_father == dest->loop_father)
393 if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES))
394 return false;
395 /* If bb doesn't have a single predecessor we'd make this
396 loop have multiple latches. Don't do that if that
397 would in turn require disambiguating them. */
398 return (single_pred_p (bb)
399 || loops_state_satisfies_p
400 (LOOPS_MAY_HAVE_MULTIPLE_LATCHES));
402 else if (bb->loop_father == loop_outer (dest->loop_father))
403 return !loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS);
404 /* Always preserve other edges into loop headers that are
405 not simple latches or preheaders. */
406 return false;
410 return true;
413 /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
414 those alternatives are equal in each of the PHI nodes, then return
415 true, else return false. */
417 static bool
418 phi_alternatives_equal (basic_block dest, edge e1, edge e2)
420 int n1 = e1->dest_idx;
421 int n2 = e2->dest_idx;
422 gphi_iterator gsi;
424 for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
426 gphi *phi = gsi.phi ();
427 tree val1 = gimple_phi_arg_def (phi, n1);
428 tree val2 = gimple_phi_arg_def (phi, n2);
430 gcc_assert (val1 != NULL_TREE);
431 gcc_assert (val2 != NULL_TREE);
433 if (!operand_equal_for_phi_arg_p (val1, val2))
434 return false;
437 return true;
440 /* Removes forwarder block BB. Returns false if this failed. */
442 static bool
443 remove_forwarder_block (basic_block bb)
445 edge succ = single_succ_edge (bb), e, s;
446 basic_block dest = succ->dest;
447 gimple *stmt;
448 edge_iterator ei;
449 gimple_stmt_iterator gsi, gsi_to;
450 bool can_move_debug_stmts;
452 /* We check for infinite loops already in tree_forwarder_block_p.
453 However it may happen that the infinite loop is created
454 afterwards due to removal of forwarders. */
455 if (dest == bb)
456 return false;
458 /* If the destination block consists of a nonlocal label or is a
459 EH landing pad, do not merge it. */
460 stmt = first_stmt (dest);
461 if (stmt)
462 if (glabel *label_stmt = dyn_cast <glabel *> (stmt))
463 if (DECL_NONLOCAL (gimple_label_label (label_stmt))
464 || EH_LANDING_PAD_NR (gimple_label_label (label_stmt)) != 0)
465 return false;
467 /* If there is an abnormal edge to basic block BB, but not into
468 dest, problems might occur during removal of the phi node at out
469 of ssa due to overlapping live ranges of registers.
471 If there is an abnormal edge in DEST, the problems would occur
472 anyway since cleanup_dead_labels would then merge the labels for
473 two different eh regions, and rest of exception handling code
474 does not like it.
476 So if there is an abnormal edge to BB, proceed only if there is
477 no abnormal edge to DEST and there are no phi nodes in DEST. */
478 if (bb_has_abnormal_pred (bb)
479 && (bb_has_abnormal_pred (dest)
480 || !gimple_seq_empty_p (phi_nodes (dest))))
481 return false;
483 /* If there are phi nodes in DEST, and some of the blocks that are
484 predecessors of BB are also predecessors of DEST, check that the
485 phi node arguments match. */
486 if (!gimple_seq_empty_p (phi_nodes (dest)))
488 FOR_EACH_EDGE (e, ei, bb->preds)
490 s = find_edge (e->src, dest);
491 if (!s)
492 continue;
494 if (!phi_alternatives_equal (dest, succ, s))
495 return false;
499 can_move_debug_stmts = MAY_HAVE_DEBUG_STMTS && single_pred_p (dest);
501 basic_block pred = NULL;
502 if (single_pred_p (bb))
503 pred = single_pred (bb);
505 /* Redirect the edges. */
506 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
508 bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
510 if (e->flags & EDGE_ABNORMAL)
512 /* If there is an abnormal edge, redirect it anyway, and
513 move the labels to the new block to make it legal. */
514 s = redirect_edge_succ_nodup (e, dest);
516 else
517 s = redirect_edge_and_branch (e, dest);
519 if (s == e)
521 /* Create arguments for the phi nodes, since the edge was not
522 here before. */
523 for (gphi_iterator psi = gsi_start_phis (dest);
524 !gsi_end_p (psi);
525 gsi_next (&psi))
527 gphi *phi = psi.phi ();
528 source_location l = gimple_phi_arg_location_from_edge (phi, succ);
529 tree def = gimple_phi_arg_def (phi, succ->dest_idx);
530 add_phi_arg (phi, unshare_expr (def), s, l);
535 /* Move nonlocal labels and computed goto targets as well as user
536 defined labels and labels with an EH landing pad number to the
537 new block, so that the redirection of the abnormal edges works,
538 jump targets end up in a sane place and debug information for
539 labels is retained. */
540 gsi_to = gsi_start_bb (dest);
541 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
543 stmt = gsi_stmt (gsi);
544 if (is_gimple_debug (stmt))
545 break;
547 /* Forwarder blocks can only contain labels and debug stmts, and
548 labels must come first, so if we get to this point, we know
549 we're looking at a label. */
550 tree decl = gimple_label_label (as_a <glabel *> (stmt));
551 if (EH_LANDING_PAD_NR (decl) != 0
552 || DECL_NONLOCAL (decl)
553 || FORCED_LABEL (decl)
554 || !DECL_ARTIFICIAL (decl))
555 gsi_move_before (&gsi, &gsi_to);
556 else
557 gsi_next (&gsi);
560 /* Move debug statements if the destination has a single predecessor. */
561 if (can_move_debug_stmts && !gsi_end_p (gsi))
563 gsi_to = gsi_after_labels (dest);
566 gimple *debug = gsi_stmt (gsi);
567 gcc_assert (is_gimple_debug (debug));
568 gsi_move_before (&gsi, &gsi_to);
570 while (!gsi_end_p (gsi));
573 bitmap_set_bit (cfgcleanup_altered_bbs, dest->index);
575 /* Update the dominators. */
576 if (dom_info_available_p (CDI_DOMINATORS))
578 basic_block dom, dombb, domdest;
580 dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
581 domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
582 if (domdest == bb)
584 /* Shortcut to avoid calling (relatively expensive)
585 nearest_common_dominator unless necessary. */
586 dom = dombb;
588 else
589 dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
591 set_immediate_dominator (CDI_DOMINATORS, dest, dom);
594 /* Adjust latch infomation of BB's parent loop as otherwise
595 the cfg hook has a hard time not to kill the loop. */
596 if (current_loops && bb->loop_father->latch == bb)
597 bb->loop_father->latch = pred;
599 /* And kill the forwarder block. */
600 delete_basic_block (bb);
602 return true;
605 /* STMT is a call that has been discovered noreturn. Split the
606 block to prepare fixing up the CFG and remove LHS.
607 Return true if cleanup-cfg needs to run. */
609 bool
610 fixup_noreturn_call (gimple *stmt)
612 basic_block bb = gimple_bb (stmt);
613 bool changed = false;
615 if (gimple_call_builtin_p (stmt, BUILT_IN_RETURN))
616 return false;
618 /* First split basic block if stmt is not last. */
619 if (stmt != gsi_stmt (gsi_last_bb (bb)))
621 if (stmt == gsi_stmt (gsi_last_nondebug_bb (bb)))
623 /* Don't split if there are only debug stmts
624 after stmt, that can result in -fcompare-debug
625 failures. Remove the debug stmts instead,
626 they should be all unreachable anyway. */
627 gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
628 for (gsi_next (&gsi); !gsi_end_p (gsi); )
629 gsi_remove (&gsi, true);
631 else
633 split_block (bb, stmt);
634 changed = true;
638 /* If there is an LHS, remove it, but only if its type has fixed size.
639 The LHS will need to be recreated during RTL expansion and creating
640 temporaries of variable-sized types is not supported. Also don't
641 do this with TREE_ADDRESSABLE types, as assign_temp will abort.
642 Drop LHS regardless of TREE_ADDRESSABLE, if the function call
643 has been changed into a call that does not return a value, like
644 __builtin_unreachable or __cxa_pure_virtual. */
645 tree lhs = gimple_call_lhs (stmt);
646 if (lhs
647 && (should_remove_lhs_p (lhs)
648 || VOID_TYPE_P (TREE_TYPE (gimple_call_fntype (stmt)))))
650 gimple_call_set_lhs (stmt, NULL_TREE);
652 /* We need to fix up the SSA name to avoid checking errors. */
653 if (TREE_CODE (lhs) == SSA_NAME)
655 tree new_var = create_tmp_reg (TREE_TYPE (lhs));
656 SET_SSA_NAME_VAR_OR_IDENTIFIER (lhs, new_var);
657 SSA_NAME_DEF_STMT (lhs) = gimple_build_nop ();
658 set_ssa_default_def (cfun, new_var, lhs);
661 update_stmt (stmt);
664 /* Mark the call as altering control flow. */
665 if (!gimple_call_ctrl_altering_p (stmt))
667 gimple_call_set_ctrl_altering (stmt, true);
668 changed = true;
671 return changed;
674 /* Return true if we want to merge BB1 and BB2 into a single block. */
676 static bool
677 want_merge_blocks_p (basic_block bb1, basic_block bb2)
679 if (!can_merge_blocks_p (bb1, bb2))
680 return false;
681 gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb1);
682 if (gsi_end_p (gsi) || !stmt_can_terminate_bb_p (gsi_stmt (gsi)))
683 return true;
684 return bb1->count.ok_for_merging (bb2->count);
688 /* Tries to cleanup cfg in basic block BB. Returns true if anything
689 changes. */
691 static bool
692 cleanup_tree_cfg_bb (basic_block bb)
694 if (tree_forwarder_block_p (bb, false)
695 && remove_forwarder_block (bb))
696 return true;
698 /* If there is a merge opportunity with the predecessor
699 do nothing now but wait until we process the predecessor.
700 This happens when we visit BBs in a non-optimal order and
701 avoids quadratic behavior with adjusting stmts BB pointer. */
702 if (single_pred_p (bb)
703 && want_merge_blocks_p (single_pred (bb), bb))
704 /* But make sure we _do_ visit it. When we remove unreachable paths
705 ending in a backedge we fail to mark the destinations predecessors
706 as changed. */
707 bitmap_set_bit (cfgcleanup_altered_bbs, single_pred (bb)->index);
709 /* Merging the blocks may create new opportunities for folding
710 conditional branches (due to the elimination of single-valued PHI
711 nodes). */
712 else if (single_succ_p (bb)
713 && want_merge_blocks_p (bb, single_succ (bb)))
715 merge_blocks (bb, single_succ (bb));
716 return true;
719 return false;
722 /* Do cleanup_control_flow_bb in PRE order. */
724 static bool
725 cleanup_control_flow_pre ()
727 bool retval = false;
729 auto_vec<edge_iterator, 20> stack (n_basic_blocks_for_fn (cfun) + 1);
730 auto_sbitmap visited (last_basic_block_for_fn (cfun));
731 bitmap_clear (visited);
733 stack.quick_push (ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs));
735 while (! stack.is_empty ())
737 /* Look at the edge on the top of the stack. */
738 edge_iterator ei = stack.last ();
739 basic_block dest = ei_edge (ei)->dest;
741 if (dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
742 && ! bitmap_bit_p (visited, dest->index))
744 bitmap_set_bit (visited, dest->index);
745 retval |= cleanup_control_flow_bb (dest);
746 if (EDGE_COUNT (dest->succs) > 0)
747 stack.quick_push (ei_start (dest->succs));
749 else
751 if (!ei_one_before_end_p (ei))
752 ei_next (&stack.last ());
753 else
754 stack.pop ();
758 return retval;
761 /* Iterate the cfg cleanups, while anything changes. */
763 static bool
764 cleanup_tree_cfg_1 (void)
766 bool retval = false;
767 basic_block bb;
768 unsigned i, n;
770 /* Prepare the worklists of altered blocks. */
771 cfgcleanup_altered_bbs = BITMAP_ALLOC (NULL);
773 /* During forwarder block cleanup, we may redirect edges out of
774 SWITCH_EXPRs, which can get expensive. So we want to enable
775 recording of edge to CASE_LABEL_EXPR. */
776 start_recording_case_labels ();
778 /* We cannot use FOR_EACH_BB_FN for the BB iterations below
779 since the basic blocks may get removed. */
781 /* Start by iterating over all basic blocks in PRE order looking for
782 edge removal opportunities. Do this first because incoming SSA form
783 may be invalid and we want to avoid performing SSA related tasks such
784 as propgating out a PHI node during BB merging in that state. */
785 retval |= cleanup_control_flow_pre ();
787 /* After doing the above SSA form should be valid (or an update SSA
788 should be required). */
790 /* Continue by iterating over all basic blocks looking for BB merging
791 opportunities. */
792 n = last_basic_block_for_fn (cfun);
793 for (i = NUM_FIXED_BLOCKS; i < n; i++)
795 bb = BASIC_BLOCK_FOR_FN (cfun, i);
796 if (bb)
797 retval |= cleanup_tree_cfg_bb (bb);
800 /* Now process the altered blocks, as long as any are available. */
801 while (!bitmap_empty_p (cfgcleanup_altered_bbs))
803 i = bitmap_first_set_bit (cfgcleanup_altered_bbs);
804 bitmap_clear_bit (cfgcleanup_altered_bbs, i);
805 if (i < NUM_FIXED_BLOCKS)
806 continue;
808 bb = BASIC_BLOCK_FOR_FN (cfun, i);
809 if (!bb)
810 continue;
812 retval |= cleanup_control_flow_bb (bb);
813 retval |= cleanup_tree_cfg_bb (bb);
816 end_recording_case_labels ();
817 BITMAP_FREE (cfgcleanup_altered_bbs);
818 return retval;
821 static bool
822 mfb_keep_latches (edge e)
824 return ! dominated_by_p (CDI_DOMINATORS, e->src, e->dest);
827 /* Remove unreachable blocks and other miscellaneous clean up work.
828 Return true if the flowgraph was modified, false otherwise. */
830 static bool
831 cleanup_tree_cfg_noloop (void)
833 bool changed;
835 timevar_push (TV_TREE_CLEANUP_CFG);
837 /* Iterate until there are no more cleanups left to do. If any
838 iteration changed the flowgraph, set CHANGED to true.
840 If dominance information is available, there cannot be any unreachable
841 blocks. */
842 if (!dom_info_available_p (CDI_DOMINATORS))
844 changed = delete_unreachable_blocks ();
845 calculate_dominance_info (CDI_DOMINATORS);
847 else
849 checking_verify_dominators (CDI_DOMINATORS);
850 changed = false;
853 /* Ensure that we have single entries into loop headers. Otherwise
854 if one of the entries is becoming a latch due to CFG cleanup
855 (from formerly being part of an irreducible region) then we mess
856 up loop fixup and associate the old loop with a different region
857 which makes niter upper bounds invalid. See for example PR80549.
858 This needs to be done before we remove trivially dead edges as
859 we need to capture the dominance state before the pending transform. */
860 if (current_loops)
862 loop_p loop;
863 unsigned i;
864 FOR_EACH_VEC_ELT (*get_loops (cfun), i, loop)
865 if (loop && loop->header)
867 basic_block bb = loop->header;
868 edge_iterator ei;
869 edge e;
870 bool found_latch = false;
871 bool any_abnormal = false;
872 unsigned n = 0;
873 /* We are only interested in preserving existing loops, but
874 we need to check whether they are still real and of course
875 if we need to add a preheader at all. */
876 FOR_EACH_EDGE (e, ei, bb->preds)
878 if (e->flags & EDGE_ABNORMAL)
880 any_abnormal = true;
881 break;
883 if (dominated_by_p (CDI_DOMINATORS, e->src, bb))
885 found_latch = true;
886 continue;
888 n++;
890 /* If we have more than one entry to the loop header
891 create a forwarder. */
892 if (found_latch && ! any_abnormal && n > 1)
894 edge fallthru = make_forwarder_block (bb, mfb_keep_latches,
895 NULL);
896 loop->header = fallthru->dest;
897 if (! loops_state_satisfies_p (LOOPS_NEED_FIXUP))
899 /* The loop updating from the CFG hook is incomplete
900 when we have multiple latches, fixup manually. */
901 remove_bb_from_loops (fallthru->src);
902 loop_p cloop = loop;
903 FOR_EACH_EDGE (e, ei, fallthru->src->preds)
904 cloop = find_common_loop (cloop, e->src->loop_father);
905 add_bb_to_loop (fallthru->src, cloop);
911 changed |= cleanup_tree_cfg_1 ();
913 gcc_assert (dom_info_available_p (CDI_DOMINATORS));
915 /* Do not renumber blocks if the SCEV cache is active, it is indexed by
916 basic-block numbers. */
917 if (! scev_initialized_p ())
918 compact_blocks ();
920 checking_verify_flow_info ();
922 timevar_pop (TV_TREE_CLEANUP_CFG);
924 if (changed && current_loops)
926 /* Removing edges and/or blocks may make recorded bounds refer
927 to stale GIMPLE stmts now, so clear them. */
928 free_numbers_of_iterations_estimates (cfun);
929 loops_state_set (LOOPS_NEED_FIXUP);
932 return changed;
935 /* Repairs loop structures. */
937 static void
938 repair_loop_structures (void)
940 bitmap changed_bbs;
941 unsigned n_new_loops;
943 calculate_dominance_info (CDI_DOMINATORS);
945 timevar_push (TV_REPAIR_LOOPS);
946 changed_bbs = BITMAP_ALLOC (NULL);
947 n_new_loops = fix_loop_structure (changed_bbs);
949 /* This usually does nothing. But sometimes parts of cfg that originally
950 were inside a loop get out of it due to edge removal (since they
951 become unreachable by back edges from latch). Also a former
952 irreducible loop can become reducible - in this case force a full
953 rewrite into loop-closed SSA form. */
954 if (loops_state_satisfies_p (LOOP_CLOSED_SSA))
955 rewrite_into_loop_closed_ssa (n_new_loops ? NULL : changed_bbs,
956 TODO_update_ssa);
958 BITMAP_FREE (changed_bbs);
960 checking_verify_loop_structure ();
961 scev_reset ();
963 timevar_pop (TV_REPAIR_LOOPS);
966 /* Cleanup cfg and repair loop structures. */
968 bool
969 cleanup_tree_cfg (void)
971 bool changed = cleanup_tree_cfg_noloop ();
973 if (current_loops != NULL
974 && loops_state_satisfies_p (LOOPS_NEED_FIXUP))
975 repair_loop_structures ();
977 return changed;
980 /* Tries to merge the PHI nodes at BB into those at BB's sole successor.
981 Returns true if successful. */
983 static bool
984 remove_forwarder_block_with_phi (basic_block bb)
986 edge succ = single_succ_edge (bb);
987 basic_block dest = succ->dest;
988 gimple *label;
989 basic_block dombb, domdest, dom;
991 /* We check for infinite loops already in tree_forwarder_block_p.
992 However it may happen that the infinite loop is created
993 afterwards due to removal of forwarders. */
994 if (dest == bb)
995 return false;
997 /* Removal of forwarders may expose new natural loops and thus
998 a block may turn into a loop header. */
999 if (current_loops && bb_loop_header_p (bb))
1000 return false;
1002 /* If the destination block consists of a nonlocal label, do not
1003 merge it. */
1004 label = first_stmt (dest);
1005 if (label)
1006 if (glabel *label_stmt = dyn_cast <glabel *> (label))
1007 if (DECL_NONLOCAL (gimple_label_label (label_stmt)))
1008 return false;
1010 /* Record BB's single pred in case we need to update the father
1011 loop's latch information later. */
1012 basic_block pred = NULL;
1013 if (single_pred_p (bb))
1014 pred = single_pred (bb);
1016 /* Redirect each incoming edge to BB to DEST. */
1017 while (EDGE_COUNT (bb->preds) > 0)
1019 edge e = EDGE_PRED (bb, 0), s;
1020 gphi_iterator gsi;
1022 s = find_edge (e->src, dest);
1023 if (s)
1025 /* We already have an edge S from E->src to DEST. If S and
1026 E->dest's sole successor edge have the same PHI arguments
1027 at DEST, redirect S to DEST. */
1028 if (phi_alternatives_equal (dest, s, succ))
1030 e = redirect_edge_and_branch (e, dest);
1031 redirect_edge_var_map_clear (e);
1032 continue;
1035 /* PHI arguments are different. Create a forwarder block by
1036 splitting E so that we can merge PHI arguments on E to
1037 DEST. */
1038 e = single_succ_edge (split_edge (e));
1040 else
1042 /* If we merge the forwarder into a loop header verify if we
1043 are creating another loop latch edge. If so, reset
1044 number of iteration information of the loop. */
1045 if (dest->loop_father->header == dest
1046 && dominated_by_p (CDI_DOMINATORS, e->src, dest))
1048 dest->loop_father->any_upper_bound = false;
1049 dest->loop_father->any_likely_upper_bound = false;
1050 free_numbers_of_iterations_estimates (dest->loop_father);
1054 s = redirect_edge_and_branch (e, dest);
1056 /* redirect_edge_and_branch must not create a new edge. */
1057 gcc_assert (s == e);
1059 /* Add to the PHI nodes at DEST each PHI argument removed at the
1060 destination of E. */
1061 for (gsi = gsi_start_phis (dest);
1062 !gsi_end_p (gsi);
1063 gsi_next (&gsi))
1065 gphi *phi = gsi.phi ();
1066 tree def = gimple_phi_arg_def (phi, succ->dest_idx);
1067 source_location locus = gimple_phi_arg_location_from_edge (phi, succ);
1069 if (TREE_CODE (def) == SSA_NAME)
1071 /* If DEF is one of the results of PHI nodes removed during
1072 redirection, replace it with the PHI argument that used
1073 to be on E. */
1074 vec<edge_var_map> *head = redirect_edge_var_map_vector (e);
1075 size_t length = head ? head->length () : 0;
1076 for (size_t i = 0; i < length; i++)
1078 edge_var_map *vm = &(*head)[i];
1079 tree old_arg = redirect_edge_var_map_result (vm);
1080 tree new_arg = redirect_edge_var_map_def (vm);
1082 if (def == old_arg)
1084 def = new_arg;
1085 locus = redirect_edge_var_map_location (vm);
1086 break;
1091 add_phi_arg (phi, def, s, locus);
1094 redirect_edge_var_map_clear (e);
1097 /* Update the dominators. */
1098 dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
1099 domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
1100 if (domdest == bb)
1102 /* Shortcut to avoid calling (relatively expensive)
1103 nearest_common_dominator unless necessary. */
1104 dom = dombb;
1106 else
1107 dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
1109 set_immediate_dominator (CDI_DOMINATORS, dest, dom);
1111 /* Adjust latch infomation of BB's parent loop as otherwise
1112 the cfg hook has a hard time not to kill the loop. */
1113 if (current_loops && bb->loop_father->latch == bb)
1114 bb->loop_father->latch = pred;
1116 /* Remove BB since all of BB's incoming edges have been redirected
1117 to DEST. */
1118 delete_basic_block (bb);
1120 return true;
1123 /* This pass merges PHI nodes if one feeds into another. For example,
1124 suppose we have the following:
1126 goto <bb 9> (<L9>);
1128 <L8>:;
1129 tem_17 = foo ();
1131 # tem_6 = PHI <tem_17(8), tem_23(7)>;
1132 <L9>:;
1134 # tem_3 = PHI <tem_6(9), tem_2(5)>;
1135 <L10>:;
1137 Then we merge the first PHI node into the second one like so:
1139 goto <bb 9> (<L10>);
1141 <L8>:;
1142 tem_17 = foo ();
1144 # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
1145 <L10>:;
1148 namespace {
1150 const pass_data pass_data_merge_phi =
1152 GIMPLE_PASS, /* type */
1153 "mergephi", /* name */
1154 OPTGROUP_NONE, /* optinfo_flags */
1155 TV_TREE_MERGE_PHI, /* tv_id */
1156 ( PROP_cfg | PROP_ssa ), /* properties_required */
1157 0, /* properties_provided */
1158 0, /* properties_destroyed */
1159 0, /* todo_flags_start */
1160 0, /* todo_flags_finish */
1163 class pass_merge_phi : public gimple_opt_pass
1165 public:
1166 pass_merge_phi (gcc::context *ctxt)
1167 : gimple_opt_pass (pass_data_merge_phi, ctxt)
1170 /* opt_pass methods: */
1171 opt_pass * clone () { return new pass_merge_phi (m_ctxt); }
1172 virtual unsigned int execute (function *);
1174 }; // class pass_merge_phi
1176 unsigned int
1177 pass_merge_phi::execute (function *fun)
1179 basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
1180 basic_block *current = worklist;
1181 basic_block bb;
1183 calculate_dominance_info (CDI_DOMINATORS);
1185 /* Find all PHI nodes that we may be able to merge. */
1186 FOR_EACH_BB_FN (bb, fun)
1188 basic_block dest;
1190 /* Look for a forwarder block with PHI nodes. */
1191 if (!tree_forwarder_block_p (bb, true))
1192 continue;
1194 dest = single_succ (bb);
1196 /* We have to feed into another basic block with PHI
1197 nodes. */
1198 if (gimple_seq_empty_p (phi_nodes (dest))
1199 /* We don't want to deal with a basic block with
1200 abnormal edges. */
1201 || bb_has_abnormal_pred (bb))
1202 continue;
1204 if (!dominated_by_p (CDI_DOMINATORS, dest, bb))
1206 /* If BB does not dominate DEST, then the PHI nodes at
1207 DEST must be the only users of the results of the PHI
1208 nodes at BB. */
1209 *current++ = bb;
1211 else
1213 gphi_iterator gsi;
1214 unsigned int dest_idx = single_succ_edge (bb)->dest_idx;
1216 /* BB dominates DEST. There may be many users of the PHI
1217 nodes in BB. However, there is still a trivial case we
1218 can handle. If the result of every PHI in BB is used
1219 only by a PHI in DEST, then we can trivially merge the
1220 PHI nodes from BB into DEST. */
1221 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1222 gsi_next (&gsi))
1224 gphi *phi = gsi.phi ();
1225 tree result = gimple_phi_result (phi);
1226 use_operand_p imm_use;
1227 gimple *use_stmt;
1229 /* If the PHI's result is never used, then we can just
1230 ignore it. */
1231 if (has_zero_uses (result))
1232 continue;
1234 /* Get the single use of the result of this PHI node. */
1235 if (!single_imm_use (result, &imm_use, &use_stmt)
1236 || gimple_code (use_stmt) != GIMPLE_PHI
1237 || gimple_bb (use_stmt) != dest
1238 || gimple_phi_arg_def (use_stmt, dest_idx) != result)
1239 break;
1242 /* If the loop above iterated through all the PHI nodes
1243 in BB, then we can merge the PHIs from BB into DEST. */
1244 if (gsi_end_p (gsi))
1245 *current++ = bb;
1249 /* Now let's drain WORKLIST. */
1250 bool changed = false;
1251 while (current != worklist)
1253 bb = *--current;
1254 changed |= remove_forwarder_block_with_phi (bb);
1256 free (worklist);
1258 /* Removing forwarder blocks can cause formerly irreducible loops
1259 to become reducible if we merged two entry blocks. */
1260 if (changed
1261 && current_loops)
1262 loops_state_set (LOOPS_NEED_FIXUP);
1264 return 0;
1267 } // anon namespace
1269 gimple_opt_pass *
1270 make_pass_merge_phi (gcc::context *ctxt)
1272 return new pass_merge_phi (ctxt);
1275 /* Pass: cleanup the CFG just before expanding trees to RTL.
1276 This is just a round of label cleanups and case node grouping
1277 because after the tree optimizers have run such cleanups may
1278 be necessary. */
1280 static unsigned int
1281 execute_cleanup_cfg_post_optimizing (void)
1283 unsigned int todo = execute_fixup_cfg ();
1284 if (cleanup_tree_cfg ())
1286 todo &= ~TODO_cleanup_cfg;
1287 todo |= TODO_update_ssa;
1289 maybe_remove_unreachable_handlers ();
1290 cleanup_dead_labels ();
1291 if (group_case_labels ())
1292 todo |= TODO_cleanup_cfg;
1293 if ((flag_compare_debug_opt || flag_compare_debug)
1294 && flag_dump_final_insns)
1296 FILE *final_output = fopen (flag_dump_final_insns, "a");
1298 if (!final_output)
1300 error ("could not open final insn dump file %qs: %m",
1301 flag_dump_final_insns);
1302 flag_dump_final_insns = NULL;
1304 else
1306 int save_unnumbered = flag_dump_unnumbered;
1307 int save_noaddr = flag_dump_noaddr;
1309 flag_dump_noaddr = flag_dump_unnumbered = 1;
1310 fprintf (final_output, "\n");
1311 dump_enumerated_decls (final_output,
1312 dump_flags | TDF_SLIM | TDF_NOUID);
1313 flag_dump_noaddr = save_noaddr;
1314 flag_dump_unnumbered = save_unnumbered;
1315 if (fclose (final_output))
1317 error ("could not close final insn dump file %qs: %m",
1318 flag_dump_final_insns);
1319 flag_dump_final_insns = NULL;
1323 return todo;
1326 namespace {
1328 const pass_data pass_data_cleanup_cfg_post_optimizing =
1330 GIMPLE_PASS, /* type */
1331 "optimized", /* name */
1332 OPTGROUP_NONE, /* optinfo_flags */
1333 TV_TREE_CLEANUP_CFG, /* tv_id */
1334 PROP_cfg, /* properties_required */
1335 0, /* properties_provided */
1336 0, /* properties_destroyed */
1337 0, /* todo_flags_start */
1338 TODO_remove_unused_locals, /* todo_flags_finish */
1341 class pass_cleanup_cfg_post_optimizing : public gimple_opt_pass
1343 public:
1344 pass_cleanup_cfg_post_optimizing (gcc::context *ctxt)
1345 : gimple_opt_pass (pass_data_cleanup_cfg_post_optimizing, ctxt)
1348 /* opt_pass methods: */
1349 virtual unsigned int execute (function *)
1351 return execute_cleanup_cfg_post_optimizing ();
1354 }; // class pass_cleanup_cfg_post_optimizing
1356 } // anon namespace
1358 gimple_opt_pass *
1359 make_pass_cleanup_cfg_post_optimizing (gcc::context *ctxt)
1361 return new pass_cleanup_cfg_post_optimizing (ctxt);