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"
34 #include "langhooks.h"
35 #include "tree-flow.h"
37 #include "tree-dump.h"
38 #include "tree-pass.h"
42 #include "cfglayout.h"
44 #include "tree-ssa-propagate.h"
45 #include "tree-scalar-evolution.h"
47 /* The set of blocks in that at least one of the following changes happened:
48 -- the statement at the end of the block was changed
49 -- the block was newly created
50 -- the set of the predecessors of the block changed
51 -- the set of the successors of the block changed
52 ??? Maybe we could track these changes separately, since they determine
53 what cleanups it makes sense to try on the block. */
54 bitmap cfgcleanup_altered_bbs
;
56 /* Remove any fallthru edge from EV. Return true if an edge was removed. */
59 remove_fallthru_edge (VEC(edge
,gc
) *ev
)
64 FOR_EACH_EDGE (e
, ei
, ev
)
65 if ((e
->flags
& EDGE_FALLTHRU
) != 0)
67 remove_edge_and_dominated_blocks (e
);
74 /* Disconnect an unreachable block in the control expression starting
78 cleanup_control_expr_graph (basic_block bb
, gimple_stmt_iterator gsi
)
82 gimple stmt
= gsi_stmt (gsi
);
85 if (!single_succ_p (bb
))
92 fold_defer_overflow_warnings ();
93 loc
= gimple_location (stmt
);
94 switch (gimple_code (stmt
))
98 tree lhs
= gimple_cond_lhs (stmt
);
99 tree rhs
= gimple_cond_rhs (stmt
);
100 /* For conditions try harder and lookup single-argument
101 PHI nodes. Only do so from the same basic-block though
102 as other basic-blocks may be dead already. */
103 if (TREE_CODE (lhs
) == SSA_NAME
104 && !name_registered_for_update_p (lhs
))
106 gimple def_stmt
= SSA_NAME_DEF_STMT (lhs
);
107 if (gimple_code (def_stmt
) == GIMPLE_PHI
108 && gimple_phi_num_args (def_stmt
) == 1
109 && gimple_bb (def_stmt
) == gimple_bb (stmt
)
110 && (TREE_CODE (PHI_ARG_DEF (def_stmt
, 0)) != SSA_NAME
111 || !name_registered_for_update_p (PHI_ARG_DEF (def_stmt
,
113 lhs
= PHI_ARG_DEF (def_stmt
, 0);
115 if (TREE_CODE (rhs
) == SSA_NAME
116 && !name_registered_for_update_p (rhs
))
118 gimple def_stmt
= SSA_NAME_DEF_STMT (rhs
);
119 if (gimple_code (def_stmt
) == GIMPLE_PHI
120 && gimple_phi_num_args (def_stmt
) == 1
121 && gimple_bb (def_stmt
) == gimple_bb (stmt
)
122 && (TREE_CODE (PHI_ARG_DEF (def_stmt
, 0)) != SSA_NAME
123 || !name_registered_for_update_p (PHI_ARG_DEF (def_stmt
,
125 rhs
= PHI_ARG_DEF (def_stmt
, 0);
127 val
= fold_binary_loc (loc
, gimple_cond_code (stmt
),
128 boolean_type_node
, lhs
, rhs
);
133 val
= gimple_switch_index (stmt
);
139 taken_edge
= find_taken_edge (bb
, val
);
142 fold_undefer_and_ignore_overflow_warnings ();
146 /* Remove all the edges except the one that is always executed. */
148 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
154 fold_undefer_overflow_warnings
155 (true, stmt
, WARN_STRICT_OVERFLOW_CONDITIONAL
);
159 taken_edge
->probability
+= e
->probability
;
160 taken_edge
->count
+= e
->count
;
161 remove_edge_and_dominated_blocks (e
);
168 fold_undefer_and_ignore_overflow_warnings ();
169 if (taken_edge
->probability
> REG_BR_PROB_BASE
)
170 taken_edge
->probability
= REG_BR_PROB_BASE
;
173 taken_edge
= single_succ_edge (bb
);
175 bitmap_set_bit (cfgcleanup_altered_bbs
, bb
->index
);
176 gsi_remove (&gsi
, true);
177 taken_edge
->flags
= EDGE_FALLTHRU
;
182 /* Try to remove superfluous control structures in basic block BB. Returns
183 true if anything changes. */
186 cleanup_control_flow_bb (basic_block bb
)
188 gimple_stmt_iterator gsi
;
192 /* If the last statement of the block could throw and now cannot,
193 we need to prune cfg. */
194 retval
|= gimple_purge_dead_eh_edges (bb
);
196 gsi
= gsi_last_bb (bb
);
200 stmt
= gsi_stmt (gsi
);
202 if (gimple_code (stmt
) == GIMPLE_COND
203 || gimple_code (stmt
) == GIMPLE_SWITCH
)
204 retval
|= cleanup_control_expr_graph (bb
, gsi
);
205 else if (gimple_code (stmt
) == GIMPLE_GOTO
206 && TREE_CODE (gimple_goto_dest (stmt
)) == ADDR_EXPR
207 && (TREE_CODE (TREE_OPERAND (gimple_goto_dest (stmt
), 0))
210 /* If we had a computed goto which has a compile-time determinable
211 destination, then we can eliminate the goto. */
215 basic_block target_block
;
217 /* First look at all the outgoing edges. Delete any outgoing
218 edges which do not go to the right block. For the one
219 edge which goes to the right block, fix up its flags. */
220 label
= TREE_OPERAND (gimple_goto_dest (stmt
), 0);
221 target_block
= label_to_block (label
);
222 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
224 if (e
->dest
!= target_block
)
225 remove_edge_and_dominated_blocks (e
);
228 /* Turn off the EDGE_ABNORMAL flag. */
229 e
->flags
&= ~EDGE_ABNORMAL
;
231 /* And set EDGE_FALLTHRU. */
232 e
->flags
|= EDGE_FALLTHRU
;
237 bitmap_set_bit (cfgcleanup_altered_bbs
, bb
->index
);
238 bitmap_set_bit (cfgcleanup_altered_bbs
, target_block
->index
);
240 /* Remove the GOTO_EXPR as it is not needed. The CFG has all the
241 relevant information we need. */
242 gsi_remove (&gsi
, true);
246 /* Check for indirect calls that have been turned into
248 else if (is_gimple_call (stmt
)
249 && gimple_call_noreturn_p (stmt
)
250 && remove_fallthru_edge (bb
->succs
))
256 /* Return true if basic block BB does nothing except pass control
257 flow to another block and that we can safely insert a label at
258 the start of the successor block.
260 As a precondition, we require that BB be not equal to
264 tree_forwarder_block_p (basic_block bb
, bool phi_wanted
)
266 gimple_stmt_iterator gsi
;
269 /* BB must have a single outgoing edge. */
270 if (single_succ_p (bb
) != 1
271 /* If PHI_WANTED is false, BB must not have any PHI nodes.
272 Otherwise, BB must have PHI nodes. */
273 || gimple_seq_empty_p (phi_nodes (bb
)) == phi_wanted
274 /* BB may not be a predecessor of EXIT_BLOCK_PTR. */
275 || single_succ (bb
) == EXIT_BLOCK_PTR
276 /* Nor should this be an infinite loop. */
277 || single_succ (bb
) == bb
278 /* BB may not have an abnormal outgoing edge. */
279 || (single_succ_edge (bb
)->flags
& EDGE_ABNORMAL
))
282 gcc_checking_assert (bb
!= ENTRY_BLOCK_PTR
);
284 locus
= single_succ_edge (bb
)->goto_locus
;
286 /* There should not be an edge coming from entry, or an EH edge. */
291 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
292 if (e
->src
== ENTRY_BLOCK_PTR
|| (e
->flags
& EDGE_EH
))
294 /* If goto_locus of any of the edges differs, prevent removing
295 the forwarder block for -O0. */
296 else if (optimize
== 0 && e
->goto_locus
!= locus
)
300 /* Now walk through the statements backward. We can ignore labels,
301 anything else means this is not a forwarder block. */
302 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
304 gimple stmt
= gsi_stmt (gsi
);
306 switch (gimple_code (stmt
))
309 if (DECL_NONLOCAL (gimple_label_label (stmt
)))
311 if (optimize
== 0 && gimple_location (stmt
) != locus
)
315 /* ??? For now, hope there's a corresponding debug
316 assignment at the destination. */
328 /* Protect loop latches, headers and preheaders. */
329 if (bb
->loop_father
->header
== bb
)
331 dest
= EDGE_SUCC (bb
, 0)->dest
;
333 if (dest
->loop_father
->header
== dest
)
339 /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
340 those alternatives are equal in each of the PHI nodes, then return
341 true, else return false. */
344 phi_alternatives_equal (basic_block dest
, edge e1
, edge e2
)
346 int n1
= e1
->dest_idx
;
347 int n2
= e2
->dest_idx
;
348 gimple_stmt_iterator gsi
;
350 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
352 gimple phi
= gsi_stmt (gsi
);
353 tree val1
= gimple_phi_arg_def (phi
, n1
);
354 tree val2
= gimple_phi_arg_def (phi
, n2
);
356 gcc_assert (val1
!= NULL_TREE
);
357 gcc_assert (val2
!= NULL_TREE
);
359 if (!operand_equal_for_phi_arg_p (val1
, val2
))
366 /* Removes forwarder block BB. Returns false if this failed. */
369 remove_forwarder_block (basic_block bb
)
371 edge succ
= single_succ_edge (bb
), e
, s
;
372 basic_block dest
= succ
->dest
;
375 gimple_stmt_iterator gsi
, gsi_to
;
376 bool can_move_debug_stmts
;
378 /* We check for infinite loops already in tree_forwarder_block_p.
379 However it may happen that the infinite loop is created
380 afterwards due to removal of forwarders. */
384 /* If the destination block consists of a nonlocal label or is a
385 EH landing pad, do not merge it. */
386 label
= first_stmt (dest
);
388 && gimple_code (label
) == GIMPLE_LABEL
389 && (DECL_NONLOCAL (gimple_label_label (label
))
390 || EH_LANDING_PAD_NR (gimple_label_label (label
)) != 0))
393 /* If there is an abnormal edge to basic block BB, but not into
394 dest, problems might occur during removal of the phi node at out
395 of ssa due to overlapping live ranges of registers.
397 If there is an abnormal edge in DEST, the problems would occur
398 anyway since cleanup_dead_labels would then merge the labels for
399 two different eh regions, and rest of exception handling code
402 So if there is an abnormal edge to BB, proceed only if there is
403 no abnormal edge to DEST and there are no phi nodes in DEST. */
404 if (bb_has_abnormal_pred (bb
)
405 && (bb_has_abnormal_pred (dest
)
406 || !gimple_seq_empty_p (phi_nodes (dest
))))
409 /* If there are phi nodes in DEST, and some of the blocks that are
410 predecessors of BB are also predecessors of DEST, check that the
411 phi node arguments match. */
412 if (!gimple_seq_empty_p (phi_nodes (dest
)))
414 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
416 s
= find_edge (e
->src
, dest
);
420 if (!phi_alternatives_equal (dest
, succ
, s
))
425 can_move_debug_stmts
= single_pred_p (dest
);
427 /* Redirect the edges. */
428 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
430 bitmap_set_bit (cfgcleanup_altered_bbs
, e
->src
->index
);
432 if (e
->flags
& EDGE_ABNORMAL
)
434 /* If there is an abnormal edge, redirect it anyway, and
435 move the labels to the new block to make it legal. */
436 s
= redirect_edge_succ_nodup (e
, dest
);
439 s
= redirect_edge_and_branch (e
, dest
);
443 /* Create arguments for the phi nodes, since the edge was not
445 for (gsi
= gsi_start_phis (dest
);
449 gimple phi
= gsi_stmt (gsi
);
450 source_location l
= gimple_phi_arg_location_from_edge (phi
, succ
);
451 add_phi_arg (phi
, gimple_phi_arg_def (phi
, succ
->dest_idx
), s
, l
);
456 /* Move nonlocal labels and computed goto targets as well as user
457 defined labels and labels with an EH landing pad number to the
458 new block, so that the redirection of the abnormal edges works,
459 jump targets end up in a sane place and debug information for
460 labels is retained. */
461 gsi_to
= gsi_start_bb (dest
);
462 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
465 label
= gsi_stmt (gsi
);
466 if (is_gimple_debug (label
))
468 decl
= gimple_label_label (label
);
469 if (EH_LANDING_PAD_NR (decl
) != 0
470 || DECL_NONLOCAL (decl
)
471 || FORCED_LABEL (decl
)
472 || !DECL_ARTIFICIAL (decl
))
474 gsi_remove (&gsi
, false);
475 gsi_insert_before (&gsi_to
, label
, GSI_SAME_STMT
);
481 /* Move debug statements if the destination has just a single
483 if (can_move_debug_stmts
)
485 gsi_to
= gsi_after_labels (dest
);
486 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); )
488 gimple debug
= gsi_stmt (gsi
);
489 if (!is_gimple_debug (debug
))
491 gsi_remove (&gsi
, false);
492 gsi_insert_before (&gsi_to
, debug
, GSI_SAME_STMT
);
496 bitmap_set_bit (cfgcleanup_altered_bbs
, dest
->index
);
498 /* Update the dominators. */
499 if (dom_info_available_p (CDI_DOMINATORS
))
501 basic_block dom
, dombb
, domdest
;
503 dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
504 domdest
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
507 /* Shortcut to avoid calling (relatively expensive)
508 nearest_common_dominator unless necessary. */
512 dom
= nearest_common_dominator (CDI_DOMINATORS
, domdest
, dombb
);
514 set_immediate_dominator (CDI_DOMINATORS
, dest
, dom
);
517 /* And kill the forwarder block. */
518 delete_basic_block (bb
);
523 /* STMT is a call that has been discovered noreturn. Fixup the CFG
524 and remove LHS. Return true if something changed. */
527 fixup_noreturn_call (gimple stmt
)
529 basic_block bb
= gimple_bb (stmt
);
530 bool changed
= false;
532 if (gimple_call_builtin_p (stmt
, BUILT_IN_RETURN
))
535 /* First split basic block if stmt is not last. */
536 if (stmt
!= gsi_stmt (gsi_last_bb (bb
)))
537 split_block (bb
, stmt
);
539 changed
|= remove_fallthru_edge (bb
->succs
);
541 /* If there is LHS, remove it. */
542 if (gimple_call_lhs (stmt
))
544 tree op
= gimple_call_lhs (stmt
);
545 gimple_call_set_lhs (stmt
, NULL_TREE
);
547 /* We need to remove SSA name to avoid checking errors.
548 All uses are dominated by the noreturn and thus will
549 be removed afterwards.
550 We proactively remove affected non-PHI statements to avoid
551 fixup_cfg from trying to update them and crashing. */
552 if (TREE_CODE (op
) == SSA_NAME
)
555 imm_use_iterator iter
;
558 unsigned int bb_index
;
560 bitmap blocks
= BITMAP_ALLOC (NULL
);
562 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, op
)
564 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
565 bitmap_set_bit (blocks
, gimple_bb (use_stmt
)->index
);
567 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
568 SET_USE (use_p
, error_mark_node
);
570 EXECUTE_IF_SET_IN_BITMAP (blocks
, 0, bb_index
, bi
)
571 delete_basic_block (BASIC_BLOCK (bb_index
));
572 BITMAP_FREE (blocks
);
573 release_ssa_name (op
);
578 /* Similarly remove VDEF if there is any. */
579 else if (gimple_vdef (stmt
))
585 /* Split basic blocks on calls in the middle of a basic block that are now
586 known not to return, and remove the unreachable code. */
589 split_bbs_on_noreturn_calls (void)
591 bool changed
= false;
595 /* Detect cases where a mid-block call is now known not to return. */
597 while (VEC_length (gimple
, MODIFIED_NORETURN_CALLS (cfun
)))
599 stmt
= VEC_pop (gimple
, MODIFIED_NORETURN_CALLS (cfun
));
600 bb
= gimple_bb (stmt
);
601 /* BB might be deleted at this point, so verify first
602 BB is present in the cfg. */
604 || bb
->index
< NUM_FIXED_BLOCKS
605 || bb
->index
>= n_basic_blocks
606 || BASIC_BLOCK (bb
->index
) != bb
607 || !gimple_call_noreturn_p (stmt
))
610 changed
|= fixup_noreturn_call (stmt
);
616 /* If GIMPLE_OMP_RETURN in basic block BB is unreachable, remove it. */
619 cleanup_omp_return (basic_block bb
)
621 gimple stmt
= last_stmt (bb
);
622 basic_block control_bb
;
625 || gimple_code (stmt
) != GIMPLE_OMP_RETURN
626 || !single_pred_p (bb
))
629 control_bb
= single_pred (bb
);
630 stmt
= last_stmt (control_bb
);
632 if (stmt
== NULL
|| gimple_code (stmt
) != GIMPLE_OMP_SECTIONS_SWITCH
)
635 /* The block with the control statement normally has two entry edges -- one
636 from entry, one from continue. If continue is removed, return is
637 unreachable, so we remove it here as well. */
638 if (EDGE_COUNT (control_bb
->preds
) == 2)
641 gcc_assert (EDGE_COUNT (control_bb
->preds
) == 1);
642 remove_edge_and_dominated_blocks (single_pred_edge (bb
));
646 /* Tries to cleanup cfg in basic block BB. Returns true if anything
650 cleanup_tree_cfg_bb (basic_block bb
)
654 if (cleanup_omp_return (bb
))
657 retval
= cleanup_control_flow_bb (bb
);
659 if (tree_forwarder_block_p (bb
, false)
660 && remove_forwarder_block (bb
))
663 /* Merging the blocks may create new opportunities for folding
664 conditional branches (due to the elimination of single-valued PHI
666 if (single_succ_p (bb
)
667 && can_merge_blocks_p (bb
, single_succ (bb
)))
669 merge_blocks (bb
, single_succ (bb
));
676 /* Iterate the cfg cleanups, while anything changes. */
679 cleanup_tree_cfg_1 (void)
685 retval
|= split_bbs_on_noreturn_calls ();
687 /* Prepare the worklists of altered blocks. */
688 cfgcleanup_altered_bbs
= BITMAP_ALLOC (NULL
);
690 /* During forwarder block cleanup, we may redirect edges out of
691 SWITCH_EXPRs, which can get expensive. So we want to enable
692 recording of edge to CASE_LABEL_EXPR. */
693 start_recording_case_labels ();
695 /* Start by iterating over all basic blocks. We cannot use FOR_EACH_BB,
696 since the basic blocks may get removed. */
697 n
= last_basic_block
;
698 for (i
= NUM_FIXED_BLOCKS
; i
< n
; i
++)
700 bb
= BASIC_BLOCK (i
);
702 retval
|= cleanup_tree_cfg_bb (bb
);
705 /* Now process the altered blocks, as long as any are available. */
706 while (!bitmap_empty_p (cfgcleanup_altered_bbs
))
708 i
= bitmap_first_set_bit (cfgcleanup_altered_bbs
);
709 bitmap_clear_bit (cfgcleanup_altered_bbs
, i
);
710 if (i
< NUM_FIXED_BLOCKS
)
713 bb
= BASIC_BLOCK (i
);
717 retval
|= cleanup_tree_cfg_bb (bb
);
719 /* Rerun split_bbs_on_noreturn_calls, in case we have altered any noreturn
721 retval
|= split_bbs_on_noreturn_calls ();
724 end_recording_case_labels ();
725 BITMAP_FREE (cfgcleanup_altered_bbs
);
730 /* Remove unreachable blocks and other miscellaneous clean up work.
731 Return true if the flowgraph was modified, false otherwise. */
734 cleanup_tree_cfg_noloop (void)
738 timevar_push (TV_TREE_CLEANUP_CFG
);
740 /* Iterate until there are no more cleanups left to do. If any
741 iteration changed the flowgraph, set CHANGED to true.
743 If dominance information is available, there cannot be any unreachable
745 if (!dom_info_available_p (CDI_DOMINATORS
))
747 changed
= delete_unreachable_blocks ();
748 calculate_dominance_info (CDI_DOMINATORS
);
752 #ifdef ENABLE_CHECKING
753 verify_dominators (CDI_DOMINATORS
);
758 changed
|= cleanup_tree_cfg_1 ();
760 gcc_assert (dom_info_available_p (CDI_DOMINATORS
));
763 #ifdef ENABLE_CHECKING
767 timevar_pop (TV_TREE_CLEANUP_CFG
);
769 if (changed
&& current_loops
)
770 loops_state_set (LOOPS_NEED_FIXUP
);
775 /* Repairs loop structures. */
778 repair_loop_structures (void)
780 bitmap changed_bbs
= BITMAP_ALLOC (NULL
);
781 fix_loop_structure (changed_bbs
);
783 /* This usually does nothing. But sometimes parts of cfg that originally
784 were inside a loop get out of it due to edge removal (since they
785 become unreachable by back edges from latch). */
786 if (loops_state_satisfies_p (LOOP_CLOSED_SSA
))
787 rewrite_into_loop_closed_ssa (changed_bbs
, TODO_update_ssa
);
789 BITMAP_FREE (changed_bbs
);
791 #ifdef ENABLE_CHECKING
792 verify_loop_structure ();
796 loops_state_clear (LOOPS_NEED_FIXUP
);
799 /* Cleanup cfg and repair loop structures. */
802 cleanup_tree_cfg (void)
804 bool changed
= cleanup_tree_cfg_noloop ();
806 if (current_loops
!= NULL
807 && loops_state_satisfies_p (LOOPS_NEED_FIXUP
))
808 repair_loop_structures ();
813 /* Merge the PHI nodes at BB into those at BB's sole successor. */
816 remove_forwarder_block_with_phi (basic_block bb
)
818 edge succ
= single_succ_edge (bb
);
819 basic_block dest
= succ
->dest
;
821 basic_block dombb
, domdest
, dom
;
823 /* We check for infinite loops already in tree_forwarder_block_p.
824 However it may happen that the infinite loop is created
825 afterwards due to removal of forwarders. */
829 /* If the destination block consists of a nonlocal label, do not
831 label
= first_stmt (dest
);
833 && gimple_code (label
) == GIMPLE_LABEL
834 && DECL_NONLOCAL (gimple_label_label (label
)))
837 /* Redirect each incoming edge to BB to DEST. */
838 while (EDGE_COUNT (bb
->preds
) > 0)
840 edge e
= EDGE_PRED (bb
, 0), s
;
841 gimple_stmt_iterator gsi
;
843 s
= find_edge (e
->src
, dest
);
846 /* We already have an edge S from E->src to DEST. If S and
847 E->dest's sole successor edge have the same PHI arguments
848 at DEST, redirect S to DEST. */
849 if (phi_alternatives_equal (dest
, s
, succ
))
851 e
= redirect_edge_and_branch (e
, dest
);
852 redirect_edge_var_map_clear (e
);
856 /* PHI arguments are different. Create a forwarder block by
857 splitting E so that we can merge PHI arguments on E to
859 e
= single_succ_edge (split_edge (e
));
862 s
= redirect_edge_and_branch (e
, dest
);
864 /* redirect_edge_and_branch must not create a new edge. */
867 /* Add to the PHI nodes at DEST each PHI argument removed at the
869 for (gsi
= gsi_start_phis (dest
);
873 gimple phi
= gsi_stmt (gsi
);
874 tree def
= gimple_phi_arg_def (phi
, succ
->dest_idx
);
875 source_location locus
= gimple_phi_arg_location_from_edge (phi
, succ
);
877 if (TREE_CODE (def
) == SSA_NAME
)
879 edge_var_map_vector head
;
883 /* If DEF is one of the results of PHI nodes removed during
884 redirection, replace it with the PHI argument that used
886 head
= redirect_edge_var_map_vector (e
);
887 FOR_EACH_VEC_ELT (edge_var_map
, head
, i
, vm
)
889 tree old_arg
= redirect_edge_var_map_result (vm
);
890 tree new_arg
= redirect_edge_var_map_def (vm
);
895 locus
= redirect_edge_var_map_location (vm
);
901 add_phi_arg (phi
, def
, s
, locus
);
904 redirect_edge_var_map_clear (e
);
907 /* Update the dominators. */
908 dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
909 domdest
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
912 /* Shortcut to avoid calling (relatively expensive)
913 nearest_common_dominator unless necessary. */
917 dom
= nearest_common_dominator (CDI_DOMINATORS
, domdest
, dombb
);
919 set_immediate_dominator (CDI_DOMINATORS
, dest
, dom
);
921 /* Remove BB since all of BB's incoming edges have been redirected
923 delete_basic_block (bb
);
926 /* This pass merges PHI nodes if one feeds into another. For example,
927 suppose we have the following:
934 # tem_6 = PHI <tem_17(8), tem_23(7)>;
937 # tem_3 = PHI <tem_6(9), tem_2(5)>;
940 Then we merge the first PHI node into the second one like so:
947 # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
952 merge_phi_nodes (void)
954 basic_block
*worklist
= XNEWVEC (basic_block
, n_basic_blocks
);
955 basic_block
*current
= worklist
;
958 calculate_dominance_info (CDI_DOMINATORS
);
960 /* Find all PHI nodes that we may be able to merge. */
965 /* Look for a forwarder block with PHI nodes. */
966 if (!tree_forwarder_block_p (bb
, true))
969 dest
= single_succ (bb
);
971 /* We have to feed into another basic block with PHI
973 if (gimple_seq_empty_p (phi_nodes (dest
))
974 /* We don't want to deal with a basic block with
976 || bb_has_abnormal_pred (bb
))
979 if (!dominated_by_p (CDI_DOMINATORS
, dest
, bb
))
981 /* If BB does not dominate DEST, then the PHI nodes at
982 DEST must be the only users of the results of the PHI
988 gimple_stmt_iterator gsi
;
989 unsigned int dest_idx
= single_succ_edge (bb
)->dest_idx
;
991 /* BB dominates DEST. There may be many users of the PHI
992 nodes in BB. However, there is still a trivial case we
993 can handle. If the result of every PHI in BB is used
994 only by a PHI in DEST, then we can trivially merge the
995 PHI nodes from BB into DEST. */
996 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
999 gimple phi
= gsi_stmt (gsi
);
1000 tree result
= gimple_phi_result (phi
);
1001 use_operand_p imm_use
;
1004 /* If the PHI's result is never used, then we can just
1006 if (has_zero_uses (result
))
1009 /* Get the single use of the result of this PHI node. */
1010 if (!single_imm_use (result
, &imm_use
, &use_stmt
)
1011 || gimple_code (use_stmt
) != GIMPLE_PHI
1012 || gimple_bb (use_stmt
) != dest
1013 || gimple_phi_arg_def (use_stmt
, dest_idx
) != result
)
1017 /* If the loop above iterated through all the PHI nodes
1018 in BB, then we can merge the PHIs from BB into DEST. */
1019 if (gsi_end_p (gsi
))
1024 /* Now let's drain WORKLIST. */
1025 while (current
!= worklist
)
1028 remove_forwarder_block_with_phi (bb
);
1036 gate_merge_phi (void)
1041 struct gimple_opt_pass pass_merge_phi
=
1045 "mergephi", /* name */
1046 gate_merge_phi
, /* gate */
1047 merge_phi_nodes
, /* execute */
1050 0, /* static_pass_number */
1051 TV_TREE_MERGE_PHI
, /* tv_id */
1052 PROP_cfg
| PROP_ssa
, /* properties_required */
1053 0, /* properties_provided */
1054 0, /* properties_destroyed */
1055 0, /* todo_flags_start */
1056 TODO_dump_func
| TODO_ggc_collect
/* todo_flags_finish */