1 /* CFG cleanup for trees.
2 Copyright (C) 2001-2013 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3, or (at your option)
11 GCC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
26 #include "basic-block.h"
27 #include "diagnostic-core.h"
31 #include "langhooks.h"
34 #include "gimple-iterator.h"
35 #include "gimple-ssa.h"
37 #include "tree-phinodes.h"
38 #include "ssa-iterators.h"
39 #include "stringpool.h"
40 #include "tree-ssanames.h"
41 #include "tree-ssa-loop-manip.h"
45 #include "tree-pass.h"
49 #include "tree-ssa-propagate.h"
50 #include "tree-scalar-evolution.h"
52 /* The set of blocks in that at least one of the following changes happened:
53 -- the statement at the end of the block was changed
54 -- the block was newly created
55 -- the set of the predecessors of the block changed
56 -- the set of the successors of the block changed
57 ??? Maybe we could track these changes separately, since they determine
58 what cleanups it makes sense to try on the block. */
59 bitmap cfgcleanup_altered_bbs
;
61 /* Remove any fallthru edge from EV. Return true if an edge was removed. */
64 remove_fallthru_edge (vec
<edge
, va_gc
> *ev
)
69 FOR_EACH_EDGE (e
, ei
, ev
)
70 if ((e
->flags
& EDGE_FALLTHRU
) != 0)
72 if (e
->flags
& EDGE_COMPLEX
)
73 e
->flags
&= ~EDGE_FALLTHRU
;
75 remove_edge_and_dominated_blocks (e
);
82 /* Disconnect an unreachable block in the control expression starting
86 cleanup_control_expr_graph (basic_block bb
, gimple_stmt_iterator gsi
)
90 gimple stmt
= gsi_stmt (gsi
);
93 if (!single_succ_p (bb
))
100 fold_defer_overflow_warnings ();
101 loc
= gimple_location (stmt
);
102 switch (gimple_code (stmt
))
105 val
= fold_binary_loc (loc
, gimple_cond_code (stmt
),
107 gimple_cond_lhs (stmt
),
108 gimple_cond_rhs (stmt
));
112 val
= gimple_switch_index (stmt
);
118 taken_edge
= find_taken_edge (bb
, val
);
121 fold_undefer_and_ignore_overflow_warnings ();
125 /* Remove all the edges except the one that is always executed. */
127 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
133 fold_undefer_overflow_warnings
134 (true, stmt
, WARN_STRICT_OVERFLOW_CONDITIONAL
);
138 taken_edge
->probability
+= e
->probability
;
139 taken_edge
->count
+= e
->count
;
140 remove_edge_and_dominated_blocks (e
);
147 fold_undefer_and_ignore_overflow_warnings ();
148 if (taken_edge
->probability
> REG_BR_PROB_BASE
)
149 taken_edge
->probability
= REG_BR_PROB_BASE
;
152 taken_edge
= single_succ_edge (bb
);
154 bitmap_set_bit (cfgcleanup_altered_bbs
, bb
->index
);
155 gsi_remove (&gsi
, true);
156 taken_edge
->flags
= EDGE_FALLTHRU
;
161 /* Try to remove superfluous control structures in basic block BB. Returns
162 true if anything changes. */
165 cleanup_control_flow_bb (basic_block bb
)
167 gimple_stmt_iterator gsi
;
171 /* If the last statement of the block could throw and now cannot,
172 we need to prune cfg. */
173 retval
|= gimple_purge_dead_eh_edges (bb
);
175 gsi
= gsi_last_bb (bb
);
179 stmt
= gsi_stmt (gsi
);
181 if (gimple_code (stmt
) == GIMPLE_COND
182 || gimple_code (stmt
) == GIMPLE_SWITCH
)
183 retval
|= cleanup_control_expr_graph (bb
, gsi
);
184 else if (gimple_code (stmt
) == GIMPLE_GOTO
185 && TREE_CODE (gimple_goto_dest (stmt
)) == ADDR_EXPR
186 && (TREE_CODE (TREE_OPERAND (gimple_goto_dest (stmt
), 0))
189 /* If we had a computed goto which has a compile-time determinable
190 destination, then we can eliminate the goto. */
194 basic_block target_block
;
196 /* First look at all the outgoing edges. Delete any outgoing
197 edges which do not go to the right block. For the one
198 edge which goes to the right block, fix up its flags. */
199 label
= TREE_OPERAND (gimple_goto_dest (stmt
), 0);
200 target_block
= label_to_block (label
);
201 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
203 if (e
->dest
!= target_block
)
204 remove_edge_and_dominated_blocks (e
);
207 /* Turn off the EDGE_ABNORMAL flag. */
208 e
->flags
&= ~EDGE_ABNORMAL
;
210 /* And set EDGE_FALLTHRU. */
211 e
->flags
|= EDGE_FALLTHRU
;
216 bitmap_set_bit (cfgcleanup_altered_bbs
, bb
->index
);
217 bitmap_set_bit (cfgcleanup_altered_bbs
, target_block
->index
);
219 /* Remove the GOTO_EXPR as it is not needed. The CFG has all the
220 relevant information we need. */
221 gsi_remove (&gsi
, true);
225 /* Check for indirect calls that have been turned into
227 else if (is_gimple_call (stmt
)
228 && gimple_call_noreturn_p (stmt
)
229 && remove_fallthru_edge (bb
->succs
))
235 /* Return true if basic block BB does nothing except pass control
236 flow to another block and that we can safely insert a label at
237 the start of the successor block.
239 As a precondition, we require that BB be not equal to
243 tree_forwarder_block_p (basic_block bb
, bool phi_wanted
)
245 gimple_stmt_iterator gsi
;
248 /* BB must have a single outgoing edge. */
249 if (single_succ_p (bb
) != 1
250 /* If PHI_WANTED is false, BB must not have any PHI nodes.
251 Otherwise, BB must have PHI nodes. */
252 || gimple_seq_empty_p (phi_nodes (bb
)) == phi_wanted
253 /* BB may not be a predecessor of EXIT_BLOCK_PTR. */
254 || single_succ (bb
) == EXIT_BLOCK_PTR
255 /* Nor should this be an infinite loop. */
256 || single_succ (bb
) == bb
257 /* BB may not have an abnormal outgoing edge. */
258 || (single_succ_edge (bb
)->flags
& EDGE_ABNORMAL
))
261 gcc_checking_assert (bb
!= ENTRY_BLOCK_PTR
);
263 locus
= single_succ_edge (bb
)->goto_locus
;
265 /* There should not be an edge coming from entry, or an EH edge. */
270 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
271 if (e
->src
== ENTRY_BLOCK_PTR
|| (e
->flags
& EDGE_EH
))
273 /* If goto_locus of any of the edges differs, prevent removing
274 the forwarder block for -O0. */
275 else if (optimize
== 0 && e
->goto_locus
!= locus
)
279 /* Now walk through the statements backward. We can ignore labels,
280 anything else means this is not a forwarder block. */
281 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
283 gimple stmt
= gsi_stmt (gsi
);
285 switch (gimple_code (stmt
))
288 if (DECL_NONLOCAL (gimple_label_label (stmt
)))
290 if (optimize
== 0 && gimple_location (stmt
) != locus
)
294 /* ??? For now, hope there's a corresponding debug
295 assignment at the destination. */
307 /* Protect loop latches, headers and preheaders. */
308 if (bb
->loop_father
->header
== bb
)
310 dest
= EDGE_SUCC (bb
, 0)->dest
;
312 if (dest
->loop_father
->header
== dest
)
318 /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
319 those alternatives are equal in each of the PHI nodes, then return
320 true, else return false. */
323 phi_alternatives_equal (basic_block dest
, edge e1
, edge e2
)
325 int n1
= e1
->dest_idx
;
326 int n2
= e2
->dest_idx
;
327 gimple_stmt_iterator gsi
;
329 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
331 gimple phi
= gsi_stmt (gsi
);
332 tree val1
= gimple_phi_arg_def (phi
, n1
);
333 tree val2
= gimple_phi_arg_def (phi
, n2
);
335 gcc_assert (val1
!= NULL_TREE
);
336 gcc_assert (val2
!= NULL_TREE
);
338 if (!operand_equal_for_phi_arg_p (val1
, val2
))
345 /* Removes forwarder block BB. Returns false if this failed. */
348 remove_forwarder_block (basic_block bb
)
350 edge succ
= single_succ_edge (bb
), e
, s
;
351 basic_block dest
= succ
->dest
;
354 gimple_stmt_iterator gsi
, gsi_to
;
355 bool can_move_debug_stmts
;
357 /* We check for infinite loops already in tree_forwarder_block_p.
358 However it may happen that the infinite loop is created
359 afterwards due to removal of forwarders. */
363 /* If the destination block consists of a nonlocal label or is a
364 EH landing pad, do not merge it. */
365 label
= first_stmt (dest
);
367 && gimple_code (label
) == GIMPLE_LABEL
368 && (DECL_NONLOCAL (gimple_label_label (label
))
369 || EH_LANDING_PAD_NR (gimple_label_label (label
)) != 0))
372 /* If there is an abnormal edge to basic block BB, but not into
373 dest, problems might occur during removal of the phi node at out
374 of ssa due to overlapping live ranges of registers.
376 If there is an abnormal edge in DEST, the problems would occur
377 anyway since cleanup_dead_labels would then merge the labels for
378 two different eh regions, and rest of exception handling code
381 So if there is an abnormal edge to BB, proceed only if there is
382 no abnormal edge to DEST and there are no phi nodes in DEST. */
383 if (bb_has_abnormal_pred (bb
)
384 && (bb_has_abnormal_pred (dest
)
385 || !gimple_seq_empty_p (phi_nodes (dest
))))
388 /* If there are phi nodes in DEST, and some of the blocks that are
389 predecessors of BB are also predecessors of DEST, check that the
390 phi node arguments match. */
391 if (!gimple_seq_empty_p (phi_nodes (dest
)))
393 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
395 s
= find_edge (e
->src
, dest
);
399 if (!phi_alternatives_equal (dest
, succ
, s
))
404 can_move_debug_stmts
= MAY_HAVE_DEBUG_STMTS
&& single_pred_p (dest
);
406 /* Redirect the edges. */
407 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
409 bitmap_set_bit (cfgcleanup_altered_bbs
, e
->src
->index
);
411 if (e
->flags
& EDGE_ABNORMAL
)
413 /* If there is an abnormal edge, redirect it anyway, and
414 move the labels to the new block to make it legal. */
415 s
= redirect_edge_succ_nodup (e
, dest
);
418 s
= redirect_edge_and_branch (e
, dest
);
422 /* Create arguments for the phi nodes, since the edge was not
424 for (gsi
= gsi_start_phis (dest
);
428 gimple phi
= gsi_stmt (gsi
);
429 source_location l
= gimple_phi_arg_location_from_edge (phi
, succ
);
430 tree def
= gimple_phi_arg_def (phi
, succ
->dest_idx
);
431 add_phi_arg (phi
, unshare_expr (def
), s
, l
);
436 /* Move nonlocal labels and computed goto targets as well as user
437 defined labels and labels with an EH landing pad number to the
438 new block, so that the redirection of the abnormal edges works,
439 jump targets end up in a sane place and debug information for
440 labels is retained. */
441 gsi_to
= gsi_start_bb (dest
);
442 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
445 label
= gsi_stmt (gsi
);
446 if (is_gimple_debug (label
))
448 decl
= gimple_label_label (label
);
449 if (EH_LANDING_PAD_NR (decl
) != 0
450 || DECL_NONLOCAL (decl
)
451 || FORCED_LABEL (decl
)
452 || !DECL_ARTIFICIAL (decl
))
454 gsi_remove (&gsi
, false);
455 gsi_insert_before (&gsi_to
, label
, GSI_SAME_STMT
);
461 /* Move debug statements if the destination has a single predecessor. */
462 if (can_move_debug_stmts
)
464 gsi_to
= gsi_after_labels (dest
);
465 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); )
467 gimple debug
= gsi_stmt (gsi
);
468 if (!is_gimple_debug (debug
))
470 gsi_remove (&gsi
, false);
471 gsi_insert_before (&gsi_to
, debug
, GSI_SAME_STMT
);
475 bitmap_set_bit (cfgcleanup_altered_bbs
, dest
->index
);
477 /* Update the dominators. */
478 if (dom_info_available_p (CDI_DOMINATORS
))
480 basic_block dom
, dombb
, domdest
;
482 dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
483 domdest
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
486 /* Shortcut to avoid calling (relatively expensive)
487 nearest_common_dominator unless necessary. */
491 dom
= nearest_common_dominator (CDI_DOMINATORS
, domdest
, dombb
);
493 set_immediate_dominator (CDI_DOMINATORS
, dest
, dom
);
496 /* And kill the forwarder block. */
497 delete_basic_block (bb
);
502 /* STMT is a call that has been discovered noreturn. Fixup the CFG
503 and remove LHS. Return true if something changed. */
506 fixup_noreturn_call (gimple stmt
)
508 basic_block bb
= gimple_bb (stmt
);
509 bool changed
= false;
511 if (gimple_call_builtin_p (stmt
, BUILT_IN_RETURN
))
514 /* First split basic block if stmt is not last. */
515 if (stmt
!= gsi_stmt (gsi_last_bb (bb
)))
516 split_block (bb
, stmt
);
518 changed
|= remove_fallthru_edge (bb
->succs
);
520 /* If there is LHS, remove it. */
521 if (gimple_call_lhs (stmt
))
523 tree op
= gimple_call_lhs (stmt
);
524 gimple_call_set_lhs (stmt
, NULL_TREE
);
526 /* We need to remove SSA name to avoid checking errors.
527 All uses are dominated by the noreturn and thus will
528 be removed afterwards.
529 We proactively remove affected non-PHI statements to avoid
530 fixup_cfg from trying to update them and crashing. */
531 if (TREE_CODE (op
) == SSA_NAME
)
534 imm_use_iterator iter
;
537 unsigned int bb_index
;
539 bitmap blocks
= BITMAP_ALLOC (NULL
);
541 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, op
)
543 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
544 bitmap_set_bit (blocks
, gimple_bb (use_stmt
)->index
);
546 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
547 SET_USE (use_p
, error_mark_node
);
549 EXECUTE_IF_SET_IN_BITMAP (blocks
, 0, bb_index
, bi
)
550 delete_basic_block (BASIC_BLOCK (bb_index
));
551 BITMAP_FREE (blocks
);
552 release_ssa_name (op
);
557 /* Similarly remove VDEF if there is any. */
558 else if (gimple_vdef (stmt
))
564 /* Split basic blocks on calls in the middle of a basic block that are now
565 known not to return, and remove the unreachable code. */
568 split_bbs_on_noreturn_calls (void)
570 bool changed
= false;
574 /* Detect cases where a mid-block call is now known not to return. */
576 while (vec_safe_length (MODIFIED_NORETURN_CALLS (cfun
)))
578 stmt
= MODIFIED_NORETURN_CALLS (cfun
)->pop ();
579 bb
= gimple_bb (stmt
);
580 /* BB might be deleted at this point, so verify first
581 BB is present in the cfg. */
583 || bb
->index
< NUM_FIXED_BLOCKS
584 || bb
->index
>= last_basic_block
585 || BASIC_BLOCK (bb
->index
) != bb
586 || !gimple_call_noreturn_p (stmt
))
589 changed
|= fixup_noreturn_call (stmt
);
595 /* Tries to cleanup cfg in basic block BB. Returns true if anything
599 cleanup_tree_cfg_bb (basic_block bb
)
601 bool retval
= cleanup_control_flow_bb (bb
);
603 if (tree_forwarder_block_p (bb
, false)
604 && remove_forwarder_block (bb
))
607 /* Merging the blocks may create new opportunities for folding
608 conditional branches (due to the elimination of single-valued PHI
610 if (single_succ_p (bb
)
611 && can_merge_blocks_p (bb
, single_succ (bb
)))
613 merge_blocks (bb
, single_succ (bb
));
620 /* Iterate the cfg cleanups, while anything changes. */
623 cleanup_tree_cfg_1 (void)
629 retval
|= split_bbs_on_noreturn_calls ();
631 /* Prepare the worklists of altered blocks. */
632 cfgcleanup_altered_bbs
= BITMAP_ALLOC (NULL
);
634 /* During forwarder block cleanup, we may redirect edges out of
635 SWITCH_EXPRs, which can get expensive. So we want to enable
636 recording of edge to CASE_LABEL_EXPR. */
637 start_recording_case_labels ();
639 /* Start by iterating over all basic blocks. We cannot use FOR_EACH_BB,
640 since the basic blocks may get removed. */
641 n
= last_basic_block
;
642 for (i
= NUM_FIXED_BLOCKS
; i
< n
; i
++)
644 bb
= BASIC_BLOCK (i
);
646 retval
|= cleanup_tree_cfg_bb (bb
);
649 /* Now process the altered blocks, as long as any are available. */
650 while (!bitmap_empty_p (cfgcleanup_altered_bbs
))
652 i
= bitmap_first_set_bit (cfgcleanup_altered_bbs
);
653 bitmap_clear_bit (cfgcleanup_altered_bbs
, i
);
654 if (i
< NUM_FIXED_BLOCKS
)
657 bb
= BASIC_BLOCK (i
);
661 retval
|= cleanup_tree_cfg_bb (bb
);
663 /* Rerun split_bbs_on_noreturn_calls, in case we have altered any noreturn
665 retval
|= split_bbs_on_noreturn_calls ();
668 end_recording_case_labels ();
669 BITMAP_FREE (cfgcleanup_altered_bbs
);
674 /* Remove unreachable blocks and other miscellaneous clean up work.
675 Return true if the flowgraph was modified, false otherwise. */
678 cleanup_tree_cfg_noloop (void)
682 timevar_push (TV_TREE_CLEANUP_CFG
);
684 /* Iterate until there are no more cleanups left to do. If any
685 iteration changed the flowgraph, set CHANGED to true.
687 If dominance information is available, there cannot be any unreachable
689 if (!dom_info_available_p (CDI_DOMINATORS
))
691 changed
= delete_unreachable_blocks ();
692 calculate_dominance_info (CDI_DOMINATORS
);
696 #ifdef ENABLE_CHECKING
697 verify_dominators (CDI_DOMINATORS
);
702 changed
|= cleanup_tree_cfg_1 ();
704 gcc_assert (dom_info_available_p (CDI_DOMINATORS
));
707 #ifdef ENABLE_CHECKING
711 timevar_pop (TV_TREE_CLEANUP_CFG
);
713 if (changed
&& current_loops
)
714 loops_state_set (LOOPS_NEED_FIXUP
);
719 /* Repairs loop structures. */
722 repair_loop_structures (void)
725 unsigned n_new_loops
;
727 calculate_dominance_info (CDI_DOMINATORS
);
729 timevar_push (TV_REPAIR_LOOPS
);
730 changed_bbs
= BITMAP_ALLOC (NULL
);
731 n_new_loops
= fix_loop_structure (changed_bbs
);
733 /* This usually does nothing. But sometimes parts of cfg that originally
734 were inside a loop get out of it due to edge removal (since they
735 become unreachable by back edges from latch). Also a former
736 irreducible loop can become reducible - in this case force a full
737 rewrite into loop-closed SSA form. */
738 if (loops_state_satisfies_p (LOOP_CLOSED_SSA
))
739 rewrite_into_loop_closed_ssa (n_new_loops
? NULL
: changed_bbs
,
742 BITMAP_FREE (changed_bbs
);
744 #ifdef ENABLE_CHECKING
745 verify_loop_structure ();
749 timevar_pop (TV_REPAIR_LOOPS
);
752 /* Cleanup cfg and repair loop structures. */
755 cleanup_tree_cfg (void)
757 bool changed
= cleanup_tree_cfg_noloop ();
759 if (current_loops
!= NULL
760 && loops_state_satisfies_p (LOOPS_NEED_FIXUP
))
761 repair_loop_structures ();
766 /* Tries to merge the PHI nodes at BB into those at BB's sole successor.
767 Returns true if successful. */
770 remove_forwarder_block_with_phi (basic_block bb
)
772 edge succ
= single_succ_edge (bb
);
773 basic_block dest
= succ
->dest
;
775 basic_block dombb
, domdest
, dom
;
777 /* We check for infinite loops already in tree_forwarder_block_p.
778 However it may happen that the infinite loop is created
779 afterwards due to removal of forwarders. */
783 /* If the destination block consists of a nonlocal label, do not
785 label
= first_stmt (dest
);
787 && gimple_code (label
) == GIMPLE_LABEL
788 && DECL_NONLOCAL (gimple_label_label (label
)))
791 /* Redirect each incoming edge to BB to DEST. */
792 while (EDGE_COUNT (bb
->preds
) > 0)
794 edge e
= EDGE_PRED (bb
, 0), s
;
795 gimple_stmt_iterator gsi
;
797 s
= find_edge (e
->src
, dest
);
800 /* We already have an edge S from E->src to DEST. If S and
801 E->dest's sole successor edge have the same PHI arguments
802 at DEST, redirect S to DEST. */
803 if (phi_alternatives_equal (dest
, s
, succ
))
805 e
= redirect_edge_and_branch (e
, dest
);
806 redirect_edge_var_map_clear (e
);
810 /* PHI arguments are different. Create a forwarder block by
811 splitting E so that we can merge PHI arguments on E to
813 e
= single_succ_edge (split_edge (e
));
816 s
= redirect_edge_and_branch (e
, dest
);
818 /* redirect_edge_and_branch must not create a new edge. */
821 /* Add to the PHI nodes at DEST each PHI argument removed at the
823 for (gsi
= gsi_start_phis (dest
);
827 gimple phi
= gsi_stmt (gsi
);
828 tree def
= gimple_phi_arg_def (phi
, succ
->dest_idx
);
829 source_location locus
= gimple_phi_arg_location_from_edge (phi
, succ
);
831 if (TREE_CODE (def
) == SSA_NAME
)
833 edge_var_map_vector
*head
;
837 /* If DEF is one of the results of PHI nodes removed during
838 redirection, replace it with the PHI argument that used
840 head
= redirect_edge_var_map_vector (e
);
841 FOR_EACH_VEC_SAFE_ELT (head
, i
, vm
)
843 tree old_arg
= redirect_edge_var_map_result (vm
);
844 tree new_arg
= redirect_edge_var_map_def (vm
);
849 locus
= redirect_edge_var_map_location (vm
);
855 add_phi_arg (phi
, def
, s
, locus
);
858 redirect_edge_var_map_clear (e
);
861 /* Update the dominators. */
862 dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
863 domdest
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
866 /* Shortcut to avoid calling (relatively expensive)
867 nearest_common_dominator unless necessary. */
871 dom
= nearest_common_dominator (CDI_DOMINATORS
, domdest
, dombb
);
873 set_immediate_dominator (CDI_DOMINATORS
, dest
, dom
);
875 /* Remove BB since all of BB's incoming edges have been redirected
877 delete_basic_block (bb
);
882 /* This pass merges PHI nodes if one feeds into another. For example,
883 suppose we have the following:
890 # tem_6 = PHI <tem_17(8), tem_23(7)>;
893 # tem_3 = PHI <tem_6(9), tem_2(5)>;
896 Then we merge the first PHI node into the second one like so:
903 # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
908 merge_phi_nodes (void)
910 basic_block
*worklist
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
));
911 basic_block
*current
= worklist
;
914 calculate_dominance_info (CDI_DOMINATORS
);
916 /* Find all PHI nodes that we may be able to merge. */
921 /* Look for a forwarder block with PHI nodes. */
922 if (!tree_forwarder_block_p (bb
, true))
925 dest
= single_succ (bb
);
927 /* We have to feed into another basic block with PHI
929 if (gimple_seq_empty_p (phi_nodes (dest
))
930 /* We don't want to deal with a basic block with
932 || bb_has_abnormal_pred (bb
))
935 if (!dominated_by_p (CDI_DOMINATORS
, dest
, bb
))
937 /* If BB does not dominate DEST, then the PHI nodes at
938 DEST must be the only users of the results of the PHI
944 gimple_stmt_iterator gsi
;
945 unsigned int dest_idx
= single_succ_edge (bb
)->dest_idx
;
947 /* BB dominates DEST. There may be many users of the PHI
948 nodes in BB. However, there is still a trivial case we
949 can handle. If the result of every PHI in BB is used
950 only by a PHI in DEST, then we can trivially merge the
951 PHI nodes from BB into DEST. */
952 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
955 gimple phi
= gsi_stmt (gsi
);
956 tree result
= gimple_phi_result (phi
);
957 use_operand_p imm_use
;
960 /* If the PHI's result is never used, then we can just
962 if (has_zero_uses (result
))
965 /* Get the single use of the result of this PHI node. */
966 if (!single_imm_use (result
, &imm_use
, &use_stmt
)
967 || gimple_code (use_stmt
) != GIMPLE_PHI
968 || gimple_bb (use_stmt
) != dest
969 || gimple_phi_arg_def (use_stmt
, dest_idx
) != result
)
973 /* If the loop above iterated through all the PHI nodes
974 in BB, then we can merge the PHIs from BB into DEST. */
980 /* Now let's drain WORKLIST. */
981 bool changed
= false;
982 while (current
!= worklist
)
985 changed
|= remove_forwarder_block_with_phi (bb
);
989 /* Removing forwarder blocks can cause formerly irreducible loops
990 to become reducible if we merged two entry blocks. */
993 loops_state_set (LOOPS_NEED_FIXUP
);
999 gate_merge_phi (void)
1006 const pass_data pass_data_merge_phi
=
1008 GIMPLE_PASS
, /* type */
1009 "mergephi", /* name */
1010 OPTGROUP_NONE
, /* optinfo_flags */
1011 true, /* has_gate */
1012 true, /* has_execute */
1013 TV_TREE_MERGE_PHI
, /* tv_id */
1014 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1015 0, /* properties_provided */
1016 0, /* properties_destroyed */
1017 0, /* todo_flags_start */
1018 TODO_verify_ssa
, /* todo_flags_finish */
1021 class pass_merge_phi
: public gimple_opt_pass
1024 pass_merge_phi (gcc::context
*ctxt
)
1025 : gimple_opt_pass (pass_data_merge_phi
, ctxt
)
1028 /* opt_pass methods: */
1029 opt_pass
* clone () { return new pass_merge_phi (m_ctxt
); }
1030 bool gate () { return gate_merge_phi (); }
1031 unsigned int execute () { return merge_phi_nodes (); }
1033 }; // class pass_merge_phi
1038 make_pass_merge_phi (gcc::context
*ctxt
)
1040 return new pass_merge_phi (ctxt
);
1043 /* Pass: cleanup the CFG just before expanding trees to RTL.
1044 This is just a round of label cleanups and case node grouping
1045 because after the tree optimizers have run such cleanups may
1049 execute_cleanup_cfg_post_optimizing (void)
1051 unsigned int todo
= 0;
1052 if (cleanup_tree_cfg ())
1053 todo
|= TODO_update_ssa
;
1054 maybe_remove_unreachable_handlers ();
1055 cleanup_dead_labels ();
1056 group_case_labels ();
1057 if ((flag_compare_debug_opt
|| flag_compare_debug
)
1058 && flag_dump_final_insns
)
1060 FILE *final_output
= fopen (flag_dump_final_insns
, "a");
1064 error ("could not open final insn dump file %qs: %m",
1065 flag_dump_final_insns
);
1066 flag_dump_final_insns
= NULL
;
1070 int save_unnumbered
= flag_dump_unnumbered
;
1071 int save_noaddr
= flag_dump_noaddr
;
1073 flag_dump_noaddr
= flag_dump_unnumbered
= 1;
1074 fprintf (final_output
, "\n");
1075 dump_enumerated_decls (final_output
, dump_flags
| TDF_NOUID
);
1076 flag_dump_noaddr
= save_noaddr
;
1077 flag_dump_unnumbered
= save_unnumbered
;
1078 if (fclose (final_output
))
1080 error ("could not close final insn dump file %qs: %m",
1081 flag_dump_final_insns
);
1082 flag_dump_final_insns
= NULL
;
1091 const pass_data pass_data_cleanup_cfg_post_optimizing
=
1093 GIMPLE_PASS
, /* type */
1094 "optimized", /* name */
1095 OPTGROUP_NONE
, /* optinfo_flags */
1096 false, /* has_gate */
1097 true, /* has_execute */
1098 TV_TREE_CLEANUP_CFG
, /* tv_id */
1099 PROP_cfg
, /* properties_required */
1100 0, /* properties_provided */
1101 0, /* properties_destroyed */
1102 0, /* todo_flags_start */
1103 TODO_remove_unused_locals
, /* todo_flags_finish */
1106 class pass_cleanup_cfg_post_optimizing
: public gimple_opt_pass
1109 pass_cleanup_cfg_post_optimizing (gcc::context
*ctxt
)
1110 : gimple_opt_pass (pass_data_cleanup_cfg_post_optimizing
, ctxt
)
1113 /* opt_pass methods: */
1114 unsigned int execute () {
1115 return execute_cleanup_cfg_post_optimizing ();
1118 }; // class pass_cleanup_cfg_post_optimizing
1123 make_pass_cleanup_cfg_post_optimizing (gcc::context
*ctxt
)
1125 return new pass_cleanup_cfg_post_optimizing (ctxt
);