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"
30 #include "langhooks.h"
31 #include "tree-ssa-alias.h"
32 #include "internal-fn.h"
34 #include "gimple-expr.h"
38 #include "gimple-iterator.h"
39 #include "gimple-ssa.h"
41 #include "tree-phinodes.h"
42 #include "ssa-iterators.h"
43 #include "stringpool.h"
44 #include "tree-ssanames.h"
45 #include "tree-ssa-loop-manip.h"
49 #include "tree-pass.h"
53 #include "tree-ssa-propagate.h"
54 #include "tree-scalar-evolution.h"
56 /* The set of blocks in that at least one of the following changes happened:
57 -- the statement at the end of the block was changed
58 -- the block was newly created
59 -- the set of the predecessors of the block changed
60 -- the set of the successors of the block changed
61 ??? Maybe we could track these changes separately, since they determine
62 what cleanups it makes sense to try on the block. */
63 bitmap cfgcleanup_altered_bbs
;
65 /* Remove any fallthru edge from EV. Return true if an edge was removed. */
68 remove_fallthru_edge (vec
<edge
, va_gc
> *ev
)
73 FOR_EACH_EDGE (e
, ei
, ev
)
74 if ((e
->flags
& EDGE_FALLTHRU
) != 0)
76 if (e
->flags
& EDGE_COMPLEX
)
77 e
->flags
&= ~EDGE_FALLTHRU
;
79 remove_edge_and_dominated_blocks (e
);
86 /* Disconnect an unreachable block in the control expression starting
90 cleanup_control_expr_graph (basic_block bb
, gimple_stmt_iterator gsi
)
94 gimple stmt
= gsi_stmt (gsi
);
97 if (!single_succ_p (bb
))
104 fold_defer_overflow_warnings ();
105 loc
= gimple_location (stmt
);
106 switch (gimple_code (stmt
))
109 val
= fold_binary_loc (loc
, gimple_cond_code (stmt
),
111 gimple_cond_lhs (stmt
),
112 gimple_cond_rhs (stmt
));
116 val
= gimple_switch_index (stmt
);
122 taken_edge
= find_taken_edge (bb
, val
);
125 fold_undefer_and_ignore_overflow_warnings ();
129 /* Remove all the edges except the one that is always executed. */
131 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
137 fold_undefer_overflow_warnings
138 (true, stmt
, WARN_STRICT_OVERFLOW_CONDITIONAL
);
142 taken_edge
->probability
+= e
->probability
;
143 taken_edge
->count
+= e
->count
;
144 remove_edge_and_dominated_blocks (e
);
151 fold_undefer_and_ignore_overflow_warnings ();
152 if (taken_edge
->probability
> REG_BR_PROB_BASE
)
153 taken_edge
->probability
= REG_BR_PROB_BASE
;
156 taken_edge
= single_succ_edge (bb
);
158 bitmap_set_bit (cfgcleanup_altered_bbs
, bb
->index
);
159 gsi_remove (&gsi
, true);
160 taken_edge
->flags
= EDGE_FALLTHRU
;
165 /* Try to remove superfluous control structures in basic block BB. Returns
166 true if anything changes. */
169 cleanup_control_flow_bb (basic_block bb
)
171 gimple_stmt_iterator gsi
;
175 /* If the last statement of the block could throw and now cannot,
176 we need to prune cfg. */
177 retval
|= gimple_purge_dead_eh_edges (bb
);
179 gsi
= gsi_last_bb (bb
);
183 stmt
= gsi_stmt (gsi
);
185 if (gimple_code (stmt
) == GIMPLE_COND
186 || gimple_code (stmt
) == GIMPLE_SWITCH
)
187 retval
|= cleanup_control_expr_graph (bb
, gsi
);
188 else if (gimple_code (stmt
) == GIMPLE_GOTO
189 && TREE_CODE (gimple_goto_dest (stmt
)) == ADDR_EXPR
190 && (TREE_CODE (TREE_OPERAND (gimple_goto_dest (stmt
), 0))
193 /* If we had a computed goto which has a compile-time determinable
194 destination, then we can eliminate the goto. */
198 basic_block target_block
;
200 /* First look at all the outgoing edges. Delete any outgoing
201 edges which do not go to the right block. For the one
202 edge which goes to the right block, fix up its flags. */
203 label
= TREE_OPERAND (gimple_goto_dest (stmt
), 0);
204 target_block
= label_to_block (label
);
205 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
207 if (e
->dest
!= target_block
)
208 remove_edge_and_dominated_blocks (e
);
211 /* Turn off the EDGE_ABNORMAL flag. */
212 e
->flags
&= ~EDGE_ABNORMAL
;
214 /* And set EDGE_FALLTHRU. */
215 e
->flags
|= EDGE_FALLTHRU
;
220 bitmap_set_bit (cfgcleanup_altered_bbs
, bb
->index
);
221 bitmap_set_bit (cfgcleanup_altered_bbs
, target_block
->index
);
223 /* Remove the GOTO_EXPR as it is not needed. The CFG has all the
224 relevant information we need. */
225 gsi_remove (&gsi
, true);
229 /* Check for indirect calls that have been turned into
231 else if (is_gimple_call (stmt
)
232 && gimple_call_noreturn_p (stmt
)
233 && remove_fallthru_edge (bb
->succs
))
239 /* Return true if basic block BB does nothing except pass control
240 flow to another block and that we can safely insert a label at
241 the start of the successor block.
243 As a precondition, we require that BB be not equal to
247 tree_forwarder_block_p (basic_block bb
, bool phi_wanted
)
249 gimple_stmt_iterator gsi
;
252 /* BB must have a single outgoing edge. */
253 if (single_succ_p (bb
) != 1
254 /* If PHI_WANTED is false, BB must not have any PHI nodes.
255 Otherwise, BB must have PHI nodes. */
256 || gimple_seq_empty_p (phi_nodes (bb
)) == phi_wanted
257 /* BB may not be a predecessor of the exit block. */
258 || single_succ (bb
) == EXIT_BLOCK_PTR_FOR_FN (cfun
)
259 /* Nor should this be an infinite loop. */
260 || single_succ (bb
) == bb
261 /* BB may not have an abnormal outgoing edge. */
262 || (single_succ_edge (bb
)->flags
& EDGE_ABNORMAL
))
265 gcc_checking_assert (bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
));
267 locus
= single_succ_edge (bb
)->goto_locus
;
269 /* There should not be an edge coming from entry, or an EH edge. */
274 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
275 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) || (e
->flags
& EDGE_EH
))
277 /* If goto_locus of any of the edges differs, prevent removing
278 the forwarder block for -O0. */
279 else if (optimize
== 0 && e
->goto_locus
!= locus
)
283 /* Now walk through the statements backward. We can ignore labels,
284 anything else means this is not a forwarder block. */
285 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
287 gimple stmt
= gsi_stmt (gsi
);
289 switch (gimple_code (stmt
))
292 if (DECL_NONLOCAL (gimple_label_label (stmt
)))
294 if (optimize
== 0 && gimple_location (stmt
) != locus
)
298 /* ??? For now, hope there's a corresponding debug
299 assignment at the destination. */
311 /* Protect loop headers. */
312 if (bb
->loop_father
->header
== bb
)
315 dest
= EDGE_SUCC (bb
, 0)->dest
;
316 /* Protect loop preheaders and latches if requested. */
317 if (dest
->loop_father
->header
== dest
)
319 if (bb
->loop_father
== dest
->loop_father
)
321 if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES
))
323 /* If bb doesn't have a single predecessor we'd make this
324 loop have multiple latches. Don't do that if that
325 would in turn require disambiguating them. */
326 return (single_pred_p (bb
)
327 || loops_state_satisfies_p
328 (LOOPS_MAY_HAVE_MULTIPLE_LATCHES
));
330 else if (bb
->loop_father
== loop_outer (dest
->loop_father
))
331 return !loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS
);
332 /* Always preserve other edges into loop headers that are
333 not simple latches or preheaders. */
341 /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
342 those alternatives are equal in each of the PHI nodes, then return
343 true, else return false. */
346 phi_alternatives_equal (basic_block dest
, edge e1
, edge e2
)
348 int n1
= e1
->dest_idx
;
349 int n2
= e2
->dest_idx
;
350 gimple_stmt_iterator gsi
;
352 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
354 gimple phi
= gsi_stmt (gsi
);
355 tree val1
= gimple_phi_arg_def (phi
, n1
);
356 tree val2
= gimple_phi_arg_def (phi
, n2
);
358 gcc_assert (val1
!= NULL_TREE
);
359 gcc_assert (val2
!= NULL_TREE
);
361 if (!operand_equal_for_phi_arg_p (val1
, val2
))
368 /* Removes forwarder block BB. Returns false if this failed. */
371 remove_forwarder_block (basic_block bb
)
373 edge succ
= single_succ_edge (bb
), e
, s
;
374 basic_block dest
= succ
->dest
;
377 gimple_stmt_iterator gsi
, gsi_to
;
378 bool can_move_debug_stmts
;
380 /* We check for infinite loops already in tree_forwarder_block_p.
381 However it may happen that the infinite loop is created
382 afterwards due to removal of forwarders. */
386 /* If the destination block consists of a nonlocal label or is a
387 EH landing pad, do not merge it. */
388 label
= first_stmt (dest
);
390 && gimple_code (label
) == GIMPLE_LABEL
391 && (DECL_NONLOCAL (gimple_label_label (label
))
392 || EH_LANDING_PAD_NR (gimple_label_label (label
)) != 0))
395 /* If there is an abnormal edge to basic block BB, but not into
396 dest, problems might occur during removal of the phi node at out
397 of ssa due to overlapping live ranges of registers.
399 If there is an abnormal edge in DEST, the problems would occur
400 anyway since cleanup_dead_labels would then merge the labels for
401 two different eh regions, and rest of exception handling code
404 So if there is an abnormal edge to BB, proceed only if there is
405 no abnormal edge to DEST and there are no phi nodes in DEST. */
406 if (bb_has_abnormal_pred (bb
)
407 && (bb_has_abnormal_pred (dest
)
408 || !gimple_seq_empty_p (phi_nodes (dest
))))
411 /* If there are phi nodes in DEST, and some of the blocks that are
412 predecessors of BB are also predecessors of DEST, check that the
413 phi node arguments match. */
414 if (!gimple_seq_empty_p (phi_nodes (dest
)))
416 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
418 s
= find_edge (e
->src
, dest
);
422 if (!phi_alternatives_equal (dest
, succ
, s
))
427 can_move_debug_stmts
= MAY_HAVE_DEBUG_STMTS
&& single_pred_p (dest
);
429 basic_block pred
= NULL
;
430 if (single_pred_p (bb
))
431 pred
= single_pred (bb
);
433 /* Redirect the edges. */
434 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
436 bitmap_set_bit (cfgcleanup_altered_bbs
, e
->src
->index
);
438 if (e
->flags
& EDGE_ABNORMAL
)
440 /* If there is an abnormal edge, redirect it anyway, and
441 move the labels to the new block to make it legal. */
442 s
= redirect_edge_succ_nodup (e
, dest
);
445 s
= redirect_edge_and_branch (e
, dest
);
449 /* Create arguments for the phi nodes, since the edge was not
451 for (gsi
= gsi_start_phis (dest
);
455 gimple phi
= gsi_stmt (gsi
);
456 source_location l
= gimple_phi_arg_location_from_edge (phi
, succ
);
457 tree def
= gimple_phi_arg_def (phi
, succ
->dest_idx
);
458 add_phi_arg (phi
, unshare_expr (def
), s
, l
);
463 /* Move nonlocal labels and computed goto targets as well as user
464 defined labels and labels with an EH landing pad number to the
465 new block, so that the redirection of the abnormal edges works,
466 jump targets end up in a sane place and debug information for
467 labels is retained. */
468 gsi_to
= gsi_start_bb (dest
);
469 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
472 label
= gsi_stmt (gsi
);
473 if (is_gimple_debug (label
))
475 decl
= gimple_label_label (label
);
476 if (EH_LANDING_PAD_NR (decl
) != 0
477 || DECL_NONLOCAL (decl
)
478 || FORCED_LABEL (decl
)
479 || !DECL_ARTIFICIAL (decl
))
481 gsi_remove (&gsi
, false);
482 gsi_insert_before (&gsi_to
, label
, GSI_SAME_STMT
);
488 /* Move debug statements if the destination has a single predecessor. */
489 if (can_move_debug_stmts
)
491 gsi_to
= gsi_after_labels (dest
);
492 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); )
494 gimple debug
= gsi_stmt (gsi
);
495 if (!is_gimple_debug (debug
))
497 gsi_remove (&gsi
, false);
498 gsi_insert_before (&gsi_to
, debug
, GSI_SAME_STMT
);
502 bitmap_set_bit (cfgcleanup_altered_bbs
, dest
->index
);
504 /* Update the dominators. */
505 if (dom_info_available_p (CDI_DOMINATORS
))
507 basic_block dom
, dombb
, domdest
;
509 dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
510 domdest
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
513 /* Shortcut to avoid calling (relatively expensive)
514 nearest_common_dominator unless necessary. */
518 dom
= nearest_common_dominator (CDI_DOMINATORS
, domdest
, dombb
);
520 set_immediate_dominator (CDI_DOMINATORS
, dest
, dom
);
523 /* Adjust latch infomation of BB's parent loop as otherwise
524 the cfg hook has a hard time not to kill the loop. */
525 if (current_loops
&& bb
->loop_father
->latch
== bb
)
526 bb
->loop_father
->latch
= pred
;
528 /* And kill the forwarder block. */
529 delete_basic_block (bb
);
534 /* STMT is a call that has been discovered noreturn. Fixup the CFG
535 and remove LHS. Return true if something changed. */
538 fixup_noreturn_call (gimple stmt
)
540 basic_block bb
= gimple_bb (stmt
);
541 bool changed
= false;
543 if (gimple_call_builtin_p (stmt
, BUILT_IN_RETURN
))
546 /* First split basic block if stmt is not last. */
547 if (stmt
!= gsi_stmt (gsi_last_bb (bb
)))
548 split_block (bb
, stmt
);
550 changed
|= remove_fallthru_edge (bb
->succs
);
552 /* If there is LHS, remove it. */
553 if (gimple_call_lhs (stmt
))
555 tree op
= gimple_call_lhs (stmt
);
556 gimple_call_set_lhs (stmt
, NULL_TREE
);
558 /* We need to remove SSA name to avoid checking errors.
559 All uses are dominated by the noreturn and thus will
560 be removed afterwards.
561 We proactively remove affected non-PHI statements to avoid
562 fixup_cfg from trying to update them and crashing. */
563 if (TREE_CODE (op
) == SSA_NAME
)
566 imm_use_iterator iter
;
569 unsigned int bb_index
;
571 bitmap blocks
= BITMAP_ALLOC (NULL
);
573 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, op
)
575 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
576 bitmap_set_bit (blocks
, gimple_bb (use_stmt
)->index
);
578 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
579 SET_USE (use_p
, error_mark_node
);
581 EXECUTE_IF_SET_IN_BITMAP (blocks
, 0, bb_index
, bi
)
582 delete_basic_block (BASIC_BLOCK_FOR_FN (cfun
, bb_index
));
583 BITMAP_FREE (blocks
);
584 release_ssa_name (op
);
593 /* Split basic blocks on calls in the middle of a basic block that are now
594 known not to return, and remove the unreachable code. */
597 split_bbs_on_noreturn_calls (void)
599 bool changed
= false;
603 /* Detect cases where a mid-block call is now known not to return. */
605 while (vec_safe_length (MODIFIED_NORETURN_CALLS (cfun
)))
607 stmt
= MODIFIED_NORETURN_CALLS (cfun
)->pop ();
608 bb
= gimple_bb (stmt
);
609 /* BB might be deleted at this point, so verify first
610 BB is present in the cfg. */
612 || bb
->index
< NUM_FIXED_BLOCKS
613 || bb
->index
>= last_basic_block_for_fn (cfun
)
614 || BASIC_BLOCK_FOR_FN (cfun
, bb
->index
) != bb
615 || !gimple_call_noreturn_p (stmt
))
618 changed
|= fixup_noreturn_call (stmt
);
624 /* Tries to cleanup cfg in basic block BB. Returns true if anything
628 cleanup_tree_cfg_bb (basic_block bb
)
630 bool retval
= cleanup_control_flow_bb (bb
);
632 if (tree_forwarder_block_p (bb
, false)
633 && remove_forwarder_block (bb
))
636 /* Merging the blocks may create new opportunities for folding
637 conditional branches (due to the elimination of single-valued PHI
639 if (single_succ_p (bb
)
640 && can_merge_blocks_p (bb
, single_succ (bb
)))
642 merge_blocks (bb
, single_succ (bb
));
649 /* Iterate the cfg cleanups, while anything changes. */
652 cleanup_tree_cfg_1 (void)
658 retval
|= split_bbs_on_noreturn_calls ();
660 /* Prepare the worklists of altered blocks. */
661 cfgcleanup_altered_bbs
= BITMAP_ALLOC (NULL
);
663 /* During forwarder block cleanup, we may redirect edges out of
664 SWITCH_EXPRs, which can get expensive. So we want to enable
665 recording of edge to CASE_LABEL_EXPR. */
666 start_recording_case_labels ();
668 /* Start by iterating over all basic blocks. We cannot use FOR_EACH_BB_FN,
669 since the basic blocks may get removed. */
670 n
= last_basic_block_for_fn (cfun
);
671 for (i
= NUM_FIXED_BLOCKS
; i
< n
; i
++)
673 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
675 retval
|= cleanup_tree_cfg_bb (bb
);
678 /* Now process the altered blocks, as long as any are available. */
679 while (!bitmap_empty_p (cfgcleanup_altered_bbs
))
681 i
= bitmap_first_set_bit (cfgcleanup_altered_bbs
);
682 bitmap_clear_bit (cfgcleanup_altered_bbs
, i
);
683 if (i
< NUM_FIXED_BLOCKS
)
686 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
690 retval
|= cleanup_tree_cfg_bb (bb
);
692 /* Rerun split_bbs_on_noreturn_calls, in case we have altered any noreturn
694 retval
|= split_bbs_on_noreturn_calls ();
697 end_recording_case_labels ();
698 BITMAP_FREE (cfgcleanup_altered_bbs
);
703 /* Remove unreachable blocks and other miscellaneous clean up work.
704 Return true if the flowgraph was modified, false otherwise. */
707 cleanup_tree_cfg_noloop (void)
711 timevar_push (TV_TREE_CLEANUP_CFG
);
713 /* Iterate until there are no more cleanups left to do. If any
714 iteration changed the flowgraph, set CHANGED to true.
716 If dominance information is available, there cannot be any unreachable
718 if (!dom_info_available_p (CDI_DOMINATORS
))
720 changed
= delete_unreachable_blocks ();
721 calculate_dominance_info (CDI_DOMINATORS
);
725 #ifdef ENABLE_CHECKING
726 verify_dominators (CDI_DOMINATORS
);
731 changed
|= cleanup_tree_cfg_1 ();
733 gcc_assert (dom_info_available_p (CDI_DOMINATORS
));
736 #ifdef ENABLE_CHECKING
740 timevar_pop (TV_TREE_CLEANUP_CFG
);
742 if (changed
&& current_loops
)
743 loops_state_set (LOOPS_NEED_FIXUP
);
748 /* Repairs loop structures. */
751 repair_loop_structures (void)
754 unsigned n_new_loops
;
756 calculate_dominance_info (CDI_DOMINATORS
);
758 timevar_push (TV_REPAIR_LOOPS
);
759 changed_bbs
= BITMAP_ALLOC (NULL
);
760 n_new_loops
= fix_loop_structure (changed_bbs
);
762 /* This usually does nothing. But sometimes parts of cfg that originally
763 were inside a loop get out of it due to edge removal (since they
764 become unreachable by back edges from latch). Also a former
765 irreducible loop can become reducible - in this case force a full
766 rewrite into loop-closed SSA form. */
767 if (loops_state_satisfies_p (LOOP_CLOSED_SSA
))
768 rewrite_into_loop_closed_ssa (n_new_loops
? NULL
: changed_bbs
,
771 BITMAP_FREE (changed_bbs
);
773 #ifdef ENABLE_CHECKING
774 verify_loop_structure ();
778 timevar_pop (TV_REPAIR_LOOPS
);
781 /* Cleanup cfg and repair loop structures. */
784 cleanup_tree_cfg (void)
786 bool changed
= cleanup_tree_cfg_noloop ();
788 if (current_loops
!= NULL
789 && loops_state_satisfies_p (LOOPS_NEED_FIXUP
))
790 repair_loop_structures ();
795 /* Tries to merge the PHI nodes at BB into those at BB's sole successor.
796 Returns true if successful. */
799 remove_forwarder_block_with_phi (basic_block bb
)
801 edge succ
= single_succ_edge (bb
);
802 basic_block dest
= succ
->dest
;
804 basic_block dombb
, domdest
, dom
;
806 /* We check for infinite loops already in tree_forwarder_block_p.
807 However it may happen that the infinite loop is created
808 afterwards due to removal of forwarders. */
812 /* If the destination block consists of a nonlocal label, do not
814 label
= first_stmt (dest
);
816 && gimple_code (label
) == GIMPLE_LABEL
817 && DECL_NONLOCAL (gimple_label_label (label
)))
820 /* Record BB's single pred in case we need to update the father
821 loop's latch information later. */
822 basic_block pred
= NULL
;
823 if (single_pred_p (bb
))
824 pred
= single_pred (bb
);
826 /* Redirect each incoming edge to BB to DEST. */
827 while (EDGE_COUNT (bb
->preds
) > 0)
829 edge e
= EDGE_PRED (bb
, 0), s
;
830 gimple_stmt_iterator gsi
;
832 s
= find_edge (e
->src
, dest
);
835 /* We already have an edge S from E->src to DEST. If S and
836 E->dest's sole successor edge have the same PHI arguments
837 at DEST, redirect S to DEST. */
838 if (phi_alternatives_equal (dest
, s
, succ
))
840 e
= redirect_edge_and_branch (e
, dest
);
841 redirect_edge_var_map_clear (e
);
845 /* PHI arguments are different. Create a forwarder block by
846 splitting E so that we can merge PHI arguments on E to
848 e
= single_succ_edge (split_edge (e
));
851 s
= redirect_edge_and_branch (e
, dest
);
853 /* redirect_edge_and_branch must not create a new edge. */
856 /* Add to the PHI nodes at DEST each PHI argument removed at the
858 for (gsi
= gsi_start_phis (dest
);
862 gimple phi
= gsi_stmt (gsi
);
863 tree def
= gimple_phi_arg_def (phi
, succ
->dest_idx
);
864 source_location locus
= gimple_phi_arg_location_from_edge (phi
, succ
);
866 if (TREE_CODE (def
) == SSA_NAME
)
868 edge_var_map_vector
*head
;
872 /* If DEF is one of the results of PHI nodes removed during
873 redirection, replace it with the PHI argument that used
875 head
= redirect_edge_var_map_vector (e
);
876 FOR_EACH_VEC_SAFE_ELT (head
, i
, vm
)
878 tree old_arg
= redirect_edge_var_map_result (vm
);
879 tree new_arg
= redirect_edge_var_map_def (vm
);
884 locus
= redirect_edge_var_map_location (vm
);
890 add_phi_arg (phi
, def
, s
, locus
);
893 redirect_edge_var_map_clear (e
);
896 /* Update the dominators. */
897 dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
898 domdest
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
901 /* Shortcut to avoid calling (relatively expensive)
902 nearest_common_dominator unless necessary. */
906 dom
= nearest_common_dominator (CDI_DOMINATORS
, domdest
, dombb
);
908 set_immediate_dominator (CDI_DOMINATORS
, dest
, dom
);
910 /* Adjust latch infomation of BB's parent loop as otherwise
911 the cfg hook has a hard time not to kill the loop. */
912 if (current_loops
&& bb
->loop_father
->latch
== bb
)
913 bb
->loop_father
->latch
= pred
;
915 /* Remove BB since all of BB's incoming edges have been redirected
917 delete_basic_block (bb
);
922 /* This pass merges PHI nodes if one feeds into another. For example,
923 suppose we have the following:
930 # tem_6 = PHI <tem_17(8), tem_23(7)>;
933 # tem_3 = PHI <tem_6(9), tem_2(5)>;
936 Then we merge the first PHI node into the second one like so:
943 # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
948 merge_phi_nodes (void)
950 basic_block
*worklist
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
));
951 basic_block
*current
= worklist
;
954 calculate_dominance_info (CDI_DOMINATORS
);
956 /* Find all PHI nodes that we may be able to merge. */
957 FOR_EACH_BB_FN (bb
, cfun
)
961 /* Look for a forwarder block with PHI nodes. */
962 if (!tree_forwarder_block_p (bb
, true))
965 dest
= single_succ (bb
);
967 /* We have to feed into another basic block with PHI
969 if (gimple_seq_empty_p (phi_nodes (dest
))
970 /* We don't want to deal with a basic block with
972 || bb_has_abnormal_pred (bb
))
975 if (!dominated_by_p (CDI_DOMINATORS
, dest
, bb
))
977 /* If BB does not dominate DEST, then the PHI nodes at
978 DEST must be the only users of the results of the PHI
984 gimple_stmt_iterator gsi
;
985 unsigned int dest_idx
= single_succ_edge (bb
)->dest_idx
;
987 /* BB dominates DEST. There may be many users of the PHI
988 nodes in BB. However, there is still a trivial case we
989 can handle. If the result of every PHI in BB is used
990 only by a PHI in DEST, then we can trivially merge the
991 PHI nodes from BB into DEST. */
992 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
995 gimple phi
= gsi_stmt (gsi
);
996 tree result
= gimple_phi_result (phi
);
997 use_operand_p imm_use
;
1000 /* If the PHI's result is never used, then we can just
1002 if (has_zero_uses (result
))
1005 /* Get the single use of the result of this PHI node. */
1006 if (!single_imm_use (result
, &imm_use
, &use_stmt
)
1007 || gimple_code (use_stmt
) != GIMPLE_PHI
1008 || gimple_bb (use_stmt
) != dest
1009 || gimple_phi_arg_def (use_stmt
, dest_idx
) != result
)
1013 /* If the loop above iterated through all the PHI nodes
1014 in BB, then we can merge the PHIs from BB into DEST. */
1015 if (gsi_end_p (gsi
))
1020 /* Now let's drain WORKLIST. */
1021 bool changed
= false;
1022 while (current
!= worklist
)
1025 changed
|= remove_forwarder_block_with_phi (bb
);
1029 /* Removing forwarder blocks can cause formerly irreducible loops
1030 to become reducible if we merged two entry blocks. */
1033 loops_state_set (LOOPS_NEED_FIXUP
);
1039 gate_merge_phi (void)
1046 const pass_data pass_data_merge_phi
=
1048 GIMPLE_PASS
, /* type */
1049 "mergephi", /* name */
1050 OPTGROUP_NONE
, /* optinfo_flags */
1051 true, /* has_execute */
1052 TV_TREE_MERGE_PHI
, /* tv_id */
1053 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1054 0, /* properties_provided */
1055 0, /* properties_destroyed */
1056 0, /* todo_flags_start */
1057 TODO_verify_ssa
, /* todo_flags_finish */
1060 class pass_merge_phi
: public gimple_opt_pass
1063 pass_merge_phi (gcc::context
*ctxt
)
1064 : gimple_opt_pass (pass_data_merge_phi
, ctxt
)
1067 /* opt_pass methods: */
1068 opt_pass
* clone () { return new pass_merge_phi (m_ctxt
); }
1069 bool gate () { return gate_merge_phi (); }
1070 unsigned int execute () { return merge_phi_nodes (); }
1072 }; // class pass_merge_phi
1077 make_pass_merge_phi (gcc::context
*ctxt
)
1079 return new pass_merge_phi (ctxt
);
1082 /* Pass: cleanup the CFG just before expanding trees to RTL.
1083 This is just a round of label cleanups and case node grouping
1084 because after the tree optimizers have run such cleanups may
1088 execute_cleanup_cfg_post_optimizing (void)
1090 unsigned int todo
= 0;
1091 if (cleanup_tree_cfg ())
1092 todo
|= TODO_update_ssa
;
1093 maybe_remove_unreachable_handlers ();
1094 cleanup_dead_labels ();
1095 group_case_labels ();
1096 if ((flag_compare_debug_opt
|| flag_compare_debug
)
1097 && flag_dump_final_insns
)
1099 FILE *final_output
= fopen (flag_dump_final_insns
, "a");
1103 error ("could not open final insn dump file %qs: %m",
1104 flag_dump_final_insns
);
1105 flag_dump_final_insns
= NULL
;
1109 int save_unnumbered
= flag_dump_unnumbered
;
1110 int save_noaddr
= flag_dump_noaddr
;
1112 flag_dump_noaddr
= flag_dump_unnumbered
= 1;
1113 fprintf (final_output
, "\n");
1114 dump_enumerated_decls (final_output
, dump_flags
| TDF_NOUID
);
1115 flag_dump_noaddr
= save_noaddr
;
1116 flag_dump_unnumbered
= save_unnumbered
;
1117 if (fclose (final_output
))
1119 error ("could not close final insn dump file %qs: %m",
1120 flag_dump_final_insns
);
1121 flag_dump_final_insns
= NULL
;
1130 const pass_data pass_data_cleanup_cfg_post_optimizing
=
1132 GIMPLE_PASS
, /* type */
1133 "optimized", /* name */
1134 OPTGROUP_NONE
, /* optinfo_flags */
1135 true, /* has_execute */
1136 TV_TREE_CLEANUP_CFG
, /* tv_id */
1137 PROP_cfg
, /* properties_required */
1138 0, /* properties_provided */
1139 0, /* properties_destroyed */
1140 0, /* todo_flags_start */
1141 TODO_remove_unused_locals
, /* todo_flags_finish */
1144 class pass_cleanup_cfg_post_optimizing
: public gimple_opt_pass
1147 pass_cleanup_cfg_post_optimizing (gcc::context
*ctxt
)
1148 : gimple_opt_pass (pass_data_cleanup_cfg_post_optimizing
, ctxt
)
1151 /* opt_pass methods: */
1152 unsigned int execute () {
1153 return execute_cleanup_cfg_post_optimizing ();
1156 }; // class pass_cleanup_cfg_post_optimizing
1161 make_pass_cleanup_cfg_post_optimizing (gcc::context
*ctxt
)
1163 return new pass_cleanup_cfg_post_optimizing (ctxt
);