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 (NONDEBUG_INSN_P (insn) && BLOCK_FOR_INSN (insn))
240 basic_block bb = BLOCK_FOR_INSN (insn);
241 if (BB_END (bb) == insn)
243 else if (DEBUG_INSN_P (BB_END (bb)))
244 for (rtx_insn *dinsn = NEXT_INSN (insn);
245 DEBUG_INSN_P (dinsn); dinsn = NEXT_INSN (dinsn))
246 if (BB_END (bb) == dinsn)
254 return purge_dead_edges (BLOCK_FOR_INSN (insn));
258 /* Unlink a chain of insns between START and FINISH, leaving notes
259 that must be paired. If CLEAR_BB is true, we set bb field for
260 insns that cannot be removed to NULL. */
263 delete_insn_chain (rtx start, rtx_insn *finish, bool clear_bb)
265 /* Unchain the insns one by one. It would be quicker to delete all of these
266 with a single unchaining, rather than one at a time, but we need to keep
268 rtx_insn *current = finish;
271 rtx_insn *prev = PREV_INSN (current);
272 if (NOTE_P (current) && !can_delete_note_p (as_a <rtx_note *> (current)))
275 delete_insn (current);
277 if (clear_bb && !current->deleted ())
278 set_block_for_insn (current, NULL);
280 if (current == start)
286 /* Create a new basic block consisting of the instructions between HEAD and END
287 inclusive. This function is designed to allow fast BB construction - reuses
288 the note and basic block struct in BB_NOTE, if any and do not grow
289 BASIC_BLOCK chain and should be used directly only by CFG construction code.
290 END can be NULL in to create new empty basic block before HEAD. Both END
291 and HEAD can be NULL to create basic block at the end of INSN chain.
292 AFTER is the basic block we should be put after. */
295 create_basic_block_structure (rtx_insn *head, rtx_insn *end, rtx_note *bb_note,
301 && (bb = NOTE_BASIC_BLOCK (bb_note)) != NULL
304 /* If we found an existing note, thread it back onto the chain. */
312 after = PREV_INSN (head);
316 if (after != bb_note && NEXT_INSN (after) != bb_note)
317 reorder_insns_nobb (bb_note, bb_note, after);
321 /* Otherwise we must create a note and a basic block structure. */
325 init_rtl_bb_info (bb);
328 = emit_note_after (NOTE_INSN_BASIC_BLOCK, get_last_insn ());
329 else if (LABEL_P (head) && end)
331 bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, head);
337 bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, head);
343 NOTE_BASIC_BLOCK (bb_note) = bb;
346 /* Always include the bb note in the block. */
347 if (NEXT_INSN (end) == bb_note)
352 bb->index = last_basic_block_for_fn (cfun)++;
353 bb->flags = BB_NEW | BB_RTL;
354 link_block (bb, after);
355 SET_BASIC_BLOCK_FOR_FN (cfun, bb->index, bb);
356 df_bb_refs_record (bb->index, false);
357 update_bb_for_insn (bb);
358 BB_SET_PARTITION (bb, BB_UNPARTITIONED);
360 /* Tag the block so that we know it has been used when considering
361 other basic block notes. */
367 /* Create new basic block consisting of instructions in between HEAD and END
368 and place it to the BB chain after block AFTER. END can be NULL to
369 create a new empty basic block before HEAD. Both END and HEAD can be
370 NULL to create basic block at the end of INSN chain. */
373 rtl_create_basic_block (void *headp, void *endp, basic_block after)
375 rtx_insn *head = (rtx_insn *) headp;
376 rtx_insn *end = (rtx_insn *) endp;
379 /* Grow the basic block array if needed. */
380 if ((size_t) last_basic_block_for_fn (cfun)
381 >= basic_block_info_for_fn (cfun)->length ())
382 vec_safe_grow_cleared (basic_block_info_for_fn (cfun),
383 last_basic_block_for_fn (cfun) + 1);
385 n_basic_blocks_for_fn (cfun)++;
387 bb = create_basic_block_structure (head, end, NULL, after);
393 cfg_layout_create_basic_block (void *head, void *end, basic_block after)
395 basic_block newbb = rtl_create_basic_block (head, end, after);
400 /* Delete the insns in a (non-live) block. We physically delete every
401 non-deleted-note insn, and update the flow graph appropriately.
403 Return nonzero if we deleted an exception handler. */
405 /* ??? Preserving all such notes strikes me as wrong. It would be nice
406 to post-process the stream to remove empty blocks, loops, ranges, etc. */
409 rtl_delete_block (basic_block b)
411 rtx_insn *insn, *end;
413 /* If the head of this block is a CODE_LABEL, then it might be the
414 label for an exception handler which can't be reached. We need
415 to remove the label from the exception_handler_label list. */
418 end = get_last_bb_insn (b);
420 /* Selectively delete the entire chain. */
422 delete_insn_chain (insn, end, true);
426 fprintf (dump_file, "deleting block %d\n", b->index);
427 df_bb_delete (b->index);
430 /* Records the basic block struct in BLOCK_FOR_INSN for every insn. */
433 compute_bb_for_insn (void)
437 FOR_EACH_BB_FN (bb, cfun)
439 rtx_insn *end = BB_END (bb);
442 for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
444 BLOCK_FOR_INSN (insn) = bb;
451 /* Release the basic_block_for_insn array. */
454 free_bb_for_insn (void)
457 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
458 if (!BARRIER_P (insn))
459 BLOCK_FOR_INSN (insn) = NULL;
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 unsigned int execute (function *) final override;
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 LOC1 and LOC2 are equivalent for
782 unique_locus_on_edge_between_p purposes. */
785 loc_equal (location_t loc1, location_t loc2)
790 expanded_location loce1 = expand_location (loc1);
791 expanded_location loce2 = expand_location (loc2);
793 if (loce1.line != loce2.line
794 || loce1.column != loce2.column
795 || loce1.data != loce2.data)
797 if (loce1.file == loce2.file)
799 return (loce1.file != NULL
800 && loce2.file != NULL
801 && filename_cmp (loce1.file, loce2.file) == 0);
804 /* Return true if the single edge between blocks A and B is the only place
805 in RTL which holds some unique locus. */
808 unique_locus_on_edge_between_p (basic_block a, basic_block b)
810 const location_t goto_locus = EDGE_SUCC (a, 0)->goto_locus;
811 rtx_insn *insn, *end;
813 if (LOCATION_LOCUS (goto_locus) == UNKNOWN_LOCATION)
816 /* First scan block A backward. */
818 end = PREV_INSN (BB_HEAD (a));
819 while (insn != end && (!NONDEBUG_INSN_P (insn) || !INSN_HAS_LOCATION (insn)))
820 insn = PREV_INSN (insn);
822 if (insn != end && loc_equal (INSN_LOCATION (insn), goto_locus))
825 /* Then scan block B forward. */
829 end = NEXT_INSN (BB_END (b));
830 while (insn != end && !NONDEBUG_INSN_P (insn))
831 insn = NEXT_INSN (insn);
833 if (insn != end && INSN_HAS_LOCATION (insn)
834 && loc_equal (INSN_LOCATION (insn), goto_locus))
841 /* If the single edge between blocks A and B is the only place in RTL which
842 holds some unique locus, emit a nop with that locus between the blocks. */
845 emit_nop_for_unique_locus_between (basic_block a, basic_block b)
847 if (!unique_locus_on_edge_between_p (a, b))
850 BB_END (a) = emit_insn_after_noloc (gen_nop (), BB_END (a), a);
851 INSN_LOCATION (BB_END (a)) = EDGE_SUCC (a, 0)->goto_locus;
854 /* Blocks A and B are to be merged into a single block A. The insns
855 are already contiguous. */
858 rtl_merge_blocks (basic_block a, basic_block b)
860 /* If B is a forwarder block whose outgoing edge has no location, we'll
861 propagate the locus of the edge between A and B onto it. */
862 const bool forward_edge_locus
863 = (b->flags & BB_FORWARDER_BLOCK) != 0
864 && LOCATION_LOCUS (EDGE_SUCC (b, 0)->goto_locus) == UNKNOWN_LOCATION;
865 rtx_insn *b_head = BB_HEAD (b), *b_end = BB_END (b), *a_end = BB_END (a);
866 rtx_insn *del_first = NULL, *del_last = NULL;
867 rtx_insn *b_debug_start = b_end, *b_debug_end = b_end;
871 fprintf (dump_file, "Merging block %d into block %d...\n", b->index,
874 while (DEBUG_INSN_P (b_end))
875 b_end = PREV_INSN (b_debug_start = b_end);
877 /* If there was a CODE_LABEL beginning B, delete it. */
878 if (LABEL_P (b_head))
880 /* Detect basic blocks with nothing but a label. This can happen
881 in particular at the end of a function. */
885 del_first = del_last = b_head;
886 b_head = NEXT_INSN (b_head);
889 /* Delete the basic block note and handle blocks containing just that
891 if (NOTE_INSN_BASIC_BLOCK_P (b_head))
899 b_head = NEXT_INSN (b_head);
902 /* If there was a jump out of A, delete it. */
907 for (prev = PREV_INSN (a_end); ; prev = PREV_INSN (prev))
909 || NOTE_INSN_BASIC_BLOCK_P (prev)
910 || prev == BB_HEAD (a))
915 a_end = PREV_INSN (del_first);
917 else if (BARRIER_P (NEXT_INSN (a_end)))
918 del_first = NEXT_INSN (a_end);
920 /* Delete everything marked above as well as crap that might be
921 hanging out between the two blocks. */
923 BB_HEAD (b) = b_empty ? NULL : b_head;
924 delete_insn_chain (del_first, del_last, true);
926 /* If not optimizing, preserve the locus of the single edge between
927 blocks A and B if necessary by emitting a nop. */
929 && !forward_edge_locus
930 && !DECL_IGNORED_P (current_function_decl))
932 emit_nop_for_unique_locus_between (a, b);
936 /* Reassociate the insns of B with A. */
939 update_bb_for_insn_chain (a_end, b_debug_end, a);
941 BB_END (a) = b_debug_end;
944 else if (b_end != b_debug_end)
946 /* Move any deleted labels and other notes between the end of A
947 and the debug insns that make up B after the debug insns,
948 bringing the debug insns into A while keeping the notes after
950 if (NEXT_INSN (a_end) != b_debug_start)
951 reorder_insns_nobb (NEXT_INSN (a_end), PREV_INSN (b_debug_start),
953 update_bb_for_insn_chain (b_debug_start, b_debug_end, a);
954 BB_END (a) = b_debug_end;
957 df_bb_delete (b->index);
959 if (forward_edge_locus)
960 EDGE_SUCC (b, 0)->goto_locus = EDGE_SUCC (a, 0)->goto_locus;
963 fprintf (dump_file, "Merged blocks %d and %d.\n", a->index, b->index);
967 /* Return true when block A and B can be merged. */
970 rtl_can_merge_blocks (basic_block a, basic_block b)
972 /* If we are partitioning hot/cold basic blocks, we don't want to
973 mess up unconditional or indirect jumps that cross between hot
976 Basic block partitioning may result in some jumps that appear to
977 be optimizable (or blocks that appear to be mergeable), but which really
978 must be left untouched (they are required to make it safely across
979 partition boundaries). See the comments at the top of
980 bb-reorder.cc:partition_hot_cold_basic_blocks for complete details. */
982 if (BB_PARTITION (a) != BB_PARTITION (b))
985 /* Protect the loop latches. */
986 if (current_loops && b->loop_father->latch == b)
989 /* There must be exactly one edge in between the blocks. */
990 return (single_succ_p (a)
991 && single_succ (a) == b
994 /* Must be simple edge. */
995 && !(single_succ_edge (a)->flags & EDGE_COMPLEX)
997 && a != ENTRY_BLOCK_PTR_FOR_FN (cfun)
998 && b != EXIT_BLOCK_PTR_FOR_FN (cfun)
999 /* If the jump insn has side effects,
1000 we can't kill the edge. */
1001 && (!JUMP_P (BB_END (a))
1002 || (reload_completed
1003 ? simplejump_p (BB_END (a)) : onlyjump_p (BB_END (a)))));
1006 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
1010 block_label (basic_block block)
1012 if (block == EXIT_BLOCK_PTR_FOR_FN (cfun))
1015 if (!LABEL_P (BB_HEAD (block)))
1017 BB_HEAD (block) = emit_label_before (gen_label_rtx (), BB_HEAD (block));
1020 return as_a <rtx_code_label *> (BB_HEAD (block));
1023 /* Remove all barriers from BB_FOOTER of a BB. */
1026 remove_barriers_from_footer (basic_block bb)
1028 rtx_insn *insn = BB_FOOTER (bb);
1030 /* Remove barriers but keep jumptables. */
1033 if (BARRIER_P (insn))
1035 if (PREV_INSN (insn))
1036 SET_NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
1038 BB_FOOTER (bb) = NEXT_INSN (insn);
1039 if (NEXT_INSN (insn))
1040 SET_PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
1044 insn = NEXT_INSN (insn);
1048 /* Attempt to perform edge redirection by replacing possibly complex jump
1049 instruction by unconditional jump or removing jump completely. This can
1050 apply only if all edges now point to the same block. The parameters and
1051 return values are equivalent to redirect_edge_and_branch. */
1054 try_redirect_by_replacing_jump (edge e, basic_block target, bool in_cfglayout)
1056 basic_block src = e->src;
1057 rtx_insn *insn = BB_END (src);
1061 /* If we are partitioning hot/cold basic blocks, we don't want to
1062 mess up unconditional or indirect jumps that cross between hot
1065 Basic block partitioning may result in some jumps that appear to
1066 be optimizable (or blocks that appear to be mergeable), but which really
1067 must be left untouched (they are required to make it safely across
1068 partition boundaries). See the comments at the top of
1069 bb-reorder.cc:partition_hot_cold_basic_blocks for complete details. */
1071 if (BB_PARTITION (src) != BB_PARTITION (target))
1074 /* We can replace or remove a complex jump only when we have exactly
1075 two edges. Also, if we have exactly one outgoing edge, we can
1077 if (EDGE_COUNT (src->succs) >= 3
1078 /* Verify that all targets will be TARGET. Specifically, the
1079 edge that is not E must also go to TARGET. */
1080 || (EDGE_COUNT (src->succs) == 2
1081 && EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target))
1084 if (!onlyjump_p (insn))
1086 if ((!optimize || reload_completed) && tablejump_p (insn, NULL, NULL))
1089 /* Avoid removing branch with side effects. */
1090 set = single_set (insn);
1091 if (!set || side_effects_p (set))
1094 /* See if we can create the fallthru edge. */
1095 if (in_cfglayout || can_fallthru (src, target))
1098 fprintf (dump_file, "Removing jump %i.\n", INSN_UID (insn));
1101 /* Selectively unlink whole insn chain. */
1104 delete_insn_chain (insn, BB_END (src), false);
1105 remove_barriers_from_footer (src);
1108 delete_insn_chain (insn, PREV_INSN (BB_HEAD (target)), false);
1111 /* If this already is simplejump, redirect it. */
1112 else if (simplejump_p (insn))
1114 if (e->dest == target)
1117 fprintf (dump_file, "Redirecting jump %i from %i to %i.\n",
1118 INSN_UID (insn), e->dest->index, target->index);
1119 if (!redirect_jump (as_a <rtx_jump_insn *> (insn),
1120 block_label (target), 0))
1122 gcc_assert (target == EXIT_BLOCK_PTR_FOR_FN (cfun));
1127 /* Cannot do anything for target exit block. */
1128 else if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
1131 /* Or replace possibly complicated jump insn by simple jump insn. */
1134 rtx_code_label *target_label = block_label (target);
1137 rtx_jump_table_data *table;
1139 emit_jump_insn_after_noloc (targetm.gen_jump (target_label), insn);
1140 JUMP_LABEL (BB_END (src)) = target_label;
1141 LABEL_NUSES (target_label)++;
1143 fprintf (dump_file, "Replacing insn %i by jump %i\n",
1144 INSN_UID (insn), INSN_UID (BB_END (src)));
1147 delete_insn_chain (insn, insn, false);
1149 /* Recognize a tablejump that we are converting to a
1150 simple jump and remove its associated CODE_LABEL
1151 and ADDR_VEC or ADDR_DIFF_VEC. */
1152 if (tablejump_p (insn, &label, &table))
1153 delete_insn_chain (label, table, false);
1155 barrier = next_nonnote_nondebug_insn (BB_END (src));
1156 if (!barrier || !BARRIER_P (barrier))
1157 emit_barrier_after (BB_END (src));
1160 if (barrier != NEXT_INSN (BB_END (src)))
1162 /* Move the jump before barrier so that the notes
1163 which originally were or were created before jump table are
1164 inside the basic block. */
1165 rtx_insn *new_insn = BB_END (src);
1167 update_bb_for_insn_chain (NEXT_INSN (BB_END (src)),
1168 PREV_INSN (barrier), src);
1170 SET_NEXT_INSN (PREV_INSN (new_insn)) = NEXT_INSN (new_insn);
1171 SET_PREV_INSN (NEXT_INSN (new_insn)) = PREV_INSN (new_insn);
1173 SET_NEXT_INSN (new_insn) = barrier;
1174 SET_NEXT_INSN (PREV_INSN (barrier)) = new_insn;
1176 SET_PREV_INSN (new_insn) = PREV_INSN (barrier);
1177 SET_PREV_INSN (barrier) = new_insn;
1182 /* Keep only one edge out and set proper flags. */
1183 if (!single_succ_p (src))
1185 gcc_assert (single_succ_p (src));
1187 e = single_succ_edge (src);
1189 e->flags = EDGE_FALLTHRU;
1193 e->probability = profile_probability::always ();
1195 if (e->dest != target)
1196 redirect_edge_succ (e, target);
1200 /* Subroutine of redirect_branch_edge that tries to patch the jump
1201 instruction INSN so that it reaches block NEW. Do this
1202 only when it originally reached block OLD. Return true if this
1203 worked or the original target wasn't OLD, return false if redirection
1207 patch_jump_insn (rtx_insn *insn, rtx_insn *old_label, basic_block new_bb)
1209 rtx_jump_table_data *table;
1211 /* Recognize a tablejump and adjust all matching cases. */
1212 if (tablejump_p (insn, NULL, &table))
1216 rtx_code_label *new_label = block_label (new_bb);
1218 if (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1220 vec = table->get_labels ();
1222 for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
1223 if (XEXP (RTVEC_ELT (vec, j), 0) == old_label)
1225 RTVEC_ELT (vec, j) = gen_rtx_LABEL_REF (Pmode, new_label);
1226 --LABEL_NUSES (old_label);
1227 ++LABEL_NUSES (new_label);
1230 /* Handle casesi dispatch insns. */
1231 if ((tmp = tablejump_casesi_pattern (insn)) != NULL_RTX
1232 && label_ref_label (XEXP (SET_SRC (tmp), 2)) == old_label)
1234 XEXP (SET_SRC (tmp), 2) = gen_rtx_LABEL_REF (Pmode,
1236 --LABEL_NUSES (old_label);
1237 ++LABEL_NUSES (new_label);
1240 else if ((tmp = extract_asm_operands (PATTERN (insn))) != NULL)
1242 int i, n = ASM_OPERANDS_LABEL_LENGTH (tmp);
1245 if (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1247 rtx_code_label *new_label = block_label (new_bb);
1249 for (i = 0; i < n; ++i)
1251 rtx old_ref = ASM_OPERANDS_LABEL (tmp, i);
1252 gcc_assert (GET_CODE (old_ref) == LABEL_REF);
1253 if (XEXP (old_ref, 0) == old_label)
1255 ASM_OPERANDS_LABEL (tmp, i)
1256 = gen_rtx_LABEL_REF (Pmode, new_label);
1257 --LABEL_NUSES (old_label);
1258 ++LABEL_NUSES (new_label);
1262 if (JUMP_LABEL (insn) == old_label)
1264 JUMP_LABEL (insn) = new_label;
1265 note = find_reg_note (insn, REG_LABEL_TARGET, new_label);
1267 remove_note (insn, note);
1271 note = find_reg_note (insn, REG_LABEL_TARGET, old_label);
1273 remove_note (insn, note);
1274 if (JUMP_LABEL (insn) != new_label
1275 && !find_reg_note (insn, REG_LABEL_TARGET, new_label))
1276 add_reg_note (insn, REG_LABEL_TARGET, new_label);
1278 while ((note = find_reg_note (insn, REG_LABEL_OPERAND, old_label))
1280 XEXP (note, 0) = new_label;
1284 /* ?? We may play the games with moving the named labels from
1285 one basic block to the other in case only one computed_jump is
1287 if (computed_jump_p (insn)
1288 /* A return instruction can't be redirected. */
1289 || returnjump_p (insn))
1292 if (!currently_expanding_to_rtl || JUMP_LABEL (insn) == old_label)
1294 /* If the insn doesn't go where we think, we're confused. */
1295 gcc_assert (JUMP_LABEL (insn) == old_label);
1297 /* If the substitution doesn't succeed, die. This can happen
1298 if the back end emitted unrecognizable instructions or if
1299 target is exit block on some arches. Or for crossing
1301 if (!redirect_jump (as_a <rtx_jump_insn *> (insn),
1302 block_label (new_bb), 0))
1304 gcc_assert (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
1305 || CROSSING_JUMP_P (insn));
1314 /* Redirect edge representing branch of (un)conditional jump or tablejump,
1317 redirect_branch_edge (edge e, basic_block target)
1319 rtx_insn *old_label = BB_HEAD (e->dest);
1320 basic_block src = e->src;
1321 rtx_insn *insn = BB_END (src);
1323 /* We can only redirect non-fallthru edges of jump insn. */
1324 if (e->flags & EDGE_FALLTHRU)
1326 else if (!JUMP_P (insn) && !currently_expanding_to_rtl)
1329 if (!currently_expanding_to_rtl)
1331 if (!patch_jump_insn (as_a <rtx_jump_insn *> (insn), old_label, target))
1335 /* When expanding this BB might actually contain multiple
1336 jumps (i.e. not yet split by find_many_sub_basic_blocks).
1337 Redirect all of those that match our label. */
1338 FOR_BB_INSNS (src, insn)
1339 if (JUMP_P (insn) && !patch_jump_insn (as_a <rtx_jump_insn *> (insn),
1344 fprintf (dump_file, "Edge %i->%i redirected to %i\n",
1345 e->src->index, e->dest->index, target->index);
1347 if (e->dest != target)
1348 e = redirect_edge_succ_nodup (e, target);
1353 /* Called when edge E has been redirected to a new destination,
1354 in order to update the region crossing flag on the edge and
1358 fixup_partition_crossing (edge e)
1360 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun) || e->dest
1361 == EXIT_BLOCK_PTR_FOR_FN (cfun))
1363 /* If we redirected an existing edge, it may already be marked
1364 crossing, even though the new src is missing a reg crossing note.
1365 But make sure reg crossing note doesn't already exist before
1367 if (BB_PARTITION (e->src) != BB_PARTITION (e->dest))
1369 e->flags |= EDGE_CROSSING;
1370 if (JUMP_P (BB_END (e->src)))
1371 CROSSING_JUMP_P (BB_END (e->src)) = 1;
1373 else if (BB_PARTITION (e->src) == BB_PARTITION (e->dest))
1375 e->flags &= ~EDGE_CROSSING;
1376 /* Remove the section crossing note from jump at end of
1377 src if it exists, and if no other successors are
1379 if (JUMP_P (BB_END (e->src)) && CROSSING_JUMP_P (BB_END (e->src)))
1381 bool has_crossing_succ = false;
1384 FOR_EACH_EDGE (e2, ei, e->src->succs)
1386 has_crossing_succ |= (e2->flags & EDGE_CROSSING);
1387 if (has_crossing_succ)
1390 if (!has_crossing_succ)
1391 CROSSING_JUMP_P (BB_END (e->src)) = 0;
1396 /* Called when block BB has been reassigned to the cold partition,
1397 because it is now dominated by another cold block,
1398 to ensure that the region crossing attributes are updated. */
1401 fixup_new_cold_bb (basic_block bb)
1406 /* This is called when a hot bb is found to now be dominated
1407 by a cold bb and therefore needs to become cold. Therefore,
1408 its preds will no longer be region crossing. Any non-dominating
1409 preds that were previously hot would also have become cold
1410 in the caller for the same region. Any preds that were previously
1411 region-crossing will be adjusted in fixup_partition_crossing. */
1412 FOR_EACH_EDGE (e, ei, bb->preds)
1414 fixup_partition_crossing (e);
1417 /* Possibly need to make bb's successor edges region crossing,
1418 or remove stale region crossing. */
1419 FOR_EACH_EDGE (e, ei, bb->succs)
1421 /* We can't have fall-through edges across partition boundaries.
1422 Note that force_nonfallthru will do any necessary partition
1423 boundary fixup by calling fixup_partition_crossing itself. */
1424 if ((e->flags & EDGE_FALLTHRU)
1425 && BB_PARTITION (bb) != BB_PARTITION (e->dest)
1426 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1427 force_nonfallthru (e);
1429 fixup_partition_crossing (e);
1433 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
1434 expense of adding new instructions or reordering basic blocks.
1436 Function can be also called with edge destination equivalent to the TARGET.
1437 Then it should try the simplifications and do nothing if none is possible.
1439 Return edge representing the branch if transformation succeeded. Return NULL
1441 We still return NULL in case E already destinated TARGET and we didn't
1442 managed to simplify instruction stream. */
1445 rtl_redirect_edge_and_branch (edge e, basic_block target)
1448 basic_block src = e->src;
1449 basic_block dest = e->dest;
1451 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
1457 if ((ret = try_redirect_by_replacing_jump (e, target, false)) != NULL)
1459 df_set_bb_dirty (src);
1460 fixup_partition_crossing (ret);
1464 ret = redirect_branch_edge (e, target);
1468 df_set_bb_dirty (src);
1469 fixup_partition_crossing (ret);
1473 /* Emit a barrier after BB, into the footer if we are in CFGLAYOUT mode. */
1476 emit_barrier_after_bb (basic_block bb)
1478 rtx_barrier *barrier = emit_barrier_after (BB_END (bb));
1479 gcc_assert (current_ir_type () == IR_RTL_CFGRTL
1480 || current_ir_type () == IR_RTL_CFGLAYOUT);
1481 if (current_ir_type () == IR_RTL_CFGLAYOUT)
1483 rtx_insn *insn = unlink_insn_chain (barrier, barrier);
1487 rtx_insn *footer_tail = BB_FOOTER (bb);
1489 while (NEXT_INSN (footer_tail))
1490 footer_tail = NEXT_INSN (footer_tail);
1491 if (!BARRIER_P (footer_tail))
1493 SET_NEXT_INSN (footer_tail) = insn;
1494 SET_PREV_INSN (insn) = footer_tail;
1498 BB_FOOTER (bb) = insn;
1502 /* Like force_nonfallthru below, but additionally performs redirection
1503 Used by redirect_edge_and_branch_force. JUMP_LABEL is used only
1504 when redirecting to the EXIT_BLOCK, it is either ret_rtx or
1505 simple_return_rtx, indicating which kind of returnjump to create.
1506 It should be NULL otherwise. */
1509 force_nonfallthru_and_redirect (edge e, basic_block target, rtx jump_label)
1511 basic_block jump_block, new_bb = NULL, src = e->src;
1514 int abnormal_edge_flags = 0;
1515 bool asm_goto_edge = false;
1518 /* In the case the last instruction is conditional jump to the next
1519 instruction, first redirect the jump itself and then continue
1520 by creating a basic block afterwards to redirect fallthru edge. */
1521 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
1522 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
1523 && any_condjump_p (BB_END (e->src))
1524 && JUMP_LABEL (BB_END (e->src)) == BB_HEAD (e->dest))
1527 edge b = unchecked_make_edge (e->src, target, 0);
1530 redirected = redirect_jump (as_a <rtx_jump_insn *> (BB_END (e->src)),
1531 block_label (target), 0);
1532 gcc_assert (redirected);
1534 note = find_reg_note (BB_END (e->src), REG_BR_PROB, NULL_RTX);
1537 int prob = XINT (note, 0);
1539 b->probability = profile_probability::from_reg_br_prob_note (prob);
1540 e->probability -= e->probability;
1544 if (e->flags & EDGE_ABNORMAL)
1546 /* Irritating special case - fallthru edge to the same block as abnormal
1548 We can't redirect abnormal edge, but we still can split the fallthru
1549 one and create separate abnormal edge to original destination.
1550 This allows bb-reorder to make such edge non-fallthru. */
1551 gcc_assert (e->dest == target);
1552 abnormal_edge_flags = e->flags & ~EDGE_FALLTHRU;
1553 e->flags &= EDGE_FALLTHRU;
1557 gcc_assert (e->flags & EDGE_FALLTHRU);
1558 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1560 /* We can't redirect the entry block. Create an empty block
1561 at the start of the function which we use to add the new
1567 basic_block bb = create_basic_block (BB_HEAD (e->dest), NULL,
1568 ENTRY_BLOCK_PTR_FOR_FN (cfun));
1569 bb->count = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count;
1571 /* Make sure new block ends up in correct hot/cold section. */
1572 BB_COPY_PARTITION (bb, e->dest);
1574 /* Change the existing edge's source to be the new block, and add
1575 a new edge from the entry block to the new block. */
1577 for (ei = ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs);
1578 (tmp = ei_safe_edge (ei)); )
1582 ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs->unordered_remove (ei.index);
1592 vec_safe_push (bb->succs, e);
1593 make_single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun), bb,
1598 /* If e->src ends with asm goto, see if any of the ASM_OPERANDS_LABELs
1599 don't point to the target or fallthru label. */
1600 if (JUMP_P (BB_END (e->src))
1601 && target != EXIT_BLOCK_PTR_FOR_FN (cfun)
1602 && (e->flags & EDGE_FALLTHRU)
1603 && (note = extract_asm_operands (PATTERN (BB_END (e->src)))))
1605 int i, n = ASM_OPERANDS_LABEL_LENGTH (note);
1606 bool adjust_jump_target = false;
1608 for (i = 0; i < n; ++i)
1610 if (XEXP (ASM_OPERANDS_LABEL (note, i), 0) == BB_HEAD (e->dest))
1612 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note, i), 0))--;
1613 XEXP (ASM_OPERANDS_LABEL (note, i), 0) = block_label (target);
1614 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note, i), 0))++;
1615 adjust_jump_target = true;
1617 if (XEXP (ASM_OPERANDS_LABEL (note, i), 0) == BB_HEAD (target))
1618 asm_goto_edge = true;
1620 if (adjust_jump_target)
1622 rtx_insn *insn = BB_END (e->src);
1624 rtx_insn *old_label = BB_HEAD (e->dest);
1625 rtx_insn *new_label = BB_HEAD (target);
1627 if (JUMP_LABEL (insn) == old_label)
1629 JUMP_LABEL (insn) = new_label;
1630 note = find_reg_note (insn, REG_LABEL_TARGET, new_label);
1632 remove_note (insn, note);
1636 note = find_reg_note (insn, REG_LABEL_TARGET, old_label);
1638 remove_note (insn, note);
1639 if (JUMP_LABEL (insn) != new_label
1640 && !find_reg_note (insn, REG_LABEL_TARGET, new_label))
1641 add_reg_note (insn, REG_LABEL_TARGET, new_label);
1643 while ((note = find_reg_note (insn, REG_LABEL_OPERAND, old_label))
1645 XEXP (note, 0) = new_label;
1649 if (EDGE_COUNT (e->src->succs) >= 2 || abnormal_edge_flags || asm_goto_edge)
1652 profile_count count = e->count ();
1653 profile_probability probability = e->probability;
1654 /* Create the new structures. */
1656 /* If the old block ended with a tablejump, skip its table
1657 by searching forward from there. Otherwise start searching
1658 forward from the last instruction of the old block. */
1659 rtx_jump_table_data *table;
1660 if (tablejump_p (BB_END (e->src), NULL, &table))
1663 new_head = BB_END (e->src);
1664 new_head = NEXT_INSN (new_head);
1666 jump_block = create_basic_block (new_head, NULL, e->src);
1667 jump_block->count = count;
1669 /* Make sure new block ends up in correct hot/cold section. */
1671 BB_COPY_PARTITION (jump_block, e->src);
1674 new_edge = make_edge (e->src, jump_block, EDGE_FALLTHRU);
1675 new_edge->probability = probability;
1677 /* Redirect old edge. */
1678 redirect_edge_pred (e, jump_block);
1679 e->probability = profile_probability::always ();
1681 /* If e->src was previously region crossing, it no longer is
1682 and the reg crossing note should be removed. */
1683 fixup_partition_crossing (new_edge);
1685 /* If asm goto has any label refs to target's label,
1686 add also edge from asm goto bb to target. */
1689 new_edge->probability /= 2;
1690 jump_block->count /= 2;
1691 edge new_edge2 = make_edge (new_edge->src, target,
1692 e->flags & ~EDGE_FALLTHRU);
1693 new_edge2->probability = probability - new_edge->probability;
1696 new_bb = jump_block;
1699 jump_block = e->src;
1701 loc = e->goto_locus;
1702 e->flags &= ~EDGE_FALLTHRU;
1703 if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
1705 if (jump_label == ret_rtx)
1706 emit_jump_insn_after_setloc (targetm.gen_return (),
1707 BB_END (jump_block), loc);
1710 gcc_assert (jump_label == simple_return_rtx);
1711 emit_jump_insn_after_setloc (targetm.gen_simple_return (),
1712 BB_END (jump_block), loc);
1714 set_return_jump_label (BB_END (jump_block));
1718 rtx_code_label *label = block_label (target);
1719 emit_jump_insn_after_setloc (targetm.gen_jump (label),
1720 BB_END (jump_block), loc);
1721 JUMP_LABEL (BB_END (jump_block)) = label;
1722 LABEL_NUSES (label)++;
1725 /* We might be in cfg layout mode, and if so, the following routine will
1726 insert the barrier correctly. */
1727 emit_barrier_after_bb (jump_block);
1728 redirect_edge_succ_nodup (e, target);
1730 if (abnormal_edge_flags)
1731 make_edge (src, target, abnormal_edge_flags);
1733 df_mark_solutions_dirty ();
1734 fixup_partition_crossing (e);
1738 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1739 (and possibly create new basic block) to make edge non-fallthru.
1740 Return newly created BB or NULL if none. */
1743 rtl_force_nonfallthru (edge e)
1745 return force_nonfallthru_and_redirect (e, e->dest, NULL_RTX);
1748 /* Redirect edge even at the expense of creating new jump insn or
1749 basic block. Return new basic block if created, NULL otherwise.
1750 Conversion must be possible. */
1753 rtl_redirect_edge_and_branch_force (edge e, basic_block target)
1755 if (redirect_edge_and_branch (e, target)
1756 || e->dest == target)
1759 /* In case the edge redirection failed, try to force it to be non-fallthru
1760 and redirect newly created simplejump. */
1761 df_set_bb_dirty (e->src);
1762 return force_nonfallthru_and_redirect (e, target, NULL_RTX);
1765 /* The given edge should potentially be a fallthru edge. If that is in
1766 fact true, delete the jump and barriers that are in the way. */
1769 rtl_tidy_fallthru_edge (edge e)
1772 basic_block b = e->src, c = b->next_bb;
1774 /* ??? In a late-running flow pass, other folks may have deleted basic
1775 blocks by nopping out blocks, leaving multiple BARRIERs between here
1776 and the target label. They ought to be chastised and fixed.
1778 We can also wind up with a sequence of undeletable labels between
1779 one block and the next.
1781 So search through a sequence of barriers, labels, and notes for
1782 the head of block C and assert that we really do fall through. */
1784 for (q = NEXT_INSN (BB_END (b)); q != BB_HEAD (c); q = NEXT_INSN (q))
1785 if (NONDEBUG_INSN_P (q))
1788 /* Remove what will soon cease being the jump insn from the source block.
1789 If block B consisted only of this single jump, turn it into a deleted
1794 && (any_uncondjump_p (q)
1795 || single_succ_p (b)))
1798 rtx_jump_table_data *table;
1800 if (tablejump_p (q, &label, &table))
1802 /* The label is likely mentioned in some instruction before
1803 the tablejump and might not be DCEd, so turn it into
1804 a note instead and move before the tablejump that is going to
1806 const char *name = LABEL_NAME (label);
1807 PUT_CODE (label, NOTE);
1808 NOTE_KIND (label) = NOTE_INSN_DELETED_LABEL;
1809 NOTE_DELETED_LABEL_NAME (label) = name;
1810 reorder_insns (label, label, PREV_INSN (q));
1811 delete_insn (table);
1816 /* Unconditional jumps with side-effects (i.e. which we can't just delete
1817 together with the barrier) should never have a fallthru edge. */
1818 else if (JUMP_P (q) && any_uncondjump_p (q))
1821 /* Selectively unlink the sequence. */
1822 if (q != PREV_INSN (BB_HEAD (c)))
1823 delete_insn_chain (NEXT_INSN (q), PREV_INSN (BB_HEAD (c)), false);
1825 e->flags |= EDGE_FALLTHRU;
1828 /* Should move basic block BB after basic block AFTER. NIY. */
1831 rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED,
1832 basic_block after ATTRIBUTE_UNUSED)
1837 /* Locate the last bb in the same partition as START_BB. */
1840 last_bb_in_partition (basic_block start_bb)
1843 FOR_BB_BETWEEN (bb, start_bb, EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
1845 if (BB_PARTITION (start_bb) != BB_PARTITION (bb->next_bb))
1848 /* Return bb before the exit block. */
1852 /* Split a (typically critical) edge. Return the new block.
1853 The edge must not be abnormal.
1855 ??? The code generally expects to be called on critical edges.
1856 The case of a block ending in an unconditional jump to a
1857 block with multiple predecessors is not handled optimally. */
1860 rtl_split_edge (edge edge_in)
1862 basic_block bb, new_bb;
1865 /* Abnormal edges cannot be split. */
1866 gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
1868 /* We are going to place the new block in front of edge destination.
1869 Avoid existence of fallthru predecessors. */
1870 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1872 edge e = find_fallthru_edge (edge_in->dest->preds);
1875 force_nonfallthru (e);
1878 /* Create the basic block note. */
1879 if (edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1880 before = BB_HEAD (edge_in->dest);
1884 /* If this is a fall through edge to the exit block, the blocks might be
1885 not adjacent, and the right place is after the source. */
1886 if ((edge_in->flags & EDGE_FALLTHRU)
1887 && edge_in->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1889 before = NEXT_INSN (BB_END (edge_in->src));
1890 bb = create_basic_block (before, NULL, edge_in->src);
1891 BB_COPY_PARTITION (bb, edge_in->src);
1895 if (edge_in->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1897 bb = create_basic_block (before, NULL, edge_in->dest->prev_bb);
1898 BB_COPY_PARTITION (bb, edge_in->dest);
1902 basic_block after = edge_in->dest->prev_bb;
1903 /* If this is post-bb reordering, and the edge crosses a partition
1904 boundary, the new block needs to be inserted in the bb chain
1905 at the end of the src partition (since we put the new bb into
1906 that partition, see below). Otherwise we may end up creating
1907 an extra partition crossing in the chain, which is illegal.
1908 It can't go after the src, because src may have a fall-through
1909 to a different block. */
1910 if (crtl->bb_reorder_complete
1911 && (edge_in->flags & EDGE_CROSSING))
1913 after = last_bb_in_partition (edge_in->src);
1914 before = get_last_bb_insn (after);
1915 /* The instruction following the last bb in partition should
1916 be a barrier, since it cannot end in a fall-through. */
1917 gcc_checking_assert (BARRIER_P (before));
1918 before = NEXT_INSN (before);
1920 bb = create_basic_block (before, NULL, after);
1921 /* Put the split bb into the src partition, to avoid creating
1922 a situation where a cold bb dominates a hot bb, in the case
1923 where src is cold and dest is hot. The src will dominate
1924 the new bb (whereas it might not have dominated dest). */
1925 BB_COPY_PARTITION (bb, edge_in->src);
1929 make_single_succ_edge (bb, edge_in->dest, EDGE_FALLTHRU);
1931 /* Can't allow a region crossing edge to be fallthrough. */
1932 if (BB_PARTITION (bb) != BB_PARTITION (edge_in->dest)
1933 && edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1935 new_bb = force_nonfallthru (single_succ_edge (bb));
1936 gcc_assert (!new_bb);
1939 /* For non-fallthru edges, we must adjust the predecessor's
1940 jump instruction to target our new block. */
1941 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1943 edge redirected = redirect_edge_and_branch (edge_in, bb);
1944 gcc_assert (redirected);
1948 if (edge_in->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
1950 /* For asm goto even splitting of fallthru edge might
1951 need insn patching, as other labels might point to the
1953 rtx_insn *last = BB_END (edge_in->src);
1956 && edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
1957 && (extract_asm_operands (PATTERN (last))
1958 || JUMP_LABEL (last) == before)
1959 && patch_jump_insn (last, before, bb))
1960 df_set_bb_dirty (edge_in->src);
1962 redirect_edge_succ (edge_in, bb);
1968 /* Queue instructions for insertion on an edge between two basic blocks.
1969 The new instructions and basic blocks (if any) will not appear in the
1970 CFG until commit_edge_insertions is called. */
1973 insert_insn_on_edge (rtx pattern, edge e)
1975 /* We cannot insert instructions on an abnormal critical edge.
1976 It will be easier to find the culprit if we die now. */
1977 gcc_assert (!((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e)));
1979 if (e->insns.r == NULL_RTX)
1982 push_to_sequence (e->insns.r);
1984 emit_insn (pattern);
1986 e->insns.r = get_insns ();
1990 /* Update the CFG for the instructions queued on edge E. */
1993 commit_one_edge_insertion (edge e)
1995 rtx_insn *before = NULL, *after = NULL, *insns, *tmp, *last;
1998 /* Pull the insns off the edge now since the edge might go away. */
2002 /* Figure out where to put these insns. If the destination has
2003 one predecessor, insert there. Except for the exit block. */
2004 if (single_pred_p (e->dest) && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
2008 /* Get the location correct wrt a code label, and "nice" wrt
2009 a basic block note, and before everything else. */
2012 tmp = NEXT_INSN (tmp);
2013 if (NOTE_INSN_BASIC_BLOCK_P (tmp))
2014 tmp = NEXT_INSN (tmp);
2015 if (tmp == BB_HEAD (bb))
2018 after = PREV_INSN (tmp);
2020 after = get_last_insn ();
2023 /* If the source has one successor and the edge is not abnormal,
2024 insert there. Except for the entry block.
2025 Don't do this if the predecessor ends in a jump other than
2026 unconditional simple jump. E.g. for asm goto that points all
2027 its labels at the fallthru basic block, we can't insert instructions
2028 before the asm goto, as the asm goto can have various of side effects,
2029 and can't emit instructions after the asm goto, as it must end
2031 else if ((e->flags & EDGE_ABNORMAL) == 0
2032 && single_succ_p (e->src)
2033 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
2034 && (!JUMP_P (BB_END (e->src))
2035 || simplejump_p (BB_END (e->src))))
2039 /* It is possible to have a non-simple jump here. Consider a target
2040 where some forms of unconditional jumps clobber a register. This
2041 happens on the fr30 for example.
2043 We know this block has a single successor, so we can just emit
2044 the queued insns before the jump. */
2045 if (JUMP_P (BB_END (bb)))
2046 before = BB_END (bb);
2049 /* We'd better be fallthru, or we've lost track of what's what. */
2050 gcc_assert (e->flags & EDGE_FALLTHRU);
2052 after = BB_END (bb);
2056 /* Otherwise we must split the edge. */
2059 bb = split_edge (e);
2061 /* If E crossed a partition boundary, we needed to make bb end in
2062 a region-crossing jump, even though it was originally fallthru. */
2063 if (JUMP_P (BB_END (bb)))
2064 before = BB_END (bb);
2066 after = BB_END (bb);
2069 /* Now that we've found the spot, do the insertion. */
2072 emit_insn_before_noloc (insns, before, bb);
2073 last = prev_nonnote_insn (before);
2076 last = emit_insn_after_noloc (insns, after, bb);
2078 if (returnjump_p (last))
2080 /* ??? Remove all outgoing edges from BB and add one for EXIT.
2081 This is not currently a problem because this only happens
2082 for the (single) epilogue, which already has a fallthru edge
2085 e = single_succ_edge (bb);
2086 gcc_assert (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
2087 && single_succ_p (bb) && (e->flags & EDGE_FALLTHRU));
2089 e->flags &= ~EDGE_FALLTHRU;
2090 emit_barrier_after (last);
2093 delete_insn (before);
2096 gcc_assert (!JUMP_P (last));
2099 /* Update the CFG for all queued instructions. */
2102 commit_edge_insertions (void)
2106 /* Optimization passes that invoke this routine can cause hot blocks
2107 previously reached by both hot and cold blocks to become dominated only
2108 by cold blocks. This will cause the verification below to fail,
2109 and lead to now cold code in the hot section. In some cases this
2110 may only be visible after newly unreachable blocks are deleted,
2111 which will be done by fixup_partitions. */
2112 fixup_partitions ();
2114 if (!currently_expanding_to_rtl)
2115 checking_verify_flow_info ();
2117 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
2118 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
2123 FOR_EACH_EDGE (e, ei, bb->succs)
2126 if (currently_expanding_to_rtl)
2127 rebuild_jump_labels_chain (e->insns.r);
2128 commit_one_edge_insertion (e);
2134 /* Print out RTL-specific basic block information (live information
2135 at start and end with TDF_DETAILS). FLAGS are the TDF_* masks
2136 documented in dumpfile.h. */
2139 rtl_dump_bb (FILE *outf, basic_block bb, int indent, dump_flags_t flags)
2143 s_indent = (char *) alloca ((size_t) indent + 1);
2144 memset (s_indent, ' ', (size_t) indent);
2145 s_indent[indent] = '\0';
2147 if (df && (flags & TDF_DETAILS))
2149 df_dump_top (bb, outf);
2153 if (bb->index != ENTRY_BLOCK && bb->index != EXIT_BLOCK
2154 && rtl_bb_info_initialized_p (bb))
2156 rtx_insn *last = BB_END (bb);
2158 last = NEXT_INSN (last);
2159 for (rtx_insn *insn = BB_HEAD (bb); insn != last; insn = NEXT_INSN (insn))
2161 if (flags & TDF_DETAILS)
2162 df_dump_insn_top (insn, outf);
2163 if (! (flags & TDF_SLIM))
2164 print_rtl_single (outf, insn);
2166 dump_insn_slim (outf, insn);
2167 if (flags & TDF_DETAILS)
2168 df_dump_insn_bottom (insn, outf);
2172 if (df && (flags & TDF_DETAILS))
2174 df_dump_bottom (bb, outf);
2180 /* Like dump_function_to_file, but for RTL. Print out dataflow information
2181 for the start of each basic block. FLAGS are the TDF_* masks documented
2185 print_rtl_with_bb (FILE *outf, const rtx_insn *rtx_first, dump_flags_t flags)
2187 const rtx_insn *tmp_rtx;
2189 fprintf (outf, "(nil)\n");
2192 enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB };
2193 int max_uid = get_max_uid ();
2194 basic_block *start = XCNEWVEC (basic_block, max_uid);
2195 basic_block *end = XCNEWVEC (basic_block, max_uid);
2196 enum bb_state *in_bb_p = XCNEWVEC (enum bb_state, max_uid);
2199 /* After freeing the CFG, we still have BLOCK_FOR_INSN set on most
2200 insns, but the CFG is not maintained so the basic block info
2201 is not reliable. Therefore it's omitted from the dumps. */
2202 if (! (cfun->curr_properties & PROP_cfg))
2203 flags &= ~TDF_BLOCKS;
2206 df_dump_start (outf);
2208 if (cfun->curr_properties & PROP_cfg)
2210 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2214 start[INSN_UID (BB_HEAD (bb))] = bb;
2215 end[INSN_UID (BB_END (bb))] = bb;
2216 if (flags & TDF_BLOCKS)
2218 for (x = BB_HEAD (bb); x != NULL_RTX; x = NEXT_INSN (x))
2220 enum bb_state state = IN_MULTIPLE_BB;
2222 if (in_bb_p[INSN_UID (x)] == NOT_IN_BB)
2224 in_bb_p[INSN_UID (x)] = state;
2226 if (x == BB_END (bb))
2233 for (tmp_rtx = rtx_first; tmp_rtx != NULL; tmp_rtx = NEXT_INSN (tmp_rtx))
2235 if (flags & TDF_BLOCKS)
2237 bb = start[INSN_UID (tmp_rtx)];
2240 dump_bb_info (outf, bb, 0, dump_flags, true, false);
2241 if (df && (flags & TDF_DETAILS))
2242 df_dump_top (bb, outf);
2245 if (in_bb_p[INSN_UID (tmp_rtx)] == NOT_IN_BB
2246 && !NOTE_P (tmp_rtx)
2247 && !BARRIER_P (tmp_rtx))
2248 fprintf (outf, ";; Insn is not within a basic block\n");
2249 else if (in_bb_p[INSN_UID (tmp_rtx)] == IN_MULTIPLE_BB)
2250 fprintf (outf, ";; Insn is in multiple basic blocks\n");
2253 if (flags & TDF_DETAILS)
2254 df_dump_insn_top (tmp_rtx, outf);
2255 if (! (flags & TDF_SLIM))
2256 print_rtl_single (outf, tmp_rtx);
2258 dump_insn_slim (outf, tmp_rtx);
2259 if (flags & TDF_DETAILS)
2260 df_dump_insn_bottom (tmp_rtx, outf);
2262 bb = end[INSN_UID (tmp_rtx)];
2265 if (flags & TDF_BLOCKS)
2267 dump_bb_info (outf, bb, 0, dump_flags, false, true);
2268 if (df && (flags & TDF_DETAILS))
2269 df_dump_bottom (bb, outf);
2272 /* Emit a hint if the fallthrough target of current basic block
2273 isn't the one placed right next. */
2274 else if (EDGE_COUNT (bb->succs) > 0)
2276 gcc_assert (BB_END (bb) == tmp_rtx);
2277 const rtx_insn *ninsn = NEXT_INSN (tmp_rtx);
2278 /* Bypass intervening deleted-insn notes and debug insns. */
2280 && !NONDEBUG_INSN_P (ninsn)
2281 && !start[INSN_UID (ninsn)])
2282 ninsn = NEXT_INSN (ninsn);
2283 edge e = find_fallthru_edge (bb->succs);
2286 basic_block dest = e->dest;
2287 if (start[INSN_UID (ninsn)] != dest)
2288 fprintf (outf, "%s ; pc falls through to BB %d\n",
2289 print_rtx_head, dest->index);
2301 /* Update the branch probability of BB if a REG_BR_PROB is present. */
2304 update_br_prob_note (basic_block bb)
2307 note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX);
2308 if (!JUMP_P (BB_END (bb)) || !BRANCH_EDGE (bb)->probability.initialized_p ())
2312 rtx *note_link, this_rtx;
2314 note_link = ®_NOTES (BB_END (bb));
2315 for (this_rtx = *note_link; this_rtx; this_rtx = XEXP (this_rtx, 1))
2316 if (this_rtx == note)
2318 *note_link = XEXP (this_rtx, 1);
2325 || XINT (note, 0) == BRANCH_EDGE (bb)->probability.to_reg_br_prob_note ())
2327 XINT (note, 0) = BRANCH_EDGE (bb)->probability.to_reg_br_prob_note ();
2330 /* Get the last insn associated with block BB (that includes barriers and
2331 tablejumps after BB). */
2333 get_last_bb_insn (basic_block bb)
2335 rtx_jump_table_data *table;
2337 rtx_insn *end = BB_END (bb);
2339 /* Include any jump table following the basic block. */
2340 if (tablejump_p (end, NULL, &table))
2343 /* Include any barriers that may follow the basic block. */
2344 tmp = next_nonnote_nondebug_insn_bb (end);
2345 while (tmp && BARRIER_P (tmp))
2348 tmp = next_nonnote_nondebug_insn_bb (end);
2354 /* Add all BBs reachable from entry via hot paths into the SET. */
2357 find_bbs_reachable_by_hot_paths (hash_set<basic_block> *set)
2359 auto_vec<basic_block, 64> worklist;
2361 set->add (ENTRY_BLOCK_PTR_FOR_FN (cfun));
2362 worklist.safe_push (ENTRY_BLOCK_PTR_FOR_FN (cfun));
2364 while (worklist.length () > 0)
2366 basic_block bb = worklist.pop ();
2370 FOR_EACH_EDGE (e, ei, bb->succs)
2371 if (BB_PARTITION (e->dest) != BB_COLD_PARTITION
2372 && !set->add (e->dest))
2373 worklist.safe_push (e->dest);
2377 /* Sanity check partition hotness to ensure that basic blocks in
2378 Â the cold partition don't dominate basic blocks in the hot partition.
2379 If FLAG_ONLY is true, report violations as errors. Otherwise
2380 re-mark the dominated blocks as cold, since this is run after
2381 cfg optimizations that may make hot blocks previously reached
2382 by both hot and cold blocks now only reachable along cold paths. */
2384 static auto_vec<basic_block>
2385 find_partition_fixes (bool flag_only)
2388 auto_vec<basic_block> bbs_to_fix;
2389 hash_set<basic_block> set;
2391 /* Callers check this. */
2392 gcc_checking_assert (crtl->has_bb_partition);
2394 find_bbs_reachable_by_hot_paths (&set);
2396 FOR_EACH_BB_FN (bb, cfun)
2397 if (!set.contains (bb)
2398 && BB_PARTITION (bb) != BB_COLD_PARTITION)
2401 error ("non-cold basic block %d reachable only "
2402 "by paths crossing the cold partition", bb->index);
2404 BB_SET_PARTITION (bb, BB_COLD_PARTITION);
2405 bbs_to_fix.safe_push (bb);
2411 /* Perform cleanup on the hot/cold bb partitioning after optimization
2412 passes that modify the cfg. */
2415 fixup_partitions (void)
2417 if (!crtl->has_bb_partition)
2420 /* Delete any blocks that became unreachable and weren't
2421 already cleaned up, for example during edge forwarding
2422 and convert_jumps_to_returns. This will expose more
2423 opportunities for fixing the partition boundaries here.
2424 Also, the calculation of the dominance graph during verification
2425 will assert if there are unreachable nodes. */
2426 delete_unreachable_blocks ();
2428 /* If there are partitions, do a sanity check on them: A basic block in
2429 Â a cold partition cannot dominate a basic block in a hot partition.
2430 Fixup any that now violate this requirement, as a result of edge
2431 forwarding and unreachable block deletion. Â */
2432 auto_vec<basic_block> bbs_to_fix = find_partition_fixes (false);
2434 /* Do the partition fixup after all necessary blocks have been converted to
2435 cold, so that we only update the region crossings the minimum number of
2436 places, which can require forcing edges to be non fallthru. */
2437 if (! bbs_to_fix.is_empty ())
2441 basic_block bb = bbs_to_fix.pop ();
2442 fixup_new_cold_bb (bb);
2444 while (! bbs_to_fix.is_empty ());
2446 /* Fix up hot cold block grouping if needed. */
2447 if (crtl->bb_reorder_complete && current_ir_type () == IR_RTL_CFGRTL)
2449 basic_block bb, first = NULL, second = NULL;
2450 int current_partition = BB_UNPARTITIONED;
2452 FOR_EACH_BB_FN (bb, cfun)
2454 if (current_partition != BB_UNPARTITIONED
2455 && BB_PARTITION (bb) != current_partition)
2459 else if (second == NULL)
2463 /* If we switch partitions for the 3rd, 5th etc. time,
2464 move bbs first (inclusive) .. second (exclusive) right
2466 basic_block prev_first = first->prev_bb;
2467 basic_block prev_second = second->prev_bb;
2468 basic_block prev_bb = bb->prev_bb;
2469 prev_first->next_bb = second;
2470 second->prev_bb = prev_first;
2471 prev_second->next_bb = bb;
2472 bb->prev_bb = prev_second;
2473 prev_bb->next_bb = first;
2474 first->prev_bb = prev_bb;
2475 rtx_insn *prev_first_insn = PREV_INSN (BB_HEAD (first));
2476 rtx_insn *prev_second_insn
2477 = PREV_INSN (BB_HEAD (second));
2478 rtx_insn *prev_bb_insn = PREV_INSN (BB_HEAD (bb));
2479 SET_NEXT_INSN (prev_first_insn) = BB_HEAD (second);
2480 SET_PREV_INSN (BB_HEAD (second)) = prev_first_insn;
2481 SET_NEXT_INSN (prev_second_insn) = BB_HEAD (bb);
2482 SET_PREV_INSN (BB_HEAD (bb)) = prev_second_insn;
2483 SET_NEXT_INSN (prev_bb_insn) = BB_HEAD (first);
2484 SET_PREV_INSN (BB_HEAD (first)) = prev_bb_insn;
2488 current_partition = BB_PARTITION (bb);
2490 gcc_assert (!second);
2495 /* Verify, in the basic block chain, that there is at most one switch
2496 between hot/cold partitions. This condition will not be true until
2497 after reorder_basic_blocks is called. */
2500 verify_hot_cold_block_grouping (void)
2504 bool switched_sections = false;
2505 int current_partition = BB_UNPARTITIONED;
2507 /* Even after bb reordering is complete, we go into cfglayout mode
2508 again (in compgoto). Ensure we don't call this before going back
2509 into linearized RTL when any layout fixes would have been committed. */
2510 if (!crtl->bb_reorder_complete
2511 || current_ir_type () != IR_RTL_CFGRTL)
2514 FOR_EACH_BB_FN (bb, cfun)
2516 if (current_partition != BB_UNPARTITIONED
2517 && BB_PARTITION (bb) != current_partition)
2519 if (switched_sections)
2521 error ("multiple hot/cold transitions found (bb %i)",
2526 switched_sections = true;
2528 if (!crtl->has_bb_partition)
2529 error ("partition found but function partition flag not set");
2531 current_partition = BB_PARTITION (bb);
2538 /* Perform several checks on the edges out of each block, such as
2539 the consistency of the branch probabilities, the correctness
2540 of hot/cold partition crossing edges, and the number of expected
2541 successor edges. Also verify that the dominance relationship
2542 between hot/cold blocks is sane. */
2545 rtl_verify_edges (void)
2550 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2552 int n_fallthru = 0, n_branch = 0, n_abnormal_call = 0, n_sibcall = 0;
2553 int n_eh = 0, n_abnormal = 0;
2554 edge e, fallthru = NULL;
2557 bool has_crossing_edge = false;
2559 if (JUMP_P (BB_END (bb))
2560 && (note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX))
2561 && EDGE_COUNT (bb->succs) >= 2
2562 && any_condjump_p (BB_END (bb)))
2564 if (!BRANCH_EDGE (bb)->probability.initialized_p ())
2566 if (profile_status_for_fn (cfun) != PROFILE_ABSENT)
2568 error ("verify_flow_info: "
2569 "REG_BR_PROB is set but cfg probability is not");
2573 else if (XINT (note, 0)
2574 != BRANCH_EDGE (bb)->probability.to_reg_br_prob_note ()
2575 && profile_status_for_fn (cfun) != PROFILE_ABSENT)
2577 error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i",
2579 BRANCH_EDGE (bb)->probability.to_reg_br_prob_note ());
2584 FOR_EACH_EDGE (e, ei, bb->succs)
2588 if (e->flags & EDGE_FALLTHRU)
2589 n_fallthru++, fallthru = e;
2591 is_crossing = (BB_PARTITION (e->src) != BB_PARTITION (e->dest)
2592 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
2593 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun));
2594 has_crossing_edge |= is_crossing;
2595 if (e->flags & EDGE_CROSSING)
2599 error ("EDGE_CROSSING incorrectly set across same section");
2602 if (e->flags & EDGE_FALLTHRU)
2604 error ("fallthru edge crosses section boundary in bb %i",
2608 if (e->flags & EDGE_EH)
2610 error ("EH edge crosses section boundary in bb %i",
2614 if (JUMP_P (BB_END (bb)) && !CROSSING_JUMP_P (BB_END (bb)))
2616 error ("No region crossing jump at section boundary in bb %i",
2621 else if (is_crossing)
2623 error ("EDGE_CROSSING missing across section boundary");
2627 if ((e->flags & ~(EDGE_DFS_BACK
2629 | EDGE_IRREDUCIBLE_LOOP
2632 | EDGE_PRESERVE)) == 0)
2635 if (e->flags & EDGE_ABNORMAL_CALL)
2638 if (e->flags & EDGE_SIBCALL)
2641 if (e->flags & EDGE_EH)
2644 if (e->flags & EDGE_ABNORMAL)
2648 if (!has_crossing_edge
2649 && JUMP_P (BB_END (bb))
2650 && CROSSING_JUMP_P (BB_END (bb)))
2652 print_rtl_with_bb (stderr, get_insns (), TDF_BLOCKS | TDF_DETAILS);
2653 error ("Region crossing jump across same section in bb %i",
2658 if (n_eh && !find_reg_note (BB_END (bb), REG_EH_REGION, NULL_RTX))
2660 error ("missing REG_EH_REGION note at the end of bb %i", bb->index);
2665 error ("too many exception handling edges in bb %i", bb->index);
2669 && (!JUMP_P (BB_END (bb))
2670 || (n_branch > 1 && (any_uncondjump_p (BB_END (bb))
2671 || any_condjump_p (BB_END (bb))))))
2673 error ("too many outgoing branch edges from bb %i", bb->index);
2676 if (n_fallthru && any_uncondjump_p (BB_END (bb)))
2678 error ("fallthru edge after unconditional jump in bb %i", bb->index);
2681 if (n_branch != 1 && any_uncondjump_p (BB_END (bb)))
2683 error ("wrong number of branch edges after unconditional jump"
2684 " in bb %i", bb->index);
2687 if (n_branch != 1 && any_condjump_p (BB_END (bb))
2688 && JUMP_LABEL (BB_END (bb)) != BB_HEAD (fallthru->dest))
2690 error ("wrong amount of branch edges after conditional jump"
2691 " in bb %i", bb->index);
2694 if (n_abnormal_call && !CALL_P (BB_END (bb)))
2696 error ("abnormal call edges for non-call insn in bb %i", bb->index);
2699 if (n_sibcall && !CALL_P (BB_END (bb)))
2701 error ("sibcall edges for non-call insn in bb %i", bb->index);
2704 if (n_abnormal > n_eh
2705 && !(CALL_P (BB_END (bb))
2706 && n_abnormal == n_abnormal_call + n_sibcall)
2707 && (!JUMP_P (BB_END (bb))
2708 || any_condjump_p (BB_END (bb))
2709 || any_uncondjump_p (BB_END (bb))))
2711 error ("abnormal edges for no purpose in bb %i", bb->index);
2716 FOR_EACH_EDGE (e, ei, bb->preds)
2719 has_eh = (e->flags & EDGE_EH);
2720 if ((e->flags & EDGE_EH) == has_eh)
2722 error ("EH incoming edge mixed with non-EH incoming edges "
2723 "in bb %i", bb->index);
2729 /* If there are partitions, do a sanity check on them: A basic block in
2730 Â a cold partition cannot dominate a basic block in a hot partition. Â */
2731 if (crtl->has_bb_partition && !err
2732 && current_ir_type () == IR_RTL_CFGLAYOUT)
2734 auto_vec<basic_block> bbs_to_fix = find_partition_fixes (true);
2735 err = !bbs_to_fix.is_empty ();
2742 /* Checks on the instructions within blocks. Currently checks that each
2743 block starts with a basic block note, and that basic block notes and
2744 control flow jumps are not found in the middle of the block. */
2747 rtl_verify_bb_insns (void)
2753 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2755 /* Now check the header of basic
2756 block. It ought to contain optional CODE_LABEL followed
2757 by NOTE_BASIC_BLOCK. */
2761 if (BB_END (bb) == x)
2763 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2771 if (!NOTE_INSN_BASIC_BLOCK_P (x) || NOTE_BASIC_BLOCK (x) != bb)
2773 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2778 if (BB_END (bb) == x)
2779 /* Do checks for empty blocks here. */
2782 for (x = NEXT_INSN (x); x; x = NEXT_INSN (x))
2784 if (NOTE_INSN_BASIC_BLOCK_P (x))
2786 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
2787 INSN_UID (x), bb->index);
2791 if (x == BB_END (bb))
2794 if (control_flow_insn_p (x))
2796 error ("in basic block %d:", bb->index);
2797 fatal_insn ("flow control insn inside a basic block", x);
2806 /* Verify that block pointers for instructions in basic blocks, headers and
2807 footers are set appropriately. */
2810 rtl_verify_bb_pointers (void)
2815 /* Check the general integrity of the basic blocks. */
2816 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2820 if (!(bb->flags & BB_RTL))
2822 error ("BB_RTL flag not set for block %d", bb->index);
2826 FOR_BB_INSNS (bb, insn)
2827 if (BLOCK_FOR_INSN (insn) != bb)
2829 error ("insn %d basic block pointer is %d, should be %d",
2831 BLOCK_FOR_INSN (insn) ? BLOCK_FOR_INSN (insn)->index : 0,
2836 for (insn = BB_HEADER (bb); insn; insn = NEXT_INSN (insn))
2837 if (!BARRIER_P (insn)
2838 && BLOCK_FOR_INSN (insn) != NULL)
2840 error ("insn %d in header of bb %d has non-NULL basic block",
2841 INSN_UID (insn), bb->index);
2844 for (insn = BB_FOOTER (bb); insn; insn = NEXT_INSN (insn))
2845 if (!BARRIER_P (insn)
2846 && BLOCK_FOR_INSN (insn) != NULL)
2848 error ("insn %d in footer of bb %d has non-NULL basic block",
2849 INSN_UID (insn), bb->index);
2858 /* Verify the CFG and RTL consistency common for both underlying RTL and
2861 Currently it does following checks:
2863 - overlapping of basic blocks
2864 - insns with wrong BLOCK_FOR_INSN pointers
2865 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
2866 - tails of basic blocks (ensure that boundary is necessary)
2867 - scans body of the basic block for JUMP_INSN, CODE_LABEL
2868 and NOTE_INSN_BASIC_BLOCK
2869 - verify that no fall_thru edge crosses hot/cold partition boundaries
2870 - verify that there are no pending RTL branch predictions
2871 - verify that hot blocks are not dominated by cold blocks
2873 In future it can be extended check a lot of other stuff as well
2874 (reachability of basic blocks, life information, etc. etc.). */
2877 rtl_verify_flow_info_1 (void)
2881 err |= rtl_verify_bb_pointers ();
2883 err |= rtl_verify_bb_insns ();
2885 err |= rtl_verify_edges ();
2890 /* Walk the instruction chain and verify that bb head/end pointers
2891 are correct, and that instructions are in exactly one bb and have
2892 correct block pointers. */
2895 rtl_verify_bb_insn_chain (void)
2900 rtx_insn *last_head = get_last_insn ();
2901 basic_block *bb_info;
2902 const int max_uid = get_max_uid ();
2904 bb_info = XCNEWVEC (basic_block, max_uid);
2906 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2908 rtx_insn *head = BB_HEAD (bb);
2909 rtx_insn *end = BB_END (bb);
2911 for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
2913 /* Verify the end of the basic block is in the INSN chain. */
2917 /* And that the code outside of basic blocks has NULL bb field. */
2919 && BLOCK_FOR_INSN (x) != NULL)
2921 error ("insn %d outside of basic blocks has non-NULL bb field",
2929 error ("end insn %d for block %d not found in the insn stream",
2930 INSN_UID (end), bb->index);
2934 /* Work backwards from the end to the head of the basic block
2935 to verify the head is in the RTL chain. */
2936 for (; x != NULL_RTX; x = PREV_INSN (x))
2938 /* While walking over the insn chain, verify insns appear
2939 in only one basic block. */
2940 if (bb_info[INSN_UID (x)] != NULL)
2942 error ("insn %d is in multiple basic blocks (%d and %d)",
2943 INSN_UID (x), bb->index, bb_info[INSN_UID (x)]->index);
2947 bb_info[INSN_UID (x)] = bb;
2954 error ("head insn %d for block %d not found in the insn stream",
2955 INSN_UID (head), bb->index);
2959 last_head = PREV_INSN (x);
2962 for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
2964 /* Check that the code before the first basic block has NULL
2967 && BLOCK_FOR_INSN (x) != NULL)
2969 error ("insn %d outside of basic blocks has non-NULL bb field",
2979 /* Verify that fallthru edges point to adjacent blocks in layout order and
2980 that barriers exist after non-fallthru blocks. */
2983 rtl_verify_fallthru (void)
2988 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2992 e = find_fallthru_edge (bb->succs);
2997 /* Ensure existence of barrier in BB with no fallthru edges. */
2998 for (insn = NEXT_INSN (BB_END (bb)); ; insn = NEXT_INSN (insn))
3000 if (!insn || NOTE_INSN_BASIC_BLOCK_P (insn))
3002 error ("missing barrier after block %i", bb->index);
3006 if (BARRIER_P (insn))
3010 else if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
3011 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
3015 if (e->src->next_bb != e->dest)
3018 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
3019 e->src->index, e->dest->index);
3023 for (insn = NEXT_INSN (BB_END (e->src)); insn != BB_HEAD (e->dest);
3024 insn = NEXT_INSN (insn))
3025 if (BARRIER_P (insn) || NONDEBUG_INSN_P (insn))
3027 error ("verify_flow_info: Incorrect fallthru %i->%i",
3028 e->src->index, e->dest->index);
3029 error ("wrong insn in the fallthru edge");
3039 /* Verify that blocks are laid out in consecutive order. While walking the
3040 instructions, verify that all expected instructions are inside the basic
3041 blocks, and that all returns are followed by barriers. */
3044 rtl_verify_bb_layout (void)
3050 rtx_insn * const rtx_first = get_insns ();
3051 basic_block last_bb_seen = ENTRY_BLOCK_PTR_FOR_FN (cfun), curr_bb = NULL;
3055 for (x = rtx_first; x; x = NEXT_INSN (x))
3057 if (NOTE_INSN_BASIC_BLOCK_P (x))
3059 bb = NOTE_BASIC_BLOCK (x);
3062 if (bb != last_bb_seen->next_bb)
3063 internal_error ("basic blocks not laid down consecutively");
3065 curr_bb = last_bb_seen = bb;
3070 switch (GET_CODE (x))
3077 /* An ADDR_VEC is placed outside any basic block. */
3079 && JUMP_TABLE_DATA_P (NEXT_INSN (x)))
3082 /* But in any case, non-deletable labels can appear anywhere. */
3086 fatal_insn ("insn outside basic block", x);
3091 && returnjump_p (x) && ! condjump_p (x)
3092 && ! ((y = next_nonnote_nondebug_insn (x))
3094 fatal_insn ("return not followed by barrier", x);
3096 if (curr_bb && x == BB_END (curr_bb))
3100 if (num_bb_notes != n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS)
3102 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
3103 num_bb_notes, n_basic_blocks_for_fn (cfun));
3108 /* Verify the CFG and RTL consistency common for both underlying RTL and
3109 cfglayout RTL, plus consistency checks specific to linearized RTL mode.
3111 Currently it does following checks:
3112 - all checks of rtl_verify_flow_info_1
3113 - test head/end pointers
3114 - check that blocks are laid out in consecutive order
3115 - check that all insns are in the basic blocks
3116 (except the switch handling code, barriers and notes)
3117 - check that all returns are followed by barriers
3118 - check that all fallthru edge points to the adjacent blocks
3119 - verify that there is a single hot/cold partition boundary after bbro */
3122 rtl_verify_flow_info (void)
3126 err |= rtl_verify_flow_info_1 ();
3128 err |= rtl_verify_bb_insn_chain ();
3130 err |= rtl_verify_fallthru ();
3132 err |= rtl_verify_bb_layout ();
3134 err |= verify_hot_cold_block_grouping ();
3139 /* Assume that the preceding pass has possibly eliminated jump instructions
3140 or converted the unconditional jumps. Eliminate the edges from CFG.
3141 Return true if any edges are eliminated. */
3144 purge_dead_edges (basic_block bb)
3147 rtx_insn *insn = BB_END (bb);
3149 bool purged = false;
3153 if ((DEBUG_INSN_P (insn) || NOTE_P (insn)) && insn != BB_HEAD (bb))
3155 insn = PREV_INSN (insn);
3156 while ((DEBUG_INSN_P (insn) || NOTE_P (insn)) && insn != BB_HEAD (bb));
3158 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
3159 if (NONJUMP_INSN_P (insn)
3160 && (note = find_reg_note (insn, REG_EH_REGION, NULL)))
3164 if (! may_trap_p (PATTERN (insn))
3165 || ((eqnote = find_reg_equal_equiv_note (insn))
3166 && ! may_trap_p (XEXP (eqnote, 0))))
3167 remove_note (insn, note);
3170 /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
3171 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
3173 bool remove = false;
3175 /* There are three types of edges we need to handle correctly here: EH
3176 edges, abnormal call EH edges, and abnormal call non-EH edges. The
3177 latter can appear when nonlocal gotos are used. */
3178 if (e->flags & EDGE_ABNORMAL_CALL)
3182 else if (can_nonlocal_goto (insn))
3184 else if ((e->flags & EDGE_EH) && can_throw_internal (insn))
3186 else if (flag_tm && find_reg_note (insn, REG_TM, NULL))
3191 else if (e->flags & EDGE_EH)
3192 remove = !can_throw_internal (insn);
3197 df_set_bb_dirty (bb);
3210 /* We do care only about conditional jumps and simplejumps. */
3211 if (!any_condjump_p (insn)
3212 && !returnjump_p (insn)
3213 && !simplejump_p (insn))
3216 /* Branch probability/prediction notes are defined only for
3217 condjumps. We've possibly turned condjump into simplejump. */
3218 if (simplejump_p (insn))
3220 note = find_reg_note (insn, REG_BR_PROB, NULL);
3222 remove_note (insn, note);
3223 while ((note = find_reg_note (insn, REG_BR_PRED, NULL)))
3224 remove_note (insn, note);
3227 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
3229 /* Avoid abnormal flags to leak from computed jumps turned
3230 into simplejumps. */
3232 e->flags &= ~EDGE_ABNORMAL;
3234 /* See if this edge is one we should keep. */
3235 if ((e->flags & EDGE_FALLTHRU) && any_condjump_p (insn))
3236 /* A conditional jump can fall through into the next
3237 block, so we should keep the edge. */
3242 else if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
3243 && BB_HEAD (e->dest) == JUMP_LABEL (insn))
3244 /* If the destination block is the target of the jump,
3250 else if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
3251 && returnjump_p (insn))
3252 /* If the destination block is the exit block, and this
3253 instruction is a return, then keep the edge. */
3258 else if ((e->flags & EDGE_EH) && can_throw_internal (insn))
3259 /* Keep the edges that correspond to exceptions thrown by
3260 this instruction and rematerialize the EDGE_ABNORMAL
3261 flag we just cleared above. */
3263 e->flags |= EDGE_ABNORMAL;
3268 /* We do not need this edge. */
3269 df_set_bb_dirty (bb);
3274 if (EDGE_COUNT (bb->succs) == 0 || !purged)
3278 fprintf (dump_file, "Purged edges from bb %i\n", bb->index);
3283 /* Redistribute probabilities. */
3284 if (single_succ_p (bb))
3286 single_succ_edge (bb)->probability = profile_probability::always ();
3290 note = find_reg_note (insn, REG_BR_PROB, NULL);
3294 b = BRANCH_EDGE (bb);
3295 f = FALLTHRU_EDGE (bb);
3296 b->probability = profile_probability::from_reg_br_prob_note
3298 f->probability = b->probability.invert ();
3303 else if (CALL_P (insn) && SIBLING_CALL_P (insn))
3305 /* First, there should not be any EH or ABCALL edges resulting
3306 from non-local gotos and the like. If there were, we shouldn't
3307 have created the sibcall in the first place. Second, there
3308 should of course never have been a fallthru edge. */
3309 gcc_assert (single_succ_p (bb));
3310 gcc_assert (single_succ_edge (bb)->flags
3311 == (EDGE_SIBCALL | EDGE_ABNORMAL));
3316 /* If we don't see a jump insn, we don't know exactly why the block would
3317 have been broken at this point. Look for a simple, non-fallthru edge,
3318 as these are only created by conditional branches. If we find such an
3319 edge we know that there used to be a jump here and can then safely
3320 remove all non-fallthru edges. */
3322 FOR_EACH_EDGE (e, ei, bb->succs)
3323 if (! (e->flags & (EDGE_COMPLEX | EDGE_FALLTHRU)))
3332 /* Remove all but the fake and fallthru edges. The fake edge may be
3333 the only successor for this block in the case of noreturn
3335 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
3337 if (!(e->flags & (EDGE_FALLTHRU | EDGE_FAKE)))
3339 df_set_bb_dirty (bb);
3347 gcc_assert (single_succ_p (bb));
3349 single_succ_edge (bb)->probability = profile_probability::always ();
3352 fprintf (dump_file, "Purged non-fallthru edges from bb %i\n",
3357 /* Search all basic blocks for potentially dead edges and purge them. Return
3358 true if some edge has been eliminated. */
3361 purge_all_dead_edges (void)
3366 FOR_EACH_BB_FN (bb, cfun)
3368 bool purged_here = purge_dead_edges (bb);
3370 purged |= purged_here;
3376 /* This is used by a few passes that emit some instructions after abnormal
3377 calls, moving the basic block's end, while they in fact do want to emit
3378 them on the fallthru edge. Look for abnormal call edges, find backward
3379 the call in the block and insert the instructions on the edge instead.
3381 Similarly, handle instructions throwing exceptions internally.
3383 Return true when instructions have been found and inserted on edges. */
3386 fixup_abnormal_edges (void)
3388 bool inserted = false;
3391 FOR_EACH_BB_FN (bb, cfun)
3396 /* Look for cases we are interested in - calls or instructions causing
3398 FOR_EACH_EDGE (e, ei, bb->succs)
3399 if ((e->flags & EDGE_ABNORMAL_CALL)
3400 || ((e->flags & (EDGE_ABNORMAL | EDGE_EH))
3401 == (EDGE_ABNORMAL | EDGE_EH)))
3404 if (e && !CALL_P (BB_END (bb)) && !can_throw_internal (BB_END (bb)))
3408 /* Get past the new insns generated. Allow notes, as the insns
3409 may be already deleted. */
3411 while ((NONJUMP_INSN_P (insn) || NOTE_P (insn))
3412 && !can_throw_internal (insn)
3413 && insn != BB_HEAD (bb))
3414 insn = PREV_INSN (insn);
3416 if (CALL_P (insn) || can_throw_internal (insn))
3418 rtx_insn *stop, *next;
3420 e = find_fallthru_edge (bb->succs);
3422 stop = NEXT_INSN (BB_END (bb));
3425 for (insn = NEXT_INSN (insn); insn != stop; insn = next)
3427 next = NEXT_INSN (insn);
3432 /* Sometimes there's still the return value USE.
3433 If it's placed after a trapping call (i.e. that
3434 call is the last insn anyway), we have no fallthru
3435 edge. Simply delete this use and don't try to insert
3436 on the non-existent edge.
3437 Similarly, sometimes a call that can throw is
3438 followed in the source with __builtin_unreachable (),
3439 meaning that there is UB if the call returns rather
3440 than throws. If there weren't any instructions
3441 following such calls before, supposedly even the ones
3442 we've deleted aren't significant and can be
3446 /* We're not deleting it, we're moving it. */
3447 insn->set_undeleted ();
3448 SET_PREV_INSN (insn) = NULL_RTX;
3449 SET_NEXT_INSN (insn) = NULL_RTX;
3451 insert_insn_on_edge (insn, e);
3455 else if (!BARRIER_P (insn))
3456 set_block_for_insn (insn, NULL);
3460 /* It may be that we don't find any trapping insn. In this
3461 case we discovered quite late that the insn that had been
3462 marked as can_throw_internal in fact couldn't trap at all.
3463 So we should in fact delete the EH edges out of the block. */
3465 purge_dead_edges (bb);
3472 /* Delete the unconditional jump INSN and adjust the CFG correspondingly.
3473 Note that the INSN should be deleted *after* removing dead edges, so
3474 that the kept edge is the fallthrough edge for a (set (pc) (pc))
3475 but not for a (set (pc) (label_ref FOO)). */
3478 update_cfg_for_uncondjump (rtx_insn *insn)
3480 basic_block bb = BLOCK_FOR_INSN (insn);
3481 gcc_assert (BB_END (bb) == insn);
3483 purge_dead_edges (bb);
3485 if (current_ir_type () != IR_RTL_CFGLAYOUT)
3487 if (!find_fallthru_edge (bb->succs))
3489 auto barrier = next_nonnote_nondebug_insn (insn);
3490 if (!barrier || !BARRIER_P (barrier))
3491 emit_barrier_after (insn);
3497 if (EDGE_COUNT (bb->succs) == 1)
3501 single_succ_edge (bb)->flags |= EDGE_FALLTHRU;
3503 /* Remove barriers from the footer if there are any. */
3504 for (insn = BB_FOOTER (bb); insn; insn = NEXT_INSN (insn))
3505 if (BARRIER_P (insn))
3507 if (PREV_INSN (insn))
3508 SET_NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
3510 BB_FOOTER (bb) = NEXT_INSN (insn);
3511 if (NEXT_INSN (insn))
3512 SET_PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
3514 else if (LABEL_P (insn))
3519 /* Cut the insns from FIRST to LAST out of the insns stream. */
3522 unlink_insn_chain (rtx_insn *first, rtx_insn *last)
3524 rtx_insn *prevfirst = PREV_INSN (first);
3525 rtx_insn *nextlast = NEXT_INSN (last);
3527 SET_PREV_INSN (first) = NULL;
3528 SET_NEXT_INSN (last) = NULL;
3530 SET_NEXT_INSN (prevfirst) = nextlast;
3532 SET_PREV_INSN (nextlast) = prevfirst;
3534 set_last_insn (prevfirst);
3536 set_first_insn (nextlast);
3540 /* Skip over inter-block insns occurring after BB which are typically
3541 associated with BB (e.g., barriers). If there are any such insns,
3542 we return the last one. Otherwise, we return the end of BB. */
3545 skip_insns_after_block (basic_block bb)
3547 rtx_insn *insn, *last_insn, *next_head, *prev;
3550 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
3551 next_head = BB_HEAD (bb->next_bb);
3553 for (last_insn = insn = BB_END (bb); (insn = NEXT_INSN (insn)) != 0; )
3555 if (insn == next_head)
3558 switch (GET_CODE (insn))
3565 gcc_assert (NOTE_KIND (insn) != NOTE_INSN_BLOCK_END);
3569 if (NEXT_INSN (insn)
3570 && JUMP_TABLE_DATA_P (NEXT_INSN (insn)))
3572 insn = NEXT_INSN (insn);
3585 /* It is possible to hit contradictory sequence. For instance:
3591 Where barrier belongs to jump_insn, but the note does not. This can be
3592 created by removing the basic block originally following
3593 NOTE_INSN_BLOCK_BEG. In such case reorder the notes. */
3595 for (insn = last_insn; insn != BB_END (bb); insn = prev)
3597 prev = PREV_INSN (insn);
3599 switch (NOTE_KIND (insn))
3601 case NOTE_INSN_BLOCK_END:
3604 case NOTE_INSN_DELETED:
3605 case NOTE_INSN_DELETED_LABEL:
3606 case NOTE_INSN_DELETED_DEBUG_LABEL:
3609 reorder_insns (insn, insn, last_insn);
3616 /* Locate or create a label for a given basic block. */
3619 label_for_bb (basic_block bb)
3621 rtx_insn *label = BB_HEAD (bb);
3623 if (!LABEL_P (label))
3626 fprintf (dump_file, "Emitting label for block %d\n", bb->index);
3628 label = block_label (bb);
3634 /* Locate the effective beginning and end of the insn chain for each
3635 block, as defined by skip_insns_after_block above. */
3638 record_effective_endpoints (void)
3640 rtx_insn *next_insn;
3644 for (insn = get_insns ();
3647 && NOTE_KIND (insn) != NOTE_INSN_BASIC_BLOCK;
3648 insn = NEXT_INSN (insn))
3650 /* No basic blocks at all? */
3653 if (PREV_INSN (insn))
3654 cfg_layout_function_header =
3655 unlink_insn_chain (get_insns (), PREV_INSN (insn));
3657 cfg_layout_function_header = NULL;
3659 next_insn = get_insns ();
3660 FOR_EACH_BB_FN (bb, cfun)
3664 if (PREV_INSN (BB_HEAD (bb)) && next_insn != BB_HEAD (bb))
3665 BB_HEADER (bb) = unlink_insn_chain (next_insn,
3666 PREV_INSN (BB_HEAD (bb)));
3667 end = skip_insns_after_block (bb);
3668 if (NEXT_INSN (BB_END (bb)) && BB_END (bb) != end)
3669 BB_FOOTER (bb) = unlink_insn_chain (NEXT_INSN (BB_END (bb)), end);
3670 next_insn = NEXT_INSN (BB_END (bb));
3673 cfg_layout_function_footer = next_insn;
3674 if (cfg_layout_function_footer)
3675 cfg_layout_function_footer = unlink_insn_chain (cfg_layout_function_footer, get_last_insn ());
3680 const pass_data pass_data_into_cfg_layout_mode =
3682 RTL_PASS, /* type */
3683 "into_cfglayout", /* name */
3684 OPTGROUP_NONE, /* optinfo_flags */
3686 0, /* properties_required */
3687 PROP_cfglayout, /* properties_provided */
3688 0, /* properties_destroyed */
3689 0, /* todo_flags_start */
3690 0, /* todo_flags_finish */
3693 class pass_into_cfg_layout_mode : public rtl_opt_pass
3696 pass_into_cfg_layout_mode (gcc::context *ctxt)
3697 : rtl_opt_pass (pass_data_into_cfg_layout_mode, ctxt)
3700 /* opt_pass methods: */
3701 unsigned int execute (function *) final override
3703 cfg_layout_initialize (0);
3707 }; // class pass_into_cfg_layout_mode
3712 make_pass_into_cfg_layout_mode (gcc::context *ctxt)
3714 return new pass_into_cfg_layout_mode (ctxt);
3719 const pass_data pass_data_outof_cfg_layout_mode =
3721 RTL_PASS, /* type */
3722 "outof_cfglayout", /* name */
3723 OPTGROUP_NONE, /* optinfo_flags */
3725 0, /* properties_required */
3726 0, /* properties_provided */
3727 PROP_cfglayout, /* properties_destroyed */
3728 0, /* todo_flags_start */
3729 0, /* todo_flags_finish */
3732 class pass_outof_cfg_layout_mode : public rtl_opt_pass
3735 pass_outof_cfg_layout_mode (gcc::context *ctxt)
3736 : rtl_opt_pass (pass_data_outof_cfg_layout_mode, ctxt)
3739 /* opt_pass methods: */
3740 unsigned int execute (function *) final override;
3742 }; // class pass_outof_cfg_layout_mode
3745 pass_outof_cfg_layout_mode::execute (function *fun)
3749 FOR_EACH_BB_FN (bb, fun)
3750 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (fun))
3751 bb->aux = bb->next_bb;
3753 cfg_layout_finalize ();
3761 make_pass_outof_cfg_layout_mode (gcc::context *ctxt)
3763 return new pass_outof_cfg_layout_mode (ctxt);
3767 /* Link the basic blocks in the correct order, compacting the basic
3768 block queue while at it. If STAY_IN_CFGLAYOUT_MODE is false, this
3769 function also clears the basic block header and footer fields.
3771 This function is usually called after a pass (e.g. tracer) finishes
3772 some transformations while in cfglayout mode. The required sequence
3773 of the basic blocks is in a linked list along the bb->aux field.
3774 This functions re-links the basic block prev_bb and next_bb pointers
3775 accordingly, and it compacts and renumbers the blocks.
3777 FIXME: This currently works only for RTL, but the only RTL-specific
3778 bits are the STAY_IN_CFGLAYOUT_MODE bits. The tracer pass was moved
3779 to GIMPLE a long time ago, but it doesn't relink the basic block
3780 chain. It could do that (to give better initial RTL) if this function
3781 is made IR-agnostic (and moved to cfganal.cc or cfg.cc while at it). */
3784 relink_block_chain (bool stay_in_cfglayout_mode)
3786 basic_block bb, prev_bb;
3789 /* Maybe dump the re-ordered sequence. */
3792 fprintf (dump_file, "Reordered sequence:\n");
3793 for (bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb, index =
3796 bb = (basic_block) bb->aux, index++)
3798 fprintf (dump_file, " %i ", index);
3799 if (get_bb_original (bb))
3800 fprintf (dump_file, "duplicate of %i\n",
3801 get_bb_original (bb)->index);
3802 else if (forwarder_block_p (bb)
3803 && !LABEL_P (BB_HEAD (bb)))
3804 fprintf (dump_file, "compensation\n");
3806 fprintf (dump_file, "bb %i\n", bb->index);
3810 /* Now reorder the blocks. */
3811 prev_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
3812 bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb;
3813 for (; bb; prev_bb = bb, bb = (basic_block) bb->aux)
3815 bb->prev_bb = prev_bb;
3816 prev_bb->next_bb = bb;
3818 prev_bb->next_bb = EXIT_BLOCK_PTR_FOR_FN (cfun);
3819 EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb = prev_bb;
3821 /* Then, clean up the aux fields. */
3822 FOR_ALL_BB_FN (bb, cfun)
3825 if (!stay_in_cfglayout_mode)
3826 BB_HEADER (bb) = BB_FOOTER (bb) = NULL;
3829 /* Maybe reset the original copy tables, they are not valid anymore
3830 when we renumber the basic blocks in compact_blocks. If we are
3831 are going out of cfglayout mode, don't re-allocate the tables. */
3832 if (original_copy_tables_initialized_p ())
3833 free_original_copy_tables ();
3834 if (stay_in_cfglayout_mode)
3835 initialize_original_copy_tables ();
3837 /* Finally, put basic_block_info in the new order. */
3842 /* Given a reorder chain, rearrange the code to match. */
3845 fixup_reorder_chain (void)
3848 rtx_insn *insn = NULL;
3850 if (cfg_layout_function_header)
3852 set_first_insn (cfg_layout_function_header);
3853 insn = cfg_layout_function_header;
3854 while (NEXT_INSN (insn))
3855 insn = NEXT_INSN (insn);
3858 /* First do the bulk reordering -- rechain the blocks without regard to
3859 the needed changes to jumps and labels. */
3861 for (bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; bb; bb = (basic_block)
3867 SET_NEXT_INSN (insn) = BB_HEADER (bb);
3869 set_first_insn (BB_HEADER (bb));
3870 SET_PREV_INSN (BB_HEADER (bb)) = insn;
3871 insn = BB_HEADER (bb);
3872 while (NEXT_INSN (insn))
3873 insn = NEXT_INSN (insn);
3876 SET_NEXT_INSN (insn) = BB_HEAD (bb);
3878 set_first_insn (BB_HEAD (bb));
3879 SET_PREV_INSN (BB_HEAD (bb)) = insn;
3883 SET_NEXT_INSN (insn) = BB_FOOTER (bb);
3884 SET_PREV_INSN (BB_FOOTER (bb)) = insn;
3885 while (NEXT_INSN (insn))
3886 insn = NEXT_INSN (insn);
3890 SET_NEXT_INSN (insn) = cfg_layout_function_footer;
3891 if (cfg_layout_function_footer)
3892 SET_PREV_INSN (cfg_layout_function_footer) = insn;
3894 while (NEXT_INSN (insn))
3895 insn = NEXT_INSN (insn);
3897 set_last_insn (insn);
3899 verify_insn_chain ();
3901 /* Now add jumps and labels as needed to match the blocks new
3904 bool remove_unreachable_blocks = false;
3905 for (bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; bb ; bb = (basic_block)
3908 edge e_fall, e_taken, e;
3909 rtx_insn *bb_end_insn;
3910 rtx ret_label = NULL_RTX;
3914 if (EDGE_COUNT (bb->succs) == 0)
3917 /* Find the old fallthru edge, and another non-EH edge for
3919 e_taken = e_fall = NULL;
3921 FOR_EACH_EDGE (e, ei, bb->succs)
3922 if (e->flags & EDGE_FALLTHRU)
3924 else if (! (e->flags & EDGE_EH))
3927 bb_end_insn = BB_END (bb);
3928 if (rtx_jump_insn *bb_end_jump = dyn_cast <rtx_jump_insn *> (bb_end_insn))
3930 ret_label = JUMP_LABEL (bb_end_jump);
3931 if (any_condjump_p (bb_end_jump))
3933 /* This might happen if the conditional jump has side
3934 effects and could therefore not be optimized away.
3935 Make the basic block to end with a barrier in order
3936 to prevent rtl_verify_flow_info from complaining. */
3939 gcc_assert (!onlyjump_p (bb_end_jump)
3940 || returnjump_p (bb_end_jump)
3941 || (e_taken->flags & EDGE_CROSSING));
3942 emit_barrier_after (bb_end_jump);
3946 /* If the old fallthru is still next, nothing to do. */
3947 if (bb->aux == e_fall->dest
3948 || e_fall->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
3951 /* The degenerated case of conditional jump jumping to the next
3952 instruction can happen for jumps with side effects. We need
3953 to construct a forwarder block and this will be done just
3954 fine by force_nonfallthru below. */
3958 /* There is another special case: if *neither* block is next,
3959 such as happens at the very end of a function, then we'll
3960 need to add a new unconditional jump. Choose the taken
3961 edge based on known or assumed probability. */
3962 else if (bb->aux != e_taken->dest)
3964 rtx note = find_reg_note (bb_end_jump, REG_BR_PROB, 0);
3967 && profile_probability::from_reg_br_prob_note
3968 (XINT (note, 0)) < profile_probability::even ()
3969 && invert_jump (bb_end_jump,
3971 == EXIT_BLOCK_PTR_FOR_FN (cfun)
3973 : label_for_bb (e_fall->dest)), 0))
3975 e_fall->flags &= ~EDGE_FALLTHRU;
3976 gcc_checking_assert (could_fall_through
3977 (e_taken->src, e_taken->dest));
3978 e_taken->flags |= EDGE_FALLTHRU;
3979 update_br_prob_note (bb);
3980 e = e_fall, e_fall = e_taken, e_taken = e;
3984 /* If the "jumping" edge is a crossing edge, and the fall
3985 through edge is non-crossing, leave things as they are. */
3986 else if ((e_taken->flags & EDGE_CROSSING)
3987 && !(e_fall->flags & EDGE_CROSSING))
3990 /* Otherwise we can try to invert the jump. This will
3991 basically never fail, however, keep up the pretense. */
3992 else if (invert_jump (bb_end_jump,
3994 == EXIT_BLOCK_PTR_FOR_FN (cfun)
3996 : label_for_bb (e_fall->dest)), 0))
3998 e_fall->flags &= ~EDGE_FALLTHRU;
3999 gcc_checking_assert (could_fall_through
4000 (e_taken->src, e_taken->dest));
4001 e_taken->flags |= EDGE_FALLTHRU;
4002 update_br_prob_note (bb);
4003 if (LABEL_NUSES (ret_label) == 0
4004 && single_pred_p (e_taken->dest))
4005 delete_insn (as_a<rtx_insn *> (ret_label));
4009 else if (extract_asm_operands (PATTERN (bb_end_insn)) != NULL)
4011 /* If the old fallthru is still next or if
4012 asm goto doesn't have a fallthru (e.g. when followed by
4013 __builtin_unreachable ()), nothing to do. */
4015 || bb->aux == e_fall->dest
4016 || e_fall->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
4019 /* Otherwise we'll have to use the fallthru fixup below. */
4023 /* Otherwise we have some return, switch or computed
4024 jump. In the 99% case, there should not have been a
4026 gcc_assert (returnjump_p (bb_end_insn) || !e_fall);
4032 /* No fallthru implies a noreturn function with EH edges, or
4033 something similarly bizarre. In any case, we don't need to
4038 /* If the fallthru block is still next, nothing to do. */
4039 if (bb->aux == e_fall->dest)
4042 /* A fallthru to exit block. */
4043 if (e_fall->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
4047 /* If E_FALL->dest is just a return block, then we can emit a
4048 return rather than a jump to the return block. */
4049 rtx_insn *ret, *use;
4051 if (bb_is_just_return (e_fall->dest, &ret, &use)
4052 && ((PATTERN (ret) == simple_return_rtx && targetm.have_simple_return ())
4053 || (PATTERN (ret) == ret_rtx && targetm.have_return ())))
4055 ret_label = PATTERN (ret);
4056 dest = EXIT_BLOCK_PTR_FOR_FN (cfun);
4058 e_fall->flags &= ~EDGE_CROSSING;
4059 /* E_FALL->dest might become unreachable as a result of
4060 replacing the jump with a return. So arrange to remove
4061 unreachable blocks. */
4062 remove_unreachable_blocks = true;
4066 dest = e_fall->dest;
4069 /* We got here if we need to add a new jump insn.
4070 Note force_nonfallthru can delete E_FALL and thus we have to
4071 save E_FALL->src prior to the call to force_nonfallthru. */
4072 nb = force_nonfallthru_and_redirect (e_fall, dest, ret_label);
4077 /* Don't process this new block. */
4082 relink_block_chain (/*stay_in_cfglayout_mode=*/false);
4084 /* Annoying special case - jump around dead jumptables left in the code. */
4085 FOR_EACH_BB_FN (bb, cfun)
4087 edge e = find_fallthru_edge (bb->succs);
4089 if (e && !can_fallthru (e->src, e->dest))
4090 force_nonfallthru (e);
4093 /* Ensure goto_locus from edges has some instructions with that locus in RTL
4094 when not optimizing. */
4095 if (!optimize && !DECL_IGNORED_P (current_function_decl))
4096 FOR_EACH_BB_FN (bb, cfun)
4101 FOR_EACH_EDGE (e, ei, bb->succs)
4102 if (LOCATION_LOCUS (e->goto_locus) != UNKNOWN_LOCATION
4103 && !(e->flags & EDGE_ABNORMAL))
4107 basic_block dest, nb;
4110 insn = BB_END (e->src);
4111 end = PREV_INSN (BB_HEAD (e->src));
4113 && (!NONDEBUG_INSN_P (insn) || !INSN_HAS_LOCATION (insn)))
4114 insn = PREV_INSN (insn);
4116 && loc_equal (INSN_LOCATION (insn), e->goto_locus))
4118 if (simplejump_p (BB_END (e->src))
4119 && !INSN_HAS_LOCATION (BB_END (e->src)))
4121 INSN_LOCATION (BB_END (e->src)) = e->goto_locus;
4125 if (dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
4127 /* Non-fallthru edges to the exit block cannot be split. */
4128 if (!(e->flags & EDGE_FALLTHRU))
4133 insn = BB_HEAD (dest);
4134 end = NEXT_INSN (BB_END (dest));
4135 while (insn != end && !NONDEBUG_INSN_P (insn))
4136 insn = NEXT_INSN (insn);
4137 if (insn != end && INSN_HAS_LOCATION (insn)
4138 && loc_equal (INSN_LOCATION (insn), e->goto_locus))
4141 nb = split_edge (e);
4142 if (!INSN_P (BB_END (nb)))
4143 BB_END (nb) = emit_insn_after_noloc (gen_nop (), BB_END (nb),
4145 INSN_LOCATION (BB_END (nb)) = e->goto_locus;
4147 /* If there are other incoming edges to the destination block
4148 with the same goto locus, redirect them to the new block as
4149 well, this can prevent other such blocks from being created
4150 in subsequent iterations of the loop. */
4151 for (ei2 = ei_start (dest->preds); (e2 = ei_safe_edge (ei2)); )
4152 if (LOCATION_LOCUS (e2->goto_locus) != UNKNOWN_LOCATION
4153 && !(e2->flags & (EDGE_ABNORMAL | EDGE_FALLTHRU))
4154 && e->goto_locus == e2->goto_locus)
4155 redirect_edge_and_branch (e2, nb);
4161 /* Replacing a jump with a return may have exposed an unreachable
4162 block. Conditionally remove them if such transformations were
4164 if (remove_unreachable_blocks)
4165 delete_unreachable_blocks ();
4168 /* Perform sanity checks on the insn chain.
4169 1. Check that next/prev pointers are consistent in both the forward and
4171 2. Count insns in chain, going both directions, and check if equal.
4172 3. Check that get_last_insn () returns the actual end of chain. */
4175 verify_insn_chain (void)
4177 rtx_insn *x, *prevx, *nextx;
4178 int insn_cnt1, insn_cnt2;
4180 for (prevx = NULL, insn_cnt1 = 1, x = get_insns ();
4182 prevx = x, insn_cnt1++, x = NEXT_INSN (x))
4183 gcc_assert (PREV_INSN (x) == prevx);
4185 gcc_assert (prevx == get_last_insn ());
4187 for (nextx = NULL, insn_cnt2 = 1, x = get_last_insn ();
4189 nextx = x, insn_cnt2++, x = PREV_INSN (x))
4190 gcc_assert (NEXT_INSN (x) == nextx);
4192 gcc_assert (insn_cnt1 == insn_cnt2);
4195 /* If we have assembler epilogues, the block falling through to exit must
4196 be the last one in the reordered chain when we reach final. Ensure
4197 that this condition is met. */
4199 fixup_fallthru_exit_predecessor (void)
4202 basic_block bb = NULL;
4204 /* This transformation is not valid before reload, because we might
4205 separate a call from the instruction that copies the return
4207 gcc_assert (reload_completed);
4209 e = find_fallthru_edge (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds);
4215 basic_block c = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb;
4217 /* If the very first block is the one with the fall-through exit
4218 edge, we have to split that block. */
4221 bb = split_block_after_labels (bb)->dest;
4224 BB_FOOTER (bb) = BB_FOOTER (c);
4225 BB_FOOTER (c) = NULL;
4228 while (c->aux != bb)
4229 c = (basic_block) c->aux;
4233 c = (basic_block) c->aux;
4240 /* In case there are more than one fallthru predecessors of exit, force that
4241 there is only one. */
4244 force_one_exit_fallthru (void)
4246 edge e, predecessor = NULL;
4249 basic_block forwarder, bb;
4251 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
4252 if (e->flags & EDGE_FALLTHRU)
4254 if (predecessor == NULL)
4266 /* Exit has several fallthru predecessors. Create a forwarder block for
4268 forwarder = split_edge (predecessor);
4269 for (ei = ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds);
4270 (e = ei_safe_edge (ei)); )
4272 if (e->src == forwarder
4273 || !(e->flags & EDGE_FALLTHRU))
4276 redirect_edge_and_branch_force (e, forwarder);
4279 /* Fix up the chain of blocks -- make FORWARDER immediately precede the
4281 FOR_EACH_BB_FN (bb, cfun)
4283 if (bb->aux == NULL && bb != forwarder)
4285 bb->aux = forwarder;
4291 /* Return true in case it is possible to duplicate the basic block BB. */
4294 cfg_layout_can_duplicate_bb_p (const_basic_block bb)
4296 /* Do not attempt to duplicate tablejumps, as we need to unshare
4297 the dispatch table. This is difficult to do, as the instructions
4298 computing jump destination may be hoisted outside the basic block. */
4299 if (tablejump_p (BB_END (bb), NULL, NULL))
4302 /* Do not duplicate blocks containing insns that can't be copied. */
4303 if (targetm.cannot_copy_insn_p)
4305 rtx_insn *insn = BB_HEAD (bb);
4308 if (INSN_P (insn) && targetm.cannot_copy_insn_p (insn))
4310 if (insn == BB_END (bb))
4312 insn = NEXT_INSN (insn);
4320 duplicate_insn_chain (rtx_insn *from, rtx_insn *to,
4321 class loop *loop, copy_bb_data *id)
4323 rtx_insn *insn, *next, *copy;
4326 /* Avoid updating of boundaries of previous basic block. The
4327 note will get removed from insn stream in fixup. */
4328 last = emit_note (NOTE_INSN_DELETED);
4330 /* Create copy at the end of INSN chain. The chain will
4331 be reordered later. */
4332 for (insn = from; insn != NEXT_INSN (to); insn = NEXT_INSN (insn))
4334 switch (GET_CODE (insn))
4337 /* Don't duplicate label debug insns. */
4338 if (DEBUG_BIND_INSN_P (insn)
4339 && TREE_CODE (INSN_VAR_LOCATION_DECL (insn)) == LABEL_DECL)
4345 copy = emit_copy_of_insn_after (insn, get_last_insn ());
4346 if (JUMP_P (insn) && JUMP_LABEL (insn) != NULL_RTX
4347 && ANY_RETURN_P (JUMP_LABEL (insn)))
4348 JUMP_LABEL (copy) = JUMP_LABEL (insn);
4349 maybe_copy_prologue_epilogue_insn (insn, copy);
4350 /* If requested remap dependence info of cliques brought in
4354 subrtx_iterator::array_type array;
4355 FOR_EACH_SUBRTX (iter, array, PATTERN (insn), ALL)
4356 if (MEM_P (*iter) && MEM_EXPR (*iter))
4358 tree op = MEM_EXPR (*iter);
4359 if (TREE_CODE (op) == WITH_SIZE_EXPR)
4360 op = TREE_OPERAND (op, 0);
4361 while (handled_component_p (op))
4362 op = TREE_OPERAND (op, 0);
4363 if ((TREE_CODE (op) == MEM_REF
4364 || TREE_CODE (op) == TARGET_MEM_REF)
4365 && MR_DEPENDENCE_CLIQUE (op) > 1
4367 || (MR_DEPENDENCE_CLIQUE (op)
4368 != loop->owned_clique)))
4370 if (!id->dependence_map)
4371 id->dependence_map = new hash_map<dependence_hash,
4374 unsigned short &newc = id->dependence_map->get_or_insert
4375 (MR_DEPENDENCE_CLIQUE (op), &existed);
4379 (MR_DEPENDENCE_CLIQUE (op) <= cfun->last_clique);
4380 newc = ++cfun->last_clique;
4382 /* We cannot adjust MR_DEPENDENCE_CLIQUE in-place
4383 since MEM_EXPR is shared so make a copy and
4384 walk to the subtree again. */
4385 tree new_expr = unshare_expr (MEM_EXPR (*iter));
4386 if (TREE_CODE (new_expr) == WITH_SIZE_EXPR)
4387 new_expr = TREE_OPERAND (new_expr, 0);
4388 while (handled_component_p (new_expr))
4389 new_expr = TREE_OPERAND (new_expr, 0);
4390 MR_DEPENDENCE_CLIQUE (new_expr) = newc;
4391 set_mem_expr (const_cast <rtx> (*iter), new_expr);
4397 case JUMP_TABLE_DATA:
4398 /* Avoid copying of dispatch tables. We never duplicate
4399 tablejumps, so this can hit only in case the table got
4400 moved far from original jump.
4401 Avoid copying following barrier as well if any
4402 (and debug insns in between). */
4403 for (next = NEXT_INSN (insn);
4404 next != NEXT_INSN (to);
4405 next = NEXT_INSN (next))
4406 if (!DEBUG_INSN_P (next))
4408 if (next != NEXT_INSN (to) && BARRIER_P (next))
4420 switch (NOTE_KIND (insn))
4422 /* In case prologue is empty and function contain label
4423 in first BB, we may want to copy the block. */
4424 case NOTE_INSN_PROLOGUE_END:
4426 case NOTE_INSN_DELETED:
4427 case NOTE_INSN_DELETED_LABEL:
4428 case NOTE_INSN_DELETED_DEBUG_LABEL:
4429 /* No problem to strip these. */
4430 case NOTE_INSN_FUNCTION_BEG:
4431 /* There is always just single entry to function. */
4432 case NOTE_INSN_BASIC_BLOCK:
4433 /* We should only switch text sections once. */
4434 case NOTE_INSN_SWITCH_TEXT_SECTIONS:
4437 case NOTE_INSN_EPILOGUE_BEG:
4438 case NOTE_INSN_UPDATE_SJLJ_CONTEXT:
4439 emit_note_copy (as_a <rtx_note *> (insn));
4443 /* All other notes should have already been eliminated. */
4451 insn = NEXT_INSN (last);
4456 /* Create a duplicate of the basic block BB. */
4459 cfg_layout_duplicate_bb (basic_block bb, copy_bb_data *id)
4464 class loop *loop = (id && current_loops) ? bb->loop_father : NULL;
4466 insn = duplicate_insn_chain (BB_HEAD (bb), BB_END (bb), loop, id);
4467 new_bb = create_basic_block (insn,
4468 insn ? get_last_insn () : NULL,
4469 EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb);
4471 BB_COPY_PARTITION (new_bb, bb);
4474 insn = BB_HEADER (bb);
4475 while (NEXT_INSN (insn))
4476 insn = NEXT_INSN (insn);
4477 insn = duplicate_insn_chain (BB_HEADER (bb), insn, loop, id);
4479 BB_HEADER (new_bb) = unlink_insn_chain (insn, get_last_insn ());
4484 insn = BB_FOOTER (bb);
4485 while (NEXT_INSN (insn))
4486 insn = NEXT_INSN (insn);
4487 insn = duplicate_insn_chain (BB_FOOTER (bb), insn, loop, id);
4489 BB_FOOTER (new_bb) = unlink_insn_chain (insn, get_last_insn ());
4496 /* Main entry point to this module - initialize the datastructures for
4497 CFG layout changes. It keeps LOOPS up-to-date if not null.
4499 FLAGS is a set of additional flags to pass to cleanup_cfg(). */
4502 cfg_layout_initialize (int flags)
4507 /* Once bb partitioning is complete, cfg layout mode should not be
4508 re-entered. Entering cfg layout mode may require fixups. As an
4509 example, if edge forwarding performed when optimizing the cfg
4510 layout required moving a block from the hot to the cold
4511 section. This would create an illegal partitioning unless some
4512 manual fixup was performed. */
4513 gcc_assert (!crtl->bb_reorder_complete || !crtl->has_bb_partition);
4515 initialize_original_copy_tables ();
4517 cfg_layout_rtl_register_cfg_hooks ();
4519 record_effective_endpoints ();
4521 /* Make sure that the targets of non local gotos are marked. */
4522 for (x = nonlocal_goto_handler_labels; x; x = x->next ())
4524 bb = BLOCK_FOR_INSN (x->insn ());
4525 bb->flags |= BB_NON_LOCAL_GOTO_TARGET;
4528 cleanup_cfg (CLEANUP_CFGLAYOUT | flags);
4531 /* Splits superblocks. */
4533 break_superblocks (void)
4538 auto_sbitmap superblocks (last_basic_block_for_fn (cfun));
4539 bitmap_clear (superblocks);
4541 FOR_EACH_BB_FN (bb, cfun)
4542 if (bb->flags & BB_SUPERBLOCK)
4544 bb->flags &= ~BB_SUPERBLOCK;
4545 bitmap_set_bit (superblocks, bb->index);
4551 rebuild_jump_labels (get_insns ());
4552 find_many_sub_basic_blocks (superblocks);
4556 /* Finalize the changes: reorder insn list according to the sequence specified
4557 by aux pointers, enter compensation code, rebuild scope forest. */
4560 cfg_layout_finalize (void)
4562 free_dominance_info (CDI_DOMINATORS);
4563 force_one_exit_fallthru ();
4564 rtl_register_cfg_hooks ();
4565 if (reload_completed && !targetm.have_epilogue ())
4566 fixup_fallthru_exit_predecessor ();
4567 fixup_reorder_chain ();
4569 rebuild_jump_labels (get_insns ());
4570 delete_dead_jumptables ();
4573 verify_insn_chain ();
4574 checking_verify_flow_info ();
4578 /* Same as split_block but update cfg_layout structures. */
4581 cfg_layout_split_block (basic_block bb, void *insnp)
4583 rtx insn = (rtx) insnp;
4584 basic_block new_bb = rtl_split_block (bb, insn);
4586 BB_FOOTER (new_bb) = BB_FOOTER (bb);
4587 BB_FOOTER (bb) = NULL;
4592 /* Redirect Edge to DEST. */
4594 cfg_layout_redirect_edge_and_branch (edge e, basic_block dest)
4596 basic_block src = e->src;
4599 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
4602 if (e->dest == dest)
4605 if (e->flags & EDGE_CROSSING
4606 && BB_PARTITION (e->src) == BB_PARTITION (dest)
4607 && simplejump_p (BB_END (src)))
4611 "Removing crossing jump while redirecting edge form %i to %i\n",
4612 e->src->index, dest->index);
4613 delete_insn (BB_END (src));
4614 remove_barriers_from_footer (src);
4615 e->flags |= EDGE_FALLTHRU;
4618 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
4619 && (ret = try_redirect_by_replacing_jump (e, dest, true)))
4621 df_set_bb_dirty (src);
4625 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)
4626 && (e->flags & EDGE_FALLTHRU) && !(e->flags & EDGE_COMPLEX))
4629 fprintf (dump_file, "Redirecting entry edge from bb %i to %i\n",
4630 e->src->index, dest->index);
4632 df_set_bb_dirty (e->src);
4633 redirect_edge_succ (e, dest);
4637 /* Redirect_edge_and_branch may decide to turn branch into fallthru edge
4638 in the case the basic block appears to be in sequence. Avoid this
4641 if (e->flags & EDGE_FALLTHRU)
4643 /* Redirect any branch edges unified with the fallthru one. */
4644 if (JUMP_P (BB_END (src))
4645 && label_is_jump_target_p (BB_HEAD (e->dest),
4651 fprintf (dump_file, "Fallthru edge unified with branch "
4652 "%i->%i redirected to %i\n",
4653 e->src->index, e->dest->index, dest->index);
4654 e->flags &= ~EDGE_FALLTHRU;
4655 redirected = redirect_branch_edge (e, dest);
4656 gcc_assert (redirected);
4657 redirected->flags |= EDGE_FALLTHRU;
4658 df_set_bb_dirty (redirected->src);
4661 /* In case we are redirecting fallthru edge to the branch edge
4662 of conditional jump, remove it. */
4663 if (EDGE_COUNT (src->succs) == 2)
4665 /* Find the edge that is different from E. */
4666 edge s = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e);
4669 && any_condjump_p (BB_END (src))
4670 && onlyjump_p (BB_END (src)))
4671 delete_insn (BB_END (src));
4674 fprintf (dump_file, "Redirecting fallthru edge %i->%i to %i\n",
4675 e->src->index, e->dest->index, dest->index);
4676 ret = redirect_edge_succ_nodup (e, dest);
4679 ret = redirect_branch_edge (e, dest);
4684 fixup_partition_crossing (ret);
4685 /* We don't want simplejumps in the insn stream during cfglayout. */
4686 gcc_assert (!simplejump_p (BB_END (src)) || CROSSING_JUMP_P (BB_END (src)));
4688 df_set_bb_dirty (src);
4692 /* Simple wrapper as we always can redirect fallthru edges. */
4694 cfg_layout_redirect_edge_and_branch_force (edge e, basic_block dest)
4696 edge redirected = cfg_layout_redirect_edge_and_branch (e, dest);
4698 gcc_assert (redirected);
4702 /* Same as delete_basic_block but update cfg_layout structures. */
4705 cfg_layout_delete_block (basic_block bb)
4707 rtx_insn *insn, *next, *prev = PREV_INSN (BB_HEAD (bb)), *remaints;
4712 next = BB_HEAD (bb);
4714 SET_NEXT_INSN (prev) = BB_HEADER (bb);
4716 set_first_insn (BB_HEADER (bb));
4717 SET_PREV_INSN (BB_HEADER (bb)) = prev;
4718 insn = BB_HEADER (bb);
4719 while (NEXT_INSN (insn))
4720 insn = NEXT_INSN (insn);
4721 SET_NEXT_INSN (insn) = next;
4722 SET_PREV_INSN (next) = insn;
4724 next = NEXT_INSN (BB_END (bb));
4727 insn = BB_FOOTER (bb);
4730 if (BARRIER_P (insn))
4732 if (PREV_INSN (insn))
4733 SET_NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
4735 BB_FOOTER (bb) = NEXT_INSN (insn);
4736 if (NEXT_INSN (insn))
4737 SET_PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
4741 insn = NEXT_INSN (insn);
4746 SET_NEXT_INSN (insn) = BB_FOOTER (bb);
4747 SET_PREV_INSN (BB_FOOTER (bb)) = insn;
4748 while (NEXT_INSN (insn))
4749 insn = NEXT_INSN (insn);
4750 SET_NEXT_INSN (insn) = next;
4752 SET_PREV_INSN (next) = insn;
4754 set_last_insn (insn);
4757 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4758 to = &BB_HEADER (bb->next_bb);
4760 to = &cfg_layout_function_footer;
4762 rtl_delete_block (bb);
4765 prev = NEXT_INSN (prev);
4767 prev = get_insns ();
4769 next = PREV_INSN (next);
4771 next = get_last_insn ();
4773 if (next && NEXT_INSN (next) != prev)
4775 remaints = unlink_insn_chain (prev, next);
4777 while (NEXT_INSN (insn))
4778 insn = NEXT_INSN (insn);
4779 SET_NEXT_INSN (insn) = *to;
4781 SET_PREV_INSN (*to) = insn;
4786 /* Return true when blocks A and B can be safely merged. */
4789 cfg_layout_can_merge_blocks_p (basic_block a, basic_block b)
4791 /* If we are partitioning hot/cold basic blocks, we don't want to
4792 mess up unconditional or indirect jumps that cross between hot
4795 Basic block partitioning may result in some jumps that appear to
4796 be optimizable (or blocks that appear to be mergeable), but which really
4797 must be left untouched (they are required to make it safely across
4798 partition boundaries). See the comments at the top of
4799 bb-reorder.cc:partition_hot_cold_basic_blocks for complete details. */
4801 if (BB_PARTITION (a) != BB_PARTITION (b))
4804 /* Protect the loop latches. */
4805 if (current_loops && b->loop_father->latch == b)
4808 /* If we would end up moving B's instructions, make sure it doesn't fall
4809 through into the exit block, since we cannot recover from a fallthrough
4810 edge into the exit block occurring in the middle of a function. */
4811 if (NEXT_INSN (BB_END (a)) != BB_HEAD (b))
4813 edge e = find_fallthru_edge (b->succs);
4814 if (e && e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
4818 /* There must be exactly one edge in between the blocks. */
4819 return (single_succ_p (a)
4820 && single_succ (a) == b
4821 && single_pred_p (b) == 1
4823 /* Must be simple edge. */
4824 && !(single_succ_edge (a)->flags & EDGE_COMPLEX)
4825 && a != ENTRY_BLOCK_PTR_FOR_FN (cfun)
4826 && b != EXIT_BLOCK_PTR_FOR_FN (cfun)
4827 /* If the jump insn has side effects, we can't kill the edge.
4828 When not optimizing, try_redirect_by_replacing_jump will
4829 not allow us to redirect an edge by replacing a table jump. */
4830 && (!JUMP_P (BB_END (a))
4831 || ((!optimize || reload_completed)
4832 ? simplejump_p (BB_END (a)) : onlyjump_p (BB_END (a)))));
4835 /* Merge block A and B. The blocks must be mergeable. */
4838 cfg_layout_merge_blocks (basic_block a, basic_block b)
4840 /* If B is a forwarder block whose outgoing edge has no location, we'll
4841 propagate the locus of the edge between A and B onto it. */
4842 const bool forward_edge_locus
4843 = (b->flags & BB_FORWARDER_BLOCK) != 0
4844 && LOCATION_LOCUS (EDGE_SUCC (b, 0)->goto_locus) == UNKNOWN_LOCATION;
4847 gcc_checking_assert (cfg_layout_can_merge_blocks_p (a, b));
4850 fprintf (dump_file, "Merging block %d into block %d...\n", b->index,
4853 /* If there was a CODE_LABEL beginning B, delete it. */
4854 if (LABEL_P (BB_HEAD (b)))
4856 delete_insn (BB_HEAD (b));
4859 /* We should have fallthru edge in a, or we can do dummy redirection to get
4861 if (JUMP_P (BB_END (a)))
4862 try_redirect_by_replacing_jump (EDGE_SUCC (a, 0), b, true);
4863 gcc_assert (!JUMP_P (BB_END (a)));
4865 /* If not optimizing, preserve the locus of the single edge between
4866 blocks A and B if necessary by emitting a nop. */
4868 && !forward_edge_locus
4869 && !DECL_IGNORED_P (current_function_decl))
4870 emit_nop_for_unique_locus_between (a, b);
4872 /* Move things from b->footer after a->footer. */
4876 BB_FOOTER (a) = BB_FOOTER (b);
4879 rtx_insn *last = BB_FOOTER (a);
4881 while (NEXT_INSN (last))
4882 last = NEXT_INSN (last);
4883 SET_NEXT_INSN (last) = BB_FOOTER (b);
4884 SET_PREV_INSN (BB_FOOTER (b)) = last;
4886 BB_FOOTER (b) = NULL;
4889 /* Move things from b->header before a->footer.
4890 Note that this may include dead tablejump data, but we don't clean
4891 those up until we go out of cfglayout mode. */
4894 if (! BB_FOOTER (a))
4895 BB_FOOTER (a) = BB_HEADER (b);
4898 rtx_insn *last = BB_HEADER (b);
4900 while (NEXT_INSN (last))
4901 last = NEXT_INSN (last);
4902 SET_NEXT_INSN (last) = BB_FOOTER (a);
4903 SET_PREV_INSN (BB_FOOTER (a)) = last;
4904 BB_FOOTER (a) = BB_HEADER (b);
4906 BB_HEADER (b) = NULL;
4909 /* In the case basic blocks are not adjacent, move them around. */
4910 if (NEXT_INSN (BB_END (a)) != BB_HEAD (b))
4912 insn = unlink_insn_chain (BB_HEAD (b), BB_END (b));
4914 emit_insn_after_noloc (insn, BB_END (a), a);
4916 /* Otherwise just re-associate the instructions. */
4920 BB_END (a) = BB_END (b);
4923 /* emit_insn_after_noloc doesn't call df_insn_change_bb.
4924 We need to explicitly call. */
4925 update_bb_for_insn_chain (insn, BB_END (b), a);
4927 /* Skip possible DELETED_LABEL insn. */
4928 if (!NOTE_INSN_BASIC_BLOCK_P (insn))
4929 insn = NEXT_INSN (insn);
4930 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
4931 BB_HEAD (b) = BB_END (b) = NULL;
4934 df_bb_delete (b->index);
4936 if (forward_edge_locus)
4937 EDGE_SUCC (b, 0)->goto_locus = EDGE_SUCC (a, 0)->goto_locus;
4940 fprintf (dump_file, "Merged blocks %d and %d.\n", a->index, b->index);
4946 cfg_layout_split_edge (edge e)
4948 basic_block new_bb =
4949 create_basic_block (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
4950 ? NEXT_INSN (BB_END (e->src)) : get_insns (),
4953 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
4954 BB_COPY_PARTITION (new_bb, e->src);
4956 BB_COPY_PARTITION (new_bb, e->dest);
4957 make_edge (new_bb, e->dest, EDGE_FALLTHRU);
4958 redirect_edge_and_branch_force (e, new_bb);
4963 /* Do postprocessing after making a forwarder block joined by edge FALLTHRU. */
4966 rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED)
4970 /* Return true if BB contains only labels or non-executable
4974 rtl_block_empty_p (basic_block bb)
4978 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
4979 || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
4982 FOR_BB_INSNS (bb, insn)
4983 if (NONDEBUG_INSN_P (insn)
4984 && (!any_uncondjump_p (insn) || !onlyjump_p (insn)))
4990 /* Split a basic block if it ends with a conditional branch and if
4991 the other part of the block is not empty. */
4994 rtl_split_block_before_cond_jump (basic_block bb)
4997 rtx_insn *split_point = NULL;
4998 rtx_insn *last = NULL;
4999 bool found_code = false;
5001 FOR_BB_INSNS (bb, insn)
5003 if (any_condjump_p (insn))
5005 else if (NONDEBUG_INSN_P (insn))
5010 /* Did not find everything. */
5011 if (found_code && split_point)
5012 return split_block (bb, split_point)->dest;
5017 /* Return 1 if BB ends with a call, possibly followed by some
5018 instructions that must stay with the call, 0 otherwise. */
5021 rtl_block_ends_with_call_p (basic_block bb)
5023 rtx_insn *insn = BB_END (bb);
5025 while (!CALL_P (insn)
5026 && insn != BB_HEAD (bb)
5027 && (keep_with_call_p (insn)
5029 || DEBUG_INSN_P (insn)))
5030 insn = PREV_INSN (insn);
5031 return (CALL_P (insn));
5034 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
5037 rtl_block_ends_with_condjump_p (const_basic_block bb)
5039 return any_condjump_p (BB_END (bb));
5042 /* Return true if we need to add fake edge to exit.
5043 Helper function for rtl_flow_call_edges_add. */
5046 need_fake_edge_p (const rtx_insn *insn)
5052 && !SIBLING_CALL_P (insn)
5053 && !find_reg_note (insn, REG_NORETURN, NULL)
5054 && !(RTL_CONST_OR_PURE_CALL_P (insn))))
5057 return ((GET_CODE (PATTERN (insn)) == ASM_OPERANDS
5058 && MEM_VOLATILE_P (PATTERN (insn)))
5059 || (GET_CODE (PATTERN (insn)) == PARALLEL
5060 && asm_noperands (insn) != -1
5061 && MEM_VOLATILE_P (XVECEXP (PATTERN (insn), 0, 0)))
5062 || GET_CODE (PATTERN (insn)) == ASM_INPUT);
5065 /* Add fake edges to the function exit for any non constant and non noreturn
5066 calls, volatile inline assembly in the bitmap of blocks specified by
5067 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
5070 The goal is to expose cases in which entering a basic block does not imply
5071 that all subsequent instructions must be executed. */
5074 rtl_flow_call_edges_add (sbitmap blocks)
5077 int blocks_split = 0;
5078 int last_bb = last_basic_block_for_fn (cfun);
5079 bool check_last_block = false;
5081 if (n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS)
5085 check_last_block = true;
5087 check_last_block = bitmap_bit_p (blocks,
5088 EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb->index);
5090 /* In the last basic block, before epilogue generation, there will be
5091 a fallthru edge to EXIT. Special care is required if the last insn
5092 of the last basic block is a call because make_edge folds duplicate
5093 edges, which would result in the fallthru edge also being marked
5094 fake, which would result in the fallthru edge being removed by
5095 remove_fake_edges, which would result in an invalid CFG.
5097 Moreover, we can't elide the outgoing fake edge, since the block
5098 profiler needs to take this into account in order to solve the minimal
5099 spanning tree in the case that the call doesn't return.
5101 Handle this by adding a dummy instruction in a new last basic block. */
5102 if (check_last_block)
5104 basic_block bb = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb;
5105 rtx_insn *insn = BB_END (bb);
5107 /* Back up past insns that must be kept in the same block as a call. */
5108 while (insn != BB_HEAD (bb)
5109 && keep_with_call_p (insn))
5110 insn = PREV_INSN (insn);
5112 if (need_fake_edge_p (insn))
5116 e = find_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun));
5119 insert_insn_on_edge (gen_use (const0_rtx), e);
5120 commit_edge_insertions ();
5125 /* Now add fake edges to the function exit for any non constant
5126 calls since there is no way that we can determine if they will
5129 for (i = NUM_FIXED_BLOCKS; i < last_bb; i++)
5131 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
5133 rtx_insn *prev_insn;
5138 if (blocks && !bitmap_bit_p (blocks, i))
5141 for (insn = BB_END (bb); ; insn = prev_insn)
5143 prev_insn = PREV_INSN (insn);
5144 if (need_fake_edge_p (insn))
5147 rtx_insn *split_at_insn = insn;
5149 /* Don't split the block between a call and an insn that should
5150 remain in the same block as the call. */
5152 while (split_at_insn != BB_END (bb)
5153 && keep_with_call_p (NEXT_INSN (split_at_insn)))
5154 split_at_insn = NEXT_INSN (split_at_insn);
5156 /* The handling above of the final block before the epilogue
5157 should be enough to verify that there is no edge to the exit
5158 block in CFG already. Calling make_edge in such case would
5159 cause us to mark that edge as fake and remove it later. */
5161 if (flag_checking && split_at_insn == BB_END (bb))
5163 e = find_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun));
5164 gcc_assert (e == NULL);
5167 /* Note that the following may create a new basic block
5168 and renumber the existing basic blocks. */
5169 if (split_at_insn != BB_END (bb))
5171 e = split_block (bb, split_at_insn);
5176 edge ne = make_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun), EDGE_FAKE);
5177 ne->probability = profile_probability::guessed_never ();
5180 if (insn == BB_HEAD (bb))
5186 verify_flow_info ();
5188 return blocks_split;
5191 /* Add COMP_RTX as a condition at end of COND_BB. FIRST_HEAD is
5192 the conditional branch target, SECOND_HEAD should be the fall-thru
5193 there is no need to handle this here the loop versioning code handles
5194 this. the reason for SECON_HEAD is that it is needed for condition
5195 in trees, and this should be of the same type since it is a hook. */
5197 rtl_lv_add_condition_to_bb (basic_block first_head ,
5198 basic_block second_head ATTRIBUTE_UNUSED,
5199 basic_block cond_bb, void *comp_rtx)
5201 rtx_code_label *label;
5202 rtx_insn *seq, *jump;
5203 rtx op0 = XEXP ((rtx)comp_rtx, 0);
5204 rtx op1 = XEXP ((rtx)comp_rtx, 1);
5205 enum rtx_code comp = GET_CODE ((rtx)comp_rtx);
5209 label = block_label (first_head);
5210 mode = GET_MODE (op0);
5211 if (mode == VOIDmode)
5212 mode = GET_MODE (op1);
5215 op0 = force_operand (op0, NULL_RTX);
5216 op1 = force_operand (op1, NULL_RTX);
5217 do_compare_rtx_and_jump (op0, op1, comp, 0, mode, NULL_RTX, NULL, label,
5218 profile_probability::uninitialized ());
5219 jump = get_last_insn ();
5220 JUMP_LABEL (jump) = label;
5221 LABEL_NUSES (label)++;
5225 /* Add the new cond, in the new head. */
5226 emit_insn_after (seq, BB_END (cond_bb));
5230 /* Given a block B with unconditional branch at its end, get the
5231 store the return the branch edge and the fall-thru edge in
5232 BRANCH_EDGE and FALLTHRU_EDGE respectively. */
5234 rtl_extract_cond_bb_edges (basic_block b, edge *branch_edge,
5235 edge *fallthru_edge)
5237 edge e = EDGE_SUCC (b, 0);
5239 if (e->flags & EDGE_FALLTHRU)
5242 *branch_edge = EDGE_SUCC (b, 1);
5247 *fallthru_edge = EDGE_SUCC (b, 1);
5252 init_rtl_bb_info (basic_block bb)
5254 gcc_assert (!bb->il.x.rtl);
5255 bb->il.x.head_ = NULL;
5256 bb->il.x.rtl = ggc_cleared_alloc<rtl_bb_info> ();
5260 rtl_bb_info_initialized_p (basic_block bb)
5262 return bb->il.x.rtl;
5265 /* Returns true if it is possible to remove edge E by redirecting
5266 it to the destination of the other edge from E->src. */
5269 rtl_can_remove_branch_p (const_edge e)
5271 const_basic_block src = e->src;
5272 const_basic_block target = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest;
5273 const rtx_insn *insn = BB_END (src);
5276 /* The conditions are taken from try_redirect_by_replacing_jump. */
5277 if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
5280 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
5283 if (BB_PARTITION (src) != BB_PARTITION (target))
5286 if (!onlyjump_p (insn)
5287 || tablejump_p (insn, NULL, NULL))
5290 set = single_set (insn);
5291 if (!set || side_effects_p (set))
5298 rtl_duplicate_bb (basic_block bb, copy_bb_data *id)
5300 bb = cfg_layout_duplicate_bb (bb, id);
5305 /* Do book-keeping of basic block BB for the profile consistency checker.
5306 Store the counting in RECORD. */
5308 rtl_account_profile_record (basic_block bb, struct profile_record *record)
5311 FOR_BB_INSNS (bb, insn)
5314 record->size += insn_cost (insn, false);
5317 if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa ().initialized_p ()
5318 && ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa ().nonzero_p ()
5319 && bb->count.ipa ().initialized_p ())
5321 += insn_cost (insn, true) * bb->count.ipa ().to_gcov_type ();
5323 else if (bb->count.initialized_p ()
5324 && ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.initialized_p ())
5326 += insn_cost (insn, true)
5327 * bb->count.to_sreal_scale
5328 (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count).to_double ();
5330 record->time += insn_cost (insn, true);
5334 /* Implementation of CFG manipulation for linearized RTL. */
5335 struct cfg_hooks rtl_cfg_hooks = {
5337 rtl_verify_flow_info,
5339 rtl_dump_bb_for_graph,
5340 rtl_create_basic_block,
5341 rtl_redirect_edge_and_branch,
5342 rtl_redirect_edge_and_branch_force,
5343 rtl_can_remove_branch_p,
5346 rtl_move_block_after,
5347 rtl_can_merge_blocks, /* can_merge_blocks_p */
5351 cfg_layout_can_duplicate_bb_p,
5354 rtl_make_forwarder_block,
5355 rtl_tidy_fallthru_edge,
5356 rtl_force_nonfallthru,
5357 rtl_block_ends_with_call_p,
5358 rtl_block_ends_with_condjump_p,
5359 rtl_flow_call_edges_add,
5360 NULL, /* execute_on_growing_pred */
5361 NULL, /* execute_on_shrinking_pred */
5362 NULL, /* duplicate loop for trees */
5363 NULL, /* lv_add_condition_to_bb */
5364 NULL, /* lv_adjust_loop_header_phi*/
5365 NULL, /* extract_cond_bb_edges */
5366 NULL, /* flush_pending_stmts */
5367 rtl_block_empty_p, /* block_empty_p */
5368 rtl_split_block_before_cond_jump, /* split_block_before_cond_jump */
5369 rtl_account_profile_record,
5372 /* Implementation of CFG manipulation for cfg layout RTL, where
5373 basic block connected via fallthru edges does not have to be adjacent.
5374 This representation will hopefully become the default one in future
5375 version of the compiler. */
5377 struct cfg_hooks cfg_layout_rtl_cfg_hooks = {
5379 rtl_verify_flow_info_1,
5381 rtl_dump_bb_for_graph,
5382 cfg_layout_create_basic_block,
5383 cfg_layout_redirect_edge_and_branch,
5384 cfg_layout_redirect_edge_and_branch_force,
5385 rtl_can_remove_branch_p,
5386 cfg_layout_delete_block,
5387 cfg_layout_split_block,
5388 rtl_move_block_after,
5389 cfg_layout_can_merge_blocks_p,
5390 cfg_layout_merge_blocks,
5393 cfg_layout_can_duplicate_bb_p,
5394 cfg_layout_duplicate_bb,
5395 cfg_layout_split_edge,
5396 rtl_make_forwarder_block,
5397 NULL, /* tidy_fallthru_edge */
5398 rtl_force_nonfallthru,
5399 rtl_block_ends_with_call_p,
5400 rtl_block_ends_with_condjump_p,
5401 rtl_flow_call_edges_add,
5402 NULL, /* execute_on_growing_pred */
5403 NULL, /* execute_on_shrinking_pred */
5404 duplicate_loop_body_to_header_edge, /* duplicate loop for trees */
5405 rtl_lv_add_condition_to_bb, /* lv_add_condition_to_bb */
5406 NULL, /* lv_adjust_loop_header_phi*/
5407 rtl_extract_cond_bb_edges, /* extract_cond_bb_edges */
5408 NULL, /* flush_pending_stmts */
5409 rtl_block_empty_p, /* block_empty_p */
5410 rtl_split_block_before_cond_jump, /* split_block_before_cond_jump */
5411 rtl_account_profile_record,
5414 #include "gt-cfgrtl.h"
5417 # pragma GCC diagnostic pop