/* Allocate registers for pseudo-registers that span basic blocks.
- Copyright (C) 1987, 88, 91, 94, 96-98, 1999 Free Software Foundation, Inc.
+ Copyright (C) 1987, 1988, 1991, 1994, 1996, 1997, 1998,
+ 1999, 2000 Free Software Foundation, Inc.
This file is part of GNU CC.
static int *reg_allocno;
-/* Indexed by allocno, gives the reg number. */
+struct allocno
+{
+ int reg;
+ /* Gives the number of consecutive hard registers needed by that
+ pseudo reg. */
+ int size;
+
+ /* Number of calls crossed by each allocno. */
+ int calls_crossed;
+
+ /* Number of refs (weighted) to each allocno. */
+ int n_refs;
+
+ /* Guess at live length of each allocno.
+ This is actually the max of the live lengths of the regs. */
+ int live_length;
+
+ /* Set of hard regs conflicting with allocno N. */
+
+ HARD_REG_SET hard_reg_conflicts;
+
+ /* Set of hard regs preferred by allocno N.
+ This is used to make allocnos go into regs that are copied to or from them,
+ when possible, to reduce register shuffling. */
+
+ HARD_REG_SET hard_reg_preferences;
-static int *allocno_reg;
+ /* Similar, but just counts register preferences made in simple copy
+ operations, rather than arithmetic. These are given priority because
+ we can always eliminate an insn by using these, but using a register
+ in the above list won't always eliminate an insn. */
+
+ HARD_REG_SET hard_reg_copy_preferences;
+
+ /* Similar to hard_reg_preferences, but includes bits for subsequent
+ registers when an allocno is multi-word. The above variable is used for
+ allocation while this is used to build reg_someone_prefers, below. */
+
+ HARD_REG_SET hard_reg_full_preferences;
+
+ /* Set of hard registers that some later allocno has a preference for. */
+
+ HARD_REG_SET regs_someone_prefers;
+};
+
+static struct allocno *allocno;
/* A vector of the integers from 0 to max_allocno-1,
sorted in the order of first-to-be-allocated first. */
static int *allocno_order;
-/* Indexed by an allocno, gives the number of consecutive
- hard registers needed by that pseudo reg. */
-
-static int *allocno_size;
-
/* Indexed by (pseudo) reg number, gives the number of another
lower-numbered pseudo reg which can share a hard reg with this pseudo
*even if the two pseudos would otherwise appear to conflict*. */
recording whether two allocno's conflict (can't go in the same
hardware register).
- `conflicts' is not symmetric; a conflict between allocno's i and j
- is recorded either in element i,j or in element j,i. */
+ `conflicts' is symmetric after the call to mirror_conflicts. */
static INT_TYPE *conflicts;
/* Two macros to test or store 1 in an element of `conflicts'. */
#define CONFLICTP(I, J) \
- (conflicts[(I) * allocno_row_words + (J) / INT_BITS] \
- & ((INT_TYPE) 1 << ((J) % INT_BITS)))
+ (conflicts[(I) * allocno_row_words + (unsigned)(J) / INT_BITS] \
+ & ((INT_TYPE) 1 << ((unsigned)(J) % INT_BITS)))
#define SET_CONFLICT(I, J) \
- (conflicts[(I) * allocno_row_words + (J) / INT_BITS] \
- |= ((INT_TYPE) 1 << ((J) % INT_BITS)))
+ (conflicts[(I) * allocno_row_words + (unsigned)(J) / INT_BITS] \
+ |= ((INT_TYPE) 1 << ((unsigned)(J) % INT_BITS)))
+
+/* For any allocno set in ALLOCNO_SET, set ALLOCNO to that allocno,
+ and execute CODE. */
+#define EXECUTE_IF_SET_IN_ALLOCNO_SET(ALLOCNO_SET, ALLOCNO, CODE) \
+do { \
+ int i_; \
+ int allocno_; \
+ INT_TYPE *p_ = (ALLOCNO_SET); \
+ \
+ for (i_ = allocno_row_words - 1, allocno_ = 0; i_ >= 0; \
+ i_--, allocno_ += INT_BITS) \
+ { \
+ unsigned INT_TYPE word_ = (unsigned INT_TYPE) *p_++; \
+ \
+ for ((ALLOCNO) = allocno_; word_; word_ >>= 1, (ALLOCNO)++) \
+ { \
+ if (word_ & 1) \
+ {CODE;} \
+ } \
+ } \
+} while (0)
+
+/* This doesn't work for non-GNU C due to the way CODE is macro expanded. */
+#if 0
+/* For any allocno that conflicts with IN_ALLOCNO, set OUT_ALLOCNO to
+ the conflicting allocno, and execute CODE. This macro assumes that
+ mirror_conflicts has been run. */
+#define EXECUTE_IF_CONFLICT(IN_ALLOCNO, OUT_ALLOCNO, CODE)\
+ EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts + (IN_ALLOCNO) * allocno_row_words,\
+ OUT_ALLOCNO, (CODE))
+#endif
/* Set of hard regs currently live (during scan of all insns). */
static HARD_REG_SET hard_regs_live;
-/* Indexed by N, set of hard regs conflicting with allocno N. */
-
-static HARD_REG_SET *hard_reg_conflicts;
-
-/* Indexed by N, set of hard regs preferred by allocno N.
- This is used to make allocnos go into regs that are copied to or from them,
- when possible, to reduce register shuffling. */
-
-static HARD_REG_SET *hard_reg_preferences;
-
-/* Similar, but just counts register preferences made in simple copy
- operations, rather than arithmetic. These are given priority because
- we can always eliminate an insn by using these, but using a register
- in the above list won't always eliminate an insn. */
-
-static HARD_REG_SET *hard_reg_copy_preferences;
-
-/* Similar to hard_reg_preferences, but includes bits for subsequent
- registers when an allocno is multi-word. The above variable is used for
- allocation while this is used to build reg_someone_prefers, below. */
-
-static HARD_REG_SET *hard_reg_full_preferences;
-
-/* Indexed by N, set of hard registers that some later allocno has a
- preference for. */
-
-static HARD_REG_SET *regs_someone_prefers;
-
/* Set of registers that global-alloc isn't supposed to use. */
static HARD_REG_SET no_global_alloc_regs;
static HARD_REG_SET regs_used_so_far;
-/* Number of calls crossed by each allocno. */
-
-static int *allocno_calls_crossed;
-
-/* Number of refs (weighted) to each allocno. */
-
-static int *allocno_n_refs;
-
-/* Guess at live length of each allocno.
- This is actually the max of the live lengths of the regs. */
-
-static int *allocno_live_length;
-
/* Number of refs (weighted) to each hard reg, as used by local alloc.
It is zero for a reg that contains global pseudos or is explicitly used. */
/* Test a bit in TABLE, a vector of HARD_REG_SETs,
for vector element I, and hard register number J. */
-#define REGBITP(TABLE, I, J) TEST_HARD_REG_BIT (TABLE[I], J)
+#define REGBITP(TABLE, I, J) TEST_HARD_REG_BIT (allocno[I].TABLE, J)
/* Set to 1 a bit in a vector of HARD_REG_SETs. Works like REGBITP. */
-#define SET_REGBIT(TABLE, I, J) SET_HARD_REG_BIT (TABLE[I], J)
+#define SET_REGBIT(TABLE, I, J) SET_HARD_REG_BIT (allocno[I].TABLE, J)
/* Bit mask for allocnos live at current point in the scan. */
/* Test, set or clear bit number I in allocnos_live,
a bit vector indexed by allocno. */
-#define ALLOCNO_LIVE_P(I) \
- (allocnos_live[(I) / INT_BITS] & ((INT_TYPE) 1 << ((I) % INT_BITS)))
+#define ALLOCNO_LIVE_P(I) \
+ (allocnos_live[(unsigned)(I) / INT_BITS] \
+ & ((INT_TYPE) 1 << ((unsigned)(I) % INT_BITS)))
-#define SET_ALLOCNO_LIVE(I) \
- (allocnos_live[(I) / INT_BITS] |= ((INT_TYPE) 1 << ((I) % INT_BITS)))
+#define SET_ALLOCNO_LIVE(I) \
+ (allocnos_live[(unsigned)(I) / INT_BITS] \
+ |= ((INT_TYPE) 1 << ((unsigned)(I) % INT_BITS)))
-#define CLEAR_ALLOCNO_LIVE(I) \
- (allocnos_live[(I) / INT_BITS] &= ~((INT_TYPE) 1 << ((I) % INT_BITS)))
+#define CLEAR_ALLOCNO_LIVE(I) \
+ (allocnos_live[(unsigned)(I) / INT_BITS] \
+ &= ~((INT_TYPE) 1 << ((unsigned)(I) % INT_BITS)))
/* This is turned off because it doesn't work right for DImode.
(And it is only used for DImode, so the other cases are worthless.)
static HARD_REG_SET eliminable_regset;
-static int allocno_compare PROTO((const PTR, const PTR));
-static void global_conflicts PROTO((void));
-static void expand_preferences PROTO((void));
-static void prune_preferences PROTO((void));
-static void find_reg PROTO((int, HARD_REG_SET, int, int, int));
-static void record_one_conflict PROTO((int));
-static void record_conflicts PROTO((int *, int));
-static void mark_reg_store PROTO((rtx, rtx, void *));
-static void mark_reg_clobber PROTO((rtx, rtx, void *));
-static void mark_reg_conflicts PROTO((rtx));
-static void mark_reg_death PROTO((rtx));
-static void mark_reg_live_nc PROTO((int, enum machine_mode));
-static void set_preference PROTO((rtx, rtx));
-static void dump_conflicts PROTO((FILE *));
-static void reg_becomes_live PROTO((rtx, rtx, void *));
-static void reg_dies PROTO((int, enum machine_mode));
-static void build_insn_chain PROTO((rtx));
+static int allocno_compare PARAMS ((const PTR, const PTR));
+static void global_conflicts PARAMS ((void));
+static void mirror_conflicts PARAMS ((void));
+static void expand_preferences PARAMS ((void));
+static void prune_preferences PARAMS ((void));
+static void find_reg PARAMS ((int, HARD_REG_SET, int, int, int));
+static void record_one_conflict PARAMS ((int));
+static void record_conflicts PARAMS ((int *, int));
+static void mark_reg_store PARAMS ((rtx, rtx, void *));
+static void mark_reg_clobber PARAMS ((rtx, rtx, void *));
+static void mark_reg_conflicts PARAMS ((rtx));
+static void mark_reg_death PARAMS ((rtx));
+static void mark_reg_live_nc PARAMS ((int, enum machine_mode));
+static void set_preference PARAMS ((rtx, rtx));
+static void dump_conflicts PARAMS ((FILE *));
+static void reg_becomes_live PARAMS ((rtx, rtx, void *));
+static void reg_dies PARAMS ((int, enum machine_mode,
+ struct insn_chain *));
\f
/* Perform allocation of pseudo-registers not allocated by local_alloc.
FILE is a file to output debugging information on,
are safe to use only within a basic block. */
CLEAR_HARD_REG_SET (no_global_alloc_regs);
-#ifdef OVERLAPPING_REGNO_P
- for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
- if (OVERLAPPING_REGNO_P (i))
- SET_HARD_REG_BIT (no_global_alloc_regs, i);
-#endif
/* Build the regset of all eliminable registers and show we can't use those
that we already know won't be eliminated. */
a leaf function. */
{
char *cheap_regs;
- static char leaf_regs[] = LEAF_REGISTERS;
+ char *leaf_regs = LEAF_REGISTERS;
if (only_leaf_regs_used () && leaf_function_p ())
cheap_regs = leaf_regs;
/* Establish mappings from register number to allocation number
and vice versa. In the process, count the allocnos. */
- reg_allocno = (int *) alloca (max_regno * sizeof (int));
+ reg_allocno = (int *) xmalloc (max_regno * sizeof (int));
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
reg_allocno[i] = -1;
/* Initialize the shared-hard-reg mapping
from the list of pairs that may share. */
- reg_may_share = (int *) alloca (max_regno * sizeof (int));
- bzero ((char *) reg_may_share, max_regno * sizeof (int));
+ reg_may_share = (int *) xcalloc (max_regno, sizeof (int));
for (x = regs_may_share; x; x = XEXP (XEXP (x, 1), 1))
{
int r1 = REGNO (XEXP (x, 0));
else
reg_allocno[i] = -1;
- allocno_reg = (int *) alloca (max_allocno * sizeof (int));
- allocno_size = (int *) alloca (max_allocno * sizeof (int));
- allocno_calls_crossed = (int *) alloca (max_allocno * sizeof (int));
- allocno_n_refs = (int *) alloca (max_allocno * sizeof (int));
- allocno_live_length = (int *) alloca (max_allocno * sizeof (int));
- bzero ((char *) allocno_size, max_allocno * sizeof (int));
- bzero ((char *) allocno_calls_crossed, max_allocno * sizeof (int));
- bzero ((char *) allocno_n_refs, max_allocno * sizeof (int));
- bzero ((char *) allocno_live_length, max_allocno * sizeof (int));
+ allocno = (struct allocno *) xcalloc (max_allocno, sizeof (struct allocno));
for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
if (reg_allocno[i] >= 0)
{
- int allocno = reg_allocno[i];
- allocno_reg[allocno] = i;
- allocno_size[allocno] = PSEUDO_REGNO_SIZE (i);
- allocno_calls_crossed[allocno] += REG_N_CALLS_CROSSED (i);
- allocno_n_refs[allocno] += REG_N_REFS (i);
- if (allocno_live_length[allocno] < REG_LIVE_LENGTH (i))
- allocno_live_length[allocno] = REG_LIVE_LENGTH (i);
+ int num = reg_allocno[i];
+ allocno[num].reg = i;
+ allocno[num].size = PSEUDO_REGNO_SIZE (i);
+ allocno[num].calls_crossed += REG_N_CALLS_CROSSED (i);
+ allocno[num].n_refs += REG_N_REFS (i);
+ if (allocno[num].live_length < REG_LIVE_LENGTH (i))
+ allocno[num].live_length = REG_LIVE_LENGTH (i);
}
/* Calculate amount of usage of each hard reg by pseudos
if (regs_ever_live[i])
local_reg_n_refs[i] = 0;
- /* Allocate the space for the conflict and preference tables and
- initialize them. */
-
- hard_reg_conflicts
- = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
- bzero ((char *) hard_reg_conflicts, max_allocno * sizeof (HARD_REG_SET));
-
- hard_reg_preferences
- = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
- bzero ((char *) hard_reg_preferences, max_allocno * sizeof (HARD_REG_SET));
-
- hard_reg_copy_preferences
- = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
- bzero ((char *) hard_reg_copy_preferences,
- max_allocno * sizeof (HARD_REG_SET));
-
- hard_reg_full_preferences
- = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
- bzero ((char *) hard_reg_full_preferences,
- max_allocno * sizeof (HARD_REG_SET));
-
- regs_someone_prefers
- = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
- bzero ((char *) regs_someone_prefers, max_allocno * sizeof (HARD_REG_SET));
-
allocno_row_words = (max_allocno + INT_BITS - 1) / INT_BITS;
/* We used to use alloca here, but the size of what it would try to
conflicts = (INT_TYPE *) xcalloc (max_allocno * allocno_row_words,
sizeof (INT_TYPE));
- allocnos_live = (INT_TYPE *) alloca (allocno_row_words * sizeof (INT_TYPE));
+ allocnos_live = (INT_TYPE *) xmalloc (allocno_row_words * sizeof (INT_TYPE));
/* If there is work to be done (at least one reg to allocate),
perform global conflict analysis and allocate the regs. */
global_conflicts ();
+ mirror_conflicts ();
+
/* Eliminate conflicts between pseudos and eliminable registers. If
the register is not eliminated, the pseudo won't really be able to
live in the eliminable register, so the conflict doesn't matter.
for (i = 0; i < (size_t) max_allocno; i++)
{
- AND_COMPL_HARD_REG_SET (hard_reg_conflicts[i], eliminable_regset);
- AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences[i],
+ AND_COMPL_HARD_REG_SET (allocno[i].hard_reg_conflicts,
+ eliminable_regset);
+ AND_COMPL_HARD_REG_SET (allocno[i].hard_reg_copy_preferences,
+ eliminable_regset);
+ AND_COMPL_HARD_REG_SET (allocno[i].hard_reg_preferences,
eliminable_regset);
- AND_COMPL_HARD_REG_SET (hard_reg_preferences[i], eliminable_regset);
}
/* Try to expand the preferences by merging them between allocnos. */
/* Determine the order to allocate the remaining pseudo registers. */
- allocno_order = (int *) alloca (max_allocno * sizeof (int));
+ allocno_order = (int *) xmalloc (max_allocno * sizeof (int));
for (i = 0; i < (size_t) max_allocno; i++)
allocno_order[i] = i;
for (i = 0; i < (size_t) max_allocno; i++)
{
- if (allocno_size[i] == 0)
- allocno_size[i] = 1;
- if (allocno_live_length[i] == 0)
- allocno_live_length[i] = -1;
+ if (allocno[i].size == 0)
+ allocno[i].size = 1;
+ if (allocno[i].live_length == 0)
+ allocno[i].live_length = -1;
}
qsort (allocno_order, max_allocno, sizeof (int), allocno_compare);
except for parameters marked with reg_live_length[regno] == -2. */
for (i = 0; i < (size_t) max_allocno; i++)
- if (reg_renumber[allocno_reg[allocno_order[i]]] < 0
- && REG_LIVE_LENGTH (allocno_reg[allocno_order[i]]) >= 0)
+ if (reg_renumber[allocno[allocno_order[i]].reg] < 0
+ && REG_LIVE_LENGTH (allocno[allocno_order[i]].reg) >= 0)
{
/* If we have more than one register class,
first try allocating in the class that is cheapest
if (N_REG_CLASSES > 1)
{
find_reg (allocno_order[i], 0, 0, 0, 0);
- if (reg_renumber[allocno_reg[allocno_order[i]]] >= 0)
+ if (reg_renumber[allocno[allocno_order[i]].reg] >= 0)
continue;
}
- if (reg_alternate_class (allocno_reg[allocno_order[i]]) != NO_REGS)
+ if (reg_alternate_class (allocno[allocno_order[i]].reg) != NO_REGS)
find_reg (allocno_order[i], 0, 1, 0, 0);
}
+
+ free (allocno_order);
}
/* Do the reloads now while the allocno data still exist, so that we can
retval = reload (get_insns (), 1, file);
}
+ /* Clean up. */
+ free (reg_allocno);
+ free (reg_may_share);
+ free (allocno);
free (conflicts);
+ free (allocnos_live);
+
return retval;
}
times a register can occur in one insn (surely less than 100).
Multiplying this by 10000 can't overflow. */
register int pri1
- = (((double) (floor_log2 (allocno_n_refs[v1]) * allocno_n_refs[v1])
- / allocno_live_length[v1])
- * 10000 * allocno_size[v1]);
+ = (((double) (floor_log2 (allocno[v1].n_refs) * allocno[v1].n_refs)
+ / allocno[v1].live_length)
+ * 10000 * allocno[v1].size);
register int pri2
- = (((double) (floor_log2 (allocno_n_refs[v2]) * allocno_n_refs[v2])
- / allocno_live_length[v2])
- * 10000 * allocno_size[v2]);
+ = (((double) (floor_log2 (allocno[v2].n_refs) * allocno[v2].n_refs)
+ / allocno[v2].live_length)
+ * 10000 * allocno[v2].size);
if (pri2 - pri1)
return pri2 - pri1;
int *block_start_allocnos;
/* Make a vector that mark_reg_{store,clobber} will store in. */
- regs_set = (rtx *) alloca (max_parallel * sizeof (rtx) * 2);
+ regs_set = (rtx *) xmalloc (max_parallel * sizeof (rtx) * 2);
- block_start_allocnos = (int *) alloca (max_allocno * sizeof (int));
+ block_start_allocnos = (int *) xmalloc (max_allocno * sizeof (int));
for (b = 0; b < n_basic_blocks; b++)
{
/* Initialize table of registers currently live
to the state at the beginning of this basic block.
- This also marks the conflicts among them.
+ This also marks the conflicts among hard registers
+ and any allocnos that are live.
For pseudo-regs, there is only one bit for each one
no matter how many hard regs it occupies.
(a, PSEUDO_REGNO_MODE (i));
});
- /* Record that each allocno now live conflicts with each other
- allocno now live, and with each hard reg now live. */
+ /* Record that each allocno now live conflicts with each hard reg
+ now live.
+
+ It is not necessary to mark any conflicts between pseudos as
+ this point, even for pseudos which are live at the start of
+ the basic block.
+
+ Given two pseudos X and Y and any point in the CFG P.
+
+ On any path to point P where X and Y are live one of the
+ following conditions must be true:
+ 1. X is live at some instruction on the path that
+ evaluates Y.
+
+ 2. Y is live at some instruction on the path that
+ evaluates X.
+
+ 3. Either X or Y is not evaluted on the path to P
+ (ie it is used uninitialized) and thus the
+ conflict can be ignored.
+
+ In cases #1 and #2 the conflict will be recorded when we
+ scan the instruction that makes either X or Y become live. */
record_conflicts (block_start_allocnos, ax);
#ifdef STACK_REGS
insn = NEXT_INSN (insn);
}
}
+
+ /* Clean up. */
+ free (block_start_allocnos);
+ free (regs_set);
}
/* Expand the preference information by looking for cases where one allocno
dies in an insn that sets an allocno. If those two allocnos don't conflict,
&& GET_CODE (XEXP (link, 0)) == REG
&& reg_allocno[REGNO (XEXP (link, 0))] >= 0
&& ! CONFLICTP (reg_allocno[REGNO (SET_DEST (set))],
- reg_allocno[REGNO (XEXP (link, 0))])
- && ! CONFLICTP (reg_allocno[REGNO (XEXP (link, 0))],
- reg_allocno[REGNO (SET_DEST (set))]))
+ reg_allocno[REGNO (XEXP (link, 0))]))
{
int a1 = reg_allocno[REGNO (SET_DEST (set))];
int a2 = reg_allocno[REGNO (XEXP (link, 0))];
if (XEXP (link, 0) == SET_SRC (set))
{
- IOR_HARD_REG_SET (hard_reg_copy_preferences[a1],
- hard_reg_copy_preferences[a2]);
- IOR_HARD_REG_SET (hard_reg_copy_preferences[a2],
- hard_reg_copy_preferences[a1]);
+ IOR_HARD_REG_SET (allocno[a1].hard_reg_copy_preferences,
+ allocno[a2].hard_reg_copy_preferences);
+ IOR_HARD_REG_SET (allocno[a2].hard_reg_copy_preferences,
+ allocno[a1].hard_reg_copy_preferences);
}
- IOR_HARD_REG_SET (hard_reg_preferences[a1],
- hard_reg_preferences[a2]);
- IOR_HARD_REG_SET (hard_reg_preferences[a2],
- hard_reg_preferences[a1]);
- IOR_HARD_REG_SET (hard_reg_full_preferences[a1],
- hard_reg_full_preferences[a2]);
- IOR_HARD_REG_SET (hard_reg_full_preferences[a2],
- hard_reg_full_preferences[a1]);
+ IOR_HARD_REG_SET (allocno[a1].hard_reg_preferences,
+ allocno[a2].hard_reg_preferences);
+ IOR_HARD_REG_SET (allocno[a2].hard_reg_preferences,
+ allocno[a1].hard_reg_preferences);
+ IOR_HARD_REG_SET (allocno[a1].hard_reg_full_preferences,
+ allocno[a2].hard_reg_full_preferences);
+ IOR_HARD_REG_SET (allocno[a2].hard_reg_full_preferences,
+ allocno[a1].hard_reg_full_preferences);
}
}
\f
static void
prune_preferences ()
{
- int i, j;
- int allocno;
+ int i;
+ int num;
+ int *allocno_to_order = (int *) xmalloc (max_allocno * sizeof (int));
/* Scan least most important to most important.
For each allocno, remove from preferences registers that cannot be used,
for (i = max_allocno - 1; i >= 0; i--)
{
- HARD_REG_SET temp, temp2;
+ HARD_REG_SET temp;
- allocno = allocno_order[i];
- COPY_HARD_REG_SET (temp, hard_reg_conflicts[allocno]);
+ num = allocno_order[i];
+ allocno_to_order[num] = i;
+ COPY_HARD_REG_SET (temp, allocno[num].hard_reg_conflicts);
- if (allocno_calls_crossed[allocno] == 0)
+ if (allocno[num].calls_crossed == 0)
IOR_HARD_REG_SET (temp, fixed_reg_set);
else
IOR_HARD_REG_SET (temp, call_used_reg_set);
IOR_COMPL_HARD_REG_SET
(temp,
- reg_class_contents[(int) reg_preferred_class (allocno_reg[allocno])]);
+ reg_class_contents[(int) reg_preferred_class (allocno[num].reg)]);
- AND_COMPL_HARD_REG_SET (hard_reg_preferences[allocno], temp);
- AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences[allocno], temp);
- AND_COMPL_HARD_REG_SET (hard_reg_full_preferences[allocno], temp);
+ AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_preferences, temp);
+ AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_copy_preferences, temp);
+ AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_full_preferences, temp);
+ }
+ for (i = max_allocno - 1; i >= 0; i--)
+ {
/* Merge in the preferences of lower-priority registers (they have
already been pruned). If we also prefer some of those registers,
don't exclude them unless we are of a smaller size (in which case
we want to give the lower-priority allocno the first chance for
these registers). */
+ HARD_REG_SET temp, temp2;
+ int allocno2;
+
+ num = allocno_order[i];
+
CLEAR_HARD_REG_SET (temp);
CLEAR_HARD_REG_SET (temp2);
- for (j = i + 1; j < max_allocno; j++)
- if (CONFLICTP (allocno, allocno_order[j])
- || CONFLICTP (allocno_order[j], allocno))
- {
- if (allocno_size[allocno_order[j]] <= allocno_size[allocno])
- IOR_HARD_REG_SET (temp,
- hard_reg_full_preferences[allocno_order[j]]);
- else
- IOR_HARD_REG_SET (temp2,
- hard_reg_full_preferences[allocno_order[j]]);
- }
- AND_COMPL_HARD_REG_SET (temp, hard_reg_full_preferences[allocno]);
+
+ EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts + num * allocno_row_words,
+ allocno2,
+ {
+ if (allocno_to_order[allocno2] > i)
+ {
+ if (allocno[allocno2].size <= allocno[num].size)
+ IOR_HARD_REG_SET (temp,
+ allocno[allocno2].hard_reg_full_preferences);
+ else
+ IOR_HARD_REG_SET (temp2,
+ allocno[allocno2].hard_reg_full_preferences);
+ }
+ });
+
+ AND_COMPL_HARD_REG_SET (temp, allocno[num].hard_reg_full_preferences);
IOR_HARD_REG_SET (temp, temp2);
- COPY_HARD_REG_SET (regs_someone_prefers[allocno], temp);
+ COPY_HARD_REG_SET (allocno[num].regs_someone_prefers, temp);
}
+ free (allocno_to_order);
}
\f
-/* Assign a hard register to ALLOCNO; look for one that is the beginning
+/* Assign a hard register to allocno NUM; look for one that is the beginning
of a long enough stretch of hard regs none of which conflicts with ALLOCNO.
The registers marked in PREFREGS are tried first.
If not, do nothing. */
static void
-find_reg (allocno, losers, alt_regs_p, accept_call_clobbered, retrying)
- int allocno;
+find_reg (num, losers, alt_regs_p, accept_call_clobbered, retrying)
+ int num;
HARD_REG_SET losers;
int alt_regs_p;
int accept_call_clobbered;
HARD_REG_SET used, used1, used2;
enum reg_class class = (alt_regs_p
- ? reg_alternate_class (allocno_reg[allocno])
- : reg_preferred_class (allocno_reg[allocno]));
- enum machine_mode mode = PSEUDO_REGNO_MODE (allocno_reg[allocno]);
+ ? reg_alternate_class (allocno[num].reg)
+ : reg_preferred_class (allocno[num].reg));
+ enum machine_mode mode = PSEUDO_REGNO_MODE (allocno[num].reg);
if (accept_call_clobbered)
COPY_HARD_REG_SET (used1, call_fixed_reg_set);
- else if (allocno_calls_crossed[allocno] == 0)
+ else if (allocno[num].calls_crossed == 0)
COPY_HARD_REG_SET (used1, fixed_reg_set);
else
COPY_HARD_REG_SET (used1, call_used_reg_set);
IOR_COMPL_HARD_REG_SET (used1, reg_class_contents[(int) class]);
COPY_HARD_REG_SET (used2, used1);
- IOR_HARD_REG_SET (used1, hard_reg_conflicts[allocno]);
+ IOR_HARD_REG_SET (used1, allocno[num].hard_reg_conflicts);
-#ifdef CLASS_CANNOT_CHANGE_SIZE
- if (REG_CHANGES_SIZE (allocno_reg[allocno]))
+#ifdef CLASS_CANNOT_CHANGE_MODE
+ if (REG_CHANGES_MODE (allocno[num].reg))
IOR_HARD_REG_SET (used1,
- reg_class_contents[(int) CLASS_CANNOT_CHANGE_SIZE]);
+ reg_class_contents[(int) CLASS_CANNOT_CHANGE_MODE]);
#endif
/* Try each hard reg to see if it fits. Do this in two passes.
COPY_HARD_REG_SET (used, used1);
IOR_COMPL_HARD_REG_SET (used, regs_used_so_far);
- IOR_HARD_REG_SET (used, regs_someone_prefers[allocno]);
+ IOR_HARD_REG_SET (used, allocno[num].regs_someone_prefers);
best_reg = -1;
for (i = FIRST_PSEUDO_REGISTER, pass = 0;
#endif
if (! TEST_HARD_REG_BIT (used, regno)
&& HARD_REGNO_MODE_OK (regno, mode)
- && (allocno_calls_crossed[allocno] == 0
+ && (allocno[num].calls_crossed == 0
|| accept_call_clobbered
|| ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode)))
{
First do this for those register with copy preferences, then all
preferred registers. */
- AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences[allocno], used);
- GO_IF_HARD_REG_SUBSET (hard_reg_copy_preferences[allocno],
+ AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_copy_preferences, used);
+ GO_IF_HARD_REG_SUBSET (allocno[num].hard_reg_copy_preferences,
reg_class_contents[(int) NO_REGS], no_copy_prefs);
if (best_reg >= 0)
{
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
- if (TEST_HARD_REG_BIT (hard_reg_copy_preferences[allocno], i)
+ if (TEST_HARD_REG_BIT (allocno[num].hard_reg_copy_preferences, i)
&& HARD_REGNO_MODE_OK (i, mode)
&& (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
|| reg_class_subset_p (REGNO_REG_CLASS (i),
}
no_copy_prefs:
- AND_COMPL_HARD_REG_SET (hard_reg_preferences[allocno], used);
- GO_IF_HARD_REG_SUBSET (hard_reg_preferences[allocno],
+ AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_preferences, used);
+ GO_IF_HARD_REG_SUBSET (allocno[num].hard_reg_preferences,
reg_class_contents[(int) NO_REGS], no_prefs);
if (best_reg >= 0)
{
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
- if (TEST_HARD_REG_BIT (hard_reg_preferences[allocno], i)
+ if (TEST_HARD_REG_BIT (allocno[num].hard_reg_preferences, i)
&& HARD_REGNO_MODE_OK (i, mode)
&& (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
|| reg_class_subset_p (REGNO_REG_CLASS (i),
allocate a call-clobbered register and save and restore it
around calls, do that. */
if (! accept_call_clobbered
- && allocno_calls_crossed[allocno] != 0
- && CALLER_SAVE_PROFITABLE (allocno_n_refs[allocno],
- allocno_calls_crossed[allocno]))
+ && allocno[num].calls_crossed != 0
+ && CALLER_SAVE_PROFITABLE (allocno[num].n_refs,
+ allocno[num].calls_crossed))
{
HARD_REG_SET new_losers;
if (! losers)
COPY_HARD_REG_SET (new_losers, losers);
IOR_HARD_REG_SET(new_losers, losing_caller_save_reg_set);
- find_reg (allocno, new_losers, alt_regs_p, 1, retrying);
- if (reg_renumber[allocno_reg[allocno]] >= 0)
+ find_reg (num, new_losers, alt_regs_p, 1, retrying);
+ if (reg_renumber[allocno[num].reg] >= 0)
{
caller_save_needed = 1;
return;
so we can use it instead. */
if (best_reg < 0 && !retrying
/* Let's not bother with multi-reg allocnos. */
- && allocno_size[allocno] == 1)
+ && allocno[num].size == 1)
{
/* Count from the end, to find the least-used ones first. */
for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
/* Don't use a reg no good for this pseudo. */
&& ! TEST_HARD_REG_BIT (used2, regno)
&& HARD_REGNO_MODE_OK (regno, mode)
-#ifdef CLASS_CANNOT_CHANGE_SIZE
- && ! (REG_CHANGES_SIZE (allocno_reg[allocno])
+#ifdef CLASS_CANNOT_CHANGE_MODE
+ && ! (REG_CHANGES_MODE (allocno[num].reg)
&& (TEST_HARD_REG_BIT
- (reg_class_contents[(int) CLASS_CANNOT_CHANGE_SIZE],
+ (reg_class_contents[(int) CLASS_CANNOT_CHANGE_MODE],
regno)))
#endif
)
double tmp1 = ((double) local_reg_n_refs[regno]
/ local_reg_live_length[regno]);
- double tmp2 = ((double) allocno_n_refs[allocno]
- / allocno_live_length[allocno]);
+ double tmp2 = ((double) allocno[num].n_refs
+ / allocno[num].live_length);
if (tmp1 < tmp2)
{
HARD_REG_SET this_reg;
/* Yes. Record it as the hard register of this pseudo-reg. */
- reg_renumber[allocno_reg[allocno]] = best_reg;
+ reg_renumber[allocno[num].reg] = best_reg;
/* Also of any pseudo-regs that share with it. */
- if (reg_may_share[allocno_reg[allocno]])
+ if (reg_may_share[allocno[num].reg])
for (j = FIRST_PSEUDO_REGISTER; j < max_regno; j++)
- if (reg_allocno[j] == allocno)
+ if (reg_allocno[j] == num)
reg_renumber[j] = best_reg;
/* Make a set of the hard regs being allocated. */
}
/* For each other pseudo-reg conflicting with this one,
mark it as conflicting with the hard regs this one occupies. */
- lim = allocno;
- for (j = 0; j < max_allocno; j++)
- if (CONFLICTP (lim, j) || CONFLICTP (j, lim))
- {
- IOR_HARD_REG_SET (hard_reg_conflicts[j], this_reg);
- }
+ lim = num;
+ EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts + lim * allocno_row_words, j,
+ {
+ IOR_HARD_REG_SET (allocno[j].hard_reg_conflicts, this_reg);
+ });
}
}
\f
if (regno < FIRST_PSEUDO_REGISTER)
/* When a hard register becomes live,
record conflicts with live pseudo regs. */
- for (j = 0; j < max_allocno; j++)
+ EXECUTE_IF_SET_IN_ALLOCNO_SET (allocnos_live, j,
{
- if (ALLOCNO_LIVE_P (j))
- SET_HARD_REG_BIT (hard_reg_conflicts[j], regno);
- }
+ SET_HARD_REG_BIT (allocno[j].hard_reg_conflicts, regno);
+ });
else
/* When a pseudo-register becomes live,
record conflicts first with hard regs,
{
register int ialloc = reg_allocno[regno];
register int ialloc_prod = ialloc * allocno_row_words;
- IOR_HARD_REG_SET (hard_reg_conflicts[ialloc], hard_regs_live);
+ IOR_HARD_REG_SET (allocno[ialloc].hard_reg_conflicts, hard_regs_live);
for (j = allocno_row_words - 1; j >= 0; j--)
{
#if 0
}
/* Record all allocnos currently live as conflicting
- with each other and with all hard regs currently live.
+ with all hard regs currently live.
+
ALLOCNO_VEC is a vector of LEN allocnos, all allocnos that
are currently live. Their bits are also flagged in allocnos_live. */
register int *allocno_vec;
register int len;
{
- register int allocno;
- register int j;
+ register int num;
register int ialloc_prod;
while (--len >= 0)
{
- allocno = allocno_vec[len];
- ialloc_prod = allocno * allocno_row_words;
- IOR_HARD_REG_SET (hard_reg_conflicts[allocno], hard_regs_live);
- for (j = allocno_row_words - 1; j >= 0; j--)
- conflicts[ialloc_prod + j] |= allocnos_live[j];
+ num = allocno_vec[len];
+ ialloc_prod = num * allocno_row_words;
+ IOR_HARD_REG_SET (allocno[num].hard_reg_conflicts, hard_regs_live);
+ }
+}
+
+/* If CONFLICTP (i, j) is true, make sure CONFLICTP (j, i) is also true. */
+static void
+mirror_conflicts ()
+{
+ register int i, j;
+ int rw = allocno_row_words;
+ int rwb = rw * INT_BITS;
+ INT_TYPE *p = conflicts;
+ INT_TYPE *q0 = conflicts, *q1, *q2;
+ unsigned INT_TYPE mask;
+
+ for (i = max_allocno - 1, mask = 1; i >= 0; i--, mask <<= 1)
+ {
+ if (! mask)
+ {
+ mask = 1;
+ q0++;
+ }
+ for (j = allocno_row_words - 1, q1 = q0; j >= 0; j--, q1 += rwb)
+ {
+ unsigned INT_TYPE word;
+
+ for (word = (unsigned INT_TYPE) *p++, q2 = q1; word;
+ word >>= 1, q2 += rw)
+ {
+ if (word & 1)
+ *q2 |= mask;
+ }
+ }
}
}
\f
set_preference (dest, src)
rtx dest, src;
{
- int src_regno, dest_regno;
+ unsigned int src_regno, dest_regno;
/* Amount to add to the hard regno for SRC, or subtract from that for DEST,
to compensate for subregs in SRC or DEST. */
int offset = 0;
- int i;
+ unsigned int i;
int copy = 1;
if (GET_RTX_FORMAT (GET_CODE (src))[0] == 'e')
&& reg_allocno[src_regno] >= 0)
{
dest_regno -= offset;
- if (dest_regno >= 0 && dest_regno < FIRST_PSEUDO_REGISTER)
+ if (dest_regno < FIRST_PSEUDO_REGISTER)
{
if (copy)
SET_REGBIT (hard_reg_copy_preferences,
&& reg_allocno[dest_regno] >= 0)
{
src_regno += offset;
- if (src_regno >= 0 && src_regno < FIRST_PSEUDO_REGISTER)
+ if (src_regno < FIRST_PSEUDO_REGISTER)
{
if (copy)
SET_REGBIT (hard_reg_copy_preferences,
current life information. */
static regset live_relevant_regs;
-/* Record in live_relevant_regs that register REG became live. This
- is called via note_stores. */
+/* Record in live_relevant_regs and REGS_SET that register REG became live.
+ This is called via note_stores. */
static void
-reg_becomes_live (reg, setter, data)
+reg_becomes_live (reg, setter, regs_set)
rtx reg;
rtx setter ATTRIBUTE_UNUSED;
- void *data ATTRIBUTE_UNUSED;
+ void *regs_set;
{
int regno;
{
int nregs = HARD_REGNO_NREGS (regno, GET_MODE (reg));
while (nregs-- > 0)
- SET_REGNO_REG_SET (live_relevant_regs, regno++);
+ {
+ SET_REGNO_REG_SET (live_relevant_regs, regno);
+ if (! fixed_regs[regno])
+ SET_REGNO_REG_SET ((regset) regs_set, regno);
+ regno++;
+ }
}
else if (reg_renumber[regno] >= 0)
- SET_REGNO_REG_SET (live_relevant_regs, regno);
+ {
+ SET_REGNO_REG_SET (live_relevant_regs, regno);
+ SET_REGNO_REG_SET ((regset) regs_set, regno);
+ }
}
/* Record in live_relevant_regs that register REGNO died. */
static void
-reg_dies (regno, mode)
+reg_dies (regno, mode, chain)
int regno;
enum machine_mode mode;
+ struct insn_chain *chain;
{
if (regno < FIRST_PSEUDO_REGISTER)
{
int nregs = HARD_REGNO_NREGS (regno, mode);
while (nregs-- > 0)
- CLEAR_REGNO_REG_SET (live_relevant_regs, regno++);
+ {
+ CLEAR_REGNO_REG_SET (live_relevant_regs, regno);
+ if (! fixed_regs[regno])
+ SET_REGNO_REG_SET (&chain->dead_or_set, regno);
+ regno++;
+ }
}
else
- CLEAR_REGNO_REG_SET (live_relevant_regs, regno);
+ {
+ CLEAR_REGNO_REG_SET (live_relevant_regs, regno);
+ if (reg_renumber[regno] >= 0)
+ SET_REGNO_REG_SET (&chain->dead_or_set, regno);
+ }
}
/* Walk the insns of the current function and build reload_insn_chain,
and record register life information. */
-static void
+void
build_insn_chain (first)
rtx first;
{
struct insn_chain **p = &reload_insn_chain;
struct insn_chain *prev = 0;
int b = 0;
+ regset_head live_relevant_regs_head;
- live_relevant_regs = ALLOCA_REG_SET ();
+ live_relevant_regs = INITIALIZE_REG_SET (live_relevant_regs_head);
for (; first; first = NEXT_INSN (first))
{
if (first == BLOCK_HEAD (b))
{
int i;
+
CLEAR_REG_SET (live_relevant_regs);
- for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
- if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start, i)
- && ! TEST_HARD_REG_BIT (eliminable_regset, i))
- SET_REGNO_REG_SET (live_relevant_regs, i);
-
- for (; i < max_regno; i++)
- if (reg_renumber[i] >= 0
- && REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start, i))
- SET_REGNO_REG_SET (live_relevant_regs, i);
- }
+
+ EXECUTE_IF_SET_IN_BITMAP
+ (BASIC_BLOCK (b)->global_live_at_start, 0, i,
+ {
+ if (i < FIRST_PSEUDO_REGISTER
+ ? ! TEST_HARD_REG_BIT (eliminable_regset, i)
+ : reg_renumber[i] >= 0)
+ SET_REGNO_REG_SET (live_relevant_regs, i);
+ });
+ }
if (GET_CODE (first) != NOTE && GET_CODE (first) != BARRIER)
{
c->insn = first;
c->block = b;
- COPY_REG_SET (c->live_before, live_relevant_regs);
-
if (GET_RTX_CLASS (GET_CODE (first)) == 'i')
{
rtx link;
for (link = REG_NOTES (first); link; link = XEXP (link, 1))
if (REG_NOTE_KIND (link) == REG_DEAD
&& GET_CODE (XEXP (link, 0)) == REG)
- reg_dies (REGNO (XEXP (link, 0)), GET_MODE (XEXP (link, 0)));
+ reg_dies (REGNO (XEXP (link, 0)), GET_MODE (XEXP (link, 0)),
+ c);
+
+ COPY_REG_SET (&c->live_throughout, live_relevant_regs);
/* Mark everything born in this instruction as live. */
- note_stores (PATTERN (first), reg_becomes_live, NULL);
+ note_stores (PATTERN (first), reg_becomes_live,
+ &c->dead_or_set);
}
-
- /* Remember which registers are live at the end of the insn, before
- killing those with REG_UNUSED notes. */
- COPY_REG_SET (c->live_after, live_relevant_regs);
+ else
+ COPY_REG_SET (&c->live_throughout, live_relevant_regs);
if (GET_RTX_CLASS (GET_CODE (first)) == 'i')
{
for (link = REG_NOTES (first); link; link = XEXP (link, 1))
if (REG_NOTE_KIND (link) == REG_UNUSED
&& GET_CODE (XEXP (link, 0)) == REG)
- reg_dies (REGNO (XEXP (link, 0)), GET_MODE (XEXP (link, 0)));
+ reg_dies (REGNO (XEXP (link, 0)), GET_MODE (XEXP (link, 0)),
+ c);
}
}
nregs = 0;
for (i = 0; i < max_allocno; i++)
{
- if (reg_renumber[allocno_reg[allocno_order[i]]] >= 0)
+ if (reg_renumber[allocno[allocno_order[i]].reg] >= 0)
continue;
nregs++;
}
for (i = 0; i < max_allocno; i++)
{
int j;
- if (reg_renumber[allocno_reg[allocno_order[i]]] >= 0)
+ if (reg_renumber[allocno[allocno_order[i]].reg] >= 0)
continue;
- fprintf (file, " %d", allocno_reg[allocno_order[i]]);
+ fprintf (file, " %d", allocno[allocno_order[i]].reg);
for (j = 0; j < max_regno; j++)
if (reg_allocno[j] == allocno_order[i]
- && j != allocno_reg[allocno_order[i]])
+ && j != allocno[allocno_order[i]].reg)
fprintf (file, "+%d", j);
- if (allocno_size[allocno_order[i]] != 1)
- fprintf (file, " (%d)", allocno_size[allocno_order[i]]);
+ if (allocno[allocno_order[i]].size != 1)
+ fprintf (file, " (%d)", allocno[allocno_order[i]].size);
}
fprintf (file, "\n");
for (i = 0; i < max_allocno; i++)
{
register int j;
- fprintf (file, ";; %d conflicts:", allocno_reg[i]);
+ fprintf (file, ";; %d conflicts:", allocno[i].reg);
for (j = 0; j < max_allocno; j++)
- if (CONFLICTP (i, j) || CONFLICTP (j, i))
- fprintf (file, " %d", allocno_reg[j]);
+ if (CONFLICTP (j, i))
+ fprintf (file, " %d", allocno[j].reg);
for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
- if (TEST_HARD_REG_BIT (hard_reg_conflicts[i], j))
+ if (TEST_HARD_REG_BIT (allocno[i].hard_reg_conflicts, j))
fprintf (file, " %d", j);
fprintf (file, "\n");
has_preferences = 0;
for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
- if (TEST_HARD_REG_BIT (hard_reg_preferences[i], j))
+ if (TEST_HARD_REG_BIT (allocno[i].hard_reg_preferences, j))
has_preferences = 1;
if (! has_preferences)
continue;
- fprintf (file, ";; %d preferences:", allocno_reg[i]);
+ fprintf (file, ";; %d preferences:", allocno[i].reg);
for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
- if (TEST_HARD_REG_BIT (hard_reg_preferences[i], j))
+ if (TEST_HARD_REG_BIT (allocno[i].hard_reg_preferences, j))
fprintf (file, " %d", j);
fprintf (file, "\n");
}
OSDN Git Service
