#include "config.h"
#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
#include "tree.h"
#include "rtl.h"
#include "hard-reg-set.h"
#include "function.h"
#include "obstack.h"
#include "cfglayout.h"
+#include "cfgloop.h"
+#include "target.h"
/* The contents of the current function definition are allocated
in this obstack, and all are freed at the end of the function. */
static void change_scope PARAMS ((rtx, tree, tree));
void verify_insn_chain PARAMS ((void));
-static void cleanup_unconditional_jumps PARAMS ((void));
+static void cleanup_unconditional_jumps PARAMS ((struct loops *));
static void fixup_fallthru_exit_predecessor PARAMS ((void));
static rtx unlink_insn_chain PARAMS ((rtx, rtx));
static rtx duplicate_insn_chain PARAMS ((rtx, rtx));
-
-/* Map insn uid to lexical block. */
-static varray_type insn_scopes;
+static void break_superblocks PARAMS ((void));
\f
static rtx
unlink_insn_chain (first, last)
rtx insn, last_insn, next_head, prev;
next_head = NULL_RTX;
- if (bb->index + 1 != n_basic_blocks)
- next_head = BASIC_BLOCK (bb->index + 1)->head;
+ if (bb->next_bb != EXIT_BLOCK_PTR)
+ next_head = bb->next_bb->head;
for (last_insn = insn = bb->end; (insn = NEXT_INSN (insn)) != 0; )
{
last_insn = insn;
continue;
}
- break;
+ break;
default:
break;
}
/* It is possible to hit contradictory sequence. For instance:
-
+
jump_insn
NOTE_INSN_LOOP_BEG
barrier
if (GET_CODE (insn) == 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:
+ case NOTE_INSN_LOOP_END:
+ case NOTE_INSN_BLOCK_END:
+ case NOTE_INSN_DELETED:
+ case NOTE_INSN_DELETED_LABEL:
continue;
- default:
+ default:
reorder_insns (insn, insn, last_insn);
- }
+ }
}
return last_insn;
record_effective_endpoints ()
{
rtx next_insn = get_insns ();
- int i;
-
- for (i = 0; i < n_basic_blocks; i++)
+ basic_block bb;
+
+ FOR_EACH_BB (bb)
{
- basic_block bb = BASIC_BLOCK (i);
rtx end;
if (PREV_INSN (bb->head) && next_insn != bb->head)
PREV_INSN (bb->head));
end = skip_insns_after_block (bb);
if (NEXT_INSN (bb->end) && bb->end != end)
- RBI (bb)->footer = unlink_insn_chain (NEXT_INSN (bb->end), end);
+ RBI (bb)->footer = unlink_insn_chain (NEXT_INSN (bb->end), end);
next_insn = NEXT_INSN (bb->end);
}
tree block = NULL;
rtx insn, next;
- VARRAY_TREE_INIT (insn_scopes, get_max_uid (), "insn scopes");
-
for (insn = get_insns (); insn; insn = next)
{
next = NEXT_INSN (insn);
if (active_insn_p (insn)
&& GET_CODE (PATTERN (insn)) != ADDR_VEC
&& GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC)
- VARRAY_TREE (insn_scopes, INSN_UID (insn)) = block;
+ INSN_SCOPE (insn) = block;
else if (GET_CODE (insn) == NOTE)
{
switch (NOTE_LINE_NUMBER (insn))
break;
case NOTE_INSN_BLOCK_END:
block = BLOCK_SUPERCONTEXT (block);
+ if (block && TREE_CODE (block) == FUNCTION_DECL)
+ block = 0;
delete_insn (insn);
break;
default:
}
}
}
+
+ /* Tag the blocks with a depth number so that change_scope can find
+ the common parent easily. */
+ set_block_levels (DECL_INITIAL (cfun->decl), 0);
}
/* For each lexical block, set BLOCK_NUMBER to the depth at which it is
}
}
\f
+/* Return sope resulting from combination of S1 and S2. */
+tree
+choose_inner_scope (s1, s2)
+ tree s1, s2;
+{
+ if (!s1)
+ return s2;
+ if (!s2)
+ return s1;
+ if (BLOCK_NUMBER (s1) > BLOCK_NUMBER (s2))
+ return s1;
+ return s2;
+}
+\f
/* Emit lexical block notes needed to change scope from S1 to S2. */
static void
tree cur_block = DECL_INITIAL (cfun->decl);
rtx insn, note;
- /* Tag the blocks with a depth number so that change_scope can find
- the common parent easily. */
- set_block_levels (cur_block, 0);
-
- for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
+ insn = get_insns ();
+ if (!active_insn_p (insn))
+ insn = next_active_insn (insn);
+ for (; insn; insn = next_active_insn (insn))
{
tree this_block;
- if ((size_t) INSN_UID (insn) >= insn_scopes->num_elements)
- continue;
- this_block = VARRAY_TREE (insn_scopes, INSN_UID (insn));
+ this_block = INSN_SCOPE (insn);
+ /* For sequences compute scope resulting from merging all scopes
+ of instructions nested inside. */
+ if (GET_CODE (PATTERN (insn)) == SEQUENCE)
+ {
+ int i;
+ rtx body = PATTERN (insn);
+
+ this_block = NULL;
+ for (i = 0; i < XVECLEN (body, 0); i++)
+ this_block = choose_inner_scope (this_block,
+ INSN_SCOPE (XVECEXP (body, 0, i)));
+ }
if (! this_block)
continue;
}
}
- VARRAY_FREE (insn_scopes);
-
/* change_scope emits before the insn, not after. */
note = emit_note (NULL, NOTE_INSN_DELETED);
change_scope (note, cur_block, DECL_INITIAL (cfun->decl));
static void
fixup_reorder_chain ()
{
- basic_block bb;
+ basic_block bb, prev_bb;
int index;
rtx insn = NULL;
/* First do the bulk reordering -- rechain the blocks without regard to
the needed changes to jumps and labels. */
- for (bb = BASIC_BLOCK (0), index = 0;
+ for (bb = ENTRY_BLOCK_PTR->next_bb, index = 0;
bb != 0;
bb = RBI (bb)->next, index++)
{
/* Now add jumps and labels as needed to match the blocks new
outgoing edges. */
- for (bb = BASIC_BLOCK (0); bb ; bb = RBI (bb)->next)
+ for (bb = ENTRY_BLOCK_PTR->next_bb; bb ; bb = RBI (bb)->next)
{
edge e_fall, e_taken, e;
rtx bb_end_insn;
&& e_fall->dest == EXIT_BLOCK_PTR))
continue;
+ /* The degenerated case of conditional jump jumping to the next
+ instruction can happen on target having jumps with side
+ effects.
+
+ Create temporarily the duplicated edge representing branch.
+ It will get unidentified by force_nonfallthru_and_redirect
+ that would otherwise get confused by fallthru edge not pointing
+ to the next basic block. */
+ if (!e_taken)
+ {
+ rtx note;
+ edge e_fake;
+
+ e_fake = unchecked_make_edge (bb, e_fall->dest, 0);
+
+ if (!redirect_jump (bb->end, block_label (bb), 0))
+ abort ();
+ note = find_reg_note (bb->end, REG_BR_PROB, NULL_RTX);
+ if (note)
+ {
+ int prob = INTVAL (XEXP (note, 0));
+
+ e_fake->probability = prob;
+ e_fake->count = e_fall->count * prob / REG_BR_PROB_BASE;
+ e_fall->probability -= e_fall->probability;
+ e_fall->count -= e_fake->count;
+ if (e_fall->probability < 0)
+ e_fall->probability = 0;
+ if (e_fall->count < 0)
+ e_fall->count = 0;
+ }
+ }
/* 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)->next != e_taken->dest)
+ else if (RBI (bb)->next != e_taken->dest)
{
rtx note = find_reg_note (bb_end_insn, REG_BR_PROB, 0);
}
}
- /* Otherwise we can try to invert the jump. This will
+ /* Otherwise we can try to invert the jump. This will
basically never fail, however, keep up the pretense. */
else if (invert_jump (bb_end_insn,
label_for_bb (e_fall->dest), 0))
if (rtl_dump_file)
{
fprintf (rtl_dump_file, "Reordered sequence:\n");
- for (bb = BASIC_BLOCK (0), index = 0; bb; bb = RBI (bb)->next, index ++)
+ for (bb = ENTRY_BLOCK_PTR->next_bb, index = 0; bb; bb = RBI (bb)->next, index ++)
{
fprintf (rtl_dump_file, " %i ", index);
if (RBI (bb)->original)
}
}
- for (bb = BASIC_BLOCK (0), index = 0; bb; bb = RBI (bb)->next, index ++)
+ prev_bb = ENTRY_BLOCK_PTR;
+ bb = ENTRY_BLOCK_PTR->next_bb;
+ index = 0;
+
+ for (; bb; prev_bb = bb, bb = RBI (bb)->next, index ++)
{
bb->index = index;
BASIC_BLOCK (index) = bb;
+
+ bb->prev_bb = prev_bb;
+ prev_bb->next_bb = bb;
}
+ prev_bb->next_bb = EXIT_BLOCK_PTR;
+ EXIT_BLOCK_PTR->prev_bb = prev_bb;
}
\f
/* Perform sanity checks on the insn chain.
}
\f
/* Remove any unconditional jumps and forwarder block creating fallthru
- edges instead. During BB reordering fallthru edges are not required
+ edges instead. During BB reordering, fallthru edges are not required
to target next basic block in the linear CFG layout, so the unconditional
jumps are not needed. If LOOPS is not null, also update loop structure &
dominators. */
static void
-cleanup_unconditional_jumps ()
+cleanup_unconditional_jumps (loops)
+ struct loops *loops;
{
- int i;
- for (i = 0; i < n_basic_blocks; i++)
- {
- basic_block bb = BASIC_BLOCK (i);
+ basic_block bb;
+ FOR_EACH_BB (bb)
+ {
if (!bb->succ)
continue;
if (bb->succ->flags & EDGE_FALLTHRU)
if (!bb->succ->succ_next)
{
rtx insn;
- if (GET_CODE (bb->head) != CODE_LABEL && forwarder_block_p (bb) && i)
+ if (GET_CODE (bb->head) != CODE_LABEL && forwarder_block_p (bb)
+ && bb->prev_bb != ENTRY_BLOCK_PTR)
{
- basic_block prev = BASIC_BLOCK (--i);
+ basic_block prev = bb->prev_bb;
if (rtl_dump_file)
fprintf (rtl_dump_file, "Removing forwarder BB %i\n",
bb->index);
- redirect_edge_succ (bb->pred, bb->succ->dest);
+ if (loops)
+ {
+ /* bb cannot be loop header, as it only has one entry
+ edge. It could be a loop latch. */
+ if (bb->loop_father->header == bb)
+ abort ();
+
+ if (bb->loop_father->latch == bb)
+ bb->loop_father->latch = bb->pred->src;
+
+ if (get_immediate_dominator
+ (loops->cfg.dom, bb->succ->dest) == bb)
+ set_immediate_dominator
+ (loops->cfg.dom, bb->succ->dest, bb->pred->src);
+
+ remove_bb_from_loops (bb);
+ delete_from_dominance_info (loops->cfg.dom, bb);
+ }
+
+ redirect_edge_succ_nodup (bb->pred, bb->succ->dest);
flow_delete_block (bb);
bb = prev;
}
else
continue;
- /* Cleanup barriers and delete ADDR_VECs in a way as they are belonging
- to removed tablejump anyway. */
insn = NEXT_INSN (bb->end);
while (insn
&& (GET_CODE (insn) != NOTE
if (GET_CODE (insn) == BARRIER)
delete_barrier (insn);
- else if (GET_CODE (insn) == JUMP_INSN)
- delete_insn_chain (PREV_INSN (insn), insn);
- else if (GET_CODE (insn) == CODE_LABEL)
- ;
- else if (GET_CODE (insn) != NOTE)
- abort ();
insn = next;
}
if (bb && RBI (bb)->next)
{
- basic_block c = BASIC_BLOCK (0);
+ basic_block c = ENTRY_BLOCK_PTR->next_bb;
while (RBI (c)->next != bb)
c = RBI (c)->next;
cfg_layout_can_duplicate_bb_p (bb)
basic_block bb;
{
- rtx next;
edge s;
if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR)
return false;
- /* Duplicating fallthru block to exit would require adding an jump
+ /* Duplicating fallthru block to exit would require adding a jump
and splitting the real last BB. */
for (s = bb->succ; s; s = s->succ_next)
if (s->dest == EXIT_BLOCK_PTR && s->flags & EDGE_FALLTHRU)
return false;
/* Do not attempt to duplicate tablejumps, as we need to unshare
- the dispatch table. This is dificult to do, as the instructions
+ the dispatch table. This is difficult to do, as the instructions
computing jump destination may be hoisted outside the basic block. */
- if (GET_CODE (bb->end) == JUMP_INSN && JUMP_LABEL (bb->end)
- && (next = next_nonnote_insn (JUMP_LABEL (bb->end)))
- && GET_CODE (next) == JUMP_INSN
- && (GET_CODE (PATTERN (next)) == ADDR_VEC
- || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
+ if (tablejump_p (bb->end, NULL, NULL))
return false;
+
+ /* Do not duplicate blocks containing insns that can't be copied. */
+ if (targetm.cannot_copy_insn_p)
+ {
+ rtx insn = bb->head;
+ while (1)
+ {
+ if (INSN_P (insn) && (*targetm.cannot_copy_insn_p) (insn))
+ return false;
+ if (insn == bb->end)
+ break;
+ insn = NEXT_INSN (insn);
+ }
+ }
+
return true;
}
be reordered later. */
for (insn = from; insn != NEXT_INSN (to); insn = NEXT_INSN (insn))
{
- rtx new;
switch (GET_CODE (insn))
{
case INSN:
if (GET_CODE (PATTERN (insn)) == ADDR_VEC
|| GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
break;
- new = emit_copy_of_insn_after (insn, get_last_insn ());
- /* Record the INSN_SCOPE. */
- VARRAY_GROW (insn_scopes, INSN_UID (new) + 1);
- VARRAY_TREE (insn_scopes, INSN_UID (new))
- = VARRAY_TREE (insn_scopes, INSN_UID (insn));
+ emit_copy_of_insn_after (insn, get_last_insn ());
break;
case CODE_LABEL:
reordering is in the progress. */
case NOTE_INSN_EH_REGION_BEG:
case NOTE_INSN_EH_REGION_END:
- case NOTE_INSN_RANGE_BEG:
- case NOTE_INSN_RANGE_END:
/* Should never exist at BB duplication time. */
abort ();
break;
}
/* Redirect Edge to DEST. */
-void
+bool
cfg_layout_redirect_edge (e, dest)
edge e;
basic_block dest;
{
- int old_index = dest->index;
basic_block src = e->src;
+ basic_block old_next_bb = src->next_bb;
+ bool ret;
/* Redirect_edge_and_branch may decide to turn branch into fallthru edge
in the case the basic block appears to be in sequence. Avoid this
transformation. */
- dest->index = n_basic_blocks + 1;
+ src->next_bb = NULL;
if (e->flags & EDGE_FALLTHRU)
{
+ /* Redirect any branch edges unified with the fallthru one. */
+ if (GET_CODE (src->end) == JUMP_INSN
+ && JUMP_LABEL (src->end) == e->dest->head)
+ {
+ if (!redirect_jump (src->end, block_label (dest), 0))
+ abort ();
+ }
/* In case we are redirecting fallthru edge to the branch edge
of conditional jump, remove it. */
if (src->succ->succ_next
delete_insn (src->end);
}
redirect_edge_succ_nodup (e, dest);
+
+ ret = true;
}
else
- redirect_edge_and_branch (e, dest);
+ ret = redirect_edge_and_branch (e, dest);
/* We don't want simplejumps in the insn stream during cfglayout. */
if (simplejump_p (src->end))
delete_barrier (NEXT_INSN (src->end));
src->succ->flags |= EDGE_FALLTHRU;
}
- dest->index = old_index;
+ src->next_bb = old_next_bb;
+
+ return ret;
+}
+
+/* Same as split_block but update cfg_layout structures. */
+edge
+cfg_layout_split_block (bb, insn)
+ basic_block bb;
+ rtx insn;
+{
+ edge fallthru = split_block (bb, insn);
+
+ alloc_aux_for_block (fallthru->dest, sizeof (struct reorder_block_def));
+ RBI (fallthru->dest)->footer = RBI (fallthru->src)->footer;
+ RBI (fallthru->src)->footer = NULL;
+ return fallthru;
}
-/* Create an duplicate of the basic block BB and redirect edge E into it. */
+/* Create a duplicate of the basic block BB and redirect edge E into it. */
basic_block
cfg_layout_duplicate_bb (bb, e)
#endif
insn = duplicate_insn_chain (bb->head, bb->end);
- new_bb = create_basic_block (n_basic_blocks, insn,
- insn ? get_last_insn () : NULL);
+ new_bb = create_basic_block (insn,
+ insn ? get_last_insn () : NULL,
+ EXIT_BLOCK_PTR->prev_bb);
alloc_aux_for_block (new_bb, sizeof (struct reorder_block_def));
if (RBI (bb)->header)
new_bb->flags = bb->flags;
for (s = bb->succ; s; s = s->succ_next)
{
- n = make_edge (new_bb, s->dest, s->flags);
+ /* Since we are creating edges from a new block to successors
+ of another block (which therefore are known to be disjoint), there
+ is no need to actually check for duplicated edges. */
+ n = unchecked_make_edge (new_bb, s->dest, s->flags);
n->probability = s->probability;
if (new_count)
/* Take care for overflows! */
bb->count -= new_count;
if (e)
- {
- new_bb->frequency = EDGE_FREQUENCY (e);
- bb->frequency -= EDGE_FREQUENCY (e);
+ {
+ new_bb->frequency = EDGE_FREQUENCY (e);
+ bb->frequency -= EDGE_FREQUENCY (e);
- cfg_layout_redirect_edge (e, new_bb);
- }
+ cfg_layout_redirect_edge (e, new_bb);
+ }
if (bb->count < 0)
bb->count = 0;
bb->frequency = 0;
RBI (new_bb)->original = bb;
+ RBI (bb)->copy = new_bb;
return new_bb;
}
\f
CFG layout changes. It keeps LOOPS up-to-date if not null. */
void
-cfg_layout_initialize ()
+cfg_layout_initialize (loops)
+ struct loops *loops;
{
/* Our algorithm depends on fact that there are now dead jumptables
around the code. */
alloc_aux_for_blocks (sizeof (struct reorder_block_def));
- cleanup_unconditional_jumps ();
-
- scope_to_insns_initialize ();
+ cleanup_unconditional_jumps (loops);
record_effective_endpoints ();
}
+/* Splits superblocks. */
+static void
+break_superblocks ()
+{
+ sbitmap superblocks;
+ int i, need;
+
+ superblocks = sbitmap_alloc (n_basic_blocks);
+ sbitmap_zero (superblocks);
+
+ need = 0;
+
+ for (i = 0; i < n_basic_blocks; i++)
+ if (BASIC_BLOCK(i)->flags & BB_SUPERBLOCK)
+ {
+ BASIC_BLOCK(i)->flags &= ~BB_SUPERBLOCK;
+ SET_BIT (superblocks, i);
+ need = 1;
+ }
+
+ if (need)
+ {
+ rebuild_jump_labels (get_insns ());
+ find_many_sub_basic_blocks (superblocks);
+ }
+
+ free (superblocks);
+}
+
/* Finalize the changes: reorder insn list according to the sequence, enter
compensation code, rebuild scope forest. */
verify_insn_chain ();
#endif
- scope_to_insns_finalize ();
-
free_aux_for_blocks ();
+ break_superblocks ();
+
#ifdef ENABLE_CHECKING
verify_flow_info ();
#endif
OSDN Git Service
