flow.c

GCC编译器源代码

/* Delete INSN by patching it out.
   Return the next insn.  */

static rtx
flow_delete_insn (insn)
     rtx insn;
{
  /* ??? For the moment we assume we don't have to watch for NULLs here
     since the start/end of basic blocks aren't deleted like this.  */
  NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
  PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
  return NEXT_INSN (insn);
}

/* Determine which registers are live at the start of each
   basic block of the function whose first insn is F.
   NREGS is the number of registers used in F.
   We allocate the vector basic_block_live_at_start
   and the regsets that it points to, and fill them with the data.
   regset_size and regset_bytes are also set here.  */

static void
life_analysis (f, nregs)
     rtx f;
     int nregs;
{
  int first_pass;
  int changed;
  /* For each basic block, a bitmask of regs
     live on exit from the block.  */
  regset *basic_block_live_at_end;
  /* For each basic block, a bitmask of regs
     live on entry to a successor-block of this block.
     If this does not match basic_block_live_at_end,
     that must be updated, and the block must be rescanned.  */
  regset *basic_block_new_live_at_end;
  /* For each basic block, a bitmask of regs
     whose liveness at the end of the basic block
     can make a difference in which regs are live on entry to the block.
     These are the regs that are set within the basic block,
     possibly excluding those that are used after they are set.  */
  regset *basic_block_significant;
  register int i;
  rtx insn;

  struct obstack flow_obstack;

  gcc_obstack_init (&flow_obstack);

  max_regno = nregs;

  bzero (regs_ever_live, sizeof regs_ever_live);

  /* Allocate and zero out many data structures
     that will record the data from lifetime analysis.  */

  allocate_for_life_analysis ();

  reg_next_use = (rtx *) alloca (nregs * sizeof (rtx));
  bzero ((char *) reg_next_use, nregs * sizeof (rtx));

  /* Set up several regset-vectors used internally within this function.
     Their meanings are documented above, with their declarations.  */

  basic_block_live_at_end
    = (regset *) alloca (n_basic_blocks * sizeof (regset));

  /* Don't use alloca since that leads to a crash rather than an error message
     if there isn't enough space.
     Don't use oballoc since we may need to allocate other things during
     this function on the temporary obstack.  */
  init_regset_vector (basic_block_live_at_end, n_basic_blocks, &flow_obstack);

  basic_block_new_live_at_end
    = (regset *) alloca (n_basic_blocks * sizeof (regset));
  init_regset_vector (basic_block_new_live_at_end, n_basic_blocks,
		      &flow_obstack);

  basic_block_significant
    = (regset *) alloca (n_basic_blocks * sizeof (regset));
  init_regset_vector (basic_block_significant, n_basic_blocks, &flow_obstack);

  /* Record which insns refer to any volatile memory
     or for any reason can't be deleted just because they are dead stores.
     Also, delete any insns that copy a register to itself.  */

  for (insn = f; insn; insn = NEXT_INSN (insn))
    {
      enum rtx_code code1 = GET_CODE (insn);
      if (code1 == CALL_INSN)
	INSN_VOLATILE (insn) = 1;
      else if (code1 == INSN || code1 == JUMP_INSN)
	{
	  /* Delete (in effect) any obvious no-op moves.  */
	  if (GET_CODE (PATTERN (insn)) == SET
	      && GET_CODE (SET_DEST (PATTERN (insn))) == REG
	      && GET_CODE (SET_SRC (PATTERN (insn))) == REG
	      && (REGNO (SET_DEST (PATTERN (insn)))
		  == REGNO (SET_SRC (PATTERN (insn))))
	      /* 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;
	    }
	  /* Delete (in effect) any obvious no-op moves.  */
	  else if (GET_CODE (PATTERN (insn)) == SET
	      && GET_CODE (SET_DEST (PATTERN (insn))) == SUBREG
	      && GET_CODE (SUBREG_REG (SET_DEST (PATTERN (insn)))) == REG
	      && GET_CODE (SET_SRC (PATTERN (insn))) == SUBREG
	      && GET_CODE (SUBREG_REG (SET_SRC (PATTERN (insn)))) == REG
	      && (REGNO (SUBREG_REG (SET_DEST (PATTERN (insn))))
		  == REGNO (SUBREG_REG (SET_SRC (PATTERN (insn)))))
	      && SUBREG_WORD (SET_DEST (PATTERN (insn))) ==
			      SUBREG_WORD (SET_SRC (PATTERN (insn)))
	      /* 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 if (GET_CODE (PATTERN (insn)) == PARALLEL)
	    {
	      /* 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.  */
	SET_REGNO_REG_SET (basic_block_live_at_end[n_basic_blocks - 1],
			   STACK_POINTER_REGNUM);
	SET_REGNO_REG_SET (basic_block_new_live_at_end[n_basic_blocks - 1],
			   STACK_POINTER_REGNUM);
      }

  /* 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)
    {
      SET_REGNO_REG_SET (basic_block_live_at_end[n_basic_blocks - 1],
			 FRAME_POINTER_REGNUM);
      SET_REGNO_REG_SET (basic_block_new_live_at_end[n_basic_blocks - 1],
			 FRAME_POINTER_REGNUM);
#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
      /* If they are different, also mark the hard frame pointer as live */
      SET_REGNO_REG_SET (basic_block_live_at_end[n_basic_blocks - 1],
			 HARD_FRAME_POINTER_REGNUM);
      SET_REGNO_REG_SET (basic_block_new_live_at_end[n_basic_blocks - 1],
			 HARD_FRAME_POINTER_REGNUM);
#endif      
      }

  /* Mark all global registers and all registers used by the epilogue
     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]
#ifdef EPILOGUE_USES
	  || EPILOGUE_USES (i)
#endif
	  )
	{
	  SET_REGNO_REG_SET (basic_block_live_at_end[n_basic_blocks - 1], i);
	  SET_REGNO_REG_SET (basic_block_new_live_at_end[n_basic_blocks - 1], i);
	}

  /* 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).  */

	      EXECUTE_IF_AND_COMPL_IN_REG_SET
		(basic_block_new_live_at_end[i],
		 basic_block_live_at_end[i], 0, j,
		 {
		   consider = 1;
		   if (REGNO_REG_SET_P (basic_block_significant[i], j))
		     {
		       must_rescan = 1;
		       goto done;
		     }
		 });
	    done:
	      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.  */
	      IOR_AND_COMPL_REG_SET (basic_block_live_at_start[i],
				     basic_block_new_live_at_end[i],
				     basic_block_live_at_end[i]);

	      IOR_AND_COMPL_REG_SET (basic_block_live_at_end[i],
				     basic_block_new_live_at_end[i],
				     basic_block_live_at_end[i]);
	    }
	  else
	    {
	      /* Update the basic_block_live_at_start
		 by propagation backwards through the block.  */
	      COPY_REG_SET (basic_block_live_at_end[i],
			    basic_block_new_live_at_end[i]);
	      COPY_REG_SET (basic_block_live_at_start[i],
			    basic_block_live_at_end[i]);
	      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];
	    if (basic_block_drops_in[i])
	      IOR_REG_SET (basic_block_new_live_at_end[i-1],
			   basic_block_live_at_start[i]);

	    /* 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));
		  IOR_REG_SET (basic_block_new_live_at_end[from_block],
			       basic_block_live_at_start[i]);
		}
	  }
#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)
    EXECUTE_IF_SET_IN_REG_SET (basic_block_live_at_start[0],
			       FIRST_PSEUDO_REGISTER, i,
			       {
				 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
  EXECUTE_IF_SET_IN_REG_SET (regs_live_at_setjmp,
			     FIRST_PSEUDO_REGISTER, i,
			     {
			       if (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.  */
  EXECUTE_IF_SET_IN_REG_SET (regs_live_at_setjmp,
			     FIRST_PSEUDO_REGISTER, i,
			     {
			       if (regno_reg_rtx[i] != 0)
				 {
				   REG_LIVE_LENGTH (i) = -1;