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"
36 #include "common/common-target.h"
38 #include "alloc-pool.h"
40 #include "tree-pass.h"
45 /* Holds the interesting trailing notes for the function. */
46 rtx cfg_layout_function_footer
;
47 rtx cfg_layout_function_header
;
49 static rtx
skip_insns_after_block (basic_block
);
50 static void record_effective_endpoints (void);
51 static rtx
label_for_bb (basic_block
);
52 static void fixup_reorder_chain (void);
54 static void change_scope (rtx
, tree
, tree
);
56 void verify_insn_chain (void);
57 static void fixup_fallthru_exit_predecessor (void);
60 unlink_insn_chain (rtx first
, rtx last
)
62 rtx prevfirst
= PREV_INSN (first
);
63 rtx nextlast
= NEXT_INSN (last
);
65 PREV_INSN (first
) = NULL
;
66 NEXT_INSN (last
) = NULL
;
68 NEXT_INSN (prevfirst
) = nextlast
;
70 PREV_INSN (nextlast
) = prevfirst
;
72 set_last_insn (prevfirst
);
74 set_first_insn (nextlast
);
78 /* Skip over inter-block insns occurring after BB which are typically
79 associated with BB (e.g., barriers). If there are any such insns,
80 we return the last one. Otherwise, we return the end of BB. */
83 skip_insns_after_block (basic_block bb
)
85 rtx insn
, last_insn
, next_head
, prev
;
88 if (bb
->next_bb
!= EXIT_BLOCK_PTR
)
89 next_head
= BB_HEAD (bb
->next_bb
);
91 for (last_insn
= insn
= BB_END (bb
); (insn
= NEXT_INSN (insn
)) != 0; )
93 if (insn
== next_head
)
96 switch (GET_CODE (insn
))
103 switch (NOTE_KIND (insn
))
105 case NOTE_INSN_BLOCK_END
:
116 && JUMP_TABLE_DATA_P (NEXT_INSN (insn
)))
118 insn
= NEXT_INSN (insn
);
131 /* It is possible to hit contradictory sequence. For instance:
137 Where barrier belongs to jump_insn, but the note does not. This can be
138 created by removing the basic block originally following
139 NOTE_INSN_BLOCK_BEG. In such case reorder the notes. */
141 for (insn
= last_insn
; insn
!= BB_END (bb
); insn
= prev
)
143 prev
= PREV_INSN (insn
);
145 switch (NOTE_KIND (insn
))
147 case NOTE_INSN_BLOCK_END
:
150 case NOTE_INSN_DELETED
:
151 case NOTE_INSN_DELETED_LABEL
:
152 case NOTE_INSN_DELETED_DEBUG_LABEL
:
155 reorder_insns (insn
, insn
, last_insn
);
162 /* Locate or create a label for a given basic block. */
165 label_for_bb (basic_block bb
)
167 rtx label
= BB_HEAD (bb
);
169 if (!LABEL_P (label
))
172 fprintf (dump_file
, "Emitting label for block %d\n", bb
->index
);
174 label
= block_label (bb
);
180 /* Locate the effective beginning and end of the insn chain for each
181 block, as defined by skip_insns_after_block above. */
184 record_effective_endpoints (void)
190 for (insn
= get_insns ();
193 && NOTE_KIND (insn
) != NOTE_INSN_BASIC_BLOCK
;
194 insn
= NEXT_INSN (insn
))
196 /* No basic blocks at all? */
199 if (PREV_INSN (insn
))
200 cfg_layout_function_header
=
201 unlink_insn_chain (get_insns (), PREV_INSN (insn
));
203 cfg_layout_function_header
= NULL_RTX
;
205 next_insn
= get_insns ();
210 if (PREV_INSN (BB_HEAD (bb
)) && next_insn
!= BB_HEAD (bb
))
211 bb
->il
.rtl
->header
= unlink_insn_chain (next_insn
,
212 PREV_INSN (BB_HEAD (bb
)));
213 end
= skip_insns_after_block (bb
);
214 if (NEXT_INSN (BB_END (bb
)) && BB_END (bb
) != end
)
215 bb
->il
.rtl
->footer
= unlink_insn_chain (NEXT_INSN (BB_END (bb
)), end
);
216 next_insn
= NEXT_INSN (BB_END (bb
));
219 cfg_layout_function_footer
= next_insn
;
220 if (cfg_layout_function_footer
)
221 cfg_layout_function_footer
= unlink_insn_chain (cfg_layout_function_footer
, get_last_insn ());
224 /* Data structures representing mapping of INSN_LOCATOR into scope blocks, line
225 numbers and files. In order to be GGC friendly we need to use separate
226 varrays. This also slightly improve the memory locality in binary search.
227 The _locs array contains locators where the given property change. The
228 block_locators_blocks contains the scope block that is used for all insn
229 locator greater than corresponding block_locators_locs value and smaller
230 than the following one. Similarly for the other properties. */
231 static VEC(int,heap
) *block_locators_locs
;
232 static GTY(()) VEC(tree
,gc
) *block_locators_blocks
;
233 static VEC(int,heap
) *locations_locators_locs
;
234 DEF_VEC_O(location_t
);
235 DEF_VEC_ALLOC_O(location_t
,heap
);
236 static VEC(location_t
,heap
) *locations_locators_vals
;
237 int prologue_locator
;
238 int epilogue_locator
;
240 /* Hold current location information and last location information, so the
241 datastructures are built lazily only when some instructions in given
243 static location_t curr_location
, last_location
;
244 static tree curr_block
, last_block
;
245 static int curr_rtl_loc
= -1;
247 /* Allocate insn locator datastructure. */
249 insn_locators_alloc (void)
251 prologue_locator
= epilogue_locator
= 0;
253 block_locators_locs
= VEC_alloc (int, heap
, 32);
254 block_locators_blocks
= VEC_alloc (tree
, gc
, 32);
255 locations_locators_locs
= VEC_alloc (int, heap
, 32);
256 locations_locators_vals
= VEC_alloc (location_t
, heap
, 32);
258 curr_location
= UNKNOWN_LOCATION
;
259 last_location
= UNKNOWN_LOCATION
;
265 /* At the end of emit stage, clear current location. */
267 insn_locators_finalize (void)
269 if (curr_rtl_loc
>= 0)
270 epilogue_locator
= curr_insn_locator ();
274 /* Allocate insn locator datastructure. */
276 insn_locators_free (void)
278 prologue_locator
= epilogue_locator
= 0;
280 VEC_free (int, heap
, block_locators_locs
);
281 VEC_free (tree
,gc
, block_locators_blocks
);
282 VEC_free (int, heap
, locations_locators_locs
);
283 VEC_free (location_t
, heap
, locations_locators_vals
);
287 /* Set current location. */
289 set_curr_insn_source_location (location_t location
)
291 /* IV opts calls into RTL expansion to compute costs of operations. At this
292 time locators are not initialized. */
293 if (curr_rtl_loc
== -1)
295 curr_location
= location
;
298 /* Get current location. */
300 get_curr_insn_source_location (void)
302 return curr_location
;
305 /* Set current scope block. */
307 set_curr_insn_block (tree b
)
309 /* IV opts calls into RTL expansion to compute costs of operations. At this
310 time locators are not initialized. */
311 if (curr_rtl_loc
== -1)
317 /* Get current scope block. */
319 get_curr_insn_block (void)
324 /* Return current insn locator. */
326 curr_insn_locator (void)
328 if (curr_rtl_loc
== -1 || curr_location
== UNKNOWN_LOCATION
)
330 if (last_block
!= curr_block
)
333 VEC_safe_push (int, heap
, block_locators_locs
, curr_rtl_loc
);
334 VEC_safe_push (tree
, gc
, block_locators_blocks
, curr_block
);
335 last_block
= curr_block
;
337 if (last_location
!= curr_location
)
340 VEC_safe_push (int, heap
, locations_locators_locs
, curr_rtl_loc
);
341 VEC_safe_push (location_t
, heap
, locations_locators_vals
, &curr_location
);
342 last_location
= curr_location
;
348 into_cfg_layout_mode (void)
350 cfg_layout_initialize (0);
355 outof_cfg_layout_mode (void)
360 if (bb
->next_bb
!= EXIT_BLOCK_PTR
)
361 bb
->aux
= bb
->next_bb
;
363 cfg_layout_finalize ();
368 struct rtl_opt_pass pass_into_cfg_layout_mode
=
372 "into_cfglayout", /* name */
374 into_cfg_layout_mode
, /* execute */
377 0, /* static_pass_number */
379 0, /* properties_required */
380 PROP_cfglayout
, /* properties_provided */
381 0, /* properties_destroyed */
382 0, /* todo_flags_start */
383 0 /* todo_flags_finish */
387 struct rtl_opt_pass pass_outof_cfg_layout_mode
=
391 "outof_cfglayout", /* name */
393 outof_cfg_layout_mode
, /* execute */
396 0, /* static_pass_number */
398 0, /* properties_required */
399 0, /* properties_provided */
400 PROP_cfglayout
, /* properties_destroyed */
401 0, /* todo_flags_start */
402 0 /* todo_flags_finish */
406 /* Return scope resulting from combination of S1 and S2. */
408 choose_inner_scope (tree s1
, tree s2
)
414 if (BLOCK_NUMBER (s1
) > BLOCK_NUMBER (s2
))
419 /* Emit lexical block notes needed to change scope from S1 to S2. */
422 change_scope (rtx orig_insn
, tree s1
, tree s2
)
424 rtx insn
= orig_insn
;
425 tree com
= NULL_TREE
;
426 tree ts1
= s1
, ts2
= s2
;
431 gcc_assert (ts1
&& ts2
);
432 if (BLOCK_NUMBER (ts1
) > BLOCK_NUMBER (ts2
))
433 ts1
= BLOCK_SUPERCONTEXT (ts1
);
434 else if (BLOCK_NUMBER (ts1
) < BLOCK_NUMBER (ts2
))
435 ts2
= BLOCK_SUPERCONTEXT (ts2
);
438 ts1
= BLOCK_SUPERCONTEXT (ts1
);
439 ts2
= BLOCK_SUPERCONTEXT (ts2
);
448 rtx note
= emit_note_before (NOTE_INSN_BLOCK_END
, insn
);
449 NOTE_BLOCK (note
) = s
;
450 s
= BLOCK_SUPERCONTEXT (s
);
457 insn
= emit_note_before (NOTE_INSN_BLOCK_BEG
, insn
);
458 NOTE_BLOCK (insn
) = s
;
459 s
= BLOCK_SUPERCONTEXT (s
);
463 /* Return lexical scope block locator belongs to. */
465 locator_scope (int loc
)
467 int max
= VEC_length (int, block_locators_locs
);
470 /* When block_locators_locs was initialized, the pro- and epilogue
471 insns didn't exist yet and can therefore not be found this way.
472 But we know that they belong to the outer most block of the
474 Without this test, the prologue would be put inside the block of
475 the first valid instruction in the function and when that first
476 insn is part of an inlined function then the low_pc of that
477 inlined function is messed up. Likewise for the epilogue and
478 the last valid instruction. */
479 if (loc
== prologue_locator
|| loc
== epilogue_locator
)
480 return DECL_INITIAL (cfun
->decl
);
486 int pos
= (min
+ max
) / 2;
487 int tmp
= VEC_index (int, block_locators_locs
, pos
);
489 if (tmp
<= loc
&& min
!= pos
)
491 else if (tmp
> loc
&& max
!= pos
)
499 return VEC_index (tree
, block_locators_blocks
, min
);
502 /* Return lexical scope block insn belongs to. */
504 insn_scope (const_rtx insn
)
506 return locator_scope (INSN_LOCATOR (insn
));
509 /* Return line number of the statement specified by the locator. */
511 locator_location (int loc
)
513 int max
= VEC_length (int, locations_locators_locs
);
518 int pos
= (min
+ max
) / 2;
519 int tmp
= VEC_index (int, locations_locators_locs
, pos
);
521 if (tmp
<= loc
&& min
!= pos
)
523 else if (tmp
> loc
&& max
!= pos
)
531 return *VEC_index (location_t
, locations_locators_vals
, min
);
534 /* Return source line of the statement that produced this insn. */
536 locator_line (int loc
)
538 expanded_location xloc
;
542 xloc
= expand_location (locator_location (loc
));
546 /* Return line number of the statement that produced this insn. */
548 insn_line (const_rtx insn
)
550 return locator_line (INSN_LOCATOR (insn
));
553 /* Return source file of the statement specified by LOC. */
555 locator_file (int loc
)
557 expanded_location xloc
;
561 xloc
= expand_location (locator_location (loc
));
565 /* Return source file of the statement that produced this insn. */
567 insn_file (const_rtx insn
)
569 return locator_file (INSN_LOCATOR (insn
));
572 /* Return true if LOC1 and LOC2 locators have the same location and scope. */
574 locator_eq (int loc1
, int loc2
)
578 if (locator_location (loc1
) != locator_location (loc2
))
580 return locator_scope (loc1
) == locator_scope (loc2
);
583 /* Rebuild all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes based
584 on the scope tree and the newly reordered instructions. */
587 reemit_insn_block_notes (void)
589 tree cur_block
= DECL_INITIAL (cfun
->decl
);
593 if (!active_insn_p (insn
))
594 insn
= next_active_insn (insn
);
595 for (; insn
; insn
= next_active_insn (insn
))
599 /* Avoid putting scope notes between jump table and its label. */
600 if (JUMP_TABLE_DATA_P (insn
))
603 this_block
= insn_scope (insn
);
604 /* For sequences compute scope resulting from merging all scopes
605 of instructions nested inside. */
606 if (GET_CODE (PATTERN (insn
)) == SEQUENCE
)
609 rtx body
= PATTERN (insn
);
612 for (i
= 0; i
< XVECLEN (body
, 0); i
++)
613 this_block
= choose_inner_scope (this_block
,
614 insn_scope (XVECEXP (body
, 0, i
)));
619 if (this_block
!= cur_block
)
621 change_scope (insn
, cur_block
, this_block
);
622 cur_block
= this_block
;
626 /* change_scope emits before the insn, not after. */
627 note
= emit_note (NOTE_INSN_DELETED
);
628 change_scope (note
, cur_block
, DECL_INITIAL (cfun
->decl
));
635 /* Link the basic blocks in the correct order, compacting the basic
636 block queue while at it. This also clears the visited flag on
637 all basic blocks. If STAY_IN_CFGLAYOUT_MODE is false, this function
638 also clears the basic block header and footer fields.
640 This function is usually called after a pass (e.g. tracer) finishes
641 some transformations while in cfglayout mode. The required sequence
642 of the basic blocks is in a linked list along the bb->aux field.
643 This functions re-links the basic block prev_bb and next_bb pointers
644 accordingly, and it compacts and renumbers the blocks. */
647 relink_block_chain (bool stay_in_cfglayout_mode
)
649 basic_block bb
, prev_bb
;
652 /* Maybe dump the re-ordered sequence. */
655 fprintf (dump_file
, "Reordered sequence:\n");
656 for (bb
= ENTRY_BLOCK_PTR
->next_bb
, index
= NUM_FIXED_BLOCKS
;
658 bb
= (basic_block
) bb
->aux
, index
++)
660 fprintf (dump_file
, " %i ", index
);
661 if (get_bb_original (bb
))
662 fprintf (dump_file
, "duplicate of %i ",
663 get_bb_original (bb
)->index
);
664 else if (forwarder_block_p (bb
)
665 && !LABEL_P (BB_HEAD (bb
)))
666 fprintf (dump_file
, "compensation ");
668 fprintf (dump_file
, "bb %i ", bb
->index
);
669 fprintf (dump_file
, " [%i]\n", bb
->frequency
);
673 /* Now reorder the blocks. */
674 prev_bb
= ENTRY_BLOCK_PTR
;
675 bb
= ENTRY_BLOCK_PTR
->next_bb
;
676 for (; bb
; prev_bb
= bb
, bb
= (basic_block
) bb
->aux
)
678 bb
->prev_bb
= prev_bb
;
679 prev_bb
->next_bb
= bb
;
681 prev_bb
->next_bb
= EXIT_BLOCK_PTR
;
682 EXIT_BLOCK_PTR
->prev_bb
= prev_bb
;
684 /* Then, clean up the aux and visited fields. */
688 bb
->il
.rtl
->visited
= 0;
689 if (!stay_in_cfglayout_mode
)
690 bb
->il
.rtl
->header
= bb
->il
.rtl
->footer
= NULL
;
693 /* Maybe reset the original copy tables, they are not valid anymore
694 when we renumber the basic blocks in compact_blocks. If we are
695 are going out of cfglayout mode, don't re-allocate the tables. */
696 free_original_copy_tables ();
697 if (stay_in_cfglayout_mode
)
698 initialize_original_copy_tables ();
700 /* Finally, put basic_block_info in the new order. */
705 /* Given a reorder chain, rearrange the code to match. */
708 fixup_reorder_chain (void)
713 if (cfg_layout_function_header
)
715 set_first_insn (cfg_layout_function_header
);
716 insn
= cfg_layout_function_header
;
717 while (NEXT_INSN (insn
))
718 insn
= NEXT_INSN (insn
);
721 /* First do the bulk reordering -- rechain the blocks without regard to
722 the needed changes to jumps and labels. */
724 for (bb
= ENTRY_BLOCK_PTR
->next_bb
; bb
; bb
= (basic_block
) bb
->aux
)
726 if (bb
->il
.rtl
->header
)
729 NEXT_INSN (insn
) = bb
->il
.rtl
->header
;
731 set_first_insn (bb
->il
.rtl
->header
);
732 PREV_INSN (bb
->il
.rtl
->header
) = insn
;
733 insn
= bb
->il
.rtl
->header
;
734 while (NEXT_INSN (insn
))
735 insn
= NEXT_INSN (insn
);
738 NEXT_INSN (insn
) = BB_HEAD (bb
);
740 set_first_insn (BB_HEAD (bb
));
741 PREV_INSN (BB_HEAD (bb
)) = insn
;
743 if (bb
->il
.rtl
->footer
)
745 NEXT_INSN (insn
) = bb
->il
.rtl
->footer
;
746 PREV_INSN (bb
->il
.rtl
->footer
) = insn
;
747 while (NEXT_INSN (insn
))
748 insn
= NEXT_INSN (insn
);
752 NEXT_INSN (insn
) = cfg_layout_function_footer
;
753 if (cfg_layout_function_footer
)
754 PREV_INSN (cfg_layout_function_footer
) = insn
;
756 while (NEXT_INSN (insn
))
757 insn
= NEXT_INSN (insn
);
759 set_last_insn (insn
);
760 #ifdef ENABLE_CHECKING
761 verify_insn_chain ();
764 /* Now add jumps and labels as needed to match the blocks new
767 for (bb
= ENTRY_BLOCK_PTR
->next_bb
; bb
; bb
= (basic_block
) bb
->aux
)
769 edge e_fall
, e_taken
, e
;
771 rtx ret_label
= NULL_RTX
;
772 basic_block nb
, src_bb
;
775 if (EDGE_COUNT (bb
->succs
) == 0)
778 /* Find the old fallthru edge, and another non-EH edge for
780 e_taken
= e_fall
= NULL
;
782 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
783 if (e
->flags
& EDGE_FALLTHRU
)
785 else if (! (e
->flags
& EDGE_EH
))
788 bb_end_insn
= BB_END (bb
);
789 if (JUMP_P (bb_end_insn
))
791 ret_label
= JUMP_LABEL (bb_end_insn
);
792 if (any_condjump_p (bb_end_insn
))
794 /* This might happen if the conditional jump has side
795 effects and could therefore not be optimized away.
796 Make the basic block to end with a barrier in order
797 to prevent rtl_verify_flow_info from complaining. */
800 gcc_assert (!onlyjump_p (bb_end_insn
)
801 || returnjump_p (bb_end_insn
));
802 bb
->il
.rtl
->footer
= emit_barrier_after (bb_end_insn
);
806 /* If the old fallthru is still next, nothing to do. */
807 if (bb
->aux
== e_fall
->dest
808 || e_fall
->dest
== EXIT_BLOCK_PTR
)
811 /* The degenerated case of conditional jump jumping to the next
812 instruction can happen for jumps with side effects. We need
813 to construct a forwarder block and this will be done just
814 fine by force_nonfallthru below. */
818 /* There is another special case: if *neither* block is next,
819 such as happens at the very end of a function, then we'll
820 need to add a new unconditional jump. Choose the taken
821 edge based on known or assumed probability. */
822 else if (bb
->aux
!= e_taken
->dest
)
824 rtx note
= find_reg_note (bb_end_insn
, REG_BR_PROB
, 0);
827 && INTVAL (XEXP (note
, 0)) < REG_BR_PROB_BASE
/ 2
828 && invert_jump (bb_end_insn
,
829 (e_fall
->dest
== EXIT_BLOCK_PTR
831 : label_for_bb (e_fall
->dest
)), 0))
833 e_fall
->flags
&= ~EDGE_FALLTHRU
;
834 gcc_checking_assert (could_fall_through
835 (e_taken
->src
, e_taken
->dest
));
836 e_taken
->flags
|= EDGE_FALLTHRU
;
837 update_br_prob_note (bb
);
838 e
= e_fall
, e_fall
= e_taken
, e_taken
= e
;
842 /* If the "jumping" edge is a crossing edge, and the fall
843 through edge is non-crossing, leave things as they are. */
844 else if ((e_taken
->flags
& EDGE_CROSSING
)
845 && !(e_fall
->flags
& EDGE_CROSSING
))
848 /* Otherwise we can try to invert the jump. This will
849 basically never fail, however, keep up the pretense. */
850 else if (invert_jump (bb_end_insn
,
851 (e_fall
->dest
== EXIT_BLOCK_PTR
853 : label_for_bb (e_fall
->dest
)), 0))
855 e_fall
->flags
&= ~EDGE_FALLTHRU
;
856 gcc_checking_assert (could_fall_through
857 (e_taken
->src
, e_taken
->dest
));
858 e_taken
->flags
|= EDGE_FALLTHRU
;
859 update_br_prob_note (bb
);
860 if (LABEL_NUSES (ret_label
) == 0
861 && single_pred_p (e_taken
->dest
))
862 delete_insn (ret_label
);
866 else if (extract_asm_operands (PATTERN (bb_end_insn
)) != NULL
)
868 /* If the old fallthru is still next or if
869 asm goto doesn't have a fallthru (e.g. when followed by
870 __builtin_unreachable ()), nothing to do. */
872 || bb
->aux
== e_fall
->dest
873 || e_fall
->dest
== EXIT_BLOCK_PTR
)
876 /* Otherwise we'll have to use the fallthru fixup below. */
880 /* Otherwise we have some return, switch or computed
881 jump. In the 99% case, there should not have been a
883 gcc_assert (returnjump_p (bb_end_insn
) || !e_fall
);
889 /* No fallthru implies a noreturn function with EH edges, or
890 something similarly bizarre. In any case, we don't need to
895 /* If the fallthru block is still next, nothing to do. */
896 if (bb
->aux
== e_fall
->dest
)
899 /* A fallthru to exit block. */
900 if (e_fall
->dest
== EXIT_BLOCK_PTR
)
904 /* We got here if we need to add a new jump insn.
905 Note force_nonfallthru can delete E_FALL and thus we have to
906 save E_FALL->src prior to the call to force_nonfallthru. */
907 src_bb
= e_fall
->src
;
908 nb
= force_nonfallthru_and_redirect (e_fall
, e_fall
->dest
, ret_label
);
911 nb
->il
.rtl
->visited
= 1;
914 /* Don't process this new block. */
917 /* Make sure new bb is tagged for correct section (same as
918 fall-thru source, since you cannot fall-thru across
919 section boundaries). */
920 BB_COPY_PARTITION (src_bb
, single_pred (bb
));
921 if (flag_reorder_blocks_and_partition
922 && targetm_common
.have_named_sections
923 && JUMP_P (BB_END (bb
))
924 && !any_condjump_p (BB_END (bb
))
925 && (EDGE_SUCC (bb
, 0)->flags
& EDGE_CROSSING
))
926 add_reg_note (BB_END (bb
), REG_CROSSING_JUMP
, NULL_RTX
);
930 relink_block_chain (/*stay_in_cfglayout_mode=*/false);
932 /* Annoying special case - jump around dead jumptables left in the code. */
935 edge e
= find_fallthru_edge (bb
->succs
);
937 if (e
&& !can_fallthru (e
->src
, e
->dest
))
938 force_nonfallthru (e
);
941 /* Ensure goto_locus from edges has some instructions with that locus
949 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
950 if (e
->goto_locus
&& !(e
->flags
& EDGE_ABNORMAL
))
954 basic_block dest
, nb
;
957 insn
= BB_END (e
->src
);
958 end
= PREV_INSN (BB_HEAD (e
->src
));
960 && (!NONDEBUG_INSN_P (insn
) || INSN_LOCATOR (insn
) == 0))
961 insn
= PREV_INSN (insn
);
963 && locator_eq (INSN_LOCATOR (insn
), (int) e
->goto_locus
))
965 if (simplejump_p (BB_END (e
->src
))
966 && INSN_LOCATOR (BB_END (e
->src
)) == 0)
968 INSN_LOCATOR (BB_END (e
->src
)) = e
->goto_locus
;
972 if (dest
== EXIT_BLOCK_PTR
)
974 /* Non-fallthru edges to the exit block cannot be split. */
975 if (!(e
->flags
& EDGE_FALLTHRU
))
980 insn
= BB_HEAD (dest
);
981 end
= NEXT_INSN (BB_END (dest
));
982 while (insn
!= end
&& !NONDEBUG_INSN_P (insn
))
983 insn
= NEXT_INSN (insn
);
984 if (insn
!= end
&& INSN_LOCATOR (insn
)
985 && locator_eq (INSN_LOCATOR (insn
), (int) e
->goto_locus
))
989 if (!INSN_P (BB_END (nb
)))
990 BB_END (nb
) = emit_insn_after_noloc (gen_nop (), BB_END (nb
),
992 INSN_LOCATOR (BB_END (nb
)) = e
->goto_locus
;
994 /* If there are other incoming edges to the destination block
995 with the same goto locus, redirect them to the new block as
996 well, this can prevent other such blocks from being created
997 in subsequent iterations of the loop. */
998 for (ei2
= ei_start (dest
->preds
); (e2
= ei_safe_edge (ei2
)); )
1000 && !(e2
->flags
& (EDGE_ABNORMAL
| EDGE_FALLTHRU
))
1001 && locator_eq (e
->goto_locus
, e2
->goto_locus
))
1002 redirect_edge_and_branch (e2
, nb
);
1009 /* Perform sanity checks on the insn chain.
1010 1. Check that next/prev pointers are consistent in both the forward and
1012 2. Count insns in chain, going both directions, and check if equal.
1013 3. Check that get_last_insn () returns the actual end of chain. */
1016 verify_insn_chain (void)
1018 rtx x
, prevx
, nextx
;
1019 int insn_cnt1
, insn_cnt2
;
1021 for (prevx
= NULL
, insn_cnt1
= 1, x
= get_insns ();
1023 prevx
= x
, insn_cnt1
++, x
= NEXT_INSN (x
))
1024 gcc_assert (PREV_INSN (x
) == prevx
);
1026 gcc_assert (prevx
== get_last_insn ());
1028 for (nextx
= NULL
, insn_cnt2
= 1, x
= get_last_insn ();
1030 nextx
= x
, insn_cnt2
++, x
= PREV_INSN (x
))
1031 gcc_assert (NEXT_INSN (x
) == nextx
);
1033 gcc_assert (insn_cnt1
== insn_cnt2
);
1036 /* If we have assembler epilogues, the block falling through to exit must
1037 be the last one in the reordered chain when we reach final. Ensure
1038 that this condition is met. */
1040 fixup_fallthru_exit_predecessor (void)
1043 basic_block bb
= NULL
;
1045 /* This transformation is not valid before reload, because we might
1046 separate a call from the instruction that copies the return
1048 gcc_assert (reload_completed
);
1050 e
= find_fallthru_edge (EXIT_BLOCK_PTR
->preds
);
1056 basic_block c
= ENTRY_BLOCK_PTR
->next_bb
;
1058 /* If the very first block is the one with the fall-through exit
1059 edge, we have to split that block. */
1062 bb
= split_block (bb
, NULL
)->dest
;
1065 bb
->il
.rtl
->footer
= c
->il
.rtl
->footer
;
1066 c
->il
.rtl
->footer
= NULL
;
1069 while (c
->aux
!= bb
)
1070 c
= (basic_block
) c
->aux
;
1074 c
= (basic_block
) c
->aux
;
1081 /* In case there are more than one fallthru predecessors of exit, force that
1082 there is only one. */
1085 force_one_exit_fallthru (void)
1087 edge e
, predecessor
= NULL
;
1090 basic_block forwarder
, bb
;
1092 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
1093 if (e
->flags
& EDGE_FALLTHRU
)
1095 if (predecessor
== NULL
)
1107 /* Exit has several fallthru predecessors. Create a forwarder block for
1109 forwarder
= split_edge (predecessor
);
1110 for (ei
= ei_start (EXIT_BLOCK_PTR
->preds
); (e
= ei_safe_edge (ei
)); )
1112 if (e
->src
== forwarder
1113 || !(e
->flags
& EDGE_FALLTHRU
))
1116 redirect_edge_and_branch_force (e
, forwarder
);
1119 /* Fix up the chain of blocks -- make FORWARDER immediately precede the
1123 if (bb
->aux
== NULL
&& bb
!= forwarder
)
1125 bb
->aux
= forwarder
;
1131 /* Return true in case it is possible to duplicate the basic block BB. */
1133 /* We do not want to declare the function in a header file, since it should
1134 only be used through the cfghooks interface, and we do not want to move
1135 it to cfgrtl.c since it would require also moving quite a lot of related
1137 extern bool cfg_layout_can_duplicate_bb_p (const_basic_block
);
1140 cfg_layout_can_duplicate_bb_p (const_basic_block bb
)
1142 /* Do not attempt to duplicate tablejumps, as we need to unshare
1143 the dispatch table. This is difficult to do, as the instructions
1144 computing jump destination may be hoisted outside the basic block. */
1145 if (tablejump_p (BB_END (bb
), NULL
, NULL
))
1148 /* Do not duplicate blocks containing insns that can't be copied. */
1149 if (targetm
.cannot_copy_insn_p
)
1151 rtx insn
= BB_HEAD (bb
);
1154 if (INSN_P (insn
) && targetm
.cannot_copy_insn_p (insn
))
1156 if (insn
== BB_END (bb
))
1158 insn
= NEXT_INSN (insn
);
1166 duplicate_insn_chain (rtx from
, rtx to
)
1168 rtx insn
, last
, copy
;
1170 /* Avoid updating of boundaries of previous basic block. The
1171 note will get removed from insn stream in fixup. */
1172 last
= emit_note (NOTE_INSN_DELETED
);
1174 /* Create copy at the end of INSN chain. The chain will
1175 be reordered later. */
1176 for (insn
= from
; insn
!= NEXT_INSN (to
); insn
= NEXT_INSN (insn
))
1178 switch (GET_CODE (insn
))
1181 /* Don't duplicate label debug insns. */
1182 if (TREE_CODE (INSN_VAR_LOCATION_DECL (insn
)) == LABEL_DECL
)
1188 /* Avoid copying of dispatch tables. We never duplicate
1189 tablejumps, so this can hit only in case the table got
1190 moved far from original jump. */
1191 if (GET_CODE (PATTERN (insn
)) == ADDR_VEC
1192 || GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
)
1194 /* Avoid copying following barrier as well if any
1195 (and debug insns in between). */
1198 for (next
= NEXT_INSN (insn
);
1199 next
!= NEXT_INSN (to
);
1200 next
= NEXT_INSN (next
))
1201 if (!DEBUG_INSN_P (next
))
1203 if (next
!= NEXT_INSN (to
) && BARRIER_P (next
))
1207 copy
= emit_copy_of_insn_after (insn
, get_last_insn ());
1208 if (JUMP_P (insn
) && JUMP_LABEL (insn
) != NULL_RTX
1209 && ANY_RETURN_P (JUMP_LABEL (insn
)))
1210 JUMP_LABEL (copy
) = JUMP_LABEL (insn
);
1211 maybe_copy_prologue_epilogue_insn (insn
, copy
);
1222 switch (NOTE_KIND (insn
))
1224 /* In case prologue is empty and function contain label
1225 in first BB, we may want to copy the block. */
1226 case NOTE_INSN_PROLOGUE_END
:
1228 case NOTE_INSN_DELETED
:
1229 case NOTE_INSN_DELETED_LABEL
:
1230 case NOTE_INSN_DELETED_DEBUG_LABEL
:
1231 /* No problem to strip these. */
1232 case NOTE_INSN_FUNCTION_BEG
:
1233 /* There is always just single entry to function. */
1234 case NOTE_INSN_BASIC_BLOCK
:
1237 case NOTE_INSN_EPILOGUE_BEG
:
1238 case NOTE_INSN_SWITCH_TEXT_SECTIONS
:
1239 emit_note_copy (insn
);
1243 /* All other notes should have already been eliminated. */
1251 insn
= NEXT_INSN (last
);
1255 /* Create a duplicate of the basic block BB. */
1257 /* We do not want to declare the function in a header file, since it should
1258 only be used through the cfghooks interface, and we do not want to move
1259 it to cfgrtl.c since it would require also moving quite a lot of related
1261 extern basic_block
cfg_layout_duplicate_bb (basic_block
);
1264 cfg_layout_duplicate_bb (basic_block bb
)
1269 insn
= duplicate_insn_chain (BB_HEAD (bb
), BB_END (bb
));
1270 new_bb
= create_basic_block (insn
,
1271 insn
? get_last_insn () : NULL
,
1272 EXIT_BLOCK_PTR
->prev_bb
);
1274 BB_COPY_PARTITION (new_bb
, bb
);
1275 if (bb
->il
.rtl
->header
)
1277 insn
= bb
->il
.rtl
->header
;
1278 while (NEXT_INSN (insn
))
1279 insn
= NEXT_INSN (insn
);
1280 insn
= duplicate_insn_chain (bb
->il
.rtl
->header
, insn
);
1282 new_bb
->il
.rtl
->header
= unlink_insn_chain (insn
, get_last_insn ());
1285 if (bb
->il
.rtl
->footer
)
1287 insn
= bb
->il
.rtl
->footer
;
1288 while (NEXT_INSN (insn
))
1289 insn
= NEXT_INSN (insn
);
1290 insn
= duplicate_insn_chain (bb
->il
.rtl
->footer
, insn
);
1292 new_bb
->il
.rtl
->footer
= unlink_insn_chain (insn
, get_last_insn ());
1299 /* Main entry point to this module - initialize the datastructures for
1300 CFG layout changes. It keeps LOOPS up-to-date if not null.
1302 FLAGS is a set of additional flags to pass to cleanup_cfg(). */
1305 cfg_layout_initialize (unsigned int flags
)
1310 initialize_original_copy_tables ();
1312 cfg_layout_rtl_register_cfg_hooks ();
1314 record_effective_endpoints ();
1316 /* Make sure that the targets of non local gotos are marked. */
1317 for (x
= nonlocal_goto_handler_labels
; x
; x
= XEXP (x
, 1))
1319 bb
= BLOCK_FOR_INSN (XEXP (x
, 0));
1320 bb
->flags
|= BB_NON_LOCAL_GOTO_TARGET
;
1323 cleanup_cfg (CLEANUP_CFGLAYOUT
| flags
);
1326 /* Splits superblocks. */
1328 break_superblocks (void)
1330 sbitmap superblocks
;
1334 superblocks
= sbitmap_alloc (last_basic_block
);
1335 sbitmap_zero (superblocks
);
1338 if (bb
->flags
& BB_SUPERBLOCK
)
1340 bb
->flags
&= ~BB_SUPERBLOCK
;
1341 SET_BIT (superblocks
, bb
->index
);
1347 rebuild_jump_labels (get_insns ());
1348 find_many_sub_basic_blocks (superblocks
);
1354 /* Finalize the changes: reorder insn list according to the sequence specified
1355 by aux pointers, enter compensation code, rebuild scope forest. */
1358 cfg_layout_finalize (void)
1360 #ifdef ENABLE_CHECKING
1361 verify_flow_info ();
1363 force_one_exit_fallthru ();
1364 rtl_register_cfg_hooks ();
1365 if (reload_completed
1366 #ifdef HAVE_epilogue
1370 fixup_fallthru_exit_predecessor ();
1371 fixup_reorder_chain ();
1373 rebuild_jump_labels (get_insns ());
1374 delete_dead_jumptables ();
1376 #ifdef ENABLE_CHECKING
1377 verify_insn_chain ();
1378 verify_flow_info ();
1382 /* Checks whether all N blocks in BBS array can be copied. */
1384 can_copy_bbs_p (basic_block
*bbs
, unsigned n
)
1390 for (i
= 0; i
< n
; i
++)
1391 bbs
[i
]->flags
|= BB_DUPLICATED
;
1393 for (i
= 0; i
< n
; i
++)
1395 /* In case we should redirect abnormal edge during duplication, fail. */
1397 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
1398 if ((e
->flags
& EDGE_ABNORMAL
)
1399 && (e
->dest
->flags
& BB_DUPLICATED
))
1405 if (!can_duplicate_block_p (bbs
[i
]))
1413 for (i
= 0; i
< n
; i
++)
1414 bbs
[i
]->flags
&= ~BB_DUPLICATED
;
1419 /* Duplicates N basic blocks stored in array BBS. Newly created basic blocks
1420 are placed into array NEW_BBS in the same order. Edges from basic blocks
1421 in BBS are also duplicated and copies of those of them
1422 that lead into BBS are redirected to appropriate newly created block. The
1423 function assigns bbs into loops (copy of basic block bb is assigned to
1424 bb->loop_father->copy loop, so this must be set up correctly in advance)
1425 and updates dominators locally (LOOPS structure that contains the information
1426 about dominators is passed to enable this).
1428 BASE is the superloop to that basic block belongs; if its header or latch
1429 is copied, we do not set the new blocks as header or latch.
1431 Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
1432 also in the same order.
1434 Newly created basic blocks are put after the basic block AFTER in the
1435 instruction stream, and the order of the blocks in BBS array is preserved. */
1438 copy_bbs (basic_block
*bbs
, unsigned n
, basic_block
*new_bbs
,
1439 edge
*edges
, unsigned num_edges
, edge
*new_edges
,
1440 struct loop
*base
, basic_block after
)
1443 basic_block bb
, new_bb
, dom_bb
;
1446 /* Duplicate bbs, update dominators, assign bbs to loops. */
1447 for (i
= 0; i
< n
; i
++)
1451 new_bb
= new_bbs
[i
] = duplicate_block (bb
, NULL
, after
);
1453 bb
->flags
|= BB_DUPLICATED
;
1454 /* Possibly set loop header. */
1455 if (bb
->loop_father
->header
== bb
&& bb
->loop_father
!= base
)
1456 new_bb
->loop_father
->header
= new_bb
;
1458 if (bb
->loop_father
->latch
== bb
&& bb
->loop_father
!= base
)
1459 new_bb
->loop_father
->latch
= new_bb
;
1462 /* Set dominators. */
1463 for (i
= 0; i
< n
; i
++)
1466 new_bb
= new_bbs
[i
];
1468 dom_bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1469 if (dom_bb
->flags
& BB_DUPLICATED
)
1471 dom_bb
= get_bb_copy (dom_bb
);
1472 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, dom_bb
);
1476 /* Redirect edges. */
1477 for (j
= 0; j
< num_edges
; j
++)
1478 new_edges
[j
] = NULL
;
1479 for (i
= 0; i
< n
; i
++)
1482 new_bb
= new_bbs
[i
];
1485 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
1487 for (j
= 0; j
< num_edges
; j
++)
1488 if (edges
[j
] && edges
[j
]->src
== bb
&& edges
[j
]->dest
== e
->dest
)
1491 if (!(e
->dest
->flags
& BB_DUPLICATED
))
1493 redirect_edge_and_branch_force (e
, get_bb_copy (e
->dest
));
1497 /* Clear information about duplicates. */
1498 for (i
= 0; i
< n
; i
++)
1499 bbs
[i
]->flags
&= ~BB_DUPLICATED
;
1502 #include "gt-cfglayout.h"