1 /* Basic block reordering routines for the GNU compiler.
2 Copyright (C) 2000 Free Software Foundation, Inc.
4 This file is part of GNU CC.
6 GNU CC is free software; you can redistribute it and/or modify
7 it 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 GNU CC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU CC; see the file COPYING. If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
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"
98 #include "insn-flags.h"
103 #ifndef HAVE_epilogue
104 #define HAVE_epilogue 0
108 /* The contents of the current function definition are allocated
109 in this obstack, and all are freed at the end of the function.
110 For top-level functions, this is temporary_obstack.
111 Separate obstacks are made for nested functions. */
113 extern struct obstack
*function_obstack
;
116 /* Structure to hold information about lexical scopes. */
117 typedef struct scope_def
121 /* The NOTE_INSN_BLOCK_BEG that started this scope. */
124 /* The NOTE_INSN_BLOCK_END that ended this scope. */
127 /* The bb containing note_beg (if any). */
130 /* The bb containing note_end (if any). */
133 /* List of basic blocks contained within this scope. */
136 /* Number of blocks contained within this scope. */
139 /* The outer scope or NULL if outermost scope. */
140 struct scope_def
*outer
;
142 /* The first inner scope or NULL if innermost scope. */
143 struct scope_def
*inner
;
145 /* The last inner scope or NULL if innermost scope. */
146 struct scope_def
*inner_last
;
148 /* Link to the next (sibling) scope. */
149 struct scope_def
*next
;
153 /* Structure to hold information about the scope forest. */
156 /* Number of trees in forest. */
159 /* List of tree roots. */
163 /* Structure to hold information about the blocks during reordering. */
164 typedef struct reorder_block_def
172 } *reorder_block_def
;
174 #define RBI(BB) ((reorder_block_def) (BB)->aux)
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 rtx emit_jump_to_block_after
PARAMS ((basic_block
, rtx
));
184 static void fixup_reorder_chain
PARAMS ((void));
185 static void relate_bbs_with_scopes
PARAMS ((scope
));
186 static scope make_new_scope
PARAMS ((int, rtx
));
187 static void build_scope_forest
PARAMS ((scope_forest_info
*));
188 static void remove_scope_notes
PARAMS ((void));
189 static void insert_intra_1
PARAMS ((scope
, rtx
*));
190 static void insert_intra_bb_scope_notes
PARAMS ((basic_block
));
191 static void insert_inter_bb_scope_notes
PARAMS ((basic_block
, basic_block
));
192 static void rebuild_scope_notes
PARAMS ((scope_forest_info
*));
193 static void free_scope_forest_1
PARAMS ((scope
));
194 static void free_scope_forest
PARAMS ((scope_forest_info
*));
195 void dump_scope_forest
PARAMS ((scope_forest_info
*));
196 static void dump_scope_forest_1
PARAMS ((scope
, int));
197 static rtx get_next_bb_note
PARAMS ((rtx
));
198 static rtx get_prev_bb_note
PARAMS ((rtx
));
200 void verify_insn_chain
PARAMS ((void));
202 /* Skip over inter-block insns occurring after BB which are typically
203 associated with BB (e.g., barriers). If there are any such insns,
204 we return the last one. Otherwise, we return the end of BB. */
207 skip_insns_after_block (bb
)
210 rtx insn
, last_insn
, next_head
;
212 next_head
= NULL_RTX
;
213 if (bb
->index
+ 1 != n_basic_blocks
)
214 next_head
= BASIC_BLOCK (bb
->index
+ 1)->head
;
216 for (last_insn
= bb
->end
; (insn
= NEXT_INSN (last_insn
)); last_insn
= insn
)
218 if (insn
== next_head
)
221 switch (GET_CODE (insn
))
227 switch (NOTE_LINE_NUMBER (insn
))
229 case NOTE_INSN_LOOP_END
:
230 case NOTE_INSN_BLOCK_END
:
231 case NOTE_INSN_DELETED
:
232 case NOTE_INSN_DELETED_LABEL
:
242 && GET_CODE (NEXT_INSN (insn
)) == JUMP_INSN
243 && (GET_CODE (PATTERN (NEXT_INSN (insn
))) == ADDR_VEC
244 || GET_CODE (PATTERN (NEXT_INSN (insn
))) == ADDR_DIFF_VEC
))
246 insn
= NEXT_INSN (insn
);
262 /* Locate the effective beginning and end of the insn chain for each
263 block, as defined by skip_insns_after_block above. */
266 record_effective_endpoints ()
268 rtx next_insn
= get_insns ();
271 for (i
= 0; i
< n_basic_blocks
; ++i
)
273 basic_block bb
= BASIC_BLOCK (i
);
276 RBI (bb
)->eff_head
= next_insn
;
277 end
= skip_insns_after_block (bb
);
278 RBI (bb
)->eff_end
= end
;
279 next_insn
= NEXT_INSN (end
);
284 /* Compute an ordering for a subgraph beginning with block BB. Record the
285 ordering in RBI()->index and chained through RBI()->next. */
288 make_reorder_chain ()
290 basic_block last_block
= NULL
;
291 basic_block prev
= NULL
;
292 int nbb_m1
= n_basic_blocks
- 1;
294 /* If we've not got epilogue in RTL, we must fallthru to the exit.
295 Force the last block to be at the end. */
296 /* ??? Some ABIs (e.g. MIPS) require the return insn to be at the
297 end of the function for stack unwinding purposes. */
300 last_block
= BASIC_BLOCK (nbb_m1
);
301 RBI (last_block
)->visited
= 1;
305 /* Loop until we've placed every block. */
309 basic_block next
= NULL
;
311 /* Find the next unplaced block. */
312 /* ??? Get rid of this loop, and track which blocks are not yet
313 placed more directly, so as to avoid the O(N^2) worst case.
314 Perhaps keep a doubly-linked list of all to-be-placed blocks;
315 remove from the list as we place. The head of that list is
316 what we're looking for here. */
318 for (i
= 0; i
<= nbb_m1
; ++i
)
320 basic_block bb
= BASIC_BLOCK (i
);
321 if (! RBI (bb
)->visited
)
330 prev
= make_reorder_chain_1 (next
, prev
);
332 while (RBI (prev
)->index
< nbb_m1
);
334 /* Terminate the chain. */
337 RBI (prev
)->next
= last_block
;
338 RBI (last_block
)->index
= RBI (prev
)->index
+ 1;
341 RBI (prev
)->next
= NULL
;
344 /* A helper function for make_reorder_chain.
346 We do not follow EH edges, or non-fallthru edges to noreturn blocks.
347 These are assumed to be the error condition and we wish to cluster
348 all of them at the very end of the function for the benefit of cache
349 locality for the rest of the function.
351 ??? We could do slightly better by noticing earlier that some subgraph
352 has all paths leading to noreturn functions, but for there to be more
353 than one block in such a subgraph is rare. */
356 make_reorder_chain_1 (bb
, prev
)
364 /* Mark this block visited. */
370 RBI (prev
)->next
= bb
;
371 new_index
= RBI (prev
)->index
+ 1;
372 RBI (bb
)->index
= new_index
;
374 if (rtl_dump_file
&& prev
->index
+ 1 != bb
->index
)
375 fprintf (rtl_dump_file
, "Reordering block %d (%d) after %d (%d)\n",
376 bb
->index
, RBI (bb
)->index
, prev
->index
, RBI (prev
)->index
);
380 RBI (bb
)->visited
= 1;
383 if (bb
->succ
== NULL
)
386 /* Find the most probable block. */
389 if (any_condjump_p (bb
->end
)
390 && (note
= find_reg_note (bb
->end
, REG_BR_PROB
, 0)) != NULL
)
392 int taken
, probability
;
393 edge e_taken
, e_fall
;
395 probability
= INTVAL (XEXP (note
, 0));
396 taken
= probability
> REG_BR_PROB_BASE
/ 2;
398 /* Find the normal taken edge and the normal fallthru edge.
399 Note that there may in fact be other edges due to
400 asynchronous_exceptions. */
402 e_taken
= e_fall
= NULL
;
403 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
404 if (e
->flags
& EDGE_FALLTHRU
)
406 else if (! (e
->flags
& EDGE_EH
))
409 next
= (taken
? e_taken
: e_fall
)->dest
;
412 /* In the absence of a prediction, disturb things as little as possible
413 by selecting the old "next" block from the list of successors. If
414 there had been a fallthru edge, that will be the one. */
417 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
418 if (e
->dest
->index
== bb
->index
+ 1)
420 if ((e
->flags
& EDGE_FALLTHRU
)
422 && ! (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))))
428 /* Make sure we didn't select a silly next block. */
429 if (! next
|| next
== EXIT_BLOCK_PTR
|| RBI (next
)->visited
)
432 /* Recurse on the successors. Unroll the last call, as the normal
433 case is exactly one or two edges, and we can tail recurse. */
434 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
435 if (e
->dest
!= EXIT_BLOCK_PTR
436 && ! RBI (e
->dest
)->visited
438 && ! (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
)))
442 prev
= make_reorder_chain_1 (next
, prev
);
443 next
= RBI (e
->dest
)->visited
? NULL
: e
->dest
;
458 /* Locate or create a label for a given basic block. */
464 rtx label
= bb
->head
;
466 if (GET_CODE (label
) != CODE_LABEL
)
469 fprintf (rtl_dump_file
, "Emitting label for block %d (%d)\n",
470 bb
->index
, RBI (bb
)->index
);
472 label
= emit_label_before (gen_label_rtx (), label
);
473 if (bb
->head
== RBI (bb
)->eff_head
)
474 RBI (bb
)->eff_head
= label
;
482 /* Emit a jump to BB after insn AFTER. */
485 emit_jump_to_block_after (bb
, after
)
491 if (bb
!= EXIT_BLOCK_PTR
)
493 rtx label
= label_for_bb (bb
);
494 jump
= emit_jump_insn_after (gen_jump (label
), after
);
495 JUMP_LABEL (jump
) = label
;
496 LABEL_NUSES (label
) += 1;
499 fprintf (rtl_dump_file
, "Emitting jump to block %d (%d)\n",
500 bb
->index
, RBI (bb
)->index
);
507 jump
= emit_jump_insn_after (gen_return (), after
);
510 fprintf (rtl_dump_file
, "Emitting return\n");
520 /* Given a reorder chain, rearrange the code to match. */
523 fixup_reorder_chain ()
525 basic_block bb
, last_bb
;
527 /* First do the bulk reordering -- rechain the blocks without regard to
528 the needed changes to jumps and labels. */
530 last_bb
= BASIC_BLOCK (0);
531 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
;
543 NEXT_INSN (RBI (last_bb
)->eff_end
) = NULL_RTX
;
544 set_last_insn (RBI (last_bb
)->eff_end
);
546 /* Now add jumps and labels as needed to match the blocks new
549 for (bb
= BASIC_BLOCK (0); bb
; bb
= RBI (bb
)->next
)
551 edge e_fall
, e_taken
, e
;
552 rtx jump_insn
, barrier_insn
, bb_end_insn
;
555 if (bb
->succ
== NULL
)
558 /* Find the old fallthru edge, and another non-EH edge for
560 e_taken
= e_fall
= NULL
;
561 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
562 if (e
->flags
& EDGE_FALLTHRU
)
564 else if (! (e
->flags
& EDGE_EH
))
567 bb_end_insn
= bb
->end
;
568 if (GET_CODE (bb_end_insn
) == JUMP_INSN
)
570 if (any_uncondjump_p (bb_end_insn
))
572 /* If the destination is still not next, nothing to do. */
573 if (RBI (bb
)->index
+ 1 != RBI (e_taken
->dest
)->index
)
576 /* Otherwise, we can remove the jump and cleanup the edge. */
577 tidy_fallthru_edge (e_taken
, bb
, e_taken
->dest
);
578 RBI (bb
)->eff_end
= skip_insns_after_block (bb
);
579 RBI (e_taken
->dest
)->eff_head
= NEXT_INSN (RBI (bb
)->eff_end
);
582 fprintf (rtl_dump_file
, "Removing jump in block %d (%d)\n",
583 bb
->index
, RBI (bb
)->index
);
586 else if (any_condjump_p (bb_end_insn
))
588 /* If the old fallthru is still next, nothing to do. */
589 if (RBI (bb
)->index
+ 1 == RBI (e_fall
->dest
)->index
590 || (RBI (bb
)->index
== n_basic_blocks
- 1
591 && e_fall
->dest
== EXIT_BLOCK_PTR
))
594 /* There is one special case: if *neither* block is next,
595 such as happens at the very end of a function, then we'll
596 need to add a new unconditional jump. Choose the taken
597 edge based on known or assumed probability. */
598 if (RBI (bb
)->index
+ 1 != RBI (e_taken
->dest
)->index
)
600 rtx note
= find_reg_note (bb_end_insn
, REG_BR_PROB
, 0);
602 && INTVAL (XEXP (note
, 0)) < REG_BR_PROB_BASE
/ 2
603 && invert_jump (bb_end_insn
,
604 label_for_bb (e_fall
->dest
), 0))
606 e_fall
->flags
&= ~EDGE_FALLTHRU
;
607 e_taken
->flags
|= EDGE_FALLTHRU
;
608 e
= e_fall
, e_fall
= e_taken
, e_taken
= e
;
612 /* Otherwise we can try to invert the jump. This will
613 basically never fail, however, keep up the pretense. */
614 else if (invert_jump (bb_end_insn
,
615 label_for_bb (e_fall
->dest
), 0))
617 e_fall
->flags
&= ~EDGE_FALLTHRU
;
618 e_taken
->flags
|= EDGE_FALLTHRU
;
622 else if (returnjump_p (bb_end_insn
))
626 /* Otherwise we have some switch or computed jump. In the
627 99% case, there should not have been a fallthru edge. */
630 #ifdef CASE_DROPS_THROUGH
631 /* Except for VAX. Since we didn't have predication for the
632 tablejump, the fallthru block should not have moved. */
633 if (RBI (bb
)->index
+ 1 == RBI (e_fall
->dest
)->index
)
635 bb_end_insn
= skip_insns_after_block (bb
);
643 /* No fallthru implies a noreturn function with EH edges, or
644 something similarly bizarre. In any case, we don't need to
649 /* If the fallthru block is still next, nothing to do. */
650 if (RBI (bb
)->index
+ 1 == RBI (e_fall
->dest
)->index
651 || (RBI (bb
)->index
== n_basic_blocks
- 1
652 && e_fall
->dest
== EXIT_BLOCK_PTR
))
655 /* We need a new jump insn. If the block has only one outgoing
656 edge, then we can stuff the new jump insn in directly. */
657 if (bb
->succ
->succ_next
== NULL
)
659 e_fall
->flags
&= ~EDGE_FALLTHRU
;
661 jump_insn
= emit_jump_to_block_after (e_fall
->dest
, bb_end_insn
);
663 barrier_insn
= emit_barrier_after (jump_insn
);
664 RBI (bb
)->eff_end
= barrier_insn
;
669 /* We got here if we need to add a new jump insn in a new block
670 across the edge e_fall. */
672 jump_insn
= emit_jump_to_block_after (e_fall
->dest
, bb_end_insn
);
673 barrier_insn
= emit_barrier_after (jump_insn
);
675 VARRAY_GROW (basic_block_info
, ++n_basic_blocks
);
676 create_basic_block (n_basic_blocks
- 1, jump_insn
, jump_insn
, NULL
);
678 nb
= BASIC_BLOCK (n_basic_blocks
- 1);
679 nb
->global_live_at_start
= OBSTACK_ALLOC_REG_SET (function_obstack
);
680 nb
->global_live_at_end
= OBSTACK_ALLOC_REG_SET (function_obstack
);
683 COPY_REG_SET (nb
->global_live_at_start
, bb
->global_live_at_start
);
684 COPY_REG_SET (nb
->global_live_at_end
, bb
->global_live_at_start
);
686 nb
->aux
= xmalloc (sizeof (struct reorder_block_def
));
687 RBI (nb
)->eff_head
= nb
->head
;
688 RBI (nb
)->eff_end
= barrier_insn
;
689 RBI (nb
)->scope
= RBI (bb
)->scope
;
690 RBI (nb
)->index
= RBI (bb
)->index
+ 1;
691 RBI (nb
)->visited
= 1;
692 RBI (nb
)->next
= RBI (bb
)->next
;
695 /* Link to new block. */
696 make_edge (NULL
, nb
, e_fall
->dest
, 0);
697 redirect_edge_succ (e_fall
, nb
);
699 /* Don't process this new block. */
702 /* Fix subsequent reorder block indices to reflect new block. */
703 while ((nb
= RBI (nb
)->next
) != NULL
)
704 RBI (nb
)->index
+= 1;
707 /* Put basic_block_info in the new order. */
708 for (bb
= BASIC_BLOCK (0); bb
; bb
= RBI (bb
)->next
)
710 bb
->index
= RBI (bb
)->index
;
711 BASIC_BLOCK (bb
->index
) = bb
;
716 /* Perform sanity checks on the insn chain.
717 1. Check that next/prev pointers are consistent in both the forward and
719 2. Count insns in chain, going both directions, and check if equal.
720 3. Check that get_last_insn () returns the actual end of chain. */
733 for (x
= get_insns (); x
; x
= NEXT_INSN (x
))
735 if (PREV_INSN (x
) != prevx
)
737 fprintf (stderr
, "Forward traversal: insn chain corrupt.\n");
738 fprintf (stderr
, "previous insn:\n");
740 fprintf (stderr
, "current insn:\n");
748 if (prevx
!= get_last_insn ())
750 fprintf (stderr
, "last_insn corrupt.\n");
756 for (x
= get_last_insn (); x
; x
= PREV_INSN (x
))
758 if (NEXT_INSN (x
) != nextx
)
760 fprintf (stderr
, "Reverse traversal: insn chain corrupt.\n");
761 fprintf (stderr
, "current insn:\n");
763 fprintf (stderr
, "next insn:\n");
771 if (insn_cnt1
!= insn_cnt2
)
773 fprintf (stderr
, "insn_cnt1 (%d) not equal to insn_cnt2 (%d).\n",
774 insn_cnt1
, insn_cnt2
);
785 if (NOTE_INSN_BASIC_BLOCK_P (x
))
799 if (NOTE_INSN_BASIC_BLOCK_P (x
))
807 /* Determine and record the relationships between basic blocks and
808 scopes in scope tree S. */
811 relate_bbs_with_scopes (s
)
815 int i
, bbi1
, bbi2
, bbs_spanned
;
818 for (p
= s
->inner
; p
; p
= p
->next
)
819 relate_bbs_with_scopes (p
);
824 /* If the begin and end notes are both inside the same basic block,
825 or if they are both outside of basic blocks, then we know immediately
826 how they are related. Otherwise, we need to poke around to make the
828 if (s
->bb_beg
!= s
->bb_end
)
830 if (s
->bb_beg
&& s
->bb_end
)
832 /* Both notes are in different bbs. This implies that all the
833 basic blocks spanned by the pair of notes are contained in
835 bbi1
= s
->bb_beg
->index
;
836 bbi2
= s
->bb_end
->index
;
839 else if (! s
->bb_beg
)
841 /* First note is outside of a bb. If the scope spans more than
842 one basic block, then they all are contained within this
843 scope. Otherwise, this scope is contained within the basic
845 bbnote
= get_next_bb_note (s
->note_beg
);
848 if (NOTE_BASIC_BLOCK (bbnote
) == s
->bb_end
)
851 s
->bb_beg
= NOTE_BASIC_BLOCK (bbnote
);
855 bbi1
= NOTE_BASIC_BLOCK (bbnote
)->index
;
856 bbi2
= s
->bb_end
->index
;
861 else /* ! s->bb_end */
863 /* Second note is outside of a bb. If the scope spans more than
864 one basic block, then they all are contained within this
865 scope. Otherwise, this scope is contained within the basic
867 bbnote
= get_prev_bb_note (s
->note_end
);
870 if (NOTE_BASIC_BLOCK (bbnote
) == s
->bb_beg
)
873 s
->bb_end
= NOTE_BASIC_BLOCK (bbnote
);
877 bbi1
= s
->bb_beg
->index
;
878 bbi2
= NOTE_BASIC_BLOCK (bbnote
)->index
;
887 /* Both notes are in the same bb, which implies the block
888 contains this scope. */
893 /* Both notes are outside of any bbs. This implies that all the
894 basic blocks spanned by the pair of notes are contained in
896 There is a degenerate case to consider. If the notes do not
897 span any basic blocks, then it is an empty scope that can
898 safely be deleted or ignored. Mark these with level = -1. */
900 x1
= get_next_bb_note (s
->note_beg
);
901 x2
= get_prev_bb_note (s
->note_end
);
909 bbi1
= NOTE_BASIC_BLOCK (x1
)->index
;
910 bbi2
= NOTE_BASIC_BLOCK (x2
)->index
;
916 /* If the scope spans one or more basic blocks, we record them. We
917 only record the bbs that are immediately contained within this
918 scope. Note that if a scope is contained within a bb, we can tell
919 by checking that bb_beg = bb_end and that they are non-null. */
925 for (i
= bbi1
; i
<= bbi2
; i
++)
926 if (! RBI (BASIC_BLOCK (i
))->scope
)
929 s
->bbs
= xmalloc (s
->num_bbs
* sizeof (basic_block
));
930 for (i
= bbi1
; i
<= bbi2
; i
++)
932 basic_block curr_bb
= BASIC_BLOCK (i
);
933 if (! RBI (curr_bb
)->scope
)
935 s
->bbs
[j
++] = curr_bb
;
936 RBI (curr_bb
)->scope
= s
;
945 /* Allocate and initialize a new scope structure with scope level LEVEL,
946 and record the NOTE beginning the scope. */
949 make_new_scope (level
, note
)
953 scope new_scope
= xcalloc (1, sizeof (struct scope_def
));
954 new_scope
->level
= level
;
955 new_scope
->note_beg
= note
;
960 /* Build a forest representing the scope structure of the function.
961 Return a pointer to a structure describing the forest. */
964 build_scope_forest (forest
)
965 scope_forest_info
*forest
;
970 scope root
, curr_scope
= 0;
972 forest
->num_trees
= 0;
973 forest
->trees
= NULL
;
978 for (x
= get_insns (); x
; x
= NEXT_INSN (x
))
980 if (bbi
< n_basic_blocks
&& x
== BASIC_BLOCK (bbi
)->head
)
981 curr_bb
= BASIC_BLOCK (bbi
);
983 if (GET_CODE (x
) == NOTE
)
985 if (NOTE_LINE_NUMBER (x
) == NOTE_INSN_BLOCK_BEG
)
993 new_scope
= make_new_scope (level
, x
);
994 new_scope
->outer
= curr_scope
;
995 new_scope
->next
= NULL
;
996 if (! curr_scope
->inner
)
998 curr_scope
->inner
= new_scope
;
999 curr_scope
->inner_last
= new_scope
;
1003 curr_scope
->inner_last
->next
= new_scope
;
1004 curr_scope
->inner_last
= new_scope
;
1006 curr_scope
= curr_scope
->inner_last
;
1010 int ntrees
= forest
->num_trees
;
1012 curr_scope
= make_new_scope (level
, x
);
1014 forest
->trees
= xrealloc (forest
->trees
,
1015 sizeof (scope
) * (ntrees
+ 1));
1016 forest
->trees
[forest
->num_trees
++] = root
;
1018 curr_scope
->bb_beg
= curr_bb
;
1020 else if (NOTE_LINE_NUMBER (x
) == NOTE_INSN_BLOCK_END
)
1022 curr_scope
->bb_end
= curr_bb
;
1023 curr_scope
->note_end
= x
;
1025 curr_scope
= curr_scope
->outer
;
1031 if (curr_bb
&& curr_bb
->end
== x
)
1039 for (i
= 0; i
< forest
->num_trees
; i
++)
1040 relate_bbs_with_scopes (forest
->trees
[i
]);
1044 /* Remove all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes from
1048 remove_scope_notes ()
1051 basic_block currbb
= NULL
;
1053 for (x
= get_insns (); x
; x
= next
)
1055 next
= NEXT_INSN (x
);
1056 if (NOTE_INSN_BASIC_BLOCK_P (x
))
1057 currbb
= NOTE_BASIC_BLOCK (x
);
1059 if (GET_CODE (x
) == NOTE
1060 && (NOTE_LINE_NUMBER (x
) == NOTE_INSN_BLOCK_BEG
1061 || NOTE_LINE_NUMBER (x
) == NOTE_INSN_BLOCK_END
))
1063 /* Check if the scope note happens to be the end of a bb. */
1064 if (currbb
&& x
== currbb
->end
)
1065 currbb
->end
= PREV_INSN (x
);
1066 if (currbb
&& x
== currbb
->head
)
1071 NEXT_INSN (PREV_INSN (x
)) = next
;
1072 PREV_INSN (next
) = PREV_INSN (x
);
1074 NEXT_INSN (x
) = NULL
;
1075 PREV_INSN (x
) = NULL
;
1084 /* Insert scope note pairs for a contained scope tree S after insn IP. */
1087 insert_intra_1 (s
, ip
)
1093 if (NOTE_BLOCK (s
->note_beg
))
1095 *ip
= emit_note_after (NOTE_INSN_BLOCK_BEG
, *ip
);
1096 NOTE_BLOCK (*ip
) = NOTE_BLOCK (s
->note_beg
);
1099 for (p
= s
->inner
; p
; p
= p
->next
)
1100 insert_intra_1 (p
, ip
);
1102 if (NOTE_BLOCK (s
->note_beg
))
1104 *ip
= emit_note_after (NOTE_INSN_BLOCK_END
, *ip
);
1105 NOTE_BLOCK (*ip
) = NOTE_BLOCK (s
->note_end
);
1110 /* Insert NOTE_INSN_BLOCK_END notes and NOTE_INSN_BLOCK_BEG notes for
1111 scopes that are contained within BB. */
1114 insert_intra_bb_scope_notes (bb
)
1117 scope s
= RBI (bb
)->scope
;
1125 if (GET_CODE (ip
) == CODE_LABEL
)
1126 ip
= NEXT_INSN (ip
);
1128 for (p
= s
->inner
; p
; p
= p
->next
)
1130 if (p
->bb_beg
!= NULL
&& p
->bb_beg
== p
->bb_end
&& p
->bb_beg
== bb
)
1131 insert_intra_1 (p
, &ip
);
1136 /* Given two consecutive basic blocks BB1 and BB2 with different scopes,
1137 insert NOTE_INSN_BLOCK_END notes after BB1 and NOTE_INSN_BLOCK_BEG
1138 notes before BB2 such that the notes are correctly balanced. If BB1 or
1139 BB2 is NULL, we are inserting scope notes for the first and last basic
1140 blocks, respectively. */
1143 insert_inter_bb_scope_notes (bb1
, bb2
)
1150 /* It is possible that a basic block is not contained in any scope.
1151 In that case, we either open or close a scope but not both. */
1154 scope s1
= RBI (bb1
)->scope
;
1155 scope s2
= RBI (bb2
)->scope
;
1164 /* Find common ancestor scope. */
1167 scope s1
= RBI (bb1
)->scope
;
1168 scope s2
= RBI (bb2
)->scope
;
1173 if (s1
->level
> s2
->level
)
1175 else if (s2
->level
> s1
->level
)
1191 scope s
= RBI (bb1
)->scope
;
1192 ip
= RBI (bb1
)->eff_end
;
1195 if (NOTE_BLOCK (s
->note_beg
))
1197 ip
= emit_note_after (NOTE_INSN_BLOCK_END
, ip
);
1198 NOTE_BLOCK (ip
) = NOTE_BLOCK (s
->note_end
);
1207 scope s
= RBI (bb2
)->scope
;
1211 if (NOTE_BLOCK (s
->note_beg
))
1213 ip
= emit_note_before (NOTE_INSN_BLOCK_BEG
, ip
);
1214 NOTE_BLOCK (ip
) = NOTE_BLOCK (s
->note_beg
);
1222 /* Rebuild all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes based
1223 on the scope forest and the newly reordered basic blocks. */
1226 rebuild_scope_notes (forest
)
1227 scope_forest_info
*forest
;
1231 if (forest
->num_trees
== 0)
1234 /* Start by opening the scopes before the first basic block. */
1235 insert_inter_bb_scope_notes (NULL
, BASIC_BLOCK (0));
1237 /* Then, open and close scopes as needed between blocks. */
1238 for (i
= 0; i
< n_basic_blocks
- 1; i
++)
1240 basic_block bb1
= BASIC_BLOCK (i
);
1241 basic_block bb2
= BASIC_BLOCK (i
+ 1);
1242 if (RBI (bb1
)->scope
!= RBI (bb2
)->scope
)
1243 insert_inter_bb_scope_notes (bb1
, bb2
);
1244 insert_intra_bb_scope_notes (bb1
);
1247 /* Finally, close the scopes after the last basic block. */
1248 insert_inter_bb_scope_notes (BASIC_BLOCK (n_basic_blocks
- 1), NULL
);
1249 insert_intra_bb_scope_notes (BASIC_BLOCK (n_basic_blocks
- 1));
1253 /* Free the storage associated with the scope tree at S. */
1256 free_scope_forest_1 (s
)
1261 for (p
= s
->inner
; p
; p
= next
)
1264 free_scope_forest_1 (p
);
1273 /* Free the storage associated with the scope forest. */
1276 free_scope_forest (forest
)
1277 scope_forest_info
*forest
;
1280 for (i
= 0; i
< forest
->num_trees
; i
++)
1281 free_scope_forest_1 (forest
->trees
[i
]);
1285 /* Visualize the scope forest. */
1288 dump_scope_forest (forest
)
1289 scope_forest_info
*forest
;
1291 if (forest
->num_trees
== 0)
1292 fprintf (stderr
, "\n< Empty scope forest >\n");
1296 fprintf (stderr
, "\n< Scope forest >\n");
1297 for (i
= 0; i
< forest
->num_trees
; i
++)
1298 dump_scope_forest_1 (forest
->trees
[i
], 0);
1303 /* Recursive portion of dump_scope_forest. */
1306 dump_scope_forest_1 (s
, indent
)
1313 if (s
->bb_beg
!= NULL
&& s
->bb_beg
== s
->bb_end
1314 && RBI (s
->bb_beg
)->scope
1315 && RBI (s
->bb_beg
)->scope
->level
+ 1 == s
->level
)
1317 fprintf (stderr
, "%*s", indent
, "");
1318 fprintf (stderr
, "BB%d:\n", s
->bb_beg
->index
);
1321 fprintf (stderr
, "%*s", indent
, "");
1322 fprintf (stderr
, "{ level %d (block %p)\n", s
->level
,
1323 (PTR
) NOTE_BLOCK (s
->note_beg
));
1325 fprintf (stderr
, "%*s%s", indent
, "", "bbs:");
1326 for (i
= 0; i
< s
->num_bbs
; i
++)
1327 fprintf (stderr
, " %d", s
->bbs
[i
]->index
);
1328 fprintf (stderr
, "\n");
1330 for (p
= s
->inner
; p
; p
= p
->next
)
1331 dump_scope_forest_1 (p
, indent
+ 2);
1333 fprintf (stderr
, "%*s", indent
, "");
1334 fprintf (stderr
, "}\n");
1338 /* Reorder basic blocks. The main entry point to this file. */
1341 reorder_basic_blocks ()
1343 scope_forest_info forest
;
1346 if (n_basic_blocks
<= 1)
1349 /* We do not currently handle correct re-placement of EH notes. */
1350 for (i
= 0; i
< n_basic_blocks
; i
++)
1353 for (e
= BASIC_BLOCK (i
)->succ
; e
; e
= e
->succ_next
)
1354 if (e
->flags
& EDGE_EH
)
1358 for (i
= 0; i
< n_basic_blocks
; i
++)
1359 BASIC_BLOCK (i
)->aux
= xcalloc (1, sizeof (struct reorder_block_def
));
1361 build_scope_forest (&forest
);
1362 remove_scope_notes ();
1364 record_effective_endpoints ();
1365 make_reorder_chain ();
1366 fixup_reorder_chain ();
1368 #ifdef ENABLE_CHECKING
1369 verify_insn_chain ();
1372 rebuild_scope_notes (&forest
);
1373 free_scope_forest (&forest
);
1376 for (i
= 0; i
< n_basic_blocks
; i
++)
1377 free (BASIC_BLOCK (i
)->aux
);
1379 #ifdef ENABLE_CHECKING
1380 verify_flow_info ();