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