cse.c

这是完整的gcc源代码

	 || uid_cuid[regno_first_uid[REGNO ((X)->exp)]] < cse_basic_block_start)	\
     && (uid_cuid[regno_last_uid[REGNO ((X)->exp)]]			\
	 > uid_cuid[regno_last_uid[REGNO ((Y)->exp)]])))

static struct table_elt *
insert (x, classp, hash, mode)
     register rtx x;
     register struct table_elt *classp;
     int hash;
     enum machine_mode mode;
{
  register struct table_elt *elt;

  /* Put an element for X into the right hash bucket.  */

  elt = get_element ();
  elt->exp = x;
  elt->cost = rtx_cost (x) * 2;
  /* Make pseudo regs a little cheaper than hard regs.  */
  if (GET_CODE (x) == REG && REGNO (x) >= FIRST_PSEUDO_REGISTER)
    elt->cost -= 1;
  elt->next_same_value = 0;
  elt->prev_same_value = 0;
  elt->next_same_hash = table[hash];
  elt->prev_same_hash = 0;
  elt->related_value = 0;
  elt->in_memory = 0;
  elt->equivalence_only = 0;
  elt->mode = mode;
  if (table[hash])
    table[hash]->prev_same_hash = elt;
  table[hash] = elt;

  /* Put it into the proper value-class.  */
  if (classp)
    {
      if (CHEAPER (elt, classp))
	/** Insert at the head of the class */
	{
	  register struct table_elt *p;
	  elt->next_same_value = classp;
	  classp->prev_same_value = elt;
	  elt->first_same_value = elt;

	  for (p = classp; p; p = p->next_same_value)
	    p->first_same_value = elt;
	}
      else
	{
	  /* Insert not at head of the class.  */
	  /* Put it after the last element cheaper than X.  */
	  register struct table_elt *p, *next;
	  for (p = classp; (next = p->next_same_value) && CHEAPER (next, elt);
	       p = next);
	  /* Put it after P and before NEXT.  */
	  elt->next_same_value = next;
	  if (next)
	    next->prev_same_value = elt;
	  elt->prev_same_value = p;
	  p->next_same_value = elt;
	  elt->first_same_value = classp;
	}
    }
  else
    elt->first_same_value = elt;

  if ((CONSTANT_P (x) || GET_CODE (x) == CONST_DOUBLE || FIXED_BASE_PLUS_P (x))
      && GET_CODE (elt->first_same_value->exp) == REG)
    {
      qty_const[reg_qty[REGNO (elt->first_same_value->exp)]] = x;
      qty_const_insn[reg_qty[REGNO (elt->first_same_value->exp)]] = this_insn;
    }

  if (GET_CODE (x) == REG)
    {
      if (elt->next_same_value != 0
	  && (CONSTANT_P (elt->next_same_value->exp)
	      || GET_CODE (elt->next_same_value->exp) == CONST_DOUBLE
	      || FIXED_BASE_PLUS_P (elt->next_same_value->exp)))
	{
	  qty_const[reg_qty[REGNO (x)]] = elt->next_same_value->exp;
	  qty_const_insn[reg_qty[REGNO (x)]] = this_insn;
	}
      if (CONSTANT_P (elt->first_same_value->exp)
	  || GET_CODE (elt->first_same_value->exp) == CONST_DOUBLE
	  || FIXED_BASE_PLUS_P (elt->first_same_value->exp))
	{
	  qty_const[reg_qty[REGNO (x)]] = elt->first_same_value->exp;
	  qty_const_insn[reg_qty[REGNO (x)]] = this_insn;
	}
    }

  /* If this is a constant with symbolic value,
     and it has a term with an explicit integer value,
     link it up with related expressions.  */
  if (GET_CODE (x) == CONST)
    {
      rtx subexp = get_related_value (x);
      int subhash;
      struct table_elt *subelt, *subelt_prev;

      if (subexp != 0)
	{
	  /* Get the integer-free subexpression in the hash table.  */
	  subhash = safe_hash (subexp, mode) % NBUCKETS;
	  subelt = lookup (subexp, subhash, mode);
	  if (subelt == 0)
	    subelt = insert (subexp, 0, subhash, mode);
	  /* Initialize SUBELT's circular chain if it has none.  */
	  if (subelt->related_value == 0)
	    subelt->related_value = subelt;
	  /* Find the element in the circular chain that precedes SUBELT.  */
	  subelt_prev = subelt;
	  while (subelt_prev->related_value != subelt)
	    subelt_prev = subelt_prev->related_value;
	  /* Put new ELT into SUBELT's circular chain just before SUBELT.
	     This way the element that follows SUBELT is the oldest one.  */
	  elt->related_value = subelt_prev->related_value;
	  subelt_prev->related_value = elt;
	}
    }

  return elt;
}

