/* 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-2018 Free Software Foundation, Inc.
This file is part of GCC.
#include "config.h"
#include "system.h"
#include "coretypes.h"
-#include "tm.h"
+#include "backend.h"
+#include "target.h"
#include "rtl.h"
+#include "df.h"
+#include "memmodel.h"
#include "tm_p.h"
#include "insn-config.h"
#include "regs.h"
-#include "addresses.h"
-#include "hard-reg-set.h"
-#include "basic-block.h"
-#include "reload.h"
-#include "output.h"
-#include "function.h"
+#include "emit-rtl.h"
#include "recog.h"
-#include "flags.h"
-#include "toplev.h"
-#include "obstack.h"
-#include "timevar.h"
+#include "addresses.h"
+#include "cfganal.h"
#include "tree-pass.h"
-#include "df.h"
+#include "regrename.h"
-/* We keep linked lists of DU_HEAD structures, each of which describes
- a chain of occurrences of a reg. */
-struct du_head
-{
- /* The next chain. */
- struct du_head *next_chain;
- /* The first and last elements of this chain. */
- struct du_chain *first, *last;
- /* Describes the register being tracked. */
- unsigned regno, nregs;
- /* Nonzero if the chain crosses a call. */
- unsigned int need_caller_save_reg:1;
- /* Nonzero if the chain is finished. */
- unsigned int terminated:1;
-};
+/* 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:
-/* This struct describes a single occurrence of a register. */
-struct du_chain
-{
- /* Links to the next occurrence of the register. */
- struct du_chain *next_use;
-
- /* The insn where the register appears. */
- rtx insn;
- /* The location inside the insn. */
- rtx *loc;
- /* The register class required by the insn at this location. */
- ENUM_BITFIELD(reg_class) cl : 16;
- /* Nonzero if the register is subject to earlyclobber. */
- unsigned int earlyclobber:1;
-};
+ 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. We pre-open chains if we have already examined a
+ predecessor block and found chains live at the end which match
+ live registers at the start of the new block.
+
+ 2. We try to combine the local chains across basic block boundaries by
+ comparing chains that were open at the start or end of a block to
+ those in successor/predecessor blocks.
+
+ 3. 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.
+
+ 4. 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.
+
+ 5. 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.
+
+ DEBUG_INSNs are treated specially, in particular registers occurring inside
+ them are treated as requiring ALL_REGS as a class. */
+
+#if HOST_BITS_PER_WIDE_INT <= MAX_RECOG_OPERANDS
+#error "Use a different bitmap implementation for untracked_operands."
+#endif
enum scan_actions
{
- terminate_all_read,
- terminate_overlapping_read,
terminate_write,
terminate_dead,
+ mark_all_read,
mark_read,
mark_write,
/* mark_access is for marking the destination regs in
static const char * const scan_actions_name[] =
{
- "terminate_all_read",
- "terminate_overlapping_read",
"terminate_write",
"terminate_dead",
+ "mark_all_read",
"mark_read",
"mark_write",
"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);
-static void scan_rtx_reg (rtx, rtx *, enum reg_class,
- enum scan_actions, enum op_type, int);
-static void scan_rtx_address (rtx, rtx *, enum reg_class,
- enum scan_actions, enum machine_mode);
-static void scan_rtx (rtx, rtx *, enum reg_class, enum scan_actions,
- enum op_type, int);
-static struct du_head *build_def_use (basic_block);
-static void dump_def_use_chain (struct du_head *);
-static void note_sets (rtx, const_rtx, void *);
-static void clear_dead_regs (HARD_REG_SET *, enum reg_note, rtx);
-static void merge_overlapping_regs (basic_block, HARD_REG_SET *,
- struct du_head *);
-
-/* Called through note_stores. Find sets of registers, and
- record them in *DATA (which is actually a HARD_REG_SET *). */
+/* If nonnull, the code calling into the register renamer requested
+ information about insn operands, and we store it here. */
+vec<insn_rr_info> insn_rr;
+
+static void scan_rtx (rtx_insn *, rtx *, enum reg_class, enum scan_actions,
+ enum op_type);
+static bool build_def_use (basic_block);
+
+/* 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> id_to_chain;
+
+/* List of currently open chains. */
+static struct du_head *open_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;
+
+/* Set while scanning RTL if INSN_RR is nonnull, i.e. if the current analysis
+ is for a caller that requires operand data. Used in
+ record_operand_use. */
+static operand_rr_info *cur_operand;
+
+/* Set while scanning RTL if a register dies. Used to tie chains. */
+static struct du_head *terminated_this_insn;
+
+/* Return the chain corresponding to id number ID. Take into account that
+ chains may have been merged. */
+du_head_p
+regrename_chain_from_id (unsigned int id)
+{
+ du_head_p first_chain = id_to_chain[id];
+ du_head_p chain = first_chain;
+ while (chain->id != id)
+ {
+ id = chain->id;
+ chain = id_to_chain[id];
+ }
+ first_chain->id = id;
+ return chain;
+}
+
+/* Dump all def/use chains, starting at id FROM. */
static void
-note_sets (rtx x, const_rtx set ATTRIBUTE_UNUSED, void *data)
+dump_def_use_chain (int from)
{
- HARD_REG_SET *pset = (HARD_REG_SET *) data;
+ du_head_p head;
+ int i;
+ FOR_EACH_VEC_ELT_FROM (id_to_chain, i, head, from)
+ {
+ struct du_chain *this_du = head->first;
- if (GET_CODE (x) == SUBREG)
- x = SUBREG_REG (x);
- if (!REG_P (x))
- return;
- /* There must not be pseudos at this point. */
- gcc_assert (HARD_REGISTER_P (x));
- add_to_hard_reg_set (pset, GET_MODE (x), REGNO (x));
+ 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;
+ }
}
-/* Clear all registers from *PSET for which a note of kind KIND can be found
- in the list NOTES. */
+static void
+free_chain_data (void)
+{
+ int i;
+ du_head_p ptr;
+ for (i = 0; id_to_chain.iterate (i, &ptr); i++)
+ bitmap_clear (&ptr->conflicts);
+
+ id_to_chain.release ();
+}
+
+/* Walk all chains starting with CHAINS and record that they conflict with
+ another chain whose id is ID. */
static void
-clear_dead_regs (HARD_REG_SET *pset, enum reg_note kind, rtx notes)
+mark_conflict (struct du_head *chains, unsigned id)
{
- rtx note;
- for (note = notes; note; note = XEXP (note, 1))
- if (REG_NOTE_KIND (note) == kind && REG_P (XEXP (note, 0)))
- {
- rtx reg = XEXP (note, 0);
- /* There must not be pseudos at this point. */
- gcc_assert (HARD_REGISTER_P (reg));
- remove_from_hard_reg_set (pset, GET_MODE (reg), REGNO (reg));
- }
+ while (chains)
+ {
+ bitmap_set_bit (&chains->conflicts, id);
+ chains = chains->next_chain;
+ }
}
-/* For a def-use chain HEAD in basic block B, find which registers overlap
- its lifetime and set the corresponding bits in *PSET. */
+/* Examine cur_operand, and if it is nonnull, record information about the
+ use THIS_DU which is part of the chain HEAD. */
static void
-merge_overlapping_regs (basic_block b, HARD_REG_SET *pset,
- struct du_head *head)
+record_operand_use (struct du_head *head, struct du_chain *this_du)
{
- struct du_chain *t;
- rtx insn;
- HARD_REG_SET live;
- df_ref *def_rec;
+ if (cur_operand == NULL || cur_operand->failed)
+ return;
+ if (head->cannot_rename)
+ {
+ cur_operand->failed = true;
+ return;
+ }
+ gcc_assert (cur_operand->n_chains < MAX_REGS_PER_ADDRESS);
+ cur_operand->heads[cur_operand->n_chains] = head;
+ cur_operand->chains[cur_operand->n_chains++] = this_du;
+}
- REG_SET_TO_HARD_REG_SET (live, df_get_live_in (b));
- for (def_rec = df_get_artificial_defs (b->index); *def_rec; def_rec++)
+/* 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 du_head_p
+create_new_chain (unsigned this_regno, unsigned this_nregs, rtx *loc,
+ rtx_insn *insn, enum reg_class cl)
+{
+ struct du_head *head = XOBNEW (&rename_obstack, struct du_head);
+ struct du_chain *this_du;
+ int nregs;
+
+ memset (head, 0, sizeof *head);
+ head->next_chain = open_chains;
+ head->regno = this_regno;
+ head->nregs = this_nregs;
+
+ id_to_chain.safe_push (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)
{
- df_ref def = *def_rec;
- if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
- SET_HARD_REG_BIT (live, DF_REF_REGNO (def));
+ SET_HARD_REG_BIT (live_in_chains, head->regno + nregs);
+ CLEAR_HARD_REG_BIT (live_hard_regs, head->regno + nregs);
}
- t = head->first;
- insn = BB_HEAD (b);
- while (t)
+ COPY_HARD_REG_SET (head->hard_conflicts, live_hard_regs);
+ bitmap_set_bit (&open_chains_set, head->id);
+
+ open_chains = head;
+
+ if (dump_file)
{
- /* Search forward until the next reference to the register to be
- renamed. */
- while (insn != t->insn)
- {
- if (INSN_P (insn))
- {
- clear_dead_regs (&live, REG_DEAD, REG_NOTES (insn));
- note_stores (PATTERN (insn), note_sets, (void *) &live);
- /* Only record currently live regs if we are inside the
- reg's live range. */
- if (t != head->first)
- IOR_HARD_REG_SET (*pset, live);
- clear_dead_regs (&live, REG_UNUSED, REG_NOTES (insn));
- }
- insn = NEXT_INSN (insn);
- }
+ 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 head;
+ }
+
+ this_du = XOBNEW (&rename_obstack, struct du_chain);
+ head->first = head->last = this_du;
- IOR_HARD_REG_SET (*pset, live);
+ this_du->next_use = 0;
+ this_du->loc = loc;
+ this_du->insn = insn;
+ this_du->cl = cl;
+ record_operand_use (head, this_du);
+ return head;
+}
- /* For the last reference, also merge in all registers set in the
- same insn.
- @@@ We only have take earlyclobbered sets into account. */
- if (! t->next_use)
- note_stores (PATTERN (insn), note_sets, (void *) pset);
+/* For a def-use chain HEAD, find which registers overlap its lifetime and
+ set the corresponding bits in *PSET. */
- t = t->next_use;
+static void
+merge_overlapping_regs (HARD_REG_SET *pset, struct du_head *head)
+{
+ bitmap_iterator bi;
+ unsigned i;
+ IOR_HARD_REG_SET (*pset, head->hard_conflicts);
+ EXECUTE_IF_SET_IN_BITMAP (&head->conflicts, 0, i, bi)
+ {
+ du_head_p other = regrename_chain_from_id (i);
+ unsigned j = other->nregs;
+ gcc_assert (other != head);
+ while (j-- > 0)
+ SET_HARD_REG_BIT (*pset, other->regno + j);
}
}
-/* Perform register renaming on the current function. */
+/* 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 unsigned int
-regrename_optimize (void)
+static bool
+check_new_reg_p (int reg ATTRIBUTE_UNUSED, int new_reg,
+ struct du_head *this_head, HARD_REG_SET this_unavailable)
{
- int tick[FIRST_PSEUDO_REGISTER];
- int this_tick = 0;
- basic_block bb;
- char *first_obj;
+ 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. */
+ || (crtl->is_leaf
+ && !LEAF_REGISTERS[new_reg + i])
+#endif
+ || ! HARD_REGNO_RENAME_OK (reg + i, new_reg + i))
+ 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 ((!targetm.hard_regno_mode_ok (new_reg, GET_MODE (*tmp->loc))
+ && ! DEBUG_INSN_P (tmp->insn))
+ || (this_head->need_caller_save_reg
+ && ! (targetm.hard_regno_call_part_clobbered
+ (reg, GET_MODE (*tmp->loc)))
+ && (targetm.hard_regno_call_part_clobbered
+ (new_reg, GET_MODE (*tmp->loc)))))
+ return false;
+
+ return true;
+}
- df_set_flags (DF_LR_RUN_DCE);
- df_note_add_problem ();
- df_analyze ();
- df_set_flags (DF_DEFER_INSN_RESCAN);
+/* For the chain THIS_HEAD, compute and return the best register to
+ rename to. SUPER_CLASS is the superunion of register classes in
+ the chain. UNAVAILABLE is a set of registers that cannot be used.
+ OLD_REG is the register currently used for the chain. BEST_RENAME
+ controls whether the register chosen must be better than the
+ current one or just respect the given constraint. */
+
+int
+find_rename_reg (du_head_p this_head, enum reg_class super_class,
+ HARD_REG_SET *unavailable, int old_reg, bool best_rename)
+{
+ bool has_preferred_class;
+ enum reg_class preferred_class;
+ int pass;
+ int best_new_reg = old_reg;
+
+ /* 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 (*unavailable, call_used_reg_set);
+
+ /* Mark registers that overlap this chain's lifetime as unavailable. */
+ merge_overlapping_regs (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);
+
+ /* Pick and check the register from the tied chain iff the tied chain
+ is not renamed. */
+ if (this_head->tied_chain && !this_head->tied_chain->renamed
+ && check_new_reg_p (old_reg, this_head->tied_chain->regno,
+ this_head, *unavailable))
+ return this_head->tied_chain->regno;
+
+ /* 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++)
+ {
+ int new_reg;
+ 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;
+
+ if (!check_new_reg_p (old_reg, new_reg, this_head, *unavailable))
+ continue;
+
+ if (!best_rename)
+ return new_reg;
+
+ /* 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 ((pass == 0
+ && !TEST_HARD_REG_BIT (reg_class_contents[preferred_class],
+ best_new_reg))
+ || tick[best_new_reg] > tick[new_reg])
+ best_new_reg = new_reg;
+ }
+ if (pass == 0 && best_new_reg != old_reg)
+ break;
+ }
+ return best_new_reg;
+}
+
+/* Iterate over elements in the chain HEAD in order to:
+ 1. Count number of uses, storing it in *PN_USES.
+ 2. Narrow the set of registers we can use for renaming, adding
+ unavailable registers to *PUNAVAILABLE, which must be
+ initialized by the caller.
+ 3. Compute the superunion of register classes in this chain
+ and return it. */
+reg_class
+regrename_find_superclass (du_head_p head, int *pn_uses,
+ HARD_REG_SET *punavailable)
+{
+ int n_uses = 0;
+ reg_class super_class = NO_REGS;
+ for (du_chain *tmp = head->first; tmp; tmp = tmp->next_use)
+ {
+ if (DEBUG_INSN_P (tmp->insn))
+ continue;
+ n_uses++;
+ IOR_COMPL_HARD_REG_SET (*punavailable,
+ reg_class_contents[tmp->cl]);
+ super_class
+ = reg_class_superunion[(int) super_class][(int) tmp->cl];
+ }
+ *pn_uses = n_uses;
+ return super_class;
+}
+
+/* Perform register renaming on the current function. */
+static void
+rename_chains (void)
+{
+ HARD_REG_SET unavailable;
+ du_head_p this_head;
+ int i;
memset (tick, 0, sizeof tick);
- gcc_obstack_init (&rename_obstack);
- first_obj = XOBNEWVAR (&rename_obstack, char, 0);
+ 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);
+ }
- FOR_EACH_BB (bb)
+ FOR_EACH_VEC_ELT (id_to_chain, i, this_head)
{
- struct du_head *all_chains = 0;
- HARD_REG_SET unavailable;
- HARD_REG_SET regs_seen;
+ int best_new_reg;
+ int n_uses;
+ HARD_REG_SET this_unavailable;
+ int reg = this_head->regno;
- CLEAR_HARD_REG_SET (unavailable);
+ if (this_head->cannot_rename)
+ continue;
- if (dump_file)
- fprintf (dump_file, "\nBasic block %d:\n", bb->index);
+ if (fixed_regs[reg] || global_regs[reg]
+ || (!HARD_FRAME_POINTER_IS_FRAME_POINTER && frame_pointer_needed
+ && reg == HARD_FRAME_POINTER_REGNUM)
+ || (HARD_FRAME_POINTER_IS_FRAME_POINTER && frame_pointer_needed
+ && reg == FRAME_POINTER_REGNUM))
+ continue;
+
+ COPY_HARD_REG_SET (this_unavailable, unavailable);
- all_chains = build_def_use (bb);
+ reg_class super_class = regrename_find_superclass (this_head, &n_uses,
+ &this_unavailable);
+ if (n_uses < 2)
+ continue;
+
+ best_new_reg = find_rename_reg (this_head, super_class,
+ &this_unavailable, reg, true);
if (dump_file)
- dump_def_use_chain (all_chains);
+ {
+ 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");
+ }
- CLEAR_HARD_REG_SET (unavailable);
- /* Don't clobber traceback for noreturn functions. */
- if (frame_pointer_needed)
+ if (best_new_reg == reg)
{
- add_to_hard_reg_set (&unavailable, Pmode, FRAME_POINTER_REGNUM);
-#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
- add_to_hard_reg_set (&unavailable, Pmode, HARD_FRAME_POINTER_REGNUM);
-#endif
+ tick[reg] = ++this_tick;
+ if (dump_file)
+ fprintf (dump_file, "; no available better choice\n");
+ continue;
}
- CLEAR_HARD_REG_SET (regs_seen);
- while (all_chains)
+ if (regrename_do_replace (this_head, best_new_reg))
{
- int new_reg, best_new_reg;
- 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 i;
+ if (dump_file)
+ fprintf (dump_file, ", renamed as %s\n", reg_names[best_new_reg]);
+ tick[best_new_reg] = ++this_tick;
+ df_set_regs_ever_live (best_new_reg, true);
+ }
+ else
+ {
+ if (dump_file)
+ fprintf (dump_file, ", renaming as %s failed\n",
+ reg_names[best_new_reg]);
+ tick[reg] = ++this_tick;
+ }
+ }
+}
- all_chains = this_head->next_chain;
+/* A structure to record information for each hard register at the start of
+ a basic block. */
+struct incoming_reg_info {
+ /* Holds the number of registers used in the chain that gave us information
+ about this register. Zero means no information known yet, while a
+ negative value is used for something that is part of, but not the first
+ register in a multi-register value. */
+ int nregs;
+ /* Set to true if we have accesses that conflict in the number of registers
+ used. */
+ bool unusable;
+};
- best_new_reg = reg;
+/* A structure recording information about each basic block. It is saved
+ and restored around basic block boundaries.
+ A pointer to such a structure is stored in each basic block's aux field
+ during regrename_analyze, except for blocks we know can't be optimized
+ (such as entry and exit blocks). */
+struct bb_rename_info
+{
+ /* The basic block corresponding to this structure. */
+ basic_block bb;
+ /* Copies of the global information. */
+ bitmap_head open_chains_set;
+ bitmap_head incoming_open_chains_set;
+ struct incoming_reg_info incoming[FIRST_PSEUDO_REGISTER];
+};
-#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
+/* 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)
+{
+ int i;
+ df_ref def;
+ HARD_REG_SET start_chains_set;
+
+ p->bb = bb;
+ bitmap_initialize (&p->open_chains_set, &bitmap_default_obstack);
+ bitmap_initialize (&p->incoming_open_chains_set, &bitmap_default_obstack);
+
+ open_chains = NULL;
+ bitmap_clear (&open_chains_set);
+
+ CLEAR_HARD_REG_SET (live_in_chains);
+ REG_SET_TO_HARD_REG_SET (live_hard_regs, df_get_live_in (bb));
+ FOR_EACH_ARTIFICIAL_DEF (def, bb->index)
+ if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
+ SET_HARD_REG_BIT (live_hard_regs, DF_REF_REGNO (def));
+
+ /* Open chains based on information from (at least one) predecessor
+ block. This gives us a chance later on to combine chains across
+ basic block boundaries. Inconsistencies (in access sizes) will
+ be caught normally and dealt with conservatively by disabling the
+ chain for renaming, and there is no risk of losing optimization
+ opportunities by opening chains either: if we did not open the
+ chains, we'd have to track the live register as a hard reg, and
+ we'd be unable to rename it in any case. */
+ CLEAR_HARD_REG_SET (start_chains_set);
+ for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+ {
+ struct incoming_reg_info *iri = p->incoming + i;
+ if (iri->nregs > 0 && !iri->unusable
+ && range_in_hard_reg_set_p (live_hard_regs, i, iri->nregs))
+ {
+ SET_HARD_REG_BIT (start_chains_set, i);
+ remove_range_from_hard_reg_set (&live_hard_regs, i, iri->nregs);
+ }
+ }
+ for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+ {
+ struct incoming_reg_info *iri = p->incoming + i;
+ if (TEST_HARD_REG_BIT (start_chains_set, i))
+ {
+ du_head_p chain;
+ if (dump_file)
+ fprintf (dump_file, "opening incoming chain\n");
+ chain = create_new_chain (i, iri->nregs, NULL, NULL, NO_REGS);
+ bitmap_set_bit (&p->incoming_open_chains_set, chain->id);
+ }
+ }
+}
- if (fixed_regs[reg] || global_regs[reg]
-#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
- || (frame_pointer_needed && reg == HARD_FRAME_POINTER_REGNUM)
-#else
- || (frame_pointer_needed && reg == FRAME_POINTER_REGNUM)
-#endif
- )
- continue;
+/* Record in RI that the block corresponding to it has an incoming
+ live value, described by CHAIN. */
+static void
+set_incoming_from_chain (struct bb_rename_info *ri, du_head_p chain)
+{
+ int i;
+ int incoming_nregs = ri->incoming[chain->regno].nregs;
+ int nregs;
- COPY_HARD_REG_SET (this_unavailable, unavailable);
+ /* If we've recorded the same information before, everything is fine. */
+ if (incoming_nregs == chain->nregs)
+ {
+ if (dump_file)
+ fprintf (dump_file, "reg %d/%d already recorded\n",
+ chain->regno, chain->nregs);
+ return;
+ }
- /* Count number of uses, and narrow the set of registers we can
- use for renaming. */
- n_uses = 0;
- for (tmp = this_head->first; tmp; tmp = tmp->next_use)
+ /* If we have no information for any of the involved registers, update
+ the incoming array. */
+ nregs = chain->nregs;
+ while (nregs-- > 0)
+ if (ri->incoming[chain->regno + nregs].nregs != 0
+ || ri->incoming[chain->regno + nregs].unusable)
+ break;
+ if (nregs < 0)
+ {
+ nregs = chain->nregs;
+ ri->incoming[chain->regno].nregs = nregs;
+ while (nregs-- > 1)
+ ri->incoming[chain->regno + nregs].nregs = -nregs;
+ if (dump_file)
+ fprintf (dump_file, "recorded reg %d/%d\n",
+ chain->regno, chain->nregs);
+ return;
+ }
+
+ /* There must be some kind of conflict. Prevent both the old and
+ new ranges from being used. */
+ if (incoming_nregs < 0)
+ ri->incoming[chain->regno + incoming_nregs].unusable = true;
+ for (i = 0; i < chain->nregs; i++)
+ ri->incoming[chain->regno + i].unusable = true;
+}
+
+/* Merge the two chains C1 and C2 so that all conflict information is
+ recorded and C1, and the id of C2 is changed to that of C1. */
+static void
+merge_chains (du_head_p c1, du_head_p c2)
+{
+ if (c1 == c2)
+ return;
+
+ if (c2->first != NULL)
+ {
+ if (c1->first == NULL)
+ c1->first = c2->first;
+ else
+ c1->last->next_use = c2->first;
+ c1->last = c2->last;
+ }
+
+ c2->first = c2->last = NULL;
+ c2->id = c1->id;
+
+ IOR_HARD_REG_SET (c1->hard_conflicts, c2->hard_conflicts);
+ bitmap_ior_into (&c1->conflicts, &c2->conflicts);
+
+ c1->need_caller_save_reg |= c2->need_caller_save_reg;
+ c1->cannot_rename |= c2->cannot_rename;
+}
+
+/* Analyze the current function and build chains for renaming. */
+
+void
+regrename_analyze (bitmap bb_mask)
+{
+ struct bb_rename_info *rename_info;
+ int i;
+ basic_block bb;
+ int n_bbs;
+ int *inverse_postorder;
+
+ inverse_postorder = XNEWVEC (int, last_basic_block_for_fn (cfun));
+ n_bbs = pre_and_rev_post_order_compute (NULL, inverse_postorder, false);
+
+ /* Gather some information about the blocks in this function. */
+ rename_info = XCNEWVEC (struct bb_rename_info, n_basic_blocks_for_fn (cfun));
+ i = 0;
+ FOR_EACH_BB_FN (bb, cfun)
+ {
+ struct bb_rename_info *ri = rename_info + i;
+ ri->bb = bb;
+ if (bb_mask != NULL && !bitmap_bit_p (bb_mask, bb->index))
+ bb->aux = NULL;
+ else
+ bb->aux = ri;
+ i++;
+ }
+
+ current_id = 0;
+ id_to_chain.create (0);
+ bitmap_initialize (&open_chains_set, &bitmap_default_obstack);
+
+ /* The order in which we visit blocks ensures that whenever
+ possible, we only process a block after at least one of its
+ predecessors, which provides a "seeding" effect to make the logic
+ in set_incoming_from_chain and init_rename_info useful. */
+
+ for (i = 0; i < n_bbs; i++)
+ {
+ basic_block bb1 = BASIC_BLOCK_FOR_FN (cfun, inverse_postorder[i]);
+ struct bb_rename_info *this_info;
+ bool success;
+ edge e;
+ edge_iterator ei;
+ int old_length = id_to_chain.length ();
+
+ this_info = (struct bb_rename_info *) bb1->aux;
+ if (this_info == NULL)
+ continue;
+
+ if (dump_file)
+ fprintf (dump_file, "\nprocessing block %d:\n", bb1->index);
+
+ init_rename_info (this_info, bb1);
+
+ success = build_def_use (bb1);
+ if (!success)
+ {
+ if (dump_file)
+ fprintf (dump_file, "failed\n");
+ bb1->aux = NULL;
+ id_to_chain.truncate (old_length);
+ current_id = old_length;
+ bitmap_clear (&this_info->incoming_open_chains_set);
+ open_chains = NULL;
+ if (insn_rr.exists ())
{
- if (DEBUG_INSN_P (tmp->insn))
- continue;
- n_uses++;
- IOR_COMPL_HARD_REG_SET (this_unavailable,
- reg_class_contents[tmp->cl]);
+ rtx_insn *insn;
+ FOR_BB_INSNS (bb1, insn)
+ {
+ insn_rr_info *p = &insn_rr[INSN_UID (insn)];
+ p->op_info = NULL;
+ }
}
+ continue;
+ }
+
+ if (dump_file)
+ dump_def_use_chain (old_length);
+ bitmap_copy (&this_info->open_chains_set, &open_chains_set);
+
+ /* Add successor blocks to the worklist if necessary, and record
+ data about our own open chains at the end of this block, which
+ will be used to pre-open chains when processing the successors. */
+ FOR_EACH_EDGE (e, ei, bb1->succs)
+ {
+ struct bb_rename_info *dest_ri;
+ struct du_head *chain;
+
+ if (dump_file)
+ fprintf (dump_file, "successor block %d\n", e->dest->index);
- if (n_uses < 2)
+ if (e->flags & (EDGE_EH | EDGE_ABNORMAL))
continue;
+ dest_ri = (struct bb_rename_info *)e->dest->aux;
+ if (dest_ri == NULL)
+ continue;
+ for (chain = open_chains; chain; chain = chain->next_chain)
+ set_incoming_from_chain (dest_ri, chain);
+ }
+ }
- if (this_head->need_caller_save_reg)
- IOR_HARD_REG_SET (this_unavailable, call_used_reg_set);
+ free (inverse_postorder);
- merge_overlapping_regs (bb, &this_unavailable, this_head);
+ /* Now, combine the chains data we have gathered across basic block
+ boundaries.
- /* 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++)
+ For every basic block, there may be chains open at the start, or at the
+ end. Rather than exclude them from renaming, we look for open chains
+ with matching registers at the other side of the CFG edge.
+
+ For a given chain using register R, open at the start of block B, we
+ must find an open chain using R on the other side of every edge leading
+ to B, if the register is live across this edge. In the code below,
+ N_PREDS_USED counts the number of edges where the register is live, and
+ N_PREDS_JOINED counts those where we found an appropriate chain for
+ joining.
+
+ We perform the analysis for both incoming and outgoing edges, but we
+ only need to merge once (in the second part, after verifying outgoing
+ edges). */
+ FOR_EACH_BB_FN (bb, cfun)
+ {
+ struct bb_rename_info *bb_ri = (struct bb_rename_info *) bb->aux;
+ unsigned j;
+ bitmap_iterator bi;
+
+ if (bb_ri == NULL)
+ continue;
+
+ if (dump_file)
+ fprintf (dump_file, "processing bb %d in edges\n", bb->index);
+
+ EXECUTE_IF_SET_IN_BITMAP (&bb_ri->incoming_open_chains_set, 0, j, bi)
+ {
+ edge e;
+ edge_iterator ei;
+ struct du_head *chain = regrename_chain_from_id (j);
+ int n_preds_used = 0, n_preds_joined = 0;
+
+ FOR_EACH_EDGE (e, ei, bb->preds)
{
- 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)
+ struct bb_rename_info *src_ri;
+ unsigned k;
+ bitmap_iterator bi2;
+ HARD_REG_SET live;
+ bool success = false;
+
+ REG_SET_TO_HARD_REG_SET (live, df_get_live_out (e->src));
+ if (!range_overlaps_hard_reg_set_p (live, chain->regno,
+ chain->nregs))
+ continue;
+ n_preds_used++;
+
+ if (e->flags & (EDGE_EH | EDGE_ABNORMAL))
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)
+ src_ri = (struct bb_rename_info *)e->src->aux;
+ if (src_ri == NULL)
+ continue;
+
+ EXECUTE_IF_SET_IN_BITMAP (&src_ri->open_chains_set,
+ 0, k, bi2)
{
- if (tick[best_new_reg] > tick[new_reg])
- best_new_reg = new_reg;
+ struct du_head *outgoing_chain = regrename_chain_from_id (k);
+
+ if (outgoing_chain->regno == chain->regno
+ && outgoing_chain->nregs == chain->nregs)
+ {
+ n_preds_joined++;
+ success = true;
+ break;
+ }
}
+ if (!success && dump_file)
+ fprintf (dump_file, "failure to match with pred block %d\n",
+ e->src->index);
}
-
- if (dump_file)
+ if (n_preds_joined < n_preds_used)
{
- 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 (dump_file)
+ fprintf (dump_file, "cannot rename chain %d\n", j);
+ chain->cannot_rename = 1;
}
+ }
+ }
+ FOR_EACH_BB_FN (bb, cfun)
+ {
+ struct bb_rename_info *bb_ri = (struct bb_rename_info *) bb->aux;
+ unsigned j;
+ bitmap_iterator bi;
+
+ if (bb_ri == NULL)
+ continue;
+
+ if (dump_file)
+ fprintf (dump_file, "processing bb %d out edges\n", bb->index);
- if (best_new_reg == reg)
+ EXECUTE_IF_SET_IN_BITMAP (&bb_ri->open_chains_set, 0, j, bi)
+ {
+ edge e;
+ edge_iterator ei;
+ struct du_head *chain = regrename_chain_from_id (j);
+ int n_succs_used = 0, n_succs_joined = 0;
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
{
- tick[reg] = ++this_tick;
- if (dump_file)
- fprintf (dump_file, "; no available better choice\n");
- continue;
- }
+ bool printed = false;
+ struct bb_rename_info *dest_ri;
+ unsigned k;
+ bitmap_iterator bi2;
+ HARD_REG_SET live;
+
+ REG_SET_TO_HARD_REG_SET (live, df_get_live_in (e->dest));
+ if (!range_overlaps_hard_reg_set_p (live, chain->regno,
+ chain->nregs))
+ continue;
+
+ n_succs_used++;
- if (dump_file)
- fprintf (dump_file, ", renamed as %s\n", reg_names[best_new_reg]);
+ dest_ri = (struct bb_rename_info *)e->dest->aux;
+ if (dest_ri == NULL)
+ continue;
- do_replace (this_head, best_new_reg);
- tick[best_new_reg] = ++this_tick;
- df_set_regs_ever_live (best_new_reg, true);
+ EXECUTE_IF_SET_IN_BITMAP (&dest_ri->incoming_open_chains_set,
+ 0, k, bi2)
+ {
+ struct du_head *incoming_chain = regrename_chain_from_id (k);
+
+ if (incoming_chain->regno == chain->regno
+ && incoming_chain->nregs == chain->nregs)
+ {
+ if (dump_file)
+ {
+ if (!printed)
+ fprintf (dump_file,
+ "merging blocks for edge %d -> %d\n",
+ e->src->index, e->dest->index);
+ printed = true;
+ fprintf (dump_file,
+ " merging chains %d (->%d) and %d (->%d) [%s]\n",
+ k, incoming_chain->id, j, chain->id,
+ reg_names[incoming_chain->regno]);
+ }
+
+ merge_chains (chain, incoming_chain);
+ n_succs_joined++;
+ break;
+ }
+ }
+ }
+ if (n_succs_joined < n_succs_used)
+ {
+ if (dump_file)
+ fprintf (dump_file, "cannot rename chain %d\n",
+ j);
+ chain->cannot_rename = 1;
+ }
}
-
- obstack_free (&rename_obstack, first_obj);
}
- obstack_free (&rename_obstack, NULL);
+ free (rename_info);
- if (dump_file)
- fputc ('\n', dump_file);
-
- return 0;
+ FOR_EACH_BB_FN (bb, cfun)
+ bb->aux = NULL;
}
-static void
-do_replace (struct du_head *head, int reg)
+/* Attempt to replace all uses of the register in the chain beginning with
+ HEAD with REG. Returns true on success and false if the replacement is
+ rejected because the insns would not validate. The latter can happen
+ e.g. if a match_parallel predicate enforces restrictions on register
+ numbering in its subpatterns. */
+
+bool
+regrename_do_replace (struct du_head *head, int reg)
{
struct du_chain *chain;
unsigned int base_regno = head->regno;
-
- gcc_assert (! DEBUG_INSN_P (head->first->insn));
+ machine_mode mode;
+ rtx last_reg = NULL_RTX, last_repl = NULL_RTX;
for (chain = head->first; chain; chain = chain->next_use)
{
int reg_ptr = REG_POINTER (*chain->loc);
if (DEBUG_INSN_P (chain->insn) && REGNO (*chain->loc) != base_regno)
- INSN_VAR_LOCATION_LOC (chain->insn) = gen_rtx_UNKNOWN_VAR_LOC ();
+ validate_change (chain->insn, &(INSN_VAR_LOCATION_LOC (chain->insn)),
+ gen_rtx_UNKNOWN_VAR_LOC (), true);
else
{
- rtx note;
-
- *chain->loc = gen_raw_REG (GET_MODE (*chain->loc), reg);
- if (regno >= FIRST_PSEUDO_REGISTER)
- ORIGINAL_REGNO (*chain->loc) = regno;
- REG_ATTRS (*chain->loc) = attr;
- REG_POINTER (*chain->loc) = reg_ptr;
-
- for (note = REG_NOTES (chain->insn); note; note = XEXP (note, 1))
+ if (*chain->loc != last_reg)
{
- if (REG_NOTE_KIND (note) == REG_DEAD
- || REG_NOTE_KIND (note) == REG_UNUSED)
- {
- rtx reg = XEXP (note, 0);
- gcc_assert (HARD_REGISTER_P (reg));
-
- if (REGNO (reg) == base_regno)
- XEXP (note, 0) = *chain->loc;
- }
+ last_repl = gen_raw_REG (GET_MODE (*chain->loc), reg);
+ if (regno >= FIRST_PSEUDO_REGISTER)
+ ORIGINAL_REGNO (last_repl) = regno;
+ REG_ATTRS (last_repl) = attr;
+ REG_POINTER (last_repl) = reg_ptr;
+ last_reg = *chain->loc;
}
+ validate_change (chain->insn, chain->loc, last_repl, true);
}
+ }
+
+ if (!apply_change_group ())
+ return false;
+
+ mode = GET_MODE (*head->first->loc);
+ head->renamed = 1;
+ head->regno = reg;
+ head->nregs = hard_regno_nregs (reg, mode);
+ return true;
+}
+
+
+/* True if we found a register with a size mismatch, which means that we
+ can't track its lifetime accurately. If so, we abort the current block
+ without renaming. */
+static bool fail_current_block;
+
+/* 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. */
- df_insn_rescan (chain->insn);
+static bool
+verify_reg_in_set (rtx op, HARD_REG_SET *pset)
+{
+ unsigned regno, nregs;
+ bool all_live, all_dead;
+ if (!REG_P (op))
+ return false;
+
+ regno = REGNO (op);
+ nregs = REG_NREGS (op);
+ all_live = all_dead = true;
+ while (nregs-- > 0)
+ if (TEST_HARD_REG_BIT (*pset, regno + nregs))
+ all_dead = false;
+ else
+ all_live = false;
+ if (!all_dead && !all_live)
+ {
+ fail_current_block = true;
+ return false;
}
+ return all_live;
}
+/* 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. */
-static struct du_head *open_chains;
-static struct du_head *closed_chains;
+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
+ CLOBBER, which tells us which kind of rtx to look at. If we have a
+ match, record the set register in live_hard_regs and in the hard_conflicts
+ bitmap of open chains. */
static void
-scan_rtx_reg (rtx insn, rtx *loc, enum reg_class cl,
- enum scan_actions action, enum op_type type, int earlyclobber)
+note_sets_clobbers (rtx x, const_rtx set, void *data)
+{
+ enum rtx_code code = *(enum rtx_code *)data;
+ struct du_head *chain;
+
+ if (GET_CODE (x) == SUBREG)
+ x = SUBREG_REG (x);
+ if (!REG_P (x) || GET_CODE (set) != code)
+ return;
+ /* There must not be pseudos at this point. */
+ gcc_assert (HARD_REGISTER_P (x));
+ add_to_hard_reg_set (&live_hard_regs, GET_MODE (x), REGNO (x));
+ for (chain = open_chains; chain; chain = chain->next_chain)
+ add_to_hard_reg_set (&chain->hard_conflicts, GET_MODE (x), REGNO (x));
+}
+
+static void
+scan_rtx_reg (rtx_insn *insn, rtx *loc, enum reg_class cl, enum scan_actions action,
+ enum op_type type)
{
struct du_head **p;
rtx x = *loc;
- enum machine_mode mode = GET_MODE (x);
unsigned this_regno = REGNO (x);
- unsigned this_nregs = hard_regno_nregs[this_regno][mode];
+ int this_nregs = REG_NREGS (x);
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);
- 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->terminated = 0;
-
- this_du->next_use = 0;
- this_du->loc = loc;
- this_du->insn = insn;
- this_du->cl = cl;
- this_du->earlyclobber = earlyclobber;
+ du_head_p c;
+ rtx pat = PATTERN (insn);
+
+ c = create_new_chain (this_regno, this_nregs, loc, insn, cl);
+
+ /* We try to tie chains in a move instruction for
+ a single output. */
+ if (recog_data.n_operands == 2
+ && GET_CODE (pat) == SET
+ && GET_CODE (SET_DEST (pat)) == REG
+ && GET_CODE (SET_SRC (pat)) == REG
+ && terminated_this_insn
+ && terminated_this_insn->nregs
+ == REG_NREGS (recog_data.operand[1]))
+ {
+ gcc_assert (terminated_this_insn->regno
+ == REGNO (recog_data.operand[1]));
+
+ c->tied_chain = terminated_this_insn;
+ terminated_this_insn->tied_chain = c;
+
+ if (dump_file)
+ fprintf (dump_file, "Tying chain %s (%d) with %s (%d)\n",
+ reg_names[c->regno], c->id,
+ reg_names[terminated_this_insn->regno],
+ terminated_this_insn->id);
+ }
}
+
return;
}
for (p = &open_chains; *p;)
{
struct du_head *head = *p;
-
- /* Check if the chain has been terminated if it has then skip to
- the next chain.
-
- This can happen when we've already appended the location to
- the chain in Step 3, but are trying to hide in-out operands
- from terminate_write in Step 5. */
-
- if (head->terminated)
- p = &head->next_chain;
- else
+ struct du_head *next = head->next_chain;
+ int exact_match = (head->regno == this_regno
+ && 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 (!bitmap_bit_p (&open_chains_set, head->id)
+ || head->regno + head->nregs <= this_regno
+ || this_regno + this_nregs <= head->regno)
{
- int exact_match = (head->regno == this_regno
- && head->nregs == this_nregs);
-
- if (head->regno + head->nregs <= this_regno
- || this_regno + this_nregs <= head->regno)
- {
- p = &head->next_chain;
- continue;
- }
-
- if (action == mark_read || action == mark_access)
- {
- gcc_assert (exact_match || DEBUG_INSN_P (insn));
+ p = &head->next_chain;
+ continue;
+ }
- /* ??? Class NO_REGS can happen if the md file makes use of
- EXTRA_CONSTRAINTS to match registers. Which is arguably
- wrong, but there we are. Since we know not what this may
- be replaced with, terminate the chain. */
- if (cl != NO_REGS)
- {
- struct du_chain *this_du;
- this_du = XOBNEW (&rename_obstack, struct du_chain);
- this_du->next_use = 0;
- this_du->loc = loc;
- this_du->insn = insn;
- this_du->cl = cl;
- head->last->next_use = this_du;
- head->last = this_du;
- return;
- }
- }
+ if (action == mark_read || action == mark_access)
+ {
+ /* ??? Class NO_REGS can happen if the md file makes use of
+ EXTRA_CONSTRAINTS to match registers. Which is arguably
+ wrong, but there we are. */
- if (action != terminate_overlapping_read || ! exact_match)
+ if (cl == NO_REGS || (!exact_match && !DEBUG_INSN_P (insn)))
{
- struct du_head *next = head->next_chain;
-
- /* Whether the terminated chain can be used for renaming
- depends on the action and this being an exact match.
- In either case, we remove this element from open_chains. */
-
- head->terminated = 1;
- if ((action == terminate_dead || action == terminate_write)
- && exact_match)
+ if (dump_file)
+ fprintf (dump_file,
+ "Cannot rename chain %s (%d) at insn %d (%s)\n",
+ reg_names[head->regno], head->id, INSN_UID (insn),
+ scan_actions_name[(int) action]);
+ head->cannot_rename = 1;
+ if (superset)
{
- head->next_chain = closed_chains;
- closed_chains = head;
+ 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,
- "Closing chain %s at insn %d (%s)\n",
- reg_names[head->regno], INSN_UID (insn),
- scan_actions_name[(int) action]);
+ "Widening register in chain %s (%d) at insn %d\n",
+ reg_names[head->regno], head->id, INSN_UID (insn));
}
- else
+ else if (!subset)
{
+ fail_current_block = true;
if (dump_file)
fprintf (dump_file,
- "Discarding chain %s at insn %d (%s)\n",
- reg_names[head->regno], INSN_UID (insn),
- scan_actions_name[(int) action]);
+ "Failing basic block due to unhandled overlap\n");
}
- *p = next;
}
else
- p = &head->next_chain;
+ {
+ struct du_chain *this_du;
+ this_du = XOBNEW (&rename_obstack, struct du_chain);
+ this_du->next_use = 0;
+ this_du->loc = loc;
+ this_du->insn = insn;
+ this_du->cl = cl;
+ if (head->first == NULL)
+ head->first = this_du;
+ else
+ head->last->next_use = this_du;
+ record_operand_use (head, this_du);
+ head->last = this_du;
+ }
+ /* Avoid adding the same location in a DEBUG_INSN multiple times,
+ which could happen with non-exact overlap. */
+ if (DEBUG_INSN_P (insn))
+ return;
+ /* Otherwise, find any other chains that do not match exactly;
+ ensure they all get marked unrenamable. */
+ p = &head->next_chain;
+ continue;
+ }
+
+ /* Whether the terminated chain can be used for renaming
+ depends on the action and this being an exact match.
+ In either case, we remove this element from open_chains. */
+
+ if ((action == terminate_dead || action == terminate_write)
+ && (superset || subset))
+ {
+ unsigned nregs;
+
+ if (subset && !superset)
+ head->cannot_rename = 1;
+ bitmap_clear_bit (&open_chains_set, head->id);
+
+ nregs = head->nregs;
+ while (nregs-- > 0)
+ {
+ CLEAR_HARD_REG_BIT (live_in_chains, head->regno + nregs);
+ if (subset && !superset
+ && (head->regno + nregs < this_regno
+ || head->regno + nregs >= this_regno + this_nregs))
+ SET_HARD_REG_BIT (live_hard_regs, head->regno + nregs);
+ }
+
+ if (action == terminate_dead)
+ terminated_this_insn = *p;
+ *p = next;
+ if (dump_file)
+ fprintf (dump_file,
+ "Closing chain %s (%d) at insn %d (%s%s)\n",
+ reg_names[head->regno], head->id, INSN_UID (insn),
+ scan_actions_name[(int) action],
+ superset ? ", superset" : subset ? ", subset" : "");
+ }
+ else if (action == terminate_dead || action == terminate_write)
+ {
+ /* In this case, tracking liveness gets too hard. Fail the
+ entire basic block. */
+ if (dump_file)
+ fprintf (dump_file,
+ "Failing basic block due to unhandled overlap\n");
+ fail_current_block = true;
+ return;
+ }
+ else
+ {
+ head->cannot_rename = 1;
+ if (dump_file)
+ fprintf (dump_file,
+ "Cannot rename chain %s (%d) at insn %d (%s)\n",
+ reg_names[head->regno], head->id, INSN_UID (insn),
+ scan_actions_name[(int) action]);
+ p = &head->next_chain;
}
}
}
+/* A wrapper around base_reg_class which returns ALL_REGS if INSN is a
+ DEBUG_INSN. The arguments MODE, AS, CODE and INDEX_CODE are as for
+ base_reg_class. */
+
+static reg_class
+base_reg_class_for_rename (rtx_insn *insn, machine_mode mode, addr_space_t as,
+ rtx_code code, rtx_code index_code)
+{
+ if (DEBUG_INSN_P (insn))
+ return ALL_REGS;
+ return base_reg_class (mode, as, code, index_code);
+}
+
/* Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or
BASE_REG_CLASS depending on how the register is being considered. */
static void
-scan_rtx_address (rtx insn, rtx *loc, enum reg_class cl,
- enum scan_actions action, enum machine_mode mode)
+scan_rtx_address (rtx_insn *insn, rtx *loc, enum reg_class cl,
+ enum scan_actions action, machine_mode mode,
+ addr_space_t as)
{
rtx x = *loc;
RTX_CODE code = GET_CODE (x);
unsigned regno0 = REGNO (op0), regno1 = REGNO (op1);
if (REGNO_OK_FOR_INDEX_P (regno1)
- && regno_ok_for_base_p (regno0, mode, PLUS, REG))
+ && regno_ok_for_base_p (regno0, mode, as, PLUS, REG))
index_op = 1;
else if (REGNO_OK_FOR_INDEX_P (regno0)
- && regno_ok_for_base_p (regno1, mode, PLUS, REG))
+ && regno_ok_for_base_p (regno1, mode, as, PLUS, REG))
index_op = 0;
- else if (regno_ok_for_base_p (regno0, mode, PLUS, REG)
+ else if (regno_ok_for_base_p (regno0, mode, as, PLUS, REG)
|| REGNO_OK_FOR_INDEX_P (regno1))
index_op = 1;
- else if (regno_ok_for_base_p (regno1, mode, PLUS, REG))
+ else if (regno_ok_for_base_p (regno1, mode, as, PLUS, REG))
index_op = 0;
else
index_op = 1;
}
if (locI)
- scan_rtx_address (insn, locI, INDEX_REG_CLASS, action, mode);
+ {
+ reg_class iclass = DEBUG_INSN_P (insn) ? ALL_REGS : INDEX_REG_CLASS;
+ scan_rtx_address (insn, locI, iclass, action, mode, as);
+ }
if (locB)
- scan_rtx_address (insn, locB, base_reg_class (mode, PLUS, index_code),
- action, mode);
-
+ {
+ reg_class bclass = base_reg_class_for_rename (insn, mode, as, PLUS,
+ index_code);
+ scan_rtx_address (insn, locB, bclass, action, mode, as);
+ }
return;
}
case PRE_INC:
case PRE_DEC:
case PRE_MODIFY:
-#ifndef AUTO_INC_DEC
/* If the target doesn't claim to handle autoinc, this must be
something special, like a stack push. Kill this chain. */
- action = terminate_all_read;
-#endif
+ if (!AUTO_INC_DEC)
+ action = mark_all_read;
+
break;
case MEM:
- scan_rtx_address (insn, &XEXP (x, 0),
- base_reg_class (GET_MODE (x), MEM, SCRATCH), action,
- GET_MODE (x));
+ {
+ reg_class bclass = base_reg_class_for_rename (insn, GET_MODE (x),
+ MEM_ADDR_SPACE (x),
+ MEM, SCRATCH);
+ scan_rtx_address (insn, &XEXP (x, 0), bclass, action, GET_MODE (x),
+ MEM_ADDR_SPACE (x));
+ }
return;
case REG:
- scan_rtx_reg (insn, loc, cl, action, OP_IN, 0);
+ scan_rtx_reg (insn, loc, cl, action, OP_IN);
return;
default:
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
{
if (fmt[i] == 'e')
- scan_rtx_address (insn, &XEXP (x, i), cl, action, mode);
+ scan_rtx_address (insn, &XEXP (x, i), cl, action, mode, as);
else if (fmt[i] == 'E')
for (j = XVECLEN (x, i) - 1; j >= 0; j--)
- scan_rtx_address (insn, &XVECEXP (x, i, j), cl, action, mode);
+ scan_rtx_address (insn, &XVECEXP (x, i, j), cl, action, mode, as);
}
}
static void
-scan_rtx (rtx insn, rtx *loc, enum reg_class cl,
- enum scan_actions action, enum op_type type, int earlyclobber)
+scan_rtx (rtx_insn *insn, rtx *loc, enum reg_class cl, enum scan_actions action,
+ enum op_type type)
{
const char *fmt;
rtx x = *loc;
switch (code)
{
case CONST:
- case CONST_INT:
- case CONST_DOUBLE:
- case CONST_FIXED:
- case CONST_VECTOR:
+ CASE_CONST_ANY:
case SYMBOL_REF:
case LABEL_REF:
case CC0:
return;
case REG:
- scan_rtx_reg (insn, loc, cl, action, type, earlyclobber);
+ scan_rtx_reg (insn, loc, cl, action, type);
return;
case MEM:
- scan_rtx_address (insn, &XEXP (x, 0),
- base_reg_class (GET_MODE (x), MEM, SCRATCH), action,
- GET_MODE (x));
+ {
+ reg_class bclass = base_reg_class_for_rename (insn, GET_MODE (x),
+ MEM_ADDR_SPACE (x),
+ MEM, SCRATCH);
+
+ scan_rtx_address (insn, &XEXP (x, 0), bclass, action, GET_MODE (x),
+ MEM_ADDR_SPACE (x));
+ }
return;
case SET:
- scan_rtx (insn, &SET_SRC (x), cl, action, OP_IN, 0);
+ scan_rtx (insn, &SET_SRC (x), cl, action, OP_IN);
scan_rtx (insn, &SET_DEST (x), cl, action,
- GET_CODE (PATTERN (insn)) == COND_EXEC ? OP_INOUT : OP_OUT, 0);
+ (GET_CODE (PATTERN (insn)) == COND_EXEC
+ && verify_reg_tracked (SET_DEST (x))) ? OP_INOUT : OP_OUT);
return;
case STRICT_LOW_PART:
- scan_rtx (insn, &XEXP (x, 0), cl, action, OP_INOUT, earlyclobber);
+ 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, earlyclobber);
- scan_rtx (insn, &XEXP (x, 1), cl, action, OP_IN, 0);
- scan_rtx (insn, &XEXP (x, 2), cl, action, OP_IN, 0);
+ (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;
case POST_INC:
case CLOBBER:
scan_rtx (insn, &SET_DEST (x), cl, action,
- GET_CODE (PATTERN (insn)) == COND_EXEC ? OP_INOUT : OP_OUT, 0);
+ (GET_CODE (PATTERN (insn)) == COND_EXEC
+ && verify_reg_tracked (SET_DEST (x))) ? OP_INOUT : OP_OUT);
return;
case EXPR_LIST:
- scan_rtx (insn, &XEXP (x, 0), cl, action, type, 0);
+ scan_rtx (insn, &XEXP (x, 0), cl, action, type);
if (XEXP (x, 1))
- scan_rtx (insn, &XEXP (x, 1), cl, action, type, 0);
+ scan_rtx (insn, &XEXP (x, 1), cl, action, type);
return;
default:
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
{
if (fmt[i] == 'e')
- scan_rtx (insn, &XEXP (x, i), cl, action, type, 0);
+ scan_rtx (insn, &XEXP (x, i), cl, action, type);
else if (fmt[i] == 'E')
for (j = XVECLEN (x, i) - 1; j >= 0; j--)
- scan_rtx (insn, &XVECEXP (x, i, j), cl, action, type, 0);
+ scan_rtx (insn, &XVECEXP (x, i, j), cl, action, type);
+ }
+}
+
+/* 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,
+ unsigned HOST_WIDE_INT do_not_hide, bool inout_and_ec_only)
+{
+ int i;
+ const operand_alternative *op_alt = which_op_alt ();
+ for (i = 0; i < n_ops; i++)
+ {
+ old_operands[i] = recog_data.operand[i];
+ /* Don't squash match_operator or match_parallel here, since
+ we don't know that all of the contained registers are
+ 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
+ || op_alt[i].earlyclobber)
+ *recog_data.operand_loc[i] = cc0_rtx;
+ }
+ for (i = 0; i < recog_data.n_dups; i++)
+ {
+ 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
+ || op_alt[opn].earlyclobber)
+ *recog_data.dup_loc[i] = cc0_rtx;
+ }
+}
+
+/* Undo the substitution performed by hide_operands. INSN is the insn we
+ are processing; the arguments are the same as in hide_operands. */
+
+static void
+restore_operands (rtx_insn *insn, int n_ops, rtx *old_operands, rtx *old_dups)
+{
+ int i;
+ for (i = 0; i < recog_data.n_dups; i++)
+ *recog_data.dup_loc[i] = old_dups[i];
+ for (i = 0; i < n_ops; i++)
+ *recog_data.operand_loc[i] = old_operands[i];
+ if (recog_data.n_dups)
+ df_insn_rescan (insn);
+}
+
+/* For each output operand of INSN, call scan_rtx to create a new
+ open chain. Do this only for normal or earlyclobber outputs,
+ depending on EARLYCLOBBER. If INSN_INFO is nonnull, use it to
+ record information about the operands in the insn. */
+
+static void
+record_out_operands (rtx_insn *insn, bool earlyclobber, insn_rr_info *insn_info)
+{
+ int n_ops = recog_data.n_operands;
+ const operand_alternative *op_alt = which_op_alt ();
+
+ int i;
+
+ for (i = 0; i < n_ops + recog_data.n_dups; i++)
+ {
+ int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
+ rtx *loc = (i < n_ops
+ ? recog_data.operand_loc[opn]
+ : recog_data.dup_loc[i - n_ops]);
+ rtx op = *loc;
+ enum reg_class cl = alternative_class (op_alt, opn);
+
+ struct du_head *prev_open;
+
+ if (recog_data.operand_type[opn] != OP_OUT
+ || op_alt[opn].earlyclobber != earlyclobber)
+ continue;
+
+ if (insn_info)
+ cur_operand = insn_info->op_info + i;
+
+ prev_open = open_chains;
+ if (earlyclobber)
+ scan_rtx (insn, loc, cl, terminate_write, OP_OUT);
+ scan_rtx (insn, loc, cl, mark_write, OP_OUT);
+
+ /* ??? Many targets have output constraints on the SET_DEST
+ of a call insn, which is stupid, since these are certainly
+ ABI defined hard registers. For these, and for asm operands
+ that originally referenced hard registers, we must record that
+ the chain cannot be renamed. */
+ if (CALL_P (insn)
+ || (asm_noperands (PATTERN (insn)) > 0
+ && REG_P (op)
+ && REGNO (op) == ORIGINAL_REGNO (op)))
+ {
+ if (prev_open != open_chains)
+ open_chains->cannot_rename = 1;
+ }
}
+ cur_operand = NULL;
}
/* Build def/use chain. */
-static struct du_head *
+static bool
build_def_use (basic_block bb)
{
- rtx insn;
+ rtx_insn *insn;
+ unsigned HOST_WIDE_INT untracked_operands;
- open_chains = closed_chains = NULL;
+ fail_current_block = false;
for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
{
rtx note;
rtx old_operands[MAX_RECOG_OPERANDS];
rtx old_dups[MAX_DUP_OPERANDS];
- int i, icode;
- int alt;
+ int i;
int predicated;
+ enum rtx_code set_code = SET;
+ enum rtx_code clobber_code = CLOBBER;
+ insn_rr_info *insn_info = NULL;
+ terminated_this_insn = NULL;
/* Process the insn, determining its effect on the def-use
- chains. We perform the following steps with the register
- references in the insn:
- (1) Any read that overlaps an open chain, but doesn't exactly
- match, causes that chain to be closed. We can't deal
- with overlaps yet.
+ chains and live hard registers. We perform the following
+ steps with the register references in the insn, simulating
+ its effect:
+ (1) Deal with earlyclobber operands and CLOBBERs of non-operands
+ by creating chains and marking hard regs live.
(2) Any read outside an operand causes any chain it overlaps
- with to be closed, since we can't replace it.
+ with to be marked unrenamable.
(3) Any read inside an operand is added if there's already
an open chain for it.
(4) For any REG_DEAD note we find, close open chains that
overlap it.
- (5) For any write we find, close open chains that overlap it.
- (6) For any write we find in an operand, make a new chain.
- (7) For any REG_UNUSED, close any chains we just opened. */
-
- icode = recog_memoized (insn);
- extract_insn (insn);
- if (! constrain_operands (1))
- fatal_insn_not_found (insn);
- preprocess_constraints ();
- alt = which_alternative;
+ (5) For any non-earlyclobber write we find, close open chains
+ that overlap it.
+ (6) For any non-earlyclobber write we find in an operand, make
+ a new chain or mark the hard register as live.
+ (7) For any REG_UNUSED, close any chains we just opened.
+ (8) For any REG_CFA_RESTORE or REG_CFA_REGISTER, kill any chain
+ containing its dest.
+
+ We cannot deal with situations where we track a reg in one mode
+ and see a reference in another mode; these will cause the chain
+ to be marked unrenamable or even cause us to abort the entire
+ basic block. */
+
+ extract_constrain_insn (insn);
+ preprocess_constraints (insn);
+ const operand_alternative *op_alt = which_op_alt ();
n_ops = recog_data.n_operands;
+ untracked_operands = 0;
+
+ if (insn_rr.exists ())
+ {
+ insn_info = &insn_rr[INSN_UID (insn)];
+ insn_info->op_info = XOBNEWVEC (&rename_obstack, operand_rr_info,
+ recog_data.n_operands);
+ memset (insn_info->op_info, 0,
+ sizeof (operand_rr_info) * recog_data.n_operands);
+ }
- /* Simplify the code below by rewriting things to reflect
- matching constraints. Also promote OP_OUT to OP_INOUT
- in predicated instructions. */
+ /* Simplify the code below by promoting OP_OUT to OP_INOUT in
+ predicated instructions, but only for register operands
+ that are already tracked, so that we can create a chain
+ when the first SET makes a register live. */
predicated = GET_CODE (PATTERN (insn)) == COND_EXEC;
for (i = 0; i < n_ops; ++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
+ rtx op = recog_data.operand[i];
+ int matches = op_alt[i].matches;
+ if (matches >= 0 || op_alt[i].matched >= 0
|| (predicated && recog_data.operand_type[i] == OP_OUT))
- recog_data.operand_type[i] = OP_INOUT;
+ {
+ 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. */
+ machine_mode i_mode = recog_data.operand_mode[i];
+ if (matches >= 0)
+ {
+ machine_mode matches_mode
+ = recog_data.operand_mode[matches];
+
+ if (maybe_ne (GET_MODE_SIZE (i_mode),
+ GET_MODE_SIZE (matches_mode))
+ && !verify_reg_in_set (op, &live_in_chains))
+ {
+ untracked_operands |= 1 << i;
+ untracked_operands |= 1 << matches;
+ }
+ }
+ }
+#ifdef STACK_REGS
+ if (regstack_completed
+ && REG_P (op)
+ && IN_RANGE (REGNO (op), FIRST_STACK_REG, LAST_STACK_REG))
+ untracked_operands |= 1 << i;
+#endif
+ /* 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))
+ create_new_chain (REGNO (op), REG_NREGS (op), NULL, NULL,
+ NO_REGS);
}
- /* Step 1: Close chains for which we have overlapping reads. */
- for (i = 0; i < n_ops; i++)
- scan_rtx (insn, recog_data.operand_loc[i],
- NO_REGS, terminate_overlapping_read,
- recog_data.operand_type[i], 0);
+ if (fail_current_block)
+ break;
- /* Step 2: Close chains for which we have reads outside operands.
- We do this by munging all operands into CC0, and closing
- everything remaining. */
+ /* Step 1a: Mark hard registers that are clobbered in this insn,
+ outside an operand, as live. */
+ 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);
- for (i = 0; i < n_ops; i++)
- {
- old_operands[i] = recog_data.operand[i];
- /* Don't squash match_operator or match_parallel here, since
- we don't know that all of the contained registers are
- reachable by proper operands. */
- if (recog_data.constraints[i][0] == '\0')
- continue;
- *recog_data.operand_loc[i] = cc0_rtx;
- }
- for (i = 0; i < recog_data.n_dups; i++)
- {
- old_dups[i] = *recog_data.dup_loc[i];
- *recog_data.dup_loc[i] = cc0_rtx;
- }
+ /* Step 1b: Begin new chains for earlyclobbered writes inside
+ operands. */
+ record_out_operands (insn, true, insn_info);
- scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_all_read,
- OP_IN, 0);
+ /* Step 2: Mark chains for which we have reads outside operands
+ as unrenamable.
+ We do this by munging all operands into CC0, and closing
+ everything remaining. */
- for (i = 0; i < recog_data.n_dups; i++)
- *recog_data.dup_loc[i] = old_dups[i];
- for (i = 0; i < n_ops; i++)
- *recog_data.operand_loc[i] = old_operands[i];
- if (recog_data.n_dups)
- df_insn_rescan (insn);
+ 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);
/* Step 2B: Can't rename function call argument registers. */
if (CALL_P (insn) && CALL_INSN_FUNCTION_USAGE (insn))
scan_rtx (insn, &CALL_INSN_FUNCTION_USAGE (insn),
- NO_REGS, terminate_all_read, OP_IN, 0);
+ NO_REGS, mark_all_read, OP_IN);
/* Step 2C: Can't rename asm operands that were originally
hard registers. */
&& REGNO (op) == ORIGINAL_REGNO (op)
&& (recog_data.operand_type[i] == OP_IN
|| recog_data.operand_type[i] == OP_INOUT))
- scan_rtx (insn, loc, NO_REGS, terminate_all_read, OP_IN, 0);
+ scan_rtx (insn, loc, NO_REGS, mark_all_read, OP_IN);
}
/* Step 3: Append to chains for reads inside operands. */
rtx *loc = (i < n_ops
? recog_data.operand_loc[opn]
: recog_data.dup_loc[i - n_ops]);
- enum reg_class cl = recog_op_alt[opn][alt].cl;
+ enum reg_class cl = alternative_class (op_alt, opn);
enum op_type type = recog_data.operand_type[opn];
/* 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)
- scan_rtx_address (insn, loc, cl, mark_read, VOIDmode);
+ if (insn_info)
+ cur_operand = i == opn ? insn_info->op_info + i : NULL;
+ if (op_alt[opn].is_address)
+ scan_rtx_address (insn, loc, cl, mark_read,
+ VOIDmode, ADDR_SPACE_GENERIC);
else
- scan_rtx (insn, loc, cl, mark_read, type, 0);
+ scan_rtx (insn, loc, cl, mark_read, type);
}
+ cur_operand = NULL;
/* Step 3B: Record updates for regs in REG_INC notes, and
source regs in REG_FRAME_RELATED_EXPR notes. */
if (REG_NOTE_KIND (note) == REG_INC
|| REG_NOTE_KIND (note) == REG_FRAME_RELATED_EXPR)
scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_read,
- OP_INOUT, 0);
-
- /* Step 4: Close chains for registers that die here. */
+ OP_INOUT);
+
+ /* Step 4: Close chains for registers that die here, unless
+ the register is mentioned in a REG_UNUSED note. In that
+ case we keep the chain open until step #7 below to ensure
+ it conflicts with other output operands of this insn.
+ See PR 52573. Arguably the insn should not have both
+ notes; it has proven difficult to fix that without
+ other undesirable side effects. */
for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
- if (REG_NOTE_KIND (note) == REG_DEAD)
- scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead,
- OP_IN, 0);
+ if (REG_NOTE_KIND (note) == REG_DEAD
+ && !find_regno_note (insn, REG_UNUSED, REGNO (XEXP (note, 0))))
+ {
+ remove_from_hard_reg_set (&live_hard_regs,
+ GET_MODE (XEXP (note, 0)),
+ REGNO (XEXP (note, 0)));
+ scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead,
+ OP_IN);
+ }
/* Step 4B: If this is a call, any chain live at this point
requires a caller-saved reg. */
/* Step 5: Close open chains that overlap writes. Similar to
step 2, we hide in-out operands, since we do not want to
- close these chains. */
-
- for (i = 0; i < n_ops; i++)
- {
- old_operands[i] = recog_data.operand[i];
- if (recog_data.operand_type[i] == OP_INOUT)
- *recog_data.operand_loc[i] = cc0_rtx;
- }
- for (i = 0; i < recog_data.n_dups; i++)
- {
- int opn = recog_data.dup_num[i];
- old_dups[i] = *recog_data.dup_loc[i];
- if (recog_data.operand_type[opn] == OP_INOUT)
- *recog_data.dup_loc[i] = cc0_rtx;
- }
-
- scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_write, OP_IN, 0);
-
- for (i = 0; i < recog_data.n_dups; i++)
- *recog_data.dup_loc[i] = old_dups[i];
- for (i = 0; i < n_ops; i++)
- *recog_data.operand_loc[i] = old_operands[i];
-
- /* Step 6: Begin new chains for writes inside operands. */
- /* ??? Many targets have output constraints on the SET_DEST
- of a call insn, which is stupid, since these are certainly
- ABI defined hard registers. Don't change calls at all.
- Similarly take special care for asm statement that originally
- referenced hard registers. */
- if (asm_noperands (PATTERN (insn)) > 0)
- {
- for (i = 0; i < n_ops; i++)
- if (recog_data.operand_type[i] == OP_OUT)
- {
- rtx *loc = recog_data.operand_loc[i];
- rtx op = *loc;
- enum reg_class cl = recog_op_alt[i][alt].cl;
-
- if (REG_P (op)
- && REGNO (op) == ORIGINAL_REGNO (op))
- continue;
-
- scan_rtx (insn, loc, cl, mark_write, OP_OUT,
- recog_op_alt[i][alt].earlyclobber);
- }
- }
- else if (!CALL_P (insn))
- for (i = 0; i < n_ops + recog_data.n_dups; i++)
- {
- int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
- rtx *loc = (i < n_ops
- ? recog_data.operand_loc[opn]
- : recog_data.dup_loc[i - n_ops]);
- enum reg_class cl = recog_op_alt[opn][alt].cl;
-
- if (recog_data.operand_type[opn] == OP_OUT)
- scan_rtx (insn, loc, cl, mark_write, OP_OUT,
- recog_op_alt[opn][alt].earlyclobber);
- }
-
- /* Step 6B: Record destination regs in REG_FRAME_RELATED_EXPR
+ close these chains. We also hide earlyclobber operands,
+ since we've opened chains for them in step 1, and earlier
+ chains they would overlap with must have been closed at
+ the previous insn at the latest, as such operands cannot
+ possibly overlap with any input operands. */
+
+ 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, untracked_operands,
+ false);
+ note_stores (PATTERN (insn), note_sets_clobbers, &set_code);
+ restore_operands (insn, n_ops, old_operands, old_dups);
+
+ /* Step 6b: Begin new chains for writes inside operands. */
+ record_out_operands (insn, false, insn_info);
+
+ /* Step 6c: Record destination regs in REG_FRAME_RELATED_EXPR
notes for update. */
for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
if (REG_NOTE_KIND (note) == REG_FRAME_RELATED_EXPR)
scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_access,
- OP_INOUT, 0);
+ OP_INOUT);
/* Step 7: Close chains for registers that were never
really used here. */
for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
if (REG_NOTE_KIND (note) == REG_UNUSED)
- scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead,
- OP_IN, 0);
+ {
+ remove_from_hard_reg_set (&live_hard_regs,
+ GET_MODE (XEXP (note, 0)),
+ REGNO (XEXP (note, 0)));
+ scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead,
+ OP_IN);
+ }
+
+ /* Step 8: Kill the chains involving register restores. Those
+ should restore _that_ register. Similar for REG_CFA_REGISTER. */
+ for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
+ if (REG_NOTE_KIND (note) == REG_CFA_RESTORE
+ || REG_NOTE_KIND (note) == REG_CFA_REGISTER)
+ {
+ rtx *x = &XEXP (note, 0);
+ if (!*x)
+ x = &PATTERN (insn);
+ if (GET_CODE (*x) == PARALLEL)
+ x = &XVECEXP (*x, 0, 0);
+ if (GET_CODE (*x) == SET)
+ x = &SET_DEST (*x);
+ scan_rtx (insn, x, NO_REGS, mark_all_read, OP_IN);
+ }
}
- else if (DEBUG_INSN_P (insn)
+ else if (DEBUG_BIND_INSN_P (insn)
&& !VAR_LOC_UNKNOWN_P (INSN_VAR_LOCATION_LOC (insn)))
{
scan_rtx (insn, &INSN_VAR_LOCATION_LOC (insn),
- ALL_REGS, mark_read, OP_IN, 0);
+ ALL_REGS, mark_read, OP_IN);
}
if (insn == BB_END (bb))
break;
}
- /* 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;
-}
+ if (fail_current_block)
+ return false;
-/* Dump all def/use chains in CHAINS to DUMP_FILE. They are
- printed in reverse order as that's how we build them. */
+ return true;
+}
+\f
+/* Initialize the register renamer. If INSN_INFO is true, ensure that
+ insn_rr is nonnull. */
+void
+regrename_init (bool insn_info)
+{
+ gcc_obstack_init (&rename_obstack);
+ insn_rr.create (0);
+ if (insn_info)
+ insn_rr.safe_grow_cleared (get_max_uid ());
+}
-static void
-dump_def_use_chain (struct du_head *head)
+/* Free all global data used by the register renamer. */
+void
+regrename_finish (void)
{
- 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;
- }
+ insn_rr.release ();
+ free_chain_data ();
+ obstack_free (&rename_obstack, NULL);
}
-\f
-static bool
-gate_handle_regrename (void)
+/* Perform register renaming on the current function. */
+
+static unsigned int
+regrename_optimize (void)
{
- return (optimize > 0 && (flag_rename_registers));
+ df_set_flags (DF_LR_RUN_DCE);
+ df_note_add_problem ();
+ df_analyze ();
+ df_set_flags (DF_DEFER_INSN_RESCAN);
+
+ regrename_init (false);
+
+ regrename_analyze (NULL);
+
+ rename_chains ();
+
+ regrename_finish ();
+
+ return 0;
}
+\f
+namespace {
-struct rtl_opt_pass pass_regrename =
+const pass_data pass_data_regrename =
{
- {
- RTL_PASS,
- "rnreg", /* name */
- gate_handle_regrename, /* gate */
- regrename_optimize, /* execute */
- NULL, /* sub */
- NULL, /* next */
- 0, /* static_pass_number */
- TV_RENAME_REGISTERS, /* tv_id */
- 0, /* properties_required */
- 0, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- TODO_df_finish | TODO_verify_rtl_sharing |
- TODO_dump_func /* todo_flags_finish */
- }
+ RTL_PASS, /* type */
+ "rnreg", /* name */
+ OPTGROUP_NONE, /* optinfo_flags */
+ TV_RENAME_REGISTERS, /* tv_id */
+ 0, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_df_finish, /* todo_flags_finish */
};
+class pass_regrename : public rtl_opt_pass
+{
+public:
+ pass_regrename (gcc::context *ctxt)
+ : rtl_opt_pass (pass_data_regrename, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ virtual bool gate (function *)
+ {
+ return (optimize > 0 && (flag_rename_registers));
+ }
+
+ virtual unsigned int execute (function *) { return regrename_optimize (); }
+
+}; // class pass_regrename
+
+} // anon namespace
+
+rtl_opt_pass *
+make_pass_regrename (gcc::context *ctxt)
+{
+ return new pass_regrename (ctxt);
+}