LCOV - code coverage report
Current view: top level - lib/Support - APInt.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 1038 1123 92.4 %
Date: 2018-02-25 19:55:18 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     2708271 : inline static uint64_t* getClearedMemory(unsigned numWords) {
      36     2708271 :   uint64_t * result = new uint64_t[numWords];
      37             :   assert(result && "APInt memory allocation fails!");
      38     2708271 :   memset(result, 0, numWords * sizeof(uint64_t));
      39     2708271 :   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     5228834 :   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     4091823 : inline static unsigned getDigit(char cdigit, uint8_t radix) {
      52             :   unsigned r;
      53             : 
      54     4091823 :   if (radix == 16 || radix == 36) {
      55        5761 :     r = cdigit - '0';
      56        5761 :     if (r <= 9)
      57             :       return r;
      58             : 
      59        1167 :     r = cdigit - 'A';
      60        1167 :     if (r <= radix - 11U)
      61         474 :       return r + 10;
      62             : 
      63         693 :     r = cdigit - 'a';
      64         693 :     if (r <= radix - 11U)
      65         693 :       return r + 10;
      66             : 
      67             :     radix = 10;
      68             :   }
      69             : 
      70     4086062 :   r = cdigit - '0';
      71     4086062 :   if (r < radix)
      72             :     return r;
      73             : 
      74           0 :   return -1U;
      75             : }
      76             : 
      77             : 
      78     2703589 : void APInt::initSlowCase(uint64_t val, bool isSigned) {
      79     5407178 :   U.pVal = getClearedMemory(getNumWords());
      80     2703589 :   U.pVal[0] = val;
      81     2703589 :   if (isSigned && int64_t(val) < 0)
      82      710928 :     for (unsigned i = 1; i < getNumWords(); ++i)
      83      146952 :       U.pVal[i] = WORD_MAX;
      84     2703589 :   clearUnusedBits();
      85     2703589 : }
      86             : 
      87     3374296 : void APInt::initSlowCase(const APInt& that) {
      88     6748592 :   U.pVal = getMemory(getNumWords());
      89     6748592 :   memcpy(U.pVal, that.U.pVal, getNumWords() * APINT_WORD_SIZE);
      90     3374296 : }
      91             : 
      92      111394 : void APInt::initFromArray(ArrayRef<uint64_t> bigVal) {
      93             :   assert(BitWidth && "Bitwidth too small");
      94             :   assert(bigVal.data() && "Null pointer detected!");
      95      111394 :   if (isSingleWord())
      96      107933 :     U.VAL = bigVal[0];
      97             :   else {
      98             :     // Get memory, cleared to 0
      99        3461 :     U.pVal = getClearedMemory(getNumWords());
     100             :     // Calculate the number of words to copy
     101       10383 :     unsigned words = std::min<unsigned>(bigVal.size(), getNumWords());
     102             :     // Copy the words from bigVal to pVal
     103        3461 :     memcpy(U.pVal, bigVal.data(), words * APINT_WORD_SIZE);
     104             :   }
     105             :   // Make sure unused high bits are cleared
     106      111394 :   clearUnusedBits();
     107      111394 : }
     108             : 
     109       27316 : APInt::APInt(unsigned numBits, ArrayRef<uint64_t> bigVal)
     110       27316 :   : BitWidth(numBits) {
     111       27316 :   initFromArray(bigVal);
     112       27316 : }
     113             : 
     114       84078 : APInt::APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[])
     115       84078 :   : BitWidth(numBits) {
     116       84078 :   initFromArray(makeArrayRef(bigVal, numWords));
     117       84078 : }
     118             : 
     119     2875889 : APInt::APInt(unsigned numbits, StringRef Str, uint8_t radix)
     120     2875889 :   : BitWidth(numbits) {
     121             :   assert(BitWidth && "Bitwidth too small");
     122     2875889 :   fromString(numbits, Str, radix);
     123     2875889 : }
     124             : 
     125      167037 : void APInt::reallocate(unsigned NewBitWidth) {
     126             :   // If the number of words is the same we can just change the width and stop.
     127      334074 :   if (getNumWords() == getNumWords(NewBitWidth)) {
     128      100376 :     BitWidth = NewBitWidth;
     129      100376 :     return;
     130             :   }
     131             : 
     132             :   // If we have an allocation, delete it.
     133       66661 :   if (!isSingleWord())
     134        6308 :     delete [] U.pVal;
     135             : 
     136             :   // Update BitWidth.
     137       66661 :   BitWidth = NewBitWidth;
     138             : 
     139             :   // If we are supposed to have an allocation, create it.
     140       66661 :   if (!isSingleWord())
     141       60353 :     U.pVal = getMemory(getNumWords());
     142             : }
     143             : 
     144       73219 : void APInt::AssignSlowCase(const APInt& RHS) {
     145             :   // Don't do anything for X = X
     146       73219 :   if (this == &RHS)
     147             :     return;
     148             : 
     149             :   // Adjust the bit width and handle allocations as necessary.
     150       73051 :   reallocate(RHS.getBitWidth());
     151             : 
     152             :   // Copy the data.
     153       73051 :   if (isSingleWord())
     154        6308 :     U.VAL = RHS.U.VAL;
     155             :   else
     156       66743 :     memcpy(U.pVal, RHS.U.pVal, getNumWords() * APINT_WORD_SIZE);
     157             : }
     158             : 
     159             : /// This method 'profiles' an APInt for use with FoldingSet.
     160     2964625 : void APInt::Profile(FoldingSetNodeID& ID) const {
     161     2964625 :   ID.AddInteger(BitWidth);
     162             : 
     163     2964625 :   if (isSingleWord()) {
     164     2964621 :     ID.AddInteger(U.VAL);
     165     2964621 :     return;
     166             :   }
     167             : 
     168             :   unsigned NumWords = getNumWords();
     169          20 :   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     1393315 : APInt& APInt::operator++() {
     175     1393315 :   if (isSingleWord())
     176     1346353 :     ++U.VAL;
     177             :   else
     178       46962 :     tcIncrement(U.pVal, getNumWords());
     179     1393315 :   return clearUnusedBits();
     180             : }
     181             : 
     182             : /// @brief Prefix decrement operator. Decrements the APInt by one.
     183       93608 : APInt& APInt::operator--() {
     184       93608 :   if (isSingleWord())
     185       93599 :     --U.VAL;
     186             :   else
     187           9 :     tcDecrement(U.pVal, getNumWords());
     188       93608 :   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    17377766 : APInt& APInt::operator+=(const APInt& RHS) {
     195             :   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
     196    17377766 :   if (isSingleWord())
     197    16534662 :     U.VAL += RHS.U.VAL;
     198             :   else
     199      843104 :     tcAdd(U.pVal, RHS.U.pVal, 0, getNumWords());
     200    17377766 :   return clearUnusedBits();
     201             : }
     202             : 
     203    17245224 : APInt& APInt::operator+=(uint64_t RHS) {
     204    17245224 :   if (isSingleWord())
     205    16939373 :     U.VAL += RHS;
     206             :   else
     207      305851 :     tcAddPart(U.pVal, RHS, getNumWords());
     208    17245224 :   return clearUnusedBits();
     209             : }
     210             : 
     211             : /// Subtracts the RHS APInt from this APInt
     212             : /// @returns this, after subtraction
     213             : /// @brief Subtraction assignment operator.
     214    28415306 : APInt& APInt::operator-=(const APInt& RHS) {
     215             :   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
     216    28415306 :   if (isSingleWord())
     217    28311710 :     U.VAL -= RHS.U.VAL;
     218             :   else
     219      103596 :     tcSubtract(U.pVal, RHS.U.pVal, 0, getNumWords());
     220    28415306 :   return clearUnusedBits();
     221             : }
     222             : 
     223     3525737 : APInt& APInt::operator-=(uint64_t RHS) {
     224     3525737 :   if (isSingleWord())
     225     3409915 :     U.VAL -= RHS;
     226             :   else
     227      115822 :     tcSubtractPart(U.pVal, RHS, getNumWords());
     228     3525737 :   return clearUnusedBits();
     229             : }
     230             : 
     231    28318664 : APInt APInt::operator*(const APInt& RHS) const {
     232             :   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
     233    28318664 :   if (isSingleWord())
     234    27154835 :     return APInt(BitWidth, U.VAL * RHS.U.VAL);
     235             : 
     236             :   APInt Result(getMemory(getNumWords()), getBitWidth());
     237             : 
     238     2327658 :   tcMultiply(Result.U.pVal, U.pVal, RHS.U.pVal, getNumWords());
     239             : 
     240     1163829 :   Result.clearUnusedBits();
     241             :   return Result;
     242             : }
     243             : 
     244       68291 : void APInt::AndAssignSlowCase(const APInt& RHS) {
     245      136582 :   tcAnd(U.pVal, RHS.U.pVal, getNumWords());
     246       68291 : }
     247             : 
     248       81485 : void APInt::OrAssignSlowCase(const APInt& RHS) {
     249      162970 :   tcOr(U.pVal, RHS.U.pVal, getNumWords());
     250       81485 : }
     251             : 
     252        1201 : void APInt::XorAssignSlowCase(const APInt& RHS) {
     253        2402 :   tcXor(U.pVal, RHS.U.pVal, getNumWords());
     254        1201 : }
     255             : 
     256      883164 : APInt& APInt::operator*=(const APInt& RHS) {
     257             :   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
     258     1766328 :   *this = *this * RHS;
     259      883164 :   return *this;
     260             : }
     261             : 
     262     2430633 : APInt& APInt::operator*=(uint64_t RHS) {
     263     2430633 :   if (isSingleWord()) {
     264     2405567 :     U.VAL *= RHS;
     265             :   } else {
     266             :     unsigned NumWords = getNumWords();
     267       25066 :     tcMultiplyPart(U.pVal, U.pVal, RHS, 0, NumWords, NumWords, false);
     268             :   }
     269     2430633 :   return clearUnusedBits();
     270             : }
     271             : 
     272     1872445 : bool APInt::EqualSlowCase(const APInt& RHS) const {
     273     5617335 :   return std::equal(U.pVal, U.pVal + getNumWords(), RHS.U.pVal);
     274             : }
     275             : 
     276    20776229 : int APInt::compare(const APInt& RHS) const {
     277             :   assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
     278    20776229 :   if (isSingleWord())
     279    20166422 :     return U.VAL < RHS.U.VAL ? -1 : U.VAL > RHS.U.VAL;
     280             : 
     281      609807 :   return tcCompare(U.pVal, RHS.U.pVal, getNumWords());
     282             : }
     283             : 
     284     6347069 : int APInt::compareSigned(const APInt& RHS) const {
     285             :   assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
     286     6347069 :   if (isSingleWord()) {
     287     5967174 :     int64_t lhsSext = SignExtend64(U.VAL, BitWidth);
     288     5967174 :     int64_t rhsSext = SignExtend64(RHS.U.VAL, BitWidth);
     289     5967174 :     return lhsSext < rhsSext ? -1 : lhsSext > rhsSext;
     290             :   }
     291             : 
     292      379895 :   bool lhsNeg = isNegative();
     293      379895 :   bool rhsNeg = RHS.isNegative();
     294             : 
     295             :   // If the sign bits don't match, then (LHS < RHS) if LHS is negative
     296      379895 :   if (lhsNeg != rhsNeg)
     297      169513 :     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      210382 :   return tcCompare(U.pVal, RHS.U.pVal, getNumWords());
     302             : }
     303             : 
     304       54745 : void APInt::setBitsSlowCase(unsigned loBit, unsigned hiBit) {
     305             :   unsigned loWord = whichWord(loBit);
     306             :   unsigned hiWord = whichWord(hiBit);
     307             : 
     308             :   // Create an initial mask for the low word with zeros below loBit.
     309       54745 :   uint64_t loMask = WORD_MAX << whichBit(loBit);
     310             : 
     311             :   // If hiBit is not aligned, we need a high mask.
     312             :   unsigned hiShiftAmt = whichBit(hiBit);
     313       54745 :   if (hiShiftAmt != 0) {
     314             :     // Create a high mask with zeros above hiBit.
     315       10806 :     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       10806 :     if (hiWord == loWord)
     319        8788 :       loMask &= hiMask;
     320             :     else
     321        2018 :       U.pVal[hiWord] |= hiMask;
     322             :   }
     323             :   // Apply the mask to the low word.
     324       54745 :   U.pVal[loWord] |= loMask;
     325             : 
     326             :   // Fill any words between loWord and hiWord with all ones.
     327       76214 :   for (unsigned word = loWord + 1; word < hiWord; ++word)
     328       21469 :     U.pVal[word] = WORD_MAX;
     329       54745 : }
     330             : 
     331             : /// @brief Toggle every bit to its opposite value.
     332       76010 : void APInt::flipAllBitsSlowCase() {
     333      152020 :   tcComplement(U.pVal, getNumWords());
     334       76010 :   clearUnusedBits();
     335       76010 : }
     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      932299 : void APInt::insertBits(const APInt &subBits, unsigned bitPosition) {
     347      932299 :   unsigned subBitWidth = subBits.getBitWidth();
     348             :   assert(0 < subBitWidth && (subBitWidth + bitPosition) <= BitWidth &&
     349             :          "Illegal bit insertion");
     350             : 
     351             :   // Insertion is a direct copy.
     352      932299 :   if (subBitWidth == BitWidth) {
     353         164 :     *this = subBits;
     354         164 :     return;
     355             :   }
     356             : 
     357             :   // Single word result can be done as a direct bitmask.
     358      932135 :   if (isSingleWord()) {
     359       26407 :     uint64_t mask = WORD_MAX >> (APINT_BITS_PER_WORD - subBitWidth);
     360       26407 :     U.VAL &= ~(mask << bitPosition);
     361       26407 :     U.VAL |= (subBits.U.VAL << bitPosition);
     362       26407 :     return;
     363             :   }
     364             : 
     365             :   unsigned loBit = whichBit(bitPosition);
     366             :   unsigned loWord = whichWord(bitPosition);
     367      905728 :   unsigned hi1Word = whichWord(bitPosition + subBitWidth - 1);
     368             : 
     369             :   // Insertion within a single word can be done as a direct bitmask.
     370      905728 :   if (loWord == hi1Word) {
     371      905698 :     uint64_t mask = WORD_MAX >> (APINT_BITS_PER_WORD - subBitWidth);
     372      905698 :     U.pVal[loWord] &= ~(mask << loBit);
     373      905698 :     U.pVal[loWord] |= (subBits.U.VAL << loBit);
     374      905698 :     return;
     375             :   }
     376             : 
     377             :   // Insert on word boundaries.
     378          30 :   if (loBit == 0) {
     379             :     // Direct copy whole words.
     380          28 :     unsigned numWholeSubWords = subBitWidth / APINT_BITS_PER_WORD;
     381          56 :     memcpy(U.pVal + loWord, subBits.getRawData(),
     382          28 :            numWholeSubWords * APINT_WORD_SIZE);
     383             : 
     384             :     // Mask+insert remaining bits.
     385          28 :     unsigned remainingBits = subBitWidth % APINT_BITS_PER_WORD;
     386          28 :     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      344029 : 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      344029 :   if (isSingleWord())
     411       37245 :     return APInt(numBits, U.VAL >> bitPosition);
     412             : 
     413             :   unsigned loBit = whichBit(bitPosition);
     414             :   unsigned loWord = whichWord(bitPosition);
     415      306784 :   unsigned hiWord = whichWord(bitPosition + numBits - 1);
     416             : 
     417             :   // Single word result extracting bits from a single word source.
     418      306784 :   if (loWord == hiWord)
     419      306766 :     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          18 :   if (loBit == 0)
     424          14 :     return APInt(numBits, makeArrayRef(U.pVal + loWord, 1 + hiWord - loWord));
     425             : 
     426             :   // General case - shift + copy source words directly into place.
     427             :   APInt Result(numBits, 0);
     428           4 :   unsigned NumSrcWords = getNumWords();
     429           4 :   unsigned NumDstWords = Result.getNumWords();
     430             : 
     431           4 :   uint64_t *DestPtr = Result.isSingleWord() ? &Result.U.VAL : Result.U.pVal;
     432          20 :   for (unsigned word = 0; word < NumDstWords; ++word) {
     433           8 :     uint64_t w0 = U.pVal[loWord + word];
     434             :     uint64_t w1 =
     435           8 :         (loWord + word + 1) < NumSrcWords ? U.pVal[loWord + word + 1] : 0;
     436           8 :     DestPtr[word] = (w0 >> loBit) | (w1 << (APINT_BITS_PER_WORD - loBit));
     437             :   }
     438             : 
     439           4 :   return Result.clearUnusedBits();
     440             : }
     441             : 
     442          61 : unsigned APInt::getBitsNeeded(StringRef str, uint8_t radix) {
     443             :   assert(!str.empty() && "Invalid string length");
     444             :   assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
     445             :           radix == 36) &&
     446             :          "Radix should be 2, 8, 10, 16, or 36!");
     447             : 
     448             :   size_t slen = str.size();
     449             : 
     450             :   // Each computation below needs to know if it's negative.
     451          61 :   StringRef::iterator p = str.begin();
     452          61 :   unsigned isNegative = *p == '-';
     453          61 :   if (*p == '-' || *p == '+') {
     454          40 :     p++;
     455          40 :     slen--;
     456             :     assert(slen && "String is only a sign, needs a value.");
     457             :   }
     458             : 
     459             :   // For radixes of power-of-two values, the bits required is accurately and
     460             :   // easily computed
     461          61 :   if (radix == 2)
     462          15 :     return slen + isNegative;
     463          46 :   if (radix == 8)
     464          15 :     return slen * 3 + isNegative;
     465          31 :   if (radix == 16)
     466          15 :     return slen * 4 + isNegative;
     467             : 
     468             :   // FIXME: base 36
     469             : 
     470             :   // This is grossly inefficient but accurate. We could probably do something
     471             :   // with a computation of roughly slen*64/20 and then adjust by the value of
     472             :   // the first few digits. But, I'm not sure how accurate that could be.
     473             : 
     474             :   // Compute a sufficient number of bits that is always large enough but might
     475             :   // be too large. This avoids the assertion in the constructor. This
     476             :   // calculation doesn't work appropriately for the numbers 0-9, so just use 4
     477             :   // bits in that case.
     478          25 :   unsigned sufficient
     479           9 :     = radix == 10? (slen == 1 ? 4 : slen * 64/18)
     480           0 :                  : (slen == 1 ? 7 : slen * 16/3);
     481             : 
     482             :   // Convert to the actual binary value.
     483          32 :   APInt tmp(sufficient, StringRef(p, slen), radix);
     484             : 
     485             :   // Compute how many bits are required. If the log is infinite, assume we need
     486             :   // just bit.
     487             :   unsigned log = tmp.logBase2();
     488          16 :   if (log == (unsigned)-1) {
     489           3 :     return isNegative + 1;
     490             :   } else {
     491          13 :     return isNegative + log + 1;
     492             :   }
     493             : }
     494             : 
     495    45609516 : hash_code llvm::hash_value(const APInt &Arg) {
     496    45609516 :   if (Arg.isSingleWord())
     497    45447429 :     return hash_combine(Arg.U.VAL);
     498             : 
     499      324174 :   return hash_combine_range(Arg.U.pVal, Arg.U.pVal + Arg.getNumWords());
     500             : }
     501             : 
     502       24926 : bool APInt::isSplat(unsigned SplatSizeInBits) const {
     503             :   assert(getBitWidth() % SplatSizeInBits == 0 &&
     504             :          "SplatSizeInBits must divide width!");
     505             :   // We can check that all parts of an integer are equal by making use of a
     506             :   // little trick: rotate and check if it's still the same value.
     507       49852 :   return *this == rotl(SplatSizeInBits);
     508             : }
     509             : 
     510             : /// This function returns the high "numBits" bits of this APInt.
     511       12988 : APInt APInt::getHiBits(unsigned numBits) const {
     512       12988 :   return this->lshr(BitWidth - numBits);
     513             : }
     514             : 
     515             : /// This function returns the low "numBits" bits of this APInt.
     516      361034 : APInt APInt::getLoBits(unsigned numBits) const {
     517      361034 :   APInt Result(getLowBitsSet(BitWidth, numBits));
     518             :   Result &= *this;
     519      361034 :   return Result;
     520             : }
     521             : 
     522             : /// Return a value containing V broadcasted over NewLen bits.
     523       23888 : APInt APInt::getSplat(unsigned NewLen, const APInt &V) {
     524             :   assert(NewLen >= V.getBitWidth() && "Can't splat to smaller bit width!");
     525             : 
     526       23888 :   APInt Val = V.zextOrSelf(NewLen);
     527       34232 :   for (unsigned I = V.getBitWidth(); I < NewLen; I <<= 1)
     528       10344 :     Val |= Val << I;
     529             : 
     530       23888 :   return Val;
     531             : }
     532             : 
     533     2915608 : unsigned APInt::countLeadingZerosSlowCase() const {
     534             :   unsigned Count = 0;
     535   153666487 :   for (int i = getNumWords()-1; i >= 0; --i) {
     536   150285941 :     uint64_t V = U.pVal[i];
     537   150285941 :     if (V == 0)
     538   147835271 :       Count += APINT_BITS_PER_WORD;
     539             :     else {
     540     2450670 :       Count += llvm::countLeadingZeros(V);
     541     2450670 :       break;
     542             :     }
     543             :   }
     544             :   // Adjust for unused bits in the most significant word (they are zero).
     545     2915608 :   unsigned Mod = BitWidth % APINT_BITS_PER_WORD;
     546     2915608 :   Count -= Mod > 0 ? APINT_BITS_PER_WORD - Mod : 0;
     547     2915608 :   return Count;
     548             : }
     549             : 
     550        5058 : unsigned APInt::countLeadingOnesSlowCase() const {
     551        5058 :   unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD;
     552             :   unsigned shift;
     553        5058 :   if (!highWordBits) {
     554             :     highWordBits = APINT_BITS_PER_WORD;
     555             :     shift = 0;
     556             :   } else {
     557         910 :     shift = APINT_BITS_PER_WORD - highWordBits;
     558             :   }
     559        5058 :   int i = getNumWords() - 1;
     560       10116 :   unsigned Count = llvm::countLeadingOnes(U.pVal[i] << shift);
     561        5058 :   if (Count == highWordBits) {
     562        3523 :     for (i--; i >= 0; --i) {
     563        3359 :       if (U.pVal[i] == WORD_MAX)
     564         579 :         Count += APINT_BITS_PER_WORD;
     565             :       else {
     566        2780 :         Count += llvm::countLeadingOnes(U.pVal[i]);
     567        2780 :         break;
     568             :       }
     569             :     }
     570             :   }
     571        5058 :   return Count;
     572             : }
     573             : 
     574        5088 : unsigned APInt::countTrailingZerosSlowCase() const {
     575        5088 :   unsigned Count = 0;
     576             :   unsigned i = 0;
     577       18969 :   for (; i < getNumWords() && U.pVal[i] == 0; ++i)
     578        2931 :     Count += APINT_BITS_PER_WORD;
     579        5088 :   if (i < getNumWords())
     580        8680 :     Count += llvm::countTrailingZeros(U.pVal[i]);
     581       10176 :   return std::min(Count, BitWidth);
     582             : }
     583             : 
     584      217337 : unsigned APInt::countTrailingOnesSlowCase() const {
     585             :   unsigned Count = 0;
     586             :   unsigned i = 0;
     587     1077133 :   for (; i < getNumWords() && U.pVal[i] == WORD_MAX; ++i)
     588      214153 :     Count += APINT_BITS_PER_WORD;
     589      217337 :   if (i < getNumWords())
     590      234616 :     Count += llvm::countTrailingOnes(U.pVal[i]);
     591             :   assert(Count <= BitWidth);
     592      217337 :   return Count;
     593             : }
     594             : 
     595        6200 : unsigned APInt::countPopulationSlowCase() const {
     596             :   unsigned Count = 0;
     597       72637 :   for (unsigned i = 0; i < getNumWords(); ++i)
     598       40158 :     Count += llvm::countPopulation(U.pVal[i]);
     599        6200 :   return Count;
     600             : }
     601             : 
     602        7274 : bool APInt::intersectsSlowCase(const APInt &RHS) const {
     603       66950 :   for (unsigned i = 0, e = getNumWords(); i != e; ++i)
     604       26228 :     if ((U.pVal[i] & RHS.U.pVal[i]) != 0)
     605             :       return true;
     606             : 
     607             :   return false;
     608             : }
     609             : 
     610       15432 : bool APInt::isSubsetOfSlowCase(const APInt &RHS) const {
     611       50678 :   for (unsigned i = 0, e = getNumWords(); i != e; ++i)
     612       23746 :     if ((U.pVal[i] & ~RHS.U.pVal[i]) != 0)
     613             :       return false;
     614             : 
     615             :   return true;
     616             : }
     617             : 
     618        9684 : APInt APInt::byteSwap() const {
     619             :   assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
     620        9684 :   if (BitWidth == 16)
     621        1576 :     return APInt(BitWidth, ByteSwap_16(uint16_t(U.VAL)));
     622        8896 :   if (BitWidth == 32)
     623       13032 :     return APInt(BitWidth, ByteSwap_32(unsigned(U.VAL)));
     624        2380 :   if (BitWidth == 48) {
     625           0 :     unsigned Tmp1 = unsigned(U.VAL >> 16);
     626             :     Tmp1 = ByteSwap_32(Tmp1);
     627           0 :     uint16_t Tmp2 = uint16_t(U.VAL);
     628           0 :     Tmp2 = ByteSwap_16(Tmp2);
     629           0 :     return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
     630             :   }
     631        2380 :   if (BitWidth == 64)
     632        2379 :     return APInt(BitWidth, ByteSwap_64(U.VAL));
     633             : 
     634           1 :   APInt Result(getNumWords() * APINT_BITS_PER_WORD, 0);
     635           6 :   for (unsigned I = 0, N = getNumWords(); I != N; ++I)
     636           4 :     Result.U.pVal[I] = ByteSwap_64(U.pVal[N - I - 1]);
     637           1 :   if (Result.BitWidth != BitWidth) {
     638           1 :     Result.lshrInPlace(Result.BitWidth - BitWidth);
     639           1 :     Result.BitWidth = BitWidth;
     640             :   }
     641             :   return Result;
     642             : }
     643             : 
     644        5337 : APInt APInt::reverseBits() const {
     645        5337 :   switch (BitWidth) {
     646         308 :   case 64:
     647         308 :     return APInt(BitWidth, llvm::reverseBits<uint64_t>(U.VAL));
     648        1072 :   case 32:
     649        2144 :     return APInt(BitWidth, llvm::reverseBits<uint32_t>(U.VAL));
     650         224 :   case 16:
     651         448 :     return APInt(BitWidth, llvm::reverseBits<uint16_t>(U.VAL));
     652         204 :   case 8:
     653         408 :     return APInt(BitWidth, llvm::reverseBits<uint8_t>(U.VAL));
     654             :   default:
     655             :     break;
     656             :   }
     657             : 
     658             :   APInt Val(*this);
     659        3529 :   APInt Reversed(BitWidth, 0);
     660        3529 :   unsigned S = BitWidth;
     661             : 
     662     1163339 :   for (; Val != 0; Val.lshrInPlace(1)) {
     663     1159810 :     Reversed <<= 1;
     664     1159810 :     Reversed |= Val[0];
     665     1159810 :     --S;
     666             :   }
     667             : 
     668        3529 :   Reversed <<= S;
     669             :   return Reversed;
     670             : }
     671             : 
     672        2605 : APInt llvm::APIntOps::GreatestCommonDivisor(APInt A, APInt B) {
     673             :   // Fast-path a common case.
     674        2605 :   if (A == B) return A;
     675             : 
     676             :   // Corner cases: if either operand is zero, the other is the gcd.
     677        1729 :   if (!A) return B;
     678         726 :   if (!B) return A;
     679             : 
     680             :   // Count common powers of 2 and remove all other powers of 2.
     681             :   unsigned Pow2;
     682             :   {
     683         532 :     unsigned Pow2_A = A.countTrailingZeros();
     684         532 :     unsigned Pow2_B = B.countTrailingZeros();
     685         532 :     if (Pow2_A > Pow2_B) {
     686          86 :       A.lshrInPlace(Pow2_A - Pow2_B);
     687             :       Pow2 = Pow2_B;
     688         446 :     } else if (Pow2_B > Pow2_A) {
     689         364 :       B.lshrInPlace(Pow2_B - Pow2_A);
     690             :       Pow2 = Pow2_A;
     691             :     } else {
     692             :       Pow2 = Pow2_A;
     693             :     }
     694             :   }
     695             : 
     696             :   // Both operands are odd multiples of 2^Pow_2:
     697             :   //
     698             :   //   gcd(a, b) = gcd(|a - b| / 2^i, min(a, b))
     699             :   //
     700             :   // This is a modified version of Stein's algorithm, taking advantage of
     701             :   // efficient countTrailingZeros().
     702        1924 :   while (A != B) {
     703        1392 :     if (A.ugt(B)) {
     704         336 :       A -= B;
     705         336 :       A.lshrInPlace(A.countTrailingZeros() - Pow2);
     706             :     } else {
     707        1056 :       B -= A;
     708        1056 :       B.lshrInPlace(B.countTrailingZeros() - Pow2);
     709             :     }
     710             :   }
     711             : 
     712             :   return A;
     713             : }
     714             : 
     715          40 : APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) {
     716             :   union {
     717             :     double D;
     718             :     uint64_t I;
     719             :   } T;
     720             :   T.D = Double;
     721             : 
     722             :   // Get the sign bit from the highest order bit
     723          40 :   bool isNeg = T.I >> 63;
     724             : 
     725             :   // Get the 11-bit exponent and adjust for the 1023 bit bias
     726          40 :   int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
     727             : 
     728             :   // If the exponent is negative, the value is < 0 so just return 0.
     729          40 :   if (exp < 0)
     730             :     return APInt(width, 0u);
     731             : 
     732             :   // Extract the mantissa by clearing the top 12 bits (sign + exponent).
     733          24 :   uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
     734             : 
     735             :   // If the exponent doesn't shift all bits out of the mantissa
     736          24 :   if (exp < 52)
     737          32 :     return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
     738          40 :                     APInt(width, mantissa >> (52 - exp));
     739             : 
     740             :   // If the client didn't provide enough bits for us to shift the mantissa into
     741             :   // then the result is undefined, just return 0
     742           0 :   if (width <= exp - 52)
     743             :     return APInt(width, 0);
     744             : 
     745             :   // Otherwise, we have to shift the mantissa bits up to the right location
     746             :   APInt Tmp(width, mantissa);
     747           0 :   Tmp <<= (unsigned)exp - 52;
     748           0 :   return isNeg ? -Tmp : Tmp;
     749             : }
     750             : 
     751             : /// This function converts this APInt to a double.
     752             : /// The layout for double is as following (IEEE Standard 754):
     753             : ///  --------------------------------------
     754             : /// |  Sign    Exponent    Fraction    Bias |
     755             : /// |-------------------------------------- |
     756             : /// |  1[63]   11[62-52]   52[51-00]   1023 |
     757             : ///  --------------------------------------
     758          50 : double APInt::roundToDouble(bool isSigned) const {
     759             : 
     760             :   // Handle the simple case where the value is contained in one uint64_t.
     761             :   // It is wrong to optimize getWord(0) to VAL; there might be more than one word.
     762          50 :   if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
     763          50 :     if (isSigned) {
     764             :       int64_t sext = SignExtend64(getWord(0), BitWidth);
     765          25 :       return double(sext);
     766             :     } else
     767          25 :       return double(getWord(0));
     768             :   }
     769             : 
     770             :   // Determine if the value is negative.
     771           0 :   bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
     772             : 
     773             :   // Construct the absolute value if we're negative.
     774           0 :   APInt Tmp(isNeg ? -(*this) : (*this));
     775             : 
     776             :   // Figure out how many bits we're using.
     777             :   unsigned n = Tmp.getActiveBits();
     778             : 
     779             :   // The exponent (without bias normalization) is just the number of bits
     780             :   // we are using. Note that the sign bit is gone since we constructed the
     781             :   // absolute value.
     782           0 :   uint64_t exp = n;
     783             : 
     784             :   // Return infinity for exponent overflow
     785           0 :   if (exp > 1023) {
     786           0 :     if (!isSigned || !isNeg)
     787             :       return std::numeric_limits<double>::infinity();
     788             :     else
     789           0 :       return -std::numeric_limits<double>::infinity();
     790             :   }
     791           0 :   exp += 1023; // Increment for 1023 bias
     792             : 
     793             :   // Number of bits in mantissa is 52. To obtain the mantissa value, we must
     794             :   // extract the high 52 bits from the correct words in pVal.
     795             :   uint64_t mantissa;
     796           0 :   unsigned hiWord = whichWord(n-1);
     797           0 :   if (hiWord == 0) {
     798           0 :     mantissa = Tmp.U.pVal[0];
     799           0 :     if (n > 52)
     800           0 :       mantissa >>= n - 52; // shift down, we want the top 52 bits.
     801             :   } else {
     802             :     assert(hiWord > 0 && "huh?");
     803           0 :     uint64_t hibits = Tmp.U.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
     804           0 :     uint64_t lobits = Tmp.U.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
     805           0 :     mantissa = hibits | lobits;
     806             :   }
     807             : 
     808             :   // The leading bit of mantissa is implicit, so get rid of it.
     809           0 :   uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
     810             :   union {
     811             :     double D;
     812             :     uint64_t I;
     813             :   } T;
     814           0 :   T.I = sign | (exp << 52) | mantissa;
     815           0 :   return T.D;
     816             : }
     817             : 
     818             : // Truncate to new width.
     819    10807525 : APInt APInt::trunc(unsigned width) const {
     820             :   assert(width < BitWidth && "Invalid APInt Truncate request");
     821             :   assert(width && "Can't truncate to 0 bits");
     822             : 
     823    10807525 :   if (width <= APINT_BITS_PER_WORD)
     824    10763437 :     return APInt(width, getRawData()[0]);
     825             : 
     826             :   APInt Result(getMemory(getNumWords(width)), width);
     827             : 
     828             :   // Copy full words.
     829             :   unsigned i;
     830      261070 :   for (i = 0; i != width / APINT_BITS_PER_WORD; i++)
     831      108491 :     Result.U.pVal[i] = U.pVal[i];
     832             : 
     833             :   // Truncate and copy any partial word.
     834       44088 :   unsigned bits = (0 - width) % APINT_BITS_PER_WORD;
     835       44088 :   if (bits != 0)
     836        1826 :     Result.U.pVal[i] = U.pVal[i] << bits >> bits;
     837             : 
     838             :   return Result;
     839             : }
     840             : 
     841             : // Sign extend to a new width.
     842     5154690 : APInt APInt::sext(unsigned Width) const {
     843             :   assert(Width > BitWidth && "Invalid APInt SignExtend request");
     844             : 
     845     5154690 :   if (Width <= APINT_BITS_PER_WORD)
     846     9798882 :     return APInt(Width, SignExtend64(U.VAL, BitWidth));
     847             : 
     848             :   APInt Result(getMemory(getNumWords(Width)), Width);
     849             : 
     850             :   // Copy words.
     851      765747 :   std::memcpy(Result.U.pVal, getRawData(), getNumWords() * APINT_WORD_SIZE);
     852             : 
     853             :   // Sign extend the last word since there may be unused bits in the input.
     854      255249 :   Result.U.pVal[getNumWords() - 1] =
     855      510498 :       SignExtend64(Result.U.pVal[getNumWords() - 1],
     856      255249 :                    ((BitWidth - 1) % APINT_BITS_PER_WORD) + 1);
     857             : 
     858             :   // Fill with sign bits.
     859      510498 :   std::memset(Result.U.pVal + getNumWords(), isNegative() ? -1 : 0,
     860      255249 :               (Result.getNumWords() - getNumWords()) * APINT_WORD_SIZE);
     861      255249 :   Result.clearUnusedBits();
     862             :   return Result;
     863             : }
     864             : 
     865             : //  Zero extend to a new width.
     866     9039952 : APInt APInt::zext(unsigned width) const {
     867             :   assert(width > BitWidth && "Invalid APInt ZeroExtend request");
     868             : 
     869     9039952 :   if (width <= APINT_BITS_PER_WORD)
     870     8708933 :     return APInt(width, U.VAL);
     871             : 
     872             :   APInt Result(getMemory(getNumWords(width)), width);
     873             : 
     874             :   // Copy words.
     875      993057 :   std::memcpy(Result.U.pVal, getRawData(), getNumWords() * APINT_WORD_SIZE);
     876             : 
     877             :   // Zero remaining words.
     878      331019 :   std::memset(Result.U.pVal + getNumWords(), 0,
     879      331019 :               (Result.getNumWords() - getNumWords()) * APINT_WORD_SIZE);
     880             : 
     881             :   return Result;
     882             : }
     883             : 
     884     6471561 : APInt APInt::zextOrTrunc(unsigned width) const {
     885     6471561 :   if (BitWidth < width)
     886     2417125 :     return zext(width);
     887     4054436 :   if (BitWidth > width)
     888      821544 :     return trunc(width);
     889             :   return *this;
     890             : }
     891             : 
     892     7839541 : APInt APInt::sextOrTrunc(unsigned width) const {
     893     7839541 :   if (BitWidth < width)
     894      442325 :     return sext(width);
     895     7397216 :   if (BitWidth > width)
     896      267279 :     return trunc(width);
     897             :   return *this;
     898             : }
     899             : 
     900      145089 : APInt APInt::zextOrSelf(unsigned width) const {
     901      145089 :   if (BitWidth < width)
     902       59254 :     return zext(width);
     903             :   return *this;
     904             : }
     905             : 
     906        5226 : APInt APInt::sextOrSelf(unsigned width) const {
     907        5226 :   if (BitWidth < width)
     908        5211 :     return sext(width);
     909             :   return *this;
     910             : }
     911             : 
     912             : /// Arithmetic right-shift this APInt by shiftAmt.
     913             : /// @brief Arithmetic right-shift function.
     914        8844 : void APInt::ashrInPlace(const APInt &shiftAmt) {
     915       17688 :   ashrInPlace((unsigned)shiftAmt.getLimitedValue(BitWidth));
     916        8844 : }
     917             : 
     918             : /// Arithmetic right-shift this APInt by shiftAmt.
     919             : /// @brief Arithmetic right-shift function.
     920        2353 : void APInt::ashrSlowCase(unsigned ShiftAmt) {
     921             :   // Don't bother performing a no-op shift.
     922        2353 :   if (!ShiftAmt)
     923             :     return;
     924             : 
     925             :   // Save the original sign bit for later.
     926        2206 :   bool Negative = isNegative();
     927             : 
     928             :   // WordShift is the inter-part shift; BitShift is is intra-part shift.
     929        2206 :   unsigned WordShift = ShiftAmt / APINT_BITS_PER_WORD;
     930        2206 :   unsigned BitShift = ShiftAmt % APINT_BITS_PER_WORD;
     931             : 
     932        2206 :   unsigned WordsToMove = getNumWords() - WordShift;
     933        2206 :   if (WordsToMove != 0) {
     934             :     // Sign extend the last word to fill in the unused bits.
     935        6612 :     U.pVal[getNumWords() - 1] = SignExtend64(
     936        2204 :         U.pVal[getNumWords() - 1], ((BitWidth - 1) % APINT_BITS_PER_WORD) + 1);
     937             : 
     938             :     // Fastpath for moving by whole words.
     939        2204 :     if (BitShift == 0) {
     940         197 :       std::memmove(U.pVal, U.pVal + WordShift, WordsToMove * APINT_WORD_SIZE);
     941             :     } else {
     942             :       // Move the words containing significant bits.
     943        5661 :       for (unsigned i = 0; i != WordsToMove - 1; ++i)
     944        3654 :         U.pVal[i] = (U.pVal[i + WordShift] >> BitShift) |
     945        1827 :                     (U.pVal[i + WordShift + 1] << (APINT_BITS_PER_WORD - BitShift));
     946             : 
     947             :       // Handle the last word which has no high bits to copy.
     948        2007 :       U.pVal[WordsToMove - 1] = U.pVal[WordShift + WordsToMove - 1] >> BitShift;
     949             :       // Sign extend one more time.
     950        2007 :       U.pVal[WordsToMove - 1] =
     951        4014 :           SignExtend64(U.pVal[WordsToMove - 1], APINT_BITS_PER_WORD - BitShift);
     952             :     }
     953             :   }
     954             : 
     955             :   // Fill in the remainder based on the original sign.
     956        2206 :   std::memset(U.pVal + WordsToMove, Negative ? -1 : 0,
     957        2206 :               WordShift * APINT_WORD_SIZE);
     958        2206 :   clearUnusedBits();
     959             : }
     960             : 
     961             : /// Logical right-shift this APInt by shiftAmt.
     962             : /// @brief Logical right-shift function.
     963       22783 : void APInt::lshrInPlace(const APInt &shiftAmt) {
     964       45566 :   lshrInPlace((unsigned)shiftAmt.getLimitedValue(BitWidth));
     965       22783 : }
     966             : 
     967             : /// Logical right-shift this APInt by shiftAmt.
     968             : /// @brief Logical right-shift function.
     969     1800958 : void APInt::lshrSlowCase(unsigned ShiftAmt) {
     970     3601916 :   tcShiftRight(U.pVal, getNumWords(), ShiftAmt);
     971     1800958 : }
     972             : 
     973             : /// Left-shift this APInt by shiftAmt.
     974             : /// @brief Left-shift function.
     975      100022 : APInt &APInt::operator<<=(const APInt &shiftAmt) {
     976             :   // It's undefined behavior in C to shift by BitWidth or greater.
     977      200044 :   *this <<= (unsigned)shiftAmt.getLimitedValue(BitWidth);
     978      100022 :   return *this;
     979             : }
     980             : 
     981     1342955 : void APInt::shlSlowCase(unsigned ShiftAmt) {
     982     2685910 :   tcShiftLeft(U.pVal, getNumWords(), ShiftAmt);
     983     1342955 :   clearUnusedBits();
     984     1342955 : }
     985             : 
     986             : // Calculate the rotate amount modulo the bit width.
     987          48 : static unsigned rotateModulo(unsigned BitWidth, const APInt &rotateAmt) {
     988          48 :   unsigned rotBitWidth = rotateAmt.getBitWidth();
     989             :   APInt rot = rotateAmt;
     990          48 :   if (rotBitWidth < BitWidth) {
     991             :     // Extend the rotate APInt, so that the urem doesn't divide by 0.
     992             :     // e.g. APInt(1, 32) would give APInt(1, 0).
     993          28 :     rot = rotateAmt.zext(BitWidth);
     994             :   }
     995         192 :   rot = rot.urem(APInt(rot.getBitWidth(), BitWidth));
     996          96 :   return rot.getLimitedValue(BitWidth);
     997             : }
     998             : 
     999          32 : APInt APInt::rotl(const APInt &rotateAmt) const {
    1000          32 :   return rotl(rotateModulo(BitWidth, rotateAmt));
    1001             : }
    1002             : 
    1003       25842 : APInt APInt::rotl(unsigned rotateAmt) const {
    1004       25842 :   rotateAmt %= BitWidth;
    1005       25842 :   if (rotateAmt == 0)
    1006             :     return *this;
    1007       76881 :   return shl(rotateAmt) | lshr(BitWidth - rotateAmt);
    1008             : }
    1009             : 
    1010          16 : APInt APInt::rotr(const APInt &rotateAmt) const {
    1011          16 :   return rotr(rotateModulo(BitWidth, rotateAmt));
    1012             : }
    1013             : 
    1014         367 : APInt APInt::rotr(unsigned rotateAmt) const {
    1015         367 :   rotateAmt %= BitWidth;
    1016         367 :   if (rotateAmt == 0)
    1017             :     return *this;
    1018         924 :   return lshr(rotateAmt) | shl(BitWidth - rotateAmt);
    1019             : }
    1020             : 
    1021             : // Square Root - this method computes and returns the square root of "this".
    1022             : // Three mechanisms are used for computation. For small values (<= 5 bits),
    1023             : // a table lookup is done. This gets some performance for common cases. For
    1024             : // values using less than 52 bits, the value is converted to double and then
    1025             : // the libc sqrt function is called. The result is rounded and then converted
    1026             : // back to a uint64_t which is then used to construct the result. Finally,
    1027             : // the Babylonian method for computing square roots is used.
    1028          21 : APInt APInt::sqrt() const {
    1029             : 
    1030             :   // Determine the magnitude of the value.
    1031             :   unsigned magnitude = getActiveBits();
    1032             : 
    1033             :   // Use a fast table for some small values. This also gets rid of some
    1034             :   // rounding errors in libc sqrt for small values.
    1035          21 :   if (magnitude <= 5) {
    1036             :     static const uint8_t results[32] = {
    1037             :       /*     0 */ 0,
    1038             :       /*  1- 2 */ 1, 1,
    1039             :       /*  3- 6 */ 2, 2, 2, 2,
    1040             :       /*  7-12 */ 3, 3, 3, 3, 3, 3,
    1041             :       /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
    1042             :       /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
    1043             :       /*    31 */ 6
    1044             :     };
    1045          13 :     return APInt(BitWidth, results[ (isSingleWord() ? U.VAL : U.pVal[0]) ]);
    1046             :   }
    1047             : 
    1048             :   // If the magnitude of the value fits in less than 52 bits (the precision of
    1049             :   // an IEEE double precision floating point value), then we can use the
    1050             :   // libc sqrt function which will probably use a hardware sqrt computation.
    1051             :   // This should be faster than the algorithm below.
    1052           8 :   if (magnitude < 52) {
    1053           8 :     return APInt(BitWidth,
    1054           8 :                  uint64_t(::round(::sqrt(double(isSingleWord() ? U.VAL
    1055           8 :                                                                : U.pVal[0])))));
    1056             :   }
    1057             : 
    1058             :   // Okay, all the short cuts are exhausted. We must compute it. The following
    1059             :   // is a classical Babylonian method for computing the square root. This code
    1060             :   // was adapted to APInt from a wikipedia article on such computations.
    1061             :   // See http://www.wikipedia.org/ and go to the page named
    1062             :   // Calculate_an_integer_square_root.
    1063             :   unsigned nbits = BitWidth, i = 4;
    1064             :   APInt testy(BitWidth, 16);
    1065           0 :   APInt x_old(BitWidth, 1);
    1066           0 :   APInt x_new(BitWidth, 0);
    1067           0 :   APInt two(BitWidth, 2);
    1068             : 
    1069             :   // Select a good starting value using binary logarithms.
    1070           0 :   for (;; i += 2, testy = testy.shl(2))
    1071           0 :     if (i >= nbits || this->ule(testy)) {
    1072           0 :       x_old = x_old.shl(i / 2);
    1073           0 :       break;
    1074             :     }
    1075             : 
    1076             :   // Use the Babylonian method to arrive at the integer square root:
    1077             :   for (;;) {
    1078           0 :     x_new = (this->udiv(x_old) + x_old).udiv(two);
    1079           0 :     if (x_old.ule(x_new))
    1080             :       break;
    1081           0 :     x_old = x_new;
    1082             :   }
    1083             : 
    1084             :   // Make sure we return the closest approximation
    1085             :   // NOTE: The rounding calculation below is correct. It will produce an
    1086             :   // off-by-one discrepancy with results from pari/gp. That discrepancy has been
    1087             :   // determined to be a rounding issue with pari/gp as it begins to use a
    1088             :   // floating point representation after 192 bits. There are no discrepancies
    1089             :   // between this algorithm and pari/gp for bit widths < 192 bits.
    1090           0 :   APInt square(x_old * x_old);
    1091           0 :   APInt nextSquare((x_old + 1) * (x_old +1));
    1092           0 :   if (this->ult(square))
    1093             :     return x_old;
    1094             :   assert(this->ule(nextSquare) && "Error in APInt::sqrt computation");
    1095           0 :   APInt midpoint((nextSquare - square).udiv(two));
    1096           0 :   APInt offset(*this - square);
    1097           0 :   if (offset.ult(midpoint))
    1098             :     return x_old;
    1099           0 :   return x_old + 1;
    1100             : }
    1101             : 
    1102             : /// Computes the multiplicative inverse of this APInt for a given modulo. The
    1103             : /// iterative extended Euclidean algorithm is used to solve for this value,
    1104             : /// however we simplify it to speed up calculating only the inverse, and take
    1105             : /// advantage of div+rem calculations. We also use some tricks to avoid copying
    1106             : /// (potentially large) APInts around.
    1107        2325 : APInt APInt::multiplicativeInverse(const APInt& modulo) const {
    1108             :   assert(ult(modulo) && "This APInt must be smaller than the modulo");
    1109             : 
    1110             :   // Using the properties listed at the following web page (accessed 06/21/08):
    1111             :   //   http://www.numbertheory.org/php/euclid.html
    1112             :   // (especially the properties numbered 3, 4 and 9) it can be proved that
    1113             :   // BitWidth bits suffice for all the computations in the algorithm implemented
    1114             :   // below. More precisely, this number of bits suffice if the multiplicative
    1115             :   // inverse exists, but may not suffice for the general extended Euclidean
    1116             :   // algorithm.
    1117             : 
    1118        6975 :   APInt r[2] = { modulo, *this };
    1119       11625 :   APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) };
    1120        2325 :   APInt q(BitWidth, 0);
    1121             : 
    1122             :   unsigned i;
    1123       16257 :   for (i = 0; r[i^1] != 0; i ^= 1) {
    1124             :     // An overview of the math without the confusing bit-flipping:
    1125             :     // q = r[i-2] / r[i-1]
    1126             :     // r[i] = r[i-2] % r[i-1]
    1127             :     // t[i] = t[i-2] - t[i-1] * q
    1128        3869 :     udivrem(r[i], r[i^1], q, r[i]);
    1129        7738 :     t[i] -= t[i^1] * q;
    1130             :   }
    1131             : 
    1132             :   // If this APInt and the modulo are not coprime, there is no multiplicative
    1133             :   // inverse, so return 0. We check this by looking at the next-to-last
    1134             :   // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean
    1135             :   // algorithm.
    1136        4650 :   if (r[i] != 1)
    1137           0 :     return APInt(BitWidth, 0);
    1138             : 
    1139             :   // The next-to-last t is the multiplicative inverse.  However, we are
    1140             :   // interested in a positive inverse. Calculate a positive one from a negative
    1141             :   // one if necessary. A simple addition of the modulo suffices because
    1142             :   // abs(t[i]) is known to be less than *this/2 (see the link above).
    1143        4650 :   if (t[i].isNegative())
    1144         464 :     t[i] += modulo;
    1145             : 
    1146             :   return std::move(t[i]);
    1147             : }
    1148             : 
    1149             : /// Calculate the magic numbers required to implement a signed integer division
    1150             : /// by a constant as a sequence of multiplies, adds and shifts.  Requires that
    1151             : /// the divisor not be 0, 1, or -1.  Taken from "Hacker's Delight", Henry S.
    1152             : /// Warren, Jr., chapter 10.
    1153         360 : APInt::ms APInt::magic() const {
    1154             :   const APInt& d = *this;
    1155             :   unsigned p;
    1156             :   APInt ad, anc, delta, q1, r1, q2, r2, t;
    1157         360 :   APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
    1158             :   struct ms mag;
    1159             : 
    1160         720 :   ad = d.abs();
    1161         720 :   t = signedMin + (d.lshr(d.getBitWidth() - 1));
    1162        2160 :   anc = t - 1 - t.urem(ad);   // absolute value of nc
    1163         360 :   p = d.getBitWidth() - 1;    // initialize p
    1164         720 :   q1 = signedMin.udiv(anc);   // initialize q1 = 2p/abs(nc)
    1165        1080 :   r1 = signedMin - q1*anc;    // initialize r1 = rem(2p,abs(nc))
    1166         720 :   q2 = signedMin.udiv(ad);    // initialize q2 = 2p/abs(d)
    1167        1080 :   r2 = signedMin - q2*ad;     // initialize r2 = rem(2p,abs(d))
    1168             :   do {
    1169        1673 :     p = p + 1;
    1170        1673 :     q1 = q1<<1;          // update q1 = 2p/abs(nc)
    1171        1673 :     r1 = r1<<1;          // update r1 = rem(2p/abs(nc))
    1172        1673 :     if (r1.uge(anc)) {  // must be unsigned comparison
    1173           1 :       q1 = q1 + 1;
    1174           1 :       r1 = r1 - anc;
    1175             :     }
    1176        1673 :     q2 = q2<<1;          // update q2 = 2p/abs(d)
    1177        1673 :     r2 = r2<<1;          // update r2 = rem(2p/abs(d))
    1178        1673 :     if (r2.uge(ad)) {   // must be unsigned comparison
    1179         681 :       q2 = q2 + 1;
    1180         681 :       r2 = r2 - ad;
    1181             :     }
    1182        1673 :     delta = ad - r2;
    1183        2033 :   } while (q1.ult(delta) || (q1 == delta && r1 == 0));
    1184             : 
    1185         720 :   mag.m = q2 + 1;
    1186         734 :   if (d.isNegative()) mag.m = -mag.m;   // resulting magic number
    1187         360 :   mag.s = p - d.getBitWidth();          // resulting shift
    1188         360 :   return mag;
    1189             : }
    1190             : 
    1191             : /// Calculate the magic numbers required to implement an unsigned integer
    1192             : /// division by a constant as a sequence of multiplies, adds and shifts.
    1193             : /// Requires that the divisor not be 0.  Taken from "Hacker's Delight", Henry
    1194             : /// S. Warren, Jr., chapter 10.
    1195             : /// LeadingZeros can be used to simplify the calculation if the upper bits
    1196             : /// of the divided value are known zero.
    1197         527 : APInt::mu APInt::magicu(unsigned LeadingZeros) const {
    1198             :   const APInt& d = *this;
    1199             :   unsigned p;
    1200             :   APInt nc, delta, q1, r1, q2, r2;
    1201             :   struct mu magu;
    1202         527 :   magu.a = 0;               // initialize "add" indicator
    1203        1054 :   APInt allOnes = APInt::getAllOnesValue(d.getBitWidth()).lshr(LeadingZeros);
    1204         527 :   APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
    1205         527 :   APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());
    1206             : 
    1207        2635 :   nc = allOnes - (allOnes - d).urem(d);
    1208         527 :   p = d.getBitWidth() - 1;  // initialize p
    1209        1054 :   q1 = signedMin.udiv(nc);  // initialize q1 = 2p/nc
    1210        1581 :   r1 = signedMin - q1*nc;   // initialize r1 = rem(2p,nc)
    1211        1054 :   q2 = signedMax.udiv(d);   // initialize q2 = (2p-1)/d
    1212        1581 :   r2 = signedMax - q2*d;    // initialize r2 = rem((2p-1),d)
    1213             :   do {
    1214        3722 :     p = p + 1;
    1215        7444 :     if (r1.uge(nc - r1)) {
    1216        1330 :       q1 = q1 + q1 + 1;  // update q1
    1217        1330 :       r1 = r1 + r1 - nc; // update r1
    1218             :     }
    1219             :     else {
    1220        3057 :       q1 = q1+q1; // update q1
    1221        3057 :       r1 = r1+r1; // update r1
    1222             :     }
    1223       14888 :     if ((r2 + 1).uge(d - r2)) {
    1224        1518 :       if (q2.uge(signedMax)) magu.a = 1;
    1225        3036 :       q2 = q2+q2 + 1;     // update q2
    1226        4554 :       r2 = r2+r2 + 1 - d; // update r2
    1227             :     }
    1228             :     else {
    1229        2204 :       if (q2.uge(signedMin)) magu.a = 1;
    1230        2204 :       q2 = q2+q2;     // update q2
    1231        4408 :       r2 = r2+r2 + 1; // update r2
    1232             :     }
    1233        7444 :     delta = d - 1 - r2;
    1234        7444 :   } while (p < d.getBitWidth()*2 &&
    1235         527 :            (q1.ult(delta) || (q1 == delta && r1 == 0)));
    1236         527 :   magu.m = q2 + 1; // resulting magic number
    1237         527 :   magu.s = p - d.getBitWidth();  // resulting shift
    1238         527 :   return magu;
    1239             : }
    1240             : 
    1241             : /// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
    1242             : /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
    1243             : /// variables here have the same names as in the algorithm. Comments explain
    1244             : /// the algorithm and any deviation from it.
    1245        2704 : static void KnuthDiv(uint32_t *u, uint32_t *v, uint32_t *q, uint32_t* r,
    1246             :                      unsigned m, unsigned n) {
    1247             :   assert(u && "Must provide dividend");
    1248             :   assert(v && "Must provide divisor");
    1249             :   assert(q && "Must provide quotient");
    1250             :   assert(u != v && u != q && v != q && "Must use different memory");
    1251             :   assert(n>1 && "n must be > 1");
    1252             : 
    1253             :   // b denotes the base of the number system. In our case b is 2^32.
    1254             :   const uint64_t b = uint64_t(1) << 32;
    1255             : 
    1256             : // The DEBUG macros here tend to be spam in the debug output if you're not
    1257             : // debugging this code. Disable them unless KNUTH_DEBUG is defined.
    1258             : #pragma push_macro("DEBUG")
    1259             : #ifndef KNUTH_DEBUG
    1260             : #undef DEBUG
    1261             : #define DEBUG(X) do {} while (false)
    1262             : #endif
    1263             : 
    1264             :   DEBUG(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n');
    1265             :   DEBUG(dbgs() << "KnuthDiv: original:");
    1266             :   DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
    1267             :   DEBUG(dbgs() << " by");
    1268             :   DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
    1269             :   DEBUG(dbgs() << '\n');
    1270             :   // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of
    1271             :   // u and v by d. Note that we have taken Knuth's advice here to use a power
    1272             :   // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
    1273             :   // 2 allows us to shift instead of multiply and it is easy to determine the
    1274             :   // shift amount from the leading zeros.  We are basically normalizing the u
    1275             :   // and v so that its high bits are shifted to the top of v's range without
    1276             :   // overflow. Note that this can require an extra word in u so that u must
    1277             :   // be of length m+n+1.
    1278        5408 :   unsigned shift = countLeadingZeros(v[n-1]);
    1279             :   uint32_t v_carry = 0;
    1280             :   uint32_t u_carry = 0;
    1281        2704 :   if (shift) {
    1282       54384 :     for (unsigned i = 0; i < m+n; ++i) {
    1283       25938 :       uint32_t u_tmp = u[i] >> (32 - shift);
    1284       25938 :       u[i] = (u[i] << shift) | u_carry;
    1285             :       u_carry = u_tmp;
    1286             :     }
    1287       46072 :     for (unsigned i = 0; i < n; ++i) {
    1288       21782 :       uint32_t v_tmp = v[i] >> (32 - shift);
    1289       21782 :       v[i] = (v[i] << shift) | v_carry;
    1290             :       v_carry = v_tmp;
    1291             :     }
    1292             :   }
    1293        2704 :   u[m+n] = u_carry;
    1294             : 
    1295             :   DEBUG(dbgs() << "KnuthDiv:   normal:");
    1296             :   DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
    1297             :   DEBUG(dbgs() << " by");
    1298             :   DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
    1299             :   DEBUG(dbgs() << '\n');
    1300             : 
    1301             :   // D2. [Initialize j.]  Set j to m. This is the loop counter over the places.
    1302        2704 :   int j = m;
    1303             :   do {
    1304             :     DEBUG(dbgs() << "KnuthDiv: quotient digit #" << j << '\n');
    1305             :     // D3. [Calculate q'.].
    1306             :     //     Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
    1307             :     //     Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
    1308             :     // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
    1309             :     // qp by 1, increase rp by v[n-1], and repeat this test if rp < b. The test
    1310             :     // on v[n-2] determines at high speed most of the cases in which the trial
    1311             :     // value qp is one too large, and it eliminates all cases where qp is two
    1312             :     // too large.
    1313        7022 :     uint64_t dividend = Make_64(u[j+n], u[j+n-1]);
    1314             :     DEBUG(dbgs() << "KnuthDiv: dividend == " << dividend << '\n');
    1315        7022 :     uint64_t qp = dividend / v[n-1];
    1316        7022 :     uint64_t rp = dividend % v[n-1];
    1317        7022 :     if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
    1318         650 :       qp--;
    1319         650 :       rp += v[n-1];
    1320         650 :       if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
    1321         161 :         qp--;
    1322             :     }
    1323             :     DEBUG(dbgs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
    1324             : 
    1325             :     // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
    1326             :     // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
    1327             :     // consists of a simple multiplication by a one-place number, combined with
    1328             :     // a subtraction.
    1329             :     // The digits (u[j+n]...u[j]) should be kept positive; if the result of
    1330             :     // this step is actually negative, (u[j+n]...u[j]) should be left as the
    1331             :     // true value plus b**(n+1), namely as the b's complement of
    1332             :     // the true value, and a "borrow" to the left should be remembered.
    1333             :     int64_t borrow = 0;
    1334      239670 :     for (unsigned i = 0; i < n; ++i) {
    1335      116324 :       uint64_t p = uint64_t(qp) * uint64_t(v[i]);
    1336      116324 :       int64_t subres = int64_t(u[j+i]) - borrow - Lo_32(p);
    1337      232648 :       u[j+i] = Lo_32(subres);
    1338      116324 :       borrow = Hi_32(p) - Hi_32(subres);
    1339             :       DEBUG(dbgs() << "KnuthDiv: u[j+i] = " << u[j+i]
    1340             :                    << ", borrow = " << borrow << '\n');
    1341             :     }
    1342        7022 :     bool isNeg = u[j+n] < borrow;
    1343        7022 :     u[j+n] -= Lo_32(borrow);
    1344             : 
    1345             :     DEBUG(dbgs() << "KnuthDiv: after subtraction:");
    1346             :     DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
    1347             :     DEBUG(dbgs() << '\n');
    1348             : 
    1349             :     // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
    1350             :     // negative, go to step D6; otherwise go on to step D7.
    1351       14044 :     q[j] = Lo_32(qp);
    1352        7022 :     if (isNeg) {
    1353             :       // D6. [Add back]. The probability that this step is necessary is very
    1354             :       // small, on the order of only 2/b. Make sure that test data accounts for
    1355             :       // this possibility. Decrease q[j] by 1
    1356          48 :       q[j]--;
    1357             :       // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
    1358             :       // A carry will occur to the left of u[j+n], and it should be ignored
    1359             :       // since it cancels with the borrow that occurred in D4.
    1360             :       bool carry = false;
    1361         864 :       for (unsigned i = 0; i < n; i++) {
    1362         816 :         uint32_t limit = std::min(u[j+i],v[i]);
    1363         408 :         u[j+i] += v[i] + carry;
    1364         408 :         carry = u[j+i] < limit || (carry && u[j+i] == limit);
    1365             :       }
    1366          48 :       u[j+n] += carry;
    1367             :     }
    1368             :     DEBUG(dbgs() << "KnuthDiv: after correction:");
    1369             :     DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
    1370             :     DEBUG(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n');
    1371             : 
    1372             :   // D7. [Loop on j.]  Decrease j by one. Now if j >= 0, go back to D3.
    1373        7022 :   } while (--j >= 0);
    1374             : 
    1375             :   DEBUG(dbgs() << "KnuthDiv: quotient:");
    1376             :   DEBUG(for (int i = m; i >=0; i--) dbgs() <<" " << q[i]);
    1377             :   DEBUG(dbgs() << '\n');
    1378             : 
    1379             :   // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
    1380             :   // remainder may be obtained by dividing u[...] by d. If r is non-null we
    1381             :   // compute the remainder (urem uses this).
    1382        2704 :   if (r) {
    1383             :     // The value d is expressed by the "shift" value above since we avoided
    1384             :     // multiplication by d by using a shift left. So, all we have to do is
    1385             :     // shift right here.
    1386          50 :     if (shift) {
    1387             :       uint32_t carry = 0;
    1388             :       DEBUG(dbgs() << "KnuthDiv: remainder:");
    1389         856 :       for (int i = n-1; i >= 0; i--) {
    1390         816 :         r[i] = (u[i] >> shift) | carry;
    1391         816 :         carry = u[i] << (32 - shift);
    1392             :         DEBUG(dbgs() << " " << r[i]);
    1393             :       }
    1394             :     } else {
    1395          38 :       for (int i = n-1; i >= 0; i--) {
    1396          28 :         r[i] = u[i];
    1397             :         DEBUG(dbgs() << " " << r[i]);
    1398             :       }
    1399             :     }
    1400             :     DEBUG(dbgs() << '\n');
    1401             :   }
    1402             :   DEBUG(dbgs() << '\n');
    1403             : 
    1404             : #pragma pop_macro("DEBUG")
    1405        2704 : }
    1406             : 
    1407       50984 : void APInt::divide(const WordType *LHS, unsigned lhsWords, const WordType *RHS,
    1408             :                    unsigned rhsWords, WordType *Quotient, WordType *Remainder) {
    1409             :   assert(lhsWords >= rhsWords && "Fractional result");
    1410             : 
    1411             :   // First, compose the values into an array of 32-bit words instead of
    1412             :   // 64-bit words. This is a necessity of both the "short division" algorithm
    1413             :   // and the Knuth "classical algorithm" which requires there to be native
    1414             :   // operations for +, -, and * on an m bit value with an m*2 bit result. We
    1415             :   // can't use 64-bit operands here because we don't have native results of
    1416             :   // 128-bits. Furthermore, casting the 64-bit values to 32-bit values won't
    1417             :   // work on large-endian machines.
    1418       50984 :   unsigned n = rhsWords * 2;
    1419       50984 :   unsigned m = (lhsWords * 2) - n;
    1420             : 
    1421             :   // Allocate space for the temporary values we need either on the stack, if
    1422             :   // it will fit, or on the heap if it won't.
    1423             :   uint32_t SPACE[128];
    1424             :   uint32_t *U = nullptr;
    1425             :   uint32_t *V = nullptr;
    1426             :   uint32_t *Q = nullptr;
    1427             :   uint32_t *R = nullptr;
    1428       50984 :   if ((Remainder?4:3)*n+2*m+1 <= 128) {
    1429             :     U = &SPACE[0];
    1430       50784 :     V = &SPACE[m+n+1];
    1431       50784 :     Q = &SPACE[(m+n+1) + n];
    1432       50784 :     if (Remainder)
    1433       45171 :       R = &SPACE[(m+n+1) + n + (m+n)];
    1434             :   } else {
    1435         200 :     U = new uint32_t[m + n + 1];
    1436         200 :     V = new uint32_t[n];
    1437         200 :     Q = new uint32_t[m+n];
    1438         200 :     if (Remainder)
    1439           8 :       R = new uint32_t[n];
    1440             :   }
    1441             : 
    1442             :   // Initialize the dividend
    1443       50984 :   memset(U, 0, (m+n+1)*sizeof(uint32_t));
    1444      275784 :   for (unsigned i = 0; i < lhsWords; ++i) {
    1445      112400 :     uint64_t tmp = LHS[i];
    1446      224800 :     U[i * 2] = Lo_32(tmp);
    1447      224800 :     U[i * 2 + 1] = Hi_32(tmp);
    1448             :   }
    1449       50984 :   U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
    1450             : 
    1451             :   // Initialize the divisor
    1452       50984 :   memset(V, 0, (n)*sizeof(uint32_t));
    1453      173920 :   for (unsigned i = 0; i < rhsWords; ++i) {
    1454       61468 :     uint64_t tmp = RHS[i];
    1455      122936 :     V[i * 2] = Lo_32(tmp);
    1456      122936 :     V[i * 2 + 1] = Hi_32(tmp);
    1457             :   }
    1458             : 
    1459             :   // initialize the quotient and remainder
    1460       50984 :   memset(Q, 0, (m+n) * sizeof(uint32_t));
    1461       50984 :   if (Remainder)
    1462       45179 :     memset(R, 0, n * sizeof(uint32_t));
    1463             : 
    1464             :   // Now, adjust m and n for the Knuth division. n is the number of words in
    1465             :   // the divisor. m is the number of words by which the dividend exceeds the
    1466             :   // divisor (i.e. m+n is the length of the dividend). These sizes must not
    1467             :   // contain any zero words or the Knuth algorithm fails.
    1468      149030 :   for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
    1469             :     n--;
    1470       49023 :     m++;
    1471             :   }
    1472       74676 :   for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
    1473       23692 :     m--;
    1474             : 
    1475             :   // If we're left with only a single word for the divisor, Knuth doesn't work
    1476             :   // so we implement the short division algorithm here. This is much simpler
    1477             :   // and faster because we are certain that we can divide a 64-bit quantity
    1478             :   // by a 32-bit quantity at hardware speed and short division is simply a
    1479             :   // series of such operations. This is just like doing short division but we
    1480             :   // are using base 2^32 instead of base 10.
    1481             :   assert(n != 0 && "Divide by zero?");
    1482       50984 :   if (n == 1) {
    1483       48280 :     uint32_t divisor = V[0];
    1484             :     uint32_t remainder = 0;
    1485      219437 :     for (int i = m; i >= 0; i--) {
    1486      171157 :       uint64_t partial_dividend = Make_64(remainder, U[i]);
    1487      171157 :       if (partial_dividend == 0) {
    1488         300 :         Q[i] = 0;
    1489             :         remainder = 0;
    1490      170857 :       } else if (partial_dividend < divisor) {
    1491        4989 :         Q[i] = 0;
    1492             :         remainder = Lo_32(partial_dividend);
    1493      165868 :       } else if (partial_dividend == divisor) {
    1494          19 :         Q[i] = 1;
    1495             :         remainder = 0;
    1496             :       } else {
    1497      331698 :         Q[i] = Lo_32(partial_dividend / divisor);
    1498      165849 :         remainder = Lo_32(partial_dividend - (Q[i] * divisor));
    1499             :       }
    1500             :     }
    1501       48280 :     if (R)
    1502       45129 :       R[0] = remainder;
    1503             :   } else {
    1504             :     // Now we're ready to invoke the Knuth classical divide algorithm. In this
    1505             :     // case n > 1.
    1506        2704 :     KnuthDiv(U, V, Q, R, m, n);
    1507             :   }
    1508             : 
    1509             :   // If the caller wants the quotient
    1510       50984 :   if (Quotient) {
    1511      274846 :     for (unsigned i = 0; i < lhsWords; ++i)
    1512      223892 :       Quotient[i] = Make_64(Q[i*2+1], Q[i*2]);
    1513             :   }
    1514             : 
    1515             :   // If the caller wants the remainder
    1516       50984 :   if (Remainder) {
    1517      136313 :     for (unsigned i = 0; i < rhsWords; ++i)
    1518       91134 :       Remainder[i] = Make_64(R[i*2+1], R[i*2]);
    1519             :   }
    1520             : 
    1521             :   // Clean up the memory we allocated.
    1522       50984 :   if (U != &SPACE[0]) {
    1523         200 :     delete [] U;
    1524         200 :     delete [] V;
    1525         200 :     delete [] Q;
    1526         200 :     delete [] R;
    1527             :   }
    1528       50984 : }
    1529             : 
    1530    20803368 : APInt APInt::udiv(const APInt &RHS) const {
    1531             :   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
    1532             : 
    1533             :   // First, deal with the easy case
    1534    20803368 :   if (isSingleWord()) {
    1535             :     assert(RHS.U.VAL != 0 && "Divide by zero?");
    1536    20780709 :     return APInt(BitWidth, U.VAL / RHS.U.VAL);
    1537             :   }
    1538             : 
    1539             :   // Get some facts about the LHS and RHS number of bits and words
    1540             :   unsigned lhsWords = getNumWords(getActiveBits());
    1541             :   unsigned rhsBits  = RHS.getActiveBits();
    1542             :   unsigned rhsWords = getNumWords(rhsBits);
    1543             :   assert(rhsWords && "Divided by zero???");
    1544             : 
    1545             :   // Deal with some degenerate cases
    1546       22659 :   if (!lhsWords)
    1547             :     // 0 / X ===> 0
    1548             :     return APInt(BitWidth, 0);
    1549       21263 :   if (rhsBits == 1)
    1550             :     // X / 1 ===> X
    1551             :     return *this;
    1552       25534 :   if (lhsWords < rhsWords || this->ult(RHS))
    1553             :     // X / Y ===> 0, iff X < Y
    1554             :     return APInt(BitWidth, 0);
    1555       11901 :   if (*this == RHS)
    1556             :     // X / X ===> 1
    1557             :     return APInt(BitWidth, 1);
    1558       11042 :   if (lhsWords == 1) // rhsWords is 1 if lhsWords is 1.
    1559             :     // All high words are zero, just use native divide
    1560        5239 :     return APInt(BitWidth, this->U.pVal[0] / RHS.U.pVal[0]);
    1561             : 
    1562             :   // We have to compute it the hard way. Invoke the Knuth divide algorithm.
    1563             :   APInt Quotient(BitWidth, 0); // to hold result.
    1564        5803 :   divide(U.pVal, lhsWords, RHS.U.pVal, rhsWords, Quotient.U.pVal, nullptr);
    1565             :   return Quotient;
    1566             : }
    1567             : 
    1568           8 : APInt APInt::udiv(uint64_t RHS) const {
    1569             :   assert(RHS != 0 && "Divide by zero?");
    1570             : 
    1571             :   // First, deal with the easy case
    1572           8 :   if (isSingleWord())
    1573           3 :     return APInt(BitWidth, U.VAL / RHS);
    1574             : 
    1575             :   // Get some facts about the LHS words.
    1576             :   unsigned lhsWords = getNumWords(getActiveBits());
    1577             : 
    1578             :   // Deal with some degenerate cases
    1579           5 :   if (!lhsWords)
    1580             :     // 0 / X ===> 0
    1581             :     return APInt(BitWidth, 0);
    1582           5 :   if (RHS == 1)
    1583             :     // X / 1 ===> X
    1584             :     return *this;
    1585           5 :   if (this->ult(RHS))
    1586             :     // X / Y ===> 0, iff X < Y
    1587             :     return APInt(BitWidth, 0);
    1588           5 :   if (*this == RHS)
    1589             :     // X / X ===> 1
    1590             :     return APInt(BitWidth, 1);
    1591           5 :   if (lhsWords == 1) // rhsWords is 1 if lhsWords is 1.
    1592             :     // All high words are zero, just use native divide
    1593           3 :     return APInt(BitWidth, this->U.pVal[0] / RHS);
    1594             : 
    1595             :   // We have to compute it the hard way. Invoke the Knuth divide algorithm.
    1596             :   APInt Quotient(BitWidth, 0); // to hold result.
    1597           2 :   divide(U.pVal, lhsWords, &RHS, 1, Quotient.U.pVal, nullptr);
    1598             :   return Quotient;
    1599             : }
    1600             : 
    1601    20426892 : APInt APInt::sdiv(const APInt &RHS) const {
    1602    40853784 :   if (isNegative()) {
    1603       10718 :     if (RHS.isNegative())
    1604        2580 :       return (-(*this)).udiv(-RHS);
    1605       19372 :     return -((-(*this)).udiv(RHS));
    1606             :   }
    1607    40843066 :   if (RHS.isNegative())
    1608        6636 :     return -(this->udiv(-RHS));
    1609    20419874 :   return this->udiv(RHS);
    1610             : }
    1611             : 
    1612           5 : APInt APInt::sdiv(int64_t RHS) const {
    1613          10 :   if (isNegative()) {
    1614           2 :     if (RHS < 0)
    1615           0 :       return (-(*this)).udiv(-RHS);
    1616           8 :     return -((-(*this)).udiv(RHS));
    1617             :   }
    1618           3 :   if (RHS < 0)
    1619           0 :     return -(this->udiv(-RHS));
    1620           3 :   return this->udiv(RHS);
    1621             : }
    1622             : 
    1623      222280 : APInt APInt::urem(const APInt &RHS) const {
    1624             :   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
    1625      222280 :   if (isSingleWord()) {
    1626             :     assert(RHS.U.VAL != 0 && "Remainder by zero?");
    1627      222247 :     return APInt(BitWidth, U.VAL % RHS.U.VAL);
    1628             :   }
    1629             : 
    1630             :   // Get some facts about the LHS
    1631             :   unsigned lhsWords = getNumWords(getActiveBits());
    1632             : 
    1633             :   // Get some facts about the RHS
    1634             :   unsigned rhsBits = RHS.getActiveBits();
    1635             :   unsigned rhsWords = getNumWords(rhsBits);
    1636             :   assert(rhsWords && "Performing remainder operation by zero ???");
    1637             : 
    1638             :   // Check the degenerate cases
    1639          33 :   if (lhsWords == 0)
    1640             :     // 0 % Y ===> 0
    1641             :     return APInt(BitWidth, 0);
    1642          29 :   if (rhsBits == 1)
    1643             :     // X % 1 ===> 0
    1644             :     return APInt(BitWidth, 0);
    1645          58 :   if (lhsWords < rhsWords || this->ult(RHS))
    1646             :     // X % Y ===> X, iff X < Y
    1647             :     return *this;
    1648          29 :   if (*this == RHS)
    1649             :     // X % X == 0;
    1650             :     return APInt(BitWidth, 0);
    1651          29 :   if (lhsWords == 1)
    1652             :     // All high words are zero, just use native remainder
    1653           1 :     return APInt(BitWidth, U.pVal[0] % RHS.U.pVal[0]);
    1654             : 
    1655             :   // We have to compute it the hard way. Invoke the Knuth divide algorithm.
    1656             :   APInt Remainder(BitWidth, 0);
    1657          28 :   divide(U.pVal, lhsWords, RHS.U.pVal, rhsWords, nullptr, Remainder.U.pVal);
    1658             :   return Remainder;
    1659             : }
    1660             : 
    1661         131 : uint64_t APInt::urem(uint64_t RHS) const {
    1662             :   assert(RHS != 0 && "Remainder by zero?");
    1663             : 
    1664         131 :   if (isSingleWord())
    1665         126 :     return U.VAL % RHS;
    1666             : 
    1667             :   // Get some facts about the LHS
    1668             :   unsigned lhsWords = getNumWords(getActiveBits());
    1669             : 
    1670             :   // Check the degenerate cases
    1671           5 :   if (lhsWords == 0)
    1672             :     // 0 % Y ===> 0
    1673             :     return 0;
    1674           5 :   if (RHS == 1)
    1675             :     // X % 1 ===> 0
    1676             :     return 0;
    1677           5 :   if (this->ult(RHS))
    1678             :     // X % Y ===> X, iff X < Y
    1679           0 :     return getZExtValue();
    1680           5 :   if (*this == RHS)
    1681             :     // X % X == 0;
    1682             :     return 0;
    1683           5 :   if (lhsWords == 1)
    1684             :     // All high words are zero, just use native remainder
    1685           3 :     return U.pVal[0] % RHS;
    1686             : 
    1687             :   // We have to compute it the hard way. Invoke the Knuth divide algorithm.
    1688             :   uint64_t Remainder;
    1689           2 :   divide(U.pVal, lhsWords, &RHS, 1, nullptr, &Remainder);
    1690           2 :   return Remainder;
    1691             : }
    1692             : 
    1693       19257 : APInt APInt::srem(const APInt &RHS) const {
    1694       38514 :   if (isNegative()) {
    1695        9184 :     if (RHS.isNegative())
    1696        2682 :       return -((-(*this)).urem(-RHS));
    1697       16580 :     return -((-(*this)).urem(RHS));
    1698             :   }
    1699       29330 :   if (RHS.isNegative())
    1700        5118 :     return this->urem(-RHS);
    1701       12959 :   return this->urem(RHS);
    1702             : }
    1703             : 
    1704           5 : int64_t APInt::srem(int64_t RHS) const {
    1705          10 :   if (isNegative()) {
    1706           2 :     if (RHS < 0)
    1707           0 :       return -((-(*this)).urem(-RHS));
    1708           6 :     return -((-(*this)).urem(RHS));
    1709             :   }
    1710           3 :   if (RHS < 0)
    1711           0 :     return this->urem(-RHS);
    1712           3 :   return this->urem(RHS);
    1713             : }
    1714             : 
    1715       92715 : void APInt::udivrem(const APInt &LHS, const APInt &RHS,
    1716             :                     APInt &Quotient, APInt &Remainder) {
    1717             :   assert(LHS.BitWidth == RHS.BitWidth && "Bit widths must be the same");
    1718       92715 :   unsigned BitWidth = LHS.BitWidth;
    1719             : 
    1720             :   // First, deal with the easy case
    1721       92715 :   if (LHS.isSingleWord()) {
    1722             :     assert(RHS.U.VAL != 0 && "Divide by zero?");
    1723       90075 :     uint64_t QuotVal = LHS.U.VAL / RHS.U.VAL;
    1724       90075 :     uint64_t RemVal = LHS.U.VAL % RHS.U.VAL;
    1725       90075 :     Quotient = APInt(BitWidth, QuotVal);
    1726       90075 :     Remainder = APInt(BitWidth, RemVal);
    1727       90075 :     return;
    1728             :   }
    1729             : 
    1730             :   // Get some size facts about the dividend and divisor
    1731             :   unsigned lhsWords = getNumWords(LHS.getActiveBits());
    1732             :   unsigned rhsBits  = RHS.getActiveBits();
    1733             :   unsigned rhsWords = getNumWords(rhsBits);
    1734             :   assert(rhsWords && "Performing divrem operation by zero ???");
    1735             : 
    1736             :   // Check the degenerate cases
    1737        2640 :   if (lhsWords == 0) {
    1738           0 :     Quotient = 0;                // 0 / Y ===> 0
    1739           0 :     Remainder = 0;               // 0 % Y ===> 0
    1740           0 :     return;
    1741             :   }
    1742             : 
    1743        2640 :   if (rhsBits == 1) {
    1744         168 :     Quotient = LHS;             // X / 1 ===> X
    1745         168 :     Remainder = 0;              // X % 1 ===> 0
    1746             :   }
    1747             : 
    1748        5280 :   if (lhsWords < rhsWords || LHS.ult(RHS)) {
    1749         383 :     Remainder = LHS;            // X % Y ===> X, iff X < Y
    1750         383 :     Quotient = 0;               // X / Y ===> 0, iff X < Y
    1751         383 :     return;
    1752             :   }
    1753             : 
    1754        2257 :   if (LHS == RHS) {
    1755          11 :     Quotient  = 1;              // X / X ===> 1
    1756          11 :     Remainder = 0;              // X % X ===> 0;
    1757          11 :     return;
    1758             :   }
    1759             : 
    1760             :   // Make sure there is enough space to hold the results.
    1761             :   // NOTE: This assumes that reallocate won't affect any bits if it doesn't
    1762             :   // change the size. This is necessary if Quotient or Remainder is aliased
    1763             :   // with LHS or RHS.
    1764        2246 :   Quotient.reallocate(BitWidth);
    1765        2246 :   Remainder.reallocate(BitWidth);
    1766             : 
    1767        2246 :   if (lhsWords == 1) { // rhsWords is 1 if lhsWords is 1.
    1768             :     // There is only one word to consider so use the native versions.
    1769        1987 :     uint64_t lhsValue = LHS.U.pVal[0];
    1770        1987 :     uint64_t rhsValue = RHS.U.pVal[0];
    1771        1987 :     Quotient = lhsValue / rhsValue;
    1772        1987 :     Remainder = lhsValue % rhsValue;
    1773        1987 :     return;
    1774             :   }
    1775             : 
    1776             :   // Okay, lets do it the long way
    1777         259 :   divide(LHS.U.pVal, lhsWords, RHS.U.pVal, rhsWords, Quotient.U.pVal,
    1778             :          Remainder.U.pVal);
    1779             :   // Clear the rest of the Quotient and Remainder.
    1780         259 :   std::memset(Quotient.U.pVal + lhsWords, 0,
    1781         259 :               (getNumWords(BitWidth) - lhsWords) * APINT_WORD_SIZE);
    1782         259 :   std::memset(Remainder.U.pVal + rhsWords, 0,
    1783         259 :               (getNumWords(BitWidth) - rhsWords) * APINT_WORD_SIZE);
    1784             : }
    1785             : 
    1786       92275 : void APInt::udivrem(const APInt &LHS, uint64_t RHS, APInt &Quotient,
    1787             :                     uint64_t &Remainder) {
    1788             :   assert(RHS != 0 && "Divide by zero?");
    1789       92275 :   unsigned BitWidth = LHS.BitWidth;
    1790             : 
    1791             :   // First, deal with the easy case
    1792       92275 :   if (LHS.isSingleWord()) {
    1793           3 :     uint64_t QuotVal = LHS.U.VAL / RHS;
    1794           3 :     Remainder = LHS.U.VAL % RHS;
    1795           3 :     Quotient = APInt(BitWidth, QuotVal);
    1796           3 :     return;
    1797             :   }
    1798             : 
    1799             :   // Get some size facts about the dividend and divisor
    1800             :   unsigned lhsWords = getNumWords(LHS.getActiveBits());
    1801             : 
    1802             :   // Check the degenerate cases
    1803       92272 :   if (lhsWords == 0) {
    1804           0 :     Quotient = 0;                // 0 / Y ===> 0
    1805           0 :     Remainder = 0;               // 0 % Y ===> 0
    1806           0 :     return;
    1807             :   }
    1808             : 
    1809       92272 :   if (RHS == 1) {
    1810           0 :     Quotient = LHS;             // X / 1 ===> X
    1811           0 :     Remainder = 0;              // X % 1 ===> 0
    1812             :   }
    1813             : 
    1814       92272 :   if (LHS.ult(RHS)) {
    1815        2752 :     Remainder = LHS.getZExtValue(); // X % Y ===> X, iff X < Y
    1816        2752 :     Quotient = 0;                   // X / Y ===> 0, iff X < Y
    1817        2752 :     return;
    1818             :   }
    1819             : 
    1820       89520 :   if (LHS == RHS) {
    1821          26 :     Quotient  = 1;              // X / X ===> 1
    1822          26 :     Remainder = 0;              // X % X ===> 0;
    1823          26 :     return;
    1824             :   }
    1825             : 
    1826             :   // Make sure there is enough space to hold the results.
    1827             :   // NOTE: This assumes that reallocate won't affect any bits if it doesn't
    1828             :   // change the size. This is necessary if Quotient is aliased with LHS.
    1829       89494 :   Quotient.reallocate(BitWidth);
    1830             : 
    1831       89494 :   if (lhsWords == 1) { // rhsWords is 1 if lhsWords is 1.
    1832             :     // There is only one word to consider so use the native versions.
    1833       44604 :     uint64_t lhsValue = LHS.U.pVal[0];
    1834       44604 :     Quotient = lhsValue / RHS;
    1835       44604 :     Remainder = lhsValue % RHS;
    1836       44604 :     return;
    1837             :   }
    1838             : 
    1839             :   // Okay, lets do it the long way
    1840       44890 :   divide(LHS.U.pVal, lhsWords, &RHS, 1, Quotient.U.pVal, &Remainder);
    1841             :   // Clear the rest of the Quotient.
    1842       44890 :   std::memset(Quotient.U.pVal + lhsWords, 0,
    1843       44890 :               (getNumWords(BitWidth) - lhsWords) * APINT_WORD_SIZE);
    1844             : }
    1845             : 
    1846       22030 : void APInt::sdivrem(const APInt &LHS, const APInt &RHS,
    1847             :                     APInt &Quotient, APInt &Remainder) {
    1848       44060 :   if (LHS.isNegative()) {
    1849         364 :     if (RHS.isNegative())
    1850         365 :       APInt::udivrem(-LHS, -RHS, Quotient, Remainder);
    1851             :     else {
    1852         327 :       APInt::udivrem(-LHS, RHS, Quotient, Remainder);
    1853             :       Quotient.negate();
    1854             :     }
    1855             :     Remainder.negate();
    1856       43696 :   } else if (RHS.isNegative()) {
    1857         342 :     APInt::udivrem(LHS, -RHS, Quotient, Remainder);
    1858             :     Quotient.negate();
    1859             :   } else {
    1860       21734 :     APInt::udivrem(LHS, RHS, Quotient, Remainder);
    1861             :   }
    1862       22030 : }
    1863             : 
    1864           5 : void APInt::sdivrem(const APInt &LHS, int64_t RHS,
    1865             :                     APInt &Quotient, int64_t &Remainder) {
    1866           5 :   uint64_t R = Remainder;
    1867          10 :   if (LHS.isNegative()) {
    1868           2 :     if (RHS < 0)
    1869           0 :       APInt::udivrem(-LHS, -RHS, Quotient, R);
    1870             :     else {
    1871           8 :       APInt::udivrem(-LHS, RHS, Quotient, R);
    1872             :       Quotient.negate();
    1873             :     }
    1874           2 :     R = -R;
    1875           3 :   } else if (RHS < 0) {
    1876           0 :     APInt::udivrem(LHS, -RHS, Quotient, R);
    1877             :     Quotient.negate();
    1878             :   } else {
    1879           3 :     APInt::udivrem(LHS, RHS, Quotient, R);
    1880             :   }
    1881           5 :   Remainder = R;
    1882           5 : }
    1883             : 
    1884        9549 : APInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const {
    1885        9549 :   APInt Res = *this+RHS;
    1886       19004 :   Overflow = isNonNegative() == RHS.isNonNegative() &&
    1887             :              Res.isNonNegative() != isNonNegative();
    1888        9549 :   return Res;
    1889             : }
    1890             : 
    1891       75603 : APInt APInt::uadd_ov(const APInt &RHS, bool &Overflow) const {
    1892       75603 :   APInt Res = *this+RHS;
    1893       75603 :   Overflow = Res.ult(RHS);
    1894       75603 :   return Res;
    1895             : }
    1896             : 
    1897       25591 : APInt APInt::ssub_ov(const APInt &RHS, bool &Overflow) const {
    1898       25591 :   APInt Res = *this - RHS;
    1899       25773 :   Overflow = isNonNegative() != RHS.isNonNegative() &&
    1900             :              Res.isNonNegative() != isNonNegative();
    1901       25591 :   return Res;
    1902             : }
    1903             : 
    1904          78 : APInt APInt::usub_ov(const APInt &RHS, bool &Overflow) const {
    1905          78 :   APInt Res = *this-RHS;
    1906          78 :   Overflow = Res.ugt(*this);
    1907          78 :   return Res;
    1908             : }
    1909             : 
    1910    20125322 : APInt APInt::sdiv_ov(const APInt &RHS, bool &Overflow) const {
    1911             :   // MININT/-1  -->  overflow.
    1912    20125322 :   Overflow = isMinSignedValue() && RHS.isAllOnesValue();
    1913    20125322 :   return sdiv(RHS);
    1914             : }
    1915             : 
    1916         240 : APInt APInt::smul_ov(const APInt &RHS, bool &Overflow) const {
    1917         240 :   APInt Res = *this * RHS;
    1918             : 
    1919         480 :   if (*this != 0 && RHS != 0)
    1920        1163 :     Overflow = Res.sdiv(RHS) != *this || Res.sdiv(*this) != RHS;
    1921             :   else
    1922           7 :     Overflow = false;
    1923         240 :   return Res;
    1924             : }
    1925             : 
    1926       13798 : APInt APInt::umul_ov(const APInt &RHS, bool &Overflow) const {
    1927       13798 :   APInt Res = *this * RHS;
    1928             : 
    1929       20899 :   if (*this != 0 && RHS != 0)
    1930       28721 :     Overflow = Res.udiv(RHS) != *this || Res.udiv(*this) != RHS;
    1931             :   else
    1932        6707 :     Overflow = false;
    1933       13798 :   return Res;
    1934             : }
    1935             : 
    1936        8891 : APInt APInt::sshl_ov(const APInt &ShAmt, bool &Overflow) const {
    1937       17782 :   Overflow = ShAmt.uge(getBitWidth());
    1938        8891 :   if (Overflow)
    1939             :     return APInt(BitWidth, 0);
    1940             : 
    1941        8891 :   if (isNonNegative()) // Don't allow sign change.
    1942       17782 :     Overflow = ShAmt.uge(countLeadingZeros());
    1943             :   else
    1944           0 :     Overflow = ShAmt.uge(countLeadingOnes());
    1945             : 
    1946             :   return *this << ShAmt;
    1947             : }
    1948             : 
    1949           5 : APInt APInt::ushl_ov(const APInt &ShAmt, bool &Overflow) const {
    1950          10 :   Overflow = ShAmt.uge(getBitWidth());
    1951           5 :   if (Overflow)
    1952             :     return APInt(BitWidth, 0);
    1953             : 
    1954           5 :   Overflow = ShAmt.ugt(countLeadingZeros());
    1955             : 
    1956             :   return *this << ShAmt;
    1957             : }
    1958             : 
    1959             : 
    1960             : 
    1961             : 
    1962     2875889 : void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) {
    1963             :   // Check our assumptions here
    1964             :   assert(!str.empty() && "Invalid string length");
    1965             :   assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
    1966             :           radix == 36) &&
    1967             :          "Radix should be 2, 8, 10, 16, or 36!");
    1968             : 
    1969             :   StringRef::iterator p = str.begin();
    1970             :   size_t slen = str.size();
    1971     2875889 :   bool isNeg = *p == '-';
    1972     2875889 :   if (*p == '-' || *p == '+') {
    1973       45830 :     p++;
    1974       45830 :     slen--;
    1975             :     assert(slen && "String is only a sign, needs a value.");
    1976             :   }
    1977             :   assert((slen <= numbits || radix != 2) && "Insufficient bit width");
    1978             :   assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width");
    1979             :   assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width");
    1980             :   assert((((slen-1)*64)/22 <= numbits || radix != 10) &&
    1981             :          "Insufficient bit width");
    1982             : 
    1983             :   // Allocate memory if needed
    1984     2875889 :   if (isSingleWord())
    1985     2874668 :     U.VAL = 0;
    1986             :   else
    1987        1221 :     U.pVal = getClearedMemory(getNumWords());
    1988             : 
    1989             :   // Figure out if we can shift instead of multiply
    1990     2875889 :   unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
    1991             : 
    1992             :   // Enter digit traversal loop
    1993    11059535 :   for (StringRef::iterator e = str.end(); p != e; ++p) {
    1994     4091823 :     unsigned digit = getDigit(*p, radix);
    1995             :     assert(digit < radix && "Invalid character in digit string");
    1996             : 
    1997             :     // Shift or multiply the value by the radix
    1998     4091823 :     if (slen > 1) {
    1999     2110494 :       if (shift)
    2000        5734 :         *this <<= shift;
    2001             :       else
    2002     2104760 :         *this *= radix;
    2003             :     }
    2004             : 
    2005             :     // Add in the digit we just interpreted
    2006     4091823 :     *this += digit;
    2007             :   }
    2008             :   // If its negative, put it in two's complement form
    2009     2875889 :   if (isNeg)
    2010             :     this->negate();
    2011     2875889 : }
    2012             : 
    2013     2010036 : void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix,
    2014             :                      bool Signed, bool formatAsCLiteral) const {
    2015             :   assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 ||
    2016             :           Radix == 36) &&
    2017             :          "Radix should be 2, 8, 10, 16, or 36!");
    2018             : 
    2019             :   const char *Prefix = "";
    2020     2010036 :   if (formatAsCLiteral) {
    2021         251 :     switch (Radix) {
    2022           3 :       case 2:
    2023             :         // Binary literals are a non-standard extension added in gcc 4.3:
    2024             :         // http://gcc.gnu.org/onlinedocs/gcc-4.3.0/gcc/Binary-constants.html
    2025             :         Prefix = "0b";
    2026           3 :         break;
    2027           3 :       case 8:
    2028             :         Prefix = "0";
    2029           3 :         break;
    2030             :       case 10:
    2031             :         break; // No prefix
    2032         216 :       case 16:
    2033             :         Prefix = "0x";
    2034         216 :         break;
    2035           0 :       default:
    2036           0 :         llvm_unreachable("Invalid radix!");
    2037             :     }
    2038             :   }
    2039             : 
    2040             :   // First, check for a zero value and just short circuit the logic below.
    2041     2010036 :   if (*this == 0) {
    2042      380271 :     while (*Prefix) {
    2043           5 :       Str.push_back(*Prefix);
    2044           5 :       ++Prefix;
    2045             :     };
    2046      380261 :     Str.push_back('0');
    2047     2387430 :     return;
    2048             :   }
    2049             : 
    2050             :   static const char Digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    2051             : 
    2052     1629775 :   if (isSingleWord()) {
    2053             :     char Buffer[65];
    2054             :     char *BufPtr = std::end(Buffer);
    2055             : 
    2056             :     uint64_t N;
    2057     1626908 :     if (!Signed) {
    2058             :       N = getZExtValue();
    2059             :     } else {
    2060             :       int64_t I = getSExtValue();
    2061     1152433 :       if (I >= 0) {
    2062     1113609 :         N = I;
    2063             :       } else {
    2064       38824 :         Str.push_back('-');
    2065       38824 :         N = -(uint64_t)I;
    2066             :       }
    2067             :     }
    2068             : 
    2069     1627320 :     while (*Prefix) {
    2070         206 :       Str.push_back(*Prefix);
    2071         206 :       ++Prefix;
    2072             :     };
    2073             : 
    2074    27604178 :     while (N) {
    2075    12988635 :       *--BufPtr = Digits[N % Radix];
    2076    12988635 :       N /= Radix;
    2077             :     }
    2078     1626908 :     Str.append(BufPtr, std::end(Buffer));
    2079             :     return;
    2080             :   }
    2081             : 
    2082             :   APInt Tmp(*this);
    2083             : 
    2084        4697 :   if (Signed && isNegative()) {
    2085             :     // They want to print the signed version and it is a negative value
    2086             :     // Flip the bits and add one to turn it into the equivalent positive
    2087             :     // value and put a '-' in the result.
    2088             :     Tmp.negate();
    2089         118 :     Str.push_back('-');
    2090             :   }
    2091             : 
    2092        3327 :   while (*Prefix) {
    2093         230 :     Str.push_back(*Prefix);
    2094         230 :     ++Prefix;
    2095             :   };
    2096             : 
    2097             :   // We insert the digits backward, then reverse them to get the right order.
    2098             :   unsigned StartDig = Str.size();
    2099             : 
    2100             :   // For the 2, 8 and 16 bit cases, we can just shift instead of divide
    2101             :   // because the number of bits per digit (1, 3 and 4 respectively) divides
    2102             :   // equally.  We just shift until the value is zero.
    2103        2867 :   if (Radix == 2 || Radix == 8 || Radix == 16) {
    2104             :     // Just shift tmp right for each digit width until it becomes zero
    2105         115 :     unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
    2106         115 :     unsigned MaskAmt = Radix - 1;
    2107             : 
    2108        1955 :     while (Tmp.getBoolValue()) {
    2109        1840 :       unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;
    2110        1840 :       Str.push_back(Digits[Digit]);
    2111             :       Tmp.lshrInPlace(ShiftAmt);
    2112             :     }
    2113             :   } else {
    2114      187286 :     while (Tmp.getBoolValue()) {
    2115             :       uint64_t Digit;
    2116       92267 :       udivrem(Tmp, Radix, Tmp, Digit);
    2117             :       assert(Digit < Radix && "divide failed");
    2118       92267 :       Str.push_back(Digits[Digit]);
    2119             :     }
    2120             :   }
    2121             : 
    2122             :   // Reverse the digits before returning.
    2123        2867 :   std::reverse(Str.begin()+StartDig, Str.end());
    2124             : }
    2125             : 
    2126             : /// Returns the APInt as a std::string. Note that this is an inefficient method.
    2127             : /// It is better to pass in a SmallVector/SmallString to the methods above.
    2128     1117173 : std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const {
    2129             :   SmallString<40> S;
    2130     1117173 :   toString(S, Radix, Signed, /* formatAsCLiteral = */false);
    2131     1117173 :   return S.str();
    2132             : }
    2133             : 
    2134             : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
    2135             : LLVM_DUMP_METHOD void APInt::dump() const {
    2136             :   SmallString<40> S, U;
    2137             :   this->toStringUnsigned(U);
    2138             :   this->toStringSigned(S);
    2139             :   dbgs() << "APInt(" << BitWidth << "b, "
    2140             :          << U << "u " << S << "s)\n";
    2141             : }
    2142             : #endif
    2143             : 
    2144      890013 : void APInt::print(raw_ostream &OS, bool isSigned) const {
    2145             :   SmallString<40> S;
    2146      890013 :   this->toString(S, 10, isSigned, /* formatAsCLiteral = */false);
    2147             :   OS << S;
    2148      890013 : }
    2149             : 
    2150             : // This implements a variety of operations on a representation of
    2151             : // arbitrary precision, two's-complement, bignum integer values.
    2152             : 
    2153             : // Assumed by lowHalf, highHalf, partMSB and partLSB.  A fairly safe
    2154             : // and unrestricting assumption.
    2155             : static_assert(APInt::APINT_BITS_PER_WORD % 2 == 0,
    2156             :               "Part width must be divisible by 2!");
    2157             : 
    2158             : /* Some handy functions local to this file.  */
    2159             : 
    2160             : /* Returns the integer part with the least significant BITS set.
    2161             :    BITS cannot be zero.  */
    2162             : static inline APInt::WordType lowBitMask(unsigned bits) {
    2163             :   assert(bits != 0 && bits <= APInt::APINT_BITS_PER_WORD);
    2164             : 
    2165      166253 :   return ~(APInt::WordType) 0 >> (APInt::APINT_BITS_PER_WORD - bits);
    2166             : }
    2167             : 
    2168             : /* Returns the value of the lower half of PART.  */
    2169             : static inline APInt::WordType lowHalf(APInt::WordType part) {
    2170     4583585 :   return part & lowBitMask(APInt::APINT_BITS_PER_WORD / 2);
    2171             : }
    2172             : 
    2173             : /* Returns the value of the upper half of PART.  */
    2174             : static inline APInt::WordType highHalf(APInt::WordType part) {
    2175    13750755 :   return part >> (APInt::APINT_BITS_PER_WORD / 2);
    2176             : }
    2177             : 
    2178             : /* Returns the bit number of the most significant set bit of a part.
    2179             :    If the input number has no bits set -1U is returned.  */
    2180             : static unsigned partMSB(APInt::WordType value) {
    2181      775617 :   return findLastSet(value, ZB_Max);
    2182             : }
    2183             : 
    2184             : /* Returns the bit number of the least significant set bit of a
    2185             :    part.  If the input number has no bits set -1U is returned.  */
    2186             : static unsigned partLSB(APInt::WordType value) {
    2187      314506 :   return findFirstSet(value, ZB_Max);
    2188             : }
    2189             : 
    2190             : /* Sets the least significant part of a bignum to the input value, and
    2191             :    zeroes out higher parts.  */
    2192     1558256 : void APInt::tcSet(WordType *dst, WordType part, unsigned parts) {
    2193             :   assert(parts > 0);
    2194             : 
    2195     1558256 :   dst[0] = part;
    2196     4619162 :   for (unsigned i = 1; i < parts; i++)
    2197     1530453 :     dst[i] = 0;
    2198     1558256 : }
    2199             : 
    2200             : /* Assign one bignum to another.  */
    2201      806270 : void APInt::tcAssign(WordType *dst, const WordType *src, unsigned parts) {
    2202     2512748 :   for (unsigned i = 0; i < parts; i++)
    2203      853239 :     dst[i] = src[i];
    2204      806270 : }
    2205             : 
    2206             : /* Returns true if a bignum is zero, false otherwise.  */
    2207       13237 : bool APInt::tcIsZero(const WordType *src, unsigned parts) {
    2208       34171 :   for (unsigned i = 0; i < parts; i++)
    2209       13407 :     if (src[i])
    2210             :       return false;
    2211             : 
    2212             :   return true;
    2213             : }
    2214             : 
    2215             : /* Extract the given bit of a bignum; returns 0 or 1.  */
    2216      154338 : int APInt::tcExtractBit(const WordType *parts, unsigned bit) {
    2217      308676 :   return (parts[whichWord(bit)] & maskBit(bit)) != 0;
    2218             : }
    2219             : 
    2220             : /* Set the given bit of a bignum. */
    2221      189633 : void APInt::tcSetBit(WordType *parts, unsigned bit) {
    2222      189633 :   parts[whichWord(bit)] |= maskBit(bit);
    2223      189633 : }
    2224             : 
    2225             : /* Clears the given bit of a bignum. */
    2226         290 : void APInt::tcClearBit(WordType *parts, unsigned bit) {
    2227         580 :   parts[whichWord(bit)] &= ~maskBit(bit);
    2228         290 : }
    2229             : 
    2230             : /* Returns the bit number of the least significant set bit of a
    2231             :    number.  If the input number has no bits set -1U is returned.  */
    2232      314506 : unsigned APInt::tcLSB(const WordType *parts, unsigned n) {
    2233      391816 :   for (unsigned i = 0; i < n; i++) {
    2234      353161 :     if (parts[i] != 0) {
    2235             :       unsigned lsb = partLSB(parts[i]);
    2236             : 
    2237      314506 :       return lsb + i * APINT_BITS_PER_WORD;
    2238             :     }
    2239             :   }
    2240             : 
    2241             :   return -1U;
    2242             : }
    2243             : 
    2244             : /* Returns the bit number of the most significant set bit of a number.
    2245             :    If the input number has no bits set -1U is returned.  */
    2246      778825 : unsigned APInt::tcMSB(const WordType *parts, unsigned n) {
    2247             :   do {
    2248      833996 :     --n;
    2249             : 
    2250      833996 :     if (parts[n] != 0) {
    2251             :       unsigned msb = partMSB(parts[n]);
    2252             : 
    2253      775617 :       return msb + n * APINT_BITS_PER_WORD;
    2254             :     }
    2255       58379 :   } while (n);
    2256             : 
    2257             :   return -1U;
    2258             : }
    2259             : 
    2260             : /* Copy the bit vector of width srcBITS from SRC, starting at bit
    2261             :    srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
    2262             :    the least significant bit of DST.  All high bits above srcBITS in
    2263             :    DST are zero-filled.  */
    2264             : void
    2265      167832 : APInt::tcExtract(WordType *dst, unsigned dstCount, const WordType *src,
    2266             :                  unsigned srcBits, unsigned srcLSB) {
    2267      167832 :   unsigned dstParts = (srcBits + APINT_BITS_PER_WORD - 1) / APINT_BITS_PER_WORD;
    2268             :   assert(dstParts <= dstCount);
    2269             : 
    2270      167832 :   unsigned firstSrcPart = srcLSB / APINT_BITS_PER_WORD;
    2271      167832 :   tcAssign (dst, src + firstSrcPart, dstParts);
    2272             : 
    2273      167832 :   unsigned shift = srcLSB % APINT_BITS_PER_WORD;
    2274      167832 :   tcShiftRight (dst, dstParts, shift);
    2275             : 
    2276             :   /* We now have (dstParts * APINT_BITS_PER_WORD - shift) bits from SRC
    2277             :      in DST.  If this is less that srcBits, append the rest, else
    2278             :      clear the high bits.  */
    2279      167832 :   unsigned n = dstParts * APINT_BITS_PER_WORD - shift;
    2280      167832 :   if (n < srcBits) {
    2281        2018 :     WordType mask = lowBitMask (srcBits - n);
    2282        4036 :     dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
    2283        2018 :                           << n % APINT_BITS_PER_WORD);
    2284      165814 :   } else if (n > srcBits) {
    2285      164369 :     if (srcBits % APINT_BITS_PER_WORD)
    2286      164235 :       dst[dstParts - 1] &= lowBitMask (srcBits % APINT_BITS_PER_WORD);
    2287             :   }
    2288             : 
    2289             :   /* Clear high parts.  */
    2290      258732 :   while (dstParts < dstCount)
    2291       45450 :     dst[dstParts++] = 0;
    2292      167832 : }
    2293             : 
    2294             : /* DST += RHS + C where C is zero or one.  Returns the carry flag.  */
    2295      844651 : APInt::WordType APInt::tcAdd(WordType *dst, const WordType *rhs,
    2296             :                              WordType c, unsigned parts) {
    2297             :   assert(c <= 1);
    2298             : 
    2299     4223825 :   for (unsigned i = 0; i < parts; i++) {
    2300     1689587 :     WordType l = dst[i];
    2301     1689587 :     if (c) {
    2302        3346 :       dst[i] += rhs[i] + 1;
    2303        3346 :       c = (dst[i] <= l);
    2304             :     } else {
    2305     1686241 :       dst[i] += rhs[i];
    2306     1686241 :       c = (dst[i] < l);
    2307             :     }
    2308             :   }
    2309             : 
    2310      844651 :   return c;
    2311             : }
    2312             : 
    2313             : /// This function adds a single "word" integer, src, to the multiple
    2314             : /// "word" integer array, dst[]. dst[] is modified to reflect the addition and
    2315             : /// 1 is returned if there is a carry out, otherwise 0 is returned.
    2316             : /// @returns the carry of the addition.
    2317      358628 : APInt::WordType APInt::tcAddPart(WordType *dst, WordType src,
    2318             :                                  unsigned parts) {
    2319      391516 :   for (unsigned i = 0; i < parts; ++i) {
    2320      370691 :     dst[i] += src;
    2321      370691 :     if (dst[i] >= src)
    2322             :       return 0; // No need to carry so exit early.
    2323             :     src = 1; // Carry one to next digit.
    2324             :   }
    2325             : 
    2326             :   return 1;
    2327             : }
    2328             : 
    2329             : /* DST -= RHS + C where C is zero or one.  Returns the carry flag.  */
    2330      292846 : APInt::WordType APInt::tcSubtract(WordType *dst, const WordType *rhs,
    2331             :                                   WordType c, unsigned parts) {
    2332             :   assert(c <= 1);
    2333             : 
    2334     1127520 :   for (unsigned i = 0; i < parts; i++) {
    2335      417337 :     WordType l = dst[i];
    2336      417337 :     if (c) {
    2337       48012 :       dst[i] -= rhs[i] + 1;
    2338       48012 :       c = (dst[i] >= l);
    2339             :     } else {
    2340      369325 :       dst[i] -= rhs[i];
    2341      369325 :       c = (dst[i] > l);
    2342             :     }
    2343             :   }
    2344             : 
    2345      292846 :   return c;
    2346             : }
    2347             : 
    2348             : /// This function subtracts a single "word" (64-bit word), src, from
    2349             : /// the multi-word integer array, dst[], propagating the borrowed 1 value until
    2350             : /// no further borrowing is needed or it runs out of "words" in dst.  The result
    2351             : /// is 1 if "borrowing" exhausted the digits in dst, or 0 if dst was not
    2352             : /// exhausted. In other words, if src > dst then this function returns 1,
    2353             : /// otherwise 0.
    2354             : /// @returns the borrow out of the subtraction
    2355      115852 : APInt::WordType APInt::tcSubtractPart(WordType *dst, WordType src,
    2356             :                                       unsigned parts) {
    2357      133758 :   for (unsigned i = 0; i < parts; ++i) {
    2358      122519 :     WordType Dst = dst[i];
    2359      122519 :     dst[i] -= src;
    2360      122519 :     if (src <= Dst)
    2361             :       return 0; // No need to borrow so exit early.
    2362             :     src = 1; // We have to "borrow 1" from next "word"
    2363             :   }
    2364             : 
    2365             :   return 1;
    2366             : }
    2367             : 
    2368             : /* Negate a bignum in-place.  */
    2369         137 : void APInt::tcNegate(WordType *dst, unsigned parts) {
    2370         137 :   tcComplement(dst, parts);
    2371             :   tcIncrement(dst, parts);
    2372         137 : }
    2373             : 
    2374             : /*  DST += SRC * MULTIPLIER + CARRY   if add is true
    2375             :     DST  = SRC * MULTIPLIER + CARRY   if add is false
    2376             : 
    2377             :     Requires 0 <= DSTPARTS <= SRCPARTS + 1.  If DST overlaps SRC
    2378             :     they must start at the same point, i.e. DST == SRC.
    2379             : 
    2380             :     If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
    2381             :     returned.  Otherwise DST is filled with the least significant
    2382             :     DSTPARTS parts of the result, and if all of the omitted higher
    2383             :     parts were zero return zero, otherwise overflow occurred and
    2384             :     return one.  */
    2385     2760093 : int APInt::tcMultiplyPart(WordType *dst, const WordType *src,
    2386             :                           WordType multiplier, WordType carry,
    2387             :                           unsigned srcParts, unsigned dstParts,
    2388             :                           bool add) {
    2389             :   /* Otherwise our writes of DST kill our later reads of SRC.  */
    2390             :   assert(dst <= src || dst >= src + srcParts);
    2391             :   assert(dstParts <= srcParts + 1);
    2392             : 
    2393             :   /* N loops; minimum of dstParts and srcParts.  */
    2394     2760093 :   unsigned n = std::min(dstParts, srcParts);
    2395             : 
    2396    28629477 :   for (unsigned i = 0; i < n; i++) {
    2397             :     WordType low, mid, high, srcPart;
    2398             : 
    2399             :       /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
    2400             : 
    2401             :          This cannot overflow, because
    2402             : 
    2403             :          (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
    2404             : 
    2405             :          which is less than n^2.  */
    2406             : 
    2407    12934692 :     srcPart = src[i];
    2408             : 
    2409    12934692 :     if (multiplier == 0 || srcPart == 0) {
    2410             :       low = carry;
    2411             :       high = 0;
    2412             :     } else {
    2413     4583585 :       low = lowHalf(srcPart) * lowHalf(multiplier);
    2414     4583585 :       high = highHalf(srcPart) * highHalf(multiplier);
    2415             : 
    2416     4583585 :       mid = lowHalf(srcPart) * highHalf(multiplier);
    2417     4583585 :       high += highHalf(mid);
    2418     4583585 :       mid <<= APINT_BITS_PER_WORD / 2;
    2419     4583585 :       if (low + mid < low)
    2420     1096194 :         high++;
    2421             :       low += mid;
    2422             : 
    2423     4583585 :       mid = highHalf(srcPart) * lowHalf(multiplier);
    2424     4583585 :       high += highHalf(mid);
    2425     4583585 :       mid <<= APINT_BITS_PER_WORD / 2;
    2426     4583585 :       if (low + mid < low)
    2427     1874095 :         high++;
    2428             :       low += mid;
    2429             : 
    2430             :       /* Now add carry.  */
    2431     4583585 :       if (low + carry < low)
    2432      896577 :         high++;
    2433             :       low += carry;
    2434             :     }
    2435             : 
    2436    12934692 :     if (add) {
    2437             :       /* And now DST[i], and store the new low part there.  */
    2438    12873226 :       if (low + dst[i] < low)
    2439     1759469 :         high++;
    2440    12873226 :       dst[i] += low;
    2441             :     } else
    2442       61466 :       dst[i] = low;
    2443             : 
    2444             :     carry = high;
    2445             :   }
    2446             : 
    2447     2760093 :   if (srcParts < dstParts) {
    2448             :     /* Full multiplication, there is no overflow.  */
    2449             :     assert(srcParts + 1 == dstParts);
    2450      158582 :     dst[srcParts] = carry;
    2451      158582 :     return 0;
    2452             :   }
    2453             : 
    2454             :   /* We overflowed if there is carry.  */
    2455     2601511 :   if (carry)
    2456             :     return 1;
    2457             : 
    2458             :   /* We would overflow if any significant unwritten parts would be
    2459             :      non-zero.  This is true if any remaining src parts are non-zero
    2460             :      and the multiplier is non-zero.  */
    2461     2447014 :   if (multiplier)
    2462     1645051 :     for (unsigned i = dstParts; i < srcParts; i++)
    2463      284069 :       if (src[i])
    2464             :         return 1;
    2465             : 
    2466             :   /* We fitted in the narrow destination.  */
    2467             :   return 0;
    2468             : }
    2469             : 
    2470             : /* DST = LHS * RHS, where DST has the same width as the operands and
    2471             :    is filled with the least significant parts of the result.  Returns
    2472             :    one if overflow occurred, otherwise zero.  DST must be disjoint
    2473             :    from both operands.  */
    2474     1163829 : int APInt::tcMultiply(WordType *dst, const WordType *lhs,
    2475             :                       const WordType *rhs, unsigned parts) {
    2476             :   assert(dst != lhs && dst != rhs);
    2477             : 
    2478             :   int overflow = 0;
    2479     1163829 :   tcSet(dst, 0, parts);
    2480             : 
    2481     6316719 :   for (unsigned i = 0; i < parts; i++)
    2482     2576445 :     overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
    2483             :                                parts - i, true);
    2484             : 
    2485     1163829 :   return overflow;
    2486             : }
    2487             : 
    2488             : /// DST = LHS * RHS, where DST has width the sum of the widths of the
    2489             : /// operands. No overflow occurs. DST must be disjoint from both operands.
    2490       49940 : void APInt::tcFullMultiply(WordType *dst, const WordType *lhs,
    2491             :                            const WordType *rhs, unsigned lhsParts,
    2492             :                            unsigned rhsParts) {
    2493             :   /* Put the narrower number on the LHS for less loops below.  */
    2494       49940 :   if (lhsParts > rhsParts)
    2495             :     return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
    2496             : 
    2497             :   assert(dst != lhs && dst != rhs);
    2498             : 
    2499       49940 :   tcSet(dst, 0, rhsParts);
    2500             : 
    2501      262350 :   for (unsigned i = 0; i < lhsParts; i++)
    2502      106205 :     tcMultiplyPart(&dst[i], rhs, lhs[i], 0, rhsParts, rhsParts + 1, true);
    2503             : }
    2504             : 
    2505             : /* If RHS is zero LHS and REMAINDER are left unchanged, return one.
    2506             :    Otherwise set LHS to LHS / RHS with the fractional part discarded,
    2507             :    set REMAINDER to the remainder, return zero.  i.e.
    2508             : 
    2509             :    OLD_LHS = RHS * LHS + REMAINDER
    2510             : 
    2511             :    SCRATCH is a bignum of the same size as the operands and result for
    2512             :    use by the routine; its contents need not be initialized and are
    2513             :    destroyed.  LHS, REMAINDER and SCRATCH must be distinct.
    2514             : */
    2515           0 : int APInt::tcDivide(WordType *lhs, const WordType *rhs,
    2516             :                     WordType *remainder, WordType *srhs,
    2517             :                     unsigned parts) {
    2518             :   assert(lhs != remainder && lhs != srhs && remainder != srhs);
    2519             : 
    2520           0 :   unsigned shiftCount = tcMSB(rhs, parts) + 1;
    2521           0 :   if (shiftCount == 0)
    2522             :     return true;
    2523             : 
    2524           0 :   shiftCount = parts * APINT_BITS_PER_WORD - shiftCount;
    2525           0 :   unsigned n = shiftCount / APINT_BITS_PER_WORD;
    2526           0 :   WordType mask = (WordType) 1 << (shiftCount % APINT_BITS_PER_WORD);
    2527             : 
    2528           0 :   tcAssign(srhs, rhs, parts);
    2529           0 :   tcShiftLeft(srhs, parts, shiftCount);
    2530           0 :   tcAssign(remainder, lhs, parts);
    2531           0 :   tcSet(lhs, 0, parts);
    2532             : 
    2533             :   /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
    2534             :      the total.  */
    2535             :   for (;;) {
    2536           0 :     int compare = tcCompare(remainder, srhs, parts);
    2537           0 :     if (compare >= 0) {
    2538           0 :       tcSubtract(remainder, srhs, 0, parts);
    2539           0 :       lhs[n] |= mask;
    2540             :     }
    2541             : 
    2542           0 :     if (shiftCount == 0)
    2543             :       break;
    2544           0 :     shiftCount--;
    2545           0 :     tcShiftRight(srhs, parts, 1);
    2546           0 :     if ((mask >>= 1) == 0) {
    2547             :       mask = (WordType) 1 << (APINT_BITS_PER_WORD - 1);
    2548           0 :       n--;
    2549             :     }
    2550             :   }
    2551             : 
    2552             :   return false;
    2553             : }
    2554             : 
    2555             : /// Shift a bignum left Cound bits in-place. Shifted in bits are zero. There are
    2556             : /// no restrictions on Count.
    2557     2427995 : void APInt::tcShiftLeft(WordType *Dst, unsigned Words, unsigned Count) {
    2558             :   // Don't bother performing a no-op shift.
    2559     2427995 :   if (!Count)
    2560             :     return;
    2561             : 
    2562             :   // WordShift is the inter-part shift; BitShift is the intra-part shift.
    2563     4854308 :   unsigned WordShift = std::min(Count / APINT_BITS_PER_WORD, Words);
    2564     2427154 :   unsigned BitShift = Count % APINT_BITS_PER_WORD;
    2565             : 
    2566             :   // Fastpath for moving by whole words.
    2567     2427154 :   if (BitShift == 0) {
    2568       19571 :     std::memmove(Dst + WordShift, Dst, (Words - WordShift) * APINT_WORD_SIZE);
    2569             :   } else {
    2570    21157383 :     while (Words-- > WordShift) {
    2571    18749800 :       Dst[Words] = Dst[Words - WordShift] << BitShift;
    2572    18749800 :       if (Words > WordShift)
    2573    16342217 :         Dst[Words] |=
    2574    16342217 :           Dst[Words - WordShift - 1] >> (APINT_BITS_PER_WORD - BitShift);
    2575             :     }
    2576             :   }
    2577             : 
    2578             :   // Fill in the remainder with 0s.
    2579     2427154 :   std::memset(Dst, 0, WordShift * APINT_WORD_SIZE);
    2580             : }
    2581             : 
    2582             : /// Shift a bignum right Count bits in-place. Shifted in bits are zero. There
    2583             : /// are no restrictions on Count.
    2584     2225940 : void APInt::tcShiftRight(WordType *Dst, unsigned Words, unsigned Count) {
    2585             :   // Don't bother performing a no-op shift.
    2586     2225940 :   if (!Count)
    2587             :     return;
    2588             : 
    2589             :   // WordShift is the inter-part shift; BitShift is the intra-part shift.
    2590     4228370 :   unsigned WordShift = std::min(Count / APINT_BITS_PER_WORD, Words);
    2591     2114185 :   unsigned BitShift = Count % APINT_BITS_PER_WORD;
    2592             : 
    2593     2114185 :   unsigned WordsToMove = Words - WordShift;
    2594             :   // Fastpath for moving by whole words.
    2595     2114185 :   if (BitShift == 0) {
    2596      640930 :     std::memmove(Dst, Dst + WordShift, WordsToMove * APINT_WORD_SIZE);
    2597             :   } else {
    2598    19043565 :     for (unsigned i = 0; i != WordsToMove; ++i) {
    2599    17570310 :       Dst[i] = Dst[i + WordShift] >> BitShift;
    2600    17570310 :       if (i + 1 != WordsToMove)
    2601    16097426 :         Dst[i] |= Dst[i + WordShift + 1] << (APINT_BITS_PER_WORD - BitShift);
    2602             :     }
    2603             :   }
    2604             : 
    2605             :   // Fill in the remainder with 0s.
    2606     2114185 :   std::memset(Dst + WordsToMove, 0, WordShift * APINT_WORD_SIZE);
    2607             : }
    2608             : 
    2609             : /* Bitwise and of two bignums.  */
    2610       68291 : void APInt::tcAnd(WordType *dst, const WordType *rhs, unsigned parts) {
    2611      397005 :   for (unsigned i = 0; i < parts; i++)
    2612      164357 :     dst[i] &= rhs[i];
    2613       68291 : }
    2614             : 
    2615             : /* Bitwise inclusive or of two bignums.  */
    2616       81485 : void APInt::tcOr(WordType *dst, const WordType *rhs, unsigned parts) {
    2617      575117 :   for (unsigned i = 0; i < parts; i++)
    2618      246816 :     dst[i] |= rhs[i];
    2619       81485 : }
    2620             : 
    2621             : /* Bitwise exclusive or of two bignums.  */
    2622        1201 : void APInt::tcXor(WordType *dst, const WordType *rhs, unsigned parts) {
    2623        9075 :   for (unsigned i = 0; i < parts; i++)
    2624        3937 :     dst[i] ^= rhs[i];
    2625        1201 : }
    2626             : 
    2627             : /* Complement a bignum in-place.  */
    2628       76147 : void APInt::tcComplement(WordType *dst, unsigned parts) {
    2629      420021 :   for (unsigned i = 0; i < parts; i++)
    2630      171937 :     dst[i] = ~dst[i];
    2631       76147 : }
    2632             : 
    2633             : /* Comparison (unsigned) of two bignums.  */
    2634     1804518 : int APInt::tcCompare(const WordType *lhs, const WordType *rhs,
    2635             :                      unsigned parts) {
    2636     2469290 :   while (parts) {
    2637     2347318 :     parts--;
    2638     2347318 :     if (lhs[parts] != rhs[parts])
    2639     1682546 :       return (lhs[parts] > rhs[parts]) ? 1 : -1;
    2640             :   }
    2641             : 
    2642             :   return 0;
    2643             : }
    2644             : 
    2645             : /* Set the least significant BITS bits of a bignum, clear the
    2646             :    rest.  */
    2647          97 : void APInt::tcSetLeastSignificantBits(WordType *dst, unsigned parts,
    2648             :                                       unsigned bits) {
    2649             :   unsigned i = 0;
    2650         103 :   while (bits > APINT_BITS_PER_WORD) {
    2651           3 :     dst[i++] = ~(WordType) 0;
    2652           3 :     bits -= APINT_BITS_PER_WORD;
    2653             :   }
    2654             : 
    2655          97 :   if (bits)
    2656          76 :     dst[i++] = ~(WordType) 0 >> (APINT_BITS_PER_WORD - bits);
    2657             : 
    2658         139 :   while (i < parts)
    2659          21 :     dst[i++] = 0;
    2660          97 : }

Generated by: LCOV version 1.13