unroll.c

GCC编译器源代码

  if (splitting_not_safe)
    temp = 0;
  else
    temp = find_splittable_regs (unroll_type, loop_start, loop_end,
				end_insert_before, unroll_number);

  /* find_splittable_regs may have created some new registers, so must
     reallocate the reg_map with the new larger size, and must realloc
     the constant maps also.  */

  maxregnum = max_reg_num ();
  map->reg_map = (rtx *) alloca (maxregnum * sizeof (rtx));

  init_reg_map (map, maxregnum);

  /* Space is needed in some of the map for new registers, so new_maxregnum
     is an (over)estimate of how many registers will exist at the end.  */
  new_maxregnum = maxregnum + (temp * unroll_number * 2);

  /* Must realloc space for the constant maps, because the number of registers
     may have changed.  */

  map->const_equiv_map = (rtx *) alloca (new_maxregnum * sizeof (rtx));
  map->const_age_map = (unsigned *) alloca (new_maxregnum * sizeof (unsigned));

  map->const_equiv_map_size = new_maxregnum;
  global_const_equiv_map = map->const_equiv_map;
  global_const_equiv_map_size = new_maxregnum;

  /* Search the list of bivs and givs to find ones which need to be remapped
     when split, and set their reg_map entry appropriately.  */

  for (bl = loop_iv_list; bl; bl = bl->next)
    {
      if (REGNO (bl->biv->src_reg) != bl->regno)
	map->reg_map[bl->regno] = bl->biv->src_reg;
#if 0
      /* Currently, non-reduced/final-value givs are never split.  */
      for (v = bl->giv; v; v = v->next_iv)
	if (REGNO (v->src_reg) != bl->regno)
	  map->reg_map[REGNO (v->dest_reg)] = v->src_reg;
#endif
    }

  /* Use our current register alignment and pointer flags.  */
  map->regno_pointer_flag = regno_pointer_flag;
  map->regno_pointer_align = regno_pointer_align;

  /* If the loop is being partially unrolled, and the iteration variables
     are being split, and are being renamed for the split, then must fix up
     the compare/jump instruction at the end of the loop to refer to the new
     registers.  This compare isn't copied, so the registers used in it
     will never be replaced if it isn't done here.  */

  if (unroll_type == UNROLL_MODULO)
    {
      insn = NEXT_INSN (copy_end);
      if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
	PATTERN (insn) = remap_split_bivs (PATTERN (insn));
    }

  /* For unroll_number - 1 times, make a copy of each instruction
     between copy_start and copy_end, and insert these new instructions
     before the end of the loop.  */

  for (i = 0; i < unroll_number; i++)
    {
      bzero ((char *) map->insn_map, max_insnno * sizeof (rtx));
      bzero ((char *) map->const_equiv_map, new_maxregnum * sizeof (rtx));
      bzero ((char *) map->const_age_map, new_maxregnum * sizeof (unsigned));
      map->const_age = 0;

      for (j = 0; j < max_labelno; j++)
	if (local_label[j])
	  map->label_map[j] = gen_label_rtx ();

      for (j = FIRST_PSEUDO_REGISTER; j < max_reg_before_loop; j++)
	if (local_regno[j])
	  map->reg_map[j] = gen_reg_rtx (GET_MODE (regno_reg_rtx[j]));

      /* If loop starts with a branch to the test, then fix it so that
	 it points to the test of the first unrolled copy of the loop.  */
      if (i == 0 && loop_start != copy_start)
	{
	  insn = PREV_INSN (copy_start);
	  pattern = PATTERN (insn);
	  
	  tem = map->label_map[CODE_LABEL_NUMBER
			       (XEXP (SET_SRC (pattern), 0))];
	  SET_SRC (pattern) = gen_rtx (LABEL_REF, VOIDmode, tem);

	  /* Set the jump label so that it can be used by later loop unrolling
	     passes.  */
	  JUMP_LABEL (insn) = tem;
	  LABEL_NUSES (tem)++;
	}

      copy_loop_body (copy_start, copy_end, map, exit_label,
		      i == unroll_number - 1, unroll_type, start_label,
		      loop_end, insert_before, insert_before);
    }

  /* Before deleting any insns, emit a CODE_LABEL immediately after the last
     insn to be deleted.  This prevents any runaway delete_insn call from
     more insns that it should, as it always stops at a CODE_LABEL.  */

  /* Delete the compare and branch at the end of the loop if completely
     unrolling the loop.  Deleting the backward branch at the end also
     deletes the code label at the start of the loop.  This is done at
     the very end to avoid problems with back_branch_in_range_p.  */

  if (unroll_type == UNROLL_COMPLETELY)
    safety_label = emit_label_after (gen_label_rtx (), last_loop_insn);
  else
    safety_label = emit_label_after (gen_label_rtx (), copy_end);

  /* Delete all of the original loop instructions.  Don't delete the 
     LOOP_BEG note, or the first code label in the loop.  */

  insn = NEXT_INSN (copy_start);
  while (insn != safety_label)
    {
      if (insn != start_label)
	insn = delete_insn (insn);
      else
	insn = NEXT_INSN (insn);
    }

  /* Can now delete the 'safety' label emitted to protect us from runaway
     delete_insn calls.  */
  if (INSN_DELETED_P (safety_label))
    abort ();
  delete_insn (safety_label);

  /* If exit_label exists, emit it after the loop.  Doing the emit here
     forces it to have a higher INSN_UID than any insn in the unrolled loop.
     This is needed so that mostly_true_jump in reorg.c will treat jumps
     to this loop end label correctly, i.e. predict that they are usually
     not taken.  */
  if (exit_label)
    emit_label_after (exit_label, loop_end);
}

