/build/source/llvm/lib/Support/APInt.cpp

Bug Summary

File:	build/source/llvm/lib/Support/APInt.cpp
Warning:	line 86, column 3 Use of memory after it is freed

Annotated Source Code

Press '?' to see keyboard shortcuts

Show analyzer invocation

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name APInt.cpp -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 -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/source/build-llvm/tools/clang/stage2-bins -resource-dir /usr/lib/llvm-17/lib/clang/17 -D _DEBUG -D _GLIBCXX_ASSERTIONS -D _GNU_SOURCE -D _LIBCPP_ENABLE_ASSERTIONS -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I lib/Support -I /build/source/llvm/lib/Support -I include -I /build/source/llvm/include -D _FORTIFY_SOURCE=2 -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-17/lib/clang/17/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -fmacro-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fmacro-prefix-map=/build/source/= -fcoverage-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fcoverage-prefix-map=/build/source/= -source-date-epoch 1683717183 -O2 -Wno-unused-command-line-argument -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -Wno-misleading-indentation -std=c++17 -fdeprecated-macro -fdebug-compilation-dir=/build/source/build-llvm/tools/clang/stage2-bins -fdebug-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fdebug-prefix-map=/build/source/= -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcolor-diagnostics -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2023-05-10-133810-16478-1 -x c++ /build/source/llvm/lib/Support/APInt.cpp

/build/source/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/SmallString.h"
19#include "llvm/ADT/StringRef.h"
20#include "llvm/ADT/bit.h"
21#include "llvm/Config/llvm-config.h"
22#include "llvm/Support/Debug.h"
23#include "llvm/Support/ErrorHandling.h"
24#include "llvm/Support/MathExtras.h"
25#include "llvm/Support/raw_ostream.h"
26#include <cmath>
27#include <optional>

29using namespace llvm;

31#define DEBUG_TYPE"apint" "apint"

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

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

47/// A utility function that converts a character to a digit.
48inline 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 UINT_MAX(2147483647 *2U +1U);
72}


75void 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();
82}

84void APInt::initSlowCase(const APInt& that) {
U.pVal = getMemory(getNumWords());
7
←
Calling 'getMemory'→
9
←
Returned allocated memory→
memcpy(U.pVal, that.U.pVal, getNumWords() * APINT_WORD_SIZE);
32
←
Use of memory after it is freed
87}

89void APInt::initFromArray(ArrayRef<uint64_t> bigVal) {
assert(bigVal.data() && "Null pointer detected!")(static_cast <bool> (bigVal.data() && "Null pointer detected!"
) ? void (0) : __assert_fail ("bigVal.data() && \"Null pointer detected!\""
, "llvm/lib/Support/APInt.cpp", 90, __extension__ __PRETTY_FUNCTION__
));
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();
103}

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

109APInt::APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[])
  : BitWidth(numBits) {
initFromArray(ArrayRef(bigVal, numWords));
112}

114APInt::APInt(unsigned numbits, StringRef Str, uint8_t radix)
  : BitWidth(numbits) {
fromString(numbits, Str, radix);
117}

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

// If we have an allocation, delete it.
if (!isSingleWord())
  delete [] U.pVal;

// Update BitWidth.
BitWidth = NewBitWidth;

// If we are supposed to have an allocation, create it.
if (!isSingleWord())
  U.pVal = getMemory(getNumWords());
136}

138void 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);
151}

153/// This method 'profiles' an APInt for use with FoldingSet.
154void 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]);
165}

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

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

185/// Adds the RHS APInt to this APInt.
186/// @returns this, after addition of RHS.
187/// Addition assignment operator.
188APInt& APInt::operator+=(const APInt& RHS) {
assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")(static_cast <bool> (BitWidth == RHS.BitWidth &&
 "Bit widths must be the same") ? void (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\""
, "llvm/lib/Support/APInt.cpp", 189, __extension__ __PRETTY_FUNCTION__
));
if (isSingleWord())
  U.VAL += RHS.U.VAL;
else
  tcAdd(U.pVal, RHS.U.pVal, 0, getNumWords());
return clearUnusedBits();
195}

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

205/// Subtracts the RHS APInt from this APInt
206/// @returns this, after subtraction
207/// Subtraction assignment operator.
208APInt& APInt::operator-=(const APInt& RHS) {
assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")(static_cast <bool> (BitWidth == RHS.BitWidth &&
 "Bit widths must be the same") ? void (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\""
, "llvm/lib/Support/APInt.cpp", 209, __extension__ __PRETTY_FUNCTION__
));
if (isSingleWord())
  U.VAL -= RHS.U.VAL;
else
  tcSubtract(U.pVal, RHS.U.pVal, 0, getNumWords());
return clearUnusedBits();
215}

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

225APInt APInt::operator*(const APInt& RHS) const {
assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")(static_cast <bool> (BitWidth == RHS.BitWidth &&
 "Bit widths must be the same") ? void (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\""
, "llvm/lib/Support/APInt.cpp", 226, __extension__ __PRETTY_FUNCTION__
));
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;
234}

236void APInt::andAssignSlowCase(const APInt &RHS) {
WordType *dst = U.pVal, *rhs = RHS.U.pVal;
for (size_t i = 0, e = getNumWords(); i != e; ++i)
  dst[i] &= rhs[i];
240}

242void APInt::orAssignSlowCase(const APInt &RHS) {
WordType *dst = U.pVal, *rhs = RHS.U.pVal;
for (size_t i = 0, e = getNumWords(); i != e; ++i)
  dst[i] |= rhs[i];
246}

248void APInt::xorAssignSlowCase(const APInt &RHS) {
WordType *dst = U.pVal, *rhs = RHS.U.pVal;
for (size_t i = 0, e = getNumWords(); i != e; ++i)
  dst[i] ^= rhs[i];
252}

254APInt &APInt::operator*=(const APInt &RHS) {
*this = *this * RHS;
return *this;
257}

259APInt& 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();
267}

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

273int APInt::compare(const APInt& RHS) const {
assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison")(static_cast <bool> (BitWidth == RHS.BitWidth &&
 "Bit widths must be same for comparison") ? void (0) : __assert_fail
 ("BitWidth == RHS.BitWidth && \"Bit widths must be same for comparison\""
, "llvm/lib/Support/APInt.cpp", 274, __extension__ __PRETTY_FUNCTION__
));
if (isSingleWord())
  return U.VAL < RHS.U.VAL ? -1 : U.VAL > RHS.U.VAL;

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

281int APInt::compareSigned(const APInt& RHS) const {
assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison")(static_cast <bool> (BitWidth == RHS.BitWidth &&
 "Bit widths must be same for comparison") ? void (0) : __assert_fail
 ("BitWidth == RHS.BitWidth && \"Bit widths must be same for comparison\""
, "llvm/lib/Support/APInt.cpp", 282, __extension__ __PRETTY_FUNCTION__
));
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());
299}

301void 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;
326}

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

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

340/// Concatenate the bits from "NewLSB" onto the bottom of *this.  This is
341/// equivalent to:
342///   (this->zext(NewWidth) << NewLSB.getBitWidth()) | NewLSB.zext(NewWidth)
343/// In the slow case, we know the result is large.
344APInt APInt::concatSlowCase(const APInt &NewLSB) const {
unsigned NewWidth = getBitWidth() + NewLSB.getBitWidth();
APInt Result = NewLSB.zext(NewWidth);
Result.insertBits(*this, NewLSB.getBitWidth());
return Result;
349}

351/// Toggle a given bit to its opposite value whose position is given
352/// as "bitPosition".
353/// Toggles a given bit to its opposite value.
354void APInt::flipBit(unsigned bitPosition) {
assert(bitPosition < BitWidth && "Out of the bit-width range!")(static_cast <bool> (bitPosition < BitWidth &&
 "Out of the bit-width range!") ? void (0) : __assert_fail ("bitPosition < BitWidth && \"Out of the bit-width range!\""
, "llvm/lib/Support/APInt.cpp", 355, __extension__ __PRETTY_FUNCTION__
));
setBitVal(bitPosition, !(*this)[bitPosition]);
357}

359void APInt::insertBits(const APInt &subBits, unsigned bitPosition) {
unsigned subBitWidth = subBits.getBitWidth();
assert((subBitWidth + bitPosition) <= BitWidth && "Illegal bit insertion")(static_cast <bool> ((subBitWidth + bitPosition) <= BitWidth
 && "Illegal bit insertion") ? void (0) : __assert_fail
 ("(subBitWidth + bitPosition) <= BitWidth && \"Illegal bit insertion\""
, "llvm/lib/Support/APInt.cpp", 361, __extension__ __PRETTY_FUNCTION__
));

// inserting no bits is a noop.
if (subBitWidth == 0)
  return;

// 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]);
415}

417void 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);
442}

