//===-- APInt.cpp - Implement APInt class ---------------------------------===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// // // This file implements a class to represent arbitrary precision integer // constant values and provide a variety of arithmetic operations on them. // //===----------------------------------------------------------------------===// #include "llvm/ADT/APInt.h" #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/FoldingSet.h" #include "llvm/ADT/Hashing.h" #include "llvm/ADT/SmallString.h" #include "llvm/ADT/StringRef.h" #include "llvm/ADT/bit.h" #include "llvm/Config/llvm-config.h" #include "llvm/Support/Alignment.h" #include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/MathExtras.h" #include "llvm/Support/raw_ostream.h" #include <cmath> #include <optional> usingnamespacellvm; #define DEBUG_TYPE … /// A utility function for allocating memory, checking for allocation failures, /// and ensuring the contents are zeroed. inline static uint64_t* getClearedMemory(unsigned numWords) { … } /// A utility function for allocating memory and checking for allocation /// failure. The content is not zeroed. inline static uint64_t* getMemory(unsigned numWords) { … } /// A utility function that converts a character to a digit. inline static unsigned getDigit(char cdigit, uint8_t radix) { … } void APInt::initSlowCase(uint64_t val, bool isSigned) { … } void APInt::initSlowCase(const APInt& that) { … } void APInt::initFromArray(ArrayRef<uint64_t> bigVal) { … } APInt::APInt(unsigned numBits, ArrayRef<uint64_t> bigVal) : … { … } APInt::APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[]) : … { … } APInt::APInt(unsigned numbits, StringRef Str, uint8_t radix) : … { … } void APInt::reallocate(unsigned NewBitWidth) { … } void APInt::assignSlowCase(const APInt &RHS) { … } /// This method 'profiles' an APInt for use with FoldingSet. void APInt::Profile(FoldingSetNodeID& ID) const { … } bool APInt::isAligned(Align A) const { … } /// Prefix increment operator. Increments the APInt by one. APInt& APInt::operator++() { … } /// Prefix decrement operator. Decrements the APInt by one. APInt& APInt::operator--() { … } /// Adds the RHS APInt to this APInt. /// @returns this, after addition of RHS. /// Addition assignment operator. APInt& APInt::operator+=(const APInt& RHS) { … } APInt& APInt::operator+=(uint64_t RHS) { … } /// Subtracts the RHS APInt from this APInt /// @returns this, after subtraction /// Subtraction assignment operator. APInt& APInt::operator-=(const APInt& RHS) { … } APInt& APInt::operator-=(uint64_t RHS) { … } APInt APInt::operator*(const APInt& RHS) const { … } void APInt::andAssignSlowCase(const APInt &RHS) { … } void APInt::orAssignSlowCase(const APInt &RHS) { … } void APInt::xorAssignSlowCase(const APInt &RHS) { … } APInt &APInt::operator*=(const APInt &RHS) { … } APInt& APInt::operator*=(uint64_t RHS) { … } bool APInt::equalSlowCase(const APInt &RHS) const { … } int APInt::compare(const APInt& RHS) const { … } int APInt::compareSigned(const APInt& RHS) const { … } void APInt::setBitsSlowCase(unsigned loBit, unsigned hiBit) { … } // Complement a bignum in-place. static void tcComplement(APInt::WordType *dst, unsigned parts) { … } /// Toggle every bit to its opposite value. void APInt::flipAllBitsSlowCase() { … } /// Concatenate the bits from "NewLSB" onto the bottom of *this. This is /// equivalent to: /// (this->zext(NewWidth) << NewLSB.getBitWidth()) | NewLSB.zext(NewWidth) /// In the slow case, we know the result is large. APInt APInt::concatSlowCase(const APInt &NewLSB) const { … } /// Toggle a given bit to its opposite value whose position is given /// as "bitPosition". /// Toggles a given bit to its opposite value. void APInt::flipBit(unsigned bitPosition) { … } void APInt::insertBits(const APInt &subBits, unsigned bitPosition) { … } void APInt::insertBits(uint64_t subBits, unsigned bitPosition, unsigned numBits) { … } APInt APInt::extractBits(unsigned numBits, unsigned bitPosition) const { … } uint64_t APInt::extractBitsAsZExtValue(unsigned numBits, unsigned bitPosition) const { … } unsigned APInt::getSufficientBitsNeeded(StringRef Str, uint8_t Radix) { … } unsigned APInt::getBitsNeeded(StringRef str, uint8_t radix) { … } hash_code llvm::hash_value(const APInt &Arg) { … } unsigned DenseMapInfo<APInt, void>::getHashValue(const APInt &Key) { … } bool APInt::isSplat(unsigned SplatSizeInBits) const { … } /// This function returns the high "numBits" bits of this APInt. APInt APInt::getHiBits(unsigned numBits) const { … } /// This function returns the low "numBits" bits of this APInt. APInt APInt::getLoBits(unsigned numBits) const { … } /// Return a value containing V broadcasted over NewLen bits. APInt APInt::getSplat(unsigned NewLen, const APInt &V) { … } unsigned APInt::countLeadingZerosSlowCase() const { … } unsigned APInt::countLeadingOnesSlowCase() const { … } unsigned APInt::countTrailingZerosSlowCase() const { … } unsigned APInt::countTrailingOnesSlowCase() const { … } unsigned APInt::countPopulationSlowCase() const { … } bool APInt::intersectsSlowCase(const APInt &RHS) const { … } bool APInt::isSubsetOfSlowCase(const APInt &RHS) const { … } APInt APInt::byteSwap() const { … } APInt APInt::reverseBits() const { … } APInt llvm::APIntOps::GreatestCommonDivisor(APInt A, APInt B) { … } APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) { … } /// This function converts this APInt to a double. /// The layout for double is as following (IEEE Standard 754): /// -------------------------------------- /// | Sign Exponent Fraction Bias | /// |-------------------------------------- | /// | 1[63] 11[62-52] 52[51-00] 1023 | /// -------------------------------------- double APInt::roundToDouble(bool isSigned) const { … } // Truncate to new width. APInt APInt::trunc(unsigned width) const { … } // Truncate to new width with unsigned saturation. APInt APInt::truncUSat(unsigned width) const { … } // Truncate to new width with signed saturation. APInt APInt::truncSSat(unsigned width) const { … } // Sign extend to a new width. APInt APInt::sext(unsigned Width) const { … } // Zero extend to a new width. APInt APInt::zext(unsigned width) const { … } APInt APInt::zextOrTrunc(unsigned width) const { … } APInt APInt::sextOrTrunc(unsigned width) const { … } /// Arithmetic right-shift this APInt by shiftAmt. /// Arithmetic right-shift function. void APInt::ashrInPlace(const APInt &shiftAmt) { … } /// Arithmetic right-shift this APInt by shiftAmt. /// Arithmetic right-shift function. void APInt::ashrSlowCase(unsigned ShiftAmt) { … } /// Logical right-shift this APInt by shiftAmt. /// Logical right-shift function. void APInt::lshrInPlace(const APInt &shiftAmt) { … } /// Logical right-shift this APInt by shiftAmt. /// Logical right-shift function. void APInt::lshrSlowCase(unsigned ShiftAmt) { … } /// Left-shift this APInt by shiftAmt. /// Left-shift function. APInt &APInt::operator<<=(const APInt &shiftAmt) { … } void APInt::shlSlowCase(unsigned ShiftAmt) { … } // Calculate the rotate amount modulo the bit width. static unsigned rotateModulo(unsigned BitWidth, const APInt &rotateAmt) { … } APInt APInt::rotl(const APInt &rotateAmt) const { … } APInt APInt::rotl(unsigned rotateAmt) const { … } APInt APInt::rotr(const APInt &rotateAmt) const { … } APInt APInt::rotr(unsigned rotateAmt) const { … } /// \returns the nearest log base 2 of this APInt. Ties round up. /// /// NOTE: When we have a BitWidth of 1, we define: /// /// log2(0) = UINT32_MAX /// log2(1) = 0 /// /// to get around any mathematical concerns resulting from /// referencing 2 in a space where 2 does no exist. unsigned APInt::nearestLogBase2() const { … } // Square Root - this method computes and returns the square root of "this". // Three mechanisms are used for computation. For small values (<= 5 bits), // a table lookup is done. This gets some performance for common cases. For // values using less than 52 bits, the value is converted to double and then // the libc sqrt function is called. The result is rounded and then converted // back to a uint64_t which is then used to construct the result. Finally, // the Babylonian method for computing square roots is used. APInt APInt::sqrt() const { … } /// \returns the multiplicative inverse of an odd APInt modulo 2^BitWidth. APInt APInt::multiplicativeInverse() const { … } /// Implementation of Knuth's Algorithm D (Division of nonnegative integers) /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The /// variables here have the same names as in the algorithm. Comments explain /// the algorithm and any deviation from it. static void KnuthDiv(uint32_t *u, uint32_t *v, uint32_t *q, uint32_t* r, unsigned m, unsigned n) { … } void APInt::divide(const WordType *LHS, unsigned lhsWords, const WordType *RHS, unsigned rhsWords, WordType *Quotient, WordType *Remainder) { … } APInt APInt::udiv(const APInt &RHS) const { … } APInt APInt::udiv(uint64_t RHS) const { … } APInt APInt::sdiv(const APInt &RHS) const { … } APInt APInt::sdiv(int64_t RHS) const { … } APInt APInt::urem(const APInt &RHS) const { … } uint64_t APInt::urem(uint64_t RHS) const { … } APInt APInt::srem(const APInt &RHS) const { … } int64_t APInt::srem(int64_t RHS) const { … } void APInt::udivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, APInt &Remainder) { … } void APInt::udivrem(const APInt &LHS, uint64_t RHS, APInt &Quotient, uint64_t &Remainder) { … } void APInt::sdivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, APInt &Remainder) { … } void APInt::sdivrem(const APInt &LHS, int64_t RHS, APInt &Quotient, int64_t &Remainder) { … } APInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const { … } APInt APInt::uadd_ov(const APInt &RHS, bool &Overflow) const { … } APInt APInt::ssub_ov(const APInt &RHS, bool &Overflow) const { … } APInt APInt::usub_ov(const APInt &RHS, bool &Overflow) const { … } APInt APInt::sdiv_ov(const APInt &RHS, bool &Overflow) const { … } APInt APInt::smul_ov(const APInt &RHS, bool &Overflow) const { … } APInt APInt::umul_ov(const APInt &RHS, bool &Overflow) const { … } APInt APInt::sshl_ov(const APInt &ShAmt, bool &Overflow) const { … } APInt APInt::sshl_ov(unsigned ShAmt, bool &Overflow) const { … } APInt APInt::ushl_ov(const APInt &ShAmt, bool &Overflow) const { … } APInt APInt::ushl_ov(unsigned ShAmt, bool &Overflow) const { … } APInt APInt::sfloordiv_ov(const APInt &RHS, bool &Overflow) const { … } APInt APInt::sadd_sat(const APInt &RHS) const { … } APInt APInt::uadd_sat(const APInt &RHS) const { … } APInt APInt::ssub_sat(const APInt &RHS) const { … } APInt APInt::usub_sat(const APInt &RHS) const { … } APInt APInt::smul_sat(const APInt &RHS) const { … } APInt APInt::umul_sat(const APInt &RHS) const { … } APInt APInt::sshl_sat(const APInt &RHS) const { … } APInt APInt::sshl_sat(unsigned RHS) const { … } APInt APInt::ushl_sat(const APInt &RHS) const { … } APInt APInt::ushl_sat(unsigned RHS) const { … } void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) { … } void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix, bool Signed, bool formatAsCLiteral, bool UpperCase, bool InsertSeparators) const { … } #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) LLVM_DUMP_METHOD void APInt::dump() const { SmallString<40> S, U; this->toStringUnsigned(U); this->toStringSigned(S); dbgs() << "APInt(" << BitWidth << "b, " << U << "u " << S << "s)\n"; } #endif void APInt::print(raw_ostream &OS, bool isSigned) const { … } // This implements a variety of operations on a representation of // arbitrary precision, two's-complement, bignum integer values. // Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe // and unrestricting assumption. static_assert …; // Returns the integer part with the least significant BITS set. // BITS cannot be zero. static inline APInt::WordType lowBitMask(unsigned bits) { … } /// Returns the value of the lower half of PART. static inline APInt::WordType lowHalf(APInt::WordType part) { … } /// Returns the value of the upper half of PART. static inline APInt::WordType highHalf(APInt::WordType part) { … } /// Sets the least significant part of a bignum to the input value, and zeroes /// out higher parts. void APInt::tcSet(WordType *dst, WordType part, unsigned parts) { … } /// Assign one bignum to another. void APInt::tcAssign(WordType *dst, const WordType *src, unsigned parts) { … } /// Returns true if a bignum is zero, false otherwise. bool APInt::tcIsZero(const WordType *src, unsigned parts) { … } /// Extract the given bit of a bignum; returns 0 or 1. int APInt::tcExtractBit(const WordType *parts, unsigned bit) { … } /// Set the given bit of a bignum. void APInt::tcSetBit(WordType *parts, unsigned bit) { … } /// Clears the given bit of a bignum. void APInt::tcClearBit(WordType *parts, unsigned bit) { … } /// Returns the bit number of the least significant set bit of a number. If the /// input number has no bits set UINT_MAX is returned. unsigned APInt::tcLSB(const WordType *parts, unsigned n) { … } /// Returns the bit number of the most significant set bit of a number. /// If the input number has no bits set UINT_MAX is returned. unsigned APInt::tcMSB(const WordType *parts, unsigned n) { … } /// 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. /// */ void APInt::tcExtract(WordType *dst, unsigned dstCount, const WordType *src, unsigned srcBits, unsigned srcLSB) { … } //// DST += RHS + C where C is zero or one. Returns the carry flag. APInt::WordType APInt::tcAdd(WordType *dst, const WordType *rhs, WordType c, unsigned parts) { … } /// This function adds a single "word" integer, src, to the multiple /// "word" integer array, dst[]. dst[] is modified to reflect the addition and /// 1 is returned if there is a carry out, otherwise 0 is returned. /// @returns the carry of the addition. APInt::WordType APInt::tcAddPart(WordType *dst, WordType src, unsigned parts) { … } /// DST -= RHS + C where C is zero or one. Returns the carry flag. APInt::WordType APInt::tcSubtract(WordType *dst, const WordType *rhs, WordType c, unsigned parts) { … } /// This function subtracts a single "word" (64-bit word), src, from /// the multi-word integer array, dst[], propagating the borrowed 1 value until /// no further borrowing is needed or it runs out of "words" in dst. The result /// is 1 if "borrowing" exhausted the digits in dst, or 0 if dst was not /// exhausted. In other words, if src > dst then this function returns 1, /// otherwise 0. /// @returns the borrow out of the subtraction APInt::WordType APInt::tcSubtractPart(WordType *dst, WordType src, unsigned parts) { … } /// Negate a bignum in-place. void APInt::tcNegate(WordType *dst, unsigned parts) { … } /// DST += SRC * MULTIPLIER + CARRY if add is true /// DST = SRC * MULTIPLIER + CARRY 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 == SRCPARTS + 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. int APInt::tcMultiplyPart(WordType *dst, const WordType *src, WordType multiplier, WordType carry, unsigned srcParts, unsigned 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. int APInt::tcMultiply(WordType *dst, const WordType *lhs, const WordType *rhs, unsigned parts) { … } /// 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. void APInt::tcFullMultiply(WordType *dst, const WordType *lhs, const WordType *rhs, unsigned lhsParts, unsigned rhsParts) { … } // 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. int APInt::tcDivide(WordType *lhs, const WordType *rhs, WordType *remainder, WordType *srhs, unsigned parts) { … } /// Shift a bignum left Count bits in-place. Shifted in bits are zero. There are /// no restrictions on Count. void APInt::tcShiftLeft(WordType *Dst, unsigned Words, unsigned Count) { … } /// Shift a bignum right Count bits in-place. Shifted in bits are zero. There /// are no restrictions on Count. void APInt::tcShiftRight(WordType *Dst, unsigned Words, unsigned Count) { … } // Comparison (unsigned) of two bignums. int APInt::tcCompare(const WordType *lhs, const WordType *rhs, unsigned parts) { … } APInt llvm::APIntOps::RoundingUDiv(const APInt &A, const APInt &B, APInt::Rounding RM) { … } APInt llvm::APIntOps::RoundingSDiv(const APInt &A, const APInt &B, APInt::Rounding RM) { … } std::optional<APInt> llvm::APIntOps::SolveQuadraticEquationWrap(APInt A, APInt B, APInt C, unsigned RangeWidth) { … } std::optional<unsigned> llvm::APIntOps::GetMostSignificantDifferentBit(const APInt &A, const APInt &B) { … } APInt llvm::APIntOps::ScaleBitMask(const APInt &A, unsigned NewBitWidth, bool MatchAllBits) { … } /// StoreIntToMemory - Fills the StoreBytes bytes of memory starting from Dst /// with the integer held in IntVal. void llvm::StoreIntToMemory(const APInt &IntVal, uint8_t *Dst, unsigned StoreBytes) { … } /// LoadIntFromMemory - Loads the integer stored in the LoadBytes bytes starting /// from Src into IntVal, which is assumed to be wide enough and to hold zero. void llvm::LoadIntFromMemory(APInt &IntVal, const uint8_t *Src, unsigned LoadBytes) { … } APInt APIntOps::avgFloorS(const APInt &C1, const APInt &C2) { … } APInt APIntOps::avgFloorU(const APInt &C1, const APInt &C2) { … } APInt APIntOps::avgCeilS(const APInt &C1, const APInt &C2) { … } APInt APIntOps::avgCeilU(const APInt &C1, const APInt &C2) { … } APInt APIntOps::mulhs(const APInt &C1, const APInt &C2) { … } APInt APIntOps::mulhu(const APInt &C1, const APInt &C2) { … }
Codebase Browser
llvm