/* Return true if the loop can be safely, and profitably, preconditioned
   so that the unrolled copies of the loop body don't need exit tests.

   This only works if final_value, initial_value and increment can be
   determined, and if increment is a constant power of 2.
   If increment is not a power of 2, then the preconditioning modulo
   operation would require a real modulo instead of a boolean AND, and this
   is not considered `profitable'.  */

/* ??? If the loop is known to be executed very many times, or the machine
   has a very cheap divide instruction, then preconditioning is a win even
   when the increment is not a power of 2.  Use RTX_COST to compute
   whether divide is cheap.  */

static int
precondition_loop_p (initial_value, final_value, increment, loop_start,
		     loop_end)
     rtx *initial_value, *final_value, *increment;
     rtx loop_start, loop_end;
{

  if (loop_n_iterations > 0)
    {
      *initial_value = const0_rtx;
      *increment = const1_rtx;
      *final_value = GEN_INT (loop_n_iterations);

      if (loop_dump_stream)
	fprintf (loop_dump_stream,
		 "Preconditioning: Success, number of iterations known, %d.\n",
		 loop_n_iterations);
      return 1;
    }

  if (loop_initial_value == 0)
    {
      if (loop_dump_stream)
	fprintf (loop_dump_stream,
		 "Preconditioning: Could not find initial value.\n");
      return 0;
    }
  else if (loop_increment == 0)
    {
      if (loop_dump_stream)
	fprintf (loop_dump_stream,
		 "Preconditioning: Could not find increment value.\n");
      return 0;
    }
  else if (GET_CODE (loop_increment) != CONST_INT)
    {
      if (loop_dump_stream)
	fprintf (loop_dump_stream,
		 "Preconditioning: Increment not a constant.\n");
      return 0;
    }
  else if ((exact_log2 (INTVAL (loop_increment)) < 0)
	   && (exact_log2 (- INTVAL (loop_increment)) < 0))
    {
      if (loop_dump_stream)
	fprintf (loop_dump_stream,
		 "Preconditioning: Increment not a constant power of 2.\n");
      return 0;
    }

  /* Unsigned_compare and compare_dir can be ignored here, since they do
     not matter for preconditioning.  */

  if (loop_final_value == 0)
    {
      if (loop_dump_stream)
	fprintf (loop_dump_stream,
		 "Preconditioning: EQ comparison loop.\n");
      return 0;
    }

  /* Must ensure that final_value is invariant, so call invariant_p to
     check.  Before doing so, must check regno against max_reg_before_loop
     to make sure that the register is in the range covered by invariant_p.
     If it isn't, then it is most likely a biv/giv which by definition are
     not invariant.  */
  if ((GET_CODE (loop_final_value) == REG
       && REGNO (loop_final_value) >= max_reg_before_loop)
      || (GET_CODE (loop_final_value) == PLUS
	  && REGNO (XEXP (loop_final_value, 0)) >= max_reg_before_loop)
      || ! invariant_p (loop_final_value))
    {
      if (loop_dump_stream)
	fprintf (loop_dump_stream,
		 "Preconditioning: Final value not invariant.\n");
      return 0;
    }

  /* Fail for floating point values, since the caller of this function
     does not have code to deal with them.  */
  if (GET_MODE_CLASS (GET_MODE (loop_final_value)) == MODE_FLOAT
      || GET_MODE_CLASS (GET_MODE (loop_initial_value)) == MODE_FLOAT)
    {
      if (loop_dump_stream)
	fprintf (loop_dump_stream,
		 "Preconditioning: Floating point final or initial value.\n");
      return 0;
    }

  /* Now set initial_value to be the iteration_var, since that may be a
     simpler expression, and is guaranteed to be correct if all of the
     above tests succeed.

     We can not use the initial_value as calculated, because it will be
     one too small for loops of the form "while (i-- > 0)".  We can not
     emit code before the loop_skip_over insns to fix this problem as this
     will then give a number one too large for loops of the form
     "while (--i > 0)".

     Note that all loops that reach here are entered at the top, because
     this function is not called if the loop starts with a jump.  */

  /* Fail if loop_iteration_var is not live before loop_start, since we need
     to test its value in the preconditioning code.  */

  if (uid_luid[REGNO_FIRST_UID (REGNO (loop_iteration_var))]
      > INSN_LUID (loop_start))
    {
      if (loop_dump_stream)
	fprintf (loop_dump_stream,
		 "Preconditioning: Iteration var not live before loop start.\n");
      return 0;
    }

  *initial_value = loop_iteration_var;
  *increment = loop_increment;
  *final_value = loop_final_value;

  /* Success! */
  if (loop_dump_stream)
    fprintf (loop_dump_stream, "Preconditioning: Successful.\n");
  return 1;
}


