unroll.c

早期freebsd实现

		  /* The value in splittable_regs may be an invariant
		     value, so we must use plus_constant here.  */
		  splittable_regs[regno]
		    = plus_constant (splittable_regs[regno], INTVAL (giv_inc));

		  if (GET_CODE (splittable_regs[regno]) == PLUS)
		    {
		      giv_src_reg = XEXP (splittable_regs[regno], 0);
		      giv_inc = XEXP (splittable_regs[regno], 1);
		    }
		  else
		    {
		      /* The splittable_regs value must be a REG or a
			 CONST_INT, so put the entire value in the giv_src_reg
			 variable.  */
		      giv_src_reg = splittable_regs[regno];
		      giv_inc = const0_rtx;
		    }
		}
	      else
		{
		  /* Partially unrolling loop.  Create a new pseudo
		     register for the iteration variable, and set it to
		     be a constant plus the original register.  Except
		     on the last iteration, when the result has to
		     go back into the original iteration var register.  */
		  
		  /* Handle bivs which must be mapped to a new register
		     when split.  This happens for bivs which need their
		     final value set before loop entry.  The new register
		     for the biv was stored in the biv's first struct
		     induction entry by find_splittable_regs.  */

		  if (regno < max_reg_before_loop
		      && reg_iv_type[regno] == BASIC_INDUCT)
		    {
		      giv_src_reg = reg_biv_class[regno]->biv->src_reg;
		      giv_dest_reg = giv_src_reg;
		    }
		  
#if 0
		  /* If non-reduced/final-value givs were split, then
		     this would have to remap those givs also.  See
		     find_splittable_regs.  */
#endif
		  
		  splittable_regs[regno]
		    = GEN_INT (INTVAL (giv_inc)
			       + INTVAL (splittable_regs[regno]));
		  giv_inc = splittable_regs[regno];
		  
		  /* Now split the induction variable by changing the dest
		     of this insn to a new register, and setting its
		     reg_map entry to point to this new register.

		     If this is the last iteration, and this is the last insn
		     that will update the iv, then reuse the original dest,
		     to ensure that the iv will have the proper value when
		     the loop exits or repeats.

		     Using splittable_regs_updates here like this is safe,
		     because it can only be greater than one if all
		     instructions modifying the iv are always executed in
		     order.  */

		  if (! last_iteration
		      || (splittable_regs_updates[regno]-- != 1))
		    {
		      tem = gen_reg_rtx (GET_MODE (giv_src_reg));
		      giv_dest_reg = tem;
		      map->reg_map[regno] = tem;
		    }
		  else
		    map->reg_map[regno] = giv_src_reg;
		}

	      /* The constant being added could be too large for an add
		 immediate, so can't directly emit an insn here.  */
	      emit_unrolled_add (giv_dest_reg, giv_src_reg, giv_inc);
	      copy = get_last_insn ();
	      pattern = PATTERN (copy);
	    }
	  else
	    {
	      pattern = copy_rtx_and_substitute (pattern, map);
	      copy = emit_insn (pattern);
	    }
	  /* REG_NOTES will be copied later.  */
	  
#ifdef HAVE_cc0
	  /* If this insn is setting CC0, it may need to look at
	     the insn that uses CC0 to see what type of insn it is.
	     In that case, the call to recog via validate_change will
	     fail.  So don't substitute constants here.  Instead,
	     do it when we emit the following insn.

	     For example, see the pyr.md file.  That machine has signed and
	     unsigned compares.  The compare patterns must check the
	     following branch insn to see which what kind of compare to
	     emit.

	     If the previous insn set CC0, substitute constants on it as
	     well.  */
	  if (sets_cc0_p (copy) != 0)
	    cc0_insn = copy;
	  else
	    {
	      if (cc0_insn)
		try_constants (cc0_insn, map);
	      cc0_insn = 0;
	      try_constants (copy, map);
	    }
#else
	  try_constants (copy, map);
