#include "config.h"
#include "system.h"
#include "machmode.h"
#include "hard-reg-set.h"
#include "rtl.h"
#include "flags.h"
#include "basic-block.h"
#include "regs.h"
#include "insn-config.h"
#include "reload.h"
#include "output.h"
#include "toplev.h"
static int max_allocno;
static int *reg_allocno;
static int *allocno_reg;
static int *allocno_order;
static int *allocno_size;
static int *reg_may_share;
#define INT_BITS HOST_BITS_PER_WIDE_INT
#define INT_TYPE HOST_WIDE_INT
static INT_TYPE *conflicts;
static int allocno_row_words;
#define CONFLICTP(I, J) \
(conflicts[(I) * allocno_row_words + (J) / INT_BITS] \
& ((INT_TYPE) 1 << ((J) % INT_BITS)))
#define SET_CONFLICT(I, J) \
(conflicts[(I) * allocno_row_words + (J) / INT_BITS] \
|= ((INT_TYPE) 1 << ((J) % INT_BITS)))
static HARD_REG_SET hard_regs_live;
static HARD_REG_SET *hard_reg_conflicts;
static HARD_REG_SET *hard_reg_preferences;
static HARD_REG_SET *hard_reg_copy_preferences;
static HARD_REG_SET *hard_reg_full_preferences;
static HARD_REG_SET *regs_someone_prefers;
static HARD_REG_SET no_global_alloc_regs;
static HARD_REG_SET regs_used_so_far;
static int *allocno_calls_crossed;
static int *allocno_n_refs;
static int *allocno_live_length;
static int local_reg_n_refs[FIRST_PSEUDO_REGISTER];
static int local_reg_live_length[FIRST_PSEUDO_REGISTER];
#define REGBITP(TABLE, I, J) TEST_HARD_REG_BIT (TABLE[I], J)
#define SET_REGBIT(TABLE, I, J) SET_HARD_REG_BIT (TABLE[I], J)
static INT_TYPE *allocnos_live;
#define ALLOCNO_LIVE_P(I) \
(allocnos_live[(I) / INT_BITS] & ((INT_TYPE) 1 << ((I) % INT_BITS)))
#define SET_ALLOCNO_LIVE(I) \
(allocnos_live[(I) / INT_BITS] |= ((INT_TYPE) 1 << ((I) % INT_BITS)))
#define CLEAR_ALLOCNO_LIVE(I) \
(allocnos_live[(I) / INT_BITS] &= ~((INT_TYPE) 1 << ((I) % INT_BITS)))
#if 0
#define NUM_NO_CONFLICT_PAIRS 4
int n_no_conflict_pairs;
static struct { int allocno1, allocno2;}
no_conflict_pairs[NUM_NO_CONFLICT_PAIRS];
#endif
static rtx *regs_set;
static int n_regs_set;
static HARD_REG_SET eliminable_regset;
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((int *, 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 *));
static void reg_becomes_live PROTO((rtx, rtx));
static void reg_dies PROTO((int, enum machine_mode));
static void build_insn_chain PROTO((rtx));
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 size_t i;
rtx x;
max_allocno = 0;
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
#ifdef ELIMINABLE_REGS
for (i = 0; i < sizeof eliminables / sizeof eliminables[0]; i++)
{
SET_HARD_REG_BIT (eliminable_regset, eliminables[i].from);
if (! CAN_ELIMINATE (eliminables[i].from, eliminables[i].to)
|| (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 (need_fp)
SET_HARD_REG_BIT (no_global_alloc_regs, FRAME_POINTER_REGNUM);
#endif
CLEAR_HARD_REG_SET (regs_used_so_far);
#ifdef LEAF_REGISTERS
{
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
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 < (size_t) max_regno; i++)
if (reg_renumber[i] >= 0)
SET_HARD_REG_BIT (regs_used_so_far, reg_renumber[i]);
reg_allocno = (int *) alloca (max_regno * sizeof (int));
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
reg_allocno[i] = -1;
reg_may_share = (int *) alloca (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));
int r2 = REGNO (XEXP (XEXP (x, 1), 0));
if (r1 > r2)
reg_may_share[r1] = r2;
else
reg_may_share[r2] = r1;
}
for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
if (REG_N_REFS (i) != 0 && REG_LIVE_LENGTH (i) != -1
&& (! current_function_has_nonlocal_label
|| REG_N_CALLS_CROSSED (i) == 0))
{
if (reg_renumber[i] < 0 && 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)
abort ();
}
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));
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);
}
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 < (size_t) max_regno; i++)
if (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);
}
}
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
if (regs_ever_live[i])
local_reg_n_refs[i] = 0;
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;
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_TYPE *) alloca (allocno_row_words * sizeof (INT_TYPE));
if (max_allocno > 0)
{
global_conflicts ();
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],
eliminable_regset);
AND_COMPL_HARD_REG_SET (hard_reg_preferences[i], eliminable_regset);
}
expand_preferences ();
allocno_order = (int *) alloca (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;
}
qsort (allocno_order, max_allocno, sizeof (int), allocno_compare);
prune_preferences ();
if (file)
dump_conflicts (file);
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 (N_REG_CLASSES > 1)
{
find_reg (allocno_order[i], 0, 0, 0, 0);
if (reg_renumber[allocno_reg[allocno_order[i]]] >= 0)
continue;
}
if (reg_alternate_class (allocno_reg[allocno_order[i]]) != NO_REGS)
find_reg (allocno_order[i], 0, 1, 0, 0);
}
}
#if 0
if (n_basic_blocks > 0)
#endif
{
build_insn_chain (get_insns ());
retval = reload (get_insns (), 1, file);
}
free (conflicts);
return retval;
}
static int
allocno_compare (v1p, v2p)
const GENERIC_PTR v1p;
const GENERIC_PTR v2p;
{
int v1 = *(int *)v1p, v2 = *(int *)v2p;
register int pri1
= (((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])
* 10000 * allocno_size[v2]);
if (pri2 - pri1)
return pri2 - pri1;
return v1 - v2;
}
static void
global_conflicts ()
{
register int b, i;
register rtx insn;
int *block_start_allocnos;
regs_set = (rtx *) alloca (max_parallel * sizeof (rtx) * 2);
block_start_allocnos = (int *) alloca (max_allocno * sizeof (int));
for (b = 0; b < n_basic_blocks; b++)
{
bzero ((char *) allocnos_live, allocno_row_words * sizeof (INT_TYPE));
{
register regset old = BASIC_BLOCK (b)->global_live_at_start;
int ax = 0;
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_conflicts (block_start_allocnos, ax);
#ifdef STACK_REGS
{
edge e;
for (e = BASIC_BLOCK (b)->pred; e ; e = e->pred_next)
if (e->flags & EDGE_ABNORMAL)
break;
if (e != NULL)
for (ax = FIRST_STACK_REG; ax <= LAST_STACK_REG; ax++)
record_one_conflict (ax);
}
#endif
}
insn = BLOCK_HEAD (b);
while (1)
{
register RTX_CODE code = GET_CODE (insn);
register rtx link;
n_regs_set = 0;
if (code == INSN || code == CALL_INSN || code == JUMP_INSN)
{
#if 0
int i = 0;
for (link = REG_NOTES (insn);
link && i < NUM_NO_CONFLICT_PAIRS;
link = XEXP (link, 1))
if (REG_NOTE_KIND (link) == REG_NO_CONFLICT)
{
no_conflict_pairs[i].allocno1
= reg_allocno[REGNO (SET_DEST (PATTERN (insn)))];
no_conflict_pairs[i].allocno2
= reg_allocno[REGNO (XEXP (link, 0))];
i++;
}
#endif
note_stores (PATTERN (insn), mark_reg_clobber);
for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
if (REG_NOTE_KIND (link) == REG_DEAD)
mark_reg_death (XEXP (link, 0));
note_stores (PATTERN (insn), mark_reg_store);
#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), NULL_RTX);
#endif
if (GET_CODE (PATTERN (insn)) == PARALLEL && multiple_sets (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);
}
while (n_regs_set > 0)
if (find_regno_note (insn, REG_UNUSED,
REGNO (regs_set[--n_regs_set])))
mark_reg_death (regs_set[n_regs_set]);
}
if (insn == BLOCK_END (b))
break;
insn = NEXT_INSN (insn);
}
}
}
static void
expand_preferences ()
{
rtx insn;
rtx link;
rtx set;
for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
&& (set = single_set (insn)) != 0
&& GET_CODE (SET_DEST (set)) == REG
&& reg_allocno[REGNO (SET_DEST (set))] >= 0)
for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
if (REG_NOTE_KIND (link) == REG_DEAD
&& 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))]))
{
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 (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]);
}
}
static void
prune_preferences ()
{
int i, j;
int allocno;
for (i = max_allocno - 1; i >= 0; i--)
{
HARD_REG_SET temp;
allocno = allocno_order[i];
COPY_HARD_REG_SET (temp, hard_reg_conflicts[allocno]);
if (allocno_calls_crossed[allocno] == 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])]);
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);
CLEAR_HARD_REG_SET (regs_someone_prefers[allocno]);
for (j = i + 1; j < max_allocno; j++)
if (CONFLICTP (allocno, allocno_order[j])
|| CONFLICTP (allocno_order[j], allocno))
{
COPY_HARD_REG_SET (temp,
hard_reg_full_preferences[allocno_order[j]]);
if (allocno_size[allocno_order[j]] <= allocno_size[allocno])
AND_COMPL_HARD_REG_SET (temp,
hard_reg_full_preferences[allocno]);
IOR_HARD_REG_SET (regs_someone_prefers[allocno], temp);
}
}
}
static void
find_reg (allocno, losers, alt_regs_p, accept_call_clobbered, retrying)
int allocno;
HARD_REG_SET losers;
int alt_regs_p;
int accept_call_clobbered;
int retrying;
{
register int i, best_reg, pass;
#ifdef HARD_REG_SET
register
#endif
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]);
if (accept_call_clobbered)
COPY_HARD_REG_SET (used1, call_fixed_reg_set);
else if (allocno_calls_crossed[allocno] == 0)
COPY_HARD_REG_SET (used1, fixed_reg_set);
else
COPY_HARD_REG_SET (used1, call_used_reg_set);
IOR_HARD_REG_SET (used1, no_global_alloc_regs);
if (losers)
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
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]);
best_reg = -1;
for (i = FIRST_PSEUDO_REGISTER, pass = 0;
pass <= 1 && i >= FIRST_PSEUDO_REGISTER;
pass++)
{
if (pass == 1)
COPY_HARD_REG_SET (used, used1);
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
{
#ifdef REG_ALLOC_ORDER
int regno = reg_alloc_order[i];
#else
int regno = i;
#endif
if (! TEST_HARD_REG_BIT (used, regno)
&& HARD_REGNO_MODE_OK (regno, mode)
&& (allocno_calls_crossed[allocno] == 0
|| accept_call_clobbered
|| ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode)))
{
register int j;
register int lim = regno + HARD_REGNO_NREGS (regno, mode);
for (j = regno + 1;
(j < lim
&& ! TEST_HARD_REG_BIT (used, j));
j++);
if (j == lim)
{
best_reg = regno;
break;
}
#ifndef REG_ALLOC_ORDER
i = j;
#endif
}
}
}
AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences[allocno], used);
GO_IF_HARD_REG_SUBSET (hard_reg_copy_preferences[allocno],
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)
&& HARD_REGNO_MODE_OK (i, mode)
&& (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
|| reg_class_subset_p (REGNO_REG_CLASS (i),
REGNO_REG_CLASS (best_reg))
|| reg_class_subset_p (REGNO_REG_CLASS (best_reg),
REGNO_REG_CLASS (i))))
{
register int j;
register int lim = i + HARD_REGNO_NREGS (i, mode);
for (j = i + 1;
(j < lim
&& ! TEST_HARD_REG_BIT (used, j)
&& (REGNO_REG_CLASS (j)
== REGNO_REG_CLASS (best_reg + (j - i))
|| reg_class_subset_p (REGNO_REG_CLASS (j),
REGNO_REG_CLASS (best_reg + (j - i)))
|| reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)),
REGNO_REG_CLASS (j))));
j++);
if (j == lim)
{
best_reg = i;
goto no_prefs;
}
}
}
no_copy_prefs:
AND_COMPL_HARD_REG_SET (hard_reg_preferences[allocno], used);
GO_IF_HARD_REG_SUBSET (hard_reg_preferences[allocno],
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)
&& HARD_REGNO_MODE_OK (i, mode)
&& (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
|| reg_class_subset_p (REGNO_REG_CLASS (i),
REGNO_REG_CLASS (best_reg))
|| reg_class_subset_p (REGNO_REG_CLASS (best_reg),
REGNO_REG_CLASS (i))))
{
register int j;
register int lim = i + HARD_REGNO_NREGS (i, mode);
for (j = i + 1;
(j < lim
&& ! TEST_HARD_REG_BIT (used, j)
&& (REGNO_REG_CLASS (j)
== REGNO_REG_CLASS (best_reg + (j - i))
|| reg_class_subset_p (REGNO_REG_CLASS (j),
REGNO_REG_CLASS (best_reg + (j - i)))
|| reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)),
REGNO_REG_CLASS (j))));
j++);
if (j == lim)
{
best_reg = i;
break;
}
}
}
no_prefs:
if (flag_caller_saves && best_reg < 0)
{
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 (best_reg < 0 && !retrying
&& allocno_size[allocno] == 1)
{
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
&& ! 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
)
{
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)
{
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;
}
}
}
}
if (best_reg >= 0)
{
register int lim, j;
HARD_REG_SET this_reg;
reg_renumber[allocno_reg[allocno]] = best_reg;
if (reg_may_share[allocno_reg[allocno]])
for (j = FIRST_PSEUDO_REGISTER; j < max_regno; j++)
if (reg_allocno[j] == allocno)
reg_renumber[j] = best_reg;
CLEAR_HARD_REG_SET (this_reg);
lim = best_reg + HARD_REGNO_NREGS (best_reg, mode);
for (j = best_reg; j < lim; j++)
{
SET_HARD_REG_BIT (this_reg, j);
SET_HARD_REG_BIT (regs_used_so_far, j);
local_reg_n_refs[j] = 0;
}
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);
}
}
}
void
retry_global_alloc (regno, forbidden_regs)
int regno;
HARD_REG_SET forbidden_regs;
{
int allocno = reg_allocno[regno];
if (allocno >= 0)
{
if (N_REG_CLASSES > 1)
find_reg (allocno, forbidden_regs, 0, 0, 1);
if (reg_renumber[regno] < 0
&& reg_alternate_class (regno) != NO_REGS)
find_reg (allocno, forbidden_regs, 1, 0, 1);
if (reg_renumber[regno] >= 0)
{
REGNO (regno_reg_rtx[regno]) = reg_renumber[regno];
mark_home_live (regno);
}
}
}
static void
record_one_conflict (regno)
int regno;
{
register int j;
if (regno < FIRST_PSEUDO_REGISTER)
for (j = 0; j < max_allocno; j++)
{
if (ALLOCNO_LIVE_P (j))
SET_HARD_REG_BIT (hard_reg_conflicts[j], regno);
}
else
{
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);
for (j = allocno_row_words - 1; j >= 0; j--)
{
#if 0
int k;
for (k = 0; k < n_no_conflict_pairs; k++)
if (! ((j == no_conflict_pairs[k].allocno1
&& ialloc == no_conflict_pairs[k].allocno2)
||
(j == no_conflict_pairs[k].allocno2
&& ialloc == no_conflict_pairs[k].allocno1)))
#endif
conflicts[ialloc_prod + j] |= allocnos_live[j];
}
}
}
static void
record_conflicts (allocno_vec, len)
register int *allocno_vec;
register int len;
{
register int allocno;
register int j;
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];
}
}
static void
mark_reg_store (reg, setter)
rtx reg, setter;
{
register int regno;
int word = 0;
if (GET_CODE (reg) == SUBREG)
{
word = SUBREG_WORD (reg);
reg = SUBREG_REG (reg);
}
if (GET_CODE (reg) != REG)
return;
regs_set[n_regs_set++] = reg;
if (setter && GET_CODE (setter) != CLOBBER)
set_preference (reg, SET_SRC (setter));
regno = REGNO (reg);
if (regno >= FIRST_PSEUDO_REGISTER)
{
if (reg_allocno[regno] >= 0)
{
SET_ALLOCNO_LIVE (reg_allocno[regno]);
record_one_conflict (regno);
}
}
if (reg_renumber[regno] >= 0)
regno = reg_renumber[regno] ;
if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno])
{
register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
while (regno < last)
{
record_one_conflict (regno);
SET_HARD_REG_BIT (hard_regs_live, regno);
regno++;
}
}
}
static void
mark_reg_clobber (reg, setter)
rtx reg, setter;
{
if (GET_CODE (setter) == CLOBBER)
mark_reg_store (reg, setter);
}
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 (regno >= FIRST_PSEUDO_REGISTER)
{
if (reg_allocno[regno] >= 0)
record_one_conflict (regno);
}
if (reg_renumber[regno] >= 0)
regno = reg_renumber[regno];
if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno])
{
register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
while (regno < last)
{
record_one_conflict (regno);
regno++;
}
}
}
static void
mark_reg_death (reg)
rtx reg;
{
register int regno = REGNO (reg);
if (regno >= FIRST_PSEUDO_REGISTER)
{
if (reg_allocno[regno] >= 0)
CLEAR_ALLOCNO_LIVE (reg_allocno[regno]);
}
if (reg_renumber[regno] >= 0)
regno = reg_renumber[regno];
if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno])
{
register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
while (regno < last)
{
CLEAR_HARD_REG_BIT (hard_regs_live, regno);
regno++;
}
}
}
static void
mark_reg_live_nc (regno, mode)
register int regno;
enum machine_mode mode;
{
register int last = regno + HARD_REGNO_NREGS (regno, mode);
while (regno < last)
{
SET_HARD_REG_BIT (hard_regs_live, regno);
regno++;
}
}
static void
set_preference (dest, src)
rtx dest, src;
{
int src_regno, dest_regno;
int offset = 0;
int i;
int copy = 1;
if (GET_RTX_FORMAT (GET_CODE (src))[0] == 'e')
src = XEXP (src, 0), copy = 0;
if (GET_CODE (src) == REG)
src_regno = REGNO (src);
else if (GET_CODE (src) == SUBREG && GET_CODE (SUBREG_REG (src)) == REG)
{
src_regno = REGNO (SUBREG_REG (src));
offset += SUBREG_WORD (src);
}
else
return;
if (GET_CODE (dest) == REG)
dest_regno = REGNO (dest);
else if (GET_CODE (dest) == SUBREG && GET_CODE (SUBREG_REG (dest)) == REG)
{
dest_regno = REGNO (SUBREG_REG (dest));
offset -= SUBREG_WORD (dest);
}
else
return;
if (reg_renumber[src_regno] >= 0)
src_regno = reg_renumber[src_regno];
if (reg_renumber[dest_regno] >= 0)
dest_regno = reg_renumber[dest_regno];
if (dest_regno < FIRST_PSEUDO_REGISTER && src_regno >= FIRST_PSEUDO_REGISTER
&& reg_allocno[src_regno] >= 0)
{
dest_regno -= offset;
if (dest_regno >= 0 && dest_regno < FIRST_PSEUDO_REGISTER)
{
if (copy)
SET_REGBIT (hard_reg_copy_preferences,
reg_allocno[src_regno], dest_regno);
SET_REGBIT (hard_reg_preferences,
reg_allocno[src_regno], dest_regno);
for (i = dest_regno;
i < dest_regno + HARD_REGNO_NREGS (dest_regno, GET_MODE (dest));
i++)
SET_REGBIT (hard_reg_full_preferences, reg_allocno[src_regno], i);
}
}
if (src_regno < FIRST_PSEUDO_REGISTER && dest_regno >= FIRST_PSEUDO_REGISTER
&& reg_allocno[dest_regno] >= 0)
{
src_regno += offset;
if (src_regno >= 0 && src_regno < FIRST_PSEUDO_REGISTER)
{
if (copy)
SET_REGBIT (hard_reg_copy_preferences,
reg_allocno[dest_regno], src_regno);
SET_REGBIT (hard_reg_preferences,
reg_allocno[dest_regno], src_regno);
for (i = src_regno;
i < src_regno + HARD_REGNO_NREGS (src_regno, GET_MODE (src));
i++)
SET_REGBIT (hard_reg_full_preferences, reg_allocno[dest_regno], i);
}
}
}
void
mark_elimination (from, to)
int from, to;
{
int i;
for (i = 0; i < n_basic_blocks; i++)
{
register regset r = BASIC_BLOCK (i)->global_live_at_start;
if (REGNO_REG_SET_P (r, from))
{
CLEAR_REGNO_REG_SET (r, from);
SET_REGNO_REG_SET (r, to);
}
}
}
static regset live_relevant_regs;
static void
reg_becomes_live (reg, setter)
rtx reg;
rtx setter ATTRIBUTE_UNUSED;
{
int regno;
if (GET_CODE (reg) == SUBREG)
reg = SUBREG_REG (reg);
if (GET_CODE (reg) != REG)
return;
regno = REGNO (reg);
if (regno < FIRST_PSEUDO_REGISTER)
{
int nregs = HARD_REGNO_NREGS (regno, GET_MODE (reg));
while (nregs-- > 0)
SET_REGNO_REG_SET (live_relevant_regs, regno++);
}
else if (reg_renumber[regno] >= 0)
SET_REGNO_REG_SET (live_relevant_regs, regno);
}
static void
reg_dies (regno, mode)
int regno;
enum machine_mode mode;
{
if (regno < FIRST_PSEUDO_REGISTER)
{
int nregs = HARD_REGNO_NREGS (regno, mode);
while (nregs-- > 0)
CLEAR_REGNO_REG_SET (live_relevant_regs, regno++);
}
else
CLEAR_REGNO_REG_SET (live_relevant_regs, regno);
}
static void
build_insn_chain (first)
rtx first;
{
struct insn_chain **p = &reload_insn_chain;
struct insn_chain *prev = 0;
int b = 0;
live_relevant_regs = ALLOCA_REG_SET ();
for (; first; first = NEXT_INSN (first))
{
struct insn_chain *c;
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);
}
if (GET_CODE (first) != NOTE && GET_CODE (first) != BARRIER)
{
c = new_insn_chain ();
c->prev = prev;
prev = c;
*p = c;
p = &c->next;
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)));
note_stores (PATTERN (first), reg_becomes_live);
}
COPY_REG_SET (c->live_after, 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_UNUSED
&& GET_CODE (XEXP (link, 0)) == REG)
reg_dies (REGNO (XEXP (link, 0)), GET_MODE (XEXP (link, 0)));
}
}
if (first == BLOCK_END (b))
b++;
if (b == n_basic_blocks)
{
for (first = NEXT_INSN (first) ; first; first = NEXT_INSN (first))
if (GET_RTX_CLASS (GET_CODE (first)) == 'i'
&& GET_CODE (PATTERN (first)) != USE)
abort ();
break;
}
}
FREE_REG_SET (live_relevant_regs);
*p = 0;
}
static void
dump_conflicts (file)
FILE *file;
{
register int i;
register int has_preferences;
register int nregs;
nregs = 0;
for (i = 0; i < max_allocno; i++)
{
if (reg_renumber[allocno_reg[allocno_order[i]]] >= 0)
continue;
nregs++;
}
fprintf (file, ";; %d regs to allocate:", nregs);
for (i = 0; i < max_allocno; i++)
{
int j;
if (reg_renumber[allocno_reg[allocno_order[i]]] >= 0)
continue;
fprintf (file, " %d", allocno_reg[allocno_order[i]]);
for (j = 0; j < max_regno; j++)
if (reg_allocno[j] == allocno_order[i]
&& j != allocno_reg[allocno_order[i]])
fprintf (file, "+%d", j);
if (allocno_size[allocno_order[i]] != 1)
fprintf (file, " (%d)", allocno_size[allocno_order[i]]);
}
fprintf (file, "\n");
for (i = 0; i < max_allocno; i++)
{
register int j;
fprintf (file, ";; %d conflicts:", allocno_reg[i]);
for (j = 0; j < max_allocno; j++)
if (CONFLICTP (i, j) || CONFLICTP (j, i))
fprintf (file, " %d", allocno_reg[j]);
for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
if (TEST_HARD_REG_BIT (hard_reg_conflicts[i], 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))
has_preferences = 1;
if (! has_preferences)
continue;
fprintf (file, ";; %d preferences:", allocno_reg[i]);
for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
if (TEST_HARD_REG_BIT (hard_reg_preferences[i], j))
fprintf (file, " %d", j);
fprintf (file, "\n");
}
fprintf (file, "\n");
}
void
dump_global_regs (file)
FILE *file;
{
register int i, j;
fprintf (file, ";; Register dispositions:\n");
for (i = FIRST_PSEUDO_REGISTER, j = 0; i < max_regno; i++)
if (reg_renumber[i] >= 0)
{
fprintf (file, "%d in %d ", i, reg_renumber[i]);
if (++j % 6 == 0)
fprintf (file, "\n");
}
fprintf (file, "\n\n;; Hard regs used: ");
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
if (regs_ever_live[i])
fprintf (file, " %d", i);
fprintf (file, "\n\n");
}