local-alloc.c

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

  /* Leaf functions and non-leaf functions have different needs.
     If defined, let the machine say what kind of ordering we
     should use.  */
#ifdef ORDER_REGS_FOR_LOCAL_ALLOC
  ORDER_REGS_FOR_LOCAL_ALLOC;
#endif

  /* Promote REG_EQUAL notes to REG_EQUIV notes and adjust status of affected
     registers.  */
  update_equiv_regs ();

  /* This sets the maximum number of quantities we can have.  Quantity
     numbers start at zero and we can have one for each pseudo plus the
     number of SCRATCHes in the largest block, in the worst case.  */
  max_qty = (max_regno - FIRST_PSEUDO_REGISTER) + max_scratch;

  /* Allocate vectors of temporary data.
     See the declarations of these variables, above,
     for what they mean.  */

  /* There can be up to MAX_SCRATCH * N_BASIC_BLOCKS SCRATCHes to allocate.
     Instead of allocating this much memory from now until the end of
     reload, only allocate space for MAX_QTY SCRATCHes.  If there are more
     reload will allocate them.  */

  scratch_list_length = max_qty;
  scratch_list = (rtx *) xmalloc (scratch_list_length * sizeof (rtx));
  bzero ((char *) scratch_list, scratch_list_length * sizeof (rtx));
  scratch_block = (int *) xmalloc (scratch_list_length * sizeof (int));
  bzero ((char *) scratch_block, scratch_list_length * sizeof (int));
  scratch_index = 0;

  qty_phys_reg = (short *) alloca (max_qty * sizeof (short));
  qty_phys_copy_sugg
    = (HARD_REG_SET *) alloca (max_qty * sizeof (HARD_REG_SET));
  qty_phys_num_copy_sugg = (short *) alloca (max_qty * sizeof (short));
  qty_phys_sugg = (HARD_REG_SET *) alloca (max_qty * sizeof (HARD_REG_SET));
  qty_phys_num_sugg = (short *) alloca (max_qty * sizeof (short));
  qty_birth = (int *) alloca (max_qty * sizeof (int));
  qty_death = (int *) alloca (max_qty * sizeof (int));
  qty_scratch_rtx = (rtx *) alloca (max_qty * sizeof (rtx));
  qty_first_reg = (int *) alloca (max_qty * sizeof (int));
  qty_size = (int *) alloca (max_qty * sizeof (int));
  qty_mode
    = (enum machine_mode *) alloca (max_qty * sizeof (enum machine_mode));
  qty_n_calls_crossed = (int *) alloca (max_qty * sizeof (int));
  qty_min_class
    = (enum reg_class *) alloca (max_qty * sizeof (enum reg_class));
  qty_alternate_class
    = (enum reg_class *) alloca (max_qty * sizeof (enum reg_class));
  qty_n_refs = (int *) alloca (max_qty * sizeof (int));
  qty_changes_size = (char *) alloca (max_qty * sizeof (char));

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

  /* Allocate the reg_renumber array */
  allocate_reg_info (max_regno, FALSE, TRUE);

  /* 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
     a few entries, 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
	      || ! CLASS_LIKELY_SPILLED_P (reg_preferred_class (i))))
	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_num_copy_sugg[i] = 0;
	      CLEAR_HARD_REG_SET (qty_phys_sugg[i]);
	      qty_phys_num_sugg[i] = 0;
	    }
	}
      else
	{
#define CLEAR(vector)  \
	  bzero ((char *) (vector), (sizeof (*(vector))) * next_qty);

	  CLEAR (qty_scratch_rtx);
	  CLEAR (qty_phys_copy_sugg);
	  CLEAR (qty_phys_num_copy_sugg);
	  CLEAR (qty_phys_sugg);
	  CLEAR (qty_phys_num_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 uses any registers for which reg_equiv_replace is true.  */

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

  switch (code)
    {
    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 REG:
      return reg_equiv_replace[REGNO (x)];
    }

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

  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 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 REG:
      return (reg_equiv_replacement[REGNO (x)]
	      && memref_referenced_p (memref,
				      reg_equiv_replacement[REGNO (x)]));

    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));
      
    default:
      break;
    }

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

  /* We don't want to mess with hard regs if register classes are small. */
  if (sregno == dregno
      || (SMALL_REGISTER_CLASSES
	  && (sregno < FIRST_PSEUDO_REGISTER
	      || dregno < FIRST_PSEUDO_REGISTER))
      /* 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;