loop.c

早期freebsd实现

		    || (GET_MODE_CLASS (GET_MODE (m->set_dest)) == MODE_INT
			&& GET_MODE_CLASS (GET_MODE (m1->set_dest)) == MODE_INT
			&& (GET_MODE_BITSIZE (GET_MODE (m->set_dest))
			    >= GET_MODE_BITSIZE (GET_MODE (m1->set_dest)))))
		   /* See if the source of M1 says it matches M.  */
		   && ((GET_CODE (m1->set_src) == REG
			&& matched_regs[REGNO (m1->set_src)])
		       || rtx_equal_for_loop_p (m->set_src, m1->set_src,
						movables))))
	      && ((m->dependencies == m1->dependencies)
		  || rtx_equal_p (m->dependencies, m1->dependencies)))
	    {
	      m->lifetime += m1->lifetime;
	      m->savings += m1->savings;
	      m1->done = 1;
	      m1->match = m;
	      matched_regs[m1->regno] = 1;
	    }
      }

  /* Now combine the regs used for zero-extension.
     This can be done for those not marked `global'
     provided their lives don't overlap.  */

  for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT); mode != VOIDmode;
       mode = GET_MODE_WIDER_MODE (mode))
    {
      register struct movable *m0 = 0;

      /* Combine all the registers for extension from mode MODE.
	 Don't combine any that are used outside this loop.  */
      for (m = movables; m; m = m->next)
	if (m->partial && ! m->global
	    && mode == GET_MODE (SET_SRC (PATTERN (NEXT_INSN (m->insn)))))
	  {
	    register struct movable *m1;
	    int first = uid_luid[regno_first_uid[m->regno]];
	    int last = uid_luid[regno_last_uid[m->regno]];

	    if (m0 == 0)
	      {
		/* First one: don't check for overlap, just record it.  */
		m0 = m;
		  continue;
	      }

	    /* Make sure they extend to the same mode.
	       (Almost always true.)  */
	    if (GET_MODE (m->set_dest) != GET_MODE (m0->set_dest))
		continue;

	    /* We already have one: check for overlap with those
	       already combined together.  */
	    for (m1 = movables; m1 != m; m1 = m1->next)
	      if (m1 == m0 || (m1->partial && m1->match == m0))
		if (! (uid_luid[regno_first_uid[m1->regno]] > last
		       || uid_luid[regno_last_uid[m1->regno]] < first))
		  goto overlap;

	    /* No overlap: we can combine this with the others.  */
	    m0->lifetime += m->lifetime;
	    m0->savings += m->savings;
	    m->done = 1;
	    m->match = m0;

	  overlap: ;
	  }
    }
}

/* Return 1 if regs X and Y will become the same if moved.  */

static int
regs_match_p (x, y, movables)
     rtx x, y;
     struct movable *movables;
{
  int xn = REGNO (x);
  int yn = REGNO (y);
  struct movable *mx, *my;

  for (mx = movables; mx; mx = mx->next)
    if (mx->regno == xn)
      break;

  for (my = movables; my; my = my->next)
    if (my->regno == yn)
      break;

  return (mx && my
	  && ((mx->match == my->match && mx->match != 0)
	      || mx->match == my
	      || mx == my->match));
}

/* Return 1 if X and Y are identical-looking rtx's.
   This is the Lisp function EQUAL for rtx arguments.

   If two registers are matching movables or a movable register and an
   equivalent constant, consider them equal.  */

static int
rtx_equal_for_loop_p (x, y, movables)
     rtx x, y;
     struct movable *movables;
{
  register int i;
  register int j;
  register struct movable *m;
  register enum rtx_code code;
  register char *fmt;

  if (x == y)
    return 1;
  if (x == 0 || y == 0)
    return 0;

  code = GET_CODE (x);

  /* If we have a register and a constant, they may sometimes be
     equal.  */
  if (GET_CODE (x) == REG && n_times_set[REGNO (x)] == -2
      && CONSTANT_P (y))
    for (m = movables; m; m = m->next)
      if (m->move_insn && m->regno == REGNO (x)
	  && rtx_equal_p (m->set_src, y))
	return 1;

  else if (GET_CODE (y) == REG && n_times_set[REGNO (y)] == -2
	   && CONSTANT_P (x))
    for (m = movables; m; m = m->next)
      if (m->move_insn && m->regno == REGNO (y)
	  && rtx_equal_p (m->set_src, x))
	return 1;

  /* Otherwise, rtx's of different codes cannot be equal.  */
  if (code != GET_CODE (y))
    return 0;

