local-alloc.c

早期freebsd实现

      /* 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)
	    {
	      SET_HARD_REG_BIT (qty_phys_copy_sugg[reg_qty[sreg]], ureg);
	      qty_phys_has_copy_sugg[reg_qty[sreg]] = 1;
	    }
	  else
	    {
	      SET_HARD_REG_BIT (qty_phys_sugg[reg_qty[sreg]], ureg);
	      qty_phys_has_sugg[reg_qty[sreg]] = 1;
	    }
	}
      return 0;
    }

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

  if (sreg < FIRST_PSEUDO_REGISTER)
    {
      if (may_save_copy)
	{
	  SET_HARD_REG_BIT (qty_phys_copy_sugg[reg_qty[ureg]], sreg);
	  qty_phys_has_copy_sugg[reg_qty[ureg]] = 1;
	}
      else
	{
	  SET_HARD_REG_BIT (qty_phys_sugg[reg_qty[ureg]], sreg);
	  qty_phys_has_sugg[reg_qty[ureg]] = 1;
	}
      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 CLASS.
   True if REG's reg class either contains or is contained in CLASS.  */

static int
reg_meets_class_p (reg, class)
     int reg;
     enum reg_class class;
{
  register enum reg_class rclass = reg_preferred_class (reg);
  return (reg_class_subset_p (rclass, class)
	  || reg_class_subset_p (class, rclass));
}

/* Return 1 if the two specified classes have registers in common.
   If CALL_SAVED, then consider only call-saved registers.  */

static int
reg_classes_overlap_p (c1, c2, call_saved)
     register enum reg_class c1;
     register enum reg_class c2;
     int call_saved;
{
  HARD_REG_SET c;
  int i;

  COPY_HARD_REG_SET (c, reg_class_contents[(int) c1]);
  AND_HARD_REG_SET (c, reg_class_contents[(int) c2]);

  for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
    if (TEST_HARD_REG_BIT (c, i)
	&& (! call_saved || ! call_used_regs[i]))
      return 1;

  return 0;
}

/* Update the class of QTY assuming that REG is being tied to it.  */

static void
update_qty_class (qty, reg)
     int qty;
     int reg;
{
  enum reg_class rclass = reg_preferred_class (reg);
  if (reg_class_subset_p (rclass, qty_min_class[qty]))
    qty_min_class[qty] = rclass;

  rclass = reg_alternate_class (reg);
  if (reg_class_subset_p (rclass, qty_alternate_class[qty]))
    qty_alternate_class[qty] = rclass;
}

/* Handle something which alters the value of an rtx REG.

   REG is whatever is set or clobbered.  SETTER is the rtx that
   is modifying the register.

   If it is not really a register, we do nothing.
   The file-global variables `this_insn' and `this_insn_number'
   carry info from `block_alloc'.  */

static void
reg_is_set (reg, setter)
     rtx reg;
     rtx setter;
{
  /* Note that note_stores will only pass us a SUBREG if it is a SUBREG of
     a hard register.  These may actually not exist any more.  */

  if (GET_CODE (reg) != SUBREG
      && GET_CODE (reg) != REG)
    return;

  /* Mark this register as being born.  If it is used in a CLOBBER, mark
     it as being born halfway between the previous insn and this insn so that
     it conflicts with our inputs but not the outputs of the previous insn.  */

  reg_is_born (reg, 2 * this_insn_number - (GET_CODE (setter) == CLOBBER));
}

/* Handle beginning of the life of register REG.
   BIRTH is the index at which this is happening.  */

