expmed.c

gcc库的原代码,对编程有很大帮助.

	 crosses a word boundary.  Thus, for a SUBREG, we must find
	 the current word starting from the base register.  */
      if (GET_CODE (op0) == SUBREG)
	{
	  word = operand_subword_force (SUBREG_REG (op0),
					SUBREG_WORD (op0) + offset,
					GET_MODE (SUBREG_REG (op0)));
	  offset = 0;
	}
      else if (GET_CODE (op0) == REG)
	{
	  word = operand_subword_force (op0, offset, GET_MODE (op0));
	  offset = 0;
	}
      else
	word = op0;

      /* Extract the parts in bit-counting order,
	 whose meaning is determined by BYTES_PER_UNIT.
	 OFFSET is in UNITs, and UNIT is in bits.
	 extract_fixed_bit_field wants offset in bytes.  */
      part = extract_fixed_bit_field (word_mode, word,
				      offset * unit / BITS_PER_UNIT,
				      thissize, thispos, 0, 1, align);
      bitsdone += thissize;

      /* Shift this part into place for the result.  */
      if (BYTES_BIG_ENDIAN)
	{
	  if (bitsize != bitsdone)
	    part = expand_shift (LSHIFT_EXPR, word_mode, part,
				 build_int_2 (bitsize - bitsdone, 0), 0, 1);
	}
      else
	{
	  if (bitsdone != thissize)
	    part = expand_shift (LSHIFT_EXPR, word_mode, part,
				 build_int_2 (bitsdone - thissize, 0), 0, 1);
	}

      if (first)
	result = part;
      else
	/* Combine the parts with bitwise or.  This works
	   because we extracted each part as an unsigned bit field.  */
	result = expand_binop (word_mode, ior_optab, part, result, NULL_RTX, 1,
			       OPTAB_LIB_WIDEN);

      first = 0;
    }

  /* Unsigned bit field: we are done.  */
  if (unsignedp)
    return result;
  /* Signed bit field: sign-extend with two arithmetic shifts.  */
  result = expand_shift (LSHIFT_EXPR, word_mode, result,
			 build_int_2 (BITS_PER_WORD - bitsize, 0),
			 NULL_RTX, 0);
  return expand_shift (RSHIFT_EXPR, word_mode, result,
		       build_int_2 (BITS_PER_WORD - bitsize, 0), NULL_RTX, 0);
}

/* Add INC into TARGET.  */

void
expand_inc (target, inc)
     rtx target, inc;
{
  rtx value = expand_binop (GET_MODE (target), add_optab,
			    target, inc,
			    target, 0, OPTAB_LIB_WIDEN);
  if (value != target)
    emit_move_insn (target, value);
}

/* Subtract DEC from TARGET.  */

void
expand_dec (target, dec)
     rtx target, dec;
{
  rtx value = expand_binop (GET_MODE (target), sub_optab,
			    target, dec,
			    target, 0, OPTAB_LIB_WIDEN);
  if (value != target)
    emit_move_insn (target, value);
}

/* Output a shift instruction for expression code CODE,
   with SHIFTED being the rtx for the value to shift,
   and AMOUNT the tree for the amount to shift by.
   Store the result in the rtx TARGET, if that is convenient.
   If UNSIGNEDP is nonzero, do a logical shift; otherwise, arithmetic.
   Return the rtx for where the value is.  */

