/usr/src/gnu/usr.bin/clang/libLLVMSupport/../../../llvm/llvm/include/llvm/ADT/APInt.h

Bug Summary

File:	src/gnu/usr.bin/clang/libLLVMSupport/../../../llvm/llvm/include/llvm/ADT/APInt.h
Warning:	line 799, column 15 Use of zero-allocated memory

Annotated Source Code

Press '?' to see keyboard shortcuts

Show analyzer invocation

clang -cc1 -cc1 -triple amd64-unknown-openbsd7.0 -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name APInt.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model static -mframe-pointer=all -relaxed-aliasing -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/usr/src/gnu/usr.bin/clang/libLLVMSupport/obj -resource-dir /usr/local/lib/clang/13.0.0 -I /usr/src/gnu/usr.bin/clang/libLLVMSupport/../../../llvm/llvm/include/llvm/ADT -I /usr/src/gnu/usr.bin/clang/libLLVMSupport/../../../llvm/llvm/include/llvm/Support -I /usr/src/gnu/usr.bin/clang/libLLVMSupport/../../../llvm/llvm/include -I /usr/src/gnu/usr.bin/clang/libLLVMSupport/../include -I /usr/src/gnu/usr.bin/clang/libLLVMSupport/obj -I /usr/src/gnu/usr.bin/clang/libLLVMSupport/obj/../include -D NDEBUG -D __STDC_LIMIT_MACROS -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D LLVM_PREFIX="/usr" -internal-isystem /usr/include/c++/v1 -internal-isystem /usr/local/lib/clang/13.0.0/include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/usr/src/gnu/usr.bin/clang/libLLVMSupport/obj -ferror-limit 19 -fvisibility-inlines-hidden -fwrapv -stack-protector 2 -fno-rtti -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -fno-builtin-malloc -fno-builtin-calloc -fno-builtin-realloc -fno-builtin-valloc -fno-builtin-free -fno-builtin-strdup -fno-builtin-strndup -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /home/ben/Projects/vmm/scan-build/2022-01-12-194120-40624-1 -x c++ /usr/src/gnu/usr.bin/clang/libLLVMSupport/../../../llvm/llvm/lib/Support/APInt.cpp

/usr/src/gnu/usr.bin/clang/libLLVMSupport/../../../llvm/llvm/lib/Support/APInt.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-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements a class to represent arbitrary precision integer
10// constant values and provide a variety of arithmetic operations on them.
11//
12//===----------------------------------------------------------------------===//

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/Optional.h"
19#include "llvm/ADT/SmallString.h"
20#include "llvm/ADT/StringRef.h"
21#include "llvm/ADT/bit.h"
22#include "llvm/Config/llvm-config.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 <climits>
28#include <cmath>
29#include <cstdlib>
30#include <cstring>
31using namespace llvm;

33#define DEBUG_TYPE"apint" "apint"

35/// A utility function for allocating memory, checking for allocation failures,
36/// and ensuring the contents are zeroed.
37inline static uint64_t* getClearedMemory(unsigned numWords) {
uint64_t *result = new uint64_t[numWords];
memset(result, 0, numWords * sizeof(uint64_t));
return result;
41}

43/// A utility function for allocating memory and checking for allocation
44/// failure.  The content is not zeroed.
45inline static uint64_t* getMemory(unsigned numWords) {
return new uint64_t[numWords];
22
←
Memory is allocated→
47}

49/// A utility function that converts a character to a digit.
50inline static unsigned getDigit(char cdigit, uint8_t radix) {
unsigned r;

if (radix == 16 || radix == 36) {
  r = cdigit - '0';
  if (r <= 9)
    return r;

  r = cdigit - 'A';
  if (r <= radix - 11U)
    return r + 10;

  r = cdigit - 'a';
  if (r <= radix - 11U)
    return r + 10;

  radix = 10;
}

r = cdigit - '0';
if (r < radix)
  return r;

return -1U;
74}


77void APInt::initSlowCase(uint64_t val, bool isSigned) {
U.pVal = getClearedMemory(getNumWords());
U.pVal[0] = val;
if (isSigned && int64_t(val) < 0)
  for (unsigned i = 1; i < getNumWords(); ++i)
    U.pVal[i] = WORDTYPE_MAX;
clearUnusedBits();
84}

86void APInt::initSlowCase(const APInt& that) {
U.pVal = getMemory(getNumWords());
memcpy(U.pVal, that.U.pVal, getNumWords() * APINT_WORD_SIZE);
89}

91void APInt::initFromArray(ArrayRef<uint64_t> bigVal) {
assert(BitWidth && "Bitwidth too small")((void)0);
assert(bigVal.data() && "Null pointer detected!")((void)0);
if (isSingleWord())
  U.VAL = bigVal[0];
else {
  // Get memory, cleared to 0
  U.pVal = getClearedMemory(getNumWords());
  // Calculate the number of words to copy
  unsigned words = std::min<unsigned>(bigVal.size(), getNumWords());
  // Copy the words from bigVal to pVal
  memcpy(U.pVal, bigVal.data(), words * APINT_WORD_SIZE);
}
// Make sure unused high bits are cleared
clearUnusedBits();
106}

108APInt::APInt(unsigned numBits, ArrayRef<uint64_t> bigVal)
: BitWidth(numBits) {
initFromArray(bigVal);
111}

113APInt::APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[])
: BitWidth(numBits) {
initFromArray(makeArrayRef(bigVal, numWords));
116}

118APInt::APInt(unsigned numbits, StringRef Str, uint8_t radix)
: BitWidth(numbits) {
assert(BitWidth && "Bitwidth too small")((void)0);
fromString(numbits, Str, radix);
122}

124void APInt::reallocate(unsigned NewBitWidth) {
// If the number of words is the same we can just change the width and stop.
if (getNumWords() == getNumWords(NewBitWidth)) {
18
←
Taking false branch→
  BitWidth = NewBitWidth;
  return;
}

// If we have an allocation, delete it.
if (!isSingleWord())
19
←
Taking false branch→
  delete [] U.pVal;

// Update BitWidth.
BitWidth = NewBitWidth;

// If we are supposed to have an allocation, create it.
if (!isSingleWord())
20
←
Taking true branch→
  U.pVal = getMemory(getNumWords());
21
←
Calling 'getMemory'→
23
←
Returned allocated memory→
141}

143void APInt::AssignSlowCase(const APInt& RHS) {
// Don't do anything for X = X
if (this == &RHS)
  return;

// Adjust the bit width and handle allocations as necessary.
reallocate(RHS.getBitWidth());

// Copy the data.
if (isSingleWord())
  U.VAL = RHS.U.VAL;
else
  memcpy(U.pVal, RHS.U.pVal, getNumWords() * APINT_WORD_SIZE);
156}

158/// This method 'profiles' an APInt for use with FoldingSet.
159void APInt::Profile(FoldingSetNodeID& ID) const {
ID.AddInteger(BitWidth);

if (isSingleWord()) {
  ID.AddInteger(U.VAL);
  return;
}

unsigned NumWords = getNumWords();
for (unsigned i = 0; i < NumWords; ++i)
  ID.AddInteger(U.pVal[i]);
170}

172/// Prefix increment operator. Increments the APInt by one.
173APInt& APInt::operator++() {
if (isSingleWord())
  ++U.VAL;
else
  tcIncrement(U.pVal, getNumWords());
return clearUnusedBits();
179}

181/// Prefix decrement operator. Decrements the APInt by one.
182APInt& APInt::operator--() {
if (isSingleWord())
  --U.VAL;
else
  tcDecrement(U.pVal, getNumWords());
return clearUnusedBits();
188}

190/// Adds the RHS APInt to this APInt.
191/// @returns this, after addition of RHS.
192/// Addition assignment operator.
193APInt& APInt::operator+=(const APInt& RHS) {
assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")((void)0);
if (isSingleWord())
  U.VAL += RHS.U.VAL;
else
  tcAdd(U.pVal, RHS.U.pVal, 0, getNumWords());
return clearUnusedBits();
200}

202APInt& APInt::operator+=(uint64_t RHS) {
if (isSingleWord())
  U.VAL += RHS;
else
  tcAddPart(U.pVal, RHS, getNumWords());
return clearUnusedBits();
208}

210/// Subtracts the RHS APInt from this APInt
211/// @returns this, after subtraction
212/// Subtraction assignment operator.
213APInt& APInt::operator-=(const APInt& RHS) {
assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")((void)0);
if (isSingleWord())
  U.VAL -= RHS.U.VAL;
else
  tcSubtract(U.pVal, RHS.U.pVal, 0, getNumWords());
return clearUnusedBits();
220}

222APInt& APInt::operator-=(uint64_t RHS) {
if (isSingleWord())
  U.VAL -= RHS;
else
  tcSubtractPart(U.pVal, RHS, getNumWords());
return clearUnusedBits();
228}

230APInt APInt::operator*(const APInt& RHS) const {
assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")((void)0);
if (isSingleWord())
  return APInt(BitWidth, U.VAL * RHS.U.VAL);

APInt Result(getMemory(getNumWords()), getBitWidth());

tcMultiply(Result.U.pVal, U.pVal, RHS.U.pVal, getNumWords());

Result.clearUnusedBits();
return Result;
241}

243void APInt::AndAssignSlowCase(const APInt& RHS) {
tcAnd(U.pVal, RHS.U.pVal, getNumWords());
245}

247void APInt::OrAssignSlowCase(const APInt& RHS) {
tcOr(U.pVal, RHS.U.pVal, getNumWords());
249}

251void APInt::XorAssignSlowCase(const APInt& RHS) {
tcXor(U.pVal, RHS.U.pVal, getNumWords());
253}

255APInt& APInt::operator*=(const APInt& RHS) {
assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")((void)0);
*this = *this * RHS;
return *this;
259}

261APInt& APInt::operator*=(uint64_t RHS) {
if (isSingleWord()) {
  U.VAL *= RHS;
} else {
  unsigned NumWords = getNumWords();
  tcMultiplyPart(U.pVal, U.pVal, RHS, 0, NumWords, NumWords, false);
}
return clearUnusedBits();
269}

271bool APInt::EqualSlowCase(const APInt& RHS) const {
return std::equal(U.pVal, U.pVal + getNumWords(), RHS.U.pVal);
273}

275int APInt::compare(const APInt& RHS) const {
assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison")((void)0);
if (isSingleWord())
  return U.VAL < RHS.U.VAL ? -1 : U.VAL > RHS.U.VAL;

return tcCompare(U.pVal, RHS.U.pVal, getNumWords());
281}

283int APInt::compareSigned(const APInt& RHS) const {
assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison")((void)0);
if (isSingleWord()) {
  int64_t lhsSext = SignExtend64(U.VAL, BitWidth);
  int64_t rhsSext = SignExtend64(RHS.U.VAL, BitWidth);
  return lhsSext < rhsSext ? -1 : lhsSext > rhsSext;
}

bool lhsNeg = isNegative();
bool rhsNeg = RHS.isNegative();

// If the sign bits don't match, then (LHS < RHS) if LHS is negative
if (lhsNeg != rhsNeg)
  return lhsNeg ? -1 : 1;

// Otherwise we can just use an unsigned comparison, because even negative
// numbers compare correctly this way if both have the same signed-ness.
return tcCompare(U.pVal, RHS.U.pVal, getNumWords());
301}

303void APInt::setBitsSlowCase(unsigned loBit, unsigned hiBit) {
unsigned loWord = whichWord(loBit);
unsigned hiWord = whichWord(hiBit);

// Create an initial mask for the low word with zeros below loBit.
uint64_t loMask = WORDTYPE_MAX << whichBit(loBit);

// If hiBit is not aligned, we need a high mask.
unsigned hiShiftAmt = whichBit(hiBit);
if (hiShiftAmt != 0) {
  // Create a high mask with zeros above hiBit.
  uint64_t hiMask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - hiShiftAmt);
  // If loWord and hiWord are equal, then we combine the masks. Otherwise,
  // set the bits in hiWord.
  if (hiWord == loWord)
    loMask &= hiMask;
  else
    U.pVal[hiWord] |= hiMask;
}
// Apply the mask to the low word.
U.pVal[loWord] |= loMask;

// Fill any words between loWord and hiWord with all ones.
for (unsigned word = loWord + 1; word < hiWord; ++word)
  U.pVal[word] = WORDTYPE_MAX;
328}

330/// Toggle every bit to its opposite value.
331void APInt::flipAllBitsSlowCase() {
tcComplement(U.pVal, getNumWords());
clearUnusedBits();
334}

336/// Toggle a given bit to its opposite value whose position is given
337/// as "bitPosition".
338/// Toggles a given bit to its opposite value.
339void APInt::flipBit(unsigned bitPosition) {
assert(bitPosition < BitWidth && "Out of the bit-width range!")((void)0);
setBitVal(bitPosition, !(*this)[bitPosition]);
342}

344void APInt::insertBits(const APInt &subBits, unsigned bitPosition) {
unsigned subBitWidth = subBits.getBitWidth();
assert(0 < subBitWidth && (subBitWidth + bitPosition) <= BitWidth &&((void)0)
       "Illegal bit insertion")((void)0);

// Insertion is a direct copy.
if (subBitWidth == BitWidth) {
  *this = subBits;
  return;
}

// Single word result can be done as a direct bitmask.
if (isSingleWord()) {
  uint64_t mask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - subBitWidth);
  U.VAL &= ~(mask << bitPosition);
  U.VAL |= (subBits.U.VAL << bitPosition);
  return;
}

unsigned loBit = whichBit(bitPosition);
unsigned loWord = whichWord(bitPosition);
unsigned hi1Word = whichWord(bitPosition + subBitWidth - 1);

// Insertion within a single word can be done as a direct bitmask.
if (loWord == hi1Word) {
  uint64_t mask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - subBitWidth);
  U.pVal[loWord] &= ~(mask << loBit);
  U.pVal[loWord] |= (subBits.U.VAL << loBit);
  return;
}

// Insert on word boundaries.
if (loBit == 0) {
  // Direct copy whole words.
  unsigned numWholeSubWords = subBitWidth / APINT_BITS_PER_WORD;
  memcpy(U.pVal + loWord, subBits.getRawData(),
         numWholeSubWords * APINT_WORD_SIZE);

  // Mask+insert remaining bits.
  unsigned remainingBits = subBitWidth % APINT_BITS_PER_WORD;
  if (remainingBits != 0) {
    uint64_t mask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - remainingBits);
    U.pVal[hi1Word] &= ~mask;
    U.pVal[hi1Word] |= subBits.getWord(subBitWidth - 1);
  }
  return;
}

// General case - set/clear individual bits in dst based on src.
// TODO - there is scope for optimization here, but at the moment this code
// path is barely used so prefer readability over performance.
for (unsigned i = 0; i != subBitWidth; ++i)
  setBitVal(bitPosition + i, subBits[i]);
397}

399void APInt::insertBits(uint64_t subBits, unsigned bitPosition, unsigned numBits) {
uint64_t maskBits = maskTrailingOnes<uint64_t>(numBits);
subBits &= maskBits;
if (isSingleWord()) {
  U.VAL &= ~(maskBits << bitPosition);
  U.VAL |= subBits << bitPosition;
  return;
}

unsigned loBit = whichBit(bitPosition);
unsigned loWord = whichWord(bitPosition);
unsigned hiWord = whichWord(bitPosition + numBits - 1);
if (loWord == hiWord) {
  U.pVal[loWord] &= ~(maskBits << loBit);
  U.pVal[loWord] |= subBits << loBit;
  return;
}

static_assert(8 * sizeof(WordType) <= 64, "This code assumes only two words affected");
unsigned wordBits = 8 * sizeof(WordType);
U.pVal[loWord] &= ~(maskBits << loBit);
U.pVal[loWord] |= subBits << loBit;

U.pVal[hiWord] &= ~(maskBits >> (wordBits - loBit));
U.pVal[hiWord] |= subBits >> (wordBits - loBit);
424}

426APInt APInt::extractBits(unsigned numBits, unsigned bitPosition) const {
assert(numBits > 0 && "Can't extract zero bits")((void)0);
assert(bitPosition < BitWidth && (numBits + bitPosition) <= BitWidth &&((void)0)
       "Illegal bit extraction")((void)0);

if (isSingleWord())
  return APInt(numBits, U.VAL >> bitPosition);

unsigned loBit = whichBit(bitPosition);
unsigned loWord = whichWord(bitPosition);
unsigned hiWord = whichWord(bitPosition + numBits - 1);

// Single word result extracting bits from a single word source.
if (loWord == hiWord)
  return APInt(numBits, U.pVal[loWord] >> loBit);

// Extracting bits that start on a source word boundary can be done
// as a fast memory copy.
if (loBit == 0)
  return APInt(numBits, makeArrayRef(U.pVal + loWord, 1 + hiWord - loWord));

// General case - shift + copy source words directly into place.
APInt Result(numBits, 0);
unsigned NumSrcWords = getNumWords();
unsigned NumDstWords = Result.getNumWords();

uint64_t *DestPtr = Result.isSingleWord() ? &Result.U.VAL : Result.U.pVal;
for (unsigned word = 0; word < NumDstWords; ++word) {
  uint64_t w0 = U.pVal[loWord + word];
  uint64_t w1 =
      (loWord + word + 1) < NumSrcWords ? U.pVal[loWord + word + 1] : 0;
  DestPtr[word] = (w0 >> loBit) | (w1 << (APINT_BITS_PER_WORD - loBit));
}

return Result.clearUnusedBits();
461}

463uint64_t APInt::extractBitsAsZExtValue(unsigned numBits,
                                     unsigned bitPosition) const {
assert(numBits > 0 && "Can't extract zero bits")((void)0);
assert(bitPosition < BitWidth && (numBits + bitPosition) <= BitWidth &&((void)0)
       "Illegal bit extraction")((void)0);
assert(numBits <= 64 && "Illegal bit extraction")((void)0);

uint64_t maskBits = maskTrailingOnes<uint64_t>(numBits);
if (isSingleWord())
  return (U.VAL >> bitPosition) & maskBits;

unsigned loBit = whichBit(bitPosition);
unsigned loWord = whichWord(bitPosition);
unsigned hiWord = whichWord(bitPosition + numBits - 1);
if (loWord == hiWord)
  return (U.pVal[loWord] >> loBit) & maskBits;

static_assert(8 * sizeof(WordType) <= 64, "This code assumes only two words affected");
unsigned wordBits = 8 * sizeof(WordType);
uint64_t retBits = U.pVal[loWord] >> loBit;
retBits |= U.pVal[hiWord] << (wordBits - loBit);
retBits &= maskBits;
return retBits;
486}

488unsigned APInt::getBitsNeeded(StringRef str, uint8_t radix) {
assert(!str.empty() && "Invalid string length")((void)0);
assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||((void)0)
        radix == 36) &&((void)0)
       "Radix should be 2, 8, 10, 16, or 36!")((void)0);

size_t slen = str.size();

// Each computation below needs to know if it's negative.
StringRef::iterator p = str.begin();
unsigned isNegative = *p == '-';
if (*p == '-' || *p == '+') {
  p++;
  slen--;
  assert(slen && "String is only a sign, needs a value.")((void)0);
}

// For radixes of power-of-two values, the bits required is accurately and
// easily computed
if (radix == 2)
  return slen + isNegative;
if (radix == 8)
  return slen * 3 + isNegative;
if (radix == 16)
  return slen * 4 + isNegative;

// FIXME: base 36

// This is grossly inefficient but accurate. We could probably do something
// with a computation of roughly slen*64/20 and then adjust by the value of
// the first few digits. But, I'm not sure how accurate that could be.

// Compute a sufficient number of bits that is always large enough but might
// be too large. This avoids the assertion in the constructor. This
// calculation doesn't work appropriately for the numbers 0-9, so just use 4
// bits in that case.
unsigned sufficient
  = radix == 10? (slen == 1 ? 4 : slen * 64/18)
               : (slen == 1 ? 7 : slen * 16/3);

// Convert to the actual binary value.
APInt tmp(sufficient, StringRef(p, slen), radix);

// Compute how many bits are required. If the log is infinite, assume we need
// just bit. If the log is exact and value is negative, then the value is
// MinSignedValue with (log + 1) bits.
unsigned log = tmp.logBase2();
if (log == (unsigned)-1) {
  return isNegative + 1;
} else if (isNegative && tmp.isPowerOf2()) {
  return isNegative + log;
} else {
  return isNegative + log + 1;
}
542}

544hash_code llvm::hash_value(const APInt &Arg) {
if (Arg.isSingleWord())
  return hash_combine(Arg.BitWidth, Arg.U.VAL);

return hash_combine(
    Arg.BitWidth,
    hash_combine_range(Arg.U.pVal, Arg.U.pVal + Arg.getNumWords()));
551}

553unsigned DenseMapInfo<APInt>::getHashValue(const APInt &Key) {
return static_cast<unsigned>(hash_value(Key));
555}

557bool APInt::isSplat(unsigned SplatSizeInBits) const {
assert(getBitWidth() % SplatSizeInBits == 0 &&((void)0)
       "SplatSizeInBits must divide width!")((void)0);
// We can check that all parts of an integer are equal by making use of a
// little trick: rotate and check if it's still the same value.
return *this == rotl(SplatSizeInBits);
563}

565/// This function returns the high "numBits" bits of this APInt.
566APInt APInt::getHiBits(unsigned numBits) const {
return this->lshr(BitWidth - numBits);
568}

570/// This function returns the low "numBits" bits of this APInt.
571APInt APInt::getLoBits(unsigned numBits) const {
APInt Result(getLowBitsSet(BitWidth, numBits));
Result &= *this;
return Result;
575}

577/// Return a value containing V broadcasted over NewLen bits.
578APInt APInt::getSplat(unsigned NewLen, const APInt &V) {
assert(NewLen >= V.getBitWidth() && "Can't splat to smaller bit width!")((void)0);

APInt Val = V.zextOrSelf(NewLen);
for (unsigned I = V.getBitWidth(); I < NewLen; I <<= 1)
  Val |= Val << I;

return Val;
586}

588unsigned APInt::countLeadingZerosSlowCase() const {
unsigned Count = 0;
for (int i = getNumWords()-1; i >= 0; --i) {
  uint64_t V = U.pVal[i];
  if (V == 0)
    Count += APINT_BITS_PER_WORD;
  else {
    Count += llvm::countLeadingZeros(V);
    break;
  }
}
// Adjust for unused bits in the most significant word (they are zero).
unsigned Mod = BitWidth % APINT_BITS_PER_WORD;
Count -= Mod > 0 ? APINT_BITS_PER_WORD - Mod : 0;
return Count;
603}

605unsigned APInt::countLeadingOnesSlowCase() const {
unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD;
unsigned shift;
if (!highWordBits) {
  highWordBits = APINT_BITS_PER_WORD;
  shift = 0;
} else {
  shift = APINT_BITS_PER_WORD - highWordBits;
}
int i = getNumWords() - 1;
unsigned Count = llvm::countLeadingOnes(U.pVal[i] << shift);
if (Count == highWordBits) {
  for (i--; i >= 0; --i) {
    if (U.pVal[i] == WORDTYPE_MAX)
      Count += APINT_BITS_PER_WORD;
    else {
      Count += llvm::countLeadingOnes(U.pVal[i]);
      break;
    }
  }
}
return Count;
627}

629unsigned APInt::countTrailingZerosSlowCase() const {
unsigned Count = 0;
unsigned i = 0;
for (; i < getNumWords() && U.pVal[i] == 0; ++i)
  Count += APINT_BITS_PER_WORD;
if (i < getNumWords())
  Count += llvm::countTrailingZeros(U.pVal[i]);
return std::min(Count, BitWidth);
637}