444APInt APInt::extractBits(unsigned numBits, unsigned bitPosition) const {
assert(bitPosition < BitWidth && (numBits + bitPosition) <= BitWidth &&(static_cast <bool> (bitPosition < BitWidth &&
 (numBits + bitPosition) <= BitWidth && "Illegal bit extraction"
) ? void (0) : __assert_fail ("bitPosition < BitWidth && (numBits + bitPosition) <= BitWidth && \"Illegal bit extraction\""
, "llvm/lib/Support/APInt.cpp", 446, __extension__ __PRETTY_FUNCTION__
))
       "Illegal bit extraction")(static_cast <bool> (bitPosition < BitWidth &&
 (numBits + bitPosition) <= BitWidth && "Illegal bit extraction"
) ? void (0) : __assert_fail ("bitPosition < BitWidth && (numBits + bitPosition) <= BitWidth && \"Illegal bit extraction\""
, "llvm/lib/Support/APInt.cpp", 446, __extension__ __PRETTY_FUNCTION__
));

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, ArrayRef(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();
478}

480uint64_t APInt::extractBitsAsZExtValue(unsigned numBits,
                                     unsigned bitPosition) const {
assert(numBits > 0 && "Can't extract zero bits")(static_cast <bool> (numBits > 0 && "Can't extract zero bits"
) ? void (0) : __assert_fail ("numBits > 0 && \"Can't extract zero bits\""
, "llvm/lib/Support/APInt.cpp", 482, __extension__ __PRETTY_FUNCTION__
));
assert(bitPosition < BitWidth && (numBits + bitPosition) <= BitWidth &&(static_cast <bool> (bitPosition < BitWidth &&
 (numBits + bitPosition) <= BitWidth && "Illegal bit extraction"
) ? void (0) : __assert_fail ("bitPosition < BitWidth && (numBits + bitPosition) <= BitWidth && \"Illegal bit extraction\""
, "llvm/lib/Support/APInt.cpp", 484, __extension__ __PRETTY_FUNCTION__
))
       "Illegal bit extraction")(static_cast <bool> (bitPosition < BitWidth &&
 (numBits + bitPosition) <= BitWidth && "Illegal bit extraction"
) ? void (0) : __assert_fail ("bitPosition < BitWidth && (numBits + bitPosition) <= BitWidth && \"Illegal bit extraction\""
, "llvm/lib/Support/APInt.cpp", 484, __extension__ __PRETTY_FUNCTION__
));
assert(numBits <= 64 && "Illegal bit extraction")(static_cast <bool> (numBits <= 64 && "Illegal bit extraction"
) ? void (0) : __assert_fail ("numBits <= 64 && \"Illegal bit extraction\""
, "llvm/lib/Support/APInt.cpp", 485, __extension__ __PRETTY_FUNCTION__
));

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;
503}

505unsigned APInt::getSufficientBitsNeeded(StringRef Str, uint8_t Radix) {
assert(!Str.empty() && "Invalid string length")(static_cast <bool> (!Str.empty() && "Invalid string length"
) ? void (0) : __assert_fail ("!Str.empty() && \"Invalid string length\""
, "llvm/lib/Support/APInt.cpp", 506, __extension__ __PRETTY_FUNCTION__
));
size_t StrLen = Str.size();

// Each computation below needs to know if it's negative.
unsigned IsNegative = false;
if (Str[0] == '-' || Str[0] == '+') {
  IsNegative = Str[0] == '-';
  StrLen--;
  assert(StrLen && "String is only a sign, needs a value.")(static_cast <bool> (StrLen && "String is only a sign, needs a value."
) ? void (0) : __assert_fail ("StrLen && \"String is only a sign, needs a value.\""
, "llvm/lib/Support/APInt.cpp", 514, __extension__ __PRETTY_FUNCTION__
));
}

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

// 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.
if (Radix == 10)
  return (StrLen == 1 ? 4 : StrLen * 64 / 18) + IsNegative;

assert(Radix == 36)(static_cast <bool> (Radix == 36) ? void (0) : __assert_fail
 ("Radix == 36", "llvm/lib/Support/APInt.cpp", 533, __extension__
 __PRETTY_FUNCTION__));
return (StrLen == 1 ? 7 : StrLen * 16 / 3) + IsNegative;
535}

537unsigned APInt::getBitsNeeded(StringRef str, uint8_t radix) {
// Compute a sufficient number of bits that is always large enough but might
// be too large.
unsigned sufficient = getSufficientBitsNeeded(str, radix);

// For bases 2, 8, and 16, the sufficient number of bits is exact and we can
// return the value directly. For bases 10 and 36, we need to do extra work.
if (radix == 2 || radix == 8 || radix == 16)
  return sufficient;

// 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.
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.")(static_cast <bool> (slen && "String is only a sign, needs a value."
) ? void (0) : __assert_fail ("slen && \"String is only a sign, needs a value.\""
, "llvm/lib/Support/APInt.cpp", 558, __extension__ __PRETTY_FUNCTION__
));
}


// 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;
}
576}

578hash_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()));
585}

587unsigned DenseMapInfo<APInt, void>::getHashValue(const APInt &Key) {
return static_cast<unsigned>(hash_value(Key));
589}

591bool APInt::isSplat(unsigned SplatSizeInBits) const {
assert(getBitWidth() % SplatSizeInBits == 0 &&(static_cast <bool> (getBitWidth() % SplatSizeInBits ==
&& "SplatSizeInBits must divide width!") ? void (0
) : __assert_fail ("getBitWidth() % SplatSizeInBits == 0 && \"SplatSizeInBits must divide width!\""
, "llvm/lib/Support/APInt.cpp", 593, __extension__ __PRETTY_FUNCTION__
))
       "SplatSizeInBits must divide width!")(static_cast <bool> (getBitWidth() % SplatSizeInBits ==
&& "SplatSizeInBits must divide width!") ? void (0
) : __assert_fail ("getBitWidth() % SplatSizeInBits == 0 && \"SplatSizeInBits must divide width!\""
, "llvm/lib/Support/APInt.cpp", 593, __extension__ __PRETTY_FUNCTION__
));
// 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);
597}

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

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

611/// Return a value containing V broadcasted over NewLen bits.
612APInt APInt::getSplat(unsigned NewLen, const APInt &V) {
assert(NewLen >= V.getBitWidth() && "Can't splat to smaller bit width!")(static_cast <bool> (NewLen >= V.getBitWidth() &&
 "Can't splat to smaller bit width!") ? void (0) : __assert_fail
 ("NewLen >= V.getBitWidth() && \"Can't splat to smaller bit width!\""
, "llvm/lib/Support/APInt.cpp", 613, __extension__ __PRETTY_FUNCTION__
));

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

return Val;
620}

622unsigned 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::countl_zero(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;
637}

639unsigned 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::countl_one(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::countl_one(U.pVal[i]);
      break;
    }
  }
}
return Count;
661}

663unsigned 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::countr_zero(U.pVal[i]);
return std::min(Count, BitWidth);
671}

673unsigned 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::countr_one(U.pVal[i]);
assert(Count <= BitWidth)(static_cast <bool> (Count <= BitWidth) ? void (0) :
 __assert_fail ("Count <= BitWidth", "llvm/lib/Support/APInt.cpp"
, 680, __extension__ __PRETTY_FUNCTION__));
return Count;
682}

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

691bool 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;
697}

699bool 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;
705}

707APInt APInt::byteSwap() const {
assert(BitWidth >= 16 && BitWidth % 8 == 0 && "Cannot byteswap!")(static_cast <bool> (BitWidth >= 16 && BitWidth
 % 8 == 0 && "Cannot byteswap!") ? void (0) : __assert_fail
 ("BitWidth >= 16 && BitWidth % 8 == 0 && \"Cannot byteswap!\""
, "llvm/lib/Support/APInt.cpp", 708, __extension__ __PRETTY_FUNCTION__
));
if (BitWidth == 16)
  return APInt(BitWidth, llvm::byteswap<uint16_t>(U.VAL));
if (BitWidth == 32)
  return APInt(BitWidth, llvm::byteswap<uint32_t>(U.VAL));
if (BitWidth <= 64) {
  uint64_t Tmp1 = llvm::byteswap<uint64_t>(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] = llvm::byteswap<uint64_t>(U.pVal[N - I - 1]);
if (Result.BitWidth != BitWidth) {
  Result.lshrInPlace(Result.BitWidth - BitWidth);
  Result.BitWidth = BitWidth;
}
return Result;
727}

729APInt 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));
case 0:
  return *this;
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;
757}

759APInt 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.countr_zero();
  unsigned Pow2_B = B.countr_zero();
  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.countr_zero() - Pow2);
  } else {
    B -= A;
    B.lshrInPlace(B.countr_zero() - Pow2);
  }
}

return A;
800}

802APInt 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;
832}

834/// This function converts this APInt to a double.
835/// The layout for double is as following (IEEE Standard 754):
836///  --------------------------------------
837/// |  Sign    Exponent    Fraction    Bias |
838/// |-------------------------------------- |
839/// |  1[63]   11[62-52]   52[51-00]   1023 |
840///  --------------------------------------
841double 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?")(static_cast <bool> (hiWord > 0 && "huh?") ?
 void (0) : __assert_fail ("hiWord > 0 && \"huh?\""
, "llvm/lib/Support/APInt.cpp", 885, __extension__ __PRETTY_FUNCTION__
));
  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);
895}

897// Truncate to new width.
898APInt APInt::trunc(unsigned width) const {
assert(width <= BitWidth && "Invalid APInt Truncate request")(static_cast <bool> (width <= BitWidth && "Invalid APInt Truncate request"
) ? void (0) : __assert_fail ("width <= BitWidth && \"Invalid APInt Truncate request\""
, "llvm/lib/Support/APInt.cpp", 899, __extension__ __PRETTY_FUNCTION__
));

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

if (width == BitWidth)
  return *this;

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;
920}

922// Truncate to new width with unsigned saturation.
923APInt APInt::truncUSat(unsigned width) const {
assert(width <= BitWidth && "Invalid APInt Truncate request")(static_cast <bool> (width <= BitWidth && "Invalid APInt Truncate request"
) ? void (0) : __assert_fail ("width <= BitWidth && \"Invalid APInt Truncate request\""
, "llvm/lib/Support/APInt.cpp", 924, __extension__ __PRETTY_FUNCTION__
));

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

933// Truncate to new width with signed saturation.
934APInt APInt::truncSSat(unsigned width) const {
assert(width <= BitWidth && "Invalid APInt Truncate request")(static_cast <bool> (width <= BitWidth && "Invalid APInt Truncate request"
) ? void (0) : __assert_fail ("width <= BitWidth && \"Invalid APInt Truncate request\""
, "llvm/lib/Support/APInt.cpp", 935, __extension__ __PRETTY_FUNCTION__
));

// 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);
943}

945// Sign extend to a new width.
946APInt APInt::sext(unsigned Width) const {
assert(Width >= BitWidth && "Invalid APInt SignExtend request")(static_cast <bool> (Width >= BitWidth && "Invalid APInt SignExtend request"
) ? void (0) : __assert_fail ("Width >= BitWidth && \"Invalid APInt SignExtend request\""
, "llvm/lib/Support/APInt.cpp", 947, __extension__ __PRETTY_FUNCTION__
));

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

if (Width == BitWidth)
  return *this;

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;
970}

972//  Zero extend to a new width.
973APInt APInt::zext(unsigned width) const {
assert(width >= BitWidth && "Invalid APInt ZeroExtend request")(static_cast <bool> (width >= BitWidth && "Invalid APInt ZeroExtend request"
) ? void (0) : __assert_fail ("width >= BitWidth && \"Invalid APInt ZeroExtend request\""
, "llvm/lib/Support/APInt.cpp", 974, __extension__ __PRETTY_FUNCTION__
));

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

if (width == BitWidth)
  return *this;

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;
992}

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

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

1010/// Arithmetic right-shift this APInt by shiftAmt.
1011/// Arithmetic right-shift function.
1012void APInt::ashrInPlace(const APInt &shiftAmt) {
ashrInPlace((unsigned)shiftAmt.getLimitedValue(BitWidth));
1014}

1016/// Arithmetic right-shift this APInt by shiftAmt.
1017/// Arithmetic right-shift function.
1018void 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();
1057}

1059/// Logical right-shift this APInt by shiftAmt.
1060/// Logical right-shift function.
1061void APInt::lshrInPlace(const APInt &shiftAmt) {
lshrInPlace((unsigned)shiftAmt.getLimitedValue(BitWidth));
1063}

1065/// Logical right-shift this APInt by shiftAmt.
1066/// Logical right-shift function.
1067void APInt::lshrSlowCase(unsigned ShiftAmt) {
tcShiftRight(U.pVal, getNumWords(), ShiftAmt);
1069}

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

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