/* Remove from the hash table, or mark as invalid,
   all expressions whose values could be altered by storing in X.
   X is a register, a subreg, or a memory reference with nonvarying address
   (because, when a memory reference with a varying address is stored in,
   all memory references are removed by invalidate_memory
   so specific invalidation is superfluous).

   A nonvarying address may be just a register or just
   a symbol reference, or it may be either of those plus
   a numeric offset.  */

static void
invalidate (x)
     rtx x;
{
  register int i;
  register struct table_elt *p;
  register rtx base;
  register int start, end;

  /* If X is a register, dependencies on its contents
     are recorded through the qty number mechanism.
     Just change the qty number of the register,
     mark it as invalid for expressions that refer to it,
     and remove it itself.  */

  if (GET_CODE (x) == REG)
    {
      register int hash = HASH (x, 0);
      reg_invalidate (REGNO (x));
      remove (lookup_for_remove (x, hash, GET_MODE (x)), hash);
      return;
    }

  if (GET_CODE (x) == SUBREG)
    {
      if (GET_CODE (SUBREG_REG (x)) != REG)
	abort ();
      invalidate (SUBREG_REG (x));
      return;
    }

  /* X is not a register; it must be a memory reference with
     a nonvarying address.  Remove all hash table elements
     that refer to overlapping pieces of memory.  */

  if (GET_CODE (x) != MEM)
    abort ();
  base = XEXP (x, 0);
  start = 0;

  /* Registers with nonvarying addresses usually have constant equivalents;
     but the frame pointer register is also possible.  */
  if (GET_CODE (base) == REG
      && qty_const[reg_qty[REGNO (base)]] != 0)
    base = qty_const[reg_qty[REGNO (base)]];

  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 + GET_MODE_SIZE (GET_MODE (x));
  for (i = 0; i < NBUCKETS; i++)
    {
      register struct table_elt *next;
      for (p = table[i]; p; p = next)
	{
	  next = p->next_same_hash;
	  if (refers_to_mem_p (p->exp, base, start, end))
	    remove (p, i);
	}
    }
}

/* Remove all expressions that refer to register REGNO,
   since they are already invalid, and we are about to
   mark that register valid again and don't want the old
   expressions to reappear as valid.  */

static void
remove_invalid_refs (regno)
     int regno;
{
  register int i;
  register struct table_elt *p, *next;
  register rtx x = reg_rtx[regno];

  for (i = 0; i < NBUCKETS; i++)
    for (p = table[i]; p; p = next)
      {
	next = p->next_same_hash;
	if (GET_CODE (p->exp) != REG && refers_to_p (p->exp, x))
	  remove (p, i);
      }
}

/* Remove from the hash table all expressions that reference memory,
   or some of them as specified by *WRITES.  */

static void
invalidate_memory (writes)
     struct write_data *writes;
{
  register int i;
  register struct table_elt *p, *next;
  int all = writes->all;
  int nonscalar = writes->nonscalar;

  for (i = 0; i < NBUCKETS; i++)
    for (p = table[i]; p; p = next)
      {
	next = p->next_same_hash;
	if (p->in_memory
	    && (all
		|| (nonscalar && p->in_struct)
		|| cse_rtx_addr_varies_p (p->exp)))
	  remove (p, i);
      }
}

/* Return the value of the integer term in X, if one is apparent;
   otherwise return 0.
   We do not check extremely carefully for the presence of integer terms
   but rather consider only the cases that `insert' notices
   for the `related_value' field.  */

static int
get_integer_term (x)
     rtx x;
{
  if (GET_CODE (x) == CONST)
    x = XEXP (x, 0);

  if (GET_CODE (x) == MINUS
      && GET_CODE (XEXP (x, 1)) == CONST_INT)
    return - INTVAL (XEXP (x, 1));
  if (GET_CODE (x) != PLUS)
    return 0;
  if (GET_CODE (XEXP (x, 0)) == CONST_INT)
    return INTVAL (XEXP (x, 0));
  if (GET_CODE (XEXP (x, 1)) == CONST_INT)
    return INTVAL (XEXP (x, 1));
  return 0;
}

static rtx
get_related_value (x)
     rtx x;
{
  if (GET_CODE (x) != CONST)
    return 0;
  x = XEXP (x, 0);
  if (GET_CODE (x) == PLUS)
    {
      if (GET_CODE (XEXP (x, 0)) == CONST_INT)
	return XEXP (x, 1);
      if (GET_CODE (XEXP (x, 1)) == CONST_INT)
	return XEXP (x, 0);
    }
  else if (GET_CODE (x) == MINUS
	   && GET_CODE (XEXP (x, 1)) == CONST_INT)
    return XEXP (x, 0);
  return 0;
}

/* Given an expression X of type CONST,
   and ELT which is its table entry (or 0 if it
   is not in the hash table),
   return an alternate expression for X as a register plus integer.
   If none can be found or it would not be a valid address, return 0.  */

