3210 lines · cpp
1//===-- APInt.cpp - Implement APInt class ---------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements a class to represent arbitrary precision integer10// constant values and provide a variety of arithmetic operations on them.11//12//===----------------------------------------------------------------------===//13 14#include "llvm/ADT/APInt.h"15#include "llvm/ADT/ArrayRef.h"16#include "llvm/ADT/FoldingSet.h"17#include "llvm/ADT/Hashing.h"18#include "llvm/ADT/Sequence.h"19#include "llvm/ADT/SmallString.h"20#include "llvm/ADT/StringRef.h"21#include "llvm/ADT/bit.h"22#include "llvm/Support/Alignment.h"23#include "llvm/Support/Debug.h"24#include "llvm/Support/ErrorHandling.h"25#include "llvm/Support/MathExtras.h"26#include "llvm/Support/raw_ostream.h"27#include <cmath>28#include <optional>29 30using namespace llvm;31 32#define DEBUG_TYPE "apint"33 34/// A utility function for allocating memory, checking for allocation failures,35/// and ensuring the contents are zeroed.36inline static uint64_t* getClearedMemory(unsigned numWords) {37 return new uint64_t[numWords]();38}39 40/// A utility function for allocating memory and checking for allocation41/// failure. The content is not zeroed.42inline static uint64_t* getMemory(unsigned numWords) {43 return new uint64_t[numWords];44}45 46/// A utility function that converts a character to a digit.47inline static unsigned getDigit(char cdigit, uint8_t radix) {48 unsigned r;49 50 if (radix == 16 || radix == 36) {51 r = cdigit - '0';52 if (r <= 9)53 return r;54 55 r = cdigit - 'A';56 if (r <= radix - 11U)57 return r + 10;58 59 r = cdigit - 'a';60 if (r <= radix - 11U)61 return r + 10;62 63 radix = 10;64 }65 66 r = cdigit - '0';67 if (r < radix)68 return r;69 70 return UINT_MAX;71}72 73 74void APInt::initSlowCase(uint64_t val, bool isSigned) {75 if (isSigned && int64_t(val) < 0) {76 U.pVal = getMemory(getNumWords());77 U.pVal[0] = val;78 memset(&U.pVal[1], 0xFF, APINT_WORD_SIZE * (getNumWords() - 1));79 clearUnusedBits();80 } else {81 U.pVal = getClearedMemory(getNumWords());82 U.pVal[0] = val;83 }84}85 86void APInt::initSlowCase(const APInt& that) {87 U.pVal = getMemory(getNumWords());88 memcpy(U.pVal, that.U.pVal, getNumWords() * APINT_WORD_SIZE);89}90 91void APInt::initFromArray(ArrayRef<uint64_t> bigVal) {92 assert(bigVal.data() && "Null pointer detected!");93 if (isSingleWord())94 U.VAL = bigVal[0];95 else {96 // Get memory, cleared to 097 U.pVal = getClearedMemory(getNumWords());98 // Calculate the number of words to copy99 unsigned words = std::min<unsigned>(bigVal.size(), getNumWords());100 // Copy the words from bigVal to pVal101 memcpy(U.pVal, bigVal.data(), words * APINT_WORD_SIZE);102 }103 // Make sure unused high bits are cleared104 clearUnusedBits();105}106 107APInt::APInt(unsigned numBits, ArrayRef<uint64_t> bigVal) : BitWidth(numBits) {108 initFromArray(bigVal);109}110 111APInt::APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[])112 : BitWidth(numBits) {113 initFromArray(ArrayRef(bigVal, numWords));114}115 116APInt::APInt(unsigned numbits, StringRef Str, uint8_t radix)117 : BitWidth(numbits) {118 fromString(numbits, Str, radix);119}120 121void APInt::reallocate(unsigned NewBitWidth) {122 // If the number of words is the same we can just change the width and stop.123 if (getNumWords() == getNumWords(NewBitWidth)) {124 BitWidth = NewBitWidth;125 return;126 }127 128 // If we have an allocation, delete it.129 if (!isSingleWord())130 delete [] U.pVal;131 132 // Update BitWidth.133 BitWidth = NewBitWidth;134 135 // If we are supposed to have an allocation, create it.136 if (!isSingleWord())137 U.pVal = getMemory(getNumWords());138}139 140void APInt::assignSlowCase(const APInt &RHS) {141 // Don't do anything for X = X142 if (this == &RHS)143 return;144 145 // Adjust the bit width and handle allocations as necessary.146 reallocate(RHS.getBitWidth());147 148 // Copy the data.149 if (isSingleWord())150 U.VAL = RHS.U.VAL;151 else152 memcpy(U.pVal, RHS.U.pVal, getNumWords() * APINT_WORD_SIZE);153}154 155/// This method 'profiles' an APInt for use with FoldingSet.156void APInt::Profile(FoldingSetNodeID& ID) const {157 ID.AddInteger(BitWidth);158 159 if (isSingleWord()) {160 ID.AddInteger(U.VAL);161 return;162 }163 164 unsigned NumWords = getNumWords();165 for (unsigned i = 0; i < NumWords; ++i)166 ID.AddInteger(U.pVal[i]);167}168 169bool APInt::isAligned(Align A) const {170 if (isZero())171 return true;172 const unsigned TrailingZeroes = countr_zero();173 const unsigned MinimumTrailingZeroes = Log2(A);174 return TrailingZeroes >= MinimumTrailingZeroes;175}176 177/// Prefix increment operator. Increments the APInt by one.178APInt& APInt::operator++() {179 if (isSingleWord())180 ++U.VAL;181 else182 tcIncrement(U.pVal, getNumWords());183 return clearUnusedBits();184}185 186/// Prefix decrement operator. Decrements the APInt by one.187APInt& APInt::operator--() {188 if (isSingleWord())189 --U.VAL;190 else191 tcDecrement(U.pVal, getNumWords());192 return clearUnusedBits();193}194 195/// Adds the RHS APInt to this APInt.196/// @returns this, after addition of RHS.197/// Addition assignment operator.198APInt& APInt::operator+=(const APInt& RHS) {199 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");200 if (isSingleWord())201 U.VAL += RHS.U.VAL;202 else203 tcAdd(U.pVal, RHS.U.pVal, 0, getNumWords());204 return clearUnusedBits();205}206 207APInt& APInt::operator+=(uint64_t RHS) {208 if (isSingleWord())209 U.VAL += RHS;210 else211 tcAddPart(U.pVal, RHS, getNumWords());212 return clearUnusedBits();213}214 215/// Subtracts the RHS APInt from this APInt216/// @returns this, after subtraction217/// Subtraction assignment operator.218APInt& APInt::operator-=(const APInt& RHS) {219 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");220 if (isSingleWord())221 U.VAL -= RHS.U.VAL;222 else223 tcSubtract(U.pVal, RHS.U.pVal, 0, getNumWords());224 return clearUnusedBits();225}226 227APInt& APInt::operator-=(uint64_t RHS) {228 if (isSingleWord())229 U.VAL -= RHS;230 else231 tcSubtractPart(U.pVal, RHS, getNumWords());232 return clearUnusedBits();233}234 235APInt APInt::operator*(const APInt& RHS) const {236 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");237 if (isSingleWord())238 return APInt(BitWidth, U.VAL * RHS.U.VAL, /*isSigned=*/false,239 /*implicitTrunc=*/true);240 241 APInt Result(getMemory(getNumWords()), getBitWidth());242 tcMultiply(Result.U.pVal, U.pVal, RHS.U.pVal, getNumWords());243 Result.clearUnusedBits();244 return Result;245}246 247void APInt::andAssignSlowCase(const APInt &RHS) {248 WordType *dst = U.pVal, *rhs = RHS.U.pVal;249 for (size_t i = 0, e = getNumWords(); i != e; ++i)250 dst[i] &= rhs[i];251}252 253void APInt::orAssignSlowCase(const APInt &RHS) {254 WordType *dst = U.pVal, *rhs = RHS.U.pVal;255 for (size_t i = 0, e = getNumWords(); i != e; ++i)256 dst[i] |= rhs[i];257}258 259void APInt::xorAssignSlowCase(const APInt &RHS) {260 WordType *dst = U.pVal, *rhs = RHS.U.pVal;261 for (size_t i = 0, e = getNumWords(); i != e; ++i)262 dst[i] ^= rhs[i];263}264 265APInt &APInt::operator*=(const APInt &RHS) {266 *this = *this * RHS;267 return *this;268}269 270APInt& APInt::operator*=(uint64_t RHS) {271 if (isSingleWord()) {272 U.VAL *= RHS;273 } else {274 unsigned NumWords = getNumWords();275 tcMultiplyPart(U.pVal, U.pVal, RHS, 0, NumWords, NumWords, false);276 }277 return clearUnusedBits();278}279 280bool APInt::equalSlowCase(const APInt &RHS) const {281 return std::equal(U.pVal, U.pVal + getNumWords(), RHS.U.pVal);282}283 284int APInt::compare(const APInt& RHS) const {285 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");286 if (isSingleWord())287 return U.VAL < RHS.U.VAL ? -1 : U.VAL > RHS.U.VAL;288 289 return tcCompare(U.pVal, RHS.U.pVal, getNumWords());290}291 292int APInt::compareSigned(const APInt& RHS) const {293 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");294 if (isSingleWord()) {295 int64_t lhsSext = SignExtend64(U.VAL, BitWidth);296 int64_t rhsSext = SignExtend64(RHS.U.VAL, BitWidth);297 return lhsSext < rhsSext ? -1 : lhsSext > rhsSext;298 }299 300 bool lhsNeg = isNegative();301 bool rhsNeg = RHS.isNegative();302 303 // If the sign bits don't match, then (LHS < RHS) if LHS is negative304 if (lhsNeg != rhsNeg)305 return lhsNeg ? -1 : 1;306 307 // Otherwise we can just use an unsigned comparison, because even negative308 // numbers compare correctly this way if both have the same signed-ness.309 return tcCompare(U.pVal, RHS.U.pVal, getNumWords());310}311 312void APInt::setBitsSlowCase(unsigned loBit, unsigned hiBit) {313 unsigned loWord = whichWord(loBit);314 unsigned hiWord = whichWord(hiBit);315 316 // Create an initial mask for the low word with zeros below loBit.317 uint64_t loMask = WORDTYPE_MAX << whichBit(loBit);318 319 // If hiBit is not aligned, we need a high mask.320 unsigned hiShiftAmt = whichBit(hiBit);321 if (hiShiftAmt != 0) {322 // Create a high mask with zeros above hiBit.323 uint64_t hiMask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - hiShiftAmt);324 // If loWord and hiWord are equal, then we combine the masks. Otherwise,325 // set the bits in hiWord.326 if (hiWord == loWord)327 loMask &= hiMask;328 else329 U.pVal[hiWord] |= hiMask;330 }331 // Apply the mask to the low word.332 U.pVal[loWord] |= loMask;333 334 // Fill any words between loWord and hiWord with all ones.335 for (unsigned word = loWord + 1; word < hiWord; ++word)336 U.pVal[word] = WORDTYPE_MAX;337}338 339void APInt::clearBitsSlowCase(unsigned LoBit, unsigned HiBit) {340 unsigned LoWord = whichWord(LoBit);341 unsigned HiWord = whichWord(HiBit);342 343 // Create an initial mask for the low word with ones below loBit.344 uint64_t LoMask = ~(WORDTYPE_MAX << whichBit(LoBit));345 346 // If HiBit is not aligned, we need a high mask.347 unsigned HiShiftAmt = whichBit(HiBit);348 if (HiShiftAmt != 0) {349 // Create a high mask with ones above HiBit.350 uint64_t HiMask = ~(WORDTYPE_MAX >> (APINT_BITS_PER_WORD - HiShiftAmt));351 // If LoWord and HiWord are equal, then we combine the masks. Otherwise,352 // clear the bits in HiWord.353 if (HiWord == LoWord)354 LoMask |= HiMask;355 else356 U.pVal[HiWord] &= HiMask;357 }358 // Apply the mask to the low word.359 U.pVal[LoWord] &= LoMask;360 361 // Fill any words between LoWord and HiWord with all zeros.362 for (unsigned Word = LoWord + 1; Word < HiWord; ++Word)363 U.pVal[Word] = 0;364}365 366// Complement a bignum in-place.367static void tcComplement(APInt::WordType *dst, unsigned parts) {368 for (unsigned i = 0; i < parts; i++)369 dst[i] = ~dst[i];370}371 372/// Toggle every bit to its opposite value.373void APInt::flipAllBitsSlowCase() {374 tcComplement(U.pVal, getNumWords());375 clearUnusedBits();376}377 378/// Concatenate the bits from "NewLSB" onto the bottom of *this. This is379/// equivalent to:380/// (this->zext(NewWidth) << NewLSB.getBitWidth()) | NewLSB.zext(NewWidth)381/// In the slow case, we know the result is large.382APInt APInt::concatSlowCase(const APInt &NewLSB) const {383 unsigned NewWidth = getBitWidth() + NewLSB.getBitWidth();384 APInt Result = NewLSB.zext(NewWidth);385 Result.insertBits(*this, NewLSB.getBitWidth());386 return Result;387}388 389/// Toggle a given bit to its opposite value whose position is given390/// as "bitPosition".391/// Toggles a given bit to its opposite value.392void APInt::flipBit(unsigned bitPosition) {393 assert(bitPosition < BitWidth && "Out of the bit-width range!");394 setBitVal(bitPosition, !(*this)[bitPosition]);395}396 397void APInt::insertBits(const APInt &subBits, unsigned bitPosition) {398 unsigned subBitWidth = subBits.getBitWidth();399 assert((subBitWidth + bitPosition) <= BitWidth && "Illegal bit insertion");400 401 // inserting no bits is a noop.402 if (subBitWidth == 0)403 return;404 405 // Insertion is a direct copy.406 if (subBitWidth == BitWidth) {407 *this = subBits;408 return;409 }410 411 // Single word result can be done as a direct bitmask.412 if (isSingleWord()) {413 uint64_t mask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - subBitWidth);414 U.VAL &= ~(mask << bitPosition);415 U.VAL |= (subBits.U.VAL << bitPosition);416 return;417 }418 419 unsigned loBit = whichBit(bitPosition);420 unsigned loWord = whichWord(bitPosition);421 unsigned hi1Word = whichWord(bitPosition + subBitWidth - 1);422 423 // Insertion within a single word can be done as a direct bitmask.424 if (loWord == hi1Word) {425 uint64_t mask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - subBitWidth);426 U.pVal[loWord] &= ~(mask << loBit);427 U.pVal[loWord] |= (subBits.U.VAL << loBit);428 return;429 }430 431 // Insert on word boundaries.432 if (loBit == 0) {433 // Direct copy whole words.434 unsigned numWholeSubWords = subBitWidth / APINT_BITS_PER_WORD;435 memcpy(U.pVal + loWord, subBits.getRawData(),436 numWholeSubWords * APINT_WORD_SIZE);437 438 // Mask+insert remaining bits.439 unsigned remainingBits = subBitWidth % APINT_BITS_PER_WORD;440 if (remainingBits != 0) {441 uint64_t mask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - remainingBits);442 U.pVal[hi1Word] &= ~mask;443 U.pVal[hi1Word] |= subBits.getWord(subBitWidth - 1);444 }445 return;446 }447 448 // General case - set/clear individual bits in dst based on src.449 // TODO - there is scope for optimization here, but at the moment this code450 // path is barely used so prefer readability over performance.451 for (unsigned i = 0; i != subBitWidth; ++i)452 setBitVal(bitPosition + i, subBits[i]);453}454 455void APInt::insertBits(uint64_t subBits, unsigned bitPosition, unsigned numBits) {456 uint64_t maskBits = maskTrailingOnes<uint64_t>(numBits);457 subBits &= maskBits;458 if (isSingleWord()) {459 U.VAL &= ~(maskBits << bitPosition);460 U.VAL |= subBits << bitPosition;461 return;462 }463 464 unsigned loBit = whichBit(bitPosition);465 unsigned loWord = whichWord(bitPosition);466 unsigned hiWord = whichWord(bitPosition + numBits - 1);467 if (loWord == hiWord) {468 U.pVal[loWord] &= ~(maskBits << loBit);469 U.pVal[loWord] |= subBits << loBit;470 return;471 }472 473 static_assert(8 * sizeof(WordType) <= 64, "This code assumes only two words affected");474 unsigned wordBits = 8 * sizeof(WordType);475 U.pVal[loWord] &= ~(maskBits << loBit);476 U.pVal[loWord] |= subBits << loBit;477 478 U.pVal[hiWord] &= ~(maskBits >> (wordBits - loBit));479 U.pVal[hiWord] |= subBits >> (wordBits - loBit);480}481 482APInt APInt::extractBits(unsigned numBits, unsigned bitPosition) const {483 assert(bitPosition < BitWidth && (numBits + bitPosition) <= BitWidth &&484 "Illegal bit extraction");485 486 if (isSingleWord())487 return APInt(numBits, U.VAL >> bitPosition, /*isSigned=*/false,488 /*implicitTrunc=*/true);489 490 unsigned loBit = whichBit(bitPosition);491 unsigned loWord = whichWord(bitPosition);492 unsigned hiWord = whichWord(bitPosition + numBits - 1);493 494 // Single word result extracting bits from a single word source.495 if (loWord == hiWord)496 return APInt(numBits, U.pVal[loWord] >> loBit, /*isSigned=*/false,497 /*implicitTrunc=*/true);498 499 // Extracting bits that start on a source word boundary can be done500 // as a fast memory copy.501 if (loBit == 0)502 return APInt(numBits, ArrayRef(U.pVal + loWord, 1 + hiWord - loWord));503 504 // General case - shift + copy source words directly into place.505 APInt Result(numBits, 0);506 unsigned NumSrcWords = getNumWords();507 unsigned NumDstWords = Result.getNumWords();508 509 uint64_t *DestPtr = Result.isSingleWord() ? &Result.U.VAL : Result.U.pVal;510 for (unsigned word = 0; word < NumDstWords; ++word) {511 uint64_t w0 = U.pVal[loWord + word];512 uint64_t w1 =513 (loWord + word + 1) < NumSrcWords ? U.pVal[loWord + word + 1] : 0;514 DestPtr[word] = (w0 >> loBit) | (w1 << (APINT_BITS_PER_WORD - loBit));515 }516 517 return Result.clearUnusedBits();518}519 520uint64_t APInt::extractBitsAsZExtValue(unsigned numBits,521 unsigned bitPosition) const {522 assert(bitPosition < BitWidth && (numBits + bitPosition) <= BitWidth &&523 "Illegal bit extraction");524 assert(numBits <= 64 && "Illegal bit extraction");525 526 uint64_t maskBits = maskTrailingOnes<uint64_t>(numBits);527 if (isSingleWord())528 return (U.VAL >> bitPosition) & maskBits;529 530 static_assert(APINT_BITS_PER_WORD >= 64,531 "This code assumes only two words affected");532 unsigned loBit = whichBit(bitPosition);533 unsigned loWord = whichWord(bitPosition);534 unsigned hiWord = whichWord(bitPosition + numBits - 1);535 if (loWord == hiWord)536 return (U.pVal[loWord] >> loBit) & maskBits;537 538 uint64_t retBits = U.pVal[loWord] >> loBit;539 retBits |= U.pVal[hiWord] << (APINT_BITS_PER_WORD - loBit);540 retBits &= maskBits;541 return retBits;542}543 544unsigned APInt::getSufficientBitsNeeded(StringRef Str, uint8_t Radix) {545 assert(!Str.empty() && "Invalid string length");546 size_t StrLen = Str.size();547 548 // Each computation below needs to know if it's negative.549 unsigned IsNegative = false;550 if (Str[0] == '-' || Str[0] == '+') {551 IsNegative = Str[0] == '-';552 StrLen--;553 assert(StrLen && "String is only a sign, needs a value.");554 }555 556 // For radixes of power-of-two values, the bits required is accurately and557 // easily computed.558 if (Radix == 2)559 return StrLen + IsNegative;560 if (Radix == 8)561 return StrLen * 3 + IsNegative;562 if (Radix == 16)563 return StrLen * 4 + IsNegative;564 565 // Compute a sufficient number of bits that is always large enough but might566 // be too large. This avoids the assertion in the constructor. This567 // calculation doesn't work appropriately for the numbers 0-9, so just use 4568 // bits in that case.569 if (Radix == 10)570 return (StrLen == 1 ? 4 : StrLen * 64 / 18) + IsNegative;571 572 assert(Radix == 36);573 return (StrLen == 1 ? 7 : StrLen * 16 / 3) + IsNegative;574}575 576unsigned APInt::getBitsNeeded(StringRef str, uint8_t radix) {577 // Compute a sufficient number of bits that is always large enough but might578 // be too large.579 unsigned sufficient = getSufficientBitsNeeded(str, radix);580 581 // For bases 2, 8, and 16, the sufficient number of bits is exact and we can582 // return the value directly. For bases 10 and 36, we need to do extra work.583 if (radix == 2 || radix == 8 || radix == 16)584 return sufficient;585 586 // This is grossly inefficient but accurate. We could probably do something587 // with a computation of roughly slen*64/20 and then adjust by the value of588 // the first few digits. But, I'm not sure how accurate that could be.589 size_t slen = str.size();590 591 // Each computation below needs to know if it's negative.592 StringRef::iterator p = str.begin();593 unsigned isNegative = *p == '-';594 if (*p == '-' || *p == '+') {595 p++;596 slen--;597 assert(slen && "String is only a sign, needs a value.");598 }599 600 601 // Convert to the actual binary value.602 APInt tmp(sufficient, StringRef(p, slen), radix);603 604 // Compute how many bits are required. If the log is infinite, assume we need605 // just bit. If the log is exact and value is negative, then the value is606 // MinSignedValue with (log + 1) bits.607 unsigned log = tmp.logBase2();608 if (log == (unsigned)-1) {609 return isNegative + 1;610 } else if (isNegative && tmp.isPowerOf2()) {611 return isNegative + log;612 } else {613 return isNegative + log + 1;614 }615}616 617hash_code llvm::hash_value(const APInt &Arg) {618 if (Arg.isSingleWord())619 return hash_combine(Arg.BitWidth, Arg.U.VAL);620 621 return hash_combine(622 Arg.BitWidth,623 hash_combine_range(Arg.U.pVal, Arg.U.pVal + Arg.getNumWords()));624}625 626unsigned DenseMapInfo<APInt, void>::getHashValue(const APInt &Key) {627 return static_cast<unsigned>(hash_value(Key));628}629 630bool APInt::isSplat(unsigned SplatSizeInBits) const {631 assert(getBitWidth() % SplatSizeInBits == 0 &&632 "SplatSizeInBits must divide width!");633 // We can check that all parts of an integer are equal by making use of a634 // little trick: rotate and check if it's still the same value.635 return *this == rotl(SplatSizeInBits);636}637 638/// This function returns the high "numBits" bits of this APInt.639APInt APInt::getHiBits(unsigned numBits) const {640 return this->lshr(BitWidth - numBits);641}642 643/// This function returns the low "numBits" bits of this APInt.644APInt APInt::getLoBits(unsigned numBits) const {645 APInt Result(getLowBitsSet(BitWidth, numBits));646 Result &= *this;647 return Result;648}649 650/// Return a value containing V broadcasted over NewLen bits.651APInt APInt::getSplat(unsigned NewLen, const APInt &V) {652 assert(NewLen >= V.getBitWidth() && "Can't splat to smaller bit width!");653 654 APInt Val = V.zext(NewLen);655 for (unsigned I = V.getBitWidth(); I < NewLen; I <<= 1)656 Val |= Val << I;657 658 return Val;659}660 661unsigned APInt::countLeadingZerosSlowCase() const {662 unsigned Count = 0;663 for (int i = getNumWords()-1; i >= 0; --i) {664 uint64_t V = U.pVal[i];665 if (V == 0)666 Count += APINT_BITS_PER_WORD;667 else {668 Count += llvm::countl_zero(V);669 break;670 }671 }672 // Adjust for unused bits in the most significant word (they are zero).673 unsigned Mod = BitWidth % APINT_BITS_PER_WORD;674 Count -= Mod > 0 ? APINT_BITS_PER_WORD - Mod : 0;675 return Count;676}677 678unsigned APInt::countLeadingOnesSlowCase() const {679 unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD;680 unsigned shift;681 if (!highWordBits) {682 highWordBits = APINT_BITS_PER_WORD;683 shift = 0;684 } else {685 shift = APINT_BITS_PER_WORD - highWordBits;686 }687 int i = getNumWords() - 1;688 unsigned Count = llvm::countl_one(U.pVal[i] << shift);689 if (Count == highWordBits) {690 for (i--; i >= 0; --i) {691 if (U.pVal[i] == WORDTYPE_MAX)692 Count += APINT_BITS_PER_WORD;693 else {694 Count += llvm::countl_one(U.pVal[i]);695 break;696 }697 }698 }699 return Count;700}701 702unsigned APInt::countTrailingZerosSlowCase() const {703 unsigned Count = 0;704 unsigned i = 0;705 for (; i < getNumWords() && U.pVal[i] == 0; ++i)706 Count += APINT_BITS_PER_WORD;707 if (i < getNumWords())708 Count += llvm::countr_zero(U.pVal[i]);709 return std::min(Count, BitWidth);710}711 712unsigned APInt::countTrailingOnesSlowCase() const {713 unsigned Count = 0;714 unsigned i = 0;715 for (; i < getNumWords() && U.pVal[i] == WORDTYPE_MAX; ++i)716 Count += APINT_BITS_PER_WORD;717 if (i < getNumWords())718 Count += llvm::countr_one(U.pVal[i]);719 assert(Count <= BitWidth);720 return Count;721}722 723unsigned APInt::countPopulationSlowCase() const {724 unsigned Count = 0;725 for (unsigned i = 0; i < getNumWords(); ++i)726 Count += llvm::popcount(U.pVal[i]);727 return Count;728}729 730bool APInt::intersectsSlowCase(const APInt &RHS) const {731 for (unsigned i = 0, e = getNumWords(); i != e; ++i)732 if ((U.pVal[i] & RHS.U.pVal[i]) != 0)733 return true;734 735 return false;736}737 738bool APInt::isSubsetOfSlowCase(const APInt &RHS) const {739 for (unsigned i = 0, e = getNumWords(); i != e; ++i)740 if ((U.pVal[i] & ~RHS.U.pVal[i]) != 0)741 return false;742 743 return true;744}745 746APInt APInt::byteSwap() const {747 assert(BitWidth >= 16 && BitWidth % 8 == 0 && "Cannot byteswap!");748 if (BitWidth == 16)749 return APInt(BitWidth, llvm::byteswap<uint16_t>(U.VAL));750 if (BitWidth == 32)751 return APInt(BitWidth, llvm::byteswap<uint32_t>(U.VAL));752 if (BitWidth <= 64) {753 uint64_t Tmp1 = llvm::byteswap<uint64_t>(U.VAL);754 Tmp1 >>= (64 - BitWidth);755 return APInt(BitWidth, Tmp1);756 }757 758 APInt Result(getNumWords() * APINT_BITS_PER_WORD, 0);759 for (unsigned I = 0, N = getNumWords(); I != N; ++I)760 Result.U.pVal[I] = llvm::byteswap<uint64_t>(U.pVal[N - I - 1]);761 if (Result.BitWidth != BitWidth) {762 Result.lshrInPlace(Result.BitWidth - BitWidth);763 Result.BitWidth = BitWidth;764 }765 return Result;766}767 768APInt APInt::reverseBits() const {769 switch (BitWidth) {770 case 64:771 return APInt(BitWidth, llvm::reverseBits<uint64_t>(U.VAL));772 case 32:773 return APInt(BitWidth, llvm::reverseBits<uint32_t>(U.VAL));774 case 16:775 return APInt(BitWidth, llvm::reverseBits<uint16_t>(U.VAL));776 case 8:777 return APInt(BitWidth, llvm::reverseBits<uint8_t>(U.VAL));778 case 0:779 return *this;780 default:781 break;782 }783 784 APInt Val(*this);785 APInt Reversed(BitWidth, 0);786 unsigned S = BitWidth;787 788 for (; Val != 0; Val.lshrInPlace(1)) {789 Reversed <<= 1;790 Reversed |= Val[0];791 --S;792 }793 794 Reversed <<= S;795 return Reversed;796}797 798APInt llvm::APIntOps::GreatestCommonDivisor(APInt A, APInt B) {799 // Fast-path a common case.800 if (A == B) return A;801 802 // Corner cases: if either operand is zero, the other is the gcd.803 if (!A) return B;804 if (!B) return A;805 806 // Count common powers of 2 and remove all other powers of 2.807 unsigned Pow2;808 {809 unsigned Pow2_A = A.countr_zero();810 unsigned Pow2_B = B.countr_zero();811 if (Pow2_A > Pow2_B) {812 A.lshrInPlace(Pow2_A - Pow2_B);813 Pow2 = Pow2_B;814 } else if (Pow2_B > Pow2_A) {815 B.lshrInPlace(Pow2_B - Pow2_A);816 Pow2 = Pow2_A;817 } else {818 Pow2 = Pow2_A;819 }820 }821 822 // Both operands are odd multiples of 2^Pow_2:823 //824 // gcd(a, b) = gcd(|a - b| / 2^i, min(a, b))825 //826 // This is a modified version of Stein's algorithm, taking advantage of827 // efficient countTrailingZeros().828 while (A != B) {829 if (A.ugt(B)) {830 A -= B;831 A.lshrInPlace(A.countr_zero() - Pow2);832 } else {833 B -= A;834 B.lshrInPlace(B.countr_zero() - Pow2);835 }836 }837 838 return A;839}840 841APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) {842 uint64_t I = bit_cast<uint64_t>(Double);843 844 // Get the sign bit from the highest order bit845 bool isNeg = I >> 63;846 847 // Get the 11-bit exponent and adjust for the 1023 bit bias848 int64_t exp = ((I >> 52) & 0x7ff) - 1023;849 850 // If the exponent is negative, the value is < 0 so just return 0.851 if (exp < 0)852 return APInt(width, 0u);853 854 // Extract the mantissa by clearing the top 12 bits (sign + exponent).855 uint64_t mantissa = (I & (~0ULL >> 12)) | 1ULL << 52;856 857 // If the exponent doesn't shift all bits out of the mantissa858 if (exp < 52)859 return isNeg ? -APInt(width, mantissa >> (52 - exp)) :860 APInt(width, mantissa >> (52 - exp));861 862 // If the client didn't provide enough bits for us to shift the mantissa into863 // then the result is undefined, just return 0864 if (width <= exp - 52)865 return APInt(width, 0);866 867 // Otherwise, we have to shift the mantissa bits up to the right location868 APInt Tmp(width, mantissa);869 Tmp <<= (unsigned)exp - 52;870 return isNeg ? -Tmp : Tmp;871}872 873/// This function converts this APInt to a double.874/// The layout for double is as following (IEEE Standard 754):875/// --------------------------------------876/// | Sign Exponent Fraction Bias |877/// |-------------------------------------- |878/// | 1[63] 11[62-52] 52[51-00] 1023 |879/// --------------------------------------880double APInt::roundToDouble(bool isSigned) const {881 // Handle the simple case where the value is contained in one uint64_t.882 // It is wrong to optimize getWord(0) to VAL; there might be more than one word.883 if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {884 if (isSigned) {885 int64_t sext = SignExtend64(getWord(0), BitWidth);886 return double(sext);887 }888 return double(getWord(0));889 }890 891 // Determine if the value is negative.892 bool isNeg = isSigned ? (*this)[BitWidth-1] : false;893 894 // Construct the absolute value if we're negative.895 APInt Tmp(isNeg ? -(*this) : (*this));896 897 // Figure out how many bits we're using.898 unsigned n = Tmp.getActiveBits();899 900 // The exponent (without bias normalization) is just the number of bits901 // we are using. Note that the sign bit is gone since we constructed the902 // absolute value.903 uint64_t exp = n;904 905 // Return infinity for exponent overflow906 if (exp > 1023) {907 if (!isSigned || !isNeg)908 return std::numeric_limits<double>::infinity();909 else910 return -std::numeric_limits<double>::infinity();911 }912 exp += 1023; // Increment for 1023 bias913 914 // Number of bits in mantissa is 52. To obtain the mantissa value, we must915 // extract the high 52 bits from the correct words in pVal.916 uint64_t mantissa;917 unsigned hiWord = whichWord(n-1);918 if (hiWord == 0) {919 mantissa = Tmp.U.pVal[0];920 if (n > 52)921 mantissa >>= n - 52; // shift down, we want the top 52 bits.922 } else {923 assert(hiWord > 0 && "huh?");924 uint64_t hibits = Tmp.U.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);925 uint64_t lobits = Tmp.U.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);926 mantissa = hibits | lobits;927 }928 929 // The leading bit of mantissa is implicit, so get rid of it.930 uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;931 uint64_t I = sign | (exp << 52) | mantissa;932 return bit_cast<double>(I);933}934 935// Truncate to new width.936APInt APInt::trunc(unsigned width) const {937 assert(width <= BitWidth && "Invalid APInt Truncate request");938 939 if (width <= APINT_BITS_PER_WORD)940 return APInt(width, getRawData()[0], /*isSigned=*/false,941 /*implicitTrunc=*/true);942 943 if (width == BitWidth)944 return *this;945 946 APInt Result(getMemory(getNumWords(width)), width);947 948 // Copy full words.949 unsigned i;950 for (i = 0; i != width / APINT_BITS_PER_WORD; i++)951 Result.U.pVal[i] = U.pVal[i];952 953 // Truncate and copy any partial word.954 unsigned bits = (0 - width) % APINT_BITS_PER_WORD;955 if (bits != 0)956 Result.U.pVal[i] = U.pVal[i] << bits >> bits;957 958 return Result;959}960 961// Truncate to new width with unsigned saturation.962APInt APInt::truncUSat(unsigned width) const {963 assert(width <= BitWidth && "Invalid APInt Truncate request");964 965 // Can we just losslessly truncate it?966 if (isIntN(width))967 return trunc(width);968 // If not, then just return the new limit.969 return APInt::getMaxValue(width);970}971 972// Truncate to new width with signed saturation.973APInt APInt::truncSSat(unsigned width) const {974 assert(width <= BitWidth && "Invalid APInt Truncate request");975 976 // Can we just losslessly truncate it?977 if (isSignedIntN(width))978 return trunc(width);979 // If not, then just return the new limits.980 return isNegative() ? APInt::getSignedMinValue(width)981 : APInt::getSignedMaxValue(width);982}983 984// Sign extend to a new width.985APInt APInt::sext(unsigned Width) const {986 assert(Width >= BitWidth && "Invalid APInt SignExtend request");987 988 if (Width <= APINT_BITS_PER_WORD)989 return APInt(Width, SignExtend64(U.VAL, BitWidth), /*isSigned=*/true);990 991 if (Width == BitWidth)992 return *this;993 994 APInt Result(getMemory(getNumWords(Width)), Width);995 996 // Copy words.997 std::memcpy(Result.U.pVal, getRawData(), getNumWords() * APINT_WORD_SIZE);998 999 // Sign extend the last word since there may be unused bits in the input.1000 Result.U.pVal[getNumWords() - 1] =1001 SignExtend64(Result.U.pVal[getNumWords() - 1],1002 ((BitWidth - 1) % APINT_BITS_PER_WORD) + 1);1003 1004 // Fill with sign bits.1005 std::memset(Result.U.pVal + getNumWords(), isNegative() ? -1 : 0,1006 (Result.getNumWords() - getNumWords()) * APINT_WORD_SIZE);1007 Result.clearUnusedBits();1008 return Result;1009}1010 1011// Zero extend to a new width.1012APInt APInt::zext(unsigned width) const {1013 assert(width >= BitWidth && "Invalid APInt ZeroExtend request");1014 1015 if (width <= APINT_BITS_PER_WORD)1016 return APInt(width, U.VAL);1017 1018 if (width == BitWidth)1019 return *this;1020 1021 APInt Result(getMemory(getNumWords(width)), width);1022 1023 // Copy words.1024 std::memcpy(Result.U.pVal, getRawData(), getNumWords() * APINT_WORD_SIZE);1025 1026 // Zero remaining words.1027 std::memset(Result.U.pVal + getNumWords(), 0,1028 (Result.getNumWords() - getNumWords()) * APINT_WORD_SIZE);1029 1030 return Result;1031}1032 1033APInt APInt::zextOrTrunc(unsigned width) const {1034 if (BitWidth < width)1035 return zext(width);1036 if (BitWidth > width)1037 return trunc(width);1038 return *this;1039}1040 1041APInt APInt::sextOrTrunc(unsigned width) const {1042 if (BitWidth < width)1043 return sext(width);1044 if (BitWidth > width)1045 return trunc(width);1046 return *this;1047}1048 1049/// Arithmetic right-shift this APInt by shiftAmt.1050/// Arithmetic right-shift function.1051void APInt::ashrInPlace(const APInt &shiftAmt) {1052 ashrInPlace((unsigned)shiftAmt.getLimitedValue(BitWidth));1053}1054 1055/// Arithmetic right-shift this APInt by shiftAmt.1056/// Arithmetic right-shift function.1057void APInt::ashrSlowCase(unsigned ShiftAmt) {1058 // Don't bother performing a no-op shift.1059 if (!ShiftAmt)1060 return;1061 1062 // Save the original sign bit for later.1063 bool Negative = isNegative();1064 1065 // WordShift is the inter-part shift; BitShift is intra-part shift.1066 unsigned WordShift = ShiftAmt / APINT_BITS_PER_WORD;1067 unsigned BitShift = ShiftAmt % APINT_BITS_PER_WORD;1068 1069 unsigned WordsToMove = getNumWords() - WordShift;1070 if (WordsToMove != 0) {1071 // Sign extend the last word to fill in the unused bits.1072 U.pVal[getNumWords() - 1] = SignExtend64(1073 U.pVal[getNumWords() - 1], ((BitWidth - 1) % APINT_BITS_PER_WORD) + 1);1074 1075 // Fastpath for moving by whole words.1076 if (BitShift == 0) {1077 std::memmove(U.pVal, U.pVal + WordShift, WordsToMove * APINT_WORD_SIZE);1078 } else {1079 // Move the words containing significant bits.1080 for (unsigned i = 0; i != WordsToMove - 1; ++i)1081 U.pVal[i] = (U.pVal[i + WordShift] >> BitShift) |1082 (U.pVal[i + WordShift + 1] << (APINT_BITS_PER_WORD - BitShift));1083 1084 // Handle the last word which has no high bits to copy. Use an arithmetic1085 // shift to preserve the sign bit.1086 U.pVal[WordsToMove - 1] =1087 (int64_t)U.pVal[WordShift + WordsToMove - 1] >> BitShift;1088 }1089 }1090 1091 // Fill in the remainder based on the original sign.1092 std::memset(U.pVal + WordsToMove, Negative ? -1 : 0,1093 WordShift * APINT_WORD_SIZE);1094 clearUnusedBits();1095}1096 1097/// Logical right-shift this APInt by shiftAmt.1098/// Logical right-shift function.1099void APInt::lshrInPlace(const APInt &shiftAmt) {1100 lshrInPlace((unsigned)shiftAmt.getLimitedValue(BitWidth));1101}1102 1103/// Logical right-shift this APInt by shiftAmt.1104/// Logical right-shift function.1105void APInt::lshrSlowCase(unsigned ShiftAmt) {1106 tcShiftRight(U.pVal, getNumWords(), ShiftAmt);1107}1108 1109/// Left-shift this APInt by shiftAmt.1110/// Left-shift function.1111APInt &APInt::operator<<=(const APInt &shiftAmt) {1112 // It's undefined behavior in C to shift by BitWidth or greater.1113 *this <<= (unsigned)shiftAmt.getLimitedValue(BitWidth);1114 return *this;1115}1116 1117void APInt::shlSlowCase(unsigned ShiftAmt) {1118 tcShiftLeft(U.pVal, getNumWords(), ShiftAmt);1119 clearUnusedBits();1120}1121 1122// Calculate the rotate amount modulo the bit width.1123static unsigned rotateModulo(unsigned BitWidth, const APInt &rotateAmt) {1124 if (LLVM_UNLIKELY(BitWidth == 0))1125 return 0;1126 unsigned rotBitWidth = rotateAmt.getBitWidth();1127 APInt rot = rotateAmt;1128 if (rotBitWidth < BitWidth) {1129 // Extend the rotate APInt, so that the urem doesn't divide by 0.1130 // e.g. APInt(1, 32) would give APInt(1, 0).1131 rot = rotateAmt.zext(BitWidth);1132 }1133 rot = rot.urem(APInt(rot.getBitWidth(), BitWidth));1134 return rot.getLimitedValue(BitWidth);1135}1136 1137APInt APInt::rotl(const APInt &rotateAmt) const {1138 return rotl(rotateModulo(BitWidth, rotateAmt));1139}1140 1141APInt APInt::rotl(unsigned rotateAmt) const {1142 if (LLVM_UNLIKELY(BitWidth == 0))1143 return *this;1144 rotateAmt %= BitWidth;1145 if (rotateAmt == 0)1146 return *this;1147 return shl(rotateAmt) | lshr(BitWidth - rotateAmt);1148}1149 1150APInt APInt::rotr(const APInt &rotateAmt) const {1151 return rotr(rotateModulo(BitWidth, rotateAmt));1152}1153 1154APInt APInt::rotr(unsigned rotateAmt) const {1155 if (BitWidth == 0)1156 return *this;1157 rotateAmt %= BitWidth;1158 if (rotateAmt == 0)1159 return *this;1160 return lshr(rotateAmt) | shl(BitWidth - rotateAmt);1161}1162 1163/// \returns the nearest log base 2 of this APInt. Ties round up.1164///1165/// NOTE: When we have a BitWidth of 1, we define:1166///1167/// log2(0) = UINT32_MAX1168/// log2(1) = 01169///1170/// to get around any mathematical concerns resulting from1171/// referencing 2 in a space where 2 does no exist.1172unsigned APInt::nearestLogBase2() const {1173 // Special case when we have a bitwidth of 1. If VAL is 1, then we1174 // get 0. If VAL is 0, we get WORDTYPE_MAX which gets truncated to1175 // UINT32_MAX.1176 if (BitWidth == 1)1177 return U.VAL - 1;1178 1179 // Handle the zero case.1180 if (isZero())1181 return UINT32_MAX;1182 1183 // The non-zero case is handled by computing:1184 //1185 // nearestLogBase2(x) = logBase2(x) + x[logBase2(x)-1].1186 //1187 // where x[i] is referring to the value of the ith bit of x.1188 unsigned lg = logBase2();1189 return lg + unsigned((*this)[lg - 1]);1190}1191 1192// Square Root - this method computes and returns the square root of "this".1193// Three mechanisms are used for computation. For small values (<= 5 bits),1194// a table lookup is done. This gets some performance for common cases. For1195// values using less than 52 bits, the value is converted to double and then1196// the libc sqrt function is called. The result is rounded and then converted1197// back to a uint64_t which is then used to construct the result. Finally,1198// the Babylonian method for computing square roots is used.1199APInt APInt::sqrt() const {1200 1201 // Determine the magnitude of the value.1202 unsigned magnitude = getActiveBits();1203 1204 // Use a fast table for some small values. This also gets rid of some1205 // rounding errors in libc sqrt for small values.1206 if (magnitude <= 5) {1207 static const uint8_t results[32] = {1208 /* 0 */ 0,1209 /* 1- 2 */ 1, 1,1210 /* 3- 6 */ 2, 2, 2, 2,1211 /* 7-12 */ 3, 3, 3, 3, 3, 3,1212 /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,1213 /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,1214 /* 31 */ 61215 };1216 return APInt(BitWidth, results[ (isSingleWord() ? U.VAL : U.pVal[0]) ]);1217 }1218 1219 // If the magnitude of the value fits in less than 52 bits (the precision of1220 // an IEEE double precision floating point value), then we can use the1221 // libc sqrt function which will probably use a hardware sqrt computation.1222 // This should be faster than the algorithm below.1223 if (magnitude < 52) {1224 return APInt(BitWidth,1225 uint64_t(::round(::sqrt(double(isSingleWord() ? U.VAL1226 : U.pVal[0])))));1227 }1228 1229 // Okay, all the short cuts are exhausted. We must compute it. The following1230 // is a classical Babylonian method for computing the square root. This code1231 // was adapted to APInt from a wikipedia article on such computations.1232 // See http://www.wikipedia.org/ and go to the page named1233 // Calculate_an_integer_square_root.1234 unsigned nbits = BitWidth, i = 4;1235 APInt testy(BitWidth, 16);1236 APInt x_old(BitWidth, 1);1237 APInt x_new(BitWidth, 0);1238 APInt two(BitWidth, 2);1239 1240 // Select a good starting value using binary logarithms.1241 for (;; i += 2, testy = testy.shl(2))1242 if (i >= nbits || this->ule(testy)) {1243 x_old = x_old.shl(i / 2);1244 break;1245 }1246 1247 // Use the Babylonian method to arrive at the integer square root:1248 for (;;) {1249 x_new = (this->udiv(x_old) + x_old).udiv(two);1250 if (x_old.ule(x_new))1251 break;1252 x_old = x_new;1253 }1254 1255 // Make sure we return the closest approximation1256 // NOTE: The rounding calculation below is correct. It will produce an1257 // off-by-one discrepancy with results from pari/gp. That discrepancy has been1258 // determined to be a rounding issue with pari/gp as it begins to use a1259 // floating point representation after 192 bits. There are no discrepancies1260 // between this algorithm and pari/gp for bit widths < 192 bits.1261 APInt square(x_old * x_old);1262 APInt nextSquare((x_old + 1) * (x_old +1));1263 if (this->ult(square))1264 return x_old;1265 assert(this->ule(nextSquare) && "Error in APInt::sqrt computation");1266 APInt midpoint((nextSquare - square).udiv(two));1267 APInt offset(*this - square);1268 if (offset.ult(midpoint))1269 return x_old;1270 return x_old + 1;1271}1272 1273/// \returns the multiplicative inverse of an odd APInt modulo 2^BitWidth.1274APInt APInt::multiplicativeInverse() const {1275 assert((*this)[0] &&1276 "multiplicative inverse is only defined for odd numbers!");1277 1278 // Use Newton's method.1279 APInt Factor = *this;1280 APInt T;1281 while (!(T = *this * Factor).isOne())1282 Factor *= 2 - std::move(T);1283 return Factor;1284}1285 1286/// Implementation of Knuth's Algorithm D (Division of nonnegative integers)1287/// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The1288/// variables here have the same names as in the algorithm. Comments explain1289/// the algorithm and any deviation from it.1290static void KnuthDiv(uint32_t *u, uint32_t *v, uint32_t *q, uint32_t* r,1291 unsigned m, unsigned n) {1292 assert(u && "Must provide dividend");1293 assert(v && "Must provide divisor");1294 assert(q && "Must provide quotient");1295 assert(u != v && u != q && v != q && "Must use different memory");1296 assert(n>1 && "n must be > 1");1297 1298 // b denotes the base of the number system. In our case b is 2^32.1299 const uint64_t b = uint64_t(1) << 32;1300 1301// The DEBUG macros here tend to be spam in the debug output if you're not1302// debugging this code. Disable them unless KNUTH_DEBUG is defined.1303#ifdef KNUTH_DEBUG1304#define DEBUG_KNUTH(X) LLVM_DEBUG(X)1305#else1306#define DEBUG_KNUTH(X) do {} while(false)1307#endif1308 1309 DEBUG_KNUTH(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n');1310 DEBUG_KNUTH(dbgs() << "KnuthDiv: original:");1311 DEBUG_KNUTH(for (int i = m + n; i >= 0; i--) dbgs() << " " << u[i]);1312 DEBUG_KNUTH(dbgs() << " by");1313 DEBUG_KNUTH(for (int i = n; i > 0; i--) dbgs() << " " << v[i - 1]);1314 DEBUG_KNUTH(dbgs() << '\n');1315 // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of1316 // u and v by d. Note that we have taken Knuth's advice here to use a power1317 // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of1318 // 2 allows us to shift instead of multiply and it is easy to determine the1319 // shift amount from the leading zeros. We are basically normalizing the u1320 // and v so that its high bits are shifted to the top of v's range without1321 // overflow. Note that this can require an extra word in u so that u must1322 // be of length m+n+1.1323 unsigned shift = llvm::countl_zero(v[n - 1]);1324 uint32_t v_carry = 0;1325 uint32_t u_carry = 0;1326 if (shift) {1327 for (unsigned i = 0; i < m+n; ++i) {1328 uint32_t u_tmp = u[i] >> (32 - shift);1329 u[i] = (u[i] << shift) | u_carry;1330 u_carry = u_tmp;1331 }1332 for (unsigned i = 0; i < n; ++i) {1333 uint32_t v_tmp = v[i] >> (32 - shift);1334 v[i] = (v[i] << shift) | v_carry;1335 v_carry = v_tmp;1336 }1337 }1338 u[m+n] = u_carry;1339 1340 DEBUG_KNUTH(dbgs() << "KnuthDiv: normal:");1341 DEBUG_KNUTH(for (int i = m + n; i >= 0; i--) dbgs() << " " << u[i]);1342 DEBUG_KNUTH(dbgs() << " by");1343 DEBUG_KNUTH(for (int i = n; i > 0; i--) dbgs() << " " << v[i - 1]);1344 DEBUG_KNUTH(dbgs() << '\n');1345 1346 // D2. [Initialize j.] Set j to m. This is the loop counter over the places.1347 int j = m;1348 do {1349 DEBUG_KNUTH(dbgs() << "KnuthDiv: quotient digit #" << j << '\n');1350 // D3. [Calculate q'.].1351 // Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')1352 // Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')1353 // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease1354 // qp by 1, increase rp by v[n-1], and repeat this test if rp < b. The test1355 // on v[n-2] determines at high speed most of the cases in which the trial1356 // value qp is one too large, and it eliminates all cases where qp is two1357 // too large.1358 uint64_t dividend = Make_64(u[j+n], u[j+n-1]);1359 DEBUG_KNUTH(dbgs() << "KnuthDiv: dividend == " << dividend << '\n');1360 uint64_t qp = dividend / v[n-1];1361 uint64_t rp = dividend % v[n-1];1362 if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {1363 qp--;1364 rp += v[n-1];1365 if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))1366 qp--;1367 }1368 DEBUG_KNUTH(dbgs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');1369 1370 // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with1371 // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation1372 // consists of a simple multiplication by a one-place number, combined with1373 // a subtraction.1374 // The digits (u[j+n]...u[j]) should be kept positive; if the result of1375 // this step is actually negative, (u[j+n]...u[j]) should be left as the1376 // true value plus b**(n+1), namely as the b's complement of1377 // the true value, and a "borrow" to the left should be remembered.1378 int64_t borrow = 0;1379 for (unsigned i = 0; i < n; ++i) {1380 uint64_t p = qp * uint64_t(v[i]);1381 int64_t subres = int64_t(u[j+i]) - borrow - Lo_32(p);1382 u[j+i] = Lo_32(subres);1383 borrow = Hi_32(p) - Hi_32(subres);1384 DEBUG_KNUTH(dbgs() << "KnuthDiv: u[j+i] = " << u[j + i]1385 << ", borrow = " << borrow << '\n');1386 }1387 bool isNeg = u[j+n] < borrow;1388 u[j+n] -= Lo_32(borrow);1389 1390 DEBUG_KNUTH(dbgs() << "KnuthDiv: after subtraction:");1391 DEBUG_KNUTH(for (int i = m + n; i >= 0; i--) dbgs() << " " << u[i]);1392 DEBUG_KNUTH(dbgs() << '\n');1393 1394 // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was1395 // negative, go to step D6; otherwise go on to step D7.1396 q[j] = Lo_32(qp);1397 if (isNeg) {1398 // D6. [Add back]. The probability that this step is necessary is very1399 // small, on the order of only 2/b. Make sure that test data accounts for1400 // this possibility. Decrease q[j] by 11401 q[j]--;1402 // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).1403 // A carry will occur to the left of u[j+n], and it should be ignored1404 // since it cancels with the borrow that occurred in D4.1405 bool carry = false;1406 for (unsigned i = 0; i < n; i++) {1407 uint32_t limit = std::min(u[j+i],v[i]);1408 u[j+i] += v[i] + carry;1409 carry = u[j+i] < limit || (carry && u[j+i] == limit);1410 }1411 u[j+n] += carry;1412 }1413 DEBUG_KNUTH(dbgs() << "KnuthDiv: after correction:");1414 DEBUG_KNUTH(for (int i = m + n; i >= 0; i--) dbgs() << " " << u[i]);1415 DEBUG_KNUTH(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n');1416 1417 // D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3.1418 } while (--j >= 0);1419 1420 DEBUG_KNUTH(dbgs() << "KnuthDiv: quotient:");1421 DEBUG_KNUTH(for (int i = m; i >= 0; i--) dbgs() << " " << q[i]);1422 DEBUG_KNUTH(dbgs() << '\n');1423 1424 // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired1425 // remainder may be obtained by dividing u[...] by d. If r is non-null we1426 // compute the remainder (urem uses this).1427 if (r) {1428 // The value d is expressed by the "shift" value above since we avoided1429 // multiplication by d by using a shift left. So, all we have to do is1430 // shift right here.1431 if (shift) {1432 uint32_t carry = 0;1433 DEBUG_KNUTH(dbgs() << "KnuthDiv: remainder:");1434 for (int i = n-1; i >= 0; i--) {1435 r[i] = (u[i] >> shift) | carry;1436 carry = u[i] << (32 - shift);1437 DEBUG_KNUTH(dbgs() << " " << r[i]);1438 }1439 } else {1440 for (int i = n-1; i >= 0; i--) {1441 r[i] = u[i];1442 DEBUG_KNUTH(dbgs() << " " << r[i]);1443 }1444 }1445 DEBUG_KNUTH(dbgs() << '\n');1446 }1447 DEBUG_KNUTH(dbgs() << '\n');1448}1449 1450void APInt::divide(const WordType *LHS, unsigned lhsWords, const WordType *RHS,1451 unsigned rhsWords, WordType *Quotient, WordType *Remainder) {1452 assert(lhsWords >= rhsWords && "Fractional result");1453 1454 // First, compose the values into an array of 32-bit words instead of1455 // 64-bit words. This is a necessity of both the "short division" algorithm1456 // and the Knuth "classical algorithm" which requires there to be native1457 // operations for +, -, and * on an m bit value with an m*2 bit result. We1458 // can't use 64-bit operands here because we don't have native results of1459 // 128-bits. Furthermore, casting the 64-bit values to 32-bit values won't1460 // work on large-endian machines.1461 unsigned n = rhsWords * 2;1462 unsigned m = (lhsWords * 2) - n;1463 1464 // Allocate space for the temporary values we need either on the stack, if1465 // it will fit, or on the heap if it won't.1466 uint32_t SPACE[128];1467 uint32_t *U = nullptr;1468 uint32_t *V = nullptr;1469 uint32_t *Q = nullptr;1470 uint32_t *R = nullptr;1471 if ((Remainder?4:3)*n+2*m+1 <= 128) {1472 U = &SPACE[0];1473 V = &SPACE[m+n+1];1474 Q = &SPACE[(m+n+1) + n];1475 if (Remainder)1476 R = &SPACE[(m+n+1) + n + (m+n)];1477 } else {1478 U = new uint32_t[m + n + 1];1479 V = new uint32_t[n];1480 Q = new uint32_t[m+n];1481 if (Remainder)1482 R = new uint32_t[n];1483 }1484 1485 // Initialize the dividend1486 memset(U, 0, (m+n+1)*sizeof(uint32_t));1487 for (unsigned i = 0; i < lhsWords; ++i) {1488 uint64_t tmp = LHS[i];1489 U[i * 2] = Lo_32(tmp);1490 U[i * 2 + 1] = Hi_32(tmp);1491 }1492 U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.1493 1494 // Initialize the divisor1495 memset(V, 0, (n)*sizeof(uint32_t));1496 for (unsigned i = 0; i < rhsWords; ++i) {1497 uint64_t tmp = RHS[i];1498 V[i * 2] = Lo_32(tmp);1499 V[i * 2 + 1] = Hi_32(tmp);1500 }1501 1502 // initialize the quotient and remainder1503 memset(Q, 0, (m+n) * sizeof(uint32_t));1504 if (Remainder)1505 memset(R, 0, n * sizeof(uint32_t));1506 1507 // Now, adjust m and n for the Knuth division. n is the number of words in1508 // the divisor. m is the number of words by which the dividend exceeds the1509 // divisor (i.e. m+n is the length of the dividend). These sizes must not1510 // contain any zero words or the Knuth algorithm fails.1511 for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {1512 n--;1513 m++;1514 }1515 for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)1516 m--;1517 1518 // If we're left with only a single word for the divisor, Knuth doesn't work1519 // so we implement the short division algorithm here. This is much simpler1520 // and faster because we are certain that we can divide a 64-bit quantity1521 // by a 32-bit quantity at hardware speed and short division is simply a1522 // series of such operations. This is just like doing short division but we1523 // are using base 2^32 instead of base 10.1524 assert(n != 0 && "Divide by zero?");1525 if (n == 1) {1526 uint32_t divisor = V[0];1527 uint32_t remainder = 0;1528 for (int i = m; i >= 0; i--) {1529 uint64_t partial_dividend = Make_64(remainder, U[i]);1530 if (partial_dividend == 0) {1531 Q[i] = 0;1532 remainder = 0;1533 } else if (partial_dividend < divisor) {1534 Q[i] = 0;1535 remainder = Lo_32(partial_dividend);1536 } else if (partial_dividend == divisor) {1537 Q[i] = 1;1538 remainder = 0;1539 } else {1540 Q[i] = Lo_32(partial_dividend / divisor);1541 remainder = Lo_32(partial_dividend - (Q[i] * divisor));1542 }1543 }1544 if (R)1545 R[0] = remainder;1546 } else {1547 // Now we're ready to invoke the Knuth classical divide algorithm. In this1548 // case n > 1.1549 KnuthDiv(U, V, Q, R, m, n);1550 }1551 1552 // If the caller wants the quotient1553 if (Quotient) {1554 for (unsigned i = 0; i < lhsWords; ++i)1555 Quotient[i] = Make_64(Q[i*2+1], Q[i*2]);1556 }1557 1558 // If the caller wants the remainder1559 if (Remainder) {1560 for (unsigned i = 0; i < rhsWords; ++i)1561 Remainder[i] = Make_64(R[i*2+1], R[i*2]);1562 }1563 1564 // Clean up the memory we allocated.1565 if (U != &SPACE[0]) {1566 delete [] U;1567 delete [] V;1568 delete [] Q;1569 delete [] R;1570 }1571}1572 1573APInt APInt::udiv(const APInt &RHS) const {1574 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");1575 1576 // First, deal with the easy case1577 if (isSingleWord()) {1578 assert(RHS.U.VAL != 0 && "Divide by zero?");1579 return APInt(BitWidth, U.VAL / RHS.U.VAL);1580 }1581 1582 // Get some facts about the LHS and RHS number of bits and words1583 unsigned lhsWords = getNumWords(getActiveBits());1584 unsigned rhsBits = RHS.getActiveBits();1585 unsigned rhsWords = getNumWords(rhsBits);1586 assert(rhsWords && "Divided by zero???");1587 1588 // Deal with some degenerate cases1589 if (!lhsWords)1590 // 0 / X ===> 01591 return APInt(BitWidth, 0);1592 if (rhsBits == 1)1593 // X / 1 ===> X1594 return *this;1595 if (lhsWords < rhsWords || this->ult(RHS))1596 // X / Y ===> 0, iff X < Y1597 return APInt(BitWidth, 0);1598 if (*this == RHS)1599 // X / X ===> 11600 return APInt(BitWidth, 1);1601 if (lhsWords == 1) // rhsWords is 1 if lhsWords is 1.1602 // All high words are zero, just use native divide1603 return APInt(BitWidth, this->U.pVal[0] / RHS.U.pVal[0]);1604 1605 // We have to compute it the hard way. Invoke the Knuth divide algorithm.1606 APInt Quotient(BitWidth, 0); // to hold result.1607 divide(U.pVal, lhsWords, RHS.U.pVal, rhsWords, Quotient.U.pVal, nullptr);1608 return Quotient;1609}1610 1611APInt APInt::udiv(uint64_t RHS) const {1612 assert(RHS != 0 && "Divide by zero?");1613 1614 // First, deal with the easy case1615 if (isSingleWord())1616 return APInt(BitWidth, U.VAL / RHS);1617 1618 // Get some facts about the LHS words.1619 unsigned lhsWords = getNumWords(getActiveBits());1620 1621 // Deal with some degenerate cases1622 if (!lhsWords)1623 // 0 / X ===> 01624 return APInt(BitWidth, 0);1625 if (RHS == 1)1626 // X / 1 ===> X1627 return *this;1628 if (this->ult(RHS))1629 // X / Y ===> 0, iff X < Y1630 return APInt(BitWidth, 0);1631 if (*this == RHS)1632 // X / X ===> 11633 return APInt(BitWidth, 1);1634 if (lhsWords == 1) // rhsWords is 1 if lhsWords is 1.1635 // All high words are zero, just use native divide1636 return APInt(BitWidth, this->U.pVal[0] / RHS);1637 1638 // We have to compute it the hard way. Invoke the Knuth divide algorithm.1639 APInt Quotient(BitWidth, 0); // to hold result.1640 divide(U.pVal, lhsWords, &RHS, 1, Quotient.U.pVal, nullptr);1641 return Quotient;1642}1643 1644APInt APInt::sdiv(const APInt &RHS) const {1645 if (isNegative()) {1646 if (RHS.isNegative())1647 return (-(*this)).udiv(-RHS);1648 return -((-(*this)).udiv(RHS));1649 }1650 if (RHS.isNegative())1651 return -(this->udiv(-RHS));1652 return this->udiv(RHS);1653}1654 1655APInt APInt::sdiv(int64_t RHS) const {1656 if (isNegative()) {1657 if (RHS < 0)1658 return (-(*this)).udiv(-RHS);1659 return -((-(*this)).udiv(RHS));1660 }1661 if (RHS < 0)1662 return -(this->udiv(-RHS));1663 return this->udiv(RHS);1664}1665 1666APInt APInt::urem(const APInt &RHS) const {1667 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");1668 if (isSingleWord()) {1669 assert(RHS.U.VAL != 0 && "Remainder by zero?");1670 return APInt(BitWidth, U.VAL % RHS.U.VAL);1671 }1672 1673 // Get some facts about the LHS1674 unsigned lhsWords = getNumWords(getActiveBits());1675 1676 // Get some facts about the RHS1677 unsigned rhsBits = RHS.getActiveBits();1678 unsigned rhsWords = getNumWords(rhsBits);1679 assert(rhsWords && "Performing remainder operation by zero ???");1680 1681 // Check the degenerate cases1682 if (lhsWords == 0)1683 // 0 % Y ===> 01684 return APInt(BitWidth, 0);1685 if (rhsBits == 1)1686 // X % 1 ===> 01687 return APInt(BitWidth, 0);1688 if (lhsWords < rhsWords || this->ult(RHS))1689 // X % Y ===> X, iff X < Y1690 return *this;1691 if (*this == RHS)1692 // X % X == 0;1693 return APInt(BitWidth, 0);1694 if (lhsWords == 1)1695 // All high words are zero, just use native remainder1696 return APInt(BitWidth, U.pVal[0] % RHS.U.pVal[0]);1697 1698 // We have to compute it the hard way. Invoke the Knuth divide algorithm.1699 APInt Remainder(BitWidth, 0);1700 divide(U.pVal, lhsWords, RHS.U.pVal, rhsWords, nullptr, Remainder.U.pVal);1701 return Remainder;1702}1703 1704uint64_t APInt::urem(uint64_t RHS) const {1705 assert(RHS != 0 && "Remainder by zero?");1706 1707 if (isSingleWord())1708 return U.VAL % RHS;1709 1710 // Get some facts about the LHS1711 unsigned lhsWords = getNumWords(getActiveBits());1712 1713 // Check the degenerate cases1714 if (lhsWords == 0)1715 // 0 % Y ===> 01716 return 0;1717 if (RHS == 1)1718 // X % 1 ===> 01719 return 0;1720 if (this->ult(RHS))1721 // X % Y ===> X, iff X < Y1722 return getZExtValue();1723 if (*this == RHS)1724 // X % X == 0;1725 return 0;1726 if (lhsWords == 1)1727 // All high words are zero, just use native remainder1728 return U.pVal[0] % RHS;1729 1730 // We have to compute it the hard way. Invoke the Knuth divide algorithm.1731 uint64_t Remainder;1732 divide(U.pVal, lhsWords, &RHS, 1, nullptr, &Remainder);1733 return Remainder;1734}1735 1736APInt APInt::srem(const APInt &RHS) const {1737 if (isNegative()) {1738 if (RHS.isNegative())1739 return -((-(*this)).urem(-RHS));1740 return -((-(*this)).urem(RHS));1741 }1742 if (RHS.isNegative())1743 return this->urem(-RHS);1744 return this->urem(RHS);1745}1746 1747int64_t APInt::srem(int64_t RHS) const {1748 if (isNegative()) {1749 if (RHS < 0)1750 return -((-(*this)).urem(-RHS));1751 return -((-(*this)).urem(RHS));1752 }1753 if (RHS < 0)1754 return this->urem(-RHS);1755 return this->urem(RHS);1756}1757 1758void APInt::udivrem(const APInt &LHS, const APInt &RHS,1759 APInt &Quotient, APInt &Remainder) {1760 assert(LHS.BitWidth == RHS.BitWidth && "Bit widths must be the same");1761 unsigned BitWidth = LHS.BitWidth;1762 1763 // First, deal with the easy case1764 if (LHS.isSingleWord()) {1765 assert(RHS.U.VAL != 0 && "Divide by zero?");1766 uint64_t QuotVal = LHS.U.VAL / RHS.U.VAL;1767 uint64_t RemVal = LHS.U.VAL % RHS.U.VAL;1768 Quotient = APInt(BitWidth, QuotVal);1769 Remainder = APInt(BitWidth, RemVal);1770 return;1771 }1772 1773 // Get some size facts about the dividend and divisor1774 unsigned lhsWords = getNumWords(LHS.getActiveBits());1775 unsigned rhsBits = RHS.getActiveBits();1776 unsigned rhsWords = getNumWords(rhsBits);1777 assert(rhsWords && "Performing divrem operation by zero ???");1778 1779 // Check the degenerate cases1780 if (lhsWords == 0) {1781 Quotient = APInt(BitWidth, 0); // 0 / Y ===> 01782 Remainder = APInt(BitWidth, 0); // 0 % Y ===> 01783 return;1784 }1785 1786 if (rhsBits == 1) {1787 Quotient = LHS; // X / 1 ===> X1788 Remainder = APInt(BitWidth, 0); // X % 1 ===> 01789 }1790 1791 if (lhsWords < rhsWords || LHS.ult(RHS)) {1792 Remainder = LHS; // X % Y ===> X, iff X < Y1793 Quotient = APInt(BitWidth, 0); // X / Y ===> 0, iff X < Y1794 return;1795 }1796 1797 if (LHS == RHS) {1798 Quotient = APInt(BitWidth, 1); // X / X ===> 11799 Remainder = APInt(BitWidth, 0); // X % X ===> 0;1800 return;1801 }1802 1803 // Make sure there is enough space to hold the results.1804 // NOTE: This assumes that reallocate won't affect any bits if it doesn't1805 // change the size. This is necessary if Quotient or Remainder is aliased1806 // with LHS or RHS.1807 Quotient.reallocate(BitWidth);1808 Remainder.reallocate(BitWidth);1809 1810 if (lhsWords == 1) { // rhsWords is 1 if lhsWords is 1.1811 // There is only one word to consider so use the native versions.1812 uint64_t lhsValue = LHS.U.pVal[0];1813 uint64_t rhsValue = RHS.U.pVal[0];1814 Quotient = lhsValue / rhsValue;1815 Remainder = lhsValue % rhsValue;1816 return;1817 }1818 1819 // Okay, lets do it the long way1820 divide(LHS.U.pVal, lhsWords, RHS.U.pVal, rhsWords, Quotient.U.pVal,1821 Remainder.U.pVal);1822 // Clear the rest of the Quotient and Remainder.1823 std::memset(Quotient.U.pVal + lhsWords, 0,1824 (getNumWords(BitWidth) - lhsWords) * APINT_WORD_SIZE);1825 std::memset(Remainder.U.pVal + rhsWords, 0,1826 (getNumWords(BitWidth) - rhsWords) * APINT_WORD_SIZE);1827}1828 1829void APInt::udivrem(const APInt &LHS, uint64_t RHS, APInt &Quotient,1830 uint64_t &Remainder) {1831 assert(RHS != 0 && "Divide by zero?");1832 unsigned BitWidth = LHS.BitWidth;1833 1834 // First, deal with the easy case1835 if (LHS.isSingleWord()) {1836 uint64_t QuotVal = LHS.U.VAL / RHS;1837 Remainder = LHS.U.VAL % RHS;1838 Quotient = APInt(BitWidth, QuotVal);1839 return;1840 }1841 1842 // Get some size facts about the dividend and divisor1843 unsigned lhsWords = getNumWords(LHS.getActiveBits());1844 1845 // Check the degenerate cases1846 if (lhsWords == 0) {1847 Quotient = APInt(BitWidth, 0); // 0 / Y ===> 01848 Remainder = 0; // 0 % Y ===> 01849 return;1850 }1851 1852 if (RHS == 1) {1853 Quotient = LHS; // X / 1 ===> X1854 Remainder = 0; // X % 1 ===> 01855 return;1856 }1857 1858 if (LHS.ult(RHS)) {1859 Remainder = LHS.getZExtValue(); // X % Y ===> X, iff X < Y1860 Quotient = APInt(BitWidth, 0); // X / Y ===> 0, iff X < Y1861 return;1862 }1863 1864 if (LHS == RHS) {1865 Quotient = APInt(BitWidth, 1); // X / X ===> 11866 Remainder = 0; // X % X ===> 0;1867 return;1868 }1869 1870 // Make sure there is enough space to hold the results.1871 // NOTE: This assumes that reallocate won't affect any bits if it doesn't1872 // change the size. This is necessary if Quotient is aliased with LHS.1873 Quotient.reallocate(BitWidth);1874 1875 if (lhsWords == 1) { // rhsWords is 1 if lhsWords is 1.1876 // There is only one word to consider so use the native versions.1877 uint64_t lhsValue = LHS.U.pVal[0];1878 Quotient = lhsValue / RHS;1879 Remainder = lhsValue % RHS;1880 return;1881 }1882 1883 // Okay, lets do it the long way1884 divide(LHS.U.pVal, lhsWords, &RHS, 1, Quotient.U.pVal, &Remainder);1885 // Clear the rest of the Quotient.1886 std::memset(Quotient.U.pVal + lhsWords, 0,1887 (getNumWords(BitWidth) - lhsWords) * APINT_WORD_SIZE);1888}1889 1890void APInt::sdivrem(const APInt &LHS, const APInt &RHS,1891 APInt &Quotient, APInt &Remainder) {1892 if (LHS.isNegative()) {1893 if (RHS.isNegative())1894 APInt::udivrem(-LHS, -RHS, Quotient, Remainder);1895 else {1896 APInt::udivrem(-LHS, RHS, Quotient, Remainder);1897 Quotient.negate();1898 }1899 Remainder.negate();1900 } else if (RHS.isNegative()) {1901 APInt::udivrem(LHS, -RHS, Quotient, Remainder);1902 Quotient.negate();1903 } else {1904 APInt::udivrem(LHS, RHS, Quotient, Remainder);1905 }1906}1907 1908void APInt::sdivrem(const APInt &LHS, int64_t RHS,1909 APInt &Quotient, int64_t &Remainder) {1910 uint64_t R = Remainder;1911 if (LHS.isNegative()) {1912 if (RHS < 0)1913 APInt::udivrem(-LHS, -RHS, Quotient, R);1914 else {1915 APInt::udivrem(-LHS, RHS, Quotient, R);1916 Quotient.negate();1917 }1918 R = -R;1919 } else if (RHS < 0) {1920 APInt::udivrem(LHS, -RHS, Quotient, R);1921 Quotient.negate();1922 } else {1923 APInt::udivrem(LHS, RHS, Quotient, R);1924 }1925 Remainder = R;1926}1927 1928APInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const {1929 APInt Res = *this+RHS;1930 Overflow = isNonNegative() == RHS.isNonNegative() &&1931 Res.isNonNegative() != isNonNegative();1932 return Res;1933}1934 1935APInt APInt::uadd_ov(const APInt &RHS, bool &Overflow) const {1936 APInt Res = *this+RHS;1937 Overflow = Res.ult(RHS);1938 return Res;1939}1940 1941APInt APInt::ssub_ov(const APInt &RHS, bool &Overflow) const {1942 APInt Res = *this - RHS;1943 Overflow = isNonNegative() != RHS.isNonNegative() &&1944 Res.isNonNegative() != isNonNegative();1945 return Res;1946}1947 1948APInt APInt::usub_ov(const APInt &RHS, bool &Overflow) const {1949 APInt Res = *this-RHS;1950 Overflow = Res.ugt(*this);1951 return Res;1952}1953 1954APInt APInt::sdiv_ov(const APInt &RHS, bool &Overflow) const {1955 // MININT/-1 --> overflow.1956 Overflow = isMinSignedValue() && RHS.isAllOnes();1957 return sdiv(RHS);1958}1959 1960APInt APInt::smul_ov(const APInt &RHS, bool &Overflow) const {1961 APInt Res = *this * RHS;1962 1963 if (RHS != 0)1964 Overflow = Res.sdiv(RHS) != *this ||1965 (isMinSignedValue() && RHS.isAllOnes());1966 else1967 Overflow = false;1968 return Res;1969}1970 1971APInt APInt::umul_ov(const APInt &RHS, bool &Overflow) const {1972 if (countl_zero() + RHS.countl_zero() + 2 <= BitWidth) {1973 Overflow = true;1974 return *this * RHS;1975 }1976 1977 APInt Res = lshr(1) * RHS;1978 Overflow = Res.isNegative();1979 Res <<= 1;1980 if ((*this)[0]) {1981 Res += RHS;1982 if (Res.ult(RHS))1983 Overflow = true;1984 }1985 return Res;1986}1987 1988APInt APInt::sshl_ov(const APInt &ShAmt, bool &Overflow) const {1989 return sshl_ov(ShAmt.getLimitedValue(getBitWidth()), Overflow);1990}1991 1992APInt APInt::sshl_ov(unsigned ShAmt, bool &Overflow) const {1993 Overflow = ShAmt >= getBitWidth();1994 if (Overflow)1995 return APInt(BitWidth, 0);1996 1997 if (isNonNegative()) // Don't allow sign change.1998 Overflow = ShAmt >= countl_zero();1999 else2000 Overflow = ShAmt >= countl_one();2001 2002 return *this << ShAmt;2003}2004 2005APInt APInt::ushl_ov(const APInt &ShAmt, bool &Overflow) const {2006 return ushl_ov(ShAmt.getLimitedValue(getBitWidth()), Overflow);2007}2008 2009APInt APInt::ushl_ov(unsigned ShAmt, bool &Overflow) const {2010 Overflow = ShAmt >= getBitWidth();2011 if (Overflow)2012 return APInt(BitWidth, 0);2013 2014 Overflow = ShAmt > countl_zero();2015 2016 return *this << ShAmt;2017}2018 2019APInt APInt::sfloordiv_ov(const APInt &RHS, bool &Overflow) const {2020 APInt quotient = sdiv_ov(RHS, Overflow);2021 if ((quotient * RHS != *this) && (isNegative() != RHS.isNegative()))2022 return quotient - 1;2023 return quotient;2024}2025 2026APInt APInt::sadd_sat(const APInt &RHS) const {2027 bool Overflow;2028 APInt Res = sadd_ov(RHS, Overflow);2029 if (!Overflow)2030 return Res;2031 2032 return isNegative() ? APInt::getSignedMinValue(BitWidth)2033 : APInt::getSignedMaxValue(BitWidth);2034}2035 2036APInt APInt::uadd_sat(const APInt &RHS) const {2037 bool Overflow;2038 APInt Res = uadd_ov(RHS, Overflow);2039 if (!Overflow)2040 return Res;2041 2042 return APInt::getMaxValue(BitWidth);2043}2044 2045APInt APInt::ssub_sat(const APInt &RHS) const {2046 bool Overflow;2047 APInt Res = ssub_ov(RHS, Overflow);2048 if (!Overflow)2049 return Res;2050 2051 return isNegative() ? APInt::getSignedMinValue(BitWidth)2052 : APInt::getSignedMaxValue(BitWidth);2053}2054 2055APInt APInt::usub_sat(const APInt &RHS) const {2056 bool Overflow;2057 APInt Res = usub_ov(RHS, Overflow);2058 if (!Overflow)2059 return Res;2060 2061 return APInt(BitWidth, 0);2062}2063 2064APInt APInt::smul_sat(const APInt &RHS) const {2065 bool Overflow;2066 APInt Res = smul_ov(RHS, Overflow);2067 if (!Overflow)2068 return Res;2069 2070 // The result is negative if one and only one of inputs is negative.2071 bool ResIsNegative = isNegative() ^ RHS.isNegative();2072 2073 return ResIsNegative ? APInt::getSignedMinValue(BitWidth)2074 : APInt::getSignedMaxValue(BitWidth);2075}2076 2077APInt APInt::umul_sat(const APInt &RHS) const {2078 bool Overflow;2079 APInt Res = umul_ov(RHS, Overflow);2080 if (!Overflow)2081 return Res;2082 2083 return APInt::getMaxValue(BitWidth);2084}2085 2086APInt APInt::sshl_sat(const APInt &RHS) const {2087 return sshl_sat(RHS.getLimitedValue(getBitWidth()));2088}2089 2090APInt APInt::sshl_sat(unsigned RHS) const {2091 bool Overflow;2092 APInt Res = sshl_ov(RHS, Overflow);2093 if (!Overflow)2094 return Res;2095 2096 return isNegative() ? APInt::getSignedMinValue(BitWidth)2097 : APInt::getSignedMaxValue(BitWidth);2098}2099 2100APInt APInt::ushl_sat(const APInt &RHS) const {2101 return ushl_sat(RHS.getLimitedValue(getBitWidth()));2102}2103 2104APInt APInt::ushl_sat(unsigned RHS) const {2105 bool Overflow;2106 APInt Res = ushl_ov(RHS, Overflow);2107 if (!Overflow)2108 return Res;2109 2110 return APInt::getMaxValue(BitWidth);2111}2112 2113void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) {2114 // Check our assumptions here2115 assert(!str.empty() && "Invalid string length");2116 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||2117 radix == 36) &&2118 "Radix should be 2, 8, 10, 16, or 36!");2119 2120 StringRef::iterator p = str.begin();2121 size_t slen = str.size();2122 bool isNeg = *p == '-';2123 if (*p == '-' || *p == '+') {2124 p++;2125 slen--;2126 assert(slen && "String is only a sign, needs a value.");2127 }2128 assert((slen <= numbits || radix != 2) && "Insufficient bit width");2129 assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width");2130 assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width");2131 assert((((slen-1)*64)/22 <= numbits || radix != 10) &&2132 "Insufficient bit width");2133 2134 // Allocate memory if needed2135 if (isSingleWord())2136 U.VAL = 0;2137 else2138 U.pVal = getClearedMemory(getNumWords());2139 2140 // Figure out if we can shift instead of multiply2141 unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);2142 2143 // Enter digit traversal loop2144 for (StringRef::iterator e = str.end(); p != e; ++p) {2145 unsigned digit = getDigit(*p, radix);2146 assert(digit < radix && "Invalid character in digit string");2147 2148 // Shift or multiply the value by the radix2149 if (slen > 1) {2150 if (shift)2151 *this <<= shift;2152 else2153 *this *= radix;2154 }2155 2156 // Add in the digit we just interpreted2157 *this += digit;2158 }2159 // If its negative, put it in two's complement form2160 if (isNeg)2161 this->negate();2162}2163 2164void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix, bool Signed,2165 bool formatAsCLiteral, bool UpperCase,2166 bool InsertSeparators) const {2167 assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 ||2168 Radix == 36) &&2169 "Radix should be 2, 8, 10, 16, or 36!");2170 2171 const char *Prefix = "";2172 if (formatAsCLiteral) {2173 switch (Radix) {2174 case 2:2175 // Binary literals are a non-standard extension added in gcc 4.3:2176 // http://gcc.gnu.org/onlinedocs/gcc-4.3.0/gcc/Binary-constants.html2177 Prefix = "0b";2178 break;2179 case 8:2180 Prefix = "0";2181 break;2182 case 10:2183 break; // No prefix2184 case 16:2185 Prefix = "0x";2186 break;2187 default:2188 llvm_unreachable("Invalid radix!");2189 }2190 }2191 2192 // Number of digits in a group between separators.2193 unsigned Grouping = (Radix == 8 || Radix == 10) ? 3 : 4;2194 2195 // First, check for a zero value and just short circuit the logic below.2196 if (isZero()) {2197 while (*Prefix) {2198 Str.push_back(*Prefix);2199 ++Prefix;2200 };2201 Str.push_back('0');2202 return;2203 }2204 2205 static const char BothDigits[] = "0123456789abcdefghijklmnopqrstuvwxyz"2206 "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";2207 const char *Digits = BothDigits + (UpperCase ? 36 : 0);2208 2209 if (isSingleWord()) {2210 char Buffer[65];2211 char *BufPtr = std::end(Buffer);2212 2213 uint64_t N;2214 if (!Signed) {2215 N = getZExtValue();2216 } else {2217 int64_t I = getSExtValue();2218 if (I >= 0) {2219 N = I;2220 } else {2221 Str.push_back('-');2222 N = -(uint64_t)I;2223 }2224 }2225 2226 while (*Prefix) {2227 Str.push_back(*Prefix);2228 ++Prefix;2229 };2230 2231 int Pos = 0;2232 while (N) {2233 if (InsertSeparators && Pos % Grouping == 0 && Pos > 0)2234 *--BufPtr = '\'';2235 *--BufPtr = Digits[N % Radix];2236 N /= Radix;2237 Pos++;2238 }2239 Str.append(BufPtr, std::end(Buffer));2240 return;2241 }2242 2243 APInt Tmp(*this);2244 2245 if (Signed && isNegative()) {2246 // They want to print the signed version and it is a negative value2247 // Flip the bits and add one to turn it into the equivalent positive2248 // value and put a '-' in the result.2249 Tmp.negate();2250 Str.push_back('-');2251 }2252 2253 while (*Prefix) {2254 Str.push_back(*Prefix);2255 ++Prefix;2256 }2257 2258 // We insert the digits backward, then reverse them to get the right order.2259 unsigned StartDig = Str.size();2260 2261 // For the 2, 8 and 16 bit cases, we can just shift instead of divide2262 // because the number of bits per digit (1, 3 and 4 respectively) divides2263 // equally. We just shift until the value is zero.2264 if (Radix == 2 || Radix == 8 || Radix == 16) {2265 // Just shift tmp right for each digit width until it becomes zero2266 unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));2267 unsigned MaskAmt = Radix - 1;2268 2269 int Pos = 0;2270 while (Tmp.getBoolValue()) {2271 unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;2272 if (InsertSeparators && Pos % Grouping == 0 && Pos > 0)2273 Str.push_back('\'');2274 2275 Str.push_back(Digits[Digit]);2276 Tmp.lshrInPlace(ShiftAmt);2277 Pos++;2278 }2279 } else {2280 int Pos = 0;2281 while (Tmp.getBoolValue()) {2282 uint64_t Digit;2283 udivrem(Tmp, Radix, Tmp, Digit);2284 assert(Digit < Radix && "divide failed");2285 if (InsertSeparators && Pos % Grouping == 0 && Pos > 0)2286 Str.push_back('\'');2287 2288 Str.push_back(Digits[Digit]);2289 Pos++;2290 }2291 }2292 2293 // Reverse the digits before returning.2294 std::reverse(Str.begin()+StartDig, Str.end());2295}2296 2297#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)2298LLVM_DUMP_METHOD void APInt::dump() const {2299 SmallString<40> S, U;2300 this->toStringUnsigned(U);2301 this->toStringSigned(S);2302 dbgs() << "APInt(" << BitWidth << "b, "2303 << U << "u " << S << "s)\n";2304}2305#endif2306 2307void APInt::print(raw_ostream &OS, bool isSigned) const {2308 SmallString<40> S;2309 this->toString(S, 10, isSigned, /* formatAsCLiteral = */false);2310 OS << S;2311}2312 2313// This implements a variety of operations on a representation of2314// arbitrary precision, two's-complement, bignum integer values.2315 2316// Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe2317// and unrestricting assumption.2318static_assert(APInt::APINT_BITS_PER_WORD % 2 == 0,2319 "Part width must be divisible by 2!");2320 2321// Returns the integer part with the least significant BITS set.2322// BITS cannot be zero.2323static inline APInt::WordType lowBitMask(unsigned bits) {2324 assert(bits != 0 && bits <= APInt::APINT_BITS_PER_WORD);2325 return ~(APInt::WordType) 0 >> (APInt::APINT_BITS_PER_WORD - bits);2326}2327 2328/// Returns the value of the lower half of PART.2329static inline APInt::WordType lowHalf(APInt::WordType part) {2330 return part & lowBitMask(APInt::APINT_BITS_PER_WORD / 2);2331}2332 2333/// Returns the value of the upper half of PART.2334static inline APInt::WordType highHalf(APInt::WordType part) {2335 return part >> (APInt::APINT_BITS_PER_WORD / 2);2336}2337 2338/// Sets the least significant part of a bignum to the input value, and zeroes2339/// out higher parts.2340void APInt::tcSet(WordType *dst, WordType part, unsigned parts) {2341 assert(parts > 0);2342 dst[0] = part;2343 for (unsigned i = 1; i < parts; i++)2344 dst[i] = 0;2345}2346 2347/// Assign one bignum to another.2348void APInt::tcAssign(WordType *dst, const WordType *src, unsigned parts) {2349 for (unsigned i = 0; i < parts; i++)2350 dst[i] = src[i];2351}2352 2353/// Returns true if a bignum is zero, false otherwise.2354bool APInt::tcIsZero(const WordType *src, unsigned parts) {2355 for (unsigned i = 0; i < parts; i++)2356 if (src[i])2357 return false;2358 2359 return true;2360}2361 2362/// Extract the given bit of a bignum; returns 0 or 1.2363int APInt::tcExtractBit(const WordType *parts, unsigned bit) {2364 return (parts[whichWord(bit)] & maskBit(bit)) != 0;2365}2366 2367/// Set the given bit of a bignum.2368void APInt::tcSetBit(WordType *parts, unsigned bit) {2369 parts[whichWord(bit)] |= maskBit(bit);2370}2371 2372/// Clears the given bit of a bignum.2373void APInt::tcClearBit(WordType *parts, unsigned bit) {2374 parts[whichWord(bit)] &= ~maskBit(bit);2375}2376 2377/// Returns the bit number of the least significant set bit of a number. If the2378/// input number has no bits set UINT_MAX is returned.2379unsigned APInt::tcLSB(const WordType *parts, unsigned n) {2380 for (unsigned i = 0; i < n; i++) {2381 if (parts[i] != 0) {2382 unsigned lsb = llvm::countr_zero(parts[i]);2383 return lsb + i * APINT_BITS_PER_WORD;2384 }2385 }2386 2387 return UINT_MAX;2388}2389 2390/// Returns the bit number of the most significant set bit of a number.2391/// If the input number has no bits set UINT_MAX is returned.2392unsigned APInt::tcMSB(const WordType *parts, unsigned n) {2393 do {2394 --n;2395 2396 if (parts[n] != 0) {2397 static_assert(sizeof(parts[n]) <= sizeof(uint64_t));2398 unsigned msb = llvm::Log2_64(parts[n]);2399 2400 return msb + n * APINT_BITS_PER_WORD;2401 }2402 } while (n);2403 2404 return UINT_MAX;2405}2406 2407/// Copy the bit vector of width srcBITS from SRC, starting at bit srcLSB, to2408/// DST, of dstCOUNT parts, such that the bit srcLSB becomes the least2409/// significant bit of DST. All high bits above srcBITS in DST are zero-filled.2410/// */2411void2412APInt::tcExtract(WordType *dst, unsigned dstCount, const WordType *src,2413 unsigned srcBits, unsigned srcLSB) {2414 unsigned dstParts = (srcBits + APINT_BITS_PER_WORD - 1) / APINT_BITS_PER_WORD;2415 assert(dstParts <= dstCount);2416 2417 unsigned firstSrcPart = srcLSB / APINT_BITS_PER_WORD;2418 tcAssign(dst, src + firstSrcPart, dstParts);2419 2420 unsigned shift = srcLSB % APINT_BITS_PER_WORD;2421 tcShiftRight(dst, dstParts, shift);2422 2423 // We now have (dstParts * APINT_BITS_PER_WORD - shift) bits from SRC2424 // in DST. If this is less that srcBits, append the rest, else2425 // clear the high bits.2426 unsigned n = dstParts * APINT_BITS_PER_WORD - shift;2427 if (n < srcBits) {2428 WordType mask = lowBitMask (srcBits - n);2429 dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)2430 << n % APINT_BITS_PER_WORD);2431 } else if (n > srcBits) {2432 if (srcBits % APINT_BITS_PER_WORD)2433 dst[dstParts - 1] &= lowBitMask (srcBits % APINT_BITS_PER_WORD);2434 }2435 2436 // Clear high parts.2437 while (dstParts < dstCount)2438 dst[dstParts++] = 0;2439}2440 2441//// DST += RHS + C where C is zero or one. Returns the carry flag.2442APInt::WordType APInt::tcAdd(WordType *dst, const WordType *rhs,2443 WordType c, unsigned parts) {2444 assert(c <= 1);2445 2446 for (unsigned i = 0; i < parts; i++) {2447 WordType l = dst[i];2448 if (c) {2449 dst[i] += rhs[i] + 1;2450 c = (dst[i] <= l);2451 } else {2452 dst[i] += rhs[i];2453 c = (dst[i] < l);2454 }2455 }2456 2457 return c;2458}2459 2460/// This function adds a single "word" integer, src, to the multiple2461/// "word" integer array, dst[]. dst[] is modified to reflect the addition and2462/// 1 is returned if there is a carry out, otherwise 0 is returned.2463/// @returns the carry of the addition.2464APInt::WordType APInt::tcAddPart(WordType *dst, WordType src,2465 unsigned parts) {2466 for (unsigned i = 0; i < parts; ++i) {2467 dst[i] += src;2468 if (dst[i] >= src)2469 return 0; // No need to carry so exit early.2470 src = 1; // Carry one to next digit.2471 }2472 2473 return 1;2474}2475 2476/// DST -= RHS + C where C is zero or one. Returns the carry flag.2477APInt::WordType APInt::tcSubtract(WordType *dst, const WordType *rhs,2478 WordType c, unsigned parts) {2479 assert(c <= 1);2480 2481 for (unsigned i = 0; i < parts; i++) {2482 WordType l = dst[i];2483 if (c) {2484 dst[i] -= rhs[i] + 1;2485 c = (dst[i] >= l);2486 } else {2487 dst[i] -= rhs[i];2488 c = (dst[i] > l);2489 }2490 }2491 2492 return c;2493}2494 2495/// This function subtracts a single "word" (64-bit word), src, from2496/// the multi-word integer array, dst[], propagating the borrowed 1 value until2497/// no further borrowing is needed or it runs out of "words" in dst. The result2498/// is 1 if "borrowing" exhausted the digits in dst, or 0 if dst was not2499/// exhausted. In other words, if src > dst then this function returns 1,2500/// otherwise 0.2501/// @returns the borrow out of the subtraction2502APInt::WordType APInt::tcSubtractPart(WordType *dst, WordType src,2503 unsigned parts) {2504 for (unsigned i = 0; i < parts; ++i) {2505 WordType Dst = dst[i];2506 dst[i] -= src;2507 if (src <= Dst)2508 return 0; // No need to borrow so exit early.2509 src = 1; // We have to "borrow 1" from next "word"2510 }2511 2512 return 1;2513}2514 2515/// Negate a bignum in-place.2516void APInt::tcNegate(WordType *dst, unsigned parts) {2517 tcComplement(dst, parts);2518 tcIncrement(dst, parts);2519}2520 2521/// DST += SRC * MULTIPLIER + CARRY if add is true2522/// DST = SRC * MULTIPLIER + CARRY if add is false2523/// Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC2524/// they must start at the same point, i.e. DST == SRC.2525/// If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is2526/// returned. Otherwise DST is filled with the least significant2527/// DSTPARTS parts of the result, and if all of the omitted higher2528/// parts were zero return zero, otherwise overflow occurred and2529/// return one.2530int APInt::tcMultiplyPart(WordType *dst, const WordType *src,2531 WordType multiplier, WordType carry,2532 unsigned srcParts, unsigned dstParts,2533 bool add) {2534 // Otherwise our writes of DST kill our later reads of SRC.2535 assert(dst <= src || dst >= src + srcParts);2536 assert(dstParts <= srcParts + 1);2537 2538 // N loops; minimum of dstParts and srcParts.2539 unsigned n = std::min(dstParts, srcParts);2540 2541 for (unsigned i = 0; i < n; i++) {2542 // [LOW, HIGH] = MULTIPLIER * SRC[i] + DST[i] + CARRY.2543 // This cannot overflow, because:2544 // (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)2545 // which is less than n^2.2546 WordType srcPart = src[i];2547 WordType low, mid, high;2548 if (multiplier == 0 || srcPart == 0) {2549 low = carry;2550 high = 0;2551 } else {2552 low = lowHalf(srcPart) * lowHalf(multiplier);2553 high = highHalf(srcPart) * highHalf(multiplier);2554 2555 mid = lowHalf(srcPart) * highHalf(multiplier);2556 high += highHalf(mid);2557 mid <<= APINT_BITS_PER_WORD / 2;2558 if (low + mid < low)2559 high++;2560 low += mid;2561 2562 mid = highHalf(srcPart) * lowHalf(multiplier);2563 high += highHalf(mid);2564 mid <<= APINT_BITS_PER_WORD / 2;2565 if (low + mid < low)2566 high++;2567 low += mid;2568 2569 // Now add carry.2570 if (low + carry < low)2571 high++;2572 low += carry;2573 }2574 2575 if (add) {2576 // And now DST[i], and store the new low part there.2577 if (low + dst[i] < low)2578 high++;2579 dst[i] += low;2580 } else {2581 dst[i] = low;2582 }2583 2584 carry = high;2585 }2586 2587 if (srcParts < dstParts) {2588 // Full multiplication, there is no overflow.2589 assert(srcParts + 1 == dstParts);2590 dst[srcParts] = carry;2591 return 0;2592 }2593 2594 // We overflowed if there is carry.2595 if (carry)2596 return 1;2597 2598 // We would overflow if any significant unwritten parts would be2599 // non-zero. This is true if any remaining src parts are non-zero2600 // and the multiplier is non-zero.2601 if (multiplier)2602 for (unsigned i = dstParts; i < srcParts; i++)2603 if (src[i])2604 return 1;2605 2606 // We fitted in the narrow destination.2607 return 0;2608}2609 2610/// DST = LHS * RHS, where DST has the same width as the operands and2611/// is filled with the least significant parts of the result. Returns2612/// one if overflow occurred, otherwise zero. DST must be disjoint2613/// from both operands.2614int APInt::tcMultiply(WordType *dst, const WordType *lhs,2615 const WordType *rhs, unsigned parts) {2616 assert(dst != lhs && dst != rhs);2617 2618 int overflow = 0;2619 2620 for (unsigned i = 0; i < parts; i++) {2621 // Don't accumulate on the first iteration so we don't need to initalize2622 // dst to 0.2623 overflow |=2624 tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts, parts - i, i != 0);2625 }2626 2627 return overflow;2628}2629 2630/// DST = LHS * RHS, where DST has width the sum of the widths of the2631/// operands. No overflow occurs. DST must be disjoint from both operands.2632void APInt::tcFullMultiply(WordType *dst, const WordType *lhs,2633 const WordType *rhs, unsigned lhsParts,2634 unsigned rhsParts) {2635 // Put the narrower number on the LHS for less loops below.2636 if (lhsParts > rhsParts)2637 return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);2638 2639 assert(dst != lhs && dst != rhs);2640 2641 for (unsigned i = 0; i < lhsParts; i++) {2642 // Don't accumulate on the first iteration so we don't need to initalize2643 // dst to 0.2644 tcMultiplyPart(&dst[i], rhs, lhs[i], 0, rhsParts, rhsParts + 1, i != 0);2645 }2646}2647 2648// If RHS is zero LHS and REMAINDER are left unchanged, return one.2649// Otherwise set LHS to LHS / RHS with the fractional part discarded,2650// set REMAINDER to the remainder, return zero. i.e.2651//2652// OLD_LHS = RHS * LHS + REMAINDER2653//2654// SCRATCH is a bignum of the same size as the operands and result for2655// use by the routine; its contents need not be initialized and are2656// destroyed. LHS, REMAINDER and SCRATCH must be distinct.2657int APInt::tcDivide(WordType *lhs, const WordType *rhs,2658 WordType *remainder, WordType *srhs,2659 unsigned parts) {2660 assert(lhs != remainder && lhs != srhs && remainder != srhs);2661 2662 unsigned shiftCount = tcMSB(rhs, parts) + 1;2663 if (shiftCount == 0)2664 return true;2665 2666 shiftCount = parts * APINT_BITS_PER_WORD - shiftCount;2667 unsigned n = shiftCount / APINT_BITS_PER_WORD;2668 WordType mask = (WordType) 1 << (shiftCount % APINT_BITS_PER_WORD);2669 2670 tcAssign(srhs, rhs, parts);2671 tcShiftLeft(srhs, parts, shiftCount);2672 tcAssign(remainder, lhs, parts);2673 tcSet(lhs, 0, parts);2674 2675 // Loop, subtracting SRHS if REMAINDER is greater and adding that to the2676 // total.2677 for (;;) {2678 int compare = tcCompare(remainder, srhs, parts);2679 if (compare >= 0) {2680 tcSubtract(remainder, srhs, 0, parts);2681 lhs[n] |= mask;2682 }2683 2684 if (shiftCount == 0)2685 break;2686 shiftCount--;2687 tcShiftRight(srhs, parts, 1);2688 if ((mask >>= 1) == 0) {2689 mask = (WordType) 1 << (APINT_BITS_PER_WORD - 1);2690 n--;2691 }2692 }2693 2694 return false;2695}2696 2697/// Shift a bignum left Count bits in-place. Shifted in bits are zero. There are2698/// no restrictions on Count.2699void APInt::tcShiftLeft(WordType *Dst, unsigned Words, unsigned Count) {2700 // Don't bother performing a no-op shift.2701 if (!Count)2702 return;2703 2704 // WordShift is the inter-part shift; BitShift is the intra-part shift.2705 unsigned WordShift = std::min(Count / APINT_BITS_PER_WORD, Words);2706 unsigned BitShift = Count % APINT_BITS_PER_WORD;2707 2708 // Fastpath for moving by whole words.2709 if (BitShift == 0) {2710 std::memmove(Dst + WordShift, Dst, (Words - WordShift) * APINT_WORD_SIZE);2711 } else {2712 while (Words-- > WordShift) {2713 Dst[Words] = Dst[Words - WordShift] << BitShift;2714 if (Words > WordShift)2715 Dst[Words] |=2716 Dst[Words - WordShift - 1] >> (APINT_BITS_PER_WORD - BitShift);2717 }2718 }2719 2720 // Fill in the remainder with 0s.2721 std::memset(Dst, 0, WordShift * APINT_WORD_SIZE);2722}2723 2724/// Shift a bignum right Count bits in-place. Shifted in bits are zero. There2725/// are no restrictions on Count.2726void APInt::tcShiftRight(WordType *Dst, unsigned Words, unsigned Count) {2727 // Don't bother performing a no-op shift.2728 if (!Count)2729 return;2730 2731 // WordShift is the inter-part shift; BitShift is the intra-part shift.2732 unsigned WordShift = std::min(Count / APINT_BITS_PER_WORD, Words);2733 unsigned BitShift = Count % APINT_BITS_PER_WORD;2734 2735 unsigned WordsToMove = Words - WordShift;2736 // Fastpath for moving by whole words.2737 if (BitShift == 0) {2738 std::memmove(Dst, Dst + WordShift, WordsToMove * APINT_WORD_SIZE);2739 } else {2740 for (unsigned i = 0; i != WordsToMove; ++i) {2741 Dst[i] = Dst[i + WordShift] >> BitShift;2742 if (i + 1 != WordsToMove)2743 Dst[i] |= Dst[i + WordShift + 1] << (APINT_BITS_PER_WORD - BitShift);2744 }2745 }2746 2747 // Fill in the remainder with 0s.2748 std::memset(Dst + WordsToMove, 0, WordShift * APINT_WORD_SIZE);2749}2750 2751// Comparison (unsigned) of two bignums.2752int APInt::tcCompare(const WordType *lhs, const WordType *rhs,2753 unsigned parts) {2754 while (parts) {2755 parts--;2756 if (lhs[parts] != rhs[parts])2757 return (lhs[parts] > rhs[parts]) ? 1 : -1;2758 }2759 2760 return 0;2761}2762 2763APInt llvm::APIntOps::RoundingUDiv(const APInt &A, const APInt &B,2764 APInt::Rounding RM) {2765 // Currently udivrem always rounds down.2766 switch (RM) {2767 case APInt::Rounding::DOWN:2768 case APInt::Rounding::TOWARD_ZERO:2769 return A.udiv(B);2770 case APInt::Rounding::UP: {2771 APInt Quo, Rem;2772 APInt::udivrem(A, B, Quo, Rem);2773 if (Rem.isZero())2774 return Quo;2775 return Quo + 1;2776 }2777 }2778 llvm_unreachable("Unknown APInt::Rounding enum");2779}2780 2781APInt llvm::APIntOps::RoundingSDiv(const APInt &A, const APInt &B,2782 APInt::Rounding RM) {2783 switch (RM) {2784 case APInt::Rounding::DOWN:2785 case APInt::Rounding::UP: {2786 APInt Quo, Rem;2787 APInt::sdivrem(A, B, Quo, Rem);2788 if (Rem.isZero())2789 return Quo;2790 // This algorithm deals with arbitrary rounding mode used by sdivrem.2791 // We want to check whether the non-integer part of the mathematical value2792 // is negative or not. If the non-integer part is negative, we need to round2793 // down from Quo; otherwise, if it's positive or 0, we return Quo, as it's2794 // already rounded down.2795 if (RM == APInt::Rounding::DOWN) {2796 if (Rem.isNegative() != B.isNegative())2797 return Quo - 1;2798 return Quo;2799 }2800 if (Rem.isNegative() != B.isNegative())2801 return Quo;2802 return Quo + 1;2803 }2804 // Currently sdiv rounds towards zero.2805 case APInt::Rounding::TOWARD_ZERO:2806 return A.sdiv(B);2807 }2808 llvm_unreachable("Unknown APInt::Rounding enum");2809}2810 2811std::optional<APInt>2812llvm::APIntOps::SolveQuadraticEquationWrap(APInt A, APInt B, APInt C,2813 unsigned RangeWidth) {2814 unsigned CoeffWidth = A.getBitWidth();2815 assert(CoeffWidth == B.getBitWidth() && CoeffWidth == C.getBitWidth());2816 assert(RangeWidth <= CoeffWidth &&2817 "Value range width should be less than coefficient width");2818 assert(RangeWidth > 1 && "Value range bit width should be > 1");2819 2820 LLVM_DEBUG(dbgs() << __func__ << ": solving " << A << "x^2 + " << B2821 << "x + " << C << ", rw:" << RangeWidth << '\n');2822 2823 // Identify 0 as a (non)solution immediately.2824 if (C.sextOrTrunc(RangeWidth).isZero()) {2825 LLVM_DEBUG(dbgs() << __func__ << ": zero solution\n");2826 return APInt(CoeffWidth, 0);2827 }2828 2829 // The result of APInt arithmetic has the same bit width as the operands,2830 // so it can actually lose high bits. A product of two n-bit integers needs2831 // 2n-1 bits to represent the full value.2832 // The operation done below (on quadratic coefficients) that can produce2833 // the largest value is the evaluation of the equation during bisection,2834 // which needs 3 times the bitwidth of the coefficient, so the total number2835 // of required bits is 3n.2836 //2837 // The purpose of this extension is to simulate the set Z of all integers,2838 // where n+1 > n for all n in Z. In Z it makes sense to talk about positive2839 // and negative numbers (not so much in a modulo arithmetic). The method2840 // used to solve the equation is based on the standard formula for real2841 // numbers, and uses the concepts of "positive" and "negative" with their2842 // usual meanings.2843 CoeffWidth *= 3;2844 A = A.sext(CoeffWidth);2845 B = B.sext(CoeffWidth);2846 C = C.sext(CoeffWidth);2847 2848 // Make A > 0 for simplicity. Negate cannot overflow at this point because2849 // the bit width has increased.2850 if (A.isNegative()) {2851 A.negate();2852 B.negate();2853 C.negate();2854 }2855 2856 // Solving an equation q(x) = 0 with coefficients in modular arithmetic2857 // is really solving a set of equations q(x) = kR for k = 0, 1, 2, ...,2858 // and R = 2^BitWidth.2859 // Since we're trying not only to find exact solutions, but also values2860 // that "wrap around", such a set will always have a solution, i.e. an x2861 // that satisfies at least one of the equations, or such that |q(x)|2862 // exceeds kR, while |q(x-1)| for the same k does not.2863 //2864 // We need to find a value k, such that Ax^2 + Bx + C = kR will have a2865 // positive solution n (in the above sense), and also such that the n2866 // will be the least among all solutions corresponding to k = 0, 1, ...2867 // (more precisely, the least element in the set2868 // { n(k) | k is such that a solution n(k) exists }).2869 //2870 // Consider the parabola (over real numbers) that corresponds to the2871 // quadratic equation. Since A > 0, the arms of the parabola will point2872 // up. Picking different values of k will shift it up and down by R.2873 //2874 // We want to shift the parabola in such a way as to reduce the problem2875 // of solving q(x) = kR to solving shifted_q(x) = 0.2876 // (The interesting solutions are the ceilings of the real number2877 // solutions.)2878 APInt R = APInt::getOneBitSet(CoeffWidth, RangeWidth);2879 APInt TwoA = 2 * A;2880 APInt SqrB = B * B;2881 bool PickLow;2882 2883 auto RoundUp = [] (const APInt &V, const APInt &A) -> APInt {2884 assert(A.isStrictlyPositive());2885 APInt T = V.abs().urem(A);2886 if (T.isZero())2887 return V;2888 return V.isNegative() ? V+T : V+(A-T);2889 };2890 2891 // The vertex of the parabola is at -B/2A, but since A > 0, it's negative2892 // iff B is positive.2893 if (B.isNonNegative()) {2894 // If B >= 0, the vertex it at a negative location (or at 0), so in2895 // order to have a non-negative solution we need to pick k that makes2896 // C-kR negative. To satisfy all the requirements for the solution2897 // that we are looking for, it needs to be closest to 0 of all k.2898 C = C.srem(R);2899 if (C.isStrictlyPositive())2900 C -= R;2901 // Pick the greater solution.2902 PickLow = false;2903 } else {2904 // If B < 0, the vertex is at a positive location. For any solution2905 // to exist, the discriminant must be non-negative. This means that2906 // C-kR <= B^2/4A is a necessary condition for k, i.e. there is a2907 // lower bound on values of k: kR >= C - B^2/4A.2908 APInt LowkR = C - SqrB.udiv(2*TwoA); // udiv because all values > 0.2909 // Round LowkR up (towards +inf) to the nearest kR.2910 LowkR = RoundUp(LowkR, R);2911 2912 // If there exists k meeting the condition above, and such that2913 // C-kR > 0, there will be two positive real number solutions of2914 // q(x) = kR. Out of all such values of k, pick the one that makes2915 // C-kR closest to 0, (i.e. pick maximum k such that C-kR > 0).2916 // In other words, find maximum k such that LowkR <= kR < C.2917 if (C.sgt(LowkR)) {2918 // If LowkR < C, then such a k is guaranteed to exist because2919 // LowkR itself is a multiple of R.2920 C -= -RoundUp(-C, R); // C = C - RoundDown(C, R)2921 // Pick the smaller solution.2922 PickLow = true;2923 } else {2924 // If C-kR < 0 for all potential k's, it means that one solution2925 // will be negative, while the other will be positive. The positive2926 // solution will shift towards 0 if the parabola is moved up.2927 // Pick the kR closest to the lower bound (i.e. make C-kR closest2928 // to 0, or in other words, out of all parabolas that have solutions,2929 // pick the one that is the farthest "up").2930 // Since LowkR is itself a multiple of R, simply take C-LowkR.2931 C -= LowkR;2932 // Pick the greater solution.2933 PickLow = false;2934 }2935 }2936 2937 LLVM_DEBUG(dbgs() << __func__ << ": updated coefficients " << A << "x^2 + "2938 << B << "x + " << C << ", rw:" << RangeWidth << '\n');2939 2940 APInt D = SqrB - 4*A*C;2941 assert(D.isNonNegative() && "Negative discriminant");2942 APInt SQ = D.sqrt();2943 2944 APInt Q = SQ * SQ;2945 bool InexactSQ = Q != D;2946 // The calculated SQ may actually be greater than the exact (non-integer)2947 // value. If that's the case, decrement SQ to get a value that is lower.2948 if (Q.sgt(D))2949 SQ -= 1;2950 2951 APInt X;2952 APInt Rem;2953 2954 // SQ is rounded down (i.e SQ * SQ <= D), so the roots may be inexact.2955 // When using the quadratic formula directly, the calculated low root2956 // may be greater than the exact one, since we would be subtracting SQ.2957 // To make sure that the calculated root is not greater than the exact2958 // one, subtract SQ+1 when calculating the low root (for inexact value2959 // of SQ).2960 if (PickLow)2961 APInt::sdivrem(-B - (SQ+InexactSQ), TwoA, X, Rem);2962 else2963 APInt::sdivrem(-B + SQ, TwoA, X, Rem);2964 2965 // The updated coefficients should be such that the (exact) solution is2966 // positive. Since APInt division rounds towards 0, the calculated one2967 // can be 0, but cannot be negative.2968 assert(X.isNonNegative() && "Solution should be non-negative");2969 2970 if (!InexactSQ && Rem.isZero()) {2971 LLVM_DEBUG(dbgs() << __func__ << ": solution (root): " << X << '\n');2972 return X;2973 }2974 2975 assert((SQ*SQ).sle(D) && "SQ = |_sqrt(D)_|, so SQ*SQ <= D");2976 // The exact value of the square root of D should be between SQ and SQ+1.2977 // This implies that the solution should be between that corresponding to2978 // SQ (i.e. X) and that corresponding to SQ+1.2979 //2980 // The calculated X cannot be greater than the exact (real) solution.2981 // Actually it must be strictly less than the exact solution, while2982 // X+1 will be greater than or equal to it.2983 2984 APInt VX = (A*X + B)*X + C;2985 APInt VY = VX + TwoA*X + A + B;2986 bool SignChange =2987 VX.isNegative() != VY.isNegative() || VX.isZero() != VY.isZero();2988 // If the sign did not change between X and X+1, X is not a valid solution.2989 // This could happen when the actual (exact) roots don't have an integer2990 // between them, so they would both be contained between X and X+1.2991 if (!SignChange) {2992 LLVM_DEBUG(dbgs() << __func__ << ": no valid solution\n");2993 return std::nullopt;2994 }2995 2996 X += 1;2997 LLVM_DEBUG(dbgs() << __func__ << ": solution (wrap): " << X << '\n');2998 return X;2999}3000 3001std::optional<unsigned>3002llvm::APIntOps::GetMostSignificantDifferentBit(const APInt &A, const APInt &B) {3003 assert(A.getBitWidth() == B.getBitWidth() && "Must have the same bitwidth");3004 if (A == B)3005 return std::nullopt;3006 return A.getBitWidth() - ((A ^ B).countl_zero() + 1);3007}3008 3009APInt llvm::APIntOps::ScaleBitMask(const APInt &A, unsigned NewBitWidth,3010 bool MatchAllBits) {3011 unsigned OldBitWidth = A.getBitWidth();3012 assert((((OldBitWidth % NewBitWidth) == 0) ||3013 ((NewBitWidth % OldBitWidth) == 0)) &&3014 "One size should be a multiple of the other one. "3015 "Can't do fractional scaling.");3016 3017 // Check for matching bitwidths.3018 if (OldBitWidth == NewBitWidth)3019 return A;3020 3021 APInt NewA = APInt::getZero(NewBitWidth);3022 3023 // Check for null input.3024 if (A.isZero())3025 return NewA;3026 3027 if (NewBitWidth > OldBitWidth) {3028 // Repeat bits.3029 unsigned Scale = NewBitWidth / OldBitWidth;3030 for (unsigned i = 0; i != OldBitWidth; ++i)3031 if (A[i])3032 NewA.setBits(i * Scale, (i + 1) * Scale);3033 } else {3034 unsigned Scale = OldBitWidth / NewBitWidth;3035 for (unsigned i = 0; i != NewBitWidth; ++i) {3036 if (MatchAllBits) {3037 if (A.extractBits(Scale, i * Scale).isAllOnes())3038 NewA.setBit(i);3039 } else {3040 if (!A.extractBits(Scale, i * Scale).isZero())3041 NewA.setBit(i);3042 }3043 }3044 }3045 3046 return NewA;3047}3048 3049/// StoreIntToMemory - Fills the StoreBytes bytes of memory starting from Dst3050/// with the integer held in IntVal.3051void llvm::StoreIntToMemory(const APInt &IntVal, uint8_t *Dst,3052 unsigned StoreBytes) {3053 assert((IntVal.getBitWidth()+7)/8 >= StoreBytes && "Integer too small!");3054 const uint8_t *Src = (const uint8_t *)IntVal.getRawData();3055 3056 if (sys::IsLittleEndianHost) {3057 // Little-endian host - the source is ordered from LSB to MSB. Order the3058 // destination from LSB to MSB: Do a straight copy.3059 memcpy(Dst, Src, StoreBytes);3060 } else {3061 // Big-endian host - the source is an array of 64 bit words ordered from3062 // LSW to MSW. Each word is ordered from MSB to LSB. Order the destination3063 // from MSB to LSB: Reverse the word order, but not the bytes in a word.3064 while (StoreBytes > sizeof(uint64_t)) {3065 StoreBytes -= sizeof(uint64_t);3066 // May not be aligned so use memcpy.3067 memcpy(Dst + StoreBytes, Src, sizeof(uint64_t));3068 Src += sizeof(uint64_t);3069 }3070 3071 memcpy(Dst, Src + sizeof(uint64_t) - StoreBytes, StoreBytes);3072 }3073}3074 3075/// LoadIntFromMemory - Loads the integer stored in the LoadBytes bytes starting3076/// from Src into IntVal, which is assumed to be wide enough and to hold zero.3077void llvm::LoadIntFromMemory(APInt &IntVal, const uint8_t *Src,3078 unsigned LoadBytes) {3079 assert((IntVal.getBitWidth()+7)/8 >= LoadBytes && "Integer too small!");3080 uint8_t *Dst = reinterpret_cast<uint8_t *>(3081 const_cast<uint64_t *>(IntVal.getRawData()));3082 3083 if (sys::IsLittleEndianHost)3084 // Little-endian host - the destination must be ordered from LSB to MSB.3085 // The source is ordered from LSB to MSB: Do a straight copy.3086 memcpy(Dst, Src, LoadBytes);3087 else {3088 // Big-endian - the destination is an array of 64 bit words ordered from3089 // LSW to MSW. Each word must be ordered from MSB to LSB. The source is3090 // ordered from MSB to LSB: Reverse the word order, but not the bytes in3091 // a word.3092 while (LoadBytes > sizeof(uint64_t)) {3093 LoadBytes -= sizeof(uint64_t);3094 // May not be aligned so use memcpy.3095 memcpy(Dst, Src + LoadBytes, sizeof(uint64_t));3096 Dst += sizeof(uint64_t);3097 }3098 3099 memcpy(Dst + sizeof(uint64_t) - LoadBytes, Src, LoadBytes);3100 }3101}3102 3103APInt APIntOps::avgFloorS(const APInt &C1, const APInt &C2) {3104 // Return floor((C1 + C2) / 2)3105 return (C1 & C2) + (C1 ^ C2).ashr(1);3106}3107 3108APInt APIntOps::avgFloorU(const APInt &C1, const APInt &C2) {3109 // Return floor((C1 + C2) / 2)3110 return (C1 & C2) + (C1 ^ C2).lshr(1);3111}3112 3113APInt APIntOps::avgCeilS(const APInt &C1, const APInt &C2) {3114 // Return ceil((C1 + C2) / 2)3115 return (C1 | C2) - (C1 ^ C2).ashr(1);3116}3117 3118APInt APIntOps::avgCeilU(const APInt &C1, const APInt &C2) {3119 // Return ceil((C1 + C2) / 2)3120 return (C1 | C2) - (C1 ^ C2).lshr(1);3121}3122 3123APInt APIntOps::mulhs(const APInt &C1, const APInt &C2) {3124 assert(C1.getBitWidth() == C2.getBitWidth() && "Unequal bitwidths");3125 unsigned FullWidth = C1.getBitWidth() * 2;3126 APInt C1Ext = C1.sext(FullWidth);3127 APInt C2Ext = C2.sext(FullWidth);3128 return (C1Ext * C2Ext).extractBits(C1.getBitWidth(), C1.getBitWidth());3129}3130 3131APInt APIntOps::mulhu(const APInt &C1, const APInt &C2) {3132 assert(C1.getBitWidth() == C2.getBitWidth() && "Unequal bitwidths");3133 unsigned FullWidth = C1.getBitWidth() * 2;3134 APInt C1Ext = C1.zext(FullWidth);3135 APInt C2Ext = C2.zext(FullWidth);3136 return (C1Ext * C2Ext).extractBits(C1.getBitWidth(), C1.getBitWidth());3137}3138 3139APInt APIntOps::mulsExtended(const APInt &C1, const APInt &C2) {3140 assert(C1.getBitWidth() == C2.getBitWidth() && "Unequal bitwidths");3141 unsigned FullWidth = C1.getBitWidth() * 2;3142 APInt C1Ext = C1.sext(FullWidth);3143 APInt C2Ext = C2.sext(FullWidth);3144 return C1Ext * C2Ext;3145}3146 3147APInt APIntOps::muluExtended(const APInt &C1, const APInt &C2) {3148 assert(C1.getBitWidth() == C2.getBitWidth() && "Unequal bitwidths");3149 unsigned FullWidth = C1.getBitWidth() * 2;3150 APInt C1Ext = C1.zext(FullWidth);3151 APInt C2Ext = C2.zext(FullWidth);3152 return C1Ext * C2Ext;3153}3154 3155APInt APIntOps::pow(const APInt &X, int64_t N) {3156 assert(N >= 0 && "negative exponents not supported.");3157 APInt Acc = APInt(X.getBitWidth(), 1);3158 if (N == 0)3159 return Acc;3160 APInt Base = X;3161 int64_t RemainingExponent = N;3162 while (RemainingExponent > 0) {3163 while (RemainingExponent % 2 == 0) {3164 Base *= Base;3165 RemainingExponent /= 2;3166 }3167 --RemainingExponent;3168 Acc *= Base;3169 }3170 return Acc;3171}3172 3173APInt llvm::APIntOps::fshl(const APInt &Hi, const APInt &Lo,3174 const APInt &Shift) {3175 assert(Hi.getBitWidth() == Lo.getBitWidth());3176 unsigned ShiftAmt = rotateModulo(Hi.getBitWidth(), Shift);3177 if (ShiftAmt == 0)3178 return Hi;3179 return Hi.shl(ShiftAmt) | Lo.lshr(Hi.getBitWidth() - ShiftAmt);3180}3181 3182APInt llvm::APIntOps::fshr(const APInt &Hi, const APInt &Lo,3183 const APInt &Shift) {3184 assert(Hi.getBitWidth() == Lo.getBitWidth());3185 unsigned ShiftAmt = rotateModulo(Hi.getBitWidth(), Shift);3186 if (ShiftAmt == 0)3187 return Lo;3188 return Hi.shl(Hi.getBitWidth() - ShiftAmt) | Lo.lshr(ShiftAmt);3189}3190 3191APInt llvm::APIntOps::clmul(const APInt &LHS, const APInt &RHS) {3192 assert(LHS.getBitWidth() == RHS.getBitWidth());3193 unsigned BW = LHS.getBitWidth();3194 APInt Result(BW, 0);3195 for (unsigned I : seq<unsigned>(BW))3196 if (RHS[I])3197 Result ^= LHS.shl(I);3198 return Result;3199}3200 3201APInt llvm::APIntOps::clmulr(const APInt &LHS, const APInt &RHS) {3202 assert(LHS.getBitWidth() == RHS.getBitWidth());3203 return clmul(LHS.reverseBits(), RHS.reverseBits()).reverseBits();3204}3205 3206APInt llvm::APIntOps::clmulh(const APInt &LHS, const APInt &RHS) {3207 assert(LHS.getBitWidth() == RHS.getBitWidth());3208 return clmulr(LHS, RHS).lshr(1);3209}3210