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"
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
170 } *reorder_block_def
;
172 #define RBI(BB) ((reorder_block_def) (BB)->aux)
175 /* Local function prototypes. */
176 static rtx skip_insns_after_block
PARAMS ((basic_block
));
177 static void record_effective_endpoints
PARAMS ((void));
178 static void make_reorder_chain
PARAMS ((void));
179 static basic_block make_reorder_chain_1
PARAMS ((basic_block
, basic_block
));
180 static rtx label_for_bb
PARAMS ((basic_block
));
181 static rtx emit_jump_to_block_after
PARAMS ((basic_block
, rtx
));
182 static void fixup_reorder_chain
PARAMS ((void));
183 static void relate_bbs_with_scopes
PARAMS ((scope
));
184 static scope make_new_scope
PARAMS ((int, rtx
));
185 static void build_scope_forest
PARAMS ((scope_forest_info
*));
186 static void remove_scope_notes
PARAMS ((void));
187 static void insert_intra_1
PARAMS ((scope
, rtx
*));
188 static void insert_intra_bb_scope_notes
PARAMS ((basic_block
));
189 static void insert_inter_bb_scope_notes
PARAMS ((basic_block
, basic_block
));
190 static void rebuild_scope_notes
PARAMS ((scope_forest_info
*));
191 static void free_scope_forest_1
PARAMS ((scope
));
192 static void free_scope_forest
PARAMS ((scope_forest_info
*));
193 void dump_scope_forest
PARAMS ((scope_forest_info
*));
194 static void dump_scope_forest_1
PARAMS ((scope
, int));
195 static rtx get_next_bb_note
PARAMS ((rtx
));
196 static rtx get_prev_bb_note
PARAMS ((rtx
));
198 void verify_insn_chain
PARAMS ((void));
200 /* Skip over inter-block insns occurring after BB which are typically
201 associated with BB (e.g., barriers). If there are any such insns,
202 we return the last one. Otherwise, we return the end of BB. */
205 skip_insns_after_block (bb
)
208 rtx insn
, last_insn
, next_head
;
210 next_head
= NULL_RTX
;
211 if (bb
->index
+ 1 != n_basic_blocks
)
212 next_head
= BASIC_BLOCK (bb
->index
+ 1)->head
;
214 for (last_insn
= bb
->end
; (insn
= NEXT_INSN (last_insn
)); last_insn
= insn
)
216 if (insn
== next_head
)
219 switch (GET_CODE (insn
))
225 switch (NOTE_LINE_NUMBER (insn
))
227 case NOTE_INSN_LOOP_END
:
228 case NOTE_INSN_BLOCK_END
:
229 case NOTE_INSN_DELETED
:
230 case NOTE_INSN_DELETED_LABEL
:
240 && GET_CODE (NEXT_INSN (insn
)) == JUMP_INSN
241 && (GET_CODE (PATTERN (NEXT_INSN (insn
))) == ADDR_VEC
242 || GET_CODE (PATTERN (NEXT_INSN (insn
))) == ADDR_DIFF_VEC
))
244 insn
= NEXT_INSN (insn
);
260 /* Locate the effective beginning and end of the insn chain for each
261 block, as defined by skip_insns_after_block above. */
264 record_effective_endpoints ()
266 rtx next_insn
= get_insns ();
269 for (i
= 0; i
< n_basic_blocks
; ++i
)
271 basic_block bb
= BASIC_BLOCK (i
);
274 RBI (bb
)->eff_head
= next_insn
;
275 end
= skip_insns_after_block (bb
);
276 RBI (bb
)->eff_end
= end
;
277 next_insn
= NEXT_INSN (end
);
282 /* Compute an ordering for a subgraph beginning with block BB. Record the
283 ordering in RBI()->index and chained through RBI()->next. */
286 make_reorder_chain ()
288 basic_block last_block
= NULL
;
289 basic_block prev
= NULL
;
290 int nbb_m1
= n_basic_blocks
- 1;
292 /* If we've not got epilogue in RTL, we must fallthru to the exit.
293 Force the last block to be at the end. */
294 /* ??? Some ABIs (e.g. MIPS) require the return insn to be at the
295 end of the function for stack unwinding purposes. */
298 last_block
= BASIC_BLOCK (nbb_m1
);
299 RBI (last_block
)->visited
= 1;
303 /* Loop until we've placed every block. */
307 basic_block next
= NULL
;
309 /* Find the next unplaced block. */
310 /* ??? Get rid of this loop, and track which blocks are not yet
311 placed more directly, so as to avoid the O(N^2) worst case.
312 Perhaps keep a doubly-linked list of all to-be-placed blocks;
313 remove from the list as we place. The head of that list is
314 what we're looking for here. */
316 for (i
= 0; i
<= nbb_m1
; ++i
)
318 basic_block bb
= BASIC_BLOCK (i
);
319 if (! RBI (bb
)->visited
)
328 prev
= make_reorder_chain_1 (next
, prev
);
330 while (RBI (prev
)->index
< nbb_m1
);
332 /* Terminate the chain. */
335 RBI (prev
)->next
= last_block
;
336 RBI (last_block
)->index
= RBI (prev
)->index
+ 1;
339 RBI (prev
)->next
= NULL
;
342 /* A helper function for make_reorder_chain.
344 We do not follow EH edges, or non-fallthru edges to noreturn blocks.
345 These are assumed to be the error condition and we wish to cluster
346 all of them at the very end of the function for the benefit of cache
347 locality for the rest of the function.
349 ??? We could do slightly better by noticing earlier that some subgraph
350 has all paths leading to noreturn functions, but for there to be more
351 than one block in such a subgraph is rare. */
354 make_reorder_chain_1 (bb
, prev
)
362 /* Mark this block visited. */
368 RBI (prev
)->next
= bb
;
369 new_index
= RBI (prev
)->index
+ 1;
370 RBI (bb
)->index
= new_index
;
372 if (rtl_dump_file
&& prev
->index
+ 1 != bb
->index
)
373 fprintf (rtl_dump_file
, "Reordering block %d (%d) after %d (%d)\n",
374 bb
->index
, RBI (bb
)->index
, prev
->index
, RBI (prev
)->index
);
378 RBI (bb
)->visited
= 1;
381 if (bb
->succ
== NULL
)
384 /* Find the most probable block. */
387 if (any_condjump_p (bb
->end
)
388 && (note
= find_reg_note (bb
->end
, REG_BR_PROB
, 0)) != NULL
)
390 int taken
, probability
;
391 edge e_taken
, e_fall
;
393 probability
= INTVAL (XEXP (note
, 0));
394 taken
= probability
> REG_BR_PROB_BASE
/ 2;
396 /* Find the normal taken edge and the normal fallthru edge.
398 Note, conditional jumps with other side effects may not
399 be fully optimized. In this case it is possible for
400 the conditional jump to branch to the same location as
403 We should probably work to improve optimization of that
404 case; however, it seems silly not to also deal with such
405 problems here if they happen to occur. */
407 e_taken
= e_fall
= NULL
;
408 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
410 if (e
->flags
& EDGE_FALLTHRU
)
412 else if (! (e
->flags
& EDGE_EH
))
416 next
= (taken
? e_taken
: e_fall
)->dest
;
419 /* In the absence of a prediction, disturb things as little as possible
420 by selecting the old "next" block from the list of successors. If
421 there had been a fallthru edge, that will be the one. */
424 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
425 if (e
->dest
->index
== bb
->index
+ 1)
427 if ((e
->flags
& EDGE_FALLTHRU
)
429 && ! (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))))
435 /* Make sure we didn't select a silly next block. */
436 if (! next
|| next
== EXIT_BLOCK_PTR
|| RBI (next
)->visited
)
439 /* Recurse on the successors. Unroll the last call, as the normal
440 case is exactly one or two edges, and we can tail recurse. */
441 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
442 if (e
->dest
!= EXIT_BLOCK_PTR
443 && ! RBI (e
->dest
)->visited
445 && ! (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
)))
449 prev
= make_reorder_chain_1 (next
, prev
);
450 next
= RBI (e
->dest
)->visited
? NULL
: e
->dest
;
465 /* Locate or create a label for a given basic block. */
471 rtx label
= bb
->head
;
473 if (GET_CODE (label
) != CODE_LABEL
)
476 fprintf (rtl_dump_file
, "Emitting label for block %d (%d)\n",
477 bb
->index
, RBI (bb
)->index
);
479 label
= emit_label_before (gen_label_rtx (), label
);
480 if (bb
->head
== RBI (bb
)->eff_head
)
481 RBI (bb
)->eff_head
= label
;
489 /* Emit a jump to BB after insn AFTER. */
492 emit_jump_to_block_after (bb
, after
)
498 if (bb
!= EXIT_BLOCK_PTR
)
500 rtx label
= label_for_bb (bb
);
501 jump
= emit_jump_insn_after (gen_jump (label
), after
);
502 JUMP_LABEL (jump
) = label
;
503 LABEL_NUSES (label
) += 1;
506 fprintf (rtl_dump_file
, "Emitting jump to block %d (%d)\n",
507 bb
->index
, RBI (bb
)->index
);
514 jump
= emit_jump_insn_after (gen_return (), after
);
517 fprintf (rtl_dump_file
, "Emitting return\n");
527 /* Given a reorder chain, rearrange the code to match. */
530 fixup_reorder_chain ()
532 basic_block bb
, last_bb
;
534 /* First do the bulk reordering -- rechain the blocks without regard to
535 the needed changes to jumps and labels. */
537 last_bb
= BASIC_BLOCK (0);
538 bb
= RBI (last_bb
)->next
;
541 rtx last_e
= RBI (last_bb
)->eff_end
;
542 rtx curr_h
= RBI (bb
)->eff_head
;
544 NEXT_INSN (last_e
) = curr_h
;
545 PREV_INSN (curr_h
) = last_e
;
550 NEXT_INSN (RBI (last_bb
)->eff_end
) = NULL_RTX
;
551 set_last_insn (RBI (last_bb
)->eff_end
);
553 /* Now add jumps and labels as needed to match the blocks new
556 for (bb
= BASIC_BLOCK (0); bb
; bb
= RBI (bb
)->next
)
558 edge e_fall
, e_taken
, e
;
559 rtx jump_insn
, barrier_insn
, bb_end_insn
;
562 if (bb
->succ
== NULL
)
565 /* Find the old fallthru edge, and another non-EH edge for
567 e_taken
= e_fall
= NULL
;
568 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
569 if (e
->flags
& EDGE_FALLTHRU
)
571 else if (! (e
->flags
& EDGE_EH
))
574 bb_end_insn
= bb
->end
;
575 if (GET_CODE (bb_end_insn
) == JUMP_INSN
)
577 if (any_uncondjump_p (bb_end_insn
))
579 /* If the destination is still not next, nothing to do. */
580 if (RBI (bb
)->index
+ 1 != RBI (e_taken
->dest
)->index
)
583 /* Otherwise, we can remove the jump and cleanup the edge. */
584 tidy_fallthru_edge (e_taken
, bb
, e_taken
->dest
);
585 RBI (bb
)->eff_end
= skip_insns_after_block (bb
);
586 RBI (e_taken
->dest
)->eff_head
= NEXT_INSN (RBI (bb
)->eff_end
);
589 fprintf (rtl_dump_file
, "Removing jump in block %d (%d)\n",
590 bb
->index
, RBI (bb
)->index
);
593 else if (any_condjump_p (bb_end_insn
))
595 /* If the old fallthru is still next, nothing to do. */
596 if (RBI (bb
)->index
+ 1 == RBI (e_fall
->dest
)->index
597 || (RBI (bb
)->index
== n_basic_blocks
- 1
598 && e_fall
->dest
== EXIT_BLOCK_PTR
))
601 /* There is one special case: if *neither* block is next,
602 such as happens at the very end of a function, then we'll
603 need to add a new unconditional jump. Choose the taken
604 edge based on known or assumed probability. */
605 if (RBI (bb
)->index
+ 1 != RBI (e_taken
->dest
)->index
)
607 rtx note
= find_reg_note (bb_end_insn
, REG_BR_PROB
, 0);
609 && INTVAL (XEXP (note
, 0)) < REG_BR_PROB_BASE
/ 2
610 && invert_jump (bb_end_insn
,
611 label_for_bb (e_fall
->dest
), 0))
613 e_fall
->flags
&= ~EDGE_FALLTHRU
;
614 e_taken
->flags
|= EDGE_FALLTHRU
;
615 e
= e_fall
, e_fall
= e_taken
, e_taken
= e
;
619 /* Otherwise we can try to invert the jump. This will
620 basically never fail, however, keep up the pretense. */
621 else if (invert_jump (bb_end_insn
,
622 label_for_bb (e_fall
->dest
), 0))
624 e_fall
->flags
&= ~EDGE_FALLTHRU
;
625 e_taken
->flags
|= EDGE_FALLTHRU
;
629 else if (returnjump_p (bb_end_insn
))
633 /* Otherwise we have some switch or computed jump. In the
634 99% case, there should not have been a fallthru edge. */
637 #ifdef CASE_DROPS_THROUGH
638 /* Except for VAX. Since we didn't have predication for the
639 tablejump, the fallthru block should not have moved. */
640 if (RBI (bb
)->index
+ 1 == RBI (e_fall
->dest
)->index
)
642 bb_end_insn
= skip_insns_after_block (bb
);
650 /* No fallthru implies a noreturn function with EH edges, or
651 something similarly bizarre. In any case, we don't need to
656 /* If the fallthru block is still next, nothing to do. */
657 if (RBI (bb
)->index
+ 1 == RBI (e_fall
->dest
)->index
658 || (RBI (bb
)->index
== n_basic_blocks
- 1
659 && e_fall
->dest
== EXIT_BLOCK_PTR
))
662 /* We need a new jump insn. If the block has only one outgoing
663 edge, then we can stuff the new jump insn in directly. */
664 if (bb
->succ
->succ_next
== NULL
)
666 e_fall
->flags
&= ~EDGE_FALLTHRU
;
668 jump_insn
= emit_jump_to_block_after (e_fall
->dest
, bb_end_insn
);
670 barrier_insn
= emit_barrier_after (jump_insn
);
671 RBI (bb
)->eff_end
= barrier_insn
;
676 /* We got here if we need to add a new jump insn in a new block
677 across the edge e_fall. */
679 jump_insn
= emit_jump_to_block_after (e_fall
->dest
, bb_end_insn
);
680 barrier_insn
= emit_barrier_after (jump_insn
);
682 VARRAY_GROW (basic_block_info
, ++n_basic_blocks
);
683 create_basic_block (n_basic_blocks
- 1, jump_insn
, jump_insn
, NULL
);
685 nb
= BASIC_BLOCK (n_basic_blocks
- 1);
686 nb
->global_live_at_start
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
687 nb
->global_live_at_end
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
690 COPY_REG_SET (nb
->global_live_at_start
, bb
->global_live_at_start
);
691 COPY_REG_SET (nb
->global_live_at_end
, bb
->global_live_at_start
);
693 nb
->aux
= xmalloc (sizeof (struct reorder_block_def
));
694 RBI (nb
)->eff_head
= nb
->head
;
695 RBI (nb
)->eff_end
= barrier_insn
;
696 RBI (nb
)->scope
= RBI (bb
)->scope
;
697 RBI (nb
)->index
= RBI (bb
)->index
+ 1;
698 RBI (nb
)->visited
= 1;
699 RBI (nb
)->next
= RBI (bb
)->next
;
702 /* Link to new block. */
703 make_edge (NULL
, nb
, e_fall
->dest
, 0);
704 redirect_edge_succ (e_fall
, nb
);
706 /* Don't process this new block. */
709 /* Fix subsequent reorder block indices to reflect new block. */
710 while ((nb
= RBI (nb
)->next
) != NULL
)
711 RBI (nb
)->index
+= 1;
714 /* Put basic_block_info in the new order. */
715 for (bb
= BASIC_BLOCK (0); bb
; bb
= RBI (bb
)->next
)
717 bb
->index
= RBI (bb
)->index
;
718 BASIC_BLOCK (bb
->index
) = bb
;
723 /* Perform sanity checks on the insn chain.
724 1. Check that next/prev pointers are consistent in both the forward and
726 2. Count insns in chain, going both directions, and check if equal.
727 3. Check that get_last_insn () returns the actual end of chain. */
740 for (x
= get_insns (); x
; x
= NEXT_INSN (x
))
742 if (PREV_INSN (x
) != prevx
)
744 fprintf (stderr
, "Forward traversal: insn chain corrupt.\n");
745 fprintf (stderr
, "previous insn:\n");
747 fprintf (stderr
, "current insn:\n");
755 if (prevx
!= get_last_insn ())
757 fprintf (stderr
, "last_insn corrupt.\n");
763 for (x
= get_last_insn (); x
; x
= PREV_INSN (x
))
765 if (NEXT_INSN (x
) != nextx
)
767 fprintf (stderr
, "Reverse traversal: insn chain corrupt.\n");
768 fprintf (stderr
, "current insn:\n");
770 fprintf (stderr
, "next insn:\n");
778 if (insn_cnt1
!= insn_cnt2
)
780 fprintf (stderr
, "insn_cnt1 (%d) not equal to insn_cnt2 (%d).\n",
781 insn_cnt1
, insn_cnt2
);
792 if (NOTE_INSN_BASIC_BLOCK_P (x
))
806 if (NOTE_INSN_BASIC_BLOCK_P (x
))
814 /* Determine and record the relationships between basic blocks and
815 scopes in scope tree S. */
818 relate_bbs_with_scopes (s
)
822 int i
, bbi1
, bbi2
, bbs_spanned
;
825 for (p
= s
->inner
; p
; p
= p
->next
)
826 relate_bbs_with_scopes (p
);
831 /* If the begin and end notes are both inside the same basic block,
832 or if they are both outside of basic blocks, then we know immediately
833 how they are related. Otherwise, we need to poke around to make the
835 if (s
->bb_beg
!= s
->bb_end
)
837 if (s
->bb_beg
&& s
->bb_end
)
839 /* Both notes are in different bbs. This implies that all the
840 basic blocks spanned by the pair of notes are contained in
842 bbi1
= s
->bb_beg
->index
;
843 bbi2
= s
->bb_end
->index
;
846 else if (! s
->bb_beg
)
848 /* First note is outside of a bb. If the scope spans more than
849 one basic block, then they all are contained within this
850 scope. Otherwise, this scope is contained within the basic
852 bbnote
= get_next_bb_note (s
->note_beg
);
855 if (NOTE_BASIC_BLOCK (bbnote
) == s
->bb_end
)
858 s
->bb_beg
= NOTE_BASIC_BLOCK (bbnote
);
862 bbi1
= NOTE_BASIC_BLOCK (bbnote
)->index
;
863 bbi2
= s
->bb_end
->index
;
868 else /* ! s->bb_end */
870 /* Second note is outside of a bb. If the scope spans more than
871 one basic block, then they all are contained within this
872 scope. Otherwise, this scope is contained within the basic
874 bbnote
= get_prev_bb_note (s
->note_end
);
877 if (NOTE_BASIC_BLOCK (bbnote
) == s
->bb_beg
)
880 s
->bb_end
= NOTE_BASIC_BLOCK (bbnote
);
884 bbi1
= s
->bb_beg
->index
;
885 bbi2
= NOTE_BASIC_BLOCK (bbnote
)->index
;
894 /* Both notes are in the same bb, which implies the block
895 contains this scope. */
900 /* Both notes are outside of any bbs. This implies that all the
901 basic blocks spanned by the pair of notes are contained in
903 There is a degenerate case to consider. If the notes do not
904 span any basic blocks, then it is an empty scope that can
905 safely be deleted or ignored. Mark these with level = -1. */
907 x1
= get_next_bb_note (s
->note_beg
);
908 x2
= get_prev_bb_note (s
->note_end
);
916 bbi1
= NOTE_BASIC_BLOCK (x1
)->index
;
917 bbi2
= NOTE_BASIC_BLOCK (x2
)->index
;
923 /* If the scope spans one or more basic blocks, we record them. We
924 only record the bbs that are immediately contained within this
925 scope. Note that if a scope is contained within a bb, we can tell
926 by checking that bb_beg = bb_end and that they are non-null. */
932 for (i
= bbi1
; i
<= bbi2
; i
++)
933 if (! RBI (BASIC_BLOCK (i
))->scope
)
936 s
->bbs
= xmalloc (s
->num_bbs
* sizeof (basic_block
));
937 for (i
= bbi1
; i
<= bbi2
; i
++)
939 basic_block curr_bb
= BASIC_BLOCK (i
);
940 if (! RBI (curr_bb
)->scope
)
942 s
->bbs
[j
++] = curr_bb
;
943 RBI (curr_bb
)->scope
= s
;
952 /* Allocate and initialize a new scope structure with scope level LEVEL,
953 and record the NOTE beginning the scope. */
956 make_new_scope (level
, note
)
960 scope new_scope
= xcalloc (1, sizeof (struct scope_def
));
961 new_scope
->level
= level
;
962 new_scope
->note_beg
= note
;
967 /* Build a forest representing the scope structure of the function.
968 Return a pointer to a structure describing the forest. */
971 build_scope_forest (forest
)
972 scope_forest_info
*forest
;
977 scope root
, curr_scope
= 0;
979 forest
->num_trees
= 0;
980 forest
->trees
= NULL
;
985 for (x
= get_insns (); x
; x
= NEXT_INSN (x
))
987 if (bbi
< n_basic_blocks
&& x
== BASIC_BLOCK (bbi
)->head
)
988 curr_bb
= BASIC_BLOCK (bbi
);
990 if (GET_CODE (x
) == NOTE
)
992 if (NOTE_LINE_NUMBER (x
) == NOTE_INSN_BLOCK_BEG
)
1000 new_scope
= make_new_scope (level
, x
);
1001 new_scope
->outer
= curr_scope
;
1002 new_scope
->next
= NULL
;
1003 if (! curr_scope
->inner
)
1005 curr_scope
->inner
= new_scope
;
1006 curr_scope
->inner_last
= new_scope
;
1010 curr_scope
->inner_last
->next
= new_scope
;
1011 curr_scope
->inner_last
= new_scope
;
1013 curr_scope
= curr_scope
->inner_last
;
1017 int ntrees
= forest
->num_trees
;
1019 curr_scope
= make_new_scope (level
, x
);
1021 forest
->trees
= xrealloc (forest
->trees
,
1022 sizeof (scope
) * (ntrees
+ 1));
1023 forest
->trees
[forest
->num_trees
++] = root
;
1025 curr_scope
->bb_beg
= curr_bb
;
1027 else if (NOTE_LINE_NUMBER (x
) == NOTE_INSN_BLOCK_END
)
1029 curr_scope
->bb_end
= curr_bb
;
1030 curr_scope
->note_end
= x
;
1032 curr_scope
= curr_scope
->outer
;
1038 if (curr_bb
&& curr_bb
->end
== x
)
1046 for (i
= 0; i
< forest
->num_trees
; i
++)
1047 relate_bbs_with_scopes (forest
->trees
[i
]);
1051 /* Remove all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes from
1055 remove_scope_notes ()
1058 basic_block currbb
= NULL
;
1060 for (x
= get_insns (); x
; x
= next
)
1062 next
= NEXT_INSN (x
);
1063 if (NOTE_INSN_BASIC_BLOCK_P (x
))
1064 currbb
= NOTE_BASIC_BLOCK (x
);
1066 if (GET_CODE (x
) == NOTE
1067 && (NOTE_LINE_NUMBER (x
) == NOTE_INSN_BLOCK_BEG
1068 || NOTE_LINE_NUMBER (x
) == NOTE_INSN_BLOCK_END
))
1070 /* Check if the scope note happens to be the end of a bb. */
1071 if (currbb
&& x
== currbb
->end
)
1072 currbb
->end
= PREV_INSN (x
);
1073 if (currbb
&& x
== currbb
->head
)
1078 NEXT_INSN (PREV_INSN (x
)) = next
;
1079 PREV_INSN (next
) = PREV_INSN (x
);
1081 NEXT_INSN (x
) = NULL
;
1082 PREV_INSN (x
) = NULL
;
1091 /* Insert scope note pairs for a contained scope tree S after insn IP. */
1094 insert_intra_1 (s
, ip
)
1100 if (NOTE_BLOCK (s
->note_beg
))
1102 *ip
= emit_note_after (NOTE_INSN_BLOCK_BEG
, *ip
);
1103 NOTE_BLOCK (*ip
) = NOTE_BLOCK (s
->note_beg
);
1106 for (p
= s
->inner
; p
; p
= p
->next
)
1107 insert_intra_1 (p
, ip
);
1109 if (NOTE_BLOCK (s
->note_beg
))
1111 *ip
= emit_note_after (NOTE_INSN_BLOCK_END
, *ip
);
1112 NOTE_BLOCK (*ip
) = NOTE_BLOCK (s
->note_end
);
1117 /* Insert NOTE_INSN_BLOCK_END notes and NOTE_INSN_BLOCK_BEG notes for
1118 scopes that are contained within BB. */
1121 insert_intra_bb_scope_notes (bb
)
1124 scope s
= RBI (bb
)->scope
;
1132 if (GET_CODE (ip
) == CODE_LABEL
)
1133 ip
= NEXT_INSN (ip
);
1135 for (p
= s
->inner
; p
; p
= p
->next
)
1137 if (p
->bb_beg
!= NULL
&& p
->bb_beg
== p
->bb_end
&& p
->bb_beg
== bb
)
1138 insert_intra_1 (p
, &ip
);
1143 /* Given two consecutive basic blocks BB1 and BB2 with different scopes,
1144 insert NOTE_INSN_BLOCK_END notes after BB1 and NOTE_INSN_BLOCK_BEG
1145 notes before BB2 such that the notes are correctly balanced. If BB1 or
1146 BB2 is NULL, we are inserting scope notes for the first and last basic
1147 blocks, respectively. */
1150 insert_inter_bb_scope_notes (bb1
, bb2
)
1157 /* It is possible that a basic block is not contained in any scope.
1158 In that case, we either open or close a scope but not both. */
1161 scope s1
= RBI (bb1
)->scope
;
1162 scope s2
= RBI (bb2
)->scope
;
1171 /* Find common ancestor scope. */
1174 scope s1
= RBI (bb1
)->scope
;
1175 scope s2
= RBI (bb2
)->scope
;
1180 if (s1
->level
> s2
->level
)
1182 else if (s2
->level
> s1
->level
)
1198 scope s
= RBI (bb1
)->scope
;
1199 ip
= RBI (bb1
)->eff_end
;
1202 if (NOTE_BLOCK (s
->note_beg
))
1204 ip
= emit_note_after (NOTE_INSN_BLOCK_END
, ip
);
1205 NOTE_BLOCK (ip
) = NOTE_BLOCK (s
->note_end
);
1214 scope s
= RBI (bb2
)->scope
;
1218 if (NOTE_BLOCK (s
->note_beg
))
1220 ip
= emit_note_before (NOTE_INSN_BLOCK_BEG
, ip
);
1221 NOTE_BLOCK (ip
) = NOTE_BLOCK (s
->note_beg
);
1229 /* Rebuild all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes based
1230 on the scope forest and the newly reordered basic blocks. */
1233 rebuild_scope_notes (forest
)
1234 scope_forest_info
*forest
;
1238 if (forest
->num_trees
== 0)
1241 /* Start by opening the scopes before the first basic block. */
1242 insert_inter_bb_scope_notes (NULL
, BASIC_BLOCK (0));
1244 /* Then, open and close scopes as needed between blocks. */
1245 for (i
= 0; i
< n_basic_blocks
- 1; i
++)
1247 basic_block bb1
= BASIC_BLOCK (i
);
1248 basic_block bb2
= BASIC_BLOCK (i
+ 1);
1249 if (RBI (bb1
)->scope
!= RBI (bb2
)->scope
)
1250 insert_inter_bb_scope_notes (bb1
, bb2
);
1251 insert_intra_bb_scope_notes (bb1
);
1254 /* Finally, close the scopes after the last basic block. */
1255 insert_inter_bb_scope_notes (BASIC_BLOCK (n_basic_blocks
- 1), NULL
);
1256 insert_intra_bb_scope_notes (BASIC_BLOCK (n_basic_blocks
- 1));
1260 /* Free the storage associated with the scope tree at S. */
1263 free_scope_forest_1 (s
)
1268 for (p
= s
->inner
; p
; p
= next
)
1271 free_scope_forest_1 (p
);
1280 /* Free the storage associated with the scope forest. */
1283 free_scope_forest (forest
)
1284 scope_forest_info
*forest
;
1287 for (i
= 0; i
< forest
->num_trees
; i
++)
1288 free_scope_forest_1 (forest
->trees
[i
]);
1292 /* Visualize the scope forest. */
1295 dump_scope_forest (forest
)
1296 scope_forest_info
*forest
;
1298 if (forest
->num_trees
== 0)
1299 fprintf (stderr
, "\n< Empty scope forest >\n");
1303 fprintf (stderr
, "\n< Scope forest >\n");
1304 for (i
= 0; i
< forest
->num_trees
; i
++)
1305 dump_scope_forest_1 (forest
->trees
[i
], 0);
1310 /* Recursive portion of dump_scope_forest. */
1313 dump_scope_forest_1 (s
, indent
)
1320 if (s
->bb_beg
!= NULL
&& s
->bb_beg
== s
->bb_end
1321 && RBI (s
->bb_beg
)->scope
1322 && RBI (s
->bb_beg
)->scope
->level
+ 1 == s
->level
)
1324 fprintf (stderr
, "%*s", indent
, "");
1325 fprintf (stderr
, "BB%d:\n", s
->bb_beg
->index
);
1328 fprintf (stderr
, "%*s", indent
, "");
1329 fprintf (stderr
, "{ level %d (block %p)\n", s
->level
,
1330 (PTR
) NOTE_BLOCK (s
->note_beg
));
1332 fprintf (stderr
, "%*s%s", indent
, "", "bbs:");
1333 for (i
= 0; i
< s
->num_bbs
; i
++)
1334 fprintf (stderr
, " %d", s
->bbs
[i
]->index
);
1335 fprintf (stderr
, "\n");
1337 for (p
= s
->inner
; p
; p
= p
->next
)
1338 dump_scope_forest_1 (p
, indent
+ 2);
1340 fprintf (stderr
, "%*s", indent
, "");
1341 fprintf (stderr
, "}\n");
1345 /* Reorder basic blocks. The main entry point to this file. */
1348 reorder_basic_blocks ()
1350 scope_forest_info forest
;
1353 if (n_basic_blocks
<= 1)
1356 for (i
= 0; i
< n_basic_blocks
; i
++)
1357 BASIC_BLOCK (i
)->aux
= xcalloc (1, sizeof (struct reorder_block_def
));
1359 EXIT_BLOCK_PTR
->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 free (EXIT_BLOCK_PTR
->aux
);
1381 #ifdef ENABLE_CHECKING
1382 verify_flow_info ();