local-alloc.c

早期freebsd实现

		      && rtx_equal_p (recog_operand[2],
				      XEXP (SET_SRC (PATTERN (insn)), 0))
#endif
		      && (r1 = recog_operand[2],
			  GET_CODE (r1) == REG || GET_CODE (r1) == SUBREG))
		    win = combine_regs (r1, r0, may_save_copy,
					insn_number, insn, 0);
		}
	    }

	  /* Recognize an insn sequence with an ultimate result
	     which can safely overlap one of the inputs.
	     The sequence begins with a CLOBBER of its result,
	     and ends with an insn that copies the result to itself
	     and has a REG_EQUAL note for an equivalent formula.
	     That note indicates what the inputs are.
	     The result and the input can overlap if each insn in
	     the sequence either doesn't mention the input
	     or has a REG_NO_CONFLICT note to inhibit the conflict.

	     We do the combining test at the CLOBBER so that the
	     destination register won't have had a quantity number
	     assigned, since that would prevent combining.  */

	  if (GET_CODE (PATTERN (insn)) == CLOBBER
	      && (r0 = XEXP (PATTERN (insn), 0),
		  GET_CODE (r0) == REG)
	      && (link = find_reg_note (insn, REG_LIBCALL, NULL_RTX)) != 0
	      && GET_CODE (XEXP (link, 0)) == INSN
	      && (set = single_set (XEXP (link, 0))) != 0
	      && SET_DEST (set) == r0 && SET_SRC (set) == r0
	      && (note = find_reg_note (XEXP (link, 0), REG_EQUAL,
					NULL_RTX)) != 0)
	    {
	      if (r1 = XEXP (note, 0), GET_CODE (r1) == REG
		  /* Check that we have such a sequence.  */
		  && no_conflict_p (insn, r0, r1))
		win = combine_regs (r1, r0, 1, insn_number, insn, 1);
	      else if (GET_RTX_FORMAT (GET_CODE (XEXP (note, 0)))[0] == 'e'
		       && (r1 = XEXP (XEXP (note, 0), 0),
			   GET_CODE (r1) == REG || GET_CODE (r1) == SUBREG)
		       && no_conflict_p (insn, r0, r1))
		win = combine_regs (r1, r0, 0, insn_number, insn, 1);

	      /* Here we care if the operation to be computed is
		 commutative.  */
	      else if ((GET_CODE (XEXP (note, 0)) == EQ
			|| GET_CODE (XEXP (note, 0)) == NE
			|| GET_RTX_CLASS (GET_CODE (XEXP (note, 0))) == 'c')
		       && (r1 = XEXP (XEXP (note, 0), 1),
			   (GET_CODE (r1) == REG || GET_CODE (r1) == SUBREG))
		       && no_conflict_p (insn, r0, r1))
		win = combine_regs (r1, r0, 0, insn_number, insn, 1);

	      /* If we did combine something, show the register number
		 in question so that we know to ignore its death.  */
	      if (win)
		no_conflict_combined_regno = REGNO (r1);
	    }

	  /* If registers were just tied, set COMBINED_REGNO
	     to the number of the register used in this insn
	     that was tied to the register set in this insn.
	     This register's qty should not be "killed".  */

	  if (win)
	    {
	      while (GET_CODE (r1) == SUBREG)
		r1 = SUBREG_REG (r1);
	      combined_regno = REGNO (r1);
	    }

	  /* Mark the death of everything that dies in this instruction,
	     except for anything that was just combined.  */

	  for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
	    if (REG_NOTE_KIND (link) == REG_DEAD
		&& GET_CODE (XEXP (link, 0)) == REG
		&& combined_regno != REGNO (XEXP (link, 0))
		&& (no_conflict_combined_regno != REGNO (XEXP (link, 0))
		    || ! find_reg_note (insn, REG_NO_CONFLICT, XEXP (link, 0))))
	      wipe_dead_reg (XEXP (link, 0), 0);

	  /* Allocate qty numbers for all registers local to this block
	     that are born (set) in this instruction.
	     A pseudo that already has a qty is not changed.  */

	  note_stores (PATTERN (insn), reg_is_set);

	  /* If anything is set in this insn and then unused, mark it as dying
	     after this insn, so it will conflict with our outputs.  This
	     can't match with something that combined, and it doesn't matter
	     if it did.  Do this after the calls to reg_is_set since these
	     die after, not during, the current insn.  */

	  for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
	    if (REG_NOTE_KIND (link) == REG_UNUSED
		&& GET_CODE (XEXP (link, 0)) == REG)
	      wipe_dead_reg (XEXP (link, 0), 1);