639unsigned APInt::countTrailingOnesSlowCase() const {
unsigned Count = 0;
unsigned i = 0;
for (; i < getNumWords() && U.pVal[i] == WORDTYPE_MAX; ++i)
  Count += APINT_BITS_PER_WORD;
if (i < getNumWords())
  Count += llvm::countTrailingOnes(U.pVal[i]);
assert(Count <= BitWidth)((void)0);
return Count;
648}

650unsigned APInt::countPopulationSlowCase() const {
unsigned Count = 0;
for (unsigned i = 0; i < getNumWords(); ++i)
  Count += llvm::countPopulation(U.pVal[i]);
return Count;
655}

657bool APInt::intersectsSlowCase(const APInt &RHS) const {
for (unsigned i = 0, e = getNumWords(); i != e; ++i)
  if ((U.pVal[i] & RHS.U.pVal[i]) != 0)
    return true;

return false;
663}

665bool APInt::isSubsetOfSlowCase(const APInt &RHS) const {
for (unsigned i = 0, e = getNumWords(); i != e; ++i)
  if ((U.pVal[i] & ~RHS.U.pVal[i]) != 0)
    return false;

return true;
671}

673APInt APInt::byteSwap() const {
assert(BitWidth >= 16 && BitWidth % 8 == 0 && "Cannot byteswap!")((void)0);
if (BitWidth == 16)
  return APInt(BitWidth, ByteSwap_16(uint16_t(U.VAL)));
if (BitWidth == 32)
  return APInt(BitWidth, ByteSwap_32(unsigned(U.VAL)));
if (BitWidth <= 64) {
  uint64_t Tmp1 = ByteSwap_64(U.VAL);
  Tmp1 >>= (64 - BitWidth);
  return APInt(BitWidth, Tmp1);
}

APInt Result(getNumWords() * APINT_BITS_PER_WORD, 0);
for (unsigned I = 0, N = getNumWords(); I != N; ++I)
  Result.U.pVal[I] = ByteSwap_64(U.pVal[N - I - 1]);
if (Result.BitWidth != BitWidth) {
  Result.lshrInPlace(Result.BitWidth - BitWidth);
  Result.BitWidth = BitWidth;
}
return Result;
693}

695APInt APInt::reverseBits() const {
switch (BitWidth) {
case 64:
  return APInt(BitWidth, llvm::reverseBits<uint64_t>(U.VAL));
case 32:
  return APInt(BitWidth, llvm::reverseBits<uint32_t>(U.VAL));
case 16:
  return APInt(BitWidth, llvm::reverseBits<uint16_t>(U.VAL));
case 8:
  return APInt(BitWidth, llvm::reverseBits<uint8_t>(U.VAL));
default:
  break;
}

APInt Val(*this);
APInt Reversed(BitWidth, 0);
unsigned S = BitWidth;

for (; Val != 0; Val.lshrInPlace(1)) {
  Reversed <<= 1;
  Reversed |= Val[0];
  --S;
}

Reversed <<= S;
return Reversed;
721}

723APInt llvm::APIntOps::GreatestCommonDivisor(APInt A, APInt B) {
// Fast-path a common case.
if (A == B) return A;

// Corner cases: if either operand is zero, the other is the gcd.
if (!A) return B;
if (!B) return A;

// Count common powers of 2 and remove all other powers of 2.
unsigned Pow2;
{
  unsigned Pow2_A = A.countTrailingZeros();
  unsigned Pow2_B = B.countTrailingZeros();
  if (Pow2_A > Pow2_B) {
    A.lshrInPlace(Pow2_A - Pow2_B);
    Pow2 = Pow2_B;
  } else if (Pow2_B > Pow2_A) {
    B.lshrInPlace(Pow2_B - Pow2_A);
    Pow2 = Pow2_A;
  } else {
    Pow2 = Pow2_A;
  }
}

// Both operands are odd multiples of 2^Pow_2:
//
//   gcd(a, b) = gcd(|a - b| / 2^i, min(a, b))
//
// This is a modified version of Stein's algorithm, taking advantage of
// efficient countTrailingZeros().
while (A != B) {
  if (A.ugt(B)) {
    A -= B;
    A.lshrInPlace(A.countTrailingZeros() - Pow2);
  } else {
    B -= A;
    B.lshrInPlace(B.countTrailingZeros() - Pow2);
  }
}

return A;
764}

766APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) {
uint64_t I = bit_cast<uint64_t>(Double);

// Get the sign bit from the highest order bit
bool isNeg = I >> 63;

// Get the 11-bit exponent and adjust for the 1023 bit bias
int64_t exp = ((I >> 52) & 0x7ff) - 1023;

// If the exponent is negative, the value is < 0 so just return 0.
if (exp < 0)
  return APInt(width, 0u);

// Extract the mantissa by clearing the top 12 bits (sign + exponent).
uint64_t mantissa = (I & (~0ULL >> 12)) | 1ULL << 52;

// If the exponent doesn't shift all bits out of the mantissa
if (exp < 52)
  return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
                  APInt(width, mantissa >> (52 - exp));

// If the client didn't provide enough bits for us to shift the mantissa into
// then the result is undefined, just return 0
if (width <= exp - 52)
  return APInt(width, 0);

// Otherwise, we have to shift the mantissa bits up to the right location
APInt Tmp(width, mantissa);
Tmp <<= (unsigned)exp - 52;
return isNeg ? -Tmp : Tmp;
796}

798/// This function converts this APInt to a double.
799/// The layout for double is as following (IEEE Standard 754):
800///  --------------------------------------
801/// |  Sign    Exponent    Fraction    Bias |
802/// |-------------------------------------- |
803/// |  1[63]   11[62-52]   52[51-00]   1023 |
804///  --------------------------------------
805double APInt::roundToDouble(bool isSigned) const {

// Handle the simple case where the value is contained in one uint64_t.
// It is wrong to optimize getWord(0) to VAL; there might be more than one word.
if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
  if (isSigned) {
    int64_t sext = SignExtend64(getWord(0), BitWidth);
    return double(sext);
  } else
    return double(getWord(0));
}

// Determine if the value is negative.
bool isNeg = isSigned ? (*this)[BitWidth-1] : false;

// Construct the absolute value if we're negative.
APInt Tmp(isNeg ? -(*this) : (*this));

// Figure out how many bits we're using.
unsigned n = Tmp.getActiveBits();

// The exponent (without bias normalization) is just the number of bits
// we are using. Note that the sign bit is gone since we constructed the
// absolute value.
uint64_t exp = n;

// Return infinity for exponent overflow
if (exp > 1023) {
  if (!isSigned || !isNeg)
    return std::numeric_limits<double>::infinity();
  else
    return -std::numeric_limits<double>::infinity();
}
exp += 1023; // Increment for 1023 bias

// Number of bits in mantissa is 52. To obtain the mantissa value, we must
// extract the high 52 bits from the correct words in pVal.
uint64_t mantissa;
unsigned hiWord = whichWord(n-1);
if (hiWord == 0) {
  mantissa = Tmp.U.pVal[0];
  if (n > 52)
    mantissa >>= n - 52; // shift down, we want the top 52 bits.
} else {
  assert(hiWord > 0 && "huh?")((void)0);
  uint64_t hibits = Tmp.U.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
  uint64_t lobits = Tmp.U.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
  mantissa = hibits | lobits;
}

// The leading bit of mantissa is implicit, so get rid of it.
uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
uint64_t I = sign | (exp << 52) | mantissa;
return bit_cast<double>(I);
859}

861// Truncate to new width.
862APInt APInt::trunc(unsigned width) const {
assert(width < BitWidth && "Invalid APInt Truncate request")((void)0);
assert(width && "Can't truncate to 0 bits")((void)0);

if (width <= APINT_BITS_PER_WORD)
  return APInt(width, getRawData()[0]);

APInt Result(getMemory(getNumWords(width)), width);

// Copy full words.
unsigned i;
for (i = 0; i != width / APINT_BITS_PER_WORD; i++)
  Result.U.pVal[i] = U.pVal[i];

// Truncate and copy any partial word.
unsigned bits = (0 - width) % APINT_BITS_PER_WORD;
if (bits != 0)
  Result.U.pVal[i] = U.pVal[i] << bits >> bits;

return Result;
882}

884// Truncate to new width with unsigned saturation.
885APInt APInt::truncUSat(unsigned width) const {
assert(width < BitWidth && "Invalid APInt Truncate request")((void)0);
assert(width && "Can't truncate to 0 bits")((void)0);

// Can we just losslessly truncate it?
if (isIntN(width))
  return trunc(width);
// If not, then just return the new limit.
return APInt::getMaxValue(width);
894}

896// Truncate to new width with signed saturation.
897APInt APInt::truncSSat(unsigned width) const {
assert(width < BitWidth && "Invalid APInt Truncate request")((void)0);
assert(width && "Can't truncate to 0 bits")((void)0);

// Can we just losslessly truncate it?
if (isSignedIntN(width))
  return trunc(width);
// If not, then just return the new limits.
return isNegative() ? APInt::getSignedMinValue(width)
                    : APInt::getSignedMaxValue(width);
907}

909// Sign extend to a new width.
910APInt APInt::sext(unsigned Width) const {
assert(Width > BitWidth && "Invalid APInt SignExtend request")((void)0);

if (Width <= APINT_BITS_PER_WORD)
  return APInt(Width, SignExtend64(U.VAL, BitWidth));

APInt Result(getMemory(getNumWords(Width)), Width);

// Copy words.
std::memcpy(Result.U.pVal, getRawData(), getNumWords() * APINT_WORD_SIZE);

// Sign extend the last word since there may be unused bits in the input.
Result.U.pVal[getNumWords() - 1] =
    SignExtend64(Result.U.pVal[getNumWords() - 1],
                 ((BitWidth - 1) % APINT_BITS_PER_WORD) + 1);

// Fill with sign bits.
std::memset(Result.U.pVal + getNumWords(), isNegative() ? -1 : 0,
            (Result.getNumWords() - getNumWords()) * APINT_WORD_SIZE);
Result.clearUnusedBits();
return Result;
931}

933//  Zero extend to a new width.
934APInt APInt::zext(unsigned width) const {
assert(width > BitWidth && "Invalid APInt ZeroExtend request")((void)0);

if (width <= APINT_BITS_PER_WORD)
  return APInt(width, U.VAL);

APInt Result(getMemory(getNumWords(width)), width);

// Copy words.
std::memcpy(Result.U.pVal, getRawData(), getNumWords() * APINT_WORD_SIZE);

// Zero remaining words.
std::memset(Result.U.pVal + getNumWords(), 0,
            (Result.getNumWords() - getNumWords()) * APINT_WORD_SIZE);

return Result;
950}

952APInt APInt::zextOrTrunc(unsigned width) const {
if (BitWidth < width)
  return zext(width);
if (BitWidth > width)
  return trunc(width);
return *this;
958}

960APInt APInt::sextOrTrunc(unsigned width) const {
if (BitWidth < width)
  return sext(width);
if (BitWidth > width)
  return trunc(width);
return *this;
966}

968APInt APInt::truncOrSelf(unsigned width) const {
if (BitWidth > width)
  return trunc(width);
return *this;
972}

974APInt APInt::zextOrSelf(unsigned width) const {
if (BitWidth < width)
  return zext(width);
return *this;
978}

980APInt APInt::sextOrSelf(unsigned width) const {
if (BitWidth < width)
  return sext(width);
return *this;
984}

986/// Arithmetic right-shift this APInt by shiftAmt.
987/// Arithmetic right-shift function.
988void APInt::ashrInPlace(const APInt &shiftAmt) {
ashrInPlace((unsigned)shiftAmt.getLimitedValue(BitWidth));
990}

992/// Arithmetic right-shift this APInt by shiftAmt.
993/// Arithmetic right-shift function.
994void APInt::ashrSlowCase(unsigned ShiftAmt) {
// Don't bother performing a no-op shift.
if (!ShiftAmt)
  return;

// Save the original sign bit for later.
bool Negative = isNegative();

// WordShift is the inter-part shift; BitShift is intra-part shift.
unsigned WordShift = ShiftAmt / APINT_BITS_PER_WORD;
unsigned BitShift = ShiftAmt % APINT_BITS_PER_WORD;

unsigned WordsToMove = getNumWords() - WordShift;
if (WordsToMove != 0) {
  // Sign extend the last word to fill in the unused bits.
  U.pVal[getNumWords() - 1] = SignExtend64(
      U.pVal[getNumWords() - 1], ((BitWidth - 1) % APINT_BITS_PER_WORD) + 1);

  // Fastpath for moving by whole words.
  if (BitShift == 0) {
    std::memmove(U.pVal, U.pVal + WordShift, WordsToMove * APINT_WORD_SIZE);
  } else {
    // Move the words containing significant bits.
    for (unsigned i = 0; i != WordsToMove - 1; ++i)
      U.pVal[i] = (U.pVal[i + WordShift] >> BitShift) |
                  (U.pVal[i + WordShift + 1] << (APINT_BITS_PER_WORD - BitShift));

    // Handle the last word which has no high bits to copy.
    U.pVal[WordsToMove - 1] = U.pVal[WordShift + WordsToMove - 1] >> BitShift;
    // Sign extend one more time.
    U.pVal[WordsToMove - 1] =
        SignExtend64(U.pVal[WordsToMove - 1], APINT_BITS_PER_WORD - BitShift);
  }
}

// Fill in the remainder based on the original sign.
std::memset(U.pVal + WordsToMove, Negative ? -1 : 0,
            WordShift * APINT_WORD_SIZE);
clearUnusedBits();
1033}

1035/// Logical right-shift this APInt by shiftAmt.
1036/// Logical right-shift function.
1037void APInt::lshrInPlace(const APInt &shiftAmt) {
lshrInPlace((unsigned)shiftAmt.getLimitedValue(BitWidth));
1039}

1041/// Logical right-shift this APInt by shiftAmt.
1042/// Logical right-shift function.
1043void APInt::lshrSlowCase(unsigned ShiftAmt) {
tcShiftRight(U.pVal, getNumWords(), ShiftAmt);
1045}

1047/// Left-shift this APInt by shiftAmt.
1048/// Left-shift function.
1049APInt &APInt::operator<<=(const APInt &shiftAmt) {
// It's undefined behavior in C to shift by BitWidth or greater.
*this <<= (unsigned)shiftAmt.getLimitedValue(BitWidth);
return *this;
1053}

1055void APInt::shlSlowCase(unsigned ShiftAmt) {
tcShiftLeft(U.pVal, getNumWords(), ShiftAmt);
clearUnusedBits();
1058}

1060// Calculate the rotate amount modulo the bit width.
1061static unsigned rotateModulo(unsigned BitWidth, const APInt &rotateAmt) {
unsigned rotBitWidth = rotateAmt.getBitWidth();
APInt rot = rotateAmt;
if (rotBitWidth < BitWidth) {
  // Extend the rotate APInt, so that the urem doesn't divide by 0.
  // e.g. APInt(1, 32) would give APInt(1, 0).
  rot = rotateAmt.zext(BitWidth);
}
rot = rot.urem(APInt(rot.getBitWidth(), BitWidth));
return rot.getLimitedValue(BitWidth);
1071}

1073APInt APInt::rotl(const APInt &rotateAmt) const {
return rotl(rotateModulo(BitWidth, rotateAmt));
1075}

1077APInt APInt::rotl(unsigned rotateAmt) const {
rotateAmt %= BitWidth;
if (rotateAmt == 0)
  return *this;
return shl(rotateAmt) | lshr(BitWidth - rotateAmt);
1082}

1084APInt APInt::rotr(const APInt &rotateAmt) const {
return rotr(rotateModulo(BitWidth, rotateAmt));
1086}

1088APInt APInt::rotr(unsigned rotateAmt) const {
rotateAmt %= BitWidth;
if (rotateAmt == 0)
  return *this;
return lshr(rotateAmt) | shl(BitWidth - rotateAmt);
1093}

1095// Square Root - this method computes and returns the square root of "this".
1096// Three mechanisms are used for computation. For small values (<= 5 bits),
1097// a table lookup is done. This gets some performance for common cases. For
1098// values using less than 52 bits, the value is converted to double and then
1099// the libc sqrt function is called. The result is rounded and then converted
1100// back to a uint64_t which is then used to construct the result. Finally,
1101// the Babylonian method for computing square roots is used.
1102APInt APInt::sqrt() const {

// Determine the magnitude of the value.
unsigned magnitude = getActiveBits();

// Use a fast table for some small values. This also gets rid of some
// rounding errors in libc sqrt for small values.
if (magnitude <= 5) {
  static const uint8_t results[32] = {
    /*     0 */ 0,
    /*  1- 2 */ 1, 1,
    /*  3- 6 */ 2, 2, 2, 2,
    /*  7-12 */ 3, 3, 3, 3, 3, 3,
    /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
    /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
    /*    31 */ 6
  };
  return APInt(BitWidth, results[ (isSingleWord() ? U.VAL : U.pVal[0]) ]);
}

// If the magnitude of the value fits in less than 52 bits (the precision of
// an IEEE double precision floating point value), then we can use the
// libc sqrt function which will probably use a hardware sqrt computation.
// This should be faster than the algorithm below.
if (magnitude < 52) {
  return APInt(BitWidth,
               uint64_t(::round(::sqrt(double(isSingleWord() ? U.VAL
                                                             : U.pVal[0])))));
}

// Okay, all the short cuts are exhausted. We must compute it. The following
// is a classical Babylonian method for computing the square root. This code
// was adapted to APInt from a wikipedia article on such computations.
// See http://www.wikipedia.org/ and go to the page named
// Calculate_an_integer_square_root.
unsigned nbits = BitWidth, i = 4;
APInt testy(BitWidth, 16);
APInt x_old(BitWidth, 1);
APInt x_new(BitWidth, 0);
APInt two(BitWidth, 2);

// Select a good starting value using binary logarithms.
for (;; i += 2, testy = testy.shl(2))
  if (i >= nbits || this->ule(testy)) {
    x_old = x_old.shl(i / 2);
    break;
  }

// Use the Babylonian method to arrive at the integer square root:
for (;;) {
  x_new = (this->udiv(x_old) + x_old).udiv(two);
  if (x_old.ule(x_new))
    break;
  x_old = x_new;
}

// Make sure we return the closest approximation
// NOTE: The rounding calculation below is correct. It will produce an
// off-by-one discrepancy with results from pari/gp. That discrepancy has been
// determined to be a rounding issue with pari/gp as it begins to use a
// floating point representation after 192 bits. There are no discrepancies
// between this algorithm and pari/gp for bit widths < 192 bits.
APInt square(x_old * x_old);
APInt nextSquare((x_old + 1) * (x_old +1));
if (this->ult(square))
  return x_old;
assert(this->ule(nextSquare) && "Error in APInt::sqrt computation")((void)0);
APInt midpoint((nextSquare - square).udiv(two));
APInt offset(*this - square);
if (offset.ult(midpoint))
  return x_old;
return x_old + 1;
1174}

1176/// Computes the multiplicative inverse of this APInt for a given modulo. The
1177/// iterative extended Euclidean algorithm is used to solve for this value,
1178/// however we simplify it to speed up calculating only the inverse, and take
1179/// advantage of div+rem calculations. We also use some tricks to avoid copying
1180/// (potentially large) APInts around.
1181/// WARNING: a value of '0' may be returned,
1182///          signifying that no multiplicative inverse exists!
1183APInt APInt::multiplicativeInverse(const APInt& modulo) const {
assert(ult(modulo) && "This APInt must be smaller than the modulo")((void)0);

// Using the properties listed at the following web page (accessed 06/21/08):
//   http://www.numbertheory.org/php/euclid.html
// (especially the properties numbered 3, 4 and 9) it can be proved that
// BitWidth bits suffice for all the computations in the algorithm implemented
// below. More precisely, this number of bits suffice if the multiplicative
// inverse exists, but may not suffice for the general extended Euclidean
// algorithm.

APInt r[2] = { modulo, *this };
APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) };
APInt q(BitWidth, 0);

unsigned i;
for (i = 0; r[i^1] != 0; i ^= 1) {
  // An overview of the math without the confusing bit-flipping:
  // q = r[i-2] / r[i-1]
  // r[i] = r[i-2] % r[i-1]
  // t[i] = t[i-2] - t[i-1] * q
  udivrem(r[i], r[i^1], q, r[i]);
  t[i] -= t[i^1] * q;
}

// If this APInt and the modulo are not coprime, there is no multiplicative
// inverse, so return 0. We check this by looking at the next-to-last
// remainder, which is the gcd(*this,modulo) as calculated by the Euclidean
// algorithm.
if (r[i] != 1)
  return APInt(BitWidth, 0);

// The next-to-last t is the multiplicative inverse.  However, we are
// interested in a positive inverse. Calculate a positive one from a negative
// one if necessary. A simple addition of the modulo suffices because
// abs(t[i]) is known to be less than *this/2 (see the link above).
if (t[i].isNegative())
  t[i] += modulo;

return std::move(t[i]);
1223}

1225/// Calculate the magic numbers required to implement a signed integer division
1226/// by a constant as a sequence of multiplies, adds and shifts.  Requires that
1227/// the divisor not be 0, 1, or -1.  Taken from "Hacker's Delight", Henry S.
1228/// Warren, Jr., chapter 10.
1229APInt::ms APInt::magic() const {
const APInt& d = *this;
unsigned p;
APInt ad, anc, delta, q1, r1, q2, r2, t;
APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
struct ms mag;

ad = d.abs();
t = signedMin + (d.lshr(d.getBitWidth() - 1));
anc = t - 1 - t.urem(ad);   // absolute value of nc
p = d.getBitWidth() - 1;    // initialize p
q1 = signedMin.udiv(anc);   // initialize q1 = 2p/abs(nc)
r1 = signedMin - q1*anc;    // initialize r1 = rem(2p,abs(nc))
q2 = signedMin.udiv(ad);    // initialize q2 = 2p/abs(d)
r2 = signedMin - q2*ad;     // initialize r2 = rem(2p,abs(d))
do {
  p = p + 1;
  q1 = q1<<1;          // update q1 = 2p/abs(nc)
  r1 = r1<<1;          // update r1 = rem(2p/abs(nc))
  if (r1.uge(anc)) {  // must be unsigned comparison
    q1 = q1 + 1;
    r1 = r1 - anc;
  }
  q2 = q2<<1;          // update q2 = 2p/abs(d)
  r2 = r2<<1;          // update r2 = rem(2p/abs(d))
  if (r2.uge(ad)) {   // must be unsigned comparison
    q2 = q2 + 1;
    r2 = r2 - ad;
  }
  delta = ad - r2;
} while (q1.ult(delta) || (q1 == delta && r1 == 0));

mag.m = q2 + 1;
if (d.isNegative()) mag.m = -mag.m;   // resulting magic number
mag.s = p - d.getBitWidth();          // resulting shift
return mag;
1265}

1267/// Calculate the magic numbers required to implement an unsigned integer
1268/// division by a constant as a sequence of multiplies, adds and shifts.
1269/// Requires that the divisor not be 0.  Taken from "Hacker's Delight", Henry
1270/// S. Warren, Jr., chapter 10.
1271/// LeadingZeros can be used to simplify the calculation if the upper bits
1272/// of the divided value are known zero.
1273APInt::mu APInt::magicu(unsigned LeadingZeros) const {
const APInt& d = *this;
unsigned p;
APInt nc, delta, q1, r1, q2, r2;
struct mu magu;
magu.a = 0;               // initialize "add" indicator
APInt allOnes = APInt::getAllOnesValue(d.getBitWidth()).lshr(LeadingZeros);
APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());

