cse.c

GCC编译器源代码

#endif
}

/* Say that register REG contains a quantity not in any register before
   and initialize that quantity.  */

static void
make_new_qty (reg)
     register int reg;
{
  register int q;

  if (next_qty >= max_qty)
    abort ();

  q = reg_qty[reg] = next_qty++;
  qty_first_reg[q] = reg;
  qty_last_reg[q] = reg;
  qty_const[q] = qty_const_insn[q] = 0;
  qty_comparison_code[q] = UNKNOWN;

  reg_next_eqv[reg] = reg_prev_eqv[reg] = -1;
}

/* Make reg NEW equivalent to reg OLD.
   OLD is not changing; NEW is.  */

static void
make_regs_eqv (new, old)
     register int new, old;
{
  register int lastr, firstr;
  register int q = reg_qty[old];

  /* Nothing should become eqv until it has a "non-invalid" qty number.  */
  if (! REGNO_QTY_VALID_P (old))
    abort ();

  reg_qty[new] = q;
  firstr = qty_first_reg[q];
  lastr = qty_last_reg[q];

  /* Prefer fixed hard registers to anything.  Prefer pseudo regs to other
     hard regs.  Among pseudos, if NEW will live longer than any other reg
     of the same qty, and that is beyond the current basic block,
     make it the new canonical replacement for this qty.  */
  if (! (firstr < FIRST_PSEUDO_REGISTER && FIXED_REGNO_P (firstr))
      /* Certain fixed registers might be of the class NO_REGS.  This means
	 that not only can they not be allocated by the compiler, but
	 they cannot be used in substitutions or canonicalizations
	 either.  */
      && (new >= FIRST_PSEUDO_REGISTER || REGNO_REG_CLASS (new) != NO_REGS)
      && ((new < FIRST_PSEUDO_REGISTER && FIXED_REGNO_P (new))
	  || (new >= FIRST_PSEUDO_REGISTER
	      && (firstr < FIRST_PSEUDO_REGISTER
		  || ((uid_cuid[REGNO_LAST_UID (new)] > cse_basic_block_end
		       || (uid_cuid[REGNO_FIRST_UID (new)]
			   < cse_basic_block_start))
		      && (uid_cuid[REGNO_LAST_UID (new)]
			  > uid_cuid[REGNO_LAST_UID (firstr)]))))))
    {
      reg_prev_eqv[firstr] = new;
      reg_next_eqv[new] = firstr;
      reg_prev_eqv[new] = -1;
      qty_first_reg[q] = new;
    }
  else
    {
      /* If NEW is a hard reg (known to be non-fixed), insert at end.
	 Otherwise, insert before any non-fixed hard regs that are at the
	 end.  Registers of class NO_REGS cannot be used as an
	 equivalent for anything.  */
      while (lastr < FIRST_PSEUDO_REGISTER && reg_prev_eqv[lastr] >= 0
	     && (REGNO_REG_CLASS (lastr) == NO_REGS || ! FIXED_REGNO_P (lastr))
	     && new >= FIRST_PSEUDO_REGISTER)
	lastr = reg_prev_eqv[lastr];
      reg_next_eqv[new] = reg_next_eqv[lastr];
      if (reg_next_eqv[lastr] >= 0)
	reg_prev_eqv[reg_next_eqv[lastr]] = new;
      else
	qty_last_reg[q] = new;
      reg_next_eqv[lastr] = new;
      reg_prev_eqv[new] = lastr;
    }
}

/* Remove REG from its equivalence class.  */

static void
delete_reg_equiv (reg)
     register int reg;
{
  register int q = reg_qty[reg];
  register int p, n;

  /* If invalid, do nothing.  */
  if (q == reg)
    return;

  p = reg_prev_eqv[reg];
  n = reg_next_eqv[reg];

  if (n != -1)
    reg_prev_eqv[n] = p;
  else
    qty_last_reg[q] = p;
  if (p != -1)
    reg_next_eqv[p] = n;
  else
    qty_first_reg[q] = n;

  reg_qty[reg] = reg;
}

