Bug Summary

File:llvm/lib/Support/APInt.cpp
Warning:line 88, 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 -disable-llvm-verifier -discard-value-names -main-file-name APInt.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -fno-split-dwarf-inlining -debugger-tuning=gdb -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-12/lib/clang/12.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/build-llvm/lib/Support -I /build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Support -I /build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/build-llvm/include -I /build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-12/lib/clang/12.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/build-llvm/lib/Support -fdebug-prefix-map=/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998=. -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -o /tmp/scan-build-2020-09-28-092409-31635-1 -x c++ /build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Support/APInt.cpp

/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Support/APInt.cpp

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

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