1 /* Basic block reordering routines for the GNU compiler.
2 Copyright (C) 2000 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
14 License for more details.
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 "Profile Guided Code Positioning"
24 Pettis and Hanson; PLDI '90.
30 if (p) goto A; // predict taken
33 if (q) goto B; // predict taken
39 We'll currently reorder this as
68 This requires that we be able to duplicate the jump at A, and
69 adjust the graph traversal such that greedy placement doesn't
70 fix D before C is considered.
72 (2) Coordinate with shorten_branches to minimize the number of
75 (3) Invent a method by which sufficiently non-predicted code can
76 be moved to either the end of the section or another section
77 entirely. Some sort of NOTE_INSN note would work fine.
79 This completely scroggs all debugging formats, so the user
80 would have to explicitly ask for it.
88 #include "hard-reg-set.h"
89 #include "basic-block.h"
90 #include "insn-config.h"
101 #ifndef HAVE_epilogue
102 #define HAVE_epilogue 0
106 /* The contents of the current function definition are allocated
107 in this obstack, and all are freed at the end of the function.
108 For top-level functions, this is temporary_obstack.
109 Separate obstacks are made for nested functions. */
111 extern struct obstack flow_obstack
;
114 /* Structure to hold information about lexical scopes. */
115 typedef struct scope_def
119 /* The NOTE_INSN_BLOCK_BEG that started this scope. */
122 /* The NOTE_INSN_BLOCK_END that ended this scope. */
125 /* The bb containing note_beg (if any). */
128 /* The bb containing note_end (if any). */
131 /* List of basic blocks contained within this scope. */
134 /* Number of blocks contained within this scope. */
137 /* The outer scope or NULL if outermost scope. */
138 struct scope_def
*outer
;
140 /* The first inner scope or NULL if innermost scope. */
141 struct scope_def
*inner
;
143 /* The last inner scope or NULL if innermost scope. */
144 struct scope_def
*inner_last
;
146 /* Link to the next (sibling) scope. */
147 struct scope_def
*next
;
151 /* Structure to hold information about the scope forest. */
154 /* Number of trees in forest. */
157 /* List of tree roots. */
161 /* Structure to hold information about the blocks during reordering. */
162 typedef struct reorder_block_def
169 } *reorder_block_def
;
171 #define RBI(BB) ((reorder_block_def) (BB)->aux)
173 /* Holds the interesting trailing notes for the function. */
174 static rtx function_tail_eff_head
;
177 /* Local function prototypes. */
178 static rtx skip_insns_after_block
PARAMS ((basic_block
));
179 static void record_effective_endpoints
PARAMS ((void));
180 static void make_reorder_chain
PARAMS ((void));
181 static basic_block make_reorder_chain_1
PARAMS ((basic_block
, basic_block
));
182 static rtx label_for_bb
PARAMS ((basic_block
));
183 static void fixup_reorder_chain
PARAMS ((void));
184 static void relate_bbs_with_scopes
PARAMS ((scope
));
185 static scope make_new_scope
PARAMS ((int, rtx
));
186 static void build_scope_forest
PARAMS ((scope_forest_info
*));
187 static void remove_scope_notes
PARAMS ((void));
188 static void insert_intra_1
PARAMS ((scope
, rtx
*, basic_block
));
189 static void insert_intra_bb_scope_notes
PARAMS ((basic_block
));
190 static void insert_inter_bb_scope_notes
PARAMS ((basic_block
, basic_block
));
191 static void rebuild_scope_notes
PARAMS ((scope_forest_info
*));
192 static void free_scope_forest_1
PARAMS ((scope
));
193 static void free_scope_forest
PARAMS ((scope_forest_info
*));
194 void dump_scope_forest
PARAMS ((scope_forest_info
*));
195 static void dump_scope_forest_1
PARAMS ((scope
, int));
196 static rtx get_next_bb_note
PARAMS ((rtx
));
197 static rtx get_prev_bb_note
PARAMS ((rtx
));
199 void verify_insn_chain
PARAMS ((void));
201 /* Skip over inter-block insns occurring after BB which are typically
202 associated with BB (e.g., barriers). If there are any such insns,
203 we return the last one. Otherwise, we return the end of BB. */
206 skip_insns_after_block (bb
)
209 rtx insn
, last_insn
, next_head
, prev
;
211 next_head
= NULL_RTX
;
212 if (bb
->index
+ 1 != n_basic_blocks
)
213 next_head
= BASIC_BLOCK (bb
->index
+ 1)->head
;
215 for (last_insn
= insn
= bb
->end
; (insn
= NEXT_INSN (insn
)); )
217 if (insn
== next_head
)
220 switch (GET_CODE (insn
))
227 switch (NOTE_LINE_NUMBER (insn
))
229 case NOTE_INSN_LOOP_END
:
230 case NOTE_INSN_BLOCK_END
:
233 case NOTE_INSN_DELETED
:
234 case NOTE_INSN_DELETED_LABEL
:
245 && GET_CODE (NEXT_INSN (insn
)) == JUMP_INSN
246 && (GET_CODE (PATTERN (NEXT_INSN (insn
))) == ADDR_VEC
247 || GET_CODE (PATTERN (NEXT_INSN (insn
))) == ADDR_DIFF_VEC
))
249 insn
= NEXT_INSN (insn
);
261 /* It is possible to hit contradicting sequence. For instance:
267 Where barrier belongs to jump_insn, but the note does not.
268 This can be created by removing the basic block originally
269 following NOTE_INSN_LOOP_BEG.
271 In such case reorder the notes. */
272 for (insn
= last_insn
; insn
!= bb
->end
; insn
= prev
)
274 prev
= PREV_INSN (insn
);
275 if (GET_CODE (insn
) == NOTE
)
276 switch (NOTE_LINE_NUMBER (insn
))
278 case NOTE_INSN_LOOP_END
:
279 case NOTE_INSN_BLOCK_END
:
280 case NOTE_INSN_DELETED
:
281 case NOTE_INSN_DELETED_LABEL
:
284 reorder_insns (insn
, insn
, last_insn
);
292 /* Locate the effective beginning and end of the insn chain for each
293 block, as defined by skip_insns_after_block above. */
296 record_effective_endpoints ()
298 rtx next_insn
= get_insns ();
301 for (i
= 0; i
< n_basic_blocks
; ++i
)
303 basic_block bb
= BASIC_BLOCK (i
);
306 RBI (bb
)->eff_head
= next_insn
;
307 end
= skip_insns_after_block (bb
);
308 RBI (bb
)->eff_end
= end
;
309 next_insn
= NEXT_INSN (end
);
311 function_tail_eff_head
= next_insn
;
315 /* Compute an ordering for a subgraph beginning with block BB. Record the
316 ordering in RBI()->index and chained through RBI()->next. */
319 make_reorder_chain ()
321 basic_block last_block
= NULL
;
322 basic_block prev
= NULL
;
323 int nbb_m1
= n_basic_blocks
- 1;
326 /* If we've not got epilogue in RTL, we must fallthru to the exit.
327 Force the last block to be at the end. */
328 /* ??? Some ABIs (e.g. MIPS) require the return insn to be at the
329 end of the function for stack unwinding purposes. */
332 last_block
= BASIC_BLOCK (nbb_m1
);
333 RBI (last_block
)->visited
= 1;
337 /* Loop until we've placed every block. */
344 /* Find the next unplaced block. */
345 /* ??? Get rid of this loop, and track which blocks are not yet
346 placed more directly, so as to avoid the O(N^2) worst case.
347 Perhaps keep a doubly-linked list of all to-be-placed blocks;
348 remove from the list as we place. The head of that list is
349 what we're looking for here. */
351 for (i
= 0; i
<= nbb_m1
&& !next
; ++i
)
353 basic_block bb
= BASIC_BLOCK (i
);
354 if (! RBI (bb
)->visited
)
358 prev
= make_reorder_chain_1 (next
, prev
);
362 /* Terminate the chain. */
365 RBI (prev
)->next
= last_block
;
368 RBI (prev
)->next
= NULL
;
371 /* A helper function for make_reorder_chain.
373 We do not follow EH edges, or non-fallthru edges to noreturn blocks.
374 These are assumed to be the error condition and we wish to cluster
375 all of them at the very end of the function for the benefit of cache
376 locality for the rest of the function.
378 ??? We could do slightly better by noticing earlier that some subgraph
379 has all paths leading to noreturn functions, but for there to be more
380 than one block in such a subgraph is rare. */
383 make_reorder_chain_1 (bb
, prev
)
391 /* Mark this block visited. */
395 RBI (prev
)->next
= bb
;
397 if (rtl_dump_file
&& prev
->index
+ 1 != bb
->index
)
398 fprintf (rtl_dump_file
, "Reordering block %d after %d\n",
399 bb
->index
, prev
->index
);
406 RBI (bb
)->visited
= 1;
409 if (bb
->succ
== NULL
)
412 /* Find the most probable block. */
415 if (any_condjump_p (bb
->end
)
416 && (note
= find_reg_note (bb
->end
, REG_BR_PROB
, 0)) != NULL
)
418 int taken
, probability
;
419 edge e_taken
, e_fall
;
421 probability
= INTVAL (XEXP (note
, 0));
422 taken
= probability
> REG_BR_PROB_BASE
/ 2;
424 /* Find the normal taken edge and the normal fallthru edge.
426 Note, conditional jumps with other side effects may not
427 be fully optimized. In this case it is possible for
428 the conditional jump to branch to the same location as
431 We should probably work to improve optimization of that
432 case; however, it seems silly not to also deal with such
433 problems here if they happen to occur. */
435 e_taken
= e_fall
= NULL
;
436 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
438 if (e
->flags
& EDGE_FALLTHRU
)
440 else if (! (e
->flags
& EDGE_EH
))
444 next
= (taken
? e_taken
: e_fall
)->dest
;
447 /* In the absence of a prediction, disturb things as little as possible
448 by selecting the old "next" block from the list of successors. If
449 there had been a fallthru edge, that will be the one. */
452 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
453 if (e
->dest
->index
== bb
->index
+ 1)
455 if ((e
->flags
& EDGE_FALLTHRU
)
457 && ! (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))))
463 /* Make sure we didn't select a silly next block. */
464 if (! next
|| next
== EXIT_BLOCK_PTR
|| RBI (next
)->visited
)
467 /* Recurse on the successors. Unroll the last call, as the normal
468 case is exactly one or two edges, and we can tail recurse. */
469 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
470 if (e
->dest
!= EXIT_BLOCK_PTR
471 && ! RBI (e
->dest
)->visited
473 && ! (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
)))
477 prev
= make_reorder_chain_1 (next
, prev
);
478 next
= RBI (e
->dest
)->visited
? NULL
: e
->dest
;
493 /* Locate or create a label for a given basic block. */
499 rtx label
= bb
->head
;
501 if (GET_CODE (label
) != CODE_LABEL
)
504 fprintf (rtl_dump_file
, "Emitting label for block %d\n",
507 label
= block_label (bb
);
508 if (bb
->head
== PREV_INSN (RBI (bb
)->eff_head
))
509 RBI (bb
)->eff_head
= label
;
516 /* Given a reorder chain, rearrange the code to match. */
519 fixup_reorder_chain ()
521 basic_block bb
, last_bb
;
524 int old_n_basic_blocks
= n_basic_blocks
;
526 /* First do the bulk reordering -- rechain the blocks without regard to
527 the needed changes to jumps and labels. */
529 last_bb
= BASIC_BLOCK (0);
530 bb
= RBI (last_bb
)->next
;
534 rtx last_e
= RBI (last_bb
)->eff_end
;
535 rtx curr_h
= RBI (bb
)->eff_head
;
537 NEXT_INSN (last_e
) = curr_h
;
538 PREV_INSN (curr_h
) = last_e
;
545 if (index
!= n_basic_blocks
)
548 insn
= RBI (last_bb
)->eff_end
;
550 NEXT_INSN (insn
) = function_tail_eff_head
;
551 if (function_tail_eff_head
)
552 PREV_INSN (function_tail_eff_head
) = insn
;
554 while (NEXT_INSN (insn
))
555 insn
= NEXT_INSN (insn
);
556 set_last_insn (insn
);
557 #ifdef ENABLE_CHECKING
558 verify_insn_chain ();
561 /* Now add jumps and labels as needed to match the blocks new
564 for (bb
= BASIC_BLOCK (0); bb
; bb
= RBI (bb
)->next
)
566 edge e_fall
, e_taken
, e
;
570 if (bb
->succ
== NULL
)
573 /* Find the old fallthru edge, and another non-EH edge for
575 e_taken
= e_fall
= NULL
;
576 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
577 if (e
->flags
& EDGE_FALLTHRU
)
579 else if (! (e
->flags
& EDGE_EH
))
582 bb_end_insn
= bb
->end
;
583 if (GET_CODE (bb_end_insn
) == JUMP_INSN
)
585 if (any_condjump_p (bb_end_insn
))
587 /* If the old fallthru is still next, nothing to do. */
588 if (RBI (bb
)->next
== e_fall
->dest
590 && e_fall
->dest
== EXIT_BLOCK_PTR
))
593 /* There is one special case: if *neither* block is next,
594 such as happens at the very end of a function, then we'll
595 need to add a new unconditional jump. Choose the taken
596 edge based on known or assumed probability. */
597 if (RBI (bb
)->next
!= e_taken
->dest
)
599 rtx note
= find_reg_note (bb_end_insn
, REG_BR_PROB
, 0);
601 && INTVAL (XEXP (note
, 0)) < REG_BR_PROB_BASE
/ 2
602 && invert_jump (bb_end_insn
,
603 label_for_bb (e_fall
->dest
), 0))
605 e_fall
->flags
&= ~EDGE_FALLTHRU
;
606 e_taken
->flags
|= EDGE_FALLTHRU
;
607 e
= e_fall
, e_fall
= e_taken
, e_taken
= e
;
611 /* Otherwise we can try to invert the jump. This will
612 basically never fail, however, keep up the pretense. */
613 else if (invert_jump (bb_end_insn
,
614 label_for_bb (e_fall
->dest
), 0))
616 e_fall
->flags
&= ~EDGE_FALLTHRU
;
617 e_taken
->flags
|= EDGE_FALLTHRU
;
621 else if (returnjump_p (bb_end_insn
))
625 /* Otherwise we have some switch or computed jump. In the
626 99% case, there should not have been a fallthru edge. */
629 #ifdef CASE_DROPS_THROUGH
630 /* Except for VAX. Since we didn't have predication for the
631 tablejump, the fallthru block should not have moved. */
632 if (RBI (bb
)->next
== e_fall
->dest
)
634 bb_end_insn
= skip_insns_after_block (bb
);
642 /* No fallthru implies a noreturn function with EH edges, or
643 something similarly bizarre. In any case, we don't need to
648 /* If the fallthru block is still next, nothing to do. */
649 if (RBI (bb
)->next
== e_fall
->dest
)
652 /* An fallthru to exit block. */
653 if (!RBI (bb
)->next
&& e_fall
->dest
== EXIT_BLOCK_PTR
)
657 /* We got here if we need to add a new jump insn. */
659 nb
= force_nonfallthru (e_fall
);
663 nb
->aux
= xmalloc (sizeof (struct reorder_block_def
));
664 RBI (nb
)->eff_head
= nb
->head
;
665 RBI (nb
)->eff_end
= NEXT_INSN (nb
->end
);
666 RBI (nb
)->scope
= RBI (bb
)->scope
;
667 RBI (nb
)->visited
= 1;
668 RBI (nb
)->next
= RBI (bb
)->next
;
670 /* Don't process this new block. */
675 /* Put basic_block_info in the new order. */
676 bb
= BASIC_BLOCK (0);
680 fprintf (rtl_dump_file
, "Reordered sequence:\n");
684 fprintf (rtl_dump_file
, " %i %sbb %i freq %i\n", index
,
685 bb
->index
>= old_n_basic_blocks
? "compensation " : "",
689 BASIC_BLOCK (index
) = bb
;
697 /* Perform sanity checks on the insn chain.
698 1. Check that next/prev pointers are consistent in both the forward and
700 2. Count insns in chain, going both directions, and check if equal.
701 3. Check that get_last_insn () returns the actual end of chain. */
714 for (x
= get_insns (); x
; x
= NEXT_INSN (x
))
716 if (PREV_INSN (x
) != prevx
)
718 fprintf (stderr
, "Forward traversal: insn chain corrupt.\n");
719 fprintf (stderr
, "previous insn:\n");
721 fprintf (stderr
, "current insn:\n");
729 if (prevx
!= get_last_insn ())
731 fprintf (stderr
, "last_insn corrupt.\n");
737 for (x
= get_last_insn (); x
; x
= PREV_INSN (x
))
739 if (NEXT_INSN (x
) != nextx
)
741 fprintf (stderr
, "Reverse traversal: insn chain corrupt.\n");
742 fprintf (stderr
, "current insn:\n");
744 fprintf (stderr
, "next insn:\n");
752 if (insn_cnt1
!= insn_cnt2
)
754 fprintf (stderr
, "insn_cnt1 (%d) not equal to insn_cnt2 (%d).\n",
755 insn_cnt1
, insn_cnt2
);
766 if (NOTE_INSN_BASIC_BLOCK_P (x
))
780 if (NOTE_INSN_BASIC_BLOCK_P (x
))
788 /* Determine and record the relationships between basic blocks and
789 scopes in scope tree S. */
792 relate_bbs_with_scopes (s
)
796 int i
, bbi1
, bbi2
, bbs_spanned
;
799 for (p
= s
->inner
; p
; p
= p
->next
)
800 relate_bbs_with_scopes (p
);
805 /* If the begin and end notes are both inside the same basic block,
806 or if they are both outside of basic blocks, then we know immediately
807 how they are related. Otherwise, we need to poke around to make the
809 if (s
->bb_beg
!= s
->bb_end
)
811 if (s
->bb_beg
&& s
->bb_end
)
813 /* Both notes are in different bbs. This implies that all the
814 basic blocks spanned by the pair of notes are contained in
816 bbi1
= s
->bb_beg
->index
;
817 bbi2
= s
->bb_end
->index
;
820 else if (! s
->bb_beg
)
822 /* First note is outside of a bb. If the scope spans more than
823 one basic block, then they all are contained within this
824 scope. Otherwise, this scope is contained within the basic
826 bbnote
= get_next_bb_note (s
->note_beg
);
829 if (NOTE_BASIC_BLOCK (bbnote
) == s
->bb_end
)
832 s
->bb_beg
= NOTE_BASIC_BLOCK (bbnote
);
836 bbi1
= NOTE_BASIC_BLOCK (bbnote
)->index
;
837 bbi2
= s
->bb_end
->index
;
842 else /* ! s->bb_end */
844 /* Second note is outside of a bb. If the scope spans more than
845 one basic block, then they all are contained within this
846 scope. Otherwise, this scope is contained within the basic
848 bbnote
= get_prev_bb_note (s
->note_end
);
851 if (NOTE_BASIC_BLOCK (bbnote
) == s
->bb_beg
)
854 s
->bb_end
= NOTE_BASIC_BLOCK (bbnote
);
858 bbi1
= s
->bb_beg
->index
;
859 bbi2
= NOTE_BASIC_BLOCK (bbnote
)->index
;
868 /* Both notes are in the same bb, which implies the block
869 contains this scope. */
874 /* Both notes are outside of any bbs. This implies that all the
875 basic blocks spanned by the pair of notes are contained in
877 There is a degenerate case to consider. If the notes do not
878 span any basic blocks, then it is an empty scope that can
879 safely be deleted or ignored. Mark these with level = -1. */
881 x1
= get_next_bb_note (s
->note_beg
);
882 x2
= get_prev_bb_note (s
->note_end
);
890 bbi1
= NOTE_BASIC_BLOCK (x1
)->index
;
891 bbi2
= NOTE_BASIC_BLOCK (x2
)->index
;
897 /* If the scope spans one or more basic blocks, we record them. We
898 only record the bbs that are immediately contained within this
899 scope. Note that if a scope is contained within a bb, we can tell
900 by checking that bb_beg = bb_end and that they are non-null. */
906 for (i
= bbi1
; i
<= bbi2
; i
++)
907 if (! RBI (BASIC_BLOCK (i
))->scope
)
910 s
->bbs
= xmalloc (s
->num_bbs
* sizeof (basic_block
));
911 for (i
= bbi1
; i
<= bbi2
; i
++)
913 basic_block curr_bb
= BASIC_BLOCK (i
);
914 if (! RBI (curr_bb
)->scope
)
916 s
->bbs
[j
++] = curr_bb
;
917 RBI (curr_bb
)->scope
= s
;
926 /* Allocate and initialize a new scope structure with scope level LEVEL,
927 and record the NOTE beginning the scope. */
930 make_new_scope (level
, note
)
934 scope new_scope
= xcalloc (1, sizeof (struct scope_def
));
935 new_scope
->level
= level
;
936 new_scope
->note_beg
= note
;
941 /* Build a forest representing the scope structure of the function.
942 Return a pointer to a structure describing the forest. */
945 build_scope_forest (forest
)
946 scope_forest_info
*forest
;
951 scope root
, curr_scope
= 0;
953 forest
->num_trees
= 0;
954 forest
->trees
= NULL
;
959 for (x
= get_insns (); x
; x
= NEXT_INSN (x
))
961 if (bbi
< n_basic_blocks
&& x
== BASIC_BLOCK (bbi
)->head
)
962 curr_bb
= BASIC_BLOCK (bbi
);
964 if (GET_CODE (x
) == NOTE
)
966 if (NOTE_LINE_NUMBER (x
) == NOTE_INSN_BLOCK_BEG
)
974 new_scope
= make_new_scope (level
, x
);
975 new_scope
->outer
= curr_scope
;
976 new_scope
->next
= NULL
;
977 if (! curr_scope
->inner
)
979 curr_scope
->inner
= new_scope
;
980 curr_scope
->inner_last
= new_scope
;
984 curr_scope
->inner_last
->next
= new_scope
;
985 curr_scope
->inner_last
= new_scope
;
987 curr_scope
= curr_scope
->inner_last
;
991 int ntrees
= forest
->num_trees
;
993 curr_scope
= make_new_scope (level
, x
);
995 forest
->trees
= xrealloc (forest
->trees
,
996 sizeof (scope
) * (ntrees
+ 1));
997 forest
->trees
[forest
->num_trees
++] = root
;
999 curr_scope
->bb_beg
= curr_bb
;
1001 else if (NOTE_LINE_NUMBER (x
) == NOTE_INSN_BLOCK_END
)
1003 curr_scope
->bb_end
= curr_bb
;
1004 curr_scope
->note_end
= x
;
1006 curr_scope
= curr_scope
->outer
;
1012 if (curr_bb
&& curr_bb
->end
== x
)
1020 for (i
= 0; i
< forest
->num_trees
; i
++)
1021 relate_bbs_with_scopes (forest
->trees
[i
]);
1025 /* Remove all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes from
1029 remove_scope_notes ()
1032 basic_block currbb
= NULL
;
1034 for (x
= get_insns (); x
; x
= next
)
1036 next
= NEXT_INSN (x
);
1037 if (NOTE_INSN_BASIC_BLOCK_P (x
))
1038 currbb
= NOTE_BASIC_BLOCK (x
);
1040 if (GET_CODE (x
) == NOTE
1041 && (NOTE_LINE_NUMBER (x
) == NOTE_INSN_BLOCK_BEG
1042 || NOTE_LINE_NUMBER (x
) == NOTE_INSN_BLOCK_END
))
1044 /* Check if the scope note happens to be the end of a bb. */
1045 if (currbb
&& x
== currbb
->end
)
1046 currbb
->end
= PREV_INSN (x
);
1047 if (currbb
&& x
== currbb
->head
)
1052 NEXT_INSN (PREV_INSN (x
)) = next
;
1053 PREV_INSN (next
) = PREV_INSN (x
);
1055 NEXT_INSN (x
) = NULL
;
1056 PREV_INSN (x
) = NULL
;
1065 /* Insert scope note pairs for a contained scope tree S after insn IP. */
1068 insert_intra_1 (s
, ip
, bb
)
1075 if (NOTE_BLOCK (s
->note_beg
))
1077 *ip
= emit_note_after (NOTE_INSN_BLOCK_BEG
, *ip
);
1078 NOTE_BLOCK (*ip
) = NOTE_BLOCK (s
->note_beg
);
1081 for (p
= s
->inner
; p
; p
= p
->next
)
1082 insert_intra_1 (p
, ip
, bb
);
1084 if (NOTE_BLOCK (s
->note_beg
))
1086 *ip
= emit_note_after (NOTE_INSN_BLOCK_END
, *ip
);
1087 NOTE_BLOCK (*ip
) = NOTE_BLOCK (s
->note_end
);
1092 /* Insert NOTE_INSN_BLOCK_END notes and NOTE_INSN_BLOCK_BEG notes for
1093 scopes that are contained within BB. */
1096 insert_intra_bb_scope_notes (bb
)
1099 scope s
= RBI (bb
)->scope
;
1107 if (GET_CODE (ip
) == CODE_LABEL
)
1108 ip
= NEXT_INSN (ip
);
1110 for (p
= s
->inner
; p
; p
= p
->next
)
1112 if (p
->bb_beg
!= NULL
&& p
->bb_beg
== p
->bb_end
&& p
->bb_beg
== bb
)
1113 insert_intra_1 (p
, &ip
, bb
);
1118 /* Given two consecutive basic blocks BB1 and BB2 with different scopes,
1119 insert NOTE_INSN_BLOCK_END notes after BB1 and NOTE_INSN_BLOCK_BEG
1120 notes before BB2 such that the notes are correctly balanced. If BB1 or
1121 BB2 is NULL, we are inserting scope notes for the first and last basic
1122 blocks, respectively. */
1125 insert_inter_bb_scope_notes (bb1
, bb2
)
1132 /* It is possible that a basic block is not contained in any scope.
1133 In that case, we either open or close a scope but not both. */
1136 scope s1
= RBI (bb1
)->scope
;
1137 scope s2
= RBI (bb2
)->scope
;
1146 /* Find common ancestor scope. */
1149 scope s1
= RBI (bb1
)->scope
;
1150 scope s2
= RBI (bb2
)->scope
;
1155 if (s1
->level
> s2
->level
)
1157 else if (s2
->level
> s1
->level
)
1175 scope s
= RBI (bb1
)->scope
;
1176 ip
= RBI (bb1
)->eff_end
;
1179 if (NOTE_BLOCK (s
->note_beg
))
1181 ip
= emit_note_after (NOTE_INSN_BLOCK_END
, ip
);
1182 NOTE_BLOCK (ip
) = NOTE_BLOCK (s
->note_end
);
1186 /* Emitting note may move the end of basic block to unwanted place. */
1193 scope s
= RBI (bb2
)->scope
;
1197 if (NOTE_BLOCK (s
->note_beg
))
1199 ip
= emit_note_before (NOTE_INSN_BLOCK_BEG
, ip
);
1200 NOTE_BLOCK (ip
) = NOTE_BLOCK (s
->note_beg
);
1208 /* Rebuild all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes based
1209 on the scope forest and the newly reordered basic blocks. */
1212 rebuild_scope_notes (forest
)
1213 scope_forest_info
*forest
;
1217 if (forest
->num_trees
== 0)
1220 /* Start by opening the scopes before the first basic block. */
1221 insert_inter_bb_scope_notes (NULL
, BASIC_BLOCK (0));
1223 /* Then, open and close scopes as needed between blocks. */
1224 for (i
= 0; i
< n_basic_blocks
- 1; i
++)
1226 basic_block bb1
= BASIC_BLOCK (i
);
1227 basic_block bb2
= BASIC_BLOCK (i
+ 1);
1228 if (RBI (bb1
)->scope
!= RBI (bb2
)->scope
)
1229 insert_inter_bb_scope_notes (bb1
, bb2
);
1230 insert_intra_bb_scope_notes (bb1
);
1233 /* Finally, close the scopes after the last basic block. */
1234 insert_inter_bb_scope_notes (BASIC_BLOCK (n_basic_blocks
- 1), NULL
);
1235 insert_intra_bb_scope_notes (BASIC_BLOCK (n_basic_blocks
- 1));
1239 /* Free the storage associated with the scope tree at S. */
1242 free_scope_forest_1 (s
)
1247 for (p
= s
->inner
; p
; p
= next
)
1250 free_scope_forest_1 (p
);
1259 /* Free the storage associated with the scope forest. */
1262 free_scope_forest (forest
)
1263 scope_forest_info
*forest
;
1266 for (i
= 0; i
< forest
->num_trees
; i
++)
1267 free_scope_forest_1 (forest
->trees
[i
]);
1271 /* Visualize the scope forest. */
1274 dump_scope_forest (forest
)
1275 scope_forest_info
*forest
;
1277 if (forest
->num_trees
== 0)
1278 fprintf (stderr
, "\n< Empty scope forest >\n");
1282 fprintf (stderr
, "\n< Scope forest >\n");
1283 for (i
= 0; i
< forest
->num_trees
; i
++)
1284 dump_scope_forest_1 (forest
->trees
[i
], 0);
1289 /* Recursive portion of dump_scope_forest. */
1292 dump_scope_forest_1 (s
, indent
)
1299 if (s
->bb_beg
!= NULL
&& s
->bb_beg
== s
->bb_end
1300 && RBI (s
->bb_beg
)->scope
1301 && RBI (s
->bb_beg
)->scope
->level
+ 1 == s
->level
)
1303 fprintf (stderr
, "%*s", indent
, "");
1304 fprintf (stderr
, "BB%d:\n", s
->bb_beg
->index
);
1307 fprintf (stderr
, "%*s", indent
, "");
1308 fprintf (stderr
, "{ level %d (block %p)\n", s
->level
,
1309 (PTR
) NOTE_BLOCK (s
->note_beg
));
1311 fprintf (stderr
, "%*s%s", indent
, "", "bbs:");
1312 for (i
= 0; i
< s
->num_bbs
; i
++)
1313 fprintf (stderr
, " %d", s
->bbs
[i
]->index
);
1314 fprintf (stderr
, "\n");
1316 for (p
= s
->inner
; p
; p
= p
->next
)
1317 dump_scope_forest_1 (p
, indent
+ 2);
1319 fprintf (stderr
, "%*s", indent
, "");
1320 fprintf (stderr
, "}\n");
1324 /* Reorder basic blocks. The main entry point to this file. */
1327 reorder_basic_blocks ()
1329 scope_forest_info forest
;
1332 if (n_basic_blocks
<= 1)
1335 for (i
= 0; i
< n_basic_blocks
; i
++)
1336 BASIC_BLOCK (i
)->aux
= xcalloc (1, sizeof (struct reorder_block_def
));
1338 EXIT_BLOCK_PTR
->aux
= xcalloc (1, sizeof (struct reorder_block_def
));
1340 build_scope_forest (&forest
);
1341 remove_scope_notes ();
1343 record_effective_endpoints ();
1344 make_reorder_chain ();
1347 dump_flow_info (rtl_dump_file
);
1349 fixup_reorder_chain ();
1351 #ifdef ENABLE_CHECKING
1352 verify_insn_chain ();
1355 rebuild_scope_notes (&forest
);
1356 free_scope_forest (&forest
);
1359 for (i
= 0; i
< n_basic_blocks
; i
++)
1360 free (BASIC_BLOCK (i
)->aux
);
1362 free (EXIT_BLOCK_PTR
->aux
);
1364 #ifdef ENABLE_CHECKING
1365 verify_flow_info ();