1 /* CFG cleanup for trees.
2 Copyright (C) 2001-2018 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 "tree-pass.h"
30 #include "diagnostic-core.h"
31 #include "fold-const.h"
33 #include "cfgcleanup.h"
36 #include "gimple-iterator.h"
38 #include "tree-ssa-loop-manip.h"
42 #include "tree-scalar-evolution.h"
43 #include "gimple-match.h"
44 #include "gimple-fold.h"
45 #include "tree-ssa-loop-niter.h"
48 /* The set of blocks in that at least one of the following changes happened:
49 -- the statement at the end of the block was changed
50 -- the block was newly created
51 -- the set of the predecessors of the block changed
52 -- the set of the successors of the block changed
53 ??? Maybe we could track these changes separately, since they determine
54 what cleanups it makes sense to try on the block. */
55 bitmap cfgcleanup_altered_bbs
;
57 /* Remove any fallthru edge from EV. Return true if an edge was removed. */
60 remove_fallthru_edge (vec
<edge
, va_gc
> *ev
)
65 FOR_EACH_EDGE (e
, ei
, ev
)
66 if ((e
->flags
& EDGE_FALLTHRU
) != 0)
68 if (e
->flags
& EDGE_COMPLEX
)
69 e
->flags
&= ~EDGE_FALLTHRU
;
71 remove_edge_and_dominated_blocks (e
);
77 /* Convert a SWTCH with single non-default case to gcond and replace it
81 convert_single_case_switch (gswitch
*swtch
, gimple_stmt_iterator
&gsi
)
83 if (gimple_switch_num_labels (swtch
) != 2)
86 tree index
= gimple_switch_index (swtch
);
87 tree default_label
= CASE_LABEL (gimple_switch_default_label (swtch
));
88 tree label
= gimple_switch_label (swtch
, 1);
89 tree low
= CASE_LOW (label
);
90 tree high
= CASE_HIGH (label
);
92 basic_block default_bb
= label_to_block_fn (cfun
, default_label
);
93 basic_block case_bb
= label_to_block_fn (cfun
, CASE_LABEL (label
));
95 basic_block bb
= gimple_bb (swtch
);
98 /* Replace switch statement with condition statement. */
102 generate_range_test (bb
, index
, low
, high
, &lhs
, &rhs
);
103 cond
= gimple_build_cond (LE_EXPR
, lhs
, rhs
, NULL_TREE
, NULL_TREE
);
106 cond
= gimple_build_cond (EQ_EXPR
, index
,
107 fold_convert (TREE_TYPE (index
), low
),
108 NULL_TREE
, NULL_TREE
);
110 gsi_replace (&gsi
, cond
, true);
113 edge case_edge
= find_edge (bb
, case_bb
);
114 edge default_edge
= find_edge (bb
, default_bb
);
116 case_edge
->flags
|= EDGE_TRUE_VALUE
;
117 default_edge
->flags
|= EDGE_FALSE_VALUE
;
121 /* Disconnect an unreachable block in the control expression starting
125 cleanup_control_expr_graph (basic_block bb
, gimple_stmt_iterator gsi
)
129 gimple
*stmt
= gsi_stmt (gsi
);
131 if (!single_succ_p (bb
))
136 tree val
= NULL_TREE
;
138 /* Try to convert a switch with just a single non-default case to
140 if (gimple_code (stmt
) == GIMPLE_SWITCH
141 && convert_single_case_switch (as_a
<gswitch
*> (stmt
), gsi
))
142 stmt
= gsi_stmt (gsi
);
144 fold_defer_overflow_warnings ();
145 switch (gimple_code (stmt
))
149 gimple_match_op res_op
;
150 if (gimple_simplify (stmt
, &res_op
, NULL
, no_follow_ssa_edges
,
152 && res_op
.code
== INTEGER_CST
)
158 val
= gimple_switch_index (as_a
<gswitch
*> (stmt
));
164 taken_edge
= find_taken_edge (bb
, val
);
167 fold_undefer_and_ignore_overflow_warnings ();
171 /* Remove all the edges except the one that is always executed. */
173 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
179 fold_undefer_overflow_warnings
180 (true, stmt
, WARN_STRICT_OVERFLOW_CONDITIONAL
);
184 taken_edge
->probability
+= e
->probability
;
185 remove_edge_and_dominated_blocks (e
);
192 fold_undefer_and_ignore_overflow_warnings ();
195 taken_edge
= single_succ_edge (bb
);
197 bitmap_set_bit (cfgcleanup_altered_bbs
, bb
->index
);
198 gsi_remove (&gsi
, true);
199 taken_edge
->flags
= EDGE_FALLTHRU
;
204 /* Cleanup the GF_CALL_CTRL_ALTERING flag according to
205 to updated gimple_call_flags. */
208 cleanup_call_ctrl_altering_flag (gimple
*bb_end
)
210 if (!is_gimple_call (bb_end
)
211 || !gimple_call_ctrl_altering_p (bb_end
))
214 int flags
= gimple_call_flags (bb_end
);
215 if (((flags
& (ECF_CONST
| ECF_PURE
))
216 && !(flags
& ECF_LOOPING_CONST_OR_PURE
))
217 || (flags
& ECF_LEAF
))
218 gimple_call_set_ctrl_altering (bb_end
, false);
221 /* Try to remove superfluous control structures in basic block BB. Returns
222 true if anything changes. */
225 cleanup_control_flow_bb (basic_block bb
)
227 gimple_stmt_iterator gsi
;
231 /* If the last statement of the block could throw and now cannot,
232 we need to prune cfg. */
233 retval
|= gimple_purge_dead_eh_edges (bb
);
235 gsi
= gsi_last_nondebug_bb (bb
);
239 stmt
= gsi_stmt (gsi
);
241 /* Try to cleanup ctrl altering flag for call which ends bb. */
242 cleanup_call_ctrl_altering_flag (stmt
);
244 if (gimple_code (stmt
) == GIMPLE_COND
245 || gimple_code (stmt
) == GIMPLE_SWITCH
)
247 gcc_checking_assert (gsi_stmt (gsi_last_bb (bb
)) == stmt
);
248 retval
|= cleanup_control_expr_graph (bb
, gsi
);
250 else if (gimple_code (stmt
) == GIMPLE_GOTO
251 && TREE_CODE (gimple_goto_dest (stmt
)) == ADDR_EXPR
252 && (TREE_CODE (TREE_OPERAND (gimple_goto_dest (stmt
), 0))
255 /* If we had a computed goto which has a compile-time determinable
256 destination, then we can eliminate the goto. */
260 basic_block target_block
;
262 gcc_checking_assert (gsi_stmt (gsi_last_bb (bb
)) == stmt
);
263 /* First look at all the outgoing edges. Delete any outgoing
264 edges which do not go to the right block. For the one
265 edge which goes to the right block, fix up its flags. */
266 label
= TREE_OPERAND (gimple_goto_dest (stmt
), 0);
267 if (DECL_CONTEXT (label
) != cfun
->decl
)
269 target_block
= label_to_block (label
);
270 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
272 if (e
->dest
!= target_block
)
273 remove_edge_and_dominated_blocks (e
);
276 /* Turn off the EDGE_ABNORMAL flag. */
277 e
->flags
&= ~EDGE_ABNORMAL
;
279 /* And set EDGE_FALLTHRU. */
280 e
->flags
|= EDGE_FALLTHRU
;
285 bitmap_set_bit (cfgcleanup_altered_bbs
, bb
->index
);
286 bitmap_set_bit (cfgcleanup_altered_bbs
, target_block
->index
);
288 /* Remove the GOTO_EXPR as it is not needed. The CFG has all the
289 relevant information we need. */
290 gsi_remove (&gsi
, true);
294 /* Check for indirect calls that have been turned into
296 else if (is_gimple_call (stmt
)
297 && gimple_call_noreturn_p (stmt
))
299 /* If there are debug stmts after the noreturn call, remove them
300 now, they should be all unreachable anyway. */
301 for (gsi_next (&gsi
); !gsi_end_p (gsi
); )
302 gsi_remove (&gsi
, true);
303 if (remove_fallthru_edge (bb
->succs
))
310 /* Return true if basic block BB does nothing except pass control
311 flow to another block and that we can safely insert a label at
312 the start of the successor block.
314 As a precondition, we require that BB be not equal to
318 tree_forwarder_block_p (basic_block bb
, bool phi_wanted
)
320 gimple_stmt_iterator gsi
;
323 /* BB must have a single outgoing edge. */
324 if (single_succ_p (bb
) != 1
325 /* If PHI_WANTED is false, BB must not have any PHI nodes.
326 Otherwise, BB must have PHI nodes. */
327 || gimple_seq_empty_p (phi_nodes (bb
)) == phi_wanted
328 /* BB may not be a predecessor of the exit block. */
329 || single_succ (bb
) == EXIT_BLOCK_PTR_FOR_FN (cfun
)
330 /* Nor should this be an infinite loop. */
331 || single_succ (bb
) == bb
332 /* BB may not have an abnormal outgoing edge. */
333 || (single_succ_edge (bb
)->flags
& EDGE_ABNORMAL
))
336 gcc_checking_assert (bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
));
338 locus
= single_succ_edge (bb
)->goto_locus
;
340 /* There should not be an edge coming from entry, or an EH edge. */
345 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
346 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) || (e
->flags
& EDGE_EH
))
348 /* If goto_locus of any of the edges differs, prevent removing
349 the forwarder block when not optimizing. */
351 && (LOCATION_LOCUS (e
->goto_locus
) != UNKNOWN_LOCATION
352 || LOCATION_LOCUS (locus
) != UNKNOWN_LOCATION
)
353 && e
->goto_locus
!= locus
)
357 /* Now walk through the statements backward. We can ignore labels,
358 anything else means this is not a forwarder block. */
359 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
361 gimple
*stmt
= gsi_stmt (gsi
);
363 switch (gimple_code (stmt
))
366 if (DECL_NONLOCAL (gimple_label_label (as_a
<glabel
*> (stmt
))))
369 && (gimple_has_location (stmt
)
370 || LOCATION_LOCUS (locus
) != UNKNOWN_LOCATION
)
371 && gimple_location (stmt
) != locus
)
375 /* ??? For now, hope there's a corresponding debug
376 assignment at the destination. */
388 /* Protect loop headers. */
389 if (bb_loop_header_p (bb
))
392 dest
= EDGE_SUCC (bb
, 0)->dest
;
393 /* Protect loop preheaders and latches if requested. */
394 if (dest
->loop_father
->header
== dest
)
396 if (bb
->loop_father
== dest
->loop_father
)
398 if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES
))
400 /* If bb doesn't have a single predecessor we'd make this
401 loop have multiple latches. Don't do that if that
402 would in turn require disambiguating them. */
403 return (single_pred_p (bb
)
404 || loops_state_satisfies_p
405 (LOOPS_MAY_HAVE_MULTIPLE_LATCHES
));
407 else if (bb
->loop_father
== loop_outer (dest
->loop_father
))
408 return !loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS
);
409 /* Always preserve other edges into loop headers that are
410 not simple latches or preheaders. */
418 /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
419 those alternatives are equal in each of the PHI nodes, then return
420 true, else return false. */
423 phi_alternatives_equal (basic_block dest
, edge e1
, edge e2
)
425 int n1
= e1
->dest_idx
;
426 int n2
= e2
->dest_idx
;
429 for (gsi
= gsi_start_phis (dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
431 gphi
*phi
= gsi
.phi ();
432 tree val1
= gimple_phi_arg_def (phi
, n1
);
433 tree val2
= gimple_phi_arg_def (phi
, n2
);
435 gcc_assert (val1
!= NULL_TREE
);
436 gcc_assert (val2
!= NULL_TREE
);
438 if (!operand_equal_for_phi_arg_p (val1
, val2
))
445 /* Removes forwarder block BB. Returns false if this failed. */
448 remove_forwarder_block (basic_block bb
)
450 edge succ
= single_succ_edge (bb
), e
, s
;
451 basic_block dest
= succ
->dest
;
454 gimple_stmt_iterator gsi
, gsi_to
;
455 bool can_move_debug_stmts
;
457 /* We check for infinite loops already in tree_forwarder_block_p.
458 However it may happen that the infinite loop is created
459 afterwards due to removal of forwarders. */
463 /* If the destination block consists of a nonlocal label or is a
464 EH landing pad, do not merge it. */
465 stmt
= first_stmt (dest
);
467 if (glabel
*label_stmt
= dyn_cast
<glabel
*> (stmt
))
468 if (DECL_NONLOCAL (gimple_label_label (label_stmt
))
469 || EH_LANDING_PAD_NR (gimple_label_label (label_stmt
)) != 0)
472 /* If there is an abnormal edge to basic block BB, but not into
473 dest, problems might occur during removal of the phi node at out
474 of ssa due to overlapping live ranges of registers.
476 If there is an abnormal edge in DEST, the problems would occur
477 anyway since cleanup_dead_labels would then merge the labels for
478 two different eh regions, and rest of exception handling code
481 So if there is an abnormal edge to BB, proceed only if there is
482 no abnormal edge to DEST and there are no phi nodes in DEST. */
483 if (bb_has_abnormal_pred (bb
)
484 && (bb_has_abnormal_pred (dest
)
485 || !gimple_seq_empty_p (phi_nodes (dest
))))
488 /* If there are phi nodes in DEST, and some of the blocks that are
489 predecessors of BB are also predecessors of DEST, check that the
490 phi node arguments match. */
491 if (!gimple_seq_empty_p (phi_nodes (dest
)))
493 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
495 s
= find_edge (e
->src
, dest
);
499 if (!phi_alternatives_equal (dest
, succ
, s
))
504 can_move_debug_stmts
= MAY_HAVE_DEBUG_STMTS
&& single_pred_p (dest
);
506 basic_block pred
= NULL
;
507 if (single_pred_p (bb
))
508 pred
= single_pred (bb
);
510 /* Redirect the edges. */
511 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
513 bitmap_set_bit (cfgcleanup_altered_bbs
, e
->src
->index
);
515 if (e
->flags
& EDGE_ABNORMAL
)
517 /* If there is an abnormal edge, redirect it anyway, and
518 move the labels to the new block to make it legal. */
519 s
= redirect_edge_succ_nodup (e
, dest
);
522 s
= redirect_edge_and_branch (e
, dest
);
526 /* Create arguments for the phi nodes, since the edge was not
528 for (gphi_iterator psi
= gsi_start_phis (dest
);
532 gphi
*phi
= psi
.phi ();
533 source_location l
= gimple_phi_arg_location_from_edge (phi
, succ
);
534 tree def
= gimple_phi_arg_def (phi
, succ
->dest_idx
);
535 add_phi_arg (phi
, unshare_expr (def
), s
, l
);
540 /* Move nonlocal labels and computed goto targets as well as user
541 defined labels and labels with an EH landing pad number to the
542 new block, so that the redirection of the abnormal edges works,
543 jump targets end up in a sane place and debug information for
544 labels is retained. */
545 gsi_to
= gsi_start_bb (dest
);
546 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
548 stmt
= gsi_stmt (gsi
);
549 if (is_gimple_debug (stmt
))
552 /* Forwarder blocks can only contain labels and debug stmts, and
553 labels must come first, so if we get to this point, we know
554 we're looking at a label. */
555 tree decl
= gimple_label_label (as_a
<glabel
*> (stmt
));
556 if (EH_LANDING_PAD_NR (decl
) != 0
557 || DECL_NONLOCAL (decl
)
558 || FORCED_LABEL (decl
)
559 || !DECL_ARTIFICIAL (decl
))
560 gsi_move_before (&gsi
, &gsi_to
);
565 /* Move debug statements if the destination has a single predecessor. */
566 if (can_move_debug_stmts
&& !gsi_end_p (gsi
))
568 gsi_to
= gsi_after_labels (dest
);
571 gimple
*debug
= gsi_stmt (gsi
);
572 gcc_assert (is_gimple_debug (debug
));
573 gsi_move_before (&gsi
, &gsi_to
);
575 while (!gsi_end_p (gsi
));
578 bitmap_set_bit (cfgcleanup_altered_bbs
, dest
->index
);
580 /* Update the dominators. */
581 if (dom_info_available_p (CDI_DOMINATORS
))
583 basic_block dom
, dombb
, domdest
;
585 dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
586 domdest
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
589 /* Shortcut to avoid calling (relatively expensive)
590 nearest_common_dominator unless necessary. */
594 dom
= nearest_common_dominator (CDI_DOMINATORS
, domdest
, dombb
);
596 set_immediate_dominator (CDI_DOMINATORS
, dest
, dom
);
599 /* Adjust latch infomation of BB's parent loop as otherwise
600 the cfg hook has a hard time not to kill the loop. */
601 if (current_loops
&& bb
->loop_father
->latch
== bb
)
602 bb
->loop_father
->latch
= pred
;
604 /* And kill the forwarder block. */
605 delete_basic_block (bb
);
610 /* STMT is a call that has been discovered noreturn. Split the
611 block to prepare fixing up the CFG and remove LHS.
612 Return true if cleanup-cfg needs to run. */
615 fixup_noreturn_call (gimple
*stmt
)
617 basic_block bb
= gimple_bb (stmt
);
618 bool changed
= false;
620 if (gimple_call_builtin_p (stmt
, BUILT_IN_RETURN
))
623 /* First split basic block if stmt is not last. */
624 if (stmt
!= gsi_stmt (gsi_last_bb (bb
)))
626 if (stmt
== gsi_stmt (gsi_last_nondebug_bb (bb
)))
628 /* Don't split if there are only debug stmts
629 after stmt, that can result in -fcompare-debug
630 failures. Remove the debug stmts instead,
631 they should be all unreachable anyway. */
632 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
633 for (gsi_next (&gsi
); !gsi_end_p (gsi
); )
634 gsi_remove (&gsi
, true);
638 split_block (bb
, stmt
);
643 /* If there is an LHS, remove it, but only if its type has fixed size.
644 The LHS will need to be recreated during RTL expansion and creating
645 temporaries of variable-sized types is not supported. Also don't
646 do this with TREE_ADDRESSABLE types, as assign_temp will abort.
647 Drop LHS regardless of TREE_ADDRESSABLE, if the function call
648 has been changed into a call that does not return a value, like
649 __builtin_unreachable or __cxa_pure_virtual. */
650 tree lhs
= gimple_call_lhs (stmt
);
652 && (should_remove_lhs_p (lhs
)
653 || VOID_TYPE_P (TREE_TYPE (gimple_call_fntype (stmt
)))))
655 gimple_call_set_lhs (stmt
, NULL_TREE
);
657 /* We need to fix up the SSA name to avoid checking errors. */
658 if (TREE_CODE (lhs
) == SSA_NAME
)
660 tree new_var
= create_tmp_reg (TREE_TYPE (lhs
));
661 SET_SSA_NAME_VAR_OR_IDENTIFIER (lhs
, new_var
);
662 SSA_NAME_DEF_STMT (lhs
) = gimple_build_nop ();
663 set_ssa_default_def (cfun
, new_var
, lhs
);
669 /* Mark the call as altering control flow. */
670 if (!gimple_call_ctrl_altering_p (stmt
))
672 gimple_call_set_ctrl_altering (stmt
, true);
679 /* Return true if we want to merge BB1 and BB2 into a single block. */
682 want_merge_blocks_p (basic_block bb1
, basic_block bb2
)
684 if (!can_merge_blocks_p (bb1
, bb2
))
686 gimple_stmt_iterator gsi
= gsi_last_nondebug_bb (bb1
);
687 if (gsi_end_p (gsi
) || !stmt_can_terminate_bb_p (gsi_stmt (gsi
)))
689 return bb1
->count
.ok_for_merging (bb2
->count
);
693 /* Tries to cleanup cfg in basic block BB by merging blocks. Returns
694 true if anything changes. */
697 cleanup_tree_cfg_bb (basic_block bb
)
699 if (tree_forwarder_block_p (bb
, false)
700 && remove_forwarder_block (bb
))
703 /* If there is a merge opportunity with the predecessor
704 do nothing now but wait until we process the predecessor.
705 This happens when we visit BBs in a non-optimal order and
706 avoids quadratic behavior with adjusting stmts BB pointer. */
707 if (single_pred_p (bb
)
708 && want_merge_blocks_p (single_pred (bb
), bb
))
709 /* But make sure we _do_ visit it. When we remove unreachable paths
710 ending in a backedge we fail to mark the destinations predecessors
712 bitmap_set_bit (cfgcleanup_altered_bbs
, single_pred (bb
)->index
);
714 /* Merging the blocks may create new opportunities for folding
715 conditional branches (due to the elimination of single-valued PHI
717 else if (single_succ_p (bb
)
718 && want_merge_blocks_p (bb
, single_succ (bb
)))
720 merge_blocks (bb
, single_succ (bb
));
727 /* Do cleanup_control_flow_bb in PRE order. */
730 cleanup_control_flow_pre ()
734 /* We want remove_edge_and_dominated_blocks to only remove edges,
735 not dominated blocks which it does when dom info isn't available.
737 dom_state saved_state
= dom_info_state (CDI_DOMINATORS
);
738 set_dom_info_availability (CDI_DOMINATORS
, DOM_NONE
);
740 auto_vec
<edge_iterator
, 20> stack (n_basic_blocks_for_fn (cfun
) + 1);
741 auto_sbitmap
visited (last_basic_block_for_fn (cfun
));
742 bitmap_clear (visited
);
744 stack
.quick_push (ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
));
746 while (! stack
.is_empty ())
748 /* Look at the edge on the top of the stack. */
749 edge_iterator ei
= stack
.last ();
750 basic_block dest
= ei_edge (ei
)->dest
;
752 if (dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
753 && ! bitmap_bit_p (visited
, dest
->index
))
755 bitmap_set_bit (visited
, dest
->index
);
756 /* We only possibly remove edges from DEST here, leaving
757 possibly unreachable code in the IL. */
758 retval
|= cleanup_control_flow_bb (dest
);
759 if (EDGE_COUNT (dest
->succs
) > 0)
760 stack
.quick_push (ei_start (dest
->succs
));
764 if (!ei_one_before_end_p (ei
))
765 ei_next (&stack
.last ());
771 set_dom_info_availability (CDI_DOMINATORS
, saved_state
);
773 /* We are deleting BBs in non-reverse dominator order, make sure
774 insert_debug_temps_for_defs is prepared for that. */
776 free_dominance_info (CDI_DOMINATORS
);
778 /* Remove all now (and previously) unreachable blocks. */
779 for (int i
= NUM_FIXED_BLOCKS
; i
< last_basic_block_for_fn (cfun
); ++i
)
781 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
782 if (bb
&& !bitmap_bit_p (visited
, bb
->index
))
785 free_dominance_info (CDI_DOMINATORS
);
786 delete_basic_block (bb
);
795 mfb_keep_latches (edge e
)
797 return !((dom_info_available_p (CDI_DOMINATORS
)
798 && dominated_by_p (CDI_DOMINATORS
, e
->src
, e
->dest
))
799 || (e
->flags
& EDGE_DFS_BACK
));
802 /* Remove unreachable blocks and other miscellaneous clean up work.
803 Return true if the flowgraph was modified, false otherwise. */
806 cleanup_tree_cfg_noloop (void)
808 timevar_push (TV_TREE_CLEANUP_CFG
);
810 /* Ensure that we have single entries into loop headers. Otherwise
811 if one of the entries is becoming a latch due to CFG cleanup
812 (from formerly being part of an irreducible region) then we mess
813 up loop fixup and associate the old loop with a different region
814 which makes niter upper bounds invalid. See for example PR80549.
815 This needs to be done before we remove trivially dead edges as
816 we need to capture the dominance state before the pending transform. */
819 /* This needs backedges or dominators. */
820 if (!dom_info_available_p (CDI_DOMINATORS
))
821 mark_dfs_back_edges ();
825 FOR_EACH_VEC_ELT (*get_loops (cfun
), i
, loop
)
826 if (loop
&& loop
->header
)
828 basic_block bb
= loop
->header
;
831 bool found_latch
= false;
832 bool any_abnormal
= false;
834 /* We are only interested in preserving existing loops, but
835 we need to check whether they are still real and of course
836 if we need to add a preheader at all. */
837 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
839 if (e
->flags
& EDGE_ABNORMAL
)
844 if ((dom_info_available_p (CDI_DOMINATORS
)
845 && dominated_by_p (CDI_DOMINATORS
, e
->src
, bb
))
846 || (e
->flags
& EDGE_DFS_BACK
))
853 /* If we have more than one entry to the loop header
854 create a forwarder. */
855 if (found_latch
&& ! any_abnormal
&& n
> 1)
857 edge fallthru
= make_forwarder_block (bb
, mfb_keep_latches
,
859 loop
->header
= fallthru
->dest
;
860 if (! loops_state_satisfies_p (LOOPS_NEED_FIXUP
))
862 /* The loop updating from the CFG hook is incomplete
863 when we have multiple latches, fixup manually. */
864 remove_bb_from_loops (fallthru
->src
);
866 FOR_EACH_EDGE (e
, ei
, fallthru
->src
->preds
)
867 cloop
= find_common_loop (cloop
, e
->src
->loop_father
);
868 add_bb_to_loop (fallthru
->src
, cloop
);
874 /* Prepare the worklists of altered blocks. */
875 cfgcleanup_altered_bbs
= BITMAP_ALLOC (NULL
);
877 /* Start by iterating over all basic blocks in PRE order looking for
878 edge removal opportunities. Do this first because incoming SSA form
879 may be invalid and we want to avoid performing SSA related tasks such
880 as propgating out a PHI node during BB merging in that state. This
881 also gets rid of unreachable blocks. */
882 bool changed
= cleanup_control_flow_pre ();
884 /* After doing the above SSA form should be valid (or an update SSA
885 should be required). */
887 /* Compute dominator info which we need for the iterative process below. */
888 if (!dom_info_available_p (CDI_DOMINATORS
))
889 calculate_dominance_info (CDI_DOMINATORS
);
891 checking_verify_dominators (CDI_DOMINATORS
);
893 /* During forwarder block cleanup, we may redirect edges out of
894 SWITCH_EXPRs, which can get expensive. So we want to enable
895 recording of edge to CASE_LABEL_EXPR. */
896 start_recording_case_labels ();
898 /* Continue by iterating over all basic blocks looking for BB merging
899 opportunities. We cannot use FOR_EACH_BB_FN for the BB iteration
900 since the basic blocks may get removed. */
901 unsigned n
= last_basic_block_for_fn (cfun
);
902 for (unsigned i
= NUM_FIXED_BLOCKS
; i
< n
; i
++)
904 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
906 changed
|= cleanup_tree_cfg_bb (bb
);
909 /* Now process the altered blocks, as long as any are available. */
910 while (!bitmap_empty_p (cfgcleanup_altered_bbs
))
912 unsigned i
= bitmap_first_set_bit (cfgcleanup_altered_bbs
);
913 bitmap_clear_bit (cfgcleanup_altered_bbs
, i
);
914 if (i
< NUM_FIXED_BLOCKS
)
917 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
921 /* BB merging done by cleanup_tree_cfg_bb can end up propagating
922 out single-argument PHIs which in turn can expose
923 cleanup_control_flow_bb opportunities so we have to repeat
925 changed
|= cleanup_control_flow_bb (bb
);
926 changed
|= cleanup_tree_cfg_bb (bb
);
929 end_recording_case_labels ();
930 BITMAP_FREE (cfgcleanup_altered_bbs
);
932 gcc_assert (dom_info_available_p (CDI_DOMINATORS
));
934 /* Do not renumber blocks if the SCEV cache is active, it is indexed by
935 basic-block numbers. */
936 if (! scev_initialized_p ())
939 checking_verify_flow_info ();
941 timevar_pop (TV_TREE_CLEANUP_CFG
);
943 if (changed
&& current_loops
)
945 /* Removing edges and/or blocks may make recorded bounds refer
946 to stale GIMPLE stmts now, so clear them. */
947 free_numbers_of_iterations_estimates (cfun
);
948 loops_state_set (LOOPS_NEED_FIXUP
);
954 /* Repairs loop structures. */
957 repair_loop_structures (void)
960 unsigned n_new_loops
;
962 calculate_dominance_info (CDI_DOMINATORS
);
964 timevar_push (TV_REPAIR_LOOPS
);
965 changed_bbs
= BITMAP_ALLOC (NULL
);
966 n_new_loops
= fix_loop_structure (changed_bbs
);
968 /* This usually does nothing. But sometimes parts of cfg that originally
969 were inside a loop get out of it due to edge removal (since they
970 become unreachable by back edges from latch). Also a former
971 irreducible loop can become reducible - in this case force a full
972 rewrite into loop-closed SSA form. */
973 if (loops_state_satisfies_p (LOOP_CLOSED_SSA
))
974 rewrite_into_loop_closed_ssa (n_new_loops
? NULL
: changed_bbs
,
977 BITMAP_FREE (changed_bbs
);
979 checking_verify_loop_structure ();
982 timevar_pop (TV_REPAIR_LOOPS
);
985 /* Cleanup cfg and repair loop structures. */
988 cleanup_tree_cfg (void)
990 bool changed
= cleanup_tree_cfg_noloop ();
992 if (current_loops
!= NULL
993 && loops_state_satisfies_p (LOOPS_NEED_FIXUP
))
994 repair_loop_structures ();
999 /* Tries to merge the PHI nodes at BB into those at BB's sole successor.
1000 Returns true if successful. */
1003 remove_forwarder_block_with_phi (basic_block bb
)
1005 edge succ
= single_succ_edge (bb
);
1006 basic_block dest
= succ
->dest
;
1008 basic_block dombb
, domdest
, dom
;
1010 /* We check for infinite loops already in tree_forwarder_block_p.
1011 However it may happen that the infinite loop is created
1012 afterwards due to removal of forwarders. */
1016 /* Removal of forwarders may expose new natural loops and thus
1017 a block may turn into a loop header. */
1018 if (current_loops
&& bb_loop_header_p (bb
))
1021 /* If the destination block consists of a nonlocal label, do not
1023 label
= first_stmt (dest
);
1025 if (glabel
*label_stmt
= dyn_cast
<glabel
*> (label
))
1026 if (DECL_NONLOCAL (gimple_label_label (label_stmt
)))
1029 /* Record BB's single pred in case we need to update the father
1030 loop's latch information later. */
1031 basic_block pred
= NULL
;
1032 if (single_pred_p (bb
))
1033 pred
= single_pred (bb
);
1035 /* Redirect each incoming edge to BB to DEST. */
1036 while (EDGE_COUNT (bb
->preds
) > 0)
1038 edge e
= EDGE_PRED (bb
, 0), s
;
1041 s
= find_edge (e
->src
, dest
);
1044 /* We already have an edge S from E->src to DEST. If S and
1045 E->dest's sole successor edge have the same PHI arguments
1046 at DEST, redirect S to DEST. */
1047 if (phi_alternatives_equal (dest
, s
, succ
))
1049 e
= redirect_edge_and_branch (e
, dest
);
1050 redirect_edge_var_map_clear (e
);
1054 /* PHI arguments are different. Create a forwarder block by
1055 splitting E so that we can merge PHI arguments on E to
1057 e
= single_succ_edge (split_edge (e
));
1061 /* If we merge the forwarder into a loop header verify if we
1062 are creating another loop latch edge. If so, reset
1063 number of iteration information of the loop. */
1064 if (dest
->loop_father
->header
== dest
1065 && dominated_by_p (CDI_DOMINATORS
, e
->src
, dest
))
1067 dest
->loop_father
->any_upper_bound
= false;
1068 dest
->loop_father
->any_likely_upper_bound
= false;
1069 free_numbers_of_iterations_estimates (dest
->loop_father
);
1073 s
= redirect_edge_and_branch (e
, dest
);
1075 /* redirect_edge_and_branch must not create a new edge. */
1076 gcc_assert (s
== e
);
1078 /* Add to the PHI nodes at DEST each PHI argument removed at the
1079 destination of E. */
1080 for (gsi
= gsi_start_phis (dest
);
1084 gphi
*phi
= gsi
.phi ();
1085 tree def
= gimple_phi_arg_def (phi
, succ
->dest_idx
);
1086 source_location locus
= gimple_phi_arg_location_from_edge (phi
, succ
);
1088 if (TREE_CODE (def
) == SSA_NAME
)
1090 /* If DEF is one of the results of PHI nodes removed during
1091 redirection, replace it with the PHI argument that used
1093 vec
<edge_var_map
> *head
= redirect_edge_var_map_vector (e
);
1094 size_t length
= head
? head
->length () : 0;
1095 for (size_t i
= 0; i
< length
; i
++)
1097 edge_var_map
*vm
= &(*head
)[i
];
1098 tree old_arg
= redirect_edge_var_map_result (vm
);
1099 tree new_arg
= redirect_edge_var_map_def (vm
);
1104 locus
= redirect_edge_var_map_location (vm
);
1110 add_phi_arg (phi
, def
, s
, locus
);
1113 redirect_edge_var_map_clear (e
);
1116 /* Update the dominators. */
1117 dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1118 domdest
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
1121 /* Shortcut to avoid calling (relatively expensive)
1122 nearest_common_dominator unless necessary. */
1126 dom
= nearest_common_dominator (CDI_DOMINATORS
, domdest
, dombb
);
1128 set_immediate_dominator (CDI_DOMINATORS
, dest
, dom
);
1130 /* Adjust latch infomation of BB's parent loop as otherwise
1131 the cfg hook has a hard time not to kill the loop. */
1132 if (current_loops
&& bb
->loop_father
->latch
== bb
)
1133 bb
->loop_father
->latch
= pred
;
1135 /* Remove BB since all of BB's incoming edges have been redirected
1137 delete_basic_block (bb
);
1142 /* This pass merges PHI nodes if one feeds into another. For example,
1143 suppose we have the following:
1150 # tem_6 = PHI <tem_17(8), tem_23(7)>;
1153 # tem_3 = PHI <tem_6(9), tem_2(5)>;
1156 Then we merge the first PHI node into the second one like so:
1158 goto <bb 9> (<L10>);
1163 # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
1169 const pass_data pass_data_merge_phi
=
1171 GIMPLE_PASS
, /* type */
1172 "mergephi", /* name */
1173 OPTGROUP_NONE
, /* optinfo_flags */
1174 TV_TREE_MERGE_PHI
, /* tv_id */
1175 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1176 0, /* properties_provided */
1177 0, /* properties_destroyed */
1178 0, /* todo_flags_start */
1179 0, /* todo_flags_finish */
1182 class pass_merge_phi
: public gimple_opt_pass
1185 pass_merge_phi (gcc::context
*ctxt
)
1186 : gimple_opt_pass (pass_data_merge_phi
, ctxt
)
1189 /* opt_pass methods: */
1190 opt_pass
* clone () { return new pass_merge_phi (m_ctxt
); }
1191 virtual unsigned int execute (function
*);
1193 }; // class pass_merge_phi
1196 pass_merge_phi::execute (function
*fun
)
1198 basic_block
*worklist
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (fun
));
1199 basic_block
*current
= worklist
;
1202 calculate_dominance_info (CDI_DOMINATORS
);
1204 /* Find all PHI nodes that we may be able to merge. */
1205 FOR_EACH_BB_FN (bb
, fun
)
1209 /* Look for a forwarder block with PHI nodes. */
1210 if (!tree_forwarder_block_p (bb
, true))
1213 dest
= single_succ (bb
);
1215 /* We have to feed into another basic block with PHI
1217 if (gimple_seq_empty_p (phi_nodes (dest
))
1218 /* We don't want to deal with a basic block with
1220 || bb_has_abnormal_pred (bb
))
1223 if (!dominated_by_p (CDI_DOMINATORS
, dest
, bb
))
1225 /* If BB does not dominate DEST, then the PHI nodes at
1226 DEST must be the only users of the results of the PHI
1233 unsigned int dest_idx
= single_succ_edge (bb
)->dest_idx
;
1235 /* BB dominates DEST. There may be many users of the PHI
1236 nodes in BB. However, there is still a trivial case we
1237 can handle. If the result of every PHI in BB is used
1238 only by a PHI in DEST, then we can trivially merge the
1239 PHI nodes from BB into DEST. */
1240 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
1243 gphi
*phi
= gsi
.phi ();
1244 tree result
= gimple_phi_result (phi
);
1245 use_operand_p imm_use
;
1248 /* If the PHI's result is never used, then we can just
1250 if (has_zero_uses (result
))
1253 /* Get the single use of the result of this PHI node. */
1254 if (!single_imm_use (result
, &imm_use
, &use_stmt
)
1255 || gimple_code (use_stmt
) != GIMPLE_PHI
1256 || gimple_bb (use_stmt
) != dest
1257 || gimple_phi_arg_def (use_stmt
, dest_idx
) != result
)
1261 /* If the loop above iterated through all the PHI nodes
1262 in BB, then we can merge the PHIs from BB into DEST. */
1263 if (gsi_end_p (gsi
))
1268 /* Now let's drain WORKLIST. */
1269 bool changed
= false;
1270 while (current
!= worklist
)
1273 changed
|= remove_forwarder_block_with_phi (bb
);
1277 /* Removing forwarder blocks can cause formerly irreducible loops
1278 to become reducible if we merged two entry blocks. */
1281 loops_state_set (LOOPS_NEED_FIXUP
);
1289 make_pass_merge_phi (gcc::context
*ctxt
)
1291 return new pass_merge_phi (ctxt
);
1294 /* Pass: cleanup the CFG just before expanding trees to RTL.
1295 This is just a round of label cleanups and case node grouping
1296 because after the tree optimizers have run such cleanups may
1300 execute_cleanup_cfg_post_optimizing (void)
1302 unsigned int todo
= execute_fixup_cfg ();
1303 if (cleanup_tree_cfg ())
1305 todo
&= ~TODO_cleanup_cfg
;
1306 todo
|= TODO_update_ssa
;
1308 maybe_remove_unreachable_handlers ();
1309 cleanup_dead_labels ();
1310 if (group_case_labels ())
1311 todo
|= TODO_cleanup_cfg
;
1312 if ((flag_compare_debug_opt
|| flag_compare_debug
)
1313 && flag_dump_final_insns
)
1315 FILE *final_output
= fopen (flag_dump_final_insns
, "a");
1319 error ("could not open final insn dump file %qs: %m",
1320 flag_dump_final_insns
);
1321 flag_dump_final_insns
= NULL
;
1325 int save_unnumbered
= flag_dump_unnumbered
;
1326 int save_noaddr
= flag_dump_noaddr
;
1328 flag_dump_noaddr
= flag_dump_unnumbered
= 1;
1329 fprintf (final_output
, "\n");
1330 dump_enumerated_decls (final_output
,
1331 dump_flags
| TDF_SLIM
| TDF_NOUID
);
1332 flag_dump_noaddr
= save_noaddr
;
1333 flag_dump_unnumbered
= save_unnumbered
;
1334 if (fclose (final_output
))
1336 error ("could not close final insn dump file %qs: %m",
1337 flag_dump_final_insns
);
1338 flag_dump_final_insns
= NULL
;
1347 const pass_data pass_data_cleanup_cfg_post_optimizing
=
1349 GIMPLE_PASS
, /* type */
1350 "optimized", /* name */
1351 OPTGROUP_NONE
, /* optinfo_flags */
1352 TV_TREE_CLEANUP_CFG
, /* tv_id */
1353 PROP_cfg
, /* properties_required */
1354 0, /* properties_provided */
1355 0, /* properties_destroyed */
1356 0, /* todo_flags_start */
1357 TODO_remove_unused_locals
, /* todo_flags_finish */
1360 class pass_cleanup_cfg_post_optimizing
: public gimple_opt_pass
1363 pass_cleanup_cfg_post_optimizing (gcc::context
*ctxt
)
1364 : gimple_opt_pass (pass_data_cleanup_cfg_post_optimizing
, ctxt
)
1367 /* opt_pass methods: */
1368 virtual unsigned int execute (function
*)
1370 return execute_cleanup_cfg_post_optimizing ();
1373 }; // class pass_cleanup_cfg_post_optimizing
1378 make_pass_cleanup_cfg_post_optimizing (gcc::context
*ctxt
)
1380 return new pass_cleanup_cfg_post_optimizing (ctxt
);