reorg.c

GCC编译器源代码

	     the jump to TARGET_LABEL may change the direction of the
	     jump (which may change the circumstances in which the
	     delay slot is nullified).  */
	  flags = get_jump_flags (insn, target_label);
	  if (eligible_for_annul_true (insn, 0, trial, flags))
	    reorg_redirect_jump (insn, target_label);
	}

      INSN_ANNULLED_BRANCH_P (insn) = 1;
    }

  return delay_list;
}
#endif


/*  Encode and return branch direction and prediction information for
    INSN assuming it will jump to LABEL.

    Non conditional branches return no direction information and
    are predicted as very likely taken.  */

static int
get_jump_flags (insn, label)
     rtx insn, label;
{
  int flags;

  /* get_jump_flags can be passed any insn with delay slots, these may
     be INSNs, CALL_INSNs, or JUMP_INSNs.  Only JUMP_INSNs have branch
     direction information, and only if they are conditional jumps.

     If LABEL is zero, then there is no way to determine the branch
     direction.  */
  if (GET_CODE (insn) == JUMP_INSN
      && (condjump_p (insn) || condjump_in_parallel_p (insn))
      && INSN_UID (insn) <= max_uid
      && label != 0
      && INSN_UID (label) <= max_uid)
    flags 
      = (uid_to_ruid[INSN_UID (label)] > uid_to_ruid[INSN_UID (insn)])
	 ? ATTR_FLAG_forward : ATTR_FLAG_backward;
  /* No valid direction information.  */
  else
    flags = 0;
  
  /* If insn is a conditional branch call mostly_true_jump to get
     determine the branch prediction.  

     Non conditional branches are predicted as very likely taken.  */
  if (GET_CODE (insn) == JUMP_INSN
      && (condjump_p (insn) || condjump_in_parallel_p (insn)))
    {
      int prediction;

      prediction = mostly_true_jump (insn, get_branch_condition (insn, label));
      switch (prediction)
	{
	  case 2:
	    flags |= (ATTR_FLAG_very_likely | ATTR_FLAG_likely);
	    break;
	  case 1:
	    flags |= ATTR_FLAG_likely;
	    break;
	  case 0:
	    flags |= ATTR_FLAG_unlikely;
	    break;
	  case -1:
	    flags |= (ATTR_FLAG_very_unlikely | ATTR_FLAG_unlikely);
	    break;

	  default:
	    abort();
	}
    }
  else
    flags |= (ATTR_FLAG_very_likely | ATTR_FLAG_likely);

  return flags;
}

/* Return 1 if INSN is a destination that will be branched to rarely (the
   return point of a function); return 2 if DEST will be branched to very
   rarely (a call to a function that doesn't return).  Otherwise,
   return 0.  */

static int
rare_destination (insn)
     rtx insn;
{
  int jump_count = 0;
  rtx next;

  for (; insn; insn = next)
    {
      if (GET_CODE (insn) == INSN && GET_CODE (PATTERN (insn)) == SEQUENCE)
	insn = XVECEXP (PATTERN (insn), 0, 0);

      next = NEXT_INSN (insn);

      switch (GET_CODE (insn))
	{
	case CODE_LABEL:
	  return 0;
	case BARRIER:
	  /* A BARRIER can either be after a JUMP_INSN or a CALL_INSN.  We 
	     don't scan past JUMP_INSNs, so any barrier we find here must
	     have been after a CALL_INSN and hence mean the call doesn't
	     return.  */
	  return 2;
	case JUMP_INSN:
	  if (GET_CODE (PATTERN (insn)) == RETURN)
	    return 1;
	  else if (simplejump_p (insn)
		   && jump_count++ < 10)
	    next = JUMP_LABEL (insn);
	  else
	    return 0;
	}
    }

  /* If we got here it means we hit the end of the function.  So this
     is an unlikely destination.  */

  return 1;
}

/* Return truth value of the statement that this branch
   is mostly taken.  If we think that the branch is extremely likely
   to be taken, we return 2.  If the branch is slightly more likely to be
   taken, return 1.  If the branch is slightly less likely to be taken,
   return 0 and if the branch is highly unlikely to be taken, return -1.

   CONDITION, if non-zero, is the condition that JUMP_INSN is testing.  */

