1 /* Basic block reordering routines for the GNU compiler.
2 Copyright (C) 2000, 2001 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
24 #include "hard-reg-set.h"
25 #include "basic-block.h"
26 #include "insn-config.h"
30 #include "cfglayout.h"
32 /* The contents of the current function definition are allocated
33 in this obstack, and all are freed at the end of the function. */
35 extern struct obstack flow_obstack
;
37 /* Structure to hold information about lexical scopes. */
42 /* The NOTE_INSN_BLOCK_BEG that started this scope. */
45 /* The NOTE_INSN_BLOCK_END that ended this scope. */
48 /* The bb containing note_beg (if any). */
51 /* The bb containing note_end (if any). */
54 /* List of basic blocks contained within this scope. */
57 /* Number of blocks contained within this scope. */
60 /* The outer scope or NULL if outermost scope. */
61 struct scope_def
*outer
;
63 /* The first inner scope or NULL if innermost scope. */
64 struct scope_def
*inner
;
66 /* The last inner scope or NULL if innermost scope. */
67 struct scope_def
*inner_last
;
69 /* Link to the next (sibling) scope. */
70 struct scope_def
*next
;
73 /* Structure to hold information about the scope forest. */
76 /* Number of trees in forest. */
79 /* List of tree roots. */
83 /* Holds the interesting trailing notes for the function. */
84 static rtx function_tail_eff_head
;
86 /* The scope forest of current function. */
87 static scope_forest_info forest
;
89 static rtx skip_insns_after_block
PARAMS ((basic_block
));
90 static void record_effective_endpoints
PARAMS ((void));
91 static rtx label_for_bb
PARAMS ((basic_block
));
92 static void fixup_reorder_chain
PARAMS ((void));
94 static void relate_bbs_with_scopes
PARAMS ((scope
));
95 static scope make_new_scope
PARAMS ((int, rtx
));
96 static void build_scope_forest
PARAMS ((scope_forest_info
*));
97 static void remove_scope_notes
PARAMS ((void));
98 static void insert_intra_1
PARAMS ((scope
, rtx
*, basic_block
));
99 static void insert_intra_bb_scope_notes
PARAMS ((basic_block
));
100 static void insert_inter_bb_scope_notes
PARAMS ((basic_block
, basic_block
));
101 static void rebuild_scope_notes
PARAMS ((scope_forest_info
*));
102 static void free_scope_forest_1
PARAMS ((scope
));
103 static void free_scope_forest
PARAMS ((scope_forest_info
*));
104 void dump_scope_forest
PARAMS ((scope_forest_info
*));
105 static void dump_scope_forest_1
PARAMS ((scope
, int));
107 static rtx get_next_bb_note
PARAMS ((rtx
));
108 static rtx get_prev_bb_note
PARAMS ((rtx
));
110 void verify_insn_chain
PARAMS ((void));
111 static void fixup_fallthru_exit_predecessor
PARAMS ((void));
113 /* Skip over inter-block insns occurring after BB which are typically
114 associated with BB (e.g., barriers). If there are any such insns,
115 we return the last one. Otherwise, we return the end of BB. */
118 skip_insns_after_block (bb
)
121 rtx insn
, last_insn
, next_head
, prev
;
123 next_head
= NULL_RTX
;
124 if (bb
->index
+ 1 != n_basic_blocks
)
125 next_head
= BASIC_BLOCK (bb
->index
+ 1)->head
;
127 for (last_insn
= insn
= bb
->end
; (insn
= NEXT_INSN (insn
)) != 0; )
129 if (insn
== next_head
)
132 switch (GET_CODE (insn
))
139 switch (NOTE_LINE_NUMBER (insn
))
141 case NOTE_INSN_LOOP_END
:
142 case NOTE_INSN_BLOCK_END
:
145 case NOTE_INSN_DELETED
:
146 case NOTE_INSN_DELETED_LABEL
:
157 && GET_CODE (NEXT_INSN (insn
)) == JUMP_INSN
158 && (GET_CODE (PATTERN (NEXT_INSN (insn
))) == ADDR_VEC
159 || GET_CODE (PATTERN (NEXT_INSN (insn
))) == ADDR_DIFF_VEC
))
161 insn
= NEXT_INSN (insn
);
174 /* It is possible to hit contradictory sequence. For instance:
180 Where barrier belongs to jump_insn, but the note does not. This can be
181 created by removing the basic block originally following
182 NOTE_INSN_LOOP_BEG. In such case reorder the notes. */
184 for (insn
= last_insn
; insn
!= bb
->end
; insn
= prev
)
186 prev
= PREV_INSN (insn
);
187 if (GET_CODE (insn
) == NOTE
)
188 switch (NOTE_LINE_NUMBER (insn
))
190 case NOTE_INSN_LOOP_END
:
191 case NOTE_INSN_BLOCK_END
:
192 case NOTE_INSN_DELETED
:
193 case NOTE_INSN_DELETED_LABEL
:
196 reorder_insns (insn
, insn
, last_insn
);
203 /* Locate or create a label for a given basic block. */
209 rtx label
= bb
->head
;
211 if (GET_CODE (label
) != CODE_LABEL
)
214 fprintf (rtl_dump_file
, "Emitting label for block %d\n", bb
->index
);
216 label
= block_label (bb
);
217 if (bb
->head
== PREV_INSN (RBI (bb
)->eff_head
))
218 RBI (bb
)->eff_head
= label
;
224 /* Locate the effective beginning and end of the insn chain for each
225 block, as defined by skip_insns_after_block above. */
228 record_effective_endpoints ()
230 rtx next_insn
= get_insns ();
233 for (i
= 0; i
< n_basic_blocks
; i
++)
235 basic_block bb
= BASIC_BLOCK (i
);
238 RBI (bb
)->eff_head
= next_insn
;
239 end
= skip_insns_after_block (bb
);
240 RBI (bb
)->eff_end
= end
;
241 next_insn
= NEXT_INSN (end
);
244 function_tail_eff_head
= next_insn
;
247 /* Return the next NOTE_INSN_BASIC_BLOCK after X. */
253 for (; x
; x
= NEXT_INSN (x
))
254 if (NOTE_INSN_BASIC_BLOCK_P (x
))
260 /* Return the fist NOTE_INSN_BASIC_BLOCK before X. */
266 for (; x
; x
= PREV_INSN (x
))
267 if (NOTE_INSN_BASIC_BLOCK_P (x
))
273 /* Determine and record the relationships between basic blocks and
274 scopes in scope tree S. */
277 relate_bbs_with_scopes (s
)
281 int i
, bbi1
, bbi2
, bbs_spanned
;
284 for (p
= s
->inner
; p
; p
= p
->next
)
285 relate_bbs_with_scopes (p
);
290 /* If the begin and end notes are both inside the same basic block,
291 or if they are both outside of basic blocks, then we know immediately
292 how they are related. Otherwise, we need to poke around to make the
294 if (s
->bb_beg
!= s
->bb_end
)
296 if (s
->bb_beg
&& s
->bb_end
)
298 /* Both notes are in different bbs. This implies that all the
299 basic blocks spanned by the pair of notes are contained in
301 bbi1
= s
->bb_beg
->index
;
302 bbi2
= s
->bb_end
->index
;
305 else if (! s
->bb_beg
)
307 /* First note is outside of a bb. If the scope spans more than
308 one basic block, then they all are contained within this
309 scope. Otherwise, this scope is contained within the basic
311 bbnote
= get_next_bb_note (s
->note_beg
);
315 if (NOTE_BASIC_BLOCK (bbnote
) == s
->bb_end
)
318 s
->bb_beg
= NOTE_BASIC_BLOCK (bbnote
);
322 bbi1
= NOTE_BASIC_BLOCK (bbnote
)->index
;
323 bbi2
= s
->bb_end
->index
;
328 else /* ! s->bb_end */
330 /* Second note is outside of a bb. If the scope spans more than
331 one basic block, then they all are contained within this
332 scope. Otherwise, this scope is contained within the basic
334 bbnote
= get_prev_bb_note (s
->note_end
);
338 if (NOTE_BASIC_BLOCK (bbnote
) == s
->bb_beg
)
341 s
->bb_end
= NOTE_BASIC_BLOCK (bbnote
);
345 bbi1
= s
->bb_beg
->index
;
346 bbi2
= NOTE_BASIC_BLOCK (bbnote
)->index
;
355 /* Both notes are in the same bb, which implies the block
356 contains this scope. */
360 /* Both notes are outside of any bbs. This implies that all the
361 basic blocks spanned by the pair of notes are contained in
363 There is a degenerate case to consider. If the notes do not
364 span any basic blocks, then it is an empty scope that can
365 safely be deleted or ignored. Mark these with level = -1. */
366 rtx x1
= get_next_bb_note (s
->note_beg
);
367 rtx x2
= get_prev_bb_note (s
->note_end
);
376 bbi1
= NOTE_BASIC_BLOCK (x1
)->index
;
377 bbi2
= NOTE_BASIC_BLOCK (x2
)->index
;
383 /* If the scope spans one or more basic blocks, we record them. We
384 only record the bbs that are immediately contained within this
385 scope. Note that if a scope is contained within a bb, we can tell
386 by checking that bb_beg = bb_end and that they are non-null. */
392 for (i
= bbi1
; i
<= bbi2
; i
++)
393 if (! RBI (BASIC_BLOCK (i
))->scope
)
396 s
->bbs
= xmalloc (s
->num_bbs
* sizeof (basic_block
));
397 for (i
= bbi1
; i
<= bbi2
; i
++)
399 basic_block curr_bb
= BASIC_BLOCK (i
);
400 if (! RBI (curr_bb
)->scope
)
402 s
->bbs
[j
++] = curr_bb
;
403 RBI (curr_bb
)->scope
= s
;
411 /* Allocate and initialize a new scope structure with scope level LEVEL,
412 and record the NOTE beginning the scope. */
415 make_new_scope (level
, note
)
419 scope new_scope
= xcalloc (1, sizeof (struct scope_def
));
421 new_scope
->level
= level
;
422 new_scope
->note_beg
= note
;
427 /* Build a forest representing the scope structure of the function.
428 Return a pointer to a structure describing the forest. */
431 build_scope_forest (forest
)
432 scope_forest_info
*forest
;
437 scope root
, curr_scope
= 0;
439 forest
->num_trees
= 0;
440 forest
->trees
= NULL
;
446 for (x
= get_insns (); x
; x
= NEXT_INSN (x
))
448 if (bbi
< n_basic_blocks
&& x
== BASIC_BLOCK (bbi
)->head
)
449 curr_bb
= BASIC_BLOCK (bbi
);
451 if (GET_CODE (x
) == NOTE
)
453 if (NOTE_LINE_NUMBER (x
) == NOTE_INSN_BLOCK_BEG
)
463 new_scope
= make_new_scope (level
, x
);
464 new_scope
->outer
= curr_scope
;
465 new_scope
->next
= NULL
;
466 if (! curr_scope
->inner
)
468 curr_scope
->inner
= new_scope
;
469 curr_scope
->inner_last
= new_scope
;
473 curr_scope
->inner_last
->next
= new_scope
;
474 curr_scope
->inner_last
= new_scope
;
476 curr_scope
= curr_scope
->inner_last
;
481 int ntrees
= forest
->num_trees
;
484 curr_scope
= make_new_scope (level
, x
);
486 forest
->trees
= xrealloc (forest
->trees
,
487 sizeof (scope
) * (ntrees
+ 1));
488 forest
->trees
[forest
->num_trees
++] = root
;
491 curr_scope
->bb_beg
= curr_bb
;
493 else if (NOTE_LINE_NUMBER (x
) == NOTE_INSN_BLOCK_END
)
495 curr_scope
->bb_end
= curr_bb
;
496 curr_scope
->note_end
= x
;
498 curr_scope
= curr_scope
->outer
;
504 if (curr_bb
&& curr_bb
->end
== x
)
511 for (i
= 0; i
< forest
->num_trees
; i
++)
512 relate_bbs_with_scopes (forest
->trees
[i
]);
515 /* Remove all NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes from the insn
519 remove_scope_notes ()
522 basic_block currbb
= NULL
;
524 for (x
= get_insns (); x
; x
= next
)
526 next
= NEXT_INSN (x
);
527 if (NOTE_INSN_BASIC_BLOCK_P (x
))
528 currbb
= NOTE_BASIC_BLOCK (x
);
530 if (GET_CODE (x
) == NOTE
531 && (NOTE_LINE_NUMBER (x
) == NOTE_INSN_BLOCK_BEG
532 || NOTE_LINE_NUMBER (x
) == NOTE_INSN_BLOCK_END
))
534 /* Check if the scope note happens to be the end of a bb. */
535 if (currbb
&& x
== currbb
->end
)
536 currbb
->end
= PREV_INSN (x
);
537 if (currbb
&& x
== currbb
->head
)
542 NEXT_INSN (PREV_INSN (x
)) = next
;
543 PREV_INSN (next
) = PREV_INSN (x
);
545 NEXT_INSN (x
) = NULL
;
546 PREV_INSN (x
) = NULL
;
554 /* Insert scope note pairs for a contained scope tree S after insn IP. */
557 insert_intra_1 (s
, ip
, bb
)
564 if (NOTE_BLOCK (s
->note_beg
))
566 *ip
= emit_note_after (NOTE_INSN_BLOCK_BEG
, *ip
);
567 NOTE_BLOCK (*ip
) = NOTE_BLOCK (s
->note_beg
);
570 for (p
= s
->inner
; p
; p
= p
->next
)
571 insert_intra_1 (p
, ip
, bb
);
573 if (NOTE_BLOCK (s
->note_beg
))
575 *ip
= emit_note_after (NOTE_INSN_BLOCK_END
, *ip
);
576 NOTE_BLOCK (*ip
) = NOTE_BLOCK (s
->note_end
);
580 /* Insert NOTE_INSN_BLOCK_END notes and NOTE_INSN_BLOCK_BEG notes for
581 scopes that are contained within BB. */
584 insert_intra_bb_scope_notes (bb
)
587 scope s
= RBI (bb
)->scope
;
595 if (GET_CODE (ip
) == CODE_LABEL
)
598 for (p
= s
->inner
; p
; p
= p
->next
)
600 if (p
->bb_beg
!= NULL
&& p
->bb_beg
== p
->bb_end
&& p
->bb_beg
== bb
)
601 insert_intra_1 (p
, &ip
, bb
);
605 /* Given two consecutive basic blocks BB1 and BB2 with different scopes,
606 insert NOTE_INSN_BLOCK_END notes after BB1 and NOTE_INSN_BLOCK_BEG
607 notes before BB2 such that the notes are correctly balanced. If BB1 or
608 BB2 is NULL, we are inserting scope notes for the first and last basic
609 blocks, respectively. */
612 insert_inter_bb_scope_notes (bb1
, bb2
)
619 /* It is possible that a basic block is not contained in any scope.
620 In that case, we either open or close a scope but not both. */
623 scope s1
= RBI (bb1
)->scope
;
624 scope s2
= RBI (bb2
)->scope
;
635 /* Find common ancestor scope. */
638 scope s1
= RBI (bb1
)->scope
;
639 scope s2
= RBI (bb2
)->scope
;
643 if (s1
->level
> s2
->level
)
645 else if (s2
->level
> s1
->level
)
665 ip
= RBI (bb1
)->eff_end
;
666 for (s
= RBI (bb1
)->scope
; s
!= com
; s
= s
->outer
)
667 if (NOTE_BLOCK (s
->note_beg
))
669 ip
= emit_note_after (NOTE_INSN_BLOCK_END
, ip
);
670 NOTE_BLOCK (ip
) = NOTE_BLOCK (s
->note_end
);
673 /* Emitting note may move the end of basic block to unwanted place. */
683 for (s
= RBI (bb2
)->scope
; s
!= com
; s
= s
->outer
)
684 if (NOTE_BLOCK (s
->note_beg
))
686 ip
= emit_note_before (NOTE_INSN_BLOCK_BEG
, ip
);
687 NOTE_BLOCK (ip
) = NOTE_BLOCK (s
->note_beg
);
693 /* Rebuild all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes based
694 on the scope forest and the newly reordered basic blocks. */
697 rebuild_scope_notes (forest
)
698 scope_forest_info
*forest
;
702 if (forest
->num_trees
== 0)
705 /* Start by opening the scopes before the first basic block. */
706 insert_inter_bb_scope_notes (NULL
, BASIC_BLOCK (0));
708 /* Then, open and close scopes as needed between blocks. */
709 for (i
= 0; i
< n_basic_blocks
- 1; i
++)
711 basic_block bb1
= BASIC_BLOCK (i
);
712 basic_block bb2
= BASIC_BLOCK (i
+ 1);
714 if (RBI (bb1
)->scope
!= RBI (bb2
)->scope
)
715 insert_inter_bb_scope_notes (bb1
, bb2
);
716 insert_intra_bb_scope_notes (bb1
);
719 /* Finally, close the scopes after the last basic block. */
720 insert_inter_bb_scope_notes (BASIC_BLOCK (n_basic_blocks
- 1), NULL
);
721 insert_intra_bb_scope_notes (BASIC_BLOCK (n_basic_blocks
- 1));
724 /* Free the storage associated with the scope tree at S. */
727 free_scope_forest_1 (s
)
732 for (p
= s
->inner
; p
; p
= next
)
735 free_scope_forest_1 (p
);
743 /* Free the storage associated with the scope forest. */
746 free_scope_forest (forest
)
747 scope_forest_info
*forest
;
751 for (i
= 0; i
< forest
->num_trees
; i
++)
752 free_scope_forest_1 (forest
->trees
[i
]);
755 /* Visualize the scope forest. */
758 dump_scope_forest (forest
)
759 scope_forest_info
*forest
;
763 if (forest
->num_trees
== 0)
764 fprintf (stderr
, "\n< Empty scope forest >\n");
766 fprintf (stderr
, "\n< Scope forest >\n");
768 for (i
= 0; i
< forest
->num_trees
; i
++)
769 dump_scope_forest_1 (forest
->trees
[i
], 0);
772 /* Recursive portion of dump_scope_forest. */
775 dump_scope_forest_1 (s
, indent
)
782 if (s
->bb_beg
!= NULL
&& s
->bb_beg
== s
->bb_end
783 && RBI (s
->bb_beg
)->scope
784 && RBI (s
->bb_beg
)->scope
->level
+ 1 == s
->level
)
786 fprintf (stderr
, "%*s", indent
, "");
787 fprintf (stderr
, "BB%d:\n", s
->bb_beg
->index
);
790 fprintf (stderr
, "%*s", indent
, "");
791 fprintf (stderr
, "{ level %d (block %p)\n", s
->level
,
792 (PTR
) NOTE_BLOCK (s
->note_beg
));
794 fprintf (stderr
, "%*s%s", indent
, "", "bbs:");
795 for (i
= 0; i
< s
->num_bbs
; i
++)
796 fprintf (stderr
, " %d", s
->bbs
[i
]->index
);
797 fprintf (stderr
, "\n");
799 for (p
= s
->inner
; p
; p
= p
->next
)
800 dump_scope_forest_1 (p
, indent
+ 2);
802 fprintf (stderr
, "%*s", indent
, "");
803 fprintf (stderr
, "}\n");
806 /* Given a reorder chain, rearrange the code to match. */
809 fixup_reorder_chain ()
811 basic_block bb
, last_bb
;
814 int old_n_basic_blocks
= n_basic_blocks
;
816 /* First do the bulk reordering -- rechain the blocks without regard to
817 the needed changes to jumps and labels. */
819 for (last_bb
= BASIC_BLOCK (0), bb
= RBI (last_bb
)->next
, index
= 1;
821 last_bb
= bb
, bb
= RBI (bb
)->next
, index
++)
823 rtx last_e
= RBI (last_bb
)->eff_end
;
824 rtx curr_h
= RBI (bb
)->eff_head
;
826 NEXT_INSN (last_e
) = curr_h
;
827 PREV_INSN (curr_h
) = last_e
;
830 if (index
!= n_basic_blocks
)
833 insn
= RBI (last_bb
)->eff_end
;
834 NEXT_INSN (insn
) = function_tail_eff_head
;
835 if (function_tail_eff_head
)
836 PREV_INSN (function_tail_eff_head
) = insn
;
838 while (NEXT_INSN (insn
))
839 insn
= NEXT_INSN (insn
);
841 set_last_insn (insn
);
842 #ifdef ENABLE_CHECKING
843 verify_insn_chain ();
846 /* Now add jumps and labels as needed to match the blocks new
849 for (bb
= BASIC_BLOCK (0); bb
; bb
= RBI (bb
)->next
)
851 edge e_fall
, e_taken
, e
;
855 if (bb
->succ
== NULL
)
858 /* Find the old fallthru edge, and another non-EH edge for
860 e_taken
= e_fall
= NULL
;
861 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
862 if (e
->flags
& EDGE_FALLTHRU
)
864 else if (! (e
->flags
& EDGE_EH
))
867 bb_end_insn
= bb
->end
;
868 if (GET_CODE (bb_end_insn
) == JUMP_INSN
)
870 if (any_condjump_p (bb_end_insn
))
872 /* If the old fallthru is still next, nothing to do. */
873 if (RBI (bb
)->next
== e_fall
->dest
875 && e_fall
->dest
== EXIT_BLOCK_PTR
))
878 /* There is one special case: if *neither* block is next,
879 such as happens at the very end of a function, then we'll
880 need to add a new unconditional jump. Choose the taken
881 edge based on known or assumed probability. */
882 if (RBI (bb
)->next
!= e_taken
->dest
)
884 rtx note
= find_reg_note (bb_end_insn
, REG_BR_PROB
, 0);
887 && INTVAL (XEXP (note
, 0)) < REG_BR_PROB_BASE
/ 2
888 && invert_jump (bb_end_insn
,
889 label_for_bb (e_fall
->dest
), 0))
891 e_fall
->flags
&= ~EDGE_FALLTHRU
;
892 e_taken
->flags
|= EDGE_FALLTHRU
;
893 e
= e_fall
, e_fall
= e_taken
, e_taken
= e
;
897 /* Otherwise we can try to invert the jump. This will
898 basically never fail, however, keep up the pretense. */
899 else if (invert_jump (bb_end_insn
,
900 label_for_bb (e_fall
->dest
), 0))
902 e_fall
->flags
&= ~EDGE_FALLTHRU
;
903 e_taken
->flags
|= EDGE_FALLTHRU
;
907 else if (returnjump_p (bb_end_insn
))
911 /* Otherwise we have some switch or computed jump. In the
912 99% case, there should not have been a fallthru edge. */
916 #ifdef CASE_DROPS_THROUGH
917 /* Except for VAX. Since we didn't have predication for the
918 tablejump, the fallthru block should not have moved. */
919 if (RBI (bb
)->next
== e_fall
->dest
)
921 bb_end_insn
= skip_insns_after_block (bb
);
929 /* No fallthru implies a noreturn function with EH edges, or
930 something similarly bizarre. In any case, we don't need to
935 /* If the fallthru block is still next, nothing to do. */
936 if (RBI (bb
)->next
== e_fall
->dest
)
939 /* A fallthru to exit block. */
940 if (!RBI (bb
)->next
&& e_fall
->dest
== EXIT_BLOCK_PTR
)
944 /* We got here if we need to add a new jump insn. */
945 nb
= force_nonfallthru (e_fall
);
948 alloc_aux_for_block (nb
, sizeof (struct reorder_block_def
));
949 RBI (nb
)->eff_head
= nb
->head
;
950 RBI (nb
)->eff_end
= NEXT_INSN (nb
->end
);
951 RBI (nb
)->scope
= RBI (bb
)->scope
;
952 RBI (nb
)->visited
= 1;
953 RBI (nb
)->next
= RBI (bb
)->next
;
955 /* Don't process this new block. */
960 /* Put basic_block_info in the new order. */
961 bb
= BASIC_BLOCK (0);
965 fprintf (rtl_dump_file
, "Reordered sequence:\n");
967 for (; bb
; bb
= RBI (bb
)->next
, index
++)
970 fprintf (rtl_dump_file
, " %i %sbb %i freq %i\n", index
,
971 bb
->index
>= old_n_basic_blocks
? "compensation " : "",
976 BASIC_BLOCK (index
) = bb
;
980 /* Perform sanity checks on the insn chain.
981 1. Check that next/prev pointers are consistent in both the forward and
983 2. Count insns in chain, going both directions, and check if equal.
984 3. Check that get_last_insn () returns the actual end of chain. */
990 int insn_cnt1
, insn_cnt2
;
992 for (prevx
= NULL
, insn_cnt1
= 1, x
= get_insns ();
994 prevx
= x
, insn_cnt1
++, x
= NEXT_INSN (x
))
995 if (PREV_INSN (x
) != prevx
)
998 if (prevx
!= get_last_insn ())
1001 for (nextx
= NULL
, insn_cnt2
= 1, x
= get_last_insn ();
1003 nextx
= x
, insn_cnt2
++, x
= PREV_INSN (x
))
1004 if (NEXT_INSN (x
) != nextx
)
1007 if (insn_cnt1
!= insn_cnt2
)
1011 /* The block falling through to exit must be the last one in the reordered
1012 chain. Ensure it is. */
1015 fixup_fallthru_exit_predecessor ()
1018 basic_block bb
= NULL
;
1020 for (e
= EXIT_BLOCK_PTR
->pred
; e
; e
= e
->pred_next
)
1021 if (e
->flags
& EDGE_FALLTHRU
)
1024 if (bb
&& RBI (bb
)->next
)
1026 basic_block c
= BASIC_BLOCK (0);
1028 while (RBI (c
)->next
!= bb
)
1031 RBI (c
)->next
= RBI (bb
)->next
;
1032 while (RBI (c
)->next
)
1036 RBI (bb
)->next
= NULL
;
1040 /* Main entry point to this module: initialize the datastructures for CFG
1044 cfg_layout_initialize ()
1046 alloc_aux_for_blocks (sizeof (struct reorder_block_def
));
1048 build_scope_forest (&forest
);
1049 remove_scope_notes ();
1051 record_effective_endpoints ();
1054 /* Finalize the changes: reorder insn list according to the sequence, enter
1055 compensation code, rebuild scope forest. */
1058 cfg_layout_finalize ()
1060 fixup_fallthru_exit_predecessor ();
1061 fixup_reorder_chain ();
1063 #ifdef ENABLE_CHECKING
1064 verify_insn_chain ();
1067 rebuild_scope_notes (&forest
);
1068 free_scope_forest (&forest
);
1071 free_aux_for_blocks ();
1073 #ifdef ENABLE_CHECKING
1074 verify_flow_info ();