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"
31 #include "hard-reg-set.h"
34 #include "dominance.h"
37 #include "cfgcleanup.h"
38 #include "basic-block.h"
39 #include "diagnostic-core.h"
41 #include "langhooks.h"
42 #include "tree-ssa-alias.h"
43 #include "internal-fn.h"
45 #include "gimple-expr.h"
49 #include "gimple-iterator.h"
50 #include "gimple-ssa.h"
52 #include "tree-phinodes.h"
53 #include "ssa-iterators.h"
54 #include "stringpool.h"
55 #include "tree-ssanames.h"
56 #include "tree-ssa-loop-manip.h"
60 #include "tree-pass.h"
63 #include "tree-ssa-propagate.h"
64 #include "tree-scalar-evolution.h"
66 /* The set of blocks in that at least one of the following changes happened:
67 -- the statement at the end of the block was changed
68 -- the block was newly created
69 -- the set of the predecessors of the block changed
70 -- the set of the successors of the block changed
71 ??? Maybe we could track these changes separately, since they determine
72 what cleanups it makes sense to try on the block. */
73 bitmap cfgcleanup_altered_bbs
;
75 /* Remove any fallthru edge from EV. Return true if an edge was removed. */
78 remove_fallthru_edge (vec
<edge
, va_gc
> *ev
)
83 FOR_EACH_EDGE (e
, ei
, ev
)
84 if ((e
->flags
& EDGE_FALLTHRU
) != 0)
86 if (e
->flags
& EDGE_COMPLEX
)
87 e
->flags
&= ~EDGE_FALLTHRU
;
89 remove_edge_and_dominated_blocks (e
);
96 /* Disconnect an unreachable block in the control expression starting
100 cleanup_control_expr_graph (basic_block bb
, gimple_stmt_iterator gsi
)
104 gimple stmt
= gsi_stmt (gsi
);
107 if (!single_succ_p (bb
))
114 fold_defer_overflow_warnings ();
115 loc
= gimple_location (stmt
);
116 switch (gimple_code (stmt
))
119 val
= fold_binary_loc (loc
, gimple_cond_code (stmt
),
121 gimple_cond_lhs (stmt
),
122 gimple_cond_rhs (stmt
));
126 val
= gimple_switch_index (as_a
<gswitch
*> (stmt
));
132 taken_edge
= find_taken_edge (bb
, val
);
135 fold_undefer_and_ignore_overflow_warnings ();
139 /* Remove all the edges except the one that is always executed. */
141 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
147 fold_undefer_overflow_warnings
148 (true, stmt
, WARN_STRICT_OVERFLOW_CONDITIONAL
);
152 taken_edge
->probability
+= e
->probability
;
153 taken_edge
->count
+= e
->count
;
154 remove_edge_and_dominated_blocks (e
);
161 fold_undefer_and_ignore_overflow_warnings ();
162 if (taken_edge
->probability
> REG_BR_PROB_BASE
)
163 taken_edge
->probability
= REG_BR_PROB_BASE
;
166 taken_edge
= single_succ_edge (bb
);
168 bitmap_set_bit (cfgcleanup_altered_bbs
, bb
->index
);
169 gsi_remove (&gsi
, true);
170 taken_edge
->flags
= EDGE_FALLTHRU
;
175 /* Cleanup the GF_CALL_CTRL_ALTERING flag according to
176 to updated gimple_call_flags. */
179 cleanup_call_ctrl_altering_flag (gimple bb_end
)
181 if (!is_gimple_call (bb_end
)
182 || !gimple_call_ctrl_altering_p (bb_end
))
185 int flags
= gimple_call_flags (bb_end
);
186 if (((flags
& (ECF_CONST
| ECF_PURE
))
187 && !(flags
& ECF_LOOPING_CONST_OR_PURE
))
188 || (flags
& ECF_LEAF
))
189 gimple_call_set_ctrl_altering (bb_end
, false);
192 /* Try to remove superfluous control structures in basic block BB. Returns
193 true if anything changes. */
196 cleanup_control_flow_bb (basic_block bb
)
198 gimple_stmt_iterator gsi
;
202 /* If the last statement of the block could throw and now cannot,
203 we need to prune cfg. */
204 retval
|= gimple_purge_dead_eh_edges (bb
);
206 gsi
= gsi_last_bb (bb
);
210 stmt
= gsi_stmt (gsi
);
212 /* Try to cleanup ctrl altering flag for call which ends bb. */
213 cleanup_call_ctrl_altering_flag (stmt
);
215 if (gimple_code (stmt
) == GIMPLE_COND
216 || gimple_code (stmt
) == GIMPLE_SWITCH
)
217 retval
|= cleanup_control_expr_graph (bb
, gsi
);
218 else if (gimple_code (stmt
) == GIMPLE_GOTO
219 && TREE_CODE (gimple_goto_dest (stmt
)) == ADDR_EXPR
220 && (TREE_CODE (TREE_OPERAND (gimple_goto_dest (stmt
), 0))
223 /* If we had a computed goto which has a compile-time determinable
224 destination, then we can eliminate the goto. */
228 basic_block target_block
;
230 /* First look at all the outgoing edges. Delete any outgoing
231 edges which do not go to the right block. For the one
232 edge which goes to the right block, fix up its flags. */
233 label
= TREE_OPERAND (gimple_goto_dest (stmt
), 0);
234 target_block
= label_to_block (label
);
235 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
237 if (e
->dest
!= target_block
)
238 remove_edge_and_dominated_blocks (e
);
241 /* Turn off the EDGE_ABNORMAL flag. */
242 e
->flags
&= ~EDGE_ABNORMAL
;
244 /* And set EDGE_FALLTHRU. */
245 e
->flags
|= EDGE_FALLTHRU
;
250 bitmap_set_bit (cfgcleanup_altered_bbs
, bb
->index
);
251 bitmap_set_bit (cfgcleanup_altered_bbs
, target_block
->index
);
253 /* Remove the GOTO_EXPR as it is not needed. The CFG has all the
254 relevant information we need. */
255 gsi_remove (&gsi
, true);
259 /* Check for indirect calls that have been turned into
261 else if (is_gimple_call (stmt
)
262 && gimple_call_noreturn_p (stmt
)
263 && remove_fallthru_edge (bb
->succs
))
269 /* Return true if basic block BB does nothing except pass control
270 flow to another block and that we can safely insert a label at
271 the start of the successor block.
273 As a precondition, we require that BB be not equal to
277 tree_forwarder_block_p (basic_block bb
, bool phi_wanted
)
279 gimple_stmt_iterator gsi
;
282 /* BB must have a single outgoing edge. */
283 if (single_succ_p (bb
) != 1
284 /* If PHI_WANTED is false, BB must not have any PHI nodes.
285 Otherwise, BB must have PHI nodes. */
286 || gimple_seq_empty_p (phi_nodes (bb
)) == phi_wanted
287 /* BB may not be a predecessor of the exit block. */
288 || single_succ (bb
) == EXIT_BLOCK_PTR_FOR_FN (cfun
)
289 /* Nor should this be an infinite loop. */
290 || single_succ (bb
) == bb
291 /* BB may not have an abnormal outgoing edge. */
292 || (single_succ_edge (bb
)->flags
& EDGE_ABNORMAL
))
295 gcc_checking_assert (bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
));
297 locus
= single_succ_edge (bb
)->goto_locus
;
299 /* There should not be an edge coming from entry, or an EH edge. */
304 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
305 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) || (e
->flags
& EDGE_EH
))
307 /* If goto_locus of any of the edges differs, prevent removing
308 the forwarder block for -O0. */
309 else if (optimize
== 0 && e
->goto_locus
!= locus
)
313 /* Now walk through the statements backward. We can ignore labels,
314 anything else means this is not a forwarder block. */
315 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
317 gimple stmt
= gsi_stmt (gsi
);
319 switch (gimple_code (stmt
))
322 if (DECL_NONLOCAL (gimple_label_label (as_a
<glabel
*> (stmt
))))
324 if (optimize
== 0 && gimple_location (stmt
) != locus
)
328 /* ??? For now, hope there's a corresponding debug
329 assignment at the destination. */
341 /* Protect loop headers. */
342 if (bb
->loop_father
->header
== bb
)
345 dest
= EDGE_SUCC (bb
, 0)->dest
;
346 /* Protect loop preheaders and latches if requested. */
347 if (dest
->loop_father
->header
== dest
)
349 if (bb
->loop_father
== dest
->loop_father
)
351 if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES
))
353 /* If bb doesn't have a single predecessor we'd make this
354 loop have multiple latches. Don't do that if that
355 would in turn require disambiguating them. */
356 return (single_pred_p (bb
)
357 || loops_state_satisfies_p
358 (LOOPS_MAY_HAVE_MULTIPLE_LATCHES
));
360 else if (bb
->loop_father
== loop_outer (dest
->loop_father
))
361 return !loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS
);
362 /* Always preserve other edges into loop headers that are
363 not simple latches or preheaders. */
371 /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
372 those alternatives are equal in each of the PHI nodes, then return
373 true, else return false. */
376 phi_alternatives_equal (basic_block dest
, edge e1
, edge e2
)
378 int n1
= e1
->dest_idx
;
379 int n2
= e2
->dest_idx
;
382 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
384 gphi
*phi
= gsi
.phi ();
385 tree val1
= gimple_phi_arg_def (phi
, n1
);
386 tree val2
= gimple_phi_arg_def (phi
, n2
);
388 gcc_assert (val1
!= NULL_TREE
);
389 gcc_assert (val2
!= NULL_TREE
);
391 if (!operand_equal_for_phi_arg_p (val1
, val2
))
398 /* Removes forwarder block BB. Returns false if this failed. */
401 remove_forwarder_block (basic_block bb
)
403 edge succ
= single_succ_edge (bb
), e
, s
;
404 basic_block dest
= succ
->dest
;
407 gimple_stmt_iterator gsi
, gsi_to
;
408 bool can_move_debug_stmts
;
410 /* We check for infinite loops already in tree_forwarder_block_p.
411 However it may happen that the infinite loop is created
412 afterwards due to removal of forwarders. */
416 /* If the destination block consists of a nonlocal label or is a
417 EH landing pad, do not merge it. */
418 label
= first_stmt (dest
);
420 if (glabel
*label_stmt
= dyn_cast
<glabel
*> (label
))
421 if (DECL_NONLOCAL (gimple_label_label (label_stmt
))
422 || EH_LANDING_PAD_NR (gimple_label_label (label_stmt
)) != 0)
425 /* If there is an abnormal edge to basic block BB, but not into
426 dest, problems might occur during removal of the phi node at out
427 of ssa due to overlapping live ranges of registers.
429 If there is an abnormal edge in DEST, the problems would occur
430 anyway since cleanup_dead_labels would then merge the labels for
431 two different eh regions, and rest of exception handling code
434 So if there is an abnormal edge to BB, proceed only if there is
435 no abnormal edge to DEST and there are no phi nodes in DEST. */
436 if (bb_has_abnormal_pred (bb
)
437 && (bb_has_abnormal_pred (dest
)
438 || !gimple_seq_empty_p (phi_nodes (dest
))))
441 /* If there are phi nodes in DEST, and some of the blocks that are
442 predecessors of BB are also predecessors of DEST, check that the
443 phi node arguments match. */
444 if (!gimple_seq_empty_p (phi_nodes (dest
)))
446 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
448 s
= find_edge (e
->src
, dest
);
452 if (!phi_alternatives_equal (dest
, succ
, s
))
457 can_move_debug_stmts
= MAY_HAVE_DEBUG_STMTS
&& single_pred_p (dest
);
459 basic_block pred
= NULL
;
460 if (single_pred_p (bb
))
461 pred
= single_pred (bb
);
463 /* Redirect the edges. */
464 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
466 bitmap_set_bit (cfgcleanup_altered_bbs
, e
->src
->index
);
468 if (e
->flags
& EDGE_ABNORMAL
)
470 /* If there is an abnormal edge, redirect it anyway, and
471 move the labels to the new block to make it legal. */
472 s
= redirect_edge_succ_nodup (e
, dest
);
475 s
= redirect_edge_and_branch (e
, dest
);
479 /* Create arguments for the phi nodes, since the edge was not
481 for (gphi_iterator psi
= gsi_start_phis (dest
);
485 gphi
*phi
= psi
.phi ();
486 source_location l
= gimple_phi_arg_location_from_edge (phi
, succ
);
487 tree def
= gimple_phi_arg_def (phi
, succ
->dest_idx
);
488 add_phi_arg (phi
, unshare_expr (def
), s
, l
);
493 /* Move nonlocal labels and computed goto targets as well as user
494 defined labels and labels with an EH landing pad number to the
495 new block, so that the redirection of the abnormal edges works,
496 jump targets end up in a sane place and debug information for
497 labels is retained. */
498 gsi_to
= gsi_start_bb (dest
);
499 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
502 label
= gsi_stmt (gsi
);
503 if (is_gimple_debug (label
))
505 decl
= gimple_label_label (as_a
<glabel
*> (label
));
506 if (EH_LANDING_PAD_NR (decl
) != 0
507 || DECL_NONLOCAL (decl
)
508 || FORCED_LABEL (decl
)
509 || !DECL_ARTIFICIAL (decl
))
511 gsi_remove (&gsi
, false);
512 gsi_insert_before (&gsi_to
, label
, GSI_SAME_STMT
);
518 /* Move debug statements if the destination has a single predecessor. */
519 if (can_move_debug_stmts
)
521 gsi_to
= gsi_after_labels (dest
);
522 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); )
524 gimple debug
= gsi_stmt (gsi
);
525 if (!is_gimple_debug (debug
))
527 gsi_remove (&gsi
, false);
528 gsi_insert_before (&gsi_to
, debug
, GSI_SAME_STMT
);
532 bitmap_set_bit (cfgcleanup_altered_bbs
, dest
->index
);
534 /* Update the dominators. */
535 if (dom_info_available_p (CDI_DOMINATORS
))
537 basic_block dom
, dombb
, domdest
;
539 dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
540 domdest
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
543 /* Shortcut to avoid calling (relatively expensive)
544 nearest_common_dominator unless necessary. */
548 dom
= nearest_common_dominator (CDI_DOMINATORS
, domdest
, dombb
);
550 set_immediate_dominator (CDI_DOMINATORS
, dest
, dom
);
553 /* Adjust latch infomation of BB's parent loop as otherwise
554 the cfg hook has a hard time not to kill the loop. */
555 if (current_loops
&& bb
->loop_father
->latch
== bb
)
556 bb
->loop_father
->latch
= pred
;
558 /* And kill the forwarder block. */
559 delete_basic_block (bb
);
564 /* STMT is a call that has been discovered noreturn. Fixup the CFG
565 and remove LHS. Return true if something changed. */
568 fixup_noreturn_call (gimple stmt
)
570 basic_block bb
= gimple_bb (stmt
);
571 bool changed
= false;
573 if (gimple_call_builtin_p (stmt
, BUILT_IN_RETURN
))
576 /* First split basic block if stmt is not last. */
577 if (stmt
!= gsi_stmt (gsi_last_bb (bb
)))
579 if (stmt
== gsi_stmt (gsi_last_nondebug_bb (bb
)))
581 /* Don't split if there are only debug stmts
582 after stmt, that can result in -fcompare-debug
583 failures. Remove the debug stmts instead,
584 they should be all unreachable anyway. */
585 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
586 for (gsi_next (&gsi
); !gsi_end_p (gsi
); )
587 gsi_remove (&gsi
, true);
590 split_block (bb
, stmt
);
593 changed
|= remove_fallthru_edge (bb
->succs
);
595 /* If there is LHS, remove it. */
596 if (gimple_call_lhs (stmt
))
598 tree op
= gimple_call_lhs (stmt
);
599 gimple_call_set_lhs (stmt
, NULL_TREE
);
601 /* We need to remove SSA name to avoid checking errors.
602 All uses are dominated by the noreturn and thus will
603 be removed afterwards.
604 We proactively remove affected non-PHI statements to avoid
605 fixup_cfg from trying to update them and crashing. */
606 if (TREE_CODE (op
) == SSA_NAME
)
609 imm_use_iterator iter
;
612 unsigned int bb_index
;
614 bitmap blocks
= BITMAP_ALLOC (NULL
);
616 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, op
)
618 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
619 bitmap_set_bit (blocks
, gimple_bb (use_stmt
)->index
);
621 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
622 SET_USE (use_p
, error_mark_node
);
624 EXECUTE_IF_SET_IN_BITMAP (blocks
, 0, bb_index
, bi
)
625 delete_basic_block (BASIC_BLOCK_FOR_FN (cfun
, bb_index
));
626 BITMAP_FREE (blocks
);
627 release_ssa_name (op
);
636 /* Split basic blocks on calls in the middle of a basic block that are now
637 known not to return, and remove the unreachable code. */
640 split_bb_on_noreturn_calls (basic_block bb
)
642 bool changed
= false;
643 gimple_stmt_iterator gsi
;
645 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
647 gimple stmt
= gsi_stmt (gsi
);
649 if (!is_gimple_call (stmt
))
652 if (gimple_call_noreturn_p (stmt
))
653 changed
|= fixup_noreturn_call (stmt
);
657 bitmap_set_bit (cfgcleanup_altered_bbs
, bb
->index
);
661 /* Tries to cleanup cfg in basic block BB. Returns true if anything
665 cleanup_tree_cfg_bb (basic_block bb
)
667 bool retval
= cleanup_control_flow_bb (bb
);
669 if (tree_forwarder_block_p (bb
, false)
670 && remove_forwarder_block (bb
))
673 /* Merging the blocks may create new opportunities for folding
674 conditional branches (due to the elimination of single-valued PHI
676 if (single_succ_p (bb
)
677 && can_merge_blocks_p (bb
, single_succ (bb
)))
679 merge_blocks (bb
, single_succ (bb
));
686 /* Iterate the cfg cleanups, while anything changes. */
689 cleanup_tree_cfg_1 (void)
695 /* Prepare the worklists of altered blocks. */
696 cfgcleanup_altered_bbs
= BITMAP_ALLOC (NULL
);
698 /* During forwarder block cleanup, we may redirect edges out of
699 SWITCH_EXPRs, which can get expensive. So we want to enable
700 recording of edge to CASE_LABEL_EXPR. */
701 start_recording_case_labels ();
703 /* Start by iterating over all basic blocks. We cannot use FOR_EACH_BB_FN,
704 since the basic blocks may get removed. */
705 n
= last_basic_block_for_fn (cfun
);
706 for (i
= NUM_FIXED_BLOCKS
; i
< n
; i
++)
708 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
711 retval
|= cleanup_tree_cfg_bb (bb
);
712 retval
|= split_bb_on_noreturn_calls (bb
);
716 /* Now process the altered blocks, as long as any are available. */
717 while (!bitmap_empty_p (cfgcleanup_altered_bbs
))
719 i
= bitmap_first_set_bit (cfgcleanup_altered_bbs
);
720 bitmap_clear_bit (cfgcleanup_altered_bbs
, i
);
721 if (i
< NUM_FIXED_BLOCKS
)
724 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
728 retval
|= cleanup_tree_cfg_bb (bb
);
730 /* Rerun split_bb_on_noreturn_calls, in case we have altered any noreturn
732 retval
|= split_bb_on_noreturn_calls (bb
);
735 end_recording_case_labels ();
736 BITMAP_FREE (cfgcleanup_altered_bbs
);
741 /* Remove unreachable blocks and other miscellaneous clean up work.
742 Return true if the flowgraph was modified, false otherwise. */
745 cleanup_tree_cfg_noloop (void)
749 timevar_push (TV_TREE_CLEANUP_CFG
);
751 /* Iterate until there are no more cleanups left to do. If any
752 iteration changed the flowgraph, set CHANGED to true.
754 If dominance information is available, there cannot be any unreachable
756 if (!dom_info_available_p (CDI_DOMINATORS
))
758 changed
= delete_unreachable_blocks ();
759 calculate_dominance_info (CDI_DOMINATORS
);
763 #ifdef ENABLE_CHECKING
764 verify_dominators (CDI_DOMINATORS
);
769 changed
|= cleanup_tree_cfg_1 ();
771 gcc_assert (dom_info_available_p (CDI_DOMINATORS
));
774 #ifdef ENABLE_CHECKING
778 timevar_pop (TV_TREE_CLEANUP_CFG
);
780 if (changed
&& current_loops
)
781 loops_state_set (LOOPS_NEED_FIXUP
);
786 /* Repairs loop structures. */
789 repair_loop_structures (void)
792 unsigned n_new_loops
;
794 calculate_dominance_info (CDI_DOMINATORS
);
796 timevar_push (TV_REPAIR_LOOPS
);
797 changed_bbs
= BITMAP_ALLOC (NULL
);
798 n_new_loops
= fix_loop_structure (changed_bbs
);
800 /* This usually does nothing. But sometimes parts of cfg that originally
801 were inside a loop get out of it due to edge removal (since they
802 become unreachable by back edges from latch). Also a former
803 irreducible loop can become reducible - in this case force a full
804 rewrite into loop-closed SSA form. */
805 if (loops_state_satisfies_p (LOOP_CLOSED_SSA
))
806 rewrite_into_loop_closed_ssa (n_new_loops
? NULL
: changed_bbs
,
809 BITMAP_FREE (changed_bbs
);
811 #ifdef ENABLE_CHECKING
812 verify_loop_structure ();
816 timevar_pop (TV_REPAIR_LOOPS
);
819 /* Cleanup cfg and repair loop structures. */
822 cleanup_tree_cfg (void)
824 bool changed
= cleanup_tree_cfg_noloop ();
826 if (current_loops
!= NULL
827 && loops_state_satisfies_p (LOOPS_NEED_FIXUP
))
828 repair_loop_structures ();
833 /* Tries to merge the PHI nodes at BB into those at BB's sole successor.
834 Returns true if successful. */
837 remove_forwarder_block_with_phi (basic_block bb
)
839 edge succ
= single_succ_edge (bb
);
840 basic_block dest
= succ
->dest
;
842 basic_block dombb
, domdest
, dom
;
844 /* We check for infinite loops already in tree_forwarder_block_p.
845 However it may happen that the infinite loop is created
846 afterwards due to removal of forwarders. */
850 /* If the destination block consists of a nonlocal label, do not
852 label
= first_stmt (dest
);
854 if (glabel
*label_stmt
= dyn_cast
<glabel
*> (label
))
855 if (DECL_NONLOCAL (gimple_label_label (label_stmt
)))
858 /* Record BB's single pred in case we need to update the father
859 loop's latch information later. */
860 basic_block pred
= NULL
;
861 if (single_pred_p (bb
))
862 pred
= single_pred (bb
);
864 /* Redirect each incoming edge to BB to DEST. */
865 while (EDGE_COUNT (bb
->preds
) > 0)
867 edge e
= EDGE_PRED (bb
, 0), s
;
870 s
= find_edge (e
->src
, dest
);
873 /* We already have an edge S from E->src to DEST. If S and
874 E->dest's sole successor edge have the same PHI arguments
875 at DEST, redirect S to DEST. */
876 if (phi_alternatives_equal (dest
, s
, succ
))
878 e
= redirect_edge_and_branch (e
, dest
);
879 redirect_edge_var_map_clear (e
);
883 /* PHI arguments are different. Create a forwarder block by
884 splitting E so that we can merge PHI arguments on E to
886 e
= single_succ_edge (split_edge (e
));
889 s
= redirect_edge_and_branch (e
, dest
);
891 /* redirect_edge_and_branch must not create a new edge. */
894 /* Add to the PHI nodes at DEST each PHI argument removed at the
896 for (gsi
= gsi_start_phis (dest
);
900 gphi
*phi
= gsi
.phi ();
901 tree def
= gimple_phi_arg_def (phi
, succ
->dest_idx
);
902 source_location locus
= gimple_phi_arg_location_from_edge (phi
, succ
);
904 if (TREE_CODE (def
) == SSA_NAME
)
906 /* If DEF is one of the results of PHI nodes removed during
907 redirection, replace it with the PHI argument that used
909 vec
<edge_var_map
> *head
= redirect_edge_var_map_vector (e
);
910 size_t length
= head
? head
->length () : 0;
911 for (size_t i
= 0; i
< length
; i
++)
913 edge_var_map
*vm
= &(*head
)[i
];
914 tree old_arg
= redirect_edge_var_map_result (vm
);
915 tree new_arg
= redirect_edge_var_map_def (vm
);
920 locus
= redirect_edge_var_map_location (vm
);
926 add_phi_arg (phi
, def
, s
, locus
);
929 redirect_edge_var_map_clear (e
);
932 /* Update the dominators. */
933 dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
934 domdest
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
937 /* Shortcut to avoid calling (relatively expensive)
938 nearest_common_dominator unless necessary. */
942 dom
= nearest_common_dominator (CDI_DOMINATORS
, domdest
, dombb
);
944 set_immediate_dominator (CDI_DOMINATORS
, dest
, dom
);
946 /* Adjust latch infomation of BB's parent loop as otherwise
947 the cfg hook has a hard time not to kill the loop. */
948 if (current_loops
&& bb
->loop_father
->latch
== bb
)
949 bb
->loop_father
->latch
= pred
;
951 /* Remove BB since all of BB's incoming edges have been redirected
953 delete_basic_block (bb
);
958 /* This pass merges PHI nodes if one feeds into another. For example,
959 suppose we have the following:
966 # tem_6 = PHI <tem_17(8), tem_23(7)>;
969 # tem_3 = PHI <tem_6(9), tem_2(5)>;
972 Then we merge the first PHI node into the second one like so:
979 # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
985 const pass_data pass_data_merge_phi
=
987 GIMPLE_PASS
, /* type */
988 "mergephi", /* name */
989 OPTGROUP_NONE
, /* optinfo_flags */
990 TV_TREE_MERGE_PHI
, /* tv_id */
991 ( PROP_cfg
| PROP_ssa
), /* properties_required */
992 0, /* properties_provided */
993 0, /* properties_destroyed */
994 0, /* todo_flags_start */
995 0, /* todo_flags_finish */
998 class pass_merge_phi
: public gimple_opt_pass
1001 pass_merge_phi (gcc::context
*ctxt
)
1002 : gimple_opt_pass (pass_data_merge_phi
, ctxt
)
1005 /* opt_pass methods: */
1006 opt_pass
* clone () { return new pass_merge_phi (m_ctxt
); }
1007 virtual unsigned int execute (function
*);
1009 }; // class pass_merge_phi
1012 pass_merge_phi::execute (function
*fun
)
1014 basic_block
*worklist
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (fun
));
1015 basic_block
*current
= worklist
;
1018 calculate_dominance_info (CDI_DOMINATORS
);
1020 /* Find all PHI nodes that we may be able to merge. */
1021 FOR_EACH_BB_FN (bb
, fun
)
1025 /* Look for a forwarder block with PHI nodes. */
1026 if (!tree_forwarder_block_p (bb
, true))
1029 dest
= single_succ (bb
);
1031 /* We have to feed into another basic block with PHI
1033 if (gimple_seq_empty_p (phi_nodes (dest
))
1034 /* We don't want to deal with a basic block with
1036 || bb_has_abnormal_pred (bb
))
1039 if (!dominated_by_p (CDI_DOMINATORS
, dest
, bb
))
1041 /* If BB does not dominate DEST, then the PHI nodes at
1042 DEST must be the only users of the results of the PHI
1049 unsigned int dest_idx
= single_succ_edge (bb
)->dest_idx
;
1051 /* BB dominates DEST. There may be many users of the PHI
1052 nodes in BB. However, there is still a trivial case we
1053 can handle. If the result of every PHI in BB is used
1054 only by a PHI in DEST, then we can trivially merge the
1055 PHI nodes from BB into DEST. */
1056 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
1059 gphi
*phi
= gsi
.phi ();
1060 tree result
= gimple_phi_result (phi
);
1061 use_operand_p imm_use
;
1064 /* If the PHI's result is never used, then we can just
1066 if (has_zero_uses (result
))
1069 /* Get the single use of the result of this PHI node. */
1070 if (!single_imm_use (result
, &imm_use
, &use_stmt
)
1071 || gimple_code (use_stmt
) != GIMPLE_PHI
1072 || gimple_bb (use_stmt
) != dest
1073 || gimple_phi_arg_def (use_stmt
, dest_idx
) != result
)
1077 /* If the loop above iterated through all the PHI nodes
1078 in BB, then we can merge the PHIs from BB into DEST. */
1079 if (gsi_end_p (gsi
))
1084 /* Now let's drain WORKLIST. */
1085 bool changed
= false;
1086 while (current
!= worklist
)
1089 changed
|= remove_forwarder_block_with_phi (bb
);
1093 /* Removing forwarder blocks can cause formerly irreducible loops
1094 to become reducible if we merged two entry blocks. */
1097 loops_state_set (LOOPS_NEED_FIXUP
);
1105 make_pass_merge_phi (gcc::context
*ctxt
)
1107 return new pass_merge_phi (ctxt
);
1110 /* Pass: cleanup the CFG just before expanding trees to RTL.
1111 This is just a round of label cleanups and case node grouping
1112 because after the tree optimizers have run such cleanups may
1116 execute_cleanup_cfg_post_optimizing (void)
1118 unsigned int todo
= 0;
1119 if (cleanup_tree_cfg ())
1120 todo
|= TODO_update_ssa
;
1121 maybe_remove_unreachable_handlers ();
1122 cleanup_dead_labels ();
1123 group_case_labels ();
1124 if ((flag_compare_debug_opt
|| flag_compare_debug
)
1125 && flag_dump_final_insns
)
1127 FILE *final_output
= fopen (flag_dump_final_insns
, "a");
1131 error ("could not open final insn dump file %qs: %m",
1132 flag_dump_final_insns
);
1133 flag_dump_final_insns
= NULL
;
1137 int save_unnumbered
= flag_dump_unnumbered
;
1138 int save_noaddr
= flag_dump_noaddr
;
1140 flag_dump_noaddr
= flag_dump_unnumbered
= 1;
1141 fprintf (final_output
, "\n");
1142 dump_enumerated_decls (final_output
, dump_flags
| TDF_NOUID
);
1143 flag_dump_noaddr
= save_noaddr
;
1144 flag_dump_unnumbered
= save_unnumbered
;
1145 if (fclose (final_output
))
1147 error ("could not close final insn dump file %qs: %m",
1148 flag_dump_final_insns
);
1149 flag_dump_final_insns
= NULL
;
1158 const pass_data pass_data_cleanup_cfg_post_optimizing
=
1160 GIMPLE_PASS
, /* type */
1161 "optimized", /* name */
1162 OPTGROUP_NONE
, /* optinfo_flags */
1163 TV_TREE_CLEANUP_CFG
, /* tv_id */
1164 PROP_cfg
, /* properties_required */
1165 0, /* properties_provided */
1166 0, /* properties_destroyed */
1167 0, /* todo_flags_start */
1168 TODO_remove_unused_locals
, /* todo_flags_finish */
1171 class pass_cleanup_cfg_post_optimizing
: public gimple_opt_pass
1174 pass_cleanup_cfg_post_optimizing (gcc::context
*ctxt
)
1175 : gimple_opt_pass (pass_data_cleanup_cfg_post_optimizing
, ctxt
)
1178 /* opt_pass methods: */
1179 virtual unsigned int execute (function
*)
1181 return execute_cleanup_cfg_post_optimizing ();
1184 }; // class pass_cleanup_cfg_post_optimizing
1189 make_pass_cleanup_cfg_post_optimizing (gcc::context
*ctxt
)
1191 return new pass_cleanup_cfg_post_optimizing (ctxt
);