nc = allOnes - (allOnes - d).urem(d);
p = d.getBitWidth() - 1;  // initialize p
q1 = signedMin.udiv(nc);  // initialize q1 = 2p/nc
r1 = signedMin - q1*nc;   // initialize r1 = rem(2p,nc)
q2 = signedMax.udiv(d);   // initialize q2 = (2p-1)/d
r2 = signedMax - q2*d;    // initialize r2 = rem((2p-1),d)
do {
  p = p + 1;
  if (r1.uge(nc - r1)) {
    q1 = q1 + q1 + 1;  // update q1
    r1 = r1 + r1 - nc; // update r1
  }
  else {
    q1 = q1+q1; // update q1
    r1 = r1+r1; // update r1
  }
  if ((r2 + 1).uge(d - r2)) {
    if (q2.uge(signedMax)) magu.a = 1;
    q2 = q2+q2 + 1;     // update q2
    r2 = r2+r2 + 1 - d; // update r2
  }
  else {
    if (q2.uge(signedMin)) magu.a = 1;
    q2 = q2+q2;     // update q2
    r2 = r2+r2 + 1; // update r2
  }
  delta = d - 1 - r2;
} while (p < d.getBitWidth()*2 &&
         (q1.ult(delta) || (q1 == delta && r1 == 0)));
magu.m = q2 + 1; // resulting magic number
magu.s = p - d.getBitWidth();  // resulting shift
return magu;
1315}

1317/// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
1318/// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
1319/// variables here have the same names as in the algorithm. Comments explain
1320/// the algorithm and any deviation from it.
1321static void KnuthDiv(uint32_t *u, uint32_t *v, uint32_t *q, uint32_t* r,
                   unsigned m, unsigned n) {
assert(u && "Must provide dividend")((void)0);
assert(v && "Must provide divisor")((void)0);
assert(q && "Must provide quotient")((void)0);
assert(u != v && u != q && v != q && "Must use different memory")((void)0);
assert(n>1 && "n must be > 1")((void)0);

// b denotes the base of the number system. In our case b is 2^32.
const uint64_t b = uint64_t(1) << 32;

1332// The DEBUG macros here tend to be spam in the debug output if you're not
1333// debugging this code. Disable them unless KNUTH_DEBUG is defined.
1334#ifdef KNUTH_DEBUG
1335#define DEBUG_KNUTH(X)do {} while(false) LLVM_DEBUG(X)do { } while (false)
1336#else
1337#define DEBUG_KNUTH(X)do {} while(false) do {} while(false)
1338#endif

DEBUG_KNUTH(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n')do {} while(false);
DEBUG_KNUTH(dbgs() << "KnuthDiv: original:")do {} while(false);
DEBUG_KNUTH(for (int i = m + n; i >= 0; i--) dbgs() << " " << u[i])do {} while(false);
DEBUG_KNUTH(dbgs() << " by")do {} while(false);
DEBUG_KNUTH(for (int i = n; i > 0; i--) dbgs() << " " << v[i - 1])do {} while(false);
DEBUG_KNUTH(dbgs() << '\n')do {} while(false);
// D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of
// u and v by d. Note that we have taken Knuth's advice here to use a power
// of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
// 2 allows us to shift instead of multiply and it is easy to determine the
// shift amount from the leading zeros.  We are basically normalizing the u
// and v so that its high bits are shifted to the top of v's range without
// overflow. Note that this can require an extra word in u so that u must
// be of length m+n+1.
unsigned shift = countLeadingZeros(v[n-1]);
uint32_t v_carry = 0;
uint32_t u_carry = 0;
if (shift) {
  for (unsigned i = 0; i < m+n; ++i) {
    uint32_t u_tmp = u[i] >> (32 - shift);
    u[i] = (u[i] << shift) | u_carry;
    u_carry = u_tmp;
  }
  for (unsigned i = 0; i < n; ++i) {
    uint32_t v_tmp = v[i] >> (32 - shift);
    v[i] = (v[i] << shift) | v_carry;
    v_carry = v_tmp;
  }
}
u[m+n] = u_carry;

DEBUG_KNUTH(dbgs() << "KnuthDiv:   normal:")do {} while(false);
DEBUG_KNUTH(for (int i = m + n; i >= 0; i--) dbgs() << " " << u[i])do {} while(false);
DEBUG_KNUTH(dbgs() << " by")do {} while(false);
DEBUG_KNUTH(for (int i = n; i > 0; i--) dbgs() << " " << v[i - 1])do {} while(false);
DEBUG_KNUTH(dbgs() << '\n')do {} while(false);

// D2. [Initialize j.]  Set j to m. This is the loop counter over the places.
int j = m;
do {
  DEBUG_KNUTH(dbgs() << "KnuthDiv: quotient digit #" << j << '\n')do {} while(false);
  // D3. [Calculate q'.].
  //     Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
  //     Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
  // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
  // qp by 1, increase rp by v[n-1], and repeat this test if rp < b. The test
  // on v[n-2] determines at high speed most of the cases in which the trial
  // value qp is one too large, and it eliminates all cases where qp is two
  // too large.
  uint64_t dividend = Make_64(u[j+n], u[j+n-1]);
  DEBUG_KNUTH(dbgs() << "KnuthDiv: dividend == " << dividend << '\n')do {} while(false);
  uint64_t qp = dividend / v[n-1];
  uint64_t rp = dividend % v[n-1];
  if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
    qp--;
    rp += v[n-1];
    if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
      qp--;
  }
  DEBUG_KNUTH(dbgs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n')do {} while(false);

  // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
  // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
  // consists of a simple multiplication by a one-place number, combined with
  // a subtraction.
  // The digits (u[j+n]...u[j]) should be kept positive; if the result of
  // this step is actually negative, (u[j+n]...u[j]) should be left as the
  // true value plus b**(n+1), namely as the b's complement of
  // the true value, and a "borrow" to the left should be remembered.
  int64_t borrow = 0;
  for (unsigned i = 0; i < n; ++i) {
    uint64_t p = uint64_t(qp) * uint64_t(v[i]);
    int64_t subres = int64_t(u[j+i]) - borrow - Lo_32(p);
    u[j+i] = Lo_32(subres);
    borrow = Hi_32(p) - Hi_32(subres);
    DEBUG_KNUTH(dbgs() << "KnuthDiv: u[j+i] = " << u[j + i]do {} while(false)
                      << ", borrow = " << borrow << '\n')do {} while(false);
  }
  bool isNeg = u[j+n] < borrow;
  u[j+n] -= Lo_32(borrow);

  DEBUG_KNUTH(dbgs() << "KnuthDiv: after subtraction:")do {} while(false);
  DEBUG_KNUTH(for (int i = m + n; i >= 0; i--) dbgs() << " " << u[i])do {} while(false);
  DEBUG_KNUTH(dbgs() << '\n')do {} while(false);

  // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
  // negative, go to step D6; otherwise go on to step D7.
  q[j] = Lo_32(qp);
  if (isNeg) {
    // D6. [Add back]. The probability that this step is necessary is very
    // small, on the order of only 2/b. Make sure that test data accounts for
    // this possibility. Decrease q[j] by 1
    q[j]--;
    // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
    // A carry will occur to the left of u[j+n], and it should be ignored
    // since it cancels with the borrow that occurred in D4.
    bool carry = false;
    for (unsigned i = 0; i < n; i++) {
      uint32_t limit = std::min(u[j+i],v[i]);
      u[j+i] += v[i] + carry;
      carry = u[j+i] < limit || (carry && u[j+i] == limit);
    }
    u[j+n] += carry;
  }
  DEBUG_KNUTH(dbgs() << "KnuthDiv: after correction:")do {} while(false);
  DEBUG_KNUTH(for (int i = m + n; i >= 0; i--) dbgs() << " " << u[i])do {} while(false);
  DEBUG_KNUTH(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n')do {} while(false);

  // D7. [Loop on j.]  Decrease j by one. Now if j >= 0, go back to D3.
} while (--j >= 0);

DEBUG_KNUTH(dbgs() << "KnuthDiv: quotient:")do {} while(false);
DEBUG_KNUTH(for (int i = m; i >= 0; i--) dbgs() << " " << q[i])do {} while(false);
DEBUG_KNUTH(dbgs() << '\n')do {} while(false);

// D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
// remainder may be obtained by dividing u[...] by d. If r is non-null we
// compute the remainder (urem uses this).
if (r) {
  // The value d is expressed by the "shift" value above since we avoided
  // multiplication by d by using a shift left. So, all we have to do is
  // shift right here.
  if (shift) {
    uint32_t carry = 0;
    DEBUG_KNUTH(dbgs() << "KnuthDiv: remainder:")do {} while(false);
    for (int i = n-1; i >= 0; i--) {
      r[i] = (u[i] >> shift) | carry;
      carry = u[i] << (32 - shift);
      DEBUG_KNUTH(dbgs() << " " << r[i])do {} while(false);
    }
  } else {
    for (int i = n-1; i >= 0; i--) {
      r[i] = u[i];
      DEBUG_KNUTH(dbgs() << " " << r[i])do {} while(false);
    }
  }
  DEBUG_KNUTH(dbgs() << '\n')do {} while(false);
}
DEBUG_KNUTH(dbgs() << '\n')do {} while(false);
1479}

1481void APInt::divide(const WordType *LHS, unsigned lhsWords, const WordType *RHS,
                 unsigned rhsWords, WordType *Quotient, WordType *Remainder) {
assert(lhsWords >= rhsWords && "Fractional result")((void)0);

// First, compose the values into an array of 32-bit words instead of
// 64-bit words. This is a necessity of both the "short division" algorithm
// and the Knuth "classical algorithm" which requires there to be native
// operations for +, -, and * on an m bit value with an m*2 bit result. We
// can't use 64-bit operands here because we don't have native results of
// 128-bits. Furthermore, casting the 64-bit values to 32-bit values won't
// work on large-endian machines.
unsigned n = rhsWords * 2;
unsigned m = (lhsWords * 2) - n;

// Allocate space for the temporary values we need either on the stack, if
// it will fit, or on the heap if it won't.
uint32_t SPACE[128];
uint32_t *U = nullptr;
uint32_t *V = nullptr;
uint32_t *Q = nullptr;
uint32_t *R = nullptr;
if ((Remainder?4:3)*n+2*m+1 <= 128) {
  U = &SPACE[0];
  V = &SPACE[m+n+1];
  Q = &SPACE[(m+n+1) + n];
  if (Remainder)
    R = &SPACE[(m+n+1) + n + (m+n)];
} else {
  U = new uint32_t[m + n + 1];
  V = new uint32_t[n];
  Q = new uint32_t[m+n];
  if (Remainder)
    R = new uint32_t[n];
}

// Initialize the dividend
memset(U, 0, (m+n+1)*sizeof(uint32_t));
for (unsigned i = 0; i < lhsWords; ++i) {
  uint64_t tmp = LHS[i];
  U[i * 2] = Lo_32(tmp);
  U[i * 2 + 1] = Hi_32(tmp);
}
U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.

// Initialize the divisor
memset(V, 0, (n)*sizeof(uint32_t));
for (unsigned i = 0; i < rhsWords; ++i) {
  uint64_t tmp = RHS[i];
  V[i * 2] = Lo_32(tmp);
  V[i * 2 + 1] = Hi_32(tmp);
}

// initialize the quotient and remainder
memset(Q, 0, (m+n) * sizeof(uint32_t));
if (Remainder)
  memset(R, 0, n * sizeof(uint32_t));

// Now, adjust m and n for the Knuth division. n is the number of words in
// the divisor. m is the number of words by which the dividend exceeds the
// divisor (i.e. m+n is the length of the dividend). These sizes must not
// contain any zero words or the Knuth algorithm fails.
for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
  n--;
  m++;
}
for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
  m--;

// If we're left with only a single word for the divisor, Knuth doesn't work
// so we implement the short division algorithm here. This is much simpler
// and faster because we are certain that we can divide a 64-bit quantity
// by a 32-bit quantity at hardware speed and short division is simply a
// series of such operations. This is just like doing short division but we
// are using base 2^32 instead of base 10.
assert(n != 0 && "Divide by zero?")((void)0);
if (n == 1) {
  uint32_t divisor = V[0];
  uint32_t remainder = 0;
  for (int i = m; i >= 0; i--) {
    uint64_t partial_dividend = Make_64(remainder, U[i]);
    if (partial_dividend == 0) {
      Q[i] = 0;
      remainder = 0;
    } else if (partial_dividend < divisor) {
      Q[i] = 0;
      remainder = Lo_32(partial_dividend);
    } else if (partial_dividend == divisor) {
      Q[i] = 1;
      remainder = 0;
    } else {
      Q[i] = Lo_32(partial_dividend / divisor);
      remainder = Lo_32(partial_dividend - (Q[i] * divisor));
    }
  }
  if (R)
    R[0] = remainder;
} else {
  // Now we're ready to invoke the Knuth classical divide algorithm. In this
  // case n > 1.
  KnuthDiv(U, V, Q, R, m, n);
}

// If the caller wants the quotient
if (Quotient) {
  for (unsigned i = 0; i < lhsWords; ++i)
    Quotient[i] = Make_64(Q[i*2+1], Q[i*2]);
}

// If the caller wants the remainder
if (Remainder) {
  for (unsigned i = 0; i < rhsWords; ++i)
    Remainder[i] = Make_64(R[i*2+1], R[i*2]);
}

// Clean up the memory we allocated.
if (U != &SPACE[0]) {
  delete [] U;
  delete [] V;
  delete [] Q;
  delete [] R;
}
1602}

1604APInt APInt::udiv(const APInt &RHS) const {
assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")((void)0);

// First, deal with the easy case
if (isSingleWord()) {
  assert(RHS.U.VAL != 0 && "Divide by zero?")((void)0);
  return APInt(BitWidth, U.VAL / RHS.U.VAL);
}

// Get some facts about the LHS and RHS number of bits and words
unsigned lhsWords = getNumWords(getActiveBits());
unsigned rhsBits  = RHS.getActiveBits();
unsigned rhsWords = getNumWords(rhsBits);
assert(rhsWords && "Divided by zero???")((void)0);

// Deal with some degenerate cases
if (!lhsWords)
  // 0 / X ===> 0
  return APInt(BitWidth, 0);
if (rhsBits == 1)
  // X / 1 ===> X
  return *this;
if (lhsWords < rhsWords || this->ult(RHS))
  // X / Y ===> 0, iff X < Y
  return APInt(BitWidth, 0);
if (*this == RHS)
  // X / X ===> 1
  return APInt(BitWidth, 1);
if (lhsWords == 1) // rhsWords is 1 if lhsWords is 1.
  // All high words are zero, just use native divide
  return APInt(BitWidth, this->U.pVal[0] / RHS.U.pVal[0]);

// We have to compute it the hard way. Invoke the Knuth divide algorithm.
APInt Quotient(BitWidth, 0); // to hold result.
divide(U.pVal, lhsWords, RHS.U.pVal, rhsWords, Quotient.U.pVal, nullptr);
return Quotient;
1640}

1642APInt APInt::udiv(uint64_t RHS) const {
assert(RHS != 0 && "Divide by zero?")((void)0);

// First, deal with the easy case
if (isSingleWord())
  return APInt(BitWidth, U.VAL / RHS);

// Get some facts about the LHS words.
unsigned lhsWords = getNumWords(getActiveBits());

// Deal with some degenerate cases
if (!lhsWords)
  // 0 / X ===> 0
  return APInt(BitWidth, 0);
if (RHS == 1)
  // X / 1 ===> X
  return *this;
if (this->ult(RHS))
  // X / Y ===> 0, iff X < Y
  return APInt(BitWidth, 0);
if (*this == RHS)
  // X / X ===> 1
  return APInt(BitWidth, 1);
if (lhsWords == 1) // rhsWords is 1 if lhsWords is 1.
  // All high words are zero, just use native divide
  return APInt(BitWidth, this->U.pVal[0] / RHS);

// We have to compute it the hard way. Invoke the Knuth divide algorithm.
APInt Quotient(BitWidth, 0); // to hold result.
divide(U.pVal, lhsWords, &RHS, 1, Quotient.U.pVal, nullptr);
return Quotient;
1673}

1675APInt APInt::sdiv(const APInt &RHS) const {
if (isNegative()) {
  if (RHS.isNegative())
    return (-(*this)).udiv(-RHS);
  return -((-(*this)).udiv(RHS));
}
if (RHS.isNegative())
  return -(this->udiv(-RHS));
return this->udiv(RHS);
1684}

1686APInt APInt::sdiv(int64_t RHS) const {
if (isNegative()) {
  if (RHS < 0)
    return (-(*this)).udiv(-RHS);
  return -((-(*this)).udiv(RHS));
}
if (RHS < 0)
  return -(this->udiv(-RHS));
return this->udiv(RHS);
1695}

1697APInt APInt::urem(const APInt &RHS) const {
assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")((void)0);
if (isSingleWord()) {
  assert(RHS.U.VAL != 0 && "Remainder by zero?")((void)0);
  return APInt(BitWidth, U.VAL % RHS.U.VAL);
}

// Get some facts about the LHS
unsigned lhsWords = getNumWords(getActiveBits());

// Get some facts about the RHS
unsigned rhsBits = RHS.getActiveBits();
unsigned rhsWords = getNumWords(rhsBits);
assert(rhsWords && "Performing remainder operation by zero ???")((void)0);

// Check the degenerate cases
if (lhsWords == 0)
  // 0 % Y ===> 0
  return APInt(BitWidth, 0);
if (rhsBits == 1)
  // X % 1 ===> 0
  return APInt(BitWidth, 0);
if (lhsWords < rhsWords || this->ult(RHS))
  // X % Y ===> X, iff X < Y
  return *this;
if (*this == RHS)
  // X % X == 0;
  return APInt(BitWidth, 0);
if (lhsWords == 1)
  // All high words are zero, just use native remainder
  return APInt(BitWidth, U.pVal[0] % RHS.U.pVal[0]);

// We have to compute it the hard way. Invoke the Knuth divide algorithm.
APInt Remainder(BitWidth, 0);
divide(U.pVal, lhsWords, RHS.U.pVal, rhsWords, nullptr, Remainder.U.pVal);
return Remainder;
1733}

1735uint64_t APInt::urem(uint64_t RHS) const {
assert(RHS != 0 && "Remainder by zero?")((void)0);

if (isSingleWord())
  return U.VAL % RHS;

// Get some facts about the LHS
unsigned lhsWords = getNumWords(getActiveBits());

// Check the degenerate cases
if (lhsWords == 0)
  // 0 % Y ===> 0
  return 0;
if (RHS == 1)
  // X % 1 ===> 0
  return 0;
if (this->ult(RHS))
  // X % Y ===> X, iff X < Y
  return getZExtValue();
if (*this == RHS)
  // X % X == 0;
  return 0;
if (lhsWords == 1)
  // All high words are zero, just use native remainder
  return U.pVal[0] % RHS;

// We have to compute it the hard way. Invoke the Knuth divide algorithm.
uint64_t Remainder;
divide(U.pVal, lhsWords, &RHS, 1, nullptr, &Remainder);
return Remainder;
1765}

1767APInt APInt::srem(const APInt &RHS) const {
if (isNegative()) {
  if (RHS.isNegative())
    return -((-(*this)).urem(-RHS));
  return -((-(*this)).urem(RHS));
}
if (RHS.isNegative())
  return this->urem(-RHS);
return this->urem(RHS);
1776}

1778int64_t APInt::srem(int64_t RHS) const {
if (isNegative()) {
  if (RHS < 0)
    return -((-(*this)).urem(-RHS));
  return -((-(*this)).urem(RHS));
}
if (RHS < 0)
  return this->urem(-RHS);
return this->urem(RHS);
1787}

1789void APInt::udivrem(const APInt &LHS, const APInt &RHS,
                  APInt &Quotient, APInt &Remainder) {
assert(LHS.BitWidth == RHS.BitWidth && "Bit widths must be the same")((void)0);
unsigned BitWidth = LHS.BitWidth;

// First, deal with the easy case
if (LHS.isSingleWord()) {
8
←
Taking false branch→
  assert(RHS.U.VAL != 0 && "Divide by zero?")((void)0);
  uint64_t QuotVal = LHS.U.VAL / RHS.U.VAL;
  uint64_t RemVal = LHS.U.VAL % RHS.U.VAL;
  Quotient = APInt(BitWidth, QuotVal);
  Remainder = APInt(BitWidth, RemVal);
  return;
}

// Get some size facts about the dividend and divisor
unsigned lhsWords = getNumWords(LHS.getActiveBits());
unsigned rhsBits  = RHS.getActiveBits();
unsigned rhsWords = getNumWords(rhsBits);
assert(rhsWords && "Performing divrem operation by zero ???")((void)0);

// Check the degenerate cases
if (lhsWords == 0) {
9
←
Assuming 'lhsWords' is not equal to 0→
10
←
Taking false branch→
  Quotient = APInt(BitWidth, 0);    // 0 / Y ===> 0
  Remainder = APInt(BitWidth, 0);   // 0 % Y ===> 0
  return;
}

if (rhsBits == 1) {
11
←
Assuming 'rhsBits' is not equal to 1→
12
←
Taking false branch→
  Quotient = LHS;                   // X / 1 ===> X
  Remainder = APInt(BitWidth, 0);   // X % 1 ===> 0
}

if (lhsWords < rhsWords || LHS.ult(RHS)) {
13
←
Assuming 'lhsWords' is >= 'rhsWords'→
14
←
Taking false branch→
  Remainder = LHS;                  // X % Y ===> X, iff X < Y
  Quotient = APInt(BitWidth, 0);    // X / Y ===> 0, iff X < Y
  return;
}

if (LHS == RHS) {
15
←
Assuming the condition is false→
16
←
Taking false branch→
  Quotient  = APInt(BitWidth, 1);   // X / X ===> 1
  Remainder = APInt(BitWidth, 0);   // X % X ===> 0;
  return;
}

// Make sure there is enough space to hold the results.
// NOTE: This assumes that reallocate won't affect any bits if it doesn't
// change the size. This is necessary if Quotient or Remainder is aliased
// with LHS or RHS.
Quotient.reallocate(BitWidth);
17
←
Calling 'APInt::reallocate'→
24
←
Returned allocated memory→
Remainder.reallocate(BitWidth);

if (lhsWords == 1) { // rhsWords is 1 if lhsWords is 1.
25
←
Assuming 'lhsWords' is equal to 1→
26
←
Taking true branch→
  // There is only one word to consider so use the native versions.
  uint64_t lhsValue = LHS.U.pVal[0];
  uint64_t rhsValue = RHS.U.pVal[0];
  Quotient = lhsValue / rhsValue;
27
←
Calling 'APInt::operator='→
  Remainder = lhsValue % rhsValue;
  return;
}

// Okay, lets do it the long way
divide(LHS.U.pVal, lhsWords, RHS.U.pVal, rhsWords, Quotient.U.pVal,
       Remainder.U.pVal);
// Clear the rest of the Quotient and Remainder.
std::memset(Quotient.U.pVal + lhsWords, 0,
            (getNumWords(BitWidth) - lhsWords) * APINT_WORD_SIZE);
std::memset(Remainder.U.pVal + rhsWords, 0,
            (getNumWords(BitWidth) - rhsWords) * APINT_WORD_SIZE);
1858}

1860void APInt::udivrem(const APInt &LHS, uint64_t RHS, APInt &Quotient,
                  uint64_t &Remainder) {
assert(RHS != 0 && "Divide by zero?")((void)0);
unsigned BitWidth = LHS.BitWidth;

// First, deal with the easy case
if (LHS.isSingleWord()) {
  uint64_t QuotVal = LHS.U.VAL / RHS;
  Remainder = LHS.U.VAL % RHS;
  Quotient = APInt(BitWidth, QuotVal);
  return;
}

// Get some size facts about the dividend and divisor
unsigned lhsWords = getNumWords(LHS.getActiveBits());

// Check the degenerate cases
if (lhsWords == 0) {
  Quotient = APInt(BitWidth, 0);    // 0 / Y ===> 0
  Remainder = 0;                    // 0 % Y ===> 0
  return;
}

if (RHS == 1) {
  Quotient = LHS;                   // X / 1 ===> X
  Remainder = 0;                    // X % 1 ===> 0
  return;
}

if (LHS.ult(RHS)) {
  Remainder = LHS.getZExtValue();   // X % Y ===> X, iff X < Y
  Quotient = APInt(BitWidth, 0);    // X / Y ===> 0, iff X < Y
  return;
}

if (LHS == RHS) {
  Quotient  = APInt(BitWidth, 1);   // X / X ===> 1
  Remainder = 0;                    // X % X ===> 0;
  return;
}

// Make sure there is enough space to hold the results.
// NOTE: This assumes that reallocate won't affect any bits if it doesn't
// change the size. This is necessary if Quotient is aliased with LHS.
Quotient.reallocate(BitWidth);

if (lhsWords == 1) { // rhsWords is 1 if lhsWords is 1.
  // There is only one word to consider so use the native versions.
  uint64_t lhsValue = LHS.U.pVal[0];
  Quotient = lhsValue / RHS;
  Remainder = lhsValue % RHS;
  return;
}

// Okay, lets do it the long way
divide(LHS.U.pVal, lhsWords, &RHS, 1, Quotient.U.pVal, &Remainder);
// Clear the rest of the Quotient.
std::memset(Quotient.U.pVal + lhsWords, 0,
            (getNumWords(BitWidth) - lhsWords) * APINT_WORD_SIZE);
1919}

1921void APInt::sdivrem(const APInt &LHS, const APInt &RHS,
                  APInt &Quotient, APInt &Remainder) {
if (LHS.isNegative()) {
3
←
Assuming the condition is false→
4
←
Taking false branch→
  if (RHS.isNegative())
    APInt::udivrem(-LHS, -RHS, Quotient, Remainder);
  else {
    APInt::udivrem(-LHS, RHS, Quotient, Remainder);
    Quotient.negate();
  }
  Remainder.negate();
} else if (RHS.isNegative()) {
5
←
Assuming the condition is false→
6
←
Taking false branch→
  APInt::udivrem(LHS, -RHS, Quotient, Remainder);
  Quotient.negate();
} else {
  APInt::udivrem(LHS, RHS, Quotient, Remainder);
7
←
Calling 'APInt::udivrem'→
}
1937}

1939void APInt::sdivrem(const APInt &LHS, int64_t RHS,
                  APInt &Quotient, int64_t &Remainder) {
uint64_t R = Remainder;
if (LHS.isNegative()) {
  if (RHS < 0)
    APInt::udivrem(-LHS, -RHS, Quotient, R);
  else {
    APInt::udivrem(-LHS, RHS, Quotient, R);
    Quotient.negate();
  }
  R = -R;
} else if (RHS < 0) {
  APInt::udivrem(LHS, -RHS, Quotient, R);
  Quotient.negate();
} else {
  APInt::udivrem(LHS, RHS, Quotient, R);
}
Remainder = R;
1957}

1959APInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const {
APInt Res = *this+RHS;
Overflow = isNonNegative() == RHS.isNonNegative() &&
           Res.isNonNegative() != isNonNegative();
return Res;
1964}

1966APInt APInt::uadd_ov(const APInt &RHS, bool &Overflow) const {
APInt Res = *this+RHS;
Overflow = Res.ult(RHS);
return Res;
1970}

1972APInt APInt::ssub_ov(const APInt &RHS, bool &Overflow) const {
APInt Res = *this - RHS;
Overflow = isNonNegative() != RHS.isNonNegative() &&
           Res.isNonNegative() != isNonNegative();
return Res;
1977}

1979APInt APInt::usub_ov(const APInt &RHS, bool &Overflow) const {
APInt Res = *this-RHS;
Overflow = Res.ugt(*this);
return Res;
1983}

1985APInt APInt::sdiv_ov(const APInt &RHS, bool &Overflow) const {
// MININT/-1  -->  overflow.
Overflow = isMinSignedValue() && RHS.isAllOnesValue();
return sdiv(RHS);
1989}

1991APInt APInt::smul_ov(const APInt &RHS, bool &Overflow) const {
APInt Res = *this * RHS;

if (*this != 0 && RHS != 0)
  Overflow = Res.sdiv(RHS) != *this || Res.sdiv(*this) != RHS;
else
  Overflow = false;
return Res;
1999}

2001APInt APInt::umul_ov(const APInt &RHS, bool &Overflow) const {
if (countLeadingZeros() + RHS.countLeadingZeros() + 2 <= BitWidth) {
  Overflow = true;
  return *this * RHS;
}

APInt Res = lshr(1) * RHS;
Overflow = Res.isNegative();
Res <<= 1;
if ((*this)[0]) {
  Res += RHS;
  if (Res.ult(RHS))
    Overflow = true;
}
return Res;
2016}

2018APInt APInt::sshl_ov(const APInt &ShAmt, bool &Overflow) const {
Overflow = ShAmt.uge(getBitWidth());
if (Overflow)
  return APInt(BitWidth, 0);

if (isNonNegative()) // Don't allow sign change.
  Overflow = ShAmt.uge(countLeadingZeros());
else
  Overflow = ShAmt.uge(countLeadingOnes());

return *this << ShAmt;
2029}

2031APInt APInt::ushl_ov(const APInt &ShAmt, bool &Overflow) const {
Overflow = ShAmt.uge(getBitWidth());
if (Overflow)
  return APInt(BitWidth, 0);

Overflow = ShAmt.ugt(countLeadingZeros());

return *this << ShAmt;
2039}

2041APInt APInt::sadd_sat(const APInt &RHS) const {
bool Overflow;
APInt Res = sadd_ov(RHS, Overflow);
if (!Overflow)
  return Res;

return isNegative() ? APInt::getSignedMinValue(BitWidth)
                    : APInt::getSignedMaxValue(BitWidth);
2049}

2051APInt APInt::uadd_sat(const APInt &RHS) const {
bool Overflow;
APInt Res = uadd_ov(RHS, Overflow);
if (!Overflow)
  return Res;

return APInt::getMaxValue(BitWidth);
2058}

2060APInt APInt::ssub_sat(const APInt &RHS) const {
bool Overflow;
APInt Res = ssub_ov(RHS, Overflow);
if (!Overflow)
  return Res;

return isNegative() ? APInt::getSignedMinValue(BitWidth)
                    : APInt::getSignedMaxValue(BitWidth);
2068}

2070APInt APInt::usub_sat(const APInt &RHS) const {
bool Overflow;
APInt Res = usub_ov(RHS, Overflow);
if (!Overflow)
  return Res;

return APInt(BitWidth, 0);
2077}

2079APInt APInt::smul_sat(const APInt &RHS) const {
bool Overflow;
APInt Res = smul_ov(RHS, Overflow);
if (!Overflow)
  return Res;

// The result is negative if one and only one of inputs is negative.
bool ResIsNegative = isNegative() ^ RHS.isNegative();

return ResIsNegative ? APInt::getSignedMinValue(BitWidth)
                     : APInt::getSignedMaxValue(BitWidth);
2090}

2092APInt APInt::umul_sat(const APInt &RHS) const {
bool Overflow;
APInt Res = umul_ov(RHS, Overflow);
if (!Overflow)
  return Res;

return APInt::getMaxValue(BitWidth);
2099}

2101APInt APInt::sshl_sat(const APInt &RHS) const {
bool Overflow;
APInt Res = sshl_ov(RHS, Overflow);
if (!Overflow)
  return Res;

return isNegative() ? APInt::getSignedMinValue(BitWidth)
                    : APInt::getSignedMaxValue(BitWidth);
2109}

2111APInt APInt::ushl_sat(const APInt &RHS) const {
bool Overflow;
APInt Res = ushl_ov(RHS, Overflow);
if (!Overflow)
  return Res;

return APInt::getMaxValue(BitWidth);
2118}

2120void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) {
// Check our assumptions here
assert(!str.empty() && "Invalid string length")((void)0);
assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||((void)0)
        radix == 36) &&((void)0)
       "Radix should be 2, 8, 10, 16, or 36!")((void)0);

