-//===-- llvm/Support/APInt.h - For Arbitrary Precision Integer -*- C++ -*--===//
+//===-- llvm/ADT/APInt.h - For Arbitrary Precision Integer -----*- C++ -*--===//
//
// The LLVM Compiler Infrastructure
//
#define LLVM_APINT_H
#include "llvm/Support/DataTypes.h"
+#include "llvm/Bitcode/SerializationFwd.h"
#include <cassert>
#include <string>
+#define COMPILE_TIME_ASSERT(cond) extern int CTAssert[(cond) ? 1 : -1]
+
namespace llvm {
+ /* An unsigned host type used as a single part of a multi-part
+ bignum. */
+ typedef uint64_t integerPart;
+
+ const unsigned int host_char_bit = 8;
+ const unsigned int integerPartWidth = host_char_bit * sizeof(integerPart);
+
//===----------------------------------------------------------------------===//
// APInt Class
//===----------------------------------------------------------------------===//
const APInt &RHS, uint32_t rhsWords,
APInt *Quotient, APInt *Remainder);
-#ifndef NDEBUG
- /// @brief debug method
- void dump() const;
-#endif
-
public:
/// @name Constructors
/// @{
/// @param numWords the number of words in bigVal
/// @param bigVal a sequence of words to form the initial value of the APInt
/// @brief Construct an APInt of numBits width, initialized as bigVal[].
- APInt(uint32_t numBits, uint32_t numWords, uint64_t bigVal[]);
+ APInt(uint32_t numBits, uint32_t numWords, const uint64_t bigVal[]);
/// This constructor interprets Val as a string in the given radix. The
/// interpretation stops when the first charater that is not suitable for the
/// @param numBits the bit width of the constructed APInt
/// @param strStart the start of the string to be interpreted
/// @param slen the maximum number of characters to interpret
+ /// @param radix the radix to use for the conversion
/// @brief Construct an APInt from a string representation.
APInt(uint32_t numBits, const char strStart[], uint32_t slen, uint8_t radix);
/// @brief Destructor.
~APInt();
+
+ /// Default constructor that creates an uninitialized APInt. This is useful
+ /// for object deserialization (pair this with the static method Read).
+ explicit APInt() : BitWidth(1) {}
+
+ /// @brief Used by the Bitcode serializer to emit APInts to Bitcode.
+ void Emit(Serializer& S) const;
+
+ /// @brief Used by the Bitcode deserializer to deserialize APInts.
+ void Read(Deserializer& D);
/// @}
/// @name Value Tests
/// @returns true if the argument APInt value is a power of two > 0.
bool isPowerOf2() const;
- /// This converts the APInt to a boolean valy as a test against zero.
+ /// isSignBit - Return true if this is the value returned by getSignBit.
+ bool isSignBit() const { return isMinSignedValue(); }
+
+ /// This converts the APInt to a boolean value as a test against zero.
/// @brief Boolean conversion function.
inline bool getBoolValue() const {
- return countLeadingZeros() != BitWidth;
+ return *this != 0;
+ }
+
+ /// getLimitedValue - If this value is smaller than the specified limit,
+ /// return it, otherwise return the limit value. This causes the value
+ /// to saturate to the limit.
+ uint64_t getLimitedValue(uint64_t Limit = ~0ULL) const {
+ return (getActiveBits() > 64 || getZExtValue() > Limit) ?
+ Limit : getZExtValue();
}
/// @}
/// less than loBit then the set bits "wrap". For example, with
/// parameters (32, 3, 28), you would get 0xF000000F.
/// @param numBits the intended bit width of the result
- /// @param hiBit the index of the highest bit set.
/// @param loBit the index of the lowest bit set.
+ /// @param hiBit the index of the highest bit set.
/// @returns An APInt value with the requested bits set.
/// @brief Get a value with a block of bits set.
- static APInt getBitsSet(uint32_t numBits, uint32_t hiBit, uint32_t loBit = 0);
+ static APInt getBitsSet(uint32_t numBits, uint32_t loBit, uint32_t hiBit) {
+ assert(hiBit < numBits && "hiBit out of range");
+ assert(loBit < numBits && "loBit out of range");
+ if (hiBit < loBit)
+ return getLowBitsSet(numBits, hiBit+1) |
+ getHighBitsSet(numBits, numBits-loBit+1);
+ return getLowBitsSet(numBits, hiBit-loBit+1).shl(loBit);
+ }
/// Constructs an APInt value that has the top hiBitsSet bits set.
/// @param numBits the bitwidth of the result
/// @param hiBitsSet the number of high-order bits set in the result.
/// @brief Get a value with high bits set
- static APInt getHighBitsSet(uint32_t numBits, uint32_t hiBitsSet);
+ static APInt getHighBitsSet(uint32_t numBits, uint32_t hiBitsSet) {
+ assert(hiBitsSet <= numBits && "Too many bits to set!");
+ // Handle a degenerate case, to avoid shifting by word size
+ if (hiBitsSet == 0)
+ return APInt(numBits, 0);
+ uint32_t shiftAmt = numBits - hiBitsSet;
+ // For small values, return quickly
+ if (numBits <= APINT_BITS_PER_WORD)
+ return APInt(numBits, ~0ULL << shiftAmt);
+ return (~APInt(numBits, 0)).shl(shiftAmt);
+ }
/// Constructs an APInt value that has the bottom loBitsSet bits set.
/// @param numBits the bitwidth of the result
/// @param loBitsSet the number of low-order bits set in the result.
/// @brief Get a value with low bits set
- static APInt getLowBitsSet(uint32_t numBits, uint32_t loBitsSet);
+ static APInt getLowBitsSet(uint32_t numBits, uint32_t loBitsSet) {
+ assert(loBitsSet <= numBits && "Too many bits to set!");
+ // Handle a degenerate case, to avoid shifting by word size
+ if (loBitsSet == 0)
+ return APInt(numBits, 0);
+ if (loBitsSet == APINT_BITS_PER_WORD)
+ return APInt(numBits, -1ULL);
+ // For small values, return quickly
+ if (numBits < APINT_BITS_PER_WORD)
+ return APInt(numBits, (1ULL << loBitsSet) - 1);
+ return (~APInt(numBits, 0)).lshr(numBits - loBitsSet);
+ }
/// The hash value is computed as the sum of the words and the bit width.
/// @returns A hash value computed from the sum of the APInt words.
return &pVal[0];
}
- /// @brief Set a sepcific word in the value to a new value.
- inline void setWordToValue(uint32_t idx, uint64_t Val) {
- assert(idx < getNumWords() && "Invalid word array index");
- if (isSingleWord())
- VAL = Val;
- else
- pVal[idx] = Val;
- }
-
/// @}
/// @name Unary Operators
/// @{
APInt operator-(uint64_t RHS) const {
return (*this) - APInt(BitWidth, RHS);
}
+
+ APInt operator<<(unsigned Bits) const {
+ return shl(Bits);
+ }
/// Arithmetic right-shift this APInt by shiftAmt.
/// @brief Arithmetic right-shift function.
/// @brief Left-shift function.
APInt shl(uint32_t shiftAmt) const;
+ /// @brief Rotate left by rotateAmt.
+ APInt rotl(uint32_t rotateAmt) const;
+
+ /// @brief Rotate right by rotateAmt.
+ APInt rotr(uint32_t rotateAmt) const;
+
/// Perform an unsigned divide operation on this APInt by RHS. Both this and
/// RHS are treated as unsigned quantities for purposes of this division.
/// @returns a new APInt value containing the division result
return this->udiv(RHS);
}
- /// Perform an Unsigned remainder operation on this APInt with RHS being the
+ /// Perform an unsigned remainder operation on this APInt with RHS being the
/// divisor. Both this and RHS are treated as unsigned quantities for purposes
- /// of this operation.
+ /// of this operation. Note that this is a true remainder operation and not
+ /// a modulo operation because the sign follows the sign of the dividend
+ /// which is *this.
/// @returns a new APInt value containing the remainder result
/// @brief Unsigned remainder operation.
APInt urem(const APInt& RHS) const;
inline APInt srem(const APInt& RHS) const {
if (isNegative())
if (RHS.isNegative())
- return (-(*this)).urem(-RHS);
+ return -((-(*this)).urem(-RHS));
else
return -((-(*this)).urem(RHS));
else if (RHS.isNegative())
- return -(this->urem(-RHS));
+ return this->urem(-RHS);
return this->urem(RHS);
}
+ /// Sometimes it is convenient to divide two APInt values and obtain both
+ /// the quotient and remainder. This function does both operations in the
+ /// same computation making it a little more efficient.
+ /// @brief Dual division/remainder interface.
+ static void udivrem(const APInt &LHS, const APInt &RHS,
+ APInt &Quotient, APInt &Remainder);
+
+ static void sdivrem(const APInt &LHS, const APInt &RHS,
+ APInt &Quotient, APInt &Remainder)
+ {
+ if (LHS.isNegative()) {
+ if (RHS.isNegative())
+ APInt::udivrem(-LHS, -RHS, Quotient, Remainder);
+ else
+ APInt::udivrem(-LHS, RHS, Quotient, Remainder);
+ Quotient = -Quotient;
+ Remainder = -Remainder;
+ } else if (RHS.isNegative()) {
+ APInt::udivrem(LHS, -RHS, Quotient, Remainder);
+ Quotient = -Quotient;
+ } else {
+ APInt::udivrem(LHS, RHS, Quotient, Remainder);
+ }
+ }
+
/// @returns the bit value at bitPosition
/// @brief Array-indexing support.
bool operator[](uint32_t bitPosition) const;
/// @brief Sign extend to a new width.
APInt &sext(uint32_t width);
- /// This operation zero extends the APInt to a new width. Thie high order bits
+ /// This operation zero extends the APInt to a new width. The high order bits
/// are filled with 0 bits. It is an error to specify a width that is less
/// than or equal to the current width.
/// @brief Zero extend to a new width.
/// @brief Zero extend or truncate to width
APInt &zextOrTrunc(uint32_t width);
- /// This is a help function for convenience. If the given \p width equals to
- /// this APInt's BitWidth, just return this APInt, otherwise, just zero
- /// extend it.
- inline APInt &zextOrCopy(uint32_t width) {
- if (width == BitWidth)
- return *this;
- return zext(width);
- }
-
/// @}
/// @name Bit Manipulation Operators
/// @{
inline uint32_t getMinSignedBits() const {
if (isNegative())
return BitWidth - countLeadingOnes() + 1;
- return getActiveBits();
+ return getActiveBits()+1;
}
/// This method attempts to return the value of this APInt as a zero extended
assert(getActiveBits() <= 64 && "Too many bits for int64_t");
return int64_t(pVal[0]);
}
+
+ /// This method determines how many bits are required to hold the APInt
+ /// equivalent of the string given by \p str of length \p slen.
+ /// @brief Get bits required for string value.
+ static uint32_t getBitsNeeded(const char* str, uint32_t slen, uint8_t radix);
+
/// countLeadingZeros - This function is an APInt version of the
/// countLeadingZeros_{32,64} functions in MathExtras.h. It counts the number
/// of zeros from the most significant bit to the first one bit.
/// radix given. The radix can be 2, 8, 10 or 16.
/// @returns a character interpretation of the APInt
/// @brief Convert unsigned APInt to string representation.
- inline std::string toString(uint8_t radix = 10) const {
+ inline std::string toStringUnsigned(uint8_t radix = 10) const {
return toString(radix, false);
}
return BitWidth - 1 - countLeadingZeros();
}
+ /// @returns the log base 2 of this APInt if its an exact power of two, -1
+ /// otherwise
+ inline int32_t exactLogBase2() const {
+ if (!isPowerOf2())
+ return -1;
+ return logBase2();
+ }
+
/// @brief Compute the square root
APInt sqrt() const;
return -(*this);
return *this;
}
+
+ /// @}
+
+ /// @}
+ /// @name Building-block Operations for APInt and APFloat
+ /// @{
+
+ // These building block operations operate on a representation of
+ // arbitrary precision, two's-complement, bignum integer values.
+ // They should be sufficient to implement APInt and APFloat bignum
+ // requirements. Inputs are generally a pointer to the base of an
+ // array of integer parts, representing an unsigned bignum, and a
+ // count of how many parts there are.
+
+ /// Sets the least significant part of a bignum to the input value,
+ /// and zeroes out higher parts. */
+ static void tcSet(integerPart *, integerPart, unsigned int);
+
+ /// Assign one bignum to another.
+ static void tcAssign(integerPart *, const integerPart *, unsigned int);
+
+ /// Returns true if a bignum is zero, false otherwise.
+ static bool tcIsZero(const integerPart *, unsigned int);
+
+ /// Extract the given bit of a bignum; returns 0 or 1. Zero-based.
+ static int tcExtractBit(const integerPart *, unsigned int bit);
+
+ /// Copy the bit vector of width srcBITS from SRC, starting at bit
+ /// srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB
+ /// becomes the least significant bit of DST. All high bits above
+ /// srcBITS in DST are zero-filled.
+ static void tcExtract(integerPart *, unsigned int dstCount, const integerPart *,
+ unsigned int srcBits, unsigned int srcLSB);
+
+ /// Set the given bit of a bignum. Zero-based.
+ static void tcSetBit(integerPart *, unsigned int bit);
+
+ /// Returns the bit number of the least or most significant set bit
+ /// of a number. If the input number has no bits set -1U is
+ /// returned.
+ static unsigned int tcLSB(const integerPart *, unsigned int);
+ static unsigned int tcMSB(const integerPart *, unsigned int);
+
+ /// Negate a bignum in-place.
+ static void tcNegate(integerPart *, unsigned int);
+
+ /// DST += RHS + CARRY where CARRY is zero or one. Returns the
+ /// carry flag.
+ static integerPart tcAdd(integerPart *, const integerPart *,
+ integerPart carry, unsigned);
+
+ /// DST -= RHS + CARRY where CARRY is zero or one. Returns the
+ /// carry flag.
+ static integerPart tcSubtract(integerPart *, const integerPart *,
+ integerPart carry, unsigned);
+
+ /// DST += SRC * MULTIPLIER + PART if add is true
+ /// DST = SRC * MULTIPLIER + PART if add is false
+ ///
+ /// Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC
+ /// they must start at the same point, i.e. DST == SRC.
+ ///
+ /// If DSTPARTS == SRC_PARTS + 1 no overflow occurs and zero is
+ /// returned. Otherwise DST is filled with the least significant
+ /// DSTPARTS parts of the result, and if all of the omitted higher
+ /// parts were zero return zero, otherwise overflow occurred and
+ /// return one.
+ static int tcMultiplyPart(integerPart *dst, const integerPart *src,
+ integerPart multiplier, integerPart carry,
+ unsigned int srcParts, unsigned int dstParts,
+ bool add);
+
+ /// DST = LHS * RHS, where DST has the same width as the operands
+ /// and is filled with the least significant parts of the result.
+ /// Returns one if overflow occurred, otherwise zero. DST must be
+ /// disjoint from both operands.
+ static int tcMultiply(integerPart *, const integerPart *,
+ const integerPart *, unsigned);
+
+ /// DST = LHS * RHS, where DST has width the sum of the widths of
+ /// the operands. No overflow occurs. DST must be disjoint from
+ /// both operands. Returns the number of parts required to hold the
+ /// result.
+ static unsigned int tcFullMultiply(integerPart *, const integerPart *,
+ const integerPart *, unsigned, unsigned);
+
+ /// If RHS is zero LHS and REMAINDER are left unchanged, return one.
+ /// Otherwise set LHS to LHS / RHS with the fractional part
+ /// discarded, set REMAINDER to the remainder, return zero. i.e.
+ ///
+ /// OLD_LHS = RHS * LHS + REMAINDER
+ ///
+ /// SCRATCH is a bignum of the same size as the operands and result
+ /// for use by the routine; its contents need not be initialized
+ /// and are destroyed. LHS, REMAINDER and SCRATCH must be
+ /// distinct.
+ static int tcDivide(integerPart *lhs, const integerPart *rhs,
+ integerPart *remainder, integerPart *scratch,
+ unsigned int parts);
+
+ /// Shift a bignum left COUNT bits. Shifted in bits are zero.
+ /// There are no restrictions on COUNT.
+ static void tcShiftLeft(integerPart *, unsigned int parts,
+ unsigned int count);
+
+ /// Shift a bignum right COUNT bits. Shifted in bits are zero.
+ /// There are no restrictions on COUNT.
+ static void tcShiftRight(integerPart *, unsigned int parts,
+ unsigned int count);
+
+ /// The obvious AND, OR and XOR and complement operations.
+ static void tcAnd(integerPart *, const integerPart *, unsigned int);
+ static void tcOr(integerPart *, const integerPart *, unsigned int);
+ static void tcXor(integerPart *, const integerPart *, unsigned int);
+ static void tcComplement(integerPart *, unsigned int);
+
+ /// Comparison (unsigned) of two bignums.
+ static int tcCompare(const integerPart *, const integerPart *,
+ unsigned int);
+
+ /// Increment a bignum in-place. Return the carry flag.
+ static integerPart tcIncrement(integerPart *, unsigned int);
+
+ /// Set the least significant BITS and clear the rest.
+ static void tcSetLeastSignificantBits(integerPart *, unsigned int,
+ unsigned int bits);
+
+ /// @brief debug method
+ void dump() const;
+
/// @}
};
/// @returns true if the argument APInt value is a sequence of ones
/// starting at the least significant bit with the remainder zero.
-inline const bool isMask(uint32_t numBits, const APInt& APIVal) {
+inline bool isMask(uint32_t numBits, const APInt& APIVal) {
return APIVal.getBoolValue() && ((APIVal + APInt(numBits,1)) & APIVal) == 0;
}
/// @returns true if the argument APInt value contains a sequence of ones
/// with the remainder zero.
-inline const bool isShiftedMask(uint32_t numBits, const APInt& APIVal) {
+inline bool isShiftedMask(uint32_t numBits, const APInt& APIVal) {
return isMask(numBits, (APIVal - APInt(numBits,1)) | APIVal);
}
projects / oota-llvm.git / blobdiff