/* Register renaming for the GNU compiler.
- Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
- Free Software Foundation, Inc.
+ Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009,
+ 2010 Free Software Foundation, Inc.
This file is part of GCC.
#include "system.h"
#include "coretypes.h"
#include "tm.h"
-#include "rtl.h"
+#include "rtl-error.h"
#include "tm_p.h"
#include "insn-config.h"
#include "regs.h"
#include "function.h"
#include "recog.h"
#include "flags.h"
-#include "toplev.h"
#include "obstack.h"
#include "timevar.h"
#include "tree-pass.h"
#include "df.h"
+#include "target.h"
+
+/* This file implements the RTL register renaming pass of the compiler. It is
+ a semi-local pass whose goal is to maximize the usage of the register file
+ of the processor by substituting registers for others in the solution given
+ by the register allocator. The algorithm is as follows:
+
+ 1. Local def/use chains are built: within each basic block, chains are
+ opened and closed; if a chain isn't closed at the end of the block,
+ it is dropped.
+
+ 2. For each chain, the set of possible renaming registers is computed.
+ This takes into account the renaming of previously processed chains.
+ Optionally, a preferred class is computed for the renaming register.
+
+ 3. The best renaming register is computed for the chain in the above set,
+ using a round-robin allocation. If a preferred class exists, then the
+ round-robin allocation is done within the class first, if possible.
+ The round-robin allocation of renaming registers itself is global.
+
+ 4. If a renaming register has been found, it is substituted in the chain.
+
+ Targets can parameterize the pass by specifying a preferred class for the
+ renaming register for a given (super)class of registers to be renamed. */
+
+#if HOST_BITS_PER_WIDE_INT <= MAX_RECOG_OPERANDS
+#error "Use a different bitmap implementation for untracked_operands."
+#endif
/* We keep linked lists of DU_HEAD structures, each of which describes
a chain of occurrences of a reg. */
}
}
+/* Check if NEW_REG can be the candidate register to rename for
+ REG in THIS_HEAD chain. THIS_UNAVAILABLE is a set of unavailable hard
+ registers. */
+
+static bool
+check_new_reg_p (int reg ATTRIBUTE_UNUSED, int new_reg,
+ struct du_head *this_head, HARD_REG_SET this_unavailable)
+{
+ enum machine_mode mode = GET_MODE (*this_head->first->loc);
+ int nregs = hard_regno_nregs[new_reg][mode];
+ int i;
+ struct du_chain *tmp;
+
+ for (i = nregs - 1; i >= 0; --i)
+ if (TEST_HARD_REG_BIT (this_unavailable, new_reg + i)
+ || fixed_regs[new_reg + i]
+ || global_regs[new_reg + i]
+ /* Can't use regs which aren't saved by the prologue. */
+ || (! df_regs_ever_live_p (new_reg + i)
+ && ! call_used_regs[new_reg + i])
+#ifdef LEAF_REGISTERS
+ /* We can't use a non-leaf register if we're in a
+ leaf function. */
+ || (current_function_is_leaf
+ && !LEAF_REGISTERS[new_reg + i])
+#endif
+#ifdef HARD_REGNO_RENAME_OK
+ || ! HARD_REGNO_RENAME_OK (reg + i, new_reg + i)
+#endif
+ )
+ return false;
+
+ /* See whether it accepts all modes that occur in
+ definition and uses. */
+ for (tmp = this_head->first; tmp; tmp = tmp->next_use)
+ if ((! HARD_REGNO_MODE_OK (new_reg, GET_MODE (*tmp->loc))
+ && ! DEBUG_INSN_P (tmp->insn))
+ || (this_head->need_caller_save_reg
+ && ! (HARD_REGNO_CALL_PART_CLOBBERED
+ (reg, GET_MODE (*tmp->loc)))
+ && (HARD_REGNO_CALL_PART_CLOBBERED
+ (new_reg, GET_MODE (*tmp->loc)))))
+ return false;
+
+ return true;
+}
+
/* Perform register renaming on the current function. */
static unsigned int
if (frame_pointer_needed)
{
add_to_hard_reg_set (&unavailable, Pmode, FRAME_POINTER_REGNUM);
-#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
+#if !HARD_FRAME_POINTER_IS_FRAME_POINTER
add_to_hard_reg_set (&unavailable, Pmode, HARD_FRAME_POINTER_REGNUM);
#endif
}
struct du_chain *tmp;
HARD_REG_SET this_unavailable;
int reg = this_head->regno;
- int i;
+ int pass;
+ enum reg_class super_class = NO_REGS;
+ enum reg_class preferred_class;
+ bool has_preferred_class;
all_chains = this_head->next_chain;
#endif
if (fixed_regs[reg] || global_regs[reg]
-#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
+#if !HARD_FRAME_POINTER_IS_FRAME_POINTER
|| (frame_pointer_needed && reg == HARD_FRAME_POINTER_REGNUM)
#else
|| (frame_pointer_needed && reg == FRAME_POINTER_REGNUM)
COPY_HARD_REG_SET (this_unavailable, unavailable);
- /* Count number of uses, and narrow the set of registers we can
- use for renaming. */
+ /* 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))
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);
- /* Now potential_regs is a reasonable approximation, let's
- have a closer look at each register still in there. */
- for (new_reg = 0; new_reg < FIRST_PSEUDO_REGISTER; new_reg++)
+ /* 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++)
{
- enum machine_mode mode = GET_MODE (*this_head->first->loc);
- int nregs = hard_regno_nregs[new_reg][mode];
-
- for (i = nregs - 1; i >= 0; --i)
- if (TEST_HARD_REG_BIT (this_unavailable, new_reg + i)
- || fixed_regs[new_reg + i]
- || global_regs[new_reg + i]
- /* Can't use regs which aren't saved by the prologue. */
- || (! df_regs_ever_live_p (new_reg + i)
- && ! call_used_regs[new_reg + i])
-#ifdef LEAF_REGISTERS
- /* We can't use a non-leaf register if we're in a
- leaf function. */
- || (current_function_is_leaf
- && !LEAF_REGISTERS[new_reg + i])
-#endif
-#ifdef HARD_REGNO_RENAME_OK
- || ! HARD_REGNO_RENAME_OK (reg + i, new_reg + i)
-#endif
- )
- break;
- if (i >= 0)
- continue;
-
- /* See whether it accepts all modes that occur in
- definition and uses. */
- for (tmp = this_head->first; tmp; tmp = tmp->next_use)
- if ((! HARD_REGNO_MODE_OK (new_reg, GET_MODE (*tmp->loc))
- && ! DEBUG_INSN_P (tmp->insn))
- || (this_head->need_caller_save_reg
- && ! (HARD_REGNO_CALL_PART_CLOBBERED
- (reg, GET_MODE (*tmp->loc)))
- && (HARD_REGNO_CALL_PART_CLOBBERED
- (new_reg, GET_MODE (*tmp->loc)))))
- break;
- if (! tmp)
+ for (new_reg = 0; new_reg < FIRST_PSEUDO_REGISTER; new_reg++)
{
- if (tick[best_new_reg] > tick[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 = nregs;
+ best_nregs = hard_regno_nregs[new_reg][mode];
}
}
+ if (pass == 0 && best_new_reg != reg)
+ break;
}
if (dump_file)
static struct du_head *open_chains;
static struct du_head *closed_chains;
-/* Conflict bitmaps, tracking the live chains and the live hard registers.
- The bits set in open_chains_set always match the list found in
+/* Bitmap of open chains. The bits set always match the list found in
open_chains. */
static bitmap_head open_chains_set;
-static HARD_REG_SET live_hard_regs;
-/* Record the registers being tracked in open_chains. The intersection
- between this and live_hard_regs is empty. */
+/* Record the registers being tracked in open_chains. */
static HARD_REG_SET live_in_chains;
-/* Return true if OP is a reg that is being tracked already in some form.
- May set fail_current_block if it sees an unhandled case of overlap. */
+/* 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. */
static bool
-verify_reg_tracked (rtx op)
+verify_reg_in_set (rtx op, HARD_REG_SET *pset)
{
unsigned regno, nregs;
bool all_live, all_dead;
nregs = hard_regno_nregs[regno][GET_MODE (op)];
all_live = all_dead = true;
while (nregs-- > 0)
- if (TEST_HARD_REG_BIT (live_hard_regs, regno + nregs))
+ if (TEST_HARD_REG_BIT (*pset, regno + nregs))
all_dead = false;
else
all_live = false;
fail_current_block = true;
return false;
}
+ return all_live;
+}
- if (all_live)
- return true;
-
- nregs = hard_regno_nregs[regno][GET_MODE (op)];
- all_live = all_dead = true;
- while (nregs-- > 0)
- if (TEST_HARD_REG_BIT (live_in_chains, regno + nregs))
- all_dead = false;
- else
- all_live = false;
- if (!all_dead && !all_live)
- {
- fail_current_block = true;
- return false;
- }
+/* Return true if OP is a reg that is being tracked already in some form.
+ May set fail_current_block if it sees an unhandled case of overlap. */
- return all_live;
+static bool
+verify_reg_tracked (rtx op)
+{
+ return (verify_reg_in_set (op, &live_hard_regs)
+ || verify_reg_in_set (op, &live_in_chains));
}
/* Called through note_stores. DATA points to a rtx_code, either SET or
add_to_hard_reg_set (&chain->hard_conflicts, GET_MODE (x), REGNO (x));
}
+/* Create a new chain for THIS_NREGS registers starting at THIS_REGNO,
+ and record its occurrence in *LOC, which is being written to in INSN.
+ This access requires a register of class CL. */
+
+static void
+create_new_chain (unsigned this_regno, unsigned this_nregs, rtx *loc,
+ rtx insn, enum reg_class cl)
+{
+ struct du_head *head = XOBNEW (&rename_obstack, struct du_head);
+ struct du_chain *this_du;
+ int nregs;
+
+ head->next_chain = open_chains;
+ open_chains = head;
+ head->regno = this_regno;
+ 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++;
+
+ bitmap_initialize (&head->conflicts, &bitmap_default_obstack);
+ bitmap_copy (&head->conflicts, &open_chains_set);
+ mark_conflict (open_chains, head->id);
+
+ /* Since we're tracking this as a chain now, remove it from the
+ list of conflicting live hard registers and track it in
+ live_in_chains instead. */
+ nregs = head->nregs;
+ while (nregs-- > 0)
+ {
+ SET_HARD_REG_BIT (live_in_chains, head->regno + nregs);
+ CLEAR_HARD_REG_BIT (live_hard_regs, head->regno + nregs);
+ }
+
+ COPY_HARD_REG_SET (head->hard_conflicts, live_hard_regs);
+ bitmap_set_bit (&open_chains_set, head->id);
+
+ open_chains = head;
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "Creating chain %s (%d)",
+ reg_names[head->regno], head->id);
+ if (insn != NULL_RTX)
+ fprintf (dump_file, " at insn %d", INSN_UID (insn));
+ fprintf (dump_file, "\n");
+ }
+
+ if (insn == NULL_RTX)
+ {
+ head->first = head->last = NULL;
+ return;
+ }
+
+ this_du = XOBNEW (&rename_obstack, struct du_chain);
+ head->first = head->last = this_du;
+
+ this_du->next_use = 0;
+ this_du->loc = loc;
+ this_du->insn = insn;
+ this_du->cl = cl;
+}
+
static void
scan_rtx_reg (rtx insn, rtx *loc, enum reg_class cl, enum scan_actions action,
enum op_type type)
if (action == mark_write)
{
if (type == OP_OUT)
- {
- struct du_head *head = XOBNEW (&rename_obstack, struct du_head);
- struct du_chain *this_du = XOBNEW (&rename_obstack, struct du_chain);
- int nregs;
-
- head->next_chain = open_chains;
- open_chains = head;
- head->first = head->last = this_du;
- head->regno = this_regno;
- 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++;
-
- bitmap_initialize (&head->conflicts, &bitmap_default_obstack);
- bitmap_copy (&head->conflicts, &open_chains_set);
- mark_conflict (open_chains, head->id);
-
- /* Since we're tracking this as a chain now, remove it from the
- list of conflicting live hard registers and track it in
- live_in_chains instead. */
- nregs = head->nregs;
- while (nregs-- > 0)
- {
- SET_HARD_REG_BIT (live_in_chains, head->regno + nregs);
- CLEAR_HARD_REG_BIT (live_hard_regs, head->regno + nregs);
- }
-
- COPY_HARD_REG_SET (head->hard_conflicts, live_hard_regs);
- bitmap_set_bit (&open_chains_set, head->id);
-
- open_chains = head;
-
- this_du->next_use = 0;
- this_du->loc = loc;
- this_du->insn = insn;
- this_du->cl = cl;
-
- if (dump_file)
- fprintf (dump_file,
- "Creating chain %s (%d) at insn %d (%s)\n",
- reg_names[head->regno], head->id, INSN_UID (insn),
- scan_actions_name[(int) action]);
- }
+ create_new_chain (this_regno, this_nregs, loc, insn, cl);
return;
}
&& head->nregs == this_nregs);
int superset = (this_regno <= head->regno
&& this_regno + this_nregs >= head->regno + head->nregs);
+ int subset = (this_regno >= head->regno
+ && this_regno + this_nregs <= head->regno + head->nregs);
if (head->terminated
|| head->regno + head->nregs <= this_regno
reg_names[head->regno], head->id, INSN_UID (insn),
scan_actions_name[(int) action]);
head->cannot_rename = 1;
+ if (superset)
+ {
+ unsigned nregs = this_nregs;
+ head->regno = this_regno;
+ head->nregs = this_nregs;
+ while (nregs-- > 0)
+ SET_HARD_REG_BIT (live_in_chains, head->regno + nregs);
+ if (dump_file)
+ fprintf (dump_file,
+ "Widening register in chain %s (%d) at insn %d\n",
+ reg_names[head->regno], head->id, INSN_UID (insn));
+ }
+ else if (!subset)
+ {
+ fail_current_block = true;
+ if (dump_file)
+ fprintf (dump_file,
+ "Failing basic block due to unhandled overlap\n");
+ }
}
else
{
this_du->loc = loc;
this_du->insn = insn;
this_du->cl = cl;
- head->last->next_use = this_du;
+ if (head->first == NULL)
+ head->first = this_du;
+ else
+ head->last->next_use = this_du;
head->last = this_du;
-
}
/* Avoid adding the same location in a DEBUG_INSN multiple times,
which could happen with non-exact overlap. */
return;
case STRICT_LOW_PART:
- scan_rtx (insn, &XEXP (x, 0), cl, action, OP_INOUT);
+ scan_rtx (insn, &XEXP (x, 0), cl, action,
+ verify_reg_tracked (XEXP (x, 0)) ? OP_INOUT : OP_OUT);
return;
case ZERO_EXTRACT:
case SIGN_EXTRACT:
scan_rtx (insn, &XEXP (x, 0), cl, action,
- type == OP_IN ? OP_IN : OP_INOUT);
+ (type == OP_IN ? OP_IN :
+ verify_reg_tracked (XEXP (x, 0)) ? OP_INOUT : OP_OUT));
scan_rtx (insn, &XEXP (x, 1), cl, action, OP_IN);
scan_rtx (insn, &XEXP (x, 2), cl, action, OP_IN);
return;
/* Hide operands of the current insn (of which there are N_OPS) by
substituting cc0 for them.
Previous values are stored in the OLD_OPERANDS and OLD_DUPS.
+ For every bit set in DO_NOT_HIDE, we leave the operand alone.
If INOUT_AND_EC_ONLY is set, we only do this for OP_INOUT type operands
and earlyclobbers. */
static void
hide_operands (int n_ops, rtx *old_operands, rtx *old_dups,
- bool inout_and_ec_only)
+ unsigned HOST_WIDE_INT do_not_hide, bool inout_and_ec_only)
{
int i;
int alt = which_alternative;
reachable by proper operands. */
if (recog_data.constraints[i][0] == '\0')
continue;
+ if (do_not_hide & (1 << i))
+ continue;
if (!inout_and_ec_only || recog_data.operand_type[i] == OP_INOUT
|| recog_op_alt[i][alt].earlyclobber)
*recog_data.operand_loc[i] = cc0_rtx;
{
int opn = recog_data.dup_num[i];
old_dups[i] = *recog_data.dup_loc[i];
+ if (do_not_hide & (1 << opn))
+ continue;
if (!inout_and_ec_only || recog_data.operand_type[opn] == OP_INOUT
|| recog_op_alt[opn][alt].earlyclobber)
*recog_data.dup_loc[i] = cc0_rtx;
{
rtx insn;
df_ref *def_rec;
+ unsigned HOST_WIDE_INT untracked_operands;
open_chains = closed_chains = NULL;
preprocess_constraints ();
alt = which_alternative;
n_ops = recog_data.n_operands;
+ untracked_operands = 0;
/* Simplify the code below by rewriting things to reflect
matching constraints. Also promote OP_OUT to OP_INOUT in
predicated = GET_CODE (PATTERN (insn)) == COND_EXEC;
for (i = 0; i < n_ops; ++i)
{
+ rtx op = recog_data.operand[i];
int matches = recog_op_alt[i][alt].matches;
if (matches >= 0)
recog_op_alt[i][alt].cl = recog_op_alt[matches][alt].cl;
if (matches >= 0 || recog_op_alt[i][alt].matched >= 0
- || (predicated && recog_data.operand_type[i] == OP_OUT
- && verify_reg_tracked (recog_data.operand[i])))
+ || (predicated && recog_data.operand_type[i] == OP_OUT))
{
recog_data.operand_type[i] = OP_INOUT;
+ /* A special case to deal with instruction patterns that
+ have matching operands with different modes. If we're
+ not already tracking such a reg, we won't start here,
+ and we must instead make sure to make the operand visible
+ to the machinery that tracks hard registers. */
if (matches >= 0
&& (GET_MODE_SIZE (recog_data.operand_mode[i])
- != GET_MODE_SIZE (recog_data.operand_mode[matches])))
- fail_current_block = true;
+ != GET_MODE_SIZE (recog_data.operand_mode[matches]))
+ && !verify_reg_in_set (op, &live_in_chains))
+ {
+ untracked_operands |= 1 << i;
+ untracked_operands |= 1 << matches;
+ }
+ }
+ /* If there's an in-out operand with a register that is not
+ being tracked at all yet, open a chain. */
+ if (recog_data.operand_type[i] == OP_INOUT
+ && !(untracked_operands & (1 << i))
+ && REG_P (op)
+ && !verify_reg_tracked (op))
+ {
+ enum machine_mode mode = GET_MODE (op);
+ unsigned this_regno = REGNO (op);
+ unsigned this_nregs = hard_regno_nregs[this_regno][mode];
+ create_new_chain (this_regno, this_nregs, NULL, NULL_RTX,
+ NO_REGS);
}
}
/* Step 1a: Mark hard registers that are clobbered in this insn,
outside an operand, as live. */
- hide_operands (n_ops, old_operands, old_dups, false);
+ hide_operands (n_ops, old_operands, old_dups, untracked_operands,
+ false);
note_stores (PATTERN (insn), note_sets_clobbers, &clobber_code);
restore_operands (insn, n_ops, old_operands, old_dups);
We do this by munging all operands into CC0, and closing
everything remaining. */
- hide_operands (n_ops, old_operands, old_dups, false);
+ hide_operands (n_ops, old_operands, old_dups, untracked_operands,
+ false);
scan_rtx (insn, &PATTERN (insn), NO_REGS, mark_all_read, OP_IN);
restore_operands (insn, n_ops, old_operands, old_dups);
/* Don't scan match_operand here, since we've no reg class
information to pass down. Any operands that we could
substitute in will be represented elsewhere. */
- if (recog_data.constraints[opn][0] == '\0')
+ if (recog_data.constraints[opn][0] == '\0'
+ || untracked_operands & (1 << opn))
continue;
if (recog_op_alt[opn][alt].is_address)
the previous insn at the latest, as such operands cannot
possibly overlap with any input operands. */
- hide_operands (n_ops, old_operands, old_dups, true);
+ hide_operands (n_ops, old_operands, old_dups, untracked_operands,
+ true);
scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_write, OP_IN);
restore_operands (insn, n_ops, old_operands, old_dups);
/* Step 6a: Mark hard registers that are set in this insn,
outside an operand, as live. */
- hide_operands (n_ops, old_operands, old_dups, false);
+ hide_operands (n_ops, old_operands, old_dups, untracked_operands,
+ false);
note_stores (PATTERN (insn), note_sets_clobbers, &set_code);
restore_operands (insn, n_ops, old_operands, old_dups);