Bug Summary

File:lib/Support/APInt.cpp
Warning:line 1824, column 25
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 -mrelocation-model pic -pic-level 2 -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-8/lib/clang/8.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-8~svn345461/build-llvm/lib/Support -I /build/llvm-toolchain-snapshot-8~svn345461/lib/Support -I /build/llvm-toolchain-snapshot-8~svn345461/build-llvm/include -I /build/llvm-toolchain-snapshot-8~svn345461/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/include/clang/8.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-8/lib/clang/8.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++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-8~svn345461/build-llvm/lib/Support -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-10-27-211344-32123-1 -x c++ /build/llvm-toolchain-snapshot-8~svn345461/lib/Support/APInt.cpp -faddrsig

/build/llvm-toolchain-snapshot-8~svn345461/lib/Support/APInt.cpp

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

/build/llvm-toolchain-snapshot-8~svn345461/include/llvm/ADT/APInt.h

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