combine.c

GCC编译器源代码

								\
      _buf->is_int = 0;						\
      _buf->where.r = &INTO;					\
      _buf->old_contents.r = INTO;				\
      INTO = _new;						\
      if (_buf->old_contents.r == INTO)				\
	_buf->next = undobuf.frees, undobuf.frees = _buf;	\
      else							\
	_buf->next = undobuf.undos, undobuf.undos = _buf;	\
    } while (0)

/* Similar to SUBST, but NEWVAL is an int expression.  Note that substitution
   for the value of a HOST_WIDE_INT value (including CONST_INT) is
   not safe.  */

#define SUBST_INT(INTO, NEWVAL)  \
 do { struct undo *_buf;					\
								\
      if (undobuf.frees)					\
	_buf = undobuf.frees, undobuf.frees = _buf->next;	\
      else							\
	_buf = (struct undo *) xmalloc (sizeof (struct undo));	\
								\
      _buf->is_int = 1;						\
      _buf->where.i = (int *) &INTO;				\
      _buf->old_contents.i = INTO;				\
      INTO = NEWVAL;						\
      if (_buf->old_contents.i == INTO)				\
	_buf->next = undobuf.frees, undobuf.frees = _buf;	\
      else							\
	_buf->next = undobuf.undos, undobuf.undos = _buf;	\
     } while (0)

/* Number of times the pseudo being substituted for
   was found and replaced.  */

static int n_occurrences;

static void init_reg_last_arrays	PROTO((void));
static void setup_incoming_promotions   PROTO((void));
static void set_nonzero_bits_and_sign_copies  PROTO((rtx, rtx));
static int can_combine_p	PROTO((rtx, rtx, rtx, rtx, rtx *, rtx *));
static int combinable_i3pat	PROTO((rtx, rtx *, rtx, rtx, int, rtx *));
static rtx try_combine		PROTO((rtx, rtx, rtx));
static void undo_all		PROTO((void));
static rtx *find_split_point	PROTO((rtx *, rtx));
static rtx subst		PROTO((rtx, rtx, rtx, int, int));
static rtx simplify_rtx		PROTO((rtx, enum machine_mode, int, int));
static rtx simplify_if_then_else  PROTO((rtx));
static rtx simplify_set		PROTO((rtx));
static rtx simplify_logical	PROTO((rtx, int));
static rtx expand_compound_operation  PROTO((rtx));
static rtx expand_field_assignment  PROTO((rtx));
static rtx make_extraction	PROTO((enum machine_mode, rtx, int, rtx, int,
				       int, int, int));
static rtx extract_left_shift	PROTO((rtx, int));
static rtx make_compound_operation  PROTO((rtx, enum rtx_code));
static int get_pos_from_mask	PROTO((unsigned HOST_WIDE_INT, int *));
static rtx force_to_mode	PROTO((rtx, enum machine_mode,
				       unsigned HOST_WIDE_INT, rtx, int));
static rtx if_then_else_cond	PROTO((rtx, rtx *, rtx *));
static rtx known_cond		PROTO((rtx, enum rtx_code, rtx, rtx));
static int rtx_equal_for_field_assignment_p PROTO((rtx, rtx));
static rtx make_field_assignment  PROTO((rtx));
static rtx apply_distributive_law  PROTO((rtx));
static rtx simplify_and_const_int  PROTO((rtx, enum machine_mode, rtx,
					  unsigned HOST_WIDE_INT));
static unsigned HOST_WIDE_INT nonzero_bits  PROTO((rtx, enum machine_mode));
static int num_sign_bit_copies  PROTO((rtx, enum machine_mode));
static int merge_outer_ops	PROTO((enum rtx_code *, HOST_WIDE_INT *,
				       enum rtx_code, HOST_WIDE_INT,
				       enum machine_mode, int *));
static rtx simplify_shift_const	PROTO((rtx, enum rtx_code, enum machine_mode,
				       rtx, int));
