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