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"
39 #include "dominance.h"
42 #include "cfgcleanup.h"
43 #include "basic-block.h"
44 #include "diagnostic-core.h"
46 #include "langhooks.h"
47 #include "tree-ssa-alias.h"
48 #include "internal-fn.h"
50 #include "gimple-expr.h"
54 #include "gimple-iterator.h"
55 #include "gimple-ssa.h"
57 #include "tree-phinodes.h"
58 #include "ssa-iterators.h"
59 #include "stringpool.h"
60 #include "tree-ssanames.h"
61 #include "tree-ssa-loop-manip.h"
64 #include "statistics.h"
66 #include "fixed-value.h"
67 #include "insn-config.h"
78 #include "tree-pass.h"
81 #include "tree-ssa-propagate.h"
82 #include "tree-scalar-evolution.h"
84 /* The set of blocks in that at least one of the following changes happened:
85 -- the statement at the end of the block was changed
86 -- the block was newly created
87 -- the set of the predecessors of the block changed
88 -- the set of the successors of the block changed
89 ??? Maybe we could track these changes separately, since they determine
90 what cleanups it makes sense to try on the block. */
91 bitmap cfgcleanup_altered_bbs
;
93 /* Remove any fallthru edge from EV. Return true if an edge was removed. */
96 remove_fallthru_edge (vec
<edge
, va_gc
> *ev
)
101 FOR_EACH_EDGE (e
, ei
, ev
)
102 if ((e
->flags
& EDGE_FALLTHRU
) != 0)
104 if (e
->flags
& EDGE_COMPLEX
)
105 e
->flags
&= ~EDGE_FALLTHRU
;
107 remove_edge_and_dominated_blocks (e
);
114 /* Disconnect an unreachable block in the control expression starting
118 cleanup_control_expr_graph (basic_block bb
, gimple_stmt_iterator gsi
)
122 gimple stmt
= gsi_stmt (gsi
);
125 if (!single_succ_p (bb
))
132 fold_defer_overflow_warnings ();
133 loc
= gimple_location (stmt
);
134 switch (gimple_code (stmt
))
137 val
= fold_binary_loc (loc
, gimple_cond_code (stmt
),
139 gimple_cond_lhs (stmt
),
140 gimple_cond_rhs (stmt
));
144 val
= gimple_switch_index (as_a
<gswitch
*> (stmt
));
150 taken_edge
= find_taken_edge (bb
, val
);
153 fold_undefer_and_ignore_overflow_warnings ();
157 /* Remove all the edges except the one that is always executed. */
159 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
165 fold_undefer_overflow_warnings
166 (true, stmt
, WARN_STRICT_OVERFLOW_CONDITIONAL
);
170 taken_edge
->probability
+= e
->probability
;
171 taken_edge
->count
+= e
->count
;
172 remove_edge_and_dominated_blocks (e
);
179 fold_undefer_and_ignore_overflow_warnings ();
180 if (taken_edge
->probability
> REG_BR_PROB_BASE
)
181 taken_edge
->probability
= REG_BR_PROB_BASE
;
184 taken_edge
= single_succ_edge (bb
);
186 bitmap_set_bit (cfgcleanup_altered_bbs
, bb
->index
);
187 gsi_remove (&gsi
, true);
188 taken_edge
->flags
= EDGE_FALLTHRU
;
193 /* Cleanup the GF_CALL_CTRL_ALTERING flag according to
194 to updated gimple_call_flags. */
197 cleanup_call_ctrl_altering_flag (gimple bb_end
)
199 if (!is_gimple_call (bb_end
)
200 || !gimple_call_ctrl_altering_p (bb_end
))
203 int flags
= gimple_call_flags (bb_end
);
204 if (((flags
& (ECF_CONST
| ECF_PURE
))
205 && !(flags
& ECF_LOOPING_CONST_OR_PURE
))
206 || (flags
& ECF_LEAF
))
207 gimple_call_set_ctrl_altering (bb_end
, false);
210 /* Try to remove superfluous control structures in basic block BB. Returns
211 true if anything changes. */
214 cleanup_control_flow_bb (basic_block bb
)
216 gimple_stmt_iterator gsi
;
220 /* If the last statement of the block could throw and now cannot,
221 we need to prune cfg. */
222 retval
|= gimple_purge_dead_eh_edges (bb
);
224 gsi
= gsi_last_bb (bb
);
228 stmt
= gsi_stmt (gsi
);
230 /* Try to cleanup ctrl altering flag for call which ends bb. */
231 cleanup_call_ctrl_altering_flag (stmt
);
233 if (gimple_code (stmt
) == GIMPLE_COND
234 || gimple_code (stmt
) == GIMPLE_SWITCH
)
235 retval
|= cleanup_control_expr_graph (bb
, gsi
);
236 else if (gimple_code (stmt
) == GIMPLE_GOTO
237 && TREE_CODE (gimple_goto_dest (stmt
)) == ADDR_EXPR
238 && (TREE_CODE (TREE_OPERAND (gimple_goto_dest (stmt
), 0))
241 /* If we had a computed goto which has a compile-time determinable
242 destination, then we can eliminate the goto. */
246 basic_block target_block
;
248 /* First look at all the outgoing edges. Delete any outgoing
249 edges which do not go to the right block. For the one
250 edge which goes to the right block, fix up its flags. */
251 label
= TREE_OPERAND (gimple_goto_dest (stmt
), 0);
252 target_block
= label_to_block (label
);
253 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
255 if (e
->dest
!= target_block
)
256 remove_edge_and_dominated_blocks (e
);
259 /* Turn off the EDGE_ABNORMAL flag. */
260 e
->flags
&= ~EDGE_ABNORMAL
;
262 /* And set EDGE_FALLTHRU. */
263 e
->flags
|= EDGE_FALLTHRU
;
268 bitmap_set_bit (cfgcleanup_altered_bbs
, bb
->index
);
269 bitmap_set_bit (cfgcleanup_altered_bbs
, target_block
->index
);
271 /* Remove the GOTO_EXPR as it is not needed. The CFG has all the
272 relevant information we need. */
273 gsi_remove (&gsi
, true);
277 /* Check for indirect calls that have been turned into
279 else if (is_gimple_call (stmt
)
280 && gimple_call_noreturn_p (stmt
)
281 && remove_fallthru_edge (bb
->succs
))
287 /* Return true if basic block BB does nothing except pass control
288 flow to another block and that we can safely insert a label at
289 the start of the successor block.
291 As a precondition, we require that BB be not equal to
295 tree_forwarder_block_p (basic_block bb
, bool phi_wanted
)
297 gimple_stmt_iterator gsi
;
300 /* BB must have a single outgoing edge. */
301 if (single_succ_p (bb
) != 1
302 /* If PHI_WANTED is false, BB must not have any PHI nodes.
303 Otherwise, BB must have PHI nodes. */
304 || gimple_seq_empty_p (phi_nodes (bb
)) == phi_wanted
305 /* BB may not be a predecessor of the exit block. */
306 || single_succ (bb
) == EXIT_BLOCK_PTR_FOR_FN (cfun
)
307 /* Nor should this be an infinite loop. */
308 || single_succ (bb
) == bb
309 /* BB may not have an abnormal outgoing edge. */
310 || (single_succ_edge (bb
)->flags
& EDGE_ABNORMAL
))
313 gcc_checking_assert (bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
));
315 locus
= single_succ_edge (bb
)->goto_locus
;
317 /* There should not be an edge coming from entry, or an EH edge. */
322 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
323 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) || (e
->flags
& EDGE_EH
))
325 /* If goto_locus of any of the edges differs, prevent removing
326 the forwarder block for -O0. */
327 else if (optimize
== 0 && e
->goto_locus
!= locus
)
331 /* Now walk through the statements backward. We can ignore labels,
332 anything else means this is not a forwarder block. */
333 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
335 gimple stmt
= gsi_stmt (gsi
);
337 switch (gimple_code (stmt
))
340 if (DECL_NONLOCAL (gimple_label_label (as_a
<glabel
*> (stmt
))))
342 if (optimize
== 0 && gimple_location (stmt
) != locus
)
346 /* ??? For now, hope there's a corresponding debug
347 assignment at the destination. */
359 /* Protect loop headers. */
360 if (bb
->loop_father
->header
== bb
)
363 dest
= EDGE_SUCC (bb
, 0)->dest
;
364 /* Protect loop preheaders and latches if requested. */
365 if (dest
->loop_father
->header
== dest
)
367 if (bb
->loop_father
== dest
->loop_father
)
369 if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES
))
371 /* If bb doesn't have a single predecessor we'd make this
372 loop have multiple latches. Don't do that if that
373 would in turn require disambiguating them. */
374 return (single_pred_p (bb
)
375 || loops_state_satisfies_p
376 (LOOPS_MAY_HAVE_MULTIPLE_LATCHES
));
378 else if (bb
->loop_father
== loop_outer (dest
->loop_father
))
379 return !loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS
);
380 /* Always preserve other edges into loop headers that are
381 not simple latches or preheaders. */
389 /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
390 those alternatives are equal in each of the PHI nodes, then return
391 true, else return false. */
394 phi_alternatives_equal (basic_block dest
, edge e1
, edge e2
)
396 int n1
= e1
->dest_idx
;
397 int n2
= e2
->dest_idx
;
400 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
402 gphi
*phi
= gsi
.phi ();
403 tree val1
= gimple_phi_arg_def (phi
, n1
);
404 tree val2
= gimple_phi_arg_def (phi
, n2
);
406 gcc_assert (val1
!= NULL_TREE
);
407 gcc_assert (val2
!= NULL_TREE
);
409 if (!operand_equal_for_phi_arg_p (val1
, val2
))
416 /* Removes forwarder block BB. Returns false if this failed. */
419 remove_forwarder_block (basic_block bb
)
421 edge succ
= single_succ_edge (bb
), e
, s
;
422 basic_block dest
= succ
->dest
;
425 gimple_stmt_iterator gsi
, gsi_to
;
426 bool can_move_debug_stmts
;
428 /* We check for infinite loops already in tree_forwarder_block_p.
429 However it may happen that the infinite loop is created
430 afterwards due to removal of forwarders. */
434 /* If the destination block consists of a nonlocal label or is a
435 EH landing pad, do not merge it. */
436 label
= first_stmt (dest
);
438 if (glabel
*label_stmt
= dyn_cast
<glabel
*> (label
))
439 if (DECL_NONLOCAL (gimple_label_label (label_stmt
))
440 || EH_LANDING_PAD_NR (gimple_label_label (label_stmt
)) != 0)
443 /* If there is an abnormal edge to basic block BB, but not into
444 dest, problems might occur during removal of the phi node at out
445 of ssa due to overlapping live ranges of registers.
447 If there is an abnormal edge in DEST, the problems would occur
448 anyway since cleanup_dead_labels would then merge the labels for
449 two different eh regions, and rest of exception handling code
452 So if there is an abnormal edge to BB, proceed only if there is
453 no abnormal edge to DEST and there are no phi nodes in DEST. */
454 if (bb_has_abnormal_pred (bb
)
455 && (bb_has_abnormal_pred (dest
)
456 || !gimple_seq_empty_p (phi_nodes (dest
))))
459 /* If there are phi nodes in DEST, and some of the blocks that are
460 predecessors of BB are also predecessors of DEST, check that the
461 phi node arguments match. */
462 if (!gimple_seq_empty_p (phi_nodes (dest
)))
464 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
466 s
= find_edge (e
->src
, dest
);
470 if (!phi_alternatives_equal (dest
, succ
, s
))
475 can_move_debug_stmts
= MAY_HAVE_DEBUG_STMTS
&& single_pred_p (dest
);
477 basic_block pred
= NULL
;
478 if (single_pred_p (bb
))
479 pred
= single_pred (bb
);
481 /* Redirect the edges. */
482 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
484 bitmap_set_bit (cfgcleanup_altered_bbs
, e
->src
->index
);
486 if (e
->flags
& EDGE_ABNORMAL
)
488 /* If there is an abnormal edge, redirect it anyway, and
489 move the labels to the new block to make it legal. */
490 s
= redirect_edge_succ_nodup (e
, dest
);
493 s
= redirect_edge_and_branch (e
, dest
);
497 /* Create arguments for the phi nodes, since the edge was not
499 for (gphi_iterator psi
= gsi_start_phis (dest
);
503 gphi
*phi
= psi
.phi ();
504 source_location l
= gimple_phi_arg_location_from_edge (phi
, succ
);
505 tree def
= gimple_phi_arg_def (phi
, succ
->dest_idx
);
506 add_phi_arg (phi
, unshare_expr (def
), s
, l
);
511 /* Move nonlocal labels and computed goto targets as well as user
512 defined labels and labels with an EH landing pad number to the
513 new block, so that the redirection of the abnormal edges works,
514 jump targets end up in a sane place and debug information for
515 labels is retained. */
516 gsi_to
= gsi_start_bb (dest
);
517 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
520 label
= gsi_stmt (gsi
);
521 if (is_gimple_debug (label
))
523 decl
= gimple_label_label (as_a
<glabel
*> (label
));
524 if (EH_LANDING_PAD_NR (decl
) != 0
525 || DECL_NONLOCAL (decl
)
526 || FORCED_LABEL (decl
)
527 || !DECL_ARTIFICIAL (decl
))
529 gsi_remove (&gsi
, false);
530 gsi_insert_before (&gsi_to
, label
, GSI_SAME_STMT
);
536 /* Move debug statements if the destination has a single predecessor. */
537 if (can_move_debug_stmts
)
539 gsi_to
= gsi_after_labels (dest
);
540 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); )
542 gimple debug
= gsi_stmt (gsi
);
543 if (!is_gimple_debug (debug
))
545 gsi_remove (&gsi
, false);
546 gsi_insert_before (&gsi_to
, debug
, GSI_SAME_STMT
);
550 bitmap_set_bit (cfgcleanup_altered_bbs
, dest
->index
);
552 /* Update the dominators. */
553 if (dom_info_available_p (CDI_DOMINATORS
))
555 basic_block dom
, dombb
, domdest
;
557 dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
558 domdest
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
561 /* Shortcut to avoid calling (relatively expensive)
562 nearest_common_dominator unless necessary. */
566 dom
= nearest_common_dominator (CDI_DOMINATORS
, domdest
, dombb
);
568 set_immediate_dominator (CDI_DOMINATORS
, dest
, dom
);
571 /* Adjust latch infomation of BB's parent loop as otherwise
572 the cfg hook has a hard time not to kill the loop. */
573 if (current_loops
&& bb
->loop_father
->latch
== bb
)
574 bb
->loop_father
->latch
= pred
;
576 /* And kill the forwarder block. */
577 delete_basic_block (bb
);
582 /* STMT is a call that has been discovered noreturn. Fixup the CFG
583 and remove LHS. Return true if something changed. */
586 fixup_noreturn_call (gimple stmt
)
588 basic_block bb
= gimple_bb (stmt
);
590 if (gimple_call_builtin_p (stmt
, BUILT_IN_RETURN
))
593 /* First split basic block if stmt is not last. */
594 if (stmt
!= gsi_stmt (gsi_last_bb (bb
)))
596 if (stmt
== gsi_stmt (gsi_last_nondebug_bb (bb
)))
598 /* Don't split if there are only debug stmts
599 after stmt, that can result in -fcompare-debug
600 failures. Remove the debug stmts instead,
601 they should be all unreachable anyway. */
602 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
603 for (gsi_next (&gsi
); !gsi_end_p (gsi
); )
604 gsi_remove (&gsi
, true);
607 split_block (bb
, stmt
);
610 /* If there is an LHS, remove it. */
611 tree lhs
= gimple_call_lhs (stmt
);
614 gimple_call_set_lhs (stmt
, NULL_TREE
);
616 /* We need to fix up the SSA name to avoid checking errors. */
617 if (TREE_CODE (lhs
) == SSA_NAME
)
619 tree new_var
= create_tmp_reg (TREE_TYPE (lhs
));
620 SET_SSA_NAME_VAR_OR_IDENTIFIER (lhs
, new_var
);
621 SSA_NAME_DEF_STMT (lhs
) = gimple_build_nop ();
622 set_ssa_default_def (cfun
, new_var
, lhs
);
628 /* Mark the call as altering control flow. */
629 gimple_call_set_ctrl_altering (stmt
, true);
631 return remove_fallthru_edge (bb
->succs
);
635 /* Tries to cleanup cfg in basic block BB. Returns true if anything
639 cleanup_tree_cfg_bb (basic_block bb
)
641 bool retval
= cleanup_control_flow_bb (bb
);
643 if (tree_forwarder_block_p (bb
, false)
644 && remove_forwarder_block (bb
))
647 /* Merging the blocks may create new opportunities for folding
648 conditional branches (due to the elimination of single-valued PHI
650 if (single_succ_p (bb
)
651 && can_merge_blocks_p (bb
, single_succ (bb
)))
653 /* If there is a merge opportunity with the predecessor
654 do nothing now but wait until we process the predecessor.
655 This happens when we visit BBs in a non-optimal order and
656 avoids quadratic behavior with adjusting stmts BB pointer. */
657 if (single_pred_p (bb
)
658 && can_merge_blocks_p (single_pred (bb
), bb
))
662 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
);
694 retval
|= cleanup_tree_cfg_bb (bb
);
697 /* Now process the altered blocks, as long as any are available. */
698 while (!bitmap_empty_p (cfgcleanup_altered_bbs
))
700 i
= bitmap_first_set_bit (cfgcleanup_altered_bbs
);
701 bitmap_clear_bit (cfgcleanup_altered_bbs
, i
);
702 if (i
< NUM_FIXED_BLOCKS
)
705 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
709 retval
|= cleanup_tree_cfg_bb (bb
);
712 end_recording_case_labels ();
713 BITMAP_FREE (cfgcleanup_altered_bbs
);
718 /* Remove unreachable blocks and other miscellaneous clean up work.
719 Return true if the flowgraph was modified, false otherwise. */
722 cleanup_tree_cfg_noloop (void)
726 timevar_push (TV_TREE_CLEANUP_CFG
);
728 /* Iterate until there are no more cleanups left to do. If any
729 iteration changed the flowgraph, set CHANGED to true.
731 If dominance information is available, there cannot be any unreachable
733 if (!dom_info_available_p (CDI_DOMINATORS
))
735 changed
= delete_unreachable_blocks ();
736 calculate_dominance_info (CDI_DOMINATORS
);
740 #ifdef ENABLE_CHECKING
741 verify_dominators (CDI_DOMINATORS
);
746 changed
|= cleanup_tree_cfg_1 ();
748 gcc_assert (dom_info_available_p (CDI_DOMINATORS
));
751 #ifdef ENABLE_CHECKING
755 timevar_pop (TV_TREE_CLEANUP_CFG
);
757 if (changed
&& current_loops
)
758 loops_state_set (LOOPS_NEED_FIXUP
);
763 /* Repairs loop structures. */
766 repair_loop_structures (void)
769 unsigned n_new_loops
;
771 calculate_dominance_info (CDI_DOMINATORS
);
773 timevar_push (TV_REPAIR_LOOPS
);
774 changed_bbs
= BITMAP_ALLOC (NULL
);
775 n_new_loops
= fix_loop_structure (changed_bbs
);
777 /* This usually does nothing. But sometimes parts of cfg that originally
778 were inside a loop get out of it due to edge removal (since they
779 become unreachable by back edges from latch). Also a former
780 irreducible loop can become reducible - in this case force a full
781 rewrite into loop-closed SSA form. */
782 if (loops_state_satisfies_p (LOOP_CLOSED_SSA
))
783 rewrite_into_loop_closed_ssa (n_new_loops
? NULL
: changed_bbs
,
786 BITMAP_FREE (changed_bbs
);
788 #ifdef ENABLE_CHECKING
789 verify_loop_structure ();
793 timevar_pop (TV_REPAIR_LOOPS
);
796 /* Cleanup cfg and repair loop structures. */
799 cleanup_tree_cfg (void)
801 bool changed
= cleanup_tree_cfg_noloop ();
803 if (current_loops
!= NULL
804 && loops_state_satisfies_p (LOOPS_NEED_FIXUP
))
805 repair_loop_structures ();
810 /* Tries to merge the PHI nodes at BB into those at BB's sole successor.
811 Returns true if successful. */
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 if (glabel
*label_stmt
= dyn_cast
<glabel
*> (label
))
832 if (DECL_NONLOCAL (gimple_label_label (label_stmt
)))
835 /* Record BB's single pred in case we need to update the father
836 loop's latch information later. */
837 basic_block pred
= NULL
;
838 if (single_pred_p (bb
))
839 pred
= single_pred (bb
);
841 /* Redirect each incoming edge to BB to DEST. */
842 while (EDGE_COUNT (bb
->preds
) > 0)
844 edge e
= EDGE_PRED (bb
, 0), s
;
847 s
= find_edge (e
->src
, dest
);
850 /* We already have an edge S from E->src to DEST. If S and
851 E->dest's sole successor edge have the same PHI arguments
852 at DEST, redirect S to DEST. */
853 if (phi_alternatives_equal (dest
, s
, succ
))
855 e
= redirect_edge_and_branch (e
, dest
);
856 redirect_edge_var_map_clear (e
);
860 /* PHI arguments are different. Create a forwarder block by
861 splitting E so that we can merge PHI arguments on E to
863 e
= single_succ_edge (split_edge (e
));
866 s
= redirect_edge_and_branch (e
, dest
);
868 /* redirect_edge_and_branch must not create a new edge. */
871 /* Add to the PHI nodes at DEST each PHI argument removed at the
873 for (gsi
= gsi_start_phis (dest
);
877 gphi
*phi
= gsi
.phi ();
878 tree def
= gimple_phi_arg_def (phi
, succ
->dest_idx
);
879 source_location locus
= gimple_phi_arg_location_from_edge (phi
, succ
);
881 if (TREE_CODE (def
) == SSA_NAME
)
883 /* If DEF is one of the results of PHI nodes removed during
884 redirection, replace it with the PHI argument that used
886 vec
<edge_var_map
> *head
= redirect_edge_var_map_vector (e
);
887 size_t length
= head
? head
->length () : 0;
888 for (size_t i
= 0; i
< length
; i
++)
890 edge_var_map
*vm
= &(*head
)[i
];
891 tree old_arg
= redirect_edge_var_map_result (vm
);
892 tree new_arg
= redirect_edge_var_map_def (vm
);
897 locus
= redirect_edge_var_map_location (vm
);
903 add_phi_arg (phi
, def
, s
, locus
);
906 redirect_edge_var_map_clear (e
);
909 /* Update the dominators. */
910 dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
911 domdest
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
914 /* Shortcut to avoid calling (relatively expensive)
915 nearest_common_dominator unless necessary. */
919 dom
= nearest_common_dominator (CDI_DOMINATORS
, domdest
, dombb
);
921 set_immediate_dominator (CDI_DOMINATORS
, dest
, dom
);
923 /* Adjust latch infomation of BB's parent loop as otherwise
924 the cfg hook has a hard time not to kill the loop. */
925 if (current_loops
&& bb
->loop_father
->latch
== bb
)
926 bb
->loop_father
->latch
= pred
;
928 /* Remove BB since all of BB's incoming edges have been redirected
930 delete_basic_block (bb
);
935 /* This pass merges PHI nodes if one feeds into another. For example,
936 suppose we have the following:
943 # tem_6 = PHI <tem_17(8), tem_23(7)>;
946 # tem_3 = PHI <tem_6(9), tem_2(5)>;
949 Then we merge the first PHI node into the second one like so:
956 # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
962 const pass_data pass_data_merge_phi
=
964 GIMPLE_PASS
, /* type */
965 "mergephi", /* name */
966 OPTGROUP_NONE
, /* optinfo_flags */
967 TV_TREE_MERGE_PHI
, /* tv_id */
968 ( PROP_cfg
| PROP_ssa
), /* properties_required */
969 0, /* properties_provided */
970 0, /* properties_destroyed */
971 0, /* todo_flags_start */
972 0, /* todo_flags_finish */
975 class pass_merge_phi
: public gimple_opt_pass
978 pass_merge_phi (gcc::context
*ctxt
)
979 : gimple_opt_pass (pass_data_merge_phi
, ctxt
)
982 /* opt_pass methods: */
983 opt_pass
* clone () { return new pass_merge_phi (m_ctxt
); }
984 virtual unsigned int execute (function
*);
986 }; // class pass_merge_phi
989 pass_merge_phi::execute (function
*fun
)
991 basic_block
*worklist
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (fun
));
992 basic_block
*current
= worklist
;
995 calculate_dominance_info (CDI_DOMINATORS
);
997 /* Find all PHI nodes that we may be able to merge. */
998 FOR_EACH_BB_FN (bb
, fun
)
1002 /* Look for a forwarder block with PHI nodes. */
1003 if (!tree_forwarder_block_p (bb
, true))
1006 dest
= single_succ (bb
);
1008 /* We have to feed into another basic block with PHI
1010 if (gimple_seq_empty_p (phi_nodes (dest
))
1011 /* We don't want to deal with a basic block with
1013 || bb_has_abnormal_pred (bb
))
1016 if (!dominated_by_p (CDI_DOMINATORS
, dest
, bb
))
1018 /* If BB does not dominate DEST, then the PHI nodes at
1019 DEST must be the only users of the results of the PHI
1026 unsigned int dest_idx
= single_succ_edge (bb
)->dest_idx
;
1028 /* BB dominates DEST. There may be many users of the PHI
1029 nodes in BB. However, there is still a trivial case we
1030 can handle. If the result of every PHI in BB is used
1031 only by a PHI in DEST, then we can trivially merge the
1032 PHI nodes from BB into DEST. */
1033 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
1036 gphi
*phi
= gsi
.phi ();
1037 tree result
= gimple_phi_result (phi
);
1038 use_operand_p imm_use
;
1041 /* If the PHI's result is never used, then we can just
1043 if (has_zero_uses (result
))
1046 /* Get the single use of the result of this PHI node. */
1047 if (!single_imm_use (result
, &imm_use
, &use_stmt
)
1048 || gimple_code (use_stmt
) != GIMPLE_PHI
1049 || gimple_bb (use_stmt
) != dest
1050 || gimple_phi_arg_def (use_stmt
, dest_idx
) != result
)
1054 /* If the loop above iterated through all the PHI nodes
1055 in BB, then we can merge the PHIs from BB into DEST. */
1056 if (gsi_end_p (gsi
))
1061 /* Now let's drain WORKLIST. */
1062 bool changed
= false;
1063 while (current
!= worklist
)
1066 changed
|= remove_forwarder_block_with_phi (bb
);
1070 /* Removing forwarder blocks can cause formerly irreducible loops
1071 to become reducible if we merged two entry blocks. */
1074 loops_state_set (LOOPS_NEED_FIXUP
);
1082 make_pass_merge_phi (gcc::context
*ctxt
)
1084 return new pass_merge_phi (ctxt
);
1087 /* Pass: cleanup the CFG just before expanding trees to RTL.
1088 This is just a round of label cleanups and case node grouping
1089 because after the tree optimizers have run such cleanups may
1093 execute_cleanup_cfg_post_optimizing (void)
1095 unsigned int todo
= execute_fixup_cfg ();
1096 if (cleanup_tree_cfg ())
1098 todo
&= ~TODO_cleanup_cfg
;
1099 todo
|= TODO_update_ssa
;
1101 maybe_remove_unreachable_handlers ();
1102 cleanup_dead_labels ();
1103 group_case_labels ();
1104 if ((flag_compare_debug_opt
|| flag_compare_debug
)
1105 && flag_dump_final_insns
)
1107 FILE *final_output
= fopen (flag_dump_final_insns
, "a");
1111 error ("could not open final insn dump file %qs: %m",
1112 flag_dump_final_insns
);
1113 flag_dump_final_insns
= NULL
;
1117 int save_unnumbered
= flag_dump_unnumbered
;
1118 int save_noaddr
= flag_dump_noaddr
;
1120 flag_dump_noaddr
= flag_dump_unnumbered
= 1;
1121 fprintf (final_output
, "\n");
1122 dump_enumerated_decls (final_output
, dump_flags
| TDF_NOUID
);
1123 flag_dump_noaddr
= save_noaddr
;
1124 flag_dump_unnumbered
= save_unnumbered
;
1125 if (fclose (final_output
))
1127 error ("could not close final insn dump file %qs: %m",
1128 flag_dump_final_insns
);
1129 flag_dump_final_insns
= NULL
;
1138 const pass_data pass_data_cleanup_cfg_post_optimizing
=
1140 GIMPLE_PASS
, /* type */
1141 "optimized", /* name */
1142 OPTGROUP_NONE
, /* optinfo_flags */
1143 TV_TREE_CLEANUP_CFG
, /* tv_id */
1144 PROP_cfg
, /* properties_required */
1145 0, /* properties_provided */
1146 0, /* properties_destroyed */
1147 0, /* todo_flags_start */
1148 TODO_remove_unused_locals
, /* todo_flags_finish */
1151 class pass_cleanup_cfg_post_optimizing
: public gimple_opt_pass
1154 pass_cleanup_cfg_post_optimizing (gcc::context
*ctxt
)
1155 : gimple_opt_pass (pass_data_cleanup_cfg_post_optimizing
, ctxt
)
1158 /* opt_pass methods: */
1159 virtual unsigned int execute (function
*)
1161 return execute_cleanup_cfg_post_optimizing ();
1164 }; // class pass_cleanup_cfg_post_optimizing
1169 make_pass_cleanup_cfg_post_optimizing (gcc::context
*ctxt
)
1171 return new pass_cleanup_cfg_post_optimizing (ctxt
);