1 /* Basic block reordering routines for the GNU compiler.
2 Copyright (C) 2000, 2001, 2003, 2004, 2005, 2006, 2007, 2008, 2009
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
27 #include "hard-reg-set.h"
29 #include "basic-block.h"
30 #include "insn-config.h"
33 #include "cfglayout.h"
37 #include "alloc-pool.h"
39 #include "tree-pass.h"
43 /* Holds the interesting trailing notes for the function. */
44 rtx cfg_layout_function_footer;
45 rtx 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 change_scope (rtx, tree, tree);
54 void verify_insn_chain (void);
55 static void fixup_fallthru_exit_predecessor (void);
56 static tree insn_scope (const_rtx);
59 unlink_insn_chain (rtx first, rtx last)
61 rtx prevfirst = PREV_INSN (first);
62 rtx nextlast = NEXT_INSN (last);
64 PREV_INSN (first) = NULL;
65 NEXT_INSN (last) = NULL;
67 NEXT_INSN (prevfirst) = nextlast;
69 PREV_INSN (nextlast) = prevfirst;
71 set_last_insn (prevfirst);
73 set_first_insn (nextlast);
77 /* Skip over inter-block insns occurring after BB which are typically
78 associated with BB (e.g., barriers). If there are any such insns,
79 we return the last one. Otherwise, we return the end of BB. */
82 skip_insns_after_block (basic_block bb)
84 rtx insn, last_insn, next_head, prev;
87 if (bb->next_bb != EXIT_BLOCK_PTR)
88 next_head = BB_HEAD (bb->next_bb);
90 for (last_insn = insn = BB_END (bb); (insn = NEXT_INSN (insn)) != 0; )
92 if (insn == next_head)
95 switch (GET_CODE (insn))
102 switch (NOTE_KIND (insn))
104 case NOTE_INSN_BLOCK_END:
115 && JUMP_P (NEXT_INSN (insn))
116 && (GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_VEC
117 || GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_DIFF_VEC))
119 insn = NEXT_INSN (insn);
132 /* It is possible to hit contradictory sequence. For instance:
138 Where barrier belongs to jump_insn, but the note does not. This can be
139 created by removing the basic block originally following
140 NOTE_INSN_BLOCK_BEG. In such case reorder the notes. */
142 for (insn = last_insn; insn != BB_END (bb); insn = prev)
144 prev = PREV_INSN (insn);
146 switch (NOTE_KIND (insn))
148 case NOTE_INSN_BLOCK_END:
151 case NOTE_INSN_DELETED:
152 case NOTE_INSN_DELETED_LABEL:
155 reorder_insns (insn, insn, last_insn);
162 /* Locate or create a label for a given basic block. */
165 label_for_bb (basic_block bb)
167 rtx label = BB_HEAD (bb);
169 if (!LABEL_P (label))
172 fprintf (dump_file, "Emitting label for block %d\n", bb->index);
174 label = block_label (bb);
180 /* Locate the effective beginning and end of the insn chain for each
181 block, as defined by skip_insns_after_block above. */
184 record_effective_endpoints (void)
190 for (insn = get_insns ();
193 && NOTE_KIND (insn) != NOTE_INSN_BASIC_BLOCK;
194 insn = NEXT_INSN (insn))
196 /* No basic blocks at all? */
199 if (PREV_INSN (insn))
200 cfg_layout_function_header =
201 unlink_insn_chain (get_insns (), PREV_INSN (insn));
203 cfg_layout_function_header = NULL_RTX;
205 next_insn = get_insns ();
210 if (PREV_INSN (BB_HEAD (bb)) && next_insn != BB_HEAD (bb))
211 bb->il.rtl->header = unlink_insn_chain (next_insn,
212 PREV_INSN (BB_HEAD (bb)));
213 end = skip_insns_after_block (bb);
214 if (NEXT_INSN (BB_END (bb)) && BB_END (bb) != end)
215 bb->il.rtl->footer = unlink_insn_chain (NEXT_INSN (BB_END (bb)), end);
216 next_insn = NEXT_INSN (BB_END (bb));
219 cfg_layout_function_footer = next_insn;
220 if (cfg_layout_function_footer)
221 cfg_layout_function_footer = unlink_insn_chain (cfg_layout_function_footer, get_last_insn ());
224 /* Data structures representing mapping of INSN_LOCATOR into scope blocks, line
225 numbers and files. In order to be GGC friendly we need to use separate
226 varrays. This also slightly improve the memory locality in binary search.
227 The _locs array contains locators where the given property change. The
228 block_locators_blocks contains the scope block that is used for all insn
229 locator greater than corresponding block_locators_locs value and smaller
230 than the following one. Similarly for the other properties. */
231 static VEC(int,heap) *block_locators_locs;
232 static GTY(()) VEC(tree,gc) *block_locators_blocks;
233 static VEC(int,heap) *locations_locators_locs;
234 DEF_VEC_O(location_t);
235 DEF_VEC_ALLOC_O(location_t,heap);
236 static VEC(location_t,heap) *locations_locators_vals;
237 int prologue_locator;
238 int epilogue_locator;
240 /* Hold current location information and last location information, so the
241 datastructures are built lazily only when some instructions in given
243 location_t curr_location, last_location;
244 static tree curr_block, last_block;
245 static int curr_rtl_loc = -1;
247 /* Allocate insn locator datastructure. */
249 insn_locators_alloc (void)
251 prologue_locator = epilogue_locator = 0;
253 block_locators_locs = VEC_alloc (int, heap, 32);
254 block_locators_blocks = VEC_alloc (tree, gc, 32);
255 locations_locators_locs = VEC_alloc (int, heap, 32);
256 locations_locators_vals = VEC_alloc (location_t, heap, 32);
265 /* At the end of emit stage, clear current location. */
267 insn_locators_finalize (void)
269 if (curr_rtl_loc >= 0)
270 epilogue_locator = curr_insn_locator ();
274 /* Allocate insn locator datastructure. */
276 insn_locators_free (void)
278 prologue_locator = epilogue_locator = 0;
280 VEC_free (int, heap, block_locators_locs);
281 VEC_free (tree,gc, block_locators_blocks);
282 VEC_free (int, heap, locations_locators_locs);
283 VEC_free (location_t, heap, locations_locators_vals);
287 /* Set current location. */
289 set_curr_insn_source_location (location_t location)
291 /* IV opts calls into RTL expansion to compute costs of operations. At this
292 time locators are not initialized. */
293 if (curr_rtl_loc == -1)
295 if (location == last_location)
297 curr_location = location;
300 /* Set current scope block. */
302 set_curr_insn_block (tree b)
304 /* IV opts calls into RTL expansion to compute costs of operations. At this
305 time locators are not initialized. */
306 if (curr_rtl_loc == -1)
312 /* Return current insn locator. */
314 curr_insn_locator (void)
316 if (curr_rtl_loc == -1)
318 if (last_block != curr_block)
321 VEC_safe_push (int, heap, block_locators_locs, curr_rtl_loc);
322 VEC_safe_push (tree, gc, block_locators_blocks, curr_block);
323 last_block = curr_block;
325 if (last_location != curr_location)
328 VEC_safe_push (int, heap, locations_locators_locs, curr_rtl_loc);
329 VEC_safe_push (location_t, heap, locations_locators_vals, &curr_location);
330 last_location = curr_location;
336 into_cfg_layout_mode (void)
338 cfg_layout_initialize (0);
343 outof_cfg_layout_mode (void)
348 if (bb->next_bb != EXIT_BLOCK_PTR)
349 bb->aux = bb->next_bb;
351 cfg_layout_finalize ();
356 struct rtl_opt_pass pass_into_cfg_layout_mode =
360 "into_cfglayout", /* name */
362 into_cfg_layout_mode, /* execute */
365 0, /* static_pass_number */
367 0, /* properties_required */
368 PROP_cfglayout, /* properties_provided */
369 0, /* properties_destroyed */
370 0, /* todo_flags_start */
371 TODO_dump_func, /* todo_flags_finish */
375 struct rtl_opt_pass pass_outof_cfg_layout_mode =
379 "outof_cfglayout", /* name */
381 outof_cfg_layout_mode, /* execute */
384 0, /* static_pass_number */
386 0, /* properties_required */
387 0, /* properties_provided */
388 PROP_cfglayout, /* properties_destroyed */
389 0, /* todo_flags_start */
390 TODO_dump_func, /* todo_flags_finish */
394 /* Return scope resulting from combination of S1 and S2. */
396 choose_inner_scope (tree s1, tree s2)
402 if (BLOCK_NUMBER (s1) > BLOCK_NUMBER (s2))
407 /* Emit lexical block notes needed to change scope from S1 to S2. */
410 change_scope (rtx orig_insn, tree s1, tree s2)
412 rtx insn = orig_insn;
413 tree com = NULL_TREE;
414 tree ts1 = s1, ts2 = s2;
419 gcc_assert (ts1 && ts2);
420 if (BLOCK_NUMBER (ts1) > BLOCK_NUMBER (ts2))
421 ts1 = BLOCK_SUPERCONTEXT (ts1);
422 else if (BLOCK_NUMBER (ts1) < BLOCK_NUMBER (ts2))
423 ts2 = BLOCK_SUPERCONTEXT (ts2);
426 ts1 = BLOCK_SUPERCONTEXT (ts1);
427 ts2 = BLOCK_SUPERCONTEXT (ts2);
436 rtx note = emit_note_before (NOTE_INSN_BLOCK_END, insn);
437 NOTE_BLOCK (note) = s;
438 s = BLOCK_SUPERCONTEXT (s);
445 insn = emit_note_before (NOTE_INSN_BLOCK_BEG, insn);
446 NOTE_BLOCK (insn) = s;
447 s = BLOCK_SUPERCONTEXT (s);
451 /* Return lexical scope block locator belongs to. */
453 locator_scope (int loc)
455 int max = VEC_length (int, block_locators_locs);
458 /* When block_locators_locs was initialized, the pro- and epilogue
459 insns didn't exist yet and can therefore not be found this way.
460 But we know that they belong to the outer most block of the
462 Without this test, the prologue would be put inside the block of
463 the first valid instruction in the function and when that first
464 insn is part of an inlined function then the low_pc of that
465 inlined function is messed up. Likewise for the epilogue and
466 the last valid instruction. */
467 if (loc == prologue_locator || loc == epilogue_locator)
468 return DECL_INITIAL (cfun->decl);
474 int pos = (min + max) / 2;
475 int tmp = VEC_index (int, block_locators_locs, pos);
477 if (tmp <= loc && min != pos)
479 else if (tmp > loc && max != pos)
487 return VEC_index (tree, block_locators_blocks, min);
490 /* Return lexical scope block insn belongs to. */
492 insn_scope (const_rtx insn)
494 return locator_scope (INSN_LOCATOR (insn));
497 /* Return line number of the statement specified by the locator. */
499 locator_location (int loc)
501 int max = VEC_length (int, locations_locators_locs);
506 int pos = (min + max) / 2;
507 int tmp = VEC_index (int, locations_locators_locs, pos);
509 if (tmp <= loc && min != pos)
511 else if (tmp > loc && max != pos)
519 return *VEC_index (location_t, locations_locators_vals, min);
522 /* Return source line of the statement that produced this insn. */
524 locator_line (int loc)
526 expanded_location xloc;
530 xloc = expand_location (locator_location (loc));
534 /* Return line number of the statement that produced this insn. */
536 insn_line (const_rtx insn)
538 return locator_line (INSN_LOCATOR (insn));
541 /* Return source file of the statement specified by LOC. */
543 locator_file (int loc)
545 expanded_location xloc;
549 xloc = expand_location (locator_location (loc));
553 /* Return source file of the statement that produced this insn. */
555 insn_file (const_rtx insn)
557 return locator_file (INSN_LOCATOR (insn));
560 /* Return true if LOC1 and LOC2 locators have the same location and scope. */
562 locator_eq (int loc1, int loc2)
566 if (locator_location (loc1) != locator_location (loc2))
568 return locator_scope (loc1) == locator_scope (loc2);
571 /* Rebuild all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes based
572 on the scope tree and the newly reordered instructions. */
575 reemit_insn_block_notes (void)
577 tree cur_block = DECL_INITIAL (cfun->decl);
581 if (!active_insn_p (insn))
582 insn = next_active_insn (insn);
583 for (; insn; insn = next_active_insn (insn))
587 /* Avoid putting scope notes between jump table and its label. */
589 && (GET_CODE (PATTERN (insn)) == ADDR_VEC
590 || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC))
593 this_block = insn_scope (insn);
594 /* For sequences compute scope resulting from merging all scopes
595 of instructions nested inside. */
596 if (GET_CODE (PATTERN (insn)) == SEQUENCE)
599 rtx body = PATTERN (insn);
602 for (i = 0; i < XVECLEN (body, 0); i++)
603 this_block = choose_inner_scope (this_block,
604 insn_scope (XVECEXP (body, 0, i)));
609 if (this_block != cur_block)
611 change_scope (insn, cur_block, this_block);
612 cur_block = this_block;
616 /* change_scope emits before the insn, not after. */
617 note = emit_note (NOTE_INSN_DELETED);
618 change_scope (note, cur_block, DECL_INITIAL (cfun->decl));
625 /* Link the basic blocks in the correct order, compacting the basic
626 block queue while at it. This also clears the visited flag on
627 all basic blocks. If STAY_IN_CFGLAYOUT_MODE is false, this function
628 also clears the basic block header and footer fields.
630 This function is usually called after a pass (e.g. tracer) finishes
631 some transformations while in cfglayout mode. The required sequence
632 of the basic blocks is in a linked list along the bb->aux field.
633 This functions re-links the basic block prev_bb and next_bb pointers
634 accordingly, and it compacts and renumbers the blocks. */
637 relink_block_chain (bool stay_in_cfglayout_mode)
639 basic_block bb, prev_bb;
642 /* Maybe dump the re-ordered sequence. */
645 fprintf (dump_file, "Reordered sequence:\n");
646 for (bb = ENTRY_BLOCK_PTR->next_bb, index = NUM_FIXED_BLOCKS;
648 bb = (basic_block) bb->aux, index++)
650 fprintf (dump_file, " %i ", index);
651 if (get_bb_original (bb))
652 fprintf (dump_file, "duplicate of %i ",
653 get_bb_original (bb)->index);
654 else if (forwarder_block_p (bb)
655 && !LABEL_P (BB_HEAD (bb)))
656 fprintf (dump_file, "compensation ");
658 fprintf (dump_file, "bb %i ", bb->index);
659 fprintf (dump_file, " [%i]\n", bb->frequency);
663 /* Now reorder the blocks. */
664 prev_bb = ENTRY_BLOCK_PTR;
665 bb = ENTRY_BLOCK_PTR->next_bb;
666 for (; bb; prev_bb = bb, bb = (basic_block) bb->aux)
668 bb->prev_bb = prev_bb;
669 prev_bb->next_bb = bb;
671 prev_bb->next_bb = EXIT_BLOCK_PTR;
672 EXIT_BLOCK_PTR->prev_bb = prev_bb;
674 /* Then, clean up the aux and visited fields. */
678 bb->il.rtl->visited = 0;
679 if (!stay_in_cfglayout_mode)
680 bb->il.rtl->header = bb->il.rtl->footer = NULL;
683 /* Maybe reset the original copy tables, they are not valid anymore
684 when we renumber the basic blocks in compact_blocks. If we are
685 are going out of cfglayout mode, don't re-allocate the tables. */
686 free_original_copy_tables ();
687 if (stay_in_cfglayout_mode)
688 initialize_original_copy_tables ();
690 /* Finally, put basic_block_info in the new order. */
695 /* Given a reorder chain, rearrange the code to match. */
698 fixup_reorder_chain (void)
703 if (cfg_layout_function_header)
705 set_first_insn (cfg_layout_function_header);
706 insn = cfg_layout_function_header;
707 while (NEXT_INSN (insn))
708 insn = NEXT_INSN (insn);
711 /* First do the bulk reordering -- rechain the blocks without regard to
712 the needed changes to jumps and labels. */
714 for (bb = ENTRY_BLOCK_PTR->next_bb; bb; bb = (basic_block) bb->aux)
716 if (bb->il.rtl->header)
719 NEXT_INSN (insn) = bb->il.rtl->header;
721 set_first_insn (bb->il.rtl->header);
722 PREV_INSN (bb->il.rtl->header) = insn;
723 insn = bb->il.rtl->header;
724 while (NEXT_INSN (insn))
725 insn = NEXT_INSN (insn);
728 NEXT_INSN (insn) = BB_HEAD (bb);
730 set_first_insn (BB_HEAD (bb));
731 PREV_INSN (BB_HEAD (bb)) = insn;
733 if (bb->il.rtl->footer)
735 NEXT_INSN (insn) = bb->il.rtl->footer;
736 PREV_INSN (bb->il.rtl->footer) = insn;
737 while (NEXT_INSN (insn))
738 insn = NEXT_INSN (insn);
742 NEXT_INSN (insn) = cfg_layout_function_footer;
743 if (cfg_layout_function_footer)
744 PREV_INSN (cfg_layout_function_footer) = insn;
746 while (NEXT_INSN (insn))
747 insn = NEXT_INSN (insn);
749 set_last_insn (insn);
750 #ifdef ENABLE_CHECKING
751 verify_insn_chain ();
754 /* Now add jumps and labels as needed to match the blocks new
757 for (bb = ENTRY_BLOCK_PTR->next_bb; bb ; bb = (basic_block) bb->aux)
759 edge e_fall, e_taken, e;
764 if (EDGE_COUNT (bb->succs) == 0)
767 /* Find the old fallthru edge, and another non-EH edge for
769 e_taken = e_fall = NULL;
771 FOR_EACH_EDGE (e, ei, bb->succs)
772 if (e->flags & EDGE_FALLTHRU)
774 else if (! (e->flags & EDGE_EH))
777 bb_end_insn = BB_END (bb);
778 if (JUMP_P (bb_end_insn))
780 if (any_condjump_p (bb_end_insn))
782 /* If the old fallthru is still next, nothing to do. */
783 if (bb->aux == e_fall->dest
784 || e_fall->dest == EXIT_BLOCK_PTR)
787 /* The degenerated case of conditional jump jumping to the next
788 instruction can happen for jumps with side effects. We need
789 to construct a forwarder block and this will be done just
790 fine by force_nonfallthru below. */
794 /* There is another special case: if *neither* block is next,
795 such as happens at the very end of a function, then we'll
796 need to add a new unconditional jump. Choose the taken
797 edge based on known or assumed probability. */
798 else if (bb->aux != e_taken->dest)
800 rtx note = find_reg_note (bb_end_insn, REG_BR_PROB, 0);
803 && INTVAL (XEXP (note, 0)) < REG_BR_PROB_BASE / 2
804 && invert_jump (bb_end_insn,
805 (e_fall->dest == EXIT_BLOCK_PTR
807 : label_for_bb (e_fall->dest)), 0))
809 e_fall->flags &= ~EDGE_FALLTHRU;
810 #ifdef ENABLE_CHECKING
811 gcc_assert (could_fall_through
812 (e_taken->src, e_taken->dest));
814 e_taken->flags |= EDGE_FALLTHRU;
815 update_br_prob_note (bb);
816 e = e_fall, e_fall = e_taken, e_taken = e;
820 /* If the "jumping" edge is a crossing edge, and the fall
821 through edge is non-crossing, leave things as they are. */
822 else if ((e_taken->flags & EDGE_CROSSING)
823 && !(e_fall->flags & EDGE_CROSSING))
826 /* Otherwise we can try to invert the jump. This will
827 basically never fail, however, keep up the pretense. */
828 else if (invert_jump (bb_end_insn,
829 (e_fall->dest == EXIT_BLOCK_PTR
831 : label_for_bb (e_fall->dest)), 0))
833 e_fall->flags &= ~EDGE_FALLTHRU;
834 #ifdef ENABLE_CHECKING
835 gcc_assert (could_fall_through
836 (e_taken->src, e_taken->dest));
838 e_taken->flags |= EDGE_FALLTHRU;
839 update_br_prob_note (bb);
845 /* Otherwise we have some return, switch or computed
846 jump. In the 99% case, there should not have been a
848 gcc_assert (returnjump_p (bb_end_insn) || !e_fall);
854 /* No fallthru implies a noreturn function with EH edges, or
855 something similarly bizarre. In any case, we don't need to
860 /* If the fallthru block is still next, nothing to do. */
861 if (bb->aux == e_fall->dest)
864 /* A fallthru to exit block. */
865 if (e_fall->dest == EXIT_BLOCK_PTR)
869 /* We got here if we need to add a new jump insn. */
870 nb = force_nonfallthru (e_fall);
873 nb->il.rtl->visited = 1;
876 /* Don't process this new block. */
879 /* Make sure new bb is tagged for correct section (same as
880 fall-thru source, since you cannot fall-throu across
881 section boundaries). */
882 BB_COPY_PARTITION (e_fall->src, single_pred (bb));
883 if (flag_reorder_blocks_and_partition
884 && targetm.have_named_sections
885 && JUMP_P (BB_END (bb))
886 && !any_condjump_p (BB_END (bb))
887 && (EDGE_SUCC (bb, 0)->flags & EDGE_CROSSING))
888 add_reg_note (BB_END (bb), REG_CROSSING_JUMP, NULL_RTX);
892 relink_block_chain (/*stay_in_cfglayout_mode=*/false);
894 /* Annoying special case - jump around dead jumptables left in the code. */
900 FOR_EACH_EDGE (e, ei, bb->succs)
901 if (e->flags & EDGE_FALLTHRU)
904 if (e && !can_fallthru (e->src, e->dest))
905 force_nonfallthru (e);
908 /* Ensure goto_locus from edges has some instructions with that locus
916 FOR_EACH_EDGE (e, ei, bb->succs)
917 if (e->goto_locus && !(e->flags & EDGE_ABNORMAL))
922 insn = BB_END (e->src);
923 end = PREV_INSN (BB_HEAD (e->src));
925 && (!INSN_P (insn) || INSN_LOCATOR (insn) == 0))
926 insn = PREV_INSN (insn);
928 && locator_eq (INSN_LOCATOR (insn), (int) e->goto_locus))
930 if (simplejump_p (BB_END (e->src))
931 && INSN_LOCATOR (BB_END (e->src)) == 0)
933 INSN_LOCATOR (BB_END (e->src)) = e->goto_locus;
936 if (e->dest != EXIT_BLOCK_PTR)
938 insn = BB_HEAD (e->dest);
939 end = NEXT_INSN (BB_END (e->dest));
940 while (insn != end && !INSN_P (insn))
941 insn = NEXT_INSN (insn);
942 if (insn != end && INSN_LOCATOR (insn)
943 && locator_eq (INSN_LOCATOR (insn), (int) e->goto_locus))
947 if (!INSN_P (BB_END (nb)))
948 BB_END (nb) = emit_insn_after_noloc (gen_nop (), BB_END (nb),
950 INSN_LOCATOR (BB_END (nb)) = e->goto_locus;
955 /* Perform sanity checks on the insn chain.
956 1. Check that next/prev pointers are consistent in both the forward and
958 2. Count insns in chain, going both directions, and check if equal.
959 3. Check that get_last_insn () returns the actual end of chain. */
962 verify_insn_chain (void)
965 int insn_cnt1, insn_cnt2;
967 for (prevx = NULL, insn_cnt1 = 1, x = get_insns ();
969 prevx = x, insn_cnt1++, x = NEXT_INSN (x))
970 gcc_assert (PREV_INSN (x) == prevx);
972 gcc_assert (prevx == get_last_insn ());
974 for (nextx = NULL, insn_cnt2 = 1, x = get_last_insn ();
976 nextx = x, insn_cnt2++, x = PREV_INSN (x))
977 gcc_assert (NEXT_INSN (x) == nextx);
979 gcc_assert (insn_cnt1 == insn_cnt2);
982 /* If we have assembler epilogues, the block falling through to exit must
983 be the last one in the reordered chain when we reach final. Ensure
984 that this condition is met. */
986 fixup_fallthru_exit_predecessor (void)
990 basic_block bb = NULL;
992 /* This transformation is not valid before reload, because we might
993 separate a call from the instruction that copies the return
995 gcc_assert (reload_completed);
997 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
998 if (e->flags & EDGE_FALLTHRU)
1003 basic_block c = ENTRY_BLOCK_PTR->next_bb;
1005 /* If the very first block is the one with the fall-through exit
1006 edge, we have to split that block. */
1009 bb = split_block (bb, NULL)->dest;
1012 bb->il.rtl->footer = c->il.rtl->footer;
1013 c->il.rtl->footer = NULL;
1016 while (c->aux != bb)
1017 c = (basic_block) c->aux;
1021 c = (basic_block) c->aux;
1028 /* In case there are more than one fallthru predecessors of exit, force that
1029 there is only one. */
1032 force_one_exit_fallthru (void)
1034 edge e, predecessor = NULL;
1037 basic_block forwarder, bb;
1039 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
1040 if (e->flags & EDGE_FALLTHRU)
1042 if (predecessor == NULL)
1054 /* Exit has several fallthru predecessors. Create a forwarder block for
1056 forwarder = split_edge (predecessor);
1057 for (ei = ei_start (EXIT_BLOCK_PTR->preds); (e = ei_safe_edge (ei)); )
1059 if (e->src == forwarder
1060 || !(e->flags & EDGE_FALLTHRU))
1063 redirect_edge_and_branch_force (e, forwarder);
1066 /* Fix up the chain of blocks -- make FORWARDER immediately precede the
1070 if (bb->aux == NULL && bb != forwarder)
1072 bb->aux = forwarder;
1078 /* Return true in case it is possible to duplicate the basic block BB. */
1080 /* We do not want to declare the function in a header file, since it should
1081 only be used through the cfghooks interface, and we do not want to move
1082 it to cfgrtl.c since it would require also moving quite a lot of related
1084 extern bool cfg_layout_can_duplicate_bb_p (const_basic_block);
1087 cfg_layout_can_duplicate_bb_p (const_basic_block bb)
1089 /* Do not attempt to duplicate tablejumps, as we need to unshare
1090 the dispatch table. This is difficult to do, as the instructions
1091 computing jump destination may be hoisted outside the basic block. */
1092 if (tablejump_p (BB_END (bb), NULL, NULL))
1095 /* Do not duplicate blocks containing insns that can't be copied. */
1096 if (targetm.cannot_copy_insn_p)
1098 rtx insn = BB_HEAD (bb);
1101 if (INSN_P (insn) && targetm.cannot_copy_insn_p (insn))
1103 if (insn == BB_END (bb))
1105 insn = NEXT_INSN (insn);
1113 duplicate_insn_chain (rtx from, rtx to)
1115 rtx insn, last, copy;
1117 /* Avoid updating of boundaries of previous basic block. The
1118 note will get removed from insn stream in fixup. */
1119 last = emit_note (NOTE_INSN_DELETED);
1121 /* Create copy at the end of INSN chain. The chain will
1122 be reordered later. */
1123 for (insn = from; insn != NEXT_INSN (to); insn = NEXT_INSN (insn))
1125 switch (GET_CODE (insn))
1130 /* Avoid copying of dispatch tables. We never duplicate
1131 tablejumps, so this can hit only in case the table got
1132 moved far from original jump. */
1133 if (GET_CODE (PATTERN (insn)) == ADDR_VEC
1134 || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
1136 copy = emit_copy_of_insn_after (insn, get_last_insn ());
1137 maybe_copy_epilogue_insn (insn, copy);
1148 switch (NOTE_KIND (insn))
1150 /* In case prologue is empty and function contain label
1151 in first BB, we may want to copy the block. */
1152 case NOTE_INSN_PROLOGUE_END:
1154 case NOTE_INSN_DELETED:
1155 case NOTE_INSN_DELETED_LABEL:
1156 /* No problem to strip these. */
1157 case NOTE_INSN_FUNCTION_BEG:
1158 /* There is always just single entry to function. */
1159 case NOTE_INSN_BASIC_BLOCK:
1162 case NOTE_INSN_EPILOGUE_BEG:
1163 case NOTE_INSN_SWITCH_TEXT_SECTIONS:
1164 emit_note_copy (insn);
1168 /* All other notes should have already been eliminated. */
1176 insn = NEXT_INSN (last);
1180 /* Create a duplicate of the basic block BB. */
1182 /* We do not want to declare the function in a header file, since it should
1183 only be used through the cfghooks interface, and we do not want to move
1184 it to cfgrtl.c since it would require also moving quite a lot of related
1186 extern basic_block cfg_layout_duplicate_bb (basic_block);
1189 cfg_layout_duplicate_bb (basic_block bb)
1194 insn = duplicate_insn_chain (BB_HEAD (bb), BB_END (bb));
1195 new_bb = create_basic_block (insn,
1196 insn ? get_last_insn () : NULL,
1197 EXIT_BLOCK_PTR->prev_bb);
1199 BB_COPY_PARTITION (new_bb, bb);
1200 if (bb->il.rtl->header)
1202 insn = bb->il.rtl->header;
1203 while (NEXT_INSN (insn))
1204 insn = NEXT_INSN (insn);
1205 insn = duplicate_insn_chain (bb->il.rtl->header, insn);
1207 new_bb->il.rtl->header = unlink_insn_chain (insn, get_last_insn ());
1210 if (bb->il.rtl->footer)
1212 insn = bb->il.rtl->footer;
1213 while (NEXT_INSN (insn))
1214 insn = NEXT_INSN (insn);
1215 insn = duplicate_insn_chain (bb->il.rtl->footer, insn);
1217 new_bb->il.rtl->footer = unlink_insn_chain (insn, get_last_insn ());
1224 /* Main entry point to this module - initialize the datastructures for
1225 CFG layout changes. It keeps LOOPS up-to-date if not null.
1227 FLAGS is a set of additional flags to pass to cleanup_cfg(). */
1230 cfg_layout_initialize (unsigned int flags)
1235 initialize_original_copy_tables ();
1237 cfg_layout_rtl_register_cfg_hooks ();
1239 record_effective_endpoints ();
1241 /* Make sure that the targets of non local gotos are marked. */
1242 for (x = nonlocal_goto_handler_labels; x; x = XEXP (x, 1))
1244 bb = BLOCK_FOR_INSN (XEXP (x, 0));
1245 bb->flags |= BB_NON_LOCAL_GOTO_TARGET;
1248 cleanup_cfg (CLEANUP_CFGLAYOUT | flags);
1251 /* Splits superblocks. */
1253 break_superblocks (void)
1255 sbitmap superblocks;
1259 superblocks = sbitmap_alloc (last_basic_block);
1260 sbitmap_zero (superblocks);
1263 if (bb->flags & BB_SUPERBLOCK)
1265 bb->flags &= ~BB_SUPERBLOCK;
1266 SET_BIT (superblocks, bb->index);
1272 rebuild_jump_labels (get_insns ());
1273 find_many_sub_basic_blocks (superblocks);
1279 /* Finalize the changes: reorder insn list according to the sequence specified
1280 by aux pointers, enter compensation code, rebuild scope forest. */
1283 cfg_layout_finalize (void)
1285 #ifdef ENABLE_CHECKING
1286 verify_flow_info ();
1288 force_one_exit_fallthru ();
1289 rtl_register_cfg_hooks ();
1290 if (reload_completed
1291 #ifdef HAVE_epilogue
1295 fixup_fallthru_exit_predecessor ();
1296 fixup_reorder_chain ();
1298 rebuild_jump_labels (get_insns ());
1299 delete_dead_jumptables ();
1301 #ifdef ENABLE_CHECKING
1302 verify_insn_chain ();
1303 verify_flow_info ();
1307 /* Checks whether all N blocks in BBS array can be copied. */
1309 can_copy_bbs_p (basic_block *bbs, unsigned n)
1315 for (i = 0; i < n; i++)
1316 bbs[i]->flags |= BB_DUPLICATED;
1318 for (i = 0; i < n; i++)
1320 /* In case we should redirect abnormal edge during duplication, fail. */
1322 FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1323 if ((e->flags & EDGE_ABNORMAL)
1324 && (e->dest->flags & BB_DUPLICATED))
1330 if (!can_duplicate_block_p (bbs[i]))
1338 for (i = 0; i < n; i++)
1339 bbs[i]->flags &= ~BB_DUPLICATED;
1344 /* Duplicates N basic blocks stored in array BBS. Newly created basic blocks
1345 are placed into array NEW_BBS in the same order. Edges from basic blocks
1346 in BBS are also duplicated and copies of those of them
1347 that lead into BBS are redirected to appropriate newly created block. The
1348 function assigns bbs into loops (copy of basic block bb is assigned to
1349 bb->loop_father->copy loop, so this must be set up correctly in advance)
1350 and updates dominators locally (LOOPS structure that contains the information
1351 about dominators is passed to enable this).
1353 BASE is the superloop to that basic block belongs; if its header or latch
1354 is copied, we do not set the new blocks as header or latch.
1356 Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
1357 also in the same order.
1359 Newly created basic blocks are put after the basic block AFTER in the
1360 instruction stream, and the order of the blocks in BBS array is preserved. */
1363 copy_bbs (basic_block *bbs, unsigned n, basic_block *new_bbs,
1364 edge *edges, unsigned num_edges, edge *new_edges,
1365 struct loop *base, basic_block after)
1368 basic_block bb, new_bb, dom_bb;
1371 /* Duplicate bbs, update dominators, assign bbs to loops. */
1372 for (i = 0; i < n; i++)
1376 new_bb = new_bbs[i] = duplicate_block (bb, NULL, after);
1378 bb->flags |= BB_DUPLICATED;
1379 /* Possibly set loop header. */
1380 if (bb->loop_father->header == bb && bb->loop_father != base)
1381 new_bb->loop_father->header = new_bb;
1383 if (bb->loop_father->latch == bb && bb->loop_father != base)
1384 new_bb->loop_father->latch = new_bb;
1387 /* Set dominators. */
1388 for (i = 0; i < n; i++)
1391 new_bb = new_bbs[i];
1393 dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
1394 if (dom_bb->flags & BB_DUPLICATED)
1396 dom_bb = get_bb_copy (dom_bb);
1397 set_immediate_dominator (CDI_DOMINATORS, new_bb, dom_bb);
1401 /* Redirect edges. */
1402 for (j = 0; j < num_edges; j++)
1403 new_edges[j] = NULL;
1404 for (i = 0; i < n; i++)
1407 new_bb = new_bbs[i];
1410 FOR_EACH_EDGE (e, ei, new_bb->succs)
1412 for (j = 0; j < num_edges; j++)
1413 if (edges[j] && edges[j]->src == bb && edges[j]->dest == e->dest)
1416 if (!(e->dest->flags & BB_DUPLICATED))
1418 redirect_edge_and_branch_force (e, get_bb_copy (e->dest));
1422 /* Clear information about duplicates. */
1423 for (i = 0; i < n; i++)
1424 bbs[i]->flags &= ~BB_DUPLICATED;
1427 #include "gt-cfglayout.h"