local-alloc.c

来自「GCC编译器源代码」· C语言 代码 · 共 1,992 行 · 第 1/5 页

      /* ... Fall through ...  */
    case 2:
      /* Put the best one to allocate in qty_order[0].  */
      if (qty_sugg_compare (0, 1) > 0)
	EXCHANGE (0, 1);

      /* ... Fall through ...  */

    case 1:
    case 0:
      /* Nothing to do here.  */
      break;

    default:
      qsort (qty_order, next_qty, sizeof (int), qty_sugg_compare_1);
    }

  /* Try to put each quantity in a suggested physical register, if it has one.
     This may cause registers to be allocated that otherwise wouldn't be, but
     this seems acceptable in local allocation (unlike global allocation).  */
  for (i = 0; i < next_qty; i++)
    {
      q = qty_order[i];
      if (qty_phys_num_sugg[q] != 0 || qty_phys_num_copy_sugg[q] != 0)
	qty_phys_reg[q] = find_free_reg (qty_min_class[q], qty_mode[q], q,
					 0, 1, qty_birth[q], qty_death[q]);
      else
	qty_phys_reg[q] = -1;
    }

  /* Order the qtys so we assign them registers in order of 
     decreasing length of life.  Normally call qsort, but if we 
     have only a very small number of quantities, sort them ourselves.  */

  for (i = 0; i < next_qty; i++)
    qty_order[i] = i;

#define EXCHANGE(I1, I2)  \
  { i = qty_order[I1]; qty_order[I1] = qty_order[I2]; qty_order[I2] = i; }

  switch (next_qty)
    {
    case 3:
      /* Make qty_order[2] be the one to allocate last.  */
      if (qty_compare (0, 1) > 0)
	EXCHANGE (0, 1);
      if (qty_compare (1, 2) > 0)
	EXCHANGE (2, 1);

      /* ... Fall through ...  */
    case 2:
      /* Put the best one to allocate in qty_order[0].  */
      if (qty_compare (0, 1) > 0)
	EXCHANGE (0, 1);

      /* ... Fall through ...  */

    case 1:
    case 0:
      /* Nothing to do here.  */
      break;

    default:
      qsort (qty_order, next_qty, sizeof (int), qty_compare_1);
    }

  /* Now for each qty that is not a hardware register,
     look for a hardware register to put it in.
     First try the register class that is cheapest for this qty,
     if there is more than one class.  */

  for (i = 0; i < next_qty; i++)
    {
      q = qty_order[i];
      if (qty_phys_reg[q] < 0)
	{
	  if (N_REG_CLASSES > 1)
	    {
	      qty_phys_reg[q] = find_free_reg (qty_min_class[q], 
					       qty_mode[q], q, 0, 0,
					       qty_birth[q], qty_death[q]);
	      if (qty_phys_reg[q] >= 0)
		continue;
	    }

	  if (qty_alternate_class[q] != NO_REGS)
	    qty_phys_reg[q] = find_free_reg (qty_alternate_class[q],
					     qty_mode[q], q, 0, 0,
					     qty_birth[q], qty_death[q]);
	}
    }

  /* Now propagate the register assignments
     to the pseudo regs belonging to the qtys.  */

  for (q = 0; q < next_qty; q++)
    if (qty_phys_reg[q] >= 0)
      {
	for (i = qty_first_reg[q]; i >= 0; i = reg_next_in_qty[i])
	  reg_renumber[i] = qty_phys_reg[q] + reg_offset[i];
	if (qty_scratch_rtx[q])
	  {
	    if (GET_CODE (qty_scratch_rtx[q]) == REG)
	      abort ();
	    qty_scratch_rtx[q] = gen_rtx (REG, GET_MODE (qty_scratch_rtx[q]),
					  qty_phys_reg[q]);
	    scratch_block[scratch_index] = b;
	    scratch_list[scratch_index++] = qty_scratch_rtx[q];

	  }
      }
}

/* Compare two quantities' priority for getting real registers.
   We give shorter-lived quantities higher priority.
   Quantities with more references are also preferred, as are quantities that
   require multiple registers.  This is the identical prioritization as
   done by global-alloc.

   We used to give preference to registers with *longer* lives, but using
   the same algorithm in both local- and global-alloc can speed up execution
   of some programs by as much as a factor of three!  */

/* Note that the quotient will never be bigger than
   the value of floor_log2 times the maximum number of
   times a register can occur in one insn (surely less than 100).
   Multiplying this by 10000 can't overflow.
   QTY_CMP_PRI is also used by qty_sugg_compare.  */

#define QTY_CMP_PRI(q)		\
  ((int) (((double) (floor_log2 (qty_n_refs[q]) * qty_n_refs[q] * qty_size[q]) \
	  / (qty_death[q] - qty_birth[q])) * 10000))

static int
qty_compare (q1, q2)
     int q1, q2;
{
  return QTY_CMP_PRI (q2) - QTY_CMP_PRI (q1);
}

