#include "config.h"
#include "system.h"
#include "rtl.h"
#include "tm_p.h"
#include "insn-config.h"
#include "recog.h"
#include "reload.h"
#include "integrate.h"
#include "function.h"
#include "regs.h"
#include "obstack.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "df.h"
#include "expr.h"
#include "output.h"
#include "toplev.h"
#include "flags.h"
#include "ra.h"
static struct obstack ra_obstack;
static void create_insn_info PARAMS ((struct df *));
static void free_insn_info PARAMS ((void));
static void alloc_mem PARAMS ((struct df *));
static void free_mem PARAMS ((struct df *));
static void free_all_mem PARAMS ((struct df *df));
static int one_pass PARAMS ((struct df *, int));
static void check_df PARAMS ((struct df *));
static void init_ra PARAMS ((void));
void reg_alloc PARAMS ((void));
sbitmap igraph;
sbitmap sup_igraph;
sbitmap insns_with_deaths;
int death_insns_max_uid;
struct web_part *web_parts;
unsigned int num_webs;
unsigned int num_subwebs;
unsigned int num_allwebs;
struct web **id2web;
struct web *hardreg2web[FIRST_PSEUDO_REGISTER];
struct web **def2web;
struct web **use2web;
struct move_list *wl_moves;
int ra_max_regno;
short *ra_reg_renumber;
struct df *df;
bitmap *live_at_end;
int ra_pass;
unsigned int max_normal_pseudo;
int an_unusable_color;
struct dlist *web_lists[(int) LAST_NODE_TYPE];
unsigned int last_def_id;
unsigned int last_use_id;
unsigned int last_num_webs;
int last_max_uid;
sbitmap last_check_uses;
unsigned int remember_conflicts;
int orig_max_uid;
HARD_REG_SET never_use_colors;
HARD_REG_SET usable_regs[N_REG_CLASSES];
unsigned int num_free_regs[N_REG_CLASSES];
HARD_REG_SET hardregs_for_mode[NUM_MACHINE_MODES];
unsigned char byte2bitcount[256];
unsigned int debug_new_regalloc = -1;
int flag_ra_biased = 0;
int flag_ra_improved_spilling = 0;
int flag_ra_ir_spilling = 0;
int flag_ra_optimistic_coalescing = 0;
int flag_ra_break_aliases = 0;
int flag_ra_merge_spill_costs = 0;
int flag_ra_spill_every_use = 0;
int flag_ra_dump_notes = 0;
void *
ra_alloc (size)
size_t size;
{
return obstack_alloc (&ra_obstack, size);
}
void *
ra_calloc (size)
size_t size;
{
void *p = obstack_alloc (&ra_obstack, size);
memset (p, 0, size);
return p;
}
int
hard_regs_count (rs)
HARD_REG_SET rs;
{
int count = 0;
#ifdef HARD_REG_SET
while (rs)
{
unsigned char byte = rs & 0xFF;
rs >>= 8;
if (byte)
count += byte2bitcount[byte];
}
#else
unsigned int ofs;
for (ofs = 0; ofs < HARD_REG_SET_LONGS; ofs++)
{
HARD_REG_ELT_TYPE elt = rs[ofs];
while (elt)
{
unsigned char byte = elt & 0xFF;
elt >>= 8;
if (byte)
count += byte2bitcount[byte];
}
}
#endif
return count;
}
rtx
ra_emit_move_insn (x, y)
rtx x, y;
{
enum machine_mode mode = GET_MODE (x);
if (GET_MODE_CLASS (mode) == MODE_CC)
return emit_insn (gen_move_insn (x, y));
else
return emit_move_insn (x, y);
}
int insn_df_max_uid;
struct ra_insn_info *insn_df;
static struct ref **refs_for_insn_df;
static void
create_insn_info (df)
struct df *df;
{
rtx insn;
struct ref **act_refs;
insn_df_max_uid = get_max_uid ();
insn_df = xcalloc (insn_df_max_uid, sizeof (insn_df[0]));
refs_for_insn_df = xcalloc (df->def_id + df->use_id, sizeof (struct ref *));
act_refs = refs_for_insn_df;
for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
{
int uid = INSN_UID (insn);
unsigned int n;
struct df_link *link;
if (!INSN_P (insn))
continue;
for (n = 0, link = DF_INSN_DEFS (df, insn); link; link = link->next)
if (link->ref
&& (DF_REF_REGNO (link->ref) >= FIRST_PSEUDO_REGISTER
|| !TEST_HARD_REG_BIT (never_use_colors,
DF_REF_REGNO (link->ref))))
{
if (n == 0)
insn_df[uid].defs = act_refs;
insn_df[uid].defs[n++] = link->ref;
}
act_refs += n;
insn_df[uid].num_defs = n;
for (n = 0, link = DF_INSN_USES (df, insn); link; link = link->next)
if (link->ref
&& (DF_REF_REGNO (link->ref) >= FIRST_PSEUDO_REGISTER
|| !TEST_HARD_REG_BIT (never_use_colors,
DF_REF_REGNO (link->ref))))
{
if (n == 0)
insn_df[uid].uses = act_refs;
insn_df[uid].uses[n++] = link->ref;
}
act_refs += n;
insn_df[uid].num_uses = n;
}
if (refs_for_insn_df + (df->def_id + df->use_id) < act_refs)
abort ();
}
static void
free_insn_info ()
{
free (refs_for_insn_df);
refs_for_insn_df = NULL;
free (insn_df);
insn_df = NULL;
insn_df_max_uid = 0;
}
struct web *
find_subweb (web, reg)
struct web *web;
rtx reg;
{
struct web *w;
if (GET_CODE (reg) != SUBREG)
abort ();
for (w = web->subreg_next; w; w = w->subreg_next)
if (GET_MODE (w->orig_x) == GET_MODE (reg)
&& SUBREG_BYTE (w->orig_x) == SUBREG_BYTE (reg))
return w;
return NULL;
}
struct web *
find_subweb_2 (web, size_word)
struct web *web;
unsigned int size_word;
{
struct web *w = web;
if (size_word == GET_MODE_SIZE (GET_MODE (web->orig_x)))
return web;
for (w = web->subreg_next; w; w = w->subreg_next)
{
unsigned int bl = rtx_to_bits (w->orig_x);
if (size_word == bl)
return w;
}
return NULL;
}
struct web *
find_web_for_subweb_1 (subweb)
struct web *subweb;
{
while (subweb->parent_web)
subweb = subweb->parent_web;
return subweb;
}
int
hard_regs_intersect_p (a, b)
HARD_REG_SET *a, *b;
{
HARD_REG_SET c;
COPY_HARD_REG_SET (c, *a);
AND_HARD_REG_SET (c, *b);
GO_IF_HARD_REG_SUBSET (c, reg_class_contents[(int) NO_REGS], lose);
return 1;
lose:
return 0;
}
static void
alloc_mem (df)
struct df *df;
{
int i;
ra_build_realloc (df);
if (!live_at_end)
{
live_at_end = (bitmap *) xmalloc ((last_basic_block + 2)
* sizeof (bitmap));
for (i = 0; i < last_basic_block + 2; i++)
live_at_end[i] = BITMAP_XMALLOC ();
live_at_end += 2;
}
create_insn_info (df);
}
static void
free_mem (df)
struct df *df ATTRIBUTE_UNUSED;
{
free_insn_info ();
ra_build_free ();
}
static void
free_all_mem (df)
struct df *df;
{
unsigned int i;
live_at_end -= 2;
for (i = 0; i < (unsigned)last_basic_block + 2; i++)
BITMAP_XFREE (live_at_end[i]);
free (live_at_end);
ra_colorize_free_all ();
ra_build_free_all (df);
obstack_free (&ra_obstack, NULL);
}
static long ticks_build;
static long ticks_rebuild;
static int
one_pass (df, rebuild)
struct df *df;
int rebuild;
{
long ticks = clock ();
int something_spilled;
remember_conflicts = 0;
build_i_graph (df);
remember_conflicts = 1;
if (!rebuild)
dump_igraph_machine ();
ra_colorize_graph (df);
last_max_uid = get_max_uid ();
something_spilled = !!WEBS(SPILLED);
if (something_spilled)
actual_spill ();
ticks = clock () - ticks;
if (rebuild)
ticks_rebuild += ticks;
else
ticks_build += ticks;
return something_spilled;
}
static void
init_ra ()
{
int i;
HARD_REG_SET rs;
#ifdef ELIMINABLE_REGS
static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
unsigned int j;
#endif
int need_fp
= (! flag_omit_frame_pointer
#ifdef EXIT_IGNORE_STACK
|| (current_function_calls_alloca && EXIT_IGNORE_STACK)
#endif
|| FRAME_POINTER_REQUIRED);
ra_colorize_init ();
COPY_HARD_REG_SET (never_use_colors, fixed_reg_set);
#ifdef ELIMINABLE_REGS
for (j = 0; j < ARRAY_SIZE (eliminables); j++)
{
if (! CAN_ELIMINATE (eliminables[j].from, eliminables[j].to)
|| (eliminables[j].to == STACK_POINTER_REGNUM && need_fp))
for (i = HARD_REGNO_NREGS (eliminables[j].from, Pmode); i--;)
SET_HARD_REG_BIT (never_use_colors, eliminables[j].from + i);
}
#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
if (need_fp)
for (i = HARD_REGNO_NREGS (HARD_FRAME_POINTER_REGNUM, Pmode); i--;)
SET_HARD_REG_BIT (never_use_colors, HARD_FRAME_POINTER_REGNUM + i);
#endif
#else
if (need_fp)
for (i = HARD_REGNO_NREGS (FRAME_POINTER_REGNUM, Pmode); i--;)
SET_HARD_REG_BIT (never_use_colors, FRAME_POINTER_REGNUM + i);
#endif
for (i = HARD_REGNO_NREGS (STACK_POINTER_REGNUM, Pmode); i--;)
SET_HARD_REG_BIT (never_use_colors, STACK_POINTER_REGNUM + i);
for (i = HARD_REGNO_NREGS (ARG_POINTER_REGNUM, Pmode); i--;)
SET_HARD_REG_BIT (never_use_colors, ARG_POINTER_REGNUM + i);
for (i = 0; i < 256; i++)
{
unsigned char byte = ((unsigned) i) & 0xFF;
unsigned char count = 0;
while (byte)
{
if (byte & 1)
count++;
byte >>= 1;
}
byte2bitcount[i] = count;
}
for (i = 0; i < N_REG_CLASSES; i++)
{
int size;
COPY_HARD_REG_SET (rs, reg_class_contents[i]);
AND_COMPL_HARD_REG_SET (rs, never_use_colors);
size = hard_regs_count (rs);
num_free_regs[i] = size;
COPY_HARD_REG_SET (usable_regs[i], rs);
}
for (i = 0; i < NUM_MACHINE_MODES; i++)
{
int reg, size;
CLEAR_HARD_REG_SET (rs);
for (reg = 0; reg < FIRST_PSEUDO_REGISTER; reg++)
if (HARD_REGNO_MODE_OK (reg, i)
&& (size = HARD_REGNO_NREGS (reg, i)) != 0
&& (reg + size) <= FIRST_PSEUDO_REGISTER)
{
while (size--)
SET_HARD_REG_BIT (rs, reg + size);
}
COPY_HARD_REG_SET (hardregs_for_mode[i], rs);
}
for (an_unusable_color = 0; an_unusable_color < FIRST_PSEUDO_REGISTER;
an_unusable_color++)
if (TEST_HARD_REG_BIT (never_use_colors, an_unusable_color))
break;
if (an_unusable_color == FIRST_PSEUDO_REGISTER)
abort ();
orig_max_uid = get_max_uid ();
compute_bb_for_insn ();
ra_reg_renumber = NULL;
insns_with_deaths = sbitmap_alloc (orig_max_uid);
death_insns_max_uid = orig_max_uid;
sbitmap_ones (insns_with_deaths);
gcc_obstack_init (&ra_obstack);
}
static void
check_df (df)
struct df *df;
{
struct df_link *link;
rtx insn;
int regno;
unsigned int ui;
bitmap b = BITMAP_XMALLOC ();
bitmap empty_defs = BITMAP_XMALLOC ();
bitmap empty_uses = BITMAP_XMALLOC ();
for (ui = 0; ui < df->def_id; ui++)
if (!df->defs[ui])
bitmap_set_bit (empty_defs, ui);
for (ui = 0; ui < df->use_id; ui++)
if (!df->uses[ui])
bitmap_set_bit (empty_uses, ui);
for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
if (INSN_P (insn))
{
bitmap_clear (b);
for (link = DF_INSN_DEFS (df, insn); link; link = link->next)
if (!link->ref || bitmap_bit_p (empty_defs, DF_REF_ID (link->ref))
|| bitmap_bit_p (b, DF_REF_ID (link->ref)))
abort ();
else
bitmap_set_bit (b, DF_REF_ID (link->ref));
bitmap_clear (b);
for (link = DF_INSN_USES (df, insn); link; link = link->next)
if (!link->ref || bitmap_bit_p (empty_uses, DF_REF_ID (link->ref))
|| bitmap_bit_p (b, DF_REF_ID (link->ref)))
abort ();
else
bitmap_set_bit (b, DF_REF_ID (link->ref));
}
for (regno = 0; regno < max_reg_num (); regno++)
{
bitmap_clear (b);
for (link = df->regs[regno].defs; link; link = link->next)
if (!link->ref || bitmap_bit_p (empty_defs, DF_REF_ID (link->ref))
|| bitmap_bit_p (b, DF_REF_ID (link->ref)))
abort ();
else
bitmap_set_bit (b, DF_REF_ID (link->ref));
bitmap_clear (b);
for (link = df->regs[regno].uses; link; link = link->next)
if (!link->ref || bitmap_bit_p (empty_uses, DF_REF_ID (link->ref))
|| bitmap_bit_p (b, DF_REF_ID (link->ref)))
abort ();
else
bitmap_set_bit (b, DF_REF_ID (link->ref));
}
BITMAP_XFREE (empty_uses);
BITMAP_XFREE (empty_defs);
BITMAP_XFREE (b);
}
void
reg_alloc ()
{
int changed;
FILE *ra_dump_file = rtl_dump_file;
rtx last = get_last_insn ();
if (! INSN_P (last))
last = prev_real_insn (last);
if (last)
{
edge e;
for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
{
basic_block bb = e->src;
last = bb->end;
if (!INSN_P (last) || GET_CODE (PATTERN (last)) != USE)
{
rtx insns;
start_sequence ();
use_return_register ();
insns = get_insns ();
end_sequence ();
emit_insn_after (insns, last);
}
}
}
switch (0)
{
case 0: debug_new_regalloc = DUMP_EVER; break;
case 1: debug_new_regalloc = DUMP_COSTS; break;
case 2: debug_new_regalloc = DUMP_IGRAPH_M; break;
case 3: debug_new_regalloc = DUMP_COLORIZE + DUMP_COSTS; break;
case 4: debug_new_regalloc = DUMP_COLORIZE + DUMP_COSTS + DUMP_WEBS;
break;
case 5: debug_new_regalloc = DUMP_FINAL_RTL + DUMP_COSTS +
DUMP_CONSTRAINTS;
break;
case 6: debug_new_regalloc = DUMP_VALIDIFY; break;
}
if (!rtl_dump_file)
debug_new_regalloc = 0;
if ((debug_new_regalloc & DUMP_REGCLASS) == 0)
rtl_dump_file = NULL;
regclass (get_insns (), max_reg_num (), rtl_dump_file);
rtl_dump_file = ra_dump_file;
count_or_remove_death_notes (NULL, 1);
init_ra ();
ra_pass = 0;
no_new_pseudos = 0;
max_normal_pseudo = (unsigned) max_reg_num ();
ra_rewrite_init ();
last_def_id = 0;
last_use_id = 0;
last_num_webs = 0;
last_max_uid = 0;
last_check_uses = NULL;
live_at_end = NULL;
WEBS(INITIAL) = NULL;
WEBS(FREE) = NULL;
memset (hardreg2web, 0, sizeof (hardreg2web));
ticks_build = ticks_rebuild = 0;
flag_ra_biased = 0;
flag_ra_spill_every_use = 0;
flag_ra_improved_spilling = 1;
flag_ra_ir_spilling = 1;
flag_ra_break_aliases = 0;
flag_ra_optimistic_coalescing = 1;
flag_ra_merge_spill_costs = 1;
if (flag_ra_optimistic_coalescing)
flag_ra_break_aliases = 1;
flag_ra_dump_notes = 0;
df = df_init ();
do
{
ra_debug_msg (DUMP_NEARLY_EVER, "RegAlloc Pass %d\n\n", ra_pass);
if (ra_pass++ > 40)
internal_error ("Didn't find a coloring.\n");
df_analyse (df, (ra_pass == 1) ? 0 : (bitmap) -1,
DF_HARD_REGS | DF_RD_CHAIN | DF_RU_CHAIN);
if ((debug_new_regalloc & DUMP_DF) != 0)
{
rtx insn;
df_dump (df, DF_HARD_REGS, rtl_dump_file);
for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
if (INSN_P (insn))
df_insn_debug_regno (df, insn, rtl_dump_file);
}
check_df (df);
alloc_mem (df);
changed = one_pass (df, ra_pass > 1);
if (!changed)
{
emit_colors (df);
setup_renumber (0);
delete_moves ();
dump_constraints ();
}
else
{
if ((debug_new_regalloc & DUMP_REGCLASS) == 0)
rtl_dump_file = NULL;
allocate_reg_info (max_reg_num (), FALSE, FALSE);
compute_bb_for_insn ();
delete_trivially_dead_insns (get_insns (), max_reg_num ());
reg_scan_update (get_insns (), NULL, max_regno);
max_regno = max_reg_num ();
regclass (get_insns (), max_reg_num (), rtl_dump_file);
rtl_dump_file = ra_dump_file;
last_def_id = df->def_id;
last_use_id = df->use_id;
}
dump_ra (df);
if (changed && (debug_new_regalloc & DUMP_RTL) != 0)
{
ra_print_rtl_with_bb (rtl_dump_file, get_insns ());
fflush (rtl_dump_file);
}
reset_lists ();
free_mem (df);
}
while (changed);
free_all_mem (df);
df_finish (df);
if ((debug_new_regalloc & DUMP_RESULTS) == 0)
dump_cost (DUMP_COSTS);
ra_debug_msg (DUMP_COSTS, "ticks for build-phase: %ld\n", ticks_build);
ra_debug_msg (DUMP_COSTS, "ticks for rebuild-phase: %ld\n", ticks_rebuild);
if ((debug_new_regalloc & (DUMP_FINAL_RTL | DUMP_RTL)) != 0)
ra_print_rtl_with_bb (rtl_dump_file, get_insns ());
if ((debug_new_regalloc & DUMP_SM) == 0)
rtl_dump_file = NULL;
no_new_pseudos = 0;
allocate_reg_info (max_reg_num (), FALSE, FALSE);
no_new_pseudos = 1;
rtl_dump_file = ra_dump_file;
fixup_abnormal_edges ();
if ((debug_new_regalloc & DUMP_LAST_FLOW) == 0)
rtl_dump_file = NULL;
life_analysis (get_insns (), rtl_dump_file,
PROP_DEATH_NOTES | PROP_LOG_LINKS | PROP_REG_INFO);
cleanup_cfg (CLEANUP_EXPENSIVE);
recompute_reg_usage (get_insns (), TRUE);
if (rtl_dump_file)
dump_flow_info (rtl_dump_file);
rtl_dump_file = ra_dump_file;
setup_renumber (1);
sbitmap_free (insns_with_deaths);
remove_suspicious_death_notes ();
if ((debug_new_regalloc & DUMP_LAST_RTL) != 0)
ra_print_rtl_with_bb (rtl_dump_file, get_insns ());
dump_static_insn_cost (rtl_dump_file,
"after allocation/spilling, before reload", NULL);
reg_equiv_memory_loc = (rtx *) xcalloc (max_regno, sizeof (rtx));
allocate_initial_values (reg_equiv_memory_loc);
regclass (get_insns (), max_reg_num (), rtl_dump_file);
}