/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp

Bug Summary

File:	lib/Support/APInt.cpp
Warning:	line 1512, column 19 Use of zero-allocated memory
Annotated Source Code

Press '?' to see keyboard shortcuts
Show analyzer invocation
clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name APInt.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-eagerly-assume -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 -mrelocation-model pic -pic-level 2 -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-7/lib/clang/7.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-7~svn338205/build-llvm/lib/Support -I /build/llvm-toolchain-snapshot-7~svn338205/lib/Support -I /build/llvm-toolchain-snapshot-7~svn338205/build-llvm/include -I /build/llvm-toolchain-snapshot-7~svn338205/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/x86_64-linux-gnu/c++/8 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/x86_64-linux-gnu/c++/8 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/backward -internal-isystem /usr/include/clang/7.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-7/lib/clang/7.0.0/include -internal-externc-isystem /usr/lib/gcc/x86_64-linux-gnu/8/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-7~svn338205/build-llvm/lib/Support -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-07-29-043837-17923-1 -x c++ /build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp -faddrsig
1//===-- APInt.cpp - Implement APInt class ---------------------------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file implements a class to represent arbitrary precision integer
11// constant values and provide a variety of arithmetic operations on them.
12//
13//===----------------------------------------------------------------------===//

15#include "llvm/ADT/APInt.h"
16#include "llvm/ADT/ArrayRef.h"
17#include "llvm/ADT/FoldingSet.h"
18#include "llvm/ADT/Hashing.h"
19#include "llvm/ADT/SmallString.h"
20#include "llvm/ADT/StringRef.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 <climits>
27#include <cmath>
28#include <cstdlib>
29#include <cstring>
30using namespace llvm;

32#define DEBUG_TYPE"apint" "apint"

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

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

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

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

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

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

  radix = 10;
}

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

return -1U;
73}


76void 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] = WORD_MAX;
clearUnusedBits();
83}

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

90void APInt::initFromArray(ArrayRef<uint64_t> bigVal) {
assert(BitWidth && "Bitwidth too small")(static_cast <bool> (BitWidth && "Bitwidth too small"
) ? void (0) : __assert_fail ("BitWidth && \"Bitwidth too small\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 91, __extension__ __PRETTY_FUNCTION__));
assert(bigVal.data() && "Null pointer detected!")(static_cast <bool> (bigVal.data() && "Null pointer detected!"
) ? void (0) : __assert_fail ("bigVal.data() && \"Null pointer detected!\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 92, __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();
105}

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

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

117APInt::APInt(unsigned numbits, StringRef Str, uint8_t radix)
: BitWidth(numbits) {
assert(BitWidth && "Bitwidth too small")(static_cast <bool> (BitWidth && "Bitwidth too small"
) ? void (0) : __assert_fail ("BitWidth && \"Bitwidth too small\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 119, __extension__ __PRETTY_FUNCTION__));
fromString(numbits, Str, radix);
121}

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

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

// Update BitWidth.
BitWidth = NewBitWidth;

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

142void 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);
155}

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

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

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

189/// Adds the RHS APint to this APInt.
190/// @returns this, after addition of RHS.
191/// Addition assignment operator.
192APInt& 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\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 193, __extension__ __PRETTY_FUNCTION__));
if (isSingleWord())
  U.VAL += RHS.U.VAL;
else
  tcAdd(U.pVal, RHS.U.pVal, 0, getNumWords());
return clearUnusedBits();
199}

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

209/// Subtracts the RHS APInt from this APInt
210/// @returns this, after subtraction
211/// Subtraction assignment operator.
212APInt& 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\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 213, __extension__ __PRETTY_FUNCTION__));
if (isSingleWord())
  U.VAL -= RHS.U.VAL;
else
  tcSubtract(U.pVal, RHS.U.pVal, 0, getNumWords());
return clearUnusedBits();
219}

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

229APInt 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\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 230, __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;
240}

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

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

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

254APInt& 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\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 255, __extension__ __PRETTY_FUNCTION__));
*this = *this * RHS;
return *this;
258}

260APInt& 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();
268}

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

274int 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\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 275, __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());
280}

282int 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\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 283, __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());
300}

302void 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 = WORD_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 = WORD_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] = WORD_MAX;
327}

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

335/// Toggle a given bit to its opposite value whose position is given
336/// as "bitPosition".
337/// Toggles a given bit to its opposite value.
338void 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!\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 339, __extension__ __PRETTY_FUNCTION__));
if ((*this)[bitPosition]) clearBit(bitPosition);
else setBit(bitPosition);
342}

