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"
35 #include "tree-dump.h"
36 #include "tree-pass.h"
40 #include "tree-ssa-propagate.h"
41 #include "tree-scalar-evolution.h"
43 /* The set of blocks in that at least one of the following changes happened:
44 -- the statement at the end of the block was changed
45 -- the block was newly created
46 -- the set of the predecessors of the block changed
47 -- the set of the successors of the block changed
48 ??? Maybe we could track these changes separately, since they determine
49 what cleanups it makes sense to try on the block. */
50 bitmap cfgcleanup_altered_bbs
;
52 /* Remove any fallthru edge from EV. Return true if an edge was removed. */
55 remove_fallthru_edge (VEC(edge
,gc
) *ev
)
60 FOR_EACH_EDGE (e
, ei
, ev
)
61 if ((e
->flags
& EDGE_FALLTHRU
) != 0)
63 remove_edge_and_dominated_blocks (e
);
70 /* Disconnect an unreachable block in the control expression starting
74 cleanup_control_expr_graph (basic_block bb
, gimple_stmt_iterator gsi
)
78 gimple stmt
= gsi_stmt (gsi
);
81 if (!single_succ_p (bb
))
88 fold_defer_overflow_warnings ();
89 loc
= gimple_location (stmt
);
90 switch (gimple_code (stmt
))
94 tree lhs
= gimple_cond_lhs (stmt
);
95 tree rhs
= gimple_cond_rhs (stmt
);
96 /* For conditions try harder and lookup single-argument
97 PHI nodes. Only do so from the same basic-block though
98 as other basic-blocks may be dead already. */
99 if (TREE_CODE (lhs
) == SSA_NAME
100 && !name_registered_for_update_p (lhs
))
102 gimple def_stmt
= SSA_NAME_DEF_STMT (lhs
);
103 if (gimple_code (def_stmt
) == GIMPLE_PHI
104 && gimple_phi_num_args (def_stmt
) == 1
105 && gimple_bb (def_stmt
) == gimple_bb (stmt
)
106 && (TREE_CODE (PHI_ARG_DEF (def_stmt
, 0)) != SSA_NAME
107 || !name_registered_for_update_p (PHI_ARG_DEF (def_stmt
,
109 lhs
= PHI_ARG_DEF (def_stmt
, 0);
111 if (TREE_CODE (rhs
) == SSA_NAME
112 && !name_registered_for_update_p (rhs
))
114 gimple def_stmt
= SSA_NAME_DEF_STMT (rhs
);
115 if (gimple_code (def_stmt
) == GIMPLE_PHI
116 && gimple_phi_num_args (def_stmt
) == 1
117 && gimple_bb (def_stmt
) == gimple_bb (stmt
)
118 && (TREE_CODE (PHI_ARG_DEF (def_stmt
, 0)) != SSA_NAME
119 || !name_registered_for_update_p (PHI_ARG_DEF (def_stmt
,
121 rhs
= PHI_ARG_DEF (def_stmt
, 0);
123 val
= fold_binary_loc (loc
, gimple_cond_code (stmt
),
124 boolean_type_node
, lhs
, rhs
);
129 val
= gimple_switch_index (stmt
);
135 taken_edge
= find_taken_edge (bb
, val
);
138 fold_undefer_and_ignore_overflow_warnings ();
142 /* Remove all the edges except the one that is always executed. */
144 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
150 fold_undefer_overflow_warnings
151 (true, stmt
, WARN_STRICT_OVERFLOW_CONDITIONAL
);
155 taken_edge
->probability
+= e
->probability
;
156 taken_edge
->count
+= e
->count
;
157 remove_edge_and_dominated_blocks (e
);
164 fold_undefer_and_ignore_overflow_warnings ();
165 if (taken_edge
->probability
> REG_BR_PROB_BASE
)
166 taken_edge
->probability
= REG_BR_PROB_BASE
;
169 taken_edge
= single_succ_edge (bb
);
171 bitmap_set_bit (cfgcleanup_altered_bbs
, bb
->index
);
172 gsi_remove (&gsi
, true);
173 taken_edge
->flags
= EDGE_FALLTHRU
;
178 /* Try to remove superfluous control structures in basic block BB. Returns
179 true if anything changes. */
182 cleanup_control_flow_bb (basic_block bb
)
184 gimple_stmt_iterator gsi
;
188 /* If the last statement of the block could throw and now cannot,
189 we need to prune cfg. */
190 retval
|= gimple_purge_dead_eh_edges (bb
);
192 gsi
= gsi_last_bb (bb
);
196 stmt
= gsi_stmt (gsi
);
198 if (gimple_code (stmt
) == GIMPLE_COND
199 || gimple_code (stmt
) == GIMPLE_SWITCH
)
200 retval
|= cleanup_control_expr_graph (bb
, gsi
);
201 else if (gimple_code (stmt
) == GIMPLE_GOTO
202 && TREE_CODE (gimple_goto_dest (stmt
)) == ADDR_EXPR
203 && (TREE_CODE (TREE_OPERAND (gimple_goto_dest (stmt
), 0))
206 /* If we had a computed goto which has a compile-time determinable
207 destination, then we can eliminate the goto. */
211 basic_block target_block
;
213 /* First look at all the outgoing edges. Delete any outgoing
214 edges which do not go to the right block. For the one
215 edge which goes to the right block, fix up its flags. */
216 label
= TREE_OPERAND (gimple_goto_dest (stmt
), 0);
217 target_block
= label_to_block (label
);
218 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
220 if (e
->dest
!= target_block
)
221 remove_edge_and_dominated_blocks (e
);
224 /* Turn off the EDGE_ABNORMAL flag. */
225 e
->flags
&= ~EDGE_ABNORMAL
;
227 /* And set EDGE_FALLTHRU. */
228 e
->flags
|= EDGE_FALLTHRU
;
233 bitmap_set_bit (cfgcleanup_altered_bbs
, bb
->index
);
234 bitmap_set_bit (cfgcleanup_altered_bbs
, target_block
->index
);
236 /* Remove the GOTO_EXPR as it is not needed. The CFG has all the
237 relevant information we need. */
238 gsi_remove (&gsi
, true);
242 /* Check for indirect calls that have been turned into
244 else if (is_gimple_call (stmt
)
245 && gimple_call_noreturn_p (stmt
)
246 && remove_fallthru_edge (bb
->succs
))
252 /* Return true if basic block BB does nothing except pass control
253 flow to another block and that we can safely insert a label at
254 the start of the successor block.
256 As a precondition, we require that BB be not equal to
260 tree_forwarder_block_p (basic_block bb
, bool phi_wanted
)
262 gimple_stmt_iterator gsi
;
265 /* BB must have a single outgoing edge. */
266 if (single_succ_p (bb
) != 1
267 /* If PHI_WANTED is false, BB must not have any PHI nodes.
268 Otherwise, BB must have PHI nodes. */
269 || gimple_seq_empty_p (phi_nodes (bb
)) == phi_wanted
270 /* BB may not be a predecessor of EXIT_BLOCK_PTR. */
271 || single_succ (bb
) == EXIT_BLOCK_PTR
272 /* Nor should this be an infinite loop. */
273 || single_succ (bb
) == bb
274 /* BB may not have an abnormal outgoing edge. */
275 || (single_succ_edge (bb
)->flags
& EDGE_ABNORMAL
))
278 gcc_checking_assert (bb
!= ENTRY_BLOCK_PTR
);
280 locus
= single_succ_edge (bb
)->goto_locus
;
282 /* There should not be an edge coming from entry, or an EH edge. */
287 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
288 if (e
->src
== ENTRY_BLOCK_PTR
|| (e
->flags
& EDGE_EH
))
290 /* If goto_locus of any of the edges differs, prevent removing
291 the forwarder block for -O0. */
292 else if (optimize
== 0 && e
->goto_locus
!= locus
)
296 /* Now walk through the statements backward. We can ignore labels,
297 anything else means this is not a forwarder block. */
298 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
300 gimple stmt
= gsi_stmt (gsi
);
302 switch (gimple_code (stmt
))
305 if (DECL_NONLOCAL (gimple_label_label (stmt
)))
307 if (optimize
== 0 && gimple_location (stmt
) != locus
)
311 /* ??? For now, hope there's a corresponding debug
312 assignment at the destination. */
324 /* Protect loop latches, headers and preheaders. */
325 if (bb
->loop_father
->header
== bb
)
327 dest
= EDGE_SUCC (bb
, 0)->dest
;
329 if (dest
->loop_father
->header
== dest
)
335 /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
336 those alternatives are equal in each of the PHI nodes, then return
337 true, else return false. */
340 phi_alternatives_equal (basic_block dest
, edge e1
, edge e2
)
342 int n1
= e1
->dest_idx
;
343 int n2
= e2
->dest_idx
;
344 gimple_stmt_iterator gsi
;
346 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
348 gimple phi
= gsi_stmt (gsi
);
349 tree val1
= gimple_phi_arg_def (phi
, n1
);
350 tree val2
= gimple_phi_arg_def (phi
, n2
);
352 gcc_assert (val1
!= NULL_TREE
);
353 gcc_assert (val2
!= NULL_TREE
);
355 if (!operand_equal_for_phi_arg_p (val1
, val2
))
362 /* Removes forwarder block BB. Returns false if this failed. */
365 remove_forwarder_block (basic_block bb
)
367 edge succ
= single_succ_edge (bb
), e
, s
;
368 basic_block dest
= succ
->dest
;
371 gimple_stmt_iterator gsi
, gsi_to
;
372 bool can_move_debug_stmts
;
374 /* We check for infinite loops already in tree_forwarder_block_p.
375 However it may happen that the infinite loop is created
376 afterwards due to removal of forwarders. */
380 /* If the destination block consists of a nonlocal label or is a
381 EH landing pad, do not merge it. */
382 label
= first_stmt (dest
);
384 && gimple_code (label
) == GIMPLE_LABEL
385 && (DECL_NONLOCAL (gimple_label_label (label
))
386 || EH_LANDING_PAD_NR (gimple_label_label (label
)) != 0))
389 /* If there is an abnormal edge to basic block BB, but not into
390 dest, problems might occur during removal of the phi node at out
391 of ssa due to overlapping live ranges of registers.
393 If there is an abnormal edge in DEST, the problems would occur
394 anyway since cleanup_dead_labels would then merge the labels for
395 two different eh regions, and rest of exception handling code
398 So if there is an abnormal edge to BB, proceed only if there is
399 no abnormal edge to DEST and there are no phi nodes in DEST. */
400 if (bb_has_abnormal_pred (bb
)
401 && (bb_has_abnormal_pred (dest
)
402 || !gimple_seq_empty_p (phi_nodes (dest
))))
405 /* If there are phi nodes in DEST, and some of the blocks that are
406 predecessors of BB are also predecessors of DEST, check that the
407 phi node arguments match. */
408 if (!gimple_seq_empty_p (phi_nodes (dest
)))
410 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
412 s
= find_edge (e
->src
, dest
);
416 if (!phi_alternatives_equal (dest
, succ
, s
))
421 can_move_debug_stmts
= MAY_HAVE_DEBUG_STMTS
&& single_pred_p (dest
);
423 /* Redirect the edges. */
424 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
426 bitmap_set_bit (cfgcleanup_altered_bbs
, e
->src
->index
);
428 if (e
->flags
& EDGE_ABNORMAL
)
430 /* If there is an abnormal edge, redirect it anyway, and
431 move the labels to the new block to make it legal. */
432 s
= redirect_edge_succ_nodup (e
, dest
);
435 s
= redirect_edge_and_branch (e
, dest
);
439 /* Create arguments for the phi nodes, since the edge was not
441 for (gsi
= gsi_start_phis (dest
);
445 gimple phi
= gsi_stmt (gsi
);
446 source_location l
= gimple_phi_arg_location_from_edge (phi
, succ
);
447 add_phi_arg (phi
, gimple_phi_arg_def (phi
, succ
->dest_idx
), s
, l
);
452 /* Move nonlocal labels and computed goto targets as well as user
453 defined labels and labels with an EH landing pad number to the
454 new block, so that the redirection of the abnormal edges works,
455 jump targets end up in a sane place and debug information for
456 labels is retained. */
457 gsi_to
= gsi_start_bb (dest
);
458 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
461 label
= gsi_stmt (gsi
);
462 if (is_gimple_debug (label
))
464 decl
= gimple_label_label (label
);
465 if (EH_LANDING_PAD_NR (decl
) != 0
466 || DECL_NONLOCAL (decl
)
467 || FORCED_LABEL (decl
)
468 || !DECL_ARTIFICIAL (decl
))
470 gsi_remove (&gsi
, false);
471 gsi_insert_before (&gsi_to
, label
, GSI_SAME_STMT
);
477 /* Move debug statements if the destination has a single predecessor. */
478 if (can_move_debug_stmts
)
480 gsi_to
= gsi_after_labels (dest
);
481 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); )
483 gimple debug
= gsi_stmt (gsi
);
484 if (!is_gimple_debug (debug
))
486 gsi_remove (&gsi
, false);
487 gsi_insert_before (&gsi_to
, debug
, GSI_SAME_STMT
);
491 bitmap_set_bit (cfgcleanup_altered_bbs
, dest
->index
);
493 /* Update the dominators. */
494 if (dom_info_available_p (CDI_DOMINATORS
))
496 basic_block dom
, dombb
, domdest
;
498 dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
499 domdest
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
502 /* Shortcut to avoid calling (relatively expensive)
503 nearest_common_dominator unless necessary. */
507 dom
= nearest_common_dominator (CDI_DOMINATORS
, domdest
, dombb
);
509 set_immediate_dominator (CDI_DOMINATORS
, dest
, dom
);
512 /* And kill the forwarder block. */
513 delete_basic_block (bb
);
518 /* STMT is a call that has been discovered noreturn. Fixup the CFG
519 and remove LHS. Return true if something changed. */
522 fixup_noreturn_call (gimple stmt
)
524 basic_block bb
= gimple_bb (stmt
);
525 bool changed
= false;
527 if (gimple_call_builtin_p (stmt
, BUILT_IN_RETURN
))
530 /* First split basic block if stmt is not last. */
531 if (stmt
!= gsi_stmt (gsi_last_bb (bb
)))
532 split_block (bb
, stmt
);
534 changed
|= remove_fallthru_edge (bb
->succs
);
536 /* If there is LHS, remove it. */
537 if (gimple_call_lhs (stmt
))
539 tree op
= gimple_call_lhs (stmt
);
540 gimple_call_set_lhs (stmt
, NULL_TREE
);
542 /* We need to remove SSA name to avoid checking errors.
543 All uses are dominated by the noreturn and thus will
544 be removed afterwards.
545 We proactively remove affected non-PHI statements to avoid
546 fixup_cfg from trying to update them and crashing. */
547 if (TREE_CODE (op
) == SSA_NAME
)
550 imm_use_iterator iter
;
553 unsigned int bb_index
;
555 bitmap blocks
= BITMAP_ALLOC (NULL
);
557 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, op
)
559 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
560 bitmap_set_bit (blocks
, gimple_bb (use_stmt
)->index
);
562 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
563 SET_USE (use_p
, error_mark_node
);
565 EXECUTE_IF_SET_IN_BITMAP (blocks
, 0, bb_index
, bi
)
566 delete_basic_block (BASIC_BLOCK (bb_index
));
567 BITMAP_FREE (blocks
);
568 release_ssa_name (op
);
573 /* Similarly remove VDEF if there is any. */
574 else if (gimple_vdef (stmt
))
580 /* Split basic blocks on calls in the middle of a basic block that are now
581 known not to return, and remove the unreachable code. */
584 split_bbs_on_noreturn_calls (void)
586 bool changed
= false;
590 /* Detect cases where a mid-block call is now known not to return. */
592 while (VEC_length (gimple
, MODIFIED_NORETURN_CALLS (cfun
)))
594 stmt
= VEC_pop (gimple
, MODIFIED_NORETURN_CALLS (cfun
));
595 bb
= gimple_bb (stmt
);
596 /* BB might be deleted at this point, so verify first
597 BB is present in the cfg. */
599 || bb
->index
< NUM_FIXED_BLOCKS
600 || bb
->index
>= last_basic_block
601 || BASIC_BLOCK (bb
->index
) != bb
602 || !gimple_call_noreturn_p (stmt
))
605 changed
|= fixup_noreturn_call (stmt
);
611 /* If GIMPLE_OMP_RETURN in basic block BB is unreachable, remove it. */
614 cleanup_omp_return (basic_block bb
)
616 gimple stmt
= last_stmt (bb
);
617 basic_block control_bb
;
620 || gimple_code (stmt
) != GIMPLE_OMP_RETURN
621 || !single_pred_p (bb
))
624 control_bb
= single_pred (bb
);
625 stmt
= last_stmt (control_bb
);
627 if (stmt
== NULL
|| gimple_code (stmt
) != GIMPLE_OMP_SECTIONS_SWITCH
)
630 /* The block with the control statement normally has two entry edges -- one
631 from entry, one from continue. If continue is removed, return is
632 unreachable, so we remove it here as well. */
633 if (EDGE_COUNT (control_bb
->preds
) == 2)
636 gcc_assert (EDGE_COUNT (control_bb
->preds
) == 1);
637 remove_edge_and_dominated_blocks (single_pred_edge (bb
));
641 /* Tries to cleanup cfg in basic block BB. Returns true if anything
645 cleanup_tree_cfg_bb (basic_block bb
)
649 if (cleanup_omp_return (bb
))
652 retval
= cleanup_control_flow_bb (bb
);
654 if (tree_forwarder_block_p (bb
, false)
655 && remove_forwarder_block (bb
))
658 /* Merging the blocks may create new opportunities for folding
659 conditional branches (due to the elimination of single-valued PHI
661 if (single_succ_p (bb
)
662 && can_merge_blocks_p (bb
, single_succ (bb
)))
664 merge_blocks (bb
, single_succ (bb
));
671 /* Iterate the cfg cleanups, while anything changes. */
674 cleanup_tree_cfg_1 (void)
680 retval
|= split_bbs_on_noreturn_calls ();
682 /* Prepare the worklists of altered blocks. */
683 cfgcleanup_altered_bbs
= BITMAP_ALLOC (NULL
);
685 /* During forwarder block cleanup, we may redirect edges out of
686 SWITCH_EXPRs, which can get expensive. So we want to enable
687 recording of edge to CASE_LABEL_EXPR. */
688 start_recording_case_labels ();
690 /* Start by iterating over all basic blocks. We cannot use FOR_EACH_BB,
691 since the basic blocks may get removed. */
692 n
= last_basic_block
;
693 for (i
= NUM_FIXED_BLOCKS
; i
< n
; i
++)
695 bb
= BASIC_BLOCK (i
);
697 retval
|= cleanup_tree_cfg_bb (bb
);
700 /* Now process the altered blocks, as long as any are available. */
701 while (!bitmap_empty_p (cfgcleanup_altered_bbs
))
703 i
= bitmap_first_set_bit (cfgcleanup_altered_bbs
);
704 bitmap_clear_bit (cfgcleanup_altered_bbs
, i
);
705 if (i
< NUM_FIXED_BLOCKS
)
708 bb
= BASIC_BLOCK (i
);
712 retval
|= cleanup_tree_cfg_bb (bb
);
714 /* Rerun split_bbs_on_noreturn_calls, in case we have altered any noreturn
716 retval
|= split_bbs_on_noreturn_calls ();
719 end_recording_case_labels ();
720 BITMAP_FREE (cfgcleanup_altered_bbs
);
725 /* Remove unreachable blocks and other miscellaneous clean up work.
726 Return true if the flowgraph was modified, false otherwise. */
729 cleanup_tree_cfg_noloop (void)
733 timevar_push (TV_TREE_CLEANUP_CFG
);
735 /* Iterate until there are no more cleanups left to do. If any
736 iteration changed the flowgraph, set CHANGED to true.
738 If dominance information is available, there cannot be any unreachable
740 if (!dom_info_available_p (CDI_DOMINATORS
))
742 changed
= delete_unreachable_blocks ();
743 calculate_dominance_info (CDI_DOMINATORS
);
747 #ifdef ENABLE_CHECKING
748 verify_dominators (CDI_DOMINATORS
);
753 changed
|= cleanup_tree_cfg_1 ();
755 gcc_assert (dom_info_available_p (CDI_DOMINATORS
));
758 #ifdef ENABLE_CHECKING
762 timevar_pop (TV_TREE_CLEANUP_CFG
);
764 if (changed
&& current_loops
)
765 loops_state_set (LOOPS_NEED_FIXUP
);
770 /* Repairs loop structures. */
773 repair_loop_structures (void)
777 timevar_push (TV_REPAIR_LOOPS
);
778 changed_bbs
= BITMAP_ALLOC (NULL
);
779 fix_loop_structure (changed_bbs
);
781 /* This usually does nothing. But sometimes parts of cfg that originally
782 were inside a loop get out of it due to edge removal (since they
783 become unreachable by back edges from latch). */
784 if (loops_state_satisfies_p (LOOP_CLOSED_SSA
))
785 rewrite_into_loop_closed_ssa (changed_bbs
, TODO_update_ssa
);
787 BITMAP_FREE (changed_bbs
);
789 #ifdef ENABLE_CHECKING
790 verify_loop_structure ();
794 timevar_pop (TV_REPAIR_LOOPS
);
797 /* Cleanup cfg and repair loop structures. */
800 cleanup_tree_cfg (void)
802 bool changed
= cleanup_tree_cfg_noloop ();
804 if (current_loops
!= NULL
805 && loops_state_satisfies_p (LOOPS_NEED_FIXUP
))
806 repair_loop_structures ();
811 /* Merge the PHI nodes at BB into those at BB's sole successor. */
814 remove_forwarder_block_with_phi (basic_block bb
)
816 edge succ
= single_succ_edge (bb
);
817 basic_block dest
= succ
->dest
;
819 basic_block dombb
, domdest
, dom
;
821 /* We check for infinite loops already in tree_forwarder_block_p.
822 However it may happen that the infinite loop is created
823 afterwards due to removal of forwarders. */
827 /* If the destination block consists of a nonlocal label, do not
829 label
= first_stmt (dest
);
831 && gimple_code (label
) == GIMPLE_LABEL
832 && DECL_NONLOCAL (gimple_label_label (label
)))
835 /* Redirect each incoming edge to BB to DEST. */
836 while (EDGE_COUNT (bb
->preds
) > 0)
838 edge e
= EDGE_PRED (bb
, 0), s
;
839 gimple_stmt_iterator gsi
;
841 s
= find_edge (e
->src
, dest
);
844 /* We already have an edge S from E->src to DEST. If S and
845 E->dest's sole successor edge have the same PHI arguments
846 at DEST, redirect S to DEST. */
847 if (phi_alternatives_equal (dest
, s
, succ
))
849 e
= redirect_edge_and_branch (e
, dest
);
850 redirect_edge_var_map_clear (e
);
854 /* PHI arguments are different. Create a forwarder block by
855 splitting E so that we can merge PHI arguments on E to
857 e
= single_succ_edge (split_edge (e
));
860 s
= redirect_edge_and_branch (e
, dest
);
862 /* redirect_edge_and_branch must not create a new edge. */
865 /* Add to the PHI nodes at DEST each PHI argument removed at the
867 for (gsi
= gsi_start_phis (dest
);
871 gimple phi
= gsi_stmt (gsi
);
872 tree def
= gimple_phi_arg_def (phi
, succ
->dest_idx
);
873 source_location locus
= gimple_phi_arg_location_from_edge (phi
, succ
);
875 if (TREE_CODE (def
) == SSA_NAME
)
877 edge_var_map_vector head
;
881 /* If DEF is one of the results of PHI nodes removed during
882 redirection, replace it with the PHI argument that used
884 head
= redirect_edge_var_map_vector (e
);
885 FOR_EACH_VEC_ELT (edge_var_map
, head
, i
, vm
)
887 tree old_arg
= redirect_edge_var_map_result (vm
);
888 tree new_arg
= redirect_edge_var_map_def (vm
);
893 locus
= redirect_edge_var_map_location (vm
);
899 add_phi_arg (phi
, def
, s
, locus
);
902 redirect_edge_var_map_clear (e
);
905 /* Update the dominators. */
906 dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
907 domdest
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
910 /* Shortcut to avoid calling (relatively expensive)
911 nearest_common_dominator unless necessary. */
915 dom
= nearest_common_dominator (CDI_DOMINATORS
, domdest
, dombb
);
917 set_immediate_dominator (CDI_DOMINATORS
, dest
, dom
);
919 /* Remove BB since all of BB's incoming edges have been redirected
921 delete_basic_block (bb
);
924 /* This pass merges PHI nodes if one feeds into another. For example,
925 suppose we have the following:
932 # tem_6 = PHI <tem_17(8), tem_23(7)>;
935 # tem_3 = PHI <tem_6(9), tem_2(5)>;
938 Then we merge the first PHI node into the second one like so:
945 # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
950 merge_phi_nodes (void)
952 basic_block
*worklist
= XNEWVEC (basic_block
, n_basic_blocks
);
953 basic_block
*current
= worklist
;
956 calculate_dominance_info (CDI_DOMINATORS
);
958 /* Find all PHI nodes that we may be able to merge. */
963 /* Look for a forwarder block with PHI nodes. */
964 if (!tree_forwarder_block_p (bb
, true))
967 dest
= single_succ (bb
);
969 /* We have to feed into another basic block with PHI
971 if (gimple_seq_empty_p (phi_nodes (dest
))
972 /* We don't want to deal with a basic block with
974 || bb_has_abnormal_pred (bb
))
977 if (!dominated_by_p (CDI_DOMINATORS
, dest
, bb
))
979 /* If BB does not dominate DEST, then the PHI nodes at
980 DEST must be the only users of the results of the PHI
986 gimple_stmt_iterator gsi
;
987 unsigned int dest_idx
= single_succ_edge (bb
)->dest_idx
;
989 /* BB dominates DEST. There may be many users of the PHI
990 nodes in BB. However, there is still a trivial case we
991 can handle. If the result of every PHI in BB is used
992 only by a PHI in DEST, then we can trivially merge the
993 PHI nodes from BB into DEST. */
994 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
997 gimple phi
= gsi_stmt (gsi
);
998 tree result
= gimple_phi_result (phi
);
999 use_operand_p imm_use
;
1002 /* If the PHI's result is never used, then we can just
1004 if (has_zero_uses (result
))
1007 /* Get the single use of the result of this PHI node. */
1008 if (!single_imm_use (result
, &imm_use
, &use_stmt
)
1009 || gimple_code (use_stmt
) != GIMPLE_PHI
1010 || gimple_bb (use_stmt
) != dest
1011 || gimple_phi_arg_def (use_stmt
, dest_idx
) != result
)
1015 /* If the loop above iterated through all the PHI nodes
1016 in BB, then we can merge the PHIs from BB into DEST. */
1017 if (gsi_end_p (gsi
))
1022 /* Now let's drain WORKLIST. */
1023 while (current
!= worklist
)
1026 remove_forwarder_block_with_phi (bb
);
1034 gate_merge_phi (void)
1039 struct gimple_opt_pass pass_merge_phi
=
1043 "mergephi", /* name */
1044 gate_merge_phi
, /* gate */
1045 merge_phi_nodes
, /* execute */
1048 0, /* static_pass_number */
1049 TV_TREE_MERGE_PHI
, /* tv_id */
1050 PROP_cfg
| PROP_ssa
, /* properties_required */
1051 0, /* properties_provided */
1052 0, /* properties_destroyed */
1053 0, /* todo_flags_start */
1054 TODO_ggc_collect
/* todo_flags_finish */