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"
33 #include "langhooks.h"
34 #include "tree-flow.h"
36 #include "tree-dump.h"
37 #include "tree-pass.h"
41 #include "cfglayout.h"
43 #include "tree-ssa-propagate.h"
44 #include "tree-scalar-evolution.h"
46 /* The set of blocks in that at least one of the following changes happened:
47 -- the statement at the end of the block was changed
48 -- the block was newly created
49 -- the set of the predecessors of the block changed
50 -- the set of the successors of the block changed
51 ??? Maybe we could track these changes separately, since they determine
52 what cleanups it makes sense to try on the block. */
53 bitmap cfgcleanup_altered_bbs
;
55 /* Remove any fallthru edge from EV. Return true if an edge was removed. */
58 remove_fallthru_edge (VEC(edge
,gc
) *ev
)
63 FOR_EACH_EDGE (e
, ei
, ev
)
64 if ((e
->flags
& EDGE_FALLTHRU
) != 0)
66 remove_edge_and_dominated_blocks (e
);
73 /* Disconnect an unreachable block in the control expression starting
77 cleanup_control_expr_graph (basic_block bb
, gimple_stmt_iterator gsi
)
81 gimple stmt
= gsi_stmt (gsi
);
84 if (!single_succ_p (bb
))
91 fold_defer_overflow_warnings ();
92 loc
= gimple_location (stmt
);
93 switch (gimple_code (stmt
))
97 tree lhs
= gimple_cond_lhs (stmt
);
98 tree rhs
= gimple_cond_rhs (stmt
);
99 /* For conditions try harder and lookup single-argument
100 PHI nodes. Only do so from the same basic-block though
101 as other basic-blocks may be dead already. */
102 if (TREE_CODE (lhs
) == SSA_NAME
103 && !name_registered_for_update_p (lhs
))
105 gimple def_stmt
= SSA_NAME_DEF_STMT (lhs
);
106 if (gimple_code (def_stmt
) == GIMPLE_PHI
107 && gimple_phi_num_args (def_stmt
) == 1
108 && gimple_bb (def_stmt
) == gimple_bb (stmt
)
109 && (TREE_CODE (PHI_ARG_DEF (def_stmt
, 0)) != SSA_NAME
110 || !name_registered_for_update_p (PHI_ARG_DEF (def_stmt
,
112 lhs
= PHI_ARG_DEF (def_stmt
, 0);
114 if (TREE_CODE (rhs
) == SSA_NAME
115 && !name_registered_for_update_p (rhs
))
117 gimple def_stmt
= SSA_NAME_DEF_STMT (rhs
);
118 if (gimple_code (def_stmt
) == GIMPLE_PHI
119 && gimple_phi_num_args (def_stmt
) == 1
120 && gimple_bb (def_stmt
) == gimple_bb (stmt
)
121 && (TREE_CODE (PHI_ARG_DEF (def_stmt
, 0)) != SSA_NAME
122 || !name_registered_for_update_p (PHI_ARG_DEF (def_stmt
,
124 rhs
= PHI_ARG_DEF (def_stmt
, 0);
126 val
= fold_binary_loc (loc
, gimple_cond_code (stmt
),
127 boolean_type_node
, lhs
, rhs
);
132 val
= gimple_switch_index (stmt
);
138 taken_edge
= find_taken_edge (bb
, val
);
141 fold_undefer_and_ignore_overflow_warnings ();
145 /* Remove all the edges except the one that is always executed. */
147 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
153 fold_undefer_overflow_warnings
154 (true, stmt
, WARN_STRICT_OVERFLOW_CONDITIONAL
);
158 taken_edge
->probability
+= e
->probability
;
159 taken_edge
->count
+= e
->count
;
160 remove_edge_and_dominated_blocks (e
);
167 fold_undefer_and_ignore_overflow_warnings ();
168 if (taken_edge
->probability
> REG_BR_PROB_BASE
)
169 taken_edge
->probability
= REG_BR_PROB_BASE
;
172 taken_edge
= single_succ_edge (bb
);
174 bitmap_set_bit (cfgcleanup_altered_bbs
, bb
->index
);
175 gsi_remove (&gsi
, true);
176 taken_edge
->flags
= EDGE_FALLTHRU
;
181 /* Try to remove superfluous control structures in basic block BB. Returns
182 true if anything changes. */
185 cleanup_control_flow_bb (basic_block bb
)
187 gimple_stmt_iterator gsi
;
191 /* If the last statement of the block could throw and now cannot,
192 we need to prune cfg. */
193 retval
|= gimple_purge_dead_eh_edges (bb
);
195 gsi
= gsi_last_bb (bb
);
199 stmt
= gsi_stmt (gsi
);
201 if (gimple_code (stmt
) == GIMPLE_COND
202 || gimple_code (stmt
) == GIMPLE_SWITCH
)
203 retval
|= cleanup_control_expr_graph (bb
, gsi
);
204 else if (gimple_code (stmt
) == GIMPLE_GOTO
205 && TREE_CODE (gimple_goto_dest (stmt
)) == ADDR_EXPR
206 && (TREE_CODE (TREE_OPERAND (gimple_goto_dest (stmt
), 0))
209 /* If we had a computed goto which has a compile-time determinable
210 destination, then we can eliminate the goto. */
214 basic_block target_block
;
216 /* First look at all the outgoing edges. Delete any outgoing
217 edges which do not go to the right block. For the one
218 edge which goes to the right block, fix up its flags. */
219 label
= TREE_OPERAND (gimple_goto_dest (stmt
), 0);
220 target_block
= label_to_block (label
);
221 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
223 if (e
->dest
!= target_block
)
224 remove_edge_and_dominated_blocks (e
);
227 /* Turn off the EDGE_ABNORMAL flag. */
228 e
->flags
&= ~EDGE_ABNORMAL
;
230 /* And set EDGE_FALLTHRU. */
231 e
->flags
|= EDGE_FALLTHRU
;
236 bitmap_set_bit (cfgcleanup_altered_bbs
, bb
->index
);
237 bitmap_set_bit (cfgcleanup_altered_bbs
, target_block
->index
);
239 /* Remove the GOTO_EXPR as it is not needed. The CFG has all the
240 relevant information we need. */
241 gsi_remove (&gsi
, true);
245 /* Check for indirect calls that have been turned into
247 else if (is_gimple_call (stmt
)
248 && gimple_call_noreturn_p (stmt
)
249 && remove_fallthru_edge (bb
->succs
))
255 /* Return true if basic block BB does nothing except pass control
256 flow to another block and that we can safely insert a label at
257 the start of the successor block.
259 As a precondition, we require that BB be not equal to
263 tree_forwarder_block_p (basic_block bb
, bool phi_wanted
)
265 gimple_stmt_iterator gsi
;
268 /* BB must have a single outgoing edge. */
269 if (single_succ_p (bb
) != 1
270 /* If PHI_WANTED is false, BB must not have any PHI nodes.
271 Otherwise, BB must have PHI nodes. */
272 || gimple_seq_empty_p (phi_nodes (bb
)) == phi_wanted
273 /* BB may not be a predecessor of EXIT_BLOCK_PTR. */
274 || single_succ (bb
) == EXIT_BLOCK_PTR
275 /* Nor should this be an infinite loop. */
276 || single_succ (bb
) == bb
277 /* BB may not have an abnormal outgoing edge. */
278 || (single_succ_edge (bb
)->flags
& EDGE_ABNORMAL
))
282 gcc_assert (bb
!= ENTRY_BLOCK_PTR
);
285 locus
= single_succ_edge (bb
)->goto_locus
;
287 /* There should not be an edge coming from entry, or an EH edge. */
292 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
293 if (e
->src
== ENTRY_BLOCK_PTR
|| (e
->flags
& EDGE_EH
))
295 /* If goto_locus of any of the edges differs, prevent removing
296 the forwarder block for -O0. */
297 else if (optimize
== 0 && e
->goto_locus
!= locus
)
301 /* Now walk through the statements backward. We can ignore labels,
302 anything else means this is not a forwarder block. */
303 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
305 gimple stmt
= gsi_stmt (gsi
);
307 switch (gimple_code (stmt
))
310 if (DECL_NONLOCAL (gimple_label_label (stmt
)))
312 if (optimize
== 0 && gimple_location (stmt
) != locus
)
316 /* ??? For now, hope there's a corresponding debug
317 assignment at the destination. */
329 /* Protect loop latches, headers and preheaders. */
330 if (bb
->loop_father
->header
== bb
)
332 dest
= EDGE_SUCC (bb
, 0)->dest
;
334 if (dest
->loop_father
->header
== dest
)
340 /* Return true if BB has at least one abnormal incoming edge. */
343 has_abnormal_incoming_edge_p (basic_block bb
)
348 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
349 if (e
->flags
& EDGE_ABNORMAL
)
355 /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
356 those alternatives are equal in each of the PHI nodes, then return
357 true, else return false. */
360 phi_alternatives_equal (basic_block dest
, edge e1
, edge e2
)
362 int n1
= e1
->dest_idx
;
363 int n2
= e2
->dest_idx
;
364 gimple_stmt_iterator gsi
;
366 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
368 gimple phi
= gsi_stmt (gsi
);
369 tree val1
= gimple_phi_arg_def (phi
, n1
);
370 tree val2
= gimple_phi_arg_def (phi
, n2
);
372 gcc_assert (val1
!= NULL_TREE
);
373 gcc_assert (val2
!= NULL_TREE
);
375 if (!operand_equal_for_phi_arg_p (val1
, val2
))
382 /* Removes forwarder block BB. Returns false if this failed. */
385 remove_forwarder_block (basic_block bb
)
387 edge succ
= single_succ_edge (bb
), e
, s
;
388 basic_block dest
= succ
->dest
;
391 gimple_stmt_iterator gsi
, gsi_to
;
392 bool can_move_debug_stmts
;
394 /* We check for infinite loops already in tree_forwarder_block_p.
395 However it may happen that the infinite loop is created
396 afterwards due to removal of forwarders. */
400 /* If the destination block consists of a nonlocal label or is a
401 EH landing pad, do not merge it. */
402 label
= first_stmt (dest
);
404 && gimple_code (label
) == GIMPLE_LABEL
405 && (DECL_NONLOCAL (gimple_label_label (label
))
406 || EH_LANDING_PAD_NR (gimple_label_label (label
)) != 0))
409 /* If there is an abnormal edge to basic block BB, but not into
410 dest, problems might occur during removal of the phi node at out
411 of ssa due to overlapping live ranges of registers.
413 If there is an abnormal edge in DEST, the problems would occur
414 anyway since cleanup_dead_labels would then merge the labels for
415 two different eh regions, and rest of exception handling code
418 So if there is an abnormal edge to BB, proceed only if there is
419 no abnormal edge to DEST and there are no phi nodes in DEST. */
420 if (has_abnormal_incoming_edge_p (bb
)
421 && (has_abnormal_incoming_edge_p (dest
)
422 || !gimple_seq_empty_p (phi_nodes (dest
))))
425 /* If there are phi nodes in DEST, and some of the blocks that are
426 predecessors of BB are also predecessors of DEST, check that the
427 phi node arguments match. */
428 if (!gimple_seq_empty_p (phi_nodes (dest
)))
430 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
432 s
= find_edge (e
->src
, dest
);
436 if (!phi_alternatives_equal (dest
, succ
, s
))
441 can_move_debug_stmts
= single_pred_p (dest
);
443 /* Redirect the edges. */
444 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
446 bitmap_set_bit (cfgcleanup_altered_bbs
, e
->src
->index
);
448 if (e
->flags
& EDGE_ABNORMAL
)
450 /* If there is an abnormal edge, redirect it anyway, and
451 move the labels to the new block to make it legal. */
452 s
= redirect_edge_succ_nodup (e
, dest
);
455 s
= redirect_edge_and_branch (e
, dest
);
459 /* Create arguments for the phi nodes, since the edge was not
461 for (gsi
= gsi_start_phis (dest
);
465 gimple phi
= gsi_stmt (gsi
);
466 source_location l
= gimple_phi_arg_location_from_edge (phi
, succ
);
467 add_phi_arg (phi
, gimple_phi_arg_def (phi
, succ
->dest_idx
), s
, l
);
472 /* Move nonlocal labels and computed goto targets as well as user
473 defined labels and labels with an EH landing pad number to the
474 new block, so that the redirection of the abnormal edges works,
475 jump targets end up in a sane place and debug information for
476 labels is retained. */
477 gsi_to
= gsi_start_bb (dest
);
478 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
481 label
= gsi_stmt (gsi
);
482 if (is_gimple_debug (label
))
484 decl
= gimple_label_label (label
);
485 if (EH_LANDING_PAD_NR (decl
) != 0
486 || DECL_NONLOCAL (decl
)
487 || FORCED_LABEL (decl
)
488 || !DECL_ARTIFICIAL (decl
))
490 gsi_remove (&gsi
, false);
491 gsi_insert_before (&gsi_to
, label
, GSI_SAME_STMT
);
497 /* Move debug statements if the destination has just a single
499 if (can_move_debug_stmts
)
501 gsi_to
= gsi_after_labels (dest
);
502 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); )
504 gimple debug
= gsi_stmt (gsi
);
505 if (!is_gimple_debug (debug
))
507 gsi_remove (&gsi
, false);
508 gsi_insert_before (&gsi_to
, debug
, GSI_SAME_STMT
);
512 bitmap_set_bit (cfgcleanup_altered_bbs
, dest
->index
);
514 /* Update the dominators. */
515 if (dom_info_available_p (CDI_DOMINATORS
))
517 basic_block dom
, dombb
, domdest
;
519 dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
520 domdest
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
523 /* Shortcut to avoid calling (relatively expensive)
524 nearest_common_dominator unless necessary. */
528 dom
= nearest_common_dominator (CDI_DOMINATORS
, domdest
, dombb
);
530 set_immediate_dominator (CDI_DOMINATORS
, dest
, dom
);
533 /* And kill the forwarder block. */
534 delete_basic_block (bb
);
539 /* STMT is a call that has been discovered noreturn. Fixup the CFG
540 and remove LHS. Return true if something changed. */
543 fixup_noreturn_call (gimple stmt
)
545 basic_block bb
= gimple_bb (stmt
);
546 bool changed
= false;
548 if (gimple_call_builtin_p (stmt
, BUILT_IN_RETURN
))
551 /* First split basic block if stmt is not last. */
552 if (stmt
!= gsi_stmt (gsi_last_bb (bb
)))
553 split_block (bb
, stmt
);
555 changed
|= remove_fallthru_edge (bb
->succs
);
557 /* If there is LHS, remove it. */
558 if (gimple_call_lhs (stmt
))
560 tree op
= gimple_call_lhs (stmt
);
561 gimple_call_set_lhs (stmt
, NULL_TREE
);
563 /* We need to remove SSA name to avoid checking errors.
564 All uses are dominated by the noreturn and thus will
565 be removed afterwards.
566 We proactively remove affected non-PHI statements to avoid
567 fixup_cfg from trying to update them and crashing. */
568 if (TREE_CODE (op
) == SSA_NAME
)
571 imm_use_iterator iter
;
574 unsigned int bb_index
;
576 bitmap blocks
= BITMAP_ALLOC (NULL
);
578 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, op
)
580 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
581 bitmap_set_bit (blocks
, gimple_bb (use_stmt
)->index
);
583 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
584 SET_USE (use_p
, error_mark_node
);
586 EXECUTE_IF_SET_IN_BITMAP (blocks
, 0, bb_index
, bi
)
587 delete_basic_block (BASIC_BLOCK (bb_index
));
588 BITMAP_FREE (blocks
);
589 release_ssa_name (op
);
594 /* Similarly remove VDEF if there is any. */
595 else if (gimple_vdef (stmt
))
601 /* Split basic blocks on calls in the middle of a basic block that are now
602 known not to return, and remove the unreachable code. */
605 split_bbs_on_noreturn_calls (void)
607 bool changed
= false;
611 /* Detect cases where a mid-block call is now known not to return. */
613 while (VEC_length (gimple
, MODIFIED_NORETURN_CALLS (cfun
)))
615 stmt
= VEC_pop (gimple
, MODIFIED_NORETURN_CALLS (cfun
));
616 bb
= gimple_bb (stmt
);
617 /* BB might be deleted at this point, so verify first
618 BB is present in the cfg. */
620 || bb
->index
< NUM_FIXED_BLOCKS
621 || bb
->index
>= n_basic_blocks
622 || BASIC_BLOCK (bb
->index
) != bb
623 || !gimple_call_noreturn_p (stmt
))
626 changed
|= fixup_noreturn_call (stmt
);
632 /* If GIMPLE_OMP_RETURN in basic block BB is unreachable, remove it. */
635 cleanup_omp_return (basic_block bb
)
637 gimple stmt
= last_stmt (bb
);
638 basic_block control_bb
;
641 || gimple_code (stmt
) != GIMPLE_OMP_RETURN
642 || !single_pred_p (bb
))
645 control_bb
= single_pred (bb
);
646 stmt
= last_stmt (control_bb
);
648 if (stmt
== NULL
|| gimple_code (stmt
) != GIMPLE_OMP_SECTIONS_SWITCH
)
651 /* The block with the control statement normally has two entry edges -- one
652 from entry, one from continue. If continue is removed, return is
653 unreachable, so we remove it here as well. */
654 if (EDGE_COUNT (control_bb
->preds
) == 2)
657 gcc_assert (EDGE_COUNT (control_bb
->preds
) == 1);
658 remove_edge_and_dominated_blocks (single_pred_edge (bb
));
662 /* Tries to cleanup cfg in basic block BB. Returns true if anything
666 cleanup_tree_cfg_bb (basic_block bb
)
670 if (cleanup_omp_return (bb
))
673 retval
= cleanup_control_flow_bb (bb
);
675 if (tree_forwarder_block_p (bb
, false)
676 && remove_forwarder_block (bb
))
679 /* Merging the blocks may create new opportunities for folding
680 conditional branches (due to the elimination of single-valued PHI
682 if (single_succ_p (bb
)
683 && can_merge_blocks_p (bb
, single_succ (bb
)))
685 merge_blocks (bb
, single_succ (bb
));
692 /* Iterate the cfg cleanups, while anything changes. */
695 cleanup_tree_cfg_1 (void)
701 retval
|= split_bbs_on_noreturn_calls ();
703 /* Prepare the worklists of altered blocks. */
704 cfgcleanup_altered_bbs
= BITMAP_ALLOC (NULL
);
706 /* During forwarder block cleanup, we may redirect edges out of
707 SWITCH_EXPRs, which can get expensive. So we want to enable
708 recording of edge to CASE_LABEL_EXPR. */
709 start_recording_case_labels ();
711 /* Start by iterating over all basic blocks. We cannot use FOR_EACH_BB,
712 since the basic blocks may get removed. */
713 n
= last_basic_block
;
714 for (i
= NUM_FIXED_BLOCKS
; i
< n
; i
++)
716 bb
= BASIC_BLOCK (i
);
718 retval
|= cleanup_tree_cfg_bb (bb
);
721 /* Now process the altered blocks, as long as any are available. */
722 while (!bitmap_empty_p (cfgcleanup_altered_bbs
))
724 i
= bitmap_first_set_bit (cfgcleanup_altered_bbs
);
725 bitmap_clear_bit (cfgcleanup_altered_bbs
, i
);
726 if (i
< NUM_FIXED_BLOCKS
)
729 bb
= BASIC_BLOCK (i
);
733 retval
|= cleanup_tree_cfg_bb (bb
);
735 /* Rerun split_bbs_on_noreturn_calls, in case we have altered any noreturn
737 retval
|= split_bbs_on_noreturn_calls ();
740 end_recording_case_labels ();
741 BITMAP_FREE (cfgcleanup_altered_bbs
);
746 /* Remove unreachable blocks and other miscellaneous clean up work.
747 Return true if the flowgraph was modified, false otherwise. */
750 cleanup_tree_cfg_noloop (void)
754 timevar_push (TV_TREE_CLEANUP_CFG
);
756 /* Iterate until there are no more cleanups left to do. If any
757 iteration changed the flowgraph, set CHANGED to true.
759 If dominance information is available, there cannot be any unreachable
761 if (!dom_info_available_p (CDI_DOMINATORS
))
763 changed
= delete_unreachable_blocks ();
764 calculate_dominance_info (CDI_DOMINATORS
);
768 #ifdef ENABLE_CHECKING
769 verify_dominators (CDI_DOMINATORS
);
774 changed
|= cleanup_tree_cfg_1 ();
776 gcc_assert (dom_info_available_p (CDI_DOMINATORS
));
779 #ifdef ENABLE_CHECKING
783 timevar_pop (TV_TREE_CLEANUP_CFG
);
785 if (changed
&& current_loops
)
786 loops_state_set (LOOPS_NEED_FIXUP
);
791 /* Repairs loop structures. */
794 repair_loop_structures (void)
796 bitmap changed_bbs
= BITMAP_ALLOC (NULL
);
797 fix_loop_structure (changed_bbs
);
799 /* This usually does nothing. But sometimes parts of cfg that originally
800 were inside a loop get out of it due to edge removal (since they
801 become unreachable by back edges from latch). */
802 if (loops_state_satisfies_p (LOOP_CLOSED_SSA
))
803 rewrite_into_loop_closed_ssa (changed_bbs
, TODO_update_ssa
);
805 BITMAP_FREE (changed_bbs
);
807 #ifdef ENABLE_CHECKING
808 verify_loop_structure ();
812 loops_state_clear (LOOPS_NEED_FIXUP
);
815 /* Cleanup cfg and repair loop structures. */
818 cleanup_tree_cfg (void)
820 bool changed
= cleanup_tree_cfg_noloop ();
822 if (current_loops
!= NULL
823 && loops_state_satisfies_p (LOOPS_NEED_FIXUP
))
824 repair_loop_structures ();
829 /* Merge the PHI nodes at BB into those at BB's sole successor. */
832 remove_forwarder_block_with_phi (basic_block bb
)
834 edge succ
= single_succ_edge (bb
);
835 basic_block dest
= succ
->dest
;
837 basic_block dombb
, domdest
, dom
;
839 /* We check for infinite loops already in tree_forwarder_block_p.
840 However it may happen that the infinite loop is created
841 afterwards due to removal of forwarders. */
845 /* If the destination block consists of a nonlocal label, do not
847 label
= first_stmt (dest
);
849 && gimple_code (label
) == GIMPLE_LABEL
850 && DECL_NONLOCAL (gimple_label_label (label
)))
853 /* Redirect each incoming edge to BB to DEST. */
854 while (EDGE_COUNT (bb
->preds
) > 0)
856 edge e
= EDGE_PRED (bb
, 0), s
;
857 gimple_stmt_iterator gsi
;
859 s
= find_edge (e
->src
, dest
);
862 /* We already have an edge S from E->src to DEST. If S and
863 E->dest's sole successor edge have the same PHI arguments
864 at DEST, redirect S to DEST. */
865 if (phi_alternatives_equal (dest
, s
, succ
))
867 e
= redirect_edge_and_branch (e
, dest
);
868 redirect_edge_var_map_clear (e
);
872 /* PHI arguments are different. Create a forwarder block by
873 splitting E so that we can merge PHI arguments on E to
875 e
= single_succ_edge (split_edge (e
));
878 s
= redirect_edge_and_branch (e
, dest
);
880 /* redirect_edge_and_branch must not create a new edge. */
883 /* Add to the PHI nodes at DEST each PHI argument removed at the
885 for (gsi
= gsi_start_phis (dest
);
889 gimple phi
= gsi_stmt (gsi
);
890 tree def
= gimple_phi_arg_def (phi
, succ
->dest_idx
);
891 source_location locus
= gimple_phi_arg_location_from_edge (phi
, succ
);
893 if (TREE_CODE (def
) == SSA_NAME
)
895 edge_var_map_vector head
;
899 /* If DEF is one of the results of PHI nodes removed during
900 redirection, replace it with the PHI argument that used
902 head
= redirect_edge_var_map_vector (e
);
903 for (i
= 0; VEC_iterate (edge_var_map
, head
, i
, vm
); ++i
)
905 tree old_arg
= redirect_edge_var_map_result (vm
);
906 tree new_arg
= redirect_edge_var_map_def (vm
);
911 locus
= redirect_edge_var_map_location (vm
);
917 add_phi_arg (phi
, def
, s
, locus
);
920 redirect_edge_var_map_clear (e
);
923 /* Update the dominators. */
924 dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
925 domdest
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
928 /* Shortcut to avoid calling (relatively expensive)
929 nearest_common_dominator unless necessary. */
933 dom
= nearest_common_dominator (CDI_DOMINATORS
, domdest
, dombb
);
935 set_immediate_dominator (CDI_DOMINATORS
, dest
, dom
);
937 /* Remove BB since all of BB's incoming edges have been redirected
939 delete_basic_block (bb
);
942 /* This pass merges PHI nodes if one feeds into another. For example,
943 suppose we have the following:
950 # tem_6 = PHI <tem_17(8), tem_23(7)>;
953 # tem_3 = PHI <tem_6(9), tem_2(5)>;
956 Then we merge the first PHI node into the second one like so:
963 # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
968 merge_phi_nodes (void)
970 basic_block
*worklist
= XNEWVEC (basic_block
, n_basic_blocks
);
971 basic_block
*current
= worklist
;
974 calculate_dominance_info (CDI_DOMINATORS
);
976 /* Find all PHI nodes that we may be able to merge. */
981 /* Look for a forwarder block with PHI nodes. */
982 if (!tree_forwarder_block_p (bb
, true))
985 dest
= single_succ (bb
);
987 /* We have to feed into another basic block with PHI
989 if (gimple_seq_empty_p (phi_nodes (dest
))
990 /* We don't want to deal with a basic block with
992 || has_abnormal_incoming_edge_p (bb
))
995 if (!dominated_by_p (CDI_DOMINATORS
, dest
, bb
))
997 /* If BB does not dominate DEST, then the PHI nodes at
998 DEST must be the only users of the results of the PHI
1004 gimple_stmt_iterator gsi
;
1005 unsigned int dest_idx
= single_succ_edge (bb
)->dest_idx
;
1007 /* BB dominates DEST. There may be many users of the PHI
1008 nodes in BB. However, there is still a trivial case we
1009 can handle. If the result of every PHI in BB is used
1010 only by a PHI in DEST, then we can trivially merge the
1011 PHI nodes from BB into DEST. */
1012 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
1015 gimple phi
= gsi_stmt (gsi
);
1016 tree result
= gimple_phi_result (phi
);
1017 use_operand_p imm_use
;
1020 /* If the PHI's result is never used, then we can just
1022 if (has_zero_uses (result
))
1025 /* Get the single use of the result of this PHI node. */
1026 if (!single_imm_use (result
, &imm_use
, &use_stmt
)
1027 || gimple_code (use_stmt
) != GIMPLE_PHI
1028 || gimple_bb (use_stmt
) != dest
1029 || gimple_phi_arg_def (use_stmt
, dest_idx
) != result
)
1033 /* If the loop above iterated through all the PHI nodes
1034 in BB, then we can merge the PHIs from BB into DEST. */
1035 if (gsi_end_p (gsi
))
1040 /* Now let's drain WORKLIST. */
1041 while (current
!= worklist
)
1044 remove_forwarder_block_with_phi (bb
);
1052 gate_merge_phi (void)
1057 struct gimple_opt_pass pass_merge_phi
=
1061 "mergephi", /* name */
1062 gate_merge_phi
, /* gate */
1063 merge_phi_nodes
, /* execute */
1066 0, /* static_pass_number */
1067 TV_TREE_MERGE_PHI
, /* tv_id */
1068 PROP_cfg
| PROP_ssa
, /* properties_required */
1069 0, /* properties_provided */
1070 0, /* properties_destroyed */
1071 0, /* todo_flags_start */
1072 TODO_dump_func
| TODO_ggc_collect
/* todo_flags_finish */