static int
qty_compare_1 (q1p, q2p)
     const GENERIC_PTR q1p;
     const GENERIC_PTR q2p;
{
  register int q1 = *(int *)q1p, q2 = *(int *)q2p;
  register int tem = QTY_CMP_PRI (q2) - QTY_CMP_PRI (q1);

  if (tem != 0)
    return tem;

  /* If qtys are equally good, sort by qty number,
     so that the results of qsort leave nothing to chance.  */
  return q1 - q2;
}

/* Compare two quantities' priority for getting real registers.  This version
   is called for quantities that have suggested hard registers.  First priority
   goes to quantities that have copy preferences, then to those that have
   normal preferences.  Within those groups, quantities with the lower
   number of preferences have the highest priority.  Of those, we use the same
   algorithm as above.  */

#define QTY_CMP_SUGG(q)		\
  (qty_phys_num_copy_sugg[q]		\
    ? qty_phys_num_copy_sugg[q]	\
    : qty_phys_num_sugg[q] * FIRST_PSEUDO_REGISTER)

static int
qty_sugg_compare (q1, q2)
     int q1, q2;
{
  register int tem = QTY_CMP_SUGG (q1) - QTY_CMP_SUGG (q2);

  if (tem != 0)
    return tem;
  
  return QTY_CMP_PRI (q2) - QTY_CMP_PRI (q1);
}

static int
qty_sugg_compare_1 (q1p, q2p)
     const GENERIC_PTR q1p;
     const GENERIC_PTR q2p;
{
  register int q1 = *(int *)q1p, q2 = *(int *)q2p;
  register int tem = QTY_CMP_SUGG (q1) - QTY_CMP_SUGG (q2);

  if (tem != 0)
    return tem;

  tem = QTY_CMP_PRI (q2) - QTY_CMP_PRI (q1);
  if (tem != 0)
    return tem;

  /* If qtys are equally good, sort by qty number,
     so that the results of qsort leave nothing to chance.  */
  return q1 - q2;
}

#undef QTY_CMP_SUGG
#undef QTY_CMP_PRI

/* Attempt to combine the two registers (rtx's) USEDREG and SETREG.
   Returns 1 if have done so, or 0 if cannot.

   Combining registers means marking them as having the same quantity
   and adjusting the offsets within the quantity if either of
   them is a SUBREG).

   We don't actually combine a hard reg with a pseudo; instead
   we just record the hard reg as the suggestion for the pseudo's quantity.
   If we really combined them, we could lose if the pseudo lives
   across an insn that clobbers the hard reg (eg, movstr).

   ALREADY_DEAD is non-zero if USEDREG is known to be dead even though
   there is no REG_DEAD note on INSN.  This occurs during the processing
   of REG_NO_CONFLICT blocks.

   MAY_SAVE_COPYCOPY is non-zero if this insn is simply copying USEDREG to
   SETREG or if the input and output must share a register.
   In that case, we record a hard reg suggestion in QTY_PHYS_COPY_SUGG.
   
   There are elaborate checks for the validity of combining.  */

   
