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"
29 #include "diagnostic-core.h"
33 #include "langhooks.h"
34 #include "tree-flow.h"
36 #include "tree-dump.h"
37 #include "tree-pass.h"
40 #include "cfglayout.h"
42 #include "tree-ssa-propagate.h"
43 #include "tree-scalar-evolution.h"
45 /* The set of blocks in that at least one of the following changes happened:
46 -- the statement at the end of the block was changed
47 -- the block was newly created
48 -- the set of the predecessors of the block changed
49 -- the set of the successors of the block changed
50 ??? Maybe we could track these changes separately, since they determine
51 what cleanups it makes sense to try on the block. */
52 bitmap cfgcleanup_altered_bbs
;
54 /* Remove any fallthru edge from EV. Return true if an edge was removed. */
57 remove_fallthru_edge (VEC(edge
,gc
) *ev
)
62 FOR_EACH_EDGE (e
, ei
, ev
)
63 if ((e
->flags
& EDGE_FALLTHRU
) != 0)
65 remove_edge_and_dominated_blocks (e
);
72 /* Disconnect an unreachable block in the control expression starting
76 cleanup_control_expr_graph (basic_block bb
, gimple_stmt_iterator gsi
)
80 gimple stmt
= gsi_stmt (gsi
);
83 if (!single_succ_p (bb
))
90 fold_defer_overflow_warnings ();
91 loc
= gimple_location (stmt
);
92 switch (gimple_code (stmt
))
96 tree lhs
= gimple_cond_lhs (stmt
);
97 tree rhs
= gimple_cond_rhs (stmt
);
98 /* For conditions try harder and lookup single-argument
99 PHI nodes. Only do so from the same basic-block though
100 as other basic-blocks may be dead already. */
101 if (TREE_CODE (lhs
) == SSA_NAME
102 && !name_registered_for_update_p (lhs
))
104 gimple def_stmt
= SSA_NAME_DEF_STMT (lhs
);
105 if (gimple_code (def_stmt
) == GIMPLE_PHI
106 && gimple_phi_num_args (def_stmt
) == 1
107 && gimple_bb (def_stmt
) == gimple_bb (stmt
)
108 && (TREE_CODE (PHI_ARG_DEF (def_stmt
, 0)) != SSA_NAME
109 || !name_registered_for_update_p (PHI_ARG_DEF (def_stmt
,
111 lhs
= PHI_ARG_DEF (def_stmt
, 0);
113 if (TREE_CODE (rhs
) == SSA_NAME
114 && !name_registered_for_update_p (rhs
))
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 && (TREE_CODE (PHI_ARG_DEF (def_stmt
, 0)) != SSA_NAME
121 || !name_registered_for_update_p (PHI_ARG_DEF (def_stmt
,
123 rhs
= PHI_ARG_DEF (def_stmt
, 0);
125 val
= fold_binary_loc (loc
, gimple_cond_code (stmt
),
126 boolean_type_node
, lhs
, rhs
);
131 val
= gimple_switch_index (stmt
);
137 taken_edge
= find_taken_edge (bb
, val
);
140 fold_undefer_and_ignore_overflow_warnings ();
144 /* Remove all the edges except the one that is always executed. */
146 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
152 fold_undefer_overflow_warnings
153 (true, stmt
, WARN_STRICT_OVERFLOW_CONDITIONAL
);
157 taken_edge
->probability
+= e
->probability
;
158 taken_edge
->count
+= e
->count
;
159 remove_edge_and_dominated_blocks (e
);
166 fold_undefer_and_ignore_overflow_warnings ();
167 if (taken_edge
->probability
> REG_BR_PROB_BASE
)
168 taken_edge
->probability
= REG_BR_PROB_BASE
;
171 taken_edge
= single_succ_edge (bb
);
173 bitmap_set_bit (cfgcleanup_altered_bbs
, bb
->index
);
174 gsi_remove (&gsi
, true);
175 taken_edge
->flags
= EDGE_FALLTHRU
;
180 /* Try to remove superfluous control structures in basic block BB. Returns
181 true if anything changes. */
184 cleanup_control_flow_bb (basic_block bb
)
186 gimple_stmt_iterator gsi
;
190 /* If the last statement of the block could throw and now cannot,
191 we need to prune cfg. */
192 retval
|= gimple_purge_dead_eh_edges (bb
);
194 gsi
= gsi_last_bb (bb
);
198 stmt
= gsi_stmt (gsi
);
200 if (gimple_code (stmt
) == GIMPLE_COND
201 || gimple_code (stmt
) == GIMPLE_SWITCH
)
202 retval
|= cleanup_control_expr_graph (bb
, gsi
);
203 else if (gimple_code (stmt
) == GIMPLE_GOTO
204 && TREE_CODE (gimple_goto_dest (stmt
)) == ADDR_EXPR
205 && (TREE_CODE (TREE_OPERAND (gimple_goto_dest (stmt
), 0))
208 /* If we had a computed goto which has a compile-time determinable
209 destination, then we can eliminate the goto. */
213 basic_block target_block
;
215 /* First look at all the outgoing edges. Delete any outgoing
216 edges which do not go to the right block. For the one
217 edge which goes to the right block, fix up its flags. */
218 label
= TREE_OPERAND (gimple_goto_dest (stmt
), 0);
219 target_block
= label_to_block (label
);
220 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
222 if (e
->dest
!= target_block
)
223 remove_edge_and_dominated_blocks (e
);
226 /* Turn off the EDGE_ABNORMAL flag. */
227 e
->flags
&= ~EDGE_ABNORMAL
;
229 /* And set EDGE_FALLTHRU. */
230 e
->flags
|= EDGE_FALLTHRU
;
235 bitmap_set_bit (cfgcleanup_altered_bbs
, bb
->index
);
236 bitmap_set_bit (cfgcleanup_altered_bbs
, target_block
->index
);
238 /* Remove the GOTO_EXPR as it is not needed. The CFG has all the
239 relevant information we need. */
240 gsi_remove (&gsi
, true);
244 /* Check for indirect calls that have been turned into
246 else if (is_gimple_call (stmt
)
247 && gimple_call_noreturn_p (stmt
)
248 && remove_fallthru_edge (bb
->succs
))
254 /* Return true if basic block BB does nothing except pass control
255 flow to another block and that we can safely insert a label at
256 the start of the successor block.
258 As a precondition, we require that BB be not equal to
262 tree_forwarder_block_p (basic_block bb
, bool phi_wanted
)
264 gimple_stmt_iterator gsi
;
267 /* BB must have a single outgoing edge. */
268 if (single_succ_p (bb
) != 1
269 /* If PHI_WANTED is false, BB must not have any PHI nodes.
270 Otherwise, BB must have PHI nodes. */
271 || gimple_seq_empty_p (phi_nodes (bb
)) == phi_wanted
272 /* BB may not be a predecessor of EXIT_BLOCK_PTR. */
273 || single_succ (bb
) == EXIT_BLOCK_PTR
274 /* Nor should this be an infinite loop. */
275 || single_succ (bb
) == bb
276 /* BB may not have an abnormal outgoing edge. */
277 || (single_succ_edge (bb
)->flags
& EDGE_ABNORMAL
))
280 gcc_checking_assert (bb
!= ENTRY_BLOCK_PTR
);
282 locus
= single_succ_edge (bb
)->goto_locus
;
284 /* There should not be an edge coming from entry, or an EH edge. */
289 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
290 if (e
->src
== ENTRY_BLOCK_PTR
|| (e
->flags
& EDGE_EH
))
292 /* If goto_locus of any of the edges differs, prevent removing
293 the forwarder block for -O0. */
294 else if (optimize
== 0 && e
->goto_locus
!= locus
)
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
)))
309 if (optimize
== 0 && gimple_location (stmt
) != locus
)
313 /* ??? For now, hope there's a corresponding debug
314 assignment at the destination. */
326 /* Protect loop latches, headers and preheaders. */
327 if (bb
->loop_father
->header
== bb
)
329 dest
= EDGE_SUCC (bb
, 0)->dest
;
331 if (dest
->loop_father
->header
== dest
)
337 /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
338 those alternatives are equal in each of the PHI nodes, then return
339 true, else return false. */
342 phi_alternatives_equal (basic_block dest
, edge e1
, edge e2
)
344 int n1
= e1
->dest_idx
;
345 int n2
= e2
->dest_idx
;
346 gimple_stmt_iterator gsi
;
348 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
350 gimple phi
= gsi_stmt (gsi
);
351 tree val1
= gimple_phi_arg_def (phi
, n1
);
352 tree val2
= gimple_phi_arg_def (phi
, n2
);
354 gcc_assert (val1
!= NULL_TREE
);
355 gcc_assert (val2
!= NULL_TREE
);
357 if (!operand_equal_for_phi_arg_p (val1
, val2
))
364 /* Removes forwarder block BB. Returns false if this failed. */
367 remove_forwarder_block (basic_block bb
)
369 edge succ
= single_succ_edge (bb
), e
, s
;
370 basic_block dest
= succ
->dest
;
373 gimple_stmt_iterator gsi
, gsi_to
;
374 bool can_move_debug_stmts
;
376 /* We check for infinite loops already in tree_forwarder_block_p.
377 However it may happen that the infinite loop is created
378 afterwards due to removal of forwarders. */
382 /* If the destination block consists of a nonlocal label or is a
383 EH landing pad, do not merge it. */
384 label
= first_stmt (dest
);
386 && gimple_code (label
) == GIMPLE_LABEL
387 && (DECL_NONLOCAL (gimple_label_label (label
))
388 || EH_LANDING_PAD_NR (gimple_label_label (label
)) != 0))
391 /* If there is an abnormal edge to basic block BB, but not into
392 dest, problems might occur during removal of the phi node at out
393 of ssa due to overlapping live ranges of registers.
395 If there is an abnormal edge in DEST, the problems would occur
396 anyway since cleanup_dead_labels would then merge the labels for
397 two different eh regions, and rest of exception handling code
400 So if there is an abnormal edge to BB, proceed only if there is
401 no abnormal edge to DEST and there are no phi nodes in DEST. */
402 if (bb_has_abnormal_pred (bb
)
403 && (bb_has_abnormal_pred (dest
)
404 || !gimple_seq_empty_p (phi_nodes (dest
))))
407 /* If there are phi nodes in DEST, and some of the blocks that are
408 predecessors of BB are also predecessors of DEST, check that the
409 phi node arguments match. */
410 if (!gimple_seq_empty_p (phi_nodes (dest
)))
412 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
414 s
= find_edge (e
->src
, dest
);
418 if (!phi_alternatives_equal (dest
, succ
, s
))
423 can_move_debug_stmts
= MAY_HAVE_DEBUG_STMTS
&& single_pred_p (dest
);
425 /* Redirect the edges. */
426 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
428 bitmap_set_bit (cfgcleanup_altered_bbs
, e
->src
->index
);
430 if (e
->flags
& EDGE_ABNORMAL
)
432 /* If there is an abnormal edge, redirect it anyway, and
433 move the labels to the new block to make it legal. */
434 s
= redirect_edge_succ_nodup (e
, dest
);
437 s
= redirect_edge_and_branch (e
, dest
);
441 /* Create arguments for the phi nodes, since the edge was not
443 for (gsi
= gsi_start_phis (dest
);
447 gimple phi
= gsi_stmt (gsi
);
448 source_location l
= gimple_phi_arg_location_from_edge (phi
, succ
);
449 add_phi_arg (phi
, gimple_phi_arg_def (phi
, succ
->dest_idx
), s
, l
);
454 /* Move nonlocal labels and computed goto targets as well as user
455 defined labels and labels with an EH landing pad number to the
456 new block, so that the redirection of the abnormal edges works,
457 jump targets end up in a sane place and debug information for
458 labels is retained. */
459 gsi_to
= gsi_start_bb (dest
);
460 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
463 label
= gsi_stmt (gsi
);
464 if (is_gimple_debug (label
))
466 decl
= gimple_label_label (label
);
467 if (EH_LANDING_PAD_NR (decl
) != 0
468 || DECL_NONLOCAL (decl
)
469 || FORCED_LABEL (decl
)
470 || !DECL_ARTIFICIAL (decl
))
472 gsi_remove (&gsi
, false);
473 gsi_insert_before (&gsi_to
, label
, GSI_SAME_STMT
);
479 /* Move debug statements if the destination has a single predecessor. */
480 if (can_move_debug_stmts
)
482 gsi_to
= gsi_after_labels (dest
);
483 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); )
485 gimple debug
= gsi_stmt (gsi
);
486 if (!is_gimple_debug (debug
))
488 gsi_remove (&gsi
, false);
489 gsi_insert_before (&gsi_to
, debug
, GSI_SAME_STMT
);
493 bitmap_set_bit (cfgcleanup_altered_bbs
, dest
->index
);
495 /* Update the dominators. */
496 if (dom_info_available_p (CDI_DOMINATORS
))
498 basic_block dom
, dombb
, domdest
;
500 dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
501 domdest
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
504 /* Shortcut to avoid calling (relatively expensive)
505 nearest_common_dominator unless necessary. */
509 dom
= nearest_common_dominator (CDI_DOMINATORS
, domdest
, dombb
);
511 set_immediate_dominator (CDI_DOMINATORS
, dest
, dom
);
514 /* And kill the forwarder block. */
515 delete_basic_block (bb
);
520 /* STMT is a call that has been discovered noreturn. Fixup the CFG
521 and remove LHS. Return true if something changed. */
524 fixup_noreturn_call (gimple stmt
)
526 basic_block bb
= gimple_bb (stmt
);
527 bool changed
= false;
529 if (gimple_call_builtin_p (stmt
, BUILT_IN_RETURN
))
532 /* First split basic block if stmt is not last. */
533 if (stmt
!= gsi_stmt (gsi_last_bb (bb
)))
534 split_block (bb
, stmt
);
536 changed
|= remove_fallthru_edge (bb
->succs
);
538 /* If there is LHS, remove it. */
539 if (gimple_call_lhs (stmt
))
541 tree op
= gimple_call_lhs (stmt
);
542 gimple_call_set_lhs (stmt
, NULL_TREE
);
544 /* We need to remove SSA name to avoid checking errors.
545 All uses are dominated by the noreturn and thus will
546 be removed afterwards.
547 We proactively remove affected non-PHI statements to avoid
548 fixup_cfg from trying to update them and crashing. */
549 if (TREE_CODE (op
) == SSA_NAME
)
552 imm_use_iterator iter
;
555 unsigned int bb_index
;
557 bitmap blocks
= BITMAP_ALLOC (NULL
);
559 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, op
)
561 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
562 bitmap_set_bit (blocks
, gimple_bb (use_stmt
)->index
);
564 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
565 SET_USE (use_p
, error_mark_node
);
567 EXECUTE_IF_SET_IN_BITMAP (blocks
, 0, bb_index
, bi
)
568 delete_basic_block (BASIC_BLOCK (bb_index
));
569 BITMAP_FREE (blocks
);
570 release_ssa_name (op
);
575 /* Similarly remove VDEF if there is any. */
576 else if (gimple_vdef (stmt
))
582 /* Split basic blocks on calls in the middle of a basic block that are now
583 known not to return, and remove the unreachable code. */
586 split_bbs_on_noreturn_calls (void)
588 bool changed
= false;
592 /* Detect cases where a mid-block call is now known not to return. */
594 while (VEC_length (gimple
, MODIFIED_NORETURN_CALLS (cfun
)))
596 stmt
= VEC_pop (gimple
, MODIFIED_NORETURN_CALLS (cfun
));
597 bb
= gimple_bb (stmt
);
598 /* BB might be deleted at this point, so verify first
599 BB is present in the cfg. */
601 || bb
->index
< NUM_FIXED_BLOCKS
602 || bb
->index
>= last_basic_block
603 || BASIC_BLOCK (bb
->index
) != bb
604 || !gimple_call_noreturn_p (stmt
))
607 changed
|= fixup_noreturn_call (stmt
);
613 /* Tries to cleanup cfg in basic block BB. Returns true if anything
617 cleanup_tree_cfg_bb (basic_block bb
)
619 bool retval
= cleanup_control_flow_bb (bb
);
621 if (tree_forwarder_block_p (bb
, false)
622 && remove_forwarder_block (bb
))
625 /* Merging the blocks may create new opportunities for folding
626 conditional branches (due to the elimination of single-valued PHI
628 if (single_succ_p (bb
)
629 && can_merge_blocks_p (bb
, single_succ (bb
)))
631 merge_blocks (bb
, single_succ (bb
));
638 /* Iterate the cfg cleanups, while anything changes. */
641 cleanup_tree_cfg_1 (void)
647 retval
|= split_bbs_on_noreturn_calls ();
649 /* Prepare the worklists of altered blocks. */
650 cfgcleanup_altered_bbs
= BITMAP_ALLOC (NULL
);
652 /* During forwarder block cleanup, we may redirect edges out of
653 SWITCH_EXPRs, which can get expensive. So we want to enable
654 recording of edge to CASE_LABEL_EXPR. */
655 start_recording_case_labels ();
657 /* Start by iterating over all basic blocks. We cannot use FOR_EACH_BB,
658 since the basic blocks may get removed. */
659 n
= last_basic_block
;
660 for (i
= NUM_FIXED_BLOCKS
; i
< n
; i
++)
662 bb
= BASIC_BLOCK (i
);
664 retval
|= cleanup_tree_cfg_bb (bb
);
667 /* Now process the altered blocks, as long as any are available. */
668 while (!bitmap_empty_p (cfgcleanup_altered_bbs
))
670 i
= bitmap_first_set_bit (cfgcleanup_altered_bbs
);
671 bitmap_clear_bit (cfgcleanup_altered_bbs
, i
);
672 if (i
< NUM_FIXED_BLOCKS
)
675 bb
= BASIC_BLOCK (i
);
679 retval
|= cleanup_tree_cfg_bb (bb
);
681 /* Rerun split_bbs_on_noreturn_calls, in case we have altered any noreturn
683 retval
|= split_bbs_on_noreturn_calls ();
686 end_recording_case_labels ();
687 BITMAP_FREE (cfgcleanup_altered_bbs
);
692 /* Remove unreachable blocks and other miscellaneous clean up work.
693 Return true if the flowgraph was modified, false otherwise. */
696 cleanup_tree_cfg_noloop (void)
700 timevar_push (TV_TREE_CLEANUP_CFG
);
702 /* Iterate until there are no more cleanups left to do. If any
703 iteration changed the flowgraph, set CHANGED to true.
705 If dominance information is available, there cannot be any unreachable
707 if (!dom_info_available_p (CDI_DOMINATORS
))
709 changed
= delete_unreachable_blocks ();
710 calculate_dominance_info (CDI_DOMINATORS
);
714 #ifdef ENABLE_CHECKING
715 verify_dominators (CDI_DOMINATORS
);
720 changed
|= cleanup_tree_cfg_1 ();
722 gcc_assert (dom_info_available_p (CDI_DOMINATORS
));
725 #ifdef ENABLE_CHECKING
729 timevar_pop (TV_TREE_CLEANUP_CFG
);
731 if (changed
&& current_loops
)
732 loops_state_set (LOOPS_NEED_FIXUP
);
737 /* Repairs loop structures. */
740 repair_loop_structures (void)
744 timevar_push (TV_REPAIR_LOOPS
);
745 changed_bbs
= BITMAP_ALLOC (NULL
);
746 fix_loop_structure (changed_bbs
);
748 /* This usually does nothing. But sometimes parts of cfg that originally
749 were inside a loop get out of it due to edge removal (since they
750 become unreachable by back edges from latch). */
751 if (loops_state_satisfies_p (LOOP_CLOSED_SSA
))
752 rewrite_into_loop_closed_ssa (changed_bbs
, TODO_update_ssa
);
754 BITMAP_FREE (changed_bbs
);
756 #ifdef ENABLE_CHECKING
757 verify_loop_structure ();
761 loops_state_clear (LOOPS_NEED_FIXUP
);
762 timevar_pop (TV_REPAIR_LOOPS
);
765 /* Cleanup cfg and repair loop structures. */
768 cleanup_tree_cfg (void)
770 bool changed
= cleanup_tree_cfg_noloop ();
772 if (current_loops
!= NULL
773 && loops_state_satisfies_p (LOOPS_NEED_FIXUP
))
774 repair_loop_structures ();
779 /* Merge the PHI nodes at BB into those at BB's sole successor. */
782 remove_forwarder_block_with_phi (basic_block bb
)
784 edge succ
= single_succ_edge (bb
);
785 basic_block dest
= succ
->dest
;
787 basic_block dombb
, domdest
, dom
;
789 /* We check for infinite loops already in tree_forwarder_block_p.
790 However it may happen that the infinite loop is created
791 afterwards due to removal of forwarders. */
795 /* If the destination block consists of a nonlocal label, do not
797 label
= first_stmt (dest
);
799 && gimple_code (label
) == GIMPLE_LABEL
800 && DECL_NONLOCAL (gimple_label_label (label
)))
803 /* Redirect each incoming edge to BB to DEST. */
804 while (EDGE_COUNT (bb
->preds
) > 0)
806 edge e
= EDGE_PRED (bb
, 0), s
;
807 gimple_stmt_iterator gsi
;
809 s
= find_edge (e
->src
, dest
);
812 /* We already have an edge S from E->src to DEST. If S and
813 E->dest's sole successor edge have the same PHI arguments
814 at DEST, redirect S to DEST. */
815 if (phi_alternatives_equal (dest
, s
, succ
))
817 e
= redirect_edge_and_branch (e
, dest
);
818 redirect_edge_var_map_clear (e
);
822 /* PHI arguments are different. Create a forwarder block by
823 splitting E so that we can merge PHI arguments on E to
825 e
= single_succ_edge (split_edge (e
));
828 s
= redirect_edge_and_branch (e
, dest
);
830 /* redirect_edge_and_branch must not create a new edge. */
833 /* Add to the PHI nodes at DEST each PHI argument removed at the
835 for (gsi
= gsi_start_phis (dest
);
839 gimple phi
= gsi_stmt (gsi
);
840 tree def
= gimple_phi_arg_def (phi
, succ
->dest_idx
);
841 source_location locus
= gimple_phi_arg_location_from_edge (phi
, succ
);
843 if (TREE_CODE (def
) == SSA_NAME
)
845 edge_var_map_vector head
;
849 /* If DEF is one of the results of PHI nodes removed during
850 redirection, replace it with the PHI argument that used
852 head
= redirect_edge_var_map_vector (e
);
853 FOR_EACH_VEC_ELT (edge_var_map
, head
, i
, vm
)
855 tree old_arg
= redirect_edge_var_map_result (vm
);
856 tree new_arg
= redirect_edge_var_map_def (vm
);
861 locus
= redirect_edge_var_map_location (vm
);
867 add_phi_arg (phi
, def
, s
, locus
);
870 redirect_edge_var_map_clear (e
);
873 /* Update the dominators. */
874 dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
875 domdest
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
878 /* Shortcut to avoid calling (relatively expensive)
879 nearest_common_dominator unless necessary. */
883 dom
= nearest_common_dominator (CDI_DOMINATORS
, domdest
, dombb
);
885 set_immediate_dominator (CDI_DOMINATORS
, dest
, dom
);
887 /* Remove BB since all of BB's incoming edges have been redirected
889 delete_basic_block (bb
);
892 /* This pass merges PHI nodes if one feeds into another. For example,
893 suppose we have the following:
900 # tem_6 = PHI <tem_17(8), tem_23(7)>;
903 # tem_3 = PHI <tem_6(9), tem_2(5)>;
906 Then we merge the first PHI node into the second one like so:
913 # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
918 merge_phi_nodes (void)
920 basic_block
*worklist
= XNEWVEC (basic_block
, n_basic_blocks
);
921 basic_block
*current
= worklist
;
924 calculate_dominance_info (CDI_DOMINATORS
);
926 /* Find all PHI nodes that we may be able to merge. */
931 /* Look for a forwarder block with PHI nodes. */
932 if (!tree_forwarder_block_p (bb
, true))
935 dest
= single_succ (bb
);
937 /* We have to feed into another basic block with PHI
939 if (gimple_seq_empty_p (phi_nodes (dest
))
940 /* We don't want to deal with a basic block with
942 || bb_has_abnormal_pred (bb
))
945 if (!dominated_by_p (CDI_DOMINATORS
, dest
, bb
))
947 /* If BB does not dominate DEST, then the PHI nodes at
948 DEST must be the only users of the results of the PHI
954 gimple_stmt_iterator gsi
;
955 unsigned int dest_idx
= single_succ_edge (bb
)->dest_idx
;
957 /* BB dominates DEST. There may be many users of the PHI
958 nodes in BB. However, there is still a trivial case we
959 can handle. If the result of every PHI in BB is used
960 only by a PHI in DEST, then we can trivially merge the
961 PHI nodes from BB into DEST. */
962 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
965 gimple phi
= gsi_stmt (gsi
);
966 tree result
= gimple_phi_result (phi
);
967 use_operand_p imm_use
;
970 /* If the PHI's result is never used, then we can just
972 if (has_zero_uses (result
))
975 /* Get the single use of the result of this PHI node. */
976 if (!single_imm_use (result
, &imm_use
, &use_stmt
)
977 || gimple_code (use_stmt
) != GIMPLE_PHI
978 || gimple_bb (use_stmt
) != dest
979 || gimple_phi_arg_def (use_stmt
, dest_idx
) != result
)
983 /* If the loop above iterated through all the PHI nodes
984 in BB, then we can merge the PHIs from BB into DEST. */
990 /* Now let's drain WORKLIST. */
991 while (current
!= worklist
)
994 remove_forwarder_block_with_phi (bb
);
1002 gate_merge_phi (void)
1007 struct gimple_opt_pass pass_merge_phi
=
1011 "mergephi", /* name */
1012 gate_merge_phi
, /* gate */
1013 merge_phi_nodes
, /* execute */
1016 0, /* static_pass_number */
1017 TV_TREE_MERGE_PHI
, /* tv_id */
1018 PROP_cfg
| PROP_ssa
, /* properties_required */
1019 0, /* properties_provided */
1020 0, /* properties_destroyed */
1021 0, /* todo_flags_start */
1022 TODO_ggc_collect
/* todo_flags_finish */