local-alloc.c

早期freebsd实现

  reg_qty = (int *) alloca (max_regno * sizeof (int));
  reg_offset = (char *) alloca (max_regno * sizeof (char));
  reg_next_in_qty = (short *) alloca (max_regno * sizeof (short));

  reg_renumber = (short *) oballoc (max_regno * sizeof (short));
  for (i = 0; i < max_regno; i++)
    reg_renumber[i] = -1;

  /* Determine which pseudo-registers can be allocated by local-alloc.
     In general, these are the registers used only in a single block and
     which only die once.  However, if a register's preferred class has only
     one entry, don't allocate this register here unless it is preferred
     or nothing since retry_global_alloc won't be able to move it to
     GENERAL_REGS if a reload register of this class is needed.

     We need not be concerned with which block actually uses the register
     since we will never see it outside that block.  */

  for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
    {
      if (reg_basic_block[i] >= 0 && reg_n_deaths[i] == 1
	  && (reg_alternate_class (i) == NO_REGS
	      || reg_class_size[(int) reg_preferred_class (i)] > 1))
	reg_qty[i] = -2;
      else
	reg_qty[i] = -1;
    }

  /* Force loop below to initialize entire quantity array.  */
  next_qty = max_qty;

  /* Allocate each block's local registers, block by block.  */

  for (b = 0; b < n_basic_blocks; b++)
    {
      /* NEXT_QTY indicates which elements of the `qty_...'
	 vectors might need to be initialized because they were used
	 for the previous block; it is set to the entire array before
	 block 0.  Initialize those, with explicit loop if there are few,
	 else with bzero and bcopy.  Do not initialize vectors that are
	 explicit set by `alloc_qty'.  */

      if (next_qty < 6)
	{
	  for (i = 0; i < next_qty; i++)
	    {
	      qty_scratch_rtx[i] = 0;
	      CLEAR_HARD_REG_SET (qty_phys_copy_sugg[i]);
	      qty_phys_has_copy_sugg[i] = 0;
	      CLEAR_HARD_REG_SET (qty_phys_sugg[i]);
	      qty_phys_has_sugg[i] = 0;
	    }
	}
      else
	{
#define CLEAR(vector)  \
	  bzero ((vector), (sizeof (*(vector))) * next_qty);

	  CLEAR (qty_scratch_rtx);
	  CLEAR (qty_phys_copy_sugg);
	  CLEAR (qty_phys_has_copy_sugg);
	  CLEAR (qty_phys_sugg);
	  CLEAR (qty_phys_has_sugg);
	}

      next_qty = 0;

      block_alloc (b);
#ifdef USE_C_ALLOCA
      alloca (0);
#endif
    }
}

/* Depth of loops we are in while in update_equiv_regs.  */
static int loop_depth;

/* Used for communication between the following two functions: contains
   a MEM that we wish to ensure remains unchanged.  */
static rtx equiv_mem;

/* Set nonzero if EQUIV_MEM is modified.  */
static int equiv_mem_modified;

/* If EQUIV_MEM is modified by modifying DEST, indicate that it is modified.
   Called via note_stores.  */

static void
validate_equiv_mem_from_store (dest, set)
     rtx dest;
     rtx set;
{
  if ((GET_CODE (dest) == REG
       && reg_overlap_mentioned_p (dest, equiv_mem))
      || (GET_CODE (dest) == MEM
	  && true_dependence (dest, equiv_mem)))
    equiv_mem_modified = 1;
}

/* Verify that no store between START and the death of REG invalidates
   MEMREF.  MEMREF is invalidated by modifying a register used in MEMREF,
   by storing into an overlapping memory location, or with a non-const
   CALL_INSN.

   Return 1 if MEMREF remains valid.  */

