local-alloc.c

gcc库的原代码,对编程有很大帮助.

	  this_insn_number = insn_number;
	  this_insn = insn;

	  if (insn_code_number >= 0)
	    insn_extract (insn);
	  which_alternative = -1;

	  /* Is this insn suitable for tying two registers?
	     If so, try doing that.
	     Suitable insns are those with at least two operands and where
	     operand 0 is an output that is a register that is not
	     earlyclobber.

	     We can tie operand 0 with some operand that dies in this insn.
	     First look for operands that are required to be in the same
	     register as operand 0.  If we find such, only try tying that
	     operand or one that can be put into that operand if the
	     operation is commutative.  If we don't find an operand
	     that is required to be in the same register as operand 0,
	     we can tie with any operand.

	     Subregs in place of regs are also ok.

	     If tying is done, WIN is set nonzero.  */

	  if (insn_code_number >= 0
#ifdef REGISTER_CONSTRAINTS
	      && insn_n_operands[insn_code_number] > 1
	      && insn_operand_constraint[insn_code_number][0][0] == '='
	      && insn_operand_constraint[insn_code_number][0][1] != '&'
#else
	      && GET_CODE (PATTERN (insn)) == SET
	      && rtx_equal_p (SET_DEST (PATTERN (insn)), recog_operand[0])
#endif
	      )
	    {
#ifdef REGISTER_CONSTRAINTS
	      /* If non-negative, is an operand that must match operand 0.  */
	      int must_match_0 = -1;
	      /* Counts number of alternatives that require a match with
		 operand 0.  */
	      int n_matching_alts = 0;

	      for (i = 1; i < insn_n_operands[insn_code_number]; i++)
		{
		  char *p = insn_operand_constraint[insn_code_number][i];
		  int this_match = (requires_inout (p));

		  n_matching_alts += this_match;
		  if (this_match == insn_n_alternatives[insn_code_number])
		    must_match_0 = i;
		}
#endif

	      r0 = recog_operand[0];
	      for (i = 1; i < insn_n_operands[insn_code_number]; i++)
		{
#ifdef REGISTER_CONSTRAINTS
		  /* Skip this operand if we found an operand that
		     must match operand 0 and this operand isn't it
		     and can't be made to be it by commutativity.  */

		  if (must_match_0 >= 0 && i != must_match_0
		      && ! (i == must_match_0 + 1
			    && insn_operand_constraint[insn_code_number][i-1][0] == '%')
		      && ! (i == must_match_0 - 1
			    && insn_operand_constraint[insn_code_number][i][0] == '%'))
		    continue;

		  /* Likewise if each alternative has some operand that
		     must match operand zero.  In that case, skip any 
		     operand that doesn't list operand 0 since we know that
		     the operand always conflicts with operand 0.  We
		     ignore commutatity in this case to keep things simple.  */
		  if (n_matching_alts == insn_n_alternatives[insn_code_number]
		      && (0 == requires_inout
			  (insn_operand_constraint[insn_code_number][i])))
		    continue;
#endif

		  r1 = recog_operand[i];

		  /* If the operand is an address, find a register in it.
		     There may be more than one register, but we only try one
		     of them.  */
		  if (
#ifdef REGISTER_CONSTRAINTS
		      insn_operand_constraint[insn_code_number][i][0] == 'p'
#else
		      insn_operand_address_p[insn_code_number][i]
#endif
		      )
		    while (GET_CODE (r1) == PLUS || GET_CODE (r1) == MULT)
		      r1 = XEXP (r1, 0);

		  if (GET_CODE (r0) == REG || GET_CODE (r0) == SUBREG)
		    {
		      /* We have two priorities for hard register preferences.
			 If we have a move insn or an insn whose first input
			 can only be in the same register as the output, give
			 priority to an equivalence found from that insn.  */
		      int may_save_copy
			= ((SET_DEST (body) == r0 && SET_SRC (body) == r1)
#ifdef REGISTER_CONSTRAINTS
			   || (r1 == recog_operand[i] && must_match_0 >= 0)
#endif
			   );
		      
		      if (GET_CODE (r1) == REG || GET_CODE (r1) == SUBREG)
			win = combine_regs (r1, r0, may_save_copy,
					    insn_number, insn, 0);
		    }
		  if (win)
		    break;
		}
	    }

	  /* 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
	      && XEXP (link, 0) != 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);

	  /* Allocate quantities for any SCRATCH operands of this insn.  */

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

	  /* 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 the
     number of suggested registers they need so we allocate those with
     the most restrictive needs first.  */

  qty_order = (int *) alloca (next_qty * sizeof (int));
  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_sugg_compare (0, 1) > 0)
	EXCHANGE (0, 1);
      if (qty_sugg_compare (1, 2) > 0)
	EXCHANGE (2, 1);

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

	    scratch_block[scratch_index] = b;
	    scratch_list[scratch_index++] = qty_scratch_rtx[q];

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