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 typedef struct reorder_block_def
{
65 #define REORDER_BLOCK_HEAD 0x1
66 #define REORDER_BLOCK_VISITED 0x2
67 #define REORDER_MOVED_BLOCK_END 0x3
69 #define REORDER_BLOCK_FLAGS(bb) \
70 ((reorder_block_def) (bb)->aux)->flags
72 #define REORDER_BLOCK_INDEX(bb) \
73 ((reorder_block_def) (bb)->aux)->index
75 #define REORDER_BLOCK_ADD_JUMP(bb) \
76 ((reorder_block_def) (bb)->aux)->add_jump
78 #define REORDER_BLOCK_SUCC(bb) \
79 ((reorder_block_def) (bb)->aux)->succ
81 #define REORDER_BLOCK_OLD_END(bb) \
82 ((reorder_block_def) (bb)->aux)->end
84 #define REORDER_BLOCK_BEGIN(bb) \
85 ((reorder_block_def) (bb)->aux)->block_begin
87 #define REORDER_BLOCK_END(bb) \
88 ((reorder_block_def) (bb)->aux)->block_end
91 static int reorder_index
;
92 static basic_block reorder_last_visited
;
94 enum reorder_skip_type
{REORDER_SKIP_BEFORE
, REORDER_SKIP_AFTER
,
95 REORDER_SKIP_BLOCK_END
};
98 /* Local function prototypes. */
99 static rtx skip_insns_between_block
PARAMS ((basic_block
,
100 enum reorder_skip_type
));
101 static basic_block get_common_dest
PARAMS ((basic_block
, basic_block
));
102 static basic_block chain_reorder_blocks
PARAMS ((edge
, basic_block
));
103 static void make_reorder_chain
PARAMS ((basic_block
));
104 static void fixup_reorder_chain
PARAMS ((void));
107 /* Skip over insns BEFORE or AFTER BB which are typically associated with
111 skip_insns_between_block (bb
, skip_type
)
113 enum reorder_skip_type skip_type
;
117 if (skip_type
== REORDER_SKIP_BEFORE
)
119 if (bb
== ENTRY_BLOCK_PTR
)
122 last_insn
= bb
->head
;
123 for (insn
= PREV_INSN (bb
->head
);
124 insn
&& insn
!= BASIC_BLOCK (bb
->index
- 1)->end
;
125 last_insn
= insn
, insn
= PREV_INSN (insn
))
127 if (NEXT_INSN (insn
) != last_insn
)
130 if (GET_CODE (insn
) == NOTE
131 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_LOOP_END
132 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_BASIC_BLOCK
133 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_BLOCK_END
)
144 if (bb
== EXIT_BLOCK_PTR
)
147 for (insn
= NEXT_INSN (bb
->end
);
149 last_insn
= insn
, insn
= NEXT_INSN (insn
))
151 if (bb
->index
+ 1 != n_basic_blocks
152 && insn
== BASIC_BLOCK (bb
->index
+ 1)->head
)
155 if (GET_CODE (insn
) == BARRIER
156 || GET_CODE (insn
) == JUMP_INSN
157 || (GET_CODE (insn
) == NOTE
158 && (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_END
159 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_BLOCK_END
)))
162 if (GET_CODE (insn
) == CODE_LABEL
163 && GET_CODE (NEXT_INSN (insn
)) == JUMP_INSN
164 && (GET_CODE (PATTERN (NEXT_INSN (insn
))) == ADDR_VEC
166 (NEXT_INSN (insn
))) == ADDR_DIFF_VEC
))
168 insn
= NEXT_INSN (insn
);
174 if (skip_type
== REORDER_SKIP_BLOCK_END
)
176 int found_block_end
= 0;
178 for (; insn
; last_insn
= insn
, insn
= NEXT_INSN (insn
))
180 if (bb
->index
+ 1 != n_basic_blocks
181 && insn
== BASIC_BLOCK (bb
->index
+ 1)->head
)
184 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_BLOCK_END
)
190 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_DELETED
)
193 if (GET_CODE (insn
) == NOTE
194 && NOTE_LINE_NUMBER (insn
) >= 0
196 && (NOTE_LINE_NUMBER (NEXT_INSN (insn
))
197 == NOTE_INSN_BLOCK_END
))
202 if (! found_block_end
)
211 /* Return common destination for blocks BB0 and BB1. */
214 get_common_dest (bb0
, bb1
)
215 basic_block bb0
, bb1
;
219 for (e0
= bb0
->succ
; e0
; e0
= e0
->succ_next
)
221 for (e1
= bb1
->succ
; e1
; e1
= e1
->succ_next
)
223 if (e0
->dest
== e1
->dest
)
233 /* Move the destination block for edge E after chain end block CEB
234 Adding jumps and labels is deferred until fixup_reorder_chain. */
237 chain_reorder_blocks (e
, ceb
)
241 basic_block sb
= e
->src
;
242 basic_block db
= e
->dest
;
243 rtx cebe_insn
, cebbe_insn
, dbh_insn
, dbe_insn
;
246 enum cond_types
{NO_COND
, PREDICT_THEN_WITH_ELSE
, PREDICT_ELSE
,
247 PREDICT_THEN_NO_ELSE
, PREDICT_NOT_THEN_NO_ELSE
};
248 enum cond_types cond_type
;
249 enum cond_block_types
{NO_COND_BLOCK
, THEN_BLOCK
, ELSE_BLOCK
,
251 enum cond_block_types cond_block_type
;
254 fprintf (rtl_dump_file
,
255 "Edge from basic block %d to basic block %d last visited %d\n",
256 sb
->index
, db
->index
, ceb
->index
);
258 dbh_insn
= skip_insns_between_block (db
, REORDER_SKIP_BEFORE
);
259 cebe_insn
= skip_insns_between_block (ceb
, REORDER_SKIP_AFTER
);
260 cebbe_insn
= skip_insns_between_block (ceb
, REORDER_SKIP_BLOCK_END
);
263 int block_begins
= 0;
266 for (insn
= dbh_insn
; insn
&& insn
!= db
->end
; insn
= NEXT_INSN (insn
))
268 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_BLOCK_BEG
)
274 REORDER_BLOCK_BEGIN (sb
) = block_begins
;
282 for (insn
= cebe_insn
; insn
; insn
= NEXT_INSN (insn
))
284 if (PREV_INSN (insn
) == cebbe_insn
)
286 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_BLOCK_END
)
292 REORDER_BLOCK_END (ceb
) = block_ends
;
295 /* Blocks are in original order. */
296 if (sb
->index
== ceb
->index
297 && ceb
->index
+ 1 == db
->index
&& NEXT_INSN (cebe_insn
))
300 /* Get the type of block and type of condition. */
302 cond_block_type
= NO_COND_BLOCK
;
303 if (GET_CODE (sb
->end
) == JUMP_INSN
&& ! simplejump_p (sb
->end
)
304 && condjump_p (sb
->end
))
306 if (e
->flags
& EDGE_FALLTHRU
)
307 cond_block_type
= THEN_BLOCK
;
308 else if (get_common_dest (sb
->succ
->dest
, sb
))
309 cond_block_type
= NO_ELSE_BLOCK
;
311 cond_block_type
= ELSE_BLOCK
;
313 if (sb
->succ
->succ_next
314 && get_common_dest (sb
->succ
->dest
, sb
))
316 if (cond_block_type
== THEN_BLOCK
)
318 if (! (REORDER_BLOCK_FLAGS (sb
->succ
->succ_next
->dest
)
319 & REORDER_BLOCK_VISITED
))
320 cond_type
= PREDICT_THEN_NO_ELSE
;
322 cond_type
= PREDICT_NOT_THEN_NO_ELSE
;
324 else if (cond_block_type
== NO_ELSE_BLOCK
)
326 if (! (REORDER_BLOCK_FLAGS (sb
->succ
->dest
)
327 & REORDER_BLOCK_VISITED
))
328 cond_type
= PREDICT_NOT_THEN_NO_ELSE
;
330 cond_type
= PREDICT_THEN_NO_ELSE
;
335 if (cond_block_type
== THEN_BLOCK
)
337 if (! (REORDER_BLOCK_FLAGS (sb
->succ
->succ_next
->dest
)
338 & REORDER_BLOCK_VISITED
))
339 cond_type
= PREDICT_THEN_WITH_ELSE
;
341 cond_type
= PREDICT_ELSE
;
343 else if (cond_block_type
== ELSE_BLOCK
344 && sb
->succ
->dest
!= EXIT_BLOCK_PTR
)
346 if (! (REORDER_BLOCK_FLAGS (sb
->succ
->dest
)
347 & REORDER_BLOCK_VISITED
))
348 cond_type
= PREDICT_ELSE
;
350 cond_type
= PREDICT_THEN_WITH_ELSE
;
357 static const char * cond_type_str
[] = {"not cond jump", "predict then",
359 "predict then w/o else",
360 "predict not then w/o else"};
361 static const char * cond_block_type_str
[] = {"not then or else block",
364 "then w/o else block"};
366 fprintf (rtl_dump_file
, " %s (looking at %s)\n",
367 cond_type_str
[(int)cond_type
],
368 cond_block_type_str
[(int)cond_block_type
]);
371 /* Reflect that then block will move and we'll jump to it. */
372 if (cond_block_type
!= THEN_BLOCK
373 && (cond_type
== PREDICT_ELSE
374 || cond_type
== PREDICT_NOT_THEN_NO_ELSE
))
377 fprintf (rtl_dump_file
,
378 " then jump from block %d to block %d\n",
379 sb
->index
, sb
->succ
->dest
->index
);
381 /* Jump to reordered then block. */
382 REORDER_BLOCK_ADD_JUMP (sb
) = sb
->succ
->dest
;
385 /* Reflect that then block will jump back when we have no else. */
386 if (cond_block_type
!= THEN_BLOCK
387 && cond_type
== PREDICT_NOT_THEN_NO_ELSE
)
389 for (ee
= sb
->succ
->dest
->succ
;
390 ee
&& ! (ee
->flags
& EDGE_FALLTHRU
);
394 if (ee
&& ! (GET_CODE (sb
->succ
->dest
->end
) == JUMP_INSN
395 && ! simplejump_p (sb
->succ
->dest
->end
)))
397 REORDER_BLOCK_ADD_JUMP (sb
->succ
->dest
) = ee
->dest
;
401 /* Reflect that else block will jump back. */
402 if (cond_block_type
== ELSE_BLOCK
403 && (cond_type
== PREDICT_THEN_WITH_ELSE
|| cond_type
== PREDICT_ELSE
))
408 && last_edge
->dest
!= EXIT_BLOCK_PTR
409 && GET_CODE (last_edge
->dest
->head
) == CODE_LABEL
410 && ! (GET_CODE (db
->end
) == JUMP_INSN
))
413 fprintf (rtl_dump_file
,
414 " else jump from block %d to block %d\n",
415 db
->index
, last_edge
->dest
->index
);
417 REORDER_BLOCK_ADD_JUMP (db
) = last_edge
->dest
;
421 /* This block's successor has already been reordered. This can happen
422 when we reorder a chain starting at a then or else. */
423 for (last_edge
= db
->succ
;
424 last_edge
&& ! (last_edge
->flags
& EDGE_FALLTHRU
);
425 last_edge
= last_edge
->succ_next
)
429 && last_edge
->dest
!= EXIT_BLOCK_PTR
430 && (REORDER_BLOCK_FLAGS (last_edge
->dest
)
431 & REORDER_BLOCK_VISITED
))
434 fprintf (rtl_dump_file
,
435 " end of chain jump from block %d to block %d\n",
436 db
->index
, last_edge
->dest
->index
);
438 REORDER_BLOCK_ADD_JUMP (db
) = last_edge
->dest
;
441 dbh_insn
= skip_insns_between_block (db
, REORDER_SKIP_BEFORE
);
442 cebe_insn
= skip_insns_between_block (ceb
, REORDER_SKIP_AFTER
);
443 dbe_insn
= skip_insns_between_block (db
, REORDER_SKIP_AFTER
);
445 /* Leave behind any lexical block markers. */
446 if (debug_info_level
> DINFO_LEVEL_TERSE
447 && ceb
->index
+ 1 < db
->index
)
449 rtx insn
, last_insn
= get_last_insn ();
450 insn
= NEXT_INSN (ceb
->end
);
452 insn
= REORDER_BLOCK_OLD_END (ceb
);
454 if (NEXT_INSN (cebe_insn
) == 0)
455 set_last_insn (cebe_insn
);
456 for (; insn
&& insn
!= db
->head
/*dbh_insn*/;
457 insn
= NEXT_INSN (insn
))
459 if (GET_CODE (insn
) == NOTE
460 && (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_BLOCK_BEG
))
462 cebe_insn
= emit_note_after (NOTE_INSN_BLOCK_BEG
, cebe_insn
);
465 if (GET_CODE (insn
) == NOTE
466 && (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_BLOCK_END
))
468 cebe_insn
= emit_note_after (NOTE_INSN_BLOCK_END
, cebe_insn
);
472 set_last_insn (last_insn
);
475 /* Rechain predicted block. */
476 NEXT_INSN (cebe_insn
) = dbh_insn
;
477 PREV_INSN (dbh_insn
) = cebe_insn
;
479 REORDER_BLOCK_OLD_END (db
) = NEXT_INSN (dbe_insn
);
480 if (db
->index
!= n_basic_blocks
- 1)
481 NEXT_INSN (dbe_insn
) = 0;
487 /* Reorder blocks starting at block B. */
490 make_reorder_chain (bb
)
494 basic_block visited_edge
= NULL
;
498 if (bb
== EXIT_BLOCK_PTR
)
501 /* Find the most probable block. */
504 if (GET_CODE (block_end
) == JUMP_INSN
&& condjump_p (block_end
))
506 rtx note
= find_reg_note (block_end
, REG_BR_PROB
, 0);
509 probability
= XINT (XEXP (note
, 0), 0);
513 if (probability
>= REG_BR_PROB_BASE
/ 2)
514 e
= bb
->succ
->succ_next
;
517 /* Add chosen successor to chain and recurse on it. */
518 if (e
&& e
->dest
!= EXIT_BLOCK_PTR
520 && (! (REORDER_BLOCK_FLAGS (e
->dest
) & REORDER_BLOCK_VISITED
)
521 || (REORDER_BLOCK_FLAGS (e
->dest
) == REORDER_BLOCK_HEAD
)))
523 if (! (REORDER_BLOCK_FLAGS (bb
) & REORDER_BLOCK_VISITED
))
525 REORDER_BLOCK_FLAGS (bb
) |= REORDER_BLOCK_HEAD
;
526 REORDER_BLOCK_INDEX (bb
) = reorder_index
++;
527 REORDER_BLOCK_FLAGS (bb
) |= REORDER_BLOCK_VISITED
;
530 if (REORDER_BLOCK_FLAGS (e
->dest
) & REORDER_BLOCK_VISITED
)
531 REORDER_BLOCK_FLAGS (e
->dest
) &= ~REORDER_BLOCK_HEAD
;
533 REORDER_BLOCK_SUCC (bb
) = e
;
535 visited_edge
= e
->dest
;
537 reorder_last_visited
= chain_reorder_blocks (e
, bb
);
540 && ! (REORDER_BLOCK_FLAGS (e
->dest
)
541 & REORDER_BLOCK_VISITED
))
542 make_reorder_chain (e
->dest
);
546 if (! (REORDER_BLOCK_FLAGS (bb
) & REORDER_BLOCK_VISITED
))
548 REORDER_BLOCK_INDEX (bb
) = reorder_index
++;
549 REORDER_BLOCK_FLAGS (bb
) |= REORDER_BLOCK_VISITED
;
553 /* Recurse on the successors. */
554 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
556 if (e
->dest
&& e
->dest
== EXIT_BLOCK_PTR
)
561 && e
->dest
!= visited_edge
562 && ! (REORDER_BLOCK_FLAGS (e
->dest
)
563 & REORDER_BLOCK_VISITED
))
566 = chain_reorder_blocks (e
, reorder_last_visited
);
567 make_reorder_chain (e
->dest
);
573 /* Fixup jumps and labels after reordering basic blocks. */
576 fixup_reorder_chain ()
581 /* Set the new last insn. */
583 i
< n_basic_blocks
- 1
584 && REORDER_BLOCK_INDEX (BASIC_BLOCK (i
)) != n_basic_blocks
;
588 for (insn
= BASIC_BLOCK (i
)->head
;
589 NEXT_INSN (insn
) != 0;
590 insn
= NEXT_INSN (insn
))
593 set_last_insn (insn
);
595 /* Add jumps and labels to fixup blocks. */
596 for (i
= 0; i
< n_basic_blocks
- 1; i
++)
598 basic_block bbi
= BASIC_BLOCK (i
);
599 if (REORDER_BLOCK_ADD_JUMP (bbi
))
601 rtx label_insn
, jump_insn
, barrier_insn
;
603 if (GET_CODE (REORDER_BLOCK_ADD_JUMP (bbi
)->head
)
605 label_insn
= REORDER_BLOCK_ADD_JUMP (bbi
)->head
;
608 rtx new_label
= gen_label_rtx ();
609 label_insn
= emit_label_before (new_label
,
610 REORDER_BLOCK_ADD_JUMP (bbi
)->head
);
612 REORDER_BLOCK_ADD_JUMP (bbi
)->head
= label_insn
;
614 jump_insn
= emit_jump_insn_after (gen_jump (label_insn
),
616 JUMP_LABEL (jump_insn
) = label_insn
;
617 ++LABEL_NUSES (label_insn
);
618 barrier_insn
= emit_barrier_after (jump_insn
);
619 if (GET_CODE (bbi
->end
) != JUMP_INSN
)
620 bbi
->end
= jump_insn
;
621 /* Add block for jump. Typically this is when a then is not
622 predicted and we are jumping to the moved then block. */
627 VARRAY_GROW (basic_block_info
, ++n_basic_blocks
);
628 create_basic_block (n_basic_blocks
- 1, jump_insn
,
630 nb
= BASIC_BLOCK (n_basic_blocks
- 1);
631 nb
->global_live_at_start
632 = OBSTACK_ALLOC_REG_SET (function_obstack
);
633 nb
->global_live_at_end
634 = OBSTACK_ALLOC_REG_SET (function_obstack
);
636 COPY_REG_SET (nb
->global_live_at_start
,
637 bbi
->global_live_at_start
);
638 COPY_REG_SET (nb
->global_live_at_end
,
639 bbi
->global_live_at_start
);
640 BASIC_BLOCK (nb
->index
)->local_set
= 0;
642 nb
->aux
= xcalloc (1, sizeof (struct reorder_block_def
));
643 REORDER_BLOCK_INDEX (BASIC_BLOCK (n_basic_blocks
- 1))
644 = REORDER_BLOCK_INDEX (bbi
) + 1;
645 /* Relink to new block. */
646 nb
->succ
= bbi
->succ
;
649 make_edge (NULL
, bbi
, nb
, 0);
651 = bbi
->succ
->succ_next
->succ_next
;
652 nb
->succ
->succ_next
= 0;
653 /* Fix reorder block index to reflect new block. */
654 for (j
= 0; j
< n_basic_blocks
- 1; j
++)
656 basic_block bbj
= BASIC_BLOCK (j
);
657 if (REORDER_BLOCK_INDEX (bbj
)
658 >= REORDER_BLOCK_INDEX (bbi
) + 1)
659 REORDER_BLOCK_INDEX (bbj
)++;
667 /* Reorder basic blocks. */
670 reorder_basic_blocks ()
673 struct loops loops_info
;
677 if (profile_arc_flag
)
680 if (n_basic_blocks
<= 1)
683 /* Exception edges are not currently handled. */
684 for (i
= 0; i
< n_basic_blocks
; i
++)
688 for (e
= BASIC_BLOCK (i
)->succ
; e
&& ! (e
->flags
& EDGE_EH
);
692 if (e
&& (e
->flags
& EDGE_EH
))
698 /* Find natural loops using the CFG. */
699 num_loops
= flow_loops_find (&loops_info
);
701 /* Dump loop information. */
702 flow_loops_dump (&loops_info
, rtl_dump_file
, 0);
704 /* Estimate using heuristics if no profiling info is available. */
705 if (! flag_branch_probabilities
)
706 estimate_probability (&loops_info
);
708 reorder_last_visited
= BASIC_BLOCK (0);
710 for (i
= 0; i
< n_basic_blocks
; i
++)
711 BASIC_BLOCK (i
)->aux
= xcalloc (1, sizeof (struct reorder_block_def
));
714 = NEXT_INSN (skip_insns_between_block (BASIC_BLOCK (n_basic_blocks
- 1),
715 REORDER_SKIP_AFTER
));
717 make_reorder_chain (BASIC_BLOCK (0));
719 fixup_reorder_chain ();
721 #ifdef ENABLE_CHECKING
724 last_insn
= get_insns ();
725 for (insn
= NEXT_INSN (get_insns ());
726 insn
&& PREV_INSN (insn
) == last_insn
727 && NEXT_INSN (PREV_INSN (insn
)) == insn
;
729 insn
= NEXT_INSN (insn
))
735 fprintf (rtl_dump_file
, "insn chaining error at %d\n",
736 INSN_UID (last_insn
));
742 /* Put basic_block_info in new order. */
743 for (i
= 0; i
< n_basic_blocks
- 1; i
++)
745 for (j
= i
; i
!= REORDER_BLOCK_INDEX (BASIC_BLOCK (j
)); j
++)
748 if (REORDER_BLOCK_INDEX (BASIC_BLOCK (j
)) == i
753 int rbi
= REORDER_BLOCK_INDEX (BASIC_BLOCK (j
));
755 temprbi
= BASIC_BLOCK (rbi
)->index
;
756 BASIC_BLOCK (rbi
)->index
= BASIC_BLOCK (j
)->index
;
757 BASIC_BLOCK (j
)->index
= temprbi
;
758 tempbb
= BASIC_BLOCK (rbi
);
759 BASIC_BLOCK (rbi
) = BASIC_BLOCK (j
);
760 BASIC_BLOCK (j
) = tempbb
;
765 rtx xafter
= skip_insns_between_block (BASIC_BLOCK (n_basic_blocks
- 1),
768 NEXT_INSN (xafter
) = last_insn
;
773 #ifdef ENABLE_CHECKING
777 for (i
= 0; i
< n_basic_blocks
; i
++)
778 free (BASIC_BLOCK (i
)->aux
);
780 /* Free loop information. */
781 flow_loops_free (&loops_info
);