static int recog_for_combine	PROTO((rtx *, rtx, rtx *, int *));
static rtx gen_lowpart_for_combine  PROTO((enum machine_mode, rtx));
static rtx gen_rtx_combine PVPROTO((enum rtx_code code, enum machine_mode mode,
				  ...));
static rtx gen_binary		PROTO((enum rtx_code, enum machine_mode,
				       rtx, rtx));
static rtx gen_unary		PROTO((enum rtx_code, enum machine_mode,
				       enum machine_mode, rtx));
static enum rtx_code simplify_comparison  PROTO((enum rtx_code, rtx *, rtx *));
static int reversible_comparison_p  PROTO((rtx));
static void update_table_tick	PROTO((rtx));
static void record_value_for_reg  PROTO((rtx, rtx, rtx));
static void record_dead_and_set_regs_1  PROTO((rtx, rtx));
static void record_dead_and_set_regs  PROTO((rtx));
static int get_last_value_validate  PROTO((rtx *, rtx, int, int));
static rtx get_last_value	PROTO((rtx));
static int use_crosses_set_p	PROTO((rtx, int));
static void reg_dead_at_p_1	PROTO((rtx, rtx));
static int reg_dead_at_p	PROTO((rtx, rtx));
static void move_deaths		PROTO((rtx, rtx, int, rtx, rtx *));
static int reg_bitfield_target_p  PROTO((rtx, rtx));
static void distribute_notes	PROTO((rtx, rtx, rtx, rtx, rtx, rtx));
static void distribute_links	PROTO((rtx));
static void mark_used_regs_combine PROTO((rtx));
static int insn_cuid		PROTO((rtx));

/* Main entry point for combiner.  F is the first insn of the function.
   NREGS is the first unused pseudo-reg number.  */

