loop.c

这是完整的gcc源代码

	   They don't have valid LUIDs, and they never jump into loops.  */
	&& INSN_UID (insn) < max_uid
	&& (INSN_LUID (insn) < INSN_LUID (start)
	    || INSN_LUID (insn) > INSN_LUID (end))
	/* We have a jump that is outside the loop.
	   Does it jump into the loop?  */
	&& can_jump_into_range_p (PATTERN (insn),
				  INSN_LUID (start), INSN_LUID (end)))
      return 0;

#if 0      
  /* Now scan all labels between them and check for any jumps from outside.
     This uses the ref-chains set up by find_basic_blocks.
     This code is not used because it's more convenient for other reasons
     to do the loop optimization before find_basic_blocks.  */

  for (insn = start; insn != end; insn = NEXT_INSN (insn))
    if (GET_CODE (insn) == CODE_LABEL)
      {
	register rtx y;
	for (y = LABEL_REFS (insn); y != insn; y = LABEL_NEXTREF (y))
	  if (INSN_LUID (CONTAINING_INSN (y)) < INSN_LUID (start)
	      || INSN_LUID (CONTAINING_INSN (y)) > INSN_LUID (end))
	    return 0;
      }
#endif

  return end;
}

/* Return 1 if somewhere in X is a LABEL_REF to a label
   located between BEG and END.  */

static int
can_jump_into_range_p (x, beg, end)
     rtx x;
     int beg, end;
{
  register enum rtx_code code = GET_CODE (x);
  register int i;
  register char *fmt;

  if (code == LABEL_REF)
    {
      register int luid = INSN_LUID (XEXP (x, 0));
      return luid > beg && luid < end;
    }

  fmt = GET_RTX_FORMAT (code);
  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
    {
      if (fmt[i] == 'e')
	{
	  if (can_jump_into_range_p (XEXP (x, i), beg, end))
	    return 1;
	}
      else if (fmt[i] == 'E')
	{
	  register int j;
	  for (j = 0; j < XVECLEN (x, i); j++)
	    if (can_jump_into_range_p (XVECEXP (x, i, j), beg, end))
	      return 1;
	}
    }

  return 0;
}

/* Return 1 if somewhere in X is a LABEL_REF to a label
   that is *not* located between BEG and END.  */

static int
can_jump_outside_range_p (x, beg, end)
     rtx x;
     int beg, end;
{
  register enum rtx_code code = GET_CODE (x);
  register int i;
  register char *fmt;

  if (code == LABEL_REF)
    {
      register int luid = INSN_LUID (XEXP (x, 0));
      return !(luid > beg && luid < end);
    }

  fmt = GET_RTX_FORMAT (code);
  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
    {
      if (fmt[i] == 'e')
	{
	  if (can_jump_outside_range_p (XEXP (x, i), beg, end))
	    return 1;
	}
      else if (fmt[i] == 'E')
	{
	  register int j;
	  for (j = 0; j < XVECLEN (x, i); j++)
	    if (can_jump_outside_range_p (XVECEXP (x, i, j), beg, end))
	      return 1;
	}
    }

  return 0;
}

/* Return nonzero if there is a label in the range from
   insn INSN to the insn whose luid is END.  */

static int
labels_in_range_p (insn, end)
     rtx insn;
     int end;
{
  while (insn && INSN_LUID (insn) <= end)
    {
      if (GET_CODE (insn) == CODE_LABEL)
	return 0;
      insn = NEXT_INSN (insn);
    }

  return 0;
}

/* Record that a memory reference X is being set.  */

static void
note_addr_stored (x)
     rtx x;
{
  if (x == 0 || GET_CODE (x) != MEM)
    return;

  /* Count number of memory writes.
     This affects heuristics in strength_reduce.  */
  num_mem_sets++;
  if (unknown_address_altered)
    return;

  if (GET_MODE (x) == BLKmode)
    unknown_address_altered = 1;
  else if (rtx_addr_varies_p (x))
    {
      if (GET_CODE (XEXP (x, 0)) == PLUS)
	unknown_aggregate_altered = 1;
      else
	unknown_address_altered = 1;
    }
  else
    {
      register int i;
      register rtx addr = XEXP (x, 0);

      if (MEM_IN_STRUCT_P (x))
	fixed_aggregate_altered = 1;
      for (i = 0; i < loop_store_addrs_idx; i++)
	if (rtx_equal_p (loop_store_addrs[i], addr))
	  {
	    if (loop_store_widths[i] < GET_MODE_SIZE (GET_MODE (x)))
	      loop_store_widths[i] = GET_MODE_SIZE (GET_MODE (x));
	    break;
	  }
      if (i == NUM_STORES)
	unknown_address_altered = 1;
      else if (i == loop_store_addrs_idx)
	{
	  loop_store_widths[i] = GET_MODE_SIZE (GET_MODE (x));
	  loop_store_addrs[loop_store_addrs_idx++] = addr;
	}
    }
}