#endif

	  /* Make split induction variable constants `permanent' since we
	     know there are no backward branches across iteration variable
	     settings which would invalidate this.  */
	  if (dest_reg_was_split)
	    {
	      int regno = REGNO (SET_DEST (pattern));

	      if (map->const_age_map[regno] == map->const_age)
		map->const_age_map[regno] = -1;
	    }
	  break;
	  
	case JUMP_INSN:
	  if (JUMP_LABEL (insn) == start_label && insn == copy_end
	      && ! last_iteration)
	    {
	      /* This is a branch to the beginning of the loop; this is the
		 last insn being copied; and this is not the last iteration.
		 In this case, we want to change the original fall through
		 case to be a branch past the end of the loop, and the
		 original jump label case to fall_through.  */
	      /* Never map the label in this case.  */

	      pattern = copy_rtx (PATTERN (insn));
	      copy = emit_jump_insn (pattern);

	      if (! invert_exp (pattern, copy)
		  || ! redirect_exp (&pattern, JUMP_LABEL (insn),
				     exit_label, copy))
		abort ();
	    }
	  else
	    {
	      pattern = copy_rtx_and_substitute (PATTERN (insn), map);
	      copy = emit_jump_insn (pattern);
	    }
	  
#ifdef HAVE_cc0
	  if (cc0_insn)
	    try_constants (cc0_insn, map);
	  cc0_insn = 0;
#endif
	  try_constants (copy, map);

	  /* Set the jump label of COPY correctly to avoid problems with
	     later passes of unroll_loop, if INSN had jump label set.  */
	  if (JUMP_LABEL (insn))
	    {
	      rtx label = 0;

	      /* Can't use the label_map for every insn, since this may be
		 the backward branch, and hence the label was not mapped.  */
	      if (GET_CODE (pattern) == SET)
		{
		  tem = SET_SRC (pattern);
		  if (GET_CODE (tem) == LABEL_REF)
		    label = XEXP (tem, 0);
		  else if (GET_CODE (tem) == IF_THEN_ELSE)
		    {
		      if (XEXP (tem, 1) != pc_rtx)
			label = XEXP (XEXP (tem, 1), 0);
		      else
			label = XEXP (XEXP (tem, 2), 0);
		    }
		}

	      if (label && GET_CODE (label) == CODE_LABEL)
		JUMP_LABEL (copy) = label;
	      else
		{
		  /* An unrecognizable jump insn, probably the entry jump
		     for a switch statement.  This label must have been mapped,
		     so just use the label_map to get the new jump label.  */
		  JUMP_LABEL (copy) = map->label_map[CODE_LABEL_NUMBER
						     (JUMP_LABEL (insn))];
		}
	  
	      /* If this is a non-local jump, then must increase the label
		 use count so that the label will not be deleted when the
		 original jump is deleted.  */
	      LABEL_NUSES (JUMP_LABEL (copy))++;
	    }
	  else if (GET_CODE (PATTERN (copy)) == ADDR_VEC
		   || GET_CODE (PATTERN (copy)) == ADDR_DIFF_VEC)
	    {
	      rtx pat = PATTERN (copy);
	      int diff_vec_p = GET_CODE (pat) == ADDR_DIFF_VEC;
	      int len = XVECLEN (pat, diff_vec_p);
	      int i;

	      for (i = 0; i < len; i++)
		LABEL_NUSES (XEXP (XVECEXP (pat, diff_vec_p, i), 0))++;
	    }

	  /* If this used to be a conditional jump insn but whose branch
	     direction is now known, we must do something special.  */
	  if (condjump_p (insn) && !simplejump_p (insn) && map->last_pc_value)
	    {
#ifdef HAVE_cc0
	      /* The previous insn set cc0 for us.  So delete it.  */
	      delete_insn (PREV_INSN (copy));
#endif

	      /* If this is now a no-op, delete it.  */
	      if (map->last_pc_value == pc_rtx)
		{
		  delete_insn (copy);
		  copy = 0;
		}
	      else
		/* Otherwise, this is unconditional jump so we must put a
		   BARRIER after it.  We could do some dead code elimination
		   here, but jump.c will do it just as well.  */
		emit_barrier ();
	    }
	  break;
	  
	case CALL_INSN:
	  pattern = copy_rtx_and_substitute (PATTERN (insn), map);
	  copy = emit_call_insn (pattern);

#ifdef HAVE_cc0
	  if (cc0_insn)
	    try_constants (cc0_insn, map);
	  cc0_insn = 0;
