cse.c

GUN开源阻止下的编译器GCC

	  && exp_equiv_p (p->exp, p->exp, 1, 0))
	return p->exp;
    }
  
  return 0;
}

/* Insert X in the hash table, assuming HASH is its hash code
   and CLASSP is an element of the class it should go in
   (or 0 if a new class should be made).
   It is inserted at the proper position to keep the class in
   the order cheapest first.

   MODE is the machine-mode of X, or if X is an integer constant
   with VOIDmode then MODE is the mode with which X will be used.

   For elements of equal cheapness, the most recent one
   goes in front, except that the first element in the list
   remains first unless a cheaper element is added.  The order of
   pseudo-registers does not matter, as canon_reg will be called to
   find the cheapest when a register is retrieved from the table.

   The in_memory field in the hash table element is set to 0.
   The caller must set it nonzero if appropriate.

   You should call insert_regs (X, CLASSP, MODIFY) before calling here,
   and if insert_regs returns a nonzero value
   you must then recompute its hash code before calling here.

   If necessary, update table showing constant values of quantities.  */

#define CHEAPER(X,Y)   ((X)->cost < (Y)->cost)

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

  /* If X is a register and we haven't made a quantity for it,
     something is wrong.  */
  if (GET_CODE (x) == REG && ! REGNO_QTY_VALID_P (REGNO (x)))
    abort ();

  /* If X is a hard register, show it is being put in the table.  */
  if (GET_CODE (x) == REG && REGNO (x) < FIRST_PSEUDO_REGISTER)
    {
      int regno = REGNO (x);
      int endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (x));
      int i;

      for (i = regno; i < endregno; i++)
	    SET_HARD_REG_BIT (hard_regs_in_table, i);
    }

  /* If X is a label, show we recorded it.  */
  if (GET_CODE (x) == LABEL_REF
      || (GET_CODE (x) == CONST && GET_CODE (XEXP (x, 0)) == PLUS
	  && GET_CODE (XEXP (XEXP (x, 0), 0)) == LABEL_REF))
    recorded_label_ref = 1;

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

  elt = get_element ();
  elt->exp = x;
  elt->cost = COST (x);
  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->mode = mode;
  elt->is_const = (CONSTANT_P (x)
		   /* GNU C++ takes advantage of this for `this'
		      (and other const values).  */
		   || (RTX_UNCHANGING_P (x)
		       && GET_CODE (x) == REG
		       && REGNO (x) >= FIRST_PSEUDO_REGISTER)
		   || FIXED_BASE_PLUS_P (x));

  if (table[hash])
    table[hash]->prev_same_hash = elt;
  table[hash] = elt;

  /* Put it into the proper value-class.  */
  if (classp)
    {
      classp = classp->first_same_value;
      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 this is a constant being set equivalent to a register or a register
     being set equivalent to a constant, note the constant equivalence.

     If this is a constant, it cannot be equivalent to a different constant,
     and a constant is the only thing that can be cheaper than a register.  So
     we know the register is the head of the class (before the constant was
     inserted).

     If this is a register that is not already known equivalent to a
     constant, we must check the entire class.

     If this is a register that is already known equivalent to an insn,
     update `qty_const_insn' to show that `this_insn' is the latest
     insn making that quantity equivalent to the constant.  */

  if (elt->is_const && classp && GET_CODE (classp->exp) == REG
      && GET_CODE (x) != REG)
    {
      qty_const[reg_qty[REGNO (classp->exp)]]
	= gen_lowpart_if_possible (qty_mode[reg_qty[REGNO (classp->exp)]], x);
      qty_const_insn[reg_qty[REGNO (classp->exp)]] = this_insn;
    }

  else if (GET_CODE (x) == REG && classp && ! qty_const[reg_qty[REGNO (x)]]
	   && ! elt->is_const)
    {
      register struct table_elt *p;

      for (p = classp; p != 0; p = p->next_same_value)
	{
	  if (p->is_const && GET_CODE (p->exp) != REG)
	    {
	      qty_const[reg_qty[REGNO (x)]]
		= gen_lowpart_if_possible (GET_MODE (x), p->exp);
	      qty_const_insn[reg_qty[REGNO (x)]] = this_insn;
	      break;
	    }
	}
    }

  else if (GET_CODE (x) == REG && qty_const[reg_qty[REGNO (x)]]
	   && GET_MODE (x) == qty_mode[reg_qty[REGNO (x)]])
    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);
      unsigned 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)
    {
      unsigned 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))
	    {
	      rehash_using_reg (exp);
	      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).
   FULL_MODE, if not VOIDmode, indicates that this much should be invalidated
   instead of just the amount indicated by the mode of X.  This is only used
   for bitfield stores into memory.

   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, full_mode)
     rtx x;
     enum machine_mode full_mode;
{
  register int i;
  register struct table_elt *p;
  rtx base;
  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 unsigned 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)
	{
	  /* Because a register can be referenced in more than one mode,
	     we might have to remove more than one table entry.  */

	  struct table_elt *elt;

	  while (elt = lookup_for_remove (x, hash, GET_MODE (x)))
	    remove_from_table (elt, hash);
	}
      else
	{
	  HOST_WIDE_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), VOIDmode);
      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 ();

  if (full_mode == VOIDmode)
    full_mode = GET_MODE (x);

  set_nonvarying_address_components (XEXP (x, 0), GET_MODE_SIZE (full_mode),
				     &base, &start, &end);

  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.  */