/* Allocate registers for pseudo-registers that span basic blocks.
- Copyright (C) 2007 Free Software Foundation, Inc.
+ Copyright (C) 2007, 2008 Free Software Foundation, Inc.
Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>
This file is part of GCC.
#include "vecprim.h"
#include "ra.h"
#include "sbitmap.h"
-
-/* Test, set or clear bit number I in allocnos_live,
- a bit vector indexed by allocno. */
-
-#define SET_ALLOCNO_LIVE(A, I) \
- ((A)[(unsigned) (I) / HOST_BITS_PER_WIDE_INT] \
- |= ((HOST_WIDE_INT) 1 << ((unsigned) (I) % HOST_BITS_PER_WIDE_INT)))
-
-#define CLEAR_ALLOCNO_LIVE(A, I) \
- ((A)[(unsigned) (I) / HOST_BITS_PER_WIDE_INT] \
- &= ~((HOST_WIDE_INT) 1 << ((unsigned) (I) % HOST_BITS_PER_WIDE_INT)))
-
-#define GET_ALLOCNO_LIVE(A, I) \
- ((A)[(unsigned) (I) / HOST_BITS_PER_WIDE_INT] \
- & ((HOST_WIDE_INT) 1 << ((unsigned) (I) % HOST_BITS_PER_WIDE_INT)))
+#include "sparseset.h"
/* Externs defined in regs.h. */
int max_allocno;
struct allocno *allocno;
-HOST_WIDE_INT *conflicts;
-int allocno_row_words;
+HOST_WIDEST_FAST_INT *conflicts;
int *reg_allocno;
+HOST_WIDE_INT *partial_bitnum;
+HOST_WIDE_INT max_bitnum;
+alloc_pool adjacency_pool;
+adjacency_t **adjacency;
typedef struct df_ref * df_ref_t;
DEF_VEC_P(df_ref_t);
DEF_VEC_ALLOC_P(df_ref_t,heap);
+/* Macros to determine the bit number within the triangular bit matrix for
+ the two allocnos Low and HIGH, with LOW strictly less than HIGH. */
+
+#define CONFLICT_BITNUM(I, J) \
+ (((I) < (J)) ? (partial_bitnum[I] + (J)) : (partial_bitnum[J] + (I)))
+
+#define CONFLICT_BITNUM_FAST(I, I_PARTIAL_BITNUM, J) \
+ (((I) < (J)) ? ((I_PARTIAL_BITNUM) + (J)) : (partial_bitnum[J] + (I)))
+
+bool
+conflict_p (int allocno1, int allocno2)
+{
+ HOST_WIDE_INT bitnum;
+ HOST_WIDEST_FAST_INT word, mask;
+
+#ifdef ENABLE_CHECKING
+ int blk1, blk2;
+
+ gcc_assert (allocno1 >= 0 && allocno1 < max_allocno);
+ gcc_assert (allocno2 >= 0 && allocno2 < max_allocno);
+
+ blk1 = regno_basic_block (allocno[allocno1].reg);
+ blk2 = regno_basic_block (allocno[allocno2].reg);
+ gcc_assert (blk1 == 0 || blk2 == 0 || blk1 == blk2);
+#endif
+
+ if (allocno1 == allocno2)
+ /* By definition, an allocno does not conflict with itself. */
+ return 0;
+
+ bitnum = CONFLICT_BITNUM (allocno1, allocno2);
+
+#ifdef ENABLE_CHECKING
+ gcc_assert (bitnum >= 0 && bitnum < max_bitnum);
+#endif
+
+ word = conflicts[bitnum / HOST_BITS_PER_WIDEST_FAST_INT];
+ mask = (HOST_WIDEST_FAST_INT) 1 << (bitnum % HOST_BITS_PER_WIDEST_FAST_INT);
+ return (word & mask) != 0;
+}
+
+/* Add conflict edges between ALLOCNO1 and ALLOCNO2. */
+
+static void
+set_conflict (int allocno1, int allocno2)
+{
+ HOST_WIDE_INT bitnum, index;
+ HOST_WIDEST_FAST_INT word, mask;
+
+#ifdef ENABLE_CHECKING
+ int blk1, blk2;
+
+ gcc_assert (allocno1 >= 0 && allocno1 < max_allocno);
+ gcc_assert (allocno2 >= 0 && allocno2 < max_allocno);
+
+ blk1 = regno_basic_block (allocno[allocno1].reg);
+ blk2 = regno_basic_block (allocno[allocno2].reg);
+ gcc_assert (blk1 == 0 || blk2 == 0 || blk1 == blk2);
+#endif
+
+ /* By definition, an allocno does not conflict with itself. */
+ if (allocno1 == allocno2)
+ return;
+
+ bitnum = CONFLICT_BITNUM (allocno1, allocno2);
+
+#ifdef ENABLE_CHECKING
+ gcc_assert (bitnum >= 0 && bitnum < max_bitnum);
+#endif
+
+ index = bitnum / HOST_BITS_PER_WIDEST_FAST_INT;
+ word = conflicts[index];
+ mask = (HOST_WIDEST_FAST_INT) 1 << (bitnum % HOST_BITS_PER_WIDEST_FAST_INT);
+
+ if ((word & mask) == 0)
+ {
+ conflicts[index] = word | mask;
+ add_neighbor (allocno1, allocno2);
+ add_neighbor (allocno2, allocno1);
+ }
+}
+
+/* Add conflict edges between ALLOCNO1 and all allocnos currently live. */
+
+static void
+set_conflicts (int allocno1, sparseset live)
+{
+ int i;
+ HOST_WIDE_INT bitnum, index;
+ HOST_WIDEST_FAST_INT word, mask;
+ HOST_WIDE_INT partial_bitnum_allocno1;
+
+#ifdef ENABLE_CHECKING
+ gcc_assert (allocno1 >= 0 && allocno1 < max_allocno);
+#endif
+
+ partial_bitnum_allocno1 = partial_bitnum[allocno1];
+
+ EXECUTE_IF_SET_IN_SPARSESET (live, i)
+ {
+ /* By definition, an allocno does not conflict with itself. */
+ if (allocno1 == i)
+ continue;
+
+#ifdef ENABLE_CHECKING
+ gcc_assert (i >= 0 && i < max_allocno);
+#endif
+
+ bitnum = CONFLICT_BITNUM_FAST (allocno1, partial_bitnum_allocno1, i);
+
+#ifdef ENABLE_CHECKING
+ gcc_assert (bitnum >= 0 && bitnum < max_bitnum);
+#endif
+
+ index = bitnum / HOST_BITS_PER_WIDEST_FAST_INT;
+ word = conflicts[index];
+ mask = (HOST_WIDEST_FAST_INT) 1 << (bitnum % HOST_BITS_PER_WIDEST_FAST_INT);
+
+ if ((word & mask) == 0)
+ {
+ conflicts[index] = word | mask;
+ add_neighbor (allocno1, i);
+ add_neighbor (i, allocno1);
+ }
+ }
+}
+
+
/* Add a conflict between R1 and R2. */
static void
record_one_conflict_between_regnos (enum machine_mode mode1, int r1,
enum machine_mode mode2, int r2)
{
+ int allocno1 = reg_allocno[r1];
+ int allocno2 = reg_allocno[r2];
+
if (dump_file)
- fprintf (dump_file, " rocbr adding %d<=>%d\n", r1, r2);
- if (reg_allocno[r1] >= 0 && reg_allocno[r2] >= 0)
- {
- int tr1 = reg_allocno[r1];
- int tr2 = reg_allocno[r2];
- int ialloc_prod = tr1 * allocno_row_words;
+ fprintf (dump_file, " rocbr adding %d<=>%d\n", r1, r2);
- SET_ALLOCNO_LIVE ((&conflicts[ialloc_prod]), tr2);
- }
- else if (reg_allocno[r1] >= 0)
+ if (allocno1 >= 0 && allocno2 >= 0)
+ set_conflict (allocno1, allocno2);
+ else if (allocno1 >= 0)
{
- int tr1 = reg_allocno[r1];
-
if (r2 < FIRST_PSEUDO_REGISTER)
- add_to_hard_reg_set (&allocno[tr1].hard_reg_conflicts, mode2, r2);
+ add_to_hard_reg_set (&allocno[allocno1].hard_reg_conflicts, mode2, r2);
}
- else if (reg_allocno[r2] >= 0)
+ else if (allocno2 >= 0)
{
- int tr2 = reg_allocno[r2];
-
if (r1 < FIRST_PSEUDO_REGISTER)
- add_to_hard_reg_set (&allocno[tr2].hard_reg_conflicts, mode1, r1);
+ add_to_hard_reg_set (&allocno[allocno2].hard_reg_conflicts, mode1, r1);
}
/* Now, recursively handle the reg_renumber cases. */
before calling here. */
static void
-record_one_conflict (HOST_WIDE_INT *allocnos_live,
+record_one_conflict (sparseset allocnos_live,
HARD_REG_SET *hard_regs_live, int regno)
{
int i;
if (regno < FIRST_PSEUDO_REGISTER)
/* When a hard register becomes live, record conflicts with live
pseudo regs. */
- EXECUTE_IF_SET_IN_ALLOCNO_SET (allocnos_live, i,
+ EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i)
{
SET_HARD_REG_BIT (allocno[i].hard_reg_conflicts, regno);
if (dump_file)
fprintf (dump_file, " roc adding %d<=>%d\n", allocno[i].reg, regno);
- });
+ }
else
/* When a pseudo-register becomes live, record conflicts first
with hard regs, then with other pseudo regs. */
{
int ialloc = reg_allocno[regno];
- int ialloc_prod = ialloc * allocno_row_words;
if (dump_file)
{
&& !TEST_HARD_REG_BIT (allocno[ialloc].hard_reg_conflicts, i))
fprintf (dump_file, "%d ", i);
- EXECUTE_IF_SET_IN_ALLOCNO_SET (allocnos_live, i,
+ EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i)
{
- if (!GET_ALLOCNO_LIVE (&conflicts[ialloc_prod], i))
+ if (!conflict_p (ialloc, i))
fprintf (dump_file, "%d ", allocno[i].reg);
- });
+ }
fprintf (dump_file, ")\n");
}
IOR_HARD_REG_SET (allocno[ialloc].hard_reg_conflicts, *hard_regs_live);
-
- for (i = allocno_row_words - 1; i >= 0; i--)
- conflicts[ialloc_prod + i] |= allocnos_live[i];
+ set_conflicts (ialloc, allocnos_live);
}
}
nothing. */
static void
-mark_reg_store (HOST_WIDE_INT *allocnos_live,
+mark_reg_store (sparseset allocnos_live,
HARD_REG_SET *hard_regs_live,
struct df_ref *ref)
{
{
unsigned int start = regno;
unsigned int last = end_hard_regno (mode, regno);
- if ((GET_CODE (reg) == SUBREG) && !DF_REF_FLAGS_IS_SET (ref, DF_REF_EXTRACT))
+ if ((GET_CODE (reg) == SUBREG) && !DF_REF_FLAGS_IS_SET (ref, DF_REF_ZERO_EXTRACT))
{
start += subreg_regno_offset (regno, GET_MODE (SUBREG_REG (reg)),
SUBREG_BYTE (reg), GET_MODE (reg));
recog_data.operand[use + 1]);
}
}
-
- if (dump_file)
- fprintf (dump_file, " finished early clobber conflicts.\n");
}
/* Init LIVE_SUBREGS[ALLOCNUM] and LIVE_SUBREGS_USED[ALLOCNUM] using
- REG to the the number of nregs, and INIT_VALUE to get the
+ REG to the number of nregs, and INIT_VALUE to get the
initialization. ALLOCNUM need not be the regno of REG. */
void
/* Set REG to be not live in the sets ALLOCNOS_LIVE, LIVE_SUBREGS,
- HARD_REGS_LIVE. If EXTRACT is false, assume that the entire reg is
- set not live even if REG is a subreg. */
+ HARD_REGS_LIVE. DEF is the definition of the register. */
inline static void
-clear_reg_in_live (HOST_WIDE_INT *allocnos_live,
+clear_reg_in_live (sparseset allocnos_live,
sbitmap *live_subregs,
int *live_subregs_used,
HARD_REG_SET *hard_regs_live,
- rtx reg,
- bool extract)
+ rtx reg, struct df_ref *def)
{
unsigned int regno = (GET_CODE (reg) == SUBREG)
? REGNO (SUBREG_REG (reg)): REGNO (reg);
if (allocnum >= 0)
{
- if ((GET_CODE (reg) == SUBREG) && !extract)
-
+ if (GET_CODE (reg) == SUBREG
+ && !DF_REF_FLAGS_IS_SET (def, DF_REF_ZERO_EXTRACT))
{
unsigned int start = SUBREG_BYTE (reg);
unsigned int last = start + GET_MODE_SIZE (GET_MODE (reg));
- ra_init_live_subregs (GET_ALLOCNO_LIVE (allocnos_live, allocnum) != 0,
+ ra_init_live_subregs (sparseset_bit_p (allocnos_live, allocnum),
live_subregs, live_subregs_used, allocnum, reg);
+ if (!DF_REF_FLAGS_IS_SET (def, DF_REF_STRICT_LOW_PART))
+ {
+ /* Expand the range to cover entire words.
+ Bytes added here are "don't care". */
+ start = start / UNITS_PER_WORD * UNITS_PER_WORD;
+ last = ((last + UNITS_PER_WORD - 1)
+ / UNITS_PER_WORD * UNITS_PER_WORD);
+ }
+
/* Ignore the paradoxical bits. */
if ((int)last > live_subregs_used[allocnum])
last = live_subregs_used[allocnum];
if (sbitmap_empty_p (live_subregs[allocnum]))
{
live_subregs_used[allocnum] = 0;
- CLEAR_ALLOCNO_LIVE (allocnos_live, allocnum);
+ sparseset_clear_bit (allocnos_live, allocnum);
}
else
/* Set the allocnos live here because that bit has to be
true to get us to look at the live_subregs fields. */
- SET_ALLOCNO_LIVE (allocnos_live, allocnum);
+ sparseset_set_bit (allocnos_live, allocnum);
}
else
{
/* Resetting the live_subregs_used is effectively saying do not use the
subregs because we are writing the whole pseudo. */
live_subregs_used[allocnum] = 0;
- CLEAR_ALLOCNO_LIVE (allocnos_live, allocnum);
+ sparseset_clear_bit (allocnos_live, allocnum);
}
}
if (! fixed_regs[regno])
{
unsigned int start = regno;
- if ((GET_CODE (reg) == SUBREG) && !extract)
+ if (GET_CODE (reg) == SUBREG
+ && !DF_REF_FLAGS_IS_SET (def, DF_REF_ZERO_EXTRACT))
{
unsigned int last;
start += SUBREG_BYTE (reg);
set live even if REG is a subreg. */
inline static void
-set_reg_in_live (HOST_WIDE_INT *allocnos_live,
+set_reg_in_live (sparseset allocnos_live,
sbitmap *live_subregs,
int *live_subregs_used,
HARD_REG_SET *hard_regs_live,
unsigned int start = SUBREG_BYTE (reg);
unsigned int last = start + GET_MODE_SIZE (GET_MODE (reg));
- ra_init_live_subregs (GET_ALLOCNO_LIVE (allocnos_live, allocnum) != 0,
+ ra_init_live_subregs (sparseset_bit_p (allocnos_live, allocnum),
live_subregs, live_subregs_used, allocnum, reg);
/* Ignore the paradoxical bits. */
subregs because we are writing the whole pseudo. */
live_subregs_used[allocnum] = 0;
- SET_ALLOCNO_LIVE (allocnos_live, allocnum);
+ sparseset_set_bit (allocnos_live, allocnum);
}
if (regno >= FIRST_PSEUDO_REGISTER)
HARD_REG_SET hard_regs_live;
HARD_REG_SET renumbers_live;
- HOST_WIDE_INT *allocnos_live;
+ sparseset allocnos_live;
bitmap live = BITMAP_ALLOC (NULL);
VEC (df_ref_t, heap) *clobbers = NULL;
VEC (df_ref_t, heap) *dying_regs = NULL;
fprintf (dump_file, "\n");
}
- allocnos_live = XNEWVEC (HOST_WIDE_INT, allocno_row_words);
+ allocnos_live = sparseset_alloc (max_allocno);
FOR_EACH_BB (bb)
{
bitmap_copy (live, DF_LIVE_OUT (bb));
df_simulate_artificial_refs_at_end (bb, live);
- memset (allocnos_live, 0, allocno_row_words * sizeof (HOST_WIDE_INT));
+ sparseset_clear (allocnos_live);
memset (live_subregs_used, 0, max_allocno * sizeof (int));
CLEAR_HARD_REG_SET (hard_regs_live);
CLEAR_HARD_REG_SET (renumbers_live);
fprintf (dump_file, "%d ", i);
fprintf (dump_file, "] pseudos [");
- EXECUTE_IF_SET_IN_ALLOCNO_SET (allocnos_live, i,
+ EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i)
{
dump_ref (dump_file, " ", "", regno_reg_rtx[allocno[i].reg],
allocno[i].reg, live_subregs, live_subregs_used);
- });
+ }
fprintf (dump_file, "]\n");
}
rtx reg = DF_REF_REG (def);
set_reg_in_live (allocnos_live, live_subregs, live_subregs_used,
&hard_regs_live, reg,
- DF_REF_FLAGS_IS_SET (def, DF_REF_EXTRACT));
+ DF_REF_FLAGS_IS_SET (def, DF_REF_ZERO_EXTRACT));
if (dump_file)
dump_ref (dump_file, " adding def", "\n",
reg, DF_REF_REGNO (def), live_subregs, live_subregs_used);
rtx reg = DF_REF_REG (def);
clear_reg_in_live (allocnos_live, live_subregs, live_subregs_used,
- &hard_regs_live, reg,
- DF_REF_FLAGS_IS_SET (def, DF_REF_EXTRACT));
+ &hard_regs_live, reg, def);
if (dump_file)
dump_ref (dump_file, " clearing def", "\n",
reg, DF_REF_REGNO (def), live_subregs, live_subregs_used);
cannot not want to kill the renumbers from the other
pseudos. */
CLEAR_HARD_REG_SET (renumbers_live);
- EXECUTE_IF_SET_IN_ALLOCNO_SET (allocnos_live, i,
+ EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i)
{
unsigned int regno = allocno[i].reg;
int renumber = reg_renumber[regno];
if (renumber >= 0 && renumber < FIRST_PSEUDO_REGISTER)
set_renumbers_live (&renumbers_live, live_subregs, live_subregs_used,
i, renumber);
- });
+ }
/* Add the uses to the live sets. Keep track of the regs
that are dying inside the insn, this set will be useful
use unless that set also happens to wrapped in a
ZERO_EXTRACT. */
if (DF_REF_FLAGS_IS_SET (use, DF_REF_READ_WRITE)
- && (!DF_REF_FLAGS_IS_SET (use, DF_REF_EXTRACT))
+ && (!DF_REF_FLAGS_IS_SET (use, DF_REF_ZERO_EXTRACT))
&& DF_REF_FLAGS_IS_SET (use, DF_REF_SUBREG))
continue;
if (allocnum >= 0)
{
if (GET_CODE (reg) == SUBREG
- && !DF_REF_FLAGS_IS_SET (use, DF_REF_EXTRACT))
+ && !DF_REF_FLAGS_IS_SET (use, DF_REF_ZERO_EXTRACT))
{
unsigned int start = SUBREG_BYTE (reg);
unsigned int last = start + GET_MODE_SIZE (GET_MODE (reg));
- ra_init_live_subregs (GET_ALLOCNO_LIVE (allocnos_live, allocnum) != 0,
+ ra_init_live_subregs (sparseset_bit_p (allocnos_live, allocnum),
live_subregs, live_subregs_used, allocnum, reg);
/* Ignore the paradoxical bits. */
start++;
}
- SET_ALLOCNO_LIVE (allocnos_live, allocnum);
+ sparseset_set_bit (allocnos_live, allocnum);
if (renumber >= 0 && renumber < FIRST_PSEUDO_REGISTER)
set_renumbers_live (&renumbers_live, live_subregs, live_subregs_used,
allocnum, renumber);
}
-
- else if (GET_ALLOCNO_LIVE (allocnos_live, allocnum) == 0)
+ else if (live_subregs_used[allocnum] > 0
+ || !sparseset_bit_p (allocnos_live, allocnum))
{
if (dump_file)
- fprintf (dump_file, " dying pseudo\n");
-
+ fprintf (dump_file, " %sdying pseudo\n",
+ (live_subregs_used[allocnum] > 0) ? "partially ": "");
/* Resetting the live_subregs_used is
effectively saying do not use the subregs
because we are reading the whole pseudo. */
live_subregs_used[allocnum] = 0;
- SET_ALLOCNO_LIVE (allocnos_live, allocnum);
+ sparseset_set_bit (allocnos_live, allocnum);
if (renumber >= 0 && renumber < FIRST_PSEUDO_REGISTER)
set_renumbers_live (&renumbers_live, live_subregs, live_subregs_used,
allocnum, renumber);
FIXME: We should consider either adding a new kind of
clobber, or adding a flag to the clobber distinguish
these two cases. */
+ if (dump_file && VEC_length (df_ref_t, clobbers))
+ fprintf (dump_file, " clobber conflicts\n");
for (k = VEC_length (df_ref_t, clobbers) - 1; k >= 0; k--)
{
struct df_ref *def = VEC_index (df_ref_t, clobbers, k);
}
/* Early clobbers, by definition, need to not only
- clobber the registers that are live accross the insn
+ clobber the registers that are live across the insn
but need to clobber the registers that die within the
insn. The clobbering for registers live across the
insn is handled above. */
if (GET_CODE (PATTERN (insn)) == PARALLEL && multiple_sets (insn))
{
int j;
+ if (dump_file)
+ fprintf (dump_file, " multiple sets\n");
for (j = VEC_length (df_ref_t, dying_regs) - 1; j >= 0; j--)
{
int used_in_output = 0;
}
}
- /* Add the renumbers live to the hard_regs_live for the next few
+ /* Add the renumbers live to the hard_regs_live for the next few
calls. All of this gets recomputed at the top of the loop so
there is no harm. */
IOR_HARD_REG_SET (hard_regs_live, renumbers_live);
break;
record_one_conflict (allocnos_live, &hard_regs_live, regno);
}
+
+ EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i)
+ {
+ allocno[i].no_eh_reg = 1;
+ }
}
#endif
because caller-save, fixup_abnormal_edges and possibly the table
driven EH machinery are not quite ready to handle such regs live
across such edges. */
- EXECUTE_IF_SET_IN_ALLOCNO_SET (allocnos_live, i,
- {
- allocno[i].no_stack_reg = 1;
- });
+ EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i)
+ {
+ allocno[i].no_stack_reg = 1;
+ }
for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++)
record_one_conflict (allocnos_live, &hard_regs_live, i);
/* No need to record conflicts for call clobbered regs if we have
nonlocal labels around, as we don't ever try to allocate such
regs in this case. */
- if (! current_function_has_nonlocal_label)
+ if (! cfun->has_nonlocal_label)
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
if (call_used_regs [i])
record_one_conflict (allocnos_live, &hard_regs_live, i);
OSDN Git Service
