#include "config.h"
#include "system.h"
#include "rtl.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "regs.h"
#include "insn-config.h"
#include "reload.h"
#include "flags.h"
#include "toplev.h"
static int *uid_suid;
#define INSN_SUID(INSN) (uid_suid[INSN_UID (INSN)])
static int last_call_suid;
static int last_setjmp_suid;
static int *reg_where_dead;
static struct insn_chain **reg_where_dead_chain;
static int *reg_where_born_exact;
static int *reg_where_born_clobber;
#define REG_WHERE_BORN(N) \
(reg_where_born_exact[(N)] - reg_where_born_clobber[(N)])
static int *reg_order;
static char *regs_live;
static char *regs_change_size;
static char *regs_crosses_setjmp;
static HARD_REG_SET *after_insn_hard_regs;
#define MARK_LIVE_AFTER(INSN,REGNO) \
SET_HARD_REG_BIT (after_insn_hard_regs[INSN_SUID (INSN)], (REGNO))
static int stupid_reg_compare PROTO((const GENERIC_PTR,const GENERIC_PTR));
static int stupid_find_reg PROTO((int, enum reg_class, enum machine_mode,
int, int, int));
static void stupid_mark_refs PROTO((rtx, struct insn_chain *));
static void find_clobbered_regs PROTO((rtx, rtx));
static struct insn_chain *current_chain;
static void
find_clobbered_regs (reg, setter)
rtx reg, setter;
{
int regno, nregs;
if (setter == 0 || GET_CODE (setter) != CLOBBER)
return;
if (GET_CODE (reg) == SUBREG)
reg = SUBREG_REG (reg);
if (GET_CODE (reg) != REG)
return;
regno = REGNO (reg);
if (regno >= FIRST_PSEUDO_REGISTER)
return;
if (GET_MODE (reg) == VOIDmode)
abort ();
else
nregs = HARD_REGNO_NREGS (regno, GET_MODE (reg));
while (nregs-- > 0)
{
SET_REGNO_REG_SET (current_chain->live_after, regno);
SET_REGNO_REG_SET (current_chain->live_before, regno++);
}
}
void
stupid_life_analysis (f, nregs, file)
rtx f;
int nregs;
FILE *file;
{
register int i;
register rtx last, insn;
int max_uid, max_suid;
current_function_has_computed_jump = 0;
bzero (regs_ever_live, sizeof regs_ever_live);
regs_live = (char *) xmalloc (nregs);
for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
if (INSN_UID (insn) > i)
i = INSN_UID (insn);
max_uid = i + 1;
uid_suid = (int *) xmalloc ((i + 1) * sizeof (int));
last = 0;
for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
{
if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
last = insn;
INSN_SUID (insn) = ++i;
}
last_call_suid = i + 1;
last_setjmp_suid = i + 1;
max_suid = i + 1;
max_regno = nregs;
reg_where_dead = (int *) xmalloc (nregs * sizeof (int));
bzero ((char *) reg_where_dead, nregs * sizeof (int));
reg_where_born_exact = (int *) xmalloc (nregs * sizeof (int));
bzero ((char *) reg_where_born_exact, nregs * sizeof (int));
reg_where_born_clobber = (int *) xmalloc (nregs * sizeof (int));
bzero ((char *) reg_where_born_clobber, nregs * sizeof (int));
reg_where_dead_chain = (struct insn_chain **) xmalloc (nregs * sizeof (struct insn_chain *));
bzero ((char *) reg_where_dead_chain, nregs * sizeof (struct insn_chain *));
reg_order = (int *) xmalloc (nregs * sizeof (int));
bzero ((char *) reg_order, nregs * sizeof (int));
regs_change_size = (char *) xmalloc (nregs * sizeof (char));
bzero ((char *) regs_change_size, nregs * sizeof (char));
regs_crosses_setjmp = (char *) xmalloc (nregs * sizeof (char));
bzero ((char *) regs_crosses_setjmp, nregs * sizeof (char));
allocate_reg_info (max_regno, FALSE, TRUE);
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
reg_renumber[i] = i;
after_insn_hard_regs
= (HARD_REG_SET *) xmalloc (max_suid * sizeof (HARD_REG_SET));
bzero ((char *) after_insn_hard_regs, max_suid * sizeof (HARD_REG_SET));
allocate_reg_life_data ();
allocate_bb_life_data ();
for (i = 0; i < max_regno; i++)
REG_N_DEATHS (i) = 1;
bzero (regs_live, nregs);
reload_insn_chain = 0;
for (insn = last; insn; insn = PREV_INSN (insn))
{
register HARD_REG_SET *p = after_insn_hard_regs + INSN_SUID (insn);
struct insn_chain *chain;
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
if (regs_live[i])
SET_HARD_REG_BIT (*p, i);
if (GET_CODE (insn) != NOTE && GET_CODE (insn) != BARRIER)
{
chain = new_insn_chain ();
if (reload_insn_chain)
reload_insn_chain->prev = chain;
chain->next = reload_insn_chain;
chain->prev = 0;
reload_insn_chain = chain;
chain->block = 0;
chain->insn = insn;
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
if (regs_live[i])
SET_REGNO_REG_SET (chain->live_before, i);
}
if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
stupid_mark_refs (PATTERN (insn), chain);
if (GET_CODE (insn) == NOTE
&& NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)
last_setjmp_suid = INSN_SUID (insn);
if (GET_CODE (insn) == CALL_INSN)
{
last_call_suid = INSN_SUID (insn);
if (current_function_has_nonlocal_label)
{
IOR_COMPL_HARD_REG_SET (after_insn_hard_regs[last_call_suid],
fixed_reg_set);
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
if (! fixed_regs[i])
regs_live[i] = 0;
}
else
{
IOR_HARD_REG_SET (after_insn_hard_regs[last_call_suid],
call_used_reg_set);
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
if (call_used_regs[i])
regs_live[i] = 0;
}
stupid_mark_refs (CALL_INSN_FUNCTION_USAGE (insn), chain);
}
if (GET_CODE (insn) != NOTE && GET_CODE (insn) != BARRIER)
{
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
if (regs_live[i])
SET_REGNO_REG_SET (chain->live_after, i);
current_chain = chain;
if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
note_stores (PATTERN (insn), find_clobbered_regs);
}
if (GET_CODE (insn) == JUMP_INSN && computed_jump_p (insn))
current_function_has_computed_jump = 1;
}
for (i = LAST_VIRTUAL_REGISTER + 1; i < max_regno; i++)
reg_order[i] = i;
qsort (®_order[LAST_VIRTUAL_REGISTER + 1],
max_regno - LAST_VIRTUAL_REGISTER - 1, sizeof (int),
stupid_reg_compare);
for (i = LAST_VIRTUAL_REGISTER + 1; i < max_regno; i++)
{
register int r = reg_order[i];
if (regno_reg_rtx[r] == 0 || regs_crosses_setjmp[r]
|| (reg_where_born_exact[r] == 0 && reg_where_dead[r] == 0)
|| (REG_N_CALLS_CROSSED (r) > 0
&& current_function_has_nonlocal_label))
continue;
if (N_REG_CLASSES > 1)
reg_renumber[r] = stupid_find_reg (REG_N_CALLS_CROSSED (r),
reg_preferred_class (r),
PSEUDO_REGNO_MODE (r),
REG_WHERE_BORN (r),
reg_where_dead[r],
regs_change_size[r]);
if (reg_renumber[r] == -1 && reg_alternate_class (r) != NO_REGS)
reg_renumber[r] = stupid_find_reg (REG_N_CALLS_CROSSED (r),
reg_alternate_class (r),
PSEUDO_REGNO_MODE (r),
REG_WHERE_BORN (r),
reg_where_dead[r],
regs_change_size[r]);
}
for (i = LAST_VIRTUAL_REGISTER + 1; i < max_regno; i++)
{
struct insn_chain *chain;
int regno;
regno = reg_renumber[i];
if (regno < 0)
continue;
chain = reg_where_dead_chain[i];
if (reg_where_dead[i] > INSN_SUID (chain->insn))
SET_REGNO_REG_SET (chain->live_after, i);
while (INSN_SUID (chain->insn) > reg_where_born_exact[i])
{
SET_REGNO_REG_SET (chain->live_before, i);
chain = chain->prev;
if (!chain)
break;
SET_REGNO_REG_SET (chain->live_after, i);
}
if (INSN_SUID (chain->insn) == reg_where_born_exact[i]
&& reg_where_born_clobber[i])
SET_REGNO_REG_SET (chain->live_before, i);
}
if (file)
dump_flow_info (file);
free (regs_live);
free (uid_suid);
free (reg_where_dead);
free (reg_where_born_exact);
free (reg_where_born_clobber);
free (reg_where_dead_chain);
free (reg_order);
free (regs_change_size);
free (regs_crosses_setjmp);
free (after_insn_hard_regs);
}
static int
stupid_reg_compare (r1p, r2p)
const GENERIC_PTR r1p;
const GENERIC_PTR r2p;
{
register int r1 = *(int *)r1p, r2 = *(int *)r2p;
register int len1 = reg_where_dead[r1] - REG_WHERE_BORN (r1);
register int len2 = reg_where_dead[r2] - REG_WHERE_BORN (r2);
int tem;
tem = len2 - len1;
if (tem != 0)
return tem;
tem = REG_N_REFS (r1) - REG_N_REFS (r2);
if (tem != 0)
return tem;
return r1 - r2;
}
static int
stupid_find_reg (call_preserved, class, mode,
born_insn, dead_insn, changes_size)
int call_preserved;
enum reg_class class;
enum machine_mode mode;
int born_insn, dead_insn;
int changes_size ATTRIBUTE_UNUSED;
{
register int i, ins;
#ifdef HARD_REG_SET
register
#endif
HARD_REG_SET used, this_reg;
#ifdef ELIMINABLE_REGS
static struct {int from, to; } eliminables[] = ELIMINABLE_REGS;
#endif
if (dead_insn > born_insn + 5000)
return -1;
COPY_HARD_REG_SET (used,
call_preserved ? call_used_reg_set : fixed_reg_set);
#ifdef ELIMINABLE_REGS
for (i = 0; i < (int)(sizeof eliminables / sizeof eliminables[0]); i++)
SET_HARD_REG_BIT (used, eliminables[i].from);
#if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
SET_HARD_REG_BIT (used, HARD_FRAME_POINTER_REGNUM);
#endif
#else
SET_HARD_REG_BIT (used, FRAME_POINTER_REGNUM);
#endif
for (ins = born_insn; ins < dead_insn; ins++)
IOR_HARD_REG_SET (used, after_insn_hard_regs[ins]);
#ifdef STACK_REGS
if (current_function_has_computed_jump)
for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++)
SET_HARD_REG_BIT (used, i);
#endif
IOR_COMPL_HARD_REG_SET (used, reg_class_contents[(int) class]);
#ifdef CLASS_CANNOT_CHANGE_SIZE
if (changes_size)
IOR_HARD_REG_SET (used,
reg_class_contents[(int) CLASS_CANNOT_CHANGE_SIZE]);
#endif
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
{
#ifdef REG_ALLOC_ORDER
int regno = reg_alloc_order[i];
#else
int regno = i;
#endif
#ifdef OVERLAPPING_REGNO_P
if (OVERLAPPING_REGNO_P (regno))
continue;
#endif
if (! TEST_HARD_REG_BIT (used, regno)
&& HARD_REGNO_MODE_OK (regno, mode))
{
register int j;
register int size1 = HARD_REGNO_NREGS (regno, mode);
for (j = 1; j < size1 && ! TEST_HARD_REG_BIT (used, regno + j); j++);
if (j == size1)
{
CLEAR_HARD_REG_SET (this_reg);
while (--j >= 0)
SET_HARD_REG_BIT (this_reg, regno + j);
for (ins = born_insn; ins < dead_insn; ins++)
{
IOR_HARD_REG_SET (after_insn_hard_regs[ins], this_reg);
}
return regno;
}
#ifndef REG_ALLOC_ORDER
i += j;
#endif
}
}
return -1;
}
static void
stupid_mark_refs (x, chain)
rtx x;
struct insn_chain *chain;
{
register RTX_CODE code;
register char *fmt;
register int regno, i;
rtx insn = chain->insn;
if (x == 0)
return;
code = GET_CODE (x);
if (code == SET || code == CLOBBER)
{
if (SET_DEST (x) != 0
&& (GET_CODE (SET_DEST (x)) == REG
|| (GET_CODE (SET_DEST (x)) == SUBREG
&& GET_CODE (SUBREG_REG (SET_DEST (x))) == REG
&& (REGNO (SUBREG_REG (SET_DEST (x)))
>= FIRST_PSEUDO_REGISTER))))
{
if (GET_CODE (SET_DEST (x)) == SUBREG)
regno = REGNO (SUBREG_REG (SET_DEST (x)));
else
regno = REGNO (SET_DEST (x));
if (regno < FIRST_PSEUDO_REGISTER)
{
register int j
= HARD_REGNO_NREGS (regno, GET_MODE (SET_DEST (x)));
while (--j >= 0)
{
regs_ever_live[regno+j] = 1;
regs_live[regno+j] = 0;
MARK_LIVE_AFTER (insn, regno+j);
if (code == CLOBBER && INSN_SUID (insn) > 0)
SET_HARD_REG_BIT (after_insn_hard_regs[INSN_SUID (insn) - 1],
regno+j);
}
}
else
{
int where_born = INSN_SUID (insn) - (code == CLOBBER);
reg_where_born_exact[regno] = INSN_SUID (insn);
reg_where_born_clobber[regno] = (code == CLOBBER);
if (reg_where_dead_chain[regno] == 0)
reg_where_dead_chain[regno] = chain;
if (reg_where_dead[regno] < where_born + 2)
{
reg_where_dead[regno] = where_born + 2;
regs_live[regno] = 1;
}
REG_N_REFS (regno)++;
if (last_call_suid < reg_where_dead[regno])
REG_N_CALLS_CROSSED (regno) += 1;
if (last_setjmp_suid < reg_where_dead[regno])
regs_crosses_setjmp[regno] = 1;
if (GET_CODE (SET_DEST (x)) == REG
&& (code == CLOBBER
|| (REGNO_FIRST_UID (regno) == INSN_UID (insn)
&& REGNO_LAST_UID (regno) == INSN_UID (insn)
&& ! reg_mentioned_p (SET_DEST (x),
SET_SRC (x)))))
REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_UNUSED,
SET_DEST (x),
REG_NOTES (insn));
}
}
if (code == SET)
{
stupid_mark_refs (SET_SRC (x), chain);
if (GET_CODE (SET_DEST (x)) != REG)
stupid_mark_refs (SET_DEST (x), chain);
}
return;
}
else if (code == SUBREG
&& GET_CODE (SUBREG_REG (x)) == REG
&& REGNO (SUBREG_REG (x)) >= FIRST_PSEUDO_REGISTER
&& (GET_MODE_SIZE (GET_MODE (x))
!= GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
&& (INTEGRAL_MODE_P (GET_MODE (x))
|| INTEGRAL_MODE_P (GET_MODE (SUBREG_REG (x)))))
regs_change_size[REGNO (SUBREG_REG (x))] = 1;
else if (code == REG)
{
regno = REGNO (x);
if (regno < FIRST_PSEUDO_REGISTER)
{
register int j = HARD_REGNO_NREGS (regno, GET_MODE (x));
while (--j >= 0)
{
regs_ever_live[regno+j] = 1;
regs_live[regno+j] = 1;
}
}
else
{
reg_where_born_exact[regno] = INSN_SUID (insn);
reg_where_born_clobber[regno] = 0;
REG_N_REFS (regno)++;
if (regs_live[regno] == 0)
{
regs_live[regno] = 1;
reg_where_dead[regno] = INSN_SUID (insn);
reg_where_dead_chain[regno] = chain;
}
}
return;
}
fmt = GET_RTX_FORMAT (code);
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
{
if (fmt[i] == 'e')
stupid_mark_refs (XEXP (x, i), chain);
if (fmt[i] == 'E')
{
register int j;
for (j = XVECLEN (x, i) - 1; j >= 0; j--)
stupid_mark_refs (XVECEXP (x, i, j), chain);
}
}
}