cse.c

GCC编译器源代码

   The `mode' field is usually the same as GET_MODE (`exp'), but
   if `exp' is a CONST_INT and has no machine mode then the `mode'
   field is the mode it was being used as.  Each constant is
   recorded separately for each mode it is used with.  */


struct table_elt
{
  rtx exp;
  struct table_elt *next_same_hash;
  struct table_elt *prev_same_hash;
  struct table_elt *next_same_value;
  struct table_elt *prev_same_value;
  struct table_elt *first_same_value;
  struct table_elt *related_value;
  int cost;
  enum machine_mode mode;
  char in_memory;
  char in_struct;
  char is_const;
  char flag;
};

/* We don't want a lot of buckets, because we rarely have very many
   things stored in the hash table, and a lot of buckets slows
   down a lot of loops that happen frequently.  */
#define NBUCKETS 31

/* Compute hash code of X in mode M.  Special-case case where X is a pseudo
   register (hard registers may require `do_not_record' to be set).  */

#define HASH(X, M)	\
 (GET_CODE (X) == REG && REGNO (X) >= FIRST_PSEUDO_REGISTER	\
  ? (((unsigned) REG << 7) + (unsigned) reg_qty[REGNO (X)]) % NBUCKETS	\
  : canon_hash (X, M) % NBUCKETS)

/* Determine whether register number N is considered a fixed register for CSE.
   It is desirable to replace other regs with fixed regs, to reduce need for
   non-fixed hard regs.
   A reg wins if it is either the frame pointer or designated as fixed,
   but not if it is an overlapping register.  */
#ifdef OVERLAPPING_REGNO_P
#define FIXED_REGNO_P(N)  \
  (((N) == FRAME_POINTER_REGNUM || (N) == HARD_FRAME_POINTER_REGNUM \
    || fixed_regs[N] || global_regs[N])	  \
   && ! OVERLAPPING_REGNO_P ((N)))
#else
#define FIXED_REGNO_P(N)  \
  ((N) == FRAME_POINTER_REGNUM || (N) == HARD_FRAME_POINTER_REGNUM \
   || fixed_regs[N] || global_regs[N])
#endif

/* Compute cost of X, as stored in the `cost' field of a table_elt.  Fixed
   hard registers and pointers into the frame are the cheapest with a cost
   of 0.  Next come pseudos with a cost of one and other hard registers with
   a cost of 2.  Aside from these special cases, call `rtx_cost'.  */

#define CHEAP_REGNO(N) \
  ((N) == FRAME_POINTER_REGNUM || (N) == HARD_FRAME_POINTER_REGNUM 	\
   || (N) == STACK_POINTER_REGNUM || (N) == ARG_POINTER_REGNUM	     	\
   || ((N) >= FIRST_VIRTUAL_REGISTER && (N) <= LAST_VIRTUAL_REGISTER) 	\
   || ((N) < FIRST_PSEUDO_REGISTER					\
       && FIXED_REGNO_P (N) && REGNO_REG_CLASS (N) != NO_REGS))

/* A register is cheap if it is a user variable assigned to the register
   or if its register number always corresponds to a cheap register.  */

#define CHEAP_REG(N) \
  ((REG_USERVAR_P (N) && REGNO (N) < FIRST_PSEUDO_REGISTER)	\
   || CHEAP_REGNO (REGNO (N)))

#define COST(X)								\
  (GET_CODE (X) == REG							\
   ? (CHEAP_REG (X) ? 0							\
      : REGNO (X) >= FIRST_PSEUDO_REGISTER ? 1				\
      : 2)								\
   : notreg_cost(X))

/* Determine if the quantity number for register X represents a valid index
   into the `qty_...' variables.  */

#define REGNO_QTY_VALID_P(N) (reg_qty[N] != (N))

static struct table_elt *table[NBUCKETS];

/* Chain of `struct table_elt's made so far for this function
   but currently removed from the table.  */

static struct table_elt *free_element_chain;

/* Number of `struct table_elt' structures made so far for this function.  */

static int n_elements_made;

