+
+ case SIGN_EXTRACT:
+ if (GET_CODE (XEXP (x, 1)) == CONST_INT)
+ return MAX (1, (int) bitwidth - INTVAL (XEXP (x, 1)));
+ break;
+
+ case SIGN_EXTEND:
+ return (bitwidth - GET_MODE_BITSIZE (GET_MODE (XEXP (x, 0)))
+ + cached_num_sign_bit_copies (XEXP (x, 0), VOIDmode,
+ known_x, known_mode, known_ret));
+
+ case TRUNCATE:
+ /* For a smaller object, just ignore the high bits. */
+ num0 = cached_num_sign_bit_copies (XEXP (x, 0), VOIDmode,
+ known_x, known_mode, known_ret);
+ return MAX (1, (num0 - (int) (GET_MODE_BITSIZE (GET_MODE (XEXP (x, 0)))
+ - bitwidth)));
+
+ case NOT:
+ return cached_num_sign_bit_copies (XEXP (x, 0), mode,
+ known_x, known_mode, known_ret);
+
+ case ROTATE: case ROTATERT:
+ /* If we are rotating left by a number of bits less than the number
+ of sign bit copies, we can just subtract that amount from the
+ number. */
+ if (GET_CODE (XEXP (x, 1)) == CONST_INT
+ && INTVAL (XEXP (x, 1)) >= 0
+ && INTVAL (XEXP (x, 1)) < (int) bitwidth)
+ {
+ num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
+ known_x, known_mode, known_ret);
+ return MAX (1, num0 - (code == ROTATE ? INTVAL (XEXP (x, 1))
+ : (int) bitwidth - INTVAL (XEXP (x, 1))));
+ }
+ break;
+
+ case NEG:
+ /* In general, this subtracts one sign bit copy. But if the value
+ is known to be positive, the number of sign bit copies is the
+ same as that of the input. Finally, if the input has just one bit
+ that might be nonzero, all the bits are copies of the sign bit. */
+ num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
+ known_x, known_mode, known_ret);
+ if (bitwidth > HOST_BITS_PER_WIDE_INT)
+ return num0 > 1 ? num0 - 1 : 1;
+
+ nonzero = nonzero_bits (XEXP (x, 0), mode);
+ if (nonzero == 1)
+ return bitwidth;
+
+ if (num0 > 1
+ && (((HOST_WIDE_INT) 1 << (bitwidth - 1)) & nonzero))
+ num0--;
+
+ return num0;
+
+ case IOR: case AND: case XOR:
+ case SMIN: case SMAX: case UMIN: case UMAX:
+ /* Logical operations will preserve the number of sign-bit copies.
+ MIN and MAX operations always return one of the operands. */
+ num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
+ known_x, known_mode, known_ret);
+ num1 = cached_num_sign_bit_copies (XEXP (x, 1), mode,
+ known_x, known_mode, known_ret);
+ return MIN (num0, num1);
+
+ case PLUS: case MINUS:
+ /* For addition and subtraction, we can have a 1-bit carry. However,
+ if we are subtracting 1 from a positive number, there will not
+ be such a carry. Furthermore, if the positive number is known to
+ be 0 or 1, we know the result is either -1 or 0. */
+
+ if (code == PLUS && XEXP (x, 1) == constm1_rtx
+ && bitwidth <= HOST_BITS_PER_WIDE_INT)
+ {
+ nonzero = nonzero_bits (XEXP (x, 0), mode);
+ if ((((HOST_WIDE_INT) 1 << (bitwidth - 1)) & nonzero) == 0)
+ return (nonzero == 1 || nonzero == 0 ? bitwidth
+ : bitwidth - floor_log2 (nonzero) - 1);
+ }
+
+ num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
+ known_x, known_mode, known_ret);
+ num1 = cached_num_sign_bit_copies (XEXP (x, 1), mode,
+ known_x, known_mode, known_ret);
+ result = MAX (1, MIN (num0, num1) - 1);
+
+#ifdef POINTERS_EXTEND_UNSIGNED
+ /* If pointers extend signed and this is an addition or subtraction
+ to a pointer in Pmode, all the bits above ptr_mode are known to be
+ sign bit copies. */
+ if (! POINTERS_EXTEND_UNSIGNED && GET_MODE (x) == Pmode
+ && (code == PLUS || code == MINUS)
+ && REG_P (XEXP (x, 0)) && REG_POINTER (XEXP (x, 0)))
+ result = MAX ((int) (GET_MODE_BITSIZE (Pmode)
+ - GET_MODE_BITSIZE (ptr_mode) + 1),
+ result);
+#endif
+ return result;
+
+ case MULT:
+ /* The number of bits of the product is the sum of the number of
+ bits of both terms. However, unless one of the terms if known
+ to be positive, we must allow for an additional bit since negating
+ a negative number can remove one sign bit copy. */
+
+ num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
+ known_x, known_mode, known_ret);
+ num1 = cached_num_sign_bit_copies (XEXP (x, 1), mode,
+ known_x, known_mode, known_ret);
+
+ result = bitwidth - (bitwidth - num0) - (bitwidth - num1);
+ if (result > 0
+ && (bitwidth > HOST_BITS_PER_WIDE_INT
+ || (((nonzero_bits (XEXP (x, 0), mode)
+ & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0)
+ && ((nonzero_bits (XEXP (x, 1), mode)
+ & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0))))
+ result--;
+
+ return MAX (1, result);
+
+ case UDIV:
+ /* The result must be <= the first operand. If the first operand
+ has the high bit set, we know nothing about the number of sign
+ bit copies. */
+ if (bitwidth > HOST_BITS_PER_WIDE_INT)
+ return 1;
+ else if ((nonzero_bits (XEXP (x, 0), mode)
+ & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0)
+ return 1;
+ else
+ return cached_num_sign_bit_copies (XEXP (x, 0), mode,
+ known_x, known_mode, known_ret);
+
+ case UMOD:
+ /* The result must be <= the second operand. */
+ return cached_num_sign_bit_copies (XEXP (x, 1), mode,
+ known_x, known_mode, known_ret);
+
+ case DIV:
+ /* Similar to unsigned division, except that we have to worry about
+ the case where the divisor is negative, in which case we have
+ to add 1. */
+ result = cached_num_sign_bit_copies (XEXP (x, 0), mode,
+ known_x, known_mode, known_ret);
+ if (result > 1
+ && (bitwidth > HOST_BITS_PER_WIDE_INT
+ || (nonzero_bits (XEXP (x, 1), mode)
+ & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0))
+ result--;
+
+ return result;
+
+ case MOD:
+ result = cached_num_sign_bit_copies (XEXP (x, 1), mode,
+ known_x, known_mode, known_ret);
+ if (result > 1
+ && (bitwidth > HOST_BITS_PER_WIDE_INT
+ || (nonzero_bits (XEXP (x, 1), mode)
+ & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0))
+ result--;
+
+ return result;
+
+ case ASHIFTRT:
+ /* Shifts by a constant add to the number of bits equal to the
+ sign bit. */
+ num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
+ known_x, known_mode, known_ret);
+ if (GET_CODE (XEXP (x, 1)) == CONST_INT
+ && INTVAL (XEXP (x, 1)) > 0)
+ num0 = MIN ((int) bitwidth, num0 + INTVAL (XEXP (x, 1)));
+
+ return num0;
+
+ case ASHIFT:
+ /* Left shifts destroy copies. */
+ if (GET_CODE (XEXP (x, 1)) != CONST_INT
+ || INTVAL (XEXP (x, 1)) < 0
+ || INTVAL (XEXP (x, 1)) >= (int) bitwidth)
+ return 1;
+
+ num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
+ known_x, known_mode, known_ret);
+ return MAX (1, num0 - INTVAL (XEXP (x, 1)));
+
+ case IF_THEN_ELSE:
+ num0 = cached_num_sign_bit_copies (XEXP (x, 1), mode,
+ known_x, known_mode, known_ret);
+ num1 = cached_num_sign_bit_copies (XEXP (x, 2), mode,
+ known_x, known_mode, known_ret);
+ return MIN (num0, num1);
+
+ case EQ: case NE: case GE: case GT: case LE: case LT:
+ case UNEQ: case LTGT: case UNGE: case UNGT: case UNLE: case UNLT:
+ case GEU: case GTU: case LEU: case LTU:
+ case UNORDERED: case ORDERED:
+ /* If the constant is negative, take its 1's complement and remask.
+ Then see how many zero bits we have. */
+ nonzero = STORE_FLAG_VALUE;
+ if (bitwidth <= HOST_BITS_PER_WIDE_INT
+ && (nonzero & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0)
+ nonzero = (~nonzero) & GET_MODE_MASK (mode);
+
+ return (nonzero == 0 ? bitwidth : bitwidth - floor_log2 (nonzero) - 1);
+
+ default:
+ break;
+ }
+
+ /* If we haven't been able to figure it out by one of the above rules,
+ see if some of the high-order bits are known to be zero. If so,
+ count those bits and return one less than that amount. If we can't
+ safely compute the mask for this mode, always return BITWIDTH. */
+
+ bitwidth = GET_MODE_BITSIZE (mode);
+ if (bitwidth > HOST_BITS_PER_WIDE_INT)
+ return 1;
+
+ nonzero = nonzero_bits (x, mode);
+ return nonzero & ((HOST_WIDE_INT) 1 << (bitwidth - 1))
+ ? 1 : bitwidth - floor_log2 (nonzero) - 1;
+}
+
+/* Calculate the rtx_cost of a single instruction. A return value of
+ zero indicates an instruction pattern without a known cost. */
+
+int
+insn_rtx_cost (rtx pat)
+{
+ int i, cost;
+ rtx set;
+
+ /* Extract the single set rtx from the instruction pattern.
+ We can't use single_set since we only have the pattern. */
+ if (GET_CODE (pat) == SET)
+ set = pat;
+ else if (GET_CODE (pat) == PARALLEL)
+ {
+ set = NULL_RTX;