/* Return nonzero if the rtx X is invariant over the current loop.

   The value is 2 if we refer to something only conditionally invariant.

   If `unknown_address_altered' is nonzero, no memory ref is invariant.
   Otherwise if `unknown_aggregate_altered' is nonzero,
   a memory ref is invariant if it is not part of an aggregate
   and its address is fixed and not in `loop_store_addrs'.
   Otherwise if `fixed_aggregate_altered' is nonzero,
   a memory ref is invariant
   if its address is fixed and not in `loop_store_addrs'.
   Otherwise, a memory ref is invariant if its address is fixed and not in
   `loop_store_addrs' or if it is not an aggregate.  */

static int
invariant_p (x)
     register rtx x;
{
  register int i;
  register enum rtx_code code;
  register char *fmt;
  int conditional = 0;

  if (x == 0)
    return 1;
  code = GET_CODE (x);
  switch (code)
    {
    case CONST_INT:
    case CONST_DOUBLE:
    case SYMBOL_REF:
    case LABEL_REF:
    case CONST:
      return 1;

    case PC:
    case CC0:
      return 0;

    case REG:
      /* We used to check RTX_UNCHANGING_P (x) here, but that is invalid
	 since the reg might be set by initialization within the loop.  */
      if (x == frame_pointer_rtx || x == arg_pointer_rtx)
	return 1;
      if (n_times_set[REGNO (x)] == -1)
	return 2;
      return n_times_set[REGNO (x)] == 0;

    case MEM:
      /* Constants in the constant pool are invariant.
	 ?? Really we should detect any constant address in the
	 text section.  */
      if (GET_CODE (XEXP (x, 0)) == SYMBOL_REF
	  && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0)))
	return 1;
      /* A store in a varying-address scalar (or a subroutine call)
	 could clobber anything in memory.  */
      if (unknown_address_altered)
	return 0;
      /* Don't mess with volatile memory references.  */
      if (MEM_VOLATILE_P (x))
	return 0;
#if 0
      /* If it's declared read-only, it is invariant
	 if its address is invariant.  */
      if (RTX_UNCHANGING_P (x))
	return invariant_p (XEXP (x, 0));
#endif
      /* A store in a varying-address aggregate component
	 could clobber anything except a scalar with a fixed address.  */
      if (unknown_aggregate_altered
	  && ((MEM_IN_STRUCT_P (x) || GET_CODE (XEXP (x, 0)) == PLUS)
	      || rtx_addr_varies_p (x)))
	return 0;
      /* A store in a fixed-address aggregate component
	 could clobber anything whose address is not fixed,
	 even an aggregate component.  */
      if (fixed_aggregate_altered
	  && rtx_addr_varies_p (x))
	return 0;
      /* Any store could clobber a varying-address scalar.  */
      if (loop_store_addrs_idx
	  && !(MEM_IN_STRUCT_P (x) || GET_CODE (XEXP (x, 0)) == PLUS)
	  && rtx_addr_varies_p (x))
	return 0;
      /* A store in a fixed address clobbers overlapping references.  */
      for (i = loop_store_addrs_idx - 1; i >= 0; i--)
	if (addr_overlap_p (x, loop_store_addrs[i], loop_store_widths[i]))
	  return 0;
      /* It's not invalidated by a store in memory
	 but we must still verify the address is invariant.  */
      break;

    case ASM_OPERANDS:
      /* Don't mess with insns declared volatile.  */
      if (MEM_VOLATILE_P (x))
	return 0;
    }

  fmt = GET_RTX_FORMAT (code);
  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
    {
      if (fmt[i] == 'e')
	{
	  int tem = invariant_p (XEXP (x, i));
	  if (tem == 0)
	    return 0;
	  if (tem == 2)
	    conditional = 1;
	}
      else if (fmt[i] == 'E')
	{
	  register int j;
	  for (j = 0; j < XVECLEN (x, i); j++)
	    {
	      int tem = invariant_p (XVECEXP (x, i, j));
	      if (tem == 0)
		return 0;
	      if (tem == 2)
		conditional = 1;
	    }

	}
    }

  return 1 + conditional;
}

