reorg.c

GUN开源阻止下的编译器GCC

    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 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.

   PANNUL_P points to a non-zero value if we already know that we need
   to annul INSN.  If this routine determines that annulling is needed,
   it may set that value non-zero.

   PNEW_THREAD points to a location that is to receive the place at which
   execution should continue.  */

static rtx
steal_delay_list_from_target (insn, condition, seq, delay_list,
			      sets, needed, other_needed,
			      slots_to_fill, pslots_filled, pannul_p,
			      pnew_thread)
     rtx insn, condition;
     rtx seq;
     rtx delay_list;
     struct resources *sets, *needed, *other_needed;
     int slots_to_fill;
     int *pslots_filled;
     int *pannul_p;
     rtx *pnew_thread;
{
  rtx temp;
  int slots_remaining = slots_to_fill - *pslots_filled;
  int total_slots_filled = *pslots_filled;
  rtx new_delay_list = 0;
  int must_annul = *pannul_p;
  int i;

  /* We can't do anything if there are more delay slots in SEQ than we
     can handle, or if we don't know that it will be a taken branch.
     We know that it will be a taken branch if it is either an unconditional
     branch or a conditional branch with a stricter branch condition.

     Also, exit if the branch has more than one set, since then it is computing
     other results that can't be ignored, e.g. the HPPA mov&branch instruction.
     ??? It may be possible to move other sets into INSN in addition to
     moving the instructions in the delay slots.  */

  if (XVECLEN (seq, 0) - 1 > slots_remaining
      || ! condition_dominates_p (condition, XVECEXP (seq, 0, 0))