1 /* Basic block reordering routines for the GNU compiler.
2 Copyright (C) 2000, 2001, 2003, 2004 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 2, 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 COPYING. If not, write to the Free
18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
23 #include "coretypes.h"
27 #include "hard-reg-set.h"
28 #include "basic-block.h"
29 #include "insn-config.h"
33 #include "cfglayout.h"
37 #include "alloc-pool.h"
40 /* The contents of the current function definition are allocated
41 in this obstack, and all are freed at the end of the function. */
42 extern struct obstack flow_obstack;
44 /* Holds the interesting trailing notes for the function. */
45 rtx cfg_layout_function_footer, cfg_layout_function_header;
47 static rtx skip_insns_after_block (basic_block);
48 static void record_effective_endpoints (void);
49 static rtx label_for_bb (basic_block);
50 static void fixup_reorder_chain (void);
52 static void set_block_levels (tree, int);
53 static void change_scope (rtx, tree, tree);
55 void verify_insn_chain (void);
56 static void fixup_fallthru_exit_predecessor (void);
57 static tree insn_scope (rtx);
58 static void update_unlikely_executed_notes (basic_block);
61 unlink_insn_chain (rtx first, rtx last)
63 rtx prevfirst = PREV_INSN (first);
64 rtx nextlast = NEXT_INSN (last);
66 PREV_INSN (first) = NULL;
67 NEXT_INSN (last) = NULL;
69 NEXT_INSN (prevfirst) = nextlast;
71 PREV_INSN (nextlast) = prevfirst;
73 set_last_insn (prevfirst);
75 set_first_insn (nextlast);
79 /* Skip over inter-block insns occurring after BB which are typically
80 associated with BB (e.g., barriers). If there are any such insns,
81 we return the last one. Otherwise, we return the end of BB. */
84 skip_insns_after_block (basic_block bb)
86 rtx insn, last_insn, next_head, prev;
89 if (bb->next_bb != EXIT_BLOCK_PTR)
90 next_head = BB_HEAD (bb->next_bb);
92 for (last_insn = insn = BB_END (bb); (insn = NEXT_INSN (insn)) != 0; )
94 if (insn == next_head)
97 switch (GET_CODE (insn))
104 switch (NOTE_LINE_NUMBER (insn))
106 case NOTE_INSN_LOOP_END:
107 case NOTE_INSN_BLOCK_END:
110 case NOTE_INSN_DELETED:
111 case NOTE_INSN_DELETED_LABEL:
122 && GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
123 && (GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_VEC
124 || GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_DIFF_VEC))
126 insn = NEXT_INSN (insn);
139 /* It is possible to hit contradictory sequence. For instance:
145 Where barrier belongs to jump_insn, but the note does not. This can be
146 created by removing the basic block originally following
147 NOTE_INSN_LOOP_BEG. In such case reorder the notes. */
149 for (insn = last_insn; insn != BB_END (bb); insn = prev)
151 prev = PREV_INSN (insn);
152 if (GET_CODE (insn) == NOTE)
153 switch (NOTE_LINE_NUMBER (insn))
155 case NOTE_INSN_LOOP_END:
156 case NOTE_INSN_BLOCK_END:
157 case NOTE_INSN_DELETED:
158 case NOTE_INSN_DELETED_LABEL:
161 reorder_insns (insn, insn, last_insn);
168 /* Locate or create a label for a given basic block. */
171 label_for_bb (basic_block bb)
173 rtx label = BB_HEAD (bb);
175 if (GET_CODE (label) != CODE_LABEL)
178 fprintf (dump_file, "Emitting label for block %d\n", bb->index);
180 label = block_label (bb);
186 /* Locate the effective beginning and end of the insn chain for each
187 block, as defined by skip_insns_after_block above. */
190 record_effective_endpoints (void)
196 for (insn = get_insns ();
198 && GET_CODE (insn) == NOTE
199 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK;
200 insn = NEXT_INSN (insn))
203 abort (); /* No basic blocks at all? */
204 if (PREV_INSN (insn))
205 cfg_layout_function_header =
206 unlink_insn_chain (get_insns (), PREV_INSN (insn));
208 cfg_layout_function_header = NULL_RTX;
210 next_insn = get_insns ();
215 if (PREV_INSN (BB_HEAD (bb)) && next_insn != BB_HEAD (bb))
216 bb->rbi->header = unlink_insn_chain (next_insn,
217 PREV_INSN (BB_HEAD (bb)));
218 end = skip_insns_after_block (bb);
219 if (NEXT_INSN (BB_END (bb)) && BB_END (bb) != end)
220 bb->rbi->footer = unlink_insn_chain (NEXT_INSN (BB_END (bb)), end);
221 next_insn = NEXT_INSN (BB_END (bb));
224 cfg_layout_function_footer = next_insn;
225 if (cfg_layout_function_footer)
226 cfg_layout_function_footer = unlink_insn_chain (cfg_layout_function_footer, get_last_insn ());
229 /* Data structures representing mapping of INSN_LOCATOR into scope blocks, line
230 numbers and files. In order to be GGC friendly we need to use separate
231 varrays. This also slightly improve the memory locality in binary search.
232 The _locs array contains locators where the given property change. The
233 block_locators_blocks contains the scope block that is used for all insn
234 locator greater than corresponding block_locators_locs value and smaller
235 than the following one. Similarly for the other properties. */
236 static GTY(()) varray_type block_locators_locs;
237 static GTY(()) varray_type block_locators_blocks;
238 static GTY(()) varray_type line_locators_locs;
239 static GTY(()) varray_type line_locators_lines;
240 static GTY(()) varray_type file_locators_locs;
241 static GTY(()) varray_type file_locators_files;
242 int prologue_locator;
243 int epilogue_locator;
245 /* During the RTL expansion the lexical blocks and line numbers are
246 represented via INSN_NOTEs. Replace them by representation using
250 insn_locators_initialize (void)
253 tree last_block = NULL;
256 int line_number = 0, last_line_number = 0;
257 char *file_name = NULL, *last_file_name = NULL;
259 prologue_locator = epilogue_locator = 0;
261 VARRAY_INT_INIT (block_locators_locs, 32, "block_locators_locs");
262 VARRAY_TREE_INIT (block_locators_blocks, 32, "block_locators_blocks");
263 VARRAY_INT_INIT (line_locators_locs, 32, "line_locators_locs");
264 VARRAY_INT_INIT (line_locators_lines, 32, "line_locators_lines");
265 VARRAY_INT_INIT (file_locators_locs, 32, "file_locators_locs");
266 VARRAY_CHAR_PTR_INIT (file_locators_files, 32, "file_locators_files");
268 for (insn = get_insns (); insn; insn = next)
270 next = NEXT_INSN (insn);
272 if ((active_insn_p (insn)
273 && GET_CODE (PATTERN (insn)) != ADDR_VEC
274 && GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC)
276 || (!prologue_locator && file_name))
278 if (last_block != block)
281 VARRAY_PUSH_INT (block_locators_locs, loc);
282 VARRAY_PUSH_TREE (block_locators_blocks, block);
285 if (last_line_number != line_number)
288 VARRAY_PUSH_INT (line_locators_locs, loc);
289 VARRAY_PUSH_INT (line_locators_lines, line_number);
290 last_line_number = line_number;
292 if (last_file_name != file_name)
295 VARRAY_PUSH_INT (file_locators_locs, loc);
296 VARRAY_PUSH_CHAR_PTR (file_locators_files, file_name);
297 last_file_name = file_name;
300 if (!prologue_locator && file_name)
301 prologue_locator = loc;
302 if (!NEXT_INSN (insn))
303 epilogue_locator = loc;
304 if (active_insn_p (insn))
305 INSN_LOCATOR (insn) = loc;
306 else if (GET_CODE (insn) == NOTE)
308 switch (NOTE_LINE_NUMBER (insn))
310 case NOTE_INSN_BLOCK_BEG:
311 if (cfun->dont_emit_block_notes)
313 block = NOTE_BLOCK (insn);
316 case NOTE_INSN_BLOCK_END:
317 if (cfun->dont_emit_block_notes)
319 block = BLOCK_SUPERCONTEXT (block);
320 if (block && TREE_CODE (block) == FUNCTION_DECL)
325 if (NOTE_LINE_NUMBER (insn) > 0)
327 line_number = NOTE_LINE_NUMBER (insn);
328 file_name = (char *)NOTE_SOURCE_FILE (insn);
334 if (cfun->dont_emit_block_notes)
335 check_block_change (insn, &block);
338 /* Tag the blocks with a depth number so that change_scope can find
339 the common parent easily. */
340 set_block_levels (DECL_INITIAL (cfun->decl), 0);
342 if (cfun->dont_emit_block_notes)
343 free_block_changes ();
346 /* For each lexical block, set BLOCK_NUMBER to the depth at which it is
347 found in the block tree. */
350 set_block_levels (tree block, int level)
354 BLOCK_NUMBER (block) = level;
355 set_block_levels (BLOCK_SUBBLOCKS (block), level + 1);
356 block = BLOCK_CHAIN (block);
360 /* Return sope resulting from combination of S1 and S2. */
362 choose_inner_scope (tree s1, tree s2)
368 if (BLOCK_NUMBER (s1) > BLOCK_NUMBER (s2))
373 /* Emit lexical block notes needed to change scope from S1 to S2. */
376 change_scope (rtx orig_insn, tree s1, tree s2)
378 rtx insn = orig_insn;
379 tree com = NULL_TREE;
380 tree ts1 = s1, ts2 = s2;
385 if (ts1 == NULL || ts2 == NULL)
387 if (BLOCK_NUMBER (ts1) > BLOCK_NUMBER (ts2))
388 ts1 = BLOCK_SUPERCONTEXT (ts1);
389 else if (BLOCK_NUMBER (ts1) < BLOCK_NUMBER (ts2))
390 ts2 = BLOCK_SUPERCONTEXT (ts2);
393 ts1 = BLOCK_SUPERCONTEXT (ts1);
394 ts2 = BLOCK_SUPERCONTEXT (ts2);
403 rtx note = emit_note_before (NOTE_INSN_BLOCK_END, insn);
404 NOTE_BLOCK (note) = s;
405 s = BLOCK_SUPERCONTEXT (s);
412 insn = emit_note_before (NOTE_INSN_BLOCK_BEG, insn);
413 NOTE_BLOCK (insn) = s;
414 s = BLOCK_SUPERCONTEXT (s);
418 /* Return lexical scope block insn belong to. */
420 insn_scope (rtx insn)
422 int max = VARRAY_ACTIVE_SIZE (block_locators_locs);
424 int loc = INSN_LOCATOR (insn);
426 /* When block_locators_locs was initialized, the pro- and epilogue
427 insns didn't exist yet and can therefore not be found this way.
428 But we know that they belong to the outer most block of the
430 Without this test, the prologue would be put inside the block of
431 the first valid instruction in the function and when that first
432 insn is part of an inlined function then the low_pc of that
433 inlined function is messed up. Likewise for the epilogue and
434 the last valid instruction. */
435 if (loc == prologue_locator || loc == epilogue_locator)
436 return DECL_INITIAL (cfun->decl);
442 int pos = (min + max) / 2;
443 int tmp = VARRAY_INT (block_locators_locs, pos);
445 if (tmp <= loc && min != pos)
447 else if (tmp > loc && max != pos)
455 return VARRAY_TREE (block_locators_blocks, min);
458 /* Return line number of the statement specified by the locator. */
460 locator_line (int loc)
462 int max = VARRAY_ACTIVE_SIZE (line_locators_locs);
469 int pos = (min + max) / 2;
470 int tmp = VARRAY_INT (line_locators_locs, pos);
472 if (tmp <= loc && min != pos)
474 else if (tmp > loc && max != pos)
482 return VARRAY_INT (line_locators_lines, min);
485 /* Return line number of the statement that produced this insn. */
489 return locator_line (INSN_LOCATOR (insn));
492 /* Return source file of the statement specified by LOC. */
494 locator_file (int loc)
496 int max = VARRAY_ACTIVE_SIZE (file_locators_locs);
503 int pos = (min + max) / 2;
504 int tmp = VARRAY_INT (file_locators_locs, pos);
506 if (tmp <= loc && min != pos)
508 else if (tmp > loc && max != pos)
516 return VARRAY_CHAR_PTR (file_locators_files, min);
519 /* Return source file of the statement that produced this insn. */
523 return locator_file (INSN_LOCATOR (insn));
526 /* Rebuild all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes based
527 on the scope tree and the newly reordered instructions. */
530 reemit_insn_block_notes (void)
532 tree cur_block = DECL_INITIAL (cfun->decl);
536 if (!active_insn_p (insn))
537 insn = next_active_insn (insn);
538 for (; insn; insn = next_active_insn (insn))
542 this_block = insn_scope (insn);
543 /* For sequences compute scope resulting from merging all scopes
544 of instructions nested inside. */
545 if (GET_CODE (PATTERN (insn)) == SEQUENCE)
548 rtx body = PATTERN (insn);
551 for (i = 0; i < XVECLEN (body, 0); i++)
552 this_block = choose_inner_scope (this_block,
553 insn_scope (XVECEXP (body, 0, i)));
558 if (this_block != cur_block)
560 change_scope (insn, cur_block, this_block);
561 cur_block = this_block;
565 /* change_scope emits before the insn, not after. */
566 note = emit_note (NOTE_INSN_DELETED);
567 change_scope (note, cur_block, DECL_INITIAL (cfun->decl));
573 /* Given a reorder chain, rearrange the code to match. */
576 fixup_reorder_chain (void)
578 basic_block bb, prev_bb;
582 if (cfg_layout_function_header)
584 set_first_insn (cfg_layout_function_header);
585 insn = cfg_layout_function_header;
586 while (NEXT_INSN (insn))
587 insn = NEXT_INSN (insn);
590 /* First do the bulk reordering -- rechain the blocks without regard to
591 the needed changes to jumps and labels. */
593 for (bb = ENTRY_BLOCK_PTR->next_bb, index = 0;
595 bb = bb->rbi->next, index++)
600 NEXT_INSN (insn) = bb->rbi->header;
602 set_first_insn (bb->rbi->header);
603 PREV_INSN (bb->rbi->header) = insn;
604 insn = bb->rbi->header;
605 while (NEXT_INSN (insn))
606 insn = NEXT_INSN (insn);
609 NEXT_INSN (insn) = BB_HEAD (bb);
611 set_first_insn (BB_HEAD (bb));
612 PREV_INSN (BB_HEAD (bb)) = insn;
616 NEXT_INSN (insn) = bb->rbi->footer;
617 PREV_INSN (bb->rbi->footer) = insn;
618 while (NEXT_INSN (insn))
619 insn = NEXT_INSN (insn);
623 if (index != n_basic_blocks)
626 NEXT_INSN (insn) = cfg_layout_function_footer;
627 if (cfg_layout_function_footer)
628 PREV_INSN (cfg_layout_function_footer) = insn;
630 while (NEXT_INSN (insn))
631 insn = NEXT_INSN (insn);
633 set_last_insn (insn);
634 #ifdef ENABLE_CHECKING
635 verify_insn_chain ();
637 delete_dead_jumptables ();
639 /* Now add jumps and labels as needed to match the blocks new
642 for (bb = ENTRY_BLOCK_PTR->next_bb; bb ; bb = bb->rbi->next)
644 edge e_fall, e_taken, e;
649 if (bb->succ == NULL)
652 /* Find the old fallthru edge, and another non-EH edge for
654 e_taken = e_fall = NULL;
655 for (e = bb->succ; e ; e = e->succ_next)
656 if (e->flags & EDGE_FALLTHRU)
658 else if (! (e->flags & EDGE_EH))
661 bb_end_insn = BB_END (bb);
662 if (GET_CODE (bb_end_insn) == JUMP_INSN)
664 if (any_condjump_p (bb_end_insn))
666 /* If the old fallthru is still next, nothing to do. */
667 if (bb->rbi->next == e_fall->dest
668 || e_fall->dest == EXIT_BLOCK_PTR)
671 /* The degenerated case of conditional jump jumping to the next
672 instruction can happen on target having jumps with side
675 Create temporarily the duplicated edge representing branch.
676 It will get unidentified by force_nonfallthru_and_redirect
677 that would otherwise get confused by fallthru edge not pointing
678 to the next basic block. */
684 e_fake = unchecked_make_edge (bb, e_fall->dest, 0);
686 if (!redirect_jump (BB_END (bb), block_label (bb), 0))
688 note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX);
691 int prob = INTVAL (XEXP (note, 0));
693 e_fake->probability = prob;
694 e_fake->count = e_fall->count * prob / REG_BR_PROB_BASE;
695 e_fall->probability -= e_fall->probability;
696 e_fall->count -= e_fake->count;
697 if (e_fall->probability < 0)
698 e_fall->probability = 0;
699 if (e_fall->count < 0)
703 /* There is one special case: if *neither* block is next,
704 such as happens at the very end of a function, then we'll
705 need to add a new unconditional jump. Choose the taken
706 edge based on known or assumed probability. */
707 else if (bb->rbi->next != e_taken->dest)
709 rtx note = find_reg_note (bb_end_insn, REG_BR_PROB, 0);
712 && INTVAL (XEXP (note, 0)) < REG_BR_PROB_BASE / 2
713 && invert_jump (bb_end_insn,
714 (e_fall->dest == EXIT_BLOCK_PTR
716 : label_for_bb (e_fall->dest)), 0))
718 e_fall->flags &= ~EDGE_FALLTHRU;
719 #ifdef ENABLE_CHECKING
720 if (!could_fall_through (e_taken->src, e_taken->dest))
723 e_taken->flags |= EDGE_FALLTHRU;
724 update_br_prob_note (bb);
725 e = e_fall, e_fall = e_taken, e_taken = e;
729 /* If the "jumping" edge is a crossing edge, and the fall
730 through edge is non-crossing, leave things as they are. */
731 else if (e_taken->crossing_edge && !e_fall->crossing_edge)
734 /* Otherwise we can try to invert the jump. This will
735 basically never fail, however, keep up the pretense. */
736 else if (invert_jump (bb_end_insn,
737 (e_fall->dest == EXIT_BLOCK_PTR
739 : label_for_bb (e_fall->dest)), 0))
741 e_fall->flags &= ~EDGE_FALLTHRU;
742 #ifdef ENABLE_CHECKING
743 if (!could_fall_through (e_taken->src, e_taken->dest))
746 e_taken->flags |= EDGE_FALLTHRU;
747 update_br_prob_note (bb);
751 else if (returnjump_p (bb_end_insn))
755 /* Otherwise we have some switch or computed jump. In the
756 99% case, there should not have been a fallthru edge. */
760 #ifdef CASE_DROPS_THROUGH
761 /* Except for VAX. Since we didn't have predication for the
762 tablejump, the fallthru block should not have moved. */
763 if (bb->rbi->next == e_fall->dest)
765 bb_end_insn = skip_insns_after_block (bb);
773 /* No fallthru implies a noreturn function with EH edges, or
774 something similarly bizarre. In any case, we don't need to
779 /* If the fallthru block is still next, nothing to do. */
780 if (bb->rbi->next == e_fall->dest)
783 /* A fallthru to exit block. */
784 if (e_fall->dest == EXIT_BLOCK_PTR)
788 /* We got here if we need to add a new jump insn. */
789 nb = force_nonfallthru (e_fall);
792 initialize_bb_rbi (nb);
793 nb->rbi->visited = 1;
794 nb->rbi->next = bb->rbi->next;
796 /* Don't process this new block. */
800 /* Make sure new bb is tagged for correct section (same as
801 fall-thru source). */
802 e_fall->src->partition = bb->pred->src->partition;
803 if (flag_reorder_blocks_and_partition)
805 if (bb->pred->src->partition == COLD_PARTITION)
808 rtx note = BB_HEAD (e_fall->src);
810 while (!INSN_P (note)
811 && note != BB_END (e_fall->src))
812 note = NEXT_INSN (note);
814 new_note = emit_note_before
815 (NOTE_INSN_UNLIKELY_EXECUTED_CODE,
817 NOTE_BASIC_BLOCK (new_note) = bb;
819 if (GET_CODE (BB_END (bb)) == JUMP_INSN
820 && !any_condjump_p (BB_END (bb))
821 && bb->succ->crossing_edge )
822 REG_NOTES (BB_END (bb)) = gen_rtx_EXPR_LIST
823 (REG_CROSSING_JUMP, NULL_RTX, REG_NOTES (BB_END (bb)));
828 /* Put basic_block_info in the new order. */
832 fprintf (dump_file, "Reordered sequence:\n");
833 for (bb = ENTRY_BLOCK_PTR->next_bb, index = 0;
835 bb = bb->rbi->next, index++)
837 fprintf (dump_file, " %i ", index);
838 if (bb->rbi->original)
839 fprintf (dump_file, "duplicate of %i ",
840 bb->rbi->original->index);
841 else if (forwarder_block_p (bb)
842 && GET_CODE (BB_HEAD (bb)) != CODE_LABEL)
843 fprintf (dump_file, "compensation ");
845 fprintf (dump_file, "bb %i ", bb->index);
846 fprintf (dump_file, " [%i]\n", bb->frequency);
850 prev_bb = ENTRY_BLOCK_PTR;
851 bb = ENTRY_BLOCK_PTR->next_bb;
854 for (; bb; prev_bb = bb, bb = bb->rbi->next, index ++)
857 BASIC_BLOCK (index) = bb;
859 update_unlikely_executed_notes (bb);
861 bb->prev_bb = prev_bb;
862 prev_bb->next_bb = bb;
864 prev_bb->next_bb = EXIT_BLOCK_PTR;
865 EXIT_BLOCK_PTR->prev_bb = prev_bb;
867 /* Annoying special case - jump around dead jumptables left in the code. */
871 for (e = bb->succ; e && !(e->flags & EDGE_FALLTHRU); e = e->succ_next)
873 if (e && !can_fallthru (e->src, e->dest))
874 force_nonfallthru (e);
878 /* Update the basic block number information in any
879 NOTE_INSN_UNLIKELY_EXECUTED_CODE notes within the basic block. */
882 update_unlikely_executed_notes (basic_block bb)
886 for (cur_insn = BB_HEAD (bb); cur_insn != BB_END (bb);
887 cur_insn = NEXT_INSN (cur_insn))
888 if (GET_CODE (cur_insn) == NOTE
889 && NOTE_LINE_NUMBER (cur_insn) == NOTE_INSN_UNLIKELY_EXECUTED_CODE)
890 NOTE_BASIC_BLOCK (cur_insn) = bb;
893 /* Perform sanity checks on the insn chain.
894 1. Check that next/prev pointers are consistent in both the forward and
896 2. Count insns in chain, going both directions, and check if equal.
897 3. Check that get_last_insn () returns the actual end of chain. */
900 verify_insn_chain (void)
903 int insn_cnt1, insn_cnt2;
905 for (prevx = NULL, insn_cnt1 = 1, x = get_insns ();
907 prevx = x, insn_cnt1++, x = NEXT_INSN (x))
908 if (PREV_INSN (x) != prevx)
911 if (prevx != get_last_insn ())
914 for (nextx = NULL, insn_cnt2 = 1, x = get_last_insn ();
916 nextx = x, insn_cnt2++, x = PREV_INSN (x))
917 if (NEXT_INSN (x) != nextx)
920 if (insn_cnt1 != insn_cnt2)
924 /* If we have assembler epilogues, the block falling through to exit must
925 be the last one in the reordered chain when we reach final. Ensure
926 that this condition is met. */
928 fixup_fallthru_exit_predecessor (void)
931 basic_block bb = NULL;
933 /* This transformation is not valid before reload, because we might separate
934 a call from the instruction that copies the return value. */
935 if (! reload_completed)
938 for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
939 if (e->flags & EDGE_FALLTHRU)
942 if (bb && bb->rbi->next)
944 basic_block c = ENTRY_BLOCK_PTR->next_bb;
946 /* If the very first block is the one with the fall-through exit
947 edge, we have to split that block. */
950 bb = split_block (bb, NULL)->dest;
951 initialize_bb_rbi (bb);
952 bb->rbi->next = c->rbi->next;
954 bb->rbi->footer = c->rbi->footer;
955 c->rbi->footer = NULL;
958 while (c->rbi->next != bb)
961 c->rbi->next = bb->rbi->next;
966 bb->rbi->next = NULL;
970 /* Return true in case it is possible to duplicate the basic block BB. */
972 /* We do not want to declare the function in a header file, since it should
973 only be used through the cfghooks interface, and we do not want to move
974 it to cfgrtl.c since it would require also moving quite a lot of related
976 extern bool cfg_layout_can_duplicate_bb_p (basic_block);
979 cfg_layout_can_duplicate_bb_p (basic_block bb)
981 /* Do not attempt to duplicate tablejumps, as we need to unshare
982 the dispatch table. This is difficult to do, as the instructions
983 computing jump destination may be hoisted outside the basic block. */
984 if (tablejump_p (BB_END (bb), NULL, NULL))
987 /* Do not duplicate blocks containing insns that can't be copied. */
988 if (targetm.cannot_copy_insn_p)
990 rtx insn = BB_HEAD (bb);
993 if (INSN_P (insn) && targetm.cannot_copy_insn_p (insn))
995 if (insn == BB_END (bb))
997 insn = NEXT_INSN (insn);
1005 duplicate_insn_chain (rtx from, rtx to)
1009 /* Avoid updating of boundaries of previous basic block. The
1010 note will get removed from insn stream in fixup. */
1011 last = emit_note (NOTE_INSN_DELETED);
1013 /* Create copy at the end of INSN chain. The chain will
1014 be reordered later. */
1015 for (insn = from; insn != NEXT_INSN (to); insn = NEXT_INSN (insn))
1017 switch (GET_CODE (insn))
1022 /* Avoid copying of dispatch tables. We never duplicate
1023 tablejumps, so this can hit only in case the table got
1024 moved far from original jump. */
1025 if (GET_CODE (PATTERN (insn)) == ADDR_VEC
1026 || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
1028 emit_copy_of_insn_after (insn, get_last_insn ());
1039 switch (NOTE_LINE_NUMBER (insn))
1041 /* In case prologue is empty and function contain label
1042 in first BB, we may want to copy the block. */
1043 case NOTE_INSN_PROLOGUE_END:
1045 case NOTE_INSN_LOOP_VTOP:
1046 case NOTE_INSN_LOOP_CONT:
1047 case NOTE_INSN_LOOP_BEG:
1048 case NOTE_INSN_LOOP_END:
1049 /* Strip down the loop notes - we don't really want to keep
1050 them consistent in loop copies. */
1051 case NOTE_INSN_DELETED:
1052 case NOTE_INSN_DELETED_LABEL:
1053 /* No problem to strip these. */
1054 case NOTE_INSN_EPILOGUE_BEG:
1055 case NOTE_INSN_FUNCTION_END:
1056 /* Debug code expect these notes to exist just once.
1057 Keep them in the master copy.
1058 ??? It probably makes more sense to duplicate them for each
1060 case NOTE_INSN_FUNCTION_BEG:
1061 /* There is always just single entry to function. */
1062 case NOTE_INSN_BASIC_BLOCK:
1065 /* There is no purpose to duplicate prologue. */
1066 case NOTE_INSN_BLOCK_BEG:
1067 case NOTE_INSN_BLOCK_END:
1068 /* The BLOCK_BEG/BLOCK_END notes should be eliminated when BB
1069 reordering is in the progress. */
1070 case NOTE_INSN_EH_REGION_BEG:
1071 case NOTE_INSN_EH_REGION_END:
1072 /* Should never exist at BB duplication time. */
1075 case NOTE_INSN_REPEATED_LINE_NUMBER:
1076 case NOTE_INSN_UNLIKELY_EXECUTED_CODE:
1077 emit_note_copy (insn);
1081 if (NOTE_LINE_NUMBER (insn) < 0)
1083 /* It is possible that no_line_number is set and the note
1084 won't be emitted. */
1085 emit_note_copy (insn);
1092 insn = NEXT_INSN (last);
1096 /* Create a duplicate of the basic block BB. */
1098 /* We do not want to declare the function in a header file, since it should
1099 only be used through the cfghooks interface, and we do not want to move
1100 it to cfgrtl.c since it would require also moving quite a lot of related
1102 extern basic_block cfg_layout_duplicate_bb (basic_block);
1105 cfg_layout_duplicate_bb (basic_block bb)
1110 insn = duplicate_insn_chain (BB_HEAD (bb), BB_END (bb));
1111 new_bb = create_basic_block (insn,
1112 insn ? get_last_insn () : NULL,
1113 EXIT_BLOCK_PTR->prev_bb);
1115 if (bb->rbi->header)
1117 insn = bb->rbi->header;
1118 while (NEXT_INSN (insn))
1119 insn = NEXT_INSN (insn);
1120 insn = duplicate_insn_chain (bb->rbi->header, insn);
1122 new_bb->rbi->header = unlink_insn_chain (insn, get_last_insn ());
1125 if (bb->rbi->footer)
1127 insn = bb->rbi->footer;
1128 while (NEXT_INSN (insn))
1129 insn = NEXT_INSN (insn);
1130 insn = duplicate_insn_chain (bb->rbi->footer, insn);
1132 new_bb->rbi->footer = unlink_insn_chain (insn, get_last_insn ());
1135 if (bb->global_live_at_start)
1137 new_bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
1138 new_bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
1139 COPY_REG_SET (new_bb->global_live_at_start, bb->global_live_at_start);
1140 COPY_REG_SET (new_bb->global_live_at_end, bb->global_live_at_end);
1146 /* Main entry point to this module - initialize the data structures for
1147 CFG layout changes. It keeps LOOPS up-to-date if not null. */
1150 cfg_layout_initialize (void)
1154 /* Our algorithm depends on fact that there are no dead jumptables
1158 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1159 initialize_bb_rbi (bb);
1161 cfg_layout_rtl_register_cfg_hooks ();
1163 record_effective_endpoints ();
1165 cleanup_cfg (CLEANUP_CFGLAYOUT);
1168 /* Splits superblocks. */
1170 break_superblocks (void)
1172 sbitmap superblocks;
1176 superblocks = sbitmap_alloc (last_basic_block);
1177 sbitmap_zero (superblocks);
1180 if (bb->flags & BB_SUPERBLOCK)
1182 bb->flags &= ~BB_SUPERBLOCK;
1183 SET_BIT (superblocks, bb->index);
1189 rebuild_jump_labels (get_insns ());
1190 find_many_sub_basic_blocks (superblocks);
1196 /* Finalize the changes: reorder insn list according to the sequence, enter
1197 compensation code, rebuild scope forest. */
1200 cfg_layout_finalize (void)
1204 #ifdef ENABLE_CHECKING
1205 verify_flow_info ();
1207 rtl_register_cfg_hooks ();
1208 if (reload_completed
1209 #ifdef HAVE_epilogue
1213 fixup_fallthru_exit_predecessor ();
1214 fixup_reorder_chain ();
1216 #ifdef ENABLE_CHECKING
1217 verify_insn_chain ();
1221 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1224 break_superblocks ();
1226 #ifdef ENABLE_CHECKING
1227 verify_flow_info ();
1231 /* Checks whether all N blocks in BBS array can be copied. */
1233 can_copy_bbs_p (basic_block *bbs, unsigned n)
1239 for (i = 0; i < n; i++)
1240 bbs[i]->rbi->duplicated = 1;
1242 for (i = 0; i < n; i++)
1244 /* In case we should redirect abnormal edge during duplication, fail. */
1245 for (e = bbs[i]->succ; e; e = e->succ_next)
1246 if ((e->flags & EDGE_ABNORMAL)
1247 && e->dest->rbi->duplicated)
1253 if (!can_duplicate_block_p (bbs[i]))
1261 for (i = 0; i < n; i++)
1262 bbs[i]->rbi->duplicated = 0;
1267 /* Duplicates N basic blocks stored in array BBS. Newly created basic blocks
1268 are placed into array NEW_BBS in the same order. Edges from basic blocks
1269 in BBS are also duplicated and copies of those of them
1270 that lead into BBS are redirected to appropriate newly created block. The
1271 function assigns bbs into loops (copy of basic block bb is assigned to
1272 bb->loop_father->copy loop, so this must be set up correctly in advance)
1273 and updates dominators locally (LOOPS structure that contains the information
1274 about dominators is passed to enable this).
1276 BASE is the superloop to that basic block belongs; if its header or latch
1277 is copied, we do not set the new blocks as header or latch.
1279 Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
1280 also in the same order. */
1283 copy_bbs (basic_block *bbs, unsigned n, basic_block *new_bbs,
1284 edge *edges, unsigned n_edges, edge *new_edges,
1288 basic_block bb, new_bb, dom_bb;
1291 /* Duplicate bbs, update dominators, assign bbs to loops. */
1292 for (i = 0; i < n; i++)
1296 new_bb = new_bbs[i] = duplicate_block (bb, NULL);
1297 bb->rbi->duplicated = 1;
1299 add_bb_to_loop (new_bb, bb->loop_father->copy);
1300 /* Possibly set header. */
1301 if (bb->loop_father->header == bb && bb->loop_father != base)
1302 new_bb->loop_father->header = new_bb;
1304 if (bb->loop_father->latch == bb && bb->loop_father != base)
1305 new_bb->loop_father->latch = new_bb;
1308 /* Set dominators. */
1309 for (i = 0; i < n; i++)
1312 new_bb = new_bbs[i];
1314 dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
1315 if (dom_bb->rbi->duplicated)
1317 dom_bb = dom_bb->rbi->copy;
1318 set_immediate_dominator (CDI_DOMINATORS, new_bb, dom_bb);
1322 /* Redirect edges. */
1323 for (j = 0; j < n_edges; j++)
1324 new_edges[j] = NULL;
1325 for (i = 0; i < n; i++)
1327 new_bb = new_bbs[i];
1330 for (e = new_bb->succ; e; e = e->succ_next)
1332 for (j = 0; j < n_edges; j++)
1333 if (edges[j] && edges[j]->src == bb && edges[j]->dest == e->dest)
1336 if (!e->dest->rbi->duplicated)
1338 redirect_edge_and_branch_force (e, e->dest->rbi->copy);
1342 /* Clear information about duplicates. */
1343 for (i = 0; i < n; i++)
1344 bbs[i]->rbi->duplicated = 0;
1347 #include "gt-cfglayout.h"