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