Bug Summary

File:build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/llvm/lib/Support/APInt.cpp
Warning:line 86, column 3
Use of memory after it is freed

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -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 -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/build-llvm -resource-dir /usr/lib/llvm-15/lib/clang/15.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I lib/Support -I /build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/llvm/lib/Support -I include -I /build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/llvm/include -D _FORTIFY_SOURCE=2 -D NDEBUG -U 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-15/lib/clang/15.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 -fmacro-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/build-llvm=build-llvm -fmacro-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/= -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/build-llvm=build-llvm -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/= -O3 -Wno-unused-command-line-argument -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-15~++20220420111733+e13d2efed663/build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/build-llvm=build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/= -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcolor-diagnostics -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-2022-04-20-140412-16051-1 -x c++ /build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/llvm/lib/Support/APInt.cpp

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

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