This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
bb-reorder cleanups
- To: gcc-patches at gcc dot gnu dot org, rth at cygnus dot com, patches at x86-64 dot org
- Subject: bb-reorder cleanups
- From: Jan Hubicka <jh at suse dot cz>
- Date: Thu, 30 Aug 2001 15:25:33 +0200
Hi,
this patch contains some peraration work for my future patches on bb-reorder.
It does not change functionality, but cleanups the code, fixes some bugs (that
don't show unless you do BB duplication) and add some sanity checking.
The changes are somewhat interwinded and it is dificult to split them up.
I've removed the index filed of RBI record, as it is dificult to maitain when
the algorithm does not home the basic blocks lineary. It does not have real
purpose, as it is redundant with the linked list maitained too.
It was usefull mostly for debugging, but now I simply dump the new sequence
at the end and I've found it easier to use than the former.
Aditinally I've added number of missing set_block_for_insn, as otherwise BB
merging after reordering dies.
Bootstrapped/regtested i686 together with other today patches and simple code
to do BB duplication.
In meantime I am testing the Sparc and PPC.
Honza
Thu Aug 30 15:08:27 CEST 2001 Jan Hubicka <jh@suse.cz>
* bb-reorder.c (reorder_block_def): Remove 'index'.
(insert_intra_1): Add argument BB, set block for new note.
(make_reorder_chain): Do not depdent on BB indexes.
(make_reorder_chain_1): Do not use BB indexes.
(label_for_bb): Likewise; set BB for new insn.
(emit_jump_to_block_after): Likewise.
(fixup_reoder_chain): Sanity check that all basic blocks
are chained; verify newly created insn chain; remove
undocnitional jump simplifying; Do not use BB indexes;
properly initialize count and frequency information;
dump reordered sequence.
(insert_intra_bb_scope_notes): update call of insert_intra_1;
handle duplicated basic blocks.
(insert_inter_bb_scope_notes): Set block for new insn.
(reorder_basic_blocks): Dump flow info before reoredering.
*** bb-reorder.c.orig Sun Aug 5 17:58:25 2001
--- bb-reorder.c Wed Aug 29 13:25:55 2001
*************** typedef struct reorder_block_def
*** 165,171 ****
rtx eff_end;
scope scope;
basic_block next;
- int index;
int visited;
} *reorder_block_def;
--- 165,170 ----
*************** static void relate_bbs_with_scopes PARAM
*** 184,190 ****
static scope make_new_scope PARAMS ((int, rtx));
static void build_scope_forest PARAMS ((scope_forest_info *));
static void remove_scope_notes PARAMS ((void));
! static void insert_intra_1 PARAMS ((scope, rtx *));
static void insert_intra_bb_scope_notes PARAMS ((basic_block));
static void insert_inter_bb_scope_notes PARAMS ((basic_block, basic_block));
static void rebuild_scope_notes PARAMS ((scope_forest_info *));
--- 184,190 ----
static scope make_new_scope PARAMS ((int, rtx));
static void build_scope_forest PARAMS ((scope_forest_info *));
static void remove_scope_notes PARAMS ((void));
! static void insert_intra_1 PARAMS ((scope, rtx *, basic_block));
static void insert_intra_bb_scope_notes PARAMS ((basic_block));
static void insert_inter_bb_scope_notes PARAMS ((basic_block, basic_block));
static void rebuild_scope_notes PARAMS ((scope_forest_info *));
*************** make_reorder_chain ()
*** 319,324 ****
--- 591,597 ----
basic_block last_block = NULL;
basic_block prev = NULL;
int nbb_m1 = n_basic_blocks - 1;
+ basic_block next;
/* If we've not got epilogue in RTL, we must fallthru to the exit.
Force the last block to be at the end. */
*************** make_reorder_chain ()
*** 335,341 ****
do
{
int i;
! basic_block next = NULL;
/* Find the next unplaced block. */
/* ??? Get rid of this loop, and track which blocks are not yet
--- 608,615 ----
do
{
int i;
!
! next = NULL;
/* Find the next unplaced block. */
/* ??? Get rid of this loop, and track which blocks are not yet
*************** make_reorder_chain ()
*** 344,370 ****
remove from the list as we place. The head of that list is
what we're looking for here. */
! for (i = 0; i <= nbb_m1; ++i)
{
basic_block bb = BASIC_BLOCK (i);
if (! RBI (bb)->visited)
! {
! next = bb;
! break;
! }
}
! if (! next)
! abort ();
!
! prev = make_reorder_chain_1 (next, prev);
}
! while (RBI (prev)->index < nbb_m1);
/* Terminate the chain. */
if (! HAVE_epilogue)
{
RBI (prev)->next = last_block;
- RBI (last_block)->index = RBI (prev)->index + 1;
prev = last_block;
}
RBI (prev)->next = NULL;
--- 618,638 ----
remove from the list as we place. The head of that list is
what we're looking for here. */
! for (i = 0; i <= nbb_m1 && !next; ++i)
{
basic_block bb = BASIC_BLOCK (i);
if (! RBI (bb)->visited)
! next = bb;
}
! if (next)
! prev = make_reorder_chain_1 (next, prev);
}
! while (next);
/* Terminate the chain. */
if (! HAVE_epilogue)
{
RBI (prev)->next = last_block;
prev = last_block;
}
RBI (prev)->next = NULL;
*************** make_reorder_chain_1 (bb, prev)
*** 393,411 ****
/* Mark this block visited. */
if (prev)
{
- int new_index;
-
restart:
RBI (prev)->next = bb;
- new_index = RBI (prev)->index + 1;
- RBI (bb)->index = new_index;
if (rtl_dump_file && prev->index + 1 != bb->index)
! fprintf (rtl_dump_file, "Reordering block %d (%d) after %d (%d)\n",
! bb->index, RBI (bb)->index, prev->index, RBI (prev)->index);
}
else
! RBI (bb)->index = 0;
RBI (bb)->visited = 1;
prev = bb;
--- 661,678 ----
/* Mark this block visited. */
if (prev)
{
restart:
RBI (prev)->next = bb;
if (rtl_dump_file && prev->index + 1 != bb->index)
! fprintf (rtl_dump_file, "Reordering block %d after %d\n",
! bb->index, prev->index);
}
else
! {
! if (bb->index != 0)
! abort ();
! }
RBI (bb)->visited = 1;
prev = bb;
*************** label_for_bb (bb)
*** 504,516 ****
if (GET_CODE (label) != CODE_LABEL)
{
if (rtl_dump_file)
! fprintf (rtl_dump_file, "Emitting label for block %d (%d)\n",
! bb->index, RBI (bb)->index);
label = emit_label_before (gen_label_rtx (), label);
if (bb->head == RBI (bb)->eff_head)
RBI (bb)->eff_head = label;
bb->head = label;
}
return label;
--- 835,849 ----
if (GET_CODE (label) != CODE_LABEL)
{
if (rtl_dump_file)
! fprintf (rtl_dump_file, "Emitting label for block %d\n",
! bb->index);
label = emit_label_before (gen_label_rtx (), label);
if (bb->head == RBI (bb)->eff_head)
RBI (bb)->eff_head = label;
bb->head = label;
+ if (basic_block_for_insn)
+ set_block_for_insn (label, bb);
}
return label;
*************** emit_jump_to_block_after (bb, after)
*** 536,543 ****
set_block_for_new_insns (jump, bb);
if (rtl_dump_file)
! fprintf (rtl_dump_file, "Emitting jump to block %d (%d)\n",
! bb->index, RBI (bb)->index);
}
else
{
--- 869,876 ----
set_block_for_new_insns (jump, bb);
if (rtl_dump_file)
! fprintf (rtl_dump_file, "Emitting jump to block %d\n",
! bb->index);
}
else
{
*************** emit_jump_to_block_after (bb, after)
*** 545,550 ****
--- 878,885 ----
if (! HAVE_return)
abort ();
jump = emit_jump_insn_after (gen_return (), after);
+ if (basic_block_for_insn)
+ set_block_for_new_insns (jump, bb);
if (rtl_dump_file)
fprintf (rtl_dump_file, "Emitting return\n");
*************** static void
*** 563,574 ****
--- 898,911 ----
fixup_reorder_chain ()
{
basic_block bb, last_bb;
+ int index;
/* First do the bulk reordering -- rechain the blocks without regard to
the needed changes to jumps and labels. */
last_bb = BASIC_BLOCK (0);
bb = RBI (last_bb)->next;
+ index = 1;
while (bb)
{
rtx last_e = RBI (last_bb)->eff_end;
*************** fixup_reorder_chain ()
*** 579,587 ****
--- 916,930 ----
last_bb = bb;
bb = RBI (bb)->next;
+ index++;
}
NEXT_INSN (RBI (last_bb)->eff_end) = NULL_RTX;
set_last_insn (RBI (last_bb)->eff_end);
+ if (index != n_basic_blocks)
+ abort ();
+ #ifdef ENABLE_CHECKING
+ verify_insn_chain ();
+ #endif
/* Now add jumps and labels as needed to match the blocks new
outgoing edges. */
*************** fixup_reorder_chain ()
*** 607,633 ****
bb_end_insn = bb->end;
if (GET_CODE (bb_end_insn) == JUMP_INSN)
{
! if (any_uncondjump_p (bb_end_insn))
! {
! /* If the destination is still not next, nothing to do. */
! if (RBI (bb)->index + 1 != RBI (e_taken->dest)->index)
! continue;
!
! /* Otherwise, we can remove the jump and cleanup the edge. */
! tidy_fallthru_edge (e_taken, bb, e_taken->dest);
! RBI (bb)->eff_end = skip_insns_after_block (bb);
! RBI (e_taken->dest)->eff_head = NEXT_INSN (RBI (bb)->eff_end);
!
! if (rtl_dump_file)
! fprintf (rtl_dump_file, "Removing jump in block %d (%d)\n",
! bb->index, RBI (bb)->index);
! continue;
! }
! else if (any_condjump_p (bb_end_insn))
{
/* If the old fallthru is still next, nothing to do. */
! if (RBI (bb)->index + 1 == RBI (e_fall->dest)->index
! || (RBI (bb)->index == n_basic_blocks - 1
&& e_fall->dest == EXIT_BLOCK_PTR))
continue;
--- 950,960 ----
bb_end_insn = bb->end;
if (GET_CODE (bb_end_insn) == JUMP_INSN)
{
! if (any_condjump_p (bb_end_insn))
{
/* If the old fallthru is still next, nothing to do. */
! if (RBI (bb)->next == e_fall->dest
! || (!RBI (bb)->next
&& e_fall->dest == EXIT_BLOCK_PTR))
continue;
*************** fixup_reorder_chain ()
*** 635,641 ****
such as happens at the very end of a function, then we'll
need to add a new unconditional jump. Choose the taken
edge based on known or assumed probability. */
! if (RBI (bb)->index + 1 != RBI (e_taken->dest)->index)
{
rtx note = find_reg_note (bb_end_insn, REG_BR_PROB, 0);
if (note
--- 962,968 ----
such as happens at the very end of a function, then we'll
need to add a new unconditional jump. Choose the taken
edge based on known or assumed probability. */
! if (RBI (bb)->next != e_taken->dest)
{
rtx note = find_reg_note (bb_end_insn, REG_BR_PROB, 0);
if (note
*************** fixup_reorder_chain ()
*** 670,676 ****
#ifdef CASE_DROPS_THROUGH
/* Except for VAX. Since we didn't have predication for the
tablejump, the fallthru block should not have moved. */
! if (RBI (bb)->index + 1 == RBI (e_fall->dest)->index)
continue;
bb_end_insn = skip_insns_after_block (bb);
#else
--- 997,1003 ----
#ifdef CASE_DROPS_THROUGH
/* Except for VAX. Since we didn't have predication for the
tablejump, the fallthru block should not have moved. */
! if (RBI (bb)->next == e_fall->dest)
continue;
bb_end_insn = skip_insns_after_block (bb);
#else
*************** fixup_reorder_chain ()
*** 687,695 ****
continue;
/* If the fallthru block is still next, nothing to do. */
! if (RBI (bb)->index + 1 == RBI (e_fall->dest)->index
! || (RBI (bb)->index == n_basic_blocks - 1
! && e_fall->dest == EXIT_BLOCK_PTR))
continue;
/* We need a new jump insn. If the block has only one outgoing
--- 1014,1020 ----
continue;
/* If the fallthru block is still next, nothing to do. */
! if (RBI (bb)->next == e_fall->dest)
continue;
/* We need a new jump insn. If the block has only one outgoing
*************** fixup_reorder_chain ()
*** 716,725 ****
create_basic_block (n_basic_blocks - 1, jump_insn, jump_insn, NULL);
nb = BASIC_BLOCK (n_basic_blocks - 1);
- nb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
- nb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
nb->local_set = 0;
COPY_REG_SET (nb->global_live_at_start, bb->global_live_at_start);
COPY_REG_SET (nb->global_live_at_end, bb->global_live_at_start);
--- 1041,1052 ----
create_basic_block (n_basic_blocks - 1, jump_insn, jump_insn, NULL);
nb = BASIC_BLOCK (n_basic_blocks - 1);
nb->local_set = 0;
+ nb->count = e_fall->count;
+ nb->frequency = EDGE_FREQUENCY (e_fall);
+ nb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
+ nb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
COPY_REG_SET (nb->global_live_at_start, bb->global_live_at_start);
COPY_REG_SET (nb->global_live_at_end, bb->global_live_at_start);
*************** fixup_reorder_chain ()
*** 727,733 ****
RBI (nb)->eff_head = nb->head;
RBI (nb)->eff_end = barrier_insn;
RBI (nb)->scope = RBI (bb)->scope;
- RBI (nb)->index = RBI (bb)->index + 1;
RBI (nb)->visited = 1;
RBI (nb)->next = RBI (bb)->next;
RBI (bb)->next = nb;
--- 1054,1059 ----
*************** fixup_reorder_chain ()
*** 735,754 ****
/* Link to new block. */
make_edge (NULL, nb, e_fall->dest, 0);
redirect_edge_succ (e_fall, nb);
/* Don't process this new block. */
bb = nb;
-
- /* Fix subsequent reorder block indices to reflect new block. */
- while ((nb = RBI (nb)->next) != NULL)
- RBI (nb)->index += 1;
}
/* Put basic_block_info in the new order. */
! for (bb = BASIC_BLOCK (0); bb ; bb = RBI (bb)->next)
{
! bb->index = RBI (bb)->index;
! BASIC_BLOCK (bb->index) = bb;
}
}
--- 1061,1086 ----
/* Link to new block. */
make_edge (NULL, nb, e_fall->dest, 0);
redirect_edge_succ (e_fall, nb);
+ nb->succ->count = e_fall->count;
+ nb->succ->probability = REG_BR_PROB_BASE;
/* Don't process this new block. */
bb = nb;
}
/* Put basic_block_info in the new order. */
! bb = BASIC_BLOCK (0);
! index = 0;
!
! if (rtl_dump_file)
! fprintf (rtl_dump_file, "Reordered sequence:\n");
! while (bb)
{
! bb->index = index;
! BASIC_BLOCK (index) = bb;
!
! bb = RBI (bb)->next;
! index++;
}
}
*************** remove_scope_notes ()
*** 1124,1132 ****
/* Insert scope note pairs for a contained scope tree S after insn IP. */
static void
! insert_intra_1 (s, ip)
scope s;
rtx *ip;
{
scope p;
--- 1456,1465 ----
/* Insert scope note pairs for a contained scope tree S after insn IP. */
static void
! insert_intra_1 (s, ip, bb)
scope s;
rtx *ip;
+ basic_block bb;
{
scope p;
*************** insert_intra_1 (s, ip)
*** 1134,1148 ****
{
*ip = emit_note_after (NOTE_INSN_BLOCK_BEG, *ip);
NOTE_BLOCK (*ip) = NOTE_BLOCK (s->note_beg);
}
for (p = s->inner; p; p = p->next)
! insert_intra_1 (p, ip);
if (NOTE_BLOCK (s->note_beg))
{
*ip = emit_note_after (NOTE_INSN_BLOCK_END, *ip);
NOTE_BLOCK (*ip) = NOTE_BLOCK (s->note_end);
}
}
--- 1467,1485 ----
{
*ip = emit_note_after (NOTE_INSN_BLOCK_BEG, *ip);
NOTE_BLOCK (*ip) = NOTE_BLOCK (s->note_beg);
+ if (basic_block_for_insn)
+ set_block_for_insn (*ip, bb);
}
for (p = s->inner; p; p = p->next)
! insert_intra_1 (p, ip, bb);
if (NOTE_BLOCK (s->note_beg))
{
*ip = emit_note_after (NOTE_INSN_BLOCK_END, *ip);
NOTE_BLOCK (*ip) = NOTE_BLOCK (s->note_end);
+ if (basic_block_for_insn)
+ set_block_for_insn (*ip, bb);
}
}
*************** insert_intra_bb_scope_notes (bb)
*** 1167,1174 ****
for (p = s->inner; p; p = p->next)
{
! if (p->bb_beg != NULL && p->bb_beg == p->bb_end && p->bb_beg == bb)
! insert_intra_1 (p, &ip);
}
}
--- 1504,1513 ----
for (p = s->inner; p; p = p->next)
{
! /* In case of duplicated basic block, the bb_beg and bb_end don't need
! to match the bb itself. */
! if (p->bb_beg != NULL && p->bb_beg == p->bb_end)
! insert_intra_1 (p, &ip, bb);
}
}
*************** insert_inter_bb_scope_notes (bb1, bb2)
*** 1236,1241 ****
--- 1575,1582 ----
{
ip = emit_note_after (NOTE_INSN_BLOCK_END, ip);
NOTE_BLOCK (ip) = NOTE_BLOCK (s->note_end);
+ if (basic_block_for_insn)
+ set_block_for_insn (ip, bb1);
}
s = s->outer;
}
*************** insert_inter_bb_scope_notes (bb1, bb2)
*** 1252,1257 ****
--- 1593,1600 ----
{
ip = emit_note_before (NOTE_INSN_BLOCK_BEG, ip);
NOTE_BLOCK (ip) = NOTE_BLOCK (s->note_beg);
+ if (basic_block_for_insn)
+ set_block_for_insn (ip, bb2);
}
s = s->outer;
}
*************** reorder_basic_blocks ()
*** 1393,1400 ****
build_scope_forest (&forest);
remove_scope_notes ();
!
record_effective_endpoints ();
make_reorder_chain ();
fixup_reorder_chain ();
--- 1736,1748 ----
build_scope_forest (&forest);
remove_scope_notes ();
record_effective_endpoints ();
+
+ if (rtl_dump_file)
+ dump_flow_info (rtl_dump_file);
+
make_reorder_chain ();
fixup_reorder_chain ();