/* Find invariant expressions that are equal and can be combined into   one register.  */static voidcombine_movables (movables, nregs)     struct movable *movables;     int nregs;{  register struct movable *m;  char *matched_regs = (char *) alloca (nregs);  enum machine_mode mode;  /* Regs that are set more than once are not allowed to match     or be matched.  I'm no longer sure why not.  */  /* Perhaps testing m->consec_sets would be more appropriate here?  */  for (m = movables; m; m = m->next)    if (m->match == 0 && n_times_used[m->regno] == 1 && !m->partial)      {	register struct movable *m1;	int regno = m->regno;	bzero (matched_regs, nregs);	matched_regs[regno] = 1;	for (m1 = movables; m1; m1 = m1->next)	  if (m != m1 && m1->match == 0 && n_times_used[m1->regno] == 1	      /* A reg used outside the loop mustn't be eliminated.  */	      && !m1->global	      /* A reg used for zero-extending mustn't be eliminated.  */	      && !m1->partial	      && (matched_regs[m1->regno]		  ||		  (		   /* Can combine regs with different modes loaded from the		      same constant only if the modes are the same or		      if both are integer modes with M wider or the same		      width as M1.  The check for integer is redundant, but		      safe, since the only case of differing destination		      modes with equal sources is when both sources are		      VOIDmode, i.e., CONST_INT.  */		   (GET_MODE (m->set_dest) == GET_MODE (m1->set_dest)		    || (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 intregs_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 intrtx_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 voidadd_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))    {      rtx next = next_real_insn (XEXP (x, 0));      /* Don't record labels that refer to dispatch tables.	 This is not necessary, since the tablejump references the same label.	 And if we did record them, flow.c would make worse code.  */      if (next == 0	  || ! (GET_CODE (next) == JUMP_INSN		&& (GET_CODE (PATTERN (next)) == ADDR_VEC		    || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC)))	{	  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 voidmove_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 ((char *) 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;