/* Perform branch target register load optimizations.
- Copyright (C) 2001, 2002, 2003 Free Software Foundation, Inc.
+ Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
This file is part of GCC.
#include "flags.h"
#include "insn-attr.h"
#include "function.h"
+#include "except.h"
#include "tm_p.h"
/* Target register optimizations - these are performed after reload. */
btr_user uses;
/* If this def has a reaching use which is not a simple use
in a branch instruction, then has_ambiguous_use will be true,
- and we will not attempt to migrate this definition. */
+ and we will not attempt to migrate this definition. */
char has_ambiguous_use;
/* live_range is an approximation to the true live range for this
def/use web, because it records the set of blocks that contain
migrating branch target load instructions. */
static struct obstack migrate_btrl_obstack;
-/* Basic block dominator information used when migrating PT instructions */
-static dominance_info dom;
-
/* Array indexed by basic block number, giving the set of registers
live in that block. */
static HARD_REG_SET *btrs_live;
+/* Array indexed by basic block number, giving the set of registers live at
+ the end of that block, including any uses by a final jump insn, if any. */
+static HARD_REG_SET *btrs_live_at_end;
+
/* Set of all target registers that we are willing to allocate. */
static HARD_REG_SET all_btrs;
-/* Return an estimate of the frequency of execution of block bb.
- If we have a profiling count available, we could use it here. */
+/* Return an estimate of the frequency of execution of block bb. */
static int
basic_block_freq (basic_block bb)
{
if (!this_group)
{
- this_group = (btr_def_group)
- obstack_alloc (&migrate_btrl_obstack,
- sizeof (struct btr_def_group_s));
+ this_group = obstack_alloc (&migrate_btrl_obstack,
+ sizeof (struct btr_def_group_s));
this_group->src = def_src;
this_group->members = NULL;
this_group->next = *all_btr_def_groups;
unsigned int dest_reg, int other_btr_uses_before_def,
btr_def_group *all_btr_def_groups)
{
- btr_def this = (btr_def)
- obstack_alloc (&migrate_btrl_obstack, sizeof (struct btr_def_s));
+ btr_def this
+ = obstack_alloc (&migrate_btrl_obstack, sizeof (struct btr_def_s));
this->bb = bb;
this->luid = insn_luid;
this->insn = insn;
usep = NULL;
}
use = usep ? *usep : NULL_RTX;
- user = (btr_user)
- obstack_alloc (&migrate_btrl_obstack, sizeof (struct btr_user_s));
+ user = obstack_alloc (&migrate_btrl_obstack, sizeof (struct btr_user_s));
user->bb = bb;
user->luid = insn_luid;
user->insn = insn;
/* Called via note_stores or directly to register stores into /
clobbers of a branch target register DEST that are not recognized as
straightforward definitions. DATA points to information about the
- current basic block that needs updating. */
+ current basic block that needs updating. */
static void
note_btr_set (rtx dest, rtx set ATTRIBUTE_UNUSED, void *data)
{
btr_def defs_this_bb = NULL;
rtx insn;
rtx last;
+ int can_throw = 0;
info.users_this_bb = NULL;
info.bb_gen = bb_gen[i];
&& REGNO_REG_SET_P (bb->global_live_at_start, reg))
SET_HARD_REG_BIT (info.btrs_live_in_block, reg);
- for (insn = bb->head, last = NEXT_INSN (bb->end);
+ for (insn = BB_HEAD (bb), last = NEXT_INSN (BB_END (bb));
insn != last;
insn = NEXT_INSN (insn), insn_luid++)
{
call_used_reg_set);
clobbered = &call_saved;
}
-
+
for (regno = first_btr; regno <= last_btr; regno++)
if (TEST_HARD_REG_BIT (*clobbered, regno))
note_btr_set (regno_reg_rtx[regno], NULL_RTX, &info);
COPY_HARD_REG_SET (btrs_live[i], info.btrs_live_in_block);
COPY_HARD_REG_SET (btrs_written[i], info.btrs_written_in_block);
+
+ REG_SET_TO_HARD_REG_SET (btrs_live_at_end[i], bb->global_live_at_end);
+ /* If this block ends in a jump insn, add any uses or even clobbers
+ of branch target registers that it might have. */
+ for (insn = BB_END (bb); insn != BB_HEAD (bb) && ! INSN_P (insn); )
+ insn = PREV_INSN (insn);
+ /* ??? for the fall-through edge, it would make sense to insert the
+ btr set on the edge, but that would require to split the block
+ early on so that we can distinguish between dominance from the fall
+ through edge - which can use the call-clobbered registers - from
+ dominance by the throw edge. */
+ if (can_throw_internal (insn))
+ {
+ HARD_REG_SET tmp;
+
+ COPY_HARD_REG_SET (tmp, call_used_reg_set);
+ AND_HARD_REG_SET (tmp, all_btrs);
+ IOR_HARD_REG_SET (btrs_live_at_end[i], tmp);
+ can_throw = 1;
+ }
+ if (can_throw || GET_CODE (insn) == JUMP_INSN)
+ {
+ int regno;
+
+ for (regno = first_btr; regno <= last_btr; regno++)
+ if (refers_to_regno_p (regno, regno+1, insn, NULL))
+ SET_HARD_REG_BIT (btrs_live_at_end[i], regno);
+ }
+
if (rtl_dump_file)
dump_btrs_live(i);
}
For each block,
BB_IN = union over predecessors of BB_OUT(pred)
BB_OUT = (BB_IN - BB_KILL) + BB_GEN
- Iterate until the bb_out sets stop growing. */
+ Iterate until the bb_out sets stop growing. */
int i;
int changed;
sbitmap bb_in = sbitmap_alloc (max_uid);
rtx last;
sbitmap_union_of_preds (reaching_defs, bb_out, i);
- for (insn = bb->head, last = NEXT_INSN (bb->end);
+ for (insn = BB_HEAD (bb), last = NEXT_INSN (BB_END (bb));
insn != last;
insn = NEXT_INSN (insn))
{
if (user != NULL)
{
- /* Find all the reaching defs for this use */
+ /* Find all the reaching defs for this use. */
sbitmap reaching_defs_of_reg = sbitmap_alloc(max_uid);
int uid;
{
btr_def def = def_array[uid];
- /* We now know that def reaches user */
+ /* We now know that def reaches user. */
if (rtl_dump_file)
fprintf (rtl_dump_file,
sbitmap *btr_defset = sbitmap_vector_alloc (
(last_btr - first_btr) + 1, max_uid);
sbitmap *bb_gen = sbitmap_vector_alloc (n_basic_blocks, max_uid);
- HARD_REG_SET *btrs_written = (HARD_REG_SET *) xcalloc (
- n_basic_blocks, sizeof (HARD_REG_SET));
+ HARD_REG_SET *btrs_written = xcalloc (n_basic_blocks, sizeof (HARD_REG_SET));
sbitmap *bb_kill;
sbitmap *bb_out;
|| !block_at_edge_of_live_range_p (bb, def))
{
CLEAR_HARD_REG_BIT (btrs_live[bb], def->btr);
+ CLEAR_HARD_REG_BIT (btrs_live_at_end[bb], def->btr);
if (rtl_dump_file)
dump_btrs_live (bb);
}
(def->live_range, 0, bb,
{
SET_HARD_REG_BIT (btrs_live[bb], def->btr);
+ SET_HARD_REG_BIT (btrs_live_at_end[bb], def->btr);
if (rtl_dump_file)
dump_btrs_live (bb);
});
{
basic_block *worklist, *tos;
- tos = worklist =
- (basic_block *) xmalloc (sizeof (basic_block) * (n_basic_blocks + 1));
+ tos = worklist = xmalloc (sizeof (basic_block) * (n_basic_blocks + 1));
- if (dominated_by_p (dom, new_bb, head_bb))
+ if (dominated_by_p (CDI_DOMINATORS, new_bb, head_bb))
*tos++ = new_bb;
- else if (dominated_by_p (dom, head_bb, new_bb))
+ else if (dominated_by_p (CDI_DOMINATORS, head_bb, new_bb))
{
edge e;
int new_block = new_bb->index;
bitmap_set_bit (live_range, new_block);
- IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live[new_block]);
+ if (flag_btr_bb_exclusive)
+ IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live[new_block]);
+ else
+ {
+ IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live_at_end[new_block]);
+ IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live[head_bb->index]);
+ }
if (rtl_dump_file)
{
fprintf (rtl_dump_file,
- "Adding block %d to live range\n", new_block);
+ "Adding end of block %d and rest of %d to live range\n",
+ new_block, head_bb->index);
fprintf (rtl_dump_file,"Now live btrs are ");
dump_hard_reg_set (*btrs_live_in_range);
fprintf (rtl_dump_file, "\n");
def->live_range = BITMAP_XMALLOC ();
bitmap_set_bit (def->live_range, def->bb->index);
- COPY_HARD_REG_SET (*btrs_live_in_range, btrs_live[def->bb->index]);
+ if (flag_btr_bb_exclusive)
+ COPY_HARD_REG_SET (*btrs_live_in_range, btrs_live[def->bb->index]);
+ else
+ COPY_HARD_REG_SET (*btrs_live_in_range,
+ btrs_live_at_end[def->bb->index]);
for (user = def->uses; user != NULL; user = user->next)
augment_live_range (def->live_range, btrs_live_in_range,
of other PT instructions may have affected it.
*/
int bb;
+ int def_bb = def->bb->index;
CLEAR_HARD_REG_SET (*btrs_live_in_range);
- EXECUTE_IF_SET_IN_BITMAP
- (def->live_range, 0, bb,
- {
- IOR_HARD_REG_SET (*btrs_live_in_range,
- btrs_live[bb]);
- });
+ if (flag_btr_bb_exclusive)
+ EXECUTE_IF_SET_IN_BITMAP
+ (def->live_range, 0, bb,
+ {
+ IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live[bb]);
+ });
+ else
+ EXECUTE_IF_SET_IN_BITMAP
+ (def->live_range, 0, bb,
+ {
+ IOR_HARD_REG_SET (*btrs_live_in_range,
+ (def_bb == bb
+ ? btrs_live_at_end : btrs_live) [bb]);
+ });
}
if (!def->other_btr_uses_before_def &&
!def->other_btr_uses_after_use)
if (other_def != def
&& other_def->uses != NULL
&& ! other_def->has_ambiguous_use
- && dominated_by_p (dom, other_def->bb, def->bb))
+ && dominated_by_p (CDI_DOMINATORS, other_def->bb, def->bb))
{
/* def->bb dominates the other def, so def and other_def could
be combined. */
btr = choose_btr (combined_btrs_live);
if (btr != -1)
{
- /* We can combine them */
+ /* We can combine them. */
if (rtl_dump_file)
fprintf (rtl_dump_file,
"Combining def in insn %d with def in insn %d\n",
def->other_btr_uses_after_use = 1;
COPY_HARD_REG_SET (*btrs_live_in_range, combined_btrs_live);
- /* Delete the old target register initialization */
+ /* Delete the old target register initialization. */
delete_insn (other_def->insn);
}
Replace all uses of the old target register definition by
uses of the new definition. Delete the old definition. */
basic_block b = new_def_bb;
- rtx insp = b->head;
+ rtx insp = BB_HEAD (b);
rtx old_insn = def->insn;
rtx src;
rtx btr_rtx;
def->bb = new_def_bb;
def->luid = 0;
def->cost = basic_block_freq (new_def_bb);
- def->other_btr_uses_before_def = 0;
+ def->other_btr_uses_before_def
+ = TEST_HARD_REG_BIT (btrs_live[b->index], btr) ? 1 : 0;
bitmap_copy (def->live_range, live_range);
combine_btr_defs (def, btrs_live_in_range);
btr = def->btr;
its basic block. */
/* ?? some assertions to check that insp is sensible? */
+ if (def->other_btr_uses_before_def)
+ {
+ insp = BB_END (b);
+ for (insp = BB_END (b); ! INSN_P (insp); insp = PREV_INSN (insp))
+ if (insp == BB_HEAD (b))
+ abort ();
+ if (GET_CODE (insp) == JUMP_INSN || can_throw_internal (insp))
+ insp = PREV_INSN (insp);
+ }
+
set = single_set (old_insn);
src = SET_SRC (set);
btr_mode = GET_MODE (SET_DEST (set));
fprintf (rtl_dump_file, "New pt is insn %d, inserted after insn %d\n",
INSN_UID (def->insn), INSN_UID (insp));
- /* Delete the old target register initialization */
+ /* Delete the old target register initialization. */
delete_insn (old_insn);
/* Replace each use of the old target register by a use of the new target
static int
can_move_up (basic_block bb, rtx insn, int n_insns)
{
- while (insn != bb->head && n_insns > 0)
+ while (insn != BB_HEAD (bb) && n_insns > 0)
{
insn = PREV_INSN (insn);
/* ??? What if we have an anti-dependency that actually prevents the
MIN_COST is the lower bound on the cost of the DEF after migration.
If we migrate DEF so that its cost falls below MIN_COST,
then we do not attempt to migrate further. The idea is that
- we migrate defintions in a priority order based on their cost,
+ we migrate definitions in a priority order based on their cost,
when the cost of this definition falls below MIN_COST, then
there is another definition with cost == MIN_COST which now
has a higher priority than this definition.
INSN_UID (def->insn), def->cost, min_cost);
if (!def->group || def->has_ambiguous_use)
- /* These defs are not migratable */
+ /* These defs are not migratable. */
{
if (rtl_dump_file)
fprintf (rtl_dump_file, "it's not migratable\n");
def_basic_block_freq = basic_block_freq (def->bb);
- for (try = get_immediate_dominator (dom, def->bb);
+ for (try = get_immediate_dominator (CDI_DOMINATORS, def->bb);
!give_up && try && try != ENTRY_BLOCK_PTR && def->cost >= min_cost;
- try = get_immediate_dominator (dom, try))
+ try = get_immediate_dominator (CDI_DOMINATORS, try))
{
/* Try to move the instruction that sets the target register into
basic block TRY. */
"Basic block %d: count = " HOST_WIDEST_INT_PRINT_DEC
" loop-depth = %d idom = %d\n",
i, (HOST_WIDEST_INT) bb->count, bb->loop_depth,
- get_immediate_dominator (dom, bb)->index);
+ get_immediate_dominator (CDI_DOMINATORS, bb)->index);
}
}
first_btr = reg;
}
- btrs_live =
- (HARD_REG_SET *) xcalloc (n_basic_blocks, sizeof (HARD_REG_SET));
+ btrs_live = xcalloc (n_basic_blocks, sizeof (HARD_REG_SET));
+ btrs_live_at_end = xcalloc (n_basic_blocks, sizeof (HARD_REG_SET));
build_btr_def_use_webs (all_btr_defs);
}
free (btrs_live);
+ free (btrs_live_at_end);
obstack_free (&migrate_btrl_obstack, NULL);
fibheap_delete (all_btr_defs);
}
life_analysis (insns, NULL, 0);
/* Dominator info is also needed for migrate_btr_def. */
- dom = calculate_dominance_info (CDI_DOMINATORS);
+ calculate_dominance_info (CDI_DOMINATORS);
migrate_btr_defs (class,
((*targetm.branch_target_register_callee_saved)
(after_prologue_epilogue_gen)));
- free_dominance_info (dom);
+ free_dominance_info (CDI_DOMINATORS);
update_life_info (NULL, UPDATE_LIFE_GLOBAL_RM_NOTES,
PROP_DEATH_NOTES | PROP_REG_INFO);