Daily bump.

[official-gcc.git] / gcc / ra-conflict.c

/* 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_ZERO_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_ZERO_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_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];

          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_ZERO_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_ZERO_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_ZERO_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_ZERO_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);
}