void
combine_instructions (f, nregs)
     rtx f;
     int nregs;
{
  register rtx insn, next, prev;
  register int i;
  register rtx links, nextlinks;

  combine_attempts = 0;
  combine_merges = 0;
  combine_extras = 0;
  combine_successes = 0;
  undobuf.undos = undobuf.previous_undos = 0;

  combine_max_regno = nregs;

  reg_nonzero_bits
    = (unsigned HOST_WIDE_INT *) alloca (nregs * sizeof (HOST_WIDE_INT));
  reg_sign_bit_copies = (char *) alloca (nregs * sizeof (char));

  bzero ((char *) reg_nonzero_bits, nregs * sizeof (HOST_WIDE_INT));
  bzero (reg_sign_bit_copies, nregs * sizeof (char));

  reg_last_death = (rtx *) alloca (nregs * sizeof (rtx));
  reg_last_set = (rtx *) alloca (nregs * sizeof (rtx));
  reg_last_set_value = (rtx *) alloca (nregs * sizeof (rtx));
  reg_last_set_table_tick = (int *) alloca (nregs * sizeof (int));
  reg_last_set_label = (int *) alloca (nregs * sizeof (int));
  reg_last_set_invalid = (char *) alloca (nregs * sizeof (char));
  reg_last_set_mode
    = (enum machine_mode *) alloca (nregs * sizeof (enum machine_mode));
  reg_last_set_nonzero_bits
    = (unsigned HOST_WIDE_INT *) alloca (nregs * sizeof (HOST_WIDE_INT));
  reg_last_set_sign_bit_copies
    = (char *) alloca (nregs * sizeof (char));

  init_reg_last_arrays ();

  init_recog_no_volatile ();

  /* Compute maximum uid value so uid_cuid can be allocated.  */

  for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
    if (INSN_UID (insn) > i)
      i = INSN_UID (insn);

  uid_cuid = (int *) alloca ((i + 1) * sizeof (int));
  max_uid_cuid = i;

  nonzero_bits_mode = mode_for_size (HOST_BITS_PER_WIDE_INT, MODE_INT, 0);

  /* Don't use reg_nonzero_bits when computing it.  This can cause problems
     when, for example, we have j <<= 1 in a loop.  */

  nonzero_sign_valid = 0;

  /* Compute the mapping from uids to cuids.
     Cuids are numbers assigned to insns, like uids,
     except that cuids increase monotonically through the code. 

     Scan all SETs and see if we can deduce anything about what
     bits are known to be zero for some registers and how many copies
     of the sign bit are known to exist for those registers.

     Also set any known values so that we can use it while searching
     for what bits are known to be set.  */

  label_tick = 1;

  /* We need to initialize it here, because record_dead_and_set_regs may call
     get_last_value.  */
  subst_prev_insn = NULL_RTX;

  setup_incoming_promotions ();

  for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
    {
      uid_cuid[INSN_UID (insn)] = ++i;
      subst_low_cuid = i;
      subst_insn = insn;

      if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
	{
	  note_stores (PATTERN (insn), set_nonzero_bits_and_sign_copies);
	  record_dead_and_set_regs (insn);

#ifdef AUTO_INC_DEC
	  for (links = REG_NOTES (insn); links; links = XEXP (links, 1))
	    if (REG_NOTE_KIND (links) == REG_INC)
	      set_nonzero_bits_and_sign_copies (XEXP (links, 0), NULL_RTX);
#endif
	}

      if (GET_CODE (insn) == CODE_LABEL)
	label_tick++;
    }

  nonzero_sign_valid = 1;

  /* Now scan all the insns in forward order.  */

  this_basic_block = -1;
  label_tick = 1;
  last_call_cuid = 0;
  mem_last_set = 0;
  init_reg_last_arrays ();
  setup_incoming_promotions ();

  for (insn = f; insn; insn = next ? next : NEXT_INSN (insn))
    {
      next = 0;

      /* If INSN starts a new basic block, update our basic block number.  */
      if (this_basic_block + 1 < n_basic_blocks
	  && basic_block_head[this_basic_block + 1] == insn)
	this_basic_block++;

      if (GET_CODE (insn) == CODE_LABEL)
	label_tick++;

      else if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
	{
	  /* Try this insn with each insn it links back to.  */

	  for (links = LOG_LINKS (insn); links; links = XEXP (links, 1))
	    if ((next = try_combine (insn, XEXP (links, 0), NULL_RTX)) != 0)
	      goto retry;

	  /* Try each sequence of three linked insns ending with this one.  */

	  for (links = LOG_LINKS (insn); links; links = XEXP (links, 1))
	    for (nextlinks = LOG_LINKS (XEXP (links, 0)); nextlinks;
		 nextlinks = XEXP (nextlinks, 1))
	      if ((next = try_combine (insn, XEXP (links, 0),
				       XEXP (nextlinks, 0))) != 0)
		goto retry;

#ifdef HAVE_cc0
	  /* Try to combine a jump insn that uses CC0
	     with a preceding insn that sets CC0, and maybe with its
	     logical predecessor as well.
	     This is how we make decrement-and-branch insns.
	     We need this special code because data flow connections
	     via CC0 do not get entered in LOG_LINKS.  */

	  if (GET_CODE (insn) == JUMP_INSN
	      && (prev = prev_nonnote_insn (insn)) != 0
	      && GET_CODE (prev) == INSN
	      && sets_cc0_p (PATTERN (prev)))
	    {
	      if ((next = try_combine (insn, prev, NULL_RTX)) != 0)
		goto retry;

	      for (nextlinks = LOG_LINKS (prev); nextlinks;
		   nextlinks = XEXP (nextlinks, 1))
		if ((next = try_combine (insn, prev,
					 XEXP (nextlinks, 0))) != 0)
		  goto retry;
	    }

	  /* Do the same for an insn that explicitly references CC0.  */
	  if (GET_CODE (insn) == INSN
	      && (prev = prev_nonnote_insn (insn)) != 0
	      && GET_CODE (prev) == INSN
	      && sets_cc0_p (PATTERN (prev))
	      && GET_CODE (PATTERN (insn)) == SET
	      && reg_mentioned_p (cc0_rtx, SET_SRC (PATTERN (insn))))
	    {
	      if ((next = try_combine (insn, prev, NULL_RTX)) != 0)
		goto retry;

	      for (nextlinks = LOG_LINKS (prev); nextlinks;
		   nextlinks = XEXP (nextlinks, 1))
		if ((next = try_combine (insn, prev,
					 XEXP (nextlinks, 0))) != 0)
		  goto retry;
	    }

	  /* Finally, see if any of the insns that this insn links to
	     explicitly references CC0.  If so, try this insn, that insn,
	     and its predecessor if it sets CC0.  */
	  for (links = LOG_LINKS (insn); links; links = XEXP (links, 1))
	    if (GET_CODE (XEXP (links, 0)) == INSN
		&& GET_CODE (PATTERN (XEXP (links, 0))) == SET
		&& reg_mentioned_p (cc0_rtx, SET_SRC (PATTERN (XEXP (links, 0))))
		&& (prev = prev_nonnote_insn (XEXP (links, 0))) != 0
		&& GET_CODE (prev) == INSN
		&& sets_cc0_p (PATTERN (prev))
		&& (next = try_combine (insn, XEXP (links, 0), prev)) != 0)
	      goto retry;
#endif

	  /* Try combining an insn with two different insns whose results it
	     uses.  */
	  for (links = LOG_LINKS (insn); links; links = XEXP (links, 1))
	    for (nextlinks = XEXP (links, 1); nextlinks;
		 nextlinks = XEXP (nextlinks, 1))
	      if ((next = try_combine (insn, XEXP (links, 0),
				       XEXP (nextlinks, 0))) != 0)
		goto retry;

	  if (GET_CODE (insn) != NOTE)
	    record_dead_and_set_regs (insn);

	retry:
	  ;
	}
    }

  total_attempts += combine_attempts;
  total_merges += combine_merges;
  total_extras += combine_extras;
  total_successes += combine_successes;

  nonzero_sign_valid = 0;
}

