flow.c

早期freebsd实现

	    {
	      /* If nothing but SETs of registers to themselves,
		 this insn can also be deleted.  */
	      for (i = 0; i < XVECLEN (PATTERN (insn), 0); i++)
		{
		  rtx tem = XVECEXP (PATTERN (insn), 0, i);

		  if (GET_CODE (tem) == USE
		      || GET_CODE (tem) == CLOBBER)
		    continue;
		    
		  if (GET_CODE (tem) != SET
		      || GET_CODE (SET_DEST (tem)) != REG
		      || GET_CODE (SET_SRC (tem)) != REG
		      || REGNO (SET_DEST (tem)) != REGNO (SET_SRC (tem)))
		    break;
		}
		
	      if (i == XVECLEN (PATTERN (insn), 0)
		  /* Insns carrying these notes are useful later on.  */
		  && ! find_reg_note (insn, REG_EQUAL, NULL_RTX))
		{
		  PUT_CODE (insn, NOTE);
		  NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
		  NOTE_SOURCE_FILE (insn) = 0;
		}
	      else
		INSN_VOLATILE (insn) = volatile_refs_p (PATTERN (insn));
	    }
	  else if (GET_CODE (PATTERN (insn)) != USE)
	    INSN_VOLATILE (insn) = volatile_refs_p (PATTERN (insn));
	  /* A SET that makes space on the stack cannot be dead.
	     (Such SETs occur only for allocating variable-size data,
	     so they will always have a PLUS or MINUS according to the
	     direction of stack growth.)
	     Even if this function never uses this stack pointer value,
	     signal handlers do!  */
	  else if (code1 == INSN && GET_CODE (PATTERN (insn)) == SET
		   && SET_DEST (PATTERN (insn)) == stack_pointer_rtx
#ifdef STACK_GROWS_DOWNWARD
		   && GET_CODE (SET_SRC (PATTERN (insn))) == MINUS
#else
		   && GET_CODE (SET_SRC (PATTERN (insn))) == PLUS
#endif
		   && XEXP (SET_SRC (PATTERN (insn)), 0) == stack_pointer_rtx)
	    INSN_VOLATILE (insn) = 1;
	}
    }

  if (n_basic_blocks > 0)
#ifdef EXIT_IGNORE_STACK
    if (! EXIT_IGNORE_STACK
	|| (! FRAME_POINTER_REQUIRED && flag_omit_frame_pointer))
