#include "function.h"
#include "obstack.h"
#include "cfglayout.h"
+#include "cfgloop.h"
+#include "target.h"
+#include "ggc.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. */
-static rtx function_footer;
+rtx cfg_layout_function_footer;
static rtx skip_insns_after_block PARAMS ((basic_block));
static void record_effective_endpoints PARAMS ((void));
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));
+static void break_superblocks PARAMS ((void));
+static tree insn_scope PARAMS ((rtx));
\f
-static rtx
+rtx
unlink_insn_chain (first, last)
rtx first;
rtx last;
next_insn = NEXT_INSN (bb->end);
}
- function_footer = next_insn;
- if (function_footer)
- function_footer = unlink_insn_chain (function_footer, get_last_insn ());
+ cfg_layout_function_footer = next_insn;
+ if (cfg_layout_function_footer)
+ cfg_layout_function_footer = unlink_insn_chain (cfg_layout_function_footer, get_last_insn ());
}
\f
-/* Build a varray mapping INSN_UID to lexical block. Return it. */
+/* Data structures representing mapping of INSN_LOCATOR into scope blocks, line
+ numbers and files. In order to be GGC friendly we need to use separate
+ varrays. This also slightly improve the memory locality in binary search.
+ The _locs array contains locators where the given property change. The
+ block_locators_blocks contains the scope block that is used for all insn
+ locator greater than corresponding block_locators_locs value and smaller
+ than the following one. Similarly for the other properties. */
+static GTY(()) varray_type block_locators_locs;
+static GTY(()) varray_type block_locators_blocks;
+static GTY(()) varray_type line_locators_locs;
+static GTY(()) varray_type line_locators_lines;
+static GTY(()) varray_type file_locators_locs;
+static GTY(()) varray_type file_locators_files;
+int prologue_locator;
+int epilogue_locator;
+
+/* During the RTL expansion the lexical blocks and line numbers are
+ represented via INSN_NOTEs. Replace them by representation using
+ INSN_LOCATORs. */
void
-scope_to_insns_initialize ()
+insn_locators_initialize ()
{
tree block = NULL;
+ tree last_block = NULL;
rtx insn, next;
+ int loc = 0;
+ int line_number = 0, last_line_number = 0;
+ char *file_name = NULL, *last_file_name = NULL;
+
+ prologue_locator = epilogue_locator = 0;
+
+ VARRAY_INT_INIT (block_locators_locs, 32, "block_locators_locs");
+ VARRAY_TREE_INIT (block_locators_blocks, 32, "block_locators_blocks");
+ VARRAY_INT_INIT (line_locators_locs, 32, "line_locators_locs");
+ VARRAY_INT_INIT (line_locators_lines, 32, "line_locators_lines");
+ VARRAY_INT_INIT (file_locators_locs, 32, "file_locators_locs");
+ VARRAY_CHAR_PTR_INIT (file_locators_files, 32, "file_locators_files");
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)
- INSN_SCOPE (insn) = block;
+ if ((active_insn_p (insn)
+ && GET_CODE (PATTERN (insn)) != ADDR_VEC
+ && GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC)
+ || !NEXT_INSN (insn)
+ || (!prologue_locator && file_name))
+ {
+ if (last_block != block)
+ {
+ loc++;
+ VARRAY_PUSH_INT (block_locators_locs, loc);
+ VARRAY_PUSH_TREE (block_locators_blocks, block);
+ last_block = block;
+ }
+ if (last_line_number != line_number)
+ {
+ loc++;
+ VARRAY_PUSH_INT (line_locators_locs, loc);
+ VARRAY_PUSH_INT (line_locators_lines, line_number);
+ last_line_number = line_number;
+ }
+ if (last_file_name != file_name)
+ {
+ loc++;
+ VARRAY_PUSH_INT (file_locators_locs, loc);
+ VARRAY_PUSH_CHAR_PTR (file_locators_files, 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))
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;
}
}
}
}
+/* Return lexical scope block insn belong to. */
+static tree
+insn_scope (insn)
+ rtx insn;
+{
+ int max = VARRAY_ACTIVE_SIZE (block_locators_locs);
+ int min = 0;
+ int loc = INSN_LOCATOR (insn);
+
+ if (!max || !loc)
+ return NULL;
+ while (1)
+ {
+ int pos = (min + max) / 2;
+ int tmp = VARRAY_INT (block_locators_locs, pos);
+
+ if (tmp <= loc && min != pos)
+ min = pos;
+ else if (tmp > loc && max != pos)
+ max = pos;
+ else
+ {
+ min = pos;
+ break;
+ }
+ }
+ return VARRAY_TREE (block_locators_blocks, min);
+}
+
+/* Return line number of the statement that produced this insn. */
+int
+insn_line (insn)
+ rtx insn;
+{
+ int max = VARRAY_ACTIVE_SIZE (line_locators_locs);
+ int min = 0;
+ int loc = INSN_LOCATOR (insn);
+
+ if (!max || !loc)
+ return 0;
+ while (1)
+ {
+ int pos = (min + max) / 2;
+ int tmp = VARRAY_INT (line_locators_locs, pos);
+
+ if (tmp <= loc && min != pos)
+ min = pos;
+ else if (tmp > loc && max != pos)
+ max = pos;
+ else
+ {
+ min = pos;
+ break;
+ }
+ }
+ return VARRAY_INT (line_locators_lines, min);
+}
+
+/* Return source file of the statement that produced this insn. */
+const char *
+insn_file (insn)
+ rtx insn;
+{
+ int max = VARRAY_ACTIVE_SIZE (file_locators_locs);
+ int min = 0;
+ int loc = INSN_LOCATOR (insn);
+
+ if (!max || !loc)
+ return NULL;
+ while (1)
+ {
+ int pos = (min + max) / 2;
+ int tmp = VARRAY_INT (file_locators_locs, pos);
+
+ if (tmp <= loc && min != pos)
+ min = pos;
+ else if (tmp > loc && max != pos)
+ max = pos;
+ else
+ {
+ min = pos;
+ break;
+ }
+ }
+ return VARRAY_CHAR_PTR (file_locators_files, min);
+}
+
/* Rebuild all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes based
on the scope tree and the newly reordered instructions. */
void
-scope_to_insns_finalize ()
+reemit_insn_block_notes ()
{
tree cur_block = DECL_INITIAL (cfun->decl);
rtx insn, note;
{
tree this_block;
- this_block = INSN_SCOPE (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)
this_block = NULL;
for (i = 0; i < XVECLEN (body, 0); i++)
this_block = choose_inner_scope (this_block,
- INSN_SCOPE (XVECEXP (body, 0, i)));
+ insn_scope (XVECEXP (body, 0, i)));
}
if (! this_block)
continue;
if (index != n_basic_blocks)
abort ();
- NEXT_INSN (insn) = function_footer;
- if (function_footer)
- PREV_INSN (function_footer) = insn;
+ NEXT_INSN (insn) = cfg_layout_function_footer;
+ if (cfg_layout_function_footer)
+ PREV_INSN (cfg_layout_function_footer) = insn;
while (NEXT_INSN (insn))
insn = NEXT_INSN (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);
/* 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. */
+ 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;
{
basic_block bb;
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);
- flow_delete_block (bb);
+ delete_block (bb);
bb = prev;
}
else if (simplejump_p (bb->end))
cfg_layout_can_duplicate_bb_p (bb)
basic_block bb;
{
- rtx next;
edge s;
if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR)
/* 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 (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;
}
abort ();
break;
case NOTE_INSN_REPEATED_LINE_NUMBER:
- emit_note (NOTE_SOURCE_FILE (insn), NOTE_LINE_NUMBER (insn));
+ emit_line_note (NOTE_SOURCE_FILE (insn),
+ NOTE_LINE_NUMBER (insn));
break;
default:
abort ();
/* It is possible that no_line_number is set and the note
won't be emitted. */
- emit_note (NOTE_SOURCE_FILE (insn), NOTE_LINE_NUMBER (insn));
+ emit_line_note (NOTE_SOURCE_FILE (insn),
+ NOTE_LINE_NUMBER (insn));
}
break;
default:
delete_insn (last);
return insn;
}
-
-/* Redirect Edge to DEST. */
-void
-cfg_layout_redirect_edge (e, dest)
- edge e;
- basic_block dest;
-{
- basic_block src = e->src;
- basic_block old_next_bb = src->next_bb;
-
- /* 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. */
-
- src->next_bb = NULL;
- if (e->flags & EDGE_FALLTHRU)
- {
- /* In case we are redirecting fallthru edge to the branch edge
- of conditional jump, remove it. */
- if (src->succ->succ_next
- && !src->succ->succ_next->succ_next)
- {
- edge s = e->succ_next ? e->succ_next : src->succ;
- if (s->dest == dest
- && any_condjump_p (src->end)
- && onlyjump_p (src->end))
- delete_insn (src->end);
- }
- redirect_edge_succ_nodup (e, dest);
- }
- else
- redirect_edge_and_branch (e, dest);
-
- /* We don't want simplejumps in the insn stream during cfglayout. */
- if (simplejump_p (src->end))
- {
- delete_insn (src->end);
- delete_barrier (NEXT_INSN (src->end));
- src->succ->flags |= EDGE_FALLTHRU;
- }
- src->next_bb = old_next_bb;
-}
-
/* Create a duplicate of the basic block BB and redirect edge E into it. */
basic_block
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! */
new_bb->frequency = EDGE_FREQUENCY (e);
bb->frequency -= EDGE_FREQUENCY (e);
- cfg_layout_redirect_edge (e, new_bb);
+ redirect_edge_and_branch_force (e, new_bb);
}
if (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));
+ cfg_layout_rtl_register_cfg_hooks ();
- cleanup_unconditional_jumps ();
+ 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. */
void
cfg_layout_finalize ()
{
+#ifdef ENABLE_CHECKING
+ verify_flow_info ();
+#endif
+ rtl_register_cfg_hooks ();
fixup_fallthru_exit_predecessor ();
fixup_reorder_chain ();
free_aux_for_blocks ();
+ break_superblocks ();
+
#ifdef ENABLE_CHECKING
verify_flow_info ();
#endif
}
+
+#include "gt-cfglayout.h"
OSDN Git Service
