LCOV - code coverage report
Current view: top level - lib/Support - APInt.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 1145 1243 92.1 %
Date: 2017-09-14 15:23:50 Functions: 122 124 98.4 %
Legend: Lines: hit not hit

          Line data    Source code
       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             : //===----------------------------------------------------------------------===//
      14             : 
      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/Support/Debug.h"
      22             : #include "llvm/Support/ErrorHandling.h"
      23             : #include "llvm/Support/MathExtras.h"
      24             : #include "llvm/Support/raw_ostream.h"
      25             : #include <climits>
      26             : #include <cmath>
      27             : #include <cstdlib>
      28             : #include <cstring>
      29             : using namespace llvm;
      30             : 
      31             : #define DEBUG_TYPE "apint"
      32             : 
      33             : /// A utility function for allocating memory, checking for allocation failures,
      34             : /// and ensuring the contents are zeroed.
      35     2219553 : inline static uint64_t* getClearedMemory(unsigned numWords) {
      36     2219553 :   uint64_t * result = new uint64_t[numWords];
      37             :   assert(result && "APInt memory allocation fails!");
      38     2219553 :   memset(result, 0, numWords * sizeof(uint64_t));
      39     2219553 :   return result;
      40             : }
      41             : 
      42             : /// A utility function for allocating memory and checking for allocation
      43             : /// failure.  The content is not zeroed.
      44             : inline static uint64_t* getMemory(unsigned numWords) {
      45     4262548 :   uint64_t * result = new uint64_t[numWords];
      46             :   assert(result && "APInt memory allocation fails!");
      47             :   return result;
      48             : }
      49             : 
      50             : /// A utility function that converts a character to a digit.
      51     3228701 : inline static unsigned getDigit(char cdigit, uint8_t radix) {
      52             :   unsigned r;
      53             : 
      54     3228701 :   if (radix == 16 || radix == 36) {
      55        4859 :     r = cdigit - '0';
      56        4859 :     if (r <= 9)
      57             :       return r;
      58             : 
      59         992 :     r = cdigit - 'A';
      60         992 :     if (r <= radix - 11U)
      61         474 :       return r + 10;
      62             : 
      63         518 :     r = cdigit - 'a';
      64         518 :     if (r <= radix - 11U)
      65         518 :       return r + 10;
      66             : 
      67             :     radix = 10;
      68             :   }
      69             : 
      70     3223842 :   r = cdigit - '0';
      71     3223842 :   if (r < radix)
      72             :     return r;
      73             : 
      74           0 :   return -1U;
      75             : }
      76             : 
      77             : 
      78     2214528 : void APInt::initSlowCase(uint64_t val, bool isSigned) {
      79     4429056 :   U.pVal = getClearedMemory(getNumWords());
      80     2214528 :   U.pVal[0] = val;
      81     2214528 :   if (isSigned && int64_t(val) < 0)
      82      618929 :     for (unsigned i = 1; i < getNumWords(); ++i)
      83      127707 :       U.pVal[i] = WORD_MAX;
      84     2214528 :   clearUnusedBits();
      85     2214528 : }
      86             : 
      87     2891834 : void APInt::initSlowCase(const APInt& that) {
      88     8675502 :   U.pVal = getMemory(getNumWords());
      89     5783668 :   memcpy(U.pVal, that.U.pVal, getNumWords() * APINT_WORD_SIZE);
      90     2891834 : }
      91             : 
      92       53327 : void APInt::initFromArray(ArrayRef<uint64_t> bigVal) {
      93             :   assert(BitWidth && "Bitwidth too small");
      94             :   assert(bigVal.data() && "Null pointer detected!");
      95       53327 :   if (isSingleWord())
      96       49391 :     U.VAL = bigVal[0];
      97             :   else {
      98             :     // Get memory, cleared to 0
      99        7872 :     U.pVal = getClearedMemory(getNumWords());
     100             :     // Calculate the number of words to copy
     101       11808 :     unsigned words = std::min<unsigned>(bigVal.size(), getNumWords());
     102             :     // Copy the words from bigVal to pVal
     103        3936 :     memcpy(U.pVal, bigVal.data(), words * APINT_WORD_SIZE);
     104             :   }
     105             :   // Make sure unused high bits are cleared
     106       53327 :   clearUnusedBits();
     107       53327 : }
     108             : 
     109       22406 : APInt::APInt(unsigned numBits, ArrayRef<uint64_t> bigVal)
     110       22406 :   : BitWidth(numBits) {
     111       22406 :   initFromArray(bigVal);
     112       22406 : }
     113             : 
     114       30921 : APInt::APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[])
     115       30921 :   : BitWidth(numBits) {
     116       61842 :   initFromArray(makeArrayRef(bigVal, numWords));
     117       30921 : }
     118             : 
     119     2394063 : APInt::APInt(unsigned numbits, StringRef Str, uint8_t radix)
     120     2394063 :   : BitWidth(numbits) {
     121             :   assert(BitWidth && "Bitwidth too small");
     122     2394063 :   fromString(numbits, Str, radix);
     123     2394063 : }
     124             : 
     125      126017 : void APInt::reallocate(unsigned NewBitWidth) {
     126             :   // If the number of words is the same we can just change the width and stop.
     127      378051 :   if (getNumWords() == getNumWords(NewBitWidth)) {
     128       88489 :     BitWidth = NewBitWidth;
     129       88489 :     return;
     130             :   }
     131             : 
     132             :   // If we have an allocation, delete it.
     133       37528 :   if (!isSingleWord())
     134        5697 :     delete [] U.pVal;
     135             : 
     136             :   // Update BitWidth.
     137       37528 :   BitWidth = NewBitWidth;
     138             : 
     139             :   // If we are supposed to have an allocation, create it.
     140       37528 :   if (!isSingleWord())
     141       95493 :     U.pVal = getMemory(getNumWords());
     142             : }
     143             : 
     144       43546 : void APInt::AssignSlowCase(const APInt& RHS) {
     145             :   // Don't do anything for X = X
     146       43546 :   if (this == &RHS)
     147             :     return;
     148             : 
     149             :   // Adjust the bit width and handle allocations as necessary.
     150       43418 :   reallocate(RHS.getBitWidth());
     151             : 
     152             :   // Copy the data.
     153       43418 :   if (isSingleWord())
     154        5697 :     U.VAL = RHS.U.VAL;
     155             :   else
     156       75442 :     memcpy(U.pVal, RHS.U.pVal, getNumWords() * APINT_WORD_SIZE);
     157             : }
     158             : 
     159             : /// This method 'profiles' an APInt for use with FoldingSet.
     160     2550387 : void APInt::Profile(FoldingSetNodeID& ID) const {
     161     2550387 :   ID.AddInteger(BitWidth);
     162             : 
     163     2550387 :   if (isSingleWord()) {
     164     2550383 :     ID.AddInteger(U.VAL);
     165     2550383 :     return;
     166             :   }
     167             : 
     168           8 :   unsigned NumWords = getNumWords();
     169          12 :   for (unsigned i = 0; i < NumWords; ++i)
     170           8 :     ID.AddInteger(U.pVal[i]);
     171             : }
     172             : 
     173             : /// @brief Prefix increment operator. Increments the APInt by one.
     174     1234388 : APInt& APInt::operator++() {
     175     1234388 :   if (isSingleWord())
     176     1190665 :     ++U.VAL;
     177             :   else
     178       87446 :     tcIncrement(U.pVal, getNumWords());
     179     1234388 :   return clearUnusedBits();
     180             : }
     181             : 
     182             : /// @brief Prefix decrement operator. Decrements the APInt by one.
     183       62833 : APInt& APInt::operator--() {
     184       62833 :   if (isSingleWord())
     185       62831 :     --U.VAL;
     186             :   else
     187           4 :     tcDecrement(U.pVal, getNumWords());
     188       62833 :   return clearUnusedBits();
     189             : }
     190             : 
     191             : /// Adds the RHS APint to this APInt.
     192             : /// @returns this, after addition of RHS.
     193             : /// @brief Addition assignment operator.
     194    15650175 : APInt& APInt::operator+=(const APInt& RHS) {
     195             :   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
     196    15650175 :   if (isSingleWord())
     197    15108756 :     U.VAL += RHS.U.VAL;
     198             :   else
     199     1082838 :     tcAdd(U.pVal, RHS.U.pVal, 0, getNumWords());
     200    15650175 :   return clearUnusedBits();
     201             : }
     202             : 
     203    15044202 : APInt& APInt::operator+=(uint64_t RHS) {
     204    15044202 :   if (isSingleWord())
     205    14773121 :     U.VAL += RHS;
     206             :   else
     207      542162 :     tcAddPart(U.pVal, RHS, getNumWords());
     208    15044202 :   return clearUnusedBits();
     209             : }
     210             : 
     211             : /// Subtracts the RHS APInt from this APInt
     212             : /// @returns this, after subtraction
     213             : /// @brief Subtraction assignment operator.
     214    26759779 : APInt& APInt::operator-=(const APInt& RHS) {
     215             :   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
     216    26759779 :   if (isSingleWord())
     217    26677191 :     U.VAL -= RHS.U.VAL;
     218             :   else
     219      165176 :     tcSubtract(U.pVal, RHS.U.pVal, 0, getNumWords());
     220    26759779 :   return clearUnusedBits();
     221             : }
     222             : 
     223     3174150 : APInt& APInt::operator-=(uint64_t RHS) {
     224     3174150 :   if (isSingleWord())
     225     3068687 :     U.VAL -= RHS;
     226             :   else
     227      210926 :     tcSubtractPart(U.pVal, RHS, getNumWords());
     228     3174150 :   return clearUnusedBits();
     229             : }
     230             : 
     231    26508818 : APInt APInt::operator*(const APInt& RHS) const {
     232             :   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
     233    26508818 :   if (isSingleWord())
     234    25690397 :     return APInt(BitWidth, U.VAL * RHS.U.VAL);
     235             : 
     236     3273684 :   APInt Result(getMemory(getNumWords()), getBitWidth());
     237             : 
     238     1636842 :   tcMultiply(Result.U.pVal, U.pVal, RHS.U.pVal, getNumWords());
     239             : 
     240      818421 :   Result.clearUnusedBits();
     241      818421 :   return Result;
     242             : }
     243             : 
     244       52722 : void APInt::AndAssignSlowCase(const APInt& RHS) {
     245      105444 :   tcAnd(U.pVal, RHS.U.pVal, getNumWords());
     246       52722 : }
     247             : 
     248       67152 : void APInt::OrAssignSlowCase(const APInt& RHS) {
     249      134304 :   tcOr(U.pVal, RHS.U.pVal, getNumWords());
     250       67152 : }
     251             : 
     252         786 : void APInt::XorAssignSlowCase(const APInt& RHS) {
     253        1572 :   tcXor(U.pVal, RHS.U.pVal, getNumWords());
     254         786 : }
     255             : 
     256      584281 : APInt& APInt::operator*=(const APInt& RHS) {
     257             :   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
     258     1752843 :   *this = *this * RHS;
     259      584281 :   return *this;
     260             : }
     261             : 
     262     1463800 : APInt& APInt::operator*=(uint64_t RHS) {
     263     1463800 :   if (isSingleWord()) {
     264     1441461 :     U.VAL *= RHS;
     265             :   } else {
     266       44678 :     unsigned NumWords = getNumWords();
     267       22339 :     tcMultiplyPart(U.pVal, U.pVal, RHS, 0, NumWords, NumWords, false);
     268             :   }
     269     1463800 :   return clearUnusedBits();
     270             : }
     271             : 
     272     1696871 : bool APInt::EqualSlowCase(const APInt& RHS) const {
     273     5090613 :   return std::equal(U.pVal, U.pVal + getNumWords(), RHS.U.pVal);
     274             : }
     275             : 
     276    19238450 : int APInt::compare(const APInt& RHS) const {
     277             :   assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
     278    19238450 :   if (isSingleWord())
     279    18695661 :     return U.VAL < RHS.U.VAL ? -1 : U.VAL > RHS.U.VAL;
     280             : 
     281     1085578 :   return tcCompare(U.pVal, RHS.U.pVal, getNumWords());
     282             : }
     283             : 
     284     5139860 : int APInt::compareSigned(const APInt& RHS) const {
     285             :   assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
     286     5139860 :   if (isSingleWord()) {
     287     9618858 :     int64_t lhsSext = SignExtend64(U.VAL, BitWidth);
     288     9618858 :     int64_t rhsSext = SignExtend64(RHS.U.VAL, BitWidth);
     289     4809429 :     return lhsSext < rhsSext ? -1 : lhsSext > rhsSext;
     290             :   }
     291             : 
     292      660862 :   bool lhsNeg = isNegative();
     293      660862 :   bool rhsNeg = RHS.isNegative();
     294             : 
     295             :   // If the sign bits don't match, then (LHS < RHS) if LHS is negative
     296      330431 :   if (lhsNeg != rhsNeg)
     297      143311 :     return lhsNeg ? -1 : 1;
     298             : 
     299             :   // Otherwise we can just use an unsigned comparison, because even negative
     300             :   // numbers compare correctly this way if both have the same signed-ness.
     301      374240 :   return tcCompare(U.pVal, RHS.U.pVal, getNumWords());
     302             : }
     303             : 
     304       44107 : void APInt::setBitsSlowCase(unsigned loBit, unsigned hiBit) {
     305       44107 :   unsigned loWord = whichWord(loBit);
     306       44107 :   unsigned hiWord = whichWord(hiBit);
     307             : 
     308             :   // Create an initial mask for the low word with zeros below loBit.
     309       44107 :   uint64_t loMask = WORD_MAX << whichBit(loBit);
     310             : 
     311             :   // If hiBit is not aligned, we need a high mask.
     312       44107 :   unsigned hiShiftAmt = whichBit(hiBit);
     313       44107 :   if (hiShiftAmt != 0) {
     314             :     // Create a high mask with zeros above hiBit.
     315        7974 :     uint64_t hiMask = WORD_MAX >> (APINT_BITS_PER_WORD - hiShiftAmt);
     316             :     // If loWord and hiWord are equal, then we combine the masks. Otherwise,
     317             :     // set the bits in hiWord.
     318        7974 :     if (hiWord == loWord)
     319        6433 :       loMask &= hiMask;
     320             :     else
     321        1541 :       U.pVal[hiWord] |= hiMask;
     322             :   }
     323             :   // Apply the mask to the low word.
     324       44107 :   U.pVal[loWord] |= loMask;
     325             : 
     326             :   // Fill any words between loWord and hiWord with all ones.
     327       64595 :   for (unsigned word = loWord + 1; word < hiWord; ++word)
     328       20488 :     U.pVal[word] = WORD_MAX;
     329       44107 : }
     330             : 
     331             : /// @brief Toggle every bit to its opposite value.
     332       66438 : void APInt::flipAllBitsSlowCase() {
     333      132876 :   tcComplement(U.pVal, getNumWords());
     334       66438 :   clearUnusedBits();
     335       66438 : }
     336             : 
     337             : /// Toggle a given bit to its opposite value whose position is given
     338             : /// as "bitPosition".
     339             : /// @brief Toggles a given bit to its opposite value.
     340           0 : void APInt::flipBit(unsigned bitPosition) {
     341             :   assert(bitPosition < BitWidth && "Out of the bit-width range!");
     342           0 :   if ((*this)[bitPosition]) clearBit(bitPosition);
     343             :   else setBit(bitPosition);
     344           0 : }
     345             : 
     346      813542 : void APInt::insertBits(const APInt &subBits, unsigned bitPosition) {
     347      813542 :   unsigned subBitWidth = subBits.getBitWidth();
     348             :   assert(0 < subBitWidth && (subBitWidth + bitPosition) <= BitWidth &&
     349             :          "Illegal bit insertion");
     350             : 
     351             :   // Insertion is a direct copy.
     352      813542 :   if (subBitWidth == BitWidth) {
     353         109 :     *this = subBits;
     354         109 :     return;
     355             :   }
     356             : 
     357             :   // Single word result can be done as a direct bitmask.
     358      813433 :   if (isSingleWord()) {
     359        3889 :     uint64_t mask = WORD_MAX >> (APINT_BITS_PER_WORD - subBitWidth);
     360        3889 :     U.VAL &= ~(mask << bitPosition);
     361        3889 :     U.VAL |= (subBits.U.VAL << bitPosition);
     362        3889 :     return;
     363             :   }
     364             : 
     365      809544 :   unsigned loBit = whichBit(bitPosition);
     366      809544 :   unsigned loWord = whichWord(bitPosition);
     367     1619088 :   unsigned hi1Word = whichWord(bitPosition + subBitWidth - 1);
     368             : 
     369             :   // Insertion within a single word can be done as a direct bitmask.
     370      809544 :   if (loWord == hi1Word) {
     371      809538 :     uint64_t mask = WORD_MAX >> (APINT_BITS_PER_WORD - subBitWidth);
     372      809538 :     U.pVal[loWord] &= ~(mask << loBit);
     373      809538 :     U.pVal[loWord] |= (subBits.U.VAL << loBit);
     374      809538 :     return;
     375             :   }
     376             : 
     377             :   // Insert on word boundaries.
     378           6 :   if (loBit == 0) {
     379             :     // Direct copy whole words.
     380           4 :     unsigned numWholeSubWords = subBitWidth / APINT_BITS_PER_WORD;
     381           8 :     memcpy(U.pVal + loWord, subBits.getRawData(),
     382           4 :            numWholeSubWords * APINT_WORD_SIZE);
     383             : 
     384             :     // Mask+insert remaining bits.
     385           4 :     unsigned remainingBits = subBitWidth % APINT_BITS_PER_WORD;
     386           4 :     if (remainingBits != 0) {
     387           3 :       uint64_t mask = WORD_MAX >> (APINT_BITS_PER_WORD - remainingBits);
     388           3 :       U.pVal[hi1Word] &= ~mask;
     389           6 :       U.pVal[hi1Word] |= subBits.getWord(subBitWidth - 1);
     390             :     }
     391             :     return;
     392             :   }
     393             : 
     394             :   // General case - set/clear individual bits in dst based on src.
     395             :   // TODO - there is scope for optimization here, but at the moment this code
     396             :   // path is barely used so prefer readability over performance.
     397         322 :   for (unsigned i = 0; i != subBitWidth; ++i) {
     398         160 :     if (subBits[i])
     399          10 :       setBit(bitPosition + i);
     400             :     else
     401         150 :       clearBit(bitPosition + i);
     402             :   }
     403             : }
     404             : 
     405      288957 : APInt APInt::extractBits(unsigned numBits, unsigned bitPosition) const {
     406             :   assert(numBits > 0 && "Can't extract zero bits");
     407             :   assert(bitPosition < BitWidth && (numBits + bitPosition) <= BitWidth &&
     408             :          "Illegal bit extraction");
     409             : 
     410      288957 :   if (isSingleWord())
     411           1 :     return APInt(numBits, U.VAL >> bitPosition);
     412             : 
     413      288956 :   unsigned loBit = whichBit(bitPosition);
     414      288956 :   unsigned loWord = whichWord(bitPosition);
     415      577912 :   unsigned hiWord = whichWord(bitPosition + numBits - 1);
     416             : 
     417             :   // Single word result extracting bits from a single word source.
     418      288956 :   if (loWord == hiWord)
     419      288951 :     return APInt(numBits, U.pVal[loWord] >> loBit);
     420             : 
     421             :   // Extracting bits that start on a source word boundary can be done
     422             :   // as a fast memory copy.
     423           5 :   if (loBit == 0)
     424           4 :     return APInt(numBits, makeArrayRef(U.pVal + loWord, 1 + hiWord - loWord));
     425             : 
     426             :   // General case - shift + copy source words directly into place.
     427           3 :   APInt Result(numBits, 0);
     428           6 :   unsigned NumSrcWords = getNumWords();
     429           6 :   unsigned NumDstWords = Result.getNumWords();
     430             : 
     431          10 :   for (unsigned word = 0; word < NumDstWords; ++word) {
     432           7 :     uint64_t w0 = U.pVal[loWord + word];
     433           7 :     uint64_t w1 =
     434           7 :         (loWord + word + 1) < NumSrcWords ? U.pVal[loWord + word + 1] : 0;
     435           7 :     Result.U.pVal[word] = (w0 >> loBit) | (w1 << (APINT_BITS_PER_WORD - loBit));
     436             :   }
     437             : 
     438           6 :   return Result.clearUnusedBits();
     439             : }
     440             : 
     441          61 : unsigned APInt::getBitsNeeded(StringRef str, uint8_t radix) {
     442             :   assert(!str.empty() && "Invalid string length");
     443             :   assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
     444             :           radix == 36) &&
     445             :          "Radix should be 2, 8, 10, 16, or 36!");
     446             : 
     447          61 :   size_t slen = str.size();
     448             : 
     449             :   // Each computation below needs to know if it's negative.
     450          61 :   StringRef::iterator p = str.begin();
     451          61 :   unsigned isNegative = *p == '-';
     452          61 :   if (*p == '-' || *p == '+') {
     453          40 :     p++;
     454          40 :     slen--;
     455             :     assert(slen && "String is only a sign, needs a value.");
     456             :   }
     457             : 
     458             :   // For radixes of power-of-two values, the bits required is accurately and
     459             :   // easily computed
     460          61 :   if (radix == 2)
     461          15 :     return slen + isNegative;
     462          46 :   if (radix == 8)
     463          15 :     return slen * 3 + isNegative;
     464          31 :   if (radix == 16)
     465          15 :     return slen * 4 + isNegative;
     466             : 
     467             :   // FIXME: base 36
     468             : 
     469             :   // This is grossly inefficient but accurate. We could probably do something
     470             :   // with a computation of roughly slen*64/20 and then adjust by the value of
     471             :   // the first few digits. But, I'm not sure how accurate that could be.
     472             : 
     473             :   // Compute a sufficient number of bits that is always large enough but might
     474             :   // be too large. This avoids the assertion in the constructor. This
     475             :   // calculation doesn't work appropriately for the numbers 0-9, so just use 4
     476             :   // bits in that case.
     477          25 :   unsigned sufficient
     478           9 :     = radix == 10? (slen == 1 ? 4 : slen * 64/18)
     479           0 :                  : (slen == 1 ? 7 : slen * 16/3);
     480             : 
     481             :   // Convert to the actual binary value.
     482          32 :   APInt tmp(sufficient, StringRef(p, slen), radix);
     483             : 
     484             :   // Compute how many bits are required. If the log is infinite, assume we need
     485             :   // just bit.
     486          16 :   unsigned log = tmp.logBase2();
     487          16 :   if (log == (unsigned)-1) {
     488           3 :     return isNegative + 1;
     489             :   } else {
     490          13 :     return isNegative + log + 1;
     491             :   }
     492             : }
     493             : 
     494    42090317 : hash_code llvm::hash_value(const APInt &Arg) {
     495    42090317 :   if (Arg.isSingleWord())
     496    41943410 :     return hash_combine(Arg.U.VAL);
     497             : 
     498      293814 :   return hash_combine_range(Arg.U.pVal, Arg.U.pVal + Arg.getNumWords());
     499             : }
     500             : 
     501       24469 : bool APInt::isSplat(unsigned SplatSizeInBits) const {
     502             :   assert(getBitWidth() % SplatSizeInBits == 0 &&
     503             :          "SplatSizeInBits must divide width!");
     504             :   // We can check that all parts of an integer are equal by making use of a
     505             :   // little trick: rotate and check if it's still the same value.
     506       73407 :   return *this == rotl(SplatSizeInBits);
     507             : }
     508             : 
     509             : /// This function returns the high "numBits" bits of this APInt.
     510        9374 : APInt APInt::getHiBits(unsigned numBits) const {
     511        9374 :   return this->lshr(BitWidth - numBits);
     512             : }
     513             : 
     514             : /// This function returns the low "numBits" bits of this APInt.
     515       23257 : APInt APInt::getLoBits(unsigned numBits) const {
     516       23257 :   APInt Result(getLowBitsSet(BitWidth, numBits));
     517       23257 :   Result &= *this;
     518       23257 :   return Result;
     519             : }
     520             : 
     521             : /// Return a value containing V broadcasted over NewLen bits.
     522       22514 : APInt APInt::getSplat(unsigned NewLen, const APInt &V) {
     523             :   assert(NewLen >= V.getBitWidth() && "Can't splat to smaller bit width!");
     524             : 
     525       22514 :   APInt Val = V.zextOrSelf(NewLen);
     526       31257 :   for (unsigned I = V.getBitWidth(); I < NewLen; I <<= 1)
     527       26229 :     Val |= Val << I;
     528             : 
     529       22514 :   return Val;
     530             : }
     531             : 
     532     2652076 : unsigned APInt::countLeadingZerosSlowCase() const {
     533     2652076 :   unsigned Count = 0;
     534   152874494 :   for (int i = getNumWords()-1; i >= 0; --i) {
     535   149797802 :     uint64_t V = U.pVal[i];
     536   149797802 :     if (V == 0)
     537   147570342 :       Count += APINT_BITS_PER_WORD;
     538             :     else {
     539     2227460 :       Count += llvm::countLeadingZeros(V);
     540     2227460 :       break;
     541             :     }
     542             :   }
     543             :   // Adjust for unused bits in the most significant word (they are zero).
     544     2652076 :   unsigned Mod = BitWidth % APINT_BITS_PER_WORD;
     545     2652076 :   Count -= Mod > 0 ? APINT_BITS_PER_WORD - Mod : 0;
     546     2652076 :   return Count;
     547             : }
     548             : 
     549        4411 : unsigned APInt::countLeadingOnesSlowCase() const {
     550        4411 :   unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD;
     551             :   unsigned shift;
     552        4411 :   if (!highWordBits) {
     553             :     highWordBits = APINT_BITS_PER_WORD;
     554             :     shift = 0;
     555             :   } else {
     556         525 :     shift = APINT_BITS_PER_WORD - highWordBits;
     557             :   }
     558        8822 :   int i = getNumWords() - 1;
     559        8822 :   unsigned Count = llvm::countLeadingOnes(U.pVal[i] << shift);
     560        4411 :   if (Count == highWordBits) {
     561        2877 :     for (i--; i >= 0; --i) {
     562        2772 :       if (U.pVal[i] == WORD_MAX)
     563         475 :         Count += APINT_BITS_PER_WORD;
     564             :       else {
     565        4594 :         Count += llvm::countLeadingOnes(U.pVal[i]);
     566        2297 :         break;
     567             :       }
     568             :     }
     569             :   }
     570        4411 :   return Count;
     571             : }
     572             : 
     573        4735 : unsigned APInt::countTrailingZerosSlowCase() const {
     574        4735 :   unsigned Count = 0;
     575        4735 :   unsigned i = 0;
     576       17732 :   for (; i < getNumWords() && U.pVal[i] == 0; ++i)
     577        2754 :     Count += APINT_BITS_PER_WORD;
     578        9470 :   if (i < getNumWords())
     579        8136 :     Count += llvm::countTrailingZeros(U.pVal[i]);
     580        9470 :   return std::min(Count, BitWidth);
     581             : }
     582             : 
     583      195888 : unsigned APInt::countTrailingOnesSlowCase() const {
     584      195888 :   unsigned Count = 0;
     585      195888 :   unsigned i = 0;
     586      984882 :   for (; i < getNumWords() && U.pVal[i] == WORD_MAX; ++i)
     587      197702 :     Count += APINT_BITS_PER_WORD;
     588      391776 :   if (i < getNumWords())
     589      207438 :     Count += llvm::countTrailingOnes(U.pVal[i]);
     590             :   assert(Count <= BitWidth);
     591      195888 :   return Count;
     592             : }
     593             : 
     594        5778 : unsigned APInt::countPopulationSlowCase() const {
     595        5778 :   unsigned Count = 0;
     596       49438 :   for (unsigned i = 0; i < getNumWords(); ++i)
     597       37882 :     Count += llvm::countPopulation(U.pVal[i]);
     598        5778 :   return Count;
     599             : }
     600             : 
     601        6750 : bool APInt::intersectsSlowCase(const APInt &RHS) const {
     602       36722 :   for (unsigned i = 0, e = getNumWords(); i != e; ++i)
     603       23917 :     if ((U.pVal[i] & RHS.U.pVal[i]) != 0)
     604             :       return true;
     605             : 
     606             :   return false;
     607             : }
     608             : 
     609       14735 : bool APInt::isSubsetOfSlowCase(const APInt &RHS) const {
     610       39113 :   for (unsigned i = 0, e = getNumWords(); i != e; ++i)
     611       22791 :     if ((U.pVal[i] & ~RHS.U.pVal[i]) != 0)
     612             :       return false;
     613             : 
     614             :   return true;
     615             : }
     616             : 
     617        9322 : APInt APInt::byteSwap() const {
     618             :   assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
     619        9322 :   if (BitWidth == 16)
     620        1520 :     return APInt(BitWidth, ByteSwap_16(uint16_t(U.VAL)));
     621        8562 :   if (BitWidth == 32)
     622       12780 :     return APInt(BitWidth, ByteSwap_32(unsigned(U.VAL)));
     623        2172 :   if (BitWidth == 48) {
     624           0 :     unsigned Tmp1 = unsigned(U.VAL >> 16);
     625           0 :     Tmp1 = ByteSwap_32(Tmp1);
     626           0 :     uint16_t Tmp2 = uint16_t(U.VAL);
     627           0 :     Tmp2 = ByteSwap_16(Tmp2);
     628           0 :     return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
     629             :   }
     630        2172 :   if (BitWidth == 64)
     631        4342 :     return APInt(BitWidth, ByteSwap_64(U.VAL));
     632             : 
     633           3 :   APInt Result(getNumWords() * APINT_BITS_PER_WORD, 0);
     634           4 :   for (unsigned I = 0, N = getNumWords(); I != N; ++I)
     635           4 :     Result.U.pVal[I] = ByteSwap_64(U.pVal[N - I - 1]);
     636           1 :   if (Result.BitWidth != BitWidth) {
     637           2 :     Result.lshrInPlace(Result.BitWidth - BitWidth);
     638           1 :     Result.BitWidth = BitWidth;
     639             :   }
     640           1 :   return Result;
     641             : }
     642             : 
     643        5253 : APInt APInt::reverseBits() const {
     644        5253 :   switch (BitWidth) {
     645         306 :   case 64:
     646         612 :     return APInt(BitWidth, llvm::reverseBits<uint64_t>(U.VAL));
     647        1040 :   case 32:
     648        2080 :     return APInt(BitWidth, llvm::reverseBits<uint32_t>(U.VAL));
     649         190 :   case 16:
     650         380 :     return APInt(BitWidth, llvm::reverseBits<uint16_t>(U.VAL));
     651         188 :   case 8:
     652         376 :     return APInt(BitWidth, llvm::reverseBits<uint8_t>(U.VAL));
     653             :   default:
     654             :     break;
     655             :   }
     656             : 
     657        7058 :   APInt Val(*this);
     658       10587 :   APInt Reversed(BitWidth, 0);
     659        3529 :   unsigned S = BitWidth;
     660             : 
     661     1163339 :   for (; Val != 0; Val.lshrInPlace(1)) {
     662     1159810 :     Reversed <<= 1;
     663     2319620 :     Reversed |= Val[0];
     664     1159810 :     --S;
     665             :   }
     666             : 
     667        3529 :   Reversed <<= S;
     668        3529 :   return Reversed;
     669             : }
     670             : 
     671        2601 : APInt llvm::APIntOps::GreatestCommonDivisor(APInt A, APInt B) {
     672             :   // Fast-path a common case.
     673        2601 :   if (A == B) return A;
     674             : 
     675             :   // Corner cases: if either operand is zero, the other is the gcd.
     676        1727 :   if (!A) return B;
     677         726 :   if (!B) return A;
     678             : 
     679             :   // Count common powers of 2 and remove all other powers of 2.
     680             :   unsigned Pow2;
     681             :   {
     682         532 :     unsigned Pow2_A = A.countTrailingZeros();
     683         532 :     unsigned Pow2_B = B.countTrailingZeros();
     684         532 :     if (Pow2_A > Pow2_B) {
     685          86 :       A.lshrInPlace(Pow2_A - Pow2_B);
     686             :       Pow2 = Pow2_B;
     687         446 :     } else if (Pow2_B > Pow2_A) {
     688         364 :       B.lshrInPlace(Pow2_B - Pow2_A);
     689             :       Pow2 = Pow2_A;
     690             :     } else {
     691             :       Pow2 = Pow2_A;
     692             :     }
     693             :   }
     694             : 
     695             :   // Both operands are odd multiples of 2^Pow_2:
     696             :   //
     697             :   //   gcd(a, b) = gcd(|a - b| / 2^i, min(a, b))
     698             :   //
     699             :   // This is a modified version of Stein's algorithm, taking advantage of
     700             :   // efficient countTrailingZeros().
     701        1924 :   while (A != B) {
     702        1392 :     if (A.ugt(B)) {
     703         336 :       A -= B;
     704         336 :       A.lshrInPlace(A.countTrailingZeros() - Pow2);
     705             :     } else {
     706        1056 :       B -= A;
     707        1056 :       B.lshrInPlace(B.countTrailingZeros() - Pow2);
     708             :     }
     709             :   }
     710             : 
     711             :   return A;
     712             : }
     713             : 
     714          40 : APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) {
     715             :   union {
     716             :     double D;
     717             :     uint64_t I;
     718             :   } T;
     719          40 :   T.D = Double;
     720             : 
     721             :   // Get the sign bit from the highest order bit
     722          40 :   bool isNeg = T.I >> 63;
     723             : 
     724             :   // Get the 11-bit exponent and adjust for the 1023 bit bias
     725          40 :   int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
     726             : 
     727             :   // If the exponent is negative, the value is < 0 so just return 0.
     728          40 :   if (exp < 0)
     729             :     return APInt(width, 0u);
     730             : 
     731             :   // Extract the mantissa by clearing the top 12 bits (sign + exponent).
     732          24 :   uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
     733             : 
     734             :   // If the exponent doesn't shift all bits out of the mantissa
     735          24 :   if (exp < 52)
     736          40 :     return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
     737          48 :                     APInt(width, mantissa >> (52 - exp));
     738             : 
     739             :   // If the client didn't provide enough bits for us to shift the mantissa into
     740             :   // then the result is undefined, just return 0
     741           0 :   if (width <= exp - 52)
     742             :     return APInt(width, 0);
     743             : 
     744             :   // Otherwise, we have to shift the mantissa bits up to the right location
     745           0 :   APInt Tmp(width, mantissa);
     746           0 :   Tmp <<= (unsigned)exp - 52;
     747           0 :   return isNeg ? -Tmp : Tmp;
     748             : }
     749             : 
     750             : /// This function converts this APInt to a double.
     751             : /// The layout for double is as following (IEEE Standard 754):
     752             : ///  --------------------------------------
     753             : /// |  Sign    Exponent    Fraction    Bias |
     754             : /// |-------------------------------------- |
     755             : /// |  1[63]   11[62-52]   52[51-00]   1023 |
     756             : ///  --------------------------------------
     757          50 : double APInt::roundToDouble(bool isSigned) const {
     758             : 
     759             :   // Handle the simple case where the value is contained in one uint64_t.
     760             :   // It is wrong to optimize getWord(0) to VAL; there might be more than one word.
     761          50 :   if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
     762          50 :     if (isSigned) {
     763          75 :       int64_t sext = SignExtend64(getWord(0), BitWidth);
     764          25 :       return double(sext);
     765             :     } else
     766          25 :       return double(getWord(0));
     767             :   }
     768             : 
     769             :   // Determine if the value is negative.
     770           0 :   bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
     771             : 
     772             :   // Construct the absolute value if we're negative.
     773           0 :   APInt Tmp(isNeg ? -(*this) : (*this));
     774             : 
     775             :   // Figure out how many bits we're using.
     776           0 :   unsigned n = Tmp.getActiveBits();
     777             : 
     778             :   // The exponent (without bias normalization) is just the number of bits
     779             :   // we are using. Note that the sign bit is gone since we constructed the
     780             :   // absolute value.
     781           0 :   uint64_t exp = n;
     782             : 
     783             :   // Return infinity for exponent overflow
     784           0 :   if (exp > 1023) {
     785           0 :     if (!isSigned || !isNeg)
     786             :       return std::numeric_limits<double>::infinity();
     787             :     else
     788           0 :       return -std::numeric_limits<double>::infinity();
     789             :   }
     790           0 :   exp += 1023; // Increment for 1023 bias
     791             : 
     792             :   // Number of bits in mantissa is 52. To obtain the mantissa value, we must
     793             :   // extract the high 52 bits from the correct words in pVal.
     794             :   uint64_t mantissa;
     795           0 :   unsigned hiWord = whichWord(n-1);
     796           0 :   if (hiWord == 0) {
     797           0 :     mantissa = Tmp.U.pVal[0];
     798           0 :     if (n > 52)
     799           0 :       mantissa >>= n - 52; // shift down, we want the top 52 bits.
     800             :   } else {
     801             :     assert(hiWord > 0 && "huh?");
     802           0 :     uint64_t hibits = Tmp.U.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
     803           0 :     uint64_t lobits = Tmp.U.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
     804           0 :     mantissa = hibits | lobits;
     805             :   }
     806             : 
     807             :   // The leading bit of mantissa is implicit, so get rid of it.
     808           0 :   uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
     809             :   union {
     810             :     double D;
     811             :     uint64_t I;
     812             :   } T;
     813           0 :   T.I = sign | (exp << 52) | mantissa;
     814           0 :   return T.D;
     815             : }
     816             : 
     817             : // Truncate to new width.
     818    10138480 : APInt APInt::trunc(unsigned width) const {
     819             :   assert(width < BitWidth && "Invalid APInt Truncate request");
     820             :   assert(width && "Can't truncate to 0 bits");
     821             : 
     822    10138480 :   if (width <= APINT_BITS_PER_WORD)
     823    10104396 :     return APInt(width, getRawData()[0]);
     824             : 
     825      102252 :   APInt Result(getMemory(getNumWords(width)), width);
     826             : 
     827             :   // Copy full words.
     828             :   unsigned i;
     829      123754 :   for (i = 0; i != width / APINT_BITS_PER_WORD; i++)
     830       89670 :     Result.U.pVal[i] = U.pVal[i];
     831             : 
     832             :   // Truncate and copy any partial word.
     833       34084 :   unsigned bits = (0 - width) % APINT_BITS_PER_WORD;
     834       34084 :   if (bits != 0)
     835        1717 :     Result.U.pVal[i] = U.pVal[i] << bits >> bits;
     836             : 
     837       34084 :   return Result;
     838             : }
     839             : 
     840             : // Sign extend to a new width.
     841     3105018 : APInt APInt::sext(unsigned Width) const {
     842             :   assert(Width > BitWidth && "Invalid APInt SignExtend request");
     843             : 
     844     3105018 :   if (Width <= APINT_BITS_PER_WORD)
     845     5802208 :     return APInt(Width, SignExtend64(U.VAL, BitWidth));
     846             : 
     847      611742 :   APInt Result(getMemory(getNumWords(Width)), Width);
     848             : 
     849             :   // Copy words.
     850      611742 :   std::memcpy(Result.U.pVal, getRawData(), getNumWords() * APINT_WORD_SIZE);
     851             : 
     852             :   // Sign extend the last word since there may be unused bits in the input.
     853      407828 :   Result.U.pVal[getNumWords() - 1] =
     854      815656 :       SignExtend64(Result.U.pVal[getNumWords() - 1],
     855      203914 :                    ((BitWidth - 1) % APINT_BITS_PER_WORD) + 1);
     856             : 
     857             :   // Fill with sign bits.
     858      611742 :   std::memset(Result.U.pVal + getNumWords(), isNegative() ? -1 : 0,
     859      611742 :               (Result.getNumWords() - getNumWords()) * APINT_WORD_SIZE);
     860      203914 :   Result.clearUnusedBits();
     861      203914 :   return Result;
     862             : }
     863             : 
     864             : //  Zero extend to a new width.
     865     7257117 : APInt APInt::zext(unsigned width) const {
     866             :   assert(width > BitWidth && "Invalid APInt ZeroExtend request");
     867             : 
     868     7257117 :   if (width <= APINT_BITS_PER_WORD)
     869     6974653 :     return APInt(width, U.VAL);
     870             : 
     871      847392 :   APInt Result(getMemory(getNumWords(width)), width);
     872             : 
     873             :   // Copy words.
     874      847392 :   std::memcpy(Result.U.pVal, getRawData(), getNumWords() * APINT_WORD_SIZE);
     875             : 
     876             :   // Zero remaining words.
     877      564928 :   std::memset(Result.U.pVal + getNumWords(), 0,
     878      847392 :               (Result.getNumWords() - getNumWords()) * APINT_WORD_SIZE);
     879             : 
     880      282464 :   return Result;
     881             : }
     882             : 
     883     5603691 : APInt APInt::zextOrTrunc(unsigned width) const {
     884     5603691 :   if (BitWidth < width)
     885     1884726 :     return zext(width);
     886     3718965 :   if (BitWidth > width)
     887      731854 :     return trunc(width);
     888             :   return *this;
     889             : }
     890             : 
     891     6507240 : APInt APInt::sextOrTrunc(unsigned width) const {
     892     6507240 :   if (BitWidth < width)
     893      226259 :     return sext(width);
     894     6280981 :   if (BitWidth > width)
     895      242064 :     return trunc(width);
     896             :   return *this;
     897             : }
     898             : 
     899      121217 : APInt APInt::zextOrSelf(unsigned width) const {
     900      121217 :   if (BitWidth < width)
     901       50569 :     return zext(width);
     902             :   return *this;
     903             : }
     904             : 
     905        5324 : APInt APInt::sextOrSelf(unsigned width) const {
     906        5324 :   if (BitWidth < width)
     907        5276 :     return sext(width);
     908             :   return *this;
     909             : }
     910             : 
     911             : /// Arithmetic right-shift this APInt by shiftAmt.
     912             : /// @brief Arithmetic right-shift function.
     913       13040 : void APInt::ashrInPlace(const APInt &shiftAmt) {
     914       26080 :   ashrInPlace((unsigned)shiftAmt.getLimitedValue(BitWidth));
     915       13040 : }
     916             : 
     917             : /// Arithmetic right-shift this APInt by shiftAmt.
     918             : /// @brief Arithmetic right-shift function.
     919        1465 : void APInt::ashrSlowCase(unsigned ShiftAmt) {
     920             :   // Don't bother performing a no-op shift.
     921        1465 :   if (!ShiftAmt)
     922             :     return;
     923             : 
     924             :   // Save the original sign bit for later.
     925        2722 :   bool Negative = isNegative();
     926             : 
     927             :   // WordShift is the inter-part shift; BitShift is is intra-part shift.
     928        1361 :   unsigned WordShift = ShiftAmt / APINT_BITS_PER_WORD;
     929        1361 :   unsigned BitShift = ShiftAmt % APINT_BITS_PER_WORD;
     930             : 
     931        2722 :   unsigned WordsToMove = getNumWords() - WordShift;
     932        1361 :   if (WordsToMove != 0) {
     933             :     // Sign extend the last word to fill in the unused bits.
     934        5436 :     U.pVal[getNumWords() - 1] = SignExtend64(
     935        2718 :         U.pVal[getNumWords() - 1], ((BitWidth - 1) % APINT_BITS_PER_WORD) + 1);
     936             : 
     937             :     // Fastpath for moving by whole words.
     938        1359 :     if (BitShift == 0) {
     939         154 :       std::memmove(U.pVal, U.pVal + WordShift, WordsToMove * APINT_WORD_SIZE);
     940             :     } else {
     941             :       // Move the words containing significant bits.
     942        3545 :       for (unsigned i = 0; i != WordsToMove - 1; ++i)
     943        2340 :         U.pVal[i] = (U.pVal[i + WordShift] >> BitShift) |
     944        1170 :                     (U.pVal[i + WordShift + 1] << (APINT_BITS_PER_WORD - BitShift));
     945             : 
     946             :       // Handle the last word which has no high bits to copy.
     947        1205 :       U.pVal[WordsToMove - 1] = U.pVal[WordShift + WordsToMove - 1] >> BitShift;
     948             :       // Sign extend one more time.
     949        1205 :       U.pVal[WordsToMove - 1] =
     950        2410 :           SignExtend64(U.pVal[WordsToMove - 1], APINT_BITS_PER_WORD - BitShift);
     951             :     }
     952             :   }
     953             : 
     954             :   // Fill in the remainder based on the original sign.
     955        1361 :   std::memset(U.pVal + WordsToMove, Negative ? -1 : 0,
     956        1361 :               WordShift * APINT_WORD_SIZE);
     957        1361 :   clearUnusedBits();
     958             : }
     959             : 
     960             : /// Logical right-shift this APInt by shiftAmt.
     961             : /// @brief Logical right-shift function.
     962     1133190 : void APInt::lshrInPlace(const APInt &shiftAmt) {
     963     3399570 :   lshrInPlace((unsigned)shiftAmt.getLimitedValue(BitWidth));
     964     1133190 : }
     965             : 
     966             : /// Logical right-shift this APInt by shiftAmt.
     967             : /// @brief Logical right-shift function.
     968     1745888 : void APInt::lshrSlowCase(unsigned ShiftAmt) {
     969     3491776 :   tcShiftRight(U.pVal, getNumWords(), ShiftAmt);
     970     1745888 : }
     971             : 
     972             : /// Left-shift this APInt by shiftAmt.
     973             : /// @brief Left-shift function.
     974     1812311 : APInt &APInt::operator<<=(const APInt &shiftAmt) {
     975             :   // It's undefined behavior in C to shift by BitWidth or greater.
     976     3624622 :   *this <<= (unsigned)shiftAmt.getLimitedValue(BitWidth);
     977     1812311 :   return *this;
     978             : }
     979             : 
     980     1325420 : void APInt::shlSlowCase(unsigned ShiftAmt) {
     981     2650840 :   tcShiftLeft(U.pVal, getNumWords(), ShiftAmt);
     982     1325420 :   clearUnusedBits();
     983     1325420 : }
     984             : 
     985             : // Calculate the rotate amount modulo the bit width.
     986          48 : static unsigned rotateModulo(unsigned BitWidth, const APInt &rotateAmt) {
     987          48 :   unsigned rotBitWidth = rotateAmt.getBitWidth();
     988          96 :   APInt rot = rotateAmt;
     989          48 :   if (rotBitWidth < BitWidth) {
     990             :     // Extend the rotate APInt, so that the urem doesn't divide by 0.
     991             :     // e.g. APInt(1, 32) would give APInt(1, 0).
     992          42 :     rot = rotateAmt.zext(BitWidth);
     993             :   }
     994         240 :   rot = rot.urem(APInt(rot.getBitWidth(), BitWidth));
     995         144 :   return rot.getLimitedValue(BitWidth);
     996             : }
     997             : 
     998          32 : APInt APInt::rotl(const APInt &rotateAmt) const {
     999          32 :   return rotl(rotateModulo(BitWidth, rotateAmt));
    1000             : }
    1001             : 
    1002       25079 : APInt APInt::rotl(unsigned rotateAmt) const {
    1003       25079 :   rotateAmt %= BitWidth;
    1004       25079 :   if (rotateAmt == 0)
    1005             :     return *this;
    1006       99544 :   return shl(rotateAmt) | lshr(BitWidth - rotateAmt);
    1007             : }
    1008             : 
    1009          16 : APInt APInt::rotr(const APInt &rotateAmt) const {
    1010          16 :   return rotr(rotateModulo(BitWidth, rotateAmt));
    1011             : }
    1012             : 
    1013         329 : APInt APInt::rotr(unsigned rotateAmt) const {
    1014         329 :   rotateAmt %= BitWidth;
    1015         329 :   if (rotateAmt == 0)
    1016             :     return *this;
    1017        1104 :   return lshr(rotateAmt) | shl(BitWidth - rotateAmt);
    1018             : }
    1019             : 
    1020             : // Square Root - this method computes and returns the square root of "this".
    1021             : // Three mechanisms are used for computation. For small values (<= 5 bits),
    1022             : // a table lookup is done. This gets some performance for common cases. For
    1023             : // values using less than 52 bits, the value is converted to double and then
    1024             : // the libc sqrt function is called. The result is rounded and then converted
    1025             : // back to a uint64_t which is then used to construct the result. Finally,
    1026             : // the Babylonian method for computing square roots is used.
    1027          21 : APInt APInt::sqrt() const {
    1028             : 
    1029             :   // Determine the magnitude of the value.
    1030          21 :   unsigned magnitude = getActiveBits();
    1031             : 
    1032             :   // Use a fast table for some small values. This also gets rid of some
    1033             :   // rounding errors in libc sqrt for small values.
    1034          21 :   if (magnitude <= 5) {
    1035             :     static const uint8_t results[32] = {
    1036             :       /*     0 */ 0,
    1037             :       /*  1- 2 */ 1, 1,
    1038             :       /*  3- 6 */ 2, 2, 2, 2,
    1039             :       /*  7-12 */ 3, 3, 3, 3, 3, 3,
    1040             :       /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
    1041             :       /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
    1042             :       /*    31 */ 6
    1043             :     };
    1044          13 :     return APInt(BitWidth, results[ (isSingleWord() ? U.VAL : U.pVal[0]) ]);
    1045             :   }
    1046             : 
    1047             :   // If the magnitude of the value fits in less than 52 bits (the precision of
    1048             :   // an IEEE double precision floating point value), then we can use the
    1049             :   // libc sqrt function which will probably use a hardware sqrt computation.
    1050             :   // This should be faster than the algorithm below.
    1051           8 :   if (magnitude < 52) {
    1052           8 :     return APInt(BitWidth,
    1053           8 :                  uint64_t(::round(::sqrt(double(isSingleWord() ? U.VAL
    1054           8 :                                                                : U.pVal[0])))));
    1055             :   }
    1056             : 
    1057             :   // Okay, all the short cuts are exhausted. We must compute it. The following
    1058             :   // is a classical Babylonian method for computing the square root. This code
    1059             :   // was adapted to APInt from a wikipedia article on such computations.
    1060             :   // See http://www.wikipedia.org/ and go to the page named
    1061             :   // Calculate_an_integer_square_root.
    1062           0 :   unsigned nbits = BitWidth, i = 4;
    1063           0 :   APInt testy(BitWidth, 16);
    1064           0 :   APInt x_old(BitWidth, 1);
    1065           0 :   APInt x_new(BitWidth, 0);
    1066           0 :   APInt two(BitWidth, 2);
    1067             : 
    1068             :   // Select a good starting value using binary logarithms.
    1069           0 :   for (;; i += 2, testy = testy.shl(2))
    1070           0 :     if (i >= nbits || this->ule(testy)) {
    1071           0 :       x_old = x_old.shl(i / 2);
    1072           0 :       break;
    1073             :     }
    1074             : 
    1075             :   // Use the Babylonian method to arrive at the integer square root:
    1076             :   for (;;) {
    1077           0 :     x_new = (this->udiv(x_old) + x_old).udiv(two);
    1078           0 :     if (x_old.ule(x_new))
    1079             :       break;
    1080           0 :     x_old = x_new;
    1081             :   }
    1082             : 
    1083             :   // Make sure we return the closest approximation
    1084             :   // NOTE: The rounding calculation below is correct. It will produce an
    1085             :   // off-by-one discrepancy with results from pari/gp. That discrepancy has been
    1086             :   // determined to be a rounding issue with pari/gp as it begins to use a
    1087             :   // floating point representation after 192 bits. There are no discrepancies
    1088             :   // between this algorithm and pari/gp for bit widths < 192 bits.
    1089           0 :   APInt square(x_old * x_old);
    1090           0 :   APInt nextSquare((x_old + 1) * (x_old +1));
    1091           0 :   if (this->ult(square))
    1092             :     return x_old;
    1093             :   assert(this->ule(nextSquare) && "Error in APInt::sqrt computation");
    1094           0 :   APInt midpoint((nextSquare - square).udiv(two));
    1095           0 :   APInt offset(*this - square);
    1096           0 :   if (offset.ult(midpoint))
    1097             :     return x_old;
    1098           0 :   return x_old + 1;
    1099             : }
    1100             : 
    1101             : /// Computes the multiplicative inverse of this APInt for a given modulo. The
    1102             : /// iterative extended Euclidean algorithm is used to solve for this value,
    1103             : /// however we simplify it to speed up calculating only the inverse, and take
    1104             : /// advantage of div+rem calculations. We also use some tricks to avoid copying
    1105             : /// (potentially large) APInts around.
    1106        2311 : APInt APInt::multiplicativeInverse(const APInt& modulo) const {
    1107             :   assert(ult(modulo) && "This APInt must be smaller than the modulo");
    1108             : 
    1109             :   // Using the properties listed at the following web page (accessed 06/21/08):
    1110             :   //   http://www.numbertheory.org/php/euclid.html
    1111             :   // (especially the properties numbered 3, 4 and 9) it can be proved that
    1112             :   // BitWidth bits suffice for all the computations in the algorithm implemented
    1113             :   // below. More precisely, this number of bits suffice if the multiplicative
    1114             :   // inverse exists, but may not suffice for the general extended Euclidean
    1115             :   // algorithm.
    1116             : 
    1117       13866 :   APInt r[2] = { modulo, *this };
    1118       13866 :   APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) };
    1119        4622 :   APInt q(BitWidth, 0);
    1120             : 
    1121             :   unsigned i;
    1122       16202 :   for (i = 0; r[i^1] != 0; i ^= 1) {
    1123             :     // An overview of the math without the confusing bit-flipping:
    1124             :     // q = r[i-2] / r[i-1]
    1125             :     // r[i] = r[i-2] % r[i-1]
    1126             :     // t[i] = t[i-2] - t[i-1] * q
    1127        3860 :     udivrem(r[i], r[i^1], q, r[i]);
    1128        7720 :     t[i] -= t[i^1] * q;
    1129             :   }
    1130             : 
    1131             :   // If this APInt and the modulo are not coprime, there is no multiplicative
    1132             :   // inverse, so return 0. We check this by looking at the next-to-last
    1133             :   // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean
    1134             :   // algorithm.
    1135        4622 :   if (r[i] != 1)
    1136           0 :     return APInt(BitWidth, 0);
    1137             : 
    1138             :   // The next-to-last t is the multiplicative inverse.  However, we are
    1139             :   // interested in a positive inverse. Calculate a positive one from a negative
    1140             :   // one if necessary. A simple addition of the modulo suffices because
    1141             :   // abs(t[i]) is known to be less than *this/2 (see the link above).
    1142        4622 :   if (t[i].isNegative())
    1143         461 :     t[i] += modulo;
    1144             : 
    1145        2311 :   return std::move(t[i]);
    1146             : }
    1147             : 
    1148             : /// Calculate the magic numbers required to implement a signed integer division
    1149             : /// by a constant as a sequence of multiplies, adds and shifts.  Requires that
    1150             : /// the divisor not be 0, 1, or -1.  Taken from "Hacker's Delight", Henry S.
    1151             : /// Warren, Jr., chapter 10.
    1152         505 : APInt::ms APInt::magic() const {
    1153         505 :   const APInt& d = *this;
    1154             :   unsigned p;
    1155        8080 :   APInt ad, anc, delta, q1, r1, q2, r2, t;
    1156        1010 :   APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
    1157         505 :   struct ms mag;
    1158             : 
    1159        1515 :   ad = d.abs();
    1160        2525 :   t = signedMin + (d.lshr(d.getBitWidth() - 1));
    1161        4040 :   anc = t - 1 - t.urem(ad);   // absolute value of nc
    1162         505 :   p = d.getBitWidth() - 1;    // initialize p
    1163        1515 :   q1 = signedMin.udiv(anc);   // initialize q1 = 2p/abs(nc)
    1164        2020 :   r1 = signedMin - q1*anc;    // initialize r1 = rem(2p,abs(nc))
    1165        1515 :   q2 = signedMin.udiv(ad);    // initialize q2 = 2p/abs(d)
    1166        2020 :   r2 = signedMin - q2*ad;     // initialize r2 = rem(2p,abs(d))
    1167             :   do {
    1168        2008 :     p = p + 1;
    1169        6024 :     q1 = q1<<1;          // update q1 = 2p/abs(nc)
    1170        6024 :     r1 = r1<<1;          // update r1 = rem(2p/abs(nc))
    1171        2008 :     if (r1.uge(anc)) {  // must be unsigned comparison
    1172           5 :       q1 = q1 + 1;
    1173           5 :       r1 = r1 - anc;
    1174             :     }
    1175        6024 :     q2 = q2<<1;          // update q2 = 2p/abs(d)
    1176        6024 :     r2 = r2<<1;          // update r2 = rem(2p/abs(d))
    1177        2008 :     if (r2.uge(ad)) {   // must be unsigned comparison
    1178        3955 :       q2 = q2 + 1;
    1179        3955 :       r2 = r2 - ad;
    1180             :     }
    1181       10040 :     delta = ad - r2;
    1182        2513 :   } while (q1.ult(delta) || (q1 == delta && r1 == 0));
    1183             : 
    1184        2525 :   mag.m = q2 + 1;
    1185        1030 :   if (d.isNegative()) mag.m = -mag.m;   // resulting magic number
    1186         505 :   mag.s = p - d.getBitWidth();          // resulting shift
    1187         505 :   return mag;
    1188             : }
    1189             : 
    1190             : /// Calculate the magic numbers required to implement an unsigned integer
    1191             : /// division by a constant as a sequence of multiplies, adds and shifts.
    1192             : /// Requires that the divisor not be 0.  Taken from "Hacker's Delight", Henry
    1193             : /// S. Warren, Jr., chapter 10.
    1194             : /// LeadingZeros can be used to simplify the calculation if the upper bits
    1195             : /// of the divided value are known zero.
    1196         664 : APInt::mu APInt::magicu(unsigned LeadingZeros) const {
    1197         664 :   const APInt& d = *this;
    1198             :   unsigned p;
    1199        7968 :   APInt nc, delta, q1, r1, q2, r2;
    1200         664 :   struct mu magu;
    1201         664 :   magu.a = 0;               // initialize "add" indicator
    1202        1992 :   APInt allOnes = APInt::getAllOnesValue(d.getBitWidth()).lshr(LeadingZeros);
    1203        1328 :   APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
    1204        1328 :   APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());
    1205             : 
    1206        4648 :   nc = allOnes - (allOnes - d).urem(d);
    1207         664 :   p = d.getBitWidth() - 1;  // initialize p
    1208        1992 :   q1 = signedMin.udiv(nc);  // initialize q1 = 2p/nc
    1209        2656 :   r1 = signedMin - q1*nc;   // initialize r1 = rem(2p,nc)
    1210        1992 :   q2 = signedMax.udiv(d);   // initialize q2 = (2p-1)/d
    1211        2656 :   r2 = signedMax - q2*d;    // initialize r2 = rem((2p-1),d)
    1212             :   do {
    1213        4184 :     p = p + 1;
    1214       20920 :     if (r1.uge(nc - r1)) {
    1215        5544 :       q1 = q1 + q1 + 1;  // update q1
    1216        5544 :       r1 = r1 + r1 - nc; // update r1
    1217             :     }
    1218             :     else {
    1219       16960 :       q1 = q1+q1; // update q1
    1220       16960 :       r1 = r1+r1; // update r1
    1221             :     }
    1222       37656 :     if ((r2 + 1).uge(d - r2)) {
    1223        1608 :       if (q2.uge(signedMax)) magu.a = 1;
    1224       11256 :       q2 = q2+q2 + 1;     // update q2
    1225       14472 :       r2 = r2+r2 + 1 - d; // update r2
    1226             :     }
    1227             :     else {
    1228        2576 :       if (q2.uge(signedMin)) magu.a = 1;
    1229       12880 :       q2 = q2+q2;     // update q2
    1230       18032 :       r2 = r2+r2 + 1; // update r2
    1231             :     }
    1232       29288 :     delta = d - 1 - r2;
    1233        8368 :   } while (p < d.getBitWidth()*2 &&
    1234        4848 :            (q1.ult(delta) || (q1 == delta && r1 == 0)));
    1235        3320 :   magu.m = q2 + 1; // resulting magic number
    1236         664 :   magu.s = p - d.getBitWidth();  // resulting shift
    1237         664 :   return magu;
    1238             : }
    1239             : 
    1240             : /// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
    1241             : /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
    1242             : /// variables here have the same names as in the algorithm. Comments explain
    1243             : /// the algorithm and any deviation from it.
    1244        2520 : static void KnuthDiv(uint32_t *u, uint32_t *v, uint32_t *q, uint32_t* r,
    1245             :                      unsigned m, unsigned n) {
    1246             :   assert(u && "Must provide dividend");
    1247             :   assert(v && "Must provide divisor");
    1248             :   assert(q && "Must provide quotient");
    1249             :   assert(u != v && u != q && v != q && "Must use different memory");
    1250             :   assert(n>1 && "n must be > 1");
    1251             : 
    1252             :   // b denotes the base of the number system. In our case b is 2^32.
    1253        2520 :   const uint64_t b = uint64_t(1) << 32;
    1254             : 
    1255             :   DEBUG(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n');
    1256             :   DEBUG(dbgs() << "KnuthDiv: original:");
    1257             :   DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
    1258             :   DEBUG(dbgs() << " by");
    1259             :   DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
    1260             :   DEBUG(dbgs() << '\n');
    1261             :   // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of
    1262             :   // u and v by d. Note that we have taken Knuth's advice here to use a power
    1263             :   // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
    1264             :   // 2 allows us to shift instead of multiply and it is easy to determine the
    1265             :   // shift amount from the leading zeros.  We are basically normalizing the u
    1266             :   // and v so that its high bits are shifted to the top of v's range without
    1267             :   // overflow. Note that this can require an extra word in u so that u must
    1268             :   // be of length m+n+1.
    1269        5040 :   unsigned shift = countLeadingZeros(v[n-1]);
    1270        2520 :   uint32_t v_carry = 0;
    1271        2520 :   uint32_t u_carry = 0;
    1272        2520 :   if (shift) {
    1273       52176 :     for (unsigned i = 0; i < m+n; ++i) {
    1274       24904 :       uint32_t u_tmp = u[i] >> (32 - shift);
    1275       24904 :       u[i] = (u[i] << shift) | u_carry;
    1276       24904 :       u_carry = u_tmp;
    1277             :     }
    1278       44270 :     for (unsigned i = 0; i < n; ++i) {
    1279       20951 :       uint32_t v_tmp = v[i] >> (32 - shift);
    1280       20951 :       v[i] = (v[i] << shift) | v_carry;
    1281       20951 :       v_carry = v_tmp;
    1282             :     }
    1283             :   }
    1284        2520 :   u[m+n] = u_carry;
    1285             : 
    1286             :   DEBUG(dbgs() << "KnuthDiv:   normal:");
    1287             :   DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
    1288             :   DEBUG(dbgs() << " by");
    1289             :   DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
    1290             :   DEBUG(dbgs() << '\n');
    1291             : 
    1292             :   // D2. [Initialize j.]  Set j to m. This is the loop counter over the places.
    1293        2520 :   int j = m;
    1294             :   do {
    1295             :     DEBUG(dbgs() << "KnuthDiv: quotient digit #" << j << '\n');
    1296             :     // D3. [Calculate q'.].
    1297             :     //     Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
    1298             :     //     Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
    1299             :     // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
    1300             :     // qp by 1, increase rp by v[n-1], and repeat this test if rp < b. The test
    1301             :     // on v[n-2] determines at high speed most of the cases in which the trial
    1302             :     // value qp is one too large, and it eliminates all cases where qp is two
    1303             :     // too large.
    1304       13290 :     uint64_t dividend = Make_64(u[j+n], u[j+n-1]);
    1305             :     DEBUG(dbgs() << "KnuthDiv: dividend == " << dividend << '\n');
    1306        6645 :     uint64_t qp = dividend / v[n-1];
    1307        6645 :     uint64_t rp = dividend % v[n-1];
    1308        6645 :     if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
    1309         626 :       qp--;
    1310         626 :       rp += v[n-1];
    1311         626 :       if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
    1312         161 :         qp--;
    1313             :     }
    1314             :     DEBUG(dbgs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
    1315             : 
    1316             :     // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
    1317             :     // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
    1318             :     // consists of a simple multiplication by a one-place number, combined with
    1319             :     // a subtraction.
    1320             :     // The digits (u[j+n]...u[j]) should be kept positive; if the result of
    1321             :     // this step is actually negative, (u[j+n]...u[j]) should be left as the
    1322             :     // true value plus b**(n+1), namely as the b's complement of
    1323             :     // the true value, and a "borrow" to the left should be remembered.
    1324        6645 :     int64_t borrow = 0;
    1325      120451 :     for (unsigned i = 0; i < n; ++i) {
    1326      113806 :       uint64_t p = uint64_t(qp) * uint64_t(v[i]);
    1327      113806 :       int64_t subres = int64_t(u[j+i]) - borrow - Lo_32(p);
    1328      227612 :       u[j+i] = Lo_32(subres);
    1329      227612 :       borrow = Hi_32(p) - Hi_32(subres);
    1330             :       DEBUG(dbgs() << "KnuthDiv: u[j+i] = " << u[j+i]
    1331             :                    << ", borrow = " << borrow << '\n');
    1332             :     }
    1333        6645 :     bool isNeg = u[j+n] < borrow;
    1334       13290 :     u[j+n] -= Lo_32(borrow);
    1335             : 
    1336             :     DEBUG(dbgs() << "KnuthDiv: after subtraction:");
    1337             :     DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
    1338             :     DEBUG(dbgs() << '\n');
    1339             : 
    1340             :     // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
    1341             :     // negative, go to step D6; otherwise go on to step D7.
    1342       13290 :     q[j] = Lo_32(qp);
    1343        6645 :     if (isNeg) {
    1344             :       // D6. [Add back]. The probability that this step is necessary is very
    1345             :       // small, on the order of only 2/b. Make sure that test data accounts for
    1346             :       // this possibility. Decrease q[j] by 1
    1347          48 :       q[j]--;
    1348             :       // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
    1349             :       // A carry will occur to the left of u[j+n], and it should be ignored
    1350             :       // since it cancels with the borrow that occurred in D4.
    1351          48 :       bool carry = false;
    1352         456 :       for (unsigned i = 0; i < n; i++) {
    1353         816 :         uint32_t limit = std::min(u[j+i],v[i]);
    1354         408 :         u[j+i] += v[i] + carry;
    1355         408 :         carry = u[j+i] < limit || (carry && u[j+i] == limit);
    1356             :       }
    1357          48 :       u[j+n] += carry;
    1358             :     }
    1359             :     DEBUG(dbgs() << "KnuthDiv: after correction:");
    1360             :     DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
    1361             :     DEBUG(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n');
    1362             : 
    1363             :   // D7. [Loop on j.]  Decrease j by one. Now if j >= 0, go back to D3.
    1364        6645 :   } while (--j >= 0);
    1365             : 
    1366             :   DEBUG(dbgs() << "KnuthDiv: quotient:");
    1367             :   DEBUG(for (int i = m; i >=0; i--) dbgs() <<" " << q[i]);
    1368             :   DEBUG(dbgs() << '\n');
    1369             : 
    1370             :   // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
    1371             :   // remainder may be obtained by dividing u[...] by d. If r is non-null we
    1372             :   // compute the remainder (urem uses this).
    1373        2520 :   if (r) {
    1374             :     // The value d is expressed by the "shift" value above since we avoided
    1375             :     // multiplication by d by using a shift left. So, all we have to do is
    1376             :     // shift right here.
    1377          50 :     if (shift) {
    1378          40 :       uint32_t carry = 0;
    1379             :       DEBUG(dbgs() << "KnuthDiv: remainder:");
    1380         856 :       for (int i = n-1; i >= 0; i--) {
    1381         816 :         r[i] = (u[i] >> shift) | carry;
    1382         816 :         carry = u[i] << (32 - shift);
    1383             :         DEBUG(dbgs() << " " << r[i]);
    1384             :       }
    1385             :     } else {
    1386          38 :       for (int i = n-1; i >= 0; i--) {
    1387          28 :         r[i] = u[i];
    1388             :         DEBUG(dbgs() << " " << r[i]);
    1389             :       }
    1390             :     }
    1391             :     DEBUG(dbgs() << '\n');
    1392             :   }
    1393             :   DEBUG(dbgs() << '\n');
    1394        2520 : }
    1395             : 
    1396       44998 : void APInt::divide(const WordType *LHS, unsigned lhsWords, const WordType *RHS,
    1397             :                    unsigned rhsWords, WordType *Quotient, WordType *Remainder) {
    1398             :   assert(lhsWords >= rhsWords && "Fractional result");
    1399             : 
    1400             :   // First, compose the values into an array of 32-bit words instead of
    1401             :   // 64-bit words. This is a necessity of both the "short division" algorithm
    1402             :   // and the Knuth "classical algorithm" which requires there to be native
    1403             :   // operations for +, -, and * on an m bit value with an m*2 bit result. We
    1404             :   // can't use 64-bit operands here because we don't have native results of
    1405             :   // 128-bits. Furthermore, casting the 64-bit values to 32-bit values won't
    1406             :   // work on large-endian machines.
    1407       44998 :   unsigned n = rhsWords * 2;
    1408       44998 :   unsigned m = (lhsWords * 2) - n;
    1409             : 
    1410             :   // Allocate space for the temporary values we need either on the stack, if
    1411             :   // it will fit, or on the heap if it won't.
    1412             :   uint32_t SPACE[128];
    1413       44998 :   uint32_t *U = nullptr;
    1414       44998 :   uint32_t *V = nullptr;
    1415       44998 :   uint32_t *Q = nullptr;
    1416       44998 :   uint32_t *R = nullptr;
    1417       44998 :   if ((Remainder?4:3)*n+2*m+1 <= 128) {
    1418       44803 :     U = &SPACE[0];
    1419       44803 :     V = &SPACE[m+n+1];
    1420       44803 :     Q = &SPACE[(m+n+1) + n];
    1421       44803 :     if (Remainder)
    1422       39603 :       R = &SPACE[(m+n+1) + n + (m+n)];
    1423             :   } else {
    1424         195 :     U = new uint32_t[m + n + 1];
    1425         195 :     V = new uint32_t[n];
    1426         195 :     Q = new uint32_t[m+n];
    1427         195 :     if (Remainder)
    1428           8 :       R = new uint32_t[n];
    1429             :   }
    1430             : 
    1431             :   // Initialize the dividend
    1432       44998 :   memset(U, 0, (m+n+1)*sizeof(uint32_t));
    1433      145148 :   for (unsigned i = 0; i < lhsWords; ++i) {
    1434      100150 :     uint64_t tmp = LHS[i];
    1435      200300 :     U[i * 2] = Lo_32(tmp);
    1436      200300 :     U[i * 2 + 1] = Hi_32(tmp);
    1437             :   }
    1438       44998 :   U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
    1439             : 
    1440             :   // Initialize the divisor
    1441       44998 :   memset(V, 0, (n)*sizeof(uint32_t));
    1442      100138 :   for (unsigned i = 0; i < rhsWords; ++i) {
    1443       55140 :     uint64_t tmp = RHS[i];
    1444      110280 :     V[i * 2] = Lo_32(tmp);
    1445      110280 :     V[i * 2 + 1] = Hi_32(tmp);
    1446             :   }
    1447             : 
    1448             :   // initialize the quotient and remainder
    1449       44998 :   memset(Q, 0, (m+n) * sizeof(uint32_t));
    1450       44998 :   if (Remainder)
    1451       39611 :     memset(R, 0, n * sizeof(uint32_t));
    1452             : 
    1453             :   // Now, adjust m and n for the Knuth division. n is the number of words in
    1454             :   // the divisor. m is the number of words by which the dividend exceeds the
    1455             :   // divisor (i.e. m+n is the length of the dividend). These sizes must not
    1456             :   // contain any zero words or the Knuth algorithm fails.
    1457       88200 :   for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
    1458       43202 :     n--;
    1459       43202 :     m++;
    1460             :   }
    1461       65912 :   for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
    1462       20914 :     m--;
    1463             : 
    1464             :   // If we're left with only a single word for the divisor, Knuth doesn't work
    1465             :   // so we implement the short division algorithm here. This is much simpler
    1466             :   // and faster because we are certain that we can divide a 64-bit quantity
    1467             :   // by a 32-bit quantity at hardware speed and short division is simply a
    1468             :   // series of such operations. This is just like doing short division but we
    1469             :   // are using base 2^32 instead of base 10.
    1470             :   assert(n != 0 && "Divide by zero?");
    1471       44998 :   if (n == 1) {
    1472       42478 :     uint32_t divisor = V[0];
    1473       42478 :     uint32_t remainder = 0;
    1474      193139 :     for (int i = m; i >= 0; i--) {
    1475      301322 :       uint64_t partial_dividend = Make_64(remainder, U[i]);
    1476      150661 :       if (partial_dividend == 0) {
    1477         300 :         Q[i] = 0;
    1478         300 :         remainder = 0;
    1479      150361 :       } else if (partial_dividend < divisor) {
    1480        4412 :         Q[i] = 0;
    1481        4412 :         remainder = Lo_32(partial_dividend);
    1482      145949 :       } else if (partial_dividend == divisor) {
    1483          19 :         Q[i] = 1;
    1484          19 :         remainder = 0;
    1485             :       } else {
    1486      291860 :         Q[i] = Lo_32(partial_dividend / divisor);
    1487      291860 :         remainder = Lo_32(partial_dividend - (Q[i] * divisor));
    1488             :       }
    1489             :     }
    1490       42478 :     if (R)
    1491       39561 :       R[0] = remainder;
    1492             :   } else {
    1493             :     // Now we're ready to invoke the Knuth classical divide algorithm. In this
    1494             :     // case n > 1.
    1495        2520 :     KnuthDiv(U, V, Q, R, m, n);
    1496             :   }
    1497             : 
    1498             :   // If the caller wants the quotient
    1499       44998 :   if (Quotient) {
    1500      244360 :     for (unsigned i = 0; i < lhsWords; ++i)
    1501      199392 :       Quotient[i] = Make_64(Q[i*2+1], Q[i*2]);
    1502             :   }
    1503             : 
    1504             :   // If the caller wants the remainder
    1505       44998 :   if (Remainder) {
    1506      119609 :     for (unsigned i = 0; i < rhsWords; ++i)
    1507       79998 :       Remainder[i] = Make_64(R[i*2+1], R[i*2]);
    1508             :   }
    1509             : 
    1510             :   // Clean up the memory we allocated.
    1511       44998 :   if (U != &SPACE[0]) {
    1512         195 :     delete [] U;
    1513         195 :     delete [] V;
    1514         195 :     delete [] Q;
    1515         195 :     delete [] R;
    1516             :   }
    1517       44998 : }
    1518             : 
    1519    19765644 : APInt APInt::udiv(const APInt &RHS) const {
    1520             :   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
    1521             : 
    1522             :   // First, deal with the easy case
    1523    19765644 :   if (isSingleWord()) {
    1524             :     assert(RHS.U.VAL != 0 && "Divide by zero?");
    1525    19745633 :     return APInt(BitWidth, U.VAL / RHS.U.VAL);
    1526             :   }
    1527             : 
    1528             :   // Get some facts about the LHS and RHS number of bits and words
    1529       40022 :   unsigned lhsWords = getNumWords(getActiveBits());
    1530       20011 :   unsigned rhsBits  = RHS.getActiveBits();
    1531       20011 :   unsigned rhsWords = getNumWords(rhsBits);
    1532             :   assert(rhsWords && "Divided by zero???");
    1533             : 
    1534             :   // Deal with some degenerate cases
    1535       20011 :   if (!lhsWords)
    1536             :     // 0 / X ===> 0
    1537        1390 :     return APInt(BitWidth, 0);
    1538       18621 :   if (rhsBits == 1)
    1539             :     // X / 1 ===> X
    1540             :     return *this;
    1541       23336 :   if (lhsWords < rhsWords || this->ult(RHS))
    1542             :     // X / Y ===> 0, iff X < Y
    1543         761 :     return APInt(BitWidth, 0);
    1544       10919 :   if (*this == RHS)
    1545             :     // X / X ===> 1
    1546         757 :     return APInt(BitWidth, 1);
    1547       10162 :   if (lhsWords == 1) // rhsWords is 1 if lhsWords is 1.
    1548             :     // All high words are zero, just use native divide
    1549        4777 :     return APInt(BitWidth, this->U.pVal[0] / RHS.U.pVal[0]);
    1550             : 
    1551             :   // We have to compute it the hard way. Invoke the Knuth divide algorithm.
    1552       10770 :   APInt Quotient(BitWidth, 0); // to hold result.
    1553        5385 :   divide(U.pVal, lhsWords, RHS.U.pVal, rhsWords, Quotient.U.pVal, nullptr);
    1554        5385 :   return Quotient;
    1555             : }
    1556             : 
    1557           8 : APInt APInt::udiv(uint64_t RHS) const {
    1558             :   assert(RHS != 0 && "Divide by zero?");
    1559             : 
    1560             :   // First, deal with the easy case
    1561           8 :   if (isSingleWord())
    1562           3 :     return APInt(BitWidth, U.VAL / RHS);
    1563             : 
    1564             :   // Get some facts about the LHS words.
    1565          10 :   unsigned lhsWords = getNumWords(getActiveBits());
    1566             : 
    1567             :   // Deal with some degenerate cases
    1568           5 :   if (!lhsWords)
    1569             :     // 0 / X ===> 0
    1570           0 :     return APInt(BitWidth, 0);
    1571           5 :   if (RHS == 1)
    1572             :     // X / 1 ===> X
    1573             :     return *this;
    1574           5 :   if (this->ult(RHS))
    1575             :     // X / Y ===> 0, iff X < Y
    1576           0 :     return APInt(BitWidth, 0);
    1577           5 :   if (*this == RHS)
    1578             :     // X / X ===> 1
    1579           0 :     return APInt(BitWidth, 1);
    1580           5 :   if (lhsWords == 1) // rhsWords is 1 if lhsWords is 1.
    1581             :     // All high words are zero, just use native divide
    1582           3 :     return APInt(BitWidth, this->U.pVal[0] / RHS);
    1583             : 
    1584             :   // We have to compute it the hard way. Invoke the Knuth divide algorithm.
    1585           4 :   APInt Quotient(BitWidth, 0); // to hold result.
    1586           2 :   divide(U.pVal, lhsWords, &RHS, 1, Quotient.U.pVal, nullptr);
    1587           2 :   return Quotient;
    1588             : }
    1589             : 
    1590    19426933 : APInt APInt::sdiv(const APInt &RHS) const {
    1591    38853866 :   if (isNegative()) {
    1592        8578 :     if (RHS.isNegative())
    1593        4048 :       return (-(*this)).udiv(-RHS);
    1594       22698 :     return -((-(*this)).udiv(RHS));
    1595             :   }
    1596    38845288 :   if (RHS.isNegative())
    1597        9258 :     return -(this->udiv(-RHS));
    1598    19421101 :   return this->udiv(RHS);
    1599             : }
    1600             : 
    1601           5 : APInt APInt::sdiv(int64_t RHS) const {
    1602          10 :   if (isNegative()) {
    1603           2 :     if (RHS < 0)
    1604           0 :       return (-(*this)).udiv(-RHS);
    1605          12 :     return -((-(*this)).udiv(RHS));
    1606             :   }
    1607           3 :   if (RHS < 0)
    1608           0 :     return -(this->udiv(-RHS));
    1609           3 :   return this->udiv(RHS);
    1610             : }
    1611             : 
    1612      205049 : APInt APInt::urem(const APInt &RHS) const {
    1613             :   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
    1614      205049 :   if (isSingleWord()) {
    1615             :     assert(RHS.U.VAL != 0 && "Remainder by zero?");
    1616      205016 :     return APInt(BitWidth, U.VAL % RHS.U.VAL);
    1617             :   }
    1618             : 
    1619             :   // Get some facts about the LHS
    1620          66 :   unsigned lhsWords = getNumWords(getActiveBits());
    1621             : 
    1622             :   // Get some facts about the RHS
    1623          33 :   unsigned rhsBits = RHS.getActiveBits();
    1624          33 :   unsigned rhsWords = getNumWords(rhsBits);
    1625             :   assert(rhsWords && "Performing remainder operation by zero ???");
    1626             : 
    1627             :   // Check the degenerate cases
    1628          33 :   if (lhsWords == 0)
    1629             :     // 0 % Y ===> 0
    1630           4 :     return APInt(BitWidth, 0);
    1631          29 :   if (rhsBits == 1)
    1632             :     // X % 1 ===> 0
    1633           0 :     return APInt(BitWidth, 0);
    1634          58 :   if (lhsWords < rhsWords || this->ult(RHS))
    1635             :     // X % Y ===> X, iff X < Y
    1636             :     return *this;
    1637          29 :   if (*this == RHS)
    1638             :     // X % X == 0;
    1639           0 :     return APInt(BitWidth, 0);
    1640          29 :   if (lhsWords == 1)
    1641             :     // All high words are zero, just use native remainder
    1642           1 :     return APInt(BitWidth, U.pVal[0] % RHS.U.pVal[0]);
    1643             : 
    1644             :   // We have to compute it the hard way. Invoke the Knuth divide algorithm.
    1645          56 :   APInt Remainder(BitWidth, 0);
    1646          28 :   divide(U.pVal, lhsWords, RHS.U.pVal, rhsWords, nullptr, Remainder.U.pVal);
    1647          28 :   return Remainder;
    1648             : }
    1649             : 
    1650          75 : uint64_t APInt::urem(uint64_t RHS) const {
    1651             :   assert(RHS != 0 && "Remainder by zero?");
    1652             : 
    1653          75 :   if (isSingleWord())
    1654          70 :     return U.VAL % RHS;
    1655             : 
    1656             :   // Get some facts about the LHS
    1657          10 :   unsigned lhsWords = getNumWords(getActiveBits());
    1658             : 
    1659             :   // Check the degenerate cases
    1660           5 :   if (lhsWords == 0)
    1661             :     // 0 % Y ===> 0
    1662             :     return 0;
    1663           5 :   if (RHS == 1)
    1664             :     // X % 1 ===> 0
    1665             :     return 0;
    1666           5 :   if (this->ult(RHS))
    1667             :     // X % Y ===> X, iff X < Y
    1668           0 :     return getZExtValue();
    1669           5 :   if (*this == RHS)
    1670             :     // X % X == 0;
    1671             :     return 0;
    1672           5 :   if (lhsWords == 1)
    1673             :     // All high words are zero, just use native remainder
    1674           3 :     return U.pVal[0] % RHS;
    1675             : 
    1676             :   // We have to compute it the hard way. Invoke the Knuth divide algorithm.
    1677             :   uint64_t Remainder;
    1678           2 :   divide(U.pVal, lhsWords, &RHS, 1, nullptr, &Remainder);
    1679           2 :   return Remainder;
    1680             : }
    1681             : 
    1682       16880 : APInt APInt::srem(const APInt &RHS) const {
    1683       33760 :   if (isNegative()) {
    1684        6732 :     if (RHS.isNegative())
    1685        4290 :       return -((-(*this)).urem(-RHS));
    1686       17622 :     return -((-(*this)).urem(RHS));
    1687             :   }
    1688       27028 :   if (RHS.isNegative())
    1689        6344 :     return this->urem(-RHS);
    1690       11928 :   return this->urem(RHS);
    1691             : }
    1692             : 
    1693           5 : int64_t APInt::srem(int64_t RHS) const {
    1694          10 :   if (isNegative()) {
    1695           2 :     if (RHS < 0)
    1696           0 :       return -((-(*this)).urem(-RHS));
    1697           8 :     return -((-(*this)).urem(RHS));
    1698             :   }
    1699           3 :   if (RHS < 0)
    1700           0 :     return this->urem(-RHS);
    1701           3 :   return this->urem(RHS);
    1702             : }
    1703             : 
    1704       85049 : void APInt::udivrem(const APInt &LHS, const APInt &RHS,
    1705             :                     APInt &Quotient, APInt &Remainder) {
    1706             :   assert(LHS.BitWidth == RHS.BitWidth && "Bit widths must be the same");
    1707       85049 :   unsigned BitWidth = LHS.BitWidth;
    1708             : 
    1709             :   // First, deal with the easy case
    1710       85049 :   if (LHS.isSingleWord()) {
    1711             :     assert(RHS.U.VAL != 0 && "Divide by zero?");
    1712       82696 :     uint64_t QuotVal = LHS.U.VAL / RHS.U.VAL;
    1713       82696 :     uint64_t RemVal = LHS.U.VAL % RHS.U.VAL;
    1714      248088 :     Quotient = APInt(BitWidth, QuotVal);
    1715      248088 :     Remainder = APInt(BitWidth, RemVal);
    1716       82696 :     return;
    1717             :   }
    1718             : 
    1719             :   // Get some size facts about the dividend and divisor
    1720        4706 :   unsigned lhsWords = getNumWords(LHS.getActiveBits());
    1721        2353 :   unsigned rhsBits  = RHS.getActiveBits();
    1722        2353 :   unsigned rhsWords = getNumWords(rhsBits);
    1723             :   assert(rhsWords && "Performing divrem operation by zero ???");
    1724             : 
    1725             :   // Check the degenerate cases
    1726        2353 :   if (lhsWords == 0) {
    1727           0 :     Quotient = 0;                // 0 / Y ===> 0
    1728           0 :     Remainder = 0;               // 0 % Y ===> 0
    1729           0 :     return;
    1730             :   }
    1731             : 
    1732        2353 :   if (rhsBits == 1) {
    1733         128 :     Quotient = LHS;             // X / 1 ===> X
    1734         128 :     Remainder = 0;              // X % 1 ===> 0
    1735             :   }
    1736             : 
    1737        4706 :   if (lhsWords < rhsWords || LHS.ult(RHS)) {
    1738         335 :     Remainder = LHS;            // X % Y ===> X, iff X < Y
    1739         335 :     Quotient = 0;               // X / Y ===> 0, iff X < Y
    1740         335 :     return;
    1741             :   }
    1742             : 
    1743        2018 :   if (LHS == RHS) {
    1744          11 :     Quotient  = 1;              // X / X ===> 1
    1745          11 :     Remainder = 0;              // X % X ===> 0;
    1746          11 :     return;
    1747             :   }
    1748             : 
    1749             :   // Make sure there is enough space to hold the results.
    1750             :   // NOTE: This assumes that reallocate won't affect any bits if it doesn't
    1751             :   // change the size. This is necessary if Quotient or Remainder is aliased
    1752             :   // with LHS or RHS.
    1753        2007 :   Quotient.reallocate(BitWidth);
    1754        2007 :   Remainder.reallocate(BitWidth);
    1755             : 
    1756        2007 :   if (lhsWords == 1) { // rhsWords is 1 if lhsWords is 1.
    1757             :     // There is only one word to consider so use the native versions.
    1758        1772 :     uint64_t lhsValue = LHS.U.pVal[0];
    1759        1772 :     uint64_t rhsValue = RHS.U.pVal[0];
    1760        1772 :     Quotient = lhsValue / rhsValue;
    1761        1772 :     Remainder = lhsValue % rhsValue;
    1762        1772 :     return;
    1763             :   }
    1764             : 
    1765             :   // Okay, lets do it the long way
    1766         235 :   divide(LHS.U.pVal, lhsWords, RHS.U.pVal, rhsWords, Quotient.U.pVal,
    1767             :          Remainder.U.pVal);
    1768             :   // Clear the rest of the Quotient and Remainder.
    1769         235 :   std::memset(Quotient.U.pVal + lhsWords, 0,
    1770         235 :               (getNumWords(BitWidth) - lhsWords) * APINT_WORD_SIZE);
    1771         235 :   std::memset(Remainder.U.pVal + rhsWords, 0,
    1772         235 :               (getNumWords(BitWidth) - rhsWords) * APINT_WORD_SIZE);
    1773             : }
    1774             : 
    1775       81070 : void APInt::udivrem(const APInt &LHS, uint64_t RHS, APInt &Quotient,
    1776             :                     uint64_t &Remainder) {
    1777             :   assert(RHS != 0 && "Divide by zero?");
    1778       81070 :   unsigned BitWidth = LHS.BitWidth;
    1779             : 
    1780             :   // First, deal with the easy case
    1781       81070 :   if (LHS.isSingleWord()) {
    1782           3 :     uint64_t QuotVal = LHS.U.VAL / RHS;
    1783           3 :     Remainder = LHS.U.VAL % RHS;
    1784           9 :     Quotient = APInt(BitWidth, QuotVal);
    1785           3 :     return;
    1786             :   }
    1787             : 
    1788             :   // Get some size facts about the dividend and divisor
    1789      162134 :   unsigned lhsWords = getNumWords(LHS.getActiveBits());
    1790             : 
    1791             :   // Check the degenerate cases
    1792       81067 :   if (lhsWords == 0) {
    1793           0 :     Quotient = 0;                // 0 / Y ===> 0
    1794           0 :     Remainder = 0;               // 0 % Y ===> 0
    1795           0 :     return;
    1796             :   }
    1797             : 
    1798       81067 :   if (RHS == 1) {
    1799           0 :     Quotient = LHS;             // X / 1 ===> X
    1800           0 :     Remainder = 0;              // X % 1 ===> 0
    1801             :   }
    1802             : 
    1803       81067 :   if (LHS.ult(RHS)) {
    1804        2456 :     Remainder = LHS.getZExtValue(); // X % Y ===> X, iff X < Y
    1805        2456 :     Quotient = 0;                   // X / Y ===> 0, iff X < Y
    1806        2456 :     return;
    1807             :   }
    1808             : 
    1809       78611 :   if (LHS == RHS) {
    1810          26 :     Quotient  = 1;              // X / X ===> 1
    1811          26 :     Remainder = 0;              // X % X ===> 0;
    1812          26 :     return;
    1813             :   }
    1814             : 
    1815             :   // Make sure there is enough space to hold the results.
    1816             :   // NOTE: This assumes that reallocate won't affect any bits if it doesn't
    1817             :   // change the size. This is necessary if Quotient is aliased with LHS.
    1818       78585 :   Quotient.reallocate(BitWidth);
    1819             : 
    1820       78585 :   if (lhsWords == 1) { // rhsWords is 1 if lhsWords is 1.
    1821             :     // There is only one word to consider so use the native versions.
    1822       39239 :     uint64_t lhsValue = LHS.U.pVal[0];
    1823       39239 :     Quotient = lhsValue / RHS;
    1824       39239 :     Remainder = lhsValue % RHS;
    1825       39239 :     return;
    1826             :   }
    1827             : 
    1828             :   // Okay, lets do it the long way
    1829       39346 :   divide(LHS.U.pVal, lhsWords, &RHS, 1, Quotient.U.pVal, &Remainder);
    1830             :   // Clear the rest of the Quotient.
    1831       39346 :   std::memset(Quotient.U.pVal + lhsWords, 0,
    1832       39346 :               (getNumWords(BitWidth) - lhsWords) * APINT_WORD_SIZE);
    1833             : }
    1834             : 
    1835       20358 : void APInt::sdivrem(const APInt &LHS, const APInt &RHS,
    1836             :                     APInt &Quotient, APInt &Remainder) {
    1837       40716 :   if (LHS.isNegative()) {
    1838         364 :     if (RHS.isNegative())
    1839         584 :       APInt::udivrem(-LHS, -RHS, Quotient, Remainder);
    1840             :     else {
    1841         436 :       APInt::udivrem(-LHS, RHS, Quotient, Remainder);
    1842             :       Quotient.negate();
    1843             :     }
    1844             :     Remainder.negate();
    1845       40352 :   } else if (RHS.isNegative()) {
    1846         456 :     APInt::udivrem(LHS, -RHS, Quotient, Remainder);
    1847             :     Quotient.negate();
    1848             :   } else {
    1849       20062 :     APInt::udivrem(LHS, RHS, Quotient, Remainder);
    1850             :   }
    1851       20358 : }
    1852             : 
    1853           5 : void APInt::sdivrem(const APInt &LHS, int64_t RHS,
    1854             :                     APInt &Quotient, int64_t &Remainder) {
    1855           5 :   uint64_t R = Remainder;
    1856          10 :   if (LHS.isNegative()) {
    1857           2 :     if (RHS < 0)
    1858           0 :       APInt::udivrem(-LHS, -RHS, Quotient, R);
    1859             :     else {
    1860          10 :       APInt::udivrem(-LHS, RHS, Quotient, R);
    1861             :       Quotient.negate();
    1862             :     }
    1863           2 :     R = -R;
    1864           3 :   } else if (RHS < 0) {
    1865           0 :     APInt::udivrem(LHS, -RHS, Quotient, R);
    1866             :     Quotient.negate();
    1867             :   } else {
    1868           3 :     APInt::udivrem(LHS, RHS, Quotient, R);
    1869             :   }
    1870           5 :   Remainder = R;
    1871           5 : }
    1872             : 
    1873        7441 : APInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const {
    1874       22323 :   APInt Res = *this+RHS;
    1875       22232 :   Overflow = isNonNegative() == RHS.isNonNegative() &&
    1876       14700 :              Res.isNonNegative() != isNonNegative();
    1877        7441 :   return Res;
    1878             : }
    1879             : 
    1880       71225 : APInt APInt::uadd_ov(const APInt &RHS, bool &Overflow) const {
    1881      213675 :   APInt Res = *this+RHS;
    1882       71225 :   Overflow = Res.ult(RHS);
    1883       71225 :   return Res;
    1884             : }
    1885             : 
    1886       24887 : APInt APInt::ssub_ov(const APInt &RHS, bool &Overflow) const {
    1887       74661 :   APInt Res = *this - RHS;
    1888       49899 :   Overflow = isNonNegative() != RHS.isNonNegative() &&
    1889         250 :              Res.isNonNegative() != isNonNegative();
    1890       24887 :   return Res;
    1891             : }
    1892             : 
    1893           4 : APInt APInt::usub_ov(const APInt &RHS, bool &Overflow) const {
    1894          12 :   APInt Res = *this-RHS;
    1895           4 :   Overflow = Res.ugt(*this);
    1896           4 :   return Res;
    1897             : }
    1898             : 
    1899    19262936 : APInt APInt::sdiv_ov(const APInt &RHS, bool &Overflow) const {
    1900             :   // MININT/-1  -->  overflow.
    1901    19262936 :   Overflow = isMinSignedValue() && RHS.isAllOnesValue();
    1902    19262936 :   return sdiv(RHS);
    1903             : }
    1904             : 
    1905         231 : APInt APInt::smul_ov(const APInt &RHS, bool &Overflow) const {
    1906         231 :   APInt Res = *this * RHS;
    1907             : 
    1908         462 :   if (*this != 0 && RHS != 0)
    1909        1118 :     Overflow = Res.sdiv(RHS) != *this || Res.sdiv(*this) != RHS;
    1910             :   else
    1911           7 :     Overflow = false;
    1912         231 :   return Res;
    1913             : }
    1914             : 
    1915       13214 : APInt APInt::umul_ov(const APInt &RHS, bool &Overflow) const {
    1916       13214 :   APInt Res = *this * RHS;
    1917             : 
    1918       20028 :   if (*this != 0 && RHS != 0)
    1919       27583 :     Overflow = Res.udiv(RHS) != *this || Res.udiv(*this) != RHS;
    1920             :   else
    1921        6410 :     Overflow = false;
    1922       13214 :   return Res;
    1923             : }
    1924             : 
    1925        6823 : APInt APInt::sshl_ov(const APInt &ShAmt, bool &Overflow) const {
    1926       13646 :   Overflow = ShAmt.uge(getBitWidth());
    1927        6823 :   if (Overflow)
    1928           0 :     return APInt(BitWidth, 0);
    1929             : 
    1930        6823 :   if (isNonNegative()) // Don't allow sign change.
    1931       13646 :     Overflow = ShAmt.uge(countLeadingZeros());
    1932             :   else
    1933           0 :     Overflow = ShAmt.uge(countLeadingOnes());
    1934             : 
    1935             :   return *this << ShAmt;
    1936             : }
    1937             : 
    1938           5 : APInt APInt::ushl_ov(const APInt &ShAmt, bool &Overflow) const {
    1939          10 :   Overflow = ShAmt.uge(getBitWidth());
    1940           5 :   if (Overflow)
    1941           0 :     return APInt(BitWidth, 0);
    1942             : 
    1943           5 :   Overflow = ShAmt.ugt(countLeadingZeros());
    1944             : 
    1945             :   return *this << ShAmt;
    1946             : }
    1947             : 
    1948             : 
    1949             : 
    1950             : 
    1951     2394063 : void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) {
    1952             :   // Check our assumptions here
    1953             :   assert(!str.empty() && "Invalid string length");
    1954             :   assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
    1955             :           radix == 36) &&
    1956             :          "Radix should be 2, 8, 10, 16, or 36!");
    1957             : 
    1958     2394063 :   StringRef::iterator p = str.begin();
    1959     2394063 :   size_t slen = str.size();
    1960     2394063 :   bool isNeg = *p == '-';
    1961     2394063 :   if (*p == '-' || *p == '+') {
    1962       38133 :     p++;
    1963       38133 :     slen--;
    1964             :     assert(slen && "String is only a sign, needs a value.");
    1965             :   }
    1966             :   assert((slen <= numbits || radix != 2) && "Insufficient bit width");
    1967             :   assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width");
    1968             :   assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width");
    1969             :   assert((((slen-1)*64)/22 <= numbits || radix != 10) &&
    1970             :          "Insufficient bit width");
    1971             : 
    1972             :   // Allocate memory if needed
    1973     2394063 :   if (isSingleWord())
    1974     2392974 :     U.VAL = 0;
    1975             :   else
    1976        2178 :     U.pVal = getClearedMemory(getNumWords());
    1977             : 
    1978             :   // Figure out if we can shift instead of multiply
    1979     2394063 :   unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
    1980             : 
    1981             :   // Enter digit traversal loop
    1982     5622764 :   for (StringRef::iterator e = str.end(); p != e; ++p) {
    1983     3228701 :     unsigned digit = getDigit(*p, radix);
    1984             :     assert(digit < radix && "Invalid character in digit string");
    1985             : 
    1986             :     // Shift or multiply the value by the radix
    1987     3228701 :     if (slen > 1) {
    1988     1468598 :       if (shift)
    1989        4832 :         *this <<= shift;
    1990             :       else
    1991     1463766 :         *this *= radix;
    1992             :     }
    1993             : 
    1994             :     // Add in the digit we just interpreted
    1995     3228701 :     *this += digit;
    1996             :   }
    1997             :   // If its negative, put it in two's complement form
    1998     2394063 :   if (isNeg)
    1999             :     this->negate();
    2000     2394063 : }
    2001             : 
    2002     1458719 : void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix,
    2003             :                      bool Signed, bool formatAsCLiteral) const {
    2004             :   assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 ||
    2005             :           Radix == 36) &&
    2006             :          "Radix should be 2, 8, 10, 16, or 36!");
    2007             : 
    2008     1458719 :   const char *Prefix = "";
    2009     1458719 :   if (formatAsCLiteral) {
    2010         234 :     switch (Radix) {
    2011           3 :       case 2:
    2012             :         // Binary literals are a non-standard extension added in gcc 4.3:
    2013             :         // http://gcc.gnu.org/onlinedocs/gcc-4.3.0/gcc/Binary-constants.html
    2014           3 :         Prefix = "0b";
    2015           3 :         break;
    2016           3 :       case 8:
    2017           3 :         Prefix = "0";
    2018           3 :         break;
    2019             :       case 10:
    2020             :         break; // No prefix
    2021         199 :       case 16:
    2022         199 :         Prefix = "0x";
    2023         199 :         break;
    2024           0 :       default:
    2025           0 :         llvm_unreachable("Invalid radix!");
    2026             :     }
    2027             :   }
    2028             : 
    2029             :   // First, check for a zero value and just short circuit the logic below.
    2030     1458719 :   if (*this == 0) {
    2031      237423 :     while (*Prefix) {
    2032           5 :       Str.push_back(*Prefix);
    2033           5 :       ++Prefix;
    2034             :     };
    2035      237413 :     Str.push_back('0');
    2036     1693570 :     return;
    2037             :   }
    2038             : 
    2039             :   static const char Digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    2040             : 
    2041     1221306 :   if (isSingleWord()) {
    2042             :     char Buffer[65];
    2043     1218744 :     char *BufPtr = std::end(Buffer);
    2044             : 
    2045             :     uint64_t N;
    2046     1218744 :     if (!Signed) {
    2047      358473 :       N = getZExtValue();
    2048             :     } else {
    2049      860271 :       int64_t I = getSExtValue();
    2050      860271 :       if (I >= 0) {
    2051      826132 :         N = I;
    2052             :       } else {
    2053       34139 :         Str.push_back('-');
    2054       34139 :         N = -(uint64_t)I;
    2055             :       }
    2056             :     }
    2057             : 
    2058     1219124 :     while (*Prefix) {
    2059         190 :       Str.push_back(*Prefix);
    2060         190 :       ++Prefix;
    2061             :     };
    2062             : 
    2063    21051128 :     while (N) {
    2064     9916192 :       *--BufPtr = Digits[N % Radix];
    2065     9916192 :       N /= Radix;
    2066             :     }
    2067     1218744 :     Str.append(BufPtr, std::end(Buffer));
    2068             :     return;
    2069             :   }
    2070             : 
    2071        5124 :   APInt Tmp(*this);
    2072             : 
    2073        4211 :   if (Signed && isNegative()) {
    2074             :     // They want to print the signed version and it is a negative value
    2075             :     // Flip the bits and add one to turn it into the equivalent positive
    2076             :     // value and put a '-' in the result.
    2077         124 :     Tmp.negate();
    2078         124 :     Str.push_back('-');
    2079             :   }
    2080             : 
    2081        2986 :   while (*Prefix) {
    2082         212 :     Str.push_back(*Prefix);
    2083         212 :     ++Prefix;
    2084             :   };
    2085             : 
    2086             :   // We insert the digits backward, then reverse them to get the right order.
    2087        5124 :   unsigned StartDig = Str.size();
    2088             : 
    2089             :   // For the 2, 8 and 16 bit cases, we can just shift instead of divide
    2090             :   // because the number of bits per digit (1, 3 and 4 respectively) divides
    2091             :   // equally.  We just shift until the value is zero.
    2092        2562 :   if (Radix == 2 || Radix == 8 || Radix == 16) {
    2093             :     // Just shift tmp right for each digit width until it becomes zero
    2094         106 :     unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
    2095         106 :     unsigned MaskAmt = Radix - 1;
    2096             : 
    2097        1802 :     while (Tmp.getBoolValue()) {
    2098        1696 :       unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;
    2099        1696 :       Str.push_back(Digits[Digit]);
    2100             :       Tmp.lshrInPlace(ShiftAmt);
    2101             :     }
    2102             :   } else {
    2103      164580 :     while (Tmp.getBoolValue()) {
    2104             :       uint64_t Digit;
    2105       81062 :       udivrem(Tmp, Radix, Tmp, Digit);
    2106             :       assert(Digit < Radix && "divide failed");
    2107       81062 :       Str.push_back(Digits[Digit]);
    2108             :     }
    2109             :   }
    2110             : 
    2111             :   // Reverse the digits before returning.
    2112       10248 :   std::reverse(Str.begin()+StartDig, Str.end());
    2113             : }
    2114             : 
    2115             : /// Returns the APInt as a std::string. Note that this is an inefficient method.
    2116             : /// It is better to pass in a SmallVector/SmallString to the methods above.
    2117      850103 : std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const {
    2118     1700206 :   SmallString<40> S;
    2119      850103 :   toString(S, Radix, Signed, /* formatAsCLiteral = */false);
    2120     2550309 :   return S.str();
    2121             : }
    2122             : 
    2123             : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
    2124             : LLVM_DUMP_METHOD void APInt::dump() const {
    2125             :   SmallString<40> S, U;
    2126             :   this->toStringUnsigned(U);
    2127             :   this->toStringSigned(S);
    2128             :   dbgs() << "APInt(" << BitWidth << "b, "
    2129             :          << U << "u " << S << "s)\n";
    2130             : }
    2131             : #endif
    2132             : 
    2133      605849 : void APInt::print(raw_ostream &OS, bool isSigned) const {
    2134     1211698 :   SmallString<40> S;
    2135      605849 :   this->toString(S, 10, isSigned, /* formatAsCLiteral = */false);
    2136      605849 :   OS << S;
    2137      605849 : }
    2138             : 
    2139             : // This implements a variety of operations on a representation of
    2140             : // arbitrary precision, two's-complement, bignum integer values.
    2141             : 
    2142             : // Assumed by lowHalf, highHalf, partMSB and partLSB.  A fairly safe
    2143             : // and unrestricting assumption.
    2144             : static_assert(APInt::APINT_BITS_PER_WORD % 2 == 0,
    2145             :               "Part width must be divisible by 2!");
    2146             : 
    2147             : /* Some handy functions local to this file.  */
    2148             : 
    2149             : /* Returns the integer part with the least significant BITS set.
    2150             :    BITS cannot be zero.  */
    2151             : static inline APInt::WordType lowBitMask(unsigned bits) {
    2152             :   assert(bits != 0 && bits <= APInt::APINT_BITS_PER_WORD);
    2153             : 
    2154      144258 :   return ~(APInt::WordType) 0 >> (APInt::APINT_BITS_PER_WORD - bits);
    2155             : }
    2156             : 
    2157             : /* Returns the value of the lower half of PART.  */
    2158             : static inline APInt::WordType lowHalf(APInt::WordType part) {
    2159    16691528 :   return part & lowBitMask(APInt::APINT_BITS_PER_WORD / 2);
    2160             : }
    2161             : 
    2162             : /* Returns the value of the upper half of PART.  */
    2163             : static inline APInt::WordType highHalf(APInt::WordType part) {
    2164    16691528 :   return part >> (APInt::APINT_BITS_PER_WORD / 2);
    2165             : }
    2166             : 
    2167             : /* Returns the bit number of the most significant set bit of a part.
    2168             :    If the input number has no bits set -1U is returned.  */
    2169             : static unsigned partMSB(APInt::WordType value) {
    2170      687232 :   return findLastSet(value, ZB_Max);
    2171             : }
    2172             : 
    2173             : /* Returns the bit number of the least significant set bit of a
    2174             :    part.  If the input number has no bits set -1U is returned.  */
    2175             : static unsigned partLSB(APInt::WordType value) {
    2176      279049 :   return findFirstSet(value, ZB_Max);
    2177             : }
    2178             : 
    2179             : /* Sets the least significant part of a bignum to the input value, and
    2180             :    zeroes out higher parts.  */
    2181     1164004 : void APInt::tcSet(WordType *dst, WordType part, unsigned parts) {
    2182             :   assert(parts > 0);
    2183             : 
    2184     1164004 :   dst[0] = part;
    2185     2334864 :   for (unsigned i = 1; i < parts; i++)
    2186     1170860 :     dst[i] = 0;
    2187     1164004 : }
    2188             : 
    2189             : /* Assign one bignum to another.  */
    2190      670549 : void APInt::tcAssign(WordType *dst, const WordType *src, unsigned parts) {
    2191     1384903 :   for (unsigned i = 0; i < parts; i++)
    2192      714354 :     dst[i] = src[i];
    2193      670549 : }
    2194             : 
    2195             : /* Returns true if a bignum is zero, false otherwise.  */
    2196       11937 : bool APInt::tcIsZero(const WordType *src, unsigned parts) {
    2197       21290 :   for (unsigned i = 0; i < parts; i++)
    2198       12099 :     if (src[i])
    2199             :       return false;
    2200             : 
    2201             :   return true;
    2202             : }
    2203             : 
    2204             : /* Extract the given bit of a bignum; returns 0 or 1.  */
    2205      134905 : int APInt::tcExtractBit(const WordType *parts, unsigned bit) {
    2206      269810 :   return (parts[whichWord(bit)] & maskBit(bit)) != 0;
    2207             : }
    2208             : 
    2209             : /* Set the given bit of a bignum. */
    2210      178220 : void APInt::tcSetBit(WordType *parts, unsigned bit) {
    2211      356440 :   parts[whichWord(bit)] |= maskBit(bit);
    2212      178220 : }
    2213             : 
    2214             : /* Clears the given bit of a bignum. */
    2215         277 : void APInt::tcClearBit(WordType *parts, unsigned bit) {
    2216         554 :   parts[whichWord(bit)] &= ~maskBit(bit);
    2217         277 : }
    2218             : 
    2219             : /* Returns the bit number of the least significant set bit of a
    2220             :    number.  If the input number has no bits set -1U is returned.  */
    2221      279049 : unsigned APInt::tcLSB(const WordType *parts, unsigned n) {
    2222      312416 :   for (unsigned i = 0; i < n; i++) {
    2223      312416 :     if (parts[i] != 0) {
    2224      558098 :       unsigned lsb = partLSB(parts[i]);
    2225             : 
    2226      279049 :       return lsb + i * APINT_BITS_PER_WORD;
    2227             :     }
    2228             :   }
    2229             : 
    2230             :   return -1U;
    2231             : }
    2232             : 
    2233             : /* Returns the bit number of the most significant set bit of a number.
    2234             :    If the input number has no bits set -1U is returned.  */
    2235      689734 : unsigned APInt::tcMSB(const WordType *parts, unsigned n) {
    2236             :   do {
    2237      744183 :     --n;
    2238             : 
    2239      744183 :     if (parts[n] != 0) {
    2240     1374464 :       unsigned msb = partMSB(parts[n]);
    2241             : 
    2242      687232 :       return msb + n * APINT_BITS_PER_WORD;
    2243             :     }
    2244       56951 :   } while (n);
    2245             : 
    2246             :   return -1U;
    2247             : }
    2248             : 
    2249             : /* Copy the bit vector of width srcBITS from SRC, starting at bit
    2250             :    srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
    2251             :    the least significant bit of DST.  All high bits above srcBITS in
    2252             :    DST are zero-filled.  */
    2253             : void
    2254      145499 : APInt::tcExtract(WordType *dst, unsigned dstCount, const WordType *src,
    2255             :                  unsigned srcBits, unsigned srcLSB) {
    2256      145499 :   unsigned dstParts = (srcBits + APINT_BITS_PER_WORD - 1) / APINT_BITS_PER_WORD;
    2257             :   assert(dstParts <= dstCount);
    2258             : 
    2259      145499 :   unsigned firstSrcPart = srcLSB / APINT_BITS_PER_WORD;
    2260      145499 :   tcAssign (dst, src + firstSrcPart, dstParts);
    2261             : 
    2262      145499 :   unsigned shift = srcLSB % APINT_BITS_PER_WORD;
    2263      145499 :   tcShiftRight (dst, dstParts, shift);
    2264             : 
    2265             :   /* We now have (dstParts * APINT_BITS_PER_WORD - shift) bits from SRC
    2266             :      in DST.  If this is less that srcBits, append the rest, else
    2267             :      clear the high bits.  */
    2268      145499 :   unsigned n = dstParts * APINT_BITS_PER_WORD - shift;
    2269      145499 :   if (n < srcBits) {
    2270        3906 :     WordType mask = lowBitMask (srcBits - n);
    2271        3906 :     dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
    2272        1953 :                           << n % APINT_BITS_PER_WORD);
    2273      143546 :   } else if (n > srcBits) {
    2274      142433 :     if (srcBits % APINT_BITS_PER_WORD)
    2275      284610 :       dst[dstParts - 1] &= lowBitMask (srcBits % APINT_BITS_PER_WORD);
    2276             :   }
    2277             : 
    2278             :   /* Clear high parts.  */
    2279      236109 :   while (dstParts < dstCount)
    2280       45305 :     dst[dstParts++] = 0;
    2281      145499 : }
    2282             : 
    2283             : /* DST += RHS + C where C is zero or one.  Returns the carry flag.  */
    2284      542567 : APInt::WordType APInt::tcAdd(WordType *dst, const WordType *rhs,
    2285             :                              WordType c, unsigned parts) {
    2286             :   assert(c <= 1);
    2287             : 
    2288     1628143 :   for (unsigned i = 0; i < parts; i++) {
    2289     1085576 :     WordType l = dst[i];
    2290     1085576 :     if (c) {
    2291        2581 :       dst[i] += rhs[i] + 1;
    2292        2581 :       c = (dst[i] <= l);
    2293             :     } else {
    2294     1082995 :       dst[i] += rhs[i];
    2295     1082995 :       c = (dst[i] < l);
    2296             :     }
    2297             :   }
    2298             : 
    2299      542567 :   return c;
    2300             : }
    2301             : 
    2302             : /// This function adds a single "word" integer, src, to the multiple
    2303             : /// "word" integer array, dst[]. dst[] is modified to reflect the addition and
    2304             : /// 1 is returned if there is a carry out, otherwise 0 is returned.
    2305             : /// @returns the carry of the addition.
    2306      320469 : APInt::WordType APInt::tcAddPart(WordType *dst, WordType src,
    2307             :                                  unsigned parts) {
    2308      333042 :   for (unsigned i = 0; i < parts; ++i) {
    2309      329277 :     dst[i] += src;
    2310      329277 :     if (dst[i] >= src)
    2311             :       return 0; // No need to carry so exit early.
    2312       12573 :     src = 1; // Carry one to next digit.
    2313             :   }
    2314             : 
    2315             :   return 1;
    2316             : }
    2317             : 
    2318             : /* DST -= RHS + C where C is zero or one.  Returns the carry flag.  */
    2319      260373 : APInt::WordType APInt::tcSubtract(WordType *dst, const WordType *rhs,
    2320             :                                   WordType c, unsigned parts) {
    2321             :   assert(c <= 1);
    2322             : 
    2323      623191 :   for (unsigned i = 0; i < parts; i++) {
    2324      362818 :     WordType l = dst[i];
    2325      362818 :     if (c) {
    2326       44318 :       dst[i] -= rhs[i] + 1;
    2327       44318 :       c = (dst[i] >= l);
    2328             :     } else {
    2329      318500 :       dst[i] -= rhs[i];
    2330      318500 :       c = (dst[i] > l);
    2331             :     }
    2332             :   }
    2333             : 
    2334      260373 :   return c;
    2335             : }
    2336             : 
    2337             : /// This function subtracts a single "word" (64-bit word), src, from
    2338             : /// the multi-word integer array, dst[], propagating the borrowed 1 value until
    2339             : /// no further borrowing is needed or it runs out of "words" in dst.  The result
    2340             : /// is 1 if "borrowing" exhausted the digits in dst, or 0 if dst was not
    2341             : /// exhausted. In other words, if src > dst then this function returns 1,
    2342             : /// otherwise 0.
    2343             : /// @returns the borrow out of the subtraction
    2344      105486 : APInt::WordType APInt::tcSubtractPart(WordType *dst, WordType src,
    2345             :                                       unsigned parts) {
    2346      113228 :   for (unsigned i = 0; i < parts; ++i) {
    2347      111196 :     WordType Dst = dst[i];
    2348      111196 :     dst[i] -= src;
    2349      111196 :     if (src <= Dst)
    2350             :       return 0; // No need to borrow so exit early.
    2351        7742 :     src = 1; // We have to "borrow 1" from next "word"
    2352             :   }
    2353             : 
    2354             :   return 1;
    2355             : }
    2356             : 
    2357             : /* Negate a bignum in-place.  */
    2358         135 : void APInt::tcNegate(WordType *dst, unsigned parts) {
    2359         135 :   tcComplement(dst, parts);
    2360         135 :   tcIncrement(dst, parts);
    2361         135 : }
    2362             : 
    2363             : /*  DST += SRC * MULTIPLIER + CARRY   if add is true
    2364             :     DST  = SRC * MULTIPLIER + CARRY   if add is false
    2365             : 
    2366             :     Requires 0 <= DSTPARTS <= SRCPARTS + 1.  If DST overlaps SRC
    2367             :     they must start at the same point, i.e. DST == SRC.
    2368             : 
    2369             :     If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
    2370             :     returned.  Otherwise DST is filled with the least significant
    2371             :     DSTPARTS parts of the result, and if all of the omitted higher
    2372             :     parts were zero return zero, otherwise overflow occurred and
    2373             :     return one.  */
    2374     2044269 : int APInt::tcMultiplyPart(WordType *dst, const WordType *src,
    2375             :                           WordType multiplier, WordType carry,
    2376             :                           unsigned srcParts, unsigned dstParts,
    2377             :                           bool add) {
    2378             :   /* Otherwise our writes of DST kill our later reads of SRC.  */
    2379             :   assert(dst <= src || dst >= src + srcParts);
    2380             :   assert(dstParts <= srcParts + 1);
    2381             : 
    2382             :   /* N loops; minimum of dstParts and srcParts.  */
    2383     2044269 :   unsigned n = std::min(dstParts, srcParts);
    2384             : 
    2385    13652833 :   for (unsigned i = 0; i < n; i++) {
    2386             :     WordType low, mid, high, srcPart;
    2387             : 
    2388             :       /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
    2389             : 
    2390             :          This cannot overflow, because
    2391             : 
    2392             :          (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
    2393             : 
    2394             :          which is less than n^2.  */
    2395             : 
    2396    11608564 :     srcPart = src[i];
    2397             : 
    2398    11608564 :     if (multiplier == 0 || srcPart == 0) {
    2399             :       low = carry;
    2400             :       high = 0;
    2401             :     } else {
    2402     8345764 :       low = lowHalf(srcPart) * lowHalf(multiplier);
    2403     8345764 :       high = highHalf(srcPart) * highHalf(multiplier);
    2404             : 
    2405     4172882 :       mid = lowHalf(srcPart) * highHalf(multiplier);
    2406     4172882 :       high += highHalf(mid);
    2407     4172882 :       mid <<= APINT_BITS_PER_WORD / 2;
    2408     4172882 :       if (low + mid < low)
    2409     1034496 :         high++;
    2410     4172882 :       low += mid;
    2411             : 
    2412     8345764 :       mid = highHalf(srcPart) * lowHalf(multiplier);
    2413     4172882 :       high += highHalf(mid);
    2414     4172882 :       mid <<= APINT_BITS_PER_WORD / 2;
    2415     4172882 :       if (low + mid < low)
    2416     1780727 :         high++;
    2417     4172882 :       low += mid;
    2418             : 
    2419             :       /* Now add carry.  */
    2420     4172882 :       if (low + carry < low)
    2421      858955 :         high++;
    2422             :       low += carry;
    2423             :     }
    2424             : 
    2425    11608564 :     if (add) {
    2426             :       /* And now DST[i], and store the new low part there.  */
    2427    11552776 :       if (low + dst[i] < low)
    2428     1677147 :         high++;
    2429    11552776 :       dst[i] += low;
    2430             :     } else
    2431       55788 :       dst[i] = low;
    2432             : 
    2433    11608564 :     carry = high;
    2434             :   }
    2435             : 
    2436     2044269 :   if (srcParts < dstParts) {
    2437             :     /* Full multiplication, there is no overflow.  */
    2438             :     assert(srcParts + 1 == dstParts);
    2439      144151 :     dst[srcParts] = carry;
    2440      144151 :     return 0;
    2441             :   }
    2442             : 
    2443             :   /* We overflowed if there is carry.  */
    2444     1900118 :   if (carry)
    2445             :     return 1;
    2446             : 
    2447             :   /* We would overflow if any significant unwritten parts would be
    2448             :      non-zero.  This is true if any remaining src parts are non-zero
    2449             :      and the multiplier is non-zero.  */
    2450     1776606 :   if (multiplier)
    2451     1316034 :     for (unsigned i = dstParts; i < srcParts; i++)
    2452      278071 :       if (src[i])
    2453             :         return 1;
    2454             : 
    2455             :   /* We fitted in the narrow destination.  */
    2456             :   return 0;
    2457             : }
    2458             : 
    2459             : /* DST = LHS * RHS, where DST has the same width as the operands and
    2460             :    is filled with the least significant parts of the result.  Returns
    2461             :    one if overflow occurred, otherwise zero.  DST must be disjoint
    2462             :    from both operands.  */
    2463      818421 : int APInt::tcMultiply(WordType *dst, const WordType *lhs,
    2464             :                       const WordType *rhs, unsigned parts) {
    2465             :   assert(dst != lhs && dst != rhs);
    2466             : 
    2467      818421 :   int overflow = 0;
    2468      818421 :   tcSet(dst, 0, parts);
    2469             : 
    2470     2696200 :   for (unsigned i = 0; i < parts; i++)
    2471     1877779 :     overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
    2472             :                                parts - i, true);
    2473             : 
    2474      818421 :   return overflow;
    2475             : }
    2476             : 
    2477             : /// DST = LHS * RHS, where DST has width the sum of the widths of the
    2478             : /// operands. No overflow occurs. DST must be disjoint from both operands.
    2479       44249 : void APInt::tcFullMultiply(WordType *dst, const WordType *lhs,
    2480             :                            const WordType *rhs, unsigned lhsParts,
    2481             :                            unsigned rhsParts) {
    2482             :   /* Put the narrower number on the LHS for less loops below.  */
    2483       44249 :   if (lhsParts > rhsParts)
    2484             :     return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
    2485             : 
    2486             :   assert(dst != lhs && dst != rhs);
    2487             : 
    2488       44249 :   tcSet(dst, 0, rhsParts);
    2489             : 
    2490      142347 :   for (unsigned i = 0; i < lhsParts; i++)
    2491       98098 :     tcMultiplyPart(&dst[i], rhs, lhs[i], 0, rhsParts, rhsParts + 1, true);
    2492             : }
    2493             : 
    2494             : /* If RHS is zero LHS and REMAINDER are left unchanged, return one.
    2495             :    Otherwise set LHS to LHS / RHS with the fractional part discarded,
    2496             :    set REMAINDER to the remainder, return zero.  i.e.
    2497             : 
    2498             :    OLD_LHS = RHS * LHS + REMAINDER
    2499             : 
    2500             :    SCRATCH is a bignum of the same size as the operands and result for
    2501             :    use by the routine; its contents need not be initialized and are
    2502             :    destroyed.  LHS, REMAINDER and SCRATCH must be distinct.
    2503             : */
    2504           0 : int APInt::tcDivide(WordType *lhs, const WordType *rhs,
    2505             :                     WordType *remainder, WordType *srhs,
    2506             :                     unsigned parts) {
    2507             :   assert(lhs != remainder && lhs != srhs && remainder != srhs);
    2508             : 
    2509           0 :   unsigned shiftCount = tcMSB(rhs, parts) + 1;
    2510           0 :   if (shiftCount == 0)
    2511             :     return true;
    2512             : 
    2513           0 :   shiftCount = parts * APINT_BITS_PER_WORD - shiftCount;
    2514           0 :   unsigned n = shiftCount / APINT_BITS_PER_WORD;
    2515           0 :   WordType mask = (WordType) 1 << (shiftCount % APINT_BITS_PER_WORD);
    2516             : 
    2517           0 :   tcAssign(srhs, rhs, parts);
    2518           0 :   tcShiftLeft(srhs, parts, shiftCount);
    2519           0 :   tcAssign(remainder, lhs, parts);
    2520           0 :   tcSet(lhs, 0, parts);
    2521             : 
    2522             :   /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
    2523             :      the total.  */
    2524             :   for (;;) {
    2525           0 :     int compare = tcCompare(remainder, srhs, parts);
    2526           0 :     if (compare >= 0) {
    2527           0 :       tcSubtract(remainder, srhs, 0, parts);
    2528           0 :       lhs[n] |= mask;
    2529             :     }
    2530             : 
    2531           0 :     if (shiftCount == 0)
    2532             :       break;
    2533           0 :     shiftCount--;
    2534           0 :     tcShiftRight(srhs, parts, 1);
    2535           0 :     if ((mask >>= 1) == 0) {
    2536           0 :       mask = (WordType) 1 << (APINT_BITS_PER_WORD - 1);
    2537           0 :       n--;
    2538             :     }
    2539             :   }
    2540             : 
    2541             :   return false;
    2542             : }
    2543             : 
    2544             : /// Shift a bignum left Cound bits in-place. Shifted in bits are zero. There are
    2545             : /// no restrictions on Count.
    2546     2314811 : void APInt::tcShiftLeft(WordType *Dst, unsigned Words, unsigned Count) {
    2547             :   // Don't bother performing a no-op shift.
    2548     2314811 :   if (!Count)
    2549             :     return;
    2550             : 
    2551             :   // WordShift is the inter-part shift; BitShift is the intra-part shift.
    2552     4628068 :   unsigned WordShift = std::min(Count / APINT_BITS_PER_WORD, Words);
    2553     2314034 :   unsigned BitShift = Count % APINT_BITS_PER_WORD;
    2554             : 
    2555             :   // Fastpath for moving by whole words.
    2556     2314034 :   if (BitShift == 0) {
    2557       18549 :     std::memmove(Dst + WordShift, Dst, (Words - WordShift) * APINT_WORD_SIZE);
    2558             :   } else {
    2559    20895474 :     while (Words-- > WordShift) {
    2560    18599989 :       Dst[Words] = Dst[Words - WordShift] << BitShift;
    2561    18599989 :       if (Words > WordShift)
    2562    16304504 :         Dst[Words] |=
    2563    16304504 :           Dst[Words - WordShift - 1] >> (APINT_BITS_PER_WORD - BitShift);
    2564             :     }
    2565             :   }
    2566             : 
    2567             :   // Fill in the remainder with 0s.
    2568     2314034 :   std::memset(Dst, 0, WordShift * APINT_WORD_SIZE);
    2569             : }
    2570             : 
    2571             : /// Shift a bignum right Count bits in-place. Shifted in bits are zero. There
    2572             : /// are no restrictions on Count.
    2573     2120020 : void APInt::tcShiftRight(WordType *Dst, unsigned Words, unsigned Count) {
    2574             :   // Don't bother performing a no-op shift.
    2575     2120020 :   if (!Count)
    2576             :     return;
    2577             : 
    2578             :   // WordShift is the inter-part shift; BitShift is the intra-part shift.
    2579     4047466 :   unsigned WordShift = std::min(Count / APINT_BITS_PER_WORD, Words);
    2580     2023733 :   unsigned BitShift = Count % APINT_BITS_PER_WORD;
    2581             : 
    2582     2023733 :   unsigned WordsToMove = Words - WordShift;
    2583             :   // Fastpath for moving by whole words.
    2584     2023733 :   if (BitShift == 0) {
    2585      586839 :     std::memmove(Dst, Dst + WordShift, WordsToMove * APINT_WORD_SIZE);
    2586             :   } else {
    2587    18963981 :     for (unsigned i = 0; i != WordsToMove; ++i) {
    2588    17527087 :       Dst[i] = Dst[i + WordShift] >> BitShift;
    2589    17527087 :       if (i + 1 != WordsToMove)
    2590    16090560 :         Dst[i] |= Dst[i + WordShift + 1] << (APINT_BITS_PER_WORD - BitShift);
    2591             :     }
    2592             :   }
    2593             : 
    2594             :   // Fill in the remainder with 0s.
    2595     2023733 :   std::memset(Dst + WordsToMove, 0, WordShift * APINT_WORD_SIZE);
    2596             : }
    2597             : 
    2598             : /* Bitwise and of two bignums.  */
    2599       52722 : void APInt::tcAnd(WordType *dst, const WordType *rhs, unsigned parts) {
    2600      184849 :   for (unsigned i = 0; i < parts; i++)
    2601      132127 :     dst[i] &= rhs[i];
    2602       52722 : }
    2603             : 
    2604             : /* Bitwise inclusive or of two bignums.  */
    2605       67152 : void APInt::tcOr(WordType *dst, const WordType *rhs, unsigned parts) {
    2606      266270 :   for (unsigned i = 0; i < parts; i++)
    2607      199118 :     dst[i] |= rhs[i];
    2608       67152 : }
    2609             : 
    2610             : /* Bitwise exclusive or of two bignums.  */
    2611         786 : void APInt::tcXor(WordType *dst, const WordType *rhs, unsigned parts) {
    2612        3537 :   for (unsigned i = 0; i < parts; i++)
    2613        2751 :     dst[i] ^= rhs[i];
    2614         786 : }
    2615             : 
    2616             : /* Complement a bignum in-place.  */
    2617       66573 : void APInt::tcComplement(WordType *dst, unsigned parts) {
    2618      217259 :   for (unsigned i = 0; i < parts; i++)
    2619      150686 :     dst[i] = ~dst[i];
    2620       66573 : }
    2621             : 
    2622             : /* Comparison (unsigned) of two bignums.  */
    2623     1633782 : int APInt::tcCompare(const WordType *lhs, const WordType *rhs,
    2624             :                      unsigned parts) {
    2625     2229417 :   while (parts) {
    2626     2126151 :     parts--;
    2627     2126151 :     if (lhs[parts] != rhs[parts])
    2628     1530516 :       return (lhs[parts] > rhs[parts]) ? 1 : -1;
    2629             :   }
    2630             : 
    2631             :   return 0;
    2632             : }
    2633             : 
    2634             : /* Set the least significant BITS bits of a bignum, clear the
    2635             :    rest.  */
    2636          99 : void APInt::tcSetLeastSignificantBits(WordType *dst, unsigned parts,
    2637             :                                       unsigned bits) {
    2638          99 :   unsigned i = 0;
    2639         105 :   while (bits > APINT_BITS_PER_WORD) {
    2640           3 :     dst[i++] = ~(WordType) 0;
    2641           3 :     bits -= APINT_BITS_PER_WORD;
    2642             :   }
    2643             : 
    2644          99 :   if (bits)
    2645          76 :     dst[i++] = ~(WordType) 0 >> (APINT_BITS_PER_WORD - bits);
    2646             : 
    2647         145 :   while (i < parts)
    2648          23 :     dst[i++] = 0;
    2649          99 : }

Generated by: LCOV version 1.13