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_before_1 PARAMS ((scope, rtx *, basic_block));
99 static void insert_intra_1 PARAMS ((scope, rtx *, basic_block));
100 static void insert_intra_bb_scope_notes PARAMS ((basic_block));
101 static void insert_inter_bb_scope_notes PARAMS ((basic_block, basic_block));
102 static void rebuild_scope_notes PARAMS ((scope_forest_info *));
103 static void free_scope_forest_1 PARAMS ((scope));
104 static void free_scope_forest PARAMS ((scope_forest_info *));
105 void dump_scope_forest PARAMS ((scope_forest_info *));
106 static void dump_scope_forest_1 PARAMS ((scope, int));
108 static rtx get_next_bb_note PARAMS ((rtx));
109 static rtx get_prev_bb_note PARAMS ((rtx));
111 void verify_insn_chain PARAMS ((void));
112 static void fixup_fallthru_exit_predecessor PARAMS ((void));
114 /* Skip over inter-block insns occurring after BB which are typically
115 associated with BB (e.g., barriers). If there are any such insns,
116 we return the last one. Otherwise, we return the end of BB. */
119 skip_insns_after_block (bb)
122 rtx insn, last_insn, next_head, prev;
124 next_head = NULL_RTX;
125 if (bb->index + 1 != n_basic_blocks)
126 next_head = BASIC_BLOCK (bb->index + 1)->head;
128 for (last_insn = insn = bb->end; (insn = NEXT_INSN (insn)) != 0; )
130 if (insn == next_head)
133 switch (GET_CODE (insn))
140 switch (NOTE_LINE_NUMBER (insn))
142 case NOTE_INSN_LOOP_END:
143 case NOTE_INSN_BLOCK_END:
146 case NOTE_INSN_DELETED:
147 case NOTE_INSN_DELETED_LABEL:
158 && GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
159 && (GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_VEC
160 || GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_DIFF_VEC))
162 insn = NEXT_INSN (insn);
175 /* It is possible to hit contradictory sequence. For instance:
181 Where barrier belongs to jump_insn, but the note does not. This can be
182 created by removing the basic block originally following
183 NOTE_INSN_LOOP_BEG. In such case reorder the notes. */
185 for (insn = last_insn; insn != bb->end; insn = prev)
187 prev = PREV_INSN (insn);
188 if (GET_CODE (insn) == NOTE)
189 switch (NOTE_LINE_NUMBER (insn))
191 case NOTE_INSN_LOOP_END:
192 case NOTE_INSN_BLOCK_END:
193 case NOTE_INSN_DELETED:
194 case NOTE_INSN_DELETED_LABEL:
197 reorder_insns (insn, insn, last_insn);
204 /* Locate or create a label for a given basic block. */
210 rtx label = bb->head;
212 if (GET_CODE (label) != CODE_LABEL)
215 fprintf (rtl_dump_file, "Emitting label for block %d\n", bb->index);
217 label = block_label (bb);
218 if (bb->head == PREV_INSN (RBI (bb)->eff_head))
219 RBI (bb)->eff_head = label;
225 /* Locate the effective beginning and end of the insn chain for each
226 block, as defined by skip_insns_after_block above. */
229 record_effective_endpoints ()
231 rtx next_insn = get_insns ();
234 for (i = 0; i < n_basic_blocks; i++)
236 basic_block bb = BASIC_BLOCK (i);
239 RBI (bb)->eff_head = next_insn;
240 end = skip_insns_after_block (bb);
241 RBI (bb)->eff_end = end;
242 next_insn = NEXT_INSN (end);
245 function_tail_eff_head = next_insn;
248 /* Return the next NOTE_INSN_BASIC_BLOCK after X. */
254 for (; x; x = NEXT_INSN (x))
255 if (NOTE_INSN_BASIC_BLOCK_P (x))
261 /* Return the fist NOTE_INSN_BASIC_BLOCK before X. */
267 for (; x; x = PREV_INSN (x))
268 if (NOTE_INSN_BASIC_BLOCK_P (x))
274 /* Determine and record the relationships between basic blocks and
275 scopes in scope tree S. */
278 relate_bbs_with_scopes (s)
282 int i, bbi1, bbi2, bbs_spanned;
285 for (p = s->inner; p; p = p->next)
286 relate_bbs_with_scopes (p);
291 /* If the begin and end notes are both inside the same basic block,
292 or if they are both outside of basic blocks, then we know immediately
293 how they are related. Otherwise, we need to poke around to make the
295 if (s->bb_beg != s->bb_end)
297 if (s->bb_beg && s->bb_end)
299 /* Both notes are in different bbs. This implies that all the
300 basic blocks spanned by the pair of notes are contained in
302 bbi1 = s->bb_beg->index;
303 bbi2 = s->bb_end->index;
306 else if (! s->bb_beg)
308 /* First note is outside of a bb. If the scope spans more than
309 one basic block, then they all are contained within this
310 scope. Otherwise, this scope is contained within the basic
312 bbnote = get_next_bb_note (s->note_beg);
316 if (NOTE_BASIC_BLOCK (bbnote) == s->bb_end)
319 s->bb_beg = NOTE_BASIC_BLOCK (bbnote);
323 bbi1 = NOTE_BASIC_BLOCK (bbnote)->index;
324 bbi2 = s->bb_end->index;
329 else /* ! s->bb_end */
331 /* Second note is outside of a bb. If the scope spans more than
332 one basic block, then they all are contained within this
333 scope. Otherwise, this scope is contained within the basic
335 bbnote = get_prev_bb_note (s->note_end);
339 if (NOTE_BASIC_BLOCK (bbnote) == s->bb_beg)
342 s->bb_end = NOTE_BASIC_BLOCK (bbnote);
346 bbi1 = s->bb_beg->index;
347 bbi2 = NOTE_BASIC_BLOCK (bbnote)->index;
356 /* Both notes are in the same bb, which implies the block
357 contains this scope. */
361 /* Both notes are outside of any bbs. This implies that all the
362 basic blocks spanned by the pair of notes are contained in
364 There is a degenerate case to consider. If the notes do not
365 span any basic blocks, then it is an empty scope that can
366 safely be deleted or ignored. Mark these with level = -1. */
367 rtx x1 = get_next_bb_note (s->note_beg);
368 rtx x2 = get_prev_bb_note (s->note_end);
377 bbi1 = NOTE_BASIC_BLOCK (x1)->index;
378 bbi2 = NOTE_BASIC_BLOCK (x2)->index;
384 /* If the scope spans one or more basic blocks, we record them. We
385 only record the bbs that are immediately contained within this
386 scope. Note that if a scope is contained within a bb, we can tell
387 by checking that bb_beg = bb_end and that they are non-null. */
393 for (i = bbi1; i <= bbi2; i++)
394 if (! RBI (BASIC_BLOCK (i))->scope)
397 s->bbs = xmalloc (s->num_bbs * sizeof (basic_block));
398 for (i = bbi1; i <= bbi2; i++)
400 basic_block curr_bb = BASIC_BLOCK (i);
401 if (! RBI (curr_bb)->scope)
403 s->bbs[j++] = curr_bb;
404 RBI (curr_bb)->scope = s;
412 /* Allocate and initialize a new scope structure with scope level LEVEL,
413 and record the NOTE beginning the scope. */
416 make_new_scope (level, note)
420 scope new_scope = xcalloc (1, sizeof (struct scope_def));
422 new_scope->level = level;
423 new_scope->note_beg = note;
428 /* Build a forest representing the scope structure of the function.
429 Return a pointer to a structure describing the forest. */
432 build_scope_forest (forest)
433 scope_forest_info *forest;
438 scope root, curr_scope = 0;
440 forest->num_trees = 0;
441 forest->trees = NULL;
447 for (x = get_insns (); x; x = NEXT_INSN (x))
449 if (bbi < n_basic_blocks && x == BASIC_BLOCK (bbi)->head)
450 curr_bb = BASIC_BLOCK (bbi);
452 if (GET_CODE (x) == NOTE)
454 if (NOTE_LINE_NUMBER (x) == NOTE_INSN_BLOCK_BEG)
464 new_scope = make_new_scope (level, x);
465 new_scope->outer = curr_scope;
466 new_scope->next = NULL;
467 if (! curr_scope->inner)
469 curr_scope->inner = new_scope;
470 curr_scope->inner_last = new_scope;
474 curr_scope->inner_last->next = new_scope;
475 curr_scope->inner_last = new_scope;
477 curr_scope = curr_scope->inner_last;
482 int ntrees = forest->num_trees;
485 curr_scope = make_new_scope (level, x);
487 forest->trees = xrealloc (forest->trees,
488 sizeof (scope) * (ntrees + 1));
489 forest->trees[forest->num_trees++] = root;
492 curr_scope->bb_beg = curr_bb;
494 else if (NOTE_LINE_NUMBER (x) == NOTE_INSN_BLOCK_END)
496 curr_scope->bb_end = curr_bb;
497 curr_scope->note_end = x;
499 curr_scope = curr_scope->outer;
505 if (curr_bb && curr_bb->end == x)
512 for (i = 0; i < forest->num_trees; i++)
513 relate_bbs_with_scopes (forest->trees[i]);
516 /* Remove all NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes from the insn
520 remove_scope_notes ()
523 basic_block currbb = NULL;
525 for (x = get_insns (); x; x = next)
527 next = NEXT_INSN (x);
528 if (NOTE_INSN_BASIC_BLOCK_P (x))
529 currbb = NOTE_BASIC_BLOCK (x);
531 if (GET_CODE (x) == NOTE
532 && (NOTE_LINE_NUMBER (x) == NOTE_INSN_BLOCK_BEG
533 || NOTE_LINE_NUMBER (x) == NOTE_INSN_BLOCK_END))
535 /* Check if the scope note happens to be the end of a bb. */
536 if (currbb && x == currbb->end)
537 currbb->end = PREV_INSN (x);
538 if (currbb && x == currbb->head)
543 NEXT_INSN (PREV_INSN (x)) = next;
545 PREV_INSN (next) = PREV_INSN (x);
547 NEXT_INSN (x) = NULL;
548 PREV_INSN (x) = NULL;
556 /* Insert scope note pairs for a contained scope tree S after insn IP. */
559 insert_intra_1 (s, ip, bb)
566 if (NOTE_BLOCK (s->note_beg))
568 *ip = emit_note_after (NOTE_INSN_BLOCK_BEG, *ip);
569 NOTE_BLOCK (*ip) = NOTE_BLOCK (s->note_beg);
572 for (p = s->inner; p; p = p->next)
573 insert_intra_1 (p, ip, bb);
575 if (NOTE_BLOCK (s->note_beg))
577 *ip = emit_note_after (NOTE_INSN_BLOCK_END, *ip);
578 NOTE_BLOCK (*ip) = NOTE_BLOCK (s->note_end);
582 /* Insert scope note pairs for a contained scope tree S before insn IP. */
585 insert_intra_before_1 (s, ip, bb)
592 if (NOTE_BLOCK (s->note_beg))
594 *ip = emit_note_before (NOTE_INSN_BLOCK_END, *ip);
595 NOTE_BLOCK (*ip) = NOTE_BLOCK (s->note_end);
598 for (p = s->inner; p; p = p->next)
599 insert_intra_before_1 (p, ip, bb);
601 if (NOTE_BLOCK (s->note_beg))
603 *ip = emit_note_before (NOTE_INSN_BLOCK_BEG, *ip);
604 NOTE_BLOCK (*ip) = NOTE_BLOCK (s->note_beg);
608 /* Insert NOTE_INSN_BLOCK_END notes and NOTE_INSN_BLOCK_BEG notes for
609 scopes that are contained within BB. */
612 insert_intra_bb_scope_notes (bb)
615 scope s = RBI (bb)->scope;
623 if (GET_CODE (ip) == CODE_LABEL)
626 for (p = s->inner; p; p = p->next)
628 if (p->bb_beg != NULL && p->bb_beg == p->bb_end && p->bb_beg == bb)
629 insert_intra_1 (p, &ip, bb);
633 /* Given two consecutive basic blocks BB1 and BB2 with different scopes,
634 insert NOTE_INSN_BLOCK_END notes after BB1 and NOTE_INSN_BLOCK_BEG
635 notes before BB2 such that the notes are correctly balanced. If BB1 or
636 BB2 is NULL, we are inserting scope notes for the first and last basic
637 blocks, respectively. */
640 insert_inter_bb_scope_notes (bb1, bb2)
647 /* It is possible that a basic block is not contained in any scope.
648 In that case, we either open or close a scope but not both. */
651 scope s1 = RBI (bb1)->scope;
652 scope s2 = RBI (bb2)->scope;
663 /* Find common ancestor scope. */
666 scope s1 = RBI (bb1)->scope;
667 scope s2 = RBI (bb2)->scope;
671 if (s1->level > s2->level)
673 else if (s2->level > s1->level)
693 ip = RBI (bb1)->eff_end;
694 for (s = RBI (bb1)->scope; s != com; s = s->outer)
696 if (NOTE_BLOCK (s->note_beg))
698 ip = emit_note_after (NOTE_INSN_BLOCK_END, ip);
699 NOTE_BLOCK (ip) = NOTE_BLOCK (s->note_end);
702 /* Now emit all sibling scopes which don't span any basic
705 for (p = s->outer->inner; p; p = p->next)
706 if (p != s && p->bb_beg == bb1 && p->bb_beg == p->bb_end)
707 insert_intra_1 (p, &ip, bb1);
710 /* Emitting note may move the end of basic block to unwanted place. */
720 for (s = RBI (bb2)->scope; s != com; s = s->outer)
722 if (NOTE_BLOCK (s->note_beg))
724 ip = emit_note_before (NOTE_INSN_BLOCK_BEG, ip);
725 NOTE_BLOCK (ip) = NOTE_BLOCK (s->note_beg);
728 /* Now emit all sibling scopes which don't span any basic
731 for (p = s->outer->inner; p; p = p->next)
732 if (p != s && p->bb_beg == bb2 && p->bb_beg == p->bb_end)
733 insert_intra_before_1 (p, &ip, bb2);
739 /* Rebuild all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes based
740 on the scope forest and the newly reordered basic blocks. */
743 rebuild_scope_notes (forest)
744 scope_forest_info *forest;
748 if (forest->num_trees == 0)
751 /* Start by opening the scopes before the first basic block. */
752 insert_inter_bb_scope_notes (NULL, BASIC_BLOCK (0));
754 /* Then, open and close scopes as needed between blocks. */
755 for (i = 0; i < n_basic_blocks - 1; i++)
757 basic_block bb1 = BASIC_BLOCK (i);
758 basic_block bb2 = BASIC_BLOCK (i + 1);
760 if (RBI (bb1)->scope != RBI (bb2)->scope)
761 insert_inter_bb_scope_notes (bb1, bb2);
762 insert_intra_bb_scope_notes (bb1);
765 /* Finally, close the scopes after the last basic block. */
766 insert_inter_bb_scope_notes (BASIC_BLOCK (n_basic_blocks - 1), NULL);
767 insert_intra_bb_scope_notes (BASIC_BLOCK (n_basic_blocks - 1));
770 /* Free the storage associated with the scope tree at S. */
773 free_scope_forest_1 (s)
778 for (p = s->inner; p; p = next)
781 free_scope_forest_1 (p);
789 /* Free the storage associated with the scope forest. */
792 free_scope_forest (forest)
793 scope_forest_info *forest;
797 for (i = 0; i < forest->num_trees; i++)
798 free_scope_forest_1 (forest->trees[i]);
801 /* Visualize the scope forest. */
804 dump_scope_forest (forest)
805 scope_forest_info *forest;
809 if (forest->num_trees == 0)
810 fprintf (stderr, "\n< Empty scope forest >\n");
812 fprintf (stderr, "\n< Scope forest >\n");
814 for (i = 0; i < forest->num_trees; i++)
815 dump_scope_forest_1 (forest->trees[i], 0);
818 /* Recursive portion of dump_scope_forest. */
821 dump_scope_forest_1 (s, indent)
828 if (s->bb_beg != NULL && s->bb_beg == s->bb_end
829 && RBI (s->bb_beg)->scope
830 && RBI (s->bb_beg)->scope->level + 1 == s->level)
832 fprintf (stderr, "%*s", indent, "");
833 fprintf (stderr, "BB%d:\n", s->bb_beg->index);
836 fprintf (stderr, "%*s", indent, "");
837 fprintf (stderr, "{ level %d (block %p)\n", s->level,
838 (PTR) NOTE_BLOCK (s->note_beg));
840 fprintf (stderr, "%*s%s", indent, "", "bbs:");
841 for (i = 0; i < s->num_bbs; i++)
842 fprintf (stderr, " %d", s->bbs[i]->index);
843 fprintf (stderr, "\n");
845 for (p = s->inner; p; p = p->next)
846 dump_scope_forest_1 (p, indent + 2);
848 fprintf (stderr, "%*s", indent, "");
849 fprintf (stderr, "}\n");
852 /* Given a reorder chain, rearrange the code to match. */
855 fixup_reorder_chain ()
857 basic_block bb, last_bb;
860 int old_n_basic_blocks = n_basic_blocks;
862 /* First do the bulk reordering -- rechain the blocks without regard to
863 the needed changes to jumps and labels. */
865 for (last_bb = BASIC_BLOCK (0), bb = RBI (last_bb)->next, index = 1;
867 last_bb = bb, bb = RBI (bb)->next, index++)
869 rtx last_e = RBI (last_bb)->eff_end;
870 rtx curr_h = RBI (bb)->eff_head;
872 NEXT_INSN (last_e) = curr_h;
873 PREV_INSN (curr_h) = last_e;
876 if (index != n_basic_blocks)
879 insn = RBI (last_bb)->eff_end;
880 NEXT_INSN (insn) = function_tail_eff_head;
881 if (function_tail_eff_head)
882 PREV_INSN (function_tail_eff_head) = insn;
884 while (NEXT_INSN (insn))
885 insn = NEXT_INSN (insn);
887 set_last_insn (insn);
888 #ifdef ENABLE_CHECKING
889 verify_insn_chain ();
892 /* Now add jumps and labels as needed to match the blocks new
895 for (bb = BASIC_BLOCK (0); bb ; bb = RBI (bb)->next)
897 edge e_fall, e_taken, e;
901 if (bb->succ == NULL)
904 /* Find the old fallthru edge, and another non-EH edge for
906 e_taken = e_fall = NULL;
907 for (e = bb->succ; e ; e = e->succ_next)
908 if (e->flags & EDGE_FALLTHRU)
910 else if (! (e->flags & EDGE_EH))
913 bb_end_insn = bb->end;
914 if (GET_CODE (bb_end_insn) == JUMP_INSN)
916 if (any_condjump_p (bb_end_insn))
918 /* If the old fallthru is still next, nothing to do. */
919 if (RBI (bb)->next == e_fall->dest
921 && e_fall->dest == EXIT_BLOCK_PTR))
924 /* There is one special case: if *neither* block is next,
925 such as happens at the very end of a function, then we'll
926 need to add a new unconditional jump. Choose the taken
927 edge based on known or assumed probability. */
928 if (RBI (bb)->next != e_taken->dest)
930 rtx note = find_reg_note (bb_end_insn, REG_BR_PROB, 0);
933 && INTVAL (XEXP (note, 0)) < REG_BR_PROB_BASE / 2
934 && invert_jump (bb_end_insn,
935 label_for_bb (e_fall->dest), 0))
937 e_fall->flags &= ~EDGE_FALLTHRU;
938 e_taken->flags |= EDGE_FALLTHRU;
939 e = e_fall, e_fall = e_taken, e_taken = e;
943 /* Otherwise we can try to invert the jump. This will
944 basically never fail, however, keep up the pretense. */
945 else if (invert_jump (bb_end_insn,
946 label_for_bb (e_fall->dest), 0))
948 e_fall->flags &= ~EDGE_FALLTHRU;
949 e_taken->flags |= EDGE_FALLTHRU;
953 else if (returnjump_p (bb_end_insn))
957 /* Otherwise we have some switch or computed jump. In the
958 99% case, there should not have been a fallthru edge. */
962 #ifdef CASE_DROPS_THROUGH
963 /* Except for VAX. Since we didn't have predication for the
964 tablejump, the fallthru block should not have moved. */
965 if (RBI (bb)->next == e_fall->dest)
967 bb_end_insn = skip_insns_after_block (bb);
975 /* No fallthru implies a noreturn function with EH edges, or
976 something similarly bizarre. In any case, we don't need to
981 /* If the fallthru block is still next, nothing to do. */
982 if (RBI (bb)->next == e_fall->dest)
985 /* A fallthru to exit block. */
986 if (!RBI (bb)->next && e_fall->dest == EXIT_BLOCK_PTR)
990 /* We got here if we need to add a new jump insn. */
991 nb = force_nonfallthru (e_fall);
994 alloc_aux_for_block (nb, sizeof (struct reorder_block_def));
995 RBI (nb)->eff_head = nb->head;
996 RBI (nb)->eff_end = NEXT_INSN (nb->end);
997 RBI (nb)->scope = RBI (bb)->scope;
998 RBI (nb)->visited = 1;
999 RBI (nb)->next = RBI (bb)->next;
1000 RBI (bb)->next = nb;
1001 /* Don't process this new block. */
1006 /* Put basic_block_info in the new order. */
1007 bb = BASIC_BLOCK (0);
1011 fprintf (rtl_dump_file, "Reordered sequence:\n");
1013 for (; bb; bb = RBI (bb)->next, index++)
1016 fprintf (rtl_dump_file, " %i %sbb %i freq %i\n", index,
1017 bb->index >= old_n_basic_blocks ? "compensation " : "",
1022 BASIC_BLOCK (index) = bb;
1026 /* Perform sanity checks on the insn chain.
1027 1. Check that next/prev pointers are consistent in both the forward and
1029 2. Count insns in chain, going both directions, and check if equal.
1030 3. Check that get_last_insn () returns the actual end of chain. */
1033 verify_insn_chain ()
1035 rtx x, prevx, nextx;
1036 int insn_cnt1, insn_cnt2;
1038 for (prevx = NULL, insn_cnt1 = 1, x = get_insns ();
1040 prevx = x, insn_cnt1++, x = NEXT_INSN (x))
1041 if (PREV_INSN (x) != prevx)
1044 if (prevx != get_last_insn ())
1047 for (nextx = NULL, insn_cnt2 = 1, x = get_last_insn ();
1049 nextx = x, insn_cnt2++, x = PREV_INSN (x))
1050 if (NEXT_INSN (x) != nextx)
1053 if (insn_cnt1 != insn_cnt2)
1057 /* The block falling through to exit must be the last one in the reordered
1058 chain. Ensure it is. */
1061 fixup_fallthru_exit_predecessor ()
1064 basic_block bb = NULL;
1066 for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
1067 if (e->flags & EDGE_FALLTHRU)
1070 if (bb && RBI (bb)->next)
1072 basic_block c = BASIC_BLOCK (0);
1074 while (RBI (c)->next != bb)
1077 RBI (c)->next = RBI (bb)->next;
1078 while (RBI (c)->next)
1082 RBI (bb)->next = NULL;
1086 /* Main entry point to this module: initialize the datastructures for CFG
1090 cfg_layout_initialize ()
1092 alloc_aux_for_blocks (sizeof (struct reorder_block_def));
1094 build_scope_forest (&forest);
1095 remove_scope_notes ();
1097 record_effective_endpoints ();
1100 /* Finalize the changes: reorder insn list according to the sequence, enter
1101 compensation code, rebuild scope forest. */
1104 cfg_layout_finalize ()
1106 fixup_fallthru_exit_predecessor ();
1107 fixup_reorder_chain ();
1109 #ifdef ENABLE_CHECKING
1110 verify_insn_chain ();
1113 rebuild_scope_notes (&forest);
1114 free_scope_forest (&forest);
1117 free_aux_for_blocks ();
1119 #ifdef ENABLE_CHECKING
1120 verify_flow_info ();