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
;
109 } *reorder_block_def
;
111 static struct reorder_block_def rbd_init
116 NULL_RTX
, /* eff_head */
117 NULL_RTX
, /* eff_end */
122 #define REORDER_BLOCK_HEAD 0x1
123 #define REORDER_BLOCK_VISITED 0x2
125 #define REORDER_BLOCK_FLAGS(bb) \
126 ((reorder_block_def) (bb)->aux)->flags
128 #define REORDER_BLOCK_INDEX(bb) \
129 ((reorder_block_def) (bb)->aux)->index
131 #define REORDER_BLOCK_ADD_JUMP(bb) \
132 ((reorder_block_def) (bb)->aux)->add_jump
134 #define REORDER_BLOCK_EFF_HEAD(bb) \
135 ((reorder_block_def) (bb)->aux)->eff_head
137 #define REORDER_BLOCK_EFF_END(bb) \
138 ((reorder_block_def) (bb)->aux)->eff_end
140 #define REORDER_BLOCK_SCOPE(bb) \
141 ((reorder_block_def) (bb)->aux)->scope
144 static int reorder_index
;
145 static basic_block reorder_last_visited
;
148 /* Local function prototypes. */
149 static rtx skip_insns_after_block
PARAMS ((basic_block
));
150 static basic_block get_common_dest
PARAMS ((basic_block
, basic_block
));
151 static basic_block chain_reorder_blocks
PARAMS ((edge
, basic_block
));
152 static void make_reorder_chain
PARAMS ((basic_block
));
153 static void fixup_reorder_chain
PARAMS ((void));
154 #ifdef ENABLE_CHECKING
155 static void verify_insn_chain
PARAMS ((void));
157 static void relate_bbs_with_scopes
PARAMS ((scope
));
158 static scope make_new_scope
PARAMS ((int, rtx
));
159 static void build_scope_forest
PARAMS ((scope_forest_info
*));
160 static void remove_scope_notes
PARAMS ((void));
161 static void insert_intra_1
PARAMS ((scope
, rtx
*));
162 static void insert_intra_bb_scope_notes
PARAMS ((basic_block
));
163 static void insert_inter_bb_scope_notes
PARAMS ((basic_block
, basic_block
));
164 static void rebuild_scope_notes
PARAMS ((scope_forest_info
*));
165 static void free_scope_forest_1
PARAMS ((scope
));
166 static void free_scope_forest
PARAMS ((scope_forest_info
*));
167 void dump_scope_forest
PARAMS ((scope_forest_info
*));
168 static void dump_scope_forest_1
PARAMS ((scope
, int));
170 /* Skip over inter-block insns occurring after BB which are typically
171 associated with BB (e.g., barriers). If there are any such insns,
172 we return the last one. Otherwise, we return the end of BB. */
175 skip_insns_after_block (bb
)
182 if (bb
== EXIT_BLOCK_PTR
)
185 for (insn
= NEXT_INSN (bb
->end
);
187 last_insn
= insn
, insn
= NEXT_INSN (insn
))
189 if (bb
->index
+ 1 != n_basic_blocks
190 && insn
== BASIC_BLOCK (bb
->index
+ 1)->head
)
193 if (GET_CODE (insn
) == BARRIER
194 || GET_CODE (insn
) == JUMP_INSN
195 || (GET_CODE (insn
) == NOTE
196 && (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_END
197 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_BLOCK_END
)))
200 if (GET_CODE (insn
) == CODE_LABEL
201 && GET_CODE (NEXT_INSN (insn
)) == JUMP_INSN
202 && (GET_CODE (PATTERN (NEXT_INSN (insn
))) == ADDR_VEC
203 || GET_CODE (PATTERN (NEXT_INSN (insn
))) == ADDR_DIFF_VEC
))
205 insn
= NEXT_INSN (insn
);
209 /* Skip to next non-deleted insn. */
210 if (GET_CODE (insn
) == NOTE
211 && (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_DELETED
212 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_DELETED_LABEL
))
222 /* Return common destination for blocks BB0 and BB1. */
225 get_common_dest (bb0
, bb1
)
226 basic_block bb0
, bb1
;
230 for (e0
= bb0
->succ
; e0
; e0
= e0
->succ_next
)
232 for (e1
= bb1
->succ
; e1
; e1
= e1
->succ_next
)
234 if (e0
->dest
== e1
->dest
)
244 /* Move the destination block for edge E after chain end block CEB
245 Adding jumps and labels is deferred until fixup_reorder_chain. */
248 chain_reorder_blocks (e
, ceb
)
252 basic_block sb
= e
->src
;
253 basic_block db
= e
->dest
;
254 rtx cebe_insn
, dbh_insn
, dbe_insn
;
256 edge e_fallthru
, e_jump
;
258 enum cond_types
{NO_COND
, PREDICT_THEN_WITH_ELSE
, PREDICT_ELSE
,
259 PREDICT_THEN_NO_ELSE
, PREDICT_NOT_THEN_NO_ELSE
};
260 enum cond_types cond_type
;
261 enum cond_block_types
{NO_COND_BLOCK
, THEN_BLOCK
, ELSE_BLOCK
,
263 enum cond_block_types cond_block_type
;
266 fprintf (rtl_dump_file
,
267 "Edge from basic block %d to basic block %d last visited %d\n",
268 sb
->index
, db
->index
, ceb
->index
);
269 cebe_insn
= REORDER_BLOCK_EFF_END (ceb
);
271 /* Blocks are in original order. */
272 if (sb
->index
== ceb
->index
273 && ceb
->index
+ 1 == db
->index
&& NEXT_INSN (cebe_insn
))
276 e_fallthru
= e_jump
= e
;
278 /* Get the type of block and type of condition. */
280 cond_block_type
= NO_COND_BLOCK
;
281 if (GET_CODE (sb
->end
) == JUMP_INSN
&& ! simplejump_p (sb
->end
)
282 && condjump_p (sb
->end
))
284 if (e
->flags
& EDGE_FALLTHRU
)
287 e_jump
= sb
->succ
->succ_next
;
288 else if (e
== sb
->succ
->succ_next
)
296 e_fallthru
= sb
->succ
->succ_next
;
297 else if (e
== sb
->succ
->succ_next
)
298 e_fallthru
= sb
->succ
;
303 if (e
->flags
& EDGE_FALLTHRU
)
304 cond_block_type
= THEN_BLOCK
;
305 else if (get_common_dest (e_fallthru
->dest
, sb
))
306 cond_block_type
= NO_ELSE_BLOCK
;
308 cond_block_type
= ELSE_BLOCK
;
310 if (get_common_dest (e_fallthru
->dest
, sb
))
312 if (cond_block_type
== THEN_BLOCK
)
314 if (! (REORDER_BLOCK_FLAGS (e
->dest
)
315 & REORDER_BLOCK_VISITED
))
316 cond_type
= PREDICT_THEN_NO_ELSE
;
318 cond_type
= PREDICT_NOT_THEN_NO_ELSE
;
320 else if (cond_block_type
== NO_ELSE_BLOCK
)
322 if (! (REORDER_BLOCK_FLAGS (e
->dest
)
323 & REORDER_BLOCK_VISITED
))
324 cond_type
= PREDICT_NOT_THEN_NO_ELSE
;
326 cond_type
= PREDICT_THEN_NO_ELSE
;
331 if (cond_block_type
== THEN_BLOCK
)
333 if (! (REORDER_BLOCK_FLAGS (e
->dest
)
334 & REORDER_BLOCK_VISITED
))
335 cond_type
= PREDICT_THEN_WITH_ELSE
;
337 cond_type
= PREDICT_ELSE
;
339 else if (cond_block_type
== ELSE_BLOCK
340 && e_fallthru
->dest
!= EXIT_BLOCK_PTR
)
342 if (! (REORDER_BLOCK_FLAGS (e
->dest
)
343 & REORDER_BLOCK_VISITED
))
344 cond_type
= PREDICT_ELSE
;
346 cond_type
= PREDICT_THEN_WITH_ELSE
;
353 static const char * cond_type_str
[] = {"not cond jump", "predict then",
355 "predict then w/o else",
356 "predict not then w/o else"};
357 static const char * cond_block_type_str
[] = {"not then or else block",
360 "then w/o else block"};
362 fprintf (rtl_dump_file
, " %s (looking at %s)\n",
363 cond_type_str
[(int)cond_type
],
364 cond_block_type_str
[(int)cond_block_type
]);
367 /* Reflect that then block will move and we'll jump to it. */
368 if (cond_block_type
!= THEN_BLOCK
369 && (cond_type
== PREDICT_ELSE
370 || cond_type
== PREDICT_NOT_THEN_NO_ELSE
))
373 fprintf (rtl_dump_file
,
374 " then jump from block %d to block %d\n",
375 sb
->index
, e_fallthru
->dest
->index
);
377 /* Jump to reordered then block. */
378 REORDER_BLOCK_ADD_JUMP (sb
) = e_fallthru
->dest
;
381 /* Reflect that then block will jump back when we have no else. */
382 if (cond_block_type
!= THEN_BLOCK
383 && cond_type
== PREDICT_NOT_THEN_NO_ELSE
)
385 basic_block jbb
= e_fallthru
->dest
;
387 ee
&& ! (ee
->flags
& EDGE_FALLTHRU
);
391 if (ee
&& ! (GET_CODE (jbb
->end
) == JUMP_INSN
392 && ! simplejump_p (jbb
->end
)))
394 REORDER_BLOCK_ADD_JUMP (jbb
) = ee
->dest
;
398 /* Reflect that else block will jump back. */
399 if (cond_block_type
== ELSE_BLOCK
400 && (cond_type
== PREDICT_THEN_WITH_ELSE
|| cond_type
== PREDICT_ELSE
))
405 && last_edge
->dest
!= EXIT_BLOCK_PTR
406 && GET_CODE (last_edge
->dest
->head
) == CODE_LABEL
407 && ! (GET_CODE (db
->end
) == JUMP_INSN
))
410 fprintf (rtl_dump_file
,
411 " else jump from block %d to block %d\n",
412 db
->index
, last_edge
->dest
->index
);
414 REORDER_BLOCK_ADD_JUMP (db
) = last_edge
->dest
;
418 /* This block's successor has already been reordered. This can happen
419 when we reorder a chain starting at a then or else. */
420 for (last_edge
= db
->succ
;
421 last_edge
&& ! (last_edge
->flags
& EDGE_FALLTHRU
);
422 last_edge
= last_edge
->succ_next
)
426 && last_edge
->dest
!= EXIT_BLOCK_PTR
427 && (REORDER_BLOCK_FLAGS (last_edge
->dest
)
428 & REORDER_BLOCK_VISITED
))
431 fprintf (rtl_dump_file
,
432 " end of chain jump from block %d to block %d\n",
433 db
->index
, last_edge
->dest
->index
);
435 REORDER_BLOCK_ADD_JUMP (db
) = last_edge
->dest
;
438 dbh_insn
= REORDER_BLOCK_EFF_HEAD (db
);
439 cebe_insn
= REORDER_BLOCK_EFF_END (ceb
);
440 dbe_insn
= REORDER_BLOCK_EFF_END (db
);
442 /* Rechain predicted block. */
443 NEXT_INSN (cebe_insn
) = dbh_insn
;
444 PREV_INSN (dbh_insn
) = cebe_insn
;
446 if (db
->index
!= n_basic_blocks
- 1)
447 NEXT_INSN (dbe_insn
) = 0;
453 /* Reorder blocks starting at block BB. */
456 make_reorder_chain (bb
)
460 basic_block visited_edge
= NULL
;
464 if (bb
== EXIT_BLOCK_PTR
)
467 /* Find the most probable block. */
470 if (GET_CODE (block_end
) == JUMP_INSN
&& condjump_p (block_end
))
472 rtx note
= find_reg_note (block_end
, REG_BR_PROB
, 0);
475 probability
= INTVAL (XEXP (note
, 0));
479 if (probability
>= REG_BR_PROB_BASE
/ 2)
480 e
= bb
->succ
->succ_next
;
483 /* Add chosen successor to chain and recurse on it. */
484 if (e
&& e
->dest
!= EXIT_BLOCK_PTR
486 && (! (REORDER_BLOCK_FLAGS (e
->dest
) & REORDER_BLOCK_VISITED
)
487 || (REORDER_BLOCK_FLAGS (e
->dest
) == REORDER_BLOCK_HEAD
)))
489 if (! (REORDER_BLOCK_FLAGS (bb
) & REORDER_BLOCK_VISITED
))
491 REORDER_BLOCK_FLAGS (bb
) |= REORDER_BLOCK_HEAD
;
492 REORDER_BLOCK_INDEX (bb
) = reorder_index
++;
493 REORDER_BLOCK_FLAGS (bb
) |= REORDER_BLOCK_VISITED
;
496 if (REORDER_BLOCK_FLAGS (e
->dest
) & REORDER_BLOCK_VISITED
)
497 REORDER_BLOCK_FLAGS (e
->dest
) &= ~REORDER_BLOCK_HEAD
;
499 visited_edge
= e
->dest
;
501 reorder_last_visited
= chain_reorder_blocks (e
, bb
);
504 && ! (REORDER_BLOCK_FLAGS (e
->dest
)
505 & REORDER_BLOCK_VISITED
))
506 make_reorder_chain (e
->dest
);
510 if (! (REORDER_BLOCK_FLAGS (bb
) & REORDER_BLOCK_VISITED
))
512 REORDER_BLOCK_INDEX (bb
) = reorder_index
++;
513 REORDER_BLOCK_FLAGS (bb
) |= REORDER_BLOCK_VISITED
;
517 /* Recurse on the successors. */
518 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
520 if (e
->dest
&& e
->dest
== EXIT_BLOCK_PTR
)
525 && e
->dest
!= visited_edge
526 && ! (REORDER_BLOCK_FLAGS (e
->dest
)
527 & REORDER_BLOCK_VISITED
))
530 = chain_reorder_blocks (e
, reorder_last_visited
);
531 make_reorder_chain (e
->dest
);
537 /* Fixup jumps and labels after reordering basic blocks. */
540 fixup_reorder_chain ()
544 int orig_num_blocks
= n_basic_blocks
;
546 /* Set the new last insn. */
550 for (j
= 0; j
< n_basic_blocks
; j
++)
552 int val
= REORDER_BLOCK_INDEX (BASIC_BLOCK (j
));
559 insn
= REORDER_BLOCK_EFF_END (BASIC_BLOCK (max_index
));
560 NEXT_INSN (insn
) = NULL_RTX
;
561 set_last_insn (insn
);
564 /* Add jumps and labels to fixup blocks. */
565 for (i
= 0; i
< orig_num_blocks
; i
++)
568 basic_block bbi
= BASIC_BLOCK (i
);
569 if (REORDER_BLOCK_ADD_JUMP (bbi
))
571 rtx label_insn
, jump_insn
, barrier_insn
;
573 if (GET_CODE (REORDER_BLOCK_ADD_JUMP (bbi
)->head
) == CODE_LABEL
)
574 label_insn
= REORDER_BLOCK_ADD_JUMP (bbi
)->head
;
577 rtx new_label
= gen_label_rtx ();
578 label_insn
= emit_label_before (new_label
,
579 REORDER_BLOCK_ADD_JUMP (bbi
)->head
);
580 REORDER_BLOCK_ADD_JUMP (bbi
)->head
= label_insn
;
583 if (GET_CODE (bbi
->end
) != JUMP_INSN
)
585 jump_insn
= emit_jump_insn_after (gen_jump (label_insn
),
587 bbi
->end
= jump_insn
;
592 jump_insn
= emit_jump_insn_after (gen_jump (label_insn
),
593 REORDER_BLOCK_EFF_END (bbi
));
597 JUMP_LABEL (jump_insn
) = label_insn
;
598 ++LABEL_NUSES (label_insn
);
599 barrier_insn
= emit_barrier_after (jump_insn
);
601 /* Add block for jump. Typically this is when a then is not
602 predicted and we are jumping to the moved then block. */
607 VARRAY_GROW (basic_block_info
, ++n_basic_blocks
);
608 create_basic_block (n_basic_blocks
- 1, jump_insn
,
610 nb
= BASIC_BLOCK (n_basic_blocks
- 1);
611 nb
->global_live_at_start
612 = OBSTACK_ALLOC_REG_SET (function_obstack
);
613 nb
->global_live_at_end
614 = OBSTACK_ALLOC_REG_SET (function_obstack
);
616 COPY_REG_SET (nb
->global_live_at_start
,
617 bbi
->global_live_at_start
);
618 COPY_REG_SET (nb
->global_live_at_end
,
619 bbi
->global_live_at_start
);
620 BASIC_BLOCK (nb
->index
)->local_set
= 0;
622 nb
->aux
= xcalloc (1, sizeof (struct reorder_block_def
));
623 REORDER_BLOCK_INDEX (nb
) = REORDER_BLOCK_INDEX (bbi
) + 1;
624 /* Relink to new block. */
625 nb
->succ
= bbi
->succ
;
628 make_edge (NULL
, bbi
, nb
, 0);
630 = bbi
->succ
->succ_next
->succ_next
;
631 nb
->succ
->succ_next
= 0;
632 /* Fix reorder block index to reflect new block. */
633 for (j
= 0; j
< n_basic_blocks
- 1; j
++)
635 basic_block bbj
= BASIC_BLOCK (j
);
636 if (REORDER_BLOCK_INDEX (bbj
)
637 >= REORDER_BLOCK_INDEX (bbi
) + 1)
638 REORDER_BLOCK_INDEX (bbj
)++;
640 REORDER_BLOCK_SCOPE (nb
) = REORDER_BLOCK_SCOPE (bbi
);
641 REORDER_BLOCK_EFF_HEAD (nb
) = nb
->head
;
642 REORDER_BLOCK_EFF_END (nb
) = barrier_insn
;
645 REORDER_BLOCK_EFF_END (bbi
) = barrier_insn
;
651 /* Perform sanity checks on the insn chain.
652 1. Check that next/prev pointers are consistent in both the forward and
654 2. Count insns in chain, going both directions, and check if equal.
655 3. Check that get_last_insn () returns the actual end of chain. */
656 #ifdef ENABLE_CHECKING
668 for (x
= get_insns (); x
; x
= NEXT_INSN (x
))
670 if (PREV_INSN (x
) != prevx
)
672 fprintf (stderr
, "Forward traversal: insn chain corrupt.\n");
673 fprintf (stderr
, "previous insn:\n");
675 fprintf (stderr
, "current insn:\n");
683 if (prevx
!= get_last_insn ())
685 fprintf (stderr
, "last_insn corrupt.\n");
691 for (x
= get_last_insn (); x
; x
= PREV_INSN (x
))
693 if (NEXT_INSN (x
) != nextx
)
695 fprintf (stderr
, "Reverse traversal: insn chain corrupt.\n");
696 fprintf (stderr
, "current insn:\n");
698 fprintf (stderr
, "next insn:\n");
706 if (insn_cnt1
!= insn_cnt2
)
708 fprintf (stderr
, "insn_cnt1 (%d) not equal to insn_cnt2 (%d).\n",
709 insn_cnt1
, insn_cnt2
);
721 if (GET_CODE (x
) == NOTE
722 && NOTE_LINE_NUMBER (x
) == NOTE_INSN_BASIC_BLOCK
)
736 if (GET_CODE (x
) == NOTE
737 && NOTE_LINE_NUMBER (x
) == NOTE_INSN_BASIC_BLOCK
)
745 /* Determine and record the relationships between basic blocks and
746 scopes in scope tree S. */
749 relate_bbs_with_scopes (s
)
753 int i
, bbi1
, bbi2
, bbs_spanned
;
756 for (p
= s
->inner
; p
; p
= p
->next
)
757 relate_bbs_with_scopes (p
);
762 /* If the begin and end notes are both inside the same basic block,
763 or if they are both outside of basic blocks, then we know immediately
764 how they are related. Otherwise, we need to poke around to make the
766 if (s
->bb_beg
!= s
->bb_end
)
768 if (s
->bb_beg
&& s
->bb_end
)
770 /* Both notes are in different bbs. This implies that all the
771 basic blocks spanned by the pair of notes are contained in
773 bbi1
= s
->bb_beg
->index
;
774 bbi2
= s
->bb_end
->index
;
777 else if (! s
->bb_beg
)
779 /* First note is outside of a bb. If the scope spans more than
780 one basic block, then they all are contained within this
781 scope. Otherwise, this scope is contained within the basic
783 bbnote
= get_next_bb_note (s
->note_beg
);
786 if (NOTE_BASIC_BLOCK (bbnote
) == s
->bb_end
)
789 s
->bb_beg
= NOTE_BASIC_BLOCK (bbnote
);
793 bbi1
= NOTE_BASIC_BLOCK (bbnote
)->index
;
794 bbi2
= s
->bb_end
->index
;
799 else /* ! s->bb_end */
801 /* Second note is outside of a bb. If the scope spans more than
802 one basic block, then they all are contained within this
803 scope. Otherwise, this scope is contained within the basic
805 bbnote
= get_prev_bb_note (s
->note_end
);
808 if (NOTE_BASIC_BLOCK (bbnote
) == s
->bb_beg
)
811 s
->bb_end
= NOTE_BASIC_BLOCK (bbnote
);
815 bbi1
= s
->bb_beg
->index
;
816 bbi2
= NOTE_BASIC_BLOCK (bbnote
)->index
;
825 /* Both notes are in the same bb, which implies the block
826 contains this scope. */
831 /* Both notes are outside of any bbs. This implies that all the
832 basic blocks spanned by the pair of notes are contained in
834 There is a degenerate case to consider. If the notes do not
835 span any basic blocks, then it is an empty scope that can
836 safely be deleted or ignored. Mark these with level = -1. */
838 x1
= get_next_bb_note (s
->note_beg
);
839 x2
= get_prev_bb_note (s
->note_end
);
847 bbi1
= NOTE_BASIC_BLOCK (x1
)->index
;
848 bbi2
= NOTE_BASIC_BLOCK (x2
)->index
;
855 /* If the scope spans one or more basic blocks, we record them. We
856 only record the bbs that are immediately contained within this
857 scope. Note that if a scope is contained within a bb, we can tell
858 by checking that bb_beg = bb_end and that they are non-null. */
864 for (i
= bbi1
; i
<= bbi2
; i
++)
865 if (! REORDER_BLOCK_SCOPE (BASIC_BLOCK (i
)))
868 s
->bbs
= xcalloc (s
->num_bbs
, sizeof (struct basic_block_def
));
869 for (i
= bbi1
; i
<= bbi2
; i
++)
871 basic_block curr_bb
= BASIC_BLOCK (i
);
872 if (! REORDER_BLOCK_SCOPE (curr_bb
))
874 s
->bbs
[j
++] = curr_bb
;
875 REORDER_BLOCK_SCOPE (curr_bb
) = s
;
884 /* Allocate and initialize a new scope structure with scope level LEVEL,
885 and record the NOTE beginning the scope. */
888 make_new_scope (level
, note
)
892 scope new_scope
= xcalloc (1, sizeof (struct scope_def
));
893 new_scope
->level
= level
;
894 new_scope
->note_beg
= note
;
895 new_scope
->note_end
= NULL
;
896 new_scope
->bb_beg
= NULL
;
897 new_scope
->bb_end
= NULL
;
898 new_scope
->inner
= NULL
;
899 new_scope
->inner_last
= NULL
;
900 new_scope
->outer
= NULL
;
901 new_scope
->next
= NULL
;
902 new_scope
->num_bbs
= 0;
903 new_scope
->bbs
= NULL
;
908 /* Build a forest representing the scope structure of the function.
909 Return a pointer to a structure describing the forest. */
912 build_scope_forest (forest
)
913 scope_forest_info
*forest
;
918 scope root
, curr_scope
;
920 forest
->num_trees
= 0;
921 forest
->trees
= NULL
;
926 for (x
= get_insns (); x
; x
= NEXT_INSN (x
))
928 if (bbi
< n_basic_blocks
&& x
== BASIC_BLOCK (bbi
)->head
)
929 curr_bb
= BASIC_BLOCK (bbi
);
931 if (GET_CODE (x
) == NOTE
)
933 if (NOTE_LINE_NUMBER (x
) == NOTE_INSN_BLOCK_BEG
)
941 new_scope
= make_new_scope (level
, x
);
942 new_scope
->outer
= curr_scope
;
943 new_scope
->next
= NULL
;
944 if (! curr_scope
->inner
)
946 curr_scope
->inner
= new_scope
;
947 curr_scope
->inner_last
= new_scope
;
951 curr_scope
->inner_last
->next
= new_scope
;
952 curr_scope
->inner_last
= new_scope
;
954 curr_scope
= curr_scope
->inner_last
;
958 int ntrees
= forest
->num_trees
;
960 curr_scope
= make_new_scope (level
, x
);
963 forest
->trees
= xcalloc (1, sizeof (scope
));
965 forest
->trees
= xrealloc (forest
->trees
,
966 sizeof (scope
) * (ntrees
+ 1));
967 forest
->trees
[forest
->num_trees
++] = root
;
969 curr_scope
->bb_beg
= curr_bb
;
971 else if (NOTE_LINE_NUMBER (x
) == NOTE_INSN_BLOCK_END
)
973 curr_scope
->bb_end
= curr_bb
;
974 curr_scope
->note_end
= x
;
976 curr_scope
= curr_scope
->outer
;
982 if (curr_bb
&& curr_bb
->end
== x
)
990 for (i
= 0; i
< forest
->num_trees
; i
++)
991 relate_bbs_with_scopes (forest
->trees
[i
]);
995 /* Remove all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes from
999 remove_scope_notes ()
1002 basic_block currbb
= NULL
;
1004 for (x
= get_insns (); x
; x
= next
)
1006 next
= NEXT_INSN (x
);
1007 if (GET_CODE (x
) == NOTE
1008 && NOTE_LINE_NUMBER (x
) == NOTE_INSN_BASIC_BLOCK
)
1009 currbb
= NOTE_BASIC_BLOCK (x
);
1011 if (GET_CODE (x
) == NOTE
1012 && (NOTE_LINE_NUMBER (x
) == NOTE_INSN_BLOCK_BEG
1013 || NOTE_LINE_NUMBER (x
) == NOTE_INSN_BLOCK_END
))
1015 /* Check if the scope note happens to be the end of a bb. */
1016 if (currbb
&& x
== currbb
->end
)
1017 currbb
->end
= PREV_INSN (x
);
1018 if (currbb
&& x
== currbb
->head
)
1023 NEXT_INSN (PREV_INSN (x
)) = next
;
1024 PREV_INSN (next
) = PREV_INSN (x
);
1026 NEXT_INSN (x
) = NULL
;
1027 PREV_INSN (x
) = NULL
;
1036 /* Insert scope note pairs for a contained scope tree S after insn IP. */
1038 insert_intra_1 (s
, ip
)
1044 if (NOTE_BLOCK (s
->note_beg
))
1046 *ip
= emit_note_after (NOTE_INSN_BLOCK_BEG
, *ip
);
1047 NOTE_BLOCK (*ip
) = NOTE_BLOCK (s
->note_beg
);
1050 for (p
= s
->inner
; p
; p
= p
->next
)
1051 insert_intra_1 (p
, ip
);
1053 if (NOTE_BLOCK (s
->note_beg
))
1055 *ip
= emit_note_after (NOTE_INSN_BLOCK_END
, *ip
);
1056 NOTE_BLOCK (*ip
) = NOTE_BLOCK (s
->note_end
);
1061 /* Insert NOTE_INSN_BLOCK_END notes and NOTE_INSN_BLOCK_BEG notes for
1062 scopes that are contained within BB. */
1065 insert_intra_bb_scope_notes (bb
)
1068 scope s
= REORDER_BLOCK_SCOPE (bb
);
1076 if (GET_CODE (ip
) == CODE_LABEL
)
1077 ip
= NEXT_INSN (ip
);
1079 for (p
= s
->inner
; p
; p
= p
->next
)
1081 if (p
->bb_beg
!= NULL
&& p
->bb_beg
== p
->bb_end
&& p
->bb_beg
== bb
)
1082 insert_intra_1 (p
, &ip
);
1087 /* Given two consecutive basic blocks BB1 and BB2 with different scopes,
1088 insert NOTE_INSN_BLOCK_END notes after BB1 and NOTE_INSN_BLOCK_BEG
1089 notes before BB2 such that the notes are correctly balanced. If BB1 or
1090 BB2 is NULL, we are inserting scope notes for the first and last basic
1091 blocks, respectively. */
1094 insert_inter_bb_scope_notes (bb1
, bb2
)
1101 /* It is possible that a basic block is not contained in any scope.
1102 In that case, we either open or close a scope but not both. */
1105 scope s1
= REORDER_BLOCK_SCOPE (bb1
);
1106 scope s2
= REORDER_BLOCK_SCOPE (bb2
);
1115 /* Find common ancestor scope. */
1118 scope s1
= REORDER_BLOCK_SCOPE (bb1
);
1119 scope s2
= REORDER_BLOCK_SCOPE (bb2
);
1124 if (s1
->level
> s2
->level
)
1126 else if (s2
->level
> s1
->level
)
1142 scope s
= REORDER_BLOCK_SCOPE (bb1
);
1143 ip
= REORDER_BLOCK_EFF_END (bb1
);
1146 if (NOTE_BLOCK (s
->note_beg
))
1148 ip
= emit_note_after (NOTE_INSN_BLOCK_END
, ip
);
1149 NOTE_BLOCK (ip
) = NOTE_BLOCK (s
->note_end
);
1158 scope s
= REORDER_BLOCK_SCOPE (bb2
);
1162 if (NOTE_BLOCK (s
->note_beg
))
1164 ip
= emit_note_before (NOTE_INSN_BLOCK_BEG
, ip
);
1165 NOTE_BLOCK (ip
) = NOTE_BLOCK (s
->note_beg
);
1173 /* Rebuild all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes based
1174 on the scope forest and the newly reordered basic blocks. */
1177 rebuild_scope_notes (forest
)
1178 scope_forest_info
*forest
;
1182 if (forest
->num_trees
== 0)
1185 /* Start by opening the scopes before the first basic block. */
1186 insert_inter_bb_scope_notes (NULL
, BASIC_BLOCK (0));
1188 /* Then, open and close scopes as needed between blocks. */
1189 for (i
= 0; i
< n_basic_blocks
- 1; i
++)
1191 basic_block bb1
= BASIC_BLOCK (i
);
1192 basic_block bb2
= BASIC_BLOCK (i
+ 1);
1193 if (REORDER_BLOCK_SCOPE (bb1
) != REORDER_BLOCK_SCOPE (bb2
))
1194 insert_inter_bb_scope_notes (bb1
, bb2
);
1195 insert_intra_bb_scope_notes (bb1
);
1198 /* Finally, close the scopes after the last basic block. */
1199 insert_inter_bb_scope_notes (BASIC_BLOCK (n_basic_blocks
- 1), NULL
);
1200 insert_intra_bb_scope_notes (BASIC_BLOCK (n_basic_blocks
- 1));
1204 /* Free the storage associated with the scope tree at S. */
1207 free_scope_forest_1 (s
)
1212 for (p
= s
->inner
; p
; p
= next
)
1215 free_scope_forest_1 (p
);
1224 /* Free the storage associated with the scope forest. */
1227 free_scope_forest (forest
)
1228 scope_forest_info
*forest
;
1231 for (i
= 0; i
< forest
->num_trees
; i
++)
1232 free_scope_forest_1 (forest
->trees
[i
]);
1236 /* Visualize the scope forest. */
1239 dump_scope_forest (forest
)
1240 scope_forest_info
*forest
;
1242 if (forest
->num_trees
== 0)
1243 fprintf (stderr
, "\n< Empty scope forest >\n");
1247 fprintf (stderr
, "\n< Scope forest >\n");
1248 for (i
= 0; i
< forest
->num_trees
; i
++)
1249 dump_scope_forest_1 (forest
->trees
[i
], 0);
1254 /* Recursive portion of dump_scope_forest. */
1257 dump_scope_forest_1 (s
, indent
)
1264 if (s
->bb_beg
!= NULL
&& s
->bb_beg
== s
->bb_end
1265 && REORDER_BLOCK_SCOPE (s
->bb_beg
)
1266 && REORDER_BLOCK_SCOPE (s
->bb_beg
)->level
+ 1 == s
->level
)
1268 fprintf (stderr
, "%*s", indent
, "");
1269 fprintf (stderr
, "BB%d:\n", s
->bb_beg
->index
);
1272 fprintf (stderr
, "%*s", indent
, "");
1273 fprintf (stderr
, "{ level %d (block %p)\n", s
->level
,
1274 NOTE_BLOCK (s
->note_beg
));
1276 fprintf (stderr
, "%*s%s", indent
, "", "bbs:");
1277 for (i
= 0; i
< s
->num_bbs
; i
++)
1278 fprintf (stderr
, " %d", s
->bbs
[i
]->index
);
1279 fprintf (stderr
, "\n");
1281 for (p
= s
->inner
; p
; p
= p
->next
)
1282 dump_scope_forest_1 (p
, indent
+ 2);
1284 fprintf (stderr
, "%*s", indent
, "");
1285 fprintf (stderr
, "}\n");
1289 /* Reorder basic blocks. */
1292 reorder_basic_blocks ()
1295 struct loops loops_info
;
1297 scope_forest_info forest
;
1299 if (profile_arc_flag
)
1302 if (n_basic_blocks
<= 1)
1305 /* Exception edges are not currently handled. */
1306 for (i
= 0; i
< n_basic_blocks
; i
++)
1310 for (e
= BASIC_BLOCK (i
)->succ
; e
&& ! (e
->flags
& EDGE_EH
);
1314 if (e
&& (e
->flags
& EDGE_EH
))
1320 /* Find natural loops using the CFG. */
1321 num_loops
= flow_loops_find (&loops_info
);
1323 /* Dump loop information. */
1324 flow_loops_dump (&loops_info
, rtl_dump_file
, 0);
1326 reorder_last_visited
= BASIC_BLOCK (0);
1328 for (i
= 0; i
< n_basic_blocks
; i
++)
1330 basic_block bbi
= BASIC_BLOCK (i
);
1331 bbi
->aux
= xcalloc (1, sizeof (struct reorder_block_def
));
1332 *((struct reorder_block_def
*)bbi
->aux
) = rbd_init
;
1335 build_scope_forest (&forest
);
1336 remove_scope_notes ();
1338 for (i
= 0; i
< n_basic_blocks
; i
++)
1340 basic_block bbi
= BASIC_BLOCK (i
);
1341 REORDER_BLOCK_EFF_END (bbi
) = skip_insns_after_block (bbi
);
1343 REORDER_BLOCK_EFF_HEAD (bbi
) = get_insns ();
1346 rtx prev_eff_end
= REORDER_BLOCK_EFF_END (BASIC_BLOCK (i
- 1));
1347 REORDER_BLOCK_EFF_HEAD (bbi
) = NEXT_INSN (prev_eff_end
);
1351 /* If we've not got epilogue in RTL, we must fallthru to the exit.
1352 Force the last block to be at the end. */
1353 /* ??? Some ABIs (e.g. MIPS) require the return insn to be at the
1354 end of the function for stack unwinding purposes. */
1356 #ifndef HAVE_epilogue
1357 #define HAVE_epilogue 0
1360 if (! HAVE_epilogue
)
1362 basic_block last
= BASIC_BLOCK (n_basic_blocks
- 1);
1363 REORDER_BLOCK_INDEX (last
) = n_basic_blocks
- 1;
1364 REORDER_BLOCK_FLAGS (last
) |= REORDER_BLOCK_VISITED
;
1367 make_reorder_chain (BASIC_BLOCK (0));
1369 fixup_reorder_chain ();
1371 #ifdef ENABLE_CHECKING
1372 verify_insn_chain ();
1375 /* Put basic_block_info in new order. */
1376 for (i
= 0; i
< n_basic_blocks
- 1; i
++)
1378 for (j
= i
; i
!= REORDER_BLOCK_INDEX (BASIC_BLOCK (j
)); j
++)
1381 if (REORDER_BLOCK_INDEX (BASIC_BLOCK (j
)) == i
1386 int rbi
= REORDER_BLOCK_INDEX (BASIC_BLOCK (j
));
1388 temprbi
= BASIC_BLOCK (rbi
)->index
;
1389 BASIC_BLOCK (rbi
)->index
= BASIC_BLOCK (j
)->index
;
1390 BASIC_BLOCK (j
)->index
= temprbi
;
1391 tempbb
= BASIC_BLOCK (rbi
);
1392 BASIC_BLOCK (rbi
) = BASIC_BLOCK (j
);
1393 BASIC_BLOCK (j
) = tempbb
;
1397 rebuild_scope_notes (&forest
);
1398 free_scope_forest (&forest
);
1401 #ifdef ENABLE_CHECKING
1402 verify_flow_info ();
1405 for (i
= 0; i
< n_basic_blocks
; i
++)
1406 free (BASIC_BLOCK (i
)->aux
);
1408 /* Free loop information. */
1409 flow_loops_free (&loops_info
);