static int
mostly_true_jump (jump_insn, condition)
     rtx jump_insn, condition;
{
  rtx target_label = JUMP_LABEL (jump_insn);
  rtx insn;
  int rare_dest = rare_destination (target_label);
  int rare_fallthrough = rare_destination (NEXT_INSN (jump_insn));

  /* If branch probabilities are available, then use that number since it
     always gives a correct answer.  */
  if (flag_branch_probabilities)
    {
      rtx note = find_reg_note (jump_insn, REG_BR_PROB, 0);;
      if (note)
	{
	  int prob = XINT (note, 0);

	  if (prob >= REG_BR_PROB_BASE * 9 / 10)
	    return 2;
	  else if (prob >= REG_BR_PROB_BASE / 2)
	    return 1;
	  else if (prob >= REG_BR_PROB_BASE / 10)
	    return 0;
	  else
	    return -1;
	}
    }

  /* If this is a branch outside a loop, it is highly unlikely.  */
  if (GET_CODE (PATTERN (jump_insn)) == SET
      && GET_CODE (SET_SRC (PATTERN (jump_insn))) == IF_THEN_ELSE
      && ((GET_CODE (XEXP (SET_SRC (PATTERN (jump_insn)), 1)) == LABEL_REF
	   && LABEL_OUTSIDE_LOOP_P (XEXP (SET_SRC (PATTERN (jump_insn)), 1)))
	  || (GET_CODE (XEXP (SET_SRC (PATTERN (jump_insn)), 2)) == LABEL_REF
	      && LABEL_OUTSIDE_LOOP_P (XEXP (SET_SRC (PATTERN (jump_insn)), 2)))))
    return -1;

  if (target_label)
    {
      /* If this is the test of a loop, it is very likely true.  We scan
	 backwards from the target label.  If we find a NOTE_INSN_LOOP_BEG
	 before the next real insn, we assume the branch is to the top of 
	 the loop.  */
      for (insn = PREV_INSN (target_label);
	   insn && GET_CODE (insn) == NOTE;
	   insn = PREV_INSN (insn))
	if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
	  return 2;

      /* If this is a jump to the test of a loop, it is likely true.  We scan
	 forwards from the target label.  If we find a NOTE_INSN_LOOP_VTOP
	 before the next real insn, we assume the branch is to the loop branch
	 test.  */
      for (insn = NEXT_INSN (target_label);
	   insn && GET_CODE (insn) == NOTE;
	   insn = PREV_INSN (insn))
	if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_VTOP)
	  return 1;
    }

  /* Look at the relative rarities of the fallthrough and destination.  If
     they differ, we can predict the branch that way.  */

  switch (rare_fallthrough - rare_dest)
    {
    case -2:
      return -1;
    case -1:
      return 0;
    case 0:
      break;
    case 1:
      return 1;
    case 2:
      return 2;
    }

  /* If we couldn't figure out what this jump was, assume it won't be 
     taken.  This should be rare.  */
  if (condition == 0)
    return 0;

  /* EQ tests are usually false and NE tests are usually true.  Also,
     most quantities are positive, so we can make the appropriate guesses
     about signed comparisons against zero.  */
  switch (GET_CODE (condition))
    {
    case CONST_INT:
      /* Unconditional branch.  */
      return 1;
    case EQ:
      return 0;
    case NE:
      return 1;
    case LE:
    case LT:
      if (XEXP (condition, 1) == const0_rtx)
        return 0;
      break;
    case GE:
    case GT:
      if (XEXP (condition, 1) == const0_rtx)
	return 1;
      break;
    }

  /* Predict backward branches usually take, forward branches usually not.  If
     we don't know whether this is forward or backward, assume the branch
     will be taken, since most are.  */
  return (target_label == 0 || INSN_UID (jump_insn) > max_uid
	  || INSN_UID (target_label) > max_uid
	  || (uid_to_ruid[INSN_UID (jump_insn)]
	      > uid_to_ruid[INSN_UID (target_label)]));;
}

/* Return the condition under which INSN will branch to TARGET.  If TARGET
   is zero, return the condition under which INSN will return.  If INSN is
   an unconditional branch, return const_true_rtx.  If INSN isn't a simple
   type of jump, or it doesn't go to TARGET, return 0.  */

static rtx
get_branch_condition (insn, target)
     rtx insn;
     rtx target;
{
  rtx pat = PATTERN (insn);
  rtx src;
  
  if (condjump_in_parallel_p (insn))
    pat = XVECEXP (pat, 0, 0);

  if (GET_CODE (pat) == RETURN)
    return target == 0 ? const_true_rtx : 0;

  else if (GET_CODE (pat) != SET || SET_DEST (pat) != pc_rtx)
    return 0;

  src = SET_SRC (pat);
  if (GET_CODE (src) == LABEL_REF && XEXP (src, 0) == target)
    return const_true_rtx;

  else if (GET_CODE (src) == IF_THEN_ELSE
	   && ((target == 0 && GET_CODE (XEXP (src, 1)) == RETURN)
	       || (GET_CODE (XEXP (src, 1)) == LABEL_REF
		   && XEXP (XEXP (src, 1), 0) == target))
	   && XEXP (src, 2) == pc_rtx)
    return XEXP (src, 0);

  else if (GET_CODE (src) == IF_THEN_ELSE
	   && ((target == 0 && GET_CODE (XEXP (src, 2)) == RETURN)
	       || (GET_CODE (XEXP (src, 2)) == LABEL_REF
		   && XEXP (XEXP (src, 2), 0) == target))
	   && XEXP (src, 1) == pc_rtx)
    return gen_rtx (reverse_condition (GET_CODE (XEXP (src, 0))),
		    GET_MODE (XEXP (src, 0)),
		    XEXP (XEXP (src, 0), 0), XEXP (XEXP (src, 0), 1));

  return 0;
}

