1 /* Control flow graph manipulation code for GNU compiler.
2 Copyright (C) 1987-2015 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
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/>. */
20 /* This file contains low level functions to manipulate the CFG and analyze it
21 that are aware of the RTL intermediate language.
23 Available functionality:
24 - Basic CFG/RTL manipulation API documented in cfghooks.h
25 - CFG-aware instruction chain manipulation
26 delete_insn, delete_insn_chain
27 - Edge splitting and committing to edges
28 insert_insn_on_edge, commit_edge_insertions
29 - CFG updating after insn simplification
30 purge_dead_edges, purge_all_dead_edges
31 - CFG fixing after coarse manipulation
34 Functions not supposed for generic use:
35 - Infrastructure to determine quickly basic block for insn
36 compute_bb_for_insn, update_bb_for_insn, set_block_for_insn,
37 - Edge redirection with updating and optimizing of insn chain
38 block_label, tidy_fallthru_edge, force_nonfallthru */
42 #include "coretypes.h"
52 #include "cfgcleanup.h"
53 #include "bb-reorder.h"
57 #include "rtl-error.h"
60 #include "insn-attr.h"
61 #include "insn-config.h"
71 #include "common/common-target.h"
73 #include "tree-pass.h"
75 /* Holds the interesting leading and trailing notes for the function.
76 Only applicable if the CFG is in cfglayout mode. */
77 static GTY(()) rtx_insn
*cfg_layout_function_footer
;
78 static GTY(()) rtx_insn
*cfg_layout_function_header
;
80 static rtx_insn
*skip_insns_after_block (basic_block
);
81 static void record_effective_endpoints (void);
82 static void fixup_reorder_chain (void);
84 void verify_insn_chain (void);
85 static void fixup_fallthru_exit_predecessor (void);
86 static int can_delete_note_p (const rtx_note
*);
87 static int can_delete_label_p (const rtx_code_label
*);
88 static basic_block
rtl_split_edge (edge
);
89 static bool rtl_move_block_after (basic_block
, basic_block
);
90 static int rtl_verify_flow_info (void);
91 static basic_block
cfg_layout_split_block (basic_block
, void *);
92 static edge
cfg_layout_redirect_edge_and_branch (edge
, basic_block
);
93 static basic_block
cfg_layout_redirect_edge_and_branch_force (edge
, basic_block
);
94 static void cfg_layout_delete_block (basic_block
);
95 static void rtl_delete_block (basic_block
);
96 static basic_block
rtl_redirect_edge_and_branch_force (edge
, basic_block
);
97 static edge
rtl_redirect_edge_and_branch (edge
, basic_block
);
98 static basic_block
rtl_split_block (basic_block
, void *);
99 static void rtl_dump_bb (FILE *, basic_block
, int, int);
100 static int rtl_verify_flow_info_1 (void);
101 static void rtl_make_forwarder_block (edge
);
103 /* Return true if NOTE is not one of the ones that must be kept paired,
104 so that we may simply delete it. */
107 can_delete_note_p (const rtx_note
*note
)
109 switch (NOTE_KIND (note
))
111 case NOTE_INSN_DELETED
:
112 case NOTE_INSN_BASIC_BLOCK
:
113 case NOTE_INSN_EPILOGUE_BEG
:
121 /* True if a given label can be deleted. */
124 can_delete_label_p (const rtx_code_label
*label
)
126 return (!LABEL_PRESERVE_P (label
)
127 /* User declared labels must be preserved. */
128 && LABEL_NAME (label
) == 0
129 && !in_insn_list_p (forced_labels
, label
));
132 /* Delete INSN by patching it out. */
135 delete_insn (rtx uncast_insn
)
137 rtx_insn
*insn
= as_a
<rtx_insn
*> (uncast_insn
);
139 bool really_delete
= true;
143 /* Some labels can't be directly removed from the INSN chain, as they
144 might be references via variables, constant pool etc.
145 Convert them to the special NOTE_INSN_DELETED_LABEL note. */
146 if (! can_delete_label_p (as_a
<rtx_code_label
*> (insn
)))
148 const char *name
= LABEL_NAME (insn
);
149 basic_block bb
= BLOCK_FOR_INSN (insn
);
150 rtx_insn
*bb_note
= NEXT_INSN (insn
);
152 really_delete
= false;
153 PUT_CODE (insn
, NOTE
);
154 NOTE_KIND (insn
) = NOTE_INSN_DELETED_LABEL
;
155 NOTE_DELETED_LABEL_NAME (insn
) = name
;
157 /* If the note following the label starts a basic block, and the
158 label is a member of the same basic block, interchange the two. */
159 if (bb_note
!= NULL_RTX
160 && NOTE_INSN_BASIC_BLOCK_P (bb_note
)
162 && bb
== BLOCK_FOR_INSN (bb_note
))
164 reorder_insns_nobb (insn
, insn
, bb_note
);
165 BB_HEAD (bb
) = bb_note
;
166 if (BB_END (bb
) == bb_note
)
171 remove_node_from_insn_list (insn
, &nonlocal_goto_handler_labels
);
176 /* If this insn has already been deleted, something is very wrong. */
177 gcc_assert (!insn
->deleted ());
179 df_insn_delete (insn
);
181 insn
->set_deleted ();
184 /* If deleting a jump, decrement the use count of the label. Deleting
185 the label itself should happen in the normal course of block merging. */
188 if (JUMP_LABEL (insn
)
189 && LABEL_P (JUMP_LABEL (insn
)))
190 LABEL_NUSES (JUMP_LABEL (insn
))--;
192 /* If there are more targets, remove them too. */
194 = find_reg_note (insn
, REG_LABEL_TARGET
, NULL_RTX
)) != NULL_RTX
195 && LABEL_P (XEXP (note
, 0)))
197 LABEL_NUSES (XEXP (note
, 0))--;
198 remove_note (insn
, note
);
202 /* Also if deleting any insn that references a label as an operand. */
203 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, NULL_RTX
)) != NULL_RTX
204 && LABEL_P (XEXP (note
, 0)))
206 LABEL_NUSES (XEXP (note
, 0))--;
207 remove_note (insn
, note
);
210 if (rtx_jump_table_data
*table
= dyn_cast
<rtx_jump_table_data
*> (insn
))
212 rtvec vec
= table
->get_labels ();
213 int len
= GET_NUM_ELEM (vec
);
216 for (i
= 0; i
< len
; i
++)
218 rtx label
= XEXP (RTVEC_ELT (vec
, i
), 0);
220 /* When deleting code in bulk (e.g. removing many unreachable
221 blocks) we can delete a label that's a target of the vector
222 before deleting the vector itself. */
224 LABEL_NUSES (label
)--;
229 /* Like delete_insn but also purge dead edges from BB. */
232 delete_insn_and_edges (rtx_insn
*insn
)
237 && BLOCK_FOR_INSN (insn
)
238 && BB_END (BLOCK_FOR_INSN (insn
)) == insn
)
242 purge_dead_edges (BLOCK_FOR_INSN (insn
));
245 /* Unlink a chain of insns between START and FINISH, leaving notes
246 that must be paired. If CLEAR_BB is true, we set bb field for
247 insns that cannot be removed to NULL. */
250 delete_insn_chain (rtx start
, rtx finish
, bool clear_bb
)
252 rtx_insn
*prev
, *current
;
254 /* Unchain the insns one by one. It would be quicker to delete all of these
255 with a single unchaining, rather than one at a time, but we need to keep
257 current
= safe_as_a
<rtx_insn
*> (finish
);
260 prev
= PREV_INSN (current
);
261 if (NOTE_P (current
) && !can_delete_note_p (as_a
<rtx_note
*> (current
)))
264 delete_insn (current
);
266 if (clear_bb
&& !current
->deleted ())
267 set_block_for_insn (current
, NULL
);
269 if (current
== start
)
275 /* Create a new basic block consisting of the instructions between HEAD and END
276 inclusive. This function is designed to allow fast BB construction - reuses
277 the note and basic block struct in BB_NOTE, if any and do not grow
278 BASIC_BLOCK chain and should be used directly only by CFG construction code.
279 END can be NULL in to create new empty basic block before HEAD. Both END
280 and HEAD can be NULL to create basic block at the end of INSN chain.
281 AFTER is the basic block we should be put after. */
284 create_basic_block_structure (rtx_insn
*head
, rtx_insn
*end
, rtx_note
*bb_note
,
290 && (bb
= NOTE_BASIC_BLOCK (bb_note
)) != NULL
293 /* If we found an existing note, thread it back onto the chain. */
301 after
= PREV_INSN (head
);
305 if (after
!= bb_note
&& NEXT_INSN (after
) != bb_note
)
306 reorder_insns_nobb (bb_note
, bb_note
, after
);
310 /* Otherwise we must create a note and a basic block structure. */
314 init_rtl_bb_info (bb
);
317 = emit_note_after (NOTE_INSN_BASIC_BLOCK
, get_last_insn ());
318 else if (LABEL_P (head
) && end
)
320 bb_note
= emit_note_after (NOTE_INSN_BASIC_BLOCK
, head
);
326 bb_note
= emit_note_before (NOTE_INSN_BASIC_BLOCK
, head
);
332 NOTE_BASIC_BLOCK (bb_note
) = bb
;
335 /* Always include the bb note in the block. */
336 if (NEXT_INSN (end
) == bb_note
)
341 bb
->index
= last_basic_block_for_fn (cfun
)++;
342 bb
->flags
= BB_NEW
| BB_RTL
;
343 link_block (bb
, after
);
344 SET_BASIC_BLOCK_FOR_FN (cfun
, bb
->index
, bb
);
345 df_bb_refs_record (bb
->index
, false);
346 update_bb_for_insn (bb
);
347 BB_SET_PARTITION (bb
, BB_UNPARTITIONED
);
349 /* Tag the block so that we know it has been used when considering
350 other basic block notes. */
356 /* Create new basic block consisting of instructions in between HEAD and END
357 and place it to the BB chain after block AFTER. END can be NULL to
358 create a new empty basic block before HEAD. Both END and HEAD can be
359 NULL to create basic block at the end of INSN chain. */
362 rtl_create_basic_block (void *headp
, void *endp
, basic_block after
)
364 rtx_insn
*head
= (rtx_insn
*) headp
;
365 rtx_insn
*end
= (rtx_insn
*) endp
;
368 /* Grow the basic block array if needed. */
369 if ((size_t) last_basic_block_for_fn (cfun
)
370 >= basic_block_info_for_fn (cfun
)->length ())
373 (last_basic_block_for_fn (cfun
)
374 + (last_basic_block_for_fn (cfun
) + 3) / 4);
375 vec_safe_grow_cleared (basic_block_info_for_fn (cfun
), new_size
);
378 n_basic_blocks_for_fn (cfun
)++;
380 bb
= create_basic_block_structure (head
, end
, NULL
, after
);
386 cfg_layout_create_basic_block (void *head
, void *end
, basic_block after
)
388 basic_block newbb
= rtl_create_basic_block (head
, end
, after
);
393 /* Delete the insns in a (non-live) block. We physically delete every
394 non-deleted-note insn, and update the flow graph appropriately.
396 Return nonzero if we deleted an exception handler. */
398 /* ??? Preserving all such notes strikes me as wrong. It would be nice
399 to post-process the stream to remove empty blocks, loops, ranges, etc. */
402 rtl_delete_block (basic_block b
)
404 rtx_insn
*insn
, *end
;
406 /* If the head of this block is a CODE_LABEL, then it might be the
407 label for an exception handler which can't be reached. We need
408 to remove the label from the exception_handler_label list. */
411 end
= get_last_bb_insn (b
);
413 /* Selectively delete the entire chain. */
415 delete_insn_chain (insn
, end
, true);
419 fprintf (dump_file
, "deleting block %d\n", b
->index
);
420 df_bb_delete (b
->index
);
423 /* Records the basic block struct in BLOCK_FOR_INSN for every insn. */
426 compute_bb_for_insn (void)
430 FOR_EACH_BB_FN (bb
, cfun
)
432 rtx_insn
*end
= BB_END (bb
);
435 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
437 BLOCK_FOR_INSN (insn
) = bb
;
444 /* Release the basic_block_for_insn array. */
447 free_bb_for_insn (void)
450 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
451 if (!BARRIER_P (insn
))
452 BLOCK_FOR_INSN (insn
) = NULL
;
458 const pass_data pass_data_free_cfg
=
461 "*free_cfg", /* name */
462 OPTGROUP_NONE
, /* optinfo_flags */
464 0, /* properties_required */
465 0, /* properties_provided */
466 PROP_cfg
, /* properties_destroyed */
467 0, /* todo_flags_start */
468 0, /* todo_flags_finish */
471 class pass_free_cfg
: public rtl_opt_pass
474 pass_free_cfg (gcc::context
*ctxt
)
475 : rtl_opt_pass (pass_data_free_cfg
, ctxt
)
478 /* opt_pass methods: */
479 virtual unsigned int execute (function
*);
481 }; // class pass_free_cfg
484 pass_free_cfg::execute (function
*)
487 /* The resource.c machinery uses DF but the CFG isn't guaranteed to be
488 valid at that point so it would be too late to call df_analyze. */
489 if (optimize
> 0 && flag_delayed_branch
)
491 df_note_add_problem ();
496 if (crtl
->has_bb_partition
)
497 insert_section_boundary_note ();
506 make_pass_free_cfg (gcc::context
*ctxt
)
508 return new pass_free_cfg (ctxt
);
511 /* Return RTX to emit after when we want to emit code on the entry of function. */
513 entry_of_function (void)
515 return (n_basic_blocks_for_fn (cfun
) > NUM_FIXED_BLOCKS
?
516 BB_HEAD (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
) : get_insns ());
519 /* Emit INSN at the entry point of the function, ensuring that it is only
520 executed once per function. */
522 emit_insn_at_entry (rtx insn
)
524 edge_iterator ei
= ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
);
525 edge e
= ei_safe_edge (ei
);
526 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
528 insert_insn_on_edge (insn
, e
);
529 commit_edge_insertions ();
532 /* Update BLOCK_FOR_INSN of insns between BEGIN and END
533 (or BARRIER if found) and notify df of the bb change.
534 The insn chain range is inclusive
535 (i.e. both BEGIN and END will be updated. */
538 update_bb_for_insn_chain (rtx_insn
*begin
, rtx_insn
*end
, basic_block bb
)
542 end
= NEXT_INSN (end
);
543 for (insn
= begin
; insn
!= end
; insn
= NEXT_INSN (insn
))
544 if (!BARRIER_P (insn
))
545 df_insn_change_bb (insn
, bb
);
548 /* Update BLOCK_FOR_INSN of insns in BB to BB,
549 and notify df of the change. */
552 update_bb_for_insn (basic_block bb
)
554 update_bb_for_insn_chain (BB_HEAD (bb
), BB_END (bb
), bb
);
558 /* Like active_insn_p, except keep the return value clobber around
559 even after reload. */
562 flow_active_insn_p (const rtx_insn
*insn
)
564 if (active_insn_p (insn
))
567 /* A clobber of the function return value exists for buggy
568 programs that fail to return a value. Its effect is to
569 keep the return value from being live across the entire
570 function. If we allow it to be skipped, we introduce the
571 possibility for register lifetime confusion. */
572 if (GET_CODE (PATTERN (insn
)) == CLOBBER
573 && REG_P (XEXP (PATTERN (insn
), 0))
574 && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn
), 0)))
580 /* Return true if the block has no effect and only forwards control flow to
581 its single destination. */
584 contains_no_active_insn_p (const_basic_block bb
)
588 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
) || bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
589 || !single_succ_p (bb
))
592 for (insn
= BB_HEAD (bb
); insn
!= BB_END (bb
); insn
= NEXT_INSN (insn
))
593 if (INSN_P (insn
) && flow_active_insn_p (insn
))
596 return (!INSN_P (insn
)
597 || (JUMP_P (insn
) && simplejump_p (insn
))
598 || !flow_active_insn_p (insn
));
601 /* Likewise, but protect loop latches, headers and preheaders. */
602 /* FIXME: Make this a cfg hook. */
605 forwarder_block_p (const_basic_block bb
)
607 if (!contains_no_active_insn_p (bb
))
610 /* Protect loop latches, headers and preheaders. */
614 if (bb
->loop_father
->header
== bb
)
616 dest
= EDGE_SUCC (bb
, 0)->dest
;
617 if (dest
->loop_father
->header
== dest
)
624 /* Return nonzero if we can reach target from src by falling through. */
625 /* FIXME: Make this a cfg hook, the result is only valid in cfgrtl mode. */
628 can_fallthru (basic_block src
, basic_block target
)
630 rtx_insn
*insn
= BB_END (src
);
635 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
637 if (src
->next_bb
!= target
)
640 /* ??? Later we may add code to move jump tables offline. */
641 if (tablejump_p (insn
, NULL
, NULL
))
644 FOR_EACH_EDGE (e
, ei
, src
->succs
)
645 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
646 && e
->flags
& EDGE_FALLTHRU
)
649 insn2
= BB_HEAD (target
);
650 if (!active_insn_p (insn2
))
651 insn2
= next_active_insn (insn2
);
653 return next_active_insn (insn
) == insn2
;
656 /* Return nonzero if we could reach target from src by falling through,
657 if the target was made adjacent. If we already have a fall-through
658 edge to the exit block, we can't do that. */
660 could_fall_through (basic_block src
, basic_block target
)
665 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
667 FOR_EACH_EDGE (e
, ei
, src
->succs
)
668 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
669 && e
->flags
& EDGE_FALLTHRU
)
674 /* Return the NOTE_INSN_BASIC_BLOCK of BB. */
676 bb_note (basic_block bb
)
682 note
= NEXT_INSN (note
);
684 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
685 return as_a
<rtx_note
*> (note
);
688 /* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK
689 note associated with the BLOCK. */
692 first_insn_after_basic_block_note (basic_block block
)
696 /* Get the first instruction in the block. */
697 insn
= BB_HEAD (block
);
699 if (insn
== NULL_RTX
)
702 insn
= NEXT_INSN (insn
);
703 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
705 return NEXT_INSN (insn
);
708 /* Creates a new basic block just after basic block BB by splitting
709 everything after specified instruction INSNP. */
712 rtl_split_block (basic_block bb
, void *insnp
)
715 rtx_insn
*insn
= (rtx_insn
*) insnp
;
721 insn
= first_insn_after_basic_block_note (bb
);
725 rtx_insn
*next
= insn
;
727 insn
= PREV_INSN (insn
);
729 /* If the block contains only debug insns, insn would have
730 been NULL in a non-debug compilation, and then we'd end
731 up emitting a DELETED note. For -fcompare-debug
732 stability, emit the note too. */
733 if (insn
!= BB_END (bb
)
734 && DEBUG_INSN_P (next
)
735 && DEBUG_INSN_P (BB_END (bb
)))
737 while (next
!= BB_END (bb
) && DEBUG_INSN_P (next
))
738 next
= NEXT_INSN (next
);
740 if (next
== BB_END (bb
))
741 emit_note_after (NOTE_INSN_DELETED
, next
);
745 insn
= get_last_insn ();
748 /* We probably should check type of the insn so that we do not create
749 inconsistent cfg. It is checked in verify_flow_info anyway, so do not
751 if (insn
== BB_END (bb
))
752 emit_note_after (NOTE_INSN_DELETED
, insn
);
754 /* Create the new basic block. */
755 new_bb
= create_basic_block (NEXT_INSN (insn
), BB_END (bb
), bb
);
756 BB_COPY_PARTITION (new_bb
, bb
);
759 /* Redirect the outgoing edges. */
760 new_bb
->succs
= bb
->succs
;
762 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
765 /* The new block starts off being dirty. */
766 df_set_bb_dirty (bb
);
770 /* Return true if the single edge between blocks A and B is the only place
771 in RTL which holds some unique locus. */
774 unique_locus_on_edge_between_p (basic_block a
, basic_block b
)
776 const location_t goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
777 rtx_insn
*insn
, *end
;
779 if (LOCATION_LOCUS (goto_locus
) == UNKNOWN_LOCATION
)
782 /* First scan block A backward. */
784 end
= PREV_INSN (BB_HEAD (a
));
785 while (insn
!= end
&& (!NONDEBUG_INSN_P (insn
) || !INSN_HAS_LOCATION (insn
)))
786 insn
= PREV_INSN (insn
);
788 if (insn
!= end
&& INSN_LOCATION (insn
) == goto_locus
)
791 /* Then scan block B forward. */
795 end
= NEXT_INSN (BB_END (b
));
796 while (insn
!= end
&& !NONDEBUG_INSN_P (insn
))
797 insn
= NEXT_INSN (insn
);
799 if (insn
!= end
&& INSN_HAS_LOCATION (insn
)
800 && INSN_LOCATION (insn
) == goto_locus
)
807 /* If the single edge between blocks A and B is the only place in RTL which
808 holds some unique locus, emit a nop with that locus between the blocks. */
811 emit_nop_for_unique_locus_between (basic_block a
, basic_block b
)
813 if (!unique_locus_on_edge_between_p (a
, b
))
816 BB_END (a
) = emit_insn_after_noloc (gen_nop (), BB_END (a
), a
);
817 INSN_LOCATION (BB_END (a
)) = EDGE_SUCC (a
, 0)->goto_locus
;
820 /* Blocks A and B are to be merged into a single block A. The insns
821 are already contiguous. */
824 rtl_merge_blocks (basic_block a
, basic_block b
)
826 rtx_insn
*b_head
= BB_HEAD (b
), *b_end
= BB_END (b
), *a_end
= BB_END (a
);
827 rtx_insn
*del_first
= NULL
, *del_last
= NULL
;
828 rtx_insn
*b_debug_start
= b_end
, *b_debug_end
= b_end
;
829 bool forwarder_p
= (b
->flags
& BB_FORWARDER_BLOCK
) != 0;
833 fprintf (dump_file
, "Merging block %d into block %d...\n", b
->index
,
836 while (DEBUG_INSN_P (b_end
))
837 b_end
= PREV_INSN (b_debug_start
= b_end
);
839 /* If there was a CODE_LABEL beginning B, delete it. */
840 if (LABEL_P (b_head
))
842 /* Detect basic blocks with nothing but a label. This can happen
843 in particular at the end of a function. */
847 del_first
= del_last
= b_head
;
848 b_head
= NEXT_INSN (b_head
);
851 /* Delete the basic block note and handle blocks containing just that
853 if (NOTE_INSN_BASIC_BLOCK_P (b_head
))
861 b_head
= NEXT_INSN (b_head
);
864 /* If there was a jump out of A, delete it. */
869 for (prev
= PREV_INSN (a_end
); ; prev
= PREV_INSN (prev
))
871 || NOTE_INSN_BASIC_BLOCK_P (prev
)
872 || prev
== BB_HEAD (a
))
877 /* If this was a conditional jump, we need to also delete
878 the insn that set cc0. */
879 if (HAVE_cc0
&& only_sets_cc0_p (prev
))
881 rtx_insn
*tmp
= prev
;
883 prev
= prev_nonnote_insn (prev
);
889 a_end
= PREV_INSN (del_first
);
891 else if (BARRIER_P (NEXT_INSN (a_end
)))
892 del_first
= NEXT_INSN (a_end
);
894 /* Delete everything marked above as well as crap that might be
895 hanging out between the two blocks. */
897 BB_HEAD (b
) = b_empty
? NULL
: b_head
;
898 delete_insn_chain (del_first
, del_last
, true);
900 /* When not optimizing and the edge is the only place in RTL which holds
901 some unique locus, emit a nop with that locus in between. */
904 emit_nop_for_unique_locus_between (a
, b
);
908 /* Reassociate the insns of B with A. */
911 update_bb_for_insn_chain (a_end
, b_debug_end
, a
);
913 BB_END (a
) = b_debug_end
;
916 else if (b_end
!= b_debug_end
)
918 /* Move any deleted labels and other notes between the end of A
919 and the debug insns that make up B after the debug insns,
920 bringing the debug insns into A while keeping the notes after
922 if (NEXT_INSN (a_end
) != b_debug_start
)
923 reorder_insns_nobb (NEXT_INSN (a_end
), PREV_INSN (b_debug_start
),
925 update_bb_for_insn_chain (b_debug_start
, b_debug_end
, a
);
926 BB_END (a
) = b_debug_end
;
929 df_bb_delete (b
->index
);
931 /* If B was a forwarder block, propagate the locus on the edge. */
933 && LOCATION_LOCUS (EDGE_SUCC (b
, 0)->goto_locus
) == UNKNOWN_LOCATION
)
934 EDGE_SUCC (b
, 0)->goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
937 fprintf (dump_file
, "Merged blocks %d and %d.\n", a
->index
, b
->index
);
941 /* Return true when block A and B can be merged. */
944 rtl_can_merge_blocks (basic_block a
, basic_block b
)
946 /* If we are partitioning hot/cold basic blocks, we don't want to
947 mess up unconditional or indirect jumps that cross between hot
950 Basic block partitioning may result in some jumps that appear to
951 be optimizable (or blocks that appear to be mergeable), but which really
952 must be left untouched (they are required to make it safely across
953 partition boundaries). See the comments at the top of
954 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
956 if (BB_PARTITION (a
) != BB_PARTITION (b
))
959 /* Protect the loop latches. */
960 if (current_loops
&& b
->loop_father
->latch
== b
)
963 /* There must be exactly one edge in between the blocks. */
964 return (single_succ_p (a
)
965 && single_succ (a
) == b
968 /* Must be simple edge. */
969 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
971 && a
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
972 && b
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
973 /* If the jump insn has side effects,
974 we can't kill the edge. */
975 && (!JUMP_P (BB_END (a
))
977 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
980 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
984 block_label (basic_block block
)
986 if (block
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
989 if (!LABEL_P (BB_HEAD (block
)))
991 BB_HEAD (block
) = emit_label_before (gen_label_rtx (), BB_HEAD (block
));
994 return as_a
<rtx_code_label
*> (BB_HEAD (block
));
997 /* Attempt to perform edge redirection by replacing possibly complex jump
998 instruction by unconditional jump or removing jump completely. This can
999 apply only if all edges now point to the same block. The parameters and
1000 return values are equivalent to redirect_edge_and_branch. */
1003 try_redirect_by_replacing_jump (edge e
, basic_block target
, bool in_cfglayout
)
1005 basic_block src
= e
->src
;
1006 rtx_insn
*insn
= BB_END (src
), *kill_from
;
1010 /* If we are partitioning hot/cold basic blocks, we don't want to
1011 mess up unconditional or indirect jumps that cross between hot
1014 Basic block partitioning may result in some jumps that appear to
1015 be optimizable (or blocks that appear to be mergeable), but which really
1016 must be left untouched (they are required to make it safely across
1017 partition boundaries). See the comments at the top of
1018 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
1020 if (BB_PARTITION (src
) != BB_PARTITION (target
))
1023 /* We can replace or remove a complex jump only when we have exactly
1024 two edges. Also, if we have exactly one outgoing edge, we can
1026 if (EDGE_COUNT (src
->succs
) >= 3
1027 /* Verify that all targets will be TARGET. Specifically, the
1028 edge that is not E must also go to TARGET. */
1029 || (EDGE_COUNT (src
->succs
) == 2
1030 && EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
!= target
))
1033 if (!onlyjump_p (insn
))
1035 if ((!optimize
|| reload_completed
) && tablejump_p (insn
, NULL
, NULL
))
1038 /* Avoid removing branch with side effects. */
1039 set
= single_set (insn
);
1040 if (!set
|| side_effects_p (set
))
1043 /* In case we zap a conditional jump, we'll need to kill
1044 the cc0 setter too. */
1046 if (HAVE_cc0
&& reg_mentioned_p (cc0_rtx
, PATTERN (insn
))
1047 && only_sets_cc0_p (PREV_INSN (insn
)))
1048 kill_from
= PREV_INSN (insn
);
1050 /* See if we can create the fallthru edge. */
1051 if (in_cfglayout
|| can_fallthru (src
, target
))
1054 fprintf (dump_file
, "Removing jump %i.\n", INSN_UID (insn
));
1057 /* Selectively unlink whole insn chain. */
1060 rtx_insn
*insn
= BB_FOOTER (src
);
1062 delete_insn_chain (kill_from
, BB_END (src
), false);
1064 /* Remove barriers but keep jumptables. */
1067 if (BARRIER_P (insn
))
1069 if (PREV_INSN (insn
))
1070 SET_NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
1072 BB_FOOTER (src
) = NEXT_INSN (insn
);
1073 if (NEXT_INSN (insn
))
1074 SET_PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
1078 insn
= NEXT_INSN (insn
);
1082 delete_insn_chain (kill_from
, PREV_INSN (BB_HEAD (target
)),
1086 /* If this already is simplejump, redirect it. */
1087 else if (simplejump_p (insn
))
1089 if (e
->dest
== target
)
1092 fprintf (dump_file
, "Redirecting jump %i from %i to %i.\n",
1093 INSN_UID (insn
), e
->dest
->index
, target
->index
);
1094 if (!redirect_jump (as_a
<rtx_jump_insn
*> (insn
),
1095 block_label (target
), 0))
1097 gcc_assert (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
));
1102 /* Cannot do anything for target exit block. */
1103 else if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1106 /* Or replace possibly complicated jump insn by simple jump insn. */
1109 rtx_code_label
*target_label
= block_label (target
);
1112 rtx_jump_table_data
*table
;
1114 emit_jump_insn_after_noloc (targetm
.gen_jump (target_label
), insn
);
1115 JUMP_LABEL (BB_END (src
)) = target_label
;
1116 LABEL_NUSES (target_label
)++;
1118 fprintf (dump_file
, "Replacing insn %i by jump %i\n",
1119 INSN_UID (insn
), INSN_UID (BB_END (src
)));
1122 delete_insn_chain (kill_from
, insn
, false);
1124 /* Recognize a tablejump that we are converting to a
1125 simple jump and remove its associated CODE_LABEL
1126 and ADDR_VEC or ADDR_DIFF_VEC. */
1127 if (tablejump_p (insn
, &label
, &table
))
1128 delete_insn_chain (label
, table
, false);
1130 barrier
= next_nonnote_insn (BB_END (src
));
1131 if (!barrier
|| !BARRIER_P (barrier
))
1132 emit_barrier_after (BB_END (src
));
1135 if (barrier
!= NEXT_INSN (BB_END (src
)))
1137 /* Move the jump before barrier so that the notes
1138 which originally were or were created before jump table are
1139 inside the basic block. */
1140 rtx_insn
*new_insn
= BB_END (src
);
1142 update_bb_for_insn_chain (NEXT_INSN (BB_END (src
)),
1143 PREV_INSN (barrier
), src
);
1145 SET_NEXT_INSN (PREV_INSN (new_insn
)) = NEXT_INSN (new_insn
);
1146 SET_PREV_INSN (NEXT_INSN (new_insn
)) = PREV_INSN (new_insn
);
1148 SET_NEXT_INSN (new_insn
) = barrier
;
1149 SET_NEXT_INSN (PREV_INSN (barrier
)) = new_insn
;
1151 SET_PREV_INSN (new_insn
) = PREV_INSN (barrier
);
1152 SET_PREV_INSN (barrier
) = new_insn
;
1157 /* Keep only one edge out and set proper flags. */
1158 if (!single_succ_p (src
))
1160 gcc_assert (single_succ_p (src
));
1162 e
= single_succ_edge (src
);
1164 e
->flags
= EDGE_FALLTHRU
;
1168 e
->probability
= REG_BR_PROB_BASE
;
1169 e
->count
= src
->count
;
1171 if (e
->dest
!= target
)
1172 redirect_edge_succ (e
, target
);
1176 /* Subroutine of redirect_branch_edge that tries to patch the jump
1177 instruction INSN so that it reaches block NEW. Do this
1178 only when it originally reached block OLD. Return true if this
1179 worked or the original target wasn't OLD, return false if redirection
1183 patch_jump_insn (rtx_insn
*insn
, rtx_insn
*old_label
, basic_block new_bb
)
1185 rtx_jump_table_data
*table
;
1187 /* Recognize a tablejump and adjust all matching cases. */
1188 if (tablejump_p (insn
, NULL
, &table
))
1192 rtx_code_label
*new_label
= block_label (new_bb
);
1194 if (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1196 vec
= table
->get_labels ();
1198 for (j
= GET_NUM_ELEM (vec
) - 1; j
>= 0; --j
)
1199 if (XEXP (RTVEC_ELT (vec
, j
), 0) == old_label
)
1201 RTVEC_ELT (vec
, j
) = gen_rtx_LABEL_REF (Pmode
, new_label
);
1202 --LABEL_NUSES (old_label
);
1203 ++LABEL_NUSES (new_label
);
1206 /* Handle casesi dispatch insns. */
1207 if ((tmp
= single_set (insn
)) != NULL
1208 && SET_DEST (tmp
) == pc_rtx
1209 && GET_CODE (SET_SRC (tmp
)) == IF_THEN_ELSE
1210 && GET_CODE (XEXP (SET_SRC (tmp
), 2)) == LABEL_REF
1211 && LABEL_REF_LABEL (XEXP (SET_SRC (tmp
), 2)) == old_label
)
1213 XEXP (SET_SRC (tmp
), 2) = gen_rtx_LABEL_REF (Pmode
,
1215 --LABEL_NUSES (old_label
);
1216 ++LABEL_NUSES (new_label
);
1219 else if ((tmp
= extract_asm_operands (PATTERN (insn
))) != NULL
)
1221 int i
, n
= ASM_OPERANDS_LABEL_LENGTH (tmp
);
1224 if (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1226 rtx_code_label
*new_label
= block_label (new_bb
);
1228 for (i
= 0; i
< n
; ++i
)
1230 rtx old_ref
= ASM_OPERANDS_LABEL (tmp
, i
);
1231 gcc_assert (GET_CODE (old_ref
) == LABEL_REF
);
1232 if (XEXP (old_ref
, 0) == old_label
)
1234 ASM_OPERANDS_LABEL (tmp
, i
)
1235 = gen_rtx_LABEL_REF (Pmode
, new_label
);
1236 --LABEL_NUSES (old_label
);
1237 ++LABEL_NUSES (new_label
);
1241 if (JUMP_LABEL (insn
) == old_label
)
1243 JUMP_LABEL (insn
) = new_label
;
1244 note
= find_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1246 remove_note (insn
, note
);
1250 note
= find_reg_note (insn
, REG_LABEL_TARGET
, old_label
);
1252 remove_note (insn
, note
);
1253 if (JUMP_LABEL (insn
) != new_label
1254 && !find_reg_note (insn
, REG_LABEL_TARGET
, new_label
))
1255 add_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1257 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, old_label
))
1259 XEXP (note
, 0) = new_label
;
1263 /* ?? We may play the games with moving the named labels from
1264 one basic block to the other in case only one computed_jump is
1266 if (computed_jump_p (insn
)
1267 /* A return instruction can't be redirected. */
1268 || returnjump_p (insn
))
1271 if (!currently_expanding_to_rtl
|| JUMP_LABEL (insn
) == old_label
)
1273 /* If the insn doesn't go where we think, we're confused. */
1274 gcc_assert (JUMP_LABEL (insn
) == old_label
);
1276 /* If the substitution doesn't succeed, die. This can happen
1277 if the back end emitted unrecognizable instructions or if
1278 target is exit block on some arches. */
1279 if (!redirect_jump (as_a
<rtx_jump_insn
*> (insn
),
1280 block_label (new_bb
), 0))
1282 gcc_assert (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
));
1291 /* Redirect edge representing branch of (un)conditional jump or tablejump,
1294 redirect_branch_edge (edge e
, basic_block target
)
1296 rtx_insn
*old_label
= BB_HEAD (e
->dest
);
1297 basic_block src
= e
->src
;
1298 rtx_insn
*insn
= BB_END (src
);
1300 /* We can only redirect non-fallthru edges of jump insn. */
1301 if (e
->flags
& EDGE_FALLTHRU
)
1303 else if (!JUMP_P (insn
) && !currently_expanding_to_rtl
)
1306 if (!currently_expanding_to_rtl
)
1308 if (!patch_jump_insn (as_a
<rtx_jump_insn
*> (insn
), old_label
, target
))
1312 /* When expanding this BB might actually contain multiple
1313 jumps (i.e. not yet split by find_many_sub_basic_blocks).
1314 Redirect all of those that match our label. */
1315 FOR_BB_INSNS (src
, insn
)
1316 if (JUMP_P (insn
) && !patch_jump_insn (as_a
<rtx_jump_insn
*> (insn
),
1321 fprintf (dump_file
, "Edge %i->%i redirected to %i\n",
1322 e
->src
->index
, e
->dest
->index
, target
->index
);
1324 if (e
->dest
!= target
)
1325 e
= redirect_edge_succ_nodup (e
, target
);
1330 /* Called when edge E has been redirected to a new destination,
1331 in order to update the region crossing flag on the edge and
1335 fixup_partition_crossing (edge e
)
1337 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) || e
->dest
1338 == EXIT_BLOCK_PTR_FOR_FN (cfun
))
1340 /* If we redirected an existing edge, it may already be marked
1341 crossing, even though the new src is missing a reg crossing note.
1342 But make sure reg crossing note doesn't already exist before
1344 if (BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
))
1346 e
->flags
|= EDGE_CROSSING
;
1347 if (JUMP_P (BB_END (e
->src
))
1348 && !CROSSING_JUMP_P (BB_END (e
->src
)))
1349 CROSSING_JUMP_P (BB_END (e
->src
)) = 1;
1351 else if (BB_PARTITION (e
->src
) == BB_PARTITION (e
->dest
))
1353 e
->flags
&= ~EDGE_CROSSING
;
1354 /* Remove the section crossing note from jump at end of
1355 src if it exists, and if no other successors are
1357 if (JUMP_P (BB_END (e
->src
)) && CROSSING_JUMP_P (BB_END (e
->src
)))
1359 bool has_crossing_succ
= false;
1362 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
1364 has_crossing_succ
|= (e2
->flags
& EDGE_CROSSING
);
1365 if (has_crossing_succ
)
1368 if (!has_crossing_succ
)
1369 CROSSING_JUMP_P (BB_END (e
->src
)) = 0;
1374 /* Called when block BB has been reassigned to the cold partition,
1375 because it is now dominated by another cold block,
1376 to ensure that the region crossing attributes are updated. */
1379 fixup_new_cold_bb (basic_block bb
)
1384 /* This is called when a hot bb is found to now be dominated
1385 by a cold bb and therefore needs to become cold. Therefore,
1386 its preds will no longer be region crossing. Any non-dominating
1387 preds that were previously hot would also have become cold
1388 in the caller for the same region. Any preds that were previously
1389 region-crossing will be adjusted in fixup_partition_crossing. */
1390 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1392 fixup_partition_crossing (e
);
1395 /* Possibly need to make bb's successor edges region crossing,
1396 or remove stale region crossing. */
1397 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1399 /* We can't have fall-through edges across partition boundaries.
1400 Note that force_nonfallthru will do any necessary partition
1401 boundary fixup by calling fixup_partition_crossing itself. */
1402 if ((e
->flags
& EDGE_FALLTHRU
)
1403 && BB_PARTITION (bb
) != BB_PARTITION (e
->dest
)
1404 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1405 force_nonfallthru (e
);
1407 fixup_partition_crossing (e
);
1411 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
1412 expense of adding new instructions or reordering basic blocks.
1414 Function can be also called with edge destination equivalent to the TARGET.
1415 Then it should try the simplifications and do nothing if none is possible.
1417 Return edge representing the branch if transformation succeeded. Return NULL
1419 We still return NULL in case E already destinated TARGET and we didn't
1420 managed to simplify instruction stream. */
1423 rtl_redirect_edge_and_branch (edge e
, basic_block target
)
1426 basic_block src
= e
->src
;
1427 basic_block dest
= e
->dest
;
1429 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
1435 if ((ret
= try_redirect_by_replacing_jump (e
, target
, false)) != NULL
)
1437 df_set_bb_dirty (src
);
1438 fixup_partition_crossing (ret
);
1442 ret
= redirect_branch_edge (e
, target
);
1446 df_set_bb_dirty (src
);
1447 fixup_partition_crossing (ret
);
1451 /* Emit a barrier after BB, into the footer if we are in CFGLAYOUT mode. */
1454 emit_barrier_after_bb (basic_block bb
)
1456 rtx_barrier
*barrier
= emit_barrier_after (BB_END (bb
));
1457 gcc_assert (current_ir_type () == IR_RTL_CFGRTL
1458 || current_ir_type () == IR_RTL_CFGLAYOUT
);
1459 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
1461 rtx_insn
*insn
= unlink_insn_chain (barrier
, barrier
);
1465 rtx_insn
*footer_tail
= BB_FOOTER (bb
);
1467 while (NEXT_INSN (footer_tail
))
1468 footer_tail
= NEXT_INSN (footer_tail
);
1469 if (!BARRIER_P (footer_tail
))
1471 SET_NEXT_INSN (footer_tail
) = insn
;
1472 SET_PREV_INSN (insn
) = footer_tail
;
1476 BB_FOOTER (bb
) = insn
;
1480 /* Like force_nonfallthru below, but additionally performs redirection
1481 Used by redirect_edge_and_branch_force. JUMP_LABEL is used only
1482 when redirecting to the EXIT_BLOCK, it is either ret_rtx or
1483 simple_return_rtx, indicating which kind of returnjump to create.
1484 It should be NULL otherwise. */
1487 force_nonfallthru_and_redirect (edge e
, basic_block target
, rtx jump_label
)
1489 basic_block jump_block
, new_bb
= NULL
, src
= e
->src
;
1492 int abnormal_edge_flags
= 0;
1493 bool asm_goto_edge
= false;
1496 /* In the case the last instruction is conditional jump to the next
1497 instruction, first redirect the jump itself and then continue
1498 by creating a basic block afterwards to redirect fallthru edge. */
1499 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1500 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1501 && any_condjump_p (BB_END (e
->src
))
1502 && JUMP_LABEL (BB_END (e
->src
)) == BB_HEAD (e
->dest
))
1505 edge b
= unchecked_make_edge (e
->src
, target
, 0);
1508 redirected
= redirect_jump (as_a
<rtx_jump_insn
*> (BB_END (e
->src
)),
1509 block_label (target
), 0);
1510 gcc_assert (redirected
);
1512 note
= find_reg_note (BB_END (e
->src
), REG_BR_PROB
, NULL_RTX
);
1515 int prob
= XINT (note
, 0);
1517 b
->probability
= prob
;
1518 /* Update this to use GCOV_COMPUTE_SCALE. */
1519 b
->count
= e
->count
* prob
/ REG_BR_PROB_BASE
;
1520 e
->probability
-= e
->probability
;
1521 e
->count
-= b
->count
;
1522 if (e
->probability
< 0)
1529 if (e
->flags
& EDGE_ABNORMAL
)
1531 /* Irritating special case - fallthru edge to the same block as abnormal
1533 We can't redirect abnormal edge, but we still can split the fallthru
1534 one and create separate abnormal edge to original destination.
1535 This allows bb-reorder to make such edge non-fallthru. */
1536 gcc_assert (e
->dest
== target
);
1537 abnormal_edge_flags
= e
->flags
& ~EDGE_FALLTHRU
;
1538 e
->flags
&= EDGE_FALLTHRU
;
1542 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
1543 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1545 /* We can't redirect the entry block. Create an empty block
1546 at the start of the function which we use to add the new
1552 basic_block bb
= create_basic_block (BB_HEAD (e
->dest
), NULL
,
1553 ENTRY_BLOCK_PTR_FOR_FN (cfun
));
1555 /* Change the existing edge's source to be the new block, and add
1556 a new edge from the entry block to the new block. */
1558 for (ei
= ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
);
1559 (tmp
= ei_safe_edge (ei
)); )
1563 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
->unordered_remove (ei
.index
);
1573 vec_safe_push (bb
->succs
, e
);
1574 make_single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
), bb
,
1579 /* If e->src ends with asm goto, see if any of the ASM_OPERANDS_LABELs
1580 don't point to the target or fallthru label. */
1581 if (JUMP_P (BB_END (e
->src
))
1582 && target
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1583 && (e
->flags
& EDGE_FALLTHRU
)
1584 && (note
= extract_asm_operands (PATTERN (BB_END (e
->src
)))))
1586 int i
, n
= ASM_OPERANDS_LABEL_LENGTH (note
);
1587 bool adjust_jump_target
= false;
1589 for (i
= 0; i
< n
; ++i
)
1591 if (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) == BB_HEAD (e
->dest
))
1593 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0))--;
1594 XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) = block_label (target
);
1595 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0))++;
1596 adjust_jump_target
= true;
1598 if (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) == BB_HEAD (target
))
1599 asm_goto_edge
= true;
1601 if (adjust_jump_target
)
1603 rtx_insn
*insn
= BB_END (e
->src
);
1605 rtx_insn
*old_label
= BB_HEAD (e
->dest
);
1606 rtx_insn
*new_label
= BB_HEAD (target
);
1608 if (JUMP_LABEL (insn
) == old_label
)
1610 JUMP_LABEL (insn
) = new_label
;
1611 note
= find_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1613 remove_note (insn
, note
);
1617 note
= find_reg_note (insn
, REG_LABEL_TARGET
, old_label
);
1619 remove_note (insn
, note
);
1620 if (JUMP_LABEL (insn
) != new_label
1621 && !find_reg_note (insn
, REG_LABEL_TARGET
, new_label
))
1622 add_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1624 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, old_label
))
1626 XEXP (note
, 0) = new_label
;
1630 if (EDGE_COUNT (e
->src
->succs
) >= 2 || abnormal_edge_flags
|| asm_goto_edge
)
1633 gcov_type count
= e
->count
;
1634 int probability
= e
->probability
;
1635 /* Create the new structures. */
1637 /* If the old block ended with a tablejump, skip its table
1638 by searching forward from there. Otherwise start searching
1639 forward from the last instruction of the old block. */
1640 rtx_jump_table_data
*table
;
1641 if (tablejump_p (BB_END (e
->src
), NULL
, &table
))
1644 new_head
= BB_END (e
->src
);
1645 new_head
= NEXT_INSN (new_head
);
1647 jump_block
= create_basic_block (new_head
, NULL
, e
->src
);
1648 jump_block
->count
= count
;
1649 jump_block
->frequency
= EDGE_FREQUENCY (e
);
1651 /* Make sure new block ends up in correct hot/cold section. */
1653 BB_COPY_PARTITION (jump_block
, e
->src
);
1656 new_edge
= make_edge (e
->src
, jump_block
, EDGE_FALLTHRU
);
1657 new_edge
->probability
= probability
;
1658 new_edge
->count
= count
;
1660 /* Redirect old edge. */
1661 redirect_edge_pred (e
, jump_block
);
1662 e
->probability
= REG_BR_PROB_BASE
;
1664 /* If e->src was previously region crossing, it no longer is
1665 and the reg crossing note should be removed. */
1666 fixup_partition_crossing (new_edge
);
1668 /* If asm goto has any label refs to target's label,
1669 add also edge from asm goto bb to target. */
1672 new_edge
->probability
/= 2;
1673 new_edge
->count
/= 2;
1674 jump_block
->count
/= 2;
1675 jump_block
->frequency
/= 2;
1676 new_edge
= make_edge (new_edge
->src
, target
,
1677 e
->flags
& ~EDGE_FALLTHRU
);
1678 new_edge
->probability
= probability
- probability
/ 2;
1679 new_edge
->count
= count
- count
/ 2;
1682 new_bb
= jump_block
;
1685 jump_block
= e
->src
;
1687 loc
= e
->goto_locus
;
1688 e
->flags
&= ~EDGE_FALLTHRU
;
1689 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1691 if (jump_label
== ret_rtx
)
1692 emit_jump_insn_after_setloc (targetm
.gen_return (),
1693 BB_END (jump_block
), loc
);
1696 gcc_assert (jump_label
== simple_return_rtx
);
1697 emit_jump_insn_after_setloc (targetm
.gen_simple_return (),
1698 BB_END (jump_block
), loc
);
1700 set_return_jump_label (BB_END (jump_block
));
1704 rtx_code_label
*label
= block_label (target
);
1705 emit_jump_insn_after_setloc (targetm
.gen_jump (label
),
1706 BB_END (jump_block
), loc
);
1707 JUMP_LABEL (BB_END (jump_block
)) = label
;
1708 LABEL_NUSES (label
)++;
1711 /* We might be in cfg layout mode, and if so, the following routine will
1712 insert the barrier correctly. */
1713 emit_barrier_after_bb (jump_block
);
1714 redirect_edge_succ_nodup (e
, target
);
1716 if (abnormal_edge_flags
)
1717 make_edge (src
, target
, abnormal_edge_flags
);
1719 df_mark_solutions_dirty ();
1720 fixup_partition_crossing (e
);
1724 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1725 (and possibly create new basic block) to make edge non-fallthru.
1726 Return newly created BB or NULL if none. */
1729 rtl_force_nonfallthru (edge e
)
1731 return force_nonfallthru_and_redirect (e
, e
->dest
, NULL_RTX
);
1734 /* Redirect edge even at the expense of creating new jump insn or
1735 basic block. Return new basic block if created, NULL otherwise.
1736 Conversion must be possible. */
1739 rtl_redirect_edge_and_branch_force (edge e
, basic_block target
)
1741 if (redirect_edge_and_branch (e
, target
)
1742 || e
->dest
== target
)
1745 /* In case the edge redirection failed, try to force it to be non-fallthru
1746 and redirect newly created simplejump. */
1747 df_set_bb_dirty (e
->src
);
1748 return force_nonfallthru_and_redirect (e
, target
, NULL_RTX
);
1751 /* The given edge should potentially be a fallthru edge. If that is in
1752 fact true, delete the jump and barriers that are in the way. */
1755 rtl_tidy_fallthru_edge (edge e
)
1758 basic_block b
= e
->src
, c
= b
->next_bb
;
1760 /* ??? In a late-running flow pass, other folks may have deleted basic
1761 blocks by nopping out blocks, leaving multiple BARRIERs between here
1762 and the target label. They ought to be chastised and fixed.
1764 We can also wind up with a sequence of undeletable labels between
1765 one block and the next.
1767 So search through a sequence of barriers, labels, and notes for
1768 the head of block C and assert that we really do fall through. */
1770 for (q
= NEXT_INSN (BB_END (b
)); q
!= BB_HEAD (c
); q
= NEXT_INSN (q
))
1774 /* Remove what will soon cease being the jump insn from the source block.
1775 If block B consisted only of this single jump, turn it into a deleted
1780 && (any_uncondjump_p (q
)
1781 || single_succ_p (b
)))
1784 rtx_jump_table_data
*table
;
1786 if (tablejump_p (q
, &label
, &table
))
1788 /* The label is likely mentioned in some instruction before
1789 the tablejump and might not be DCEd, so turn it into
1790 a note instead and move before the tablejump that is going to
1792 const char *name
= LABEL_NAME (label
);
1793 PUT_CODE (label
, NOTE
);
1794 NOTE_KIND (label
) = NOTE_INSN_DELETED_LABEL
;
1795 NOTE_DELETED_LABEL_NAME (label
) = name
;
1796 rtx_insn
*lab
= safe_as_a
<rtx_insn
*> (label
);
1797 reorder_insns (lab
, lab
, PREV_INSN (q
));
1798 delete_insn (table
);
1801 /* If this was a conditional jump, we need to also delete
1802 the insn that set cc0. */
1803 if (HAVE_cc0
&& any_condjump_p (q
) && only_sets_cc0_p (PREV_INSN (q
)))
1809 /* Selectively unlink the sequence. */
1810 if (q
!= PREV_INSN (BB_HEAD (c
)))
1811 delete_insn_chain (NEXT_INSN (q
), PREV_INSN (BB_HEAD (c
)), false);
1813 e
->flags
|= EDGE_FALLTHRU
;
1816 /* Should move basic block BB after basic block AFTER. NIY. */
1819 rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED
,
1820 basic_block after ATTRIBUTE_UNUSED
)
1825 /* Locate the last bb in the same partition as START_BB. */
1828 last_bb_in_partition (basic_block start_bb
)
1831 FOR_BB_BETWEEN (bb
, start_bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
1833 if (BB_PARTITION (start_bb
) != BB_PARTITION (bb
->next_bb
))
1836 /* Return bb before the exit block. */
1840 /* Split a (typically critical) edge. Return the new block.
1841 The edge must not be abnormal.
1843 ??? The code generally expects to be called on critical edges.
1844 The case of a block ending in an unconditional jump to a
1845 block with multiple predecessors is not handled optimally. */
1848 rtl_split_edge (edge edge_in
)
1850 basic_block bb
, new_bb
;
1853 /* Abnormal edges cannot be split. */
1854 gcc_assert (!(edge_in
->flags
& EDGE_ABNORMAL
));
1856 /* We are going to place the new block in front of edge destination.
1857 Avoid existence of fallthru predecessors. */
1858 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1860 edge e
= find_fallthru_edge (edge_in
->dest
->preds
);
1863 force_nonfallthru (e
);
1866 /* Create the basic block note. */
1867 if (edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1868 before
= BB_HEAD (edge_in
->dest
);
1872 /* If this is a fall through edge to the exit block, the blocks might be
1873 not adjacent, and the right place is after the source. */
1874 if ((edge_in
->flags
& EDGE_FALLTHRU
)
1875 && edge_in
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1877 before
= NEXT_INSN (BB_END (edge_in
->src
));
1878 bb
= create_basic_block (before
, NULL
, edge_in
->src
);
1879 BB_COPY_PARTITION (bb
, edge_in
->src
);
1883 if (edge_in
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1885 bb
= create_basic_block (before
, NULL
, edge_in
->dest
->prev_bb
);
1886 BB_COPY_PARTITION (bb
, edge_in
->dest
);
1890 basic_block after
= edge_in
->dest
->prev_bb
;
1891 /* If this is post-bb reordering, and the edge crosses a partition
1892 boundary, the new block needs to be inserted in the bb chain
1893 at the end of the src partition (since we put the new bb into
1894 that partition, see below). Otherwise we may end up creating
1895 an extra partition crossing in the chain, which is illegal.
1896 It can't go after the src, because src may have a fall-through
1897 to a different block. */
1898 if (crtl
->bb_reorder_complete
1899 && (edge_in
->flags
& EDGE_CROSSING
))
1901 after
= last_bb_in_partition (edge_in
->src
);
1902 before
= get_last_bb_insn (after
);
1903 /* The instruction following the last bb in partition should
1904 be a barrier, since it cannot end in a fall-through. */
1905 gcc_checking_assert (BARRIER_P (before
));
1906 before
= NEXT_INSN (before
);
1908 bb
= create_basic_block (before
, NULL
, after
);
1909 /* Put the split bb into the src partition, to avoid creating
1910 a situation where a cold bb dominates a hot bb, in the case
1911 where src is cold and dest is hot. The src will dominate
1912 the new bb (whereas it might not have dominated dest). */
1913 BB_COPY_PARTITION (bb
, edge_in
->src
);
1917 make_single_succ_edge (bb
, edge_in
->dest
, EDGE_FALLTHRU
);
1919 /* Can't allow a region crossing edge to be fallthrough. */
1920 if (BB_PARTITION (bb
) != BB_PARTITION (edge_in
->dest
)
1921 && edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1923 new_bb
= force_nonfallthru (single_succ_edge (bb
));
1924 gcc_assert (!new_bb
);
1927 /* For non-fallthru edges, we must adjust the predecessor's
1928 jump instruction to target our new block. */
1929 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1931 edge redirected
= redirect_edge_and_branch (edge_in
, bb
);
1932 gcc_assert (redirected
);
1936 if (edge_in
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1938 /* For asm goto even splitting of fallthru edge might
1939 need insn patching, as other labels might point to the
1941 rtx_insn
*last
= BB_END (edge_in
->src
);
1944 && edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1945 && extract_asm_operands (PATTERN (last
)) != NULL_RTX
1946 && patch_jump_insn (last
, before
, bb
))
1947 df_set_bb_dirty (edge_in
->src
);
1949 redirect_edge_succ (edge_in
, bb
);
1955 /* Queue instructions for insertion on an edge between two basic blocks.
1956 The new instructions and basic blocks (if any) will not appear in the
1957 CFG until commit_edge_insertions is called. */
1960 insert_insn_on_edge (rtx pattern
, edge e
)
1962 /* We cannot insert instructions on an abnormal critical edge.
1963 It will be easier to find the culprit if we die now. */
1964 gcc_assert (!((e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
)));
1966 if (e
->insns
.r
== NULL_RTX
)
1969 push_to_sequence (e
->insns
.r
);
1971 emit_insn (pattern
);
1973 e
->insns
.r
= get_insns ();
1977 /* Update the CFG for the instructions queued on edge E. */
1980 commit_one_edge_insertion (edge e
)
1982 rtx_insn
*before
= NULL
, *after
= NULL
, *insns
, *tmp
, *last
;
1985 /* Pull the insns off the edge now since the edge might go away. */
1989 /* Figure out where to put these insns. If the destination has
1990 one predecessor, insert there. Except for the exit block. */
1991 if (single_pred_p (e
->dest
) && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1995 /* Get the location correct wrt a code label, and "nice" wrt
1996 a basic block note, and before everything else. */
1999 tmp
= NEXT_INSN (tmp
);
2000 if (NOTE_INSN_BASIC_BLOCK_P (tmp
))
2001 tmp
= NEXT_INSN (tmp
);
2002 if (tmp
== BB_HEAD (bb
))
2005 after
= PREV_INSN (tmp
);
2007 after
= get_last_insn ();
2010 /* If the source has one successor and the edge is not abnormal,
2011 insert there. Except for the entry block.
2012 Don't do this if the predecessor ends in a jump other than
2013 unconditional simple jump. E.g. for asm goto that points all
2014 its labels at the fallthru basic block, we can't insert instructions
2015 before the asm goto, as the asm goto can have various of side effects,
2016 and can't emit instructions after the asm goto, as it must end
2018 else if ((e
->flags
& EDGE_ABNORMAL
) == 0
2019 && single_succ_p (e
->src
)
2020 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2021 && (!JUMP_P (BB_END (e
->src
))
2022 || simplejump_p (BB_END (e
->src
))))
2026 /* It is possible to have a non-simple jump here. Consider a target
2027 where some forms of unconditional jumps clobber a register. This
2028 happens on the fr30 for example.
2030 We know this block has a single successor, so we can just emit
2031 the queued insns before the jump. */
2032 if (JUMP_P (BB_END (bb
)))
2033 before
= BB_END (bb
);
2036 /* We'd better be fallthru, or we've lost track of what's what. */
2037 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
2039 after
= BB_END (bb
);
2043 /* Otherwise we must split the edge. */
2046 bb
= split_edge (e
);
2048 /* If E crossed a partition boundary, we needed to make bb end in
2049 a region-crossing jump, even though it was originally fallthru. */
2050 if (JUMP_P (BB_END (bb
)))
2051 before
= BB_END (bb
);
2053 after
= BB_END (bb
);
2056 /* Now that we've found the spot, do the insertion. */
2059 emit_insn_before_noloc (insns
, before
, bb
);
2060 last
= prev_nonnote_insn (before
);
2063 last
= emit_insn_after_noloc (insns
, after
, bb
);
2065 if (returnjump_p (last
))
2067 /* ??? Remove all outgoing edges from BB and add one for EXIT.
2068 This is not currently a problem because this only happens
2069 for the (single) epilogue, which already has a fallthru edge
2072 e
= single_succ_edge (bb
);
2073 gcc_assert (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
2074 && single_succ_p (bb
) && (e
->flags
& EDGE_FALLTHRU
));
2076 e
->flags
&= ~EDGE_FALLTHRU
;
2077 emit_barrier_after (last
);
2080 delete_insn (before
);
2083 gcc_assert (!JUMP_P (last
));
2086 /* Update the CFG for all queued instructions. */
2089 commit_edge_insertions (void)
2093 /* Optimization passes that invoke this routine can cause hot blocks
2094 previously reached by both hot and cold blocks to become dominated only
2095 by cold blocks. This will cause the verification below to fail,
2096 and lead to now cold code in the hot section. In some cases this
2097 may only be visible after newly unreachable blocks are deleted,
2098 which will be done by fixup_partitions. */
2099 fixup_partitions ();
2101 #ifdef ENABLE_CHECKING
2102 verify_flow_info ();
2105 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
2106 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
2111 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2113 commit_one_edge_insertion (e
);
2118 /* Print out RTL-specific basic block information (live information
2119 at start and end with TDF_DETAILS). FLAGS are the TDF_* masks
2120 documented in dumpfile.h. */
2123 rtl_dump_bb (FILE *outf
, basic_block bb
, int indent
, int flags
)
2129 s_indent
= (char *) alloca ((size_t) indent
+ 1);
2130 memset (s_indent
, ' ', (size_t) indent
);
2131 s_indent
[indent
] = '\0';
2133 if (df
&& (flags
& TDF_DETAILS
))
2135 df_dump_top (bb
, outf
);
2139 if (bb
->index
!= ENTRY_BLOCK
&& bb
->index
!= EXIT_BLOCK
)
2140 for (insn
= BB_HEAD (bb
), last
= NEXT_INSN (BB_END (bb
)); insn
!= last
;
2141 insn
= NEXT_INSN (insn
))
2143 if (flags
& TDF_DETAILS
)
2144 df_dump_insn_top (insn
, outf
);
2145 if (! (flags
& TDF_SLIM
))
2146 print_rtl_single (outf
, insn
);
2148 dump_insn_slim (outf
, insn
);
2149 if (flags
& TDF_DETAILS
)
2150 df_dump_insn_bottom (insn
, outf
);
2153 if (df
&& (flags
& TDF_DETAILS
))
2155 df_dump_bottom (bb
, outf
);
2161 /* Like dump_function_to_file, but for RTL. Print out dataflow information
2162 for the start of each basic block. FLAGS are the TDF_* masks documented
2166 print_rtl_with_bb (FILE *outf
, const rtx_insn
*rtx_first
, int flags
)
2168 const rtx_insn
*tmp_rtx
;
2170 fprintf (outf
, "(nil)\n");
2173 enum bb_state
{ NOT_IN_BB
, IN_ONE_BB
, IN_MULTIPLE_BB
};
2174 int max_uid
= get_max_uid ();
2175 basic_block
*start
= XCNEWVEC (basic_block
, max_uid
);
2176 basic_block
*end
= XCNEWVEC (basic_block
, max_uid
);
2177 enum bb_state
*in_bb_p
= XCNEWVEC (enum bb_state
, max_uid
);
2180 /* After freeing the CFG, we still have BLOCK_FOR_INSN set on most
2181 insns, but the CFG is not maintained so the basic block info
2182 is not reliable. Therefore it's omitted from the dumps. */
2183 if (! (cfun
->curr_properties
& PROP_cfg
))
2184 flags
&= ~TDF_BLOCKS
;
2187 df_dump_start (outf
);
2189 if (flags
& TDF_BLOCKS
)
2191 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2195 start
[INSN_UID (BB_HEAD (bb
))] = bb
;
2196 end
[INSN_UID (BB_END (bb
))] = bb
;
2197 for (x
= BB_HEAD (bb
); x
!= NULL_RTX
; x
= NEXT_INSN (x
))
2199 enum bb_state state
= IN_MULTIPLE_BB
;
2201 if (in_bb_p
[INSN_UID (x
)] == NOT_IN_BB
)
2203 in_bb_p
[INSN_UID (x
)] = state
;
2205 if (x
== BB_END (bb
))
2211 for (tmp_rtx
= rtx_first
; NULL
!= tmp_rtx
; tmp_rtx
= NEXT_INSN (tmp_rtx
))
2213 if (flags
& TDF_BLOCKS
)
2215 bb
= start
[INSN_UID (tmp_rtx
)];
2218 dump_bb_info (outf
, bb
, 0, dump_flags
| TDF_COMMENT
, true, false);
2219 if (df
&& (flags
& TDF_DETAILS
))
2220 df_dump_top (bb
, outf
);
2223 if (in_bb_p
[INSN_UID (tmp_rtx
)] == NOT_IN_BB
2224 && !NOTE_P (tmp_rtx
)
2225 && !BARRIER_P (tmp_rtx
))
2226 fprintf (outf
, ";; Insn is not within a basic block\n");
2227 else if (in_bb_p
[INSN_UID (tmp_rtx
)] == IN_MULTIPLE_BB
)
2228 fprintf (outf
, ";; Insn is in multiple basic blocks\n");
2231 if (flags
& TDF_DETAILS
)
2232 df_dump_insn_top (tmp_rtx
, outf
);
2233 if (! (flags
& TDF_SLIM
))
2234 print_rtl_single (outf
, tmp_rtx
);
2236 dump_insn_slim (outf
, tmp_rtx
);
2237 if (flags
& TDF_DETAILS
)
2238 df_dump_insn_bottom (tmp_rtx
, outf
);
2240 if (flags
& TDF_BLOCKS
)
2242 bb
= end
[INSN_UID (tmp_rtx
)];
2245 dump_bb_info (outf
, bb
, 0, dump_flags
| TDF_COMMENT
, false, true);
2246 if (df
&& (flags
& TDF_DETAILS
))
2247 df_dump_bottom (bb
, outf
);
2259 /* Update the branch probability of BB if a REG_BR_PROB is present. */
2262 update_br_prob_note (basic_block bb
)
2265 if (!JUMP_P (BB_END (bb
)))
2267 note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
);
2268 if (!note
|| XINT (note
, 0) == BRANCH_EDGE (bb
)->probability
)
2270 XINT (note
, 0) = BRANCH_EDGE (bb
)->probability
;
2273 /* Get the last insn associated with block BB (that includes barriers and
2274 tablejumps after BB). */
2276 get_last_bb_insn (basic_block bb
)
2278 rtx_jump_table_data
*table
;
2280 rtx_insn
*end
= BB_END (bb
);
2282 /* Include any jump table following the basic block. */
2283 if (tablejump_p (end
, NULL
, &table
))
2286 /* Include any barriers that may follow the basic block. */
2287 tmp
= next_nonnote_insn_bb (end
);
2288 while (tmp
&& BARRIER_P (tmp
))
2291 tmp
= next_nonnote_insn_bb (end
);
2297 /* Sanity check partition hotness to ensure that basic blocks in
2298 Â the cold partition don't dominate basic blocks in the hot partition.
2299 If FLAG_ONLY is true, report violations as errors. Otherwise
2300 re-mark the dominated blocks as cold, since this is run after
2301 cfg optimizations that may make hot blocks previously reached
2302 by both hot and cold blocks now only reachable along cold paths. */
2304 static vec
<basic_block
>
2305 find_partition_fixes (bool flag_only
)
2308 vec
<basic_block
> bbs_in_cold_partition
= vNULL
;
2309 vec
<basic_block
> bbs_to_fix
= vNULL
;
2311 /* Callers check this. */
2312 gcc_checking_assert (crtl
->has_bb_partition
);
2314 FOR_EACH_BB_FN (bb
, cfun
)
2315 if ((BB_PARTITION (bb
) == BB_COLD_PARTITION
))
2316 bbs_in_cold_partition
.safe_push (bb
);
2318 if (bbs_in_cold_partition
.is_empty ())
2321 bool dom_calculated_here
= !dom_info_available_p (CDI_DOMINATORS
);
2323 if (dom_calculated_here
)
2324 calculate_dominance_info (CDI_DOMINATORS
);
2326 while (! bbs_in_cold_partition
.is_empty ())
2328 bb
= bbs_in_cold_partition
.pop ();
2329 /* Any blocks dominated by a block in the cold section
2330 must also be cold. */
2332 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
2334 son
= next_dom_son (CDI_DOMINATORS
, son
))
2336 /* If son is not yet cold, then mark it cold here and
2337 enqueue it for further processing. */
2338 if ((BB_PARTITION (son
) != BB_COLD_PARTITION
))
2341 error ("non-cold basic block %d dominated "
2342 "by a block in the cold partition (%d)", son
->index
, bb
->index
);
2344 BB_SET_PARTITION (son
, BB_COLD_PARTITION
);
2345 bbs_to_fix
.safe_push (son
);
2346 bbs_in_cold_partition
.safe_push (son
);
2351 if (dom_calculated_here
)
2352 free_dominance_info (CDI_DOMINATORS
);
2357 /* Perform cleanup on the hot/cold bb partitioning after optimization
2358 passes that modify the cfg. */
2361 fixup_partitions (void)
2365 if (!crtl
->has_bb_partition
)
2368 /* Delete any blocks that became unreachable and weren't
2369 already cleaned up, for example during edge forwarding
2370 and convert_jumps_to_returns. This will expose more
2371 opportunities for fixing the partition boundaries here.
2372 Also, the calculation of the dominance graph during verification
2373 will assert if there are unreachable nodes. */
2374 delete_unreachable_blocks ();
2376 /* If there are partitions, do a sanity check on them: A basic block in
2377 Â a cold partition cannot dominate a basic block in a hot partition.
2378 Fixup any that now violate this requirement, as a result of edge
2379 forwarding and unreachable block deletion. Â */
2380 vec
<basic_block
> bbs_to_fix
= find_partition_fixes (false);
2382 /* Do the partition fixup after all necessary blocks have been converted to
2383 cold, so that we only update the region crossings the minimum number of
2384 places, which can require forcing edges to be non fallthru. */
2385 while (! bbs_to_fix
.is_empty ())
2387 bb
= bbs_to_fix
.pop ();
2388 fixup_new_cold_bb (bb
);
2392 /* Verify, in the basic block chain, that there is at most one switch
2393 between hot/cold partitions. This condition will not be true until
2394 after reorder_basic_blocks is called. */
2397 verify_hot_cold_block_grouping (void)
2401 bool switched_sections
= false;
2402 int current_partition
= BB_UNPARTITIONED
;
2404 /* Even after bb reordering is complete, we go into cfglayout mode
2405 again (in compgoto). Ensure we don't call this before going back
2406 into linearized RTL when any layout fixes would have been committed. */
2407 if (!crtl
->bb_reorder_complete
2408 || current_ir_type () != IR_RTL_CFGRTL
)
2411 FOR_EACH_BB_FN (bb
, cfun
)
2413 if (current_partition
!= BB_UNPARTITIONED
2414 && BB_PARTITION (bb
) != current_partition
)
2416 if (switched_sections
)
2418 error ("multiple hot/cold transitions found (bb %i)",
2423 switched_sections
= true;
2425 if (!crtl
->has_bb_partition
)
2426 error ("partition found but function partition flag not set");
2428 current_partition
= BB_PARTITION (bb
);
2435 /* Perform several checks on the edges out of each block, such as
2436 the consistency of the branch probabilities, the correctness
2437 of hot/cold partition crossing edges, and the number of expected
2438 successor edges. Also verify that the dominance relationship
2439 between hot/cold blocks is sane. */
2442 rtl_verify_edges (void)
2447 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2449 int n_fallthru
= 0, n_branch
= 0, n_abnormal_call
= 0, n_sibcall
= 0;
2450 int n_eh
= 0, n_abnormal
= 0;
2451 edge e
, fallthru
= NULL
;
2454 bool has_crossing_edge
= false;
2456 if (JUMP_P (BB_END (bb
))
2457 && (note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
))
2458 && EDGE_COUNT (bb
->succs
) >= 2
2459 && any_condjump_p (BB_END (bb
)))
2461 if (XINT (note
, 0) != BRANCH_EDGE (bb
)->probability
2462 && profile_status_for_fn (cfun
) != PROFILE_ABSENT
)
2464 error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i",
2465 XINT (note
, 0), BRANCH_EDGE (bb
)->probability
);
2470 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2474 if (e
->flags
& EDGE_FALLTHRU
)
2475 n_fallthru
++, fallthru
= e
;
2477 is_crossing
= (BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
)
2478 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2479 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
2480 has_crossing_edge
|= is_crossing
;
2481 if (e
->flags
& EDGE_CROSSING
)
2485 error ("EDGE_CROSSING incorrectly set across same section");
2488 if (e
->flags
& EDGE_FALLTHRU
)
2490 error ("fallthru edge crosses section boundary in bb %i",
2494 if (e
->flags
& EDGE_EH
)
2496 error ("EH edge crosses section boundary in bb %i",
2500 if (JUMP_P (BB_END (bb
)) && !CROSSING_JUMP_P (BB_END (bb
)))
2502 error ("No region crossing jump at section boundary in bb %i",
2507 else if (is_crossing
)
2509 error ("EDGE_CROSSING missing across section boundary");
2513 if ((e
->flags
& ~(EDGE_DFS_BACK
2515 | EDGE_IRREDUCIBLE_LOOP
2518 | EDGE_PRESERVE
)) == 0)
2521 if (e
->flags
& EDGE_ABNORMAL_CALL
)
2524 if (e
->flags
& EDGE_SIBCALL
)
2527 if (e
->flags
& EDGE_EH
)
2530 if (e
->flags
& EDGE_ABNORMAL
)
2534 if (!has_crossing_edge
2535 && JUMP_P (BB_END (bb
))
2536 && CROSSING_JUMP_P (BB_END (bb
)))
2538 print_rtl_with_bb (stderr
, get_insns (), TDF_RTL
| TDF_BLOCKS
| TDF_DETAILS
);
2539 error ("Region crossing jump across same section in bb %i",
2544 if (n_eh
&& !find_reg_note (BB_END (bb
), REG_EH_REGION
, NULL_RTX
))
2546 error ("missing REG_EH_REGION note at the end of bb %i", bb
->index
);
2551 error ("too many exception handling edges in bb %i", bb
->index
);
2555 && (!JUMP_P (BB_END (bb
))
2556 || (n_branch
> 1 && (any_uncondjump_p (BB_END (bb
))
2557 || any_condjump_p (BB_END (bb
))))))
2559 error ("too many outgoing branch edges from bb %i", bb
->index
);
2562 if (n_fallthru
&& any_uncondjump_p (BB_END (bb
)))
2564 error ("fallthru edge after unconditional jump in bb %i", bb
->index
);
2567 if (n_branch
!= 1 && any_uncondjump_p (BB_END (bb
)))
2569 error ("wrong number of branch edges after unconditional jump"
2570 " in bb %i", bb
->index
);
2573 if (n_branch
!= 1 && any_condjump_p (BB_END (bb
))
2574 && JUMP_LABEL (BB_END (bb
)) != BB_HEAD (fallthru
->dest
))
2576 error ("wrong amount of branch edges after conditional jump"
2577 " in bb %i", bb
->index
);
2580 if (n_abnormal_call
&& !CALL_P (BB_END (bb
)))
2582 error ("abnormal call edges for non-call insn in bb %i", bb
->index
);
2585 if (n_sibcall
&& !CALL_P (BB_END (bb
)))
2587 error ("sibcall edges for non-call insn in bb %i", bb
->index
);
2590 if (n_abnormal
> n_eh
2591 && !(CALL_P (BB_END (bb
))
2592 && n_abnormal
== n_abnormal_call
+ n_sibcall
)
2593 && (!JUMP_P (BB_END (bb
))
2594 || any_condjump_p (BB_END (bb
))
2595 || any_uncondjump_p (BB_END (bb
))))
2597 error ("abnormal edges for no purpose in bb %i", bb
->index
);
2602 /* If there are partitions, do a sanity check on them: A basic block in
2603 Â a cold partition cannot dominate a basic block in a hot partition. Â */
2604 if (crtl
->has_bb_partition
&& !err
)
2606 vec
<basic_block
> bbs_to_fix
= find_partition_fixes (true);
2607 err
= !bbs_to_fix
.is_empty ();
2614 /* Checks on the instructions within blocks. Currently checks that each
2615 block starts with a basic block note, and that basic block notes and
2616 control flow jumps are not found in the middle of the block. */
2619 rtl_verify_bb_insns (void)
2625 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2627 /* Now check the header of basic
2628 block. It ought to contain optional CODE_LABEL followed
2629 by NOTE_BASIC_BLOCK. */
2633 if (BB_END (bb
) == x
)
2635 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2643 if (!NOTE_INSN_BASIC_BLOCK_P (x
) || NOTE_BASIC_BLOCK (x
) != bb
)
2645 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2650 if (BB_END (bb
) == x
)
2651 /* Do checks for empty blocks here. */
2654 for (x
= NEXT_INSN (x
); x
; x
= NEXT_INSN (x
))
2656 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2658 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
2659 INSN_UID (x
), bb
->index
);
2663 if (x
== BB_END (bb
))
2666 if (control_flow_insn_p (x
))
2668 error ("in basic block %d:", bb
->index
);
2669 fatal_insn ("flow control insn inside a basic block", x
);
2678 /* Verify that block pointers for instructions in basic blocks, headers and
2679 footers are set appropriately. */
2682 rtl_verify_bb_pointers (void)
2687 /* Check the general integrity of the basic blocks. */
2688 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2692 if (!(bb
->flags
& BB_RTL
))
2694 error ("BB_RTL flag not set for block %d", bb
->index
);
2698 FOR_BB_INSNS (bb
, insn
)
2699 if (BLOCK_FOR_INSN (insn
) != bb
)
2701 error ("insn %d basic block pointer is %d, should be %d",
2703 BLOCK_FOR_INSN (insn
) ? BLOCK_FOR_INSN (insn
)->index
: 0,
2708 for (insn
= BB_HEADER (bb
); insn
; insn
= NEXT_INSN (insn
))
2709 if (!BARRIER_P (insn
)
2710 && BLOCK_FOR_INSN (insn
) != NULL
)
2712 error ("insn %d in header of bb %d has non-NULL basic block",
2713 INSN_UID (insn
), bb
->index
);
2716 for (insn
= BB_FOOTER (bb
); insn
; insn
= NEXT_INSN (insn
))
2717 if (!BARRIER_P (insn
)
2718 && BLOCK_FOR_INSN (insn
) != NULL
)
2720 error ("insn %d in footer of bb %d has non-NULL basic block",
2721 INSN_UID (insn
), bb
->index
);
2730 /* Verify the CFG and RTL consistency common for both underlying RTL and
2733 Currently it does following checks:
2735 - overlapping of basic blocks
2736 - insns with wrong BLOCK_FOR_INSN pointers
2737 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
2738 - tails of basic blocks (ensure that boundary is necessary)
2739 - scans body of the basic block for JUMP_INSN, CODE_LABEL
2740 and NOTE_INSN_BASIC_BLOCK
2741 - verify that no fall_thru edge crosses hot/cold partition boundaries
2742 - verify that there are no pending RTL branch predictions
2743 - verify that hot blocks are not dominated by cold blocks
2745 In future it can be extended check a lot of other stuff as well
2746 (reachability of basic blocks, life information, etc. etc.). */
2749 rtl_verify_flow_info_1 (void)
2753 err
|= rtl_verify_bb_pointers ();
2755 err
|= rtl_verify_bb_insns ();
2757 err
|= rtl_verify_edges ();
2762 /* Walk the instruction chain and verify that bb head/end pointers
2763 are correct, and that instructions are in exactly one bb and have
2764 correct block pointers. */
2767 rtl_verify_bb_insn_chain (void)
2772 rtx_insn
*last_head
= get_last_insn ();
2773 basic_block
*bb_info
;
2774 const int max_uid
= get_max_uid ();
2776 bb_info
= XCNEWVEC (basic_block
, max_uid
);
2778 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2780 rtx_insn
*head
= BB_HEAD (bb
);
2781 rtx_insn
*end
= BB_END (bb
);
2783 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2785 /* Verify the end of the basic block is in the INSN chain. */
2789 /* And that the code outside of basic blocks has NULL bb field. */
2791 && BLOCK_FOR_INSN (x
) != NULL
)
2793 error ("insn %d outside of basic blocks has non-NULL bb field",
2801 error ("end insn %d for block %d not found in the insn stream",
2802 INSN_UID (end
), bb
->index
);
2806 /* Work backwards from the end to the head of the basic block
2807 to verify the head is in the RTL chain. */
2808 for (; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2810 /* While walking over the insn chain, verify insns appear
2811 in only one basic block. */
2812 if (bb_info
[INSN_UID (x
)] != NULL
)
2814 error ("insn %d is in multiple basic blocks (%d and %d)",
2815 INSN_UID (x
), bb
->index
, bb_info
[INSN_UID (x
)]->index
);
2819 bb_info
[INSN_UID (x
)] = bb
;
2826 error ("head insn %d for block %d not found in the insn stream",
2827 INSN_UID (head
), bb
->index
);
2831 last_head
= PREV_INSN (x
);
2834 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2836 /* Check that the code before the first basic block has NULL
2839 && BLOCK_FOR_INSN (x
) != NULL
)
2841 error ("insn %d outside of basic blocks has non-NULL bb field",
2851 /* Verify that fallthru edges point to adjacent blocks in layout order and
2852 that barriers exist after non-fallthru blocks. */
2855 rtl_verify_fallthru (void)
2860 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2864 e
= find_fallthru_edge (bb
->succs
);
2869 /* Ensure existence of barrier in BB with no fallthru edges. */
2870 for (insn
= NEXT_INSN (BB_END (bb
)); ; insn
= NEXT_INSN (insn
))
2872 if (!insn
|| NOTE_INSN_BASIC_BLOCK_P (insn
))
2874 error ("missing barrier after block %i", bb
->index
);
2878 if (BARRIER_P (insn
))
2882 else if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2883 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
2887 if (e
->src
->next_bb
!= e
->dest
)
2890 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
2891 e
->src
->index
, e
->dest
->index
);
2895 for (insn
= NEXT_INSN (BB_END (e
->src
)); insn
!= BB_HEAD (e
->dest
);
2896 insn
= NEXT_INSN (insn
))
2897 if (BARRIER_P (insn
) || INSN_P (insn
))
2899 error ("verify_flow_info: Incorrect fallthru %i->%i",
2900 e
->src
->index
, e
->dest
->index
);
2901 fatal_insn ("wrong insn in the fallthru edge", insn
);
2910 /* Verify that blocks are laid out in consecutive order. While walking the
2911 instructions, verify that all expected instructions are inside the basic
2912 blocks, and that all returns are followed by barriers. */
2915 rtl_verify_bb_layout (void)
2921 rtx_insn
* const rtx_first
= get_insns ();
2922 basic_block last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
), curr_bb
= NULL
;
2925 last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
2927 for (x
= rtx_first
; x
; x
= NEXT_INSN (x
))
2929 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2931 bb
= NOTE_BASIC_BLOCK (x
);
2934 if (bb
!= last_bb_seen
->next_bb
)
2935 internal_error ("basic blocks not laid down consecutively");
2937 curr_bb
= last_bb_seen
= bb
;
2942 switch (GET_CODE (x
))
2949 /* An ADDR_VEC is placed outside any basic block. */
2951 && JUMP_TABLE_DATA_P (NEXT_INSN (x
)))
2954 /* But in any case, non-deletable labels can appear anywhere. */
2958 fatal_insn ("insn outside basic block", x
);
2963 && returnjump_p (x
) && ! condjump_p (x
)
2964 && ! (next_nonnote_insn (x
) && BARRIER_P (next_nonnote_insn (x
))))
2965 fatal_insn ("return not followed by barrier", x
);
2967 if (curr_bb
&& x
== BB_END (curr_bb
))
2971 if (num_bb_notes
!= n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
)
2973 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
2974 num_bb_notes
, n_basic_blocks_for_fn (cfun
));
2979 /* Verify the CFG and RTL consistency common for both underlying RTL and
2980 cfglayout RTL, plus consistency checks specific to linearized RTL mode.
2982 Currently it does following checks:
2983 - all checks of rtl_verify_flow_info_1
2984 - test head/end pointers
2985 - check that blocks are laid out in consecutive order
2986 - check that all insns are in the basic blocks
2987 (except the switch handling code, barriers and notes)
2988 - check that all returns are followed by barriers
2989 - check that all fallthru edge points to the adjacent blocks
2990 - verify that there is a single hot/cold partition boundary after bbro */
2993 rtl_verify_flow_info (void)
2997 err
|= rtl_verify_flow_info_1 ();
2999 err
|= rtl_verify_bb_insn_chain ();
3001 err
|= rtl_verify_fallthru ();
3003 err
|= rtl_verify_bb_layout ();
3005 err
|= verify_hot_cold_block_grouping ();
3010 /* Assume that the preceding pass has possibly eliminated jump instructions
3011 or converted the unconditional jumps. Eliminate the edges from CFG.
3012 Return true if any edges are eliminated. */
3015 purge_dead_edges (basic_block bb
)
3018 rtx_insn
*insn
= BB_END (bb
);
3020 bool purged
= false;
3024 if (DEBUG_INSN_P (insn
) && insn
!= BB_HEAD (bb
))
3026 insn
= PREV_INSN (insn
);
3027 while ((DEBUG_INSN_P (insn
) || NOTE_P (insn
)) && insn
!= BB_HEAD (bb
));
3029 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
3030 if (NONJUMP_INSN_P (insn
)
3031 && (note
= find_reg_note (insn
, REG_EH_REGION
, NULL
)))
3035 if (! may_trap_p (PATTERN (insn
))
3036 || ((eqnote
= find_reg_equal_equiv_note (insn
))
3037 && ! may_trap_p (XEXP (eqnote
, 0))))
3038 remove_note (insn
, note
);
3041 /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
3042 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3044 bool remove
= false;
3046 /* There are three types of edges we need to handle correctly here: EH
3047 edges, abnormal call EH edges, and abnormal call non-EH edges. The
3048 latter can appear when nonlocal gotos are used. */
3049 if (e
->flags
& EDGE_ABNORMAL_CALL
)
3053 else if (can_nonlocal_goto (insn
))
3055 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
3057 else if (flag_tm
&& find_reg_note (insn
, REG_TM
, NULL
))
3062 else if (e
->flags
& EDGE_EH
)
3063 remove
= !can_throw_internal (insn
);
3068 df_set_bb_dirty (bb
);
3081 /* We do care only about conditional jumps and simplejumps. */
3082 if (!any_condjump_p (insn
)
3083 && !returnjump_p (insn
)
3084 && !simplejump_p (insn
))
3087 /* Branch probability/prediction notes are defined only for
3088 condjumps. We've possibly turned condjump into simplejump. */
3089 if (simplejump_p (insn
))
3091 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
3093 remove_note (insn
, note
);
3094 while ((note
= find_reg_note (insn
, REG_BR_PRED
, NULL
)))
3095 remove_note (insn
, note
);
3098 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3100 /* Avoid abnormal flags to leak from computed jumps turned
3101 into simplejumps. */
3103 e
->flags
&= ~EDGE_ABNORMAL
;
3105 /* See if this edge is one we should keep. */
3106 if ((e
->flags
& EDGE_FALLTHRU
) && any_condjump_p (insn
))
3107 /* A conditional jump can fall through into the next
3108 block, so we should keep the edge. */
3113 else if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
3114 && BB_HEAD (e
->dest
) == JUMP_LABEL (insn
))
3115 /* If the destination block is the target of the jump,
3121 else if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
3122 && returnjump_p (insn
))
3123 /* If the destination block is the exit block, and this
3124 instruction is a return, then keep the edge. */
3129 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
3130 /* Keep the edges that correspond to exceptions thrown by
3131 this instruction and rematerialize the EDGE_ABNORMAL
3132 flag we just cleared above. */
3134 e
->flags
|= EDGE_ABNORMAL
;
3139 /* We do not need this edge. */
3140 df_set_bb_dirty (bb
);
3145 if (EDGE_COUNT (bb
->succs
) == 0 || !purged
)
3149 fprintf (dump_file
, "Purged edges from bb %i\n", bb
->index
);
3154 /* Redistribute probabilities. */
3155 if (single_succ_p (bb
))
3157 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
3158 single_succ_edge (bb
)->count
= bb
->count
;
3162 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
3166 b
= BRANCH_EDGE (bb
);
3167 f
= FALLTHRU_EDGE (bb
);
3168 b
->probability
= XINT (note
, 0);
3169 f
->probability
= REG_BR_PROB_BASE
- b
->probability
;
3170 /* Update these to use GCOV_COMPUTE_SCALE. */
3171 b
->count
= bb
->count
* b
->probability
/ REG_BR_PROB_BASE
;
3172 f
->count
= bb
->count
* f
->probability
/ REG_BR_PROB_BASE
;
3177 else if (CALL_P (insn
) && SIBLING_CALL_P (insn
))
3179 /* First, there should not be any EH or ABCALL edges resulting
3180 from non-local gotos and the like. If there were, we shouldn't
3181 have created the sibcall in the first place. Second, there
3182 should of course never have been a fallthru edge. */
3183 gcc_assert (single_succ_p (bb
));
3184 gcc_assert (single_succ_edge (bb
)->flags
3185 == (EDGE_SIBCALL
| EDGE_ABNORMAL
));
3190 /* If we don't see a jump insn, we don't know exactly why the block would
3191 have been broken at this point. Look for a simple, non-fallthru edge,
3192 as these are only created by conditional branches. If we find such an
3193 edge we know that there used to be a jump here and can then safely
3194 remove all non-fallthru edges. */
3196 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3197 if (! (e
->flags
& (EDGE_COMPLEX
| EDGE_FALLTHRU
)))
3206 /* Remove all but the fake and fallthru edges. The fake edge may be
3207 the only successor for this block in the case of noreturn
3209 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3211 if (!(e
->flags
& (EDGE_FALLTHRU
| EDGE_FAKE
)))
3213 df_set_bb_dirty (bb
);
3221 gcc_assert (single_succ_p (bb
));
3223 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
3224 single_succ_edge (bb
)->count
= bb
->count
;
3227 fprintf (dump_file
, "Purged non-fallthru edges from bb %i\n",
3232 /* Search all basic blocks for potentially dead edges and purge them. Return
3233 true if some edge has been eliminated. */
3236 purge_all_dead_edges (void)
3241 FOR_EACH_BB_FN (bb
, cfun
)
3243 bool purged_here
= purge_dead_edges (bb
);
3245 purged
|= purged_here
;
3251 /* This is used by a few passes that emit some instructions after abnormal
3252 calls, moving the basic block's end, while they in fact do want to emit
3253 them on the fallthru edge. Look for abnormal call edges, find backward
3254 the call in the block and insert the instructions on the edge instead.
3256 Similarly, handle instructions throwing exceptions internally.
3258 Return true when instructions have been found and inserted on edges. */
3261 fixup_abnormal_edges (void)
3263 bool inserted
= false;
3266 FOR_EACH_BB_FN (bb
, cfun
)
3271 /* Look for cases we are interested in - calls or instructions causing
3273 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3274 if ((e
->flags
& EDGE_ABNORMAL_CALL
)
3275 || ((e
->flags
& (EDGE_ABNORMAL
| EDGE_EH
))
3276 == (EDGE_ABNORMAL
| EDGE_EH
)))
3279 if (e
&& !CALL_P (BB_END (bb
)) && !can_throw_internal (BB_END (bb
)))
3283 /* Get past the new insns generated. Allow notes, as the insns
3284 may be already deleted. */
3286 while ((NONJUMP_INSN_P (insn
) || NOTE_P (insn
))
3287 && !can_throw_internal (insn
)
3288 && insn
!= BB_HEAD (bb
))
3289 insn
= PREV_INSN (insn
);
3291 if (CALL_P (insn
) || can_throw_internal (insn
))
3293 rtx_insn
*stop
, *next
;
3295 e
= find_fallthru_edge (bb
->succs
);
3297 stop
= NEXT_INSN (BB_END (bb
));
3300 for (insn
= NEXT_INSN (insn
); insn
!= stop
; insn
= next
)
3302 next
= NEXT_INSN (insn
);
3307 /* Sometimes there's still the return value USE.
3308 If it's placed after a trapping call (i.e. that
3309 call is the last insn anyway), we have no fallthru
3310 edge. Simply delete this use and don't try to insert
3311 on the non-existent edge. */
3312 if (GET_CODE (PATTERN (insn
)) != USE
)
3314 /* We're not deleting it, we're moving it. */
3315 insn
->set_undeleted ();
3316 SET_PREV_INSN (insn
) = NULL_RTX
;
3317 SET_NEXT_INSN (insn
) = NULL_RTX
;
3319 insert_insn_on_edge (insn
, e
);
3323 else if (!BARRIER_P (insn
))
3324 set_block_for_insn (insn
, NULL
);
3328 /* It may be that we don't find any trapping insn. In this
3329 case we discovered quite late that the insn that had been
3330 marked as can_throw_internal in fact couldn't trap at all.
3331 So we should in fact delete the EH edges out of the block. */
3333 purge_dead_edges (bb
);
3340 /* Cut the insns from FIRST to LAST out of the insns stream. */
3343 unlink_insn_chain (rtx_insn
*first
, rtx_insn
*last
)
3345 rtx_insn
*prevfirst
= PREV_INSN (first
);
3346 rtx_insn
*nextlast
= NEXT_INSN (last
);
3348 SET_PREV_INSN (first
) = NULL
;
3349 SET_NEXT_INSN (last
) = NULL
;
3351 SET_NEXT_INSN (prevfirst
) = nextlast
;
3353 SET_PREV_INSN (nextlast
) = prevfirst
;
3355 set_last_insn (prevfirst
);
3357 set_first_insn (nextlast
);
3361 /* Skip over inter-block insns occurring after BB which are typically
3362 associated with BB (e.g., barriers). If there are any such insns,
3363 we return the last one. Otherwise, we return the end of BB. */
3366 skip_insns_after_block (basic_block bb
)
3368 rtx_insn
*insn
, *last_insn
, *next_head
, *prev
;
3371 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3372 next_head
= BB_HEAD (bb
->next_bb
);
3374 for (last_insn
= insn
= BB_END (bb
); (insn
= NEXT_INSN (insn
)) != 0; )
3376 if (insn
== next_head
)
3379 switch (GET_CODE (insn
))
3386 switch (NOTE_KIND (insn
))
3388 case NOTE_INSN_BLOCK_END
:
3398 if (NEXT_INSN (insn
)
3399 && JUMP_TABLE_DATA_P (NEXT_INSN (insn
)))
3401 insn
= NEXT_INSN (insn
);
3414 /* It is possible to hit contradictory sequence. For instance:
3420 Where barrier belongs to jump_insn, but the note does not. This can be
3421 created by removing the basic block originally following
3422 NOTE_INSN_BLOCK_BEG. In such case reorder the notes. */
3424 for (insn
= last_insn
; insn
!= BB_END (bb
); insn
= prev
)
3426 prev
= PREV_INSN (insn
);
3428 switch (NOTE_KIND (insn
))
3430 case NOTE_INSN_BLOCK_END
:
3433 case NOTE_INSN_DELETED
:
3434 case NOTE_INSN_DELETED_LABEL
:
3435 case NOTE_INSN_DELETED_DEBUG_LABEL
:
3438 reorder_insns (insn
, insn
, last_insn
);
3445 /* Locate or create a label for a given basic block. */
3448 label_for_bb (basic_block bb
)
3450 rtx_insn
*label
= BB_HEAD (bb
);
3452 if (!LABEL_P (label
))
3455 fprintf (dump_file
, "Emitting label for block %d\n", bb
->index
);
3457 label
= block_label (bb
);
3463 /* Locate the effective beginning and end of the insn chain for each
3464 block, as defined by skip_insns_after_block above. */
3467 record_effective_endpoints (void)
3469 rtx_insn
*next_insn
;
3473 for (insn
= get_insns ();
3476 && NOTE_KIND (insn
) != NOTE_INSN_BASIC_BLOCK
;
3477 insn
= NEXT_INSN (insn
))
3479 /* No basic blocks at all? */
3482 if (PREV_INSN (insn
))
3483 cfg_layout_function_header
=
3484 unlink_insn_chain (get_insns (), PREV_INSN (insn
));
3486 cfg_layout_function_header
= NULL
;
3488 next_insn
= get_insns ();
3489 FOR_EACH_BB_FN (bb
, cfun
)
3493 if (PREV_INSN (BB_HEAD (bb
)) && next_insn
!= BB_HEAD (bb
))
3494 BB_HEADER (bb
) = unlink_insn_chain (next_insn
,
3495 PREV_INSN (BB_HEAD (bb
)));
3496 end
= skip_insns_after_block (bb
);
3497 if (NEXT_INSN (BB_END (bb
)) && BB_END (bb
) != end
)
3498 BB_FOOTER (bb
) = unlink_insn_chain (NEXT_INSN (BB_END (bb
)), end
);
3499 next_insn
= NEXT_INSN (BB_END (bb
));
3502 cfg_layout_function_footer
= next_insn
;
3503 if (cfg_layout_function_footer
)
3504 cfg_layout_function_footer
= unlink_insn_chain (cfg_layout_function_footer
, get_last_insn ());
3509 const pass_data pass_data_into_cfg_layout_mode
=
3511 RTL_PASS
, /* type */
3512 "into_cfglayout", /* name */
3513 OPTGROUP_NONE
, /* optinfo_flags */
3515 0, /* properties_required */
3516 PROP_cfglayout
, /* properties_provided */
3517 0, /* properties_destroyed */
3518 0, /* todo_flags_start */
3519 0, /* todo_flags_finish */
3522 class pass_into_cfg_layout_mode
: public rtl_opt_pass
3525 pass_into_cfg_layout_mode (gcc::context
*ctxt
)
3526 : rtl_opt_pass (pass_data_into_cfg_layout_mode
, ctxt
)
3529 /* opt_pass methods: */
3530 virtual unsigned int execute (function
*)
3532 cfg_layout_initialize (0);
3536 }; // class pass_into_cfg_layout_mode
3541 make_pass_into_cfg_layout_mode (gcc::context
*ctxt
)
3543 return new pass_into_cfg_layout_mode (ctxt
);
3548 const pass_data pass_data_outof_cfg_layout_mode
=
3550 RTL_PASS
, /* type */
3551 "outof_cfglayout", /* name */
3552 OPTGROUP_NONE
, /* optinfo_flags */
3554 0, /* properties_required */
3555 0, /* properties_provided */
3556 PROP_cfglayout
, /* properties_destroyed */
3557 0, /* todo_flags_start */
3558 0, /* todo_flags_finish */
3561 class pass_outof_cfg_layout_mode
: public rtl_opt_pass
3564 pass_outof_cfg_layout_mode (gcc::context
*ctxt
)
3565 : rtl_opt_pass (pass_data_outof_cfg_layout_mode
, ctxt
)
3568 /* opt_pass methods: */
3569 virtual unsigned int execute (function
*);
3571 }; // class pass_outof_cfg_layout_mode
3574 pass_outof_cfg_layout_mode::execute (function
*fun
)
3578 FOR_EACH_BB_FN (bb
, fun
)
3579 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (fun
))
3580 bb
->aux
= bb
->next_bb
;
3582 cfg_layout_finalize ();
3590 make_pass_outof_cfg_layout_mode (gcc::context
*ctxt
)
3592 return new pass_outof_cfg_layout_mode (ctxt
);
3596 /* Link the basic blocks in the correct order, compacting the basic
3597 block queue while at it. If STAY_IN_CFGLAYOUT_MODE is false, this
3598 function also clears the basic block header and footer fields.
3600 This function is usually called after a pass (e.g. tracer) finishes
3601 some transformations while in cfglayout mode. The required sequence
3602 of the basic blocks is in a linked list along the bb->aux field.
3603 This functions re-links the basic block prev_bb and next_bb pointers
3604 accordingly, and it compacts and renumbers the blocks.
3606 FIXME: This currently works only for RTL, but the only RTL-specific
3607 bits are the STAY_IN_CFGLAYOUT_MODE bits. The tracer pass was moved
3608 to GIMPLE a long time ago, but it doesn't relink the basic block
3609 chain. It could do that (to give better initial RTL) if this function
3610 is made IR-agnostic (and moved to cfganal.c or cfg.c while at it). */
3613 relink_block_chain (bool stay_in_cfglayout_mode
)
3615 basic_block bb
, prev_bb
;
3618 /* Maybe dump the re-ordered sequence. */
3621 fprintf (dump_file
, "Reordered sequence:\n");
3622 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
, index
=
3625 bb
= (basic_block
) bb
->aux
, index
++)
3627 fprintf (dump_file
, " %i ", index
);
3628 if (get_bb_original (bb
))
3629 fprintf (dump_file
, "duplicate of %i ",
3630 get_bb_original (bb
)->index
);
3631 else if (forwarder_block_p (bb
)
3632 && !LABEL_P (BB_HEAD (bb
)))
3633 fprintf (dump_file
, "compensation ");
3635 fprintf (dump_file
, "bb %i ", bb
->index
);
3636 fprintf (dump_file
, " [%i]\n", bb
->frequency
);
3640 /* Now reorder the blocks. */
3641 prev_bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
3642 bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
;
3643 for (; bb
; prev_bb
= bb
, bb
= (basic_block
) bb
->aux
)
3645 bb
->prev_bb
= prev_bb
;
3646 prev_bb
->next_bb
= bb
;
3648 prev_bb
->next_bb
= EXIT_BLOCK_PTR_FOR_FN (cfun
);
3649 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
= prev_bb
;
3651 /* Then, clean up the aux fields. */
3652 FOR_ALL_BB_FN (bb
, cfun
)
3655 if (!stay_in_cfglayout_mode
)
3656 BB_HEADER (bb
) = BB_FOOTER (bb
) = NULL
;
3659 /* Maybe reset the original copy tables, they are not valid anymore
3660 when we renumber the basic blocks in compact_blocks. If we are
3661 are going out of cfglayout mode, don't re-allocate the tables. */
3662 free_original_copy_tables ();
3663 if (stay_in_cfglayout_mode
)
3664 initialize_original_copy_tables ();
3666 /* Finally, put basic_block_info in the new order. */
3671 /* Given a reorder chain, rearrange the code to match. */
3674 fixup_reorder_chain (void)
3677 rtx_insn
*insn
= NULL
;
3679 if (cfg_layout_function_header
)
3681 set_first_insn (cfg_layout_function_header
);
3682 insn
= cfg_layout_function_header
;
3683 while (NEXT_INSN (insn
))
3684 insn
= NEXT_INSN (insn
);
3687 /* First do the bulk reordering -- rechain the blocks without regard to
3688 the needed changes to jumps and labels. */
3690 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
; bb
; bb
= (basic_block
)
3696 SET_NEXT_INSN (insn
) = BB_HEADER (bb
);
3698 set_first_insn (BB_HEADER (bb
));
3699 SET_PREV_INSN (BB_HEADER (bb
)) = insn
;
3700 insn
= BB_HEADER (bb
);
3701 while (NEXT_INSN (insn
))
3702 insn
= NEXT_INSN (insn
);
3705 SET_NEXT_INSN (insn
) = BB_HEAD (bb
);
3707 set_first_insn (BB_HEAD (bb
));
3708 SET_PREV_INSN (BB_HEAD (bb
)) = insn
;
3712 SET_NEXT_INSN (insn
) = BB_FOOTER (bb
);
3713 SET_PREV_INSN (BB_FOOTER (bb
)) = insn
;
3714 while (NEXT_INSN (insn
))
3715 insn
= NEXT_INSN (insn
);
3719 SET_NEXT_INSN (insn
) = cfg_layout_function_footer
;
3720 if (cfg_layout_function_footer
)
3721 SET_PREV_INSN (cfg_layout_function_footer
) = insn
;
3723 while (NEXT_INSN (insn
))
3724 insn
= NEXT_INSN (insn
);
3726 set_last_insn (insn
);
3727 #ifdef ENABLE_CHECKING
3728 verify_insn_chain ();
3731 /* Now add jumps and labels as needed to match the blocks new
3734 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
; bb
; bb
= (basic_block
)
3737 edge e_fall
, e_taken
, e
;
3738 rtx_insn
*bb_end_insn
;
3739 rtx ret_label
= NULL_RTX
;
3743 if (EDGE_COUNT (bb
->succs
) == 0)
3746 /* Find the old fallthru edge, and another non-EH edge for
3748 e_taken
= e_fall
= NULL
;
3750 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3751 if (e
->flags
& EDGE_FALLTHRU
)
3753 else if (! (e
->flags
& EDGE_EH
))
3756 bb_end_insn
= BB_END (bb
);
3757 if (rtx_jump_insn
*bb_end_jump
= dyn_cast
<rtx_jump_insn
*> (bb_end_insn
))
3759 ret_label
= JUMP_LABEL (bb_end_jump
);
3760 if (any_condjump_p (bb_end_jump
))
3762 /* This might happen if the conditional jump has side
3763 effects and could therefore not be optimized away.
3764 Make the basic block to end with a barrier in order
3765 to prevent rtl_verify_flow_info from complaining. */
3768 gcc_assert (!onlyjump_p (bb_end_jump
)
3769 || returnjump_p (bb_end_jump
)
3770 || (e_taken
->flags
& EDGE_CROSSING
));
3771 emit_barrier_after (bb_end_jump
);
3775 /* If the old fallthru is still next, nothing to do. */
3776 if (bb
->aux
== e_fall
->dest
3777 || e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3780 /* The degenerated case of conditional jump jumping to the next
3781 instruction can happen for jumps with side effects. We need
3782 to construct a forwarder block and this will be done just
3783 fine by force_nonfallthru below. */
3787 /* There is another special case: if *neither* block is next,
3788 such as happens at the very end of a function, then we'll
3789 need to add a new unconditional jump. Choose the taken
3790 edge based on known or assumed probability. */
3791 else if (bb
->aux
!= e_taken
->dest
)
3793 rtx note
= find_reg_note (bb_end_jump
, REG_BR_PROB
, 0);
3796 && XINT (note
, 0) < REG_BR_PROB_BASE
/ 2
3797 && invert_jump (bb_end_jump
,
3799 == EXIT_BLOCK_PTR_FOR_FN (cfun
)
3801 : label_for_bb (e_fall
->dest
)), 0))
3803 e_fall
->flags
&= ~EDGE_FALLTHRU
;
3804 gcc_checking_assert (could_fall_through
3805 (e_taken
->src
, e_taken
->dest
));
3806 e_taken
->flags
|= EDGE_FALLTHRU
;
3807 update_br_prob_note (bb
);
3808 e
= e_fall
, e_fall
= e_taken
, e_taken
= e
;
3812 /* If the "jumping" edge is a crossing edge, and the fall
3813 through edge is non-crossing, leave things as they are. */
3814 else if ((e_taken
->flags
& EDGE_CROSSING
)
3815 && !(e_fall
->flags
& EDGE_CROSSING
))
3818 /* Otherwise we can try to invert the jump. This will
3819 basically never fail, however, keep up the pretense. */
3820 else if (invert_jump (bb_end_jump
,
3822 == EXIT_BLOCK_PTR_FOR_FN (cfun
)
3824 : label_for_bb (e_fall
->dest
)), 0))
3826 e_fall
->flags
&= ~EDGE_FALLTHRU
;
3827 gcc_checking_assert (could_fall_through
3828 (e_taken
->src
, e_taken
->dest
));
3829 e_taken
->flags
|= EDGE_FALLTHRU
;
3830 update_br_prob_note (bb
);
3831 if (LABEL_NUSES (ret_label
) == 0
3832 && single_pred_p (e_taken
->dest
))
3833 delete_insn (ret_label
);
3837 else if (extract_asm_operands (PATTERN (bb_end_insn
)) != NULL
)
3839 /* If the old fallthru is still next or if
3840 asm goto doesn't have a fallthru (e.g. when followed by
3841 __builtin_unreachable ()), nothing to do. */
3843 || bb
->aux
== e_fall
->dest
3844 || e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3847 /* Otherwise we'll have to use the fallthru fixup below. */
3851 /* Otherwise we have some return, switch or computed
3852 jump. In the 99% case, there should not have been a
3854 gcc_assert (returnjump_p (bb_end_insn
) || !e_fall
);
3860 /* No fallthru implies a noreturn function with EH edges, or
3861 something similarly bizarre. In any case, we don't need to
3866 /* If the fallthru block is still next, nothing to do. */
3867 if (bb
->aux
== e_fall
->dest
)
3870 /* A fallthru to exit block. */
3871 if (e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3875 /* We got here if we need to add a new jump insn.
3876 Note force_nonfallthru can delete E_FALL and thus we have to
3877 save E_FALL->src prior to the call to force_nonfallthru. */
3878 nb
= force_nonfallthru_and_redirect (e_fall
, e_fall
->dest
, ret_label
);
3883 /* Don't process this new block. */
3888 relink_block_chain (/*stay_in_cfglayout_mode=*/false);
3890 /* Annoying special case - jump around dead jumptables left in the code. */
3891 FOR_EACH_BB_FN (bb
, cfun
)
3893 edge e
= find_fallthru_edge (bb
->succs
);
3895 if (e
&& !can_fallthru (e
->src
, e
->dest
))
3896 force_nonfallthru (e
);
3899 /* Ensure goto_locus from edges has some instructions with that locus
3902 FOR_EACH_BB_FN (bb
, cfun
)
3907 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3908 if (LOCATION_LOCUS (e
->goto_locus
) != UNKNOWN_LOCATION
3909 && !(e
->flags
& EDGE_ABNORMAL
))
3913 basic_block dest
, nb
;
3916 insn
= BB_END (e
->src
);
3917 end
= PREV_INSN (BB_HEAD (e
->src
));
3919 && (!NONDEBUG_INSN_P (insn
) || !INSN_HAS_LOCATION (insn
)))
3920 insn
= PREV_INSN (insn
);
3922 && INSN_LOCATION (insn
) == e
->goto_locus
)
3924 if (simplejump_p (BB_END (e
->src
))
3925 && !INSN_HAS_LOCATION (BB_END (e
->src
)))
3927 INSN_LOCATION (BB_END (e
->src
)) = e
->goto_locus
;
3931 if (dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3933 /* Non-fallthru edges to the exit block cannot be split. */
3934 if (!(e
->flags
& EDGE_FALLTHRU
))
3939 insn
= BB_HEAD (dest
);
3940 end
= NEXT_INSN (BB_END (dest
));
3941 while (insn
!= end
&& !NONDEBUG_INSN_P (insn
))
3942 insn
= NEXT_INSN (insn
);
3943 if (insn
!= end
&& INSN_HAS_LOCATION (insn
)
3944 && INSN_LOCATION (insn
) == e
->goto_locus
)
3947 nb
= split_edge (e
);
3948 if (!INSN_P (BB_END (nb
)))
3949 BB_END (nb
) = emit_insn_after_noloc (gen_nop (), BB_END (nb
),
3951 INSN_LOCATION (BB_END (nb
)) = e
->goto_locus
;
3953 /* If there are other incoming edges to the destination block
3954 with the same goto locus, redirect them to the new block as
3955 well, this can prevent other such blocks from being created
3956 in subsequent iterations of the loop. */
3957 for (ei2
= ei_start (dest
->preds
); (e2
= ei_safe_edge (ei2
)); )
3958 if (LOCATION_LOCUS (e2
->goto_locus
) != UNKNOWN_LOCATION
3959 && !(e2
->flags
& (EDGE_ABNORMAL
| EDGE_FALLTHRU
))
3960 && e
->goto_locus
== e2
->goto_locus
)
3961 redirect_edge_and_branch (e2
, nb
);
3968 /* Perform sanity checks on the insn chain.
3969 1. Check that next/prev pointers are consistent in both the forward and
3971 2. Count insns in chain, going both directions, and check if equal.
3972 3. Check that get_last_insn () returns the actual end of chain. */
3975 verify_insn_chain (void)
3977 rtx_insn
*x
, *prevx
, *nextx
;
3978 int insn_cnt1
, insn_cnt2
;
3980 for (prevx
= NULL
, insn_cnt1
= 1, x
= get_insns ();
3982 prevx
= x
, insn_cnt1
++, x
= NEXT_INSN (x
))
3983 gcc_assert (PREV_INSN (x
) == prevx
);
3985 gcc_assert (prevx
== get_last_insn ());
3987 for (nextx
= NULL
, insn_cnt2
= 1, x
= get_last_insn ();
3989 nextx
= x
, insn_cnt2
++, x
= PREV_INSN (x
))
3990 gcc_assert (NEXT_INSN (x
) == nextx
);
3992 gcc_assert (insn_cnt1
== insn_cnt2
);
3995 /* If we have assembler epilogues, the block falling through to exit must
3996 be the last one in the reordered chain when we reach final. Ensure
3997 that this condition is met. */
3999 fixup_fallthru_exit_predecessor (void)
4002 basic_block bb
= NULL
;
4004 /* This transformation is not valid before reload, because we might
4005 separate a call from the instruction that copies the return
4007 gcc_assert (reload_completed
);
4009 e
= find_fallthru_edge (EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
);
4015 basic_block c
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
;
4017 /* If the very first block is the one with the fall-through exit
4018 edge, we have to split that block. */
4021 bb
= split_block_after_labels (bb
)->dest
;
4024 BB_FOOTER (bb
) = BB_FOOTER (c
);
4025 BB_FOOTER (c
) = NULL
;
4028 while (c
->aux
!= bb
)
4029 c
= (basic_block
) c
->aux
;
4033 c
= (basic_block
) c
->aux
;
4040 /* In case there are more than one fallthru predecessors of exit, force that
4041 there is only one. */
4044 force_one_exit_fallthru (void)
4046 edge e
, predecessor
= NULL
;
4049 basic_block forwarder
, bb
;
4051 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
4052 if (e
->flags
& EDGE_FALLTHRU
)
4054 if (predecessor
== NULL
)
4066 /* Exit has several fallthru predecessors. Create a forwarder block for
4068 forwarder
= split_edge (predecessor
);
4069 for (ei
= ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
);
4070 (e
= ei_safe_edge (ei
)); )
4072 if (e
->src
== forwarder
4073 || !(e
->flags
& EDGE_FALLTHRU
))
4076 redirect_edge_and_branch_force (e
, forwarder
);
4079 /* Fix up the chain of blocks -- make FORWARDER immediately precede the
4081 FOR_EACH_BB_FN (bb
, cfun
)
4083 if (bb
->aux
== NULL
&& bb
!= forwarder
)
4085 bb
->aux
= forwarder
;
4091 /* Return true in case it is possible to duplicate the basic block BB. */
4094 cfg_layout_can_duplicate_bb_p (const_basic_block bb
)
4096 /* Do not attempt to duplicate tablejumps, as we need to unshare
4097 the dispatch table. This is difficult to do, as the instructions
4098 computing jump destination may be hoisted outside the basic block. */
4099 if (tablejump_p (BB_END (bb
), NULL
, NULL
))
4102 /* Do not duplicate blocks containing insns that can't be copied. */
4103 if (targetm
.cannot_copy_insn_p
)
4105 rtx_insn
*insn
= BB_HEAD (bb
);
4108 if (INSN_P (insn
) && targetm
.cannot_copy_insn_p (insn
))
4110 if (insn
== BB_END (bb
))
4112 insn
= NEXT_INSN (insn
);
4120 duplicate_insn_chain (rtx_insn
*from
, rtx_insn
*to
)
4122 rtx_insn
*insn
, *next
, *copy
;
4125 /* Avoid updating of boundaries of previous basic block. The
4126 note will get removed from insn stream in fixup. */
4127 last
= emit_note (NOTE_INSN_DELETED
);
4129 /* Create copy at the end of INSN chain. The chain will
4130 be reordered later. */
4131 for (insn
= from
; insn
!= NEXT_INSN (to
); insn
= NEXT_INSN (insn
))
4133 switch (GET_CODE (insn
))
4136 /* Don't duplicate label debug insns. */
4137 if (TREE_CODE (INSN_VAR_LOCATION_DECL (insn
)) == LABEL_DECL
)
4143 copy
= emit_copy_of_insn_after (insn
, get_last_insn ());
4144 if (JUMP_P (insn
) && JUMP_LABEL (insn
) != NULL_RTX
4145 && ANY_RETURN_P (JUMP_LABEL (insn
)))
4146 JUMP_LABEL (copy
) = JUMP_LABEL (insn
);
4147 maybe_copy_prologue_epilogue_insn (insn
, copy
);
4150 case JUMP_TABLE_DATA
:
4151 /* Avoid copying of dispatch tables. We never duplicate
4152 tablejumps, so this can hit only in case the table got
4153 moved far from original jump.
4154 Avoid copying following barrier as well if any
4155 (and debug insns in between). */
4156 for (next
= NEXT_INSN (insn
);
4157 next
!= NEXT_INSN (to
);
4158 next
= NEXT_INSN (next
))
4159 if (!DEBUG_INSN_P (next
))
4161 if (next
!= NEXT_INSN (to
) && BARRIER_P (next
))
4173 switch (NOTE_KIND (insn
))
4175 /* In case prologue is empty and function contain label
4176 in first BB, we may want to copy the block. */
4177 case NOTE_INSN_PROLOGUE_END
:
4179 case NOTE_INSN_DELETED
:
4180 case NOTE_INSN_DELETED_LABEL
:
4181 case NOTE_INSN_DELETED_DEBUG_LABEL
:
4182 /* No problem to strip these. */
4183 case NOTE_INSN_FUNCTION_BEG
:
4184 /* There is always just single entry to function. */
4185 case NOTE_INSN_BASIC_BLOCK
:
4186 /* We should only switch text sections once. */
4187 case NOTE_INSN_SWITCH_TEXT_SECTIONS
:
4190 case NOTE_INSN_EPILOGUE_BEG
:
4191 case NOTE_INSN_UPDATE_SJLJ_CONTEXT
:
4192 emit_note_copy (as_a
<rtx_note
*> (insn
));
4196 /* All other notes should have already been eliminated. */
4204 insn
= NEXT_INSN (last
);
4209 /* Create a duplicate of the basic block BB. */
4212 cfg_layout_duplicate_bb (basic_block bb
)
4217 insn
= duplicate_insn_chain (BB_HEAD (bb
), BB_END (bb
));
4218 new_bb
= create_basic_block (insn
,
4219 insn
? get_last_insn () : NULL
,
4220 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
);
4222 BB_COPY_PARTITION (new_bb
, bb
);
4225 insn
= BB_HEADER (bb
);
4226 while (NEXT_INSN (insn
))
4227 insn
= NEXT_INSN (insn
);
4228 insn
= duplicate_insn_chain (BB_HEADER (bb
), insn
);
4230 BB_HEADER (new_bb
) = unlink_insn_chain (insn
, get_last_insn ());
4235 insn
= BB_FOOTER (bb
);
4236 while (NEXT_INSN (insn
))
4237 insn
= NEXT_INSN (insn
);
4238 insn
= duplicate_insn_chain (BB_FOOTER (bb
), insn
);
4240 BB_FOOTER (new_bb
) = unlink_insn_chain (insn
, get_last_insn ());
4247 /* Main entry point to this module - initialize the datastructures for
4248 CFG layout changes. It keeps LOOPS up-to-date if not null.
4250 FLAGS is a set of additional flags to pass to cleanup_cfg(). */
4253 cfg_layout_initialize (unsigned int flags
)
4258 /* Once bb partitioning is complete, cfg layout mode should not be
4259 re-entered. Entering cfg layout mode may require fixups. As an
4260 example, if edge forwarding performed when optimizing the cfg
4261 layout required moving a block from the hot to the cold
4262 section. This would create an illegal partitioning unless some
4263 manual fixup was performed. */
4264 gcc_assert (!(crtl
->bb_reorder_complete
4265 && flag_reorder_blocks_and_partition
));
4267 initialize_original_copy_tables ();
4269 cfg_layout_rtl_register_cfg_hooks ();
4271 record_effective_endpoints ();
4273 /* Make sure that the targets of non local gotos are marked. */
4274 for (x
= nonlocal_goto_handler_labels
; x
; x
= x
->next ())
4276 bb
= BLOCK_FOR_INSN (x
->insn ());
4277 bb
->flags
|= BB_NON_LOCAL_GOTO_TARGET
;
4280 cleanup_cfg (CLEANUP_CFGLAYOUT
| flags
);
4283 /* Splits superblocks. */
4285 break_superblocks (void)
4287 sbitmap superblocks
;
4291 superblocks
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
4292 bitmap_clear (superblocks
);
4294 FOR_EACH_BB_FN (bb
, cfun
)
4295 if (bb
->flags
& BB_SUPERBLOCK
)
4297 bb
->flags
&= ~BB_SUPERBLOCK
;
4298 bitmap_set_bit (superblocks
, bb
->index
);
4304 rebuild_jump_labels (get_insns ());
4305 find_many_sub_basic_blocks (superblocks
);
4311 /* Finalize the changes: reorder insn list according to the sequence specified
4312 by aux pointers, enter compensation code, rebuild scope forest. */
4315 cfg_layout_finalize (void)
4317 #ifdef ENABLE_CHECKING
4318 verify_flow_info ();
4320 force_one_exit_fallthru ();
4321 rtl_register_cfg_hooks ();
4322 if (reload_completed
&& !targetm
.have_epilogue ())
4323 fixup_fallthru_exit_predecessor ();
4324 fixup_reorder_chain ();
4326 rebuild_jump_labels (get_insns ());
4327 delete_dead_jumptables ();
4329 #ifdef ENABLE_CHECKING
4330 verify_insn_chain ();
4331 verify_flow_info ();
4336 /* Same as split_block but update cfg_layout structures. */
4339 cfg_layout_split_block (basic_block bb
, void *insnp
)
4341 rtx insn
= (rtx
) insnp
;
4342 basic_block new_bb
= rtl_split_block (bb
, insn
);
4344 BB_FOOTER (new_bb
) = BB_FOOTER (bb
);
4345 BB_FOOTER (bb
) = NULL
;
4350 /* Redirect Edge to DEST. */
4352 cfg_layout_redirect_edge_and_branch (edge e
, basic_block dest
)
4354 basic_block src
= e
->src
;
4357 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
4360 if (e
->dest
== dest
)
4363 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4364 && (ret
= try_redirect_by_replacing_jump (e
, dest
, true)))
4366 df_set_bb_dirty (src
);
4370 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4371 && (e
->flags
& EDGE_FALLTHRU
) && !(e
->flags
& EDGE_COMPLEX
))
4374 fprintf (dump_file
, "Redirecting entry edge from bb %i to %i\n",
4375 e
->src
->index
, dest
->index
);
4377 df_set_bb_dirty (e
->src
);
4378 redirect_edge_succ (e
, dest
);
4382 /* Redirect_edge_and_branch may decide to turn branch into fallthru edge
4383 in the case the basic block appears to be in sequence. Avoid this
4386 if (e
->flags
& EDGE_FALLTHRU
)
4388 /* Redirect any branch edges unified with the fallthru one. */
4389 if (JUMP_P (BB_END (src
))
4390 && label_is_jump_target_p (BB_HEAD (e
->dest
),
4396 fprintf (dump_file
, "Fallthru edge unified with branch "
4397 "%i->%i redirected to %i\n",
4398 e
->src
->index
, e
->dest
->index
, dest
->index
);
4399 e
->flags
&= ~EDGE_FALLTHRU
;
4400 redirected
= redirect_branch_edge (e
, dest
);
4401 gcc_assert (redirected
);
4402 redirected
->flags
|= EDGE_FALLTHRU
;
4403 df_set_bb_dirty (redirected
->src
);
4406 /* In case we are redirecting fallthru edge to the branch edge
4407 of conditional jump, remove it. */
4408 if (EDGE_COUNT (src
->succs
) == 2)
4410 /* Find the edge that is different from E. */
4411 edge s
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
);
4414 && any_condjump_p (BB_END (src
))
4415 && onlyjump_p (BB_END (src
)))
4416 delete_insn (BB_END (src
));
4419 fprintf (dump_file
, "Redirecting fallthru edge %i->%i to %i\n",
4420 e
->src
->index
, e
->dest
->index
, dest
->index
);
4421 ret
= redirect_edge_succ_nodup (e
, dest
);
4424 ret
= redirect_branch_edge (e
, dest
);
4426 /* We don't want simplejumps in the insn stream during cfglayout. */
4427 gcc_assert (!simplejump_p (BB_END (src
)));
4429 df_set_bb_dirty (src
);
4433 /* Simple wrapper as we always can redirect fallthru edges. */
4435 cfg_layout_redirect_edge_and_branch_force (edge e
, basic_block dest
)
4437 edge redirected
= cfg_layout_redirect_edge_and_branch (e
, dest
);
4439 gcc_assert (redirected
);
4443 /* Same as delete_basic_block but update cfg_layout structures. */
4446 cfg_layout_delete_block (basic_block bb
)
4448 rtx_insn
*insn
, *next
, *prev
= PREV_INSN (BB_HEAD (bb
)), *remaints
;
4453 next
= BB_HEAD (bb
);
4455 SET_NEXT_INSN (prev
) = BB_HEADER (bb
);
4457 set_first_insn (BB_HEADER (bb
));
4458 SET_PREV_INSN (BB_HEADER (bb
)) = prev
;
4459 insn
= BB_HEADER (bb
);
4460 while (NEXT_INSN (insn
))
4461 insn
= NEXT_INSN (insn
);
4462 SET_NEXT_INSN (insn
) = next
;
4463 SET_PREV_INSN (next
) = insn
;
4465 next
= NEXT_INSN (BB_END (bb
));
4468 insn
= BB_FOOTER (bb
);
4471 if (BARRIER_P (insn
))
4473 if (PREV_INSN (insn
))
4474 SET_NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
4476 BB_FOOTER (bb
) = NEXT_INSN (insn
);
4477 if (NEXT_INSN (insn
))
4478 SET_PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
4482 insn
= NEXT_INSN (insn
);
4487 SET_NEXT_INSN (insn
) = BB_FOOTER (bb
);
4488 SET_PREV_INSN (BB_FOOTER (bb
)) = insn
;
4489 while (NEXT_INSN (insn
))
4490 insn
= NEXT_INSN (insn
);
4491 SET_NEXT_INSN (insn
) = next
;
4493 SET_PREV_INSN (next
) = insn
;
4495 set_last_insn (insn
);
4498 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
4499 to
= &BB_HEADER (bb
->next_bb
);
4501 to
= &cfg_layout_function_footer
;
4503 rtl_delete_block (bb
);
4506 prev
= NEXT_INSN (prev
);
4508 prev
= get_insns ();
4510 next
= PREV_INSN (next
);
4512 next
= get_last_insn ();
4514 if (next
&& NEXT_INSN (next
) != prev
)
4516 remaints
= unlink_insn_chain (prev
, next
);
4518 while (NEXT_INSN (insn
))
4519 insn
= NEXT_INSN (insn
);
4520 SET_NEXT_INSN (insn
) = *to
;
4522 SET_PREV_INSN (*to
) = insn
;
4527 /* Return true when blocks A and B can be safely merged. */
4530 cfg_layout_can_merge_blocks_p (basic_block a
, basic_block b
)
4532 /* If we are partitioning hot/cold basic blocks, we don't want to
4533 mess up unconditional or indirect jumps that cross between hot
4536 Basic block partitioning may result in some jumps that appear to
4537 be optimizable (or blocks that appear to be mergeable), but which really
4538 must be left untouched (they are required to make it safely across
4539 partition boundaries). See the comments at the top of
4540 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
4542 if (BB_PARTITION (a
) != BB_PARTITION (b
))
4545 /* Protect the loop latches. */
4546 if (current_loops
&& b
->loop_father
->latch
== b
)
4549 /* If we would end up moving B's instructions, make sure it doesn't fall
4550 through into the exit block, since we cannot recover from a fallthrough
4551 edge into the exit block occurring in the middle of a function. */
4552 if (NEXT_INSN (BB_END (a
)) != BB_HEAD (b
))
4554 edge e
= find_fallthru_edge (b
->succs
);
4555 if (e
&& e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4559 /* There must be exactly one edge in between the blocks. */
4560 return (single_succ_p (a
)
4561 && single_succ (a
) == b
4562 && single_pred_p (b
) == 1
4564 /* Must be simple edge. */
4565 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
4566 && a
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4567 && b
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
4568 /* If the jump insn has side effects, we can't kill the edge.
4569 When not optimizing, try_redirect_by_replacing_jump will
4570 not allow us to redirect an edge by replacing a table jump. */
4571 && (!JUMP_P (BB_END (a
))
4572 || ((!optimize
|| reload_completed
)
4573 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
4576 /* Merge block A and B. The blocks must be mergeable. */
4579 cfg_layout_merge_blocks (basic_block a
, basic_block b
)
4581 bool forwarder_p
= (b
->flags
& BB_FORWARDER_BLOCK
) != 0;
4584 gcc_checking_assert (cfg_layout_can_merge_blocks_p (a
, b
));
4587 fprintf (dump_file
, "Merging block %d into block %d...\n", b
->index
,
4590 /* If there was a CODE_LABEL beginning B, delete it. */
4591 if (LABEL_P (BB_HEAD (b
)))
4593 delete_insn (BB_HEAD (b
));
4596 /* We should have fallthru edge in a, or we can do dummy redirection to get
4598 if (JUMP_P (BB_END (a
)))
4599 try_redirect_by_replacing_jump (EDGE_SUCC (a
, 0), b
, true);
4600 gcc_assert (!JUMP_P (BB_END (a
)));
4602 /* When not optimizing and the edge is the only place in RTL which holds
4603 some unique locus, emit a nop with that locus in between. */
4605 emit_nop_for_unique_locus_between (a
, b
);
4607 /* Move things from b->footer after a->footer. */
4611 BB_FOOTER (a
) = BB_FOOTER (b
);
4614 rtx_insn
*last
= BB_FOOTER (a
);
4616 while (NEXT_INSN (last
))
4617 last
= NEXT_INSN (last
);
4618 SET_NEXT_INSN (last
) = BB_FOOTER (b
);
4619 SET_PREV_INSN (BB_FOOTER (b
)) = last
;
4621 BB_FOOTER (b
) = NULL
;
4624 /* Move things from b->header before a->footer.
4625 Note that this may include dead tablejump data, but we don't clean
4626 those up until we go out of cfglayout mode. */
4629 if (! BB_FOOTER (a
))
4630 BB_FOOTER (a
) = BB_HEADER (b
);
4633 rtx_insn
*last
= BB_HEADER (b
);
4635 while (NEXT_INSN (last
))
4636 last
= NEXT_INSN (last
);
4637 SET_NEXT_INSN (last
) = BB_FOOTER (a
);
4638 SET_PREV_INSN (BB_FOOTER (a
)) = last
;
4639 BB_FOOTER (a
) = BB_HEADER (b
);
4641 BB_HEADER (b
) = NULL
;
4644 /* In the case basic blocks are not adjacent, move them around. */
4645 if (NEXT_INSN (BB_END (a
)) != BB_HEAD (b
))
4647 insn
= unlink_insn_chain (BB_HEAD (b
), BB_END (b
));
4649 emit_insn_after_noloc (insn
, BB_END (a
), a
);
4651 /* Otherwise just re-associate the instructions. */
4655 BB_END (a
) = BB_END (b
);
4658 /* emit_insn_after_noloc doesn't call df_insn_change_bb.
4659 We need to explicitly call. */
4660 update_bb_for_insn_chain (insn
, BB_END (b
), a
);
4662 /* Skip possible DELETED_LABEL insn. */
4663 if (!NOTE_INSN_BASIC_BLOCK_P (insn
))
4664 insn
= NEXT_INSN (insn
);
4665 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
4666 BB_HEAD (b
) = BB_END (b
) = NULL
;
4669 df_bb_delete (b
->index
);
4671 /* If B was a forwarder block, propagate the locus on the edge. */
4673 && LOCATION_LOCUS (EDGE_SUCC (b
, 0)->goto_locus
) == UNKNOWN_LOCATION
)
4674 EDGE_SUCC (b
, 0)->goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
4677 fprintf (dump_file
, "Merged blocks %d and %d.\n", a
->index
, b
->index
);
4683 cfg_layout_split_edge (edge e
)
4685 basic_block new_bb
=
4686 create_basic_block (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4687 ? NEXT_INSN (BB_END (e
->src
)) : get_insns (),
4690 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4691 BB_COPY_PARTITION (new_bb
, e
->src
);
4693 BB_COPY_PARTITION (new_bb
, e
->dest
);
4694 make_edge (new_bb
, e
->dest
, EDGE_FALLTHRU
);
4695 redirect_edge_and_branch_force (e
, new_bb
);
4700 /* Do postprocessing after making a forwarder block joined by edge FALLTHRU. */
4703 rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED
)
4707 /* Return true if BB contains only labels or non-executable
4711 rtl_block_empty_p (basic_block bb
)
4715 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4716 || bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4719 FOR_BB_INSNS (bb
, insn
)
4720 if (NONDEBUG_INSN_P (insn
) && !any_uncondjump_p (insn
))
4726 /* Split a basic block if it ends with a conditional branch and if
4727 the other part of the block is not empty. */
4730 rtl_split_block_before_cond_jump (basic_block bb
)
4733 rtx_insn
*split_point
= NULL
;
4734 rtx_insn
*last
= NULL
;
4735 bool found_code
= false;
4737 FOR_BB_INSNS (bb
, insn
)
4739 if (any_condjump_p (insn
))
4741 else if (NONDEBUG_INSN_P (insn
))
4746 /* Did not find everything. */
4747 if (found_code
&& split_point
)
4748 return split_block (bb
, split_point
)->dest
;
4753 /* Return 1 if BB ends with a call, possibly followed by some
4754 instructions that must stay with the call, 0 otherwise. */
4757 rtl_block_ends_with_call_p (basic_block bb
)
4759 rtx_insn
*insn
= BB_END (bb
);
4761 while (!CALL_P (insn
)
4762 && insn
!= BB_HEAD (bb
)
4763 && (keep_with_call_p (insn
)
4765 || DEBUG_INSN_P (insn
)))
4766 insn
= PREV_INSN (insn
);
4767 return (CALL_P (insn
));
4770 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
4773 rtl_block_ends_with_condjump_p (const_basic_block bb
)
4775 return any_condjump_p (BB_END (bb
));
4778 /* Return true if we need to add fake edge to exit.
4779 Helper function for rtl_flow_call_edges_add. */
4782 need_fake_edge_p (const rtx_insn
*insn
)
4788 && !SIBLING_CALL_P (insn
)
4789 && !find_reg_note (insn
, REG_NORETURN
, NULL
)
4790 && !(RTL_CONST_OR_PURE_CALL_P (insn
))))
4793 return ((GET_CODE (PATTERN (insn
)) == ASM_OPERANDS
4794 && MEM_VOLATILE_P (PATTERN (insn
)))
4795 || (GET_CODE (PATTERN (insn
)) == PARALLEL
4796 && asm_noperands (insn
) != -1
4797 && MEM_VOLATILE_P (XVECEXP (PATTERN (insn
), 0, 0)))
4798 || GET_CODE (PATTERN (insn
)) == ASM_INPUT
);
4801 /* Add fake edges to the function exit for any non constant and non noreturn
4802 calls, volatile inline assembly in the bitmap of blocks specified by
4803 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
4806 The goal is to expose cases in which entering a basic block does not imply
4807 that all subsequent instructions must be executed. */
4810 rtl_flow_call_edges_add (sbitmap blocks
)
4813 int blocks_split
= 0;
4814 int last_bb
= last_basic_block_for_fn (cfun
);
4815 bool check_last_block
= false;
4817 if (n_basic_blocks_for_fn (cfun
) == NUM_FIXED_BLOCKS
)
4821 check_last_block
= true;
4823 check_last_block
= bitmap_bit_p (blocks
,
4824 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
->index
);
4826 /* In the last basic block, before epilogue generation, there will be
4827 a fallthru edge to EXIT. Special care is required if the last insn
4828 of the last basic block is a call because make_edge folds duplicate
4829 edges, which would result in the fallthru edge also being marked
4830 fake, which would result in the fallthru edge being removed by
4831 remove_fake_edges, which would result in an invalid CFG.
4833 Moreover, we can't elide the outgoing fake edge, since the block
4834 profiler needs to take this into account in order to solve the minimal
4835 spanning tree in the case that the call doesn't return.
4837 Handle this by adding a dummy instruction in a new last basic block. */
4838 if (check_last_block
)
4840 basic_block bb
= EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
;
4841 rtx_insn
*insn
= BB_END (bb
);
4843 /* Back up past insns that must be kept in the same block as a call. */
4844 while (insn
!= BB_HEAD (bb
)
4845 && keep_with_call_p (insn
))
4846 insn
= PREV_INSN (insn
);
4848 if (need_fake_edge_p (insn
))
4852 e
= find_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
4855 insert_insn_on_edge (gen_use (const0_rtx
), e
);
4856 commit_edge_insertions ();
4861 /* Now add fake edges to the function exit for any non constant
4862 calls since there is no way that we can determine if they will
4865 for (i
= NUM_FIXED_BLOCKS
; i
< last_bb
; i
++)
4867 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
4869 rtx_insn
*prev_insn
;
4874 if (blocks
&& !bitmap_bit_p (blocks
, i
))
4877 for (insn
= BB_END (bb
); ; insn
= prev_insn
)
4879 prev_insn
= PREV_INSN (insn
);
4880 if (need_fake_edge_p (insn
))
4883 rtx_insn
*split_at_insn
= insn
;
4885 /* Don't split the block between a call and an insn that should
4886 remain in the same block as the call. */
4888 while (split_at_insn
!= BB_END (bb
)
4889 && keep_with_call_p (NEXT_INSN (split_at_insn
)))
4890 split_at_insn
= NEXT_INSN (split_at_insn
);
4892 /* The handling above of the final block before the epilogue
4893 should be enough to verify that there is no edge to the exit
4894 block in CFG already. Calling make_edge in such case would
4895 cause us to mark that edge as fake and remove it later. */
4897 #ifdef ENABLE_CHECKING
4898 if (split_at_insn
== BB_END (bb
))
4900 e
= find_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
4901 gcc_assert (e
== NULL
);
4905 /* Note that the following may create a new basic block
4906 and renumber the existing basic blocks. */
4907 if (split_at_insn
!= BB_END (bb
))
4909 e
= split_block (bb
, split_at_insn
);
4914 make_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), EDGE_FAKE
);
4917 if (insn
== BB_HEAD (bb
))
4923 verify_flow_info ();
4925 return blocks_split
;
4928 /* Add COMP_RTX as a condition at end of COND_BB. FIRST_HEAD is
4929 the conditional branch target, SECOND_HEAD should be the fall-thru
4930 there is no need to handle this here the loop versioning code handles
4931 this. the reason for SECON_HEAD is that it is needed for condition
4932 in trees, and this should be of the same type since it is a hook. */
4934 rtl_lv_add_condition_to_bb (basic_block first_head
,
4935 basic_block second_head ATTRIBUTE_UNUSED
,
4936 basic_block cond_bb
, void *comp_rtx
)
4938 rtx_code_label
*label
;
4939 rtx_insn
*seq
, *jump
;
4940 rtx op0
= XEXP ((rtx
)comp_rtx
, 0);
4941 rtx op1
= XEXP ((rtx
)comp_rtx
, 1);
4942 enum rtx_code comp
= GET_CODE ((rtx
)comp_rtx
);
4946 label
= block_label (first_head
);
4947 mode
= GET_MODE (op0
);
4948 if (mode
== VOIDmode
)
4949 mode
= GET_MODE (op1
);
4952 op0
= force_operand (op0
, NULL_RTX
);
4953 op1
= force_operand (op1
, NULL_RTX
);
4954 do_compare_rtx_and_jump (op0
, op1
, comp
, 0, mode
, NULL_RTX
, NULL
, label
, -1);
4955 jump
= get_last_insn ();
4956 JUMP_LABEL (jump
) = label
;
4957 LABEL_NUSES (label
)++;
4961 /* Add the new cond, in the new head. */
4962 emit_insn_after (seq
, BB_END (cond_bb
));
4966 /* Given a block B with unconditional branch at its end, get the
4967 store the return the branch edge and the fall-thru edge in
4968 BRANCH_EDGE and FALLTHRU_EDGE respectively. */
4970 rtl_extract_cond_bb_edges (basic_block b
, edge
*branch_edge
,
4971 edge
*fallthru_edge
)
4973 edge e
= EDGE_SUCC (b
, 0);
4975 if (e
->flags
& EDGE_FALLTHRU
)
4978 *branch_edge
= EDGE_SUCC (b
, 1);
4983 *fallthru_edge
= EDGE_SUCC (b
, 1);
4988 init_rtl_bb_info (basic_block bb
)
4990 gcc_assert (!bb
->il
.x
.rtl
);
4991 bb
->il
.x
.head_
= NULL
;
4992 bb
->il
.x
.rtl
= ggc_cleared_alloc
<rtl_bb_info
> ();
4995 /* Returns true if it is possible to remove edge E by redirecting
4996 it to the destination of the other edge from E->src. */
4999 rtl_can_remove_branch_p (const_edge e
)
5001 const_basic_block src
= e
->src
;
5002 const_basic_block target
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
;
5003 const rtx_insn
*insn
= BB_END (src
);
5006 /* The conditions are taken from try_redirect_by_replacing_jump. */
5007 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
5010 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
5013 if (BB_PARTITION (src
) != BB_PARTITION (target
))
5016 if (!onlyjump_p (insn
)
5017 || tablejump_p (insn
, NULL
, NULL
))
5020 set
= single_set (insn
);
5021 if (!set
|| side_effects_p (set
))
5028 rtl_duplicate_bb (basic_block bb
)
5030 bb
= cfg_layout_duplicate_bb (bb
);
5035 /* Do book-keeping of basic block BB for the profile consistency checker.
5036 If AFTER_PASS is 0, do pre-pass accounting, or if AFTER_PASS is 1
5037 then do post-pass accounting. Store the counting in RECORD. */
5039 rtl_account_profile_record (basic_block bb
, int after_pass
,
5040 struct profile_record
*record
)
5043 FOR_BB_INSNS (bb
, insn
)
5046 record
->size
[after_pass
]
5047 += insn_rtx_cost (PATTERN (insn
), false);
5048 if (profile_status_for_fn (cfun
) == PROFILE_READ
)
5049 record
->time
[after_pass
]
5050 += insn_rtx_cost (PATTERN (insn
), true) * bb
->count
;
5051 else if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
)
5052 record
->time
[after_pass
]
5053 += insn_rtx_cost (PATTERN (insn
), true) * bb
->frequency
;
5057 /* Implementation of CFG manipulation for linearized RTL. */
5058 struct cfg_hooks rtl_cfg_hooks
= {
5060 rtl_verify_flow_info
,
5062 rtl_dump_bb_for_graph
,
5063 rtl_create_basic_block
,
5064 rtl_redirect_edge_and_branch
,
5065 rtl_redirect_edge_and_branch_force
,
5066 rtl_can_remove_branch_p
,
5069 rtl_move_block_after
,
5070 rtl_can_merge_blocks
, /* can_merge_blocks_p */
5074 cfg_layout_can_duplicate_bb_p
,
5077 rtl_make_forwarder_block
,
5078 rtl_tidy_fallthru_edge
,
5079 rtl_force_nonfallthru
,
5080 rtl_block_ends_with_call_p
,
5081 rtl_block_ends_with_condjump_p
,
5082 rtl_flow_call_edges_add
,
5083 NULL
, /* execute_on_growing_pred */
5084 NULL
, /* execute_on_shrinking_pred */
5085 NULL
, /* duplicate loop for trees */
5086 NULL
, /* lv_add_condition_to_bb */
5087 NULL
, /* lv_adjust_loop_header_phi*/
5088 NULL
, /* extract_cond_bb_edges */
5089 NULL
, /* flush_pending_stmts */
5090 rtl_block_empty_p
, /* block_empty_p */
5091 rtl_split_block_before_cond_jump
, /* split_block_before_cond_jump */
5092 rtl_account_profile_record
,
5095 /* Implementation of CFG manipulation for cfg layout RTL, where
5096 basic block connected via fallthru edges does not have to be adjacent.
5097 This representation will hopefully become the default one in future
5098 version of the compiler. */
5100 struct cfg_hooks cfg_layout_rtl_cfg_hooks
= {
5102 rtl_verify_flow_info_1
,
5104 rtl_dump_bb_for_graph
,
5105 cfg_layout_create_basic_block
,
5106 cfg_layout_redirect_edge_and_branch
,
5107 cfg_layout_redirect_edge_and_branch_force
,
5108 rtl_can_remove_branch_p
,
5109 cfg_layout_delete_block
,
5110 cfg_layout_split_block
,
5111 rtl_move_block_after
,
5112 cfg_layout_can_merge_blocks_p
,
5113 cfg_layout_merge_blocks
,
5116 cfg_layout_can_duplicate_bb_p
,
5117 cfg_layout_duplicate_bb
,
5118 cfg_layout_split_edge
,
5119 rtl_make_forwarder_block
,
5120 NULL
, /* tidy_fallthru_edge */
5121 rtl_force_nonfallthru
,
5122 rtl_block_ends_with_call_p
,
5123 rtl_block_ends_with_condjump_p
,
5124 rtl_flow_call_edges_add
,
5125 NULL
, /* execute_on_growing_pred */
5126 NULL
, /* execute_on_shrinking_pred */
5127 duplicate_loop_to_header_edge
, /* duplicate loop for trees */
5128 rtl_lv_add_condition_to_bb
, /* lv_add_condition_to_bb */
5129 NULL
, /* lv_adjust_loop_header_phi*/
5130 rtl_extract_cond_bb_edges
, /* extract_cond_bb_edges */
5131 NULL
, /* flush_pending_stmts */
5132 rtl_block_empty_p
, /* block_empty_p */
5133 rtl_split_block_before_cond_jump
, /* split_block_before_cond_jump */
5134 rtl_account_profile_record
,
5137 #include "gt-cfgrtl.h"