  /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
     (REG:SI x) and (REG:HI x) are NOT equivalent.  */

  if (GET_MODE (x) != GET_MODE (y))
    return 0;

  /* These three types of rtx's can be compared nonrecursively.  */
  if (code == REG)
    return (REGNO (x) == REGNO (y) || regs_match_p (x, y, movables));

  if (code == LABEL_REF)
    return XEXP (x, 0) == XEXP (y, 0);
  if (code == SYMBOL_REF)
    return XSTR (x, 0) == XSTR (y, 0);

  /* Compare the elements.  If any pair of corresponding elements
     fail to match, return 0 for the whole things.  */

  fmt = GET_RTX_FORMAT (code);
  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
    {
      switch (fmt[i])
	{
	case 'w':
	  if (XWINT (x, i) != XWINT (y, i))
	    return 0;
	  break;

	case 'i':
	  if (XINT (x, i) != XINT (y, i))
	    return 0;
	  break;

	case 'E':
	  /* Two vectors must have the same length.  */
	  if (XVECLEN (x, i) != XVECLEN (y, i))
	    return 0;

	  /* And the corresponding elements must match.  */
	  for (j = 0; j < XVECLEN (x, i); j++)
	    if (rtx_equal_for_loop_p (XVECEXP (x, i, j), XVECEXP (y, i, j), movables) == 0)
	      return 0;
	  break;

	case 'e':
	  if (rtx_equal_for_loop_p (XEXP (x, i), XEXP (y, i), movables) == 0)
	    return 0;
	  break;

	case 's':
	  if (strcmp (XSTR (x, i), XSTR (y, i)))
	    return 0;
	  break;

	case 'u':
	  /* These are just backpointers, so they don't matter.  */
	  break;

	case '0':
	  break;

	  /* It is believed that rtx's at this level will never
	     contain anything but integers and other rtx's,
	     except for within LABEL_REFs and SYMBOL_REFs.  */
	default:
	  abort ();
	}
    }
  return 1;
}

/* If X contains any LABEL_REF's, add REG_LABEL notes for them to all
  insns in INSNS which use thet reference.  */

static void
add_label_notes (x, insns)
     rtx x;
     rtx insns;
{
  enum rtx_code code = GET_CODE (x);
  int i, j;
  char *fmt;
  rtx insn;

  if (code == LABEL_REF && !LABEL_REF_NONLOCAL_P (x))
    {
      for (insn = insns; insn; insn = NEXT_INSN (insn))
	if (reg_mentioned_p (XEXP (x, 0), insn))
	  REG_NOTES (insn) = gen_rtx (EXPR_LIST, REG_LABEL, XEXP (x, 0),
				      REG_NOTES (insn));
      return;
    }

  fmt = GET_RTX_FORMAT (code);
  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
    {
      if (fmt[i] == 'e')
	add_label_notes (XEXP (x, i), insns);
      else if (fmt[i] == 'E')
	for (j = XVECLEN (x, i) - 1; j >= 0; j--)
	  add_label_notes (XVECEXP (x, i, j), insns);
    }
}

/* Scan MOVABLES, and move the insns that deserve to be moved.
   If two matching movables are combined, replace one reg with the
   other throughout.  */

