1 /* Basic block reordering routines for the GNU compiler.
2 Copyright (C) 2000, 2001, 2003, 2004, 2005 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 2, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to the Free
18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
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"
40 /* Holds the interesting trailing notes for the function. */
41 rtx cfg_layout_function_footer
, cfg_layout_function_header
;
43 static rtx
skip_insns_after_block (basic_block
);
44 static void record_effective_endpoints (void);
45 static rtx
label_for_bb (basic_block
);
46 static void fixup_reorder_chain (void);
48 static void set_block_levels (tree
, int);
49 static void change_scope (rtx
, tree
, tree
);
51 void verify_insn_chain (void);
52 static void fixup_fallthru_exit_predecessor (void);
53 static tree
insn_scope (rtx
);
54 static void update_unlikely_executed_notes (basic_block
);
57 unlink_insn_chain (rtx first
, rtx last
)
59 rtx prevfirst
= PREV_INSN (first
);
60 rtx nextlast
= NEXT_INSN (last
);
62 PREV_INSN (first
) = NULL
;
63 NEXT_INSN (last
) = NULL
;
65 NEXT_INSN (prevfirst
) = nextlast
;
67 PREV_INSN (nextlast
) = prevfirst
;
69 set_last_insn (prevfirst
);
71 set_first_insn (nextlast
);
75 /* Skip over inter-block insns occurring after BB which are typically
76 associated with BB (e.g., barriers). If there are any such insns,
77 we return the last one. Otherwise, we return the end of BB. */
80 skip_insns_after_block (basic_block bb
)
82 rtx insn
, last_insn
, next_head
, prev
;
85 if (bb
->next_bb
!= EXIT_BLOCK_PTR
)
86 next_head
= BB_HEAD (bb
->next_bb
);
88 for (last_insn
= insn
= BB_END (bb
); (insn
= NEXT_INSN (insn
)) != 0; )
90 if (insn
== next_head
)
93 switch (GET_CODE (insn
))
100 switch (NOTE_LINE_NUMBER (insn
))
102 case NOTE_INSN_LOOP_END
:
103 case NOTE_INSN_BLOCK_END
:
106 case NOTE_INSN_DELETED
:
107 case NOTE_INSN_DELETED_LABEL
:
118 && JUMP_P (NEXT_INSN (insn
))
119 && (GET_CODE (PATTERN (NEXT_INSN (insn
))) == ADDR_VEC
120 || GET_CODE (PATTERN (NEXT_INSN (insn
))) == ADDR_DIFF_VEC
))
122 insn
= NEXT_INSN (insn
);
135 /* It is possible to hit contradictory sequence. For instance:
141 Where barrier belongs to jump_insn, but the note does not. This can be
142 created by removing the basic block originally following
143 NOTE_INSN_LOOP_BEG. In such case reorder the notes. */
145 for (insn
= last_insn
; insn
!= BB_END (bb
); insn
= prev
)
147 prev
= PREV_INSN (insn
);
149 switch (NOTE_LINE_NUMBER (insn
))
151 case NOTE_INSN_LOOP_END
:
152 case NOTE_INSN_BLOCK_END
:
153 case NOTE_INSN_DELETED
:
154 case NOTE_INSN_DELETED_LABEL
:
157 reorder_insns (insn
, insn
, last_insn
);
164 /* Locate or create a label for a given basic block. */
167 label_for_bb (basic_block bb
)
169 rtx label
= BB_HEAD (bb
);
171 if (!LABEL_P (label
))
174 fprintf (dump_file
, "Emitting label for block %d\n", bb
->index
);
176 label
= block_label (bb
);
182 /* Locate the effective beginning and end of the insn chain for each
183 block, as defined by skip_insns_after_block above. */
186 record_effective_endpoints (void)
192 for (insn
= get_insns ();
195 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_BASIC_BLOCK
;
196 insn
= NEXT_INSN (insn
))
198 /* No basic blocks at all? */
201 if (PREV_INSN (insn
))
202 cfg_layout_function_header
=
203 unlink_insn_chain (get_insns (), PREV_INSN (insn
));
205 cfg_layout_function_header
= NULL_RTX
;
207 next_insn
= get_insns ();
212 if (PREV_INSN (BB_HEAD (bb
)) && next_insn
!= BB_HEAD (bb
))
213 bb
->rbi
->header
= unlink_insn_chain (next_insn
,
214 PREV_INSN (BB_HEAD (bb
)));
215 end
= skip_insns_after_block (bb
);
216 if (NEXT_INSN (BB_END (bb
)) && BB_END (bb
) != end
)
217 bb
->rbi
->footer
= unlink_insn_chain (NEXT_INSN (BB_END (bb
)), end
);
218 next_insn
= NEXT_INSN (BB_END (bb
));
221 cfg_layout_function_footer
= next_insn
;
222 if (cfg_layout_function_footer
)
223 cfg_layout_function_footer
= unlink_insn_chain (cfg_layout_function_footer
, get_last_insn ());
226 /* Data structures representing mapping of INSN_LOCATOR into scope blocks, line
227 numbers and files. In order to be GGC friendly we need to use separate
228 varrays. This also slightly improve the memory locality in binary search.
229 The _locs array contains locators where the given property change. The
230 block_locators_blocks contains the scope block that is used for all insn
231 locator greater than corresponding block_locators_locs value and smaller
232 than the following one. Similarly for the other properties. */
233 static GTY(()) varray_type block_locators_locs
;
234 static GTY(()) varray_type block_locators_blocks
;
235 static GTY(()) varray_type line_locators_locs
;
236 static GTY(()) varray_type line_locators_lines
;
237 static GTY(()) varray_type file_locators_locs
;
238 static GTY(()) varray_type file_locators_files
;
239 int prologue_locator
;
240 int epilogue_locator
;
242 /* During the RTL expansion the lexical blocks and line numbers are
243 represented via INSN_NOTEs. Replace them by representation using
247 insn_locators_initialize (void)
250 tree last_block
= NULL
;
253 int line_number
= 0, last_line_number
= 0;
254 const char *file_name
= NULL
, *last_file_name
= NULL
;
256 prologue_locator
= epilogue_locator
= 0;
258 VARRAY_INT_INIT (block_locators_locs
, 32, "block_locators_locs");
259 VARRAY_TREE_INIT (block_locators_blocks
, 32, "block_locators_blocks");
260 VARRAY_INT_INIT (line_locators_locs
, 32, "line_locators_locs");
261 VARRAY_INT_INIT (line_locators_lines
, 32, "line_locators_lines");
262 VARRAY_INT_INIT (file_locators_locs
, 32, "file_locators_locs");
263 VARRAY_CHAR_PTR_INIT (file_locators_files
, 32, "file_locators_files");
265 for (insn
= get_insns (); insn
; insn
= next
)
269 next
= NEXT_INSN (insn
);
273 gcc_assert (NOTE_LINE_NUMBER (insn
) != NOTE_INSN_BLOCK_BEG
274 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_BLOCK_END
);
275 if (NOTE_LINE_NUMBER (insn
) > 0)
277 expanded_location xloc
;
278 NOTE_EXPANDED_LOCATION (xloc
, insn
);
279 line_number
= xloc
.line
;
280 file_name
= xloc
.file
;
284 active
= (active_insn_p (insn
)
285 && GET_CODE (PATTERN (insn
)) != ADDR_VEC
286 && GET_CODE (PATTERN (insn
)) != ADDR_DIFF_VEC
);
288 check_block_change (insn
, &block
);
292 || (!prologue_locator
&& file_name
))
294 if (last_block
!= block
)
297 VARRAY_PUSH_INT (block_locators_locs
, loc
);
298 VARRAY_PUSH_TREE (block_locators_blocks
, block
);
301 if (last_line_number
!= line_number
)
304 VARRAY_PUSH_INT (line_locators_locs
, loc
);
305 VARRAY_PUSH_INT (line_locators_lines
, line_number
);
306 last_line_number
= line_number
;
308 if (last_file_name
!= file_name
)
311 VARRAY_PUSH_INT (file_locators_locs
, loc
);
312 VARRAY_PUSH_CHAR_PTR (file_locators_files
, (char *) file_name
);
313 last_file_name
= file_name
;
315 if (!prologue_locator
&& file_name
)
316 prologue_locator
= loc
;
318 epilogue_locator
= loc
;
320 INSN_LOCATOR (insn
) = loc
;
324 /* Tag the blocks with a depth number so that change_scope can find
325 the common parent easily. */
326 set_block_levels (DECL_INITIAL (cfun
->decl
), 0);
328 free_block_changes ();
331 /* For each lexical block, set BLOCK_NUMBER to the depth at which it is
332 found in the block tree. */
335 set_block_levels (tree block
, int level
)
339 BLOCK_NUMBER (block
) = level
;
340 set_block_levels (BLOCK_SUBBLOCKS (block
), level
+ 1);
341 block
= BLOCK_CHAIN (block
);
345 /* Return sope resulting from combination of S1 and S2. */
347 choose_inner_scope (tree s1
, tree s2
)
353 if (BLOCK_NUMBER (s1
) > BLOCK_NUMBER (s2
))
358 /* Emit lexical block notes needed to change scope from S1 to S2. */
361 change_scope (rtx orig_insn
, tree s1
, tree s2
)
363 rtx insn
= orig_insn
;
364 tree com
= NULL_TREE
;
365 tree ts1
= s1
, ts2
= s2
;
370 gcc_assert (ts1
&& ts2
);
371 if (BLOCK_NUMBER (ts1
) > BLOCK_NUMBER (ts2
))
372 ts1
= BLOCK_SUPERCONTEXT (ts1
);
373 else if (BLOCK_NUMBER (ts1
) < BLOCK_NUMBER (ts2
))
374 ts2
= BLOCK_SUPERCONTEXT (ts2
);
377 ts1
= BLOCK_SUPERCONTEXT (ts1
);
378 ts2
= BLOCK_SUPERCONTEXT (ts2
);
387 rtx note
= emit_note_before (NOTE_INSN_BLOCK_END
, insn
);
388 NOTE_BLOCK (note
) = s
;
389 s
= BLOCK_SUPERCONTEXT (s
);
396 insn
= emit_note_before (NOTE_INSN_BLOCK_BEG
, insn
);
397 NOTE_BLOCK (insn
) = s
;
398 s
= BLOCK_SUPERCONTEXT (s
);
402 /* Return lexical scope block insn belong to. */
404 insn_scope (rtx insn
)
406 int max
= VARRAY_ACTIVE_SIZE (block_locators_locs
);
408 int loc
= INSN_LOCATOR (insn
);
410 /* When block_locators_locs was initialized, the pro- and epilogue
411 insns didn't exist yet and can therefore not be found this way.
412 But we know that they belong to the outer most block of the
414 Without this test, the prologue would be put inside the block of
415 the first valid instruction in the function and when that first
416 insn is part of an inlined function then the low_pc of that
417 inlined function is messed up. Likewise for the epilogue and
418 the last valid instruction. */
419 if (loc
== prologue_locator
|| loc
== epilogue_locator
)
420 return DECL_INITIAL (cfun
->decl
);
426 int pos
= (min
+ max
) / 2;
427 int tmp
= VARRAY_INT (block_locators_locs
, pos
);
429 if (tmp
<= loc
&& min
!= pos
)
431 else if (tmp
> loc
&& max
!= pos
)
439 return VARRAY_TREE (block_locators_blocks
, min
);
442 /* Return line number of the statement specified by the locator. */
444 locator_line (int loc
)
446 int max
= VARRAY_ACTIVE_SIZE (line_locators_locs
);
453 int pos
= (min
+ max
) / 2;
454 int tmp
= VARRAY_INT (line_locators_locs
, pos
);
456 if (tmp
<= loc
&& min
!= pos
)
458 else if (tmp
> loc
&& max
!= pos
)
466 return VARRAY_INT (line_locators_lines
, min
);
469 /* Return line number of the statement that produced this insn. */
473 return locator_line (INSN_LOCATOR (insn
));
476 /* Return source file of the statement specified by LOC. */
478 locator_file (int loc
)
480 int max
= VARRAY_ACTIVE_SIZE (file_locators_locs
);
487 int pos
= (min
+ max
) / 2;
488 int tmp
= VARRAY_INT (file_locators_locs
, pos
);
490 if (tmp
<= loc
&& min
!= pos
)
492 else if (tmp
> loc
&& max
!= pos
)
500 return VARRAY_CHAR_PTR (file_locators_files
, min
);
503 /* Return source file of the statement that produced this insn. */
507 return locator_file (INSN_LOCATOR (insn
));
510 /* Rebuild all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes based
511 on the scope tree and the newly reordered instructions. */
514 reemit_insn_block_notes (void)
516 tree cur_block
= DECL_INITIAL (cfun
->decl
);
520 if (!active_insn_p (insn
))
521 insn
= next_active_insn (insn
);
522 for (; insn
; insn
= next_active_insn (insn
))
526 /* Avoid putting scope notes between jump table and its label. */
528 && (GET_CODE (PATTERN (insn
)) == ADDR_VEC
529 || GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
))
532 this_block
= insn_scope (insn
);
533 /* For sequences compute scope resulting from merging all scopes
534 of instructions nested inside. */
535 if (GET_CODE (PATTERN (insn
)) == SEQUENCE
)
538 rtx body
= PATTERN (insn
);
541 for (i
= 0; i
< XVECLEN (body
, 0); i
++)
542 this_block
= choose_inner_scope (this_block
,
543 insn_scope (XVECEXP (body
, 0, i
)));
548 if (this_block
!= cur_block
)
550 change_scope (insn
, cur_block
, this_block
);
551 cur_block
= this_block
;
555 /* change_scope emits before the insn, not after. */
556 note
= emit_note (NOTE_INSN_DELETED
);
557 change_scope (note
, cur_block
, DECL_INITIAL (cfun
->decl
));
563 /* Given a reorder chain, rearrange the code to match. */
566 fixup_reorder_chain (void)
568 basic_block bb
, prev_bb
;
572 if (cfg_layout_function_header
)
574 set_first_insn (cfg_layout_function_header
);
575 insn
= cfg_layout_function_header
;
576 while (NEXT_INSN (insn
))
577 insn
= NEXT_INSN (insn
);
580 /* First do the bulk reordering -- rechain the blocks without regard to
581 the needed changes to jumps and labels. */
583 for (bb
= ENTRY_BLOCK_PTR
->next_bb
, index
= 0;
585 bb
= bb
->rbi
->next
, index
++)
590 NEXT_INSN (insn
) = bb
->rbi
->header
;
592 set_first_insn (bb
->rbi
->header
);
593 PREV_INSN (bb
->rbi
->header
) = insn
;
594 insn
= bb
->rbi
->header
;
595 while (NEXT_INSN (insn
))
596 insn
= NEXT_INSN (insn
);
599 NEXT_INSN (insn
) = BB_HEAD (bb
);
601 set_first_insn (BB_HEAD (bb
));
602 PREV_INSN (BB_HEAD (bb
)) = insn
;
606 NEXT_INSN (insn
) = bb
->rbi
->footer
;
607 PREV_INSN (bb
->rbi
->footer
) = insn
;
608 while (NEXT_INSN (insn
))
609 insn
= NEXT_INSN (insn
);
613 gcc_assert (index
== n_basic_blocks
);
615 NEXT_INSN (insn
) = cfg_layout_function_footer
;
616 if (cfg_layout_function_footer
)
617 PREV_INSN (cfg_layout_function_footer
) = insn
;
619 while (NEXT_INSN (insn
))
620 insn
= NEXT_INSN (insn
);
622 set_last_insn (insn
);
623 #ifdef ENABLE_CHECKING
624 verify_insn_chain ();
626 delete_dead_jumptables ();
628 /* Now add jumps and labels as needed to match the blocks new
631 for (bb
= ENTRY_BLOCK_PTR
->next_bb
; bb
; bb
= bb
->rbi
->next
)
633 edge e_fall
, e_taken
, e
;
638 if (EDGE_COUNT (bb
->succs
) == 0)
641 /* Find the old fallthru edge, and another non-EH edge for
643 e_taken
= e_fall
= NULL
;
645 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
646 if (e
->flags
& EDGE_FALLTHRU
)
648 else if (! (e
->flags
& EDGE_EH
))
651 bb_end_insn
= BB_END (bb
);
652 if (JUMP_P (bb_end_insn
))
654 if (any_condjump_p (bb_end_insn
))
656 /* If the old fallthru is still next, nothing to do. */
657 if (bb
->rbi
->next
== e_fall
->dest
658 || e_fall
->dest
== EXIT_BLOCK_PTR
)
661 /* The degenerated case of conditional jump jumping to the next
662 instruction can happen on target having jumps with side
665 Create temporarily the duplicated edge representing branch.
666 It will get unidentified by force_nonfallthru_and_redirect
667 that would otherwise get confused by fallthru edge not pointing
668 to the next basic block. */
675 e_fake
= unchecked_make_edge (bb
, e_fall
->dest
, 0);
677 redirected
= redirect_jump (BB_END (bb
),
678 block_label (bb
), 0);
679 gcc_assert (redirected
);
681 note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
);
684 int prob
= INTVAL (XEXP (note
, 0));
686 e_fake
->probability
= prob
;
687 e_fake
->count
= e_fall
->count
* prob
/ REG_BR_PROB_BASE
;
688 e_fall
->probability
-= e_fall
->probability
;
689 e_fall
->count
-= e_fake
->count
;
690 if (e_fall
->probability
< 0)
691 e_fall
->probability
= 0;
692 if (e_fall
->count
< 0)
696 /* There is one special case: if *neither* block is next,
697 such as happens at the very end of a function, then we'll
698 need to add a new unconditional jump. Choose the taken
699 edge based on known or assumed probability. */
700 else if (bb
->rbi
->next
!= e_taken
->dest
)
702 rtx note
= find_reg_note (bb_end_insn
, REG_BR_PROB
, 0);
705 && INTVAL (XEXP (note
, 0)) < REG_BR_PROB_BASE
/ 2
706 && invert_jump (bb_end_insn
,
707 (e_fall
->dest
== EXIT_BLOCK_PTR
709 : label_for_bb (e_fall
->dest
)), 0))
711 e_fall
->flags
&= ~EDGE_FALLTHRU
;
712 #ifdef ENABLE_CHECKING
713 gcc_assert (could_fall_through
714 (e_taken
->src
, e_taken
->dest
));
716 e_taken
->flags
|= EDGE_FALLTHRU
;
717 update_br_prob_note (bb
);
718 e
= e_fall
, e_fall
= e_taken
, e_taken
= e
;
722 /* If the "jumping" edge is a crossing edge, and the fall
723 through edge is non-crossing, leave things as they are. */
724 else if ((e_taken
->flags
& EDGE_CROSSING
)
725 && !(e_fall
->flags
& EDGE_CROSSING
))
728 /* Otherwise we can try to invert the jump. This will
729 basically never fail, however, keep up the pretense. */
730 else if (invert_jump (bb_end_insn
,
731 (e_fall
->dest
== EXIT_BLOCK_PTR
733 : label_for_bb (e_fall
->dest
)), 0))
735 e_fall
->flags
&= ~EDGE_FALLTHRU
;
736 #ifdef ENABLE_CHECKING
737 gcc_assert (could_fall_through
738 (e_taken
->src
, e_taken
->dest
));
740 e_taken
->flags
|= EDGE_FALLTHRU
;
741 update_br_prob_note (bb
);
747 /* Otherwise we have some return, switch or computed
748 jump. In the 99% case, there should not have been a
750 gcc_assert (returnjump_p (bb_end_insn
) || !e_fall
);
756 /* No fallthru implies a noreturn function with EH edges, or
757 something similarly bizarre. In any case, we don't need to
762 /* If the fallthru block is still next, nothing to do. */
763 if (bb
->rbi
->next
== e_fall
->dest
)
766 /* A fallthru to exit block. */
767 if (e_fall
->dest
== EXIT_BLOCK_PTR
)
771 /* We got here if we need to add a new jump insn. */
772 nb
= force_nonfallthru (e_fall
);
775 initialize_bb_rbi (nb
);
776 nb
->rbi
->visited
= 1;
777 nb
->rbi
->next
= bb
->rbi
->next
;
779 /* Don't process this new block. */
782 /* Make sure new bb is tagged for correct section (same as
783 fall-thru source, since you cannot fall-throu across
784 section boundaries). */
785 BB_COPY_PARTITION (e_fall
->src
, single_pred (bb
));
786 if (flag_reorder_blocks_and_partition
787 && targetm
.have_named_sections
)
789 if (BB_PARTITION (single_pred (bb
)) == BB_COLD_PARTITION
)
792 rtx note
= BB_HEAD (e_fall
->src
);
794 while (!INSN_P (note
)
795 && note
!= BB_END (e_fall
->src
))
796 note
= NEXT_INSN (note
);
798 new_note
= emit_note_before
799 (NOTE_INSN_UNLIKELY_EXECUTED_CODE
,
801 NOTE_BASIC_BLOCK (new_note
) = bb
;
803 if (JUMP_P (BB_END (bb
))
804 && !any_condjump_p (BB_END (bb
))
805 && (single_succ_edge (bb
)->flags
& EDGE_CROSSING
))
806 REG_NOTES (BB_END (bb
)) = gen_rtx_EXPR_LIST
807 (REG_CROSSING_JUMP
, NULL_RTX
, REG_NOTES (BB_END (bb
)));
812 /* Put basic_block_info in the new order. */
816 fprintf (dump_file
, "Reordered sequence:\n");
817 for (bb
= ENTRY_BLOCK_PTR
->next_bb
, index
= 0;
819 bb
= bb
->rbi
->next
, index
++)
821 fprintf (dump_file
, " %i ", index
);
822 if (bb
->rbi
->original
)
823 fprintf (dump_file
, "duplicate of %i ",
824 bb
->rbi
->original
->index
);
825 else if (forwarder_block_p (bb
)
826 && !LABEL_P (BB_HEAD (bb
)))
827 fprintf (dump_file
, "compensation ");
829 fprintf (dump_file
, "bb %i ", bb
->index
);
830 fprintf (dump_file
, " [%i]\n", bb
->frequency
);
834 prev_bb
= ENTRY_BLOCK_PTR
;
835 bb
= ENTRY_BLOCK_PTR
->next_bb
;
838 for (; bb
; prev_bb
= bb
, bb
= bb
->rbi
->next
, index
++)
841 BASIC_BLOCK (index
) = bb
;
843 update_unlikely_executed_notes (bb
);
845 bb
->prev_bb
= prev_bb
;
846 prev_bb
->next_bb
= bb
;
848 prev_bb
->next_bb
= EXIT_BLOCK_PTR
;
849 EXIT_BLOCK_PTR
->prev_bb
= prev_bb
;
851 /* Annoying special case - jump around dead jumptables left in the code. */
857 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
858 if (e
->flags
& EDGE_FALLTHRU
)
861 if (e
&& !can_fallthru (e
->src
, e
->dest
))
862 force_nonfallthru (e
);
866 /* Update the basic block number information in any
867 NOTE_INSN_UNLIKELY_EXECUTED_CODE notes within the basic block. */
870 update_unlikely_executed_notes (basic_block bb
)
874 for (cur_insn
= BB_HEAD (bb
); cur_insn
!= BB_END (bb
);
875 cur_insn
= NEXT_INSN (cur_insn
))
876 if (NOTE_P (cur_insn
)
877 && NOTE_LINE_NUMBER (cur_insn
) == NOTE_INSN_UNLIKELY_EXECUTED_CODE
)
878 NOTE_BASIC_BLOCK (cur_insn
) = bb
;
881 /* Perform sanity checks on the insn chain.
882 1. Check that next/prev pointers are consistent in both the forward and
884 2. Count insns in chain, going both directions, and check if equal.
885 3. Check that get_last_insn () returns the actual end of chain. */
888 verify_insn_chain (void)
891 int insn_cnt1
, insn_cnt2
;
893 for (prevx
= NULL
, insn_cnt1
= 1, x
= get_insns ();
895 prevx
= x
, insn_cnt1
++, x
= NEXT_INSN (x
))
896 gcc_assert (PREV_INSN (x
) == prevx
);
898 gcc_assert (prevx
== get_last_insn ());
900 for (nextx
= NULL
, insn_cnt2
= 1, x
= get_last_insn ();
902 nextx
= x
, insn_cnt2
++, x
= PREV_INSN (x
))
903 gcc_assert (NEXT_INSN (x
) == nextx
);
905 gcc_assert (insn_cnt1
== insn_cnt2
);
908 /* If we have assembler epilogues, the block falling through to exit must
909 be the last one in the reordered chain when we reach final. Ensure
910 that this condition is met. */
912 fixup_fallthru_exit_predecessor (void)
916 basic_block bb
= NULL
;
918 /* This transformation is not valid before reload, because we might
919 separate a call from the instruction that copies the return
921 gcc_assert (reload_completed
);
923 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
924 if (e
->flags
& EDGE_FALLTHRU
)
927 if (bb
&& bb
->rbi
->next
)
929 basic_block c
= ENTRY_BLOCK_PTR
->next_bb
;
931 /* If the very first block is the one with the fall-through exit
932 edge, we have to split that block. */
935 bb
= split_block (bb
, NULL
)->dest
;
936 initialize_bb_rbi (bb
);
937 bb
->rbi
->next
= c
->rbi
->next
;
939 bb
->rbi
->footer
= c
->rbi
->footer
;
940 c
->rbi
->footer
= NULL
;
943 while (c
->rbi
->next
!= bb
)
946 c
->rbi
->next
= bb
->rbi
->next
;
951 bb
->rbi
->next
= NULL
;
955 /* Return true in case it is possible to duplicate the basic block BB. */
957 /* We do not want to declare the function in a header file, since it should
958 only be used through the cfghooks interface, and we do not want to move
959 it to cfgrtl.c since it would require also moving quite a lot of related
961 extern bool cfg_layout_can_duplicate_bb_p (basic_block
);
964 cfg_layout_can_duplicate_bb_p (basic_block bb
)
966 /* Do not attempt to duplicate tablejumps, as we need to unshare
967 the dispatch table. This is difficult to do, as the instructions
968 computing jump destination may be hoisted outside the basic block. */
969 if (tablejump_p (BB_END (bb
), NULL
, NULL
))
972 /* Do not duplicate blocks containing insns that can't be copied. */
973 if (targetm
.cannot_copy_insn_p
)
975 rtx insn
= BB_HEAD (bb
);
978 if (INSN_P (insn
) && targetm
.cannot_copy_insn_p (insn
))
980 if (insn
== BB_END (bb
))
982 insn
= NEXT_INSN (insn
);
990 duplicate_insn_chain (rtx from
, rtx to
)
994 /* Avoid updating of boundaries of previous basic block. The
995 note will get removed from insn stream in fixup. */
996 last
= emit_note (NOTE_INSN_DELETED
);
998 /* Create copy at the end of INSN chain. The chain will
999 be reordered later. */
1000 for (insn
= from
; insn
!= NEXT_INSN (to
); insn
= NEXT_INSN (insn
))
1002 switch (GET_CODE (insn
))
1007 /* Avoid copying of dispatch tables. We never duplicate
1008 tablejumps, so this can hit only in case the table got
1009 moved far from original jump. */
1010 if (GET_CODE (PATTERN (insn
)) == ADDR_VEC
1011 || GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
)
1013 emit_copy_of_insn_after (insn
, get_last_insn ());
1024 switch (NOTE_LINE_NUMBER (insn
))
1026 /* In case prologue is empty and function contain label
1027 in first BB, we may want to copy the block. */
1028 case NOTE_INSN_PROLOGUE_END
:
1030 case NOTE_INSN_LOOP_BEG
:
1031 case NOTE_INSN_LOOP_END
:
1032 /* Strip down the loop notes - we don't really want to keep
1033 them consistent in loop copies. */
1034 case NOTE_INSN_DELETED
:
1035 case NOTE_INSN_DELETED_LABEL
:
1036 /* No problem to strip these. */
1037 case NOTE_INSN_EPILOGUE_BEG
:
1038 case NOTE_INSN_FUNCTION_END
:
1039 /* Debug code expect these notes to exist just once.
1040 Keep them in the master copy.
1041 ??? It probably makes more sense to duplicate them for each
1043 case NOTE_INSN_FUNCTION_BEG
:
1044 /* There is always just single entry to function. */
1045 case NOTE_INSN_BASIC_BLOCK
:
1048 case NOTE_INSN_REPEATED_LINE_NUMBER
:
1049 case NOTE_INSN_UNLIKELY_EXECUTED_CODE
:
1050 emit_note_copy (insn
);
1054 /* All other notes should have already been eliminated.
1056 gcc_assert (NOTE_LINE_NUMBER (insn
) >= 0);
1058 /* It is possible that no_line_number is set and the note
1059 won't be emitted. */
1060 emit_note_copy (insn
);
1067 insn
= NEXT_INSN (last
);
1071 /* Create a duplicate of the basic block BB. */
1073 /* We do not want to declare the function in a header file, since it should
1074 only be used through the cfghooks interface, and we do not want to move
1075 it to cfgrtl.c since it would require also moving quite a lot of related
1077 extern basic_block
cfg_layout_duplicate_bb (basic_block
);
1080 cfg_layout_duplicate_bb (basic_block bb
)
1085 insn
= duplicate_insn_chain (BB_HEAD (bb
), BB_END (bb
));
1086 new_bb
= create_basic_block (insn
,
1087 insn
? get_last_insn () : NULL
,
1088 EXIT_BLOCK_PTR
->prev_bb
);
1090 BB_COPY_PARTITION (new_bb
, bb
);
1091 if (bb
->rbi
->header
)
1093 insn
= bb
->rbi
->header
;
1094 while (NEXT_INSN (insn
))
1095 insn
= NEXT_INSN (insn
);
1096 insn
= duplicate_insn_chain (bb
->rbi
->header
, insn
);
1098 new_bb
->rbi
->header
= unlink_insn_chain (insn
, get_last_insn ());
1101 if (bb
->rbi
->footer
)
1103 insn
= bb
->rbi
->footer
;
1104 while (NEXT_INSN (insn
))
1105 insn
= NEXT_INSN (insn
);
1106 insn
= duplicate_insn_chain (bb
->rbi
->footer
, insn
);
1108 new_bb
->rbi
->footer
= unlink_insn_chain (insn
, get_last_insn ());
1111 if (bb
->global_live_at_start
)
1113 new_bb
->global_live_at_start
= ALLOC_REG_SET (®_obstack
);
1114 new_bb
->global_live_at_end
= ALLOC_REG_SET (®_obstack
);
1115 COPY_REG_SET (new_bb
->global_live_at_start
, bb
->global_live_at_start
);
1116 COPY_REG_SET (new_bb
->global_live_at_end
, bb
->global_live_at_end
);
1122 /* Main entry point to this module - initialize the datastructures for
1123 CFG layout changes. It keeps LOOPS up-to-date if not null.
1125 FLAGS is a set of additional flags to pass to cleanup_cfg(). It should
1126 include CLEANUP_UPDATE_LIFE if liveness information must be kept up
1130 cfg_layout_initialize (unsigned int flags
)
1134 /* Our algorithm depends on fact that there are no dead jumptables
1138 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1139 initialize_bb_rbi (bb
);
1141 cfg_layout_rtl_register_cfg_hooks ();
1143 record_effective_endpoints ();
1145 cleanup_cfg (CLEANUP_CFGLAYOUT
| flags
);
1148 /* Splits superblocks. */
1150 break_superblocks (void)
1152 sbitmap superblocks
;
1156 superblocks
= sbitmap_alloc (last_basic_block
);
1157 sbitmap_zero (superblocks
);
1160 if (bb
->flags
& BB_SUPERBLOCK
)
1162 bb
->flags
&= ~BB_SUPERBLOCK
;
1163 SET_BIT (superblocks
, bb
->index
);
1169 rebuild_jump_labels (get_insns ());
1170 find_many_sub_basic_blocks (superblocks
);
1176 /* Finalize the changes: reorder insn list according to the sequence, enter
1177 compensation code, rebuild scope forest. */
1180 cfg_layout_finalize (void)
1184 #ifdef ENABLE_CHECKING
1185 verify_flow_info ();
1187 rtl_register_cfg_hooks ();
1188 if (reload_completed
1189 #ifdef HAVE_epilogue
1193 fixup_fallthru_exit_predecessor ();
1194 fixup_reorder_chain ();
1196 #ifdef ENABLE_CHECKING
1197 verify_insn_chain ();
1201 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1204 break_superblocks ();
1206 #ifdef ENABLE_CHECKING
1207 verify_flow_info ();
1211 /* Checks whether all N blocks in BBS array can be copied. */
1213 can_copy_bbs_p (basic_block
*bbs
, unsigned n
)
1219 for (i
= 0; i
< n
; i
++)
1220 bbs
[i
]->rbi
->duplicated
= 1;
1222 for (i
= 0; i
< n
; i
++)
1224 /* In case we should redirect abnormal edge during duplication, fail. */
1226 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
1227 if ((e
->flags
& EDGE_ABNORMAL
)
1228 && e
->dest
->rbi
->duplicated
)
1234 if (!can_duplicate_block_p (bbs
[i
]))
1242 for (i
= 0; i
< n
; i
++)
1243 bbs
[i
]->rbi
->duplicated
= 0;
1248 /* Duplicates N basic blocks stored in array BBS. Newly created basic blocks
1249 are placed into array NEW_BBS in the same order. Edges from basic blocks
1250 in BBS are also duplicated and copies of those of them
1251 that lead into BBS are redirected to appropriate newly created block. The
1252 function assigns bbs into loops (copy of basic block bb is assigned to
1253 bb->loop_father->copy loop, so this must be set up correctly in advance)
1254 and updates dominators locally (LOOPS structure that contains the information
1255 about dominators is passed to enable this).
1257 BASE is the superloop to that basic block belongs; if its header or latch
1258 is copied, we do not set the new blocks as header or latch.
1260 Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
1261 also in the same order. */
1264 copy_bbs (basic_block
*bbs
, unsigned n
, basic_block
*new_bbs
,
1265 edge
*edges
, unsigned n_edges
, edge
*new_edges
,
1269 basic_block bb
, new_bb
, dom_bb
;
1272 /* Duplicate bbs, update dominators, assign bbs to loops. */
1273 for (i
= 0; i
< n
; i
++)
1277 new_bb
= new_bbs
[i
] = duplicate_block (bb
, NULL
);
1278 bb
->rbi
->duplicated
= 1;
1280 add_bb_to_loop (new_bb
, bb
->loop_father
->copy
);
1281 /* Possibly set header. */
1282 if (bb
->loop_father
->header
== bb
&& bb
->loop_father
!= base
)
1283 new_bb
->loop_father
->header
= new_bb
;
1285 if (bb
->loop_father
->latch
== bb
&& bb
->loop_father
!= base
)
1286 new_bb
->loop_father
->latch
= new_bb
;
1289 /* Set dominators. */
1290 for (i
= 0; i
< n
; i
++)
1293 new_bb
= new_bbs
[i
];
1295 dom_bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1296 if (dom_bb
->rbi
->duplicated
)
1298 dom_bb
= dom_bb
->rbi
->copy
;
1299 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, dom_bb
);
1303 /* Redirect edges. */
1304 for (j
= 0; j
< n_edges
; j
++)
1305 new_edges
[j
] = NULL
;
1306 for (i
= 0; i
< n
; i
++)
1309 new_bb
= new_bbs
[i
];
1312 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
1314 for (j
= 0; j
< n_edges
; j
++)
1315 if (edges
[j
] && edges
[j
]->src
== bb
&& edges
[j
]->dest
== e
->dest
)
1318 if (!e
->dest
->rbi
->duplicated
)
1320 redirect_edge_and_branch_force (e
, e
->dest
->rbi
->copy
);
1324 /* Clear information about duplicates. */
1325 for (i
= 0; i
< n
; i
++)
1326 bbs
[i
]->rbi
->duplicated
= 0;
1329 #include "gt-cfglayout.h"