Home | History | Annotate | Download | only in Support
      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 #define DEBUG_TYPE "apint"
     16 #include "llvm/ADT/APInt.h"
     17 #include "llvm/ADT/FoldingSet.h"
     18 #include "llvm/ADT/Hashing.h"
     19 #include "llvm/ADT/SmallString.h"
     20 #include "llvm/ADT/StringRef.h"
     21 #include "llvm/Support/Debug.h"
     22 #include "llvm/Support/ErrorHandling.h"
     23 #include "llvm/Support/MathExtras.h"
     24 #include "llvm/Support/raw_ostream.h"
     25 #include <cmath>
     26 #include <limits>
     27 #include <cstring>
     28 #include <cstdlib>
     29 using namespace llvm;
     30 
     31 /// A utility function for allocating memory, checking for allocation failures,
     32 /// and ensuring the contents are zeroed.
     33 inline static uint64_t* getClearedMemory(unsigned numWords) {
     34   uint64_t * result = new uint64_t[numWords];
     35   assert(result && "APInt memory allocation fails!");
     36   memset(result, 0, numWords * sizeof(uint64_t));
     37   return result;
     38 }
     39 
     40 /// A utility function for allocating memory and checking for allocation
     41 /// failure.  The content is not zeroed.
     42 inline static uint64_t* getMemory(unsigned numWords) {
     43   uint64_t * result = new uint64_t[numWords];
     44   assert(result && "APInt memory allocation fails!");
     45   return result;
     46 }
     47 
     48 /// A utility function that converts a character to a digit.
     49 inline static unsigned getDigit(char cdigit, uint8_t radix) {
     50   unsigned r;
     51 
     52   if (radix == 16 || radix == 36) {
     53     r = cdigit - '0';
     54     if (r <= 9)
     55       return r;
     56 
     57     r = cdigit - 'A';
     58     if (r <= radix - 11U)
     59       return r + 10;
     60 
     61     r = cdigit - 'a';
     62     if (r <= radix - 11U)
     63       return r + 10;
     64 
     65     radix = 10;
     66   }
     67 
     68   r = cdigit - '0';
     69   if (r < radix)
     70     return r;
     71 
     72   return -1U;
     73 }
     74 
     75 
     76 void APInt::initSlowCase(unsigned numBits, uint64_t val, bool isSigned) {
     77   pVal = getClearedMemory(getNumWords());
     78   pVal[0] = val;
     79   if (isSigned && int64_t(val) < 0)
     80     for (unsigned i = 1; i < getNumWords(); ++i)
     81       pVal[i] = -1ULL;
     82 }
     83 
     84 void APInt::initSlowCase(const APInt& that) {
     85   pVal = getMemory(getNumWords());
     86   memcpy(pVal, that.pVal, getNumWords() * APINT_WORD_SIZE);
     87 }
     88 
     89 void APInt::initFromArray(ArrayRef<uint64_t> bigVal) {
     90   assert(BitWidth && "Bitwidth too small");
     91   assert(bigVal.data() && "Null pointer detected!");
     92   if (isSingleWord())
     93     VAL = bigVal[0];
     94   else {
     95     // Get memory, cleared to 0
     96     pVal = getClearedMemory(getNumWords());
     97     // Calculate the number of words to copy
     98     unsigned words = std::min<unsigned>(bigVal.size(), getNumWords());
     99     // Copy the words from bigVal to pVal
    100     memcpy(pVal, bigVal.data(), words * APINT_WORD_SIZE);
    101   }
    102   // Make sure unused high bits are cleared
    103   clearUnusedBits();
    104 }
    105 
    106 APInt::APInt(unsigned numBits, ArrayRef<uint64_t> bigVal)
    107   : BitWidth(numBits), VAL(0) {
    108   initFromArray(bigVal);
    109 }
    110 
    111 APInt::APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[])
    112   : BitWidth(numBits), VAL(0) {
    113   initFromArray(makeArrayRef(bigVal, numWords));
    114 }
    115 
    116 APInt::APInt(unsigned numbits, StringRef Str, uint8_t radix)
    117   : BitWidth(numbits), VAL(0) {
    118   assert(BitWidth && "Bitwidth too small");
    119   fromString(numbits, Str, radix);
    120 }
    121 
    122 APInt& APInt::AssignSlowCase(const APInt& RHS) {
    123   // Don't do anything for X = X
    124   if (this == &RHS)
    125     return *this;
    126 
    127   if (BitWidth == RHS.getBitWidth()) {
    128     // assume same bit-width single-word case is already handled
    129     assert(!isSingleWord());
    130     memcpy(pVal, RHS.pVal, getNumWords() * APINT_WORD_SIZE);
    131     return *this;
    132   }
    133 
    134   if (isSingleWord()) {
    135     // assume case where both are single words is already handled
    136     assert(!RHS.isSingleWord());
    137     VAL = 0;
    138     pVal = getMemory(RHS.getNumWords());
    139     memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
    140   } else if (getNumWords() == RHS.getNumWords())
    141     memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
    142   else if (RHS.isSingleWord()) {
    143     delete [] pVal;
    144     VAL = RHS.VAL;
    145   } else {
    146     delete [] pVal;
    147     pVal = getMemory(RHS.getNumWords());
    148     memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
    149   }
    150   BitWidth = RHS.BitWidth;
    151   return clearUnusedBits();
    152 }
    153 
    154 APInt& APInt::operator=(uint64_t RHS) {
    155   if (isSingleWord())
    156     VAL = RHS;
    157   else {
    158     pVal[0] = RHS;
    159     memset(pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE);
    160   }
    161   return clearUnusedBits();
    162 }
    163 
    164 /// Profile - This method 'profiles' an APInt for use with FoldingSet.
    165 void APInt::Profile(FoldingSetNodeID& ID) const {
    166   ID.AddInteger(BitWidth);
    167 
    168   if (isSingleWord()) {
    169     ID.AddInteger(VAL);
    170     return;
    171   }
    172 
    173   unsigned NumWords = getNumWords();
    174   for (unsigned i = 0; i < NumWords; ++i)
    175     ID.AddInteger(pVal[i]);
    176 }
    177 
    178 /// add_1 - This function adds a single "digit" integer, y, to the multiple
    179 /// "digit" integer array,  x[]. x[] is modified to reflect the addition and
    180 /// 1 is returned if there is a carry out, otherwise 0 is returned.
    181 /// @returns the carry of the addition.
    182 static bool add_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) {
    183   for (unsigned i = 0; i < len; ++i) {
    184     dest[i] = y + x[i];
    185     if (dest[i] < y)
    186       y = 1; // Carry one to next digit.
    187     else {
    188       y = 0; // No need to carry so exit early
    189       break;
    190     }
    191   }
    192   return y;
    193 }
    194 
    195 /// @brief Prefix increment operator. Increments the APInt by one.
    196 APInt& APInt::operator++() {
    197   if (isSingleWord())
    198     ++VAL;
    199   else
    200     add_1(pVal, pVal, getNumWords(), 1);
    201   return clearUnusedBits();
    202 }
    203 
    204 /// sub_1 - This function subtracts a single "digit" (64-bit word), y, from
    205 /// the multi-digit integer array, x[], propagating the borrowed 1 value until
    206 /// no further borrowing is neeeded or it runs out of "digits" in x.  The result
    207 /// is 1 if "borrowing" exhausted the digits in x, or 0 if x was not exhausted.
    208 /// In other words, if y > x then this function returns 1, otherwise 0.
    209 /// @returns the borrow out of the subtraction
    210 static bool sub_1(uint64_t x[], unsigned len, uint64_t y) {
    211   for (unsigned i = 0; i < len; ++i) {
    212     uint64_t X = x[i];
    213     x[i] -= y;
    214     if (y > X)
    215       y = 1;  // We have to "borrow 1" from next "digit"
    216     else {
    217       y = 0;  // No need to borrow
    218       break;  // Remaining digits are unchanged so exit early
    219     }
    220   }
    221   return bool(y);
    222 }
    223 
    224 /// @brief Prefix decrement operator. Decrements the APInt by one.
    225 APInt& APInt::operator--() {
    226   if (isSingleWord())
    227     --VAL;
    228   else
    229     sub_1(pVal, getNumWords(), 1);
    230   return clearUnusedBits();
    231 }
    232 
    233 /// add - This function adds the integer array x to the integer array Y and
    234 /// places the result in dest.
    235 /// @returns the carry out from the addition
    236 /// @brief General addition of 64-bit integer arrays
    237 static bool add(uint64_t *dest, const uint64_t *x, const uint64_t *y,
    238                 unsigned len) {
    239   bool carry = false;
    240   for (unsigned i = 0; i< len; ++i) {
    241     uint64_t limit = std::min(x[i],y[i]); // must come first in case dest == x
    242     dest[i] = x[i] + y[i] + carry;
    243     carry = dest[i] < limit || (carry && dest[i] == limit);
    244   }
    245   return carry;
    246 }
    247 
    248 /// Adds the RHS APint to this APInt.
    249 /// @returns this, after addition of RHS.
    250 /// @brief Addition assignment operator.
    251 APInt& APInt::operator+=(const APInt& RHS) {
    252   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
    253   if (isSingleWord())
    254     VAL += RHS.VAL;
    255   else {
    256     add(pVal, pVal, RHS.pVal, getNumWords());
    257   }
    258   return clearUnusedBits();
    259 }
    260 
    261 /// Subtracts the integer array y from the integer array x
    262 /// @returns returns the borrow out.
    263 /// @brief Generalized subtraction of 64-bit integer arrays.
    264 static bool sub(uint64_t *dest, const uint64_t *x, const uint64_t *y,
    265                 unsigned len) {
    266   bool borrow = false;
    267   for (unsigned i = 0; i < len; ++i) {
    268     uint64_t x_tmp = borrow ? x[i] - 1 : x[i];
    269     borrow = y[i] > x_tmp || (borrow && x[i] == 0);
    270     dest[i] = x_tmp - y[i];
    271   }
    272   return borrow;
    273 }
    274 
    275 /// Subtracts the RHS APInt from this APInt
    276 /// @returns this, after subtraction
    277 /// @brief Subtraction assignment operator.
    278 APInt& APInt::operator-=(const APInt& RHS) {
    279   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
    280   if (isSingleWord())
    281     VAL -= RHS.VAL;
    282   else
    283     sub(pVal, pVal, RHS.pVal, getNumWords());
    284   return clearUnusedBits();
    285 }
    286 
    287 /// Multiplies an integer array, x, by a uint64_t integer and places the result
    288 /// into dest.
    289 /// @returns the carry out of the multiplication.
    290 /// @brief Multiply a multi-digit APInt by a single digit (64-bit) integer.
    291 static uint64_t mul_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) {
    292   // Split y into high 32-bit part (hy)  and low 32-bit part (ly)
    293   uint64_t ly = y & 0xffffffffULL, hy = y >> 32;
    294   uint64_t carry = 0;
    295 
    296   // For each digit of x.
    297   for (unsigned i = 0; i < len; ++i) {
    298     // Split x into high and low words
    299     uint64_t lx = x[i] & 0xffffffffULL;
    300     uint64_t hx = x[i] >> 32;
    301     // hasCarry - A flag to indicate if there is a carry to the next digit.
    302     // hasCarry == 0, no carry
    303     // hasCarry == 1, has carry
    304     // hasCarry == 2, no carry and the calculation result == 0.
    305     uint8_t hasCarry = 0;
    306     dest[i] = carry + lx * ly;
    307     // Determine if the add above introduces carry.
    308     hasCarry = (dest[i] < carry) ? 1 : 0;
    309     carry = hx * ly + (dest[i] >> 32) + (hasCarry ? (1ULL << 32) : 0);
    310     // The upper limit of carry can be (2^32 - 1)(2^32 - 1) +
    311     // (2^32 - 1) + 2^32 = 2^64.
    312     hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
    313 
    314     carry += (lx * hy) & 0xffffffffULL;
    315     dest[i] = (carry << 32) | (dest[i] & 0xffffffffULL);
    316     carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0) +
    317             (carry >> 32) + ((lx * hy) >> 32) + hx * hy;
    318   }
    319   return carry;
    320 }
    321 
    322 /// Multiplies integer array x by integer array y and stores the result into
    323 /// the integer array dest. Note that dest's size must be >= xlen + ylen.
    324 /// @brief Generalized multiplicate of integer arrays.
    325 static void mul(uint64_t dest[], uint64_t x[], unsigned xlen, uint64_t y[],
    326                 unsigned ylen) {
    327   dest[xlen] = mul_1(dest, x, xlen, y[0]);
    328   for (unsigned i = 1; i < ylen; ++i) {
    329     uint64_t ly = y[i] & 0xffffffffULL, hy = y[i] >> 32;
    330     uint64_t carry = 0, lx = 0, hx = 0;
    331     for (unsigned j = 0; j < xlen; ++j) {
    332       lx = x[j] & 0xffffffffULL;
    333       hx = x[j] >> 32;
    334       // hasCarry - A flag to indicate if has carry.
    335       // hasCarry == 0, no carry
    336       // hasCarry == 1, has carry
    337       // hasCarry == 2, no carry and the calculation result == 0.
    338       uint8_t hasCarry = 0;
    339       uint64_t resul = carry + lx * ly;
    340       hasCarry = (resul < carry) ? 1 : 0;
    341       carry = (hasCarry ? (1ULL << 32) : 0) + hx * ly + (resul >> 32);
    342       hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
    343 
    344       carry += (lx * hy) & 0xffffffffULL;
    345       resul = (carry << 32) | (resul & 0xffffffffULL);
    346       dest[i+j] += resul;
    347       carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0)+
    348               (carry >> 32) + (dest[i+j] < resul ? 1 : 0) +
    349               ((lx * hy) >> 32) + hx * hy;
    350     }
    351     dest[i+xlen] = carry;
    352   }
    353 }
    354 
    355 APInt& APInt::operator*=(const APInt& RHS) {
    356   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
    357   if (isSingleWord()) {
    358     VAL *= RHS.VAL;
    359     clearUnusedBits();
    360     return *this;
    361   }
    362 
    363   // Get some bit facts about LHS and check for zero
    364   unsigned lhsBits = getActiveBits();
    365   unsigned lhsWords = !lhsBits ? 0 : whichWord(lhsBits - 1) + 1;
    366   if (!lhsWords)
    367     // 0 * X ===> 0
    368     return *this;
    369 
    370   // Get some bit facts about RHS and check for zero
    371   unsigned rhsBits = RHS.getActiveBits();
    372   unsigned rhsWords = !rhsBits ? 0 : whichWord(rhsBits - 1) + 1;
    373   if (!rhsWords) {
    374     // X * 0 ===> 0
    375     clearAllBits();
    376     return *this;
    377   }
    378 
    379   // Allocate space for the result
    380   unsigned destWords = rhsWords + lhsWords;
    381   uint64_t *dest = getMemory(destWords);
    382 
    383   // Perform the long multiply
    384   mul(dest, pVal, lhsWords, RHS.pVal, rhsWords);
    385 
    386   // Copy result back into *this
    387   clearAllBits();
    388   unsigned wordsToCopy = destWords >= getNumWords() ? getNumWords() : destWords;
    389   memcpy(pVal, dest, wordsToCopy * APINT_WORD_SIZE);
    390   clearUnusedBits();
    391 
    392   // delete dest array and return
    393   delete[] dest;
    394   return *this;
    395 }
    396 
    397 APInt& APInt::operator&=(const APInt& RHS) {
    398   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
    399   if (isSingleWord()) {
    400     VAL &= RHS.VAL;
    401     return *this;
    402   }
    403   unsigned numWords = getNumWords();
    404   for (unsigned i = 0; i < numWords; ++i)
    405     pVal[i] &= RHS.pVal[i];
    406   return *this;
    407 }
    408 
    409 APInt& APInt::operator|=(const APInt& RHS) {
    410   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
    411   if (isSingleWord()) {
    412     VAL |= RHS.VAL;
    413     return *this;
    414   }
    415   unsigned numWords = getNumWords();
    416   for (unsigned i = 0; i < numWords; ++i)
    417     pVal[i] |= RHS.pVal[i];
    418   return *this;
    419 }
    420 
    421 APInt& APInt::operator^=(const APInt& RHS) {
    422   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
    423   if (isSingleWord()) {
    424     VAL ^= RHS.VAL;
    425     this->clearUnusedBits();
    426     return *this;
    427   }
    428   unsigned numWords = getNumWords();
    429   for (unsigned i = 0; i < numWords; ++i)
    430     pVal[i] ^= RHS.pVal[i];
    431   return clearUnusedBits();
    432 }
    433 
    434 APInt APInt::AndSlowCase(const APInt& RHS) const {
    435   unsigned numWords = getNumWords();
    436   uint64_t* val = getMemory(numWords);
    437   for (unsigned i = 0; i < numWords; ++i)
    438     val[i] = pVal[i] & RHS.pVal[i];
    439   return APInt(val, getBitWidth());
    440 }
    441 
    442 APInt APInt::OrSlowCase(const APInt& RHS) const {
    443   unsigned numWords = getNumWords();
    444   uint64_t *val = getMemory(numWords);
    445   for (unsigned i = 0; i < numWords; ++i)
    446     val[i] = pVal[i] | RHS.pVal[i];
    447   return APInt(val, getBitWidth());
    448 }
    449 
    450 APInt APInt::XorSlowCase(const APInt& RHS) const {
    451   unsigned numWords = getNumWords();
    452   uint64_t *val = getMemory(numWords);
    453   for (unsigned i = 0; i < numWords; ++i)
    454     val[i] = pVal[i] ^ RHS.pVal[i];
    455 
    456   // 0^0==1 so clear the high bits in case they got set.
    457   return APInt(val, getBitWidth()).clearUnusedBits();
    458 }
    459 
    460 APInt APInt::operator*(const APInt& RHS) const {
    461   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
    462   if (isSingleWord())
    463     return APInt(BitWidth, VAL * RHS.VAL);
    464   APInt Result(*this);
    465   Result *= RHS;
    466   return Result;
    467 }
    468 
    469 APInt APInt::operator+(const APInt& RHS) const {
    470   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
    471   if (isSingleWord())
    472     return APInt(BitWidth, VAL + RHS.VAL);
    473   APInt Result(BitWidth, 0);
    474   add(Result.pVal, this->pVal, RHS.pVal, getNumWords());
    475   return Result.clearUnusedBits();
    476 }
    477 
    478 APInt APInt::operator-(const APInt& RHS) const {
    479   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
    480   if (isSingleWord())
    481     return APInt(BitWidth, VAL - RHS.VAL);
    482   APInt Result(BitWidth, 0);
    483   sub(Result.pVal, this->pVal, RHS.pVal, getNumWords());
    484   return Result.clearUnusedBits();
    485 }
    486 
    487 bool APInt::EqualSlowCase(const APInt& RHS) const {
    488   // Get some facts about the number of bits used in the two operands.
    489   unsigned n1 = getActiveBits();
    490   unsigned n2 = RHS.getActiveBits();
    491 
    492   // If the number of bits isn't the same, they aren't equal
    493   if (n1 != n2)
    494     return false;
    495 
    496   // If the number of bits fits in a word, we only need to compare the low word.
    497   if (n1 <= APINT_BITS_PER_WORD)
    498     return pVal[0] == RHS.pVal[0];
    499 
    500   // Otherwise, compare everything
    501   for (int i = whichWord(n1 - 1); i >= 0; --i)
    502     if (pVal[i] != RHS.pVal[i])
    503       return false;
    504   return true;
    505 }
    506 
    507 bool APInt::EqualSlowCase(uint64_t Val) const {
    508   unsigned n = getActiveBits();
    509   if (n <= APINT_BITS_PER_WORD)
    510     return pVal[0] == Val;
    511   else
    512     return false;
    513 }
    514 
    515 bool APInt::ult(const APInt& RHS) const {
    516   assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
    517   if (isSingleWord())
    518     return VAL < RHS.VAL;
    519 
    520   // Get active bit length of both operands
    521   unsigned n1 = getActiveBits();
    522   unsigned n2 = RHS.getActiveBits();
    523 
    524   // If magnitude of LHS is less than RHS, return true.
    525   if (n1 < n2)
    526     return true;
    527 
    528   // If magnitude of RHS is greather than LHS, return false.
    529   if (n2 < n1)
    530     return false;
    531 
    532   // If they bot fit in a word, just compare the low order word
    533   if (n1 <= APINT_BITS_PER_WORD && n2 <= APINT_BITS_PER_WORD)
    534     return pVal[0] < RHS.pVal[0];
    535 
    536   // Otherwise, compare all words
    537   unsigned topWord = whichWord(std::max(n1,n2)-1);
    538   for (int i = topWord; i >= 0; --i) {
    539     if (pVal[i] > RHS.pVal[i])
    540       return false;
    541     if (pVal[i] < RHS.pVal[i])
    542       return true;
    543   }
    544   return false;
    545 }
    546 
    547 bool APInt::slt(const APInt& RHS) const {
    548   assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
    549   if (isSingleWord()) {
    550     int64_t lhsSext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth);
    551     int64_t rhsSext = (int64_t(RHS.VAL) << (64-BitWidth)) >> (64-BitWidth);
    552     return lhsSext < rhsSext;
    553   }
    554 
    555   APInt lhs(*this);
    556   APInt rhs(RHS);
    557   bool lhsNeg = isNegative();
    558   bool rhsNeg = rhs.isNegative();
    559   if (lhsNeg) {
    560     // Sign bit is set so perform two's complement to make it positive
    561     lhs.flipAllBits();
    562     lhs++;
    563   }
    564   if (rhsNeg) {
    565     // Sign bit is set so perform two's complement to make it positive
    566     rhs.flipAllBits();
    567     rhs++;
    568   }
    569 
    570   // Now we have unsigned values to compare so do the comparison if necessary
    571   // based on the negativeness of the values.
    572   if (lhsNeg)
    573     if (rhsNeg)
    574       return lhs.ugt(rhs);
    575     else
    576       return true;
    577   else if (rhsNeg)
    578     return false;
    579   else
    580     return lhs.ult(rhs);
    581 }
    582 
    583 void APInt::setBit(unsigned bitPosition) {
    584   if (isSingleWord())
    585     VAL |= maskBit(bitPosition);
    586   else
    587     pVal[whichWord(bitPosition)] |= maskBit(bitPosition);
    588 }
    589 
    590 /// Set the given bit to 0 whose position is given as "bitPosition".
    591 /// @brief Set a given bit to 0.
    592 void APInt::clearBit(unsigned bitPosition) {
    593   if (isSingleWord())
    594     VAL &= ~maskBit(bitPosition);
    595   else
    596     pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition);
    597 }
    598 
    599 /// @brief Toggle every bit to its opposite value.
    600 
    601 /// Toggle a given bit to its opposite value whose position is given
    602 /// as "bitPosition".
    603 /// @brief Toggles a given bit to its opposite value.
    604 void APInt::flipBit(unsigned bitPosition) {
    605   assert(bitPosition < BitWidth && "Out of the bit-width range!");
    606   if ((*this)[bitPosition]) clearBit(bitPosition);
    607   else setBit(bitPosition);
    608 }
    609 
    610 unsigned APInt::getBitsNeeded(StringRef str, uint8_t radix) {
    611   assert(!str.empty() && "Invalid string length");
    612   assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
    613           radix == 36) &&
    614          "Radix should be 2, 8, 10, 16, or 36!");
    615 
    616   size_t slen = str.size();
    617 
    618   // Each computation below needs to know if it's negative.
    619   StringRef::iterator p = str.begin();
    620   unsigned isNegative = *p == '-';
    621   if (*p == '-' || *p == '+') {
    622     p++;
    623     slen--;
    624     assert(slen && "String is only a sign, needs a value.");
    625   }
    626 
    627   // For radixes of power-of-two values, the bits required is accurately and
    628   // easily computed
    629   if (radix == 2)
    630     return slen + isNegative;
    631   if (radix == 8)
    632     return slen * 3 + isNegative;
    633   if (radix == 16)
    634     return slen * 4 + isNegative;
    635 
    636   // FIXME: base 36
    637 
    638   // This is grossly inefficient but accurate. We could probably do something
    639   // with a computation of roughly slen*64/20 and then adjust by the value of
    640   // the first few digits. But, I'm not sure how accurate that could be.
    641 
    642   // Compute a sufficient number of bits that is always large enough but might
    643   // be too large. This avoids the assertion in the constructor. This
    644   // calculation doesn't work appropriately for the numbers 0-9, so just use 4
    645   // bits in that case.
    646   unsigned sufficient
    647     = radix == 10? (slen == 1 ? 4 : slen * 64/18)
    648                  : (slen == 1 ? 7 : slen * 16/3);
    649 
    650   // Convert to the actual binary value.
    651   APInt tmp(sufficient, StringRef(p, slen), radix);
    652 
    653   // Compute how many bits are required. If the log is infinite, assume we need
    654   // just bit.
    655   unsigned log = tmp.logBase2();
    656   if (log == (unsigned)-1) {
    657     return isNegative + 1;
    658   } else {
    659     return isNegative + log + 1;
    660   }
    661 }
    662 
    663 hash_code llvm::hash_value(const APInt &Arg) {
    664   if (Arg.isSingleWord())
    665     return hash_combine(Arg.VAL);
    666 
    667   return hash_combine_range(Arg.pVal, Arg.pVal + Arg.getNumWords());
    668 }
    669 
    670 /// HiBits - This function returns the high "numBits" bits of this APInt.
    671 APInt APInt::getHiBits(unsigned numBits) const {
    672   return APIntOps::lshr(*this, BitWidth - numBits);
    673 }
    674 
    675 /// LoBits - This function returns the low "numBits" bits of this APInt.
    676 APInt APInt::getLoBits(unsigned numBits) const {
    677   return APIntOps::lshr(APIntOps::shl(*this, BitWidth - numBits),
    678                         BitWidth - numBits);
    679 }
    680 
    681 unsigned APInt::countLeadingZerosSlowCase() const {
    682   // Treat the most significand word differently because it might have
    683   // meaningless bits set beyond the precision.
    684   unsigned BitsInMSW = BitWidth % APINT_BITS_PER_WORD;
    685   integerPart MSWMask;
    686   if (BitsInMSW) MSWMask = (integerPart(1) << BitsInMSW) - 1;
    687   else {
    688     MSWMask = ~integerPart(0);
    689     BitsInMSW = APINT_BITS_PER_WORD;
    690   }
    691 
    692   unsigned i = getNumWords();
    693   integerPart MSW = pVal[i-1] & MSWMask;
    694   if (MSW)
    695     return CountLeadingZeros_64(MSW) - (APINT_BITS_PER_WORD - BitsInMSW);
    696 
    697   unsigned Count = BitsInMSW;
    698   for (--i; i > 0u; --i) {
    699     if (pVal[i-1] == 0)
    700       Count += APINT_BITS_PER_WORD;
    701     else {
    702       Count += CountLeadingZeros_64(pVal[i-1]);
    703       break;
    704     }
    705   }
    706   return Count;
    707 }
    708 
    709 unsigned APInt::countLeadingOnes() const {
    710   if (isSingleWord())
    711     return CountLeadingOnes_64(VAL << (APINT_BITS_PER_WORD - BitWidth));
    712 
    713   unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD;
    714   unsigned shift;
    715   if (!highWordBits) {
    716     highWordBits = APINT_BITS_PER_WORD;
    717     shift = 0;
    718   } else {
    719     shift = APINT_BITS_PER_WORD - highWordBits;
    720   }
    721   int i = getNumWords() - 1;
    722   unsigned Count = CountLeadingOnes_64(pVal[i] << shift);
    723   if (Count == highWordBits) {
    724     for (i--; i >= 0; --i) {
    725       if (pVal[i] == -1ULL)
    726         Count += APINT_BITS_PER_WORD;
    727       else {
    728         Count += CountLeadingOnes_64(pVal[i]);
    729         break;
    730       }
    731     }
    732   }
    733   return Count;
    734 }
    735 
    736 unsigned APInt::countTrailingZeros() const {
    737   if (isSingleWord())
    738     return std::min(unsigned(CountTrailingZeros_64(VAL)), BitWidth);
    739   unsigned Count = 0;
    740   unsigned i = 0;
    741   for (; i < getNumWords() && pVal[i] == 0; ++i)
    742     Count += APINT_BITS_PER_WORD;
    743   if (i < getNumWords())
    744     Count += CountTrailingZeros_64(pVal[i]);
    745   return std::min(Count, BitWidth);
    746 }
    747 
    748 unsigned APInt::countTrailingOnesSlowCase() const {
    749   unsigned Count = 0;
    750   unsigned i = 0;
    751   for (; i < getNumWords() && pVal[i] == -1ULL; ++i)
    752     Count += APINT_BITS_PER_WORD;
    753   if (i < getNumWords())
    754     Count += CountTrailingOnes_64(pVal[i]);
    755   return std::min(Count, BitWidth);
    756 }
    757 
    758 unsigned APInt::countPopulationSlowCase() const {
    759   unsigned Count = 0;
    760   for (unsigned i = 0; i < getNumWords(); ++i)
    761     Count += CountPopulation_64(pVal[i]);
    762   return Count;
    763 }
    764 
    765 /// Perform a logical right-shift from Src to Dst, which must be equal or
    766 /// non-overlapping, of Words words, by Shift, which must be less than 64.
    767 static void lshrNear(uint64_t *Dst, uint64_t *Src, unsigned Words,
    768                      unsigned Shift) {
    769   uint64_t Carry = 0;
    770   for (int I = Words - 1; I >= 0; --I) {
    771     uint64_t Tmp = Src[I];
    772     Dst[I] = (Tmp >> Shift) | Carry;
    773     Carry = Tmp << (64 - Shift);
    774   }
    775 }
    776 
    777 APInt APInt::byteSwap() const {
    778   assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
    779   if (BitWidth == 16)
    780     return APInt(BitWidth, ByteSwap_16(uint16_t(VAL)));
    781   if (BitWidth == 32)
    782     return APInt(BitWidth, ByteSwap_32(unsigned(VAL)));
    783   if (BitWidth == 48) {
    784     unsigned Tmp1 = unsigned(VAL >> 16);
    785     Tmp1 = ByteSwap_32(Tmp1);
    786     uint16_t Tmp2 = uint16_t(VAL);
    787     Tmp2 = ByteSwap_16(Tmp2);
    788     return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
    789   }
    790   if (BitWidth == 64)
    791     return APInt(BitWidth, ByteSwap_64(VAL));
    792 
    793   APInt Result(getNumWords() * APINT_BITS_PER_WORD, 0);
    794   for (unsigned I = 0, N = getNumWords(); I != N; ++I)
    795     Result.pVal[I] = ByteSwap_64(pVal[N - I - 1]);
    796   if (Result.BitWidth != BitWidth) {
    797     lshrNear(Result.pVal, Result.pVal, getNumWords(),
    798              Result.BitWidth - BitWidth);
    799     Result.BitWidth = BitWidth;
    800   }
    801   return Result;
    802 }
    803 
    804 APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1,
    805                                             const APInt& API2) {
    806   APInt A = API1, B = API2;
    807   while (!!B) {
    808     APInt T = B;
    809     B = APIntOps::urem(A, B);
    810     A = T;
    811   }
    812   return A;
    813 }
    814 
    815 APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) {
    816   union {
    817     double D;
    818     uint64_t I;
    819   } T;
    820   T.D = Double;
    821 
    822   // Get the sign bit from the highest order bit
    823   bool isNeg = T.I >> 63;
    824 
    825   // Get the 11-bit exponent and adjust for the 1023 bit bias
    826   int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
    827 
    828   // If the exponent is negative, the value is < 0 so just return 0.
    829   if (exp < 0)
    830     return APInt(width, 0u);
    831 
    832   // Extract the mantissa by clearing the top 12 bits (sign + exponent).
    833   uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
    834 
    835   // If the exponent doesn't shift all bits out of the mantissa
    836   if (exp < 52)
    837     return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
    838                     APInt(width, mantissa >> (52 - exp));
    839 
    840   // If the client didn't provide enough bits for us to shift the mantissa into
    841   // then the result is undefined, just return 0
    842   if (width <= exp - 52)
    843     return APInt(width, 0);
    844 
    845   // Otherwise, we have to shift the mantissa bits up to the right location
    846   APInt Tmp(width, mantissa);
    847   Tmp = Tmp.shl((unsigned)exp - 52);
    848   return isNeg ? -Tmp : Tmp;
    849 }
    850 
    851 /// RoundToDouble - This function converts this APInt to a double.
    852 /// The layout for double is as following (IEEE Standard 754):
    853 ///  --------------------------------------
    854 /// |  Sign    Exponent    Fraction    Bias |
    855 /// |-------------------------------------- |
    856 /// |  1[63]   11[62-52]   52[51-00]   1023 |
    857 ///  --------------------------------------
    858 double APInt::roundToDouble(bool isSigned) const {
    859 
    860   // Handle the simple case where the value is contained in one uint64_t.
    861   // It is wrong to optimize getWord(0) to VAL; there might be more than one word.
    862   if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
    863     if (isSigned) {
    864       int64_t sext = (int64_t(getWord(0)) << (64-BitWidth)) >> (64-BitWidth);
    865       return double(sext);
    866     } else
    867       return double(getWord(0));
    868   }
    869 
    870   // Determine if the value is negative.
    871   bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
    872 
    873   // Construct the absolute value if we're negative.
    874   APInt Tmp(isNeg ? -(*this) : (*this));
    875 
    876   // Figure out how many bits we're using.
    877   unsigned n = Tmp.getActiveBits();
    878 
    879   // The exponent (without bias normalization) is just the number of bits
    880   // we are using. Note that the sign bit is gone since we constructed the
    881   // absolute value.
    882   uint64_t exp = n;
    883 
    884   // Return infinity for exponent overflow
    885   if (exp > 1023) {
    886     if (!isSigned || !isNeg)
    887       return std::numeric_limits<double>::infinity();
    888     else
    889       return -std::numeric_limits<double>::infinity();
    890   }
    891   exp += 1023; // Increment for 1023 bias
    892 
    893   // Number of bits in mantissa is 52. To obtain the mantissa value, we must
    894   // extract the high 52 bits from the correct words in pVal.
    895   uint64_t mantissa;
    896   unsigned hiWord = whichWord(n-1);
    897   if (hiWord == 0) {
    898     mantissa = Tmp.pVal[0];
    899     if (n > 52)
    900       mantissa >>= n - 52; // shift down, we want the top 52 bits.
    901   } else {
    902     assert(hiWord > 0 && "huh?");
    903     uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
    904     uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
    905     mantissa = hibits | lobits;
    906   }
    907 
    908   // The leading bit of mantissa is implicit, so get rid of it.
    909   uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
    910   union {
    911     double D;
    912     uint64_t I;
    913   } T;
    914   T.I = sign | (exp << 52) | mantissa;
    915   return T.D;
    916 }
    917 
    918 // Truncate to new width.
    919 APInt APInt::trunc(unsigned width) const {
    920   assert(width < BitWidth && "Invalid APInt Truncate request");
    921   assert(width && "Can't truncate to 0 bits");
    922 
    923   if (width <= APINT_BITS_PER_WORD)
    924     return APInt(width, getRawData()[0]);
    925 
    926   APInt Result(getMemory(getNumWords(width)), width);
    927 
    928   // Copy full words.
    929   unsigned i;
    930   for (i = 0; i != width / APINT_BITS_PER_WORD; i++)
    931     Result.pVal[i] = pVal[i];
    932 
    933   // Truncate and copy any partial word.
    934   unsigned bits = (0 - width) % APINT_BITS_PER_WORD;
    935   if (bits != 0)
    936     Result.pVal[i] = pVal[i] << bits >> bits;
    937 
    938   return Result;
    939 }
    940 
    941 // Sign extend to a new width.
    942 APInt APInt::sext(unsigned width) const {
    943   assert(width > BitWidth && "Invalid APInt SignExtend request");
    944 
    945   if (width <= APINT_BITS_PER_WORD) {
    946     uint64_t val = VAL << (APINT_BITS_PER_WORD - BitWidth);
    947     val = (int64_t)val >> (width - BitWidth);
    948     return APInt(width, val >> (APINT_BITS_PER_WORD - width));
    949   }
    950 
    951   APInt Result(getMemory(getNumWords(width)), width);
    952 
    953   // Copy full words.
    954   unsigned i;
    955   uint64_t word = 0;
    956   for (i = 0; i != BitWidth / APINT_BITS_PER_WORD; i++) {
    957     word = getRawData()[i];
    958     Result.pVal[i] = word;
    959   }
    960 
    961   // Read and sign-extend any partial word.
    962   unsigned bits = (0 - BitWidth) % APINT_BITS_PER_WORD;
    963   if (bits != 0)
    964     word = (int64_t)getRawData()[i] << bits >> bits;
    965   else
    966     word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);
    967 
    968   // Write remaining full words.
    969   for (; i != width / APINT_BITS_PER_WORD; i++) {
    970     Result.pVal[i] = word;
    971     word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);
    972   }
    973 
    974   // Write any partial word.
    975   bits = (0 - width) % APINT_BITS_PER_WORD;
    976   if (bits != 0)
    977     Result.pVal[i] = word << bits >> bits;
    978 
    979   return Result;
    980 }
    981 
    982 //  Zero extend to a new width.
    983 APInt APInt::zext(unsigned width) const {
    984   assert(width > BitWidth && "Invalid APInt ZeroExtend request");
    985 
    986   if (width <= APINT_BITS_PER_WORD)
    987     return APInt(width, VAL);
    988 
    989   APInt Result(getMemory(getNumWords(width)), width);
    990 
    991   // Copy words.
    992   unsigned i;
    993   for (i = 0; i != getNumWords(); i++)
    994     Result.pVal[i] = getRawData()[i];
    995 
    996   // Zero remaining words.
    997   memset(&Result.pVal[i], 0, (Result.getNumWords() - i) * APINT_WORD_SIZE);
    998 
    999   return Result;
   1000 }
   1001 
   1002 APInt APInt::zextOrTrunc(unsigned width) const {
   1003   if (BitWidth < width)
   1004     return zext(width);
   1005   if (BitWidth > width)
   1006     return trunc(width);
   1007   return *this;
   1008 }
   1009 
   1010 APInt APInt::sextOrTrunc(unsigned width) const {
   1011   if (BitWidth < width)
   1012     return sext(width);
   1013   if (BitWidth > width)
   1014     return trunc(width);
   1015   return *this;
   1016 }
   1017 
   1018 APInt APInt::zextOrSelf(unsigned width) const {
   1019   if (BitWidth < width)
   1020     return zext(width);
   1021   return *this;
   1022 }
   1023 
   1024 APInt APInt::sextOrSelf(unsigned width) const {
   1025   if (BitWidth < width)
   1026     return sext(width);
   1027   return *this;
   1028 }
   1029 
   1030 /// Arithmetic right-shift this APInt by shiftAmt.
   1031 /// @brief Arithmetic right-shift function.
   1032 APInt APInt::ashr(const APInt &shiftAmt) const {
   1033   return ashr((unsigned)shiftAmt.getLimitedValue(BitWidth));
   1034 }
   1035 
   1036 /// Arithmetic right-shift this APInt by shiftAmt.
   1037 /// @brief Arithmetic right-shift function.
   1038 APInt APInt::ashr(unsigned shiftAmt) const {
   1039   assert(shiftAmt <= BitWidth && "Invalid shift amount");
   1040   // Handle a degenerate case
   1041   if (shiftAmt == 0)
   1042     return *this;
   1043 
   1044   // Handle single word shifts with built-in ashr
   1045   if (isSingleWord()) {
   1046     if (shiftAmt == BitWidth)
   1047       return APInt(BitWidth, 0); // undefined
   1048     else {
   1049       unsigned SignBit = APINT_BITS_PER_WORD - BitWidth;
   1050       return APInt(BitWidth,
   1051         (((int64_t(VAL) << SignBit) >> SignBit) >> shiftAmt));
   1052     }
   1053   }
   1054 
   1055   // If all the bits were shifted out, the result is, technically, undefined.
   1056   // We return -1 if it was negative, 0 otherwise. We check this early to avoid
   1057   // issues in the algorithm below.
   1058   if (shiftAmt == BitWidth) {
   1059     if (isNegative())
   1060       return APInt(BitWidth, -1ULL, true);
   1061     else
   1062       return APInt(BitWidth, 0);
   1063   }
   1064 
   1065   // Create some space for the result.
   1066   uint64_t * val = new uint64_t[getNumWords()];
   1067 
   1068   // Compute some values needed by the following shift algorithms
   1069   unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word
   1070   unsigned offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift
   1071   unsigned breakWord = getNumWords() - 1 - offset; // last word affected
   1072   unsigned bitsInWord = whichBit(BitWidth); // how many bits in last word?
   1073   if (bitsInWord == 0)
   1074     bitsInWord = APINT_BITS_PER_WORD;
   1075 
   1076   // If we are shifting whole words, just move whole words
   1077   if (wordShift == 0) {
   1078     // Move the words containing significant bits
   1079     for (unsigned i = 0; i <= breakWord; ++i)
   1080       val[i] = pVal[i+offset]; // move whole word
   1081 
   1082     // Adjust the top significant word for sign bit fill, if negative
   1083     if (isNegative())
   1084       if (bitsInWord < APINT_BITS_PER_WORD)
   1085         val[breakWord] |= ~0ULL << bitsInWord; // set high bits
   1086   } else {
   1087     // Shift the low order words
   1088     for (unsigned i = 0; i < breakWord; ++i) {
   1089       // This combines the shifted corresponding word with the low bits from
   1090       // the next word (shifted into this word's high bits).
   1091       val[i] = (pVal[i+offset] >> wordShift) |
   1092                (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
   1093     }
   1094 
   1095     // Shift the break word. In this case there are no bits from the next word
   1096     // to include in this word.
   1097     val[breakWord] = pVal[breakWord+offset] >> wordShift;
   1098 
   1099     // Deal with sign extenstion in the break word, and possibly the word before
   1100     // it.
   1101     if (isNegative()) {
   1102       if (wordShift > bitsInWord) {
   1103         if (breakWord > 0)
   1104           val[breakWord-1] |=
   1105             ~0ULL << (APINT_BITS_PER_WORD - (wordShift - bitsInWord));
   1106         val[breakWord] |= ~0ULL;
   1107       } else
   1108         val[breakWord] |= (~0ULL << (bitsInWord - wordShift));
   1109     }
   1110   }
   1111 
   1112   // Remaining words are 0 or -1, just assign them.
   1113   uint64_t fillValue = (isNegative() ? -1ULL : 0);
   1114   for (unsigned i = breakWord+1; i < getNumWords(); ++i)
   1115     val[i] = fillValue;
   1116   return APInt(val, BitWidth).clearUnusedBits();
   1117 }
   1118 
   1119 /// Logical right-shift this APInt by shiftAmt.
   1120 /// @brief Logical right-shift function.
   1121 APInt APInt::lshr(const APInt &shiftAmt) const {
   1122   return lshr((unsigned)shiftAmt.getLimitedValue(BitWidth));
   1123 }
   1124 
   1125 /// Logical right-shift this APInt by shiftAmt.
   1126 /// @brief Logical right-shift function.
   1127 APInt APInt::lshr(unsigned shiftAmt) const {
   1128   if (isSingleWord()) {
   1129     if (shiftAmt >= BitWidth)
   1130       return APInt(BitWidth, 0);
   1131     else
   1132       return APInt(BitWidth, this->VAL >> shiftAmt);
   1133   }
   1134 
   1135   // If all the bits were shifted out, the result is 0. This avoids issues
   1136   // with shifting by the size of the integer type, which produces undefined
   1137   // results. We define these "undefined results" to always be 0.
   1138   if (shiftAmt == BitWidth)
   1139     return APInt(BitWidth, 0);
   1140 
   1141   // If none of the bits are shifted out, the result is *this. This avoids
   1142   // issues with shifting by the size of the integer type, which produces
   1143   // undefined results in the code below. This is also an optimization.
   1144   if (shiftAmt == 0)
   1145     return *this;
   1146 
   1147   // Create some space for the result.
   1148   uint64_t * val = new uint64_t[getNumWords()];
   1149 
   1150   // If we are shifting less than a word, compute the shift with a simple carry
   1151   if (shiftAmt < APINT_BITS_PER_WORD) {
   1152     lshrNear(val, pVal, getNumWords(), shiftAmt);
   1153     return APInt(val, BitWidth).clearUnusedBits();
   1154   }
   1155 
   1156   // Compute some values needed by the remaining shift algorithms
   1157   unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
   1158   unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
   1159 
   1160   // If we are shifting whole words, just move whole words
   1161   if (wordShift == 0) {
   1162     for (unsigned i = 0; i < getNumWords() - offset; ++i)
   1163       val[i] = pVal[i+offset];
   1164     for (unsigned i = getNumWords()-offset; i < getNumWords(); i++)
   1165       val[i] = 0;
   1166     return APInt(val,BitWidth).clearUnusedBits();
   1167   }
   1168 
   1169   // Shift the low order words
   1170   unsigned breakWord = getNumWords() - offset -1;
   1171   for (unsigned i = 0; i < breakWord; ++i)
   1172     val[i] = (pVal[i+offset] >> wordShift) |
   1173              (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
   1174   // Shift the break word.
   1175   val[breakWord] = pVal[breakWord+offset] >> wordShift;
   1176 
   1177   // Remaining words are 0
   1178   for (unsigned i = breakWord+1; i < getNumWords(); ++i)
   1179     val[i] = 0;
   1180   return APInt(val, BitWidth).clearUnusedBits();
   1181 }
   1182 
   1183 /// Left-shift this APInt by shiftAmt.
   1184 /// @brief Left-shift function.
   1185 APInt APInt::shl(const APInt &shiftAmt) const {
   1186   // It's undefined behavior in C to shift by BitWidth or greater.
   1187   return shl((unsigned)shiftAmt.getLimitedValue(BitWidth));
   1188 }
   1189 
   1190 APInt APInt::shlSlowCase(unsigned shiftAmt) const {
   1191   // If all the bits were shifted out, the result is 0. This avoids issues
   1192   // with shifting by the size of the integer type, which produces undefined
   1193   // results. We define these "undefined results" to always be 0.
   1194   if (shiftAmt == BitWidth)
   1195     return APInt(BitWidth, 0);
   1196 
   1197   // If none of the bits are shifted out, the result is *this. This avoids a
   1198   // lshr by the words size in the loop below which can produce incorrect
   1199   // results. It also avoids the expensive computation below for a common case.
   1200   if (shiftAmt == 0)
   1201     return *this;
   1202 
   1203   // Create some space for the result.
   1204   uint64_t * val = new uint64_t[getNumWords()];
   1205 
   1206   // If we are shifting less than a word, do it the easy way
   1207   if (shiftAmt < APINT_BITS_PER_WORD) {
   1208     uint64_t carry = 0;
   1209     for (unsigned i = 0; i < getNumWords(); i++) {
   1210       val[i] = pVal[i] << shiftAmt | carry;
   1211       carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt);
   1212     }
   1213     return APInt(val, BitWidth).clearUnusedBits();
   1214   }
   1215 
   1216   // Compute some values needed by the remaining shift algorithms
   1217   unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
   1218   unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
   1219 
   1220   // If we are shifting whole words, just move whole words
   1221   if (wordShift == 0) {
   1222     for (unsigned i = 0; i < offset; i++)
   1223       val[i] = 0;
   1224     for (unsigned i = offset; i < getNumWords(); i++)
   1225       val[i] = pVal[i-offset];
   1226     return APInt(val,BitWidth).clearUnusedBits();
   1227   }
   1228 
   1229   // Copy whole words from this to Result.
   1230   unsigned i = getNumWords() - 1;
   1231   for (; i > offset; --i)
   1232     val[i] = pVal[i-offset] << wordShift |
   1233              pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift);
   1234   val[offset] = pVal[0] << wordShift;
   1235   for (i = 0; i < offset; ++i)
   1236     val[i] = 0;
   1237   return APInt(val, BitWidth).clearUnusedBits();
   1238 }
   1239 
   1240 APInt APInt::rotl(const APInt &rotateAmt) const {
   1241   return rotl((unsigned)rotateAmt.getLimitedValue(BitWidth));
   1242 }
   1243 
   1244 APInt APInt::rotl(unsigned rotateAmt) const {
   1245   rotateAmt %= BitWidth;
   1246   if (rotateAmt == 0)
   1247     return *this;
   1248   return shl(rotateAmt) | lshr(BitWidth - rotateAmt);
   1249 }
   1250 
   1251 APInt APInt::rotr(const APInt &rotateAmt) const {
   1252   return rotr((unsigned)rotateAmt.getLimitedValue(BitWidth));
   1253 }
   1254 
   1255 APInt APInt::rotr(unsigned rotateAmt) const {
   1256   rotateAmt %= BitWidth;
   1257   if (rotateAmt == 0)
   1258     return *this;
   1259   return lshr(rotateAmt) | shl(BitWidth - rotateAmt);
   1260 }
   1261 
   1262 // Square Root - this method computes and returns the square root of "this".
   1263 // Three mechanisms are used for computation. For small values (<= 5 bits),
   1264 // a table lookup is done. This gets some performance for common cases. For
   1265 // values using less than 52 bits, the value is converted to double and then
   1266 // the libc sqrt function is called. The result is rounded and then converted
   1267 // back to a uint64_t which is then used to construct the result. Finally,
   1268 // the Babylonian method for computing square roots is used.
   1269 APInt APInt::sqrt() const {
   1270 
   1271   // Determine the magnitude of the value.
   1272   unsigned magnitude = getActiveBits();
   1273 
   1274   // Use a fast table for some small values. This also gets rid of some
   1275   // rounding errors in libc sqrt for small values.
   1276   if (magnitude <= 5) {
   1277     static const uint8_t results[32] = {
   1278       /*     0 */ 0,
   1279       /*  1- 2 */ 1, 1,
   1280       /*  3- 6 */ 2, 2, 2, 2,
   1281       /*  7-12 */ 3, 3, 3, 3, 3, 3,
   1282       /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
   1283       /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
   1284       /*    31 */ 6
   1285     };
   1286     return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]);
   1287   }
   1288 
   1289   // If the magnitude of the value fits in less than 52 bits (the precision of
   1290   // an IEEE double precision floating point value), then we can use the
   1291   // libc sqrt function which will probably use a hardware sqrt computation.
   1292   // This should be faster than the algorithm below.
   1293   if (magnitude < 52) {
   1294 #if HAVE_ROUND
   1295     return APInt(BitWidth,
   1296                  uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0])))));
   1297 #else
   1298     return APInt(BitWidth,
   1299                  uint64_t(::sqrt(double(isSingleWord()?VAL:pVal[0])) + 0.5));
   1300 #endif
   1301   }
   1302 
   1303   // Okay, all the short cuts are exhausted. We must compute it. The following
   1304   // is a classical Babylonian method for computing the square root. This code
   1305   // was adapted to APINt from a wikipedia article on such computations.
   1306   // See http://www.wikipedia.org/ and go to the page named
   1307   // Calculate_an_integer_square_root.
   1308   unsigned nbits = BitWidth, i = 4;
   1309   APInt testy(BitWidth, 16);
   1310   APInt x_old(BitWidth, 1);
   1311   APInt x_new(BitWidth, 0);
   1312   APInt two(BitWidth, 2);
   1313 
   1314   // Select a good starting value using binary logarithms.
   1315   for (;; i += 2, testy = testy.shl(2))
   1316     if (i >= nbits || this->ule(testy)) {
   1317       x_old = x_old.shl(i / 2);
   1318       break;
   1319     }
   1320 
   1321   // Use the Babylonian method to arrive at the integer square root:
   1322   for (;;) {
   1323     x_new = (this->udiv(x_old) + x_old).udiv(two);
   1324     if (x_old.ule(x_new))
   1325       break;
   1326     x_old = x_new;
   1327   }
   1328 
   1329   // Make sure we return the closest approximation
   1330   // NOTE: The rounding calculation below is correct. It will produce an
   1331   // off-by-one discrepancy with results from pari/gp. That discrepancy has been
   1332   // determined to be a rounding issue with pari/gp as it begins to use a
   1333   // floating point representation after 192 bits. There are no discrepancies
   1334   // between this algorithm and pari/gp for bit widths < 192 bits.
   1335   APInt square(x_old * x_old);
   1336   APInt nextSquare((x_old + 1) * (x_old +1));
   1337   if (this->ult(square))
   1338     return x_old;
   1339   assert(this->ule(nextSquare) && "Error in APInt::sqrt computation");
   1340   APInt midpoint((nextSquare - square).udiv(two));
   1341   APInt offset(*this - square);
   1342   if (offset.ult(midpoint))
   1343     return x_old;
   1344   return x_old + 1;
   1345 }
   1346 
   1347 /// Computes the multiplicative inverse of this APInt for a given modulo. The
   1348 /// iterative extended Euclidean algorithm is used to solve for this value,
   1349 /// however we simplify it to speed up calculating only the inverse, and take
   1350 /// advantage of div+rem calculations. We also use some tricks to avoid copying
   1351 /// (potentially large) APInts around.
   1352 APInt APInt::multiplicativeInverse(const APInt& modulo) const {
   1353   assert(ult(modulo) && "This APInt must be smaller than the modulo");
   1354 
   1355   // Using the properties listed at the following web page (accessed 06/21/08):
   1356   //   http://www.numbertheory.org/php/euclid.html
   1357   // (especially the properties numbered 3, 4 and 9) it can be proved that
   1358   // BitWidth bits suffice for all the computations in the algorithm implemented
   1359   // below. More precisely, this number of bits suffice if the multiplicative
   1360   // inverse exists, but may not suffice for the general extended Euclidean
   1361   // algorithm.
   1362 
   1363   APInt r[2] = { modulo, *this };
   1364   APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) };
   1365   APInt q(BitWidth, 0);
   1366 
   1367   unsigned i;
   1368   for (i = 0; r[i^1] != 0; i ^= 1) {
   1369     // An overview of the math without the confusing bit-flipping:
   1370     // q = r[i-2] / r[i-1]
   1371     // r[i] = r[i-2] % r[i-1]
   1372     // t[i] = t[i-2] - t[i-1] * q
   1373     udivrem(r[i], r[i^1], q, r[i]);
   1374     t[i] -= t[i^1] * q;
   1375   }
   1376 
   1377   // If this APInt and the modulo are not coprime, there is no multiplicative
   1378   // inverse, so return 0. We check this by looking at the next-to-last
   1379   // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean
   1380   // algorithm.
   1381   if (r[i] != 1)
   1382     return APInt(BitWidth, 0);
   1383 
   1384   // The next-to-last t is the multiplicative inverse.  However, we are
   1385   // interested in a positive inverse. Calcuate a positive one from a negative
   1386   // one if necessary. A simple addition of the modulo suffices because
   1387   // abs(t[i]) is known to be less than *this/2 (see the link above).
   1388   return t[i].isNegative() ? t[i] + modulo : t[i];
   1389 }
   1390 
   1391 /// Calculate the magic numbers required to implement a signed integer division
   1392 /// by a constant as a sequence of multiplies, adds and shifts.  Requires that
   1393 /// the divisor not be 0, 1, or -1.  Taken from "Hacker's Delight", Henry S.
   1394 /// Warren, Jr., chapter 10.
   1395 APInt::ms APInt::magic() const {
   1396   const APInt& d = *this;
   1397   unsigned p;
   1398   APInt ad, anc, delta, q1, r1, q2, r2, t;
   1399   APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
   1400   struct ms mag;
   1401 
   1402   ad = d.abs();
   1403   t = signedMin + (d.lshr(d.getBitWidth() - 1));
   1404   anc = t - 1 - t.urem(ad);   // absolute value of nc
   1405   p = d.getBitWidth() - 1;    // initialize p
   1406   q1 = signedMin.udiv(anc);   // initialize q1 = 2p/abs(nc)
   1407   r1 = signedMin - q1*anc;    // initialize r1 = rem(2p,abs(nc))
   1408   q2 = signedMin.udiv(ad);    // initialize q2 = 2p/abs(d)
   1409   r2 = signedMin - q2*ad;     // initialize r2 = rem(2p,abs(d))
   1410   do {
   1411     p = p + 1;
   1412     q1 = q1<<1;          // update q1 = 2p/abs(nc)
   1413     r1 = r1<<1;          // update r1 = rem(2p/abs(nc))
   1414     if (r1.uge(anc)) {  // must be unsigned comparison
   1415       q1 = q1 + 1;
   1416       r1 = r1 - anc;
   1417     }
   1418     q2 = q2<<1;          // update q2 = 2p/abs(d)
   1419     r2 = r2<<1;          // update r2 = rem(2p/abs(d))
   1420     if (r2.uge(ad)) {   // must be unsigned comparison
   1421       q2 = q2 + 1;
   1422       r2 = r2 - ad;
   1423     }
   1424     delta = ad - r2;
   1425   } while (q1.ult(delta) || (q1 == delta && r1 == 0));
   1426 
   1427   mag.m = q2 + 1;
   1428   if (d.isNegative()) mag.m = -mag.m;   // resulting magic number
   1429   mag.s = p - d.getBitWidth();          // resulting shift
   1430   return mag;
   1431 }
   1432 
   1433 /// Calculate the magic numbers required to implement an unsigned integer
   1434 /// division by a constant as a sequence of multiplies, adds and shifts.
   1435 /// Requires that the divisor not be 0.  Taken from "Hacker's Delight", Henry
   1436 /// S. Warren, Jr., chapter 10.
   1437 /// LeadingZeros can be used to simplify the calculation if the upper bits
   1438 /// of the divided value are known zero.
   1439 APInt::mu APInt::magicu(unsigned LeadingZeros) const {
   1440   const APInt& d = *this;
   1441   unsigned p;
   1442   APInt nc, delta, q1, r1, q2, r2;
   1443   struct mu magu;
   1444   magu.a = 0;               // initialize "add" indicator
   1445   APInt allOnes = APInt::getAllOnesValue(d.getBitWidth()).lshr(LeadingZeros);
   1446   APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
   1447   APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());
   1448 
   1449   nc = allOnes - (-d).urem(d);
   1450   p = d.getBitWidth() - 1;  // initialize p
   1451   q1 = signedMin.udiv(nc);  // initialize q1 = 2p/nc
   1452   r1 = signedMin - q1*nc;   // initialize r1 = rem(2p,nc)
   1453   q2 = signedMax.udiv(d);   // initialize q2 = (2p-1)/d
   1454   r2 = signedMax - q2*d;    // initialize r2 = rem((2p-1),d)
   1455   do {
   1456     p = p + 1;
   1457     if (r1.uge(nc - r1)) {
   1458       q1 = q1 + q1 + 1;  // update q1
   1459       r1 = r1 + r1 - nc; // update r1
   1460     }
   1461     else {
   1462       q1 = q1+q1; // update q1
   1463       r1 = r1+r1; // update r1
   1464     }
   1465     if ((r2 + 1).uge(d - r2)) {
   1466       if (q2.uge(signedMax)) magu.a = 1;
   1467       q2 = q2+q2 + 1;     // update q2
   1468       r2 = r2+r2 + 1 - d; // update r2
   1469     }
   1470     else {
   1471       if (q2.uge(signedMin)) magu.a = 1;
   1472       q2 = q2+q2;     // update q2
   1473       r2 = r2+r2 + 1; // update r2
   1474     }
   1475     delta = d - 1 - r2;
   1476   } while (p < d.getBitWidth()*2 &&
   1477            (q1.ult(delta) || (q1 == delta && r1 == 0)));
   1478   magu.m = q2 + 1; // resulting magic number
   1479   magu.s = p - d.getBitWidth();  // resulting shift
   1480   return magu;
   1481 }
   1482 
   1483 /// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
   1484 /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
   1485 /// variables here have the same names as in the algorithm. Comments explain
   1486 /// the algorithm and any deviation from it.
   1487 static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r,
   1488                      unsigned m, unsigned n) {
   1489   assert(u && "Must provide dividend");
   1490   assert(v && "Must provide divisor");
   1491   assert(q && "Must provide quotient");
   1492   assert(u != v && u != q && v != q && "Must us different memory");
   1493   assert(n>1 && "n must be > 1");
   1494 
   1495   // Knuth uses the value b as the base of the number system. In our case b
   1496   // is 2^31 so we just set it to -1u.
   1497   uint64_t b = uint64_t(1) << 32;
   1498 
   1499 #if 0
   1500   DEBUG(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n');
   1501   DEBUG(dbgs() << "KnuthDiv: original:");
   1502   DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
   1503   DEBUG(dbgs() << " by");
   1504   DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
   1505   DEBUG(dbgs() << '\n');
   1506 #endif
   1507   // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of
   1508   // u and v by d. Note that we have taken Knuth's advice here to use a power
   1509   // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
   1510   // 2 allows us to shift instead of multiply and it is easy to determine the
   1511   // shift amount from the leading zeros.  We are basically normalizing the u
   1512   // and v so that its high bits are shifted to the top of v's range without
   1513   // overflow. Note that this can require an extra word in u so that u must
   1514   // be of length m+n+1.
   1515   unsigned shift = CountLeadingZeros_32(v[n-1]);
   1516   unsigned v_carry = 0;
   1517   unsigned u_carry = 0;
   1518   if (shift) {
   1519     for (unsigned i = 0; i < m+n; ++i) {
   1520       unsigned u_tmp = u[i] >> (32 - shift);
   1521       u[i] = (u[i] << shift) | u_carry;
   1522       u_carry = u_tmp;
   1523     }
   1524     for (unsigned i = 0; i < n; ++i) {
   1525       unsigned v_tmp = v[i] >> (32 - shift);
   1526       v[i] = (v[i] << shift) | v_carry;
   1527       v_carry = v_tmp;
   1528     }
   1529   }
   1530   u[m+n] = u_carry;
   1531 #if 0
   1532   DEBUG(dbgs() << "KnuthDiv:   normal:");
   1533   DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
   1534   DEBUG(dbgs() << " by");
   1535   DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
   1536   DEBUG(dbgs() << '\n');
   1537 #endif
   1538 
   1539   // D2. [Initialize j.]  Set j to m. This is the loop counter over the places.
   1540   int j = m;
   1541   do {
   1542     DEBUG(dbgs() << "KnuthDiv: quotient digit #" << j << '\n');
   1543     // D3. [Calculate q'.].
   1544     //     Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
   1545     //     Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
   1546     // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
   1547     // qp by 1, inrease rp by v[n-1], and repeat this test if rp < b. The test
   1548     // on v[n-2] determines at high speed most of the cases in which the trial
   1549     // value qp is one too large, and it eliminates all cases where qp is two
   1550     // too large.
   1551     uint64_t dividend = ((uint64_t(u[j+n]) << 32) + u[j+n-1]);
   1552     DEBUG(dbgs() << "KnuthDiv: dividend == " << dividend << '\n');
   1553     uint64_t qp = dividend / v[n-1];
   1554     uint64_t rp = dividend % v[n-1];
   1555     if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
   1556       qp--;
   1557       rp += v[n-1];
   1558       if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
   1559         qp--;
   1560     }
   1561     DEBUG(dbgs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
   1562 
   1563     // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
   1564     // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
   1565     // consists of a simple multiplication by a one-place number, combined with
   1566     // a subtraction.
   1567     bool isNeg = false;
   1568     for (unsigned i = 0; i < n; ++i) {
   1569       uint64_t u_tmp = uint64_t(u[j+i]) | (uint64_t(u[j+i+1]) << 32);
   1570       uint64_t subtrahend = uint64_t(qp) * uint64_t(v[i]);
   1571       bool borrow = subtrahend > u_tmp;
   1572       DEBUG(dbgs() << "KnuthDiv: u_tmp == " << u_tmp
   1573                    << ", subtrahend == " << subtrahend
   1574                    << ", borrow = " << borrow << '\n');
   1575 
   1576       uint64_t result = u_tmp - subtrahend;
   1577       unsigned k = j + i;
   1578       u[k++] = (unsigned)(result & (b-1)); // subtract low word
   1579       u[k++] = (unsigned)(result >> 32);   // subtract high word
   1580       while (borrow && k <= m+n) { // deal with borrow to the left
   1581         borrow = u[k] == 0;
   1582         u[k]--;
   1583         k++;
   1584       }
   1585       isNeg |= borrow;
   1586       DEBUG(dbgs() << "KnuthDiv: u[j+i] == " << u[j+i] << ",  u[j+i+1] == " <<
   1587                     u[j+i+1] << '\n');
   1588     }
   1589     DEBUG(dbgs() << "KnuthDiv: after subtraction:");
   1590     DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
   1591     DEBUG(dbgs() << '\n');
   1592     // The digits (u[j+n]...u[j]) should be kept positive; if the result of
   1593     // this step is actually negative, (u[j+n]...u[j]) should be left as the
   1594     // true value plus b**(n+1), namely as the b's complement of
   1595     // the true value, and a "borrow" to the left should be remembered.
   1596     //
   1597     if (isNeg) {
   1598       bool carry = true;  // true because b's complement is "complement + 1"
   1599       for (unsigned i = 0; i <= m+n; ++i) {
   1600         u[i] = ~u[i] + carry; // b's complement
   1601         carry = carry && u[i] == 0;
   1602       }
   1603     }
   1604     DEBUG(dbgs() << "KnuthDiv: after complement:");
   1605     DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
   1606     DEBUG(dbgs() << '\n');
   1607 
   1608     // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
   1609     // negative, go to step D6; otherwise go on to step D7.
   1610     q[j] = (unsigned)qp;
   1611     if (isNeg) {
   1612       // D6. [Add back]. The probability that this step is necessary is very
   1613       // small, on the order of only 2/b. Make sure that test data accounts for
   1614       // this possibility. Decrease q[j] by 1
   1615       q[j]--;
   1616       // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
   1617       // A carry will occur to the left of u[j+n], and it should be ignored
   1618       // since it cancels with the borrow that occurred in D4.
   1619       bool carry = false;
   1620       for (unsigned i = 0; i < n; i++) {
   1621         unsigned limit = std::min(u[j+i],v[i]);
   1622         u[j+i] += v[i] + carry;
   1623         carry = u[j+i] < limit || (carry && u[j+i] == limit);
   1624       }
   1625       u[j+n] += carry;
   1626     }
   1627     DEBUG(dbgs() << "KnuthDiv: after correction:");
   1628     DEBUG(for (int i = m+n; i >=0; i--) dbgs() <<" " << u[i]);
   1629     DEBUG(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n');
   1630 
   1631   // D7. [Loop on j.]  Decrease j by one. Now if j >= 0, go back to D3.
   1632   } while (--j >= 0);
   1633 
   1634   DEBUG(dbgs() << "KnuthDiv: quotient:");
   1635   DEBUG(for (int i = m; i >=0; i--) dbgs() <<" " << q[i]);
   1636   DEBUG(dbgs() << '\n');
   1637 
   1638   // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
   1639   // remainder may be obtained by dividing u[...] by d. If r is non-null we
   1640   // compute the remainder (urem uses this).
   1641   if (r) {
   1642     // The value d is expressed by the "shift" value above since we avoided
   1643     // multiplication by d by using a shift left. So, all we have to do is
   1644     // shift right here. In order to mak
   1645     if (shift) {
   1646       unsigned carry = 0;
   1647       DEBUG(dbgs() << "KnuthDiv: remainder:");
   1648       for (int i = n-1; i >= 0; i--) {
   1649         r[i] = (u[i] >> shift) | carry;
   1650         carry = u[i] << (32 - shift);
   1651         DEBUG(dbgs() << " " << r[i]);
   1652       }
   1653     } else {
   1654       for (int i = n-1; i >= 0; i--) {
   1655         r[i] = u[i];
   1656         DEBUG(dbgs() << " " << r[i]);
   1657       }
   1658     }
   1659     DEBUG(dbgs() << '\n');
   1660   }
   1661 #if 0
   1662   DEBUG(dbgs() << '\n');
   1663 #endif
   1664 }
   1665 
   1666 void APInt::divide(const APInt LHS, unsigned lhsWords,
   1667                    const APInt &RHS, unsigned rhsWords,
   1668                    APInt *Quotient, APInt *Remainder)
   1669 {
   1670   assert(lhsWords >= rhsWords && "Fractional result");
   1671 
   1672   // First, compose the values into an array of 32-bit words instead of
   1673   // 64-bit words. This is a necessity of both the "short division" algorithm
   1674   // and the Knuth "classical algorithm" which requires there to be native
   1675   // operations for +, -, and * on an m bit value with an m*2 bit result. We
   1676   // can't use 64-bit operands here because we don't have native results of
   1677   // 128-bits. Furthermore, casting the 64-bit values to 32-bit values won't
   1678   // work on large-endian machines.
   1679   uint64_t mask = ~0ull >> (sizeof(unsigned)*CHAR_BIT);
   1680   unsigned n = rhsWords * 2;
   1681   unsigned m = (lhsWords * 2) - n;
   1682 
   1683   // Allocate space for the temporary values we need either on the stack, if
   1684   // it will fit, or on the heap if it won't.
   1685   unsigned SPACE[128];
   1686   unsigned *U = 0;
   1687   unsigned *V = 0;
   1688   unsigned *Q = 0;
   1689   unsigned *R = 0;
   1690   if ((Remainder?4:3)*n+2*m+1 <= 128) {
   1691     U = &SPACE[0];
   1692     V = &SPACE[m+n+1];
   1693     Q = &SPACE[(m+n+1) + n];
   1694     if (Remainder)
   1695       R = &SPACE[(m+n+1) + n + (m+n)];
   1696   } else {
   1697     U = new unsigned[m + n + 1];
   1698     V = new unsigned[n];
   1699     Q = new unsigned[m+n];
   1700     if (Remainder)
   1701       R = new unsigned[n];
   1702   }
   1703 
   1704   // Initialize the dividend
   1705   memset(U, 0, (m+n+1)*sizeof(unsigned));
   1706   for (unsigned i = 0; i < lhsWords; ++i) {
   1707     uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]);
   1708     U[i * 2] = (unsigned)(tmp & mask);
   1709     U[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
   1710   }
   1711   U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
   1712 
   1713   // Initialize the divisor
   1714   memset(V, 0, (n)*sizeof(unsigned));
   1715   for (unsigned i = 0; i < rhsWords; ++i) {
   1716     uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]);
   1717     V[i * 2] = (unsigned)(tmp & mask);
   1718     V[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
   1719   }
   1720 
   1721   // initialize the quotient and remainder
   1722   memset(Q, 0, (m+n) * sizeof(unsigned));
   1723   if (Remainder)
   1724     memset(R, 0, n * sizeof(unsigned));
   1725 
   1726   // Now, adjust m and n for the Knuth division. n is the number of words in
   1727   // the divisor. m is the number of words by which the dividend exceeds the
   1728   // divisor (i.e. m+n is the length of the dividend). These sizes must not
   1729   // contain any zero words or the Knuth algorithm fails.
   1730   for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
   1731     n--;
   1732     m++;
   1733   }
   1734   for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
   1735     m--;
   1736 
   1737   // If we're left with only a single word for the divisor, Knuth doesn't work
   1738   // so we implement the short division algorithm here. This is much simpler
   1739   // and faster because we are certain that we can divide a 64-bit quantity
   1740   // by a 32-bit quantity at hardware speed and short division is simply a
   1741   // series of such operations. This is just like doing short division but we
   1742   // are using base 2^32 instead of base 10.
   1743   assert(n != 0 && "Divide by zero?");
   1744   if (n == 1) {
   1745     unsigned divisor = V[0];
   1746     unsigned remainder = 0;
   1747     for (int i = m+n-1; i >= 0; i--) {
   1748       uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i];
   1749       if (partial_dividend == 0) {
   1750         Q[i] = 0;
   1751         remainder = 0;
   1752       } else if (partial_dividend < divisor) {
   1753         Q[i] = 0;
   1754         remainder = (unsigned)partial_dividend;
   1755       } else if (partial_dividend == divisor) {
   1756         Q[i] = 1;
   1757         remainder = 0;
   1758       } else {
   1759         Q[i] = (unsigned)(partial_dividend / divisor);
   1760         remainder = (unsigned)(partial_dividend - (Q[i] * divisor));
   1761       }
   1762     }
   1763     if (R)
   1764       R[0] = remainder;
   1765   } else {
   1766     // Now we're ready to invoke the Knuth classical divide algorithm. In this
   1767     // case n > 1.
   1768     KnuthDiv(U, V, Q, R, m, n);
   1769   }
   1770 
   1771   // If the caller wants the quotient
   1772   if (Quotient) {
   1773     // Set up the Quotient value's memory.
   1774     if (Quotient->BitWidth != LHS.BitWidth) {
   1775       if (Quotient->isSingleWord())
   1776         Quotient->VAL = 0;
   1777       else
   1778         delete [] Quotient->pVal;
   1779       Quotient->BitWidth = LHS.BitWidth;
   1780       if (!Quotient->isSingleWord())
   1781         Quotient->pVal = getClearedMemory(Quotient->getNumWords());
   1782     } else
   1783       Quotient->clearAllBits();
   1784 
   1785     // The quotient is in Q. Reconstitute the quotient into Quotient's low
   1786     // order words.
   1787     if (lhsWords == 1) {
   1788       uint64_t tmp =
   1789         uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2));
   1790       if (Quotient->isSingleWord())
   1791         Quotient->VAL = tmp;
   1792       else
   1793         Quotient->pVal[0] = tmp;
   1794     } else {
   1795       assert(!Quotient->isSingleWord() && "Quotient APInt not large enough");
   1796       for (unsigned i = 0; i < lhsWords; ++i)
   1797         Quotient->pVal[i] =
   1798           uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2));
   1799     }
   1800   }
   1801 
   1802   // If the caller wants the remainder
   1803   if (Remainder) {
   1804     // Set up the Remainder value's memory.
   1805     if (Remainder->BitWidth != RHS.BitWidth) {
   1806       if (Remainder->isSingleWord())
   1807         Remainder->VAL = 0;
   1808       else
   1809         delete [] Remainder->pVal;
   1810       Remainder->BitWidth = RHS.BitWidth;
   1811       if (!Remainder->isSingleWord())
   1812         Remainder->pVal = getClearedMemory(Remainder->getNumWords());
   1813     } else
   1814       Remainder->clearAllBits();
   1815 
   1816     // The remainder is in R. Reconstitute the remainder into Remainder's low
   1817     // order words.
   1818     if (rhsWords == 1) {
   1819       uint64_t tmp =
   1820         uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2));
   1821       if (Remainder->isSingleWord())
   1822         Remainder->VAL = tmp;
   1823       else
   1824         Remainder->pVal[0] = tmp;
   1825     } else {
   1826       assert(!Remainder->isSingleWord() && "Remainder APInt not large enough");
   1827       for (unsigned i = 0; i < rhsWords; ++i)
   1828         Remainder->pVal[i] =
   1829           uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2));
   1830     }
   1831   }
   1832 
   1833   // Clean up the memory we allocated.
   1834   if (U != &SPACE[0]) {
   1835     delete [] U;
   1836     delete [] V;
   1837     delete [] Q;
   1838     delete [] R;
   1839   }
   1840 }
   1841 
   1842 APInt APInt::udiv(const APInt& RHS) const {
   1843   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
   1844 
   1845   // First, deal with the easy case
   1846   if (isSingleWord()) {
   1847     assert(RHS.VAL != 0 && "Divide by zero?");
   1848     return APInt(BitWidth, VAL / RHS.VAL);
   1849   }
   1850 
   1851   // Get some facts about the LHS and RHS number of bits and words
   1852   unsigned rhsBits = RHS.getActiveBits();
   1853   unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
   1854   assert(rhsWords && "Divided by zero???");
   1855   unsigned lhsBits = this->getActiveBits();
   1856   unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
   1857 
   1858   // Deal with some degenerate cases
   1859   if (!lhsWords)
   1860     // 0 / X ===> 0
   1861     return APInt(BitWidth, 0);
   1862   else if (lhsWords < rhsWords || this->ult(RHS)) {
   1863     // X / Y ===> 0, iff X < Y
   1864     return APInt(BitWidth, 0);
   1865   } else if (*this == RHS) {
   1866     // X / X ===> 1
   1867     return APInt(BitWidth, 1);
   1868   } else if (lhsWords == 1 && rhsWords == 1) {
   1869     // All high words are zero, just use native divide
   1870     return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]);
   1871   }
   1872 
   1873   // We have to compute it the hard way. Invoke the Knuth divide algorithm.
   1874   APInt Quotient(1,0); // to hold result.
   1875   divide(*this, lhsWords, RHS, rhsWords, &Quotient, 0);
   1876   return Quotient;
   1877 }
   1878 
   1879 APInt APInt::urem(const APInt& RHS) const {
   1880   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
   1881   if (isSingleWord()) {
   1882     assert(RHS.VAL != 0 && "Remainder by zero?");
   1883     return APInt(BitWidth, VAL % RHS.VAL);
   1884   }
   1885 
   1886   // Get some facts about the LHS
   1887   unsigned lhsBits = getActiveBits();
   1888   unsigned lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1);
   1889 
   1890   // Get some facts about the RHS
   1891   unsigned rhsBits = RHS.getActiveBits();
   1892   unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
   1893   assert(rhsWords && "Performing remainder operation by zero ???");
   1894 
   1895   // Check the degenerate cases
   1896   if (lhsWords == 0) {
   1897     // 0 % Y ===> 0
   1898     return APInt(BitWidth, 0);
   1899   } else if (lhsWords < rhsWords || this->ult(RHS)) {
   1900     // X % Y ===> X, iff X < Y
   1901     return *this;
   1902   } else if (*this == RHS) {
   1903     // X % X == 0;
   1904     return APInt(BitWidth, 0);
   1905   } else if (lhsWords == 1) {
   1906     // All high words are zero, just use native remainder
   1907     return APInt(BitWidth, pVal[0] % RHS.pVal[0]);
   1908   }
   1909 
   1910   // We have to compute it the hard way. Invoke the Knuth divide algorithm.
   1911   APInt Remainder(1,0);
   1912   divide(*this, lhsWords, RHS, rhsWords, 0, &Remainder);
   1913   return Remainder;
   1914 }
   1915 
   1916 void APInt::udivrem(const APInt &LHS, const APInt &RHS,
   1917                     APInt &Quotient, APInt &Remainder) {
   1918   // Get some size facts about the dividend and divisor
   1919   unsigned lhsBits  = LHS.getActiveBits();
   1920   unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
   1921   unsigned rhsBits  = RHS.getActiveBits();
   1922   unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
   1923 
   1924   // Check the degenerate cases
   1925   if (lhsWords == 0) {
   1926     Quotient = 0;                // 0 / Y ===> 0
   1927     Remainder = 0;               // 0 % Y ===> 0
   1928     return;
   1929   }
   1930 
   1931   if (lhsWords < rhsWords || LHS.ult(RHS)) {
   1932     Remainder = LHS;            // X % Y ===> X, iff X < Y
   1933     Quotient = 0;               // X / Y ===> 0, iff X < Y
   1934     return;
   1935   }
   1936 
   1937   if (LHS == RHS) {
   1938     Quotient  = 1;              // X / X ===> 1
   1939     Remainder = 0;              // X % X ===> 0;
   1940     return;
   1941   }
   1942 
   1943   if (lhsWords == 1 && rhsWords == 1) {
   1944     // There is only one word to consider so use the native versions.
   1945     uint64_t lhsValue = LHS.isSingleWord() ? LHS.VAL : LHS.pVal[0];
   1946     uint64_t rhsValue = RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
   1947     Quotient = APInt(LHS.getBitWidth(), lhsValue / rhsValue);
   1948     Remainder = APInt(LHS.getBitWidth(), lhsValue % rhsValue);
   1949     return;
   1950   }
   1951 
   1952   // Okay, lets do it the long way
   1953   divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder);
   1954 }
   1955 
   1956 APInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const {
   1957   APInt Res = *this+RHS;
   1958   Overflow = isNonNegative() == RHS.isNonNegative() &&
   1959              Res.isNonNegative() != isNonNegative();
   1960   return Res;
   1961 }
   1962 
   1963 APInt APInt::uadd_ov(const APInt &RHS, bool &Overflow) const {
   1964   APInt Res = *this+RHS;
   1965   Overflow = Res.ult(RHS);
   1966   return Res;
   1967 }
   1968 
   1969 APInt APInt::ssub_ov(const APInt &RHS, bool &Overflow) const {
   1970   APInt Res = *this - RHS;
   1971   Overflow = isNonNegative() != RHS.isNonNegative() &&
   1972              Res.isNonNegative() != isNonNegative();
   1973   return Res;
   1974 }
   1975 
   1976 APInt APInt::usub_ov(const APInt &RHS, bool &Overflow) const {
   1977   APInt Res = *this-RHS;
   1978   Overflow = Res.ugt(*this);
   1979   return Res;
   1980 }
   1981 
   1982 APInt APInt::sdiv_ov(const APInt &RHS, bool &Overflow) const {
   1983   // MININT/-1  -->  overflow.
   1984   Overflow = isMinSignedValue() && RHS.isAllOnesValue();
   1985   return sdiv(RHS);
   1986 }
   1987 
   1988 APInt APInt::smul_ov(const APInt &RHS, bool &Overflow) const {
   1989   APInt Res = *this * RHS;
   1990 
   1991   if (*this != 0 && RHS != 0)
   1992     Overflow = Res.sdiv(RHS) != *this || Res.sdiv(*this) != RHS;
   1993   else
   1994     Overflow = false;
   1995   return Res;
   1996 }
   1997 
   1998 APInt APInt::umul_ov(const APInt &RHS, bool &Overflow) const {
   1999   APInt Res = *this * RHS;
   2000 
   2001   if (*this != 0 && RHS != 0)
   2002     Overflow = Res.udiv(RHS) != *this || Res.udiv(*this) != RHS;
   2003   else
   2004     Overflow = false;
   2005   return Res;
   2006 }
   2007 
   2008 APInt APInt::sshl_ov(unsigned ShAmt, bool &Overflow) const {
   2009   Overflow = ShAmt >= getBitWidth();
   2010   if (Overflow)
   2011     ShAmt = getBitWidth()-1;
   2012 
   2013   if (isNonNegative()) // Don't allow sign change.
   2014     Overflow = ShAmt >= countLeadingZeros();
   2015   else
   2016     Overflow = ShAmt >= countLeadingOnes();
   2017 
   2018   return *this << ShAmt;
   2019 }
   2020 
   2021 
   2022 
   2023 
   2024 void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) {
   2025   // Check our assumptions here
   2026   assert(!str.empty() && "Invalid string length");
   2027   assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
   2028           radix == 36) &&
   2029          "Radix should be 2, 8, 10, 16, or 36!");
   2030 
   2031   StringRef::iterator p = str.begin();
   2032   size_t slen = str.size();
   2033   bool isNeg = *p == '-';
   2034   if (*p == '-' || *p == '+') {
   2035     p++;
   2036     slen--;
   2037     assert(slen && "String is only a sign, needs a value.");
   2038   }
   2039   assert((slen <= numbits || radix != 2) && "Insufficient bit width");
   2040   assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width");
   2041   assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width");
   2042   assert((((slen-1)*64)/22 <= numbits || radix != 10) &&
   2043          "Insufficient bit width");
   2044 
   2045   // Allocate memory
   2046   if (!isSingleWord())
   2047     pVal = getClearedMemory(getNumWords());
   2048 
   2049   // Figure out if we can shift instead of multiply
   2050   unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
   2051 
   2052   // Set up an APInt for the digit to add outside the loop so we don't
   2053   // constantly construct/destruct it.
   2054   APInt apdigit(getBitWidth(), 0);
   2055   APInt apradix(getBitWidth(), radix);
   2056 
   2057   // Enter digit traversal loop
   2058   for (StringRef::iterator e = str.end(); p != e; ++p) {
   2059     unsigned digit = getDigit(*p, radix);
   2060     assert(digit < radix && "Invalid character in digit string");
   2061 
   2062     // Shift or multiply the value by the radix
   2063     if (slen > 1) {
   2064       if (shift)
   2065         *this <<= shift;
   2066       else
   2067         *this *= apradix;
   2068     }
   2069 
   2070     // Add in the digit we just interpreted
   2071     if (apdigit.isSingleWord())
   2072       apdigit.VAL = digit;
   2073     else
   2074       apdigit.pVal[0] = digit;
   2075     *this += apdigit;
   2076   }
   2077   // If its negative, put it in two's complement form
   2078   if (isNeg) {
   2079     (*this)--;
   2080     this->flipAllBits();
   2081   }
   2082 }
   2083 
   2084 void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix,
   2085                      bool Signed, bool formatAsCLiteral) const {
   2086   assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 ||
   2087           Radix == 36) &&
   2088          "Radix should be 2, 8, 10, 16, or 36!");
   2089 
   2090   const char *Prefix = "";
   2091   if (formatAsCLiteral) {
   2092     switch (Radix) {
   2093       case 2:
   2094         // Binary literals are a non-standard extension added in gcc 4.3:
   2095         // http://gcc.gnu.org/onlinedocs/gcc-4.3.0/gcc/Binary-constants.html
   2096         Prefix = "0b";
   2097         break;
   2098       case 8:
   2099         Prefix = "0";
   2100         break;
   2101       case 10:
   2102         break; // No prefix
   2103       case 16:
   2104         Prefix = "0x";
   2105         break;
   2106       default:
   2107         llvm_unreachable("Invalid radix!");
   2108     }
   2109   }
   2110 
   2111   // First, check for a zero value and just short circuit the logic below.
   2112   if (*this == 0) {
   2113     while (*Prefix) {
   2114       Str.push_back(*Prefix);
   2115       ++Prefix;
   2116     };
   2117     Str.push_back('0');
   2118     return;
   2119   }
   2120 
   2121   static const char Digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
   2122 
   2123   if (isSingleWord()) {
   2124     char Buffer[65];
   2125     char *BufPtr = Buffer+65;
   2126 
   2127     uint64_t N;
   2128     if (!Signed) {
   2129       N = getZExtValue();
   2130     } else {
   2131       int64_t I = getSExtValue();
   2132       if (I >= 0) {
   2133         N = I;
   2134       } else {
   2135         Str.push_back('-');
   2136         N = -(uint64_t)I;
   2137       }
   2138     }
   2139 
   2140     while (*Prefix) {
   2141       Str.push_back(*Prefix);
   2142       ++Prefix;
   2143     };
   2144 
   2145     while (N) {
   2146       *--BufPtr = Digits[N % Radix];
   2147       N /= Radix;
   2148     }
   2149     Str.append(BufPtr, Buffer+65);
   2150     return;
   2151   }
   2152 
   2153   APInt Tmp(*this);
   2154 
   2155   if (Signed && isNegative()) {
   2156     // They want to print the signed version and it is a negative value
   2157     // Flip the bits and add one to turn it into the equivalent positive
   2158     // value and put a '-' in the result.
   2159     Tmp.flipAllBits();
   2160     Tmp++;
   2161     Str.push_back('-');
   2162   }
   2163 
   2164   while (*Prefix) {
   2165     Str.push_back(*Prefix);
   2166     ++Prefix;
   2167   };
   2168 
   2169   // We insert the digits backward, then reverse them to get the right order.
   2170   unsigned StartDig = Str.size();
   2171 
   2172   // For the 2, 8 and 16 bit cases, we can just shift instead of divide
   2173   // because the number of bits per digit (1, 3 and 4 respectively) divides
   2174   // equaly.  We just shift until the value is zero.
   2175   if (Radix == 2 || Radix == 8 || Radix == 16) {
   2176     // Just shift tmp right for each digit width until it becomes zero
   2177     unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
   2178     unsigned MaskAmt = Radix - 1;
   2179 
   2180     while (Tmp != 0) {
   2181       unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;
   2182       Str.push_back(Digits[Digit]);
   2183       Tmp = Tmp.lshr(ShiftAmt);
   2184     }
   2185   } else {
   2186     APInt divisor(Radix == 10? 4 : 8, Radix);
   2187     while (Tmp != 0) {
   2188       APInt APdigit(1, 0);
   2189       APInt tmp2(Tmp.getBitWidth(), 0);
   2190       divide(Tmp, Tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2,
   2191              &APdigit);
   2192       unsigned Digit = (unsigned)APdigit.getZExtValue();
   2193       assert(Digit < Radix && "divide failed");
   2194       Str.push_back(Digits[Digit]);
   2195       Tmp = tmp2;
   2196     }
   2197   }
   2198 
   2199   // Reverse the digits before returning.
   2200   std::reverse(Str.begin()+StartDig, Str.end());
   2201 }
   2202 
   2203 /// toString - This returns the APInt as a std::string.  Note that this is an
   2204 /// inefficient method.  It is better to pass in a SmallVector/SmallString
   2205 /// to the methods above.
   2206 std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const {
   2207   SmallString<40> S;
   2208   toString(S, Radix, Signed, /* formatAsCLiteral = */false);
   2209   return S.str();
   2210 }
   2211 
   2212 
   2213 void APInt::dump() const {
   2214   SmallString<40> S, U;
   2215   this->toStringUnsigned(U);
   2216   this->toStringSigned(S);
   2217   dbgs() << "APInt(" << BitWidth << "b, "
   2218          << U.str() << "u " << S.str() << "s)";
   2219 }
   2220 
   2221 void APInt::print(raw_ostream &OS, bool isSigned) const {
   2222   SmallString<40> S;
   2223   this->toString(S, 10, isSigned, /* formatAsCLiteral = */false);
   2224   OS << S.str();
   2225 }
   2226 
   2227 // This implements a variety of operations on a representation of
   2228 // arbitrary precision, two's-complement, bignum integer values.
   2229 
   2230 // Assumed by lowHalf, highHalf, partMSB and partLSB.  A fairly safe
   2231 // and unrestricting assumption.
   2232 #define COMPILE_TIME_ASSERT(cond) extern int CTAssert[(cond) ? 1 : -1]
   2233 COMPILE_TIME_ASSERT(integerPartWidth % 2 == 0);
   2234 
   2235 /* Some handy functions local to this file.  */
   2236 namespace {
   2237 
   2238   /* Returns the integer part with the least significant BITS set.
   2239      BITS cannot be zero.  */
   2240   static inline integerPart
   2241   lowBitMask(unsigned int bits)
   2242   {
   2243     assert(bits != 0 && bits <= integerPartWidth);
   2244 
   2245     return ~(integerPart) 0 >> (integerPartWidth - bits);
   2246   }
   2247 
   2248   /* Returns the value of the lower half of PART.  */
   2249   static inline integerPart
   2250   lowHalf(integerPart part)
   2251   {
   2252     return part & lowBitMask(integerPartWidth / 2);
   2253   }
   2254 
   2255   /* Returns the value of the upper half of PART.  */
   2256   static inline integerPart
   2257   highHalf(integerPart part)
   2258   {
   2259     return part >> (integerPartWidth / 2);
   2260   }
   2261 
   2262   /* Returns the bit number of the most significant set bit of a part.
   2263      If the input number has no bits set -1U is returned.  */
   2264   static unsigned int
   2265   partMSB(integerPart value)
   2266   {
   2267     unsigned int n, msb;
   2268 
   2269     if (value == 0)
   2270       return -1U;
   2271 
   2272     n = integerPartWidth / 2;
   2273 
   2274     msb = 0;
   2275     do {
   2276       if (value >> n) {
   2277         value >>= n;
   2278         msb += n;
   2279       }
   2280 
   2281       n >>= 1;
   2282     } while (n);
   2283 
   2284     return msb;
   2285   }
   2286 
   2287   /* Returns the bit number of the least significant set bit of a
   2288      part.  If the input number has no bits set -1U is returned.  */
   2289   static unsigned int
   2290   partLSB(integerPart value)
   2291   {
   2292     unsigned int n, lsb;
   2293 
   2294     if (value == 0)
   2295       return -1U;
   2296 
   2297     lsb = integerPartWidth - 1;
   2298     n = integerPartWidth / 2;
   2299 
   2300     do {
   2301       if (value << n) {
   2302         value <<= n;
   2303         lsb -= n;
   2304       }
   2305 
   2306       n >>= 1;
   2307     } while (n);
   2308 
   2309     return lsb;
   2310   }
   2311 }
   2312 
   2313 /* Sets the least significant part of a bignum to the input value, and
   2314    zeroes out higher parts.  */
   2315 void
   2316 APInt::tcSet(integerPart *dst, integerPart part, unsigned int parts)
   2317 {
   2318   unsigned int i;
   2319 
   2320   assert(parts > 0);
   2321 
   2322   dst[0] = part;
   2323   for (i = 1; i < parts; i++)
   2324     dst[i] = 0;
   2325 }
   2326 
   2327 /* Assign one bignum to another.  */
   2328 void
   2329 APInt::tcAssign(integerPart *dst, const integerPart *src, unsigned int parts)
   2330 {
   2331   unsigned int i;
   2332 
   2333   for (i = 0; i < parts; i++)
   2334     dst[i] = src[i];
   2335 }
   2336 
   2337 /* Returns true if a bignum is zero, false otherwise.  */
   2338 bool
   2339 APInt::tcIsZero(const integerPart *src, unsigned int parts)
   2340 {
   2341   unsigned int i;
   2342 
   2343   for (i = 0; i < parts; i++)
   2344     if (src[i])
   2345       return false;
   2346 
   2347   return true;
   2348 }
   2349 
   2350 /* Extract the given bit of a bignum; returns 0 or 1.  */
   2351 int
   2352 APInt::tcExtractBit(const integerPart *parts, unsigned int bit)
   2353 {
   2354   return (parts[bit / integerPartWidth] &
   2355           ((integerPart) 1 << bit % integerPartWidth)) != 0;
   2356 }
   2357 
   2358 /* Set the given bit of a bignum. */
   2359 void
   2360 APInt::tcSetBit(integerPart *parts, unsigned int bit)
   2361 {
   2362   parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth);
   2363 }
   2364 
   2365 /* Clears the given bit of a bignum. */
   2366 void
   2367 APInt::tcClearBit(integerPart *parts, unsigned int bit)
   2368 {
   2369   parts[bit / integerPartWidth] &=
   2370     ~((integerPart) 1 << (bit % integerPartWidth));
   2371 }
   2372 
   2373 /* Returns the bit number of the least significant set bit of a
   2374    number.  If the input number has no bits set -1U is returned.  */
   2375 unsigned int
   2376 APInt::tcLSB(const integerPart *parts, unsigned int n)
   2377 {
   2378   unsigned int i, lsb;
   2379 
   2380   for (i = 0; i < n; i++) {
   2381       if (parts[i] != 0) {
   2382           lsb = partLSB(parts[i]);
   2383 
   2384           return lsb + i * integerPartWidth;
   2385       }
   2386   }
   2387 
   2388   return -1U;
   2389 }
   2390 
   2391 /* Returns the bit number of the most significant set bit of a number.
   2392    If the input number has no bits set -1U is returned.  */
   2393 unsigned int
   2394 APInt::tcMSB(const integerPart *parts, unsigned int n)
   2395 {
   2396   unsigned int msb;
   2397 
   2398   do {
   2399     --n;
   2400 
   2401     if (parts[n] != 0) {
   2402       msb = partMSB(parts[n]);
   2403 
   2404       return msb + n * integerPartWidth;
   2405     }
   2406   } while (n);
   2407 
   2408   return -1U;
   2409 }
   2410 
   2411 /* Copy the bit vector of width srcBITS from SRC, starting at bit
   2412    srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
   2413    the least significant bit of DST.  All high bits above srcBITS in
   2414    DST are zero-filled.  */
   2415 void
   2416 APInt::tcExtract(integerPart *dst, unsigned int dstCount,const integerPart *src,
   2417                  unsigned int srcBits, unsigned int srcLSB)
   2418 {
   2419   unsigned int firstSrcPart, dstParts, shift, n;
   2420 
   2421   dstParts = (srcBits + integerPartWidth - 1) / integerPartWidth;
   2422   assert(dstParts <= dstCount);
   2423 
   2424   firstSrcPart = srcLSB / integerPartWidth;
   2425   tcAssign (dst, src + firstSrcPart, dstParts);
   2426 
   2427   shift = srcLSB % integerPartWidth;
   2428   tcShiftRight (dst, dstParts, shift);
   2429 
   2430   /* We now have (dstParts * integerPartWidth - shift) bits from SRC
   2431      in DST.  If this is less that srcBits, append the rest, else
   2432      clear the high bits.  */
   2433   n = dstParts * integerPartWidth - shift;
   2434   if (n < srcBits) {
   2435     integerPart mask = lowBitMask (srcBits - n);
   2436     dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
   2437                           << n % integerPartWidth);
   2438   } else if (n > srcBits) {
   2439     if (srcBits % integerPartWidth)
   2440       dst[dstParts - 1] &= lowBitMask (srcBits % integerPartWidth);
   2441   }
   2442 
   2443   /* Clear high parts.  */
   2444   while (dstParts < dstCount)
   2445     dst[dstParts++] = 0;
   2446 }
   2447 
   2448 /* DST += RHS + C where C is zero or one.  Returns the carry flag.  */
   2449 integerPart
   2450 APInt::tcAdd(integerPart *dst, const integerPart *rhs,
   2451              integerPart c, unsigned int parts)
   2452 {
   2453   unsigned int i;
   2454 
   2455   assert(c <= 1);
   2456 
   2457   for (i = 0; i < parts; i++) {
   2458     integerPart l;
   2459 
   2460     l = dst[i];
   2461     if (c) {
   2462       dst[i] += rhs[i] + 1;
   2463       c = (dst[i] <= l);
   2464     } else {
   2465       dst[i] += rhs[i];
   2466       c = (dst[i] < l);
   2467     }
   2468   }
   2469 
   2470   return c;
   2471 }
   2472 
   2473 /* DST -= RHS + C where C is zero or one.  Returns the carry flag.  */
   2474 integerPart
   2475 APInt::tcSubtract(integerPart *dst, const integerPart *rhs,
   2476                   integerPart c, unsigned int parts)
   2477 {
   2478   unsigned int i;
   2479 
   2480   assert(c <= 1);
   2481 
   2482   for (i = 0; i < parts; i++) {
   2483     integerPart l;
   2484 
   2485     l = dst[i];
   2486     if (c) {
   2487       dst[i] -= rhs[i] + 1;
   2488       c = (dst[i] >= l);
   2489     } else {
   2490       dst[i] -= rhs[i];
   2491       c = (dst[i] > l);
   2492     }
   2493   }
   2494 
   2495   return c;
   2496 }
   2497 
   2498 /* Negate a bignum in-place.  */
   2499 void
   2500 APInt::tcNegate(integerPart *dst, unsigned int parts)
   2501 {
   2502   tcComplement(dst, parts);
   2503   tcIncrement(dst, parts);
   2504 }
   2505 
   2506 /*  DST += SRC * MULTIPLIER + CARRY   if add is true
   2507     DST  = SRC * MULTIPLIER + CARRY   if add is false
   2508 
   2509     Requires 0 <= DSTPARTS <= SRCPARTS + 1.  If DST overlaps SRC
   2510     they must start at the same point, i.e. DST == SRC.
   2511 
   2512     If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
   2513     returned.  Otherwise DST is filled with the least significant
   2514     DSTPARTS parts of the result, and if all of the omitted higher
   2515     parts were zero return zero, otherwise overflow occurred and
   2516     return one.  */
   2517 int
   2518 APInt::tcMultiplyPart(integerPart *dst, const integerPart *src,
   2519                       integerPart multiplier, integerPart carry,
   2520                       unsigned int srcParts, unsigned int dstParts,
   2521                       bool add)
   2522 {
   2523   unsigned int i, n;
   2524 
   2525   /* Otherwise our writes of DST kill our later reads of SRC.  */
   2526   assert(dst <= src || dst >= src + srcParts);
   2527   assert(dstParts <= srcParts + 1);
   2528 
   2529   /* N loops; minimum of dstParts and srcParts.  */
   2530   n = dstParts < srcParts ? dstParts: srcParts;
   2531 
   2532   for (i = 0; i < n; i++) {
   2533     integerPart low, mid, high, srcPart;
   2534 
   2535       /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
   2536 
   2537          This cannot overflow, because
   2538 
   2539          (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
   2540 
   2541          which is less than n^2.  */
   2542 
   2543     srcPart = src[i];
   2544 
   2545     if (multiplier == 0 || srcPart == 0)        {
   2546       low = carry;
   2547       high = 0;
   2548     } else {
   2549       low = lowHalf(srcPart) * lowHalf(multiplier);
   2550       high = highHalf(srcPart) * highHalf(multiplier);
   2551 
   2552       mid = lowHalf(srcPart) * highHalf(multiplier);
   2553       high += highHalf(mid);
   2554       mid <<= integerPartWidth / 2;
   2555       if (low + mid < low)
   2556         high++;
   2557       low += mid;
   2558 
   2559       mid = highHalf(srcPart) * lowHalf(multiplier);
   2560       high += highHalf(mid);
   2561       mid <<= integerPartWidth / 2;
   2562       if (low + mid < low)
   2563         high++;
   2564       low += mid;
   2565 
   2566       /* Now add carry.  */
   2567       if (low + carry < low)
   2568         high++;
   2569       low += carry;
   2570     }
   2571 
   2572     if (add) {
   2573       /* And now DST[i], and store the new low part there.  */
   2574       if (low + dst[i] < low)
   2575         high++;
   2576       dst[i] += low;
   2577     } else
   2578       dst[i] = low;
   2579 
   2580     carry = high;
   2581   }
   2582 
   2583   if (i < dstParts) {
   2584     /* Full multiplication, there is no overflow.  */
   2585     assert(i + 1 == dstParts);
   2586     dst[i] = carry;
   2587     return 0;
   2588   } else {
   2589     /* We overflowed if there is carry.  */
   2590     if (carry)
   2591       return 1;
   2592 
   2593     /* We would overflow if any significant unwritten parts would be
   2594        non-zero.  This is true if any remaining src parts are non-zero
   2595        and the multiplier is non-zero.  */
   2596     if (multiplier)
   2597       for (; i < srcParts; i++)
   2598         if (src[i])
   2599           return 1;
   2600 
   2601     /* We fitted in the narrow destination.  */
   2602     return 0;
   2603   }
   2604 }
   2605 
   2606 /* DST = LHS * RHS, where DST has the same width as the operands and
   2607    is filled with the least significant parts of the result.  Returns
   2608    one if overflow occurred, otherwise zero.  DST must be disjoint
   2609    from both operands.  */
   2610 int
   2611 APInt::tcMultiply(integerPart *dst, const integerPart *lhs,
   2612                   const integerPart *rhs, unsigned int parts)
   2613 {
   2614   unsigned int i;
   2615   int overflow;
   2616 
   2617   assert(dst != lhs && dst != rhs);
   2618 
   2619   overflow = 0;
   2620   tcSet(dst, 0, parts);
   2621 
   2622   for (i = 0; i < parts; i++)
   2623     overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
   2624                                parts - i, true);
   2625 
   2626   return overflow;
   2627 }
   2628 
   2629 /* DST = LHS * RHS, where DST has width the sum of the widths of the
   2630    operands.  No overflow occurs.  DST must be disjoint from both
   2631    operands.  Returns the number of parts required to hold the
   2632    result.  */
   2633 unsigned int
   2634 APInt::tcFullMultiply(integerPart *dst, const integerPart *lhs,
   2635                       const integerPart *rhs, unsigned int lhsParts,
   2636                       unsigned int rhsParts)
   2637 {
   2638   /* Put the narrower number on the LHS for less loops below.  */
   2639   if (lhsParts > rhsParts) {
   2640     return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
   2641   } else {
   2642     unsigned int n;
   2643 
   2644     assert(dst != lhs && dst != rhs);
   2645 
   2646     tcSet(dst, 0, rhsParts);
   2647 
   2648     for (n = 0; n < lhsParts; n++)
   2649       tcMultiplyPart(&dst[n], rhs, lhs[n], 0, rhsParts, rhsParts + 1, true);
   2650 
   2651     n = lhsParts + rhsParts;
   2652 
   2653     return n - (dst[n - 1] == 0);
   2654   }
   2655 }
   2656 
   2657 /* If RHS is zero LHS and REMAINDER are left unchanged, return one.
   2658    Otherwise set LHS to LHS / RHS with the fractional part discarded,
   2659    set REMAINDER to the remainder, return zero.  i.e.
   2660 
   2661    OLD_LHS = RHS * LHS + REMAINDER
   2662 
   2663    SCRATCH is a bignum of the same size as the operands and result for
   2664    use by the routine; its contents need not be initialized and are
   2665    destroyed.  LHS, REMAINDER and SCRATCH must be distinct.
   2666 */
   2667 int
   2668 APInt::tcDivide(integerPart *lhs, const integerPart *rhs,
   2669                 integerPart *remainder, integerPart *srhs,
   2670                 unsigned int parts)
   2671 {
   2672   unsigned int n, shiftCount;
   2673   integerPart mask;
   2674 
   2675   assert(lhs != remainder && lhs != srhs && remainder != srhs);
   2676 
   2677   shiftCount = tcMSB(rhs, parts) + 1;
   2678   if (shiftCount == 0)
   2679     return true;
   2680 
   2681   shiftCount = parts * integerPartWidth - shiftCount;
   2682   n = shiftCount / integerPartWidth;
   2683   mask = (integerPart) 1 << (shiftCount % integerPartWidth);
   2684 
   2685   tcAssign(srhs, rhs, parts);
   2686   tcShiftLeft(srhs, parts, shiftCount);
   2687   tcAssign(remainder, lhs, parts);
   2688   tcSet(lhs, 0, parts);
   2689 
   2690   /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
   2691      the total.  */
   2692   for (;;) {
   2693       int compare;
   2694 
   2695       compare = tcCompare(remainder, srhs, parts);
   2696       if (compare >= 0) {
   2697         tcSubtract(remainder, srhs, 0, parts);
   2698         lhs[n] |= mask;
   2699       }
   2700 
   2701       if (shiftCount == 0)
   2702         break;
   2703       shiftCount--;
   2704       tcShiftRight(srhs, parts, 1);
   2705       if ((mask >>= 1) == 0)
   2706         mask = (integerPart) 1 << (integerPartWidth - 1), n--;
   2707   }
   2708 
   2709   return false;
   2710 }
   2711 
   2712 /* Shift a bignum left COUNT bits in-place.  Shifted in bits are zero.
   2713    There are no restrictions on COUNT.  */
   2714 void
   2715 APInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count)
   2716 {
   2717   if (count) {
   2718     unsigned int jump, shift;
   2719 
   2720     /* Jump is the inter-part jump; shift is is intra-part shift.  */
   2721     jump = count / integerPartWidth;
   2722     shift = count % integerPartWidth;
   2723 
   2724     while (parts > jump) {
   2725       integerPart part;
   2726 
   2727       parts--;
   2728 
   2729       /* dst[i] comes from the two parts src[i - jump] and, if we have
   2730          an intra-part shift, src[i - jump - 1].  */
   2731       part = dst[parts - jump];
   2732       if (shift) {
   2733         part <<= shift;
   2734         if (parts >= jump + 1)
   2735           part |= dst[parts - jump - 1] >> (integerPartWidth - shift);
   2736       }
   2737 
   2738       dst[parts] = part;
   2739     }
   2740 
   2741     while (parts > 0)
   2742       dst[--parts] = 0;
   2743   }
   2744 }
   2745 
   2746 /* Shift a bignum right COUNT bits in-place.  Shifted in bits are
   2747    zero.  There are no restrictions on COUNT.  */
   2748 void
   2749 APInt::tcShiftRight(integerPart *dst, unsigned int parts, unsigned int count)
   2750 {
   2751   if (count) {
   2752     unsigned int i, jump, shift;
   2753 
   2754     /* Jump is the inter-part jump; shift is is intra-part shift.  */
   2755     jump = count / integerPartWidth;
   2756     shift = count % integerPartWidth;
   2757 
   2758     /* Perform the shift.  This leaves the most significant COUNT bits
   2759        of the result at zero.  */
   2760     for (i = 0; i < parts; i++) {
   2761       integerPart part;
   2762 
   2763       if (i + jump >= parts) {
   2764         part = 0;
   2765       } else {
   2766         part = dst[i + jump];
   2767         if (shift) {
   2768           part >>= shift;
   2769           if (i + jump + 1 < parts)
   2770             part |= dst[i + jump + 1] << (integerPartWidth - shift);
   2771         }
   2772       }
   2773 
   2774       dst[i] = part;
   2775     }
   2776   }
   2777 }
   2778 
   2779 /* Bitwise and of two bignums.  */
   2780 void
   2781 APInt::tcAnd(integerPart *dst, const integerPart *rhs, unsigned int parts)
   2782 {
   2783   unsigned int i;
   2784 
   2785   for (i = 0; i < parts; i++)
   2786     dst[i] &= rhs[i];
   2787 }
   2788 
   2789 /* Bitwise inclusive or of two bignums.  */
   2790 void
   2791 APInt::tcOr(integerPart *dst, const integerPart *rhs, unsigned int parts)
   2792 {
   2793   unsigned int i;
   2794 
   2795   for (i = 0; i < parts; i++)
   2796     dst[i] |= rhs[i];
   2797 }
   2798 
   2799 /* Bitwise exclusive or of two bignums.  */
   2800 void
   2801 APInt::tcXor(integerPart *dst, const integerPart *rhs, unsigned int parts)
   2802 {
   2803   unsigned int i;
   2804 
   2805   for (i = 0; i < parts; i++)
   2806     dst[i] ^= rhs[i];
   2807 }
   2808 
   2809 /* Complement a bignum in-place.  */
   2810 void
   2811 APInt::tcComplement(integerPart *dst, unsigned int parts)
   2812 {
   2813   unsigned int i;
   2814 
   2815   for (i = 0; i < parts; i++)
   2816     dst[i] = ~dst[i];
   2817 }
   2818 
   2819 /* Comparison (unsigned) of two bignums.  */
   2820 int
   2821 APInt::tcCompare(const integerPart *lhs, const integerPart *rhs,
   2822                  unsigned int parts)
   2823 {
   2824   while (parts) {
   2825       parts--;
   2826       if (lhs[parts] == rhs[parts])
   2827         continue;
   2828 
   2829       if (lhs[parts] > rhs[parts])
   2830         return 1;
   2831       else
   2832         return -1;
   2833     }
   2834 
   2835   return 0;
   2836 }
   2837 
   2838 /* Increment a bignum in-place, return the carry flag.  */
   2839 integerPart
   2840 APInt::tcIncrement(integerPart *dst, unsigned int parts)
   2841 {
   2842   unsigned int i;
   2843 
   2844   for (i = 0; i < parts; i++)
   2845     if (++dst[i] != 0)
   2846       break;
   2847 
   2848   return i == parts;
   2849 }
   2850 
   2851 /* Set the least significant BITS bits of a bignum, clear the
   2852    rest.  */
   2853 void
   2854 APInt::tcSetLeastSignificantBits(integerPart *dst, unsigned int parts,
   2855                                  unsigned int bits)
   2856 {
   2857   unsigned int i;
   2858 
   2859   i = 0;
   2860   while (bits > integerPartWidth) {
   2861     dst[i++] = ~(integerPart) 0;
   2862     bits -= integerPartWidth;
   2863   }
   2864 
   2865   if (bits)
   2866     dst[i++] = ~(integerPart) 0 >> (integerPartWidth - bits);
   2867 
   2868   while (i < parts)
   2869     dst[i++] = 0;
   2870 }
   2871