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-06-17 00:07:59 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/Config/llvm-config.h"
      22             : #include "llvm/Support/Debug.h"
      23             : #include "llvm/Support/ErrorHandling.h"
      24             : #include "llvm/Support/MathExtras.h"
      25             : #include "llvm/Support/raw_ostream.h"
      26             : #include <climits>
      27             : #include <cmath>
      28             : #include <cstdlib>
      29             : #include <cstring>
      30             : using namespace llvm;
      31             : 
      32             : #define DEBUG_TYPE "apint"
      33             : 
      34             : /// A utility function for allocating memory, checking for allocation failures,
      35             : /// and ensuring the contents are zeroed.
      36     3200897 : inline static uint64_t* getClearedMemory(unsigned numWords) {
      37     3200897 :   uint64_t *result = new uint64_t[numWords];
      38     3200897 :   memset(result, 0, numWords * sizeof(uint64_t));
      39     3200897 :   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     6396887 :   return new uint64_t[numWords];
      46             : }
      47             : 
      48             : /// A utility function that converts a character to a digit.
      49     4618009 : inline static unsigned getDigit(char cdigit, uint8_t radix) {
      50             :   unsigned r;
      51             : 
      52     4618009 :   if (radix == 16 || radix == 36) {
      53        9121 :     r = cdigit - '0';
      54        9121 :     if (r <= 9)
      55             :       return r;
      56             : 
      57        1176 :     r = cdigit - 'A';
      58        1176 :     if (r <= radix - 11U)
      59         474 :       return r + 10;
      60             : 
      61         702 :     r = cdigit - 'a';
      62         702 :     if (r <= radix - 11U)
      63         702 :       return r + 10;
      64             : 
      65             :     radix = 10;
      66             :   }
      67             : 
      68     4608888 :   r = cdigit - '0';
      69     4608888 :   if (r < radix)
      70             :     return r;
      71             : 
      72           0 :   return -1U;
      73             : }
      74             : 
      75             : 
      76     3192137 : void APInt::initSlowCase(uint64_t val, bool isSigned) {
      77     6384274 :   U.pVal = getClearedMemory(getNumWords());
      78     3192137 :   U.pVal[0] = val;
      79     3192137 :   if (isSigned && int64_t(val) < 0)
      80     1006582 :     for (unsigned i = 1; i < getNumWords(); ++i)
      81      206562 :       U.pVal[i] = WORD_MAX;
      82     3192137 :   clearUnusedBits();
      83     3192137 : }
      84             : 
      85     4222210 : void APInt::initSlowCase(const APInt& that) {
      86     8444420 :   U.pVal = getMemory(getNumWords());
      87     8444420 :   memcpy(U.pVal, that.U.pVal, getNumWords() * APINT_WORD_SIZE);
      88     4222210 : }
      89             : 
      90      117736 : void APInt::initFromArray(ArrayRef<uint64_t> bigVal) {
      91             :   assert(BitWidth && "Bitwidth too small");
      92             :   assert(bigVal.data() && "Null pointer detected!");
      93      117736 :   if (isSingleWord())
      94      110293 :     U.VAL = bigVal[0];
      95             :   else {
      96             :     // Get memory, cleared to 0
      97        7443 :     U.pVal = getClearedMemory(getNumWords());
      98             :     // Calculate the number of words to copy
      99       22329 :     unsigned words = std::min<unsigned>(bigVal.size(), getNumWords());
     100             :     // Copy the words from bigVal to pVal
     101        7443 :     memcpy(U.pVal, bigVal.data(), words * APINT_WORD_SIZE);
     102             :   }
     103             :   // Make sure unused high bits are cleared
     104      117736 :   clearUnusedBits();
     105      117736 : }
     106             : 
     107       31158 : APInt::APInt(unsigned numBits, ArrayRef<uint64_t> bigVal)
     108       31158 :   : BitWidth(numBits) {
     109       31158 :   initFromArray(bigVal);
     110       31158 : }
     111             : 
     112       86578 : APInt::APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[])
     113       86578 :   : BitWidth(numBits) {
     114       86578 :   initFromArray(makeArrayRef(bigVal, numWords));
     115       86578 : }
     116             : 
     117     3248898 : APInt::APInt(unsigned numbits, StringRef Str, uint8_t radix)
     118     3248898 :   : BitWidth(numbits) {
     119             :   assert(BitWidth && "Bitwidth too small");
     120     3248898 :   fromString(numbits, Str, radix);
     121     3248898 : }
     122             : 
     123      181254 : void APInt::reallocate(unsigned NewBitWidth) {
     124             :   // If the number of words is the same we can just change the width and stop.
     125      362508 :   if (getNumWords() == getNumWords(NewBitWidth)) {
     126      106065 :     BitWidth = NewBitWidth;
     127      106065 :     return;
     128             :   }
     129             : 
     130             :   // If we have an allocation, delete it.
     131       75189 :   if (!isSingleWord())
     132        6625 :     delete [] U.pVal;
     133             : 
     134             :   // Update BitWidth.
     135       75189 :   BitWidth = NewBitWidth;
     136             : 
     137             :   // If we are supposed to have an allocation, create it.
     138       75189 :   if (!isSingleWord())
     139       68564 :     U.pVal = getMemory(getNumWords());
     140             : }
     141             : 
     142       83046 : void APInt::AssignSlowCase(const APInt& RHS) {
     143             :   // Don't do anything for X = X
     144       83046 :   if (this == &RHS)
     145             :     return;
     146             : 
     147             :   // Adjust the bit width and handle allocations as necessary.
     148       82914 :   reallocate(RHS.getBitWidth());
     149             : 
     150             :   // Copy the data.
     151       82914 :   if (isSingleWord())
     152        6625 :     U.VAL = RHS.U.VAL;
     153             :   else
     154       76289 :     memcpy(U.pVal, RHS.U.pVal, getNumWords() * APINT_WORD_SIZE);
     155             : }
     156             : 
     157             : /// This method 'profiles' an APInt for use with FoldingSet.
     158     4023220 : void APInt::Profile(FoldingSetNodeID& ID) const {
     159     4023220 :   ID.AddInteger(BitWidth);
     160             : 
     161     4023220 :   if (isSingleWord()) {
     162     4023213 :     ID.AddInteger(U.VAL);
     163     4023213 :     return;
     164             :   }
     165             : 
     166             :   unsigned NumWords = getNumWords();
     167          35 :   for (unsigned i = 0; i < NumWords; ++i)
     168          14 :     ID.AddInteger(U.pVal[i]);
     169             : }
     170             : 
     171             : /// Prefix increment operator. Increments the APInt by one.
     172     2560211 : APInt& APInt::operator++() {
     173     2560211 :   if (isSingleWord())
     174     2485192 :     ++U.VAL;
     175             :   else
     176       75019 :     tcIncrement(U.pVal, getNumWords());
     177     2560211 :   return clearUnusedBits();
     178             : }
     179             : 
     180             : /// Prefix decrement operator. Decrements the APInt by one.
     181       98472 : APInt& APInt::operator--() {
     182       98472 :   if (isSingleWord())
     183       98457 :     --U.VAL;
     184             :   else
     185          15 :     tcDecrement(U.pVal, getNumWords());
     186       98472 :   return clearUnusedBits();
     187             : }
     188             : 
     189             : /// Adds the RHS APint to this APInt.
     190             : /// @returns this, after addition of RHS.
     191             : /// Addition assignment operator.
     192    18613599 : APInt& APInt::operator+=(const APInt& RHS) {
     193             :   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
     194    18613599 :   if (isSingleWord())
     195    17630227 :     U.VAL += RHS.U.VAL;
     196             :   else
     197      983372 :     tcAdd(U.pVal, RHS.U.pVal, 0, getNumWords());
     198    18613599 :   return clearUnusedBits();
     199             : }
     200             : 
     201    21367598 : APInt& APInt::operator+=(uint64_t RHS) {
     202    21367598 :   if (isSingleWord())
     203    20957631 :     U.VAL += RHS;
     204             :   else
     205      409967 :     tcAddPart(U.pVal, RHS, getNumWords());
     206    21367598 :   return clearUnusedBits();
     207             : }
     208             : 
     209             : /// Subtracts the RHS APInt from this APInt
     210             : /// @returns this, after subtraction
     211             : /// Subtraction assignment operator.
     212    28939144 : APInt& APInt::operator-=(const APInt& RHS) {
     213             :   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
     214    28939144 :   if (isSingleWord())
     215    28820406 :     U.VAL -= RHS.U.VAL;
     216             :   else
     217      118738 :     tcSubtract(U.pVal, RHS.U.pVal, 0, getNumWords());
     218    28939144 :   return clearUnusedBits();
     219             : }
     220             : 
     221     4264811 : APInt& APInt::operator-=(uint64_t RHS) {
     222     4264811 :   if (isSingleWord())
     223     4120243 :     U.VAL -= RHS;
     224             :   else
     225      144568 :     tcSubtractPart(U.pVal, RHS, getNumWords());
     226     4264811 :   return clearUnusedBits();
     227             : }
     228             : 
     229    29668730 : APInt APInt::operator*(const APInt& RHS) const {
     230             :   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
     231    29668730 :   if (isSingleWord())
     232    28309015 :     return APInt(BitWidth, U.VAL * RHS.U.VAL);
     233             : 
     234             :   APInt Result(getMemory(getNumWords()), getBitWidth());
     235             : 
     236     2719430 :   tcMultiply(Result.U.pVal, U.pVal, RHS.U.pVal, getNumWords());
     237             : 
     238     1359715 :   Result.clearUnusedBits();
     239             :   return Result;
     240             : }
     241             : 
     242       79014 : void APInt::AndAssignSlowCase(const APInt& RHS) {
     243      158028 :   tcAnd(U.pVal, RHS.U.pVal, getNumWords());
     244       79014 : }
     245             : 
     246       72984 : void APInt::OrAssignSlowCase(const APInt& RHS) {
     247      145968 :   tcOr(U.pVal, RHS.U.pVal, getNumWords());
     248       72984 : }
     249             : 
     250        1231 : void APInt::XorAssignSlowCase(const APInt& RHS) {
     251        2462 :   tcXor(U.pVal, RHS.U.pVal, getNumWords());
     252        1231 : }
     253             : 
     254     1021300 : APInt& APInt::operator*=(const APInt& RHS) {
     255             :   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
     256     2042600 :   *this = *this * RHS;
     257     1021300 :   return *this;
     258             : }
     259             : 
     260     2708953 : APInt& APInt::operator*=(uint64_t RHS) {
     261     2708953 :   if (isSingleWord()) {
     262     2682035 :     U.VAL *= RHS;
     263             :   } else {
     264             :     unsigned NumWords = getNumWords();
     265       26918 :     tcMultiplyPart(U.pVal, U.pVal, RHS, 0, NumWords, NumWords, false);
     266             :   }
     267     2708953 :   return clearUnusedBits();
     268             : }
     269             : 
     270     2431056 : bool APInt::EqualSlowCase(const APInt& RHS) const {
     271     7293168 :   return std::equal(U.pVal, U.pVal + getNumWords(), RHS.U.pVal);
     272             : }
     273             : 
     274    26259924 : int APInt::compare(const APInt& RHS) const {
     275             :   assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
     276    26259924 :   if (isSingleWord())
     277    25511301 :     return U.VAL < RHS.U.VAL ? -1 : U.VAL > RHS.U.VAL;
     278             : 
     279      748623 :   return tcCompare(U.pVal, RHS.U.pVal, getNumWords());
     280             : }
     281             : 
     282    12591307 : int APInt::compareSigned(const APInt& RHS) const {
     283             :   assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
     284    12591307 :   if (isSingleWord()) {
     285    12163793 :     int64_t lhsSext = SignExtend64(U.VAL, BitWidth);
     286    12163793 :     int64_t rhsSext = SignExtend64(RHS.U.VAL, BitWidth);
     287    12163793 :     return lhsSext < rhsSext ? -1 : lhsSext > rhsSext;
     288             :   }
     289             : 
     290      427514 :   bool lhsNeg = isNegative();
     291      427514 :   bool rhsNeg = RHS.isNegative();
     292             : 
     293             :   // If the sign bits don't match, then (LHS < RHS) if LHS is negative
     294      427514 :   if (lhsNeg != rhsNeg)
     295      199357 :     return lhsNeg ? -1 : 1;
     296             : 
     297             :   // Otherwise we can just use an unsigned comparison, because even negative
     298             :   // numbers compare correctly this way if both have the same signed-ness.
     299      228157 :   return tcCompare(U.pVal, RHS.U.pVal, getNumWords());
     300             : }
     301             : 
     302       61326 : void APInt::setBitsSlowCase(unsigned loBit, unsigned hiBit) {
     303             :   unsigned loWord = whichWord(loBit);
     304             :   unsigned hiWord = whichWord(hiBit);
     305             : 
     306             :   // Create an initial mask for the low word with zeros below loBit.
     307       61326 :   uint64_t loMask = WORD_MAX << whichBit(loBit);
     308             : 
     309             :   // If hiBit is not aligned, we need a high mask.
     310             :   unsigned hiShiftAmt = whichBit(hiBit);
     311       61326 :   if (hiShiftAmt != 0) {
     312             :     // Create a high mask with zeros above hiBit.
     313       11111 :     uint64_t hiMask = WORD_MAX >> (APINT_BITS_PER_WORD - hiShiftAmt);
     314             :     // If loWord and hiWord are equal, then we combine the masks. Otherwise,
     315             :     // set the bits in hiWord.
     316       11111 :     if (hiWord == loWord)
     317        9059 :       loMask &= hiMask;
     318             :     else
     319        2052 :       U.pVal[hiWord] |= hiMask;
     320             :   }
     321             :   // Apply the mask to the low word.
     322       61326 :   U.pVal[loWord] |= loMask;
     323             : 
     324             :   // Fill any words between loWord and hiWord with all ones.
     325       82460 :   for (unsigned word = loWord + 1; word < hiWord; ++word)
     326       21134 :     U.pVal[word] = WORD_MAX;
     327       61326 : }
     328             : 
     329             : /// Toggle every bit to its opposite value.
     330      106379 : void APInt::flipAllBitsSlowCase() {
     331      212758 :   tcComplement(U.pVal, getNumWords());
     332      106379 :   clearUnusedBits();
     333      106379 : }
     334             : 
     335             : /// Toggle a given bit to its opposite value whose position is given
     336             : /// as "bitPosition".
     337             : /// Toggles a given bit to its opposite value.
     338           0 : void APInt::flipBit(unsigned bitPosition) {
     339             :   assert(bitPosition < BitWidth && "Out of the bit-width range!");
     340           0 :   if ((*this)[bitPosition]) clearBit(bitPosition);
     341             :   else setBit(bitPosition);
     342           0 : }
     343             : 
     344      990027 : void APInt::insertBits(const APInt &subBits, unsigned bitPosition) {
     345      990027 :   unsigned subBitWidth = subBits.getBitWidth();
     346             :   assert(0 < subBitWidth && (subBitWidth + bitPosition) <= BitWidth &&
     347             :          "Illegal bit insertion");
     348             : 
     349             :   // Insertion is a direct copy.
     350      990027 :   if (subBitWidth == BitWidth) {
     351         129 :     *this = subBits;
     352         129 :     return;
     353             :   }
     354             : 
     355             :   // Single word result can be done as a direct bitmask.
     356      989898 :   if (isSingleWord()) {
     357       40212 :     uint64_t mask = WORD_MAX >> (APINT_BITS_PER_WORD - subBitWidth);
     358       40212 :     U.VAL &= ~(mask << bitPosition);
     359       40212 :     U.VAL |= (subBits.U.VAL << bitPosition);
     360       40212 :     return;
     361             :   }
     362             : 
     363             :   unsigned loBit = whichBit(bitPosition);
     364             :   unsigned loWord = whichWord(bitPosition);
     365      949686 :   unsigned hi1Word = whichWord(bitPosition + subBitWidth - 1);
     366             : 
     367             :   // Insertion within a single word can be done as a direct bitmask.
     368      949686 :   if (loWord == hi1Word) {
     369      949656 :     uint64_t mask = WORD_MAX >> (APINT_BITS_PER_WORD - subBitWidth);
     370      949656 :     U.pVal[loWord] &= ~(mask << loBit);
     371      949656 :     U.pVal[loWord] |= (subBits.U.VAL << loBit);
     372      949656 :     return;
     373             :   }
     374             : 
     375             :   // Insert on word boundaries.
     376          30 :   if (loBit == 0) {
     377             :     // Direct copy whole words.
     378          28 :     unsigned numWholeSubWords = subBitWidth / APINT_BITS_PER_WORD;
     379          56 :     memcpy(U.pVal + loWord, subBits.getRawData(),
     380          28 :            numWholeSubWords * APINT_WORD_SIZE);
     381             : 
     382             :     // Mask+insert remaining bits.
     383          28 :     unsigned remainingBits = subBitWidth % APINT_BITS_PER_WORD;
     384          28 :     if (remainingBits != 0) {
     385           3 :       uint64_t mask = WORD_MAX >> (APINT_BITS_PER_WORD - remainingBits);
     386           3 :       U.pVal[hi1Word] &= ~mask;
     387           6 :       U.pVal[hi1Word] |= subBits.getWord(subBitWidth - 1);
     388             :     }
     389             :     return;
     390             :   }
     391             : 
     392             :   // General case - set/clear individual bits in dst based on src.
     393             :   // TODO - there is scope for optimization here, but at the moment this code
     394             :   // path is barely used so prefer readability over performance.
     395         322 :   for (unsigned i = 0; i != subBitWidth; ++i) {
     396         160 :     if (subBits[i])
     397          10 :       setBit(bitPosition + i);
     398             :     else
     399         150 :       clearBit(bitPosition + i);
     400             :   }
     401             : }
     402             : 
     403      441143 : APInt APInt::extractBits(unsigned numBits, unsigned bitPosition) const {
     404             :   assert(numBits > 0 && "Can't extract zero bits");
     405             :   assert(bitPosition < BitWidth && (numBits + bitPosition) <= BitWidth &&
     406             :          "Illegal bit extraction");
     407             : 
     408      441143 :   if (isSingleWord())
     409       71763 :     return APInt(numBits, U.VAL >> bitPosition);
     410             : 
     411             :   unsigned loBit = whichBit(bitPosition);
     412             :   unsigned loWord = whichWord(bitPosition);
     413      369380 :   unsigned hiWord = whichWord(bitPosition + numBits - 1);
     414             : 
     415             :   // Single word result extracting bits from a single word source.
     416      369380 :   if (loWord == hiWord)
     417      369362 :     return APInt(numBits, U.pVal[loWord] >> loBit);
     418             : 
     419             :   // Extracting bits that start on a source word boundary can be done
     420             :   // as a fast memory copy.
     421          18 :   if (loBit == 0)
     422          14 :     return APInt(numBits, makeArrayRef(U.pVal + loWord, 1 + hiWord - loWord));
     423             : 
     424             :   // General case - shift + copy source words directly into place.
     425             :   APInt Result(numBits, 0);
     426           4 :   unsigned NumSrcWords = getNumWords();
     427           4 :   unsigned NumDstWords = Result.getNumWords();
     428             : 
     429           4 :   uint64_t *DestPtr = Result.isSingleWord() ? &Result.U.VAL : Result.U.pVal;
     430          20 :   for (unsigned word = 0; word < NumDstWords; ++word) {
     431           8 :     uint64_t w0 = U.pVal[loWord + word];
     432             :     uint64_t w1 =
     433           8 :         (loWord + word + 1) < NumSrcWords ? U.pVal[loWord + word + 1] : 0;
     434           8 :     DestPtr[word] = (w0 >> loBit) | (w1 << (APINT_BITS_PER_WORD - loBit));
     435             :   }
     436             : 
     437           4 :   return Result.clearUnusedBits();
     438             : }
     439             : 
     440          61 : unsigned APInt::getBitsNeeded(StringRef str, uint8_t radix) {
     441             :   assert(!str.empty() && "Invalid string length");
     442             :   assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
     443             :           radix == 36) &&
     444             :          "Radix should be 2, 8, 10, 16, or 36!");
     445             : 
     446             :   size_t slen = str.size();
     447             : 
     448             :   // Each computation below needs to know if it's negative.
     449          61 :   StringRef::iterator p = str.begin();
     450          61 :   unsigned isNegative = *p == '-';
     451          61 :   if (*p == '-' || *p == '+') {
     452          40 :     p++;
     453          40 :     slen--;
     454             :     assert(slen && "String is only a sign, needs a value.");
     455             :   }
     456             : 
     457             :   // For radixes of power-of-two values, the bits required is accurately and
     458             :   // easily computed
     459          61 :   if (radix == 2)
     460          15 :     return slen + isNegative;
     461          46 :   if (radix == 8)
     462          15 :     return slen * 3 + isNegative;
     463          31 :   if (radix == 16)
     464          15 :     return slen * 4 + isNegative;
     465             : 
     466             :   // FIXME: base 36
     467             : 
     468             :   // This is grossly inefficient but accurate. We could probably do something
     469             :   // with a computation of roughly slen*64/20 and then adjust by the value of
     470             :   // the first few digits. But, I'm not sure how accurate that could be.
     471             : 
     472             :   // Compute a sufficient number of bits that is always large enough but might
     473             :   // be too large. This avoids the assertion in the constructor. This
     474             :   // calculation doesn't work appropriately for the numbers 0-9, so just use 4
     475             :   // bits in that case.
     476          25 :   unsigned sufficient
     477           9 :     = radix == 10? (slen == 1 ? 4 : slen * 64/18)
     478           0 :                  : (slen == 1 ? 7 : slen * 16/3);
     479             : 
     480             :   // Convert to the actual binary value.
     481          32 :   APInt tmp(sufficient, StringRef(p, slen), radix);
     482             : 
     483             :   // Compute how many bits are required. If the log is infinite, assume we need
     484             :   // just bit.
     485             :   unsigned log = tmp.logBase2();
     486          16 :   if (log == (unsigned)-1) {
     487           3 :     return isNegative + 1;
     488             :   } else {
     489          13 :     return isNegative + log + 1;
     490             :   }
     491             : }
     492             : 
     493    47838633 : hash_code llvm::hash_value(const APInt &Arg) {
     494    47838633 :   if (Arg.isSingleWord())
     495    47672055 :     return hash_combine(Arg.U.VAL);
     496             : 
     497      333156 :   return hash_combine_range(Arg.U.pVal, Arg.U.pVal + Arg.getNumWords());
     498             : }
     499             : 
     500       25706 : bool APInt::isSplat(unsigned SplatSizeInBits) const {
     501             :   assert(getBitWidth() % SplatSizeInBits == 0 &&
     502             :          "SplatSizeInBits must divide width!");
     503             :   // We can check that all parts of an integer are equal by making use of a
     504             :   // little trick: rotate and check if it's still the same value.
     505       51412 :   return *this == rotl(SplatSizeInBits);
     506             : }
     507             : 
     508             : /// This function returns the high "numBits" bits of this APInt.
     509       13141 : APInt APInt::getHiBits(unsigned numBits) const {
     510       13141 :   return this->lshr(BitWidth - numBits);
     511             : }
     512             : 
     513             : /// This function returns the low "numBits" bits of this APInt.
     514      374100 : APInt APInt::getLoBits(unsigned numBits) const {
     515      374100 :   APInt Result(getLowBitsSet(BitWidth, numBits));
     516             :   Result &= *this;
     517      374100 :   return Result;
     518             : }
     519             : 
     520             : /// Return a value containing V broadcasted over NewLen bits.
     521       25594 : APInt APInt::getSplat(unsigned NewLen, const APInt &V) {
     522             :   assert(NewLen >= V.getBitWidth() && "Can't splat to smaller bit width!");
     523             : 
     524       25594 :   APInt Val = V.zextOrSelf(NewLen);
     525       36649 :   for (unsigned I = V.getBitWidth(); I < NewLen; I <<= 1)
     526       11055 :     Val |= Val << I;
     527             : 
     528       25594 :   return Val;
     529             : }
     530             : 
     531     3184228 : unsigned APInt::countLeadingZerosSlowCase() const {
     532             :   unsigned Count = 0;
     533   154531754 :   for (int i = getNumWords()-1; i >= 0; --i) {
     534   150799128 :     uint64_t V = U.pVal[i];
     535   150799128 :     if (V == 0)
     536   148163298 :       Count += APINT_BITS_PER_WORD;
     537             :     else {
     538     2635830 :       Count += llvm::countLeadingZeros(V);
     539     2635830 :       break;
     540             :     }
     541             :   }
     542             :   // Adjust for unused bits in the most significant word (they are zero).
     543     3184228 :   unsigned Mod = BitWidth % APINT_BITS_PER_WORD;
     544     3184228 :   Count -= Mod > 0 ? APINT_BITS_PER_WORD - Mod : 0;
     545     3184228 :   return Count;
     546             : }
     547             : 
     548        5282 : unsigned APInt::countLeadingOnesSlowCase() const {
     549        5282 :   unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD;
     550             :   unsigned shift;
     551        5282 :   if (!highWordBits) {
     552             :     highWordBits = APINT_BITS_PER_WORD;
     553             :     shift = 0;
     554             :   } else {
     555         911 :     shift = APINT_BITS_PER_WORD - highWordBits;
     556             :   }
     557        5282 :   int i = getNumWords() - 1;
     558       10564 :   unsigned Count = llvm::countLeadingOnes(U.pVal[i] << shift);
     559        5282 :   if (Count == highWordBits) {
     560        3632 :     for (i--; i >= 0; --i) {
     561        3467 :       if (U.pVal[i] == WORD_MAX)
     562         580 :         Count += APINT_BITS_PER_WORD;
     563             :       else {
     564        2887 :         Count += llvm::countLeadingOnes(U.pVal[i]);
     565        2887 :         break;
     566             :       }
     567             :     }
     568             :   }
     569        5282 :   return Count;
     570             : }
     571             : 
     572        5410 : unsigned APInt::countTrailingZerosSlowCase() const {
     573        5410 :   unsigned Count = 0;
     574             :   unsigned i = 0;
     575       20123 :   for (; i < getNumWords() && U.pVal[i] == 0; ++i)
     576        3101 :     Count += APINT_BITS_PER_WORD;
     577        5410 :   if (i < getNumWords())
     578        9204 :     Count += llvm::countTrailingZeros(U.pVal[i]);
     579       10820 :   return std::min(Count, BitWidth);
     580             : }
     581             : 
     582      307408 : unsigned APInt::countTrailingOnesSlowCase() const {
     583             :   unsigned Count = 0;
     584             :   unsigned i = 0;
     585     1417610 :   for (; i < getNumWords() && U.pVal[i] == WORD_MAX; ++i)
     586      267598 :     Count += APINT_BITS_PER_WORD;
     587      307408 :   if (i < getNumWords())
     588      362278 :     Count += llvm::countTrailingOnes(U.pVal[i]);
     589             :   assert(Count <= BitWidth);
     590      307408 :   return Count;
     591             : }
     592             : 
     593        6241 : unsigned APInt::countPopulationSlowCase() const {
     594             :   unsigned Count = 0;
     595       73025 :   for (unsigned i = 0; i < getNumWords(); ++i)
     596       40362 :     Count += llvm::countPopulation(U.pVal[i]);
     597        6241 :   return Count;
     598             : }
     599             : 
     600        7259 : bool APInt::intersectsSlowCase(const APInt &RHS) const {
     601       67120 :   for (unsigned i = 0, e = getNumWords(); i != e; ++i)
     602       26328 :     if ((U.pVal[i] & RHS.U.pVal[i]) != 0)
     603             :       return true;
     604             : 
     605             :   return false;
     606             : }
     607             : 
     608       15850 : bool APInt::isSubsetOfSlowCase(const APInt &RHS) const {
     609       51718 :   for (unsigned i = 0, e = getNumWords(); i != e; ++i)
     610       24203 :     if ((U.pVal[i] & ~RHS.U.pVal[i]) != 0)
     611             :       return false;
     612             : 
     613             :   return true;
     614             : }
     615             : 
     616       11154 : APInt APInt::byteSwap() const {
     617             :   assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
     618       11154 :   if (BitWidth == 16)
     619        1576 :     return APInt(BitWidth, ByteSwap_16(uint16_t(U.VAL)));
     620       10366 :   if (BitWidth == 32)
     621       14576 :     return APInt(BitWidth, ByteSwap_32(unsigned(U.VAL)));
     622        3078 :   if (BitWidth == 48) {
     623           0 :     unsigned Tmp1 = unsigned(U.VAL >> 16);
     624             :     Tmp1 = ByteSwap_32(Tmp1);
     625           0 :     uint16_t Tmp2 = uint16_t(U.VAL);
     626           0 :     Tmp2 = ByteSwap_16(Tmp2);
     627           0 :     return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
     628             :   }
     629        3078 :   if (BitWidth == 64)
     630        3077 :     return APInt(BitWidth, ByteSwap_64(U.VAL));
     631             : 
     632           1 :   APInt Result(getNumWords() * APINT_BITS_PER_WORD, 0);
     633           6 :   for (unsigned I = 0, N = getNumWords(); I != N; ++I)
     634           4 :     Result.U.pVal[I] = ByteSwap_64(U.pVal[N - I - 1]);
     635           1 :   if (Result.BitWidth != BitWidth) {
     636           1 :     Result.lshrInPlace(Result.BitWidth - BitWidth);
     637           1 :     Result.BitWidth = BitWidth;
     638             :   }
     639             :   return Result;
     640             : }
     641             : 
     642        5337 : APInt APInt::reverseBits() const {
     643        5337 :   switch (BitWidth) {
     644         308 :   case 64:
     645         308 :     return APInt(BitWidth, llvm::reverseBits<uint64_t>(U.VAL));
     646        1072 :   case 32:
     647        2144 :     return APInt(BitWidth, llvm::reverseBits<uint32_t>(U.VAL));
     648         224 :   case 16:
     649         448 :     return APInt(BitWidth, llvm::reverseBits<uint16_t>(U.VAL));
     650         204 :   case 8:
     651         408 :     return APInt(BitWidth, llvm::reverseBits<uint8_t>(U.VAL));
     652             :   default:
     653             :     break;
     654             :   }
     655             : 
     656             :   APInt Val(*this);
     657        3529 :   APInt Reversed(BitWidth, 0);
     658        3529 :   unsigned S = BitWidth;
     659             : 
     660     1163339 :   for (; Val != 0; Val.lshrInPlace(1)) {
     661     1159810 :     Reversed <<= 1;
     662     1159810 :     Reversed |= Val[0];
     663     1159810 :     --S;
     664             :   }
     665             : 
     666        3529 :   Reversed <<= S;
     667             :   return Reversed;
     668             : }
     669             : 
     670        2328 : APInt llvm::APIntOps::GreatestCommonDivisor(APInt A, APInt B) {
     671             :   // Fast-path a common case.
     672        2328 :   if (A == B) return A;
     673             : 
     674             :   // Corner cases: if either operand is zero, the other is the gcd.
     675        1653 :   if (!A) return B;
     676         897 :   if (!B) return A;
     677             : 
     678             :   // Count common powers of 2 and remove all other powers of 2.
     679             :   unsigned Pow2;
     680             :   {
     681         721 :     unsigned Pow2_A = A.countTrailingZeros();
     682         721 :     unsigned Pow2_B = B.countTrailingZeros();
     683         721 :     if (Pow2_A > Pow2_B) {
     684          93 :       A.lshrInPlace(Pow2_A - Pow2_B);
     685             :       Pow2 = Pow2_B;
     686         628 :     } else if (Pow2_B > Pow2_A) {
     687         469 :       B.lshrInPlace(Pow2_B - Pow2_A);
     688             :       Pow2 = Pow2_A;
     689             :     } else {
     690             :       Pow2 = Pow2_A;
     691             :     }
     692             :   }
     693             : 
     694             :   // Both operands are odd multiples of 2^Pow_2:
     695             :   //
     696             :   //   gcd(a, b) = gcd(|a - b| / 2^i, min(a, b))
     697             :   //
     698             :   // This is a modified version of Stein's algorithm, taking advantage of
     699             :   // efficient countTrailingZeros().
     700        3063 :   while (A != B) {
     701        2342 :     if (A.ugt(B)) {
     702         412 :       A -= B;
     703         412 :       A.lshrInPlace(A.countTrailingZeros() - Pow2);
     704             :     } else {
     705        1930 :       B -= A;
     706        1930 :       B.lshrInPlace(B.countTrailingZeros() - Pow2);
     707             :     }
     708             :   }
     709             : 
     710             :   return A;
     711             : }
     712             : 
     713          40 : APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) {
     714             :   union {
     715             :     double D;
     716             :     uint64_t I;
     717             :   } T;
     718             :   T.D = Double;
     719             : 
     720             :   // Get the sign bit from the highest order bit
     721          40 :   bool isNeg = T.I >> 63;
     722             : 
     723             :   // Get the 11-bit exponent and adjust for the 1023 bit bias
     724          40 :   int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
     725             : 
     726             :   // If the exponent is negative, the value is < 0 so just return 0.
     727          40 :   if (exp < 0)
     728             :     return APInt(width, 0u);
     729             : 
     730             :   // Extract the mantissa by clearing the top 12 bits (sign + exponent).
     731          24 :   uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
     732             : 
     733             :   // If the exponent doesn't shift all bits out of the mantissa
     734          24 :   if (exp < 52)
     735          32 :     return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
     736          40 :                     APInt(width, mantissa >> (52 - exp));
     737             : 
     738             :   // If the client didn't provide enough bits for us to shift the mantissa into
     739             :   // then the result is undefined, just return 0
     740           0 :   if (width <= exp - 52)
     741             :     return APInt(width, 0);
     742             : 
     743             :   // Otherwise, we have to shift the mantissa bits up to the right location
     744             :   APInt Tmp(width, mantissa);
     745           0 :   Tmp <<= (unsigned)exp - 52;
     746           0 :   return isNeg ? -Tmp : Tmp;
     747             : }
     748             : 
     749             : /// This function converts this APInt to a double.
     750             : /// The layout for double is as following (IEEE Standard 754):
     751             : ///  --------------------------------------
     752             : /// |  Sign    Exponent    Fraction    Bias |
     753             : /// |-------------------------------------- |
     754             : /// |  1[63]   11[62-52]   52[51-00]   1023 |
     755             : ///  --------------------------------------
     756          53 : double APInt::roundToDouble(bool isSigned) const {
     757             : 
     758             :   // Handle the simple case where the value is contained in one uint64_t.
     759             :   // It is wrong to optimize getWord(0) to VAL; there might be more than one word.
     760          53 :   if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
     761          53 :     if (isSigned) {
     762             :       int64_t sext = SignExtend64(getWord(0), BitWidth);
     763          25 :       return double(sext);
     764             :     } else
     765          28 :       return double(getWord(0));
     766             :   }
     767             : 
     768             :   // Determine if the value is negative.
     769           0 :   bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
     770             : 
     771             :   // Construct the absolute value if we're negative.
     772           0 :   APInt Tmp(isNeg ? -(*this) : (*this));
     773             : 
     774             :   // Figure out how many bits we're using.
     775             :   unsigned n = Tmp.getActiveBits();
     776             : 
     777             :   // The exponent (without bias normalization) is just the number of bits
     778             :   // we are using. Note that the sign bit is gone since we constructed the
     779             :   // absolute value.
     780           0 :   uint64_t exp = n;
     781             : 
     782             :   // Return infinity for exponent overflow
     783           0 :   if (exp > 1023) {
     784           0 :     if (!isSigned || !isNeg)
     785             :       return std::numeric_limits<double>::infinity();
     786             :     else
     787           0 :       return -std::numeric_limits<double>::infinity();
     788             :   }
     789           0 :   exp += 1023; // Increment for 1023 bias
     790             : 
     791             :   // Number of bits in mantissa is 52. To obtain the mantissa value, we must
     792             :   // extract the high 52 bits from the correct words in pVal.
     793             :   uint64_t mantissa;
     794           0 :   unsigned hiWord = whichWord(n-1);
     795           0 :   if (hiWord == 0) {
     796           0 :     mantissa = Tmp.U.pVal[0];
     797           0 :     if (n > 52)
     798           0 :       mantissa >>= n - 52; // shift down, we want the top 52 bits.
     799             :   } else {
     800             :     assert(hiWord > 0 && "huh?");
     801           0 :     uint64_t hibits = Tmp.U.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
     802           0 :     uint64_t lobits = Tmp.U.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
     803           0 :     mantissa = hibits | lobits;
     804             :   }
     805             : 
     806             :   // The leading bit of mantissa is implicit, so get rid of it.
     807           0 :   uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
     808             :   union {
     809             :     double D;
     810             :     uint64_t I;
     811             :   } T;
     812           0 :   T.I = sign | (exp << 52) | mantissa;
     813           0 :   return T.D;
     814             : }
     815             : 
     816             : // Truncate to new width.
     817    12512625 : APInt APInt::trunc(unsigned width) const {
     818             :   assert(width < BitWidth && "Invalid APInt Truncate request");
     819             :   assert(width && "Can't truncate to 0 bits");
     820             : 
     821    12512625 :   if (width <= APINT_BITS_PER_WORD)
     822    12465692 :     return APInt(width, getRawData()[0]);
     823             : 
     824             :   APInt Result(getMemory(getNumWords(width)), width);
     825             : 
     826             :   // Copy full words.
     827             :   unsigned i;
     828      279763 :   for (i = 0; i != width / APINT_BITS_PER_WORD; i++)
     829      116415 :     Result.U.pVal[i] = U.pVal[i];
     830             : 
     831             :   // Truncate and copy any partial word.
     832       46933 :   unsigned bits = (0 - width) % APINT_BITS_PER_WORD;
     833       46933 :   if (bits != 0)
     834        2332 :     Result.U.pVal[i] = U.pVal[i] << bits >> bits;
     835             : 
     836             :   return Result;
     837             : }
     838             : 
     839             : // Sign extend to a new width.
     840     5377345 : APInt APInt::sext(unsigned Width) const {
     841             :   assert(Width > BitWidth && "Invalid APInt SignExtend request");
     842             : 
     843     5377345 :   if (Width <= APINT_BITS_PER_WORD)
     844    10075942 :     return APInt(Width, SignExtend64(U.VAL, BitWidth));
     845             : 
     846             :   APInt Result(getMemory(getNumWords(Width)), Width);
     847             : 
     848             :   // Copy words.
     849     1018122 :   std::memcpy(Result.U.pVal, getRawData(), getNumWords() * APINT_WORD_SIZE);
     850             : 
     851             :   // Sign extend the last word since there may be unused bits in the input.
     852      339374 :   Result.U.pVal[getNumWords() - 1] =
     853      678748 :       SignExtend64(Result.U.pVal[getNumWords() - 1],
     854      339374 :                    ((BitWidth - 1) % APINT_BITS_PER_WORD) + 1);
     855             : 
     856             :   // Fill with sign bits.
     857      678748 :   std::memset(Result.U.pVal + getNumWords(), isNegative() ? -1 : 0,
     858      339374 :               (Result.getNumWords() - getNumWords()) * APINT_WORD_SIZE);
     859      339374 :   Result.clearUnusedBits();
     860             :   return Result;
     861             : }
     862             : 
     863             : //  Zero extend to a new width.
     864    10889797 : APInt APInt::zext(unsigned width) const {
     865             :   assert(width > BitWidth && "Invalid APInt ZeroExtend request");
     866             : 
     867    10889797 :   if (width <= APINT_BITS_PER_WORD)
     868    10529706 :     return APInt(width, U.VAL);
     869             : 
     870             :   APInt Result(getMemory(getNumWords(width)), width);
     871             : 
     872             :   // Copy words.
     873     1080273 :   std::memcpy(Result.U.pVal, getRawData(), getNumWords() * APINT_WORD_SIZE);
     874             : 
     875             :   // Zero remaining words.
     876      360091 :   std::memset(Result.U.pVal + getNumWords(), 0,
     877      360091 :               (Result.getNumWords() - getNumWords()) * APINT_WORD_SIZE);
     878             : 
     879             :   return Result;
     880             : }
     881             : 
     882     8016640 : APInt APInt::zextOrTrunc(unsigned width) const {
     883     8016640 :   if (BitWidth < width)
     884     3098534 :     return zext(width);
     885     4918106 :   if (BitWidth > width)
     886     1292326 :     return trunc(width);
     887             :   return *this;
     888             : }
     889             : 
     890     8547035 : APInt APInt::sextOrTrunc(unsigned width) const {
     891     8547035 :   if (BitWidth < width)
     892      712789 :     return sext(width);
     893     7834246 :   if (BitWidth > width)
     894      347100 :     return trunc(width);
     895             :   return *this;
     896             : }
     897             : 
     898      146601 : APInt APInt::zextOrSelf(unsigned width) const {
     899      146601 :   if (BitWidth < width)
     900       60588 :     return zext(width);
     901             :   return *this;
     902             : }
     903             : 
     904        5222 : APInt APInt::sextOrSelf(unsigned width) const {
     905        5222 :   if (BitWidth < width)
     906        5179 :     return sext(width);
     907             :   return *this;
     908             : }
     909             : 
     910             : /// Arithmetic right-shift this APInt by shiftAmt.
     911             : /// Arithmetic right-shift function.
     912        9105 : void APInt::ashrInPlace(const APInt &shiftAmt) {
     913       18210 :   ashrInPlace((unsigned)shiftAmt.getLimitedValue(BitWidth));
     914        9105 : }
     915             : 
     916             : /// Arithmetic right-shift this APInt by shiftAmt.
     917             : /// Arithmetic right-shift function.
     918        2450 : void APInt::ashrSlowCase(unsigned ShiftAmt) {
     919             :   // Don't bother performing a no-op shift.
     920        2450 :   if (!ShiftAmt)
     921             :     return;
     922             : 
     923             :   // Save the original sign bit for later.
     924        2294 :   bool Negative = isNegative();
     925             : 
     926             :   // WordShift is the inter-part shift; BitShift is intra-part shift.
     927        2294 :   unsigned WordShift = ShiftAmt / APINT_BITS_PER_WORD;
     928        2294 :   unsigned BitShift = ShiftAmt % APINT_BITS_PER_WORD;
     929             : 
     930        2294 :   unsigned WordsToMove = getNumWords() - WordShift;
     931        2294 :   if (WordsToMove != 0) {
     932             :     // Sign extend the last word to fill in the unused bits.
     933        6876 :     U.pVal[getNumWords() - 1] = SignExtend64(
     934        2292 :         U.pVal[getNumWords() - 1], ((BitWidth - 1) % APINT_BITS_PER_WORD) + 1);
     935             : 
     936             :     // Fastpath for moving by whole words.
     937        2292 :     if (BitShift == 0) {
     938         206 :       std::memmove(U.pVal, U.pVal + WordShift, WordsToMove * APINT_WORD_SIZE);
     939             :     } else {
     940             :       // Move the words containing significant bits.
     941        5894 :       for (unsigned i = 0; i != WordsToMove - 1; ++i)
     942        3808 :         U.pVal[i] = (U.pVal[i + WordShift] >> BitShift) |
     943        1904 :                     (U.pVal[i + WordShift + 1] << (APINT_BITS_PER_WORD - BitShift));
     944             : 
     945             :       // Handle the last word which has no high bits to copy.
     946        2086 :       U.pVal[WordsToMove - 1] = U.pVal[WordShift + WordsToMove - 1] >> BitShift;
     947             :       // Sign extend one more time.
     948        2086 :       U.pVal[WordsToMove - 1] =
     949        4172 :           SignExtend64(U.pVal[WordsToMove - 1], APINT_BITS_PER_WORD - BitShift);
     950             :     }
     951             :   }
     952             : 
     953             :   // Fill in the remainder based on the original sign.
     954        2294 :   std::memset(U.pVal + WordsToMove, Negative ? -1 : 0,
     955        2294 :               WordShift * APINT_WORD_SIZE);
     956        2294 :   clearUnusedBits();
     957             : }
     958             : 
     959             : /// Logical right-shift this APInt by shiftAmt.
     960             : /// Logical right-shift function.
     961       23383 : void APInt::lshrInPlace(const APInt &shiftAmt) {
     962       46766 :   lshrInPlace((unsigned)shiftAmt.getLimitedValue(BitWidth));
     963       23383 : }
     964             : 
     965             : /// Logical right-shift this APInt by shiftAmt.
     966             : /// Logical right-shift function.
     967     1838863 : void APInt::lshrSlowCase(unsigned ShiftAmt) {
     968     3677726 :   tcShiftRight(U.pVal, getNumWords(), ShiftAmt);
     969     1838863 : }
     970             : 
     971             : /// Left-shift this APInt by shiftAmt.
     972             : /// Left-shift function.
     973      415510 : APInt &APInt::operator<<=(const APInt &shiftAmt) {
     974             :   // It's undefined behavior in C to shift by BitWidth or greater.
     975      831020 :   *this <<= (unsigned)shiftAmt.getLimitedValue(BitWidth);
     976      415510 :   return *this;
     977             : }
     978             : 
     979     1350845 : void APInt::shlSlowCase(unsigned ShiftAmt) {
     980     2701690 :   tcShiftLeft(U.pVal, getNumWords(), ShiftAmt);
     981     1350845 :   clearUnusedBits();
     982     1350845 : }
     983             : 
     984             : // Calculate the rotate amount modulo the bit width.
     985          48 : static unsigned rotateModulo(unsigned BitWidth, const APInt &rotateAmt) {
     986          48 :   unsigned rotBitWidth = rotateAmt.getBitWidth();
     987             :   APInt rot = rotateAmt;
     988          48 :   if (rotBitWidth < BitWidth) {
     989             :     // Extend the rotate APInt, so that the urem doesn't divide by 0.
     990             :     // e.g. APInt(1, 32) would give APInt(1, 0).
     991          28 :     rot = rotateAmt.zext(BitWidth);
     992             :   }
     993         192 :   rot = rot.urem(APInt(rot.getBitWidth(), BitWidth));
     994          96 :   return rot.getLimitedValue(BitWidth);
     995             : }
     996             : 
     997          32 : APInt APInt::rotl(const APInt &rotateAmt) const {
     998          32 :   return rotl(rotateModulo(BitWidth, rotateAmt));
     999             : }
    1000             : 
    1001       26268 : APInt APInt::rotl(unsigned rotateAmt) const {
    1002       26268 :   rotateAmt %= BitWidth;
    1003       26268 :   if (rotateAmt == 0)
    1004             :     return *this;
    1005       78090 :   return shl(rotateAmt) | lshr(BitWidth - rotateAmt);
    1006             : }
    1007             : 
    1008          16 : APInt APInt::rotr(const APInt &rotateAmt) const {
    1009          16 :   return rotr(rotateModulo(BitWidth, rotateAmt));
    1010             : }
    1011             : 
    1012         417 : APInt APInt::rotr(unsigned rotateAmt) const {
    1013         417 :   rotateAmt %= BitWidth;
    1014         417 :   if (rotateAmt == 0)
    1015             :     return *this;
    1016        1005 :   return lshr(rotateAmt) | shl(BitWidth - rotateAmt);
    1017             : }
    1018             : 
    1019             : // Square Root - this method computes and returns the square root of "this".
    1020             : // Three mechanisms are used for computation. For small values (<= 5 bits),
    1021             : // a table lookup is done. This gets some performance for common cases. For
    1022             : // values using less than 52 bits, the value is converted to double and then
    1023             : // the libc sqrt function is called. The result is rounded and then converted
    1024             : // back to a uint64_t which is then used to construct the result. Finally,
    1025             : // the Babylonian method for computing square roots is used.
    1026          21 : APInt APInt::sqrt() const {
    1027             : 
    1028             :   // Determine the magnitude of the value.
    1029             :   unsigned magnitude = getActiveBits();
    1030             : 
    1031             :   // Use a fast table for some small values. This also gets rid of some
    1032             :   // rounding errors in libc sqrt for small values.
    1033          21 :   if (magnitude <= 5) {
    1034             :     static const uint8_t results[32] = {
    1035             :       /*     0 */ 0,
    1036             :       /*  1- 2 */ 1, 1,
    1037             :       /*  3- 6 */ 2, 2, 2, 2,
    1038             :       /*  7-12 */ 3, 3, 3, 3, 3, 3,
    1039             :       /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
    1040             :       /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
    1041             :       /*    31 */ 6
    1042             :     };
    1043          13 :     return APInt(BitWidth, results[ (isSingleWord() ? U.VAL : U.pVal[0]) ]);
    1044             :   }
    1045             : 
    1046             :   // If the magnitude of the value fits in less than 52 bits (the precision of
    1047             :   // an IEEE double precision floating point value), then we can use the
    1048             :   // libc sqrt function which will probably use a hardware sqrt computation.
    1049             :   // This should be faster than the algorithm below.
    1050           8 :   if (magnitude < 52) {
    1051           8 :     return APInt(BitWidth,
    1052           8 :                  uint64_t(::round(::sqrt(double(isSingleWord() ? U.VAL
    1053           8 :                                                                : U.pVal[0])))));
    1054             :   }
    1055             : 
    1056             :   // Okay, all the short cuts are exhausted. We must compute it. The following
    1057             :   // is a classical Babylonian method for computing the square root. This code
    1058             :   // was adapted to APInt from a wikipedia article on such computations.
    1059             :   // See http://www.wikipedia.org/ and go to the page named
    1060             :   // Calculate_an_integer_square_root.
    1061             :   unsigned nbits = BitWidth, i = 4;
    1062             :   APInt testy(BitWidth, 16);
    1063           0 :   APInt x_old(BitWidth, 1);
    1064           0 :   APInt x_new(BitWidth, 0);
    1065           0 :   APInt two(BitWidth, 2);
    1066             : 
    1067             :   // Select a good starting value using binary logarithms.
    1068           0 :   for (;; i += 2, testy = testy.shl(2))
    1069           0 :     if (i >= nbits || this->ule(testy)) {
    1070           0 :       x_old = x_old.shl(i / 2);
    1071           0 :       break;
    1072             :     }
    1073             : 
    1074             :   // Use the Babylonian method to arrive at the integer square root:
    1075             :   for (;;) {
    1076           0 :     x_new = (this->udiv(x_old) + x_old).udiv(two);
    1077           0 :     if (x_old.ule(x_new))
    1078             :       break;
    1079           0 :     x_old = x_new;
    1080             :   }
    1081             : 
    1082             :   // Make sure we return the closest approximation
    1083             :   // NOTE: The rounding calculation below is correct. It will produce an
    1084             :   // off-by-one discrepancy with results from pari/gp. That discrepancy has been
    1085             :   // determined to be a rounding issue with pari/gp as it begins to use a
    1086             :   // floating point representation after 192 bits. There are no discrepancies
    1087             :   // between this algorithm and pari/gp for bit widths < 192 bits.
    1088           0 :   APInt square(x_old * x_old);
    1089           0 :   APInt nextSquare((x_old + 1) * (x_old +1));
    1090           0 :   if (this->ult(square))
    1091             :     return x_old;
    1092             :   assert(this->ule(nextSquare) && "Error in APInt::sqrt computation");
    1093           0 :   APInt midpoint((nextSquare - square).udiv(two));
    1094           0 :   APInt offset(*this - square);
    1095           0 :   if (offset.ult(midpoint))
    1096             :     return x_old;
    1097           0 :   return x_old + 1;
    1098             : }
    1099             : 
    1100             : /// Computes the multiplicative inverse of this APInt for a given modulo. The
    1101             : /// iterative extended Euclidean algorithm is used to solve for this value,
    1102             : /// however we simplify it to speed up calculating only the inverse, and take
    1103             : /// advantage of div+rem calculations. We also use some tricks to avoid copying
    1104             : /// (potentially large) APInts around.
    1105        2571 : APInt APInt::multiplicativeInverse(const APInt& modulo) const {
    1106             :   assert(ult(modulo) && "This APInt must be smaller than the modulo");
    1107             : 
    1108             :   // Using the properties listed at the following web page (accessed 06/21/08):
    1109             :   //   http://www.numbertheory.org/php/euclid.html
    1110             :   // (especially the properties numbered 3, 4 and 9) it can be proved that
    1111             :   // BitWidth bits suffice for all the computations in the algorithm implemented
    1112             :   // below. More precisely, this number of bits suffice if the multiplicative
    1113             :   // inverse exists, but may not suffice for the general extended Euclidean
    1114             :   // algorithm.
    1115             : 
    1116        7713 :   APInt r[2] = { modulo, *this };
    1117       12855 :   APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) };
    1118        2571 :   APInt q(BitWidth, 0);
    1119             : 
    1120             :   unsigned i;
    1121       17709 :   for (i = 0; r[i^1] != 0; i ^= 1) {
    1122             :     // An overview of the math without the confusing bit-flipping:
    1123             :     // q = r[i-2] / r[i-1]
    1124             :     // r[i] = r[i-2] % r[i-1]
    1125             :     // t[i] = t[i-2] - t[i-1] * q
    1126        4189 :     udivrem(r[i], r[i^1], q, r[i]);
    1127        8378 :     t[i] -= t[i^1] * q;
    1128             :   }
    1129             : 
    1130             :   // If this APInt and the modulo are not coprime, there is no multiplicative
    1131             :   // inverse, so return 0. We check this by looking at the next-to-last
    1132             :   // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean
    1133             :   // algorithm.
    1134        5142 :   if (r[i] != 1)
    1135           0 :     return APInt(BitWidth, 0);
    1136             : 
    1137             :   // The next-to-last t is the multiplicative inverse.  However, we are
    1138             :   // interested in a positive inverse. Calculate a positive one from a negative
    1139             :   // one if necessary. A simple addition of the modulo suffices because
    1140             :   // abs(t[i]) is known to be less than *this/2 (see the link above).
    1141        5142 :   if (t[i].isNegative())
    1142         530 :     t[i] += modulo;
    1143             : 
    1144             :   return std::move(t[i]);
    1145             : }
    1146             : 
    1147             : /// Calculate the magic numbers required to implement a signed integer division
    1148             : /// by a constant as a sequence of multiplies, adds and shifts.  Requires that
    1149             : /// the divisor not be 0, 1, or -1.  Taken from "Hacker's Delight", Henry S.
    1150             : /// Warren, Jr., chapter 10.
    1151         356 : APInt::ms APInt::magic() const {
    1152             :   const APInt& d = *this;
    1153             :   unsigned p;
    1154             :   APInt ad, anc, delta, q1, r1, q2, r2, t;
    1155         356 :   APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
    1156             :   struct ms mag;
    1157             : 
    1158         712 :   ad = d.abs();
    1159         712 :   t = signedMin + (d.lshr(d.getBitWidth() - 1));
    1160        2136 :   anc = t - 1 - t.urem(ad);   // absolute value of nc
    1161         356 :   p = d.getBitWidth() - 1;    // initialize p
    1162         712 :   q1 = signedMin.udiv(anc);   // initialize q1 = 2p/abs(nc)
    1163        1068 :   r1 = signedMin - q1*anc;    // initialize r1 = rem(2p,abs(nc))
    1164         712 :   q2 = signedMin.udiv(ad);    // initialize q2 = 2p/abs(d)
    1165        1068 :   r2 = signedMin - q2*ad;     // initialize r2 = rem(2p,abs(d))
    1166             :   do {
    1167        1679 :     p = p + 1;
    1168        1679 :     q1 = q1<<1;          // update q1 = 2p/abs(nc)
    1169        1679 :     r1 = r1<<1;          // update r1 = rem(2p/abs(nc))
    1170        1679 :     if (r1.uge(anc)) {  // must be unsigned comparison
    1171          16 :       q1 = q1 + 1;
    1172          16 :       r1 = r1 - anc;
    1173             :     }
    1174        1679 :     q2 = q2<<1;          // update q2 = 2p/abs(d)
    1175        1679 :     r2 = r2<<1;          // update r2 = rem(2p/abs(d))
    1176        1679 :     if (r2.uge(ad)) {   // must be unsigned comparison
    1177         685 :       q2 = q2 + 1;
    1178         685 :       r2 = r2 - ad;
    1179             :     }
    1180        1679 :     delta = ad - r2;
    1181        2035 :   } while (q1.ult(delta) || (q1 == delta && r1 == 0));
    1182             : 
    1183         712 :   mag.m = q2 + 1;
    1184         726 :   if (d.isNegative()) mag.m = -mag.m;   // resulting magic number
    1185         356 :   mag.s = p - d.getBitWidth();          // resulting shift
    1186         356 :   return mag;
    1187             : }
    1188             : 
    1189             : /// Calculate the magic numbers required to implement an unsigned integer
    1190             : /// division by a constant as a sequence of multiplies, adds and shifts.
    1191             : /// Requires that the divisor not be 0.  Taken from "Hacker's Delight", Henry
    1192             : /// S. Warren, Jr., chapter 10.
    1193             : /// LeadingZeros can be used to simplify the calculation if the upper bits
    1194             : /// of the divided value are known zero.
    1195         551 : APInt::mu APInt::magicu(unsigned LeadingZeros) const {
    1196             :   const APInt& d = *this;
    1197             :   unsigned p;
    1198             :   APInt nc, delta, q1, r1, q2, r2;
    1199             :   struct mu magu;
    1200         551 :   magu.a = 0;               // initialize "add" indicator
    1201        1102 :   APInt allOnes = APInt::getAllOnesValue(d.getBitWidth()).lshr(LeadingZeros);
    1202         551 :   APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
    1203         551 :   APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());
    1204             : 
    1205        2755 :   nc = allOnes - (allOnes - d).urem(d);
    1206         551 :   p = d.getBitWidth() - 1;  // initialize p
    1207        1102 :   q1 = signedMin.udiv(nc);  // initialize q1 = 2p/nc
    1208        1653 :   r1 = signedMin - q1*nc;   // initialize r1 = rem(2p,nc)
    1209        1102 :   q2 = signedMax.udiv(d);   // initialize q2 = (2p-1)/d
    1210        1653 :   r2 = signedMax - q2*d;    // initialize r2 = rem((2p-1),d)
    1211             :   do {
    1212        3951 :     p = p + 1;
    1213        7902 :     if (r1.uge(nc - r1)) {
    1214        1448 :       q1 = q1 + q1 + 1;  // update q1
    1215        1448 :       r1 = r1 + r1 - nc; // update r1
    1216             :     }
    1217             :     else {
    1218        3227 :       q1 = q1+q1; // update q1
    1219        3227 :       r1 = r1+r1; // update r1
    1220             :     }
    1221       15804 :     if ((r2 + 1).uge(d - r2)) {
    1222        1589 :       if (q2.uge(signedMax)) magu.a = 1;
    1223        3178 :       q2 = q2+q2 + 1;     // update q2
    1224        4767 :       r2 = r2+r2 + 1 - d; // update r2
    1225             :     }
    1226             :     else {
    1227        2362 :       if (q2.uge(signedMin)) magu.a = 1;
    1228        2362 :       q2 = q2+q2;     // update q2
    1229        4724 :       r2 = r2+r2 + 1; // update r2
    1230             :     }
    1231        7902 :     delta = d - 1 - r2;
    1232        7902 :   } while (p < d.getBitWidth()*2 &&
    1233         551 :            (q1.ult(delta) || (q1 == delta && r1 == 0)));
    1234         551 :   magu.m = q2 + 1; // resulting magic number
    1235         551 :   magu.s = p - d.getBitWidth();  // resulting shift
    1236         551 :   return magu;
    1237             : }
    1238             : 
    1239             : /// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
    1240             : /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
    1241             : /// variables here have the same names as in the algorithm. Comments explain
    1242             : /// the algorithm and any deviation from it.
    1243        2816 : static void KnuthDiv(uint32_t *u, uint32_t *v, uint32_t *q, uint32_t* r,
    1244             :                      unsigned m, unsigned n) {
    1245             :   assert(u && "Must provide dividend");
    1246             :   assert(v && "Must provide divisor");
    1247             :   assert(q && "Must provide quotient");
    1248             :   assert(u != v && u != q && v != q && "Must use different memory");
    1249             :   assert(n>1 && "n must be > 1");
    1250             : 
    1251             :   // b denotes the base of the number system. In our case b is 2^32.
    1252             :   const uint64_t b = uint64_t(1) << 32;
    1253             : 
    1254             : // The DEBUG macros here tend to be spam in the debug output if you're not
    1255             : // debugging this code. Disable them unless KNUTH_DEBUG is defined.
    1256             : #pragma push_macro("LLVM_DEBUG")
    1257             : #ifndef KNUTH_DEBUG
    1258             : #undef LLVM_DEBUG
    1259             : #define LLVM_DEBUG(X)                                                          \
    1260             :   do {                                                                         \
    1261             :   } while (false)
    1262             : #endif
    1263             : 
    1264             :   LLVM_DEBUG(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n');
    1265             :   LLVM_DEBUG(dbgs() << "KnuthDiv: original:");
    1266             :   LLVM_DEBUG(for (int i = m + n; i >= 0; i--) dbgs() << " " << u[i]);
    1267             :   LLVM_DEBUG(dbgs() << " by");
    1268             :   LLVM_DEBUG(for (int i = n; i > 0; i--) dbgs() << " " << v[i - 1]);
    1269             :   LLVM_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        5632 :   unsigned shift = countLeadingZeros(v[n-1]);
    1279             :   uint32_t v_carry = 0;
    1280             :   uint32_t u_carry = 0;
    1281        2816 :   if (shift) {
    1282       56937 :     for (unsigned i = 0; i < m+n; ++i) {
    1283       27175 :       uint32_t u_tmp = u[i] >> (32 - shift);
    1284       27175 :       u[i] = (u[i] << shift) | u_carry;
    1285             :       u_carry = u_tmp;
    1286             :     }
    1287       48395 :     for (unsigned i = 0; i < n; ++i) {
    1288       22904 :       uint32_t v_tmp = v[i] >> (32 - shift);
    1289       22904 :       v[i] = (v[i] << shift) | v_carry;
    1290             :       v_carry = v_tmp;
    1291             :     }
    1292             :   }
    1293        2816 :   u[m+n] = u_carry;
    1294             : 
    1295             :   LLVM_DEBUG(dbgs() << "KnuthDiv:   normal:");
    1296             :   LLVM_DEBUG(for (int i = m + n; i >= 0; i--) dbgs() << " " << u[i]);
    1297             :   LLVM_DEBUG(dbgs() << " by");
    1298             :   LLVM_DEBUG(for (int i = n; i > 0; i--) dbgs() << " " << v[i - 1]);
    1299             :   LLVM_DEBUG(dbgs() << '\n');
    1300             : 
    1301             :   // D2. [Initialize j.]  Set j to m. This is the loop counter over the places.
    1302        2816 :   int j = m;
    1303             :   do {
    1304             :     LLVM_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        7250 :     uint64_t dividend = Make_64(u[j+n], u[j+n-1]);
    1314             :     LLVM_DEBUG(dbgs() << "KnuthDiv: dividend == " << dividend << '\n');
    1315        7250 :     uint64_t qp = dividend / v[n-1];
    1316        7250 :     uint64_t rp = dividend % v[n-1];
    1317        7250 :     if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
    1318         663 :       qp--;
    1319         663 :       rp += v[n-1];
    1320         663 :       if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
    1321         161 :         qp--;
    1322             :     }
    1323             :     LLVM_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      245232 :     for (unsigned i = 0; i < n; ++i) {
    1335      118991 :       uint64_t p = uint64_t(qp) * uint64_t(v[i]);
    1336      118991 :       int64_t subres = int64_t(u[j+i]) - borrow - Lo_32(p);
    1337      237982 :       u[j+i] = Lo_32(subres);
    1338      118991 :       borrow = Hi_32(p) - Hi_32(subres);
    1339             :       LLVM_DEBUG(dbgs() << "KnuthDiv: u[j+i] = " << u[j + i]
    1340             :                         << ", borrow = " << borrow << '\n');
    1341             :     }
    1342        7250 :     bool isNeg = u[j+n] < borrow;
    1343        7250 :     u[j+n] -= Lo_32(borrow);
    1344             : 
    1345             :     LLVM_DEBUG(dbgs() << "KnuthDiv: after subtraction:");
    1346             :     LLVM_DEBUG(for (int i = m + n; i >= 0; i--) dbgs() << " " << u[i]);
    1347             :     LLVM_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       14500 :     q[j] = Lo_32(qp);
    1352        7250 :     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             :     LLVM_DEBUG(dbgs() << "KnuthDiv: after correction:");
    1369             :     LLVM_DEBUG(for (int i = m + n; i >= 0; i--) dbgs() << " " << u[i]);
    1370             :     LLVM_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        7250 :   } while (--j >= 0);
    1374             : 
    1375             :   LLVM_DEBUG(dbgs() << "KnuthDiv: quotient:");
    1376             :   LLVM_DEBUG(for (int i = m; i >= 0; i--) dbgs() << " " << q[i]);
    1377             :   LLVM_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        2816 :   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             :       LLVM_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             :         LLVM_DEBUG(dbgs() << " " << r[i]);
    1393             :       }
    1394             :     } else {
    1395          38 :       for (int i = n-1; i >= 0; i--) {
    1396          28 :         r[i] = u[i];
    1397             :         LLVM_DEBUG(dbgs() << " " << r[i]);
    1398             :       }
    1399             :     }
    1400             :     LLVM_DEBUG(dbgs() << '\n');
    1401             :   }
    1402             :   LLVM_DEBUG(dbgs() << '\n');
    1403             : 
    1404             : #pragma pop_macro("LLVM_DEBUG")
    1405        2816 : }
    1406             : 
    1407       53326 : 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       53326 :   unsigned n = rhsWords * 2;
    1419       53326 :   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       53326 :   if ((Remainder?4:3)*n+2*m+1 <= 128) {
    1429             :     U = &SPACE[0];
    1430       53124 :     V = &SPACE[m+n+1];
    1431       53124 :     Q = &SPACE[(m+n+1) + n];
    1432       53124 :     if (Remainder)
    1433       47166 :       R = &SPACE[(m+n+1) + n + (m+n)];
    1434             :   } else {
    1435         202 :     U = new uint32_t[m + n + 1];
    1436         202 :     V = new uint32_t[n];
    1437         202 :     Q = new uint32_t[m+n];
    1438         202 :     if (Remainder)
    1439           8 :       R = new uint32_t[n];
    1440             :   }
    1441             : 
    1442             :   // Initialize the dividend
    1443       53326 :   memset(U, 0, (m+n+1)*sizeof(uint32_t));
    1444      288444 :   for (unsigned i = 0; i < lhsWords; ++i) {
    1445      117559 :     uint64_t tmp = LHS[i];
    1446      235118 :     U[i * 2] = Lo_32(tmp);
    1447      235118 :     U[i * 2 + 1] = Hi_32(tmp);
    1448             :   }
    1449       53326 :   U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
    1450             : 
    1451             :   // Initialize the divisor
    1452       53326 :   memset(V, 0, (n)*sizeof(uint32_t));
    1453      181994 :   for (unsigned i = 0; i < rhsWords; ++i) {
    1454       64334 :     uint64_t tmp = RHS[i];
    1455      128668 :     V[i * 2] = Lo_32(tmp);
    1456      128668 :     V[i * 2 + 1] = Hi_32(tmp);
    1457             :   }
    1458             : 
    1459             :   // initialize the quotient and remainder
    1460       53326 :   memset(Q, 0, (m+n) * sizeof(uint32_t));
    1461       53326 :   if (Remainder)
    1462       47174 :     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      155872 :   for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
    1469             :     n--;
    1470       51273 :     m++;
    1471             :   }
    1472       78016 :   for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
    1473       24690 :     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       53326 :   if (n == 1) {
    1483       50510 :     uint32_t divisor = V[0];
    1484             :     uint32_t remainder = 0;
    1485      229619 :     for (int i = m; i >= 0; i--) {
    1486      179109 :       uint64_t partial_dividend = Make_64(remainder, U[i]);
    1487      179109 :       if (partial_dividend == 0) {
    1488         301 :         Q[i] = 0;
    1489             :         remainder = 0;
    1490      178808 :       } else if (partial_dividend < divisor) {
    1491        5199 :         Q[i] = 0;
    1492             :         remainder = Lo_32(partial_dividend);
    1493      173609 :       } else if (partial_dividend == divisor) {
    1494          19 :         Q[i] = 1;
    1495             :         remainder = 0;
    1496             :       } else {
    1497      347180 :         Q[i] = Lo_32(partial_dividend / divisor);
    1498      173590 :         remainder = Lo_32(partial_dividend - (Q[i] * divisor));
    1499             :       }
    1500             :     }
    1501       50510 :     if (R)
    1502       47124 :       R[0] = remainder;
    1503             :   } else {
    1504             :     // Now we're ready to invoke the Knuth classical divide algorithm. In this
    1505             :     // case n > 1.
    1506        2816 :     KnuthDiv(U, V, Q, R, m, n);
    1507             :   }
    1508             : 
    1509             :   // If the caller wants the quotient
    1510       53326 :   if (Quotient) {
    1511      287506 :     for (unsigned i = 0; i < lhsWords; ++i)
    1512      234210 :       Quotient[i] = Make_64(Q[i*2+1], Q[i*2]);
    1513             :   }
    1514             : 
    1515             :   // If the caller wants the remainder
    1516       53326 :   if (Remainder) {
    1517      142298 :     for (unsigned i = 0; i < rhsWords; ++i)
    1518       95124 :       Remainder[i] = Make_64(R[i*2+1], R[i*2]);
    1519             :   }
    1520             : 
    1521             :   // Clean up the memory we allocated.
    1522       53326 :   if (U != &SPACE[0]) {
    1523         202 :     delete [] U;
    1524         202 :     delete [] V;
    1525         202 :     delete [] Q;
    1526         202 :     delete [] R;
    1527             :   }
    1528       53326 : }
    1529             : 
    1530    20944632 : 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    20944632 :   if (isSingleWord()) {
    1535             :     assert(RHS.U.VAL != 0 && "Divide by zero?");
    1536    20921518 :     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       23114 :   if (!lhsWords)
    1547             :     // 0 / X ===> 0
    1548             :     return APInt(BitWidth, 0);
    1549       21858 :   if (rhsBits == 1)
    1550             :     // X / 1 ===> X
    1551             :     return *this;
    1552       26166 :   if (lhsWords < rhsWords || this->ult(RHS))
    1553             :     // X / Y ===> 0, iff X < Y
    1554             :     return APInt(BitWidth, 0);
    1555       12274 :   if (*this == RHS)
    1556             :     // X / X ===> 1
    1557             :     return APInt(BitWidth, 1);
    1558       11381 :   if (lhsWords == 1) // rhsWords is 1 if lhsWords is 1.
    1559             :     // All high words are zero, just use native divide
    1560        5231 :     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        6150 :   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    20499022 : APInt APInt::sdiv(const APInt &RHS) const {
    1602    40998044 :   if (isNegative()) {
    1603       12524 :     if (RHS.isNegative())
    1604        3710 :       return (-(*this)).udiv(-RHS);
    1605       22080 :     return -((-(*this)).udiv(RHS));
    1606             :   }
    1607    40985520 :   if (RHS.isNegative())
    1608        8920 :     return -(this->udiv(-RHS));
    1609    20490530 :   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      245502 : APInt APInt::urem(const APInt &RHS) const {
    1624             :   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
    1625      245502 :   if (isSingleWord()) {
    1626             :     assert(RHS.U.VAL != 0 && "Remainder by zero?");
    1627      245469 :     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       23208 : APInt APInt::srem(const APInt &RHS) const {
    1694       46416 :   if (isNegative()) {
    1695       10902 :     if (RHS.isNegative())
    1696        3918 :       return -((-(*this)).urem(-RHS));
    1697       19192 :     return -((-(*this)).urem(RHS));
    1698             :   }
    1699       35514 :   if (RHS.isNegative())
    1700        6843 :     return this->urem(-RHS);
    1701       15476 :   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       97352 : 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       97352 :   unsigned BitWidth = LHS.BitWidth;
    1719             : 
    1720             :   // First, deal with the easy case
    1721       97352 :   if (LHS.isSingleWord()) {
    1722             :     assert(RHS.U.VAL != 0 && "Divide by zero?");
    1723       94468 :     uint64_t QuotVal = LHS.U.VAL / RHS.U.VAL;
    1724       94468 :     uint64_t RemVal = LHS.U.VAL % RHS.U.VAL;
    1725       94468 :     Quotient = APInt(BitWidth, QuotVal);
    1726       94468 :     Remainder = APInt(BitWidth, RemVal);
    1727       94468 :     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        2884 :   if (lhsWords == 0) {
    1738           0 :     Quotient = 0;                // 0 / Y ===> 0
    1739           0 :     Remainder = 0;               // 0 % Y ===> 0
    1740           0 :     return;
    1741             :   }
    1742             : 
    1743        2884 :   if (rhsBits == 1) {
    1744         132 :     Quotient = LHS;             // X / 1 ===> X
    1745         132 :     Remainder = 0;              // X % 1 ===> 0
    1746             :   }
    1747             : 
    1748        5768 :   if (lhsWords < rhsWords || LHS.ult(RHS)) {
    1749         364 :     Remainder = LHS;            // X % Y ===> X, iff X < Y
    1750         364 :     Quotient = 0;               // X / Y ===> 0, iff X < Y
    1751         364 :     return;
    1752             :   }
    1753             : 
    1754        2520 :   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        2509 :   Quotient.reallocate(BitWidth);
    1765        2509 :   Remainder.reallocate(BitWidth);
    1766             : 
    1767        2509 :   if (lhsWords == 1) { // rhsWords is 1 if lhsWords is 1.
    1768             :     // There is only one word to consider so use the native versions.
    1769        2196 :     uint64_t lhsValue = LHS.U.pVal[0];
    1770        2196 :     uint64_t rhsValue = RHS.U.pVal[0];
    1771        2196 :     Quotient = lhsValue / rhsValue;
    1772        2196 :     Remainder = lhsValue % rhsValue;
    1773        2196 :     return;
    1774             :   }
    1775             : 
    1776             :   // Okay, lets do it the long way
    1777         313 :   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         313 :   std::memset(Quotient.U.pVal + lhsWords, 0,
    1781         313 :               (getNumWords(BitWidth) - lhsWords) * APINT_WORD_SIZE);
    1782         313 :   std::memset(Remainder.U.pVal + rhsWords, 0,
    1783         313 :               (getNumWords(BitWidth) - rhsWords) * APINT_WORD_SIZE);
    1784             : }
    1785             : 
    1786       96207 : void APInt::udivrem(const APInt &LHS, uint64_t RHS, APInt &Quotient,
    1787             :                     uint64_t &Remainder) {
    1788             :   assert(RHS != 0 && "Divide by zero?");
    1789       96207 :   unsigned BitWidth = LHS.BitWidth;
    1790             : 
    1791             :   // First, deal with the easy case
    1792       96207 :   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       96204 :   if (lhsWords == 0) {
    1804           0 :     Quotient = 0;                // 0 / Y ===> 0
    1805           0 :     Remainder = 0;               // 0 % Y ===> 0
    1806           0 :     return;
    1807             :   }
    1808             : 
    1809       96204 :   if (RHS == 1) {
    1810           0 :     Quotient = LHS;             // X / 1 ===> X
    1811           0 :     Remainder = 0;              // X % 1 ===> 0
    1812             :   }
    1813             : 
    1814       96204 :   if (LHS.ult(RHS)) {
    1815        2856 :     Remainder = LHS.getZExtValue(); // X % Y ===> X, iff X < Y
    1816        2856 :     Quotient = 0;                   // X / Y ===> 0, iff X < Y
    1817        2856 :     return;
    1818             :   }
    1819             : 
    1820       93348 :   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       93322 :   Quotient.reallocate(BitWidth);
    1830             : 
    1831       93322 :   if (lhsWords == 1) { // rhsWords is 1 if lhsWords is 1.
    1832             :     // There is only one word to consider so use the native versions.
    1833       46491 :     uint64_t lhsValue = LHS.U.pVal[0];
    1834       46491 :     Quotient = lhsValue / RHS;
    1835       46491 :     Remainder = lhsValue % RHS;
    1836       46491 :     return;
    1837             :   }
    1838             : 
    1839             :   // Okay, lets do it the long way
    1840       46831 :   divide(LHS.U.pVal, lhsWords, &RHS, 1, Quotient.U.pVal, &Remainder);
    1841             :   // Clear the rest of the Quotient.
    1842       46831 :   std::memset(Quotient.U.pVal + lhsWords, 0,
    1843       46831 :               (getNumWords(BitWidth) - lhsWords) * APINT_WORD_SIZE);
    1844             : }
    1845             : 
    1846       20911 : void APInt::sdivrem(const APInt &LHS, const APInt &RHS,
    1847             :                     APInt &Quotient, APInt &Remainder) {
    1848       41822 :   if (LHS.isNegative()) {
    1849         322 :     if (RHS.isNegative())
    1850          95 :       APInt::udivrem(-LHS, -RHS, Quotient, Remainder);
    1851             :     else {
    1852         426 :       APInt::udivrem(-LHS, RHS, Quotient, Remainder);
    1853             :       Quotient.negate();
    1854             :     }
    1855             :     Remainder.negate();
    1856       41500 :   } else if (RHS.isNegative()) {
    1857         309 :     APInt::udivrem(LHS, -RHS, Quotient, Remainder);
    1858             :     Quotient.negate();
    1859             :   } else {
    1860       20647 :     APInt::udivrem(LHS, RHS, Quotient, Remainder);
    1861             :   }
    1862       20911 : }
    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      321579 : APInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const {
    1885      321579 :   APInt Res = *this+RHS;
    1886      643046 :   Overflow = isNonNegative() == RHS.isNonNegative() &&
    1887             :              Res.isNonNegative() != isNonNegative();
    1888      321579 :   return Res;
    1889             : }
    1890             : 
    1891       78655 : APInt APInt::uadd_ov(const APInt &RHS, bool &Overflow) const {
    1892       78655 :   APInt Res = *this+RHS;
    1893       78655 :   Overflow = Res.ult(RHS);
    1894       78655 :   return Res;
    1895             : }
    1896             : 
    1897       60133 : APInt APInt::ssub_ov(const APInt &RHS, bool &Overflow) const {
    1898       60133 :   APInt Res = *this - RHS;
    1899       60321 :   Overflow = isNonNegative() != RHS.isNonNegative() &&
    1900             :              Res.isNonNegative() != isNonNegative();
    1901       60133 :   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    20172136 : APInt APInt::sdiv_ov(const APInt &RHS, bool &Overflow) const {
    1911             :   // MININT/-1  -->  overflow.
    1912    20172136 :   Overflow = isMinSignedValue() && RHS.isAllOnesValue();
    1913    20172136 :   return sdiv(RHS);
    1914             : }
    1915             : 
    1916        5310 : APInt APInt::smul_ov(const APInt &RHS, bool &Overflow) const {
    1917        5310 :   APInt Res = *this * RHS;
    1918             : 
    1919       10620 :   if (*this != 0 && RHS != 0)
    1920       26445 :     Overflow = Res.sdiv(RHS) != *this || Res.sdiv(*this) != RHS;
    1921             :   else
    1922          18 :     Overflow = false;
    1923        5310 :   return Res;
    1924             : }
    1925             : 
    1926       14016 : APInt APInt::umul_ov(const APInt &RHS, bool &Overflow) const {
    1927       14016 :   APInt Res = *this * RHS;
    1928             : 
    1929       21292 :   if (*this != 0 && RHS != 0)
    1930       29529 :     Overflow = Res.udiv(RHS) != *this || Res.udiv(*this) != RHS;
    1931             :   else
    1932        6750 :     Overflow = false;
    1933       14016 :   return Res;
    1934             : }
    1935             : 
    1936      315857 : APInt APInt::sshl_ov(const APInt &ShAmt, bool &Overflow) const {
    1937      631714 :   Overflow = ShAmt.uge(getBitWidth());
    1938      315857 :   if (Overflow)
    1939             :     return APInt(BitWidth, 0);
    1940             : 
    1941      315857 :   if (isNonNegative()) // Don't allow sign change.
    1942      631714 :     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     3248898 : 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     3248898 :   bool isNeg = *p == '-';
    1972     3248898 :   if (*p == '-' || *p == '+') {
    1973       51542 :     p++;
    1974       51542 :     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     3248898 :   if (isSingleWord())
    1985     3247581 :     U.VAL = 0;
    1986             :   else
    1987        1317 :     U.pVal = getClearedMemory(getNumWords());
    1988             : 
    1989             :   // Figure out if we can shift instead of multiply
    1990     3248898 :   unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
    1991             : 
    1992             :   // Enter digit traversal loop
    1993    12484916 :   for (StringRef::iterator e = str.end(); p != e; ++p) {
    1994     4618009 :     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     4618009 :     if (slen > 1) {
    1999     2381255 :       if (shift)
    2000        9094 :         *this <<= shift;
    2001             :       else
    2002     2372161 :         *this *= radix;
    2003             :     }
    2004             : 
    2005             :     // Add in the digit we just interpreted
    2006     4618009 :     *this += digit;
    2007             :   }
    2008             :   // If its negative, put it in two's complement form
    2009     3248898 :   if (isNeg)
    2010             :     this->negate();
    2011     3248898 : }
    2012             : 
    2013     2405855 : 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     2405855 :   if (formatAsCLiteral) {
    2021         935 :     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         900 :       case 16:
    2033             :         Prefix = "0x";
    2034         900 :         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     2405855 :   if (*this == 0) {
    2042      417690 :     while (*Prefix) {
    2043           5 :       Str.push_back(*Prefix);
    2044           5 :       ++Prefix;
    2045             :     };
    2046      417680 :     Str.push_back('0');
    2047     2820215 :     return;
    2048             :   }
    2049             : 
    2050             :   static const char Digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    2051             : 
    2052     1988175 :   if (isSingleWord()) {
    2053             :     char Buffer[65];
    2054             :     char *BufPtr = std::end(Buffer);
    2055             : 
    2056             :     uint64_t N;
    2057     1984855 :     if (!Signed) {
    2058             :       N = getZExtValue();
    2059             :     } else {
    2060             :       int64_t I = getSExtValue();
    2061     1350338 :       if (I >= 0) {
    2062     1302850 :         N = I;
    2063             :       } else {
    2064       47488 :         Str.push_back('-');
    2065       47488 :         N = -(uint64_t)I;
    2066             :       }
    2067             :     }
    2068             : 
    2069     1986607 :     while (*Prefix) {
    2070         876 :       Str.push_back(*Prefix);
    2071         876 :       ++Prefix;
    2072             :     };
    2073             : 
    2074    33183607 :     while (N) {
    2075    15599376 :       *--BufPtr = Digits[N % Radix];
    2076    15599376 :       N /= Radix;
    2077             :     }
    2078     1984855 :     Str.append(BufPtr, std::end(Buffer));
    2079             :     return;
    2080             :   }
    2081             : 
    2082             :   APInt Tmp(*this);
    2083             : 
    2084        5213 :   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        5176 :   while (*Prefix) {
    2093         928 :     Str.push_back(*Prefix);
    2094         928 :     ++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        3320 :   if (Radix == 2 || Radix == 8 || Radix == 16) {
    2104             :     // Just shift tmp right for each digit width until it becomes zero
    2105         464 :     unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
    2106         464 :     unsigned MaskAmt = Radix - 1;
    2107             : 
    2108        7888 :     while (Tmp.getBoolValue()) {
    2109        7424 :       unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;
    2110        7424 :       Str.push_back(Digits[Digit]);
    2111             :       Tmp.lshrInPlace(ShiftAmt);
    2112             :     }
    2113             :   } else {
    2114      195254 :     while (Tmp.getBoolValue()) {
    2115             :       uint64_t Digit;
    2116       96199 :       udivrem(Tmp, Radix, Tmp, Digit);
    2117             :       assert(Digit < Radix && "divide failed");
    2118       96199 :       Str.push_back(Digits[Digit]);
    2119             :     }
    2120             :   }
    2121             : 
    2122             :   // Reverse the digits before returning.
    2123        3320 :   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     1321104 : std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const {
    2129             :   SmallString<40> S;
    2130     1321104 :   toString(S, Radix, Signed, /* formatAsCLiteral = */false);
    2131     1321105 :   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     1081024 : void APInt::print(raw_ostream &OS, bool isSigned) const {
    2145             :   SmallString<40> S;
    2146     1081024 :   this->toString(S, 10, isSigned, /* formatAsCLiteral = */false);
    2147             :   OS << S;
    2148     1081024 : }
    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      227578 :   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    12586428 :   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    37759284 :   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     1000898 :   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      388375 :   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     1865809 : void APInt::tcSet(WordType *dst, WordType part, unsigned parts) {
    2193             :   assert(parts > 0);
    2194             : 
    2195     1865809 :   dst[0] = part;
    2196     5783923 :   for (unsigned i = 1; i < parts; i++)
    2197     1959057 :     dst[i] = 0;
    2198     1865809 : }
    2199             : 
    2200             : /* Assign one bignum to another.  */
    2201      946735 : void APInt::tcAssign(WordType *dst, const WordType *src, unsigned parts) {
    2202     3070595 :   for (unsigned i = 0; i < parts; i++)
    2203     1061930 :     dst[i] = src[i];
    2204      946735 : }
    2205             : 
    2206             : /* Returns true if a bignum is zero, false otherwise.  */
    2207       21096 : bool APInt::tcIsZero(const WordType *src, unsigned parts) {
    2208       56676 :   for (unsigned i = 0; i < parts; i++)
    2209       21584 :     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      186912 : int APInt::tcExtractBit(const WordType *parts, unsigned bit) {
    2217      373824 :   return (parts[whichWord(bit)] & maskBit(bit)) != 0;
    2218             : }
    2219             : 
    2220             : /* Set the given bit of a bignum. */
    2221      303590 : void APInt::tcSetBit(WordType *parts, unsigned bit) {
    2222      303590 :   parts[whichWord(bit)] |= maskBit(bit);
    2223      303590 : }
    2224             : 
    2225             : /* Clears the given bit of a bignum. */
    2226         758 : void APInt::tcClearBit(WordType *parts, unsigned bit) {
    2227        1516 :   parts[whichWord(bit)] &= ~maskBit(bit);
    2228         758 : }
    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      388375 : unsigned APInt::tcLSB(const WordType *parts, unsigned n) {
    2233      484639 :   for (unsigned i = 0; i < n; i++) {
    2234      436507 :     if (parts[i] != 0) {
    2235             :       unsigned lsb = partLSB(parts[i]);
    2236             : 
    2237      388375 :       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     1004696 : unsigned APInt::tcMSB(const WordType *parts, unsigned n) {
    2247             :   do {
    2248     1070407 :     --n;
    2249             : 
    2250     1070407 :     if (parts[n] != 0) {
    2251             :       unsigned msb = partMSB(parts[n]);
    2252             : 
    2253     1000898 :       return msb + n * APINT_BITS_PER_WORD;
    2254             :     }
    2255       69509 :   } 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      229612 : APInt::tcExtract(WordType *dst, unsigned dstCount, const WordType *src,
    2266             :                  unsigned srcBits, unsigned srcLSB) {
    2267      229612 :   unsigned dstParts = (srcBits + APINT_BITS_PER_WORD - 1) / APINT_BITS_PER_WORD;
    2268             :   assert(dstParts <= dstCount);
    2269             : 
    2270      229612 :   unsigned firstSrcPart = srcLSB / APINT_BITS_PER_WORD;
    2271      229612 :   tcAssign (dst, src + firstSrcPart, dstParts);
    2272             : 
    2273      229612 :   unsigned shift = srcLSB % APINT_BITS_PER_WORD;
    2274      229612 :   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      229612 :   unsigned n = dstParts * APINT_BITS_PER_WORD - shift;
    2280      229612 :   if (n < srcBits) {
    2281        5185 :     WordType mask = lowBitMask (srcBits - n);
    2282       10370 :     dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
    2283        5185 :                           << n % APINT_BITS_PER_WORD);
    2284      224427 :   } else if (n > srcBits) {
    2285      222839 :     if (srcBits % APINT_BITS_PER_WORD)
    2286      222393 :       dst[dstParts - 1] &= lowBitMask (srcBits % APINT_BITS_PER_WORD);
    2287             :   }
    2288             : 
    2289             :   /* Clear high parts.  */
    2290      329688 :   while (dstParts < dstCount)
    2291       50038 :     dst[dstParts++] = 0;
    2292      229612 : }
    2293             : 
    2294             : /* DST += RHS + C where C is zero or one.  Returns the carry flag.  */
    2295      984986 : APInt::WordType APInt::tcAdd(WordType *dst, const WordType *rhs,
    2296             :                              WordType c, unsigned parts) {
    2297             :   assert(c <= 1);
    2298             : 
    2299     4925404 :   for (unsigned i = 0; i < parts; i++) {
    2300     1970209 :     WordType l = dst[i];
    2301     1970209 :     if (c) {
    2302        3496 :       dst[i] += rhs[i] + 1;
    2303        3496 :       c = (dst[i] <= l);
    2304             :     } else {
    2305     1966713 :       dst[i] += rhs[i];
    2306     1966713 :       c = (dst[i] < l);
    2307             :     }
    2308             :   }
    2309             : 
    2310      984986 :   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      494378 : APInt::WordType APInt::tcAddPart(WordType *dst, WordType src,
    2318             :                                  unsigned parts) {
    2319      535010 :   for (unsigned i = 0; i < parts; ++i) {
    2320      509605 :     dst[i] += src;
    2321      509605 :     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      419108 : APInt::WordType APInt::tcSubtract(WordType *dst, const WordType *rhs,
    2331             :                                   WordType c, unsigned parts) {
    2332             :   assert(c <= 1);
    2333             : 
    2334     1631682 :   for (unsigned i = 0; i < parts; i++) {
    2335      606287 :     WordType l = dst[i];
    2336      606287 :     if (c) {
    2337       68913 :       dst[i] -= rhs[i] + 1;
    2338       68913 :       c = (dst[i] >= l);
    2339             :     } else {
    2340      537374 :       dst[i] -= rhs[i];
    2341      537374 :       c = (dst[i] > l);
    2342             :     }
    2343             :   }
    2344             : 
    2345      419108 :   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      144604 : APInt::WordType APInt::tcSubtractPart(WordType *dst, WordType src,
    2356             :                                       unsigned parts) {
    2357      164064 :   for (unsigned i = 0; i < parts; ++i) {
    2358      151909 :     WordType Dst = dst[i];
    2359      151909 :     dst[i] -= src;
    2360      151909 :     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         139 : void APInt::tcNegate(WordType *dst, unsigned parts) {
    2370         139 :   tcComplement(dst, parts);
    2371             :   tcIncrement(dst, parts);
    2372         139 : }
    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     3334332 : 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     3334332 :   unsigned n = std::min(dstParts, srcParts);
    2395             : 
    2396    46284244 :   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    21474956 :     srcPart = src[i];
    2408             : 
    2409    21474956 :     if (multiplier == 0 || srcPart == 0) {
    2410             :       low = carry;
    2411             :       high = 0;
    2412             :     } else {
    2413    12586428 :       low = lowHalf(srcPart) * lowHalf(multiplier);
    2414    12586428 :       high = highHalf(srcPart) * highHalf(multiplier);
    2415             : 
    2416    12586428 :       mid = lowHalf(srcPart) * highHalf(multiplier);
    2417    12586428 :       high += highHalf(mid);
    2418    12586428 :       mid <<= APINT_BITS_PER_WORD / 2;
    2419    12586428 :       if (low + mid < low)
    2420     3324224 :         high++;
    2421             :       low += mid;
    2422             : 
    2423    12586428 :       mid = highHalf(srcPart) * lowHalf(multiplier);
    2424    12586428 :       high += highHalf(mid);
    2425    12586428 :       mid <<= APINT_BITS_PER_WORD / 2;
    2426    12586428 :       if (low + mid < low)
    2427     5736081 :         high++;
    2428             :       low += mid;
    2429             : 
    2430             :       /* Now add carry.  */
    2431    12586428 :       if (low + carry < low)
    2432     2805127 :         high++;
    2433             :       low += carry;
    2434             :     }
    2435             : 
    2436    21474956 :     if (add) {
    2437             :       /* And now DST[i], and store the new low part there.  */
    2438    21408630 :       if (low + dst[i] < low)
    2439     5487748 :         high++;
    2440    21408630 :       dst[i] += low;
    2441             :     } else
    2442       66326 :       dst[i] = low;
    2443             : 
    2444             :     carry = high;
    2445             :   }
    2446             : 
    2447     3334332 :   if (srcParts < dstParts) {
    2448             :     /* Full multiplication, there is no overflow.  */
    2449             :     assert(srcParts + 1 == dstParts);
    2450      330291 :     dst[srcParts] = carry;
    2451      330291 :     return 0;
    2452             :   }
    2453             : 
    2454             :   /* We overflowed if there is carry.  */
    2455     3004041 :   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     2811260 :   if (multiplier)
    2462     1818913 :     for (unsigned i = dstParts; i < srcParts; i++)
    2463      289379 :       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     1359715 : 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     1359715 :   tcSet(dst, 0, parts);
    2480             : 
    2481     7313961 :   for (unsigned i = 0; i < parts; i++)
    2482     2977123 :     overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
    2483             :                                parts - i, true);
    2484             : 
    2485     1359715 :   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       77938 : 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       77938 :   if (lhsParts > rhsParts)
    2495             :     return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
    2496             : 
    2497             :   assert(dst != lhs && dst != rhs);
    2498             : 
    2499       77938 :   tcSet(dst, 0, rhsParts);
    2500             : 
    2501      594870 :   for (unsigned i = 0; i < lhsParts; i++)
    2502      258466 :     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     3100116 : void APInt::tcShiftLeft(WordType *Dst, unsigned Words, unsigned Count) {
    2558             :   // Don't bother performing a no-op shift.
    2559     3100116 :   if (!Count)
    2560             :     return;
    2561             : 
    2562             :   // WordShift is the inter-part shift; BitShift is the intra-part shift.
    2563     6198128 :   unsigned WordShift = std::min(Count / APINT_BITS_PER_WORD, Words);
    2564     3099064 :   unsigned BitShift = Count % APINT_BITS_PER_WORD;
    2565             : 
    2566             :   // Fastpath for moving by whole words.
    2567     3099064 :   if (BitShift == 0) {
    2568       20708 :     std::memmove(Dst + WordShift, Dst, (Words - WordShift) * APINT_WORD_SIZE);
    2569             :   } else {
    2570    22644475 :     while (Words-- > WordShift) {
    2571    19566119 :       Dst[Words] = Dst[Words - WordShift] << BitShift;
    2572    19566119 :       if (Words > WordShift)
    2573    16487763 :         Dst[Words] |=
    2574    16487763 :           Dst[Words - WordShift - 1] >> (APINT_BITS_PER_WORD - BitShift);
    2575             :     }
    2576             :   }
    2577             : 
    2578             :   // Fill in the remainder with 0s.
    2579     3099064 :   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     2377071 : void APInt::tcShiftRight(WordType *Dst, unsigned Words, unsigned Count) {
    2585             :   // Don't bother performing a no-op shift.
    2586     2377071 :   if (!Count)
    2587             :     return;
    2588             : 
    2589             :   // WordShift is the inter-part shift; BitShift is the intra-part shift.
    2590     4450832 :   unsigned WordShift = std::min(Count / APINT_BITS_PER_WORD, Words);
    2591     2225416 :   unsigned BitShift = Count % APINT_BITS_PER_WORD;
    2592             : 
    2593     2225416 :   unsigned WordsToMove = Words - WordShift;
    2594             :   // Fastpath for moving by whole words.
    2595     2225416 :   if (BitShift == 0) {
    2596      671244 :     std::memmove(Dst, Dst + WordShift, WordsToMove * APINT_WORD_SIZE);
    2597             :   } else {
    2598    19220727 :     for (unsigned i = 0; i != WordsToMove; ++i) {
    2599    17666555 :       Dst[i] = Dst[i + WordShift] >> BitShift;
    2600    17666555 :       if (i + 1 != WordsToMove)
    2601    16113066 :         Dst[i] |= Dst[i + WordShift + 1] << (APINT_BITS_PER_WORD - BitShift);
    2602             :     }
    2603             :   }
    2604             : 
    2605             :   // Fill in the remainder with 0s.
    2606     2225416 :   std::memset(Dst + WordsToMove, 0, WordShift * APINT_WORD_SIZE);
    2607             : }
    2608             : 
    2609             : /* Bitwise and of two bignums.  */
    2610       79014 : void APInt::tcAnd(WordType *dst, const WordType *rhs, unsigned parts) {
    2611      454816 :   for (unsigned i = 0; i < parts; i++)
    2612      187901 :     dst[i] &= rhs[i];
    2613       79014 : }
    2614             : 
    2615             : /* Bitwise inclusive or of two bignums.  */
    2616       72984 : void APInt::tcOr(WordType *dst, const WordType *rhs, unsigned parts) {
    2617      531126 :   for (unsigned i = 0; i < parts; i++)
    2618      229071 :     dst[i] |= rhs[i];
    2619       72984 : }
    2620             : 
    2621             : /* Bitwise exclusive or of two bignums.  */
    2622        1231 : void APInt::tcXor(WordType *dst, const WordType *rhs, unsigned parts) {
    2623        9241 :   for (unsigned i = 0; i < parts; i++)
    2624        4005 :     dst[i] ^= rhs[i];
    2625        1231 : }
    2626             : 
    2627             : /* Complement a bignum in-place.  */
    2628      106518 : void APInt::tcComplement(WordType *dst, unsigned parts) {
    2629      575470 :   for (unsigned i = 0; i < parts; i++)
    2630      234476 :     dst[i] = ~dst[i];
    2631      106518 : }
    2632             : 
    2633             : /* Comparison (unsigned) of two bignums.  */
    2634     2589597 : int APInt::tcCompare(const WordType *lhs, const WordType *rhs,
    2635             :                      unsigned parts) {
    2636     3358231 :   while (parts) {
    2637     3209390 :     parts--;
    2638     3209390 :     if (lhs[parts] != rhs[parts])
    2639     2440756 :       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         129 : void APInt::tcSetLeastSignificantBits(WordType *dst, unsigned parts,
    2648             :                                       unsigned bits) {
    2649             :   unsigned i = 0;
    2650         135 :   while (bits > APINT_BITS_PER_WORD) {
    2651           3 :     dst[i++] = ~(WordType) 0;
    2652           3 :     bits -= APINT_BITS_PER_WORD;
    2653             :   }
    2654             : 
    2655         129 :   if (bits)
    2656          81 :     dst[i++] = ~(WordType) 0 >> (APINT_BITS_PER_WORD - bits);
    2657             : 
    2658         225 :   while (i < parts)
    2659          48 :     dst[i++] = 0;
    2660         129 : }

Generated by: LCOV version 1.13