combine.c

早期freebsd实现

static rtx known_cond ();
static rtx make_field_assignment ();
static rtx make_compound_operation ();
static rtx apply_distributive_law ();
static rtx simplify_and_const_int ();
static unsigned HOST_WIDE_INT significant_bits ();
static int num_sign_bit_copies ();
static int merge_outer_ops ();
static rtx simplify_shift_const ();
static int recog_for_combine ();
static rtx gen_lowpart_for_combine ();
static rtx gen_rtx_combine ();
static rtx gen_binary ();
static rtx gen_unary ();
static enum rtx_code simplify_comparison ();
static int reversible_comparison_p ();
static int get_last_value_validate ();
static rtx get_last_value ();
static void distribute_notes ();
static void distribute_links ();

/* 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;

  combine_max_regno = nregs;

  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 = (short *) alloca (nregs * sizeof (short));
  reg_last_set_label = (short *) alloca (nregs * sizeof (short));
  reg_last_set_invalid = (char *) alloca (nregs * sizeof (char));
  reg_significant = (HOST_WIDE_INT *) alloca (nregs * sizeof (HOST_WIDE_INT));
  reg_sign_bit_copies = (char *) alloca (nregs * sizeof (char));

  bzero (reg_last_death, nregs * sizeof (rtx));
  bzero (reg_last_set, nregs * sizeof (rtx));
  bzero (reg_last_set_value, nregs * sizeof (rtx));
  bzero (reg_last_set_table_tick, nregs * sizeof (short));
  bzero (reg_last_set_invalid, nregs * sizeof (char));
  bzero (reg_significant, nregs * sizeof (HOST_WIDE_INT));
  bzero (reg_sign_bit_copies, nregs * sizeof (char));

  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));

  significant_mode = mode_for_size (HOST_BITS_PER_WIDE_INT, MODE_INT, 0);

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

  significant_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 significant for some registers.  */

  for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
    {
      INSN_CUID (insn) = ++i;
      if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
	note_stores (PATTERN (insn), set_significant);
    }

  significant_valid = 1;

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

  label_tick = 1;
  last_call_cuid = 0;
  mem_last_set = 0;

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

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

      else if (GET_CODE (insn) == INSN
	       || GET_CODE (insn) == CALL_INSN
	       || GET_CODE (insn) == JUMP_INSN)
	{
	  /* 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;

  significant_valid = 0;
}

/* Called via note_stores.  If X is a pseudo that is used in more than
   one basic block, is narrower that HOST_BITS_PER_WIDE_INT, and is being
   set, record what bits are significant.  If we are clobbering X,
   ignore this "set" because the clobbered value won't be used. 

   If we are setting only a portion of X and we can't figure out what
   portion, assume all bits will be used since we don't know what will
   be happening.

   Similarly, set how many bits of X are known to be copies of the sign bit
   at all locations in the function.  This is the smallest number implied 
   by any set of X.  */

static void
set_significant (x, set)
     rtx x;
     rtx set;
{
  int num;

  if (GET_CODE (x) == REG
      && REGNO (x) >= FIRST_PSEUDO_REGISTER
      && reg_n_sets[REGNO (x)] > 1
      && reg_basic_block[REGNO (x)] < 0
      && GET_MODE_BITSIZE (GET_MODE (x)) <= HOST_BITS_PER_WIDE_INT)
    {
      if (GET_CODE (set) == CLOBBER)
	return;

      /* If this is a complex assignment, see if we can convert it into a
	 simple assignment.  */
      set = expand_field_assignment (set);
      if (SET_DEST (set) == x)
	{
	  reg_significant[REGNO (x)]
	    |= significant_bits (SET_SRC (set), significant_mode);
	  num = num_sign_bit_copies (SET_SRC (set), GET_MODE (x));
	  if (reg_sign_bit_copies[REGNO (x)] == 0
	      || reg_sign_bit_copies[REGNO (x)] > num)
	    reg_sign_bit_copies[REGNO (x)] = num;
	}
      else
	{
	  reg_significant[REGNO (x)] = GET_MODE_MASK (GET_MODE (x));
	  reg_sign_bit_copies[REGNO (x)] = 0;
	}
    }
}

/* See if INSN can be combined into I3.  PRED and SUCC are optionally
   insns that were previously combined into I3 or that will be combined
   into the merger of INSN and I3.

   Return 0 if the combination is not allowed for any reason.

   If the combination is allowed, *PDEST will be set to the single 
   destination of INSN and *PSRC to the single source, and this function
   will return 1.  */

static int
can_combine_p (insn, i3, pred, succ, pdest, psrc)
     rtx insn;
     rtx i3;
     rtx pred, succ;
     rtx *pdest, *psrc;
{
  int i;
  rtx set = 0, src, dest;
  rtx p, link;
  int all_adjacent = (succ ? (next_active_insn (insn) == succ
			      && next_active_insn (succ) == i3)
		      : next_active_insn (insn) == i3);

  /* Can combine only if previous insn is a SET of a REG, a SUBREG or CC0.
     or a PARALLEL consisting of such a SET and CLOBBERs. 

     If INSN has CLOBBER parallel parts, ignore them for our processing.
     By definition, these happen during the execution of the insn.  When it
     is merged with another insn, all bets are off.  If they are, in fact,
     needed and aren't also supplied in I3, they may be added by
     recog_for_combine.  Otherwise, it won't match. 

     We can also ignore a SET whose SET_DEST is mentioned in a REG_UNUSED
     note.

     Get the source and destination of INSN.  If more than one, can't 
     combine.  */
     
  if (GET_CODE (PATTERN (insn)) == SET)
    set = PATTERN (insn);
  else if (GET_CODE (PATTERN (insn)) == PARALLEL
	   && GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) == SET)
    {
      for (i = 0; i < XVECLEN (PATTERN (insn), 0); i++)
	{
	  rtx elt = XVECEXP (PATTERN (insn), 0, i);

	  switch (GET_CODE (elt))
	    {
	      /* We can ignore CLOBBERs.  */
	    case CLOBBER:
	      break;

	    case SET:
	      /* Ignore SETs whose result isn't used but not those that
		 have side-effects.  */
	      if (find_reg_note (insn, REG_UNUSED, SET_DEST (elt))
		  && ! side_effects_p (elt))
		break;

	      /* If we have already found a SET, this is a second one and
		 so we cannot combine with this insn.  */
	      if (set)
		return 0;

	      set = elt;
	      break;

	    default:
	      /* Anything else means we can't combine.  */
	      return 0;
	    }
	}

      if (set == 0
	  /* If SET_SRC is an ASM_OPERANDS we can't throw away these CLOBBERs,
	     so don't do anything with it.  */
	  || GET_CODE (SET_SRC (set)) == ASM_OPERANDS)
	return 0;
    }
  else
    return 0;

  if (set == 0)
    return 0;

  set = expand_field_assignment (set);
  src = SET_SRC (set), dest = SET_DEST (set);

  /* Don't eliminate a store in the stack pointer.  */
  if (dest == stack_pointer_rtx
      /* Don't install a subreg involving two modes not tieable.
	 It can worsen register allocation, and can even make invalid reload
	 insns, since the reg inside may need to be copied from in the
	 outside mode, and that may be invalid if it is an fp reg copied in
	 integer mode.  As a special exception, we can allow this if
	 I3 is simply copying DEST, a REG,  to CC0.  */
      || (GET_CODE (src) == SUBREG
	  && ! MODES_TIEABLE_P (GET_MODE (src), GET_MODE (SUBREG_REG (src)))
#ifdef HAVE_cc0
	  && ! (GET_CODE (i3) == INSN && GET_CODE (PATTERN (i3)) == SET
		&& SET_DEST (PATTERN (i3)) == cc0_rtx
		&& GET_CODE (dest) == REG && dest == SET_SRC (PATTERN (i3)))
#endif
	  )