1 /* Control flow graph manipulation code for GNU compiler.
2 Copyright (C) 1987-2024 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, prepend_insn_to_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"
49 #include "insn-config.h"
55 #include "cfgcleanup.h"
56 #include "bb-reorder.h"
57 #include "rtl-error.h"
58 #include "insn-attr.h"
62 #include "tree-pass.h"
63 #include "print-rtl.h"
69 /* Disable warnings about missing quoting in GCC diagnostics. */
71 # pragma GCC diagnostic push
72 # pragma GCC diagnostic ignored "-Wformat-diag"
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 bool can_delete_note_p (const rtx_note
*);
87 static bool 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 bool 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, dump_flags_t
);
100 static bool rtl_verify_flow_info_1 (void);
101 static void rtl_make_forwarder_block (edge
);
102 static bool rtl_bb_info_initialized_p (basic_block bb
);
104 /* Return true if NOTE is not one of the ones that must be kept paired,
105 so that we may simply delete it. */
108 can_delete_note_p (const rtx_note
*note
)
110 switch (NOTE_KIND (note
))
112 case NOTE_INSN_DELETED
:
113 case NOTE_INSN_BASIC_BLOCK
:
114 case NOTE_INSN_EPILOGUE_BEG
:
122 /* True if a given label can be deleted. */
125 can_delete_label_p (const rtx_code_label
*label
)
127 return (!LABEL_PRESERVE_P (label
)
128 /* User declared labels must be preserved. */
129 && LABEL_NAME (label
) == 0
130 && !vec_safe_contains
<rtx_insn
*> (forced_labels
,
131 const_cast<rtx_code_label
*> (label
)));
134 /* Delete INSN by patching it out. */
137 delete_insn (rtx_insn
*insn
)
140 bool really_delete
= true;
144 /* Some labels can't be directly removed from the INSN chain, as they
145 might be references via variables, constant pool etc.
146 Convert them to the special NOTE_INSN_DELETED_LABEL note. */
147 if (! can_delete_label_p (as_a
<rtx_code_label
*> (insn
)))
149 const char *name
= LABEL_NAME (insn
);
150 basic_block bb
= BLOCK_FOR_INSN (insn
);
151 rtx_insn
*bb_note
= NEXT_INSN (insn
);
153 really_delete
= false;
154 PUT_CODE (insn
, NOTE
);
155 NOTE_KIND (insn
) = NOTE_INSN_DELETED_LABEL
;
156 NOTE_DELETED_LABEL_NAME (insn
) = name
;
158 /* If the note following the label starts a basic block, and the
159 label is a member of the same basic block, interchange the two. */
160 if (bb_note
!= NULL_RTX
161 && NOTE_INSN_BASIC_BLOCK_P (bb_note
)
163 && bb
== BLOCK_FOR_INSN (bb_note
))
165 reorder_insns_nobb (insn
, insn
, bb_note
);
166 BB_HEAD (bb
) = bb_note
;
167 if (BB_END (bb
) == bb_note
)
172 remove_node_from_insn_list (insn
, &nonlocal_goto_handler_labels
);
177 /* If this insn has already been deleted, something is very wrong. */
178 gcc_assert (!insn
->deleted ());
180 df_insn_delete (insn
);
182 insn
->set_deleted ();
185 /* If deleting a jump, decrement the use count of the label. Deleting
186 the label itself should happen in the normal course of block merging. */
189 if (JUMP_LABEL (insn
)
190 && LABEL_P (JUMP_LABEL (insn
)))
191 LABEL_NUSES (JUMP_LABEL (insn
))--;
193 /* If there are more targets, remove them too. */
195 = find_reg_note (insn
, REG_LABEL_TARGET
, NULL_RTX
)) != NULL_RTX
196 && LABEL_P (XEXP (note
, 0)))
198 LABEL_NUSES (XEXP (note
, 0))--;
199 remove_note (insn
, note
);
203 /* Also if deleting any insn that references a label as an operand. */
204 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, NULL_RTX
)) != NULL_RTX
205 && LABEL_P (XEXP (note
, 0)))
207 LABEL_NUSES (XEXP (note
, 0))--;
208 remove_note (insn
, note
);
211 if (rtx_jump_table_data
*table
= dyn_cast
<rtx_jump_table_data
*> (insn
))
213 rtvec vec
= table
->get_labels ();
214 int len
= GET_NUM_ELEM (vec
);
217 for (i
= 0; i
< len
; i
++)
219 rtx label
= XEXP (RTVEC_ELT (vec
, i
), 0);
221 /* When deleting code in bulk (e.g. removing many unreachable
222 blocks) we can delete a label that's a target of the vector
223 before deleting the vector itself. */
225 LABEL_NUSES (label
)--;
230 /* Like delete_insn but also purge dead edges from BB.
231 Return true if any edges are eliminated. */
234 delete_insn_and_edges (rtx_insn
*insn
)
238 if (NONDEBUG_INSN_P (insn
) && BLOCK_FOR_INSN (insn
))
240 basic_block bb
= BLOCK_FOR_INSN (insn
);
241 if (BB_END (bb
) == insn
)
243 else if (DEBUG_INSN_P (BB_END (bb
)))
244 for (rtx_insn
*dinsn
= NEXT_INSN (insn
);
245 DEBUG_INSN_P (dinsn
); dinsn
= NEXT_INSN (dinsn
))
246 if (BB_END (bb
) == dinsn
)
254 return purge_dead_edges (BLOCK_FOR_INSN (insn
));
258 /* Unlink a chain of insns between START and FINISH, leaving notes
259 that must be paired. If CLEAR_BB is true, we set bb field for
260 insns that cannot be removed to NULL. */
263 delete_insn_chain (rtx start
, rtx_insn
*finish
, bool clear_bb
)
265 /* Unchain the insns one by one. It would be quicker to delete all of these
266 with a single unchaining, rather than one at a time, but we need to keep
268 rtx_insn
*current
= finish
;
271 rtx_insn
*prev
= PREV_INSN (current
);
272 if (NOTE_P (current
) && !can_delete_note_p (as_a
<rtx_note
*> (current
)))
275 delete_insn (current
);
277 if (clear_bb
&& !current
->deleted ())
278 set_block_for_insn (current
, NULL
);
280 if (current
== start
)
286 /* Create a new basic block consisting of the instructions between HEAD and END
287 inclusive. This function is designed to allow fast BB construction - reuses
288 the note and basic block struct in BB_NOTE, if any and do not grow
289 BASIC_BLOCK chain and should be used directly only by CFG construction code.
290 END can be NULL in to create new empty basic block before HEAD. Both END
291 and HEAD can be NULL to create basic block at the end of INSN chain.
292 AFTER is the basic block we should be put after. */
295 create_basic_block_structure (rtx_insn
*head
, rtx_insn
*end
, rtx_note
*bb_note
,
301 && (bb
= NOTE_BASIC_BLOCK (bb_note
)) != NULL
304 /* If we found an existing note, thread it back onto the chain. */
312 after
= PREV_INSN (head
);
316 if (after
!= bb_note
&& NEXT_INSN (after
) != bb_note
)
317 reorder_insns_nobb (bb_note
, bb_note
, after
);
321 /* Otherwise we must create a note and a basic block structure. */
325 init_rtl_bb_info (bb
);
328 = emit_note_after (NOTE_INSN_BASIC_BLOCK
, get_last_insn ());
329 else if (LABEL_P (head
) && end
)
331 bb_note
= emit_note_after (NOTE_INSN_BASIC_BLOCK
, head
);
337 bb_note
= emit_note_before (NOTE_INSN_BASIC_BLOCK
, head
);
343 NOTE_BASIC_BLOCK (bb_note
) = bb
;
346 /* Always include the bb note in the block. */
347 if (NEXT_INSN (end
) == bb_note
)
352 bb
->index
= last_basic_block_for_fn (cfun
)++;
353 bb
->flags
= BB_NEW
| BB_RTL
;
354 link_block (bb
, after
);
355 SET_BASIC_BLOCK_FOR_FN (cfun
, bb
->index
, bb
);
356 df_bb_refs_record (bb
->index
, false);
357 update_bb_for_insn (bb
);
358 BB_SET_PARTITION (bb
, BB_UNPARTITIONED
);
360 /* Tag the block so that we know it has been used when considering
361 other basic block notes. */
367 /* Create new basic block consisting of instructions in between HEAD and END
368 and place it to the BB chain after block AFTER. END can be NULL to
369 create a new empty basic block before HEAD. Both END and HEAD can be
370 NULL to create basic block at the end of INSN chain. */
373 rtl_create_basic_block (void *headp
, void *endp
, basic_block after
)
375 rtx_insn
*head
= (rtx_insn
*) headp
;
376 rtx_insn
*end
= (rtx_insn
*) endp
;
379 /* Grow the basic block array if needed. */
380 if ((size_t) last_basic_block_for_fn (cfun
)
381 >= basic_block_info_for_fn (cfun
)->length ())
382 vec_safe_grow_cleared (basic_block_info_for_fn (cfun
),
383 last_basic_block_for_fn (cfun
) + 1);
385 n_basic_blocks_for_fn (cfun
)++;
387 bb
= create_basic_block_structure (head
, end
, NULL
, after
);
393 cfg_layout_create_basic_block (void *head
, void *end
, basic_block after
)
395 basic_block newbb
= rtl_create_basic_block (head
, end
, after
);
400 /* Delete the insns in a (non-live) block. We physically delete every
401 non-deleted-note insn, and update the flow graph appropriately.
403 Return nonzero if we deleted an exception handler. */
405 /* ??? Preserving all such notes strikes me as wrong. It would be nice
406 to post-process the stream to remove empty blocks, loops, ranges, etc. */
409 rtl_delete_block (basic_block b
)
411 rtx_insn
*insn
, *end
;
413 /* If the head of this block is a CODE_LABEL, then it might be the
414 label for an exception handler which can't be reached. We need
415 to remove the label from the exception_handler_label list. */
418 end
= get_last_bb_insn (b
);
420 /* Selectively delete the entire chain. */
422 delete_insn_chain (insn
, end
, true);
426 fprintf (dump_file
, "deleting block %d\n", b
->index
);
427 df_bb_delete (b
->index
);
430 /* Records the basic block struct in BLOCK_FOR_INSN for every insn. */
433 compute_bb_for_insn (void)
437 FOR_EACH_BB_FN (bb
, cfun
)
439 rtx_insn
*end
= BB_END (bb
);
442 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
444 BLOCK_FOR_INSN (insn
) = bb
;
451 /* Release the basic_block_for_insn array. */
454 free_bb_for_insn (void)
457 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
458 if (!BARRIER_P (insn
))
459 BLOCK_FOR_INSN (insn
) = NULL
;
464 const pass_data pass_data_free_cfg
=
467 "*free_cfg", /* name */
468 OPTGROUP_NONE
, /* optinfo_flags */
470 0, /* properties_required */
471 0, /* properties_provided */
472 PROP_cfg
, /* properties_destroyed */
473 0, /* todo_flags_start */
474 0, /* todo_flags_finish */
477 class pass_free_cfg
: public rtl_opt_pass
480 pass_free_cfg (gcc::context
*ctxt
)
481 : rtl_opt_pass (pass_data_free_cfg
, ctxt
)
484 /* opt_pass methods: */
485 unsigned int execute (function
*) final override
;
487 }; // class pass_free_cfg
490 pass_free_cfg::execute (function
*)
492 /* The resource.cc machinery uses DF but the CFG isn't guaranteed to be
493 valid at that point so it would be too late to call df_analyze. */
494 if (DELAY_SLOTS
&& optimize
> 0 && flag_delayed_branch
)
496 df_note_add_problem ();
500 if (crtl
->has_bb_partition
)
501 insert_section_boundary_note ();
510 make_pass_free_cfg (gcc::context
*ctxt
)
512 return new pass_free_cfg (ctxt
);
515 /* Return RTX to emit after when we want to emit code on the entry of function. */
517 entry_of_function (void)
519 return (n_basic_blocks_for_fn (cfun
) > NUM_FIXED_BLOCKS
?
520 BB_HEAD (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
) : get_insns ());
523 /* Emit INSN at the entry point of the function, ensuring that it is only
524 executed once per function. */
526 emit_insn_at_entry (rtx insn
)
528 edge_iterator ei
= ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
);
529 edge e
= ei_safe_edge (ei
);
530 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
532 insert_insn_on_edge (insn
, e
);
533 commit_edge_insertions ();
536 /* Update BLOCK_FOR_INSN of insns between BEGIN and END
537 (or BARRIER if found) and notify df of the bb change.
538 The insn chain range is inclusive
539 (i.e. both BEGIN and END will be updated. */
542 update_bb_for_insn_chain (rtx_insn
*begin
, rtx_insn
*end
, basic_block bb
)
546 end
= NEXT_INSN (end
);
547 for (insn
= begin
; insn
!= end
; insn
= NEXT_INSN (insn
))
548 if (!BARRIER_P (insn
))
549 df_insn_change_bb (insn
, bb
);
552 /* Update BLOCK_FOR_INSN of insns in BB to BB,
553 and notify df of the change. */
556 update_bb_for_insn (basic_block bb
)
558 update_bb_for_insn_chain (BB_HEAD (bb
), BB_END (bb
), bb
);
562 /* Like active_insn_p, except keep the return value use or clobber around
563 even after reload. */
566 flow_active_insn_p (const rtx_insn
*insn
)
568 if (active_insn_p (insn
))
571 /* A clobber of the function return value exists for buggy
572 programs that fail to return a value. Its effect is to
573 keep the return value from being live across the entire
574 function. If we allow it to be skipped, we introduce the
575 possibility for register lifetime confusion.
576 Similarly, keep a USE of the function return value, otherwise
577 the USE is dropped and we could fail to thread jump if USE
578 appears on some paths and not on others, see PR90257. */
579 if ((GET_CODE (PATTERN (insn
)) == CLOBBER
580 || GET_CODE (PATTERN (insn
)) == USE
)
581 && REG_P (XEXP (PATTERN (insn
), 0))
582 && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn
), 0)))
588 /* Return true if the block has no effect and only forwards control flow to
589 its single destination. */
592 contains_no_active_insn_p (const_basic_block bb
)
596 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
597 || bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
598 || !single_succ_p (bb
)
599 || (single_succ_edge (bb
)->flags
& EDGE_FAKE
) != 0)
602 for (insn
= BB_HEAD (bb
); insn
!= BB_END (bb
); insn
= NEXT_INSN (insn
))
603 if (INSN_P (insn
) && flow_active_insn_p (insn
))
606 return (!INSN_P (insn
)
607 || (JUMP_P (insn
) && simplejump_p (insn
))
608 || !flow_active_insn_p (insn
));
611 /* Likewise, but protect loop latches, headers and preheaders. */
612 /* FIXME: Make this a cfg hook. */
615 forwarder_block_p (const_basic_block bb
)
617 if (!contains_no_active_insn_p (bb
))
620 /* Protect loop latches, headers and preheaders. */
624 if (bb
->loop_father
->header
== bb
)
626 dest
= EDGE_SUCC (bb
, 0)->dest
;
627 if (dest
->loop_father
->header
== dest
)
634 /* Return nonzero if we can reach target from src by falling through. */
635 /* FIXME: Make this a cfg hook, the result is only valid in cfgrtl mode. */
638 can_fallthru (basic_block src
, basic_block target
)
640 rtx_insn
*insn
= BB_END (src
);
645 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
647 if (src
->next_bb
!= target
)
650 /* ??? Later we may add code to move jump tables offline. */
651 if (tablejump_p (insn
, NULL
, NULL
))
654 FOR_EACH_EDGE (e
, ei
, src
->succs
)
655 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
656 && e
->flags
& EDGE_FALLTHRU
)
659 insn2
= BB_HEAD (target
);
660 if (!active_insn_p (insn2
))
661 insn2
= next_active_insn (insn2
);
663 return next_active_insn (insn
) == insn2
;
666 /* Return nonzero if we could reach target from src by falling through,
667 if the target was made adjacent. If we already have a fall-through
668 edge to the exit block, we can't do that. */
670 could_fall_through (basic_block src
, basic_block target
)
675 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
677 FOR_EACH_EDGE (e
, ei
, src
->succs
)
678 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
679 && e
->flags
& EDGE_FALLTHRU
)
684 /* Return the NOTE_INSN_BASIC_BLOCK of BB. */
686 bb_note (basic_block bb
)
692 note
= NEXT_INSN (note
);
694 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
695 return as_a
<rtx_note
*> (note
);
698 /* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK
699 note associated with the BLOCK. */
702 first_insn_after_basic_block_note (basic_block block
)
706 /* Get the first instruction in the block. */
707 insn
= BB_HEAD (block
);
709 if (insn
== NULL_RTX
)
712 insn
= NEXT_INSN (insn
);
713 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
715 return NEXT_INSN (insn
);
718 /* Creates a new basic block just after basic block BB by splitting
719 everything after specified instruction INSNP. */
722 rtl_split_block (basic_block bb
, void *insnp
)
725 rtx_insn
*insn
= (rtx_insn
*) insnp
;
731 insn
= first_insn_after_basic_block_note (bb
);
735 rtx_insn
*next
= insn
;
737 insn
= PREV_INSN (insn
);
739 /* If the block contains only debug insns, insn would have
740 been NULL in a non-debug compilation, and then we'd end
741 up emitting a DELETED note. For -fcompare-debug
742 stability, emit the note too. */
743 if (insn
!= BB_END (bb
)
744 && DEBUG_INSN_P (next
)
745 && DEBUG_INSN_P (BB_END (bb
)))
747 while (next
!= BB_END (bb
) && DEBUG_INSN_P (next
))
748 next
= NEXT_INSN (next
);
750 if (next
== BB_END (bb
))
751 emit_note_after (NOTE_INSN_DELETED
, next
);
755 insn
= get_last_insn ();
758 /* We probably should check type of the insn so that we do not create
759 inconsistent cfg. It is checked in verify_flow_info anyway, so do not
761 if (insn
== BB_END (bb
))
762 emit_note_after (NOTE_INSN_DELETED
, insn
);
764 /* Create the new basic block. */
765 new_bb
= create_basic_block (NEXT_INSN (insn
), BB_END (bb
), bb
);
766 BB_COPY_PARTITION (new_bb
, bb
);
769 /* Redirect the outgoing edges. */
770 new_bb
->succs
= bb
->succs
;
772 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
775 /* The new block starts off being dirty. */
776 df_set_bb_dirty (bb
);
780 /* Return true if LOC1 and LOC2 are equivalent for
781 unique_locus_on_edge_between_p purposes. */
784 loc_equal (location_t loc1
, location_t loc2
)
789 expanded_location loce1
= expand_location (loc1
);
790 expanded_location loce2
= expand_location (loc2
);
792 if (loce1
.line
!= loce2
.line
793 || loce1
.column
!= loce2
.column
794 || loce1
.data
!= loce2
.data
)
796 if (loce1
.file
== loce2
.file
)
798 return (loce1
.file
!= NULL
799 && loce2
.file
!= NULL
800 && filename_cmp (loce1
.file
, loce2
.file
) == 0);
803 /* Return true if the single edge between blocks A and B is the only place
804 in RTL which holds some unique locus. */
807 unique_locus_on_edge_between_p (basic_block a
, basic_block b
)
809 const location_t goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
810 rtx_insn
*insn
, *end
;
812 if (LOCATION_LOCUS (goto_locus
) == UNKNOWN_LOCATION
)
815 /* First scan block A backward. */
817 end
= PREV_INSN (BB_HEAD (a
));
818 while (insn
!= end
&& (!NONDEBUG_INSN_P (insn
) || !INSN_HAS_LOCATION (insn
)))
819 insn
= PREV_INSN (insn
);
821 if (insn
!= end
&& loc_equal (INSN_LOCATION (insn
), goto_locus
))
824 /* Then scan block B forward. */
828 end
= NEXT_INSN (BB_END (b
));
829 while (insn
!= end
&& !NONDEBUG_INSN_P (insn
))
830 insn
= NEXT_INSN (insn
);
832 if (insn
!= end
&& INSN_HAS_LOCATION (insn
)
833 && loc_equal (INSN_LOCATION (insn
), goto_locus
))
840 /* If the single edge between blocks A and B is the only place in RTL which
841 holds some unique locus, emit a nop with that locus between the blocks. */
844 emit_nop_for_unique_locus_between (basic_block a
, basic_block b
)
846 if (!unique_locus_on_edge_between_p (a
, b
))
849 BB_END (a
) = emit_insn_after_noloc (gen_nop (), BB_END (a
), a
);
850 INSN_LOCATION (BB_END (a
)) = EDGE_SUCC (a
, 0)->goto_locus
;
853 /* Blocks A and B are to be merged into a single block A. The insns
854 are already contiguous. */
857 rtl_merge_blocks (basic_block a
, basic_block b
)
859 /* If B is a forwarder block whose outgoing edge has no location, we'll
860 propagate the locus of the edge between A and B onto it. */
861 const bool forward_edge_locus
862 = (b
->flags
& BB_FORWARDER_BLOCK
) != 0
863 && LOCATION_LOCUS (EDGE_SUCC (b
, 0)->goto_locus
) == UNKNOWN_LOCATION
;
864 rtx_insn
*b_head
= BB_HEAD (b
), *b_end
= BB_END (b
), *a_end
= BB_END (a
);
865 rtx_insn
*del_first
= NULL
, *del_last
= NULL
;
866 rtx_insn
*b_debug_start
= b_end
, *b_debug_end
= b_end
;
867 bool b_empty
= false;
870 fprintf (dump_file
, "Merging block %d into block %d...\n", b
->index
,
873 while (DEBUG_INSN_P (b_end
))
874 b_end
= PREV_INSN (b_debug_start
= b_end
);
876 /* If there was a CODE_LABEL beginning B, delete it. */
877 if (LABEL_P (b_head
))
879 /* Detect basic blocks with nothing but a label. This can happen
880 in particular at the end of a function. */
884 del_first
= del_last
= b_head
;
885 b_head
= NEXT_INSN (b_head
);
888 /* Delete the basic block note and handle blocks containing just that
890 if (NOTE_INSN_BASIC_BLOCK_P (b_head
))
898 b_head
= NEXT_INSN (b_head
);
901 /* If there was a jump out of A, delete it. */
906 for (prev
= PREV_INSN (a_end
); ; prev
= PREV_INSN (prev
))
908 || NOTE_INSN_BASIC_BLOCK_P (prev
)
909 || prev
== BB_HEAD (a
))
914 a_end
= PREV_INSN (del_first
);
916 else if (BARRIER_P (NEXT_INSN (a_end
)))
917 del_first
= NEXT_INSN (a_end
);
919 /* Delete everything marked above as well as crap that might be
920 hanging out between the two blocks. */
922 BB_HEAD (b
) = b_empty
? NULL
: b_head
;
923 delete_insn_chain (del_first
, del_last
, true);
925 /* If not optimizing, preserve the locus of the single edge between
926 blocks A and B if necessary by emitting a nop. */
928 && !forward_edge_locus
929 && !DECL_IGNORED_P (current_function_decl
))
931 emit_nop_for_unique_locus_between (a
, b
);
935 /* Reassociate the insns of B with A. */
938 update_bb_for_insn_chain (a_end
, b_debug_end
, a
);
940 BB_END (a
) = b_debug_end
;
943 else if (b_end
!= b_debug_end
)
945 /* Move any deleted labels and other notes between the end of A
946 and the debug insns that make up B after the debug insns,
947 bringing the debug insns into A while keeping the notes after
949 if (NEXT_INSN (a_end
) != b_debug_start
)
950 reorder_insns_nobb (NEXT_INSN (a_end
), PREV_INSN (b_debug_start
),
952 update_bb_for_insn_chain (b_debug_start
, b_debug_end
, a
);
953 BB_END (a
) = b_debug_end
;
956 df_bb_delete (b
->index
);
958 if (forward_edge_locus
)
959 EDGE_SUCC (b
, 0)->goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
962 fprintf (dump_file
, "Merged blocks %d and %d.\n", a
->index
, b
->index
);
966 /* Return true when block A and B can be merged. */
969 rtl_can_merge_blocks (basic_block a
, basic_block b
)
971 /* If we are partitioning hot/cold basic blocks, we don't want to
972 mess up unconditional or indirect jumps that cross between hot
975 Basic block partitioning may result in some jumps that appear to
976 be optimizable (or blocks that appear to be mergeable), but which really
977 must be left untouched (they are required to make it safely across
978 partition boundaries). See the comments at the top of
979 bb-reorder.cc:partition_hot_cold_basic_blocks for complete details. */
981 if (BB_PARTITION (a
) != BB_PARTITION (b
))
984 /* Protect the loop latches. */
985 if (current_loops
&& b
->loop_father
->latch
== b
)
988 /* There must be exactly one edge in between the blocks. */
989 return (single_succ_p (a
)
990 && single_succ (a
) == b
993 /* Must be simple edge. */
994 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
996 && a
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
997 && b
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
998 /* If the jump insn has side effects,
999 we can't kill the edge. */
1000 && (!JUMP_P (BB_END (a
))
1001 || (reload_completed
1002 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
1005 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
1009 block_label (basic_block block
)
1011 if (block
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1014 if (!LABEL_P (BB_HEAD (block
)))
1016 BB_HEAD (block
) = emit_label_before (gen_label_rtx (), BB_HEAD (block
));
1019 return as_a
<rtx_code_label
*> (BB_HEAD (block
));
1022 /* Remove all barriers from BB_FOOTER of a BB. */
1025 remove_barriers_from_footer (basic_block bb
)
1027 rtx_insn
*insn
= BB_FOOTER (bb
);
1029 /* Remove barriers but keep jumptables. */
1032 if (BARRIER_P (insn
))
1034 if (PREV_INSN (insn
))
1035 SET_NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
1037 BB_FOOTER (bb
) = NEXT_INSN (insn
);
1038 if (NEXT_INSN (insn
))
1039 SET_PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
1043 insn
= NEXT_INSN (insn
);
1047 /* Attempt to perform edge redirection by replacing possibly complex jump
1048 instruction by unconditional jump or removing jump completely. This can
1049 apply only if all edges now point to the same block. The parameters and
1050 return values are equivalent to redirect_edge_and_branch. */
1053 try_redirect_by_replacing_jump (edge e
, basic_block target
, bool in_cfglayout
)
1055 basic_block src
= e
->src
;
1056 rtx_insn
*insn
= BB_END (src
);
1058 bool fallthru
= false;
1060 /* If we are partitioning hot/cold basic blocks, we don't want to
1061 mess up unconditional or indirect jumps that cross between hot
1064 Basic block partitioning may result in some jumps that appear to
1065 be optimizable (or blocks that appear to be mergeable), but which really
1066 must be left untouched (they are required to make it safely across
1067 partition boundaries). See the comments at the top of
1068 bb-reorder.cc:partition_hot_cold_basic_blocks for complete details. */
1070 if (BB_PARTITION (src
) != BB_PARTITION (target
))
1073 /* We can replace or remove a complex jump only when we have exactly
1074 two edges. Also, if we have exactly one outgoing edge, we can
1076 if (EDGE_COUNT (src
->succs
) >= 3
1077 /* Verify that all targets will be TARGET. Specifically, the
1078 edge that is not E must also go to TARGET. */
1079 || (EDGE_COUNT (src
->succs
) == 2
1080 && EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
!= target
))
1083 if (!onlyjump_p (insn
))
1085 if ((!optimize
|| reload_completed
) && tablejump_p (insn
, NULL
, NULL
))
1088 /* Avoid removing branch with side effects. */
1089 set
= single_set (insn
);
1090 if (!set
|| side_effects_p (set
))
1093 /* See if we can create the fallthru edge. */
1094 if (in_cfglayout
|| can_fallthru (src
, target
))
1097 fprintf (dump_file
, "Removing jump %i.\n", INSN_UID (insn
));
1100 /* Selectively unlink whole insn chain. */
1103 delete_insn_chain (insn
, BB_END (src
), false);
1104 remove_barriers_from_footer (src
);
1107 delete_insn_chain (insn
, PREV_INSN (BB_HEAD (target
)), false);
1110 /* If this already is simplejump, redirect it. */
1111 else if (simplejump_p (insn
))
1113 if (e
->dest
== target
)
1116 fprintf (dump_file
, "Redirecting jump %i from %i to %i.\n",
1117 INSN_UID (insn
), e
->dest
->index
, target
->index
);
1118 if (!redirect_jump (as_a
<rtx_jump_insn
*> (insn
),
1119 block_label (target
), 0))
1121 gcc_assert (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
));
1126 /* Cannot do anything for target exit block. */
1127 else if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1130 /* Or replace possibly complicated jump insn by simple jump insn. */
1133 rtx_code_label
*target_label
= block_label (target
);
1136 rtx_jump_table_data
*table
;
1138 emit_jump_insn_after_noloc (targetm
.gen_jump (target_label
), insn
);
1139 JUMP_LABEL (BB_END (src
)) = target_label
;
1140 LABEL_NUSES (target_label
)++;
1142 fprintf (dump_file
, "Replacing insn %i by jump %i\n",
1143 INSN_UID (insn
), INSN_UID (BB_END (src
)));
1146 delete_insn_chain (insn
, insn
, false);
1148 /* Recognize a tablejump that we are converting to a
1149 simple jump and remove its associated CODE_LABEL
1150 and ADDR_VEC or ADDR_DIFF_VEC. */
1151 if (tablejump_p (insn
, &label
, &table
))
1152 delete_insn_chain (label
, table
, false);
1154 barrier
= next_nonnote_nondebug_insn (BB_END (src
));
1155 if (!barrier
|| !BARRIER_P (barrier
))
1156 emit_barrier_after (BB_END (src
));
1159 if (barrier
!= NEXT_INSN (BB_END (src
)))
1161 /* Move the jump before barrier so that the notes
1162 which originally were or were created before jump table are
1163 inside the basic block. */
1164 rtx_insn
*new_insn
= BB_END (src
);
1166 update_bb_for_insn_chain (NEXT_INSN (BB_END (src
)),
1167 PREV_INSN (barrier
), src
);
1169 SET_NEXT_INSN (PREV_INSN (new_insn
)) = NEXT_INSN (new_insn
);
1170 SET_PREV_INSN (NEXT_INSN (new_insn
)) = PREV_INSN (new_insn
);
1172 SET_NEXT_INSN (new_insn
) = barrier
;
1173 SET_NEXT_INSN (PREV_INSN (barrier
)) = new_insn
;
1175 SET_PREV_INSN (new_insn
) = PREV_INSN (barrier
);
1176 SET_PREV_INSN (barrier
) = new_insn
;
1181 /* Keep only one edge out and set proper flags. */
1182 if (!single_succ_p (src
))
1184 gcc_assert (single_succ_p (src
));
1186 e
= single_succ_edge (src
);
1188 e
->flags
= EDGE_FALLTHRU
;
1192 e
->probability
= profile_probability::always ();
1194 if (e
->dest
!= target
)
1195 redirect_edge_succ (e
, target
);
1199 /* Subroutine of redirect_branch_edge that tries to patch the jump
1200 instruction INSN so that it reaches block NEW. Do this
1201 only when it originally reached block OLD. Return true if this
1202 worked or the original target wasn't OLD, return false if redirection
1206 patch_jump_insn (rtx_insn
*insn
, rtx_insn
*old_label
, basic_block new_bb
)
1208 rtx_jump_table_data
*table
;
1210 /* Recognize a tablejump and adjust all matching cases. */
1211 if (tablejump_p (insn
, NULL
, &table
))
1215 rtx_code_label
*new_label
= block_label (new_bb
);
1217 if (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1219 vec
= table
->get_labels ();
1221 for (j
= GET_NUM_ELEM (vec
) - 1; j
>= 0; --j
)
1222 if (XEXP (RTVEC_ELT (vec
, j
), 0) == old_label
)
1224 RTVEC_ELT (vec
, j
) = gen_rtx_LABEL_REF (Pmode
, new_label
);
1225 --LABEL_NUSES (old_label
);
1226 ++LABEL_NUSES (new_label
);
1229 /* Handle casesi dispatch insns. */
1230 if ((tmp
= tablejump_casesi_pattern (insn
)) != NULL_RTX
1231 && label_ref_label (XEXP (SET_SRC (tmp
), 2)) == old_label
)
1233 XEXP (SET_SRC (tmp
), 2) = gen_rtx_LABEL_REF (Pmode
,
1235 --LABEL_NUSES (old_label
);
1236 ++LABEL_NUSES (new_label
);
1239 else if ((tmp
= extract_asm_operands (PATTERN (insn
))) != NULL
)
1241 int i
, n
= ASM_OPERANDS_LABEL_LENGTH (tmp
);
1244 if (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1246 rtx_code_label
*new_label
= block_label (new_bb
);
1248 for (i
= 0; i
< n
; ++i
)
1250 rtx old_ref
= ASM_OPERANDS_LABEL (tmp
, i
);
1251 gcc_assert (GET_CODE (old_ref
) == LABEL_REF
);
1252 if (XEXP (old_ref
, 0) == old_label
)
1254 ASM_OPERANDS_LABEL (tmp
, i
)
1255 = gen_rtx_LABEL_REF (Pmode
, new_label
);
1256 --LABEL_NUSES (old_label
);
1257 ++LABEL_NUSES (new_label
);
1261 if (JUMP_LABEL (insn
) == old_label
)
1263 JUMP_LABEL (insn
) = new_label
;
1264 note
= find_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1266 remove_note (insn
, note
);
1270 note
= find_reg_note (insn
, REG_LABEL_TARGET
, old_label
);
1272 remove_note (insn
, note
);
1273 if (JUMP_LABEL (insn
) != new_label
1274 && !find_reg_note (insn
, REG_LABEL_TARGET
, new_label
))
1275 add_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1277 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, old_label
))
1279 XEXP (note
, 0) = new_label
;
1283 /* ?? We may play the games with moving the named labels from
1284 one basic block to the other in case only one computed_jump is
1286 if (computed_jump_p (insn
)
1287 /* A return instruction can't be redirected. */
1288 || returnjump_p (insn
))
1291 if (!currently_expanding_to_rtl
|| JUMP_LABEL (insn
) == old_label
)
1293 /* If the insn doesn't go where we think, we're confused. */
1294 gcc_assert (JUMP_LABEL (insn
) == old_label
);
1296 /* If the substitution doesn't succeed, die. This can happen
1297 if the back end emitted unrecognizable instructions or if
1298 target is exit block on some arches. Or for crossing
1300 if (!redirect_jump (as_a
<rtx_jump_insn
*> (insn
),
1301 block_label (new_bb
), 0))
1303 gcc_assert (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
1304 || CROSSING_JUMP_P (insn
));
1313 /* Redirect edge representing branch of (un)conditional jump or tablejump,
1316 redirect_branch_edge (edge e
, basic_block target
)
1318 rtx_insn
*old_label
= BB_HEAD (e
->dest
);
1319 basic_block src
= e
->src
;
1320 rtx_insn
*insn
= BB_END (src
);
1322 /* We can only redirect non-fallthru edges of jump insn. */
1323 if (e
->flags
& EDGE_FALLTHRU
)
1325 else if (!JUMP_P (insn
) && !currently_expanding_to_rtl
)
1328 if (!currently_expanding_to_rtl
)
1330 if (!patch_jump_insn (as_a
<rtx_jump_insn
*> (insn
), old_label
, target
))
1334 /* When expanding this BB might actually contain multiple
1335 jumps (i.e. not yet split by find_many_sub_basic_blocks).
1336 Redirect all of those that match our label. */
1337 FOR_BB_INSNS (src
, insn
)
1338 if (JUMP_P (insn
) && !patch_jump_insn (as_a
<rtx_jump_insn
*> (insn
),
1343 fprintf (dump_file
, "Edge %i->%i redirected to %i\n",
1344 e
->src
->index
, e
->dest
->index
, target
->index
);
1346 if (e
->dest
!= target
)
1347 e
= redirect_edge_succ_nodup (e
, target
);
1352 /* Called when edge E has been redirected to a new destination,
1353 in order to update the region crossing flag on the edge and
1357 fixup_partition_crossing (edge e
)
1359 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) || e
->dest
1360 == EXIT_BLOCK_PTR_FOR_FN (cfun
))
1362 /* If we redirected an existing edge, it may already be marked
1363 crossing, even though the new src is missing a reg crossing note.
1364 But make sure reg crossing note doesn't already exist before
1366 if (BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
))
1368 e
->flags
|= EDGE_CROSSING
;
1369 if (JUMP_P (BB_END (e
->src
)))
1370 CROSSING_JUMP_P (BB_END (e
->src
)) = 1;
1372 else if (BB_PARTITION (e
->src
) == BB_PARTITION (e
->dest
))
1374 e
->flags
&= ~EDGE_CROSSING
;
1375 /* Remove the section crossing note from jump at end of
1376 src if it exists, and if no other successors are
1378 if (JUMP_P (BB_END (e
->src
)) && CROSSING_JUMP_P (BB_END (e
->src
)))
1380 bool has_crossing_succ
= false;
1383 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
1385 has_crossing_succ
|= (e2
->flags
& EDGE_CROSSING
);
1386 if (has_crossing_succ
)
1389 if (!has_crossing_succ
)
1390 CROSSING_JUMP_P (BB_END (e
->src
)) = 0;
1395 /* Called when block BB has been reassigned to the cold partition,
1396 because it is now dominated by another cold block,
1397 to ensure that the region crossing attributes are updated. */
1400 fixup_new_cold_bb (basic_block bb
)
1405 /* This is called when a hot bb is found to now be dominated
1406 by a cold bb and therefore needs to become cold. Therefore,
1407 its preds will no longer be region crossing. Any non-dominating
1408 preds that were previously hot would also have become cold
1409 in the caller for the same region. Any preds that were previously
1410 region-crossing will be adjusted in fixup_partition_crossing. */
1411 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1413 fixup_partition_crossing (e
);
1416 /* Possibly need to make bb's successor edges region crossing,
1417 or remove stale region crossing. */
1418 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1420 /* We can't have fall-through edges across partition boundaries.
1421 Note that force_nonfallthru will do any necessary partition
1422 boundary fixup by calling fixup_partition_crossing itself. */
1423 if ((e
->flags
& EDGE_FALLTHRU
)
1424 && BB_PARTITION (bb
) != BB_PARTITION (e
->dest
)
1425 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1426 force_nonfallthru (e
);
1428 fixup_partition_crossing (e
);
1432 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
1433 expense of adding new instructions or reordering basic blocks.
1435 Function can be also called with edge destination equivalent to the TARGET.
1436 Then it should try the simplifications and do nothing if none is possible.
1438 Return edge representing the branch if transformation succeeded. Return NULL
1440 We still return NULL in case E already destinated TARGET and we didn't
1441 managed to simplify instruction stream. */
1444 rtl_redirect_edge_and_branch (edge e
, basic_block target
)
1447 basic_block src
= e
->src
;
1448 basic_block dest
= e
->dest
;
1450 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
1456 if ((ret
= try_redirect_by_replacing_jump (e
, target
, false)) != NULL
)
1458 df_set_bb_dirty (src
);
1459 fixup_partition_crossing (ret
);
1463 ret
= redirect_branch_edge (e
, target
);
1467 df_set_bb_dirty (src
);
1468 fixup_partition_crossing (ret
);
1472 /* Emit a barrier after BB, into the footer if we are in CFGLAYOUT mode. */
1475 emit_barrier_after_bb (basic_block bb
)
1477 rtx_barrier
*barrier
= emit_barrier_after (BB_END (bb
));
1478 gcc_assert (current_ir_type () == IR_RTL_CFGRTL
1479 || current_ir_type () == IR_RTL_CFGLAYOUT
);
1480 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
1482 rtx_insn
*insn
= unlink_insn_chain (barrier
, barrier
);
1486 rtx_insn
*footer_tail
= BB_FOOTER (bb
);
1488 while (NEXT_INSN (footer_tail
))
1489 footer_tail
= NEXT_INSN (footer_tail
);
1490 if (!BARRIER_P (footer_tail
))
1492 SET_NEXT_INSN (footer_tail
) = insn
;
1493 SET_PREV_INSN (insn
) = footer_tail
;
1497 BB_FOOTER (bb
) = insn
;
1501 /* Like force_nonfallthru below, but additionally performs redirection
1502 Used by redirect_edge_and_branch_force. JUMP_LABEL is used only
1503 when redirecting to the EXIT_BLOCK, it is either ret_rtx or
1504 simple_return_rtx, indicating which kind of returnjump to create.
1505 It should be NULL otherwise. */
1508 force_nonfallthru_and_redirect (edge e
, basic_block target
, rtx jump_label
)
1510 basic_block jump_block
, new_bb
= NULL
, src
= e
->src
;
1513 int abnormal_edge_flags
= 0;
1514 bool asm_goto_edge
= false;
1517 /* In the case the last instruction is conditional jump to the next
1518 instruction, first redirect the jump itself and then continue
1519 by creating a basic block afterwards to redirect fallthru edge. */
1520 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1521 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1522 && any_condjump_p (BB_END (e
->src
))
1523 && JUMP_LABEL (BB_END (e
->src
)) == BB_HEAD (e
->dest
))
1526 edge b
= unchecked_make_edge (e
->src
, target
, 0);
1529 redirected
= redirect_jump (as_a
<rtx_jump_insn
*> (BB_END (e
->src
)),
1530 block_label (target
), 0);
1531 gcc_assert (redirected
);
1533 note
= find_reg_note (BB_END (e
->src
), REG_BR_PROB
, NULL_RTX
);
1536 int prob
= XINT (note
, 0);
1538 b
->probability
= profile_probability::from_reg_br_prob_note (prob
);
1539 e
->probability
-= e
->probability
;
1543 if (e
->flags
& EDGE_ABNORMAL
)
1545 /* Irritating special case - fallthru edge to the same block as abnormal
1547 We can't redirect abnormal edge, but we still can split the fallthru
1548 one and create separate abnormal edge to original destination.
1549 This allows bb-reorder to make such edge non-fallthru. */
1550 gcc_assert (e
->dest
== target
);
1551 abnormal_edge_flags
= e
->flags
& ~EDGE_FALLTHRU
;
1552 e
->flags
&= EDGE_FALLTHRU
;
1556 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
1557 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1559 /* We can't redirect the entry block. Create an empty block
1560 at the start of the function which we use to add the new
1566 basic_block bb
= create_basic_block (BB_HEAD (e
->dest
), NULL
,
1567 ENTRY_BLOCK_PTR_FOR_FN (cfun
));
1568 bb
->count
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
;
1570 /* Make sure new block ends up in correct hot/cold section. */
1571 BB_COPY_PARTITION (bb
, e
->dest
);
1573 /* Change the existing edge's source to be the new block, and add
1574 a new edge from the entry block to the new block. */
1576 for (ei
= ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
);
1577 (tmp
= ei_safe_edge (ei
)); )
1581 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
->unordered_remove (ei
.index
);
1591 vec_safe_push (bb
->succs
, e
);
1592 make_single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
), bb
,
1597 /* If e->src ends with asm goto, see if any of the ASM_OPERANDS_LABELs
1598 don't point to the target or fallthru label. */
1599 if (JUMP_P (BB_END (e
->src
))
1600 && target
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1601 && (e
->flags
& EDGE_FALLTHRU
)
1602 && (note
= extract_asm_operands (PATTERN (BB_END (e
->src
)))))
1604 int i
, n
= ASM_OPERANDS_LABEL_LENGTH (note
);
1605 bool adjust_jump_target
= false;
1607 for (i
= 0; i
< n
; ++i
)
1609 if (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) == BB_HEAD (e
->dest
))
1611 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0))--;
1612 XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) = block_label (target
);
1613 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0))++;
1614 adjust_jump_target
= true;
1616 if (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) == BB_HEAD (target
))
1617 asm_goto_edge
= true;
1619 if (adjust_jump_target
)
1621 rtx_insn
*insn
= BB_END (e
->src
);
1623 rtx_insn
*old_label
= BB_HEAD (e
->dest
);
1624 rtx_insn
*new_label
= BB_HEAD (target
);
1626 if (JUMP_LABEL (insn
) == old_label
)
1628 JUMP_LABEL (insn
) = new_label
;
1629 note
= find_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1631 remove_note (insn
, note
);
1635 note
= find_reg_note (insn
, REG_LABEL_TARGET
, old_label
);
1637 remove_note (insn
, note
);
1638 if (JUMP_LABEL (insn
) != new_label
1639 && !find_reg_note (insn
, REG_LABEL_TARGET
, new_label
))
1640 add_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1642 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, old_label
))
1644 XEXP (note
, 0) = new_label
;
1648 if (EDGE_COUNT (e
->src
->succs
) >= 2 || abnormal_edge_flags
|| asm_goto_edge
)
1651 profile_count count
= e
->count ();
1652 profile_probability probability
= e
->probability
;
1653 /* Create the new structures. */
1655 /* If the old block ended with a tablejump, skip its table
1656 by searching forward from there. Otherwise start searching
1657 forward from the last instruction of the old block. */
1658 rtx_jump_table_data
*table
;
1659 if (tablejump_p (BB_END (e
->src
), NULL
, &table
))
1662 new_head
= BB_END (e
->src
);
1663 new_head
= NEXT_INSN (new_head
);
1665 jump_block
= create_basic_block (new_head
, NULL
, e
->src
);
1666 jump_block
->count
= count
;
1668 /* Make sure new block ends up in correct hot/cold section. */
1670 BB_COPY_PARTITION (jump_block
, e
->src
);
1673 new_edge
= make_edge (e
->src
, jump_block
, EDGE_FALLTHRU
);
1674 new_edge
->probability
= probability
;
1676 /* Redirect old edge. */
1677 redirect_edge_pred (e
, jump_block
);
1678 e
->probability
= profile_probability::always ();
1680 /* If e->src was previously region crossing, it no longer is
1681 and the reg crossing note should be removed. */
1682 fixup_partition_crossing (new_edge
);
1684 /* If asm goto has any label refs to target's label,
1685 add also edge from asm goto bb to target. */
1688 new_edge
->probability
/= 2;
1689 jump_block
->count
/= 2;
1690 edge new_edge2
= make_edge (new_edge
->src
, target
,
1691 e
->flags
& ~EDGE_FALLTHRU
);
1692 new_edge2
->probability
= probability
- new_edge
->probability
;
1695 new_bb
= jump_block
;
1698 jump_block
= e
->src
;
1700 loc
= e
->goto_locus
;
1701 e
->flags
&= ~EDGE_FALLTHRU
;
1702 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1704 if (jump_label
== ret_rtx
)
1705 emit_jump_insn_after_setloc (targetm
.gen_return (),
1706 BB_END (jump_block
), loc
);
1709 gcc_assert (jump_label
== simple_return_rtx
);
1710 emit_jump_insn_after_setloc (targetm
.gen_simple_return (),
1711 BB_END (jump_block
), loc
);
1713 set_return_jump_label (BB_END (jump_block
));
1717 rtx_code_label
*label
= block_label (target
);
1718 emit_jump_insn_after_setloc (targetm
.gen_jump (label
),
1719 BB_END (jump_block
), loc
);
1720 JUMP_LABEL (BB_END (jump_block
)) = label
;
1721 LABEL_NUSES (label
)++;
1724 /* We might be in cfg layout mode, and if so, the following routine will
1725 insert the barrier correctly. */
1726 emit_barrier_after_bb (jump_block
);
1727 redirect_edge_succ_nodup (e
, target
);
1729 if (abnormal_edge_flags
)
1730 make_edge (src
, target
, abnormal_edge_flags
);
1732 df_mark_solutions_dirty ();
1733 fixup_partition_crossing (e
);
1737 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1738 (and possibly create new basic block) to make edge non-fallthru.
1739 Return newly created BB or NULL if none. */
1742 rtl_force_nonfallthru (edge e
)
1744 return force_nonfallthru_and_redirect (e
, e
->dest
, NULL_RTX
);
1747 /* Redirect edge even at the expense of creating new jump insn or
1748 basic block. Return new basic block if created, NULL otherwise.
1749 Conversion must be possible. */
1752 rtl_redirect_edge_and_branch_force (edge e
, basic_block target
)
1754 if (redirect_edge_and_branch (e
, target
)
1755 || e
->dest
== target
)
1758 /* In case the edge redirection failed, try to force it to be non-fallthru
1759 and redirect newly created simplejump. */
1760 df_set_bb_dirty (e
->src
);
1761 return force_nonfallthru_and_redirect (e
, target
, NULL_RTX
);
1764 /* The given edge should potentially be a fallthru edge. If that is in
1765 fact true, delete the jump and barriers that are in the way. */
1768 rtl_tidy_fallthru_edge (edge e
)
1771 basic_block b
= e
->src
, c
= b
->next_bb
;
1773 /* ??? In a late-running flow pass, other folks may have deleted basic
1774 blocks by nopping out blocks, leaving multiple BARRIERs between here
1775 and the target label. They ought to be chastised and fixed.
1777 We can also wind up with a sequence of undeletable labels between
1778 one block and the next.
1780 So search through a sequence of barriers, labels, and notes for
1781 the head of block C and assert that we really do fall through. */
1783 for (q
= NEXT_INSN (BB_END (b
)); q
!= BB_HEAD (c
); q
= NEXT_INSN (q
))
1784 if (NONDEBUG_INSN_P (q
))
1787 /* Remove what will soon cease being the jump insn from the source block.
1788 If block B consisted only of this single jump, turn it into a deleted
1793 && (any_uncondjump_p (q
)
1794 || single_succ_p (b
)))
1797 rtx_jump_table_data
*table
;
1799 if (tablejump_p (q
, &label
, &table
))
1801 /* The label is likely mentioned in some instruction before
1802 the tablejump and might not be DCEd, so turn it into
1803 a note instead and move before the tablejump that is going to
1805 const char *name
= LABEL_NAME (label
);
1806 PUT_CODE (label
, NOTE
);
1807 NOTE_KIND (label
) = NOTE_INSN_DELETED_LABEL
;
1808 NOTE_DELETED_LABEL_NAME (label
) = name
;
1809 reorder_insns (label
, label
, PREV_INSN (q
));
1810 delete_insn (table
);
1815 /* Unconditional jumps with side-effects (i.e. which we can't just delete
1816 together with the barrier) should never have a fallthru edge. */
1817 else if (JUMP_P (q
) && any_uncondjump_p (q
))
1820 /* Selectively unlink the sequence. */
1821 if (q
!= PREV_INSN (BB_HEAD (c
)))
1822 delete_insn_chain (NEXT_INSN (q
), PREV_INSN (BB_HEAD (c
)), false);
1824 e
->flags
|= EDGE_FALLTHRU
;
1827 /* Should move basic block BB after basic block AFTER. NIY. */
1830 rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED
,
1831 basic_block after ATTRIBUTE_UNUSED
)
1836 /* Locate the last bb in the same partition as START_BB. */
1839 last_bb_in_partition (basic_block start_bb
)
1842 FOR_BB_BETWEEN (bb
, start_bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
1844 if (BB_PARTITION (start_bb
) != BB_PARTITION (bb
->next_bb
))
1847 /* Return bb before the exit block. */
1851 /* Split a (typically critical) edge. Return the new block.
1852 The edge must not be abnormal.
1854 ??? The code generally expects to be called on critical edges.
1855 The case of a block ending in an unconditional jump to a
1856 block with multiple predecessors is not handled optimally. */
1859 rtl_split_edge (edge edge_in
)
1861 basic_block bb
, new_bb
;
1864 /* Abnormal edges cannot be split. */
1865 gcc_assert (!(edge_in
->flags
& EDGE_ABNORMAL
));
1867 /* We are going to place the new block in front of edge destination.
1868 Avoid existence of fallthru predecessors. */
1869 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1871 edge e
= find_fallthru_edge (edge_in
->dest
->preds
);
1874 force_nonfallthru (e
);
1877 /* Create the basic block note. */
1878 if (edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1879 before
= BB_HEAD (edge_in
->dest
);
1883 /* If this is a fall through edge to the exit block, the blocks might be
1884 not adjacent, and the right place is after the source. */
1885 if ((edge_in
->flags
& EDGE_FALLTHRU
)
1886 && edge_in
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1888 before
= NEXT_INSN (BB_END (edge_in
->src
));
1889 bb
= create_basic_block (before
, NULL
, edge_in
->src
);
1890 BB_COPY_PARTITION (bb
, edge_in
->src
);
1894 if (edge_in
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1896 bb
= create_basic_block (before
, NULL
, edge_in
->dest
->prev_bb
);
1897 BB_COPY_PARTITION (bb
, edge_in
->dest
);
1901 basic_block after
= edge_in
->dest
->prev_bb
;
1902 /* If this is post-bb reordering, and the edge crosses a partition
1903 boundary, the new block needs to be inserted in the bb chain
1904 at the end of the src partition (since we put the new bb into
1905 that partition, see below). Otherwise we may end up creating
1906 an extra partition crossing in the chain, which is illegal.
1907 It can't go after the src, because src may have a fall-through
1908 to a different block. */
1909 if (crtl
->bb_reorder_complete
1910 && (edge_in
->flags
& EDGE_CROSSING
))
1912 after
= last_bb_in_partition (edge_in
->src
);
1913 before
= get_last_bb_insn (after
);
1914 /* The instruction following the last bb in partition should
1915 be a barrier, since it cannot end in a fall-through. */
1916 gcc_checking_assert (BARRIER_P (before
));
1917 before
= NEXT_INSN (before
);
1919 bb
= create_basic_block (before
, NULL
, after
);
1920 /* Put the split bb into the src partition, to avoid creating
1921 a situation where a cold bb dominates a hot bb, in the case
1922 where src is cold and dest is hot. The src will dominate
1923 the new bb (whereas it might not have dominated dest). */
1924 BB_COPY_PARTITION (bb
, edge_in
->src
);
1928 make_single_succ_edge (bb
, edge_in
->dest
, EDGE_FALLTHRU
);
1930 /* Can't allow a region crossing edge to be fallthrough. */
1931 if (BB_PARTITION (bb
) != BB_PARTITION (edge_in
->dest
)
1932 && edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1934 new_bb
= force_nonfallthru (single_succ_edge (bb
));
1935 gcc_assert (!new_bb
);
1938 /* For non-fallthru edges, we must adjust the predecessor's
1939 jump instruction to target our new block. */
1940 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1942 edge redirected
= redirect_edge_and_branch (edge_in
, bb
);
1943 gcc_assert (redirected
);
1947 if (edge_in
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1949 /* For asm goto even splitting of fallthru edge might
1950 need insn patching, as other labels might point to the
1952 rtx_insn
*last
= BB_END (edge_in
->src
);
1955 && edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1956 && (extract_asm_operands (PATTERN (last
))
1957 || JUMP_LABEL (last
) == before
)
1958 && patch_jump_insn (last
, before
, bb
))
1959 df_set_bb_dirty (edge_in
->src
);
1961 redirect_edge_succ (edge_in
, bb
);
1967 /* Queue instructions for insertion on an edge between two basic blocks.
1968 The new instructions and basic blocks (if any) will not appear in the
1969 CFG until commit_edge_insertions is called. If there are already
1970 queued instructions on the edge, PATTERN is appended to them. */
1973 insert_insn_on_edge (rtx pattern
, edge e
)
1975 /* We cannot insert instructions on an abnormal critical edge.
1976 It will be easier to find the culprit if we die now. */
1977 gcc_assert (!((e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
)));
1979 if (e
->insns
.r
== NULL_RTX
)
1982 push_to_sequence (e
->insns
.r
);
1984 emit_insn (pattern
);
1986 e
->insns
.r
= get_insns ();
1990 /* Like insert_insn_on_edge, but if there are already queued instructions
1991 on the edge, PATTERN is prepended to them. */
1994 prepend_insn_to_edge (rtx pattern
, edge e
)
1996 /* We cannot insert instructions on an abnormal critical edge.
1997 It will be easier to find the culprit if we die now. */
1998 gcc_assert (!((e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
)));
2002 emit_insn (pattern
);
2003 emit_insn (e
->insns
.r
);
2005 e
->insns
.r
= get_insns ();
2009 /* Update the CFG for the instructions queued on edge E. */
2012 commit_one_edge_insertion (edge e
)
2014 rtx_insn
*before
= NULL
, *after
= NULL
, *insns
, *tmp
, *last
;
2017 /* Pull the insns off the edge now since the edge might go away. */
2021 /* Allow the sequence to contain internal jumps, such as a memcpy loop
2022 or an allocation loop. If such a sequence is emitted during RTL
2023 expansion, we'll create the appropriate basic blocks later,
2024 at the end of the pass. But if such a sequence is emitted after
2025 initial expansion, we'll need to find the subblocks ourselves. */
2026 bool contains_jump
= false;
2027 if (!currently_expanding_to_rtl
)
2028 for (rtx_insn
*insn
= insns
; insn
; insn
= NEXT_INSN (insn
))
2031 rebuild_jump_labels_chain (insns
);
2032 contains_jump
= true;
2036 /* Figure out where to put these insns. If the destination has
2037 one predecessor, insert there. Except for the exit block. */
2038 if (single_pred_p (e
->dest
) && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
2042 /* Get the location correct wrt a code label, and "nice" wrt
2043 a basic block note, and before everything else. */
2046 tmp
= NEXT_INSN (tmp
);
2047 if (NOTE_INSN_BASIC_BLOCK_P (tmp
))
2048 tmp
= NEXT_INSN (tmp
);
2049 if (tmp
== BB_HEAD (bb
))
2052 after
= PREV_INSN (tmp
);
2054 after
= get_last_insn ();
2057 /* If the source has one successor and the edge is not abnormal,
2058 insert there. Except for the entry block.
2059 Don't do this if the predecessor ends in a jump other than
2060 unconditional simple jump. E.g. for asm goto that points all
2061 its labels at the fallthru basic block, we can't insert instructions
2062 before the asm goto, as the asm goto can have various of side effects,
2063 and can't emit instructions after the asm goto, as it must end
2065 else if ((e
->flags
& EDGE_ABNORMAL
) == 0
2066 && single_succ_p (e
->src
)
2067 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2068 && (!JUMP_P (BB_END (e
->src
))
2069 || simplejump_p (BB_END (e
->src
))))
2073 /* It is possible to have a non-simple jump here. Consider a target
2074 where some forms of unconditional jumps clobber a register. This
2075 happens on the fr30 for example.
2077 We know this block has a single successor, so we can just emit
2078 the queued insns before the jump. */
2079 if (JUMP_P (BB_END (bb
)))
2080 before
= BB_END (bb
);
2083 /* We'd better be fallthru, or we've lost track of what's what. */
2084 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
2086 after
= BB_END (bb
);
2090 /* Otherwise we must split the edge. */
2093 bb
= split_edge (e
);
2095 /* If E crossed a partition boundary, we needed to make bb end in
2096 a region-crossing jump, even though it was originally fallthru. */
2097 if (JUMP_P (BB_END (bb
)))
2098 before
= BB_END (bb
);
2100 after
= BB_END (bb
);
2103 /* Now that we've found the spot, do the insertion. */
2106 emit_insn_before_noloc (insns
, before
, bb
);
2107 last
= prev_nonnote_insn (before
);
2110 last
= emit_insn_after_noloc (insns
, after
, bb
);
2112 if (returnjump_p (last
))
2114 /* ??? Remove all outgoing edges from BB and add one for EXIT.
2115 This is not currently a problem because this only happens
2116 for the (single) epilogue, which already has a fallthru edge
2119 e
= single_succ_edge (bb
);
2120 gcc_assert (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
2121 && single_succ_p (bb
) && (e
->flags
& EDGE_FALLTHRU
));
2123 e
->flags
&= ~EDGE_FALLTHRU
;
2124 emit_barrier_after (last
);
2127 delete_insn (before
);
2130 /* Sequences inserted after RTL expansion are expected to be SESE,
2131 with only internal branches allowed. If the sequence jumps outside
2132 itself then we do not know how to add the associated edges here. */
2133 gcc_assert (!JUMP_P (last
) || currently_expanding_to_rtl
);
2136 find_sub_basic_blocks (bb
);
2139 /* Update the CFG for all queued instructions. */
2142 commit_edge_insertions (void)
2146 /* Optimization passes that invoke this routine can cause hot blocks
2147 previously reached by both hot and cold blocks to become dominated only
2148 by cold blocks. This will cause the verification below to fail,
2149 and lead to now cold code in the hot section. In some cases this
2150 may only be visible after newly unreachable blocks are deleted,
2151 which will be done by fixup_partitions. */
2152 fixup_partitions ();
2154 if (!currently_expanding_to_rtl
)
2155 checking_verify_flow_info ();
2157 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
2158 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
2163 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2166 if (currently_expanding_to_rtl
)
2167 rebuild_jump_labels_chain (e
->insns
.r
);
2168 commit_one_edge_insertion (e
);
2174 /* Print out RTL-specific basic block information (live information
2175 at start and end with TDF_DETAILS). FLAGS are the TDF_* masks
2176 documented in dumpfile.h. */
2179 rtl_dump_bb (FILE *outf
, basic_block bb
, int indent
, dump_flags_t flags
)
2183 s_indent
= (char *) alloca ((size_t) indent
+ 1);
2184 memset (s_indent
, ' ', (size_t) indent
);
2185 s_indent
[indent
] = '\0';
2187 if (df
&& (flags
& TDF_DETAILS
))
2189 df_dump_top (bb
, outf
);
2193 if (bb
->index
!= ENTRY_BLOCK
&& bb
->index
!= EXIT_BLOCK
2194 && rtl_bb_info_initialized_p (bb
))
2196 rtx_insn
*last
= BB_END (bb
);
2198 last
= NEXT_INSN (last
);
2199 for (rtx_insn
*insn
= BB_HEAD (bb
); insn
!= last
; insn
= NEXT_INSN (insn
))
2201 if (flags
& TDF_DETAILS
)
2202 df_dump_insn_top (insn
, outf
);
2203 if (! (flags
& TDF_SLIM
))
2204 print_rtl_single (outf
, insn
);
2206 dump_insn_slim (outf
, insn
);
2207 if (flags
& TDF_DETAILS
)
2208 df_dump_insn_bottom (insn
, outf
);
2212 if (df
&& (flags
& TDF_DETAILS
))
2214 df_dump_bottom (bb
, outf
);
2220 /* Like dump_function_to_file, but for RTL. Print out dataflow information
2221 for the start of each basic block. FLAGS are the TDF_* masks documented
2225 print_rtl_with_bb (FILE *outf
, const rtx_insn
*rtx_first
, dump_flags_t flags
)
2227 const rtx_insn
*tmp_rtx
;
2229 fprintf (outf
, "(nil)\n");
2232 enum bb_state
{ NOT_IN_BB
, IN_ONE_BB
, IN_MULTIPLE_BB
};
2233 int max_uid
= get_max_uid ();
2234 basic_block
*start
= XCNEWVEC (basic_block
, max_uid
);
2235 basic_block
*end
= XCNEWVEC (basic_block
, max_uid
);
2236 enum bb_state
*in_bb_p
= XCNEWVEC (enum bb_state
, max_uid
);
2239 /* After freeing the CFG, we still have BLOCK_FOR_INSN set on most
2240 insns, but the CFG is not maintained so the basic block info
2241 is not reliable. Therefore it's omitted from the dumps. */
2242 if (! (cfun
->curr_properties
& PROP_cfg
))
2243 flags
&= ~TDF_BLOCKS
;
2246 df_dump_start (outf
);
2248 if (cfun
->curr_properties
& PROP_cfg
)
2250 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2254 start
[INSN_UID (BB_HEAD (bb
))] = bb
;
2255 end
[INSN_UID (BB_END (bb
))] = bb
;
2256 if (flags
& TDF_BLOCKS
)
2258 for (x
= BB_HEAD (bb
); x
!= NULL_RTX
; x
= NEXT_INSN (x
))
2260 enum bb_state state
= IN_MULTIPLE_BB
;
2262 if (in_bb_p
[INSN_UID (x
)] == NOT_IN_BB
)
2264 in_bb_p
[INSN_UID (x
)] = state
;
2266 if (x
== BB_END (bb
))
2273 for (tmp_rtx
= rtx_first
; tmp_rtx
!= NULL
; tmp_rtx
= NEXT_INSN (tmp_rtx
))
2275 if (flags
& TDF_BLOCKS
)
2277 bb
= start
[INSN_UID (tmp_rtx
)];
2280 dump_bb_info (outf
, bb
, 0, dump_flags
, true, false);
2281 if (df
&& (flags
& TDF_DETAILS
))
2282 df_dump_top (bb
, outf
);
2285 if (in_bb_p
[INSN_UID (tmp_rtx
)] == NOT_IN_BB
2286 && !NOTE_P (tmp_rtx
)
2287 && !BARRIER_P (tmp_rtx
))
2288 fprintf (outf
, ";; Insn is not within a basic block\n");
2289 else if (in_bb_p
[INSN_UID (tmp_rtx
)] == IN_MULTIPLE_BB
)
2290 fprintf (outf
, ";; Insn is in multiple basic blocks\n");
2293 if (flags
& TDF_DETAILS
)
2294 df_dump_insn_top (tmp_rtx
, outf
);
2295 if (! (flags
& TDF_SLIM
))
2296 print_rtl_single (outf
, tmp_rtx
);
2298 dump_insn_slim (outf
, tmp_rtx
);
2299 if (flags
& TDF_DETAILS
)
2300 df_dump_insn_bottom (tmp_rtx
, outf
);
2302 bb
= end
[INSN_UID (tmp_rtx
)];
2305 if (flags
& TDF_BLOCKS
)
2307 dump_bb_info (outf
, bb
, 0, dump_flags
, false, true);
2308 if (df
&& (flags
& TDF_DETAILS
))
2309 df_dump_bottom (bb
, outf
);
2312 /* Emit a hint if the fallthrough target of current basic block
2313 isn't the one placed right next. */
2314 else if (EDGE_COUNT (bb
->succs
) > 0)
2316 gcc_assert (BB_END (bb
) == tmp_rtx
);
2317 const rtx_insn
*ninsn
= NEXT_INSN (tmp_rtx
);
2318 /* Bypass intervening deleted-insn notes and debug insns. */
2320 && !NONDEBUG_INSN_P (ninsn
)
2321 && !start
[INSN_UID (ninsn
)])
2322 ninsn
= NEXT_INSN (ninsn
);
2323 edge e
= find_fallthru_edge (bb
->succs
);
2326 basic_block dest
= e
->dest
;
2327 if (start
[INSN_UID (ninsn
)] != dest
)
2328 fprintf (outf
, "%s ; pc falls through to BB %d\n",
2329 print_rtx_head
, dest
->index
);
2341 /* Update the branch probability of BB if a REG_BR_PROB is present. */
2344 update_br_prob_note (basic_block bb
)
2347 note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
);
2348 if (!JUMP_P (BB_END (bb
)) || !BRANCH_EDGE (bb
)->probability
.initialized_p ())
2352 rtx
*note_link
, this_rtx
;
2354 note_link
= ®_NOTES (BB_END (bb
));
2355 for (this_rtx
= *note_link
; this_rtx
; this_rtx
= XEXP (this_rtx
, 1))
2356 if (this_rtx
== note
)
2358 *note_link
= XEXP (this_rtx
, 1);
2365 || XINT (note
, 0) == BRANCH_EDGE (bb
)->probability
.to_reg_br_prob_note ())
2367 XINT (note
, 0) = BRANCH_EDGE (bb
)->probability
.to_reg_br_prob_note ();
2370 /* Get the last insn associated with block BB (that includes barriers and
2371 tablejumps after BB). */
2373 get_last_bb_insn (basic_block bb
)
2375 rtx_jump_table_data
*table
;
2377 rtx_insn
*end
= BB_END (bb
);
2379 /* Include any jump table following the basic block. */
2380 if (tablejump_p (end
, NULL
, &table
))
2383 /* Include any barriers that may follow the basic block. */
2384 tmp
= next_nonnote_nondebug_insn_bb (end
);
2385 while (tmp
&& BARRIER_P (tmp
))
2388 tmp
= next_nonnote_nondebug_insn_bb (end
);
2394 /* Add all BBs reachable from entry via hot paths into the SET. */
2397 find_bbs_reachable_by_hot_paths (hash_set
<basic_block
> *set
)
2399 auto_vec
<basic_block
, 64> worklist
;
2401 set
->add (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
2402 worklist
.safe_push (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
2404 while (worklist
.length () > 0)
2406 basic_block bb
= worklist
.pop ();
2410 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2411 if (BB_PARTITION (e
->dest
) != BB_COLD_PARTITION
2412 && !set
->add (e
->dest
))
2413 worklist
.safe_push (e
->dest
);
2417 /* Sanity check partition hotness to ensure that basic blocks in
2418 Â the cold partition don't dominate basic blocks in the hot partition.
2419 If FLAG_ONLY is true, report violations as errors. Otherwise
2420 re-mark the dominated blocks as cold, since this is run after
2421 cfg optimizations that may make hot blocks previously reached
2422 by both hot and cold blocks now only reachable along cold paths. */
2424 static auto_vec
<basic_block
>
2425 find_partition_fixes (bool flag_only
)
2428 auto_vec
<basic_block
> bbs_to_fix
;
2429 hash_set
<basic_block
> set
;
2431 /* Callers check this. */
2432 gcc_checking_assert (crtl
->has_bb_partition
);
2434 find_bbs_reachable_by_hot_paths (&set
);
2436 FOR_EACH_BB_FN (bb
, cfun
)
2437 if (!set
.contains (bb
)
2438 && BB_PARTITION (bb
) != BB_COLD_PARTITION
)
2441 error ("non-cold basic block %d reachable only "
2442 "by paths crossing the cold partition", bb
->index
);
2444 BB_SET_PARTITION (bb
, BB_COLD_PARTITION
);
2445 bbs_to_fix
.safe_push (bb
);
2451 /* Perform cleanup on the hot/cold bb partitioning after optimization
2452 passes that modify the cfg. */
2455 fixup_partitions (void)
2457 if (!crtl
->has_bb_partition
)
2460 /* Delete any blocks that became unreachable and weren't
2461 already cleaned up, for example during edge forwarding
2462 and convert_jumps_to_returns. This will expose more
2463 opportunities for fixing the partition boundaries here.
2464 Also, the calculation of the dominance graph during verification
2465 will assert if there are unreachable nodes. */
2466 delete_unreachable_blocks ();
2468 /* If there are partitions, do a sanity check on them: A basic block in
2469 Â a cold partition cannot dominate a basic block in a hot partition.
2470 Fixup any that now violate this requirement, as a result of edge
2471 forwarding and unreachable block deletion. Â */
2472 auto_vec
<basic_block
> bbs_to_fix
= find_partition_fixes (false);
2474 /* Do the partition fixup after all necessary blocks have been converted to
2475 cold, so that we only update the region crossings the minimum number of
2476 places, which can require forcing edges to be non fallthru. */
2477 if (! bbs_to_fix
.is_empty ())
2481 basic_block bb
= bbs_to_fix
.pop ();
2482 fixup_new_cold_bb (bb
);
2484 while (! bbs_to_fix
.is_empty ());
2486 /* Fix up hot cold block grouping if needed. */
2487 if (crtl
->bb_reorder_complete
&& current_ir_type () == IR_RTL_CFGRTL
)
2489 basic_block bb
, first
= NULL
, second
= NULL
;
2490 int current_partition
= BB_UNPARTITIONED
;
2492 FOR_EACH_BB_FN (bb
, cfun
)
2494 if (current_partition
!= BB_UNPARTITIONED
2495 && BB_PARTITION (bb
) != current_partition
)
2499 else if (second
== NULL
)
2503 /* If we switch partitions for the 3rd, 5th etc. time,
2504 move bbs first (inclusive) .. second (exclusive) right
2506 basic_block prev_first
= first
->prev_bb
;
2507 basic_block prev_second
= second
->prev_bb
;
2508 basic_block prev_bb
= bb
->prev_bb
;
2509 prev_first
->next_bb
= second
;
2510 second
->prev_bb
= prev_first
;
2511 prev_second
->next_bb
= bb
;
2512 bb
->prev_bb
= prev_second
;
2513 prev_bb
->next_bb
= first
;
2514 first
->prev_bb
= prev_bb
;
2515 rtx_insn
*prev_first_insn
= PREV_INSN (BB_HEAD (first
));
2516 rtx_insn
*prev_second_insn
2517 = PREV_INSN (BB_HEAD (second
));
2518 rtx_insn
*prev_bb_insn
= PREV_INSN (BB_HEAD (bb
));
2519 SET_NEXT_INSN (prev_first_insn
) = BB_HEAD (second
);
2520 SET_PREV_INSN (BB_HEAD (second
)) = prev_first_insn
;
2521 SET_NEXT_INSN (prev_second_insn
) = BB_HEAD (bb
);
2522 SET_PREV_INSN (BB_HEAD (bb
)) = prev_second_insn
;
2523 SET_NEXT_INSN (prev_bb_insn
) = BB_HEAD (first
);
2524 SET_PREV_INSN (BB_HEAD (first
)) = prev_bb_insn
;
2528 current_partition
= BB_PARTITION (bb
);
2530 gcc_assert (!second
);
2535 /* Verify, in the basic block chain, that there is at most one switch
2536 between hot/cold partitions. This condition will not be true until
2537 after reorder_basic_blocks is called. */
2540 verify_hot_cold_block_grouping (void)
2544 bool switched_sections
= false;
2545 int current_partition
= BB_UNPARTITIONED
;
2547 /* Even after bb reordering is complete, we go into cfglayout mode
2548 again (in compgoto). Ensure we don't call this before going back
2549 into linearized RTL when any layout fixes would have been committed. */
2550 if (!crtl
->bb_reorder_complete
2551 || current_ir_type () != IR_RTL_CFGRTL
)
2554 FOR_EACH_BB_FN (bb
, cfun
)
2556 if (current_partition
!= BB_UNPARTITIONED
2557 && BB_PARTITION (bb
) != current_partition
)
2559 if (switched_sections
)
2561 error ("multiple hot/cold transitions found (bb %i)",
2566 switched_sections
= true;
2568 if (!crtl
->has_bb_partition
)
2569 error ("partition found but function partition flag not set");
2571 current_partition
= BB_PARTITION (bb
);
2578 /* Perform several checks on the edges out of each block, such as
2579 the consistency of the branch probabilities, the correctness
2580 of hot/cold partition crossing edges, and the number of expected
2581 successor edges. Also verify that the dominance relationship
2582 between hot/cold blocks is sane. */
2585 rtl_verify_edges (void)
2590 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2592 int n_fallthru
= 0, n_branch
= 0, n_abnormal_call
= 0, n_sibcall
= 0;
2593 int n_eh
= 0, n_abnormal
= 0;
2594 edge e
, fallthru
= NULL
;
2597 bool has_crossing_edge
= false;
2599 if (JUMP_P (BB_END (bb
))
2600 && (note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
))
2601 && EDGE_COUNT (bb
->succs
) >= 2
2602 && any_condjump_p (BB_END (bb
)))
2604 if (!BRANCH_EDGE (bb
)->probability
.initialized_p ())
2606 if (profile_status_for_fn (cfun
) != PROFILE_ABSENT
)
2608 error ("verify_flow_info: "
2609 "REG_BR_PROB is set but cfg probability is not");
2613 else if (XINT (note
, 0)
2614 != BRANCH_EDGE (bb
)->probability
.to_reg_br_prob_note ()
2615 && profile_status_for_fn (cfun
) != PROFILE_ABSENT
)
2617 error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i",
2619 BRANCH_EDGE (bb
)->probability
.to_reg_br_prob_note ());
2624 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2628 if (e
->flags
& EDGE_FALLTHRU
)
2629 n_fallthru
++, fallthru
= e
;
2631 is_crossing
= (BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
)
2632 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2633 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
2634 has_crossing_edge
|= is_crossing
;
2635 if (e
->flags
& EDGE_CROSSING
)
2639 error ("EDGE_CROSSING incorrectly set across same section");
2642 if (e
->flags
& EDGE_FALLTHRU
)
2644 error ("fallthru edge crosses section boundary in bb %i",
2648 if (e
->flags
& EDGE_EH
)
2650 error ("EH edge crosses section boundary in bb %i",
2654 if (JUMP_P (BB_END (bb
)) && !CROSSING_JUMP_P (BB_END (bb
)))
2656 error ("No region crossing jump at section boundary in bb %i",
2661 else if (is_crossing
)
2663 error ("EDGE_CROSSING missing across section boundary");
2667 if ((e
->flags
& ~(EDGE_DFS_BACK
2669 | EDGE_IRREDUCIBLE_LOOP
2672 | EDGE_PRESERVE
)) == 0)
2675 if (e
->flags
& EDGE_ABNORMAL_CALL
)
2678 if (e
->flags
& EDGE_SIBCALL
)
2681 if (e
->flags
& EDGE_EH
)
2684 if (e
->flags
& EDGE_ABNORMAL
)
2688 if (!has_crossing_edge
2689 && JUMP_P (BB_END (bb
))
2690 && CROSSING_JUMP_P (BB_END (bb
)))
2692 print_rtl_with_bb (stderr
, get_insns (), TDF_BLOCKS
| TDF_DETAILS
);
2693 error ("Region crossing jump across same section in bb %i",
2698 if (n_eh
&& !find_reg_note (BB_END (bb
), REG_EH_REGION
, NULL_RTX
))
2700 error ("missing REG_EH_REGION note at the end of bb %i", bb
->index
);
2705 error ("too many exception handling edges in bb %i", bb
->index
);
2709 && (!JUMP_P (BB_END (bb
))
2710 || (n_branch
> 1 && (any_uncondjump_p (BB_END (bb
))
2711 || any_condjump_p (BB_END (bb
))))))
2713 error ("too many outgoing branch edges from bb %i", bb
->index
);
2716 if (n_fallthru
&& any_uncondjump_p (BB_END (bb
)))
2718 error ("fallthru edge after unconditional jump in bb %i", bb
->index
);
2721 if (n_branch
!= 1 && any_uncondjump_p (BB_END (bb
)))
2723 error ("wrong number of branch edges after unconditional jump"
2724 " in bb %i", bb
->index
);
2727 if (n_branch
!= 1 && any_condjump_p (BB_END (bb
))
2728 && JUMP_LABEL (BB_END (bb
)) != BB_HEAD (fallthru
->dest
))
2730 error ("wrong amount of branch edges after conditional jump"
2731 " in bb %i", bb
->index
);
2734 if (n_abnormal_call
&& !CALL_P (BB_END (bb
)))
2736 error ("abnormal call edges for non-call insn in bb %i", bb
->index
);
2739 if (n_sibcall
&& !CALL_P (BB_END (bb
)))
2741 error ("sibcall edges for non-call insn in bb %i", bb
->index
);
2744 if (n_abnormal
> n_eh
2745 && !(CALL_P (BB_END (bb
))
2746 && n_abnormal
== n_abnormal_call
+ n_sibcall
)
2747 && (!JUMP_P (BB_END (bb
))
2748 || any_condjump_p (BB_END (bb
))
2749 || any_uncondjump_p (BB_END (bb
))))
2751 error ("abnormal edges for no purpose in bb %i", bb
->index
);
2756 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2759 has_eh
= (e
->flags
& EDGE_EH
);
2760 if ((e
->flags
& EDGE_EH
) == has_eh
)
2762 error ("EH incoming edge mixed with non-EH incoming edges "
2763 "in bb %i", bb
->index
);
2769 /* If there are partitions, do a sanity check on them: A basic block in
2770 Â a cold partition cannot dominate a basic block in a hot partition. Â */
2771 if (crtl
->has_bb_partition
&& !err
2772 && current_ir_type () == IR_RTL_CFGLAYOUT
)
2774 auto_vec
<basic_block
> bbs_to_fix
= find_partition_fixes (true);
2775 err
= !bbs_to_fix
.is_empty ();
2782 /* Checks on the instructions within blocks. Currently checks that each
2783 block starts with a basic block note, and that basic block notes and
2784 control flow jumps are not found in the middle of the block. */
2787 rtl_verify_bb_insns (void)
2793 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2795 /* Now check the header of basic
2796 block. It ought to contain optional CODE_LABEL followed
2797 by NOTE_BASIC_BLOCK. */
2801 if (BB_END (bb
) == x
)
2803 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2811 if (!NOTE_INSN_BASIC_BLOCK_P (x
) || NOTE_BASIC_BLOCK (x
) != bb
)
2813 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2818 if (BB_END (bb
) == x
)
2819 /* Do checks for empty blocks here. */
2822 for (x
= NEXT_INSN (x
); x
; x
= NEXT_INSN (x
))
2824 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2826 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
2827 INSN_UID (x
), bb
->index
);
2831 if (x
== BB_END (bb
))
2834 if (control_flow_insn_p (x
))
2836 error ("in basic block %d:", bb
->index
);
2837 fatal_insn ("flow control insn inside a basic block", x
);
2846 /* Verify that block pointers for instructions in basic blocks, headers and
2847 footers are set appropriately. */
2850 rtl_verify_bb_pointers (void)
2855 /* Check the general integrity of the basic blocks. */
2856 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2860 if (!(bb
->flags
& BB_RTL
))
2862 error ("BB_RTL flag not set for block %d", bb
->index
);
2866 FOR_BB_INSNS (bb
, insn
)
2867 if (BLOCK_FOR_INSN (insn
) != bb
)
2869 error ("insn %d basic block pointer is %d, should be %d",
2871 BLOCK_FOR_INSN (insn
) ? BLOCK_FOR_INSN (insn
)->index
: 0,
2876 for (insn
= BB_HEADER (bb
); insn
; insn
= NEXT_INSN (insn
))
2877 if (!BARRIER_P (insn
)
2878 && BLOCK_FOR_INSN (insn
) != NULL
)
2880 error ("insn %d in header of bb %d has non-NULL basic block",
2881 INSN_UID (insn
), bb
->index
);
2884 for (insn
= BB_FOOTER (bb
); insn
; insn
= NEXT_INSN (insn
))
2885 if (!BARRIER_P (insn
)
2886 && BLOCK_FOR_INSN (insn
) != NULL
)
2888 error ("insn %d in footer of bb %d has non-NULL basic block",
2889 INSN_UID (insn
), bb
->index
);
2898 /* Verify the CFG and RTL consistency common for both underlying RTL and
2901 Currently it does following checks:
2903 - overlapping of basic blocks
2904 - insns with wrong BLOCK_FOR_INSN pointers
2905 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
2906 - tails of basic blocks (ensure that boundary is necessary)
2907 - scans body of the basic block for JUMP_INSN, CODE_LABEL
2908 and NOTE_INSN_BASIC_BLOCK
2909 - verify that no fall_thru edge crosses hot/cold partition boundaries
2910 - verify that there are no pending RTL branch predictions
2911 - verify that hot blocks are not dominated by cold blocks
2913 In future it can be extended check a lot of other stuff as well
2914 (reachability of basic blocks, life information, etc. etc.). */
2917 rtl_verify_flow_info_1 (void)
2921 if (rtl_verify_bb_pointers ())
2924 if (rtl_verify_bb_insns ())
2927 if (rtl_verify_edges ())
2933 /* Walk the instruction chain and verify that bb head/end pointers
2934 are correct, and that instructions are in exactly one bb and have
2935 correct block pointers. */
2938 rtl_verify_bb_insn_chain (void)
2943 rtx_insn
*last_head
= get_last_insn ();
2944 basic_block
*bb_info
;
2945 const int max_uid
= get_max_uid ();
2947 bb_info
= XCNEWVEC (basic_block
, max_uid
);
2949 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2951 rtx_insn
*head
= BB_HEAD (bb
);
2952 rtx_insn
*end
= BB_END (bb
);
2954 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2956 /* Verify the end of the basic block is in the INSN chain. */
2960 /* And that the code outside of basic blocks has NULL bb field. */
2962 && BLOCK_FOR_INSN (x
) != NULL
)
2964 error ("insn %d outside of basic blocks has non-NULL bb field",
2972 error ("end insn %d for block %d not found in the insn stream",
2973 INSN_UID (end
), bb
->index
);
2977 /* Work backwards from the end to the head of the basic block
2978 to verify the head is in the RTL chain. */
2979 for (; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2981 /* While walking over the insn chain, verify insns appear
2982 in only one basic block. */
2983 if (bb_info
[INSN_UID (x
)] != NULL
)
2985 error ("insn %d is in multiple basic blocks (%d and %d)",
2986 INSN_UID (x
), bb
->index
, bb_info
[INSN_UID (x
)]->index
);
2990 bb_info
[INSN_UID (x
)] = bb
;
2997 error ("head insn %d for block %d not found in the insn stream",
2998 INSN_UID (head
), bb
->index
);
3002 last_head
= PREV_INSN (x
);
3005 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
3007 /* Check that the code before the first basic block has NULL
3010 && BLOCK_FOR_INSN (x
) != NULL
)
3012 error ("insn %d outside of basic blocks has non-NULL bb field",
3022 /* Verify that fallthru edges point to adjacent blocks in layout order and
3023 that barriers exist after non-fallthru blocks. */
3026 rtl_verify_fallthru (void)
3031 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
3035 e
= find_fallthru_edge (bb
->succs
);
3040 /* Ensure existence of barrier in BB with no fallthru edges. */
3041 for (insn
= NEXT_INSN (BB_END (bb
)); ; insn
= NEXT_INSN (insn
))
3043 if (!insn
|| NOTE_INSN_BASIC_BLOCK_P (insn
))
3045 error ("missing barrier after block %i", bb
->index
);
3049 if (BARRIER_P (insn
))
3053 else if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
3054 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3058 if (e
->src
->next_bb
!= e
->dest
)
3061 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
3062 e
->src
->index
, e
->dest
->index
);
3066 for (insn
= NEXT_INSN (BB_END (e
->src
)); insn
!= BB_HEAD (e
->dest
);
3067 insn
= NEXT_INSN (insn
))
3068 if (BARRIER_P (insn
) || NONDEBUG_INSN_P (insn
))
3070 error ("verify_flow_info: Incorrect fallthru %i->%i",
3071 e
->src
->index
, e
->dest
->index
);
3072 error ("wrong insn in the fallthru edge");
3082 /* Verify that blocks are laid out in consecutive order. While walking the
3083 instructions, verify that all expected instructions are inside the basic
3084 blocks, and that all returns are followed by barriers. */
3087 rtl_verify_bb_layout (void)
3093 rtx_insn
* const rtx_first
= get_insns ();
3094 basic_block last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
), curr_bb
= NULL
;
3098 for (x
= rtx_first
; x
; x
= NEXT_INSN (x
))
3100 if (NOTE_INSN_BASIC_BLOCK_P (x
))
3102 bb
= NOTE_BASIC_BLOCK (x
);
3105 if (bb
!= last_bb_seen
->next_bb
)
3106 internal_error ("basic blocks not laid down consecutively");
3108 curr_bb
= last_bb_seen
= bb
;
3113 switch (GET_CODE (x
))
3120 /* An ADDR_VEC is placed outside any basic block. */
3122 && JUMP_TABLE_DATA_P (NEXT_INSN (x
)))
3125 /* But in any case, non-deletable labels can appear anywhere. */
3129 fatal_insn ("insn outside basic block", x
);
3134 && returnjump_p (x
) && ! condjump_p (x
)
3135 && ! ((y
= next_nonnote_nondebug_insn (x
))
3137 fatal_insn ("return not followed by barrier", x
);
3139 if (curr_bb
&& x
== BB_END (curr_bb
))
3143 if (num_bb_notes
!= n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
)
3145 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
3146 num_bb_notes
, n_basic_blocks_for_fn (cfun
));
3151 /* Verify the CFG and RTL consistency common for both underlying RTL and
3152 cfglayout RTL, plus consistency checks specific to linearized RTL mode.
3154 Currently it does following checks:
3155 - all checks of rtl_verify_flow_info_1
3156 - test head/end pointers
3157 - check that blocks are laid out in consecutive order
3158 - check that all insns are in the basic blocks
3159 (except the switch handling code, barriers and notes)
3160 - check that all returns are followed by barriers
3161 - check that all fallthru edge points to the adjacent blocks
3162 - verify that there is a single hot/cold partition boundary after bbro */
3165 rtl_verify_flow_info (void)
3169 if (rtl_verify_flow_info_1 ())
3172 if (rtl_verify_bb_insn_chain ())
3175 if (rtl_verify_fallthru ())
3178 if (rtl_verify_bb_layout ())
3181 if (verify_hot_cold_block_grouping ())
3187 /* Assume that the preceding pass has possibly eliminated jump instructions
3188 or converted the unconditional jumps. Eliminate the edges from CFG.
3189 Return true if any edges are eliminated. */
3192 purge_dead_edges (basic_block bb
)
3195 rtx_insn
*insn
= BB_END (bb
);
3197 bool purged
= false;
3201 if ((DEBUG_INSN_P (insn
) || NOTE_P (insn
)) && insn
!= BB_HEAD (bb
))
3203 insn
= PREV_INSN (insn
);
3204 while ((DEBUG_INSN_P (insn
) || NOTE_P (insn
)) && insn
!= BB_HEAD (bb
));
3206 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
3207 if (NONJUMP_INSN_P (insn
)
3208 && (note
= find_reg_note (insn
, REG_EH_REGION
, NULL
)))
3212 if (! may_trap_p (PATTERN (insn
))
3213 || ((eqnote
= find_reg_equal_equiv_note (insn
))
3214 && ! may_trap_p (XEXP (eqnote
, 0))))
3215 remove_note (insn
, note
);
3218 /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
3219 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3221 bool remove
= false;
3223 /* There are three types of edges we need to handle correctly here: EH
3224 edges, abnormal call EH edges, and abnormal call non-EH edges. The
3225 latter can appear when nonlocal gotos are used. */
3226 if (e
->flags
& EDGE_ABNORMAL_CALL
)
3230 else if (can_nonlocal_goto (insn
))
3232 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
3234 else if (flag_tm
&& find_reg_note (insn
, REG_TM
, NULL
))
3239 else if (e
->flags
& EDGE_EH
)
3240 remove
= !can_throw_internal (insn
);
3245 df_set_bb_dirty (bb
);
3258 /* We do care only about conditional jumps and simplejumps. */
3259 if (!any_condjump_p (insn
)
3260 && !returnjump_p (insn
)
3261 && !simplejump_p (insn
))
3264 /* Branch probability/prediction notes are defined only for
3265 condjumps. We've possibly turned condjump into simplejump. */
3266 if (simplejump_p (insn
))
3268 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
3270 remove_note (insn
, note
);
3271 while ((note
= find_reg_note (insn
, REG_BR_PRED
, NULL
)))
3272 remove_note (insn
, note
);
3275 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3277 /* Avoid abnormal flags to leak from computed jumps turned
3278 into simplejumps. */
3280 e
->flags
&= ~EDGE_ABNORMAL
;
3282 /* See if this edge is one we should keep. */
3283 if ((e
->flags
& EDGE_FALLTHRU
) && any_condjump_p (insn
))
3284 /* A conditional jump can fall through into the next
3285 block, so we should keep the edge. */
3290 else if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
3291 && BB_HEAD (e
->dest
) == JUMP_LABEL (insn
))
3292 /* If the destination block is the target of the jump,
3298 else if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
3299 && returnjump_p (insn
))
3300 /* If the destination block is the exit block, and this
3301 instruction is a return, then keep the edge. */
3306 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
3307 /* Keep the edges that correspond to exceptions thrown by
3308 this instruction and rematerialize the EDGE_ABNORMAL
3309 flag we just cleared above. */
3311 e
->flags
|= EDGE_ABNORMAL
;
3316 /* We do not need this edge. */
3317 df_set_bb_dirty (bb
);
3322 if (EDGE_COUNT (bb
->succs
) == 0 || !purged
)
3326 fprintf (dump_file
, "Purged edges from bb %i\n", bb
->index
);
3331 /* Redistribute probabilities. */
3332 if (single_succ_p (bb
))
3334 single_succ_edge (bb
)->probability
= profile_probability::always ();
3338 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
3342 b
= BRANCH_EDGE (bb
);
3343 f
= FALLTHRU_EDGE (bb
);
3344 b
->probability
= profile_probability::from_reg_br_prob_note
3346 f
->probability
= b
->probability
.invert ();
3351 else if (CALL_P (insn
) && SIBLING_CALL_P (insn
))
3353 /* First, there should not be any EH or ABCALL edges resulting
3354 from non-local gotos and the like. If there were, we shouldn't
3355 have created the sibcall in the first place. Second, there
3356 should of course never have been a fallthru edge. */
3357 gcc_assert (single_succ_p (bb
));
3358 gcc_assert (single_succ_edge (bb
)->flags
3359 == (EDGE_SIBCALL
| EDGE_ABNORMAL
));
3364 /* If we don't see a jump insn, we don't know exactly why the block would
3365 have been broken at this point. Look for a simple, non-fallthru edge,
3366 as these are only created by conditional branches. If we find such an
3367 edge we know that there used to be a jump here and can then safely
3368 remove all non-fallthru edges. */
3370 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3371 if (! (e
->flags
& (EDGE_COMPLEX
| EDGE_FALLTHRU
)))
3380 /* Remove all but the fake and fallthru edges. The fake edge may be
3381 the only successor for this block in the case of noreturn
3383 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3385 if (!(e
->flags
& (EDGE_FALLTHRU
| EDGE_FAKE
)))
3387 df_set_bb_dirty (bb
);
3395 gcc_assert (single_succ_p (bb
));
3397 single_succ_edge (bb
)->probability
= profile_probability::always ();
3400 fprintf (dump_file
, "Purged non-fallthru edges from bb %i\n",
3405 /* Search all basic blocks for potentially dead edges and purge them. Return
3406 true if some edge has been eliminated. */
3409 purge_all_dead_edges (void)
3411 bool purged
= false;
3414 FOR_EACH_BB_FN (bb
, cfun
)
3415 if (purge_dead_edges (bb
))
3421 /* This is used by a few passes that emit some instructions after abnormal
3422 calls, moving the basic block's end, while they in fact do want to emit
3423 them on the fallthru edge. Look for abnormal call edges, find backward
3424 the call in the block and insert the instructions on the edge instead.
3426 Similarly, handle instructions throwing exceptions internally.
3428 Return true when instructions have been found and inserted on edges. */
3431 fixup_abnormal_edges (void)
3433 bool inserted
= false;
3436 FOR_EACH_BB_FN (bb
, cfun
)
3441 /* Look for cases we are interested in - calls or instructions causing
3443 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3444 if ((e
->flags
& EDGE_ABNORMAL_CALL
)
3445 || ((e
->flags
& (EDGE_ABNORMAL
| EDGE_EH
))
3446 == (EDGE_ABNORMAL
| EDGE_EH
)))
3449 if (e
&& !CALL_P (BB_END (bb
)) && !can_throw_internal (BB_END (bb
)))
3453 /* Get past the new insns generated. Allow notes, as the insns
3454 may be already deleted. */
3456 while ((NONJUMP_INSN_P (insn
) || NOTE_P (insn
))
3457 && !can_throw_internal (insn
)
3458 && insn
!= BB_HEAD (bb
))
3459 insn
= PREV_INSN (insn
);
3461 if (CALL_P (insn
) || can_throw_internal (insn
))
3463 rtx_insn
*stop
, *next
;
3465 e
= find_fallthru_edge (bb
->succs
);
3467 stop
= NEXT_INSN (BB_END (bb
));
3470 for (insn
= NEXT_INSN (insn
); insn
!= stop
; insn
= next
)
3472 next
= NEXT_INSN (insn
);
3477 /* Sometimes there's still the return value USE.
3478 If it's placed after a trapping call (i.e. that
3479 call is the last insn anyway), we have no fallthru
3480 edge. Simply delete this use and don't try to insert
3481 on the non-existent edge.
3482 Similarly, sometimes a call that can throw is
3483 followed in the source with __builtin_unreachable (),
3484 meaning that there is UB if the call returns rather
3485 than throws. If there weren't any instructions
3486 following such calls before, supposedly even the ones
3487 we've deleted aren't significant and can be
3491 /* We're not deleting it, we're moving it. */
3492 insn
->set_undeleted ();
3493 SET_PREV_INSN (insn
) = NULL_RTX
;
3494 SET_NEXT_INSN (insn
) = NULL_RTX
;
3496 insert_insn_on_edge (insn
, e
);
3500 else if (!BARRIER_P (insn
))
3501 set_block_for_insn (insn
, NULL
);
3505 /* It may be that we don't find any trapping insn. In this
3506 case we discovered quite late that the insn that had been
3507 marked as can_throw_internal in fact couldn't trap at all.
3508 So we should in fact delete the EH edges out of the block. */
3510 purge_dead_edges (bb
);
3517 /* Delete the unconditional jump INSN and adjust the CFG correspondingly.
3518 Note that the INSN should be deleted *after* removing dead edges, so
3519 that the kept edge is the fallthrough edge for a (set (pc) (pc))
3520 but not for a (set (pc) (label_ref FOO)). */
3523 update_cfg_for_uncondjump (rtx_insn
*insn
)
3525 basic_block bb
= BLOCK_FOR_INSN (insn
);
3526 gcc_assert (BB_END (bb
) == insn
);
3528 purge_dead_edges (bb
);
3530 if (current_ir_type () != IR_RTL_CFGLAYOUT
)
3532 if (!find_fallthru_edge (bb
->succs
))
3534 auto barrier
= next_nonnote_nondebug_insn (insn
);
3535 if (!barrier
|| !BARRIER_P (barrier
))
3536 emit_barrier_after (insn
);
3542 if (EDGE_COUNT (bb
->succs
) == 1)
3546 single_succ_edge (bb
)->flags
|= EDGE_FALLTHRU
;
3548 /* Remove barriers from the footer if there are any. */
3549 for (insn
= BB_FOOTER (bb
); insn
; insn
= NEXT_INSN (insn
))
3550 if (BARRIER_P (insn
))
3552 if (PREV_INSN (insn
))
3553 SET_NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
3555 BB_FOOTER (bb
) = NEXT_INSN (insn
);
3556 if (NEXT_INSN (insn
))
3557 SET_PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
3559 else if (LABEL_P (insn
))
3564 /* Cut the insns from FIRST to LAST out of the insns stream. */
3567 unlink_insn_chain (rtx_insn
*first
, rtx_insn
*last
)
3569 rtx_insn
*prevfirst
= PREV_INSN (first
);
3570 rtx_insn
*nextlast
= NEXT_INSN (last
);
3572 SET_PREV_INSN (first
) = NULL
;
3573 SET_NEXT_INSN (last
) = NULL
;
3575 SET_NEXT_INSN (prevfirst
) = nextlast
;
3577 SET_PREV_INSN (nextlast
) = prevfirst
;
3579 set_last_insn (prevfirst
);
3581 set_first_insn (nextlast
);
3585 /* Skip over inter-block insns occurring after BB which are typically
3586 associated with BB (e.g., barriers). If there are any such insns,
3587 we return the last one. Otherwise, we return the end of BB. */
3590 skip_insns_after_block (basic_block bb
)
3592 rtx_insn
*insn
, *last_insn
, *next_head
, *prev
;
3595 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3596 next_head
= BB_HEAD (bb
->next_bb
);
3598 for (last_insn
= insn
= BB_END (bb
); (insn
= NEXT_INSN (insn
)) != 0; )
3600 if (insn
== next_head
)
3603 switch (GET_CODE (insn
))
3610 gcc_assert (NOTE_KIND (insn
) != NOTE_INSN_BLOCK_END
);
3614 if (NEXT_INSN (insn
)
3615 && JUMP_TABLE_DATA_P (NEXT_INSN (insn
)))
3617 insn
= NEXT_INSN (insn
);
3630 /* It is possible to hit contradictory sequence. For instance:
3636 Where barrier belongs to jump_insn, but the note does not. This can be
3637 created by removing the basic block originally following
3638 NOTE_INSN_BLOCK_BEG. In such case reorder the notes. */
3640 for (insn
= last_insn
; insn
!= BB_END (bb
); insn
= prev
)
3642 prev
= PREV_INSN (insn
);
3644 switch (NOTE_KIND (insn
))
3646 case NOTE_INSN_BLOCK_END
:
3649 case NOTE_INSN_DELETED
:
3650 case NOTE_INSN_DELETED_LABEL
:
3651 case NOTE_INSN_DELETED_DEBUG_LABEL
:
3654 reorder_insns (insn
, insn
, last_insn
);
3661 /* Locate or create a label for a given basic block. */
3664 label_for_bb (basic_block bb
)
3666 rtx_insn
*label
= BB_HEAD (bb
);
3668 if (!LABEL_P (label
))
3671 fprintf (dump_file
, "Emitting label for block %d\n", bb
->index
);
3673 label
= block_label (bb
);
3679 /* Locate the effective beginning and end of the insn chain for each
3680 block, as defined by skip_insns_after_block above. */
3683 record_effective_endpoints (void)
3685 rtx_insn
*next_insn
;
3689 for (insn
= get_insns ();
3692 && NOTE_KIND (insn
) != NOTE_INSN_BASIC_BLOCK
;
3693 insn
= NEXT_INSN (insn
))
3695 /* No basic blocks at all? */
3698 if (PREV_INSN (insn
))
3699 cfg_layout_function_header
=
3700 unlink_insn_chain (get_insns (), PREV_INSN (insn
));
3702 cfg_layout_function_header
= NULL
;
3704 next_insn
= get_insns ();
3705 FOR_EACH_BB_FN (bb
, cfun
)
3709 if (PREV_INSN (BB_HEAD (bb
)) && next_insn
!= BB_HEAD (bb
))
3710 BB_HEADER (bb
) = unlink_insn_chain (next_insn
,
3711 PREV_INSN (BB_HEAD (bb
)));
3712 end
= skip_insns_after_block (bb
);
3713 if (NEXT_INSN (BB_END (bb
)) && BB_END (bb
) != end
)
3714 BB_FOOTER (bb
) = unlink_insn_chain (NEXT_INSN (BB_END (bb
)), end
);
3715 next_insn
= NEXT_INSN (BB_END (bb
));
3718 cfg_layout_function_footer
= next_insn
;
3719 if (cfg_layout_function_footer
)
3720 cfg_layout_function_footer
= unlink_insn_chain (cfg_layout_function_footer
, get_last_insn ());
3725 const pass_data pass_data_into_cfg_layout_mode
=
3727 RTL_PASS
, /* type */
3728 "into_cfglayout", /* name */
3729 OPTGROUP_NONE
, /* optinfo_flags */
3731 0, /* properties_required */
3732 PROP_cfglayout
, /* properties_provided */
3733 0, /* properties_destroyed */
3734 0, /* todo_flags_start */
3735 0, /* todo_flags_finish */
3738 class pass_into_cfg_layout_mode
: public rtl_opt_pass
3741 pass_into_cfg_layout_mode (gcc::context
*ctxt
)
3742 : rtl_opt_pass (pass_data_into_cfg_layout_mode
, ctxt
)
3745 /* opt_pass methods: */
3746 unsigned int execute (function
*) final override
3748 cfg_layout_initialize (0);
3752 }; // class pass_into_cfg_layout_mode
3757 make_pass_into_cfg_layout_mode (gcc::context
*ctxt
)
3759 return new pass_into_cfg_layout_mode (ctxt
);
3764 const pass_data pass_data_outof_cfg_layout_mode
=
3766 RTL_PASS
, /* type */
3767 "outof_cfglayout", /* name */
3768 OPTGROUP_NONE
, /* optinfo_flags */
3770 0, /* properties_required */
3771 0, /* properties_provided */
3772 PROP_cfglayout
, /* properties_destroyed */
3773 0, /* todo_flags_start */
3774 0, /* todo_flags_finish */
3777 class pass_outof_cfg_layout_mode
: public rtl_opt_pass
3780 pass_outof_cfg_layout_mode (gcc::context
*ctxt
)
3781 : rtl_opt_pass (pass_data_outof_cfg_layout_mode
, ctxt
)
3784 /* opt_pass methods: */
3785 unsigned int execute (function
*) final override
;
3787 }; // class pass_outof_cfg_layout_mode
3790 pass_outof_cfg_layout_mode::execute (function
*fun
)
3794 FOR_EACH_BB_FN (bb
, fun
)
3795 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (fun
))
3796 bb
->aux
= bb
->next_bb
;
3798 cfg_layout_finalize ();
3806 make_pass_outof_cfg_layout_mode (gcc::context
*ctxt
)
3808 return new pass_outof_cfg_layout_mode (ctxt
);
3812 /* Link the basic blocks in the correct order, compacting the basic
3813 block queue while at it. If STAY_IN_CFGLAYOUT_MODE is false, this
3814 function also clears the basic block header and footer fields.
3816 This function is usually called after a pass (e.g. tracer) finishes
3817 some transformations while in cfglayout mode. The required sequence
3818 of the basic blocks is in a linked list along the bb->aux field.
3819 This functions re-links the basic block prev_bb and next_bb pointers
3820 accordingly, and it compacts and renumbers the blocks.
3822 FIXME: This currently works only for RTL, but the only RTL-specific
3823 bits are the STAY_IN_CFGLAYOUT_MODE bits. The tracer pass was moved
3824 to GIMPLE a long time ago, but it doesn't relink the basic block
3825 chain. It could do that (to give better initial RTL) if this function
3826 is made IR-agnostic (and moved to cfganal.cc or cfg.cc while at it). */
3829 relink_block_chain (bool stay_in_cfglayout_mode
)
3831 basic_block bb
, prev_bb
;
3834 /* Maybe dump the re-ordered sequence. */
3837 fprintf (dump_file
, "Reordered sequence:\n");
3838 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
, index
=
3841 bb
= (basic_block
) bb
->aux
, index
++)
3843 fprintf (dump_file
, " %i ", index
);
3844 if (get_bb_original (bb
))
3845 fprintf (dump_file
, "duplicate of %i\n",
3846 get_bb_original (bb
)->index
);
3847 else if (forwarder_block_p (bb
)
3848 && !LABEL_P (BB_HEAD (bb
)))
3849 fprintf (dump_file
, "compensation\n");
3851 fprintf (dump_file
, "bb %i\n", bb
->index
);
3855 /* Now reorder the blocks. */
3856 prev_bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
3857 bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
;
3858 for (; bb
; prev_bb
= bb
, bb
= (basic_block
) bb
->aux
)
3860 bb
->prev_bb
= prev_bb
;
3861 prev_bb
->next_bb
= bb
;
3863 prev_bb
->next_bb
= EXIT_BLOCK_PTR_FOR_FN (cfun
);
3864 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
= prev_bb
;
3866 /* Then, clean up the aux fields. */
3867 FOR_ALL_BB_FN (bb
, cfun
)
3870 if (!stay_in_cfglayout_mode
)
3871 BB_HEADER (bb
) = BB_FOOTER (bb
) = NULL
;
3874 /* Maybe reset the original copy tables, they are not valid anymore
3875 when we renumber the basic blocks in compact_blocks. If we are
3876 are going out of cfglayout mode, don't re-allocate the tables. */
3877 if (original_copy_tables_initialized_p ())
3878 free_original_copy_tables ();
3879 if (stay_in_cfglayout_mode
)
3880 initialize_original_copy_tables ();
3882 /* Finally, put basic_block_info in the new order. */
3887 /* Given a reorder chain, rearrange the code to match. */
3890 fixup_reorder_chain (void)
3893 rtx_insn
*insn
= NULL
;
3895 if (cfg_layout_function_header
)
3897 set_first_insn (cfg_layout_function_header
);
3898 insn
= cfg_layout_function_header
;
3899 while (NEXT_INSN (insn
))
3900 insn
= NEXT_INSN (insn
);
3903 /* First do the bulk reordering -- rechain the blocks without regard to
3904 the needed changes to jumps and labels. */
3906 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
; bb
; bb
= (basic_block
)
3912 SET_NEXT_INSN (insn
) = BB_HEADER (bb
);
3914 set_first_insn (BB_HEADER (bb
));
3915 SET_PREV_INSN (BB_HEADER (bb
)) = insn
;
3916 insn
= BB_HEADER (bb
);
3917 while (NEXT_INSN (insn
))
3918 insn
= NEXT_INSN (insn
);
3921 SET_NEXT_INSN (insn
) = BB_HEAD (bb
);
3923 set_first_insn (BB_HEAD (bb
));
3924 SET_PREV_INSN (BB_HEAD (bb
)) = insn
;
3928 SET_NEXT_INSN (insn
) = BB_FOOTER (bb
);
3929 SET_PREV_INSN (BB_FOOTER (bb
)) = insn
;
3930 while (NEXT_INSN (insn
))
3931 insn
= NEXT_INSN (insn
);
3935 SET_NEXT_INSN (insn
) = cfg_layout_function_footer
;
3936 if (cfg_layout_function_footer
)
3937 SET_PREV_INSN (cfg_layout_function_footer
) = insn
;
3939 while (NEXT_INSN (insn
))
3940 insn
= NEXT_INSN (insn
);
3942 set_last_insn (insn
);
3944 verify_insn_chain ();
3946 /* Now add jumps and labels as needed to match the blocks new
3949 bool remove_unreachable_blocks
= false;
3950 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
; bb
; bb
= (basic_block
)
3953 edge e_fall
, e_taken
, e
;
3954 rtx_insn
*bb_end_insn
;
3955 rtx ret_label
= NULL_RTX
;
3958 bool asm_goto
= false;
3960 if (EDGE_COUNT (bb
->succs
) == 0)
3963 /* Find the old fallthru edge, and another non-EH edge for
3965 e_taken
= e_fall
= NULL
;
3967 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3968 if (e
->flags
& EDGE_FALLTHRU
)
3970 else if (! (e
->flags
& EDGE_EH
))
3973 bb_end_insn
= BB_END (bb
);
3974 if (rtx_jump_insn
*bb_end_jump
= dyn_cast
<rtx_jump_insn
*> (bb_end_insn
))
3976 ret_label
= JUMP_LABEL (bb_end_jump
);
3977 if (any_condjump_p (bb_end_jump
))
3979 /* This might happen if the conditional jump has side
3980 effects and could therefore not be optimized away.
3981 Make the basic block to end with a barrier in order
3982 to prevent rtl_verify_flow_info from complaining. */
3985 gcc_assert (!onlyjump_p (bb_end_jump
)
3986 || returnjump_p (bb_end_jump
)
3987 || (e_taken
->flags
& EDGE_CROSSING
));
3988 emit_barrier_after (bb_end_jump
);
3992 /* If the old fallthru is still next, nothing to do. */
3993 if (bb
->aux
== e_fall
->dest
3994 || e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3997 /* The degenerated case of conditional jump jumping to the next
3998 instruction can happen for jumps with side effects. We need
3999 to construct a forwarder block and this will be done just
4000 fine by force_nonfallthru below. */
4004 /* There is another special case: if *neither* block is next,
4005 such as happens at the very end of a function, then we'll
4006 need to add a new unconditional jump. Choose the taken
4007 edge based on known or assumed probability. */
4008 else if (bb
->aux
!= e_taken
->dest
)
4010 rtx note
= find_reg_note (bb_end_jump
, REG_BR_PROB
, 0);
4013 && profile_probability::from_reg_br_prob_note
4014 (XINT (note
, 0)) < profile_probability::even ()
4015 && invert_jump (bb_end_jump
,
4017 == EXIT_BLOCK_PTR_FOR_FN (cfun
)
4019 : label_for_bb (e_fall
->dest
)), 0))
4021 e_fall
->flags
&= ~EDGE_FALLTHRU
;
4022 gcc_checking_assert (could_fall_through
4023 (e_taken
->src
, e_taken
->dest
));
4024 e_taken
->flags
|= EDGE_FALLTHRU
;
4025 update_br_prob_note (bb
);
4026 e
= e_fall
, e_fall
= e_taken
, e_taken
= e
;
4030 /* If the "jumping" edge is a crossing edge, and the fall
4031 through edge is non-crossing, leave things as they are. */
4032 else if ((e_taken
->flags
& EDGE_CROSSING
)
4033 && !(e_fall
->flags
& EDGE_CROSSING
))
4036 /* Otherwise we can try to invert the jump. This will
4037 basically never fail, however, keep up the pretense. */
4038 else if (invert_jump (bb_end_jump
,
4040 == EXIT_BLOCK_PTR_FOR_FN (cfun
)
4042 : label_for_bb (e_fall
->dest
)), 0))
4044 e_fall
->flags
&= ~EDGE_FALLTHRU
;
4045 gcc_checking_assert (could_fall_through
4046 (e_taken
->src
, e_taken
->dest
));
4047 e_taken
->flags
|= EDGE_FALLTHRU
;
4048 update_br_prob_note (bb
);
4049 if (LABEL_NUSES (ret_label
) == 0
4050 && single_pred_p (e_taken
->dest
))
4051 delete_insn (as_a
<rtx_insn
*> (ret_label
));
4055 else if (extract_asm_operands (PATTERN (bb_end_insn
)) != NULL
)
4057 /* If the old fallthru is still next or if
4058 asm goto doesn't have a fallthru (e.g. when followed by
4059 __builtin_unreachable ()), nothing to do. */
4061 || bb
->aux
== e_fall
->dest
4062 || e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4065 /* Otherwise we'll have to use the fallthru fixup below.
4066 But avoid redirecting asm goto to EXIT. */
4071 /* Otherwise we have some return, switch or computed
4072 jump. In the 99% case, there should not have been a
4074 gcc_assert (returnjump_p (bb_end_insn
) || !e_fall
);
4080 /* No fallthru implies a noreturn function with EH edges, or
4081 something similarly bizarre. In any case, we don't need to
4086 /* If the fallthru block is still next, nothing to do. */
4087 if (bb
->aux
== e_fall
->dest
)
4090 /* A fallthru to exit block. */
4091 if (e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4095 /* If E_FALL->dest is just a return block, then we can emit a
4096 return rather than a jump to the return block. */
4097 rtx_insn
*ret
, *use
;
4100 && bb_is_just_return (e_fall
->dest
, &ret
, &use
)
4101 && ((PATTERN (ret
) == simple_return_rtx
&& targetm
.have_simple_return ())
4102 || (PATTERN (ret
) == ret_rtx
&& targetm
.have_return ())))
4104 ret_label
= PATTERN (ret
);
4105 dest
= EXIT_BLOCK_PTR_FOR_FN (cfun
);
4107 e_fall
->flags
&= ~EDGE_CROSSING
;
4108 /* E_FALL->dest might become unreachable as a result of
4109 replacing the jump with a return. So arrange to remove
4110 unreachable blocks. */
4111 remove_unreachable_blocks
= true;
4115 dest
= e_fall
->dest
;
4118 /* We got here if we need to add a new jump insn.
4119 Note force_nonfallthru can delete E_FALL and thus we have to
4120 save E_FALL->src prior to the call to force_nonfallthru. */
4121 nb
= force_nonfallthru_and_redirect (e_fall
, dest
, ret_label
);
4126 /* Don't process this new block. */
4131 relink_block_chain (/*stay_in_cfglayout_mode=*/false);
4133 /* Annoying special case - jump around dead jumptables left in the code. */
4134 FOR_EACH_BB_FN (bb
, cfun
)
4136 edge e
= find_fallthru_edge (bb
->succs
);
4138 if (e
&& !can_fallthru (e
->src
, e
->dest
))
4139 force_nonfallthru (e
);
4142 /* Ensure goto_locus from edges has some instructions with that locus in RTL
4143 when not optimizing. */
4144 if (!optimize
&& !DECL_IGNORED_P (current_function_decl
))
4145 FOR_EACH_BB_FN (bb
, cfun
)
4150 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
4151 if (LOCATION_LOCUS (e
->goto_locus
) != UNKNOWN_LOCATION
4152 && !(e
->flags
& EDGE_ABNORMAL
))
4156 basic_block dest
, nb
;
4159 insn
= BB_END (e
->src
);
4160 end
= PREV_INSN (BB_HEAD (e
->src
));
4162 && (!NONDEBUG_INSN_P (insn
) || !INSN_HAS_LOCATION (insn
)))
4163 insn
= PREV_INSN (insn
);
4165 && loc_equal (INSN_LOCATION (insn
), e
->goto_locus
))
4167 if (simplejump_p (BB_END (e
->src
))
4168 && !INSN_HAS_LOCATION (BB_END (e
->src
)))
4170 INSN_LOCATION (BB_END (e
->src
)) = e
->goto_locus
;
4174 if (dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4176 /* Non-fallthru edges to the exit block cannot be split. */
4177 if (!(e
->flags
& EDGE_FALLTHRU
))
4182 insn
= BB_HEAD (dest
);
4183 end
= NEXT_INSN (BB_END (dest
));
4184 while (insn
!= end
&& !NONDEBUG_INSN_P (insn
))
4185 insn
= NEXT_INSN (insn
);
4186 if (insn
!= end
&& INSN_HAS_LOCATION (insn
)
4187 && loc_equal (INSN_LOCATION (insn
), e
->goto_locus
))
4190 nb
= split_edge (e
);
4191 if (!INSN_P (BB_END (nb
)))
4192 BB_END (nb
) = emit_insn_after_noloc (gen_nop (), BB_END (nb
),
4194 INSN_LOCATION (BB_END (nb
)) = e
->goto_locus
;
4196 /* If there are other incoming edges to the destination block
4197 with the same goto locus, redirect them to the new block as
4198 well, this can prevent other such blocks from being created
4199 in subsequent iterations of the loop. */
4200 for (ei2
= ei_start (dest
->preds
); (e2
= ei_safe_edge (ei2
)); )
4201 if (LOCATION_LOCUS (e2
->goto_locus
) != UNKNOWN_LOCATION
4202 && !(e2
->flags
& (EDGE_ABNORMAL
| EDGE_FALLTHRU
))
4203 && e
->goto_locus
== e2
->goto_locus
)
4204 redirect_edge_and_branch (e2
, nb
);
4210 /* Replacing a jump with a return may have exposed an unreachable
4211 block. Conditionally remove them if such transformations were
4213 if (remove_unreachable_blocks
)
4214 delete_unreachable_blocks ();
4217 /* Perform sanity checks on the insn chain.
4218 1. Check that next/prev pointers are consistent in both the forward and
4220 2. Count insns in chain, going both directions, and check if equal.
4221 3. Check that get_last_insn () returns the actual end of chain. */
4224 verify_insn_chain (void)
4226 rtx_insn
*x
, *prevx
, *nextx
;
4227 int insn_cnt1
, insn_cnt2
;
4229 for (prevx
= NULL
, insn_cnt1
= 1, x
= get_insns ();
4231 prevx
= x
, insn_cnt1
++, x
= NEXT_INSN (x
))
4232 gcc_assert (PREV_INSN (x
) == prevx
);
4234 gcc_assert (prevx
== get_last_insn ());
4236 for (nextx
= NULL
, insn_cnt2
= 1, x
= get_last_insn ();
4238 nextx
= x
, insn_cnt2
++, x
= PREV_INSN (x
))
4239 gcc_assert (NEXT_INSN (x
) == nextx
);
4241 gcc_assert (insn_cnt1
== insn_cnt2
);
4244 /* If we have assembler epilogues, the block falling through to exit must
4245 be the last one in the reordered chain when we reach final. Ensure
4246 that this condition is met. */
4248 fixup_fallthru_exit_predecessor (void)
4251 basic_block bb
= NULL
;
4253 /* This transformation is not valid before reload, because we might
4254 separate a call from the instruction that copies the return
4256 gcc_assert (reload_completed
);
4258 e
= find_fallthru_edge (EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
);
4264 basic_block c
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
;
4266 /* If the very first block is the one with the fall-through exit
4267 edge, we have to split that block. */
4270 bb
= split_block_after_labels (bb
)->dest
;
4273 BB_FOOTER (bb
) = BB_FOOTER (c
);
4274 BB_FOOTER (c
) = NULL
;
4277 while (c
->aux
!= bb
)
4278 c
= (basic_block
) c
->aux
;
4282 c
= (basic_block
) c
->aux
;
4289 /* In case there are more than one fallthru predecessors of exit, force that
4290 there is only one. */
4293 force_one_exit_fallthru (void)
4295 edge e
, predecessor
= NULL
;
4298 basic_block forwarder
, bb
;
4300 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
4301 if (e
->flags
& EDGE_FALLTHRU
)
4303 if (predecessor
== NULL
)
4315 /* Exit has several fallthru predecessors. Create a forwarder block for
4317 forwarder
= split_edge (predecessor
);
4318 for (ei
= ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
);
4319 (e
= ei_safe_edge (ei
)); )
4321 if (e
->src
== forwarder
4322 || !(e
->flags
& EDGE_FALLTHRU
))
4325 redirect_edge_and_branch_force (e
, forwarder
);
4328 /* Fix up the chain of blocks -- make FORWARDER immediately precede the
4330 FOR_EACH_BB_FN (bb
, cfun
)
4332 if (bb
->aux
== NULL
&& bb
!= forwarder
)
4334 bb
->aux
= forwarder
;
4340 /* Return true in case it is possible to duplicate the basic block BB. */
4343 cfg_layout_can_duplicate_bb_p (const_basic_block bb
)
4345 /* Do not attempt to duplicate tablejumps, as we need to unshare
4346 the dispatch table. This is difficult to do, as the instructions
4347 computing jump destination may be hoisted outside the basic block. */
4348 if (tablejump_p (BB_END (bb
), NULL
, NULL
))
4351 /* Do not duplicate blocks containing insns that can't be copied. */
4352 if (targetm
.cannot_copy_insn_p
)
4354 rtx_insn
*insn
= BB_HEAD (bb
);
4357 if (INSN_P (insn
) && targetm
.cannot_copy_insn_p (insn
))
4359 if (insn
== BB_END (bb
))
4361 insn
= NEXT_INSN (insn
);
4369 duplicate_insn_chain (rtx_insn
*from
, rtx_insn
*to
,
4370 class loop
*loop
, copy_bb_data
*id
)
4372 rtx_insn
*insn
, *next
, *copy
;
4375 /* Avoid updating of boundaries of previous basic block. The
4376 note will get removed from insn stream in fixup. */
4377 last
= emit_note (NOTE_INSN_DELETED
);
4379 /* Create copy at the end of INSN chain. The chain will
4380 be reordered later. */
4381 for (insn
= from
; insn
!= NEXT_INSN (to
); insn
= NEXT_INSN (insn
))
4383 switch (GET_CODE (insn
))
4386 /* Don't duplicate label debug insns. */
4387 if (DEBUG_BIND_INSN_P (insn
)
4388 && TREE_CODE (INSN_VAR_LOCATION_DECL (insn
)) == LABEL_DECL
)
4394 copy
= emit_copy_of_insn_after (insn
, get_last_insn ());
4395 if (JUMP_P (insn
) && JUMP_LABEL (insn
) != NULL_RTX
4396 && ANY_RETURN_P (JUMP_LABEL (insn
)))
4397 JUMP_LABEL (copy
) = JUMP_LABEL (insn
);
4398 maybe_copy_prologue_epilogue_insn (insn
, copy
);
4399 /* If requested remap dependence info of cliques brought in
4403 subrtx_iterator::array_type array
;
4404 FOR_EACH_SUBRTX (iter
, array
, PATTERN (insn
), ALL
)
4405 if (MEM_P (*iter
) && MEM_EXPR (*iter
))
4407 tree op
= MEM_EXPR (*iter
);
4408 if (TREE_CODE (op
) == WITH_SIZE_EXPR
)
4409 op
= TREE_OPERAND (op
, 0);
4410 while (handled_component_p (op
))
4411 op
= TREE_OPERAND (op
, 0);
4412 if ((TREE_CODE (op
) == MEM_REF
4413 || TREE_CODE (op
) == TARGET_MEM_REF
)
4414 && MR_DEPENDENCE_CLIQUE (op
) > 1
4416 || (MR_DEPENDENCE_CLIQUE (op
)
4417 != loop
->owned_clique
)))
4419 if (!id
->dependence_map
)
4420 id
->dependence_map
= new hash_map
<dependence_hash
,
4423 unsigned short &newc
= id
->dependence_map
->get_or_insert
4424 (MR_DEPENDENCE_CLIQUE (op
), &existed
);
4428 (MR_DEPENDENCE_CLIQUE (op
) <= cfun
->last_clique
);
4429 newc
= get_new_clique (cfun
);
4431 /* We cannot adjust MR_DEPENDENCE_CLIQUE in-place
4432 since MEM_EXPR is shared so make a copy and
4433 walk to the subtree again. */
4434 tree new_expr
= unshare_expr (MEM_EXPR (*iter
));
4435 tree orig_new_expr
= new_expr
;
4436 if (TREE_CODE (new_expr
) == WITH_SIZE_EXPR
)
4437 new_expr
= TREE_OPERAND (new_expr
, 0);
4438 while (handled_component_p (new_expr
))
4439 new_expr
= TREE_OPERAND (new_expr
, 0);
4440 MR_DEPENDENCE_CLIQUE (new_expr
) = newc
;
4441 set_mem_expr (const_cast <rtx
> (*iter
), orig_new_expr
);
4447 case JUMP_TABLE_DATA
:
4448 /* Avoid copying of dispatch tables. We never duplicate
4449 tablejumps, so this can hit only in case the table got
4450 moved far from original jump.
4451 Avoid copying following barrier as well if any
4452 (and debug insns in between). */
4453 for (next
= NEXT_INSN (insn
);
4454 next
!= NEXT_INSN (to
);
4455 next
= NEXT_INSN (next
))
4456 if (!DEBUG_INSN_P (next
))
4458 if (next
!= NEXT_INSN (to
) && BARRIER_P (next
))
4470 switch (NOTE_KIND (insn
))
4472 /* In case prologue is empty and function contain label
4473 in first BB, we may want to copy the block. */
4474 case NOTE_INSN_PROLOGUE_END
:
4476 case NOTE_INSN_DELETED
:
4477 case NOTE_INSN_DELETED_LABEL
:
4478 case NOTE_INSN_DELETED_DEBUG_LABEL
:
4479 /* No problem to strip these. */
4480 case NOTE_INSN_FUNCTION_BEG
:
4481 /* There is always just single entry to function. */
4482 case NOTE_INSN_BASIC_BLOCK
:
4483 /* We should only switch text sections once. */
4484 case NOTE_INSN_SWITCH_TEXT_SECTIONS
:
4487 case NOTE_INSN_EPILOGUE_BEG
:
4488 case NOTE_INSN_UPDATE_SJLJ_CONTEXT
:
4489 emit_note_copy (as_a
<rtx_note
*> (insn
));
4493 /* All other notes should have already been eliminated. */
4501 insn
= NEXT_INSN (last
);
4506 /* Create a duplicate of the basic block BB. */
4509 cfg_layout_duplicate_bb (basic_block bb
, copy_bb_data
*id
)
4514 class loop
*loop
= (id
&& current_loops
) ? bb
->loop_father
: NULL
;
4516 insn
= duplicate_insn_chain (BB_HEAD (bb
), BB_END (bb
), loop
, id
);
4517 new_bb
= create_basic_block (insn
,
4518 insn
? get_last_insn () : NULL
,
4519 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
);
4521 BB_COPY_PARTITION (new_bb
, bb
);
4524 insn
= BB_HEADER (bb
);
4525 while (NEXT_INSN (insn
))
4526 insn
= NEXT_INSN (insn
);
4527 insn
= duplicate_insn_chain (BB_HEADER (bb
), insn
, loop
, id
);
4529 BB_HEADER (new_bb
) = unlink_insn_chain (insn
, get_last_insn ());
4534 insn
= BB_FOOTER (bb
);
4535 while (NEXT_INSN (insn
))
4536 insn
= NEXT_INSN (insn
);
4537 insn
= duplicate_insn_chain (BB_FOOTER (bb
), insn
, loop
, id
);
4539 BB_FOOTER (new_bb
) = unlink_insn_chain (insn
, get_last_insn ());
4546 /* Main entry point to this module - initialize the datastructures for
4547 CFG layout changes. It keeps LOOPS up-to-date if not null.
4549 FLAGS is a set of additional flags to pass to cleanup_cfg(). */
4552 cfg_layout_initialize (int flags
)
4557 /* Once bb partitioning is complete, cfg layout mode should not be
4558 re-entered. Entering cfg layout mode may require fixups. As an
4559 example, if edge forwarding performed when optimizing the cfg
4560 layout required moving a block from the hot to the cold
4561 section. This would create an illegal partitioning unless some
4562 manual fixup was performed. */
4563 gcc_assert (!crtl
->bb_reorder_complete
|| !crtl
->has_bb_partition
);
4565 initialize_original_copy_tables ();
4567 cfg_layout_rtl_register_cfg_hooks ();
4569 record_effective_endpoints ();
4571 /* Make sure that the targets of non local gotos are marked. */
4572 for (x
= nonlocal_goto_handler_labels
; x
; x
= x
->next ())
4574 bb
= BLOCK_FOR_INSN (x
->insn ());
4575 bb
->flags
|= BB_NON_LOCAL_GOTO_TARGET
;
4578 cleanup_cfg (CLEANUP_CFGLAYOUT
| flags
);
4581 /* Splits superblocks. */
4583 break_superblocks (void)
4588 auto_sbitmap
superblocks (last_basic_block_for_fn (cfun
));
4589 bitmap_clear (superblocks
);
4591 FOR_EACH_BB_FN (bb
, cfun
)
4592 if (bb
->flags
& BB_SUPERBLOCK
)
4594 bb
->flags
&= ~BB_SUPERBLOCK
;
4595 bitmap_set_bit (superblocks
, bb
->index
);
4601 rebuild_jump_labels (get_insns ());
4602 find_many_sub_basic_blocks (superblocks
);
4606 /* Finalize the changes: reorder insn list according to the sequence specified
4607 by aux pointers, enter compensation code, rebuild scope forest. */
4610 cfg_layout_finalize (void)
4612 free_dominance_info (CDI_DOMINATORS
);
4613 force_one_exit_fallthru ();
4614 rtl_register_cfg_hooks ();
4615 if (reload_completed
&& !targetm
.have_epilogue ())
4616 fixup_fallthru_exit_predecessor ();
4617 fixup_reorder_chain ();
4619 rebuild_jump_labels (get_insns ());
4620 delete_dead_jumptables ();
4623 verify_insn_chain ();
4624 checking_verify_flow_info ();
4628 /* Same as split_block but update cfg_layout structures. */
4631 cfg_layout_split_block (basic_block bb
, void *insnp
)
4633 rtx insn
= (rtx
) insnp
;
4634 basic_block new_bb
= rtl_split_block (bb
, insn
);
4636 BB_FOOTER (new_bb
) = BB_FOOTER (bb
);
4637 BB_FOOTER (bb
) = NULL
;
4642 /* Redirect Edge to DEST. */
4644 cfg_layout_redirect_edge_and_branch (edge e
, basic_block dest
)
4646 basic_block src
= e
->src
;
4649 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
4652 if (e
->dest
== dest
)
4655 if (e
->flags
& EDGE_CROSSING
4656 && BB_PARTITION (e
->src
) == BB_PARTITION (dest
)
4657 && simplejump_p (BB_END (src
)))
4661 "Removing crossing jump while redirecting edge form %i to %i\n",
4662 e
->src
->index
, dest
->index
);
4663 delete_insn (BB_END (src
));
4664 remove_barriers_from_footer (src
);
4665 e
->flags
|= EDGE_FALLTHRU
;
4668 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4669 && (ret
= try_redirect_by_replacing_jump (e
, dest
, true)))
4671 df_set_bb_dirty (src
);
4675 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4676 && (e
->flags
& EDGE_FALLTHRU
) && !(e
->flags
& EDGE_COMPLEX
))
4679 fprintf (dump_file
, "Redirecting entry edge from bb %i to %i\n",
4680 e
->src
->index
, dest
->index
);
4682 df_set_bb_dirty (e
->src
);
4683 redirect_edge_succ (e
, dest
);
4687 /* Redirect_edge_and_branch may decide to turn branch into fallthru edge
4688 in the case the basic block appears to be in sequence. Avoid this
4691 if (e
->flags
& EDGE_FALLTHRU
)
4693 /* Redirect any branch edges unified with the fallthru one. */
4694 if (JUMP_P (BB_END (src
))
4695 && label_is_jump_target_p (BB_HEAD (e
->dest
),
4701 fprintf (dump_file
, "Fallthru edge unified with branch "
4702 "%i->%i redirected to %i\n",
4703 e
->src
->index
, e
->dest
->index
, dest
->index
);
4704 e
->flags
&= ~EDGE_FALLTHRU
;
4705 redirected
= redirect_branch_edge (e
, dest
);
4706 gcc_assert (redirected
);
4707 redirected
->flags
|= EDGE_FALLTHRU
;
4708 df_set_bb_dirty (redirected
->src
);
4711 /* In case we are redirecting fallthru edge to the branch edge
4712 of conditional jump, remove it. */
4713 if (EDGE_COUNT (src
->succs
) == 2)
4715 /* Find the edge that is different from E. */
4716 edge s
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
);
4719 && any_condjump_p (BB_END (src
))
4720 && onlyjump_p (BB_END (src
)))
4721 delete_insn (BB_END (src
));
4724 fprintf (dump_file
, "Redirecting fallthru edge %i->%i to %i\n",
4725 e
->src
->index
, e
->dest
->index
, dest
->index
);
4726 ret
= redirect_edge_succ_nodup (e
, dest
);
4729 ret
= redirect_branch_edge (e
, dest
);
4734 fixup_partition_crossing (ret
);
4735 /* We don't want simplejumps in the insn stream during cfglayout. */
4736 gcc_assert (!simplejump_p (BB_END (src
)) || CROSSING_JUMP_P (BB_END (src
)));
4738 df_set_bb_dirty (src
);
4742 /* Simple wrapper as we always can redirect fallthru edges. */
4744 cfg_layout_redirect_edge_and_branch_force (edge e
, basic_block dest
)
4746 edge redirected
= cfg_layout_redirect_edge_and_branch (e
, dest
);
4748 gcc_assert (redirected
);
4752 /* Same as delete_basic_block but update cfg_layout structures. */
4755 cfg_layout_delete_block (basic_block bb
)
4757 rtx_insn
*insn
, *next
, *prev
= PREV_INSN (BB_HEAD (bb
)), *remaints
;
4762 next
= BB_HEAD (bb
);
4764 SET_NEXT_INSN (prev
) = BB_HEADER (bb
);
4766 set_first_insn (BB_HEADER (bb
));
4767 SET_PREV_INSN (BB_HEADER (bb
)) = prev
;
4768 insn
= BB_HEADER (bb
);
4769 while (NEXT_INSN (insn
))
4770 insn
= NEXT_INSN (insn
);
4771 SET_NEXT_INSN (insn
) = next
;
4772 SET_PREV_INSN (next
) = insn
;
4774 next
= NEXT_INSN (BB_END (bb
));
4777 insn
= BB_FOOTER (bb
);
4780 if (BARRIER_P (insn
))
4782 if (PREV_INSN (insn
))
4783 SET_NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
4785 BB_FOOTER (bb
) = NEXT_INSN (insn
);
4786 if (NEXT_INSN (insn
))
4787 SET_PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
4791 insn
= NEXT_INSN (insn
);
4796 SET_NEXT_INSN (insn
) = BB_FOOTER (bb
);
4797 SET_PREV_INSN (BB_FOOTER (bb
)) = insn
;
4798 while (NEXT_INSN (insn
))
4799 insn
= NEXT_INSN (insn
);
4800 SET_NEXT_INSN (insn
) = next
;
4802 SET_PREV_INSN (next
) = insn
;
4804 set_last_insn (insn
);
4807 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
4808 to
= &BB_HEADER (bb
->next_bb
);
4810 to
= &cfg_layout_function_footer
;
4812 rtl_delete_block (bb
);
4815 prev
= NEXT_INSN (prev
);
4817 prev
= get_insns ();
4819 next
= PREV_INSN (next
);
4821 next
= get_last_insn ();
4823 if (next
&& NEXT_INSN (next
) != prev
)
4825 remaints
= unlink_insn_chain (prev
, next
);
4827 while (NEXT_INSN (insn
))
4828 insn
= NEXT_INSN (insn
);
4829 SET_NEXT_INSN (insn
) = *to
;
4831 SET_PREV_INSN (*to
) = insn
;
4836 /* Return true when blocks A and B can be safely merged. */
4839 cfg_layout_can_merge_blocks_p (basic_block a
, basic_block b
)
4841 /* If we are partitioning hot/cold basic blocks, we don't want to
4842 mess up unconditional or indirect jumps that cross between hot
4845 Basic block partitioning may result in some jumps that appear to
4846 be optimizable (or blocks that appear to be mergeable), but which really
4847 must be left untouched (they are required to make it safely across
4848 partition boundaries). See the comments at the top of
4849 bb-reorder.cc:partition_hot_cold_basic_blocks for complete details. */
4851 if (BB_PARTITION (a
) != BB_PARTITION (b
))
4854 /* Protect the loop latches. */
4855 if (current_loops
&& b
->loop_father
->latch
== b
)
4858 /* If we would end up moving B's instructions, make sure it doesn't fall
4859 through into the exit block, since we cannot recover from a fallthrough
4860 edge into the exit block occurring in the middle of a function. */
4861 if (NEXT_INSN (BB_END (a
)) != BB_HEAD (b
))
4863 edge e
= find_fallthru_edge (b
->succs
);
4864 if (e
&& e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4868 /* There must be exactly one edge in between the blocks. */
4869 return (single_succ_p (a
)
4870 && single_succ (a
) == b
4871 && single_pred_p (b
) == 1
4873 /* Must be simple edge. */
4874 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
4875 && a
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4876 && b
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
4877 /* If the jump insn has side effects, we can't kill the edge.
4878 When not optimizing, try_redirect_by_replacing_jump will
4879 not allow us to redirect an edge by replacing a table jump. */
4880 && (!JUMP_P (BB_END (a
))
4881 || ((!optimize
|| reload_completed
)
4882 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
4885 /* Merge block A and B. The blocks must be mergeable. */
4888 cfg_layout_merge_blocks (basic_block a
, basic_block b
)
4890 /* If B is a forwarder block whose outgoing edge has no location, we'll
4891 propagate the locus of the edge between A and B onto it. */
4892 const bool forward_edge_locus
4893 = (b
->flags
& BB_FORWARDER_BLOCK
) != 0
4894 && LOCATION_LOCUS (EDGE_SUCC (b
, 0)->goto_locus
) == UNKNOWN_LOCATION
;
4897 gcc_checking_assert (cfg_layout_can_merge_blocks_p (a
, b
));
4900 fprintf (dump_file
, "Merging block %d into block %d...\n", b
->index
,
4903 /* If there was a CODE_LABEL beginning B, delete it. */
4904 if (LABEL_P (BB_HEAD (b
)))
4906 delete_insn (BB_HEAD (b
));
4909 /* We should have fallthru edge in a, or we can do dummy redirection to get
4911 if (JUMP_P (BB_END (a
)))
4912 try_redirect_by_replacing_jump (EDGE_SUCC (a
, 0), b
, true);
4913 gcc_assert (!JUMP_P (BB_END (a
)));
4915 /* If not optimizing, preserve the locus of the single edge between
4916 blocks A and B if necessary by emitting a nop. */
4918 && !forward_edge_locus
4919 && !DECL_IGNORED_P (current_function_decl
))
4920 emit_nop_for_unique_locus_between (a
, b
);
4922 /* Move things from b->footer after a->footer. */
4926 BB_FOOTER (a
) = BB_FOOTER (b
);
4929 rtx_insn
*last
= BB_FOOTER (a
);
4931 while (NEXT_INSN (last
))
4932 last
= NEXT_INSN (last
);
4933 SET_NEXT_INSN (last
) = BB_FOOTER (b
);
4934 SET_PREV_INSN (BB_FOOTER (b
)) = last
;
4936 BB_FOOTER (b
) = NULL
;
4939 /* Move things from b->header before a->footer.
4940 Note that this may include dead tablejump data, but we don't clean
4941 those up until we go out of cfglayout mode. */
4944 if (! BB_FOOTER (a
))
4945 BB_FOOTER (a
) = BB_HEADER (b
);
4948 rtx_insn
*last
= BB_HEADER (b
);
4950 while (NEXT_INSN (last
))
4951 last
= NEXT_INSN (last
);
4952 SET_NEXT_INSN (last
) = BB_FOOTER (a
);
4953 SET_PREV_INSN (BB_FOOTER (a
)) = last
;
4954 BB_FOOTER (a
) = BB_HEADER (b
);
4956 BB_HEADER (b
) = NULL
;
4959 /* In the case basic blocks are not adjacent, move them around. */
4960 if (NEXT_INSN (BB_END (a
)) != BB_HEAD (b
))
4962 insn
= unlink_insn_chain (BB_HEAD (b
), BB_END (b
));
4964 emit_insn_after_noloc (insn
, BB_END (a
), a
);
4966 /* Otherwise just re-associate the instructions. */
4970 BB_END (a
) = BB_END (b
);
4973 /* emit_insn_after_noloc doesn't call df_insn_change_bb.
4974 We need to explicitly call. */
4975 update_bb_for_insn_chain (insn
, BB_END (b
), a
);
4977 /* Skip possible DELETED_LABEL insn. */
4978 if (!NOTE_INSN_BASIC_BLOCK_P (insn
))
4979 insn
= NEXT_INSN (insn
);
4980 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
4981 BB_HEAD (b
) = BB_END (b
) = NULL
;
4984 df_bb_delete (b
->index
);
4986 if (forward_edge_locus
)
4987 EDGE_SUCC (b
, 0)->goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
4990 fprintf (dump_file
, "Merged blocks %d and %d.\n", a
->index
, b
->index
);
4996 cfg_layout_split_edge (edge e
)
4998 basic_block new_bb
=
4999 create_basic_block (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
5000 ? NEXT_INSN (BB_END (e
->src
)) : get_insns (),
5003 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
5004 BB_COPY_PARTITION (new_bb
, e
->src
);
5006 BB_COPY_PARTITION (new_bb
, e
->dest
);
5007 make_edge (new_bb
, e
->dest
, EDGE_FALLTHRU
);
5008 redirect_edge_and_branch_force (e
, new_bb
);
5013 /* Do postprocessing after making a forwarder block joined by edge FALLTHRU. */
5016 rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED
)
5020 /* Return true if BB contains only labels or non-executable
5024 rtl_block_empty_p (basic_block bb
)
5028 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
5029 || bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
5032 FOR_BB_INSNS (bb
, insn
)
5033 if (NONDEBUG_INSN_P (insn
)
5034 && (!any_uncondjump_p (insn
) || !onlyjump_p (insn
)))
5040 /* Split a basic block if it ends with a conditional branch and if
5041 the other part of the block is not empty. */
5044 rtl_split_block_before_cond_jump (basic_block bb
)
5047 rtx_insn
*split_point
= NULL
;
5048 rtx_insn
*last
= NULL
;
5049 bool found_code
= false;
5051 FOR_BB_INSNS (bb
, insn
)
5053 if (any_condjump_p (insn
))
5055 else if (NONDEBUG_INSN_P (insn
))
5060 /* Did not find everything. */
5061 if (found_code
&& split_point
)
5062 return split_block (bb
, split_point
)->dest
;
5067 /* Return true if BB ends with a call, possibly followed by some
5068 instructions that must stay with the call, false otherwise. */
5071 rtl_block_ends_with_call_p (basic_block bb
)
5073 rtx_insn
*insn
= BB_END (bb
);
5075 while (!CALL_P (insn
)
5076 && insn
!= BB_HEAD (bb
)
5077 && (keep_with_call_p (insn
)
5079 || DEBUG_INSN_P (insn
)))
5080 insn
= PREV_INSN (insn
);
5081 return (CALL_P (insn
));
5084 /* Return true if BB ends with a conditional branch, false otherwise. */
5087 rtl_block_ends_with_condjump_p (const_basic_block bb
)
5089 return any_condjump_p (BB_END (bb
));
5092 /* Return true if we need to add fake edge to exit.
5093 Helper function for rtl_flow_call_edges_add. */
5096 need_fake_edge_p (const rtx_insn
*insn
)
5102 && !SIBLING_CALL_P (insn
)
5103 && !find_reg_note (insn
, REG_NORETURN
, NULL
)
5104 && !(RTL_CONST_OR_PURE_CALL_P (insn
))))
5107 return ((GET_CODE (PATTERN (insn
)) == ASM_OPERANDS
5108 && MEM_VOLATILE_P (PATTERN (insn
)))
5109 || (GET_CODE (PATTERN (insn
)) == PARALLEL
5110 && asm_noperands (insn
) != -1
5111 && MEM_VOLATILE_P (XVECEXP (PATTERN (insn
), 0, 0)))
5112 || GET_CODE (PATTERN (insn
)) == ASM_INPUT
);
5115 /* Add fake edges to the function exit for any non constant and non noreturn
5116 calls, volatile inline assembly in the bitmap of blocks specified by
5117 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
5120 The goal is to expose cases in which entering a basic block does not imply
5121 that all subsequent instructions must be executed. */
5124 rtl_flow_call_edges_add (sbitmap blocks
)
5127 int blocks_split
= 0;
5128 int last_bb
= last_basic_block_for_fn (cfun
);
5129 bool check_last_block
= false;
5131 if (n_basic_blocks_for_fn (cfun
) == NUM_FIXED_BLOCKS
)
5135 check_last_block
= true;
5137 check_last_block
= bitmap_bit_p (blocks
,
5138 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
->index
);
5140 /* In the last basic block, before epilogue generation, there will be
5141 a fallthru edge to EXIT. Special care is required if the last insn
5142 of the last basic block is a call because make_edge folds duplicate
5143 edges, which would result in the fallthru edge also being marked
5144 fake, which would result in the fallthru edge being removed by
5145 remove_fake_edges, which would result in an invalid CFG.
5147 Moreover, we can't elide the outgoing fake edge, since the block
5148 profiler needs to take this into account in order to solve the minimal
5149 spanning tree in the case that the call doesn't return.
5151 Handle this by adding a dummy instruction in a new last basic block. */
5152 if (check_last_block
)
5154 basic_block bb
= EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
;
5155 rtx_insn
*insn
= BB_END (bb
);
5157 /* Back up past insns that must be kept in the same block as a call. */
5158 while (insn
!= BB_HEAD (bb
)
5159 && keep_with_call_p (insn
))
5160 insn
= PREV_INSN (insn
);
5162 if (need_fake_edge_p (insn
))
5166 e
= find_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
5169 insert_insn_on_edge (gen_use (const0_rtx
), e
);
5170 commit_edge_insertions ();
5175 /* Now add fake edges to the function exit for any non constant
5176 calls since there is no way that we can determine if they will
5179 for (i
= NUM_FIXED_BLOCKS
; i
< last_bb
; i
++)
5181 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
5183 rtx_insn
*prev_insn
;
5188 if (blocks
&& !bitmap_bit_p (blocks
, i
))
5191 for (insn
= BB_END (bb
); ; insn
= prev_insn
)
5193 prev_insn
= PREV_INSN (insn
);
5194 if (need_fake_edge_p (insn
))
5197 rtx_insn
*split_at_insn
= insn
;
5199 /* Don't split the block between a call and an insn that should
5200 remain in the same block as the call. */
5202 while (split_at_insn
!= BB_END (bb
)
5203 && keep_with_call_p (NEXT_INSN (split_at_insn
)))
5204 split_at_insn
= NEXT_INSN (split_at_insn
);
5206 /* The handling above of the final block before the epilogue
5207 should be enough to verify that there is no edge to the exit
5208 block in CFG already. Calling make_edge in such case would
5209 cause us to mark that edge as fake and remove it later. */
5211 if (flag_checking
&& split_at_insn
== BB_END (bb
))
5213 e
= find_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
5214 gcc_assert (e
== NULL
);
5217 /* Note that the following may create a new basic block
5218 and renumber the existing basic blocks. */
5219 if (split_at_insn
!= BB_END (bb
))
5221 e
= split_block (bb
, split_at_insn
);
5226 edge ne
= make_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), EDGE_FAKE
);
5227 ne
->probability
= profile_probability::guessed_never ();
5230 if (insn
== BB_HEAD (bb
))
5236 verify_flow_info ();
5238 return blocks_split
;
5241 /* Add COMP_RTX as a condition at end of COND_BB. FIRST_HEAD is
5242 the conditional branch target, SECOND_HEAD should be the fall-thru
5243 there is no need to handle this here the loop versioning code handles
5244 this. the reason for SECON_HEAD is that it is needed for condition
5245 in trees, and this should be of the same type since it is a hook. */
5247 rtl_lv_add_condition_to_bb (basic_block first_head
,
5248 basic_block second_head ATTRIBUTE_UNUSED
,
5249 basic_block cond_bb
, void *comp_rtx
)
5251 rtx_code_label
*label
;
5252 rtx_insn
*seq
, *jump
;
5253 rtx op0
= XEXP ((rtx
)comp_rtx
, 0);
5254 rtx op1
= XEXP ((rtx
)comp_rtx
, 1);
5255 enum rtx_code comp
= GET_CODE ((rtx
)comp_rtx
);
5259 label
= block_label (first_head
);
5260 mode
= GET_MODE (op0
);
5261 if (mode
== VOIDmode
)
5262 mode
= GET_MODE (op1
);
5265 op0
= force_operand (op0
, NULL_RTX
);
5266 op1
= force_operand (op1
, NULL_RTX
);
5267 do_compare_rtx_and_jump (op0
, op1
, comp
, 0, mode
, NULL_RTX
, NULL
, label
,
5268 profile_probability::uninitialized ());
5269 jump
= get_last_insn ();
5270 JUMP_LABEL (jump
) = label
;
5271 LABEL_NUSES (label
)++;
5275 /* Add the new cond, in the new head. */
5276 emit_insn_after (seq
, BB_END (cond_bb
));
5280 /* Given a block B with unconditional branch at its end, get the
5281 store the return the branch edge and the fall-thru edge in
5282 BRANCH_EDGE and FALLTHRU_EDGE respectively. */
5284 rtl_extract_cond_bb_edges (basic_block b
, edge
*branch_edge
,
5285 edge
*fallthru_edge
)
5287 edge e
= EDGE_SUCC (b
, 0);
5289 if (e
->flags
& EDGE_FALLTHRU
)
5292 *branch_edge
= EDGE_SUCC (b
, 1);
5297 *fallthru_edge
= EDGE_SUCC (b
, 1);
5302 init_rtl_bb_info (basic_block bb
)
5304 gcc_assert (!bb
->il
.x
.rtl
);
5305 bb
->il
.x
.head_
= NULL
;
5306 bb
->il
.x
.rtl
= ggc_cleared_alloc
<rtl_bb_info
> ();
5310 rtl_bb_info_initialized_p (basic_block bb
)
5312 return bb
->il
.x
.rtl
;
5315 /* Returns true if it is possible to remove edge E by redirecting
5316 it to the destination of the other edge from E->src. */
5319 rtl_can_remove_branch_p (const_edge e
)
5321 const_basic_block src
= e
->src
;
5322 const_basic_block target
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
;
5323 const rtx_insn
*insn
= BB_END (src
);
5326 /* The conditions are taken from try_redirect_by_replacing_jump. */
5327 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
5330 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
5333 if (BB_PARTITION (src
) != BB_PARTITION (target
))
5336 if (!onlyjump_p (insn
)
5337 || tablejump_p (insn
, NULL
, NULL
))
5340 set
= single_set (insn
);
5341 if (!set
|| side_effects_p (set
))
5348 rtl_duplicate_bb (basic_block bb
, copy_bb_data
*id
)
5350 bb
= cfg_layout_duplicate_bb (bb
, id
);
5355 /* Do book-keeping of basic block BB for the profile consistency checker.
5356 Store the counting in RECORD. */
5358 rtl_account_profile_record (basic_block bb
, struct profile_record
*record
)
5361 FOR_BB_INSNS (bb
, insn
)
5364 record
->size
+= insn_cost (insn
, false);
5367 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.ipa ().initialized_p ()
5368 && ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.ipa ().nonzero_p ()
5369 && bb
->count
.ipa ().initialized_p ())
5371 += insn_cost (insn
, true) * bb
->count
.ipa ().to_gcov_type ();
5373 else if (bb
->count
.initialized_p ()
5374 && ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.initialized_p ())
5376 += insn_cost (insn
, true)
5377 * bb
->count
.to_sreal_scale
5378 (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
).to_double ();
5380 record
->time
+= insn_cost (insn
, true);
5384 /* Implementation of CFG manipulation for linearized RTL. */
5385 struct cfg_hooks rtl_cfg_hooks
= {
5387 rtl_verify_flow_info
,
5389 rtl_dump_bb_for_graph
,
5390 rtl_create_basic_block
,
5391 rtl_redirect_edge_and_branch
,
5392 rtl_redirect_edge_and_branch_force
,
5393 rtl_can_remove_branch_p
,
5396 rtl_move_block_after
,
5397 rtl_can_merge_blocks
, /* can_merge_blocks_p */
5401 cfg_layout_can_duplicate_bb_p
,
5404 rtl_make_forwarder_block
,
5405 rtl_tidy_fallthru_edge
,
5406 rtl_force_nonfallthru
,
5407 rtl_block_ends_with_call_p
,
5408 rtl_block_ends_with_condjump_p
,
5409 rtl_flow_call_edges_add
,
5410 NULL
, /* execute_on_growing_pred */
5411 NULL
, /* execute_on_shrinking_pred */
5412 NULL
, /* duplicate loop for trees */
5413 NULL
, /* lv_add_condition_to_bb */
5414 NULL
, /* lv_adjust_loop_header_phi*/
5415 NULL
, /* extract_cond_bb_edges */
5416 NULL
, /* flush_pending_stmts */
5417 rtl_block_empty_p
, /* block_empty_p */
5418 rtl_split_block_before_cond_jump
, /* split_block_before_cond_jump */
5419 rtl_account_profile_record
,
5422 /* Implementation of CFG manipulation for cfg layout RTL, where
5423 basic block connected via fallthru edges does not have to be adjacent.
5424 This representation will hopefully become the default one in future
5425 version of the compiler. */
5427 struct cfg_hooks cfg_layout_rtl_cfg_hooks
= {
5429 rtl_verify_flow_info_1
,
5431 rtl_dump_bb_for_graph
,
5432 cfg_layout_create_basic_block
,
5433 cfg_layout_redirect_edge_and_branch
,
5434 cfg_layout_redirect_edge_and_branch_force
,
5435 rtl_can_remove_branch_p
,
5436 cfg_layout_delete_block
,
5437 cfg_layout_split_block
,
5438 rtl_move_block_after
,
5439 cfg_layout_can_merge_blocks_p
,
5440 cfg_layout_merge_blocks
,
5443 cfg_layout_can_duplicate_bb_p
,
5444 cfg_layout_duplicate_bb
,
5445 cfg_layout_split_edge
,
5446 rtl_make_forwarder_block
,
5447 NULL
, /* tidy_fallthru_edge */
5448 rtl_force_nonfallthru
,
5449 rtl_block_ends_with_call_p
,
5450 rtl_block_ends_with_condjump_p
,
5451 rtl_flow_call_edges_add
,
5452 NULL
, /* execute_on_growing_pred */
5453 NULL
, /* execute_on_shrinking_pred */
5454 duplicate_loop_body_to_header_edge
, /* duplicate loop for rtl */
5455 rtl_lv_add_condition_to_bb
, /* lv_add_condition_to_bb */
5456 NULL
, /* lv_adjust_loop_header_phi*/
5457 rtl_extract_cond_bb_edges
, /* extract_cond_bb_edges */
5458 NULL
, /* flush_pending_stmts */
5459 rtl_block_empty_p
, /* block_empty_p */
5460 rtl_split_block_before_cond_jump
, /* split_block_before_cond_jump */
5461 rtl_account_profile_record
,
5464 #include "gt-cfgrtl.h"
5467 # pragma GCC diagnostic pop