unroll.c

早期freebsd实现

   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;
{
  int unsigned_compare, compare_dir;

  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;

  /* 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.  */
      increment = SET_SRC (PATTERN (PREV_INSN (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);

      if (GET_CODE (increment) != CONST_INT)
	abort ();
		  
      /* The insn loading the constant into a register is not longer needed,
	 so delete it.  */
      delete_insn (get_last_insn ());
    }

  /* Check that the source register is the same as the dest register.  */
  if (GET_CODE (XEXP (SET_SRC (pattern), 0)) != REG
      || REGNO (XEXP (SET_SRC (pattern), 0)) != regno)
    abort ();

  return increment;
}


/* Copy each instruction in the loop, substituting from map as appropriate.
   This is very similar to a loop in expand_inline_function.  */
  
static void
copy_loop_body (copy_start, copy_end, map, exit_label, last_iteration,
		unroll_type, start_label, loop_end, insert_before,
		copy_notes_from)
     rtx copy_start, copy_end;
     struct inline_remap *map;
     rtx exit_label;
     int last_iteration;
     enum unroll_types unroll_type;
     rtx start_label, loop_end, insert_before, copy_notes_from;
{
  rtx insn, pattern;
  rtx tem, copy;
  int dest_reg_was_split, i;
  rtx cc0_insn = 0;
  rtx final_label = 0;
  rtx giv_inc, giv_dest_reg, giv_src_reg;

  /* If this isn't the last iteration, then map any references to the
     start_label to final_label.  Final label will then be emitted immediately
     after the end of this loop body if it was ever used.

     If this is the last iteration, then map references to the start_label
     to itself.  */
  if (! last_iteration)
    {
      final_label = gen_label_rtx ();
      map->label_map[CODE_LABEL_NUMBER (start_label)] = final_label;
    }
  else
    map->label_map[CODE_LABEL_NUMBER (start_label)] = start_label;

  start_sequence ();
  
  insn = copy_start;
  do
    {
      insn = NEXT_INSN (insn);
      
      map->orig_asm_operands_vector = 0;
      
      switch (GET_CODE (insn))
	{
	case INSN:
	  pattern = PATTERN (insn);
	  copy = 0;
	  giv_inc = 0;
	  
	  /* Check to see if this is a giv that has been combined with
	     some split address givs.  (Combined in the sense that 
	     `combine_givs' in loop.c has put two givs in the same register.)
	     In this case, we must search all givs based on the same biv to
	     find the address givs.  Then split the address givs.
	     Do this before splitting the giv, since that may map the
	     SET_DEST to a new register.  */
	  
	  if (GET_CODE (pattern) == SET
	      && GET_CODE (SET_DEST (pattern)) == REG
	      && addr_combined_regs[REGNO (SET_DEST (pattern))])
	    {
	      struct iv_class *bl;
	      struct induction *v, *tv;
	      int regno = REGNO (SET_DEST (pattern));
	      
	      v = addr_combined_regs[REGNO (SET_DEST (pattern))];
	      bl = reg_biv_class[REGNO (v->src_reg)];
	      
	      /* Although the giv_inc amount is not needed here, we must call
		 calculate_giv_inc here since it might try to delete the
		 last insn emitted.  If we wait until later to call it,
		 we might accidentally delete insns generated immediately
		 below by emit_unrolled_add.  */

	      giv_inc = calculate_giv_inc (pattern, insn, regno);

	      /* Now find all address giv's that were combined with this
		 giv 'v'.  */
	      for (tv = bl->giv; tv; tv = tv->next_iv)
		if (tv->giv_type == DEST_ADDR && tv->same == v)
		  {
		    int this_giv_inc = INTVAL (giv_inc);

		    /* Scale this_giv_inc if the multiplicative factors of
		       the two givs are different.  */
		    if (tv->mult_val != v->mult_val)
		      this_giv_inc = (this_giv_inc / INTVAL (v->mult_val)
				      * INTVAL (tv->mult_val));
		       
		    tv->dest_reg = plus_constant (tv->dest_reg, this_giv_inc);
		    *tv->location = tv->dest_reg;
		    
		    if (last_iteration && unroll_type != UNROLL_COMPLETELY)
		      {
			/* Must emit an insn to increment the split address
			   giv.  Add in the const_adjust field in case there
			   was a constant eliminated from the address.  */
			rtx value, dest_reg;
			
			/* tv->dest_reg will be either a bare register,
			   or else a register plus a constant.  */
			if (GET_CODE (tv->dest_reg) == REG)
			  dest_reg = tv->dest_reg;
			else
			  dest_reg = XEXP (tv->dest_reg, 0);
			
			/* tv->dest_reg may actually be a (PLUS (REG) (CONST))
			   here, so we must call plus_constant to add
			   the const_adjust amount before calling
			   emit_unrolled_add below.  */
			value = plus_constant (tv->dest_reg, tv->const_adjust);

			/* The constant could be too large for an add
			   immediate, so can't directly emit an insn here.  */
			emit_unrolled_add (dest_reg, XEXP (value, 0),
					   XEXP (value, 1));
			
			/* Reset the giv to be just the register again, in case
			   it is used after the set we have just emitted.
			   We must subtract the const_adjust factor added in
			   above.  */
			tv->dest_reg = plus_constant (dest_reg,
						      - tv->const_adjust);
			*tv->location = tv->dest_reg;
		      }
		  }
	    }
	  
	  /* If this is a setting of a splittable variable, then determine
	     how to split the variable, create a new set based on this split,
	     and set up the reg_map so that later uses of the variable will
	     use the new split variable.  */
	  
	  dest_reg_was_split = 0;
	  
	  if (GET_CODE (pattern) == SET
	      && GET_CODE (SET_DEST (pattern)) == REG
	      && splittable_regs[REGNO (SET_DEST (pattern))])
	    {
	      int regno = REGNO (SET_DEST (pattern));
	      
	      dest_reg_was_split = 1;
	      
	      /* Compute the increment value for the giv, if it wasn't
		 already computed above.  */

	      if (giv_inc == 0)
		giv_inc = calculate_giv_inc (pattern, insn, regno);
	      giv_dest_reg = SET_DEST (pattern);
	      giv_src_reg = SET_DEST (pattern);

	      if (unroll_type == UNROLL_COMPLETELY)
		{
		  /* Completely unrolling the loop.  Set the induction
		     variable to a known constant value.  */