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