344void APInt::insertBits(const APInt &subBits, unsigned bitPosition) {
unsigned subBitWidth = subBits.getBitWidth();
assert(0 < subBitWidth && (subBitWidth + bitPosition) <= BitWidth &&(static_cast <bool> (0 < subBitWidth && (subBitWidth
 + bitPosition) <= BitWidth && "Illegal bit insertion"
) ? void (0) : __assert_fail ("0 < subBitWidth && (subBitWidth + bitPosition) <= BitWidth && \"Illegal bit insertion\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 347, __extension__ __PRETTY_FUNCTION__))
       "Illegal bit insertion")(static_cast <bool> (0 < subBitWidth && (subBitWidth
 + bitPosition) <= BitWidth && "Illegal bit insertion"
) ? void (0) : __assert_fail ("0 < subBitWidth && (subBitWidth + bitPosition) <= BitWidth && \"Illegal bit insertion\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 347, __extension__ __PRETTY_FUNCTION__));

// 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 = WORD_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 = WORD_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 = WORD_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) {
  if (subBits[i])
    setBit(bitPosition + i);
  else
    clearBit(bitPosition + i);
}
401}

403APInt APInt::extractBits(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\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 404, __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\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 406, __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\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 406, __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, makeArrayRef(U.pVal + loWord, 1 + hiWord - loWord));

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

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

return Result.clearUnusedBits();
438}

440unsigned APInt::getBitsNeeded(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\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 441, __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!\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 444, __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!\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 444, __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!\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 444, __extension__ __PRETTY_FUNCTION__));

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.\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 454, __extension__ __PRETTY_FUNCTION__));
}

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

// FIXME: base 36

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

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

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

// Compute how many bits are required. If the log is infinite, assume we need
// just bit.
unsigned log = tmp.logBase2();
if (log == (unsigned)-1) {
  return isNegative + 1;
} else {
  return isNegative + log + 1;
}
491}

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

return hash_combine_range(Arg.U.pVal, Arg.U.pVal + Arg.getNumWords());
498}

500bool 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!\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 502, __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!\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 502, __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);
506}

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

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

520/// Return a value containing V broadcasted over NewLen bits.
521APInt 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!\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 522, __extension__ __PRETTY_FUNCTION__));

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

return Val;
529}

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

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

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

582unsigned APInt::countTrailingOnesSlowCase() const {
unsigned Count = 0;
unsigned i = 0;
for (; i < getNumWords() && U.pVal[i] == WORD_MAX; ++i)
  Count += APINT_BITS_PER_WORD;
if (i < getNumWords())
  Count += llvm::countTrailingOnes(U.pVal[i]);
assert(Count <= BitWidth)(static_cast <bool> (Count <= BitWidth) ? void (0) :
 __assert_fail ("Count <= BitWidth", "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 589, __extension__ __PRETTY_FUNCTION__));
return Count;
591}

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

600bool 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;
606}

608bool 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;
614}

616APInt APInt::byteSwap() const {
assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!")(static_cast <bool> (BitWidth >= 16 && BitWidth
 % 16 == 0 && "Cannot byteswap!") ? void (0) : __assert_fail
 ("BitWidth >= 16 && BitWidth % 16 == 0 && \"Cannot byteswap!\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 617, __extension__ __PRETTY_FUNCTION__));
if (BitWidth == 16)
  return APInt(BitWidth, ByteSwap_16(uint16_t(U.VAL)));
if (BitWidth == 32)
  return APInt(BitWidth, ByteSwap_32(unsigned(U.VAL)));
if (BitWidth == 48) {
  unsigned Tmp1 = unsigned(U.VAL >> 16);
  Tmp1 = ByteSwap_32(Tmp1);
  uint16_t Tmp2 = uint16_t(U.VAL);
  Tmp2 = ByteSwap_16(Tmp2);
  return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
}
if (BitWidth == 64)
  return APInt(BitWidth, ByteSwap_64(U.VAL));

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

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

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

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

Reversed <<= S;
return Reversed;
668}

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

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

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

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

return A;
711}

713APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) {
union {
  double D;
  uint64_t I;
} T;
T.D = Double;

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

// Get the 11-bit exponent and adjust for the 1023 bit bias
int64_t exp = ((T.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 = (T.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;
747}

749/// This function converts this APInt to a double.
750/// The layout for double is as following (IEEE Standard 754):
751///  --------------------------------------
752/// |  Sign    Exponent    Fraction    Bias |
753/// |-------------------------------------- |
754/// |  1[63]   11[62-52]   52[51-00]   1023 |
755///  --------------------------------------
756double 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?\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 800, __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;
union {
  double D;
  uint64_t I;
} T;
T.I = sign | (exp << 52) | mantissa;
return T.D;
814}

816// Truncate to new width.
817APInt 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\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 818, __extension__ __PRETTY_FUNCTION__));
assert(width && "Can't truncate to 0 bits")(static_cast <bool> (width && "Can't truncate to 0 bits"
) ? void (0) : __assert_fail ("width && \"Can't truncate to 0 bits\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 819, __extension__ __PRETTY_FUNCTION__));

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

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

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

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

return Result;
837}

839// Sign extend to a new width.
840APInt 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\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 841, __extension__ __PRETTY_FUNCTION__));

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

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

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

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

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

863//  Zero extend to a new width.
864APInt 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\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 865, __extension__ __PRETTY_FUNCTION__));

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

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

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

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

return Result;
880}

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

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

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

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

910/// Arithmetic right-shift this APInt by shiftAmt.
911/// Arithmetic right-shift function.
912void APInt::ashrInPlace(const APInt &shiftAmt) {
ashrInPlace((unsigned)shiftAmt.getLimitedValue(BitWidth));
914}

916/// Arithmetic right-shift this APInt by shiftAmt.
917/// Arithmetic right-shift function.
918void 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();
957}

959/// Logical right-shift this APInt by shiftAmt.
960/// Logical right-shift function.
961void APInt::lshrInPlace(const APInt &shiftAmt) {
lshrInPlace((unsigned)shiftAmt.getLimitedValue(BitWidth));
963}

965/// Logical right-shift this APInt by shiftAmt.
966/// Logical right-shift function.
967void APInt::lshrSlowCase(unsigned ShiftAmt) {
tcShiftRight(U.pVal, getNumWords(), ShiftAmt);
969}

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

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

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

997APInt APInt::rotl(const APInt &rotateAmt) const {
return rotl(rotateModulo(BitWidth, rotateAmt));
999}

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

1008APInt APInt::rotr(const APInt &rotateAmt) const {
return rotr(rotateModulo(BitWidth, rotateAmt));
1010}

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

1019// Square Root - this method computes and returns the square root of "this".
1020// Three mechanisms are used for computation. For small values (<= 5 bits),
1021// a table lookup is done. This gets some performance for common cases. For
1022// values using less than 52 bits, the value is converted to double and then
1023// the libc sqrt function is called. The result is rounded and then converted
1024// back to a uint64_t which is then used to construct the result. Finally,
1025// the Babylonian method for computing square roots is used.
1026APInt 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\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 1092, __extension__ __PRETTY_FUNCTION__));
APInt midpoint((nextSquare - square).udiv(two));
APInt offset(*this - square);
if (offset.ult(midpoint))
  return x_old;
return x_old + 1;
1098}

1100/// Computes the multiplicative inverse of this APInt for a given modulo. The
1101/// iterative extended Euclidean algorithm is used to solve for this value,
1102/// however we simplify it to speed up calculating only the inverse, and take
1103/// advantage of div+rem calculations. We also use some tricks to avoid copying
1104/// (potentially large) APInts around.
1105APInt 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\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 1106, __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]);
1145}

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

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

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

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

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

1239/// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
1240/// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
1241/// variables here have the same names as in the algorithm. Comments explain
1242/// the algorithm and any deviation from it.
1243static 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\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 1245, __extension__ __PRETTY_FUNCTION__));
assert(v && "Must provide divisor")(static_cast <bool> (v && "Must provide divisor"
) ? void (0) : __assert_fail ("v && \"Must provide divisor\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 1246, __extension__ __PRETTY_FUNCTION__));
assert(q && "Must provide quotient")(static_cast <bool> (q && "Must provide quotient"
) ? void (0) : __assert_fail ("q && \"Must provide quotient\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 1247, __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\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 1248, __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\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 1249, __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;

1254// The DEBUG macros here tend to be spam in the debug output if you're not
1255// debugging this code. Disable them unless KNUTH_DEBUG is defined.
1256#pragma push_macro("LLVM_DEBUG")
1257#ifndef KNUTH_DEBUG
1258#undef LLVM_DEBUG
1259#define LLVM_DEBUG(X)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { X; } } while (false)                                                          \
do {                                                                         \
} while (false)
1262#endif

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

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

// D2. [Initialize j.]  Set j to m. This is the loop counter over the places.
int j = m;
do {
  LLVM_DEBUG(dbgs() << "KnuthDiv: quotient digit #" << j << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << "KnuthDiv: quotient digit #" <<
 j << '\n'; } } 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]);
  LLVM_DEBUG(dbgs() << "KnuthDiv: dividend == " << dividend << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << "KnuthDiv: dividend == " <<
 dividend << '\n'; } } 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--;
  }
  LLVM_DEBUG(dbgs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << "KnuthDiv: qp == " << qp <<
 ", rp == " << rp << '\n'; } } 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);
    LLVM_DEBUG(dbgs() << "KnuthDiv: u[j+i] = " << u[j + i]do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << "KnuthDiv: u[j+i] = " << u
[j + i] << ", borrow = " << borrow << '\n';
 } } while (false)
                      << ", borrow = " << borrow << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << "KnuthDiv: u[j+i] = " << u
