1 /* Control flow graph manipulation code for GNU compiler.
2 Copyright (C) 1987-2022 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* This file contains low level functions to manipulate the CFG and analyze it
21 that are aware of the RTL intermediate language.
23 Available functionality:
24 - Basic CFG/RTL manipulation API documented in cfghooks.h
25 - CFG-aware instruction chain manipulation
26 delete_insn, delete_insn_chain
27 - Edge splitting and committing to edges
28 insert_insn_on_edge, commit_edge_insertions
29 - CFG updating after insn simplification
30 purge_dead_edges, purge_all_dead_edges
31 - CFG fixing after coarse manipulation
34 Functions not supposed for generic use:
35 - Infrastructure to determine quickly basic block for insn
36 compute_bb_for_insn, update_bb_for_insn, set_block_for_insn,
37 - Edge redirection with updating and optimizing of insn chain
38 block_label, tidy_fallthru_edge, force_nonfallthru */
42 #include "coretypes.h"
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 int can_delete_note_p (const rtx_note
*);
87 static int can_delete_label_p (const rtx_code_label
*);
88 static basic_block
rtl_split_edge (edge
);
89 static bool rtl_move_block_after (basic_block
, basic_block
);
90 static int rtl_verify_flow_info (void);
91 static basic_block
cfg_layout_split_block (basic_block
, void *);
92 static edge
cfg_layout_redirect_edge_and_branch (edge
, basic_block
);
93 static basic_block
cfg_layout_redirect_edge_and_branch_force (edge
, basic_block
);
94 static void cfg_layout_delete_block (basic_block
);
95 static void rtl_delete_block (basic_block
);
96 static basic_block
rtl_redirect_edge_and_branch_force (edge
, basic_block
);
97 static edge
rtl_redirect_edge_and_branch (edge
, basic_block
);
98 static basic_block
rtl_split_block (basic_block
, void *);
99 static void rtl_dump_bb (FILE *, basic_block
, int, dump_flags_t
);
100 static int 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 (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
;
465 const pass_data pass_data_free_cfg
=
468 "*free_cfg", /* name */
469 OPTGROUP_NONE
, /* optinfo_flags */
471 0, /* properties_required */
472 0, /* properties_provided */
473 PROP_cfg
, /* properties_destroyed */
474 0, /* todo_flags_start */
475 0, /* todo_flags_finish */
478 class pass_free_cfg
: public rtl_opt_pass
481 pass_free_cfg (gcc::context
*ctxt
)
482 : rtl_opt_pass (pass_data_free_cfg
, ctxt
)
485 /* opt_pass methods: */
486 virtual unsigned int execute (function
*);
488 }; // class pass_free_cfg
491 pass_free_cfg::execute (function
*)
493 /* The resource.cc machinery uses DF but the CFG isn't guaranteed to be
494 valid at that point so it would be too late to call df_analyze. */
495 if (DELAY_SLOTS
&& optimize
> 0 && flag_delayed_branch
)
497 df_note_add_problem ();
501 if (crtl
->has_bb_partition
)
502 insert_section_boundary_note ();
511 make_pass_free_cfg (gcc::context
*ctxt
)
513 return new pass_free_cfg (ctxt
);
516 /* Return RTX to emit after when we want to emit code on the entry of function. */
518 entry_of_function (void)
520 return (n_basic_blocks_for_fn (cfun
) > NUM_FIXED_BLOCKS
?
521 BB_HEAD (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
) : get_insns ());
524 /* Emit INSN at the entry point of the function, ensuring that it is only
525 executed once per function. */
527 emit_insn_at_entry (rtx insn
)
529 edge_iterator ei
= ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
);
530 edge e
= ei_safe_edge (ei
);
531 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
533 insert_insn_on_edge (insn
, e
);
534 commit_edge_insertions ();
537 /* Update BLOCK_FOR_INSN of insns between BEGIN and END
538 (or BARRIER if found) and notify df of the bb change.
539 The insn chain range is inclusive
540 (i.e. both BEGIN and END will be updated. */
543 update_bb_for_insn_chain (rtx_insn
*begin
, rtx_insn
*end
, basic_block bb
)
547 end
= NEXT_INSN (end
);
548 for (insn
= begin
; insn
!= end
; insn
= NEXT_INSN (insn
))
549 if (!BARRIER_P (insn
))
550 df_insn_change_bb (insn
, bb
);
553 /* Update BLOCK_FOR_INSN of insns in BB to BB,
554 and notify df of the change. */
557 update_bb_for_insn (basic_block bb
)
559 update_bb_for_insn_chain (BB_HEAD (bb
), BB_END (bb
), bb
);
563 /* Like active_insn_p, except keep the return value use or clobber around
564 even after reload. */
567 flow_active_insn_p (const rtx_insn
*insn
)
569 if (active_insn_p (insn
))
572 /* A clobber of the function return value exists for buggy
573 programs that fail to return a value. Its effect is to
574 keep the return value from being live across the entire
575 function. If we allow it to be skipped, we introduce the
576 possibility for register lifetime confusion.
577 Similarly, keep a USE of the function return value, otherwise
578 the USE is dropped and we could fail to thread jump if USE
579 appears on some paths and not on others, see PR90257. */
580 if ((GET_CODE (PATTERN (insn
)) == CLOBBER
581 || GET_CODE (PATTERN (insn
)) == USE
)
582 && REG_P (XEXP (PATTERN (insn
), 0))
583 && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn
), 0)))
589 /* Return true if the block has no effect and only forwards control flow to
590 its single destination. */
593 contains_no_active_insn_p (const_basic_block bb
)
597 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
598 || bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
599 || !single_succ_p (bb
)
600 || (single_succ_edge (bb
)->flags
& EDGE_FAKE
) != 0)
603 for (insn
= BB_HEAD (bb
); insn
!= BB_END (bb
); insn
= NEXT_INSN (insn
))
604 if (INSN_P (insn
) && flow_active_insn_p (insn
))
607 return (!INSN_P (insn
)
608 || (JUMP_P (insn
) && simplejump_p (insn
))
609 || !flow_active_insn_p (insn
));
612 /* Likewise, but protect loop latches, headers and preheaders. */
613 /* FIXME: Make this a cfg hook. */
616 forwarder_block_p (const_basic_block bb
)
618 if (!contains_no_active_insn_p (bb
))
621 /* Protect loop latches, headers and preheaders. */
625 if (bb
->loop_father
->header
== bb
)
627 dest
= EDGE_SUCC (bb
, 0)->dest
;
628 if (dest
->loop_father
->header
== dest
)
635 /* Return nonzero if we can reach target from src by falling through. */
636 /* FIXME: Make this a cfg hook, the result is only valid in cfgrtl mode. */
639 can_fallthru (basic_block src
, basic_block target
)
641 rtx_insn
*insn
= BB_END (src
);
646 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
648 if (src
->next_bb
!= target
)
651 /* ??? Later we may add code to move jump tables offline. */
652 if (tablejump_p (insn
, NULL
, NULL
))
655 FOR_EACH_EDGE (e
, ei
, src
->succs
)
656 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
657 && e
->flags
& EDGE_FALLTHRU
)
660 insn2
= BB_HEAD (target
);
661 if (!active_insn_p (insn2
))
662 insn2
= next_active_insn (insn2
);
664 return next_active_insn (insn
) == insn2
;
667 /* Return nonzero if we could reach target from src by falling through,
668 if the target was made adjacent. If we already have a fall-through
669 edge to the exit block, we can't do that. */
671 could_fall_through (basic_block src
, basic_block target
)
676 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
678 FOR_EACH_EDGE (e
, ei
, src
->succs
)
679 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
680 && e
->flags
& EDGE_FALLTHRU
)
685 /* Return the NOTE_INSN_BASIC_BLOCK of BB. */
687 bb_note (basic_block bb
)
693 note
= NEXT_INSN (note
);
695 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
696 return as_a
<rtx_note
*> (note
);
699 /* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK
700 note associated with the BLOCK. */
703 first_insn_after_basic_block_note (basic_block block
)
707 /* Get the first instruction in the block. */
708 insn
= BB_HEAD (block
);
710 if (insn
== NULL_RTX
)
713 insn
= NEXT_INSN (insn
);
714 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
716 return NEXT_INSN (insn
);
719 /* Creates a new basic block just after basic block BB by splitting
720 everything after specified instruction INSNP. */
723 rtl_split_block (basic_block bb
, void *insnp
)
726 rtx_insn
*insn
= (rtx_insn
*) insnp
;
732 insn
= first_insn_after_basic_block_note (bb
);
736 rtx_insn
*next
= insn
;
738 insn
= PREV_INSN (insn
);
740 /* If the block contains only debug insns, insn would have
741 been NULL in a non-debug compilation, and then we'd end
742 up emitting a DELETED note. For -fcompare-debug
743 stability, emit the note too. */
744 if (insn
!= BB_END (bb
)
745 && DEBUG_INSN_P (next
)
746 && DEBUG_INSN_P (BB_END (bb
)))
748 while (next
!= BB_END (bb
) && DEBUG_INSN_P (next
))
749 next
= NEXT_INSN (next
);
751 if (next
== BB_END (bb
))
752 emit_note_after (NOTE_INSN_DELETED
, next
);
756 insn
= get_last_insn ();
759 /* We probably should check type of the insn so that we do not create
760 inconsistent cfg. It is checked in verify_flow_info anyway, so do not
762 if (insn
== BB_END (bb
))
763 emit_note_after (NOTE_INSN_DELETED
, insn
);
765 /* Create the new basic block. */
766 new_bb
= create_basic_block (NEXT_INSN (insn
), BB_END (bb
), bb
);
767 BB_COPY_PARTITION (new_bb
, bb
);
770 /* Redirect the outgoing edges. */
771 new_bb
->succs
= bb
->succs
;
773 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
776 /* The new block starts off being dirty. */
777 df_set_bb_dirty (bb
);
781 /* Return true if the single edge between blocks A and B is the only place
782 in RTL which holds some unique locus. */
785 unique_locus_on_edge_between_p (basic_block a
, basic_block b
)
787 const location_t goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
788 rtx_insn
*insn
, *end
;
790 if (LOCATION_LOCUS (goto_locus
) == UNKNOWN_LOCATION
)
793 /* First scan block A backward. */
795 end
= PREV_INSN (BB_HEAD (a
));
796 while (insn
!= end
&& (!NONDEBUG_INSN_P (insn
) || !INSN_HAS_LOCATION (insn
)))
797 insn
= PREV_INSN (insn
);
799 if (insn
!= end
&& INSN_LOCATION (insn
) == goto_locus
)
802 /* Then scan block B forward. */
806 end
= NEXT_INSN (BB_END (b
));
807 while (insn
!= end
&& !NONDEBUG_INSN_P (insn
))
808 insn
= NEXT_INSN (insn
);
810 if (insn
!= end
&& INSN_HAS_LOCATION (insn
)
811 && INSN_LOCATION (insn
) == goto_locus
)
818 /* If the single edge between blocks A and B is the only place in RTL which
819 holds some unique locus, emit a nop with that locus between the blocks. */
822 emit_nop_for_unique_locus_between (basic_block a
, basic_block b
)
824 if (!unique_locus_on_edge_between_p (a
, b
))
827 BB_END (a
) = emit_insn_after_noloc (gen_nop (), BB_END (a
), a
);
828 INSN_LOCATION (BB_END (a
)) = EDGE_SUCC (a
, 0)->goto_locus
;
831 /* Blocks A and B are to be merged into a single block A. The insns
832 are already contiguous. */
835 rtl_merge_blocks (basic_block a
, basic_block b
)
837 /* If B is a forwarder block whose outgoing edge has no location, we'll
838 propagate the locus of the edge between A and B onto it. */
839 const bool forward_edge_locus
840 = (b
->flags
& BB_FORWARDER_BLOCK
) != 0
841 && LOCATION_LOCUS (EDGE_SUCC (b
, 0)->goto_locus
) == UNKNOWN_LOCATION
;
842 rtx_insn
*b_head
= BB_HEAD (b
), *b_end
= BB_END (b
), *a_end
= BB_END (a
);
843 rtx_insn
*del_first
= NULL
, *del_last
= NULL
;
844 rtx_insn
*b_debug_start
= b_end
, *b_debug_end
= b_end
;
848 fprintf (dump_file
, "Merging block %d into block %d...\n", b
->index
,
851 while (DEBUG_INSN_P (b_end
))
852 b_end
= PREV_INSN (b_debug_start
= b_end
);
854 /* If there was a CODE_LABEL beginning B, delete it. */
855 if (LABEL_P (b_head
))
857 /* Detect basic blocks with nothing but a label. This can happen
858 in particular at the end of a function. */
862 del_first
= del_last
= b_head
;
863 b_head
= NEXT_INSN (b_head
);
866 /* Delete the basic block note and handle blocks containing just that
868 if (NOTE_INSN_BASIC_BLOCK_P (b_head
))
876 b_head
= NEXT_INSN (b_head
);
879 /* If there was a jump out of A, delete it. */
884 for (prev
= PREV_INSN (a_end
); ; prev
= PREV_INSN (prev
))
886 || NOTE_INSN_BASIC_BLOCK_P (prev
)
887 || prev
== BB_HEAD (a
))
892 a_end
= PREV_INSN (del_first
);
894 else if (BARRIER_P (NEXT_INSN (a_end
)))
895 del_first
= NEXT_INSN (a_end
);
897 /* Delete everything marked above as well as crap that might be
898 hanging out between the two blocks. */
900 BB_HEAD (b
) = b_empty
? NULL
: b_head
;
901 delete_insn_chain (del_first
, del_last
, true);
903 /* If not optimizing, preserve the locus of the single edge between
904 blocks A and B if necessary by emitting a nop. */
906 && !forward_edge_locus
907 && !DECL_IGNORED_P (current_function_decl
))
909 emit_nop_for_unique_locus_between (a
, b
);
913 /* Reassociate the insns of B with A. */
916 update_bb_for_insn_chain (a_end
, b_debug_end
, a
);
918 BB_END (a
) = b_debug_end
;
921 else if (b_end
!= b_debug_end
)
923 /* Move any deleted labels and other notes between the end of A
924 and the debug insns that make up B after the debug insns,
925 bringing the debug insns into A while keeping the notes after
927 if (NEXT_INSN (a_end
) != b_debug_start
)
928 reorder_insns_nobb (NEXT_INSN (a_end
), PREV_INSN (b_debug_start
),
930 update_bb_for_insn_chain (b_debug_start
, b_debug_end
, a
);
931 BB_END (a
) = b_debug_end
;
934 df_bb_delete (b
->index
);
936 if (forward_edge_locus
)
937 EDGE_SUCC (b
, 0)->goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
940 fprintf (dump_file
, "Merged blocks %d and %d.\n", a
->index
, b
->index
);
944 /* Return true when block A and B can be merged. */
947 rtl_can_merge_blocks (basic_block a
, basic_block b
)
949 /* If we are partitioning hot/cold basic blocks, we don't want to
950 mess up unconditional or indirect jumps that cross between hot
953 Basic block partitioning may result in some jumps that appear to
954 be optimizable (or blocks that appear to be mergeable), but which really
955 must be left untouched (they are required to make it safely across
956 partition boundaries). See the comments at the top of
957 bb-reorder.cc:partition_hot_cold_basic_blocks for complete details. */
959 if (BB_PARTITION (a
) != BB_PARTITION (b
))
962 /* Protect the loop latches. */
963 if (current_loops
&& b
->loop_father
->latch
== b
)
966 /* There must be exactly one edge in between the blocks. */
967 return (single_succ_p (a
)
968 && single_succ (a
) == b
971 /* Must be simple edge. */
972 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
974 && a
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
975 && b
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
976 /* If the jump insn has side effects,
977 we can't kill the edge. */
978 && (!JUMP_P (BB_END (a
))
980 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
983 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
987 block_label (basic_block block
)
989 if (block
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
992 if (!LABEL_P (BB_HEAD (block
)))
994 BB_HEAD (block
) = emit_label_before (gen_label_rtx (), BB_HEAD (block
));
997 return as_a
<rtx_code_label
*> (BB_HEAD (block
));
1000 /* Remove all barriers from BB_FOOTER of a BB. */
1003 remove_barriers_from_footer (basic_block bb
)
1005 rtx_insn
*insn
= BB_FOOTER (bb
);
1007 /* Remove barriers but keep jumptables. */
1010 if (BARRIER_P (insn
))
1012 if (PREV_INSN (insn
))
1013 SET_NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
1015 BB_FOOTER (bb
) = NEXT_INSN (insn
);
1016 if (NEXT_INSN (insn
))
1017 SET_PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
1021 insn
= NEXT_INSN (insn
);
1025 /* Attempt to perform edge redirection by replacing possibly complex jump
1026 instruction by unconditional jump or removing jump completely. This can
1027 apply only if all edges now point to the same block. The parameters and
1028 return values are equivalent to redirect_edge_and_branch. */
1031 try_redirect_by_replacing_jump (edge e
, basic_block target
, bool in_cfglayout
)
1033 basic_block src
= e
->src
;
1034 rtx_insn
*insn
= BB_END (src
);
1038 /* If we are partitioning hot/cold basic blocks, we don't want to
1039 mess up unconditional or indirect jumps that cross between hot
1042 Basic block partitioning may result in some jumps that appear to
1043 be optimizable (or blocks that appear to be mergeable), but which really
1044 must be left untouched (they are required to make it safely across
1045 partition boundaries). See the comments at the top of
1046 bb-reorder.cc:partition_hot_cold_basic_blocks for complete details. */
1048 if (BB_PARTITION (src
) != BB_PARTITION (target
))
1051 /* We can replace or remove a complex jump only when we have exactly
1052 two edges. Also, if we have exactly one outgoing edge, we can
1054 if (EDGE_COUNT (src
->succs
) >= 3
1055 /* Verify that all targets will be TARGET. Specifically, the
1056 edge that is not E must also go to TARGET. */
1057 || (EDGE_COUNT (src
->succs
) == 2
1058 && EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
!= target
))
1061 if (!onlyjump_p (insn
))
1063 if ((!optimize
|| reload_completed
) && tablejump_p (insn
, NULL
, NULL
))
1066 /* Avoid removing branch with side effects. */
1067 set
= single_set (insn
);
1068 if (!set
|| side_effects_p (set
))
1071 /* See if we can create the fallthru edge. */
1072 if (in_cfglayout
|| can_fallthru (src
, target
))
1075 fprintf (dump_file
, "Removing jump %i.\n", INSN_UID (insn
));
1078 /* Selectively unlink whole insn chain. */
1081 delete_insn_chain (insn
, BB_END (src
), false);
1082 remove_barriers_from_footer (src
);
1085 delete_insn_chain (insn
, PREV_INSN (BB_HEAD (target
)), false);
1088 /* If this already is simplejump, redirect it. */
1089 else if (simplejump_p (insn
))
1091 if (e
->dest
== target
)
1094 fprintf (dump_file
, "Redirecting jump %i from %i to %i.\n",
1095 INSN_UID (insn
), e
->dest
->index
, target
->index
);
1096 if (!redirect_jump (as_a
<rtx_jump_insn
*> (insn
),
1097 block_label (target
), 0))
1099 gcc_assert (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
));
1104 /* Cannot do anything for target exit block. */
1105 else if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1108 /* Or replace possibly complicated jump insn by simple jump insn. */
1111 rtx_code_label
*target_label
= block_label (target
);
1114 rtx_jump_table_data
*table
;
1116 emit_jump_insn_after_noloc (targetm
.gen_jump (target_label
), insn
);
1117 JUMP_LABEL (BB_END (src
)) = target_label
;
1118 LABEL_NUSES (target_label
)++;
1120 fprintf (dump_file
, "Replacing insn %i by jump %i\n",
1121 INSN_UID (insn
), INSN_UID (BB_END (src
)));
1124 delete_insn_chain (insn
, insn
, false);
1126 /* Recognize a tablejump that we are converting to a
1127 simple jump and remove its associated CODE_LABEL
1128 and ADDR_VEC or ADDR_DIFF_VEC. */
1129 if (tablejump_p (insn
, &label
, &table
))
1130 delete_insn_chain (label
, table
, false);
1132 barrier
= next_nonnote_nondebug_insn (BB_END (src
));
1133 if (!barrier
|| !BARRIER_P (barrier
))
1134 emit_barrier_after (BB_END (src
));
1137 if (barrier
!= NEXT_INSN (BB_END (src
)))
1139 /* Move the jump before barrier so that the notes
1140 which originally were or were created before jump table are
1141 inside the basic block. */
1142 rtx_insn
*new_insn
= BB_END (src
);
1144 update_bb_for_insn_chain (NEXT_INSN (BB_END (src
)),
1145 PREV_INSN (barrier
), src
);
1147 SET_NEXT_INSN (PREV_INSN (new_insn
)) = NEXT_INSN (new_insn
);
1148 SET_PREV_INSN (NEXT_INSN (new_insn
)) = PREV_INSN (new_insn
);
1150 SET_NEXT_INSN (new_insn
) = barrier
;
1151 SET_NEXT_INSN (PREV_INSN (barrier
)) = new_insn
;
1153 SET_PREV_INSN (new_insn
) = PREV_INSN (barrier
);
1154 SET_PREV_INSN (barrier
) = new_insn
;
1159 /* Keep only one edge out and set proper flags. */
1160 if (!single_succ_p (src
))
1162 gcc_assert (single_succ_p (src
));
1164 e
= single_succ_edge (src
);
1166 e
->flags
= EDGE_FALLTHRU
;
1170 e
->probability
= profile_probability::always ();
1172 if (e
->dest
!= target
)
1173 redirect_edge_succ (e
, target
);
1177 /* Subroutine of redirect_branch_edge that tries to patch the jump
1178 instruction INSN so that it reaches block NEW. Do this
1179 only when it originally reached block OLD. Return true if this
1180 worked or the original target wasn't OLD, return false if redirection
1184 patch_jump_insn (rtx_insn
*insn
, rtx_insn
*old_label
, basic_block new_bb
)
1186 rtx_jump_table_data
*table
;
1188 /* Recognize a tablejump and adjust all matching cases. */
1189 if (tablejump_p (insn
, NULL
, &table
))
1193 rtx_code_label
*new_label
= block_label (new_bb
);
1195 if (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1197 vec
= table
->get_labels ();
1199 for (j
= GET_NUM_ELEM (vec
) - 1; j
>= 0; --j
)
1200 if (XEXP (RTVEC_ELT (vec
, j
), 0) == old_label
)
1202 RTVEC_ELT (vec
, j
) = gen_rtx_LABEL_REF (Pmode
, new_label
);
1203 --LABEL_NUSES (old_label
);
1204 ++LABEL_NUSES (new_label
);
1207 /* Handle casesi dispatch insns. */
1208 if ((tmp
= tablejump_casesi_pattern (insn
)) != NULL_RTX
1209 && label_ref_label (XEXP (SET_SRC (tmp
), 2)) == old_label
)
1211 XEXP (SET_SRC (tmp
), 2) = gen_rtx_LABEL_REF (Pmode
,
1213 --LABEL_NUSES (old_label
);
1214 ++LABEL_NUSES (new_label
);
1217 else if ((tmp
= extract_asm_operands (PATTERN (insn
))) != NULL
)
1219 int i
, n
= ASM_OPERANDS_LABEL_LENGTH (tmp
);
1222 if (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1224 rtx_code_label
*new_label
= block_label (new_bb
);
1226 for (i
= 0; i
< n
; ++i
)
1228 rtx old_ref
= ASM_OPERANDS_LABEL (tmp
, i
);
1229 gcc_assert (GET_CODE (old_ref
) == LABEL_REF
);
1230 if (XEXP (old_ref
, 0) == old_label
)
1232 ASM_OPERANDS_LABEL (tmp
, i
)
1233 = gen_rtx_LABEL_REF (Pmode
, new_label
);
1234 --LABEL_NUSES (old_label
);
1235 ++LABEL_NUSES (new_label
);
1239 if (JUMP_LABEL (insn
) == old_label
)
1241 JUMP_LABEL (insn
) = new_label
;
1242 note
= find_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1244 remove_note (insn
, note
);
1248 note
= find_reg_note (insn
, REG_LABEL_TARGET
, old_label
);
1250 remove_note (insn
, note
);
1251 if (JUMP_LABEL (insn
) != new_label
1252 && !find_reg_note (insn
, REG_LABEL_TARGET
, new_label
))
1253 add_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1255 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, old_label
))
1257 XEXP (note
, 0) = new_label
;
1261 /* ?? We may play the games with moving the named labels from
1262 one basic block to the other in case only one computed_jump is
1264 if (computed_jump_p (insn
)
1265 /* A return instruction can't be redirected. */
1266 || returnjump_p (insn
))
1269 if (!currently_expanding_to_rtl
|| JUMP_LABEL (insn
) == old_label
)
1271 /* If the insn doesn't go where we think, we're confused. */
1272 gcc_assert (JUMP_LABEL (insn
) == old_label
);
1274 /* If the substitution doesn't succeed, die. This can happen
1275 if the back end emitted unrecognizable instructions or if
1276 target is exit block on some arches. Or for crossing
1278 if (!redirect_jump (as_a
<rtx_jump_insn
*> (insn
),
1279 block_label (new_bb
), 0))
1281 gcc_assert (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
1282 || CROSSING_JUMP_P (insn
));
1291 /* Redirect edge representing branch of (un)conditional jump or tablejump,
1294 redirect_branch_edge (edge e
, basic_block target
)
1296 rtx_insn
*old_label
= BB_HEAD (e
->dest
);
1297 basic_block src
= e
->src
;
1298 rtx_insn
*insn
= BB_END (src
);
1300 /* We can only redirect non-fallthru edges of jump insn. */
1301 if (e
->flags
& EDGE_FALLTHRU
)
1303 else if (!JUMP_P (insn
) && !currently_expanding_to_rtl
)
1306 if (!currently_expanding_to_rtl
)
1308 if (!patch_jump_insn (as_a
<rtx_jump_insn
*> (insn
), old_label
, target
))
1312 /* When expanding this BB might actually contain multiple
1313 jumps (i.e. not yet split by find_many_sub_basic_blocks).
1314 Redirect all of those that match our label. */
1315 FOR_BB_INSNS (src
, insn
)
1316 if (JUMP_P (insn
) && !patch_jump_insn (as_a
<rtx_jump_insn
*> (insn
),
1321 fprintf (dump_file
, "Edge %i->%i redirected to %i\n",
1322 e
->src
->index
, e
->dest
->index
, target
->index
);
1324 if (e
->dest
!= target
)
1325 e
= redirect_edge_succ_nodup (e
, target
);
1330 /* Called when edge E has been redirected to a new destination,
1331 in order to update the region crossing flag on the edge and
1335 fixup_partition_crossing (edge e
)
1337 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) || e
->dest
1338 == EXIT_BLOCK_PTR_FOR_FN (cfun
))
1340 /* If we redirected an existing edge, it may already be marked
1341 crossing, even though the new src is missing a reg crossing note.
1342 But make sure reg crossing note doesn't already exist before
1344 if (BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
))
1346 e
->flags
|= EDGE_CROSSING
;
1347 if (JUMP_P (BB_END (e
->src
)))
1348 CROSSING_JUMP_P (BB_END (e
->src
)) = 1;
1350 else if (BB_PARTITION (e
->src
) == BB_PARTITION (e
->dest
))
1352 e
->flags
&= ~EDGE_CROSSING
;
1353 /* Remove the section crossing note from jump at end of
1354 src if it exists, and if no other successors are
1356 if (JUMP_P (BB_END (e
->src
)) && CROSSING_JUMP_P (BB_END (e
->src
)))
1358 bool has_crossing_succ
= false;
1361 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
1363 has_crossing_succ
|= (e2
->flags
& EDGE_CROSSING
);
1364 if (has_crossing_succ
)
1367 if (!has_crossing_succ
)
1368 CROSSING_JUMP_P (BB_END (e
->src
)) = 0;
1373 /* Called when block BB has been reassigned to the cold partition,
1374 because it is now dominated by another cold block,
1375 to ensure that the region crossing attributes are updated. */
1378 fixup_new_cold_bb (basic_block bb
)
1383 /* This is called when a hot bb is found to now be dominated
1384 by a cold bb and therefore needs to become cold. Therefore,
1385 its preds will no longer be region crossing. Any non-dominating
1386 preds that were previously hot would also have become cold
1387 in the caller for the same region. Any preds that were previously
1388 region-crossing will be adjusted in fixup_partition_crossing. */
1389 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1391 fixup_partition_crossing (e
);
1394 /* Possibly need to make bb's successor edges region crossing,
1395 or remove stale region crossing. */
1396 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1398 /* We can't have fall-through edges across partition boundaries.
1399 Note that force_nonfallthru will do any necessary partition
1400 boundary fixup by calling fixup_partition_crossing itself. */
1401 if ((e
->flags
& EDGE_FALLTHRU
)
1402 && BB_PARTITION (bb
) != BB_PARTITION (e
->dest
)
1403 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1404 force_nonfallthru (e
);
1406 fixup_partition_crossing (e
);
1410 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
1411 expense of adding new instructions or reordering basic blocks.
1413 Function can be also called with edge destination equivalent to the TARGET.
1414 Then it should try the simplifications and do nothing if none is possible.
1416 Return edge representing the branch if transformation succeeded. Return NULL
1418 We still return NULL in case E already destinated TARGET and we didn't
1419 managed to simplify instruction stream. */
1422 rtl_redirect_edge_and_branch (edge e
, basic_block target
)
1425 basic_block src
= e
->src
;
1426 basic_block dest
= e
->dest
;
1428 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
1434 if ((ret
= try_redirect_by_replacing_jump (e
, target
, false)) != NULL
)
1436 df_set_bb_dirty (src
);
1437 fixup_partition_crossing (ret
);
1441 ret
= redirect_branch_edge (e
, target
);
1445 df_set_bb_dirty (src
);
1446 fixup_partition_crossing (ret
);
1450 /* Emit a barrier after BB, into the footer if we are in CFGLAYOUT mode. */
1453 emit_barrier_after_bb (basic_block bb
)
1455 rtx_barrier
*barrier
= emit_barrier_after (BB_END (bb
));
1456 gcc_assert (current_ir_type () == IR_RTL_CFGRTL
1457 || current_ir_type () == IR_RTL_CFGLAYOUT
);
1458 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
1460 rtx_insn
*insn
= unlink_insn_chain (barrier
, barrier
);
1464 rtx_insn
*footer_tail
= BB_FOOTER (bb
);
1466 while (NEXT_INSN (footer_tail
))
1467 footer_tail
= NEXT_INSN (footer_tail
);
1468 if (!BARRIER_P (footer_tail
))
1470 SET_NEXT_INSN (footer_tail
) = insn
;
1471 SET_PREV_INSN (insn
) = footer_tail
;
1475 BB_FOOTER (bb
) = insn
;
1479 /* Like force_nonfallthru below, but additionally performs redirection
1480 Used by redirect_edge_and_branch_force. JUMP_LABEL is used only
1481 when redirecting to the EXIT_BLOCK, it is either ret_rtx or
1482 simple_return_rtx, indicating which kind of returnjump to create.
1483 It should be NULL otherwise. */
1486 force_nonfallthru_and_redirect (edge e
, basic_block target
, rtx jump_label
)
1488 basic_block jump_block
, new_bb
= NULL
, src
= e
->src
;
1491 int abnormal_edge_flags
= 0;
1492 bool asm_goto_edge
= false;
1495 /* In the case the last instruction is conditional jump to the next
1496 instruction, first redirect the jump itself and then continue
1497 by creating a basic block afterwards to redirect fallthru edge. */
1498 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1499 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1500 && any_condjump_p (BB_END (e
->src
))
1501 && JUMP_LABEL (BB_END (e
->src
)) == BB_HEAD (e
->dest
))
1504 edge b
= unchecked_make_edge (e
->src
, target
, 0);
1507 redirected
= redirect_jump (as_a
<rtx_jump_insn
*> (BB_END (e
->src
)),
1508 block_label (target
), 0);
1509 gcc_assert (redirected
);
1511 note
= find_reg_note (BB_END (e
->src
), REG_BR_PROB
, NULL_RTX
);
1514 int prob
= XINT (note
, 0);
1516 b
->probability
= profile_probability::from_reg_br_prob_note (prob
);
1517 e
->probability
-= e
->probability
;
1521 if (e
->flags
& EDGE_ABNORMAL
)
1523 /* Irritating special case - fallthru edge to the same block as abnormal
1525 We can't redirect abnormal edge, but we still can split the fallthru
1526 one and create separate abnormal edge to original destination.
1527 This allows bb-reorder to make such edge non-fallthru. */
1528 gcc_assert (e
->dest
== target
);
1529 abnormal_edge_flags
= e
->flags
& ~EDGE_FALLTHRU
;
1530 e
->flags
&= EDGE_FALLTHRU
;
1534 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
1535 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1537 /* We can't redirect the entry block. Create an empty block
1538 at the start of the function which we use to add the new
1544 basic_block bb
= create_basic_block (BB_HEAD (e
->dest
), NULL
,
1545 ENTRY_BLOCK_PTR_FOR_FN (cfun
));
1546 bb
->count
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
;
1548 /* Make sure new block ends up in correct hot/cold section. */
1549 BB_COPY_PARTITION (bb
, e
->dest
);
1551 /* Change the existing edge's source to be the new block, and add
1552 a new edge from the entry block to the new block. */
1554 for (ei
= ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
);
1555 (tmp
= ei_safe_edge (ei
)); )
1559 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
->unordered_remove (ei
.index
);
1569 vec_safe_push (bb
->succs
, e
);
1570 make_single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
), bb
,
1575 /* If e->src ends with asm goto, see if any of the ASM_OPERANDS_LABELs
1576 don't point to the target or fallthru label. */
1577 if (JUMP_P (BB_END (e
->src
))
1578 && target
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1579 && (e
->flags
& EDGE_FALLTHRU
)
1580 && (note
= extract_asm_operands (PATTERN (BB_END (e
->src
)))))
1582 int i
, n
= ASM_OPERANDS_LABEL_LENGTH (note
);
1583 bool adjust_jump_target
= false;
1585 for (i
= 0; i
< n
; ++i
)
1587 if (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) == BB_HEAD (e
->dest
))
1589 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0))--;
1590 XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) = block_label (target
);
1591 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0))++;
1592 adjust_jump_target
= true;
1594 if (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) == BB_HEAD (target
))
1595 asm_goto_edge
= true;
1597 if (adjust_jump_target
)
1599 rtx_insn
*insn
= BB_END (e
->src
);
1601 rtx_insn
*old_label
= BB_HEAD (e
->dest
);
1602 rtx_insn
*new_label
= BB_HEAD (target
);
1604 if (JUMP_LABEL (insn
) == old_label
)
1606 JUMP_LABEL (insn
) = new_label
;
1607 note
= find_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1609 remove_note (insn
, note
);
1613 note
= find_reg_note (insn
, REG_LABEL_TARGET
, old_label
);
1615 remove_note (insn
, note
);
1616 if (JUMP_LABEL (insn
) != new_label
1617 && !find_reg_note (insn
, REG_LABEL_TARGET
, new_label
))
1618 add_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1620 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, old_label
))
1622 XEXP (note
, 0) = new_label
;
1626 if (EDGE_COUNT (e
->src
->succs
) >= 2 || abnormal_edge_flags
|| asm_goto_edge
)
1629 profile_count count
= e
->count ();
1630 profile_probability probability
= e
->probability
;
1631 /* Create the new structures. */
1633 /* If the old block ended with a tablejump, skip its table
1634 by searching forward from there. Otherwise start searching
1635 forward from the last instruction of the old block. */
1636 rtx_jump_table_data
*table
;
1637 if (tablejump_p (BB_END (e
->src
), NULL
, &table
))
1640 new_head
= BB_END (e
->src
);
1641 new_head
= NEXT_INSN (new_head
);
1643 jump_block
= create_basic_block (new_head
, NULL
, e
->src
);
1644 jump_block
->count
= count
;
1646 /* Make sure new block ends up in correct hot/cold section. */
1648 BB_COPY_PARTITION (jump_block
, e
->src
);
1651 new_edge
= make_edge (e
->src
, jump_block
, EDGE_FALLTHRU
);
1652 new_edge
->probability
= probability
;
1654 /* Redirect old edge. */
1655 redirect_edge_pred (e
, jump_block
);
1656 e
->probability
= profile_probability::always ();
1658 /* If e->src was previously region crossing, it no longer is
1659 and the reg crossing note should be removed. */
1660 fixup_partition_crossing (new_edge
);
1662 /* If asm goto has any label refs to target's label,
1663 add also edge from asm goto bb to target. */
1666 new_edge
->probability
= new_edge
->probability
.apply_scale (1, 2);
1667 jump_block
->count
= jump_block
->count
.apply_scale (1, 2);
1668 edge new_edge2
= make_edge (new_edge
->src
, target
,
1669 e
->flags
& ~EDGE_FALLTHRU
);
1670 new_edge2
->probability
= probability
- new_edge
->probability
;
1673 new_bb
= jump_block
;
1676 jump_block
= e
->src
;
1678 loc
= e
->goto_locus
;
1679 e
->flags
&= ~EDGE_FALLTHRU
;
1680 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1682 if (jump_label
== ret_rtx
)
1683 emit_jump_insn_after_setloc (targetm
.gen_return (),
1684 BB_END (jump_block
), loc
);
1687 gcc_assert (jump_label
== simple_return_rtx
);
1688 emit_jump_insn_after_setloc (targetm
.gen_simple_return (),
1689 BB_END (jump_block
), loc
);
1691 set_return_jump_label (BB_END (jump_block
));
1695 rtx_code_label
*label
= block_label (target
);
1696 emit_jump_insn_after_setloc (targetm
.gen_jump (label
),
1697 BB_END (jump_block
), loc
);
1698 JUMP_LABEL (BB_END (jump_block
)) = label
;
1699 LABEL_NUSES (label
)++;
1702 /* We might be in cfg layout mode, and if so, the following routine will
1703 insert the barrier correctly. */
1704 emit_barrier_after_bb (jump_block
);
1705 redirect_edge_succ_nodup (e
, target
);
1707 if (abnormal_edge_flags
)
1708 make_edge (src
, target
, abnormal_edge_flags
);
1710 df_mark_solutions_dirty ();
1711 fixup_partition_crossing (e
);
1715 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1716 (and possibly create new basic block) to make edge non-fallthru.
1717 Return newly created BB or NULL if none. */
1720 rtl_force_nonfallthru (edge e
)
1722 return force_nonfallthru_and_redirect (e
, e
->dest
, NULL_RTX
);
1725 /* Redirect edge even at the expense of creating new jump insn or
1726 basic block. Return new basic block if created, NULL otherwise.
1727 Conversion must be possible. */
1730 rtl_redirect_edge_and_branch_force (edge e
, basic_block target
)
1732 if (redirect_edge_and_branch (e
, target
)
1733 || e
->dest
== target
)
1736 /* In case the edge redirection failed, try to force it to be non-fallthru
1737 and redirect newly created simplejump. */
1738 df_set_bb_dirty (e
->src
);
1739 return force_nonfallthru_and_redirect (e
, target
, NULL_RTX
);
1742 /* The given edge should potentially be a fallthru edge. If that is in
1743 fact true, delete the jump and barriers that are in the way. */
1746 rtl_tidy_fallthru_edge (edge e
)
1749 basic_block b
= e
->src
, c
= b
->next_bb
;
1751 /* ??? In a late-running flow pass, other folks may have deleted basic
1752 blocks by nopping out blocks, leaving multiple BARRIERs between here
1753 and the target label. They ought to be chastised and fixed.
1755 We can also wind up with a sequence of undeletable labels between
1756 one block and the next.
1758 So search through a sequence of barriers, labels, and notes for
1759 the head of block C and assert that we really do fall through. */
1761 for (q
= NEXT_INSN (BB_END (b
)); q
!= BB_HEAD (c
); q
= NEXT_INSN (q
))
1762 if (NONDEBUG_INSN_P (q
))
1765 /* Remove what will soon cease being the jump insn from the source block.
1766 If block B consisted only of this single jump, turn it into a deleted
1771 && (any_uncondjump_p (q
)
1772 || single_succ_p (b
)))
1775 rtx_jump_table_data
*table
;
1777 if (tablejump_p (q
, &label
, &table
))
1779 /* The label is likely mentioned in some instruction before
1780 the tablejump and might not be DCEd, so turn it into
1781 a note instead and move before the tablejump that is going to
1783 const char *name
= LABEL_NAME (label
);
1784 PUT_CODE (label
, NOTE
);
1785 NOTE_KIND (label
) = NOTE_INSN_DELETED_LABEL
;
1786 NOTE_DELETED_LABEL_NAME (label
) = name
;
1787 reorder_insns (label
, label
, PREV_INSN (q
));
1788 delete_insn (table
);
1793 /* Unconditional jumps with side-effects (i.e. which we can't just delete
1794 together with the barrier) should never have a fallthru edge. */
1795 else if (JUMP_P (q
) && any_uncondjump_p (q
))
1798 /* Selectively unlink the sequence. */
1799 if (q
!= PREV_INSN (BB_HEAD (c
)))
1800 delete_insn_chain (NEXT_INSN (q
), PREV_INSN (BB_HEAD (c
)), false);
1802 e
->flags
|= EDGE_FALLTHRU
;
1805 /* Should move basic block BB after basic block AFTER. NIY. */
1808 rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED
,
1809 basic_block after ATTRIBUTE_UNUSED
)
1814 /* Locate the last bb in the same partition as START_BB. */
1817 last_bb_in_partition (basic_block start_bb
)
1820 FOR_BB_BETWEEN (bb
, start_bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
1822 if (BB_PARTITION (start_bb
) != BB_PARTITION (bb
->next_bb
))
1825 /* Return bb before the exit block. */
1829 /* Split a (typically critical) edge. Return the new block.
1830 The edge must not be abnormal.
1832 ??? The code generally expects to be called on critical edges.
1833 The case of a block ending in an unconditional jump to a
1834 block with multiple predecessors is not handled optimally. */
1837 rtl_split_edge (edge edge_in
)
1839 basic_block bb
, new_bb
;
1842 /* Abnormal edges cannot be split. */
1843 gcc_assert (!(edge_in
->flags
& EDGE_ABNORMAL
));
1845 /* We are going to place the new block in front of edge destination.
1846 Avoid existence of fallthru predecessors. */
1847 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1849 edge e
= find_fallthru_edge (edge_in
->dest
->preds
);
1852 force_nonfallthru (e
);
1855 /* Create the basic block note. */
1856 if (edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1857 before
= BB_HEAD (edge_in
->dest
);
1861 /* If this is a fall through edge to the exit block, the blocks might be
1862 not adjacent, and the right place is after the source. */
1863 if ((edge_in
->flags
& EDGE_FALLTHRU
)
1864 && edge_in
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1866 before
= NEXT_INSN (BB_END (edge_in
->src
));
1867 bb
= create_basic_block (before
, NULL
, edge_in
->src
);
1868 BB_COPY_PARTITION (bb
, edge_in
->src
);
1872 if (edge_in
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1874 bb
= create_basic_block (before
, NULL
, edge_in
->dest
->prev_bb
);
1875 BB_COPY_PARTITION (bb
, edge_in
->dest
);
1879 basic_block after
= edge_in
->dest
->prev_bb
;
1880 /* If this is post-bb reordering, and the edge crosses a partition
1881 boundary, the new block needs to be inserted in the bb chain
1882 at the end of the src partition (since we put the new bb into
1883 that partition, see below). Otherwise we may end up creating
1884 an extra partition crossing in the chain, which is illegal.
1885 It can't go after the src, because src may have a fall-through
1886 to a different block. */
1887 if (crtl
->bb_reorder_complete
1888 && (edge_in
->flags
& EDGE_CROSSING
))
1890 after
= last_bb_in_partition (edge_in
->src
);
1891 before
= get_last_bb_insn (after
);
1892 /* The instruction following the last bb in partition should
1893 be a barrier, since it cannot end in a fall-through. */
1894 gcc_checking_assert (BARRIER_P (before
));
1895 before
= NEXT_INSN (before
);
1897 bb
= create_basic_block (before
, NULL
, after
);
1898 /* Put the split bb into the src partition, to avoid creating
1899 a situation where a cold bb dominates a hot bb, in the case
1900 where src is cold and dest is hot. The src will dominate
1901 the new bb (whereas it might not have dominated dest). */
1902 BB_COPY_PARTITION (bb
, edge_in
->src
);
1906 make_single_succ_edge (bb
, edge_in
->dest
, EDGE_FALLTHRU
);
1908 /* Can't allow a region crossing edge to be fallthrough. */
1909 if (BB_PARTITION (bb
) != BB_PARTITION (edge_in
->dest
)
1910 && edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1912 new_bb
= force_nonfallthru (single_succ_edge (bb
));
1913 gcc_assert (!new_bb
);
1916 /* For non-fallthru edges, we must adjust the predecessor's
1917 jump instruction to target our new block. */
1918 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1920 edge redirected
= redirect_edge_and_branch (edge_in
, bb
);
1921 gcc_assert (redirected
);
1925 if (edge_in
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1927 /* For asm goto even splitting of fallthru edge might
1928 need insn patching, as other labels might point to the
1930 rtx_insn
*last
= BB_END (edge_in
->src
);
1933 && edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1934 && (extract_asm_operands (PATTERN (last
))
1935 || JUMP_LABEL (last
) == before
)
1936 && patch_jump_insn (last
, before
, bb
))
1937 df_set_bb_dirty (edge_in
->src
);
1939 redirect_edge_succ (edge_in
, bb
);
1945 /* Queue instructions for insertion on an edge between two basic blocks.
1946 The new instructions and basic blocks (if any) will not appear in the
1947 CFG until commit_edge_insertions is called. */
1950 insert_insn_on_edge (rtx pattern
, edge e
)
1952 /* We cannot insert instructions on an abnormal critical edge.
1953 It will be easier to find the culprit if we die now. */
1954 gcc_assert (!((e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
)));
1956 if (e
->insns
.r
== NULL_RTX
)
1959 push_to_sequence (e
->insns
.r
);
1961 emit_insn (pattern
);
1963 e
->insns
.r
= get_insns ();
1967 /* Update the CFG for the instructions queued on edge E. */
1970 commit_one_edge_insertion (edge e
)
1972 rtx_insn
*before
= NULL
, *after
= NULL
, *insns
, *tmp
, *last
;
1975 /* Pull the insns off the edge now since the edge might go away. */
1979 /* Figure out where to put these insns. If the destination has
1980 one predecessor, insert there. Except for the exit block. */
1981 if (single_pred_p (e
->dest
) && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1985 /* Get the location correct wrt a code label, and "nice" wrt
1986 a basic block note, and before everything else. */
1989 tmp
= NEXT_INSN (tmp
);
1990 if (NOTE_INSN_BASIC_BLOCK_P (tmp
))
1991 tmp
= NEXT_INSN (tmp
);
1992 if (tmp
== BB_HEAD (bb
))
1995 after
= PREV_INSN (tmp
);
1997 after
= get_last_insn ();
2000 /* If the source has one successor and the edge is not abnormal,
2001 insert there. Except for the entry block.
2002 Don't do this if the predecessor ends in a jump other than
2003 unconditional simple jump. E.g. for asm goto that points all
2004 its labels at the fallthru basic block, we can't insert instructions
2005 before the asm goto, as the asm goto can have various of side effects,
2006 and can't emit instructions after the asm goto, as it must end
2008 else if ((e
->flags
& EDGE_ABNORMAL
) == 0
2009 && single_succ_p (e
->src
)
2010 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2011 && (!JUMP_P (BB_END (e
->src
))
2012 || simplejump_p (BB_END (e
->src
))))
2016 /* It is possible to have a non-simple jump here. Consider a target
2017 where some forms of unconditional jumps clobber a register. This
2018 happens on the fr30 for example.
2020 We know this block has a single successor, so we can just emit
2021 the queued insns before the jump. */
2022 if (JUMP_P (BB_END (bb
)))
2023 before
= BB_END (bb
);
2026 /* We'd better be fallthru, or we've lost track of what's what. */
2027 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
2029 after
= BB_END (bb
);
2033 /* Otherwise we must split the edge. */
2036 bb
= split_edge (e
);
2038 /* If E crossed a partition boundary, we needed to make bb end in
2039 a region-crossing jump, even though it was originally fallthru. */
2040 if (JUMP_P (BB_END (bb
)))
2041 before
= BB_END (bb
);
2043 after
= BB_END (bb
);
2046 /* Now that we've found the spot, do the insertion. */
2049 emit_insn_before_noloc (insns
, before
, bb
);
2050 last
= prev_nonnote_insn (before
);
2053 last
= emit_insn_after_noloc (insns
, after
, bb
);
2055 if (returnjump_p (last
))
2057 /* ??? Remove all outgoing edges from BB and add one for EXIT.
2058 This is not currently a problem because this only happens
2059 for the (single) epilogue, which already has a fallthru edge
2062 e
= single_succ_edge (bb
);
2063 gcc_assert (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
2064 && single_succ_p (bb
) && (e
->flags
& EDGE_FALLTHRU
));
2066 e
->flags
&= ~EDGE_FALLTHRU
;
2067 emit_barrier_after (last
);
2070 delete_insn (before
);
2073 gcc_assert (!JUMP_P (last
));
2076 /* Update the CFG for all queued instructions. */
2079 commit_edge_insertions (void)
2083 /* Optimization passes that invoke this routine can cause hot blocks
2084 previously reached by both hot and cold blocks to become dominated only
2085 by cold blocks. This will cause the verification below to fail,
2086 and lead to now cold code in the hot section. In some cases this
2087 may only be visible after newly unreachable blocks are deleted,
2088 which will be done by fixup_partitions. */
2089 fixup_partitions ();
2091 if (!currently_expanding_to_rtl
)
2092 checking_verify_flow_info ();
2094 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
2095 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
2100 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2103 if (currently_expanding_to_rtl
)
2104 rebuild_jump_labels_chain (e
->insns
.r
);
2105 commit_one_edge_insertion (e
);
2111 /* Print out RTL-specific basic block information (live information
2112 at start and end with TDF_DETAILS). FLAGS are the TDF_* masks
2113 documented in dumpfile.h. */
2116 rtl_dump_bb (FILE *outf
, basic_block bb
, int indent
, dump_flags_t flags
)
2120 s_indent
= (char *) alloca ((size_t) indent
+ 1);
2121 memset (s_indent
, ' ', (size_t) indent
);
2122 s_indent
[indent
] = '\0';
2124 if (df
&& (flags
& TDF_DETAILS
))
2126 df_dump_top (bb
, outf
);
2130 if (bb
->index
!= ENTRY_BLOCK
&& bb
->index
!= EXIT_BLOCK
2131 && rtl_bb_info_initialized_p (bb
))
2133 rtx_insn
*last
= BB_END (bb
);
2135 last
= NEXT_INSN (last
);
2136 for (rtx_insn
*insn
= BB_HEAD (bb
); insn
!= last
; insn
= NEXT_INSN (insn
))
2138 if (flags
& TDF_DETAILS
)
2139 df_dump_insn_top (insn
, outf
);
2140 if (! (flags
& TDF_SLIM
))
2141 print_rtl_single (outf
, insn
);
2143 dump_insn_slim (outf
, insn
);
2144 if (flags
& TDF_DETAILS
)
2145 df_dump_insn_bottom (insn
, outf
);
2149 if (df
&& (flags
& TDF_DETAILS
))
2151 df_dump_bottom (bb
, outf
);
2157 /* Like dump_function_to_file, but for RTL. Print out dataflow information
2158 for the start of each basic block. FLAGS are the TDF_* masks documented
2162 print_rtl_with_bb (FILE *outf
, const rtx_insn
*rtx_first
, dump_flags_t flags
)
2164 const rtx_insn
*tmp_rtx
;
2166 fprintf (outf
, "(nil)\n");
2169 enum bb_state
{ NOT_IN_BB
, IN_ONE_BB
, IN_MULTIPLE_BB
};
2170 int max_uid
= get_max_uid ();
2171 basic_block
*start
= XCNEWVEC (basic_block
, max_uid
);
2172 basic_block
*end
= XCNEWVEC (basic_block
, max_uid
);
2173 enum bb_state
*in_bb_p
= XCNEWVEC (enum bb_state
, max_uid
);
2176 /* After freeing the CFG, we still have BLOCK_FOR_INSN set on most
2177 insns, but the CFG is not maintained so the basic block info
2178 is not reliable. Therefore it's omitted from the dumps. */
2179 if (! (cfun
->curr_properties
& PROP_cfg
))
2180 flags
&= ~TDF_BLOCKS
;
2183 df_dump_start (outf
);
2185 if (cfun
->curr_properties
& PROP_cfg
)
2187 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2191 start
[INSN_UID (BB_HEAD (bb
))] = bb
;
2192 end
[INSN_UID (BB_END (bb
))] = bb
;
2193 if (flags
& TDF_BLOCKS
)
2195 for (x
= BB_HEAD (bb
); x
!= NULL_RTX
; x
= NEXT_INSN (x
))
2197 enum bb_state state
= IN_MULTIPLE_BB
;
2199 if (in_bb_p
[INSN_UID (x
)] == NOT_IN_BB
)
2201 in_bb_p
[INSN_UID (x
)] = state
;
2203 if (x
== BB_END (bb
))
2210 for (tmp_rtx
= rtx_first
; tmp_rtx
!= NULL
; tmp_rtx
= NEXT_INSN (tmp_rtx
))
2212 if (flags
& TDF_BLOCKS
)
2214 bb
= start
[INSN_UID (tmp_rtx
)];
2217 dump_bb_info (outf
, bb
, 0, dump_flags
, true, false);
2218 if (df
&& (flags
& TDF_DETAILS
))
2219 df_dump_top (bb
, outf
);
2222 if (in_bb_p
[INSN_UID (tmp_rtx
)] == NOT_IN_BB
2223 && !NOTE_P (tmp_rtx
)
2224 && !BARRIER_P (tmp_rtx
))
2225 fprintf (outf
, ";; Insn is not within a basic block\n");
2226 else if (in_bb_p
[INSN_UID (tmp_rtx
)] == IN_MULTIPLE_BB
)
2227 fprintf (outf
, ";; Insn is in multiple basic blocks\n");
2230 if (flags
& TDF_DETAILS
)
2231 df_dump_insn_top (tmp_rtx
, outf
);
2232 if (! (flags
& TDF_SLIM
))
2233 print_rtl_single (outf
, tmp_rtx
);
2235 dump_insn_slim (outf
, tmp_rtx
);
2236 if (flags
& TDF_DETAILS
)
2237 df_dump_insn_bottom (tmp_rtx
, outf
);
2239 bb
= end
[INSN_UID (tmp_rtx
)];
2242 if (flags
& TDF_BLOCKS
)
2244 dump_bb_info (outf
, bb
, 0, dump_flags
, false, true);
2245 if (df
&& (flags
& TDF_DETAILS
))
2246 df_dump_bottom (bb
, outf
);
2249 /* Emit a hint if the fallthrough target of current basic block
2250 isn't the one placed right next. */
2251 else if (EDGE_COUNT (bb
->succs
) > 0)
2253 gcc_assert (BB_END (bb
) == tmp_rtx
);
2254 const rtx_insn
*ninsn
= NEXT_INSN (tmp_rtx
);
2255 /* Bypass intervening deleted-insn notes and debug insns. */
2257 && !NONDEBUG_INSN_P (ninsn
)
2258 && !start
[INSN_UID (ninsn
)])
2259 ninsn
= NEXT_INSN (ninsn
);
2260 edge e
= find_fallthru_edge (bb
->succs
);
2263 basic_block dest
= e
->dest
;
2264 if (start
[INSN_UID (ninsn
)] != dest
)
2265 fprintf (outf
, "%s ; pc falls through to BB %d\n",
2266 print_rtx_head
, dest
->index
);
2278 /* Update the branch probability of BB if a REG_BR_PROB is present. */
2281 update_br_prob_note (basic_block bb
)
2284 note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
);
2285 if (!JUMP_P (BB_END (bb
)) || !BRANCH_EDGE (bb
)->probability
.initialized_p ())
2289 rtx
*note_link
, this_rtx
;
2291 note_link
= ®_NOTES (BB_END (bb
));
2292 for (this_rtx
= *note_link
; this_rtx
; this_rtx
= XEXP (this_rtx
, 1))
2293 if (this_rtx
== note
)
2295 *note_link
= XEXP (this_rtx
, 1);
2302 || XINT (note
, 0) == BRANCH_EDGE (bb
)->probability
.to_reg_br_prob_note ())
2304 XINT (note
, 0) = BRANCH_EDGE (bb
)->probability
.to_reg_br_prob_note ();
2307 /* Get the last insn associated with block BB (that includes barriers and
2308 tablejumps after BB). */
2310 get_last_bb_insn (basic_block bb
)
2312 rtx_jump_table_data
*table
;
2314 rtx_insn
*end
= BB_END (bb
);
2316 /* Include any jump table following the basic block. */
2317 if (tablejump_p (end
, NULL
, &table
))
2320 /* Include any barriers that may follow the basic block. */
2321 tmp
= next_nonnote_nondebug_insn_bb (end
);
2322 while (tmp
&& BARRIER_P (tmp
))
2325 tmp
= next_nonnote_nondebug_insn_bb (end
);
2331 /* Add all BBs reachable from entry via hot paths into the SET. */
2334 find_bbs_reachable_by_hot_paths (hash_set
<basic_block
> *set
)
2336 auto_vec
<basic_block
, 64> worklist
;
2338 set
->add (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
2339 worklist
.safe_push (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
2341 while (worklist
.length () > 0)
2343 basic_block bb
= worklist
.pop ();
2347 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2348 if (BB_PARTITION (e
->dest
) != BB_COLD_PARTITION
2349 && !set
->add (e
->dest
))
2350 worklist
.safe_push (e
->dest
);
2354 /* Sanity check partition hotness to ensure that basic blocks in
2355 Â the cold partition don't dominate basic blocks in the hot partition.
2356 If FLAG_ONLY is true, report violations as errors. Otherwise
2357 re-mark the dominated blocks as cold, since this is run after
2358 cfg optimizations that may make hot blocks previously reached
2359 by both hot and cold blocks now only reachable along cold paths. */
2361 static auto_vec
<basic_block
>
2362 find_partition_fixes (bool flag_only
)
2365 auto_vec
<basic_block
> bbs_to_fix
;
2366 hash_set
<basic_block
> set
;
2368 /* Callers check this. */
2369 gcc_checking_assert (crtl
->has_bb_partition
);
2371 find_bbs_reachable_by_hot_paths (&set
);
2373 FOR_EACH_BB_FN (bb
, cfun
)
2374 if (!set
.contains (bb
)
2375 && BB_PARTITION (bb
) != BB_COLD_PARTITION
)
2378 error ("non-cold basic block %d reachable only "
2379 "by paths crossing the cold partition", bb
->index
);
2381 BB_SET_PARTITION (bb
, BB_COLD_PARTITION
);
2382 bbs_to_fix
.safe_push (bb
);
2388 /* Perform cleanup on the hot/cold bb partitioning after optimization
2389 passes that modify the cfg. */
2392 fixup_partitions (void)
2394 if (!crtl
->has_bb_partition
)
2397 /* Delete any blocks that became unreachable and weren't
2398 already cleaned up, for example during edge forwarding
2399 and convert_jumps_to_returns. This will expose more
2400 opportunities for fixing the partition boundaries here.
2401 Also, the calculation of the dominance graph during verification
2402 will assert if there are unreachable nodes. */
2403 delete_unreachable_blocks ();
2405 /* If there are partitions, do a sanity check on them: A basic block in
2406 Â a cold partition cannot dominate a basic block in a hot partition.
2407 Fixup any that now violate this requirement, as a result of edge
2408 forwarding and unreachable block deletion. Â */
2409 auto_vec
<basic_block
> bbs_to_fix
= find_partition_fixes (false);
2411 /* Do the partition fixup after all necessary blocks have been converted to
2412 cold, so that we only update the region crossings the minimum number of
2413 places, which can require forcing edges to be non fallthru. */
2414 if (! bbs_to_fix
.is_empty ())
2418 basic_block bb
= bbs_to_fix
.pop ();
2419 fixup_new_cold_bb (bb
);
2421 while (! bbs_to_fix
.is_empty ());
2423 /* Fix up hot cold block grouping if needed. */
2424 if (crtl
->bb_reorder_complete
&& current_ir_type () == IR_RTL_CFGRTL
)
2426 basic_block bb
, first
= NULL
, second
= NULL
;
2427 int current_partition
= BB_UNPARTITIONED
;
2429 FOR_EACH_BB_FN (bb
, cfun
)
2431 if (current_partition
!= BB_UNPARTITIONED
2432 && BB_PARTITION (bb
) != current_partition
)
2436 else if (second
== NULL
)
2440 /* If we switch partitions for the 3rd, 5th etc. time,
2441 move bbs first (inclusive) .. second (exclusive) right
2443 basic_block prev_first
= first
->prev_bb
;
2444 basic_block prev_second
= second
->prev_bb
;
2445 basic_block prev_bb
= bb
->prev_bb
;
2446 prev_first
->next_bb
= second
;
2447 second
->prev_bb
= prev_first
;
2448 prev_second
->next_bb
= bb
;
2449 bb
->prev_bb
= prev_second
;
2450 prev_bb
->next_bb
= first
;
2451 first
->prev_bb
= prev_bb
;
2452 rtx_insn
*prev_first_insn
= PREV_INSN (BB_HEAD (first
));
2453 rtx_insn
*prev_second_insn
2454 = PREV_INSN (BB_HEAD (second
));
2455 rtx_insn
*prev_bb_insn
= PREV_INSN (BB_HEAD (bb
));
2456 SET_NEXT_INSN (prev_first_insn
) = BB_HEAD (second
);
2457 SET_PREV_INSN (BB_HEAD (second
)) = prev_first_insn
;
2458 SET_NEXT_INSN (prev_second_insn
) = BB_HEAD (bb
);
2459 SET_PREV_INSN (BB_HEAD (bb
)) = prev_second_insn
;
2460 SET_NEXT_INSN (prev_bb_insn
) = BB_HEAD (first
);
2461 SET_PREV_INSN (BB_HEAD (first
)) = prev_bb_insn
;
2465 current_partition
= BB_PARTITION (bb
);
2467 gcc_assert (!second
);
2472 /* Verify, in the basic block chain, that there is at most one switch
2473 between hot/cold partitions. This condition will not be true until
2474 after reorder_basic_blocks is called. */
2477 verify_hot_cold_block_grouping (void)
2481 bool switched_sections
= false;
2482 int current_partition
= BB_UNPARTITIONED
;
2484 /* Even after bb reordering is complete, we go into cfglayout mode
2485 again (in compgoto). Ensure we don't call this before going back
2486 into linearized RTL when any layout fixes would have been committed. */
2487 if (!crtl
->bb_reorder_complete
2488 || current_ir_type () != IR_RTL_CFGRTL
)
2491 FOR_EACH_BB_FN (bb
, cfun
)
2493 if (current_partition
!= BB_UNPARTITIONED
2494 && BB_PARTITION (bb
) != current_partition
)
2496 if (switched_sections
)
2498 error ("multiple hot/cold transitions found (bb %i)",
2503 switched_sections
= true;
2505 if (!crtl
->has_bb_partition
)
2506 error ("partition found but function partition flag not set");
2508 current_partition
= BB_PARTITION (bb
);
2515 /* Perform several checks on the edges out of each block, such as
2516 the consistency of the branch probabilities, the correctness
2517 of hot/cold partition crossing edges, and the number of expected
2518 successor edges. Also verify that the dominance relationship
2519 between hot/cold blocks is sane. */
2522 rtl_verify_edges (void)
2527 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2529 int n_fallthru
= 0, n_branch
= 0, n_abnormal_call
= 0, n_sibcall
= 0;
2530 int n_eh
= 0, n_abnormal
= 0;
2531 edge e
, fallthru
= NULL
;
2534 bool has_crossing_edge
= false;
2536 if (JUMP_P (BB_END (bb
))
2537 && (note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
))
2538 && EDGE_COUNT (bb
->succs
) >= 2
2539 && any_condjump_p (BB_END (bb
)))
2541 if (!BRANCH_EDGE (bb
)->probability
.initialized_p ())
2543 if (profile_status_for_fn (cfun
) != PROFILE_ABSENT
)
2545 error ("verify_flow_info: "
2546 "REG_BR_PROB is set but cfg probability is not");
2550 else if (XINT (note
, 0)
2551 != BRANCH_EDGE (bb
)->probability
.to_reg_br_prob_note ()
2552 && profile_status_for_fn (cfun
) != PROFILE_ABSENT
)
2554 error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i",
2556 BRANCH_EDGE (bb
)->probability
.to_reg_br_prob_note ());
2561 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2565 if (e
->flags
& EDGE_FALLTHRU
)
2566 n_fallthru
++, fallthru
= e
;
2568 is_crossing
= (BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
)
2569 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2570 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
2571 has_crossing_edge
|= is_crossing
;
2572 if (e
->flags
& EDGE_CROSSING
)
2576 error ("EDGE_CROSSING incorrectly set across same section");
2579 if (e
->flags
& EDGE_FALLTHRU
)
2581 error ("fallthru edge crosses section boundary in bb %i",
2585 if (e
->flags
& EDGE_EH
)
2587 error ("EH edge crosses section boundary in bb %i",
2591 if (JUMP_P (BB_END (bb
)) && !CROSSING_JUMP_P (BB_END (bb
)))
2593 error ("No region crossing jump at section boundary in bb %i",
2598 else if (is_crossing
)
2600 error ("EDGE_CROSSING missing across section boundary");
2604 if ((e
->flags
& ~(EDGE_DFS_BACK
2606 | EDGE_IRREDUCIBLE_LOOP
2609 | EDGE_PRESERVE
)) == 0)
2612 if (e
->flags
& EDGE_ABNORMAL_CALL
)
2615 if (e
->flags
& EDGE_SIBCALL
)
2618 if (e
->flags
& EDGE_EH
)
2621 if (e
->flags
& EDGE_ABNORMAL
)
2625 if (!has_crossing_edge
2626 && JUMP_P (BB_END (bb
))
2627 && CROSSING_JUMP_P (BB_END (bb
)))
2629 print_rtl_with_bb (stderr
, get_insns (), TDF_BLOCKS
| TDF_DETAILS
);
2630 error ("Region crossing jump across same section in bb %i",
2635 if (n_eh
&& !find_reg_note (BB_END (bb
), REG_EH_REGION
, NULL_RTX
))
2637 error ("missing REG_EH_REGION note at the end of bb %i", bb
->index
);
2642 error ("too many exception handling edges in bb %i", bb
->index
);
2646 && (!JUMP_P (BB_END (bb
))
2647 || (n_branch
> 1 && (any_uncondjump_p (BB_END (bb
))
2648 || any_condjump_p (BB_END (bb
))))))
2650 error ("too many outgoing branch edges from bb %i", bb
->index
);
2653 if (n_fallthru
&& any_uncondjump_p (BB_END (bb
)))
2655 error ("fallthru edge after unconditional jump in bb %i", bb
->index
);
2658 if (n_branch
!= 1 && any_uncondjump_p (BB_END (bb
)))
2660 error ("wrong number of branch edges after unconditional jump"
2661 " in bb %i", bb
->index
);
2664 if (n_branch
!= 1 && any_condjump_p (BB_END (bb
))
2665 && JUMP_LABEL (BB_END (bb
)) != BB_HEAD (fallthru
->dest
))
2667 error ("wrong amount of branch edges after conditional jump"
2668 " in bb %i", bb
->index
);
2671 if (n_abnormal_call
&& !CALL_P (BB_END (bb
)))
2673 error ("abnormal call edges for non-call insn in bb %i", bb
->index
);
2676 if (n_sibcall
&& !CALL_P (BB_END (bb
)))
2678 error ("sibcall edges for non-call insn in bb %i", bb
->index
);
2681 if (n_abnormal
> n_eh
2682 && !(CALL_P (BB_END (bb
))
2683 && n_abnormal
== n_abnormal_call
+ n_sibcall
)
2684 && (!JUMP_P (BB_END (bb
))
2685 || any_condjump_p (BB_END (bb
))
2686 || any_uncondjump_p (BB_END (bb
))))
2688 error ("abnormal edges for no purpose in bb %i", bb
->index
);
2693 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2696 has_eh
= (e
->flags
& EDGE_EH
);
2697 if ((e
->flags
& EDGE_EH
) == has_eh
)
2699 error ("EH incoming edge mixed with non-EH incoming edges "
2700 "in bb %i", bb
->index
);
2706 /* If there are partitions, do a sanity check on them: A basic block in
2707 Â a cold partition cannot dominate a basic block in a hot partition. Â */
2708 if (crtl
->has_bb_partition
&& !err
2709 && current_ir_type () == IR_RTL_CFGLAYOUT
)
2711 auto_vec
<basic_block
> bbs_to_fix
= find_partition_fixes (true);
2712 err
= !bbs_to_fix
.is_empty ();
2719 /* Checks on the instructions within blocks. Currently checks that each
2720 block starts with a basic block note, and that basic block notes and
2721 control flow jumps are not found in the middle of the block. */
2724 rtl_verify_bb_insns (void)
2730 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2732 /* Now check the header of basic
2733 block. It ought to contain optional CODE_LABEL followed
2734 by NOTE_BASIC_BLOCK. */
2738 if (BB_END (bb
) == x
)
2740 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2748 if (!NOTE_INSN_BASIC_BLOCK_P (x
) || NOTE_BASIC_BLOCK (x
) != bb
)
2750 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2755 if (BB_END (bb
) == x
)
2756 /* Do checks for empty blocks here. */
2759 for (x
= NEXT_INSN (x
); x
; x
= NEXT_INSN (x
))
2761 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2763 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
2764 INSN_UID (x
), bb
->index
);
2768 if (x
== BB_END (bb
))
2771 if (control_flow_insn_p (x
))
2773 error ("in basic block %d:", bb
->index
);
2774 fatal_insn ("flow control insn inside a basic block", x
);
2783 /* Verify that block pointers for instructions in basic blocks, headers and
2784 footers are set appropriately. */
2787 rtl_verify_bb_pointers (void)
2792 /* Check the general integrity of the basic blocks. */
2793 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2797 if (!(bb
->flags
& BB_RTL
))
2799 error ("BB_RTL flag not set for block %d", bb
->index
);
2803 FOR_BB_INSNS (bb
, insn
)
2804 if (BLOCK_FOR_INSN (insn
) != bb
)
2806 error ("insn %d basic block pointer is %d, should be %d",
2808 BLOCK_FOR_INSN (insn
) ? BLOCK_FOR_INSN (insn
)->index
: 0,
2813 for (insn
= BB_HEADER (bb
); insn
; insn
= NEXT_INSN (insn
))
2814 if (!BARRIER_P (insn
)
2815 && BLOCK_FOR_INSN (insn
) != NULL
)
2817 error ("insn %d in header of bb %d has non-NULL basic block",
2818 INSN_UID (insn
), bb
->index
);
2821 for (insn
= BB_FOOTER (bb
); insn
; insn
= NEXT_INSN (insn
))
2822 if (!BARRIER_P (insn
)
2823 && BLOCK_FOR_INSN (insn
) != NULL
)
2825 error ("insn %d in footer of bb %d has non-NULL basic block",
2826 INSN_UID (insn
), bb
->index
);
2835 /* Verify the CFG and RTL consistency common for both underlying RTL and
2838 Currently it does following checks:
2840 - overlapping of basic blocks
2841 - insns with wrong BLOCK_FOR_INSN pointers
2842 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
2843 - tails of basic blocks (ensure that boundary is necessary)
2844 - scans body of the basic block for JUMP_INSN, CODE_LABEL
2845 and NOTE_INSN_BASIC_BLOCK
2846 - verify that no fall_thru edge crosses hot/cold partition boundaries
2847 - verify that there are no pending RTL branch predictions
2848 - verify that hot blocks are not dominated by cold blocks
2850 In future it can be extended check a lot of other stuff as well
2851 (reachability of basic blocks, life information, etc. etc.). */
2854 rtl_verify_flow_info_1 (void)
2858 err
|= rtl_verify_bb_pointers ();
2860 err
|= rtl_verify_bb_insns ();
2862 err
|= rtl_verify_edges ();
2867 /* Walk the instruction chain and verify that bb head/end pointers
2868 are correct, and that instructions are in exactly one bb and have
2869 correct block pointers. */
2872 rtl_verify_bb_insn_chain (void)
2877 rtx_insn
*last_head
= get_last_insn ();
2878 basic_block
*bb_info
;
2879 const int max_uid
= get_max_uid ();
2881 bb_info
= XCNEWVEC (basic_block
, max_uid
);
2883 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2885 rtx_insn
*head
= BB_HEAD (bb
);
2886 rtx_insn
*end
= BB_END (bb
);
2888 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2890 /* Verify the end of the basic block is in the INSN chain. */
2894 /* And that the code outside of basic blocks has NULL bb field. */
2896 && BLOCK_FOR_INSN (x
) != NULL
)
2898 error ("insn %d outside of basic blocks has non-NULL bb field",
2906 error ("end insn %d for block %d not found in the insn stream",
2907 INSN_UID (end
), bb
->index
);
2911 /* Work backwards from the end to the head of the basic block
2912 to verify the head is in the RTL chain. */
2913 for (; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2915 /* While walking over the insn chain, verify insns appear
2916 in only one basic block. */
2917 if (bb_info
[INSN_UID (x
)] != NULL
)
2919 error ("insn %d is in multiple basic blocks (%d and %d)",
2920 INSN_UID (x
), bb
->index
, bb_info
[INSN_UID (x
)]->index
);
2924 bb_info
[INSN_UID (x
)] = bb
;
2931 error ("head insn %d for block %d not found in the insn stream",
2932 INSN_UID (head
), bb
->index
);
2936 last_head
= PREV_INSN (x
);
2939 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2941 /* Check that the code before the first basic block has NULL
2944 && BLOCK_FOR_INSN (x
) != NULL
)
2946 error ("insn %d outside of basic blocks has non-NULL bb field",
2956 /* Verify that fallthru edges point to adjacent blocks in layout order and
2957 that barriers exist after non-fallthru blocks. */
2960 rtl_verify_fallthru (void)
2965 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2969 e
= find_fallthru_edge (bb
->succs
);
2974 /* Ensure existence of barrier in BB with no fallthru edges. */
2975 for (insn
= NEXT_INSN (BB_END (bb
)); ; insn
= NEXT_INSN (insn
))
2977 if (!insn
|| NOTE_INSN_BASIC_BLOCK_P (insn
))
2979 error ("missing barrier after block %i", bb
->index
);
2983 if (BARRIER_P (insn
))
2987 else if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2988 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
2992 if (e
->src
->next_bb
!= e
->dest
)
2995 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
2996 e
->src
->index
, e
->dest
->index
);
3000 for (insn
= NEXT_INSN (BB_END (e
->src
)); insn
!= BB_HEAD (e
->dest
);
3001 insn
= NEXT_INSN (insn
))
3002 if (BARRIER_P (insn
) || NONDEBUG_INSN_P (insn
))
3004 error ("verify_flow_info: Incorrect fallthru %i->%i",
3005 e
->src
->index
, e
->dest
->index
);
3006 error ("wrong insn in the fallthru edge");
3016 /* Verify that blocks are laid out in consecutive order. While walking the
3017 instructions, verify that all expected instructions are inside the basic
3018 blocks, and that all returns are followed by barriers. */
3021 rtl_verify_bb_layout (void)
3027 rtx_insn
* const rtx_first
= get_insns ();
3028 basic_block last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
), curr_bb
= NULL
;
3032 for (x
= rtx_first
; x
; x
= NEXT_INSN (x
))
3034 if (NOTE_INSN_BASIC_BLOCK_P (x
))
3036 bb
= NOTE_BASIC_BLOCK (x
);
3039 if (bb
!= last_bb_seen
->next_bb
)
3040 internal_error ("basic blocks not laid down consecutively");
3042 curr_bb
= last_bb_seen
= bb
;
3047 switch (GET_CODE (x
))
3054 /* An ADDR_VEC is placed outside any basic block. */
3056 && JUMP_TABLE_DATA_P (NEXT_INSN (x
)))
3059 /* But in any case, non-deletable labels can appear anywhere. */
3063 fatal_insn ("insn outside basic block", x
);
3068 && returnjump_p (x
) && ! condjump_p (x
)
3069 && ! ((y
= next_nonnote_nondebug_insn (x
))
3071 fatal_insn ("return not followed by barrier", x
);
3073 if (curr_bb
&& x
== BB_END (curr_bb
))
3077 if (num_bb_notes
!= n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
)
3079 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
3080 num_bb_notes
, n_basic_blocks_for_fn (cfun
));
3085 /* Verify the CFG and RTL consistency common for both underlying RTL and
3086 cfglayout RTL, plus consistency checks specific to linearized RTL mode.
3088 Currently it does following checks:
3089 - all checks of rtl_verify_flow_info_1
3090 - test head/end pointers
3091 - check that blocks are laid out in consecutive order
3092 - check that all insns are in the basic blocks
3093 (except the switch handling code, barriers and notes)
3094 - check that all returns are followed by barriers
3095 - check that all fallthru edge points to the adjacent blocks
3096 - verify that there is a single hot/cold partition boundary after bbro */
3099 rtl_verify_flow_info (void)
3103 err
|= rtl_verify_flow_info_1 ();
3105 err
|= rtl_verify_bb_insn_chain ();
3107 err
|= rtl_verify_fallthru ();
3109 err
|= rtl_verify_bb_layout ();
3111 err
|= verify_hot_cold_block_grouping ();
3116 /* Assume that the preceding pass has possibly eliminated jump instructions
3117 or converted the unconditional jumps. Eliminate the edges from CFG.
3118 Return true if any edges are eliminated. */
3121 purge_dead_edges (basic_block bb
)
3124 rtx_insn
*insn
= BB_END (bb
);
3126 bool purged
= false;
3130 if ((DEBUG_INSN_P (insn
) || NOTE_P (insn
)) && insn
!= BB_HEAD (bb
))
3132 insn
= PREV_INSN (insn
);
3133 while ((DEBUG_INSN_P (insn
) || NOTE_P (insn
)) && insn
!= BB_HEAD (bb
));
3135 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
3136 if (NONJUMP_INSN_P (insn
)
3137 && (note
= find_reg_note (insn
, REG_EH_REGION
, NULL
)))
3141 if (! may_trap_p (PATTERN (insn
))
3142 || ((eqnote
= find_reg_equal_equiv_note (insn
))
3143 && ! may_trap_p (XEXP (eqnote
, 0))))
3144 remove_note (insn
, note
);
3147 /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
3148 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3150 bool remove
= false;
3152 /* There are three types of edges we need to handle correctly here: EH
3153 edges, abnormal call EH edges, and abnormal call non-EH edges. The
3154 latter can appear when nonlocal gotos are used. */
3155 if (e
->flags
& EDGE_ABNORMAL_CALL
)
3159 else if (can_nonlocal_goto (insn
))
3161 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
3163 else if (flag_tm
&& find_reg_note (insn
, REG_TM
, NULL
))
3168 else if (e
->flags
& EDGE_EH
)
3169 remove
= !can_throw_internal (insn
);
3174 df_set_bb_dirty (bb
);
3187 /* We do care only about conditional jumps and simplejumps. */
3188 if (!any_condjump_p (insn
)
3189 && !returnjump_p (insn
)
3190 && !simplejump_p (insn
))
3193 /* Branch probability/prediction notes are defined only for
3194 condjumps. We've possibly turned condjump into simplejump. */
3195 if (simplejump_p (insn
))
3197 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
3199 remove_note (insn
, note
);
3200 while ((note
= find_reg_note (insn
, REG_BR_PRED
, NULL
)))
3201 remove_note (insn
, note
);
3204 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3206 /* Avoid abnormal flags to leak from computed jumps turned
3207 into simplejumps. */
3209 e
->flags
&= ~EDGE_ABNORMAL
;
3211 /* See if this edge is one we should keep. */
3212 if ((e
->flags
& EDGE_FALLTHRU
) && any_condjump_p (insn
))
3213 /* A conditional jump can fall through into the next
3214 block, so we should keep the edge. */
3219 else if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
3220 && BB_HEAD (e
->dest
) == JUMP_LABEL (insn
))
3221 /* If the destination block is the target of the jump,
3227 else if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
3228 && returnjump_p (insn
))
3229 /* If the destination block is the exit block, and this
3230 instruction is a return, then keep the edge. */
3235 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
3236 /* Keep the edges that correspond to exceptions thrown by
3237 this instruction and rematerialize the EDGE_ABNORMAL
3238 flag we just cleared above. */
3240 e
->flags
|= EDGE_ABNORMAL
;
3245 /* We do not need this edge. */
3246 df_set_bb_dirty (bb
);
3251 if (EDGE_COUNT (bb
->succs
) == 0 || !purged
)
3255 fprintf (dump_file
, "Purged edges from bb %i\n", bb
->index
);
3260 /* Redistribute probabilities. */
3261 if (single_succ_p (bb
))
3263 single_succ_edge (bb
)->probability
= profile_probability::always ();
3267 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
3271 b
= BRANCH_EDGE (bb
);
3272 f
= FALLTHRU_EDGE (bb
);
3273 b
->probability
= profile_probability::from_reg_br_prob_note
3275 f
->probability
= b
->probability
.invert ();
3280 else if (CALL_P (insn
) && SIBLING_CALL_P (insn
))
3282 /* First, there should not be any EH or ABCALL edges resulting
3283 from non-local gotos and the like. If there were, we shouldn't
3284 have created the sibcall in the first place. Second, there
3285 should of course never have been a fallthru edge. */
3286 gcc_assert (single_succ_p (bb
));
3287 gcc_assert (single_succ_edge (bb
)->flags
3288 == (EDGE_SIBCALL
| EDGE_ABNORMAL
));
3293 /* If we don't see a jump insn, we don't know exactly why the block would
3294 have been broken at this point. Look for a simple, non-fallthru edge,
3295 as these are only created by conditional branches. If we find such an
3296 edge we know that there used to be a jump here and can then safely
3297 remove all non-fallthru edges. */
3299 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3300 if (! (e
->flags
& (EDGE_COMPLEX
| EDGE_FALLTHRU
)))
3309 /* Remove all but the fake and fallthru edges. The fake edge may be
3310 the only successor for this block in the case of noreturn
3312 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3314 if (!(e
->flags
& (EDGE_FALLTHRU
| EDGE_FAKE
)))
3316 df_set_bb_dirty (bb
);
3324 gcc_assert (single_succ_p (bb
));
3326 single_succ_edge (bb
)->probability
= profile_probability::always ();
3329 fprintf (dump_file
, "Purged non-fallthru edges from bb %i\n",
3334 /* Search all basic blocks for potentially dead edges and purge them. Return
3335 true if some edge has been eliminated. */
3338 purge_all_dead_edges (void)
3343 FOR_EACH_BB_FN (bb
, cfun
)
3345 bool purged_here
= purge_dead_edges (bb
);
3347 purged
|= purged_here
;
3353 /* This is used by a few passes that emit some instructions after abnormal
3354 calls, moving the basic block's end, while they in fact do want to emit
3355 them on the fallthru edge. Look for abnormal call edges, find backward
3356 the call in the block and insert the instructions on the edge instead.
3358 Similarly, handle instructions throwing exceptions internally.
3360 Return true when instructions have been found and inserted on edges. */
3363 fixup_abnormal_edges (void)
3365 bool inserted
= false;
3368 FOR_EACH_BB_FN (bb
, cfun
)
3373 /* Look for cases we are interested in - calls or instructions causing
3375 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3376 if ((e
->flags
& EDGE_ABNORMAL_CALL
)
3377 || ((e
->flags
& (EDGE_ABNORMAL
| EDGE_EH
))
3378 == (EDGE_ABNORMAL
| EDGE_EH
)))
3381 if (e
&& !CALL_P (BB_END (bb
)) && !can_throw_internal (BB_END (bb
)))
3385 /* Get past the new insns generated. Allow notes, as the insns
3386 may be already deleted. */
3388 while ((NONJUMP_INSN_P (insn
) || NOTE_P (insn
))
3389 && !can_throw_internal (insn
)
3390 && insn
!= BB_HEAD (bb
))
3391 insn
= PREV_INSN (insn
);
3393 if (CALL_P (insn
) || can_throw_internal (insn
))
3395 rtx_insn
*stop
, *next
;
3397 e
= find_fallthru_edge (bb
->succs
);
3399 stop
= NEXT_INSN (BB_END (bb
));
3402 for (insn
= NEXT_INSN (insn
); insn
!= stop
; insn
= next
)
3404 next
= NEXT_INSN (insn
);
3409 /* Sometimes there's still the return value USE.
3410 If it's placed after a trapping call (i.e. that
3411 call is the last insn anyway), we have no fallthru
3412 edge. Simply delete this use and don't try to insert
3413 on the non-existent edge.
3414 Similarly, sometimes a call that can throw is
3415 followed in the source with __builtin_unreachable (),
3416 meaning that there is UB if the call returns rather
3417 than throws. If there weren't any instructions
3418 following such calls before, supposedly even the ones
3419 we've deleted aren't significant and can be
3423 /* We're not deleting it, we're moving it. */
3424 insn
->set_undeleted ();
3425 SET_PREV_INSN (insn
) = NULL_RTX
;
3426 SET_NEXT_INSN (insn
) = NULL_RTX
;
3428 insert_insn_on_edge (insn
, e
);
3432 else if (!BARRIER_P (insn
))
3433 set_block_for_insn (insn
, NULL
);
3437 /* It may be that we don't find any trapping insn. In this
3438 case we discovered quite late that the insn that had been
3439 marked as can_throw_internal in fact couldn't trap at all.
3440 So we should in fact delete the EH edges out of the block. */
3442 purge_dead_edges (bb
);
3449 /* Delete the unconditional jump INSN and adjust the CFG correspondingly.
3450 Note that the INSN should be deleted *after* removing dead edges, so
3451 that the kept edge is the fallthrough edge for a (set (pc) (pc))
3452 but not for a (set (pc) (label_ref FOO)). */
3455 update_cfg_for_uncondjump (rtx_insn
*insn
)
3457 basic_block bb
= BLOCK_FOR_INSN (insn
);
3458 gcc_assert (BB_END (bb
) == insn
);
3460 purge_dead_edges (bb
);
3462 if (current_ir_type () != IR_RTL_CFGLAYOUT
)
3464 if (!find_fallthru_edge (bb
->succs
))
3466 auto barrier
= next_nonnote_nondebug_insn (insn
);
3467 if (!barrier
|| !BARRIER_P (barrier
))
3468 emit_barrier_after (insn
);
3474 if (EDGE_COUNT (bb
->succs
) == 1)
3478 single_succ_edge (bb
)->flags
|= EDGE_FALLTHRU
;
3480 /* Remove barriers from the footer if there are any. */
3481 for (insn
= BB_FOOTER (bb
); insn
; insn
= NEXT_INSN (insn
))
3482 if (BARRIER_P (insn
))
3484 if (PREV_INSN (insn
))
3485 SET_NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
3487 BB_FOOTER (bb
) = NEXT_INSN (insn
);
3488 if (NEXT_INSN (insn
))
3489 SET_PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
3491 else if (LABEL_P (insn
))
3496 /* Cut the insns from FIRST to LAST out of the insns stream. */
3499 unlink_insn_chain (rtx_insn
*first
, rtx_insn
*last
)
3501 rtx_insn
*prevfirst
= PREV_INSN (first
);
3502 rtx_insn
*nextlast
= NEXT_INSN (last
);
3504 SET_PREV_INSN (first
) = NULL
;
3505 SET_NEXT_INSN (last
) = NULL
;
3507 SET_NEXT_INSN (prevfirst
) = nextlast
;
3509 SET_PREV_INSN (nextlast
) = prevfirst
;
3511 set_last_insn (prevfirst
);
3513 set_first_insn (nextlast
);
3517 /* Skip over inter-block insns occurring after BB which are typically
3518 associated with BB (e.g., barriers). If there are any such insns,
3519 we return the last one. Otherwise, we return the end of BB. */
3522 skip_insns_after_block (basic_block bb
)
3524 rtx_insn
*insn
, *last_insn
, *next_head
, *prev
;
3527 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3528 next_head
= BB_HEAD (bb
->next_bb
);
3530 for (last_insn
= insn
= BB_END (bb
); (insn
= NEXT_INSN (insn
)) != 0; )
3532 if (insn
== next_head
)
3535 switch (GET_CODE (insn
))
3542 gcc_assert (NOTE_KIND (insn
) != NOTE_INSN_BLOCK_END
);
3546 if (NEXT_INSN (insn
)
3547 && JUMP_TABLE_DATA_P (NEXT_INSN (insn
)))
3549 insn
= NEXT_INSN (insn
);
3562 /* It is possible to hit contradictory sequence. For instance:
3568 Where barrier belongs to jump_insn, but the note does not. This can be
3569 created by removing the basic block originally following
3570 NOTE_INSN_BLOCK_BEG. In such case reorder the notes. */
3572 for (insn
= last_insn
; insn
!= BB_END (bb
); insn
= prev
)
3574 prev
= PREV_INSN (insn
);
3576 switch (NOTE_KIND (insn
))
3578 case NOTE_INSN_BLOCK_END
:
3581 case NOTE_INSN_DELETED
:
3582 case NOTE_INSN_DELETED_LABEL
:
3583 case NOTE_INSN_DELETED_DEBUG_LABEL
:
3586 reorder_insns (insn
, insn
, last_insn
);
3593 /* Locate or create a label for a given basic block. */
3596 label_for_bb (basic_block bb
)
3598 rtx_insn
*label
= BB_HEAD (bb
);
3600 if (!LABEL_P (label
))
3603 fprintf (dump_file
, "Emitting label for block %d\n", bb
->index
);
3605 label
= block_label (bb
);
3611 /* Locate the effective beginning and end of the insn chain for each
3612 block, as defined by skip_insns_after_block above. */
3615 record_effective_endpoints (void)
3617 rtx_insn
*next_insn
;
3621 for (insn
= get_insns ();
3624 && NOTE_KIND (insn
) != NOTE_INSN_BASIC_BLOCK
;
3625 insn
= NEXT_INSN (insn
))
3627 /* No basic blocks at all? */
3630 if (PREV_INSN (insn
))
3631 cfg_layout_function_header
=
3632 unlink_insn_chain (get_insns (), PREV_INSN (insn
));
3634 cfg_layout_function_header
= NULL
;
3636 next_insn
= get_insns ();
3637 FOR_EACH_BB_FN (bb
, cfun
)
3641 if (PREV_INSN (BB_HEAD (bb
)) && next_insn
!= BB_HEAD (bb
))
3642 BB_HEADER (bb
) = unlink_insn_chain (next_insn
,
3643 PREV_INSN (BB_HEAD (bb
)));
3644 end
= skip_insns_after_block (bb
);
3645 if (NEXT_INSN (BB_END (bb
)) && BB_END (bb
) != end
)
3646 BB_FOOTER (bb
) = unlink_insn_chain (NEXT_INSN (BB_END (bb
)), end
);
3647 next_insn
= NEXT_INSN (BB_END (bb
));
3650 cfg_layout_function_footer
= next_insn
;
3651 if (cfg_layout_function_footer
)
3652 cfg_layout_function_footer
= unlink_insn_chain (cfg_layout_function_footer
, get_last_insn ());
3657 const pass_data pass_data_into_cfg_layout_mode
=
3659 RTL_PASS
, /* type */
3660 "into_cfglayout", /* name */
3661 OPTGROUP_NONE
, /* optinfo_flags */
3663 0, /* properties_required */
3664 PROP_cfglayout
, /* properties_provided */
3665 0, /* properties_destroyed */
3666 0, /* todo_flags_start */
3667 0, /* todo_flags_finish */
3670 class pass_into_cfg_layout_mode
: public rtl_opt_pass
3673 pass_into_cfg_layout_mode (gcc::context
*ctxt
)
3674 : rtl_opt_pass (pass_data_into_cfg_layout_mode
, ctxt
)
3677 /* opt_pass methods: */
3678 virtual unsigned int execute (function
*)
3680 cfg_layout_initialize (0);
3684 }; // class pass_into_cfg_layout_mode
3689 make_pass_into_cfg_layout_mode (gcc::context
*ctxt
)
3691 return new pass_into_cfg_layout_mode (ctxt
);
3696 const pass_data pass_data_outof_cfg_layout_mode
=
3698 RTL_PASS
, /* type */
3699 "outof_cfglayout", /* name */
3700 OPTGROUP_NONE
, /* optinfo_flags */
3702 0, /* properties_required */
3703 0, /* properties_provided */
3704 PROP_cfglayout
, /* properties_destroyed */
3705 0, /* todo_flags_start */
3706 0, /* todo_flags_finish */
3709 class pass_outof_cfg_layout_mode
: public rtl_opt_pass
3712 pass_outof_cfg_layout_mode (gcc::context
*ctxt
)
3713 : rtl_opt_pass (pass_data_outof_cfg_layout_mode
, ctxt
)
3716 /* opt_pass methods: */
3717 virtual unsigned int execute (function
*);
3719 }; // class pass_outof_cfg_layout_mode
3722 pass_outof_cfg_layout_mode::execute (function
*fun
)
3726 FOR_EACH_BB_FN (bb
, fun
)
3727 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (fun
))
3728 bb
->aux
= bb
->next_bb
;
3730 cfg_layout_finalize ();
3738 make_pass_outof_cfg_layout_mode (gcc::context
*ctxt
)
3740 return new pass_outof_cfg_layout_mode (ctxt
);
3744 /* Link the basic blocks in the correct order, compacting the basic
3745 block queue while at it. If STAY_IN_CFGLAYOUT_MODE is false, this
3746 function also clears the basic block header and footer fields.
3748 This function is usually called after a pass (e.g. tracer) finishes
3749 some transformations while in cfglayout mode. The required sequence
3750 of the basic blocks is in a linked list along the bb->aux field.
3751 This functions re-links the basic block prev_bb and next_bb pointers
3752 accordingly, and it compacts and renumbers the blocks.
3754 FIXME: This currently works only for RTL, but the only RTL-specific
3755 bits are the STAY_IN_CFGLAYOUT_MODE bits. The tracer pass was moved
3756 to GIMPLE a long time ago, but it doesn't relink the basic block
3757 chain. It could do that (to give better initial RTL) if this function
3758 is made IR-agnostic (and moved to cfganal.cc or cfg.cc while at it). */
3761 relink_block_chain (bool stay_in_cfglayout_mode
)
3763 basic_block bb
, prev_bb
;
3766 /* Maybe dump the re-ordered sequence. */
3769 fprintf (dump_file
, "Reordered sequence:\n");
3770 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
, index
=
3773 bb
= (basic_block
) bb
->aux
, index
++)
3775 fprintf (dump_file
, " %i ", index
);
3776 if (get_bb_original (bb
))
3777 fprintf (dump_file
, "duplicate of %i\n",
3778 get_bb_original (bb
)->index
);
3779 else if (forwarder_block_p (bb
)
3780 && !LABEL_P (BB_HEAD (bb
)))
3781 fprintf (dump_file
, "compensation\n");
3783 fprintf (dump_file
, "bb %i\n", bb
->index
);
3787 /* Now reorder the blocks. */
3788 prev_bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
3789 bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
;
3790 for (; bb
; prev_bb
= bb
, bb
= (basic_block
) bb
->aux
)
3792 bb
->prev_bb
= prev_bb
;
3793 prev_bb
->next_bb
= bb
;
3795 prev_bb
->next_bb
= EXIT_BLOCK_PTR_FOR_FN (cfun
);
3796 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
= prev_bb
;
3798 /* Then, clean up the aux fields. */
3799 FOR_ALL_BB_FN (bb
, cfun
)
3802 if (!stay_in_cfglayout_mode
)
3803 BB_HEADER (bb
) = BB_FOOTER (bb
) = NULL
;
3806 /* Maybe reset the original copy tables, they are not valid anymore
3807 when we renumber the basic blocks in compact_blocks. If we are
3808 are going out of cfglayout mode, don't re-allocate the tables. */
3809 if (original_copy_tables_initialized_p ())
3810 free_original_copy_tables ();
3811 if (stay_in_cfglayout_mode
)
3812 initialize_original_copy_tables ();
3814 /* Finally, put basic_block_info in the new order. */
3819 /* Given a reorder chain, rearrange the code to match. */
3822 fixup_reorder_chain (void)
3825 rtx_insn
*insn
= NULL
;
3827 if (cfg_layout_function_header
)
3829 set_first_insn (cfg_layout_function_header
);
3830 insn
= cfg_layout_function_header
;
3831 while (NEXT_INSN (insn
))
3832 insn
= NEXT_INSN (insn
);
3835 /* First do the bulk reordering -- rechain the blocks without regard to
3836 the needed changes to jumps and labels. */
3838 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
; bb
; bb
= (basic_block
)
3844 SET_NEXT_INSN (insn
) = BB_HEADER (bb
);
3846 set_first_insn (BB_HEADER (bb
));
3847 SET_PREV_INSN (BB_HEADER (bb
)) = insn
;
3848 insn
= BB_HEADER (bb
);
3849 while (NEXT_INSN (insn
))
3850 insn
= NEXT_INSN (insn
);
3853 SET_NEXT_INSN (insn
) = BB_HEAD (bb
);
3855 set_first_insn (BB_HEAD (bb
));
3856 SET_PREV_INSN (BB_HEAD (bb
)) = insn
;
3860 SET_NEXT_INSN (insn
) = BB_FOOTER (bb
);
3861 SET_PREV_INSN (BB_FOOTER (bb
)) = insn
;
3862 while (NEXT_INSN (insn
))
3863 insn
= NEXT_INSN (insn
);
3867 SET_NEXT_INSN (insn
) = cfg_layout_function_footer
;
3868 if (cfg_layout_function_footer
)
3869 SET_PREV_INSN (cfg_layout_function_footer
) = insn
;
3871 while (NEXT_INSN (insn
))
3872 insn
= NEXT_INSN (insn
);
3874 set_last_insn (insn
);
3876 verify_insn_chain ();
3878 /* Now add jumps and labels as needed to match the blocks new
3881 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
; bb
; bb
= (basic_block
)
3884 edge e_fall
, e_taken
, e
;
3885 rtx_insn
*bb_end_insn
;
3886 rtx ret_label
= NULL_RTX
;
3890 if (EDGE_COUNT (bb
->succs
) == 0)
3893 /* Find the old fallthru edge, and another non-EH edge for
3895 e_taken
= e_fall
= NULL
;
3897 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3898 if (e
->flags
& EDGE_FALLTHRU
)
3900 else if (! (e
->flags
& EDGE_EH
))
3903 bb_end_insn
= BB_END (bb
);
3904 if (rtx_jump_insn
*bb_end_jump
= dyn_cast
<rtx_jump_insn
*> (bb_end_insn
))
3906 ret_label
= JUMP_LABEL (bb_end_jump
);
3907 if (any_condjump_p (bb_end_jump
))
3909 /* This might happen if the conditional jump has side
3910 effects and could therefore not be optimized away.
3911 Make the basic block to end with a barrier in order
3912 to prevent rtl_verify_flow_info from complaining. */
3915 gcc_assert (!onlyjump_p (bb_end_jump
)
3916 || returnjump_p (bb_end_jump
)
3917 || (e_taken
->flags
& EDGE_CROSSING
));
3918 emit_barrier_after (bb_end_jump
);
3922 /* If the old fallthru is still next, nothing to do. */
3923 if (bb
->aux
== e_fall
->dest
3924 || e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3927 /* The degenerated case of conditional jump jumping to the next
3928 instruction can happen for jumps with side effects. We need
3929 to construct a forwarder block and this will be done just
3930 fine by force_nonfallthru below. */
3934 /* There is another special case: if *neither* block is next,
3935 such as happens at the very end of a function, then we'll
3936 need to add a new unconditional jump. Choose the taken
3937 edge based on known or assumed probability. */
3938 else if (bb
->aux
!= e_taken
->dest
)
3940 rtx note
= find_reg_note (bb_end_jump
, REG_BR_PROB
, 0);
3943 && profile_probability::from_reg_br_prob_note
3944 (XINT (note
, 0)) < profile_probability::even ()
3945 && invert_jump (bb_end_jump
,
3947 == EXIT_BLOCK_PTR_FOR_FN (cfun
)
3949 : label_for_bb (e_fall
->dest
)), 0))
3951 e_fall
->flags
&= ~EDGE_FALLTHRU
;
3952 gcc_checking_assert (could_fall_through
3953 (e_taken
->src
, e_taken
->dest
));
3954 e_taken
->flags
|= EDGE_FALLTHRU
;
3955 update_br_prob_note (bb
);
3956 e
= e_fall
, e_fall
= e_taken
, e_taken
= e
;
3960 /* If the "jumping" edge is a crossing edge, and the fall
3961 through edge is non-crossing, leave things as they are. */
3962 else if ((e_taken
->flags
& EDGE_CROSSING
)
3963 && !(e_fall
->flags
& EDGE_CROSSING
))
3966 /* Otherwise we can try to invert the jump. This will
3967 basically never fail, however, keep up the pretense. */
3968 else if (invert_jump (bb_end_jump
,
3970 == EXIT_BLOCK_PTR_FOR_FN (cfun
)
3972 : label_for_bb (e_fall
->dest
)), 0))
3974 e_fall
->flags
&= ~EDGE_FALLTHRU
;
3975 gcc_checking_assert (could_fall_through
3976 (e_taken
->src
, e_taken
->dest
));
3977 e_taken
->flags
|= EDGE_FALLTHRU
;
3978 update_br_prob_note (bb
);
3979 if (LABEL_NUSES (ret_label
) == 0
3980 && single_pred_p (e_taken
->dest
))
3981 delete_insn (as_a
<rtx_insn
*> (ret_label
));
3985 else if (extract_asm_operands (PATTERN (bb_end_insn
)) != NULL
)
3987 /* If the old fallthru is still next or if
3988 asm goto doesn't have a fallthru (e.g. when followed by
3989 __builtin_unreachable ()), nothing to do. */
3991 || bb
->aux
== e_fall
->dest
3992 || e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3995 /* Otherwise we'll have to use the fallthru fixup below. */
3999 /* Otherwise we have some return, switch or computed
4000 jump. In the 99% case, there should not have been a
4002 gcc_assert (returnjump_p (bb_end_insn
) || !e_fall
);
4008 /* No fallthru implies a noreturn function with EH edges, or
4009 something similarly bizarre. In any case, we don't need to
4014 /* If the fallthru block is still next, nothing to do. */
4015 if (bb
->aux
== e_fall
->dest
)
4018 /* A fallthru to exit block. */
4019 if (e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4023 /* We got here if we need to add a new jump insn.
4024 Note force_nonfallthru can delete E_FALL and thus we have to
4025 save E_FALL->src prior to the call to force_nonfallthru. */
4026 nb
= force_nonfallthru_and_redirect (e_fall
, e_fall
->dest
, ret_label
);
4031 /* Don't process this new block. */
4036 relink_block_chain (/*stay_in_cfglayout_mode=*/false);
4038 /* Annoying special case - jump around dead jumptables left in the code. */
4039 FOR_EACH_BB_FN (bb
, cfun
)
4041 edge e
= find_fallthru_edge (bb
->succs
);
4043 if (e
&& !can_fallthru (e
->src
, e
->dest
))
4044 force_nonfallthru (e
);
4047 /* Ensure goto_locus from edges has some instructions with that locus in RTL
4048 when not optimizing. */
4049 if (!optimize
&& !DECL_IGNORED_P (current_function_decl
))
4050 FOR_EACH_BB_FN (bb
, cfun
)
4055 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
4056 if (LOCATION_LOCUS (e
->goto_locus
) != UNKNOWN_LOCATION
4057 && !(e
->flags
& EDGE_ABNORMAL
))
4061 basic_block dest
, nb
;
4064 insn
= BB_END (e
->src
);
4065 end
= PREV_INSN (BB_HEAD (e
->src
));
4067 && (!NONDEBUG_INSN_P (insn
) || !INSN_HAS_LOCATION (insn
)))
4068 insn
= PREV_INSN (insn
);
4070 && INSN_LOCATION (insn
) == e
->goto_locus
)
4072 if (simplejump_p (BB_END (e
->src
))
4073 && !INSN_HAS_LOCATION (BB_END (e
->src
)))
4075 INSN_LOCATION (BB_END (e
->src
)) = e
->goto_locus
;
4079 if (dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4081 /* Non-fallthru edges to the exit block cannot be split. */
4082 if (!(e
->flags
& EDGE_FALLTHRU
))
4087 insn
= BB_HEAD (dest
);
4088 end
= NEXT_INSN (BB_END (dest
));
4089 while (insn
!= end
&& !NONDEBUG_INSN_P (insn
))
4090 insn
= NEXT_INSN (insn
);
4091 if (insn
!= end
&& INSN_HAS_LOCATION (insn
)
4092 && INSN_LOCATION (insn
) == e
->goto_locus
)
4095 nb
= split_edge (e
);
4096 if (!INSN_P (BB_END (nb
)))
4097 BB_END (nb
) = emit_insn_after_noloc (gen_nop (), BB_END (nb
),
4099 INSN_LOCATION (BB_END (nb
)) = e
->goto_locus
;
4101 /* If there are other incoming edges to the destination block
4102 with the same goto locus, redirect them to the new block as
4103 well, this can prevent other such blocks from being created
4104 in subsequent iterations of the loop. */
4105 for (ei2
= ei_start (dest
->preds
); (e2
= ei_safe_edge (ei2
)); )
4106 if (LOCATION_LOCUS (e2
->goto_locus
) != UNKNOWN_LOCATION
4107 && !(e2
->flags
& (EDGE_ABNORMAL
| EDGE_FALLTHRU
))
4108 && e
->goto_locus
== e2
->goto_locus
)
4109 redirect_edge_and_branch (e2
, nb
);
4116 /* Perform sanity checks on the insn chain.
4117 1. Check that next/prev pointers are consistent in both the forward and
4119 2. Count insns in chain, going both directions, and check if equal.
4120 3. Check that get_last_insn () returns the actual end of chain. */
4123 verify_insn_chain (void)
4125 rtx_insn
*x
, *prevx
, *nextx
;
4126 int insn_cnt1
, insn_cnt2
;
4128 for (prevx
= NULL
, insn_cnt1
= 1, x
= get_insns ();
4130 prevx
= x
, insn_cnt1
++, x
= NEXT_INSN (x
))
4131 gcc_assert (PREV_INSN (x
) == prevx
);
4133 gcc_assert (prevx
== get_last_insn ());
4135 for (nextx
= NULL
, insn_cnt2
= 1, x
= get_last_insn ();
4137 nextx
= x
, insn_cnt2
++, x
= PREV_INSN (x
))
4138 gcc_assert (NEXT_INSN (x
) == nextx
);
4140 gcc_assert (insn_cnt1
== insn_cnt2
);
4143 /* If we have assembler epilogues, the block falling through to exit must
4144 be the last one in the reordered chain when we reach final. Ensure
4145 that this condition is met. */
4147 fixup_fallthru_exit_predecessor (void)
4150 basic_block bb
= NULL
;
4152 /* This transformation is not valid before reload, because we might
4153 separate a call from the instruction that copies the return
4155 gcc_assert (reload_completed
);
4157 e
= find_fallthru_edge (EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
);
4163 basic_block c
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
;
4165 /* If the very first block is the one with the fall-through exit
4166 edge, we have to split that block. */
4169 bb
= split_block_after_labels (bb
)->dest
;
4172 BB_FOOTER (bb
) = BB_FOOTER (c
);
4173 BB_FOOTER (c
) = NULL
;
4176 while (c
->aux
!= bb
)
4177 c
= (basic_block
) c
->aux
;
4181 c
= (basic_block
) c
->aux
;
4188 /* In case there are more than one fallthru predecessors of exit, force that
4189 there is only one. */
4192 force_one_exit_fallthru (void)
4194 edge e
, predecessor
= NULL
;
4197 basic_block forwarder
, bb
;
4199 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
4200 if (e
->flags
& EDGE_FALLTHRU
)
4202 if (predecessor
== NULL
)
4214 /* Exit has several fallthru predecessors. Create a forwarder block for
4216 forwarder
= split_edge (predecessor
);
4217 for (ei
= ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
);
4218 (e
= ei_safe_edge (ei
)); )
4220 if (e
->src
== forwarder
4221 || !(e
->flags
& EDGE_FALLTHRU
))
4224 redirect_edge_and_branch_force (e
, forwarder
);
4227 /* Fix up the chain of blocks -- make FORWARDER immediately precede the
4229 FOR_EACH_BB_FN (bb
, cfun
)
4231 if (bb
->aux
== NULL
&& bb
!= forwarder
)
4233 bb
->aux
= forwarder
;
4239 /* Return true in case it is possible to duplicate the basic block BB. */
4242 cfg_layout_can_duplicate_bb_p (const_basic_block bb
)
4244 /* Do not attempt to duplicate tablejumps, as we need to unshare
4245 the dispatch table. This is difficult to do, as the instructions
4246 computing jump destination may be hoisted outside the basic block. */
4247 if (tablejump_p (BB_END (bb
), NULL
, NULL
))
4250 /* Do not duplicate blocks containing insns that can't be copied. */
4251 if (targetm
.cannot_copy_insn_p
)
4253 rtx_insn
*insn
= BB_HEAD (bb
);
4256 if (INSN_P (insn
) && targetm
.cannot_copy_insn_p (insn
))
4258 if (insn
== BB_END (bb
))
4260 insn
= NEXT_INSN (insn
);
4268 duplicate_insn_chain (rtx_insn
*from
, rtx_insn
*to
,
4269 class loop
*loop
, copy_bb_data
*id
)
4271 rtx_insn
*insn
, *next
, *copy
;
4274 /* Avoid updating of boundaries of previous basic block. The
4275 note will get removed from insn stream in fixup. */
4276 last
= emit_note (NOTE_INSN_DELETED
);
4278 /* Create copy at the end of INSN chain. The chain will
4279 be reordered later. */
4280 for (insn
= from
; insn
!= NEXT_INSN (to
); insn
= NEXT_INSN (insn
))
4282 switch (GET_CODE (insn
))
4285 /* Don't duplicate label debug insns. */
4286 if (DEBUG_BIND_INSN_P (insn
)
4287 && TREE_CODE (INSN_VAR_LOCATION_DECL (insn
)) == LABEL_DECL
)
4293 copy
= emit_copy_of_insn_after (insn
, get_last_insn ());
4294 if (JUMP_P (insn
) && JUMP_LABEL (insn
) != NULL_RTX
4295 && ANY_RETURN_P (JUMP_LABEL (insn
)))
4296 JUMP_LABEL (copy
) = JUMP_LABEL (insn
);
4297 maybe_copy_prologue_epilogue_insn (insn
, copy
);
4298 /* If requested remap dependence info of cliques brought in
4302 subrtx_iterator::array_type array
;
4303 FOR_EACH_SUBRTX (iter
, array
, PATTERN (insn
), ALL
)
4304 if (MEM_P (*iter
) && MEM_EXPR (*iter
))
4306 tree op
= MEM_EXPR (*iter
);
4307 if (TREE_CODE (op
) == WITH_SIZE_EXPR
)
4308 op
= TREE_OPERAND (op
, 0);
4309 while (handled_component_p (op
))
4310 op
= TREE_OPERAND (op
, 0);
4311 if ((TREE_CODE (op
) == MEM_REF
4312 || TREE_CODE (op
) == TARGET_MEM_REF
)
4313 && MR_DEPENDENCE_CLIQUE (op
) > 1
4315 || (MR_DEPENDENCE_CLIQUE (op
)
4316 != loop
->owned_clique
)))
4318 if (!id
->dependence_map
)
4319 id
->dependence_map
= new hash_map
<dependence_hash
,
4322 unsigned short &newc
= id
->dependence_map
->get_or_insert
4323 (MR_DEPENDENCE_CLIQUE (op
), &existed
);
4327 (MR_DEPENDENCE_CLIQUE (op
) <= cfun
->last_clique
);
4328 newc
= ++cfun
->last_clique
;
4330 /* We cannot adjust MR_DEPENDENCE_CLIQUE in-place
4331 since MEM_EXPR is shared so make a copy and
4332 walk to the subtree again. */
4333 tree new_expr
= unshare_expr (MEM_EXPR (*iter
));
4334 if (TREE_CODE (new_expr
) == WITH_SIZE_EXPR
)
4335 new_expr
= TREE_OPERAND (new_expr
, 0);
4336 while (handled_component_p (new_expr
))
4337 new_expr
= TREE_OPERAND (new_expr
, 0);
4338 MR_DEPENDENCE_CLIQUE (new_expr
) = newc
;
4339 set_mem_expr (const_cast <rtx
> (*iter
), new_expr
);
4345 case JUMP_TABLE_DATA
:
4346 /* Avoid copying of dispatch tables. We never duplicate
4347 tablejumps, so this can hit only in case the table got
4348 moved far from original jump.
4349 Avoid copying following barrier as well if any
4350 (and debug insns in between). */
4351 for (next
= NEXT_INSN (insn
);
4352 next
!= NEXT_INSN (to
);
4353 next
= NEXT_INSN (next
))
4354 if (!DEBUG_INSN_P (next
))
4356 if (next
!= NEXT_INSN (to
) && BARRIER_P (next
))
4368 switch (NOTE_KIND (insn
))
4370 /* In case prologue is empty and function contain label
4371 in first BB, we may want to copy the block. */
4372 case NOTE_INSN_PROLOGUE_END
:
4374 case NOTE_INSN_DELETED
:
4375 case NOTE_INSN_DELETED_LABEL
:
4376 case NOTE_INSN_DELETED_DEBUG_LABEL
:
4377 /* No problem to strip these. */
4378 case NOTE_INSN_FUNCTION_BEG
:
4379 /* There is always just single entry to function. */
4380 case NOTE_INSN_BASIC_BLOCK
:
4381 /* We should only switch text sections once. */
4382 case NOTE_INSN_SWITCH_TEXT_SECTIONS
:
4385 case NOTE_INSN_EPILOGUE_BEG
:
4386 case NOTE_INSN_UPDATE_SJLJ_CONTEXT
:
4387 emit_note_copy (as_a
<rtx_note
*> (insn
));
4391 /* All other notes should have already been eliminated. */
4399 insn
= NEXT_INSN (last
);
4404 /* Create a duplicate of the basic block BB. */
4407 cfg_layout_duplicate_bb (basic_block bb
, copy_bb_data
*id
)
4412 class loop
*loop
= (id
&& current_loops
) ? bb
->loop_father
: NULL
;
4414 insn
= duplicate_insn_chain (BB_HEAD (bb
), BB_END (bb
), loop
, id
);
4415 new_bb
= create_basic_block (insn
,
4416 insn
? get_last_insn () : NULL
,
4417 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
);
4419 BB_COPY_PARTITION (new_bb
, bb
);
4422 insn
= BB_HEADER (bb
);
4423 while (NEXT_INSN (insn
))
4424 insn
= NEXT_INSN (insn
);
4425 insn
= duplicate_insn_chain (BB_HEADER (bb
), insn
, loop
, id
);
4427 BB_HEADER (new_bb
) = unlink_insn_chain (insn
, get_last_insn ());
4432 insn
= BB_FOOTER (bb
);
4433 while (NEXT_INSN (insn
))
4434 insn
= NEXT_INSN (insn
);
4435 insn
= duplicate_insn_chain (BB_FOOTER (bb
), insn
, loop
, id
);
4437 BB_FOOTER (new_bb
) = unlink_insn_chain (insn
, get_last_insn ());
4444 /* Main entry point to this module - initialize the datastructures for
4445 CFG layout changes. It keeps LOOPS up-to-date if not null.
4447 FLAGS is a set of additional flags to pass to cleanup_cfg(). */
4450 cfg_layout_initialize (int flags
)
4455 /* Once bb partitioning is complete, cfg layout mode should not be
4456 re-entered. Entering cfg layout mode may require fixups. As an
4457 example, if edge forwarding performed when optimizing the cfg
4458 layout required moving a block from the hot to the cold
4459 section. This would create an illegal partitioning unless some
4460 manual fixup was performed. */
4461 gcc_assert (!crtl
->bb_reorder_complete
|| !crtl
->has_bb_partition
);
4463 initialize_original_copy_tables ();
4465 cfg_layout_rtl_register_cfg_hooks ();
4467 record_effective_endpoints ();
4469 /* Make sure that the targets of non local gotos are marked. */
4470 for (x
= nonlocal_goto_handler_labels
; x
; x
= x
->next ())
4472 bb
= BLOCK_FOR_INSN (x
->insn ());
4473 bb
->flags
|= BB_NON_LOCAL_GOTO_TARGET
;
4476 cleanup_cfg (CLEANUP_CFGLAYOUT
| flags
);
4479 /* Splits superblocks. */
4481 break_superblocks (void)
4486 auto_sbitmap
superblocks (last_basic_block_for_fn (cfun
));
4487 bitmap_clear (superblocks
);
4489 FOR_EACH_BB_FN (bb
, cfun
)
4490 if (bb
->flags
& BB_SUPERBLOCK
)
4492 bb
->flags
&= ~BB_SUPERBLOCK
;
4493 bitmap_set_bit (superblocks
, bb
->index
);
4499 rebuild_jump_labels (get_insns ());
4500 find_many_sub_basic_blocks (superblocks
);
4504 /* Finalize the changes: reorder insn list according to the sequence specified
4505 by aux pointers, enter compensation code, rebuild scope forest. */
4508 cfg_layout_finalize (void)
4510 free_dominance_info (CDI_DOMINATORS
);
4511 force_one_exit_fallthru ();
4512 rtl_register_cfg_hooks ();
4513 if (reload_completed
&& !targetm
.have_epilogue ())
4514 fixup_fallthru_exit_predecessor ();
4515 fixup_reorder_chain ();
4517 rebuild_jump_labels (get_insns ());
4518 delete_dead_jumptables ();
4521 verify_insn_chain ();
4522 checking_verify_flow_info ();
4526 /* Same as split_block but update cfg_layout structures. */
4529 cfg_layout_split_block (basic_block bb
, void *insnp
)
4531 rtx insn
= (rtx
) insnp
;
4532 basic_block new_bb
= rtl_split_block (bb
, insn
);
4534 BB_FOOTER (new_bb
) = BB_FOOTER (bb
);
4535 BB_FOOTER (bb
) = NULL
;
4540 /* Redirect Edge to DEST. */
4542 cfg_layout_redirect_edge_and_branch (edge e
, basic_block dest
)
4544 basic_block src
= e
->src
;
4547 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
4550 if (e
->dest
== dest
)
4553 if (e
->flags
& EDGE_CROSSING
4554 && BB_PARTITION (e
->src
) == BB_PARTITION (dest
)
4555 && simplejump_p (BB_END (src
)))
4559 "Removing crossing jump while redirecting edge form %i to %i\n",
4560 e
->src
->index
, dest
->index
);
4561 delete_insn (BB_END (src
));
4562 remove_barriers_from_footer (src
);
4563 e
->flags
|= EDGE_FALLTHRU
;
4566 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4567 && (ret
= try_redirect_by_replacing_jump (e
, dest
, true)))
4569 df_set_bb_dirty (src
);
4573 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4574 && (e
->flags
& EDGE_FALLTHRU
) && !(e
->flags
& EDGE_COMPLEX
))
4577 fprintf (dump_file
, "Redirecting entry edge from bb %i to %i\n",
4578 e
->src
->index
, dest
->index
);
4580 df_set_bb_dirty (e
->src
);
4581 redirect_edge_succ (e
, dest
);
4585 /* Redirect_edge_and_branch may decide to turn branch into fallthru edge
4586 in the case the basic block appears to be in sequence. Avoid this
4589 if (e
->flags
& EDGE_FALLTHRU
)
4591 /* Redirect any branch edges unified with the fallthru one. */
4592 if (JUMP_P (BB_END (src
))
4593 && label_is_jump_target_p (BB_HEAD (e
->dest
),
4599 fprintf (dump_file
, "Fallthru edge unified with branch "
4600 "%i->%i redirected to %i\n",
4601 e
->src
->index
, e
->dest
->index
, dest
->index
);
4602 e
->flags
&= ~EDGE_FALLTHRU
;
4603 redirected
= redirect_branch_edge (e
, dest
);
4604 gcc_assert (redirected
);
4605 redirected
->flags
|= EDGE_FALLTHRU
;
4606 df_set_bb_dirty (redirected
->src
);
4609 /* In case we are redirecting fallthru edge to the branch edge
4610 of conditional jump, remove it. */
4611 if (EDGE_COUNT (src
->succs
) == 2)
4613 /* Find the edge that is different from E. */
4614 edge s
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
);
4617 && any_condjump_p (BB_END (src
))
4618 && onlyjump_p (BB_END (src
)))
4619 delete_insn (BB_END (src
));
4622 fprintf (dump_file
, "Redirecting fallthru edge %i->%i to %i\n",
4623 e
->src
->index
, e
->dest
->index
, dest
->index
);
4624 ret
= redirect_edge_succ_nodup (e
, dest
);
4627 ret
= redirect_branch_edge (e
, dest
);
4632 fixup_partition_crossing (ret
);
4633 /* We don't want simplejumps in the insn stream during cfglayout. */
4634 gcc_assert (!simplejump_p (BB_END (src
)) || CROSSING_JUMP_P (BB_END (src
)));
4636 df_set_bb_dirty (src
);
4640 /* Simple wrapper as we always can redirect fallthru edges. */
4642 cfg_layout_redirect_edge_and_branch_force (edge e
, basic_block dest
)
4644 edge redirected
= cfg_layout_redirect_edge_and_branch (e
, dest
);
4646 gcc_assert (redirected
);
4650 /* Same as delete_basic_block but update cfg_layout structures. */
4653 cfg_layout_delete_block (basic_block bb
)
4655 rtx_insn
*insn
, *next
, *prev
= PREV_INSN (BB_HEAD (bb
)), *remaints
;
4660 next
= BB_HEAD (bb
);
4662 SET_NEXT_INSN (prev
) = BB_HEADER (bb
);
4664 set_first_insn (BB_HEADER (bb
));
4665 SET_PREV_INSN (BB_HEADER (bb
)) = prev
;
4666 insn
= BB_HEADER (bb
);
4667 while (NEXT_INSN (insn
))
4668 insn
= NEXT_INSN (insn
);
4669 SET_NEXT_INSN (insn
) = next
;
4670 SET_PREV_INSN (next
) = insn
;
4672 next
= NEXT_INSN (BB_END (bb
));
4675 insn
= BB_FOOTER (bb
);
4678 if (BARRIER_P (insn
))
4680 if (PREV_INSN (insn
))
4681 SET_NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
4683 BB_FOOTER (bb
) = NEXT_INSN (insn
);
4684 if (NEXT_INSN (insn
))
4685 SET_PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
4689 insn
= NEXT_INSN (insn
);
4694 SET_NEXT_INSN (insn
) = BB_FOOTER (bb
);
4695 SET_PREV_INSN (BB_FOOTER (bb
)) = insn
;
4696 while (NEXT_INSN (insn
))
4697 insn
= NEXT_INSN (insn
);
4698 SET_NEXT_INSN (insn
) = next
;
4700 SET_PREV_INSN (next
) = insn
;
4702 set_last_insn (insn
);
4705 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
4706 to
= &BB_HEADER (bb
->next_bb
);
4708 to
= &cfg_layout_function_footer
;
4710 rtl_delete_block (bb
);
4713 prev
= NEXT_INSN (prev
);
4715 prev
= get_insns ();
4717 next
= PREV_INSN (next
);
4719 next
= get_last_insn ();
4721 if (next
&& NEXT_INSN (next
) != prev
)
4723 remaints
= unlink_insn_chain (prev
, next
);
4725 while (NEXT_INSN (insn
))
4726 insn
= NEXT_INSN (insn
);
4727 SET_NEXT_INSN (insn
) = *to
;
4729 SET_PREV_INSN (*to
) = insn
;
4734 /* Return true when blocks A and B can be safely merged. */
4737 cfg_layout_can_merge_blocks_p (basic_block a
, basic_block b
)
4739 /* If we are partitioning hot/cold basic blocks, we don't want to
4740 mess up unconditional or indirect jumps that cross between hot
4743 Basic block partitioning may result in some jumps that appear to
4744 be optimizable (or blocks that appear to be mergeable), but which really
4745 must be left untouched (they are required to make it safely across
4746 partition boundaries). See the comments at the top of
4747 bb-reorder.cc:partition_hot_cold_basic_blocks for complete details. */
4749 if (BB_PARTITION (a
) != BB_PARTITION (b
))
4752 /* Protect the loop latches. */
4753 if (current_loops
&& b
->loop_father
->latch
== b
)
4756 /* If we would end up moving B's instructions, make sure it doesn't fall
4757 through into the exit block, since we cannot recover from a fallthrough
4758 edge into the exit block occurring in the middle of a function. */
4759 if (NEXT_INSN (BB_END (a
)) != BB_HEAD (b
))
4761 edge e
= find_fallthru_edge (b
->succs
);
4762 if (e
&& e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4766 /* There must be exactly one edge in between the blocks. */
4767 return (single_succ_p (a
)
4768 && single_succ (a
) == b
4769 && single_pred_p (b
) == 1
4771 /* Must be simple edge. */
4772 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
4773 && a
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4774 && b
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
4775 /* If the jump insn has side effects, we can't kill the edge.
4776 When not optimizing, try_redirect_by_replacing_jump will
4777 not allow us to redirect an edge by replacing a table jump. */
4778 && (!JUMP_P (BB_END (a
))
4779 || ((!optimize
|| reload_completed
)
4780 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
4783 /* Merge block A and B. The blocks must be mergeable. */
4786 cfg_layout_merge_blocks (basic_block a
, basic_block b
)
4788 /* If B is a forwarder block whose outgoing edge has no location, we'll
4789 propagate the locus of the edge between A and B onto it. */
4790 const bool forward_edge_locus
4791 = (b
->flags
& BB_FORWARDER_BLOCK
) != 0
4792 && LOCATION_LOCUS (EDGE_SUCC (b
, 0)->goto_locus
) == UNKNOWN_LOCATION
;
4795 gcc_checking_assert (cfg_layout_can_merge_blocks_p (a
, b
));
4798 fprintf (dump_file
, "Merging block %d into block %d...\n", b
->index
,
4801 /* If there was a CODE_LABEL beginning B, delete it. */
4802 if (LABEL_P (BB_HEAD (b
)))
4804 delete_insn (BB_HEAD (b
));
4807 /* We should have fallthru edge in a, or we can do dummy redirection to get
4809 if (JUMP_P (BB_END (a
)))
4810 try_redirect_by_replacing_jump (EDGE_SUCC (a
, 0), b
, true);
4811 gcc_assert (!JUMP_P (BB_END (a
)));
4813 /* If not optimizing, preserve the locus of the single edge between
4814 blocks A and B if necessary by emitting a nop. */
4816 && !forward_edge_locus
4817 && !DECL_IGNORED_P (current_function_decl
))
4818 emit_nop_for_unique_locus_between (a
, b
);
4820 /* Move things from b->footer after a->footer. */
4824 BB_FOOTER (a
) = BB_FOOTER (b
);
4827 rtx_insn
*last
= BB_FOOTER (a
);
4829 while (NEXT_INSN (last
))
4830 last
= NEXT_INSN (last
);
4831 SET_NEXT_INSN (last
) = BB_FOOTER (b
);
4832 SET_PREV_INSN (BB_FOOTER (b
)) = last
;
4834 BB_FOOTER (b
) = NULL
;
4837 /* Move things from b->header before a->footer.
4838 Note that this may include dead tablejump data, but we don't clean
4839 those up until we go out of cfglayout mode. */
4842 if (! BB_FOOTER (a
))
4843 BB_FOOTER (a
) = BB_HEADER (b
);
4846 rtx_insn
*last
= BB_HEADER (b
);
4848 while (NEXT_INSN (last
))
4849 last
= NEXT_INSN (last
);
4850 SET_NEXT_INSN (last
) = BB_FOOTER (a
);
4851 SET_PREV_INSN (BB_FOOTER (a
)) = last
;
4852 BB_FOOTER (a
) = BB_HEADER (b
);
4854 BB_HEADER (b
) = NULL
;
4857 /* In the case basic blocks are not adjacent, move them around. */
4858 if (NEXT_INSN (BB_END (a
)) != BB_HEAD (b
))
4860 insn
= unlink_insn_chain (BB_HEAD (b
), BB_END (b
));
4862 emit_insn_after_noloc (insn
, BB_END (a
), a
);
4864 /* Otherwise just re-associate the instructions. */
4868 BB_END (a
) = BB_END (b
);
4871 /* emit_insn_after_noloc doesn't call df_insn_change_bb.
4872 We need to explicitly call. */
4873 update_bb_for_insn_chain (insn
, BB_END (b
), a
);
4875 /* Skip possible DELETED_LABEL insn. */
4876 if (!NOTE_INSN_BASIC_BLOCK_P (insn
))
4877 insn
= NEXT_INSN (insn
);
4878 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
4879 BB_HEAD (b
) = BB_END (b
) = NULL
;
4882 df_bb_delete (b
->index
);
4884 if (forward_edge_locus
)
4885 EDGE_SUCC (b
, 0)->goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
4888 fprintf (dump_file
, "Merged blocks %d and %d.\n", a
->index
, b
->index
);
4894 cfg_layout_split_edge (edge e
)
4896 basic_block new_bb
=
4897 create_basic_block (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4898 ? NEXT_INSN (BB_END (e
->src
)) : get_insns (),
4901 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4902 BB_COPY_PARTITION (new_bb
, e
->src
);
4904 BB_COPY_PARTITION (new_bb
, e
->dest
);
4905 make_edge (new_bb
, e
->dest
, EDGE_FALLTHRU
);
4906 redirect_edge_and_branch_force (e
, new_bb
);
4911 /* Do postprocessing after making a forwarder block joined by edge FALLTHRU. */
4914 rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED
)
4918 /* Return true if BB contains only labels or non-executable
4922 rtl_block_empty_p (basic_block bb
)
4926 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4927 || bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4930 FOR_BB_INSNS (bb
, insn
)
4931 if (NONDEBUG_INSN_P (insn
)
4932 && (!any_uncondjump_p (insn
) || !onlyjump_p (insn
)))
4938 /* Split a basic block if it ends with a conditional branch and if
4939 the other part of the block is not empty. */
4942 rtl_split_block_before_cond_jump (basic_block bb
)
4945 rtx_insn
*split_point
= NULL
;
4946 rtx_insn
*last
= NULL
;
4947 bool found_code
= false;
4949 FOR_BB_INSNS (bb
, insn
)
4951 if (any_condjump_p (insn
))
4953 else if (NONDEBUG_INSN_P (insn
))
4958 /* Did not find everything. */
4959 if (found_code
&& split_point
)
4960 return split_block (bb
, split_point
)->dest
;
4965 /* Return 1 if BB ends with a call, possibly followed by some
4966 instructions that must stay with the call, 0 otherwise. */
4969 rtl_block_ends_with_call_p (basic_block bb
)
4971 rtx_insn
*insn
= BB_END (bb
);
4973 while (!CALL_P (insn
)
4974 && insn
!= BB_HEAD (bb
)
4975 && (keep_with_call_p (insn
)
4977 || DEBUG_INSN_P (insn
)))
4978 insn
= PREV_INSN (insn
);
4979 return (CALL_P (insn
));
4982 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
4985 rtl_block_ends_with_condjump_p (const_basic_block bb
)
4987 return any_condjump_p (BB_END (bb
));
4990 /* Return true if we need to add fake edge to exit.
4991 Helper function for rtl_flow_call_edges_add. */
4994 need_fake_edge_p (const rtx_insn
*insn
)
5000 && !SIBLING_CALL_P (insn
)
5001 && !find_reg_note (insn
, REG_NORETURN
, NULL
)
5002 && !(RTL_CONST_OR_PURE_CALL_P (insn
))))
5005 return ((GET_CODE (PATTERN (insn
)) == ASM_OPERANDS
5006 && MEM_VOLATILE_P (PATTERN (insn
)))
5007 || (GET_CODE (PATTERN (insn
)) == PARALLEL
5008 && asm_noperands (insn
) != -1
5009 && MEM_VOLATILE_P (XVECEXP (PATTERN (insn
), 0, 0)))
5010 || GET_CODE (PATTERN (insn
)) == ASM_INPUT
);
5013 /* Add fake edges to the function exit for any non constant and non noreturn
5014 calls, volatile inline assembly in the bitmap of blocks specified by
5015 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
5018 The goal is to expose cases in which entering a basic block does not imply
5019 that all subsequent instructions must be executed. */
5022 rtl_flow_call_edges_add (sbitmap blocks
)
5025 int blocks_split
= 0;
5026 int last_bb
= last_basic_block_for_fn (cfun
);
5027 bool check_last_block
= false;
5029 if (n_basic_blocks_for_fn (cfun
) == NUM_FIXED_BLOCKS
)
5033 check_last_block
= true;
5035 check_last_block
= bitmap_bit_p (blocks
,
5036 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
->index
);
5038 /* In the last basic block, before epilogue generation, there will be
5039 a fallthru edge to EXIT. Special care is required if the last insn
5040 of the last basic block is a call because make_edge folds duplicate
5041 edges, which would result in the fallthru edge also being marked
5042 fake, which would result in the fallthru edge being removed by
5043 remove_fake_edges, which would result in an invalid CFG.
5045 Moreover, we can't elide the outgoing fake edge, since the block
5046 profiler needs to take this into account in order to solve the minimal
5047 spanning tree in the case that the call doesn't return.
5049 Handle this by adding a dummy instruction in a new last basic block. */
5050 if (check_last_block
)
5052 basic_block bb
= EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
;
5053 rtx_insn
*insn
= BB_END (bb
);
5055 /* Back up past insns that must be kept in the same block as a call. */
5056 while (insn
!= BB_HEAD (bb
)
5057 && keep_with_call_p (insn
))
5058 insn
= PREV_INSN (insn
);
5060 if (need_fake_edge_p (insn
))
5064 e
= find_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
5067 insert_insn_on_edge (gen_use (const0_rtx
), e
);
5068 commit_edge_insertions ();
5073 /* Now add fake edges to the function exit for any non constant
5074 calls since there is no way that we can determine if they will
5077 for (i
= NUM_FIXED_BLOCKS
; i
< last_bb
; i
++)
5079 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
5081 rtx_insn
*prev_insn
;
5086 if (blocks
&& !bitmap_bit_p (blocks
, i
))
5089 for (insn
= BB_END (bb
); ; insn
= prev_insn
)
5091 prev_insn
= PREV_INSN (insn
);
5092 if (need_fake_edge_p (insn
))
5095 rtx_insn
*split_at_insn
= insn
;
5097 /* Don't split the block between a call and an insn that should
5098 remain in the same block as the call. */
5100 while (split_at_insn
!= BB_END (bb
)
5101 && keep_with_call_p (NEXT_INSN (split_at_insn
)))
5102 split_at_insn
= NEXT_INSN (split_at_insn
);
5104 /* The handling above of the final block before the epilogue
5105 should be enough to verify that there is no edge to the exit
5106 block in CFG already. Calling make_edge in such case would
5107 cause us to mark that edge as fake and remove it later. */
5109 if (flag_checking
&& split_at_insn
== BB_END (bb
))
5111 e
= find_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
5112 gcc_assert (e
== NULL
);
5115 /* Note that the following may create a new basic block
5116 and renumber the existing basic blocks. */
5117 if (split_at_insn
!= BB_END (bb
))
5119 e
= split_block (bb
, split_at_insn
);
5124 edge ne
= make_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), EDGE_FAKE
);
5125 ne
->probability
= profile_probability::guessed_never ();
5128 if (insn
== BB_HEAD (bb
))
5134 verify_flow_info ();
5136 return blocks_split
;
5139 /* Add COMP_RTX as a condition at end of COND_BB. FIRST_HEAD is
5140 the conditional branch target, SECOND_HEAD should be the fall-thru
5141 there is no need to handle this here the loop versioning code handles
5142 this. the reason for SECON_HEAD is that it is needed for condition
5143 in trees, and this should be of the same type since it is a hook. */
5145 rtl_lv_add_condition_to_bb (basic_block first_head
,
5146 basic_block second_head ATTRIBUTE_UNUSED
,
5147 basic_block cond_bb
, void *comp_rtx
)
5149 rtx_code_label
*label
;
5150 rtx_insn
*seq
, *jump
;
5151 rtx op0
= XEXP ((rtx
)comp_rtx
, 0);
5152 rtx op1
= XEXP ((rtx
)comp_rtx
, 1);
5153 enum rtx_code comp
= GET_CODE ((rtx
)comp_rtx
);
5157 label
= block_label (first_head
);
5158 mode
= GET_MODE (op0
);
5159 if (mode
== VOIDmode
)
5160 mode
= GET_MODE (op1
);
5163 op0
= force_operand (op0
, NULL_RTX
);
5164 op1
= force_operand (op1
, NULL_RTX
);
5165 do_compare_rtx_and_jump (op0
, op1
, comp
, 0, mode
, NULL_RTX
, NULL
, label
,
5166 profile_probability::uninitialized ());
5167 jump
= get_last_insn ();
5168 JUMP_LABEL (jump
) = label
;
5169 LABEL_NUSES (label
)++;
5173 /* Add the new cond, in the new head. */
5174 emit_insn_after (seq
, BB_END (cond_bb
));
5178 /* Given a block B with unconditional branch at its end, get the
5179 store the return the branch edge and the fall-thru edge in
5180 BRANCH_EDGE and FALLTHRU_EDGE respectively. */
5182 rtl_extract_cond_bb_edges (basic_block b
, edge
*branch_edge
,
5183 edge
*fallthru_edge
)
5185 edge e
= EDGE_SUCC (b
, 0);
5187 if (e
->flags
& EDGE_FALLTHRU
)
5190 *branch_edge
= EDGE_SUCC (b
, 1);
5195 *fallthru_edge
= EDGE_SUCC (b
, 1);
5200 init_rtl_bb_info (basic_block bb
)
5202 gcc_assert (!bb
->il
.x
.rtl
);
5203 bb
->il
.x
.head_
= NULL
;
5204 bb
->il
.x
.rtl
= ggc_cleared_alloc
<rtl_bb_info
> ();
5208 rtl_bb_info_initialized_p (basic_block bb
)
5210 return bb
->il
.x
.rtl
;
5213 /* Returns true if it is possible to remove edge E by redirecting
5214 it to the destination of the other edge from E->src. */
5217 rtl_can_remove_branch_p (const_edge e
)
5219 const_basic_block src
= e
->src
;
5220 const_basic_block target
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
;
5221 const rtx_insn
*insn
= BB_END (src
);
5224 /* The conditions are taken from try_redirect_by_replacing_jump. */
5225 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
5228 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
5231 if (BB_PARTITION (src
) != BB_PARTITION (target
))
5234 if (!onlyjump_p (insn
)
5235 || tablejump_p (insn
, NULL
, NULL
))
5238 set
= single_set (insn
);
5239 if (!set
|| side_effects_p (set
))
5246 rtl_duplicate_bb (basic_block bb
, copy_bb_data
*id
)
5248 bb
= cfg_layout_duplicate_bb (bb
, id
);
5253 /* Do book-keeping of basic block BB for the profile consistency checker.
5254 Store the counting in RECORD. */
5256 rtl_account_profile_record (basic_block bb
, struct profile_record
*record
)
5259 FOR_BB_INSNS (bb
, insn
)
5262 record
->size
+= insn_cost (insn
, false);
5265 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.ipa ().initialized_p ()
5266 && ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.ipa ().nonzero_p ()
5267 && bb
->count
.ipa ().initialized_p ())
5269 += insn_cost (insn
, true) * bb
->count
.ipa ().to_gcov_type ();
5271 else if (bb
->count
.initialized_p ()
5272 && ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.initialized_p ())
5274 += insn_cost (insn
, true)
5275 * bb
->count
.to_sreal_scale
5276 (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
).to_double ();
5278 record
->time
+= insn_cost (insn
, true);
5282 /* Implementation of CFG manipulation for linearized RTL. */
5283 struct cfg_hooks rtl_cfg_hooks
= {
5285 rtl_verify_flow_info
,
5287 rtl_dump_bb_for_graph
,
5288 rtl_create_basic_block
,
5289 rtl_redirect_edge_and_branch
,
5290 rtl_redirect_edge_and_branch_force
,
5291 rtl_can_remove_branch_p
,
5294 rtl_move_block_after
,
5295 rtl_can_merge_blocks
, /* can_merge_blocks_p */
5299 cfg_layout_can_duplicate_bb_p
,
5302 rtl_make_forwarder_block
,
5303 rtl_tidy_fallthru_edge
,
5304 rtl_force_nonfallthru
,
5305 rtl_block_ends_with_call_p
,
5306 rtl_block_ends_with_condjump_p
,
5307 rtl_flow_call_edges_add
,
5308 NULL
, /* execute_on_growing_pred */
5309 NULL
, /* execute_on_shrinking_pred */
5310 NULL
, /* duplicate loop for trees */
5311 NULL
, /* lv_add_condition_to_bb */
5312 NULL
, /* lv_adjust_loop_header_phi*/
5313 NULL
, /* extract_cond_bb_edges */
5314 NULL
, /* flush_pending_stmts */
5315 rtl_block_empty_p
, /* block_empty_p */
5316 rtl_split_block_before_cond_jump
, /* split_block_before_cond_jump */
5317 rtl_account_profile_record
,
5320 /* Implementation of CFG manipulation for cfg layout RTL, where
5321 basic block connected via fallthru edges does not have to be adjacent.
5322 This representation will hopefully become the default one in future
5323 version of the compiler. */
5325 struct cfg_hooks cfg_layout_rtl_cfg_hooks
= {
5327 rtl_verify_flow_info_1
,
5329 rtl_dump_bb_for_graph
,
5330 cfg_layout_create_basic_block
,
5331 cfg_layout_redirect_edge_and_branch
,
5332 cfg_layout_redirect_edge_and_branch_force
,
5333 rtl_can_remove_branch_p
,
5334 cfg_layout_delete_block
,
5335 cfg_layout_split_block
,
5336 rtl_move_block_after
,
5337 cfg_layout_can_merge_blocks_p
,
5338 cfg_layout_merge_blocks
,
5341 cfg_layout_can_duplicate_bb_p
,
5342 cfg_layout_duplicate_bb
,
5343 cfg_layout_split_edge
,
5344 rtl_make_forwarder_block
,
5345 NULL
, /* tidy_fallthru_edge */
5346 rtl_force_nonfallthru
,
5347 rtl_block_ends_with_call_p
,
5348 rtl_block_ends_with_condjump_p
,
5349 rtl_flow_call_edges_add
,
5350 NULL
, /* execute_on_growing_pred */
5351 NULL
, /* execute_on_shrinking_pred */
5352 duplicate_loop_body_to_header_edge
, /* duplicate loop for trees */
5353 rtl_lv_add_condition_to_bb
, /* lv_add_condition_to_bb */
5354 NULL
, /* lv_adjust_loop_header_phi*/
5355 rtl_extract_cond_bb_edges
, /* extract_cond_bb_edges */
5356 NULL
, /* flush_pending_stmts */
5357 rtl_block_empty_p
, /* block_empty_p */
5358 rtl_split_block_before_cond_jump
, /* split_block_before_cond_jump */
5359 rtl_account_profile_record
,
5362 #include "gt-cfgrtl.h"
5365 # pragma GCC diagnostic pop