static void
move_movables (movables, threshold, insn_count, loop_start, end, nregs)
     struct movable *movables;
     int threshold;
     int insn_count;
     rtx loop_start;
     rtx end;
     int nregs;
{
  rtx new_start = 0;
  register struct movable *m;
  register rtx p;
  /* Map of pseudo-register replacements to handle combining
     when we move several insns that load the same value
     into different pseudo-registers.  */
  rtx *reg_map = (rtx *) alloca (nregs * sizeof (rtx));
  char *already_moved = (char *) alloca (nregs);

  bzero (already_moved, nregs);
  bzero (reg_map, nregs * sizeof (rtx));

  num_movables = 0;

  for (m = movables; m; m = m->next)
    {
      /* Describe this movable insn.  */

      if (loop_dump_stream)
	{
	  fprintf (loop_dump_stream, "Insn %d: regno %d (life %d), ",
		   INSN_UID (m->insn), m->regno, m->lifetime);
	  if (m->consec > 0)
	    fprintf (loop_dump_stream, "consec %d, ", m->consec);
	  if (m->cond)
	    fprintf (loop_dump_stream, "cond ");
	  if (m->force)
	    fprintf (loop_dump_stream, "force ");
	  if (m->global)
	    fprintf (loop_dump_stream, "global ");
	  if (m->done)
	    fprintf (loop_dump_stream, "done ");
	  if (m->move_insn)
	    fprintf (loop_dump_stream, "move-insn ");
	  if (m->match)
	    fprintf (loop_dump_stream, "matches %d ",
		     INSN_UID (m->match->insn));
	  if (m->forces)
	    fprintf (loop_dump_stream, "forces %d ",
		     INSN_UID (m->forces->insn));
	}

      /* Count movables.  Value used in heuristics in strength_reduce.  */
      num_movables++;

      /* Ignore the insn if it's already done (it matched something else).
	 Otherwise, see if it is now safe to move.  */

      if (!m->done
	  && (! m->cond
	      || (1 == invariant_p (m->set_src)
		  && (m->dependencies == 0
		      || 1 == invariant_p (m->dependencies))
		  && (m->consec == 0
		      || 1 == consec_sets_invariant_p (m->set_dest,
						       m->consec + 1,
						       m->insn))))
	  && (! m->forces || m->forces->done))
	{
	  register int regno;
	  register rtx p;
	  int savings = m->savings;

	  /* We have an insn that is safe to move.
	     Compute its desirability.  */

	  p = m->insn;
	  regno = m->regno;

	  if (loop_dump_stream)
	    fprintf (loop_dump_stream, "savings %d ", savings);

	  if (moved_once[regno])
	    {
	      insn_count *= 2;

	      if (loop_dump_stream)
		fprintf (loop_dump_stream, "halved since already moved ");
	    }

	  /* An insn MUST be moved if we already moved something else
	     which is safe only if this one is moved too: that is,
	     if already_moved[REGNO] is nonzero.  */

	  /* An insn is desirable to move if the new lifetime of the
	     register is no more than THRESHOLD times the old lifetime.
	     If it's not desirable, it means the loop is so big
	     that moving won't speed things up much,
	     and it is liable to make register usage worse.  */

	  /* It is also desirable to move if it can be moved at no
	     extra cost because something else was already moved.  */

	  if (already_moved[regno]
	      || (threshold * savings * m->lifetime) >= insn_count
	      || (m->forces && m->forces->done
		  && n_times_used[m->forces->regno] == 1))
	    {
	      int count;
	      register struct movable *m1;
	      rtx first;

	      /* Now move the insns that set the reg.  */

	      if (m->partial && m->match)
		{
		  rtx newpat, i1;
		  rtx r1, r2;
		  /* Find the end of this chain of matching regs.
		     Thus, we load each reg in the chain from that one reg.
		     And that reg is loaded with 0 directly,
		     since it has ->match == 0.  */
		  for (m1 = m; m1->match; m1 = m1->match);
		  newpat = gen_move_insn (SET_DEST (PATTERN (m->insn)),
					  SET_DEST (PATTERN (m1->insn)));
		  i1 = emit_insn_before (newpat, loop_start);

		  /* Mark the moved, invariant reg as being allowed to
		     share a hard reg with the other matching invariant.  */
		  REG_NOTES (i1) = REG_NOTES (m->insn);
		  r1 = SET_DEST (PATTERN (m->insn));
		  r2 = SET_DEST (PATTERN (m1->insn));
		  regs_may_share = gen_rtx (EXPR_LIST, VOIDmode, r1,
					    gen_rtx (EXPR_LIST, VOIDmode, r2,
						     regs_may_share));
		  delete_insn (m->insn);

		  if (new_start == 0)
		    new_start = i1;

		  if (loop_dump_stream)
		    fprintf (loop_dump_stream, " moved to %d", INSN_UID (i1));
		}
	      /* If we are to re-generate the item being moved with a
		 new move insn, first delete what we have and then emit
		 the move insn before the loop.  */
	      else if (m->move_insn)
		{
		  rtx i1, temp;

		  for (count = m->consec; count >= 0; count--)
		    {
		      /* If this is the first insn of a library call sequence,
			 skip to the end.  */
		      if (GET_CODE (p) != NOTE
			  && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
			p = XEXP (temp, 0);

		      /* If this is the last insn of a libcall sequence, then
			 delete every insn in the sequence except the last.
			 The last insn is handled in the normal manner.  */
		      if (GET_CODE (p) != NOTE
			  && (temp = find_reg_note (p, REG_RETVAL, NULL_RTX)))
			{
			  temp = XEXP (temp, 0);
			  while (temp != p)
			    temp = delete_insn (temp);
			}

		      p = delete_insn (p);
		    }