cse.c

早期freebsd实现

  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, NULL_PTR, 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;
}

/* Given two equivalence classes, CLASS1 and CLASS2, put all the entries from
   CLASS2 into CLASS1.  This is done when we have reached an insn which makes
   the two classes equivalent.

   CLASS1 will be the surviving class; CLASS2 should not be used after this
   call.

   Any invalid entries in CLASS2 will not be copied.  */

static void
merge_equiv_classes (class1, class2)
     struct table_elt *class1, *class2;
{
  struct table_elt *elt, *next, *new;

  /* Ensure we start with the head of the classes.  */
  class1 = class1->first_same_value;
  class2 = class2->first_same_value;

  /* If they were already equal, forget it.  */
  if (class1 == class2)
    return;

  for (elt = class2; elt; elt = next)
    {
      int hash;
      rtx exp = elt->exp;
      enum machine_mode mode = elt->mode;

      next = elt->next_same_value;

      /* Remove old entry, make a new one in CLASS1's class.
	 Don't do this for invalid entries as we cannot find their
	 hash code (it also isn't necessary). */
      if (GET_CODE (exp) == REG || exp_equiv_p (exp, exp, 1, 0))
	{
	  hash_arg_in_memory = 0;
	  hash_arg_in_struct = 0;
	  hash = HASH (exp, mode);
	      
	  if (GET_CODE (exp) == REG)
	    delete_reg_equiv (REGNO (exp));
	      
	  remove_from_table (elt, hash);

	  if (insert_regs (exp, class1, 0))
	    hash = HASH (exp, mode);
	  new = insert (exp, class1, hash, mode);
	  new->in_memory = hash_arg_in_memory;
	  new->in_struct = hash_arg_in_struct;
	}
    }
}

/* 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 HOST_WIDE_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 regno = REGNO (x);
      register int hash = HASH (x, GET_MODE (x));

      /* Remove REGNO from any quantity list it might be on and indicate
	 that it's value might have changed.  If it is a pseudo, remove its
	 entry from the hash table.

	 For a hard register, we do the first two actions above for any
	 additional hard registers corresponding to X.  Then, if any of these
	 registers are in the table, we must remove any REG entries that
	 overlap these registers.  */

      delete_reg_equiv (regno);
      reg_tick[regno]++;

      if (regno >= FIRST_PSEUDO_REGISTER)
	remove_from_table (lookup_for_remove (x, hash, GET_MODE (x)), hash);
      else
	{
	  int in_table = TEST_HARD_REG_BIT (hard_regs_in_table, regno);
	  int endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (x));
	  int tregno, tendregno;
	  register struct table_elt *p, *next;

	  CLEAR_HARD_REG_BIT (hard_regs_in_table, regno);

	  for (i = regno + 1; i < endregno; i++)
	    {
	      in_table |= TEST_HARD_REG_BIT (hard_regs_in_table, i);
	      CLEAR_HARD_REG_BIT (hard_regs_in_table, i);
	      delete_reg_equiv (i);
	      reg_tick[i]++;
	    }

	  if (in_table)
	    for (hash = 0; hash < NBUCKETS; hash++)
	      for (p = table[hash]; p; p = next)
		{
		  next = p->next_same_hash;

		  if (GET_CODE (p->exp) != REG
		      || REGNO (p->exp) >= FIRST_PSEUDO_REGISTER)
		    continue;

		  tregno = REGNO (p->exp);
		  tendregno
		    = tregno + HARD_REGNO_NREGS (tregno, GET_MODE (p->exp));
		  if (tendregno > regno && tregno < endregno)
		  remove_from_table (p, 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
      && REGNO_QTY_VALID_P (REGNO (base))
      && qty_mode[reg_qty[REGNO (base)]] == GET_MODE (base)
      && qty_const[reg_qty[REGNO (base)]] != 0)
    base = qty_const[reg_qty[REGNO (base)]];
  else if (GET_CODE (base) == PLUS
	   && GET_CODE (XEXP (base, 1)) == CONST_INT
	   && GET_CODE (XEXP (base, 0)) == REG
	   && REGNO_QTY_VALID_P (REGNO (XEXP (base, 0)))
	   && (qty_mode[reg_qty[REGNO (XEXP (base, 0))]]
	       == GET_MODE (XEXP (base, 0)))
	   && qty_const[reg_qty[REGNO (XEXP (base, 0))]])
    {
      start = INTVAL (XEXP (base, 1));
      base = qty_const[reg_qty[REGNO (XEXP (base, 0))]];
    }

  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_from_table (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;

  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_regno_p (regno, regno + 1, p->exp, NULL_PTR))
	  remove_from_table (p, i);
      }
}

