This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
bb-reorder rewrite
- To: jle at cygnus dot com, scox at cygnus dot com
- Subject: bb-reorder rewrite
- From: Richard Henderson <rth at twiddle dot net>
- Date: Mon, 22 May 2000 00:49:37 -0700
- Cc: gcc-patches at gcc dot gnu dot org
While reviewing Jan's profile.c rewrite, I ran across a testcase
(which I now can't find again, annoyingly) in which -freorder-blocks
appeared to not be recognizing that it needed to perform a
transformation. On closer examination, it did. But bb-reorder
is written expecting jump2 to come along and fix up all the
jump-to-next and jump-over-jump cases that it introduces.
What happened is that jump2 decided to fix up several of the jumps
by *undoing* the rearrangement bb-reorder had effected.
Given that this sort of thing is possible, and that long-term we'd
like to reduce or eliminate jump_optimize, it seems clear that
bb-reorder should do the entire transformation itself. This isn't
really as bad as it sounds, though, since there already exist
utility functions (mainly invert_jump) to help us out.
At first I just started to rearrange fixup_reorder_chain, but I
soon discovered that the ADD_JUMP flag was largely inaccurate for
the kind of thing I wanted to do. Worse, chain_reorder_blocks
was largely inscrutible -- it talked about "predict then" and
"predict else" without doing any sort of prediction at all as
far as I could tell. The only real work it seemed to do was the
bulk rechaining of the insns.
What I have here cleanly divides the work into two independant parts:
First, make_reorder_chain constructs an ordering for the blocks.
It does not change anything whatsoever. My thinking is that we can
now more easily substitute more clever ordering algorithms. (See
the big block comment at the top of the file for ideas.)
Second, fixup_reorder_chain implements everything needed to
realize the previously constructed ordering.
Bootstrapped on alphaev67-linux; I'll wait til I can test something
else as well before checking it in.
r~
* bb-reorder.c (reorder_block_def): Reorder elements for size.
Remove add_jump; add next; replace flags with visited.
(rbd_init): Remove.
(REORDER_BLOCK_HEAD, REORDER_BLOCK_VISITED): Remove.
(REORDER_BLOCK_FLAGS, REORDER_BLOCK_INDEX): Remove.
(REORDER_BLOCK_ADD_JUMP, REORDER_BLOCK_EFF_HEAD): Remove.
(REORDER_BLOCK_EFF_END, REORDER_BLOCK_SCOPE): Remove.
(RBI): New.
(reorder_index, reorder_last_visited): Remove.
(skip_insns_after_block): Rewrite to use a switch.
(get_common_dest): Remove.
(chain_reorder_blocks): Remove.
(record_effective_endpoints): Split out from reorder_basic_blocks.
(make_reorder_chain): Likewise. Loop until all blocks are placed.
(make_reorder_chain_1): Renamed from old make_reorder_chain.
Only construct the reorder chain, do not move insns. Try harder
to tail recurse.
(label_for_bb, emit_jump_to_block_after): New.
(fixup_reorder_chain): Use them. Do bulk block movement. Examine
and adjust the jump insns appropriately. Fixup basic_block_info.
(verify_insn_chain): Always define.
(relate_bbs_with_scopes): Call xmalloc, not xcalloc. Fix thinko
in allocation size.
(make_new_scope): Don't write zeros to calloc'd space.
(build_scope_forest): Rely on xrealloc to DTRT.
(reorder_basic_blocks): Don't build loop nest. Don't fail if
profile_arc_flag. Streamline EH test.
* flow.c (tidy_fallthru_edge): Use any_uncondjump_p.
* jump.c (can_reverse_comparison_p): Be prepared for insn null.
Index: bb-reorder.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/bb-reorder.c,v
retrieving revision 1.14
diff -c -p -d -r1.14 bb-reorder.c
*** bb-reorder.c 2000/05/19 22:27:26 1.14
--- bb-reorder.c 2000/05/22 07:07:32
***************
*** 22,27 ****
--- 22,83 ----
"Profile Guided Code Positioning"
Pettis and Hanson; PLDI '90.
+
+ TODO:
+
+ (1) Consider:
+
+ if (p) goto A; // predict taken
+ foo ();
+ A:
+ if (q) goto B; // predict taken
+ bar ();
+ B:
+ baz ();
+ return;
+
+ We'll currently reorder this as
+
+ if (!p) goto C;
+ A:
+ if (!q) goto D;
+ B:
+ baz ();
+ return;
+ D:
+ bar ();
+ goto B;
+ C:
+ foo ();
+ goto A;
+
+ A better ordering is
+
+ if (!p) goto C;
+ if (!q) goto D;
+ B:
+ baz ();
+ return;
+ C:
+ foo ();
+ if (q) goto B;
+ D:
+ bar ();
+ goto B;
+
+ This requires that we be able to duplicate the jump at A, and
+ adjust the graph traversal such that greedy placement doesn't
+ fix D before C is considered.
+
+ (2) Coordinate with shorten_branches to minimize the number of
+ long branches.
+
+ (3) Invent a method by which sufficiently non-predicted code can
+ be moved to either the end of the section or another section
+ entirely. Some sort of NOTE_INSN note would work fine.
+
+ This completely scroggs all debugging formats, so the user
+ would have to explicitly ask for it.
*/
#include "config.h"
***************
*** 44,49 ****
--- 100,110 ----
#include "obstack.h"
+ #ifndef HAVE_epilogue
+ #define HAVE_epilogue 0
+ #endif
+
+
/* The contents of the current function definition are allocated
in this obstack, and all are freed at the end of the function.
For top-level functions, this is temporary_obstack.
*************** typedef struct scope_def
*** 88,93 ****
--- 149,155 ----
struct scope_def *next;
} *scope;
+
/* Structure to hold information about the scope forest. */
typedef struct
{
*************** typedef struct
*** 98,159 ****
scope *trees;
} scope_forest_info;
!
! typedef struct reorder_block_def {
! int flags;
! int index;
! basic_block add_jump;
rtx eff_head;
rtx eff_end;
scope scope;
} *reorder_block_def;
-
- static struct reorder_block_def rbd_init
- = {
- 0, /* flags */
- 0, /* index */
- NULL, /* add_jump */
- NULL_RTX, /* eff_head */
- NULL_RTX, /* eff_end */
- NULL /* scope */
- };
-
-
- #define REORDER_BLOCK_HEAD 0x1
- #define REORDER_BLOCK_VISITED 0x2
-
- #define REORDER_BLOCK_FLAGS(bb) \
- ((reorder_block_def) (bb)->aux)->flags
-
- #define REORDER_BLOCK_INDEX(bb) \
- ((reorder_block_def) (bb)->aux)->index
-
- #define REORDER_BLOCK_ADD_JUMP(bb) \
- ((reorder_block_def) (bb)->aux)->add_jump
-
- #define REORDER_BLOCK_EFF_HEAD(bb) \
- ((reorder_block_def) (bb)->aux)->eff_head
! #define REORDER_BLOCK_EFF_END(bb) \
! ((reorder_block_def) (bb)->aux)->eff_end
!
! #define REORDER_BLOCK_SCOPE(bb) \
! ((reorder_block_def) (bb)->aux)->scope
!
!
! static int reorder_index;
! static basic_block reorder_last_visited;
/* Local function prototypes. */
static rtx skip_insns_after_block PARAMS ((basic_block));
! static basic_block get_common_dest PARAMS ((basic_block, basic_block));
! static basic_block chain_reorder_blocks PARAMS ((edge, basic_block));
! static void make_reorder_chain PARAMS ((basic_block));
static void fixup_reorder_chain PARAMS ((void));
- #ifdef ENABLE_CHECKING
- static void verify_insn_chain PARAMS ((void));
- #endif
static void relate_bbs_with_scopes PARAMS ((scope));
static scope make_new_scope PARAMS ((int, rtx));
static void build_scope_forest PARAMS ((scope_forest_info *));
--- 160,187 ----
scope *trees;
} scope_forest_info;
! /* Structure to hold information about the blocks during reordering. */
! typedef struct reorder_block_def
! {
rtx eff_head;
rtx eff_end;
scope scope;
+ basic_block next;
+ int index;
+ int visited;
} *reorder_block_def;
! #define RBI(BB) ((reorder_block_def) (BB)->aux)
/* Local function prototypes. */
static rtx skip_insns_after_block PARAMS ((basic_block));
! static void record_effective_endpoints PARAMS ((void));
! static void make_reorder_chain PARAMS ((void));
! static basic_block make_reorder_chain_1 PARAMS ((basic_block, basic_block));
! static rtx label_for_bb PARAMS ((basic_block));
! static rtx emit_jump_to_block_after PARAMS ((basic_block, rtx));
static void fixup_reorder_chain PARAMS ((void));
static void relate_bbs_with_scopes PARAMS ((scope));
static scope make_new_scope PARAMS ((int, rtx));
static void build_scope_forest PARAMS ((scope_forest_info *));
*************** static void dump_scope_forest_1 PARAMS
*** 169,174 ****
--- 197,204 ----
static rtx get_next_bb_note PARAMS ((rtx));
static rtx get_prev_bb_note PARAMS ((rtx));
+ void verify_insn_chain PARAMS ((void));
+
/* Skip over inter-block insns occurring after BB which are typically
associated with BB (e.g., barriers). If there are any such insns,
we return the last one. Otherwise, we return the end of BB. */
*************** static rtx
*** 177,219 ****
skip_insns_after_block (bb)
basic_block bb;
{
! rtx insn, last_insn;
!
! last_insn = bb->end;
! if (bb == EXIT_BLOCK_PTR)
! 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;
- }
! /* Skip to next non-deleted insn. */
! if (GET_CODE (insn) == NOTE
! && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED
! || NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED_LABEL))
! continue;
break;
}
--- 207,257 ----
skip_insns_after_block (bb)
basic_block bb;
{
! rtx insn, last_insn, next_head;
! next_head = NULL_RTX;
! if (bb->index + 1 != n_basic_blocks)
! next_head = BASIC_BLOCK (bb->index + 1)->head;
! for (last_insn = bb->end; (insn = NEXT_INSN (last_insn)); last_insn = insn)
{
! if (insn == next_head)
break;
! switch (GET_CODE (insn))
{
! case BARRIER:
continue;
! case NOTE:
! switch (NOTE_LINE_NUMBER (insn))
! {
! case NOTE_INSN_LOOP_END:
! case NOTE_INSN_BLOCK_END:
! case NOTE_INSN_DELETED:
! case NOTE_INSN_DELETED_LABEL:
! continue;
!
! default:
! break;
! }
! break;
!
! case CODE_LABEL:
! if (NEXT_INSN (insn)
! && 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;
+ default:
+ break;
+ }
+
break;
}
*************** skip_insns_after_block (bb)
*** 221,652 ****
}
! /* 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;
! rtx cebe_insn, dbh_insn, dbe_insn;
! edge ee, last_edge;
! edge e_fallthru, e_jump;
!
! 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 (rtl_dump_file)
! fprintf (rtl_dump_file,
! "Edge from basic block %d to basic block %d last visited %d\n",
! sb->index, db->index, ceb->index);
! cebe_insn = REORDER_BLOCK_EFF_END (ceb);
!
! /* Blocks are in original order. */
! if (sb->index == ceb->index
! && ceb->index + 1 == db->index && NEXT_INSN (cebe_insn))
! return db;
! e_fallthru = e_jump = e;
! /* 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)
! {
! if (e == sb->succ)
! e_jump = sb->succ->succ_next;
! else if (e == sb->succ->succ_next)
! e_jump = sb->succ;
! else
! abort ();
! }
! else
! {
! if (e == sb->succ)
! e_fallthru = sb->succ->succ_next;
! else if (e == sb->succ->succ_next)
! e_fallthru = sb->succ;
! else
! abort ();
! }
! if (e->flags & EDGE_FALLTHRU)
! cond_block_type = THEN_BLOCK;
! else if (get_common_dest (e_fallthru->dest, sb))
! cond_block_type = NO_ELSE_BLOCK;
! else
! cond_block_type = ELSE_BLOCK;
! if (get_common_dest (e_fallthru->dest, sb))
! {
! if (cond_block_type == THEN_BLOCK)
! {
! if (! (REORDER_BLOCK_FLAGS (e->dest)
! & 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 (e->dest)
! & 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 (e->dest)
! & REORDER_BLOCK_VISITED))
! cond_type = PREDICT_THEN_WITH_ELSE;
! else
! cond_type = PREDICT_ELSE;
! }
! else if (cond_block_type == ELSE_BLOCK
! && e_fallthru->dest != EXIT_BLOCK_PTR)
{
! if (! (REORDER_BLOCK_FLAGS (e->dest)
! & REORDER_BLOCK_VISITED))
! cond_type = PREDICT_ELSE;
! else
! cond_type = PREDICT_THEN_WITH_ELSE;
}
}
! }
!
! if (rtl_dump_file)
! {
! static const char * cond_type_str [] = {"not cond jump", "predict then",
! "predict else",
! "predict then w/o else",
! "predict not then w/o else"};
! static const char * cond_block_type_str [] = {"not then or else block",
! "then block",
! "else block",
! "then w/o else block"};
! fprintf (rtl_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 (rtl_dump_file)
! fprintf (rtl_dump_file,
! " then jump from block %d to block %d\n",
! sb->index, e_fallthru->dest->index);
!
! /* Jump to reordered then block. */
! REORDER_BLOCK_ADD_JUMP (sb) = e_fallthru->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)
! {
! basic_block jbb = e_fallthru->dest;
! for (ee = jbb->succ;
! ee && ! (ee->flags & EDGE_FALLTHRU);
! ee = ee->succ_next)
! continue;
! if (ee && ! (GET_CODE (jbb->end) == JUMP_INSN
! && ! simplejump_p (jbb->end)))
! {
! REORDER_BLOCK_ADD_JUMP (jbb) = 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 != EXIT_BLOCK_PTR
! && GET_CODE (last_edge->dest->head) == CODE_LABEL
! && ! (GET_CODE (db->end) == JUMP_INSN))
! {
! if (rtl_dump_file)
! fprintf (rtl_dump_file,
! " else jump from block %d to block %d\n",
! db->index, last_edge->dest->index);
! REORDER_BLOCK_ADD_JUMP (db) = 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)
! continue;
! if (last_edge
! && last_edge->dest != EXIT_BLOCK_PTR
! && (REORDER_BLOCK_FLAGS (last_edge->dest)
! & REORDER_BLOCK_VISITED))
{
! if (rtl_dump_file)
! fprintf (rtl_dump_file,
! " end of chain jump from block %d to block %d\n",
! db->index, last_edge->dest->index);
! REORDER_BLOCK_ADD_JUMP (db) = last_edge->dest;
}
! dbh_insn = REORDER_BLOCK_EFF_HEAD (db);
! cebe_insn = REORDER_BLOCK_EFF_END (ceb);
! dbe_insn = REORDER_BLOCK_EFF_END (db);
! /* Rechain predicted block. */
! NEXT_INSN (cebe_insn) = dbh_insn;
! PREV_INSN (dbh_insn) = cebe_insn;
! if (db->index != n_basic_blocks - 1)
! NEXT_INSN (dbe_insn) = 0;
! return db;
}
! /* Reorder blocks starting at block BB. */
! static void
! make_reorder_chain (bb)
basic_block bb;
{
! edge e;
! basic_block visited_edge = NULL;
! rtx block_end;
! int probability;
!
! if (bb == EXIT_BLOCK_PTR)
! 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 = INTVAL (XEXP (note, 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 != EXIT_BLOCK_PTR
! && e->dest != e->src
! && (! (REORDER_BLOCK_FLAGS (e->dest) & REORDER_BLOCK_VISITED)
! || (REORDER_BLOCK_FLAGS (e->dest) == REORDER_BLOCK_HEAD)))
! {
! if (! (REORDER_BLOCK_FLAGS (bb) & REORDER_BLOCK_VISITED))
! {
! REORDER_BLOCK_FLAGS (bb) |= REORDER_BLOCK_HEAD;
! REORDER_BLOCK_INDEX (bb) = reorder_index++;
! REORDER_BLOCK_FLAGS (bb) |= REORDER_BLOCK_VISITED;
! }
- if (REORDER_BLOCK_FLAGS (e->dest) & REORDER_BLOCK_VISITED)
- REORDER_BLOCK_FLAGS (e->dest) &= ~REORDER_BLOCK_HEAD;
-
- visited_edge = e->dest;
! reorder_last_visited = chain_reorder_blocks (e, bb);
! if (e->dest
! && ! (REORDER_BLOCK_FLAGS (e->dest)
! & REORDER_BLOCK_VISITED))
! make_reorder_chain (e->dest);
! }
! else
{
! if (! (REORDER_BLOCK_FLAGS (bb) & REORDER_BLOCK_VISITED))
! {
! REORDER_BLOCK_INDEX (bb) = reorder_index++;
! REORDER_BLOCK_FLAGS (bb) |= REORDER_BLOCK_VISITED;
! }
! }
! /* Recurse on the successors. */
! for (e = bb->succ; e; e = e->succ_next)
{
! if (e->dest && e->dest == EXIT_BLOCK_PTR)
! continue;
! if (e->dest
! && e->dest != e->src
! && e->dest != visited_edge
! && ! (REORDER_BLOCK_FLAGS (e->dest)
! & REORDER_BLOCK_VISITED))
! {
! reorder_last_visited
! = chain_reorder_blocks (e, reorder_last_visited);
! make_reorder_chain (e->dest);
! }
}
}
! /* Fixup jumps and labels after reordering basic blocks. */
static void
fixup_reorder_chain ()
{
! int i, j;
! rtx insn;
! int orig_num_blocks = n_basic_blocks;
! /* Set the new last insn. */
! {
! int max_val = 0;
! int max_index = 0;
! for (j = 0; j < n_basic_blocks; j++)
! {
! int val = REORDER_BLOCK_INDEX (BASIC_BLOCK (j));
! if (val > max_val)
! {
! max_val = val;
! max_index = j;
! }
! }
! insn = REORDER_BLOCK_EFF_END (BASIC_BLOCK (max_index));
! NEXT_INSN (insn) = NULL_RTX;
! set_last_insn (insn);
! }
! /* Add jumps and labels to fixup blocks. */
! for (i = 0; i < orig_num_blocks; i++)
{
! int need_block = 0;
! basic_block bbi = BASIC_BLOCK (i);
! if (REORDER_BLOCK_ADD_JUMP (bbi))
! {
! rtx label_insn, jump_insn, barrier_insn;
! if (GET_CODE (REORDER_BLOCK_ADD_JUMP (bbi)->head) == CODE_LABEL)
! label_insn = REORDER_BLOCK_ADD_JUMP (bbi)->head;
! else
{
! rtx new_label = gen_label_rtx ();
! label_insn = emit_label_before (new_label,
! REORDER_BLOCK_ADD_JUMP (bbi)->head);
! REORDER_BLOCK_ADD_JUMP (bbi)->head = label_insn;
! }
! if (GET_CODE (bbi->end) != JUMP_INSN)
{
! jump_insn = emit_jump_insn_after (gen_jump (label_insn),
! bbi->end);
! bbi->end = jump_insn;
! need_block = 0;
}
else
{
! jump_insn = emit_jump_insn_after (gen_jump (label_insn),
! REORDER_BLOCK_EFF_END (bbi));
! need_block = 1;
}
! JUMP_LABEL (jump_insn) = label_insn;
! ++LABEL_NUSES (label_insn);
! barrier_insn = emit_barrier_after (jump_insn);
! /* Add block for jump. Typically this is when a then is not
! predicted and we are jumping to the moved then block. */
! if (need_block)
{
! basic_block nb;
! VARRAY_GROW (basic_block_info, ++n_basic_blocks);
! 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 (function_obstack);
! nb->global_live_at_end
! = OBSTACK_ALLOC_REG_SET (function_obstack);
! COPY_REG_SET (nb->global_live_at_start,
! bbi->global_live_at_start);
! COPY_REG_SET (nb->global_live_at_end,
! bbi->global_live_at_start);
! BASIC_BLOCK (nb->index)->local_set = 0;
! nb->aux = xcalloc (1, sizeof (struct reorder_block_def));
! REORDER_BLOCK_INDEX (nb) = REORDER_BLOCK_INDEX (bbi) + 1;
! /* Relink to new block. */
! nb->succ = bbi->succ;
! nb->succ->src = nb;
! make_edge (NULL, bbi, nb, 0);
! bbi->succ->succ_next
! = bbi->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++)
! {
! basic_block bbj = BASIC_BLOCK (j);
! if (REORDER_BLOCK_INDEX (bbj)
! >= REORDER_BLOCK_INDEX (bbi) + 1)
! REORDER_BLOCK_INDEX (bbj)++;
! }
! REORDER_BLOCK_SCOPE (nb) = REORDER_BLOCK_SCOPE (bbi);
! REORDER_BLOCK_EFF_HEAD (nb) = nb->head;
! REORDER_BLOCK_EFF_END (nb) = barrier_insn;
! }
! else
! REORDER_BLOCK_EFF_END (bbi) = barrier_insn;
! }
}
}
--- 259,715 ----
}
! /* Locate the effective beginning and end of the insn chain for each
! block, as defined by skip_insns_after_block above. */
! static void
! record_effective_endpoints ()
{
! rtx next_insn = get_insns ();
! int i;
!
! for (i = 0; i < n_basic_blocks; ++i)
{
! basic_block bb = BASIC_BLOCK (i);
! rtx end;
!
! RBI (bb)->eff_head = next_insn;
! end = skip_insns_after_block (bb);
! RBI (bb)->eff_end = end;
! next_insn = NEXT_INSN (end);
}
}
! /* Compute an ordering for a subgraph beginning with block BB. Record the
! ordering in RBI()->index and chained through RBI()->next. */
! static void
! make_reorder_chain ()
{
! basic_block last_block = NULL;
! basic_block prev = NULL;
! int nbb_m1 = n_basic_blocks - 1;
! /* If we've not got epilogue in RTL, we must fallthru to the exit.
! Force the last block to be at the end. */
! /* ??? Some ABIs (e.g. MIPS) require the return insn to be at the
! end of the function for stack unwinding purposes. */
! if (! HAVE_epilogue)
! {
! last_block = BASIC_BLOCK (nbb_m1);
! RBI (last_block)->visited = 1;
! nbb_m1 -= 1;
! }
! /* Loop until we've placed every block. */
! do
{
! int i;
! basic_block next = NULL;
! /* Find the next unplaced block. */
! /* ??? Get rid of this loop, and track which blocks are not yet
! placed more directly, so as to avoid the O(N^2) worst case.
! Perhaps keep a doubly-linked list of all to-be-placed blocks;
! 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;
! }
! /* A helper function for make_reorder_chain.
! We do not follow EH edges, or non-fallthru edges to noreturn blocks.
! These are assumed to be the error condition and we wish to cluster
! all of them at the very end of the function for the benefit of cache
! locality for the rest of the function.
!
! ??? We could do slightly better by noticing earlier that some subgraph
! has all paths leading to noreturn functions, but for there to be more
! than one block in such a subgraph is rare. */
!
! static basic_block
! make_reorder_chain_1 (bb, prev)
! basic_block bb;
! basic_block prev;
! {
! edge e;
! basic_block next;
! rtx note;
!
! /* 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;
! if (bb->succ == NULL)
! return prev;
! /* Find the most probable block. */
!
! next = NULL;
! if (any_condjump_p (bb->end)
! && (note = find_reg_note (bb->end, REG_BR_PROB, 0)) != NULL)
{
! int taken, probability;
! edge e_taken, e_fall;
! probability = INTVAL (XEXP (note, 0));
! taken = probability > REG_BR_PROB_BASE / 2;
!
! /* Find the normal taken edge and the normal fallthru edge.
! Note that there may in fact be other edges due to
! asynchronous_exceptions. */
!
! e_taken = e_fall = NULL;
! for (e = bb->succ; e ; e = e->succ_next)
! if (e->flags & EDGE_FALLTHRU)
! e_fall = e;
! else if (! (e->flags & EDGE_EH))
! e_taken = e;
!
! next = (taken ? e_taken : e_fall)->dest;
}
! /* In the absense of prediction, disturb things as little as possible
! by selecting the old "next" block from the list of successors. If
! there had been a fallthru edge, that will be the one. */
! if (! next)
! {
! for (e = bb->succ; e ; e = e->succ_next)
! if (e->dest->index == bb->index + 1)
! {
! if ((e->flags & EDGE_FALLTHRU)
! || (e->dest->succ
! && ! (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))))
! next = e->dest;
! break;
! }
! }
! /* Make sure we didn't select a silly next block. */
! if (!next || next == EXIT_BLOCK_PTR || RBI (next)->visited)
! next = NULL;
! /* Recurse on the successors. Unroll the last call, as the normal
! case is exactly one or two edges, and we can tail recurse. */
! for (e = bb->succ; e; e = e->succ_next)
! if (e->dest != EXIT_BLOCK_PTR
! && ! RBI (e->dest)->visited
! && e->dest->succ
! && ! (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH)))
! {
! if (next)
! {
! prev = make_reorder_chain_1 (next, prev);
! next = RBI (e->dest)->visited ? NULL : e->dest;
! }
! else
! next = e->dest;
! }
! if (next)
! {
! bb = next;
! goto restart;
! }
! return prev;
}
! /* Locate or create a label for a given basic block. */
! static rtx
! label_for_bb (bb)
basic_block bb;
{
! rtx label = bb->head;
! 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;
! }
! /* Emit a jump to BB after insn AFTER. */
! static rtx
! emit_jump_to_block_after (bb, after)
! basic_block bb;
! rtx after;
! {
! rtx jump;
!
! if (bb != EXIT_BLOCK_PTR)
{
! rtx label = label_for_bb (bb);
! jump = emit_jump_insn_after (gen_jump (label), after);
! JUMP_LABEL (jump) = label;
! LABEL_NUSES (label) += 1;
! if (rtl_dump_file)
! fprintf (rtl_dump_file, "Emitting jump to block %d (%d)\n",
! bb->index, RBI (bb)->index);
! }
! else
{
! if (! HAVE_return)
! abort ();
! jump = emit_jump_insn_after (gen_return (), after);
! if (rtl_dump_file)
! fprintf (rtl_dump_file, "Emitting return\n");
}
+
+ return jump;
}
! /* Given a reorder chain, rearrange the code to match. */
static void
fixup_reorder_chain ()
{
! basic_block bb, last_bb;
! /* 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;
! while (bb)
{
! rtx last_e = RBI (last_bb)->eff_end;
! rtx curr_h = RBI (bb)->eff_head;
! NEXT_INSN (last_e) = curr_h;
! PREV_INSN (curr_h) = last_e;
!
! last_bb = bb;
! bb = RBI (bb)->next;
! }
! NEXT_INSN (RBI (last_bb)->eff_end) = NULL_RTX;
! set_last_insn (RBI (last_bb)->eff_end);
!
! /* Now add jumps and labels as needed to match the blocks new
! outgoing edges. */
!
! for (bb = BASIC_BLOCK (0); bb ; bb = RBI (bb)->next)
! {
! edge e_fall, e_taken, e;
! rtx jump_insn, barrier_insn;
! basic_block nb;
!
! if (bb->succ == NULL)
! continue;
!
! /* Find the old fallthru edge, and another non-EH edge for
! a taken jump. */
! e_taken = e_fall = NULL;
! for (e = bb->succ; e ; e = e->succ_next)
! if (e->flags & EDGE_FALLTHRU)
! e_fall = e;
! else if (! (e->flags & EDGE_EH))
! e_taken = e;
!
! if (GET_CODE (bb->end) == JUMP_INSN)
! {
! if (any_uncondjump_p (bb->end))
{
! /* 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))
{
! /* 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;
!
! /* There is one special case: if *neither* block is next,
! 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, REG_BR_PROB, 0);
! if (note
! && INTVAL (XEXP (note, 0)) < REG_BR_PROB_BASE / 2
! && invert_jump (bb->end, label_for_bb (e_fall->dest), 0))
! {
! e_fall->flags &= ~EDGE_FALLTHRU;
! e_taken->flags |= EDGE_FALLTHRU;
! e = e_fall, e_fall = e_taken, e_taken = e;
! }
! }
!
! /* Otherwise we can try to invert the jump. This will
! basically never fail, however, keep up the pretense. */
! else if (invert_jump (bb->end, label_for_bb (e_fall->dest), 0))
! {
! e_fall->flags &= ~EDGE_FALLTHRU;
! e_taken->flags |= EDGE_FALLTHRU;
! continue;
! }
}
+ else if (returnjump_p (bb->end))
+ continue;
else
{
! /* Otherwise we have some switch or computed jump. In the
! 99% case, there should not have been a fallthru edge. */
! if (! e_fall)
! continue;
! #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;
! #endif
! abort ();
}
+ }
+ else
+ {
+ /* No fallthru implies a noreturn function with EH edges, or
+ something similarly bizzare. In any case, we don't need to
+ do anything. */
+ if (! e_fall)
+ 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
! edge, then we can stuff the new jump insn in directly. */
! if (bb->succ->succ_next == NULL)
{
! e_fall->flags &= ~EDGE_FALLTHRU;
! jump_insn = emit_jump_to_block_after (e_fall->dest, bb->end);
! bb->end = jump_insn;
! barrier_insn = emit_barrier_after (jump_insn);
! RBI (bb)->eff_end = barrier_insn;
! continue;
! }
! }
! /* We got here if we need to add a new jump insn in a new block
! across the edge e_fall. */
! jump_insn = emit_jump_to_block_after (e_fall->dest, bb->end);
! barrier_insn = emit_barrier_after (jump_insn);
! VARRAY_GROW (basic_block_info, ++n_basic_blocks);
! 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 (function_obstack);
! nb->global_live_at_end = OBSTACK_ALLOC_REG_SET (function_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);
!
! nb->aux = xmalloc (sizeof (struct reorder_block_def));
! 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;
!
! /* Disconnect the existing edge from the target block. */
! {
! edge *pe = &e_fall->dest->pred;
! for (e = *pe; e != e_fall; pe = &e->pred_next, e = *pe)
! continue;
! *pe = e->pred_next;
! }
!
! /* Link to new block. */
! make_edge (NULL, nb, e_fall->dest, 0);
! nb->pred = e_fall;
! e_fall->dest = nb;
!
! /* Don't process this new block. */
! bb = nb;
!
! /* Fix subsequent reorder block indicies 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;
+ }
}
*************** fixup_reorder_chain ()
*** 655,662 ****
reverse direction.
2. Count insns in chain, going both directions, and check if equal.
3. Check that get_last_insn () returns the actual end of chain. */
! #ifdef ENABLE_CHECKING
! static void
verify_insn_chain ()
{
rtx x,
--- 718,725 ----
reverse direction.
2. Count insns in chain, going both directions, and check if equal.
3. Check that get_last_insn () returns the actual end of chain. */
!
! void
verify_insn_chain ()
{
rtx x,
*************** verify_insn_chain ()
*** 712,718 ****
abort ();
}
}
- #endif
static rtx
get_next_bb_note (x)
--- 775,780 ----
*************** relate_bbs_with_scopes (s)
*** 853,859 ****
}
}
-
/* If the scope spans one or more basic blocks, we record them. We
only record the bbs that are immediately contained within this
scope. Note that if a scope is contained within a bb, we can tell
--- 915,920 ----
*************** relate_bbs_with_scopes (s)
*** 864,880 ****
s->num_bbs = 0;
for (i = bbi1; i <= bbi2; i++)
! if (! REORDER_BLOCK_SCOPE (BASIC_BLOCK (i)))
s->num_bbs++;
! s->bbs = xcalloc (s->num_bbs, sizeof (struct basic_block_def));
for (i = bbi1; i <= bbi2; i++)
{
basic_block curr_bb = BASIC_BLOCK (i);
! if (! REORDER_BLOCK_SCOPE (curr_bb))
{
s->bbs[j++] = curr_bb;
! REORDER_BLOCK_SCOPE (curr_bb) = s;
}
}
}
--- 925,941 ----
s->num_bbs = 0;
for (i = bbi1; i <= bbi2; i++)
! if (! RBI (BASIC_BLOCK (i))->scope)
s->num_bbs++;
! s->bbs = xmalloc (s->num_bbs * sizeof (basic_block));
for (i = bbi1; i <= bbi2; i++)
{
basic_block curr_bb = BASIC_BLOCK (i);
! if (! RBI (curr_bb)->scope)
{
s->bbs[j++] = curr_bb;
! RBI (curr_bb)->scope = s;
}
}
}
*************** make_new_scope (level, note)
*** 894,908 ****
scope new_scope = xcalloc (1, sizeof (struct scope_def));
new_scope->level = level;
new_scope->note_beg = note;
- new_scope->note_end = NULL;
- new_scope->bb_beg = NULL;
- new_scope->bb_end = NULL;
- new_scope->inner = NULL;
- new_scope->inner_last = NULL;
- new_scope->outer = NULL;
- new_scope->next = NULL;
- new_scope->num_bbs = 0;
- new_scope->bbs = NULL;
return new_scope;
}
--- 955,960 ----
*************** build_scope_forest (forest)
*** 961,971 ****
level++;
curr_scope = make_new_scope (level, x);
root = curr_scope;
! if (ntrees == 0)
! forest->trees = xcalloc (1, sizeof (scope));
! else
! forest->trees = xrealloc (forest->trees,
! sizeof (scope) * (ntrees + 1));
forest->trees[forest->num_trees++] = root;
}
curr_scope->bb_beg = curr_bb;
--- 1013,1020 ----
level++;
curr_scope = make_new_scope (level, x);
root = curr_scope;
! forest->trees = xrealloc (forest->trees,
! sizeof (scope) * (ntrees + 1));
forest->trees[forest->num_trees++] = root;
}
curr_scope->bb_beg = curr_bb;
*************** remove_scope_notes ()
*** 1036,1041 ****
--- 1085,1091 ----
/* Insert scope note pairs for a contained scope tree S after insn IP. */
+
static void
insert_intra_1 (s, ip)
scope s;
*************** static void
*** 1067,1073 ****
insert_intra_bb_scope_notes (bb)
basic_block bb;
{
! scope s = REORDER_BLOCK_SCOPE (bb);
scope p;
rtx ip;
--- 1117,1123 ----
insert_intra_bb_scope_notes (bb)
basic_block bb;
{
! scope s = RBI (bb)->scope;
scope p;
rtx ip;
*************** insert_inter_bb_scope_notes (bb1, bb2)
*** 1104,1111 ****
In that case, we either open or close a scope but not both. */
if (bb1 && bb2)
{
! scope s1 = REORDER_BLOCK_SCOPE (bb1);
! scope s2 = REORDER_BLOCK_SCOPE (bb2);
if (! s1 && ! s2)
return;
if (! s1)
--- 1154,1161 ----
In that case, we either open or close a scope but not both. */
if (bb1 && bb2)
{
! scope s1 = RBI (bb1)->scope;
! scope s2 = RBI (bb2)->scope;
if (! s1 && ! s2)
return;
if (! s1)
*************** insert_inter_bb_scope_notes (bb1, bb2)
*** 1117,1124 ****
/* Find common ancestor scope. */
if (bb1 && bb2)
{
! scope s1 = REORDER_BLOCK_SCOPE (bb1);
! scope s2 = REORDER_BLOCK_SCOPE (bb2);
while (s1 != s2)
{
if (! (s1 && s2))
--- 1167,1174 ----
/* Find common ancestor scope. */
if (bb1 && bb2)
{
! scope s1 = RBI (bb1)->scope;
! scope s2 = RBI (bb2)->scope;
while (s1 != s2)
{
if (! (s1 && s2))
*************** insert_inter_bb_scope_notes (bb1, bb2)
*** 1141,1148 ****
/* Close scopes. */
if (bb1)
{
! scope s = REORDER_BLOCK_SCOPE (bb1);
! ip = REORDER_BLOCK_EFF_END (bb1);
while (s != com)
{
if (NOTE_BLOCK (s->note_beg))
--- 1191,1198 ----
/* Close scopes. */
if (bb1)
{
! scope s = RBI (bb1)->scope;
! ip = RBI (bb1)->eff_end;
while (s != com)
{
if (NOTE_BLOCK (s->note_beg))
*************** insert_inter_bb_scope_notes (bb1, bb2)
*** 1157,1163 ****
/* Open scopes. */
if (bb2)
{
! scope s = REORDER_BLOCK_SCOPE (bb2);
ip = bb2->head;
while (s != com)
{
--- 1207,1213 ----
/* Open scopes. */
if (bb2)
{
! scope s = RBI (bb2)->scope;
ip = bb2->head;
while (s != com)
{
*************** rebuild_scope_notes (forest)
*** 1192,1198 ****
{
basic_block bb1 = BASIC_BLOCK (i);
basic_block bb2 = BASIC_BLOCK (i + 1);
! if (REORDER_BLOCK_SCOPE (bb1) != REORDER_BLOCK_SCOPE (bb2))
insert_inter_bb_scope_notes (bb1, bb2);
insert_intra_bb_scope_notes (bb1);
}
--- 1242,1248 ----
{
basic_block bb1 = BASIC_BLOCK (i);
basic_block bb2 = BASIC_BLOCK (i + 1);
! if (RBI (bb1)->scope != RBI (bb2)->scope)
insert_inter_bb_scope_notes (bb1, bb2);
insert_intra_bb_scope_notes (bb1);
}
*************** dump_scope_forest_1 (s, indent)
*** 1264,1271 ****
int i;
if (s->bb_beg != NULL && s->bb_beg == s->bb_end
! && REORDER_BLOCK_SCOPE (s->bb_beg)
! && REORDER_BLOCK_SCOPE (s->bb_beg)->level + 1 == s->level)
{
fprintf (stderr, "%*s", indent, "");
fprintf (stderr, "BB%d:\n", s->bb_beg->index);
--- 1314,1321 ----
int i;
if (s->bb_beg != NULL && s->bb_beg == s->bb_end
! && RBI (s->bb_beg)->scope
! && RBI (s->bb_beg)->scope->level + 1 == s->level)
{
fprintf (stderr, "%*s", indent, "");
fprintf (stderr, "BB%d:\n", s->bb_beg->index);
*************** dump_scope_forest_1 (s, indent)
*** 1288,1414 ****
}
! /* Reorder basic blocks. */
void
reorder_basic_blocks ()
{
- int i, j;
- struct loops loops_info;
- int num_loops;
scope_forest_info forest;
!
! if (profile_arc_flag)
! return;
if (n_basic_blocks <= 1)
return;
! /* 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)
! continue;
!
! if (e && (e->flags & EDGE_EH))
! return;
}
- reorder_index = 0;
-
- /* Find natural loops using the CFG. */
- num_loops = flow_loops_find (&loops_info);
-
- /* Dump loop information. */
- flow_loops_dump (&loops_info, rtl_dump_file, 0);
-
- reorder_last_visited = BASIC_BLOCK (0);
-
for (i = 0; i < n_basic_blocks; i++)
! {
! basic_block bbi = BASIC_BLOCK (i);
! bbi->aux = xcalloc (1, sizeof (struct reorder_block_def));
! *((struct reorder_block_def *)bbi->aux) = rbd_init;
! }
build_scope_forest (&forest);
remove_scope_notes ();
! for (i = 0; i < n_basic_blocks; i++)
! {
! basic_block bbi = BASIC_BLOCK (i);
! REORDER_BLOCK_EFF_END (bbi) = skip_insns_after_block (bbi);
! if (i == 0)
! REORDER_BLOCK_EFF_HEAD (bbi) = get_insns ();
! else
! {
! rtx prev_eff_end = REORDER_BLOCK_EFF_END (BASIC_BLOCK (i - 1));
! REORDER_BLOCK_EFF_HEAD (bbi) = NEXT_INSN (prev_eff_end);
! }
! }
!
! /* If we've not got epilogue in RTL, we must fallthru to the exit.
! Force the last block to be at the end. */
! /* ??? Some ABIs (e.g. MIPS) require the return insn to be at the
! end of the function for stack unwinding purposes. */
!
! #ifndef HAVE_epilogue
! #define HAVE_epilogue 0
! #endif
!
! if (! HAVE_epilogue)
! {
! basic_block last = BASIC_BLOCK (n_basic_blocks - 1);
! REORDER_BLOCK_INDEX (last) = n_basic_blocks - 1;
! REORDER_BLOCK_FLAGS (last) |= REORDER_BLOCK_VISITED;
! }
!
! make_reorder_chain (BASIC_BLOCK (0));
!
fixup_reorder_chain ();
#ifdef ENABLE_CHECKING
verify_insn_chain ();
#endif
- /* Put basic_block_info in new order. */
- for (i = 0; i < n_basic_blocks - 1; i++)
- {
- for (j = i; i != REORDER_BLOCK_INDEX (BASIC_BLOCK (j)); j++)
- continue;
-
- if (REORDER_BLOCK_INDEX (BASIC_BLOCK (j)) == i
- && i != j)
- {
- basic_block tempbb;
- int temprbi;
- int rbi = REORDER_BLOCK_INDEX (BASIC_BLOCK (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;
- }
- }
-
rebuild_scope_notes (&forest);
free_scope_forest (&forest);
reorder_blocks ();
- #ifdef ENABLE_CHECKING
- verify_flow_info ();
- #endif
-
for (i = 0; i < n_basic_blocks; i++)
free (BASIC_BLOCK (i)->aux);
-
- /* Free loop information. */
- flow_loops_free (&loops_info);
}
-
--- 1338,1385 ----
}
! /* Reorder basic blocks. The main entry point to this file. */
void
reorder_basic_blocks ()
{
scope_forest_info forest;
! int i;
if (n_basic_blocks <= 1)
return;
! /* We do not currently handle correct re-placement of EH notes. */
for (i = 0; i < n_basic_blocks; i++)
{
edge e;
! for (e = BASIC_BLOCK (i)->succ; e ; e = e->succ_next)
! if (e->flags & EDGE_EH)
! return;
}
for (i = 0; i < n_basic_blocks; i++)
! BASIC_BLOCK (i)->aux = xcalloc (1, sizeof (struct reorder_block_def));
build_scope_forest (&forest);
remove_scope_notes ();
! record_effective_endpoints ();
! make_reorder_chain ();
fixup_reorder_chain ();
#ifdef ENABLE_CHECKING
verify_insn_chain ();
#endif
rebuild_scope_notes (&forest);
free_scope_forest (&forest);
reorder_blocks ();
for (i = 0; i < n_basic_blocks; i++)
free (BASIC_BLOCK (i)->aux);
+ #ifdef ENABLE_CHECKING
+ verify_flow_info ();
+ #endif
}
Index: flow.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/flow.c,v
retrieving revision 1.290
diff -c -p -d -r1.290 flow.c
*** flow.c 2000/05/19 22:27:27 1.290
--- flow.c 2000/05/22 07:07:34
*************** tidy_fallthru_edge (e, b, c)
*** 2454,2460 ****
note. */
q = b->end;
if (GET_CODE (q) == JUMP_INSN
! && (simplejump_p (q)
|| (b->succ == e && e->succ_next == NULL)))
{
#ifdef HAVE_cc0
--- 2454,2460 ----
note. */
q = b->end;
if (GET_CODE (q) == JUMP_INSN
! && (any_uncondjump_p (q)
|| (b->succ == e && e->succ_next == NULL)))
{
#ifdef HAVE_cc0
Index: jump.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/jump.c,v
retrieving revision 1.127
diff -c -p -d -r1.127 jump.c
*** jump.c 2000/05/19 19:53:16 1.127
--- jump.c 2000/05/22 07:07:35
*************** can_reverse_comparison_p (comparison, in
*** 1775,1782 ****
#endif
)
{
! rtx prev = prev_nonnote_insn (insn);
! rtx set;
/* First see if the condition code mode alone if enough to say we can
reverse the condition. If not, then search backwards for a set of
--- 1775,1781 ----
#endif
)
{
! rtx prev, set;
/* First see if the condition code mode alone if enough to say we can
reverse the condition. If not, then search backwards for a set of
*************** can_reverse_comparison_p (comparison, in
*** 1788,1793 ****
--- 1787,1795 ----
&& REVERSIBLE_CC_MODE (GET_MODE (arg0)))
return 1;
#endif
+
+ if (! insn)
+ return 0;
for (prev = prev_nonnote_insn (insn);
prev != 0 && GET_CODE (prev) != CODE_LABEL;