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
)
108 gimple def_stmt
= SSA_NAME_DEF_STMT (lhs
);
109 if (gimple_code (def_stmt
) == GIMPLE_PHI
110 && gimple_phi_num_args (def_stmt
) == 1
111 && gimple_bb (def_stmt
) == gimple_bb (stmt
))
112 lhs
= PHI_ARG_DEF (def_stmt
, 0);
114 if (TREE_CODE (rhs
) == SSA_NAME
)
116 gimple def_stmt
= SSA_NAME_DEF_STMT (rhs
);
117 if (gimple_code (def_stmt
) == GIMPLE_PHI
118 && gimple_phi_num_args (def_stmt
) == 1
119 && gimple_bb (def_stmt
) == gimple_bb (stmt
))
120 rhs
= PHI_ARG_DEF (def_stmt
, 0);
122 val
= fold_binary_loc (loc
, gimple_cond_code (stmt
),
123 boolean_type_node
, lhs
, rhs
);
128 val
= gimple_switch_index (stmt
);
134 taken_edge
= find_taken_edge (bb
, val
);
137 fold_undefer_and_ignore_overflow_warnings ();
141 /* Remove all the edges except the one that is always executed. */
143 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
149 fold_undefer_overflow_warnings
150 (true, stmt
, WARN_STRICT_OVERFLOW_CONDITIONAL
);
154 taken_edge
->probability
+= e
->probability
;
155 taken_edge
->count
+= e
->count
;
156 remove_edge_and_dominated_blocks (e
);
163 fold_undefer_and_ignore_overflow_warnings ();
164 if (taken_edge
->probability
> REG_BR_PROB_BASE
)
165 taken_edge
->probability
= REG_BR_PROB_BASE
;
168 taken_edge
= single_succ_edge (bb
);
170 bitmap_set_bit (cfgcleanup_altered_bbs
, bb
->index
);
171 gsi_remove (&gsi
, true);
172 taken_edge
->flags
= EDGE_FALLTHRU
;
177 /* Try to remove superfluous control structures in basic block BB. Returns
178 true if anything changes. */
181 cleanup_control_flow_bb (basic_block bb
)
183 gimple_stmt_iterator gsi
;
187 /* If the last statement of the block could throw and now cannot,
188 we need to prune cfg. */
189 retval
|= gimple_purge_dead_eh_edges (bb
);
191 gsi
= gsi_last_bb (bb
);
195 stmt
= gsi_stmt (gsi
);
197 if (gimple_code (stmt
) == GIMPLE_COND
198 || gimple_code (stmt
) == GIMPLE_SWITCH
)
199 retval
|= cleanup_control_expr_graph (bb
, gsi
);
200 else if (gimple_code (stmt
) == GIMPLE_GOTO
201 && TREE_CODE (gimple_goto_dest (stmt
)) == ADDR_EXPR
202 && (TREE_CODE (TREE_OPERAND (gimple_goto_dest (stmt
), 0))
205 /* If we had a computed goto which has a compile-time determinable
206 destination, then we can eliminate the goto. */
210 basic_block target_block
;
212 /* First look at all the outgoing edges. Delete any outgoing
213 edges which do not go to the right block. For the one
214 edge which goes to the right block, fix up its flags. */
215 label
= TREE_OPERAND (gimple_goto_dest (stmt
), 0);
216 target_block
= label_to_block (label
);
217 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
219 if (e
->dest
!= target_block
)
220 remove_edge_and_dominated_blocks (e
);
223 /* Turn off the EDGE_ABNORMAL flag. */
224 e
->flags
&= ~EDGE_ABNORMAL
;
226 /* And set EDGE_FALLTHRU. */
227 e
->flags
|= EDGE_FALLTHRU
;
232 bitmap_set_bit (cfgcleanup_altered_bbs
, bb
->index
);
233 bitmap_set_bit (cfgcleanup_altered_bbs
, target_block
->index
);
235 /* Remove the GOTO_EXPR as it is not needed. The CFG has all the
236 relevant information we need. */
237 gsi_remove (&gsi
, true);
241 /* Check for indirect calls that have been turned into
243 else if (is_gimple_call (stmt
)
244 && gimple_call_noreturn_p (stmt
)
245 && remove_fallthru_edge (bb
->succs
))
251 /* Return true if basic block BB does nothing except pass control
252 flow to another block and that we can safely insert a label at
253 the start of the successor block.
255 As a precondition, we require that BB be not equal to
259 tree_forwarder_block_p (basic_block bb
, bool phi_wanted
)
261 gimple_stmt_iterator gsi
;
263 /* BB must have a single outgoing edge. */
264 if (single_succ_p (bb
) != 1
265 /* If PHI_WANTED is false, BB must not have any PHI nodes.
266 Otherwise, BB must have PHI nodes. */
267 || gimple_seq_empty_p (phi_nodes (bb
)) == phi_wanted
268 /* BB may not be a predecessor of EXIT_BLOCK_PTR. */
269 || single_succ (bb
) == EXIT_BLOCK_PTR
270 /* Nor should this be an infinite loop. */
271 || single_succ (bb
) == bb
272 /* BB may not have an abnormal outgoing edge. */
273 || (single_succ_edge (bb
)->flags
& EDGE_ABNORMAL
))
277 gcc_assert (bb
!= ENTRY_BLOCK_PTR
);
280 /* There should not be an edge coming from entry, or an EH edge. */
285 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
286 if (e
->src
== ENTRY_BLOCK_PTR
|| (e
->flags
& EDGE_EH
))
290 /* Now walk through the statements backward. We can ignore labels,
291 anything else means this is not a forwarder block. */
292 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
294 gimple stmt
= gsi_stmt (gsi
);
296 switch (gimple_code (stmt
))
299 if (DECL_NONLOCAL (gimple_label_label (stmt
)))
303 /* ??? For now, hope there's a corresponding debug
304 assignment at the destination. */
316 /* Protect loop latches, headers and preheaders. */
317 if (bb
->loop_father
->header
== bb
)
319 dest
= EDGE_SUCC (bb
, 0)->dest
;
321 if (dest
->loop_father
->header
== dest
)
327 /* Return true if BB has at least one abnormal incoming edge. */
330 has_abnormal_incoming_edge_p (basic_block bb
)
335 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
336 if (e
->flags
& EDGE_ABNORMAL
)
342 /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
343 those alternatives are equal in each of the PHI nodes, then return
344 true, else return false. */
347 phi_alternatives_equal (basic_block dest
, edge e1
, edge e2
)
349 int n1
= e1
->dest_idx
;
350 int n2
= e2
->dest_idx
;
351 gimple_stmt_iterator gsi
;
353 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
355 gimple phi
= gsi_stmt (gsi
);
356 tree val1
= gimple_phi_arg_def (phi
, n1
);
357 tree val2
= gimple_phi_arg_def (phi
, n2
);
359 gcc_assert (val1
!= NULL_TREE
);
360 gcc_assert (val2
!= NULL_TREE
);
362 if (!operand_equal_for_phi_arg_p (val1
, val2
))
369 /* Removes forwarder block BB. Returns false if this failed. */
372 remove_forwarder_block (basic_block bb
)
374 edge succ
= single_succ_edge (bb
), e
, s
;
375 basic_block dest
= succ
->dest
;
378 gimple_stmt_iterator gsi
, gsi_to
;
379 bool can_move_debug_stmts
;
381 /* We check for infinite loops already in tree_forwarder_block_p.
382 However it may happen that the infinite loop is created
383 afterwards due to removal of forwarders. */
387 /* If the destination block consists of a nonlocal label or is a
388 EH landing pad, do not merge it. */
389 label
= first_stmt (dest
);
391 && gimple_code (label
) == GIMPLE_LABEL
392 && (DECL_NONLOCAL (gimple_label_label (label
))
393 || EH_LANDING_PAD_NR (gimple_label_label (label
)) != 0))
396 /* If there is an abnormal edge to basic block BB, but not into
397 dest, problems might occur during removal of the phi node at out
398 of ssa due to overlapping live ranges of registers.
400 If there is an abnormal edge in DEST, the problems would occur
401 anyway since cleanup_dead_labels would then merge the labels for
402 two different eh regions, and rest of exception handling code
405 So if there is an abnormal edge to BB, proceed only if there is
406 no abnormal edge to DEST and there are no phi nodes in DEST. */
407 if (has_abnormal_incoming_edge_p (bb
)
408 && (has_abnormal_incoming_edge_p (dest
)
409 || !gimple_seq_empty_p (phi_nodes (dest
))))
412 /* If there are phi nodes in DEST, and some of the blocks that are
413 predecessors of BB are also predecessors of DEST, check that the
414 phi node arguments match. */
415 if (!gimple_seq_empty_p (phi_nodes (dest
)))
417 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
419 s
= find_edge (e
->src
, dest
);
423 if (!phi_alternatives_equal (dest
, succ
, s
))
428 can_move_debug_stmts
= single_pred_p (dest
);
430 /* Redirect the edges. */
431 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
433 bitmap_set_bit (cfgcleanup_altered_bbs
, e
->src
->index
);
435 if (e
->flags
& EDGE_ABNORMAL
)
437 /* If there is an abnormal edge, redirect it anyway, and
438 move the labels to the new block to make it legal. */
439 s
= redirect_edge_succ_nodup (e
, dest
);
442 s
= redirect_edge_and_branch (e
, dest
);
446 /* Create arguments for the phi nodes, since the edge was not
448 for (gsi
= gsi_start_phis (dest
);
452 gimple phi
= gsi_stmt (gsi
);
453 source_location l
= gimple_phi_arg_location_from_edge (phi
, succ
);
454 add_phi_arg (phi
, gimple_phi_arg_def (phi
, succ
->dest_idx
), s
, l
);
459 /* Move nonlocal labels and computed goto targets as well as user
460 defined labels and labels with an EH landing pad number to the
461 new block, so that the redirection of the abnormal edges works,
462 jump targets end up in a sane place and debug information for
463 labels is retained. */
464 gsi_to
= gsi_start_bb (dest
);
465 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
468 label
= gsi_stmt (gsi
);
469 if (is_gimple_debug (label
))
471 decl
= gimple_label_label (label
);
472 if (EH_LANDING_PAD_NR (decl
) != 0
473 || DECL_NONLOCAL (decl
)
474 || FORCED_LABEL (decl
)
475 || !DECL_ARTIFICIAL (decl
))
477 gsi_remove (&gsi
, false);
478 gsi_insert_before (&gsi_to
, label
, GSI_SAME_STMT
);
484 /* Move debug statements if the destination has just a single
486 if (can_move_debug_stmts
)
488 gsi_to
= gsi_after_labels (dest
);
489 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); )
491 gimple debug
= gsi_stmt (gsi
);
492 if (!is_gimple_debug (debug
))
494 gsi_remove (&gsi
, false);
495 gsi_insert_before (&gsi_to
, debug
, GSI_SAME_STMT
);
499 bitmap_set_bit (cfgcleanup_altered_bbs
, dest
->index
);
501 /* Update the dominators. */
502 if (dom_info_available_p (CDI_DOMINATORS
))
504 basic_block dom
, dombb
, domdest
;
506 dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
507 domdest
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
510 /* Shortcut to avoid calling (relatively expensive)
511 nearest_common_dominator unless necessary. */
515 dom
= nearest_common_dominator (CDI_DOMINATORS
, domdest
, dombb
);
517 set_immediate_dominator (CDI_DOMINATORS
, dest
, dom
);
520 /* And kill the forwarder block. */
521 delete_basic_block (bb
);
526 /* Split basic blocks on calls in the middle of a basic block that are now
527 known not to return, and remove the unreachable code. */
530 split_bbs_on_noreturn_calls (void)
532 bool changed
= false;
536 /* Detect cases where a mid-block call is now known not to return. */
538 while (VEC_length (gimple
, MODIFIED_NORETURN_CALLS (cfun
)))
540 stmt
= VEC_pop (gimple
, MODIFIED_NORETURN_CALLS (cfun
));
541 bb
= gimple_bb (stmt
);
542 /* BB might be deleted at this point, so verify first
543 BB is present in the cfg. */
545 || bb
->index
< NUM_FIXED_BLOCKS
546 || bb
->index
>= n_basic_blocks
547 || BASIC_BLOCK (bb
->index
) != bb
548 || last_stmt (bb
) == stmt
549 || !gimple_call_noreturn_p (stmt
))
553 split_block (bb
, stmt
);
554 remove_fallthru_edge (bb
->succs
);
560 /* If GIMPLE_OMP_RETURN in basic block BB is unreachable, remove it. */
563 cleanup_omp_return (basic_block bb
)
565 gimple stmt
= last_stmt (bb
);
566 basic_block control_bb
;
569 || gimple_code (stmt
) != GIMPLE_OMP_RETURN
570 || !single_pred_p (bb
))
573 control_bb
= single_pred (bb
);
574 stmt
= last_stmt (control_bb
);
576 if (stmt
== NULL
|| gimple_code (stmt
) != GIMPLE_OMP_SECTIONS_SWITCH
)
579 /* The block with the control statement normally has two entry edges -- one
580 from entry, one from continue. If continue is removed, return is
581 unreachable, so we remove it here as well. */
582 if (EDGE_COUNT (control_bb
->preds
) == 2)
585 gcc_assert (EDGE_COUNT (control_bb
->preds
) == 1);
586 remove_edge_and_dominated_blocks (single_pred_edge (bb
));
590 /* Tries to cleanup cfg in basic block BB. Returns true if anything
594 cleanup_tree_cfg_bb (basic_block bb
)
598 if (cleanup_omp_return (bb
))
601 retval
= cleanup_control_flow_bb (bb
);
603 /* Forwarder blocks can carry line number information which is
604 useful when debugging, so we only clean them up when
607 && tree_forwarder_block_p (bb
, false)
608 && remove_forwarder_block (bb
))
611 /* Merging the blocks may create new opportunities for folding
612 conditional branches (due to the elimination of single-valued PHI
614 if (single_succ_p (bb
)
615 && can_merge_blocks_p (bb
, single_succ (bb
)))
617 merge_blocks (bb
, single_succ (bb
));
624 /* Iterate the cfg cleanups, while anything changes. */
627 cleanup_tree_cfg_1 (void)
633 retval
|= split_bbs_on_noreturn_calls ();
635 /* Prepare the worklists of altered blocks. */
636 cfgcleanup_altered_bbs
= BITMAP_ALLOC (NULL
);
638 /* During forwarder block cleanup, we may redirect edges out of
639 SWITCH_EXPRs, which can get expensive. So we want to enable
640 recording of edge to CASE_LABEL_EXPR. */
641 start_recording_case_labels ();
643 /* Start by iterating over all basic blocks. We cannot use FOR_EACH_BB,
644 since the basic blocks may get removed. */
645 n
= last_basic_block
;
646 for (i
= NUM_FIXED_BLOCKS
; i
< n
; i
++)
648 bb
= BASIC_BLOCK (i
);
650 retval
|= cleanup_tree_cfg_bb (bb
);
653 /* Now process the altered blocks, as long as any are available. */
654 while (!bitmap_empty_p (cfgcleanup_altered_bbs
))
656 i
= bitmap_first_set_bit (cfgcleanup_altered_bbs
);
657 bitmap_clear_bit (cfgcleanup_altered_bbs
, i
);
658 if (i
< NUM_FIXED_BLOCKS
)
661 bb
= BASIC_BLOCK (i
);
665 retval
|= cleanup_tree_cfg_bb (bb
);
667 /* Rerun split_bbs_on_noreturn_calls, in case we have altered any noreturn
669 retval
|= split_bbs_on_noreturn_calls ();
672 end_recording_case_labels ();
673 BITMAP_FREE (cfgcleanup_altered_bbs
);
678 /* Remove unreachable blocks and other miscellaneous clean up work.
679 Return true if the flowgraph was modified, false otherwise. */
682 cleanup_tree_cfg_noloop (void)
686 timevar_push (TV_TREE_CLEANUP_CFG
);
688 /* Iterate until there are no more cleanups left to do. If any
689 iteration changed the flowgraph, set CHANGED to true.
691 If dominance information is available, there cannot be any unreachable
693 if (!dom_info_available_p (CDI_DOMINATORS
))
695 changed
= delete_unreachable_blocks ();
696 calculate_dominance_info (CDI_DOMINATORS
);
700 #ifdef ENABLE_CHECKING
701 verify_dominators (CDI_DOMINATORS
);
706 changed
|= cleanup_tree_cfg_1 ();
708 gcc_assert (dom_info_available_p (CDI_DOMINATORS
));
711 #ifdef ENABLE_CHECKING
715 timevar_pop (TV_TREE_CLEANUP_CFG
);
717 if (changed
&& current_loops
)
718 loops_state_set (LOOPS_NEED_FIXUP
);
723 /* Repairs loop structures. */
726 repair_loop_structures (void)
728 bitmap changed_bbs
= BITMAP_ALLOC (NULL
);
729 fix_loop_structure (changed_bbs
);
731 /* This usually does nothing. But sometimes parts of cfg that originally
732 were inside a loop get out of it due to edge removal (since they
733 become unreachable by back edges from latch). */
734 if (loops_state_satisfies_p (LOOP_CLOSED_SSA
))
735 rewrite_into_loop_closed_ssa (changed_bbs
, TODO_update_ssa
);
737 BITMAP_FREE (changed_bbs
);
739 #ifdef ENABLE_CHECKING
740 verify_loop_structure ();
744 loops_state_clear (LOOPS_NEED_FIXUP
);
747 /* Cleanup cfg and repair loop structures. */
750 cleanup_tree_cfg (void)
752 bool changed
= cleanup_tree_cfg_noloop ();
754 if (current_loops
!= NULL
755 && loops_state_satisfies_p (LOOPS_NEED_FIXUP
))
756 repair_loop_structures ();
761 /* Merge the PHI nodes at BB into those at BB's sole successor. */
764 remove_forwarder_block_with_phi (basic_block bb
)
766 edge succ
= single_succ_edge (bb
);
767 basic_block dest
= succ
->dest
;
769 basic_block dombb
, domdest
, dom
;
771 /* We check for infinite loops already in tree_forwarder_block_p.
772 However it may happen that the infinite loop is created
773 afterwards due to removal of forwarders. */
777 /* If the destination block consists of a nonlocal label, do not
779 label
= first_stmt (dest
);
781 && gimple_code (label
) == GIMPLE_LABEL
782 && DECL_NONLOCAL (gimple_label_label (label
)))
785 /* Redirect each incoming edge to BB to DEST. */
786 while (EDGE_COUNT (bb
->preds
) > 0)
788 edge e
= EDGE_PRED (bb
, 0), s
;
789 gimple_stmt_iterator gsi
;
791 s
= find_edge (e
->src
, dest
);
794 /* We already have an edge S from E->src to DEST. If S and
795 E->dest's sole successor edge have the same PHI arguments
796 at DEST, redirect S to DEST. */
797 if (phi_alternatives_equal (dest
, s
, succ
))
799 e
= redirect_edge_and_branch (e
, dest
);
800 redirect_edge_var_map_clear (e
);
804 /* PHI arguments are different. Create a forwarder block by
805 splitting E so that we can merge PHI arguments on E to
807 e
= single_succ_edge (split_edge (e
));
810 s
= redirect_edge_and_branch (e
, dest
);
812 /* redirect_edge_and_branch must not create a new edge. */
815 /* Add to the PHI nodes at DEST each PHI argument removed at the
817 for (gsi
= gsi_start_phis (dest
);
821 gimple phi
= gsi_stmt (gsi
);
822 tree def
= gimple_phi_arg_def (phi
, succ
->dest_idx
);
823 source_location locus
= gimple_phi_arg_location_from_edge (phi
, succ
);
825 if (TREE_CODE (def
) == SSA_NAME
)
827 edge_var_map_vector head
;
831 /* If DEF is one of the results of PHI nodes removed during
832 redirection, replace it with the PHI argument that used
834 head
= redirect_edge_var_map_vector (e
);
835 for (i
= 0; VEC_iterate (edge_var_map
, head
, i
, vm
); ++i
)
837 tree old_arg
= redirect_edge_var_map_result (vm
);
838 tree new_arg
= redirect_edge_var_map_def (vm
);
843 locus
= redirect_edge_var_map_location (vm
);
849 add_phi_arg (phi
, def
, s
, locus
);
852 redirect_edge_var_map_clear (e
);
855 /* Update the dominators. */
856 dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
857 domdest
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
860 /* Shortcut to avoid calling (relatively expensive)
861 nearest_common_dominator unless necessary. */
865 dom
= nearest_common_dominator (CDI_DOMINATORS
, domdest
, dombb
);
867 set_immediate_dominator (CDI_DOMINATORS
, dest
, dom
);
869 /* Remove BB since all of BB's incoming edges have been redirected
871 delete_basic_block (bb
);
874 /* This pass merges PHI nodes if one feeds into another. For example,
875 suppose we have the following:
882 # tem_6 = PHI <tem_17(8), tem_23(7)>;
885 # tem_3 = PHI <tem_6(9), tem_2(5)>;
888 Then we merge the first PHI node into the second one like so:
895 # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
900 merge_phi_nodes (void)
902 basic_block
*worklist
= XNEWVEC (basic_block
, n_basic_blocks
);
903 basic_block
*current
= worklist
;
906 calculate_dominance_info (CDI_DOMINATORS
);
908 /* Find all PHI nodes that we may be able to merge. */
913 /* Look for a forwarder block with PHI nodes. */
914 if (!tree_forwarder_block_p (bb
, true))
917 dest
= single_succ (bb
);
919 /* We have to feed into another basic block with PHI
921 if (gimple_seq_empty_p (phi_nodes (dest
))
922 /* We don't want to deal with a basic block with
924 || has_abnormal_incoming_edge_p (bb
))
927 if (!dominated_by_p (CDI_DOMINATORS
, dest
, bb
))
929 /* If BB does not dominate DEST, then the PHI nodes at
930 DEST must be the only users of the results of the PHI
936 gimple_stmt_iterator gsi
;
937 unsigned int dest_idx
= single_succ_edge (bb
)->dest_idx
;
939 /* BB dominates DEST. There may be many users of the PHI
940 nodes in BB. However, there is still a trivial case we
941 can handle. If the result of every PHI in BB is used
942 only by a PHI in DEST, then we can trivially merge the
943 PHI nodes from BB into DEST. */
944 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
947 gimple phi
= gsi_stmt (gsi
);
948 tree result
= gimple_phi_result (phi
);
949 use_operand_p imm_use
;
952 /* If the PHI's result is never used, then we can just
954 if (has_zero_uses (result
))
957 /* Get the single use of the result of this PHI node. */
958 if (!single_imm_use (result
, &imm_use
, &use_stmt
)
959 || gimple_code (use_stmt
) != GIMPLE_PHI
960 || gimple_bb (use_stmt
) != dest
961 || gimple_phi_arg_def (use_stmt
, dest_idx
) != result
)
965 /* If the loop above iterated through all the PHI nodes
966 in BB, then we can merge the PHIs from BB into DEST. */
972 /* Now let's drain WORKLIST. */
973 while (current
!= worklist
)
976 remove_forwarder_block_with_phi (bb
);
984 gate_merge_phi (void)
989 struct gimple_opt_pass pass_merge_phi
=
993 "mergephi", /* name */
994 gate_merge_phi
, /* gate */
995 merge_phi_nodes
, /* execute */
998 0, /* static_pass_number */
999 TV_TREE_MERGE_PHI
, /* tv_id */
1000 PROP_cfg
| PROP_ssa
, /* properties_required */
1001 0, /* properties_provided */
1002 0, /* properties_destroyed */
1003 0, /* todo_flags_start */
1004 TODO_dump_func
| TODO_ggc_collect
/* todo_flags_finish */