1 /* Basic block reordering routines for the GNU compiler.
2 Copyright (C) 2000, 2001, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
3 2011 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"
44 /* Holds the interesting trailing notes for the function. */
45 rtx cfg_layout_function_footer
;
46 rtx cfg_layout_function_header
;
48 static rtx
skip_insns_after_block (basic_block
);
49 static void record_effective_endpoints (void);
50 static rtx
label_for_bb (basic_block
);
51 static void fixup_reorder_chain (void);
53 static void change_scope (rtx
, tree
, tree
);
55 void verify_insn_chain (void);
56 static void fixup_fallthru_exit_predecessor (void);
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 /* This might happen if the conditional jump has side
791 effects and could therefore not be optimized away.
792 Make the basic block to end with a barrier in order
793 to prevent rtl_verify_flow_info from complaining. */
796 gcc_assert (!onlyjump_p (bb_end_insn
)
797 || returnjump_p (bb_end_insn
));
798 bb
->il
.rtl
->footer
= emit_barrier_after (bb_end_insn
);
802 /* If the old fallthru is still next, nothing to do. */
803 if (bb
->aux
== e_fall
->dest
804 || e_fall
->dest
== EXIT_BLOCK_PTR
)
807 /* The degenerated case of conditional jump jumping to the next
808 instruction can happen for jumps with side effects. We need
809 to construct a forwarder block and this will be done just
810 fine by force_nonfallthru below. */
814 /* There is another special case: if *neither* block is next,
815 such as happens at the very end of a function, then we'll
816 need to add a new unconditional jump. Choose the taken
817 edge based on known or assumed probability. */
818 else if (bb
->aux
!= e_taken
->dest
)
820 rtx note
= find_reg_note (bb_end_insn
, REG_BR_PROB
, 0);
823 && INTVAL (XEXP (note
, 0)) < REG_BR_PROB_BASE
/ 2
824 && invert_jump (bb_end_insn
,
825 (e_fall
->dest
== EXIT_BLOCK_PTR
827 : label_for_bb (e_fall
->dest
)), 0))
829 e_fall
->flags
&= ~EDGE_FALLTHRU
;
830 gcc_checking_assert (could_fall_through
831 (e_taken
->src
, e_taken
->dest
));
832 e_taken
->flags
|= EDGE_FALLTHRU
;
833 update_br_prob_note (bb
);
834 e
= e_fall
, e_fall
= e_taken
, e_taken
= e
;
838 /* If the "jumping" edge is a crossing edge, and the fall
839 through edge is non-crossing, leave things as they are. */
840 else if ((e_taken
->flags
& EDGE_CROSSING
)
841 && !(e_fall
->flags
& EDGE_CROSSING
))
844 /* Otherwise we can try to invert the jump. This will
845 basically never fail, however, keep up the pretense. */
846 else if (invert_jump (bb_end_insn
,
847 (e_fall
->dest
== EXIT_BLOCK_PTR
849 : label_for_bb (e_fall
->dest
)), 0))
851 e_fall
->flags
&= ~EDGE_FALLTHRU
;
852 gcc_checking_assert (could_fall_through
853 (e_taken
->src
, e_taken
->dest
));
854 e_taken
->flags
|= EDGE_FALLTHRU
;
855 update_br_prob_note (bb
);
859 else if (extract_asm_operands (PATTERN (bb_end_insn
)) != NULL
)
861 /* If the old fallthru is still next or if
862 asm goto doesn't have a fallthru (e.g. when followed by
863 __builtin_unreachable ()), nothing to do. */
865 || bb
->aux
== e_fall
->dest
866 || e_fall
->dest
== EXIT_BLOCK_PTR
)
869 /* Otherwise we'll have to use the fallthru fixup below. */
873 /* Otherwise we have some return, switch or computed
874 jump. In the 99% case, there should not have been a
876 gcc_assert (returnjump_p (bb_end_insn
) || !e_fall
);
882 /* No fallthru implies a noreturn function with EH edges, or
883 something similarly bizarre. In any case, we don't need to
888 /* If the fallthru block is still next, nothing to do. */
889 if (bb
->aux
== e_fall
->dest
)
892 /* A fallthru to exit block. */
893 if (e_fall
->dest
== EXIT_BLOCK_PTR
)
897 /* We got here if we need to add a new jump insn. */
898 nb
= force_nonfallthru (e_fall
);
901 nb
->il
.rtl
->visited
= 1;
904 /* Don't process this new block. */
907 /* Make sure new bb is tagged for correct section (same as
908 fall-thru source, since you cannot fall-throu across
909 section boundaries). */
910 BB_COPY_PARTITION (e_fall
->src
, single_pred (bb
));
911 if (flag_reorder_blocks_and_partition
912 && targetm
.have_named_sections
913 && JUMP_P (BB_END (bb
))
914 && !any_condjump_p (BB_END (bb
))
915 && (EDGE_SUCC (bb
, 0)->flags
& EDGE_CROSSING
))
916 add_reg_note (BB_END (bb
), REG_CROSSING_JUMP
, NULL_RTX
);
920 relink_block_chain (/*stay_in_cfglayout_mode=*/false);
922 /* Annoying special case - jump around dead jumptables left in the code. */
925 edge e
= find_fallthru_edge (bb
->succs
);
927 if (e
&& !can_fallthru (e
->src
, e
->dest
))
928 force_nonfallthru (e
);
931 /* Ensure goto_locus from edges has some instructions with that locus
939 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
940 if (e
->goto_locus
&& !(e
->flags
& EDGE_ABNORMAL
))
944 basic_block dest
, nb
;
947 insn
= BB_END (e
->src
);
948 end
= PREV_INSN (BB_HEAD (e
->src
));
950 && (!NONDEBUG_INSN_P (insn
) || INSN_LOCATOR (insn
) == 0))
951 insn
= PREV_INSN (insn
);
953 && locator_eq (INSN_LOCATOR (insn
), (int) e
->goto_locus
))
955 if (simplejump_p (BB_END (e
->src
))
956 && INSN_LOCATOR (BB_END (e
->src
)) == 0)
958 INSN_LOCATOR (BB_END (e
->src
)) = e
->goto_locus
;
962 if (dest
== EXIT_BLOCK_PTR
)
964 /* Non-fallthru edges to the exit block cannot be split. */
965 if (!(e
->flags
& EDGE_FALLTHRU
))
970 insn
= BB_HEAD (dest
);
971 end
= NEXT_INSN (BB_END (dest
));
972 while (insn
!= end
&& !NONDEBUG_INSN_P (insn
))
973 insn
= NEXT_INSN (insn
);
974 if (insn
!= end
&& INSN_LOCATOR (insn
)
975 && locator_eq (INSN_LOCATOR (insn
), (int) e
->goto_locus
))
979 if (!INSN_P (BB_END (nb
)))
980 BB_END (nb
) = emit_insn_after_noloc (gen_nop (), BB_END (nb
),
982 INSN_LOCATOR (BB_END (nb
)) = e
->goto_locus
;
984 /* If there are other incoming edges to the destination block
985 with the same goto locus, redirect them to the new block as
986 well, this can prevent other such blocks from being created
987 in subsequent iterations of the loop. */
988 for (ei2
= ei_start (dest
->preds
); (e2
= ei_safe_edge (ei2
)); )
990 && !(e2
->flags
& (EDGE_ABNORMAL
| EDGE_FALLTHRU
))
991 && locator_eq (e
->goto_locus
, e2
->goto_locus
))
992 redirect_edge_and_branch (e2
, nb
);
999 /* Perform sanity checks on the insn chain.
1000 1. Check that next/prev pointers are consistent in both the forward and
1002 2. Count insns in chain, going both directions, and check if equal.
1003 3. Check that get_last_insn () returns the actual end of chain. */
1006 verify_insn_chain (void)
1008 rtx x
, prevx
, nextx
;
1009 int insn_cnt1
, insn_cnt2
;
1011 for (prevx
= NULL
, insn_cnt1
= 1, x
= get_insns ();
1013 prevx
= x
, insn_cnt1
++, x
= NEXT_INSN (x
))
1014 gcc_assert (PREV_INSN (x
) == prevx
);
1016 gcc_assert (prevx
== get_last_insn ());
1018 for (nextx
= NULL
, insn_cnt2
= 1, x
= get_last_insn ();
1020 nextx
= x
, insn_cnt2
++, x
= PREV_INSN (x
))
1021 gcc_assert (NEXT_INSN (x
) == nextx
);
1023 gcc_assert (insn_cnt1
== insn_cnt2
);
1026 /* If we have assembler epilogues, the block falling through to exit must
1027 be the last one in the reordered chain when we reach final. Ensure
1028 that this condition is met. */
1030 fixup_fallthru_exit_predecessor (void)
1033 basic_block bb
= NULL
;
1035 /* This transformation is not valid before reload, because we might
1036 separate a call from the instruction that copies the return
1038 gcc_assert (reload_completed
);
1040 e
= find_fallthru_edge (EXIT_BLOCK_PTR
->preds
);
1046 basic_block c
= ENTRY_BLOCK_PTR
->next_bb
;
1048 /* If the very first block is the one with the fall-through exit
1049 edge, we have to split that block. */
1052 bb
= split_block (bb
, NULL
)->dest
;
1055 bb
->il
.rtl
->footer
= c
->il
.rtl
->footer
;
1056 c
->il
.rtl
->footer
= NULL
;
1059 while (c
->aux
!= bb
)
1060 c
= (basic_block
) c
->aux
;
1064 c
= (basic_block
) c
->aux
;
1071 /* In case there are more than one fallthru predecessors of exit, force that
1072 there is only one. */
1075 force_one_exit_fallthru (void)
1077 edge e
, predecessor
= NULL
;
1080 basic_block forwarder
, bb
;
1082 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
1083 if (e
->flags
& EDGE_FALLTHRU
)
1085 if (predecessor
== NULL
)
1097 /* Exit has several fallthru predecessors. Create a forwarder block for
1099 forwarder
= split_edge (predecessor
);
1100 for (ei
= ei_start (EXIT_BLOCK_PTR
->preds
); (e
= ei_safe_edge (ei
)); )
1102 if (e
->src
== forwarder
1103 || !(e
->flags
& EDGE_FALLTHRU
))
1106 redirect_edge_and_branch_force (e
, forwarder
);
1109 /* Fix up the chain of blocks -- make FORWARDER immediately precede the
1113 if (bb
->aux
== NULL
&& bb
!= forwarder
)
1115 bb
->aux
= forwarder
;
1121 /* Return true in case it is possible to duplicate the basic block BB. */
1123 /* We do not want to declare the function in a header file, since it should
1124 only be used through the cfghooks interface, and we do not want to move
1125 it to cfgrtl.c since it would require also moving quite a lot of related
1127 extern bool cfg_layout_can_duplicate_bb_p (const_basic_block
);
1130 cfg_layout_can_duplicate_bb_p (const_basic_block bb
)
1132 /* Do not attempt to duplicate tablejumps, as we need to unshare
1133 the dispatch table. This is difficult to do, as the instructions
1134 computing jump destination may be hoisted outside the basic block. */
1135 if (tablejump_p (BB_END (bb
), NULL
, NULL
))
1138 /* Do not duplicate blocks containing insns that can't be copied. */
1139 if (targetm
.cannot_copy_insn_p
)
1141 rtx insn
= BB_HEAD (bb
);
1144 if (INSN_P (insn
) && targetm
.cannot_copy_insn_p (insn
))
1146 if (insn
== BB_END (bb
))
1148 insn
= NEXT_INSN (insn
);
1156 duplicate_insn_chain (rtx from
, rtx to
)
1158 rtx insn
, last
, copy
;
1160 /* Avoid updating of boundaries of previous basic block. The
1161 note will get removed from insn stream in fixup. */
1162 last
= emit_note (NOTE_INSN_DELETED
);
1164 /* Create copy at the end of INSN chain. The chain will
1165 be reordered later. */
1166 for (insn
= from
; insn
!= NEXT_INSN (to
); insn
= NEXT_INSN (insn
))
1168 switch (GET_CODE (insn
))
1174 /* Avoid copying of dispatch tables. We never duplicate
1175 tablejumps, so this can hit only in case the table got
1176 moved far from original jump. */
1177 if (GET_CODE (PATTERN (insn
)) == ADDR_VEC
1178 || GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
)
1180 /* Avoid copying following barrier as well if any
1181 (and debug insns in between). */
1184 for (next
= NEXT_INSN (insn
);
1185 next
!= NEXT_INSN (to
);
1186 next
= NEXT_INSN (next
))
1187 if (!DEBUG_INSN_P (next
))
1189 if (next
!= NEXT_INSN (to
) && BARRIER_P (next
))
1193 copy
= emit_copy_of_insn_after (insn
, get_last_insn ());
1194 maybe_copy_prologue_epilogue_insn (insn
, copy
);
1205 switch (NOTE_KIND (insn
))
1207 /* In case prologue is empty and function contain label
1208 in first BB, we may want to copy the block. */
1209 case NOTE_INSN_PROLOGUE_END
:
1211 case NOTE_INSN_DELETED
:
1212 case NOTE_INSN_DELETED_LABEL
:
1213 /* No problem to strip these. */
1214 case NOTE_INSN_FUNCTION_BEG
:
1215 /* There is always just single entry to function. */
1216 case NOTE_INSN_BASIC_BLOCK
:
1219 case NOTE_INSN_EPILOGUE_BEG
:
1220 case NOTE_INSN_SWITCH_TEXT_SECTIONS
:
1221 emit_note_copy (insn
);
1225 /* All other notes should have already been eliminated. */
1233 insn
= NEXT_INSN (last
);
1237 /* Create a duplicate of the basic block BB. */
1239 /* We do not want to declare the function in a header file, since it should
1240 only be used through the cfghooks interface, and we do not want to move
1241 it to cfgrtl.c since it would require also moving quite a lot of related
1243 extern basic_block
cfg_layout_duplicate_bb (basic_block
);
1246 cfg_layout_duplicate_bb (basic_block bb
)
1251 insn
= duplicate_insn_chain (BB_HEAD (bb
), BB_END (bb
));
1252 new_bb
= create_basic_block (insn
,
1253 insn
? get_last_insn () : NULL
,
1254 EXIT_BLOCK_PTR
->prev_bb
);
1256 BB_COPY_PARTITION (new_bb
, bb
);
1257 if (bb
->il
.rtl
->header
)
1259 insn
= bb
->il
.rtl
->header
;
1260 while (NEXT_INSN (insn
))
1261 insn
= NEXT_INSN (insn
);
1262 insn
= duplicate_insn_chain (bb
->il
.rtl
->header
, insn
);
1264 new_bb
->il
.rtl
->header
= unlink_insn_chain (insn
, get_last_insn ());
1267 if (bb
->il
.rtl
->footer
)
1269 insn
= bb
->il
.rtl
->footer
;
1270 while (NEXT_INSN (insn
))
1271 insn
= NEXT_INSN (insn
);
1272 insn
= duplicate_insn_chain (bb
->il
.rtl
->footer
, insn
);
1274 new_bb
->il
.rtl
->footer
= unlink_insn_chain (insn
, get_last_insn ());
1281 /* Main entry point to this module - initialize the datastructures for
1282 CFG layout changes. It keeps LOOPS up-to-date if not null.
1284 FLAGS is a set of additional flags to pass to cleanup_cfg(). */
1287 cfg_layout_initialize (unsigned int flags
)
1292 initialize_original_copy_tables ();
1294 cfg_layout_rtl_register_cfg_hooks ();
1296 record_effective_endpoints ();
1298 /* Make sure that the targets of non local gotos are marked. */
1299 for (x
= nonlocal_goto_handler_labels
; x
; x
= XEXP (x
, 1))
1301 bb
= BLOCK_FOR_INSN (XEXP (x
, 0));
1302 bb
->flags
|= BB_NON_LOCAL_GOTO_TARGET
;
1305 cleanup_cfg (CLEANUP_CFGLAYOUT
| flags
);
1308 /* Splits superblocks. */
1310 break_superblocks (void)
1312 sbitmap superblocks
;
1316 superblocks
= sbitmap_alloc (last_basic_block
);
1317 sbitmap_zero (superblocks
);
1320 if (bb
->flags
& BB_SUPERBLOCK
)
1322 bb
->flags
&= ~BB_SUPERBLOCK
;
1323 SET_BIT (superblocks
, bb
->index
);
1329 rebuild_jump_labels (get_insns ());
1330 find_many_sub_basic_blocks (superblocks
);
1336 /* Finalize the changes: reorder insn list according to the sequence specified
1337 by aux pointers, enter compensation code, rebuild scope forest. */
1340 cfg_layout_finalize (void)
1342 #ifdef ENABLE_CHECKING
1343 verify_flow_info ();
1345 force_one_exit_fallthru ();
1346 rtl_register_cfg_hooks ();
1347 if (reload_completed
1348 #ifdef HAVE_epilogue
1352 fixup_fallthru_exit_predecessor ();
1353 fixup_reorder_chain ();
1355 rebuild_jump_labels (get_insns ());
1356 delete_dead_jumptables ();
1358 #ifdef ENABLE_CHECKING
1359 verify_insn_chain ();
1360 verify_flow_info ();
1364 /* Checks whether all N blocks in BBS array can be copied. */
1366 can_copy_bbs_p (basic_block
*bbs
, unsigned n
)
1372 for (i
= 0; i
< n
; i
++)
1373 bbs
[i
]->flags
|= BB_DUPLICATED
;
1375 for (i
= 0; i
< n
; i
++)
1377 /* In case we should redirect abnormal edge during duplication, fail. */
1379 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
1380 if ((e
->flags
& EDGE_ABNORMAL
)
1381 && (e
->dest
->flags
& BB_DUPLICATED
))
1387 if (!can_duplicate_block_p (bbs
[i
]))
1395 for (i
= 0; i
< n
; i
++)
1396 bbs
[i
]->flags
&= ~BB_DUPLICATED
;
1401 /* Duplicates N basic blocks stored in array BBS. Newly created basic blocks
1402 are placed into array NEW_BBS in the same order. Edges from basic blocks
1403 in BBS are also duplicated and copies of those of them
1404 that lead into BBS are redirected to appropriate newly created block. The
1405 function assigns bbs into loops (copy of basic block bb is assigned to
1406 bb->loop_father->copy loop, so this must be set up correctly in advance)
1407 and updates dominators locally (LOOPS structure that contains the information
1408 about dominators is passed to enable this).
1410 BASE is the superloop to that basic block belongs; if its header or latch
1411 is copied, we do not set the new blocks as header or latch.
1413 Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
1414 also in the same order.
1416 Newly created basic blocks are put after the basic block AFTER in the
1417 instruction stream, and the order of the blocks in BBS array is preserved. */
1420 copy_bbs (basic_block
*bbs
, unsigned n
, basic_block
*new_bbs
,
1421 edge
*edges
, unsigned num_edges
, edge
*new_edges
,
1422 struct loop
*base
, basic_block after
)
1425 basic_block bb
, new_bb
, dom_bb
;
1428 /* Duplicate bbs, update dominators, assign bbs to loops. */
1429 for (i
= 0; i
< n
; i
++)
1433 new_bb
= new_bbs
[i
] = duplicate_block (bb
, NULL
, after
);
1435 bb
->flags
|= BB_DUPLICATED
;
1436 /* Possibly set loop header. */
1437 if (bb
->loop_father
->header
== bb
&& bb
->loop_father
!= base
)
1438 new_bb
->loop_father
->header
= new_bb
;
1440 if (bb
->loop_father
->latch
== bb
&& bb
->loop_father
!= base
)
1441 new_bb
->loop_father
->latch
= new_bb
;
1444 /* Set dominators. */
1445 for (i
= 0; i
< n
; i
++)
1448 new_bb
= new_bbs
[i
];
1450 dom_bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1451 if (dom_bb
->flags
& BB_DUPLICATED
)
1453 dom_bb
= get_bb_copy (dom_bb
);
1454 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, dom_bb
);
1458 /* Redirect edges. */
1459 for (j
= 0; j
< num_edges
; j
++)
1460 new_edges
[j
] = NULL
;
1461 for (i
= 0; i
< n
; i
++)
1464 new_bb
= new_bbs
[i
];
1467 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
1469 for (j
= 0; j
< num_edges
; j
++)
1470 if (edges
[j
] && edges
[j
]->src
== bb
&& edges
[j
]->dest
== e
->dest
)
1473 if (!(e
->dest
->flags
& BB_DUPLICATED
))
1475 redirect_edge_and_branch_force (e
, get_bb_copy (e
->dest
));
1479 /* Clear information about duplicates. */
1480 for (i
= 0; i
< n
; i
++)
1481 bbs
[i
]->flags
&= ~BB_DUPLICATED
;
1484 #include "gt-cfglayout.h"