Bug Summary

File:llvm/lib/Support/APInt.cpp
Warning:line 1908, column 3
Use of memory after it is freed

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -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 -mthread-model posix -mframe-pointer=none -fmath-errno -fno-rounding-math -masm-verbose -mconstructor-aliases -munwind-tables -target-cpu x86-64 -dwarf-column-info -fno-split-dwarf-inlining -debugger-tuning=gdb -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-11/lib/clang/11.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/build-llvm/lib/Support -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Support -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/build-llvm/include -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/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-11/lib/clang/11.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-11~++20200309111110+2c36c23f347/build-llvm/lib/Support -fdebug-prefix-map=/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347=. -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -o /tmp/scan-build-2020-03-09-184146-41876-1 -x c++ /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Support/APInt.cpp

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

/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/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;
34
35class APInt;
36
37inline APInt operator-(APInt);
38
39//===----------------------------------------------------------------------===//
40// APInt Class
41//===----------------------------------------------------------------------===//
42
43/// Class for arbitrary precision integers.
44///
45/// APInt is a functional replacement for common case unsigned integer type like
46/// "unsigned", "unsigned long" or "uint64_t", but also allows non-byte-width
47/// integer sizes and large integer value types such as 3-bits, 15-bits, or more
48/// than 64-bits of precision. APInt provides a variety of arithmetic operators
49/// and methods to manipulate integer values of any bit-width. It supports both
50/// the typical integer arithmetic and comparison operations as well as bitwise
51/// manipulation.
52///
53/// The class has several invariants worth noting:
54/// * All bit, byte, and word positions are zero-based.
55/// * Once the bit width is set, it doesn't change except by the Truncate,
56/// SignExtend, or ZeroExtend operations.
57/// * All binary operators must be on APInt instances of the same bit width.
58/// Attempting to use these operators on instances with different bit
59/// widths will yield an assertion.
60/// * The value is stored canonically as an unsigned value. For operations
61/// where it makes a difference, there are both signed and unsigned variants
62/// of the operation. For example, sdiv and udiv. However, because the bit
63/// widths must be the same, operations such as Mul and Add produce the same
64/// results regardless of whether the values are interpreted as signed or
65/// not.
66/// * In general, the class tries to follow the style of computation that LLVM
67/// uses in its IR. This simplifies its use for LLVM.
68///
69class LLVM_NODISCARD[[clang::warn_unused_result]] APInt {
70public:
71 typedef uint64_t WordType;
72
73 /// This enum is used to hold the constants we needed for APInt.
74 enum : unsigned {
75 /// Byte size of a word.
76 APINT_WORD_SIZE = sizeof(WordType),
77 /// Bits in a word.
78 APINT_BITS_PER_WORD = APINT_WORD_SIZE * CHAR_BIT8
79 };
80
81 enum class Rounding {
82 DOWN,
83 TOWARD_ZERO,
84 UP,
85 };
86
87 static const WordType WORDTYPE_MAX = ~WordType(0);
88
89private:
90 /// This union is used to store the integer value. When the
91 /// integer bit-width <= 64, it uses VAL, otherwise it uses pVal.
92 union {
93 uint64_t VAL; ///< Used to store the <= 64 bits integer value.
94 uint64_t *pVal; ///< Used to store the >64 bits integer value.
95 } U;
96
97 unsigned BitWidth; ///< The number of bits in this APInt.
98
99 friend struct DenseMapAPIntKeyInfo;
100
101 friend class APSInt;
102
103 /// Fast internal constructor
104 ///
105 /// This constructor is used only internally for speed of construction of
106 /// temporaries. It is unsafe for general use so it is not public.
107 APInt(uint64_t *val, unsigned bits) : BitWidth(bits) {
108 U.pVal = val;
109 }
110
111 /// Determine if this APInt just has one word to store value.
112 ///
113 /// \returns true if the number of bits <= 64, false otherwise.
114 bool isSingleWord() const { return BitWidth <= APINT_BITS_PER_WORD; }
115
116 /// Determine which word a bit is in.
117 ///
118 /// \returns the word position for the specified bit position.
119 static unsigned whichWord(unsigned bitPosition) {
120 return bitPosition / APINT_BITS_PER_WORD;
121 }
122
123 /// Determine which bit in a word a bit is in.
124 ///
125 /// \returns the bit position in a word for the specified bit position
126 /// in the APInt.
127 static unsigned whichBit(unsigned bitPosition) {
128 return bitPosition % APINT_BITS_PER_WORD;
129 }
130
131 /// Get a single bit mask.
132 ///
133 /// \returns a uint64_t with only bit at "whichBit(bitPosition)" set
134 /// This method generates and returns a uint64_t (word) mask for a single
135 /// bit at a specific bit position. This is used to mask the bit in the
136 /// corresponding word.
137 static uint64_t maskBit(unsigned bitPosition) {
138 return 1ULL << whichBit(bitPosition);
139 }
140
141 /// Clear unused high order bits
142 ///
143 /// This method is used internally to clear the top "N" bits in the high order
144 /// word that are not used by the APInt. This is needed after the most
145 /// significant word is assigned a value to ensure that those bits are
146 /// zero'd out.
147 APInt &clearUnusedBits() {
148 // Compute how many bits are used in the final word
149 unsigned WordBits = ((BitWidth-1) % APINT_BITS_PER_WORD) + 1;
150
151 // Mask out the high bits.
152 uint64_t mask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - WordBits);
153 if (isSingleWord())
154 U.VAL &= mask;
155 else
156 U.pVal[getNumWords() - 1] &= mask;
157 return *this;
158 }
159
160 /// Get the word corresponding to a bit position
161 /// \returns the corresponding word for the specified bit position.
162 uint64_t getWord(unsigned bitPosition) const {
163 return isSingleWord() ? U.VAL : U.pVal[whichWord(bitPosition)];
164 }
165
166 /// Utility method to change the bit width of this APInt to new bit width,
167 /// allocating and/or deallocating as necessary. There is no guarantee on the
168 /// value of any bits upon return. Caller should populate the bits after.
169 void reallocate(unsigned NewBitWidth);
170
171 /// Convert a char array into an APInt
172 ///
173 /// \param radix 2, 8, 10, 16, or 36
174 /// Converts a string into a number. The string must be non-empty
175 /// and well-formed as a number of the given base. The bit-width
176 /// must be sufficient to hold the result.
177 ///
178 /// This is used by the constructors that take string arguments.
179 ///
180 /// StringRef::getAsInteger is superficially similar but (1) does
181 /// not assume that the string is well-formed and (2) grows the
182 /// result to hold the input.
183 void fromString(unsigned numBits, StringRef str, uint8_t radix);
184
185 /// An internal division function for dividing APInts.
186 ///
187 /// This is used by the toString method to divide by the radix. It simply
188 /// provides a more convenient form of divide for internal use since KnuthDiv
189 /// has specific constraints on its inputs. If those constraints are not met
190 /// then it provides a simpler form of divide.
191 static void divide(const WordType *LHS, unsigned lhsWords,
192 const WordType *RHS, unsigned rhsWords, WordType *Quotient,
193 WordType *Remainder);
194
195 /// out-of-line slow case for inline constructor
196 void initSlowCase(uint64_t val, bool isSigned);
197
198 /// shared code between two array constructors
199 void initFromArray(ArrayRef<uint64_t> array);
200
201 /// out-of-line slow case for inline copy constructor
202 void initSlowCase(const APInt &that);
203
204 /// out-of-line slow case for shl
205 void shlSlowCase(unsigned ShiftAmt);
206
207 /// out-of-line slow case for lshr.
208 void lshrSlowCase(unsigned ShiftAmt);
209
210 /// out-of-line slow case for ashr.
211 void ashrSlowCase(unsigned ShiftAmt);
212
213 /// out-of-line slow case for operator=
214 void AssignSlowCase(const APInt &RHS);
215
216 /// out-of-line slow case for operator==
217 bool EqualSlowCase(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__));
218
219 /// out-of-line slow case for countLeadingZeros
220 unsigned countLeadingZerosSlowCase() const LLVM_READONLY__attribute__((__pure__));
221
222 /// out-of-line slow case for countLeadingOnes.
223 unsigned countLeadingOnesSlowCase() const LLVM_READONLY__attribute__((__pure__));
224
225 /// out-of-line slow case for countTrailingZeros.
226 unsigned countTrailingZerosSlowCase() const LLVM_READONLY__attribute__((__pure__));
227
228 /// out-of-line slow case for countTrailingOnes
229 unsigned countTrailingOnesSlowCase() const LLVM_READONLY__attribute__((__pure__));
230
231 /// out-of-line slow case for countPopulation
232 unsigned countPopulationSlowCase() const LLVM_READONLY__attribute__((__pure__));
233
234 /// out-of-line slow case for intersects.
235 bool intersectsSlowCase(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__));
236
237 /// out-of-line slow case for isSubsetOf.
238 bool isSubsetOfSlowCase(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__));
239
240 /// out-of-line slow case for setBits.
241 void setBitsSlowCase(unsigned loBit, unsigned hiBit);
242
243 /// out-of-line slow case for flipAllBits.
244 void flipAllBitsSlowCase();
245
246 /// out-of-line slow case for operator&=.
247 void AndAssignSlowCase(const APInt& RHS);
248
249 /// out-of-line slow case for operator|=.
250 void OrAssignSlowCase(const APInt& RHS);
251
252 /// out-of-line slow case for operator^=.
253 void XorAssignSlowCase(const APInt& RHS);
254
255 /// Unsigned comparison. Returns -1, 0, or 1 if this APInt is less than, equal
256 /// to, or greater than RHS.
257 int compare(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__));
258
259 /// Signed comparison. Returns -1, 0, or 1 if this APInt is less than, equal
260 /// to, or greater than RHS.
261 int compareSigned(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__));
262
263public:
264 /// \name Constructors
265 /// @{
266
267 /// Create a new APInt of numBits width, initialized as val.
268 ///
269 /// If isSigned is true then val is treated as if it were a signed value
270 /// (i.e. as an int64_t) and the appropriate sign extension to the bit width
271 /// will be done. Otherwise, no sign extension occurs (high order bits beyond
272 /// the range of val are zero filled).
273 ///
274 /// \param numBits the bit width of the constructed APInt
275 /// \param val the initial value of the APInt
276 /// \param isSigned how to treat signedness of val
277 APInt(unsigned numBits, uint64_t val, bool isSigned = false)
278 : BitWidth(numBits) {
279 assert(BitWidth && "bitwidth too small")((BitWidth && "bitwidth too small") ? static_cast<
void> (0) : __assert_fail ("BitWidth && \"bitwidth too small\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/ADT/APInt.h"
, 279, __PRETTY_FUNCTION__))
;
280 if (isSingleWord()) {
281 U.VAL = val;
282 clearUnusedBits();
283 } else {
284 initSlowCase(val, isSigned);
285 }
286 }
287
288 /// Construct an APInt of numBits width, initialized as bigVal[].
289 ///
290 /// Note that bigVal.size() can be smaller or larger than the corresponding
291 /// bit width but any extraneous bits will be dropped.
292 ///
293 /// \param numBits the bit width of the constructed APInt
294 /// \param bigVal a sequence of words to form the initial value of the APInt
295 APInt(unsigned numBits, ArrayRef<uint64_t> bigVal);
296
297 /// Equivalent to APInt(numBits, ArrayRef<uint64_t>(bigVal, numWords)), but
298 /// deprecated because this constructor is prone to ambiguity with the
299 /// APInt(unsigned, uint64_t, bool) constructor.
300 ///
301 /// If this overload is ever deleted, care should be taken to prevent calls
302 /// from being incorrectly captured by the APInt(unsigned, uint64_t, bool)
303 /// constructor.
304 APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[]);
305
306 /// Construct an APInt from a string representation.
307 ///
308 /// This constructor interprets the string \p str in the given radix. The
309 /// interpretation stops when the first character that is not suitable for the
310 /// radix is encountered, or the end of the string. Acceptable radix values
311 /// are 2, 8, 10, 16, and 36. It is an error for the value implied by the
312 /// string to require more bits than numBits.
313 ///
314 /// \param numBits the bit width of the constructed APInt
315 /// \param str the string to be interpreted
316 /// \param radix the radix to use for the conversion
317 APInt(unsigned numBits, StringRef str, uint8_t radix);
318
319 /// Simply makes *this a copy of that.
320 /// Copy Constructor.
321 APInt(const APInt &that) : BitWidth(that.BitWidth) {
322 if (isSingleWord())
8
Taking false branch
323 U.VAL = that.U.VAL;
324 else
325 initSlowCase(that);
9
Calling 'APInt::initSlowCase'
13
Returned allocated memory
326 }
327
328 /// Move Constructor.
329 APInt(APInt &&that) : BitWidth(that.BitWidth) {
330 memcpy(&U, &that.U, sizeof(U));
331 that.BitWidth = 0;
332 }
333
334 /// Destructor.
335 ~APInt() {
336 if (needsCleanup())
337 delete[] U.pVal;
338 }
339
340 /// Default constructor that creates an uninteresting APInt
341 /// representing a 1-bit zero value.
342 ///
343 /// This is useful for object deserialization (pair this with the static
344 /// method Read).
345 explicit APInt() : BitWidth(1) { U.VAL = 0; }
346
347 /// Returns whether this instance allocated memory.
348 bool needsCleanup() const { return !isSingleWord(); }
349
350 /// Used to insert APInt objects, or objects that contain APInt objects, into
351 /// FoldingSets.
352 void Profile(FoldingSetNodeID &id) const;
353
354 /// @}
355 /// \name Value Tests
356 /// @{
357
358 /// Determine sign of this APInt.
359 ///
360 /// This tests the high bit of this APInt to determine if it is set.
361 ///
362 /// \returns true if this APInt is negative, false otherwise
363 bool isNegative() const { return (*this)[BitWidth - 1]; }
364
365 /// Determine if this APInt Value is non-negative (>= 0)
366 ///
367 /// This tests the high bit of the APInt to determine if it is unset.
368 bool isNonNegative() const { return !isNegative(); }
369
370 /// Determine if sign bit of this APInt is set.
371 ///
372 /// This tests the high bit of this APInt to determine if it is set.
373 ///
374 /// \returns true if this APInt has its sign bit set, false otherwise.
375 bool isSignBitSet() const { return (*this)[BitWidth-1]; }
376
377 /// Determine if sign bit of this APInt is clear.
378 ///
379 /// This tests the high bit of this APInt to determine if it is clear.
380 ///
381 /// \returns true if this APInt has its sign bit clear, false otherwise.
382 bool isSignBitClear() const { return !isSignBitSet(); }
383
384 /// Determine if this APInt Value is positive.
385 ///
386 /// This tests if the value of this APInt is positive (> 0). Note
387 /// that 0 is not a positive value.
388 ///
389 /// \returns true if this APInt is positive.
390 bool isStrictlyPositive() const { return isNonNegative() && !isNullValue(); }
391
392 /// Determine if this APInt Value is non-positive (<= 0).
393 ///
394 /// \returns true if this APInt is non-positive.
395 bool isNonPositive() const { return !isStrictlyPositive(); }
396
397 /// Determine if all bits are set
398 ///
399 /// This checks to see if the value has all bits of the APInt are set or not.
400 bool isAllOnesValue() const {
401 if (isSingleWord())
402 return U.VAL == WORDTYPE_MAX >> (APINT_BITS_PER_WORD - BitWidth);
403 return countTrailingOnesSlowCase() == BitWidth;
404 }
405
406 /// Determine if all bits are clear
407 ///
408 /// This checks to see if the value has all bits of the APInt are clear or
409 /// not.
410 bool isNullValue() const { return !*this; }
411
412 /// Determine if this is a value of 1.
413 ///
414 /// This checks to see if the value of this APInt is one.
415 bool isOneValue() const {
416 if (isSingleWord())
417 return U.VAL == 1;
418 return countLeadingZerosSlowCase() == BitWidth - 1;
419 }
420
421 /// Determine if this is the largest unsigned value.
422 ///
423 /// This checks to see if the value of this APInt is the maximum unsigned
424 /// value for the APInt's bit width.
425 bool isMaxValue() const { return isAllOnesValue(); }
426
427 /// Determine if this is the largest signed value.
428 ///
429 /// This checks to see if the value of this APInt is the maximum signed
430 /// value for the APInt's bit width.
431 bool isMaxSignedValue() const {
432 if (isSingleWord())
433 return U.VAL == ((WordType(1) << (BitWidth - 1)) - 1);
434 return !isNegative() && countTrailingOnesSlowCase() == BitWidth - 1;
435 }
436
437 /// Determine if this is the smallest unsigned value.
438 ///
439 /// This checks to see if the value of this APInt is the minimum unsigned
440 /// value for the APInt's bit width.
441 bool isMinValue() const { return isNullValue(); }
442
443 /// Determine if this is the smallest signed value.
444 ///
445 /// This checks to see if the value of this APInt is the minimum signed
446 /// value for the APInt's bit width.
447 bool isMinSignedValue() const {
448 if (isSingleWord())
449 return U.VAL == (WordType(1) << (BitWidth - 1));
450 return isNegative() && countTrailingZerosSlowCase() == BitWidth - 1;
451 }
452
453 /// Check if this APInt has an N-bits unsigned integer value.
454 bool isIntN(unsigned N) const {
455 assert(N && "N == 0 ???")((N && "N == 0 ???") ? static_cast<void> (0) : __assert_fail
("N && \"N == 0 ???\"", "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/ADT/APInt.h"
, 455, __PRETTY_FUNCTION__))
;
456 return getActiveBits() <= N;
457 }
458
459 /// Check if this APInt has an N-bits signed integer value.
460 bool isSignedIntN(unsigned N) const {
461 assert(N && "N == 0 ???")((N && "N == 0 ???") ? static_cast<void> (0) : __assert_fail
("N && \"N == 0 ???\"", "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/ADT/APInt.h"
, 461, __PRETTY_FUNCTION__))
;
462 return getMinSignedBits() <= N;
463 }
464
465 /// Check if this APInt's value is a power of two greater than zero.
466 ///
467 /// \returns true if the argument APInt value is a power of two > 0.
468 bool isPowerOf2() const {
469 if (isSingleWord())
470 return isPowerOf2_64(U.VAL);
471 return countPopulationSlowCase() == 1;
472 }
473
474 /// Check if the APInt's value is returned by getSignMask.
475 ///
476 /// \returns true if this is the value returned by getSignMask.
477 bool isSignMask() const { return isMinSignedValue(); }
478
479 /// Convert APInt to a boolean value.
480 ///
481 /// This converts the APInt to a boolean value as a test against zero.
482 bool getBoolValue() const { return !!*this; }
483
484 /// If this value is smaller than the specified limit, return it, otherwise
485 /// return the limit value. This causes the value to saturate to the limit.
486 uint64_t getLimitedValue(uint64_t Limit = UINT64_MAX(18446744073709551615UL)) const {
487 return ugt(Limit) ? Limit : getZExtValue();
488 }
489
490 /// Check if the APInt consists of a repeated bit pattern.
491 ///
492 /// e.g. 0x01010101 satisfies isSplat(8).
493 /// \param SplatSizeInBits The size of the pattern in bits. Must divide bit
494 /// width without remainder.
495 bool isSplat(unsigned SplatSizeInBits) const;
496
497 /// \returns true if this APInt value is a sequence of \param numBits ones
498 /// starting at the least significant bit with the remainder zero.
499 bool isMask(unsigned numBits) const {
500 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-11~++20200309111110+2c36c23f347/llvm/include/llvm/ADT/APInt.h"
, 500, __PRETTY_FUNCTION__))
;
501 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-11~++20200309111110+2c36c23f347/llvm/include/llvm/ADT/APInt.h"
, 501, __PRETTY_FUNCTION__))
;
502 if (isSingleWord())
503 return U.VAL == (WORDTYPE_MAX >> (APINT_BITS_PER_WORD - numBits));
504 unsigned Ones = countTrailingOnesSlowCase();
505 return (numBits == Ones) &&
506 ((Ones + countLeadingZerosSlowCase()) == BitWidth);
507 }
508
509 /// \returns true if this APInt is a non-empty sequence of ones starting at
510 /// the least significant bit with the remainder zero.
511 /// Ex. isMask(0x0000FFFFU) == true.
512 bool isMask() const {
513 if (isSingleWord())
514 return isMask_64(U.VAL);
515 unsigned Ones = countTrailingOnesSlowCase();
516 return (Ones > 0) && ((Ones + countLeadingZerosSlowCase()) == BitWidth);
517 }
518
519 /// Return true if this APInt value contains a sequence of ones with
520 /// the remainder zero.
521 bool isShiftedMask() const {
522 if (isSingleWord())
523 return isShiftedMask_64(U.VAL);
524 unsigned Ones = countPopulationSlowCase();
525 unsigned LeadZ = countLeadingZerosSlowCase();
526 return (Ones + LeadZ + countTrailingZeros()) == BitWidth;
527 }
528
529 /// @}
530 /// \name Value Generators
531 /// @{
532
533 /// Gets maximum unsigned value of APInt for specific bit width.
534 static APInt getMaxValue(unsigned numBits) {
535 return getAllOnesValue(numBits);
536 }
537
538 /// Gets maximum signed value of APInt for a specific bit width.
539 static APInt getSignedMaxValue(unsigned numBits) {
540 APInt API = getAllOnesValue(numBits);
541 API.clearBit(numBits - 1);
542 return API;
543 }
544
545 /// Gets minimum unsigned value of APInt for a specific bit width.
546 static APInt getMinValue(unsigned numBits) { return APInt(numBits, 0); }
547
548 /// Gets minimum signed value of APInt for a specific bit width.
549 static APInt getSignedMinValue(unsigned numBits) {
550 APInt API(numBits, 0);
551 API.setBit(numBits - 1);
552 return API;
553 }
554
555 /// Get the SignMask for a specific bit width.
556 ///
557 /// This is just a wrapper function of getSignedMinValue(), and it helps code
558 /// readability when we want to get a SignMask.
559 static APInt getSignMask(unsigned BitWidth) {
560 return getSignedMinValue(BitWidth);
561 }
562
563 /// Get the all-ones value.
564 ///
565 /// \returns the all-ones value for an APInt of the specified bit-width.
566 static APInt getAllOnesValue(unsigned numBits) {
567 return APInt(numBits, WORDTYPE_MAX, true);
568 }
569
570 /// Get the '0' value.
571 ///
572 /// \returns the '0' value for an APInt of the specified bit-width.
573 static APInt getNullValue(unsigned numBits) { return APInt(numBits, 0); }
574
575 /// Compute an APInt containing numBits highbits from this APInt.
576 ///
577 /// Get an APInt with the same BitWidth as this APInt, just zero mask
578 /// the low bits and right shift to the least significant bit.
579 ///
580 /// \returns the high "numBits" bits of this APInt.
581 APInt getHiBits(unsigned numBits) const;
582
583 /// Compute an APInt containing numBits lowbits from this APInt.
584 ///
585 /// Get an APInt with the same BitWidth as this APInt, just zero mask
586 /// the high bits.
587 ///
588 /// \returns the low "numBits" bits of this APInt.
589 APInt getLoBits(unsigned numBits) const;
590
591 /// Return an APInt with exactly one bit set in the result.
592 static APInt getOneBitSet(unsigned numBits, unsigned BitNo) {
593 APInt Res(numBits, 0);
594 Res.setBit(BitNo);
595 return Res;
596 }
597
598 /// Get a value with a block of bits set.
599 ///
600 /// Constructs an APInt value that has a contiguous range of bits set. The
601 /// bits from loBit (inclusive) to hiBit (exclusive) will be set. All other
602 /// bits will be zero. For example, with parameters(32, 0, 16) you would get
603 /// 0x0000FFFF. Please call getBitsSetWithWrap if \p loBit may be greater than
604 /// \p hiBit.
605 ///
606 /// \param numBits the intended bit width of the result
607 /// \param loBit the index of the lowest bit set.
608 /// \param hiBit the index of the highest bit set.
609 ///
610 /// \returns An APInt value with the requested bits set.
611 static APInt getBitsSet(unsigned numBits, unsigned loBit, unsigned hiBit) {
612 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-11~++20200309111110+2c36c23f347/llvm/include/llvm/ADT/APInt.h"
, 612, __PRETTY_FUNCTION__))
;
613 APInt Res(numBits, 0);
614 Res.setBits(loBit, hiBit);
615 return Res;
616 }
617
618 /// Wrap version of getBitsSet.
619 /// If \p hiBit is no less than \p loBit, this is same with getBitsSet.
620 /// If \p hiBit is less than \p loBit, the set bits "wrap". For example, with
621 /// parameters (32, 28, 4), you would get 0xF000000F.
622 static APInt getBitsSetWithWrap(unsigned numBits, unsigned loBit,
623 unsigned hiBit) {
624 APInt Res(numBits, 0);
625 Res.setBitsWithWrap(loBit, hiBit);
626 return Res;
627 }
628
629 /// Get a value with upper bits starting at loBit set.
630 ///
631 /// Constructs an APInt value that has a contiguous range of bits set. The
632 /// bits from loBit (inclusive) to numBits (exclusive) will be set. All other
633 /// bits will be zero. For example, with parameters(32, 12) you would get
634 /// 0xFFFFF000.
635 ///
636 /// \param numBits the intended bit width of the result
637 /// \param loBit the index of the lowest bit to set.
638 ///
639 /// \returns An APInt value with the requested bits set.
640 static APInt getBitsSetFrom(unsigned numBits, unsigned loBit) {
641 APInt Res(numBits, 0);
642 Res.setBitsFrom(loBit);
643 return Res;
644 }
645
646 /// Get a value with high bits set
647 ///
648 /// Constructs an APInt value that has the top hiBitsSet bits set.
649 ///
650 /// \param numBits the bitwidth of the result
651 /// \param hiBitsSet the number of high-order bits set in the result.
652 static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet) {
653 APInt Res(numBits, 0);
654 Res.setHighBits(hiBitsSet);
655 return Res;
656 }
657
658 /// Get a value with low bits set
659 ///
660 /// Constructs an APInt value that has the bottom loBitsSet bits set.
661 ///
662 /// \param numBits the bitwidth of the result
663 /// \param loBitsSet the number of low-order bits set in the result.
664 static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet) {
665 APInt Res(numBits, 0);
666 Res.setLowBits(loBitsSet);
667 return Res;
668 }
669
670 /// Return a value containing V broadcasted over NewLen bits.
671 static APInt getSplat(unsigned NewLen, const APInt &V);
672
673 /// Determine if two APInts have the same value, after zero-extending
674 /// one of them (if needed!) to ensure that the bit-widths match.
675 static bool isSameValue(const APInt &I1, const APInt &I2) {
676 if (I1.getBitWidth() == I2.getBitWidth())
677 return I1 == I2;
678
679 if (I1.getBitWidth() > I2.getBitWidth())
680 return I1 == I2.zext(I1.getBitWidth());
681
682 return I1.zext(I2.getBitWidth()) == I2;
683 }
684
685 /// Overload to compute a hash_code for an APInt value.
686 friend hash_code hash_value(const APInt &Arg);
687
688 /// This function returns a pointer to the internal storage of the APInt.
689 /// This is useful for writing out the APInt in binary form without any
690 /// conversions.
691 const uint64_t *getRawData() const {
692 if (isSingleWord())
693 return &U.VAL;
694 return &U.pVal[0];
695 }
696
697 /// @}
698 /// \name Unary Operators
699 /// @{
700
701 /// Postfix increment operator.
702 ///
703 /// Increments *this by 1.
704 ///
705 /// \returns a new APInt value representing the original value of *this.
706 const APInt operator++(int) {
707 APInt API(*this);
708 ++(*this);
709 return API;
710 }
711
712 /// Prefix increment operator.
713 ///
714 /// \returns *this incremented by one
715 APInt &operator++();
716
717 /// Postfix decrement operator.
718 ///
719 /// Decrements *this by 1.
720 ///
721 /// \returns a new APInt value representing the original value of *this.
722 const APInt operator--(int) {
723 APInt API(*this);
724 --(*this);
725 return API;
726 }
727
728 /// Prefix decrement operator.
729 ///
730 /// \returns *this decremented by one.
731 APInt &operator--();
732
733 /// Logical negation operator.
734 ///
735 /// Performs logical negation operation on this APInt.
736 ///
737 /// \returns true if *this is zero, false otherwise.
738 bool operator!() const {
739 if (isSingleWord())
740 return U.VAL == 0;
741 return countLeadingZerosSlowCase() == BitWidth;
742 }
743
744 /// @}
745 /// \name Assignment Operators
746 /// @{
747
748 /// Copy assignment operator.
749 ///
750 /// \returns *this after assignment of RHS.
751 APInt &operator=(const APInt &RHS) {
752 // If the bitwidths are the same, we can avoid mucking with memory
753 if (isSingleWord() && RHS.isSingleWord()) {
754 U.VAL = RHS.U.VAL;
755 BitWidth = RHS.BitWidth;
756 return clearUnusedBits();
757 }
758
759 AssignSlowCase(RHS);
760 return *this;
761 }
762
763 /// Move assignment operator.
764 APInt &operator=(APInt &&that) {
765#ifdef _MSC_VER
766 // The MSVC std::shuffle implementation still does self-assignment.
767 if (this == &that)
768 return *this;
769#endif
770 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-11~++20200309111110+2c36c23f347/llvm/include/llvm/ADT/APInt.h"
, 770, __PRETTY_FUNCTION__))
;
24
'?' condition is true
771 if (!isSingleWord())
25
Taking true branch
772 delete[] U.pVal;
26
Memory is released
773
774 // Use memcpy so that type based alias analysis sees both VAL and pVal
775 // as modified.
776 memcpy(&U, &that.U, sizeof(U));
777
778 BitWidth = that.BitWidth;
779 that.BitWidth = 0;
780
781 return *this;
782 }
783
784 /// Assignment operator.
785 ///
786 /// The RHS value is assigned to *this. If the significant bits in RHS exceed
787 /// the bit width, the excess bits are truncated. If the bit width is larger
788 /// than 64, the value is zero filled in the unspecified high order bits.
789 ///
790 /// \returns *this after assignment of RHS value.
791 APInt &operator=(uint64_t RHS) {
792 if (isSingleWord()) {
793 U.VAL = RHS;
794 clearUnusedBits();
795 } else {
796 U.pVal[0] = RHS;
797 memset(U.pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE);
798 }
799 return *this;
800 }
801
802 /// Bitwise AND assignment operator.
803 ///
804 /// Performs a bitwise AND operation on this APInt and RHS. The result is
805 /// assigned to *this.
806 ///
807 /// \returns *this after ANDing with RHS.
808 APInt &operator&=(const APInt &RHS) {
809 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-11~++20200309111110+2c36c23f347/llvm/include/llvm/ADT/APInt.h"
, 809, __PRETTY_FUNCTION__))
;
810 if (isSingleWord())
811 U.VAL &= RHS.U.VAL;
812 else
813 AndAssignSlowCase(RHS);
814 return *this;
815 }
816
817 /// Bitwise AND assignment operator.
818 ///
819 /// Performs a bitwise AND operation on this APInt and RHS. RHS is
820 /// logically zero-extended or truncated to match the bit-width of
821 /// the LHS.
822 APInt &operator&=(uint64_t RHS) {
823 if (isSingleWord()) {
824 U.VAL &= RHS;
825 return *this;
826 }
827 U.pVal[0] &= RHS;
828 memset(U.pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE);
829 return *this;
830 }
831
832 /// Bitwise OR assignment operator.
833 ///
834 /// Performs a bitwise OR operation on this APInt and RHS. The result is
835 /// assigned *this;
836 ///
837 /// \returns *this after ORing with RHS.
838 APInt &operator|=(const APInt &RHS) {
839 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-11~++20200309111110+2c36c23f347/llvm/include/llvm/ADT/APInt.h"
, 839, __PRETTY_FUNCTION__))
;
840 if (isSingleWord())
841 U.VAL |= RHS.U.VAL;
842 else
843 OrAssignSlowCase(RHS);
844 return *this;
845 }
846
847 /// Bitwise OR assignment operator.
848 ///
849 /// Performs a bitwise OR operation on this APInt and RHS. RHS is
850 /// logically zero-extended or truncated to match the bit-width of
851 /// the LHS.
852 APInt &operator|=(uint64_t RHS) {
853 if (isSingleWord()) {
854 U.VAL |= RHS;
855 clearUnusedBits();
856 } else {
857 U.pVal[0] |= RHS;
858 }
859 return *this;
860 }
861
862 /// Bitwise XOR assignment operator.
863 ///
864 /// Performs a bitwise XOR operation on this APInt and RHS. The result is
865 /// assigned to *this.
866 ///
867 /// \returns *this after XORing with RHS.
868 APInt &operator^=(const APInt &RHS) {
869 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-11~++20200309111110+2c36c23f347/llvm/include/llvm/ADT/APInt.h"
, 869, __PRETTY_FUNCTION__))
;
870 if (isSingleWord())
871 U.VAL ^= RHS.U.VAL;
872 else
873 XorAssignSlowCase(RHS);
874 return *this;
875 }
876
877 /// Bitwise XOR assignment operator.
878 ///
879 /// Performs a bitwise XOR operation on this APInt and RHS. RHS is
880 /// logically zero-extended or truncated to match the bit-width of
881 /// the LHS.
882 APInt &operator^=(uint64_t RHS) {
883 if (isSingleWord()) {
884 U.VAL ^= RHS;
885 clearUnusedBits();
886 } else {
887 U.pVal[0] ^= RHS;
888 }
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-11~++20200309111110+2c36c23f347/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-11~++20200309111110+2c36c23f347/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-11~++20200309111110+2c36c23f347/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-11~++20200309111110+2c36c23f347/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-11~++20200309111110+2c36c23f347/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-11~++20200309111110+2c36c23f347/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-11~++20200309111110+2c36c23f347/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-11~++20200309111110+2c36c23f347/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 the bits from loBit (inclusive) to hiBit (exclusive) to 1.
1451 /// This function handles "wrap" case when \p loBit > \p hiBit, and calls
1452 /// setBits when \p loBit <= \p hiBit.
1453 void setBitsWithWrap(unsigned loBit, unsigned hiBit) {
1454 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-11~++20200309111110+2c36c23f347/llvm/include/llvm/ADT/APInt.h"
, 1454, __PRETTY_FUNCTION__))
;
1455 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-11~++20200309111110+2c36c23f347/llvm/include/llvm/ADT/APInt.h"
, 1455, __PRETTY_FUNCTION__))
;
1456 if (loBit <= hiBit) {
1457 setBits(loBit, hiBit);
1458 return;
1459 }
1460 setLowBits(hiBit);
1461 setHighBits(BitWidth - loBit);
1462 }
1463
1464 /// Set the bits from loBit (inclusive) to hiBit (exclusive) to 1.
1465 /// This function handles case when \p loBit <= \p hiBit.
1466 void setBits(unsigned loBit, unsigned hiBit) {
1467 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-11~++20200309111110+2c36c23f347/llvm/include/llvm/ADT/APInt.h"
, 1467, __PRETTY_FUNCTION__))
;
1468 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-11~++20200309111110+2c36c23f347/llvm/include/llvm/ADT/APInt.h"
, 1468, __PRETTY_FUNCTION__))
;
1469 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-11~++20200309111110+2c36c23f347/llvm/include/llvm/ADT/APInt.h"
, 1469, __PRETTY_FUNCTION__))
;
1470 if (loBit == hiBit)
1471 return;
1472 if (loBit < APINT_BITS_PER_WORD && hiBit <= APINT_BITS_PER_WORD) {
1473 uint64_t mask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - (hiBit - loBit));
1474 mask <<= loBit;
1475 if (isSingleWord())
1476 U.VAL |= mask;
1477 else
1478 U.pVal[0] |= mask;
1479 } else {
1480 setBitsSlowCase(loBit, hiBit);
1481 }
1482 }
1483
1484 /// Set the top bits starting from loBit.
1485 void setBitsFrom(unsigned loBit) {
1486 return setBits(loBit, BitWidth);
1487 }
1488
1489 /// Set the bottom loBits bits.
1490 void setLowBits(unsigned loBits) {
1491 return setBits(0, loBits);
1492 }
1493
1494 /// Set the top hiBits bits.
1495 void setHighBits(unsigned hiBits) {
1496 return setBits(BitWidth - hiBits, BitWidth);
1497 }
1498
1499 /// Set every bit to 0.
1500 void clearAllBits() {
1501 if (isSingleWord())
1502 U.VAL = 0;
1503 else
1504 memset(U.pVal, 0, getNumWords() * APINT_WORD_SIZE);
1505 }
1506
1507 /// Set a given bit to 0.
1508 ///
1509 /// Set the given bit to 0 whose position is given as "bitPosition".
1510 void clearBit(unsigned BitPosition) {
1511 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-11~++20200309111110+2c36c23f347/llvm/include/llvm/ADT/APInt.h"
, 1511, __PRETTY_FUNCTION__))
;
1512 WordType Mask = ~maskBit(BitPosition);
1513 if (isSingleWord())
1514 U.VAL &= Mask;
1515 else
1516 U.pVal[whichWord(BitPosition)] &= Mask;
1517 }
1518
1519 /// Set bottom loBits bits to 0.
1520 void clearLowBits(unsigned loBits) {
1521 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-11~++20200309111110+2c36c23f347/llvm/include/llvm/ADT/APInt.h"
, 1521, __PRETTY_FUNCTION__))
;
1522 APInt Keep = getHighBitsSet(BitWidth, BitWidth - loBits);
1523 *this &= Keep;
1524 }
1525
1526 /// Set the sign bit to 0.
1527 void clearSignBit() {
1528 clearBit(BitWidth - 1);
1529 }
1530
1531 /// Toggle every bit to its opposite value.
1532 void flipAllBits() {
1533 if (isSingleWord()) {
1534 U.VAL ^= WORDTYPE_MAX;
1535 clearUnusedBits();
1536 } else {
1537 flipAllBitsSlowCase();
1538 }
1539 }
1540
1541 /// Toggles a given bit to its opposite value.
1542 ///
1543 /// Toggle a given bit to its opposite value whose position is given
1544 /// as "bitPosition".
1545 void flipBit(unsigned bitPosition);
1546
1547 /// Negate this APInt in place.
1548 void negate() {
1549 flipAllBits();
1550 ++(*this);
1551 }
1552
1553 /// Insert the bits from a smaller APInt starting at bitPosition.
1554 void insertBits(const APInt &SubBits, unsigned bitPosition);
1555 void insertBits(uint64_t SubBits, unsigned bitPosition, unsigned numBits);
1556
1557 /// Return an APInt with the extracted bits [bitPosition,bitPosition+numBits).
1558 APInt extractBits(unsigned numBits, unsigned bitPosition) const;
1559 uint64_t extractBitsAsZExtValue(unsigned numBits, unsigned bitPosition) const;
1560
1561 /// @}
1562 /// \name Value Characterization Functions
1563 /// @{
1564
1565 /// Return the number of bits in the APInt.
1566 unsigned getBitWidth() const { return BitWidth; }
1567
1568 /// Get the number of words.
1569 ///
1570 /// Here one word's bitwidth equals to that of uint64_t.
1571 ///
1572 /// \returns the number of words to hold the integer value of this APInt.
1573 unsigned getNumWords() const { return getNumWords(BitWidth); }
1574
1575 /// Get the number of words.
1576 ///
1577 /// *NOTE* Here one word's bitwidth equals to that of uint64_t.
1578 ///
1579 /// \returns the number of words to hold the integer value with a given bit
1580 /// width.
1581 static unsigned getNumWords(unsigned BitWidth) {
1582 return ((uint64_t)BitWidth + APINT_BITS_PER_WORD - 1) / APINT_BITS_PER_WORD;
1583 }
1584
1585 /// Compute the number of active bits in the value
1586 ///
1587 /// This function returns the number of active bits which is defined as the
1588 /// bit width minus the number of leading zeros. This is used in several
1589 /// computations to see how "wide" the value is.
1590 unsigned getActiveBits() const { return BitWidth - countLeadingZeros(); }
1591
1592 /// Compute the number of active words in the value of this APInt.
1593 ///
1594 /// This is used in conjunction with getActiveData to extract the raw value of
1595 /// the APInt.
1596 unsigned getActiveWords() const {
1597 unsigned numActiveBits = getActiveBits();
1598 return numActiveBits ? whichWord(numActiveBits - 1) + 1 : 1;
1599 }
1600
1601 /// Get the minimum bit size for this signed APInt
1602 ///
1603 /// Computes the minimum bit width for this APInt while considering it to be a
1604 /// signed (and probably negative) value. If the value is not negative, this
1605 /// function returns the same value as getActiveBits()+1. Otherwise, it
1606 /// returns the smallest bit width that will retain the negative value. For
1607 /// example, -1 can be written as 0b1 or 0xFFFFFFFFFF. 0b1 is shorter and so
1608 /// for -1, this function will always return 1.
1609 unsigned getMinSignedBits() const {
1610 if (isNegative())
1611 return BitWidth - countLeadingOnes() + 1;
1612 return getActiveBits() + 1;
1613 }
1614
1615 /// Get zero extended value
1616 ///
1617 /// This method attempts to return the value of this APInt as a zero extended
1618 /// uint64_t. The bitwidth must be <= 64 or the value must fit within a
1619 /// uint64_t. Otherwise an assertion will result.
1620 uint64_t getZExtValue() const {
1621 if (isSingleWord())
1622 return U.VAL;
1623 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-11~++20200309111110+2c36c23f347/llvm/include/llvm/ADT/APInt.h"
, 1623, __PRETTY_FUNCTION__))
;
1624 return U.pVal[0];
1625 }
1626
1627 /// Get sign extended value
1628 ///
1629 /// This method attempts to return the value of this APInt as a sign extended
1630 /// int64_t. The bit width must be <= 64 or the value must fit within an
1631 /// int64_t. Otherwise an assertion will result.
1632 int64_t getSExtValue() const {
1633 if (isSingleWord())
1634 return SignExtend64(U.VAL, BitWidth);
1635 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-11~++20200309111110+2c36c23f347/llvm/include/llvm/ADT/APInt.h"
, 1635, __PRETTY_FUNCTION__))
;
1636 return int64_t(U.pVal[0]);
1637 }
1638
1639 /// Get bits required for string value.
1640 ///
1641 /// This method determines how many bits are required to hold the APInt
1642 /// equivalent of the string given by \p str.
1643 static unsigned getBitsNeeded(StringRef str, uint8_t radix);
1644
1645 /// The APInt version of the countLeadingZeros functions in
1646 /// MathExtras.h.
1647 ///
1648 /// It counts the number of zeros from the most significant bit to the first
1649 /// one bit.
1650 ///
1651 /// \returns BitWidth if the value is zero, otherwise returns the number of
1652 /// zeros from the most significant bit to the first one bits.
1653 unsigned countLeadingZeros() const {
1654 if (isSingleWord()) {
1655 unsigned unusedBits = APINT_BITS_PER_WORD - BitWidth;
1656 return llvm::countLeadingZeros(U.VAL) - unusedBits;
1657 }
1658 return countLeadingZerosSlowCase();
1659 }
1660
1661 /// Count the number of leading one bits.
1662 ///
1663 /// This function is an APInt version of the countLeadingOnes
1664 /// functions in MathExtras.h. It counts the number of ones from the most
1665 /// significant bit to the first zero bit.
1666 ///
1667 /// \returns 0 if the high order bit is not set, otherwise returns the number
1668 /// of 1 bits from the most significant to the least
1669 unsigned countLeadingOnes() const {
1670 if (isSingleWord())
1671 return llvm::countLeadingOnes(U.VAL << (APINT_BITS_PER_WORD - BitWidth));
1672 return countLeadingOnesSlowCase();
1673 }
1674
1675 /// Computes the number of leading bits of this APInt that are equal to its
1676 /// sign bit.
1677 unsigned getNumSignBits() const {
1678 return isNegative() ? countLeadingOnes() : countLeadingZeros();
1679 }
1680
1681 /// Count the number of trailing zero bits.
1682 ///
1683 /// This function is an APInt version of the countTrailingZeros
1684 /// functions in MathExtras.h. It counts the number of zeros from the least
1685 /// significant bit to the first set bit.
1686 ///
1687 /// \returns BitWidth if the value is zero, otherwise returns the number of
1688 /// zeros from the least significant bit to the first one bit.
1689 unsigned countTrailingZeros() const {
1690 if (isSingleWord())
1691 return std::min(unsigned(llvm::countTrailingZeros(U.VAL)), BitWidth);
1692 return countTrailingZerosSlowCase();
1693 }
1694
1695 /// Count the number of trailing one bits.
1696 ///
1697 /// This function is an APInt version of the countTrailingOnes
1698 /// functions in MathExtras.h. It counts the number of ones from the least
1699 /// significant bit to the first zero bit.
1700 ///
1701 /// \returns BitWidth if the value is all ones, otherwise returns the number
1702 /// of ones from the least significant bit to the first zero bit.
1703 unsigned countTrailingOnes() const {
1704 if (isSingleWord())
1705 return llvm::countTrailingOnes(U.VAL);
1706 return countTrailingOnesSlowCase();
1707 }
1708
1709 /// Count the number of bits set.
1710 ///
1711 /// This function is an APInt version of the countPopulation functions
1712 /// in MathExtras.h. It counts the number of 1 bits in the APInt value.
1713 ///
1714 /// \returns 0 if the value is zero, otherwise returns the number of set bits.
1715 unsigned countPopulation() const {
1716 if (isSingleWord())
1717 return llvm::countPopulation(U.VAL);
1718 return countPopulationSlowCase();
1719 }
1720
1721 /// @}
1722 /// \name Conversion Functions
1723 /// @{
1724 void print(raw_ostream &OS, bool isSigned) const;
1725
1726 /// Converts an APInt to a string and append it to Str. Str is commonly a
1727 /// SmallString.
1728 void toString(SmallVectorImpl<char> &Str, unsigned Radix, bool Signed,
1729 bool formatAsCLiteral = false) const;
1730
1731 /// Considers the APInt to be unsigned and converts it into a string in the
1732 /// radix given. The radix can be 2, 8, 10 16, or 36.
1733 void toStringUnsigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const {
1734 toString(Str, Radix, false, false);
2
Calling 'APInt::toString'
1735 }
1736
1737 /// Considers the APInt to be signed and converts it into a string in the
1738 /// radix given. The radix can be 2, 8, 10, 16, or 36.
1739 void toStringSigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const {
1740 toString(Str, Radix, true, false);
1741 }
1742
1743 /// Return the APInt as a std::string.
1744 ///
1745 /// Note that this is an inefficient method. It is better to pass in a
1746 /// SmallVector/SmallString to the methods above to avoid thrashing the heap
1747 /// for the string.
1748 std::string toString(unsigned Radix, bool Signed) const;
1749
1750 /// \returns a byte-swapped representation of this APInt Value.
1751 APInt byteSwap() const;
1752
1753 /// \returns the value with the bit representation reversed of this APInt
1754 /// Value.
1755 APInt reverseBits() const;
1756
1757 /// Converts this APInt to a double value.
1758 double roundToDouble(bool isSigned) const;
1759
1760 /// Converts this unsigned APInt to a double value.
1761 double roundToDouble() const { return roundToDouble(false); }
1762
1763 /// Converts this signed APInt to a double value.
1764 double signedRoundToDouble() const { return roundToDouble(true); }
1765
1766 /// Converts APInt bits to a double
1767 ///
1768 /// The conversion does not do a translation from integer to double, it just
1769 /// re-interprets the bits as a double. Note that it is valid to do this on
1770 /// any bit width. Exactly 64 bits will be translated.
1771 double bitsToDouble() const {
1772 return BitsToDouble(getWord(0));
1773 }
1774
1775 /// Converts APInt bits to a float
1776 ///
1777 /// The conversion does not do a translation from integer to float, it just
1778 /// re-interprets the bits as a float. Note that it is valid to do this on
1779 /// any bit width. Exactly 32 bits will be translated.
1780 float bitsToFloat() const {
1781 return BitsToFloat(static_cast<uint32_t>(getWord(0)));
1782 }
1783
1784 /// Converts a double to APInt bits.
1785 ///
1786 /// The conversion does not do a translation from double to integer, it just
1787 /// re-interprets the bits of the double.
1788 static APInt doubleToBits(double V) {
1789 return APInt(sizeof(double) * CHAR_BIT8, DoubleToBits(V));
1790 }
1791
1792 /// Converts a float to APInt bits.
1793 ///
1794 /// The conversion does not do a translation from float to integer, it just
1795 /// re-interprets the bits of the float.
1796 static APInt floatToBits(float V) {
1797 return APInt(sizeof(float) * CHAR_BIT8, FloatToBits(V));
1798 }
1799
1800 /// @}
1801 /// \name Mathematics Operations
1802 /// @{
1803
1804 /// \returns the floor log base 2 of this APInt.
1805 unsigned logBase2() const { return getActiveBits() - 1; }
1806
1807 /// \returns the ceil log base 2 of this APInt.
1808 unsigned ceilLogBase2() const {
1809 APInt temp(*this);
1810 --temp;
1811 return temp.getActiveBits();
1812 }
1813
1814 /// \returns the nearest log base 2 of this APInt. Ties round up.
1815 ///
1816 /// NOTE: When we have a BitWidth of 1, we define:
1817 ///
1818 /// log2(0) = UINT32_MAX
1819 /// log2(1) = 0
1820 ///
1821 /// to get around any mathematical concerns resulting from
1822 /// referencing 2 in a space where 2 does no exist.
1823 unsigned nearestLogBase2() const {
1824 // Special case when we have a bitwidth of 1. If VAL is 1, then we
1825 // get 0. If VAL is 0, we get WORDTYPE_MAX which gets truncated to
1826 // UINT32_MAX.
1827 if (BitWidth == 1)
1828 return U.VAL - 1;
1829
1830 // Handle the zero case.
1831 if (isNullValue())
1832 return UINT32_MAX(4294967295U);
1833
1834 // The non-zero case is handled by computing:
1835 //
1836 // nearestLogBase2(x) = logBase2(x) + x[logBase2(x)-1].
1837 //
1838 // where x[i] is referring to the value of the ith bit of x.
1839 unsigned lg = logBase2();
1840 return lg + unsigned((*this)[lg - 1]);
1841 }
1842
1843 /// \returns the log base 2 of this APInt if its an exact power of two, -1
1844 /// otherwise
1845 int32_t exactLogBase2() const {
1846 if (!isPowerOf2())
1847 return -1;
1848 return logBase2();
1849 }
1850
1851 /// Compute the square root
1852 APInt sqrt() const;
1853
1854 /// Get the absolute value;
1855 ///
1856 /// If *this is < 0 then return -(*this), otherwise *this;
1857 APInt abs() const {
1858 if (isNegative())
1859 return -(*this);
1860 return *this;
1861 }
1862
1863 /// \returns the multiplicative inverse for a given modulo.
1864 APInt multiplicativeInverse(const APInt &modulo) const;
1865
1866 /// @}
1867 /// \name Support for division by constant
1868 /// @{
1869
1870 /// Calculate the magic number for signed division by a constant.
1871 struct ms;
1872 ms magic() const;
1873
1874 /// Calculate the magic number for unsigned division by a constant.
1875 struct mu;
1876 mu magicu(unsigned LeadingZeros = 0) const;
1877
1878 /// @}
1879 /// \name Building-block Operations for APInt and APFloat
1880 /// @{
1881
1882 // These building block operations operate on a representation of arbitrary
1883 // precision, two's-complement, bignum integer values. They should be
1884 // sufficient to implement APInt and APFloat bignum requirements. Inputs are
1885 // generally a pointer to the base of an array of integer parts, representing
1886 // an unsigned bignum, and a count of how many parts there are.
1887
1888 /// Sets the least significant part of a bignum to the input value, and zeroes
1889 /// out higher parts.
1890 static void tcSet(WordType *, WordType, unsigned);
1891
1892 /// Assign one bignum to another.
1893 static void tcAssign(WordType *, const WordType *, unsigned);
1894
1895 /// Returns true if a bignum is zero, false otherwise.
1896 static bool tcIsZero(const WordType *, unsigned);
1897
1898 /// Extract the given bit of a bignum; returns 0 or 1. Zero-based.
1899 static int tcExtractBit(const WordType *, unsigned bit);
1900
1901 /// Copy the bit vector of width srcBITS from SRC, starting at bit srcLSB, to
1902 /// DST, of dstCOUNT parts, such that the bit srcLSB becomes the least
1903 /// significant bit of DST. All high bits above srcBITS in DST are
1904 /// zero-filled.
1905 static void tcExtract(WordType *, unsigned dstCount,
1906 const WordType *, unsigned srcBits,
1907 unsigned srcLSB);
1908
1909 /// Set the given bit of a bignum. Zero-based.
1910 static void tcSetBit(WordType *, unsigned bit);
1911
1912 /// Clear the given bit of a bignum. Zero-based.
1913 static void tcClearBit(WordType *, unsigned bit);
1914
1915 /// Returns the bit number of the least or most significant set bit of a
1916 /// number. If the input number has no bits set -1U is returned.
1917 static unsigned tcLSB(const WordType *, unsigned n);
1918 static unsigned tcMSB(const WordType *parts, unsigned n);
1919
1920 /// Negate a bignum in-place.
1921 static void tcNegate(WordType *, unsigned);
1922
1923 /// DST += RHS + CARRY where CARRY is zero or one. Returns the carry flag.
1924 static WordType tcAdd(WordType *, const WordType *,
1925 WordType carry, unsigned);
1926 /// DST += RHS. Returns the carry flag.
1927 static WordType tcAddPart(WordType *, WordType, unsigned);
1928
1929 /// DST -= RHS + CARRY where CARRY is zero or one. Returns the carry flag.
1930 static WordType tcSubtract(WordType *, const WordType *,
1931 WordType carry, unsigned);
1932 /// DST -= RHS. Returns the carry flag.
1933 static WordType tcSubtractPart(WordType *, WordType, unsigned);
1934
1935 /// DST += SRC * MULTIPLIER + PART if add is true
1936 /// DST = SRC * MULTIPLIER + PART if add is false
1937 ///
1938 /// Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC they must
1939 /// start at the same point, i.e. DST == SRC.
1940 ///
1941 /// If DSTPARTS == SRC_PARTS + 1 no overflow occurs and zero is returned.
1942 /// Otherwise DST is filled with the least significant DSTPARTS parts of the
1943 /// result, and if all of the omitted higher parts were zero return zero,
1944 /// otherwise overflow occurred and return one.
1945 static int tcMultiplyPart(WordType *dst, const WordType *src,
1946 WordType multiplier, WordType carry,
1947 unsigned srcParts, unsigned dstParts,
1948 bool add);
1949
1950 /// DST = LHS * RHS, where DST has the same width as the operands and is
1951 /// filled with the least significant parts of the result. Returns one if
1952 /// overflow occurred, otherwise zero. DST must be disjoint from both
1953 /// operands.
1954 static int tcMultiply(WordType *, const WordType *, const WordType *,
1955 unsigned);
1956
1957 /// DST = LHS * RHS, where DST has width the sum of the widths of the
1958 /// operands. No overflow occurs. DST must be disjoint from both operands.
1959 static void tcFullMultiply(WordType *, const WordType *,
1960 const WordType *, unsigned, unsigned);
1961
1962 /// If RHS is zero LHS and REMAINDER are left unchanged, return one.
1963 /// Otherwise set LHS to LHS / RHS with the fractional part discarded, set
1964 /// REMAINDER to the remainder, return zero. i.e.
1965 ///
1966 /// OLD_LHS = RHS * LHS + REMAINDER
1967 ///
1968 /// SCRATCH is a bignum of the same size as the operands and result for use by
1969 /// the routine; its contents need not be initialized and are destroyed. LHS,
1970 /// REMAINDER and SCRATCH must be distinct.
1971 static int tcDivide(WordType *lhs, const WordType *rhs,
1972 WordType *remainder, WordType *scratch,
1973 unsigned parts);
1974
1975 /// Shift a bignum left Count bits. Shifted in bits are zero. There are no
1976 /// restrictions on Count.
1977 static void tcShiftLeft(WordType *, unsigned Words, unsigned Count);
1978
1979 /// Shift a bignum right Count bits. Shifted in bits are zero. There are no
1980 /// restrictions on Count.
1981 static void tcShiftRight(WordType *, unsigned Words, unsigned Count);
1982
1983 /// The obvious AND, OR and XOR and complement operations.
1984 static void tcAnd(WordType *, const WordType *, unsigned);
1985 static void tcOr(WordType *, const WordType *, unsigned);
1986 static void tcXor(WordType *, const WordType *, unsigned);
1987 static void tcComplement(WordType *, unsigned);
1988
1989 /// Comparison (unsigned) of two bignums.
1990 static int tcCompare(const WordType *, const WordType *, unsigned);
1991
1992 /// Increment a bignum in-place. Return the carry flag.
1993 static WordType tcIncrement(WordType *dst, unsigned parts) {
1994 return tcAddPart(dst, 1, parts);
1995 }
1996
1997 /// Decrement a bignum in-place. Return the borrow flag.
1998 static WordType tcDecrement(WordType *dst, unsigned parts) {
1999 return tcSubtractPart(dst, 1, parts);
2000 }
2001
2002 /// Set the least significant BITS and clear the rest.
2003 static void tcSetLeastSignificantBits(WordType *, unsigned, unsigned bits);
2004
2005 /// debug method
2006 void dump() const;
2007
2008 /// @}
2009};
2010
2011/// Magic data for optimising signed division by a constant.
2012struct APInt::ms {
2013 APInt m; ///< magic number
2014 unsigned s; ///< shift amount
2015};
2016
2017/// Magic data for optimising unsigned division by a constant.
2018struct APInt::mu {
2019 APInt m; ///< magic number
2020 bool a; ///< add indicator
2021 unsigned s; ///< shift amount
2022};
2023
2024inline bool operator==(uint64_t V1, const APInt &V2) { return V2 == V1; }
2025
2026inline bool operator!=(uint64_t V1, const APInt &V2) { return V2 != V1; }
2027
2028/// Unary bitwise complement operator.
2029///
2030/// \returns an APInt that is the bitwise complement of \p v.
2031inline APInt operator~(APInt v) {
2032 v.flipAllBits();
2033 return v;
2034}
2035
2036inline APInt operator&(APInt a, const APInt &b) {
2037 a &= b;
2038 return a;
2039}
2040
2041inline APInt operator&(const APInt &a, APInt &&b) {
2042 b &= a;
2043 return std::move(b);
2044}
2045
2046inline APInt operator&(APInt a, uint64_t RHS) {
2047 a &= RHS;
2048 return a;
2049}
2050
2051inline APInt operator&(uint64_t LHS, APInt b) {
2052 b &= LHS;
2053 return b;
2054}
2055
2056inline APInt operator|(APInt a, const APInt &b) {
2057 a |= b;
2058 return a;
2059}
2060
2061inline APInt operator|(const APInt &a, APInt &&b) {
2062 b |= a;
2063 return std::move(b);
2064}
2065
2066inline APInt operator|(APInt a, uint64_t RHS) {
2067 a |= RHS;
2068 return a;
2069}
2070
2071inline APInt operator|(uint64_t LHS, APInt b) {
2072 b |= LHS;
2073 return b;
2074}
2075
2076inline APInt operator^(APInt a, const APInt &b) {
2077 a ^= b;
2078 return a;
2079}
2080
2081inline APInt operator^(const APInt &a, APInt &&b) {
2082 b ^= a;
2083 return std::move(b);
2084}
2085
2086inline APInt operator^(APInt a, uint64_t RHS) {
2087 a ^= RHS;
2088 return a;
2089}
2090
2091inline APInt operator^(uint64_t LHS, APInt b) {
2092 b ^= LHS;
2093 return b;
2094}
2095
2096inline raw_ostream &operator<<(raw_ostream &OS, const APInt &I) {
2097 I.print(OS, true);
2098 return OS;
2099}
2100
2101inline APInt operator-(APInt v) {
2102 v.negate();
2103 return v;
2104}
2105
2106inline APInt operator+(APInt a, const APInt &b) {
2107 a += b;
2108 return a;
2109}
2110
2111inline APInt operator+(const APInt &a, APInt &&b) {
2112 b += a;
2113 return std::move(b);
2114}
2115
2116inline APInt operator+(APInt a, uint64_t RHS) {
2117 a += RHS;
2118 return a;
2119}
2120
2121inline APInt operator+(uint64_t LHS, APInt b) {
2122 b += LHS;
2123 return b;
2124}
2125
2126inline APInt operator-(APInt a, const APInt &b) {
2127 a -= b;
2128 return a;
2129}
2130
2131inline APInt operator-(const APInt &a, APInt &&b) {
2132 b.negate();
2133 b += a;
2134 return std::move(b);
2135}
2136
2137inline APInt operator-(APInt a, uint64_t RHS) {
2138 a -= RHS;
2139 return a;
2140}
2141
2142inline APInt operator-(uint64_t LHS, APInt b) {
2143 b.negate();
2144 b += LHS;
2145 return b;
2146}
2147
2148inline APInt operator*(APInt a, uint64_t RHS) {
2149 a *= RHS;
2150 return a;
2151}
2152
2153inline APInt operator*(uint64_t LHS, APInt b) {
2154 b *= LHS;
2155 return b;
2156}
2157
2158
2159namespace APIntOps {
2160
2161/// Determine the smaller of two APInts considered to be signed.
2162inline const APInt &smin(const APInt &A, const APInt &B) {
2163 return A.slt(B) ? A : B;
2164}
2165
2166/// Determine the larger of two APInts considered to be signed.
2167inline const APInt &smax(const APInt &A, const APInt &B) {
2168 return A.sgt(B) ? A : B;
2169}
2170
2171/// Determine the smaller of two APInts considered to be signed.
2172inline const APInt &umin(const APInt &A, const APInt &B) {
2173 return A.ult(B) ? A : B;
2174}
2175
2176/// Determine the larger of two APInts considered to be unsigned.
2177inline const APInt &umax(const APInt &A, const APInt &B) {
2178 return A.ugt(B) ? A : B;
2179}
2180
2181/// Compute GCD of two unsigned APInt values.
2182///
2183/// This function returns the greatest common divisor of the two APInt values
2184/// using Stein's algorithm.
2185///
2186/// \returns the greatest common divisor of A and B.
2187APInt GreatestCommonDivisor(APInt A, APInt B);
2188
2189/// Converts the given APInt to a double value.
2190///
2191/// Treats the APInt as an unsigned value for conversion purposes.
2192inline double RoundAPIntToDouble(const APInt &APIVal) {
2193 return APIVal.roundToDouble();
2194}
2195
2196/// Converts the given APInt to a double value.
2197///
2198/// Treats the APInt as a signed value for conversion purposes.
2199inline double RoundSignedAPIntToDouble(const APInt &APIVal) {
2200 return APIVal.signedRoundToDouble();
2201}
2202
2203/// Converts the given APInt to a float vlalue.
2204inline float RoundAPIntToFloat(const APInt &APIVal) {
2205 return float(RoundAPIntToDouble(APIVal));
2206}
2207
2208/// Converts the given APInt to a float value.
2209///
2210/// Treats the APInt as a signed value for conversion purposes.
2211inline float RoundSignedAPIntToFloat(const APInt &APIVal) {
2212 return float(APIVal.signedRoundToDouble());
2213}
2214
2215/// Converts the given double value into a APInt.
2216///
2217/// This function convert a double value to an APInt value.
2218APInt RoundDoubleToAPInt(double Double, unsigned width);
2219
2220/// Converts a float value into a APInt.
2221///
2222/// Converts a float value into an APInt value.
2223inline APInt RoundFloatToAPInt(float Float, unsigned width) {
2224 return RoundDoubleToAPInt(double(Float), width);
2225}
2226
2227/// Return A unsign-divided by B, rounded by the given rounding mode.
2228APInt RoundingUDiv(const APInt &A, const APInt &B, APInt::Rounding RM);
2229
2230/// Return A sign-divided by B, rounded by the given rounding mode.
2231APInt RoundingSDiv(const APInt &A, const APInt &B, APInt::Rounding RM);
2232
2233/// Let q(n) = An^2 + Bn + C, and BW = bit width of the value range
2234/// (e.g. 32 for i32).
2235/// This function finds the smallest number n, such that
2236/// (a) n >= 0 and q(n) = 0, or
2237/// (b) n >= 1 and q(n-1) and q(n), when evaluated in the set of all
2238/// integers, belong to two different intervals [Rk, Rk+R),
2239/// where R = 2^BW, and k is an integer.
2240/// The idea here is to find when q(n) "overflows" 2^BW, while at the
2241/// same time "allowing" subtraction. In unsigned modulo arithmetic a
2242/// subtraction (treated as addition of negated numbers) would always
2243/// count as an overflow, but here we want to allow values to decrease
2244/// and increase as long as they are within the same interval.
2245/// Specifically, adding of two negative numbers should not cause an
2246/// overflow (as long as the magnitude does not exceed the bit width).
2247/// On the other hand, given a positive number, adding a negative
2248/// number to it can give a negative result, which would cause the
2249/// value to go from [-2^BW, 0) to [0, 2^BW). In that sense, zero is
2250/// treated as a special case of an overflow.
2251///
2252/// This function returns None if after finding k that minimizes the
2253/// positive solution to q(n) = kR, both solutions are contained between
2254/// two consecutive integers.
2255///
2256/// There are cases where q(n) > T, and q(n+1) < T (assuming evaluation
2257/// in arithmetic modulo 2^BW, and treating the values as signed) by the
2258/// virtue of *signed* overflow. This function will *not* find such an n,
2259/// however it may find a value of n satisfying the inequalities due to
2260/// an *unsigned* overflow (if the values are treated as unsigned).
2261/// To find a solution for a signed overflow, treat it as a problem of
2262/// finding an unsigned overflow with a range with of BW-1.
2263///
2264/// The returned value may have a different bit width from the input
2265/// coefficients.
2266Optional<APInt> SolveQuadraticEquationWrap(APInt A, APInt B, APInt C,
2267 unsigned RangeWidth);
2268
2269/// Compare two values, and if they are different, return the position of the
2270/// most significant bit that is different in the values.
2271Optional<unsigned> GetMostSignificantDifferentBit(const APInt &A,
2272 const APInt &B);
2273
2274} // End of APIntOps namespace
2275
2276// See friend declaration above. This additional declaration is required in
2277// order to compile LLVM with IBM xlC compiler.
2278hash_code hash_value(const APInt &Arg);
2279
2280/// StoreIntToMemory - Fills the StoreBytes bytes of memory starting from Dst
2281/// with the integer held in IntVal.
2282void StoreIntToMemory(const APInt &IntVal, uint8_t *Dst, unsigned StoreBytes);
2283
2284/// LoadIntFromMemory - Loads the integer stored in the LoadBytes bytes starting
2285/// from Src into IntVal, which is assumed to be wide enough and to hold zero.
2286void LoadIntFromMemory(APInt &IntVal, uint8_t *Src, unsigned LoadBytes);
2287
2288} // namespace llvm
2289
2290#endif