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_TABLE_DATA_P (NEXT_INSN (insn)))
117 insn = NEXT_INSN (insn);
130 /* It is possible to hit contradictory sequence. For instance:
136 Where barrier belongs to jump_insn, but the note does not. This can be
137 created by removing the basic block originally following
138 NOTE_INSN_BLOCK_BEG. In such case reorder the notes. */
140 for (insn = last_insn; insn != BB_END (bb); insn = prev)
142 prev = PREV_INSN (insn);
144 switch (NOTE_KIND (insn))
146 case NOTE_INSN_BLOCK_END:
149 case NOTE_INSN_DELETED:
150 case NOTE_INSN_DELETED_LABEL:
153 reorder_insns (insn, insn, last_insn);
160 /* Locate or create a label for a given basic block. */
163 label_for_bb (basic_block bb)
165 rtx label = BB_HEAD (bb);
167 if (!LABEL_P (label))
170 fprintf (dump_file, "Emitting label for block %d\n", bb->index);
172 label = block_label (bb);
178 /* Locate the effective beginning and end of the insn chain for each
179 block, as defined by skip_insns_after_block above. */
182 record_effective_endpoints (void)
188 for (insn = get_insns ();
191 && NOTE_KIND (insn) != NOTE_INSN_BASIC_BLOCK;
192 insn = NEXT_INSN (insn))
194 /* No basic blocks at all? */
197 if (PREV_INSN (insn))
198 cfg_layout_function_header =
199 unlink_insn_chain (get_insns (), PREV_INSN (insn));
201 cfg_layout_function_header = NULL_RTX;
203 next_insn = get_insns ();
208 if (PREV_INSN (BB_HEAD (bb)) && next_insn != BB_HEAD (bb))
209 bb->il.rtl->header = unlink_insn_chain (next_insn,
210 PREV_INSN (BB_HEAD (bb)));
211 end = skip_insns_after_block (bb);
212 if (NEXT_INSN (BB_END (bb)) && BB_END (bb) != end)
213 bb->il.rtl->footer = unlink_insn_chain (NEXT_INSN (BB_END (bb)), end);
214 next_insn = NEXT_INSN (BB_END (bb));
217 cfg_layout_function_footer = next_insn;
218 if (cfg_layout_function_footer)
219 cfg_layout_function_footer = unlink_insn_chain (cfg_layout_function_footer, get_last_insn ());
222 /* Data structures representing mapping of INSN_LOCATOR into scope blocks, line
223 numbers and files. In order to be GGC friendly we need to use separate
224 varrays. This also slightly improve the memory locality in binary search.
225 The _locs array contains locators where the given property change. The
226 block_locators_blocks contains the scope block that is used for all insn
227 locator greater than corresponding block_locators_locs value and smaller
228 than the following one. Similarly for the other properties. */
229 static VEC(int,heap) *block_locators_locs;
230 static GTY(()) VEC(tree,gc) *block_locators_blocks;
231 static VEC(int,heap) *locations_locators_locs;
232 DEF_VEC_O(location_t);
233 DEF_VEC_ALLOC_O(location_t,heap);
234 static VEC(location_t,heap) *locations_locators_vals;
235 int prologue_locator;
236 int epilogue_locator;
238 /* Hold current location information and last location information, so the
239 datastructures are built lazily only when some instructions in given
241 static location_t curr_location, last_location;
242 static tree curr_block, last_block;
243 static int curr_rtl_loc = -1;
245 /* Allocate insn locator datastructure. */
247 insn_locators_alloc (void)
249 prologue_locator = epilogue_locator = 0;
251 block_locators_locs = VEC_alloc (int, heap, 32);
252 block_locators_blocks = VEC_alloc (tree, gc, 32);
253 locations_locators_locs = VEC_alloc (int, heap, 32);
254 locations_locators_vals = VEC_alloc (location_t, heap, 32);
263 /* At the end of emit stage, clear current location. */
265 insn_locators_finalize (void)
267 if (curr_rtl_loc >= 0)
268 epilogue_locator = curr_insn_locator ();
272 /* Allocate insn locator datastructure. */
274 insn_locators_free (void)
276 prologue_locator = epilogue_locator = 0;
278 VEC_free (int, heap, block_locators_locs);
279 VEC_free (tree,gc, block_locators_blocks);
280 VEC_free (int, heap, locations_locators_locs);
281 VEC_free (location_t, heap, locations_locators_vals);
285 /* Set current location. */
287 set_curr_insn_source_location (location_t location)
289 /* IV opts calls into RTL expansion to compute costs of operations. At this
290 time locators are not initialized. */
291 if (curr_rtl_loc == -1)
293 curr_location = location;
296 /* Get current location. */
298 get_curr_insn_source_location (void)
300 return curr_location;
303 /* Set current scope block. */
305 set_curr_insn_block (tree b)
307 /* IV opts calls into RTL expansion to compute costs of operations. At this
308 time locators are not initialized. */
309 if (curr_rtl_loc == -1)
315 /* Get current scope block. */
317 get_curr_insn_block (void)
322 /* Return current insn locator. */
324 curr_insn_locator (void)
326 if (curr_rtl_loc == -1)
328 if (last_block != curr_block)
331 VEC_safe_push (int, heap, block_locators_locs, curr_rtl_loc);
332 VEC_safe_push (tree, gc, block_locators_blocks, curr_block);
333 last_block = curr_block;
335 if (last_location != curr_location)
338 VEC_safe_push (int, heap, locations_locators_locs, curr_rtl_loc);
339 VEC_safe_push (location_t, heap, locations_locators_vals, &curr_location);
340 last_location = curr_location;
346 into_cfg_layout_mode (void)
348 cfg_layout_initialize (0);
353 outof_cfg_layout_mode (void)
358 if (bb->next_bb != EXIT_BLOCK_PTR)
359 bb->aux = bb->next_bb;
361 cfg_layout_finalize ();
366 struct rtl_opt_pass pass_into_cfg_layout_mode =
370 "into_cfglayout", /* name */
372 into_cfg_layout_mode, /* execute */
375 0, /* static_pass_number */
377 0, /* properties_required */
378 PROP_cfglayout, /* properties_provided */
379 0, /* properties_destroyed */
380 0, /* todo_flags_start */
381 TODO_dump_func, /* todo_flags_finish */
385 struct rtl_opt_pass pass_outof_cfg_layout_mode =
389 "outof_cfglayout", /* name */
391 outof_cfg_layout_mode, /* execute */
394 0, /* static_pass_number */
396 0, /* properties_required */
397 0, /* properties_provided */
398 PROP_cfglayout, /* properties_destroyed */
399 0, /* todo_flags_start */
400 TODO_dump_func, /* todo_flags_finish */
404 /* Return scope resulting from combination of S1 and S2. */
406 choose_inner_scope (tree s1, tree s2)
412 if (BLOCK_NUMBER (s1) > BLOCK_NUMBER (s2))
417 /* Emit lexical block notes needed to change scope from S1 to S2. */
420 change_scope (rtx orig_insn, tree s1, tree s2)
422 rtx insn = orig_insn;
423 tree com = NULL_TREE;
424 tree ts1 = s1, ts2 = s2;
429 gcc_assert (ts1 && ts2);
430 if (BLOCK_NUMBER (ts1) > BLOCK_NUMBER (ts2))
431 ts1 = BLOCK_SUPERCONTEXT (ts1);
432 else if (BLOCK_NUMBER (ts1) < BLOCK_NUMBER (ts2))
433 ts2 = BLOCK_SUPERCONTEXT (ts2);
436 ts1 = BLOCK_SUPERCONTEXT (ts1);
437 ts2 = BLOCK_SUPERCONTEXT (ts2);
446 rtx note = emit_note_before (NOTE_INSN_BLOCK_END, insn);
447 NOTE_BLOCK (note) = s;
448 s = BLOCK_SUPERCONTEXT (s);
455 insn = emit_note_before (NOTE_INSN_BLOCK_BEG, insn);
456 NOTE_BLOCK (insn) = s;
457 s = BLOCK_SUPERCONTEXT (s);
461 /* Return lexical scope block locator belongs to. */
463 locator_scope (int loc)
465 int max = VEC_length (int, block_locators_locs);
468 /* When block_locators_locs was initialized, the pro- and epilogue
469 insns didn't exist yet and can therefore not be found this way.
470 But we know that they belong to the outer most block of the
472 Without this test, the prologue would be put inside the block of
473 the first valid instruction in the function and when that first
474 insn is part of an inlined function then the low_pc of that
475 inlined function is messed up. Likewise for the epilogue and
476 the last valid instruction. */
477 if (loc == prologue_locator || loc == epilogue_locator)
478 return DECL_INITIAL (cfun->decl);
484 int pos = (min + max) / 2;
485 int tmp = VEC_index (int, block_locators_locs, pos);
487 if (tmp <= loc && min != pos)
489 else if (tmp > loc && max != pos)
497 return VEC_index (tree, block_locators_blocks, min);
500 /* Return lexical scope block insn belongs to. */
502 insn_scope (const_rtx insn)
504 return locator_scope (INSN_LOCATOR (insn));
507 /* Return line number of the statement specified by the locator. */
509 locator_location (int loc)
511 int max = VEC_length (int, locations_locators_locs);
516 int pos = (min + max) / 2;
517 int tmp = VEC_index (int, locations_locators_locs, pos);
519 if (tmp <= loc && min != pos)
521 else if (tmp > loc && max != pos)
529 return *VEC_index (location_t, locations_locators_vals, min);
532 /* Return source line of the statement that produced this insn. */
534 locator_line (int loc)
536 expanded_location xloc;
540 xloc = expand_location (locator_location (loc));
544 /* Return line number of the statement that produced this insn. */
546 insn_line (const_rtx insn)
548 return locator_line (INSN_LOCATOR (insn));
551 /* Return source file of the statement specified by LOC. */
553 locator_file (int loc)
555 expanded_location xloc;
559 xloc = expand_location (locator_location (loc));
563 /* Return source file of the statement that produced this insn. */
565 insn_file (const_rtx insn)
567 return locator_file (INSN_LOCATOR (insn));
570 /* Return true if LOC1 and LOC2 locators have the same location and scope. */
572 locator_eq (int loc1, int loc2)
576 if (locator_location (loc1) != locator_location (loc2))
578 return locator_scope (loc1) == locator_scope (loc2);
581 /* Rebuild all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes based
582 on the scope tree and the newly reordered instructions. */
585 reemit_insn_block_notes (void)
587 tree cur_block = DECL_INITIAL (cfun->decl);
591 if (!active_insn_p (insn))
592 insn = next_active_insn (insn);
593 for (; insn; insn = next_active_insn (insn))
597 /* Avoid putting scope notes between jump table and its label. */
598 if (JUMP_TABLE_DATA_P (insn))
601 this_block = insn_scope (insn);
602 /* For sequences compute scope resulting from merging all scopes
603 of instructions nested inside. */
604 if (GET_CODE (PATTERN (insn)) == SEQUENCE)
607 rtx body = PATTERN (insn);
610 for (i = 0; i < XVECLEN (body, 0); i++)
611 this_block = choose_inner_scope (this_block,
612 insn_scope (XVECEXP (body, 0, i)));
617 if (this_block != cur_block)
619 change_scope (insn, cur_block, this_block);
620 cur_block = this_block;
624 /* change_scope emits before the insn, not after. */
625 note = emit_note (NOTE_INSN_DELETED);
626 change_scope (note, cur_block, DECL_INITIAL (cfun->decl));
633 /* Link the basic blocks in the correct order, compacting the basic
634 block queue while at it. This also clears the visited flag on
635 all basic blocks. If STAY_IN_CFGLAYOUT_MODE is false, this function
636 also clears the basic block header and footer fields.
638 This function is usually called after a pass (e.g. tracer) finishes
639 some transformations while in cfglayout mode. The required sequence
640 of the basic blocks is in a linked list along the bb->aux field.
641 This functions re-links the basic block prev_bb and next_bb pointers
642 accordingly, and it compacts and renumbers the blocks. */
645 relink_block_chain (bool stay_in_cfglayout_mode)
647 basic_block bb, prev_bb;
650 /* Maybe dump the re-ordered sequence. */
653 fprintf (dump_file, "Reordered sequence:\n");
654 for (bb = ENTRY_BLOCK_PTR->next_bb, index = NUM_FIXED_BLOCKS;
656 bb = (basic_block) bb->aux, index++)
658 fprintf (dump_file, " %i ", index);
659 if (get_bb_original (bb))
660 fprintf (dump_file, "duplicate of %i ",
661 get_bb_original (bb)->index);
662 else if (forwarder_block_p (bb)
663 && !LABEL_P (BB_HEAD (bb)))
664 fprintf (dump_file, "compensation ");
666 fprintf (dump_file, "bb %i ", bb->index);
667 fprintf (dump_file, " [%i]\n", bb->frequency);
671 /* Now reorder the blocks. */
672 prev_bb = ENTRY_BLOCK_PTR;
673 bb = ENTRY_BLOCK_PTR->next_bb;
674 for (; bb; prev_bb = bb, bb = (basic_block) bb->aux)
676 bb->prev_bb = prev_bb;
677 prev_bb->next_bb = bb;
679 prev_bb->next_bb = EXIT_BLOCK_PTR;
680 EXIT_BLOCK_PTR->prev_bb = prev_bb;
682 /* Then, clean up the aux and visited fields. */
686 bb->il.rtl->visited = 0;
687 if (!stay_in_cfglayout_mode)
688 bb->il.rtl->header = bb->il.rtl->footer = NULL;
691 /* Maybe reset the original copy tables, they are not valid anymore
692 when we renumber the basic blocks in compact_blocks. If we are
693 are going out of cfglayout mode, don't re-allocate the tables. */
694 free_original_copy_tables ();
695 if (stay_in_cfglayout_mode)
696 initialize_original_copy_tables ();
698 /* Finally, put basic_block_info in the new order. */
703 /* Given a reorder chain, rearrange the code to match. */
706 fixup_reorder_chain (void)
711 if (cfg_layout_function_header)
713 set_first_insn (cfg_layout_function_header);
714 insn = cfg_layout_function_header;
715 while (NEXT_INSN (insn))
716 insn = NEXT_INSN (insn);
719 /* First do the bulk reordering -- rechain the blocks without regard to
720 the needed changes to jumps and labels. */
722 for (bb = ENTRY_BLOCK_PTR->next_bb; bb; bb = (basic_block) bb->aux)
724 if (bb->il.rtl->header)
727 NEXT_INSN (insn) = bb->il.rtl->header;
729 set_first_insn (bb->il.rtl->header);
730 PREV_INSN (bb->il.rtl->header) = insn;
731 insn = bb->il.rtl->header;
732 while (NEXT_INSN (insn))
733 insn = NEXT_INSN (insn);
736 NEXT_INSN (insn) = BB_HEAD (bb);
738 set_first_insn (BB_HEAD (bb));
739 PREV_INSN (BB_HEAD (bb)) = insn;
741 if (bb->il.rtl->footer)
743 NEXT_INSN (insn) = bb->il.rtl->footer;
744 PREV_INSN (bb->il.rtl->footer) = insn;
745 while (NEXT_INSN (insn))
746 insn = NEXT_INSN (insn);
750 NEXT_INSN (insn) = cfg_layout_function_footer;
751 if (cfg_layout_function_footer)
752 PREV_INSN (cfg_layout_function_footer) = insn;
754 while (NEXT_INSN (insn))
755 insn = NEXT_INSN (insn);
757 set_last_insn (insn);
758 #ifdef ENABLE_CHECKING
759 verify_insn_chain ();
762 /* Now add jumps and labels as needed to match the blocks new
765 for (bb = ENTRY_BLOCK_PTR->next_bb; bb ; bb = (basic_block) bb->aux)
767 edge e_fall, e_taken, e;
772 if (EDGE_COUNT (bb->succs) == 0)
775 /* Find the old fallthru edge, and another non-EH edge for
777 e_taken = e_fall = NULL;
779 FOR_EACH_EDGE (e, ei, bb->succs)
780 if (e->flags & EDGE_FALLTHRU)
782 else if (! (e->flags & EDGE_EH))
785 bb_end_insn = BB_END (bb);
786 if (JUMP_P (bb_end_insn))
788 if (any_condjump_p (bb_end_insn))
790 /* If the old fallthru is still next, nothing to do. */
791 if (bb->aux == e_fall->dest
792 || e_fall->dest == EXIT_BLOCK_PTR)
795 /* The degenerated case of conditional jump jumping to the next
796 instruction can happen for jumps with side effects. We need
797 to construct a forwarder block and this will be done just
798 fine by force_nonfallthru below. */
802 /* There is another special case: if *neither* block is next,
803 such as happens at the very end of a function, then we'll
804 need to add a new unconditional jump. Choose the taken
805 edge based on known or assumed probability. */
806 else if (bb->aux != e_taken->dest)
808 rtx note = find_reg_note (bb_end_insn, REG_BR_PROB, 0);
811 && INTVAL (XEXP (note, 0)) < REG_BR_PROB_BASE / 2
812 && invert_jump (bb_end_insn,
813 (e_fall->dest == EXIT_BLOCK_PTR
815 : label_for_bb (e_fall->dest)), 0))
817 e_fall->flags &= ~EDGE_FALLTHRU;
818 #ifdef ENABLE_CHECKING
819 gcc_assert (could_fall_through
820 (e_taken->src, e_taken->dest));
822 e_taken->flags |= EDGE_FALLTHRU;
823 update_br_prob_note (bb);
824 e = e_fall, e_fall = e_taken, e_taken = e;
828 /* If the "jumping" edge is a crossing edge, and the fall
829 through edge is non-crossing, leave things as they are. */
830 else if ((e_taken->flags & EDGE_CROSSING)
831 && !(e_fall->flags & EDGE_CROSSING))
834 /* Otherwise we can try to invert the jump. This will
835 basically never fail, however, keep up the pretense. */
836 else if (invert_jump (bb_end_insn,
837 (e_fall->dest == EXIT_BLOCK_PTR
839 : label_for_bb (e_fall->dest)), 0))
841 e_fall->flags &= ~EDGE_FALLTHRU;
842 #ifdef ENABLE_CHECKING
843 gcc_assert (could_fall_through
844 (e_taken->src, e_taken->dest));
846 e_taken->flags |= EDGE_FALLTHRU;
847 update_br_prob_note (bb);
851 else if (extract_asm_operands (PATTERN (bb_end_insn)) != NULL)
853 /* If the old fallthru is still next, nothing to do. */
854 if (bb->aux == e_fall->dest
855 || e_fall->dest == EXIT_BLOCK_PTR)
858 /* Otherwise we'll have to use the fallthru fixup below. */
862 /* Otherwise we have some return, switch or computed
863 jump. In the 99% case, there should not have been a
865 gcc_assert (returnjump_p (bb_end_insn) || !e_fall);
871 /* No fallthru implies a noreturn function with EH edges, or
872 something similarly bizarre. In any case, we don't need to
877 /* If the fallthru block is still next, nothing to do. */
878 if (bb->aux == e_fall->dest)
881 /* A fallthru to exit block. */
882 if (e_fall->dest == EXIT_BLOCK_PTR)
886 /* We got here if we need to add a new jump insn. */
887 nb = force_nonfallthru (e_fall);
890 nb->il.rtl->visited = 1;
893 /* Don't process this new block. */
896 /* Make sure new bb is tagged for correct section (same as
897 fall-thru source, since you cannot fall-throu across
898 section boundaries). */
899 BB_COPY_PARTITION (e_fall->src, single_pred (bb));
900 if (flag_reorder_blocks_and_partition
901 && targetm.have_named_sections
902 && JUMP_P (BB_END (bb))
903 && !any_condjump_p (BB_END (bb))
904 && (EDGE_SUCC (bb, 0)->flags & EDGE_CROSSING))
905 add_reg_note (BB_END (bb), REG_CROSSING_JUMP, NULL_RTX);
909 relink_block_chain (/*stay_in_cfglayout_mode=*/false);
911 /* Annoying special case - jump around dead jumptables left in the code. */
917 FOR_EACH_EDGE (e, ei, bb->succs)
918 if (e->flags & EDGE_FALLTHRU)
921 if (e && !can_fallthru (e->src, e->dest))
922 force_nonfallthru (e);
925 /* Ensure goto_locus from edges has some instructions with that locus
933 FOR_EACH_EDGE (e, ei, bb->succs)
934 if (e->goto_locus && !(e->flags & EDGE_ABNORMAL))
939 insn = BB_END (e->src);
940 end = PREV_INSN (BB_HEAD (e->src));
942 && (!INSN_P (insn) || INSN_LOCATOR (insn) == 0))
943 insn = PREV_INSN (insn);
945 && locator_eq (INSN_LOCATOR (insn), (int) e->goto_locus))
947 if (simplejump_p (BB_END (e->src))
948 && INSN_LOCATOR (BB_END (e->src)) == 0)
950 INSN_LOCATOR (BB_END (e->src)) = e->goto_locus;
953 if (e->dest != EXIT_BLOCK_PTR)
955 insn = BB_HEAD (e->dest);
956 end = NEXT_INSN (BB_END (e->dest));
957 while (insn != end && !INSN_P (insn))
958 insn = NEXT_INSN (insn);
959 if (insn != end && INSN_LOCATOR (insn)
960 && locator_eq (INSN_LOCATOR (insn), (int) e->goto_locus))
964 if (!INSN_P (BB_END (nb)))
965 BB_END (nb) = emit_insn_after_noloc (gen_nop (), BB_END (nb),
967 INSN_LOCATOR (BB_END (nb)) = e->goto_locus;
972 /* Perform sanity checks on the insn chain.
973 1. Check that next/prev pointers are consistent in both the forward and
975 2. Count insns in chain, going both directions, and check if equal.
976 3. Check that get_last_insn () returns the actual end of chain. */
979 verify_insn_chain (void)
982 int insn_cnt1, insn_cnt2;
984 for (prevx = NULL, insn_cnt1 = 1, x = get_insns ();
986 prevx = x, insn_cnt1++, x = NEXT_INSN (x))
987 gcc_assert (PREV_INSN (x) == prevx);
989 gcc_assert (prevx == get_last_insn ());
991 for (nextx = NULL, insn_cnt2 = 1, x = get_last_insn ();
993 nextx = x, insn_cnt2++, x = PREV_INSN (x))
994 gcc_assert (NEXT_INSN (x) == nextx);
996 gcc_assert (insn_cnt1 == insn_cnt2);
999 /* If we have assembler epilogues, the block falling through to exit must
1000 be the last one in the reordered chain when we reach final. Ensure
1001 that this condition is met. */
1003 fixup_fallthru_exit_predecessor (void)
1007 basic_block bb = NULL;
1009 /* This transformation is not valid before reload, because we might
1010 separate a call from the instruction that copies the return
1012 gcc_assert (reload_completed);
1014 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
1015 if (e->flags & EDGE_FALLTHRU)
1020 basic_block c = ENTRY_BLOCK_PTR->next_bb;
1022 /* If the very first block is the one with the fall-through exit
1023 edge, we have to split that block. */
1026 bb = split_block (bb, NULL)->dest;
1029 bb->il.rtl->footer = c->il.rtl->footer;
1030 c->il.rtl->footer = NULL;
1033 while (c->aux != bb)
1034 c = (basic_block) c->aux;
1038 c = (basic_block) c->aux;
1045 /* In case there are more than one fallthru predecessors of exit, force that
1046 there is only one. */
1049 force_one_exit_fallthru (void)
1051 edge e, predecessor = NULL;
1054 basic_block forwarder, bb;
1056 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
1057 if (e->flags & EDGE_FALLTHRU)
1059 if (predecessor == NULL)
1071 /* Exit has several fallthru predecessors. Create a forwarder block for
1073 forwarder = split_edge (predecessor);
1074 for (ei = ei_start (EXIT_BLOCK_PTR->preds); (e = ei_safe_edge (ei)); )
1076 if (e->src == forwarder
1077 || !(e->flags & EDGE_FALLTHRU))
1080 redirect_edge_and_branch_force (e, forwarder);
1083 /* Fix up the chain of blocks -- make FORWARDER immediately precede the
1087 if (bb->aux == NULL && bb != forwarder)
1089 bb->aux = forwarder;
1095 /* Return true in case it is possible to duplicate the basic block BB. */
1097 /* We do not want to declare the function in a header file, since it should
1098 only be used through the cfghooks interface, and we do not want to move
1099 it to cfgrtl.c since it would require also moving quite a lot of related
1101 extern bool cfg_layout_can_duplicate_bb_p (const_basic_block);
1104 cfg_layout_can_duplicate_bb_p (const_basic_block bb)
1106 /* Do not attempt to duplicate tablejumps, as we need to unshare
1107 the dispatch table. This is difficult to do, as the instructions
1108 computing jump destination may be hoisted outside the basic block. */
1109 if (tablejump_p (BB_END (bb), NULL, NULL))
1112 /* Do not duplicate blocks containing insns that can't be copied. */
1113 if (targetm.cannot_copy_insn_p)
1115 rtx insn = BB_HEAD (bb);
1118 if (INSN_P (insn) && targetm.cannot_copy_insn_p (insn))
1120 if (insn == BB_END (bb))
1122 insn = NEXT_INSN (insn);
1130 duplicate_insn_chain (rtx from, rtx to)
1132 rtx insn, last, copy;
1134 /* Avoid updating of boundaries of previous basic block. The
1135 note will get removed from insn stream in fixup. */
1136 last = emit_note (NOTE_INSN_DELETED);
1138 /* Create copy at the end of INSN chain. The chain will
1139 be reordered later. */
1140 for (insn = from; insn != NEXT_INSN (to); insn = NEXT_INSN (insn))
1142 switch (GET_CODE (insn))
1148 /* Avoid copying of dispatch tables. We never duplicate
1149 tablejumps, so this can hit only in case the table got
1150 moved far from original jump. */
1151 if (GET_CODE (PATTERN (insn)) == ADDR_VEC
1152 || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
1154 copy = emit_copy_of_insn_after (insn, get_last_insn ());
1155 maybe_copy_epilogue_insn (insn, copy);
1166 switch (NOTE_KIND (insn))
1168 /* In case prologue is empty and function contain label
1169 in first BB, we may want to copy the block. */
1170 case NOTE_INSN_PROLOGUE_END:
1172 case NOTE_INSN_DELETED:
1173 case NOTE_INSN_DELETED_LABEL:
1174 /* No problem to strip these. */
1175 case NOTE_INSN_FUNCTION_BEG:
1176 /* There is always just single entry to function. */
1177 case NOTE_INSN_BASIC_BLOCK:
1180 case NOTE_INSN_EPILOGUE_BEG:
1181 case NOTE_INSN_SWITCH_TEXT_SECTIONS:
1182 emit_note_copy (insn);
1186 /* All other notes should have already been eliminated. */
1194 insn = NEXT_INSN (last);
1198 /* Create a duplicate of the basic block BB. */
1200 /* We do not want to declare the function in a header file, since it should
1201 only be used through the cfghooks interface, and we do not want to move
1202 it to cfgrtl.c since it would require also moving quite a lot of related
1204 extern basic_block cfg_layout_duplicate_bb (basic_block);
1207 cfg_layout_duplicate_bb (basic_block bb)
1212 insn = duplicate_insn_chain (BB_HEAD (bb), BB_END (bb));
1213 new_bb = create_basic_block (insn,
1214 insn ? get_last_insn () : NULL,
1215 EXIT_BLOCK_PTR->prev_bb);
1217 BB_COPY_PARTITION (new_bb, bb);
1218 if (bb->il.rtl->header)
1220 insn = bb->il.rtl->header;
1221 while (NEXT_INSN (insn))
1222 insn = NEXT_INSN (insn);
1223 insn = duplicate_insn_chain (bb->il.rtl->header, insn);
1225 new_bb->il.rtl->header = unlink_insn_chain (insn, get_last_insn ());
1228 if (bb->il.rtl->footer)
1230 insn = bb->il.rtl->footer;
1231 while (NEXT_INSN (insn))
1232 insn = NEXT_INSN (insn);
1233 insn = duplicate_insn_chain (bb->il.rtl->footer, insn);
1235 new_bb->il.rtl->footer = unlink_insn_chain (insn, get_last_insn ());
1242 /* Main entry point to this module - initialize the datastructures for
1243 CFG layout changes. It keeps LOOPS up-to-date if not null.
1245 FLAGS is a set of additional flags to pass to cleanup_cfg(). */
1248 cfg_layout_initialize (unsigned int flags)
1253 initialize_original_copy_tables ();
1255 cfg_layout_rtl_register_cfg_hooks ();
1257 record_effective_endpoints ();
1259 /* Make sure that the targets of non local gotos are marked. */
1260 for (x = nonlocal_goto_handler_labels; x; x = XEXP (x, 1))
1262 bb = BLOCK_FOR_INSN (XEXP (x, 0));
1263 bb->flags |= BB_NON_LOCAL_GOTO_TARGET;
1266 cleanup_cfg (CLEANUP_CFGLAYOUT | flags);
1269 /* Splits superblocks. */
1271 break_superblocks (void)
1273 sbitmap superblocks;
1277 superblocks = sbitmap_alloc (last_basic_block);
1278 sbitmap_zero (superblocks);
1281 if (bb->flags & BB_SUPERBLOCK)
1283 bb->flags &= ~BB_SUPERBLOCK;
1284 SET_BIT (superblocks, bb->index);
1290 rebuild_jump_labels (get_insns ());
1291 find_many_sub_basic_blocks (superblocks);
1297 /* Finalize the changes: reorder insn list according to the sequence specified
1298 by aux pointers, enter compensation code, rebuild scope forest. */
1301 cfg_layout_finalize (void)
1303 #ifdef ENABLE_CHECKING
1304 verify_flow_info ();
1306 force_one_exit_fallthru ();
1307 rtl_register_cfg_hooks ();
1308 if (reload_completed
1309 #ifdef HAVE_epilogue
1313 fixup_fallthru_exit_predecessor ();
1314 fixup_reorder_chain ();
1316 rebuild_jump_labels (get_insns ());
1317 delete_dead_jumptables ();
1319 #ifdef ENABLE_CHECKING
1320 verify_insn_chain ();
1321 verify_flow_info ();
1325 /* Checks whether all N blocks in BBS array can be copied. */
1327 can_copy_bbs_p (basic_block *bbs, unsigned n)
1333 for (i = 0; i < n; i++)
1334 bbs[i]->flags |= BB_DUPLICATED;
1336 for (i = 0; i < n; i++)
1338 /* In case we should redirect abnormal edge during duplication, fail. */
1340 FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1341 if ((e->flags & EDGE_ABNORMAL)
1342 && (e->dest->flags & BB_DUPLICATED))
1348 if (!can_duplicate_block_p (bbs[i]))
1356 for (i = 0; i < n; i++)
1357 bbs[i]->flags &= ~BB_DUPLICATED;
1362 /* Duplicates N basic blocks stored in array BBS. Newly created basic blocks
1363 are placed into array NEW_BBS in the same order. Edges from basic blocks
1364 in BBS are also duplicated and copies of those of them
1365 that lead into BBS are redirected to appropriate newly created block. The
1366 function assigns bbs into loops (copy of basic block bb is assigned to
1367 bb->loop_father->copy loop, so this must be set up correctly in advance)
1368 and updates dominators locally (LOOPS structure that contains the information
1369 about dominators is passed to enable this).
1371 BASE is the superloop to that basic block belongs; if its header or latch
1372 is copied, we do not set the new blocks as header or latch.
1374 Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
1375 also in the same order.
1377 Newly created basic blocks are put after the basic block AFTER in the
1378 instruction stream, and the order of the blocks in BBS array is preserved. */
1381 copy_bbs (basic_block *bbs, unsigned n, basic_block *new_bbs,
1382 edge *edges, unsigned num_edges, edge *new_edges,
1383 struct loop *base, basic_block after)
1386 basic_block bb, new_bb, dom_bb;
1389 /* Duplicate bbs, update dominators, assign bbs to loops. */
1390 for (i = 0; i < n; i++)
1394 new_bb = new_bbs[i] = duplicate_block (bb, NULL, after);
1396 bb->flags |= BB_DUPLICATED;
1397 /* Possibly set loop header. */
1398 if (bb->loop_father->header == bb && bb->loop_father != base)
1399 new_bb->loop_father->header = new_bb;
1401 if (bb->loop_father->latch == bb && bb->loop_father != base)
1402 new_bb->loop_father->latch = new_bb;
1405 /* Set dominators. */
1406 for (i = 0; i < n; i++)
1409 new_bb = new_bbs[i];
1411 dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
1412 if (dom_bb->flags & BB_DUPLICATED)
1414 dom_bb = get_bb_copy (dom_bb);
1415 set_immediate_dominator (CDI_DOMINATORS, new_bb, dom_bb);
1419 /* Redirect edges. */
1420 for (j = 0; j < num_edges; j++)
1421 new_edges[j] = NULL;
1422 for (i = 0; i < n; i++)
1425 new_bb = new_bbs[i];
1428 FOR_EACH_EDGE (e, ei, new_bb->succs)
1430 for (j = 0; j < num_edges; j++)
1431 if (edges[j] && edges[j]->src == bb && edges[j]->dest == e->dest)
1434 if (!(e->dest->flags & BB_DUPLICATED))
1436 redirect_edge_and_branch_force (e, get_bb_copy (e->dest));
1440 /* Clear information about duplicates. */
1441 for (i = 0; i < n; i++)
1442 bbs[i]->flags &= ~BB_DUPLICATED;
1445 #include "gt-cfglayout.h"