[j + i] << ", borrow = " << borrow << '\n';
 } } while (false);
  }
  bool isNeg = u[j+n] < borrow;
  u[j+n] -= Lo_32(borrow);

  LLVM_DEBUG(dbgs() << "KnuthDiv: after subtraction:")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << "KnuthDiv: after subtraction:"; }
 } while (false);
  LLVM_DEBUG(for (int i = m + n; i >= 0; i--) dbgs() << " " << u[i])do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { for (int i = m + n; i >= 0; i--) dbgs() <<
 " " << u[i]; } } while (false);
  LLVM_DEBUG(dbgs() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << '\n'; } } 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;
  }
  LLVM_DEBUG(dbgs() << "KnuthDiv: after correction:")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << "KnuthDiv: after correction:"; }
 } while (false);
  LLVM_DEBUG(for (int i = m + n; i >= 0; i--) dbgs() << " " << u[i])do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { for (int i = m + n; i >= 0; i--) dbgs() <<
 " " << u[i]; } } while (false);
  LLVM_DEBUG(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << "\nKnuthDiv: digit result = " <<
 q[j] << '\n'; } } while (false);

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

LLVM_DEBUG(dbgs() << "KnuthDiv: quotient:")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << "KnuthDiv: quotient:"; } } while
 (false);
LLVM_DEBUG(for (int i = m; i >= 0; i--) dbgs() << " " << q[i])do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { for (int i = m; i >= 0; i--) dbgs() << " "
 << q[i]; } } while (false);
LLVM_DEBUG(dbgs() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << '\n'; } } 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;
    LLVM_DEBUG(dbgs() << "KnuthDiv: remainder:")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << "KnuthDiv: remainder:"; } } while
 (false);
    for (int i = n-1; i >= 0; i--) {
      r[i] = (u[i] >> shift) | carry;
      carry = u[i] << (32 - shift);
      LLVM_DEBUG(dbgs() << " " << r[i])do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << " " << r[i]; } } while (false
);
    }
  } else {
    for (int i = n-1; i >= 0; i--) {
      r[i] = u[i];
      LLVM_DEBUG(dbgs() << " " << r[i])do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << " " << r[i]; } } while (false
);
    }
  }
  LLVM_DEBUG(dbgs() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << '\n'; } } while (false);
}
LLVM_DEBUG(dbgs() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << '\n'; } } while (false);

1404#pragma pop_macro("LLVM_DEBUG")
1405}

1407void 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\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 1409, __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) {
26
←
'?' condition is true→
27
←
Assuming the condition is false→
28
←
Taking false branch→
  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)
29
←
Taking true branch→
    R = new uint32_t[n];
}

// Initialize the dividend
memset(U, 0, (m+n+1)*sizeof(uint32_t));
for (unsigned i = 0; i < lhsWords; ++i) {
30
←
Loop condition is true.  Entering loop body→
31
←
Loop condition is true.  Entering loop body→
32
←
Assuming 'i' is >= 'lhsWords'→
33
←
Loop condition is false. Execution continues on line 1449→
  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) {
34
←
Loop condition is true.  Entering loop body→
35
←
Assuming 'i' is >= 'rhsWords'→
36
←
Loop condition is false. Execution continues on line 1460→
  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)
37
←
Taking true branch→
  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--) {
38
←
Loop condition is false. Execution continues on line 1472→
  n--;
  m++;
}
for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
39
←
Loop condition is false. Execution continues on line 1481→
  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?\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 1481, __extension__ __PRETTY_FUNCTION__));
