flow.c

GUN开源阻止下的编译器GCC

   Store the correct data in the tables that describe the basic blocks,
   set up the chains of references for each CODE_LABEL, and
   delete any entire basic blocks that cannot be reached.

   NONLOCAL_LABEL_LIST is the same local variable from flow_analysis.  */

static void
find_basic_blocks (f, nonlocal_label_list)
     rtx f, nonlocal_label_list;
{
  register rtx insn;
  register int i;
  register char *block_live = (char *) alloca (n_basic_blocks);
  register char *block_marked = (char *) alloca (n_basic_blocks);
  /* List of label_refs to all labels whose addresses are taken
     and used as data.  */
  rtx label_value_list;
  rtx x, note;
  enum rtx_code prev_code, code;
  int depth, pass;

  pass = 1;
 restart:

  label_value_list = 0;
  block_live_static = block_live;
  bzero (block_live, n_basic_blocks);
  bzero (block_marked, n_basic_blocks);

  /* Initialize with just block 0 reachable and no blocks marked.  */
  if (n_basic_blocks > 0)
    block_live[0] = 1;

  /* Initialize the ref chain of each label to 0.  Record where all the
     blocks start and end and their depth in loops.  For each insn, record
     the block it is in.   Also mark as reachable any blocks headed by labels
     that must not be deleted.  */

  for (insn = f, i = -1, prev_code = JUMP_INSN, depth = 1;
       insn; insn = NEXT_INSN (insn))
    {
      code = GET_CODE (insn);
      if (code == NOTE)
	{
	  if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
	    depth++;
	  else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
	    depth--;
	}

      /* A basic block starts at label, or after something that can jump.  */
      else if (code == CODE_LABEL
	       || (GET_RTX_CLASS (code) == 'i'
		   && (prev_code == JUMP_INSN
		       || (prev_code == CALL_INSN
			   && nonlocal_label_list != 0)
		       || prev_code == BARRIER)))
	{
	  basic_block_head[++i] = insn;
	  basic_block_end[i] = insn;
	  basic_block_loop_depth[i] = depth;

	  if (code == CODE_LABEL)
	    {
		LABEL_REFS (insn) = insn;
		/* Any label that cannot be deleted
		   is considered to start a reachable block.  */
		if (LABEL_PRESERVE_P (insn))
		  block_live[i] = 1;
	      }
	}

      else if (GET_RTX_CLASS (code) == 'i')
	{
	  basic_block_end[i] = insn;
	  basic_block_loop_depth[i] = depth;
	}

      if (GET_RTX_CLASS (code) == 'i')
	{
	  /* Make a list of all labels referred to other than by jumps.  */
	  for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
	    if (REG_NOTE_KIND (note) == REG_LABEL)
	      label_value_list = gen_rtx (EXPR_LIST, VOIDmode, XEXP (note, 0),
					  label_value_list);
	}

      BLOCK_NUM (insn) = i;

      if (code != NOTE)
	prev_code = code;
    }

  /* During the second pass, `n_basic_blocks' is only an upper bound.
     Only perform the sanity check for the first pass, and on the second
     pass ensure `n_basic_blocks' is set to the correct value.  */
  if (pass == 1 && i + 1 != n_basic_blocks)
    abort ();
  n_basic_blocks = i + 1;

  /* Don't delete the labels (in this function)
     that are referenced by non-jump instructions.  */

  for (x = label_value_list; x; x = XEXP (x, 1))
    if (! LABEL_REF_NONLOCAL_P (x))
      block_live[BLOCK_NUM (XEXP (x, 0))] = 1;

  for (x = forced_labels; x; x = XEXP (x, 1))
    if (! LABEL_REF_NONLOCAL_P (x))
      block_live[BLOCK_NUM (XEXP (x, 0))] = 1;

  /* Record which basic blocks control can drop in to.  */

  for (i = 0; i < n_basic_blocks; i++)
    {
      for (insn = PREV_INSN (basic_block_head[i]);
	   insn && GET_CODE (insn) == NOTE; insn = PREV_INSN (insn))
	;

      basic_block_drops_in[i] = insn && GET_CODE (insn) != BARRIER;
    }

  /* Now find which basic blocks can actually be reached
     and put all jump insns' LABEL_REFS onto the ref-chains
     of their target labels.  */

  if (n_basic_blocks > 0)
    {
      int something_marked = 1;
      int deleted;

      /* Find all indirect jump insns and mark them as possibly jumping to all
	 the labels whose addresses are explicitly used.  This is because,
	 when there are computed gotos, we can't tell which labels they jump
	 to, of all the possibilities.

	 Tablejumps and casesi insns are OK and we can recognize them by
	 a (use (label_ref)).  */

      for (insn = f; insn; insn = NEXT_INSN (insn))
	if (GET_CODE (insn) == JUMP_INSN)
	  {
	    rtx pat = PATTERN (insn);
	    int computed_jump = 0;

	    if (GET_CODE (pat) == PARALLEL)
	      {
		int len = XVECLEN (pat, 0);
		int has_use_labelref = 0;

		for (i = len - 1; i >= 0; i--)
		  if (GET_CODE (XVECEXP (pat, 0, i)) == USE
		      && (GET_CODE (XEXP (XVECEXP (pat, 0, i), 0))
			  == LABEL_REF))
		    has_use_labelref = 1;

		if (! has_use_labelref)
		  for (i = len - 1; i >= 0; i--)
		    if (GET_CODE (XVECEXP (pat, 0, i)) == SET
			&& SET_DEST (XVECEXP (pat, 0, i)) == pc_rtx
			&& uses_reg_or_mem (SET_SRC (XVECEXP (pat, 0, i))))
		      computed_jump = 1;
	      }
	    else if (GET_CODE (pat) == SET
		     && SET_DEST (pat) == pc_rtx
		     && uses_reg_or_mem (SET_SRC (pat)))
	      computed_jump = 1;
		    
	    if (computed_jump)
	      {
		for (x = label_value_list; x; x = XEXP (x, 1))
		  mark_label_ref (gen_rtx (LABEL_REF, VOIDmode, XEXP (x, 0)),
				  insn, 0);

		for (x = forced_labels; x; x = XEXP (x, 1))
		  mark_label_ref (gen_rtx (LABEL_REF, VOIDmode, XEXP (x, 0)),
			      insn, 0);
	      }
	  }

      /* Find all call insns and mark them as possibly jumping
	 to all the nonlocal goto handler labels.  */

      for (insn = f; insn; insn = NEXT_INSN (insn))
	if (GET_CODE (insn) == CALL_INSN)
	  {
	    for (x = nonlocal_label_list; x; x = XEXP (x, 1))
	      mark_label_ref (gen_rtx (LABEL_REF, VOIDmode, XEXP (x, 0)),
			      insn, 0);

	    /* ??? This could be made smarter:
	       in some cases it's possible to tell that certain
	       calls will not do a nonlocal goto.

	       For example, if the nested functions that do the
	       nonlocal gotos do not have their addresses taken, then
	       only calls to those functions or to other nested
	       functions that use them could possibly do nonlocal
	       gotos.  */
	  }

      /* Pass over all blocks, marking each block that is reachable
	 and has not yet been marked.
	 Keep doing this until, in one pass, no blocks have been marked.
	 Then blocks_live and blocks_marked are identical and correct.
	 In addition, all jumps actually reachable have been marked.  */

      while (something_marked)
	{
	  something_marked = 0;
	  for (i = 0; i < n_basic_blocks; i++)
	    if (block_live[i] && !block_marked[i])
	      {
		block_marked[i] = 1;
		something_marked = 1;
		if (i + 1 < n_basic_blocks && basic_block_drops_in[i + 1])
		  block_live[i + 1] = 1;
		insn = basic_block_end[i];
		if (GET_CODE (insn) == JUMP_INSN)
		  mark_label_ref (PATTERN (insn), insn, 0);
	      }
	}

      /* ??? See if we have a "live" basic block that is not reachable.
	 This can happen if it is headed by a label that is preserved or
	 in one of the label lists, but no call or computed jump is in
	 the loop.  It's not clear if we can delete the block or not,
	 but don't for now.  However, we will mess up register status if
	 it remains unreachable, so add a fake reachability from the
	 previous block.  */

      for (i = 1; i < n_basic_blocks; i++)
	if (block_live[i] && ! basic_block_drops_in[i]
	    && GET_CODE (basic_block_head[i]) == CODE_LABEL
	    && LABEL_REFS (basic_block_head[i]) == basic_block_head[i])
	  basic_block_drops_in[i] = 1;

      /* Now delete the code for any basic blocks that can't be reached.
	 They can occur because jump_optimize does not recognize
	 unreachable loops as unreachable.  */

      deleted = 0;
      for (i = 0; i < n_basic_blocks; i++)
	if (!block_live[i])
	  {
	    deleted++;

	    /* Delete the insns in a (non-live) block.  We physically delete
	       every non-note insn except the start and end (so
	       basic_block_head/end needn't be updated), we turn the latter
	       into NOTE_INSN_DELETED notes.
	       We use to "delete" the insns by turning them into notes, but
	       we may be deleting lots of insns that subsequent passes would
	       otherwise have to process.  Secondly, lots of deleted blocks in
	       a row can really slow down propagate_block since it will
	       otherwise process insn-turned-notes multiple times when it
	       looks for loop begin/end notes.  */
	    if (basic_block_head[i] != basic_block_end[i])
	      {
		/* It would be quicker to delete all of these with a single
		   unchaining, rather than one at a time, but we need to keep
		   the NOTE's.  */
		insn = NEXT_INSN (basic_block_head[i]);
		while (insn != basic_block_end[i])
		  {
		    if (GET_CODE (insn) == BARRIER)
		      abort ();
		    else if (GET_CODE (insn) != NOTE)
		      insn = flow_delete_insn (insn);
		    else
		      insn = NEXT_INSN (insn);
		  }
	      }
	    insn = basic_block_head[i];
	    if (GET_CODE (insn) != NOTE)
	      {
		/* Turn the head into a deleted insn note.  */
		if (GET_CODE (insn) == BARRIER)
		  abort ();
		PUT_CODE (insn, NOTE);
		NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
		NOTE_SOURCE_FILE (insn) = 0;
	      }
	    insn = basic_block_end[i];
	    if (GET_CODE (insn) != NOTE)
	      {
		/* Turn the tail into a deleted insn note.  */
		if (GET_CODE (insn) == BARRIER)
		  abort ();
		PUT_CODE (insn, NOTE);
		NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
		NOTE_SOURCE_FILE (insn) = 0;
	      }
	    /* BARRIERs are between basic blocks, not part of one.
	       Delete a BARRIER if the preceding jump is deleted.
	       We cannot alter a BARRIER into a NOTE
	       because it is too short; but we can really delete
	       it because it is not part of a basic block.  */
	    if (NEXT_INSN (insn) != 0
		&& GET_CODE (NEXT_INSN (insn)) == BARRIER)
	      delete_insn (NEXT_INSN (insn));

	    /* Each time we delete some basic blocks,
	       see if there is a jump around them that is
	       being turned into a no-op.  If so, delete it.  */

	    if (block_live[i - 1])
	      {
		register int j;
		for (j = i + 1; j < n_basic_blocks; j++)
		  if (block_live[j])
		    {
		      rtx label;
		      insn = basic_block_end[i - 1];
		      if (GET_CODE (insn) == JUMP_INSN
			  /* An unconditional jump is the only possibility
			     we must check for, since a conditional one
			     would make these blocks live.  */
			  && simplejump_p (insn)
			  && (label = XEXP (SET_SRC (PATTERN (insn)), 0), 1)
			  && INSN_UID (label) != 0
			  && BLOCK_NUM (label) == j)
			{
			  PUT_CODE (insn, NOTE);
			  NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
			  NOTE_SOURCE_FILE (insn) = 0;
			  if (GET_CODE (NEXT_INSN (insn)) != BARRIER)
			    abort ();
			  delete_insn (NEXT_INSN (insn));
			}
		      break;
		    }
	      }
	  }

      /* There are pathological cases where one function calling hundreds of
	 nested inline functions can generate lots and lots of unreachable
	 blocks that jump can't delete.  Since we don't use sparse matrices
	 a lot of memory will be needed to compile such functions.
	 Implementing sparse matrices is a fair bit of work and it is not
	 clear that they win more than they lose (we don't want to
	 unnecessarily slow down compilation of normal code).  By making
	 another pass for the pathological case, we can greatly speed up
	 their compilation without hurting normal code.  This works because
	 all the insns in the unreachable blocks have either been deleted or
	 turned into notes.
	 Note that we're talking about reducing memory usage by 10's of
	 megabytes and reducing compilation time by several minutes.  */
      /* ??? The choice of when to make another pass is a bit arbitrary,
	 and was derived from empirical data.  */
      if (pass == 1
	  && deleted > 200)
	{
	  pass++;
	  n_basic_blocks -= deleted;
	  /* `n_basic_blocks' may not be correct at this point: two previously
	     separate blocks may now be merged.  That's ok though as we
	     recalculate it during the second pass.  It certainly can't be
	     any larger than the current value.  */
	  goto restart;
	}
    }
}

/* Subroutines of find_basic_blocks.  */

/* Return 1 if X contain a REG or MEM that is not in the constant pool.  */

static int
uses_reg_or_mem (x)
     rtx x;
{
  enum rtx_code code = GET_CODE (x);
  int i, j;
  char *fmt;

  if (code == REG
      || (code == MEM
	  && ! (GET_CODE (XEXP (x, 0)) == SYMBOL_REF
		&& CONSTANT_POOL_ADDRESS_P (XEXP (x, 0)))))
    return 1;

  fmt = GET_RTX_FORMAT (code);
  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
    {
      if (fmt[i] == 'e'
	  && uses_reg_or_mem (XEXP (x, i)))
	return 1;

      if (fmt[i] == 'E')
	for (j = 0; j < XVECLEN (x, i); j++)
	  if (uses_reg_or_mem (XVECEXP (x, i, j)))
	    return 1;
    }