flow.c

早期freebsd实现

  dead = (regset) alloca (regset_bytes);
  live = (regset) alloca (regset_bytes);

  cc0_live = 0;
  last_mem_set = 0;

  /* Include any notes at the end of the block in the scan.
     This is in case the block ends with a call to setjmp.  */

  while (NEXT_INSN (last) != 0 && GET_CODE (NEXT_INSN (last)) == NOTE)
    {
      /* Look for loop boundaries, we are going forward here.  */
      last = NEXT_INSN (last);
      if (NOTE_LINE_NUMBER (last) == NOTE_INSN_LOOP_BEG)
	loop_depth++;
      else if (NOTE_LINE_NUMBER (last) == NOTE_INSN_LOOP_END)
	loop_depth--;
    }

  if (final)
    {
      register int i, offset;
      REGSET_ELT_TYPE bit;

      num_scratch = 0;
      maxlive = (regset) alloca (regset_bytes);
      bcopy (old, maxlive, regset_bytes);
      regs_sometimes_live
	= (struct sometimes *) alloca (max_regno * sizeof (struct sometimes));

      /* Process the regs live at the end of the block.
	 Enter them in MAXLIVE and REGS_SOMETIMES_LIVE.
	 Also mark them as not local to any one basic block.  */

      for (offset = 0, i = 0; offset < regset_size; offset++)
	for (bit = 1; bit; bit <<= 1, i++)
	  {
	    if (i == max_regno)
	      break;
	    if (old[offset] & bit)
	      {
		reg_basic_block[i] = REG_BLOCK_GLOBAL;
		regs_sometimes_live[sometimes_max].offset = offset;
		regs_sometimes_live[sometimes_max].bit = i % REGSET_ELT_BITS;
		sometimes_max++;
	      }
	  }
    }

  /* Scan the block an insn at a time from end to beginning.  */

  for (insn = last; ; insn = prev)
    {
      prev = PREV_INSN (insn);

      /* Look for loop boundaries, remembering that we are going backwards.  */
      if (GET_CODE (insn) == NOTE
	  && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
	loop_depth++;
      else if (GET_CODE (insn) == NOTE
	       && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
	loop_depth--;

      /* If we have LOOP_DEPTH == 0, there has been a bookkeeping error. 
	 Abort now rather than setting register status incorrectly.  */
      if (loop_depth == 0)
	abort ();

      /* If this is a call to `setjmp' et al,
	 warn if any non-volatile datum is live.  */

      if (final && GET_CODE (insn) == NOTE
	  && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)
	{
	  int i;
	  for (i = 0; i < regset_size; i++)
	    regs_live_at_setjmp[i] |= old[i];
	}

      /* Update the life-status of regs for this insn.
	 First DEAD gets which regs are set in this insn
	 then LIVE gets which regs are used in this insn.
	 Then the regs live before the insn
	 are those live after, with DEAD regs turned off,
	 and then LIVE regs turned on.  */

      if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
	{
	  register int i;
	  rtx note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
	  int insn_is_dead
	    = (insn_dead_p (PATTERN (insn), old, 0)
	       /* Don't delete something that refers to volatile storage!  */
	       && ! INSN_VOLATILE (insn));
	  int libcall_is_dead 
	    = (insn_is_dead && note != 0
	       && libcall_dead_p (PATTERN (insn), old, note, insn));

	  /* If an instruction consists of just dead store(s) on final pass,
	     "delete" it by turning it into a NOTE of type NOTE_INSN_DELETED.
	     We could really delete it with delete_insn, but that
	     can cause trouble for first or last insn in a basic block.  */
	  if (final && insn_is_dead)
	    {
	      PUT_CODE (insn, NOTE);
	      NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
	      NOTE_SOURCE_FILE (insn) = 0;

	      /* CC0 is now known to be dead.  Either this insn used it,
		 in which case it doesn't anymore, or clobbered it,
		 so the next insn can't use it.  */
	      cc0_live = 0;

	      /* If this insn is copying the return value from a library call,
		 delete the entire library call.  */
	      if (libcall_is_dead)
		{
		  rtx first = XEXP (note, 0);
		  rtx p = insn;
		  while (INSN_DELETED_P (first))
		    first = NEXT_INSN (first);
		  while (p != first)
		    {
		      p = PREV_INSN (p);
		      PUT_CODE (p, NOTE);
		      NOTE_LINE_NUMBER (p) = NOTE_INSN_DELETED;
		      NOTE_SOURCE_FILE (p) = 0;
		    }
		}
	      goto flushed;
	    }

	  for (i = 0; i < regset_size; i++)
	    {
	      dead[i] = 0;	/* Faster than bzero here */
	      live[i] = 0;	/* since regset_size is usually small */
	    }

	  /* See if this is an increment or decrement that can be
	     merged into a following memory address.  */
#ifdef AUTO_INC_DEC
	  {
	    register rtx x = PATTERN (insn);
	    /* Does this instruction increment or decrement a register?  */
	    if (final && GET_CODE (x) == SET
		&& GET_CODE (SET_DEST (x)) == REG
		&& (GET_CODE (SET_SRC (x)) == PLUS
		    || GET_CODE (SET_SRC (x)) == MINUS)
		&& XEXP (SET_SRC (x), 0) == SET_DEST (x)
		&& GET_CODE (XEXP (SET_SRC (x), 1)) == CONST_INT
		/* Ok, look for a following memory ref we can combine with.
		   If one is found, change the memory ref to a PRE_INC
		   or PRE_DEC, cancel this insn, and return 1.
		   Return 0 if nothing has been done.  */
		&& try_pre_increment_1 (insn))
	      goto flushed;
	  }
#endif /* AUTO_INC_DEC */

	  /* If this is not the final pass, and this insn is copying the
	     value of a library call and it's dead, don't scan the
	     insns that perform the library call, so that the call's
	     arguments are not marked live.  */
	  if (libcall_is_dead)
	    {
	      /* Mark the dest reg as `significant'.  */
	      mark_set_regs (old, dead, PATTERN (insn), NULL_RTX, significant);

	      insn = XEXP (note, 0);
	      prev = PREV_INSN (insn);
	    }
	  else if (GET_CODE (PATTERN (insn)) == SET
		   && SET_DEST (PATTERN (insn)) == stack_pointer_rtx
		   && GET_CODE (SET_SRC (PATTERN (insn))) == PLUS
		   && XEXP (SET_SRC (PATTERN (insn)), 0) == stack_pointer_rtx
		   && GET_CODE (XEXP (SET_SRC (PATTERN (insn)), 1)) == CONST_INT)
	    /* We have an insn to pop a constant amount off the stack.
	       (Such insns use PLUS regardless of the direction of the stack,
	       and any insn to adjust the stack by a constant is always a pop.)
	       These insns, if not dead stores, have no effect on life.  */
	    ;
	  else
	    {
	      /* LIVE gets the regs used in INSN;
		 DEAD gets those set by it.  Dead insns don't make anything
		 live.  */

	      mark_set_regs (old, dead, PATTERN (insn),
			     final ? insn : NULL_RTX, significant);

	      /* If an insn doesn't use CC0, it becomes dead since we 
		 assume that every insn clobbers it.  So show it dead here;
		 mark_used_regs will set it live if it is referenced.  */
	      cc0_live = 0;

	      if (! insn_is_dead)
		mark_used_regs (old, live, PATTERN (insn), final, insn);

	      /* Sometimes we may have inserted something before INSN (such as
		 a move) when we make an auto-inc.  So ensure we will scan
		 those insns.  */
#ifdef AUTO_INC_DEC
	      prev = PREV_INSN (insn);
#endif

	      if (! insn_is_dead && GET_CODE (insn) == CALL_INSN)
		{
		  register int i;

		  /* Each call clobbers all call-clobbered regs that are not
		     global.  Note that the function-value reg is a
		     call-clobbered reg, and mark_set_regs has already had
		     a chance to handle it.  */

		  for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
		    if (call_used_regs[i] && ! global_regs[i])
		      dead[i / REGSET_ELT_BITS]
			|= ((REGSET_ELT_TYPE) 1 << (i % REGSET_ELT_BITS));

		  /* The stack ptr is used (honorarily) by a CALL insn.  */
		  live[STACK_POINTER_REGNUM / REGSET_ELT_BITS]
		    |= ((REGSET_ELT_TYPE) 1
			<< (STACK_POINTER_REGNUM % REGSET_ELT_BITS));

		  /* Calls may also reference any of the global registers,
		     so they are made live.  */

		  for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
		    if (global_regs[i])
		      live[i / REGSET_ELT_BITS]
			|= ((REGSET_ELT_TYPE) 1 << (i % REGSET_ELT_BITS));

		  /* Calls also clobber memory.  */
		  last_mem_set = 0;
		}

	      /* Update OLD for the registers used or set.  */
	      for (i = 0; i < regset_size; i++)
		{
		  old[i] &= ~dead[i];
		  old[i] |= live[i];
		}

	      if (GET_CODE (insn) == CALL_INSN && final)
		{
		  /* Any regs live at the time of a call instruction
		     must not go in a register clobbered by calls.
		     Find all regs now live and record this for them.  */

		  register struct sometimes *p = regs_sometimes_live;

		  for (i = 0; i < sometimes_max; i++, p++)
		    if (old[p->offset] & ((REGSET_ELT_TYPE) 1 << p->bit))
		      reg_n_calls_crossed[p->offset * REGSET_ELT_BITS + p->bit]+= 1;
		}
	    }

	  /* On final pass, add any additional sometimes-live regs
	     into MAXLIVE and REGS_SOMETIMES_LIVE.
	     Also update counts of how many insns each reg is live at.  */

	  if (final)
	    {
	      for (i = 0; i < regset_size; i++)
		{
		  register REGSET_ELT_TYPE diff = live[i] & ~maxlive[i];

		  if (diff)
		    {
		      register int regno;
		      maxlive[i] |= diff;
		      for (regno = 0; diff && regno < REGSET_ELT_BITS; regno++)
			if (diff & ((REGSET_ELT_TYPE) 1 << regno))
			  {
			    regs_sometimes_live[sometimes_max].offset = i;
			    regs_sometimes_live[sometimes_max].bit = regno;
			    diff &= ~ ((REGSET_ELT_TYPE) 1 << regno);
			    sometimes_max++;
			  }
		    }
		}

	      {
		register struct sometimes *p = regs_sometimes_live;
		for (i = 0; i < sometimes_max; i++, p++)
		  {
		    if (old[p->offset] & ((REGSET_ELT_TYPE) 1 << p->bit))
		      reg_live_length[p->offset * REGSET_ELT_BITS + p->bit]++;
		  }
	      }
	    }
	}
    flushed: ;
      if (insn == first)
	break;
    }

  if (num_scratch > max_scratch)
    max_scratch = num_scratch;
}

/* Return 1 if X (the body of an insn, or part of it) is just dead stores
   (SET expressions whose destinations are registers dead after the insn).
   NEEDED is the regset that says which regs are alive after the insn.

   Unless CALL_OK is non-zero, an insn is needed if it contains a CALL.  */

static int
insn_dead_p (x, needed, call_ok)
     rtx x;
     regset needed;
     int call_ok;
{
  register RTX_CODE code = GET_CODE (x);
  /* If setting something that's a reg or part of one,
     see if that register's altered value will be live.  */

  if (code == SET)
    {
      register rtx r = SET_DEST (x);
      /* A SET that is a subroutine call cannot be dead.  */
      if (! call_ok && GET_CODE (SET_SRC (x)) == CALL)
	return 0;

#ifdef HAVE_cc0
      if (GET_CODE (r) == CC0)
	return ! cc0_live;
#endif
      
      if (GET_CODE (r) == MEM && last_mem_set && ! MEM_VOLATILE_P (r)
	  && rtx_equal_p (r, last_mem_set))
	return 1;

      while (GET_CODE (r) == SUBREG
	     || GET_CODE (r) == STRICT_LOW_PART
	     || GET_CODE (r) == ZERO_EXTRACT
	     || GET_CODE (r) == SIGN_EXTRACT)
	r = SUBREG_REG (r);

      if (GET_CODE (r) == REG)
	{
	  register int regno = REGNO (r);
	  register int offset = regno / REGSET_ELT_BITS;
	  register REGSET_ELT_TYPE bit
	    = (REGSET_ELT_TYPE) 1 << (regno % REGSET_ELT_BITS);

	  /* Don't delete insns to set global regs.  */
	  if ((regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
	      /* Make sure insns to set frame pointer aren't deleted.  */
	      || regno == FRAME_POINTER_REGNUM
#if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
	      /* Make sure insns to set arg pointer are never deleted
		 (if the arg pointer isn't fixed, there will be a USE for
		 it, so we can treat it normally). */
	      || (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
#endif
	      || (needed[offset] & bit) != 0)
	    return 0;

	  /* If this is a hard register, verify that subsequent words are
	     not needed.  */
	  if (regno < FIRST_PSEUDO_REGISTER)
	    {
	      int n = HARD_REGNO_NREGS (regno, GET_MODE (r));

	      while (--n > 0)
		if ((needed[(regno + n) / REGSET_ELT_BITS]
		     & ((REGSET_ELT_TYPE) 1
			<< ((regno + n) % REGSET_ELT_BITS))) != 0)
		  return 0;
	    }

	  return 1;
	}
    }
  /* If performing several activities,
     insn is dead if each activity is individually dead.
     Also, CLOBBERs and USEs can be ignored; a CLOBBER or USE
     that's inside a PARALLEL doesn't make the insn worth keeping.  */
  else if (code == PARALLEL)
    {
      register int i = XVECLEN (x, 0);
      for (i--; i >= 0; i--)
	{
	  rtx elt = XVECEXP (x, 0, i);
	  if (!insn_dead_p (elt, needed, call_ok)
	      && GET_CODE (elt) != CLOBBER
	      && GET_CODE (elt) != USE)
	    return 0;
	}
      return 1;
    }
  /* We do not check CLOBBER or USE here.
     An insn consisting of just a CLOBBER or just a USE
     should not be deleted.  */
  return 0;
}