if (n == 1) {
40
←
Assuming 'n' is not equal to 1→
41
←
Taking false branch→
  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) {
42
←
Taking true branch→
  for (unsigned i = 0; i < lhsWords; ++i)
43
←
Loop condition is true.  Entering loop body→
    Quotient[i] = Make_64(Q[i*2+1], Q[i*2]);
44
←
Use of zero-allocated memory
}

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

1530APInt 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\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 1531, __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?\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 1535, __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???\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 1543, __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;
1566}

1568APInt 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?\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 1569, __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;
1599}

1601APInt 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);
1610}

1612APInt 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);
1621}

1623APInt 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\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 1624, __extension__ __PRETTY_FUNCTION__));
if (isSingleWord()) {
  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?\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 1626, __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 ???\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 1636, __extension__ __PRETTY_FUNCTION__));

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

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

1661uint64_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?\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 1662, __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;
1691}

1693APInt 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);
1702}

1704int64_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);
1713}

1715void 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\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 1717, __extension__ __PRETTY_FUNCTION__));
unsigned BitWidth = LHS.BitWidth;

// First, deal with the easy case
if (LHS.isSingleWord()) {
6
←
Taking false branch→
  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?\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 1722, __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 ???\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 1734, __extension__ __PRETTY_FUNCTION__));

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

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

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

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

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

if (lhsWords == 1) { // rhsWords is 1 if lhsWords is 1.
23
←
Assuming 'lhsWords' is not equal to 1→
24
←
Taking false branch→
  // There is only one word to consider so use the native versions.
  uint64_t lhsValue = LHS.U.pVal[0];
  uint64_t rhsValue = RHS.U.pVal[0];
  Quotient = lhsValue / rhsValue;
  Remainder = lhsValue % rhsValue;
  return;
}

// Okay, lets do it the long way
divide(LHS.U.pVal, lhsWords, RHS.U.pVal, rhsWords, Quotient.U.pVal,
25
←
Calling 'APInt::divide'→
       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);
1784}

1786void 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?\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 1788, __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);
1845}

1847void APInt::sdivrem(const APInt &LHS, const APInt &RHS,
                  APInt &Quotient, APInt &Remainder) {
if (LHS.isNegative()) {
3
←
Taking false branch→
  if (RHS.isNegative())
    APInt::udivrem(-LHS, -RHS, Quotient, Remainder);
  else {
    APInt::udivrem(-LHS, RHS, Quotient, Remainder);
    Quotient.negate();
  }
  Remainder.negate();
} else if (RHS.isNegative()) {
4
←
Taking false branch→
  APInt::udivrem(LHS, -RHS, Quotient, Remainder);
  Quotient.negate();
} else {
  APInt::udivrem(LHS, RHS, Quotient, Remainder);
5
←
Calling 'APInt::udivrem'→
}
1863}

1865void 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;
1883}

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

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

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

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

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

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

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

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

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

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

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

return *this << ShAmt;
1948}

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

Overflow = ShAmt.ugt(countLeadingZeros());

return *this << ShAmt;
1958}




1963void 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\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 1965, __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!\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 1968, __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!\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 1968, __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!\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 1968, __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.\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 1976, __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\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 1978, __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\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 1979, __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\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 1980, __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\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 1982, __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\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 1982, __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\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 1996, __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();
2012}

2014void 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!\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 2018, __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!\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 2018, __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!\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 2018, __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!", "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 2037);
  }
}

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

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

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

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

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

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

APInt Tmp(*this);

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

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

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

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

  while (Tmp.getBoolValue()) {
    unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;
    Str.push_back(Digits[Digit]);
    Tmp.lshrInPlace(ShiftAmt);
  }
} else {
  while (Tmp.getBoolValue()) {
    uint64_t Digit;
    udivrem(Tmp, Radix, Tmp, Digit);
    assert(Digit < Radix && "divide failed")(static_cast <bool> (Digit < Radix && "divide failed"
) ? void (0) : __assert_fail ("Digit < Radix && \"divide failed\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 2118, __extension__ __PRETTY_FUNCTION__));
    Str.push_back(Digits[Digit]);
  }
}

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

2127/// Returns the APInt as a std::string. Note that this is an inefficient method.
2128/// It is better to pass in a SmallVector/SmallString to the methods above.
2129std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const {
SmallString<40> S;
toString(S, Radix, Signed, /* formatAsCLiteral = */false);
return S.str();
2133}

2135#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2136LLVM_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";
2142}
2143#endif

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

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

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

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

2161/* Returns the integer part with the least significant BITS set.
 BITS cannot be zero.  */
2163static 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"
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 2164, __extension__ __PRETTY_FUNCTION__));

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

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

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

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

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

