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);
853 /* Otherwise we have some return, switch or computed
854 jump. In the 99% case, there should not have been a
856 gcc_assert (returnjump_p (bb_end_insn) || !e_fall);
862 /* No fallthru implies a noreturn function with EH edges, or
863 something similarly bizarre. In any case, we don't need to
868 /* If the fallthru block is still next, nothing to do. */
869 if (bb->aux == e_fall->dest)
872 /* A fallthru to exit block. */
873 if (e_fall->dest == EXIT_BLOCK_PTR)
877 /* We got here if we need to add a new jump insn. */
878 nb = force_nonfallthru (e_fall);
881 nb->il.rtl->visited = 1;
884 /* Don't process this new block. */
887 /* Make sure new bb is tagged for correct section (same as
888 fall-thru source, since you cannot fall-throu across
889 section boundaries). */
890 BB_COPY_PARTITION (e_fall->src, single_pred (bb));
891 if (flag_reorder_blocks_and_partition
892 && targetm.have_named_sections
893 && JUMP_P (BB_END (bb))
894 && !any_condjump_p (BB_END (bb))
895 && (EDGE_SUCC (bb, 0)->flags & EDGE_CROSSING))
896 add_reg_note (BB_END (bb), REG_CROSSING_JUMP, NULL_RTX);
900 relink_block_chain (/*stay_in_cfglayout_mode=*/false);
902 /* Annoying special case - jump around dead jumptables left in the code. */
908 FOR_EACH_EDGE (e, ei, bb->succs)
909 if (e->flags & EDGE_FALLTHRU)
912 if (e && !can_fallthru (e->src, e->dest))
913 force_nonfallthru (e);
916 /* Ensure goto_locus from edges has some instructions with that locus
924 FOR_EACH_EDGE (e, ei, bb->succs)
925 if (e->goto_locus && !(e->flags & EDGE_ABNORMAL))
930 insn = BB_END (e->src);
931 end = PREV_INSN (BB_HEAD (e->src));
933 && (!INSN_P (insn) || INSN_LOCATOR (insn) == 0))
934 insn = PREV_INSN (insn);
936 && locator_eq (INSN_LOCATOR (insn), (int) e->goto_locus))
938 if (simplejump_p (BB_END (e->src))
939 && INSN_LOCATOR (BB_END (e->src)) == 0)
941 INSN_LOCATOR (BB_END (e->src)) = e->goto_locus;
944 if (e->dest != EXIT_BLOCK_PTR)
946 insn = BB_HEAD (e->dest);
947 end = NEXT_INSN (BB_END (e->dest));
948 while (insn != end && !INSN_P (insn))
949 insn = NEXT_INSN (insn);
950 if (insn != end && INSN_LOCATOR (insn)
951 && locator_eq (INSN_LOCATOR (insn), (int) e->goto_locus))
955 if (!INSN_P (BB_END (nb)))
956 BB_END (nb) = emit_insn_after_noloc (gen_nop (), BB_END (nb),
958 INSN_LOCATOR (BB_END (nb)) = e->goto_locus;
963 /* Perform sanity checks on the insn chain.
964 1. Check that next/prev pointers are consistent in both the forward and
966 2. Count insns in chain, going both directions, and check if equal.
967 3. Check that get_last_insn () returns the actual end of chain. */
970 verify_insn_chain (void)
973 int insn_cnt1, insn_cnt2;
975 for (prevx = NULL, insn_cnt1 = 1, x = get_insns ();
977 prevx = x, insn_cnt1++, x = NEXT_INSN (x))
978 gcc_assert (PREV_INSN (x) == prevx);
980 gcc_assert (prevx == get_last_insn ());
982 for (nextx = NULL, insn_cnt2 = 1, x = get_last_insn ();
984 nextx = x, insn_cnt2++, x = PREV_INSN (x))
985 gcc_assert (NEXT_INSN (x) == nextx);
987 gcc_assert (insn_cnt1 == insn_cnt2);
990 /* If we have assembler epilogues, the block falling through to exit must
991 be the last one in the reordered chain when we reach final. Ensure
992 that this condition is met. */
994 fixup_fallthru_exit_predecessor (void)
998 basic_block bb = NULL;
1000 /* This transformation is not valid before reload, because we might
1001 separate a call from the instruction that copies the return
1003 gcc_assert (reload_completed);
1005 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
1006 if (e->flags & EDGE_FALLTHRU)
1011 basic_block c = ENTRY_BLOCK_PTR->next_bb;
1013 /* If the very first block is the one with the fall-through exit
1014 edge, we have to split that block. */
1017 bb = split_block (bb, NULL)->dest;
1020 bb->il.rtl->footer = c->il.rtl->footer;
1021 c->il.rtl->footer = NULL;
1024 while (c->aux != bb)
1025 c = (basic_block) c->aux;
1029 c = (basic_block) c->aux;
1036 /* In case there are more than one fallthru predecessors of exit, force that
1037 there is only one. */
1040 force_one_exit_fallthru (void)
1042 edge e, predecessor = NULL;
1045 basic_block forwarder, bb;
1047 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
1048 if (e->flags & EDGE_FALLTHRU)
1050 if (predecessor == NULL)
1062 /* Exit has several fallthru predecessors. Create a forwarder block for
1064 forwarder = split_edge (predecessor);
1065 for (ei = ei_start (EXIT_BLOCK_PTR->preds); (e = ei_safe_edge (ei)); )
1067 if (e->src == forwarder
1068 || !(e->flags & EDGE_FALLTHRU))
1071 redirect_edge_and_branch_force (e, forwarder);
1074 /* Fix up the chain of blocks -- make FORWARDER immediately precede the
1078 if (bb->aux == NULL && bb != forwarder)
1080 bb->aux = forwarder;
1086 /* Return true in case it is possible to duplicate the basic block BB. */
1088 /* We do not want to declare the function in a header file, since it should
1089 only be used through the cfghooks interface, and we do not want to move
1090 it to cfgrtl.c since it would require also moving quite a lot of related
1092 extern bool cfg_layout_can_duplicate_bb_p (const_basic_block);
1095 cfg_layout_can_duplicate_bb_p (const_basic_block bb)
1097 /* Do not attempt to duplicate tablejumps, as we need to unshare
1098 the dispatch table. This is difficult to do, as the instructions
1099 computing jump destination may be hoisted outside the basic block. */
1100 if (tablejump_p (BB_END (bb), NULL, NULL))
1103 /* Do not duplicate blocks containing insns that can't be copied. */
1104 if (targetm.cannot_copy_insn_p)
1106 rtx insn = BB_HEAD (bb);
1109 if (INSN_P (insn) && targetm.cannot_copy_insn_p (insn))
1111 if (insn == BB_END (bb))
1113 insn = NEXT_INSN (insn);
1121 duplicate_insn_chain (rtx from, rtx to)
1123 rtx insn, last, copy;
1125 /* Avoid updating of boundaries of previous basic block. The
1126 note will get removed from insn stream in fixup. */
1127 last = emit_note (NOTE_INSN_DELETED);
1129 /* Create copy at the end of INSN chain. The chain will
1130 be reordered later. */
1131 for (insn = from; insn != NEXT_INSN (to); insn = NEXT_INSN (insn))
1133 switch (GET_CODE (insn))
1139 /* Avoid copying of dispatch tables. We never duplicate
1140 tablejumps, so this can hit only in case the table got
1141 moved far from original jump. */
1142 if (GET_CODE (PATTERN (insn)) == ADDR_VEC
1143 || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
1145 copy = emit_copy_of_insn_after (insn, get_last_insn ());
1146 maybe_copy_epilogue_insn (insn, copy);
1157 switch (NOTE_KIND (insn))
1159 /* In case prologue is empty and function contain label
1160 in first BB, we may want to copy the block. */
1161 case NOTE_INSN_PROLOGUE_END:
1163 case NOTE_INSN_DELETED:
1164 case NOTE_INSN_DELETED_LABEL:
1165 /* No problem to strip these. */
1166 case NOTE_INSN_FUNCTION_BEG:
1167 /* There is always just single entry to function. */
1168 case NOTE_INSN_BASIC_BLOCK:
1171 case NOTE_INSN_EPILOGUE_BEG:
1172 case NOTE_INSN_SWITCH_TEXT_SECTIONS:
1173 emit_note_copy (insn);
1177 /* All other notes should have already been eliminated. */
1185 insn = NEXT_INSN (last);
1189 /* Create a duplicate of the basic block BB. */
1191 /* We do not want to declare the function in a header file, since it should
1192 only be used through the cfghooks interface, and we do not want to move
1193 it to cfgrtl.c since it would require also moving quite a lot of related
1195 extern basic_block cfg_layout_duplicate_bb (basic_block);
1198 cfg_layout_duplicate_bb (basic_block bb)
1203 insn = duplicate_insn_chain (BB_HEAD (bb), BB_END (bb));
1204 new_bb = create_basic_block (insn,
1205 insn ? get_last_insn () : NULL,
1206 EXIT_BLOCK_PTR->prev_bb);
1208 BB_COPY_PARTITION (new_bb, bb);
1209 if (bb->il.rtl->header)
1211 insn = bb->il.rtl->header;
1212 while (NEXT_INSN (insn))
1213 insn = NEXT_INSN (insn);
1214 insn = duplicate_insn_chain (bb->il.rtl->header, insn);
1216 new_bb->il.rtl->header = unlink_insn_chain (insn, get_last_insn ());
1219 if (bb->il.rtl->footer)
1221 insn = bb->il.rtl->footer;
1222 while (NEXT_INSN (insn))
1223 insn = NEXT_INSN (insn);
1224 insn = duplicate_insn_chain (bb->il.rtl->footer, insn);
1226 new_bb->il.rtl->footer = unlink_insn_chain (insn, get_last_insn ());
1233 /* Main entry point to this module - initialize the datastructures for
1234 CFG layout changes. It keeps LOOPS up-to-date if not null.
1236 FLAGS is a set of additional flags to pass to cleanup_cfg(). */
1239 cfg_layout_initialize (unsigned int flags)
1244 initialize_original_copy_tables ();
1246 cfg_layout_rtl_register_cfg_hooks ();
1248 record_effective_endpoints ();
1250 /* Make sure that the targets of non local gotos are marked. */
1251 for (x = nonlocal_goto_handler_labels; x; x = XEXP (x, 1))
1253 bb = BLOCK_FOR_INSN (XEXP (x, 0));
1254 bb->flags |= BB_NON_LOCAL_GOTO_TARGET;
1257 cleanup_cfg (CLEANUP_CFGLAYOUT | flags);
1260 /* Splits superblocks. */
1262 break_superblocks (void)
1264 sbitmap superblocks;
1268 superblocks = sbitmap_alloc (last_basic_block);
1269 sbitmap_zero (superblocks);
1272 if (bb->flags & BB_SUPERBLOCK)
1274 bb->flags &= ~BB_SUPERBLOCK;
1275 SET_BIT (superblocks, bb->index);
1281 rebuild_jump_labels (get_insns ());
1282 find_many_sub_basic_blocks (superblocks);
1288 /* Finalize the changes: reorder insn list according to the sequence specified
1289 by aux pointers, enter compensation code, rebuild scope forest. */
1292 cfg_layout_finalize (void)
1294 #ifdef ENABLE_CHECKING
1295 verify_flow_info ();
1297 force_one_exit_fallthru ();
1298 rtl_register_cfg_hooks ();
1299 if (reload_completed
1300 #ifdef HAVE_epilogue
1304 fixup_fallthru_exit_predecessor ();
1305 fixup_reorder_chain ();
1307 rebuild_jump_labels (get_insns ());
1308 delete_dead_jumptables ();
1310 #ifdef ENABLE_CHECKING
1311 verify_insn_chain ();
1312 verify_flow_info ();
1316 /* Checks whether all N blocks in BBS array can be copied. */
1318 can_copy_bbs_p (basic_block *bbs, unsigned n)
1324 for (i = 0; i < n; i++)
1325 bbs[i]->flags |= BB_DUPLICATED;
1327 for (i = 0; i < n; i++)
1329 /* In case we should redirect abnormal edge during duplication, fail. */
1331 FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1332 if ((e->flags & EDGE_ABNORMAL)
1333 && (e->dest->flags & BB_DUPLICATED))
1339 if (!can_duplicate_block_p (bbs[i]))
1347 for (i = 0; i < n; i++)
1348 bbs[i]->flags &= ~BB_DUPLICATED;
1353 /* Duplicates N basic blocks stored in array BBS. Newly created basic blocks
1354 are placed into array NEW_BBS in the same order. Edges from basic blocks
1355 in BBS are also duplicated and copies of those of them
1356 that lead into BBS are redirected to appropriate newly created block. The
1357 function assigns bbs into loops (copy of basic block bb is assigned to
1358 bb->loop_father->copy loop, so this must be set up correctly in advance)
1359 and updates dominators locally (LOOPS structure that contains the information
1360 about dominators is passed to enable this).
1362 BASE is the superloop to that basic block belongs; if its header or latch
1363 is copied, we do not set the new blocks as header or latch.
1365 Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
1366 also in the same order.
1368 Newly created basic blocks are put after the basic block AFTER in the
1369 instruction stream, and the order of the blocks in BBS array is preserved. */
1372 copy_bbs (basic_block *bbs, unsigned n, basic_block *new_bbs,
1373 edge *edges, unsigned num_edges, edge *new_edges,
1374 struct loop *base, basic_block after)
1377 basic_block bb, new_bb, dom_bb;
1380 /* Duplicate bbs, update dominators, assign bbs to loops. */
1381 for (i = 0; i < n; i++)
1385 new_bb = new_bbs[i] = duplicate_block (bb, NULL, after);
1387 bb->flags |= BB_DUPLICATED;
1388 /* Possibly set loop header. */
1389 if (bb->loop_father->header == bb && bb->loop_father != base)
1390 new_bb->loop_father->header = new_bb;
1392 if (bb->loop_father->latch == bb && bb->loop_father != base)
1393 new_bb->loop_father->latch = new_bb;
1396 /* Set dominators. */
1397 for (i = 0; i < n; i++)
1400 new_bb = new_bbs[i];
1402 dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
1403 if (dom_bb->flags & BB_DUPLICATED)
1405 dom_bb = get_bb_copy (dom_bb);
1406 set_immediate_dominator (CDI_DOMINATORS, new_bb, dom_bb);
1410 /* Redirect edges. */
1411 for (j = 0; j < num_edges; j++)
1412 new_edges[j] = NULL;
1413 for (i = 0; i < n; i++)
1416 new_bb = new_bbs[i];
1419 FOR_EACH_EDGE (e, ei, new_bb->succs)
1421 for (j = 0; j < num_edges; j++)
1422 if (edges[j] && edges[j]->src == bb && edges[j]->dest == e->dest)
1425 if (!(e->dest->flags & BB_DUPLICATED))
1427 redirect_edge_and_branch_force (e, get_bb_copy (e->dest));
1431 /* Clear information about duplicates. */
1432 for (i = 0; i < n; i++)
1433 bbs[i]->flags &= ~BB_DUPLICATED;
1436 #include "gt-cfglayout.h"