flow.c

GCC编译器源代码

  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
			   && ! find_reg_note (insn, REG_RETVAL, NULL_RTX))
		       || 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;

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

  for (x = exception_handler_labels; x; x = XEXP (x, 1))
    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.  */

      for (insn = f; insn; insn = NEXT_INSN (insn))
	if (computed_jump_p (insn))
	  {
	    if (label_value_list_marked_live == 0)
	      {
		label_value_list_marked_live = 1;

		/* This could be made smarter by only considering
		   these live, if the computed goto is live.  */

		/* 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 = 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
	    && ! find_reg_note (insn, REG_RETVAL, NULL_RTX))
	  {
	    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.  */
	  }

      /* All blocks associated with labels in label_value_list are
	 trivially considered as marked live, if the list is empty.
	 We do this to speed up the below code.  */

      if (label_value_list == 0)
	label_value_list_marked_live = 1;

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

		if (label_value_list_marked_live == 0)
		  /* Now that we know that this block is live, mark as
		     live, all the blocks that we might be able to get
		     to as live.  */

		  for (insn = basic_block_head[i];
		       insn != NEXT_INSN (basic_block_end[i]);
		       insn = NEXT_INSN (insn))
		    {
		      if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
			{
			  for (note = REG_NOTES (insn);
			       note;
			       note = XEXP (note, 1))
			    if (REG_NOTE_KIND (note) == REG_LABEL)
			      {
				x = XEXP (note, 0);
				block_live[BLOCK_NUM (x)] = 1;
			      }
			}
		    }
	      }
	}

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

/* Check expression X for label references;
   if one is found, add INSN to the label's chain of references.

   CHECKDUP means check for and avoid creating duplicate references
   from the same insn.  Such duplicates do no serious harm but
   can slow life analysis.  CHECKDUP is set only when duplicates
   are likely.  */

static void
mark_label_ref (x, insn, checkdup)
     rtx x, insn;
     int checkdup;
{
  register RTX_CODE code;
  register int i;
  register char *fmt;

  /* We can be called with NULL when scanning label_value_list.  */
  if (x == 0)
    return;

  code = GET_CODE (x);
  if (code == LABEL_REF)
    {
      register rtx label = XEXP (x, 0);
      register rtx y;
      if (GET_CODE (label) != CODE_LABEL)
	abort ();
      /* If the label was never emitted, this insn is junk,
	 but avoid a crash trying to refer to BLOCK_NUM (label).
	 This can happen as a result of a syntax error
	 and a diagnostic has already been printed.  */
      if (INSN_UID (label) == 0)
	return;
      CONTAINING_INSN (x) = insn;
      /* if CHECKDUP is set, check for duplicate ref from same insn
	 and don't insert.  */
      if (checkdup)
	for (y = LABEL_REFS (label); y != label; y = LABEL_NEXTREF (y))
	  if (CONTAINING_INSN (y) == insn)
	    return;
      LABEL_NEXTREF (x) = LABEL_REFS (label);
      LABEL_REFS (label) = x;
      block_live_static[BLOCK_NUM (label)] = 1;
      return;
    }

  fmt = GET_RTX_FORMAT (code);
  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
    {
      if (fmt[i] == 'e')
	mark_label_ref (XEXP (x, i), insn, 0);
      if (fmt[i] == 'E')
	{
	  register int j;
	  for (j = 0; j < XVECLEN (x, i); j++)
	    mark_label_ref (XVECEXP (x, i, j), insn, 1);
	}
    }
}