1 /* CFG cleanup for trees.
2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
28 #include "hard-reg-set.h"
29 #include "basic-block.h"
36 #include "langhooks.h"
37 #include "diagnostic.h"
38 #include "tree-flow.h"
40 #include "tree-dump.h"
41 #include "tree-pass.h"
45 #include "cfglayout.h"
47 #include "tree-ssa-propagate.h"
48 #include "tree-scalar-evolution.h"
50 /* The set of blocks in that at least one of the following changes happened:
51 -- the statement at the end of the block was changed
52 -- the block was newly created
53 -- the set of the predecessors of the block changed
54 -- the set of the successors of the block changed
55 ??? Maybe we could track these changes separately, since they determine
56 what cleanups it makes sense to try on the block. */
57 bitmap cfgcleanup_altered_bbs;
59 /* Remove any fallthru edge from EV. Return true if an edge was removed. */
62 remove_fallthru_edge (VEC(edge,gc) *ev)
67 FOR_EACH_EDGE (e, ei, ev)
68 if ((e->flags & EDGE_FALLTHRU) != 0)
70 remove_edge_and_dominated_blocks (e);
76 /* Disconnect an unreachable block in the control expression starting
80 cleanup_control_expr_graph (basic_block bb, block_stmt_iterator bsi)
84 tree expr = bsi_stmt (bsi), val;
86 if (!single_succ_p (bb))
92 fold_defer_overflow_warnings ();
94 switch (TREE_CODE (expr))
97 val = fold (COND_EXPR_COND (expr));
101 val = fold (SWITCH_COND (expr));
102 if (TREE_CODE (val) != INTEGER_CST)
104 fold_undefer_and_ignore_overflow_warnings ();
113 taken_edge = find_taken_edge (bb, val);
116 fold_undefer_and_ignore_overflow_warnings ();
120 /* Remove all the edges except the one that is always executed. */
122 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
128 fold_undefer_overflow_warnings
129 (true, expr, WARN_STRICT_OVERFLOW_CONDITIONAL);
133 taken_edge->probability += e->probability;
134 taken_edge->count += e->count;
135 remove_edge_and_dominated_blocks (e);
142 fold_undefer_and_ignore_overflow_warnings ();
143 if (taken_edge->probability > REG_BR_PROB_BASE)
144 taken_edge->probability = REG_BR_PROB_BASE;
147 taken_edge = single_succ_edge (bb);
149 bitmap_set_bit (cfgcleanup_altered_bbs, bb->index);
150 bsi_remove (&bsi, true);
151 taken_edge->flags = EDGE_FALLTHRU;
156 /* Try to remove superfluous control structures in basic block BB. Returns
157 true if anything changes. */
160 cleanup_control_flow_bb (basic_block bb)
162 block_stmt_iterator bsi;
166 /* If the last statement of the block could throw and now cannot,
167 we need to prune cfg. */
168 retval |= tree_purge_dead_eh_edges (bb);
174 stmt = bsi_stmt (bsi);
176 if (TREE_CODE (stmt) == COND_EXPR
177 || TREE_CODE (stmt) == SWITCH_EXPR)
178 retval |= cleanup_control_expr_graph (bb, bsi);
179 /* If we had a computed goto which has a compile-time determinable
180 destination, then we can eliminate the goto. */
181 else if (TREE_CODE (stmt) == GOTO_EXPR
182 && TREE_CODE (GOTO_DESTINATION (stmt)) == ADDR_EXPR
183 && (TREE_CODE (TREE_OPERAND (GOTO_DESTINATION (stmt), 0))
189 basic_block target_block;
191 /* First look at all the outgoing edges. Delete any outgoing
192 edges which do not go to the right block. For the one
193 edge which goes to the right block, fix up its flags. */
194 label = TREE_OPERAND (GOTO_DESTINATION (stmt), 0);
195 target_block = label_to_block (label);
196 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
198 if (e->dest != target_block)
199 remove_edge_and_dominated_blocks (e);
202 /* Turn off the EDGE_ABNORMAL flag. */
203 e->flags &= ~EDGE_ABNORMAL;
205 /* And set EDGE_FALLTHRU. */
206 e->flags |= EDGE_FALLTHRU;
211 bitmap_set_bit (cfgcleanup_altered_bbs, bb->index);
212 bitmap_set_bit (cfgcleanup_altered_bbs, target_block->index);
214 /* Remove the GOTO_EXPR as it is not needed. The CFG has all the
215 relevant information we need. */
216 bsi_remove (&bsi, true);
220 /* Check for indirect calls that have been turned into
222 else if (noreturn_call_p (stmt) && remove_fallthru_edge (bb->succs))
228 /* Return true if basic block BB does nothing except pass control
229 flow to another block and that we can safely insert a label at
230 the start of the successor block.
232 As a precondition, we require that BB be not equal to
236 tree_forwarder_block_p (basic_block bb, bool phi_wanted)
238 block_stmt_iterator bsi;
243 /* BB must have a single outgoing edge. */
244 if (single_succ_p (bb) != 1
245 /* If PHI_WANTED is false, BB must not have any PHI nodes.
246 Otherwise, BB must have PHI nodes. */
247 || (phi_nodes (bb) != NULL_TREE) != phi_wanted
248 /* BB may not be a predecessor of EXIT_BLOCK_PTR. */
249 || single_succ (bb) == EXIT_BLOCK_PTR
250 /* Nor should this be an infinite loop. */
251 || single_succ (bb) == bb
252 /* BB may not have an abnormal outgoing edge. */
253 || (single_succ_edge (bb)->flags & EDGE_ABNORMAL))
257 gcc_assert (bb != ENTRY_BLOCK_PTR);
260 /* Now walk through the statements backward. We can ignore labels,
261 anything else means this is not a forwarder block. */
262 for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
264 tree stmt = bsi_stmt (bsi);
266 switch (TREE_CODE (stmt))
269 if (DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
278 if (find_edge (ENTRY_BLOCK_PTR, bb))
284 /* Protect loop latches, headers and preheaders. */
285 if (bb->loop_father->header == bb)
287 dest = EDGE_SUCC (bb, 0)->dest;
289 if (dest->loop_father->header == dest)
293 /* If we have an EH edge leaving this block, make sure that the
294 destination of this block has only one predecessor. This ensures
295 that we don't get into the situation where we try to remove two
296 forwarders that go to the same basic block but are handlers for
297 different EH regions. */
298 succ = single_succ_edge (bb);
300 FOR_EACH_EDGE (e, ei, bb->preds)
302 if (e->flags & EDGE_EH)
304 if (!single_pred_p (dest))
312 /* Return true if BB has at least one abnormal incoming edge. */
315 has_abnormal_incoming_edge_p (basic_block bb)
320 FOR_EACH_EDGE (e, ei, bb->preds)
321 if (e->flags & EDGE_ABNORMAL)
327 /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
328 those alternatives are equal in each of the PHI nodes, then return
329 true, else return false. */
332 phi_alternatives_equal (basic_block dest, edge e1, edge e2)
334 int n1 = e1->dest_idx;
335 int n2 = e2->dest_idx;
338 for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
340 tree val1 = PHI_ARG_DEF (phi, n1);
341 tree val2 = PHI_ARG_DEF (phi, n2);
343 gcc_assert (val1 != NULL_TREE);
344 gcc_assert (val2 != NULL_TREE);
346 if (!operand_equal_for_phi_arg_p (val1, val2))
353 /* Removes forwarder block BB. Returns false if this failed. */
356 remove_forwarder_block (basic_block bb)
358 edge succ = single_succ_edge (bb), e, s;
359 basic_block dest = succ->dest;
363 block_stmt_iterator bsi, bsi_to;
364 bool seen_abnormal_edge = false;
366 /* We check for infinite loops already in tree_forwarder_block_p.
367 However it may happen that the infinite loop is created
368 afterwards due to removal of forwarders. */
372 /* If the destination block consists of a nonlocal label, do not merge
374 label = first_stmt (dest);
376 && TREE_CODE (label) == LABEL_EXPR
377 && DECL_NONLOCAL (LABEL_EXPR_LABEL (label)))
380 /* If there is an abnormal edge to basic block BB, but not into
381 dest, problems might occur during removal of the phi node at out
382 of ssa due to overlapping live ranges of registers.
384 If there is an abnormal edge in DEST, the problems would occur
385 anyway since cleanup_dead_labels would then merge the labels for
386 two different eh regions, and rest of exception handling code
389 So if there is an abnormal edge to BB, proceed only if there is
390 no abnormal edge to DEST and there are no phi nodes in DEST. */
391 if (has_abnormal_incoming_edge_p (bb))
393 seen_abnormal_edge = true;
395 if (has_abnormal_incoming_edge_p (dest)
396 || phi_nodes (dest) != NULL_TREE)
400 /* If there are phi nodes in DEST, and some of the blocks that are
401 predecessors of BB are also predecessors of DEST, check that the
402 phi node arguments match. */
403 if (phi_nodes (dest))
405 FOR_EACH_EDGE (e, ei, bb->preds)
407 s = find_edge (e->src, dest);
411 if (!phi_alternatives_equal (dest, succ, s))
416 /* Redirect the edges. */
417 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
419 bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
421 if (e->flags & EDGE_ABNORMAL)
423 /* If there is an abnormal edge, redirect it anyway, and
424 move the labels to the new block to make it legal. */
425 s = redirect_edge_succ_nodup (e, dest);
428 s = redirect_edge_and_branch (e, dest);
432 /* Create arguments for the phi nodes, since the edge was not
434 for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
435 add_phi_arg (phi, PHI_ARG_DEF (phi, succ->dest_idx), s);
439 if (seen_abnormal_edge)
441 /* Move the labels to the new block, so that the redirection of
442 the abnormal edges works. */
444 bsi_to = bsi_start (dest);
445 for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
447 label = bsi_stmt (bsi);
448 gcc_assert (TREE_CODE (label) == LABEL_EXPR);
449 bsi_remove (&bsi, false);
450 bsi_insert_before (&bsi_to, label, BSI_CONTINUE_LINKING);
454 bitmap_set_bit (cfgcleanup_altered_bbs, dest->index);
456 /* Update the dominators. */
457 if (dom_info_available_p (CDI_DOMINATORS))
459 basic_block dom, dombb, domdest;
461 dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
462 domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
465 /* Shortcut to avoid calling (relatively expensive)
466 nearest_common_dominator unless necessary. */
470 dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
472 set_immediate_dominator (CDI_DOMINATORS, dest, dom);
475 /* And kill the forwarder block. */
476 delete_basic_block (bb);
481 /* Split basic blocks on calls in the middle of a basic block that are now
482 known not to return, and remove the unreachable code. */
485 split_bbs_on_noreturn_calls (void)
487 bool changed = false;
491 /* Detect cases where a mid-block call is now known not to return. */
493 while (VEC_length (tree, MODIFIED_NORETURN_CALLS (cfun)))
495 stmt = VEC_pop (tree, MODIFIED_NORETURN_CALLS (cfun));
496 bb = bb_for_stmt (stmt);
498 || last_stmt (bb) == stmt
499 || !noreturn_call_p (stmt))
503 split_block (bb, stmt);
504 remove_fallthru_edge (bb->succs);
510 /* Tries to cleanup cfg in basic block BB. Returns true if anything
514 cleanup_tree_cfg_bb (basic_block bb)
518 retval = cleanup_control_flow_bb (bb);
520 /* Forwarder blocks can carry line number information which is
521 useful when debugging, so we only clean them up when
525 && tree_forwarder_block_p (bb, false)
526 && remove_forwarder_block (bb))
529 /* Merging the blocks may create new opportunities for folding
530 conditional branches (due to the elimination of single-valued PHI
532 if (single_succ_p (bb)
533 && can_merge_blocks_p (bb, single_succ (bb)))
535 merge_blocks (bb, single_succ (bb));
542 /* Iterate the cfg cleanups, while anything changes. */
545 cleanup_tree_cfg_1 (void)
551 retval |= split_bbs_on_noreturn_calls ();
553 /* Prepare the worklists of altered blocks. */
554 cfgcleanup_altered_bbs = BITMAP_ALLOC (NULL);
556 /* During forwarder block cleanup, we may redirect edges out of
557 SWITCH_EXPRs, which can get expensive. So we want to enable
558 recording of edge to CASE_LABEL_EXPR. */
559 start_recording_case_labels ();
561 /* Start by iterating over all basic blocks. We cannot use FOR_EACH_BB,
562 since the basic blocks may get removed. */
563 n = last_basic_block;
564 for (i = NUM_FIXED_BLOCKS; i < n; i++)
566 bb = BASIC_BLOCK (i);
568 retval |= cleanup_tree_cfg_bb (bb);
571 /* Now process the altered blocks, as long as any are available. */
572 while (!bitmap_empty_p (cfgcleanup_altered_bbs))
574 i = bitmap_first_set_bit (cfgcleanup_altered_bbs);
575 bitmap_clear_bit (cfgcleanup_altered_bbs, i);
576 if (i < NUM_FIXED_BLOCKS)
579 bb = BASIC_BLOCK (i);
583 retval |= cleanup_tree_cfg_bb (bb);
585 /* Rerun split_bbs_on_noreturn_calls, in case we have altered any noreturn
587 retval |= split_bbs_on_noreturn_calls ();
590 end_recording_case_labels ();
591 BITMAP_FREE (cfgcleanup_altered_bbs);
596 /* Remove unreachable blocks and other miscellaneous clean up work.
597 Return true if the flowgraph was modified, false otherwise. */
600 cleanup_tree_cfg (void)
604 timevar_push (TV_TREE_CLEANUP_CFG);
606 /* Iterate until there are no more cleanups left to do. If any
607 iteration changed the flowgraph, set CHANGED to true.
609 If dominance information is available, there cannot be any unreachable
611 if (!dom_info_available_p (CDI_DOMINATORS))
613 changed = delete_unreachable_blocks ();
614 calculate_dominance_info (CDI_DOMINATORS);
618 #ifdef ENABLE_CHECKING
619 verify_dominators (CDI_DOMINATORS);
624 changed |= cleanup_tree_cfg_1 ();
626 gcc_assert (dom_info_available_p (CDI_DOMINATORS));
629 #ifdef ENABLE_CHECKING
633 timevar_pop (TV_TREE_CLEANUP_CFG);
638 /* Cleanup cfg and repair loop structures. */
641 cleanup_tree_cfg_loop (void)
643 bool changed = cleanup_tree_cfg ();
645 if (changed && current_loops != NULL)
647 bitmap changed_bbs = BITMAP_ALLOC (NULL);
648 fix_loop_structure (changed_bbs);
650 /* This usually does nothing. But sometimes parts of cfg that originally
651 were inside a loop get out of it due to edge removal (since they
652 become unreachable by back edges from latch). */
653 if ((current_loops->state & LOOP_CLOSED_SSA) != 0)
654 rewrite_into_loop_closed_ssa (changed_bbs, TODO_update_ssa);
656 BITMAP_FREE (changed_bbs);
658 #ifdef ENABLE_CHECKING
659 verify_loop_structure ();
666 /* Merge the PHI nodes at BB into those at BB's sole successor. */
669 remove_forwarder_block_with_phi (basic_block bb)
671 edge succ = single_succ_edge (bb);
672 basic_block dest = succ->dest;
674 basic_block dombb, domdest, dom;
676 /* We check for infinite loops already in tree_forwarder_block_p.
677 However it may happen that the infinite loop is created
678 afterwards due to removal of forwarders. */
682 /* If the destination block consists of a nonlocal label, do not
684 label = first_stmt (dest);
686 && TREE_CODE (label) == LABEL_EXPR
687 && DECL_NONLOCAL (LABEL_EXPR_LABEL (label)))
690 /* Redirect each incoming edge to BB to DEST. */
691 while (EDGE_COUNT (bb->preds) > 0)
693 edge e = EDGE_PRED (bb, 0), s;
696 s = find_edge (e->src, dest);
699 /* We already have an edge S from E->src to DEST. If S and
700 E->dest's sole successor edge have the same PHI arguments
701 at DEST, redirect S to DEST. */
702 if (phi_alternatives_equal (dest, s, succ))
704 e = redirect_edge_and_branch (e, dest);
705 PENDING_STMT (e) = NULL_TREE;
709 /* PHI arguments are different. Create a forwarder block by
710 splitting E so that we can merge PHI arguments on E to
712 e = single_succ_edge (split_edge (e));
715 s = redirect_edge_and_branch (e, dest);
717 /* redirect_edge_and_branch must not create a new edge. */
720 /* Add to the PHI nodes at DEST each PHI argument removed at the
722 for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
724 tree def = PHI_ARG_DEF (phi, succ->dest_idx);
726 if (TREE_CODE (def) == SSA_NAME)
730 /* If DEF is one of the results of PHI nodes removed during
731 redirection, replace it with the PHI argument that used
733 for (var = PENDING_STMT (e); var; var = TREE_CHAIN (var))
735 tree old_arg = TREE_PURPOSE (var);
736 tree new_arg = TREE_VALUE (var);
746 add_phi_arg (phi, def, s);
749 PENDING_STMT (e) = NULL;
752 /* Update the dominators. */
753 dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
754 domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
757 /* Shortcut to avoid calling (relatively expensive)
758 nearest_common_dominator unless necessary. */
762 dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
764 set_immediate_dominator (CDI_DOMINATORS, dest, dom);
766 /* Remove BB since all of BB's incoming edges have been redirected
768 delete_basic_block (bb);
771 /* This pass merges PHI nodes if one feeds into another. For example,
772 suppose we have the following:
779 # tem_6 = PHI <tem_17(8), tem_23(7)>;
782 # tem_3 = PHI <tem_6(9), tem_2(5)>;
785 Then we merge the first PHI node into the second one like so:
792 # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
797 merge_phi_nodes (void)
799 basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks);
800 basic_block *current = worklist;
803 calculate_dominance_info (CDI_DOMINATORS);
805 /* Find all PHI nodes that we may be able to merge. */
810 /* Look for a forwarder block with PHI nodes. */
811 if (!tree_forwarder_block_p (bb, true))
814 dest = single_succ (bb);
816 /* We have to feed into another basic block with PHI
818 if (!phi_nodes (dest)
819 /* We don't want to deal with a basic block with
821 || has_abnormal_incoming_edge_p (bb))
824 if (!dominated_by_p (CDI_DOMINATORS, dest, bb))
826 /* If BB does not dominate DEST, then the PHI nodes at
827 DEST must be the only users of the results of the PHI
834 unsigned int dest_idx = single_succ_edge (bb)->dest_idx;
836 /* BB dominates DEST. There may be many users of the PHI
837 nodes in BB. However, there is still a trivial case we
838 can handle. If the result of every PHI in BB is used
839 only by a PHI in DEST, then we can trivially merge the
840 PHI nodes from BB into DEST. */
841 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
843 tree result = PHI_RESULT (phi);
844 use_operand_p imm_use;
847 /* If the PHI's result is never used, then we can just
849 if (has_zero_uses (result))
852 /* Get the single use of the result of this PHI node. */
853 if (!single_imm_use (result, &imm_use, &use_stmt)
854 || TREE_CODE (use_stmt) != PHI_NODE
855 || bb_for_stmt (use_stmt) != dest
856 || PHI_ARG_DEF (use_stmt, dest_idx) != result)
860 /* If the loop above iterated through all the PHI nodes
861 in BB, then we can merge the PHIs from BB into DEST. */
867 /* Now let's drain WORKLIST. */
868 while (current != worklist)
871 remove_forwarder_block_with_phi (bb);
879 gate_merge_phi (void)
884 struct tree_opt_pass pass_merge_phi = {
885 "mergephi", /* name */
886 gate_merge_phi, /* gate */
887 merge_phi_nodes, /* execute */
890 0, /* static_pass_number */
891 TV_TREE_MERGE_PHI, /* tv_id */
892 PROP_cfg | PROP_ssa, /* properties_required */
893 0, /* properties_provided */
894 0, /* properties_destroyed */
895 0, /* todo_flags_start */
896 TODO_dump_func | TODO_ggc_collect /* todo_flags_finish */