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"
59 #include "insn-attr.h"
60 #include "insn-config.h"
70 #include "common/common-target.h"
72 #include "tree-pass.h"
73 #include "print-rtl.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
*)
486 /* The resource.c machinery uses DF but the CFG isn't guaranteed to be
487 valid at that point so it would be too late to call df_analyze. */
488 if (DELAY_SLOTS
&& optimize
> 0 && flag_delayed_branch
)
490 df_note_add_problem ();
494 if (crtl
->has_bb_partition
)
495 insert_section_boundary_note ();
504 make_pass_free_cfg (gcc::context
*ctxt
)
506 return new pass_free_cfg (ctxt
);
509 /* Return RTX to emit after when we want to emit code on the entry of function. */
511 entry_of_function (void)
513 return (n_basic_blocks_for_fn (cfun
) > NUM_FIXED_BLOCKS
?
514 BB_HEAD (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
) : get_insns ());
517 /* Emit INSN at the entry point of the function, ensuring that it is only
518 executed once per function. */
520 emit_insn_at_entry (rtx insn
)
522 edge_iterator ei
= ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
);
523 edge e
= ei_safe_edge (ei
);
524 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
526 insert_insn_on_edge (insn
, e
);
527 commit_edge_insertions ();
530 /* Update BLOCK_FOR_INSN of insns between BEGIN and END
531 (or BARRIER if found) and notify df of the bb change.
532 The insn chain range is inclusive
533 (i.e. both BEGIN and END will be updated. */
536 update_bb_for_insn_chain (rtx_insn
*begin
, rtx_insn
*end
, basic_block bb
)
540 end
= NEXT_INSN (end
);
541 for (insn
= begin
; insn
!= end
; insn
= NEXT_INSN (insn
))
542 if (!BARRIER_P (insn
))
543 df_insn_change_bb (insn
, bb
);
546 /* Update BLOCK_FOR_INSN of insns in BB to BB,
547 and notify df of the change. */
550 update_bb_for_insn (basic_block bb
)
552 update_bb_for_insn_chain (BB_HEAD (bb
), BB_END (bb
), bb
);
556 /* Like active_insn_p, except keep the return value clobber around
557 even after reload. */
560 flow_active_insn_p (const rtx_insn
*insn
)
562 if (active_insn_p (insn
))
565 /* A clobber of the function return value exists for buggy
566 programs that fail to return a value. Its effect is to
567 keep the return value from being live across the entire
568 function. If we allow it to be skipped, we introduce the
569 possibility for register lifetime confusion. */
570 if (GET_CODE (PATTERN (insn
)) == CLOBBER
571 && REG_P (XEXP (PATTERN (insn
), 0))
572 && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn
), 0)))
578 /* Return true if the block has no effect and only forwards control flow to
579 its single destination. */
582 contains_no_active_insn_p (const_basic_block bb
)
586 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
) || bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
587 || !single_succ_p (bb
))
590 for (insn
= BB_HEAD (bb
); insn
!= BB_END (bb
); insn
= NEXT_INSN (insn
))
591 if (INSN_P (insn
) && flow_active_insn_p (insn
))
594 return (!INSN_P (insn
)
595 || (JUMP_P (insn
) && simplejump_p (insn
))
596 || !flow_active_insn_p (insn
));
599 /* Likewise, but protect loop latches, headers and preheaders. */
600 /* FIXME: Make this a cfg hook. */
603 forwarder_block_p (const_basic_block bb
)
605 if (!contains_no_active_insn_p (bb
))
608 /* Protect loop latches, headers and preheaders. */
612 if (bb
->loop_father
->header
== bb
)
614 dest
= EDGE_SUCC (bb
, 0)->dest
;
615 if (dest
->loop_father
->header
== dest
)
622 /* Return nonzero if we can reach target from src by falling through. */
623 /* FIXME: Make this a cfg hook, the result is only valid in cfgrtl mode. */
626 can_fallthru (basic_block src
, basic_block target
)
628 rtx_insn
*insn
= BB_END (src
);
633 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
635 if (src
->next_bb
!= target
)
638 /* ??? Later we may add code to move jump tables offline. */
639 if (tablejump_p (insn
, NULL
, NULL
))
642 FOR_EACH_EDGE (e
, ei
, src
->succs
)
643 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
644 && e
->flags
& EDGE_FALLTHRU
)
647 insn2
= BB_HEAD (target
);
648 if (!active_insn_p (insn2
))
649 insn2
= next_active_insn (insn2
);
651 return next_active_insn (insn
) == insn2
;
654 /* Return nonzero if we could reach target from src by falling through,
655 if the target was made adjacent. If we already have a fall-through
656 edge to the exit block, we can't do that. */
658 could_fall_through (basic_block src
, basic_block target
)
663 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
665 FOR_EACH_EDGE (e
, ei
, src
->succs
)
666 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
667 && e
->flags
& EDGE_FALLTHRU
)
672 /* Return the NOTE_INSN_BASIC_BLOCK of BB. */
674 bb_note (basic_block bb
)
680 note
= NEXT_INSN (note
);
682 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
683 return as_a
<rtx_note
*> (note
);
686 /* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK
687 note associated with the BLOCK. */
690 first_insn_after_basic_block_note (basic_block block
)
694 /* Get the first instruction in the block. */
695 insn
= BB_HEAD (block
);
697 if (insn
== NULL_RTX
)
700 insn
= NEXT_INSN (insn
);
701 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
703 return NEXT_INSN (insn
);
706 /* Creates a new basic block just after basic block BB by splitting
707 everything after specified instruction INSNP. */
710 rtl_split_block (basic_block bb
, void *insnp
)
713 rtx_insn
*insn
= (rtx_insn
*) insnp
;
719 insn
= first_insn_after_basic_block_note (bb
);
723 rtx_insn
*next
= insn
;
725 insn
= PREV_INSN (insn
);
727 /* If the block contains only debug insns, insn would have
728 been NULL in a non-debug compilation, and then we'd end
729 up emitting a DELETED note. For -fcompare-debug
730 stability, emit the note too. */
731 if (insn
!= BB_END (bb
)
732 && DEBUG_INSN_P (next
)
733 && DEBUG_INSN_P (BB_END (bb
)))
735 while (next
!= BB_END (bb
) && DEBUG_INSN_P (next
))
736 next
= NEXT_INSN (next
);
738 if (next
== BB_END (bb
))
739 emit_note_after (NOTE_INSN_DELETED
, next
);
743 insn
= get_last_insn ();
746 /* We probably should check type of the insn so that we do not create
747 inconsistent cfg. It is checked in verify_flow_info anyway, so do not
749 if (insn
== BB_END (bb
))
750 emit_note_after (NOTE_INSN_DELETED
, insn
);
752 /* Create the new basic block. */
753 new_bb
= create_basic_block (NEXT_INSN (insn
), BB_END (bb
), bb
);
754 BB_COPY_PARTITION (new_bb
, bb
);
757 /* Redirect the outgoing edges. */
758 new_bb
->succs
= bb
->succs
;
760 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
763 /* The new block starts off being dirty. */
764 df_set_bb_dirty (bb
);
768 /* Return true if the single edge between blocks A and B is the only place
769 in RTL which holds some unique locus. */
772 unique_locus_on_edge_between_p (basic_block a
, basic_block b
)
774 const location_t goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
775 rtx_insn
*insn
, *end
;
777 if (LOCATION_LOCUS (goto_locus
) == UNKNOWN_LOCATION
)
780 /* First scan block A backward. */
782 end
= PREV_INSN (BB_HEAD (a
));
783 while (insn
!= end
&& (!NONDEBUG_INSN_P (insn
) || !INSN_HAS_LOCATION (insn
)))
784 insn
= PREV_INSN (insn
);
786 if (insn
!= end
&& INSN_LOCATION (insn
) == goto_locus
)
789 /* Then scan block B forward. */
793 end
= NEXT_INSN (BB_END (b
));
794 while (insn
!= end
&& !NONDEBUG_INSN_P (insn
))
795 insn
= NEXT_INSN (insn
);
797 if (insn
!= end
&& INSN_HAS_LOCATION (insn
)
798 && INSN_LOCATION (insn
) == goto_locus
)
805 /* If the single edge between blocks A and B is the only place in RTL which
806 holds some unique locus, emit a nop with that locus between the blocks. */
809 emit_nop_for_unique_locus_between (basic_block a
, basic_block b
)
811 if (!unique_locus_on_edge_between_p (a
, b
))
814 BB_END (a
) = emit_insn_after_noloc (gen_nop (), BB_END (a
), a
);
815 INSN_LOCATION (BB_END (a
)) = EDGE_SUCC (a
, 0)->goto_locus
;
818 /* Blocks A and B are to be merged into a single block A. The insns
819 are already contiguous. */
822 rtl_merge_blocks (basic_block a
, basic_block b
)
824 rtx_insn
*b_head
= BB_HEAD (b
), *b_end
= BB_END (b
), *a_end
= BB_END (a
);
825 rtx_insn
*del_first
= NULL
, *del_last
= NULL
;
826 rtx_insn
*b_debug_start
= b_end
, *b_debug_end
= b_end
;
827 bool forwarder_p
= (b
->flags
& BB_FORWARDER_BLOCK
) != 0;
831 fprintf (dump_file
, "Merging block %d into block %d...\n", b
->index
,
834 while (DEBUG_INSN_P (b_end
))
835 b_end
= PREV_INSN (b_debug_start
= b_end
);
837 /* If there was a CODE_LABEL beginning B, delete it. */
838 if (LABEL_P (b_head
))
840 /* Detect basic blocks with nothing but a label. This can happen
841 in particular at the end of a function. */
845 del_first
= del_last
= b_head
;
846 b_head
= NEXT_INSN (b_head
);
849 /* Delete the basic block note and handle blocks containing just that
851 if (NOTE_INSN_BASIC_BLOCK_P (b_head
))
859 b_head
= NEXT_INSN (b_head
);
862 /* If there was a jump out of A, delete it. */
867 for (prev
= PREV_INSN (a_end
); ; prev
= PREV_INSN (prev
))
869 || NOTE_INSN_BASIC_BLOCK_P (prev
)
870 || prev
== BB_HEAD (a
))
875 /* If this was a conditional jump, we need to also delete
876 the insn that set cc0. */
877 if (HAVE_cc0
&& only_sets_cc0_p (prev
))
879 rtx_insn
*tmp
= prev
;
881 prev
= prev_nonnote_insn (prev
);
887 a_end
= PREV_INSN (del_first
);
889 else if (BARRIER_P (NEXT_INSN (a_end
)))
890 del_first
= NEXT_INSN (a_end
);
892 /* Delete everything marked above as well as crap that might be
893 hanging out between the two blocks. */
895 BB_HEAD (b
) = b_empty
? NULL
: b_head
;
896 delete_insn_chain (del_first
, del_last
, true);
898 /* When not optimizing and the edge is the only place in RTL which holds
899 some unique locus, emit a nop with that locus in between. */
902 emit_nop_for_unique_locus_between (a
, b
);
906 /* Reassociate the insns of B with A. */
909 update_bb_for_insn_chain (a_end
, b_debug_end
, a
);
911 BB_END (a
) = b_debug_end
;
914 else if (b_end
!= b_debug_end
)
916 /* Move any deleted labels and other notes between the end of A
917 and the debug insns that make up B after the debug insns,
918 bringing the debug insns into A while keeping the notes after
920 if (NEXT_INSN (a_end
) != b_debug_start
)
921 reorder_insns_nobb (NEXT_INSN (a_end
), PREV_INSN (b_debug_start
),
923 update_bb_for_insn_chain (b_debug_start
, b_debug_end
, a
);
924 BB_END (a
) = b_debug_end
;
927 df_bb_delete (b
->index
);
929 /* If B was a forwarder block, propagate the locus on the edge. */
931 && LOCATION_LOCUS (EDGE_SUCC (b
, 0)->goto_locus
) == UNKNOWN_LOCATION
)
932 EDGE_SUCC (b
, 0)->goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
935 fprintf (dump_file
, "Merged blocks %d and %d.\n", a
->index
, b
->index
);
939 /* Return true when block A and B can be merged. */
942 rtl_can_merge_blocks (basic_block a
, basic_block b
)
944 /* If we are partitioning hot/cold basic blocks, we don't want to
945 mess up unconditional or indirect jumps that cross between hot
948 Basic block partitioning may result in some jumps that appear to
949 be optimizable (or blocks that appear to be mergeable), but which really
950 must be left untouched (they are required to make it safely across
951 partition boundaries). See the comments at the top of
952 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
954 if (BB_PARTITION (a
) != BB_PARTITION (b
))
957 /* Protect the loop latches. */
958 if (current_loops
&& b
->loop_father
->latch
== b
)
961 /* There must be exactly one edge in between the blocks. */
962 return (single_succ_p (a
)
963 && single_succ (a
) == b
966 /* Must be simple edge. */
967 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
969 && a
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
970 && b
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
971 /* If the jump insn has side effects,
972 we can't kill the edge. */
973 && (!JUMP_P (BB_END (a
))
975 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
978 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
982 block_label (basic_block block
)
984 if (block
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
987 if (!LABEL_P (BB_HEAD (block
)))
989 BB_HEAD (block
) = emit_label_before (gen_label_rtx (), BB_HEAD (block
));
992 return as_a
<rtx_code_label
*> (BB_HEAD (block
));
995 /* Attempt to perform edge redirection by replacing possibly complex jump
996 instruction by unconditional jump or removing jump completely. This can
997 apply only if all edges now point to the same block. The parameters and
998 return values are equivalent to redirect_edge_and_branch. */
1001 try_redirect_by_replacing_jump (edge e
, basic_block target
, bool in_cfglayout
)
1003 basic_block src
= e
->src
;
1004 rtx_insn
*insn
= BB_END (src
), *kill_from
;
1008 /* If we are partitioning hot/cold basic blocks, we don't want to
1009 mess up unconditional or indirect jumps that cross between hot
1012 Basic block partitioning may result in some jumps that appear to
1013 be optimizable (or blocks that appear to be mergeable), but which really
1014 must be left untouched (they are required to make it safely across
1015 partition boundaries). See the comments at the top of
1016 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
1018 if (BB_PARTITION (src
) != BB_PARTITION (target
))
1021 /* We can replace or remove a complex jump only when we have exactly
1022 two edges. Also, if we have exactly one outgoing edge, we can
1024 if (EDGE_COUNT (src
->succs
) >= 3
1025 /* Verify that all targets will be TARGET. Specifically, the
1026 edge that is not E must also go to TARGET. */
1027 || (EDGE_COUNT (src
->succs
) == 2
1028 && EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
!= target
))
1031 if (!onlyjump_p (insn
))
1033 if ((!optimize
|| reload_completed
) && tablejump_p (insn
, NULL
, NULL
))
1036 /* Avoid removing branch with side effects. */
1037 set
= single_set (insn
);
1038 if (!set
|| side_effects_p (set
))
1041 /* In case we zap a conditional jump, we'll need to kill
1042 the cc0 setter too. */
1044 if (HAVE_cc0
&& reg_mentioned_p (cc0_rtx
, PATTERN (insn
))
1045 && only_sets_cc0_p (PREV_INSN (insn
)))
1046 kill_from
= PREV_INSN (insn
);
1048 /* See if we can create the fallthru edge. */
1049 if (in_cfglayout
|| can_fallthru (src
, target
))
1052 fprintf (dump_file
, "Removing jump %i.\n", INSN_UID (insn
));
1055 /* Selectively unlink whole insn chain. */
1058 rtx_insn
*insn
= BB_FOOTER (src
);
1060 delete_insn_chain (kill_from
, BB_END (src
), false);
1062 /* Remove barriers but keep jumptables. */
1065 if (BARRIER_P (insn
))
1067 if (PREV_INSN (insn
))
1068 SET_NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
1070 BB_FOOTER (src
) = NEXT_INSN (insn
);
1071 if (NEXT_INSN (insn
))
1072 SET_PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
1076 insn
= NEXT_INSN (insn
);
1080 delete_insn_chain (kill_from
, PREV_INSN (BB_HEAD (target
)),
1084 /* If this already is simplejump, redirect it. */
1085 else if (simplejump_p (insn
))
1087 if (e
->dest
== target
)
1090 fprintf (dump_file
, "Redirecting jump %i from %i to %i.\n",
1091 INSN_UID (insn
), e
->dest
->index
, target
->index
);
1092 if (!redirect_jump (as_a
<rtx_jump_insn
*> (insn
),
1093 block_label (target
), 0))
1095 gcc_assert (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
));
1100 /* Cannot do anything for target exit block. */
1101 else if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1104 /* Or replace possibly complicated jump insn by simple jump insn. */
1107 rtx_code_label
*target_label
= block_label (target
);
1110 rtx_jump_table_data
*table
;
1112 emit_jump_insn_after_noloc (targetm
.gen_jump (target_label
), insn
);
1113 JUMP_LABEL (BB_END (src
)) = target_label
;
1114 LABEL_NUSES (target_label
)++;
1116 fprintf (dump_file
, "Replacing insn %i by jump %i\n",
1117 INSN_UID (insn
), INSN_UID (BB_END (src
)));
1120 delete_insn_chain (kill_from
, insn
, false);
1122 /* Recognize a tablejump that we are converting to a
1123 simple jump and remove its associated CODE_LABEL
1124 and ADDR_VEC or ADDR_DIFF_VEC. */
1125 if (tablejump_p (insn
, &label
, &table
))
1126 delete_insn_chain (label
, table
, false);
1128 barrier
= next_nonnote_insn (BB_END (src
));
1129 if (!barrier
|| !BARRIER_P (barrier
))
1130 emit_barrier_after (BB_END (src
));
1133 if (barrier
!= NEXT_INSN (BB_END (src
)))
1135 /* Move the jump before barrier so that the notes
1136 which originally were or were created before jump table are
1137 inside the basic block. */
1138 rtx_insn
*new_insn
= BB_END (src
);
1140 update_bb_for_insn_chain (NEXT_INSN (BB_END (src
)),
1141 PREV_INSN (barrier
), src
);
1143 SET_NEXT_INSN (PREV_INSN (new_insn
)) = NEXT_INSN (new_insn
);
1144 SET_PREV_INSN (NEXT_INSN (new_insn
)) = PREV_INSN (new_insn
);
1146 SET_NEXT_INSN (new_insn
) = barrier
;
1147 SET_NEXT_INSN (PREV_INSN (barrier
)) = new_insn
;
1149 SET_PREV_INSN (new_insn
) = PREV_INSN (barrier
);
1150 SET_PREV_INSN (barrier
) = new_insn
;
1155 /* Keep only one edge out and set proper flags. */
1156 if (!single_succ_p (src
))
1158 gcc_assert (single_succ_p (src
));
1160 e
= single_succ_edge (src
);
1162 e
->flags
= EDGE_FALLTHRU
;
1166 e
->probability
= REG_BR_PROB_BASE
;
1167 e
->count
= src
->count
;
1169 if (e
->dest
!= target
)
1170 redirect_edge_succ (e
, target
);
1174 /* Subroutine of redirect_branch_edge that tries to patch the jump
1175 instruction INSN so that it reaches block NEW. Do this
1176 only when it originally reached block OLD. Return true if this
1177 worked or the original target wasn't OLD, return false if redirection
1181 patch_jump_insn (rtx_insn
*insn
, rtx_insn
*old_label
, basic_block new_bb
)
1183 rtx_jump_table_data
*table
;
1185 /* Recognize a tablejump and adjust all matching cases. */
1186 if (tablejump_p (insn
, NULL
, &table
))
1190 rtx_code_label
*new_label
= block_label (new_bb
);
1192 if (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1194 vec
= table
->get_labels ();
1196 for (j
= GET_NUM_ELEM (vec
) - 1; j
>= 0; --j
)
1197 if (XEXP (RTVEC_ELT (vec
, j
), 0) == old_label
)
1199 RTVEC_ELT (vec
, j
) = gen_rtx_LABEL_REF (Pmode
, new_label
);
1200 --LABEL_NUSES (old_label
);
1201 ++LABEL_NUSES (new_label
);
1204 /* Handle casesi dispatch insns. */
1205 if ((tmp
= single_set (insn
)) != NULL
1206 && SET_DEST (tmp
) == pc_rtx
1207 && GET_CODE (SET_SRC (tmp
)) == IF_THEN_ELSE
1208 && GET_CODE (XEXP (SET_SRC (tmp
), 2)) == LABEL_REF
1209 && LABEL_REF_LABEL (XEXP (SET_SRC (tmp
), 2)) == old_label
)
1211 XEXP (SET_SRC (tmp
), 2) = gen_rtx_LABEL_REF (Pmode
,
1213 --LABEL_NUSES (old_label
);
1214 ++LABEL_NUSES (new_label
);
1217 else if ((tmp
= extract_asm_operands (PATTERN (insn
))) != NULL
)
1219 int i
, n
= ASM_OPERANDS_LABEL_LENGTH (tmp
);
1222 if (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1224 rtx_code_label
*new_label
= block_label (new_bb
);
1226 for (i
= 0; i
< n
; ++i
)
1228 rtx old_ref
= ASM_OPERANDS_LABEL (tmp
, i
);
1229 gcc_assert (GET_CODE (old_ref
) == LABEL_REF
);
1230 if (XEXP (old_ref
, 0) == old_label
)
1232 ASM_OPERANDS_LABEL (tmp
, i
)
1233 = gen_rtx_LABEL_REF (Pmode
, new_label
);
1234 --LABEL_NUSES (old_label
);
1235 ++LABEL_NUSES (new_label
);
1239 if (JUMP_LABEL (insn
) == old_label
)
1241 JUMP_LABEL (insn
) = new_label
;
1242 note
= find_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1244 remove_note (insn
, note
);
1248 note
= find_reg_note (insn
, REG_LABEL_TARGET
, old_label
);
1250 remove_note (insn
, note
);
1251 if (JUMP_LABEL (insn
) != new_label
1252 && !find_reg_note (insn
, REG_LABEL_TARGET
, new_label
))
1253 add_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1255 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, old_label
))
1257 XEXP (note
, 0) = new_label
;
1261 /* ?? We may play the games with moving the named labels from
1262 one basic block to the other in case only one computed_jump is
1264 if (computed_jump_p (insn
)
1265 /* A return instruction can't be redirected. */
1266 || returnjump_p (insn
))
1269 if (!currently_expanding_to_rtl
|| JUMP_LABEL (insn
) == old_label
)
1271 /* If the insn doesn't go where we think, we're confused. */
1272 gcc_assert (JUMP_LABEL (insn
) == old_label
);
1274 /* If the substitution doesn't succeed, die. This can happen
1275 if the back end emitted unrecognizable instructions or if
1276 target is exit block on some arches. */
1277 if (!redirect_jump (as_a
<rtx_jump_insn
*> (insn
),
1278 block_label (new_bb
), 0))
1280 gcc_assert (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
));
1289 /* Redirect edge representing branch of (un)conditional jump or tablejump,
1292 redirect_branch_edge (edge e
, basic_block target
)
1294 rtx_insn
*old_label
= BB_HEAD (e
->dest
);
1295 basic_block src
= e
->src
;
1296 rtx_insn
*insn
= BB_END (src
);
1298 /* We can only redirect non-fallthru edges of jump insn. */
1299 if (e
->flags
& EDGE_FALLTHRU
)
1301 else if (!JUMP_P (insn
) && !currently_expanding_to_rtl
)
1304 if (!currently_expanding_to_rtl
)
1306 if (!patch_jump_insn (as_a
<rtx_jump_insn
*> (insn
), old_label
, target
))
1310 /* When expanding this BB might actually contain multiple
1311 jumps (i.e. not yet split by find_many_sub_basic_blocks).
1312 Redirect all of those that match our label. */
1313 FOR_BB_INSNS (src
, insn
)
1314 if (JUMP_P (insn
) && !patch_jump_insn (as_a
<rtx_jump_insn
*> (insn
),
1319 fprintf (dump_file
, "Edge %i->%i redirected to %i\n",
1320 e
->src
->index
, e
->dest
->index
, target
->index
);
1322 if (e
->dest
!= target
)
1323 e
= redirect_edge_succ_nodup (e
, target
);
1328 /* Called when edge E has been redirected to a new destination,
1329 in order to update the region crossing flag on the edge and
1333 fixup_partition_crossing (edge e
)
1335 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) || e
->dest
1336 == EXIT_BLOCK_PTR_FOR_FN (cfun
))
1338 /* If we redirected an existing edge, it may already be marked
1339 crossing, even though the new src is missing a reg crossing note.
1340 But make sure reg crossing note doesn't already exist before
1342 if (BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
))
1344 e
->flags
|= EDGE_CROSSING
;
1345 if (JUMP_P (BB_END (e
->src
))
1346 && !CROSSING_JUMP_P (BB_END (e
->src
)))
1347 CROSSING_JUMP_P (BB_END (e
->src
)) = 1;
1349 else if (BB_PARTITION (e
->src
) == BB_PARTITION (e
->dest
))
1351 e
->flags
&= ~EDGE_CROSSING
;
1352 /* Remove the section crossing note from jump at end of
1353 src if it exists, and if no other successors are
1355 if (JUMP_P (BB_END (e
->src
)) && CROSSING_JUMP_P (BB_END (e
->src
)))
1357 bool has_crossing_succ
= false;
1360 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
1362 has_crossing_succ
|= (e2
->flags
& EDGE_CROSSING
);
1363 if (has_crossing_succ
)
1366 if (!has_crossing_succ
)
1367 CROSSING_JUMP_P (BB_END (e
->src
)) = 0;
1372 /* Called when block BB has been reassigned to the cold partition,
1373 because it is now dominated by another cold block,
1374 to ensure that the region crossing attributes are updated. */
1377 fixup_new_cold_bb (basic_block bb
)
1382 /* This is called when a hot bb is found to now be dominated
1383 by a cold bb and therefore needs to become cold. Therefore,
1384 its preds will no longer be region crossing. Any non-dominating
1385 preds that were previously hot would also have become cold
1386 in the caller for the same region. Any preds that were previously
1387 region-crossing will be adjusted in fixup_partition_crossing. */
1388 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1390 fixup_partition_crossing (e
);
1393 /* Possibly need to make bb's successor edges region crossing,
1394 or remove stale region crossing. */
1395 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1397 /* We can't have fall-through edges across partition boundaries.
1398 Note that force_nonfallthru will do any necessary partition
1399 boundary fixup by calling fixup_partition_crossing itself. */
1400 if ((e
->flags
& EDGE_FALLTHRU
)
1401 && BB_PARTITION (bb
) != BB_PARTITION (e
->dest
)
1402 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1403 force_nonfallthru (e
);
1405 fixup_partition_crossing (e
);
1409 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
1410 expense of adding new instructions or reordering basic blocks.
1412 Function can be also called with edge destination equivalent to the TARGET.
1413 Then it should try the simplifications and do nothing if none is possible.
1415 Return edge representing the branch if transformation succeeded. Return NULL
1417 We still return NULL in case E already destinated TARGET and we didn't
1418 managed to simplify instruction stream. */
1421 rtl_redirect_edge_and_branch (edge e
, basic_block target
)
1424 basic_block src
= e
->src
;
1425 basic_block dest
= e
->dest
;
1427 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
1433 if ((ret
= try_redirect_by_replacing_jump (e
, target
, false)) != NULL
)
1435 df_set_bb_dirty (src
);
1436 fixup_partition_crossing (ret
);
1440 ret
= redirect_branch_edge (e
, target
);
1444 df_set_bb_dirty (src
);
1445 fixup_partition_crossing (ret
);
1449 /* Emit a barrier after BB, into the footer if we are in CFGLAYOUT mode. */
1452 emit_barrier_after_bb (basic_block bb
)
1454 rtx_barrier
*barrier
= emit_barrier_after (BB_END (bb
));
1455 gcc_assert (current_ir_type () == IR_RTL_CFGRTL
1456 || current_ir_type () == IR_RTL_CFGLAYOUT
);
1457 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
1459 rtx_insn
*insn
= unlink_insn_chain (barrier
, barrier
);
1463 rtx_insn
*footer_tail
= BB_FOOTER (bb
);
1465 while (NEXT_INSN (footer_tail
))
1466 footer_tail
= NEXT_INSN (footer_tail
);
1467 if (!BARRIER_P (footer_tail
))
1469 SET_NEXT_INSN (footer_tail
) = insn
;
1470 SET_PREV_INSN (insn
) = footer_tail
;
1474 BB_FOOTER (bb
) = insn
;
1478 /* Like force_nonfallthru below, but additionally performs redirection
1479 Used by redirect_edge_and_branch_force. JUMP_LABEL is used only
1480 when redirecting to the EXIT_BLOCK, it is either ret_rtx or
1481 simple_return_rtx, indicating which kind of returnjump to create.
1482 It should be NULL otherwise. */
1485 force_nonfallthru_and_redirect (edge e
, basic_block target
, rtx jump_label
)
1487 basic_block jump_block
, new_bb
= NULL
, src
= e
->src
;
1490 int abnormal_edge_flags
= 0;
1491 bool asm_goto_edge
= false;
1494 /* In the case the last instruction is conditional jump to the next
1495 instruction, first redirect the jump itself and then continue
1496 by creating a basic block afterwards to redirect fallthru edge. */
1497 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1498 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1499 && any_condjump_p (BB_END (e
->src
))
1500 && JUMP_LABEL (BB_END (e
->src
)) == BB_HEAD (e
->dest
))
1503 edge b
= unchecked_make_edge (e
->src
, target
, 0);
1506 redirected
= redirect_jump (as_a
<rtx_jump_insn
*> (BB_END (e
->src
)),
1507 block_label (target
), 0);
1508 gcc_assert (redirected
);
1510 note
= find_reg_note (BB_END (e
->src
), REG_BR_PROB
, NULL_RTX
);
1513 int prob
= XINT (note
, 0);
1515 b
->probability
= prob
;
1516 /* Update this to use GCOV_COMPUTE_SCALE. */
1517 b
->count
= e
->count
* prob
/ REG_BR_PROB_BASE
;
1518 e
->probability
-= e
->probability
;
1519 e
->count
-= b
->count
;
1520 if (e
->probability
< 0)
1527 if (e
->flags
& EDGE_ABNORMAL
)
1529 /* Irritating special case - fallthru edge to the same block as abnormal
1531 We can't redirect abnormal edge, but we still can split the fallthru
1532 one and create separate abnormal edge to original destination.
1533 This allows bb-reorder to make such edge non-fallthru. */
1534 gcc_assert (e
->dest
== target
);
1535 abnormal_edge_flags
= e
->flags
& ~EDGE_FALLTHRU
;
1536 e
->flags
&= EDGE_FALLTHRU
;
1540 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
1541 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1543 /* We can't redirect the entry block. Create an empty block
1544 at the start of the function which we use to add the new
1550 basic_block bb
= create_basic_block (BB_HEAD (e
->dest
), NULL
,
1551 ENTRY_BLOCK_PTR_FOR_FN (cfun
));
1553 /* Change the existing edge's source to be the new block, and add
1554 a new edge from the entry block to the new block. */
1556 for (ei
= ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
);
1557 (tmp
= ei_safe_edge (ei
)); )
1561 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
->unordered_remove (ei
.index
);
1571 vec_safe_push (bb
->succs
, e
);
1572 make_single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
), bb
,
1577 /* If e->src ends with asm goto, see if any of the ASM_OPERANDS_LABELs
1578 don't point to the target or fallthru label. */
1579 if (JUMP_P (BB_END (e
->src
))
1580 && target
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1581 && (e
->flags
& EDGE_FALLTHRU
)
1582 && (note
= extract_asm_operands (PATTERN (BB_END (e
->src
)))))
1584 int i
, n
= ASM_OPERANDS_LABEL_LENGTH (note
);
1585 bool adjust_jump_target
= false;
1587 for (i
= 0; i
< n
; ++i
)
1589 if (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) == BB_HEAD (e
->dest
))
1591 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0))--;
1592 XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) = block_label (target
);
1593 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0))++;
1594 adjust_jump_target
= true;
1596 if (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) == BB_HEAD (target
))
1597 asm_goto_edge
= true;
1599 if (adjust_jump_target
)
1601 rtx_insn
*insn
= BB_END (e
->src
);
1603 rtx_insn
*old_label
= BB_HEAD (e
->dest
);
1604 rtx_insn
*new_label
= BB_HEAD (target
);
1606 if (JUMP_LABEL (insn
) == old_label
)
1608 JUMP_LABEL (insn
) = new_label
;
1609 note
= find_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1611 remove_note (insn
, note
);
1615 note
= find_reg_note (insn
, REG_LABEL_TARGET
, old_label
);
1617 remove_note (insn
, note
);
1618 if (JUMP_LABEL (insn
) != new_label
1619 && !find_reg_note (insn
, REG_LABEL_TARGET
, new_label
))
1620 add_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1622 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, old_label
))
1624 XEXP (note
, 0) = new_label
;
1628 if (EDGE_COUNT (e
->src
->succs
) >= 2 || abnormal_edge_flags
|| asm_goto_edge
)
1631 gcov_type count
= e
->count
;
1632 int probability
= e
->probability
;
1633 /* Create the new structures. */
1635 /* If the old block ended with a tablejump, skip its table
1636 by searching forward from there. Otherwise start searching
1637 forward from the last instruction of the old block. */
1638 rtx_jump_table_data
*table
;
1639 if (tablejump_p (BB_END (e
->src
), NULL
, &table
))
1642 new_head
= BB_END (e
->src
);
1643 new_head
= NEXT_INSN (new_head
);
1645 jump_block
= create_basic_block (new_head
, NULL
, e
->src
);
1646 jump_block
->count
= count
;
1647 jump_block
->frequency
= EDGE_FREQUENCY (e
);
1649 /* Make sure new block ends up in correct hot/cold section. */
1651 BB_COPY_PARTITION (jump_block
, e
->src
);
1654 new_edge
= make_edge (e
->src
, jump_block
, EDGE_FALLTHRU
);
1655 new_edge
->probability
= probability
;
1656 new_edge
->count
= count
;
1658 /* Redirect old edge. */
1659 redirect_edge_pred (e
, jump_block
);
1660 e
->probability
= REG_BR_PROB_BASE
;
1662 /* If e->src was previously region crossing, it no longer is
1663 and the reg crossing note should be removed. */
1664 fixup_partition_crossing (new_edge
);
1666 /* If asm goto has any label refs to target's label,
1667 add also edge from asm goto bb to target. */
1670 new_edge
->probability
/= 2;
1671 new_edge
->count
/= 2;
1672 jump_block
->count
/= 2;
1673 jump_block
->frequency
/= 2;
1674 new_edge
= make_edge (new_edge
->src
, target
,
1675 e
->flags
& ~EDGE_FALLTHRU
);
1676 new_edge
->probability
= probability
- probability
/ 2;
1677 new_edge
->count
= count
- count
/ 2;
1680 new_bb
= jump_block
;
1683 jump_block
= e
->src
;
1685 loc
= e
->goto_locus
;
1686 e
->flags
&= ~EDGE_FALLTHRU
;
1687 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1689 if (jump_label
== ret_rtx
)
1690 emit_jump_insn_after_setloc (targetm
.gen_return (),
1691 BB_END (jump_block
), loc
);
1694 gcc_assert (jump_label
== simple_return_rtx
);
1695 emit_jump_insn_after_setloc (targetm
.gen_simple_return (),
1696 BB_END (jump_block
), loc
);
1698 set_return_jump_label (BB_END (jump_block
));
1702 rtx_code_label
*label
= block_label (target
);
1703 emit_jump_insn_after_setloc (targetm
.gen_jump (label
),
1704 BB_END (jump_block
), loc
);
1705 JUMP_LABEL (BB_END (jump_block
)) = label
;
1706 LABEL_NUSES (label
)++;
1709 /* We might be in cfg layout mode, and if so, the following routine will
1710 insert the barrier correctly. */
1711 emit_barrier_after_bb (jump_block
);
1712 redirect_edge_succ_nodup (e
, target
);
1714 if (abnormal_edge_flags
)
1715 make_edge (src
, target
, abnormal_edge_flags
);
1717 df_mark_solutions_dirty ();
1718 fixup_partition_crossing (e
);
1722 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1723 (and possibly create new basic block) to make edge non-fallthru.
1724 Return newly created BB or NULL if none. */
1727 rtl_force_nonfallthru (edge e
)
1729 return force_nonfallthru_and_redirect (e
, e
->dest
, NULL_RTX
);
1732 /* Redirect edge even at the expense of creating new jump insn or
1733 basic block. Return new basic block if created, NULL otherwise.
1734 Conversion must be possible. */
1737 rtl_redirect_edge_and_branch_force (edge e
, basic_block target
)
1739 if (redirect_edge_and_branch (e
, target
)
1740 || e
->dest
== target
)
1743 /* In case the edge redirection failed, try to force it to be non-fallthru
1744 and redirect newly created simplejump. */
1745 df_set_bb_dirty (e
->src
);
1746 return force_nonfallthru_and_redirect (e
, target
, NULL_RTX
);
1749 /* The given edge should potentially be a fallthru edge. If that is in
1750 fact true, delete the jump and barriers that are in the way. */
1753 rtl_tidy_fallthru_edge (edge e
)
1756 basic_block b
= e
->src
, c
= b
->next_bb
;
1758 /* ??? In a late-running flow pass, other folks may have deleted basic
1759 blocks by nopping out blocks, leaving multiple BARRIERs between here
1760 and the target label. They ought to be chastised and fixed.
1762 We can also wind up with a sequence of undeletable labels between
1763 one block and the next.
1765 So search through a sequence of barriers, labels, and notes for
1766 the head of block C and assert that we really do fall through. */
1768 for (q
= NEXT_INSN (BB_END (b
)); q
!= BB_HEAD (c
); q
= NEXT_INSN (q
))
1772 /* Remove what will soon cease being the jump insn from the source block.
1773 If block B consisted only of this single jump, turn it into a deleted
1778 && (any_uncondjump_p (q
)
1779 || single_succ_p (b
)))
1782 rtx_jump_table_data
*table
;
1784 if (tablejump_p (q
, &label
, &table
))
1786 /* The label is likely mentioned in some instruction before
1787 the tablejump and might not be DCEd, so turn it into
1788 a note instead and move before the tablejump that is going to
1790 const char *name
= LABEL_NAME (label
);
1791 PUT_CODE (label
, NOTE
);
1792 NOTE_KIND (label
) = NOTE_INSN_DELETED_LABEL
;
1793 NOTE_DELETED_LABEL_NAME (label
) = name
;
1794 rtx_insn
*lab
= safe_as_a
<rtx_insn
*> (label
);
1795 reorder_insns (lab
, lab
, PREV_INSN (q
));
1796 delete_insn (table
);
1799 /* If this was a conditional jump, we need to also delete
1800 the insn that set cc0. */
1801 if (HAVE_cc0
&& any_condjump_p (q
) && only_sets_cc0_p (PREV_INSN (q
)))
1807 /* Selectively unlink the sequence. */
1808 if (q
!= PREV_INSN (BB_HEAD (c
)))
1809 delete_insn_chain (NEXT_INSN (q
), PREV_INSN (BB_HEAD (c
)), false);
1811 e
->flags
|= EDGE_FALLTHRU
;
1814 /* Should move basic block BB after basic block AFTER. NIY. */
1817 rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED
,
1818 basic_block after ATTRIBUTE_UNUSED
)
1823 /* Locate the last bb in the same partition as START_BB. */
1826 last_bb_in_partition (basic_block start_bb
)
1829 FOR_BB_BETWEEN (bb
, start_bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
1831 if (BB_PARTITION (start_bb
) != BB_PARTITION (bb
->next_bb
))
1834 /* Return bb before the exit block. */
1838 /* Split a (typically critical) edge. Return the new block.
1839 The edge must not be abnormal.
1841 ??? The code generally expects to be called on critical edges.
1842 The case of a block ending in an unconditional jump to a
1843 block with multiple predecessors is not handled optimally. */
1846 rtl_split_edge (edge edge_in
)
1848 basic_block bb
, new_bb
;
1851 /* Abnormal edges cannot be split. */
1852 gcc_assert (!(edge_in
->flags
& EDGE_ABNORMAL
));
1854 /* We are going to place the new block in front of edge destination.
1855 Avoid existence of fallthru predecessors. */
1856 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1858 edge e
= find_fallthru_edge (edge_in
->dest
->preds
);
1861 force_nonfallthru (e
);
1864 /* Create the basic block note. */
1865 if (edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1866 before
= BB_HEAD (edge_in
->dest
);
1870 /* If this is a fall through edge to the exit block, the blocks might be
1871 not adjacent, and the right place is after the source. */
1872 if ((edge_in
->flags
& EDGE_FALLTHRU
)
1873 && edge_in
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1875 before
= NEXT_INSN (BB_END (edge_in
->src
));
1876 bb
= create_basic_block (before
, NULL
, edge_in
->src
);
1877 BB_COPY_PARTITION (bb
, edge_in
->src
);
1881 if (edge_in
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1883 bb
= create_basic_block (before
, NULL
, edge_in
->dest
->prev_bb
);
1884 BB_COPY_PARTITION (bb
, edge_in
->dest
);
1888 basic_block after
= edge_in
->dest
->prev_bb
;
1889 /* If this is post-bb reordering, and the edge crosses a partition
1890 boundary, the new block needs to be inserted in the bb chain
1891 at the end of the src partition (since we put the new bb into
1892 that partition, see below). Otherwise we may end up creating
1893 an extra partition crossing in the chain, which is illegal.
1894 It can't go after the src, because src may have a fall-through
1895 to a different block. */
1896 if (crtl
->bb_reorder_complete
1897 && (edge_in
->flags
& EDGE_CROSSING
))
1899 after
= last_bb_in_partition (edge_in
->src
);
1900 before
= get_last_bb_insn (after
);
1901 /* The instruction following the last bb in partition should
1902 be a barrier, since it cannot end in a fall-through. */
1903 gcc_checking_assert (BARRIER_P (before
));
1904 before
= NEXT_INSN (before
);
1906 bb
= create_basic_block (before
, NULL
, after
);
1907 /* Put the split bb into the src partition, to avoid creating
1908 a situation where a cold bb dominates a hot bb, in the case
1909 where src is cold and dest is hot. The src will dominate
1910 the new bb (whereas it might not have dominated dest). */
1911 BB_COPY_PARTITION (bb
, edge_in
->src
);
1915 make_single_succ_edge (bb
, edge_in
->dest
, EDGE_FALLTHRU
);
1917 /* Can't allow a region crossing edge to be fallthrough. */
1918 if (BB_PARTITION (bb
) != BB_PARTITION (edge_in
->dest
)
1919 && edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1921 new_bb
= force_nonfallthru (single_succ_edge (bb
));
1922 gcc_assert (!new_bb
);
1925 /* For non-fallthru edges, we must adjust the predecessor's
1926 jump instruction to target our new block. */
1927 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1929 edge redirected
= redirect_edge_and_branch (edge_in
, bb
);
1930 gcc_assert (redirected
);
1934 if (edge_in
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1936 /* For asm goto even splitting of fallthru edge might
1937 need insn patching, as other labels might point to the
1939 rtx_insn
*last
= BB_END (edge_in
->src
);
1942 && edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1943 && extract_asm_operands (PATTERN (last
)) != NULL_RTX
1944 && patch_jump_insn (last
, before
, bb
))
1945 df_set_bb_dirty (edge_in
->src
);
1947 redirect_edge_succ (edge_in
, bb
);
1953 /* Queue instructions for insertion on an edge between two basic blocks.
1954 The new instructions and basic blocks (if any) will not appear in the
1955 CFG until commit_edge_insertions is called. */
1958 insert_insn_on_edge (rtx pattern
, edge e
)
1960 /* We cannot insert instructions on an abnormal critical edge.
1961 It will be easier to find the culprit if we die now. */
1962 gcc_assert (!((e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
)));
1964 if (e
->insns
.r
== NULL_RTX
)
1967 push_to_sequence (e
->insns
.r
);
1969 emit_insn (pattern
);
1971 e
->insns
.r
= get_insns ();
1975 /* Update the CFG for the instructions queued on edge E. */
1978 commit_one_edge_insertion (edge e
)
1980 rtx_insn
*before
= NULL
, *after
= NULL
, *insns
, *tmp
, *last
;
1983 /* Pull the insns off the edge now since the edge might go away. */
1987 /* Figure out where to put these insns. If the destination has
1988 one predecessor, insert there. Except for the exit block. */
1989 if (single_pred_p (e
->dest
) && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1993 /* Get the location correct wrt a code label, and "nice" wrt
1994 a basic block note, and before everything else. */
1997 tmp
= NEXT_INSN (tmp
);
1998 if (NOTE_INSN_BASIC_BLOCK_P (tmp
))
1999 tmp
= NEXT_INSN (tmp
);
2000 if (tmp
== BB_HEAD (bb
))
2003 after
= PREV_INSN (tmp
);
2005 after
= get_last_insn ();
2008 /* If the source has one successor and the edge is not abnormal,
2009 insert there. Except for the entry block.
2010 Don't do this if the predecessor ends in a jump other than
2011 unconditional simple jump. E.g. for asm goto that points all
2012 its labels at the fallthru basic block, we can't insert instructions
2013 before the asm goto, as the asm goto can have various of side effects,
2014 and can't emit instructions after the asm goto, as it must end
2016 else if ((e
->flags
& EDGE_ABNORMAL
) == 0
2017 && single_succ_p (e
->src
)
2018 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2019 && (!JUMP_P (BB_END (e
->src
))
2020 || simplejump_p (BB_END (e
->src
))))
2024 /* It is possible to have a non-simple jump here. Consider a target
2025 where some forms of unconditional jumps clobber a register. This
2026 happens on the fr30 for example.
2028 We know this block has a single successor, so we can just emit
2029 the queued insns before the jump. */
2030 if (JUMP_P (BB_END (bb
)))
2031 before
= BB_END (bb
);
2034 /* We'd better be fallthru, or we've lost track of what's what. */
2035 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
2037 after
= BB_END (bb
);
2041 /* Otherwise we must split the edge. */
2044 bb
= split_edge (e
);
2046 /* If E crossed a partition boundary, we needed to make bb end in
2047 a region-crossing jump, even though it was originally fallthru. */
2048 if (JUMP_P (BB_END (bb
)))
2049 before
= BB_END (bb
);
2051 after
= BB_END (bb
);
2054 /* Now that we've found the spot, do the insertion. */
2057 emit_insn_before_noloc (insns
, before
, bb
);
2058 last
= prev_nonnote_insn (before
);
2061 last
= emit_insn_after_noloc (insns
, after
, bb
);
2063 if (returnjump_p (last
))
2065 /* ??? Remove all outgoing edges from BB and add one for EXIT.
2066 This is not currently a problem because this only happens
2067 for the (single) epilogue, which already has a fallthru edge
2070 e
= single_succ_edge (bb
);
2071 gcc_assert (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
2072 && single_succ_p (bb
) && (e
->flags
& EDGE_FALLTHRU
));
2074 e
->flags
&= ~EDGE_FALLTHRU
;
2075 emit_barrier_after (last
);
2078 delete_insn (before
);
2081 gcc_assert (!JUMP_P (last
));
2084 /* Update the CFG for all queued instructions. */
2087 commit_edge_insertions (void)
2091 /* Optimization passes that invoke this routine can cause hot blocks
2092 previously reached by both hot and cold blocks to become dominated only
2093 by cold blocks. This will cause the verification below to fail,
2094 and lead to now cold code in the hot section. In some cases this
2095 may only be visible after newly unreachable blocks are deleted,
2096 which will be done by fixup_partitions. */
2097 fixup_partitions ();
2099 checking_verify_flow_info ();
2101 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
2102 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
2107 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2109 commit_one_edge_insertion (e
);
2114 /* Print out RTL-specific basic block information (live information
2115 at start and end with TDF_DETAILS). FLAGS are the TDF_* masks
2116 documented in dumpfile.h. */
2119 rtl_dump_bb (FILE *outf
, basic_block bb
, int indent
, int flags
)
2125 s_indent
= (char *) alloca ((size_t) indent
+ 1);
2126 memset (s_indent
, ' ', (size_t) indent
);
2127 s_indent
[indent
] = '\0';
2129 if (df
&& (flags
& TDF_DETAILS
))
2131 df_dump_top (bb
, outf
);
2135 if (bb
->index
!= ENTRY_BLOCK
&& bb
->index
!= EXIT_BLOCK
)
2136 for (insn
= BB_HEAD (bb
), last
= NEXT_INSN (BB_END (bb
)); insn
!= last
;
2137 insn
= NEXT_INSN (insn
))
2139 if (flags
& TDF_DETAILS
)
2140 df_dump_insn_top (insn
, outf
);
2141 if (! (flags
& TDF_SLIM
))
2142 print_rtl_single (outf
, insn
);
2144 dump_insn_slim (outf
, insn
);
2145 if (flags
& TDF_DETAILS
)
2146 df_dump_insn_bottom (insn
, outf
);
2149 if (df
&& (flags
& TDF_DETAILS
))
2151 df_dump_bottom (bb
, outf
);
2157 /* Like dump_function_to_file, but for RTL. Print out dataflow information
2158 for the start of each basic block. FLAGS are the TDF_* masks documented
2162 print_rtl_with_bb (FILE *outf
, const rtx_insn
*rtx_first
, int flags
)
2164 const rtx_insn
*tmp_rtx
;
2166 fprintf (outf
, "(nil)\n");
2169 enum bb_state
{ NOT_IN_BB
, IN_ONE_BB
, IN_MULTIPLE_BB
};
2170 int max_uid
= get_max_uid ();
2171 basic_block
*start
= XCNEWVEC (basic_block
, max_uid
);
2172 basic_block
*end
= XCNEWVEC (basic_block
, max_uid
);
2173 enum bb_state
*in_bb_p
= XCNEWVEC (enum bb_state
, max_uid
);
2176 /* After freeing the CFG, we still have BLOCK_FOR_INSN set on most
2177 insns, but the CFG is not maintained so the basic block info
2178 is not reliable. Therefore it's omitted from the dumps. */
2179 if (! (cfun
->curr_properties
& PROP_cfg
))
2180 flags
&= ~TDF_BLOCKS
;
2183 df_dump_start (outf
);
2185 if (flags
& TDF_BLOCKS
)
2187 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2191 start
[INSN_UID (BB_HEAD (bb
))] = bb
;
2192 end
[INSN_UID (BB_END (bb
))] = bb
;
2193 for (x
= BB_HEAD (bb
); x
!= NULL_RTX
; x
= NEXT_INSN (x
))
2195 enum bb_state state
= IN_MULTIPLE_BB
;
2197 if (in_bb_p
[INSN_UID (x
)] == NOT_IN_BB
)
2199 in_bb_p
[INSN_UID (x
)] = state
;
2201 if (x
== BB_END (bb
))
2207 for (tmp_rtx
= rtx_first
; NULL
!= tmp_rtx
; tmp_rtx
= NEXT_INSN (tmp_rtx
))
2209 if (flags
& TDF_BLOCKS
)
2211 bb
= start
[INSN_UID (tmp_rtx
)];
2214 dump_bb_info (outf
, bb
, 0, dump_flags
| TDF_COMMENT
, true, false);
2215 if (df
&& (flags
& TDF_DETAILS
))
2216 df_dump_top (bb
, outf
);
2219 if (in_bb_p
[INSN_UID (tmp_rtx
)] == NOT_IN_BB
2220 && !NOTE_P (tmp_rtx
)
2221 && !BARRIER_P (tmp_rtx
))
2222 fprintf (outf
, ";; Insn is not within a basic block\n");
2223 else if (in_bb_p
[INSN_UID (tmp_rtx
)] == IN_MULTIPLE_BB
)
2224 fprintf (outf
, ";; Insn is in multiple basic blocks\n");
2227 if (flags
& TDF_DETAILS
)
2228 df_dump_insn_top (tmp_rtx
, outf
);
2229 if (! (flags
& TDF_SLIM
))
2230 print_rtl_single (outf
, tmp_rtx
);
2232 dump_insn_slim (outf
, tmp_rtx
);
2233 if (flags
& TDF_DETAILS
)
2234 df_dump_insn_bottom (tmp_rtx
, outf
);
2236 if (flags
& TDF_BLOCKS
)
2238 bb
= end
[INSN_UID (tmp_rtx
)];
2241 dump_bb_info (outf
, bb
, 0, dump_flags
| TDF_COMMENT
, false, true);
2242 if (df
&& (flags
& TDF_DETAILS
))
2243 df_dump_bottom (bb
, outf
);
2255 /* Update the branch probability of BB if a REG_BR_PROB is present. */
2258 update_br_prob_note (basic_block bb
)
2261 if (!JUMP_P (BB_END (bb
)))
2263 note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
);
2264 if (!note
|| XINT (note
, 0) == BRANCH_EDGE (bb
)->probability
)
2266 XINT (note
, 0) = BRANCH_EDGE (bb
)->probability
;
2269 /* Get the last insn associated with block BB (that includes barriers and
2270 tablejumps after BB). */
2272 get_last_bb_insn (basic_block bb
)
2274 rtx_jump_table_data
*table
;
2276 rtx_insn
*end
= BB_END (bb
);
2278 /* Include any jump table following the basic block. */
2279 if (tablejump_p (end
, NULL
, &table
))
2282 /* Include any barriers that may follow the basic block. */
2283 tmp
= next_nonnote_insn_bb (end
);
2284 while (tmp
&& BARRIER_P (tmp
))
2287 tmp
= next_nonnote_insn_bb (end
);
2293 /* Sanity check partition hotness to ensure that basic blocks in
2294 Â the cold partition don't dominate basic blocks in the hot partition.
2295 If FLAG_ONLY is true, report violations as errors. Otherwise
2296 re-mark the dominated blocks as cold, since this is run after
2297 cfg optimizations that may make hot blocks previously reached
2298 by both hot and cold blocks now only reachable along cold paths. */
2300 static vec
<basic_block
>
2301 find_partition_fixes (bool flag_only
)
2304 vec
<basic_block
> bbs_in_cold_partition
= vNULL
;
2305 vec
<basic_block
> bbs_to_fix
= vNULL
;
2307 /* Callers check this. */
2308 gcc_checking_assert (crtl
->has_bb_partition
);
2310 FOR_EACH_BB_FN (bb
, cfun
)
2311 if ((BB_PARTITION (bb
) == BB_COLD_PARTITION
))
2312 bbs_in_cold_partition
.safe_push (bb
);
2314 if (bbs_in_cold_partition
.is_empty ())
2317 bool dom_calculated_here
= !dom_info_available_p (CDI_DOMINATORS
);
2319 if (dom_calculated_here
)
2320 calculate_dominance_info (CDI_DOMINATORS
);
2322 while (! bbs_in_cold_partition
.is_empty ())
2324 bb
= bbs_in_cold_partition
.pop ();
2325 /* Any blocks dominated by a block in the cold section
2326 must also be cold. */
2328 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
2330 son
= next_dom_son (CDI_DOMINATORS
, son
))
2332 /* If son is not yet cold, then mark it cold here and
2333 enqueue it for further processing. */
2334 if ((BB_PARTITION (son
) != BB_COLD_PARTITION
))
2337 error ("non-cold basic block %d dominated "
2338 "by a block in the cold partition (%d)", son
->index
, bb
->index
);
2340 BB_SET_PARTITION (son
, BB_COLD_PARTITION
);
2341 bbs_to_fix
.safe_push (son
);
2342 bbs_in_cold_partition
.safe_push (son
);
2347 if (dom_calculated_here
)
2348 free_dominance_info (CDI_DOMINATORS
);
2353 /* Perform cleanup on the hot/cold bb partitioning after optimization
2354 passes that modify the cfg. */
2357 fixup_partitions (void)
2361 if (!crtl
->has_bb_partition
)
2364 /* Delete any blocks that became unreachable and weren't
2365 already cleaned up, for example during edge forwarding
2366 and convert_jumps_to_returns. This will expose more
2367 opportunities for fixing the partition boundaries here.
2368 Also, the calculation of the dominance graph during verification
2369 will assert if there are unreachable nodes. */
2370 delete_unreachable_blocks ();
2372 /* If there are partitions, do a sanity check on them: A basic block in
2373 Â a cold partition cannot dominate a basic block in a hot partition.
2374 Fixup any that now violate this requirement, as a result of edge
2375 forwarding and unreachable block deletion. Â */
2376 vec
<basic_block
> bbs_to_fix
= find_partition_fixes (false);
2378 /* Do the partition fixup after all necessary blocks have been converted to
2379 cold, so that we only update the region crossings the minimum number of
2380 places, which can require forcing edges to be non fallthru. */
2381 while (! bbs_to_fix
.is_empty ())
2383 bb
= bbs_to_fix
.pop ();
2384 fixup_new_cold_bb (bb
);
2388 /* Verify, in the basic block chain, that there is at most one switch
2389 between hot/cold partitions. This condition will not be true until
2390 after reorder_basic_blocks is called. */
2393 verify_hot_cold_block_grouping (void)
2397 bool switched_sections
= false;
2398 int current_partition
= BB_UNPARTITIONED
;
2400 /* Even after bb reordering is complete, we go into cfglayout mode
2401 again (in compgoto). Ensure we don't call this before going back
2402 into linearized RTL when any layout fixes would have been committed. */
2403 if (!crtl
->bb_reorder_complete
2404 || current_ir_type () != IR_RTL_CFGRTL
)
2407 FOR_EACH_BB_FN (bb
, cfun
)
2409 if (current_partition
!= BB_UNPARTITIONED
2410 && BB_PARTITION (bb
) != current_partition
)
2412 if (switched_sections
)
2414 error ("multiple hot/cold transitions found (bb %i)",
2419 switched_sections
= true;
2421 if (!crtl
->has_bb_partition
)
2422 error ("partition found but function partition flag not set");
2424 current_partition
= BB_PARTITION (bb
);
2431 /* Perform several checks on the edges out of each block, such as
2432 the consistency of the branch probabilities, the correctness
2433 of hot/cold partition crossing edges, and the number of expected
2434 successor edges. Also verify that the dominance relationship
2435 between hot/cold blocks is sane. */
2438 rtl_verify_edges (void)
2443 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2445 int n_fallthru
= 0, n_branch
= 0, n_abnormal_call
= 0, n_sibcall
= 0;
2446 int n_eh
= 0, n_abnormal
= 0;
2447 edge e
, fallthru
= NULL
;
2450 bool has_crossing_edge
= false;
2452 if (JUMP_P (BB_END (bb
))
2453 && (note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
))
2454 && EDGE_COUNT (bb
->succs
) >= 2
2455 && any_condjump_p (BB_END (bb
)))
2457 if (XINT (note
, 0) != BRANCH_EDGE (bb
)->probability
2458 && profile_status_for_fn (cfun
) != PROFILE_ABSENT
)
2460 error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i",
2461 XINT (note
, 0), BRANCH_EDGE (bb
)->probability
);
2466 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2470 if (e
->flags
& EDGE_FALLTHRU
)
2471 n_fallthru
++, fallthru
= e
;
2473 is_crossing
= (BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
)
2474 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2475 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
2476 has_crossing_edge
|= is_crossing
;
2477 if (e
->flags
& EDGE_CROSSING
)
2481 error ("EDGE_CROSSING incorrectly set across same section");
2484 if (e
->flags
& EDGE_FALLTHRU
)
2486 error ("fallthru edge crosses section boundary in bb %i",
2490 if (e
->flags
& EDGE_EH
)
2492 error ("EH edge crosses section boundary in bb %i",
2496 if (JUMP_P (BB_END (bb
)) && !CROSSING_JUMP_P (BB_END (bb
)))
2498 error ("No region crossing jump at section boundary in bb %i",
2503 else if (is_crossing
)
2505 error ("EDGE_CROSSING missing across section boundary");
2509 if ((e
->flags
& ~(EDGE_DFS_BACK
2511 | EDGE_IRREDUCIBLE_LOOP
2514 | EDGE_PRESERVE
)) == 0)
2517 if (e
->flags
& EDGE_ABNORMAL_CALL
)
2520 if (e
->flags
& EDGE_SIBCALL
)
2523 if (e
->flags
& EDGE_EH
)
2526 if (e
->flags
& EDGE_ABNORMAL
)
2530 if (!has_crossing_edge
2531 && JUMP_P (BB_END (bb
))
2532 && CROSSING_JUMP_P (BB_END (bb
)))
2534 print_rtl_with_bb (stderr
, get_insns (), TDF_RTL
| TDF_BLOCKS
| TDF_DETAILS
);
2535 error ("Region crossing jump across same section in bb %i",
2540 if (n_eh
&& !find_reg_note (BB_END (bb
), REG_EH_REGION
, NULL_RTX
))
2542 error ("missing REG_EH_REGION note at the end of bb %i", bb
->index
);
2547 error ("too many exception handling edges in bb %i", bb
->index
);
2551 && (!JUMP_P (BB_END (bb
))
2552 || (n_branch
> 1 && (any_uncondjump_p (BB_END (bb
))
2553 || any_condjump_p (BB_END (bb
))))))
2555 error ("too many outgoing branch edges from bb %i", bb
->index
);
2558 if (n_fallthru
&& any_uncondjump_p (BB_END (bb
)))
2560 error ("fallthru edge after unconditional jump in bb %i", bb
->index
);
2563 if (n_branch
!= 1 && any_uncondjump_p (BB_END (bb
)))
2565 error ("wrong number of branch edges after unconditional jump"
2566 " in bb %i", bb
->index
);
2569 if (n_branch
!= 1 && any_condjump_p (BB_END (bb
))
2570 && JUMP_LABEL (BB_END (bb
)) != BB_HEAD (fallthru
->dest
))
2572 error ("wrong amount of branch edges after conditional jump"
2573 " in bb %i", bb
->index
);
2576 if (n_abnormal_call
&& !CALL_P (BB_END (bb
)))
2578 error ("abnormal call edges for non-call insn in bb %i", bb
->index
);
2581 if (n_sibcall
&& !CALL_P (BB_END (bb
)))
2583 error ("sibcall edges for non-call insn in bb %i", bb
->index
);
2586 if (n_abnormal
> n_eh
2587 && !(CALL_P (BB_END (bb
))
2588 && n_abnormal
== n_abnormal_call
+ n_sibcall
)
2589 && (!JUMP_P (BB_END (bb
))
2590 || any_condjump_p (BB_END (bb
))
2591 || any_uncondjump_p (BB_END (bb
))))
2593 error ("abnormal edges for no purpose in bb %i", bb
->index
);
2598 /* If there are partitions, do a sanity check on them: A basic block in
2599 Â a cold partition cannot dominate a basic block in a hot partition. Â */
2600 if (crtl
->has_bb_partition
&& !err
)
2602 vec
<basic_block
> bbs_to_fix
= find_partition_fixes (true);
2603 err
= !bbs_to_fix
.is_empty ();
2610 /* Checks on the instructions within blocks. Currently checks that each
2611 block starts with a basic block note, and that basic block notes and
2612 control flow jumps are not found in the middle of the block. */
2615 rtl_verify_bb_insns (void)
2621 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2623 /* Now check the header of basic
2624 block. It ought to contain optional CODE_LABEL followed
2625 by NOTE_BASIC_BLOCK. */
2629 if (BB_END (bb
) == x
)
2631 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2639 if (!NOTE_INSN_BASIC_BLOCK_P (x
) || NOTE_BASIC_BLOCK (x
) != bb
)
2641 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2646 if (BB_END (bb
) == x
)
2647 /* Do checks for empty blocks here. */
2650 for (x
= NEXT_INSN (x
); x
; x
= NEXT_INSN (x
))
2652 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2654 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
2655 INSN_UID (x
), bb
->index
);
2659 if (x
== BB_END (bb
))
2662 if (control_flow_insn_p (x
))
2664 error ("in basic block %d:", bb
->index
);
2665 fatal_insn ("flow control insn inside a basic block", x
);
2674 /* Verify that block pointers for instructions in basic blocks, headers and
2675 footers are set appropriately. */
2678 rtl_verify_bb_pointers (void)
2683 /* Check the general integrity of the basic blocks. */
2684 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2688 if (!(bb
->flags
& BB_RTL
))
2690 error ("BB_RTL flag not set for block %d", bb
->index
);
2694 FOR_BB_INSNS (bb
, insn
)
2695 if (BLOCK_FOR_INSN (insn
) != bb
)
2697 error ("insn %d basic block pointer is %d, should be %d",
2699 BLOCK_FOR_INSN (insn
) ? BLOCK_FOR_INSN (insn
)->index
: 0,
2704 for (insn
= BB_HEADER (bb
); insn
; insn
= NEXT_INSN (insn
))
2705 if (!BARRIER_P (insn
)
2706 && BLOCK_FOR_INSN (insn
) != NULL
)
2708 error ("insn %d in header of bb %d has non-NULL basic block",
2709 INSN_UID (insn
), bb
->index
);
2712 for (insn
= BB_FOOTER (bb
); insn
; insn
= NEXT_INSN (insn
))
2713 if (!BARRIER_P (insn
)
2714 && BLOCK_FOR_INSN (insn
) != NULL
)
2716 error ("insn %d in footer of bb %d has non-NULL basic block",
2717 INSN_UID (insn
), bb
->index
);
2726 /* Verify the CFG and RTL consistency common for both underlying RTL and
2729 Currently it does following checks:
2731 - overlapping of basic blocks
2732 - insns with wrong BLOCK_FOR_INSN pointers
2733 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
2734 - tails of basic blocks (ensure that boundary is necessary)
2735 - scans body of the basic block for JUMP_INSN, CODE_LABEL
2736 and NOTE_INSN_BASIC_BLOCK
2737 - verify that no fall_thru edge crosses hot/cold partition boundaries
2738 - verify that there are no pending RTL branch predictions
2739 - verify that hot blocks are not dominated by cold blocks
2741 In future it can be extended check a lot of other stuff as well
2742 (reachability of basic blocks, life information, etc. etc.). */
2745 rtl_verify_flow_info_1 (void)
2749 err
|= rtl_verify_bb_pointers ();
2751 err
|= rtl_verify_bb_insns ();
2753 err
|= rtl_verify_edges ();
2758 /* Walk the instruction chain and verify that bb head/end pointers
2759 are correct, and that instructions are in exactly one bb and have
2760 correct block pointers. */
2763 rtl_verify_bb_insn_chain (void)
2768 rtx_insn
*last_head
= get_last_insn ();
2769 basic_block
*bb_info
;
2770 const int max_uid
= get_max_uid ();
2772 bb_info
= XCNEWVEC (basic_block
, max_uid
);
2774 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2776 rtx_insn
*head
= BB_HEAD (bb
);
2777 rtx_insn
*end
= BB_END (bb
);
2779 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2781 /* Verify the end of the basic block is in the INSN chain. */
2785 /* And that the code outside of basic blocks has NULL bb field. */
2787 && BLOCK_FOR_INSN (x
) != NULL
)
2789 error ("insn %d outside of basic blocks has non-NULL bb field",
2797 error ("end insn %d for block %d not found in the insn stream",
2798 INSN_UID (end
), bb
->index
);
2802 /* Work backwards from the end to the head of the basic block
2803 to verify the head is in the RTL chain. */
2804 for (; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2806 /* While walking over the insn chain, verify insns appear
2807 in only one basic block. */
2808 if (bb_info
[INSN_UID (x
)] != NULL
)
2810 error ("insn %d is in multiple basic blocks (%d and %d)",
2811 INSN_UID (x
), bb
->index
, bb_info
[INSN_UID (x
)]->index
);
2815 bb_info
[INSN_UID (x
)] = bb
;
2822 error ("head insn %d for block %d not found in the insn stream",
2823 INSN_UID (head
), bb
->index
);
2827 last_head
= PREV_INSN (x
);
2830 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2832 /* Check that the code before the first basic block has NULL
2835 && BLOCK_FOR_INSN (x
) != NULL
)
2837 error ("insn %d outside of basic blocks has non-NULL bb field",
2847 /* Verify that fallthru edges point to adjacent blocks in layout order and
2848 that barriers exist after non-fallthru blocks. */
2851 rtl_verify_fallthru (void)
2856 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2860 e
= find_fallthru_edge (bb
->succs
);
2865 /* Ensure existence of barrier in BB with no fallthru edges. */
2866 for (insn
= NEXT_INSN (BB_END (bb
)); ; insn
= NEXT_INSN (insn
))
2868 if (!insn
|| NOTE_INSN_BASIC_BLOCK_P (insn
))
2870 error ("missing barrier after block %i", bb
->index
);
2874 if (BARRIER_P (insn
))
2878 else if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2879 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
2883 if (e
->src
->next_bb
!= e
->dest
)
2886 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
2887 e
->src
->index
, e
->dest
->index
);
2891 for (insn
= NEXT_INSN (BB_END (e
->src
)); insn
!= BB_HEAD (e
->dest
);
2892 insn
= NEXT_INSN (insn
))
2893 if (BARRIER_P (insn
) || INSN_P (insn
))
2895 error ("verify_flow_info: Incorrect fallthru %i->%i",
2896 e
->src
->index
, e
->dest
->index
);
2897 fatal_insn ("wrong insn in the fallthru edge", insn
);
2906 /* Verify that blocks are laid out in consecutive order. While walking the
2907 instructions, verify that all expected instructions are inside the basic
2908 blocks, and that all returns are followed by barriers. */
2911 rtl_verify_bb_layout (void)
2917 rtx_insn
* const rtx_first
= get_insns ();
2918 basic_block last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
), curr_bb
= NULL
;
2921 last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
2923 for (x
= rtx_first
; x
; x
= NEXT_INSN (x
))
2925 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2927 bb
= NOTE_BASIC_BLOCK (x
);
2930 if (bb
!= last_bb_seen
->next_bb
)
2931 internal_error ("basic blocks not laid down consecutively");
2933 curr_bb
= last_bb_seen
= bb
;
2938 switch (GET_CODE (x
))
2945 /* An ADDR_VEC is placed outside any basic block. */
2947 && JUMP_TABLE_DATA_P (NEXT_INSN (x
)))
2950 /* But in any case, non-deletable labels can appear anywhere. */
2954 fatal_insn ("insn outside basic block", x
);
2959 && returnjump_p (x
) && ! condjump_p (x
)
2960 && ! (next_nonnote_insn (x
) && BARRIER_P (next_nonnote_insn (x
))))
2961 fatal_insn ("return not followed by barrier", x
);
2963 if (curr_bb
&& x
== BB_END (curr_bb
))
2967 if (num_bb_notes
!= n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
)
2969 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
2970 num_bb_notes
, n_basic_blocks_for_fn (cfun
));
2975 /* Verify the CFG and RTL consistency common for both underlying RTL and
2976 cfglayout RTL, plus consistency checks specific to linearized RTL mode.
2978 Currently it does following checks:
2979 - all checks of rtl_verify_flow_info_1
2980 - test head/end pointers
2981 - check that blocks are laid out in consecutive order
2982 - check that all insns are in the basic blocks
2983 (except the switch handling code, barriers and notes)
2984 - check that all returns are followed by barriers
2985 - check that all fallthru edge points to the adjacent blocks
2986 - verify that there is a single hot/cold partition boundary after bbro */
2989 rtl_verify_flow_info (void)
2993 err
|= rtl_verify_flow_info_1 ();
2995 err
|= rtl_verify_bb_insn_chain ();
2997 err
|= rtl_verify_fallthru ();
2999 err
|= rtl_verify_bb_layout ();
3001 err
|= verify_hot_cold_block_grouping ();
3006 /* Assume that the preceding pass has possibly eliminated jump instructions
3007 or converted the unconditional jumps. Eliminate the edges from CFG.
3008 Return true if any edges are eliminated. */
3011 purge_dead_edges (basic_block bb
)
3014 rtx_insn
*insn
= BB_END (bb
);
3016 bool purged
= false;
3020 if (DEBUG_INSN_P (insn
) && insn
!= BB_HEAD (bb
))
3022 insn
= PREV_INSN (insn
);
3023 while ((DEBUG_INSN_P (insn
) || NOTE_P (insn
)) && insn
!= BB_HEAD (bb
));
3025 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
3026 if (NONJUMP_INSN_P (insn
)
3027 && (note
= find_reg_note (insn
, REG_EH_REGION
, NULL
)))
3031 if (! may_trap_p (PATTERN (insn
))
3032 || ((eqnote
= find_reg_equal_equiv_note (insn
))
3033 && ! may_trap_p (XEXP (eqnote
, 0))))
3034 remove_note (insn
, note
);
3037 /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
3038 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3040 bool remove
= false;
3042 /* There are three types of edges we need to handle correctly here: EH
3043 edges, abnormal call EH edges, and abnormal call non-EH edges. The
3044 latter can appear when nonlocal gotos are used. */
3045 if (e
->flags
& EDGE_ABNORMAL_CALL
)
3049 else if (can_nonlocal_goto (insn
))
3051 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
3053 else if (flag_tm
&& find_reg_note (insn
, REG_TM
, NULL
))
3058 else if (e
->flags
& EDGE_EH
)
3059 remove
= !can_throw_internal (insn
);
3064 df_set_bb_dirty (bb
);
3077 /* We do care only about conditional jumps and simplejumps. */
3078 if (!any_condjump_p (insn
)
3079 && !returnjump_p (insn
)
3080 && !simplejump_p (insn
))
3083 /* Branch probability/prediction notes are defined only for
3084 condjumps. We've possibly turned condjump into simplejump. */
3085 if (simplejump_p (insn
))
3087 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
3089 remove_note (insn
, note
);
3090 while ((note
= find_reg_note (insn
, REG_BR_PRED
, NULL
)))
3091 remove_note (insn
, note
);
3094 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3096 /* Avoid abnormal flags to leak from computed jumps turned
3097 into simplejumps. */
3099 e
->flags
&= ~EDGE_ABNORMAL
;
3101 /* See if this edge is one we should keep. */
3102 if ((e
->flags
& EDGE_FALLTHRU
) && any_condjump_p (insn
))
3103 /* A conditional jump can fall through into the next
3104 block, so we should keep the edge. */
3109 else if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
3110 && BB_HEAD (e
->dest
) == JUMP_LABEL (insn
))
3111 /* If the destination block is the target of the jump,
3117 else if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
3118 && returnjump_p (insn
))
3119 /* If the destination block is the exit block, and this
3120 instruction is a return, then keep the edge. */
3125 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
3126 /* Keep the edges that correspond to exceptions thrown by
3127 this instruction and rematerialize the EDGE_ABNORMAL
3128 flag we just cleared above. */
3130 e
->flags
|= EDGE_ABNORMAL
;
3135 /* We do not need this edge. */
3136 df_set_bb_dirty (bb
);
3141 if (EDGE_COUNT (bb
->succs
) == 0 || !purged
)
3145 fprintf (dump_file
, "Purged edges from bb %i\n", bb
->index
);
3150 /* Redistribute probabilities. */
3151 if (single_succ_p (bb
))
3153 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
3154 single_succ_edge (bb
)->count
= bb
->count
;
3158 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
3162 b
= BRANCH_EDGE (bb
);
3163 f
= FALLTHRU_EDGE (bb
);
3164 b
->probability
= XINT (note
, 0);
3165 f
->probability
= REG_BR_PROB_BASE
- b
->probability
;
3166 /* Update these to use GCOV_COMPUTE_SCALE. */
3167 b
->count
= bb
->count
* b
->probability
/ REG_BR_PROB_BASE
;
3168 f
->count
= bb
->count
* f
->probability
/ REG_BR_PROB_BASE
;
3173 else if (CALL_P (insn
) && SIBLING_CALL_P (insn
))
3175 /* First, there should not be any EH or ABCALL edges resulting
3176 from non-local gotos and the like. If there were, we shouldn't
3177 have created the sibcall in the first place. Second, there
3178 should of course never have been a fallthru edge. */
3179 gcc_assert (single_succ_p (bb
));
3180 gcc_assert (single_succ_edge (bb
)->flags
3181 == (EDGE_SIBCALL
| EDGE_ABNORMAL
));
3186 /* If we don't see a jump insn, we don't know exactly why the block would
3187 have been broken at this point. Look for a simple, non-fallthru edge,
3188 as these are only created by conditional branches. If we find such an
3189 edge we know that there used to be a jump here and can then safely
3190 remove all non-fallthru edges. */
3192 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3193 if (! (e
->flags
& (EDGE_COMPLEX
| EDGE_FALLTHRU
)))
3202 /* Remove all but the fake and fallthru edges. The fake edge may be
3203 the only successor for this block in the case of noreturn
3205 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3207 if (!(e
->flags
& (EDGE_FALLTHRU
| EDGE_FAKE
)))
3209 df_set_bb_dirty (bb
);
3217 gcc_assert (single_succ_p (bb
));
3219 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
3220 single_succ_edge (bb
)->count
= bb
->count
;
3223 fprintf (dump_file
, "Purged non-fallthru edges from bb %i\n",
3228 /* Search all basic blocks for potentially dead edges and purge them. Return
3229 true if some edge has been eliminated. */
3232 purge_all_dead_edges (void)
3237 FOR_EACH_BB_FN (bb
, cfun
)
3239 bool purged_here
= purge_dead_edges (bb
);
3241 purged
|= purged_here
;
3247 /* This is used by a few passes that emit some instructions after abnormal
3248 calls, moving the basic block's end, while they in fact do want to emit
3249 them on the fallthru edge. Look for abnormal call edges, find backward
3250 the call in the block and insert the instructions on the edge instead.
3252 Similarly, handle instructions throwing exceptions internally.
3254 Return true when instructions have been found and inserted on edges. */
3257 fixup_abnormal_edges (void)
3259 bool inserted
= false;
3262 FOR_EACH_BB_FN (bb
, cfun
)
3267 /* Look for cases we are interested in - calls or instructions causing
3269 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3270 if ((e
->flags
& EDGE_ABNORMAL_CALL
)
3271 || ((e
->flags
& (EDGE_ABNORMAL
| EDGE_EH
))
3272 == (EDGE_ABNORMAL
| EDGE_EH
)))
3275 if (e
&& !CALL_P (BB_END (bb
)) && !can_throw_internal (BB_END (bb
)))
3279 /* Get past the new insns generated. Allow notes, as the insns
3280 may be already deleted. */
3282 while ((NONJUMP_INSN_P (insn
) || NOTE_P (insn
))
3283 && !can_throw_internal (insn
)
3284 && insn
!= BB_HEAD (bb
))
3285 insn
= PREV_INSN (insn
);
3287 if (CALL_P (insn
) || can_throw_internal (insn
))
3289 rtx_insn
*stop
, *next
;
3291 e
= find_fallthru_edge (bb
->succs
);
3293 stop
= NEXT_INSN (BB_END (bb
));
3296 for (insn
= NEXT_INSN (insn
); insn
!= stop
; insn
= next
)
3298 next
= NEXT_INSN (insn
);
3303 /* Sometimes there's still the return value USE.
3304 If it's placed after a trapping call (i.e. that
3305 call is the last insn anyway), we have no fallthru
3306 edge. Simply delete this use and don't try to insert
3307 on the non-existent edge. */
3308 if (GET_CODE (PATTERN (insn
)) != USE
)
3310 /* We're not deleting it, we're moving it. */
3311 insn
->set_undeleted ();
3312 SET_PREV_INSN (insn
) = NULL_RTX
;
3313 SET_NEXT_INSN (insn
) = NULL_RTX
;
3315 insert_insn_on_edge (insn
, e
);
3319 else if (!BARRIER_P (insn
))
3320 set_block_for_insn (insn
, NULL
);
3324 /* It may be that we don't find any trapping insn. In this
3325 case we discovered quite late that the insn that had been
3326 marked as can_throw_internal in fact couldn't trap at all.
3327 So we should in fact delete the EH edges out of the block. */
3329 purge_dead_edges (bb
);
3336 /* Cut the insns from FIRST to LAST out of the insns stream. */
3339 unlink_insn_chain (rtx_insn
*first
, rtx_insn
*last
)
3341 rtx_insn
*prevfirst
= PREV_INSN (first
);
3342 rtx_insn
*nextlast
= NEXT_INSN (last
);
3344 SET_PREV_INSN (first
) = NULL
;
3345 SET_NEXT_INSN (last
) = NULL
;
3347 SET_NEXT_INSN (prevfirst
) = nextlast
;
3349 SET_PREV_INSN (nextlast
) = prevfirst
;
3351 set_last_insn (prevfirst
);
3353 set_first_insn (nextlast
);
3357 /* Skip over inter-block insns occurring after BB which are typically
3358 associated with BB (e.g., barriers). If there are any such insns,
3359 we return the last one. Otherwise, we return the end of BB. */
3362 skip_insns_after_block (basic_block bb
)
3364 rtx_insn
*insn
, *last_insn
, *next_head
, *prev
;
3367 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3368 next_head
= BB_HEAD (bb
->next_bb
);
3370 for (last_insn
= insn
= BB_END (bb
); (insn
= NEXT_INSN (insn
)) != 0; )
3372 if (insn
== next_head
)
3375 switch (GET_CODE (insn
))
3382 switch (NOTE_KIND (insn
))
3384 case NOTE_INSN_BLOCK_END
:
3394 if (NEXT_INSN (insn
)
3395 && JUMP_TABLE_DATA_P (NEXT_INSN (insn
)))
3397 insn
= NEXT_INSN (insn
);
3410 /* It is possible to hit contradictory sequence. For instance:
3416 Where barrier belongs to jump_insn, but the note does not. This can be
3417 created by removing the basic block originally following
3418 NOTE_INSN_BLOCK_BEG. In such case reorder the notes. */
3420 for (insn
= last_insn
; insn
!= BB_END (bb
); insn
= prev
)
3422 prev
= PREV_INSN (insn
);
3424 switch (NOTE_KIND (insn
))
3426 case NOTE_INSN_BLOCK_END
:
3429 case NOTE_INSN_DELETED
:
3430 case NOTE_INSN_DELETED_LABEL
:
3431 case NOTE_INSN_DELETED_DEBUG_LABEL
:
3434 reorder_insns (insn
, insn
, last_insn
);
3441 /* Locate or create a label for a given basic block. */
3444 label_for_bb (basic_block bb
)
3446 rtx_insn
*label
= BB_HEAD (bb
);
3448 if (!LABEL_P (label
))
3451 fprintf (dump_file
, "Emitting label for block %d\n", bb
->index
);
3453 label
= block_label (bb
);
3459 /* Locate the effective beginning and end of the insn chain for each
3460 block, as defined by skip_insns_after_block above. */
3463 record_effective_endpoints (void)
3465 rtx_insn
*next_insn
;
3469 for (insn
= get_insns ();
3472 && NOTE_KIND (insn
) != NOTE_INSN_BASIC_BLOCK
;
3473 insn
= NEXT_INSN (insn
))
3475 /* No basic blocks at all? */
3478 if (PREV_INSN (insn
))
3479 cfg_layout_function_header
=
3480 unlink_insn_chain (get_insns (), PREV_INSN (insn
));
3482 cfg_layout_function_header
= NULL
;
3484 next_insn
= get_insns ();
3485 FOR_EACH_BB_FN (bb
, cfun
)
3489 if (PREV_INSN (BB_HEAD (bb
)) && next_insn
!= BB_HEAD (bb
))
3490 BB_HEADER (bb
) = unlink_insn_chain (next_insn
,
3491 PREV_INSN (BB_HEAD (bb
)));
3492 end
= skip_insns_after_block (bb
);
3493 if (NEXT_INSN (BB_END (bb
)) && BB_END (bb
) != end
)
3494 BB_FOOTER (bb
) = unlink_insn_chain (NEXT_INSN (BB_END (bb
)), end
);
3495 next_insn
= NEXT_INSN (BB_END (bb
));
3498 cfg_layout_function_footer
= next_insn
;
3499 if (cfg_layout_function_footer
)
3500 cfg_layout_function_footer
= unlink_insn_chain (cfg_layout_function_footer
, get_last_insn ());
3505 const pass_data pass_data_into_cfg_layout_mode
=
3507 RTL_PASS
, /* type */
3508 "into_cfglayout", /* name */
3509 OPTGROUP_NONE
, /* optinfo_flags */
3511 0, /* properties_required */
3512 PROP_cfglayout
, /* properties_provided */
3513 0, /* properties_destroyed */
3514 0, /* todo_flags_start */
3515 0, /* todo_flags_finish */
3518 class pass_into_cfg_layout_mode
: public rtl_opt_pass
3521 pass_into_cfg_layout_mode (gcc::context
*ctxt
)
3522 : rtl_opt_pass (pass_data_into_cfg_layout_mode
, ctxt
)
3525 /* opt_pass methods: */
3526 virtual unsigned int execute (function
*)
3528 cfg_layout_initialize (0);
3532 }; // class pass_into_cfg_layout_mode
3537 make_pass_into_cfg_layout_mode (gcc::context
*ctxt
)
3539 return new pass_into_cfg_layout_mode (ctxt
);
3544 const pass_data pass_data_outof_cfg_layout_mode
=
3546 RTL_PASS
, /* type */
3547 "outof_cfglayout", /* name */
3548 OPTGROUP_NONE
, /* optinfo_flags */
3550 0, /* properties_required */
3551 0, /* properties_provided */
3552 PROP_cfglayout
, /* properties_destroyed */
3553 0, /* todo_flags_start */
3554 0, /* todo_flags_finish */
3557 class pass_outof_cfg_layout_mode
: public rtl_opt_pass
3560 pass_outof_cfg_layout_mode (gcc::context
*ctxt
)
3561 : rtl_opt_pass (pass_data_outof_cfg_layout_mode
, ctxt
)
3564 /* opt_pass methods: */
3565 virtual unsigned int execute (function
*);
3567 }; // class pass_outof_cfg_layout_mode
3570 pass_outof_cfg_layout_mode::execute (function
*fun
)
3574 FOR_EACH_BB_FN (bb
, fun
)
3575 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (fun
))
3576 bb
->aux
= bb
->next_bb
;
3578 cfg_layout_finalize ();
3586 make_pass_outof_cfg_layout_mode (gcc::context
*ctxt
)
3588 return new pass_outof_cfg_layout_mode (ctxt
);
3592 /* Link the basic blocks in the correct order, compacting the basic
3593 block queue while at it. If STAY_IN_CFGLAYOUT_MODE is false, this
3594 function also clears the basic block header and footer fields.
3596 This function is usually called after a pass (e.g. tracer) finishes
3597 some transformations while in cfglayout mode. The required sequence
3598 of the basic blocks is in a linked list along the bb->aux field.
3599 This functions re-links the basic block prev_bb and next_bb pointers
3600 accordingly, and it compacts and renumbers the blocks.
3602 FIXME: This currently works only for RTL, but the only RTL-specific
3603 bits are the STAY_IN_CFGLAYOUT_MODE bits. The tracer pass was moved
3604 to GIMPLE a long time ago, but it doesn't relink the basic block
3605 chain. It could do that (to give better initial RTL) if this function
3606 is made IR-agnostic (and moved to cfganal.c or cfg.c while at it). */
3609 relink_block_chain (bool stay_in_cfglayout_mode
)
3611 basic_block bb
, prev_bb
;
3614 /* Maybe dump the re-ordered sequence. */
3617 fprintf (dump_file
, "Reordered sequence:\n");
3618 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
, index
=
3621 bb
= (basic_block
) bb
->aux
, index
++)
3623 fprintf (dump_file
, " %i ", index
);
3624 if (get_bb_original (bb
))
3625 fprintf (dump_file
, "duplicate of %i ",
3626 get_bb_original (bb
)->index
);
3627 else if (forwarder_block_p (bb
)
3628 && !LABEL_P (BB_HEAD (bb
)))
3629 fprintf (dump_file
, "compensation ");
3631 fprintf (dump_file
, "bb %i ", bb
->index
);
3632 fprintf (dump_file
, " [%i]\n", bb
->frequency
);
3636 /* Now reorder the blocks. */
3637 prev_bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
3638 bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
;
3639 for (; bb
; prev_bb
= bb
, bb
= (basic_block
) bb
->aux
)
3641 bb
->prev_bb
= prev_bb
;
3642 prev_bb
->next_bb
= bb
;
3644 prev_bb
->next_bb
= EXIT_BLOCK_PTR_FOR_FN (cfun
);
3645 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
= prev_bb
;
3647 /* Then, clean up the aux fields. */
3648 FOR_ALL_BB_FN (bb
, cfun
)
3651 if (!stay_in_cfglayout_mode
)
3652 BB_HEADER (bb
) = BB_FOOTER (bb
) = NULL
;
3655 /* Maybe reset the original copy tables, they are not valid anymore
3656 when we renumber the basic blocks in compact_blocks. If we are
3657 are going out of cfglayout mode, don't re-allocate the tables. */
3658 free_original_copy_tables ();
3659 if (stay_in_cfglayout_mode
)
3660 initialize_original_copy_tables ();
3662 /* Finally, put basic_block_info in the new order. */
3667 /* Given a reorder chain, rearrange the code to match. */
3670 fixup_reorder_chain (void)
3673 rtx_insn
*insn
= NULL
;
3675 if (cfg_layout_function_header
)
3677 set_first_insn (cfg_layout_function_header
);
3678 insn
= cfg_layout_function_header
;
3679 while (NEXT_INSN (insn
))
3680 insn
= NEXT_INSN (insn
);
3683 /* First do the bulk reordering -- rechain the blocks without regard to
3684 the needed changes to jumps and labels. */
3686 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
; bb
; bb
= (basic_block
)
3692 SET_NEXT_INSN (insn
) = BB_HEADER (bb
);
3694 set_first_insn (BB_HEADER (bb
));
3695 SET_PREV_INSN (BB_HEADER (bb
)) = insn
;
3696 insn
= BB_HEADER (bb
);
3697 while (NEXT_INSN (insn
))
3698 insn
= NEXT_INSN (insn
);
3701 SET_NEXT_INSN (insn
) = BB_HEAD (bb
);
3703 set_first_insn (BB_HEAD (bb
));
3704 SET_PREV_INSN (BB_HEAD (bb
)) = insn
;
3708 SET_NEXT_INSN (insn
) = BB_FOOTER (bb
);
3709 SET_PREV_INSN (BB_FOOTER (bb
)) = insn
;
3710 while (NEXT_INSN (insn
))
3711 insn
= NEXT_INSN (insn
);
3715 SET_NEXT_INSN (insn
) = cfg_layout_function_footer
;
3716 if (cfg_layout_function_footer
)
3717 SET_PREV_INSN (cfg_layout_function_footer
) = insn
;
3719 while (NEXT_INSN (insn
))
3720 insn
= NEXT_INSN (insn
);
3722 set_last_insn (insn
);
3724 verify_insn_chain ();
3726 /* Now add jumps and labels as needed to match the blocks new
3729 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
; bb
; bb
= (basic_block
)
3732 edge e_fall
, e_taken
, e
;
3733 rtx_insn
*bb_end_insn
;
3734 rtx ret_label
= NULL_RTX
;
3738 if (EDGE_COUNT (bb
->succs
) == 0)
3741 /* Find the old fallthru edge, and another non-EH edge for
3743 e_taken
= e_fall
= NULL
;
3745 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3746 if (e
->flags
& EDGE_FALLTHRU
)
3748 else if (! (e
->flags
& EDGE_EH
))
3751 bb_end_insn
= BB_END (bb
);
3752 if (rtx_jump_insn
*bb_end_jump
= dyn_cast
<rtx_jump_insn
*> (bb_end_insn
))
3754 ret_label
= JUMP_LABEL (bb_end_jump
);
3755 if (any_condjump_p (bb_end_jump
))
3757 /* This might happen if the conditional jump has side
3758 effects and could therefore not be optimized away.
3759 Make the basic block to end with a barrier in order
3760 to prevent rtl_verify_flow_info from complaining. */
3763 gcc_assert (!onlyjump_p (bb_end_jump
)
3764 || returnjump_p (bb_end_jump
)
3765 || (e_taken
->flags
& EDGE_CROSSING
));
3766 emit_barrier_after (bb_end_jump
);
3770 /* If the old fallthru is still next, nothing to do. */
3771 if (bb
->aux
== e_fall
->dest
3772 || e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3775 /* The degenerated case of conditional jump jumping to the next
3776 instruction can happen for jumps with side effects. We need
3777 to construct a forwarder block and this will be done just
3778 fine by force_nonfallthru below. */
3782 /* There is another special case: if *neither* block is next,
3783 such as happens at the very end of a function, then we'll
3784 need to add a new unconditional jump. Choose the taken
3785 edge based on known or assumed probability. */
3786 else if (bb
->aux
!= e_taken
->dest
)
3788 rtx note
= find_reg_note (bb_end_jump
, REG_BR_PROB
, 0);
3791 && XINT (note
, 0) < REG_BR_PROB_BASE
/ 2
3792 && invert_jump (bb_end_jump
,
3794 == EXIT_BLOCK_PTR_FOR_FN (cfun
)
3796 : label_for_bb (e_fall
->dest
)), 0))
3798 e_fall
->flags
&= ~EDGE_FALLTHRU
;
3799 gcc_checking_assert (could_fall_through
3800 (e_taken
->src
, e_taken
->dest
));
3801 e_taken
->flags
|= EDGE_FALLTHRU
;
3802 update_br_prob_note (bb
);
3803 e
= e_fall
, e_fall
= e_taken
, e_taken
= e
;
3807 /* If the "jumping" edge is a crossing edge, and the fall
3808 through edge is non-crossing, leave things as they are. */
3809 else if ((e_taken
->flags
& EDGE_CROSSING
)
3810 && !(e_fall
->flags
& EDGE_CROSSING
))
3813 /* Otherwise we can try to invert the jump. This will
3814 basically never fail, however, keep up the pretense. */
3815 else if (invert_jump (bb_end_jump
,
3817 == EXIT_BLOCK_PTR_FOR_FN (cfun
)
3819 : label_for_bb (e_fall
->dest
)), 0))
3821 e_fall
->flags
&= ~EDGE_FALLTHRU
;
3822 gcc_checking_assert (could_fall_through
3823 (e_taken
->src
, e_taken
->dest
));
3824 e_taken
->flags
|= EDGE_FALLTHRU
;
3825 update_br_prob_note (bb
);
3826 if (LABEL_NUSES (ret_label
) == 0
3827 && single_pred_p (e_taken
->dest
))
3828 delete_insn (ret_label
);
3832 else if (extract_asm_operands (PATTERN (bb_end_insn
)) != NULL
)
3834 /* If the old fallthru is still next or if
3835 asm goto doesn't have a fallthru (e.g. when followed by
3836 __builtin_unreachable ()), nothing to do. */
3838 || bb
->aux
== e_fall
->dest
3839 || e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3842 /* Otherwise we'll have to use the fallthru fixup below. */
3846 /* Otherwise we have some return, switch or computed
3847 jump. In the 99% case, there should not have been a
3849 gcc_assert (returnjump_p (bb_end_insn
) || !e_fall
);
3855 /* No fallthru implies a noreturn function with EH edges, or
3856 something similarly bizarre. In any case, we don't need to
3861 /* If the fallthru block is still next, nothing to do. */
3862 if (bb
->aux
== e_fall
->dest
)
3865 /* A fallthru to exit block. */
3866 if (e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3870 /* We got here if we need to add a new jump insn.
3871 Note force_nonfallthru can delete E_FALL and thus we have to
3872 save E_FALL->src prior to the call to force_nonfallthru. */
3873 nb
= force_nonfallthru_and_redirect (e_fall
, e_fall
->dest
, ret_label
);
3878 /* Don't process this new block. */
3883 relink_block_chain (/*stay_in_cfglayout_mode=*/false);
3885 /* Annoying special case - jump around dead jumptables left in the code. */
3886 FOR_EACH_BB_FN (bb
, cfun
)
3888 edge e
= find_fallthru_edge (bb
->succs
);
3890 if (e
&& !can_fallthru (e
->src
, e
->dest
))
3891 force_nonfallthru (e
);
3894 /* Ensure goto_locus from edges has some instructions with that locus
3897 FOR_EACH_BB_FN (bb
, cfun
)
3902 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3903 if (LOCATION_LOCUS (e
->goto_locus
) != UNKNOWN_LOCATION
3904 && !(e
->flags
& EDGE_ABNORMAL
))
3908 basic_block dest
, nb
;
3911 insn
= BB_END (e
->src
);
3912 end
= PREV_INSN (BB_HEAD (e
->src
));
3914 && (!NONDEBUG_INSN_P (insn
) || !INSN_HAS_LOCATION (insn
)))
3915 insn
= PREV_INSN (insn
);
3917 && INSN_LOCATION (insn
) == e
->goto_locus
)
3919 if (simplejump_p (BB_END (e
->src
))
3920 && !INSN_HAS_LOCATION (BB_END (e
->src
)))
3922 INSN_LOCATION (BB_END (e
->src
)) = e
->goto_locus
;
3926 if (dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3928 /* Non-fallthru edges to the exit block cannot be split. */
3929 if (!(e
->flags
& EDGE_FALLTHRU
))
3934 insn
= BB_HEAD (dest
);
3935 end
= NEXT_INSN (BB_END (dest
));
3936 while (insn
!= end
&& !NONDEBUG_INSN_P (insn
))
3937 insn
= NEXT_INSN (insn
);
3938 if (insn
!= end
&& INSN_HAS_LOCATION (insn
)
3939 && INSN_LOCATION (insn
) == e
->goto_locus
)
3942 nb
= split_edge (e
);
3943 if (!INSN_P (BB_END (nb
)))
3944 BB_END (nb
) = emit_insn_after_noloc (gen_nop (), BB_END (nb
),
3946 INSN_LOCATION (BB_END (nb
)) = e
->goto_locus
;
3948 /* If there are other incoming edges to the destination block
3949 with the same goto locus, redirect them to the new block as
3950 well, this can prevent other such blocks from being created
3951 in subsequent iterations of the loop. */
3952 for (ei2
= ei_start (dest
->preds
); (e2
= ei_safe_edge (ei2
)); )
3953 if (LOCATION_LOCUS (e2
->goto_locus
) != UNKNOWN_LOCATION
3954 && !(e2
->flags
& (EDGE_ABNORMAL
| EDGE_FALLTHRU
))
3955 && e
->goto_locus
== e2
->goto_locus
)
3956 redirect_edge_and_branch (e2
, nb
);
3963 /* Perform sanity checks on the insn chain.
3964 1. Check that next/prev pointers are consistent in both the forward and
3966 2. Count insns in chain, going both directions, and check if equal.
3967 3. Check that get_last_insn () returns the actual end of chain. */
3970 verify_insn_chain (void)
3972 rtx_insn
*x
, *prevx
, *nextx
;
3973 int insn_cnt1
, insn_cnt2
;
3975 for (prevx
= NULL
, insn_cnt1
= 1, x
= get_insns ();
3977 prevx
= x
, insn_cnt1
++, x
= NEXT_INSN (x
))
3978 gcc_assert (PREV_INSN (x
) == prevx
);
3980 gcc_assert (prevx
== get_last_insn ());
3982 for (nextx
= NULL
, insn_cnt2
= 1, x
= get_last_insn ();
3984 nextx
= x
, insn_cnt2
++, x
= PREV_INSN (x
))
3985 gcc_assert (NEXT_INSN (x
) == nextx
);
3987 gcc_assert (insn_cnt1
== insn_cnt2
);
3990 /* If we have assembler epilogues, the block falling through to exit must
3991 be the last one in the reordered chain when we reach final. Ensure
3992 that this condition is met. */
3994 fixup_fallthru_exit_predecessor (void)
3997 basic_block bb
= NULL
;
3999 /* This transformation is not valid before reload, because we might
4000 separate a call from the instruction that copies the return
4002 gcc_assert (reload_completed
);
4004 e
= find_fallthru_edge (EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
);
4010 basic_block c
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
;
4012 /* If the very first block is the one with the fall-through exit
4013 edge, we have to split that block. */
4016 bb
= split_block_after_labels (bb
)->dest
;
4019 BB_FOOTER (bb
) = BB_FOOTER (c
);
4020 BB_FOOTER (c
) = NULL
;
4023 while (c
->aux
!= bb
)
4024 c
= (basic_block
) c
->aux
;
4028 c
= (basic_block
) c
->aux
;
4035 /* In case there are more than one fallthru predecessors of exit, force that
4036 there is only one. */
4039 force_one_exit_fallthru (void)
4041 edge e
, predecessor
= NULL
;
4044 basic_block forwarder
, bb
;
4046 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
4047 if (e
->flags
& EDGE_FALLTHRU
)
4049 if (predecessor
== NULL
)
4061 /* Exit has several fallthru predecessors. Create a forwarder block for
4063 forwarder
= split_edge (predecessor
);
4064 for (ei
= ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
);
4065 (e
= ei_safe_edge (ei
)); )
4067 if (e
->src
== forwarder
4068 || !(e
->flags
& EDGE_FALLTHRU
))
4071 redirect_edge_and_branch_force (e
, forwarder
);
4074 /* Fix up the chain of blocks -- make FORWARDER immediately precede the
4076 FOR_EACH_BB_FN (bb
, cfun
)
4078 if (bb
->aux
== NULL
&& bb
!= forwarder
)
4080 bb
->aux
= forwarder
;
4086 /* Return true in case it is possible to duplicate the basic block BB. */
4089 cfg_layout_can_duplicate_bb_p (const_basic_block bb
)
4091 /* Do not attempt to duplicate tablejumps, as we need to unshare
4092 the dispatch table. This is difficult to do, as the instructions
4093 computing jump destination may be hoisted outside the basic block. */
4094 if (tablejump_p (BB_END (bb
), NULL
, NULL
))
4097 /* Do not duplicate blocks containing insns that can't be copied. */
4098 if (targetm
.cannot_copy_insn_p
)
4100 rtx_insn
*insn
= BB_HEAD (bb
);
4103 if (INSN_P (insn
) && targetm
.cannot_copy_insn_p (insn
))
4105 if (insn
== BB_END (bb
))
4107 insn
= NEXT_INSN (insn
);
4115 duplicate_insn_chain (rtx_insn
*from
, rtx_insn
*to
)
4117 rtx_insn
*insn
, *next
, *copy
;
4120 /* Avoid updating of boundaries of previous basic block. The
4121 note will get removed from insn stream in fixup. */
4122 last
= emit_note (NOTE_INSN_DELETED
);
4124 /* Create copy at the end of INSN chain. The chain will
4125 be reordered later. */
4126 for (insn
= from
; insn
!= NEXT_INSN (to
); insn
= NEXT_INSN (insn
))
4128 switch (GET_CODE (insn
))
4131 /* Don't duplicate label debug insns. */
4132 if (TREE_CODE (INSN_VAR_LOCATION_DECL (insn
)) == LABEL_DECL
)
4138 copy
= emit_copy_of_insn_after (insn
, get_last_insn ());
4139 if (JUMP_P (insn
) && JUMP_LABEL (insn
) != NULL_RTX
4140 && ANY_RETURN_P (JUMP_LABEL (insn
)))
4141 JUMP_LABEL (copy
) = JUMP_LABEL (insn
);
4142 maybe_copy_prologue_epilogue_insn (insn
, copy
);
4145 case JUMP_TABLE_DATA
:
4146 /* Avoid copying of dispatch tables. We never duplicate
4147 tablejumps, so this can hit only in case the table got
4148 moved far from original jump.
4149 Avoid copying following barrier as well if any
4150 (and debug insns in between). */
4151 for (next
= NEXT_INSN (insn
);
4152 next
!= NEXT_INSN (to
);
4153 next
= NEXT_INSN (next
))
4154 if (!DEBUG_INSN_P (next
))
4156 if (next
!= NEXT_INSN (to
) && BARRIER_P (next
))
4168 switch (NOTE_KIND (insn
))
4170 /* In case prologue is empty and function contain label
4171 in first BB, we may want to copy the block. */
4172 case NOTE_INSN_PROLOGUE_END
:
4174 case NOTE_INSN_DELETED
:
4175 case NOTE_INSN_DELETED_LABEL
:
4176 case NOTE_INSN_DELETED_DEBUG_LABEL
:
4177 /* No problem to strip these. */
4178 case NOTE_INSN_FUNCTION_BEG
:
4179 /* There is always just single entry to function. */
4180 case NOTE_INSN_BASIC_BLOCK
:
4181 /* We should only switch text sections once. */
4182 case NOTE_INSN_SWITCH_TEXT_SECTIONS
:
4185 case NOTE_INSN_EPILOGUE_BEG
:
4186 case NOTE_INSN_UPDATE_SJLJ_CONTEXT
:
4187 emit_note_copy (as_a
<rtx_note
*> (insn
));
4191 /* All other notes should have already been eliminated. */
4199 insn
= NEXT_INSN (last
);
4204 /* Create a duplicate of the basic block BB. */
4207 cfg_layout_duplicate_bb (basic_block bb
)
4212 insn
= duplicate_insn_chain (BB_HEAD (bb
), BB_END (bb
));
4213 new_bb
= create_basic_block (insn
,
4214 insn
? get_last_insn () : NULL
,
4215 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
);
4217 BB_COPY_PARTITION (new_bb
, bb
);
4220 insn
= BB_HEADER (bb
);
4221 while (NEXT_INSN (insn
))
4222 insn
= NEXT_INSN (insn
);
4223 insn
= duplicate_insn_chain (BB_HEADER (bb
), insn
);
4225 BB_HEADER (new_bb
) = unlink_insn_chain (insn
, get_last_insn ());
4230 insn
= BB_FOOTER (bb
);
4231 while (NEXT_INSN (insn
))
4232 insn
= NEXT_INSN (insn
);
4233 insn
= duplicate_insn_chain (BB_FOOTER (bb
), insn
);
4235 BB_FOOTER (new_bb
) = unlink_insn_chain (insn
, get_last_insn ());
4242 /* Main entry point to this module - initialize the datastructures for
4243 CFG layout changes. It keeps LOOPS up-to-date if not null.
4245 FLAGS is a set of additional flags to pass to cleanup_cfg(). */
4248 cfg_layout_initialize (unsigned int flags
)
4253 /* Once bb partitioning is complete, cfg layout mode should not be
4254 re-entered. Entering cfg layout mode may require fixups. As an
4255 example, if edge forwarding performed when optimizing the cfg
4256 layout required moving a block from the hot to the cold
4257 section. This would create an illegal partitioning unless some
4258 manual fixup was performed. */
4259 gcc_assert (!(crtl
->bb_reorder_complete
4260 && flag_reorder_blocks_and_partition
));
4262 initialize_original_copy_tables ();
4264 cfg_layout_rtl_register_cfg_hooks ();
4266 record_effective_endpoints ();
4268 /* Make sure that the targets of non local gotos are marked. */
4269 for (x
= nonlocal_goto_handler_labels
; x
; x
= x
->next ())
4271 bb
= BLOCK_FOR_INSN (x
->insn ());
4272 bb
->flags
|= BB_NON_LOCAL_GOTO_TARGET
;
4275 cleanup_cfg (CLEANUP_CFGLAYOUT
| flags
);
4278 /* Splits superblocks. */
4280 break_superblocks (void)
4282 sbitmap superblocks
;
4286 superblocks
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
4287 bitmap_clear (superblocks
);
4289 FOR_EACH_BB_FN (bb
, cfun
)
4290 if (bb
->flags
& BB_SUPERBLOCK
)
4292 bb
->flags
&= ~BB_SUPERBLOCK
;
4293 bitmap_set_bit (superblocks
, bb
->index
);
4299 rebuild_jump_labels (get_insns ());
4300 find_many_sub_basic_blocks (superblocks
);
4306 /* Finalize the changes: reorder insn list according to the sequence specified
4307 by aux pointers, enter compensation code, rebuild scope forest. */
4310 cfg_layout_finalize (void)
4312 checking_verify_flow_info ();
4313 force_one_exit_fallthru ();
4314 rtl_register_cfg_hooks ();
4315 if (reload_completed
&& !targetm
.have_epilogue ())
4316 fixup_fallthru_exit_predecessor ();
4317 fixup_reorder_chain ();
4319 rebuild_jump_labels (get_insns ());
4320 delete_dead_jumptables ();
4323 verify_insn_chain ();
4324 checking_verify_flow_info ();
4328 /* Same as split_block but update cfg_layout structures. */
4331 cfg_layout_split_block (basic_block bb
, void *insnp
)
4333 rtx insn
= (rtx
) insnp
;
4334 basic_block new_bb
= rtl_split_block (bb
, insn
);
4336 BB_FOOTER (new_bb
) = BB_FOOTER (bb
);
4337 BB_FOOTER (bb
) = NULL
;
4342 /* Redirect Edge to DEST. */
4344 cfg_layout_redirect_edge_and_branch (edge e
, basic_block dest
)
4346 basic_block src
= e
->src
;
4349 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
4352 if (e
->dest
== dest
)
4355 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4356 && (ret
= try_redirect_by_replacing_jump (e
, dest
, true)))
4358 df_set_bb_dirty (src
);
4362 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4363 && (e
->flags
& EDGE_FALLTHRU
) && !(e
->flags
& EDGE_COMPLEX
))
4366 fprintf (dump_file
, "Redirecting entry edge from bb %i to %i\n",
4367 e
->src
->index
, dest
->index
);
4369 df_set_bb_dirty (e
->src
);
4370 redirect_edge_succ (e
, dest
);
4374 /* Redirect_edge_and_branch may decide to turn branch into fallthru edge
4375 in the case the basic block appears to be in sequence. Avoid this
4378 if (e
->flags
& EDGE_FALLTHRU
)
4380 /* Redirect any branch edges unified with the fallthru one. */
4381 if (JUMP_P (BB_END (src
))
4382 && label_is_jump_target_p (BB_HEAD (e
->dest
),
4388 fprintf (dump_file
, "Fallthru edge unified with branch "
4389 "%i->%i redirected to %i\n",
4390 e
->src
->index
, e
->dest
->index
, dest
->index
);
4391 e
->flags
&= ~EDGE_FALLTHRU
;
4392 redirected
= redirect_branch_edge (e
, dest
);
4393 gcc_assert (redirected
);
4394 redirected
->flags
|= EDGE_FALLTHRU
;
4395 df_set_bb_dirty (redirected
->src
);
4398 /* In case we are redirecting fallthru edge to the branch edge
4399 of conditional jump, remove it. */
4400 if (EDGE_COUNT (src
->succs
) == 2)
4402 /* Find the edge that is different from E. */
4403 edge s
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
);
4406 && any_condjump_p (BB_END (src
))
4407 && onlyjump_p (BB_END (src
)))
4408 delete_insn (BB_END (src
));
4411 fprintf (dump_file
, "Redirecting fallthru edge %i->%i to %i\n",
4412 e
->src
->index
, e
->dest
->index
, dest
->index
);
4413 ret
= redirect_edge_succ_nodup (e
, dest
);
4416 ret
= redirect_branch_edge (e
, dest
);
4418 /* We don't want simplejumps in the insn stream during cfglayout. */
4419 gcc_assert (!simplejump_p (BB_END (src
)));
4421 df_set_bb_dirty (src
);
4425 /* Simple wrapper as we always can redirect fallthru edges. */
4427 cfg_layout_redirect_edge_and_branch_force (edge e
, basic_block dest
)
4429 edge redirected
= cfg_layout_redirect_edge_and_branch (e
, dest
);
4431 gcc_assert (redirected
);
4435 /* Same as delete_basic_block but update cfg_layout structures. */
4438 cfg_layout_delete_block (basic_block bb
)
4440 rtx_insn
*insn
, *next
, *prev
= PREV_INSN (BB_HEAD (bb
)), *remaints
;
4445 next
= BB_HEAD (bb
);
4447 SET_NEXT_INSN (prev
) = BB_HEADER (bb
);
4449 set_first_insn (BB_HEADER (bb
));
4450 SET_PREV_INSN (BB_HEADER (bb
)) = prev
;
4451 insn
= BB_HEADER (bb
);
4452 while (NEXT_INSN (insn
))
4453 insn
= NEXT_INSN (insn
);
4454 SET_NEXT_INSN (insn
) = next
;
4455 SET_PREV_INSN (next
) = insn
;
4457 next
= NEXT_INSN (BB_END (bb
));
4460 insn
= BB_FOOTER (bb
);
4463 if (BARRIER_P (insn
))
4465 if (PREV_INSN (insn
))
4466 SET_NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
4468 BB_FOOTER (bb
) = NEXT_INSN (insn
);
4469 if (NEXT_INSN (insn
))
4470 SET_PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
4474 insn
= NEXT_INSN (insn
);
4479 SET_NEXT_INSN (insn
) = BB_FOOTER (bb
);
4480 SET_PREV_INSN (BB_FOOTER (bb
)) = insn
;
4481 while (NEXT_INSN (insn
))
4482 insn
= NEXT_INSN (insn
);
4483 SET_NEXT_INSN (insn
) = next
;
4485 SET_PREV_INSN (next
) = insn
;
4487 set_last_insn (insn
);
4490 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
4491 to
= &BB_HEADER (bb
->next_bb
);
4493 to
= &cfg_layout_function_footer
;
4495 rtl_delete_block (bb
);
4498 prev
= NEXT_INSN (prev
);
4500 prev
= get_insns ();
4502 next
= PREV_INSN (next
);
4504 next
= get_last_insn ();
4506 if (next
&& NEXT_INSN (next
) != prev
)
4508 remaints
= unlink_insn_chain (prev
, next
);
4510 while (NEXT_INSN (insn
))
4511 insn
= NEXT_INSN (insn
);
4512 SET_NEXT_INSN (insn
) = *to
;
4514 SET_PREV_INSN (*to
) = insn
;
4519 /* Return true when blocks A and B can be safely merged. */
4522 cfg_layout_can_merge_blocks_p (basic_block a
, basic_block b
)
4524 /* If we are partitioning hot/cold basic blocks, we don't want to
4525 mess up unconditional or indirect jumps that cross between hot
4528 Basic block partitioning may result in some jumps that appear to
4529 be optimizable (or blocks that appear to be mergeable), but which really
4530 must be left untouched (they are required to make it safely across
4531 partition boundaries). See the comments at the top of
4532 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
4534 if (BB_PARTITION (a
) != BB_PARTITION (b
))
4537 /* Protect the loop latches. */
4538 if (current_loops
&& b
->loop_father
->latch
== b
)
4541 /* If we would end up moving B's instructions, make sure it doesn't fall
4542 through into the exit block, since we cannot recover from a fallthrough
4543 edge into the exit block occurring in the middle of a function. */
4544 if (NEXT_INSN (BB_END (a
)) != BB_HEAD (b
))
4546 edge e
= find_fallthru_edge (b
->succs
);
4547 if (e
&& e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4551 /* There must be exactly one edge in between the blocks. */
4552 return (single_succ_p (a
)
4553 && single_succ (a
) == b
4554 && single_pred_p (b
) == 1
4556 /* Must be simple edge. */
4557 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
4558 && a
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4559 && b
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
4560 /* If the jump insn has side effects, we can't kill the edge.
4561 When not optimizing, try_redirect_by_replacing_jump will
4562 not allow us to redirect an edge by replacing a table jump. */
4563 && (!JUMP_P (BB_END (a
))
4564 || ((!optimize
|| reload_completed
)
4565 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
4568 /* Merge block A and B. The blocks must be mergeable. */
4571 cfg_layout_merge_blocks (basic_block a
, basic_block b
)
4573 bool forwarder_p
= (b
->flags
& BB_FORWARDER_BLOCK
) != 0;
4576 gcc_checking_assert (cfg_layout_can_merge_blocks_p (a
, b
));
4579 fprintf (dump_file
, "Merging block %d into block %d...\n", b
->index
,
4582 /* If there was a CODE_LABEL beginning B, delete it. */
4583 if (LABEL_P (BB_HEAD (b
)))
4585 delete_insn (BB_HEAD (b
));
4588 /* We should have fallthru edge in a, or we can do dummy redirection to get
4590 if (JUMP_P (BB_END (a
)))
4591 try_redirect_by_replacing_jump (EDGE_SUCC (a
, 0), b
, true);
4592 gcc_assert (!JUMP_P (BB_END (a
)));
4594 /* When not optimizing and the edge is the only place in RTL which holds
4595 some unique locus, emit a nop with that locus in between. */
4597 emit_nop_for_unique_locus_between (a
, b
);
4599 /* Move things from b->footer after a->footer. */
4603 BB_FOOTER (a
) = BB_FOOTER (b
);
4606 rtx_insn
*last
= BB_FOOTER (a
);
4608 while (NEXT_INSN (last
))
4609 last
= NEXT_INSN (last
);
4610 SET_NEXT_INSN (last
) = BB_FOOTER (b
);
4611 SET_PREV_INSN (BB_FOOTER (b
)) = last
;
4613 BB_FOOTER (b
) = NULL
;
4616 /* Move things from b->header before a->footer.
4617 Note that this may include dead tablejump data, but we don't clean
4618 those up until we go out of cfglayout mode. */
4621 if (! BB_FOOTER (a
))
4622 BB_FOOTER (a
) = BB_HEADER (b
);
4625 rtx_insn
*last
= BB_HEADER (b
);
4627 while (NEXT_INSN (last
))
4628 last
= NEXT_INSN (last
);
4629 SET_NEXT_INSN (last
) = BB_FOOTER (a
);
4630 SET_PREV_INSN (BB_FOOTER (a
)) = last
;
4631 BB_FOOTER (a
) = BB_HEADER (b
);
4633 BB_HEADER (b
) = NULL
;
4636 /* In the case basic blocks are not adjacent, move them around. */
4637 if (NEXT_INSN (BB_END (a
)) != BB_HEAD (b
))
4639 insn
= unlink_insn_chain (BB_HEAD (b
), BB_END (b
));
4641 emit_insn_after_noloc (insn
, BB_END (a
), a
);
4643 /* Otherwise just re-associate the instructions. */
4647 BB_END (a
) = BB_END (b
);
4650 /* emit_insn_after_noloc doesn't call df_insn_change_bb.
4651 We need to explicitly call. */
4652 update_bb_for_insn_chain (insn
, BB_END (b
), a
);
4654 /* Skip possible DELETED_LABEL insn. */
4655 if (!NOTE_INSN_BASIC_BLOCK_P (insn
))
4656 insn
= NEXT_INSN (insn
);
4657 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
4658 BB_HEAD (b
) = BB_END (b
) = NULL
;
4661 df_bb_delete (b
->index
);
4663 /* If B was a forwarder block, propagate the locus on the edge. */
4665 && LOCATION_LOCUS (EDGE_SUCC (b
, 0)->goto_locus
) == UNKNOWN_LOCATION
)
4666 EDGE_SUCC (b
, 0)->goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
4669 fprintf (dump_file
, "Merged blocks %d and %d.\n", a
->index
, b
->index
);
4675 cfg_layout_split_edge (edge e
)
4677 basic_block new_bb
=
4678 create_basic_block (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4679 ? NEXT_INSN (BB_END (e
->src
)) : get_insns (),
4682 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4683 BB_COPY_PARTITION (new_bb
, e
->src
);
4685 BB_COPY_PARTITION (new_bb
, e
->dest
);
4686 make_edge (new_bb
, e
->dest
, EDGE_FALLTHRU
);
4687 redirect_edge_and_branch_force (e
, new_bb
);
4692 /* Do postprocessing after making a forwarder block joined by edge FALLTHRU. */
4695 rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED
)
4699 /* Return true if BB contains only labels or non-executable
4703 rtl_block_empty_p (basic_block bb
)
4707 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4708 || bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4711 FOR_BB_INSNS (bb
, insn
)
4712 if (NONDEBUG_INSN_P (insn
) && !any_uncondjump_p (insn
))
4718 /* Split a basic block if it ends with a conditional branch and if
4719 the other part of the block is not empty. */
4722 rtl_split_block_before_cond_jump (basic_block bb
)
4725 rtx_insn
*split_point
= NULL
;
4726 rtx_insn
*last
= NULL
;
4727 bool found_code
= false;
4729 FOR_BB_INSNS (bb
, insn
)
4731 if (any_condjump_p (insn
))
4733 else if (NONDEBUG_INSN_P (insn
))
4738 /* Did not find everything. */
4739 if (found_code
&& split_point
)
4740 return split_block (bb
, split_point
)->dest
;
4745 /* Return 1 if BB ends with a call, possibly followed by some
4746 instructions that must stay with the call, 0 otherwise. */
4749 rtl_block_ends_with_call_p (basic_block bb
)
4751 rtx_insn
*insn
= BB_END (bb
);
4753 while (!CALL_P (insn
)
4754 && insn
!= BB_HEAD (bb
)
4755 && (keep_with_call_p (insn
)
4757 || DEBUG_INSN_P (insn
)))
4758 insn
= PREV_INSN (insn
);
4759 return (CALL_P (insn
));
4762 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
4765 rtl_block_ends_with_condjump_p (const_basic_block bb
)
4767 return any_condjump_p (BB_END (bb
));
4770 /* Return true if we need to add fake edge to exit.
4771 Helper function for rtl_flow_call_edges_add. */
4774 need_fake_edge_p (const rtx_insn
*insn
)
4780 && !SIBLING_CALL_P (insn
)
4781 && !find_reg_note (insn
, REG_NORETURN
, NULL
)
4782 && !(RTL_CONST_OR_PURE_CALL_P (insn
))))
4785 return ((GET_CODE (PATTERN (insn
)) == ASM_OPERANDS
4786 && MEM_VOLATILE_P (PATTERN (insn
)))
4787 || (GET_CODE (PATTERN (insn
)) == PARALLEL
4788 && asm_noperands (insn
) != -1
4789 && MEM_VOLATILE_P (XVECEXP (PATTERN (insn
), 0, 0)))
4790 || GET_CODE (PATTERN (insn
)) == ASM_INPUT
);
4793 /* Add fake edges to the function exit for any non constant and non noreturn
4794 calls, volatile inline assembly in the bitmap of blocks specified by
4795 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
4798 The goal is to expose cases in which entering a basic block does not imply
4799 that all subsequent instructions must be executed. */
4802 rtl_flow_call_edges_add (sbitmap blocks
)
4805 int blocks_split
= 0;
4806 int last_bb
= last_basic_block_for_fn (cfun
);
4807 bool check_last_block
= false;
4809 if (n_basic_blocks_for_fn (cfun
) == NUM_FIXED_BLOCKS
)
4813 check_last_block
= true;
4815 check_last_block
= bitmap_bit_p (blocks
,
4816 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
->index
);
4818 /* In the last basic block, before epilogue generation, there will be
4819 a fallthru edge to EXIT. Special care is required if the last insn
4820 of the last basic block is a call because make_edge folds duplicate
4821 edges, which would result in the fallthru edge also being marked
4822 fake, which would result in the fallthru edge being removed by
4823 remove_fake_edges, which would result in an invalid CFG.
4825 Moreover, we can't elide the outgoing fake edge, since the block
4826 profiler needs to take this into account in order to solve the minimal
4827 spanning tree in the case that the call doesn't return.
4829 Handle this by adding a dummy instruction in a new last basic block. */
4830 if (check_last_block
)
4832 basic_block bb
= EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
;
4833 rtx_insn
*insn
= BB_END (bb
);
4835 /* Back up past insns that must be kept in the same block as a call. */
4836 while (insn
!= BB_HEAD (bb
)
4837 && keep_with_call_p (insn
))
4838 insn
= PREV_INSN (insn
);
4840 if (need_fake_edge_p (insn
))
4844 e
= find_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
4847 insert_insn_on_edge (gen_use (const0_rtx
), e
);
4848 commit_edge_insertions ();
4853 /* Now add fake edges to the function exit for any non constant
4854 calls since there is no way that we can determine if they will
4857 for (i
= NUM_FIXED_BLOCKS
; i
< last_bb
; i
++)
4859 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
4861 rtx_insn
*prev_insn
;
4866 if (blocks
&& !bitmap_bit_p (blocks
, i
))
4869 for (insn
= BB_END (bb
); ; insn
= prev_insn
)
4871 prev_insn
= PREV_INSN (insn
);
4872 if (need_fake_edge_p (insn
))
4875 rtx_insn
*split_at_insn
= insn
;
4877 /* Don't split the block between a call and an insn that should
4878 remain in the same block as the call. */
4880 while (split_at_insn
!= BB_END (bb
)
4881 && keep_with_call_p (NEXT_INSN (split_at_insn
)))
4882 split_at_insn
= NEXT_INSN (split_at_insn
);
4884 /* The handling above of the final block before the epilogue
4885 should be enough to verify that there is no edge to the exit
4886 block in CFG already. Calling make_edge in such case would
4887 cause us to mark that edge as fake and remove it later. */
4889 if (flag_checking
&& split_at_insn
== BB_END (bb
))
4891 e
= find_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
4892 gcc_assert (e
== NULL
);
4895 /* Note that the following may create a new basic block
4896 and renumber the existing basic blocks. */
4897 if (split_at_insn
!= BB_END (bb
))
4899 e
= split_block (bb
, split_at_insn
);
4904 make_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), EDGE_FAKE
);
4907 if (insn
== BB_HEAD (bb
))
4913 verify_flow_info ();
4915 return blocks_split
;
4918 /* Add COMP_RTX as a condition at end of COND_BB. FIRST_HEAD is
4919 the conditional branch target, SECOND_HEAD should be the fall-thru
4920 there is no need to handle this here the loop versioning code handles
4921 this. the reason for SECON_HEAD is that it is needed for condition
4922 in trees, and this should be of the same type since it is a hook. */
4924 rtl_lv_add_condition_to_bb (basic_block first_head
,
4925 basic_block second_head ATTRIBUTE_UNUSED
,
4926 basic_block cond_bb
, void *comp_rtx
)
4928 rtx_code_label
*label
;
4929 rtx_insn
*seq
, *jump
;
4930 rtx op0
= XEXP ((rtx
)comp_rtx
, 0);
4931 rtx op1
= XEXP ((rtx
)comp_rtx
, 1);
4932 enum rtx_code comp
= GET_CODE ((rtx
)comp_rtx
);
4936 label
= block_label (first_head
);
4937 mode
= GET_MODE (op0
);
4938 if (mode
== VOIDmode
)
4939 mode
= GET_MODE (op1
);
4942 op0
= force_operand (op0
, NULL_RTX
);
4943 op1
= force_operand (op1
, NULL_RTX
);
4944 do_compare_rtx_and_jump (op0
, op1
, comp
, 0, mode
, NULL_RTX
, NULL
, label
, -1);
4945 jump
= get_last_insn ();
4946 JUMP_LABEL (jump
) = label
;
4947 LABEL_NUSES (label
)++;
4951 /* Add the new cond, in the new head. */
4952 emit_insn_after (seq
, BB_END (cond_bb
));
4956 /* Given a block B with unconditional branch at its end, get the
4957 store the return the branch edge and the fall-thru edge in
4958 BRANCH_EDGE and FALLTHRU_EDGE respectively. */
4960 rtl_extract_cond_bb_edges (basic_block b
, edge
*branch_edge
,
4961 edge
*fallthru_edge
)
4963 edge e
= EDGE_SUCC (b
, 0);
4965 if (e
->flags
& EDGE_FALLTHRU
)
4968 *branch_edge
= EDGE_SUCC (b
, 1);
4973 *fallthru_edge
= EDGE_SUCC (b
, 1);
4978 init_rtl_bb_info (basic_block bb
)
4980 gcc_assert (!bb
->il
.x
.rtl
);
4981 bb
->il
.x
.head_
= NULL
;
4982 bb
->il
.x
.rtl
= ggc_cleared_alloc
<rtl_bb_info
> ();
4985 /* Returns true if it is possible to remove edge E by redirecting
4986 it to the destination of the other edge from E->src. */
4989 rtl_can_remove_branch_p (const_edge e
)
4991 const_basic_block src
= e
->src
;
4992 const_basic_block target
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
;
4993 const rtx_insn
*insn
= BB_END (src
);
4996 /* The conditions are taken from try_redirect_by_replacing_jump. */
4997 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
5000 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
5003 if (BB_PARTITION (src
) != BB_PARTITION (target
))
5006 if (!onlyjump_p (insn
)
5007 || tablejump_p (insn
, NULL
, NULL
))
5010 set
= single_set (insn
);
5011 if (!set
|| side_effects_p (set
))
5018 rtl_duplicate_bb (basic_block bb
)
5020 bb
= cfg_layout_duplicate_bb (bb
);
5025 /* Do book-keeping of basic block BB for the profile consistency checker.
5026 If AFTER_PASS is 0, do pre-pass accounting, or if AFTER_PASS is 1
5027 then do post-pass accounting. Store the counting in RECORD. */
5029 rtl_account_profile_record (basic_block bb
, int after_pass
,
5030 struct profile_record
*record
)
5033 FOR_BB_INSNS (bb
, insn
)
5036 record
->size
[after_pass
]
5037 += insn_rtx_cost (PATTERN (insn
), false);
5038 if (profile_status_for_fn (cfun
) == PROFILE_READ
)
5039 record
->time
[after_pass
]
5040 += insn_rtx_cost (PATTERN (insn
), true) * bb
->count
;
5041 else if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
)
5042 record
->time
[after_pass
]
5043 += insn_rtx_cost (PATTERN (insn
), true) * bb
->frequency
;
5047 /* Implementation of CFG manipulation for linearized RTL. */
5048 struct cfg_hooks rtl_cfg_hooks
= {
5050 rtl_verify_flow_info
,
5052 rtl_dump_bb_for_graph
,
5053 rtl_create_basic_block
,
5054 rtl_redirect_edge_and_branch
,
5055 rtl_redirect_edge_and_branch_force
,
5056 rtl_can_remove_branch_p
,
5059 rtl_move_block_after
,
5060 rtl_can_merge_blocks
, /* can_merge_blocks_p */
5064 cfg_layout_can_duplicate_bb_p
,
5067 rtl_make_forwarder_block
,
5068 rtl_tidy_fallthru_edge
,
5069 rtl_force_nonfallthru
,
5070 rtl_block_ends_with_call_p
,
5071 rtl_block_ends_with_condjump_p
,
5072 rtl_flow_call_edges_add
,
5073 NULL
, /* execute_on_growing_pred */
5074 NULL
, /* execute_on_shrinking_pred */
5075 NULL
, /* duplicate loop for trees */
5076 NULL
, /* lv_add_condition_to_bb */
5077 NULL
, /* lv_adjust_loop_header_phi*/
5078 NULL
, /* extract_cond_bb_edges */
5079 NULL
, /* flush_pending_stmts */
5080 rtl_block_empty_p
, /* block_empty_p */
5081 rtl_split_block_before_cond_jump
, /* split_block_before_cond_jump */
5082 rtl_account_profile_record
,
5085 /* Implementation of CFG manipulation for cfg layout RTL, where
5086 basic block connected via fallthru edges does not have to be adjacent.
5087 This representation will hopefully become the default one in future
5088 version of the compiler. */
5090 struct cfg_hooks cfg_layout_rtl_cfg_hooks
= {
5092 rtl_verify_flow_info_1
,
5094 rtl_dump_bb_for_graph
,
5095 cfg_layout_create_basic_block
,
5096 cfg_layout_redirect_edge_and_branch
,
5097 cfg_layout_redirect_edge_and_branch_force
,
5098 rtl_can_remove_branch_p
,
5099 cfg_layout_delete_block
,
5100 cfg_layout_split_block
,
5101 rtl_move_block_after
,
5102 cfg_layout_can_merge_blocks_p
,
5103 cfg_layout_merge_blocks
,
5106 cfg_layout_can_duplicate_bb_p
,
5107 cfg_layout_duplicate_bb
,
5108 cfg_layout_split_edge
,
5109 rtl_make_forwarder_block
,
5110 NULL
, /* tidy_fallthru_edge */
5111 rtl_force_nonfallthru
,
5112 rtl_block_ends_with_call_p
,
5113 rtl_block_ends_with_condjump_p
,
5114 rtl_flow_call_edges_add
,
5115 NULL
, /* execute_on_growing_pred */
5116 NULL
, /* execute_on_shrinking_pred */
5117 duplicate_loop_to_header_edge
, /* duplicate loop for trees */
5118 rtl_lv_add_condition_to_bb
, /* lv_add_condition_to_bb */
5119 NULL
, /* lv_adjust_loop_header_phi*/
5120 rtl_extract_cond_bb_edges
, /* extract_cond_bb_edges */
5121 NULL
, /* flush_pending_stmts */
5122 rtl_block_empty_p
, /* block_empty_p */
5123 rtl_split_block_before_cond_jump
, /* split_block_before_cond_jump */
5124 rtl_account_profile_record
,
5127 #include "gt-cfgrtl.h"