1084// Calculate the rotate amount modulo the bit width.
1085static unsigned rotateModulo(unsigned BitWidth, const APInt &rotateAmt) {
if (LLVM_UNLIKELY(BitWidth == 0)__builtin_expect((bool)(BitWidth == 0), false))
2
←
Assuming 'BitWidth' is not equal to 0→
3
←
Taking false branch→
  return 0;
unsigned rotBitWidth = rotateAmt.getBitWidth();
APInt rot = rotateAmt;
4
←
Calling copy constructor for 'APInt'→
11
←
Returning from copy constructor for 'APInt'→
if (rotBitWidth < BitWidth) {
12
←
Assuming 'rotBitWidth' is < 'BitWidth'→
13
←
Taking true branch→
  // 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);
14
←
Calling move assignment operator for 'APInt'→
18
←
Returning; memory was released→
}
rot = rot.urem(APInt(rot.getBitWidth(), BitWidth));
19
←
Calling 'APInt::urem'→
return rot.getLimitedValue(BitWidth);
1097}

1099APInt APInt::rotl(const APInt &rotateAmt) const {
return rotl(rotateModulo(BitWidth, rotateAmt));
1101}

1103APInt APInt::rotl(unsigned rotateAmt) const {
if (LLVM_UNLIKELY(BitWidth == 0)__builtin_expect((bool)(BitWidth == 0), false))
  return *this;
rotateAmt %= BitWidth;
if (rotateAmt == 0)
  return *this;
return shl(rotateAmt) | lshr(BitWidth - rotateAmt);
1110}

1112APInt APInt::rotr(const APInt &rotateAmt) const {
return rotr(rotateModulo(BitWidth, rotateAmt));
1
Calling 'rotateModulo'→
1114}

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

1125/// \returns the nearest log base 2 of this APInt. Ties round up.
1126///
1127/// NOTE: When we have a BitWidth of 1, we define:
1128///
1129///   log2(0) = UINT32_MAX
1130///   log2(1) = 0
1131///
1132/// to get around any mathematical concerns resulting from
1133/// referencing 2 in a space where 2 does no exist.
1134unsigned APInt::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 (isZero())
  return UINT32_MAX(4294967295U);

// 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]);
1152}

1154// Square Root - this method computes and returns the square root of "this".
1155// Three mechanisms are used for computation. For small values (<= 5 bits),
1156// a table lookup is done. This gets some performance for common cases. For
1157// values using less than 52 bits, the value is converted to double and then
1158// the libc sqrt function is called. The result is rounded and then converted
1159// back to a uint64_t which is then used to construct the result. Finally,
1160// the Babylonian method for computing square roots is used.
1161APInt 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")(static_cast <bool> (this->ule(nextSquare) &&
 "Error in APInt::sqrt computation") ? void (0) : __assert_fail
 ("this->ule(nextSquare) && \"Error in APInt::sqrt computation\""
, "llvm/lib/Support/APInt.cpp", 1227, __extension__ __PRETTY_FUNCTION__
));
APInt midpoint((nextSquare - square).udiv(two));
APInt offset(*this - square);
if (offset.ult(midpoint))
  return x_old;
return x_old + 1;
1233}

1235/// Computes the multiplicative inverse of this APInt for a given modulo. The
1236/// iterative extended Euclidean algorithm is used to solve for this value,
1237/// however we simplify it to speed up calculating only the inverse, and take
1238/// advantage of div+rem calculations. We also use some tricks to avoid copying
1239/// (potentially large) APInts around.
1240/// WARNING: a value of '0' may be returned,
1241///          signifying that no multiplicative inverse exists!
1242APInt APInt::multiplicativeInverse(const APInt& modulo) const {
assert(ult(modulo) && "This APInt must be smaller than the modulo")(static_cast <bool> (ult(modulo) && "This APInt must be smaller than the modulo"
) ? void (0) : __assert_fail ("ult(modulo) && \"This APInt must be smaller than the modulo\""
, "llvm/lib/Support/APInt.cpp", 1243, __extension__ __PRETTY_FUNCTION__
));

// 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]);
1282}

1284/// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
1285/// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
1286/// variables here have the same names as in the algorithm. Comments explain
1287/// the algorithm and any deviation from it.
1288static void KnuthDiv(uint32_t *u, uint32_t *v, uint32_t *q, uint32_t* r,
                   unsigned m, unsigned n) {
assert(u && "Must provide dividend")(static_cast <bool> (u && "Must provide dividend"
) ? void (0) : __assert_fail ("u && \"Must provide dividend\""
, "llvm/lib/Support/APInt.cpp", 1290, __extension__ __PRETTY_FUNCTION__
));
assert(v && "Must provide divisor")(static_cast <bool> (v && "Must provide divisor"
) ? void (0) : __assert_fail ("v && \"Must provide divisor\""
, "llvm/lib/Support/APInt.cpp", 1291, __extension__ __PRETTY_FUNCTION__
));
assert(q && "Must provide quotient")(static_cast <bool> (q && "Must provide quotient"
) ? void (0) : __assert_fail ("q && \"Must provide quotient\""
, "llvm/lib/Support/APInt.cpp", 1292, __extension__ __PRETTY_FUNCTION__
));
assert(u != v && u != q && v != q && "Must use different memory")(static_cast <bool> (u != v && u != q &&
 v != q && "Must use different memory") ? void (0) : __assert_fail
 ("u != v && u != q && v != q && \"Must use different memory\""
, "llvm/lib/Support/APInt.cpp", 1293, __extension__ __PRETTY_FUNCTION__
));
assert(n>1 && "n must be > 1")(static_cast <bool> (n>1 && "n must be > 1"
) ? void (0) : __assert_fail ("n>1 && \"n must be > 1\""
, "llvm/lib/Support/APInt.cpp", 1294, __extension__ __PRETTY_FUNCTION__
));

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

1299// The DEBUG macros here tend to be spam in the debug output if you're not
1300// debugging this code. Disable them unless KNUTH_DEBUG is defined.
1301#ifdef KNUTH_DEBUG
1302#define DEBUG_KNUTH(X)do {} while(false) LLVM_DEBUG(X)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { X; } } while (false)
1303#else
1304#define DEBUG_KNUTH(X)do {} while(false) do {} while(false)
1305#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 = llvm::countl_zero(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);
1446}

1448void APInt::divide(const WordType *LHS, unsigned lhsWords, const WordType *RHS,
                 unsigned rhsWords, WordType *Quotient, WordType *Remainder) {
assert(lhsWords >= rhsWords && "Fractional result")(static_cast <bool> (lhsWords >= rhsWords &&
 "Fractional result") ? void (0) : __assert_fail ("lhsWords >= rhsWords && \"Fractional result\""
, "llvm/lib/Support/APInt.cpp", 1450, __extension__ __PRETTY_FUNCTION__
));

// 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?")(static_cast <bool> (n != 0 && "Divide by zero?"
) ? void (0) : __assert_fail ("n != 0 && \"Divide by zero?\""
, "llvm/lib/Support/APInt.cpp", 1522, __extension__ __PRETTY_FUNCTION__
));
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;
}
1569}

1571APInt APInt::udiv(const APInt &RHS) const {
assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")(static_cast <bool> (BitWidth == RHS.BitWidth &&
 "Bit widths must be the same") ? void (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\""
, "llvm/lib/Support/APInt.cpp", 1572, __extension__ __PRETTY_FUNCTION__
));

// First, deal with the easy case
if (isSingleWord()) {
  assert(RHS.U.VAL != 0 && "Divide by zero?")(static_cast <bool> (RHS.U.VAL != 0 && "Divide by zero?"
) ? void (0) : __assert_fail ("RHS.U.VAL != 0 && \"Divide by zero?\""
, "llvm/lib/Support/APInt.cpp", 1576, __extension__ __PRETTY_FUNCTION__
));
  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???")(static_cast <bool> (rhsWords && "Divided by zero???"
) ? void (0) : __assert_fail ("rhsWords && \"Divided by zero???\""
, "llvm/lib/Support/APInt.cpp", 1584, __extension__ __PRETTY_FUNCTION__
));

// 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;
1607}

1609APInt APInt::udiv(uint64_t RHS) const {
assert(RHS != 0 && "Divide by zero?")(static_cast <bool> (RHS != 0 && "Divide by zero?"
) ? void (0) : __assert_fail ("RHS != 0 && \"Divide by zero?\""
, "llvm/lib/Support/APInt.cpp", 1610, __extension__ __PRETTY_FUNCTION__
));

// 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;
1640}

1642APInt 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);
1651}

1653APInt 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);
1662}

1664APInt APInt::urem(const APInt &RHS) const {
assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")(static_cast <bool> (BitWidth == RHS.BitWidth &&
 "Bit widths must be the same") ? void (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\""
, "llvm/lib/Support/APInt.cpp", 1665, __extension__ __PRETTY_FUNCTION__
));
20
←
Assuming 'BitWidth' is equal to 'RHS.BitWidth'→
21
←
'?' condition is true→
if (isSingleWord()) {
22
←
Taking false branch→
  assert(RHS.U.VAL != 0 && "Remainder by zero?")(static_cast <bool> (RHS.U.VAL != 0 && "Remainder by zero?"
) ? void (0) : __assert_fail ("RHS.U.VAL != 0 && \"Remainder by zero?\""
, "llvm/lib/Support/APInt.cpp", 1667, __extension__ __PRETTY_FUNCTION__
));
  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 ???")(static_cast <bool> (rhsWords && "Performing remainder operation by zero ???"
) ? void (0) : __assert_fail ("rhsWords && \"Performing remainder operation by zero ???\""
, "llvm/lib/Support/APInt.cpp", 1677, __extension__ __PRETTY_FUNCTION__
));
23
←
Assuming 'rhsWords' is not equal to 0→
24
←
'?' condition is true→

// Check the degenerate cases
if (lhsWords == 0)
25
←
Assuming 'lhsWords' is not equal to 0→
26
←
Taking false branch→
  // 0 % Y ===> 0
  return APInt(BitWidth, 0);
if (rhsBits == 1)
27
←
Assuming 'rhsBits' is not equal to 1→
  // X % 1 ===> 0
  return APInt(BitWidth, 0);
if (lhsWords < rhsWords || this->ult(RHS))
28
←
Assuming 'lhsWords' is < 'rhsWords'→
  // X % Y ===> X, iff X < Y
  return *this;
29
←
Calling copy constructor for 'APInt'→
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;
1700}

1702uint64_t APInt::urem(uint64_t RHS) const {
assert(RHS != 0 && "Remainder by zero?")(static_cast <bool> (RHS != 0 && "Remainder by zero?"
) ? void (0) : __assert_fail ("RHS != 0 && \"Remainder by zero?\""
, "llvm/lib/Support/APInt.cpp", 1703, __extension__ __PRETTY_FUNCTION__
));

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;
1732}

1734APInt 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);
1743}

1745int64_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);
1754}