2191/* Sets the least significant part of a bignum to the input value, and
 zeroes out higher parts.  */
2193void APInt::tcSet(WordType *dst, WordType part, unsigned parts) {
assert(parts > 0)(static_cast <bool> (parts > 0) ? void (0) : __assert_fail
 ("parts > 0", "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 2194, __extension__ __PRETTY_FUNCTION__));

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

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

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

return true;
2214}

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

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

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

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

    return lsb + i * APINT_BITS_PER_WORD;
  }
}

return -1U;
2243}

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

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

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

return -1U;
2259}

2261/* 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.  */
2265void
2266APInt::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", "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 2269, __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;
2293}

2295/* DST += RHS + C where C is zero or one.  Returns the carry flag.  */
2296APInt::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", "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 2298, __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;
2312}

2314/// This function adds a single "word" integer, src, to the multiple
2315/// "word" integer array, dst[]. dst[] is modified to reflect the addition and
2316/// 1 is returned if there is a carry out, otherwise 0 is returned.
2317/// @returns the carry of the addition.
2318APInt::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;
2328}

2330/* DST -= RHS + C where C is zero or one.  Returns the carry flag.  */
2331APInt::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", "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 2333, __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;
2347}

2349/// This function subtracts a single "word" (64-bit word), src, from
2350/// the multi-word integer array, dst[], propagating the borrowed 1 value until
2351/// no further borrowing is needed or it runs out of "words" in dst.  The result
2352/// is 1 if "borrowing" exhausted the digits in dst, or 0 if dst was not
2353/// exhausted. In other words, if src > dst then this function returns 1,
2354/// otherwise 0.
2355/// @returns the borrow out of the subtraction
2356APInt::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;
2367}

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

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

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

  If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
  returned.  Otherwise DST is filled with the least significant
  DSTPARTS parts of the result, and if all of the omitted higher
  parts were zero return zero, otherwise overflow occurred and
  return one.  */
2386int 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"
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 2391, __extension__ __PRETTY_FUNCTION__));
assert(dstParts <= srcParts + 1)(static_cast <bool> (dstParts <= srcParts + 1) ? void
 (0) : __assert_fail ("dstParts <= srcParts + 1", "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 2392, __extension__ __PRETTY_FUNCTION__));

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

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

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

       This cannot overflow, because

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

       which is less than n^2.  */

  srcPart = src[i];

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

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

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

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

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

  carry = high;
}

if (srcParts < dstParts) {
  /* Full multiplication, there is no overflow.  */
  assert(srcParts + 1 == dstParts)(static_cast <bool> (srcParts + 1 == dstParts) ? void (
0) : __assert_fail ("srcParts + 1 == dstParts", "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 2450, __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;
2469}

2471/* 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.  */
2475int 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"
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 2477, __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;
2487}

2489/// DST = LHS * RHS, where DST has width the sum of the widths of the
2490/// operands. No overflow occurs. DST must be disjoint from both operands.
2491void 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"
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 2498, __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);
2504}

2506/* 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.
2515*/
2516int 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"
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 2519, __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;
2554}

2556/// Shift a bignum left Cound bits in-place. Shifted in bits are zero. There are
2557/// no restrictions on Count.
2558void 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);
2581}

2583/// Shift a bignum right Count bits in-place. Shifted in bits are zero. There
2584/// are no restrictions on Count.
2585void 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);
2608}

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

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

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

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

2634/* Comparison (unsigned) of two bignums.  */
2635int 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;
2644}

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

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

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

2663APInt llvm::APIntOps::RoundingUDiv(const APInt &A, const APInt &B,
                                 APInt::Rounding RM) {
// Currently udivrem always rounds down.
switch (RM) {
case APInt::Rounding::DOWN:
case APInt::Rounding::TOWARD_ZERO:
  return A.udiv(B);
case APInt::Rounding::UP: {
  APInt Quo, Rem;
  APInt::udivrem(A, B, Quo, Rem);
  if (Rem == 0)
    return Quo;
  return Quo + 1;
}
}
llvm_unreachable("Unknown APInt::Rounding enum")::llvm::llvm_unreachable_internal("Unknown APInt::Rounding enum"
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 2678);
2679}

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