Bug Summary

File:llvm/include/llvm/ADT/APInt.h
Warning:line 775, column 7
Attempt to free released memory

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name APInt.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/Support -resource-dir /usr/lib/llvm-14/lib/clang/14.0.0 -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/Support -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/Support -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/include -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/include -D NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-14/lib/clang/14.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/Support -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e=. -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2021-09-04-040900-46481-1 -x c++ /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/Support/APInt.cpp

/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/Support/APInt.cpp

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

/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/include/llvm/ADT/APInt.h

1//===-- llvm/ADT/APInt.h - For Arbitrary Precision Integer -----*- C++ -*--===//
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/// \file
10/// This file implements a class to represent arbitrary precision
11/// integral constant values and operations on them.
12///
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_ADT_APINT_H
16#define LLVM_ADT_APINT_H
17
18#include "llvm/Support/Compiler.h"
19#include "llvm/Support/MathExtras.h"
20#include <cassert>
21#include <climits>
22#include <cstring>
23#include <utility>
24
25namespace llvm {
26class FoldingSetNodeID;
27class StringRef;
28class hash_code;
29class raw_ostream;
30
31template <typename T> class SmallVectorImpl;
32template <typename T> class ArrayRef;
33template <typename T> class Optional;
34template <typename T> struct DenseMapInfo;
35
36class APInt;
37
38inline APInt operator-(APInt);
39
40//===----------------------------------------------------------------------===//
41// APInt Class
42//===----------------------------------------------------------------------===//
43
44/// Class for arbitrary precision integers.
45///
46/// APInt is a functional replacement for common case unsigned integer type like
47/// "unsigned", "unsigned long" or "uint64_t", but also allows non-byte-width
48/// integer sizes and large integer value types such as 3-bits, 15-bits, or more
49/// than 64-bits of precision. APInt provides a variety of arithmetic operators
50/// and methods to manipulate integer values of any bit-width. It supports both
51/// the typical integer arithmetic and comparison operations as well as bitwise
52/// manipulation.
53///
54/// The class has several invariants worth noting:
55/// * All bit, byte, and word positions are zero-based.
56/// * Once the bit width is set, it doesn't change except by the Truncate,
57/// SignExtend, or ZeroExtend operations.
58/// * All binary operators must be on APInt instances of the same bit width.
59/// Attempting to use these operators on instances with different bit
60/// widths will yield an assertion.
61/// * The value is stored canonically as an unsigned value. For operations
62/// where it makes a difference, there are both signed and unsigned variants
63/// of the operation. For example, sdiv and udiv. However, because the bit
64/// widths must be the same, operations such as Mul and Add produce the same
65/// results regardless of whether the values are interpreted as signed or
66/// not.
67/// * In general, the class tries to follow the style of computation that LLVM
68/// uses in its IR. This simplifies its use for LLVM.
69///
70class LLVM_NODISCARD[[clang::warn_unused_result]] APInt {
71public:
72 typedef uint64_t WordType;
73
74 /// This enum is used to hold the constants we needed for APInt.
75 enum : unsigned {
76 /// Byte size of a word.
77 APINT_WORD_SIZE = sizeof(WordType),
78 /// Bits in a word.
79 APINT_BITS_PER_WORD = APINT_WORD_SIZE * CHAR_BIT8
80 };
81
82 enum class Rounding {
83 DOWN,
84 TOWARD_ZERO,
85 UP,
86 };
87
88 static constexpr WordType WORDTYPE_MAX = ~WordType(0);
89
90private:
91 /// This union is used to store the integer value. When the
92 /// integer bit-width <= 64, it uses VAL, otherwise it uses pVal.
93 union {
94 uint64_t VAL; ///< Used to store the <= 64 bits integer value.
95 uint64_t *pVal; ///< Used to store the >64 bits integer value.
96 } U;
97
98 unsigned BitWidth; ///< The number of bits in this APInt.
99
100 friend struct DenseMapInfo<APInt>;
101
102 friend class APSInt;
103
104 /// Fast internal constructor
105 ///
106 /// This constructor is used only internally for speed of construction of
107 /// temporaries. It is unsafe for general use so it is not public.
108 APInt(uint64_t *val, unsigned bits) : BitWidth(bits) {
109 U.pVal = val;
110 }
111
112 /// Determine which word a bit is in.
113 ///
114 /// \returns the word position for the specified bit position.
115 static unsigned whichWord(unsigned bitPosition) {
116 return bitPosition / APINT_BITS_PER_WORD;
117 }
118
119 /// Determine which bit in a word a bit is in.
120 ///
121 /// \returns the bit position in a word for the specified bit position
122 /// in the APInt.
123 static unsigned whichBit(unsigned bitPosition) {
124 return bitPosition % APINT_BITS_PER_WORD;
125 }
126
127 /// Get a single bit mask.
128 ///
129 /// \returns a uint64_t with only bit at "whichBit(bitPosition)" set
130 /// This method generates and returns a uint64_t (word) mask for a single
131 /// bit at a specific bit position. This is used to mask the bit in the
132 /// corresponding word.
133 static uint64_t maskBit(unsigned bitPosition) {
134 return 1ULL << whichBit(bitPosition);
135 }
136
137 /// Clear unused high order bits
138 ///
139 /// This method is used internally to clear the top "N" bits in the high order
140 /// word that are not used by the APInt. This is needed after the most
141 /// significant word is assigned a value to ensure that those bits are
142 /// zero'd out.
143 APInt &clearUnusedBits() {
144 // Compute how many bits are used in the final word
145 unsigned WordBits = ((BitWidth-1) % APINT_BITS_PER_WORD) + 1;
146
147 // Mask out the high bits.
148 uint64_t mask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - WordBits);
149 if (isSingleWord())
150 U.VAL &= mask;
151 else
152 U.pVal[getNumWords() - 1] &= mask;
153 return *this;
154 }
155
156 /// Get the word corresponding to a bit position
157 /// \returns the corresponding word for the specified bit position.
158 uint64_t getWord(unsigned bitPosition) const {
159 return isSingleWord() ? U.VAL : U.pVal[whichWord(bitPosition)];
160 }
161
162 /// Utility method to change the bit width of this APInt to new bit width,
163 /// allocating and/or deallocating as necessary. There is no guarantee on the
164 /// value of any bits upon return. Caller should populate the bits after.
165 void reallocate(unsigned NewBitWidth);
166
167 /// Convert a char array into an APInt
168 ///
169 /// \param radix 2, 8, 10, 16, or 36
170 /// Converts a string into a number. The string must be non-empty
171 /// and well-formed as a number of the given base. The bit-width
172 /// must be sufficient to hold the result.
173 ///
174 /// This is used by the constructors that take string arguments.
175 ///
176 /// StringRef::getAsInteger is superficially similar but (1) does
177 /// not assume that the string is well-formed and (2) grows the
178 /// result to hold the input.
179 void fromString(unsigned numBits, StringRef str, uint8_t radix);
180
181 /// An internal division function for dividing APInts.
182 ///
183 /// This is used by the toString method to divide by the radix. It simply
184 /// provides a more convenient form of divide for internal use since KnuthDiv
185 /// has specific constraints on its inputs. If those constraints are not met
186 /// then it provides a simpler form of divide.
187 static void divide(const WordType *LHS, unsigned lhsWords,
188 const WordType *RHS, unsigned rhsWords, WordType *Quotient,
189 WordType *Remainder);
190
191 /// out-of-line slow case for inline constructor
192 void initSlowCase(uint64_t val, bool isSigned);
193
194 /// shared code between two array constructors
195 void initFromArray(ArrayRef<uint64_t> array);
196
197 /// out-of-line slow case for inline copy constructor
198 void initSlowCase(const APInt &that);
199
200 /// out-of-line slow case for shl
201 void shlSlowCase(unsigned ShiftAmt);
202
203 /// out-of-line slow case for lshr.
204 void lshrSlowCase(unsigned ShiftAmt);
205
206 /// out-of-line slow case for ashr.
207 void ashrSlowCase(unsigned ShiftAmt);
208
209 /// out-of-line slow case for operator=
210 void AssignSlowCase(const APInt &RHS);
211
212 /// out-of-line slow case for operator==
213 bool EqualSlowCase(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__));
214
215 /// out-of-line slow case for countLeadingZeros
216 unsigned countLeadingZerosSlowCase() const LLVM_READONLY__attribute__((__pure__));
217
218 /// out-of-line slow case for countLeadingOnes.
219 unsigned countLeadingOnesSlowCase() const LLVM_READONLY__attribute__((__pure__));
220
221 /// out-of-line slow case for countTrailingZeros.
222 unsigned countTrailingZerosSlowCase() const LLVM_READONLY__attribute__((__pure__));
223
224 /// out-of-line slow case for countTrailingOnes
225 unsigned countTrailingOnesSlowCase() const LLVM_READONLY__attribute__((__pure__));
226
227 /// out-of-line slow case for countPopulation
228 unsigned countPopulationSlowCase() const LLVM_READONLY__attribute__((__pure__));
229
230 /// out-of-line slow case for intersects.
231 bool intersectsSlowCase(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__));
232
233 /// out-of-line slow case for isSubsetOf.
234 bool isSubsetOfSlowCase(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__));
235
236 /// out-of-line slow case for setBits.
237 void setBitsSlowCase(unsigned loBit, unsigned hiBit);
238
239 /// out-of-line slow case for flipAllBits.
240 void flipAllBitsSlowCase();
241
242 /// out-of-line slow case for operator&=.
243 void AndAssignSlowCase(const APInt& RHS);
244
245 /// out-of-line slow case for operator|=.
246 void OrAssignSlowCase(const APInt& RHS);
247
248 /// out-of-line slow case for operator^=.
249 void XorAssignSlowCase(const APInt& RHS);
250
251 /// Unsigned comparison. Returns -1, 0, or 1 if this APInt is less than, equal
252 /// to, or greater than RHS.
253 int compare(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__));
254
255 /// Signed comparison. Returns -1, 0, or 1 if this APInt is less than, equal
256 /// to, or greater than RHS.
257 int compareSigned(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__));
258
259public:
260 /// \name Constructors
261 /// @{
262
263 /// Create a new APInt of numBits width, initialized as val.
264 ///
265 /// If isSigned is true then val is treated as if it were a signed value
266 /// (i.e. as an int64_t) and the appropriate sign extension to the bit width
267 /// will be done. Otherwise, no sign extension occurs (high order bits beyond
268 /// the range of val are zero filled).
269 ///
270 /// \param numBits the bit width of the constructed APInt
271 /// \param val the initial value of the APInt
272 /// \param isSigned how to treat signedness of val
273 APInt(unsigned numBits, uint64_t val, bool isSigned = false)
274 : BitWidth(numBits) {
275 assert(BitWidth && "bitwidth too small")(static_cast<void> (0));
276 if (isSingleWord()) {
277 U.VAL = val;
278 clearUnusedBits();
279 } else {
280 initSlowCase(val, isSigned);
281 }
282 }
283
284 /// Construct an APInt of numBits width, initialized as bigVal[].
285 ///
286 /// Note that bigVal.size() can be smaller or larger than the corresponding
287 /// bit width but any extraneous bits will be dropped.
288 ///
289 /// \param numBits the bit width of the constructed APInt
290 /// \param bigVal a sequence of words to form the initial value of the APInt
291 APInt(unsigned numBits, ArrayRef<uint64_t> bigVal);
292
293 /// Equivalent to APInt(numBits, ArrayRef<uint64_t>(bigVal, numWords)), but
294 /// deprecated because this constructor is prone to ambiguity with the
295 /// APInt(unsigned, uint64_t, bool) constructor.
296 ///
297 /// If this overload is ever deleted, care should be taken to prevent calls
298 /// from being incorrectly captured by the APInt(unsigned, uint64_t, bool)
299 /// constructor.
300 APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[]);
301
302 /// Construct an APInt from a string representation.
303 ///
304 /// This constructor interprets the string \p str in the given radix. The
305 /// interpretation stops when the first character that is not suitable for the
306 /// radix is encountered, or the end of the string. Acceptable radix values
307 /// are 2, 8, 10, 16, and 36. It is an error for the value implied by the
308 /// string to require more bits than numBits.
309 ///
310 /// \param numBits the bit width of the constructed APInt
311 /// \param str the string to be interpreted
312 /// \param radix the radix to use for the conversion
313 APInt(unsigned numBits, StringRef str, uint8_t radix);
314
315 /// Simply makes *this a copy of that.
316 /// Copy Constructor.
317 APInt(const APInt &that) : BitWidth(that.BitWidth) {
318 if (isSingleWord())
3
Taking false branch
319 U.VAL = that.U.VAL;
320 else
321 initSlowCase(that);
4
Calling 'APInt::initSlowCase'
8
Returned allocated memory
322 }
323
324 /// Move Constructor.
325 APInt(APInt &&that) : BitWidth(that.BitWidth) {
326 memcpy(&U, &that.U, sizeof(U));
327 that.BitWidth = 0;
328 }
329
330 /// Destructor.
331 ~APInt() {
332 if (needsCleanup())
333 delete[] U.pVal;
334 }
335
336 /// Default constructor that creates an uninteresting APInt
337 /// representing a 1-bit zero value.
338 ///
339 /// This is useful for object deserialization (pair this with the static
340 /// method Read).
341 explicit APInt() : BitWidth(1) { U.VAL = 0; }
342
343 /// Returns whether this instance allocated memory.
344 bool needsCleanup() const { return !isSingleWord(); }
345
346 /// Used to insert APInt objects, or objects that contain APInt objects, into
347 /// FoldingSets.
348 void Profile(FoldingSetNodeID &id) const;
349
350 /// @}
351 /// \name Value Tests
352 /// @{
353
354 /// Determine if this APInt just has one word to store value.
355 ///
356 /// \returns true if the number of bits <= 64, false otherwise.
357 bool isSingleWord() const { return BitWidth <= APINT_BITS_PER_WORD; }
358
359 /// Determine sign of this APInt.
360 ///
361 /// This tests the high bit of this APInt to determine if it is set.
362 ///
363 /// \returns true if this APInt is negative, false otherwise
364 bool isNegative() const { return (*this)[BitWidth - 1]; }
365
366 /// Determine if this APInt Value is non-negative (>= 0)
367 ///
368 /// This tests the high bit of the APInt to determine if it is unset.
369 bool isNonNegative() const { return !isNegative(); }
370
371 /// Determine if sign bit of this APInt is set.
372 ///
373 /// This tests the high bit of this APInt to determine if it is set.
374 ///
375 /// \returns true if this APInt has its sign bit set, false otherwise.
376 bool isSignBitSet() const { return (*this)[BitWidth-1]; }
377
378 /// Determine if sign bit of this APInt is clear.
379 ///
380 /// This tests the high bit of this APInt to determine if it is clear.
381 ///
382 /// \returns true if this APInt has its sign bit clear, false otherwise.
383 bool isSignBitClear() const { return !isSignBitSet(); }
384
385 /// Determine if this APInt Value is positive.
386 ///
387 /// This tests if the value of this APInt is positive (> 0). Note
388 /// that 0 is not a positive value.
389 ///
390 /// \returns true if this APInt is positive.
391 bool isStrictlyPositive() const { return isNonNegative() && !isNullValue(); }
392
393 /// Determine if this APInt Value is non-positive (<= 0).
394 ///
395 /// \returns true if this APInt is non-positive.
396 bool isNonPositive() const { return !isStrictlyPositive(); }
397
398 /// Determine if all bits are set
399 ///
400 /// This checks to see if the value has all bits of the APInt are set or not.
401 bool isAllOnesValue() const {
402 if (isSingleWord())
403 return U.VAL == WORDTYPE_MAX >> (APINT_BITS_PER_WORD - BitWidth);
404 return countTrailingOnesSlowCase() == BitWidth;
405 }
406
407 /// Determine if all bits are clear
408 ///
409 /// This checks to see if the value has all bits of the APInt are clear or
410 /// not.
411 bool isNullValue() const { return !*this; }
412
413 /// Determine if this is a value of 1.
414 ///
415 /// This checks to see if the value of this APInt is one.
416 bool isOneValue() const {
417 if (isSingleWord())
418 return U.VAL == 1;
419 return countLeadingZerosSlowCase() == BitWidth - 1;
420 }
421
422 /// Determine if this is the largest unsigned value.
423 ///
424 /// This checks to see if the value of this APInt is the maximum unsigned
425 /// value for the APInt's bit width.
426 bool isMaxValue() const { return isAllOnesValue(); }
427
428 /// Determine if this is the largest signed value.
429 ///
430 /// This checks to see if the value of this APInt is the maximum signed
431 /// value for the APInt's bit width.
432 bool isMaxSignedValue() const {
433 if (isSingleWord())
434 return U.VAL == ((WordType(1) << (BitWidth - 1)) - 1);
435 return !isNegative() && countTrailingOnesSlowCase() == BitWidth - 1;
436 }
437
438 /// Determine if this is the smallest unsigned value.
439 ///
440 /// This checks to see if the value of this APInt is the minimum unsigned
441 /// value for the APInt's bit width.
442 bool isMinValue() const { return isNullValue(); }
443
444 /// Determine if this is the smallest signed value.
445 ///
446 /// This checks to see if the value of this APInt is the minimum signed
447 /// value for the APInt's bit width.
448 bool isMinSignedValue() const {
449 if (isSingleWord())
450 return U.VAL == (WordType(1) << (BitWidth - 1));
451 return isNegative() && countTrailingZerosSlowCase() == BitWidth - 1;
452 }
453
454 /// Check if this APInt has an N-bits unsigned integer value.
455 bool isIntN(unsigned N) const {
456 assert(N && "N == 0 ???")(static_cast<void> (0));
457 return getActiveBits() <= N;
458 }
459
460 /// Check if this APInt has an N-bits signed integer value.
461 bool isSignedIntN(unsigned N) const {
462 assert(N && "N == 0 ???")(static_cast<void> (0));
463 return getMinSignedBits() <= N;
464 }
465
466 /// Check if this APInt's value is a power of two greater than zero.
467 ///
468 /// \returns true if the argument APInt value is a power of two > 0.
469 bool isPowerOf2() const {
470 if (isSingleWord())
471 return isPowerOf2_64(U.VAL);
472 return countPopulationSlowCase() == 1;
473 }
474
475 /// Check if the APInt's value is returned by getSignMask.
476 ///
477 /// \returns true if this is the value returned by getSignMask.
478 bool isSignMask() const { return isMinSignedValue(); }
479
480 /// Convert APInt to a boolean value.
481 ///
482 /// This converts the APInt to a boolean value as a test against zero.
483 bool getBoolValue() const { return !!*this; }
484
485 /// If this value is smaller than the specified limit, return it, otherwise
486 /// return the limit value. This causes the value to saturate to the limit.
487 uint64_t getLimitedValue(uint64_t Limit = UINT64_MAX(18446744073709551615UL)) const {
488 return ugt(Limit) ? Limit : getZExtValue();
489 }
490
491 /// Check if the APInt consists of a repeated bit pattern.
492 ///
493 /// e.g. 0x01010101 satisfies isSplat(8).
494 /// \param SplatSizeInBits The size of the pattern in bits. Must divide bit
495 /// width without remainder.
496 bool isSplat(unsigned SplatSizeInBits) const;
497
498 /// \returns true if this APInt value is a sequence of \param numBits ones
499 /// starting at the least significant bit with the remainder zero.
500 bool isMask(unsigned numBits) const {
501 assert(numBits != 0 && "numBits must be non-zero")(static_cast<void> (0));
502 assert(numBits <= BitWidth && "numBits out of range")(static_cast<void> (0));
503 if (isSingleWord())
504 return U.VAL == (WORDTYPE_MAX >> (APINT_BITS_PER_WORD - numBits));
505 unsigned Ones = countTrailingOnesSlowCase();
506 return (numBits == Ones) &&
507 ((Ones + countLeadingZerosSlowCase()) == BitWidth);
508 }
509
510 /// \returns true if this APInt is a non-empty sequence of ones starting at
511 /// the least significant bit with the remainder zero.
512 /// Ex. isMask(0x0000FFFFU) == true.
513 bool isMask() const {
514 if (isSingleWord())
515 return isMask_64(U.VAL);
516 unsigned Ones = countTrailingOnesSlowCase();
517 return (Ones > 0) && ((Ones + countLeadingZerosSlowCase()) == BitWidth);
518 }
519
520 /// Return true if this APInt value contains a sequence of ones with
521 /// the remainder zero.
522 bool isShiftedMask() const {
523 if (isSingleWord())
524 return isShiftedMask_64(U.VAL);
525 unsigned Ones = countPopulationSlowCase();
526 unsigned LeadZ = countLeadingZerosSlowCase();
527 return (Ones + LeadZ + countTrailingZeros()) == BitWidth;
528 }
529
530 /// @}
531 /// \name Value Generators
532 /// @{
533
534 /// Gets maximum unsigned value of APInt for specific bit width.
535 static APInt getMaxValue(unsigned numBits) {
536 return getAllOnesValue(numBits);
537 }
538
539 /// Gets maximum signed value of APInt for a specific bit width.
540 static APInt getSignedMaxValue(unsigned numBits) {
541 APInt API = getAllOnesValue(numBits);
542 API.clearBit(numBits - 1);
543 return API;
544 }
545
546 /// Gets minimum unsigned value of APInt for a specific bit width.
547 static APInt getMinValue(unsigned numBits) { return APInt(numBits, 0); }
548
549 /// Gets minimum signed value of APInt for a specific bit width.
550 static APInt getSignedMinValue(unsigned numBits) {
551 APInt API(numBits, 0);
552 API.setBit(numBits - 1);
553 return API;
554 }
555
556 /// Get the SignMask for a specific bit width.
557 ///
558 /// This is just a wrapper function of getSignedMinValue(), and it helps code
559 /// readability when we want to get a SignMask.
560 static APInt getSignMask(unsigned BitWidth) {
561 return getSignedMinValue(BitWidth);
562 }
563
564 /// Get the all-ones value.
565 ///
566 /// \returns the all-ones value for an APInt of the specified bit-width.
567 static APInt getAllOnesValue(unsigned numBits) {
568 return APInt(numBits, WORDTYPE_MAX, true);
569 }
570
571 /// Get the '0' value.
572 ///
573 /// \returns the '0' value for an APInt of the specified bit-width.
574 static APInt getNullValue(unsigned numBits) { return APInt(numBits, 0); }
575
576 /// Compute an APInt containing numBits highbits from this APInt.
577 ///
578 /// Get an APInt with the same BitWidth as this APInt, just zero mask
579 /// the low bits and right shift to the least significant bit.
580 ///
581 /// \returns the high "numBits" bits of this APInt.
582 APInt getHiBits(unsigned numBits) const;
583
584 /// Compute an APInt containing numBits lowbits from this APInt.
585 ///
586 /// Get an APInt with the same BitWidth as this APInt, just zero mask
587 /// the high bits.
588 ///
589 /// \returns the low "numBits" bits of this APInt.
590 APInt getLoBits(unsigned numBits) const;
591
592 /// Return an APInt with exactly one bit set in the result.
593 static APInt getOneBitSet(unsigned numBits, unsigned BitNo) {
594 APInt Res(numBits, 0);
595 Res.setBit(BitNo);
596 return Res;
597 }
598
599 /// Get a value with a block of bits set.
600 ///
601 /// Constructs an APInt value that has a contiguous range of bits set. The
602 /// bits from loBit (inclusive) to hiBit (exclusive) will be set. All other
603 /// bits will be zero. For example, with parameters(32, 0, 16) you would get
604 /// 0x0000FFFF. Please call getBitsSetWithWrap if \p loBit may be greater than
605 /// \p hiBit.
606 ///
607 /// \param numBits the intended bit width of the result
608 /// \param loBit the index of the lowest bit set.
609 /// \param hiBit the index of the highest bit set.
610 ///
611 /// \returns An APInt value with the requested bits set.
612 static APInt getBitsSet(unsigned numBits, unsigned loBit, unsigned hiBit) {
613 assert(loBit <= hiBit && "loBit greater than hiBit")(static_cast<void> (0));
614 APInt Res(numBits, 0);
615 Res.setBits(loBit, hiBit);
616 return Res;
617 }
618
619 /// Wrap version of getBitsSet.
620 /// If \p hiBit is bigger than \p loBit, this is same with getBitsSet.
621 /// If \p hiBit is not bigger than \p loBit, the set bits "wrap". For example,
622 /// with parameters (32, 28, 4), you would get 0xF000000F.
623 /// If \p hiBit is equal to \p loBit, you would get a result with all bits
624 /// set.
625 static APInt getBitsSetWithWrap(unsigned numBits, unsigned loBit,
626 unsigned hiBit) {
627 APInt Res(numBits, 0);
628 Res.setBitsWithWrap(loBit, hiBit);
629 return Res;
630 }
631
632 /// Get a value with upper bits starting at loBit set.
633 ///
634 /// Constructs an APInt value that has a contiguous range of bits set. The
635 /// bits from loBit (inclusive) to numBits (exclusive) will be set. All other
636 /// bits will be zero. For example, with parameters(32, 12) you would get
637 /// 0xFFFFF000.
638 ///
639 /// \param numBits the intended bit width of the result
640 /// \param loBit the index of the lowest bit to set.
641 ///
642 /// \returns An APInt value with the requested bits set.
643 static APInt getBitsSetFrom(unsigned numBits, unsigned loBit) {
644 APInt Res(numBits, 0);
645 Res.setBitsFrom(loBit);
646 return Res;
647 }
648
649 /// Get a value with high bits set
650 ///
651 /// Constructs an APInt value that has the top hiBitsSet bits set.
652 ///
653 /// \param numBits the bitwidth of the result
654 /// \param hiBitsSet the number of high-order bits set in the result.
655 static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet) {
656 APInt Res(numBits, 0);
657 Res.setHighBits(hiBitsSet);
658 return Res;
659 }
660
661 /// Get a value with low bits set
662 ///
663 /// Constructs an APInt value that has the bottom loBitsSet bits set.
664 ///
665 /// \param numBits the bitwidth of the result
666 /// \param loBitsSet the number of low-order bits set in the result.
667 static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet) {
668 APInt Res(numBits, 0);
669 Res.setLowBits(loBitsSet);
670 return Res;
671 }
672
673 /// Return a value containing V broadcasted over NewLen bits.
674 static APInt getSplat(unsigned NewLen, const APInt &V);
675
676 /// Determine if two APInts have the same value, after zero-extending
677 /// one of them (if needed!) to ensure that the bit-widths match.
678 static bool isSameValue(const APInt &I1, const APInt &I2) {
679 if (I1.getBitWidth() == I2.getBitWidth())
680 return I1 == I2;
681
682 if (I1.getBitWidth() > I2.getBitWidth())
683 return I1 == I2.zext(I1.getBitWidth());
684
685 return I1.zext(I2.getBitWidth()) == I2;
686 }
687
688 /// Overload to compute a hash_code for an APInt value.
689 friend hash_code hash_value(const APInt &Arg);
690
691 /// This function returns a pointer to the internal storage of the APInt.
692 /// This is useful for writing out the APInt in binary form without any
693 /// conversions.
694 const uint64_t *getRawData() const {
695 if (isSingleWord())
696 return &U.VAL;
697 return &U.pVal[0];
698 }
699
700 /// @}
701 /// \name Unary Operators
702 /// @{
703
704 /// Postfix increment operator.
705 ///
706 /// Increments *this by 1.
707 ///
708 /// \returns a new APInt value representing the original value of *this.
709 APInt operator++(int) {
710 APInt API(*this);
711 ++(*this);
712 return API;
713 }
714
715 /// Prefix increment operator.
716 ///
717 /// \returns *this incremented by one
718 APInt &operator++();
719
720 /// Postfix decrement operator.
721 ///
722 /// Decrements *this by 1.
723 ///
724 /// \returns a new APInt value representing the original value of *this.
725 APInt operator--(int) {
726 APInt API(*this);
727 --(*this);
728 return API;
729 }
730
731 /// Prefix decrement operator.
732 ///
733 /// \returns *this decremented by one.
734 APInt &operator--();
735
736 /// Logical negation operator.
737 ///
738 /// Performs logical negation operation on this APInt.
739 ///
740 /// \returns true if *this is zero, false otherwise.
741 bool operator!() const {
742 if (isSingleWord())
743 return U.VAL == 0;
744 return countLeadingZerosSlowCase() == BitWidth;
745 }
746
747 /// @}
748 /// \name Assignment Operators
749 /// @{
750
751 /// Copy assignment operator.
752 ///
753 /// \returns *this after assignment of RHS.
754 APInt &operator=(const APInt &RHS) {
755 // If the bitwidths are the same, we can avoid mucking with memory
756 if (isSingleWord() && RHS.isSingleWord()) {
757 U.VAL = RHS.U.VAL;
758 BitWidth = RHS.BitWidth;
759 return clearUnusedBits();
760 }
761
762 AssignSlowCase(RHS);
763 return *this;
764 }
765
766 /// Move assignment operator.
767 APInt &operator=(APInt &&that) {
768#ifdef EXPENSIVE_CHECKS
769 // Some std::shuffle implementations still do self-assignment.
770 if (this == &that)
771 return *this;
772#endif
773 assert(this != &that && "Self-move not supported")(static_cast<void> (0));
774 if (!isSingleWord())
13
Taking true branch
17
Taking true branch
775 delete[] U.pVal;
14
Memory is released
18
Attempt to free released memory
776
777 // Use memcpy so that type based alias analysis sees both VAL and pVal
778 // as modified.
779 memcpy(&U, &that.U, sizeof(U));
780
781 BitWidth = that.BitWidth;
782 that.BitWidth = 0;
783
784 return *this;
785 }
786
787 /// Assignment operator.
788 ///
789 /// The RHS value is assigned to *this. If the significant bits in RHS exceed
790 /// the bit width, the excess bits are truncated. If the bit width is larger
791 /// than 64, the value is zero filled in the unspecified high order bits.
792 ///
793 /// \returns *this after assignment of RHS value.
794 APInt &operator=(uint64_t RHS) {
795 if (isSingleWord()) {
796 U.VAL = RHS;
797 return clearUnusedBits();
798 }
799 U.pVal[0] = RHS;
800 memset(U.pVal + 1, 0, (getNumWords() - 1) * APINT_WORD_SIZE);
801 return *this;
802 }
803
804 /// Bitwise AND assignment operator.
805 ///
806 /// Performs a bitwise AND operation on this APInt and RHS. The result is
807 /// assigned to *this.
808 ///
809 /// \returns *this after ANDing with RHS.
810 APInt &operator&=(const APInt &RHS) {
811 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")(static_cast<void> (0));
812 if (isSingleWord())
813 U.VAL &= RHS.U.VAL;
814 else
815 AndAssignSlowCase(RHS);
816 return *this;
817 }
818
819 /// Bitwise AND assignment operator.
820 ///
821 /// Performs a bitwise AND operation on this APInt and RHS. RHS is
822 /// logically zero-extended or truncated to match the bit-width of
823 /// the LHS.
824 APInt &operator&=(uint64_t RHS) {
825 if (isSingleWord()) {
826 U.VAL &= RHS;
827 return *this;
828 }
829 U.pVal[0] &= RHS;
830 memset(U.pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE);
831 return *this;
832 }
833
834 /// Bitwise OR assignment operator.
835 ///
836 /// Performs a bitwise OR operation on this APInt and RHS. The result is
837 /// assigned *this;
838 ///
839 /// \returns *this after ORing with RHS.
840 APInt &operator|=(const APInt &RHS) {
841 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")(static_cast<void> (0));
842 if (isSingleWord())
843 U.VAL |= RHS.U.VAL;
844 else
845 OrAssignSlowCase(RHS);
846 return *this;
847 }
848
849 /// Bitwise OR assignment operator.
850 ///
851 /// Performs a bitwise OR operation on this APInt and RHS. RHS is
852 /// logically zero-extended or truncated to match the bit-width of
853 /// the LHS.
854 APInt &operator|=(uint64_t RHS) {
855 if (isSingleWord()) {
856 U.VAL |= RHS;
857 return clearUnusedBits();
858 }
859 U.pVal[0] |= RHS;
860 return *this;
861 }
862
863 /// Bitwise XOR assignment operator.
864 ///
865 /// Performs a bitwise XOR operation on this APInt and RHS. The result is
866 /// assigned to *this.
867 ///
868 /// \returns *this after XORing with RHS.
869 APInt &operator^=(const APInt &RHS) {
870 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")(static_cast<void> (0));
871 if (isSingleWord())
872 U.VAL ^= RHS.U.VAL;
873 else
874 XorAssignSlowCase(RHS);
875 return *this;
876 }
877
878 /// Bitwise XOR assignment operator.
879 ///
880 /// Performs a bitwise XOR operation on this APInt and RHS. RHS is
881 /// logically zero-extended or truncated to match the bit-width of
882 /// the LHS.
883 APInt &operator^=(uint64_t RHS) {
884 if (isSingleWord()) {
885 U.VAL ^= RHS;
886 return clearUnusedBits();
887 }
888 U.pVal[0] ^= RHS;
889 return *this;
890 }
891
892 /// Multiplication assignment operator.
893 ///
894 /// Multiplies this APInt by RHS and assigns the result to *this.
895 ///
896 /// \returns *this
897 APInt &operator*=(const APInt &RHS);
898 APInt &operator*=(uint64_t RHS);
899
900 /// Addition assignment operator.
901 ///
902 /// Adds RHS to *this and assigns the result to *this.
903 ///
904 /// \returns *this
905 APInt &operator+=(const APInt &RHS);
906 APInt &operator+=(uint64_t RHS);
907
908 /// Subtraction assignment operator.
909 ///
910 /// Subtracts RHS from *this and assigns the result to *this.
911 ///
912 /// \returns *this
913 APInt &operator-=(const APInt &RHS);
914 APInt &operator-=(uint64_t RHS);
915
916 /// Left-shift assignment function.
917 ///
918 /// Shifts *this left by shiftAmt and assigns the result to *this.
919 ///
920 /// \returns *this after shifting left by ShiftAmt
921 APInt &operator<<=(unsigned ShiftAmt) {
922 assert(ShiftAmt <= BitWidth && "Invalid shift amount")(static_cast<void> (0));
923 if (isSingleWord()) {
924 if (ShiftAmt == BitWidth)
925 U.VAL = 0;
926 else
927 U.VAL <<= ShiftAmt;
928 return clearUnusedBits();
929 }
930 shlSlowCase(ShiftAmt);
931 return *this;
932 }
933
934 /// Left-shift assignment function.
935 ///
936 /// Shifts *this left by shiftAmt and assigns the result to *this.
937 ///
938 /// \returns *this after shifting left by ShiftAmt
939 APInt &operator<<=(const APInt &ShiftAmt);
940
941 /// @}
942 /// \name Binary Operators
943 /// @{
944
945 /// Multiplication operator.
946 ///
947 /// Multiplies this APInt by RHS and returns the result.
948 APInt operator*(const APInt &RHS) const;
949
950 /// Left logical shift operator.
951 ///
952 /// Shifts this APInt left by \p Bits and returns the result.
953 APInt operator<<(unsigned Bits) const { return shl(Bits); }
954
955 /// Left logical shift operator.
956 ///
957 /// Shifts this APInt left by \p Bits and returns the result.
958 APInt operator<<(const APInt &Bits) const { return shl(Bits); }
959
960 /// Arithmetic right-shift function.
961 ///
962 /// Arithmetic right-shift this APInt by shiftAmt.
963 APInt ashr(unsigned ShiftAmt) const {
964 APInt R(*this);
965 R.ashrInPlace(ShiftAmt);
966 return R;
967 }
968
969 /// Arithmetic right-shift this APInt by ShiftAmt in place.
970 void ashrInPlace(unsigned ShiftAmt) {
971 assert(ShiftAmt <= BitWidth && "Invalid shift amount")(static_cast<void> (0));
972 if (isSingleWord()) {
973 int64_t SExtVAL = SignExtend64(U.VAL, BitWidth);
974 if (ShiftAmt == BitWidth)
975 U.VAL = SExtVAL >> (APINT_BITS_PER_WORD - 1); // Fill with sign bit.
976 else
977 U.VAL = SExtVAL >> ShiftAmt;
978 clearUnusedBits();
979 return;
980 }
981 ashrSlowCase(ShiftAmt);
982 }
983
984 /// Logical right-shift function.
985 ///
986 /// Logical right-shift this APInt by shiftAmt.
987 APInt lshr(unsigned shiftAmt) const {
988 APInt R(*this);
989 R.lshrInPlace(shiftAmt);
990 return R;
991 }
992
993 /// Logical right-shift this APInt by ShiftAmt in place.
994 void lshrInPlace(unsigned ShiftAmt) {
995 assert(ShiftAmt <= BitWidth && "Invalid shift amount")(static_cast<void> (0));
996 if (isSingleWord()) {
997 if (ShiftAmt == BitWidth)
998 U.VAL = 0;
999 else
1000 U.VAL >>= ShiftAmt;
1001 return;
1002 }
1003 lshrSlowCase(ShiftAmt);
1004 }
1005
1006 /// Left-shift function.
1007 ///
1008 /// Left-shift this APInt by shiftAmt.
1009 APInt shl(unsigned shiftAmt) const {
1010 APInt R(*this);
1011 R <<= shiftAmt;
1012 return R;
1013 }
1014
1015 /// Rotate left by rotateAmt.
1016 APInt rotl(unsigned rotateAmt) const;
1017
1018 /// Rotate right by rotateAmt.
1019 APInt rotr(unsigned rotateAmt) const;
1020
1021 /// Arithmetic right-shift function.
1022 ///
1023 /// Arithmetic right-shift this APInt by shiftAmt.
1024 APInt ashr(const APInt &ShiftAmt) const {
1025 APInt R(*this);
1026 R.ashrInPlace(ShiftAmt);
1027 return R;
1028 }
1029
1030 /// Arithmetic right-shift this APInt by shiftAmt in place.
1031 void ashrInPlace(const APInt &shiftAmt);
1032
1033 /// Logical right-shift function.
1034 ///
1035 /// Logical right-shift this APInt by shiftAmt.
1036 APInt lshr(const APInt &ShiftAmt) const {
1037 APInt R(*this);
1038 R.lshrInPlace(ShiftAmt);
1039 return R;
1040 }
1041
1042 /// Logical right-shift this APInt by ShiftAmt in place.
1043 void lshrInPlace(const APInt &ShiftAmt);
1044
1045 /// Left-shift function.
1046 ///
1047 /// Left-shift this APInt by shiftAmt.
1048 APInt shl(const APInt &ShiftAmt) const {
1049 APInt R(*this);
1050 R <<= ShiftAmt;
1051 return R;
1052 }
1053
1054 /// Rotate left by rotateAmt.
1055 APInt rotl(const APInt &rotateAmt) const;
1056
1057 /// Rotate right by rotateAmt.
1058 APInt rotr(const APInt &rotateAmt) const;
1059
1060 /// Unsigned division operation.
1061 ///
1062 /// Perform an unsigned divide operation on this APInt by RHS. Both this and
1063 /// RHS are treated as unsigned quantities for purposes of this division.
1064 ///
1065 /// \returns a new APInt value containing the division result, rounded towards
1066 /// zero.
1067 APInt udiv(const APInt &RHS) const;
1068 APInt udiv(uint64_t RHS) const;
1069
1070 /// Signed division function for APInt.
1071 ///
1072 /// Signed divide this APInt by APInt RHS.
1073 ///
1074 /// The result is rounded towards zero.
1075 APInt sdiv(const APInt &RHS) const;
1076 APInt sdiv(int64_t RHS) const;
1077
1078 /// Unsigned remainder operation.
1079 ///
1080 /// Perform an unsigned remainder operation on this APInt with RHS being the
1081 /// divisor. Both this and RHS are treated as unsigned quantities for purposes
1082 /// of this operation. Note that this is a true remainder operation and not a
1083 /// modulo operation because the sign follows the sign of the dividend which
1084 /// is *this.
1085 ///
1086 /// \returns a new APInt value containing the remainder result
1087 APInt urem(const APInt &RHS) const;
1088 uint64_t urem(uint64_t RHS) const;
1089
1090 /// Function for signed remainder operation.
1091 ///
1092 /// Signed remainder operation on APInt.
1093 APInt srem(const APInt &RHS) const;
1094 int64_t srem(int64_t RHS) const;
1095
1096 /// Dual division/remainder interface.
1097 ///
1098 /// Sometimes it is convenient to divide two APInt values and obtain both the
1099 /// quotient and remainder. This function does both operations in the same
1100 /// computation making it a little more efficient. The pair of input arguments
1101 /// may overlap with the pair of output arguments. It is safe to call
1102 /// udivrem(X, Y, X, Y), for example.
1103 static void udivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient,
1104 APInt &Remainder);
1105 static void udivrem(const APInt &LHS, uint64_t RHS, APInt &Quotient,
1106 uint64_t &Remainder);
1107
1108 static void sdivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient,
1109 APInt &Remainder);
1110 static void sdivrem(const APInt &LHS, int64_t RHS, APInt &Quotient,
1111 int64_t &Remainder);
1112
1113 // Operations that return overflow indicators.
1114 APInt sadd_ov(const APInt &RHS, bool &Overflow) const;
1115 APInt uadd_ov(const APInt &RHS, bool &Overflow) const;
1116 APInt ssub_ov(const APInt &RHS, bool &Overflow) const;
1117 APInt usub_ov(const APInt &RHS, bool &Overflow) const;
1118 APInt sdiv_ov(const APInt &RHS, bool &Overflow) const;
1119 APInt smul_ov(const APInt &RHS, bool &Overflow) const;
1120 APInt umul_ov(const APInt &RHS, bool &Overflow) const;
1121 APInt sshl_ov(const APInt &Amt, bool &Overflow) const;
1122 APInt ushl_ov(const APInt &Amt, bool &Overflow) const;
1123
1124 // Operations that saturate
1125 APInt sadd_sat(const APInt &RHS) const;
1126 APInt uadd_sat(const APInt &RHS) const;
1127 APInt ssub_sat(const APInt &RHS) const;
1128 APInt usub_sat(const APInt &RHS) const;
1129 APInt smul_sat(const APInt &RHS) const;
1130 APInt umul_sat(const APInt &RHS) const;
1131 APInt sshl_sat(const APInt &RHS) const;
1132 APInt ushl_sat(const APInt &RHS) const;
1133
1134 /// Array-indexing support.
1135 ///
1136 /// \returns the bit value at bitPosition
1137 bool operator[](unsigned bitPosition) const {
1138 assert(bitPosition < getBitWidth() && "Bit position out of bounds!")(static_cast<void> (0));
1139 return (maskBit(bitPosition) & getWord(bitPosition)) != 0;
1140 }
1141
1142 /// @}
1143 /// \name Comparison Operators
1144 /// @{
1145
1146 /// Equality operator.
1147 ///
1148 /// Compares this APInt with RHS for the validity of the equality
1149 /// relationship.
1150 bool operator==(const APInt &RHS) const {
1151 assert(BitWidth == RHS.BitWidth && "Comparison requires equal bit widths")(static_cast<void> (0));
1152 if (isSingleWord())
1153 return U.VAL == RHS.U.VAL;
1154 return EqualSlowCase(RHS);
1155 }
1156
1157 /// Equality operator.
1158 ///
1159 /// Compares this APInt with a uint64_t for the validity of the equality
1160 /// relationship.
1161 ///
1162 /// \returns true if *this == Val
1163 bool operator==(uint64_t Val) const {
1164 return (isSingleWord() || getActiveBits() <= 64) && getZExtValue() == Val;
1165 }
1166
1167 /// Equality comparison.
1168 ///
1169 /// Compares this APInt with RHS for the validity of the equality
1170 /// relationship.
1171 ///
1172 /// \returns true if *this == Val
1173 bool eq(const APInt &RHS) const { return (*this) == RHS; }
1174
1175 /// Inequality operator.
1176 ///
1177 /// Compares this APInt with RHS for the validity of the inequality
1178 /// relationship.
1179 ///
1180 /// \returns true if *this != Val
1181 bool operator!=(const APInt &RHS) const { return !((*this) == RHS); }
1182
1183 /// Inequality operator.
1184 ///
1185 /// Compares this APInt with a uint64_t for the validity of the inequality
1186 /// relationship.
1187 ///
1188 /// \returns true if *this != Val
1189 bool operator!=(uint64_t Val) const { return !((*this) == Val); }
1190
1191 /// Inequality comparison
1192 ///
1193 /// Compares this APInt with RHS for the validity of the inequality
1194 /// relationship.
1195 ///
1196 /// \returns true if *this != Val
1197 bool ne(const APInt &RHS) const { return !((*this) == RHS); }
1198
1199 /// Unsigned less than comparison
1200 ///
1201 /// Regards both *this and RHS as unsigned quantities and compares them for
1202 /// the validity of the less-than relationship.
1203 ///
1204 /// \returns true if *this < RHS when both are considered unsigned.
1205 bool ult(const APInt &RHS) const { return compare(RHS) < 0; }
1206
1207 /// Unsigned less than comparison
1208 ///
1209 /// Regards both *this as an unsigned quantity and compares it with RHS for
1210 /// the validity of the less-than relationship.
1211 ///
1212 /// \returns true if *this < RHS when considered unsigned.
1213 bool ult(uint64_t RHS) const {
1214 // Only need to check active bits if not a single word.
1215 return (isSingleWord() || getActiveBits() <= 64) && getZExtValue() < RHS;
1216 }
1217
1218 /// Signed less than comparison
1219 ///
1220 /// Regards both *this and RHS as signed quantities and compares them for
1221 /// validity of the less-than relationship.
1222 ///
1223 /// \returns true if *this < RHS when both are considered signed.
1224 bool slt(const APInt &RHS) const { return compareSigned(RHS) < 0; }
1225
1226 /// Signed less than comparison
1227 ///
1228 /// Regards both *this as a signed quantity and compares it with RHS for
1229 /// the validity of the less-than relationship.
1230 ///
1231 /// \returns true if *this < RHS when considered signed.
1232 bool slt(int64_t RHS) const {
1233 return (!isSingleWord() && getMinSignedBits() > 64) ? isNegative()
1234 : getSExtValue() < RHS;
1235 }
1236
1237 /// Unsigned less or equal comparison
1238 ///
1239 /// Regards both *this and RHS as unsigned quantities and compares them for
1240 /// validity of the less-or-equal relationship.
1241 ///
1242 /// \returns true if *this <= RHS when both are considered unsigned.
1243 bool ule(const APInt &RHS) const { return compare(RHS) <= 0; }
1244
1245 /// Unsigned less or equal comparison
1246 ///
1247 /// Regards both *this as an unsigned quantity and compares it with RHS for
1248 /// the validity of the less-or-equal relationship.
1249 ///
1250 /// \returns true if *this <= RHS when considered unsigned.
1251 bool ule(uint64_t RHS) const { return !ugt(RHS); }
1252
1253 /// Signed less or equal comparison
1254 ///
1255 /// Regards both *this and RHS as signed quantities and compares them for
1256 /// validity of the less-or-equal relationship.
1257 ///
1258 /// \returns true if *this <= RHS when both are considered signed.
1259 bool sle(const APInt &RHS) const { return compareSigned(RHS) <= 0; }
1260
1261 /// Signed less or equal comparison
1262 ///
1263 /// Regards both *this as a signed quantity and compares it with RHS for the
1264 /// validity of the less-or-equal relationship.
1265 ///
1266 /// \returns true if *this <= RHS when considered signed.
1267 bool sle(uint64_t RHS) const { return !sgt(RHS); }
1268
1269 /// Unsigned greater than comparison
1270 ///
1271 /// Regards both *this and RHS as unsigned quantities and compares them for
1272 /// the validity of the greater-than relationship.
1273 ///
1274 /// \returns true if *this > RHS when both are considered unsigned.
1275 bool ugt(const APInt &RHS) const { return !ule(RHS); }
1276
1277 /// Unsigned greater than comparison
1278 ///
1279 /// Regards both *this as an unsigned quantity and compares it with RHS for
1280 /// the validity of the greater-than relationship.
1281 ///
1282 /// \returns true if *this > RHS when considered unsigned.
1283 bool ugt(uint64_t RHS) const {
1284 // Only need to check active bits if not a single word.
1285 return (!isSingleWord() && getActiveBits() > 64) || getZExtValue() > RHS;
1286 }
1287
1288 /// Signed greater than comparison
1289 ///
1290 /// Regards both *this and RHS as signed quantities and compares them for the
1291 /// validity of the greater-than relationship.
1292 ///
1293 /// \returns true if *this > RHS when both are considered signed.
1294 bool sgt(const APInt &RHS) const { return !sle(RHS); }
1295
1296 /// Signed greater than comparison
1297 ///
1298 /// Regards both *this as a signed quantity and compares it with RHS for
1299 /// the validity of the greater-than relationship.
1300 ///
1301 /// \returns true if *this > RHS when considered signed.
1302 bool sgt(int64_t RHS) const {
1303 return (!isSingleWord() && getMinSignedBits() > 64) ? !isNegative()
1304 : getSExtValue() > RHS;
1305 }
1306
1307 /// Unsigned greater or equal comparison
1308 ///
1309 /// Regards both *this and RHS as unsigned quantities and compares them for
1310 /// validity of the greater-or-equal relationship.
1311 ///
1312 /// \returns true if *this >= RHS when both are considered unsigned.
1313 bool uge(const APInt &RHS) const { return !ult(RHS); }
1314
1315 /// Unsigned greater or equal comparison
1316 ///
1317 /// Regards both *this as an unsigned quantity and compares it with RHS for
1318 /// the validity of the greater-or-equal relationship.
1319 ///
1320 /// \returns true if *this >= RHS when considered unsigned.
1321 bool uge(uint64_t RHS) const { return !ult(RHS); }
1322
1323 /// Signed greater or equal comparison
1324 ///
1325 /// Regards both *this and RHS as signed quantities and compares them for
1326 /// validity of the greater-or-equal relationship.
1327 ///
1328 /// \returns true if *this >= RHS when both are considered signed.
1329 bool sge(const APInt &RHS) const { return !slt(RHS); }
1330
1331 /// Signed greater or equal comparison
1332 ///
1333 /// Regards both *this as a signed quantity and compares it with RHS for
1334 /// the validity of the greater-or-equal relationship.
1335 ///
1336 /// \returns true if *this >= RHS when considered signed.
1337 bool sge(int64_t RHS) const { return !slt(RHS); }
1338
1339 /// This operation tests if there are any pairs of corresponding bits
1340 /// between this APInt and RHS that are both set.
1341 bool intersects(const APInt &RHS) const {
1342 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")(static_cast<void> (0));
1343 if (isSingleWord())
1344 return (U.VAL & RHS.U.VAL) != 0;
1345 return intersectsSlowCase(RHS);
1346 }
1347
1348 /// This operation checks that all bits set in this APInt are also set in RHS.
1349 bool isSubsetOf(const APInt &RHS) const {
1350 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")(static_cast<void> (0));
1351 if (isSingleWord())
1352 return (U.VAL & ~RHS.U.VAL) == 0;
1353 return isSubsetOfSlowCase(RHS);
1354 }
1355
1356 /// @}
1357 /// \name Resizing Operators
1358 /// @{
1359
1360 /// Truncate to new width.
1361 ///
1362 /// Truncate the APInt to a specified width. It is an error to specify a width
1363 /// that is greater than or equal to the current width.
1364 APInt trunc(unsigned width) const;
1365
1366 /// Truncate to new width with unsigned saturation.
1367 ///
1368 /// If the APInt, treated as unsigned integer, can be losslessly truncated to
1369 /// the new bitwidth, then return truncated APInt. Else, return max value.
1370 APInt truncUSat(unsigned width) const;
1371
1372 /// Truncate to new width with signed saturation.
1373 ///
1374 /// If this APInt, treated as signed integer, can be losslessly truncated to
1375 /// the new bitwidth, then return truncated APInt. Else, return either
1376 /// signed min value if the APInt was negative, or signed max value.
1377 APInt truncSSat(unsigned width) const;
1378
1379 /// Sign extend to a new width.
1380 ///
1381 /// This operation sign extends the APInt to a new width. If the high order
1382 /// bit is set, the fill on the left will be done with 1 bits, otherwise zero.
1383 /// It is an error to specify a width that is less than or equal to the
1384 /// current width.
1385 APInt sext(unsigned width) const;
1386
1387 /// Zero extend to a new width.
1388 ///
1389 /// This operation zero extends the APInt to a new width. The high order bits
1390 /// are filled with 0 bits. It is an error to specify a width that is less
1391 /// than or equal to the current width.
1392 APInt zext(unsigned width) const;
1393
1394 /// Sign extend or truncate to width
1395 ///
1396 /// Make this APInt have the bit width given by \p width. The value is sign
1397 /// extended, truncated, or left alone to make it that width.
1398 APInt sextOrTrunc(unsigned width) const;
1399
1400 /// Zero extend or truncate to width
1401 ///
1402 /// Make this APInt have the bit width given by \p width. The value is zero
1403 /// extended, truncated, or left alone to make it that width.
1404 APInt zextOrTrunc(unsigned width) const;
1405
1406 /// Truncate to width
1407 ///
1408 /// Make this APInt have the bit width given by \p width. The value is
1409 /// truncated or left alone to make it that width.
1410 APInt truncOrSelf(unsigned width) const;
1411
1412 /// Sign extend or truncate to width
1413 ///
1414 /// Make this APInt have the bit width given by \p width. The value is sign
1415 /// extended, or left alone to make it that width.
1416 APInt sextOrSelf(unsigned width) const;
1417
1418 /// Zero extend or truncate to width
1419 ///
1420 /// Make this APInt have the bit width given by \p width. The value is zero
1421 /// extended, or left alone to make it that width.
1422 APInt zextOrSelf(unsigned width) const;
1423
1424 /// @}
1425 /// \name Bit Manipulation Operators
1426 /// @{
1427
1428 /// Set every bit to 1.
1429 void setAllBits() {
1430 if (isSingleWord())
1431 U.VAL = WORDTYPE_MAX;
1432 else
1433 // Set all the bits in all the words.
1434 memset(U.pVal, -1, getNumWords() * APINT_WORD_SIZE);
1435 // Clear the unused ones
1436 clearUnusedBits();
1437 }
1438
1439 /// Set a given bit to 1.
1440 ///
1441 /// Set the given bit to 1 whose position is given as "bitPosition".
1442 void setBit(unsigned BitPosition) {
1443 assert(BitPosition < BitWidth && "BitPosition out of range")(static_cast<void> (0));
1444 WordType Mask = maskBit(BitPosition);
1445 if (isSingleWord())
1446 U.VAL |= Mask;
1447 else
1448 U.pVal[whichWord(BitPosition)] |= Mask;
1449 }
1450
1451 /// Set the sign bit to 1.
1452 void setSignBit() {
1453 setBit(BitWidth - 1);
1454 }
1455
1456 /// Set a given bit to a given value.
1457 void setBitVal(unsigned BitPosition, bool BitValue) {
1458 if (BitValue)
1459 setBit(BitPosition);
1460 else
1461 clearBit(BitPosition);
1462 }
1463
1464 /// Set the bits from loBit (inclusive) to hiBit (exclusive) to 1.
1465 /// This function handles "wrap" case when \p loBit >= \p hiBit, and calls
1466 /// setBits when \p loBit < \p hiBit.
1467 /// For \p loBit == \p hiBit wrap case, set every bit to 1.
1468 void setBitsWithWrap(unsigned loBit, unsigned hiBit) {
1469 assert(hiBit <= BitWidth && "hiBit out of range")(static_cast<void> (0));
1470 assert(loBit <= BitWidth && "loBit out of range")(static_cast<void> (0));
1471 if (loBit < hiBit) {
1472 setBits(loBit, hiBit);
1473 return;
1474 }
1475 setLowBits(hiBit);
1476 setHighBits(BitWidth - loBit);
1477 }
1478
1479 /// Set the bits from loBit (inclusive) to hiBit (exclusive) to 1.
1480 /// This function handles case when \p loBit <= \p hiBit.
1481 void setBits(unsigned loBit, unsigned hiBit) {
1482 assert(hiBit <= BitWidth && "hiBit out of range")(static_cast<void> (0));
1483 assert(loBit <= BitWidth && "loBit out of range")(static_cast<void> (0));
1484 assert(loBit <= hiBit && "loBit greater than hiBit")(static_cast<void> (0));
1485 if (loBit == hiBit)
1486 return;
1487 if (loBit < APINT_BITS_PER_WORD && hiBit <= APINT_BITS_PER_WORD) {
1488 uint64_t mask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - (hiBit - loBit));
1489 mask <<= loBit;
1490 if (isSingleWord())
1491 U.VAL |= mask;
1492 else
1493 U.pVal[0] |= mask;
1494 } else {
1495 setBitsSlowCase(loBit, hiBit);
1496 }
1497 }
1498
1499 /// Set the top bits starting from loBit.
1500 void setBitsFrom(unsigned loBit) {
1501 return setBits(loBit, BitWidth);
1502 }
1503
1504 /// Set the bottom loBits bits.
1505 void setLowBits(unsigned loBits) {
1506 return setBits(0, loBits);
1507 }
1508
1509 /// Set the top hiBits bits.
1510 void setHighBits(unsigned hiBits) {
1511 return setBits(BitWidth - hiBits, BitWidth);
1512 }
1513
1514 /// Set every bit to 0.
1515 void clearAllBits() {
1516 if (isSingleWord())
1517 U.VAL = 0;
1518 else
1519 memset(U.pVal, 0, getNumWords() * APINT_WORD_SIZE);
1520 }
1521
1522 /// Set a given bit to 0.
1523 ///
1524 /// Set the given bit to 0 whose position is given as "bitPosition".
1525 void clearBit(unsigned BitPosition) {
1526 assert(BitPosition < BitWidth && "BitPosition out of range")(static_cast<void> (0));
1527 WordType Mask = ~maskBit(BitPosition);
1528 if (isSingleWord())
1529 U.VAL &= Mask;
1530 else
1531 U.pVal[whichWord(BitPosition)] &= Mask;
1532 }
1533
1534 /// Set bottom loBits bits to 0.
1535 void clearLowBits(unsigned loBits) {
1536 assert(loBits <= BitWidth && "More bits than bitwidth")(static_cast<void> (0));
1537 APInt Keep = getHighBitsSet(BitWidth, BitWidth - loBits);
1538 *this &= Keep;
1539 }
1540
1541 /// Set the sign bit to 0.
1542 void clearSignBit() {
1543 clearBit(BitWidth - 1);
1544 }
1545
1546 /// Toggle every bit to its opposite value.
1547 void flipAllBits() {
1548 if (isSingleWord()) {
1549 U.VAL ^= WORDTYPE_MAX;
1550 clearUnusedBits();
1551 } else {
1552 flipAllBitsSlowCase();
1553 }
1554 }
1555
1556 /// Toggles a given bit to its opposite value.
1557 ///
1558 /// Toggle a given bit to its opposite value whose position is given
1559 /// as "bitPosition".
1560 void flipBit(unsigned bitPosition);
1561
1562 /// Negate this APInt in place.
1563 void negate() {
1564 flipAllBits();
1565 ++(*this);
1566 }
1567
1568 /// Insert the bits from a smaller APInt starting at bitPosition.
1569 void insertBits(const APInt &SubBits, unsigned bitPosition);
1570 void insertBits(uint64_t SubBits, unsigned bitPosition, unsigned numBits);
1571
1572 /// Return an APInt with the extracted bits [bitPosition,bitPosition+numBits).
1573 APInt extractBits(unsigned numBits, unsigned bitPosition) const;
1574 uint64_t extractBitsAsZExtValue(unsigned numBits, unsigned bitPosition) const;
1575
1576 /// @}
1577 /// \name Value Characterization Functions
1578 /// @{
1579
1580 /// Return the number of bits in the APInt.
1581 unsigned getBitWidth() const { return BitWidth; }
1582
1583 /// Get the number of words.
1584 ///
1585 /// Here one word's bitwidth equals to that of uint64_t.
1586 ///
1587 /// \returns the number of words to hold the integer value of this APInt.
1588 unsigned getNumWords() const { return getNumWords(BitWidth); }
1589
1590 /// Get the number of words.
1591 ///
1592 /// *NOTE* Here one word's bitwidth equals to that of uint64_t.
1593 ///
1594 /// \returns the number of words to hold the integer value with a given bit
1595 /// width.
1596 static unsigned getNumWords(unsigned BitWidth) {
1597 return ((uint64_t)BitWidth + APINT_BITS_PER_WORD - 1) / APINT_BITS_PER_WORD;
1598 }
1599
1600 /// Compute the number of active bits in the value
1601 ///
1602 /// This function returns the number of active bits which is defined as the
1603 /// bit width minus the number of leading zeros. This is used in several
1604 /// computations to see how "wide" the value is.
1605 unsigned getActiveBits() const { return BitWidth - countLeadingZeros(); }
1606
1607 /// Compute the number of active words in the value of this APInt.
1608 ///
1609 /// This is used in conjunction with getActiveData to extract the raw value of
1610 /// the APInt.
1611 unsigned getActiveWords() const {
1612 unsigned numActiveBits = getActiveBits();
1613 return numActiveBits ? whichWord(numActiveBits - 1) + 1 : 1;
1614 }
1615
1616 /// Get the minimum bit size for this signed APInt
1617 ///
1618 /// Computes the minimum bit width for this APInt while considering it to be a
1619 /// signed (and probably negative) value. If the value is not negative, this
1620 /// function returns the same value as getActiveBits()+1. Otherwise, it
1621 /// returns the smallest bit width that will retain the negative value. For
1622 /// example, -1 can be written as 0b1 or 0xFFFFFFFFFF. 0b1 is shorter and so
1623 /// for -1, this function will always return 1.
1624 unsigned getMinSignedBits() const { return BitWidth - getNumSignBits() + 1; }
1625
1626 /// Get zero extended value
1627 ///
1628 /// This method attempts to return the value of this APInt as a zero extended
1629 /// uint64_t. The bitwidth must be <= 64 or the value must fit within a
1630 /// uint64_t. Otherwise an assertion will result.
1631 uint64_t getZExtValue() const {
1632 if (isSingleWord())
1633 return U.VAL;
1634 assert(getActiveBits() <= 64 && "Too many bits for uint64_t")(static_cast<void> (0));
1635 return U.pVal[0];
1636 }
1637
1638 /// Get sign extended value
1639 ///
1640 /// This method attempts to return the value of this APInt as a sign extended
1641 /// int64_t. The bit width must be <= 64 or the value must fit within an
1642 /// int64_t. Otherwise an assertion will result.
1643 int64_t getSExtValue() const {
1644 if (isSingleWord())
1645 return SignExtend64(U.VAL, BitWidth);
1646 assert(getMinSignedBits() <= 64 && "Too many bits for int64_t")(static_cast<void> (0));
1647 return int64_t(U.pVal[0]);
1648 }
1649
1650 /// Get bits required for string value.
1651 ///
1652 /// This method determines how many bits are required to hold the APInt
1653 /// equivalent of the string given by \p str.
1654 static unsigned getBitsNeeded(StringRef str, uint8_t radix);
1655
1656 /// The APInt version of the countLeadingZeros functions in
1657 /// MathExtras.h.
1658 ///
1659 /// It counts the number of zeros from the most significant bit to the first
1660 /// one bit.
1661 ///
1662 /// \returns BitWidth if the value is zero, otherwise returns the number of
1663 /// zeros from the most significant bit to the first one bits.
1664 unsigned countLeadingZeros() const {
1665 if (isSingleWord()) {
1666 unsigned unusedBits = APINT_BITS_PER_WORD - BitWidth;
1667 return llvm::countLeadingZeros(U.VAL) - unusedBits;
1668 }
1669 return countLeadingZerosSlowCase();
1670 }
1671
1672 /// Count the number of leading one bits.
1673 ///
1674 /// This function is an APInt version of the countLeadingOnes
1675 /// functions in MathExtras.h. It counts the number of ones from the most
1676 /// significant bit to the first zero bit.
1677 ///
1678 /// \returns 0 if the high order bit is not set, otherwise returns the number
1679 /// of 1 bits from the most significant to the least
1680 unsigned countLeadingOnes() const {
1681 if (isSingleWord())
1682 return llvm::countLeadingOnes(U.VAL << (APINT_BITS_PER_WORD - BitWidth));
1683 return countLeadingOnesSlowCase();
1684 }
1685
1686 /// Computes the number of leading bits of this APInt that are equal to its
1687 /// sign bit.
1688 unsigned getNumSignBits() const {
1689 return isNegative() ? countLeadingOnes() : countLeadingZeros();
1690 }
1691
1692 /// Count the number of trailing zero bits.
1693 ///
1694 /// This function is an APInt version of the countTrailingZeros
1695 /// functions in MathExtras.h. It counts the number of zeros from the least
1696 /// significant bit to the first set bit.
1697 ///
1698 /// \returns BitWidth if the value is zero, otherwise returns the number of
1699 /// zeros from the least significant bit to the first one bit.
1700 unsigned countTrailingZeros() const {
1701 if (isSingleWord()) {
1702 unsigned TrailingZeros = llvm::countTrailingZeros(U.VAL);
1703 return (TrailingZeros > BitWidth ? BitWidth : TrailingZeros);
1704 }
1705 return countTrailingZerosSlowCase();
1706 }
1707
1708 /// Count the number of trailing one bits.
1709 ///
1710 /// This function is an APInt version of the countTrailingOnes
1711 /// functions in MathExtras.h. It counts the number of ones from the least
1712 /// significant bit to the first zero bit.
1713 ///
1714 /// \returns BitWidth if the value is all ones, otherwise returns the number
1715 /// of ones from the least significant bit to the first zero bit.
1716 unsigned countTrailingOnes() const {
1717 if (isSingleWord())
1718 return llvm::countTrailingOnes(U.VAL);
1719 return countTrailingOnesSlowCase();
1720 }
1721
1722 /// Count the number of bits set.
1723 ///
1724 /// This function is an APInt version of the countPopulation functions
1725 /// in MathExtras.h. It counts the number of 1 bits in the APInt value.
1726 ///
1727 /// \returns 0 if the value is zero, otherwise returns the number of set bits.
1728 unsigned countPopulation() const {
1729 if (isSingleWord())
1730 return llvm::countPopulation(U.VAL);
1731 return countPopulationSlowCase();
1732 }
1733
1734 /// @}
1735 /// \name Conversion Functions
1736 /// @{
1737 void print(raw_ostream &OS, bool isSigned) const;
1738
1739 /// Converts an APInt to a string and append it to Str. Str is commonly a
1740 /// SmallString.
1741 void toString(SmallVectorImpl<char> &Str, unsigned Radix, bool Signed,
1742 bool formatAsCLiteral = false) const;
1743
1744 /// Considers the APInt to be unsigned and converts it into a string in the
1745 /// radix given. The radix can be 2, 8, 10 16, or 36.
1746 void toStringUnsigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const {
1747 toString(Str, Radix, false, false);
1748 }
1749
1750 /// Considers the APInt to be signed and converts it into a string in the
1751 /// radix given. The radix can be 2, 8, 10, 16, or 36.
1752 void toStringSigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const {
1753 toString(Str, Radix, true, false);
1754 }
1755
1756 /// \returns a byte-swapped representation of this APInt Value.
1757 APInt byteSwap() const;
1758
1759 /// \returns the value with the bit representation reversed of this APInt
1760 /// Value.
1761 APInt reverseBits() const;
1762
1763 /// Converts this APInt to a double value.
1764 double roundToDouble(bool isSigned) const;
1765
1766 /// Converts this unsigned APInt to a double value.
1767 double roundToDouble() const { return roundToDouble(false); }
1768
1769 /// Converts this signed APInt to a double value.
1770 double signedRoundToDouble() const { return roundToDouble(true); }
1771
1772 /// Converts APInt bits to a double
1773 ///
1774 /// The conversion does not do a translation from integer to double, it just
1775 /// re-interprets the bits as a double. Note that it is valid to do this on
1776 /// any bit width. Exactly 64 bits will be translated.
1777 double bitsToDouble() const {
1778 return BitsToDouble(getWord(0));
1779 }
1780
1781 /// Converts APInt bits to a float
1782 ///
1783 /// The conversion does not do a translation from integer to float, it just
1784 /// re-interprets the bits as a float. Note that it is valid to do this on
1785 /// any bit width. Exactly 32 bits will be translated.
1786 float bitsToFloat() const {
1787 return BitsToFloat(static_cast<uint32_t>(getWord(0)));
1788 }
1789
1790 /// Converts a double to APInt bits.
1791 ///
1792 /// The conversion does not do a translation from double to integer, it just
1793 /// re-interprets the bits of the double.
1794 static APInt doubleToBits(double V) {
1795 return APInt(sizeof(double) * CHAR_BIT8, DoubleToBits(V));
1796 }
1797
1798 /// Converts a float to APInt bits.
1799 ///
1800 /// The conversion does not do a translation from float to integer, it just
1801 /// re-interprets the bits of the float.
1802 static APInt floatToBits(float V) {
1803 return APInt(sizeof(float) * CHAR_BIT8, FloatToBits(V));
1804 }
1805
1806 /// @}
1807 /// \name Mathematics Operations
1808 /// @{
1809
1810 /// \returns the floor log base 2 of this APInt.
1811 unsigned logBase2() const { return getActiveBits() - 1; }
1812
1813 /// \returns the ceil log base 2 of this APInt.
1814 unsigned ceilLogBase2() const {
1815 APInt temp(*this);
1816 --temp;
1817 return temp.getActiveBits();
1818 }
1819
1820 /// \returns the nearest log base 2 of this APInt. Ties round up.
1821 ///
1822 /// NOTE: When we have a BitWidth of 1, we define:
1823 ///
1824 /// log2(0) = UINT32_MAX
1825 /// log2(1) = 0
1826 ///
1827 /// to get around any mathematical concerns resulting from
1828 /// referencing 2 in a space where 2 does no exist.
1829 unsigned nearestLogBase2() const {
1830 // Special case when we have a bitwidth of 1. If VAL is 1, then we
1831 // get 0. If VAL is 0, we get WORDTYPE_MAX which gets truncated to
1832 // UINT32_MAX.
1833 if (BitWidth == 1)
1834 return U.VAL - 1;
1835
1836 // Handle the zero case.
1837 if (isNullValue())
1838 return UINT32_MAX(4294967295U);
1839
1840 // The non-zero case is handled by computing:
1841 //
1842 // nearestLogBase2(x) = logBase2(x) + x[logBase2(x)-1].
1843 //
1844 // where x[i] is referring to the value of the ith bit of x.
1845 unsigned lg = logBase2();
1846 return lg + unsigned((*this)[lg - 1]);
1847 }
1848
1849 /// \returns the log base 2 of this APInt if its an exact power of two, -1
1850 /// otherwise
1851 int32_t exactLogBase2() const {
1852 if (!isPowerOf2())
1853 return -1;
1854 return logBase2();
1855 }
1856
1857 /// Compute the square root
1858 APInt sqrt() const;
1859
1860 /// Get the absolute value;
1861 ///
1862 /// If *this is < 0 then return -(*this), otherwise *this;
1863 APInt abs() const {
1864 if (isNegative())
1865 return -(*this);
1866 return *this;
1867 }
1868
1869 /// \returns the multiplicative inverse for a given modulo.
1870 APInt multiplicativeInverse(const APInt &modulo) const;
1871
1872 /// @}
1873 /// \name Support for division by constant
1874 /// @{
1875
1876 /// Calculate the magic number for signed division by a constant.
1877 struct ms;
1878 ms magic() const;
1879
1880 /// Calculate the magic number for unsigned division by a constant.
1881 struct mu;
1882 mu magicu(unsigned LeadingZeros = 0) const;
1883
1884 /// @}
1885 /// \name Building-block Operations for APInt and APFloat
1886 /// @{
1887
1888 // These building block operations operate on a representation of arbitrary
1889 // precision, two's-complement, bignum integer values. They should be
1890 // sufficient to implement APInt and APFloat bignum requirements. Inputs are
1891 // generally a pointer to the base of an array of integer parts, representing
1892 // an unsigned bignum, and a count of how many parts there are.
1893
1894 /// Sets the least significant part of a bignum to the input value, and zeroes
1895 /// out higher parts.
1896 static void tcSet(WordType *, WordType, unsigned);
1897
1898 /// Assign one bignum to another.
1899 static void tcAssign(WordType *, const WordType *, unsigned);
1900
1901 /// Returns true if a bignum is zero, false otherwise.
1902 static bool tcIsZero(const WordType *, unsigned);
1903
1904 /// Extract the given bit of a bignum; returns 0 or 1. Zero-based.
1905 static int tcExtractBit(const WordType *, unsigned bit);
1906
1907 /// Copy the bit vector of width srcBITS from SRC, starting at bit srcLSB, to
1908 /// DST, of dstCOUNT parts, such that the bit srcLSB becomes the least
1909 /// significant bit of DST. All high bits above srcBITS in DST are
1910 /// zero-filled.
1911 static void tcExtract(WordType *, unsigned dstCount,
1912 const WordType *, unsigned srcBits,
1913 unsigned srcLSB);
1914
1915 /// Set the given bit of a bignum. Zero-based.
1916 static void tcSetBit(WordType *, unsigned bit);
1917
1918 /// Clear the given bit of a bignum. Zero-based.
1919 static void tcClearBit(WordType *, unsigned bit);
1920
1921 /// Returns the bit number of the least or most significant set bit of a
1922 /// number. If the input number has no bits set -1U is returned.
1923 static unsigned tcLSB(const WordType *, unsigned n);
1924 static unsigned tcMSB(const WordType *parts, unsigned n);
1925
1926 /// Negate a bignum in-place.
1927 static void tcNegate(WordType *, unsigned);
1928
1929 /// DST += RHS + CARRY where CARRY is zero or one. Returns the carry flag.
1930 static WordType tcAdd(WordType *, const WordType *,
1931 WordType carry, unsigned);
1932 /// DST += RHS. Returns the carry flag.
1933 static WordType tcAddPart(WordType *, WordType, unsigned);
1934
1935 /// DST -= RHS + CARRY where CARRY is zero or one. Returns the carry flag.
1936 static WordType tcSubtract(WordType *, const WordType *,
1937 WordType carry, unsigned);
1938 /// DST -= RHS. Returns the carry flag.
1939 static WordType tcSubtractPart(WordType *, WordType, unsigned);
1940
1941 /// DST += SRC * MULTIPLIER + PART if add is true
1942 /// DST = SRC * MULTIPLIER + PART if add is false
1943 ///
1944 /// Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC they must
1945 /// start at the same point, i.e. DST == SRC.
1946 ///
1947 /// If DSTPARTS == SRC_PARTS + 1 no overflow occurs and zero is returned.
1948 /// Otherwise DST is filled with the least significant DSTPARTS parts of the
1949 /// result, and if all of the omitted higher parts were zero return zero,
1950 /// otherwise overflow occurred and return one.
1951 static int tcMultiplyPart(WordType *dst, const WordType *src,
1952 WordType multiplier, WordType carry,
1953 unsigned srcParts, unsigned dstParts,
1954 bool add);
1955
1956 /// DST = LHS * RHS, where DST has the same width as the operands and is
1957 /// filled with the least significant parts of the result. Returns one if
1958 /// overflow occurred, otherwise zero. DST must be disjoint from both
1959 /// operands.
1960 static int tcMultiply(WordType *, const WordType *, const WordType *,
1961 unsigned);
1962
1963 /// DST = LHS * RHS, where DST has width the sum of the widths of the
1964 /// operands. No overflow occurs. DST must be disjoint from both operands.
1965 static void tcFullMultiply(WordType *, const WordType *,
1966 const WordType *, unsigned, unsigned);
1967
1968 /// If RHS is zero LHS and REMAINDER are left unchanged, return one.
1969 /// Otherwise set LHS to LHS / RHS with the fractional part discarded, set
1970 /// REMAINDER to the remainder, return zero. i.e.
1971 ///
1972 /// OLD_LHS = RHS * LHS + REMAINDER
1973 ///
1974 /// SCRATCH is a bignum of the same size as the operands and result for use by
1975 /// the routine; its contents need not be initialized and are destroyed. LHS,
1976 /// REMAINDER and SCRATCH must be distinct.
1977 static int tcDivide(WordType *lhs, const WordType *rhs,
1978 WordType *remainder, WordType *scratch,
1979 unsigned parts);
1980
1981 /// Shift a bignum left Count bits. Shifted in bits are zero. There are no
1982 /// restrictions on Count.
1983 static void tcShiftLeft(WordType *, unsigned Words, unsigned Count);
1984
1985 /// Shift a bignum right Count bits. Shifted in bits are zero. There are no
1986 /// restrictions on Count.
1987 static void tcShiftRight(WordType *, unsigned Words, unsigned Count);
1988
1989 /// The obvious AND, OR and XOR and complement operations.
1990 static void tcAnd(WordType *, const WordType *, unsigned);
1991 static void tcOr(WordType *, const WordType *, unsigned);
1992 static void tcXor(WordType *, const WordType *, unsigned);
1993 static void tcComplement(WordType *, unsigned);
1994
1995 /// Comparison (unsigned) of two bignums.
1996 static int tcCompare(const WordType *, const WordType *, unsigned);
1997
1998 /// Increment a bignum in-place. Return the carry flag.
1999 static WordType tcIncrement(WordType *dst, unsigned parts) {
2000 return tcAddPart(dst, 1, parts);
2001 }
2002
2003 /// Decrement a bignum in-place. Return the borrow flag.
2004 static WordType tcDecrement(WordType *dst, unsigned parts) {
2005 return tcSubtractPart(dst, 1, parts);
2006 }
2007
2008 /// Set the least significant BITS and clear the rest.
2009 static void tcSetLeastSignificantBits(WordType *, unsigned, unsigned bits);
2010
2011 /// debug method
2012 void dump() const;
2013
2014 /// @}
2015};
2016
2017/// Magic data for optimising signed division by a constant.
2018struct APInt::ms {
2019 APInt m; ///< magic number
2020 unsigned s; ///< shift amount
2021};
2022
2023/// Magic data for optimising unsigned division by a constant.
2024struct APInt::mu {
2025 APInt m; ///< magic number
2026 bool a; ///< add indicator
2027 unsigned s; ///< shift amount
2028};
2029
2030inline bool operator==(uint64_t V1, const APInt &V2) { return V2 == V1; }
2031
2032inline bool operator!=(uint64_t V1, const APInt &V2) { return V2 != V1; }
2033
2034/// Unary bitwise complement operator.
2035///
2036/// \returns an APInt that is the bitwise complement of \p v.
2037inline APInt operator~(APInt v) {
2038 v.flipAllBits();
2039 return v;
2040}
2041
2042inline APInt operator&(APInt a, const APInt &b) {
2043 a &= b;
2044 return a;
2045}
2046
2047inline APInt operator&(const APInt &a, APInt &&b) {
2048 b &= a;
2049 return std::move(b);
2050}
2051
2052inline APInt operator&(APInt a, uint64_t RHS) {
2053 a &= RHS;
2054 return a;
2055}
2056
2057inline APInt operator&(uint64_t LHS, APInt b) {
2058 b &= LHS;
2059 return b;
2060}
2061
2062inline APInt operator|(APInt a, const APInt &b) {
2063 a |= b;
2064 return a;
2065}
2066
2067inline APInt operator|(const APInt &a, APInt &&b) {
2068 b |= a;
2069 return std::move(b);
2070}
2071
2072inline APInt operator|(APInt a, uint64_t RHS) {
2073 a |= RHS;
2074 return a;
2075}
2076
2077inline APInt operator|(uint64_t LHS, APInt b) {
2078 b |= LHS;
2079 return b;
2080}
2081
2082inline APInt operator^(APInt a, const APInt &b) {
2083 a ^= b;
2084 return a;
2085}
2086
2087inline APInt operator^(const APInt &a, APInt &&b) {
2088 b ^= a;
2089 return std::move(b);
2090}
2091
2092inline APInt operator^(APInt a, uint64_t RHS) {
2093 a ^= RHS;
2094 return a;
2095}
2096
2097inline APInt operator^(uint64_t LHS, APInt b) {
2098 b ^= LHS;
2099 return b;
2100}
2101
2102inline raw_ostream &operator<<(raw_ostream &OS, const APInt &I) {
2103 I.print(OS, true);
2104 return OS;
2105}
2106
2107inline APInt operator-(APInt v) {
2108 v.negate();
2109 return v;
2110}
2111
2112inline APInt operator+(APInt a, const APInt &b) {
2113 a += b;
2114 return a;
2115}
2116
2117inline APInt operator+(const APInt &a, APInt &&b) {
2118 b += a;
2119 return std::move(b);
2120}
2121
2122inline APInt operator+(APInt a, uint64_t RHS) {
2123 a += RHS;
2124 return a;
2125}
2126
2127inline APInt operator+(uint64_t LHS, APInt b) {
2128 b += LHS;
2129 return b;
2130}
2131
2132inline APInt operator-(APInt a, const APInt &b) {
2133 a -= b;
2134 return a;
2135}
2136
2137inline APInt operator-(const APInt &a, APInt &&b) {
2138 b.negate();
2139 b += a;
2140 return std::move(b);
2141}
2142
2143inline APInt operator-(APInt a, uint64_t RHS) {
2144 a -= RHS;
2145 return a;
2146}
2147
2148inline APInt operator-(uint64_t LHS, APInt b) {
2149 b.negate();
2150 b += LHS;
2151 return b;
2152}
2153
2154inline APInt operator*(APInt a, uint64_t RHS) {
2155 a *= RHS;
2156 return a;
2157}
2158
2159inline APInt operator*(uint64_t LHS, APInt b) {
2160 b *= LHS;
2161 return b;
2162}
2163
2164
2165namespace APIntOps {
2166
2167/// Determine the smaller of two APInts considered to be signed.
2168inline const APInt &smin(const APInt &A, const APInt &B) {
2169 return A.slt(B) ? A : B;
2170}
2171
2172/// Determine the larger of two APInts considered to be signed.
2173inline const APInt &smax(const APInt &A, const APInt &B) {
2174 return A.sgt(B) ? A : B;
2175}
2176
2177/// Determine the smaller of two APInts considered to be unsigned.
2178inline const APInt &umin(const APInt &A, const APInt &B) {
2179 return A.ult(B) ? A : B;
2180}
2181
2182/// Determine the larger of two APInts considered to be unsigned.
2183inline const APInt &umax(const APInt &A, const APInt &B) {
2184 return A.ugt(B) ? A : B;
2185}
2186
2187/// Compute GCD of two unsigned APInt values.
2188///
2189/// This function returns the greatest common divisor of the two APInt values
2190/// using Stein's algorithm.
2191///
2192/// \returns the greatest common divisor of A and B.
2193APInt GreatestCommonDivisor(APInt A, APInt B);
2194
2195/// Converts the given APInt to a double value.
2196///
2197/// Treats the APInt as an unsigned value for conversion purposes.
2198inline double RoundAPIntToDouble(const APInt &APIVal) {
2199 return APIVal.roundToDouble();
2200}
2201
2202/// Converts the given APInt to a double value.
2203///
2204/// Treats the APInt as a signed value for conversion purposes.
2205inline double RoundSignedAPIntToDouble(const APInt &APIVal) {
2206 return APIVal.signedRoundToDouble();
2207}
2208
2209/// Converts the given APInt to a float value.
2210inline float RoundAPIntToFloat(const APInt &APIVal) {
2211 return float(RoundAPIntToDouble(APIVal));
2212}
2213
2214/// Converts the given APInt to a float value.
2215///
2216/// Treats the APInt as a signed value for conversion purposes.
2217inline float RoundSignedAPIntToFloat(const APInt &APIVal) {
2218 return float(APIVal.signedRoundToDouble());
2219}
2220
2221/// Converts the given double value into a APInt.
2222///
2223/// This function convert a double value to an APInt value.
2224APInt RoundDoubleToAPInt(double Double, unsigned width);
2225
2226/// Converts a float value into a APInt.
2227///
2228/// Converts a float value into an APInt value.
2229inline APInt RoundFloatToAPInt(float Float, unsigned width) {
2230 return RoundDoubleToAPInt(double(Float), width);
2231}
2232
2233/// Return A unsign-divided by B, rounded by the given rounding mode.
2234APInt RoundingUDiv(const APInt &A, const APInt &B, APInt::Rounding RM);
2235
2236/// Return A sign-divided by B, rounded by the given rounding mode.
2237APInt RoundingSDiv(const APInt &A, const APInt &B, APInt::Rounding RM);
2238
2239/// Let q(n) = An^2 + Bn + C, and BW = bit width of the value range
2240/// (e.g. 32 for i32).
2241/// This function finds the smallest number n, such that
2242/// (a) n >= 0 and q(n) = 0, or
2243/// (b) n >= 1 and q(n-1) and q(n), when evaluated in the set of all
2244/// integers, belong to two different intervals [Rk, Rk+R),
2245/// where R = 2^BW, and k is an integer.
2246/// The idea here is to find when q(n) "overflows" 2^BW, while at the
2247/// same time "allowing" subtraction. In unsigned modulo arithmetic a
2248/// subtraction (treated as addition of negated numbers) would always
2249/// count as an overflow, but here we want to allow values to decrease
2250/// and increase as long as they are within the same interval.
2251/// Specifically, adding of two negative numbers should not cause an
2252/// overflow (as long as the magnitude does not exceed the bit width).
2253/// On the other hand, given a positive number, adding a negative
2254/// number to it can give a negative result, which would cause the
2255/// value to go from [-2^BW, 0) to [0, 2^BW). In that sense, zero is
2256/// treated as a special case of an overflow.
2257///
2258/// This function returns None if after finding k that minimizes the
2259/// positive solution to q(n) = kR, both solutions are contained between
2260/// two consecutive integers.
2261///
2262/// There are cases where q(n) > T, and q(n+1) < T (assuming evaluation
2263/// in arithmetic modulo 2^BW, and treating the values as signed) by the
2264/// virtue of *signed* overflow. This function will *not* find such an n,
2265/// however it may find a value of n satisfying the inequalities due to
2266/// an *unsigned* overflow (if the values are treated as unsigned).
2267/// To find a solution for a signed overflow, treat it as a problem of
2268/// finding an unsigned overflow with a range with of BW-1.
2269///
2270/// The returned value may have a different bit width from the input
2271/// coefficients.
2272Optional<APInt> SolveQuadraticEquationWrap(APInt A, APInt B, APInt C,
2273 unsigned RangeWidth);
2274
2275/// Compare two values, and if they are different, return the position of the
2276/// most significant bit that is different in the values.
2277Optional<unsigned> GetMostSignificantDifferentBit(const APInt &A,
2278 const APInt &B);
2279
2280} // End of APIntOps namespace
2281
2282// See friend declaration above. This additional declaration is required in
2283// order to compile LLVM with IBM xlC compiler.
2284hash_code hash_value(const APInt &Arg);
2285
2286/// StoreIntToMemory - Fills the StoreBytes bytes of memory starting from Dst
2287/// with the integer held in IntVal.
2288void StoreIntToMemory(const APInt &IntVal, uint8_t *Dst, unsigned StoreBytes);
2289
2290/// LoadIntFromMemory - Loads the integer stored in the LoadBytes bytes starting
2291/// from Src into IntVal, which is assumed to be wide enough and to hold zero.
2292void LoadIntFromMemory(APInt &IntVal, const uint8_t *Src, unsigned LoadBytes);
2293
2294/// Provide DenseMapInfo for APInt.
2295template <> struct DenseMapInfo<APInt> {
2296 static inline APInt getEmptyKey() {
2297 APInt V(nullptr, 0);
2298 V.U.VAL = 0;
2299 return V;
2300 }
2301
2302 static inline APInt getTombstoneKey() {
2303 APInt V(nullptr, 0);
2304 V.U.VAL = 1;
2305 return V;
2306 }
2307
2308 static unsigned getHashValue(const APInt &Key);
2309
2310 static bool isEqual(const APInt &LHS, const APInt &RHS) {
2311 return LHS.getBitWidth() == RHS.getBitWidth() && LHS == RHS;
2312 }
2313};
2314
2315} // namespace llvm
2316
2317#endif