StringRef::iterator p = str.begin();
size_t slen = str.size();
bool isNeg = *p == '-';
if (*p == '-' || *p == '+') {
  p++;
  slen--;
  assert(slen && "String is only a sign, needs a value.")((void)0);
}
assert((slen <= numbits || radix != 2) && "Insufficient bit width")((void)0);
assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width")((void)0);
assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width")((void)0);
assert((((slen-1)*64)/22 <= numbits || radix != 10) &&((void)0)
       "Insufficient bit width")((void)0);

// Allocate memory if needed
if (isSingleWord())
  U.VAL = 0;
else
  U.pVal = getClearedMemory(getNumWords());

// Figure out if we can shift instead of multiply
unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);

// Enter digit traversal loop
for (StringRef::iterator e = str.end(); p != e; ++p) {
  unsigned digit = getDigit(*p, radix);
  assert(digit < radix && "Invalid character in digit string")((void)0);

  // Shift or multiply the value by the radix
  if (slen > 1) {
    if (shift)
      *this <<= shift;
    else
      *this *= radix;
  }

  // Add in the digit we just interpreted
  *this += digit;
}
// If its negative, put it in two's complement form
if (isNeg)
  this->negate();
2169}

2171void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix,
                   bool Signed, bool formatAsCLiteral) const {
assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 ||((void)0)
        Radix == 36) &&((void)0)
       "Radix should be 2, 8, 10, 16, or 36!")((void)0);

const char *Prefix = "";
if (formatAsCLiteral) {
  switch (Radix) {
    case 2:
      // Binary literals are a non-standard extension added in gcc 4.3:
      // http://gcc.gnu.org/onlinedocs/gcc-4.3.0/gcc/Binary-constants.html
      Prefix = "0b";
      break;
    case 8:
      Prefix = "0";
      break;
    case 10:
      break; // No prefix
    case 16:
      Prefix = "0x";
      break;
    default:
      llvm_unreachable("Invalid radix!")__builtin_unreachable();
  }
}

// First, check for a zero value and just short circuit the logic below.
if (*this == 0) {
  while (*Prefix) {
    Str.push_back(*Prefix);
    ++Prefix;
  };
  Str.push_back('0');
  return;
}

static const char Digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

if (isSingleWord()) {
  char Buffer[65];
  char *BufPtr = std::end(Buffer);

  uint64_t N;
  if (!Signed) {
    N = getZExtValue();
  } else {
    int64_t I = getSExtValue();
    if (I >= 0) {
      N = I;
    } else {
      Str.push_back('-');
      N = -(uint64_t)I;
    }
  }

  while (*Prefix) {
    Str.push_back(*Prefix);
    ++Prefix;
  };

  while (N) {
    *--BufPtr = Digits[N % Radix];
    N /= Radix;
  }
  Str.append(BufPtr, std::end(Buffer));
  return;
}

APInt Tmp(*this);

if (Signed && isNegative()) {
  // They want to print the signed version and it is a negative value
  // Flip the bits and add one to turn it into the equivalent positive
  // value and put a '-' in the result.
  Tmp.negate();
  Str.push_back('-');
}

while (*Prefix) {
  Str.push_back(*Prefix);
  ++Prefix;
};

// We insert the digits backward, then reverse them to get the right order.
unsigned StartDig = Str.size();

// For the 2, 8 and 16 bit cases, we can just shift instead of divide
// because the number of bits per digit (1, 3 and 4 respectively) divides
// equally.  We just shift until the value is zero.
if (Radix == 2 || Radix == 8 || Radix == 16) {
  // Just shift tmp right for each digit width until it becomes zero
  unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
  unsigned MaskAmt = Radix - 1;

  while (Tmp.getBoolValue()) {
    unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;
    Str.push_back(Digits[Digit]);
    Tmp.lshrInPlace(ShiftAmt);
  }
} else {
  while (Tmp.getBoolValue()) {
    uint64_t Digit;
    udivrem(Tmp, Radix, Tmp, Digit);
    assert(Digit < Radix && "divide failed")((void)0);
    Str.push_back(Digits[Digit]);
  }
}

// Reverse the digits before returning.
std::reverse(Str.begin()+StartDig, Str.end());
2282}

2284#if !defined(NDEBUG1) || defined(LLVM_ENABLE_DUMP)
2285LLVM_DUMP_METHOD__attribute__((noinline)) void APInt::dump() const {
SmallString<40> S, U;
this->toStringUnsigned(U);
this->toStringSigned(S);
dbgs() << "APInt(" << BitWidth << "b, "
       << U << "u " << S << "s)\n";
2291}
2292#endif

2294void APInt::print(raw_ostream &OS, bool isSigned) const {
SmallString<40> S;
this->toString(S, 10, isSigned, /* formatAsCLiteral = */false);
OS << S;
2298}

2300// This implements a variety of operations on a representation of
2301// arbitrary precision, two's-complement, bignum integer values.

2303// Assumed by lowHalf, highHalf, partMSB and partLSB.  A fairly safe
2304// and unrestricting assumption.
2305static_assert(APInt::APINT_BITS_PER_WORD % 2 == 0,
            "Part width must be divisible by 2!");

2308/* Some handy functions local to this file.  */

2310/* Returns the integer part with the least significant BITS set.
 BITS cannot be zero.  */
2312static inline APInt::WordType lowBitMask(unsigned bits) {
assert(bits != 0 && bits <= APInt::APINT_BITS_PER_WORD)((void)0);

return ~(APInt::WordType) 0 >> (APInt::APINT_BITS_PER_WORD - bits);
2316}

2318/* Returns the value of the lower half of PART.  */
2319static inline APInt::WordType lowHalf(APInt::WordType part) {
return part & lowBitMask(APInt::APINT_BITS_PER_WORD / 2);
2321}

2323/* Returns the value of the upper half of PART.  */
2324static inline APInt::WordType highHalf(APInt::WordType part) {
return part >> (APInt::APINT_BITS_PER_WORD / 2);
2326}

2328/* Returns the bit number of the most significant set bit of a part.
 If the input number has no bits set -1U is returned.  */
2330static unsigned partMSB(APInt::WordType value) {
return findLastSet(value, ZB_Max);
2332}

2334/* Returns the bit number of the least significant set bit of a
 part.  If the input number has no bits set -1U is returned.  */
2336static unsigned partLSB(APInt::WordType value) {
return findFirstSet(value, ZB_Max);
2338}

2340/* Sets the least significant part of a bignum to the input value, and
 zeroes out higher parts.  */
2342void APInt::tcSet(WordType *dst, WordType part, unsigned parts) {
assert(parts > 0)((void)0);

dst[0] = part;
for (unsigned i = 1; i < parts; i++)
  dst[i] = 0;
2348}

2350/* Assign one bignum to another.  */
2351void APInt::tcAssign(WordType *dst, const WordType *src, unsigned parts) {
for (unsigned i = 0; i < parts; i++)
  dst[i] = src[i];
2354}

2356/* Returns true if a bignum is zero, false otherwise.  */
2357bool APInt::tcIsZero(const WordType *src, unsigned parts) {
for (unsigned i = 0; i < parts; i++)
  if (src[i])
    return false;

return true;
2363}

2365/* Extract the given bit of a bignum; returns 0 or 1.  */
2366int APInt::tcExtractBit(const WordType *parts, unsigned bit) {
return (parts[whichWord(bit)] & maskBit(bit)) != 0;
2368}

2370/* Set the given bit of a bignum. */
2371void APInt::tcSetBit(WordType *parts, unsigned bit) {
parts[whichWord(bit)] |= maskBit(bit);
2373}

2375/* Clears the given bit of a bignum. */
2376void APInt::tcClearBit(WordType *parts, unsigned bit) {
parts[whichWord(bit)] &= ~maskBit(bit);
2378}

2380/* Returns the bit number of the least significant set bit of a
 number.  If the input number has no bits set -1U is returned.  */
2382unsigned APInt::tcLSB(const WordType *parts, unsigned n) {
for (unsigned i = 0; i < n; i++) {
  if (parts[i] != 0) {
    unsigned lsb = partLSB(parts[i]);

    return lsb + i * APINT_BITS_PER_WORD;
  }
}

return -1U;
2392}

2394/* Returns the bit number of the most significant set bit of a number.
 If the input number has no bits set -1U is returned.  */
2396unsigned APInt::tcMSB(const WordType *parts, unsigned n) {
do {
  --n;

  if (parts[n] != 0) {
    unsigned msb = partMSB(parts[n]);

    return msb + n * APINT_BITS_PER_WORD;
  }
} while (n);

return -1U;
2408}

2410/* Copy the bit vector of width srcBITS from SRC, starting at bit
 srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
 the least significant bit of DST.  All high bits above srcBITS in
 DST are zero-filled.  */
2414void
2415APInt::tcExtract(WordType *dst, unsigned dstCount, const WordType *src,
               unsigned srcBits, unsigned srcLSB) {
unsigned dstParts = (srcBits + APINT_BITS_PER_WORD - 1) / APINT_BITS_PER_WORD;
assert(dstParts <= dstCount)((void)0);

unsigned firstSrcPart = srcLSB / APINT_BITS_PER_WORD;
tcAssign (dst, src + firstSrcPart, dstParts);

unsigned shift = srcLSB % APINT_BITS_PER_WORD;
tcShiftRight (dst, dstParts, shift);

/* We now have (dstParts * APINT_BITS_PER_WORD - shift) bits from SRC
   in DST.  If this is less that srcBits, append the rest, else
   clear the high bits.  */
unsigned n = dstParts * APINT_BITS_PER_WORD - shift;
if (n < srcBits) {
  WordType mask = lowBitMask (srcBits - n);
  dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
                        << n % APINT_BITS_PER_WORD);
} else if (n > srcBits) {
  if (srcBits % APINT_BITS_PER_WORD)
    dst[dstParts - 1] &= lowBitMask (srcBits % APINT_BITS_PER_WORD);
}

/* Clear high parts.  */
while (dstParts < dstCount)
  dst[dstParts++] = 0;
2442}

2444/* DST += RHS + C where C is zero or one.  Returns the carry flag.  */
2445APInt::WordType APInt::tcAdd(WordType *dst, const WordType *rhs,
                           WordType c, unsigned parts) {
assert(c <= 1)((void)0);

for (unsigned i = 0; i < parts; i++) {
  WordType l = dst[i];
  if (c) {
    dst[i] += rhs[i] + 1;
    c = (dst[i] <= l);
  } else {
    dst[i] += rhs[i];
    c = (dst[i] < l);
  }
}

return c;
2461}

2463/// This function adds a single "word" integer, src, to the multiple
2464/// "word" integer array, dst[]. dst[] is modified to reflect the addition and
2465/// 1 is returned if there is a carry out, otherwise 0 is returned.
2466/// @returns the carry of the addition.
2467APInt::WordType APInt::tcAddPart(WordType *dst, WordType src,
                               unsigned parts) {
for (unsigned i = 0; i < parts; ++i) {
  dst[i] += src;
  if (dst[i] >= src)
    return 0; // No need to carry so exit early.
  src = 1; // Carry one to next digit.
}

return 1;
2477}

2479/* DST -= RHS + C where C is zero or one.  Returns the carry flag.  */
2480APInt::WordType APInt::tcSubtract(WordType *dst, const WordType *rhs,
                                WordType c, unsigned parts) {
assert(c <= 1)((void)0);

for (unsigned i = 0; i < parts; i++) {
  WordType l = dst[i];
  if (c) {
    dst[i] -= rhs[i] + 1;
    c = (dst[i] >= l);
  } else {
    dst[i] -= rhs[i];
    c = (dst[i] > l);
  }
}

return c;
2496}

2498/// This function subtracts a single "word" (64-bit word), src, from
2499/// the multi-word integer array, dst[], propagating the borrowed 1 value until
2500/// no further borrowing is needed or it runs out of "words" in dst.  The result
2501/// is 1 if "borrowing" exhausted the digits in dst, or 0 if dst was not
2502/// exhausted. In other words, if src > dst then this function returns 1,
2503/// otherwise 0.
2504/// @returns the borrow out of the subtraction
2505APInt::WordType APInt::tcSubtractPart(WordType *dst, WordType src,
                                    unsigned parts) {
for (unsigned i = 0; i < parts; ++i) {
  WordType Dst = dst[i];
  dst[i] -= src;
  if (src <= Dst)
    return 0; // No need to borrow so exit early.
  src = 1; // We have to "borrow 1" from next "word"
}

return 1;
2516}

2518/* Negate a bignum in-place.  */
2519void APInt::tcNegate(WordType *dst, unsigned parts) {
tcComplement(dst, parts);
tcIncrement(dst, parts);
2522}

2524/*  DST += SRC * MULTIPLIER + CARRY   if add is true
  DST  = SRC * MULTIPLIER + CARRY   if add is false

  Requires 0 <= DSTPARTS <= SRCPARTS + 1.  If DST overlaps SRC
  they must start at the same point, i.e. DST == SRC.

  If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
  returned.  Otherwise DST is filled with the least significant
  DSTPARTS parts of the result, and if all of the omitted higher
  parts were zero return zero, otherwise overflow occurred and
  return one.  */
2535int APInt::tcMultiplyPart(WordType *dst, const WordType *src,
                        WordType multiplier, WordType carry,
                        unsigned srcParts, unsigned dstParts,
                        bool add) {
/* Otherwise our writes of DST kill our later reads of SRC.  */
assert(dst <= src || dst >= src + srcParts)((void)0);
assert(dstParts <= srcParts + 1)((void)0);

/* N loops; minimum of dstParts and srcParts.  */
unsigned n = std::min(dstParts, srcParts);

for (unsigned i = 0; i < n; i++) {
  WordType low, mid, high, srcPart;

    /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.

       This cannot overflow, because

       (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)

       which is less than n^2.  */

  srcPart = src[i];

  if (multiplier == 0 || srcPart == 0) {
    low = carry;
    high = 0;
  } else {
    low = lowHalf(srcPart) * lowHalf(multiplier);
    high = highHalf(srcPart) * highHalf(multiplier);

    mid = lowHalf(srcPart) * highHalf(multiplier);
    high += highHalf(mid);
    mid <<= APINT_BITS_PER_WORD / 2;
    if (low + mid < low)
      high++;
    low += mid;

    mid = highHalf(srcPart) * lowHalf(multiplier);
    high += highHalf(mid);
    mid <<= APINT_BITS_PER_WORD / 2;
    if (low + mid < low)
      high++;
    low += mid;

    /* Now add carry.  */
    if (low + carry < low)
      high++;
    low += carry;
  }

  if (add) {
    /* And now DST[i], and store the new low part there.  */
    if (low + dst[i] < low)
      high++;
    dst[i] += low;
  } else
    dst[i] = low;

  carry = high;
}

if (srcParts < dstParts) {
  /* Full multiplication, there is no overflow.  */
  assert(srcParts + 1 == dstParts)((void)0);
  dst[srcParts] = carry;
  return 0;
}

/* We overflowed if there is carry.  */
if (carry)
  return 1;

/* We would overflow if any significant unwritten parts would be
   non-zero.  This is true if any remaining src parts are non-zero
   and the multiplier is non-zero.  */
if (multiplier)
  for (unsigned i = dstParts; i < srcParts; i++)
    if (src[i])
      return 1;

/* We fitted in the narrow destination.  */
return 0;
2618}

2620/* DST = LHS * RHS, where DST has the same width as the operands and
 is filled with the least significant parts of the result.  Returns
 one if overflow occurred, otherwise zero.  DST must be disjoint
 from both operands.  */
2624int APInt::tcMultiply(WordType *dst, const WordType *lhs,
                    const WordType *rhs, unsigned parts) {
assert(dst != lhs && dst != rhs)((void)0);

int overflow = 0;
tcSet(dst, 0, parts);

for (unsigned i = 0; i < parts; i++)
  overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
                             parts - i, true);

return overflow;
2636}

