* [1/2] Rename across ebbs
@ 2011-05-27 20:10 Bernd Schmidt
2011-05-27 20:20 ` [2/2] " Bernd Schmidt
2011-08-24 11:21 ` [1/2] " Richard Sandiford
0 siblings, 2 replies; 3+ messages in thread
From: Bernd Schmidt @ 2011-05-27 20:10 UTC (permalink / raw)
To: GCC Patches
[-- Attachment #1: Type: text/plain, Size: 1353 bytes --]
While working on a C6X scheduling patch, I found myself wondering - what
would be involved in making the register renamer operate on extended
basic blocks rather than simple bbs? Somewhat surprisingly, the answer
turns out to be "not much". After the last rewrite, all the conflict
tests are based on id numbers and bitmaps, not live ranges.
The following two patches add support for saving and restoring renamer
state at basic block boundaries. Below is the initial patch, which just
reorders the code a little without changing functionality. Besides
moving and splitting out functions, I've only removed one redundant
structure field and some #if 0'ed code.
Bootstrapped and regression tested (with both patches applied) on
i686-linux, with
@@ -5106,6 +5106,9 @@ static const struct default_options ix86
+#ifdef INSN_SCHEDULING
+ { OPT_LEVELS_2_PLUS, OPT_frename_registers, NULL, 1 },
+#endif
to ensure it gets tested. Also tested with a 4.5 c6x-elf toolchain,
which has -frename-registers enabled by default. With a few other
changes to make full use of it, I get up to 10% speedup on certain
testcases on c6x. It would be nice if someone could run benchmarks on
other targets where this could affect performance. I may or may not
manage an i686 SPEC run over the weekend; it's unlikely to be affected
much due to not using sched_ebb.
Bernd
[-- Attachment #2: rnreg-prelim.diff --]
[-- Type: text/plain, Size: 15866 bytes --]
* regrename.c (struct du_head): Remove member terminated.
(create_new_chain): Don't initialize it.
(scan_rtx_reg): Don't set or test it, test the open_chains_set
bitmap instead.
(tick, this_tick): New global variables, moved out of
regrename_optimize.
(current_id, open_chains, closed_chains, open_chains_set,
live_in_chains, live_hard_regs): Reorder declarations.
(dump_def_use_chain): Move function earlier in the file.
(rename_chains): New static function, broken out of
regrename_optimize.
(regrename_optimize): Use it. Remove #if 0'ed code.
Index: gcc/regrename.c
===================================================================
--- gcc/regrename.c.orig
+++ gcc/regrename.c
@@ -85,8 +85,6 @@ struct du_head
/* Conflicts with untracked hard registers. */
HARD_REG_SET hard_conflicts;
- /* Nonzero if the chain is finished; zero if it is still open. */
- unsigned int terminated:1;
/* Nonzero if the chain crosses a call. */
unsigned int need_caller_save_reg:1;
/* Nonzero if the register is used in a way that prevents renaming,
@@ -132,6 +130,11 @@ static const char * const scan_actions_n
"mark_access"
};
+/* TICK and THIS_TICK are used to record the last time we saw each
+ register. */
+static int tick[FIRST_PSEUDO_REGISTER];
+static int this_tick = 0;
+
static struct obstack rename_obstack;
static void do_replace (struct du_head *, int);
@@ -147,8 +150,49 @@ static void dump_def_use_chain (struct d
typedef struct du_head *du_head_p;
DEF_VEC_P (du_head_p);
DEF_VEC_ALLOC_P (du_head_p, heap);
+
+/* The id to be given to the next opened chain. */
+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. */
+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. */
+static bitmap_head open_chains_set;
+
+/* Record the registers being tracked in open_chains. */
+static HARD_REG_SET live_in_chains;
+
+/* Record the registers that are live but not tracked. The intersection
+ between this and live_in_chains is empty. */
+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)
+{
+ while (head)
+ {
+ struct du_chain *this_du = head->first;
+ fprintf (dump_file, "Register %s (%d):",
+ reg_names[head->regno], head->nregs);
+ while (this_du)
+ {
+ fprintf (dump_file, " %d [%s]", INSN_UID (this_du->insn),
+ reg_class_names[this_du->cl]);
+ this_du = this_du->next_use;
+ }
+ fprintf (dump_file, "\n");
+ head = head->next_chain;
+ }
+}
+
static void
free_chain_data (void)
{
@@ -225,13 +269,160 @@ check_new_reg_p (int reg ATTRIBUTE_UNUSE
return true;
}
+/* Process the closed chains starting with ALL_CHAINS and rename
+ registers if possible. */
+static void
+rename_chains (du_head_p all_chains)
+{
+ HARD_REG_SET unavailable;
+
+
+ CLEAR_HARD_REG_SET (unavailable);
+ /* Don't clobber traceback for noreturn functions. */
+ if (frame_pointer_needed)
+ {
+ add_to_hard_reg_set (&unavailable, Pmode, FRAME_POINTER_REGNUM);
+#if !HARD_FRAME_POINTER_IS_FRAME_POINTER
+ add_to_hard_reg_set (&unavailable, Pmode, HARD_FRAME_POINTER_REGNUM);
+#endif
+ }
+
+ while (all_chains)
+ {
+ 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;
+ int pass;
+ enum reg_class super_class = NO_REGS;
+ enum reg_class preferred_class;
+ bool has_preferred_class;
+
+ all_chains = this_head->next_chain;
+
+ if (this_head->cannot_rename)
+ continue;
+
+ best_new_reg = reg;
+ best_nregs = this_head->nregs;
+
+ if (fixed_regs[reg] || global_regs[reg]
+#if !HARD_FRAME_POINTER_IS_FRAME_POINTER
+ || (frame_pointer_needed && reg == HARD_FRAME_POINTER_REGNUM)
+#else
+ || (frame_pointer_needed && reg == FRAME_POINTER_REGNUM)
+#endif
+ )
+ continue;
+
+ COPY_HARD_REG_SET (this_unavailable, unavailable);
+
+ /* Iterate over elements in the chain in order to:
+ 1. Count number of uses, and narrow the set of registers we can
+ use for renaming.
+ 2. Compute the superunion of register classes in this chain. */
+ n_uses = 0;
+ super_class = NO_REGS;
+ for (tmp = this_head->first; tmp; tmp = tmp->next_use)
+ {
+ if (DEBUG_INSN_P (tmp->insn))
+ continue;
+ n_uses++;
+ IOR_COMPL_HARD_REG_SET (this_unavailable,
+ reg_class_contents[tmp->cl]);
+ super_class
+ = reg_class_superunion[(int) super_class][(int) tmp->cl];
+ }
+
+ if (n_uses < 2)
+ continue;
+
+ /* Further narrow the set of registers we can use for renaming.
+ If the chain needs a call-saved register, mark the call-used
+ registers as unavailable. */
+ if (this_head->need_caller_save_reg)
+ IOR_HARD_REG_SET (this_unavailable, call_used_reg_set);
+
+ /* And mark registers that overlap its lifetime as unavailable. */
+ merge_overlapping_regs (&this_unavailable, this_head);
+
+ /* Compute preferred rename class of super union of all the classes
+ in the chain. */
+ preferred_class
+ = (enum reg_class) targetm.preferred_rename_class (super_class);
+
+ /* If PREFERRED_CLASS is not NO_REGS, we iterate in the first pass
+ over registers that belong to PREFERRED_CLASS and try to find the
+ best register within the class. If that failed, we iterate in
+ the second pass over registers that don't belong to the class.
+ If PREFERRED_CLASS is NO_REGS, we iterate over all registers in
+ ascending order without any preference. */
+ has_preferred_class = (preferred_class != NO_REGS);
+ for (pass = (has_preferred_class ? 0 : 1); pass < 2; pass++)
+ {
+ for (new_reg = 0; new_reg < FIRST_PSEUDO_REGISTER; new_reg++)
+ {
+ if (has_preferred_class
+ && (pass == 0)
+ != TEST_HARD_REG_BIT
+ (reg_class_contents[preferred_class], new_reg))
+ continue;
+
+ /* In the first pass, we force the renaming of registers that
+ don't belong to PREFERRED_CLASS to registers that do, even
+ though the latters were used not very long ago. */
+ if (check_new_reg_p (reg, new_reg, this_head,
+ this_unavailable)
+ && ((pass == 0
+ && !TEST_HARD_REG_BIT
+ (reg_class_contents[preferred_class],
+ best_new_reg))
+ || tick[best_new_reg] > tick[new_reg]))
+ {
+ enum machine_mode mode
+ = GET_MODE (*this_head->first->loc);
+ best_new_reg = new_reg;
+ best_nregs = hard_regno_nregs[new_reg][mode];
+ }
+ }
+ if (pass == 0 && best_new_reg != reg)
+ break;
+ }
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "Register %s in insn %d",
+ reg_names[reg], INSN_UID (this_head->first->insn));
+ if (this_head->need_caller_save_reg)
+ fprintf (dump_file, " crosses a call");
+ }
+
+ if (best_new_reg == reg)
+ {
+ tick[reg] = ++this_tick;
+ if (dump_file)
+ fprintf (dump_file, "; no available better choice\n");
+ continue;
+ }
+
+ if (dump_file)
+ fprintf (dump_file, ", renamed as %s\n", reg_names[best_new_reg]);
+
+ do_replace (this_head, best_new_reg);
+ this_head->regno = best_new_reg;
+ this_head->nregs = best_nregs;
+ tick[best_new_reg] = ++this_tick;
+ df_set_regs_ever_live (best_new_reg, true);
+ }
+}
+
/* Perform register renaming on the current function. */
static unsigned int
regrename_optimize (void)
{
- int tick[FIRST_PSEUDO_REGISTER];
- int this_tick = 0;
basic_block bb;
char *first_obj;
@@ -248,16 +439,9 @@ regrename_optimize (void)
FOR_EACH_BB (bb)
{
struct du_head *all_chains = 0;
- HARD_REG_SET unavailable;
-#if 0
- HARD_REG_SET regs_seen;
- CLEAR_HARD_REG_SET (regs_seen);
-#endif
id_to_chain = VEC_alloc (du_head_p, heap, 0);
- CLEAR_HARD_REG_SET (unavailable);
-
if (dump_file)
fprintf (dump_file, "\nBasic block %d:\n", bb->index);
@@ -266,154 +450,7 @@ regrename_optimize (void)
if (dump_file)
dump_def_use_chain (all_chains);
- CLEAR_HARD_REG_SET (unavailable);
- /* Don't clobber traceback for noreturn functions. */
- if (frame_pointer_needed)
- {
- add_to_hard_reg_set (&unavailable, Pmode, FRAME_POINTER_REGNUM);
-#if !HARD_FRAME_POINTER_IS_FRAME_POINTER
- add_to_hard_reg_set (&unavailable, Pmode, HARD_FRAME_POINTER_REGNUM);
-#endif
- }
-
- while (all_chains)
- {
- 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;
- int pass;
- enum reg_class super_class = NO_REGS;
- enum reg_class preferred_class;
- bool has_preferred_class;
-
- all_chains = this_head->next_chain;
-
- if (this_head->cannot_rename)
- continue;
-
- best_new_reg = reg;
- best_nregs = this_head->nregs;
-
-#if 0 /* This just disables optimization opportunities. */
- /* Only rename once we've seen the reg more than once. */
- if (! TEST_HARD_REG_BIT (regs_seen, reg))
- {
- SET_HARD_REG_BIT (regs_seen, reg);
- continue;
- }
-#endif
-
- if (fixed_regs[reg] || global_regs[reg]
-#if !HARD_FRAME_POINTER_IS_FRAME_POINTER
- || (frame_pointer_needed && reg == HARD_FRAME_POINTER_REGNUM)
-#else
- || (frame_pointer_needed && reg == FRAME_POINTER_REGNUM)
-#endif
- )
- continue;
-
- COPY_HARD_REG_SET (this_unavailable, unavailable);
-
- /* Iterate over elements in the chain in order to:
- 1. Count number of uses, and narrow the set of registers we can
- use for renaming.
- 2. Compute the superunion of register classes in this chain. */
- n_uses = 0;
- super_class = NO_REGS;
- for (tmp = this_head->first; tmp; tmp = tmp->next_use)
- {
- if (DEBUG_INSN_P (tmp->insn))
- continue;
- n_uses++;
- IOR_COMPL_HARD_REG_SET (this_unavailable,
- reg_class_contents[tmp->cl]);
- super_class
- = reg_class_superunion[(int) super_class][(int) tmp->cl];
- }
-
- if (n_uses < 2)
- continue;
-
- /* Further narrow the set of registers we can use for renaming.
- If the chain needs a call-saved register, mark the call-used
- registers as unavailable. */
- if (this_head->need_caller_save_reg)
- IOR_HARD_REG_SET (this_unavailable, call_used_reg_set);
-
- /* And mark registers that overlap its lifetime as unavailable. */
- merge_overlapping_regs (&this_unavailable, this_head);
-
- /* Compute preferred rename class of super union of all the classes
- in the chain. */
- preferred_class
- = (enum reg_class) targetm.preferred_rename_class (super_class);
-
- /* If PREFERRED_CLASS is not NO_REGS, we iterate in the first pass
- over registers that belong to PREFERRED_CLASS and try to find the
- best register within the class. If that failed, we iterate in
- the second pass over registers that don't belong to the class.
- If PREFERRED_CLASS is NO_REGS, we iterate over all registers in
- ascending order without any preference. */
- has_preferred_class = (preferred_class != NO_REGS);
- for (pass = (has_preferred_class ? 0 : 1); pass < 2; pass++)
- {
- for (new_reg = 0; new_reg < FIRST_PSEUDO_REGISTER; new_reg++)
- {
- if (has_preferred_class
- && (pass == 0)
- != TEST_HARD_REG_BIT
- (reg_class_contents[preferred_class], new_reg))
- continue;
-
- /* In the first pass, we force the renaming of registers that
- don't belong to PREFERRED_CLASS to registers that do, even
- though the latters were used not very long ago. */
- if (check_new_reg_p (reg, new_reg, this_head,
- this_unavailable)
- && ((pass == 0
- && !TEST_HARD_REG_BIT
- (reg_class_contents[preferred_class],
- best_new_reg))
- || tick[best_new_reg] > tick[new_reg]))
- {
- enum machine_mode mode
- = GET_MODE (*this_head->first->loc);
- best_new_reg = new_reg;
- best_nregs = hard_regno_nregs[new_reg][mode];
- }
- }
- if (pass == 0 && best_new_reg != reg)
- break;
- }
-
- if (dump_file)
- {
- fprintf (dump_file, "Register %s in insn %d",
- reg_names[reg], INSN_UID (this_head->first->insn));
- if (this_head->need_caller_save_reg)
- fprintf (dump_file, " crosses a call");
- }
-
- if (best_new_reg == reg)
- {
- tick[reg] = ++this_tick;
- if (dump_file)
- fprintf (dump_file, "; no available better choice\n");
- continue;
- }
-
- if (dump_file)
- fprintf (dump_file, ", renamed as %s\n", reg_names[best_new_reg]);
-
- do_replace (this_head, best_new_reg);
- this_head->regno = best_new_reg;
- this_head->nregs = best_nregs;
- tick[best_new_reg] = ++this_tick;
- df_set_regs_ever_live (best_new_reg, true);
- }
+ rename_chains (all_chains);
free_chain_data ();
obstack_free (&rename_obstack, first_obj);
@@ -507,24 +544,6 @@ mark_conflict (struct du_head *chains, u
without renaming. */
static bool fail_current_block;
-/* The id to be given to the next opened chain. */
-static unsigned current_id;
-
-/* List of currently open chains, and closed chains that can be renamed. */
-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. */
-static bitmap_head open_chains_set;
-
-/* Record the registers being tracked in open_chains. */
-static HARD_REG_SET live_in_chains;
-
-/* Record the registers that are live but not tracked. The intersection
- between this and live_in_chains is empty. */
-static HARD_REG_SET live_hard_regs;
-
/* Return true if OP is a reg for which all bits are set in PSET, false
if all bits are clear.
In other cases, set fail_current_block and return false. */
@@ -603,7 +622,6 @@ create_new_chain (unsigned this_regno, u
head->nregs = this_nregs;
head->need_caller_save_reg = 0;
head->cannot_rename = 0;
- head->terminated = 0;
VEC_safe_push (du_head_p, heap, id_to_chain, head);
head->id = current_id++;
@@ -682,7 +700,7 @@ scan_rtx_reg (rtx insn, rtx *loc, enum r
int subset = (this_regno >= head->regno
&& this_regno + this_nregs <= head->regno + head->nregs);
- if (head->terminated
+ if (!bitmap_bit_p (&open_chains_set, head->id)
|| head->regno + head->nregs <= this_regno
|| this_regno + this_nregs <= head->regno)
{
@@ -757,7 +775,6 @@ scan_rtx_reg (rtx insn, rtx *loc, enum r
{
unsigned nregs;
- head->terminated = 1;
head->next_chain = closed_chains;
closed_chains = head;
bitmap_clear_bit (&open_chains_set, head->id);
@@ -1407,29 +1424,6 @@ build_def_use (basic_block bb)
is still open lives past the basic block, so it can't be renamed. */
return closed_chains;
}
-
-/* Dump all def/use chains in CHAINS to DUMP_FILE. They are
- printed in reverse order as that's how we build them. */
-
-static void
-dump_def_use_chain (struct du_head *head)
-{
- while (head)
- {
- struct du_chain *this_du = head->first;
- fprintf (dump_file, "Register %s (%d):",
- reg_names[head->regno], head->nregs);
- while (this_du)
- {
- fprintf (dump_file, " %d [%s]", INSN_UID (this_du->insn),
- reg_class_names[this_du->cl]);
- this_du = this_du->next_use;
- }
- fprintf (dump_file, "\n");
- head = head->next_chain;
- }
-}
-
\f
static bool
gate_handle_regrename (void)
^ permalink raw reply [flat|nested] 3+ messages in thread
* [2/2] Rename across ebbs
2011-05-27 20:10 [1/2] Rename across ebbs Bernd Schmidt
@ 2011-05-27 20:20 ` Bernd Schmidt
2011-08-24 11:21 ` [1/2] " Richard Sandiford
1 sibling, 0 replies; 3+ messages in thread
From: Bernd Schmidt @ 2011-05-27 20:20 UTC (permalink / raw)
To: GCC Patches
[-- Attachment #1: Type: text/plain, Size: 350 bytes --]
This patch contains the actual changes for renaming across extended
basic blocks (where ebb here is a tree where each basic block except the
root has exactly one predecessor).
All we really have to do is reconstruct some information when starting
to scan a different bb; the open_chains list can be rebuilt from the
open_chains_set bitmap.
Bernd
[-- Attachment #2: rnreg-ebb.diff --]
[-- Type: text/plain, Size: 11090 bytes --]
* regrename.c (build_def_use): Return bool, true if we produced
a valid set of chains. All callers and declaration changed.
Rely on the caller to initialize global state.
(closed_chains): Remove variable.
(dump_def_use_chain): Take no arg. All callers changed. Use
the id_to_chain vector as a source of things to print.
(rename_chains): Replace argument with a bitmap of chains that
cannot be renamed. All callers changed. Use the id_to_chain
vector to find candidate chains for renaming.
(struct bb_rename_info): New structure.
(init_rename_info, save_rename_info, restore_rename_info): New
static functions.
(regrename_optimize): Use them to process ebbs rather than single
basic blocks and to initialize global state for build_def_use.
(scan_rtx_reg): Don't update closed_chains.
Index: trunk/gcc/regrename.c
===================================================================
--- trunk.orig/gcc/regrename.c
+++ trunk/gcc/regrename.c
@@ -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;
}
\f
static bool
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [1/2] Rename across ebbs
2011-05-27 20:10 [1/2] Rename across ebbs Bernd Schmidt
2011-05-27 20:20 ` [2/2] " Bernd Schmidt
@ 2011-08-24 11:21 ` Richard Sandiford
1 sibling, 0 replies; 3+ messages in thread
From: Richard Sandiford @ 2011-08-24 11:21 UTC (permalink / raw)
To: Bernd Schmidt; +Cc: GCC Patches
Bernd Schmidt <bernds@codesourcery.com> writes:
> * regrename.c (struct du_head): Remove member terminated.
> (create_new_chain): Don't initialize it.
> (scan_rtx_reg): Don't set or test it, test the open_chains_set
> bitmap instead.
> (tick, this_tick): New global variables, moved out of
> regrename_optimize.
> (current_id, open_chains, closed_chains, open_chains_set,
> live_in_chains, live_hard_regs): Reorder declarations.
> (dump_def_use_chain): Move function earlier in the file.
> (rename_chains): New static function, broken out of
> regrename_optimize.
> (regrename_optimize): Use it. Remove #if 0'ed code.
The reindent operation seems to have introduced some weird formatting
(due in some cases to the existing code not really following the rules).
So:
> +/* Process the closed chains starting with ALL_CHAINS and rename
> + registers if possible. */
> +static void
> +rename_chains (du_head_p all_chains)
> +{
> + HARD_REG_SET unavailable;
> +
> +
excess whitespace here.
> + /* Iterate over elements in the chain in order to:
> + 1. Count number of uses, and narrow the set of registers we can
> + use for renaming.
> + 2. Compute the superunion of register classes in this chain. */
original formatting was better:
/* Iterate over elements in the chain in order to:
1. Count number of uses, and narrow the set of registers we can
use for renaming.
2. Compute the superunion of register classes in this chain. */
> + if (has_preferred_class
> + && (pass == 0)
> + != TEST_HARD_REG_BIT
> + (reg_class_contents[preferred_class], new_reg))
> + continue;
The last two lines of the condition aren't indented properly.
(I checked it wasn't just a diff artefact.)
> + && ((pass == 0
> + && !TEST_HARD_REG_BIT
> + (reg_class_contents[preferred_class],
> + best_new_reg))
> + || tick[best_new_reg] > tick[new_reg]))
Same thing with the TEST_HARD_REG_BIT argument here.
OK otherwise, thanks. I suppose removing the terminated field is a
(very) slight compile-time pessimisation in itself. We only set it
when we were modifying the chain anyway, so there should be no cache
pollution problems. And calling bitmap_bit_p is more expensive than
a bitfield test on a structure that we're already looking at.
The difference is nothing like enough to be a problem though, especially
if it makes the other patch easier. Just saying in case anyone thought
it wasn't being considered...
Richard
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2011-08-24 10:12 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2011-05-27 20:10 [1/2] Rename across ebbs Bernd Schmidt
2011-05-27 20:20 ` [2/2] " Bernd Schmidt
2011-08-24 11:21 ` [1/2] " Richard Sandiford
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).