/* Return non-zero if CONDITION is more strict than the condition of
   INSN, i.e., if INSN will always branch if CONDITION is true.  */

static int
condition_dominates_p (condition, insn)
     rtx condition;
     rtx insn;
{
  rtx other_condition = get_branch_condition (insn, JUMP_LABEL (insn));
  enum rtx_code code = GET_CODE (condition);
  enum rtx_code other_code;

  if (rtx_equal_p (condition, other_condition)
      || other_condition == const_true_rtx)
    return 1;

  else if (condition == const_true_rtx || other_condition == 0)
    return 0;

  other_code = GET_CODE (other_condition);
  if (GET_RTX_LENGTH (code) != 2 || GET_RTX_LENGTH (other_code) != 2
      || ! rtx_equal_p (XEXP (condition, 0), XEXP (other_condition, 0))
      || ! rtx_equal_p (XEXP (condition, 1), XEXP (other_condition, 1)))
    return 0;

  return comparison_dominates_p (code, other_code);
}

/* Return non-zero if redirecting JUMP to NEWLABEL does not invalidate
   any insns already in the delay slot of JUMP.  */

static int
redirect_with_delay_slots_safe_p (jump, newlabel, seq)
     rtx jump, newlabel, seq;
{
  int flags, slots, i;
  rtx pat = PATTERN (seq);

  /* Make sure all the delay slots of this jump would still
     be valid after threading the jump.  If they are still
     valid, then return non-zero.  */

  flags = get_jump_flags (jump, newlabel);
  for (i = 1; i < XVECLEN (pat, 0); i++)
    if (! (
#ifdef ANNUL_IFFALSE_SLOTS
	   (INSN_ANNULLED_BRANCH_P (jump)
	    && INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
	   ? eligible_for_annul_false (jump, i - 1,
				       XVECEXP (pat, 0, i), flags) :
#endif
#ifdef ANNUL_IFTRUE_SLOTS
	   (INSN_ANNULLED_BRANCH_P (jump)
	    && ! INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
	   ? eligible_for_annul_true (jump, i - 1,
				      XVECEXP (pat, 0, i), flags) :
#endif
	   eligible_for_delay (jump, i -1, XVECEXP (pat, 0, i), flags)))
      break;

  return (i == XVECLEN (pat, 0));
}

/* Return non-zero if redirecting JUMP to NEWLABEL does not invalidate
   any insns we wish to place in the delay slot of JUMP.  */

static int
redirect_with_delay_list_safe_p (jump, newlabel, delay_list)
     rtx jump, newlabel, delay_list;
{
  int flags, i;
  rtx li;

  /* Make sure all the insns in DELAY_LIST would still be
     valid after threading the jump.  If they are still
     valid, then return non-zero.  */

  flags = get_jump_flags (jump, newlabel);
  for (li = delay_list, i = 0; li; li = XEXP (li, 1), i++)
    if (! (
#ifdef ANNUL_IFFALSE_SLOTS
	   (INSN_ANNULLED_BRANCH_P (jump)
	    && INSN_FROM_TARGET_P (XEXP (li, 0)))
	   ? eligible_for_annul_false (jump, i, XEXP (li, 0), flags) :
#endif
#ifdef ANNUL_IFTRUE_SLOTS
	   (INSN_ANNULLED_BRANCH_P (jump)
	    && ! INSN_FROM_TARGET_P (XEXP (li, 0)))
	   ? eligible_for_annul_true (jump, i, XEXP (li, 0), flags) :
#endif
	   eligible_for_delay (jump, i, XEXP (li, 0), flags)))
      break;

  return (li == NULL);
}


/* INSN branches to an insn whose pattern SEQ is a SEQUENCE.  Given that
   the condition tested by INSN is CONDITION and the resources shown in
   OTHER_NEEDED are needed after INSN, see whether INSN can take all the insns
   from SEQ's delay list, in addition to whatever insns it may execute
   (in DELAY_LIST).   SETS and NEEDED are denote resources already set and
   needed while searching for delay slot insns.  Return the concatenated
   delay list if possible, otherwise, return 0.

   SLOTS_TO_FILL is the total number of slots required by INSN, and
   PSLOTS_FILLED points to the number filled so far (also the number of
   insns in DELAY_LIST).  It is updated with the number that have been
   filled from the SEQUENCE, if any.