1756void APInt::udivrem(const APInt &LHS, const APInt &RHS,
                  APInt &Quotient, APInt &Remainder) {
assert(LHS.BitWidth == RHS.BitWidth && "Bit widths must be the same")(static_cast <bool> (LHS.BitWidth == RHS.BitWidth &&
 "Bit widths must be the same") ? void (0) : __assert_fail ("LHS.BitWidth == RHS.BitWidth && \"Bit widths must be the same\""
, "llvm/lib/Support/APInt.cpp", 1758, __extension__ __PRETTY_FUNCTION__
));
unsigned BitWidth = LHS.BitWidth;

// First, deal with the easy case
if (LHS.isSingleWord()) {
  assert(RHS.U.VAL != 0 && "Divide by zero?")(static_cast <bool> (RHS.U.VAL != 0 && "Divide by zero?"
) ? void (0) : __assert_fail ("RHS.U.VAL != 0 && \"Divide by zero?\""
, "llvm/lib/Support/APInt.cpp", 1763, __extension__ __PRETTY_FUNCTION__
));
  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 ???")(static_cast <bool> (rhsWords && "Performing divrem operation by zero ???"
) ? void (0) : __assert_fail ("rhsWords && \"Performing divrem operation by zero ???\""
, "llvm/lib/Support/APInt.cpp", 1775, __extension__ __PRETTY_FUNCTION__
));

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

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

if (lhsWords < rhsWords || LHS.ult(RHS)) {
  Remainder = LHS;                  // 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 = 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);
Remainder.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];
  uint64_t rhsValue = RHS.U.pVal[0];
  Quotient = lhsValue / rhsValue;
  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);
1825}

1827void APInt::udivrem(const APInt &LHS, uint64_t RHS, APInt &Quotient,
                  uint64_t &Remainder) {
assert(RHS != 0 && "Divide by zero?")(static_cast <bool> (RHS != 0 && "Divide by zero?"
) ? void (0) : __assert_fail ("RHS != 0 && \"Divide by zero?\""
, "llvm/lib/Support/APInt.cpp", 1829, __extension__ __PRETTY_FUNCTION__
));
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);
1886}

1888void APInt::sdivrem(const APInt &LHS, const APInt &RHS,
                  APInt &Quotient, APInt &Remainder) {
if (LHS.isNegative()) {
  if (RHS.isNegative())
    APInt::udivrem(-LHS, -RHS, Quotient, Remainder);
  else {
    APInt::udivrem(-LHS, RHS, Quotient, Remainder);
    Quotient.negate();
  }
  Remainder.negate();
} else if (RHS.isNegative()) {
  APInt::udivrem(LHS, -RHS, Quotient, Remainder);
  Quotient.negate();
} else {
  APInt::udivrem(LHS, RHS, Quotient, Remainder);
}
1904}

1906void 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;
1924}

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

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

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

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

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

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

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

1969APInt APInt::umul_ov(const APInt &RHS, bool &Overflow) const {
if (countl_zero() + RHS.countl_zero() + 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;
1984}

1986APInt 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(countl_zero());
else
  Overflow = ShAmt.uge(countl_one());

return *this << ShAmt;
1997}

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

Overflow = ShAmt.ugt(countl_zero());

return *this << ShAmt;
2007}

2009APInt 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);
2017}

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

return APInt::getMaxValue(BitWidth);
2026}

2028APInt 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);
2036}

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

return APInt(BitWidth, 0);
2045}

2047APInt 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);
2058}

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

return APInt::getMaxValue(BitWidth);
2067}

2069APInt 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);
2077}

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

return APInt::getMaxValue(BitWidth);
2086}

2088void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) {
// Check our assumptions here
assert(!str.empty() && "Invalid string length")(static_cast <bool> (!str.empty() && "Invalid string length"
) ? void (0) : __assert_fail ("!str.empty() && \"Invalid string length\""
, "llvm/lib/Support/APInt.cpp", 2090, __extension__ __PRETTY_FUNCTION__
));
assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||(static_cast <bool> ((radix == 10 || radix == 8 || radix
 == 16 || radix == 2 || radix == 36) && "Radix should be 2, 8, 10, 16, or 36!"
) ? void (0) : __assert_fail ("(radix == 10 || radix == 8 || radix == 16 || radix == 2 || radix == 36) && \"Radix should be 2, 8, 10, 16, or 36!\""
, "llvm/lib/Support/APInt.cpp", 2093, __extension__ __PRETTY_FUNCTION__
))
        radix == 36) &&(static_cast <bool> ((radix == 10 || radix == 8 || radix
 == 16 || radix == 2 || radix == 36) && "Radix should be 2, 8, 10, 16, or 36!"
) ? void (0) : __assert_fail ("(radix == 10 || radix == 8 || radix == 16 || radix == 2 || radix == 36) && \"Radix should be 2, 8, 10, 16, or 36!\""
, "llvm/lib/Support/APInt.cpp", 2093, __extension__ __PRETTY_FUNCTION__
))
       "Radix should be 2, 8, 10, 16, or 36!")(static_cast <bool> ((radix == 10 || radix == 8 || radix
 == 16 || radix == 2 || radix == 36) && "Radix should be 2, 8, 10, 16, or 36!"
) ? void (0) : __assert_fail ("(radix == 10 || radix == 8 || radix == 16 || radix == 2 || radix == 36) && \"Radix should be 2, 8, 10, 16, or 36!\""
, "llvm/lib/Support/APInt.cpp", 2093, __extension__ __PRETTY_FUNCTION__
));

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.")(static_cast <bool> (slen && "String is only a sign, needs a value."
) ? void (0) : __assert_fail ("slen && \"String is only a sign, needs a value.\""
, "llvm/lib/Support/APInt.cpp", 2101, __extension__ __PRETTY_FUNCTION__
));
}
assert((slen <= numbits || radix != 2) && "Insufficient bit width")(static_cast <bool> ((slen <= numbits || radix != 2)
 && "Insufficient bit width") ? void (0) : __assert_fail
 ("(slen <= numbits || radix != 2) && \"Insufficient bit width\""
, "llvm/lib/Support/APInt.cpp", 2103, __extension__ __PRETTY_FUNCTION__
));
assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width")(static_cast <bool> (((slen-1)*3 <= numbits || radix
 != 8) && "Insufficient bit width") ? void (0) : __assert_fail
 ("((slen-1)*3 <= numbits || radix != 8) && \"Insufficient bit width\""
, "llvm/lib/Support/APInt.cpp", 2104, __extension__ __PRETTY_FUNCTION__
));
assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width")(static_cast <bool> (((slen-1)*4 <= numbits || radix
 != 16) && "Insufficient bit width") ? void (0) : __assert_fail
 ("((slen-1)*4 <= numbits || radix != 16) && \"Insufficient bit width\""
, "llvm/lib/Support/APInt.cpp", 2105, __extension__ __PRETTY_FUNCTION__
));
assert((((slen-1)*64)/22 <= numbits || radix != 10) &&(static_cast <bool> ((((slen-1)*64)/22 <= numbits ||
 radix != 10) && "Insufficient bit width") ? void (0)
 : __assert_fail ("(((slen-1)*64)/22 <= numbits || radix != 10) && \"Insufficient bit width\""
, "llvm/lib/Support/APInt.cpp", 2107, __extension__ __PRETTY_FUNCTION__
))
       "Insufficient bit width")(static_cast <bool> ((((slen-1)*64)/22 <= numbits ||
 radix != 10) && "Insufficient bit width") ? void (0)
 : __assert_fail ("(((slen-1)*64)/22 <= numbits || radix != 10) && \"Insufficient bit width\""
, "llvm/lib/Support/APInt.cpp", 2107, __extension__ __PRETTY_FUNCTION__
));

// 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")(static_cast <bool> (digit < radix && "Invalid character in digit string"
) ? void (0) : __assert_fail ("digit < radix && \"Invalid character in digit string\""
, "llvm/lib/Support/APInt.cpp", 2121, __extension__ __PRETTY_FUNCTION__
));

  // 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();
2137}

2139void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix,
                   bool Signed, bool formatAsCLiteral) const {
assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 ||(static_cast <bool> ((Radix == 10 || Radix == 8 || Radix
 == 16 || Radix == 2 || Radix == 36) && "Radix should be 2, 8, 10, 16, or 36!"
) ? void (0) : __assert_fail ("(Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 || Radix == 36) && \"Radix should be 2, 8, 10, 16, or 36!\""
, "llvm/lib/Support/APInt.cpp", 2143, __extension__ __PRETTY_FUNCTION__
))
        Radix == 36) &&(static_cast <bool> ((Radix == 10 || Radix == 8 || Radix
 == 16 || Radix == 2 || Radix == 36) && "Radix should be 2, 8, 10, 16, or 36!"
) ? void (0) : __assert_fail ("(Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 || Radix == 36) && \"Radix should be 2, 8, 10, 16, or 36!\""
, "llvm/lib/Support/APInt.cpp", 2143, __extension__ __PRETTY_FUNCTION__
))
       "Radix should be 2, 8, 10, 16, or 36!")(static_cast <bool> ((Radix == 10 || Radix == 8 || Radix
 == 16 || Radix == 2 || Radix == 36) && "Radix should be 2, 8, 10, 16, or 36!"
) ? void (0) : __assert_fail ("(Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 || Radix == 36) && \"Radix should be 2, 8, 10, 16, or 36!\""
, "llvm/lib/Support/APInt.cpp", 2143, __extension__ __PRETTY_FUNCTION__
));

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!")::llvm::llvm_unreachable_internal("Invalid radix!", "llvm/lib/Support/APInt.cpp"
, 2162);
  }
}

// First, check for a zero value and just short circuit the logic below.
if (isZero()) {
  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")(static_cast <bool> (Digit < Radix && "divide failed"
) ? void (0) : __assert_fail ("Digit < Radix && \"divide failed\""
, "llvm/lib/Support/APInt.cpp", 2243, __extension__ __PRETTY_FUNCTION__
));
    Str.push_back(Digits[Digit]);
  }
}

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

2252#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2253LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void APInt::dump() const {
SmallString<40> S, U;
this->toStringUnsigned(U);
this->toStringSigned(S);
dbgs() << "APInt(" << BitWidth << "b, "
       << U << "u " << S << "s)\n";
2259}
2260#endif

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

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

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

2276// Returns the integer part with the least significant BITS set.
2277// BITS cannot be zero.
2278static inline APInt::WordType lowBitMask(unsigned bits) {
assert(bits != 0 && bits <= APInt::APINT_BITS_PER_WORD)(static_cast <bool> (bits != 0 && bits <= APInt
::APINT_BITS_PER_WORD) ? void (0) : __assert_fail ("bits != 0 && bits <= APInt::APINT_BITS_PER_WORD"
, "llvm/lib/Support/APInt.cpp", 2279, __extension__ __PRETTY_FUNCTION__
));
return ~(APInt::WordType) 0 >> (APInt::APINT_BITS_PER_WORD - bits);
2281}

2283/// Returns the value of the lower half of PART.
2284static inline APInt::WordType lowHalf(APInt::WordType part) {
return part & lowBitMask(APInt::APINT_BITS_PER_WORD / 2);
2286}

2288/// Returns the value of the upper half of PART.
2289static inline APInt::WordType highHalf(APInt::WordType part) {
return part >> (APInt::APINT_BITS_PER_WORD / 2);
2291}

