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"
28 #include "fold-const.h"
31 #include "hard-reg-set.h"
33 #include "dominance.h"
36 #include "cfgcleanup.h"
37 #include "basic-block.h"
38 #include "diagnostic-core.h"
40 #include "langhooks.h"
41 #include "tree-ssa-alias.h"
42 #include "internal-fn.h"
44 #include "gimple-expr.h"
48 #include "gimple-iterator.h"
49 #include "gimple-ssa.h"
51 #include "tree-phinodes.h"
52 #include "ssa-iterators.h"
53 #include "stringpool.h"
54 #include "tree-ssanames.h"
55 #include "tree-ssa-loop-manip.h"
57 #include "insn-config.h"
68 #include "tree-pass.h"
71 #include "tree-ssa-propagate.h"
72 #include "tree-scalar-evolution.h"
74 /* The set of blocks in that at least one of the following changes happened:
75 -- the statement at the end of the block was changed
76 -- the block was newly created
77 -- the set of the predecessors of the block changed
78 -- the set of the successors of the block changed
79 ??? Maybe we could track these changes separately, since they determine
80 what cleanups it makes sense to try on the block. */
81 bitmap cfgcleanup_altered_bbs
;
83 /* Remove any fallthru edge from EV. Return true if an edge was removed. */
86 remove_fallthru_edge (vec
<edge
, va_gc
> *ev
)
91 FOR_EACH_EDGE (e
, ei
, ev
)
92 if ((e
->flags
& EDGE_FALLTHRU
) != 0)
94 if (e
->flags
& EDGE_COMPLEX
)
95 e
->flags
&= ~EDGE_FALLTHRU
;
97 remove_edge_and_dominated_blocks (e
);
104 /* Disconnect an unreachable block in the control expression starting
108 cleanup_control_expr_graph (basic_block bb
, gimple_stmt_iterator gsi
)
112 gimple stmt
= gsi_stmt (gsi
);
115 if (!single_succ_p (bb
))
122 fold_defer_overflow_warnings ();
123 loc
= gimple_location (stmt
);
124 switch (gimple_code (stmt
))
127 val
= fold_binary_loc (loc
, gimple_cond_code (stmt
),
129 gimple_cond_lhs (stmt
),
130 gimple_cond_rhs (stmt
));
134 val
= gimple_switch_index (as_a
<gswitch
*> (stmt
));
140 taken_edge
= find_taken_edge (bb
, val
);
143 fold_undefer_and_ignore_overflow_warnings ();
147 /* Remove all the edges except the one that is always executed. */
149 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
155 fold_undefer_overflow_warnings
156 (true, stmt
, WARN_STRICT_OVERFLOW_CONDITIONAL
);
160 taken_edge
->probability
+= e
->probability
;
161 taken_edge
->count
+= e
->count
;
162 remove_edge_and_dominated_blocks (e
);
169 fold_undefer_and_ignore_overflow_warnings ();
170 if (taken_edge
->probability
> REG_BR_PROB_BASE
)
171 taken_edge
->probability
= REG_BR_PROB_BASE
;
174 taken_edge
= single_succ_edge (bb
);
176 bitmap_set_bit (cfgcleanup_altered_bbs
, bb
->index
);
177 gsi_remove (&gsi
, true);
178 taken_edge
->flags
= EDGE_FALLTHRU
;
183 /* Cleanup the GF_CALL_CTRL_ALTERING flag according to
184 to updated gimple_call_flags. */
187 cleanup_call_ctrl_altering_flag (gimple bb_end
)
189 if (!is_gimple_call (bb_end
)
190 || !gimple_call_ctrl_altering_p (bb_end
))
193 int flags
= gimple_call_flags (bb_end
);
194 if (((flags
& (ECF_CONST
| ECF_PURE
))
195 && !(flags
& ECF_LOOPING_CONST_OR_PURE
))
196 || (flags
& ECF_LEAF
))
197 gimple_call_set_ctrl_altering (bb_end
, false);
200 /* Try to remove superfluous control structures in basic block BB. Returns
201 true if anything changes. */
204 cleanup_control_flow_bb (basic_block bb
)
206 gimple_stmt_iterator gsi
;
210 /* If the last statement of the block could throw and now cannot,
211 we need to prune cfg. */
212 retval
|= gimple_purge_dead_eh_edges (bb
);
214 gsi
= gsi_last_bb (bb
);
218 stmt
= gsi_stmt (gsi
);
220 /* Try to cleanup ctrl altering flag for call which ends bb. */
221 cleanup_call_ctrl_altering_flag (stmt
);
223 if (gimple_code (stmt
) == GIMPLE_COND
224 || gimple_code (stmt
) == GIMPLE_SWITCH
)
225 retval
|= cleanup_control_expr_graph (bb
, gsi
);
226 else if (gimple_code (stmt
) == GIMPLE_GOTO
227 && TREE_CODE (gimple_goto_dest (stmt
)) == ADDR_EXPR
228 && (TREE_CODE (TREE_OPERAND (gimple_goto_dest (stmt
), 0))
231 /* If we had a computed goto which has a compile-time determinable
232 destination, then we can eliminate the goto. */
236 basic_block target_block
;
238 /* First look at all the outgoing edges. Delete any outgoing
239 edges which do not go to the right block. For the one
240 edge which goes to the right block, fix up its flags. */
241 label
= TREE_OPERAND (gimple_goto_dest (stmt
), 0);
242 target_block
= label_to_block (label
);
243 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
245 if (e
->dest
!= target_block
)
246 remove_edge_and_dominated_blocks (e
);
249 /* Turn off the EDGE_ABNORMAL flag. */
250 e
->flags
&= ~EDGE_ABNORMAL
;
252 /* And set EDGE_FALLTHRU. */
253 e
->flags
|= EDGE_FALLTHRU
;
258 bitmap_set_bit (cfgcleanup_altered_bbs
, bb
->index
);
259 bitmap_set_bit (cfgcleanup_altered_bbs
, target_block
->index
);
261 /* Remove the GOTO_EXPR as it is not needed. The CFG has all the
262 relevant information we need. */
263 gsi_remove (&gsi
, true);
267 /* Check for indirect calls that have been turned into
269 else if (is_gimple_call (stmt
)
270 && gimple_call_noreturn_p (stmt
)
271 && remove_fallthru_edge (bb
->succs
))
277 /* Return true if basic block BB does nothing except pass control
278 flow to another block and that we can safely insert a label at
279 the start of the successor block.
281 As a precondition, we require that BB be not equal to
285 tree_forwarder_block_p (basic_block bb
, bool phi_wanted
)
287 gimple_stmt_iterator gsi
;
290 /* BB must have a single outgoing edge. */
291 if (single_succ_p (bb
) != 1
292 /* If PHI_WANTED is false, BB must not have any PHI nodes.
293 Otherwise, BB must have PHI nodes. */
294 || gimple_seq_empty_p (phi_nodes (bb
)) == phi_wanted
295 /* BB may not be a predecessor of the exit block. */
296 || single_succ (bb
) == EXIT_BLOCK_PTR_FOR_FN (cfun
)
297 /* Nor should this be an infinite loop. */
298 || single_succ (bb
) == bb
299 /* BB may not have an abnormal outgoing edge. */
300 || (single_succ_edge (bb
)->flags
& EDGE_ABNORMAL
))
303 gcc_checking_assert (bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
));
305 locus
= single_succ_edge (bb
)->goto_locus
;
307 /* There should not be an edge coming from entry, or an EH edge. */
312 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
313 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) || (e
->flags
& EDGE_EH
))
315 /* If goto_locus of any of the edges differs, prevent removing
316 the forwarder block for -O0. */
317 else if (optimize
== 0 && e
->goto_locus
!= locus
)
321 /* Now walk through the statements backward. We can ignore labels,
322 anything else means this is not a forwarder block. */
323 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
325 gimple stmt
= gsi_stmt (gsi
);
327 switch (gimple_code (stmt
))
330 if (DECL_NONLOCAL (gimple_label_label (as_a
<glabel
*> (stmt
))))
332 if (optimize
== 0 && gimple_location (stmt
) != locus
)
336 /* ??? For now, hope there's a corresponding debug
337 assignment at the destination. */
349 /* Protect loop headers. */
350 if (bb
->loop_father
->header
== bb
)
353 dest
= EDGE_SUCC (bb
, 0)->dest
;
354 /* Protect loop preheaders and latches if requested. */
355 if (dest
->loop_father
->header
== dest
)
357 if (bb
->loop_father
== dest
->loop_father
)
359 if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES
))
361 /* If bb doesn't have a single predecessor we'd make this
362 loop have multiple latches. Don't do that if that
363 would in turn require disambiguating them. */
364 return (single_pred_p (bb
)
365 || loops_state_satisfies_p
366 (LOOPS_MAY_HAVE_MULTIPLE_LATCHES
));
368 else if (bb
->loop_father
== loop_outer (dest
->loop_father
))
369 return !loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS
);
370 /* Always preserve other edges into loop headers that are
371 not simple latches or preheaders. */
379 /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
380 those alternatives are equal in each of the PHI nodes, then return
381 true, else return false. */
384 phi_alternatives_equal (basic_block dest
, edge e1
, edge e2
)
386 int n1
= e1
->dest_idx
;
387 int n2
= e2
->dest_idx
;
390 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
392 gphi
*phi
= gsi
.phi ();
393 tree val1
= gimple_phi_arg_def (phi
, n1
);
394 tree val2
= gimple_phi_arg_def (phi
, n2
);
396 gcc_assert (val1
!= NULL_TREE
);
397 gcc_assert (val2
!= NULL_TREE
);
399 if (!operand_equal_for_phi_arg_p (val1
, val2
))
406 /* Removes forwarder block BB. Returns false if this failed. */
409 remove_forwarder_block (basic_block bb
)
411 edge succ
= single_succ_edge (bb
), e
, s
;
412 basic_block dest
= succ
->dest
;
415 gimple_stmt_iterator gsi
, gsi_to
;
416 bool can_move_debug_stmts
;
418 /* We check for infinite loops already in tree_forwarder_block_p.
419 However it may happen that the infinite loop is created
420 afterwards due to removal of forwarders. */
424 /* If the destination block consists of a nonlocal label or is a
425 EH landing pad, do not merge it. */
426 label
= first_stmt (dest
);
428 if (glabel
*label_stmt
= dyn_cast
<glabel
*> (label
))
429 if (DECL_NONLOCAL (gimple_label_label (label_stmt
))
430 || EH_LANDING_PAD_NR (gimple_label_label (label_stmt
)) != 0)
433 /* If there is an abnormal edge to basic block BB, but not into
434 dest, problems might occur during removal of the phi node at out
435 of ssa due to overlapping live ranges of registers.
437 If there is an abnormal edge in DEST, the problems would occur
438 anyway since cleanup_dead_labels would then merge the labels for
439 two different eh regions, and rest of exception handling code
442 So if there is an abnormal edge to BB, proceed only if there is
443 no abnormal edge to DEST and there are no phi nodes in DEST. */
444 if (bb_has_abnormal_pred (bb
)
445 && (bb_has_abnormal_pred (dest
)
446 || !gimple_seq_empty_p (phi_nodes (dest
))))
449 /* If there are phi nodes in DEST, and some of the blocks that are
450 predecessors of BB are also predecessors of DEST, check that the
451 phi node arguments match. */
452 if (!gimple_seq_empty_p (phi_nodes (dest
)))
454 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
456 s
= find_edge (e
->src
, dest
);
460 if (!phi_alternatives_equal (dest
, succ
, s
))
465 can_move_debug_stmts
= MAY_HAVE_DEBUG_STMTS
&& single_pred_p (dest
);
467 basic_block pred
= NULL
;
468 if (single_pred_p (bb
))
469 pred
= single_pred (bb
);
471 /* Redirect the edges. */
472 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
474 bitmap_set_bit (cfgcleanup_altered_bbs
, e
->src
->index
);
476 if (e
->flags
& EDGE_ABNORMAL
)
478 /* If there is an abnormal edge, redirect it anyway, and
479 move the labels to the new block to make it legal. */
480 s
= redirect_edge_succ_nodup (e
, dest
);
483 s
= redirect_edge_and_branch (e
, dest
);
487 /* Create arguments for the phi nodes, since the edge was not
489 for (gphi_iterator psi
= gsi_start_phis (dest
);
493 gphi
*phi
= psi
.phi ();
494 source_location l
= gimple_phi_arg_location_from_edge (phi
, succ
);
495 tree def
= gimple_phi_arg_def (phi
, succ
->dest_idx
);
496 add_phi_arg (phi
, unshare_expr (def
), s
, l
);
501 /* Move nonlocal labels and computed goto targets as well as user
502 defined labels and labels with an EH landing pad number to the
503 new block, so that the redirection of the abnormal edges works,
504 jump targets end up in a sane place and debug information for
505 labels is retained. */
506 gsi_to
= gsi_start_bb (dest
);
507 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
510 label
= gsi_stmt (gsi
);
511 if (is_gimple_debug (label
))
513 decl
= gimple_label_label (as_a
<glabel
*> (label
));
514 if (EH_LANDING_PAD_NR (decl
) != 0
515 || DECL_NONLOCAL (decl
)
516 || FORCED_LABEL (decl
)
517 || !DECL_ARTIFICIAL (decl
))
519 gsi_remove (&gsi
, false);
520 gsi_insert_before (&gsi_to
, label
, GSI_SAME_STMT
);
526 /* Move debug statements if the destination has a single predecessor. */
527 if (can_move_debug_stmts
)
529 gsi_to
= gsi_after_labels (dest
);
530 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); )
532 gimple debug
= gsi_stmt (gsi
);
533 if (!is_gimple_debug (debug
))
535 gsi_remove (&gsi
, false);
536 gsi_insert_before (&gsi_to
, debug
, GSI_SAME_STMT
);
540 bitmap_set_bit (cfgcleanup_altered_bbs
, dest
->index
);
542 /* Update the dominators. */
543 if (dom_info_available_p (CDI_DOMINATORS
))
545 basic_block dom
, dombb
, domdest
;
547 dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
548 domdest
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
551 /* Shortcut to avoid calling (relatively expensive)
552 nearest_common_dominator unless necessary. */
556 dom
= nearest_common_dominator (CDI_DOMINATORS
, domdest
, dombb
);
558 set_immediate_dominator (CDI_DOMINATORS
, dest
, dom
);
561 /* Adjust latch infomation of BB's parent loop as otherwise
562 the cfg hook has a hard time not to kill the loop. */
563 if (current_loops
&& bb
->loop_father
->latch
== bb
)
564 bb
->loop_father
->latch
= pred
;
566 /* And kill the forwarder block. */
567 delete_basic_block (bb
);
572 /* STMT is a call that has been discovered noreturn. Split the
573 block to prepare fixing up the CFG and remove LHS.
574 Return true if cleanup-cfg needs to run. */
577 fixup_noreturn_call (gimple stmt
)
579 basic_block bb
= gimple_bb (stmt
);
580 bool changed
= false;
582 if (gimple_call_builtin_p (stmt
, BUILT_IN_RETURN
))
585 /* First split basic block if stmt is not last. */
586 if (stmt
!= gsi_stmt (gsi_last_bb (bb
)))
588 if (stmt
== gsi_stmt (gsi_last_nondebug_bb (bb
)))
590 /* Don't split if there are only debug stmts
591 after stmt, that can result in -fcompare-debug
592 failures. Remove the debug stmts instead,
593 they should be all unreachable anyway. */
594 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
595 for (gsi_next (&gsi
); !gsi_end_p (gsi
); )
596 gsi_remove (&gsi
, true);
600 split_block (bb
, stmt
);
605 /* If there is an LHS, remove it, but only if its type has fixed size.
606 The LHS will need to be recreated during RTL expansion and creating
607 temporaries of variable-sized types is not supported. */
608 tree lhs
= gimple_call_lhs (stmt
);
609 if (lhs
&& TREE_CODE (TYPE_SIZE_UNIT (TREE_TYPE (lhs
))) == INTEGER_CST
)
611 gimple_call_set_lhs (stmt
, NULL_TREE
);
613 /* We need to fix up the SSA name to avoid checking errors. */
614 if (TREE_CODE (lhs
) == SSA_NAME
)
616 tree new_var
= create_tmp_reg (TREE_TYPE (lhs
));
617 SET_SSA_NAME_VAR_OR_IDENTIFIER (lhs
, new_var
);
618 SSA_NAME_DEF_STMT (lhs
) = gimple_build_nop ();
619 set_ssa_default_def (cfun
, new_var
, lhs
);
625 /* Mark the call as altering control flow. */
626 if (!gimple_call_ctrl_altering_p (stmt
))
628 gimple_call_set_ctrl_altering (stmt
, true);
636 /* Tries to cleanup cfg in basic block BB. Returns true if anything
640 cleanup_tree_cfg_bb (basic_block bb
)
642 bool retval
= cleanup_control_flow_bb (bb
);
644 if (tree_forwarder_block_p (bb
, false)
645 && remove_forwarder_block (bb
))
648 /* Merging the blocks may create new opportunities for folding
649 conditional branches (due to the elimination of single-valued PHI
651 if (single_succ_p (bb
)
652 && can_merge_blocks_p (bb
, single_succ (bb
)))
654 /* If there is a merge opportunity with the predecessor
655 do nothing now but wait until we process the predecessor.
656 This happens when we visit BBs in a non-optimal order and
657 avoids quadratic behavior with adjusting stmts BB pointer. */
658 if (single_pred_p (bb
)
659 && can_merge_blocks_p (single_pred (bb
), bb
))
663 merge_blocks (bb
, single_succ (bb
));
671 /* Iterate the cfg cleanups, while anything changes. */
674 cleanup_tree_cfg_1 (void)
680 /* Prepare the worklists of altered blocks. */
681 cfgcleanup_altered_bbs
= BITMAP_ALLOC (NULL
);
683 /* During forwarder block cleanup, we may redirect edges out of
684 SWITCH_EXPRs, which can get expensive. So we want to enable
685 recording of edge to CASE_LABEL_EXPR. */
686 start_recording_case_labels ();
688 /* Start by iterating over all basic blocks. We cannot use FOR_EACH_BB_FN,
689 since the basic blocks may get removed. */
690 n
= last_basic_block_for_fn (cfun
);
691 for (i
= NUM_FIXED_BLOCKS
; i
< n
; i
++)
693 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
695 retval
|= cleanup_tree_cfg_bb (bb
);
698 /* Now process the altered blocks, as long as any are available. */
699 while (!bitmap_empty_p (cfgcleanup_altered_bbs
))
701 i
= bitmap_first_set_bit (cfgcleanup_altered_bbs
);
702 bitmap_clear_bit (cfgcleanup_altered_bbs
, i
);
703 if (i
< NUM_FIXED_BLOCKS
)
706 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
710 retval
|= cleanup_tree_cfg_bb (bb
);
713 end_recording_case_labels ();
714 BITMAP_FREE (cfgcleanup_altered_bbs
);
719 /* Remove unreachable blocks and other miscellaneous clean up work.
720 Return true if the flowgraph was modified, false otherwise. */
723 cleanup_tree_cfg_noloop (void)
727 timevar_push (TV_TREE_CLEANUP_CFG
);
729 /* Iterate until there are no more cleanups left to do. If any
730 iteration changed the flowgraph, set CHANGED to true.
732 If dominance information is available, there cannot be any unreachable
734 if (!dom_info_available_p (CDI_DOMINATORS
))
736 changed
= delete_unreachable_blocks ();
737 calculate_dominance_info (CDI_DOMINATORS
);
741 #ifdef ENABLE_CHECKING
742 verify_dominators (CDI_DOMINATORS
);
747 changed
|= cleanup_tree_cfg_1 ();
749 gcc_assert (dom_info_available_p (CDI_DOMINATORS
));
752 #ifdef ENABLE_CHECKING
756 timevar_pop (TV_TREE_CLEANUP_CFG
);
758 if (changed
&& current_loops
)
759 loops_state_set (LOOPS_NEED_FIXUP
);
764 /* Repairs loop structures. */
767 repair_loop_structures (void)
770 unsigned n_new_loops
;
772 calculate_dominance_info (CDI_DOMINATORS
);
774 timevar_push (TV_REPAIR_LOOPS
);
775 changed_bbs
= BITMAP_ALLOC (NULL
);
776 n_new_loops
= fix_loop_structure (changed_bbs
);
778 /* This usually does nothing. But sometimes parts of cfg that originally
779 were inside a loop get out of it due to edge removal (since they
780 become unreachable by back edges from latch). Also a former
781 irreducible loop can become reducible - in this case force a full
782 rewrite into loop-closed SSA form. */
783 if (loops_state_satisfies_p (LOOP_CLOSED_SSA
))
784 rewrite_into_loop_closed_ssa (n_new_loops
? NULL
: changed_bbs
,
787 BITMAP_FREE (changed_bbs
);
789 #ifdef ENABLE_CHECKING
790 verify_loop_structure ();
794 timevar_pop (TV_REPAIR_LOOPS
);
797 /* Cleanup cfg and repair loop structures. */
800 cleanup_tree_cfg (void)
802 bool changed
= cleanup_tree_cfg_noloop ();
804 if (current_loops
!= NULL
805 && loops_state_satisfies_p (LOOPS_NEED_FIXUP
))
806 repair_loop_structures ();
811 /* Tries to merge the PHI nodes at BB into those at BB's sole successor.
812 Returns true if successful. */
815 remove_forwarder_block_with_phi (basic_block bb
)
817 edge succ
= single_succ_edge (bb
);
818 basic_block dest
= succ
->dest
;
820 basic_block dombb
, domdest
, dom
;
822 /* We check for infinite loops already in tree_forwarder_block_p.
823 However it may happen that the infinite loop is created
824 afterwards due to removal of forwarders. */
828 /* If the destination block consists of a nonlocal label, do not
830 label
= first_stmt (dest
);
832 if (glabel
*label_stmt
= dyn_cast
<glabel
*> (label
))
833 if (DECL_NONLOCAL (gimple_label_label (label_stmt
)))
836 /* Record BB's single pred in case we need to update the father
837 loop's latch information later. */
838 basic_block pred
= NULL
;
839 if (single_pred_p (bb
))
840 pred
= single_pred (bb
);
842 /* Redirect each incoming edge to BB to DEST. */
843 while (EDGE_COUNT (bb
->preds
) > 0)
845 edge e
= EDGE_PRED (bb
, 0), s
;
848 s
= find_edge (e
->src
, dest
);
851 /* We already have an edge S from E->src to DEST. If S and
852 E->dest's sole successor edge have the same PHI arguments
853 at DEST, redirect S to DEST. */
854 if (phi_alternatives_equal (dest
, s
, succ
))
856 e
= redirect_edge_and_branch (e
, dest
);
857 redirect_edge_var_map_clear (e
);
861 /* PHI arguments are different. Create a forwarder block by
862 splitting E so that we can merge PHI arguments on E to
864 e
= single_succ_edge (split_edge (e
));
867 s
= redirect_edge_and_branch (e
, dest
);
869 /* redirect_edge_and_branch must not create a new edge. */
872 /* Add to the PHI nodes at DEST each PHI argument removed at the
874 for (gsi
= gsi_start_phis (dest
);
878 gphi
*phi
= gsi
.phi ();
879 tree def
= gimple_phi_arg_def (phi
, succ
->dest_idx
);
880 source_location locus
= gimple_phi_arg_location_from_edge (phi
, succ
);
882 if (TREE_CODE (def
) == SSA_NAME
)
884 /* If DEF is one of the results of PHI nodes removed during
885 redirection, replace it with the PHI argument that used
887 vec
<edge_var_map
> *head
= redirect_edge_var_map_vector (e
);
888 size_t length
= head
? head
->length () : 0;
889 for (size_t i
= 0; i
< length
; i
++)
891 edge_var_map
*vm
= &(*head
)[i
];
892 tree old_arg
= redirect_edge_var_map_result (vm
);
893 tree new_arg
= redirect_edge_var_map_def (vm
);
898 locus
= redirect_edge_var_map_location (vm
);
904 add_phi_arg (phi
, def
, s
, locus
);
907 redirect_edge_var_map_clear (e
);
910 /* Update the dominators. */
911 dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
912 domdest
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
915 /* Shortcut to avoid calling (relatively expensive)
916 nearest_common_dominator unless necessary. */
920 dom
= nearest_common_dominator (CDI_DOMINATORS
, domdest
, dombb
);
922 set_immediate_dominator (CDI_DOMINATORS
, dest
, dom
);
924 /* Adjust latch infomation of BB's parent loop as otherwise
925 the cfg hook has a hard time not to kill the loop. */
926 if (current_loops
&& bb
->loop_father
->latch
== bb
)
927 bb
->loop_father
->latch
= pred
;
929 /* Remove BB since all of BB's incoming edges have been redirected
931 delete_basic_block (bb
);
936 /* This pass merges PHI nodes if one feeds into another. For example,
937 suppose we have the following:
944 # tem_6 = PHI <tem_17(8), tem_23(7)>;
947 # tem_3 = PHI <tem_6(9), tem_2(5)>;
950 Then we merge the first PHI node into the second one like so:
957 # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
963 const pass_data pass_data_merge_phi
=
965 GIMPLE_PASS
, /* type */
966 "mergephi", /* name */
967 OPTGROUP_NONE
, /* optinfo_flags */
968 TV_TREE_MERGE_PHI
, /* tv_id */
969 ( PROP_cfg
| PROP_ssa
), /* properties_required */
970 0, /* properties_provided */
971 0, /* properties_destroyed */
972 0, /* todo_flags_start */
973 0, /* todo_flags_finish */
976 class pass_merge_phi
: public gimple_opt_pass
979 pass_merge_phi (gcc::context
*ctxt
)
980 : gimple_opt_pass (pass_data_merge_phi
, ctxt
)
983 /* opt_pass methods: */
984 opt_pass
* clone () { return new pass_merge_phi (m_ctxt
); }
985 virtual unsigned int execute (function
*);
987 }; // class pass_merge_phi
990 pass_merge_phi::execute (function
*fun
)
992 basic_block
*worklist
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (fun
));
993 basic_block
*current
= worklist
;
996 calculate_dominance_info (CDI_DOMINATORS
);
998 /* Find all PHI nodes that we may be able to merge. */
999 FOR_EACH_BB_FN (bb
, fun
)
1003 /* Look for a forwarder block with PHI nodes. */
1004 if (!tree_forwarder_block_p (bb
, true))
1007 dest
= single_succ (bb
);
1009 /* We have to feed into another basic block with PHI
1011 if (gimple_seq_empty_p (phi_nodes (dest
))
1012 /* We don't want to deal with a basic block with
1014 || bb_has_abnormal_pred (bb
))
1017 if (!dominated_by_p (CDI_DOMINATORS
, dest
, bb
))
1019 /* If BB does not dominate DEST, then the PHI nodes at
1020 DEST must be the only users of the results of the PHI
1027 unsigned int dest_idx
= single_succ_edge (bb
)->dest_idx
;
1029 /* BB dominates DEST. There may be many users of the PHI
1030 nodes in BB. However, there is still a trivial case we
1031 can handle. If the result of every PHI in BB is used
1032 only by a PHI in DEST, then we can trivially merge the
1033 PHI nodes from BB into DEST. */
1034 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
1037 gphi
*phi
= gsi
.phi ();
1038 tree result
= gimple_phi_result (phi
);
1039 use_operand_p imm_use
;
1042 /* If the PHI's result is never used, then we can just
1044 if (has_zero_uses (result
))
1047 /* Get the single use of the result of this PHI node. */
1048 if (!single_imm_use (result
, &imm_use
, &use_stmt
)
1049 || gimple_code (use_stmt
) != GIMPLE_PHI
1050 || gimple_bb (use_stmt
) != dest
1051 || gimple_phi_arg_def (use_stmt
, dest_idx
) != result
)
1055 /* If the loop above iterated through all the PHI nodes
1056 in BB, then we can merge the PHIs from BB into DEST. */
1057 if (gsi_end_p (gsi
))
1062 /* Now let's drain WORKLIST. */
1063 bool changed
= false;
1064 while (current
!= worklist
)
1067 changed
|= remove_forwarder_block_with_phi (bb
);
1071 /* Removing forwarder blocks can cause formerly irreducible loops
1072 to become reducible if we merged two entry blocks. */
1075 loops_state_set (LOOPS_NEED_FIXUP
);
1083 make_pass_merge_phi (gcc::context
*ctxt
)
1085 return new pass_merge_phi (ctxt
);
1088 /* Pass: cleanup the CFG just before expanding trees to RTL.
1089 This is just a round of label cleanups and case node grouping
1090 because after the tree optimizers have run such cleanups may
1094 execute_cleanup_cfg_post_optimizing (void)
1096 unsigned int todo
= execute_fixup_cfg ();
1097 if (cleanup_tree_cfg ())
1099 todo
&= ~TODO_cleanup_cfg
;
1100 todo
|= TODO_update_ssa
;
1102 maybe_remove_unreachable_handlers ();
1103 cleanup_dead_labels ();
1104 group_case_labels ();
1105 if ((flag_compare_debug_opt
|| flag_compare_debug
)
1106 && flag_dump_final_insns
)
1108 FILE *final_output
= fopen (flag_dump_final_insns
, "a");
1112 error ("could not open final insn dump file %qs: %m",
1113 flag_dump_final_insns
);
1114 flag_dump_final_insns
= NULL
;
1118 int save_unnumbered
= flag_dump_unnumbered
;
1119 int save_noaddr
= flag_dump_noaddr
;
1121 flag_dump_noaddr
= flag_dump_unnumbered
= 1;
1122 fprintf (final_output
, "\n");
1123 dump_enumerated_decls (final_output
, dump_flags
| TDF_NOUID
);
1124 flag_dump_noaddr
= save_noaddr
;
1125 flag_dump_unnumbered
= save_unnumbered
;
1126 if (fclose (final_output
))
1128 error ("could not close final insn dump file %qs: %m",
1129 flag_dump_final_insns
);
1130 flag_dump_final_insns
= NULL
;
1139 const pass_data pass_data_cleanup_cfg_post_optimizing
=
1141 GIMPLE_PASS
, /* type */
1142 "optimized", /* name */
1143 OPTGROUP_NONE
, /* optinfo_flags */
1144 TV_TREE_CLEANUP_CFG
, /* tv_id */
1145 PROP_cfg
, /* properties_required */
1146 0, /* properties_provided */
1147 0, /* properties_destroyed */
1148 0, /* todo_flags_start */
1149 TODO_remove_unused_locals
, /* todo_flags_finish */
1152 class pass_cleanup_cfg_post_optimizing
: public gimple_opt_pass
1155 pass_cleanup_cfg_post_optimizing (gcc::context
*ctxt
)
1156 : gimple_opt_pass (pass_data_cleanup_cfg_post_optimizing
, ctxt
)
1159 /* opt_pass methods: */
1160 virtual unsigned int execute (function
*)
1162 return execute_cleanup_cfg_post_optimizing ();
1165 }; // class pass_cleanup_cfg_post_optimizing
1170 make_pass_cleanup_cfg_post_optimizing (gcc::context
*ctxt
)
1172 return new pass_cleanup_cfg_post_optimizing (ctxt
);