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