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"
30 #include "fold-const.h"
33 #include "cfgcleanup.h"
34 #include "diagnostic-core.h"
36 #include "langhooks.h"
37 #include "internal-fn.h"
40 #include "gimple-iterator.h"
42 #include "tree-ssa-loop-manip.h"
43 #include "insn-config.h"
54 #include "tree-pass.h"
57 #include "tree-ssa-propagate.h"
58 #include "tree-scalar-evolution.h"
59 #include "gimple-match.h"
60 #include "gimple-fold.h"
63 /* The set of blocks in that at least one of the following changes happened:
64 -- the statement at the end of the block was changed
65 -- the block was newly created
66 -- the set of the predecessors of the block changed
67 -- the set of the successors of the block changed
68 ??? Maybe we could track these changes separately, since they determine
69 what cleanups it makes sense to try on the block. */
70 bitmap cfgcleanup_altered_bbs
;
72 /* Remove any fallthru edge from EV. Return true if an edge was removed. */
75 remove_fallthru_edge (vec
<edge
, va_gc
> *ev
)
80 FOR_EACH_EDGE (e
, ei
, ev
)
81 if ((e
->flags
& EDGE_FALLTHRU
) != 0)
83 if (e
->flags
& EDGE_COMPLEX
)
84 e
->flags
&= ~EDGE_FALLTHRU
;
86 remove_edge_and_dominated_blocks (e
);
93 /* Disconnect an unreachable block in the control expression starting
97 cleanup_control_expr_graph (basic_block bb
, gimple_stmt_iterator gsi
)
101 gimple
*stmt
= gsi_stmt (gsi
);
103 if (!single_succ_p (bb
))
108 tree val
= NULL_TREE
;
110 fold_defer_overflow_warnings ();
111 switch (gimple_code (stmt
))
117 if (gimple_simplify (stmt
, &rcode
, ops
, NULL
, no_follow_ssa_edges
,
119 && rcode
== INTEGER_CST
)
125 val
= gimple_switch_index (as_a
<gswitch
*> (stmt
));
131 taken_edge
= find_taken_edge (bb
, val
);
134 fold_undefer_and_ignore_overflow_warnings ();
138 /* Remove all the edges except the one that is always executed. */
140 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
146 fold_undefer_overflow_warnings
147 (true, stmt
, WARN_STRICT_OVERFLOW_CONDITIONAL
);
151 taken_edge
->probability
+= e
->probability
;
152 taken_edge
->count
+= e
->count
;
153 remove_edge_and_dominated_blocks (e
);
160 fold_undefer_and_ignore_overflow_warnings ();
161 if (taken_edge
->probability
> REG_BR_PROB_BASE
)
162 taken_edge
->probability
= REG_BR_PROB_BASE
;
165 taken_edge
= single_succ_edge (bb
);
167 bitmap_set_bit (cfgcleanup_altered_bbs
, bb
->index
);
168 gsi_remove (&gsi
, true);
169 taken_edge
->flags
= EDGE_FALLTHRU
;
174 /* Cleanup the GF_CALL_CTRL_ALTERING flag according to
175 to updated gimple_call_flags. */
178 cleanup_call_ctrl_altering_flag (gimple
*bb_end
)
180 if (!is_gimple_call (bb_end
)
181 || !gimple_call_ctrl_altering_p (bb_end
))
184 int flags
= gimple_call_flags (bb_end
);
185 if (((flags
& (ECF_CONST
| ECF_PURE
))
186 && !(flags
& ECF_LOOPING_CONST_OR_PURE
))
187 || (flags
& ECF_LEAF
))
188 gimple_call_set_ctrl_altering (bb_end
, false);
191 /* Try to remove superfluous control structures in basic block BB. Returns
192 true if anything changes. */
195 cleanup_control_flow_bb (basic_block bb
)
197 gimple_stmt_iterator gsi
;
201 /* If the last statement of the block could throw and now cannot,
202 we need to prune cfg. */
203 retval
|= gimple_purge_dead_eh_edges (bb
);
205 gsi
= gsi_last_bb (bb
);
209 stmt
= gsi_stmt (gsi
);
211 /* Try to cleanup ctrl altering flag for call which ends bb. */
212 cleanup_call_ctrl_altering_flag (stmt
);
214 if (gimple_code (stmt
) == GIMPLE_COND
215 || gimple_code (stmt
) == GIMPLE_SWITCH
)
216 retval
|= cleanup_control_expr_graph (bb
, gsi
);
217 else if (gimple_code (stmt
) == GIMPLE_GOTO
218 && TREE_CODE (gimple_goto_dest (stmt
)) == ADDR_EXPR
219 && (TREE_CODE (TREE_OPERAND (gimple_goto_dest (stmt
), 0))
222 /* If we had a computed goto which has a compile-time determinable
223 destination, then we can eliminate the goto. */
227 basic_block target_block
;
229 /* First look at all the outgoing edges. Delete any outgoing
230 edges which do not go to the right block. For the one
231 edge which goes to the right block, fix up its flags. */
232 label
= TREE_OPERAND (gimple_goto_dest (stmt
), 0);
233 target_block
= label_to_block (label
);
234 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
236 if (e
->dest
!= target_block
)
237 remove_edge_and_dominated_blocks (e
);
240 /* Turn off the EDGE_ABNORMAL flag. */
241 e
->flags
&= ~EDGE_ABNORMAL
;
243 /* And set EDGE_FALLTHRU. */
244 e
->flags
|= EDGE_FALLTHRU
;
249 bitmap_set_bit (cfgcleanup_altered_bbs
, bb
->index
);
250 bitmap_set_bit (cfgcleanup_altered_bbs
, target_block
->index
);
252 /* Remove the GOTO_EXPR as it is not needed. The CFG has all the
253 relevant information we need. */
254 gsi_remove (&gsi
, true);
258 /* Check for indirect calls that have been turned into
260 else if (is_gimple_call (stmt
)
261 && gimple_call_noreturn_p (stmt
)
262 && remove_fallthru_edge (bb
->succs
))
268 /* Return true if basic block BB does nothing except pass control
269 flow to another block and that we can safely insert a label at
270 the start of the successor block.
272 As a precondition, we require that BB be not equal to
276 tree_forwarder_block_p (basic_block bb
, bool phi_wanted
)
278 gimple_stmt_iterator gsi
;
281 /* BB must have a single outgoing edge. */
282 if (single_succ_p (bb
) != 1
283 /* If PHI_WANTED is false, BB must not have any PHI nodes.
284 Otherwise, BB must have PHI nodes. */
285 || gimple_seq_empty_p (phi_nodes (bb
)) == phi_wanted
286 /* BB may not be a predecessor of the exit block. */
287 || single_succ (bb
) == EXIT_BLOCK_PTR_FOR_FN (cfun
)
288 /* Nor should this be an infinite loop. */
289 || single_succ (bb
) == bb
290 /* BB may not have an abnormal outgoing edge. */
291 || (single_succ_edge (bb
)->flags
& EDGE_ABNORMAL
))
294 gcc_checking_assert (bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
));
296 locus
= single_succ_edge (bb
)->goto_locus
;
298 /* There should not be an edge coming from entry, or an EH edge. */
303 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
304 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) || (e
->flags
& EDGE_EH
))
306 /* If goto_locus of any of the edges differs, prevent removing
307 the forwarder block for -O0. */
308 else if (optimize
== 0 && e
->goto_locus
!= locus
)
312 /* Now walk through the statements backward. We can ignore labels,
313 anything else means this is not a forwarder block. */
314 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
316 gimple
*stmt
= gsi_stmt (gsi
);
318 switch (gimple_code (stmt
))
321 if (DECL_NONLOCAL (gimple_label_label (as_a
<glabel
*> (stmt
))))
323 if (optimize
== 0 && gimple_location (stmt
) != locus
)
327 /* ??? For now, hope there's a corresponding debug
328 assignment at the destination. */
340 /* Protect loop headers. */
341 if (bb
->loop_father
->header
== bb
)
344 dest
= EDGE_SUCC (bb
, 0)->dest
;
345 /* Protect loop preheaders and latches if requested. */
346 if (dest
->loop_father
->header
== dest
)
348 if (bb
->loop_father
== dest
->loop_father
)
350 if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES
))
352 /* If bb doesn't have a single predecessor we'd make this
353 loop have multiple latches. Don't do that if that
354 would in turn require disambiguating them. */
355 return (single_pred_p (bb
)
356 || loops_state_satisfies_p
357 (LOOPS_MAY_HAVE_MULTIPLE_LATCHES
));
359 else if (bb
->loop_father
== loop_outer (dest
->loop_father
))
360 return !loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS
);
361 /* Always preserve other edges into loop headers that are
362 not simple latches or preheaders. */
370 /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
371 those alternatives are equal in each of the PHI nodes, then return
372 true, else return false. */
375 phi_alternatives_equal (basic_block dest
, edge e1
, edge e2
)
377 int n1
= e1
->dest_idx
;
378 int n2
= e2
->dest_idx
;
381 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
383 gphi
*phi
= gsi
.phi ();
384 tree val1
= gimple_phi_arg_def (phi
, n1
);
385 tree val2
= gimple_phi_arg_def (phi
, n2
);
387 gcc_assert (val1
!= NULL_TREE
);
388 gcc_assert (val2
!= NULL_TREE
);
390 if (!operand_equal_for_phi_arg_p (val1
, val2
))
397 /* Removes forwarder block BB. Returns false if this failed. */
400 remove_forwarder_block (basic_block bb
)
402 edge succ
= single_succ_edge (bb
), e
, s
;
403 basic_block dest
= succ
->dest
;
406 gimple_stmt_iterator gsi
, gsi_to
;
407 bool can_move_debug_stmts
;
409 /* We check for infinite loops already in tree_forwarder_block_p.
410 However it may happen that the infinite loop is created
411 afterwards due to removal of forwarders. */
415 /* If the destination block consists of a nonlocal label or is a
416 EH landing pad, do not merge it. */
417 label
= first_stmt (dest
);
419 if (glabel
*label_stmt
= dyn_cast
<glabel
*> (label
))
420 if (DECL_NONLOCAL (gimple_label_label (label_stmt
))
421 || EH_LANDING_PAD_NR (gimple_label_label (label_stmt
)) != 0)
424 /* If there is an abnormal edge to basic block BB, but not into
425 dest, problems might occur during removal of the phi node at out
426 of ssa due to overlapping live ranges of registers.
428 If there is an abnormal edge in DEST, the problems would occur
429 anyway since cleanup_dead_labels would then merge the labels for
430 two different eh regions, and rest of exception handling code
433 So if there is an abnormal edge to BB, proceed only if there is
434 no abnormal edge to DEST and there are no phi nodes in DEST. */
435 if (bb_has_abnormal_pred (bb
)
436 && (bb_has_abnormal_pred (dest
)
437 || !gimple_seq_empty_p (phi_nodes (dest
))))
440 /* If there are phi nodes in DEST, and some of the blocks that are
441 predecessors of BB are also predecessors of DEST, check that the
442 phi node arguments match. */
443 if (!gimple_seq_empty_p (phi_nodes (dest
)))
445 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
447 s
= find_edge (e
->src
, dest
);
451 if (!phi_alternatives_equal (dest
, succ
, s
))
456 can_move_debug_stmts
= MAY_HAVE_DEBUG_STMTS
&& single_pred_p (dest
);
458 basic_block pred
= NULL
;
459 if (single_pred_p (bb
))
460 pred
= single_pred (bb
);
462 /* Redirect the edges. */
463 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
465 bitmap_set_bit (cfgcleanup_altered_bbs
, e
->src
->index
);
467 if (e
->flags
& EDGE_ABNORMAL
)
469 /* If there is an abnormal edge, redirect it anyway, and
470 move the labels to the new block to make it legal. */
471 s
= redirect_edge_succ_nodup (e
, dest
);
474 s
= redirect_edge_and_branch (e
, dest
);
478 /* Create arguments for the phi nodes, since the edge was not
480 for (gphi_iterator psi
= gsi_start_phis (dest
);
484 gphi
*phi
= psi
.phi ();
485 source_location l
= gimple_phi_arg_location_from_edge (phi
, succ
);
486 tree def
= gimple_phi_arg_def (phi
, succ
->dest_idx
);
487 add_phi_arg (phi
, unshare_expr (def
), s
, l
);
492 /* Move nonlocal labels and computed goto targets as well as user
493 defined labels and labels with an EH landing pad number to the
494 new block, so that the redirection of the abnormal edges works,
495 jump targets end up in a sane place and debug information for
496 labels is retained. */
497 gsi_to
= gsi_start_bb (dest
);
498 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
501 label
= gsi_stmt (gsi
);
502 if (is_gimple_debug (label
))
504 decl
= gimple_label_label (as_a
<glabel
*> (label
));
505 if (EH_LANDING_PAD_NR (decl
) != 0
506 || DECL_NONLOCAL (decl
)
507 || FORCED_LABEL (decl
)
508 || !DECL_ARTIFICIAL (decl
))
510 gsi_remove (&gsi
, false);
511 gsi_insert_before (&gsi_to
, label
, GSI_SAME_STMT
);
517 /* Move debug statements if the destination has a single predecessor. */
518 if (can_move_debug_stmts
)
520 gsi_to
= gsi_after_labels (dest
);
521 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); )
523 gimple
*debug
= gsi_stmt (gsi
);
524 if (!is_gimple_debug (debug
))
526 gsi_remove (&gsi
, false);
527 gsi_insert_before (&gsi_to
, debug
, GSI_SAME_STMT
);
531 bitmap_set_bit (cfgcleanup_altered_bbs
, dest
->index
);
533 /* Update the dominators. */
534 if (dom_info_available_p (CDI_DOMINATORS
))
536 basic_block dom
, dombb
, domdest
;
538 dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
539 domdest
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
542 /* Shortcut to avoid calling (relatively expensive)
543 nearest_common_dominator unless necessary. */
547 dom
= nearest_common_dominator (CDI_DOMINATORS
, domdest
, dombb
);
549 set_immediate_dominator (CDI_DOMINATORS
, dest
, dom
);
552 /* Adjust latch infomation of BB's parent loop as otherwise
553 the cfg hook has a hard time not to kill the loop. */
554 if (current_loops
&& bb
->loop_father
->latch
== bb
)
555 bb
->loop_father
->latch
= pred
;
557 /* And kill the forwarder block. */
558 delete_basic_block (bb
);
563 /* STMT is a call that has been discovered noreturn. Split the
564 block to prepare fixing up the CFG and remove LHS.
565 Return true if cleanup-cfg needs to run. */
568 fixup_noreturn_call (gimple
*stmt
)
570 basic_block bb
= gimple_bb (stmt
);
571 bool changed
= false;
573 if (gimple_call_builtin_p (stmt
, BUILT_IN_RETURN
))
576 /* First split basic block if stmt is not last. */
577 if (stmt
!= gsi_stmt (gsi_last_bb (bb
)))
579 if (stmt
== gsi_stmt (gsi_last_nondebug_bb (bb
)))
581 /* Don't split if there are only debug stmts
582 after stmt, that can result in -fcompare-debug
583 failures. Remove the debug stmts instead,
584 they should be all unreachable anyway. */
585 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
586 for (gsi_next (&gsi
); !gsi_end_p (gsi
); )
587 gsi_remove (&gsi
, true);
591 split_block (bb
, stmt
);
596 /* If there is an LHS, remove it, but only if its type has fixed size.
597 The LHS will need to be recreated during RTL expansion and creating
598 temporaries of variable-sized types is not supported. */
599 tree lhs
= gimple_call_lhs (stmt
);
600 if (lhs
&& TREE_CODE (TYPE_SIZE_UNIT (TREE_TYPE (lhs
))) == INTEGER_CST
)
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 /* Mark the call as altering control flow. */
617 if (!gimple_call_ctrl_altering_p (stmt
))
619 gimple_call_set_ctrl_altering (stmt
, true);
627 /* Tries to cleanup cfg in basic block BB. Returns true if anything
631 cleanup_tree_cfg_bb (basic_block bb
)
633 bool retval
= cleanup_control_flow_bb (bb
);
635 if (tree_forwarder_block_p (bb
, false)
636 && remove_forwarder_block (bb
))
639 /* Merging the blocks may create new opportunities for folding
640 conditional branches (due to the elimination of single-valued PHI
642 if (single_succ_p (bb
)
643 && can_merge_blocks_p (bb
, single_succ (bb
)))
645 /* If there is a merge opportunity with the predecessor
646 do nothing now but wait until we process the predecessor.
647 This happens when we visit BBs in a non-optimal order and
648 avoids quadratic behavior with adjusting stmts BB pointer. */
649 if (single_pred_p (bb
)
650 && can_merge_blocks_p (single_pred (bb
), bb
))
654 merge_blocks (bb
, single_succ (bb
));
662 /* Iterate the cfg cleanups, while anything changes. */
665 cleanup_tree_cfg_1 (void)
671 /* Prepare the worklists of altered blocks. */
672 cfgcleanup_altered_bbs
= BITMAP_ALLOC (NULL
);
674 /* During forwarder block cleanup, we may redirect edges out of
675 SWITCH_EXPRs, which can get expensive. So we want to enable
676 recording of edge to CASE_LABEL_EXPR. */
677 start_recording_case_labels ();
679 /* Start by iterating over all basic blocks. We cannot use FOR_EACH_BB_FN,
680 since the basic blocks may get removed. */
681 n
= last_basic_block_for_fn (cfun
);
682 for (i
= NUM_FIXED_BLOCKS
; i
< n
; i
++)
684 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
686 retval
|= cleanup_tree_cfg_bb (bb
);
689 /* Now process the altered blocks, as long as any are available. */
690 while (!bitmap_empty_p (cfgcleanup_altered_bbs
))
692 i
= bitmap_first_set_bit (cfgcleanup_altered_bbs
);
693 bitmap_clear_bit (cfgcleanup_altered_bbs
, i
);
694 if (i
< NUM_FIXED_BLOCKS
)
697 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
701 retval
|= cleanup_tree_cfg_bb (bb
);
704 end_recording_case_labels ();
705 BITMAP_FREE (cfgcleanup_altered_bbs
);
710 /* Remove unreachable blocks and other miscellaneous clean up work.
711 Return true if the flowgraph was modified, false otherwise. */
714 cleanup_tree_cfg_noloop (void)
718 timevar_push (TV_TREE_CLEANUP_CFG
);
720 /* Iterate until there are no more cleanups left to do. If any
721 iteration changed the flowgraph, set CHANGED to true.
723 If dominance information is available, there cannot be any unreachable
725 if (!dom_info_available_p (CDI_DOMINATORS
))
727 changed
= delete_unreachable_blocks ();
728 calculate_dominance_info (CDI_DOMINATORS
);
732 #ifdef ENABLE_CHECKING
733 verify_dominators (CDI_DOMINATORS
);
738 changed
|= cleanup_tree_cfg_1 ();
740 gcc_assert (dom_info_available_p (CDI_DOMINATORS
));
743 #ifdef ENABLE_CHECKING
747 timevar_pop (TV_TREE_CLEANUP_CFG
);
749 if (changed
&& current_loops
)
750 loops_state_set (LOOPS_NEED_FIXUP
);
755 /* Repairs loop structures. */
758 repair_loop_structures (void)
761 unsigned n_new_loops
;
763 calculate_dominance_info (CDI_DOMINATORS
);
765 timevar_push (TV_REPAIR_LOOPS
);
766 changed_bbs
= BITMAP_ALLOC (NULL
);
767 n_new_loops
= fix_loop_structure (changed_bbs
);
769 /* This usually does nothing. But sometimes parts of cfg that originally
770 were inside a loop get out of it due to edge removal (since they
771 become unreachable by back edges from latch). Also a former
772 irreducible loop can become reducible - in this case force a full
773 rewrite into loop-closed SSA form. */
774 if (loops_state_satisfies_p (LOOP_CLOSED_SSA
))
775 rewrite_into_loop_closed_ssa (n_new_loops
? NULL
: changed_bbs
,
778 BITMAP_FREE (changed_bbs
);
780 #ifdef ENABLE_CHECKING
781 verify_loop_structure ();
785 timevar_pop (TV_REPAIR_LOOPS
);
788 /* Cleanup cfg and repair loop structures. */
791 cleanup_tree_cfg (void)
793 bool changed
= cleanup_tree_cfg_noloop ();
795 if (current_loops
!= NULL
796 && loops_state_satisfies_p (LOOPS_NEED_FIXUP
))
797 repair_loop_structures ();
802 /* Tries to merge the PHI nodes at BB into those at BB's sole successor.
803 Returns true if successful. */
806 remove_forwarder_block_with_phi (basic_block bb
)
808 edge succ
= single_succ_edge (bb
);
809 basic_block dest
= succ
->dest
;
811 basic_block dombb
, domdest
, dom
;
813 /* We check for infinite loops already in tree_forwarder_block_p.
814 However it may happen that the infinite loop is created
815 afterwards due to removal of forwarders. */
819 /* If the destination block consists of a nonlocal label, do not
821 label
= first_stmt (dest
);
823 if (glabel
*label_stmt
= dyn_cast
<glabel
*> (label
))
824 if (DECL_NONLOCAL (gimple_label_label (label_stmt
)))
827 /* Record BB's single pred in case we need to update the father
828 loop's latch information later. */
829 basic_block pred
= NULL
;
830 if (single_pred_p (bb
))
831 pred
= single_pred (bb
);
833 /* Redirect each incoming edge to BB to DEST. */
834 while (EDGE_COUNT (bb
->preds
) > 0)
836 edge e
= EDGE_PRED (bb
, 0), s
;
839 s
= find_edge (e
->src
, dest
);
842 /* We already have an edge S from E->src to DEST. If S and
843 E->dest's sole successor edge have the same PHI arguments
844 at DEST, redirect S to DEST. */
845 if (phi_alternatives_equal (dest
, s
, succ
))
847 e
= redirect_edge_and_branch (e
, dest
);
848 redirect_edge_var_map_clear (e
);
852 /* PHI arguments are different. Create a forwarder block by
853 splitting E so that we can merge PHI arguments on E to
855 e
= single_succ_edge (split_edge (e
));
858 s
= redirect_edge_and_branch (e
, dest
);
860 /* redirect_edge_and_branch must not create a new edge. */
863 /* Add to the PHI nodes at DEST each PHI argument removed at the
865 for (gsi
= gsi_start_phis (dest
);
869 gphi
*phi
= gsi
.phi ();
870 tree def
= gimple_phi_arg_def (phi
, succ
->dest_idx
);
871 source_location locus
= gimple_phi_arg_location_from_edge (phi
, succ
);
873 if (TREE_CODE (def
) == SSA_NAME
)
875 /* If DEF is one of the results of PHI nodes removed during
876 redirection, replace it with the PHI argument that used
878 vec
<edge_var_map
> *head
= redirect_edge_var_map_vector (e
);
879 size_t length
= head
? head
->length () : 0;
880 for (size_t i
= 0; i
< length
; i
++)
882 edge_var_map
*vm
= &(*head
)[i
];
883 tree old_arg
= redirect_edge_var_map_result (vm
);
884 tree new_arg
= redirect_edge_var_map_def (vm
);
889 locus
= redirect_edge_var_map_location (vm
);
895 add_phi_arg (phi
, def
, s
, locus
);
898 redirect_edge_var_map_clear (e
);
901 /* Update the dominators. */
902 dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
903 domdest
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
906 /* Shortcut to avoid calling (relatively expensive)
907 nearest_common_dominator unless necessary. */
911 dom
= nearest_common_dominator (CDI_DOMINATORS
, domdest
, dombb
);
913 set_immediate_dominator (CDI_DOMINATORS
, dest
, dom
);
915 /* Adjust latch infomation of BB's parent loop as otherwise
916 the cfg hook has a hard time not to kill the loop. */
917 if (current_loops
&& bb
->loop_father
->latch
== bb
)
918 bb
->loop_father
->latch
= pred
;
920 /* Remove BB since all of BB's incoming edges have been redirected
922 delete_basic_block (bb
);
927 /* This pass merges PHI nodes if one feeds into another. For example,
928 suppose we have the following:
935 # tem_6 = PHI <tem_17(8), tem_23(7)>;
938 # tem_3 = PHI <tem_6(9), tem_2(5)>;
941 Then we merge the first PHI node into the second one like so:
948 # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
954 const pass_data pass_data_merge_phi
=
956 GIMPLE_PASS
, /* type */
957 "mergephi", /* name */
958 OPTGROUP_NONE
, /* optinfo_flags */
959 TV_TREE_MERGE_PHI
, /* tv_id */
960 ( PROP_cfg
| PROP_ssa
), /* properties_required */
961 0, /* properties_provided */
962 0, /* properties_destroyed */
963 0, /* todo_flags_start */
964 0, /* todo_flags_finish */
967 class pass_merge_phi
: public gimple_opt_pass
970 pass_merge_phi (gcc::context
*ctxt
)
971 : gimple_opt_pass (pass_data_merge_phi
, ctxt
)
974 /* opt_pass methods: */
975 opt_pass
* clone () { return new pass_merge_phi (m_ctxt
); }
976 virtual unsigned int execute (function
*);
978 }; // class pass_merge_phi
981 pass_merge_phi::execute (function
*fun
)
983 basic_block
*worklist
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (fun
));
984 basic_block
*current
= worklist
;
987 calculate_dominance_info (CDI_DOMINATORS
);
989 /* Find all PHI nodes that we may be able to merge. */
990 FOR_EACH_BB_FN (bb
, fun
)
994 /* Look for a forwarder block with PHI nodes. */
995 if (!tree_forwarder_block_p (bb
, true))
998 dest
= single_succ (bb
);
1000 /* We have to feed into another basic block with PHI
1002 if (gimple_seq_empty_p (phi_nodes (dest
))
1003 /* We don't want to deal with a basic block with
1005 || bb_has_abnormal_pred (bb
))
1008 if (!dominated_by_p (CDI_DOMINATORS
, dest
, bb
))
1010 /* If BB does not dominate DEST, then the PHI nodes at
1011 DEST must be the only users of the results of the PHI
1018 unsigned int dest_idx
= single_succ_edge (bb
)->dest_idx
;
1020 /* BB dominates DEST. There may be many users of the PHI
1021 nodes in BB. However, there is still a trivial case we
1022 can handle. If the result of every PHI in BB is used
1023 only by a PHI in DEST, then we can trivially merge the
1024 PHI nodes from BB into DEST. */
1025 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
1028 gphi
*phi
= gsi
.phi ();
1029 tree result
= gimple_phi_result (phi
);
1030 use_operand_p imm_use
;
1033 /* If the PHI's result is never used, then we can just
1035 if (has_zero_uses (result
))
1038 /* Get the single use of the result of this PHI node. */
1039 if (!single_imm_use (result
, &imm_use
, &use_stmt
)
1040 || gimple_code (use_stmt
) != GIMPLE_PHI
1041 || gimple_bb (use_stmt
) != dest
1042 || gimple_phi_arg_def (use_stmt
, dest_idx
) != result
)
1046 /* If the loop above iterated through all the PHI nodes
1047 in BB, then we can merge the PHIs from BB into DEST. */
1048 if (gsi_end_p (gsi
))
1053 /* Now let's drain WORKLIST. */
1054 bool changed
= false;
1055 while (current
!= worklist
)
1058 changed
|= remove_forwarder_block_with_phi (bb
);
1062 /* Removing forwarder blocks can cause formerly irreducible loops
1063 to become reducible if we merged two entry blocks. */
1066 loops_state_set (LOOPS_NEED_FIXUP
);
1074 make_pass_merge_phi (gcc::context
*ctxt
)
1076 return new pass_merge_phi (ctxt
);
1079 /* Pass: cleanup the CFG just before expanding trees to RTL.
1080 This is just a round of label cleanups and case node grouping
1081 because after the tree optimizers have run such cleanups may
1085 execute_cleanup_cfg_post_optimizing (void)
1087 unsigned int todo
= execute_fixup_cfg ();
1088 if (cleanup_tree_cfg ())
1090 todo
&= ~TODO_cleanup_cfg
;
1091 todo
|= TODO_update_ssa
;
1093 maybe_remove_unreachable_handlers ();
1094 cleanup_dead_labels ();
1095 group_case_labels ();
1096 if ((flag_compare_debug_opt
|| flag_compare_debug
)
1097 && flag_dump_final_insns
)
1099 FILE *final_output
= fopen (flag_dump_final_insns
, "a");
1103 error ("could not open final insn dump file %qs: %m",
1104 flag_dump_final_insns
);
1105 flag_dump_final_insns
= NULL
;
1109 int save_unnumbered
= flag_dump_unnumbered
;
1110 int save_noaddr
= flag_dump_noaddr
;
1112 flag_dump_noaddr
= flag_dump_unnumbered
= 1;
1113 fprintf (final_output
, "\n");
1114 dump_enumerated_decls (final_output
, dump_flags
| TDF_NOUID
);
1115 flag_dump_noaddr
= save_noaddr
;
1116 flag_dump_unnumbered
= save_unnumbered
;
1117 if (fclose (final_output
))
1119 error ("could not close final insn dump file %qs: %m",
1120 flag_dump_final_insns
);
1121 flag_dump_final_insns
= NULL
;
1130 const pass_data pass_data_cleanup_cfg_post_optimizing
=
1132 GIMPLE_PASS
, /* type */
1133 "optimized", /* name */
1134 OPTGROUP_NONE
, /* optinfo_flags */
1135 TV_TREE_CLEANUP_CFG
, /* tv_id */
1136 PROP_cfg
, /* properties_required */
1137 0, /* properties_provided */
1138 0, /* properties_destroyed */
1139 0, /* todo_flags_start */
1140 TODO_remove_unused_locals
, /* todo_flags_finish */
1143 class pass_cleanup_cfg_post_optimizing
: public gimple_opt_pass
1146 pass_cleanup_cfg_post_optimizing (gcc::context
*ctxt
)
1147 : gimple_opt_pass (pass_data_cleanup_cfg_post_optimizing
, ctxt
)
1150 /* opt_pass methods: */
1151 virtual unsigned int execute (function
*)
1153 return execute_cleanup_cfg_post_optimizing ();
1156 }; // class pass_cleanup_cfg_post_optimizing
1161 make_pass_cleanup_cfg_post_optimizing (gcc::context
*ctxt
)
1163 return new pass_cleanup_cfg_post_optimizing (ctxt
);