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