1 /* CFG cleanup for trees.
2 Copyright (C) 2001-2014 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)
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/>. */
22 #include "coretypes.h"
26 #include "basic-block.h"
27 #include "diagnostic-core.h"
33 #include "hard-reg-set.h"
36 #include "langhooks.h"
37 #include "tree-ssa-alias.h"
38 #include "internal-fn.h"
40 #include "gimple-expr.h"
44 #include "gimple-iterator.h"
45 #include "gimple-ssa.h"
47 #include "tree-phinodes.h"
48 #include "ssa-iterators.h"
49 #include "stringpool.h"
50 #include "tree-ssanames.h"
51 #include "tree-ssa-loop-manip.h"
55 #include "tree-pass.h"
58 #include "tree-ssa-propagate.h"
59 #include "tree-scalar-evolution.h"
61 /* The set of blocks in that at least one of the following changes happened:
62 -- the statement at the end of the block was changed
63 -- the block was newly created
64 -- the set of the predecessors of the block changed
65 -- the set of the successors of the block changed
66 ??? Maybe we could track these changes separately, since they determine
67 what cleanups it makes sense to try on the block. */
68 bitmap cfgcleanup_altered_bbs
;
70 /* Remove any fallthru edge from EV. Return true if an edge was removed. */
73 remove_fallthru_edge (vec
<edge
, va_gc
> *ev
)
78 FOR_EACH_EDGE (e
, ei
, ev
)
79 if ((e
->flags
& EDGE_FALLTHRU
) != 0)
81 if (e
->flags
& EDGE_COMPLEX
)
82 e
->flags
&= ~EDGE_FALLTHRU
;
84 remove_edge_and_dominated_blocks (e
);
91 /* Disconnect an unreachable block in the control expression starting
95 cleanup_control_expr_graph (basic_block bb
, gimple_stmt_iterator gsi
)
99 gimple stmt
= gsi_stmt (gsi
);
102 if (!single_succ_p (bb
))
109 fold_defer_overflow_warnings ();
110 loc
= gimple_location (stmt
);
111 switch (gimple_code (stmt
))
114 val
= fold_binary_loc (loc
, gimple_cond_code (stmt
),
116 gimple_cond_lhs (stmt
),
117 gimple_cond_rhs (stmt
));
121 val
= gimple_switch_index (stmt
);
127 taken_edge
= find_taken_edge (bb
, val
);
130 fold_undefer_and_ignore_overflow_warnings ();
134 /* Remove all the edges except the one that is always executed. */
136 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
142 fold_undefer_overflow_warnings
143 (true, stmt
, WARN_STRICT_OVERFLOW_CONDITIONAL
);
147 taken_edge
->probability
+= e
->probability
;
148 taken_edge
->count
+= e
->count
;
149 remove_edge_and_dominated_blocks (e
);
156 fold_undefer_and_ignore_overflow_warnings ();
157 if (taken_edge
->probability
> REG_BR_PROB_BASE
)
158 taken_edge
->probability
= REG_BR_PROB_BASE
;
161 taken_edge
= single_succ_edge (bb
);
163 bitmap_set_bit (cfgcleanup_altered_bbs
, bb
->index
);
164 gsi_remove (&gsi
, true);
165 taken_edge
->flags
= EDGE_FALLTHRU
;
170 /* Cleanup the GF_CALL_CTRL_ALTERING flag according to
171 to updated gimple_call_flags. */
174 cleanup_call_ctrl_altering_flag (gimple bb_end
)
176 if (!is_gimple_call (bb_end
)
177 || !gimple_call_ctrl_altering_p (bb_end
))
180 int flags
= gimple_call_flags (bb_end
);
181 if (((flags
& (ECF_CONST
| ECF_PURE
))
182 && !(flags
& ECF_LOOPING_CONST_OR_PURE
))
183 || (flags
& ECF_LEAF
))
184 gimple_call_set_ctrl_altering (bb_end
, false);
187 /* Try to remove superfluous control structures in basic block BB. Returns
188 true if anything changes. */
191 cleanup_control_flow_bb (basic_block bb
)
193 gimple_stmt_iterator gsi
;
197 /* If the last statement of the block could throw and now cannot,
198 we need to prune cfg. */
199 retval
|= gimple_purge_dead_eh_edges (bb
);
201 gsi
= gsi_last_bb (bb
);
205 stmt
= gsi_stmt (gsi
);
207 /* Try to cleanup ctrl altering flag for call which ends bb. */
208 cleanup_call_ctrl_altering_flag (stmt
);
210 if (gimple_code (stmt
) == GIMPLE_COND
211 || gimple_code (stmt
) == GIMPLE_SWITCH
)
212 retval
|= cleanup_control_expr_graph (bb
, gsi
);
213 else if (gimple_code (stmt
) == GIMPLE_GOTO
214 && TREE_CODE (gimple_goto_dest (stmt
)) == ADDR_EXPR
215 && (TREE_CODE (TREE_OPERAND (gimple_goto_dest (stmt
), 0))
218 /* If we had a computed goto which has a compile-time determinable
219 destination, then we can eliminate the goto. */
223 basic_block target_block
;
225 /* First look at all the outgoing edges. Delete any outgoing
226 edges which do not go to the right block. For the one
227 edge which goes to the right block, fix up its flags. */
228 label
= TREE_OPERAND (gimple_goto_dest (stmt
), 0);
229 target_block
= label_to_block (label
);
230 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
232 if (e
->dest
!= target_block
)
233 remove_edge_and_dominated_blocks (e
);
236 /* Turn off the EDGE_ABNORMAL flag. */
237 e
->flags
&= ~EDGE_ABNORMAL
;
239 /* And set EDGE_FALLTHRU. */
240 e
->flags
|= EDGE_FALLTHRU
;
245 bitmap_set_bit (cfgcleanup_altered_bbs
, bb
->index
);
246 bitmap_set_bit (cfgcleanup_altered_bbs
, target_block
->index
);
248 /* Remove the GOTO_EXPR as it is not needed. The CFG has all the
249 relevant information we need. */
250 gsi_remove (&gsi
, true);
254 /* Check for indirect calls that have been turned into
256 else if (is_gimple_call (stmt
)
257 && gimple_call_noreturn_p (stmt
)
258 && remove_fallthru_edge (bb
->succs
))
264 /* Return true if basic block BB does nothing except pass control
265 flow to another block and that we can safely insert a label at
266 the start of the successor block.
268 As a precondition, we require that BB be not equal to
272 tree_forwarder_block_p (basic_block bb
, bool phi_wanted
)
274 gimple_stmt_iterator gsi
;
277 /* BB must have a single outgoing edge. */
278 if (single_succ_p (bb
) != 1
279 /* If PHI_WANTED is false, BB must not have any PHI nodes.
280 Otherwise, BB must have PHI nodes. */
281 || gimple_seq_empty_p (phi_nodes (bb
)) == phi_wanted
282 /* BB may not be a predecessor of the exit block. */
283 || single_succ (bb
) == EXIT_BLOCK_PTR_FOR_FN (cfun
)
284 /* Nor should this be an infinite loop. */
285 || single_succ (bb
) == bb
286 /* BB may not have an abnormal outgoing edge. */
287 || (single_succ_edge (bb
)->flags
& EDGE_ABNORMAL
))
290 gcc_checking_assert (bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
));
292 locus
= single_succ_edge (bb
)->goto_locus
;
294 /* There should not be an edge coming from entry, or an EH edge. */
299 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
300 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) || (e
->flags
& EDGE_EH
))
302 /* If goto_locus of any of the edges differs, prevent removing
303 the forwarder block for -O0. */
304 else if (optimize
== 0 && e
->goto_locus
!= locus
)
308 /* Now walk through the statements backward. We can ignore labels,
309 anything else means this is not a forwarder block. */
310 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
312 gimple stmt
= gsi_stmt (gsi
);
314 switch (gimple_code (stmt
))
317 if (DECL_NONLOCAL (gimple_label_label (stmt
)))
319 if (optimize
== 0 && gimple_location (stmt
) != locus
)
323 /* ??? For now, hope there's a corresponding debug
324 assignment at the destination. */
336 /* Protect loop headers. */
337 if (bb
->loop_father
->header
== bb
)
340 dest
= EDGE_SUCC (bb
, 0)->dest
;
341 /* Protect loop preheaders and latches if requested. */
342 if (dest
->loop_father
->header
== dest
)
344 if (bb
->loop_father
== dest
->loop_father
)
346 if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES
))
348 /* If bb doesn't have a single predecessor we'd make this
349 loop have multiple latches. Don't do that if that
350 would in turn require disambiguating them. */
351 return (single_pred_p (bb
)
352 || loops_state_satisfies_p
353 (LOOPS_MAY_HAVE_MULTIPLE_LATCHES
));
355 else if (bb
->loop_father
== loop_outer (dest
->loop_father
))
356 return !loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS
);
357 /* Always preserve other edges into loop headers that are
358 not simple latches or preheaders. */
366 /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
367 those alternatives are equal in each of the PHI nodes, then return
368 true, else return false. */
371 phi_alternatives_equal (basic_block dest
, edge e1
, edge e2
)
373 int n1
= e1
->dest_idx
;
374 int n2
= e2
->dest_idx
;
375 gimple_stmt_iterator gsi
;
377 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
379 gimple phi
= gsi_stmt (gsi
);
380 tree val1
= gimple_phi_arg_def (phi
, n1
);
381 tree val2
= gimple_phi_arg_def (phi
, n2
);
383 gcc_assert (val1
!= NULL_TREE
);
384 gcc_assert (val2
!= NULL_TREE
);
386 if (!operand_equal_for_phi_arg_p (val1
, val2
))
393 /* Removes forwarder block BB. Returns false if this failed. */
396 remove_forwarder_block (basic_block bb
)
398 edge succ
= single_succ_edge (bb
), e
, s
;
399 basic_block dest
= succ
->dest
;
402 gimple_stmt_iterator gsi
, gsi_to
;
403 bool can_move_debug_stmts
;
405 /* We check for infinite loops already in tree_forwarder_block_p.
406 However it may happen that the infinite loop is created
407 afterwards due to removal of forwarders. */
411 /* If the destination block consists of a nonlocal label or is a
412 EH landing pad, do not merge it. */
413 label
= first_stmt (dest
);
415 && gimple_code (label
) == GIMPLE_LABEL
416 && (DECL_NONLOCAL (gimple_label_label (label
))
417 || EH_LANDING_PAD_NR (gimple_label_label (label
)) != 0))
420 /* If there is an abnormal edge to basic block BB, but not into
421 dest, problems might occur during removal of the phi node at out
422 of ssa due to overlapping live ranges of registers.
424 If there is an abnormal edge in DEST, the problems would occur
425 anyway since cleanup_dead_labels would then merge the labels for
426 two different eh regions, and rest of exception handling code
429 So if there is an abnormal edge to BB, proceed only if there is
430 no abnormal edge to DEST and there are no phi nodes in DEST. */
431 if (bb_has_abnormal_pred (bb
)
432 && (bb_has_abnormal_pred (dest
)
433 || !gimple_seq_empty_p (phi_nodes (dest
))))
436 /* If there are phi nodes in DEST, and some of the blocks that are
437 predecessors of BB are also predecessors of DEST, check that the
438 phi node arguments match. */
439 if (!gimple_seq_empty_p (phi_nodes (dest
)))
441 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
443 s
= find_edge (e
->src
, dest
);
447 if (!phi_alternatives_equal (dest
, succ
, s
))
452 can_move_debug_stmts
= MAY_HAVE_DEBUG_STMTS
&& single_pred_p (dest
);
454 basic_block pred
= NULL
;
455 if (single_pred_p (bb
))
456 pred
= single_pred (bb
);
458 /* Redirect the edges. */
459 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
461 bitmap_set_bit (cfgcleanup_altered_bbs
, e
->src
->index
);
463 if (e
->flags
& EDGE_ABNORMAL
)
465 /* If there is an abnormal edge, redirect it anyway, and
466 move the labels to the new block to make it legal. */
467 s
= redirect_edge_succ_nodup (e
, dest
);
470 s
= redirect_edge_and_branch (e
, dest
);
474 /* Create arguments for the phi nodes, since the edge was not
476 for (gsi
= gsi_start_phis (dest
);
480 gimple phi
= gsi_stmt (gsi
);
481 source_location l
= gimple_phi_arg_location_from_edge (phi
, succ
);
482 tree def
= gimple_phi_arg_def (phi
, succ
->dest_idx
);
483 add_phi_arg (phi
, unshare_expr (def
), s
, l
);
488 /* Move nonlocal labels and computed goto targets as well as user
489 defined labels and labels with an EH landing pad number to the
490 new block, so that the redirection of the abnormal edges works,
491 jump targets end up in a sane place and debug information for
492 labels is retained. */
493 gsi_to
= gsi_start_bb (dest
);
494 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
497 label
= gsi_stmt (gsi
);
498 if (is_gimple_debug (label
))
500 decl
= gimple_label_label (label
);
501 if (EH_LANDING_PAD_NR (decl
) != 0
502 || DECL_NONLOCAL (decl
)
503 || FORCED_LABEL (decl
)
504 || !DECL_ARTIFICIAL (decl
))
506 gsi_remove (&gsi
, false);
507 gsi_insert_before (&gsi_to
, label
, GSI_SAME_STMT
);
513 /* Move debug statements if the destination has a single predecessor. */
514 if (can_move_debug_stmts
)
516 gsi_to
= gsi_after_labels (dest
);
517 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); )
519 gimple debug
= gsi_stmt (gsi
);
520 if (!is_gimple_debug (debug
))
522 gsi_remove (&gsi
, false);
523 gsi_insert_before (&gsi_to
, debug
, GSI_SAME_STMT
);
527 bitmap_set_bit (cfgcleanup_altered_bbs
, dest
->index
);
529 /* Update the dominators. */
530 if (dom_info_available_p (CDI_DOMINATORS
))
532 basic_block dom
, dombb
, domdest
;
534 dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
535 domdest
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
538 /* Shortcut to avoid calling (relatively expensive)
539 nearest_common_dominator unless necessary. */
543 dom
= nearest_common_dominator (CDI_DOMINATORS
, domdest
, dombb
);
545 set_immediate_dominator (CDI_DOMINATORS
, dest
, dom
);
548 /* Adjust latch infomation of BB's parent loop as otherwise
549 the cfg hook has a hard time not to kill the loop. */
550 if (current_loops
&& bb
->loop_father
->latch
== bb
)
551 bb
->loop_father
->latch
= pred
;
553 /* And kill the forwarder block. */
554 delete_basic_block (bb
);
559 /* STMT is a call that has been discovered noreturn. Fixup the CFG
560 and remove LHS. Return true if something changed. */
563 fixup_noreturn_call (gimple stmt
)
565 basic_block bb
= gimple_bb (stmt
);
566 bool changed
= false;
568 if (gimple_call_builtin_p (stmt
, BUILT_IN_RETURN
))
571 /* First split basic block if stmt is not last. */
572 if (stmt
!= gsi_stmt (gsi_last_bb (bb
)))
574 if (stmt
== gsi_stmt (gsi_last_nondebug_bb (bb
)))
576 /* Don't split if there are only debug stmts
577 after stmt, that can result in -fcompare-debug
578 failures. Remove the debug stmts instead,
579 they should be all unreachable anyway. */
580 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
581 for (gsi_next (&gsi
); !gsi_end_p (gsi
); )
582 gsi_remove (&gsi
, true);
585 split_block (bb
, stmt
);
588 changed
|= remove_fallthru_edge (bb
->succs
);
590 /* If there is LHS, remove it. */
591 if (gimple_call_lhs (stmt
))
593 tree op
= gimple_call_lhs (stmt
);
594 gimple_call_set_lhs (stmt
, NULL_TREE
);
596 /* We need to remove SSA name to avoid checking errors.
597 All uses are dominated by the noreturn and thus will
598 be removed afterwards.
599 We proactively remove affected non-PHI statements to avoid
600 fixup_cfg from trying to update them and crashing. */
601 if (TREE_CODE (op
) == SSA_NAME
)
604 imm_use_iterator iter
;
607 unsigned int bb_index
;
609 bitmap blocks
= BITMAP_ALLOC (NULL
);
611 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, op
)
613 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
614 bitmap_set_bit (blocks
, gimple_bb (use_stmt
)->index
);
616 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
617 SET_USE (use_p
, error_mark_node
);
619 EXECUTE_IF_SET_IN_BITMAP (blocks
, 0, bb_index
, bi
)
620 delete_basic_block (BASIC_BLOCK_FOR_FN (cfun
, bb_index
));
621 BITMAP_FREE (blocks
);
622 release_ssa_name (op
);
631 /* Split basic blocks on calls in the middle of a basic block that are now
632 known not to return, and remove the unreachable code. */
635 split_bb_on_noreturn_calls (basic_block bb
)
637 bool changed
= false;
638 gimple_stmt_iterator gsi
;
640 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
642 gimple stmt
= gsi_stmt (gsi
);
644 if (!is_gimple_call (stmt
))
647 if (gimple_call_noreturn_p (stmt
))
648 changed
|= fixup_noreturn_call (stmt
);
652 bitmap_set_bit (cfgcleanup_altered_bbs
, bb
->index
);
656 /* Tries to cleanup cfg in basic block BB. Returns true if anything
660 cleanup_tree_cfg_bb (basic_block bb
)
662 bool retval
= cleanup_control_flow_bb (bb
);
664 if (tree_forwarder_block_p (bb
, false)
665 && remove_forwarder_block (bb
))
668 /* Merging the blocks may create new opportunities for folding
669 conditional branches (due to the elimination of single-valued PHI
671 if (single_succ_p (bb
)
672 && can_merge_blocks_p (bb
, single_succ (bb
)))
674 merge_blocks (bb
, single_succ (bb
));
681 /* Iterate the cfg cleanups, while anything changes. */
684 cleanup_tree_cfg_1 (void)
690 /* Prepare the worklists of altered blocks. */
691 cfgcleanup_altered_bbs
= BITMAP_ALLOC (NULL
);
693 /* During forwarder block cleanup, we may redirect edges out of
694 SWITCH_EXPRs, which can get expensive. So we want to enable
695 recording of edge to CASE_LABEL_EXPR. */
696 start_recording_case_labels ();
698 /* Start by iterating over all basic blocks. We cannot use FOR_EACH_BB_FN,
699 since the basic blocks may get removed. */
700 n
= last_basic_block_for_fn (cfun
);
701 for (i
= NUM_FIXED_BLOCKS
; i
< n
; i
++)
703 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
706 retval
|= cleanup_tree_cfg_bb (bb
);
707 retval
|= split_bb_on_noreturn_calls (bb
);
711 /* Now process the altered blocks, as long as any are available. */
712 while (!bitmap_empty_p (cfgcleanup_altered_bbs
))
714 i
= bitmap_first_set_bit (cfgcleanup_altered_bbs
);
715 bitmap_clear_bit (cfgcleanup_altered_bbs
, i
);
716 if (i
< NUM_FIXED_BLOCKS
)
719 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
723 retval
|= cleanup_tree_cfg_bb (bb
);
725 /* Rerun split_bb_on_noreturn_calls, in case we have altered any noreturn
727 retval
|= split_bb_on_noreturn_calls (bb
);
730 end_recording_case_labels ();
731 BITMAP_FREE (cfgcleanup_altered_bbs
);
736 /* Remove unreachable blocks and other miscellaneous clean up work.
737 Return true if the flowgraph was modified, false otherwise. */
740 cleanup_tree_cfg_noloop (void)
744 timevar_push (TV_TREE_CLEANUP_CFG
);
746 /* Iterate until there are no more cleanups left to do. If any
747 iteration changed the flowgraph, set CHANGED to true.
749 If dominance information is available, there cannot be any unreachable
751 if (!dom_info_available_p (CDI_DOMINATORS
))
753 changed
= delete_unreachable_blocks ();
754 calculate_dominance_info (CDI_DOMINATORS
);
758 #ifdef ENABLE_CHECKING
759 verify_dominators (CDI_DOMINATORS
);
764 changed
|= cleanup_tree_cfg_1 ();
766 gcc_assert (dom_info_available_p (CDI_DOMINATORS
));
769 #ifdef ENABLE_CHECKING
773 timevar_pop (TV_TREE_CLEANUP_CFG
);
775 if (changed
&& current_loops
)
776 loops_state_set (LOOPS_NEED_FIXUP
);
781 /* Repairs loop structures. */
784 repair_loop_structures (void)
787 unsigned n_new_loops
;
789 calculate_dominance_info (CDI_DOMINATORS
);
791 timevar_push (TV_REPAIR_LOOPS
);
792 changed_bbs
= BITMAP_ALLOC (NULL
);
793 n_new_loops
= fix_loop_structure (changed_bbs
);
795 /* This usually does nothing. But sometimes parts of cfg that originally
796 were inside a loop get out of it due to edge removal (since they
797 become unreachable by back edges from latch). Also a former
798 irreducible loop can become reducible - in this case force a full
799 rewrite into loop-closed SSA form. */
800 if (loops_state_satisfies_p (LOOP_CLOSED_SSA
))
801 rewrite_into_loop_closed_ssa (n_new_loops
? NULL
: changed_bbs
,
804 BITMAP_FREE (changed_bbs
);
806 #ifdef ENABLE_CHECKING
807 verify_loop_structure ();
811 timevar_pop (TV_REPAIR_LOOPS
);
814 /* Cleanup cfg and repair loop structures. */
817 cleanup_tree_cfg (void)
819 bool changed
= cleanup_tree_cfg_noloop ();
821 if (current_loops
!= NULL
822 && loops_state_satisfies_p (LOOPS_NEED_FIXUP
))
823 repair_loop_structures ();
828 /* Tries to merge the PHI nodes at BB into those at BB's sole successor.
829 Returns true if successful. */
832 remove_forwarder_block_with_phi (basic_block bb
)
834 edge succ
= single_succ_edge (bb
);
835 basic_block dest
= succ
->dest
;
837 basic_block dombb
, domdest
, dom
;
839 /* We check for infinite loops already in tree_forwarder_block_p.
840 However it may happen that the infinite loop is created
841 afterwards due to removal of forwarders. */
845 /* If the destination block consists of a nonlocal label, do not
847 label
= first_stmt (dest
);
849 && gimple_code (label
) == GIMPLE_LABEL
850 && DECL_NONLOCAL (gimple_label_label (label
)))
853 /* Record BB's single pred in case we need to update the father
854 loop's latch information later. */
855 basic_block pred
= NULL
;
856 if (single_pred_p (bb
))
857 pred
= single_pred (bb
);
859 /* Redirect each incoming edge to BB to DEST. */
860 while (EDGE_COUNT (bb
->preds
) > 0)
862 edge e
= EDGE_PRED (bb
, 0), s
;
863 gimple_stmt_iterator gsi
;
865 s
= find_edge (e
->src
, dest
);
868 /* We already have an edge S from E->src to DEST. If S and
869 E->dest's sole successor edge have the same PHI arguments
870 at DEST, redirect S to DEST. */
871 if (phi_alternatives_equal (dest
, s
, succ
))
873 e
= redirect_edge_and_branch (e
, dest
);
874 redirect_edge_var_map_clear (e
);
878 /* PHI arguments are different. Create a forwarder block by
879 splitting E so that we can merge PHI arguments on E to
881 e
= single_succ_edge (split_edge (e
));
884 s
= redirect_edge_and_branch (e
, dest
);
886 /* redirect_edge_and_branch must not create a new edge. */
889 /* Add to the PHI nodes at DEST each PHI argument removed at the
891 for (gsi
= gsi_start_phis (dest
);
895 gimple phi
= gsi_stmt (gsi
);
896 tree def
= gimple_phi_arg_def (phi
, succ
->dest_idx
);
897 source_location locus
= gimple_phi_arg_location_from_edge (phi
, succ
);
899 if (TREE_CODE (def
) == SSA_NAME
)
901 /* If DEF is one of the results of PHI nodes removed during
902 redirection, replace it with the PHI argument that used
904 vec
<edge_var_map
> *head
= redirect_edge_var_map_vector (e
);
905 size_t length
= head
? head
->length () : 0;
906 for (size_t i
= 0; i
< length
; i
++)
908 edge_var_map
*vm
= &(*head
)[i
];
909 tree old_arg
= redirect_edge_var_map_result (vm
);
910 tree new_arg
= redirect_edge_var_map_def (vm
);
915 locus
= redirect_edge_var_map_location (vm
);
921 add_phi_arg (phi
, def
, s
, locus
);
924 redirect_edge_var_map_clear (e
);
927 /* Update the dominators. */
928 dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
929 domdest
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
932 /* Shortcut to avoid calling (relatively expensive)
933 nearest_common_dominator unless necessary. */
937 dom
= nearest_common_dominator (CDI_DOMINATORS
, domdest
, dombb
);
939 set_immediate_dominator (CDI_DOMINATORS
, dest
, dom
);
941 /* Adjust latch infomation of BB's parent loop as otherwise
942 the cfg hook has a hard time not to kill the loop. */
943 if (current_loops
&& bb
->loop_father
->latch
== bb
)
944 bb
->loop_father
->latch
= pred
;
946 /* Remove BB since all of BB's incoming edges have been redirected
948 delete_basic_block (bb
);
953 /* This pass merges PHI nodes if one feeds into another. For example,
954 suppose we have the following:
961 # tem_6 = PHI <tem_17(8), tem_23(7)>;
964 # tem_3 = PHI <tem_6(9), tem_2(5)>;
967 Then we merge the first PHI node into the second one like so:
974 # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
980 const pass_data pass_data_merge_phi
=
982 GIMPLE_PASS
, /* type */
983 "mergephi", /* name */
984 OPTGROUP_NONE
, /* optinfo_flags */
985 TV_TREE_MERGE_PHI
, /* tv_id */
986 ( PROP_cfg
| PROP_ssa
), /* properties_required */
987 0, /* properties_provided */
988 0, /* properties_destroyed */
989 0, /* todo_flags_start */
990 0, /* todo_flags_finish */
993 class pass_merge_phi
: public gimple_opt_pass
996 pass_merge_phi (gcc::context
*ctxt
)
997 : gimple_opt_pass (pass_data_merge_phi
, ctxt
)
1000 /* opt_pass methods: */
1001 opt_pass
* clone () { return new pass_merge_phi (m_ctxt
); }
1002 virtual unsigned int execute (function
*);
1004 }; // class pass_merge_phi
1007 pass_merge_phi::execute (function
*fun
)
1009 basic_block
*worklist
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (fun
));
1010 basic_block
*current
= worklist
;
1013 calculate_dominance_info (CDI_DOMINATORS
);
1015 /* Find all PHI nodes that we may be able to merge. */
1016 FOR_EACH_BB_FN (bb
, fun
)
1020 /* Look for a forwarder block with PHI nodes. */
1021 if (!tree_forwarder_block_p (bb
, true))
1024 dest
= single_succ (bb
);
1026 /* We have to feed into another basic block with PHI
1028 if (gimple_seq_empty_p (phi_nodes (dest
))
1029 /* We don't want to deal with a basic block with
1031 || bb_has_abnormal_pred (bb
))
1034 if (!dominated_by_p (CDI_DOMINATORS
, dest
, bb
))
1036 /* If BB does not dominate DEST, then the PHI nodes at
1037 DEST must be the only users of the results of the PHI
1043 gimple_stmt_iterator gsi
;
1044 unsigned int dest_idx
= single_succ_edge (bb
)->dest_idx
;
1046 /* BB dominates DEST. There may be many users of the PHI
1047 nodes in BB. However, there is still a trivial case we
1048 can handle. If the result of every PHI in BB is used
1049 only by a PHI in DEST, then we can trivially merge the
1050 PHI nodes from BB into DEST. */
1051 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
1054 gimple phi
= gsi_stmt (gsi
);
1055 tree result
= gimple_phi_result (phi
);
1056 use_operand_p imm_use
;
1059 /* If the PHI's result is never used, then we can just
1061 if (has_zero_uses (result
))
1064 /* Get the single use of the result of this PHI node. */
1065 if (!single_imm_use (result
, &imm_use
, &use_stmt
)
1066 || gimple_code (use_stmt
) != GIMPLE_PHI
1067 || gimple_bb (use_stmt
) != dest
1068 || gimple_phi_arg_def (use_stmt
, dest_idx
) != result
)
1072 /* If the loop above iterated through all the PHI nodes
1073 in BB, then we can merge the PHIs from BB into DEST. */
1074 if (gsi_end_p (gsi
))
1079 /* Now let's drain WORKLIST. */
1080 bool changed
= false;
1081 while (current
!= worklist
)
1084 changed
|= remove_forwarder_block_with_phi (bb
);
1088 /* Removing forwarder blocks can cause formerly irreducible loops
1089 to become reducible if we merged two entry blocks. */
1092 loops_state_set (LOOPS_NEED_FIXUP
);
1100 make_pass_merge_phi (gcc::context
*ctxt
)
1102 return new pass_merge_phi (ctxt
);
1105 /* Pass: cleanup the CFG just before expanding trees to RTL.
1106 This is just a round of label cleanups and case node grouping
1107 because after the tree optimizers have run such cleanups may
1111 execute_cleanup_cfg_post_optimizing (void)
1113 unsigned int todo
= 0;
1114 if (cleanup_tree_cfg ())
1115 todo
|= TODO_update_ssa
;
1116 maybe_remove_unreachable_handlers ();
1117 cleanup_dead_labels ();
1118 group_case_labels ();
1119 if ((flag_compare_debug_opt
|| flag_compare_debug
)
1120 && flag_dump_final_insns
)
1122 FILE *final_output
= fopen (flag_dump_final_insns
, "a");
1126 error ("could not open final insn dump file %qs: %m",
1127 flag_dump_final_insns
);
1128 flag_dump_final_insns
= NULL
;
1132 int save_unnumbered
= flag_dump_unnumbered
;
1133 int save_noaddr
= flag_dump_noaddr
;
1135 flag_dump_noaddr
= flag_dump_unnumbered
= 1;
1136 fprintf (final_output
, "\n");
1137 dump_enumerated_decls (final_output
, dump_flags
| TDF_NOUID
);
1138 flag_dump_noaddr
= save_noaddr
;
1139 flag_dump_unnumbered
= save_unnumbered
;
1140 if (fclose (final_output
))
1142 error ("could not close final insn dump file %qs: %m",
1143 flag_dump_final_insns
);
1144 flag_dump_final_insns
= NULL
;
1153 const pass_data pass_data_cleanup_cfg_post_optimizing
=
1155 GIMPLE_PASS
, /* type */
1156 "optimized", /* name */
1157 OPTGROUP_NONE
, /* optinfo_flags */
1158 TV_TREE_CLEANUP_CFG
, /* tv_id */
1159 PROP_cfg
, /* properties_required */
1160 0, /* properties_provided */
1161 0, /* properties_destroyed */
1162 0, /* todo_flags_start */
1163 TODO_remove_unused_locals
, /* todo_flags_finish */
1166 class pass_cleanup_cfg_post_optimizing
: public gimple_opt_pass
1169 pass_cleanup_cfg_post_optimizing (gcc::context
*ctxt
)
1170 : gimple_opt_pass (pass_data_cleanup_cfg_post_optimizing
, ctxt
)
1173 /* opt_pass methods: */
1174 virtual unsigned int execute (function
*)
1176 return execute_cleanup_cfg_post_optimizing ();
1179 }; // class pass_cleanup_cfg_post_optimizing
1184 make_pass_cleanup_cfg_post_optimizing (gcc::context
*ctxt
)
1186 return new pass_cleanup_cfg_post_optimizing (ctxt
);