2638/// DST = LHS * RHS, where DST has width the sum of the widths of the
2639/// operands. No overflow occurs. DST must be disjoint from both operands.
2640void APInt::tcFullMultiply(WordType *dst, const WordType *lhs,
                         const WordType *rhs, unsigned lhsParts,
                         unsigned rhsParts) {
/* Put the narrower number on the LHS for less loops below.  */
if (lhsParts > rhsParts)
  return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);

assert(dst != lhs && dst != rhs)((void)0);

tcSet(dst, 0, rhsParts);

for (unsigned i = 0; i < lhsParts; i++)
  tcMultiplyPart(&dst[i], rhs, lhs[i], 0, rhsParts, rhsParts + 1, true);
2653}

2655/* If RHS is zero LHS and REMAINDER are left unchanged, return one.
 Otherwise set LHS to LHS / RHS with the fractional part discarded,
 set REMAINDER to the remainder, return zero.  i.e.

 OLD_LHS = RHS * LHS + REMAINDER

 SCRATCH is a bignum of the same size as the operands and result for
 use by the routine; its contents need not be initialized and are
 destroyed.  LHS, REMAINDER and SCRATCH must be distinct.
2664*/
2665int APInt::tcDivide(WordType *lhs, const WordType *rhs,
                  WordType *remainder, WordType *srhs,
                  unsigned parts) {
assert(lhs != remainder && lhs != srhs && remainder != srhs)((void)0);

unsigned shiftCount = tcMSB(rhs, parts) + 1;
if (shiftCount == 0)
  return true;

shiftCount = parts * APINT_BITS_PER_WORD - shiftCount;
unsigned n = shiftCount / APINT_BITS_PER_WORD;
WordType mask = (WordType) 1 << (shiftCount % APINT_BITS_PER_WORD);

tcAssign(srhs, rhs, parts);
tcShiftLeft(srhs, parts, shiftCount);
tcAssign(remainder, lhs, parts);
tcSet(lhs, 0, parts);

/* Loop, subtracting SRHS if REMAINDER is greater and adding that to
   the total.  */
for (;;) {
  int compare = tcCompare(remainder, srhs, parts);
  if (compare >= 0) {
    tcSubtract(remainder, srhs, 0, parts);
    lhs[n] |= mask;
  }

  if (shiftCount == 0)
    break;
  shiftCount--;
  tcShiftRight(srhs, parts, 1);
  if ((mask >>= 1) == 0) {
    mask = (WordType) 1 << (APINT_BITS_PER_WORD - 1);
    n--;
  }
}

return false;
2703}

2705/// Shift a bignum left Cound bits in-place. Shifted in bits are zero. There are
2706/// no restrictions on Count.
2707void APInt::tcShiftLeft(WordType *Dst, unsigned Words, unsigned Count) {
// Don't bother performing a no-op shift.
if (!Count)
  return;

// WordShift is the inter-part shift; BitShift is the intra-part shift.
unsigned WordShift = std::min(Count / APINT_BITS_PER_WORD, Words);
unsigned BitShift = Count % APINT_BITS_PER_WORD;

// Fastpath for moving by whole words.
if (BitShift == 0) {
  std::memmove(Dst + WordShift, Dst, (Words - WordShift) * APINT_WORD_SIZE);
} else {
  while (Words-- > WordShift) {
    Dst[Words] = Dst[Words - WordShift] << BitShift;
    if (Words > WordShift)
      Dst[Words] |=
        Dst[Words - WordShift - 1] >> (APINT_BITS_PER_WORD - BitShift);
  }
}

// Fill in the remainder with 0s.
std::memset(Dst, 0, WordShift * APINT_WORD_SIZE);
2730}

2732/// Shift a bignum right Count bits in-place. Shifted in bits are zero. There
2733/// are no restrictions on Count.
2734void APInt::tcShiftRight(WordType *Dst, unsigned Words, unsigned Count) {
// Don't bother performing a no-op shift.
if (!Count)
  return;

// WordShift is the inter-part shift; BitShift is the intra-part shift.
unsigned WordShift = std::min(Count / APINT_BITS_PER_WORD, Words);
unsigned BitShift = Count % APINT_BITS_PER_WORD;

unsigned WordsToMove = Words - WordShift;
// Fastpath for moving by whole words.
if (BitShift == 0) {
  std::memmove(Dst, Dst + WordShift, WordsToMove * APINT_WORD_SIZE);
} else {
  for (unsigned i = 0; i != WordsToMove; ++i) {
    Dst[i] = Dst[i + WordShift] >> BitShift;
    if (i + 1 != WordsToMove)
      Dst[i] |= Dst[i + WordShift + 1] << (APINT_BITS_PER_WORD - BitShift);
  }
}

// Fill in the remainder with 0s.
std::memset(Dst + WordsToMove, 0, WordShift * APINT_WORD_SIZE);
2757}

2759/* Bitwise and of two bignums.  */
2760void APInt::tcAnd(WordType *dst, const WordType *rhs, unsigned parts) {
for (unsigned i = 0; i < parts; i++)
  dst[i] &= rhs[i];
2763}

2765/* Bitwise inclusive or of two bignums.  */
2766void APInt::tcOr(WordType *dst, const WordType *rhs, unsigned parts) {
for (unsigned i = 0; i < parts; i++)
  dst[i] |= rhs[i];
2769}

2771/* Bitwise exclusive or of two bignums.  */
2772void APInt::tcXor(WordType *dst, const WordType *rhs, unsigned parts) {
for (unsigned i = 0; i < parts; i++)
  dst[i] ^= rhs[i];
2775}

2777/* Complement a bignum in-place.  */
2778void APInt::tcComplement(WordType *dst, unsigned parts) {
for (unsigned i = 0; i < parts; i++)
  dst[i] = ~dst[i];
2781}

2783/* Comparison (unsigned) of two bignums.  */
2784int APInt::tcCompare(const WordType *lhs, const WordType *rhs,
                   unsigned parts) {
while (parts) {
  parts--;
  if (lhs[parts] != rhs[parts])
    return (lhs[parts] > rhs[parts]) ? 1 : -1;
}

return 0;
2793}

2795/* Set the least significant BITS bits of a bignum, clear the
 rest.  */
2797void APInt::tcSetLeastSignificantBits(WordType *dst, unsigned parts,
                                    unsigned bits) {
unsigned i = 0;
while (bits > APINT_BITS_PER_WORD) {
  dst[i++] = ~(WordType) 0;
  bits -= APINT_BITS_PER_WORD;
}

if (bits)
  dst[i++] = ~(WordType) 0 >> (APINT_BITS_PER_WORD - bits);

while (i < parts)
  dst[i++] = 0;
2810}

2812APInt llvm::APIntOps::RoundingUDiv(const APInt &A, const APInt &B,
                                 APInt::Rounding RM) {
// Currently udivrem always rounds down.
switch (RM) {
case APInt::Rounding::DOWN:
case APInt::Rounding::TOWARD_ZERO:
  return A.udiv(B);
case APInt::Rounding::UP: {
  APInt Quo, Rem;
  APInt::udivrem(A, B, Quo, Rem);
  if (Rem == 0)
    return Quo;
  return Quo + 1;
}
}
llvm_unreachable("Unknown APInt::Rounding enum")__builtin_unreachable();
2828}

2830APInt llvm::APIntOps::RoundingSDiv(const APInt &A, const APInt &B,
                                 APInt::Rounding RM) {
switch (RM) {
1
Control jumps to 'case DOWN:'  at line 2833→
case APInt::Rounding::DOWN:
case APInt::Rounding::UP: {
  APInt Quo, Rem;
  APInt::sdivrem(A, B, Quo, Rem);
2
←
Calling 'APInt::sdivrem'→
  if (Rem == 0)
    return Quo;
  // This algorithm deals with arbitrary rounding mode used by sdivrem.
  // We want to check whether the non-integer part of the mathematical value
  // is negative or not. If the non-integer part is negative, we need to round
  // down from Quo; otherwise, if it's positive or 0, we return Quo, as it's
  // already rounded down.
  if (RM == APInt::Rounding::DOWN) {
    if (Rem.isNegative() != B.isNegative())
      return Quo - 1;
    return Quo;
  }
  if (Rem.isNegative() != B.isNegative())
    return Quo;
  return Quo + 1;
}
// Currently sdiv rounds towards zero.
case APInt::Rounding::TOWARD_ZERO:
  return A.sdiv(B);
}
llvm_unreachable("Unknown APInt::Rounding enum")__builtin_unreachable();
2858}

2860Optional<APInt>
2861llvm::APIntOps::SolveQuadraticEquationWrap(APInt A, APInt B, APInt C,
                                         unsigned RangeWidth) {
unsigned CoeffWidth = A.getBitWidth();
assert(CoeffWidth == B.getBitWidth() && CoeffWidth == C.getBitWidth())((void)0);
assert(RangeWidth <= CoeffWidth &&((void)0)
       "Value range width should be less than coefficient width")((void)0);
assert(RangeWidth > 1 && "Value range bit width should be > 1")((void)0);

LLVM_DEBUG(dbgs() << __func__ << ": solving " << A << "x^2 + " << Bdo { } while (false)
                  << "x + " << C << ", rw:" << RangeWidth << '\n')do { } while (false);

// Identify 0 as a (non)solution immediately.
if (C.sextOrTrunc(RangeWidth).isNullValue() ) {
  LLVM_DEBUG(dbgs() << __func__ << ": zero solution\n")do { } while (false);
  return APInt(CoeffWidth, 0);
}

// The result of APInt arithmetic has the same bit width as the operands,
// so it can actually lose high bits. A product of two n-bit integers needs
// 2n-1 bits to represent the full value.
// The operation done below (on quadratic coefficients) that can produce
// the largest value is the evaluation of the equation during bisection,
// which needs 3 times the bitwidth of the coefficient, so the total number
// of required bits is 3n.
//
// The purpose of this extension is to simulate the set Z of all integers,
// where n+1 > n for all n in Z. In Z it makes sense to talk about positive
// and negative numbers (not so much in a modulo arithmetic). The method
// used to solve the equation is based on the standard formula for real
// numbers, and uses the concepts of "positive" and "negative" with their
// usual meanings.
CoeffWidth *= 3;
A = A.sext(CoeffWidth);
B = B.sext(CoeffWidth);
C = C.sext(CoeffWidth);

// Make A > 0 for simplicity. Negate cannot overflow at this point because
// the bit width has increased.
if (A.isNegative()) {
  A.negate();
  B.negate();
  C.negate();
}

// Solving an equation q(x) = 0 with coefficients in modular arithmetic
// is really solving a set of equations q(x) = kR for k = 0, 1, 2, ...,
// and R = 2^BitWidth.
// Since we're trying not only to find exact solutions, but also values
// that "wrap around", such a set will always have a solution, i.e. an x
// that satisfies at least one of the equations, or such that |q(x)|
// exceeds kR, while |q(x-1)| for the same k does not.
//
// We need to find a value k, such that Ax^2 + Bx + C = kR will have a
// positive solution n (in the above sense), and also such that the n
// will be the least among all solutions corresponding to k = 0, 1, ...
// (more precisely, the least element in the set
//   { n(k) | k is such that a solution n(k) exists }).
//
// Consider the parabola (over real numbers) that corresponds to the
// quadratic equation. Since A > 0, the arms of the parabola will point
// up. Picking different values of k will shift it up and down by R.
//
// We want to shift the parabola in such a way as to reduce the problem
// of solving q(x) = kR to solving shifted_q(x) = 0.
// (The interesting solutions are the ceilings of the real number
// solutions.)
APInt R = APInt::getOneBitSet(CoeffWidth, RangeWidth);
APInt TwoA = 2 * A;
APInt SqrB = B * B;
bool PickLow;

auto RoundUp = [] (const APInt &V, const APInt &A) -> APInt {
  assert(A.isStrictlyPositive())((void)0);
  APInt T = V.abs().urem(A);
  if (T.isNullValue())
    return V;
  return V.isNegative() ? V+T : V+(A-T);
};

// The vertex of the parabola is at -B/2A, but since A > 0, it's negative
// iff B is positive.
if (B.isNonNegative()) {
  // If B >= 0, the vertex it at a negative location (or at 0), so in
  // order to have a non-negative solution we need to pick k that makes
  // C-kR negative. To satisfy all the requirements for the solution
  // that we are looking for, it needs to be closest to 0 of all k.
  C = C.srem(R);
  if (C.isStrictlyPositive())
    C -= R;
  // Pick the greater solution.
  PickLow = false;
} else {
  // If B < 0, the vertex is at a positive location. For any solution
  // to exist, the discriminant must be non-negative. This means that
  // C-kR <= B^2/4A is a necessary condition for k, i.e. there is a
  // lower bound on values of k: kR >= C - B^2/4A.
  APInt LowkR = C - SqrB.udiv(2*TwoA); // udiv because all values > 0.
  // Round LowkR up (towards +inf) to the nearest kR.
  LowkR = RoundUp(LowkR, R);

  // If there exists k meeting the condition above, and such that
  // C-kR > 0, there will be two positive real number solutions of
  // q(x) = kR. Out of all such values of k, pick the one that makes
  // C-kR closest to 0, (i.e. pick maximum k such that C-kR > 0).
  // In other words, find maximum k such that LowkR <= kR < C.
  if (C.sgt(LowkR)) {
    // If LowkR < C, then such a k is guaranteed to exist because
    // LowkR itself is a multiple of R.
    C -= -RoundUp(-C, R);      // C = C - RoundDown(C, R)
    // Pick the smaller solution.
    PickLow = true;
  } else {
    // If C-kR < 0 for all potential k's, it means that one solution
    // will be negative, while the other will be positive. The positive
    // solution will shift towards 0 if the parabola is moved up.
    // Pick the kR closest to the lower bound (i.e. make C-kR closest
    // to 0, or in other words, out of all parabolas that have solutions,
    // pick the one that is the farthest "up").
    // Since LowkR is itself a multiple of R, simply take C-LowkR.
    C -= LowkR;
    // Pick the greater solution.
    PickLow = false;
  }
}

LLVM_DEBUG(dbgs() << __func__ << ": updated coefficients " << A << "x^2 + "do { } while (false)
                  << B << "x + " << C << ", rw:" << RangeWidth << '\n')do { } while (false);

APInt D = SqrB - 4*A*C;
assert(D.isNonNegative() && "Negative discriminant")((void)0);
APInt SQ = D.sqrt();

APInt Q = SQ * SQ;
bool InexactSQ = Q != D;
// The calculated SQ may actually be greater than the exact (non-integer)
// value. If that's the case, decrement SQ to get a value that is lower.
if (Q.sgt(D))
  SQ -= 1;

APInt X;
APInt Rem;

// SQ is rounded down (i.e SQ * SQ <= D), so the roots may be inexact.
// When using the quadratic formula directly, the calculated low root
// may be greater than the exact one, since we would be subtracting SQ.
// To make sure that the calculated root is not greater than the exact
// one, subtract SQ+1 when calculating the low root (for inexact value
// of SQ).
if (PickLow)
  APInt::sdivrem(-B - (SQ+InexactSQ), TwoA, X, Rem);
else
  APInt::sdivrem(-B + SQ, TwoA, X, Rem);

// The updated coefficients should be such that the (exact) solution is
// positive. Since APInt division rounds towards 0, the calculated one
// can be 0, but cannot be negative.
assert(X.isNonNegative() && "Solution should be non-negative")((void)0);

if (!InexactSQ && Rem.isNullValue()) {
  LLVM_DEBUG(dbgs() << __func__ << ": solution (root): " << X << '\n')do { } while (false);
  return X;
}

assert((SQ*SQ).sle(D) && "SQ = |_sqrt(D)_|, so SQ*SQ <= D")((void)0);
// The exact value of the square root of D should be between SQ and SQ+1.
// This implies that the solution should be between that corresponding to
// SQ (i.e. X) and that corresponding to SQ+1.
//
// The calculated X cannot be greater than the exact (real) solution.
// Actually it must be strictly less than the exact solution, while
// X+1 will be greater than or equal to it.

APInt VX = (A*X + B)*X + C;
APInt VY = VX + TwoA*X + A + B;
bool SignChange = VX.isNegative() != VY.isNegative() ||
                  VX.isNullValue() != VY.isNullValue();
// If the sign did not change between X and X+1, X is not a valid solution.
// This could happen when the actual (exact) roots don't have an integer
// between them, so they would both be contained between X and X+1.
if (!SignChange) {
  LLVM_DEBUG(dbgs() << __func__ << ": no valid solution\n")do { } while (false);
  return None;
}

X += 1;
LLVM_DEBUG(dbgs() << __func__ << ": solution (wrap): " << X << '\n')do { } while (false);
return X;
3048}

3050Optional<unsigned>
3051llvm::APIntOps::GetMostSignificantDifferentBit(const APInt &A, const APInt &B) {
assert(A.getBitWidth() == B.getBitWidth() && "Must have the same bitwidth")((void)0);
if (A == B)
  return llvm::None;
return A.getBitWidth() - ((A ^ B).countLeadingZeros() + 1);
3056}

3058/// StoreIntToMemory - Fills the StoreBytes bytes of memory starting from Dst
3059/// with the integer held in IntVal.
3060void llvm::StoreIntToMemory(const APInt &IntVal, uint8_t *Dst,
                          unsigned StoreBytes) {
assert((IntVal.getBitWidth()+7)/8 >= StoreBytes && "Integer too small!")((void)0);
const uint8_t *Src = (const uint8_t *)IntVal.getRawData();

if (sys::IsLittleEndianHost) {
  // Little-endian host - the source is ordered from LSB to MSB.  Order the
  // destination from LSB to MSB: Do a straight copy.
  memcpy(Dst, Src, StoreBytes);
} else {
  // Big-endian host - the source is an array of 64 bit words ordered from
  // LSW to MSW.  Each word is ordered from MSB to LSB.  Order the destination
  // from MSB to LSB: Reverse the word order, but not the bytes in a word.
  while (StoreBytes > sizeof(uint64_t)) {
    StoreBytes -= sizeof(uint64_t);
    // May not be aligned so use memcpy.
    memcpy(Dst + StoreBytes, Src, sizeof(uint64_t));
    Src += sizeof(uint64_t);
  }

  memcpy(Dst, Src + sizeof(uint64_t) - StoreBytes, StoreBytes);
}
3082}

3084/// LoadIntFromMemory - Loads the integer stored in the LoadBytes bytes starting
3085/// from Src into IntVal, which is assumed to be wide enough and to hold zero.
3086void llvm::LoadIntFromMemory(APInt &IntVal, const uint8_t *Src,
                           unsigned LoadBytes) {
assert((IntVal.getBitWidth()+7)/8 >= LoadBytes && "Integer too small!")((void)0);
uint8_t *Dst = reinterpret_cast<uint8_t *>(
                 const_cast<uint64_t *>(IntVal.getRawData()));

if (sys::IsLittleEndianHost)
  // Little-endian host - the destination must be ordered from LSB to MSB.
  // The source is ordered from LSB to MSB: Do a straight copy.
  memcpy(Dst, Src, LoadBytes);
else {
  // Big-endian - the destination is an array of 64 bit words ordered from
  // LSW to MSW.  Each word must be ordered from MSB to LSB.  The source is
  // ordered from MSB to LSB: Reverse the word order, but not the bytes in
  // a word.
  while (LoadBytes > sizeof(uint64_t)) {
    LoadBytes -= sizeof(uint64_t);
    // May not be aligned so use memcpy.
    memcpy(Dst, Src + LoadBytes, sizeof(uint64_t));
    Dst += sizeof(uint64_t);
  }

  memcpy(Dst + sizeof(uint64_t) - LoadBytes, Src, LoadBytes);
}
3110}

←

/usr/src/gnu/usr.bin/clang/libLLVMSupport/../../../llvm/llvm/include/llvm/ADT/APInt.h

1//===-- llvm/ADT/APInt.h - For Arbitrary Precision Integer -----*- C++ -*--===//
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-exception
6//
7//===----------------------------------------------------------------------===//
8///
9/// \file
10/// This file implements a class to represent arbitrary precision
11/// integral constant values and operations on them.
12///
13//===----------------------------------------------------------------------===//

15#ifndef LLVM_ADT_APINT_H
16#define LLVM_ADT_APINT_H

18#include "llvm/Support/Compiler.h"
19#include "llvm/Support/MathExtras.h"
20#include <cassert>
21#include <climits>
22#include <cstring>
23#include <utility>

25namespace llvm {
26class FoldingSetNodeID;
27class StringRef;
28class hash_code;
29class raw_ostream;

31template <typename T> class SmallVectorImpl;
32template <typename T> class ArrayRef;
33template <typename T> class Optional;
34template <typename T> struct DenseMapInfo;

36class APInt;

38inline APInt operator-(APInt);

40//===----------------------------------------------------------------------===//
41//                              APInt Class
42//===----------------------------------------------------------------------===//

44/// Class for arbitrary precision integers.
45///
46/// APInt is a functional replacement for common case unsigned integer type like
47/// "unsigned", "unsigned long" or "uint64_t", but also allows non-byte-width
48/// integer sizes and large integer value types such as 3-bits, 15-bits, or more
49/// than 64-bits of precision. APInt provides a variety of arithmetic operators
50/// and methods to manipulate integer values of any bit-width. It supports both
51/// the typical integer arithmetic and comparison operations as well as bitwise
52/// manipulation.
53///
54/// The class has several invariants worth noting:
55///   * All bit, byte, and word positions are zero-based.
56///   * Once the bit width is set, it doesn't change except by the Truncate,
57///     SignExtend, or ZeroExtend operations.
58///   * All binary operators must be on APInt instances of the same bit width.
59///     Attempting to use these operators on instances with different bit
60///     widths will yield an assertion.
61///   * The value is stored canonically as an unsigned value. For operations
62///     where it makes a difference, there are both signed and unsigned variants
63///     of the operation. For example, sdiv and udiv. However, because the bit
64///     widths must be the same, operations such as Mul and Add produce the same
65///     results regardless of whether the values are interpreted as signed or
66///     not.
67///   * In general, the class tries to follow the style of computation that LLVM
68///     uses in its IR. This simplifies its use for LLVM.
69///
70class LLVM_NODISCARD[[clang::warn_unused_result]] APInt {
71public:
typedef uint64_t WordType;

/// This enum is used to hold the constants we needed for APInt.
enum : unsigned {
  /// Byte size of a word.
  APINT_WORD_SIZE = sizeof(WordType),
  /// Bits in a word.
  APINT_BITS_PER_WORD = APINT_WORD_SIZE * CHAR_BIT8
};

enum class Rounding {
  DOWN,
  TOWARD_ZERO,
  UP,
};

static constexpr WordType WORDTYPE_MAX = ~WordType(0);

90private:
/// This union is used to store the integer value. When the
/// integer bit-width <= 64, it uses VAL, otherwise it uses pVal.
union {
  uint64_t VAL;   ///< Used to store the <= 64 bits integer value.
  uint64_t *pVal; ///< Used to store the >64 bits integer value.
} U;

unsigned BitWidth; ///< The number of bits in this APInt.

friend struct DenseMapInfo<APInt>;

friend class APSInt;

/// Fast internal constructor
///
/// This constructor is used only internally for speed of construction of
/// temporaries. It is unsafe for general use so it is not public.
APInt(uint64_t *val, unsigned bits) : BitWidth(bits) {
  U.pVal = val;
}

/// Determine which word a bit is in.
///
/// \returns the word position for the specified bit position.
static unsigned whichWord(unsigned bitPosition) {
  return bitPosition / APINT_BITS_PER_WORD;
}

/// Determine which bit in a word a bit is in.
///
/// \returns the bit position in a word for the specified bit position
/// in the APInt.
static unsigned whichBit(unsigned bitPosition) {
  return bitPosition % APINT_BITS_PER_WORD;
}

/// Get a single bit mask.
///
/// \returns a uint64_t with only bit at "whichBit(bitPosition)" set
/// This method generates and returns a uint64_t (word) mask for a single
/// bit at a specific bit position. This is used to mask the bit in the
/// corresponding word.
static uint64_t maskBit(unsigned bitPosition) {
  return 1ULL << whichBit(bitPosition);
}

/// Clear unused high order bits
///
/// This method is used internally to clear the top "N" bits in the high order
/// word that are not used by the APInt. This is needed after the most
/// significant word is assigned a value to ensure that those bits are
/// zero'd out.
APInt &clearUnusedBits() {
  // Compute how many bits are used in the final word
  unsigned WordBits = ((BitWidth-1) % APINT_BITS_PER_WORD) + 1;

  // Mask out the high bits.
  uint64_t mask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - WordBits);
  if (isSingleWord())
    U.VAL &= mask;
  else
    U.pVal[getNumWords() - 1] &= mask;
  return *this;
}

/// Get the word corresponding to a bit position
/// \returns the corresponding word for the specified bit position.
uint64_t getWord(unsigned bitPosition) const {
  return isSingleWord() ? U.VAL : U.pVal[whichWord(bitPosition)];
}

/// Utility method to change the bit width of this APInt to new bit width,
/// allocating and/or deallocating as necessary. There is no guarantee on the
/// value of any bits upon return. Caller should populate the bits after.
void reallocate(unsigned NewBitWidth);

/// Convert a char array into an APInt
///
/// \param radix 2, 8, 10, 16, or 36
/// Converts a string into a number.  The string must be non-empty
/// and well-formed as a number of the given base. The bit-width
/// must be sufficient to hold the result.
///
/// This is used by the constructors that take string arguments.
///
/// StringRef::getAsInteger is superficially similar but (1) does
/// not assume that the string is well-formed and (2) grows the
/// result to hold the input.
void fromString(unsigned numBits, StringRef str, uint8_t radix);

/// An internal division function for dividing APInts.
///
/// This is used by the toString method to divide by the radix. It simply
/// provides a more convenient form of divide for internal use since KnuthDiv
/// has specific constraints on its inputs. If those constraints are not met
/// then it provides a simpler form of divide.
static void divide(const WordType *LHS, unsigned lhsWords,
                   const WordType *RHS, unsigned rhsWords, WordType *Quotient,
                   WordType *Remainder);

/// out-of-line slow case for inline constructor
void initSlowCase(uint64_t val, bool isSigned);

/// shared code between two array constructors
void initFromArray(ArrayRef<uint64_t> array);

/// out-of-line slow case for inline copy constructor
void initSlowCase(const APInt &that);

/// out-of-line slow case for shl
void shlSlowCase(unsigned ShiftAmt);

/// out-of-line slow case for lshr.
void lshrSlowCase(unsigned ShiftAmt);

/// out-of-line slow case for ashr.
void ashrSlowCase(unsigned ShiftAmt);

/// out-of-line slow case for operator=
void AssignSlowCase(const APInt &RHS);

/// out-of-line slow case for operator==
bool EqualSlowCase(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__));

