===================================================================
@@ -144,8 +144,7 @@ static void scan_rtx_address (rtx, rtx *
enum scan_actions, enum machine_mode);
static void scan_rtx (rtx, rtx *, enum reg_class, enum scan_actions,
enum op_type);
-static struct du_head *build_def_use (basic_block);
-static void dump_def_use_chain (struct du_head *);
+static bool build_def_use (basic_block);
typedef struct du_head *du_head_p;
DEF_VEC_P (du_head_p);
@@ -157,9 +156,8 @@ static unsigned current_id;
/* A mapping of unique id numbers to chains. */
static VEC(du_head_p, heap) *id_to_chain;
-/* List of currently open chains, and closed chains that can be renamed. */
+/* List of currently open chains. */
static struct du_head *open_chains;
-static struct du_head *closed_chains;
/* Bitmap of open chains. The bits set always match the list found in
open_chains. */
@@ -175,9 +173,11 @@ static HARD_REG_SET live_hard_regs;
/* Dump all def/use chains in CHAINS to DUMP_FILE. */
static void
-dump_def_use_chain (struct du_head *head)
+dump_def_use_chain (void)
{
- while (head)
+ du_head_p head;
+ int i;
+ FOR_EACH_VEC_ELT (du_head_p, id_to_chain, i, head)
{
struct du_chain *this_du = head->first;
fprintf (dump_file, "Register %s (%d):",
@@ -269,13 +269,16 @@ check_new_reg_p (int reg ATTRIBUTE_UNUSE
return true;
}
-/* Process the closed chains starting with ALL_CHAINS and rename
- registers if possible. */
+/* Process the chains found in id_to_chain and rename registers if
+ possible. CANNOT_RENAME_CHAINS is a bitmap containing chains
+ that cannot be renamed for some reason. */
+
static void
-rename_chains (du_head_p all_chains)
+rename_chains (bitmap cannot_rename_chains)
{
HARD_REG_SET unavailable;
-
+ du_head_p this_head;
+ int i;
CLEAR_HARD_REG_SET (unavailable);
/* Don't clobber traceback for noreturn functions. */
@@ -287,11 +290,10 @@ rename_chains (du_head_p all_chains)
#endif
}
- while (all_chains)
+ FOR_EACH_VEC_ELT (du_head_p, id_to_chain, i, this_head)
{
int new_reg, best_new_reg, best_nregs;
int n_uses;
- struct du_head *this_head = all_chains;
struct du_chain *tmp;
HARD_REG_SET this_unavailable;
int reg = this_head->regno;
@@ -300,9 +302,8 @@ rename_chains (du_head_p all_chains)
enum reg_class preferred_class;
bool has_preferred_class;
- all_chains = this_head->next_chain;
-
- if (this_head->cannot_rename)
+ if (this_head->cannot_rename
+ || bitmap_bit_p (cannot_rename_chains, this_head->id))
continue;
best_new_reg = reg;
@@ -418,13 +419,100 @@ rename_chains (du_head_p all_chains)
}
}
+/* A structure recording information about each basic block. It is saved
+ and restored around basic block boundaries. */
+struct bb_rename_info
+{
+ /* The basic block corresponding to this structure. */
+ basic_block bb;
+ /* Copies of the global information. */
+ bitmap_head open_chains_set;
+ HARD_REG_SET live_in_chains;
+ HARD_REG_SET live_hard_regs;
+};
+
+/* Initialize a rename_info structure P for basic block BB, which starts a new
+ scan. */
+static void
+init_rename_info (struct bb_rename_info *p, basic_block bb)
+{
+ df_ref *def_rec;
+
+ p->bb = bb;
+ bitmap_initialize (&p->open_chains_set, &bitmap_default_obstack);
+
+ CLEAR_HARD_REG_SET (p->live_in_chains);
+ REG_SET_TO_HARD_REG_SET (p->live_hard_regs, df_get_live_in (bb));
+ for (def_rec = df_get_artificial_defs (bb->index); *def_rec; def_rec++)
+ {
+ df_ref def = *def_rec;
+ if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
+ SET_HARD_REG_BIT (p->live_hard_regs, DF_REF_REGNO (def));
+ }
+
+}
+
+/* Save current rename info data into structure P, which will be restored later
+ to continue scanning at basic block BB. OPEN_SET is the set of open chains
+ at the start of BB. */
+static void
+save_rename_info (struct bb_rename_info *p, basic_block bb, bitmap open_set)
+{
+ HARD_REG_SET live;
+
+ p->bb = bb;
+
+ bitmap_initialize (&p->open_chains_set, &bitmap_default_obstack);
+ bitmap_copy (&p->open_chains_set, open_set);
+
+ REG_SET_TO_HARD_REG_SET (live, df_get_live_in (bb));
+
+ COPY_HARD_REG_SET (p->live_in_chains, live_in_chains);
+ COPY_HARD_REG_SET (p->live_hard_regs, live_hard_regs);
+ AND_HARD_REG_SET (p->live_in_chains, live);
+ AND_HARD_REG_SET (p->live_hard_regs, live);
+}
+
+/* Restore global state from the rename info structure P. Recompute the
+ open_chains list and the live_in_chains set from the bitmap stored in P.
+ This function frees the bitmap data associated with P. */
+static void
+restore_rename_info (struct bb_rename_info *p)
+{
+ bitmap_iterator bi;
+ unsigned int i;
+
+ open_chains = NULL;
+ bitmap_copy (&open_chains_set, &p->open_chains_set);
+ bitmap_clear (&p->open_chains_set);
+
+ CLEAR_HARD_REG_SET (live_in_chains);
+ EXECUTE_IF_SET_IN_BITMAP (&open_chains_set, 0, i, bi)
+ {
+ struct du_head *this_chain = VEC_index (du_head_p, id_to_chain,
+ i);
+
+ this_chain->next_chain = open_chains;
+ open_chains = this_chain;
+ if (dump_file)
+ fprintf (dump_file, " reopening %s (chain %d)\n",
+ reg_names[this_chain->regno], this_chain->id);
+ }
+ COPY_HARD_REG_SET (live_hard_regs, p->live_hard_regs);
+ COPY_HARD_REG_SET (live_in_chains, p->live_in_chains);
+}
+
/* Perform register renaming on the current function. */
static unsigned int
regrename_optimize (void)
{
+ struct bb_rename_info *rename_info;
+ int ri_index;
basic_block bb;
char *first_obj;
+ bitmap_head processed_bbs;
+ bitmap_initialize (&processed_bbs, &bitmap_default_obstack);
df_set_flags (DF_LR_RUN_DCE);
df_note_add_problem ();
@@ -436,21 +524,99 @@ regrename_optimize (void)
gcc_obstack_init (&rename_obstack);
first_obj = XOBNEWVAR (&rename_obstack, char, 0);
+ rename_info = XNEWVEC (struct bb_rename_info, n_basic_blocks);
FOR_EACH_BB (bb)
{
- struct du_head *all_chains = 0;
+ VEC (int, heap) *bb_queue;
+ edge e;
+ edge_iterator ei;
+ bitmap_head chains_open_at_end;
+ bitmap_head tmp_chains;
+ bool fail = false;
+ if (!bitmap_set_bit (&processed_bbs, bb->index))
+ continue;
+
+ ri_index = 0;
+ current_id = 0;
id_to_chain = VEC_alloc (du_head_p, heap, 0);
+ bb_queue = VEC_alloc (int, heap, 0);
+
+ VEC_safe_push (int, heap, bb_queue, ri_index);
+ init_rename_info (rename_info + ri_index, bb);
+ ri_index++;
if (dump_file)
fprintf (dump_file, "\nBasic block %d:\n", bb->index);
- all_chains = build_def_use (bb);
+ bitmap_initialize (&chains_open_at_end, &bitmap_default_obstack);
+ bitmap_initialize (&tmp_chains, &bitmap_default_obstack);
+
+ while (!VEC_empty (int, bb_queue))
+ {
+ int this_index = VEC_pop (int, bb_queue);
+ struct bb_rename_info *this_info = rename_info + this_index;
+ basic_block bb1 = this_info->bb;
+
+ if (dump_file)
+ fprintf (dump_file, "processing block %d:\n", bb1->index);
+ bitmap_set_bit (&processed_bbs, bb1->index);
+
+ restore_rename_info (this_info);
+
+ if (!build_def_use (this_info->bb))
+ {
+ fail = true;
+ break;
+ }
+
+ FOR_EACH_EDGE (e, ei, bb1->succs)
+ {
+ struct du_head *chain;
+ regset live = df_get_live_in (e->dest);
+ if (dump_file)
+ fprintf (dump_file, "successor block %d: live regs", e->dest->index);
+ for (chain = open_chains; chain; chain = chain->next_chain)
+ {
+ int nregs = chain->nregs;
+ while (nregs-- > 0)
+ {
+ if (REGNO_REG_SET_P (live, chain->regno + nregs))
+ {
+ bitmap_set_bit (&tmp_chains, chain->id);
+ if (dump_file)
+ fprintf (dump_file, " %s (%d)",
+ reg_names[chain->regno], chain->id);
+ break;
+ }
+ }
+ }
+ if (dump_file)
+ fprintf (dump_file, "\n");
+ if ((e->flags & (EDGE_ABNORMAL | EDGE_EH)) != 0
+ || EDGE_COUNT (e->dest->preds) > 1
+ || e->dest == EXIT_BLOCK_PTR
+ || bitmap_bit_p (&processed_bbs, e->dest->index))
+ {
+ if (dump_file)
+ fprintf (dump_file, " no further processing\n");
+ bitmap_ior_into (&chains_open_at_end, &tmp_chains);
+ }
+ else
+ {
+ VEC_safe_push (int, heap, bb_queue, ri_index);
+ save_rename_info (rename_info + ri_index, e->dest, &tmp_chains);
+ ri_index++;
+ }
+ bitmap_clear (&tmp_chains);
+ }
+ }
if (dump_file)
- dump_def_use_chain (all_chains);
+ dump_def_use_chain ();
- rename_chains (all_chains);
+ if (!fail)
+ rename_chains (&chains_open_at_end);
free_chain_data ();
obstack_free (&rename_obstack, first_obj);
@@ -775,8 +941,6 @@ scan_rtx_reg (rtx insn, rtx *loc, enum r
{
unsigned nregs;
- head->next_chain = closed_chains;
- closed_chains = head;
bitmap_clear_bit (&open_chains_set, head->id);
nregs = head->nregs;
@@ -1155,28 +1319,14 @@ record_out_operands (rtx insn, bool earl
/* Build def/use chain. */
-static struct du_head *
+static bool
build_def_use (basic_block bb)
{
rtx insn;
- df_ref *def_rec;
unsigned HOST_WIDE_INT untracked_operands;
- open_chains = closed_chains = NULL;
-
fail_current_block = false;
- current_id = 0;
- bitmap_initialize (&open_chains_set, &bitmap_default_obstack);
- CLEAR_HARD_REG_SET (live_in_chains);
- REG_SET_TO_HARD_REG_SET (live_hard_regs, df_get_live_in (bb));
- for (def_rec = df_get_artificial_defs (bb->index); *def_rec; def_rec++)
- {
- df_ref def = *def_rec;
- if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
- SET_HARD_REG_BIT (live_hard_regs, DF_REF_REGNO (def));
- }
-
for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
{
if (NONDEBUG_INSN_P (insn))
@@ -1418,11 +1568,9 @@ build_def_use (basic_block bb)
bitmap_clear (&open_chains_set);
if (fail_current_block)
- return NULL;
+ return false;
- /* Since we close every chain when we find a REG_DEAD note, anything that
- is still open lives past the basic block, so it can't be renamed. */
- return closed_chains;
+ return true;
}
static bool