local-alloc.c

早期freebsd实现

      else if (sregno < FIRST_PSEUDO_REGISTER
	       && dead_or_set_p (p, src))
	break;
    }
}

/* INSN is a copy of SRC to DEST, in which SRC dies.  See if we now have
   a sequence of insns that modify DEST followed by an insn that sets
   SRC to DEST in which DEST dies, with no prior modification of DEST.
   (There is no need to check if the insns in between actually modify
   DEST.  We should not have cases where DEST is not modified, but
   the optimization is safe if no such modification is detected.)
   In that case, we can replace all uses of DEST, starting with INSN and
   ending with the set of SRC to DEST, with SRC.  We do not do this
   optimization if a CALL_INSN is crossed unless SRC already crosses a
   call.

   It is assumed that DEST and SRC are pseudos; it is too complicated to do
   this for hard registers since the substitutions we may make might fail.  */

static void
optimize_reg_copy_2 (insn, dest, src)
     rtx insn;
     rtx dest;
     rtx src;
{
  rtx p, q;
  rtx set;
  int sregno = REGNO (src);
  int dregno = REGNO (dest);

  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;

      set = single_set (p);
      if (set && SET_SRC (set) == dest && SET_DEST (set) == src
	  && find_reg_note (p, REG_DEAD, dest))
	{
	  /* We can do the optimization.  Scan forward from INSN again,
	     replacing regs as we go.  */

	  /* Set to stop at next insn.  */
	  for (q = insn; q != NEXT_INSN (p); q = NEXT_INSN (q))
	    if (GET_RTX_CLASS (GET_CODE (q)) == 'i')
	      {
		if (reg_mentioned_p (dest, PATTERN (q)))
		  {
		    PATTERN (q) = replace_rtx (PATTERN (q), dest, src);

		    /* 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.  */
		    reg_n_refs[dregno] -= loop_depth;
		    reg_n_refs[sregno] += loop_depth;
		  }


	      if (GET_CODE (q) == CALL_INSN)
		{
		  reg_n_calls_crossed[dregno]--;
		  reg_n_calls_crossed[sregno]++;
		}
	      }

	  remove_note (p, find_reg_note (p, REG_DEAD, dest));
	  reg_n_deaths[dregno]--;
	  remove_note (insn, find_reg_note (insn, REG_DEAD, src));
	  reg_n_deaths[sregno]--;
	  return;
	}

      if (reg_set_p (src, p)
	  || (GET_CODE (p) == CALL_INSN && reg_n_calls_crossed[sregno] == 0))
	break;
    }
}
	      
/* Find registers that are equivalent to a single value throughout the
   compilation (either because they can be referenced in memory or are set once
   from a single constant).  Lower their priority for a register.

   If such a register is only referenced once, try substituting its value
   into the using insn.  If it succeeds, we can eliminate the register
   completely.  */