#ifndef SMALL_REGISTER_CLASSES
	  /* Allocate quantities for any SCRATCH operands of this insn.  We
	     don't do this for machines with small register classes because
	     those machines can use registers explicitly mentioned in the
	     RTL as spill registers and our usage of hard registers
	     explicitly for SCRATCH operands will conflict.  On those machines,
	     reload will allocate the SCRATCH.  */

	  if (insn_code_number >= 0)
	    for (i = 0; i < insn_n_operands[insn_code_number]; i++)
	      if (GET_CODE (recog_operand[i]) == SCRATCH)
		alloc_qty_for_scratch (recog_operand[i], i, insn,
				       insn_code_number, insn_number);
#endif

	  /* If this is an insn that has a REG_RETVAL note pointing at a 
	     CLOBBER insn, we have reached the end of a REG_NO_CONFLICT
	     block, so clear any register number that combined within it.  */
	  if ((note = find_reg_note (insn, REG_RETVAL, NULL_RTX)) != 0
	      && GET_CODE (XEXP (note, 0)) == INSN
	      && GET_CODE (PATTERN (XEXP (note, 0))) == CLOBBER)
	    no_conflict_combined_regno = -1;
	}

      /* Set the registers live after INSN_NUMBER.  Note that we never
	 record the registers live before the block's first insn, since no
	 pseudos we care about are live before that insn.  */

      IOR_HARD_REG_SET (regs_live_at[2 * insn_number], regs_live);
      IOR_HARD_REG_SET (regs_live_at[2 * insn_number + 1], regs_live);

      if (insn == basic_block_end[b])
	break;

      insn = NEXT_INSN (insn);
    }

  /* Now every register that is local to this basic block
     should have been given a quantity, or else -1 meaning ignore it.
     Every quantity should have a known birth and death.  

     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.  */

  qty_order = (short *) alloca (next_qty * sizeof (short));
  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 (short), qty_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_has_sugg[q] || qty_phys_has_copy_sugg[q])
	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;
    }

  /* 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])
	  {
	    PUT_CODE (qty_scratch_rtx[q], REG);
	    REGNO (qty_scratch_rtx[q]) = qty_phys_reg[q];

	    for (i = HARD_REGNO_NREGS (qty_phys_reg[q],
				       GET_MODE (qty_scratch_rtx[q])) - 1;
		 i >= 0; i--)
	      regs_ever_live[qty_phys_reg[q] + i] = 1;

	    /* Must clear the USED field, because it will have been set by
	       copy_rtx_if_shared, but the leaf_register code expects that
	       it is zero in all REG rtx.  copy_rtx_if_shared does not set the
	       used bit for REGs, but does for SCRATCHes.  */
	    qty_scratch_rtx[q]->used = 0;
	  }
      }
}

/* 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!  */

static int
qty_compare (q1, q2)
     int q1, q2;
{
  /* 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.  */
  register int pri1
    = (((double) (floor_log2 (qty_n_refs[q1]) * qty_n_refs[q1])
	/ ((qty_death[q1] - qty_birth[q1]) * qty_size[q1]))
       * 10000);
  register int pri2
    = (((double) (floor_log2 (qty_n_refs[q2]) * qty_n_refs[q2])
	/ ((qty_death[q2] - qty_birth[q2]) * qty_size[q2]))
       * 10000);
  return pri2 - pri1;
}

static int
qty_compare_1 (q1, q2)
     short *q1, *q2;
{
  register int tem;

  /* 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.  */
  register int pri1
    = (((double) (floor_log2 (qty_n_refs[*q1]) * qty_n_refs[*q1])
	/ ((qty_death[*q1] - qty_birth[*q1]) * qty_size[*q1]))
       * 10000);
  register int pri2
    = (((double) (floor_log2 (qty_n_refs[*q2]) * qty_n_refs[*q2])
	/ ((qty_death[*q2] - qty_birth[*q2]) * qty_size[*q2]))
       * 10000);

  tem = pri2 - pri1;
  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;
}

/* 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)
    {