#endif
	  try_constants (copy, map);

	  /* Be lazy and assume CALL_INSNs clobber all hard registers.  */
	  for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
	    map->const_equiv_map[i] = 0;
	  break;
	  
	case CODE_LABEL:
	  /* If this is the loop start label, then we don't need to emit a
	     copy of this label since no one will use it.  */

	  if (insn != start_label)
	    {
	      copy = emit_label (map->label_map[CODE_LABEL_NUMBER (insn)]);
	      map->const_age++;
	    }
	  break;
	  
	case BARRIER:
	  copy = emit_barrier ();
	  break;
	  
	case NOTE:
	  /* VTOP notes are valid only before the loop exit test.  If placed
	     anywhere else, loop may generate bad code.  */
	     
	  if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_DELETED
	      && (NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_VTOP
		  || (last_iteration && unroll_type != UNROLL_COMPLETELY)))
	    copy = emit_note (NOTE_SOURCE_FILE (insn),
			      NOTE_LINE_NUMBER (insn));
	  else
	    copy = 0;
	  break;
	  
	default:
	  abort ();
	  break;
	}
      
      map->insn_map[INSN_UID (insn)] = copy;
    }
  while (insn != copy_end);
  
  /* Now copy the REG_NOTES.  */
  insn = copy_start;
  do
    {
      insn = NEXT_INSN (insn);
      if ((GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN
	   || GET_CODE (insn) == CALL_INSN)
	  && map->insn_map[INSN_UID (insn)])
	REG_NOTES (map->insn_map[INSN_UID (insn)])
	  = copy_rtx_and_substitute (REG_NOTES (insn), map);
    }
  while (insn != copy_end);

  /* There may be notes between copy_notes_from and loop_end.  Emit a copy of
     each of these notes here, since there may be some important ones, such as
     NOTE_INSN_BLOCK_END notes, in this group.  We don't do this on the last
     iteration, because the original notes won't be deleted.

     We can't use insert_before here, because when from preconditioning,
     insert_before points before the loop.  We can't use copy_end, because
     there may be insns already inserted after it (which we don't want to
     copy) when not from preconditioning code.  */

  if (! last_iteration)
    {
      for (insn = copy_notes_from; insn != loop_end; insn = NEXT_INSN (insn))
	{
	  if (GET_CODE (insn) == NOTE
	      && NOTE_LINE_NUMBER (insn) != NOTE_INSN_DELETED)
	    emit_note (NOTE_SOURCE_FILE (insn), NOTE_LINE_NUMBER (insn));
	}
    }

  if (final_label && LABEL_NUSES (final_label) > 0)
    emit_label (final_label);

  tem = gen_sequence ();
  end_sequence ();
  emit_insn_before (tem, insert_before);
}

/* Emit an insn, using the expand_binop to ensure that a valid insn is
   emitted.  This will correctly handle the case where the increment value
   won't fit in the immediate field of a PLUS insns.  */

void
emit_unrolled_add (dest_reg, src_reg, increment)
     rtx dest_reg, src_reg, increment;
{
  rtx result;

  result = expand_binop (GET_MODE (dest_reg), add_optab, src_reg, increment,
			 dest_reg, 0, OPTAB_LIB_WIDEN);

  if (dest_reg != result)
    emit_move_insn (dest_reg, result);
}

/* Searches the insns between INSN and LOOP_END.  Returns 1 if there
   is a backward branch in that range that branches to somewhere between
   LOOP_START and INSN.  Returns 0 otherwise.  */

/* ??? This is quadratic algorithm.  Could be rewritten to be linear.
   In practice, this is not a problem, because this function is seldom called,
   and uses a negligible amount of CPU time on average.  */

static int
back_branch_in_range_p (insn, loop_start, loop_end)
     rtx insn;
     rtx loop_start, loop_end;
{
  rtx p, q, target_insn;

  /* Stop before we get to the backward branch at the end of the loop.  */
  loop_end = prev_nonnote_insn (loop_end);
  if (GET_CODE (loop_end) == BARRIER)
    loop_end = PREV_INSN (loop_end);

  /* Check in case insn has been deleted, search forward for first non
     deleted insn following it.  */
  while (INSN_DELETED_P (insn))
    insn = NEXT_INSN (insn);

  /* Check for the case where insn is the last insn in the loop.  */
  if (insn == loop_end)
    return 0;

  for (p = NEXT_INSN (insn); p != loop_end; p = NEXT_INSN (p))
    {
      if (GET_CODE (p) == JUMP_INSN)
	{
	  target_insn = JUMP_LABEL (p);
	  
	  /* Search from loop_start to insn, to see if one of them is
	     the target_insn.  We can't use INSN_LUI