/* Allocate registers for pseudo-registers that span basic blocks.
- Copyright (C) 1987-1991 Free Software Foundation, Inc.
+ Copyright (C) 1987, 88, 91, 94, 96, 1997 Free Software Foundation, Inc.
This file is part of GNU CC.
You should have received a copy of the GNU General Public License
along with GNU CC; see the file COPYING. If not, write to
-the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
+the Free Software Foundation, 59 Temple Place - Suite 330,
+Boston, MA 02111-1307, USA. */
#include <stdio.h>
/* Indexed by (pseudo) reg number, gives the allocno, or -1
for pseudo registers already allocated by local_allocate. */
-static int *reg_allocno;
+int *reg_allocno;
/* Indexed by allocno, gives the reg number. */
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 peudo
+ lower-numbered pseudo reg which can share a hard reg with this pseudo
*even if the two pseudos would otherwise appear to conflict*. */
static int *reg_may_share;
+/* Define the number of bits in each element of `conflicts' and what
+ type that element has. We use the largest integer format on the
+ host machine. */
+
+#define INT_BITS HOST_BITS_PER_WIDE_INT
+#define INT_TYPE HOST_WIDE_INT
+
/* max_allocno by max_allocno array of bits,
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. */
-static int *conflicts;
+static INT_TYPE *conflicts;
/* Number of ints require to hold max_allocno bits.
This is the length of a row in `conflicts'. */
#define CONFLICTP(I, J) \
(conflicts[(I) * allocno_row_words + (J) / INT_BITS] \
- & (1 << ((J) % INT_BITS)))
+ & ((INT_TYPE) 1 << ((J) % INT_BITS)))
#define SET_CONFLICT(I, J) \
(conflicts[(I) * allocno_row_words + (J) / INT_BITS] \
- |= (1 << ((J) % INT_BITS)))
+ |= ((INT_TYPE) 1 << ((J) % INT_BITS)))
/* Set of hard regs currently live (during scan of all insns). */
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. */
+
+static int local_reg_n_refs[FIRST_PSEUDO_REGISTER];
+
+/* Guess at live length of each hard reg, as used by local alloc.
+ This is actually the sum of the live lengths of the specific regs. */
+
+static int local_reg_live_length[FIRST_PSEUDO_REGISTER];
+
/* Test a bit in TABLE, a vector of HARD_REG_SETs,
for vector element I, and hard register number J. */
/* Bit mask for allocnos live at current point in the scan. */
-static int *allocnos_live;
-
-#define INT_BITS HOST_BITS_PER_INT
+static INT_TYPE *allocnos_live;
/* 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] & (1 << ((I) % INT_BITS)))
+ (allocnos_live[(I) / INT_BITS] & ((INT_TYPE) 1 << ((I) % INT_BITS)))
#define SET_ALLOCNO_LIVE(I) \
- (allocnos_live[(I) / INT_BITS] |= (1 << ((I) % INT_BITS)))
+ (allocnos_live[(I) / INT_BITS] |= ((INT_TYPE) 1 << ((I) % INT_BITS)))
#define CLEAR_ALLOCNO_LIVE(I) \
- (allocnos_live[(I) / INT_BITS] &= ~(1 << ((I) % INT_BITS)))
+ (allocnos_live[(I) / INT_BITS] &= ~((INT_TYPE) 1 << ((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 rtx *regs_set;
static int n_regs_set;
-/* All register that can be eliminated. */
+/* All registers that can be eliminated. */
static HARD_REG_SET eliminable_regset;
-static int allocno_compare ();
-static void mark_reg_store ();
-static void mark_reg_clobber ();
-static void mark_reg_live_nc ();
-static void mark_reg_death ();
-static void dump_conflicts ();
-void dump_global_regs ();
-static void find_reg ();
-static void global_conflicts ();
-static void expand_preferences ();
-static void prune_preferences ();
-static void record_conflicts ();
-static void set_preference ();
+static int allocno_compare PROTO((const GENERIC_PTR, const GENERIC_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((short *, int));
+static void mark_reg_store PROTO((rtx, rtx));
+static void mark_reg_clobber PROTO((rtx, rtx));
+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 *));
\f
/* Perform allocation of pseudo-registers not allocated by local_alloc.
FILE is a file to output debugging information on,
- or zero if such output is not desired. */
+ or zero if such output is not desired.
-void
+ Return value is nonzero if reload failed
+ and we must not do any more for this function. */
+
+int
global_alloc (file)
FILE *file;
{
+ int retval;
#ifdef ELIMINABLE_REGS
static struct {int from, to; } eliminables[] = ELIMINABLE_REGS;
#endif
+ int need_fp
+ = (! flag_omit_frame_pointer
+#ifdef EXIT_IGNORE_STACK
+ || (current_function_calls_alloca && EXIT_IGNORE_STACK)
+#endif
+ || FRAME_POINTER_REQUIRED);
+
register int i;
rtx x;
SET_HARD_REG_BIT (eliminable_regset, eliminables[i].from);
if (! CAN_ELIMINATE (eliminables[i].from, eliminables[i].to)
- || (eliminables[i].from == FRAME_POINTER_REGNUM
- && (! flag_omit_frame_pointer || FRAME_POINTER_REQUIRED
- || caller_save_needed)))
+ || (eliminables[i].to == STACK_POINTER_REGNUM && need_fp))
SET_HARD_REG_BIT (no_global_alloc_regs, eliminables[i].from);
}
+#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
+ SET_HARD_REG_BIT (eliminable_regset, HARD_FRAME_POINTER_REGNUM);
+ if (need_fp)
+ SET_HARD_REG_BIT (no_global_alloc_regs, HARD_FRAME_POINTER_REGNUM);
+#endif
+
#else
SET_HARD_REG_BIT (eliminable_regset, FRAME_POINTER_REGNUM);
-
- /* If we know we will definitely not be eliminating the frame pointer,
- don't allocate it. */
- if (! flag_omit_frame_pointer || FRAME_POINTER_REQUIRED
- || caller_save_needed)
+ if (need_fp)
SET_HARD_REG_BIT (no_global_alloc_regs, FRAME_POINTER_REGNUM);
#endif
/* Track which registers have already been used. Start with registers
explicitly in the rtl, then registers allocated by local register
- allocation.
-
- We consider registers that do not have to be saved over calls as if
- they were already used since there is no cost in using them. */
+ allocation. */
CLEAR_HARD_REG_SET (regs_used_so_far);
+#ifdef LEAF_REGISTERS
+ /* If we are doing the leaf function optimization, and this is a leaf
+ function, it means that the registers that take work to save are those
+ that need a register window. So prefer the ones that can be used in
+ a leaf function. */
+ {
+ char *cheap_regs;
+ static char leaf_regs[] = LEAF_REGISTERS;
+
+ if (only_leaf_regs_used () && leaf_function_p ())
+ cheap_regs = leaf_regs;
+ else
+ cheap_regs = call_used_regs;
+ for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+ if (regs_ever_live[i] || cheap_regs[i])
+ SET_HARD_REG_BIT (regs_used_so_far, i);
+ }
+#else
+ /* We consider registers that do not have to be saved over calls as if
+ they were already used since there is no cost in using them. */
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
if (regs_ever_live[i] || call_used_regs[i])
SET_HARD_REG_BIT (regs_used_so_far, i);
+#endif
for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
if (reg_renumber[i] >= 0)
/* Initialize the shared-hard-reg mapping
from the list of pairs that may share. */
reg_may_share = (int *) alloca (max_regno * sizeof (int));
- bzero (reg_may_share, max_regno * sizeof (int));
+ bzero ((char *) reg_may_share, max_regno * sizeof (int));
for (x = regs_may_share; x; x = XEXP (XEXP (x, 1), 1))
{
int r1 = REGNO (XEXP (x, 0));
/* Note that reg_live_length[i] < 0 indicates a "constant" reg
that we are supposed to refrain from putting in a hard reg.
-2 means do make an allocno but don't allocate it. */
- if (reg_n_refs[i] != 0 && reg_renumber[i] < 0 && reg_live_length[i] != -1
+ if (REG_N_REFS (i) != 0 && reg_renumber[i] < 0 && REG_LIVE_LENGTH (i) != -1
/* Don't allocate pseudos that cross calls,
if this function receives a nonlocal goto. */
&& (! current_function_has_nonlocal_label
- || reg_n_calls_crossed[i] == 0))
+ || REG_N_CALLS_CROSSED (i) == 0))
{
if (reg_may_share[i] && reg_allocno[reg_may_share[i]] >= 0)
reg_allocno[i] = reg_allocno[reg_may_share[i]];
else
reg_allocno[i] = max_allocno++;
- if (reg_live_length[i] == 0)
+ if (REG_LIVE_LENGTH (i) == 0)
abort ();
}
else
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 (allocno_size, max_allocno * sizeof (int));
- bzero (allocno_calls_crossed, max_allocno * sizeof (int));
- bzero (allocno_n_refs, max_allocno * sizeof (int));
- bzero (allocno_live_length, 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));
for (i = FIRST_PSEUDO_REGISTER; i < 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];
+ 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);
}
+ /* Calculate amount of usage of each hard reg by pseudos
+ allocated by local-alloc. This is to see if we want to
+ override it. */
+ bzero ((char *) local_reg_live_length, sizeof local_reg_live_length);
+ bzero ((char *) local_reg_n_refs, sizeof local_reg_n_refs);
+ for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
+ if (reg_allocno[i] < 0 && reg_renumber[i] >= 0)
+ {
+ int regno = reg_renumber[i];
+ int endregno = regno + HARD_REGNO_NREGS (regno, PSEUDO_REGNO_MODE (i));
+ int j;
+
+ for (j = regno; j < endregno; j++)
+ {
+ local_reg_n_refs[j] += REG_N_REFS (i);
+ local_reg_live_length[j] += REG_LIVE_LENGTH (i);
+ }
+ }
+
+ /* We can't override local-alloc for a reg used not just by local-alloc. */
+ for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+ if (regs_ever_live[i])
+ local_reg_n_refs[i] = 0;
+
+ /* Likewise for regs used in a SCRATCH. */
+ for (i = 0; i < scratch_list_length; i++)
+ if (scratch_list[i])
+ {
+ int regno = REGNO (scratch_list[i]);
+ int lim = regno + HARD_REGNO_NREGS (regno, GET_MODE (scratch_list[i]));
+ int j;
+
+ for (j = regno; j < lim; j++)
+ local_reg_n_refs[j] = 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 (hard_reg_conflicts, 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 (hard_reg_preferences, 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 (hard_reg_copy_preferences, 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 (hard_reg_full_preferences, 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 (regs_someone_prefers, 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;
- conflicts = (int *) alloca (max_allocno * allocno_row_words * sizeof (int));
- bzero (conflicts, max_allocno * allocno_row_words * sizeof (int));
+ /* We used to use alloca here, but the size of what it would try to
+ allocate would occasionally cause it to exceed the stack limit and
+ cause unpredictable core dumps. Some examples were > 2Mb in size. */
+ conflicts = (INT_TYPE *) xmalloc (max_allocno * allocno_row_words
+ * sizeof (INT_TYPE));
+ bzero ((char *) conflicts,
+ max_allocno * allocno_row_words * sizeof (INT_TYPE));
- allocnos_live = (int *) alloca (allocno_row_words * sizeof (int));
+ allocnos_live = (INT_TYPE *) alloca (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. */
the register is not eliminated, the pseudo won't really be able to
live in the eliminable register, so the conflict doesn't matter.
If we do eliminate the register, the conflict will no longer exist.
- So in either case, we can ignore the conflict. */
+ So in either case, we can ignore the conflict. Likewise for
+ preferences. */
for (i = 0; i < max_allocno; i++)
- AND_COMPL_HARD_REG_SET (hard_reg_conflicts[i], eliminable_regset);
+ {
+ AND_COMPL_HARD_REG_SET (hard_reg_conflicts[i], eliminable_regset);
+ AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences[i],
+ eliminable_regset);
+ AND_COMPL_HARD_REG_SET (hard_reg_preferences[i], eliminable_regset);
+ }
/* Try to expand the preferences by merging them between allocnos. */
except for parameters marked with reg_live_length[regno] == -2. */
for (i = 0; i < max_allocno; i++)
- if (reg_live_length[allocno_reg[allocno_order[i]]] >= 0)
+ if (REG_LIVE_LENGTH (allocno_reg[allocno_order[i]]) >= 0)
{
/* If we have more than one register class,
first try allocating in the class that is cheapest
for this pseudo-reg. If that fails, try any reg. */
if (N_REG_CLASSES > 1)
{
- find_reg (allocno_order[i], HARD_CONST (0), 0, 0);
+ find_reg (allocno_order[i], HARD_CONST (0), 0, 0, 0);
if (reg_renumber[allocno_reg[allocno_order[i]]] >= 0)
continue;
}
- if (!reg_preferred_or_nothing (allocno_reg[allocno_order[i]]))
- find_reg (allocno_order[i], HARD_CONST (0), 1, 0);
+ if (reg_alternate_class (allocno_reg[allocno_order[i]]) != NO_REGS)
+ find_reg (allocno_order[i], HARD_CONST (0), 1, 0, 0);
}
}
/* Do the reloads now while the allocno data still exist, so that we can
try to assign new hard regs to any pseudo regs that are spilled. */
+#if 0 /* We need to eliminate regs even if there is no rtl code,
+ for the sake of debugging information. */
if (n_basic_blocks > 0)
- reload (basic_block_head[0], 1, file);
+#endif
+ retval = reload (get_insns (), 1, file);
+
+ free (conflicts);
+ return retval;
}
/* Sort predicate for ordering the allocnos.
Returns -1 (1) if *v1 should be allocated before (after) *v2. */
static int
-allocno_compare (v1, v2)
- int *v1, *v2;
+allocno_compare (v1p, v2p)
+ const GENERIC_PTR v1p;
+ const GENERIC_PTR v2p;
{
+ int v1 = *(int *)v1p, v2 = *(int *)v2p;
/* Note that the quotient will never be bigger than
the value of floor_log2 times the maximum number of
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] * allocno_size[*v1]))
- * 10000);
+ = (((double) (floor_log2 (allocno_n_refs[v1]) * allocno_n_refs[v1])
+ / allocno_live_length[v1])
+ * 10000 * allocno_size[v1]);
register int pri2
- = (((double) (floor_log2 (allocno_n_refs[*v2]) * allocno_n_refs[*v2])
- / (allocno_live_length[*v2] * allocno_size[*v2]))
- * 10000);
+ = (((double) (floor_log2 (allocno_n_refs[v2]) * allocno_n_refs[v2])
+ / allocno_live_length[v2])
+ * 10000 * allocno_size[v2]);
if (pri2 - pri1)
return pri2 - pri1;
/* If regs are equally good, sort by allocno,
so that the results of qsort leave nothing to chance. */
- return *v1 - *v2;
+ return v1 - v2;
}
\f
/* Scan the rtl code and record all conflicts and register preferences in the
for (b = 0; b < n_basic_blocks; b++)
{
- bzero (allocnos_live, allocno_row_words * sizeof (int));
+ bzero ((char *) allocnos_live, allocno_row_words * sizeof (INT_TYPE));
/* Initialize table of registers currently live
to the state at the beginning of this basic block.
are explicitly marked in basic_block_live_at_start. */
{
- register int offset, bit;
register regset old = basic_block_live_at_start[b];
int ax = 0;
-#ifdef HARD_REG_SET
- hard_regs_live = old[0];
-#else
- COPY_HARD_REG_SET (hard_regs_live, old);
-#endif
- for (offset = 0, i = 0; offset < regset_size; offset++)
- if (old[offset] == 0)
- i += HOST_BITS_PER_INT;
- else
- for (bit = 1; bit; bit <<= 1, i++)
- {
- if (i >= max_regno)
- break;
- if (old[offset] & bit)
- {
- register int a = reg_allocno[i];
- if (a >= 0)
- {
- SET_ALLOCNO_LIVE (a);
- block_start_allocnos[ax++] = a;
- }
- else if ((a = reg_renumber[i]) >= 0)
- mark_reg_live_nc (a, PSEUDO_REGNO_MODE (i));
- }
- }
+ REG_SET_TO_HARD_REG_SET (hard_regs_live, old);
+ EXECUTE_IF_SET_IN_REG_SET (old, FIRST_PSEUDO_REGISTER, i,
+ {
+ register int a = reg_allocno[i];
+ if (a >= 0)
+ {
+ SET_ALLOCNO_LIVE (a);
+ block_start_allocnos[ax++] = a;
+ }
+ else if ((a = reg_renumber[i]) >= 0)
+ mark_reg_live_nc
+ (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. */
if (code == INSN || code == CALL_INSN || code == JUMP_INSN)
{
- int i = 0;
#if 0
+ int i = 0;
for (link = REG_NOTES (insn);
link && i < NUM_NO_CONFLICT_PAIRS;
link = XEXP (link, 1))
#ifdef AUTO_INC_DEC
for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
if (REG_NOTE_KIND (link) == REG_INC)
- mark_reg_store (XEXP (link, 0), 0);
+ mark_reg_store (XEXP (link, 0), NULL_RTX);
#endif
+ /* If INSN has multiple outputs, then any reg that dies here
+ and is used inside of an output
+ must conflict with the other outputs. */
+
+ if (GET_CODE (PATTERN (insn)) == PARALLEL && !single_set (insn))
+ for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
+ if (REG_NOTE_KIND (link) == REG_DEAD)
+ {
+ int used_in_output = 0;
+ int i;
+ rtx reg = XEXP (link, 0);
+
+ for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
+ {
+ rtx set = XVECEXP (PATTERN (insn), 0, i);
+ if (GET_CODE (set) == SET
+ && GET_CODE (SET_DEST (set)) != REG
+ && !rtx_equal_p (reg, SET_DEST (set))
+ && reg_overlap_mentioned_p (reg, SET_DEST (set)))
+ used_in_output = 1;
+ }
+ if (used_in_output)
+ mark_reg_conflicts (reg);
+ }
+
/* Mark any registers set in INSN and then never used. */
while (n_regs_set > 0)
/* Scan least most important to most important.
For each allocno, remove from preferences registers that cannot be used,
either because of conflicts or register type. Then compute all registers
- prefered by each lower-priority register that conflicts. */
+ preferred by each lower-priority register that conflicts. */
for (i = max_allocno - 1; i >= 0; i--)
{
we want to give the lower-priority allocno the first chance for
these registers). */
for (j = i + 1; j < max_allocno; j++)
- if (CONFLICTP (allocno, allocno_order[j]))
+ if (CONFLICTP (allocno, allocno_order[j])
+ || CONFLICTP (allocno_order[j], allocno))
{
COPY_HARD_REG_SET (temp,
hard_reg_full_preferences[allocno_order[j]]);
LOSERS, if non-zero, is a HARD_REG_SET indicating registers that cannot
be used for this allocation.
- If ALL_REGS_P is zero, consider only the preferred class of ALLOCNO's reg.
- Otherwise ignore that preferred class.
+ If ALT_REGS_P is zero, consider only the preferred class of ALLOCNO's reg.
+ Otherwise ignore that preferred class and use the alternate class.
If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that
will have to be saved and restored at calls.
+ RETRYING is nonzero if this is called from retry_global_alloc.
+
If we find one, record it in reg_renumber.
If not, do nothing. */
static void
-find_reg (allocno, losers, all_regs_p, accept_call_clobbered)
+find_reg (allocno, losers, alt_regs_p, accept_call_clobbered, retrying)
int allocno;
HARD_REG_SET losers;
- int all_regs_p;
+ int alt_regs_p;
int accept_call_clobbered;
+ int retrying;
{
register int i, best_reg, pass;
#ifdef HARD_REG_SET
register /* Declare it register if it's a scalar. */
#endif
- HARD_REG_SET used, used1;
+ HARD_REG_SET used, used1, used2;
- enum reg_class class
- = all_regs_p ? ALL_REGS : reg_preferred_class (allocno_reg[allocno]);
+ 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]);
if (accept_call_clobbered)
IOR_HARD_REG_SET (used1, losers);
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]);
+#ifdef CLASS_CANNOT_CHANGE_SIZE
+ if (REG_CHANGES_SIZE (allocno_reg[allocno]))
+ IOR_HARD_REG_SET (used1,
+ reg_class_contents[(int) CLASS_CANNOT_CHANGE_SIZE]);
+#endif
+
/* Try each hard reg to see if it fits. Do this in two passes.
- In the first pass, skip registers that are prefered by some other pseudo
+ In the first pass, skip registers that are preferred by some other pseudo
to give it a better chance of getting one of those registers. Only if
we can't get a register when excluding those do we take one of them.
However, we never allocate a register for the first time in pass 0. */
}
no_prefs:
+ /* If we haven't succeeded yet, try with caller-saves.
+ We need not check to see if the current function has nonlocal
+ labels because we don't put any pseudos that are live over calls in
+ registers in that case. */
+
+ if (flag_caller_saves && best_reg < 0)
+ {
+ /* Did not find a register. If it would be profitable to
+ 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]))
+ {
+ HARD_REG_SET new_losers;
+ if (! losers)
+ CLEAR_HARD_REG_SET (new_losers);
+ else
+ 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)
+ {
+ caller_save_needed = 1;
+ return;
+ }
+ }
+ }
+
+ /* If we haven't succeeded yet,
+ see if some hard reg that conflicts with us
+ was utilized poorly by local-alloc.
+ If so, kick out the regs that were put there by local-alloc
+ so we can use it instead. */
+ if (best_reg < 0 && !retrying
+ /* Let's not bother with multi-reg allocnos. */
+ && allocno_size[allocno] == 1)
+ {
+ /* Count from the end, to find the least-used ones first. */
+ for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
+ {
+#ifdef REG_ALLOC_ORDER
+ int regno = reg_alloc_order[i];
+#else
+ int regno = i;
+#endif
+
+ if (local_reg_n_refs[regno] != 0
+ /* 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])
+ && (TEST_HARD_REG_BIT
+ (reg_class_contents[(int) CLASS_CANNOT_CHANGE_SIZE],
+ regno)))
+#endif
+ )
+ {
+ /* We explicitly evaluate the divide results into temporary
+ variables so as to avoid excess precision problems that occur
+ on a i386-unknown-sysv4.2 (unixware) host. */
+
+ double tmp1 = ((double) local_reg_n_refs[regno]
+ / local_reg_live_length[regno]);
+ double tmp2 = ((double) allocno_n_refs[allocno]
+ / allocno_live_length[allocno]);
+
+ if (tmp1 < tmp2)
+ {
+ /* Hard reg REGNO was used less in total by local regs
+ than it would be used by this one allocno! */
+ int k;
+ for (k = 0; k < max_regno; k++)
+ if (reg_renumber[k] >= 0)
+ {
+ int r = reg_renumber[k];
+ int endregno
+ = r + HARD_REGNO_NREGS (r, PSEUDO_REGNO_MODE (k));
+
+ if (regno >= r && regno < endregno)
+ reg_renumber[k] = -1;
+ }
+
+ best_reg = regno;
+ break;
+ }
+ }
+ }
+ }
+
/* Did we find a register? */
if (best_reg >= 0)
{
SET_HARD_REG_BIT (this_reg, j);
SET_HARD_REG_BIT (regs_used_so_far, j);
+ /* This is no longer a reg used just by local regs. */
+ local_reg_n_refs[j] = 0;
}
/* For each other pseudo-reg conflicting with this one,
mark it as conflicting with the hard regs this one occupies. */
IOR_HARD_REG_SET (hard_reg_conflicts[j], this_reg);
}
}
- else if (flag_caller_saves)
- {
- /* Did not find a register. If it would be profitable to
- 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]))
- {
- find_reg (allocno, losers, all_regs_p, 1);
- if (reg_renumber[allocno_reg[allocno]] >= 0)
- caller_save_needed = 1;
- }
- }
}
\f
/* Called from `reload' to look for a hard reg to put pseudo reg REGNO in.
first try allocating in the class that is cheapest
for this pseudo-reg. If that fails, try any reg. */
if (N_REG_CLASSES > 1)
- find_reg (allocno, forbidden_regs, 0, 0);
+ find_reg (allocno, forbidden_regs, 0, 0, 1);
if (reg_renumber[regno] < 0
- && !reg_preferred_or_nothing (regno))
- find_reg (allocno, forbidden_regs, 1, 0);
+ && reg_alternate_class (regno) != NO_REGS)
+ find_reg (allocno, forbidden_regs, 1, 0, 1);
/* If we found a register, modify the RTL for the register to
show the hard register, and mark that register live. */
}
}
}
+
+/* Record that REG has conflicts with all the regs currently live.
+ Do not mark REG itself as live. */
+
+static void
+mark_reg_conflicts (reg)
+ rtx reg;
+{
+ register int regno;
+
+ if (GET_CODE (reg) == SUBREG)
+ reg = SUBREG_REG (reg);
+
+ if (GET_CODE (reg) != REG)
+ return;
+
+ regno = REGNO (reg);
+
+ if (reg_renumber[regno] >= 0)
+ regno = reg_renumber[regno];
+
+ /* Either this is one of the max_allocno pseudo regs not allocated,
+ or it is or has a hardware reg. First handle the pseudo-regs. */
+ if (regno >= FIRST_PSEUDO_REGISTER)
+ {
+ if (reg_allocno[regno] >= 0)
+ record_one_conflict (regno);
+ }
+ /* Handle hardware regs (and pseudos allocated to hard regs). */
+ else if (! fixed_regs[regno])
+ {
+ register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
+ while (regno < last)
+ {
+ record_one_conflict (regno);
+ regno++;
+ }
+ }
+}
\f
/* Mark REG as being dead (following the insn being scanned now).
Store a 0 in regs_live or allocnos_live for this register. */
try to set a preference. If one of the two is a hard register and the other
is a pseudo-register, mark the preference.
- Note that we are not as agressive as local-alloc in trying to tie a
+ Note that we are not as aggressive as local-alloc in trying to tie a
pseudo-register to a hard register. */
static void
int i;
for (i = 0; i < n_basic_blocks; i++)
- if ((basic_block_live_at_start[i][from / HOST_BITS_PER_INT]
- & (1 << (from % HOST_BITS_PER_INT))) != 0)
+ if (REGNO_REG_SET_P (basic_block_live_at_start[i], from))
{
- basic_block_live_at_start[i][from / HOST_BITS_PER_INT]
- &= ~ (1 << (from % HOST_BITS_PER_INT));
- basic_block_live_at_start[i][to / HOST_BITS_PER_INT]
- |= (1 << (to % HOST_BITS_PER_INT));
+ CLEAR_REGNO_REG_SET (basic_block_live_at_start[i], from);
+ SET_REGNO_REG_SET (basic_block_live_at_start[i], to);
}
}
\f
OSDN Git Service
