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