/* Remove any invalid expressions from the hash table
   that refer to any of the registers contained in expression X.

   Make sure that newly inserted references to those registers
   as subexpressions will be considered valid.

   mention_regs is not called when a register itself
   is being stored in the table.

   Return 1 if we have done something that may have changed the hash code
   of X.  */

static int
mention_regs (x)
     rtx x;
{
  register enum rtx_code code;
  register int i, j;
  register char *fmt;
  register int changed = 0;

  if (x == 0)
    return 0;

  code = GET_CODE (x);
  if (code == REG)
    {
      register int regno = REGNO (x);
      register int endregno
	= regno + (regno >= FIRST_PSEUDO_REGISTER ? 1
		   : HARD_REGNO_NREGS (regno, GET_MODE (x)));
      int i;

      for (i = regno; i < endregno; i++)
	{
	  if (reg_in_table[i] >= 0 && reg_in_table[i] != reg_tick[i])
	    remove_invalid_refs (i);

	  reg_in_table[i] = reg_tick[i];
	}

      return 0;
    }

  /* If X is a comparison or a COMPARE and either operand is a register
     that does not have a quantity, give it one.  This is so that a later
     call to record_jump_equiv won't cause X to be assigned a different
     hash code and not found in the table after that call.

     It is not necessary to do this here, since rehash_using_reg can
     fix up the table later, but doing this here eliminates the need to
     call that expensive function in the most common case where the only
     use of the register is in the comparison.  */

  if (code == COMPARE || GET_RTX_CLASS (code) == '<')
    {
      if (GET_CODE (XEXP (x, 0)) == REG
	  && ! REGNO_QTY_VALID_P (REGNO (XEXP (x, 0))))
	if (insert_regs (XEXP (x, 0), NULL_PTR, 0))
	  {
	    rehash_using_reg (XEXP (x, 0));
	    changed = 1;
	  }

      if (GET_CODE (XEXP (x, 1)) == REG
	  && ! REGNO_QTY_VALID_P (REGNO (XEXP (x, 1))))
	if (insert_regs (XEXP (x, 1), NULL_PTR, 0))
	  {
	    rehash_using_reg (XEXP (x, 1));
	    changed = 1;
	  }
    }

  fmt = GET_RTX_FORMAT (code);
  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
    if (fmt[i] == 'e')
      changed |= mention_regs (XEXP (x, i));
    else if (fmt[i] == 'E')
      for (j = 0; j < XVECLEN (x, i); j++)
	changed |= mention_regs (XVECEXP (x, i, j));

  return changed;
}

/* Update the register quantities for inserting X into the hash table
   with a value equivalent to CLASSP.
   (If the class does not contain a REG, it is irrelevant.)
   If MODIFIED is nonzero, X is a destination; it is being modified.
   Note that delete_reg_equiv should be called on a register
   before insert_regs is done on that register with MODIFIED != 0.

   Nonzero value means that elements of reg_qty have changed
   so X's hash code may be different.  */

static int
insert_regs (x, classp, modified)
     rtx x;
     struct table_elt *classp;
     int modified;
{
  if (GET_CODE (x) == REG)
    {
      register int regno = REGNO (x);

      /* If REGNO is in the equivalence table already but is of the
	 wrong mode for that equivalence, don't do anything here.  */

      if (REGNO_QTY_VALID_P (regno)
	  && qty_mode[reg_qty[regno]] != GET_MODE (x))
	return 0;

      if (modified || ! REGNO_QTY_VALID_P (regno))
	{
	  if (classp)
	    for (classp = classp->first_same_value;
		 classp != 0;
		 classp = classp->next_same_value)
	      if (GET_CODE (classp->exp) == REG
		  && GET_MODE (classp->exp) == GET_MODE (x))
		{
		  make_regs_eqv (regno, REGNO (classp->exp));
		  return 1;
		}

	  make_new_qty (regno);
	  qty_mode[reg_qty[regno]] = GET_MODE (x);
	  return 1;
	}

      return 0;
    }

  /* If X is a SUBREG, we will likely be inserting the inner register in the
     table.  If that register doesn't have an assigned quantity number at
     this point but does later, the insertion that we will be doing now will
     not be accessible because its hash code will have changed.  So assign
     a quantity number now.  */

  else if (GET_CODE (x) == SUBREG && GET_CODE (SUBREG_REG (x)) == REG
	   && ! REGNO_QTY_VALID_P (REGNO (SUBREG_REG (x))))
    {
      insert_regs (SUBREG_REG (x), NULL_PTR, 0);
      mention_regs (SUBREG_REG (x));
      return 1;
    }
  else
    return mention_regs (x);
}

