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