static void
reg_is_born (reg, birth)
     rtx reg;
     int birth;
{
  register int regno;
     
  if (GET_CODE (reg) == SUBREG)
    regno = REGNO (SUBREG_REG (reg)) + SUBREG_WORD (reg);
  else
    regno = REGNO (reg);

  if (regno < FIRST_PSEUDO_REGISTER)
    {
      mark_life (regno, GET_MODE (reg), 1);

      /* If the register was to have been born earlier that the present
	 insn, mark it as live where it is actually born.  */
      if (birth < 2 * this_insn_number)
	post_mark_life (regno, GET_MODE (reg), 1, birth, 2 * this_insn_number);
    }
  else
    {
      if (reg_qty[regno] == -2)
	alloc_qty (regno, GET_MODE (reg), PSEUDO_REGNO_SIZE (regno), birth);

      /* If this register has a quantity number, show that it isn't dead.  */
      if (reg_qty[regno] >= 0)
	qty_death[reg_qty[regno]] = -1;
    }
}

/* Record the death of REG in the current insn.  If OUTPUT_P is non-zero,
   REG is an output that is dying (i.e., it is never used), otherwise it
   is an input (the normal case).
   If OUTPUT_P is 1, then we extend the life past the end of this insn.  */

static void
wipe_dead_reg (reg, output_p)
     register rtx reg;
     int output_p;
{
  register int regno = REGNO (reg);

  /* If this insn has multiple results,
     and the dead reg is used in one of the results,
     extend its life to after this insn,
     so it won't get allocated together with any other result of this insn.  */
  if (GET_CODE (PATTERN (this_insn)) == PARALLEL
      && !single_set (this_insn))
    {
      int i;
      for (i = XVECLEN (PATTERN (this_insn), 0) - 1; i >= 0; i--)
	{
	  rtx set = XVECEXP (PATTERN (this_insn), 0, i);
	  if (GET_CODE (set) == SET
	      && GET_CODE (SET_DEST (set)) != REG
	      && !rtx_equal_p (reg, SET_DEST (set))
	      && reg_overlap_mentioned_p (reg, SET_DEST (set)))
	    output_p = 1;
	}
    }

  if (regno < FIRST_PSEUDO_REGISTER)
    {
      mark_life (regno, GET_MODE (reg), 0);

      /* If a hard register is dying as an output, mark it as in use at
	 the beginning of this insn (the above statement would cause this
	 not to happen).  */
      if (output_p)
	post_mark_life (regno, GET_MODE (reg), 1,
			2 * this_insn_number, 2 * this_insn_number+ 1);
    }

  else if (reg_qty[regno] >= 0)
    qty_death[reg_qty[regno]] = 2 * this_insn_number + output_p;
}

/* Find a block of SIZE words of hard regs in reg_class CLASS
   that can hold something of machine-mode MODE
     (but actually we test only the first of the block for holding MODE)
   and still free between insn BORN_INDEX and insn DEAD_INDEX,
   and return the number of the first of them.
   Return -1 if such a block cannot be found. 
   If QTY crosses calls, insist on a register preserved by calls,
   unless ACCEPT_CALL_CLOBBERED is nonzero.

   If JUST_TRY_SUGGESTED is non-zero, only try to see if the suggested
   register is available.  If not, return -1.  */