/* Return 1 if OTHER (a mem ref) overlaps the area of memory
   which is SIZE bytes starting at BASE.  */

int
addr_overlap_p (other, base, size)
     rtx other;
     rtx base;
     int size;
{
  int start = 0, end;

  if (GET_CODE (base) == CONST)
    base = XEXP (base, 0);
  if (GET_CODE (base) == PLUS
      && GET_CODE (XEXP (base, 1)) == CONST_INT)
    {
      start = INTVAL (XEXP (base, 1));
      base = XEXP (base, 0);
    }

  end = start + size;
  return refers_to_mem_p (other, base, start, end);
}

/* Return nonzero if all the insns in the loop that set REG
   are INSN and the immediately following insns,
   and if each of those insns sets REG in an invariant way
   (not counting uses of REG in them).

   The value is 2 if some of these insns are only conditionally invariant.

   We assume that INSN itself is the first set of REG
   and that its source is invariant.  */

static int
consec_sets_invariant_p (reg, n_sets, insn)
     int n_sets;
     rtx reg, insn;
{
  register rtx p = insn;
  register int regno = REGNO (reg);
  rtx temp;
  /* Number of sets we have to insist on finding after INSN.  */
  int count = n_sets - 1;
  int old = n_times_set[regno];
  int value = 0;
  int this;

  /* If N_SETS hit the limit, we can't rely on its value.  */
  if (n_sets == 127)
    return 0;

  n_times_set[regno] = 0;

  while (count > 0)
    {
      register enum rtx_code code;
      p = NEXT_INSN (p);
      code = GET_CODE (p);

      /* If library call, skip to end of of it.  */
      if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, 0)))
	p = XEXP (temp, 0);

      this = 0;
      if (code == INSN && GET_CODE (PATTERN (p)) == SET
	  && GET_CODE (SET_DEST (PATTERN (p))) == REG
	  && REGNO (SET_DEST (PATTERN (p))) == regno)
	{
	  this = invariant_p (SET_SRC (PATTERN (p)));
	  if (this != 0)
	    value |= this;
	  else if (temp = loop_find_reg_equal (p))
	    {
	      this = invariant_p (XEXP (temp, 0));
	      if (this != 0)
		value |= this;
	    }
	}
      if (this != 0)
	count--;
      else if (code != NOTE)
	{
	  n_times_set[regno] = old;
	  return 0;
	}
    }

  n_times_set[regno] = old;
  /* If invariant_p ever returned 2, we return 2.  */
  return 1 + (value & 2);
}

#if 0
/* I don't think this condition is sufficient to allow INSN
   to be moved, so we no longer test it.  */

/* Return 1 if all insns in the basic block of INSN and following INSN
   that set REG are invariant according to TABLE.  */

static int
all_sets_invariant_p (reg, insn, table)
     rtx reg, insn;
     short *table;
{
  register rtx p = insn;
  register int regno = REGNO (reg);

  while (1)
    {
      register enum rtx_code code;
      p = NEXT_INSN (p);
      code = GET_CODE (p);
      if (code == CODE_LABEL || code == JUMP_INSN)
	return 1;
      if (code == INSN && GET_CODE (PATTERN (p)) == SET
	  && GET_CODE (SET_DEST (PATTERN (p))) == REG
	  && REGNO (SET_DEST (PATTERN (p))) == regno)
	{
	  if (!invariant_p (SET_SRC (PATTERN (p)), table))
	    return 0;
	}
    }
}
#endif /* 0 */

/* Increment N_TIMES_SET at the index of each register
   that is modified by an insn between FROM and TO.
   If the value of an element of N_TIMES_SET becomes 127 or more,
   stop incrementing it, to avoid overflow.

   Store in *COUNT_PTR the number of actual instruction
   in the loop.  We use this to decide what is worth moving out.  */

/* last_set[n] is nonzero iff reg n has been set in the current basic block.
   In that case, it is the insn that last set reg n.  */

stati