/// out-of-line slow case for countLeadingZeros
unsigned countLeadingZerosSlowCase() const LLVM_READONLY__attribute__((__pure__));

/// out-of-line slow case for countLeadingOnes.
unsigned countLeadingOnesSlowCase() const LLVM_READONLY__attribute__((__pure__));

/// out-of-line slow case for countTrailingZeros.
unsigned countTrailingZerosSlowCase() const LLVM_READONLY__attribute__((__pure__));

/// out-of-line slow case for countTrailingOnes
unsigned countTrailingOnesSlowCase() const LLVM_READONLY__attribute__((__pure__));

/// out-of-line slow case for countPopulation
unsigned countPopulationSlowCase() const LLVM_READONLY__attribute__((__pure__));

/// out-of-line slow case for intersects.
bool intersectsSlowCase(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__));

/// out-of-line slow case for isSubsetOf.
bool isSubsetOfSlowCase(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__));

/// out-of-line slow case for setBits.
void setBitsSlowCase(unsigned loBit, unsigned hiBit);

/// out-of-line slow case for flipAllBits.
void flipAllBitsSlowCase();

/// out-of-line slow case for operator&=.
void AndAssignSlowCase(const APInt& RHS);

/// out-of-line slow case for operator|=.
void OrAssignSlowCase(const APInt& RHS);

/// out-of-line slow case for operator^=.
void XorAssignSlowCase(const APInt& RHS);

/// Unsigned comparison. Returns -1, 0, or 1 if this APInt is less than, equal
/// to, or greater than RHS.
int compare(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__));

/// Signed comparison. Returns -1, 0, or 1 if this APInt is less than, equal
/// to, or greater than RHS.
int compareSigned(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__));

259public:
/// \name Constructors
/// @{

/// Create a new APInt of numBits width, initialized as val.
///
/// If isSigned is true then val is treated as if it were a signed value
/// (i.e. as an int64_t) and the appropriate sign extension to the bit width
/// will be done. Otherwise, no sign extension occurs (high order bits beyond
/// the range of val are zero filled).
///
/// \param numBits the bit width of the constructed APInt
/// \param val the initial value of the APInt
/// \param isSigned how to treat signedness of val
APInt(unsigned numBits, uint64_t val, bool isSigned = false)
    : BitWidth(numBits) {
  assert(BitWidth && "bitwidth too small")((void)0);
  if (isSingleWord()) {
    U.VAL = val;
    clearUnusedBits();
  } else {
    initSlowCase(val, isSigned);
  }
}

/// Construct an APInt of numBits width, initialized as bigVal[].
///
/// Note that bigVal.size() can be smaller or larger than the corresponding
/// bit width but any extraneous bits will be dropped.
///
/// \param numBits the bit width of the constructed APInt
/// \param bigVal a sequence of words to form the initial value of the APInt
APInt(unsigned numBits, ArrayRef<uint64_t> bigVal);

/// Equivalent to APInt(numBits, ArrayRef<uint64_t>(bigVal, numWords)), but
/// deprecated because this constructor is prone to ambiguity with the
/// APInt(unsigned, uint64_t, bool) constructor.
///
/// If this overload is ever deleted, care should be taken to prevent calls
/// from being incorrectly captured by the APInt(unsigned, uint64_t, bool)
/// constructor.
APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[]);

/// Construct an APInt from a string representation.
///
/// This constructor interprets the string \p str in the given radix. The
/// interpretation stops when the first character that is not suitable for the
/// radix is encountered, or the end of the string. Acceptable radix values
/// are 2, 8, 10, 16, and 36. It is an error for the value implied by the
/// string to require more bits than numBits.
///
/// \param numBits the bit width of the constructed APInt
/// \param str the string to be interpreted
/// \param radix the radix to use for the conversion
APInt(unsigned numBits, StringRef str, uint8_t radix);

/// Simply makes *this a copy of that.
/// Copy Constructor.
APInt(const APInt &that) : BitWidth(that.BitWidth) {
  if (isSingleWord())
    U.VAL = that.U.VAL;
  else
    initSlowCase(that);
}

/// Move Constructor.
APInt(APInt &&that) : BitWidth(that.BitWidth) {
  memcpy(&U, &that.U, sizeof(U));
  that.BitWidth = 0;
}

/// Destructor.
~APInt() {
  if (needsCleanup())
    delete[] U.pVal;
}

/// Default constructor that creates an uninteresting APInt
/// representing a 1-bit zero value.
///
/// This is useful for object deserialization (pair this with the static
///  method Read).
explicit APInt() : BitWidth(1) { U.VAL = 0; }

/// Returns whether this instance allocated memory.
bool needsCleanup() const { return !isSingleWord(); }

/// Used to insert APInt objects, or objects that contain APInt objects, into
///  FoldingSets.
void Profile(FoldingSetNodeID &id) const;

/// @}
/// \name Value Tests
/// @{

/// Determine if this APInt just has one word to store value.
///
/// \returns true if the number of bits <= 64, false otherwise.
bool isSingleWord() const { return BitWidth <= APINT_BITS_PER_WORD; }

/// Determine sign of this APInt.
///
/// This tests the high bit of this APInt to determine if it is set.
///
/// \returns true if this APInt is negative, false otherwise
bool isNegative() const { return (*this)[BitWidth - 1]; }

/// Determine if this APInt Value is non-negative (>= 0)
///
/// This tests the high bit of the APInt to determine if it is unset.
bool isNonNegative() const { return !isNegative(); }

/// Determine if sign bit of this APInt is set.
///
/// This tests the high bit of this APInt to determine if it is set.
///
/// \returns true if this APInt has its sign bit set, false otherwise.
bool isSignBitSet() const { return (*this)[BitWidth-1]; }

/// Determine if sign bit of this APInt is clear.
///
/// This tests the high bit of this APInt to determine if it is clear.
///
/// \returns true if this APInt has its sign bit clear, false otherwise.
bool isSignBitClear() const { return !isSignBitSet(); }

/// Determine if this APInt Value is positive.
///
/// This tests if the value of this APInt is positive (> 0). Note
/// that 0 is not a positive value.
///
/// \returns true if this APInt is positive.
bool isStrictlyPositive() const { return isNonNegative() && !isNullValue(); }

/// Determine if this APInt Value is non-positive (<= 0).
///
/// \returns true if this APInt is non-positive.
bool isNonPositive() const { return !isStrictlyPositive(); }

/// Determine if all bits are set
///
/// This checks to see if the value has all bits of the APInt are set or not.
bool isAllOnesValue() const {
  if (isSingleWord())
    return U.VAL == WORDTYPE_MAX >> (APINT_BITS_PER_WORD - BitWidth);
  return countTrailingOnesSlowCase() == BitWidth;
}

/// Determine if all bits are clear
///
/// This checks to see if the value has all bits of the APInt are clear or
/// not.
bool isNullValue() const { return !*this; }

/// Determine if this is a value of 1.
///
/// This checks to see if the value of this APInt is one.
bool isOneValue() const {
  if (isSingleWord())
    return U.VAL == 1;
  return countLeadingZerosSlowCase() == BitWidth - 1;
}

/// Determine if this is the largest unsigned value.
///
/// This checks to see if the value of this APInt is the maximum unsigned
/// value for the APInt's bit width.
bool isMaxValue() const { return isAllOnesValue(); }

/// Determine if this is the largest signed value.
///
/// This checks to see if the value of this APInt is the maximum signed
/// value for the APInt's bit width.
bool isMaxSignedValue() const {
  if (isSingleWord())
    return U.VAL == ((WordType(1) << (BitWidth - 1)) - 1);
  return !isNegative() && countTrailingOnesSlowCase() == BitWidth - 1;
}

/// Determine if this is the smallest unsigned value.
///
/// This checks to see if the value of this APInt is the minimum unsigned
/// value for the APInt's bit width.
bool isMinValue() const { return isNullValue(); }

/// Determine if this is the smallest signed value.
///
/// This checks to see if the value of this APInt is the minimum signed
/// value for the APInt's bit width.
bool isMinSignedValue() const {
  if (isSingleWord())
    return U.VAL == (WordType(1) << (BitWidth - 1));
  return isNegative() && countTrailingZerosSlowCase() == BitWidth - 1;
}

/// Check if this APInt has an N-bits unsigned integer value.
bool isIntN(unsigned N) const {
  assert(N && "N == 0 ???")((void)0);
  return getActiveBits() <= N;
}

/// Check if this APInt has an N-bits signed integer value.
bool isSignedIntN(unsigned N) const {
  assert(N && "N == 0 ???")((void)0);
  return getMinSignedBits() <= N;
}

/// Check if this APInt's value is a power of two greater than zero.
///
/// \returns true if the argument APInt value is a power of two > 0.
bool isPowerOf2() const {
  if (isSingleWord())
    return isPowerOf2_64(U.VAL);
  return countPopulationSlowCase() == 1;
}

/// Check if the APInt's value is returned by getSignMask.
///
/// \returns true if this is the value returned by getSignMask.
bool isSignMask() const { return isMinSignedValue(); }

/// Convert APInt to a boolean value.
///
/// This converts the APInt to a boolean value as a test against zero.
bool getBoolValue() const { return !!*this; }

/// If this value is smaller than the specified limit, return it, otherwise
/// return the limit value.  This causes the value to saturate to the limit.
uint64_t getLimitedValue(uint64_t Limit = UINT64_MAX0xffffffffffffffffULL) const {
  return ugt(Limit) ? Limit : getZExtValue();
}

/// Check if the APInt consists of a repeated bit pattern.
///
/// e.g. 0x01010101 satisfies isSplat(8).
/// \param SplatSizeInBits The size of the pattern in bits. Must divide bit
/// width without remainder.
bool isSplat(unsigned SplatSizeInBits) const;

/// \returns true if this APInt value is a sequence of \param numBits ones
/// starting at the least significant bit with the remainder zero.
bool isMask(unsigned numBits) const {
  assert(numBits != 0 && "numBits must be non-zero")((void)0);
  assert(numBits <= BitWidth && "numBits out of range")((void)0);
  if (isSingleWord())
    return U.VAL == (WORDTYPE_MAX >> (APINT_BITS_PER_WORD - numBits));
  unsigned Ones = countTrailingOnesSlowCase();
  return (numBits == Ones) &&
         ((Ones + countLeadingZerosSlowCase()) == BitWidth);
}

/// \returns true if this APInt is a non-empty sequence of ones starting at
/// the least significant bit with the remainder zero.
/// Ex. isMask(0x0000FFFFU) == true.
bool isMask() const {
  if (isSingleWord())
    return isMask_64(U.VAL);
  unsigned Ones = countTrailingOnesSlowCase();
  return (Ones > 0) && ((Ones + countLeadingZerosSlowCase()) == BitWidth);
}

/// Return true if this APInt value contains a sequence of ones with
/// the remainder zero.
bool isShiftedMask() const {
  if (isSingleWord())
    return isShiftedMask_64(U.VAL);
  unsigned Ones = countPopulationSlowCase();
  unsigned LeadZ = countLeadingZerosSlowCase();
  return (Ones + LeadZ + countTrailingZeros()) == BitWidth;
}

/// @}
/// \name Value Generators
/// @{

/// Gets maximum unsigned value of APInt for specific bit width.
static APInt getMaxValue(unsigned numBits) {
  return getAllOnesValue(numBits);
}

/// Gets maximum signed value of APInt for a specific bit width.
static APInt getSignedMaxValue(unsigned numBits) {
  APInt API = getAllOnesValue(numBits);
  API.clearBit(numBits - 1);
  return API;
}

/// Gets minimum unsigned value of APInt for a specific bit width.
static APInt getMinValue(unsigned numBits) { return APInt(numBits, 0); }

/// Gets minimum signed value of APInt for a specific bit width.
static APInt getSignedMinValue(unsigned numBits) {
  APInt API(numBits, 0);
  API.setBit(numBits - 1);
  return API;
}

/// Get the SignMask for a specific bit width.
///
/// This is just a wrapper function of getSignedMinValue(), and it helps code
/// readability when we want to get a SignMask.
static APInt getSignMask(unsigned BitWidth) {
  return getSignedMinValue(BitWidth);
}

/// Get the all-ones value.
///
/// \returns the all-ones value for an APInt of the specified bit-width.
static APInt getAllOnesValue(unsigned numBits) {
  return APInt(numBits, WORDTYPE_MAX, true);
}

/// Get the '0' value.
///
/// \returns the '0' value for an APInt of the specified bit-width.
static APInt getNullValue(unsigned numBits) { return APInt(numBits, 0); }

/// Compute an APInt containing numBits highbits from this APInt.
///
/// Get an APInt with the same BitWidth as this APInt, just zero mask
/// the low bits and right shift to the least significant bit.
///
/// \returns the high "numBits" bits of this APInt.
APInt getHiBits(unsigned numBits) const;

/// Compute an APInt containing numBits lowbits from this APInt.
///
/// Get an APInt with the same BitWidth as this APInt, just zero mask
/// the high bits.
///
/// \returns the low "numBits" bits of this APInt.
APInt getLoBits(unsigned numBits) const;

/// Return an APInt with exactly one bit set in the result.
static APInt getOneBitSet(unsigned numBits, unsigned BitNo) {
  APInt Res(numBits, 0);
  Res.setBit(BitNo);
  return Res;
}

/// Get a value with a block of bits set.
///
/// Constructs an APInt value that has a contiguous range of bits set. The
/// bits from loBit (inclusive) to hiBit (exclusive) will be set. All other
/// bits will be zero. For example, with parameters(32, 0, 16) you would get
/// 0x0000FFFF. Please call getBitsSetWithWrap if \p loBit may be greater than
/// \p hiBit.
///
/// \param numBits the intended bit width of the result
/// \param loBit the index of the lowest bit set.
/// \param hiBit the index of the highest bit set.
///
/// \returns An APInt value with the requested bits set.
static APInt getBitsSet(unsigned numBits, unsigned loBit, unsigned hiBit) {
  assert(loBit <= hiBit && "loBit greater than hiBit")((void)0);
  APInt Res(numBits, 0);
  Res.setBits(loBit, hiBit);
  return Res;
}

/// Wrap version of getBitsSet.
/// If \p hiBit is bigger than \p loBit, this is same with getBitsSet.
/// If \p hiBit is not bigger than \p loBit, the set bits "wrap". For example,
/// with parameters (32, 28, 4), you would get 0xF000000F.
/// If \p hiBit is equal to \p loBit, you would get a result with all bits
/// set.
static APInt getBitsSetWithWrap(unsigned numBits, unsigned loBit,
                                unsigned hiBit) {
  APInt Res(numBits, 0);
  Res.setBitsWithWrap(loBit, hiBit);
  return Res;
}

/// Get a value with upper bits starting at loBit set.
///
/// Constructs an APInt value that has a contiguous range of bits set. The
/// bits from loBit (inclusive) to numBits (exclusive) will be set. All other
/// bits will be zero. For example, with parameters(32, 12) you would get
/// 0xFFFFF000.
///
/// \param numBits the intended bit width of the result
/// \param loBit the index of the lowest bit to set.
///
/// \returns An APInt value with the requested bits set.
static APInt getBitsSetFrom(unsigned numBits, unsigned loBit) {
  APInt Res(numBits, 0);
  Res.setBitsFrom(loBit);
  return Res;
}

/// Get a value with high bits set
///
/// Constructs an APInt value that has the top hiBitsSet bits set.
///
/// \param numBits the bitwidth of the result
/// \param hiBitsSet the number of high-order bits set in the result.
static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet) {
  APInt Res(numBits, 0);
  Res.setHighBits(hiBitsSet);
  return Res;
}

/// Get a value with low bits set
///
/// Constructs an APInt value that has the bottom loBitsSet bits set.
///
/// \param numBits the bitwidth of the result
/// \param loBitsSet the number of low-order bits set in the result.
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet) {
  APInt Res(numBits, 0);
  Res.setLowBits(loBitsSet);
  return Res;
}

/// Return a value containing V broadcasted over NewLen bits.
static APInt getSplat(unsigned NewLen, const APInt &V);

/// Determine if two APInts have the same value, after zero-extending
/// one of them (if needed!) to ensure that the bit-widths match.
static bool isSameValue(const APInt &I1, const APInt &I2) {
  if (I1.getBitWidth() == I2.getBitWidth())
    return I1 == I2;

  if (I1.getBitWidth() > I2.getBitWidth())
    return I1 == I2.zext(I1.getBitWidth());

  return I1.zext(I2.getBitWidth()) == I2;
}

/// Overload to compute a hash_code for an APInt value.
friend hash_code hash_value(const APInt &Arg);

/// This function returns a pointer to the internal storage of the APInt.
/// This is useful for writing out the APInt in binary form without any
/// conversions.
const uint64_t *getRawData() const {
  if (isSingleWord())
    return &U.VAL;
  return &U.pVal[0];
}

/// @}
/// \name Unary Operators
/// @{

/// Postfix increment operator.
///
/// Increments *this by 1.
///
/// \returns a new APInt value representing the original value of *this.
const APInt operator++(int) {
  APInt API(*this);
  ++(*this);
  return API;
}

/// Prefix increment operator.
///
/// \returns *this incremented by one
APInt &operator++();

/// Postfix decrement operator.
///
/// Decrements *this by 1.
///
/// \returns a new APInt value representing the original value of *this.
const APInt operator--(int) {
  APInt API(*this);
  --(*this);
  return API;
}

/// Prefix decrement operator.
///
/// \returns *this decremented by one.
APInt &operator--();

/// Logical negation operator.
///
/// Performs logical negation operation on this APInt.
///
/// \returns true if *this is zero, false otherwise.
bool operator!() const {
  if (isSingleWord())
    return U.VAL == 0;
  return countLeadingZerosSlowCase() == BitWidth;
}

/// @}
/// \name Assignment Operators
/// @{

/// Copy assignment operator.
///
/// \returns *this after assignment of RHS.
APInt &operator=(const APInt &RHS) {
  // If the bitwidths are the same, we can avoid mucking with memory
  if (isSingleWord() && RHS.isSingleWord()) {
    U.VAL = RHS.U.VAL;
    BitWidth = RHS.BitWidth;
    return clearUnusedBits();
  }

  AssignSlowCase(RHS);
  return *this;
}

/// Move assignment operator.
APInt &operator=(APInt &&that) {
768#ifdef EXPENSIVE_CHECKS
  // Some std::shuffle implementations still do self-assignment.
  if (this == &that)
    return *this;
772#endif
  assert(this != &that && "Self-move not supported")((void)0);
  if (!isSingleWord())
    delete[] U.pVal;

  // Use memcpy so that type based alias analysis sees both VAL and pVal
  // as modified.
  memcpy(&U, &that.U, sizeof(U));

  BitWidth = that.BitWidth;
  that.BitWidth = 0;

  return *this;
}

/// Assignment operator.
///
/// The RHS value is assigned to *this. If the significant bits in RHS exceed
/// the bit width, the excess bits are truncated. If the bit width is larger
/// than 64, the value is zero filled in the unspecified high order bits.
///
/// \returns *this after assignment of RHS value.
APInt &operator=(uint64_t RHS) {
  if (isSingleWord()) {
28
←
Taking false branch→
    U.VAL = RHS;
    return clearUnusedBits();
  }
  U.pVal[0] = RHS;
29
←
Use of zero-allocated memory
  memset(U.pVal + 1, 0, (getNumWords() - 1) * APINT_WORD_SIZE);
  return *this;
}

/// Bitwise AND assignment operator.
///
/// Performs a bitwise AND operation on this APInt and RHS. The result is
/// assigned to *this.
///
/// \returns *this after ANDing with RHS.
APInt &operator&=(const APInt &RHS) {
  assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")((void)0);
  if (isSingleWord())
    U.VAL &= RHS.U.VAL;
  else
    AndAssignSlowCase(RHS);
  return *this;
}

/// Bitwise AND assignment operator.
///
/// Performs a bitwise AND operation on this APInt and RHS. RHS is
/// logically zero-extended or truncated to match the bit-width of
/// the LHS.
APInt &operator&=(uint64_t RHS) {
  if (isSingleWord()) {
    U.VAL &= RHS;
    return *this;
  }
  U.pVal[0] &= RHS;
  memset(U.pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE);
  return *this;
}

/// Bitwise OR assignment operator.
///
/// Performs a bitwise OR operation on this APInt and RHS. The result is
/// assigned *this;
///
/// \returns *this after ORing with RHS.
APInt &operator|=(const APInt &RHS) {
  assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")((void)0);
  if (isSingleWord())
    U.VAL |= RHS.U.VAL;
  else
    OrAssignSlowCase(RHS);
  return *this;
}

/// Bitwise OR assignment operator.
///
/// Performs a bitwise OR operation on this APInt and RHS. RHS is
/// logically zero-extended or truncated to match the bit-width of
/// the LHS.
APInt &operator|=(uint64_t RHS) {
  if (isSingleWord()) {
    U.VAL |= RHS;
    return clearUnusedBits();
  }
  U.pVal[0] |= RHS;
  return *this;
}