2293/// Sets the least significant part of a bignum to the input value, and zeroes
2294/// out higher parts.
2295void APInt::tcSet(WordType *dst, WordType part, unsigned parts) {
assert(parts > 0)(static_cast <bool> (parts > 0) ? void (0) : __assert_fail
 ("parts > 0", "llvm/lib/Support/APInt.cpp", 2296, __extension__
 __PRETTY_FUNCTION__));
dst[0] = part;
for (unsigned i = 1; i < parts; i++)
  dst[i] = 0;
2300}

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

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

return true;
2315}

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

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

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

2332/// Returns the bit number of the least significant set bit of a number.  If the
2333/// input number has no bits set UINT_MAX is returned.
2334unsigned APInt::tcLSB(const WordType *parts, unsigned n) {
for (unsigned i = 0; i < n; i++) {
  if (parts[i] != 0) {
    unsigned lsb = llvm::countr_zero(parts[i]);
    return lsb + i * APINT_BITS_PER_WORD;
  }
}

return UINT_MAX(2147483647 *2U +1U);
2343}

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

  if (parts[n] != 0) {
    static_assert(sizeof(parts[n]) <= sizeof(uint64_t));
    unsigned msb = llvm::Log2_64(parts[n]);

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

return UINT_MAX(2147483647 *2U +1U);
2360}

2362/// Copy the bit vector of width srcBITS from SRC, starting at bit srcLSB, to
2363/// DST, of dstCOUNT parts, such that the bit srcLSB becomes the least
2364/// significant bit of DST.  All high bits above srcBITS in DST are zero-filled.
2365/// */
2366void
2367APInt::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)(static_cast <bool> (dstParts <= dstCount) ? void (0
) : __assert_fail ("dstParts <= dstCount", "llvm/lib/Support/APInt.cpp"
, 2370, __extension__ __PRETTY_FUNCTION__));

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;
2394}

2396//// DST += RHS + C where C is zero or one.  Returns the carry flag.
2397APInt::WordType APInt::tcAdd(WordType *dst, const WordType *rhs,
                           WordType c, unsigned parts) {
assert(c <= 1)(static_cast <bool> (c <= 1) ? void (0) : __assert_fail
 ("c <= 1", "llvm/lib/Support/APInt.cpp", 2399, __extension__
 __PRETTY_FUNCTION__));

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;
2413}

2415/// This function adds a single "word" integer, src, to the multiple
2416/// "word" integer array, dst[]. dst[] is modified to reflect the addition and
2417/// 1 is returned if there is a carry out, otherwise 0 is returned.
2418/// @returns the carry of the addition.
2419APInt::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;
2429}

2431/// DST -= RHS + C where C is zero or one.  Returns the carry flag.
2432APInt::WordType APInt::tcSubtract(WordType *dst, const WordType *rhs,
                                WordType c, unsigned parts) {
assert(c <= 1)(static_cast <bool> (c <= 1) ? void (0) : __assert_fail
 ("c <= 1", "llvm/lib/Support/APInt.cpp", 2434, __extension__
 __PRETTY_FUNCTION__));

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;
2448}

2450/// This function subtracts a single "word" (64-bit word), src, from
2451/// the multi-word integer array, dst[], propagating the borrowed 1 value until
2452/// no further borrowing is needed or it runs out of "words" in dst.  The result
2453/// is 1 if "borrowing" exhausted the digits in dst, or 0 if dst was not
2454/// exhausted. In other words, if src > dst then this function returns 1,
2455/// otherwise 0.
2456/// @returns the borrow out of the subtraction
2457APInt::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;
2468}

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

2476/// DST += SRC * MULTIPLIER + CARRY   if add is true
2477/// DST  = SRC * MULTIPLIER + CARRY   if add is false
2478/// Requires 0 <= DSTPARTS <= SRCPARTS + 1.  If DST overlaps SRC
2479/// they must start at the same point, i.e. DST == SRC.
2480/// If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
2481/// returned.  Otherwise DST is filled with the least significant
2482/// DSTPARTS parts of the result, and if all of the omitted higher
2483/// parts were zero return zero, otherwise overflow occurred and
2484/// return one.
2485int 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)(static_cast <bool> (dst <= src || dst >= src + srcParts
) ? void (0) : __assert_fail ("dst <= src || dst >= src + srcParts"
, "llvm/lib/Support/APInt.cpp", 2490, __extension__ __PRETTY_FUNCTION__
));
assert(dstParts <= srcParts + 1)(static_cast <bool> (dstParts <= srcParts + 1) ? void
 (0) : __assert_fail ("dstParts <= srcParts + 1", "llvm/lib/Support/APInt.cpp"
, 2491, __extension__ __PRETTY_FUNCTION__));

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

for (unsigned i = 0; i < n; i++) {
  // [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.
  WordType srcPart = src[i];
  WordType low, mid, high;
  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)(static_cast <bool> (srcParts + 1 == dstParts) ? void (
0) : __assert_fail ("srcParts + 1 == dstParts", "llvm/lib/Support/APInt.cpp"
, 2543, __extension__ __PRETTY_FUNCTION__));
  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;
2562}

2564/// DST = LHS * RHS, where DST has the same width as the operands and
2565/// is filled with the least significant parts of the result.  Returns
2566/// one if overflow occurred, otherwise zero.  DST must be disjoint
2567/// from both operands.
2568int APInt::tcMultiply(WordType *dst, const WordType *lhs,
                    const WordType *rhs, unsigned parts) {
assert(dst != lhs && dst != rhs)(static_cast <bool> (dst != lhs && dst != rhs) ?
 void (0) : __assert_fail ("dst != lhs && dst != rhs"
, "llvm/lib/Support/APInt.cpp", 2570, __extension__ __PRETTY_FUNCTION__
));

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;
2580}

2582/// DST = LHS * RHS, where DST has width the sum of the widths of the
2583/// operands. No overflow occurs. DST must be disjoint from both operands.
2584void 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)(static_cast <bool> (dst != lhs && dst != rhs) ?
 void (0) : __assert_fail ("dst != lhs && dst != rhs"
, "llvm/lib/Support/APInt.cpp", 2591, __extension__ __PRETTY_FUNCTION__
));

tcSet(dst, 0, rhsParts);

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

2599// If RHS is zero LHS and REMAINDER are left unchanged, return one.
2600// Otherwise set LHS to LHS / RHS with the fractional part discarded,
2601// set REMAINDER to the remainder, return zero.  i.e.
2602//
2603//   OLD_LHS = RHS * LHS + REMAINDER
2604//
2605// SCRATCH is a bignum of the same size as the operands and result for
2606// use by the routine; its contents need not be initialized and are
2607// destroyed.  LHS, REMAINDER and SCRATCH must be distinct.
2608int APInt::tcDivide(WordType *lhs, const WordType *rhs,
                  WordType *remainder, WordType *srhs,
                  unsigned parts) {
assert(lhs != remainder && lhs != srhs && remainder != srhs)(static_cast <bool> (lhs != remainder && lhs !=
 srhs && remainder != srhs) ? void (0) : __assert_fail
 ("lhs != remainder && lhs != srhs && remainder != srhs"
, "llvm/lib/Support/APInt.cpp", 2611, __extension__ __PRETTY_FUNCTION__
));

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;
2646}

2648/// Shift a bignum left Cound bits in-place. Shifted in bits are zero. There are
2649/// no restrictions on Count.
2650void 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);
2673}

2675/// Shift a bignum right Count bits in-place. Shifted in bits are zero. There
2676/// are no restrictions on Count.
2677void 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);
2700}

2702// Comparison (unsigned) of two bignums.
2703int 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;
2712}

2714APInt 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.isZero())
    return Quo;
  return Quo + 1;
}
}
llvm_unreachable("Unknown APInt::Rounding enum")::llvm::llvm_unreachable_internal("Unknown APInt::Rounding enum"
, "llvm/lib/Support/APInt.cpp", 2729);
2730}

2732APInt llvm::APIntOps::RoundingSDiv(const APInt &A, const APInt &B,
                                 APInt::Rounding RM) {
switch (RM) {
case APInt::Rounding::DOWN:
case APInt::Rounding::UP: {
  APInt Quo, Rem;
  APInt::sdivrem(A, B, Quo, Rem);
  if (Rem.isZero())
    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")::llvm::llvm_unreachable_internal("Unknown APInt::Rounding enum"
, "llvm/lib/Support/APInt.cpp", 2759);
2760}

2762std::optional<APInt>
2763llvm::APIntOps::SolveQuadraticEquationWrap(APInt A, APInt B, APInt C,
                                         unsigned RangeWidth) {
unsigned CoeffWidth = A.getBitWidth();
assert(CoeffWidth == B.getBitWidth() && CoeffWidth == C.getBitWidth())(static_cast <bool> (CoeffWidth == B.getBitWidth() &&
 CoeffWidth == C.getBitWidth()) ? void (0) : __assert_fail ("CoeffWidth == B.getBitWidth() && CoeffWidth == C.getBitWidth()"
, "llvm/lib/Support/APInt.cpp", 2766, __extension__ __PRETTY_FUNCTION__
));
assert(RangeWidth <= CoeffWidth &&(static_cast <bool> (RangeWidth <= CoeffWidth &&
 "Value range width should be less than coefficient width") ?
 void (0) : __assert_fail ("RangeWidth <= CoeffWidth && \"Value range width should be less than coefficient width\""
, "llvm/lib/Support/APInt.cpp", 2768, __extension__ __PRETTY_FUNCTION__
))
       "Value range width should be less than coefficient width")(static_cast <bool> (RangeWidth <= CoeffWidth &&
 "Value range width should be less than coefficient width") ?
 void (0) : __assert_fail ("RangeWidth <= CoeffWidth && \"Value range width should be less than coefficient width\""
, "llvm/lib/Support/APInt.cpp", 2768, __extension__ __PRETTY_FUNCTION__
));
assert(RangeWidth > 1 && "Value range bit width should be > 1")(static_cast <bool> (RangeWidth > 1 && "Value range bit width should be > 1"
) ? void (0) : __assert_fail ("RangeWidth > 1 && \"Value range bit width should be > 1\""
, "llvm/lib/Support/APInt.cpp", 2769, __extension__ __PRETTY_FUNCTION__
));

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

// Identify 0 as a (non)solution immediately.
if (C.sextOrTrunc(RangeWidth).isZero()) {
  LLVM_DEBUG(dbgs() << __func__ << ": zero solution\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << __func__ << ": zero solution\n"
; } } 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())(static_cast <bool> (A.isStrictlyPositive()) ? void (0)
 : __assert_fail ("A.isStrictlyPositive()", "llvm/lib/Support/APInt.cpp"
, 2835, __extension__ __PRETTY_FUNCTION__));
  APInt T = V.abs().urem(A);
  if (T.isZero())
    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 { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << __func__ << ": updated coefficients "
 << A << "x^2 + " << B << "x + " <<
 C << ", rw:" << RangeWidth << '\n'; } } while
 (false)
                  << B << "x + " << C << ", rw:" << RangeWidth << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << __func__ << ": updated coefficients "
 << A << "x^2 + " << B << "x + " <<
 C << ", rw:" << RangeWidth << '\n'; } } while
 (false);

