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.
32 #include "basic-block.h"
33 #include "insn-config.h"
35 #include "hard-reg-set.h"
42 #include "insn-flags.h"
47 /* The contents of the current function definition are allocated
48 in this obstack, and all are freed at the end of the function.
49 For top-level functions, this is temporary_obstack.
50 Separate obstacks are made for nested functions. */
52 extern struct obstack
*function_obstack
;
55 /* Structure to hold information about lexical scopes. */
56 typedef struct scope_def
60 /* The NOTE_INSN_BLOCK_BEG that started this scope. */
63 /* The NOTE_INSN_BLOCK_END that ended this scope. */
66 /* The bb containing note_beg (if any). */
69 /* The bb containing note_end (if any). */
72 /* List of basic blocks contained within this scope. */
75 /* Number of blocks contained within this scope. */
78 /* The outer scope or NULL if outermost scope. */
79 struct scope_def
*outer
;
81 /* The first inner scope or NULL if innermost scope. */
82 struct scope_def
*inner
;
84 /* The last inner scope or NULL if innermost scope. */
85 struct scope_def
*inner_last
;
87 /* Link to the next (sibling) scope. */
88 struct scope_def
*next
;
91 /* Structure to hold information about the scope forest. */
94 /* Number of trees in forest. */
97 /* List of tree roots. */
102 typedef struct reorder_block_def
{
105 basic_block add_jump
;
110 } *reorder_block_def
;
112 static struct reorder_block_def rbd_init
118 NULL_RTX
, /* eff_head */
119 NULL_RTX
, /* eff_end */
124 #define REORDER_BLOCK_HEAD 0x1
125 #define REORDER_BLOCK_VISITED 0x2
127 #define REORDER_BLOCK_FLAGS(bb) \
128 ((reorder_block_def) (bb)->aux)->flags
130 #define REORDER_BLOCK_INDEX(bb) \
131 ((reorder_block_def) (bb)->aux)->index
133 #define REORDER_BLOCK_ADD_JUMP(bb) \
134 ((reorder_block_def) (bb)->aux)->add_jump
136 #define REORDER_BLOCK_SUCC(bb) \
137 ((reorder_block_def) (bb)->aux)->succ
139 #define REORDER_BLOCK_EFF_HEAD(bb) \
140 ((reorder_block_def) (bb)->aux)->eff_head
142 #define REORDER_BLOCK_EFF_END(bb) \
143 ((reorder_block_def) (bb)->aux)->eff_end
145 #define REORDER_BLOCK_SCOPE(bb) \
146 ((reorder_block_def) (bb)->aux)->scope
149 static int reorder_index
;
150 static basic_block reorder_last_visited
;
152 enum reorder_skip_type
{REORDER_SKIP_BEFORE
, REORDER_SKIP_AFTER
,
153 REORDER_SKIP_BLOCK_END
};
156 /* Local function prototypes. */
157 static rtx skip_insns_between_block
PARAMS ((basic_block
,
158 enum reorder_skip_type
));
159 static basic_block get_common_dest
PARAMS ((basic_block
, basic_block
));
160 static basic_block chain_reorder_blocks
PARAMS ((edge
, basic_block
));
161 static void make_reorder_chain
PARAMS ((basic_block
));
162 static void fixup_reorder_chain
PARAMS ((void));
163 #ifdef ENABLE_CHECKING
164 static void verify_insn_chain
PARAMS ((void));
166 static void relate_bbs_with_scopes
PARAMS ((scope
));
167 static scope make_new_scope
PARAMS ((int, rtx
));
168 static void build_scope_forest
PARAMS ((scope_forest_info
*));
169 static void remove_scope_notes
PARAMS ((void));
170 static void insert_intra_1
PARAMS ((scope
, rtx
*));
171 static void insert_intra_bb_scope_notes
PARAMS ((basic_block
));
172 static void insert_inter_bb_scope_notes
PARAMS ((basic_block
, basic_block
));
173 static void rebuild_scope_notes
PARAMS ((scope_forest_info
*));
174 static void free_scope_forest_1
PARAMS ((scope
));
175 static void free_scope_forest
PARAMS ((scope_forest_info
*));
176 void dump_scope_forest
PARAMS ((scope_forest_info
*));
177 static void dump_scope_forest_1
PARAMS ((scope
, int));
179 /* Skip over insns BEFORE or AFTER BB which are typically associated with
183 skip_insns_between_block (bb
, skip_type
)
185 enum reorder_skip_type skip_type
;
189 if (skip_type
== REORDER_SKIP_BEFORE
)
191 if (bb
== ENTRY_BLOCK_PTR
)
194 last_insn
= bb
->head
;
195 for (insn
= PREV_INSN (bb
->head
);
196 insn
&& insn
!= BASIC_BLOCK (bb
->index
- 1)->end
;
197 last_insn
= insn
, insn
= PREV_INSN (insn
))
199 if (NEXT_INSN (insn
) != last_insn
)
202 if (GET_CODE (insn
) == NOTE
203 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_LOOP_END
204 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_BASIC_BLOCK
205 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_BLOCK_END
)
215 if (bb
== EXIT_BLOCK_PTR
)
218 for (insn
= NEXT_INSN (bb
->end
);
220 last_insn
= insn
, insn
= NEXT_INSN (insn
))
222 if (bb
->index
+ 1 != n_basic_blocks
223 && insn
== BASIC_BLOCK (bb
->index
+ 1)->head
)
226 if (GET_CODE (insn
) == BARRIER
227 || GET_CODE (insn
) == JUMP_INSN
228 || (GET_CODE (insn
) == NOTE
229 && (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_END
230 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_BLOCK_END
)))
233 if (GET_CODE (insn
) == CODE_LABEL
234 && GET_CODE (NEXT_INSN (insn
)) == JUMP_INSN
235 && (GET_CODE (PATTERN (NEXT_INSN (insn
))) == ADDR_VEC
237 (NEXT_INSN (insn
))) == ADDR_DIFF_VEC
))
239 insn
= NEXT_INSN (insn
);
243 /* Skip to next non-deleted insn. */
244 if (GET_CODE (insn
) == NOTE
245 && (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_DELETED
246 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_DELETED_LABEL
))
252 if (skip_type
== REORDER_SKIP_BLOCK_END
)
254 int found_block_end
= 0;
256 for (; insn
; last_insn
= insn
, insn
= NEXT_INSN (insn
))
258 if (bb
->index
+ 1 != n_basic_blocks
259 && insn
== BASIC_BLOCK (bb
->index
+ 1)->head
)
262 if (GET_CODE (insn
) == NOTE
263 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_BLOCK_END
)
269 if (GET_CODE (insn
) == NOTE
270 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_DELETED
)
273 if (GET_CODE (insn
) == NOTE
274 && NOTE_LINE_NUMBER (insn
) >= 0
276 && GET_CODE (NEXT_INSN (insn
)) == NOTE
277 && (NOTE_LINE_NUMBER (NEXT_INSN (insn
))
278 == NOTE_INSN_BLOCK_END
))
283 if (! found_block_end
)
292 /* Return common destination for blocks BB0 and BB1. */
295 get_common_dest (bb0
, bb1
)
296 basic_block bb0
, bb1
;
300 for (e0
= bb0
->succ
; e0
; e0
= e0
->succ_next
)
302 for (e1
= bb1
->succ
; e1
; e1
= e1
->succ_next
)
304 if (e0
->dest
== e1
->dest
)
314 /* Move the destination block for edge E after chain end block CEB
315 Adding jumps and labels is deferred until fixup_reorder_chain. */
318 chain_reorder_blocks (e
, ceb
)
322 basic_block sb
= e
->src
;
323 basic_block db
= e
->dest
;
324 rtx cebe_insn
, dbh_insn
, dbe_insn
;
327 enum cond_types
{NO_COND
, PREDICT_THEN_WITH_ELSE
, PREDICT_ELSE
,
328 PREDICT_THEN_NO_ELSE
, PREDICT_NOT_THEN_NO_ELSE
};
329 enum cond_types cond_type
;
330 enum cond_block_types
{NO_COND_BLOCK
, THEN_BLOCK
, ELSE_BLOCK
,
332 enum cond_block_types cond_block_type
;
335 fprintf (rtl_dump_file
,
336 "Edge from basic block %d to basic block %d last visited %d\n",
337 sb
->index
, db
->index
, ceb
->index
);
338 cebe_insn
= REORDER_BLOCK_EFF_END (ceb
);
340 /* Blocks are in original order. */
341 if (sb
->index
== ceb
->index
342 && ceb
->index
+ 1 == db
->index
&& NEXT_INSN (cebe_insn
))
345 /* Get the type of block and type of condition. */
347 cond_block_type
= NO_COND_BLOCK
;
348 if (GET_CODE (sb
->end
) == JUMP_INSN
&& ! simplejump_p (sb
->end
)
349 && condjump_p (sb
->end
))
351 if (e
->flags
& EDGE_FALLTHRU
)
352 cond_block_type
= THEN_BLOCK
;
353 else if (get_common_dest (sb
->succ
->dest
, sb
))
354 cond_block_type
= NO_ELSE_BLOCK
;
356 cond_block_type
= ELSE_BLOCK
;
358 if (sb
->succ
->succ_next
359 && get_common_dest (sb
->succ
->dest
, sb
))
361 if (cond_block_type
== THEN_BLOCK
)
363 if (! (REORDER_BLOCK_FLAGS (sb
->succ
->succ_next
->dest
)
364 & REORDER_BLOCK_VISITED
))
365 cond_type
= PREDICT_THEN_NO_ELSE
;
367 cond_type
= PREDICT_NOT_THEN_NO_ELSE
;
369 else if (cond_block_type
== NO_ELSE_BLOCK
)
371 if (! (REORDER_BLOCK_FLAGS (sb
->succ
->dest
)
372 & REORDER_BLOCK_VISITED
))
373 cond_type
= PREDICT_NOT_THEN_NO_ELSE
;
375 cond_type
= PREDICT_THEN_NO_ELSE
;
380 if (cond_block_type
== THEN_BLOCK
)
382 if (! (REORDER_BLOCK_FLAGS (sb
->succ
->succ_next
->dest
)
383 & REORDER_BLOCK_VISITED
))
384 cond_type
= PREDICT_THEN_WITH_ELSE
;
386 cond_type
= PREDICT_ELSE
;
388 else if (cond_block_type
== ELSE_BLOCK
389 && sb
->succ
->dest
!= EXIT_BLOCK_PTR
)
391 if (! (REORDER_BLOCK_FLAGS (sb
->succ
->dest
)
392 & REORDER_BLOCK_VISITED
))
393 cond_type
= PREDICT_ELSE
;
395 cond_type
= PREDICT_THEN_WITH_ELSE
;
402 static const char * cond_type_str
[] = {"not cond jump", "predict then",
404 "predict then w/o else",
405 "predict not then w/o else"};
406 static const char * cond_block_type_str
[] = {"not then or else block",
409 "then w/o else block"};
411 fprintf (rtl_dump_file
, " %s (looking at %s)\n",
412 cond_type_str
[(int)cond_type
],
413 cond_block_type_str
[(int)cond_block_type
]);
416 /* Reflect that then block will move and we'll jump to it. */
417 if (cond_block_type
!= THEN_BLOCK
418 && (cond_type
== PREDICT_ELSE
419 || cond_type
== PREDICT_NOT_THEN_NO_ELSE
))
422 fprintf (rtl_dump_file
,
423 " then jump from block %d to block %d\n",
424 sb
->index
, sb
->succ
->dest
->index
);
426 /* Jump to reordered then block. */
427 REORDER_BLOCK_ADD_JUMP (sb
) = sb
->succ
->dest
;
430 /* Reflect that then block will jump back when we have no else. */
431 if (cond_block_type
!= THEN_BLOCK
432 && cond_type
== PREDICT_NOT_THEN_NO_ELSE
)
434 for (ee
= sb
->succ
->dest
->succ
;
435 ee
&& ! (ee
->flags
& EDGE_FALLTHRU
);
439 if (ee
&& ! (GET_CODE (sb
->succ
->dest
->end
) == JUMP_INSN
440 && ! simplejump_p (sb
->succ
->dest
->end
)))
442 REORDER_BLOCK_ADD_JUMP (sb
->succ
->dest
) = ee
->dest
;
446 /* Reflect that else block will jump back. */
447 if (cond_block_type
== ELSE_BLOCK
448 && (cond_type
== PREDICT_THEN_WITH_ELSE
|| cond_type
== PREDICT_ELSE
))
453 && last_edge
->dest
!= EXIT_BLOCK_PTR
454 && GET_CODE (last_edge
->dest
->head
) == CODE_LABEL
455 && ! (GET_CODE (db
->end
) == JUMP_INSN
))
458 fprintf (rtl_dump_file
,
459 " else jump from block %d to block %d\n",
460 db
->index
, last_edge
->dest
->index
);
462 REORDER_BLOCK_ADD_JUMP (db
) = last_edge
->dest
;
466 /* This block's successor has already been reordered. This can happen
467 when we reorder a chain starting at a then or else. */
468 for (last_edge
= db
->succ
;
469 last_edge
&& ! (last_edge
->flags
& EDGE_FALLTHRU
);
470 last_edge
= last_edge
->succ_next
)
474 && last_edge
->dest
!= EXIT_BLOCK_PTR
475 && (REORDER_BLOCK_FLAGS (last_edge
->dest
)
476 & REORDER_BLOCK_VISITED
))
479 fprintf (rtl_dump_file
,
480 " end of chain jump from block %d to block %d\n",
481 db
->index
, last_edge
->dest
->index
);
483 REORDER_BLOCK_ADD_JUMP (db
) = last_edge
->dest
;
486 dbh_insn
= REORDER_BLOCK_EFF_HEAD (db
);
487 cebe_insn
= REORDER_BLOCK_EFF_END (ceb
);
488 dbe_insn
= REORDER_BLOCK_EFF_END (db
);
490 /* Rechain predicted block. */
491 NEXT_INSN (cebe_insn
) = dbh_insn
;
492 PREV_INSN (dbh_insn
) = cebe_insn
;
494 if (db
->index
!= n_basic_blocks
- 1)
495 NEXT_INSN (dbe_insn
) = 0;
501 /* Reorder blocks starting at block BB. */
504 make_reorder_chain (bb
)
508 basic_block visited_edge
= NULL
;
512 if (bb
== EXIT_BLOCK_PTR
)
515 /* Find the most probable block. */
518 if (GET_CODE (block_end
) == JUMP_INSN
&& condjump_p (block_end
))
520 rtx note
= find_reg_note (block_end
, REG_BR_PROB
, 0);
523 probability
= INTVAL (XEXP (note
, 0));
527 if (probability
>= REG_BR_PROB_BASE
/ 2)
528 e
= bb
->succ
->succ_next
;
531 /* Add chosen successor to chain and recurse on it. */
532 if (e
&& e
->dest
!= EXIT_BLOCK_PTR
534 && (! (REORDER_BLOCK_FLAGS (e
->dest
) & REORDER_BLOCK_VISITED
)
535 || (REORDER_BLOCK_FLAGS (e
->dest
) == REORDER_BLOCK_HEAD
)))
537 if (! (REORDER_BLOCK_FLAGS (bb
) & REORDER_BLOCK_VISITED
))
539 REORDER_BLOCK_FLAGS (bb
) |= REORDER_BLOCK_HEAD
;
540 REORDER_BLOCK_INDEX (bb
) = reorder_index
++;
541 REORDER_BLOCK_FLAGS (bb
) |= REORDER_BLOCK_VISITED
;
544 if (REORDER_BLOCK_FLAGS (e
->dest
) & REORDER_BLOCK_VISITED
)
545 REORDER_BLOCK_FLAGS (e
->dest
) &= ~REORDER_BLOCK_HEAD
;
547 REORDER_BLOCK_SUCC (bb
) = e
;
549 visited_edge
= e
->dest
;
551 reorder_last_visited
= chain_reorder_blocks (e
, bb
);
554 && ! (REORDER_BLOCK_FLAGS (e
->dest
)
555 & REORDER_BLOCK_VISITED
))
556 make_reorder_chain (e
->dest
);
560 if (! (REORDER_BLOCK_FLAGS (bb
) & REORDER_BLOCK_VISITED
))
562 REORDER_BLOCK_INDEX (bb
) = reorder_index
++;
563 REORDER_BLOCK_FLAGS (bb
) |= REORDER_BLOCK_VISITED
;
567 /* Recurse on the successors. */
568 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
570 if (e
->dest
&& e
->dest
== EXIT_BLOCK_PTR
)
575 && e
->dest
!= visited_edge
576 && ! (REORDER_BLOCK_FLAGS (e
->dest
)
577 & REORDER_BLOCK_VISITED
))
580 = chain_reorder_blocks (e
, reorder_last_visited
);
581 make_reorder_chain (e
->dest
);
587 /* Fixup jumps and labels after reordering basic blocks. */
590 fixup_reorder_chain ()
594 int orig_num_blocks
= n_basic_blocks
;
596 /* Set the new last insn. */
600 for (j
= 0; j
< n_basic_blocks
; j
++)
602 int val
= REORDER_BLOCK_INDEX (BASIC_BLOCK (j
));
609 insn
= REORDER_BLOCK_EFF_END (BASIC_BLOCK (max_index
));
610 NEXT_INSN (insn
) = NULL_RTX
;
611 set_last_insn (insn
);
614 /* Add jumps and labels to fixup blocks. */
615 for (i
= 0; i
< orig_num_blocks
; i
++)
618 basic_block bbi
= BASIC_BLOCK (i
);
619 if (REORDER_BLOCK_ADD_JUMP (bbi
))
621 rtx label_insn
, jump_insn
, barrier_insn
;
623 if (GET_CODE (REORDER_BLOCK_ADD_JUMP (bbi
)->head
) == CODE_LABEL
)
624 label_insn
= REORDER_BLOCK_ADD_JUMP (bbi
)->head
;
627 rtx new_label
= gen_label_rtx ();
628 label_insn
= emit_label_before (new_label
,
629 REORDER_BLOCK_ADD_JUMP (bbi
)->head
);
630 REORDER_BLOCK_ADD_JUMP (bbi
)->head
= label_insn
;
633 if (GET_CODE (bbi
->end
) != JUMP_INSN
)
635 jump_insn
= emit_jump_insn_after (gen_jump (label_insn
),
637 bbi
->end
= jump_insn
;
642 jump_insn
= emit_jump_insn_after (gen_jump (label_insn
),
643 REORDER_BLOCK_EFF_END (bbi
));
647 JUMP_LABEL (jump_insn
) = label_insn
;
648 ++LABEL_NUSES (label_insn
);
649 barrier_insn
= emit_barrier_after (jump_insn
);
651 /* Add block for jump. Typically this is when a then is not
652 predicted and we are jumping to the moved then block. */
657 VARRAY_GROW (basic_block_info
, ++n_basic_blocks
);
658 create_basic_block (n_basic_blocks
- 1, jump_insn
,
660 nb
= BASIC_BLOCK (n_basic_blocks
- 1);
661 nb
->global_live_at_start
662 = OBSTACK_ALLOC_REG_SET (function_obstack
);
663 nb
->global_live_at_end
664 = OBSTACK_ALLOC_REG_SET (function_obstack
);
666 COPY_REG_SET (nb
->global_live_at_start
,
667 bbi
->global_live_at_start
);
668 COPY_REG_SET (nb
->global_live_at_end
,
669 bbi
->global_live_at_start
);
670 BASIC_BLOCK (nb
->index
)->local_set
= 0;
672 nb
->aux
= xcalloc (1, sizeof (struct reorder_block_def
));
673 REORDER_BLOCK_INDEX (nb
) = REORDER_BLOCK_INDEX (bbi
) + 1;
674 /* Relink to new block. */
675 nb
->succ
= bbi
->succ
;
678 make_edge (NULL
, bbi
, nb
, 0);
680 = bbi
->succ
->succ_next
->succ_next
;
681 nb
->succ
->succ_next
= 0;
682 /* Fix reorder block index to reflect new block. */
683 for (j
= 0; j
< n_basic_blocks
- 1; j
++)
685 basic_block bbj
= BASIC_BLOCK (j
);
686 if (REORDER_BLOCK_INDEX (bbj
)
687 >= REORDER_BLOCK_INDEX (bbi
) + 1)
688 REORDER_BLOCK_INDEX (bbj
)++;
690 REORDER_BLOCK_SCOPE (nb
) = REORDER_BLOCK_SCOPE (bbi
);
691 REORDER_BLOCK_EFF_HEAD (nb
) = nb
->head
;
692 REORDER_BLOCK_EFF_END (nb
) = barrier_insn
;
695 REORDER_BLOCK_EFF_END (bbi
) = barrier_insn
;
701 /* Perform sanity checks on the insn chain.
702 1. Check that next/prev pointers are consistent in both the forward and
704 2. Count insns in chain, going both directions, and check if equal.
705 3. Check that get_last_insn () returns the actual end of chain. */
706 #ifdef ENABLE_CHECKING
718 for (x
= get_insns (); x
; x
= NEXT_INSN (x
))
720 if (PREV_INSN (x
) != prevx
)
722 fprintf (stderr
, "Forward traversal: insn chain corrupt.\n");
723 fprintf (stderr
, "previous insn:\n");
725 fprintf (stderr
, "current insn:\n");
733 if (prevx
!= get_last_insn ())
735 fprintf (stderr
, "last_insn corrupt.\n");
741 for (x
= get_last_insn (); x
; x
= PREV_INSN (x
))
743 if (NEXT_INSN (x
) != nextx
)
745 fprintf (stderr
, "Reverse traversal: insn chain corrupt.\n");
746 fprintf (stderr
, "current insn:\n");
748 fprintf (stderr
, "next insn:\n");
756 if (insn_cnt1
!= insn_cnt2
)
758 fprintf (stderr
, "insn_cnt1 (%d) not equal to insn_cnt2 (%d).\n",
759 insn_cnt1
, insn_cnt2
);
771 if (GET_CODE (x
) == NOTE
772 && NOTE_LINE_NUMBER (x
) == NOTE_INSN_BASIC_BLOCK
)
786 if (GET_CODE (x
) == NOTE
787 && NOTE_LINE_NUMBER (x
) == NOTE_INSN_BASIC_BLOCK
)
795 /* Determine and record the relationships between basic blocks and
796 scopes in scope tree S. */
799 relate_bbs_with_scopes (s
)
803 int i
, bbi1
, bbi2
, bbs_spanned
;
806 for (p
= s
->inner
; p
; p
= p
->next
)
807 relate_bbs_with_scopes (p
);
812 /* If the begin and end notes are both inside the same basic block,
813 or if they are both outside of basic blocks, then we know immediately
814 how they are related. Otherwise, we need to poke around to make the
816 if (s
->bb_beg
!= s
->bb_end
)
818 if (s
->bb_beg
&& s
->bb_end
)
820 /* Both notes are in different bbs. This implies that all the
821 basic blocks spanned by the pair of notes are contained in
823 bbi1
= s
->bb_beg
->index
;
824 bbi2
= s
->bb_end
->index
;
827 else if (! s
->bb_beg
)
829 /* First note is outside of a bb. If the scope spans more than
830 one basic block, then they all are contained within this
831 scope. Otherwise, this scope is contained within the basic
833 bbnote
= get_next_bb_note (s
->note_beg
);
836 if (NOTE_BASIC_BLOCK (bbnote
) == s
->bb_end
)
839 s
->bb_beg
= NOTE_BASIC_BLOCK (bbnote
);
843 bbi1
= NOTE_BASIC_BLOCK (bbnote
)->index
;
844 bbi2
= s
->bb_end
->index
;
849 else /* ! s->bb_end */
851 /* Second note is outside of a bb. If the scope spans more than
852 one basic block, then they all are contained within this
853 scope. Otherwise, this scope is contained within the basic
855 bbnote
= get_prev_bb_note (s
->note_end
);
858 if (NOTE_BASIC_BLOCK (bbnote
) == s
->bb_beg
)
861 s
->bb_end
= NOTE_BASIC_BLOCK (bbnote
);
865 bbi1
= s
->bb_beg
->index
;
866 bbi2
= NOTE_BASIC_BLOCK (bbnote
)->index
;
875 /* Both notes are in the same bb, which implies the block
876 contains this scope. */
881 /* Both notes are outside of any bbs. This implies that all the
882 basic blocks spanned by the pair of notes are contained in
884 There is a degenerate case to consider. If the notes do not
885 span any basic blocks, then it is an empty scope that can
886 safely be deleted or ignored. Mark these with level = -1. */
888 x1
= get_next_bb_note (s
->note_beg
);
889 x2
= get_prev_bb_note (s
->note_end
);
897 bbi1
= NOTE_BASIC_BLOCK (x1
)->index
;
898 bbi2
= NOTE_BASIC_BLOCK (x2
)->index
;
905 /* If the scope spans one or more basic blocks, we record them. We
906 only record the bbs that are immediately contained within this
907 scope. Note that if a scope is contained within a bb, we can tell
908 by checking that bb_beg = bb_end and that they are non-null. */
914 for (i
= bbi1
; i
<= bbi2
; i
++)
915 if (! REORDER_BLOCK_SCOPE (BASIC_BLOCK (i
)))
918 s
->bbs
= xcalloc (s
->num_bbs
, sizeof (struct basic_block_def
));
919 for (i
= bbi1
; i
<= bbi2
; i
++)
921 basic_block curr_bb
= BASIC_BLOCK (i
);
922 if (! REORDER_BLOCK_SCOPE (curr_bb
))
924 s
->bbs
[j
++] = curr_bb
;
925 REORDER_BLOCK_SCOPE (curr_bb
) = s
;
934 /* Allocate and initialize a new scope structure with scope level LEVEL,
935 and record the NOTE beginning the scope. */
938 make_new_scope (level
, note
)
942 scope new_scope
= xcalloc (1, sizeof (struct scope_def
));
943 new_scope
->level
= level
;
944 new_scope
->note_beg
= note
;
945 new_scope
->note_end
= NULL
;
946 new_scope
->bb_beg
= NULL
;
947 new_scope
->bb_end
= NULL
;
948 new_scope
->inner
= NULL
;
949 new_scope
->inner_last
= NULL
;
950 new_scope
->outer
= NULL
;
951 new_scope
->next
= NULL
;
952 new_scope
->num_bbs
= 0;
953 new_scope
->bbs
= NULL
;
958 /* Build a forest representing the scope structure of the function.
959 Return a pointer to a structure describing the forest. */
962 build_scope_forest (forest
)
963 scope_forest_info
*forest
;
968 scope root
, curr_scope
;
970 forest
->num_trees
= 0;
971 forest
->trees
= NULL
;
976 for (x
= get_insns (); x
; x
= NEXT_INSN (x
))
978 if (bbi
< n_basic_blocks
&& x
== BASIC_BLOCK (bbi
)->head
)
979 curr_bb
= BASIC_BLOCK (bbi
);
981 if (GET_CODE (x
) == NOTE
)
983 if (NOTE_LINE_NUMBER (x
) == NOTE_INSN_BLOCK_BEG
)
991 new_scope
= make_new_scope (level
, x
);
992 new_scope
->outer
= curr_scope
;
993 new_scope
->next
= NULL
;
994 if (! curr_scope
->inner
)
996 curr_scope
->inner
= new_scope
;
997 curr_scope
->inner_last
= new_scope
;
1001 curr_scope
->inner_last
->next
= new_scope
;
1002 curr_scope
->inner_last
= new_scope
;
1004 curr_scope
= curr_scope
->inner_last
;
1008 int ntrees
= forest
->num_trees
;
1010 curr_scope
= make_new_scope (level
, x
);
1013 forest
->trees
= xcalloc (1, sizeof (scope
));
1015 forest
->trees
= xrealloc (forest
->trees
,
1016 sizeof (scope
) * (ntrees
+ 1));
1017 forest
->trees
[forest
->num_trees
++] = root
;
1019 curr_scope
->bb_beg
= curr_bb
;
1021 else if (NOTE_LINE_NUMBER (x
) == NOTE_INSN_BLOCK_END
)
1023 curr_scope
->bb_end
= curr_bb
;
1024 curr_scope
->note_end
= x
;
1026 curr_scope
= curr_scope
->outer
;
1032 if (curr_bb
&& curr_bb
->end
== x
)
1040 for (i
= 0; i
< forest
->num_trees
; i
++)
1041 relate_bbs_with_scopes (forest
->trees
[i
]);
1045 /* Remove all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes from
1049 remove_scope_notes ()
1052 basic_block currbb
= NULL
;
1054 for (x
= get_insns (); x
; x
= next
)
1056 next
= NEXT_INSN (x
);
1057 if (GET_CODE (x
) == NOTE
1058 && NOTE_LINE_NUMBER (x
) == NOTE_INSN_BASIC_BLOCK
)
1059 currbb
= NOTE_BASIC_BLOCK (x
);
1061 if (GET_CODE (x
) == NOTE
1062 && (NOTE_LINE_NUMBER (x
) == NOTE_INSN_BLOCK_BEG
1063 || NOTE_LINE_NUMBER (x
) == NOTE_INSN_BLOCK_END
))
1065 /* Check if the scope note happens to be the end of a bb. */
1066 if (currbb
&& x
== currbb
->end
)
1067 currbb
->end
= PREV_INSN (x
);
1068 if (currbb
&& x
== currbb
->head
)
1073 NEXT_INSN (PREV_INSN (x
)) = next
;
1074 PREV_INSN (next
) = PREV_INSN (x
);
1076 NEXT_INSN (x
) = NULL
;
1077 PREV_INSN (x
) = NULL
;
1086 /* Insert scope note pairs for a contained scope tree S after insn IP. */
1088 insert_intra_1 (s
, ip
)
1094 if (NOTE_BLOCK (s
->note_beg
))
1096 *ip
= emit_note_after (NOTE_INSN_BLOCK_BEG
, *ip
);
1097 NOTE_BLOCK (*ip
) = NOTE_BLOCK (s
->note_beg
);
1100 for (p
= s
->inner
; p
; p
= p
->next
)
1101 insert_intra_1 (p
, ip
);
1103 if (NOTE_BLOCK (s
->note_beg
))
1105 *ip
= emit_note_after (NOTE_INSN_BLOCK_END
, *ip
);
1106 NOTE_BLOCK (*ip
) = NOTE_BLOCK (s
->note_end
);
1111 /* Insert NOTE_INSN_BLOCK_END notes and NOTE_INSN_BLOCK_BEG notes for
1112 scopes that are contained within BB. */
1115 insert_intra_bb_scope_notes (bb
)
1118 scope s
= REORDER_BLOCK_SCOPE (bb
);
1126 if (GET_CODE (ip
) == CODE_LABEL
)
1127 ip
= NEXT_INSN (ip
);
1129 for (p
= s
->inner
; p
; p
= p
->next
)
1131 if (p
->bb_beg
!= NULL
&& p
->bb_beg
== p
->bb_end
&& p
->bb_beg
== bb
)
1132 insert_intra_1 (p
, &ip
);
1137 /* Given two consecutive basic blocks BB1 and BB2 with different scopes,
1138 insert NOTE_INSN_BLOCK_END notes after BB1 and NOTE_INSN_BLOCK_BEG
1139 notes before BB2 such that the notes are correctly balanced. If BB1 or
1140 BB2 is NULL, we are inserting scope notes for the first and last basic
1141 blocks, respectively. */
1144 insert_inter_bb_scope_notes (bb1
, bb2
)
1151 /* It is possible that a basic block is not contained in any scope.
1152 In that case, we either open or close a scope but not both. */
1155 scope s1
= REORDER_BLOCK_SCOPE (bb1
);
1156 scope s2
= REORDER_BLOCK_SCOPE (bb2
);
1165 /* Find common ancestor scope. */
1168 scope s1
= REORDER_BLOCK_SCOPE (bb1
);
1169 scope s2
= REORDER_BLOCK_SCOPE (bb2
);
1174 if (s1
->level
> s2
->level
)
1176 else if (s2
->level
> s1
->level
)
1192 scope s
= REORDER_BLOCK_SCOPE (bb1
);
1193 ip
= REORDER_BLOCK_EFF_END (bb1
);
1196 if (NOTE_BLOCK (s
->note_beg
))
1198 ip
= emit_note_after (NOTE_INSN_BLOCK_END
, ip
);
1199 NOTE_BLOCK (ip
) = NOTE_BLOCK (s
->note_end
);
1208 scope s
= REORDER_BLOCK_SCOPE (bb2
);
1212 if (NOTE_BLOCK (s
->note_beg
))
1214 ip
= emit_note_before (NOTE_INSN_BLOCK_BEG
, ip
);
1215 NOTE_BLOCK (ip
) = NOTE_BLOCK (s
->note_beg
);
1223 /* Rebuild all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes based
1224 on the scope forest and the newly reordered basic blocks. */
1227 rebuild_scope_notes (forest
)
1228 scope_forest_info
*forest
;
1232 if (forest
->num_trees
== 0)
1235 /* Start by opening the scopes before the first basic block. */
1236 insert_inter_bb_scope_notes (NULL
, BASIC_BLOCK (0));
1238 /* Then, open and close scopes as needed between blocks. */
1239 for (i
= 0; i
< n_basic_blocks
- 1; i
++)
1241 basic_block bb1
= BASIC_BLOCK (i
);
1242 basic_block bb2
= BASIC_BLOCK (i
+ 1);
1243 if (REORDER_BLOCK_SCOPE (bb1
) != REORDER_BLOCK_SCOPE (bb2
))
1244 insert_inter_bb_scope_notes (bb1
, bb2
);
1245 insert_intra_bb_scope_notes (bb1
);
1248 /* Finally, close the scopes after the last basic block. */
1249 insert_inter_bb_scope_notes (BASIC_BLOCK (n_basic_blocks
- 1), NULL
);
1250 insert_intra_bb_scope_notes (BASIC_BLOCK (n_basic_blocks
- 1));
1254 /* Free the storage associated with the scope tree at S. */
1257 free_scope_forest_1 (s
)
1262 for (p
= s
->inner
; p
; p
= next
)
1265 free_scope_forest_1 (p
);
1274 /* Free the storage associated with the scope forest. */
1277 free_scope_forest (forest
)
1278 scope_forest_info
*forest
;
1281 for (i
= 0; i
< forest
->num_trees
; i
++)
1282 free_scope_forest_1 (forest
->trees
[i
]);
1286 /* Visualize the scope forest. */
1289 dump_scope_forest (forest
)
1290 scope_forest_info
*forest
;
1292 if (forest
->num_trees
== 0)
1293 fprintf (stderr
, "\n< Empty scope forest >\n");
1297 fprintf (stderr
, "\n< Scope forest >\n");
1298 for (i
= 0; i
< forest
->num_trees
; i
++)
1299 dump_scope_forest_1 (forest
->trees
[i
], 0);
1304 /* Recursive portion of dump_scope_forest. */
1307 dump_scope_forest_1 (s
, indent
)
1314 if (s
->bb_beg
!= NULL
&& s
->bb_beg
== s
->bb_end
1315 && REORDER_BLOCK_SCOPE (s
->bb_beg
)
1316 && REORDER_BLOCK_SCOPE (s
->bb_beg
)->level
+ 1 == s
->level
)
1318 fprintf (stderr
, "%*s", indent
, "");
1319 fprintf (stderr
, "BB%d:\n", s
->bb_beg
->index
);
1322 fprintf (stderr
, "%*s", indent
, "");
1323 fprintf (stderr
, "{ level %d (block %p)\n", s
->level
,
1324 NOTE_BLOCK (s
->note_beg
));
1326 fprintf (stderr
, "%*s%s", indent
, "", "bbs:");
1327 for (i
= 0; i
< s
->num_bbs
; i
++)
1328 fprintf (stderr
, " %d", s
->bbs
[i
]->index
);
1329 fprintf (stderr
, "\n");
1331 for (p
= s
->inner
; p
; p
= p
->next
)
1332 dump_scope_forest_1 (p
, indent
+ 2);
1334 fprintf (stderr
, "%*s", indent
, "");
1335 fprintf (stderr
, "}\n");
1339 /* Reorder basic blocks. */
1342 reorder_basic_blocks ()
1345 struct loops loops_info
;
1347 scope_forest_info forest
;
1349 if (profile_arc_flag
)
1352 if (n_basic_blocks
<= 1)
1355 /* Exception edges are not currently handled. */
1356 for (i
= 0; i
< n_basic_blocks
; i
++)
1360 for (e
= BASIC_BLOCK (i
)->succ
; e
&& ! (e
->flags
& EDGE_EH
);
1364 if (e
&& (e
->flags
& EDGE_EH
))
1370 /* Find natural loops using the CFG. */
1371 num_loops
= flow_loops_find (&loops_info
);
1373 /* Dump loop information. */
1374 flow_loops_dump (&loops_info
, rtl_dump_file
, 0);
1376 reorder_last_visited
= BASIC_BLOCK (0);
1378 for (i
= 0; i
< n_basic_blocks
; i
++)
1380 basic_block bbi
= BASIC_BLOCK (i
);
1381 bbi
->aux
= xcalloc (1, sizeof (struct reorder_block_def
));
1382 *((struct reorder_block_def
*)bbi
->aux
) = rbd_init
;
1385 build_scope_forest (&forest
);
1386 remove_scope_notes ();
1388 for (i
= 0; i
< n_basic_blocks
; i
++)
1390 basic_block bbi
= BASIC_BLOCK (i
);
1391 REORDER_BLOCK_EFF_END (bbi
)
1392 = skip_insns_between_block (bbi
, REORDER_SKIP_AFTER
);
1394 REORDER_BLOCK_EFF_HEAD (bbi
) = get_insns ();
1397 rtx prev_eff_end
= REORDER_BLOCK_EFF_END (BASIC_BLOCK (i
- 1));
1398 REORDER_BLOCK_EFF_HEAD (bbi
) = NEXT_INSN (prev_eff_end
);
1402 /* If we've not got epilogue in RTL, we must fallthru to the exit.
1403 Force the last block to be at the end. */
1404 /* ??? Some ABIs (e.g. MIPS) require the return insn to be at the
1405 end of the function for stack unwinding purposes. */
1407 #ifndef HAVE_epilogue
1408 #define HAVE_epilogue 0
1411 if (! HAVE_epilogue
)
1413 basic_block last
= BASIC_BLOCK (n_basic_blocks
- 1);
1414 REORDER_BLOCK_INDEX (last
) = n_basic_blocks
- 1;
1415 REORDER_BLOCK_FLAGS (last
) |= REORDER_BLOCK_VISITED
;
1418 make_reorder_chain (BASIC_BLOCK (0));
1420 fixup_reorder_chain ();
1422 #ifdef ENABLE_CHECKING
1423 verify_insn_chain ();
1426 /* Put basic_block_info in new order. */
1427 for (i
= 0; i
< n_basic_blocks
- 1; i
++)
1429 for (j
= i
; i
!= REORDER_BLOCK_INDEX (BASIC_BLOCK (j
)); j
++)
1432 if (REORDER_BLOCK_INDEX (BASIC_BLOCK (j
)) == i
1437 int rbi
= REORDER_BLOCK_INDEX (BASIC_BLOCK (j
));
1439 temprbi
= BASIC_BLOCK (rbi
)->index
;
1440 BASIC_BLOCK (rbi
)->index
= BASIC_BLOCK (j
)->index
;
1441 BASIC_BLOCK (j
)->index
= temprbi
;
1442 tempbb
= BASIC_BLOCK (rbi
);
1443 BASIC_BLOCK (rbi
) = BASIC_BLOCK (j
);
1444 BASIC_BLOCK (j
) = tempbb
;
1448 rebuild_scope_notes (&forest
);
1449 free_scope_forest (&forest
);
1452 #ifdef ENABLE_CHECKING
1453 verify_flow_info ();
1456 for (i
= 0; i
< n_basic_blocks
; i
++)
1457 free (BASIC_BLOCK (i
)->aux
);
1459 /* Free loop information. */
1460 flow_loops_free (&loops_info
);