/* Basic block reordering routines for the GNU compiler.
- Copyright (C) 2000, 2001, 2003, 2004 Free Software Foundation, Inc.
+ Copyright (C) 2000, 2001, 2003, 2004, 2005 Free Software Foundation, Inc.
This file is part of GCC.
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA. */
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA. */
#include "config.h"
#include "system.h"
#include "ggc.h"
#include "alloc-pool.h"
#include "flags.h"
+#include "tree-pass.h"
/* Holds the interesting trailing notes for the function. */
rtx cfg_layout_function_footer, cfg_layout_function_header;
void verify_insn_chain (void);
static void fixup_fallthru_exit_predecessor (void);
static tree insn_scope (rtx);
-static void update_unlikely_executed_notes (basic_block);
\f
rtx
unlink_insn_chain (rtx first, rtx last)
rtx end;
if (PREV_INSN (BB_HEAD (bb)) && next_insn != BB_HEAD (bb))
- bb->rbi->header = unlink_insn_chain (next_insn,
+ bb->il.rtl->header = unlink_insn_chain (next_insn,
PREV_INSN (BB_HEAD (bb)));
end = skip_insns_after_block (bb);
if (NEXT_INSN (BB_END (bb)) && BB_END (bb) != end)
- bb->rbi->footer = unlink_insn_chain (NEXT_INSN (BB_END (bb)), end);
+ bb->il.rtl->footer = unlink_insn_chain (NEXT_INSN (BB_END (bb)), end);
next_insn = NEXT_INSN (BB_END (bb));
}
cfg_layout_function_footer = unlink_insn_chain (cfg_layout_function_footer, get_last_insn ());
}
\f
+DEF_VEC_I(int);
+DEF_VEC_ALLOC_I(int,heap);
+
/* 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.
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 VEC(int,heap) *block_locators_locs;
+static GTY(()) VEC(tree,gc) *block_locators_blocks;
+static VEC(int,heap) *line_locators_locs;
+static VEC(int,heap) *line_locators_lines;
+static VEC(int,heap) *file_locators_locs;
static GTY(()) varray_type file_locators_files;
int prologue_locator;
int epilogue_locator;
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");
+ block_locators_locs = VEC_alloc (int, heap, 32);
+ block_locators_blocks = VEC_alloc (tree, gc, 32);
+ line_locators_locs = VEC_alloc (int, heap, 32);
+ line_locators_lines = VEC_alloc (int, heap, 32);
+ file_locators_locs = VEC_alloc (int, heap, 32);
VARRAY_CHAR_PTR_INIT (file_locators_files, 32, "file_locators_files");
for (insn = get_insns (); insn; insn = next)
if (last_block != block)
{
loc++;
- VARRAY_PUSH_INT (block_locators_locs, loc);
- VARRAY_PUSH_TREE (block_locators_blocks, block);
+ VEC_safe_push (int, heap, block_locators_locs, loc);
+ VEC_safe_push (tree, gc, 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);
+ VEC_safe_push (int, heap, line_locators_locs, loc);
+ VEC_safe_push (int, heap, line_locators_lines, line_number);
last_line_number = line_number;
}
if (last_file_name != file_name)
{
loc++;
- VARRAY_PUSH_INT (file_locators_locs, loc);
+ VEC_safe_push (int, heap, file_locators_locs, loc);
VARRAY_PUSH_CHAR_PTR (file_locators_files, (char *) file_name);
last_file_name = file_name;
}
free_block_changes ();
}
+struct tree_opt_pass pass_insn_locators_initialize =
+{
+ "locators", /* name */
+ NULL, /* gate */
+ insn_locators_initialize, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ 0, /* tv_id */
+ 0, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_dump_func, /* todo_flags_finish */
+ 0 /* letter */
+};
+
+
/* For each lexical block, set BLOCK_NUMBER to the depth at which it is
found in the block tree. */
static tree
insn_scope (rtx insn)
{
- int max = VARRAY_ACTIVE_SIZE (block_locators_locs);
+ int max = VEC_length (int, block_locators_locs);
int min = 0;
int loc = INSN_LOCATOR (insn);
while (1)
{
int pos = (min + max) / 2;
- int tmp = VARRAY_INT (block_locators_locs, pos);
+ int tmp = VEC_index (int, block_locators_locs, pos);
if (tmp <= loc && min != pos)
min = pos;
break;
}
}
- return VARRAY_TREE (block_locators_blocks, min);
+ return VEC_index (tree, block_locators_blocks, min);
}
/* Return line number of the statement specified by the locator. */
int
locator_line (int loc)
{
- int max = VARRAY_ACTIVE_SIZE (line_locators_locs);
+ int max = VEC_length (int, line_locators_locs);
int min = 0;
if (!max || !loc)
while (1)
{
int pos = (min + max) / 2;
- int tmp = VARRAY_INT (line_locators_locs, pos);
+ int tmp = VEC_index (int, line_locators_locs, pos);
if (tmp <= loc && min != pos)
min = pos;
break;
}
}
- return VARRAY_INT (line_locators_lines, min);
+ return VEC_index (int, line_locators_lines, min);
}
/* Return line number of the statement that produced this insn. */
const char *
locator_file (int loc)
{
- int max = VARRAY_ACTIVE_SIZE (file_locators_locs);
+ int max = VEC_length (int, file_locators_locs);
int min = 0;
if (!max || !loc)
while (1)
{
int pos = (min + max) / 2;
- int tmp = VARRAY_INT (file_locators_locs, pos);
+ int tmp = VEC_index (int, file_locators_locs, pos);
if (tmp <= loc && min != pos)
min = pos;
{
tree this_block;
+ /* Avoid putting scope notes between jump table and its label. */
+ if (JUMP_P (insn)
+ && (GET_CODE (PATTERN (insn)) == ADDR_VEC
+ || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC))
+ continue;
+
this_block = insn_scope (insn);
/* For sequences compute scope resulting from merging all scopes
of instructions nested inside. */
for (bb = ENTRY_BLOCK_PTR->next_bb, index = 0;
bb != 0;
- bb = bb->rbi->next, index++)
+ bb = bb->aux, index++)
{
- if (bb->rbi->header)
+ if (bb->il.rtl->header)
{
if (insn)
- NEXT_INSN (insn) = bb->rbi->header;
+ NEXT_INSN (insn) = bb->il.rtl->header;
else
- set_first_insn (bb->rbi->header);
- PREV_INSN (bb->rbi->header) = insn;
- insn = bb->rbi->header;
+ set_first_insn (bb->il.rtl->header);
+ PREV_INSN (bb->il.rtl->header) = insn;
+ insn = bb->il.rtl->header;
while (NEXT_INSN (insn))
insn = NEXT_INSN (insn);
}
set_first_insn (BB_HEAD (bb));
PREV_INSN (BB_HEAD (bb)) = insn;
insn = BB_END (bb);
- if (bb->rbi->footer)
+ if (bb->il.rtl->footer)
{
- NEXT_INSN (insn) = bb->rbi->footer;
- PREV_INSN (bb->rbi->footer) = insn;
+ NEXT_INSN (insn) = bb->il.rtl->footer;
+ PREV_INSN (bb->il.rtl->footer) = insn;
while (NEXT_INSN (insn))
insn = NEXT_INSN (insn);
}
/* Now add jumps and labels as needed to match the blocks new
outgoing edges. */
- for (bb = ENTRY_BLOCK_PTR->next_bb; bb ; bb = bb->rbi->next)
+ for (bb = ENTRY_BLOCK_PTR->next_bb; bb ; bb = bb->aux)
{
edge e_fall, e_taken, e;
rtx bb_end_insn;
basic_block nb;
- basic_block old_bb;
edge_iterator ei;
if (EDGE_COUNT (bb->succs) == 0)
if (any_condjump_p (bb_end_insn))
{
/* If the old fallthru is still next, nothing to do. */
- if (bb->rbi->next == e_fall->dest
+ if (bb->aux == e_fall->dest
|| e_fall->dest == EXIT_BLOCK_PTR)
continue;
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 (bb->rbi->next != e_taken->dest)
+ else if (bb->aux != e_taken->dest)
{
rtx note = find_reg_note (bb_end_insn, REG_BR_PROB, 0);
}
else
{
-#ifndef CASE_DROPS_THROUGH
/* Otherwise we have some return, switch or computed
jump. In the 99% case, there should not have been a
fallthru edge. */
gcc_assert (returnjump_p (bb_end_insn) || !e_fall);
continue;
-#else
- if (returnjump_p (bb_end_insn) || !e_fall)
- continue;
- /* Except for VAX. Since we didn't have predication for the
- tablejump, the fallthru block should not have moved. */
- if (bb->rbi->next == e_fall->dest)
- continue;
- bb_end_insn = skip_insns_after_block (bb);
-#endif
}
}
else
continue;
/* If the fallthru block is still next, nothing to do. */
- if (bb->rbi->next == e_fall->dest)
+ if (bb->aux == e_fall->dest)
continue;
/* A fallthru to exit block. */
nb = force_nonfallthru (e_fall);
if (nb)
{
- initialize_bb_rbi (nb);
- nb->rbi->visited = 1;
- nb->rbi->next = bb->rbi->next;
- bb->rbi->next = nb;
+ nb->il.rtl->visited = 1;
+ nb->aux = bb->aux;
+ bb->aux = 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, EDGE_PRED (bb, 0)->src);
+ BB_COPY_PARTITION (e_fall->src, single_pred (bb));
if (flag_reorder_blocks_and_partition
- && targetm.have_named_sections)
- {
- if (BB_PARTITION (EDGE_PRED (bb, 0)->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))
- && (EDGE_SUCC (bb, 0)->flags & EDGE_CROSSING))
- REG_NOTES (BB_END (bb)) = gen_rtx_EXPR_LIST
- (REG_CROSSING_JUMP, NULL_RTX, REG_NOTES (BB_END (bb)));
- }
+ && targetm.have_named_sections
+ && JUMP_P (BB_END (bb))
+ && !any_condjump_p (BB_END (bb))
+ && (EDGE_SUCC (bb, 0)->flags & EDGE_CROSSING))
+ REG_NOTES (BB_END (bb)) = gen_rtx_EXPR_LIST
+ (REG_CROSSING_JUMP, NULL_RTX, REG_NOTES (BB_END (bb)));
}
}
fprintf (dump_file, "Reordered sequence:\n");
for (bb = ENTRY_BLOCK_PTR->next_bb, index = 0;
bb;
- bb = bb->rbi->next, index++)
+ bb = bb->aux, index++)
{
fprintf (dump_file, " %i ", index);
- if (bb->rbi->original)
+ if (get_bb_original (bb))
fprintf (dump_file, "duplicate of %i ",
- bb->rbi->original->index);
+ get_bb_original (bb)->index);
else if (forwarder_block_p (bb)
&& !LABEL_P (BB_HEAD (bb)))
fprintf (dump_file, "compensation ");
bb = ENTRY_BLOCK_PTR->next_bb;
index = 0;
- for (; bb; prev_bb = bb, bb = bb->rbi->next, index ++)
+ for (; bb; prev_bb = bb, bb = bb->aux, index ++)
{
bb->index = index;
BASIC_BLOCK (index) = bb;
- update_unlikely_executed_notes (bb);
-
bb->prev_bb = prev_bb;
prev_bb->next_bb = bb;
}
}
}
\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.
1. Check that next/prev pointers are consistent in both the forward and
reverse direction.
if (e->flags & EDGE_FALLTHRU)
bb = e->src;
- if (bb && bb->rbi->next)
+ if (bb && bb->aux)
{
basic_block c = ENTRY_BLOCK_PTR->next_bb;
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;
+ bb->aux = c->aux;
+ c->aux = bb;
+ bb->il.rtl->footer = c->il.rtl->footer;
+ c->il.rtl->footer = NULL;
}
- while (c->rbi->next != bb)
- c = c->rbi->next;
+ while (c->aux != bb)
+ c = c->aux;
- c->rbi->next = bb->rbi->next;
- while (c->rbi->next)
- c = c->rbi->next;
+ c->aux = bb->aux;
+ while (c->aux)
+ c = c->aux;
- c->rbi->next = bb;
- bb->rbi->next = NULL;
+ c->aux = bb;
+ bb->aux = NULL;
}
}
\f
break;
case NOTE_INSN_REPEATED_LINE_NUMBER:
- case NOTE_INSN_UNLIKELY_EXECUTED_CODE:
+ case NOTE_INSN_SWITCH_TEXT_SECTIONS:
emit_note_copy (insn);
break;
EXIT_BLOCK_PTR->prev_bb);
BB_COPY_PARTITION (new_bb, bb);
- if (bb->rbi->header)
+ if (bb->il.rtl->header)
{
- insn = bb->rbi->header;
+ insn = bb->il.rtl->header;
while (NEXT_INSN (insn))
insn = NEXT_INSN (insn);
- insn = duplicate_insn_chain (bb->rbi->header, insn);
+ insn = duplicate_insn_chain (bb->il.rtl->header, insn);
if (insn)
- new_bb->rbi->header = unlink_insn_chain (insn, get_last_insn ());
+ new_bb->il.rtl->header = unlink_insn_chain (insn, get_last_insn ());
}
- if (bb->rbi->footer)
+ if (bb->il.rtl->footer)
{
- insn = bb->rbi->footer;
+ insn = bb->il.rtl->footer;
while (NEXT_INSN (insn))
insn = NEXT_INSN (insn);
- insn = duplicate_insn_chain (bb->rbi->footer, insn);
+ insn = duplicate_insn_chain (bb->il.rtl->footer, insn);
if (insn)
- new_bb->rbi->footer = unlink_insn_chain (insn, get_last_insn ());
+ new_bb->il.rtl->footer = unlink_insn_chain (insn, get_last_insn ());
}
- if (bb->global_live_at_start)
+ if (bb->il.rtl->global_live_at_start)
{
- new_bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (®_obstack);
- new_bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (®_obstack);
- COPY_REG_SET (new_bb->global_live_at_start, bb->global_live_at_start);
- COPY_REG_SET (new_bb->global_live_at_end, bb->global_live_at_end);
+ new_bb->il.rtl->global_live_at_start = ALLOC_REG_SET (®_obstack);
+ new_bb->il.rtl->global_live_at_end = ALLOC_REG_SET (®_obstack);
+ COPY_REG_SET (new_bb->il.rtl->global_live_at_start,
+ bb->il.rtl->global_live_at_start);
+ COPY_REG_SET (new_bb->il.rtl->global_live_at_end,
+ bb->il.rtl->global_live_at_end);
}
return new_bb;
void
cfg_layout_initialize (unsigned int flags)
{
- basic_block bb;
-
- /* Our algorithm depends on fact that there are no dead jumptables
- around the code. */
- alloc_rbi_pool ();
-
- FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
- initialize_bb_rbi (bb);
+ initialize_original_copy_tables ();
cfg_layout_rtl_register_cfg_hooks ();
free (superblocks);
}
-/* Finalize the changes: reorder insn list according to the sequence, enter
- compensation code, rebuild scope forest. */
+/* Finalize the changes: reorder insn list according to the sequence specified
+ by aux pointers, enter compensation code, rebuild scope forest. */
void
cfg_layout_finalize (void)
#ifdef ENABLE_CHECKING
verify_insn_chain ();
#endif
-
- free_rbi_pool ();
FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
- bb->rbi = NULL;
+ {
+ bb->il.rtl->header = bb->il.rtl->footer = NULL;
+ bb->aux = NULL;
+ bb->il.rtl->visited = 0;
+ }
break_superblocks ();
#ifdef ENABLE_CHECKING
verify_flow_info ();
#endif
+
+ free_original_copy_tables ();
}
/* Checks whether all N blocks in BBS array can be copied. */
int ret = true;
for (i = 0; i < n; i++)
- bbs[i]->rbi->duplicated = 1;
+ bbs[i]->flags |= BB_DUPLICATED;
for (i = 0; i < n; i++)
{
edge_iterator ei;
FOR_EACH_EDGE (e, ei, bbs[i]->succs)
if ((e->flags & EDGE_ABNORMAL)
- && e->dest->rbi->duplicated)
+ && (e->dest->flags & BB_DUPLICATED))
{
ret = false;
goto end;
end:
for (i = 0; i < n; i++)
- bbs[i]->rbi->duplicated = 0;
+ bbs[i]->flags &= ~BB_DUPLICATED;
return ret;
}
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. */
+ also in the same order.
+
+ Newly created basic blocks are put after the basic block AFTER in the
+ instruction stream, and the order of the blocks in BBS array is preserved. */
void
copy_bbs (basic_block *bbs, unsigned n, basic_block *new_bbs,
- edge *edges, unsigned n_edges, edge *new_edges,
- struct loop *base)
+ edge *edges, unsigned num_edges, edge *new_edges,
+ struct loop *base, basic_block after)
{
unsigned i, j;
basic_block bb, new_bb, dom_bb;
{
/* Duplicate. */
bb = bbs[i];
- new_bb = new_bbs[i] = duplicate_block (bb, NULL);
- bb->rbi->duplicated = 1;
+ new_bb = new_bbs[i] = duplicate_block (bb, NULL, after);
+ after = new_bb;
+ bb->flags |= BB_DUPLICATED;
/* Add to loop. */
add_bb_to_loop (new_bb, bb->loop_father->copy);
/* Possibly set header. */
new_bb = new_bbs[i];
dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
- if (dom_bb->rbi->duplicated)
+ if (dom_bb->flags & BB_DUPLICATED)
{
- dom_bb = dom_bb->rbi->copy;
+ dom_bb = get_bb_copy (dom_bb);
set_immediate_dominator (CDI_DOMINATORS, new_bb, dom_bb);
}
}
/* Redirect edges. */
- for (j = 0; j < n_edges; j++)
+ for (j = 0; j < num_edges; j++)
new_edges[j] = NULL;
for (i = 0; i < n; i++)
{
FOR_EACH_EDGE (e, ei, new_bb->succs)
{
- for (j = 0; j < n_edges; j++)
+ for (j = 0; j < num_edges; j++)
if (edges[j] && edges[j]->src == bb && edges[j]->dest == e->dest)
new_edges[j] = e;
- if (!e->dest->rbi->duplicated)
+ if (!(e->dest->flags & BB_DUPLICATED))
continue;
- redirect_edge_and_branch_force (e, e->dest->rbi->copy);
+ redirect_edge_and_branch_force (e, get_bb_copy (e->dest));
}
}
/* Clear information about duplicates. */
for (i = 0; i < n; i++)
- bbs[i]->rbi->duplicated = 0;
+ bbs[i]->flags &= ~BB_DUPLICATED;
}
#include "gt-cfglayout.h"
OSDN Git Service
