1 /* Basic block reordering routines for the GNU compiler.
2 Copyright (C) 2000, 2001, 2003, 2004 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"
28 #include "basic-block.h"
29 #include "insn-config.h"
33 #include "cfglayout.h"
37 #include "alloc-pool.h"
40 /* The contents of the current function definition are allocated
41 in this obstack, and all are freed at the end of the function. */
42 extern struct obstack flow_obstack
;
44 /* Holds the interesting trailing notes for the function. */
45 rtx cfg_layout_function_footer
, cfg_layout_function_header
;
47 static rtx
skip_insns_after_block (basic_block
);
48 static void record_effective_endpoints (void);
49 static rtx
label_for_bb (basic_block
);
50 static void fixup_reorder_chain (void);
52 static void set_block_levels (tree
, int);
53 static void change_scope (rtx
, tree
, tree
);
55 void verify_insn_chain (void);
56 static void fixup_fallthru_exit_predecessor (void);
57 static tree
insn_scope (rtx
);
58 static void update_unlikely_executed_notes (basic_block
);
61 unlink_insn_chain (rtx first
, rtx last
)
63 rtx prevfirst
= PREV_INSN (first
);
64 rtx nextlast
= NEXT_INSN (last
);
66 PREV_INSN (first
) = NULL
;
67 NEXT_INSN (last
) = NULL
;
69 NEXT_INSN (prevfirst
) = nextlast
;
71 PREV_INSN (nextlast
) = prevfirst
;
73 set_last_insn (prevfirst
);
75 set_first_insn (nextlast
);
79 /* Skip over inter-block insns occurring after BB which are typically
80 associated with BB (e.g., barriers). If there are any such insns,
81 we return the last one. Otherwise, we return the end of BB. */
84 skip_insns_after_block (basic_block bb
)
86 rtx insn
, last_insn
, next_head
, prev
;
89 if (bb
->next_bb
!= EXIT_BLOCK_PTR
)
90 next_head
= BB_HEAD (bb
->next_bb
);
92 for (last_insn
= insn
= BB_END (bb
); (insn
= NEXT_INSN (insn
)) != 0; )
94 if (insn
== next_head
)
97 switch (GET_CODE (insn
))
104 switch (NOTE_LINE_NUMBER (insn
))
106 case NOTE_INSN_LOOP_END
:
107 case NOTE_INSN_BLOCK_END
:
110 case NOTE_INSN_DELETED
:
111 case NOTE_INSN_DELETED_LABEL
:
122 && JUMP_P (NEXT_INSN (insn
))
123 && (GET_CODE (PATTERN (NEXT_INSN (insn
))) == ADDR_VEC
124 || GET_CODE (PATTERN (NEXT_INSN (insn
))) == ADDR_DIFF_VEC
))
126 insn
= NEXT_INSN (insn
);
139 /* It is possible to hit contradictory sequence. For instance:
145 Where barrier belongs to jump_insn, but the note does not. This can be
146 created by removing the basic block originally following
147 NOTE_INSN_LOOP_BEG. In such case reorder the notes. */
149 for (insn
= last_insn
; insn
!= BB_END (bb
); insn
= prev
)
151 prev
= PREV_INSN (insn
);
153 switch (NOTE_LINE_NUMBER (insn
))
155 case NOTE_INSN_LOOP_END
:
156 case NOTE_INSN_BLOCK_END
:
157 case NOTE_INSN_DELETED
:
158 case NOTE_INSN_DELETED_LABEL
:
161 reorder_insns (insn
, insn
, last_insn
);
168 /* Locate or create a label for a given basic block. */
171 label_for_bb (basic_block bb
)
173 rtx label
= BB_HEAD (bb
);
175 if (!LABEL_P (label
))
178 fprintf (dump_file
, "Emitting label for block %d\n", bb
->index
);
180 label
= block_label (bb
);
186 /* Locate the effective beginning and end of the insn chain for each
187 block, as defined by skip_insns_after_block above. */
190 record_effective_endpoints (void)
196 for (insn
= get_insns ();
199 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_BASIC_BLOCK
;
200 insn
= NEXT_INSN (insn
))
203 abort (); /* No basic blocks at all? */
204 if (PREV_INSN (insn
))
205 cfg_layout_function_header
=
206 unlink_insn_chain (get_insns (), PREV_INSN (insn
));
208 cfg_layout_function_header
= NULL_RTX
;
210 next_insn
= get_insns ();
215 if (PREV_INSN (BB_HEAD (bb
)) && next_insn
!= BB_HEAD (bb
))
216 bb
->rbi
->header
= unlink_insn_chain (next_insn
,
217 PREV_INSN (BB_HEAD (bb
)));
218 end
= skip_insns_after_block (bb
);
219 if (NEXT_INSN (BB_END (bb
)) && BB_END (bb
) != end
)
220 bb
->rbi
->footer
= unlink_insn_chain (NEXT_INSN (BB_END (bb
)), end
);
221 next_insn
= NEXT_INSN (BB_END (bb
));
224 cfg_layout_function_footer
= next_insn
;
225 if (cfg_layout_function_footer
)
226 cfg_layout_function_footer
= unlink_insn_chain (cfg_layout_function_footer
, get_last_insn ());
229 /* Data structures representing mapping of INSN_LOCATOR into scope blocks, line
230 numbers and files. In order to be GGC friendly we need to use separate
231 varrays. This also slightly improve the memory locality in binary search.
232 The _locs array contains locators where the given property change. The
233 block_locators_blocks contains the scope block that is used for all insn
234 locator greater than corresponding block_locators_locs value and smaller
235 than the following one. Similarly for the other properties. */
236 static GTY(()) varray_type block_locators_locs
;
237 static GTY(()) varray_type block_locators_blocks
;
238 static GTY(()) varray_type line_locators_locs
;
239 static GTY(()) varray_type line_locators_lines
;
240 static GTY(()) varray_type file_locators_locs
;
241 static GTY(()) varray_type file_locators_files
;
242 int prologue_locator
;
243 int epilogue_locator
;
245 /* During the RTL expansion the lexical blocks and line numbers are
246 represented via INSN_NOTEs. Replace them by representation using
250 insn_locators_initialize (void)
253 tree last_block
= NULL
;
256 int line_number
= 0, last_line_number
= 0;
257 const char *file_name
= NULL
, *last_file_name
= NULL
;
259 prologue_locator
= epilogue_locator
= 0;
261 VARRAY_INT_INIT (block_locators_locs
, 32, "block_locators_locs");
262 VARRAY_TREE_INIT (block_locators_blocks
, 32, "block_locators_blocks");
263 VARRAY_INT_INIT (line_locators_locs
, 32, "line_locators_locs");
264 VARRAY_INT_INIT (line_locators_lines
, 32, "line_locators_lines");
265 VARRAY_INT_INIT (file_locators_locs
, 32, "file_locators_locs");
266 VARRAY_CHAR_PTR_INIT (file_locators_files
, 32, "file_locators_files");
268 for (insn
= get_insns (); insn
; insn
= next
)
272 next
= NEXT_INSN (insn
);
276 switch (NOTE_LINE_NUMBER (insn
))
278 case NOTE_INSN_BLOCK_BEG
:
279 case NOTE_INSN_BLOCK_END
:
283 if (NOTE_LINE_NUMBER (insn
) > 0)
285 expanded_location xloc
;
286 NOTE_EXPANDED_LOCATION (xloc
, insn
);
287 line_number
= xloc
.line
;
288 file_name
= xloc
.file
;
294 active
= (active_insn_p (insn
)
295 && GET_CODE (PATTERN (insn
)) != ADDR_VEC
296 && GET_CODE (PATTERN (insn
)) != ADDR_DIFF_VEC
);
298 check_block_change (insn
, &block
);
302 || (!prologue_locator
&& file_name
))
304 if (last_block
!= block
)
307 VARRAY_PUSH_INT (block_locators_locs
, loc
);
308 VARRAY_PUSH_TREE (block_locators_blocks
, block
);
311 if (last_line_number
!= line_number
)
314 VARRAY_PUSH_INT (line_locators_locs
, loc
);
315 VARRAY_PUSH_INT (line_locators_lines
, line_number
);
316 last_line_number
= line_number
;
318 if (last_file_name
!= file_name
)
321 VARRAY_PUSH_INT (file_locators_locs
, loc
);
322 VARRAY_PUSH_CHAR_PTR (file_locators_files
, (char *) file_name
);
323 last_file_name
= file_name
;
325 if (!prologue_locator
&& file_name
)
326 prologue_locator
= loc
;
328 epilogue_locator
= loc
;
330 INSN_LOCATOR (insn
) = loc
;
334 /* Tag the blocks with a depth number so that change_scope can find
335 the common parent easily. */
336 set_block_levels (DECL_INITIAL (cfun
->decl
), 0);
338 free_block_changes ();
341 /* For each lexical block, set BLOCK_NUMBER to the depth at which it is
342 found in the block tree. */
345 set_block_levels (tree block
, int level
)
349 BLOCK_NUMBER (block
) = level
;
350 set_block_levels (BLOCK_SUBBLOCKS (block
), level
+ 1);
351 block
= BLOCK_CHAIN (block
);
355 /* Return sope resulting from combination of S1 and S2. */
357 choose_inner_scope (tree s1
, tree s2
)
363 if (BLOCK_NUMBER (s1
) > BLOCK_NUMBER (s2
))
368 /* Emit lexical block notes needed to change scope from S1 to S2. */
371 change_scope (rtx orig_insn
, tree s1
, tree s2
)
373 rtx insn
= orig_insn
;
374 tree com
= NULL_TREE
;
375 tree ts1
= s1
, ts2
= s2
;
380 if (ts1
== NULL
|| ts2
== NULL
)
382 if (BLOCK_NUMBER (ts1
) > BLOCK_NUMBER (ts2
))
383 ts1
= BLOCK_SUPERCONTEXT (ts1
);
384 else if (BLOCK_NUMBER (ts1
) < BLOCK_NUMBER (ts2
))
385 ts2
= BLOCK_SUPERCONTEXT (ts2
);
388 ts1
= BLOCK_SUPERCONTEXT (ts1
);
389 ts2
= BLOCK_SUPERCONTEXT (ts2
);
398 rtx note
= emit_note_before (NOTE_INSN_BLOCK_END
, insn
);
399 NOTE_BLOCK (note
) = s
;
400 s
= BLOCK_SUPERCONTEXT (s
);
407 insn
= emit_note_before (NOTE_INSN_BLOCK_BEG
, insn
);
408 NOTE_BLOCK (insn
) = s
;
409 s
= BLOCK_SUPERCONTEXT (s
);
413 /* Return lexical scope block insn belong to. */
415 insn_scope (rtx insn
)
417 int max
= VARRAY_ACTIVE_SIZE (block_locators_locs
);
419 int loc
= INSN_LOCATOR (insn
);
421 /* When block_locators_locs was initialized, the pro- and epilogue
422 insns didn't exist yet and can therefore not be found this way.
423 But we know that they belong to the outer most block of the
425 Without this test, the prologue would be put inside the block of
426 the first valid instruction in the function and when that first
427 insn is part of an inlined function then the low_pc of that
428 inlined function is messed up. Likewise for the epilogue and
429 the last valid instruction. */
430 if (loc
== prologue_locator
|| loc
== epilogue_locator
)
431 return DECL_INITIAL (cfun
->decl
);
437 int pos
= (min
+ max
) / 2;
438 int tmp
= VARRAY_INT (block_locators_locs
, pos
);
440 if (tmp
<= loc
&& min
!= pos
)
442 else if (tmp
> loc
&& max
!= pos
)
450 return VARRAY_TREE (block_locators_blocks
, min
);
453 /* Return line number of the statement specified by the locator. */
455 locator_line (int loc
)
457 int max
= VARRAY_ACTIVE_SIZE (line_locators_locs
);
464 int pos
= (min
+ max
) / 2;
465 int tmp
= VARRAY_INT (line_locators_locs
, pos
);
467 if (tmp
<= loc
&& min
!= pos
)
469 else if (tmp
> loc
&& max
!= pos
)
477 return VARRAY_INT (line_locators_lines
, min
);
480 /* Return line number of the statement that produced this insn. */
484 return locator_line (INSN_LOCATOR (insn
));
487 /* Return source file of the statement specified by LOC. */
489 locator_file (int loc
)
491 int max
= VARRAY_ACTIVE_SIZE (file_locators_locs
);
498 int pos
= (min
+ max
) / 2;
499 int tmp
= VARRAY_INT (file_locators_locs
, pos
);
501 if (tmp
<= loc
&& min
!= pos
)
503 else if (tmp
> loc
&& max
!= pos
)
511 return VARRAY_CHAR_PTR (file_locators_files
, min
);
514 /* Return source file of the statement that produced this insn. */
518 return locator_file (INSN_LOCATOR (insn
));
521 /* Rebuild all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes based
522 on the scope tree and the newly reordered instructions. */
525 reemit_insn_block_notes (void)
527 tree cur_block
= DECL_INITIAL (cfun
->decl
);
531 if (!active_insn_p (insn
))
532 insn
= next_active_insn (insn
);
533 for (; insn
; insn
= next_active_insn (insn
))
537 this_block
= insn_scope (insn
);
538 /* For sequences compute scope resulting from merging all scopes
539 of instructions nested inside. */
540 if (GET_CODE (PATTERN (insn
)) == SEQUENCE
)
543 rtx body
= PATTERN (insn
);
546 for (i
= 0; i
< XVECLEN (body
, 0); i
++)
547 this_block
= choose_inner_scope (this_block
,
548 insn_scope (XVECEXP (body
, 0, i
)));
553 if (this_block
!= cur_block
)
555 change_scope (insn
, cur_block
, this_block
);
556 cur_block
= this_block
;
560 /* change_scope emits before the insn, not after. */
561 note
= emit_note (NOTE_INSN_DELETED
);
562 change_scope (note
, cur_block
, DECL_INITIAL (cfun
->decl
));
568 /* Given a reorder chain, rearrange the code to match. */
571 fixup_reorder_chain (void)
573 basic_block bb
, prev_bb
;
577 if (cfg_layout_function_header
)
579 set_first_insn (cfg_layout_function_header
);
580 insn
= cfg_layout_function_header
;
581 while (NEXT_INSN (insn
))
582 insn
= NEXT_INSN (insn
);
585 /* First do the bulk reordering -- rechain the blocks without regard to
586 the needed changes to jumps and labels. */
588 for (bb
= ENTRY_BLOCK_PTR
->next_bb
, index
= 0;
590 bb
= bb
->rbi
->next
, index
++)
595 NEXT_INSN (insn
) = bb
->rbi
->header
;
597 set_first_insn (bb
->rbi
->header
);
598 PREV_INSN (bb
->rbi
->header
) = insn
;
599 insn
= bb
->rbi
->header
;
600 while (NEXT_INSN (insn
))
601 insn
= NEXT_INSN (insn
);
604 NEXT_INSN (insn
) = BB_HEAD (bb
);
606 set_first_insn (BB_HEAD (bb
));
607 PREV_INSN (BB_HEAD (bb
)) = insn
;
611 NEXT_INSN (insn
) = bb
->rbi
->footer
;
612 PREV_INSN (bb
->rbi
->footer
) = insn
;
613 while (NEXT_INSN (insn
))
614 insn
= NEXT_INSN (insn
);
618 if (index
!= n_basic_blocks
)
621 NEXT_INSN (insn
) = cfg_layout_function_footer
;
622 if (cfg_layout_function_footer
)
623 PREV_INSN (cfg_layout_function_footer
) = insn
;
625 while (NEXT_INSN (insn
))
626 insn
= NEXT_INSN (insn
);
628 set_last_insn (insn
);
629 #ifdef ENABLE_CHECKING
630 verify_insn_chain ();
632 delete_dead_jumptables ();
634 /* Now add jumps and labels as needed to match the blocks new
637 for (bb
= ENTRY_BLOCK_PTR
->next_bb
; bb
; bb
= bb
->rbi
->next
)
639 edge e_fall
, e_taken
, e
;
644 if (bb
->succ
== NULL
)
647 /* Find the old fallthru edge, and another non-EH edge for
649 e_taken
= e_fall
= NULL
;
650 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
651 if (e
->flags
& EDGE_FALLTHRU
)
653 else if (! (e
->flags
& EDGE_EH
))
656 bb_end_insn
= BB_END (bb
);
657 if (JUMP_P (bb_end_insn
))
659 if (any_condjump_p (bb_end_insn
))
661 /* If the old fallthru is still next, nothing to do. */
662 if (bb
->rbi
->next
== e_fall
->dest
663 || e_fall
->dest
== EXIT_BLOCK_PTR
)
666 /* The degenerated case of conditional jump jumping to the next
667 instruction can happen on target having jumps with side
670 Create temporarily the duplicated edge representing branch.
671 It will get unidentified by force_nonfallthru_and_redirect
672 that would otherwise get confused by fallthru edge not pointing
673 to the next basic block. */
679 e_fake
= unchecked_make_edge (bb
, e_fall
->dest
, 0);
681 if (!redirect_jump (BB_END (bb
), block_label (bb
), 0))
683 note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
);
686 int prob
= INTVAL (XEXP (note
, 0));
688 e_fake
->probability
= prob
;
689 e_fake
->count
= e_fall
->count
* prob
/ REG_BR_PROB_BASE
;
690 e_fall
->probability
-= e_fall
->probability
;
691 e_fall
->count
-= e_fake
->count
;
692 if (e_fall
->probability
< 0)
693 e_fall
->probability
= 0;
694 if (e_fall
->count
< 0)
698 /* There is one special case: if *neither* block is next,
699 such as happens at the very end of a function, then we'll
700 need to add a new unconditional jump. Choose the taken
701 edge based on known or assumed probability. */
702 else if (bb
->rbi
->next
!= e_taken
->dest
)
704 rtx note
= find_reg_note (bb_end_insn
, REG_BR_PROB
, 0);
707 && INTVAL (XEXP (note
, 0)) < REG_BR_PROB_BASE
/ 2
708 && invert_jump (bb_end_insn
,
709 (e_fall
->dest
== EXIT_BLOCK_PTR
711 : label_for_bb (e_fall
->dest
)), 0))
713 e_fall
->flags
&= ~EDGE_FALLTHRU
;
714 #ifdef ENABLE_CHECKING
715 if (!could_fall_through (e_taken
->src
, e_taken
->dest
))
718 e_taken
->flags
|= EDGE_FALLTHRU
;
719 update_br_prob_note (bb
);
720 e
= e_fall
, e_fall
= e_taken
, e_taken
= e
;
724 /* If the "jumping" edge is a crossing edge, and the fall
725 through edge is non-crossing, leave things as they are. */
726 else if ((e_taken
->flags
& EDGE_CROSSING
)
727 && !(e_fall
->flags
& EDGE_CROSSING
))
730 /* Otherwise we can try to invert the jump. This will
731 basically never fail, however, keep up the pretense. */
732 else if (invert_jump (bb_end_insn
,
733 (e_fall
->dest
== EXIT_BLOCK_PTR
735 : label_for_bb (e_fall
->dest
)), 0))
737 e_fall
->flags
&= ~EDGE_FALLTHRU
;
738 #ifdef ENABLE_CHECKING
739 if (!could_fall_through (e_taken
->src
, e_taken
->dest
))
742 e_taken
->flags
|= EDGE_FALLTHRU
;
743 update_br_prob_note (bb
);
747 else if (returnjump_p (bb_end_insn
))
751 /* Otherwise we have some switch or computed jump. In the
752 99% case, there should not have been a fallthru edge. */
756 #ifdef CASE_DROPS_THROUGH
757 /* Except for VAX. Since we didn't have predication for the
758 tablejump, the fallthru block should not have moved. */
759 if (bb
->rbi
->next
== e_fall
->dest
)
761 bb_end_insn
= skip_insns_after_block (bb
);
769 /* No fallthru implies a noreturn function with EH edges, or
770 something similarly bizarre. In any case, we don't need to
775 /* If the fallthru block is still next, nothing to do. */
776 if (bb
->rbi
->next
== e_fall
->dest
)
779 /* A fallthru to exit block. */
780 if (e_fall
->dest
== EXIT_BLOCK_PTR
)
784 /* We got here if we need to add a new jump insn. */
785 nb
= force_nonfallthru (e_fall
);
788 initialize_bb_rbi (nb
);
789 nb
->rbi
->visited
= 1;
790 nb
->rbi
->next
= bb
->rbi
->next
;
792 /* Don't process this new block. */
796 /* Make sure new bb is tagged for correct section (same as
797 fall-thru source, since you cannot fall-throu across
798 section boundaries). */
799 BB_COPY_PARTITION (e_fall
->src
, bb
->pred
->src
);
800 if (flag_reorder_blocks_and_partition
801 && targetm
.have_named_sections
)
803 if (BB_PARTITION (bb
->pred
->src
) == BB_COLD_PARTITION
)
806 rtx note
= BB_HEAD (e_fall
->src
);
808 while (!INSN_P (note
)
809 && note
!= BB_END (e_fall
->src
))
810 note
= NEXT_INSN (note
);
812 new_note
= emit_note_before
813 (NOTE_INSN_UNLIKELY_EXECUTED_CODE
,
815 NOTE_BASIC_BLOCK (new_note
) = bb
;
817 if (JUMP_P (BB_END (bb
))
818 && !any_condjump_p (BB_END (bb
))
819 && (bb
->succ
->flags
& EDGE_CROSSING
))
820 REG_NOTES (BB_END (bb
)) = gen_rtx_EXPR_LIST
821 (REG_CROSSING_JUMP
, NULL_RTX
, REG_NOTES (BB_END (bb
)));
826 /* Put basic_block_info in the new order. */
830 fprintf (dump_file
, "Reordered sequence:\n");
831 for (bb
= ENTRY_BLOCK_PTR
->next_bb
, index
= 0;
833 bb
= bb
->rbi
->next
, index
++)
835 fprintf (dump_file
, " %i ", index
);
836 if (bb
->rbi
->original
)
837 fprintf (dump_file
, "duplicate of %i ",
838 bb
->rbi
->original
->index
);
839 else if (forwarder_block_p (bb
)
840 && !LABEL_P (BB_HEAD (bb
)))
841 fprintf (dump_file
, "compensation ");
843 fprintf (dump_file
, "bb %i ", bb
->index
);
844 fprintf (dump_file
, " [%i]\n", bb
->frequency
);
848 prev_bb
= ENTRY_BLOCK_PTR
;
849 bb
= ENTRY_BLOCK_PTR
->next_bb
;
852 for (; bb
; prev_bb
= bb
, bb
= bb
->rbi
->next
, index
++)
855 BASIC_BLOCK (index
) = bb
;
857 update_unlikely_executed_notes (bb
);
859 bb
->prev_bb
= prev_bb
;
860 prev_bb
->next_bb
= bb
;
862 prev_bb
->next_bb
= EXIT_BLOCK_PTR
;
863 EXIT_BLOCK_PTR
->prev_bb
= prev_bb
;
865 /* Annoying special case - jump around dead jumptables left in the code. */
869 for (e
= bb
->succ
; e
&& !(e
->flags
& EDGE_FALLTHRU
); e
= e
->succ_next
)
871 if (e
&& !can_fallthru (e
->src
, e
->dest
))
872 force_nonfallthru (e
);
876 /* Update the basic block number information in any
877 NOTE_INSN_UNLIKELY_EXECUTED_CODE notes within the basic block. */
880 update_unlikely_executed_notes (basic_block bb
)
884 for (cur_insn
= BB_HEAD (bb
); cur_insn
!= BB_END (bb
);
885 cur_insn
= NEXT_INSN (cur_insn
))
886 if (NOTE_P (cur_insn
)
887 && NOTE_LINE_NUMBER (cur_insn
) == NOTE_INSN_UNLIKELY_EXECUTED_CODE
)
888 NOTE_BASIC_BLOCK (cur_insn
) = bb
;
891 /* Perform sanity checks on the insn chain.
892 1. Check that next/prev pointers are consistent in both the forward and
894 2. Count insns in chain, going both directions, and check if equal.
895 3. Check that get_last_insn () returns the actual end of chain. */
898 verify_insn_chain (void)
901 int insn_cnt1
, insn_cnt2
;
903 for (prevx
= NULL
, insn_cnt1
= 1, x
= get_insns ();
905 prevx
= x
, insn_cnt1
++, x
= NEXT_INSN (x
))
906 if (PREV_INSN (x
) != prevx
)
909 if (prevx
!= get_last_insn ())
912 for (nextx
= NULL
, insn_cnt2
= 1, x
= get_last_insn ();
914 nextx
= x
, insn_cnt2
++, x
= PREV_INSN (x
))
915 if (NEXT_INSN (x
) != nextx
)
918 if (insn_cnt1
!= insn_cnt2
)
922 /* If we have assembler epilogues, the block falling through to exit must
923 be the last one in the reordered chain when we reach final. Ensure
924 that this condition is met. */
926 fixup_fallthru_exit_predecessor (void)
929 basic_block bb
= NULL
;
931 /* This transformation is not valid before reload, because we might separate
932 a call from the instruction that copies the return value. */
933 if (! reload_completed
)
936 for (e
= EXIT_BLOCK_PTR
->pred
; e
; e
= e
->pred_next
)
937 if (e
->flags
& EDGE_FALLTHRU
)
940 if (bb
&& bb
->rbi
->next
)
942 basic_block c
= ENTRY_BLOCK_PTR
->next_bb
;
944 /* If the very first block is the one with the fall-through exit
945 edge, we have to split that block. */
948 bb
= split_block (bb
, NULL
)->dest
;
949 initialize_bb_rbi (bb
);
950 bb
->rbi
->next
= c
->rbi
->next
;
952 bb
->rbi
->footer
= c
->rbi
->footer
;
953 c
->rbi
->footer
= NULL
;
956 while (c
->rbi
->next
!= bb
)
959 c
->rbi
->next
= bb
->rbi
->next
;
964 bb
->rbi
->next
= NULL
;
968 /* Return true in case it is possible to duplicate the basic block BB. */
970 /* We do not want to declare the function in a header file, since it should
971 only be used through the cfghooks interface, and we do not want to move
972 it to cfgrtl.c since it would require also moving quite a lot of related
974 extern bool cfg_layout_can_duplicate_bb_p (basic_block
);
977 cfg_layout_can_duplicate_bb_p (basic_block bb
)
979 /* Do not attempt to duplicate tablejumps, as we need to unshare
980 the dispatch table. This is difficult to do, as the instructions
981 computing jump destination may be hoisted outside the basic block. */
982 if (tablejump_p (BB_END (bb
), NULL
, NULL
))
985 /* Do not duplicate blocks containing insns that can't be copied. */
986 if (targetm
.cannot_copy_insn_p
)
988 rtx insn
= BB_HEAD (bb
);
991 if (INSN_P (insn
) && targetm
.cannot_copy_insn_p (insn
))
993 if (insn
== BB_END (bb
))
995 insn
= NEXT_INSN (insn
);
1003 duplicate_insn_chain (rtx from
, rtx to
)
1007 /* Avoid updating of boundaries of previous basic block. The
1008 note will get removed from insn stream in fixup. */
1009 last
= emit_note (NOTE_INSN_DELETED
);
1011 /* Create copy at the end of INSN chain. The chain will
1012 be reordered later. */
1013 for (insn
= from
; insn
!= NEXT_INSN (to
); insn
= NEXT_INSN (insn
))
1015 switch (GET_CODE (insn
))
1020 /* Avoid copying of dispatch tables. We never duplicate
1021 tablejumps, so this can hit only in case the table got
1022 moved far from original jump. */
1023 if (GET_CODE (PATTERN (insn
)) == ADDR_VEC
1024 || GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
)
1026 emit_copy_of_insn_after (insn
, get_last_insn ());
1037 switch (NOTE_LINE_NUMBER (insn
))
1039 /* In case prologue is empty and function contain label
1040 in first BB, we may want to copy the block. */
1041 case NOTE_INSN_PROLOGUE_END
:
1043 case NOTE_INSN_LOOP_BEG
:
1044 case NOTE_INSN_LOOP_END
:
1045 /* Strip down the loop notes - we don't really want to keep
1046 them consistent in loop copies. */
1047 case NOTE_INSN_DELETED
:
1048 case NOTE_INSN_DELETED_LABEL
:
1049 /* No problem to strip these. */
1050 case NOTE_INSN_EPILOGUE_BEG
:
1051 case NOTE_INSN_FUNCTION_END
:
1052 /* Debug code expect these notes to exist just once.
1053 Keep them in the master copy.
1054 ??? It probably makes more sense to duplicate them for each
1056 case NOTE_INSN_FUNCTION_BEG
:
1057 /* There is always just single entry to function. */
1058 case NOTE_INSN_BASIC_BLOCK
:
1061 /* There is no purpose to duplicate prologue. */
1062 case NOTE_INSN_BLOCK_BEG
:
1063 case NOTE_INSN_BLOCK_END
:
1064 /* The BLOCK_BEG/BLOCK_END notes should be eliminated when BB
1065 reordering is in the progress. */
1066 case NOTE_INSN_EH_REGION_BEG
:
1067 case NOTE_INSN_EH_REGION_END
:
1068 /* Should never exist at BB duplication time. */
1071 case NOTE_INSN_REPEATED_LINE_NUMBER
:
1072 case NOTE_INSN_UNLIKELY_EXECUTED_CODE
:
1073 emit_note_copy (insn
);
1077 if (NOTE_LINE_NUMBER (insn
) < 0)
1079 /* It is possible that no_line_number is set and the note
1080 won't be emitted. */
1081 emit_note_copy (insn
);
1088 insn
= NEXT_INSN (last
);
1092 /* Create a duplicate of the basic block BB. */
1094 /* We do not want to declare the function in a header file, since it should
1095 only be used through the cfghooks interface, and we do not want to move
1096 it to cfgrtl.c since it would require also moving quite a lot of related
1098 extern basic_block
cfg_layout_duplicate_bb (basic_block
);
1101 cfg_layout_duplicate_bb (basic_block bb
)
1106 insn
= duplicate_insn_chain (BB_HEAD (bb
), BB_END (bb
));
1107 new_bb
= create_basic_block (insn
,
1108 insn
? get_last_insn () : NULL
,
1109 EXIT_BLOCK_PTR
->prev_bb
);
1111 BB_COPY_PARTITION (new_bb
, bb
);
1112 if (bb
->rbi
->header
)
1114 insn
= bb
->rbi
->header
;
1115 while (NEXT_INSN (insn
))
1116 insn
= NEXT_INSN (insn
);
1117 insn
= duplicate_insn_chain (bb
->rbi
->header
, insn
);
1119 new_bb
->rbi
->header
= unlink_insn_chain (insn
, get_last_insn ());
1122 if (bb
->rbi
->footer
)
1124 insn
= bb
->rbi
->footer
;
1125 while (NEXT_INSN (insn
))
1126 insn
= NEXT_INSN (insn
);
1127 insn
= duplicate_insn_chain (bb
->rbi
->footer
, insn
);
1129 new_bb
->rbi
->footer
= unlink_insn_chain (insn
, get_last_insn ());
1132 if (bb
->global_live_at_start
)
1134 new_bb
->global_live_at_start
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
1135 new_bb
->global_live_at_end
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
1136 COPY_REG_SET (new_bb
->global_live_at_start
, bb
->global_live_at_start
);
1137 COPY_REG_SET (new_bb
->global_live_at_end
, bb
->global_live_at_end
);
1143 /* Main entry point to this module - initialize the datastructures for
1144 CFG layout changes. It keeps LOOPS up-to-date if not null.
1146 FLAGS is a set of additional flags to pass to cleanup_cfg(). It should
1147 include CLEANUP_UPDATE_LIFE if liveness information must be kept up
1151 cfg_layout_initialize (unsigned int flags
)
1155 /* Our algorithm depends on fact that there are no dead jumptables
1159 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1160 initialize_bb_rbi (bb
);
1162 cfg_layout_rtl_register_cfg_hooks ();
1164 record_effective_endpoints ();
1166 cleanup_cfg (CLEANUP_CFGLAYOUT
| flags
);
1169 /* Splits superblocks. */
1171 break_superblocks (void)
1173 sbitmap superblocks
;
1177 superblocks
= sbitmap_alloc (last_basic_block
);
1178 sbitmap_zero (superblocks
);
1181 if (bb
->flags
& BB_SUPERBLOCK
)
1183 bb
->flags
&= ~BB_SUPERBLOCK
;
1184 SET_BIT (superblocks
, bb
->index
);
1190 rebuild_jump_labels (get_insns ());
1191 find_many_sub_basic_blocks (superblocks
);
1197 /* Finalize the changes: reorder insn list according to the sequence, enter
1198 compensation code, rebuild scope forest. */
1201 cfg_layout_finalize (void)
1205 #ifdef ENABLE_CHECKING
1206 verify_flow_info ();
1208 rtl_register_cfg_hooks ();
1209 if (reload_completed
1210 #ifdef HAVE_epilogue
1214 fixup_fallthru_exit_predecessor ();
1215 fixup_reorder_chain ();
1217 #ifdef ENABLE_CHECKING
1218 verify_insn_chain ();
1222 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1225 break_superblocks ();
1227 #ifdef ENABLE_CHECKING
1228 verify_flow_info ();
1232 /* Checks whether all N blocks in BBS array can be copied. */
1234 can_copy_bbs_p (basic_block
*bbs
, unsigned n
)
1240 for (i
= 0; i
< n
; i
++)
1241 bbs
[i
]->rbi
->duplicated
= 1;
1243 for (i
= 0; i
< n
; i
++)
1245 /* In case we should redirect abnormal edge during duplication, fail. */
1246 for (e
= bbs
[i
]->succ
; e
; e
= e
->succ_next
)
1247 if ((e
->flags
& EDGE_ABNORMAL
)
1248 && e
->dest
->rbi
->duplicated
)
1254 if (!can_duplicate_block_p (bbs
[i
]))
1262 for (i
= 0; i
< n
; i
++)
1263 bbs
[i
]->rbi
->duplicated
= 0;
1268 /* Duplicates N basic blocks stored in array BBS. Newly created basic blocks
1269 are placed into array NEW_BBS in the same order. Edges from basic blocks
1270 in BBS are also duplicated and copies of those of them
1271 that lead into BBS are redirected to appropriate newly created block. The
1272 function assigns bbs into loops (copy of basic block bb is assigned to
1273 bb->loop_father->copy loop, so this must be set up correctly in advance)
1274 and updates dominators locally (LOOPS structure that contains the information
1275 about dominators is passed to enable this).
1277 BASE is the superloop to that basic block belongs; if its header or latch
1278 is copied, we do not set the new blocks as header or latch.
1280 Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
1281 also in the same order. */
1284 copy_bbs (basic_block
*bbs
, unsigned n
, basic_block
*new_bbs
,
1285 edge
*edges
, unsigned n_edges
, edge
*new_edges
,
1289 basic_block bb
, new_bb
, dom_bb
;
1292 /* Duplicate bbs, update dominators, assign bbs to loops. */
1293 for (i
= 0; i
< n
; i
++)
1297 new_bb
= new_bbs
[i
] = duplicate_block (bb
, NULL
);
1298 bb
->rbi
->duplicated
= 1;
1300 add_bb_to_loop (new_bb
, bb
->loop_father
->copy
);
1301 /* Possibly set header. */
1302 if (bb
->loop_father
->header
== bb
&& bb
->loop_father
!= base
)
1303 new_bb
->loop_father
->header
= new_bb
;
1305 if (bb
->loop_father
->latch
== bb
&& bb
->loop_father
!= base
)
1306 new_bb
->loop_father
->latch
= new_bb
;
1309 /* Set dominators. */
1310 for (i
= 0; i
< n
; i
++)
1313 new_bb
= new_bbs
[i
];
1315 dom_bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1316 if (dom_bb
->rbi
->duplicated
)
1318 dom_bb
= dom_bb
->rbi
->copy
;
1319 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, dom_bb
);
1323 /* Redirect edges. */
1324 for (j
= 0; j
< n_edges
; j
++)
1325 new_edges
[j
] = NULL
;
1326 for (i
= 0; i
< n
; i
++)
1328 new_bb
= new_bbs
[i
];
1331 for (e
= new_bb
->succ
; e
; e
= e
->succ_next
)
1333 for (j
= 0; j
< n_edges
; j
++)
1334 if (edges
[j
] && edges
[j
]->src
== bb
&& edges
[j
]->dest
== e
->dest
)
1337 if (!e
->dest
->rbi
->duplicated
)
1339 redirect_edge_and_branch_force (e
, e
->dest
->rbi
->copy
);
1343 /* Clear information about duplicates. */
1344 for (i
= 0; i
< n
; i
++)
1345 bbs
[i
]->rbi
->duplicated
= 0;
1348 #include "gt-cfglayout.h"