static int
find_free_reg (class, mode, qty, accept_call_clobbered, just_try_suggested,
	       born_index, dead_index)
     enum reg_class class;
     enum machine_mode mode;
     int accept_call_clobbered;
     int just_try_suggested;
     int qty;
     int born_index, dead_index;
{
  register int i, ins;
#ifdef HARD_REG_SET
  register		/* Declare it register if it's a scalar.  */
#endif
    HARD_REG_SET used, first_used;
#ifdef ELIMINABLE_REGS
  static struct {int from, to; } eliminables[] = ELIMINABLE_REGS;
#endif

  /* Validate our parameters.  */
  if (born_index < 0 || born_index > dead_index)
    abort ();

  /* Don't let a pseudo live in a reg across a function call
     if we might get a nonlocal goto.  */
  if (current_function_has_nonlocal_label
      && qty_n_calls_crossed[qty] > 0)
    return -1;

  if (accept_call_clobbered)
    COPY_HARD_REG_SET (used, call_fixed_reg_set);
  else if (qty_n_calls_crossed[qty] == 0)
    COPY_HARD_REG_SET (used, fixed_reg_set);
  else
    COPY_HARD_REG_SET (used, call_used_reg_set);

  for (ins = born_index; ins < dead_index; ins++)
    IOR_HARD_REG_SET (used, regs_live_at[ins]);

  IOR_COMPL_HARD_REG_SET (used, reg_class_contents[(int) class]);

  /* Don't use the frame pointer reg in local-alloc even if
     we may omit the frame pointer, because if we do that and then we
     need a frame pointer, reload won't know how to move the pseudo
     to another hard reg.  It can move only regs made by global-alloc.

     This is true of any register that can be eliminated.  */
#ifdef ELIMINABLE_REGS
  for (i = 0; i < sizeof eliminables / sizeof eliminables[0]; i++)
    SET_HARD_REG_BIT (used, eliminables[i].from);
#else
  SET_HARD_REG_BIT (used, FRAME_POINTER_REGNUM);
#endif

  /* Normally, the registers that can be used for the first register in
     a multi-register quantity are the same as those that can be used for
     subsequent registers.  However, if just trying suggested registers,
     restrict our consideration to them.  If there are copy-suggested
     register, try them.  Otherwise, try the arithmetic-suggested
     registers.  */
  COPY_HARD_REG_SET (first_used, used);

  if (just_try_suggested)
    {
      if (qty_phys_has_copy_sugg[qty])
	IOR_COMPL_HARD_REG_SET (first_used, qty_phys_copy_sugg[qty]);
      else
	IOR_COMPL_HARD_REG_SET (first_used, qty_phys_sugg[qty]);
    }

  /* If all registers are excluded, we can't do anything.  */
  GO_IF_HARD_REG_SUBSET (reg_class_contents[(int) ALL_REGS], first_used, fail);

  /* If at least one would be suitable, test each hard reg.  */

  for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
    {
#ifdef REG_ALLOC_ORDER
      int regno = reg_alloc_order[i];
#else
      int regno = i;
#endif
      if (! TEST_HARD_REG_BIT (first_used, regno)
	  && HARD_REGNO_MODE_OK (regno, mode))
	{
	  register int j;
	  register int size1 = HARD_REGNO_NREGS (regno, mode);
	  for (j = 1; j < size1 && ! TEST_HARD_REG_BIT (used, regno + j); j++);
	  if (j == size1)
	    {
	      /* Mark that this register is in use between its birth and death
		 insns.  */
	      post_mark_life (regno, mode, 1, born_index, dead_index);
	      return regno;
	    }
#ifndef REG_ALLOC_ORDER
	  i += j;		/* Skip starting points we know will lose */
#endif
	}
    }

 fail:

  /* If we are just trying suggested register, we have just tried copy-
     suggested registers, and there are arithmetic-suggested registers,
     try them.  */
  
  /* If it would be profitable to allocate a call-clobbered register
     and save and restore it around calls, do that.  */
  if (just_try_suggested && qty_phys_has_copy_sugg[qty]
      && qty_phys_has_sugg[qty])
    {
      /* Don't try the copy-suggested regs again.  */
      qty_phys_has_copy_sugg[qty] = 0;
      return find_free_reg (class, mode, qty, accept_call_clobbered, 1,
			    born_index, dead_index);
    }

  if (! accept_call_clobbered
      && flag_caller_saves
      && ! just_try_suggested
      && qty_n_calls_crossed[qty] != 0
      && CALLER_SAVE_PROFITABLE (qty_n_refs[qty], qty_n_calls_crossed[qty]))
    {
      i = find_free_reg (class, mode, qty, 1, 0, born_index, dead_index);
      if (i >= 0)
	caller_save_needed = 1;
      return i;
    }
  return -1;
}

/* Mark that REGNO with machine-mode MODE is live starting from the current
   insn (if LIFE is non-zero) or dead starting at the current insn (if LIFE
   is zero).  */

static void
mark_life (regno, mode, life)