1 /* CFG cleanup for trees.
2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008
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 /* Now walk through the statements backward. We can ignore labels,
243 anything else means this is not a forwarder block. */
244 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
246 gimple stmt
= gsi_stmt (gsi
);
248 switch (gimple_code (stmt
))
251 if (DECL_NONLOCAL (gimple_label_label (stmt
)))
260 if (find_edge (ENTRY_BLOCK_PTR
, bb
))
266 /* Protect loop latches, headers and preheaders. */
267 if (bb
->loop_father
->header
== bb
)
269 dest
= EDGE_SUCC (bb
, 0)->dest
;
271 if (dest
->loop_father
->header
== dest
)
277 /* Return true if BB has at least one abnormal incoming edge. */
280 has_abnormal_incoming_edge_p (basic_block bb
)
285 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
286 if (e
->flags
& EDGE_ABNORMAL
)
292 /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
293 those alternatives are equal in each of the PHI nodes, then return
294 true, else return false. */
297 phi_alternatives_equal (basic_block dest
, edge e1
, edge e2
)
299 int n1
= e1
->dest_idx
;
300 int n2
= e2
->dest_idx
;
301 gimple_stmt_iterator gsi
;
303 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
305 gimple phi
= gsi_stmt (gsi
);
306 tree val1
= gimple_phi_arg_def (phi
, n1
);
307 tree val2
= gimple_phi_arg_def (phi
, n2
);
309 gcc_assert (val1
!= NULL_TREE
);
310 gcc_assert (val2
!= NULL_TREE
);
312 if (!operand_equal_for_phi_arg_p (val1
, val2
))
319 /* Removes forwarder block BB. Returns false if this failed. */
322 remove_forwarder_block (basic_block bb
)
324 edge succ
= single_succ_edge (bb
), e
, s
;
325 basic_block dest
= succ
->dest
;
328 gimple_stmt_iterator gsi
, gsi_to
;
329 bool seen_abnormal_edge
= false;
331 /* We check for infinite loops already in tree_forwarder_block_p.
332 However it may happen that the infinite loop is created
333 afterwards due to removal of forwarders. */
337 /* If the destination block consists of a nonlocal label, do not merge
339 label
= first_stmt (dest
);
341 && gimple_code (label
) == GIMPLE_LABEL
342 && DECL_NONLOCAL (gimple_label_label (label
)))
345 /* If there is an abnormal edge to basic block BB, but not into
346 dest, problems might occur during removal of the phi node at out
347 of ssa due to overlapping live ranges of registers.
349 If there is an abnormal edge in DEST, the problems would occur
350 anyway since cleanup_dead_labels would then merge the labels for
351 two different eh regions, and rest of exception handling code
354 So if there is an abnormal edge to BB, proceed only if there is
355 no abnormal edge to DEST and there are no phi nodes in DEST. */
356 if (has_abnormal_incoming_edge_p (bb
))
358 seen_abnormal_edge
= true;
360 if (has_abnormal_incoming_edge_p (dest
)
361 || !gimple_seq_empty_p (phi_nodes (dest
)))
365 /* If there are phi nodes in DEST, and some of the blocks that are
366 predecessors of BB are also predecessors of DEST, check that the
367 phi node arguments match. */
368 if (!gimple_seq_empty_p (phi_nodes (dest
)))
370 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
372 s
= find_edge (e
->src
, dest
);
376 if (!phi_alternatives_equal (dest
, succ
, s
))
381 /* Redirect the edges. */
382 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
384 bitmap_set_bit (cfgcleanup_altered_bbs
, e
->src
->index
);
386 if (e
->flags
& EDGE_ABNORMAL
)
388 /* If there is an abnormal edge, redirect it anyway, and
389 move the labels to the new block to make it legal. */
390 s
= redirect_edge_succ_nodup (e
, dest
);
393 s
= redirect_edge_and_branch (e
, dest
);
397 /* Create arguments for the phi nodes, since the edge was not
399 for (gsi
= gsi_start_phis (dest
);
403 gimple phi
= gsi_stmt (gsi
);
404 add_phi_arg (phi
, gimple_phi_arg_def (phi
, succ
->dest_idx
), s
);
409 if (seen_abnormal_edge
)
411 /* Move the labels to the new block, so that the redirection of
412 the abnormal edges works. */
413 gsi_to
= gsi_start_bb (dest
);
414 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
416 label
= gsi_stmt (gsi
);
417 gcc_assert (gimple_code (label
) == GIMPLE_LABEL
);
418 gsi_remove (&gsi
, false);
419 gsi_insert_before (&gsi_to
, label
, GSI_CONTINUE_LINKING
);
423 bitmap_set_bit (cfgcleanup_altered_bbs
, dest
->index
);
425 /* Update the dominators. */
426 if (dom_info_available_p (CDI_DOMINATORS
))
428 basic_block dom
, dombb
, domdest
;
430 dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
431 domdest
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
434 /* Shortcut to avoid calling (relatively expensive)
435 nearest_common_dominator unless necessary. */
439 dom
= nearest_common_dominator (CDI_DOMINATORS
, domdest
, dombb
);
441 set_immediate_dominator (CDI_DOMINATORS
, dest
, dom
);
444 /* And kill the forwarder block. */
445 delete_basic_block (bb
);
450 /* Split basic blocks on calls in the middle of a basic block that are now
451 known not to return, and remove the unreachable code. */
454 split_bbs_on_noreturn_calls (void)
456 bool changed
= false;
460 /* Detect cases where a mid-block call is now known not to return. */
462 while (VEC_length (gimple
, MODIFIED_NORETURN_CALLS (cfun
)))
464 stmt
= VEC_pop (gimple
, MODIFIED_NORETURN_CALLS (cfun
));
465 bb
= gimple_bb (stmt
);
466 /* BB might be deleted at this point, so verify first
467 BB is present in the cfg. */
469 || bb
->index
< NUM_FIXED_BLOCKS
470 || bb
->index
>= n_basic_blocks
471 || BASIC_BLOCK (bb
->index
) != bb
472 || last_stmt (bb
) == stmt
473 || !gimple_call_noreturn_p (stmt
))
477 split_block (bb
, stmt
);
478 remove_fallthru_edge (bb
->succs
);
484 /* If GIMPLE_OMP_RETURN in basic block BB is unreachable, remove it. */
487 cleanup_omp_return (basic_block bb
)
489 gimple stmt
= last_stmt (bb
);
490 basic_block control_bb
;
493 || gimple_code (stmt
) != GIMPLE_OMP_RETURN
494 || !single_pred_p (bb
))
497 control_bb
= single_pred (bb
);
498 stmt
= last_stmt (control_bb
);
500 if (gimple_code (stmt
) != GIMPLE_OMP_SECTIONS_SWITCH
)
503 /* The block with the control statement normally has two entry edges -- one
504 from entry, one from continue. If continue is removed, return is
505 unreachable, so we remove it here as well. */
506 if (EDGE_COUNT (control_bb
->preds
) == 2)
509 gcc_assert (EDGE_COUNT (control_bb
->preds
) == 1);
510 remove_edge_and_dominated_blocks (single_pred_edge (bb
));
514 /* Tries to cleanup cfg in basic block BB. Returns true if anything
518 cleanup_tree_cfg_bb (basic_block bb
)
522 if (cleanup_omp_return (bb
))
525 retval
= cleanup_control_flow_bb (bb
);
527 /* Forwarder blocks can carry line number information which is
528 useful when debugging, so we only clean them up when
531 && tree_forwarder_block_p (bb
, false)
532 && remove_forwarder_block (bb
))
535 /* Merging the blocks may create new opportunities for folding
536 conditional branches (due to the elimination of single-valued PHI
538 if (single_succ_p (bb
)
539 && can_merge_blocks_p (bb
, single_succ (bb
)))
541 merge_blocks (bb
, single_succ (bb
));
548 /* Iterate the cfg cleanups, while anything changes. */
551 cleanup_tree_cfg_1 (void)
557 retval
|= split_bbs_on_noreturn_calls ();
559 /* Prepare the worklists of altered blocks. */
560 cfgcleanup_altered_bbs
= BITMAP_ALLOC (NULL
);
562 /* During forwarder block cleanup, we may redirect edges out of
563 SWITCH_EXPRs, which can get expensive. So we want to enable
564 recording of edge to CASE_LABEL_EXPR. */
565 start_recording_case_labels ();
567 /* Start by iterating over all basic blocks. We cannot use FOR_EACH_BB,
568 since the basic blocks may get removed. */
569 n
= last_basic_block
;
570 for (i
= NUM_FIXED_BLOCKS
; i
< n
; i
++)
572 bb
= BASIC_BLOCK (i
);
574 retval
|= cleanup_tree_cfg_bb (bb
);
577 /* Now process the altered blocks, as long as any are available. */
578 while (!bitmap_empty_p (cfgcleanup_altered_bbs
))
580 i
= bitmap_first_set_bit (cfgcleanup_altered_bbs
);
581 bitmap_clear_bit (cfgcleanup_altered_bbs
, i
);
582 if (i
< NUM_FIXED_BLOCKS
)
585 bb
= BASIC_BLOCK (i
);
589 retval
|= cleanup_tree_cfg_bb (bb
);
591 /* Rerun split_bbs_on_noreturn_calls, in case we have altered any noreturn
593 retval
|= split_bbs_on_noreturn_calls ();
596 end_recording_case_labels ();
597 BITMAP_FREE (cfgcleanup_altered_bbs
);
602 /* Remove unreachable blocks and other miscellaneous clean up work.
603 Return true if the flowgraph was modified, false otherwise. */
606 cleanup_tree_cfg_noloop (void)
610 timevar_push (TV_TREE_CLEANUP_CFG
);
612 /* Iterate until there are no more cleanups left to do. If any
613 iteration changed the flowgraph, set CHANGED to true.
615 If dominance information is available, there cannot be any unreachable
617 if (!dom_info_available_p (CDI_DOMINATORS
))
619 changed
= delete_unreachable_blocks ();
620 calculate_dominance_info (CDI_DOMINATORS
);
624 #ifdef ENABLE_CHECKING
625 verify_dominators (CDI_DOMINATORS
);
630 changed
|= cleanup_tree_cfg_1 ();
632 gcc_assert (dom_info_available_p (CDI_DOMINATORS
));
635 #ifdef ENABLE_CHECKING
639 timevar_pop (TV_TREE_CLEANUP_CFG
);
641 if (changed
&& current_loops
)
642 loops_state_set (LOOPS_NEED_FIXUP
);
647 /* Repairs loop structures. */
650 repair_loop_structures (void)
652 bitmap changed_bbs
= BITMAP_ALLOC (NULL
);
653 fix_loop_structure (changed_bbs
);
655 /* This usually does nothing. But sometimes parts of cfg that originally
656 were inside a loop get out of it due to edge removal (since they
657 become unreachable by back edges from latch). */
658 if (loops_state_satisfies_p (LOOP_CLOSED_SSA
))
659 rewrite_into_loop_closed_ssa (changed_bbs
, TODO_update_ssa
);
661 BITMAP_FREE (changed_bbs
);
663 #ifdef ENABLE_CHECKING
664 verify_loop_structure ();
668 loops_state_clear (LOOPS_NEED_FIXUP
);
671 /* Cleanup cfg and repair loop structures. */
674 cleanup_tree_cfg (void)
676 bool changed
= cleanup_tree_cfg_noloop ();
678 if (current_loops
!= NULL
679 && loops_state_satisfies_p (LOOPS_NEED_FIXUP
))
680 repair_loop_structures ();
685 /* Merge the PHI nodes at BB into those at BB's sole successor. */
688 remove_forwarder_block_with_phi (basic_block bb
)
690 edge succ
= single_succ_edge (bb
);
691 basic_block dest
= succ
->dest
;
693 basic_block dombb
, domdest
, dom
;
695 /* We check for infinite loops already in tree_forwarder_block_p.
696 However it may happen that the infinite loop is created
697 afterwards due to removal of forwarders. */
701 /* If the destination block consists of a nonlocal label, do not
703 label
= first_stmt (dest
);
705 && gimple_code (label
) == GIMPLE_LABEL
706 && DECL_NONLOCAL (gimple_label_label (label
)))
709 /* Redirect each incoming edge to BB to DEST. */
710 while (EDGE_COUNT (bb
->preds
) > 0)
712 edge e
= EDGE_PRED (bb
, 0), s
;
713 gimple_stmt_iterator gsi
;
715 s
= find_edge (e
->src
, dest
);
718 /* We already have an edge S from E->src to DEST. If S and
719 E->dest's sole successor edge have the same PHI arguments
720 at DEST, redirect S to DEST. */
721 if (phi_alternatives_equal (dest
, s
, succ
))
723 e
= redirect_edge_and_branch (e
, dest
);
724 redirect_edge_var_map_clear (e
);
728 /* PHI arguments are different. Create a forwarder block by
729 splitting E so that we can merge PHI arguments on E to
731 e
= single_succ_edge (split_edge (e
));
734 s
= redirect_edge_and_branch (e
, dest
);
736 /* redirect_edge_and_branch must not create a new edge. */
739 /* Add to the PHI nodes at DEST each PHI argument removed at the
741 for (gsi
= gsi_start_phis (dest
);
745 gimple phi
= gsi_stmt (gsi
);
746 tree def
= gimple_phi_arg_def (phi
, succ
->dest_idx
);
748 if (TREE_CODE (def
) == SSA_NAME
)
750 edge_var_map_vector head
;
754 /* If DEF is one of the results of PHI nodes removed during
755 redirection, replace it with the PHI argument that used
757 head
= redirect_edge_var_map_vector (e
);
758 for (i
= 0; VEC_iterate (edge_var_map
, head
, i
, vm
); ++i
)
760 tree old_arg
= redirect_edge_var_map_result (vm
);
761 tree new_arg
= redirect_edge_var_map_def (vm
);
771 add_phi_arg (phi
, def
, s
);
774 redirect_edge_var_map_clear (e
);
777 /* Update the dominators. */
778 dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
779 domdest
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
782 /* Shortcut to avoid calling (relatively expensive)
783 nearest_common_dominator unless necessary. */
787 dom
= nearest_common_dominator (CDI_DOMINATORS
, domdest
, dombb
);
789 set_immediate_dominator (CDI_DOMINATORS
, dest
, dom
);
791 /* Remove BB since all of BB's incoming edges have been redirected
793 delete_basic_block (bb
);
796 /* This pass merges PHI nodes if one feeds into another. For example,
797 suppose we have the following:
804 # tem_6 = PHI <tem_17(8), tem_23(7)>;
807 # tem_3 = PHI <tem_6(9), tem_2(5)>;
810 Then we merge the first PHI node into the second one like so:
817 # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
822 merge_phi_nodes (void)
824 basic_block
*worklist
= XNEWVEC (basic_block
, n_basic_blocks
);
825 basic_block
*current
= worklist
;
828 calculate_dominance_info (CDI_DOMINATORS
);
830 /* Find all PHI nodes that we may be able to merge. */
835 /* Look for a forwarder block with PHI nodes. */
836 if (!tree_forwarder_block_p (bb
, true))
839 dest
= single_succ (bb
);
841 /* We have to feed into another basic block with PHI
843 if (!phi_nodes (dest
)
844 /* We don't want to deal with a basic block with
846 || has_abnormal_incoming_edge_p (bb
))
849 if (!dominated_by_p (CDI_DOMINATORS
, dest
, bb
))
851 /* If BB does not dominate DEST, then the PHI nodes at
852 DEST must be the only users of the results of the PHI
858 gimple_stmt_iterator gsi
;
859 unsigned int dest_idx
= single_succ_edge (bb
)->dest_idx
;
861 /* BB dominates DEST. There may be many users of the PHI
862 nodes in BB. However, there is still a trivial case we
863 can handle. If the result of every PHI in BB is used
864 only by a PHI in DEST, then we can trivially merge the
865 PHI nodes from BB into DEST. */
866 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
869 gimple phi
= gsi_stmt (gsi
);
870 tree result
= gimple_phi_result (phi
);
871 use_operand_p imm_use
;
874 /* If the PHI's result is never used, then we can just
876 if (has_zero_uses (result
))
879 /* Get the single use of the result of this PHI node. */
880 if (!single_imm_use (result
, &imm_use
, &use_stmt
)
881 || gimple_code (use_stmt
) != GIMPLE_PHI
882 || gimple_bb (use_stmt
) != dest
883 || gimple_phi_arg_def (use_stmt
, dest_idx
) != result
)
887 /* If the loop above iterated through all the PHI nodes
888 in BB, then we can merge the PHIs from BB into DEST. */
894 /* Now let's drain WORKLIST. */
895 while (current
!= worklist
)
898 remove_forwarder_block_with_phi (bb
);
906 gate_merge_phi (void)
911 struct gimple_opt_pass pass_merge_phi
=
915 "mergephi", /* name */
916 gate_merge_phi
, /* gate */
917 merge_phi_nodes
, /* execute */
920 0, /* static_pass_number */
921 TV_TREE_MERGE_PHI
, /* tv_id */
922 PROP_cfg
| PROP_ssa
, /* properties_required */
923 0, /* properties_provided */
924 0, /* properties_destroyed */
925 0, /* todo_flags_start */
926 TODO_dump_func
| TODO_ggc_collect
/* todo_flags_finish */