Google Git
Sign in
gnu / gcc / a553301508c06badb13dac809ab0b07b9ce29622 / . / gcc / ra-conflict.c
blob: 78d4f9246f07935201361bb5ff82ed719b087067 [file] [log] [blame]
/* Allocate registers for pseudo-registers that span basic blocks.
Copyright (C) 2007 Free Software Foundation, Inc.
Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later
version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
for more details.
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3. If not see
<http://www.gnu.org/licenses/>. */
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "machmode.h"
#include "hard-reg-set.h"
#include "rtl.h"
#include "tm_p.h"
#include "flags.h"
#include "regs.h"
#include "function.h"
#include "insn-config.h"
#include "recog.h"
#include "reload.h"
#include "output.h"
#include "toplev.h"
#include "tree-pass.h"
#include "timevar.h"
#include "df.h"
#include "vecprim.h"
#include "ra.h"
#include "sbitmap.h"
#include "sparseset.h"
/* Externs defined in regs.h. */
int max_allocno;
struct allocno *allocno;
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 (allocno1 >= 0 && allocno2 >= 0)
set_conflict (allocno1, allocno2);
else if (allocno1 >= 0)
{
if (r2 < FIRST_PSEUDO_REGISTER)
add_to_hard_reg_set (&allocno[allocno1].hard_reg_conflicts, mode2, r2);
}
else if (allocno2 >= 0)
{
if (r1 < FIRST_PSEUDO_REGISTER)
add_to_hard_reg_set (&allocno[allocno2].hard_reg_conflicts, mode1, r1);
}
/* Now, recursively handle the reg_renumber cases. */
if (reg_renumber[r1] >= 0)
record_one_conflict_between_regnos (mode1, reg_renumber[r1], mode2, r2);
if (reg_renumber[r2] >= 0)
record_one_conflict_between_regnos (mode1, r1, mode2, reg_renumber[r2]);
}
/* Record a conflict between register REGNO and everything currently
live. REGNO must not be a pseudo reg that was allocated by
local_alloc; such numbers must be translated through reg_renumber
before calling here. */
static void
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_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];
if (dump_file)
{
fprintf (dump_file, " roc adding %d<=>(", regno);
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
if (TEST_HARD_REG_BIT (*hard_regs_live, i)
&& !TEST_HARD_REG_BIT (allocno[ialloc].hard_reg_conflicts, i))
fprintf (dump_file, "%d ", i);
EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, 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);
set_conflicts (ialloc, allocnos_live);
}
}
/* Handle the case where REG is set by the insn being scanned, during
the backward scan to accumulate conflicts. Record a conflict with
all other registers already live.
REG might actually be something other than a register; if so, we do
nothing. */
static void
mark_reg_store (sparseset allocnos_live,
HARD_REG_SET *hard_regs_live,
struct df_ref *ref)
{
rtx reg = DF_REF_REG (ref);
unsigned int regno = DF_REF_REGNO (ref);
enum machine_mode mode = GET_MODE (reg);
/* Either this is one of the max_allocno pseudo regs not allocated,
or it is or has a hardware reg. First handle the pseudo-regs. */
if (regno >= FIRST_PSEUDO_REGISTER && reg_allocno[regno] >= 0)
record_one_conflict (allocnos_live, hard_regs_live, regno);
if (reg_renumber[regno] >= 0)
regno = reg_renumber[regno];
/* Handle hardware regs (and pseudos allocated to hard regs). */
if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno])
{
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))
{
start += subreg_regno_offset (regno, GET_MODE (SUBREG_REG (reg)),
SUBREG_BYTE (reg), GET_MODE (reg));
last = start + subreg_nregs_with_regno (regno, reg);
}
regno = start;
while (regno < last)
record_one_conflict (allocnos_live, hard_regs_live, regno++);
}
}
/* Return true if REGNO with MODE can be assigned to a register in
CL. */
static bool
may_overlap_class_p (enum machine_mode mode, unsigned int regno,
enum reg_class rc)
{
if (regno >= FIRST_PSEUDO_REGISTER)
{
enum reg_class pref_class = reg_preferred_class (regno);
enum reg_class alt_class = reg_alternate_class (regno);
return (reg_classes_intersect_p (rc, pref_class)
|| reg_classes_intersect_p (rc, alt_class));
}
else
return in_hard_reg_set_p (reg_class_contents[rc], mode, regno);
}
/* SRC is an input operand to an instruction in which register DEST is
an output operand. SRC may be bound to a member of class SRC_CLASS
and DEST may be bound to an earlyclobbered register that overlaps
SRC_CLASS. If SRC is a register that might be allocated a member
of SRC_CLASS, add a conflict between it and DEST. */
static void
add_conflicts_for_earlyclobber (rtx dest, enum reg_class src_class, rtx src)
{
if (GET_CODE (src) == SUBREG)
src = SUBREG_REG (src);
if (REG_P (src)
&& may_overlap_class_p (GET_MODE (src), REGNO (src), src_class))
record_one_conflict_between_regnos (GET_MODE (src), REGNO (src),
GET_MODE (dest), REGNO (dest));
}
/* Look at the defs in INSN and determine if any of them are marked as
early clobber. If they are marked as early clobber, add a conflict
between any input operand that could be allocated to the same
register. */
static void
set_conflicts_for_earlyclobber (rtx insn)
{
int alt;
int def;
int use;
extract_insn (insn);
preprocess_constraints ();
if (dump_file)
fprintf (dump_file, " starting early clobber conflicts.\n");
for (alt = 0; alt < recog_data.n_alternatives; alt++)
for (def = 0; def < recog_data.n_operands; def++)
if ((recog_op_alt[def][alt].earlyclobber)
&& (recog_op_alt[def][alt].cl != NO_REGS))
{
rtx dreg = recog_data.operand[def];
enum machine_mode dmode = recog_data.operand_mode[def];
if (GET_CODE (dreg) == SUBREG)
dreg = SUBREG_REG (dreg);
if (REG_P (dreg)
&& may_overlap_class_p (dmode, REGNO (dreg), recog_op_alt[def][alt].cl))
for (use = 0; use < recog_data.n_operands; use++)
if (use != def
&& recog_data.operand_type[use] != OP_OUT
&& reg_classes_intersect_p (recog_op_alt[def][alt].cl,
recog_op_alt[use][alt].cl))
{
add_conflicts_for_earlyclobber (dreg,
recog_op_alt[use][alt].cl,
recog_data.operand[use]);
/* Reload may end up swapping commutative operands,
so you have to take both orderings into account.
The constraints for the two operands can be
completely different. (Indeed, if the
constraints for the two operands are the same
for all alternatives, there's no point marking
them as commutative.) */
if (use < recog_data.n_operands + 1
&& recog_data.constraints[use][0] == '%')
add_conflicts_for_earlyclobber (dreg,
recog_op_alt[use][alt].cl,
recog_data.operand[use + 1]);
}
}
}
/* Init LIVE_SUBREGS[ALLOCNUM] and LIVE_SUBREGS_USED[ALLOCNUM] using
REG to the the number of nregs, and INIT_VALUE to get the
initialization. ALLOCNUM need not be the regno of REG. */
void
ra_init_live_subregs (bool init_value,
sbitmap *live_subregs,
int *live_subregs_used,
int allocnum,
rtx reg)
{
unsigned int regno = REGNO (SUBREG_REG (reg));
int size = GET_MODE_SIZE (GET_MODE (regno_reg_rtx[regno]));
gcc_assert (size > 0);
/* Been there, done that. */
if (live_subregs_used[allocnum])
return;
/* Create a new one with zeros. */
if (live_subregs[allocnum] == NULL)
live_subregs[allocnum] = sbitmap_alloc (size);
/* If the entire reg was live before blasting into subregs, we need
to init all of the subregs to ones else init to 0. */
if (init_value)
sbitmap_ones (live_subregs[allocnum]);
else
sbitmap_zero (live_subregs[allocnum]);
/* Set the number of bits that we really want. */
live_subregs_used[allocnum] = size;
}
/* Set REG to be not live in the sets ALLOCNOS_LIVE, LIVE_SUBREGS,
HARD_REGS_LIVE. DEF is the definition of the register. */
inline static void
clear_reg_in_live (sparseset allocnos_live,
sbitmap *live_subregs,
int *live_subregs_used,
HARD_REG_SET *hard_regs_live,
rtx reg, struct df_ref *def)
{
unsigned int regno = (GET_CODE (reg) == SUBREG)
? REGNO (SUBREG_REG (reg)): REGNO (reg);
int allocnum = reg_allocno[regno];
if (allocnum >= 0)
{
if (GET_CODE (reg) == SUBREG
&& !DF_REF_FLAGS_IS_SET (def, DF_REF_EXTRACT))
{
unsigned int start = SUBREG_BYTE (reg);
unsigned int last = start + GET_MODE_SIZE (GET_MODE (reg));
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_LOWER_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];
while (start < last)
{
RESET_BIT (live_subregs[allocnum], start);
start++;
}
if (sbitmap_empty_p (live_subregs[allocnum]))
{
live_subregs_used[allocnum] = 0;
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. */
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;
sparseset_clear_bit (allocnos_live, allocnum);
}
}
if (regno >= FIRST_PSEUDO_REGISTER)
return;
/* Handle hardware regs (and pseudos allocated to hard regs). */
if (! fixed_regs[regno])
{
unsigned int start = regno;
if (GET_CODE (reg) == SUBREG
&& !DF_REF_FLAGS_IS_SET (def, DF_REF_EXTRACT))
{
unsigned int last;
start += SUBREG_BYTE (reg);
last = start + subreg_nregs_with_regno (regno, reg);
regno = start;
while (regno < last)
{
CLEAR_HARD_REG_BIT (*hard_regs_live, regno);
regno++;
}
}
else
remove_from_hard_reg_set (hard_regs_live, GET_MODE (reg), regno);
}
}
/* Set REG to be live in the sets ALLOCNOS_LIVE, LIVE_SUBREGS,
HARD_REGS_LIVE. If EXTRACT is false, assume that the entire reg is
set live even if REG is a subreg. */
inline static void
set_reg_in_live (sparseset allocnos_live,
sbitmap *live_subregs,
int *live_subregs_used,
HARD_REG_SET *hard_regs_live,
rtx reg,
bool extract)
{
unsigned int regno = (GET_CODE (reg) == SUBREG)
? REGNO (SUBREG_REG (reg)): REGNO (reg);
int allocnum = reg_allocno[regno];
if (allocnum >= 0)
{
if ((GET_CODE (reg) == SUBREG) && !extract)
{
unsigned int start = SUBREG_BYTE (reg);
unsigned int last = start + GET_MODE_SIZE (GET_MODE (reg));
ra_init_live_subregs (sparseset_bit_p (allocnos_live, allocnum),
live_subregs, live_subregs_used, allocnum, reg);
/* Ignore the paradoxical bits. */
if ((int)last > live_subregs_used[allocnum])
last = live_subregs_used[allocnum];
while (start < last)
{
SET_BIT (live_subregs[allocnum], start);
start++;
}
}
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;
sparseset_set_bit (allocnos_live, allocnum);
}
if (regno >= FIRST_PSEUDO_REGISTER)
return;
/* Handle hardware regs (and pseudos allocated to hard regs). */
if (! fixed_regs[regno])
{
if ((GET_CODE (reg) == SUBREG) && !extract)
{
unsigned int start = regno;
unsigned int last;
start += subreg_regno_offset (regno, GET_MODE (SUBREG_REG (reg)),
SUBREG_BYTE (reg), GET_MODE (reg));
last = start + subreg_nregs_with_regno (regno, reg);
regno = start;
while (regno < last)
{
SET_HARD_REG_BIT (*hard_regs_live, regno);
regno++;
}
}
else
add_to_hard_reg_set (hard_regs_live, GET_MODE (reg), regno);
}
}
/* Add hard reg conflicts to RENUMBERS_LIVE assuming that pseudo in
allocno[ALLOCNUM] is allocated to a set of hard regs starting at
RENUMBER.
We are smart about the case where only subregs of REG have been
set, as indicated by LIVE_SUBREGS[ALLOCNUM] and
LIVE_SUBREGS_USED[ALLOCNUM]. See global_conflicts for description
of LIVE_SUBREGS and LIVE_SUBREGS_USED. */
inline static void
set_renumbers_live (HARD_REG_SET *renumbers_live,
sbitmap *live_subregs,
int *live_subregs_used,
int allocnum, int renumber)
{
/* The width of the pseudo. */
int nbytes = live_subregs_used[allocnum];
int regno = allocno[allocnum].reg;
enum machine_mode mode = GET_MODE (regno_reg_rtx[regno]);
if (dump_file)
fprintf (dump_file, " set_renumbers_live %d->%d ",
regno, renumber);
if (nbytes > 0)
{
int i;
sbitmap live_subs = live_subregs[allocnum];
/* First figure out how many hard regs we are considering using. */
int target_nregs = hard_regno_nregs[renumber][mode];
/* Now figure out the number of bytes per hard reg. Note that
this may be different that what would be obtained by looking
at the mode in the pseudo. For instance, a complex number
made up of 2 32-bit parts gets mapped to 2 hard regs, even if
the hardregs are 64-bit floating point values. */
int target_width = nbytes / target_nregs;
if (dump_file)
fprintf (dump_file, "target_nregs=%d target_width=%d nbytes=%d",
target_nregs, target_width, nbytes);
for (i = 0; i < target_nregs; i++)
{
int j;
bool set = false;
for (j = 0; j < target_width; j++)
{
int reg_start = i * target_width;
if (reg_start + j >= nbytes)
break;
set |= TEST_BIT (live_subs, reg_start + j);
}
if (set)
SET_HARD_REG_BIT (*renumbers_live, renumber + i);
}
}
else
add_to_hard_reg_set (renumbers_live, mode, renumber);
if (dump_file)
fprintf (dump_file, "\n");
}
/* Dump out a REF with its reg_renumber range to FILE using
PREFIX. */
static void
dump_ref (FILE *file,
const char * prefix,
const char * suffix,
rtx reg,
unsigned int regno,
sbitmap *live_subregs,
int *live_subregs_used
)
{
int allocnum = reg_allocno[regno];
fprintf (file, "%s %d", prefix, regno);
if (allocnum >= 0
&& live_subregs_used[allocnum] > 0)
{
int j;
char s = '[';
for (j = 0; j < live_subregs_used[allocnum]; j++)
if (TEST_BIT (live_subregs[allocnum], j))
{
fprintf (dump_file, "%c%d", s, j);
s = ',';
}
fprintf (dump_file, "]");
}
if (reg_renumber[regno] >= 0)
{
enum machine_mode mode = GET_MODE (reg);
unsigned int start;
unsigned int last;
regno = reg_renumber[regno];
start = regno;
last = end_hard_regno (mode, regno);
if (GET_CODE (reg) == SUBREG)
{
start += subreg_regno_offset (regno, GET_MODE (SUBREG_REG (reg)),
SUBREG_BYTE (reg), GET_MODE (reg));
last = start + subreg_nregs_with_regno (regno, reg);
}
if (start == last - 1)
fprintf (file, "(%d)", start);
else
fprintf (file, "(%d:%d..%d)", regno, start, last-1);
}
fprintf (file, suffix);
}
/* Scan the rtl code and record all conflicts and register preferences in the
conflict matrices and preference tables. */
void
global_conflicts (void)
{
unsigned int i;
basic_block bb;
rtx insn;
/* Regs that have allocnos can be in either
hard_regs_live (if regno < FIRST_PSEUDO_REGISTER) or
allocnos_live (if regno >= FIRST_PSEUDO_REGISTER) or
both if local_alloc has preallocated it and reg_renumber >= 0. */
HARD_REG_SET hard_regs_live;
HARD_REG_SET renumbers_live;
sparseset allocnos_live;
bitmap live = BITMAP_ALLOC (NULL);
VEC (df_ref_t, heap) *clobbers = NULL;
VEC (df_ref_t, heap) *dying_regs = NULL;
/* live_subregs is a vector used to keep accurate information about
which hardregs are live in multiword pseudos. live_subregs and
live_subregs_used are indexed by reg_allocno. The live_subreg
entry for a particular pseudo is a bitmap with one bit per byte
of the register. It is only used if the corresponding element is
non zero in live_subregs_used. The value in live_subregs_used is
number of bytes that the pseudo can occupy. */
sbitmap *live_subregs = XCNEWVEC (sbitmap, max_allocno);
int *live_subregs_used = XNEWVEC (int, max_allocno);
if (dump_file)
{
fprintf (dump_file, "fixed registers : ");
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
if (fixed_regs[i])
fprintf (dump_file, "%d ", i);
fprintf (dump_file, "\n");
}
allocnos_live = sparseset_alloc (max_allocno);
FOR_EACH_BB (bb)
{
bitmap_iterator bi;
bitmap_copy (live, DF_LIVE_OUT (bb));
df_simulate_artificial_refs_at_end (bb, live);
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);
/* Initialize allocnos_live and hard_regs_live for bottom of block. */
EXECUTE_IF_SET_IN_BITMAP (live, 0, i, bi)
{
if (i >= FIRST_PSEUDO_REGISTER)
break;
if (! fixed_regs[i])
SET_HARD_REG_BIT (hard_regs_live, i);
}
EXECUTE_IF_SET_IN_BITMAP (live, FIRST_PSEUDO_REGISTER, i, bi)
{
int allocnum = reg_allocno[i];
if (allocnum >= 0)
{
int renumber = reg_renumber[i];
rtx reg = regno_reg_rtx[i];
set_reg_in_live (allocnos_live, live_subregs, live_subregs_used,
&hard_regs_live, reg, false);
if (renumber >= 0 && renumber < FIRST_PSEUDO_REGISTER)
set_renumbers_live (&renumbers_live, live_subregs, live_subregs_used,
allocnum, renumber);
}
}
if (dump_file)
fprintf (dump_file, "\nstarting basic block %d\n\n", bb->index);
FOR_BB_INSNS_REVERSE (bb, insn)
{
unsigned int uid = INSN_UID (insn);
struct df_ref **def_rec;
struct df_ref **use_rec;
if (!INSN_P (insn))
continue;
if (dump_file)
{
fprintf (dump_file, "insn = %d live = hardregs [", uid);
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
if (TEST_HARD_REG_BIT (hard_regs_live, i))
fprintf (dump_file, "%d ", i);
fprintf (dump_file, "] renumbered [");
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
if (TEST_HARD_REG_BIT (renumbers_live, i))
fprintf (dump_file, "%d ", i);
fprintf (dump_file, "] pseudos [");
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");
}
/* Add the defs into live. Most of them will already be
there, the ones that are missing are the unused ones and
the clobbers. We do this in order to make sure that
interferences are added between every def and everything
that is live across the insn. These defs will be removed
later. */
for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
{
struct df_ref *def = *def_rec;
/* FIXME: Ignoring may clobbers is technically the wrong
thing to do. However the old version of the this
code ignores may clobbers (and instead has many
places in the register allocator to handle these
constraints). It is quite likely that with a new
allocator, the correct thing to do is to not ignore
the constraints and then do not put in the large
number of special checks. */
if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
{
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));
if (dump_file)
dump_ref (dump_file, " adding def", "\n",
reg, DF_REF_REGNO (def), live_subregs, live_subregs_used);
}
}
/* Add the hardregs into renumbers_live to build the
interferences. Renumbers_live will be rebuilt in the
next step from scratch, so corrupting it here is no
problem. */
IOR_HARD_REG_SET (renumbers_live, hard_regs_live);
/* Add the interferences for the defs. */
for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
{
struct df_ref *def = *def_rec;
if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
mark_reg_store (allocnos_live, &renumbers_live, def);
}
/* Remove the defs from the live sets. Leave the partial
and conditional defs in the set because they do not
kill. */
VEC_truncate (df_ref_t, clobbers, 0);
for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
{
struct df_ref *def = *def_rec;
if (!DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL))
{
rtx reg = DF_REF_REG (def);
clear_reg_in_live (allocnos_live, live_subregs, live_subregs_used,
&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);
}
if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER))
VEC_safe_push (df_ref_t, heap, clobbers, def);
}
/* Go thru all of the live pseudos and reset renumbers_live.
We must start from scratch here because there could have
been several pseudos alive that have the same
reg_renumber and if we see a clobber for one of them, we
cannot not want to kill the renumbers from the other
pseudos. */
CLEAR_HARD_REG_SET (renumbers_live);
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
later. */
VEC_truncate (df_ref_t, dying_regs, 0);
for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
{
struct df_ref *use = *use_rec;
unsigned int regno = DF_REF_REGNO (use);
bool added = false;
int renumber = reg_renumber[regno];
int allocnum = reg_allocno[regno];
bool renumbering = false;
rtx reg = DF_REF_REG (use);
/* DF_REF_READ_WRITE on a use means that this use is
fabricated from a def that is a partial set to a
multiword reg. Here, we only model the subreg case
precisely so we do not need to look at the fabricated
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_SUBREG))
continue;
if (dump_file)
dump_ref (dump_file, " seeing use", "\n",
reg, regno, live_subregs, live_subregs_used);
if (allocnum >= 0)
{
if (GET_CODE (reg) == SUBREG
&& !DF_REF_FLAGS_IS_SET (use, DF_REF_EXTRACT))
{
unsigned int start = SUBREG_BYTE (reg);
unsigned int last = start + GET_MODE_SIZE (GET_MODE (reg));
ra_init_live_subregs (sparseset_bit_p (allocnos_live, allocnum),
live_subregs, live_subregs_used, allocnum, reg);
/* Ignore the paradoxical bits. */
if ((int)last > live_subregs_used[allocnum])
last = live_subregs_used[allocnum];
while (start < last)
{
if (!TEST_BIT (live_subregs[allocnum], start))
{
if (dump_file)
fprintf (dump_file, " dying pseudo subreg %d[%d]\n", regno, start);
SET_BIT (live_subregs[allocnum], start);
added = true;
}
start++;
}
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 (live_subregs_used[allocnum] > 0
|| !sparseset_bit_p (allocnos_live, allocnum))
{
if (dump_file)
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;
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);
added = true;
}
}
if (renumber >= 0 && renumber < FIRST_PSEUDO_REGISTER)
{
regno = renumber;
renumbering = true;
}
if (regno < FIRST_PSEUDO_REGISTER)
{
unsigned int start = regno;
unsigned int last;
if (GET_CODE (reg) == SUBREG)
{
start += subreg_regno_offset (regno, GET_MODE (SUBREG_REG (reg)),
SUBREG_BYTE (reg), GET_MODE (reg));
last = start + subreg_nregs_with_regno (regno, reg);
}
else
last = end_hard_regno (GET_MODE (reg), regno);
regno = start;
while (regno < last)
{
if ((!TEST_HARD_REG_BIT (hard_regs_live, regno))
&& (!TEST_HARD_REG_BIT (renumbers_live, regno))
&& ! fixed_regs[regno])
{
if (dump_file)
fprintf (dump_file, " dying hard reg %d\n", regno);
if (renumbering)
SET_HARD_REG_BIT (renumbers_live, regno);
else
SET_HARD_REG_BIT (hard_regs_live, regno);
added = true;
}
regno++;
}
}
if (added)
VEC_safe_push (df_ref_t, heap, dying_regs, use);
}
/* These three cases are all closely related, they all deal
with some set of outputs of the insn need to conflict
with some of the registers that are used by the insn but
die within the insn. If no registers die within the insn,
the tests can be skipped. */
if (VEC_length (df_ref_t, dying_regs) > 0)
{
int k;
/* There appears to be an ambiguity as to what a clobber
means in an insn. In some cases, the clobber happens
within the processing of the insn and in some cases
it happens at the end of processing the insn. There
is currently no way to distinguish these two cases so
this code causes real clobbers to interfere with
registers that die within an insn.
This is consistent with the prior version of
interference graph builder but is was discovered
while developing this version of the code, that on
some architectures such as the x86-64, the clobbers
only appear to happen at the end of the insn.
However, the ppc-32 contains clobbers for which these
interferences are necessary.
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);
int j;
for (j = VEC_length (df_ref_t, dying_regs) - 1; j >= 0; j--)
{
struct df_ref *use = VEC_index (df_ref_t, dying_regs, j);
record_one_conflict_between_regnos (GET_MODE (DF_REF_REG (def)),
DF_REF_REGNO (def),
GET_MODE (DF_REF_REG (use)),
DF_REF_REGNO (use));
}
}
/* Early clobbers, by definition, need to not only
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. */
set_conflicts_for_earlyclobber (insn);
/* If INSN is a store with multiple outputs, then any
reg that dies here and is used inside of the address
of the output must conflict with the other outputs.
FIXME: There has been some discussion as to whether
this is right place to handle this issue. This is a
hold over from an early version global conflicts.
1) There is some evidence that code only deals with a
bug that is only on the m68k. The conditions of this
test are such that this case only triggers for a very
peculiar insn, one that is a parallel where one of
the sets is a store and the other sets a reg that is
used in the address of the store. See
http://gcc.gnu.org/ml/gcc-patches/1998-12/msg00259.html
2) The situation that this is addressing is a bug in
the part of reload that handles stores, adding this
conflict only hides the problem. (Of course no one
really wants to fix reload so it is understandable
why a bandaid was just added here.)
Just because an output is unused does not mean the
compiler can assume the side effect will not occur.
Consider if REG appears in the address of an output
and we reload the output. If we allocate REG to the
same hard register as an unused output we could set
the hard register before the output reload insn.
3) This could actually be handled by making the other
(non store) operand of the insn be an early clobber.
This would insert the same conflict, even if it is
not technically an early clobber. */
/* It is unsafe to use !single_set here since it will ignore an
unused output. */
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;
struct df_ref *use = VEC_index (df_ref_t, dying_regs, j);
rtx reg = DF_REF_REG (use);
int uregno = DF_REF_REGNO (use);
enum machine_mode umode = GET_MODE (DF_REF_REG (use));
int k;
for (k = XVECLEN (PATTERN (insn), 0) - 1; k >= 0; k--)
{
rtx set = XVECEXP (PATTERN (insn), 0, k);
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)))
used_in_output = 1;
}
if (used_in_output)
for (k = XVECLEN (PATTERN (insn), 0) - 1; k >= 0; k--)
{
rtx set = XVECEXP (PATTERN (insn), 0, k);
if (GET_CODE (set) == SET
&& REG_P (SET_DEST (set))
&& !rtx_equal_p (reg, SET_DEST (set)))
record_one_conflict_between_regnos (GET_MODE (SET_DEST (set)),
REGNO (SET_DEST (set)),
umode, uregno);
}
}
}
}
}
/* 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);
#ifdef EH_RETURN_DATA_REGNO
if (bb_has_eh_pred (bb))
{
unsigned int i;
for (i = 0; ; ++i)
{
unsigned int regno = EH_RETURN_DATA_REGNO (i);
if (regno == INVALID_REGNUM)
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
if (bb_has_abnormal_pred (bb))
{
unsigned int i;
#ifdef STACK_REGS
/* Pseudos can't go in stack regs at the start of a basic block that
is reached by an abnormal edge. Likewise for call clobbered regs,
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_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);
#endif
/* 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)
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
if (call_used_regs [i])
record_one_conflict (allocnos_live, &hard_regs_live, i);
}
}
for (i = 0; i < (unsigned int)max_allocno; i++)
if (live_subregs[i])
free (live_subregs[i]);
/* Clean up. */
free (allocnos_live);
free (live_subregs);
free (live_subregs_used);
VEC_free (df_ref_t, heap, dying_regs);
VEC_free (df_ref_t, heap, clobbers);
BITMAP_FREE (live);
}