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