/* All pseudo-registers must be mapped to themselves.  Two hard registers
   must be mapped, VIRTUAL_STACK_VARS_REGNUM and VIRTUAL_INCOMING_ARGS_
   REGNUM, to avoid function-inlining specific conversions of these
   registers.  All other hard regs can not be mapped because they may be
   used with different
   modes.  */

static void
init_reg_map (map, maxregnum)
     struct inline_remap *map;
     int maxregnum;
{
  int i;

  for (i = maxregnum - 1; i > LAST_VIRTUAL_REGISTER; i--)
    map->reg_map[i] = regno_reg_rtx[i];
  /* Just clear the rest of the entries.  */
  for (i = LAST_VIRTUAL_REGISTER; i >= 0; i--)
    map->reg_map[i] = 0;

  map->reg_map[VIRTUAL_STACK_VARS_REGNUM]
    = regno_reg_rtx[VIRTUAL_STACK_VARS_REGNUM];
  map->reg_map[VIRTUAL_INCOMING_ARGS_REGNUM]
    = regno_reg_rtx[VIRTUAL_INCOMING_ARGS_REGNUM];
}

/* Strength-reduction will often emit code for optimized biv/givs which
   calculates their value in a temporary register, and then copies the result
   to the iv.  This procedure reconstructs the pattern computing the iv;
   verifying that all operands are of the proper form.

   The return value is the amount that the giv is incremented by.  */

static rtx
calculate_giv_inc (pattern, src_insn, regno)
     rtx pattern, src_insn;
     int regno;
{
  rtx increment;
  rtx increment_total = 0;
  int tries = 0;

 retry:
  /* Verify that we have an increment insn here.  First check for a plus
     as the set source.  */
  if (GET_CODE (SET_SRC (pattern)) != PLUS)
    {
      /* SR sometimes computes the new giv value in a temp, then copies it
	 to the new_reg.  */
      src_insn = PREV_INSN (src_insn);
      pattern = PATTERN (src_insn);
      if (GET_CODE (SET_SRC (pattern)) != PLUS)
	abort ();
		  
      /* The last insn emitted is not needed, so delete it to avoid confusing
	 the second cse pass.  This insn sets the giv unnecessarily.  */
      delete_insn (get_last_insn ());
    }

  /* Verify that we have a constant as the second operand of the plus.  */
  increment = XEXP (SET_SRC (pattern), 1);
  if (GET_CODE (increment) != CONST_INT)
    {
      /* SR sometimes puts the constant in a register, especially if it is
	 too big to be an add immed operand.  */
      src_insn = PREV_INSN (src_insn);
      increment = SET_SRC (PATTERN (src_insn));

      /* SR may have used LO_SUM to compute the constant if it is too large
	 for a load immed operand.  In this case, the constant is in operand
	 one of the LO_SUM rtx.  */
      if (GET_CODE (increment) == LO_SUM)
	increment = XEXP (increment, 1);
      else if (GET_CODE (increment) == IOR
	       || GET_CODE (increment) == ASHIFT
	       || GET_CODE (increment) == PLUS)
	{
	  /* The rs6000 port loads some constants with IOR.
	     The alpha port loads some constants with ASHIFT and PLUS.  */
	  rtx second_part = XEXP (increment, 1);
	  enum rtx_code code = GET_CODE (increment);

	  src_insn = PREV_INSN (src_insn);
	  increment = SET_SRC (PATTERN (src_insn));
	  /* Don't need the last insn anymore.  */
	  delete_insn (get_last_insn ());

	  if (GET_CODE (second_part) != CONST_INT
	      || GET_CODE (increment) != CONST_INT)
	    abort ();