rtx
expand_shift (code, mode, shifted, amount, target, unsignedp)
     enum tree_code code;
     register enum machine_mode mode;
     rtx shifted;
     tree amount;
     register rtx target;
     int unsignedp;
{
  register rtx op1, temp = 0;
  register int left = (code == LSHIFT_EXPR || code == LROTATE_EXPR);
  register int rotate = (code == LROTATE_EXPR || code == RROTATE_EXPR);
  int try;

  /* Previously detected shift-counts computed by NEGATE_EXPR
     and shifted in the other direction; but that does not work
     on all machines.  */

  op1 = expand_expr (amount, NULL_RTX, VOIDmode, 0);

#ifdef SHIFT_COUNT_TRUNCATED
  if (SHIFT_COUNT_TRUNCATED
      && GET_CODE (op1) == CONST_INT
      && (unsigned HOST_WIDE_INT) INTVAL (op1) >= GET_MODE_BITSIZE (mode))
    op1 = GEN_INT ((unsigned HOST_WIDE_INT) INTVAL (op1)
		   % GET_MODE_BITSIZE (mode));
#endif

  if (op1 == const0_rtx)
    return shifted;

  for (try = 0; temp == 0 && try < 3; try++)
    {
      enum optab_methods methods;

      if (try == 0)
	methods = OPTAB_DIRECT;
      else if (try == 1)
	methods = OPTAB_WIDEN;
      else
	methods = OPTAB_LIB_WIDEN;

      if (rotate)
	{
	  /* Widening does not work for rotation.  */
	  if (methods == OPTAB_WIDEN)
	    continue;
	  else if (methods == OPTAB_LIB_WIDEN)
	    {
	      /* If we have been unable to open-code this by a rotation,
		 do it as the IOR of two shifts.  I.e., to rotate A
		 by N bits, compute (A << N) | ((unsigned) A >> (C - N))
		 where C is the bitsize of A.

		 It is theoretically possible that the target machine might
		 not be able to perform either shift and hence we would
		 be making two libcalls rather than just the one for the
		 shift (similarly if IOR could not be done).  We will allow
		 this extremely unlikely lossage to avoid complicating the
		 code below.  */

	      rtx subtarget = target == shifted ? 0 : target;
	      rtx temp1;
	      tree type = TREE_TYPE (amount);
	      tree new_amount = make_tree (type, op1);
	      tree other_amount
		= fold (build (MINUS_EXPR, type,
			       convert (type,
					build_int_2 (GET_MODE_BITSIZE (mode),
						     0)),
			       amount));

	      shifted = force_reg (mode, shifted);

	      temp = expand_shift (left ? LSHIFT_EXPR : RSHIFT_EXPR,
				   mode, shifted, new_amount, subtarget, 1);
	      temp1 = expand_shift (left ? RSHIFT_EXPR : LSHIFT_EXPR,
				    mode, shifted, other_amount, 0, 1);
	      return expand_binop (mode, ior_optab, temp, temp1, target,
				   unsignedp, methods);
	    }

	  temp = expand_binop (mode,
			       left ? rotl_optab : rotr_optab,
			       shifted, op1, target, unsignedp, methods);

	  /* If we don't have the rotate, but we are rotating by a constant
	     that is in range, try a rotate in the opposite direction.  */

	  if (temp == 0 && GET_CODE (op1) == CONST_INT
	      && INTVAL (op1) > 0 && INTVAL (op1) < GET_MODE_BITSIZE (mode))
	    temp = expand_binop (mode,
				 left ? rotr_optab : rotl_optab,
				 shifted, 
				 GEN_INT (GET_MODE_BITSIZE (mode)
					  - INTVAL (op1)),
				 target, unsignedp, methods);
	}
      else if (unsignedp)
	temp = expand_binop (mode,
			     left ? ashl_optab : lshr_optab,
			     shifted, op1, target, unsignedp, methods);

      /* Do arithmetic shifts.
	 Also, if we are going to widen the operand, we can just as well
	 use an arithmetic right-shift instead of a logical one.  */
      if (temp == 0 && ! rotate
	  && (! unsignedp || (! left && methods == OPTAB_WIDEN)))
	{
	  enum optab_methods methods1 = methods;

	  /* If trying to widen a log shift to an arithmetic shift,
	     don't accept an arithmetic shift of the same size.  */
	  if (unsignedp)
	    methods1 = OPTAB_MUST_WIDEN;

	  /* Arithmetic shift */

	  temp = expand_binop (mode,
			       left ? ashl_optab : ashr_optab,
			       shifted, op1, target, unsignedp, methods1);
	}

      /* We used to try extzv here for logical right shifts, but that was
	 only useful for one machine, the VAX, and caused poor code 
	 generation there for lshrdi3, so the code was deleted and a
	 define_expand for lshrsi3 was added to vax.md.  */
    }

  if (temp == 0)
    abort ();
  return temp;
}

enum alg_code { alg_zero, alg_m, alg_shift,
		  alg_add_t_m2, alg_sub_t_m2,
		  alg_add_factor, alg_sub_factor,
		  alg_add_t2_m, alg_sub_t2_m,
		  alg_add, alg_subtract, alg_factor, alg_shiftop };

/* This structure records a sequence of operations.
   `ops' is the number of operations recorded.
   `cost' is their total cost.
   The operations are stored in `op' and the corresponding
   logarithms of the integer coefficients in `log'.

   These are the operations:
   alg_zero		total := 0;
   alg_m		total := multiplicand;
   alg_shift		total := total * coeff
   alg_add_t_m2		total := total + multiplicand * coeff;
   alg_sub_t_m2		total := total - multiplicand * coeff;
   alg_add_factor	total := total * coeff + total;
   alg_sub_factor	total := total * coeff - total;
   alg_add_t2_m		total := total * coeff + multiplicand;
   alg_sub_t2_m		total := total * coeff - multiplicand;

   The first operand must be either alg_zero or alg_m.  */