/* Wipe the reg_last_xxx arrays in preparation for another pass.  */

static void
init_reg_last_arrays ()
{
  int nregs = combine_max_regno;

  bzero ((char *) reg_last_death, nregs * sizeof (rtx));
  bzero ((char *) reg_last_set, nregs * sizeof (rtx));
  bzero ((char *) reg_last_set_value, nregs * sizeof (rtx));
  bzero ((char *) reg_last_set_table_tick, nregs * sizeof (int));
  bzero ((char *) reg_last_set_label, nregs * sizeof (int));
  bzero (reg_last_set_invalid, nregs * sizeof (char));
  bzero ((char *) reg_last_set_mode, nregs * sizeof (enum machine_mode));
  bzero ((char *) reg_last_set_nonzero_bits, nregs * sizeof (HOST_WIDE_INT));
  bzero (reg_last_set_sign_bit_copies, nregs * sizeof (char));
}

/* Set up any promoted values for incoming argument registers.  */

static void
setup_incoming_promotions ()
{
#ifdef PROMOTE_FUNCTION_ARGS
  int regno;
  rtx reg;
  enum machine_mode mode;
  int unsignedp;
  rtx first = get_insns ();

  for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
    if (FUNCTION_ARG_REGNO_P (regno)
	&& (reg = promoted_input_arg (regno, &mode, &unsignedp)) != 0)
      record_value_for_reg (reg, first,
			    gen_rtx (unsignedp ? ZERO_EXTEND : SIGN_EXTEND,
				     GET_MODE (reg),
				     gen_rtx (CLOBBER, mode, const0_rtx)));
#endif