/* Graph coloring register allocator
- Copyright (C) 2001, 2002 Free Software Foundation, Inc.
+ Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
Contributed by Michael Matz <matz@suse.de>
and Daniel Berlin <dan@cgsoftware.com>.
* use the constraints from asms
*/
+static int first_hard_reg (HARD_REG_SET);
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));
+static void create_insn_info (struct df *);
+static void free_insn_info (void);
+static void alloc_mem (struct df *);
+static void free_mem (struct df *);
+static void free_all_mem (struct df *df);
+static int one_pass (struct df *, int);
+static void check_df (struct df *);
+static void init_ra (void);
-void reg_alloc PARAMS ((void));
+void reg_alloc (void);
/* These global variables are "internal" to the register allocator.
They are all documented at their declarations in ra.h. */
HARD_REG_SET never_use_colors;
HARD_REG_SET usable_regs[N_REG_CLASSES];
unsigned int num_free_regs[N_REG_CLASSES];
+int single_reg_in_regclass[N_REG_CLASSES];
HARD_REG_SET hardregs_for_mode[NUM_MACHINE_MODES];
+HARD_REG_SET invalid_mode_change_regs;
unsigned char byte2bitcount[256];
unsigned int debug_new_regalloc = -1;
is done. Allocate an object of SIZE bytes. */
void *
-ra_alloc (size)
- size_t size;
+ra_alloc (size_t size)
{
return obstack_alloc (&ra_obstack, size);
}
/* Like ra_alloc(), but clear the returned memory. */
void *
-ra_calloc (size)
- size_t size;
+ra_calloc (size_t size)
{
void *p = obstack_alloc (&ra_obstack, size);
memset (p, 0, size);
/* Returns the number of hardregs in HARD_REG_SET RS. */
int
-hard_regs_count (rs)
- HARD_REG_SET rs;
+hard_regs_count (HARD_REG_SET rs)
{
int count = 0;
#ifdef HARD_REG_SET
return count;
}
+/* Returns the first hardreg in HARD_REG_SET RS. Assumes there is at
+ least one reg in the set. */
+
+static int
+first_hard_reg (HARD_REG_SET rs)
+{
+ int c;
+ for (c = 0; c < FIRST_PSEUDO_REGISTER && !TEST_HARD_REG_BIT (rs, c); c++)
+ if (c == FIRST_PSEUDO_REGISTER)
+ abort();
+ return c;
+}
+
/* Basically like emit_move_insn (i.e. validifies constants and such),
but also handle MODE_CC moves (but then the operands must already
be basically valid. */
rtx
-ra_emit_move_insn (x, y)
- rtx x, y;
+ra_emit_move_insn (rtx x, rtx y)
{
enum machine_mode mode = GET_MODE (x);
if (GET_MODE_CLASS (mode) == MODE_CC)
all valid defs and uses in an insn. */
static void
-create_insn_info (df)
- struct df *df;
+create_insn_info (struct df *df)
{
rtx insn;
struct ref **act_refs;
/* Free the insn_df structures. */
static void
-free_insn_info ()
+free_insn_info (void)
{
free (refs_for_insn_df);
refs_for_insn_df = NULL;
represented by WEB. Returns the matching subweb or NULL. */
struct web *
-find_subweb (web, reg)
- struct web *web;
- rtx reg;
+find_subweb (struct web *web, rtx reg)
{
struct web *w;
if (GET_CODE (reg) != SUBREG)
a collection of the needed size and offset (in bytes). */
struct web *
-find_subweb_2 (web, size_word)
- struct web *web;
- unsigned int size_word;
+find_subweb_2 (struct web *web, unsigned int size_word)
{
struct web *w = web;
if (size_word == GET_MODE_SIZE (GET_MODE (web->orig_x)))
/* Returns the superweb for SUBWEB. */
struct web *
-find_web_for_subweb_1 (subweb)
- struct web *subweb;
+find_web_for_subweb_1 (struct web *subweb)
{
while (subweb->parent_web)
subweb = subweb->parent_web;
Return 1 if they do. */
int
-hard_regs_intersect_p (a, b)
- HARD_REG_SET *a, *b;
+hard_regs_intersect_p (HARD_REG_SET *a, HARD_REG_SET *b)
{
HARD_REG_SET c;
COPY_HARD_REG_SET (c, *a);
register allocator. */
static void
-alloc_mem (df)
- struct df *df;
+alloc_mem (struct df *df)
{
int i;
ra_build_realloc (df);
if (!live_at_end)
{
- live_at_end = (bitmap *) xmalloc ((last_basic_block + 2)
- * sizeof (bitmap));
+ live_at_end = 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;
/* Free the memory which isn't necessary for the next pass. */
static void
-free_mem (df)
- struct df *df ATTRIBUTE_UNUSED;
+free_mem (struct df *df ATTRIBUTE_UNUSED)
{
free_insn_info ();
ra_build_free ();
it's done. */
static void
-free_all_mem (df)
- struct df *df;
+free_all_mem (struct df *df)
{
unsigned int i;
live_at_end -= 2;
was added, i.e. if the allocator needs to rerun. */
static int
-one_pass (df, rebuild)
- struct df *df;
- int rebuild;
+one_pass (struct df *df, int rebuild)
{
long ticks = clock ();
int something_spilled;
/* Initialize various arrays for the register allocator. */
static void
-init_ra ()
+init_ra (void)
{
int i;
HARD_REG_SET rs;
#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 ();
{
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--;)
+ 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--;)
+ 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--;)
+ for (i = hard_regno_nregs[FRAME_POINTER_REGNUM][Pmode]; i--;)
SET_HARD_REG_BIT (never_use_colors, FRAME_POINTER_REGNUM + i);
#endif
/* Stack and argument pointer are also rather useless to us. */
- for (i = HARD_REGNO_NREGS (STACK_POINTER_REGNUM, Pmode); i--;)
+ 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--;)
+ 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++)
size = hard_regs_count (rs);
num_free_regs[i] = size;
COPY_HARD_REG_SET (usable_regs[i], rs);
+ if (size == 1)
+ single_reg_in_regclass[i] = first_hard_reg (rs);
+ else
+ single_reg_in_regclass[i] = -1;
}
/* Setup hardregs_for_mode[].
for (reg = 0; reg < FIRST_PSEUDO_REGISTER; reg++)
if (HARD_REGNO_MODE_OK (reg, i)
/* Ignore VOIDmode and similar things. */
- && (size = HARD_REGNO_NREGS (reg, i)) != 0
+ && (size = hard_regno_nregs[reg][i]) != 0
&& (reg + size) <= FIRST_PSEUDO_REGISTER)
{
while (size--)
COPY_HARD_REG_SET (hardregs_for_mode[i], rs);
}
+ CLEAR_HARD_REG_SET (invalid_mode_change_regs);
+#ifdef CANNOT_CHANGE_MODE_CLASS
+ if (0)
+ for (i = 0; i < NUM_MACHINE_MODES; i++)
+ {
+ enum machine_mode from = (enum machine_mode) i;
+ enum machine_mode to;
+ for (to = VOIDmode; to < MAX_MACHINE_MODE; ++to)
+ {
+ int r;
+ for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
+ if (REG_CANNOT_CHANGE_MODE_P (from, to, r))
+ SET_HARD_REG_BIT (invalid_mode_change_regs, r);
+ }
+ }
+#endif
+
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))
invariances we expect. */
static void
-check_df (df)
- struct df *df;
+check_df (struct df *df)
{
struct df_link *link;
rtx insn;
/* Main register allocator entry point. */
void
-reg_alloc ()
+reg_alloc (void)
{
int changed;
- FILE *ra_dump_file = rtl_dump_file;
+ FILE *ra_dump_file = dump_file;
rtx last = get_last_insn ();
if (! INSN_P (last))
for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
{
basic_block bb = e->src;
- last = bb->end;
+ last = BB_END (bb);
if (!INSN_P (last) || GET_CODE (PATTERN (last)) != USE)
{
rtx insns;
break;
case 6: debug_new_regalloc = DUMP_VALIDIFY; break;
}
- if (!rtl_dump_file)
+ if (!dump_file)
debug_new_regalloc = 0;
/* Run regclass first, so we know the preferred and alternate classes
for each pseudo. Deactivate emitting of debug info, if it's not
explicitly requested. */
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;
+ dump_file = NULL;
+ regclass (get_insns (), max_reg_num (), dump_file);
+ dump_file = ra_dump_file;
/* We don't use those NOTEs, and as we anyway change all registers,
they only make problems later. */
/* First collect all the register refs and put them into
chains per insn, and per regno. In later passes only update
that info from the new and modified insns. */
- df_analyse (df, (ra_pass == 1) ? 0 : (bitmap) -1,
- DF_HARD_REGS | DF_RD_CHAIN | DF_RU_CHAIN);
+ df_analyze (df, (ra_pass == 1) ? 0 : (bitmap) -1,
+ DF_HARD_REGS | DF_RD_CHAIN | DF_RU_CHAIN | DF_FOR_REGALLOC);
if ((debug_new_regalloc & DUMP_DF) != 0)
{
rtx insn;
- df_dump (df, DF_HARD_REGS, rtl_dump_file);
+ df_dump (df, DF_HARD_REGS, dump_file);
for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
if (INSN_P (insn))
- df_insn_debug_regno (df, insn, rtl_dump_file);
+ df_insn_debug_regno (df, insn, dump_file);
}
check_df (df);
therefore repeat some things, including some initialization
of global data structures. */
if ((debug_new_regalloc & DUMP_REGCLASS) == 0)
- rtl_dump_file = NULL;
+ dump_file = NULL;
/* We have new pseudos (the stackwebs). */
allocate_reg_info (max_reg_num (), FALSE, FALSE);
/* And new insns. */
reg_scan_update (get_insns (), NULL, max_regno);
max_regno = max_reg_num ();
/* And they need useful classes too. */
- regclass (get_insns (), max_reg_num (), rtl_dump_file);
- rtl_dump_file = ra_dump_file;
+ regclass (get_insns (), max_reg_num (), dump_file);
+ dump_file = ra_dump_file;
/* Remember the number of defs and uses, so we can distinguish
new from old refs in the next pass. */
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);
+ ra_print_rtl_with_bb (dump_file, get_insns ());
+ fflush (dump_file);
}
/* Reset the web lists. */
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 ());
+ ra_print_rtl_with_bb (dump_file, get_insns ());
/* We might have new pseudos, so allocate the info arrays for them. */
if ((debug_new_regalloc & DUMP_SM) == 0)
- rtl_dump_file = NULL;
+ 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;
+ dump_file = ra_dump_file;
/* Some spill insns could've been inserted after trapping calls, i.e.
at the end of a basic block, which really ends at that call.
/* Cleanup the flow graph. */
if ((debug_new_regalloc & DUMP_LAST_FLOW) == 0)
- rtl_dump_file = NULL;
- life_analysis (get_insns (), rtl_dump_file,
+ dump_file = NULL;
+ life_analysis (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;
+ if (dump_file)
+ dump_flow_info (dump_file);
+ dump_file = ra_dump_file;
/* update_equiv_regs() can't be called after register allocation.
It might delete some pseudos, and insert other insns setting
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,
+ ra_print_rtl_with_bb (dump_file, get_insns ());
+ dump_static_insn_cost (dump_file,
"after allocation/spilling, before reload", NULL);
/* Allocate the reg_equiv_memory_loc array for reload. */
- reg_equiv_memory_loc = (rtx *) xcalloc (max_regno, sizeof (rtx));
+ VARRAY_GROW (reg_equiv_memory_loc_varray, max_regno);
+ reg_equiv_memory_loc = &VARRAY_RTX (reg_equiv_memory_loc_varray, 0);
/* And possibly initialize it. */
allocate_initial_values (reg_equiv_memory_loc);
/* And one last regclass pass just before reload. */
- regclass (get_insns (), max_reg_num (), rtl_dump_file);
+ regclass (get_insns (), max_reg_num (), dump_file);
}
/*