struct algorithm
{
  short cost;
  short ops;
  /* The size of the OP and LOG fields are not directly related to the
     word size, but the worst-case algorithms will be if we have few
     consecutive ones or zeros, i.e., a multiplicand like 10101010101...
     In that case we will generate shift-by-2, add, shift-by-2, add,...,
     in total wordsize operations.  */
  enum alg_code op[MAX_BITS_PER_WORD];
  char log[MAX_BITS_PER_WORD];
};

/* Compute and return the best algorithm for multiplying by T.
   The algorithm must cost less than cost_limit
   If retval.cost >= COST_LIMIT, no algorithm was found and all
   other field of the returned struct are undefined.  */

static void
synth_mult (alg_out, t, cost_limit)
     struct algorithm *alg_out;
     unsigned HOST_WIDE_INT t;
     int cost_limit;
{
  int m;
  struct algorithm *alg_in, *best_alg;
  unsigned int cost;
  unsigned HOST_WIDE_INT q;

  /* Indicate that no algorithm is yet found.  If no algorithm
     is found, this value will be returned and indicate failure.  */
  alg_out->cost = cost_limit;

  if (cost_limit <= 0)
    return;

  /* t == 1 can be done in zero cost.  */
  if (t == 1)
    {
      alg_out->ops = 1;
      alg_out->cost = 0;
      alg_out->op[0] = alg_m;
      return;
    }

  /* t == 0 sometimes has a cost.  If it does and it exceeds our limit,
     fail now.  */
  if (t == 0)
    {
      if (zero_cost >= cost_limit)
	return;
      else
	{
	  alg_out->ops = 1;
	  alg_out->cost = zero_cost;
	  alg_out->op[0] = alg_zero;
	  return;
	}
    }

  /* We'll be needing a couple extra algorithm structures now.  */

  alg_in = (struct algorithm *)alloca (sizeof (struct algorithm));
  best_alg = (struct algorithm *)alloca (sizeof (struct algorithm));

  /* If we have a group of zero bits at the low-order part of T, try
     multiplying by the remaining bits and then doing a shift.  */

  if ((t & 1) == 0)
    {
      m = floor_log2 (t & -t);	/* m = number of low zero bits */
      q = t >> m;
      cost = shift_cost[m];
      synth_mult (alg_in, q, cost_limit - cost);

      cost += alg_in->cost;
      if (cost < cost_limit)
	{
	  struct algorithm *x;
	  x = alg_in, alg_in = best_alg, best_alg = x;
	  best_alg->log[best_alg->ops] = m;
	  best_alg->op[best_alg->ops] = alg_shift;
	  cost_limit = cost;
	}
    }

  /* If we have an odd number, add or subtract one.  */
  if ((t & 1) != 0)
    {
      unsigned HOST_WIDE_INT w;

      for (w = 1; (w & t) != 0; w <<= 1)
	;
      if (w > 2
	  /* Reject the case where t is 3.
	     Thus we prefer addition in that case.  */
	  && t != 3)
	{
	  /* T ends with ...111.  Multiply by (T + 1) and subtract 1.  */

	  cost = add_cost;
	  synth_mult (alg_in, t + 1, cost_limit - cost);

	  cost += alg_in->cost;
	  if (cost < cost_limit)
	    {
	      struct algorithm *x;
	      x = alg_in, alg_in = best_alg, best_alg = x;
	      best_alg->log[best_alg->ops] = 0;
	      best_alg->op[best_alg->ops] = alg_sub_t_m2;
	      cost_limit = cost;
	    }
	}
      else
	{
	  /* T ends with ...01 or ...011.  Multiply by (T - 1) and add 1.  */

	  cost = add_cost;
	  synth_mult (alg_in, t - 1, cost_limit - cost);

	  cost += alg_in->cost;
	  if (cost < cost_limit)
	    {
	      struct algorithm *x;
	      x = alg_in, alg_in = best_alg, best_alg = x;
	      best_alg->log[best_alg->ops] = 0;
	      best_alg->op[best_alg->ops] = alg_add_t_m2;
	      cost_limit = cost;
	    }
	}
    }

  /* Look for factors of t of the form
     t = q(2**m +- 1), 2 <= m <= floor(log2(t - 1)).
     If we find such a factor, we can multiply by t using an algorithm that
     multiplies by q, shift the result by m and add/subtract it to itself.

     We search for large factors first and loop down, even if large factors
     are less probable than small; if we find a large factor we will find a
     good sequence quickly, and therefore be able to prune (by decreasing
     COST_LIMIT) the search.  */

  for (m = floor_log2 (t - 1); m >= 2; m--)
    {
      unsigned HOST_WIDE_INT d;

      d = ((unsigned HOST_WIDE_INT) 1 << m) + 1;
      if (t % d == 0 && t