APInt D = SqrB - 4*A*C;
assert(D.isNonNegative() && "Negative discriminant")(static_cast <bool> (D.isNonNegative() && "Negative discriminant"
) ? void (0) : __assert_fail ("D.isNonNegative() && \"Negative discriminant\""
, "llvm/lib/Support/APInt.cpp", 2892, __extension__ __PRETTY_FUNCTION__
));
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")(static_cast <bool> (X.isNonNegative() && "Solution should be non-negative"
) ? void (0) : __assert_fail ("X.isNonNegative() && \"Solution should be non-negative\""
, "llvm/lib/Support/APInt.cpp", 2919, __extension__ __PRETTY_FUNCTION__
));

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

assert((SQ*SQ).sle(D) && "SQ = |_sqrt(D)_|, so SQ*SQ <= D")(static_cast <bool> ((SQ*SQ).sle(D) && "SQ = |_sqrt(D)_|, so SQ*SQ <= D"
) ? void (0) : __assert_fail ("(SQ*SQ).sle(D) && \"SQ = |_sqrt(D)_|, so SQ*SQ <= D\""
, "llvm/lib/Support/APInt.cpp", 2926, __extension__ __PRETTY_FUNCTION__
));
// 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.isZero() != VY.isZero();
// 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 { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << __func__ << ": no valid solution\n"
; } } while (false);
  return std::nullopt;
}

X += 1;
LLVM_DEBUG(dbgs() << __func__ << ": solution (wrap): " << X << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << __func__ << ": solution (wrap): "
 << X << '\n'; } } while (false);
return X;
2950}

2952std::optional<unsigned>
2953llvm::APIntOps::GetMostSignificantDifferentBit(const APInt &A, const APInt &B) {
assert(A.getBitWidth() == B.getBitWidth() && "Must have the same bitwidth")(static_cast <bool> (A.getBitWidth() == B.getBitWidth()
 && "Must have the same bitwidth") ? void (0) : __assert_fail
 ("A.getBitWidth() == B.getBitWidth() && \"Must have the same bitwidth\""
, "llvm/lib/Support/APInt.cpp", 2954, __extension__ __PRETTY_FUNCTION__
));
if (A == B)
  return std::nullopt;
return A.getBitWidth() - ((A ^ B).countl_zero() + 1);
2958}

2960APInt llvm::APIntOps::ScaleBitMask(const APInt &A, unsigned NewBitWidth,
                                 bool MatchAllBits) {
unsigned OldBitWidth = A.getBitWidth();
assert((((OldBitWidth % NewBitWidth) == 0) ||(static_cast <bool> ((((OldBitWidth % NewBitWidth) == 0
) || ((NewBitWidth % OldBitWidth) == 0)) && "One size should be a multiple of the other one. "
 "Can't do fractional scaling.") ? void (0) : __assert_fail (
"(((OldBitWidth % NewBitWidth) == 0) || ((NewBitWidth % OldBitWidth) == 0)) && \"One size should be a multiple of the other one. \" \"Can't do fractional scaling.\""
, "llvm/lib/Support/APInt.cpp", 2966, __extension__ __PRETTY_FUNCTION__
))
        ((NewBitWidth % OldBitWidth) == 0)) &&(static_cast <bool> ((((OldBitWidth % NewBitWidth) == 0
) || ((NewBitWidth % OldBitWidth) == 0)) && "One size should be a multiple of the other one. "
 "Can't do fractional scaling.") ? void (0) : __assert_fail (
"(((OldBitWidth % NewBitWidth) == 0) || ((NewBitWidth % OldBitWidth) == 0)) && \"One size should be a multiple of the other one. \" \"Can't do fractional scaling.\""
, "llvm/lib/Support/APInt.cpp", 2966, __extension__ __PRETTY_FUNCTION__
))
       "One size should be a multiple of the other one. "(static_cast <bool> ((((OldBitWidth % NewBitWidth) == 0
) || ((NewBitWidth % OldBitWidth) == 0)) && "One size should be a multiple of the other one. "
 "Can't do fractional scaling.") ? void (0) : __assert_fail (
"(((OldBitWidth % NewBitWidth) == 0) || ((NewBitWidth % OldBitWidth) == 0)) && \"One size should be a multiple of the other one. \" \"Can't do fractional scaling.\""
, "llvm/lib/Support/APInt.cpp", 2966, __extension__ __PRETTY_FUNCTION__
))
       "Can't do fractional scaling.")(static_cast <bool> ((((OldBitWidth % NewBitWidth) == 0
) || ((NewBitWidth % OldBitWidth) == 0)) && "One size should be a multiple of the other one. "
 "Can't do fractional scaling.") ? void (0) : __assert_fail (
"(((OldBitWidth % NewBitWidth) == 0) || ((NewBitWidth % OldBitWidth) == 0)) && \"One size should be a multiple of the other one. \" \"Can't do fractional scaling.\""
, "llvm/lib/Support/APInt.cpp", 2966, __extension__ __PRETTY_FUNCTION__
));

// Check for matching bitwidths.
if (OldBitWidth == NewBitWidth)
  return A;

APInt NewA = APInt::getZero(NewBitWidth);

// Check for null input.
if (A.isZero())
  return NewA;

if (NewBitWidth > OldBitWidth) {
  // Repeat bits.
  unsigned Scale = NewBitWidth / OldBitWidth;
  for (unsigned i = 0; i != OldBitWidth; ++i)
    if (A[i])
      NewA.setBits(i * Scale, (i + 1) * Scale);
} else {
  unsigned Scale = OldBitWidth / NewBitWidth;
  for (unsigned i = 0; i != NewBitWidth; ++i) {
    if (MatchAllBits) {
      if (A.extractBits(Scale, i * Scale).isAllOnes())
        NewA.setBit(i);
    } else {
      if (!A.extractBits(Scale, i * Scale).isZero())
        NewA.setBit(i);
    }
  }
}

return NewA;
2998}

3000/// StoreIntToMemory - Fills the StoreBytes bytes of memory starting from Dst
3001/// with the integer held in IntVal.
3002void llvm::StoreIntToMemory(const APInt &IntVal, uint8_t *Dst,
                          unsigned StoreBytes) {
assert((IntVal.getBitWidth()+7)/8 >= StoreBytes && "Integer too small!")(static_cast <bool> ((IntVal.getBitWidth()+7)/8 >= StoreBytes
 && "Integer too small!") ? void (0) : __assert_fail (
"(IntVal.getBitWidth()+7)/8 >= StoreBytes && \"Integer too small!\""
, "llvm/lib/Support/APInt.cpp", 3004, __extension__ __PRETTY_FUNCTION__
));
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);
}
3024}

3026/// LoadIntFromMemory - Loads the integer stored in the LoadBytes bytes starting
3027/// from Src into IntVal, which is assumed to be wide enough and to hold zero.
3028void llvm::LoadIntFromMemory(APInt &IntVal, const uint8_t *Src,
                           unsigned LoadBytes) {
assert((IntVal.getBitWidth()+7)/8 >= LoadBytes && "Integer too small!")(static_cast <bool> ((IntVal.getBitWidth()+7)/8 >= LoadBytes
 && "Integer too small!") ? void (0) : __assert_fail (
"(IntVal.getBitWidth()+7)/8 >= LoadBytes && \"Integer too small!\""
, "llvm/lib/Support/APInt.cpp", 3030, __extension__ __PRETTY_FUNCTION__
));
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);
}
3052}

←

/build/source/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 <optional>
24#include <utility>

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

32template <typename T> class SmallVectorImpl;
33template <typename T> class ArrayRef;
34template <typename T, typename Enable> 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///   * APInt supports zero-bit-width values, but operations that require bits
70///     are not defined on it (e.g. you cannot ask for the sign of a zero-bit
71///     integer).  This means that operations like zero extension and logical
72///     shifts are defined, but sign extension and ashr is not.  Zero bit values
73///     compare and hash equal to themselves, and countLeadingZeros returns 0.
74///
75class [[nodiscard]] APInt {
76public:
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);

/// \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) {
  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);

/// Default constructor that creates an APInt with a 1-bit zero value.
explicit APInt() { U.VAL = 0; }

/// Copy Constructor.
APInt(const APInt &that) : BitWidth(that.BitWidth) {
  if (isSingleWord())
5
←
Taking false branch→
30
←
Taking false branch→
    U.VAL = that.U.VAL;
  else
    initSlowCase(that);
6
←
Calling 'APInt::initSlowCase'→
10
←
Returned allocated memory→
31
←
Calling 'APInt::initSlowCase'→
}

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

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

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

/// Get the '0' value for the specified bit-width.
static APInt getZero(unsigned numBits) { return APInt(numBits, 0); }

LLVM_DEPRECATED("use getZero instead", "getZero")__attribute__((deprecated("use getZero instead", "getZero")))
static APInt getNullValue(unsigned numBits) { return getZero(numBits); }

/// Return an APInt zero bits wide.
static APInt getZeroWidth() { return getZero(0); }

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

/// Gets maximum signed value of APInt for a specific bit width.
static APInt getSignedMaxValue(unsigned numBits) {
  APInt API = getAllOnes(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);
}

/// Return an APInt of a specified width with all bits set.
static APInt getAllOnes(unsigned numBits) {
  return APInt(numBits, WORDTYPE_MAX, true);
}

LLVM_DEPRECATED("use getAllOnes instead", "getAllOnes")__attribute__((deprecated("use getAllOnes instead", "getAllOnes"
)))
static APInt getAllOnesValue(unsigned numBits) { return getAllOnes(numBits); }

/// 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) {
  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;
}

/// 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;
}

/// 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;
}

/// 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);

/// @}
/// \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() && !isZero(); }

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

/// Determine if this APInt Value only has the specified bit set.
///
/// \returns true if this APInt only has the specified bit set.
bool isOneBitSet(unsigned BitNo) const {
  return (*this)[BitNo] && popcount() == 1;
}

/// Determine if all bits are set.  This is true for zero-width values.
bool isAllOnes() const {
  if (BitWidth == 0)
    return true;
  if (isSingleWord())
    return U.VAL == WORDTYPE_MAX >> (APINT_BITS_PER_WORD - BitWidth);
  return countTrailingOnesSlowCase() == BitWidth;
}

LLVM_DEPRECATED("use isAllOnes instead", "isAllOnes")__attribute__((deprecated("use isAllOnes instead", "isAllOnes"
)))
bool isAllOnesValue() const { return isAllOnes(); }

/// Determine if this value is zero, i.e. all bits are clear.
bool isZero() const {
  if (isSingleWord())
    return U.VAL == 0;
  return countLeadingZerosSlowCase() == BitWidth;
}

LLVM_DEPRECATED("use isZero instead", "isZero")__attribute__((deprecated("use isZero instead", "isZero")))
bool isNullValue() const { return isZero(); }

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

LLVM_DEPRECATED("use isOne instead", "isOne")__attribute__((deprecated("use isOne instead", "isOne")))
bool isOneValue() const { return isOne(); }

