/* Basic block reordering routines for the GNU compiler.
- Copyright (C) 2000, 2001, 2003 Free Software Foundation, Inc.
+ Copyright (C) 2000, 2001, 2003, 2004 Free Software Foundation, Inc.
This file is part of GCC.
#include "cfgloop.h"
#include "target.h"
#include "ggc.h"
+#include "alloc-pool.h"
+#include "flags.h"
/* The contents of the current function definition are allocated
in this obstack, and all are freed at the end of the function. */
extern struct obstack flow_obstack;
/* Holds the interesting trailing notes for the function. */
-rtx cfg_layout_function_footer;
+rtx cfg_layout_function_footer, cfg_layout_function_header;
static rtx skip_insns_after_block (basic_block);
static void record_effective_endpoints (void);
static void change_scope (rtx, tree, tree);
void verify_insn_chain (void);
-static void cleanup_unconditional_jumps (struct loops *);
static void fixup_fallthru_exit_predecessor (void);
-static rtx duplicate_insn_chain (rtx, rtx);
-static void break_superblocks (void);
static tree insn_scope (rtx);
+static void update_unlikely_executed_notes (basic_block);
\f
rtx
unlink_insn_chain (rtx first, rtx last)
next_head = NULL_RTX;
if (bb->next_bb != EXIT_BLOCK_PTR)
- next_head = bb->next_bb->head;
+ next_head = BB_HEAD (bb->next_bb);
- for (last_insn = insn = bb->end; (insn = NEXT_INSN (insn)) != 0; )
+ for (last_insn = insn = BB_END (bb); (insn = NEXT_INSN (insn)) != 0; )
{
if (insn == next_head)
break;
case CODE_LABEL:
if (NEXT_INSN (insn)
- && GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
+ && JUMP_P (NEXT_INSN (insn))
&& (GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_VEC
|| GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_DIFF_VEC))
{
created by removing the basic block originally following
NOTE_INSN_LOOP_BEG. In such case reorder the notes. */
- for (insn = last_insn; insn != bb->end; insn = prev)
+ for (insn = last_insn; insn != BB_END (bb); insn = prev)
{
prev = PREV_INSN (insn);
- if (GET_CODE (insn) == NOTE)
+ if (NOTE_P (insn))
switch (NOTE_LINE_NUMBER (insn))
{
case NOTE_INSN_LOOP_END:
static rtx
label_for_bb (basic_block bb)
{
- rtx label = bb->head;
+ rtx label = BB_HEAD (bb);
- if (GET_CODE (label) != CODE_LABEL)
+ if (!LABEL_P (label))
{
- if (rtl_dump_file)
- fprintf (rtl_dump_file, "Emitting label for block %d\n", bb->index);
+ if (dump_file)
+ fprintf (dump_file, "Emitting label for block %d\n", bb->index);
label = block_label (bb);
}
static void
record_effective_endpoints (void)
{
- rtx next_insn = get_insns ();
+ rtx next_insn;
basic_block bb;
+ rtx insn;
+
+ for (insn = get_insns ();
+ insn
+ && NOTE_P (insn)
+ && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK;
+ insn = NEXT_INSN (insn))
+ continue;
+ if (!insn)
+ abort (); /* No basic blocks at all? */
+ if (PREV_INSN (insn))
+ cfg_layout_function_header =
+ unlink_insn_chain (get_insns (), PREV_INSN (insn));
+ else
+ cfg_layout_function_header = NULL_RTX;
+ next_insn = get_insns ();
FOR_EACH_BB (bb)
{
rtx end;
- if (PREV_INSN (bb->head) && next_insn != bb->head)
- RBI (bb)->header = unlink_insn_chain (next_insn,
- PREV_INSN (bb->head));
+ if (PREV_INSN (BB_HEAD (bb)) && next_insn != BB_HEAD (bb))
+ bb->rbi->header = unlink_insn_chain (next_insn,
+ PREV_INSN (BB_HEAD (bb)));
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);
- next_insn = NEXT_INSN (bb->end);
+ if (NEXT_INSN (BB_END (bb)) && BB_END (bb) != end)
+ bb->rbi->footer = unlink_insn_chain (NEXT_INSN (BB_END (bb)), end);
+ next_insn = NEXT_INSN (BB_END (bb));
}
cfg_layout_function_footer = next_insn;
rtx insn, next;
int loc = 0;
int line_number = 0, last_line_number = 0;
- char *file_name = NULL, *last_file_name = NULL;
+ const char *file_name = NULL, *last_file_name = NULL;
prologue_locator = epilogue_locator = 0;
for (insn = get_insns (); insn; insn = next)
{
+ int active = 0;
+
next = NEXT_INSN (insn);
- if ((active_insn_p (insn)
- && GET_CODE (PATTERN (insn)) != ADDR_VEC
- && GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC)
- || !NEXT_INSN (insn)
+ if (NOTE_P (insn))
+ {
+ switch (NOTE_LINE_NUMBER (insn))
+ {
+ case NOTE_INSN_BLOCK_BEG:
+ case NOTE_INSN_BLOCK_END:
+ abort ();
+
+ default:
+ if (NOTE_LINE_NUMBER (insn) > 0)
+ {
+ expanded_location xloc;
+ NOTE_EXPANDED_LOCATION (xloc, insn);
+ line_number = xloc.line;
+ file_name = xloc.file;
+ }
+ break;
+ }
+ }
+ else
+ active = (active_insn_p (insn)
+ && GET_CODE (PATTERN (insn)) != ADDR_VEC
+ && GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC);
+
+ check_block_change (insn, &block);
+
+ if (active
+ || !next
|| (!prologue_locator && file_name))
{
if (last_block != block)
{
loc++;
VARRAY_PUSH_INT (file_locators_locs, loc);
- VARRAY_PUSH_CHAR_PTR (file_locators_files, file_name);
+ VARRAY_PUSH_CHAR_PTR (file_locators_files, (char *) file_name);
last_file_name = file_name;
}
- }
- if (!prologue_locator && file_name)
- prologue_locator = loc;
- if (!NEXT_INSN (insn))
- epilogue_locator = loc;
- if (active_insn_p (insn))
- INSN_LOCATOR (insn) = loc;
- else if (GET_CODE (insn) == NOTE)
- {
- switch (NOTE_LINE_NUMBER (insn))
- {
- case NOTE_INSN_BLOCK_BEG:
- block = NOTE_BLOCK (insn);
- delete_insn (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:
- if (NOTE_LINE_NUMBER (insn) > 0)
- {
- line_number = NOTE_LINE_NUMBER (insn);
- file_name = (char *)NOTE_SOURCE_FILE (insn);
- }
- break;
- }
+ if (!prologue_locator && file_name)
+ prologue_locator = loc;
+ if (!next)
+ epilogue_locator = loc;
+ if (active)
+ INSN_LOCATOR (insn) = loc;
}
}
/* 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);
+
+ free_block_changes ();
}
/* For each lexical block, set BLOCK_NUMBER to the depth at which it is
int min = 0;
int loc = INSN_LOCATOR (insn);
+ /* When block_locators_locs was initialized, the pro- and epilogue
+ insns didn't exist yet and can therefore not be found this way.
+ But we know that they belong to the outer most block of the
+ current function.
+ Without this test, the prologue would be put inside the block of
+ the first valid instruction in the function and when that first
+ insn is part of an inlined function then the low_pc of that
+ inlined function is messed up. Likewise for the epilogue and
+ the last valid instruction. */
+ if (loc == prologue_locator || loc == epilogue_locator)
+ return DECL_INITIAL (cfun->decl);
+
if (!max || !loc)
return NULL;
while (1)
return VARRAY_TREE (block_locators_blocks, min);
}
-/* Return line number of the statement that produced this insn. */
+/* Return line number of the statement specified by the locator. */
int
-insn_line (rtx insn)
+locator_line (int loc)
{
int max = VARRAY_ACTIVE_SIZE (line_locators_locs);
int min = 0;
- int loc = INSN_LOCATOR (insn);
if (!max || !loc)
return 0;
return VARRAY_INT (line_locators_lines, min);
}
-/* Return source file of the statement that produced this insn. */
+/* Return line number of the statement that produced this insn. */
+int
+insn_line (rtx insn)
+{
+ return locator_line (INSN_LOCATOR (insn));
+}
+
+/* Return source file of the statement specified by LOC. */
const char *
-insn_file (rtx insn)
+locator_file (int loc)
{
int max = VARRAY_ACTIVE_SIZE (file_locators_locs);
int min = 0;
- int loc = INSN_LOCATOR (insn);
if (!max || !loc)
return NULL;
return VARRAY_CHAR_PTR (file_locators_files, min);
}
+/* Return source file of the statement that produced this insn. */
+const char *
+insn_file (rtx insn)
+{
+ return locator_file (INSN_LOCATOR (insn));
+}
+
/* Rebuild all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes based
on the scope tree and the newly reordered instructions. */
}
/* change_scope emits before the insn, not after. */
- note = emit_note (NULL, NOTE_INSN_DELETED);
+ note = emit_note (NOTE_INSN_DELETED);
change_scope (note, cur_block, DECL_INITIAL (cfun->decl));
delete_insn (note);
int index;
rtx insn = NULL;
+ if (cfg_layout_function_header)
+ {
+ set_first_insn (cfg_layout_function_header);
+ insn = cfg_layout_function_header;
+ while (NEXT_INSN (insn))
+ insn = NEXT_INSN (insn);
+ }
+
/* First do the bulk reordering -- rechain the blocks without regard to
the needed changes to jumps and labels. */
for (bb = ENTRY_BLOCK_PTR->next_bb, index = 0;
bb != 0;
- bb = RBI (bb)->next, index++)
+ bb = bb->rbi->next, index++)
{
- if (RBI (bb)->header)
+ if (bb->rbi->header)
{
if (insn)
- NEXT_INSN (insn) = RBI (bb)->header;
+ NEXT_INSN (insn) = bb->rbi->header;
else
- set_first_insn (RBI (bb)->header);
- PREV_INSN (RBI (bb)->header) = insn;
- insn = RBI (bb)->header;
+ set_first_insn (bb->rbi->header);
+ PREV_INSN (bb->rbi->header) = insn;
+ insn = bb->rbi->header;
while (NEXT_INSN (insn))
insn = NEXT_INSN (insn);
}
if (insn)
- NEXT_INSN (insn) = bb->head;
+ NEXT_INSN (insn) = BB_HEAD (bb);
else
- set_first_insn (bb->head);
- PREV_INSN (bb->head) = insn;
- insn = bb->end;
- if (RBI (bb)->footer)
+ set_first_insn (BB_HEAD (bb));
+ PREV_INSN (BB_HEAD (bb)) = insn;
+ insn = BB_END (bb);
+ if (bb->rbi->footer)
{
- NEXT_INSN (insn) = RBI (bb)->footer;
- PREV_INSN (RBI (bb)->footer) = insn;
+ NEXT_INSN (insn) = bb->rbi->footer;
+ PREV_INSN (bb->rbi->footer) = insn;
while (NEXT_INSN (insn))
insn = NEXT_INSN (insn);
}
#ifdef ENABLE_CHECKING
verify_insn_chain ();
#endif
+ delete_dead_jumptables ();
/* Now add jumps and labels as needed to match the blocks new
outgoing edges. */
- for (bb = ENTRY_BLOCK_PTR->next_bb; bb ; bb = RBI (bb)->next)
+ for (bb = ENTRY_BLOCK_PTR->next_bb; bb ; bb = bb->rbi->next)
{
edge e_fall, e_taken, e;
rtx bb_end_insn;
basic_block nb;
+ basic_block old_bb;
if (bb->succ == NULL)
continue;
else if (! (e->flags & EDGE_EH))
e_taken = e;
- bb_end_insn = bb->end;
- if (GET_CODE (bb_end_insn) == JUMP_INSN)
+ bb_end_insn = BB_END (bb);
+ if (JUMP_P (bb_end_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))
+ if (bb->rbi->next == e_fall->dest
+ || e_fall->dest == EXIT_BLOCK_PTR)
continue;
/* The degenerated case of conditional jump jumping to the next
e_fake = unchecked_make_edge (bb, e_fall->dest, 0);
- if (!redirect_jump (bb->end, block_label (bb), 0))
+ if (!redirect_jump (BB_END (bb), block_label (bb), 0))
abort ();
- note = find_reg_note (bb->end, REG_BR_PROB, NULL_RTX);
+ note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX);
if (note)
{
int prob = INTVAL (XEXP (note, 0));
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. */
- else if (RBI (bb)->next != e_taken->dest)
+ else if (bb->rbi->next != e_taken->dest)
{
rtx note = find_reg_note (bb_end_insn, REG_BR_PROB, 0);
if (note
&& INTVAL (XEXP (note, 0)) < REG_BR_PROB_BASE / 2
&& invert_jump (bb_end_insn,
- label_for_bb (e_fall->dest), 0))
+ (e_fall->dest == EXIT_BLOCK_PTR
+ ? NULL_RTX
+ : label_for_bb (e_fall->dest)), 0))
{
e_fall->flags &= ~EDGE_FALLTHRU;
+#ifdef ENABLE_CHECKING
+ if (!could_fall_through (e_taken->src, e_taken->dest))
+ abort ();
+#endif
e_taken->flags |= EDGE_FALLTHRU;
update_br_prob_note (bb);
e = e_fall, e_fall = e_taken, e_taken = e;
}
}
+ /* If the "jumping" edge is a crossing edge, and the fall
+ through edge is non-crossing, leave things as they are. */
+ else if ((e_taken->flags & EDGE_CROSSING)
+ && !(e_fall->flags & EDGE_CROSSING))
+ continue;
+
/* 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))
+ (e_fall->dest == EXIT_BLOCK_PTR
+ ? NULL_RTX
+ : label_for_bb (e_fall->dest)), 0))
{
e_fall->flags &= ~EDGE_FALLTHRU;
+#ifdef ENABLE_CHECKING
+ if (!could_fall_through (e_taken->src, e_taken->dest))
+ abort ();
+#endif
e_taken->flags |= EDGE_FALLTHRU;
update_br_prob_note (bb);
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)->next == e_fall->dest)
+ if (bb->rbi->next == e_fall->dest)
continue;
bb_end_insn = skip_insns_after_block (bb);
#else
continue;
/* If the fallthru block is still next, nothing to do. */
- if (RBI (bb)->next == e_fall->dest)
+ if (bb->rbi->next == e_fall->dest)
continue;
/* A fallthru to exit block. */
- if (!RBI (bb)->next && e_fall->dest == EXIT_BLOCK_PTR)
+ if (e_fall->dest == EXIT_BLOCK_PTR)
continue;
}
nb = force_nonfallthru (e_fall);
if (nb)
{
- alloc_aux_for_block (nb, sizeof (struct reorder_block_def));
- RBI (nb)->visited = 1;
- RBI (nb)->next = RBI (bb)->next;
- RBI (bb)->next = nb;
+ initialize_bb_rbi (nb);
+ nb->rbi->visited = 1;
+ nb->rbi->next = bb->rbi->next;
+ bb->rbi->next = nb;
/* Don't process this new block. */
+ old_bb = bb;
bb = nb;
+
+ /* Make sure new bb is tagged for correct section (same as
+ fall-thru source, since you cannot fall-throu across
+ section boundaries). */
+ BB_COPY_PARTITION (e_fall->src, bb->pred->src);
+ if (flag_reorder_blocks_and_partition
+ && targetm.have_named_sections)
+ {
+ if (BB_PARTITION (bb->pred->src) == BB_COLD_PARTITION)
+ {
+ rtx new_note;
+ rtx note = BB_HEAD (e_fall->src);
+
+ while (!INSN_P (note)
+ && note != BB_END (e_fall->src))
+ note = NEXT_INSN (note);
+
+ new_note = emit_note_before
+ (NOTE_INSN_UNLIKELY_EXECUTED_CODE,
+ note);
+ NOTE_BASIC_BLOCK (new_note) = bb;
+ }
+ if (JUMP_P (BB_END (bb))
+ && !any_condjump_p (BB_END (bb))
+ && (bb->succ->flags & EDGE_CROSSING))
+ REG_NOTES (BB_END (bb)) = gen_rtx_EXPR_LIST
+ (REG_CROSSING_JUMP, NULL_RTX, REG_NOTES (BB_END (bb)));
+ }
}
}
/* Put basic_block_info in the new order. */
- if (rtl_dump_file)
+ if (dump_file)
{
- fprintf (rtl_dump_file, "Reordered sequence:\n");
- for (bb = ENTRY_BLOCK_PTR->next_bb, index = 0; bb; bb = RBI (bb)->next, index ++)
+ fprintf (dump_file, "Reordered sequence:\n");
+ for (bb = ENTRY_BLOCK_PTR->next_bb, index = 0;
+ bb;
+ bb = bb->rbi->next, index++)
{
- fprintf (rtl_dump_file, " %i ", index);
- if (RBI (bb)->original)
- fprintf (rtl_dump_file, "duplicate of %i ",
- RBI (bb)->original->index);
- else if (forwarder_block_p (bb) && GET_CODE (bb->head) != CODE_LABEL)
- fprintf (rtl_dump_file, "compensation ");
+ fprintf (dump_file, " %i ", index);
+ if (bb->rbi->original)
+ fprintf (dump_file, "duplicate of %i ",
+ bb->rbi->original->index);
+ else if (forwarder_block_p (bb)
+ && !LABEL_P (BB_HEAD (bb)))
+ fprintf (dump_file, "compensation ");
else
- fprintf (rtl_dump_file, "bb %i ", bb->index);
- fprintf (rtl_dump_file, " [%i]\n", bb->frequency);
+ fprintf (dump_file, "bb %i ", bb->index);
+ fprintf (dump_file, " [%i]\n", bb->frequency);
}
}
bb = ENTRY_BLOCK_PTR->next_bb;
index = 0;
- for (; bb; prev_bb = bb, bb = RBI (bb)->next, index ++)
+ for (; bb; prev_bb = bb, bb = bb->rbi->next, index ++)
{
bb->index = index;
BASIC_BLOCK (index) = bb;
+ update_unlikely_executed_notes (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;
+
+ /* Annoying special case - jump around dead jumptables left in the code. */
+ FOR_EACH_BB (bb)
+ {
+ edge e;
+ for (e = bb->succ; e && !(e->flags & EDGE_FALLTHRU); e = e->succ_next)
+ continue;
+ if (e && !can_fallthru (e->src, e->dest))
+ force_nonfallthru (e);
+ }
+}
+\f
+/* Update the basic block number information in any
+ NOTE_INSN_UNLIKELY_EXECUTED_CODE notes within the basic block. */
+
+static void
+update_unlikely_executed_notes (basic_block bb)
+{
+ rtx cur_insn;
+
+ for (cur_insn = BB_HEAD (bb); cur_insn != BB_END (bb);
+ cur_insn = NEXT_INSN (cur_insn))
+ if (NOTE_P (cur_insn)
+ && NOTE_LINE_NUMBER (cur_insn) == NOTE_INSN_UNLIKELY_EXECUTED_CODE)
+ NOTE_BASIC_BLOCK (cur_insn) = bb;
}
\f
/* Perform sanity checks on the insn chain.
abort ();
}
\f
-/* Remove any unconditional jumps and forwarder block creating fallthru
- 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 (struct loops *loops)
-{
- basic_block bb;
-
- FOR_EACH_BB (bb)
- {
- if (!bb->succ)
- continue;
- if (bb->succ->flags & EDGE_FALLTHRU)
- continue;
- if (!bb->succ->succ_next)
- {
- rtx insn;
- if (GET_CODE (bb->head) != CODE_LABEL && forwarder_block_p (bb)
- && bb->prev_bb != ENTRY_BLOCK_PTR)
- {
- basic_block prev = bb->prev_bb;
-
- if (rtl_dump_file)
- fprintf (rtl_dump_file, "Removing forwarder BB %i\n",
- bb->index);
-
- 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);
- delete_block (bb);
- bb = prev;
- }
- else if (simplejump_p (bb->end))
- {
- rtx jump = bb->end;
-
- if (rtl_dump_file)
- fprintf (rtl_dump_file, "Removing jump %i in BB %i\n",
- INSN_UID (jump), bb->index);
- delete_insn (jump);
- bb->succ->flags |= EDGE_FALLTHRU;
- }
- else
- continue;
-
- insn = NEXT_INSN (bb->end);
- while (insn
- && (GET_CODE (insn) != NOTE
- || NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK))
- {
- rtx next = NEXT_INSN (insn);
-
- if (GET_CODE (insn) == BARRIER)
- delete_barrier (insn);
-
- insn = next;
- }
- }
- }
-}
-\f
-/* The block falling through to exit must be the last one in the
- reordered chain. Ensure that this condition is met. */
+/* If we have assembler epilogues, the block falling through to exit must
+ be the last one in the reordered chain when we reach final. Ensure
+ that this condition is met. */
static void
fixup_fallthru_exit_predecessor (void)
{
edge e;
basic_block bb = NULL;
+ /* This transformation is not valid before reload, because we might separate
+ a call from the instruction that copies the return value. */
+ if (! reload_completed)
+ abort ();
+
for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
if (e->flags & EDGE_FALLTHRU)
bb = e->src;
- if (bb && RBI (bb)->next)
+ if (bb && bb->rbi->next)
{
basic_block c = ENTRY_BLOCK_PTR->next_bb;
- while (RBI (c)->next != bb)
- c = RBI (c)->next;
+ /* If the very first block is the one with the fall-through exit
+ edge, we have to split that block. */
+ if (c == bb)
+ {
+ bb = split_block (bb, NULL)->dest;
+ initialize_bb_rbi (bb);
+ bb->rbi->next = c->rbi->next;
+ c->rbi->next = bb;
+ bb->rbi->footer = c->rbi->footer;
+ c->rbi->footer = NULL;
+ }
+
+ while (c->rbi->next != bb)
+ c = c->rbi->next;
- RBI (c)->next = RBI (bb)->next;
- while (RBI (c)->next)
- c = RBI (c)->next;
+ c->rbi->next = bb->rbi->next;
+ while (c->rbi->next)
+ c = c->rbi->next;
- RBI (c)->next = bb;
- RBI (bb)->next = NULL;
+ c->rbi->next = bb;
+ bb->rbi->next = NULL;
}
}
\f
/* Return true in case it is possible to duplicate the basic block BB. */
+/* We do not want to declare the function in a header file, since it should
+ only be used through the cfghooks interface, and we do not want to move
+ it to cfgrtl.c since it would require also moving quite a lot of related
+ code. */
+extern bool cfg_layout_can_duplicate_bb_p (basic_block);
+
bool
cfg_layout_can_duplicate_bb_p (basic_block bb)
{
- edge s;
-
- if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR)
- return false;
-
- /* 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 difficult to do, as the instructions
computing jump destination may be hoisted outside the basic block. */
- if (tablejump_p (bb->end, NULL, NULL))
+ if (tablejump_p (BB_END (bb), 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;
+ rtx insn = BB_HEAD (bb);
while (1)
{
- if (INSN_P (insn) && (*targetm.cannot_copy_insn_p) (insn))
+ if (INSN_P (insn) && targetm.cannot_copy_insn_p (insn))
return false;
- if (insn == bb->end)
+ if (insn == BB_END (bb))
break;
insn = NEXT_INSN (insn);
}
return true;
}
-static rtx
+rtx
duplicate_insn_chain (rtx from, rtx to)
{
rtx insn, last;
/* Avoid updating of boundaries of previous basic block. The
note will get removed from insn stream in fixup. */
- last = emit_note (NULL, NOTE_INSN_DELETED);
+ last = emit_note (NOTE_INSN_DELETED);
/* Create copy at the end of INSN chain. The chain will
be reordered later. */
in first BB, we may want to copy the block. */
case NOTE_INSN_PROLOGUE_END:
- case NOTE_INSN_LOOP_VTOP:
- case NOTE_INSN_LOOP_CONT:
case NOTE_INSN_LOOP_BEG:
case NOTE_INSN_LOOP_END:
/* Strip down the loop notes - we don't really want to keep
abort ();
break;
case NOTE_INSN_REPEATED_LINE_NUMBER:
- emit_line_note (NOTE_SOURCE_FILE (insn),
- NOTE_LINE_NUMBER (insn));
+ case NOTE_INSN_UNLIKELY_EXECUTED_CODE:
+ emit_note_copy (insn);
break;
default:
abort ();
/* It is possible that no_line_number is set and the note
won't be emitted. */
- emit_line_note (NOTE_SOURCE_FILE (insn),
- NOTE_LINE_NUMBER (insn));
+ emit_note_copy (insn);
}
break;
default:
delete_insn (last);
return insn;
}
-/* Create a duplicate of the basic block BB and redirect edge E into it. */
+/* Create a duplicate of the basic block BB. */
+
+/* We do not want to declare the function in a header file, since it should
+ only be used through the cfghooks interface, and we do not want to move
+ it to cfgrtl.c since it would require also moving quite a lot of related
+ code. */
+extern basic_block cfg_layout_duplicate_bb (basic_block);
basic_block
-cfg_layout_duplicate_bb (basic_block bb, edge e)
+cfg_layout_duplicate_bb (basic_block bb)
{
rtx insn;
- edge s, n;
basic_block new_bb;
- gcov_type new_count = e ? e->count : 0;
-
- if (bb->count < new_count)
- new_count = bb->count;
- if (!bb->pred)
- abort ();
-#ifdef ENABLE_CHECKING
- if (!cfg_layout_can_duplicate_bb_p (bb))
- abort ();
-#endif
- insn = duplicate_insn_chain (bb->head, bb->end);
+ insn = duplicate_insn_chain (BB_HEAD (bb), BB_END (bb));
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)
+ BB_COPY_PARTITION (new_bb, bb);
+ if (bb->rbi->header)
{
- insn = RBI (bb)->header;
+ insn = bb->rbi->header;
while (NEXT_INSN (insn))
insn = NEXT_INSN (insn);
- insn = duplicate_insn_chain (RBI (bb)->header, insn);
+ insn = duplicate_insn_chain (bb->rbi->header, insn);
if (insn)
- RBI (new_bb)->header = unlink_insn_chain (insn, get_last_insn ());
+ new_bb->rbi->header = unlink_insn_chain (insn, get_last_insn ());
}
- if (RBI (bb)->footer)
+ if (bb->rbi->footer)
{
- insn = RBI (bb)->footer;
+ insn = bb->rbi->footer;
while (NEXT_INSN (insn))
insn = NEXT_INSN (insn);
- insn = duplicate_insn_chain (RBI (bb)->footer, insn);
+ insn = duplicate_insn_chain (bb->rbi->footer, insn);
if (insn)
- RBI (new_bb)->footer = unlink_insn_chain (insn, get_last_insn ());
+ new_bb->rbi->footer = unlink_insn_chain (insn, get_last_insn ());
}
if (bb->global_live_at_start)
COPY_REG_SET (new_bb->global_live_at_end, bb->global_live_at_end);
}
- new_bb->loop_depth = bb->loop_depth;
- new_bb->flags = bb->flags;
- for (s = bb->succ; s; s = s->succ_next)
- {
- /* 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! */
- n->count = s->count * (new_count * 10000 / bb->count) / 10000;
- else
- n->count = 0;
- s->count -= n->count;
- }
-
- new_bb->count = new_count;
- bb->count -= new_count;
-
- if (e)
- {
- new_bb->frequency = EDGE_FREQUENCY (e);
- bb->frequency -= EDGE_FREQUENCY (e);
-
- redirect_edge_and_branch_force (e, new_bb);
- }
-
- if (bb->count < 0)
- bb->count = 0;
- if (bb->frequency < 0)
- bb->frequency = 0;
-
- RBI (new_bb)->original = bb;
- RBI (bb)->copy = new_bb;
return new_bb;
}
\f
/* Main entry point to this module - initialize the datastructures for
- CFG layout changes. It keeps LOOPS up-to-date if not null. */
+ CFG layout changes. It keeps LOOPS up-to-date if not null.
+
+ FLAGS is a set of additional flags to pass to cleanup_cfg(). It should
+ include CLEANUP_UPDATE_LIFE if liveness information must be kept up
+ to date. */
void
-cfg_layout_initialize (struct loops *loops)
+cfg_layout_initialize (unsigned int flags)
{
- /* Our algorithm depends on fact that there are now dead jumptables
+ basic_block bb;
+
+ /* Our algorithm depends on fact that there are no dead jumptables
around the code. */
- alloc_aux_for_blocks (sizeof (struct reorder_block_def));
- cfg_layout_rtl_register_cfg_hooks ();
+ alloc_rbi_pool ();
+
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
+ initialize_bb_rbi (bb);
- cleanup_unconditional_jumps (loops);
+ cfg_layout_rtl_register_cfg_hooks ();
record_effective_endpoints ();
+
+ cleanup_cfg (CLEANUP_CFGLAYOUT | flags);
}
/* Splits superblocks. */
-static void
+void
break_superblocks (void)
{
sbitmap superblocks;
- int i, need;
+ bool need = false;
+ basic_block bb;
- superblocks = sbitmap_alloc (n_basic_blocks);
+ superblocks = sbitmap_alloc (last_basic_block);
sbitmap_zero (superblocks);
- need = 0;
-
- for (i = 0; i < n_basic_blocks; i++)
- if (BASIC_BLOCK(i)->flags & BB_SUPERBLOCK)
+ FOR_EACH_BB (bb)
+ if (bb->flags & BB_SUPERBLOCK)
{
- BASIC_BLOCK(i)->flags &= ~BB_SUPERBLOCK;
- SET_BIT (superblocks, i);
- need = 1;
+ bb->flags &= ~BB_SUPERBLOCK;
+ SET_BIT (superblocks, bb->index);
+ need = true;
}
if (need)
void
cfg_layout_finalize (void)
{
+ basic_block bb;
+
#ifdef ENABLE_CHECKING
verify_flow_info ();
#endif
rtl_register_cfg_hooks ();
- fixup_fallthru_exit_predecessor ();
+ if (reload_completed
+#ifdef HAVE_epilogue
+ && !HAVE_epilogue
+#endif
+ )
+ fixup_fallthru_exit_predecessor ();
fixup_reorder_chain ();
#ifdef ENABLE_CHECKING
verify_insn_chain ();
#endif
- free_aux_for_blocks ();
+ free_rbi_pool ();
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
+ bb->rbi = NULL;
break_superblocks ();
#endif
}
+/* Checks whether all N blocks in BBS array can be copied. */
+bool
+can_copy_bbs_p (basic_block *bbs, unsigned n)
+{
+ unsigned i;
+ edge e;
+ int ret = true;
+
+ for (i = 0; i < n; i++)
+ bbs[i]->rbi->duplicated = 1;
+
+ for (i = 0; i < n; i++)
+ {
+ /* In case we should redirect abnormal edge during duplication, fail. */
+ for (e = bbs[i]->succ; e; e = e->succ_next)
+ if ((e->flags & EDGE_ABNORMAL)
+ && e->dest->rbi->duplicated)
+ {
+ ret = false;
+ goto end;
+ }
+
+ if (!can_duplicate_block_p (bbs[i]))
+ {
+ ret = false;
+ break;
+ }
+ }
+
+end:
+ for (i = 0; i < n; i++)
+ bbs[i]->rbi->duplicated = 0;
+
+ return ret;
+}
+
+/* Duplicates N basic blocks stored in array BBS. Newly created basic blocks
+ are placed into array NEW_BBS in the same order. Edges from basic blocks
+ in BBS are also duplicated and copies of those of them
+ that lead into BBS are redirected to appropriate newly created block. The
+ function assigns bbs into loops (copy of basic block bb is assigned to
+ bb->loop_father->copy loop, so this must be set up correctly in advance)
+ and updates dominators locally (LOOPS structure that contains the information
+ about dominators is passed to enable this).
+
+ BASE is the superloop to that basic block belongs; if its header or latch
+ is copied, we do not set the new blocks as header or latch.
+
+ Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
+ also in the same order. */
+
+void
+copy_bbs (basic_block *bbs, unsigned n, basic_block *new_bbs,
+ edge *edges, unsigned n_edges, edge *new_edges,
+ struct loop *base)
+{
+ unsigned i, j;
+ basic_block bb, new_bb, dom_bb;
+ edge e;
+
+ /* Duplicate bbs, update dominators, assign bbs to loops. */
+ for (i = 0; i < n; i++)
+ {
+ /* Duplicate. */
+ bb = bbs[i];
+ new_bb = new_bbs[i] = duplicate_block (bb, NULL);
+ bb->rbi->duplicated = 1;
+ /* Add to loop. */
+ add_bb_to_loop (new_bb, bb->loop_father->copy);
+ /* Possibly set header. */
+ if (bb->loop_father->header == bb && bb->loop_father != base)
+ new_bb->loop_father->header = new_bb;
+ /* Or latch. */
+ if (bb->loop_father->latch == bb && bb->loop_father != base)
+ new_bb->loop_father->latch = new_bb;
+ }
+
+ /* Set dominators. */
+ for (i = 0; i < n; i++)
+ {
+ bb = bbs[i];
+ new_bb = new_bbs[i];
+
+ dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
+ if (dom_bb->rbi->duplicated)
+ {
+ dom_bb = dom_bb->rbi->copy;
+ set_immediate_dominator (CDI_DOMINATORS, new_bb, dom_bb);
+ }
+ }
+
+ /* Redirect edges. */
+ for (j = 0; j < n_edges; j++)
+ new_edges[j] = NULL;
+ for (i = 0; i < n; i++)
+ {
+ new_bb = new_bbs[i];
+ bb = bbs[i];
+
+ for (e = new_bb->succ; e; e = e->succ_next)
+ {
+ for (j = 0; j < n_edges; j++)
+ if (edges[j] && edges[j]->src == bb && edges[j]->dest == e->dest)
+ new_edges[j] = e;
+
+ if (!e->dest->rbi->duplicated)
+ continue;
+ redirect_edge_and_branch_force (e, e->dest->rbi->copy);
+ }
+ }
+
+ /* Clear information about duplicates. */
+ for (i = 0; i < n; i++)
+ bbs[i]->rbi->duplicated = 0;
+}
+
#include "gt-cfglayout.h"
OSDN Git Service