/// Bitwise XOR assignment operator.
///
/// Performs a bitwise XOR operation on this APInt and RHS. The result is
/// assigned to *this.
///
/// \returns *this after XORing with RHS.
APInt &operator^=(const APInt &RHS) {
  assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")((void)0);
  if (isSingleWord())
    U.VAL ^= RHS.U.VAL;
  else
    XorAssignSlowCase(RHS);
  return *this;
}

/// Bitwise XOR assignment operator.
///
/// Performs a bitwise XOR operation on this APInt and RHS. RHS is
/// logically zero-extended or truncated to match the bit-width of
/// the LHS.
APInt &operator^=(uint64_t RHS) {
  if (isSingleWord()) {
    U.VAL ^= RHS;
    return clearUnusedBits();
  }
  U.pVal[0] ^= RHS;
  return *this;
}

/// Multiplication assignment operator.
///
/// Multiplies this APInt by RHS and assigns the result to *this.
///
/// \returns *this
APInt &operator*=(const APInt &RHS);
APInt &operator*=(uint64_t RHS);

/// Addition assignment operator.
///
/// Adds RHS to *this and assigns the result to *this.
///
/// \returns *this
APInt &operator+=(const APInt &RHS);
APInt &operator+=(uint64_t RHS);

/// Subtraction assignment operator.
///
/// Subtracts RHS from *this and assigns the result to *this.
///
/// \returns *this
APInt &operator-=(const APInt &RHS);
APInt &operator-=(uint64_t RHS);

/// Left-shift assignment function.
///
/// Shifts *this left by shiftAmt and assigns the result to *this.
///
/// \returns *this after shifting left by ShiftAmt
APInt &operator<<=(unsigned ShiftAmt) {
  assert(ShiftAmt <= BitWidth && "Invalid shift amount")((void)0);
  if (isSingleWord()) {
    if (ShiftAmt == BitWidth)
      U.VAL = 0;
    else
      U.VAL <<= ShiftAmt;
    return clearUnusedBits();
  }
  shlSlowCase(ShiftAmt);
  return *this;
}

/// Left-shift assignment function.
///
/// Shifts *this left by shiftAmt and assigns the result to *this.
///
/// \returns *this after shifting left by ShiftAmt
APInt &operator<<=(const APInt &ShiftAmt);

/// @}
/// \name Binary Operators
/// @{

/// Multiplication operator.
///
/// Multiplies this APInt by RHS and returns the result.
APInt operator*(const APInt &RHS) const;

/// Left logical shift operator.
///
/// Shifts this APInt left by \p Bits and returns the result.
APInt operator<<(unsigned Bits) const { return shl(Bits); }

/// Left logical shift operator.
///
/// Shifts this APInt left by \p Bits and returns the result.
APInt operator<<(const APInt &Bits) const { return shl(Bits); }

/// Arithmetic right-shift function.
///
/// Arithmetic right-shift this APInt by shiftAmt.
APInt ashr(unsigned ShiftAmt) const {
  APInt R(*this);
  R.ashrInPlace(ShiftAmt);
  return R;
}

/// Arithmetic right-shift this APInt by ShiftAmt in place.
void ashrInPlace(unsigned ShiftAmt) {
  assert(ShiftAmt <= BitWidth && "Invalid shift amount")((void)0);
  if (isSingleWord()) {
    int64_t SExtVAL = SignExtend64(U.VAL, BitWidth);
    if (ShiftAmt == BitWidth)
      U.VAL = SExtVAL >> (APINT_BITS_PER_WORD - 1); // Fill with sign bit.
    else
      U.VAL = SExtVAL >> ShiftAmt;
    clearUnusedBits();
    return;
  }
  ashrSlowCase(ShiftAmt);
}

/// Logical right-shift function.
///
/// Logical right-shift this APInt by shiftAmt.
APInt lshr(unsigned shiftAmt) const {
  APInt R(*this);
  R.lshrInPlace(shiftAmt);
  return R;
}

/// Logical right-shift this APInt by ShiftAmt in place.
void lshrInPlace(unsigned ShiftAmt) {
  assert(ShiftAmt <= BitWidth && "Invalid shift amount")((void)0);
  if (isSingleWord()) {
    if (ShiftAmt == BitWidth)
      U.VAL = 0;
    else
      U.VAL >>= ShiftAmt;
    return;
  }
  lshrSlowCase(ShiftAmt);
}

/// Left-shift function.
///
/// Left-shift this APInt by shiftAmt.
APInt shl(unsigned shiftAmt) const {
  APInt R(*this);
  R <<= shiftAmt;
  return R;
}

/// Rotate left by rotateAmt.
APInt rotl(unsigned rotateAmt) const;

/// Rotate right by rotateAmt.
APInt rotr(unsigned rotateAmt) const;

/// Arithmetic right-shift function.
///
/// Arithmetic right-shift this APInt by shiftAmt.
APInt ashr(const APInt &ShiftAmt) const {
  APInt R(*this);
  R.ashrInPlace(ShiftAmt);
  return R;
}

/// Arithmetic right-shift this APInt by shiftAmt in place.
void ashrInPlace(const APInt &shiftAmt);

/// Logical right-shift function.
///
/// Logical right-shift this APInt by shiftAmt.
APInt lshr(const APInt &ShiftAmt) const {
  APInt R(*this);
  R.lshrInPlace(ShiftAmt);
  return R;
}

/// Logical right-shift this APInt by ShiftAmt in place.
void lshrInPlace(const APInt &ShiftAmt);

/// Left-shift function.
///
/// Left-shift this APInt by shiftAmt.
APInt shl(const APInt &ShiftAmt) const {
  APInt R(*this);
  R <<= ShiftAmt;
  return R;
}

/// Rotate left by rotateAmt.
APInt rotl(const APInt &rotateAmt) const;

/// Rotate right by rotateAmt.
APInt rotr(const APInt &rotateAmt) const;

/// Unsigned division operation.
///
/// Perform an unsigned divide operation on this APInt by RHS. Both this and
/// RHS are treated as unsigned quantities for purposes of this division.
///
/// \returns a new APInt value containing the division result, rounded towards
/// zero.
APInt udiv(const APInt &RHS) const;
APInt udiv(uint64_t RHS) const;

/// Signed division function for APInt.
///
/// Signed divide this APInt by APInt RHS.
///
/// The result is rounded towards zero.
APInt sdiv(const APInt &RHS) const;
APInt sdiv(int64_t RHS) const;

/// Unsigned remainder operation.
///
/// Perform an unsigned remainder operation on this APInt with RHS being the
/// divisor. Both this and RHS are treated as unsigned quantities for purposes
/// of this operation. Note that this is a true remainder operation and not a
/// modulo operation because the sign follows the sign of the dividend which
/// is *this.
///
/// \returns a new APInt value containing the remainder result
APInt urem(const APInt &RHS) const;
uint64_t urem(uint64_t RHS) const;

/// Function for signed remainder operation.
///
/// Signed remainder operation on APInt.
APInt srem(const APInt &RHS) const;
int64_t srem(int64_t RHS) const;

/// Dual division/remainder interface.
///
/// Sometimes it is convenient to divide two APInt values and obtain both the
/// quotient and remainder. This function does both operations in the same
/// computation making it a little more efficient. The pair of input arguments
/// may overlap with the pair of output arguments. It is safe to call
/// udivrem(X, Y, X, Y), for example.
static void udivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient,
                    APInt &Remainder);
static void udivrem(const APInt &LHS, uint64_t RHS, APInt &Quotient,
                    uint64_t &Remainder);

static void sdivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient,
                    APInt &Remainder);
static void sdivrem(const APInt &LHS, int64_t RHS, APInt &Quotient,
                    int64_t &Remainder);

// Operations that return overflow indicators.
APInt sadd_ov(const APInt &RHS, bool &Overflow) const;
APInt uadd_ov(const APInt &RHS, bool &Overflow) const;
APInt ssub_ov(const APInt &RHS, bool &Overflow) const;
APInt usub_ov(const APInt &RHS, bool &Overflow) const;
APInt sdiv_ov(const APInt &RHS, bool &Overflow) const;
APInt smul_ov(const APInt &RHS, bool &Overflow) const;
APInt umul_ov(const APInt &RHS, bool &Overflow) const;
APInt sshl_ov(const APInt &Amt, bool &Overflow) const;
APInt ushl_ov(const APInt &Amt, bool &Overflow) const;

// Operations that saturate
APInt sadd_sat(const APInt &RHS) const;
APInt uadd_sat(const APInt &RHS) const;
APInt ssub_sat(const APInt &RHS) const;
APInt usub_sat(const APInt &RHS) const;
APInt smul_sat(const APInt &RHS) const;
APInt umul_sat(const APInt &RHS) const;
APInt sshl_sat(const APInt &RHS) const;
APInt ushl_sat(const APInt &RHS) const;

/// Array-indexing support.
///
/// \returns the bit value at bitPosition
bool operator[](unsigned bitPosition) const {
  assert(bitPosition < getBitWidth() && "Bit position out of bounds!")((void)0);
  return (maskBit(bitPosition) & getWord(bitPosition)) != 0;
}

/// @}
/// \name Comparison Operators
/// @{

/// Equality operator.
///
/// Compares this APInt with RHS for the validity of the equality
/// relationship.
bool operator==(const APInt &RHS) const {
  assert(BitWidth == RHS.BitWidth && "Comparison requires equal bit widths")((void)0);
  if (isSingleWord())
    return U.VAL == RHS.U.VAL;
  return EqualSlowCase(RHS);
}

/// Equality operator.
///
/// Compares this APInt with a uint64_t for the validity of the equality
/// relationship.
///
/// \returns true if *this == Val
bool operator==(uint64_t Val) const {
  return (isSingleWord() || getActiveBits() <= 64) && getZExtValue() == Val;
}

/// Equality comparison.
///
/// Compares this APInt with RHS for the validity of the equality
/// relationship.
///
/// \returns true if *this == Val
bool eq(const APInt &RHS) const { return (*this) == RHS; }

/// Inequality operator.
///
/// Compares this APInt with RHS for the validity of the inequality
/// relationship.
///
/// \returns true if *this != Val
bool operator!=(const APInt &RHS) const { return !((*this) == RHS); }

/// Inequality operator.
///
/// Compares this APInt with a uint64_t for the validity of the inequality
/// relationship.
///
/// \returns true if *this != Val
bool operator!=(uint64_t Val) const { return !((*this) == Val); }

/// Inequality comparison
///
/// Compares this APInt with RHS for the validity of the inequality
/// relationship.
///
/// \returns true if *this != Val
bool ne(const APInt &RHS) const { return !((*this) == RHS); }

/// Unsigned less than comparison
///
/// Regards both *this and RHS as unsigned quantities and compares them for
/// the validity of the less-than relationship.
///
/// \returns true if *this < RHS when both are considered unsigned.
bool ult(const APInt &RHS) const { return compare(RHS) < 0; }

/// Unsigned less than comparison
///
/// Regards both *this as an unsigned quantity and compares it with RHS for
/// the validity of the less-than relationship.
///
/// \returns true if *this < RHS when considered unsigned.
bool ult(uint64_t RHS) const {
  // Only need to check active bits if not a single word.
  return (isSingleWord() || getActiveBits() <= 64) && getZExtValue() < RHS;
}

/// Signed less than comparison
///
/// Regards both *this and RHS as signed quantities and compares them for
/// validity of the less-than relationship.
///
/// \returns true if *this < RHS when both are considered signed.
bool slt(const APInt &RHS) const { return compareSigned(RHS) < 0; }

/// Signed less than comparison
///
/// Regards both *this as a signed quantity and compares it with RHS for
/// the validity of the less-than relationship.
///
/// \returns true if *this < RHS when considered signed.
bool slt(int64_t RHS) const {
  return (!isSingleWord() && getMinSignedBits() > 64) ? isNegative()
                                                      : getSExtValue() < RHS;
}

/// Unsigned less or equal comparison
///
/// Regards both *this and RHS as unsigned quantities and compares them for
/// validity of the less-or-equal relationship.
///
/// \returns true if *this <= RHS when both are considered unsigned.
bool ule(const APInt &RHS) const { return compare(RHS) <= 0; }

/// Unsigned less or equal comparison
///
/// Regards both *this as an unsigned quantity and compares it with RHS for
/// the validity of the less-or-equal relationship.
///
/// \returns true if *this <= RHS when considered unsigned.
bool ule(uint64_t RHS) const { return !ugt(RHS); }

/// Signed less or equal comparison
///
/// Regards both *this and RHS as signed quantities and compares them for
/// validity of the less-or-equal relationship.
///
/// \returns true if *this <= RHS when both are considered signed.
bool sle(const APInt &RHS) const { return compareSigned(RHS) <= 0; }

/// Signed less or equal comparison
///
/// Regards both *this as a signed quantity and compares it with RHS for the
/// validity of the less-or-equal relationship.
///
/// \returns true if *this <= RHS when considered signed.
bool sle(uint64_t RHS) const { return !sgt(RHS); }

/// Unsigned greater than comparison
///
/// Regards both *this and RHS as unsigned quantities and compares them for
/// the validity of the greater-than relationship.
///
/// \returns true if *this > RHS when both are considered unsigned.
bool ugt(const APInt &RHS) const { return !ule(RHS); }

/// Unsigned greater than comparison
///
/// Regards both *this as an unsigned quantity and compares it with RHS for
/// the validity of the greater-than relationship.
///
/// \returns true if *this > RHS when considered unsigned.
bool ugt(uint64_t RHS) const {
  // Only need to check active bits if not a single word.
  return (!isSingleWord() && getActiveBits() > 64) || getZExtValue() > RHS;
}

/// Signed greater than comparison
///
/// Regards both *this and RHS as signed quantities and compares them for the
/// validity of the greater-than relationship.
///
/// \returns true if *this > RHS when both are considered signed.
bool sgt(const APInt &RHS) const { return !sle(RHS); }

/// Signed greater than comparison
///
/// Regards both *this as a signed quantity and compares it with RHS for
/// the validity of the greater-than relationship.
///
/// \returns true if *this > RHS when considered signed.
bool sgt(int64_t RHS) const {
  return (!isSingleWord() && getMinSignedBits() > 64) ? !isNegative()
                                                      : getSExtValue() > RHS;
}

/// Unsigned greater or equal comparison
///
/// Regards both *this and RHS as unsigned quantities and compares them for
/// validity of the greater-or-equal relationship.
///
/// \returns true if *this >= RHS when both are considered unsigned.
bool uge(const APInt &RHS) const { return !ult(RHS); }

/// Unsigned greater or equal comparison
///
/// Regards both *this as an unsigned quantity and compares it with RHS for
/// the validity of the greater-or-equal relationship.
///
/// \returns true if *this >= RHS when considered unsigned.
bool uge(uint64_t RHS) const { return !ult(RHS); }

/// Signed greater or equal comparison
///
/// Regards both *this and RHS as signed quantities and compares them for
/// validity of the greater-or-equal relationship.
///
/// \returns true if *this >= RHS when both are considered signed.
bool sge(const APInt &RHS) const { return !slt(RHS); }

/// Signed greater or equal comparison
///
/// Regards both *this as a signed quantity and compares it with RHS for
/// the validity of the greater-or-equal relationship.
///
/// \returns true if *this >= RHS when considered signed.
bool sge(int64_t RHS) const { return !slt(RHS); }

/// This operation tests if there are any pairs of corresponding bits
/// between this APInt and RHS that are both set.
bool intersects(const APInt &RHS) const {
  assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")((void)0);
  if (isSingleWord())
    return (U.VAL & RHS.U.VAL) != 0;
  return intersectsSlowCase(RHS);
}

/// This operation checks that all bits set in this APInt are also set in RHS.
bool isSubsetOf(const APInt &RHS) const {
  assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")((void)0);
  if (isSingleWord())
    return (U.VAL & ~RHS.U.VAL) == 0;
  return isSubsetOfSlowCase(RHS);
}

/// @}
/// \name Resizing Operators
/// @{

/// Truncate to new width.
///
/// Truncate the APInt to a specified width. It is an error to specify a width
/// that is greater than or equal to the current width.
APInt trunc(unsigned width) const;

/// Truncate to new width with unsigned saturation.
///
/// If the APInt, treated as unsigned integer, can be losslessly truncated to
/// the new bitwidth, then return truncated APInt. Else, return max value.
APInt truncUSat(unsigned width) const;

/// Truncate to new width with signed saturation.
///
/// If this APInt, treated as signed integer, can be losslessly truncated to
/// the new bitwidth, then return truncated APInt. Else, return either
/// signed min value if the APInt was negative, or signed max value.
APInt truncSSat(unsigned width) const;

/// Sign extend to a new width.
///
/// This operation sign extends the APInt to a new width. If the high order
/// bit is set, the fill on the left will be done with 1 bits, otherwise zero.
/// It is an error to specify a width that is less than or equal to the
/// current width.
APInt sext(unsigned width) const;

/// Zero extend to a new width.
///
/// This operation zero extends the APInt to a new width. The high order bits
/// are filled with 0 bits.  It is an error to specify a width that is less
/// than or equal to the current width.
APInt zext(unsigned width) const;

/// Sign extend or truncate to width
///
/// Make this APInt have the bit width given by \p width. The value is sign
/// extended, truncated, or left alone to make it that width.
APInt sextOrTrunc(unsigned width) const;

/// Zero extend or truncate to width
///
/// Make this APInt have the bit width given by \p width. The value is zero
/// extended, truncated, or left alone to make it that width.
APInt zextOrTrunc(unsigned width) const;

/// Truncate to width
///
/// Make this APInt have the bit width given by \p width. The value is
/// truncated or left alone to make it that width.
APInt truncOrSelf(unsigned width) const;

/// Sign extend or truncate to width
///
/// Make this APInt have the bit width given by \p width. The value is sign
/// extended, or left alone to make it that width.
APInt sextOrSelf(unsigned width) const;

/// Zero extend or truncate to width
///
/// Make this APInt have the bit width given by \p width. The value is zero
/// extended, or left alone to make it that width.
APInt zextOrSelf(unsigned width) const;

/// @}
/// \name Bit Manipulation Operators
/// @{

/// Set every bit to 1.
void setAllBits() {
  if (isSingleWord())
    U.VAL = WORDTYPE_MAX;
  else
    // Set all the bits in all the words.
    memset(U.pVal, -1, getNumWords() * APINT_WORD_SIZE);
  // Clear the unused ones
  clearUnusedBits();
}

/// Set a given bit to 1.
///
/// Set the given bit to 1 whose position is given as "bitPosition".
void setBit(unsigned BitPosition) {
  assert(BitPosition < BitWidth && "BitPosition out of range")((void)0);
  WordType Mask = maskBit(BitPosition);
  if (isSingleWord())
    U.VAL |= Mask;
  else
    U.pVal[whichWord(BitPosition)] |= Mask;
}

/// Set the sign bit to 1.
void setSignBit() {
  setBit(BitWidth - 1);
}

/// Set a given bit to a given value.
void setBitVal(unsigned BitPosition, bool BitValue) {
  if (BitValue)
    setBit(BitPosition);
  else
    clearBit(BitPosition);
}

/// Set the bits from loBit (inclusive) to hiBit (exclusive) to 1.
/// This function handles "wrap" case when \p loBit >= \p hiBit, and calls
/// setBits when \p loBit < \p hiBit.
/// For \p loBit == \p hiBit wrap case, set every bit to 1.
void setBitsWithWrap(unsigned loBit, unsigned hiBit) {
  assert(hiBit <= BitWidth && "hiBit out of range")((void)0);
  assert(loBit <= BitWidth && "loBit out of range")((void)0);
  if (loBit < hiBit) {
    setBits(loBit, hiBit);
    return;
  }
  setLowBits(hiBit);
  setHighBits(BitWidth - loBit);
}

/// Set the bits from loBit (inclusive) to hiBit (exclusive) to 1.
/// This function handles case when \p loBit <= \p hiBit.
void setBits(unsigned loBit, unsigned hiBit) {
  assert(hiBit <= BitWidth && "hiBit out of range")((void)0);
  assert(loBit <= BitWidth && "loBit out of range")((void)0);
  assert(loBit <= hiBit && "loBit greater than hiBit")((void)0);
  if (loBit == hiBit)
    return;
  if (loBit < APINT_BITS_PER_WORD && hiBit <= APINT_BITS_PER_WORD) {
    uint64_t mask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - (hiBit - loBit));
    mask <<= loBit;
    if (isSingleWord())
      U.VAL |= mask;
    else
      U.pVal[0] |= mask;
  } else {
    setBitsSlowCase(loBit, hiBit);
  }
}

/// Set the top bits starting from loBit.
void setBitsFrom(unsigned loBit) {
  return setBits(loBit, BitWidth);
}

/// Set the bottom loBits bits.
void setLowBits(unsigned loBits) {
  return setBits(0, loBits);
}

/// Set the top hiBits bits.
void setHighBits(unsigned hiBits) {
  return setBits(BitWidth - hiBits, BitWidth);
}

/// Set every bit to 0.
void clearAllBits() {
  if (isSingleWord())
    U.VAL = 0;
  else
    memset(U.pVal, 0, getNumWords() * APINT_WORD_SIZE);
}

/// Set a given bit to 0.
///
/// Set the given bit to 0 whose position is given as "bitPosition".
void clearBit(unsigned BitPosition) {
  assert(BitPosition < BitWidth && "BitPosition out of range")((void)0);
  WordType Mask = ~maskBit(BitPosition);
  if (isSingleWord())
    U.VAL &= Mask;
  else
    U.pVal[whichWord(BitPosition)] &= Mask;
}

/// Set bottom loBits bits to 0.
void clearLowBits(unsigned loBits) {
  assert(loBits <= BitWidth && "More bits than bitwidth")((void)0);
  APInt Keep = getHighBitsSet(BitWidth, BitWidth - loBits);
  *this &= Keep;
}

/// Set the sign bit to 0.
void clearSignBit() {
  clearBit(BitWidth - 1);
}

/// Toggle every bit to its opposite value.
void flipAllBits() {
  if (isSingleWord()) {
    U.VAL ^= WORDTYPE_MAX;
    clearUnusedBits();
  } else {
    flipAllBitsSlowCase();
  }
}

/// Toggles a given bit to its opposite value.
///
/// Toggle a given bit to its opposite value whose position is given
/// as "bitPosition".
void flipBit(unsigned bitPosition);

/// Negate this APInt in place.
void negate() {
  flipAllBits();
  ++(*this);
}

/// Insert the bits from a smaller APInt starting at bitPosition.
void insertBits(const APInt &SubBits, unsigned bitPosition);
void insertBits(uint64_t SubBits, unsigned bitPosition, unsigned numBits);

/// Return an APInt with the extracted bits [bitPosition,bitPosition+numBits).
APInt extractBits(unsigned numBits, unsigned bitPosition) const;
uint64_t extractBitsAsZExtValue(unsigned numBits, unsigned bitPosition) const;

/// @}
/// \name Value Characterization Functions
/// @{

/// Return the number of bits in the APInt.
unsigned getBitWidth() const { return BitWidth; }

/// Get the number of words.
///
/// Here one word's bitwidth equals to that of uint64_t.
///
/// \returns the number of words to hold the integer value of this APInt.
unsigned getNumWords() const { return getNumWords(BitWidth); }

/// Get the number of words.
///
/// *NOTE* Here one word's bitwidth equals to that of uint64_t.
///
/// \returns the number of words to hold the integer value with a given bit
/// width.
static unsigned getNumWords(unsigned BitWidth) {
  return ((uint64_t)BitWidth + APINT_BITS_PER_WORD - 1) / APINT_BITS_PER_WORD;
}

/// Compute the number of active bits in the value
///
/// This function returns the number of active bits which is defined as the
/// bit width minus the number of leading zeros. This is used in several
/// computations to see how "wide" the value is.
unsigned getActiveBits() const { return BitWidth - countLeadingZeros(); }

