loop.c

GUN开源阻止下的编译器GCC

    }

  max_luid = i + 1;

  /* Don't leave gaps in uid_luid for insns that have been
     deleted.  It is possible that the first or last insn
     using some register has been deleted by cross-jumping.
     Make sure that uid_luid for that former insn's uid
     points to the general area where that insn used to be.  */
  for (i = 0; i < max_uid_for_loop; i++)
    {
      uid_luid[0] = uid_luid[i];
      if (uid_luid[0] != 0)
	break;
    }
  for (i = 0; i < max_uid_for_loop; i++)
    if (uid_luid[i] == 0)
      uid_luid[i] = uid_luid[i - 1];

  /* Create a mapping from loops to BLOCK tree nodes.  */
  if (flag_unroll_loops && write_symbols != NO_DEBUG)
    find_loop_tree_blocks ();

  /* Now scan the loops, last ones first, since this means inner ones are done
     before outer ones.  */
  for (i = max_loop_num-1; i >= 0; i--)
    if (! loop_invalid[i] && loop_number_loop_ends[i])
      scan_loop (loop_number_loop_starts[i], loop_number_loop_ends[i],
		 max_reg_num ());

  /* If debugging and unrolling loops, we must replicate the tree nodes
     corresponding to the blocks inside the loop, so that the original one
     to one mapping will remain.  */
  if (flag_unroll_loops && write_symbols != NO_DEBUG)
    unroll_block_trees ();
}

/* Optimize one loop whose start is LOOP_START and end is END.
   LOOP_START is the NOTE_INSN_LOOP_BEG and END is the matching
   NOTE_INSN_LOOP_END.  */

/* ??? Could also move memory writes out of loops if the destination address
   is invariant, the source is invariant, the memory write is not volatile,
   and if we can prove that no read inside the loop can read this address
   before the write occurs.  If there is a read of this address after the
   write, then we can also mark the memory read as invariant.  */

