1 /* CFG cleanup for trees.
2 Copyright (C) 2001-2015 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"
27 #include "double-int.h"
34 #include "fold-const.h"
37 #include "hard-reg-set.h"
40 #include "dominance.h"
43 #include "cfgcleanup.h"
44 #include "basic-block.h"
45 #include "diagnostic-core.h"
47 #include "langhooks.h"
48 #include "tree-ssa-alias.h"
49 #include "internal-fn.h"
51 #include "gimple-expr.h"
55 #include "gimple-iterator.h"
56 #include "gimple-ssa.h"
58 #include "tree-phinodes.h"
59 #include "ssa-iterators.h"
60 #include "stringpool.h"
61 #include "tree-ssanames.h"
62 #include "tree-ssa-loop-manip.h"
66 #include "tree-pass.h"
69 #include "tree-ssa-propagate.h"
70 #include "tree-scalar-evolution.h"
72 /* The set of blocks in that at least one of the following changes happened:
73 -- the statement at the end of the block was changed
74 -- the block was newly created
75 -- the set of the predecessors of the block changed
76 -- the set of the successors of the block changed
77 ??? Maybe we could track these changes separately, since they determine
78 what cleanups it makes sense to try on the block. */
79 bitmap cfgcleanup_altered_bbs
;
81 /* Remove any fallthru edge from EV. Return true if an edge was removed. */
84 remove_fallthru_edge (vec
<edge
, va_gc
> *ev
)
89 FOR_EACH_EDGE (e
, ei
, ev
)
90 if ((e
->flags
& EDGE_FALLTHRU
) != 0)
92 if (e
->flags
& EDGE_COMPLEX
)
93 e
->flags
&= ~EDGE_FALLTHRU
;
95 remove_edge_and_dominated_blocks (e
);
102 /* Disconnect an unreachable block in the control expression starting
106 cleanup_control_expr_graph (basic_block bb
, gimple_stmt_iterator gsi
)
110 gimple stmt
= gsi_stmt (gsi
);
113 if (!single_succ_p (bb
))
120 fold_defer_overflow_warnings ();
121 loc
= gimple_location (stmt
);
122 switch (gimple_code (stmt
))
125 val
= fold_binary_loc (loc
, gimple_cond_code (stmt
),
127 gimple_cond_lhs (stmt
),
128 gimple_cond_rhs (stmt
));
132 val
= gimple_switch_index (as_a
<gswitch
*> (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 /* Cleanup the GF_CALL_CTRL_ALTERING flag according to
182 to updated gimple_call_flags. */
185 cleanup_call_ctrl_altering_flag (gimple bb_end
)
187 if (!is_gimple_call (bb_end
)
188 || !gimple_call_ctrl_altering_p (bb_end
))
191 int flags
= gimple_call_flags (bb_end
);
192 if (((flags
& (ECF_CONST
| ECF_PURE
))
193 && !(flags
& ECF_LOOPING_CONST_OR_PURE
))
194 || (flags
& ECF_LEAF
))
195 gimple_call_set_ctrl_altering (bb_end
, false);
198 /* Try to remove superfluous control structures in basic block BB. Returns
199 true if anything changes. */
202 cleanup_control_flow_bb (basic_block bb
)
204 gimple_stmt_iterator gsi
;
208 /* If the last statement of the block could throw and now cannot,
209 we need to prune cfg. */
210 retval
|= gimple_purge_dead_eh_edges (bb
);
212 gsi
= gsi_last_bb (bb
);
216 stmt
= gsi_stmt (gsi
);
218 /* Try to cleanup ctrl altering flag for call which ends bb. */
219 cleanup_call_ctrl_altering_flag (stmt
);
221 if (gimple_code (stmt
) == GIMPLE_COND
222 || gimple_code (stmt
) == GIMPLE_SWITCH
)
223 retval
|= cleanup_control_expr_graph (bb
, gsi
);
224 else if (gimple_code (stmt
) == GIMPLE_GOTO
225 && TREE_CODE (gimple_goto_dest (stmt
)) == ADDR_EXPR
226 && (TREE_CODE (TREE_OPERAND (gimple_goto_dest (stmt
), 0))
229 /* If we had a computed goto which has a compile-time determinable
230 destination, then we can eliminate the goto. */
234 basic_block target_block
;
236 /* First look at all the outgoing edges. Delete any outgoing
237 edges which do not go to the right block. For the one
238 edge which goes to the right block, fix up its flags. */
239 label
= TREE_OPERAND (gimple_goto_dest (stmt
), 0);
240 target_block
= label_to_block (label
);
241 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
243 if (e
->dest
!= target_block
)
244 remove_edge_and_dominated_blocks (e
);
247 /* Turn off the EDGE_ABNORMAL flag. */
248 e
->flags
&= ~EDGE_ABNORMAL
;
250 /* And set EDGE_FALLTHRU. */
251 e
->flags
|= EDGE_FALLTHRU
;
256 bitmap_set_bit (cfgcleanup_altered_bbs
, bb
->index
);
257 bitmap_set_bit (cfgcleanup_altered_bbs
, target_block
->index
);
259 /* Remove the GOTO_EXPR as it is not needed. The CFG has all the
260 relevant information we need. */
261 gsi_remove (&gsi
, true);
265 /* Check for indirect calls that have been turned into
267 else if (is_gimple_call (stmt
)
268 && gimple_call_noreturn_p (stmt
)
269 && remove_fallthru_edge (bb
->succs
))
275 /* Return true if basic block BB does nothing except pass control
276 flow to another block and that we can safely insert a label at
277 the start of the successor block.
279 As a precondition, we require that BB be not equal to
283 tree_forwarder_block_p (basic_block bb
, bool phi_wanted
)
285 gimple_stmt_iterator gsi
;
288 /* BB must have a single outgoing edge. */
289 if (single_succ_p (bb
) != 1
290 /* If PHI_WANTED is false, BB must not have any PHI nodes.
291 Otherwise, BB must have PHI nodes. */
292 || gimple_seq_empty_p (phi_nodes (bb
)) == phi_wanted
293 /* BB may not be a predecessor of the exit block. */
294 || single_succ (bb
) == EXIT_BLOCK_PTR_FOR_FN (cfun
)
295 /* Nor should this be an infinite loop. */
296 || single_succ (bb
) == bb
297 /* BB may not have an abnormal outgoing edge. */
298 || (single_succ_edge (bb
)->flags
& EDGE_ABNORMAL
))
301 gcc_checking_assert (bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
));
303 locus
= single_succ_edge (bb
)->goto_locus
;
305 /* There should not be an edge coming from entry, or an EH edge. */
310 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
311 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) || (e
->flags
& EDGE_EH
))
313 /* If goto_locus of any of the edges differs, prevent removing
314 the forwarder block for -O0. */
315 else if (optimize
== 0 && e
->goto_locus
!= locus
)
319 /* Now walk through the statements backward. We can ignore labels,
320 anything else means this is not a forwarder block. */
321 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
323 gimple stmt
= gsi_stmt (gsi
);
325 switch (gimple_code (stmt
))
328 if (DECL_NONLOCAL (gimple_label_label (as_a
<glabel
*> (stmt
))))
330 if (optimize
== 0 && gimple_location (stmt
) != locus
)
334 /* ??? For now, hope there's a corresponding debug
335 assignment at the destination. */
347 /* Protect loop headers. */
348 if (bb
->loop_father
->header
== bb
)
351 dest
= EDGE_SUCC (bb
, 0)->dest
;
352 /* Protect loop preheaders and latches if requested. */
353 if (dest
->loop_father
->header
== dest
)
355 if (bb
->loop_father
== dest
->loop_father
)
357 if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES
))
359 /* If bb doesn't have a single predecessor we'd make this
360 loop have multiple latches. Don't do that if that
361 would in turn require disambiguating them. */
362 return (single_pred_p (bb
)
363 || loops_state_satisfies_p
364 (LOOPS_MAY_HAVE_MULTIPLE_LATCHES
));
366 else if (bb
->loop_father
== loop_outer (dest
->loop_father
))
367 return !loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS
);
368 /* Always preserve other edges into loop headers that are
369 not simple latches or preheaders. */
377 /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
378 those alternatives are equal in each of the PHI nodes, then return
379 true, else return false. */
382 phi_alternatives_equal (basic_block dest
, edge e1
, edge e2
)
384 int n1
= e1
->dest_idx
;
385 int n2
= e2
->dest_idx
;
388 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
390 gphi
*phi
= gsi
.phi ();
391 tree val1
= gimple_phi_arg_def (phi
, n1
);
392 tree val2
= gimple_phi_arg_def (phi
, n2
);
394 gcc_assert (val1
!= NULL_TREE
);
395 gcc_assert (val2
!= NULL_TREE
);
397 if (!operand_equal_for_phi_arg_p (val1
, val2
))
404 /* Removes forwarder block BB. Returns false if this failed. */
407 remove_forwarder_block (basic_block bb
)
409 edge succ
= single_succ_edge (bb
), e
, s
;
410 basic_block dest
= succ
->dest
;
413 gimple_stmt_iterator gsi
, gsi_to
;
414 bool can_move_debug_stmts
;
416 /* We check for infinite loops already in tree_forwarder_block_p.
417 However it may happen that the infinite loop is created
418 afterwards due to removal of forwarders. */
422 /* If the destination block consists of a nonlocal label or is a
423 EH landing pad, do not merge it. */
424 label
= first_stmt (dest
);
426 if (glabel
*label_stmt
= dyn_cast
<glabel
*> (label
))
427 if (DECL_NONLOCAL (gimple_label_label (label_stmt
))
428 || EH_LANDING_PAD_NR (gimple_label_label (label_stmt
)) != 0)
431 /* If there is an abnormal edge to basic block BB, but not into
432 dest, problems might occur during removal of the phi node at out
433 of ssa due to overlapping live ranges of registers.
435 If there is an abnormal edge in DEST, the problems would occur
436 anyway since cleanup_dead_labels would then merge the labels for
437 two different eh regions, and rest of exception handling code
440 So if there is an abnormal edge to BB, proceed only if there is
441 no abnormal edge to DEST and there are no phi nodes in DEST. */
442 if (bb_has_abnormal_pred (bb
)
443 && (bb_has_abnormal_pred (dest
)
444 || !gimple_seq_empty_p (phi_nodes (dest
))))
447 /* If there are phi nodes in DEST, and some of the blocks that are
448 predecessors of BB are also predecessors of DEST, check that the
449 phi node arguments match. */
450 if (!gimple_seq_empty_p (phi_nodes (dest
)))
452 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
454 s
= find_edge (e
->src
, dest
);
458 if (!phi_alternatives_equal (dest
, succ
, s
))
463 can_move_debug_stmts
= MAY_HAVE_DEBUG_STMTS
&& single_pred_p (dest
);
465 basic_block pred
= NULL
;
466 if (single_pred_p (bb
))
467 pred
= single_pred (bb
);
469 /* Redirect the edges. */
470 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
472 bitmap_set_bit (cfgcleanup_altered_bbs
, e
->src
->index
);
474 if (e
->flags
& EDGE_ABNORMAL
)
476 /* If there is an abnormal edge, redirect it anyway, and
477 move the labels to the new block to make it legal. */
478 s
= redirect_edge_succ_nodup (e
, dest
);
481 s
= redirect_edge_and_branch (e
, dest
);
485 /* Create arguments for the phi nodes, since the edge was not
487 for (gphi_iterator psi
= gsi_start_phis (dest
);
491 gphi
*phi
= psi
.phi ();
492 source_location l
= gimple_phi_arg_location_from_edge (phi
, succ
);
493 tree def
= gimple_phi_arg_def (phi
, succ
->dest_idx
);
494 add_phi_arg (phi
, unshare_expr (def
), s
, l
);
499 /* Move nonlocal labels and computed goto targets as well as user
500 defined labels and labels with an EH landing pad number to the
501 new block, so that the redirection of the abnormal edges works,
502 jump targets end up in a sane place and debug information for
503 labels is retained. */
504 gsi_to
= gsi_start_bb (dest
);
505 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
508 label
= gsi_stmt (gsi
);
509 if (is_gimple_debug (label
))
511 decl
= gimple_label_label (as_a
<glabel
*> (label
));
512 if (EH_LANDING_PAD_NR (decl
) != 0
513 || DECL_NONLOCAL (decl
)
514 || FORCED_LABEL (decl
)
515 || !DECL_ARTIFICIAL (decl
))
517 gsi_remove (&gsi
, false);
518 gsi_insert_before (&gsi_to
, label
, GSI_SAME_STMT
);
524 /* Move debug statements if the destination has a single predecessor. */
525 if (can_move_debug_stmts
)
527 gsi_to
= gsi_after_labels (dest
);
528 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); )
530 gimple debug
= gsi_stmt (gsi
);
531 if (!is_gimple_debug (debug
))
533 gsi_remove (&gsi
, false);
534 gsi_insert_before (&gsi_to
, debug
, GSI_SAME_STMT
);
538 bitmap_set_bit (cfgcleanup_altered_bbs
, dest
->index
);
540 /* Update the dominators. */
541 if (dom_info_available_p (CDI_DOMINATORS
))
543 basic_block dom
, dombb
, domdest
;
545 dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
546 domdest
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
549 /* Shortcut to avoid calling (relatively expensive)
550 nearest_common_dominator unless necessary. */
554 dom
= nearest_common_dominator (CDI_DOMINATORS
, domdest
, dombb
);
556 set_immediate_dominator (CDI_DOMINATORS
, dest
, dom
);
559 /* Adjust latch infomation of BB's parent loop as otherwise
560 the cfg hook has a hard time not to kill the loop. */
561 if (current_loops
&& bb
->loop_father
->latch
== bb
)
562 bb
->loop_father
->latch
= pred
;
564 /* And kill the forwarder block. */
565 delete_basic_block (bb
);
570 /* STMT is a call that has been discovered noreturn. Fixup the CFG
571 and remove LHS. Return true if something changed. */
574 fixup_noreturn_call (gimple stmt
)
576 basic_block bb
= gimple_bb (stmt
);
578 if (gimple_call_builtin_p (stmt
, BUILT_IN_RETURN
))
581 /* First split basic block if stmt is not last. */
582 if (stmt
!= gsi_stmt (gsi_last_bb (bb
)))
584 if (stmt
== gsi_stmt (gsi_last_nondebug_bb (bb
)))
586 /* Don't split if there are only debug stmts
587 after stmt, that can result in -fcompare-debug
588 failures. Remove the debug stmts instead,
589 they should be all unreachable anyway. */
590 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
591 for (gsi_next (&gsi
); !gsi_end_p (gsi
); )
592 gsi_remove (&gsi
, true);
595 split_block (bb
, stmt
);
598 /* If there is an LHS, remove it. */
599 tree lhs
= gimple_call_lhs (stmt
);
602 gimple_call_set_lhs (stmt
, NULL_TREE
);
604 /* We need to fix up the SSA name to avoid checking errors. */
605 if (TREE_CODE (lhs
) == SSA_NAME
)
607 tree new_var
= create_tmp_reg (TREE_TYPE (lhs
));
608 SET_SSA_NAME_VAR_OR_IDENTIFIER (lhs
, new_var
);
609 SSA_NAME_DEF_STMT (lhs
) = gimple_build_nop ();
610 set_ssa_default_def (cfun
, new_var
, lhs
);
616 return remove_fallthru_edge (bb
->succs
);
620 /* Split basic blocks on calls in the middle of a basic block that are now
621 known not to return, and remove the unreachable code. */
624 split_bb_on_noreturn_calls (basic_block bb
)
626 bool changed
= false;
627 gimple_stmt_iterator gsi
;
629 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
631 gimple stmt
= gsi_stmt (gsi
);
633 if (!is_gimple_call (stmt
))
636 if (gimple_call_noreturn_p (stmt
))
637 changed
|= fixup_noreturn_call (stmt
);
641 bitmap_set_bit (cfgcleanup_altered_bbs
, bb
->index
);
645 /* Tries to cleanup cfg in basic block BB. Returns true if anything
649 cleanup_tree_cfg_bb (basic_block bb
)
651 bool retval
= cleanup_control_flow_bb (bb
);
653 if (tree_forwarder_block_p (bb
, false)
654 && remove_forwarder_block (bb
))
657 /* Merging the blocks may create new opportunities for folding
658 conditional branches (due to the elimination of single-valued PHI
660 if (single_succ_p (bb
)
661 && can_merge_blocks_p (bb
, single_succ (bb
)))
663 merge_blocks (bb
, single_succ (bb
));
670 /* Iterate the cfg cleanups, while anything changes. */
673 cleanup_tree_cfg_1 (void)
679 /* Prepare the worklists of altered blocks. */
680 cfgcleanup_altered_bbs
= BITMAP_ALLOC (NULL
);
682 /* During forwarder block cleanup, we may redirect edges out of
683 SWITCH_EXPRs, which can get expensive. So we want to enable
684 recording of edge to CASE_LABEL_EXPR. */
685 start_recording_case_labels ();
687 /* Start by iterating over all basic blocks. We cannot use FOR_EACH_BB_FN,
688 since the basic blocks may get removed. */
689 n
= last_basic_block_for_fn (cfun
);
690 for (i
= NUM_FIXED_BLOCKS
; i
< n
; i
++)
692 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
695 retval
|= cleanup_tree_cfg_bb (bb
);
696 retval
|= split_bb_on_noreturn_calls (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_FOR_FN (cfun
, i
);
712 retval
|= cleanup_tree_cfg_bb (bb
);
714 /* Rerun split_bb_on_noreturn_calls, in case we have altered any noreturn
716 retval
|= split_bb_on_noreturn_calls (bb
);
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)
776 unsigned n_new_loops
;
778 calculate_dominance_info (CDI_DOMINATORS
);
780 timevar_push (TV_REPAIR_LOOPS
);
781 changed_bbs
= BITMAP_ALLOC (NULL
);
782 n_new_loops
= fix_loop_structure (changed_bbs
);
784 /* This usually does nothing. But sometimes parts of cfg that originally
785 were inside a loop get out of it due to edge removal (since they
786 become unreachable by back edges from latch). Also a former
787 irreducible loop can become reducible - in this case force a full
788 rewrite into loop-closed SSA form. */
789 if (loops_state_satisfies_p (LOOP_CLOSED_SSA
))
790 rewrite_into_loop_closed_ssa (n_new_loops
? NULL
: changed_bbs
,
793 BITMAP_FREE (changed_bbs
);
795 #ifdef ENABLE_CHECKING
796 verify_loop_structure ();
800 timevar_pop (TV_REPAIR_LOOPS
);
803 /* Cleanup cfg and repair loop structures. */
806 cleanup_tree_cfg (void)
808 bool changed
= cleanup_tree_cfg_noloop ();
810 if (current_loops
!= NULL
811 && loops_state_satisfies_p (LOOPS_NEED_FIXUP
))
812 repair_loop_structures ();
817 /* Tries to merge the PHI nodes at BB into those at BB's sole successor.
818 Returns true if successful. */
821 remove_forwarder_block_with_phi (basic_block bb
)
823 edge succ
= single_succ_edge (bb
);
824 basic_block dest
= succ
->dest
;
826 basic_block dombb
, domdest
, dom
;
828 /* We check for infinite loops already in tree_forwarder_block_p.
829 However it may happen that the infinite loop is created
830 afterwards due to removal of forwarders. */
834 /* If the destination block consists of a nonlocal label, do not
836 label
= first_stmt (dest
);
838 if (glabel
*label_stmt
= dyn_cast
<glabel
*> (label
))
839 if (DECL_NONLOCAL (gimple_label_label (label_stmt
)))
842 /* Record BB's single pred in case we need to update the father
843 loop's latch information later. */
844 basic_block pred
= NULL
;
845 if (single_pred_p (bb
))
846 pred
= single_pred (bb
);
848 /* Redirect each incoming edge to BB to DEST. */
849 while (EDGE_COUNT (bb
->preds
) > 0)
851 edge e
= EDGE_PRED (bb
, 0), s
;
854 s
= find_edge (e
->src
, dest
);
857 /* We already have an edge S from E->src to DEST. If S and
858 E->dest's sole successor edge have the same PHI arguments
859 at DEST, redirect S to DEST. */
860 if (phi_alternatives_equal (dest
, s
, succ
))
862 e
= redirect_edge_and_branch (e
, dest
);
863 redirect_edge_var_map_clear (e
);
867 /* PHI arguments are different. Create a forwarder block by
868 splitting E so that we can merge PHI arguments on E to
870 e
= single_succ_edge (split_edge (e
));
873 s
= redirect_edge_and_branch (e
, dest
);
875 /* redirect_edge_and_branch must not create a new edge. */
878 /* Add to the PHI nodes at DEST each PHI argument removed at the
880 for (gsi
= gsi_start_phis (dest
);
884 gphi
*phi
= gsi
.phi ();
885 tree def
= gimple_phi_arg_def (phi
, succ
->dest_idx
);
886 source_location locus
= gimple_phi_arg_location_from_edge (phi
, succ
);
888 if (TREE_CODE (def
) == SSA_NAME
)
890 /* If DEF is one of the results of PHI nodes removed during
891 redirection, replace it with the PHI argument that used
893 vec
<edge_var_map
> *head
= redirect_edge_var_map_vector (e
);
894 size_t length
= head
? head
->length () : 0;
895 for (size_t i
= 0; i
< length
; i
++)
897 edge_var_map
*vm
= &(*head
)[i
];
898 tree old_arg
= redirect_edge_var_map_result (vm
);
899 tree new_arg
= redirect_edge_var_map_def (vm
);
904 locus
= redirect_edge_var_map_location (vm
);
910 add_phi_arg (phi
, def
, s
, locus
);
913 redirect_edge_var_map_clear (e
);
916 /* Update the dominators. */
917 dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
918 domdest
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
921 /* Shortcut to avoid calling (relatively expensive)
922 nearest_common_dominator unless necessary. */
926 dom
= nearest_common_dominator (CDI_DOMINATORS
, domdest
, dombb
);
928 set_immediate_dominator (CDI_DOMINATORS
, dest
, dom
);
930 /* Adjust latch infomation of BB's parent loop as otherwise
931 the cfg hook has a hard time not to kill the loop. */
932 if (current_loops
&& bb
->loop_father
->latch
== bb
)
933 bb
->loop_father
->latch
= pred
;
935 /* Remove BB since all of BB's incoming edges have been redirected
937 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)>;
969 const pass_data pass_data_merge_phi
=
971 GIMPLE_PASS
, /* type */
972 "mergephi", /* name */
973 OPTGROUP_NONE
, /* optinfo_flags */
974 TV_TREE_MERGE_PHI
, /* tv_id */
975 ( PROP_cfg
| PROP_ssa
), /* properties_required */
976 0, /* properties_provided */
977 0, /* properties_destroyed */
978 0, /* todo_flags_start */
979 0, /* todo_flags_finish */
982 class pass_merge_phi
: public gimple_opt_pass
985 pass_merge_phi (gcc::context
*ctxt
)
986 : gimple_opt_pass (pass_data_merge_phi
, ctxt
)
989 /* opt_pass methods: */
990 opt_pass
* clone () { return new pass_merge_phi (m_ctxt
); }
991 virtual unsigned int execute (function
*);
993 }; // class pass_merge_phi
996 pass_merge_phi::execute (function
*fun
)
998 basic_block
*worklist
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (fun
));
999 basic_block
*current
= worklist
;
1002 calculate_dominance_info (CDI_DOMINATORS
);
1004 /* Find all PHI nodes that we may be able to merge. */
1005 FOR_EACH_BB_FN (bb
, fun
)
1009 /* Look for a forwarder block with PHI nodes. */
1010 if (!tree_forwarder_block_p (bb
, true))
1013 dest
= single_succ (bb
);
1015 /* We have to feed into another basic block with PHI
1017 if (gimple_seq_empty_p (phi_nodes (dest
))
1018 /* We don't want to deal with a basic block with
1020 || bb_has_abnormal_pred (bb
))
1023 if (!dominated_by_p (CDI_DOMINATORS
, dest
, bb
))
1025 /* If BB does not dominate DEST, then the PHI nodes at
1026 DEST must be the only users of the results of the PHI
1033 unsigned int dest_idx
= single_succ_edge (bb
)->dest_idx
;
1035 /* BB dominates DEST. There may be many users of the PHI
1036 nodes in BB. However, there is still a trivial case we
1037 can handle. If the result of every PHI in BB is used
1038 only by a PHI in DEST, then we can trivially merge the
1039 PHI nodes from BB into DEST. */
1040 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
1043 gphi
*phi
= gsi
.phi ();
1044 tree result
= gimple_phi_result (phi
);
1045 use_operand_p imm_use
;
1048 /* If the PHI's result is never used, then we can just
1050 if (has_zero_uses (result
))
1053 /* Get the single use of the result of this PHI node. */
1054 if (!single_imm_use (result
, &imm_use
, &use_stmt
)
1055 || gimple_code (use_stmt
) != GIMPLE_PHI
1056 || gimple_bb (use_stmt
) != dest
1057 || gimple_phi_arg_def (use_stmt
, dest_idx
) != result
)
1061 /* If the loop above iterated through all the PHI nodes
1062 in BB, then we can merge the PHIs from BB into DEST. */
1063 if (gsi_end_p (gsi
))
1068 /* Now let's drain WORKLIST. */
1069 bool changed
= false;
1070 while (current
!= worklist
)
1073 changed
|= remove_forwarder_block_with_phi (bb
);
1077 /* Removing forwarder blocks can cause formerly irreducible loops
1078 to become reducible if we merged two entry blocks. */
1081 loops_state_set (LOOPS_NEED_FIXUP
);
1089 make_pass_merge_phi (gcc::context
*ctxt
)
1091 return new pass_merge_phi (ctxt
);
1094 /* Pass: cleanup the CFG just before expanding trees to RTL.
1095 This is just a round of label cleanups and case node grouping
1096 because after the tree optimizers have run such cleanups may
1100 execute_cleanup_cfg_post_optimizing (void)
1102 unsigned int todo
= 0;
1103 if (cleanup_tree_cfg ())
1104 todo
|= TODO_update_ssa
;
1105 maybe_remove_unreachable_handlers ();
1106 cleanup_dead_labels ();
1107 group_case_labels ();
1108 if ((flag_compare_debug_opt
|| flag_compare_debug
)
1109 && flag_dump_final_insns
)
1111 FILE *final_output
= fopen (flag_dump_final_insns
, "a");
1115 error ("could not open final insn dump file %qs: %m",
1116 flag_dump_final_insns
);
1117 flag_dump_final_insns
= NULL
;
1121 int save_unnumbered
= flag_dump_unnumbered
;
1122 int save_noaddr
= flag_dump_noaddr
;
1124 flag_dump_noaddr
= flag_dump_unnumbered
= 1;
1125 fprintf (final_output
, "\n");
1126 dump_enumerated_decls (final_output
, dump_flags
| TDF_NOUID
);
1127 flag_dump_noaddr
= save_noaddr
;
1128 flag_dump_unnumbered
= save_unnumbered
;
1129 if (fclose (final_output
))
1131 error ("could not close final insn dump file %qs: %m",
1132 flag_dump_final_insns
);
1133 flag_dump_final_insns
= NULL
;
1142 const pass_data pass_data_cleanup_cfg_post_optimizing
=
1144 GIMPLE_PASS
, /* type */
1145 "optimized", /* name */
1146 OPTGROUP_NONE
, /* optinfo_flags */
1147 TV_TREE_CLEANUP_CFG
, /* tv_id */
1148 PROP_cfg
, /* properties_required */
1149 0, /* properties_provided */
1150 0, /* properties_destroyed */
1151 0, /* todo_flags_start */
1152 TODO_remove_unused_locals
, /* todo_flags_finish */
1155 class pass_cleanup_cfg_post_optimizing
: public gimple_opt_pass
1158 pass_cleanup_cfg_post_optimizing (gcc::context
*ctxt
)
1159 : gimple_opt_pass (pass_data_cleanup_cfg_post_optimizing
, ctxt
)
1162 /* opt_pass methods: */
1163 virtual unsigned int execute (function
*)
1165 return execute_cleanup_cfg_post_optimizing ();
1168 }; // class pass_cleanup_cfg_post_optimizing
1173 make_pass_cleanup_cfg_post_optimizing (gcc::context
*ctxt
)
1175 return new pass_cleanup_cfg_post_optimizing (ctxt
);