/// Compute the number of active words in the value of this APInt.
///
/// This is used in conjunction with getActiveData to extract the raw value of
/// the APInt.
unsigned getActiveWords() const {
  unsigned numActiveBits = getActiveBits();
  return numActiveBits ? whichWord(numActiveBits - 1) + 1 : 1;
}

/// Get the minimum bit size for this signed APInt
///
/// Computes the minimum bit width for this APInt while considering it to be a
/// signed (and probably negative) value. If the value is not negative, this
/// function returns the same value as getActiveBits()+1. Otherwise, it
/// returns the smallest bit width that will retain the negative value. For
/// example, -1 can be written as 0b1 or 0xFFFFFFFFFF. 0b1 is shorter and so
/// for -1, this function will always return 1.
unsigned getMinSignedBits() const { return BitWidth - getNumSignBits() + 1; }

/// Get zero extended value
///
/// This method attempts to return the value of this APInt as a zero extended
/// uint64_t. The bitwidth must be <= 64 or the value must fit within a
/// uint64_t. Otherwise an assertion will result.
uint64_t getZExtValue() const {
  if (isSingleWord())
    return U.VAL;
  assert(getActiveBits() <= 64 && "Too many bits for uint64_t")((void)0);
  return U.pVal[0];
}

/// Get sign extended value
///
/// This method attempts to return the value of this APInt as a sign extended
/// int64_t. The bit width must be <= 64 or the value must fit within an
/// int64_t. Otherwise an assertion will result.
int64_t getSExtValue() const {
  if (isSingleWord())
    return SignExtend64(U.VAL, BitWidth);
  assert(getMinSignedBits() <= 64 && "Too many bits for int64_t")((void)0);
  return int64_t(U.pVal[0]);
}

/// Get bits required for string value.
///
/// This method determines how many bits are required to hold the APInt
/// equivalent of the string given by \p str.
static unsigned getBitsNeeded(StringRef str, uint8_t radix);

/// The APInt version of the countLeadingZeros functions in
///   MathExtras.h.
///
/// It counts the number of zeros from the most significant bit to the first
/// one bit.
///
/// \returns BitWidth if the value is zero, otherwise returns the number of
///   zeros from the most significant bit to the first one bits.
unsigned countLeadingZeros() const {
  if (isSingleWord()) {
    unsigned unusedBits = APINT_BITS_PER_WORD - BitWidth;
    return llvm::countLeadingZeros(U.VAL) - unusedBits;
  }
  return countLeadingZerosSlowCase();
}

/// Count the number of leading one bits.
///
/// This function is an APInt version of the countLeadingOnes
/// functions in MathExtras.h. It counts the number of ones from the most
/// significant bit to the first zero bit.
///
/// \returns 0 if the high order bit is not set, otherwise returns the number
/// of 1 bits from the most significant to the least
unsigned countLeadingOnes() const {
  if (isSingleWord())
    return llvm::countLeadingOnes(U.VAL << (APINT_BITS_PER_WORD - BitWidth));
  return countLeadingOnesSlowCase();
}

/// Computes the number of leading bits of this APInt that are equal to its
/// sign bit.
unsigned getNumSignBits() const {
  return isNegative() ? countLeadingOnes() : countLeadingZeros();
}

/// Count the number of trailing zero bits.
///
/// This function is an APInt version of the countTrailingZeros
/// functions in MathExtras.h. It counts the number of zeros from the least
/// significant bit to the first set bit.
///
/// \returns BitWidth if the value is zero, otherwise returns the number of
/// zeros from the least significant bit to the first one bit.
unsigned countTrailingZeros() const {
  if (isSingleWord()) {
    unsigned TrailingZeros = llvm::countTrailingZeros(U.VAL);
    return (TrailingZeros > BitWidth ? BitWidth : TrailingZeros);
  }
  return countTrailingZerosSlowCase();
}

/// Count the number of trailing one bits.
///
/// This function is an APInt version of the countTrailingOnes
/// functions in MathExtras.h. It counts the number of ones from the least
/// significant bit to the first zero bit.
///
/// \returns BitWidth if the value is all ones, otherwise returns the number
/// of ones from the least significant bit to the first zero bit.
unsigned countTrailingOnes() const {
  if (isSingleWord())
    return llvm::countTrailingOnes(U.VAL);
  return countTrailingOnesSlowCase();
}

/// Count the number of bits set.
///
/// This function is an APInt version of the countPopulation functions
/// in MathExtras.h. It counts the number of 1 bits in the APInt value.
///
/// \returns 0 if the value is zero, otherwise returns the number of set bits.
unsigned countPopulation() const {
  if (isSingleWord())
    return llvm::countPopulation(U.VAL);
  return countPopulationSlowCase();
}

/// @}
/// \name Conversion Functions
/// @{
void print(raw_ostream &OS, bool isSigned) const;

/// Converts an APInt to a string and append it to Str.  Str is commonly a
/// SmallString.
void toString(SmallVectorImpl<char> &Str, unsigned Radix, bool Signed,
              bool formatAsCLiteral = false) const;

/// Considers the APInt to be unsigned and converts it into a string in the
/// radix given. The radix can be 2, 8, 10 16, or 36.
void toStringUnsigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const {
  toString(Str, Radix, false, false);
}

/// Considers the APInt to be signed and converts it into a string in the
/// radix given. The radix can be 2, 8, 10, 16, or 36.
void toStringSigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const {
  toString(Str, Radix, true, false);
}

/// \returns a byte-swapped representation of this APInt Value.
APInt byteSwap() const;

/// \returns the value with the bit representation reversed of this APInt
/// Value.
APInt reverseBits() const;

/// Converts this APInt to a double value.
double roundToDouble(bool isSigned) const;

/// Converts this unsigned APInt to a double value.
double roundToDouble() const { return roundToDouble(false); }

/// Converts this signed APInt to a double value.
double signedRoundToDouble() const { return roundToDouble(true); }

/// Converts APInt bits to a double
///
/// The conversion does not do a translation from integer to double, it just
/// re-interprets the bits as a double. Note that it is valid to do this on
/// any bit width. Exactly 64 bits will be translated.
double bitsToDouble() const {
  return BitsToDouble(getWord(0));
}

/// Converts APInt bits to a float
///
/// The conversion does not do a translation from integer to float, it just
/// re-interprets the bits as a float. Note that it is valid to do this on
/// any bit width. Exactly 32 bits will be translated.
float bitsToFloat() const {
  return BitsToFloat(static_cast<uint32_t>(getWord(0)));
}

/// Converts a double to APInt bits.
///
/// The conversion does not do a translation from double to integer, it just
/// re-interprets the bits of the double.
static APInt doubleToBits(double V) {
  return APInt(sizeof(double) * CHAR_BIT8, DoubleToBits(V));
}

/// Converts a float to APInt bits.
///
/// The conversion does not do a translation from float to integer, it just
/// re-interprets the bits of the float.
static APInt floatToBits(float V) {
  return APInt(sizeof(float) * CHAR_BIT8, FloatToBits(V));
}

/// @}
/// \name Mathematics Operations
/// @{

/// \returns the floor log base 2 of this APInt.
unsigned logBase2() const { return getActiveBits() -  1; }

/// \returns the ceil log base 2 of this APInt.
unsigned ceilLogBase2() const {
  APInt temp(*this);
  --temp;
  return temp.getActiveBits();
}

/// \returns the nearest log base 2 of this APInt. Ties round up.
///
/// NOTE: When we have a BitWidth of 1, we define:
///
///   log2(0) = UINT32_MAX
///   log2(1) = 0
///
/// to get around any mathematical concerns resulting from
/// referencing 2 in a space where 2 does no exist.
unsigned nearestLogBase2() const {
  // Special case when we have a bitwidth of 1. If VAL is 1, then we
  // get 0. If VAL is 0, we get WORDTYPE_MAX which gets truncated to
  // UINT32_MAX.
  if (BitWidth == 1)
    return U.VAL - 1;

  // Handle the zero case.
  if (isNullValue())
    return UINT32_MAX0xffffffffU;

  // The non-zero case is handled by computing:
  //
  //   nearestLogBase2(x) = logBase2(x) + x[logBase2(x)-1].
  //
  // where x[i] is referring to the value of the ith bit of x.
  unsigned lg = logBase2();
  return lg + unsigned((*this)[lg - 1]);
}

/// \returns the log base 2 of this APInt if its an exact power of two, -1
/// otherwise
int32_t exactLogBase2() const {
  if (!isPowerOf2())
    return -1;
  return logBase2();
}

/// Compute the square root
APInt sqrt() const;

/// Get the absolute value;
///
/// If *this is < 0 then return -(*this), otherwise *this;
APInt abs() const {
  if (isNegative())
    return -(*this);
  return *this;
}

/// \returns the multiplicative inverse for a given modulo.
APInt multiplicativeInverse(const APInt &modulo) const;

/// @}
/// \name Support for division by constant
/// @{

/// Calculate the magic number for signed division by a constant.
struct ms;
ms magic() const;

/// Calculate the magic number for unsigned division by a constant.
struct mu;
mu magicu(unsigned LeadingZeros = 0) const;

/// @}
/// \name Building-block Operations for APInt and APFloat
/// @{

// These building block operations operate on a representation of arbitrary
// precision, two's-complement, bignum integer values. They should be
// sufficient to implement APInt and APFloat bignum requirements. Inputs are
// generally a pointer to the base of an array of integer parts, representing
// an unsigned bignum, and a count of how many parts there are.

/// Sets the least significant part of a bignum to the input value, and zeroes
/// out higher parts.
static void tcSet(WordType *, WordType, unsigned);

/// Assign one bignum to another.
static void tcAssign(WordType *, const WordType *, unsigned);

/// Returns true if a bignum is zero, false otherwise.
static bool tcIsZero(const WordType *, unsigned);

/// Extract the given bit of a bignum; returns 0 or 1.  Zero-based.
static int tcExtractBit(const WordType *, unsigned bit);

/// Copy the bit vector of width srcBITS from SRC, starting at bit srcLSB, to
/// DST, of dstCOUNT parts, such that the bit srcLSB becomes the least
/// significant bit of DST.  All high bits above srcBITS in DST are
/// zero-filled.
static void tcExtract(WordType *, unsigned dstCount,
                      const WordType *, unsigned srcBits,
                      unsigned srcLSB);

/// Set the given bit of a bignum.  Zero-based.
static void tcSetBit(WordType *, unsigned bit);

/// Clear the given bit of a bignum.  Zero-based.
static void tcClearBit(WordType *, unsigned bit);

/// Returns the bit number of the least or most significant set bit of a
/// number.  If the input number has no bits set -1U is returned.
static unsigned tcLSB(const WordType *, unsigned n);
static unsigned tcMSB(const WordType *parts, unsigned n);

/// Negate a bignum in-place.
static void tcNegate(WordType *, unsigned);

/// DST += RHS + CARRY where CARRY is zero or one.  Returns the carry flag.
static WordType tcAdd(WordType *, const WordType *,
                      WordType carry, unsigned);
/// DST += RHS.  Returns the carry flag.
static WordType tcAddPart(WordType *, WordType, unsigned);

/// DST -= RHS + CARRY where CARRY is zero or one. Returns the carry flag.
static WordType tcSubtract(WordType *, const WordType *,
                           WordType carry, unsigned);
/// DST -= RHS.  Returns the carry flag.
static WordType tcSubtractPart(WordType *, WordType, unsigned);

/// DST += SRC * MULTIPLIER + PART   if add is true
/// DST  = SRC * MULTIPLIER + PART   if add is false
///
/// Requires 0 <= DSTPARTS <= SRCPARTS + 1.  If DST overlaps SRC they must
/// start at the same point, i.e. DST == SRC.
///
/// If DSTPARTS == SRC_PARTS + 1 no overflow occurs and zero is returned.
/// Otherwise DST is filled with the least significant DSTPARTS parts of the
/// result, and if all of the omitted higher parts were zero return zero,
/// otherwise overflow occurred and return one.
static int tcMultiplyPart(WordType *dst, const WordType *src,
                          WordType multiplier, WordType carry,
                          unsigned srcParts, unsigned dstParts,
                          bool add);

/// DST = LHS * RHS, where DST has the same width as the operands and is
/// filled with the least significant parts of the result.  Returns one if
/// overflow occurred, otherwise zero.  DST must be disjoint from both
/// operands.
static int tcMultiply(WordType *, const WordType *, const WordType *,
                      unsigned);

/// DST = LHS * RHS, where DST has width the sum of the widths of the
/// operands. No overflow occurs. DST must be disjoint from both operands.
static void tcFullMultiply(WordType *, const WordType *,
                           const WordType *, unsigned, unsigned);

/// If RHS is zero LHS and REMAINDER are left unchanged, return one.
/// Otherwise set LHS to LHS / RHS with the fractional part discarded, set
/// REMAINDER to the remainder, return zero.  i.e.
///
///  OLD_LHS = RHS * LHS + REMAINDER
///
/// SCRATCH is a bignum of the same size as the operands and result for use by
/// the routine; its contents need not be initialized and are destroyed.  LHS,
/// REMAINDER and SCRATCH must be distinct.
static int tcDivide(WordType *lhs, const WordType *rhs,
                    WordType *remainder, WordType *scratch,
                    unsigned parts);

/// Shift a bignum left Count bits. Shifted in bits are zero. There are no
/// restrictions on Count.
static void tcShiftLeft(WordType *, unsigned Words, unsigned Count);

/// Shift a bignum right Count bits.  Shifted in bits are zero.  There are no
/// restrictions on Count.
static void tcShiftRight(WordType *, unsigned Words, unsigned Count);

/// The obvious AND, OR and XOR and complement operations.
static void tcAnd(WordType *, const WordType *, unsigned);
static void tcOr(WordType *, const WordType *, unsigned);
static void tcXor(WordType *, const WordType *, unsigned);
static void tcComplement(WordType *, unsigned);

/// Comparison (unsigned) of two bignums.
static int tcCompare(const WordType *, const WordType *, unsigned);

/// Increment a bignum in-place.  Return the carry flag.
static WordType tcIncrement(WordType *dst, unsigned parts) {
  return tcAddPart(dst, 1, parts);
}

/// Decrement a bignum in-place.  Return the borrow flag.
static WordType tcDecrement(WordType *dst, unsigned parts) {
  return tcSubtractPart(dst, 1, parts);
}

/// Set the least significant BITS and clear the rest.
static void tcSetLeastSignificantBits(WordType *, unsigned, unsigned bits);

/// debug method
void dump() const;

/// @}
2015};

2017/// Magic data for optimising signed division by a constant.
2018struct APInt::ms {
APInt m;    ///< magic number
unsigned s; ///< shift amount
2021};

2023/// Magic data for optimising unsigned division by a constant.
2024struct APInt::mu {
APInt m;    ///< magic number
bool a;     ///< add indicator
unsigned s; ///< shift amount
2028};

2030inline bool operator==(uint64_t V1, const APInt &V2) { return V2 == V1; }

2032inline bool operator!=(uint64_t V1, const APInt &V2) { return V2 != V1; }

2034/// Unary bitwise complement operator.
2035///
2036/// \returns an APInt that is the bitwise complement of \p v.
2037inline APInt operator~(APInt v) {
v.flipAllBits();
return v;
2040}

2042inline APInt operator&(APInt a, const APInt &b) {
a &= b;
return a;
2045}

2047inline APInt operator&(const APInt &a, APInt &&b) {
b &= a;
return std::move(b);
2050}

2052inline APInt operator&(APInt a, uint64_t RHS) {
a &= RHS;
return a;
2055}

2057inline APInt operator&(uint64_t LHS, APInt b) {
b &= LHS;
return b;
2060}

2062inline APInt operator|(APInt a, const APInt &b) {
a |= b;
return a;
2065}

2067inline APInt operator|(const APInt &a, APInt &&b) {
b |= a;
return std::move(b);
2070}

2072inline APInt operator|(APInt a, uint64_t RHS) {
a |= RHS;
return a;
2075}

2077inline APInt operator|(uint64_t LHS, APInt b) {
b |= LHS;
return b;
2080}

2082inline APInt operator^(APInt a, const APInt &b) {
a ^= b;
return a;
2085}

2087inline APInt operator^(const APInt &a, APInt &&b) {
b ^= a;
return std::move(b);
2090}

2092inline APInt operator^(APInt a, uint64_t RHS) {
a ^= RHS;
return a;
2095}

2097inline APInt operator^(uint64_t LHS, APInt b) {
b ^= LHS;
return b;
2100}

2102inline raw_ostream &operator<<(raw_ostream &OS, const APInt &I) {
I.print(OS, true);
return OS;
2105}

2107inline APInt operator-(APInt v) {
v.negate();
return v;
2110}

2112inline APInt operator+(APInt a, const APInt &b) {
a += b;
return a;
2115}

2117inline APInt operator+(const APInt &a, APInt &&b) {
b += a;
return std::move(b);
2120}

2122inline APInt operator+(APInt a, uint64_t RHS) {
a += RHS;
return a;
2125}

2127inline APInt operator+(uint64_t LHS, APInt b) {
b += LHS;
return b;
2130}

2132inline APInt operator-(APInt a, const APInt &b) {
a -= b;
return a;
2135}

2137inline APInt operator-(const APInt &a, APInt &&b) {
b.negate();
b += a;
return std::move(b);
2141}

2143inline APInt operator-(APInt a, uint64_t RHS) {
a -= RHS;
return a;
2146}

2148inline APInt operator-(uint64_t LHS, APInt b) {
b.negate();
b += LHS;
return b;
2152}

2154inline APInt operator*(APInt a, uint64_t RHS) {
a *= RHS;
return a;
2157}

2159inline APInt operator*(uint64_t LHS, APInt b) {
b *= LHS;
return b;
2162}


2165namespace APIntOps {

2167/// Determine the smaller of two APInts considered to be signed.
2168inline const APInt &smin(const APInt &A, const APInt &B) {
return A.slt(B) ? A : B;
2170}

2172/// Determine the larger of two APInts considered to be signed.
2173inline const APInt &smax(const APInt &A, const APInt &B) {
return A.sgt(B) ? A : B;
2175}

2177/// Determine the smaller of two APInts considered to be unsigned.
2178inline const APInt &umin(const APInt &A, const APInt &B) {
return A.ult(B) ? A : B;
2180}

2182/// Determine the larger of two APInts considered to be unsigned.
2183inline const APInt &umax(const APInt &A, const APInt &B) {
return A.ugt(B) ? A : B;
2185}

2187/// Compute GCD of two unsigned APInt values.
2188///
2189/// This function returns the greatest common divisor of the two APInt values
2190/// using Stein's algorithm.
2191///
2192/// \returns the greatest common divisor of A and B.
2193APInt GreatestCommonDivisor(APInt A, APInt B);

2195/// Converts the given APInt to a double value.
2196///
2197/// Treats the APInt as an unsigned value for conversion purposes.
2198inline double RoundAPIntToDouble(const APInt &APIVal) {
return APIVal.roundToDouble();
2200}

2202/// Converts the given APInt to a double value.
2203///
2204/// Treats the APInt as a signed value for conversion purposes.
2205inline double RoundSignedAPIntToDouble(const APInt &APIVal) {
return APIVal.signedRoundToDouble();
2207}

2209/// Converts the given APInt to a float value.
2210inline float RoundAPIntToFloat(const APInt &APIVal) {
return float(RoundAPIntToDouble(APIVal));
2212}

2214/// Converts the given APInt to a float value.
2215///
2216/// Treats the APInt as a signed value for conversion purposes.
2217inline float RoundSignedAPIntToFloat(const APInt &APIVal) {
return float(APIVal.signedRoundToDouble());
2219}

2221/// Converts the given double value into a APInt.
2222///
2223/// This function convert a double value to an APInt value.
2224APInt RoundDoubleToAPInt(double Double, unsigned width);

2226/// Converts a float value into a APInt.
2227///
2228/// Converts a float value into an APInt value.
2229inline APInt RoundFloatToAPInt(float Float, unsigned width) {
return RoundDoubleToAPInt(double(Float), width);
2231}

2233/// Return A unsign-divided by B, rounded by the given rounding mode.
2234APInt RoundingUDiv(const APInt &A, const APInt &B, APInt::Rounding RM);

2236/// Return A sign-divided by B, rounded by the given rounding mode.
2237APInt RoundingSDiv(const APInt &A, const APInt &B, APInt::Rounding RM);

2239/// Let q(n) = An^2 + Bn + C, and BW = bit width of the value range
2240/// (e.g. 32 for i32).
2241/// This function finds the smallest number n, such that
2242/// (a) n >= 0 and q(n) = 0, or
2243/// (b) n >= 1 and q(n-1) and q(n), when evaluated in the set of all
2244///     integers, belong to two different intervals [Rk, Rk+R),
2245///     where R = 2^BW, and k is an integer.
2246/// The idea here is to find when q(n) "overflows" 2^BW, while at the
2247/// same time "allowing" subtraction. In unsigned modulo arithmetic a
2248/// subtraction (treated as addition of negated numbers) would always
2249/// count as an overflow, but here we want to allow values to decrease
2250/// and increase as long as they are within the same interval.
2251/// Specifically, adding of two negative numbers should not cause an
2252/// overflow (as long as the magnitude does not exceed the bit width).
2253/// On the other hand, given a positive number, adding a negative
2254/// number to it can give a negative result, which would cause the
2255/// value to go from [-2^BW, 0) to [0, 2^BW). In that sense, zero is
2256/// treated as a special case of an overflow.
2257///
2258/// This function returns None if after finding k that minimizes the
2259/// positive solution to q(n) = kR, both solutions are contained between
2260/// two consecutive integers.
2261///
2262/// There are cases where q(n) > T, and q(n+1) < T (assuming evaluation
2263/// in arithmetic modulo 2^BW, and treating the values as signed) by the
2264/// virtue of *signed* overflow. This function will *not* find such an n,
2265/// however it may find a value of n satisfying the inequalities due to
2266/// an *unsigned* overflow (if the values are treated as unsigned).
2267/// To find a solution for a signed overflow, treat it as a problem of
2268/// finding an unsigned overflow with a range with of BW-1.
2269///
2270/// The returned value may have a different bit width from the input
2271/// coefficients.
2272Optional<APInt> SolveQuadraticEquationWrap(APInt A, APInt B, APInt C,
                                         unsigned RangeWidth);

2275/// Compare two values, and if they are different, return the position of the
2276/// most significant bit that is different in the values.
2277Optional<unsigned> GetMostSignificantDifferentBit(const APInt &A,
                                                const APInt &B);

2280} // End of APIntOps namespace

2282// See friend declaration above. This additional declaration is required in
2283// order to compile LLVM with IBM xlC compiler.
2284hash_code hash_value(const APInt &Arg);

2286/// StoreIntToMemory - Fills the StoreBytes bytes of memory starting from Dst
2287/// with the integer held in IntVal.
2288void StoreIntToMemory(const APInt &IntVal, uint8_t *Dst, unsigned StoreBytes);

2290/// LoadIntFromMemory - Loads the integer stored in the LoadBytes bytes starting
2291/// from Src into IntVal, which is assumed to be wide enough and to hold zero.
2292void LoadIntFromMemory(APInt &IntVal, const uint8_t *Src, unsigned LoadBytes);

2294/// Provide DenseMapInfo for APInt.
2295template <> struct DenseMapInfo<APInt> {
static inline APInt getEmptyKey() {
  APInt V(nullptr, 0);
  V.U.VAL = 0;
  return V;
}

static inline APInt getTombstoneKey() {
  APInt V(nullptr, 0);
  V.U.VAL = 1;
  return V;
}

static unsigned getHashValue(const APInt &Key);

static bool isEqual(const APInt &LHS, const APInt &RHS) {
  return LHS.getBitWidth() == RHS.getBitWidth() && LHS == RHS;
}
2313};

2315} // namespace llvm

2317#endif