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