static int
validate_equiv_mem (start, reg, memref)
     rtx start;
     rtx reg;
     rtx memref;
{
  rtx insn;
  rtx note;

  equiv_mem = memref;
  equiv_mem_modified = 0;

  /* If the memory reference has side effects or is volatile, it isn't a
     valid equivalence.  */
  if (side_effects_p (memref))
    return 0;

  for (insn = start; insn && ! equiv_mem_modified; insn = NEXT_INSN (insn))
    {
      if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
	continue;

      if (find_reg_note (insn, REG_DEAD, reg))
	return 1;

      if (GET_CODE (insn) == CALL_INSN && ! RTX_UNCHANGING_P (memref)
	  && ! CONST_CALL_P (insn))
	return 0;

      note_stores (PATTERN (insn), validate_equiv_mem_from_store);

      /* If a register mentioned in MEMREF is modified via an
	 auto-increment, we lose the equivalence.  Do the same if one
	 dies; although we could extend the life, it doesn't seem worth
	 the trouble.  */

      for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
	if ((REG_NOTE_KIND (note) == REG_INC
	     || REG_NOTE_KIND (note) == REG_DEAD)
	    && GET_CODE (XEXP (note, 0)) == REG
	    && reg_overlap_mentioned_p (XEXP (note, 0), memref))
	  return 0;
    }

  return 0;
}

/* TRUE if X references a memory location that would be affected by a store
   to MEMREF.  */

static int
memref_referenced_p (memref, x)
     rtx x;
     rtx memref;
{
  int i, j;
  char *fmt;
  enum rtx_code code = GET_CODE (x);

  switch (code)
    {
    case REG:
    case CONST_INT:
    case CONST:
    case LABEL_REF:
    case SYMBOL_REF:
    case CONST_DOUBLE:
    case PC:
    case CC0:
    case HIGH:
    case LO_SUM:
      return 0;

    case MEM:
      if (true_dependence (memref, x))
	return 1;
      break;

    case SET:
      /* If we are setting a MEM, it doesn't count (its address does), but any
	 other SET_DEST that has a MEM in it is referencing the MEM.  */
      if (GET_CODE (SET_DEST (x)) == MEM)
	{
	  if (memref_referenced_p (memref, XEXP (SET_DEST (x), 0)))
	    return 1;
	}
      else if (memref_referenced_p (memref, SET_DEST (x)))
	return 1;

      return memref_referenced_p (memref, SET_SRC (x));
    }

  fmt = GET_RTX_FORMAT (code);
  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
    switch (fmt[i])
      {
      case 'e':
	if (memref_referenced_p (memref, XEXP (x, i)))
	  return 1;
	break;
      case 'E':
	for (j = XVECLEN (x, i) - 1; j >= 0; j--)
	  if (memref_referenced_p (memref, XVECEXP (x, i, j)))
	    return 1;
	break;
      }

  return 0;
}

/* TRUE if some insn in the range (START, END] references a memory location
   that would be affected by a store to MEMREF.  */

static int
memref_used_between_p (memref, start, end)
     rtx memref;
     rtx start;
     rtx end;
{
  rtx insn;

  for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
       insn = NEXT_INSN (insn))
    if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
	&& memref_referenced_p (memref, PATTERN (insn)))
      return 1;

  return 0;
}

/* INSN is a copy from SRC to DEST, both registers, and SRC does not die
   in INSN.

   Search forward to see if SRC dies before either it or DEST is modified,
   but don't scan past the end of a basic block.  If so, we can replace SRC
   with DEST and let SRC die in INSN. 

   This will reduce the number of registers live in that range and may enable
   DEST to be tied to SRC, thus often saving one register in addition to a
   register-register copy.  */

