1 /* CFG cleanup for trees.
2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
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"
27 #include "basic-block.h"
28 #include "diagnostic-core.h"
32 #include "langhooks.h"
33 #include "tree-flow.h"
34 #include "tree-pass.h"
38 #include "tree-ssa-propagate.h"
39 #include "tree-scalar-evolution.h"
41 /* The set of blocks in that at least one of the following changes happened:
42 -- the statement at the end of the block was changed
43 -- the block was newly created
44 -- the set of the predecessors of the block changed
45 -- the set of the successors of the block changed
46 ??? Maybe we could track these changes separately, since they determine
47 what cleanups it makes sense to try on the block. */
48 bitmap cfgcleanup_altered_bbs
;
50 /* Remove any fallthru edge from EV. Return true if an edge was removed. */
53 remove_fallthru_edge (VEC(edge
,gc
) *ev
)
58 FOR_EACH_EDGE (e
, ei
, ev
)
59 if ((e
->flags
& EDGE_FALLTHRU
) != 0)
61 remove_edge_and_dominated_blocks (e
);
68 /* Disconnect an unreachable block in the control expression starting
72 cleanup_control_expr_graph (basic_block bb
, gimple_stmt_iterator gsi
)
76 gimple stmt
= gsi_stmt (gsi
);
79 if (!single_succ_p (bb
))
86 fold_defer_overflow_warnings ();
87 loc
= gimple_location (stmt
);
88 switch (gimple_code (stmt
))
91 val
= fold_binary_loc (loc
, gimple_cond_code (stmt
),
93 gimple_cond_lhs (stmt
),
94 gimple_cond_rhs (stmt
));
98 val
= gimple_switch_index (stmt
);
104 taken_edge
= find_taken_edge (bb
, val
);
107 fold_undefer_and_ignore_overflow_warnings ();
111 /* Remove all the edges except the one that is always executed. */
113 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
119 fold_undefer_overflow_warnings
120 (true, stmt
, WARN_STRICT_OVERFLOW_CONDITIONAL
);
124 taken_edge
->probability
+= e
->probability
;
125 taken_edge
->count
+= e
->count
;
126 remove_edge_and_dominated_blocks (e
);
133 fold_undefer_and_ignore_overflow_warnings ();
134 if (taken_edge
->probability
> REG_BR_PROB_BASE
)
135 taken_edge
->probability
= REG_BR_PROB_BASE
;
138 taken_edge
= single_succ_edge (bb
);
140 bitmap_set_bit (cfgcleanup_altered_bbs
, bb
->index
);
141 gsi_remove (&gsi
, true);
142 taken_edge
->flags
= EDGE_FALLTHRU
;
147 /* Try to remove superfluous control structures in basic block BB. Returns
148 true if anything changes. */
151 cleanup_control_flow_bb (basic_block bb
)
153 gimple_stmt_iterator gsi
;
157 /* If the last statement of the block could throw and now cannot,
158 we need to prune cfg. */
159 retval
|= gimple_purge_dead_eh_edges (bb
);
161 gsi
= gsi_last_bb (bb
);
165 stmt
= gsi_stmt (gsi
);
167 if (gimple_code (stmt
) == GIMPLE_COND
168 || gimple_code (stmt
) == GIMPLE_SWITCH
)
169 retval
|= cleanup_control_expr_graph (bb
, gsi
);
170 else if (gimple_code (stmt
) == GIMPLE_GOTO
171 && TREE_CODE (gimple_goto_dest (stmt
)) == ADDR_EXPR
172 && (TREE_CODE (TREE_OPERAND (gimple_goto_dest (stmt
), 0))
175 /* If we had a computed goto which has a compile-time determinable
176 destination, then we can eliminate the goto. */
180 basic_block target_block
;
182 /* First look at all the outgoing edges. Delete any outgoing
183 edges which do not go to the right block. For the one
184 edge which goes to the right block, fix up its flags. */
185 label
= TREE_OPERAND (gimple_goto_dest (stmt
), 0);
186 target_block
= label_to_block (label
);
187 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
189 if (e
->dest
!= target_block
)
190 remove_edge_and_dominated_blocks (e
);
193 /* Turn off the EDGE_ABNORMAL flag. */
194 e
->flags
&= ~EDGE_ABNORMAL
;
196 /* And set EDGE_FALLTHRU. */
197 e
->flags
|= EDGE_FALLTHRU
;
202 bitmap_set_bit (cfgcleanup_altered_bbs
, bb
->index
);
203 bitmap_set_bit (cfgcleanup_altered_bbs
, target_block
->index
);
205 /* Remove the GOTO_EXPR as it is not needed. The CFG has all the
206 relevant information we need. */
207 gsi_remove (&gsi
, true);
211 /* Check for indirect calls that have been turned into
213 else if (is_gimple_call (stmt
)
214 && gimple_call_noreturn_p (stmt
)
215 && remove_fallthru_edge (bb
->succs
))
221 /* Return true if basic block BB does nothing except pass control
222 flow to another block and that we can safely insert a label at
223 the start of the successor block.
225 As a precondition, we require that BB be not equal to
229 tree_forwarder_block_p (basic_block bb
, bool phi_wanted
)
231 gimple_stmt_iterator gsi
;
234 /* BB must have a single outgoing edge. */
235 if (single_succ_p (bb
) != 1
236 /* If PHI_WANTED is false, BB must not have any PHI nodes.
237 Otherwise, BB must have PHI nodes. */
238 || gimple_seq_empty_p (phi_nodes (bb
)) == phi_wanted
239 /* BB may not be a predecessor of EXIT_BLOCK_PTR. */
240 || single_succ (bb
) == EXIT_BLOCK_PTR
241 /* Nor should this be an infinite loop. */
242 || single_succ (bb
) == bb
243 /* BB may not have an abnormal outgoing edge. */
244 || (single_succ_edge (bb
)->flags
& EDGE_ABNORMAL
))
247 gcc_checking_assert (bb
!= ENTRY_BLOCK_PTR
);
249 locus
= single_succ_edge (bb
)->goto_locus
;
251 /* There should not be an edge coming from entry, or an EH edge. */
256 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
257 if (e
->src
== ENTRY_BLOCK_PTR
|| (e
->flags
& EDGE_EH
))
259 /* If goto_locus of any of the edges differs, prevent removing
260 the forwarder block for -O0. */
261 else if (optimize
== 0 && e
->goto_locus
!= locus
)
265 /* Now walk through the statements backward. We can ignore labels,
266 anything else means this is not a forwarder block. */
267 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
269 gimple stmt
= gsi_stmt (gsi
);
271 switch (gimple_code (stmt
))
274 if (DECL_NONLOCAL (gimple_label_label (stmt
)))
276 if (optimize
== 0 && gimple_location (stmt
) != locus
)
280 /* ??? For now, hope there's a corresponding debug
281 assignment at the destination. */
293 /* Protect loop latches, headers and preheaders. */
294 if (bb
->loop_father
->header
== bb
)
296 dest
= EDGE_SUCC (bb
, 0)->dest
;
298 if (dest
->loop_father
->header
== dest
)
304 /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
305 those alternatives are equal in each of the PHI nodes, then return
306 true, else return false. */
309 phi_alternatives_equal (basic_block dest
, edge e1
, edge e2
)
311 int n1
= e1
->dest_idx
;
312 int n2
= e2
->dest_idx
;
313 gimple_stmt_iterator gsi
;
315 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
317 gimple phi
= gsi_stmt (gsi
);
318 tree val1
= gimple_phi_arg_def (phi
, n1
);
319 tree val2
= gimple_phi_arg_def (phi
, n2
);
321 gcc_assert (val1
!= NULL_TREE
);
322 gcc_assert (val2
!= NULL_TREE
);
324 if (!operand_equal_for_phi_arg_p (val1
, val2
))
331 /* Removes forwarder block BB. Returns false if this failed. */
334 remove_forwarder_block (basic_block bb
)
336 edge succ
= single_succ_edge (bb
), e
, s
;
337 basic_block dest
= succ
->dest
;
340 gimple_stmt_iterator gsi
, gsi_to
;
341 bool can_move_debug_stmts
;
343 /* We check for infinite loops already in tree_forwarder_block_p.
344 However it may happen that the infinite loop is created
345 afterwards due to removal of forwarders. */
349 /* If the destination block consists of a nonlocal label or is a
350 EH landing pad, do not merge it. */
351 label
= first_stmt (dest
);
353 && gimple_code (label
) == GIMPLE_LABEL
354 && (DECL_NONLOCAL (gimple_label_label (label
))
355 || EH_LANDING_PAD_NR (gimple_label_label (label
)) != 0))
358 /* If there is an abnormal edge to basic block BB, but not into
359 dest, problems might occur during removal of the phi node at out
360 of ssa due to overlapping live ranges of registers.
362 If there is an abnormal edge in DEST, the problems would occur
363 anyway since cleanup_dead_labels would then merge the labels for
364 two different eh regions, and rest of exception handling code
367 So if there is an abnormal edge to BB, proceed only if there is
368 no abnormal edge to DEST and there are no phi nodes in DEST. */
369 if (bb_has_abnormal_pred (bb
)
370 && (bb_has_abnormal_pred (dest
)
371 || !gimple_seq_empty_p (phi_nodes (dest
))))
374 /* If there are phi nodes in DEST, and some of the blocks that are
375 predecessors of BB are also predecessors of DEST, check that the
376 phi node arguments match. */
377 if (!gimple_seq_empty_p (phi_nodes (dest
)))
379 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
381 s
= find_edge (e
->src
, dest
);
385 if (!phi_alternatives_equal (dest
, succ
, s
))
390 can_move_debug_stmts
= MAY_HAVE_DEBUG_STMTS
&& single_pred_p (dest
);
392 /* Redirect the edges. */
393 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
395 bitmap_set_bit (cfgcleanup_altered_bbs
, e
->src
->index
);
397 if (e
->flags
& EDGE_ABNORMAL
)
399 /* If there is an abnormal edge, redirect it anyway, and
400 move the labels to the new block to make it legal. */
401 s
= redirect_edge_succ_nodup (e
, dest
);
404 s
= redirect_edge_and_branch (e
, dest
);
408 /* Create arguments for the phi nodes, since the edge was not
410 for (gsi
= gsi_start_phis (dest
);
414 gimple phi
= gsi_stmt (gsi
);
415 source_location l
= gimple_phi_arg_location_from_edge (phi
, succ
);
416 add_phi_arg (phi
, gimple_phi_arg_def (phi
, succ
->dest_idx
), s
, l
);
421 /* Move nonlocal labels and computed goto targets as well as user
422 defined labels and labels with an EH landing pad number to the
423 new block, so that the redirection of the abnormal edges works,
424 jump targets end up in a sane place and debug information for
425 labels is retained. */
426 gsi_to
= gsi_start_bb (dest
);
427 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
430 label
= gsi_stmt (gsi
);
431 if (is_gimple_debug (label
))
433 decl
= gimple_label_label (label
);
434 if (EH_LANDING_PAD_NR (decl
) != 0
435 || DECL_NONLOCAL (decl
)
436 || FORCED_LABEL (decl
)
437 || !DECL_ARTIFICIAL (decl
))
439 gsi_remove (&gsi
, false);
440 gsi_insert_before (&gsi_to
, label
, GSI_SAME_STMT
);
446 /* Move debug statements if the destination has a single predecessor. */
447 if (can_move_debug_stmts
)
449 gsi_to
= gsi_after_labels (dest
);
450 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); )
452 gimple debug
= gsi_stmt (gsi
);
453 if (!is_gimple_debug (debug
))
455 gsi_remove (&gsi
, false);
456 gsi_insert_before (&gsi_to
, debug
, GSI_SAME_STMT
);
460 bitmap_set_bit (cfgcleanup_altered_bbs
, dest
->index
);
462 /* Update the dominators. */
463 if (dom_info_available_p (CDI_DOMINATORS
))
465 basic_block dom
, dombb
, domdest
;
467 dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
468 domdest
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
471 /* Shortcut to avoid calling (relatively expensive)
472 nearest_common_dominator unless necessary. */
476 dom
= nearest_common_dominator (CDI_DOMINATORS
, domdest
, dombb
);
478 set_immediate_dominator (CDI_DOMINATORS
, dest
, dom
);
481 /* And kill the forwarder block. */
482 delete_basic_block (bb
);
487 /* STMT is a call that has been discovered noreturn. Fixup the CFG
488 and remove LHS. Return true if something changed. */
491 fixup_noreturn_call (gimple stmt
)
493 basic_block bb
= gimple_bb (stmt
);
494 bool changed
= false;
496 if (gimple_call_builtin_p (stmt
, BUILT_IN_RETURN
))
499 /* First split basic block if stmt is not last. */
500 if (stmt
!= gsi_stmt (gsi_last_bb (bb
)))
501 split_block (bb
, stmt
);
503 changed
|= remove_fallthru_edge (bb
->succs
);
505 /* If there is LHS, remove it. */
506 if (gimple_call_lhs (stmt
))
508 tree op
= gimple_call_lhs (stmt
);
509 gimple_call_set_lhs (stmt
, NULL_TREE
);
511 /* We need to remove SSA name to avoid checking errors.
512 All uses are dominated by the noreturn and thus will
513 be removed afterwards.
514 We proactively remove affected non-PHI statements to avoid
515 fixup_cfg from trying to update them and crashing. */
516 if (TREE_CODE (op
) == SSA_NAME
)
519 imm_use_iterator iter
;
522 unsigned int bb_index
;
524 bitmap blocks
= BITMAP_ALLOC (NULL
);
526 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, op
)
528 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
529 bitmap_set_bit (blocks
, gimple_bb (use_stmt
)->index
);
531 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
532 SET_USE (use_p
, error_mark_node
);
534 EXECUTE_IF_SET_IN_BITMAP (blocks
, 0, bb_index
, bi
)
535 delete_basic_block (BASIC_BLOCK (bb_index
));
536 BITMAP_FREE (blocks
);
537 release_ssa_name (op
);
542 /* Similarly remove VDEF if there is any. */
543 else if (gimple_vdef (stmt
))
549 /* Split basic blocks on calls in the middle of a basic block that are now
550 known not to return, and remove the unreachable code. */
553 split_bbs_on_noreturn_calls (void)
555 bool changed
= false;
559 /* Detect cases where a mid-block call is now known not to return. */
561 while (VEC_length (gimple
, MODIFIED_NORETURN_CALLS (cfun
)))
563 stmt
= VEC_pop (gimple
, MODIFIED_NORETURN_CALLS (cfun
));
564 bb
= gimple_bb (stmt
);
565 /* BB might be deleted at this point, so verify first
566 BB is present in the cfg. */
568 || bb
->index
< NUM_FIXED_BLOCKS
569 || bb
->index
>= last_basic_block
570 || BASIC_BLOCK (bb
->index
) != bb
571 || !gimple_call_noreturn_p (stmt
))
574 changed
|= fixup_noreturn_call (stmt
);
580 /* Tries to cleanup cfg in basic block BB. Returns true if anything
584 cleanup_tree_cfg_bb (basic_block bb
)
586 bool retval
= cleanup_control_flow_bb (bb
);
588 if (tree_forwarder_block_p (bb
, false)
589 && remove_forwarder_block (bb
))
592 /* Merging the blocks may create new opportunities for folding
593 conditional branches (due to the elimination of single-valued PHI
595 if (single_succ_p (bb
)
596 && can_merge_blocks_p (bb
, single_succ (bb
)))
598 merge_blocks (bb
, single_succ (bb
));
605 /* Iterate the cfg cleanups, while anything changes. */
608 cleanup_tree_cfg_1 (void)
614 retval
|= split_bbs_on_noreturn_calls ();
616 /* Prepare the worklists of altered blocks. */
617 cfgcleanup_altered_bbs
= BITMAP_ALLOC (NULL
);
619 /* During forwarder block cleanup, we may redirect edges out of
620 SWITCH_EXPRs, which can get expensive. So we want to enable
621 recording of edge to CASE_LABEL_EXPR. */
622 start_recording_case_labels ();
624 /* Start by iterating over all basic blocks. We cannot use FOR_EACH_BB,
625 since the basic blocks may get removed. */
626 n
= last_basic_block
;
627 for (i
= NUM_FIXED_BLOCKS
; i
< n
; i
++)
629 bb
= BASIC_BLOCK (i
);
631 retval
|= cleanup_tree_cfg_bb (bb
);
634 /* Now process the altered blocks, as long as any are available. */
635 while (!bitmap_empty_p (cfgcleanup_altered_bbs
))
637 i
= bitmap_first_set_bit (cfgcleanup_altered_bbs
);
638 bitmap_clear_bit (cfgcleanup_altered_bbs
, i
);
639 if (i
< NUM_FIXED_BLOCKS
)
642 bb
= BASIC_BLOCK (i
);
646 retval
|= cleanup_tree_cfg_bb (bb
);
648 /* Rerun split_bbs_on_noreturn_calls, in case we have altered any noreturn
650 retval
|= split_bbs_on_noreturn_calls ();
653 end_recording_case_labels ();
654 BITMAP_FREE (cfgcleanup_altered_bbs
);
659 /* Remove unreachable blocks and other miscellaneous clean up work.
660 Return true if the flowgraph was modified, false otherwise. */
663 cleanup_tree_cfg_noloop (void)
667 timevar_push (TV_TREE_CLEANUP_CFG
);
669 /* Iterate until there are no more cleanups left to do. If any
670 iteration changed the flowgraph, set CHANGED to true.
672 If dominance information is available, there cannot be any unreachable
674 if (!dom_info_available_p (CDI_DOMINATORS
))
676 changed
= delete_unreachable_blocks ();
677 calculate_dominance_info (CDI_DOMINATORS
);
681 #ifdef ENABLE_CHECKING
682 verify_dominators (CDI_DOMINATORS
);
687 changed
|= cleanup_tree_cfg_1 ();
689 gcc_assert (dom_info_available_p (CDI_DOMINATORS
));
692 #ifdef ENABLE_CHECKING
696 timevar_pop (TV_TREE_CLEANUP_CFG
);
698 if (changed
&& current_loops
)
699 loops_state_set (LOOPS_NEED_FIXUP
);
704 /* Repairs loop structures. */
707 repair_loop_structures (void)
711 calculate_dominance_info (CDI_DOMINATORS
);
713 timevar_push (TV_REPAIR_LOOPS
);
714 changed_bbs
= BITMAP_ALLOC (NULL
);
715 fix_loop_structure (changed_bbs
);
717 /* This usually does nothing. But sometimes parts of cfg that originally
718 were inside a loop get out of it due to edge removal (since they
719 become unreachable by back edges from latch). */
720 if (loops_state_satisfies_p (LOOP_CLOSED_SSA
))
721 rewrite_into_loop_closed_ssa (changed_bbs
, TODO_update_ssa
);
723 BITMAP_FREE (changed_bbs
);
725 #ifdef ENABLE_CHECKING
726 verify_loop_structure ();
730 timevar_pop (TV_REPAIR_LOOPS
);
733 /* Cleanup cfg and repair loop structures. */
736 cleanup_tree_cfg (void)
738 bool changed
= cleanup_tree_cfg_noloop ();
740 if (current_loops
!= NULL
741 && loops_state_satisfies_p (LOOPS_NEED_FIXUP
))
742 repair_loop_structures ();
747 /* Merge the PHI nodes at BB into those at BB's sole successor. */
750 remove_forwarder_block_with_phi (basic_block bb
)
752 edge succ
= single_succ_edge (bb
);
753 basic_block dest
= succ
->dest
;
755 basic_block dombb
, domdest
, dom
;
757 /* We check for infinite loops already in tree_forwarder_block_p.
758 However it may happen that the infinite loop is created
759 afterwards due to removal of forwarders. */
763 /* If the destination block consists of a nonlocal label, do not
765 label
= first_stmt (dest
);
767 && gimple_code (label
) == GIMPLE_LABEL
768 && DECL_NONLOCAL (gimple_label_label (label
)))
771 /* Redirect each incoming edge to BB to DEST. */
772 while (EDGE_COUNT (bb
->preds
) > 0)
774 edge e
= EDGE_PRED (bb
, 0), s
;
775 gimple_stmt_iterator gsi
;
777 s
= find_edge (e
->src
, dest
);
780 /* We already have an edge S from E->src to DEST. If S and
781 E->dest's sole successor edge have the same PHI arguments
782 at DEST, redirect S to DEST. */
783 if (phi_alternatives_equal (dest
, s
, succ
))
785 e
= redirect_edge_and_branch (e
, dest
);
786 redirect_edge_var_map_clear (e
);
790 /* PHI arguments are different. Create a forwarder block by
791 splitting E so that we can merge PHI arguments on E to
793 e
= single_succ_edge (split_edge (e
));
796 s
= redirect_edge_and_branch (e
, dest
);
798 /* redirect_edge_and_branch must not create a new edge. */
801 /* Add to the PHI nodes at DEST each PHI argument removed at the
803 for (gsi
= gsi_start_phis (dest
);
807 gimple phi
= gsi_stmt (gsi
);
808 tree def
= gimple_phi_arg_def (phi
, succ
->dest_idx
);
809 source_location locus
= gimple_phi_arg_location_from_edge (phi
, succ
);
811 if (TREE_CODE (def
) == SSA_NAME
)
813 edge_var_map_vector head
;
817 /* If DEF is one of the results of PHI nodes removed during
818 redirection, replace it with the PHI argument that used
820 head
= redirect_edge_var_map_vector (e
);
821 FOR_EACH_VEC_ELT (edge_var_map
, head
, i
, vm
)
823 tree old_arg
= redirect_edge_var_map_result (vm
);
824 tree new_arg
= redirect_edge_var_map_def (vm
);
829 locus
= redirect_edge_var_map_location (vm
);
835 add_phi_arg (phi
, def
, s
, locus
);
838 redirect_edge_var_map_clear (e
);
841 /* Update the dominators. */
842 dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
843 domdest
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
846 /* Shortcut to avoid calling (relatively expensive)
847 nearest_common_dominator unless necessary. */
851 dom
= nearest_common_dominator (CDI_DOMINATORS
, domdest
, dombb
);
853 set_immediate_dominator (CDI_DOMINATORS
, dest
, dom
);
855 /* Remove BB since all of BB's incoming edges have been redirected
857 delete_basic_block (bb
);
860 /* This pass merges PHI nodes if one feeds into another. For example,
861 suppose we have the following:
868 # tem_6 = PHI <tem_17(8), tem_23(7)>;
871 # tem_3 = PHI <tem_6(9), tem_2(5)>;
874 Then we merge the first PHI node into the second one like so:
881 # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
886 merge_phi_nodes (void)
888 basic_block
*worklist
= XNEWVEC (basic_block
, n_basic_blocks
);
889 basic_block
*current
= worklist
;
892 calculate_dominance_info (CDI_DOMINATORS
);
894 /* Find all PHI nodes that we may be able to merge. */
899 /* Look for a forwarder block with PHI nodes. */
900 if (!tree_forwarder_block_p (bb
, true))
903 dest
= single_succ (bb
);
905 /* We have to feed into another basic block with PHI
907 if (gimple_seq_empty_p (phi_nodes (dest
))
908 /* We don't want to deal with a basic block with
910 || bb_has_abnormal_pred (bb
))
913 if (!dominated_by_p (CDI_DOMINATORS
, dest
, bb
))
915 /* If BB does not dominate DEST, then the PHI nodes at
916 DEST must be the only users of the results of the PHI
922 gimple_stmt_iterator gsi
;
923 unsigned int dest_idx
= single_succ_edge (bb
)->dest_idx
;
925 /* BB dominates DEST. There may be many users of the PHI
926 nodes in BB. However, there is still a trivial case we
927 can handle. If the result of every PHI in BB is used
928 only by a PHI in DEST, then we can trivially merge the
929 PHI nodes from BB into DEST. */
930 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
933 gimple phi
= gsi_stmt (gsi
);
934 tree result
= gimple_phi_result (phi
);
935 use_operand_p imm_use
;
938 /* If the PHI's result is never used, then we can just
940 if (has_zero_uses (result
))
943 /* Get the single use of the result of this PHI node. */
944 if (!single_imm_use (result
, &imm_use
, &use_stmt
)
945 || gimple_code (use_stmt
) != GIMPLE_PHI
946 || gimple_bb (use_stmt
) != dest
947 || gimple_phi_arg_def (use_stmt
, dest_idx
) != result
)
951 /* If the loop above iterated through all the PHI nodes
952 in BB, then we can merge the PHIs from BB into DEST. */
958 /* Now let's drain WORKLIST. */
959 while (current
!= worklist
)
962 remove_forwarder_block_with_phi (bb
);
970 gate_merge_phi (void)
975 struct gimple_opt_pass pass_merge_phi
=
979 "mergephi", /* name */
980 OPTGROUP_NONE
, /* optinfo_flags */
981 gate_merge_phi
, /* gate */
982 merge_phi_nodes
, /* execute */
985 0, /* static_pass_number */
986 TV_TREE_MERGE_PHI
, /* tv_id */
987 PROP_cfg
| PROP_ssa
, /* properties_required */
988 0, /* properties_provided */
989 0, /* properties_destroyed */
990 0, /* todo_flags_start */
991 TODO_ggc_collect
/* todo_flags_finish */