This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Patch: More basic-block reordering infrastructure.
- To: gcc-patches at gcc dot gnu dot org
- Subject: Patch: More basic-block reordering infrastructure.
- From: Jason Eckhardt <jle at cygnus dot com>
- Date: Sat, 29 Jan 2000 13:02:38 -0800 (PST)
These are changes to flow.c and toplev.c to perform basic block reordering.
By using either profiling feedback or static estimates of branch probabilities,
this code will reorder the basic blocks such that infrequently executed blocks
are positioned out of the way and frequently executed blocks are chained
together in a straight line sequence. This can create longer sequences of
branch-free code; reduce penalties from mispredicted branches; improve
I$ usage; etc.
While the code 'works', it can still be considered preliminary. There are
improvements that can be made and there are some difficulties regarding
debugging info when reordering is enabled (see below).
With -freorder-blocks enabled, we pass torture and I successfully bootstrapped
on x86 this morning.
Overview of operation:
The main entry is reorder_basic_blocks. It first finds the natural
loops. Then if there is no profiling information it estimates
conditional branches. Two types are currently predicted:
if a condjump in a loop has a successor that is not part of
the natural loop, predict it not taken.
if a condition is testing an integer is less than zero, predict it
not taken.
there are some other possibilities mentioned in Larus's paper (I'll be
adding some of these to predict.c).
Call make_reorder_chain on block 0:
Look at probabilities to determine which condjump path is most likely
Each block has added info pointed to by aux
Call chain_reorder_blocks on most likely edge
Recurse on edge destination
When this returns after following a chain of blocks as far as it can go
(see ascii figure below)
call chain_reorder_blocks on other successors
chain_reorder_blocks chains blocks as it encounters them.
First it determines what type of destination block and condition it has.
The possibilities are:
Predicted: Becomes:
1 if() then{} else{} then if() then{} else{go X}
Y:{}... X:{...;go Y}
2 if() then{} else{} else if() then{go X} else{}
Y:{}... X:{...}
3 if() then{} then if() then {}
4 if() then{} not then if() then{go X}
Y:{}... X:{...;go Y}
The first code block handles adding {go X} X: for 2 and 4
The second code block handles adding go Y for 4 as a then without an
else will have a fall-through edge
The third code block handles adding {go Y} for 1
The fourth code block handles adding a branch to a visited successor
whenever we reach the end of a chain (e.g. 8 - 4 below)
The blocks are handled as they are seen. If insns were only
accessible within a basic block so labels/jumps could be added to the
beginning/end only of a basic block then the above would be easier
than what the code does. What it does is try and insure the addition only
effects that block and does not change the insn chaining in a possibly
already reordered block. These sections of code are demarcated with
the BEGIN/END splice comments. As one can probably imagine, most of
the errors have concerned this.
skip_insns_between_blocks tries to skip over those pesky insns that
can appear between blocks.
0 ascii representation indicating
/ \ a possible order that blocks would
1 9 be visited and placed in
/ \ / \
2 5 10 11
/ \ / \ |
4 3 6 7 12
\ | |
--------8 13
Currently exception regions are handled only to the extent that
functions having them are ignored. This needs improvement of course.
Another problem involves the lack of debugging support when reordering
is enabled. Because basic blocks can be substantially repositioned,
the associated lexical blocks do not stay in sync. For now, this isn't
crippling, but is something that will be attended to. Any helpful comments
would be appreciated (or, if you want to do it...).
Sat Jan 29 15:37:21 2000 Stan Cox <scox@cygnus.com>
Jason Eckhardt <jle@cygnus.com>
* toplev.c: Changes to add -freorder-blocks and graph dump after
block reordering is done.
* flow.c (reorder_block_def): New structure for use during block
reordering.
(REORDER_BLOCK_*): New macros to access members of above structure.
(skip_insns_between_block, get_common_dest, chain_reorder_blocks,
make_reorder_chain, fixup_reorder_chain, reorder_basic_blocks): New
functions for block reordering.
Index: toplev.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/toplev.c,v
retrieving revision 1.284
diff -c -3 -p -r1.284 toplev.c
*** toplev.c 2000/01/28 22:22:50 1.284
--- toplev.c 2000/01/29 20:13:33
*************** int jump2_opt_dump = 0;
*** 250,255 ****
--- 250,256 ----
#ifdef DELAY_SLOTS
int dbr_sched_dump = 0;
#endif
+ int reorder_blocks_dump = 0;
int flag_print_asm_name = 0;
#ifdef STACK_REGS
int stack_reg_dump = 0;
*************** int flag_test_coverage = 0;
*** 352,357 ****
--- 353,362 ----
int flag_branch_probabilities = 0;
+ /* Nonzero if basic blocks should be reordered. */
+
+ int flag_reorder_blocks = 0;
+
/* Nonzero for -pedantic switch: warn about anything
that standard spec forbids. */
*************** lang_independent_options f_options[] =
*** 937,942 ****
--- 942,949 ----
"Create data files needed by gcov" },
{"branch-probabilities", &flag_branch_probabilities, 1,
"Use profiling information for branch probabilities" },
+ {"reorder-blocks", &flag_reorder_blocks, 1,
+ "Reorder basic blocks to improve code placement" },
{"fast-math", &flag_fast_math, 1,
"Improve FP speed by violating ANSI & IEEE rules" },
{"common", &flag_no_common, 0,
*************** int flow2_time;
*** 1330,1335 ****
--- 1337,1343 ----
int peephole2_time;
int sched2_time;
int dbr_sched_time;
+ int reorder_blocks_time;
int shorten_branch_time;
int stack_reg_time;
int final_time;
*************** compile_file (name)
*** 2023,2028 ****
--- 2031,2037 ----
peephole2_time = 0;
sched2_time = 0;
dbr_sched_time = 0;
+ reorder_blocks_time = 0;
shorten_branch_time = 0;
stack_reg_time = 0;
final_time = 0;
*************** compile_file (name)
*** 2174,2179 ****
--- 2183,2194 ----
clean_graph_dump_file (dump_base_name, ".16.sched2");
}
#endif
+ if (reorder_blocks_dump)
+ {
+ clean_dump_file (".bbro");
+ if (graph_dump_format != no_graph)
+ clean_graph_dump_file (dump_base_name, ".bbro");
+ }
if (jump2_opt_dump)
{
clean_dump_file (".17.jump2");
*************** compile_file (name)
*** 2556,2561 ****
--- 2571,2578 ----
if (sched2_dump)
finish_graph_dump_file (dump_base_name, ".16.sched2");
#endif
+ if (reorder_blocks_dump)
+ finish_graph_dump_file (dump_base_name, ".bbro");
if (jump2_opt_dump)
finish_graph_dump_file (dump_base_name, ".17.jump2");
#ifdef MACHINE_DEPENDENT_REORG
*************** compile_file (name)
*** 2609,2614 ****
--- 2626,2632 ----
#ifdef DELAY_SLOTS
print_time ("dbranch", dbr_sched_time);
#endif
+ print_time ("bbro", reorder_blocks_time);
print_time ("shorten-branch", shorten_branch_time);
#ifdef STACK_REGS
print_time ("stack-reg", stack_reg_time);
*************** rest_of_compilation (decl)
*** 3486,3491 ****
--- 3504,3524 ----
= optimize > 0 && only_leaf_regs_used () && leaf_function_p ();
#endif
+ if (optimize > 0 && flag_reorder_blocks)
+ {
+ if (reorder_blocks_dump)
+ open_dump_file (".bbro", decl_printable_name (decl, 2));
+
+ TIMEVAR (reorder_blocks_time, reorder_basic_blocks (rtl_dump_file));
+
+ if (reorder_blocks_dump)
+ {
+ close_dump_file (print_rtl_with_bb, insns);
+ if (graph_dump_format != no_graph)
+ print_rtl_graph_with_bb (dump_base_name, ".bbro", insns);
+ }
+ }
+
/* One more attempt to remove jumps to .+1 left by dead-store elimination.
Also do cross-jumping this time and delete no-op move insns. */
*************** decode_d_option (arg)
*** 3890,3895 ****
--- 3923,3929 ----
#ifdef DELAY_SLOTS
dbr_sched_dump = 1;
#endif
+ reorder_blocks_dump = 1;
flow_dump = 1;
flow2_dump = 1;
global_reg_dump = 1;
*************** decode_d_option (arg)
*** 3918,3923 ****
--- 3952,3960 ----
break;
case 'b':
branch_prob_dump = 1;
+ break;
+ case 'B':
+ reorder_blocks_dump = 1;
break;
case 'c':
combine_dump = 1;
Index: flow.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/flow.c,v
retrieving revision 1.212
diff -c -3 -p -r1.212 flow.c
*** flow.c 2000/01/29 01:41:22 1.212
--- flow.c 2000/01/29 20:13:54
*************** Boston, MA 02111-1307, USA. */
*** 134,139 ****
--- 134,140 ----
#include "toplev.h"
#include "recog.h"
#include "insn-flags.h"
+ #include "expr.h"
#include "obstack.h"
*************** flow_loop_outside_edge_p (loop, e)
*** 7038,7040 ****
--- 7039,7804 ----
return (e->src == ENTRY_BLOCK_PTR)
|| ! TEST_BIT (loop->nodes, e->src->index);
}
+
+
+ typedef struct reorder_block_def {
+ int flags;
+ int index;
+ basic_block add_jump;
+ edge succ;
+ rtx end;
+ int block_begin;
+ int block_end;
+ } *reorder_block_def;
+
+ #define REORDER_BLOCK_HEAD 0x1
+ #define REORDER_BLOCK_VISITED 0x2
+ #define REORDER_MOVED_BLOCK_END 0x3
+
+ #define REORDER_BLOCK_FLAGS(b) \
+ ((reorder_block_def) BASIC_BLOCK (b)->aux)->flags
+
+ #define REORDER_BLOCK_INDEX(b) \
+ ((reorder_block_def) BASIC_BLOCK (b)->aux)->index
+
+ #define REORDER_BLOCK_ADD_JUMP(b) \
+ ((reorder_block_def) BASIC_BLOCK (b)->aux)->add_jump
+
+ #define REORDER_BLOCK_SUCC(b) \
+ ((reorder_block_def) BASIC_BLOCK (b)->aux)->succ
+
+ #define REORDER_BLOCK_OLD_END(b) \
+ ((reorder_block_def) BASIC_BLOCK (b)->aux)->end
+
+ #define REORDER_BLOCK_BEGIN(b) \
+ ((reorder_block_def) BASIC_BLOCK (b)->aux)->block_begin
+
+ #define REORDER_BLOCK_END(b) \
+ ((reorder_block_def) BASIC_BLOCK (b)->aux)->block_end
+
+ /* Dominator bitmaps. */
+ static FILE *rob_dump_file;
+
+ static int reorder_index;
+ static basic_block reorder_last_visited;
+
+ #define REORDER_SKIP_BEFORE 0x1
+ #define REORDER_SKIP_AFTER 0x2
+ #define REORDER_SKIP_BLOCK_END 0x3
+
+ /* Skip over insns BEFORE or AFTER BB which are typically associated with
+ basic block BB. */
+
+ static rtx
+ skip_insns_between_block (bb, skip_type)
+ basic_block bb;
+ int skip_type;
+ {
+ rtx insn, last_insn;
+
+ if (skip_type == REORDER_SKIP_BEFORE)
+ {
+ if (bb->index == ENTRY_BLOCK)
+ return 0;
+ last_insn = bb->head;
+ for (insn = PREV_INSN (bb->head);
+ insn && insn != BASIC_BLOCK (bb->index - 1)->end;
+ last_insn = insn, insn = PREV_INSN (insn))
+ {
+ if (NEXT_INSN (insn) != last_insn)
+ break;
+ if (GET_CODE (insn) == NOTE
+ && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_END
+ && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK
+ && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BLOCK_END)
+ continue;
+
+ break;
+ }
+ }
+ else if (skip_type == REORDER_SKIP_AFTER
+ || skip_type == REORDER_SKIP_BLOCK_END)
+ {
+ last_insn = bb->end;
+
+ if (bb->index == EXIT_BLOCK)
+ return 0;
+
+ for (insn = NEXT_INSN (bb->end);
+ insn;
+ last_insn = insn, insn = NEXT_INSN (insn))
+ {
+ if (bb->index + 1 != n_basic_blocks
+ && insn == BASIC_BLOCK (bb->index + 1)->head)
+ break;
+
+ if (GET_CODE (insn) == BARRIER
+ || GET_CODE (insn) == JUMP_INSN
+ || (GET_CODE (insn) == NOTE
+ && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
+ || NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END)))
+ continue;
+ if (GET_CODE (insn) == CODE_LABEL
+ && GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
+ && (GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_VEC
+ || GET_CODE (PATTERN
+ (NEXT_INSN (insn))) == ADDR_DIFF_VEC))
+ {
+ insn = NEXT_INSN (insn);
+ continue;
+ }
+ break;
+ }
+ }
+ if (skip_type == REORDER_SKIP_BLOCK_END)
+ {
+ int found_block_end = 0;
+
+ for (; insn; last_insn = insn, insn = NEXT_INSN (insn))
+ {
+ if (bb->index + 1 != n_basic_blocks
+ && insn == BASIC_BLOCK (bb->index + 1)->head)
+ break;
+
+ if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END)
+ {
+ found_block_end = 1;
+ continue;
+ }
+ if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED)
+ continue;
+ if (GET_CODE (insn) == NOTE
+ && NOTE_LINE_NUMBER (insn) >= 0
+ && NEXT_INSN (insn)
+ && NOTE_LINE_NUMBER (NEXT_INSN (insn)) == NOTE_INSN_BLOCK_END)
+ continue;
+ break;
+ }
+ if (! found_block_end)
+ last_insn = 0;
+ }
+ return last_insn;
+ }
+
+
+ /* Return common destination for blocks BB0 and BB1. */
+
+ static basic_block
+ get_common_dest (bb0, bb1)
+ basic_block bb0, bb1;
+ {
+ edge e0, e1;
+
+ for (e0 = bb0->succ; e0; e0 = e0->succ_next)
+ {
+ for (e1 = bb1->succ; e1; e1 = e1->succ_next)
+ {
+ if (e0->dest == e1->dest)
+ {
+ return e0->dest;
+ }
+ }
+ }
+ return 0;
+ }
+
+
+ /* Move the destination block for edge E after chain end block CEB
+ Adding jumps and labels is deferred until fixup_reorder_chain. */
+
+ static basic_block
+ chain_reorder_blocks (e, ceb)
+ edge e;
+ basic_block ceb;
+ {
+ basic_block sb = e->src;
+ basic_block db = e->dest;
+ int chain_end_block = ceb->index;
+ int src_block = e->src->index;
+ int dest_block = e->dest->index;
+ rtx cebe_insn, cebbe_insn, dbh_insn, dbe_insn;
+ edge ee, last_edge;
+
+ enum cond_types {NO_COND, PREDICT_THEN_WITH_ELSE, PREDICT_ELSE,
+ PREDICT_THEN_NO_ELSE, PREDICT_NOT_THEN_NO_ELSE};
+ enum cond_types cond_type;
+ enum cond_block_types {NO_COND_BLOCK, THEN_BLOCK, ELSE_BLOCK,
+ NO_ELSE_BLOCK};
+ enum cond_block_types cond_block_type;
+
+ if (rob_dump_file)
+ fprintf (rob_dump_file,
+ "Edge from basic block %d to basic block %d last visited %d\n",
+ src_block, dest_block, chain_end_block);
+
+ dbh_insn = skip_insns_between_block (db, REORDER_SKIP_BEFORE);
+ cebe_insn = skip_insns_between_block (ceb, REORDER_SKIP_AFTER);
+ cebbe_insn = skip_insns_between_block (ceb, REORDER_SKIP_BLOCK_END);
+
+ {
+ int block_begins = 0;
+ rtx insn;
+
+ for (insn = dbh_insn; insn && insn != db->end; insn = NEXT_INSN (insn))
+ {
+ if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_BEG)
+ {
+ block_begins += 1;
+ break;
+ }
+ }
+ REORDER_BLOCK_BEGIN (src_block) = block_begins;
+ }
+
+ if (cebbe_insn)
+ {
+ int block_ends = 0;
+ rtx insn;
+
+ for (insn = cebe_insn; insn; insn = NEXT_INSN (insn))
+ {
+ if (PREV_INSN (insn) == cebbe_insn)
+ break;
+ if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END)
+ {
+ block_ends += 1;
+ continue;
+ }
+ }
+ REORDER_BLOCK_END (chain_end_block) = block_ends;
+ }
+
+ /* Blocks are in original order. */
+ if (src_block == chain_end_block
+ && chain_end_block + 1 == dest_block && NEXT_INSN (cebe_insn))
+ return db;
+
+ /* Get the type of block and type of condition. */
+ cond_type = NO_COND;
+ cond_block_type = NO_COND_BLOCK;
+ if (GET_CODE (sb->end) == JUMP_INSN && ! simplejump_p (sb->end)
+ && condjump_p (sb->end))
+ {
+ if (e->flags & EDGE_FALLTHRU)
+ cond_block_type = THEN_BLOCK;
+ else if (get_common_dest (sb->succ->dest, sb))
+ cond_block_type = NO_ELSE_BLOCK;
+ else
+ cond_block_type = ELSE_BLOCK;
+
+ if (sb->succ->succ_next
+ && get_common_dest (sb->succ->dest, sb))
+ {
+ if (cond_block_type == THEN_BLOCK)
+ {
+ if (! (REORDER_BLOCK_FLAGS (sb->succ->succ_next->dest->index)
+ & REORDER_BLOCK_VISITED))
+ cond_type = PREDICT_THEN_NO_ELSE;
+ else
+ cond_type = PREDICT_NOT_THEN_NO_ELSE;
+ }
+ else if (cond_block_type == NO_ELSE_BLOCK)
+ {
+ if (! (REORDER_BLOCK_FLAGS (sb->succ->dest->index)
+ & REORDER_BLOCK_VISITED))
+ cond_type = PREDICT_NOT_THEN_NO_ELSE;
+ else
+ cond_type = PREDICT_THEN_NO_ELSE;
+ }
+ }
+ else
+ {
+ if (cond_block_type == THEN_BLOCK)
+ {
+ if (! (REORDER_BLOCK_FLAGS (sb->succ->succ_next->dest->index)
+ & REORDER_BLOCK_VISITED))
+ cond_type = PREDICT_THEN_WITH_ELSE;
+ else
+ cond_type = PREDICT_ELSE;
+ }
+ else if (cond_block_type == ELSE_BLOCK
+ && sb->succ->dest->index != EXIT_BLOCK)
+ {
+ if (! (REORDER_BLOCK_FLAGS (sb->succ->dest->index)
+ & REORDER_BLOCK_VISITED))
+ cond_type = PREDICT_ELSE;
+ else
+ cond_type = PREDICT_THEN_WITH_ELSE;
+ }
+ }
+ }
+
+ if (rob_dump_file)
+ {
+ char *cond_type_str [] = {"not cond jump", "predict then",
+ "predict else",
+ "predict then w/o else",
+ "predict not then w/o else"};
+ char *cond_block_type_str [] = {"not then or else block", "then block",
+ "else block", "then w/o else block"};
+
+ fprintf (rob_dump_file, " %s (looking at %s)\n",
+ cond_type_str[(int)cond_type],
+ cond_block_type_str[(int)cond_block_type]);
+ }
+
+ /* Reflect that then block will move and we'll jump to it. */
+ if (cond_block_type != THEN_BLOCK
+ && (cond_type == PREDICT_ELSE
+ || cond_type == PREDICT_NOT_THEN_NO_ELSE))
+ {
+ if (rob_dump_file)
+ fprintf (rob_dump_file,
+ " then jump from block %d to block %d\n",
+ src_block, sb->succ->dest->index);
+
+ /* Jump to reordered then block. */
+ REORDER_BLOCK_ADD_JUMP (sb->index) = sb->succ->dest;
+ }
+
+ /* Reflect that then block will jump back when we have no else. */
+ if (cond_block_type != THEN_BLOCK
+ && cond_type == PREDICT_NOT_THEN_NO_ELSE)
+ {
+ for (ee = sb->succ->dest->succ;
+ ee && ! (ee->flags & EDGE_FALLTHRU);
+ ee = ee->succ_next)
+ { /* Empty. */ }
+
+ if (ee && ! (GET_CODE (sb->succ->dest->end) == JUMP_INSN
+ && ! simplejump_p (sb->succ->dest->end)))
+ {
+ REORDER_BLOCK_ADD_JUMP (sb->succ->dest->index) = ee->dest;
+ }
+ }
+
+ /* Reflect that else block will jump back. */
+ if (cond_block_type == ELSE_BLOCK
+ && (cond_type == PREDICT_THEN_WITH_ELSE || cond_type == PREDICT_ELSE))
+ {
+ last_edge=db->succ;
+
+ if (last_edge
+ && last_edge->dest->index != EXIT_BLOCK
+ && GET_CODE (last_edge->dest->head) == CODE_LABEL
+ && ! (GET_CODE (db->end) == JUMP_INSN))
+ {
+ if (rob_dump_file)
+ fprintf (rob_dump_file,
+ " else jump from block %d to block %d\n",
+ dest_block, last_edge->dest->index);
+
+ REORDER_BLOCK_ADD_JUMP (db->index) = last_edge->dest;
+ }
+ }
+
+ /* This block's successor has already been reordered. This can happen
+ when we reorder a chain starting at a then or else. */
+ for (last_edge = db->succ;
+ last_edge && ! (last_edge->flags & EDGE_FALLTHRU);
+ last_edge = last_edge->succ_next)
+ { /* Empty. */ }
+
+ if (last_edge
+ && last_edge->dest->index != EXIT_BLOCK
+ && (REORDER_BLOCK_FLAGS (last_edge->dest->index)
+ & REORDER_BLOCK_VISITED))
+ {
+ if (rob_dump_file)
+ fprintf (rob_dump_file,
+ " end of chain jump from block %d to block %d\n",
+ dest_block, last_edge->dest->index);
+
+ REORDER_BLOCK_ADD_JUMP (db->index) = last_edge->dest;
+ }
+
+ dbh_insn = skip_insns_between_block (db, REORDER_SKIP_BEFORE);
+ cebe_insn = skip_insns_between_block (ceb, REORDER_SKIP_AFTER);
+ dbe_insn = skip_insns_between_block (db, REORDER_SKIP_AFTER);
+
+ /* Leave behind any lexical block markers. */
+ if (debug_info_level > DINFO_LEVEL_TERSE
+ && chain_end_block + 1 < dest_block)
+ {
+ rtx insn, last_insn = get_last_insn ();
+ insn = NEXT_INSN (ceb->end);
+ if (! insn)
+ insn = REORDER_BLOCK_OLD_END (chain_end_block);
+
+ if (NEXT_INSN (cebe_insn) == 0)
+ set_last_insn (cebe_insn);
+ for (; insn && insn != db->head/*dbh_insn*/;
+ insn = NEXT_INSN (insn))
+ {
+ if (GET_CODE (insn) == NOTE
+ && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_BEG))
+ {
+ cebe_insn = emit_note_after (NOTE_INSN_BLOCK_BEG, cebe_insn);
+ delete_insn (insn);
+ }
+ if (GET_CODE (insn) == NOTE
+ && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END))
+ {
+ cebe_insn = emit_note_after (NOTE_INSN_BLOCK_END, cebe_insn);
+ delete_insn (insn);
+ }
+ }
+ set_last_insn (last_insn);
+ }
+
+ /* Rechain predicted block. */
+ NEXT_INSN (cebe_insn) = dbh_insn;
+ PREV_INSN (dbh_insn) = cebe_insn;
+
+ REORDER_BLOCK_OLD_END (db->index) = NEXT_INSN (dbe_insn);
+ if (dest_block != n_basic_blocks - 1)
+ NEXT_INSN (dbe_insn) = 0;
+
+ return db;
+ }
+
+
+ /* Reorder blocks starting at block B. */
+
+ static void
+ make_reorder_chain (b)
+ int b;
+ {
+ edge e;
+ int visited_edge = 0;
+ basic_block bb = BASIC_BLOCK (b);
+ rtx block_end;
+ int probability;
+
+ if (b == EXIT_BLOCK)
+ return;
+
+ /* Find the most probable block. */
+ e = bb->succ;
+ block_end = bb->end;
+ if (GET_CODE (block_end) == JUMP_INSN && condjump_p (block_end))
+ {
+ rtx note = find_reg_note (block_end, REG_BR_PROB, 0);
+
+ if (note)
+ probability = XINT (XEXP (note, 0), 0);
+ else
+ probability = 0;
+
+ if (probability >= REG_BR_PROB_BASE / 2)
+ e = bb->succ->succ_next;
+ }
+
+ /* Add chosen successor to chain and recurse on it. */
+ if (e && e->dest->index != EXIT_BLOCK
+ && e->dest->index != e->src->index
+ && (! (REORDER_BLOCK_FLAGS (e->dest->index) & REORDER_BLOCK_VISITED)
+ || (REORDER_BLOCK_FLAGS (e->dest->index) == REORDER_BLOCK_HEAD)))
+ {
+ if (! (REORDER_BLOCK_FLAGS (b) & REORDER_BLOCK_VISITED))
+ {
+ REORDER_BLOCK_FLAGS (b) |= REORDER_BLOCK_HEAD;
+ REORDER_BLOCK_INDEX (b) = reorder_index++;
+ REORDER_BLOCK_FLAGS (b) |= REORDER_BLOCK_VISITED;
+ }
+
+ if (REORDER_BLOCK_FLAGS (e->dest->index) & REORDER_BLOCK_VISITED)
+ REORDER_BLOCK_FLAGS (e->dest->index) &= ! REORDER_BLOCK_HEAD;
+
+ REORDER_BLOCK_SUCC (b) = e;
+
+ visited_edge = e->dest->index;
+
+ reorder_last_visited = chain_reorder_blocks (e, BASIC_BLOCK (b));
+
+ if (e->dest
+ && ! (REORDER_BLOCK_FLAGS (e->dest->index)
+ & REORDER_BLOCK_VISITED))
+ make_reorder_chain (e->dest->index);
+ }
+ else
+ {
+ if (! (REORDER_BLOCK_FLAGS (b) & REORDER_BLOCK_VISITED))
+ {
+ REORDER_BLOCK_INDEX (b) = reorder_index++;
+ REORDER_BLOCK_FLAGS (b) |= REORDER_BLOCK_VISITED;
+ }
+ }
+
+ /* Recurse on the successors. */
+ for (e = BASIC_BLOCK (b)->succ; e; e = e->succ_next)
+ {
+ if (e->dest && e->dest->index == EXIT_BLOCK)
+ continue;
+
+ if (e->dest
+ && e->dest->index != e->src->index
+ && e->dest->index != visited_edge
+ && ! (REORDER_BLOCK_FLAGS (e->dest->index)
+ & REORDER_BLOCK_VISITED))
+ {
+ reorder_last_visited
+ = chain_reorder_blocks (e, reorder_last_visited);
+ make_reorder_chain (e->dest->index);
+ }
+ }
+ }
+
+
+ /* Fixup jumps and labels after reordering basic blocks. */
+
+ static void
+ fixup_reorder_chain ()
+ {
+ int i, j;
+ rtx insn;
+
+ /* Set the new last insn. */
+ for (i = 0;
+ i < n_basic_blocks - 1 && REORDER_BLOCK_INDEX (i) != n_basic_blocks;
+ i++)
+ { /* Empty. */ }
+ for (insn = BASIC_BLOCK (i)->head;
+ NEXT_INSN (insn) != 0;
+ insn = NEXT_INSN (insn))
+ { /* Empty. */ }
+ set_last_insn (insn);
+
+ #if 0
+ /* Add NOTE_INSN_BLOCK_END */
+ for (i = 0; i < n_basic_blocks - 1; i++)
+ {
+ basic_block bb = BASIC_BLOCK (i);
+ int block_begin_cnt = 0, block_end_cnt = 0;
+
+ if (REORDER_BLOCK_INDEX (i) == n_basic_blocks - 1)
+ emit_note_after (NOTE_INSN_BLOCK_END, BASIC_BLOCK (i)->end);
+ if (REORDER_BLOCK_INDEX (i + 1) > REORDER_BLOCK_INDEX (i) + 1)
+ {
+
+ for (k = 0 ; k < REORDER_BLOCK_END (i); k++)
+ emit_note_after (NOTE_INSN_BLOCK_END, BASIC_BLOCK (k)->end);
+ for (j = i;
+ j < n_basic_blocks
+ && REORDER_BLOCK_INDEX (j) != REORDER_BLOCK_INDEX (i) + 1;
+ j++)
+ {
+ block_begin_cnt += REORDER_BLOCK_BEGIN (j);
+ block_end_cnt += REORDER_BLOCK_END (j);
+ }
+ if (REORDER_BLOCK_INDEX (j) == REORDER_BLOCK_INDEX (i) + 1)
+ {
+ block_begin_cnt += REORDER_BLOCK_BEGIN (j);
+ block_end_cnt += REORDER_BLOCK_END (j);
+ }
+ if (j == n_basic_blocks - 1)
+ block_end_cnt -= 1;
+ if (block_end_cnt > block_begin_cnt)
+ {
+ for (k = j - 1; REORDER_BLOCK_END (k) != 0; k--)
+ {
+ REORDER_BLOCK_END (k) -= 1;
+ }
+ for (k = 0 ; k < block_end_cnt - block_begin_cnt; k++)
+ emit_note_after (NOTE_INSN_BLOCK_END, BASIC_BLOCK (i)->end);
+ }
+ }
+ else
+ for (k = 0 ; k < REORDER_BLOCK_END (i); k++)
+ emit_note_after (NOTE_INSN_BLOCK_END, BASIC_BLOCK (k)->end);
+ }
+ #endif
+
+ /* Add jumps and labels to fixup blocks. */
+ for (i = 0; i < n_basic_blocks - 1; i++)
+ {
+ if (REORDER_BLOCK_ADD_JUMP (i))
+ {
+ rtx new_label = gen_label_rtx ();
+ rtx label_insn, jump_insn, barrier_insn;
+
+ label_insn = emit_label_before (new_label,
+ REORDER_BLOCK_ADD_JUMP (i)->head);
+ REORDER_BLOCK_ADD_JUMP (i)->head = label_insn;
+
+ jump_insn = emit_jump_insn_after (gen_jump (label_insn),
+ BASIC_BLOCK (i)->end);
+ JUMP_LABEL (jump_insn) = label_insn;
+ ++LABEL_NUSES (label_insn);
+ barrier_insn = emit_barrier_after (jump_insn);
+ if (GET_CODE (BASIC_BLOCK (i)->end) != JUMP_INSN)
+ BASIC_BLOCK (i)->end = barrier_insn;
+ /* Add block for jump. Typically this is when a then is not
+ predicted and we are jumping to the moved then block. */
+ else
+ {
+ basic_block b;
+
+ b = (basic_block) obstack_alloc (function_obstack, sizeof (*b));
+ VARRAY_GROW (basic_block_info, ++n_basic_blocks);
+ BASIC_BLOCK (n_basic_blocks - 1) = b;
+ b->index = n_basic_blocks - 1;
+ b->head = emit_note_before (NOTE_INSN_BASIC_BLOCK, jump_insn);
+ NOTE_BASIC_BLOCK (b->head) = b;
+ b->end = barrier_insn;
+
+ {
+ basic_block nb = BASIC_BLOCK (n_basic_blocks - 1);
+ nb->global_live_at_start
+ = OBSTACK_ALLOC_REG_SET (function_obstack);
+ nb->global_live_at_end
+ = OBSTACK_ALLOC_REG_SET (function_obstack);
+
+ COPY_REG_SET (nb->global_live_at_start,
+ BASIC_BLOCK (i)->global_live_at_start);
+ COPY_REG_SET (nb->global_live_at_end,
+ BASIC_BLOCK (i)->global_live_at_start);
+ if (BASIC_BLOCK (i)->local_set)
+ {
+ OBSTACK_ALLOC_REG_SET (function_obstack);
+ COPY_REG_SET (nb->local_set, BASIC_BLOCK (i)->local_set);
+ }
+ else
+ BASIC_BLOCK (nb->index)->local_set = 0;
+
+ nb->aux = xcalloc (1, sizeof (struct reorder_block_def));
+ REORDER_BLOCK_INDEX (n_basic_blocks - 1)
+ = REORDER_BLOCK_INDEX (i) + 1;
+ /* Relink to new block. */
+ nb->succ = BASIC_BLOCK (i)->succ;
+
+ make_edge (0, BASIC_BLOCK (i), nb, 0);
+ BASIC_BLOCK (i)->succ->succ_next
+ = BASIC_BLOCK (i)->succ->succ_next->succ_next;
+ nb->succ->succ_next = 0;
+ /* Fix reorder block index to reflect new block. */
+ for (j = 0; j < n_basic_blocks - 1; j++)
+ {
+ if (REORDER_BLOCK_INDEX (j) >= REORDER_BLOCK_INDEX (i) + 1)
+ REORDER_BLOCK_INDEX (j)++;
+ }
+ }
+ }
+ }
+ }
+ }
+
+
+ /* Reorder basic blocks. */
+
+ void
+ reorder_basic_blocks (dump_file)
+ FILE *dump_file;
+ {
+ int i, j;
+ struct loops loops_info;
+ int num_loops;
+ rtx last_insn;
+
+ if (profile_arc_flag)
+ return;
+
+ #if 0
+ if (debug_info_level > DINFO_LEVEL_TERSE)
+ fatal ("debug level greater than 1 not supported with -freorder-blocks");
+ #endif
+
+ /* Debugging information. */
+ rob_dump_file = dump_file;
+
+ /* Exception edges are not currently handled. */
+ for (i = 0; i < n_basic_blocks; i++)
+ {
+ edge e;
+
+ for (e = BASIC_BLOCK (i)->succ; e && ! (e->flags & EDGE_EH);
+ e = e->succ_next)
+ {
+ }
+ if (e && e->flags & EDGE_EH)
+ return;
+ }
+
+ reorder_index = 0;
+
+ if (n_basic_blocks <= 1)
+ {
+ return;
+ }
+
+ /* Find natural loops using the CFG. */
+ num_loops = flow_loops_find (&loops_info);
+
+ /* Dump loop information. */
+ flow_loops_dump (&loops_info, dump_file, 0);
+
+ /* Estimate using heuristics if no profiling info is available. */
+ if (! flag_branch_probabilities)
+ estimate_probability (&loops_info);
+
+ reorder_last_visited = BASIC_BLOCK (0);
+
+ for (i = 0; i < n_basic_blocks; i++)
+ {
+ BASIC_BLOCK (i)->aux = xcalloc (1, sizeof (struct reorder_block_def));
+ }
+
+ last_insn
+ = NEXT_INSN (skip_insns_between_block (BASIC_BLOCK (n_basic_blocks - 1),
+ REORDER_SKIP_AFTER));
+
+ make_reorder_chain (0);
+
+ fixup_reorder_chain (0);
+
+ if (dump_file)
+ {
+ rtx insn, last_insn;
+ last_insn = get_insns ();
+ for (insn = NEXT_INSN (get_insns ());
+ insn && PREV_INSN (insn) == last_insn
+ && NEXT_INSN (PREV_INSN (insn)) == insn;
+ last_insn = insn,
+ insn = NEXT_INSN (insn))
+ { /* Empty. */};
+ if (insn)
+ {
+ warning ("insn chaining error at %d while reordering basic blocks\n",
+ INSN_UID (last_insn));
+ fprintf (rob_dump_file, "insn chaining error at %d\n",
+ INSN_UID (last_insn));
+ }
+ }
+
+ /* Put basic_block_info in new order. */
+ for (i = 0; i < n_basic_blocks - 1; i++)
+ {
+ for (j = i; i != REORDER_BLOCK_INDEX (j); j++)
+ { /* Empty. */ }
+ if (REORDER_BLOCK_INDEX (j) == i
+ && i != j)
+ {
+ basic_block tempbb;
+ int temprbi;
+ int rbi = REORDER_BLOCK_INDEX (j);
+
+ temprbi = BASIC_BLOCK (rbi)->index;
+ BASIC_BLOCK (rbi)->index = BASIC_BLOCK (j)->index;
+ BASIC_BLOCK (j)->index = temprbi;
+ tempbb = BASIC_BLOCK (rbi);
+ BASIC_BLOCK (rbi) = BASIC_BLOCK (j);
+ BASIC_BLOCK (j) = tempbb;
+ }
+ }
+
+ NEXT_INSN (BASIC_BLOCK (n_basic_blocks - 1)->end) = last_insn;
+
+ for (i = 0; i < n_basic_blocks - 1; i++)
+ {
+ free (BASIC_BLOCK (i)->aux);
+ }
+
+ /* Free loop information. */
+ flow_loops_free (&loops_info);
+ }
+