cse.c

早期freebsd实现

	    break;

      if (q)
	break;

      p = p->related_value;

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

  if (q == 0)
    return 0;

  offset = (get_integer_term (x) - get_integer_term (p->exp));
  /* Note: OFFSET may be 0 if P->xexp and X are related by commutativity.  */
  return plus_constant (q->exp, offset);
}

/* 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.  */

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:
      {
	register int regno = REGNO (x);

	/* On some machines, we can't record any non-fixed hard register,
	   because extending its life will cause reload problems.  We
	   consider ap, fp, and sp to be fixed for this purpose.
	   On all machines, we can't record any global registers. */

	if (regno < FIRST_PSEUDO_REGISTER
	    && (global_regs[regno]
#ifdef SMALL_REGISTER_CLASSES
		|| (! fixed_regs[regno]
		    && regno != FRAME_POINTER_REGNUM
		    && regno != ARG_POINTER_REGNUM
		    && regno != STACK_POINTER_REGNUM)
#endif
		))
	  {
	    do_not_record = 1;
	    return 0;
	  }
	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 integers representing the constant.  */
      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 + ((HOST_WIDE_INT) LABEL_REF << 7)
	      + ((HOST_WIDE_INT) XEXP (x, 0) & ((1 << HASHBITS) - 1)));

    case SYMBOL_REF:
      return (hash + ((HOST_WIDE_INT) SYMBOL_REF << 7)
	      + ((HOST_WIDE_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;
      x = XEXP (x, 0);
      goto repeat;

    case PRE_DEC:
    case PRE_INC:
    case POST_DEC:
    case POST_INC:
    case PC:
    case CC0:
    case CALL:
    case UNSPEC_VOLATILE:
      do_not_record = 1;
      return 0;

    case ASM_OPERANDS:
      if (MEM_VOLATILE_P (x))
	{
	  do_not_record = 1;
	  return 0;
	}
    }

  i = GET_RTX_LENGTH (code) - 1;
  hash += (int) code + (int) GET_MODE (x);
  fmt = GET_RTX_FORMAT (code);
  for (; i >= 0; i--)
    {
      if (fmt[i] == 'e')
	{
	  rtx tem = XEXP (x, i);
	  rtx tem1;

	  /* If the operand is a REG that is equivalent to a constant, hash
	     as if we were hashing the constant, since we will be comparing
	     that way.  */
	  if (tem != 0 && GET_CODE (tem) == REG
	      && REGNO_QTY_VALID_P (REGNO (tem))
	      && qty_mode[reg_qty[REGNO (tem)]] == GET_MODE (tem)
	      && (tem1 = qty_const[reg_qty[REGNO (tem)]]) != 0
	      && CONSTANT_P (tem1))
	    tem = tem1;

	  /* If we are about to do the last recursive call
	     needed at this level, change it into iteration.
	     This function  is called enough to be worth it.  */
	  if (i == 0)
	    {
	      x = tem;
	      goto repeat;
	    }
	  hash += canon_hash (tem, 0);
	}
      else if (fmt[i] == 'E')
	for (j = 0; j < XVECLEN (x, i); j++)
	  hash += canon_hash (XVECEXP (x, i, j), 0);
      else if (fmt[i] == 's')
	{
	  register char *p = XSTR (x, i);
	  if (p)
	    while (*p)
	      {
		register int tem = *p++;
		hash += ((1 << HASHBITS) - 1) & (tem + (tem >> HASHBITS));
	      }
	}
      else if (fmt[i] == 'i')
	{
	  register int tem = XINT (x, i);
	  hash += ((1 << HASHBITS) - 1) & (tem + (tem >> HASHBITS));
	}
      else
	abort ();
    }
  return hash;
}

/* Like canon_hash but with no side effects.  */

static int
safe_hash (x, mode)
     rtx x;
     enum machine_mode mode;
{
  int save_do_not_record = do_not_record;
  int save_hash_arg_in_memory = hash_arg_in_memory;
  int save_hash_arg_in_struct = hash_arg_in_struct;
  int hash = canon_hash (x, mode);
  hash_arg_in_memory = save_hash_arg_in_memory;
  hash_arg_in_struct = save_hash_arg_in_struct;
  do_not_record = save_do_not_record;
  return hash;
}

/* Return 1 iff X and Y would canonicalize into the same thing,
   without actually constructing the canonicalization of either one.
   If VALIDATE is nonzero,
   we assume X is an expression being processed from the rtl
   and Y was found in the hash table.  We check register refs
   in Y for being marked as valid.

   If EQUAL_VALUES is nonzero, we allow a register to match a constant value
   that is known to be in the register.  Ordinarily, we don't allow them
   to match, because letting them match would cause unpredictable results
   in all the places that search a hash table chain for an equivalent
   for a given value.  A possible equivalent that has different structure
   has its hash code computed from different data.  Whether the hash code
   is the same as that of the the given value is pure luck.  */

static int
exp_equiv_p (x, y, validate, equal_values)
     rtx x, y;
     int validate;
     int equal_values;
{
  register int i, j;
  register enum rtx_code code;
  register char *fmt;

  /* Note: it is incorrect to assume an expression is equivalent to itself
     if VALIDATE is nonzero.  */
  if (x == y && !validate)
    return 1;
  if (x == 0 || y == 0)
    return x == y;

  code = GET_CODE (x);
  if (code != GET_CODE (y))
    {
      if (!equal_values)
	return 0;

      /* If X is a constant and Y is a register or vice versa, they may be
	 equivalent.  We only have to validate if Y is a register.  */
      if (CONSTANT_P (x) && GET_CODE (y) == REG
	  && REGNO_QTY_VALID_P (REGNO (y))
	  && GET_MODE (y) == qty_mode[reg_qty[REGNO (y)]]
	  && rtx_equal_p (x, qty_const[reg_qty[REGNO (y)]])
	  && (! validate || reg_in_table[REGNO (y)] == reg_tick[REGNO (y)]))
	return 1;

      if (CONSTANT_P (y) && code == REG
	  && REGNO_QTY_VALID_P (REGNO (x))
	  && GET_MODE (x) == qty_mode[reg_qty[REGNO (x)]]
	  && rtx_equal_p (y, qty_const[reg_qty[REGNO (x)]]))
	return 1;

      return 0;
    }

  /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.  */
  if (GET_MODE (x) != GET_MODE (y))
    return 0;

  switch (code)
    {
    case PC:
    case CC0:
      return x == y;

    case CONST_INT:
      return INTVAL (x) == INTVAL (y);

    case LABEL_REF:
    case SYMBOL_REF:
      return XEXP (x, 0) == XEXP (y, 0);

    case REG:
      {
	int regno = REGNO (y);
	int endregno
	  = regno + (regno >= FIRST_PSEUDO_REGISTER ? 1
		     : HARD_REGNO_NREGS (regno, GET_MODE (y)));
	int i;

	/* If the quantities are not the same, the expressions are not
	   equivalent.  If there are and we are not to validate, they
	   are equivalent.  Otherwise, ensure all regs are up-to-date.  */

	if (reg_qty[REGNO (x)] != reg_qty[regno])
	  return 0;

	if (! validate)
	  return 1;

	for (i = regno; i < endregno; i++)
	  if (reg_in_table[i] != reg_tick[i])
	    return 0;

	return 1;
      }

    /*  For commutative operations, check both orders.  */
    case PLUS:
    case MULT:
    case AND:
    case IOR:
    case XOR:
    case NE:
    case EQ:
      return ((exp_equiv_p (XEXP (x, 0), XEXP (y, 0), validate, equal_values)
	       && exp_equiv_p (XEXP (x, 1), XEXP (y, 1),
			       validate, equal_values))
	      || (exp_equiv_p (XEXP (x, 0), XEXP (y, 1),
			       validate, equal_values)
		  && exp_equiv_p (XEXP (x, 1), XEXP (y, 0),
				  validate, equal_values)));
    }

  /* 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 'e':
	  if (! exp_equiv_p (XEXP (x, i), XEXP (y, i), validate, equal_values))
	    return 0;
	  break;

	case 'E':
	  if (XVECLEN (x, i) != XVECLEN (y, i))
	    return 0;
	  for (j = 0; j < XVECLEN (x, i); j++)
	    if (! exp_equiv_p (XVECEXP (x, i, j), XVECEXP (y, i, j),
			       validate, equal_values))
	      return 0;
	  break;

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

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

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

	case '0':
	  break;

	default:
	  abort ();
	}
      }

  return 1;
}

/* Return 1 iff any subexpression of X matches Y.
   Here we do not require that X or Y be valid (for registers referred to)
   for being in the hash table.  */

int
refers_to_p (x, y)
     rtx x, y;
{
  register int i;
  register enum rtx_code code;
  register char *fmt;

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

  code = GET_CODE (x);
  /* If X as a whole has the same code as Y, they may match.
     If so, return 1.  */
  if (code == GET_CODE (y))
    {
      if (exp_equiv_p (x, y, 0, 1))
	return 1;
    }

  /* X does not match, so try its subexpressions.  */

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