1 /* CFG cleanup for trees.
2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
28 #include "hard-reg-set.h"
29 #include "basic-block.h"
36 #include "langhooks.h"
37 #include "diagnostic.h"
38 #include "tree-flow.h"
40 #include "tree-dump.h"
41 #include "tree-pass.h"
45 #include "cfglayout.h"
47 #include "tree-ssa-propagate.h"
48 #include "tree-scalar-evolution.h"
50 /* The set of blocks in that at least one of the following changes happened:
51 -- the statement at the end of the block was changed
52 -- the block was newly created
53 -- the set of the predecessors of the block changed
54 -- the set of the successors of the block changed
55 ??? Maybe we could track these changes separately, since they determine
56 what cleanups it makes sense to try on the block. */
57 bitmap cfgcleanup_altered_bbs
;
59 /* Remove any fallthru edge from EV. Return true if an edge was removed. */
62 remove_fallthru_edge (VEC(edge
,gc
) *ev
)
67 FOR_EACH_EDGE (e
, ei
, ev
)
68 if ((e
->flags
& EDGE_FALLTHRU
) != 0)
70 remove_edge_and_dominated_blocks (e
);
77 /* Disconnect an unreachable block in the control expression starting
81 cleanup_control_expr_graph (basic_block bb
, gimple_stmt_iterator gsi
)
85 gimple stmt
= gsi_stmt (gsi
);
88 if (!single_succ_p (bb
))
95 fold_defer_overflow_warnings ();
96 loc
= gimple_location (stmt
);
97 switch (gimple_code (stmt
))
101 tree lhs
= gimple_cond_lhs (stmt
);
102 tree rhs
= gimple_cond_rhs (stmt
);
103 /* For conditions try harder and lookup single-argument
104 PHI nodes. Only do so from the same basic-block though
105 as other basic-blocks may be dead already. */
106 if (TREE_CODE (lhs
) == SSA_NAME
107 && !name_registered_for_update_p (lhs
))
109 gimple def_stmt
= SSA_NAME_DEF_STMT (lhs
);
110 if (gimple_code (def_stmt
) == GIMPLE_PHI
111 && gimple_phi_num_args (def_stmt
) == 1
112 && gimple_bb (def_stmt
) == gimple_bb (stmt
)
113 && (TREE_CODE (PHI_ARG_DEF (def_stmt
, 0)) != SSA_NAME
114 || !name_registered_for_update_p (PHI_ARG_DEF (def_stmt
,
116 lhs
= PHI_ARG_DEF (def_stmt
, 0);
118 if (TREE_CODE (rhs
) == SSA_NAME
119 && !name_registered_for_update_p (rhs
))
121 gimple def_stmt
= SSA_NAME_DEF_STMT (rhs
);
122 if (gimple_code (def_stmt
) == GIMPLE_PHI
123 && gimple_phi_num_args (def_stmt
) == 1
124 && gimple_bb (def_stmt
) == gimple_bb (stmt
)
125 && (TREE_CODE (PHI_ARG_DEF (def_stmt
, 0)) != SSA_NAME
126 || !name_registered_for_update_p (PHI_ARG_DEF (def_stmt
,
128 rhs
= PHI_ARG_DEF (def_stmt
, 0);
130 val
= fold_binary_loc (loc
, gimple_cond_code (stmt
),
131 boolean_type_node
, lhs
, rhs
);
136 val
= gimple_switch_index (stmt
);
142 taken_edge
= find_taken_edge (bb
, val
);
145 fold_undefer_and_ignore_overflow_warnings ();
149 /* Remove all the edges except the one that is always executed. */
151 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
157 fold_undefer_overflow_warnings
158 (true, stmt
, WARN_STRICT_OVERFLOW_CONDITIONAL
);
162 taken_edge
->probability
+= e
->probability
;
163 taken_edge
->count
+= e
->count
;
164 remove_edge_and_dominated_blocks (e
);
171 fold_undefer_and_ignore_overflow_warnings ();
172 if (taken_edge
->probability
> REG_BR_PROB_BASE
)
173 taken_edge
->probability
= REG_BR_PROB_BASE
;
176 taken_edge
= single_succ_edge (bb
);
178 bitmap_set_bit (cfgcleanup_altered_bbs
, bb
->index
);
179 gsi_remove (&gsi
, true);
180 taken_edge
->flags
= EDGE_FALLTHRU
;
185 /* Try to remove superfluous control structures in basic block BB. Returns
186 true if anything changes. */
189 cleanup_control_flow_bb (basic_block bb
)
191 gimple_stmt_iterator gsi
;
195 /* If the last statement of the block could throw and now cannot,
196 we need to prune cfg. */
197 retval
|= gimple_purge_dead_eh_edges (bb
);
199 gsi
= gsi_last_bb (bb
);
203 stmt
= gsi_stmt (gsi
);
205 if (gimple_code (stmt
) == GIMPLE_COND
206 || gimple_code (stmt
) == GIMPLE_SWITCH
)
207 retval
|= cleanup_control_expr_graph (bb
, gsi
);
208 else if (gimple_code (stmt
) == GIMPLE_GOTO
209 && TREE_CODE (gimple_goto_dest (stmt
)) == ADDR_EXPR
210 && (TREE_CODE (TREE_OPERAND (gimple_goto_dest (stmt
), 0))
213 /* If we had a computed goto which has a compile-time determinable
214 destination, then we can eliminate the goto. */
218 basic_block target_block
;
220 /* First look at all the outgoing edges. Delete any outgoing
221 edges which do not go to the right block. For the one
222 edge which goes to the right block, fix up its flags. */
223 label
= TREE_OPERAND (gimple_goto_dest (stmt
), 0);
224 target_block
= label_to_block (label
);
225 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
227 if (e
->dest
!= target_block
)
228 remove_edge_and_dominated_blocks (e
);
231 /* Turn off the EDGE_ABNORMAL flag. */
232 e
->flags
&= ~EDGE_ABNORMAL
;
234 /* And set EDGE_FALLTHRU. */
235 e
->flags
|= EDGE_FALLTHRU
;
240 bitmap_set_bit (cfgcleanup_altered_bbs
, bb
->index
);
241 bitmap_set_bit (cfgcleanup_altered_bbs
, target_block
->index
);
243 /* Remove the GOTO_EXPR as it is not needed. The CFG has all the
244 relevant information we need. */
245 gsi_remove (&gsi
, true);
249 /* Check for indirect calls that have been turned into
251 else if (is_gimple_call (stmt
)
252 && gimple_call_noreturn_p (stmt
)
253 && remove_fallthru_edge (bb
->succs
))
259 /* Return true if basic block BB does nothing except pass control
260 flow to another block and that we can safely insert a label at
261 the start of the successor block.
263 As a precondition, we require that BB be not equal to
267 tree_forwarder_block_p (basic_block bb
, bool phi_wanted
)
269 gimple_stmt_iterator gsi
;
271 /* BB must have a single outgoing edge. */
272 if (single_succ_p (bb
) != 1
273 /* If PHI_WANTED is false, BB must not have any PHI nodes.
274 Otherwise, BB must have PHI nodes. */
275 || gimple_seq_empty_p (phi_nodes (bb
)) == phi_wanted
276 /* BB may not be a predecessor of EXIT_BLOCK_PTR. */
277 || single_succ (bb
) == EXIT_BLOCK_PTR
278 /* Nor should this be an infinite loop. */
279 || single_succ (bb
) == bb
280 /* BB may not have an abnormal outgoing edge. */
281 || (single_succ_edge (bb
)->flags
& EDGE_ABNORMAL
))
285 gcc_assert (bb
!= ENTRY_BLOCK_PTR
);
288 /* There should not be an edge coming from entry, or an EH edge. */
293 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
294 if (e
->src
== ENTRY_BLOCK_PTR
|| (e
->flags
& EDGE_EH
))
298 /* Now walk through the statements backward. We can ignore labels,
299 anything else means this is not a forwarder block. */
300 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
302 gimple stmt
= gsi_stmt (gsi
);
304 switch (gimple_code (stmt
))
307 if (DECL_NONLOCAL (gimple_label_label (stmt
)))
311 /* ??? For now, hope there's a corresponding debug
312 assignment at the destination. */
324 /* Protect loop latches, headers and preheaders. */
325 if (bb
->loop_father
->header
== bb
)
327 dest
= EDGE_SUCC (bb
, 0)->dest
;
329 if (dest
->loop_father
->header
== dest
)
335 /* Return true if BB has at least one abnormal incoming edge. */
338 has_abnormal_incoming_edge_p (basic_block bb
)
343 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
344 if (e
->flags
& EDGE_ABNORMAL
)
350 /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
351 those alternatives are equal in each of the PHI nodes, then return
352 true, else return false. */
355 phi_alternatives_equal (basic_block dest
, edge e1
, edge e2
)
357 int n1
= e1
->dest_idx
;
358 int n2
= e2
->dest_idx
;
359 gimple_stmt_iterator gsi
;
361 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
363 gimple phi
= gsi_stmt (gsi
);
364 tree val1
= gimple_phi_arg_def (phi
, n1
);
365 tree val2
= gimple_phi_arg_def (phi
, n2
);
367 gcc_assert (val1
!= NULL_TREE
);
368 gcc_assert (val2
!= NULL_TREE
);
370 if (!operand_equal_for_phi_arg_p (val1
, val2
))
377 /* Removes forwarder block BB. Returns false if this failed. */
380 remove_forwarder_block (basic_block bb
)
382 edge succ
= single_succ_edge (bb
), e
, s
;
383 basic_block dest
= succ
->dest
;
386 gimple_stmt_iterator gsi
, gsi_to
;
387 bool can_move_debug_stmts
;
389 /* We check for infinite loops already in tree_forwarder_block_p.
390 However it may happen that the infinite loop is created
391 afterwards due to removal of forwarders. */
395 /* If the destination block consists of a nonlocal label or is a
396 EH landing pad, do not merge it. */
397 label
= first_stmt (dest
);
399 && gimple_code (label
) == GIMPLE_LABEL
400 && (DECL_NONLOCAL (gimple_label_label (label
))
401 || EH_LANDING_PAD_NR (gimple_label_label (label
)) != 0))
404 /* If there is an abnormal edge to basic block BB, but not into
405 dest, problems might occur during removal of the phi node at out
406 of ssa due to overlapping live ranges of registers.
408 If there is an abnormal edge in DEST, the problems would occur
409 anyway since cleanup_dead_labels would then merge the labels for
410 two different eh regions, and rest of exception handling code
413 So if there is an abnormal edge to BB, proceed only if there is
414 no abnormal edge to DEST and there are no phi nodes in DEST. */
415 if (has_abnormal_incoming_edge_p (bb
)
416 && (has_abnormal_incoming_edge_p (dest
)
417 || !gimple_seq_empty_p (phi_nodes (dest
))))
420 /* If there are phi nodes in DEST, and some of the blocks that are
421 predecessors of BB are also predecessors of DEST, check that the
422 phi node arguments match. */
423 if (!gimple_seq_empty_p (phi_nodes (dest
)))
425 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
427 s
= find_edge (e
->src
, dest
);
431 if (!phi_alternatives_equal (dest
, succ
, s
))
436 can_move_debug_stmts
= single_pred_p (dest
);
438 /* Redirect the edges. */
439 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
441 bitmap_set_bit (cfgcleanup_altered_bbs
, e
->src
->index
);
443 if (e
->flags
& EDGE_ABNORMAL
)
445 /* If there is an abnormal edge, redirect it anyway, and
446 move the labels to the new block to make it legal. */
447 s
= redirect_edge_succ_nodup (e
, dest
);
450 s
= redirect_edge_and_branch (e
, dest
);
454 /* Create arguments for the phi nodes, since the edge was not
456 for (gsi
= gsi_start_phis (dest
);
460 gimple phi
= gsi_stmt (gsi
);
461 source_location l
= gimple_phi_arg_location_from_edge (phi
, succ
);
462 add_phi_arg (phi
, gimple_phi_arg_def (phi
, succ
->dest_idx
), s
, l
);
467 /* Move nonlocal labels and computed goto targets as well as user
468 defined labels and labels with an EH landing pad number to the
469 new block, so that the redirection of the abnormal edges works,
470 jump targets end up in a sane place and debug information for
471 labels is retained. */
472 gsi_to
= gsi_start_bb (dest
);
473 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
476 label
= gsi_stmt (gsi
);
477 if (is_gimple_debug (label
))
479 decl
= gimple_label_label (label
);
480 if (EH_LANDING_PAD_NR (decl
) != 0
481 || DECL_NONLOCAL (decl
)
482 || FORCED_LABEL (decl
)
483 || !DECL_ARTIFICIAL (decl
))
485 gsi_remove (&gsi
, false);
486 gsi_insert_before (&gsi_to
, label
, GSI_SAME_STMT
);
492 /* Move debug statements if the destination has just a single
494 if (can_move_debug_stmts
)
496 gsi_to
= gsi_after_labels (dest
);
497 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); )
499 gimple debug
= gsi_stmt (gsi
);
500 if (!is_gimple_debug (debug
))
502 gsi_remove (&gsi
, false);
503 gsi_insert_before (&gsi_to
, debug
, GSI_SAME_STMT
);
507 bitmap_set_bit (cfgcleanup_altered_bbs
, dest
->index
);
509 /* Update the dominators. */
510 if (dom_info_available_p (CDI_DOMINATORS
))
512 basic_block dom
, dombb
, domdest
;
514 dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
515 domdest
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
518 /* Shortcut to avoid calling (relatively expensive)
519 nearest_common_dominator unless necessary. */
523 dom
= nearest_common_dominator (CDI_DOMINATORS
, domdest
, dombb
);
525 set_immediate_dominator (CDI_DOMINATORS
, dest
, dom
);
528 /* And kill the forwarder block. */
529 delete_basic_block (bb
);
534 /* Split basic blocks on calls in the middle of a basic block that are now
535 known not to return, and remove the unreachable code. */
538 split_bbs_on_noreturn_calls (void)
540 bool changed
= false;
544 /* Detect cases where a mid-block call is now known not to return. */
546 while (VEC_length (gimple
, MODIFIED_NORETURN_CALLS (cfun
)))
548 stmt
= VEC_pop (gimple
, MODIFIED_NORETURN_CALLS (cfun
));
549 bb
= gimple_bb (stmt
);
550 /* BB might be deleted at this point, so verify first
551 BB is present in the cfg. */
553 || bb
->index
< NUM_FIXED_BLOCKS
554 || bb
->index
>= n_basic_blocks
555 || BASIC_BLOCK (bb
->index
) != bb
556 || last_stmt (bb
) == stmt
557 || !gimple_call_noreturn_p (stmt
))
561 split_block (bb
, stmt
);
562 remove_fallthru_edge (bb
->succs
);
568 /* If GIMPLE_OMP_RETURN in basic block BB is unreachable, remove it. */
571 cleanup_omp_return (basic_block bb
)
573 gimple stmt
= last_stmt (bb
);
574 basic_block control_bb
;
577 || gimple_code (stmt
) != GIMPLE_OMP_RETURN
578 || !single_pred_p (bb
))
581 control_bb
= single_pred (bb
);
582 stmt
= last_stmt (control_bb
);
584 if (stmt
== NULL
|| gimple_code (stmt
) != GIMPLE_OMP_SECTIONS_SWITCH
)
587 /* The block with the control statement normally has two entry edges -- one
588 from entry, one from continue. If continue is removed, return is
589 unreachable, so we remove it here as well. */
590 if (EDGE_COUNT (control_bb
->preds
) == 2)
593 gcc_assert (EDGE_COUNT (control_bb
->preds
) == 1);
594 remove_edge_and_dominated_blocks (single_pred_edge (bb
));
598 /* Tries to cleanup cfg in basic block BB. Returns true if anything
602 cleanup_tree_cfg_bb (basic_block bb
)
606 if (cleanup_omp_return (bb
))
609 retval
= cleanup_control_flow_bb (bb
);
611 /* Forwarder blocks can carry line number information which is
612 useful when debugging, so we only clean them up when
615 && tree_forwarder_block_p (bb
, false)
616 && remove_forwarder_block (bb
))
619 /* Merging the blocks may create new opportunities for folding
620 conditional branches (due to the elimination of single-valued PHI
622 if (single_succ_p (bb
)
623 && can_merge_blocks_p (bb
, single_succ (bb
)))
625 merge_blocks (bb
, single_succ (bb
));
632 /* Iterate the cfg cleanups, while anything changes. */
635 cleanup_tree_cfg_1 (void)
641 retval
|= split_bbs_on_noreturn_calls ();
643 /* Prepare the worklists of altered blocks. */
644 cfgcleanup_altered_bbs
= BITMAP_ALLOC (NULL
);
646 /* During forwarder block cleanup, we may redirect edges out of
647 SWITCH_EXPRs, which can get expensive. So we want to enable
648 recording of edge to CASE_LABEL_EXPR. */
649 start_recording_case_labels ();
651 /* Start by iterating over all basic blocks. We cannot use FOR_EACH_BB,
652 since the basic blocks may get removed. */
653 n
= last_basic_block
;
654 for (i
= NUM_FIXED_BLOCKS
; i
< n
; i
++)
656 bb
= BASIC_BLOCK (i
);
658 retval
|= cleanup_tree_cfg_bb (bb
);
661 /* Now process the altered blocks, as long as any are available. */
662 while (!bitmap_empty_p (cfgcleanup_altered_bbs
))
664 i
= bitmap_first_set_bit (cfgcleanup_altered_bbs
);
665 bitmap_clear_bit (cfgcleanup_altered_bbs
, i
);
666 if (i
< NUM_FIXED_BLOCKS
)
669 bb
= BASIC_BLOCK (i
);
673 retval
|= cleanup_tree_cfg_bb (bb
);
675 /* Rerun split_bbs_on_noreturn_calls, in case we have altered any noreturn
677 retval
|= split_bbs_on_noreturn_calls ();
680 end_recording_case_labels ();
681 BITMAP_FREE (cfgcleanup_altered_bbs
);
686 /* Remove unreachable blocks and other miscellaneous clean up work.
687 Return true if the flowgraph was modified, false otherwise. */
690 cleanup_tree_cfg_noloop (void)
694 timevar_push (TV_TREE_CLEANUP_CFG
);
696 /* Iterate until there are no more cleanups left to do. If any
697 iteration changed the flowgraph, set CHANGED to true.
699 If dominance information is available, there cannot be any unreachable
701 if (!dom_info_available_p (CDI_DOMINATORS
))
703 changed
= delete_unreachable_blocks ();
704 calculate_dominance_info (CDI_DOMINATORS
);
708 #ifdef ENABLE_CHECKING
709 verify_dominators (CDI_DOMINATORS
);
714 changed
|= cleanup_tree_cfg_1 ();
716 gcc_assert (dom_info_available_p (CDI_DOMINATORS
));
719 #ifdef ENABLE_CHECKING
723 timevar_pop (TV_TREE_CLEANUP_CFG
);
725 if (changed
&& current_loops
)
726 loops_state_set (LOOPS_NEED_FIXUP
);
731 /* Repairs loop structures. */
734 repair_loop_structures (void)
736 bitmap changed_bbs
= BITMAP_ALLOC (NULL
);
737 fix_loop_structure (changed_bbs
);
739 /* This usually does nothing. But sometimes parts of cfg that originally
740 were inside a loop get out of it due to edge removal (since they
741 become unreachable by back edges from latch). */
742 if (loops_state_satisfies_p (LOOP_CLOSED_SSA
))
743 rewrite_into_loop_closed_ssa (changed_bbs
, TODO_update_ssa
);
745 BITMAP_FREE (changed_bbs
);
747 #ifdef ENABLE_CHECKING
748 verify_loop_structure ();
752 loops_state_clear (LOOPS_NEED_FIXUP
);
755 /* Cleanup cfg and repair loop structures. */
758 cleanup_tree_cfg (void)
760 bool changed
= cleanup_tree_cfg_noloop ();
762 if (current_loops
!= NULL
763 && loops_state_satisfies_p (LOOPS_NEED_FIXUP
))
764 repair_loop_structures ();
769 /* Merge the PHI nodes at BB into those at BB's sole successor. */
772 remove_forwarder_block_with_phi (basic_block bb
)
774 edge succ
= single_succ_edge (bb
);
775 basic_block dest
= succ
->dest
;
777 basic_block dombb
, domdest
, dom
;
779 /* We check for infinite loops already in tree_forwarder_block_p.
780 However it may happen that the infinite loop is created
781 afterwards due to removal of forwarders. */
785 /* If the destination block consists of a nonlocal label, do not
787 label
= first_stmt (dest
);
789 && gimple_code (label
) == GIMPLE_LABEL
790 && DECL_NONLOCAL (gimple_label_label (label
)))
793 /* Redirect each incoming edge to BB to DEST. */
794 while (EDGE_COUNT (bb
->preds
) > 0)
796 edge e
= EDGE_PRED (bb
, 0), s
;
797 gimple_stmt_iterator gsi
;
799 s
= find_edge (e
->src
, dest
);
802 /* We already have an edge S from E->src to DEST. If S and
803 E->dest's sole successor edge have the same PHI arguments
804 at DEST, redirect S to DEST. */
805 if (phi_alternatives_equal (dest
, s
, succ
))
807 e
= redirect_edge_and_branch (e
, dest
);
808 redirect_edge_var_map_clear (e
);
812 /* PHI arguments are different. Create a forwarder block by
813 splitting E so that we can merge PHI arguments on E to
815 e
= single_succ_edge (split_edge (e
));
818 s
= redirect_edge_and_branch (e
, dest
);
820 /* redirect_edge_and_branch must not create a new edge. */
823 /* Add to the PHI nodes at DEST each PHI argument removed at the
825 for (gsi
= gsi_start_phis (dest
);
829 gimple phi
= gsi_stmt (gsi
);
830 tree def
= gimple_phi_arg_def (phi
, succ
->dest_idx
);
831 source_location locus
= gimple_phi_arg_location_from_edge (phi
, succ
);
833 if (TREE_CODE (def
) == SSA_NAME
)
835 edge_var_map_vector head
;
839 /* If DEF is one of the results of PHI nodes removed during
840 redirection, replace it with the PHI argument that used
842 head
= redirect_edge_var_map_vector (e
);
843 for (i
= 0; VEC_iterate (edge_var_map
, head
, i
, vm
); ++i
)
845 tree old_arg
= redirect_edge_var_map_result (vm
);
846 tree new_arg
= redirect_edge_var_map_def (vm
);
851 locus
= redirect_edge_var_map_location (vm
);
857 add_phi_arg (phi
, def
, s
, locus
);
860 redirect_edge_var_map_clear (e
);
863 /* Update the dominators. */
864 dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
865 domdest
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
868 /* Shortcut to avoid calling (relatively expensive)
869 nearest_common_dominator unless necessary. */
873 dom
= nearest_common_dominator (CDI_DOMINATORS
, domdest
, dombb
);
875 set_immediate_dominator (CDI_DOMINATORS
, dest
, dom
);
877 /* Remove BB since all of BB's incoming edges have been redirected
879 delete_basic_block (bb
);
882 /* This pass merges PHI nodes if one feeds into another. For example,
883 suppose we have the following:
890 # tem_6 = PHI <tem_17(8), tem_23(7)>;
893 # tem_3 = PHI <tem_6(9), tem_2(5)>;
896 Then we merge the first PHI node into the second one like so:
903 # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
908 merge_phi_nodes (void)
910 basic_block
*worklist
= XNEWVEC (basic_block
, n_basic_blocks
);
911 basic_block
*current
= worklist
;
914 calculate_dominance_info (CDI_DOMINATORS
);
916 /* Find all PHI nodes that we may be able to merge. */
921 /* Look for a forwarder block with PHI nodes. */
922 if (!tree_forwarder_block_p (bb
, true))
925 dest
= single_succ (bb
);
927 /* We have to feed into another basic block with PHI
929 if (gimple_seq_empty_p (phi_nodes (dest
))
930 /* We don't want to deal with a basic block with
932 || has_abnormal_incoming_edge_p (bb
))
935 if (!dominated_by_p (CDI_DOMINATORS
, dest
, bb
))
937 /* If BB does not dominate DEST, then the PHI nodes at
938 DEST must be the only users of the results of the PHI
944 gimple_stmt_iterator gsi
;
945 unsigned int dest_idx
= single_succ_edge (bb
)->dest_idx
;
947 /* BB dominates DEST. There may be many users of the PHI
948 nodes in BB. However, there is still a trivial case we
949 can handle. If the result of every PHI in BB is used
950 only by a PHI in DEST, then we can trivially merge the
951 PHI nodes from BB into DEST. */
952 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
955 gimple phi
= gsi_stmt (gsi
);
956 tree result
= gimple_phi_result (phi
);
957 use_operand_p imm_use
;
960 /* If the PHI's result is never used, then we can just
962 if (has_zero_uses (result
))
965 /* Get the single use of the result of this PHI node. */
966 if (!single_imm_use (result
, &imm_use
, &use_stmt
)
967 || gimple_code (use_stmt
) != GIMPLE_PHI
968 || gimple_bb (use_stmt
) != dest
969 || gimple_phi_arg_def (use_stmt
, dest_idx
) != result
)
973 /* If the loop above iterated through all the PHI nodes
974 in BB, then we can merge the PHIs from BB into DEST. */
980 /* Now let's drain WORKLIST. */
981 while (current
!= worklist
)
984 remove_forwarder_block_with_phi (bb
);
992 gate_merge_phi (void)
997 struct gimple_opt_pass pass_merge_phi
=
1001 "mergephi", /* name */
1002 gate_merge_phi
, /* gate */
1003 merge_phi_nodes
, /* execute */
1006 0, /* static_pass_number */
1007 TV_TREE_MERGE_PHI
, /* tv_id */
1008 PROP_cfg
| PROP_ssa
, /* properties_required */
1009 0, /* properties_provided */
1010 0, /* properties_destroyed */
1011 0, /* todo_flags_start */
1012 TODO_dump_func
| TODO_ggc_collect
/* todo_flags_finish */