#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "hard-reg-set.h"
#include "rtl.h"
#include "tm_p.h"
#include "flags.h"
#include "basic-block.h"
#include "regs.h"
#include "function.h"
#include "insn-config.h"
#include "insn-attr.h"
#include "recog.h"
#include "output.h"
#include "toplev.h"
#include "except.h"
#include "integrate.h"
static int next_qty;
struct qty
{
int n_refs;
int freq;
int birth;
int death;
int size;
int n_calls_crossed;
int first_reg;
enum reg_class min_class;
enum reg_class alternate_class;
enum machine_mode mode;
short phys_reg;
};
static struct qty *qty;
static HARD_REG_SET *qty_phys_copy_sugg;
static HARD_REG_SET *qty_phys_sugg;
static short *qty_phys_num_copy_sugg;
static short *qty_phys_num_sugg;
static int *reg_next_in_qty;
static int *reg_qty;
static char *reg_offset;
short *reg_renumber;
static HARD_REG_SET regs_live;
static HARD_REG_SET *regs_live_at;
static int this_insn_number;
static rtx this_insn;
struct equivalence
{
char replace;
rtx replacement;
rtx *src_p;
int loop_depth;
rtx init_insns;
};
static struct equivalence *reg_equiv;
static int recorded_label_ref;
static void alloc_qty (int, enum machine_mode, int, int);
static void validate_equiv_mem_from_store (rtx, rtx, void *);
static int validate_equiv_mem (rtx, rtx, rtx);
static int equiv_init_varies_p (rtx);
static int equiv_init_movable_p (rtx, int);
static int contains_replace_regs (rtx);
static int memref_referenced_p (rtx, rtx);
static int memref_used_between_p (rtx, rtx, rtx);
static void update_equiv_regs (void);
static void no_equiv (rtx, rtx, void *);
static void block_alloc (int);
static int qty_sugg_compare (int, int);
static int qty_sugg_compare_1 (const void *, const void *);
static int qty_compare (int, int);
static int qty_compare_1 (const void *, const void *);
static int combine_regs (rtx, rtx, int, int, rtx, int);
static int reg_meets_class_p (int, enum reg_class);
static void update_qty_class (int, int);
static void reg_is_set (rtx, rtx, void *);
static void reg_is_born (rtx, int);
static void wipe_dead_reg (rtx, int);
static int find_free_reg (enum reg_class, enum machine_mode, int, int, int,
int, int);
static void mark_life (int, enum machine_mode, int);
static void post_mark_life (int, enum machine_mode, int, int, int);
static int no_conflict_p (rtx, rtx, rtx);
static int requires_inout (const char *);
static void
alloc_qty (int regno, enum machine_mode mode, int size, int birth)
{
int qtyno = next_qty++;
reg_qty[regno] = qtyno;
reg_offset[regno] = 0;
reg_next_in_qty[regno] = -1;
qty[qtyno].first_reg = regno;
qty[qtyno].size = size;
qty[qtyno].mode = mode;
qty[qtyno].birth = birth;
qty[qtyno].n_calls_crossed = REG_N_CALLS_CROSSED (regno);
qty[qtyno].min_class = reg_preferred_class (regno);
qty[qtyno].alternate_class = reg_alternate_class (regno);
qty[qtyno].n_refs = REG_N_REFS (regno);
qty[qtyno].freq = REG_FREQ (regno);
}
int
local_alloc (void)
{
int i;
int max_qty;
basic_block b;
recorded_label_ref = 0;
#ifdef ORDER_REGS_FOR_LOCAL_ALLOC
ORDER_REGS_FOR_LOCAL_ALLOC;
#endif
if (optimize)
update_equiv_regs ();
max_qty = (max_regno - FIRST_PSEUDO_REGISTER);
qty = xmalloc (max_qty * sizeof (struct qty));
qty_phys_copy_sugg = xmalloc (max_qty * sizeof (HARD_REG_SET));
qty_phys_num_copy_sugg = xmalloc (max_qty * sizeof (short));
qty_phys_sugg = xmalloc (max_qty * sizeof (HARD_REG_SET));
qty_phys_num_sugg = xmalloc (max_qty * sizeof (short));
reg_qty = xmalloc (max_regno * sizeof (int));
reg_offset = xmalloc (max_regno * sizeof (char));
reg_next_in_qty = xmalloc (max_regno * sizeof (int));
for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
{
if (REG_BASIC_BLOCK (i) >= 0 && REG_N_DEATHS (i) == 1)
reg_qty[i] = -2;
else
reg_qty[i] = -1;
}
next_qty = max_qty;
FOR_EACH_BB (b)
{
if (next_qty < 6)
{
for (i = 0; i < next_qty; i++)
{
CLEAR_HARD_REG_SET (qty_phys_copy_sugg[i]);
qty_phys_num_copy_sugg[i] = 0;
CLEAR_HARD_REG_SET (qty_phys_sugg[i]);
qty_phys_num_sugg[i] = 0;
}
}
else
{
#define CLEAR(vector) \
memset ((vector), 0, (sizeof (*(vector))) * next_qty);
CLEAR (qty_phys_copy_sugg);
CLEAR (qty_phys_num_copy_sugg);
CLEAR (qty_phys_sugg);
CLEAR (qty_phys_num_sugg);
}
next_qty = 0;
block_alloc (b->index);
}
free (qty);
free (qty_phys_copy_sugg);
free (qty_phys_num_copy_sugg);
free (qty_phys_sugg);
free (qty_phys_num_sugg);
free (reg_qty);
free (reg_offset);
free (reg_next_in_qty);
return recorded_label_ref;
}
static rtx equiv_mem;
static int equiv_mem_modified;
static void
validate_equiv_mem_from_store (rtx dest, rtx set ATTRIBUTE_UNUSED,
void *data ATTRIBUTE_UNUSED)
{
if ((REG_P (dest)
&& reg_overlap_mentioned_p (dest, equiv_mem))
|| (MEM_P (dest)
&& true_dependence (dest, VOIDmode, equiv_mem, rtx_varies_p)))
equiv_mem_modified = 1;
}
static int
validate_equiv_mem (rtx start, rtx reg, rtx memref)
{
rtx insn;
rtx note;
equiv_mem = memref;
equiv_mem_modified = 0;
if (side_effects_p (memref))
return 0;
for (insn = start; insn && ! equiv_mem_modified; insn = NEXT_INSN (insn))
{
if (! INSN_P (insn))
continue;
if (find_reg_note (insn, REG_DEAD, reg))
return 1;
if (CALL_P (insn) && ! MEM_READONLY_P (memref)
&& ! CONST_OR_PURE_CALL_P (insn))
return 0;
note_stores (PATTERN (insn), validate_equiv_mem_from_store, NULL);
for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
if ((REG_NOTE_KIND (note) == REG_INC
|| REG_NOTE_KIND (note) == REG_DEAD)
&& REG_P (XEXP (note, 0))
&& reg_overlap_mentioned_p (XEXP (note, 0), memref))
return 0;
}
return 0;
}
static int
equiv_init_varies_p (rtx x)
{
RTX_CODE code = GET_CODE (x);
int i;
const char *fmt;
switch (code)
{
case MEM:
return !MEM_READONLY_P (x) || equiv_init_varies_p (XEXP (x, 0));
case CONST:
case CONST_INT:
case CONST_DOUBLE:
case CONST_VECTOR:
case SYMBOL_REF:
case LABEL_REF:
return 0;
case REG:
return reg_equiv[REGNO (x)].replace == 0 && rtx_varies_p (x, 0);
case ASM_OPERANDS:
if (MEM_VOLATILE_P (x))
return 1;
default:
break;
}
fmt = GET_RTX_FORMAT (code);
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
if (fmt[i] == 'e')
{
if (equiv_init_varies_p (XEXP (x, i)))
return 1;
}
else if (fmt[i] == 'E')
{
int j;
for (j = 0; j < XVECLEN (x, i); j++)
if (equiv_init_varies_p (XVECEXP (x, i, j)))
return 1;
}
return 0;
}
static int
equiv_init_movable_p (rtx x, int regno)
{
int i, j;
const char *fmt;
enum rtx_code code = GET_CODE (x);
switch (code)
{
case SET:
return equiv_init_movable_p (SET_SRC (x), regno);
case CC0:
case CLOBBER:
return 0;
case PRE_INC:
case PRE_DEC:
case POST_INC:
case POST_DEC:
case PRE_MODIFY:
case POST_MODIFY:
return 0;
case REG:
return (reg_equiv[REGNO (x)].loop_depth >= reg_equiv[regno].loop_depth
&& reg_equiv[REGNO (x)].replace)
|| (REG_BASIC_BLOCK (REGNO (x)) < 0 && ! rtx_varies_p (x, 0));
case UNSPEC_VOLATILE:
return 0;
case ASM_OPERANDS:
if (MEM_VOLATILE_P (x))
return 0;
default:
break;
}
fmt = GET_RTX_FORMAT (code);
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
switch (fmt[i])
{
case 'e':
if (! equiv_init_movable_p (XEXP (x, i), regno))
return 0;
break;
case 'E':
for (j = XVECLEN (x, i) - 1; j >= 0; j--)
if (! equiv_init_movable_p (XVECEXP (x, i, j), regno))
return 0;
break;
}
return 1;
}
static int
contains_replace_regs (rtx x)
{
int i, j;
const char *fmt;
enum rtx_code code = GET_CODE (x);
switch (code)
{
case CONST_INT:
case CONST:
case LABEL_REF:
case SYMBOL_REF:
case CONST_DOUBLE:
case CONST_VECTOR:
case PC:
case CC0:
case HIGH:
return 0;
case REG:
return reg_equiv[REGNO (x)].replace;
default:
break;
}
fmt = GET_RTX_FORMAT (code);
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
switch (fmt[i])
{
case 'e':
if (contains_replace_regs (XEXP (x, i)))
return 1;
break;
case 'E':
for (j = XVECLEN (x, i) - 1; j >= 0; j--)
if (contains_replace_regs (XVECEXP (x, i, j)))
return 1;
break;
}
return 0;
}
static int
memref_referenced_p (rtx memref, rtx x)
{
int i, j;
const char *fmt;
enum rtx_code code = GET_CODE (x);
switch (code)
{
case CONST_INT:
case CONST:
case LABEL_REF:
case SYMBOL_REF:
case CONST_DOUBLE:
case CONST_VECTOR:
case PC:
case CC0:
case HIGH:
case LO_SUM:
return 0;
case REG:
return (reg_equiv[REGNO (x)].replacement
&& memref_referenced_p (memref,
reg_equiv[REGNO (x)].replacement));
case MEM:
if (true_dependence (memref, VOIDmode, x, rtx_varies_p))
return 1;
break;
case SET:
if (MEM_P (SET_DEST (x)))
{
if (memref_referenced_p (memref, XEXP (SET_DEST (x), 0)))
return 1;
}
else if (memref_referenced_p (memref, SET_DEST (x)))
return 1;
return memref_referenced_p (memref, SET_SRC (x));
default:
break;
}
fmt = GET_RTX_FORMAT (code);
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
switch (fmt[i])
{
case 'e':
if (memref_referenced_p (memref, XEXP (x, i)))
return 1;
break;
case 'E':
for (j = XVECLEN (x, i) - 1; j >= 0; j--)
if (memref_referenced_p (memref, XVECEXP (x, i, j)))
return 1;
break;
}
return 0;
}
static int
memref_used_between_p (rtx memref, rtx start, rtx end)
{
rtx insn;
for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
insn = NEXT_INSN (insn))
if (INSN_P (insn) && memref_referenced_p (memref, PATTERN (insn)))
return 1;
return 0;
}
static void
update_equiv_regs (void)
{
rtx insn;
basic_block bb;
int loop_depth;
regset_head cleared_regs;
int clear_regnos = 0;
reg_equiv = xcalloc (max_regno, sizeof *reg_equiv);
INIT_REG_SET (&cleared_regs);
init_alias_analysis ();
FOR_EACH_BB (bb)
{
loop_depth = bb->loop_depth;
for (insn = BB_HEAD (bb);
insn != NEXT_INSN (BB_END (bb));
insn = NEXT_INSN (insn))
{
rtx note;
rtx set;
rtx dest, src;
int regno;
if (! INSN_P (insn))
continue;
for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
if (REG_NOTE_KIND (note) == REG_INC)
no_equiv (XEXP (note, 0), note, NULL);
set = single_set (insn);
if (set == 0)
{
note_stores (PATTERN (insn), no_equiv, NULL);
continue;
}
else if (GET_CODE (PATTERN (insn)) == PARALLEL)
{
int i;
for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
{
rtx part = XVECEXP (PATTERN (insn), 0, i);
if (part != set)
note_stores (part, no_equiv, NULL);
}
}
dest = SET_DEST (set);
src = SET_SRC (set);
if (MEM_P (dest) && REG_P (src)
&& (regno = REGNO (src)) >= FIRST_PSEUDO_REGISTER
&& REG_BASIC_BLOCK (regno) >= 0
&& REG_N_SETS (regno) == 1
&& reg_equiv[regno].init_insns != 0
&& reg_equiv[regno].init_insns != const0_rtx
&& ! find_reg_note (XEXP (reg_equiv[regno].init_insns, 0),
REG_EQUIV, NULL_RTX)
&& ! contains_replace_regs (XEXP (dest, 0)))
{
rtx init_insn = XEXP (reg_equiv[regno].init_insns, 0);
if (validate_equiv_mem (init_insn, src, dest)
&& ! memref_used_between_p (dest, init_insn, insn))
REG_NOTES (init_insn)
= gen_rtx_EXPR_LIST (REG_EQUIV, dest, REG_NOTES (init_insn));
}
if (!REG_P (dest)
|| (regno = REGNO (dest)) < FIRST_PSEUDO_REGISTER
|| reg_equiv[regno].init_insns == const0_rtx
|| (CLASS_LIKELY_SPILLED_P (reg_preferred_class (regno))
&& MEM_P (src)))
{
note_stores (set, no_equiv, NULL);
continue;
}
note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
if (! note && ! rtx_varies_p (src, 0))
note = set_unique_reg_note (insn, REG_EQUAL, src);
if (note && GET_CODE (XEXP (note, 0)) == EXPR_LIST)
note = NULL_RTX;
if (REG_N_SETS (regno) != 1
&& (! note
|| rtx_varies_p (XEXP (note, 0), 0)
|| (reg_equiv[regno].replacement
&& ! rtx_equal_p (XEXP (note, 0),
reg_equiv[regno].replacement))))
{
no_equiv (dest, set, NULL);
continue;
}
reg_equiv[regno].init_insns
= gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv[regno].init_insns);
if (note && ! rtx_varies_p (XEXP (note, 0), 0))
PUT_MODE (note, (enum machine_mode) REG_EQUIV);
note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
if (note == 0 && REG_BASIC_BLOCK (regno) >= 0
&& MEM_P (SET_SRC (set))
&& validate_equiv_mem (insn, dest, SET_SRC (set)))
REG_NOTES (insn) = note = gen_rtx_EXPR_LIST (REG_EQUIV, SET_SRC (set),
REG_NOTES (insn));
if (note)
{
int regno = REGNO (dest);
if (GET_CODE (XEXP (note, 0)) == LABEL_REF
|| (GET_CODE (XEXP (note, 0)) == CONST
&& GET_CODE (XEXP (XEXP (note, 0), 0)) == PLUS
&& (GET_CODE (XEXP (XEXP (XEXP (note, 0), 0), 0))
== LABEL_REF)))
recorded_label_ref = 1;
reg_equiv[regno].replacement = XEXP (note, 0);
reg_equiv[regno].src_p = &SET_SRC (set);
reg_equiv[regno].loop_depth = loop_depth;
if (REG_LIVE_LENGTH (regno) >= 0 && optimize)
{
REG_LIVE_LENGTH (regno) *= 2;
if (REG_N_REFS (regno) == 2
&& (rtx_equal_p (XEXP (note, 0), src)
|| ! equiv_init_varies_p (src))
&& NONJUMP_INSN_P (insn)
&& equiv_init_movable_p (PATTERN (insn), regno))
reg_equiv[regno].replace = 1;
}
}
}
}
FOR_EACH_BB_REVERSE (bb)
{
loop_depth = bb->loop_depth;
for (insn = BB_END (bb);
insn != PREV_INSN (BB_HEAD (bb));
insn = PREV_INSN (insn))
{
rtx link;
if (! INSN_P (insn))
continue;
if (JUMP_P (insn)
&& find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX))
continue;
for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
{
if (REG_NOTE_KIND (link) == REG_DEAD
&& reg_mentioned_p (XEXP (link, 0), PATTERN (insn)))
{
int regno = REGNO (XEXP (link, 0));
rtx equiv_insn;
if (! reg_equiv[regno].replace
|| reg_equiv[regno].loop_depth < loop_depth)
continue;
if (reg_equiv[regno].init_insns == NULL_RTX
|| XEXP (reg_equiv[regno].init_insns, 1) != NULL_RTX)
abort ();
equiv_insn = XEXP (reg_equiv[regno].init_insns, 0);
if (can_throw_internal (equiv_insn))
continue;
if (asm_noperands (PATTERN (equiv_insn)) < 0
&& validate_replace_rtx (regno_reg_rtx[regno],
*(reg_equiv[regno].src_p), insn))
{
rtx equiv_link;
rtx last_link;
rtx note;
for (last_link = link; XEXP (last_link, 1);
last_link = XEXP (last_link, 1))
;
equiv_link = REG_NOTES (equiv_insn);
while (equiv_link)
{
note = equiv_link;
equiv_link = XEXP (equiv_link, 1);
if (REG_NOTE_KIND (note) == REG_DEAD)
{
remove_note (equiv_insn, note);
XEXP (last_link, 1) = note;
XEXP (note, 1) = NULL_RTX;
last_link = note;
}
}
remove_death (regno, insn);
REG_N_REFS (regno) = 0;
REG_FREQ (regno) = 0;
delete_insn (equiv_insn);
reg_equiv[regno].init_insns
= XEXP (reg_equiv[regno].init_insns, 1);
}
else if (PREV_INSN (insn) != equiv_insn)
{
rtx new_insn;
new_insn = emit_insn_before (PATTERN (equiv_insn), insn);
REG_NOTES (new_insn) = REG_NOTES (equiv_insn);
REG_NOTES (equiv_insn) = 0;
INSN_CODE (new_insn) = INSN_CODE (equiv_insn);
delete_insn (equiv_insn);
XEXP (reg_equiv[regno].init_insns, 0) = new_insn;
REG_BASIC_BLOCK (regno) = bb->index;
REG_N_CALLS_CROSSED (regno) = 0;
REG_LIVE_LENGTH (regno) = 2;
if (insn == BB_HEAD (bb))
BB_HEAD (bb) = PREV_INSN (insn);
SET_REGNO_REG_SET (&cleared_regs, regno);
clear_regnos++;
}
}
}
}
}
if (clear_regnos)
{
int j;
if (clear_regnos > 8)
{
FOR_EACH_BB (bb)
{
AND_COMPL_REG_SET (bb->global_live_at_start, &cleared_regs);
AND_COMPL_REG_SET (bb->global_live_at_end, &cleared_regs);
}
}
else
{
reg_set_iterator rsi;
EXECUTE_IF_SET_IN_REG_SET (&cleared_regs, 0, j, rsi)
{
FOR_EACH_BB (bb)
{
CLEAR_REGNO_REG_SET (bb->global_live_at_start, j);
CLEAR_REGNO_REG_SET (bb->global_live_at_end, j);
}
}
}
}
end_alias_analysis ();
CLEAR_REG_SET (&cleared_regs);
free (reg_equiv);
}
static void
no_equiv (rtx reg, rtx store ATTRIBUTE_UNUSED, void *data ATTRIBUTE_UNUSED)
{
int regno;
rtx list;
if (!REG_P (reg))
return;
regno = REGNO (reg);
list = reg_equiv[regno].init_insns;
if (list == const0_rtx)
return;
for (; list; list = XEXP (list, 1))
{
rtx insn = XEXP (list, 0);
remove_note (insn, find_reg_note (insn, REG_EQUIV, NULL_RTX));
}
reg_equiv[regno].init_insns = const0_rtx;
reg_equiv[regno].replacement = NULL_RTX;
}
static void
block_alloc (int b)
{
int i, q;
rtx insn;
rtx note, hard_reg;
int insn_number = 0;
int insn_count = 0;
int max_uid = get_max_uid ();
int *qty_order;
int no_conflict_combined_regno = -1;
insn = BB_END (BASIC_BLOCK (b));
while (1)
{
if (!NOTE_P (insn))
if (++insn_count > max_uid)
abort ();
if (insn == BB_HEAD (BASIC_BLOCK (b)))
break;
insn = PREV_INSN (insn);
}
regs_live_at = xcalloc ((2 * insn_count + 2), sizeof (HARD_REG_SET));
REG_SET_TO_HARD_REG_SET (regs_live, BASIC_BLOCK (b)->global_live_at_start);
insn = BB_HEAD (BASIC_BLOCK (b));
while (1)
{
if (!NOTE_P (insn))
insn_number++;
if (INSN_P (insn))
{
rtx link, set;
int win = 0;
rtx r0, r1 = NULL_RTX;
int combined_regno = -1;
int i;
this_insn_number = insn_number;
this_insn = insn;
extract_insn (insn);
which_alternative = -1;
if (optimize
&& recog_data.n_operands > 1
&& recog_data.constraints[0][0] == '='
&& recog_data.constraints[0][1] != '&')
{
int must_match_0 = -1;
int n_matching_alts = 0;
for (i = 1; i < recog_data.n_operands; i++)
{
const char *p = recog_data.constraints[i];
int this_match = requires_inout (p);
n_matching_alts += this_match;
if (this_match == recog_data.n_alternatives)
must_match_0 = i;
}
r0 = recog_data.operand[0];
for (i = 1; i < recog_data.n_operands; i++)
{
if (must_match_0 >= 0 && i != must_match_0
&& ! (i == must_match_0 + 1
&& recog_data.constraints[i-1][0] == '%')
&& ! (i == must_match_0 - 1
&& recog_data.constraints[i][0] == '%'))
continue;
if (n_matching_alts == recog_data.n_alternatives
&& 0 == requires_inout (recog_data.constraints[i]))
continue;
r1 = recog_data.operand[i];
if (recog_data.constraints[i][0] == 'p'
|| EXTRA_ADDRESS_CONSTRAINT (recog_data.constraints[i][0],
recog_data.constraints[i]))
while (GET_CODE (r1) == PLUS || GET_CODE (r1) == MULT)
r1 = XEXP (r1, 0);
hard_reg = get_hard_reg_initial_reg (cfun, r1);
if (hard_reg != NULL_RTX)
{
if (REG_P (hard_reg)
&& IN_RANGE (REGNO (hard_reg),
0, FIRST_PSEUDO_REGISTER - 1)
&& ! call_used_regs[REGNO (hard_reg)])
continue;
}
if (REG_P (r0) || GET_CODE (r0) == SUBREG)
{
int may_save_copy
= (r1 == recog_data.operand[i] && must_match_0 >= 0);
if (REG_P (r1) || GET_CODE (r1) == SUBREG)
win = combine_regs (r1, r0, may_save_copy,
insn_number, insn, 0);
}
if (win)
break;
}
}
if (optimize
&& GET_CODE (PATTERN (insn)) == CLOBBER
&& (r0 = XEXP (PATTERN (insn), 0),
REG_P (r0))
&& (link = find_reg_note (insn, REG_LIBCALL, NULL_RTX)) != 0
&& XEXP (link, 0) != 0
&& NONJUMP_INSN_P (XEXP (link, 0))
&& (set = single_set (XEXP (link, 0))) != 0
&& SET_DEST (set) == r0 && SET_SRC (set) == r0
&& (note = find_reg_note (XEXP (link, 0), REG_EQUAL,
NULL_RTX)) != 0)
{
if (r1 = XEXP (note, 0), REG_P (r1)
&& no_conflict_p (insn, r0, r1))
win = combine_regs (r1, r0, 1, insn_number, insn, 1);
else if (GET_RTX_FORMAT (GET_CODE (XEXP (note, 0)))[0] == 'e'
&& (r1 = XEXP (XEXP (note, 0), 0),
REG_P (r1) || GET_CODE (r1) == SUBREG)
&& no_conflict_p (insn, r0, r1))
win = combine_regs (r1, r0, 0, insn_number, insn, 1);
else if (COMMUTATIVE_P (XEXP (note, 0))
&& (r1 = XEXP (XEXP (note, 0), 1),
(REG_P (r1) || GET_CODE (r1) == SUBREG))
&& no_conflict_p (insn, r0, r1))
win = combine_regs (r1, r0, 0, insn_number, insn, 1);
if (win)
no_conflict_combined_regno = REGNO (r1);
}
if (win)
{
while (GET_CODE (r1) == SUBREG)
r1 = SUBREG_REG (r1);
combined_regno = REGNO (r1);
}
for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
if (REG_NOTE_KIND (link) == REG_DEAD
&& REG_P (XEXP (link, 0))
&& combined_regno != (int) REGNO (XEXP (link, 0))
&& (no_conflict_combined_regno != (int) REGNO (XEXP (link, 0))
|| ! find_reg_note (insn, REG_NO_CONFLICT,
XEXP (link, 0))))
wipe_dead_reg (XEXP (link, 0), 0);
note_stores (PATTERN (insn), reg_is_set, NULL);
for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
if (REG_NOTE_KIND (link) == REG_UNUSED
&& REG_P (XEXP (link, 0)))
wipe_dead_reg (XEXP (link, 0), 1);
if ((note = find_reg_note (insn, REG_RETVAL, NULL_RTX)) != 0
&& NONJUMP_INSN_P (XEXP (note, 0))
&& GET_CODE (PATTERN (XEXP (note, 0))) == CLOBBER)
no_conflict_combined_regno = -1;
}
IOR_HARD_REG_SET (regs_live_at[2 * insn_number], regs_live);
IOR_HARD_REG_SET (regs_live_at[2 * insn_number + 1], regs_live);
if (insn == BB_END (BASIC_BLOCK (b)))
break;
insn = NEXT_INSN (insn);
}
qty_order = xmalloc (next_qty * sizeof (int));
for (i = 0; i < next_qty; i++)
qty_order[i] = i;
#define EXCHANGE(I1, I2) \
{ i = qty_order[I1]; qty_order[I1] = qty_order[I2]; qty_order[I2] = i; }
switch (next_qty)
{
case 3:
if (qty_sugg_compare (0, 1) > 0)
EXCHANGE (0, 1);
if (qty_sugg_compare (1, 2) > 0)
EXCHANGE (2, 1);
case 2:
if (qty_sugg_compare (0, 1) > 0)
EXCHANGE (0, 1);
case 1:
case 0:
break;
default:
qsort (qty_order, next_qty, sizeof (int), qty_sugg_compare_1);
}
for (i = 0; i < next_qty; i++)
{
q = qty_order[i];
if (qty_phys_num_sugg[q] != 0 || qty_phys_num_copy_sugg[q] != 0)
qty[q].phys_reg = find_free_reg (qty[q].min_class, qty[q].mode, q,
0, 1, qty[q].birth, qty[q].death);
else
qty[q].phys_reg = -1;
}
for (i = 0; i < next_qty; i++)
qty_order[i] = i;
#define EXCHANGE(I1, I2) \
{ i = qty_order[I1]; qty_order[I1] = qty_order[I2]; qty_order[I2] = i; }
switch (next_qty)
{
case 3:
if (qty_compare (0, 1) > 0)
EXCHANGE (0, 1);
if (qty_compare (1, 2) > 0)
EXCHANGE (2, 1);
case 2:
if (qty_compare (0, 1) > 0)
EXCHANGE (0, 1);
case 1:
case 0:
break;
default:
qsort (qty_order, next_qty, sizeof (int), qty_compare_1);
}
for (i = 0; i < next_qty; i++)
{
q = qty_order[i];
if (qty[q].phys_reg < 0)
{
#ifdef INSN_SCHEDULING
int fake_birth = MAX (0, qty[q].birth - 2 + qty[q].birth % 2);
int fake_death = MIN (insn_number * 2 + 1,
qty[q].death + 2 - qty[q].death % 2);
#endif
if (N_REG_CLASSES > 1)
{
#ifdef INSN_SCHEDULING
if (flag_schedule_insns_after_reload
&& !optimize_size
&& !SMALL_REGISTER_CLASSES)
{
qty[q].phys_reg = find_free_reg (qty[q].min_class,
qty[q].mode, q, 0, 0,
fake_birth, fake_death);
if (qty[q].phys_reg >= 0)
continue;
}
#endif
qty[q].phys_reg = find_free_reg (qty[q].min_class,
qty[q].mode, q, 0, 0,
qty[q].birth, qty[q].death);
if (qty[q].phys_reg >= 0)
continue;
}
#ifdef INSN_SCHEDULING
if (flag_schedule_insns_after_reload
&& !optimize_size
&& !SMALL_REGISTER_CLASSES
&& qty[q].alternate_class != NO_REGS)
qty[q].phys_reg = find_free_reg (qty[q].alternate_class,
qty[q].mode, q, 0, 0,
fake_birth, fake_death);
#endif
if (qty[q].alternate_class != NO_REGS)
qty[q].phys_reg = find_free_reg (qty[q].alternate_class,
qty[q].mode, q, 0, 0,
qty[q].birth, qty[q].death);
}
}
for (q = 0; q < next_qty; q++)
if (qty[q].phys_reg >= 0)
{
for (i = qty[q].first_reg; i >= 0; i = reg_next_in_qty[i])
reg_renumber[i] = qty[q].phys_reg + reg_offset[i];
}
free (regs_live_at);
free (qty_order);
}
#define QTY_CMP_PRI(q) \
((int) (((double) (floor_log2 (qty[q].n_refs) * qty[q].freq * qty[q].size) \
/ (qty[q].death - qty[q].birth)) * (10000 / REG_FREQ_MAX)))
static int
qty_compare (int q1, int q2)
{
return QTY_CMP_PRI (q2) - QTY_CMP_PRI (q1);
}
static int
qty_compare_1 (const void *q1p, const void *q2p)
{
int q1 = *(const int *) q1p, q2 = *(const int *) q2p;
int tem = QTY_CMP_PRI (q2) - QTY_CMP_PRI (q1);
if (tem != 0)
return tem;
return q1 - q2;
}
#define QTY_CMP_SUGG(q) \
(qty_phys_num_copy_sugg[q] \
? qty_phys_num_copy_sugg[q] \
: qty_phys_num_sugg[q] * FIRST_PSEUDO_REGISTER)
static int
qty_sugg_compare (int q1, int q2)
{
int tem = QTY_CMP_SUGG (q1) - QTY_CMP_SUGG (q2);
if (tem != 0)
return tem;
return QTY_CMP_PRI (q2) - QTY_CMP_PRI (q1);
}
static int
qty_sugg_compare_1 (const void *q1p, const void *q2p)
{
int q1 = *(const int *) q1p, q2 = *(const int *) q2p;
int tem = QTY_CMP_SUGG (q1) - QTY_CMP_SUGG (q2);
if (tem != 0)
return tem;
tem = QTY_CMP_PRI (q2) - QTY_CMP_PRI (q1);
if (tem != 0)
return tem;
return q1 - q2;
}
#undef QTY_CMP_SUGG
#undef QTY_CMP_PRI
static int
combine_regs (rtx usedreg, rtx setreg, int may_save_copy, int insn_number,
rtx insn, int already_dead)
{
int ureg, sreg;
int offset = 0;
int usize, ssize;
int sqty;
while (GET_CODE (usedreg) == SUBREG)
{
rtx subreg = SUBREG_REG (usedreg);
if (REG_P (subreg))
{
if (GET_MODE_SIZE (GET_MODE (subreg)) > UNITS_PER_WORD)
may_save_copy = 0;
if (REGNO (subreg) < FIRST_PSEUDO_REGISTER)
offset += subreg_regno_offset (REGNO (subreg),
GET_MODE (subreg),
SUBREG_BYTE (usedreg),
GET_MODE (usedreg));
else
offset += (SUBREG_BYTE (usedreg)
/ REGMODE_NATURAL_SIZE (GET_MODE (usedreg)));
}
usedreg = subreg;
}
if (!REG_P (usedreg))
return 0;
ureg = REGNO (usedreg);
if (ureg < FIRST_PSEUDO_REGISTER)
usize = hard_regno_nregs[ureg][GET_MODE (usedreg)];
else
usize = ((GET_MODE_SIZE (GET_MODE (usedreg))
+ (REGMODE_NATURAL_SIZE (GET_MODE (usedreg)) - 1))
/ REGMODE_NATURAL_SIZE (GET_MODE (usedreg)));
while (GET_CODE (setreg) == SUBREG)
{
rtx subreg = SUBREG_REG (setreg);
if (REG_P (subreg))
{
if (GET_MODE_SIZE (GET_MODE (subreg)) > UNITS_PER_WORD)
may_save_copy = 0;
if (REGNO (subreg) < FIRST_PSEUDO_REGISTER)
offset -= subreg_regno_offset (REGNO (subreg),
GET_MODE (subreg),
SUBREG_BYTE (setreg),
GET_MODE (setreg));
else
offset -= (SUBREG_BYTE (setreg)
/ REGMODE_NATURAL_SIZE (GET_MODE (setreg)));
}
setreg = subreg;
}
if (!REG_P (setreg))
return 0;
sreg = REGNO (setreg);
if (sreg < FIRST_PSEUDO_REGISTER)
ssize = hard_regno_nregs[sreg][GET_MODE (setreg)];
else
ssize = ((GET_MODE_SIZE (GET_MODE (setreg))
+ (REGMODE_NATURAL_SIZE (GET_MODE (setreg)) - 1))
/ REGMODE_NATURAL_SIZE (GET_MODE (setreg)));
if ((ureg >= FIRST_PSEUDO_REGISTER && reg_qty[ureg] < 0)
|| (offset > 0 && usize + offset > ssize)
|| (offset < 0 && usize + offset < ssize)
|| (ssize > usize && ureg >= FIRST_PSEUDO_REGISTER
&& usize < qty[reg_qty[ureg]].size)
|| (sreg >= FIRST_PSEUDO_REGISTER && reg_qty[sreg] == -1)
|| (ureg >= FIRST_PSEUDO_REGISTER
&& find_reg_note (insn, REG_NO_CONFLICT, usedreg))
|| ureg == sreg
|| (ureg < FIRST_PSEUDO_REGISTER && sreg < FIRST_PSEUDO_REGISTER)
|| !MODES_TIEABLE_P (GET_MODE (usedreg), GET_MODE (setreg)))
return 0;
if (ureg < FIRST_PSEUDO_REGISTER)
{
if (reg_qty[sreg] == -2)
reg_is_born (setreg, 2 * insn_number);
if (reg_qty[sreg] >= 0)
{
if (may_save_copy
&& ! TEST_HARD_REG_BIT (qty_phys_copy_sugg[reg_qty[sreg]], ureg))
{
SET_HARD_REG_BIT (qty_phys_copy_sugg[reg_qty[sreg]], ureg);
qty_phys_num_copy_sugg[reg_qty[sreg]]++;
}
else if (! TEST_HARD_REG_BIT (qty_phys_sugg[reg_qty[sreg]], ureg))
{
SET_HARD_REG_BIT (qty_phys_sugg[reg_qty[sreg]], ureg);
qty_phys_num_sugg[reg_qty[sreg]]++;
}
}
return 0;
}
if (sreg < FIRST_PSEUDO_REGISTER)
{
if (may_save_copy
&& ! TEST_HARD_REG_BIT (qty_phys_copy_sugg[reg_qty[ureg]], sreg))
{
SET_HARD_REG_BIT (qty_phys_copy_sugg[reg_qty[ureg]], sreg);
qty_phys_num_copy_sugg[reg_qty[ureg]]++;
}
else if (! TEST_HARD_REG_BIT (qty_phys_sugg[reg_qty[ureg]], sreg))
{
SET_HARD_REG_BIT (qty_phys_sugg[reg_qty[ureg]], sreg);
qty_phys_num_sugg[reg_qty[ureg]]++;
}
return 0;
}
if (reg_qty[sreg] >= -1
|| (current_function_has_nonlocal_label
&& ((REG_N_CALLS_CROSSED (ureg) > 0)
!= (REG_N_CALLS_CROSSED (sreg) > 0))))
return 0;
if ((already_dead || find_regno_note (insn, REG_DEAD, ureg))
&& reg_meets_class_p (sreg, qty[reg_qty[ureg]].min_class))
{
sqty = reg_qty[ureg];
reg_qty[sreg] = sqty;
reg_offset[sreg] = reg_offset[ureg] + offset;
reg_next_in_qty[sreg] = qty[sqty].first_reg;
qty[sqty].first_reg = sreg;
update_qty_class (sqty, sreg);
qty[sqty].n_calls_crossed += REG_N_CALLS_CROSSED (sreg);
qty[sqty].n_refs += REG_N_REFS (sreg);
qty[sqty].freq += REG_FREQ (sreg);
if (usize < ssize)
{
int i;
for (i = qty[sqty].first_reg; i >= 0; i = reg_next_in_qty[i])
reg_offset[i] -= offset;
qty[sqty].size = ssize;
qty[sqty].mode = GET_MODE (setreg);
}
}
else
return 0;
return 1;
}
static int
reg_meets_class_p (int reg, enum reg_class class)
{
enum reg_class rclass = reg_preferred_class (reg);
return (reg_class_subset_p (rclass, class)
|| reg_class_subset_p (class, rclass));
}
static void
update_qty_class (int qtyno, int reg)
{
enum reg_class rclass = reg_preferred_class (reg);
if (reg_class_subset_p (rclass, qty[qtyno].min_class))
qty[qtyno].min_class = rclass;
rclass = reg_alternate_class (reg);
if (reg_class_subset_p (rclass, qty[qtyno].alternate_class))
qty[qtyno].alternate_class = rclass;
}
static void
reg_is_set (rtx reg, rtx setter, void *data ATTRIBUTE_UNUSED)
{
if (GET_CODE (reg) != SUBREG
&& !REG_P (reg))
return;
reg_is_born (reg, 2 * this_insn_number - (GET_CODE (setter) == CLOBBER));
}
static void
reg_is_born (rtx reg, int birth)
{
int regno;
if (GET_CODE (reg) == SUBREG)
{
regno = REGNO (SUBREG_REG (reg));
if (regno < FIRST_PSEUDO_REGISTER)
regno = subreg_hard_regno (reg, 1);
}
else
regno = REGNO (reg);
if (regno < FIRST_PSEUDO_REGISTER)
{
mark_life (regno, GET_MODE (reg), 1);
if (birth < 2 * this_insn_number)
post_mark_life (regno, GET_MODE (reg), 1, birth, 2 * this_insn_number);
}
else
{
if (reg_qty[regno] == -2)
alloc_qty (regno, GET_MODE (reg), PSEUDO_REGNO_SIZE (regno), birth);
if (reg_qty[regno] >= 0)
qty[reg_qty[regno]].death = -1;
}
}
static void
wipe_dead_reg (rtx reg, int output_p)
{
int regno = REGNO (reg);
if (GET_CODE (PATTERN (this_insn)) == PARALLEL
&& multiple_sets (this_insn))
{
int i;
for (i = XVECLEN (PATTERN (this_insn), 0) - 1; i >= 0; i--)
{
rtx set = XVECEXP (PATTERN (this_insn), 0, i);
if (GET_CODE (set) == SET
&& !REG_P (SET_DEST (set))
&& !rtx_equal_p (reg, SET_DEST (set))
&& reg_overlap_mentioned_p (reg, SET_DEST (set)))
output_p = 1;
}
}
if (! output_p && find_regno_note (this_insn, REG_INC, regno))
output_p = 1;
if (regno < FIRST_PSEUDO_REGISTER)
{
mark_life (regno, GET_MODE (reg), 0);
if (output_p)
post_mark_life (regno, GET_MODE (reg), 1,
2 * this_insn_number, 2 * this_insn_number + 1);
}
else if (reg_qty[regno] >= 0)
qty[reg_qty[regno]].death = 2 * this_insn_number + output_p;
}
static int
find_free_reg (enum reg_class class, enum machine_mode mode, int qtyno,
int accept_call_clobbered, int just_try_suggested,
int born_index, int dead_index)
{
int i, ins;
HARD_REG_SET first_used, used;
#ifdef ELIMINABLE_REGS
static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
#endif
if (born_index < 0 || born_index > dead_index)
abort ();
if (current_function_has_nonlocal_label
&& qty[qtyno].n_calls_crossed > 0)
return -1;
if (accept_call_clobbered)
COPY_HARD_REG_SET (used, call_fixed_reg_set);
else if (qty[qtyno].n_calls_crossed == 0)
COPY_HARD_REG_SET (used, fixed_reg_set);
else
COPY_HARD_REG_SET (used, call_used_reg_set);
if (accept_call_clobbered)
IOR_HARD_REG_SET (used, losing_caller_save_reg_set);
for (ins = born_index; ins < dead_index; ins++)
IOR_HARD_REG_SET (used, regs_live_at[ins]);
IOR_COMPL_HARD_REG_SET (used, reg_class_contents[(int) class]);
#ifdef ELIMINABLE_REGS
for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++)
SET_HARD_REG_BIT (used, eliminables[i].from);
#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
SET_HARD_REG_BIT (used, HARD_FRAME_POINTER_REGNUM);
#endif
#else
SET_HARD_REG_BIT (used, FRAME_POINTER_REGNUM);
#endif
#ifdef CANNOT_CHANGE_MODE_CLASS
cannot_change_mode_set_regs (&used, mode, qty[qtyno].first_reg);
#endif
COPY_HARD_REG_SET (first_used, used);
if (just_try_suggested)
{
if (qty_phys_num_copy_sugg[qtyno] != 0)
IOR_COMPL_HARD_REG_SET (first_used, qty_phys_copy_sugg[qtyno]);
else
IOR_COMPL_HARD_REG_SET (first_used, qty_phys_sugg[qtyno]);
}
GO_IF_HARD_REG_SUBSET (reg_class_contents[(int) ALL_REGS], first_used, fail);
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 (first_used, regno)
&& HARD_REGNO_MODE_OK (regno, mode)
&& (qty[qtyno].n_calls_crossed == 0
|| accept_call_clobbered
|| ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode)))
{
int j;
int size1 = hard_regno_nregs[regno][mode];
for (j = 1; j < size1 && ! TEST_HARD_REG_BIT (used, regno + j); j++);
if (j == size1)
{
post_mark_life (regno, mode, 1, born_index, dead_index);
return regno;
}
#ifndef REG_ALLOC_ORDER
i += j;
#endif
}
}
fail:
if (just_try_suggested && qty_phys_num_copy_sugg[qtyno] != 0
&& qty_phys_num_sugg[qtyno] != 0)
{
qty_phys_num_copy_sugg[qtyno] = 0;
return find_free_reg (class, mode, qtyno, accept_call_clobbered, 1,
born_index, dead_index);
}
if (! accept_call_clobbered
&& flag_caller_saves
&& ! just_try_suggested
&& qty[qtyno].n_calls_crossed != 0
&& CALLER_SAVE_PROFITABLE (qty[qtyno].n_refs,
qty[qtyno].n_calls_crossed))
{
i = find_free_reg (class, mode, qtyno, 1, 0, born_index, dead_index);
if (i >= 0)
caller_save_needed = 1;
return i;
}
return -1;
}
static void
mark_life (int regno, enum machine_mode mode, int life)
{
int j = hard_regno_nregs[regno][mode];
if (life)
while (--j >= 0)
SET_HARD_REG_BIT (regs_live, regno + j);
else
while (--j >= 0)
CLEAR_HARD_REG_BIT (regs_live, regno + j);
}
static void
post_mark_life (int regno, enum machine_mode mode, int life, int birth,
int death)
{
int j = hard_regno_nregs[regno][mode];
HARD_REG_SET this_reg;
CLEAR_HARD_REG_SET (this_reg);
while (--j >= 0)
SET_HARD_REG_BIT (this_reg, regno + j);
if (life)
while (birth < death)
{
IOR_HARD_REG_SET (regs_live_at[birth], this_reg);
birth++;
}
else
while (birth < death)
{
AND_COMPL_HARD_REG_SET (regs_live_at[birth], this_reg);
birth++;
}
}
static int
no_conflict_p (rtx insn, rtx r0 ATTRIBUTE_UNUSED, rtx r1)
{
int ok = 0;
rtx note = find_reg_note (insn, REG_LIBCALL, NULL_RTX);
rtx p, last;
if (note == 0
|| (REG_P (r1) && REGNO (r1) < FIRST_PSEUDO_REGISTER)
|| (GET_CODE (r1) == SUBREG && REG_P (SUBREG_REG (r1))
&& REGNO (SUBREG_REG (r1)) < FIRST_PSEUDO_REGISTER))
return 0;
last = XEXP (note, 0);
for (p = NEXT_INSN (insn); p && p != last; p = NEXT_INSN (p))
if (INSN_P (p))
{
if (find_reg_note (p, REG_DEAD, r1))
ok = 1;
if (! find_reg_note (p, REG_NO_CONFLICT, r1))
return 0;
}
return ok;
}
static int
requires_inout (const char *p)
{
char c;
int found_zero = 0;
int reg_allowed = 0;
int num_matching_alts = 0;
int len;
for ( ; (c = *p); p += len)
{
len = CONSTRAINT_LEN (c, p);
switch (c)
{
case '=': case '+': case '?':
case '#': case '&': case '!':
case '*': case '%':
case 'm': case '<': case '>': case 'V': case 'o':
case 'E': case 'F': case 'G': case 'H':
case 's': case 'i': case 'n':
case 'I': case 'J': case 'K': case 'L':
case 'M': case 'N': case 'O': case 'P':
case 'X':
break;
case ',':
if (found_zero && ! reg_allowed)
num_matching_alts++;
found_zero = reg_allowed = 0;
break;
case '0':
found_zero = 1;
break;
case '1': case '2': case '3': case '4': case '5':
case '6': case '7': case '8': case '9':
do
p++;
while (ISDIGIT (*p));
len = 0;
break;
default:
if (REG_CLASS_FROM_CONSTRAINT (c, p) == NO_REGS
&& !EXTRA_ADDRESS_CONSTRAINT (c, p))
break;
case 'p':
case 'g': case 'r':
reg_allowed = 1;
break;
}
}
if (found_zero && ! reg_allowed)
num_matching_alts++;
return num_matching_alts;
}
void
dump_local_alloc (FILE *file)
{
int i;
for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
if (reg_renumber[i] != -1)
fprintf (file, ";; Register %d in %d.\n", i, reg_renumber[i]);
}