static void
update_equiv_regs ()
{
  rtx *reg_equiv_init_insn = (rtx *) alloca (max_regno * sizeof (rtx *));
  rtx *reg_equiv_replacement = (rtx *) alloca (max_regno * sizeof (rtx *));
  rtx insn;

  bzero (reg_equiv_init_insn, max_regno * sizeof (rtx *));
  bzero (reg_equiv_replacement, max_regno * sizeof (rtx *));

  init_alias_analysis ();

  loop_depth = 1;

  /* Scan the insns and find which registers have equivalences.  Do this
     in a separate scan of the insns because (due to -fcse-follow-jumps)
     a register can be set below its use.  */
  for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
    {
      rtx note;
      rtx set = single_set (insn);
      rtx dest;
      int regno;

      if (GET_CODE (insn) == NOTE)
	{
	  if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
	    loop_depth++;
	  else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
	    loop_depth--;
	}

      /* If this insn contains more (or less) than a single SET, ignore it.  */
      if (set == 0)
	continue;

      dest = SET_DEST (set);

      /* If this sets a MEM to the contents of a REG that is only used
	 in a single basic block, see if the register is always equivalent
	 to that memory location and if moving the store from INSN to the
	 insn that set REG is safe.  If so, put a REG_EQUIV note on the
	 initializing insn.  */

      if (GET_CODE (dest) == MEM && GET_CODE (SET_SRC (set)) == REG
	  && (regno = REGNO (SET_SRC (set))) >= FIRST_PSEUDO_REGISTER
	  && reg_basic_block[regno] >= 0
	  && reg_equiv_init_insn[regno] != 0
	  && validate_equiv_mem (reg_equiv_init_insn[regno], SET_SRC (set),
				 dest)
	  && ! memref_used_between_p (SET_DEST (set),
				      reg_equiv_init_insn[regno], insn))
	REG_NOTES (reg_equiv_init_insn[regno])
	  = gen_rtx (EXPR_LIST, REG_EQUIV, dest,
		     REG_NOTES (reg_equiv_init_insn[regno]));

      /* If this is a register-register copy where SRC is not dead, see if we
	 can optimize it.  */
      if (flag_expensive_optimizations && GET_CODE (dest) == REG
	  && GET_CODE (SET_SRC (set)) == REG
	  && ! find_reg_note (insn, REG_DEAD, SET_SRC (set)))
	optimize_reg_copy_1 (insn, dest, SET_SRC (set));

      /* Similarly for a pseudo-pseudo copy when SRC is dead.  */
      else if (flag_expensive_optimizations && GET_CODE (dest) == REG
	       && REGNO (dest) >= FIRST_PSEUDO_REGISTER
	       && GET_CODE (SET_SRC (set)) == REG
	       && REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER
	       && find_reg_note (insn, REG_DEAD, SET_SRC (set)))
	optimize_reg_copy_2 (insn, dest, SET_SRC (set));

      /* Otherwise, we only handle the case of a pseudo register being set
	 once.  */
      if (GET_CODE (dest) != REG
	  || (regno = REGNO (dest)) < FIRST_PSEUDO_REGISTER
	  || reg_n_sets[regno] != 1)
	continue;

      note = find_reg_note (insn, REG_EQUAL, NULL_RTX);

      /* Record this insn as initializing this register.  */
      reg_equiv_init_insn[regno] = insn;

      /* If this register is known to be equal to a constant, record that
	 it is always equivalent to the constant.  */
      if (note && CONSTANT_P (XEXP (note, 0)))
	PUT_MODE (note, (enum machine_mode) REG_EQUIV);

      /* If this insn introduces a "constant" register, decrease the priority
	 of that register.  Record this insn if the register is only used once
	 more and the equivalence value is the same as our source.

	 The latter condition is checked for two reasons:  First, it is an
	 indication that it may be more efficient to actually emit the insn
	 as written (if no registers are available, reload will substitute
	 the equivalence).  Secondly, it avoids problems with any registers
	 dying in this insn whose death notes would be missed.

	 If we don't have a REG_EQUIV note, see if this insn is loading
	 a register used only in one basic block from a MEM.  If so, and the
	 MEM remains unchanged for the life of the register, add a REG_EQUIV
	 note.  */
	 
      note = find_reg_note (insn, REG_EQUIV, NULL_RTX);

      if (note == 0 && reg_basic_block[regno] >= 0
	  && GET_CODE (SET_SRC (set)) == MEM
	  && validate_equiv_mem (insn, dest, SET_SRC (set)))
	REG_NOTES (insn) = note = gen_rtx (EXPR_LIST, REG_EQUIV, SET_SRC (set),
					   REG_NOTES (insn));

      /* Don't mess with things live during setjmp.  */
      if (note && reg_live_length[regno] >= 0)
	{
	  int regno = REGNO (dest);

	  /* Note that the statement below does not affect the priority
	     in local-alloc!  */
	  reg_live_length[regno] *= 2;

	  /* If the register is referenced exactly twice, meaning it is set
	     once and used once, indicate that the reference may be replaced
	     by the equivalence we computed above.  If the register is only
	     used in one basic block, this can't succeed or combine would
	     have done it.

	     It would be nice to use "loop_depth * 2" in the compare
	     below.  Unfortunately, LOOP_DEPTH need not be constant within
	     a basic block so this would be too complicated.

	     This case normally occurs when a parameter is read from memory
	     and then used exactly once, not in a loop.  */

	  if (reg_n_refs[regno] == 2
	      && reg_basic_block[regno] < 0
	      && rtx_equal_p (XEXP (note, 0), SET_SRC (set)))
	    reg_equiv_replacement[regno] = SET_SRC (set);
	}
    }

  /* Now scan all regs killed in an insn to see if any of them are registers
     only used that once.  If so, see if we can replace the reference with
     the equivalent from.  If we can, delete the initializing reference
     and this register will go away.  */
  for (insn = next_active_insn (get_insns ());
       insn;
       insn = next_active_insn (insn))
    {
      rtx link;

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

	    if (reg_equiv_replacement[regno]
		&& validate_replace_rtx (regno_reg_rtx[regno],
					 reg_equiv_replacement[regno], insn))
	      {
		rtx equiv_insn = reg_equiv_init_insn[regno];

		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;
	      }
	  }
    }
}

/* 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 ();
  short *qty_order;
  int no_conflict_combined_regno = -1;

  /* 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 (regs_live_at, (2 * insn_count + 2) * sizeof (HARD_REG_SET));

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

#ifdef HARD_REG_SET
  regs_live = *basic_block_live_at_start[b];
#else
  COPY_HARD_REG_SET (regs_live, basic_block_live_at_start[b]);
#endif

  /* 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.
	     For a commutative operation, try (set reg0 (arithop ... reg1)).
	     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
	      )
	    {
	      r0 = recog_operand[0];
	      r1 = recog_operand[1];

	      /* If the first 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][1][0] == 'p'
#else
		  insn_operand_address_p[insn_code_number][1]
#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.  */
#ifdef REGISTER_CONSTRAINTS
		  int may_save_copy
		    = ((SET_DEST (body) == r0 && SET_SRC (body) == r1)
		       || (r1 == recog_operand[1]
			   && (requires_inout_p (insn_operand_constraint[insn_code_number][1]))));
#else
		  int may_save_copy = 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 == 0
		      && insn_n_operands[insn_code_number] > 2
#ifdef REGISTER_CONSTRAINTS
		      && insn_operand_constraint[insn_code_number][1][0] == '%'
#else
		      && GET_CODE (PATTERN (insn)) == SET
		      && (GET_RTX_CLASS (GET_CODE (SET_SRC (PATTERN (insn))))
			  == 'c')