static void
scan_loop (loop_start, end, nregs)
     rtx loop_start, end;
     int nregs;
{
  register int i;
  register rtx p;
  /* 1 if we are scanning insns that could be executed zero times.  */
  int maybe_never = 0;
  /* 1 if we are scanning insns that might never be executed
     due to a subroutine call which might exit before they are reached.  */
  int call_passed = 0;
  /* For a rotated loop that is entered near the bottom,
     this is the label at the top.  Otherwise it is zero.  */
  rtx loop_top = 0;
  /* Jump insn that enters the loop, or 0 if control drops in.  */
  rtx loop_entry_jump = 0;
  /* Place in the loop where control enters.  */
  rtx scan_start;
  /* Number of insns in the loop.  */
  int insn_count;
  int in_libcall = 0;
  int tem;
  rtx temp;
  /* The SET from an insn, if it is the only SET in the insn.  */
  rtx set, set1;
  /* Chain describing insns movable in current loop.  */
  struct movable *movables = 0;
  /* Last element in `movables' -- so we can add elements at the end.  */
  struct movable *last_movable = 0;
  /* Ratio of extra register life span we can justify
     for saving an instruction.  More if loop doesn't call subroutines
     since in that case saving an insn makes more difference
     and more registers are available.  */
  int threshold;
  /* If we have calls, contains the insn in which a register was used
     if it was used exactly once; contains const0_rtx if it was used more
     than once.  */
  rtx *reg_single_usage = 0;
  /* Nonzero if we are scanning instructions in a sub-loop.  */
  int loop_depth = 0;

  n_times_set = (short *) alloca (nregs * sizeof (short));
  n_times_used = (short *) alloca (nregs * sizeof (short));
  may_not_optimize = (char *) alloca (nregs);

  /* Determine whether this loop starts with a jump down to a test at
     the end.  This will occur for a small number of loops with a test
     that is too complex to duplicate in front of the loop.

     We search for the first insn or label in the loop, skipping NOTEs.
     However, we must be careful not to skip past a NOTE_INSN_LOOP_BEG
     (because we might have a loop executed only once that contains a
     loop which starts with a jump to its exit test) or a NOTE_INSN_LOOP_END
     (in case we have a degenerate loop).

     Note that if we mistakenly think that a loop is entered at the top
     when, in fact, it is entered at the exit test, the only effect will be
     slightly poorer optimization.  Making the opposite error can generate
     incorrect code.  Since very few loops now start with a jump to the 
     exit test, the code here to detect that case is very conservative.  */

  for (p = NEXT_INSN (loop_start);
       p != end
	 && GET_CODE (p) != CODE_LABEL && GET_RTX_CLASS (GET_CODE (p)) != 'i'
	 && (GET_CODE (p) != NOTE
	     || (NOTE_LINE_NUMBER (p) != NOTE_INSN_LOOP_BEG
		 && NOTE_LINE_NUMBER (p) != NOTE_INSN_LOOP_END));
       p = NEXT_INSN (p))
    ;

  scan_start = p;

  /* Set up variables describing this loop.  */
  prescan_loop (loop_start, end);
  threshold = (loop_has_call ? 1 : 2) * (1 + n_non_fixed_regs);

  /* If loop has a jump before the first label,
     the true entry is the target of that jump.
     Start scan from there.
     But record in LOOP_TOP the place where the end-test jumps
     back to so we can scan that after the end of the loop.  */
  if (GET_CODE (p) == JUMP_INSN)
    {
      loop_entry_jump = p;

      /* Loop entry must be unconditional jump (and not a RETURN)  */
      if (simplejump_p (p)
	  && JUMP_LABEL (p) != 0
	  /* Check to see whether the jump actually
	     jumps out of the loop (meaning it's no loop).
	     This case can happen for things like
	     do {..} while (0).  If this label was generated previously
	     by loop, we can't tell anything about it and have to reject
	     the loop.  */
	  && INSN_UID (JUMP_LABEL (p)) < max_uid_for_loop
	  && INSN_LUID (JUMP_LABEL (p)) >= INSN_LUID (loop_start)
	  && INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (end))
	{
	  loop_top = next_label (scan_start);
	  scan_start = JUMP_LABEL (p);
	}
    }

  /* If SCAN_START was an insn created by loop, we don't know its luid
     as required by loop_reg_used_before_p.  So skip such loops.  (This
     test may never be true, but it's best to play it safe.) 

     Also, skip loops where we do not start scanning at a label.  This
     test also rejects loops starting with a JUMP_INSN that failed the
     test above.  */

  if (INSN_UID (scan_start) >= max_uid_for_loop
      || GET_CODE (scan_start) != CODE_LABEL)
    {
      if (loop_dump_stream)
	fprintf (loop_dump_stream, "\nLoop from %d to %d is phony.\n\n",
		 INSN_UID (loop_start), INSN_UID (end));
      return;
    }

  /* Count number of times each reg is set during this loop.
     Set may_not_optimize[I] if it is not safe to move out
     the setting of register I.  If this loop has calls, set
     reg_single_usage[I].  */

  bzero ((char *) n_times_set, nregs * sizeof (short));
  bzero (may_not_optimize, nregs);

  if (loop_has_call)
    {
      reg_single_usage = (rtx *) alloca (nregs * sizeof (rtx));
      bzero ((char *) reg_single_usage, nregs * sizeof (rtx));
    }

  count_loop_regs_set (loop_top ? loop_top : loop_start, end,
		       may_not_optimize, reg_single_usage, &insn_count, nregs);

  for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
    may_not_optimize[i] = 1, n_times_set[i] = 1;
  bcopy ((char *) n_times_set, (char *) n_times_used, nregs * sizeof (short));

  if (loop_dump_stream)
    {
      fprintf (loop_dump_stream, "\nLoop from %d to %d: %d real insns.\n",
	       INSN_UID (loop_start), INSN_UID (end), insn_count);
      if (loop_continue)
	fprintf (loop_dump_stream, "Continue at insn %d.\n",
		 INSN_UID (loop_continue));
    }

  /* Scan through the loop finding insns that are safe to move.
     Set n_times_set negative for the reg being set, so that
     this reg will be considered invariant for subsequent insns.
     We consider whether subsequent insns use the reg
     in deciding whether it is worth actually moving.

     MAYBE_NEVER is nonzero if we have passed a conditional jump insn
     and therefore it is possible that the insns we are scanning
     would never be executed.  At such times, we must make sure
     that it is safe to execute the insn once instead of zero times.
     When MAYBE_NEVER is 0, all insns will be executed at least once
     so that is not a problem.  */

  p = scan_start;
  while (1)
    {
      p = NEXT_INSN (p);
      /* At end of a straight-in loop, we are done.
	 At end of a loop entered at the bottom, scan the top.  */
      if (p == scan_start)
	break;
      if (p == end)
	{
	  if (loop_top != 0)
	    p = loop_top;
	  else
	    break;
	  if (p == scan_start)
	    break;
	}

      if (GET_RTX_CLASS (GET_CODE (p)) == 'i'
	  && find_reg_note (p, REG_LIBCALL, NULL_RTX))
	in_libcall = 1;
      else if (GET_RTX_CLASS (GET_CODE (p)) == 'i'
	       && find_reg_note (p, REG_RETVAL, NULL_RTX))
	in_libcall = 0;

      if (GET_CODE (p) == INSN
	  && (set = single_set (p))
	  && GET_CODE (SET_DEST (set)) == REG
	  && ! may_not_optimize[REGNO (SET_DEST (set))])
	{
	  int tem1 = 0;
	  int tem2 = 0;
	  int move_insn = 0;
	  rtx src = SET_SRC (set);
	  rtx dependencies = 0;

	  /* Figure out what to use as a source of this insn.  If a REG_EQUIV
	     note is given or if a REG_EQUAL note with a constant operand is
	     specified, use it as the source and mark that we should move
	     this insn by calling emit_move_insn rather that duplicating the
	     insn.

	     Otherwise, only use the REG_EQUAL contents if a REG_RETVAL note
	     is present.  */
	  temp = find_reg_note (p, REG_EQUIV, NULL_RTX);
	  if (temp)
	    src = XEXP (temp, 0), move_insn = 1;
	  else 
	    {
	      temp = find_reg_note (p, REG_EQUAL, NULL_RTX);
	      if (temp && CONSTANT_P (XEXP (temp, 0)))
		src = XEXP (temp, 0), move_insn = 1;
	      if (temp && find_reg_note (p, REG_RETVAL, NULL_RTX))
		{
		  src = XEXP (temp, 0);
		  /* A libcall block can use regs that don't appear in
		     the equivalent expression.  To move the libcall,
		     we must move those regs too.  */
		  dependencies = libcall_other_reg (p, src);
		}
	    }

	  /* Don't try to optimize a register that was made
	     by loop-optimization for an inner loop.
	     We don't know its life-span, so we can't compute the benefit.  */
	  if (REGNO (SET_DEST (set)) >= max_reg_before_loop)
	    ;
	  /* In order to move a register, we need to have one of three cases:
	     (1) it is used only in the same basic block as the set
	     (2) it is not a user variable and it is not used in the
	         exit test (this can cause the variable to be used
		 before it is set just like a user-variable).
	     (3) the set is guaranteed to be executed once the loop starts,
	         and the reg is not used until after that.  */
	  else if (! ((! maybe_never
		       && ! loop_reg_used_before_p (set, p, loop_start,
						    scan_start, end))
		      || (! REG_USERVAR_P (SET_DEST (set))
			  && ! REG_LOOP_TEST_P (SET_DEST (set)))
		      || reg_in_basic_block_p (p, SET_DEST (set))))
	    ;
	  else if ((tem = invariant_p (src))
		   && (dependencies == 0
		       || (tem2 = invariant_p (dependencies)) != 0)
		   && (n_times_set[REGNO (SET_DEST (set))] == 1
		       || (tem1
			   = consec_sets_invariant_p (SET_DEST (set),
						      n_times_set[REGNO (SET_DEST (set))],
						      p)))
		   /* If the insn can cause a trap (such as divide by zero),
		      can't move it unless it's guaranteed to be executed
		      once loop is entered.  Even a function call might
		      prevent the trap insn from being reached
		      (since it might exit!)  */
		   && ! ((maybe_never || call_passed)
			 && may_trap_p (src)))
	    {
	      register struct movable *m;
	      register int regno = REGNO (SET_DEST (set));

	      /* A potential lossage is where we have a case where two insns
		 can be combined as long as they are both in the loop, but
		 we move one of them outside the loop.  For large loops,
		 this can lose.  The most common case of this is the address
		 of a function being called.  

		 Therefore, if this register is marked as being used exactly
		 once if we are in a loop with calls (a "large loop"), see if
		 we can replace the usage of this register with the source
		 of this SET.  If we can, delete this insn. 

		 Don't do this if P has a REG_RETVAL note or if we have
		 SMALL_REGISTER_CLASSES and SET_SRC is a hard register.  */

	      if (reg_single_usage && reg_single_usage[regno] != 0
		  && reg_single_usage[regno] != const0_rtx
		  && regno_first_uid[regno] == INSN_UID (p)
		  && (regno_last_uid[regno]
		      == INSN_UID (reg_single_usage[regno]))
		  && n_times_set[REGNO (SET_DEST (set))] == 1
		  && ! side_effects_p (SET_SRC (set))
		  && ! find_reg_note (p, REG_RETVAL, NULL_RTX)
#ifdef SMALL_REGISTER_CLASSES
		  && ! (GET_CODE (SET_SRC (set)) == REG
			&& REGNO (SET_SRC (set)) < FIRST_PSEUDO_REGISTER)
#endif
		  /* This test is not redundant; SET_SRC (set) might be
		     a call-clobbered register and the life of REGNO
		     might span a call.  */
		  && ! modified_between_p (SET_SRC (set), p,
					   reg_single_usage[regno])
		  && no_labels_between_p (p, reg_single_usage[regno])
		  && validate_replace_rtx (SET_DEST (set), SET_SRC (set),
					   reg_single_usage[regno]))
		{
		  /* Replace any usage in a REG_EQUAL note.  Must copy the
		     new source, so that we don't get rtx sharing between the
		     SET_SOURCE and REG_NOTES of insn p.  */
		  REG_NOTES (reg_single_usage[regno])
		    = replace_rtx (REG_NOTES (reg_single_usage[regno]),
				   SET_DEST (set), copy_rtx (SET_SRC (set)));
				   
		  PUT_CODE (p, NOTE);
		  NOTE_LINE_NUMBER (p) = NOTE_INSN_DELETED;
		  NOTE_SOURCE_FILE (p) = 0;
		  n_times_set[regno] = 0;
		  continue;
		}

	      m = (struct movable *) alloca (sizeof (struct movable));
	      m->next = 0;
	      m->insn = p;
	      m->set_src = src;
	      m->dependencies = dependencies;
	      m->set_dest = SET_DEST (set);
	      m->force = 0;
	      m->consec = n_times_set[REGNO (SET_DEST (set))] - 1;
	      m->done = 0;
	      m->forces = 0;
	      m->partial = 0;
	      m->move_insn = move_insn;
	      m->is_equiv = (find_reg_note (p, REG_EQUIV, NULL_RTX) != 0);
	      m->savemode = VOIDmode;
	      m->regno = regno;
	      /* Set M->cond if either invariant_p or consec_sets_invariant_p
		 returned 2 (only conditionally invariant).  */
	      m->cond = ((tem | tem1 | tem2) > 1);
	      m->global = (uid_luid[regno_last_uid[regno]] > INSN_LUID (end)
			   || uid_luid[regno_first_uid[regno]] < INSN_LUID (loop_start));
	      m->match = 0;
	      m->lifetime = (uid_luid[regno_last_uid[regno]]
			     - uid_luid[regno_first_uid[regno]]);
	      m->savings = n_times_used[regno];
	      if (find_reg_note (p, REG_RETVAL, NULL_RTX))
		m->savings += libcall_benefit (p);
	      n_times_set[regno] = move_insn ? -2 : -1;
	      /* Add M to the end of the chain MOVABLES.  */
	      if (movables == 0)
		movables = m;
	      else
		last_movable->next = m;
	      last_movable = m;

	      if (m->consec > 0)
		{
		  /* Skip this insn, not checking REG_LIBCALL notes.  */
		  p = next_nonnote_insn (p);
		  /* Skip the consecutive insns, if there are any.  */
		  p = skip_consec_insns (p, m->consec);
		  /* Back up to the last insn of the consecutive group.  */
		  p = prev_nonnote_insn (p);

		  /* We must now reset m->move_insn, m->is_equiv, and possibly
		     m->set_src to correspond to the effects of all the
		     insns.  */
		  temp = find_reg_note (p, REG_EQUIV, NULL_RTX);
		  if (temp)
		    m->set_src = XEXP (temp, 0), m->move_insn = 1;