/// 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 isAllOnes(); }

/// 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()) {
    assert(BitWidth && "zero width values not allowed")(static_cast <bool> (BitWidth && "zero width values not allowed"
) ? void (0) : __assert_fail ("BitWidth && \"zero width values not allowed\""
, "llvm/include/llvm/ADT/APInt.h", 399, __extension__ __PRETTY_FUNCTION__
));
    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 isZero(); }

/// 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()) {
    assert(BitWidth && "zero width values not allowed")(static_cast <bool> (BitWidth && "zero width values not allowed"
) ? void (0) : __assert_fail ("BitWidth && \"zero width values not allowed\""
, "llvm/include/llvm/ADT/APInt.h", 417, __extension__ __PRETTY_FUNCTION__
));
    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 { return getActiveBits() <= N; }

/// Check if this APInt has an N-bits signed integer value.
bool isSignedIntN(unsigned N) const { return getSignificantBits() <= 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()) {
    assert(BitWidth && "zero width values not allowed")(static_cast <bool> (BitWidth && "zero width values not allowed"
) ? void (0) : __assert_fail ("BitWidth && \"zero width values not allowed\""
, "llvm/include/llvm/ADT/APInt.h", 434, __extension__ __PRETTY_FUNCTION__
));
    return isPowerOf2_64(U.VAL);
  }
  return countPopulationSlowCase() == 1;
}

/// Check if this APInt's negated value is a power of two greater than zero.
bool isNegatedPowerOf2() const {
  assert(BitWidth && "zero width values not allowed")(static_cast <bool> (BitWidth && "zero width values not allowed"
) ? void (0) : __assert_fail ("BitWidth && \"zero width values not allowed\""
, "llvm/include/llvm/ADT/APInt.h", 442, __extension__ __PRETTY_FUNCTION__
));
  if (isNonNegative())
    return false;
  // NegatedPowerOf2 - shifted mask in the top bits.
  unsigned LO = countl_one();
  unsigned TZ = countr_zero();
  return (LO + TZ) == BitWidth;
}

/// 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 !isZero(); }

/// 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_MAX(18446744073709551615UL)) 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")(static_cast <bool> (numBits != 0 && "numBits must be non-zero"
) ? void (0) : __assert_fail ("numBits != 0 && \"numBits must be non-zero\""
, "llvm/include/llvm/ADT/APInt.h", 477, __extension__ __PRETTY_FUNCTION__
));
  assert(numBits <= BitWidth && "numBits out of range")(static_cast <bool> (numBits <= BitWidth && "numBits out of range"
) ? void (0) : __assert_fail ("numBits <= BitWidth && \"numBits out of range\""
, "llvm/include/llvm/ADT/APInt.h", 478, __extension__ __PRETTY_FUNCTION__
));
  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 non-empty 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 + countr_zero()) == BitWidth;
}

/// Return true if this APInt value contains a non-empty sequence of ones with
/// the remainder zero. If true, \p MaskIdx will specify the index of the
/// lowest set bit and \p MaskLen is updated to specify the length of the
/// mask, else neither are updated.
bool isShiftedMask(unsigned &MaskIdx, unsigned &MaskLen) const {
  if (isSingleWord())
    return isShiftedMask_64(U.VAL, MaskIdx, MaskLen);
  unsigned Ones = countPopulationSlowCase();
  unsigned LeadZ = countLeadingZerosSlowCase();
  unsigned TrailZ = countTrailingZerosSlowCase();
  if ((Ones + LeadZ + TrailZ) != BitWidth)
    return false;
  MaskLen = Ones;
  MaskIdx = TrailZ;
  return true;
}

/// 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;

/// 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.  Increment *this by 1.
///
/// \returns a new APInt value representing the original value of *this.
APInt operator++(int) {
  APInt API(*this);
  ++(*this);
  return API;
}

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

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

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

/// Logical negation operation on this APInt returns true if zero, like normal
/// integers.
bool operator!() const { return isZero(); }

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

/// Copy assignment operator.
///
/// \returns *this after assignment of RHS.
APInt &operator=(const APInt &RHS) {
  // The common case (both source or dest being inline) doesn't require
  // allocation or deallocation.
  if (isSingleWord() && RHS.isSingleWord()) {
    U.VAL = RHS.U.VAL;
    BitWidth = RHS.BitWidth;
    return *this;
  }

  assignSlowCase(RHS);
  return *this;
}

/// Move assignment operator.
APInt &operator=(APInt &&that) {
621#ifdef EXPENSIVE_CHECKS
  // Some std::shuffle implementations still do self-assignment.
  if (this == &that)
    return *this;
625#endif
  assert(this != &that && "Self-move not supported")(static_cast <bool> (this != &that && "Self-move not supported"
) ? void (0) : __assert_fail ("this != &that && \"Self-move not supported\""
, "llvm/include/llvm/ADT/APInt.h", 626, __extension__ __PRETTY_FUNCTION__
));
15
←
'?' condition is true→
  if (!isSingleWord())
16
←
Taking true branch→
    delete[] U.pVal;
17
←
Memory is released→

  // 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()) {
    U.VAL = RHS;
    return clearUnusedBits();
  }
  U.pVal[0] = RHS;
  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")(static_cast <bool> (BitWidth == RHS.BitWidth &&
 "Bit widths must be the same") ? void (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\""
, "llvm/include/llvm/ADT/APInt.h", 663, __extension__ __PRETTY_FUNCTION__
));
  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")(static_cast <bool> (BitWidth == RHS.BitWidth &&
 "Bit widths must be the same") ? void (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\""
, "llvm/include/llvm/ADT/APInt.h", 693, __extension__ __PRETTY_FUNCTION__
));
  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")(static_cast <bool> (BitWidth == RHS.BitWidth &&
 "Bit widths must be the same") ? void (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\""
, "llvm/include/llvm/ADT/APInt.h", 722, __extension__ __PRETTY_FUNCTION__
));
  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")(static_cast <bool> (ShiftAmt <= BitWidth &&
 "Invalid shift amount") ? void (0) : __assert_fail ("ShiftAmt <= BitWidth && \"Invalid shift amount\""
, "llvm/include/llvm/ADT/APInt.h", 774, __extension__ __PRETTY_FUNCTION__
));
  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")(static_cast <bool> (ShiftAmt <= BitWidth &&
 "Invalid shift amount") ? void (0) : __assert_fail ("ShiftAmt <= BitWidth && \"Invalid shift amount\""
, "llvm/include/llvm/ADT/APInt.h", 823, __extension__ __PRETTY_FUNCTION__
));
  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")(static_cast <bool> (ShiftAmt <= BitWidth &&
 "Invalid shift amount") ? void (0) : __assert_fail ("ShiftAmt <= BitWidth && \"Invalid shift amount\""
, "llvm/include/llvm/ADT/APInt.h", 847, __extension__ __PRETTY_FUNCTION__
));
  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;
}

/// relative logical shift right
APInt relativeLShr(int RelativeShift) const {
  return RelativeShift > 0 ? lshr(RelativeShift) : shl(-RelativeShift);
}

/// relative logical shift left
APInt relativeLShl(int RelativeShift) const {
  return relativeLShr(-RelativeShift);
}

/// relative arithmetic shift right
APInt relativeAShr(int RelativeShift) const {
  return RelativeShift > 0 ? ashr(RelativeShift) : shl(-RelativeShift);
}

/// relative arithmetic shift left
APInt relativeAShl(int RelativeShift) const {
  return relativeAShr(-RelativeShift);
}

/// 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;

/// Concatenate the bits from "NewLSB" onto the bottom of *this.  This is
/// equivalent to:
///   (this->zext(NewWidth) << NewLSB.getBitWidth()) | NewLSB.zext(NewWidth)
APInt concat(const APInt &NewLSB) const {
  /// If the result will be small, then both the merged values are small.
  unsigned NewWidth = getBitWidth() + NewLSB.getBitWidth();
  if (NewWidth <= APINT_BITS_PER_WORD)
    return APInt(NewWidth, (U.VAL << NewLSB.getBitWidth()) | NewLSB.U.VAL);
  return concatSlowCase(NewLSB);
}

/// 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.
///
/// \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.
///
/// 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.
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!")(static_cast <bool> (bitPosition < getBitWidth() &&
 "Bit position out of bounds!") ? void (0) : __assert_fail ("bitPosition < getBitWidth() && \"Bit position out of bounds!\""
, "llvm/include/llvm/ADT/APInt.h", 1022, __extension__ __PRETTY_FUNCTION__
));
  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")(static_cast <bool> (BitWidth == RHS.BitWidth &&
 "Comparison requires equal bit widths") ? void (0) : __assert_fail
 ("BitWidth == RHS.BitWidth && \"Comparison requires equal bit widths\""
, "llvm/include/llvm/ADT/APInt.h", 1035, __extension__ __PRETTY_FUNCTION__
));
  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() && getSignificantBits() > 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() && getSignificantBits() > 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")(static_cast <bool> (BitWidth == RHS.BitWidth &&
 "Bit widths must be the same") ? void (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\""
, "llvm/include/llvm/ADT/APInt.h", 1228, __extension__ __PRETTY_FUNCTION__
));
  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")(static_cast <bool> (BitWidth == RHS.BitWidth &&
 "Bit widths must be the same") ? void (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\""
, "llvm/include/llvm/ADT/APInt.h", 1236, __extension__ __PRETTY_FUNCTION__
));
  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 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 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 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;

/// @}
/// \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 the given bit to 1 whose position is given as "bitPosition".
void setBit(unsigned BitPosition) {
  assert(BitPosition < BitWidth && "BitPosition out of range")(static_cast <bool> (BitPosition < BitWidth &&
 "BitPosition out of range") ? void (0) : __assert_fail ("BitPosition < BitWidth && \"BitPosition out of range\""
, "llvm/include/llvm/ADT/APInt.h", 1309, __extension__ __PRETTY_FUNCTION__
));
  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")(static_cast <bool> (hiBit <= BitWidth && "hiBit out of range"
) ? void (0) : __assert_fail ("hiBit <= BitWidth && \"hiBit out of range\""
, "llvm/include/llvm/ADT/APInt.h", 1333, __extension__ __PRETTY_FUNCTION__
));
  assert(loBit <= BitWidth && "loBit out of range")(static_cast <bool> (loBit <= BitWidth && "loBit out of range"
) ? void (0) : __assert_fail ("loBit <= BitWidth && \"loBit out of range\""
, "llvm/include/llvm/ADT/APInt.h", 1334, __extension__ __PRETTY_FUNCTION__
));
  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")(static_cast <bool> (hiBit <= BitWidth && "hiBit out of range"
) ? void (0) : __assert_fail ("hiBit <= BitWidth && \"hiBit out of range\""
, "llvm/include/llvm/ADT/APInt.h", 1346, __extension__ __PRETTY_FUNCTION__
));
  assert(loBit <= BitWidth && "loBit out of range")(static_cast <bool> (loBit <= BitWidth && "loBit out of range"
) ? void (0) : __assert_fail ("loBit <= BitWidth && \"loBit out of range\""
, "llvm/include/llvm/ADT/APInt.h", 1347, __extension__ __PRETTY_FUNCTION__
));
  assert(loBit <= hiBit && "loBit greater than hiBit")(static_cast <bool> (loBit <= hiBit && "loBit greater than hiBit"
) ? void (0) : __assert_fail ("loBit <= hiBit && \"loBit greater than hiBit\""
, "llvm/include/llvm/ADT/APInt.h", 1348, __extension__ __PRETTY_FUNCTION__
));
  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")(static_cast <bool> (BitPosition < BitWidth &&
 "BitPosition out of range") ? void (0) : __assert_fail ("BitPosition < BitWidth && \"BitPosition out of range\""
, "llvm/include/llvm/ADT/APInt.h", 1386, __extension__ __PRETTY_FUNCTION__
));
  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")(static_cast <bool> (loBits <= BitWidth && "More bits than bitwidth"
) ? void (0) : __assert_fail ("loBits <= BitWidth && \"More bits than bitwidth\""
, "llvm/include/llvm/ADT/APInt.h", 1396, __extension__ __PRETTY_FUNCTION__
));
  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 - countl_zero(); }