/* Maximum value `n_elements_made' has had so far in this compilation
   for functions previously processed.  */

static int max_elements_made;

/* Surviving equivalence class when two equivalence classes are merged 
   by recording the effects of a jump in the last insn.  Zero if the
   last insn was not a conditional jump.  */

static struct table_elt *last_jump_equiv_class;

/* Set to the cost of a constant pool reference if one was found for a
   symbolic constant.  If this was found, it means we should try to
   convert constants into constant pool entries if they don't fit in
   the insn.  */

static int constant_pool_entries_cost;

/* Bits describing what kind of values in memory must be invalidated
   for a particular instruction.  If all three bits are zero,
   no memory refs need to be invalidated.  Each bit is more powerful
   than the preceding ones, and if a bit is set then the preceding
   bits are also set.

   Here is how the bits are set:
   Pushing onto the stack invalidates only the stack pointer,
   writing at a fixed address invalidates only variable addresses,
   writing in a structure element at variable address
     invalidates all but scalar variables,
   and writing in anything else at variable address invalidates everything.  */

struct write_data
{
  int sp : 1;			/* Invalidate stack pointer.  */
  int var : 1;			/* Invalidate variable addresses.  */
  int nonscalar : 1;		/* Invalidate all but scalar variables.  */
  int all : 1;			/* Invalidate all memory refs.  */
};

/* Define maximum length of a branch path.  */

#define PATHLENGTH	10

/* This data describes a block that will be processed by cse_basic_block.  */

struct cse_basic_block_data {
  /* Lowest CUID value of insns in block.  */
  int low_cuid;
  /* Highest CUID value of insns in block.  */
  int high_cuid;
  /* Total number of SETs in block.  */
  int nsets;
  /* Last insn in the block.  */
  rtx last;
  /* Size of current branch path, if any.  */
  int path_size;
  /* Current branch path, indicating which branches will be taken.  */
  struct branch_path {
    /* The branch insn.  */
    rtx branch;
    /* Whether it should be taken or not.  AROUND is the same as taken
       except that it is used when the destination label is not preceded
       by a BARRIER.  */
    enum taken {TAKEN, NOT_TAKEN, AROUND} status;
  } path[PATHLENGTH];
};

/* Nonzero if X has the form (PLUS frame-pointer integer).  We check for
   virtual regs here because the simplify_*_operation routines are called
   by integrate.c, which is called before virtual register instantiation.  */

#define FIXED_BASE_PLUS_P(X)					\
  ((X) == frame_pointer_rtx || (X) == hard_frame_pointer_rtx	\
   || (X) == arg_pointer_rtx					\
   || (X) == virtual_stack_vars_rtx				\
   || (X) == virtual_incoming_args_rtx				\
   || (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 1)) == CONST_INT \
       && (XEXP (X, 0) == frame_pointer_rtx			\
	   || XEXP (X, 0) == hard_frame_pointer_rtx		\
	   || XEXP (X, 0) == arg_pointer_rtx			\
	   || XEXP (X, 0) == virtual_stack_vars_rtx		\
	   || XEXP (X, 0) == virtual_incoming_args_rtx))	\
   || GET_CODE (X) == ADDRESSOF)

/* Similar, but also allows reference to the stack pointer.

   This used to include FIXED_BASE_PLUS_P, however, we can't assume that
   arg_pointer_rtx by itself is nonzero, because on at least one machine,
   the i960, the arg pointer is zero when it is unused.  */

#define NONZERO_BASE_PLUS_P(X)					\
  ((X) == frame_pointer_rtx || (X) == hard_frame_pointer_rtx	\
   || (X) == virtual_stack_vars_rtx				\
   || (X) == virtual_incoming_args_rtx				\
   || (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 1)) == CONST_INT \
       && (XEXP (X, 0) == frame_pointer_rtx			\
	   || XEXP (X, 0) == hard_frame_pointer_rtx		\
	   || XEXP (X, 0) == arg_pointer_rtx			\
	   || XEXP (X, 0) == virtual_stack_vars_rtx		\
	   || XEXP (X, 0) == virtual_incoming_args_rtx))	\
   || (X) == stack_pointer_rtx					\
   || (X) == virtual_stack_dynamic_rtx				\
   || (X) == virtual_outgoing_args_rtx				\
   || (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 1)) == CONST_INT \
       && (XEXP (X, 0) == stack_pointer_rtx			\
	   || XEXP (X, 0) == virtual_stack_dynamic_rtx		\
	   || XEXP (X, 0) == virtual_outgoing_args_rtx))	\
   || GET_CODE (X) == ADDRESSOF)