/* Recompute the hash codes of any valid entries in the hash table that
   reference X, if X is a register, or SUBREG_REG (X) if X is a SUBREG.

   This is called when we make a jump equivalence.  */

static void
rehash_using_reg (x)
     rtx x;
{
  int i;
  struct table_elt *p, *next;
  int hash;

  if (GET_CODE (x) == SUBREG)
    x = SUBREG_REG (x);

  /* If X is not a register or if the register is known not to be in any
     valid entries in the table, we have no work to do.  */

  if (GET_CODE (x) != REG
      || reg_in_table[REGNO (x)] < 0
      || reg_in_table[REGNO (x)] != reg_tick[REGNO (x)])
    return;

  /* Scan all hash chains looking for valid entries that mention X.
     If we find one and it is in the wrong hash chain, move it.  We can skip
     objects that are registers, since they are handled specially.  */

  for (i = 0; i < NBUCKETS; i++)
    for (p = table[i]; p; p = next)
      {
	next = p->next_same_hash;
	if (GET_CODE (p->exp) != REG && reg_mentioned_p (x, p->exp)
	    && exp_equiv_p (p->exp, p->exp, 1, 0)
	    && i != (hash = safe_hash (p->exp, p->mode) % NBUCKETS))
	  {
	    if (p->next_same_hash)
	      p->next_same_hash->prev_same_hash = p->prev_same_hash;

	    if (p->prev_same_hash)
	      p->prev_same_hash->next_same_hash = p->next_same_hash;
	    else
	      table[i] = p->next_same_hash;

	    p->next_same_hash = table[hash];
	    p->prev_same_hash = 0;
	    if (table[hash])
	      table[hash]->prev_same_hash = p;
	    table[hash] = p;
	  }
      }
}

/* 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_from_table (p, i);
      }
}

/* Remove from the hash table any expression that is a call-clobbered
   register.  Also update their TICK values.  */

static void
invalidate_for_call ()
{
  int regno, endregno;
  int i;
  int hash;
  struct table_elt *p, *next;
  int in_table = 0;

  /* Go through all the hard registers.  For each that is clobbered in
     a CALL_INSN, remove the register from quantity chains and update
     reg_tick if defined.  Also see if any of these registers is currently
     in the table.  */

  for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
    if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
      {
	delete_reg_equiv (regno);
	if (reg_tick[regno] >= 0)
	  reg_tick[regno]++;

	in_table |= TEST_HARD_REG_BIT (hard_regs_in_table, regno);
      }

  /* In the case where we have no call-clobbered hard registers in the
     table, we are done.  Otherwise, scan the table and remove any
     entry that overlaps a call-clobbered register.  */

  if (in_table)
    for (hash = 0; hash < NBUCKETS; hash++)
      for (p = table[hash]; p; p = next)
	{
	  next = p->next_same_hash;

	  if (GET_CODE (p->exp) != REG
	      || REGNO (p->exp) >= FIRST_PSEUDO_REGISTER)
	    continue;

	  regno = REGNO (p->exp);
	  endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (p->exp));

	  for (i = regno; i < endregno; i++)
	    if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
	      {
		remove_from_table (p, hash);
		break;
	      }
	}
}

/* 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, 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, *q;
  HOST_WIDE_INT offset;

  /* 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)
    {
      /* This loop is strange in that it is executed in two different cases.
	 The first is when X is already in the table.  Then it is searching
	 the RELATED_VALUE list of X's class (RELT).  The second case is when
	 X is not in the table.  Then RELT points to a class for the related
	 value.

	 Ensure that, whatever case we are in, that we ignore classes that have
	 the same value as X.  */

      if (rtx_equal_p (x, p->exp))
	q = 0;
      else
	for (q = p->first_same_value; q; q = q->next_same_value)
	  if (GET_CODE (q->exp) == REG)