static void
optimize_reg_copy_1 (insn, dest, src)
     rtx insn;
     rtx dest;
     rtx src;
{
  rtx p, q;
  rtx note;
  rtx dest_death = 0;
  int sregno = REGNO (src);
  int dregno = REGNO (dest);

  if (sregno == dregno
#ifdef SMALL_REGISTER_CLASSES
      /* We don't want to mess with hard regs if register classes are small. */
      || sregno < FIRST_PSEUDO_REGISTER || dregno < FIRST_PSEUDO_REGISTER
#endif
      /* We don't see all updates to SP if they are in an auto-inc memory
	 reference, so we must disallow this optimization on them.  */
      || sregno == STACK_POINTER_REGNUM || dregno == STACK_POINTER_REGNUM)
    return;

  for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
    {
      if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN
	  || (GET_CODE (p) == NOTE
	      && (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG
		  || NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)))
	break;

      if (GET_RTX_CLASS (GET_CODE (p)) != 'i')
	continue;

      if (reg_set_p (src, p) || reg_set_p (dest, p)
	  /* Don't change a USE of a register.  */
	  || (GET_CODE (PATTERN (p)) == USE
	      && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
	break;

      /* See if all of SRC dies in P.  This test is slightly more
	 conservative than it needs to be. */
      if ((note = find_regno_note (p, REG_DEAD, sregno)) != 0
	  && GET_MODE (XEXP (note, 0)) == GET_MODE (src))
	{
	  int failed = 0;
	  int length = 0;
	  int d_length = 0;
	  int n_calls = 0;
	  int d_n_calls = 0;

	  /* If P is a CALL_INSN, SRC crosses one more call, since it
	     used to die there.  */

	  if (GET_CODE (p) == CALL_INSN)
	    n_calls++;

	  /* We can do the optimization.  Scan forward from INSN again,
	     replacing regs as we go.  Set FAILED if a replacement can't
	     be done.  In that case, we can't move the death note for SRC.
	     This should be rare.  */

	  /* Set to stop at next insn.  */
	  for (q = next_real_insn (insn);
	       q != next_real_insn (p);
	       q = next_real_insn (q))
	    {
	      if (reg_overlap_mentioned_p (src, PATTERN (q)))
		{
		  /* If SRC is a hard register, we might miss some
		     overlapping registers with validate_replace_rtx,
		     so we would have to undo it.  We can't if DEST is
		     present in the insn, so fail in that combination
		     of cases.  */
		  if (sregno < FIRST_PSEUDO_REGISTER
		      && reg_mentioned_p (dest, PATTERN (q)))
		    failed = 1;

		  /* Replace all uses and make sure that the register
		     isn't still present.  */
		  else if (validate_replace_rtx (src, dest, q)
			   && (sregno >= FIRST_PSEUDO_REGISTER
			       || ! reg_overlap_mentioned_p (src,
							     PATTERN (q))))
		    {
		      /* We assume that a register is used exactly once per
			 insn in the updates below.  If this is not correct,
			 no great harm is done.  */
		      if (sregno >= FIRST_PSEUDO_REGISTER)
			reg_n_refs[sregno] -= loop_depth;
		      if (dregno >= FIRST_PSEUDO_REGISTER)
			reg_n_refs[dregno] += loop_depth;
		    }
		  else
		    {
		      validate_replace_rtx (dest, src, q);
		      failed = 1;
		    }
		}

	      /* Count the insns and CALL_INSNs passed.  If we passed the
		 death note of DEST, show increased live length.  */
	      length++;
	      if (dest_death)
		d_length++;

	      if (GET_CODE (q) == CALL_INSN)
		{
		  n_calls++;
		  if (dest_death)
		    d_n_calls++;
		}

	      /* If DEST dies here, remove the death note and save it for
		 later.  Make sure ALL of DEST dies here; again, this is
		 overly conservative.  */
	      if (dest_death == 0
		  && (dest_death = find_regno_note (q, REG_DEAD, dregno)) != 0
		  && GET_MODE (XEXP (dest_death, 0)) == GET_MODE (dest))
		remove_note (q, dest_death);
	    }

	  if (! failed)
	    {
	      if (sregno >= FIRST_PSEUDO_REGISTER)
		{
		  reg_live_length[sregno] -= length;
		  reg_n_calls_crossed[sregno] -= n_calls;
		}

	      if (dregno >= FIRST_PSEUDO_REGISTER)
		{
		  reg_live_length[dregno] += d_length;
		  reg_n_calls_crossed[dregno] += d_n_calls;
		}

	      /* Move death note of SRC from P to INSN.  */
	      remove_note (p, note);
	      XEXP (note, 1) = REG_NOTES (insn);
	      REG_NOTES (insn) = note;
	    }

	  /* Put death note of DEST on P if we saw it die.  */
	  if (dest_death)
	    {
	      XEXP (dest_death, 1) = REG_NOTES (p);
	      REG_NOTES (p) = dest_death;
	    }

	  return;
	}

      /* If SRC is a hard register which is set or killed in some other
	 way, we can't do this optimization.  */