static int notreg_cost		PROTO((rtx));
static void new_basic_block	PROTO((void));
static void make_new_qty	PROTO((int));
static void make_regs_eqv	PROTO((int, int));
static void delete_reg_equiv	PROTO((int));
static int mention_regs		PROTO((rtx));
static int insert_regs		PROTO((rtx, struct table_elt *, int));
static void free_element	PROTO((struct table_elt *));
static void remove_from_table	PROTO((struct table_elt *, unsigned));
static struct table_elt *get_element PROTO((void));
static struct table_elt *lookup	PROTO((rtx, unsigned, enum machine_mode)),
       *lookup_for_remove PROTO((rtx, unsigned, enum machine_mode));
static rtx lookup_as_function	PROTO((rtx, enum rtx_code));
static struct table_elt *insert PROTO((rtx, struct table_elt *, unsigned,
				       enum machine_mode));
static void merge_equiv_classes PROTO((struct table_elt *,
				       struct table_elt *));
static void invalidate		PROTO((rtx, enum machine_mode));
static void remove_invalid_refs	PROTO((int));
static void rehash_using_reg	PROTO((rtx));
static void invalidate_memory	PROTO((struct write_data *));
static void invalidate_for_call	PROTO((void));
static rtx use_related_value	PROTO((rtx, struct table_elt *));
static unsigned canon_hash	PROTO((rtx, enum machine_mode));
static unsigned safe_hash	PROTO((rtx, enum machine_mode));
static int exp_equiv_p		PROTO((rtx, rtx, int, int));
static void set_nonvarying_address_components PROTO((rtx, int, rtx *,
						     HOST_WIDE_INT *,
						     HOST_WIDE_INT *));
static int refers_to_p		PROTO((rtx, rtx));
static int refers_to_mem_p	PROTO((rtx, rtx, HOST_WIDE_INT,
				       HOST_WIDE_INT));
static int cse_rtx_addr_varies_p PROTO((rtx));
static rtx canon_reg		PROTO((rtx, rtx));
static void find_best_addr	PROTO((rtx, rtx *));
static enum rtx_code find_comparison_args PROTO((enum rtx_code, rtx *, rtx *,
						 enum machine_mode *,
						 enum machine_mode *));
static rtx cse_gen_binary	PROTO((enum rtx_code, enum machine_mode,
				       rtx, rtx));
static rtx simplify_plus_minus	PROTO((enum rtx_code, enum machine_mode,
				       rtx, rtx));
static rtx fold_rtx		PROTO((rtx, rtx));
static rtx equiv_constant	PROTO((rtx));
static void record_jump_equiv	PROTO((rtx, int));
static void record_jump_cond	PROTO((enum rtx_code, enum machine_mode,
				       rtx, rtx, int));
static void cse_insn		PROTO((rtx, int));
static void note_mem_written	PROTO((rtx, struct write_data *));
static void invalidate_from_clobbers PROTO((struct write_data *, rtx));
static rtx cse_process_notes	PROTO((rtx, rtx));
static void cse_around_loop	PROTO((rtx));
static void invalidate_skipped_set PROTO((rtx, rtx));
static void invalidate_skipped_block PROTO((rtx));
static void cse_check_loop_start PROTO((rtx, rtx));
static void cse_set_around_loop	PROTO((rtx, rtx, rtx));
static rtx cse_basic_block	PROTO((rtx, rtx, struct branch_path *, int));
static void count_reg_usage	PROTO((rtx, int *, rtx, int));

extern int rtx_equal_function_value_matters;