static int
combine_regs (usedreg, setreg, may_save_copy, insn_number, insn, already_dead)
     rtx usedreg, setreg;
     int may_save_copy;
     int insn_number;
     rtx insn;
     int already_dead;
{
  register int ureg, sreg;
  register int offset = 0;
  int usize, ssize;
  register int sqty;

  /* Determine the numbers and sizes of registers being used.  If a subreg
     is present that does not change the entire register, don't consider
     this a copy insn.  */

  while (GET_CODE (usedreg) == SUBREG)
    {
      if (GET_MODE_SIZE (GET_MODE (SUBREG_REG (usedreg))) > UNITS_PER_WORD)
	may_save_copy = 0;
      offset += SUBREG_WORD (usedreg);
      usedreg = SUBREG_REG (usedreg);
    }
  if (GET_CODE (usedreg) != REG)
    return 0;
  ureg = REGNO (usedreg);
  usize = REG_SIZE (usedreg);

  while (GET_CODE (setreg) == SUBREG)
    {
      if (GET_MODE_SIZE (GET_MODE (SUBREG_REG (setreg))) > UNITS_PER_WORD)
	may_save_copy = 0;
      offset -= SUBREG_WORD (setreg);
      setreg = SUBREG_REG (setreg);
    }
  if (GET_CODE (setreg) != REG)
    return 0;
  sreg = REGNO (setreg);
  ssize = REG_SIZE (setreg);

  /* If UREG is a pseudo-register that hasn't already been assigned a
     quantity number, it means that it is not local to this block or dies
     more than once.  In either event, we can't do anything with it.  */
  if ((ureg >= FIRST_PSEUDO_REGISTER && reg_qty[ureg] < 0)
      /* Do not combine registers unless one fits within the other.  */
      || (offset > 0 && usize + offset > ssize)
      || (offset < 0 && usize + offset < ssize)
      /* Do not combine with a smaller already-assigned object
	 if that smaller object is already combined with something bigger.  */
      || (ssize > usize && ureg >= FIRST_PSEUDO_REGISTER
	  && usize < qty_size[reg_qty[ureg]])
      /* Can't combine if SREG is not a register we can allocate.  */
      || (sreg >= FIRST_PSEUDO_REGISTER && reg_qty[sreg] == -1)
      /* Don't combine with a pseudo mentioned in a REG_NO_CONFLICT note.
	 These have already been taken care of.  This probably wouldn't
	 combine anyway, but don't take any chances.  */
      || (ureg >= FIRST_PSEUDO_REGISTER
	  && find_reg_note (insn, REG_NO_CONFLICT, usedreg))
      /* Don't tie something to itself.  In most cases it would make no
	 difference, but it would screw up if the reg being tied to itself
	 also dies in this insn.  */
      || ureg == sreg
      /* Don't try to connect two different hardware registers.  */
      || (ureg < FIRST_PSEUDO_REGISTER && sreg < FIRST_PSEUDO_REGISTER)
      /* Don't connect two different machine modes if they have different
	 implications as to which registers may be used.  */
      || !MODES_TIEABLE_P (GET_MODE (usedreg), GET_MODE (setreg)))
    return 0;

  /* Now, if UREG is a hard reg and SREG is a pseudo, record the hard reg in
     qty_phys_sugg for the pseudo instead of tying them.

     Return "failure" so that the lifespan of UREG is terminated here;
     that way the two lifespans will be disjoint and nothing will prevent
     the pseudo reg from being given this hard reg.  */

  if (ureg < FIRST_PSEUDO_REGISTER)
    {
      /* Allocate a quantity number so we have a place to put our
	 suggestions.  */
      if (reg_qty[sreg] == -2)
	reg_is_born (setreg, 2 * insn_number);

      if (reg_qty[sreg] >= 0)
	{
	  if (may_save_copy
	      && ! TEST_HARD_REG_BIT (qty_phys_copy_sugg[reg_qty[sreg]], ureg))
	    {
	      SET_HARD_REG_BIT (qty_phys_copy_sugg[reg_qty[sreg]], ureg);
	      qty_phys_num_copy_sugg[reg_qty[sreg]]++;
	    }
	  else if (! TEST_HARD_REG_BIT (qty_phys_sugg[reg_qty[sreg]], ureg))
	    {
	      SET_HARD_REG_BIT (qty_phys_sugg[reg_qty[sreg]], ureg);
	      qty_phys_num_sugg[reg_qty[sreg]]++;
	    }
	}
      return 0;
    }

  /* Similarly for SREG a hard register and UREG a pseudo register.  */

  if (sreg < FIRST_PSEUDO_REGISTER)
    {
      if (may_save_copy
	  && ! TEST_HARD_REG_BIT (qty_phys_copy_sugg[reg_qty[ureg]], sreg))
	{
	  SET_HARD_REG_BIT (qty_phys_copy_sugg[reg_qty[ureg]], sreg);
	  qty_phys_num_copy_sugg[reg_qty[ureg]]++;
	}
      else if (! TEST_HARD_REG_BIT (qty_phys_sugg[reg_qty[ureg]], sreg))
	{
	  SET_HARD_REG_BIT (qty_phys_sugg[reg_qty[ureg]], sreg);
	  qty_phys_num_sugg[reg_qty[ureg]]++;
	}
      return 0;
    }

  /* At this point we know that SREG and UREG are both pseudos.
     Do nothing if SREG already has a quantity or is a register that we
     don't allocate.  */
  if (reg_qty[sreg] >= -1
      /* If we are not going to let any regs live across calls,
	 don't tie a call-crossing reg to a non-call-crossing reg.  */
      || (current_function_has_nonlocal_label
	  && ((REG_N_CALLS_CROSSED (ureg) > 0)
	      != (REG_N_CALLS_CROSSED (sreg) > 0))))
    return 0;

  /* We don't already know about SREG, so tie it to UREG
     if this is the last use of UREG, provided the classes they want
     are compatible.  */

  if ((already_dead || find_regno_note (insn, REG_DEAD, ureg))
      && reg_meets_class_p (sreg, qty_min_class[reg_qty[ureg]]))
    {
      /* Add SREG to UREG's quantity.  */
      sqty = reg_qty[ureg];
      reg_qty[sreg] = sqty;
      reg_offset[sreg] = reg_offset[ureg] + offset;
      reg_next_in_qty[sreg] = qty_first_reg[sqty];
      qty_first_reg[sqty] = sreg;

      /* If SREG's reg class is smaller, set qty_min_class[SQTY].  */
      update_qty_class (sqty, sreg);

      /* Update info about quantity SQTY.  */
      qty_n_calls_crossed[sqty] += REG_N_CALLS_CROSSED (sreg);
      qty_n_refs[sqty] += REG_N_REFS (sreg);
      if (usize < ssize)
	{
	  register int i;

	  for (i = qty_first_reg[sqty]; i >= 0; i = reg_next_in_qty[i])
	    reg_offset[i] -= offset;

	  qty_size[sqty] = ssize;
	  qty_mode[sqty] = GET_MODE (setreg);
	}
    }
  else
    return 0;

  return 1;
}

/* Return 1 if the preferred class of REG allows it to be tied
   to a quantity or register whose class is CLAS