1 /* CFG cleanup for trees.
2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
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);
77 /* Disconnect an unreachable block in the control expression starting
81 cleanup_control_expr_graph (basic_block bb, gimple_stmt_iterator gsi)
85 gimple stmt = gsi_stmt (gsi);
88 if (!single_succ_p (bb))
94 fold_defer_overflow_warnings ();
95 val = gimple_fold (stmt);
96 taken_edge = find_taken_edge (bb, val);
99 fold_undefer_and_ignore_overflow_warnings ();
103 /* Remove all the edges except the one that is always executed. */
105 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
111 fold_undefer_overflow_warnings
112 (true, stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
116 taken_edge->probability += e->probability;
117 taken_edge->count += e->count;
118 remove_edge_and_dominated_blocks (e);
125 fold_undefer_and_ignore_overflow_warnings ();
126 if (taken_edge->probability > REG_BR_PROB_BASE)
127 taken_edge->probability = REG_BR_PROB_BASE;
130 taken_edge = single_succ_edge (bb);
132 bitmap_set_bit (cfgcleanup_altered_bbs, bb->index);
133 gsi_remove (&gsi, true);
134 taken_edge->flags = EDGE_FALLTHRU;
139 /* Try to remove superfluous control structures in basic block BB. Returns
140 true if anything changes. */
143 cleanup_control_flow_bb (basic_block bb)
145 gimple_stmt_iterator gsi;
149 /* If the last statement of the block could throw and now cannot,
150 we need to prune cfg. */
151 retval |= gimple_purge_dead_eh_edges (bb);
153 gsi = gsi_last_bb (bb);
157 stmt = gsi_stmt (gsi);
159 if (gimple_code (stmt) == GIMPLE_COND
160 || gimple_code (stmt) == GIMPLE_SWITCH)
161 retval |= cleanup_control_expr_graph (bb, gsi);
162 else if (gimple_code (stmt) == GIMPLE_GOTO
163 && TREE_CODE (gimple_goto_dest (stmt)) == ADDR_EXPR
164 && (TREE_CODE (TREE_OPERAND (gimple_goto_dest (stmt), 0))
167 /* If we had a computed goto which has a compile-time determinable
168 destination, then we can eliminate the goto. */
172 basic_block target_block;
174 /* First look at all the outgoing edges. Delete any outgoing
175 edges which do not go to the right block. For the one
176 edge which goes to the right block, fix up its flags. */
177 label = TREE_OPERAND (gimple_goto_dest (stmt), 0);
178 target_block = label_to_block (label);
179 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
181 if (e->dest != target_block)
182 remove_edge_and_dominated_blocks (e);
185 /* Turn off the EDGE_ABNORMAL flag. */
186 e->flags &= ~EDGE_ABNORMAL;
188 /* And set EDGE_FALLTHRU. */
189 e->flags |= EDGE_FALLTHRU;
194 bitmap_set_bit (cfgcleanup_altered_bbs, bb->index);
195 bitmap_set_bit (cfgcleanup_altered_bbs, target_block->index);
197 /* Remove the GOTO_EXPR as it is not needed. The CFG has all the
198 relevant information we need. */
199 gsi_remove (&gsi, true);
203 /* Check for indirect calls that have been turned into
205 else if (is_gimple_call (stmt)
206 && gimple_call_noreturn_p (stmt)
207 && remove_fallthru_edge (bb->succs))
213 /* Return true if basic block BB does nothing except pass control
214 flow to another block and that we can safely insert a label at
215 the start of the successor block.
217 As a precondition, we require that BB be not equal to
221 tree_forwarder_block_p (basic_block bb, bool phi_wanted)
223 gimple_stmt_iterator gsi;
225 /* BB must have a single outgoing edge. */
226 if (single_succ_p (bb) != 1
227 /* If PHI_WANTED is false, BB must not have any PHI nodes.
228 Otherwise, BB must have PHI nodes. */
229 || gimple_seq_empty_p (phi_nodes (bb)) == phi_wanted
230 /* BB may not be a predecessor of EXIT_BLOCK_PTR. */
231 || single_succ (bb) == EXIT_BLOCK_PTR
232 /* Nor should this be an infinite loop. */
233 || single_succ (bb) == bb
234 /* BB may not have an abnormal outgoing edge. */
235 || (single_succ_edge (bb)->flags & EDGE_ABNORMAL))
239 gcc_assert (bb != ENTRY_BLOCK_PTR);
242 /* There should not be an edge coming from entry, or an EH edge. */
247 FOR_EACH_EDGE (e, ei, bb->preds)
248 if (e->src == ENTRY_BLOCK_PTR || (e->flags & EDGE_EH))
252 /* Now walk through the statements backward. We can ignore labels,
253 anything else means this is not a forwarder block. */
254 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
256 gimple stmt = gsi_stmt (gsi);
258 switch (gimple_code (stmt))
261 if (DECL_NONLOCAL (gimple_label_label (stmt)))
265 /* ??? For now, hope there's a corresponding debug
266 assignment at the destination. */
278 /* Protect loop latches, headers and preheaders. */
279 if (bb->loop_father->header == bb)
281 dest = EDGE_SUCC (bb, 0)->dest;
283 if (dest->loop_father->header == dest)
289 /* Return true if BB has at least one abnormal incoming edge. */
292 has_abnormal_incoming_edge_p (basic_block bb)
297 FOR_EACH_EDGE (e, ei, bb->preds)
298 if (e->flags & EDGE_ABNORMAL)
304 /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
305 those alternatives are equal in each of the PHI nodes, then return
306 true, else return false. */
309 phi_alternatives_equal (basic_block dest, edge e1, edge e2)
311 int n1 = e1->dest_idx;
312 int n2 = e2->dest_idx;
313 gimple_stmt_iterator gsi;
315 for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
317 gimple phi = gsi_stmt (gsi);
318 tree val1 = gimple_phi_arg_def (phi, n1);
319 tree val2 = gimple_phi_arg_def (phi, n2);
321 gcc_assert (val1 != NULL_TREE);
322 gcc_assert (val2 != NULL_TREE);
324 if (!operand_equal_for_phi_arg_p (val1, val2))
331 /* Removes forwarder block BB. Returns false if this failed. */
334 remove_forwarder_block (basic_block bb)
336 edge succ = single_succ_edge (bb), e, s;
337 basic_block dest = succ->dest;
340 gimple_stmt_iterator gsi, gsi_to;
342 /* We check for infinite loops already in tree_forwarder_block_p.
343 However it may happen that the infinite loop is created
344 afterwards due to removal of forwarders. */
348 /* If the destination block consists of a nonlocal label, do not merge
350 label = first_stmt (dest);
352 && gimple_code (label) == GIMPLE_LABEL
353 && DECL_NONLOCAL (gimple_label_label (label)))
356 /* If there is an abnormal edge to basic block BB, but not into
357 dest, problems might occur during removal of the phi node at out
358 of ssa due to overlapping live ranges of registers.
360 If there is an abnormal edge in DEST, the problems would occur
361 anyway since cleanup_dead_labels would then merge the labels for
362 two different eh regions, and rest of exception handling code
365 So if there is an abnormal edge to BB, proceed only if there is
366 no abnormal edge to DEST and there are no phi nodes in DEST. */
367 if (has_abnormal_incoming_edge_p (bb)
368 && (has_abnormal_incoming_edge_p (dest)
369 || !gimple_seq_empty_p (phi_nodes (dest))))
372 /* If there are phi nodes in DEST, and some of the blocks that are
373 predecessors of BB are also predecessors of DEST, check that the
374 phi node arguments match. */
375 if (!gimple_seq_empty_p (phi_nodes (dest)))
377 FOR_EACH_EDGE (e, ei, bb->preds)
379 s = find_edge (e->src, dest);
383 if (!phi_alternatives_equal (dest, succ, s))
388 /* Redirect the edges. */
389 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
391 bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
393 if (e->flags & EDGE_ABNORMAL)
395 /* If there is an abnormal edge, redirect it anyway, and
396 move the labels to the new block to make it legal. */
397 s = redirect_edge_succ_nodup (e, dest);
400 s = redirect_edge_and_branch (e, dest);
404 /* Create arguments for the phi nodes, since the edge was not
406 for (gsi = gsi_start_phis (dest);
410 gimple phi = gsi_stmt (gsi);
411 source_location l = gimple_phi_arg_location_from_edge (phi, succ);
412 add_phi_arg (phi, gimple_phi_arg_def (phi, succ->dest_idx), s, l);
417 /* Move nonlocal labels and computed goto targets as well as user
418 defined labels and labels with an EH landing pad number to the
419 new block, so that the redirection of the abnormal edges works,
420 jump targets end up in a sane place and debug information for
421 labels is retained. */
422 gsi_to = gsi_start_bb (dest);
423 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
426 label = gsi_stmt (gsi);
427 if (is_gimple_debug (label))
429 decl = gimple_label_label (label);
430 if (EH_LANDING_PAD_NR (decl) != 0
431 || DECL_NONLOCAL (decl)
432 || FORCED_LABEL (decl)
433 || !DECL_ARTIFICIAL (decl))
435 gsi_remove (&gsi, false);
436 gsi_insert_before (&gsi_to, label, GSI_SAME_STMT);
442 /* Move debug statements if the destination has just a single
444 if (single_pred_p (dest))
446 gsi_to = gsi_after_labels (dest);
447 for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); )
449 if (!is_gimple_debug (gsi_stmt (gsi)))
451 gsi_remove (&gsi, false);
452 gsi_insert_before (&gsi_to, label, GSI_SAME_STMT);
456 bitmap_set_bit (cfgcleanup_altered_bbs, dest->index);
458 /* Update the dominators. */
459 if (dom_info_available_p (CDI_DOMINATORS))
461 basic_block dom, dombb, domdest;
463 dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
464 domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
467 /* Shortcut to avoid calling (relatively expensive)
468 nearest_common_dominator unless necessary. */
472 dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
474 set_immediate_dominator (CDI_DOMINATORS, dest, dom);
477 /* And kill the forwarder block. */
478 delete_basic_block (bb);
483 /* Split basic blocks on calls in the middle of a basic block that are now
484 known not to return, and remove the unreachable code. */
487 split_bbs_on_noreturn_calls (void)
489 bool changed = false;
493 /* Detect cases where a mid-block call is now known not to return. */
495 while (VEC_length (gimple, MODIFIED_NORETURN_CALLS (cfun)))
497 stmt = VEC_pop (gimple, MODIFIED_NORETURN_CALLS (cfun));
498 bb = gimple_bb (stmt);
499 /* BB might be deleted at this point, so verify first
500 BB is present in the cfg. */
502 || bb->index < NUM_FIXED_BLOCKS
503 || bb->index >= n_basic_blocks
504 || BASIC_BLOCK (bb->index) != bb
505 || last_stmt (bb) == stmt
506 || !gimple_call_noreturn_p (stmt))
510 split_block (bb, stmt);
511 remove_fallthru_edge (bb->succs);
517 /* If GIMPLE_OMP_RETURN in basic block BB is unreachable, remove it. */
520 cleanup_omp_return (basic_block bb)
522 gimple stmt = last_stmt (bb);
523 basic_block control_bb;
526 || gimple_code (stmt) != GIMPLE_OMP_RETURN
527 || !single_pred_p (bb))
530 control_bb = single_pred (bb);
531 stmt = last_stmt (control_bb);
533 if (stmt == NULL || gimple_code (stmt) != GIMPLE_OMP_SECTIONS_SWITCH)
536 /* The block with the control statement normally has two entry edges -- one
537 from entry, one from continue. If continue is removed, return is
538 unreachable, so we remove it here as well. */
539 if (EDGE_COUNT (control_bb->preds) == 2)
542 gcc_assert (EDGE_COUNT (control_bb->preds) == 1);
543 remove_edge_and_dominated_blocks (single_pred_edge (bb));
547 /* Tries to cleanup cfg in basic block BB. Returns true if anything
551 cleanup_tree_cfg_bb (basic_block bb)
555 if (cleanup_omp_return (bb))
558 retval = cleanup_control_flow_bb (bb);
560 /* Forwarder blocks can carry line number information which is
561 useful when debugging, so we only clean them up when
564 && tree_forwarder_block_p (bb, false)
565 && remove_forwarder_block (bb))
568 /* Merging the blocks may create new opportunities for folding
569 conditional branches (due to the elimination of single-valued PHI
571 if (single_succ_p (bb)
572 && can_merge_blocks_p (bb, single_succ (bb)))
574 merge_blocks (bb, single_succ (bb));
581 /* Iterate the cfg cleanups, while anything changes. */
584 cleanup_tree_cfg_1 (void)
590 retval |= split_bbs_on_noreturn_calls ();
592 /* Prepare the worklists of altered blocks. */
593 cfgcleanup_altered_bbs = BITMAP_ALLOC (NULL);
595 /* During forwarder block cleanup, we may redirect edges out of
596 SWITCH_EXPRs, which can get expensive. So we want to enable
597 recording of edge to CASE_LABEL_EXPR. */
598 start_recording_case_labels ();
600 /* Start by iterating over all basic blocks. We cannot use FOR_EACH_BB,
601 since the basic blocks may get removed. */
602 n = last_basic_block;
603 for (i = NUM_FIXED_BLOCKS; i < n; i++)
605 bb = BASIC_BLOCK (i);
607 retval |= cleanup_tree_cfg_bb (bb);
610 /* Now process the altered blocks, as long as any are available. */
611 while (!bitmap_empty_p (cfgcleanup_altered_bbs))
613 i = bitmap_first_set_bit (cfgcleanup_altered_bbs);
614 bitmap_clear_bit (cfgcleanup_altered_bbs, i);
615 if (i < NUM_FIXED_BLOCKS)
618 bb = BASIC_BLOCK (i);
622 retval |= cleanup_tree_cfg_bb (bb);
624 /* Rerun split_bbs_on_noreturn_calls, in case we have altered any noreturn
626 retval |= split_bbs_on_noreturn_calls ();
629 end_recording_case_labels ();
630 BITMAP_FREE (cfgcleanup_altered_bbs);
635 /* Remove unreachable blocks and other miscellaneous clean up work.
636 Return true if the flowgraph was modified, false otherwise. */
639 cleanup_tree_cfg_noloop (void)
643 timevar_push (TV_TREE_CLEANUP_CFG);
645 /* Iterate until there are no more cleanups left to do. If any
646 iteration changed the flowgraph, set CHANGED to true.
648 If dominance information is available, there cannot be any unreachable
650 if (!dom_info_available_p (CDI_DOMINATORS))
652 changed = delete_unreachable_blocks ();
653 calculate_dominance_info (CDI_DOMINATORS);
657 #ifdef ENABLE_CHECKING
658 verify_dominators (CDI_DOMINATORS);
663 changed |= cleanup_tree_cfg_1 ();
665 gcc_assert (dom_info_available_p (CDI_DOMINATORS));
668 #ifdef ENABLE_CHECKING
672 timevar_pop (TV_TREE_CLEANUP_CFG);
674 if (changed && current_loops)
675 loops_state_set (LOOPS_NEED_FIXUP);
680 /* Repairs loop structures. */
683 repair_loop_structures (void)
685 bitmap changed_bbs = BITMAP_ALLOC (NULL);
686 fix_loop_structure (changed_bbs);
688 /* This usually does nothing. But sometimes parts of cfg that originally
689 were inside a loop get out of it due to edge removal (since they
690 become unreachable by back edges from latch). */
691 if (loops_state_satisfies_p (LOOP_CLOSED_SSA))
692 rewrite_into_loop_closed_ssa (changed_bbs, TODO_update_ssa);
694 BITMAP_FREE (changed_bbs);
696 #ifdef ENABLE_CHECKING
697 verify_loop_structure ();
701 loops_state_clear (LOOPS_NEED_FIXUP);
704 /* Cleanup cfg and repair loop structures. */
707 cleanup_tree_cfg (void)
709 bool changed = cleanup_tree_cfg_noloop ();
711 if (current_loops != NULL
712 && loops_state_satisfies_p (LOOPS_NEED_FIXUP))
713 repair_loop_structures ();
718 /* Merge the PHI nodes at BB into those at BB's sole successor. */
721 remove_forwarder_block_with_phi (basic_block bb)
723 edge succ = single_succ_edge (bb);
724 basic_block dest = succ->dest;
726 basic_block dombb, domdest, dom;
728 /* We check for infinite loops already in tree_forwarder_block_p.
729 However it may happen that the infinite loop is created
730 afterwards due to removal of forwarders. */
734 /* If the destination block consists of a nonlocal label, do not
736 label = first_stmt (dest);
738 && gimple_code (label) == GIMPLE_LABEL
739 && DECL_NONLOCAL (gimple_label_label (label)))
742 /* Redirect each incoming edge to BB to DEST. */
743 while (EDGE_COUNT (bb->preds) > 0)
745 edge e = EDGE_PRED (bb, 0), s;
746 gimple_stmt_iterator gsi;
748 s = find_edge (e->src, dest);
751 /* We already have an edge S from E->src to DEST. If S and
752 E->dest's sole successor edge have the same PHI arguments
753 at DEST, redirect S to DEST. */
754 if (phi_alternatives_equal (dest, s, succ))
756 e = redirect_edge_and_branch (e, dest);
757 redirect_edge_var_map_clear (e);
761 /* PHI arguments are different. Create a forwarder block by
762 splitting E so that we can merge PHI arguments on E to
764 e = single_succ_edge (split_edge (e));
767 s = redirect_edge_and_branch (e, dest);
769 /* redirect_edge_and_branch must not create a new edge. */
772 /* Add to the PHI nodes at DEST each PHI argument removed at the
774 for (gsi = gsi_start_phis (dest);
778 gimple phi = gsi_stmt (gsi);
779 tree def = gimple_phi_arg_def (phi, succ->dest_idx);
780 source_location locus = gimple_phi_arg_location_from_edge (phi, succ);
782 if (TREE_CODE (def) == SSA_NAME)
784 edge_var_map_vector head;
788 /* If DEF is one of the results of PHI nodes removed during
789 redirection, replace it with the PHI argument that used
791 head = redirect_edge_var_map_vector (e);
792 for (i = 0; VEC_iterate (edge_var_map, head, i, vm); ++i)
794 tree old_arg = redirect_edge_var_map_result (vm);
795 tree new_arg = redirect_edge_var_map_def (vm);
800 locus = redirect_edge_var_map_location (vm);
806 add_phi_arg (phi, def, s, locus);
809 redirect_edge_var_map_clear (e);
812 /* Update the dominators. */
813 dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
814 domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
817 /* Shortcut to avoid calling (relatively expensive)
818 nearest_common_dominator unless necessary. */
822 dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
824 set_immediate_dominator (CDI_DOMINATORS, dest, dom);
826 /* Remove BB since all of BB's incoming edges have been redirected
828 delete_basic_block (bb);
831 /* This pass merges PHI nodes if one feeds into another. For example,
832 suppose we have the following:
839 # tem_6 = PHI <tem_17(8), tem_23(7)>;
842 # tem_3 = PHI <tem_6(9), tem_2(5)>;
845 Then we merge the first PHI node into the second one like so:
852 # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
857 merge_phi_nodes (void)
859 basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks);
860 basic_block *current = worklist;
863 calculate_dominance_info (CDI_DOMINATORS);
865 /* Find all PHI nodes that we may be able to merge. */
870 /* Look for a forwarder block with PHI nodes. */
871 if (!tree_forwarder_block_p (bb, true))
874 dest = single_succ (bb);
876 /* We have to feed into another basic block with PHI
878 if (gimple_seq_empty_p (phi_nodes (dest))
879 /* We don't want to deal with a basic block with
881 || has_abnormal_incoming_edge_p (bb))
884 if (!dominated_by_p (CDI_DOMINATORS, dest, bb))
886 /* If BB does not dominate DEST, then the PHI nodes at
887 DEST must be the only users of the results of the PHI
893 gimple_stmt_iterator gsi;
894 unsigned int dest_idx = single_succ_edge (bb)->dest_idx;
896 /* BB dominates DEST. There may be many users of the PHI
897 nodes in BB. However, there is still a trivial case we
898 can handle. If the result of every PHI in BB is used
899 only by a PHI in DEST, then we can trivially merge the
900 PHI nodes from BB into DEST. */
901 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
904 gimple phi = gsi_stmt (gsi);
905 tree result = gimple_phi_result (phi);
906 use_operand_p imm_use;
909 /* If the PHI's result is never used, then we can just
911 if (has_zero_uses (result))
914 /* Get the single use of the result of this PHI node. */
915 if (!single_imm_use (result, &imm_use, &use_stmt)
916 || gimple_code (use_stmt) != GIMPLE_PHI
917 || gimple_bb (use_stmt) != dest
918 || gimple_phi_arg_def (use_stmt, dest_idx) != result)
922 /* If the loop above iterated through all the PHI nodes
923 in BB, then we can merge the PHIs from BB into DEST. */
929 /* Now let's drain WORKLIST. */
930 while (current != worklist)
933 remove_forwarder_block_with_phi (bb);
941 gate_merge_phi (void)
946 struct gimple_opt_pass pass_merge_phi =
950 "mergephi", /* name */
951 gate_merge_phi, /* gate */
952 merge_phi_nodes, /* execute */
955 0, /* static_pass_number */
956 TV_TREE_MERGE_PHI, /* tv_id */
957 PROP_cfg | PROP_ssa, /* properties_required */
958 0, /* properties_provided */
959 0, /* properties_destroyed */
960 0, /* todo_flags_start */
961 TODO_dump_func | TODO_ggc_collect /* todo_flags_finish */