/* Return an estimate of the cost of computing rtx X.
   One use is in cse, to decide which expression to keep in the hash table.
   Another is in rtl generation, to pick the cheapest way to multiply.
   Other uses like the latter are expected in the future.  */

/* Internal function, to compute cost when X is not a register; called
   from COST macro to keep it simple.  */

static int
notreg_cost (x)
     rtx x;
{
  return ((GET_CODE (x) == SUBREG
	   && GET_CODE (SUBREG_REG (x)) == REG
	   && GET_MODE_CLASS (GET_MODE (x)) == MODE_INT
	   && GET_MODE_CLASS (GET_MODE (SUBREG_REG (x))) == MODE_INT
	   && (GET_MODE_SIZE (GET_MODE (x))
	       < GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
	   && subreg_lowpart_p (x)
	   && TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (GET_MODE (x)),
				     GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x)))))
	  ? (CHEAP_REG (SUBREG_REG (x)) ? 0
	     : (REGNO (SUBREG_REG (x)) >= FIRST_PSEUDO_REGISTER ? 1
		: 2))
	  : rtx_cost (x, SET) * 2);
}

/* Return the right cost to give to an operation
   to make the cost of the corresponding register-to-register instruction
   N times that of a fast register-to-register instruction.  */

#define COSTS_N_INSNS(N) ((N) * 4 - 2)

int
rtx_cost (x, outer_code)
     rtx x;
     enum rtx_code outer_code;
{
  register int i, j;
  register enum rtx_code code;
  register char *fmt;
  register int total;

  if (x == 0)
    return 0;

  /* Compute the default costs of certain things.
     Note that RTX_COSTS can override the defaults.  */

  code = GET_CODE (x);
  switch (code)
    {
    case MULT:
      /* Count multiplication by 2**n as a shift,
	 because if we are considering it, we would output it as a shift.  */
      if (GET_CODE (XEXP (x, 1)) == CONST_INT
	  && exact_log2 (INTVAL (XEXP (x, 1))) >= 0)
	total = 2;
      else
	total = COSTS_N_INSNS (5);
      break;
    case DIV:
    case UDIV:
    case MOD:
    case UMOD:
      total = COSTS_N_INSNS (7);
      break;
    case USE:
      /* Used in loop.c and combine.c as a marker.  */
      total = 0;
      break;
    case ASM_OPERANDS:
      /* We don't want these to be used in substitutions because
	 we have no way of validating the resulting insn.  So assign
	 anything containing an ASM_OPERANDS a very high cost.  */
      total = 1000;
      break;
    default:
      total = 2;
    }

  switch (code)
    {
    case REG:
      return ! CHEAP_REG (x);

    case SUBREG:
      /* If we can't tie these modes, make this expensive.  The larger
	 the mode, the more expensive it is.  */
      if (! MODES_TIEABLE_P (GET_MODE (x), GET_MODE (SUBREG_REG (x))))
	return COSTS_N_INSNS (2
			      + GET_MODE_SIZE (GET_MODE (x)) / UNITS_PER_WORD);
      return 2;
#ifdef RTX_COSTS
      RTX_COSTS (x, code, outer_code);
#endif 
      CONST_COSTS (x, code, outer_code);
    }

  /* Sum the costs of the sub-rtx's, plus cost of this operation,
     which is already in total.  */

  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), code);
    else if (fmt[i] == 'E')
      for (j = 0; j < XVECLEN (x, i); j++)
	total += rtx_cost (XVECEXP (x, i, j), code);

  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;

  next_qty = max_reg;

  bzero ((char *) reg_tick, max_reg * sizeof (int));

  bcopy ((char *) all_minus_one, (char *) reg_in_table,
	 max_reg * sizeof (int));
  bcopy ((char *) consec_ints, (char *) reg_qty, max_reg * sizeof (int));
  CLEAR_HARD_REG_SET (hard_regs_in_table);

  /* The per-quantity values used to be initialized here, but it is
     much faster to initialize each as it is made in `make_new_qty'.  */

  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 ((char *) table, sizeof table);

  prev_insn = 0;

#ifdef HAVE_cc0
  prev_insn_cc0 = 0;