local-alloc.c

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

	    {
	      if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
		++depth;
	      else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
		{
		  --depth;
		  if (depth < 0)
		    abort ();
		}
	    }

	  continue;
	}

      for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
	{
	  if (REG_NOTE_KIND (link) == REG_DEAD
	      /* Make sure this insn still refers to the register.  */
	      && reg_mentioned_p (XEXP (link, 0), PATTERN (insn)))
	    {
	      int regno = REGNO (XEXP (link, 0));
	      rtx equiv_insn;

	      if (! reg_equiv_replace[regno])
		continue;

	      equiv_insn = reg_equiv_init_insn[regno];

	      if (validate_replace_rtx (regno_reg_rtx[regno],
					reg_equiv_replacement[regno], insn))
		{
		  remove_death (regno, insn);
		  REG_N_REFS (regno) = 0;
		  PUT_CODE (equiv_insn, NOTE);
		  NOTE_LINE_NUMBER (equiv_insn) = NOTE_INSN_DELETED;
		  NOTE_SOURCE_FILE (equiv_insn) = 0;
		}
	      /* If we aren't in a loop, and there are no calls in
		 INSN or in the initialization of the register, then
		 move the initialization of the register to just
		 before INSN.  Update the flow information.  */
	      else if (depth == 0
		       && GET_CODE (equiv_insn) == INSN
		       && GET_CODE (insn) == INSN
		       && REG_BASIC_BLOCK (regno) < 0)
		{
		  int l;

		  emit_insn_before (copy_rtx (PATTERN (equiv_insn)), insn);
		  REG_NOTES (PREV_INSN (insn)) = REG_NOTES (equiv_insn);

		  PUT_CODE (equiv_insn, NOTE);
		  NOTE_LINE_NUMBER (equiv_insn) = NOTE_INSN_DELETED;
		  NOTE_SOURCE_FILE (equiv_insn) = 0;
		  REG_NOTES (equiv_insn) = 0;

		  if (block < 0)
		    REG_BASIC_BLOCK (regno) = 0;
		  else
		    REG_BASIC_BLOCK (regno) = block;
		  REG_N_CALLS_CROSSED (regno) = 0;
		  REG_LIVE_LENGTH (regno) = 2;

		  if (block >= 0 && insn == basic_block_head[block])
		    basic_block_head[block] = PREV_INSN (insn);

		  for (l = 0; l < n_basic_blocks; l++)
		    CLEAR_REGNO_REG_SET (basic_block_live_at_start[l], regno);
		}
	    }
	}
    }
}

/* Allocate hard regs to the pseudo regs used only within block number B.
   Only the pseudos that die but once can be handled.  */

static void
block_alloc (b)
     int b;
{
  register int i, q;
  register rtx insn;
  rtx note;
  int insn_number = 0;
  int insn_count = 0;
  int max_uid = get_max_uid ();
  int *qty_order;
  int no_conflict_combined_regno = -1;
  /* Counter to prevent allocating more SCRATCHes than can be stored
     in SCRATCH_LIST.  */
  int scratches_allocated = scratch_index;

  /* Count the instructions in the basic block.  */

  insn = basic_block_end[b];
  while (1)
    {
      if (GET_CODE (insn) != NOTE)
	if (++insn_count > max_uid)
	  abort ();
      if (insn == basic_block_head[b])
	break;
      insn = PREV_INSN (insn);
    }

  /* +2 to leave room for a post_mark_life at the last insn and for
     the birth of a CLOBBER in the first insn.  */
  regs_live_at = (HARD_REG_SET *) alloca ((2 * insn_count + 2)
					  * sizeof (HARD_REG_SET));
  bzero ((char *) regs_live_at, (2 * insn_count + 2) * sizeof (HARD_REG_SET));

  /* Initialize table of hardware registers currently live.  */

  REG_SET_TO_HARD_REG_SET (regs_live, basic_block_live_at_start[b]);

  /* This loop scans the instructions of the basic block
     and assigns quantities to registers.
     It computes which registers to tie.  */

  insn = basic_block_head[b];
  while (1)
    {
      register rtx body = PATTERN (insn);

      if (GET_CODE (insn) != NOTE)
	insn_number++;

      if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
	{
	  register rtx link, set;
	  register int win = 0;
	  register rtx r0, r1;
	  int combined_regno = -1;
	  int i;
	  int insn_code_number = recog_memoized (insn);

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