cse.c

这是完整的gcc源代码

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

  return total;
}

/* Clear the hash table and initialize each register with its own quantity,
   for a new basic block.  */

static void
new_basic_block ()
{
  register int i;
  register int vecsize = max_reg * sizeof (rtx);
  next_qty = max_reg;

  bzero (reg_rtx, vecsize);
  bzero (reg_tick, vecsize);

  bcopy (all_minus_one, reg_in_table, vecsize);
  bcopy (all_minus_one, reg_next_eqv, vecsize);
  bcopy (all_minus_one, reg_prev_eqv, vecsize);
  bcopy (consec_ints, reg_qty, vecsize);

  for (i = 0; i < max_qty; i++)
    {
      qty_first_reg[i] = i;
      qty_last_reg[i] = i;
      qty_const[i] = 0;
      qty_const_insn[i] = 0;
    }

  for (i = 0; i < NBUCKETS; i++)
    {
      register struct table_elt *this, *next;
      for (this = table[i]; this; this = next)
	{
	  next = this->next_same_hash;
	  free_element (this);
	}
    }

  bzero (table, sizeof table);

  prev_insn_cc0 = 0;
  prev_insn_explicit_cc0 = 0;
  prev_insn = 0;
}

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

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

  q = reg_qty[reg] = next_qty++;
  qty_first_reg[q] = reg;
  qty_last_reg[q] = reg;
}

/* 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 (q == old)
    abort ();

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

  /* Prefer pseudo regs to hard regs with the same value.
     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 (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, insert at end.
	 Otherwise, insert before any hard regs that are at the end.  */
      while (lastr < FIRST_PSEUDO_REGISTER && 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;
    }
}

/* Discard the records of what is in register REG.  */

static void
reg_invalidate (reg)
     register int reg;
{
  register int n = reg_next_eqv[reg];
  register int p = reg_prev_eqv[reg];
  register int q = reg_qty[reg];

  reg_tick[reg]++;

  if (q == reg)
    {
      /* Save time if already invalid */
      /* It shouldn't be linked to anything if it's invalid.  */
      if (reg_prev_eqv[q] != -1)
	abort ();
      if (reg_next_eqv[q] != -1)
	abort ();
      return;
    }

  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;
  qty_first_reg[reg] = reg;
  qty_last_reg[reg] = reg;
  reg_next_eqv[reg] = -1;
  reg_prev_eqv[reg] = -1;
}

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

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

  if (x == 0)
    return;

  code = GET_CODE (x);
  if (code == REG)
    {
      register int regno = REGNO (x);
      reg_rtx[regno] = x;

      if (reg_in_table[regno] >= 0 && reg_in_table[regno] != reg_tick[regno])
	remove_invalid_refs (regno);

      reg_in_table[regno] = reg_tick[regno];

      return;
    }

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

/* Update the register quantities for inserting X into the hash table
   with a value equivalent to CLASSP.
   (If CLASSP is not a REG or a SUBREG, it is irrelevant.)
   If MODIFIED is nonzero, X is a destination; it is being modified.
   Note that reg_invalidate 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);
      reg_rtx[regno] = x;
      if (modified || reg_qty[regno] == regno)
	{
	  if (classp && GET_CODE (classp->exp) == REG)
	    {
	      make_regs_eqv (regno, REGNO (classp->exp));
	      /* Make sure reg_rtx is set up even for regs
		 not explicitly set (such as function value).  */
	      reg_rtx[REGNO (classp->exp)] = classp->exp;
	    }
	  else
	    make_new_qty (regno);
	  return 1;
	}
    }
  /* Copying a subreg into a subreg makes the regs equivalent,
     but only if the entire regs' mode is within one word.
     Copying one reg of a DImode into one reg of another DImode
     does not make them equivalent.  */
  else if (GET_CODE (x) == SUBREG
	   && GET_CODE (SUBREG_REG (x)) == REG
	   && GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))) <= UNITS_PER_WORD
	   && (modified
	       || reg_qty[REGNO (SUBREG_REG (x))] == REGNO (SUBREG_REG (x))))
    {
      if (classp && GET_CODE (classp->exp) == SUBREG
	  && GET_CODE (SUBREG_REG (classp->exp)) == REG
	  && GET_MODE (SUBREG_REG (classp->exp)) == GET_MODE (SUBREG_REG (x)))
	{
	  int oregno = REGNO (SUBREG_REG (classp->exp));
	  make_regs_eqv (REGNO (SUBREG_REG (x)), oregno);
	  /* Make sure reg_rtx is set up even for regs
	     not explicitly set (such as function value).  */
	  reg_rtx[oregno] = SUBREG_REG (classp->exp);
	}
      else
	make_new_qty (REGNO (SUBREG_REG (x)));
      return 1;
    }
  else
    mention_regs (x);
  return 0;
}

/* 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 (elt, hash)
     register struct table_elt *elt;
     int 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
      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;
     int 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 || exp_equiv_p (x, p->exp, 1)))
      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;
     int 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
    {
      for (p = table[hash]; p; p = p->next_same_hash)
	if (mode == p->mode && (x == p->exp || exp_equiv_p (x, p->exp, 0)))
	  return p;
    }

  return 0;
}

/* Look for an expression equivalent to X and with code CODE.
   If one is found, return that expression.  */

static rtx
lookup_as_function (x, code)
     rtx x;
     enum rtx_code code;
{
  register struct table_elt *p = lookup (x, safe_hash (x, 0) % NBUCKETS,
					 GET_MODE (x));
  if (p == 0)
    return 0;

  for (p = p->first_same_value; p; p = p->next_same_value)
    {
      if (GET_CODE (p->exp) == code
	  /* Make sure this is a valid entry in the table.  */
	  && (exp_equiv_p (XEXP (p->exp, 0), XEXP (p->exp, 0), 1)))
	return p->exp;
    }
  
  return 0;
}

/* Insert X in the hash table, assuming HASH is its hash code
   and CLASSP is the current first 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 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) ||						\
    ((X)->cost == (Y)->cost						\
     && GET_CODE ((X)->exp) == REG && GET_CODE ((Y)->exp) == REG	\
     && (uid_cuid[regno_last_uid[REGNO ((X)->exp)]] > cse_basic_block_end		\