X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;ds=sidebyside;f=include%2Fllvm%2FADT%2FAPInt.h;h=c98ff18d1017ee9d5ba91f5da2ed1b9ee59c4757;hb=300c6c5167d2869d1568d783d0e3e48bf4b03a6c;hp=3a98ae42349d7cdb0e378892b01d537dfc283dab;hpb=7ed47a13356daed2a34cd2209a31f92552e3bdd8;p=oota-llvm.git diff --git a/include/llvm/ADT/APInt.h b/include/llvm/ADT/APInt.h index 3a98ae42349..c98ff18d101 100644 --- a/include/llvm/ADT/APInt.h +++ b/include/llvm/ADT/APInt.h @@ -24,13 +24,15 @@ namespace llvm { class Serializer; class Deserializer; + class FoldingSetNodeID; /* 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); + const unsigned int integerPartWidth = host_char_bit * + static_cast(sizeof(integerPart)); //===----------------------------------------------------------------------===// // APInt Class @@ -75,8 +77,10 @@ class APInt { /// This enum is used to hold the constants we needed for APInt. enum { - APINT_BITS_PER_WORD = sizeof(uint64_t) * 8, ///< Bits in a word - APINT_WORD_SIZE = sizeof(uint64_t) ///< Byte size of a word + /// Bits in a word + APINT_BITS_PER_WORD = static_cast(sizeof(uint64_t)) * 8, + /// Byte size of a word + APINT_WORD_SIZE = static_cast(sizeof(uint64_t)) }; /// This constructor is used only internally for speed of construction of @@ -86,20 +90,20 @@ class APInt { /// @returns true if the number of bits <= 64, false otherwise. /// @brief Determine if this APInt just has one word to store value. - inline bool isSingleWord() const { + bool isSingleWord() const { return BitWidth <= APINT_BITS_PER_WORD; } /// @returns the word position for the specified bit position. /// @brief Determine which word a bit is in. - static inline uint32_t whichWord(uint32_t bitPosition) { + static uint32_t whichWord(uint32_t bitPosition) { return bitPosition / APINT_BITS_PER_WORD; } /// @returns the bit position in a word for the specified bit position /// in the APInt. /// @brief Determine which bit in a word a bit is in. - static inline uint32_t whichBit(uint32_t bitPosition) { + static uint32_t whichBit(uint32_t bitPosition) { return bitPosition % APINT_BITS_PER_WORD; } @@ -108,7 +112,7 @@ class APInt { /// corresponding word. /// @returns a uint64_t with only bit at "whichBit(bitPosition)" set /// @brief Get a single bit mask. - static inline uint64_t maskBit(uint32_t bitPosition) { + static uint64_t maskBit(uint32_t bitPosition) { return 1ULL << whichBit(bitPosition); } @@ -117,16 +121,16 @@ class APInt { /// significant word is assigned a value to ensure that those bits are /// zero'd out. /// @brief Clear unused high order bits - inline APInt& clearUnusedBits() { + APInt& clearUnusedBits() { // Compute how many bits are used in the final word uint32_t wordBits = BitWidth % APINT_BITS_PER_WORD; if (wordBits == 0) // If all bits are used, we want to leave the value alone. This also - // avoids the undefined behavior of >> when the shfit is the same size as + // avoids the undefined behavior of >> when the shift is the same size as // the word size (64). return *this; - // Mask out the hight bits. + // Mask out the high bits. uint64_t mask = ~uint64_t(0ULL) >> (APINT_BITS_PER_WORD - wordBits); if (isSingleWord()) VAL &= mask; @@ -137,7 +141,7 @@ class APInt { /// @returns the corresponding word for the specified bit position. /// @brief Get the word corresponding to a bit position - inline uint64_t getWord(uint32_t bitPosition) const { + uint64_t getWord(uint32_t bitPosition) const { return isSingleWord() ? VAL : pVal[whichWord(bitPosition)]; } @@ -210,6 +214,10 @@ public: /// for object deserialization (pair this with the static method Read). explicit APInt() : BitWidth(1) {} + /// Profile - Used to insert APInt objects, or objects that contain APInt + /// objects, into FoldingSets. + void Profile(FoldingSetNodeID& id) const; + /// @brief Used by the Bitcode serializer to emit APInts to Bitcode. void Emit(Serializer& S) const; @@ -227,21 +235,22 @@ public: } /// This tests the high bit of the APInt to determine if it is unset. - /// @brief Determine if this APInt Value is positive (not negative). - bool isPositive() const { + /// @brief Determine if this APInt Value is non-negative (>= 0) + bool isNonNegative() const { return !isNegative(); } - /// This tests if the value of this APInt is strictly positive (> 0). - /// @returns true if this APInt is Positive and not zero. - /// @brief Determine if this APInt Value is strictly positive. - inline bool isStrictlyPositive() const { - return isPositive() && (*this) != 0; + /// This tests if the value of this APInt is positive (> 0). Note + /// that 0 is not a positive value. + /// @returns true if this APInt is positive. + /// @brief Determine if this APInt Value is positive. + bool isStrictlyPositive() const { + return isNonNegative() && (*this) != 0; } /// This checks to see if the value has all bits of the APInt are set or not. /// @brief Determine if all bits are set - inline bool isAllOnesValue() const { + bool isAllOnesValue() const { return countPopulation() == BitWidth; } @@ -275,8 +284,8 @@ public: isNegative() && countPopulation() == 1; } - /// @brief Check if this APInt has an N-bits integer value. - inline bool isIntN(uint32_t N) const { + /// @brief Check if this APInt has an N-bits unsigned integer value. + bool isIntN(uint32_t N) const { assert(N && "N == 0 ???"); if (isSingleWord()) { return VAL == (VAL & (~0ULL >> (64 - N))); @@ -286,6 +295,12 @@ public: } } + /// @brief Check if this APInt has an N-bits signed integer value. + bool isSignedIntN(uint32_t N) const { + assert(N && "N == 0 ???"); + return getMinSignedBits() <= N; + } + /// @returns true if the argument APInt value is a power of two > 0. bool isPowerOf2() const; @@ -294,7 +309,7 @@ public: /// This converts the APInt to a boolean value as a test against zero. /// @brief Boolean conversion function. - inline bool getBoolValue() const { + bool getBoolValue() const { return *this != 0; } @@ -332,7 +347,7 @@ public: /// getSignBit - This is just a wrapper function of getSignedMinValue(), and /// it helps code readability when we want to get a SignBit. /// @brief Get the SignBit for a specific bit width. - inline static APInt getSignBit(uint32_t BitWidth) { + static APInt getSignBit(uint32_t BitWidth) { return getSignedMinValue(BitWidth); } @@ -359,22 +374,22 @@ public: APInt getLoBits(uint32_t numBits) const; /// Constructs an APInt value that has a contiguous range of bits set. The - /// bits from loBit to hiBit will be set. All other bits will be zero. For - /// example, with parameters(32, 15, 0) you would get 0x0000FFFF. If hiBit is - /// less than loBit then the set bits "wrap". For example, with - /// parameters (32, 3, 28), you would get 0xF000000F. + /// bits from loBit (inclusive) to hiBit (exclusive) will be set. All other + /// bits will be zero. For example, with parameters(32, 0, 16) you would get + /// 0x0000FFFF. If hiBit is less than loBit then the set bits "wrap". For + /// example, with parameters (32, 28, 4), you would get 0xF000000F. /// @param numBits the intended bit width of the result /// @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 loBit, uint32_t hiBit) { - assert(hiBit < numBits && "hiBit out of range"); + 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); + return getLowBitsSet(numBits, hiBit) | + getHighBitsSet(numBits, numBits-loBit); + return getLowBitsSet(numBits, hiBit-loBit).shl(loBit); } /// Constructs an APInt value that has the top hiBitsSet bits set. @@ -418,7 +433,7 @@ public: /// This function returns a pointer to the internal storage of the APInt. /// This is useful for writing out the APInt in binary form without any /// conversions. - inline const uint64_t* getRawData() const { + const uint64_t* getRawData() const { if (isSingleWord()) return &VAL; return &pVal[0]; @@ -429,7 +444,7 @@ public: /// @{ /// @returns a new APInt value representing *this incremented by one /// @brief Postfix increment operator. - inline const APInt operator++(int) { + const APInt operator++(int) { APInt API(*this); ++(*this); return API; @@ -441,7 +456,7 @@ public: /// @returns a new APInt representing *this decremented by one. /// @brief Postfix decrement operator. - inline const APInt operator--(int) { + const APInt operator--(int) { APInt API(*this); --(*this); return API; @@ -459,7 +474,7 @@ public: /// Negates *this using two's complement logic. /// @returns An APInt value representing the negation of *this. /// @brief Unary negation operator - inline APInt operator-() const { + APInt operator-() const { return APInt(BitWidth, 0) - (*this); } @@ -518,7 +533,7 @@ public: /// Shifts *this left by shiftAmt and assigns the result to *this. /// @returns *this after shifting left by shiftAmt /// @brief Left-shift assignment function. - inline APInt& operator<<=(uint32_t shiftAmt) { + APInt& operator<<=(uint32_t shiftAmt) { *this = shl(shiftAmt); return *this; } @@ -572,6 +587,10 @@ public: return shl(Bits); } + APInt operator<<(const APInt &Bits) const { + return shl(Bits); + } + /// Arithmetic right-shift this APInt by shiftAmt. /// @brief Arithmetic right-shift function. APInt ashr(uint32_t shiftAmt) const; @@ -590,6 +609,24 @@ public: /// @brief Rotate right by rotateAmt. APInt rotr(uint32_t rotateAmt) const; + /// Arithmetic right-shift this APInt by shiftAmt. + /// @brief Arithmetic right-shift function. + APInt ashr(const APInt &shiftAmt) const; + + /// Logical right-shift this APInt by shiftAmt. + /// @brief Logical right-shift function. + APInt lshr(const APInt &shiftAmt) const; + + /// Left-shift this APInt by shiftAmt. + /// @brief Left-shift function. + APInt shl(const APInt &shiftAmt) const; + + /// @brief Rotate left by rotateAmt. + APInt rotl(const APInt &rotateAmt) const; + + /// @brief Rotate right by rotateAmt. + APInt rotr(const APInt &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 @@ -598,7 +635,7 @@ public: /// Signed divide this APInt by APInt RHS. /// @brief Signed division function for APInt. - inline APInt sdiv(const APInt& RHS) const { + APInt sdiv(const APInt& RHS) const { if (isNegative()) if (RHS.isNegative()) return (-(*this)).udiv(-RHS); @@ -620,7 +657,7 @@ public: /// Signed remainder operation on APInt. /// @brief Function for signed remainder operation. - inline APInt srem(const APInt& RHS) const { + APInt srem(const APInt& RHS) const { if (isNegative()) if (RHS.isNegative()) return -((-(*this)).urem(-RHS)); @@ -631,9 +668,11 @@ public: 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. + /// 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. The pair of input arguments + /// may overlap with the pair of output arguments. It is safe to call + /// udivrem(X, Y, X, Y), for example. /// @brief Dual division/remainder interface. static void udivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, APInt &Remainder); @@ -686,7 +725,7 @@ public: /// relationship. /// @returns true if *this != Val /// @brief Inequality operator. - inline bool operator!=(const APInt& RHS) const { + bool operator!=(const APInt& RHS) const { return !((*this) == RHS); } @@ -694,7 +733,7 @@ public: /// relationship. /// @returns true if *this != Val /// @brief Inequality operator. - inline bool operator!=(uint64_t Val) const { + bool operator!=(uint64_t Val) const { return !((*this) == Val); } @@ -766,6 +805,12 @@ public: return !slt(RHS); } + /// This operation tests if there are any pairs of corresponding bits + /// between this APInt and RHS that are both set. + bool intersects(const APInt &RHS) const { + return (*this & RHS) != 0; + } + /// @} /// @name Resizing Operators /// @{ @@ -827,14 +872,14 @@ public: /// @{ /// @returns the total number of bits. - inline uint32_t getBitWidth() const { + uint32_t getBitWidth() const { return BitWidth; } /// Here one word's bitwidth equals to that of uint64_t. /// @returns the number of words to hold the integer value of this APInt. /// @brief Get the number of words. - inline uint32_t getNumWords() const { + uint32_t getNumWords() const { return (BitWidth + APINT_BITS_PER_WORD - 1) / APINT_BITS_PER_WORD; } @@ -842,25 +887,25 @@ public: /// bit width minus the number of leading zeros. This is used in several /// computations to see how "wide" the value is. /// @brief Compute the number of active bits in the value - inline uint32_t getActiveBits() const { + uint32_t getActiveBits() const { return BitWidth - countLeadingZeros(); } /// This function returns the number of active words in the value of this /// APInt. This is used in conjunction with getActiveData to extract the raw /// value of the APInt. - inline uint32_t getActiveWords() const { + uint32_t getActiveWords() const { return whichWord(getActiveBits()-1) + 1; } /// Computes the minimum bit width for this APInt while considering it to be /// a signed (and probably negative) value. If the value is not negative, - /// this function returns the same value as getActiveBits(). Otherwise, it + /// this function returns the same value as getActiveBits()+1. Otherwise, it /// returns the smallest bit width that will retain the negative value. For /// example, -1 can be written as 0b1 or 0xFFFFFFFFFF. 0b1 is shorter and so /// for -1, this function will always return 1. /// @brief Get the minimum bit size for this signed APInt - inline uint32_t getMinSignedBits() const { + uint32_t getMinSignedBits() const { if (isNegative()) return BitWidth - countLeadingOnes() + 1; return getActiveBits()+1; @@ -870,7 +915,7 @@ public: /// uint64_t. The bitwidth must be <= 64 or the value must fit within a /// uint64_t. Otherwise an assertion will result. /// @brief Get zero extended value - inline uint64_t getZExtValue() const { + uint64_t getZExtValue() const { if (isSingleWord()) return VAL; assert(getActiveBits() <= 64 && "Too many bits for uint64_t"); @@ -881,7 +926,7 @@ public: /// int64_t. The bit width must be <= 64 or the value must fit within an /// int64_t. Otherwise an assertion will result. /// @brief Get sign extended value - inline int64_t getSExtValue() const { + int64_t getSExtValue() const { if (isSingleWord()) return int64_t(VAL << (APINT_BITS_PER_WORD - BitWidth)) >> (APINT_BITS_PER_WORD - BitWidth); @@ -902,15 +947,16 @@ public: /// one bits. uint32_t countLeadingZeros() const; - /// countLeadingOnes - This function counts the number of contiguous 1 bits - /// in the high order bits. The count stops when the first 0 bit is reached. + /// countLeadingOnes - This function is an APInt version of the + /// countLeadingOnes_{32,64} functions in MathExtras.h. It counts the number + /// of ones from the most significant bit to the first zero bit. /// @returns 0 if the high order bit is not set /// @returns the number of 1 bits from the most significant to the least /// @brief Count the number of leading one bits. uint32_t countLeadingOnes() const; /// countTrailingZeros - This function is an APInt version of the - /// countTrailingZoers_{32,64} functions in MathExtras.h. It counts + /// countTrailingZeros_{32,64} functions in MathExtras.h. It counts /// the number of zeros from the least significant bit to the first set bit. /// @returns BitWidth if the value is zero. /// @returns the number of zeros from the least significant bit to the first @@ -918,6 +964,15 @@ public: /// @brief Count the number of trailing zero bits. uint32_t countTrailingZeros() const; + /// countTrailingOnes - This function is an APInt version of the + /// countTrailingOnes_{32,64} functions in MathExtras.h. It counts + /// the number of ones from the least significant bit to the first zero bit. + /// @returns BitWidth if the value is all ones. + /// @returns the number of ones from the least significant bit to the first + /// zero bit. + /// @brief Count the number of trailing one bits. + uint32_t countTrailingOnes() const; + /// countPopulation - This function is an APInt version of the /// countPopulation_{32,64} functions in MathExtras.h. It counts the number /// of 1 bits in the APInt value. @@ -938,7 +993,7 @@ public: /// 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 toStringUnsigned(uint8_t radix = 10) const { + std::string toStringUnsigned(uint8_t radix = 10) const { return toString(radix, false); } @@ -946,7 +1001,7 @@ public: /// 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 toStringSigned(uint8_t radix = 10) const { + std::string toStringSigned(uint8_t radix = 10) const { return toString(radix, true); } @@ -1031,13 +1086,13 @@ public: /// @{ /// @returns the floor log base 2 of this APInt. - inline uint32_t logBase2() const { + uint32_t logBase2() const { 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 { + int32_t exactLogBase2() const { if (!isPowerOf2()) return -1; return logBase2(); @@ -1054,7 +1109,8 @@ public: return *this; } - /// @} + /// @returns the multiplicative inverse for a given modulo. + APInt multiplicativeInverse(const APInt& modulo) const; /// @} /// @name Building-block Operations for APInt and APFloat @@ -1102,12 +1158,12 @@ public: /// DST += RHS + CARRY where CARRY is zero or one. Returns the /// carry flag. static integerPart tcAdd(integerPart *, const integerPart *, - integerPart carry, unsigned); + 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); + integerPart carry, unsigned); /// DST += SRC * MULTIPLIER + PART if add is true /// DST = SRC * MULTIPLIER + PART if add is false @@ -1121,23 +1177,23 @@ public: /// 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); + 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); + 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); + 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 @@ -1150,18 +1206,18 @@ public: /// 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); + 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); + 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); + unsigned int count); /// The obvious AND, OR and XOR and complement operations. static void tcAnd(integerPart *, const integerPart *, unsigned int); @@ -1171,14 +1227,14 @@ public: /// Comparison (unsigned) of two bignums. static int tcCompare(const integerPart *, const integerPart *, - unsigned int); + 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); + unsigned int bits); /// @brief debug method void dump() const; @@ -1216,15 +1272,21 @@ inline APInt umax(const APInt &A, const APInt &B) { return A.ugt(B) ? A : B; } -/// @brief Check if the specified APInt has a N-bits integer value. +/// @brief Check if the specified APInt has a N-bits unsigned integer value. inline bool isIntN(uint32_t N, const APInt& APIVal) { return APIVal.isIntN(N); } +/// @brief Check if the specified APInt has a N-bits signed integer value. +inline bool isSignedIntN(uint32_t N, const APInt& APIVal) { + return APIVal.isSignedIntN(N); +} + /// @returns true if the argument APInt value is a sequence of ones /// starting at the least significant bit with the remainder zero. inline bool isMask(uint32_t numBits, const APInt& APIVal) { - return APIVal.getBoolValue() && ((APIVal + APInt(numBits,1)) & APIVal) == 0; + return numBits <= APIVal.getBitWidth() && + APIVal == APInt::getLowBitsSet(APIVal.getBitWidth(), numBits); } /// @returns true if the argument APInt value contains a sequence of ones @@ -1244,7 +1306,7 @@ inline uint32_t logBase2(const APInt& APIVal) { } /// GreatestCommonDivisor - This function returns the greatest common -/// divisor of the two APInt values using Enclid's algorithm. +/// divisor of the two APInt values using Euclid's algorithm. /// @returns the greatest common divisor of Val1 and Val2 /// @brief Compute GCD of two APInt values. APInt GreatestCommonDivisor(const APInt& Val1, const APInt& Val2);