/* Look in or update the hash table.  */

/* Put the element ELT on the list of free elements.  */

static void
free_element (elt)
     struct table_elt *elt;
{
  elt->next_same_hash = free_element_chain;
  free_element_chain = elt;
}

/* Return an element that is free for use.  */

static struct table_elt *
get_element ()
{
  struct table_elt *elt = free_element_chain;
  if (elt)
    {
      free_element_chain = elt->next_same_hash;
      return elt;
    }
  n_elements_made++;
  return (struct table_elt *) oballoc (sizeof (struct table_elt));
}

/* Remove table element ELT from use in the table.
   HASH is its hash code, made using the HASH macro.
   It's an argument because often that is known in advance
   and we save much time not recomputing it.  */

static void
remove_from_table (elt, hash)
     register struct table_elt *elt;
     unsigned hash;
{
  if (elt == 0)
    return;

  /* Mark this element as removed.  See cse_insn.  */
  elt->first_same_value = 0;

  /* Remove the table element from its equivalence class.  */
     
  {
    register struct table_elt *prev = elt->prev_same_value;
    register struct table_elt *next = elt->next_same_value;

    if (next) next->prev_same_value = prev;

    if (prev)
      prev->next_same_value = next;
    else
      {
	register struct table_elt *newfirst = next;
	while (next)
	  {
	    next->first_same_value = newfirst;
	    next = next->next_same_value;
	  }
      }
  }

  /* Remove the table element from its hash bucket.  */

  {
    register struct table_elt *prev = elt->prev_same_hash;
    register struct table_elt *next = elt->next_same_hash;

    if (next) next->prev_same_hash = prev;

    if (prev)
      prev->next_same_hash = next;
    else if (table[hash] == elt)
      table[hash] = next;
    else
      {
	/* This entry is not in the proper hash bucket.  This can happen
	   when two classes were merged by `merge_equiv_classes'.  Search
	   for the hash bucket that it heads.  This happens only very
	   rarely, so the cost is acceptable.  */
	for (hash = 0; hash < NBUCKETS; hash++)
	  if (table[hash] == elt)
	    table[hash] = next;
      }
  }

  /* Remove the table element from its related-value circular chain.  */

  if (elt->related_value != 0 && elt->related_value != elt)
    {
      register struct table_elt *p = elt->related_value;
      while (p->related_value != elt)
	p = p->related_value;
      p->related_value = elt->related_value;
      if (p->related_value == p)
	p->related_value = 0;
    }

  free_element (elt);
}

/* Look up X in the hash table and return its table element,
   or 0 if X is not in the table.

   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.

   Here we are satisfied to find an expression whose tree structure
   looks like X.  */

static struct table_elt *
lookup (x, hash, mode)
     rtx x;
     unsigned hash;
     enum machine_mode mode;
{
  register struct table_elt *p;

  for (p = table[hash]; p; p = p->next_same_hash)
    if (mode == p->mode && ((x == p->exp && GET_CODE (x) == REG)
			    || exp_equiv_p (x, p->exp, GET_CODE (x) != REG, 0)))
      return p;

  return 0;
}

/* Like `lookup' but don't care whether the table element uses invalid regs.
   Also ignore discrepancies in the machine mode of a register.  */

static struct table_elt *
lookup_for_remove (x, hash, mode)
     rtx x;
     unsigned hash;
     enum machine_mode mode;
{
  register struct table_elt *p;

  if (GET_CODE (x) == REG)
    {
      int regno = REGNO (x);
      /* Don't check the machine mode when comparing registers;
	 invalidating (REG:SI 0) also invalidates (REG:DF 0).  */
      for (p = table[hash]; p; p = p->next_same_hash)
	if (GET_CODE (p->exp) == REG
	    && REGNO (p->exp) == regno)
	  return p;
    }
  else
    {