static rtx
use_related_value (x, elt)
     rtx x;
     struct table_elt *elt;
{
  register struct table_elt *relt = 0;
  register struct table_elt *p;
  int offset;
  rtx addr;

  /* First, is there anything related known?
     If we have a table element, we can tell from that.
     Otherwise, must look it up.  */

  if (elt != 0 && elt->related_value != 0)
    relt = elt;
  else if (elt == 0 && GET_CODE (x) == CONST)
    {
      rtx subexp = get_related_value (x);
      if (subexp != 0)
	relt = lookup (subexp,
		       safe_hash (subexp, GET_MODE (subexp)) % NBUCKETS,
		       GET_MODE (subexp));
    }

  if (relt == 0)
    return 0;

  /* Search all related table entries for one that has an
     equivalent register.  */

  p = relt;
  while (1)
    {
      if (p->first_same_value != 0
	  && GET_CODE (p->first_same_value->exp) == REG)
	break;
      p = p->related_value;

      /* We went all the way around, so there is nothing to be found.
	 Return failure.  */
      if (p == relt)
	return 0;
      /* Perhaps RELT was in the table for some other reason and
	 it has no related values recorded.  */
      if (p == 0)
	return 0;
    }

  /* Note: OFFSET may be 0 if P->xexp and X are related by commutativity.  */
  offset = (get_integer_term (x) - get_integer_term (p->exp));
  addr = plus_constant (p->first_same_value->exp, offset);
  if (memory_address_p (QImode, addr))
    return addr;
  return 0;
}

/* Hash an rtx.  We are careful to make sure the value is never negative.
   Equivalent registers hash identically.
   MODE is used in hashing for CONST_INTs only;
   otherwise the mode of X is used.

   Store 1 in do_not_record if any subexpression is volatile.

   Store 1 in hash_arg_in_memory if X contains a MEM rtx
   which does not have the RTX_UNCHANGING_P bit set.
   In this case, also store 1 in hash_arg_in_struct
   if there is a MEM rtx which has the MEM_IN_STRUCT_P bit set.

   Note that cse_insn knows that the hash code of a MEM expression
   is just (int) MEM plus the hash code of the address.  */

#define HASHBITS 16

static int
canon_hash (x, mode)
     rtx x;
     enum machine_mode mode;
{
  register int i, j;
  register int hash = 0;
  register enum rtx_code code;
  register char *fmt;

  /* repeat is used to turn tail-recursion into iteration.  */
 repeat:
  if (x == 0)
    return hash;

  code = GET_CODE (x);
  switch (code)
    {
    case REG:
      {
	/* We do not invalidate anything on pushing or popping
	   because they cannot change anything but the stack pointer;
	   but that means we must consider the stack pointer volatile
	   since it can be changed "mysteriously".  */

	register int regno = REGNO (x);
	if (regno == STACK_POINTER_REGNUM
	    || (regno < FIRST_PSEUDO_REGISTER && global_regs[regno]))
	  {
	    do_not_record = 1;
	    return 0;
	  }
#ifdef SMALL_REGISTER_CLASSES
	if (regno < FIRST_PSEUDO_REGISTER && regno != FRAME_POINTER_REGNUM
	    && regno != ARG_POINTER_REGNUM)
	  {
	    do_not_record = 1;
	    return 0;
	  }
#endif
	return hash + ((int) REG << 7) + reg_qty[regno];
      }

    case CONST_INT:
      hash += ((int) mode + ((int) CONST_INT << 7)
	       + INTVAL (x) + (INTVAL (x) >> HASHBITS));
      return ((1 << HASHBITS) - 1) & hash;

    case CONST_DOUBLE:
      /* This is like the general case, except that it only counts
	 the first two elements.  */
      hash += (int) code + (int) GET_MODE (x);
      {
	int i;
	for (i = 2; i < GET_RTX_LENGTH (CONST_DOUBLE); i++)
	  {
	    int tem = XINT (x, i);
	    hash += ((1 << HASHBITS) - 1) & (tem + (tem >> HASHBITS));
	  }
      }
      return hash;

      /* Assume there is only one rtx object for any given label.  */
    case LABEL_REF:
      /* Use `and' to ensure a positive number.  */
      return (hash + ((int) LABEL_REF << 7)
	      + ((int) XEXP (x, 0) & ((1 << HASHBITS) - 1)));

    case SYMBOL_REF:
      return (hash + ((int) SYMBOL_REF << 7)
	      + ((int) XEXP (x, 0) & ((1 << HASHBITS) - 1)));

    case MEM:
      if (MEM_VOLATILE_P (x))
	{
	  do_not_record = 1;
	  return 0;
	}
      if (! RTX_UNCHANGING_P (x))
	{
	  hash_arg_in_memory = 1;
	  if (MEM_IN_STRUCT_P (x)) hash_arg_in_struct = 1;
	}
      /* Now that we have already found this special case,
	 might as well speed it up as much as possible.  */
      hash += (int) MEM;