#endif
      {
	/* If exiting needs the right stack value,
	   consider the stack pointer live at the end of the function.  */
	basic_block_live_at_end[n_basic_blocks - 1]
	  [STACK_POINTER_REGNUM / REGSET_ELT_BITS]
	    |= (REGSET_ELT_TYPE) 1 << (STACK_POINTER_REGNUM % REGSET_ELT_BITS);
	basic_block_new_live_at_end[n_basic_blocks - 1]
	  [STACK_POINTER_REGNUM / REGSET_ELT_BITS]
	    |= (REGSET_ELT_TYPE) 1 << (STACK_POINTER_REGNUM % REGSET_ELT_BITS);
      }

  /* Mark the frame pointer is needed at the end of the function.  If
     we end up eliminating it, it will be removed from the live list
     of each basic block by reload.  */

  if (n_basic_blocks > 0)
    {
      basic_block_live_at_end[n_basic_blocks - 1]
	[FRAME_POINTER_REGNUM / REGSET_ELT_BITS]
	  |= (REGSET_ELT_TYPE) 1 << (FRAME_POINTER_REGNUM % REGSET_ELT_BITS);
      basic_block_new_live_at_end[n_basic_blocks - 1]
	[FRAME_POINTER_REGNUM / REGSET_ELT_BITS]
	  |= (REGSET_ELT_TYPE) 1 << (FRAME_POINTER_REGNUM % REGSET_ELT_BITS);
      }

  /* Mark all global registers as being live at the end of the function
     since they may be referenced by our caller.  */

  if (n_basic_blocks > 0)
    for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
      if (global_regs[i])
	{
	  basic_block_live_at_end[n_basic_blocks - 1]
	    [i / REGSET_ELT_BITS]
	      |= (REGSET_ELT_TYPE) 1 << (i % REGSET_ELT_BITS);
	  basic_block_new_live_at_end[n_basic_blocks - 1]
	    [i / REGSET_ELT_BITS]
	      |= (REGSET_ELT_TYPE) 1 << (i % REGSET_ELT_BITS);
	}

  /* Propagate life info through the basic blocks
     around the graph of basic blocks.

     This is a relaxation process: each time a new register
     is live at the end of the basic block, we must scan the block
     to determine which registers are, as a consequence, live at the beginning
     of that block.  These registers must then be marked live at the ends
     of all the blocks that can transfer control to that block.
     The process continues until it reaches a fixed point.  */

  first_pass = 1;
  changed = 1;
  while (changed)
    {
      changed = 0;
      for (i = n_basic_blocks - 1; i >= 0; i--)
	{
	  int consider = first_pass;
	  int must_rescan = first_pass;
	  register int j;

	  if (!first_pass)
	    {
	      /* Set CONSIDER if this block needs thinking about at all
		 (that is, if the regs live now at the end of it
		 are not the same as were live at the end of it when
		 we last thought about it).
		 Set must_rescan if it needs to be thought about
		 instruction by instruction (that is, if any additional
		 reg that is live at the end now but was not live there before
		 is one of the significant regs of this basic block).  */

	      for (j = 0; j < regset_size; j++)
		{
		  register REGSET_ELT_TYPE x
		    = (basic_block_new_live_at_end[i][j]
		       & ~basic_block_live_at_end[i][j]);
		  if (x)
		    consider = 1;
		  if (x & basic_block_significant[i][j])
		    {
		      must_rescan = 1;
		      consider = 1;
		      break;
		    }
		}

	      if (! consider)
		continue;
	    }

	  /* The live_at_start of this block may be changing,
	     so another pass will be required after this one.  */
	  changed = 1;

	  if (! must_rescan)
	    {
	      /* No complete rescan needed;
		 just record those variables newly known live at end
		 as live at start as well.  */
	      for (j = 0; j < regset_size; j++)
		{
		  register REGSET_ELT_TYPE x
		    = (basic_block_new_live_at_end[i][j]
		       & ~basic_block_live_at_end[i][j]);
		  basic_block_live_at_start[i][j] |= x;
		  basic_block_live_at_end[i][j] |= x;
		}
	    }
	  else
	    {
	      /* Update the basic_block_live_at_start
		 by propagation backwards through the block.  */
	      bcopy (basic_block_new_live_at_end[i],
		     basic_block_live_at_end[i], regset_bytes);
	      bcopy (basic_block_live_at_end[i],
		     basic_block_live_at_start[i], regset_bytes);
	      propagate_block (basic_block_live_at_start[i],
			       basic_block_head[i], basic_block_end[i], 0,
			       first_pass ? basic_block_significant[i]
			       : (regset) 0,
			       i);
	    }

	  {
	    register rtx jump, head;
	    /* Update the basic_block_new_live_at_end's of the block
	       that falls through into this one (if any).  */
	    head = basic_block_head[i];
	    jump = PREV_INSN (head);
	    if (basic_block_drops_in[i])
	      {
		register int from_block = BLOCK_NUM (jump);
		register int j;
		for (j = 0; j < regset_size; j++)
		  basic_block_new_live_at_end[from_block][j]
		    |= basic_block_live_at_start[i][j];
	      }
	    /* Update the basic_block_new_live_at_end's of
	       all the blocks that jump to this one.  */
	    if (GET_CODE (head) == CODE_LABEL)
	      for (jump = LABEL_REFS (head);
		   jump != head;
		   jump = LABEL_NEXTREF (jump))
		{
		  register int from_block = BLOCK_NUM (CONTAINING_INSN (jump));
		  register int j;
		  for (j = 0; j < regset_size; j++)
		    basic_block_new_live_at_end[from_block][j]
		      |= basic_block_live_at_start[i][j];
		}
	  }
#ifdef USE_C_ALLOCA
	  alloca (0);
#endif
	}
      first_pass = 0;
    }

  /* The only pseudos that are live at the beginning of the function are
     those that were not set anywhere in the function.  local-alloc doesn't
     know how to handle these correctly, so mark them as not local to any
     one basic block.  */

  if (n_basic_blocks > 0)
    for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
      if (basic_block_live_at_start[0][i / REGSET_ELT_BITS]
	  & ((REGSET_ELT_TYPE) 1 << (i % REGSET_ELT_BITS)))
	reg_basic_block[i] = REG_BLOCK_GLOBAL;

  /* Now the life information is accurate.
     Make one more pass over each basic block
     to delete dead stores, create autoincrement addressing
     and record how many times each register is used, is set, or dies.

     To save time, we operate directly in basic_block_live_at_end[i],
     thus destroying it (in fact, converting it into a copy of
     basic_block_live_at_start[i]).  This is ok now because
     basic_block_live_at_end[i] is no longer used past this point.  */

  max_scratch = 0;

  for (i = 0; i < n_basic_blocks; i++)
    {
      propagate_block (basic_block_live_at_end[i],
		       basic_block_head[i], basic_block_end[i], 1,
		       (regset) 0, i);
#ifdef USE_C_ALLOCA
      alloca (0);
#endif
    }

#if 0
  /* Something live during a setjmp should not be put in a register
     on certain machines which restore regs from stack frames
     rather than from the jmpbuf.
     But we don't need to do this for the user's variables, since
     ANSI says only volatile variables need this.  */
#ifdef LONGJMP_RESTORE_FROM_STACK
  for (i = FIRST_PSEUDO_REGISTER; i < nregs; i++)
    if (regs_live_at_setjmp[i / REGSET_ELT_BITS]
	& ((REGSET_ELT_TYPE) 1 << (i % REGSET_ELT_BITS))
	&& regno_reg_rtx[i] != 0 && ! REG_USERVAR_P (regno_reg_rtx[i]))
      {
	reg_live_length[i] = -1;
	reg_basic_block[i] = -1;
      }
