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
;
113 } *reorder_block_def
;
115 static struct reorder_block_def rbd_init
124 NULL_RTX
, /* eff_head */
125 NULL_RTX
, /* eff_end */
130 #define REORDER_BLOCK_HEAD 0x1
131 #define REORDER_BLOCK_VISITED 0x2
133 #define REORDER_BLOCK_FLAGS(bb) \
134 ((reorder_block_def) (bb)->aux)->flags
136 #define REORDER_BLOCK_INDEX(bb) \
137 ((reorder_block_def) (bb)->aux)->index
139 #define REORDER_BLOCK_ADD_JUMP(bb) \
140 ((reorder_block_def) (bb)->aux)->add_jump
142 #define REORDER_BLOCK_SUCC(bb) \
143 ((reorder_block_def) (bb)->aux)->succ
145 #define REORDER_BLOCK_OLD_END(bb) \
146 ((reorder_block_def) (bb)->aux)->end
148 #define REORDER_BLOCK_BEGIN(bb) \
149 ((reorder_block_def) (bb)->aux)->block_begin
151 #define REORDER_BLOCK_END(bb) \
152 ((reorder_block_def) (bb)->aux)->block_end
154 #define REORDER_BLOCK_EFF_HEAD(bb) \
155 ((reorder_block_def) (bb)->aux)->eff_head
157 #define REORDER_BLOCK_EFF_END(bb) \
158 ((reorder_block_def) (bb)->aux)->eff_end
160 #define REORDER_BLOCK_SCOPE(bb) \
161 ((reorder_block_def) (bb)->aux)->scope
164 static int reorder_index
;
165 static basic_block reorder_last_visited
;
167 enum reorder_skip_type
{REORDER_SKIP_BEFORE
, REORDER_SKIP_AFTER
,
168 REORDER_SKIP_BLOCK_END
};
171 /* Local function prototypes. */
172 static rtx skip_insns_between_block
PARAMS ((basic_block
,
173 enum reorder_skip_type
));
174 static basic_block get_common_dest
PARAMS ((basic_block
, basic_block
));
175 static basic_block chain_reorder_blocks
PARAMS ((edge
, basic_block
));
176 static void make_reorder_chain
PARAMS ((basic_block
));
177 static void fixup_reorder_chain
PARAMS ((void));
178 #ifdef ENABLE_CHECKING
179 static void verify_insn_chain
PARAMS ((void));
181 static void relate_bbs_with_scopes
PARAMS ((scope
));
182 static scope make_new_scope
PARAMS ((int, rtx
));
183 static void build_scope_forest
PARAMS ((scope_forest_info
*));
184 static void remove_scope_notes
PARAMS ((void));
185 static void insert_intra_1
PARAMS ((scope
, rtx
*));
186 static void insert_intra_bb_scope_notes
PARAMS ((basic_block
));
187 static void insert_inter_bb_scope_notes
PARAMS ((basic_block
, basic_block
));
188 static void rebuild_scope_notes
PARAMS ((scope_forest_info
*));
189 static void free_scope_forest_1
PARAMS ((scope
));
190 static void free_scope_forest
PARAMS ((scope_forest_info
*));
191 void dump_scope_forest
PARAMS ((scope_forest_info
*));
192 static void dump_scope_forest_1
PARAMS ((scope
, int));
194 /* Skip over insns BEFORE or AFTER BB which are typically associated with
198 skip_insns_between_block (bb
, skip_type
)
200 enum reorder_skip_type skip_type
;
204 if (skip_type
== REORDER_SKIP_BEFORE
)
206 if (bb
== ENTRY_BLOCK_PTR
)
209 last_insn
= bb
->head
;
210 for (insn
= PREV_INSN (bb
->head
);
211 insn
&& insn
!= BASIC_BLOCK (bb
->index
- 1)->end
;
212 last_insn
= insn
, insn
= PREV_INSN (insn
))
214 if (NEXT_INSN (insn
) != last_insn
)
217 if (GET_CODE (insn
) == NOTE
218 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_LOOP_END
219 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_BASIC_BLOCK
220 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_BLOCK_END
)
230 if (bb
== EXIT_BLOCK_PTR
)
233 for (insn
= NEXT_INSN (bb
->end
);
235 last_insn
= insn
, insn
= NEXT_INSN (insn
))
237 if (bb
->index
+ 1 != n_basic_blocks
238 && insn
== BASIC_BLOCK (bb
->index
+ 1)->head
)
241 if (GET_CODE (insn
) == BARRIER
242 || GET_CODE (insn
) == JUMP_INSN
243 || (GET_CODE (insn
) == NOTE
244 && (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_END
245 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_BLOCK_END
)))
248 if (GET_CODE (insn
) == CODE_LABEL
249 && GET_CODE (NEXT_INSN (insn
)) == JUMP_INSN
250 && (GET_CODE (PATTERN (NEXT_INSN (insn
))) == ADDR_VEC
252 (NEXT_INSN (insn
))) == ADDR_DIFF_VEC
))
254 insn
= NEXT_INSN (insn
);
258 /* Skip to next non-deleted insn. */
259 if (GET_CODE (insn
) == NOTE
260 && (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_DELETED
261 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_DELETED_LABEL
))
267 if (skip_type
== REORDER_SKIP_BLOCK_END
)
269 int found_block_end
= 0;
271 for (; insn
; last_insn
= insn
, insn
= NEXT_INSN (insn
))
273 if (bb
->index
+ 1 != n_basic_blocks
274 && insn
== BASIC_BLOCK (bb
->index
+ 1)->head
)
277 if (GET_CODE (insn
) == NOTE
278 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_BLOCK_END
)
284 if (GET_CODE (insn
) == NOTE
285 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_DELETED
)
288 if (GET_CODE (insn
) == NOTE
289 && NOTE_LINE_NUMBER (insn
) >= 0
291 && GET_CODE (NEXT_INSN (insn
)) == NOTE
292 && (NOTE_LINE_NUMBER (NEXT_INSN (insn
))
293 == NOTE_INSN_BLOCK_END
))
298 if (! found_block_end
)
307 /* Return common destination for blocks BB0 and BB1. */
310 get_common_dest (bb0
, bb1
)
311 basic_block bb0
, bb1
;
315 for (e0
= bb0
->succ
; e0
; e0
= e0
->succ_next
)
317 for (e1
= bb1
->succ
; e1
; e1
= e1
->succ_next
)
319 if (e0
->dest
== e1
->dest
)
329 /* Move the destination block for edge E after chain end block CEB
330 Adding jumps and labels is deferred until fixup_reorder_chain. */
333 chain_reorder_blocks (e
, ceb
)
337 basic_block sb
= e
->src
;
338 basic_block db
= e
->dest
;
339 rtx cebe_insn
, cebbe_insn
, dbh_insn
, dbe_insn
;
342 enum cond_types
{NO_COND
, PREDICT_THEN_WITH_ELSE
, PREDICT_ELSE
,
343 PREDICT_THEN_NO_ELSE
, PREDICT_NOT_THEN_NO_ELSE
};
344 enum cond_types cond_type
;
345 enum cond_block_types
{NO_COND_BLOCK
, THEN_BLOCK
, ELSE_BLOCK
,
347 enum cond_block_types cond_block_type
;
350 fprintf (rtl_dump_file
,
351 "Edge from basic block %d to basic block %d last visited %d\n",
352 sb
->index
, db
->index
, ceb
->index
);
354 dbh_insn
= REORDER_BLOCK_EFF_HEAD (db
);
355 cebe_insn
= REORDER_BLOCK_EFF_END (ceb
);
356 cebbe_insn
= skip_insns_between_block (ceb
, REORDER_SKIP_BLOCK_END
);
359 int block_begins
= 0;
362 for (insn
= dbh_insn
; insn
&& insn
!= db
->end
; insn
= NEXT_INSN (insn
))
364 if (GET_CODE (insn
) == NOTE
365 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_BLOCK_BEG
)
371 REORDER_BLOCK_BEGIN (sb
) = block_begins
;
379 for (insn
= cebe_insn
; insn
; insn
= NEXT_INSN (insn
))
381 if (PREV_INSN (insn
) == cebbe_insn
)
383 if (GET_CODE (insn
) == NOTE
384 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_BLOCK_END
)
390 REORDER_BLOCK_END (ceb
) = block_ends
;
393 /* Blocks are in original order. */
394 if (sb
->index
== ceb
->index
395 && ceb
->index
+ 1 == db
->index
&& NEXT_INSN (cebe_insn
))
398 /* Get the type of block and type of condition. */
400 cond_block_type
= NO_COND_BLOCK
;
401 if (GET_CODE (sb
->end
) == JUMP_INSN
&& ! simplejump_p (sb
->end
)
402 && condjump_p (sb
->end
))
404 if (e
->flags
& EDGE_FALLTHRU
)
405 cond_block_type
= THEN_BLOCK
;
406 else if (get_common_dest (sb
->succ
->dest
, sb
))
407 cond_block_type
= NO_ELSE_BLOCK
;
409 cond_block_type
= ELSE_BLOCK
;
411 if (sb
->succ
->succ_next
412 && get_common_dest (sb
->succ
->dest
, sb
))
414 if (cond_block_type
== THEN_BLOCK
)
416 if (! (REORDER_BLOCK_FLAGS (sb
->succ
->succ_next
->dest
)
417 & REORDER_BLOCK_VISITED
))
418 cond_type
= PREDICT_THEN_NO_ELSE
;
420 cond_type
= PREDICT_NOT_THEN_NO_ELSE
;
422 else if (cond_block_type
== NO_ELSE_BLOCK
)
424 if (! (REORDER_BLOCK_FLAGS (sb
->succ
->dest
)
425 & REORDER_BLOCK_VISITED
))
426 cond_type
= PREDICT_NOT_THEN_NO_ELSE
;
428 cond_type
= PREDICT_THEN_NO_ELSE
;
433 if (cond_block_type
== THEN_BLOCK
)
435 if (! (REORDER_BLOCK_FLAGS (sb
->succ
->succ_next
->dest
)
436 & REORDER_BLOCK_VISITED
))
437 cond_type
= PREDICT_THEN_WITH_ELSE
;
439 cond_type
= PREDICT_ELSE
;
441 else if (cond_block_type
== ELSE_BLOCK
442 && sb
->succ
->dest
!= EXIT_BLOCK_PTR
)
444 if (! (REORDER_BLOCK_FLAGS (sb
->succ
->dest
)
445 & REORDER_BLOCK_VISITED
))
446 cond_type
= PREDICT_ELSE
;
448 cond_type
= PREDICT_THEN_WITH_ELSE
;
455 static const char * cond_type_str
[] = {"not cond jump", "predict then",
457 "predict then w/o else",
458 "predict not then w/o else"};
459 static const char * cond_block_type_str
[] = {"not then or else block",
462 "then w/o else block"};
464 fprintf (rtl_dump_file
, " %s (looking at %s)\n",
465 cond_type_str
[(int)cond_type
],
466 cond_block_type_str
[(int)cond_block_type
]);
469 /* Reflect that then block will move and we'll jump to it. */
470 if (cond_block_type
!= THEN_BLOCK
471 && (cond_type
== PREDICT_ELSE
472 || cond_type
== PREDICT_NOT_THEN_NO_ELSE
))
475 fprintf (rtl_dump_file
,
476 " then jump from block %d to block %d\n",
477 sb
->index
, sb
->succ
->dest
->index
);
479 /* Jump to reordered then block. */
480 REORDER_BLOCK_ADD_JUMP (sb
) = sb
->succ
->dest
;
483 /* Reflect that then block will jump back when we have no else. */
484 if (cond_block_type
!= THEN_BLOCK
485 && cond_type
== PREDICT_NOT_THEN_NO_ELSE
)
487 for (ee
= sb
->succ
->dest
->succ
;
488 ee
&& ! (ee
->flags
& EDGE_FALLTHRU
);
492 if (ee
&& ! (GET_CODE (sb
->succ
->dest
->end
) == JUMP_INSN
493 && ! simplejump_p (sb
->succ
->dest
->end
)))
495 REORDER_BLOCK_ADD_JUMP (sb
->succ
->dest
) = ee
->dest
;
499 /* Reflect that else block will jump back. */
500 if (cond_block_type
== ELSE_BLOCK
501 && (cond_type
== PREDICT_THEN_WITH_ELSE
|| cond_type
== PREDICT_ELSE
))
506 && last_edge
->dest
!= EXIT_BLOCK_PTR
507 && GET_CODE (last_edge
->dest
->head
) == CODE_LABEL
508 && ! (GET_CODE (db
->end
) == JUMP_INSN
))
511 fprintf (rtl_dump_file
,
512 " else jump from block %d to block %d\n",
513 db
->index
, last_edge
->dest
->index
);
515 REORDER_BLOCK_ADD_JUMP (db
) = last_edge
->dest
;
519 /* This block's successor has already been reordered. This can happen
520 when we reorder a chain starting at a then or else. */
521 for (last_edge
= db
->succ
;
522 last_edge
&& ! (last_edge
->flags
& EDGE_FALLTHRU
);
523 last_edge
= last_edge
->succ_next
)
527 && last_edge
->dest
!= EXIT_BLOCK_PTR
528 && (REORDER_BLOCK_FLAGS (last_edge
->dest
)
529 & REORDER_BLOCK_VISITED
))
532 fprintf (rtl_dump_file
,
533 " end of chain jump from block %d to block %d\n",
534 db
->index
, last_edge
->dest
->index
);
536 REORDER_BLOCK_ADD_JUMP (db
) = last_edge
->dest
;
539 dbh_insn
= REORDER_BLOCK_EFF_HEAD (db
);
540 cebe_insn
= REORDER_BLOCK_EFF_END (ceb
);
541 dbe_insn
= REORDER_BLOCK_EFF_END (db
);
543 /* Leave behind any lexical block markers. */
544 if (0 && debug_info_level
> DINFO_LEVEL_TERSE
545 && ceb
->index
+ 1 < db
->index
)
547 rtx insn
, last_insn
= get_last_insn ();
548 insn
= NEXT_INSN (ceb
->end
);
550 insn
= REORDER_BLOCK_OLD_END (ceb
);
552 if (NEXT_INSN (cebe_insn
) == 0)
553 set_last_insn (cebe_insn
);
554 for (; insn
&& insn
!= db
->head
/*dbh_insn*/;
555 insn
= NEXT_INSN (insn
))
557 if (GET_CODE (insn
) == NOTE
558 && (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_BLOCK_BEG
))
560 cebe_insn
= emit_note_after (NOTE_INSN_BLOCK_BEG
, cebe_insn
);
563 if (GET_CODE (insn
) == NOTE
564 && (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_BLOCK_END
))
566 cebe_insn
= emit_note_after (NOTE_INSN_BLOCK_END
, cebe_insn
);
570 set_last_insn (last_insn
);
573 /* Rechain predicted block. */
574 NEXT_INSN (cebe_insn
) = dbh_insn
;
575 PREV_INSN (dbh_insn
) = cebe_insn
;
577 REORDER_BLOCK_OLD_END (db
) = NEXT_INSN (dbe_insn
);
578 if (db
->index
!= n_basic_blocks
- 1)
579 NEXT_INSN (dbe_insn
) = 0;
585 /* Reorder blocks starting at block BB. */
588 make_reorder_chain (bb
)
592 basic_block visited_edge
= NULL
;
596 if (bb
== EXIT_BLOCK_PTR
)
599 /* Find the most probable block. */
602 if (GET_CODE (block_end
) == JUMP_INSN
&& condjump_p (block_end
))
604 rtx note
= find_reg_note (block_end
, REG_BR_PROB
, 0);
607 probability
= INTVAL (XEXP (note
, 0));
611 if (probability
>= REG_BR_PROB_BASE
/ 2)
612 e
= bb
->succ
->succ_next
;
615 /* Add chosen successor to chain and recurse on it. */
616 if (e
&& e
->dest
!= EXIT_BLOCK_PTR
618 && (! (REORDER_BLOCK_FLAGS (e
->dest
) & REORDER_BLOCK_VISITED
)
619 || (REORDER_BLOCK_FLAGS (e
->dest
) == REORDER_BLOCK_HEAD
)))
621 if (! (REORDER_BLOCK_FLAGS (bb
) & REORDER_BLOCK_VISITED
))
623 REORDER_BLOCK_FLAGS (bb
) |= REORDER_BLOCK_HEAD
;
624 REORDER_BLOCK_INDEX (bb
) = reorder_index
++;
625 REORDER_BLOCK_FLAGS (bb
) |= REORDER_BLOCK_VISITED
;
628 if (REORDER_BLOCK_FLAGS (e
->dest
) & REORDER_BLOCK_VISITED
)
629 REORDER_BLOCK_FLAGS (e
->dest
) &= ~REORDER_BLOCK_HEAD
;
631 REORDER_BLOCK_SUCC (bb
) = e
;
633 visited_edge
= e
->dest
;
635 reorder_last_visited
= chain_reorder_blocks (e
, bb
);
638 && ! (REORDER_BLOCK_FLAGS (e
->dest
)
639 & REORDER_BLOCK_VISITED
))
640 make_reorder_chain (e
->dest
);
644 if (! (REORDER_BLOCK_FLAGS (bb
) & REORDER_BLOCK_VISITED
))
646 REORDER_BLOCK_INDEX (bb
) = reorder_index
++;
647 REORDER_BLOCK_FLAGS (bb
) |= REORDER_BLOCK_VISITED
;
651 /* Recurse on the successors. */
652 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
654 if (e
->dest
&& e
->dest
== EXIT_BLOCK_PTR
)
659 && e
->dest
!= visited_edge
660 && ! (REORDER_BLOCK_FLAGS (e
->dest
)
661 & REORDER_BLOCK_VISITED
))
664 = chain_reorder_blocks (e
, reorder_last_visited
);
665 make_reorder_chain (e
->dest
);
671 /* Fixup jumps and labels after reordering basic blocks. */
674 fixup_reorder_chain ()
678 int orig_num_blocks
= n_basic_blocks
;
680 /* Set the new last insn. */
684 for (j
= 0; j
< n_basic_blocks
; j
++)
686 int val
= REORDER_BLOCK_INDEX (BASIC_BLOCK (j
));
693 insn
= REORDER_BLOCK_EFF_END (BASIC_BLOCK (max_index
));
694 NEXT_INSN (insn
) = NULL_RTX
;
695 set_last_insn (insn
);
698 /* Add jumps and labels to fixup blocks. */
699 for (i
= 0; i
< orig_num_blocks
; i
++)
702 basic_block bbi
= BASIC_BLOCK (i
);
703 if (REORDER_BLOCK_ADD_JUMP (bbi
))
705 rtx label_insn
, jump_insn
, barrier_insn
;
707 if (GET_CODE (REORDER_BLOCK_ADD_JUMP (bbi
)->head
) == CODE_LABEL
)
708 label_insn
= REORDER_BLOCK_ADD_JUMP (bbi
)->head
;
711 rtx new_label
= gen_label_rtx ();
712 label_insn
= emit_label_before (new_label
,
713 REORDER_BLOCK_ADD_JUMP (bbi
)->head
);
714 REORDER_BLOCK_ADD_JUMP (bbi
)->head
= label_insn
;
717 if (GET_CODE (bbi
->end
) != JUMP_INSN
)
719 jump_insn
= emit_jump_insn_after (gen_jump (label_insn
),
721 bbi
->end
= jump_insn
;
726 jump_insn
= emit_jump_insn_after (gen_jump (label_insn
),
727 REORDER_BLOCK_EFF_END (bbi
));
731 JUMP_LABEL (jump_insn
) = label_insn
;
732 ++LABEL_NUSES (label_insn
);
733 barrier_insn
= emit_barrier_after (jump_insn
);
735 /* Add block for jump. Typically this is when a then is not
736 predicted and we are jumping to the moved then block. */
741 VARRAY_GROW (basic_block_info
, ++n_basic_blocks
);
742 create_basic_block (n_basic_blocks
- 1, jump_insn
,
744 nb
= BASIC_BLOCK (n_basic_blocks
- 1);
745 nb
->global_live_at_start
746 = OBSTACK_ALLOC_REG_SET (function_obstack
);
747 nb
->global_live_at_end
748 = OBSTACK_ALLOC_REG_SET (function_obstack
);
750 COPY_REG_SET (nb
->global_live_at_start
,
751 bbi
->global_live_at_start
);
752 COPY_REG_SET (nb
->global_live_at_end
,
753 bbi
->global_live_at_start
);
754 BASIC_BLOCK (nb
->index
)->local_set
= 0;
756 nb
->aux
= xcalloc (1, sizeof (struct reorder_block_def
));
757 REORDER_BLOCK_INDEX (nb
) = REORDER_BLOCK_INDEX (bbi
) + 1;
758 /* Relink to new block. */
759 nb
->succ
= bbi
->succ
;
762 make_edge (NULL
, bbi
, nb
, 0);
764 = bbi
->succ
->succ_next
->succ_next
;
765 nb
->succ
->succ_next
= 0;
766 /* Fix reorder block index to reflect new block. */
767 for (j
= 0; j
< n_basic_blocks
- 1; j
++)
769 basic_block bbj
= BASIC_BLOCK (j
);
770 if (REORDER_BLOCK_INDEX (bbj
)
771 >= REORDER_BLOCK_INDEX (bbi
) + 1)
772 REORDER_BLOCK_INDEX (bbj
)++;
774 REORDER_BLOCK_SCOPE (nb
) = REORDER_BLOCK_SCOPE (bbi
);
775 REORDER_BLOCK_EFF_HEAD (nb
) = nb
->head
;
776 REORDER_BLOCK_EFF_END (nb
) = barrier_insn
;
779 REORDER_BLOCK_EFF_END (bbi
) = barrier_insn
;
785 /* Perform sanity checks on the insn chain.
786 1. Check that next/prev pointers are consistent in both the forward and
788 2. Count insns in chain, going both directions, and check if equal.
789 3. Check that get_last_insn () returns the actual end of chain. */
790 #ifdef ENABLE_CHECKING
802 for (x
= get_insns (); x
; x
= NEXT_INSN (x
))
804 if (PREV_INSN (x
) != prevx
)
806 fprintf (stderr
, "Forward traversal: insn chain corrupt.\n");
807 fprintf (stderr
, "previous insn:\n");
809 fprintf (stderr
, "current insn:\n");
817 if (prevx
!= get_last_insn ())
819 fprintf (stderr
, "last_insn corrupt.\n");
825 for (x
= get_last_insn (); x
; x
= PREV_INSN (x
))
827 if (NEXT_INSN (x
) != nextx
)
829 fprintf (stderr
, "Reverse traversal: insn chain corrupt.\n");
830 fprintf (stderr
, "current insn:\n");
832 fprintf (stderr
, "next insn:\n");
840 if (insn_cnt1
!= insn_cnt2
)
842 fprintf (stderr
, "insn_cnt1 (%d) not equal to insn_cnt2 (%d).\n",
843 insn_cnt1
, insn_cnt2
);
855 if (GET_CODE (x
) == NOTE
856 && NOTE_LINE_NUMBER (x
) == NOTE_INSN_BASIC_BLOCK
)
870 if (GET_CODE (x
) == NOTE
871 && NOTE_LINE_NUMBER (x
) == NOTE_INSN_BASIC_BLOCK
)
879 /* Determine and record the relationships between basic blocks and
880 scopes in scope tree S. */
883 relate_bbs_with_scopes (s
)
887 int i
, bbi1
, bbi2
, bbs_spanned
;
890 for (p
= s
->inner
; p
; p
= p
->next
)
891 relate_bbs_with_scopes (p
);
896 /* If the begin and end notes are both inside the same basic block,
897 or if they are both outside of basic blocks, then we know immediately
898 how they are related. Otherwise, we need to poke around to make the
900 if (s
->bb_beg
!= s
->bb_end
)
902 if (s
->bb_beg
&& s
->bb_end
)
904 /* Both notes are in different bbs. This implies that all the
905 basic blocks spanned by the pair of notes are contained in
907 bbi1
= s
->bb_beg
->index
;
908 bbi2
= s
->bb_end
->index
;
911 else if (! s
->bb_beg
)
913 /* First note is outside of a bb. If the scope spans more than
914 one basic block, then they all are contained within this
915 scope. Otherwise, this scope is contained within the basic
917 bbnote
= get_next_bb_note (s
->note_beg
);
920 if (NOTE_BASIC_BLOCK (bbnote
) == s
->bb_end
)
923 s
->bb_beg
= NOTE_BASIC_BLOCK (bbnote
);
927 bbi1
= NOTE_BASIC_BLOCK (bbnote
)->index
;
928 bbi2
= s
->bb_end
->index
;
933 else /* ! s->bb_end */
935 /* Second note is outside of a bb. If the scope spans more than
936 one basic block, then they all are contained within this
937 scope. Otherwise, this scope is contained within the basic
939 bbnote
= get_prev_bb_note (s
->note_end
);
942 if (NOTE_BASIC_BLOCK (bbnote
) == s
->bb_beg
)
945 s
->bb_end
= NOTE_BASIC_BLOCK (bbnote
);
949 bbi1
= s
->bb_beg
->index
;
950 bbi2
= NOTE_BASIC_BLOCK (bbnote
)->index
;
959 /* Both notes are in the same bb, which implies the block
960 contains this scope. */
965 /* Both notes are outside of any bbs. This implies that all the
966 basic blocks spanned by the pair of notes are contained in
968 There is a degenerate case to consider. If the notes do not
969 span any basic blocks, then it is an empty scope that can
970 safely be deleted or ignored. Mark these with level = -1. */
972 x1
= get_next_bb_note (s
->note_beg
);
973 x2
= get_prev_bb_note (s
->note_end
);
981 bbi1
= NOTE_BASIC_BLOCK (x1
)->index
;
982 bbi2
= NOTE_BASIC_BLOCK (x2
)->index
;
989 /* If the scope spans one or more basic blocks, we record them. We
990 only record the bbs that are immediately contained within this
991 scope. Note that if a scope is contained within a bb, we can tell
992 by checking that bb_beg = bb_end and that they are non-null. */
998 for (i
= bbi1
; i
<= bbi2
; i
++)
999 if (! REORDER_BLOCK_SCOPE (BASIC_BLOCK (i
)))
1002 s
->bbs
= xcalloc (s
->num_bbs
, sizeof (struct basic_block_def
));
1003 for (i
= bbi1
; i
<= bbi2
; i
++)
1005 basic_block curr_bb
= BASIC_BLOCK (i
);
1006 if (! REORDER_BLOCK_SCOPE (curr_bb
))
1008 s
->bbs
[j
++] = curr_bb
;
1009 REORDER_BLOCK_SCOPE (curr_bb
) = s
;
1018 /* Allocate and initialize a new scope structure with scope level LEVEL,
1019 and record the NOTE beginning the scope. */
1022 make_new_scope (level
, note
)
1026 scope new_scope
= xcalloc (1, sizeof (struct scope_def
));
1027 new_scope
->level
= level
;
1028 new_scope
->note_beg
= note
;
1029 new_scope
->note_end
= NULL
;
1030 new_scope
->bb_beg
= NULL
;
1031 new_scope
->bb_end
= NULL
;
1032 new_scope
->inner
= NULL
;
1033 new_scope
->inner_last
= NULL
;
1034 new_scope
->outer
= NULL
;
1035 new_scope
->next
= NULL
;
1036 new_scope
->num_bbs
= 0;
1037 new_scope
->bbs
= NULL
;
1042 /* Build a forest representing the scope structure of the function.
1043 Return a pointer to a structure describing the forest. */
1046 build_scope_forest (forest
)
1047 scope_forest_info
*forest
;
1051 basic_block curr_bb
;
1052 scope root
, curr_scope
;
1054 forest
->num_trees
= 0;
1055 forest
->trees
= NULL
;
1060 for (x
= get_insns (); x
; x
= NEXT_INSN (x
))
1062 if (bbi
< n_basic_blocks
&& x
== BASIC_BLOCK (bbi
)->head
)
1063 curr_bb
= BASIC_BLOCK (bbi
);
1065 if (GET_CODE (x
) == NOTE
)
1067 if (NOTE_LINE_NUMBER (x
) == NOTE_INSN_BLOCK_BEG
)
1075 new_scope
= make_new_scope (level
, x
);
1076 new_scope
->outer
= curr_scope
;
1077 new_scope
->next
= NULL
;
1078 if (! curr_scope
->inner
)
1080 curr_scope
->inner
= new_scope
;
1081 curr_scope
->inner_last
= new_scope
;
1085 curr_scope
->inner_last
->next
= new_scope
;
1086 curr_scope
->inner_last
= new_scope
;
1088 curr_scope
= curr_scope
->inner_last
;
1092 int ntrees
= forest
->num_trees
;
1094 curr_scope
= make_new_scope (level
, x
);
1097 forest
->trees
= xcalloc (1, sizeof (scope
));
1099 forest
->trees
= xrealloc (forest
->trees
,
1100 sizeof (scope
) * (ntrees
+ 1));
1101 forest
->trees
[forest
->num_trees
++] = root
;
1103 curr_scope
->bb_beg
= curr_bb
;
1105 else if (NOTE_LINE_NUMBER (x
) == NOTE_INSN_BLOCK_END
)
1107 curr_scope
->bb_end
= curr_bb
;
1108 curr_scope
->note_end
= x
;
1110 curr_scope
= curr_scope
->outer
;
1116 if (curr_bb
&& curr_bb
->end
== x
)
1124 for (i
= 0; i
< forest
->num_trees
; i
++)
1125 relate_bbs_with_scopes (forest
->trees
[i
]);
1129 /* Remove all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes from
1133 remove_scope_notes ()
1136 basic_block currbb
= NULL
;
1138 for (x
= get_insns (); x
; x
= next
)
1140 next
= NEXT_INSN (x
);
1141 if (GET_CODE (x
) == NOTE
1142 && NOTE_LINE_NUMBER (x
) == NOTE_INSN_BASIC_BLOCK
)
1143 currbb
= NOTE_BASIC_BLOCK (x
);
1145 if (GET_CODE (x
) == NOTE
1146 && (NOTE_LINE_NUMBER (x
) == NOTE_INSN_BLOCK_BEG
1147 || NOTE_LINE_NUMBER (x
) == NOTE_INSN_BLOCK_END
))
1149 /* Check if the scope note happens to be the end of a bb. */
1150 if (currbb
&& x
== currbb
->end
)
1151 currbb
->end
= PREV_INSN (x
);
1152 if (currbb
&& x
== currbb
->head
)
1157 NEXT_INSN (PREV_INSN (x
)) = next
;
1158 PREV_INSN (next
) = PREV_INSN (x
);
1160 NEXT_INSN (x
) = NULL
;
1161 PREV_INSN (x
) = NULL
;
1170 /* Insert scope note pairs for a contained scope tree S after insn IP. */
1172 insert_intra_1 (s
, ip
)
1178 if (NOTE_BLOCK (s
->note_beg
))
1180 *ip
= emit_note_after (NOTE_INSN_BLOCK_BEG
, *ip
);
1181 NOTE_BLOCK (*ip
) = NOTE_BLOCK (s
->note_beg
);
1184 for (p
= s
->inner
; p
; p
= p
->next
)
1185 insert_intra_1 (p
, ip
);
1187 if (NOTE_BLOCK (s
->note_beg
))
1189 *ip
= emit_note_after (NOTE_INSN_BLOCK_END
, *ip
);
1190 NOTE_BLOCK (*ip
) = NOTE_BLOCK (s
->note_end
);
1195 /* Insert NOTE_INSN_BLOCK_END notes and NOTE_INSN_BLOCK_BEG notes for
1196 scopes that are contained within BB. */
1199 insert_intra_bb_scope_notes (bb
)
1202 scope s
= REORDER_BLOCK_SCOPE (bb
);
1210 if (GET_CODE (ip
) == CODE_LABEL
)
1211 ip
= NEXT_INSN (ip
);
1213 for (p
= s
->inner
; p
; p
= p
->next
)
1215 if (p
->bb_beg
!= NULL
&& p
->bb_beg
== p
->bb_end
&& p
->bb_beg
== bb
)
1216 insert_intra_1 (p
, &ip
);
1221 /* Given two consecutive basic blocks BB1 and BB2 with different scopes,
1222 insert NOTE_INSN_BLOCK_END notes after BB1 and NOTE_INSN_BLOCK_BEG
1223 notes before BB2 such that the notes are correctly balanced. If BB1 or
1224 BB2 is NULL, we are inserting scope notes for the first and last basic
1225 blocks, respectively. */
1228 insert_inter_bb_scope_notes (bb1
, bb2
)
1235 /* It is possible that a basic block is not contained in any scope.
1236 In that case, we either open or close a scope but not both. */
1239 scope s1
= REORDER_BLOCK_SCOPE (bb1
);
1240 scope s2
= REORDER_BLOCK_SCOPE (bb2
);
1249 /* Find common ancestor scope. */
1252 scope s1
= REORDER_BLOCK_SCOPE (bb1
);
1253 scope s2
= REORDER_BLOCK_SCOPE (bb2
);
1258 if (s1
->level
> s2
->level
)
1260 else if (s2
->level
> s1
->level
)
1276 scope s
= REORDER_BLOCK_SCOPE (bb1
);
1277 ip
= REORDER_BLOCK_EFF_END (bb1
);
1280 if (NOTE_BLOCK (s
->note_beg
))
1282 ip
= emit_note_after (NOTE_INSN_BLOCK_END
, ip
);
1283 NOTE_BLOCK (ip
) = NOTE_BLOCK (s
->note_end
);
1292 scope s
= REORDER_BLOCK_SCOPE (bb2
);
1296 if (NOTE_BLOCK (s
->note_beg
))
1298 ip
= emit_note_before (NOTE_INSN_BLOCK_BEG
, ip
);
1299 NOTE_BLOCK (ip
) = NOTE_BLOCK (s
->note_beg
);
1307 /* Rebuild all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes based
1308 on the scope forest and the newly reordered basic blocks. */
1311 rebuild_scope_notes (forest
)
1312 scope_forest_info
*forest
;
1316 if (forest
->num_trees
== 0)
1319 /* Start by opening the scopes before the first basic block. */
1320 insert_inter_bb_scope_notes (NULL
, BASIC_BLOCK (0));
1322 /* Then, open and close scopes as needed between blocks. */
1323 for (i
= 0; i
< n_basic_blocks
- 1; i
++)
1325 basic_block bb1
= BASIC_BLOCK (i
);
1326 basic_block bb2
= BASIC_BLOCK (i
+ 1);
1327 if (REORDER_BLOCK_SCOPE (bb1
) != REORDER_BLOCK_SCOPE (bb2
))
1328 insert_inter_bb_scope_notes (bb1
, bb2
);
1329 insert_intra_bb_scope_notes (bb1
);
1332 /* Finally, close the scopes after the last basic block. */
1333 insert_inter_bb_scope_notes (BASIC_BLOCK (n_basic_blocks
- 1), NULL
);
1334 insert_intra_bb_scope_notes (BASIC_BLOCK (n_basic_blocks
- 1));
1338 /* Free the storage associated with the scope tree at S. */
1341 free_scope_forest_1 (s
)
1346 for (p
= s
->inner
; p
; p
= next
)
1349 free_scope_forest_1 (p
);
1358 /* Free the storage associated with the scope forest. */
1361 free_scope_forest (forest
)
1362 scope_forest_info
*forest
;
1365 for (i
= 0; i
< forest
->num_trees
; i
++)
1366 free_scope_forest_1 (forest
->trees
[i
]);
1370 /* Visualize the scope forest. */
1373 dump_scope_forest (forest
)
1374 scope_forest_info
*forest
;
1376 if (forest
->num_trees
== 0)
1377 fprintf (stderr
, "\n< Empty scope forest >\n");
1381 fprintf (stderr
, "\n< Scope forest >\n");
1382 for (i
= 0; i
< forest
->num_trees
; i
++)
1383 dump_scope_forest_1 (forest
->trees
[i
], 0);
1388 /* Recursive portion of dump_scope_forest. */
1391 dump_scope_forest_1 (s
, indent
)
1398 if (s
->bb_beg
!= NULL
&& s
->bb_beg
== s
->bb_end
1399 && REORDER_BLOCK_SCOPE (s
->bb_beg
)
1400 && REORDER_BLOCK_SCOPE (s
->bb_beg
)->level
+ 1 == s
->level
)
1402 fprintf (stderr
, "%*s", indent
, "");
1403 fprintf (stderr
, "BB%d:\n", s
->bb_beg
->index
);
1406 fprintf (stderr
, "%*s", indent
, "");
1407 fprintf (stderr
, "{ level %d (block %p)\n", s
->level
,
1408 NOTE_BLOCK (s
->note_beg
));
1410 fprintf (stderr
, "%*s%s", indent
, "", "bbs:");
1411 for (i
= 0; i
< s
->num_bbs
; i
++)
1412 fprintf (stderr
, " %d", s
->bbs
[i
]->index
);
1413 fprintf (stderr
, "\n");
1415 for (p
= s
->inner
; p
; p
= p
->next
)
1416 dump_scope_forest_1 (p
, indent
+ 2);
1418 fprintf (stderr
, "%*s", indent
, "");
1419 fprintf (stderr
, "}\n");
1423 /* Reorder basic blocks. */
1426 reorder_basic_blocks ()
1429 struct loops loops_info
;
1431 scope_forest_info forest
;
1433 if (profile_arc_flag
)
1436 if (n_basic_blocks
<= 1)
1439 /* Exception edges are not currently handled. */
1440 for (i
= 0; i
< n_basic_blocks
; i
++)
1444 for (e
= BASIC_BLOCK (i
)->succ
; e
&& ! (e
->flags
& EDGE_EH
);
1448 if (e
&& (e
->flags
& EDGE_EH
))
1454 /* Find natural loops using the CFG. */
1455 num_loops
= flow_loops_find (&loops_info
);
1457 /* Dump loop information. */
1458 flow_loops_dump (&loops_info
, rtl_dump_file
, 0);
1460 reorder_last_visited
= BASIC_BLOCK (0);
1462 for (i
= 0; i
< n_basic_blocks
; i
++)
1464 basic_block bbi
= BASIC_BLOCK (i
);
1465 bbi
->aux
= xcalloc (1, sizeof (struct reorder_block_def
));
1466 *((struct reorder_block_def
*)bbi
->aux
) = rbd_init
;
1469 build_scope_forest (&forest
);
1470 remove_scope_notes ();
1472 for (i
= 0; i
< n_basic_blocks
; i
++)
1474 basic_block bbi
= BASIC_BLOCK (i
);
1475 REORDER_BLOCK_EFF_END (bbi
)
1476 = skip_insns_between_block (bbi
, REORDER_SKIP_AFTER
);
1478 REORDER_BLOCK_EFF_HEAD (bbi
) = get_insns ();
1481 rtx prev_eff_end
= REORDER_BLOCK_EFF_END (BASIC_BLOCK (i
- 1));
1482 REORDER_BLOCK_EFF_HEAD (bbi
) = NEXT_INSN (prev_eff_end
);
1486 /* If we've not got epilogue in RTL, we must fallthru to the exit.
1487 Force the last block to be at the end. */
1488 /* ??? Some ABIs (e.g. MIPS) require the return insn to be at the
1489 end of the function for stack unwinding purposes. */
1491 #ifndef HAVE_epilogue
1492 #define HAVE_epilogue 0
1495 if (! HAVE_epilogue
)
1497 basic_block last
= BASIC_BLOCK (n_basic_blocks
- 1);
1498 REORDER_BLOCK_INDEX (last
) = n_basic_blocks
- 1;
1499 REORDER_BLOCK_FLAGS (last
) |= REORDER_BLOCK_VISITED
;
1502 make_reorder_chain (BASIC_BLOCK (0));
1504 fixup_reorder_chain ();
1506 #ifdef ENABLE_CHECKING
1507 verify_insn_chain ();
1510 /* Put basic_block_info in new order. */
1511 for (i
= 0; i
< n_basic_blocks
- 1; i
++)
1513 for (j
= i
; i
!= REORDER_BLOCK_INDEX (BASIC_BLOCK (j
)); j
++)
1516 if (REORDER_BLOCK_INDEX (BASIC_BLOCK (j
)) == i
1521 int rbi
= REORDER_BLOCK_INDEX (BASIC_BLOCK (j
));
1523 temprbi
= BASIC_BLOCK (rbi
)->index
;
1524 BASIC_BLOCK (rbi
)->index
= BASIC_BLOCK (j
)->index
;
1525 BASIC_BLOCK (j
)->index
= temprbi
;
1526 tempbb
= BASIC_BLOCK (rbi
);
1527 BASIC_BLOCK (rbi
) = BASIC_BLOCK (j
);
1528 BASIC_BLOCK (j
) = tempbb
;
1532 rebuild_scope_notes (&forest
);
1533 free_scope_forest (&forest
);
1536 #ifdef ENABLE_CHECKING
1537 verify_flow_info ();
1540 for (i
= 0; i
< n_basic_blocks
; i
++)
1541 free (BASIC_BLOCK (i
)->aux
);
1543 /* Free loop information. */
1544 flow_loops_free (&loops_info
);