/// 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 getSignificantBits() const {
  return BitWidth - getNumSignBits() + 1;
}

LLVM_DEPRECATED("use getSignificantBits instead", "getSignificantBits")__attribute__((deprecated("use getSignificantBits instead", "getSignificantBits"
)))
unsigned getMinSignedBits() const { return getSignificantBits(); }

/// 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")(static_cast <bool> (getActiveBits() <= 64 &&
 "Too many bits for uint64_t") ? void (0) : __assert_fail ("getActiveBits() <= 64 && \"Too many bits for uint64_t\""
, "llvm/include/llvm/ADT/APInt.h", 1497, __extension__ __PRETTY_FUNCTION__
));
  return U.pVal[0];
}

/// Get zero extended value if possible
///
/// 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 no value is returned.
std::optional<uint64_t> tryZExtValue() const {
  return (getActiveBits() <= 64) ? std::optional<uint64_t>(getZExtValue())
                                 : std::nullopt;
};

/// 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(getSignificantBits() <= 64 && "Too many bits for int64_t")(static_cast <bool> (getSignificantBits() <= 64 &&
 "Too many bits for int64_t") ? void (0) : __assert_fail ("getSignificantBits() <= 64 && \"Too many bits for int64_t\""
, "llvm/include/llvm/ADT/APInt.h", 1519, __extension__ __PRETTY_FUNCTION__
));
  return int64_t(U.pVal[0]);
}

/// Get sign extended value if possible
///
/// This method attempts to return the value of this APInt as a sign extended
/// int64_t. The bitwidth must be <= 64 or the value must fit within an
/// int64_t. Otherwise no value is returned.
std::optional<int64_t> trySExtValue() const {
  return (getSignificantBits() <= 64) ? std::optional<int64_t>(getSExtValue())
                                      : std::nullopt;
};

/// 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);

/// Get the bits that are sufficient to represent the string value. This may
/// over estimate the amount of bits required, but it does not require
/// parsing the value in the string.
static unsigned getSufficientBitsNeeded(StringRef Str, uint8_t Radix);

/// The APInt version of std::countl_zero.
///
/// 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 countl_zero() const {
  if (isSingleWord()) {
    unsigned unusedBits = APINT_BITS_PER_WORD - BitWidth;
    return llvm::countl_zero(U.VAL) - unusedBits;
  }
  return countLeadingZerosSlowCase();
}

unsigned countLeadingZeros() const { return countl_zero(); }

/// Count the number of leading one bits.
///
/// This function is an APInt version of std::countl_one. 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 countl_one() const {
  if (isSingleWord()) {
    if (LLVM_UNLIKELY(BitWidth == 0)__builtin_expect((bool)(BitWidth == 0), false))
      return 0;
    return llvm::countl_one(U.VAL << (APINT_BITS_PER_WORD - BitWidth));
  }
  return countLeadingOnesSlowCase();
}

unsigned countLeadingOnes() const { return countl_one(); }

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

/// Count the number of trailing zero bits.
///
/// This function is an APInt version of std::countr_zero. 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 countr_zero() const {
  if (isSingleWord()) {
    unsigned TrailingZeros = llvm::countr_zero(U.VAL);
    return (TrailingZeros > BitWidth ? BitWidth : TrailingZeros);
  }
  return countTrailingZerosSlowCase();
}

unsigned countTrailingZeros() const { return countr_zero(); }

/// Count the number of trailing one bits.
///
/// This function is an APInt version of std::countr_one. 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 countr_one() const {
  if (isSingleWord())
    return llvm::countr_one(U.VAL);
  return countTrailingOnesSlowCase();
}

unsigned countTrailingOnes() const { return countr_one(); }

/// Count the number of bits set.
///
/// This function is an APInt version of std::popcount. 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 popcount() const {
  if (isSingleWord())
    return llvm::popcount(U.VAL);
  return countPopulationSlowCase();
}

LLVM_DEPRECATED("use popcount instead", "popcount")__attribute__((deprecated("use popcount instead", "popcount")
))
unsigned countPopulation() const { return popcount(); }

/// @}
/// \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 llvm::bit_cast<double>(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 llvm::bit_cast<float>(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, llvm::bit_cast<uint64_t>(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, llvm::bit_cast<uint32_t>(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;

/// \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.  Note that the "most negative" signed number (e.g. -128 for 8 bit
/// wide APInt) is unchanged due to how negation works.
APInt abs() const {
  if (isNegative())
    return -(*this);
  return *this;
}

/// \returns the multiplicative inverse for a given modulo.
APInt multiplicativeInverse(const APInt &modulo) 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);

/// 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);
}

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

/// debug method
void dump() const;

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

1874private:
/// 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 = 1; ///< The number of bits in this APInt.

friend struct DenseMapInfo<APInt, void>;
friend class APSInt;

/// This constructor is used only internally for speed of construction of
/// temporaries. It is unsafe since it takes ownership of the pointer, 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 the specified bit position is in.
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 (LLVM_UNLIKELY(BitWidth == 0)__builtin_expect((bool)(BitWidth == 0), false))
    mask = 0;

  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 concat.
APInt concatSlowCase(const APInt &NewLSB) const;

/// 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__));

/// @}
2043};

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

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

2049/// Unary bitwise complement operator.
2050///
2051/// \returns an APInt that is the bitwise complement of \p v.
2052inline APInt operator~(APInt v) {
v.flipAllBits();
return v;
2055}

2057inline APInt operator&(APInt a, const APInt &b) {
a &= b;
return a;
2060}

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

2067inline APInt operator&(APInt a, uint64_t RHS) {
a &= RHS;
return a;
2070}

2072inline APInt operator&(uint64_t LHS, APInt b) {
b &= LHS;
return b;
2075}

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

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

2087inline APInt operator|(APInt a, uint64_t RHS) {
a |= RHS;
return a;
2090}

2092inline APInt operator|(uint64_t LHS, APInt b) {
b |= LHS;
return b;
2095}

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

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

2107inline APInt operator^(APInt a, uint64_t RHS) {
a ^= RHS;
return a;
2110}

2112inline APInt operator^(uint64_t LHS, APInt b) {
b ^= LHS;
return b;
2115}

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

2122inline APInt operator-(APInt v) {
v.negate();
return v;
2125}

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

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

2137inline APInt operator+(APInt a, uint64_t RHS) {
a += RHS;
return a;
2140}

2142inline APInt operator+(uint64_t LHS, APInt b) {
b += LHS;
return b;
2145}

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

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

2158inline APInt operator-(APInt a, uint64_t RHS) {
a -= RHS;
return a;
2161}

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

2169inline APInt operator*(APInt a, uint64_t RHS) {
a *= RHS;
return a;
2172}

2174inline APInt operator*(uint64_t LHS, APInt b) {
b *= LHS;
return b;
2177}

2179namespace APIntOps {

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

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

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

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

2201/// Compute GCD of two unsigned APInt values.
2202///
2203/// This function returns the greatest common divisor of the two APInt values
2204/// using Stein's algorithm.
2205///
2206/// \returns the greatest common divisor of A and B.
2207APInt GreatestCommonDivisor(APInt A, APInt B);

2209/// Converts the given APInt to a double value.
2210///
2211/// Treats the APInt as an unsigned value for conversion purposes.
2212inline double RoundAPIntToDouble(const APInt &APIVal) {
return APIVal.roundToDouble();
2214}

2216/// Converts the given APInt to a double value.
2217///
2218/// Treats the APInt as a signed value for conversion purposes.
2219inline double RoundSignedAPIntToDouble(const APInt &APIVal) {
return APIVal.signedRoundToDouble();
2221}

2223/// Converts the given APInt to a float value.
2224inline float RoundAPIntToFloat(const APInt &APIVal) {
return float(RoundAPIntToDouble(APIVal));
2226}

2228/// Converts the given APInt to a float value.
2229///
2230/// Treats the APInt as a signed value for conversion purposes.
2231inline float RoundSignedAPIntToFloat(const APInt &APIVal) {
return float(APIVal.signedRoundToDouble());
2233}

2235/// Converts the given double value into a APInt.
2236///
2237/// This function convert a double value to an APInt value.
2238APInt RoundDoubleToAPInt(double Double, unsigned width);

2240/// Converts a float value into a APInt.
2241///
2242/// Converts a float value into an APInt value.
2243inline APInt RoundFloatToAPInt(float Float, unsigned width) {
return RoundDoubleToAPInt(double(Float), width);
2245}

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

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

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

2289/// Compare two values, and if they are different, return the position of the
2290/// most significant bit that is different in the values.
2291std::optional<unsigned> GetMostSignificantDifferentBit(const APInt &A,
                                                     const APInt &B);

2294/// Splat/Merge neighboring bits to widen/narrow the bitmask represented
2295/// by \param A to \param NewBitWidth bits.
2296///
2297/// MatchAnyBits: (Default)
2298/// e.g. ScaleBitMask(0b0101, 8) -> 0b00110011
2299/// e.g. ScaleBitMask(0b00011011, 4) -> 0b0111
2300///
2301/// MatchAllBits:
2302/// e.g. ScaleBitMask(0b0101, 8) -> 0b00110011
2303/// e.g. ScaleBitMask(0b00011011, 4) -> 0b0001
2304/// A.getBitwidth() or NewBitWidth must be a whole multiples of the other.
2305APInt ScaleBitMask(const APInt &A, unsigned NewBitWidth,
                 bool MatchAllBits = false);
2307} // namespace APIntOps

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

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

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

2321/// Provide DenseMapInfo for APInt.
2322template <> struct DenseMapInfo<APInt, void> {
static inline APInt getEmptyKey() {
  APInt V(nullptr, 0);
  V.U.VAL = ~0ULL;
  return V;
}

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

static unsigned getHashValue(const APInt &Key);

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

2342} // namespace llvm

2344#endif