#endif
#endif

  /* We have a problem with any pseudoreg that
     lives across the setjmp.  ANSI says that if a
     user variable does not change in value
     between the setjmp and the longjmp, then the longjmp preserves it.
     This includes longjmp from a place where the pseudo appears dead.
     (In principle, the value still exists if it is in scope.)
     If the pseudo goes in a hard reg, some other value may occupy
     that hard reg where this pseudo is dead, thus clobbering the pseudo.
     Conclusion: such a pseudo must not go in a hard reg.  */
  for (i = FIRST_PSEUDO_REGISTER; i < nregs; i++)
    if ((regs_live_at_setjmp[i / REGSET_ELT_BITS]
	 & ((REGSET_ELT_TYPE) 1 << (i % REGSET_ELT_BITS)))
	&& regno_reg_rtx[i] != 0)
      {
	reg_live_length[i] = -1;
	reg_basic_block[i] = -1;
      }

  obstack_free (&flow_obstack, NULL_PTR);
}

/* Subroutines of life analysis.  */

/* Allocate the permanent data structures that represent the results
   of life analysis.  Not static since used also for stupid life analysis.  */

void
allocate_for_life_analysis ()
{
  register int i;
  register regset tem;

  regset_size = ((max_regno + REGSET_ELT_BITS - 1) / REGSET_ELT_BITS);
  regset_bytes = regset_size * sizeof (*(regset)0);

  reg_n_refs = (int *) oballoc (max_regno * sizeof (int));
  bzero (reg_n_refs, max_regno * sizeof (int));

  reg_n_sets = (short *) oballoc (max_regno * sizeof (short));
  bzero (reg_n_sets, max_regno * sizeof (short));

  reg_n_deaths = (short *) oballoc (max_regno * sizeof (short));
  bzero (reg_n_deaths, max_regno * sizeof (short));

  reg_live_length = (int *) oballoc (max_regno * sizeof (int));
  bzero (reg_live_length, max_regno * sizeof (int));

  reg_n_calls_crossed = (int *) oballoc (max_regno * sizeof (int));
  bzero (reg_n_calls_crossed, max_regno * sizeof (int));

  reg_basic_block = (short *) oballoc (max_regno * sizeof (short));
  for (i = 0; i < max_regno; i++)
    reg_basic_block[i] = REG_BLOCK_UNKNOWN;

  basic_block_live_at_start = (regset *) oballoc (n_basic_blocks * sizeof (regset));
  tem = (regset) oballoc (n_basic_blocks * regset_bytes);
  bzero (tem, n_basic_blocks * regset_bytes);
  init_regset_vector (basic_block_live_at_start, tem, n_basic_blocks, regset_bytes);

  regs_live_at_setjmp = (regset) oballoc (regset_bytes);
  bzero (regs_live_at_setjmp, regset_bytes);
}

/* Make each element of VECTOR point at a regset,
   taking the space for all those regsets from SPACE.
   SPACE is of type regset, but it is really as long as NELTS regsets.
   BYTES_PER_ELT is the number of bytes in one regset.  */

static void
init_regset_vector (vector, space, nelts, bytes_per_elt)
     regset *vector;
     regset space;
     int nelts;
     int bytes_per_elt;
{
  register int i;
  register regset p = space;

  for (i = 0; i < nelts; i++)
    {
      vector[i] = p;
      p += bytes_per_elt / sizeof (*p);
    }
}

/* Compute the registers live at the beginning of a basic block
   from those live at the end.

   When called, OLD contains those live at the end.
   On return, it contains those live at the beginning.
   FIRST and LAST are the first and last insns of the basic block.

   FINAL is nonzero if we are doing the final pass which is not
   for computing the life info (since that has already been done)
   but for acting on it.  On this pass, we delete dead stores,
   set up the logical links and dead-variables lists of instructions,
   and merge instructions for autoincrement and autodecrement addresses.

   SIGNIFICANT is nonzero only the first time for each basic block.
   If it is nonzero, it points to a regset in which we store
   a 1 for each register that is set within the block.

   BNUM is the number of the basic block.  */

static void
propagate_block (old, first, last, final, significant, bnum)
     register regset old;
     rtx first;
     rtx last;
     int final;
     regset significant;
     int bnum;
{
  register rtx insn;
  rtx prev;
  regset live;
  regset dead;

  /* The following variables are used only if FINAL is nonzero.  */
  /* This vector gets one element for each reg that has been live
     at any point in the basic block that has been scanned so far.
     SOMETIMES_MAX says how many elements are in use so far.
     In each element, OFFSET is the byte-number within a regset
     for the register described by the element, and BIT is a mask
     for that register's bit within the byte.  */
  register struct sometimes { short offset; short bit; } *regs_sometimes_live;
  int sometimes_max = 0;
  /* This regset has 1 for each reg that we have seen live so far.
     It and REGS_SOMETIMES_LIVE are updated together.  */
  regset maxlive;

  /* The loop depth may change in the middle of a basic block.  Since we
     scan from end to beginning, we start with the depth at the end of the
     current basic block, and adjust as we pass ends and starts of loops.  */
  loop_depth = basic_block_loop_depth[bnum];