Bug Summary

File:lib/Support/APInt.cpp
Warning:line 199, column 5
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-eagerly-assume -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-7/lib/clang/7.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-7~svn326425/build-llvm/lib/Support -I /build/llvm-toolchain-snapshot-7~svn326425/lib/Support -I /build/llvm-toolchain-snapshot-7~svn326425/build-llvm/include -I /build/llvm-toolchain-snapshot-7~svn326425/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/x86_64-linux-gnu/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/x86_64-linux-gnu/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0/backward -internal-isystem /usr/include/clang/7.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-7/lib/clang/7.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-7~svn326425/build-llvm/lib/Support -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-checker optin.performance.Padding -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-03-01-211340-26438-1 -x c++ /build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp

/build/llvm-toolchain-snapshot-7~svn326425/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/SmallString.h"
20#include "llvm/ADT/StringRef.h"
21#include "llvm/Support/Debug.h"
22#include "llvm/Support/ErrorHandling.h"
23#include "llvm/Support/MathExtras.h"
24#include "llvm/Support/raw_ostream.h"
25#include <climits>
26#include <cmath>
27#include <cstdlib>
28#include <cstring>
29using namespace llvm;
30
31#define DEBUG_TYPE"apint" "apint"
32
33/// A utility function for allocating memory, checking for allocation failures,
34/// and ensuring the contents are zeroed.
35inline static uint64_t* getClearedMemory(unsigned numWords) {
36 uint64_t * result = new uint64_t[numWords];
9
Memory is allocated
37 assert(result && "APInt memory allocation fails!")(static_cast <bool> (result && "APInt memory allocation fails!"
) ? void (0) : __assert_fail ("result && \"APInt memory allocation fails!\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 37, __extension__ __PRETTY_FUNCTION__))
;
38 memset(result, 0, numWords * sizeof(uint64_t));
39 return result;
40}
41
42/// A utility function for allocating memory and checking for allocation
43/// failure. The content is not zeroed.
44inline static uint64_t* getMemory(unsigned numWords) {
45 uint64_t * result = new uint64_t[numWords];
46 assert(result && "APInt memory allocation fails!")(static_cast <bool> (result && "APInt memory allocation fails!"
) ? void (0) : __assert_fail ("result && \"APInt memory allocation fails!\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 46, __extension__ __PRETTY_FUNCTION__))
;
47 return result;
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());
8
Calling 'getClearedMemory'
10
Returned allocated memory
80 U.pVal[0] = val;
81 if (isSigned && int64_t(val) < 0)
82 for (unsigned i = 1; i < getNumWords(); ++i)
83 U.pVal[i] = WORD_MAX;
84 clearUnusedBits();
85}
86
87void APInt::initSlowCase(const APInt& that) {
88 U.pVal = getMemory(getNumWords());
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")(static_cast <bool> (BitWidth && "Bitwidth too small"
) ? void (0) : __assert_fail ("BitWidth && \"Bitwidth too small\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 93, __extension__ __PRETTY_FUNCTION__))
;
94 assert(bigVal.data() && "Null pointer detected!")(static_cast <bool> (bigVal.data() && "Null pointer detected!"
) ? void (0) : __assert_fail ("bigVal.data() && \"Null pointer detected!\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 94, __extension__ __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")(static_cast <bool> (BitWidth && "Bitwidth too small"
) ? void (0) : __assert_fail ("BitWidth && \"Bitwidth too small\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 121, __extension__ __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/// @brief 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/// @brief 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/// @brief Addition assignment operator.
194APInt& APInt::operator+=(const APInt& RHS) {
195 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")(static_cast <bool> (BitWidth == RHS.BitWidth &&
"Bit widths must be the same") ? void (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 195, __extension__ __PRETTY_FUNCTION__))
;
196 if (isSingleWord())
23
Taking false branch
197 U.VAL += RHS.U.VAL;
198 else
199 tcAdd(U.pVal, RHS.U.pVal, 0, getNumWords());
24
Use of memory after it is freed
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/// @brief Subtraction assignment operator.
214APInt& APInt::operator-=(const APInt& RHS) {
215 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")(static_cast <bool> (BitWidth == RHS.BitWidth &&
"Bit widths must be the same") ? void (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 215, __extension__ __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")(static_cast <bool> (BitWidth == RHS.BitWidth &&
"Bit widths must be the same") ? void (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 232, __extension__ __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")(static_cast <bool> (BitWidth == RHS.BitWidth &&
"Bit widths must be the same") ? void (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 257, __extension__ __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")(static_cast <bool> (BitWidth == RHS.BitWidth &&
"Bit widths must be same for comparison") ? void (0) : __assert_fail
("BitWidth == RHS.BitWidth && \"Bit widths must be same for comparison\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 277, __extension__ __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")(static_cast <bool> (BitWidth == RHS.BitWidth &&
"Bit widths must be same for comparison") ? void (0) : __assert_fail
("BitWidth == RHS.BitWidth && \"Bit widths must be same for comparison\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 285, __extension__ __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 = WORD_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 = WORD_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] = WORD_MAX;
329}
330
331/// @brief 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/// @brief Toggles a given bit to its opposite value.
340void APInt::flipBit(unsigned bitPosition) {
341 assert(bitPosition < BitWidth && "Out of the bit-width range!")(static_cast <bool> (bitPosition < BitWidth &&
"Out of the bit-width range!") ? void (0) : __assert_fail ("bitPosition < BitWidth && \"Out of the bit-width range!\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 341, __extension__ __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 &&(static_cast <bool> (0 < subBitWidth && (subBitWidth
+ bitPosition) <= BitWidth && "Illegal bit insertion"
) ? void (0) : __assert_fail ("0 < subBitWidth && (subBitWidth + bitPosition) <= BitWidth && \"Illegal bit insertion\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 349, __extension__ __PRETTY_FUNCTION__))
349 "Illegal bit insertion")(static_cast <bool> (0 < subBitWidth && (subBitWidth
+ bitPosition) <= BitWidth && "Illegal bit insertion"
) ? void (0) : __assert_fail ("0 < subBitWidth && (subBitWidth + bitPosition) <= BitWidth && \"Illegal bit insertion\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 349, __extension__ __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 = WORD_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 = WORD_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 = WORD_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")(static_cast <bool> (numBits > 0 && "Can't extract zero bits"
) ? void (0) : __assert_fail ("numBits > 0 && \"Can't extract zero bits\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 406, __extension__ __PRETTY_FUNCTION__))
;
407 assert(bitPosition < BitWidth && (numBits + bitPosition) <= BitWidth &&(static_cast <bool> (bitPosition < BitWidth &&
(numBits + bitPosition) <= BitWidth && "Illegal bit extraction"
) ? void (0) : __assert_fail ("bitPosition < BitWidth && (numBits + bitPosition) <= BitWidth && \"Illegal bit extraction\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 408, __extension__ __PRETTY_FUNCTION__))
408 "Illegal bit extraction")(static_cast <bool> (bitPosition < BitWidth &&
(numBits + bitPosition) <= BitWidth && "Illegal bit extraction"
) ? void (0) : __assert_fail ("bitPosition < BitWidth && (numBits + bitPosition) <= BitWidth && \"Illegal bit extraction\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 408, __extension__ __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")(static_cast <bool> (!str.empty() && "Invalid string length"
) ? void (0) : __assert_fail ("!str.empty() && \"Invalid string length\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 443, __extension__ __PRETTY_FUNCTION__))
;
444 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||(static_cast <bool> ((radix == 10 || radix == 8 || radix
== 16 || radix == 2 || radix == 36) && "Radix should be 2, 8, 10, 16, or 36!"
) ? void (0) : __assert_fail ("(radix == 10 || radix == 8 || radix == 16 || radix == 2 || radix == 36) && \"Radix should be 2, 8, 10, 16, or 36!\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 446, __extension__ __PRETTY_FUNCTION__))
445 radix == 36) &&(static_cast <bool> ((radix == 10 || radix == 8 || radix
== 16 || radix == 2 || radix == 36) && "Radix should be 2, 8, 10, 16, or 36!"
) ? void (0) : __assert_fail ("(radix == 10 || radix == 8 || radix == 16 || radix == 2 || radix == 36) && \"Radix should be 2, 8, 10, 16, or 36!\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 446, __extension__ __PRETTY_FUNCTION__))
446 "Radix should be 2, 8, 10, 16, or 36!")(static_cast <bool> ((radix == 10 || radix == 8 || radix
== 16 || radix == 2 || radix == 36) && "Radix should be 2, 8, 10, 16, or 36!"
) ? void (0) : __assert_fail ("(radix == 10 || radix == 8 || radix == 16 || radix == 2 || radix == 36) && \"Radix should be 2, 8, 10, 16, or 36!\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 446, __extension__ __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.")(static_cast <bool> (slen && "String is only a sign, needs a value."
) ? void (0) : __assert_fail ("slen && \"String is only a sign, needs a value.\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 456, __extension__ __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 &&(static_cast <bool> (getBitWidth() % SplatSizeInBits ==
0 && "SplatSizeInBits must divide width!") ? void (0
) : __assert_fail ("getBitWidth() % SplatSizeInBits == 0 && \"SplatSizeInBits must divide width!\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 504, __extension__ __PRETTY_FUNCTION__))
504 "SplatSizeInBits must divide width!")(static_cast <bool> (getBitWidth() % SplatSizeInBits ==
0 && "SplatSizeInBits must divide width!") ? void (0
) : __assert_fail ("getBitWidth() % SplatSizeInBits == 0 && \"SplatSizeInBits must divide width!\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 504, __extension__ __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!")(static_cast <bool> (NewLen >= V.getBitWidth() &&
"Can't splat to smaller bit width!") ? void (0) : __assert_fail
("NewLen >= V.getBitWidth() && \"Can't splat to smaller bit width!\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 524, __extension__ __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] == WORD_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] == WORD_MAX; ++i)
588 Count += APINT_BITS_PER_WORD;
589 if (i < getNumWords())
590 Count += llvm::countTrailingOnes(U.pVal[i]);
591 assert(Count <= BitWidth)(static_cast <bool> (Count <= BitWidth) ? void (0) :
__assert_fail ("Count <= BitWidth", "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 591, __extension__ __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!")(static_cast <bool> (BitWidth >= 16 && BitWidth
% 16 == 0 && "Cannot byteswap!") ? void (0) : __assert_fail
("BitWidth >= 16 && BitWidth % 16 == 0 && \"Cannot byteswap!\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 619, __extension__ __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 union {
717 double D;
718 uint64_t I;
719 } T;
720 T.D = Double;
721
722 // Get the sign bit from the highest order bit
723 bool isNeg = T.I >> 63;
724
725 // Get the 11-bit exponent and adjust for the 1023 bit bias
726 int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
727
728 // If the exponent is negative, the value is < 0 so just return 0.
729 if (exp < 0)
730 return APInt(width, 0u);
731
732 // Extract the mantissa by clearing the top 12 bits (sign + exponent).
733 uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
734
735 // If the exponent doesn't shift all bits out of the mantissa
736 if (exp < 52)
737 return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
738 APInt(width, mantissa >> (52 - exp));
739
740 // If the client didn't provide enough bits for us to shift the mantissa into
741 // then the result is undefined, just return 0
742 if (width <= exp - 52)
743 return APInt(width, 0);
744
745 // Otherwise, we have to shift the mantissa bits up to the right location
746 APInt Tmp(width, mantissa);
747 Tmp <<= (unsigned)exp - 52;
748 return isNeg ? -Tmp : Tmp;
749}
750
751/// This function converts this APInt to a double.
752/// The layout for double is as following (IEEE Standard 754):
753/// --------------------------------------
754/// | Sign Exponent Fraction Bias |
755/// |-------------------------------------- |
756/// | 1[63] 11[62-52] 52[51-00] 1023 |
757/// --------------------------------------
758double APInt::roundToDouble(bool isSigned) const {
759
760 // Handle the simple case where the value is contained in one uint64_t.
761 // It is wrong to optimize getWord(0) to VAL; there might be more than one word.
762 if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
763 if (isSigned) {
764 int64_t sext = SignExtend64(getWord(0), BitWidth);
765 return double(sext);
766 } else
767 return double(getWord(0));
768 }
769
770 // Determine if the value is negative.
771 bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
772
773 // Construct the absolute value if we're negative.
774 APInt Tmp(isNeg ? -(*this) : (*this));
775
776 // Figure out how many bits we're using.
777 unsigned n = Tmp.getActiveBits();
778
779 // The exponent (without bias normalization) is just the number of bits
780 // we are using. Note that the sign bit is gone since we constructed the
781 // absolute value.
782 uint64_t exp = n;
783
784 // Return infinity for exponent overflow
785 if (exp > 1023) {
786 if (!isSigned || !isNeg)
787 return std::numeric_limits<double>::infinity();
788 else
789 return -std::numeric_limits<double>::infinity();
790 }
791 exp += 1023; // Increment for 1023 bias
792
793 // Number of bits in mantissa is 52. To obtain the mantissa value, we must
794 // extract the high 52 bits from the correct words in pVal.
795 uint64_t mantissa;
796 unsigned hiWord = whichWord(n-1);
797 if (hiWord == 0) {
798 mantissa = Tmp.U.pVal[0];
799 if (n > 52)
800 mantissa >>= n - 52; // shift down, we want the top 52 bits.
801 } else {
802 assert(hiWord > 0 && "huh?")(static_cast <bool> (hiWord > 0 && "huh?") ?
void (0) : __assert_fail ("hiWord > 0 && \"huh?\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 802, __extension__ __PRETTY_FUNCTION__))
;
803 uint64_t hibits = Tmp.U.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
804 uint64_t lobits = Tmp.U.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
805 mantissa = hibits | lobits;
806 }
807
808 // The leading bit of mantissa is implicit, so get rid of it.
809 uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
810 union {
811 double D;
812 uint64_t I;
813 } T;
814 T.I = sign | (exp << 52) | mantissa;
815 return T.D;
816}
817
818// Truncate to new width.
819APInt APInt::trunc(unsigned width) const {
820 assert(width < BitWidth && "Invalid APInt Truncate request")(static_cast <bool> (width < BitWidth && "Invalid APInt Truncate request"
) ? void (0) : __assert_fail ("width < BitWidth && \"Invalid APInt Truncate request\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 820, __extension__ __PRETTY_FUNCTION__))
;
821 assert(width && "Can't truncate to 0 bits")(static_cast <bool> (width && "Can't truncate to 0 bits"
) ? void (0) : __assert_fail ("width && \"Can't truncate to 0 bits\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 821, __extension__ __PRETTY_FUNCTION__))
;
822
823 if (width <= APINT_BITS_PER_WORD)
824 return APInt(width, getRawData()[0]);
825
826 APInt Result(getMemory(getNumWords(width)), width);
827
828 // Copy full words.
829 unsigned i;
830 for (i = 0; i != width / APINT_BITS_PER_WORD; i++)
831 Result.U.pVal[i] = U.pVal[i];
832
833 // Truncate and copy any partial word.
834 unsigned bits = (0 - width) % APINT_BITS_PER_WORD;
835 if (bits != 0)
836 Result.U.pVal[i] = U.pVal[i] << bits >> bits;
837
838 return Result;
839}
840
841// Sign extend to a new width.
842APInt APInt::sext(unsigned Width) const {
843 assert(Width > BitWidth && "Invalid APInt SignExtend request")(static_cast <bool> (Width > BitWidth && "Invalid APInt SignExtend request"
) ? void (0) : __assert_fail ("Width > BitWidth && \"Invalid APInt SignExtend request\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 843, __extension__ __PRETTY_FUNCTION__))
;
844
845 if (Width <= APINT_BITS_PER_WORD)
846 return APInt(Width, SignExtend64(U.VAL, BitWidth));
847
848 APInt Result(getMemory(getNumWords(Width)), Width);
849
850 // Copy words.
851 std::memcpy(Result.U.pVal, getRawData(), getNumWords() * APINT_WORD_SIZE);
852
853 // Sign extend the last word since there may be unused bits in the input.
854 Result.U.pVal[getNumWords() - 1] =
855 SignExtend64(Result.U.pVal[getNumWords() - 1],
856 ((BitWidth - 1) % APINT_BITS_PER_WORD) + 1);
857
858 // Fill with sign bits.
859 std::memset(Result.U.pVal + getNumWords(), isNegative() ? -1 : 0,
860 (Result.getNumWords() - getNumWords()) * APINT_WORD_SIZE);
861 Result.clearUnusedBits();
862 return Result;
863}
864
865// Zero extend to a new width.
866APInt APInt::zext(unsigned width) const {
867 assert(width > BitWidth && "Invalid APInt ZeroExtend request")(static_cast <bool> (width > BitWidth && "Invalid APInt ZeroExtend request"
) ? void (0) : __assert_fail ("width > BitWidth && \"Invalid APInt ZeroExtend request\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 867, __extension__ __PRETTY_FUNCTION__))
;
868
869 if (width <= APINT_BITS_PER_WORD)
870 return APInt(width, U.VAL);
871
872 APInt Result(getMemory(getNumWords(width)), width);
873
874 // Copy words.
875 std::memcpy(Result.U.pVal, getRawData(), getNumWords() * APINT_WORD_SIZE);
876
877 // Zero remaining words.
878 std::memset(Result.U.pVal + getNumWords(), 0,
879 (Result.getNumWords() - getNumWords()) * APINT_WORD_SIZE);
880
881 return Result;
882}
883
884APInt APInt::zextOrTrunc(unsigned width) const {
885 if (BitWidth < width)
886 return zext(width);
887 if (BitWidth > width)
888 return trunc(width);
889 return *this;
890}
891
892APInt APInt::sextOrTrunc(unsigned width) const {
893 if (BitWidth < width)
894 return sext(width);
895 if (BitWidth > width)
896 return trunc(width);
897 return *this;
898}
899
900APInt APInt::zextOrSelf(unsigned width) const {
901 if (BitWidth < width)
902 return zext(width);
903 return *this;
904}
905
906APInt APInt::sextOrSelf(unsigned width) const {
907 if (BitWidth < width)
908 return sext(width);
909 return *this;
910}
911
912/// Arithmetic right-shift this APInt by shiftAmt.
913/// @brief Arithmetic right-shift function.
914void APInt::ashrInPlace(const APInt &shiftAmt) {
915 ashrInPlace((unsigned)shiftAmt.getLimitedValue(BitWidth));
916}
917
918/// Arithmetic right-shift this APInt by shiftAmt.
919/// @brief Arithmetic right-shift function.
920void APInt::ashrSlowCase(unsigned ShiftAmt) {
921 // Don't bother performing a no-op shift.
922 if (!ShiftAmt)
923 return;
924
925 // Save the original sign bit for later.
926 bool Negative = isNegative();
927
928 // WordShift is the inter-part shift; BitShift is is intra-part shift.
929 unsigned WordShift = ShiftAmt / APINT_BITS_PER_WORD;
930 unsigned BitShift = ShiftAmt % APINT_BITS_PER_WORD;
931
932 unsigned WordsToMove = getNumWords() - WordShift;
933 if (WordsToMove != 0) {
934 // Sign extend the last word to fill in the unused bits.
935 U.pVal[getNumWords() - 1] = SignExtend64(
936 U.pVal[getNumWords() - 1], ((BitWidth - 1) % APINT_BITS_PER_WORD) + 1);
937
938 // Fastpath for moving by whole words.
939 if (BitShift == 0) {
940 std::memmove(U.pVal, U.pVal + WordShift, WordsToMove * APINT_WORD_SIZE);
941 } else {
942 // Move the words containing significant bits.
943 for (unsigned i = 0; i != WordsToMove - 1; ++i)
944 U.pVal[i] = (U.pVal[i + WordShift] >> BitShift) |
945 (U.pVal[i + WordShift + 1] << (APINT_BITS_PER_WORD - BitShift));
946
947 // Handle the last word which has no high bits to copy.
948 U.pVal[WordsToMove - 1] = U.pVal[WordShift + WordsToMove - 1] >> BitShift;
949 // Sign extend one more time.
950 U.pVal[WordsToMove - 1] =
951 SignExtend64(U.pVal[WordsToMove - 1], APINT_BITS_PER_WORD - BitShift);
952 }
953 }
954
955 // Fill in the remainder based on the original sign.
956 std::memset(U.pVal + WordsToMove, Negative ? -1 : 0,
957 WordShift * APINT_WORD_SIZE);
958 clearUnusedBits();
959}
960
961/// Logical right-shift this APInt by shiftAmt.
962/// @brief Logical right-shift function.
963void APInt::lshrInPlace(const APInt &shiftAmt) {
964 lshrInPlace((unsigned)shiftAmt.getLimitedValue(BitWidth));
965}
966
967/// Logical right-shift this APInt by shiftAmt.
968/// @brief Logical right-shift function.
969void APInt::lshrSlowCase(unsigned ShiftAmt) {
970 tcShiftRight(U.pVal, getNumWords(), ShiftAmt);
971}
972
973/// Left-shift this APInt by shiftAmt.
974/// @brief Left-shift function.
975APInt &APInt::operator<<=(const APInt &shiftAmt) {
976 // It's undefined behavior in C to shift by BitWidth or greater.
977 *this <<= (unsigned)shiftAmt.getLimitedValue(BitWidth);
978 return *this;
979}
980
981void APInt::shlSlowCase(unsigned ShiftAmt) {
982 tcShiftLeft(U.pVal, getNumWords(), ShiftAmt);
983 clearUnusedBits();
984}
985
986// Calculate the rotate amount modulo the bit width.
987static unsigned rotateModulo(unsigned BitWidth, const APInt &rotateAmt) {
988 unsigned rotBitWidth = rotateAmt.getBitWidth();
989 APInt rot = rotateAmt;
990 if (rotBitWidth < BitWidth) {
991 // Extend the rotate APInt, so that the urem doesn't divide by 0.
992 // e.g. APInt(1, 32) would give APInt(1, 0).
993 rot = rotateAmt.zext(BitWidth);
994 }
995 rot = rot.urem(APInt(rot.getBitWidth(), BitWidth));
996 return rot.getLimitedValue(BitWidth);
997}
998
999APInt APInt::rotl(const APInt &rotateAmt) const {
1000 return rotl(rotateModulo(BitWidth, rotateAmt));
1001}
1002
1003APInt APInt::rotl(unsigned rotateAmt) const {
1004 rotateAmt %= BitWidth;
1005 if (rotateAmt == 0)
1006 return *this;
1007 return shl(rotateAmt) | lshr(BitWidth - rotateAmt);
1008}
1009
1010APInt APInt::rotr(const APInt &rotateAmt) const {
1011 return rotr(rotateModulo(BitWidth, rotateAmt));
1012}
1013
1014APInt APInt::rotr(unsigned rotateAmt) const {
1015 rotateAmt %= BitWidth;
1016 if (rotateAmt == 0)
1017 return *this;
1018 return lshr(rotateAmt) | shl(BitWidth - rotateAmt);
1019}
1020
1021// Square Root - this method computes and returns the square root of "this".
1022// Three mechanisms are used for computation. For small values (<= 5 bits),
1023// a table lookup is done. This gets some performance for common cases. For
1024// values using less than 52 bits, the value is converted to double and then
1025// the libc sqrt function is called. The result is rounded and then converted
1026// back to a uint64_t which is then used to construct the result. Finally,
1027// the Babylonian method for computing square roots is used.
1028APInt APInt::sqrt() const {
1029
1030 // Determine the magnitude of the value.
1031 unsigned magnitude = getActiveBits();
1032
1033 // Use a fast table for some small values. This also gets rid of some
1034 // rounding errors in libc sqrt for small values.
1035 if (magnitude <= 5) {
1
Assuming 'magnitude' is > 5
2
Taking false branch
1036 static const uint8_t results[32] = {
1037 /* 0 */ 0,
1038 /* 1- 2 */ 1, 1,
1039 /* 3- 6 */ 2, 2, 2, 2,
1040 /* 7-12 */ 3, 3, 3, 3, 3, 3,
1041 /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
1042 /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1043 /* 31 */ 6
1044 };
1045 return APInt(BitWidth, results[ (isSingleWord() ? U.VAL : U.pVal[0]) ]);
1046 }
1047
1048 // If the magnitude of the value fits in less than 52 bits (the precision of
1049 // an IEEE double precision floating point value), then we can use the
1050 // libc sqrt function which will probably use a hardware sqrt computation.
1051 // This should be faster than the algorithm below.
1052 if (magnitude < 52) {
3
Assuming 'magnitude' is >= 52
4
Taking false branch
1053 return APInt(BitWidth,
1054 uint64_t(::round(::sqrt(double(isSingleWord() ? U.VAL
1055 : U.pVal[0])))));
1056 }
1057
1058 // Okay, all the short cuts are exhausted. We must compute it. The following
1059 // is a classical Babylonian method for computing the square root. This code
1060 // was adapted to APInt from a wikipedia article on such computations.
1061 // See http://www.wikipedia.org/ and go to the page named
1062 // Calculate_an_integer_square_root.
1063 unsigned nbits = BitWidth, i = 4;
1064 APInt testy(BitWidth, 16);
1065 APInt x_old(BitWidth, 1);
5
Calling constructor for 'APInt'
12
Returning from constructor for 'APInt'
1066 APInt x_new(BitWidth, 0);
1067 APInt two(BitWidth, 2);
1068
1069 // Select a good starting value using binary logarithms.
1070 for (;; i += 2, testy = testy.shl(2))
13
Loop condition is true. Entering loop body
1071 if (i >= nbits || this->ule(testy)) {
14
Taking true branch
1072 x_old = x_old.shl(i / 2);
15
Calling move assignment operator for 'APInt'
18
Returning; memory was released
1073 break;
19
Execution continues on line 1077
1074 }
1075
1076 // Use the Babylonian method to arrive at the integer square root:
1077 for (;;) {
20
Loop condition is true. Entering loop body
1078 x_new = (this->udiv(x_old) + x_old).udiv(two);
21
Calling 'operator+'
1079 if (x_old.ule(x_new))
1080 break;
1081 x_old = x_new;
1082 }
1083
1084 // Make sure we return the closest approximation
1085 // NOTE: The rounding calculation below is correct. It will produce an
1086 // off-by-one discrepancy with results from pari/gp. That discrepancy has been
1087 // determined to be a rounding issue with pari/gp as it begins to use a
1088 // floating point representation after 192 bits. There are no discrepancies
1089 // between this algorithm and pari/gp for bit widths < 192 bits.
1090 APInt square(x_old * x_old);
1091 APInt nextSquare((x_old + 1) * (x_old +1));
1092 if (this->ult(square))
1093 return x_old;
1094 assert(this->ule(nextSquare) && "Error in APInt::sqrt computation")(static_cast <bool> (this->ule(nextSquare) &&
"Error in APInt::sqrt computation") ? void (0) : __assert_fail
("this->ule(nextSquare) && \"Error in APInt::sqrt computation\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 1094, __extension__ __PRETTY_FUNCTION__))
;
1095 APInt midpoint((nextSquare - square).udiv(two));
1096 APInt offset(*this - square);
1097 if (offset.ult(midpoint))
1098 return x_old;
1099 return x_old + 1;
1100}
1101
1102/// Computes the multiplicative inverse of this APInt for a given modulo. The
1103/// iterative extended Euclidean algorithm is used to solve for this value,
1104/// however we simplify it to speed up calculating only the inverse, and take
1105/// advantage of div+rem calculations. We also use some tricks to avoid copying
1106/// (potentially large) APInts around.
1107APInt APInt::multiplicativeInverse(const APInt& modulo) const {
1108 assert(ult(modulo) && "This APInt must be smaller than the modulo")(static_cast <bool> (ult(modulo) && "This APInt must be smaller than the modulo"
) ? void (0) : __assert_fail ("ult(modulo) && \"This APInt must be smaller than the modulo\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 1108, __extension__ __PRETTY_FUNCTION__))
;
1109
1110 // Using the properties listed at the following web page (accessed 06/21/08):
1111 // http://www.numbertheory.org/php/euclid.html
1112 // (especially the properties numbered 3, 4 and 9) it can be proved that
1113 // BitWidth bits suffice for all the computations in the algorithm implemented
1114 // below. More precisely, this number of bits suffice if the multiplicative
1115 // inverse exists, but may not suffice for the general extended Euclidean
1116 // algorithm.
1117
1118 APInt r[2] = { modulo, *this };
1119 APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) };
1120 APInt q(BitWidth, 0);
1121
1122 unsigned i;
1123 for (i = 0; r[i^1] != 0; i ^= 1) {
1124 // An overview of the math without the confusing bit-flipping:
1125 // q = r[i-2] / r[i-1]
1126 // r[i] = r[i-2] % r[i-1]
1127 // t[i] = t[i-2] - t[i-1] * q
1128 udivrem(r[i], r[i^1], q, r[i]);
1129 t[i] -= t[i^1] * q;
1130 }
1131
1132 // If this APInt and the modulo are not coprime, there is no multiplicative
1133 // inverse, so return 0. We check this by looking at the next-to-last
1134 // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean
1135 // algorithm.
1136 if (r[i] != 1)
1137 return APInt(BitWidth, 0);
1138
1139 // The next-to-last t is the multiplicative inverse. However, we are
1140 // interested in a positive inverse. Calculate a positive one from a negative
1141 // one if necessary. A simple addition of the modulo suffices because
1142 // abs(t[i]) is known to be less than *this/2 (see the link above).
1143 if (t[i].isNegative())
1144 t[i] += modulo;
1145
1146 return std::move(t[i]);
1147}
1148
1149/// Calculate the magic numbers required to implement a signed integer division
1150/// by a constant as a sequence of multiplies, adds and shifts. Requires that
1151/// the divisor not be 0, 1, or -1. Taken from "Hacker's Delight", Henry S.
1152/// Warren, Jr., chapter 10.
1153APInt::ms APInt::magic() const {
1154 const APInt& d = *this;
1155 unsigned p;
1156 APInt ad, anc, delta, q1, r1, q2, r2, t;
1157 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1158 struct ms mag;
1159
1160 ad = d.abs();
1161 t = signedMin + (d.lshr(d.getBitWidth() - 1));
1162 anc = t - 1 - t.urem(ad); // absolute value of nc
1163 p = d.getBitWidth() - 1; // initialize p
1164 q1 = signedMin.udiv(anc); // initialize q1 = 2p/abs(nc)
1165 r1 = signedMin - q1*anc; // initialize r1 = rem(2p,abs(nc))
1166 q2 = signedMin.udiv(ad); // initialize q2 = 2p/abs(d)
1167 r2 = signedMin - q2*ad; // initialize r2 = rem(2p,abs(d))
1168 do {
1169 p = p + 1;
1170 q1 = q1<<1; // update q1 = 2p/abs(nc)
1171 r1 = r1<<1; // update r1 = rem(2p/abs(nc))
1172 if (r1.uge(anc)) { // must be unsigned comparison
1173 q1 = q1 + 1;
1174 r1 = r1 - anc;
1175 }
1176 q2 = q2<<1; // update q2 = 2p/abs(d)
1177 r2 = r2<<1; // update r2 = rem(2p/abs(d))
1178 if (r2.uge(ad)) { // must be unsigned comparison
1179 q2 = q2 + 1;
1180 r2 = r2 - ad;
1181 }
1182 delta = ad - r2;
1183 } while (q1.ult(delta) || (q1 == delta && r1 == 0));
1184
1185 mag.m = q2 + 1;
1186 if (d.isNegative()) mag.m = -mag.m; // resulting magic number
1187 mag.s = p - d.getBitWidth(); // resulting shift
1188 return mag;
1189}
1190
1191/// Calculate the magic numbers required to implement an unsigned integer
1192/// division by a constant as a sequence of multiplies, adds and shifts.
1193/// Requires that the divisor not be 0. Taken from "Hacker's Delight", Henry
1194/// S. Warren, Jr., chapter 10.
1195/// LeadingZeros can be used to simplify the calculation if the upper bits
1196/// of the divided value are known zero.
1197APInt::mu APInt::magicu(unsigned LeadingZeros) const {
1198 const APInt& d = *this;
1199 unsigned p;
1200 APInt nc, delta, q1, r1, q2, r2;
1201 struct mu magu;
1202 magu.a = 0; // initialize "add" indicator
1203 APInt allOnes = APInt::getAllOnesValue(d.getBitWidth()).lshr(LeadingZeros);
1204 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1205 APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());
1206
1207 nc = allOnes - (allOnes - d).urem(d);
1208 p = d.getBitWidth() - 1; // initialize p
1209 q1 = signedMin.udiv(nc); // initialize q1 = 2p/nc
1210 r1 = signedMin - q1*nc; // initialize r1 = rem(2p,nc)
1211 q2 = signedMax.udiv(d); // initialize q2 = (2p-1)/d
1212 r2 = signedMax - q2*d; // initialize r2 = rem((2p-1),d)
1213 do {
1214 p = p + 1;
1215 if (r1.uge(nc - r1)) {
1216 q1 = q1 + q1 + 1; // update q1
1217 r1 = r1 + r1 - nc; // update r1
1218 }
1219 else {
1220 q1 = q1+q1; // update q1
1221 r1 = r1+r1; // update r1
1222 }
1223 if ((r2 + 1).uge(d - r2)) {
1224 if (q2.uge(signedMax)) magu.a = 1;
1225 q2 = q2+q2 + 1; // update q2
1226 r2 = r2+r2 + 1 - d; // update r2
1227 }
1228 else {
1229 if (q2.uge(signedMin)) magu.a = 1;
1230 q2 = q2+q2; // update q2
1231 r2 = r2+r2 + 1; // update r2
1232 }
1233 delta = d - 1 - r2;
1234 } while (p < d.getBitWidth()*2 &&
1235 (q1.ult(delta) || (q1 == delta && r1 == 0)));
1236 magu.m = q2 + 1; // resulting magic number
1237 magu.s = p - d.getBitWidth(); // resulting shift
1238 return magu;
1239}
1240
1241/// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
1242/// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
1243/// variables here have the same names as in the algorithm. Comments explain
1244/// the algorithm and any deviation from it.
1245static void KnuthDiv(uint32_t *u, uint32_t *v, uint32_t *q, uint32_t* r,
1246 unsigned m, unsigned n) {
1247 assert(u && "Must provide dividend")(static_cast <bool> (u && "Must provide dividend"
) ? void (0) : __assert_fail ("u && \"Must provide dividend\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 1247, __extension__ __PRETTY_FUNCTION__))
;
1248 assert(v && "Must provide divisor")(static_cast <bool> (v && "Must provide divisor"
) ? void (0) : __assert_fail ("v && \"Must provide divisor\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 1248, __extension__ __PRETTY_FUNCTION__))
;
1249 assert(q && "Must provide quotient")(static_cast <bool> (q && "Must provide quotient"
) ? void (0) : __assert_fail ("q && \"Must provide quotient\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 1249, __extension__ __PRETTY_FUNCTION__))
;
1250 assert(u != v && u != q && v != q && "Must use different memory")(static_cast <bool> (u != v && u != q &&
v != q && "Must use different memory") ? void (0) : __assert_fail
("u != v && u != q && v != q && \"Must use different memory\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 1250, __extension__ __PRETTY_FUNCTION__))
;
1251 assert(n>1 && "n must be > 1")(static_cast <bool> (n>1 && "n must be > 1"
) ? void (0) : __assert_fail ("n>1 && \"n must be > 1\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 1251, __extension__ __PRETTY_FUNCTION__))
;
1252
1253 // b denotes the base of the number system. In our case b is 2^32.
1254 const uint64_t b = uint64_t(1) << 32;
1255
1256// The DEBUG macros here tend to be spam in the debug output if you're not
1257// debugging this code. Disable them unless KNUTH_DEBUG is defined.
1258#pragma push_macro("DEBUG")
1259#ifndef KNUTH_DEBUG
1260#undef DEBUG
1261#define DEBUG(X)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { X; } } while (false)
do {} while (false)
1262#endif
1263
1264 DEBUG(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << "KnuthDiv: m=" << m <<
" n=" << n << '\n'; } } while (false)
;
1265 DEBUG(dbgs() << "KnuthDiv: original:")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << "KnuthDiv: original:"; } } while
(false)
;
1266 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i])do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { for (int i = m+n; i >=0; i--) dbgs() <<
" " << u[i]; } } while (false)
;
1267 DEBUG(dbgs() << " by")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << " by"; } } while (false)
;
1268 DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1])do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { for (int i = n; i >0; i--) dbgs() << " "
<< v[i-1]; } } while (false)
;
1269 DEBUG(dbgs() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << '\n'; } } while (false)
;
1270 // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of
1271 // u and v by d. Note that we have taken Knuth's advice here to use a power
1272 // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
1273 // 2 allows us to shift instead of multiply and it is easy to determine the
1274 // shift amount from the leading zeros. We are basically normalizing the u
1275 // and v so that its high bits are shifted to the top of v's range without
1276 // overflow. Note that this can require an extra word in u so that u must
1277 // be of length m+n+1.
1278 unsigned shift = countLeadingZeros(v[n-1]);
1279 uint32_t v_carry = 0;
1280 uint32_t u_carry = 0;
1281 if (shift) {
1282 for (unsigned i = 0; i < m+n; ++i) {
1283 uint32_t u_tmp = u[i] >> (32 - shift);
1284 u[i] = (u[i] << shift) | u_carry;
1285 u_carry = u_tmp;
1286 }
1287 for (unsigned i = 0; i < n; ++i) {
1288 uint32_t v_tmp = v[i] >> (32 - shift);
1289 v[i] = (v[i] << shift) | v_carry;
1290 v_carry = v_tmp;
1291 }
1292 }
1293 u[m+n] = u_carry;
1294
1295 DEBUG(dbgs() << "KnuthDiv: normal:")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << "KnuthDiv: normal:"; } } while
(false)
;
1296 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i])do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { for (int i = m+n; i >=0; i--) dbgs() <<
" " << u[i]; } } while (false)
;
1297 DEBUG(dbgs() << " by")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << " by"; } } while (false)
;
1298 DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1])do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { for (int i = n; i >0; i--) dbgs() << " "
<< v[i-1]; } } while (false)
;
1299 DEBUG(dbgs() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << '\n'; } } while (false)
;
1300
1301 // D2. [Initialize j.] Set j to m. This is the loop counter over the places.
1302 int j = m;
1303 do {
1304 DEBUG(dbgs() << "KnuthDiv: quotient digit #" << j << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << "KnuthDiv: quotient digit #" <<
j << '\n'; } } while (false)
;
1305 // D3. [Calculate q'.].
1306 // Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
1307 // Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
1308 // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
1309 // qp by 1, increase rp by v[n-1], and repeat this test if rp < b. The test
1310 // on v[n-2] determines at high speed most of the cases in which the trial
1311 // value qp is one too large, and it eliminates all cases where qp is two
1312 // too large.
1313 uint64_t dividend = Make_64(u[j+n], u[j+n-1]);
1314 DEBUG(dbgs() << "KnuthDiv: dividend == " << dividend << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << "KnuthDiv: dividend == " <<
dividend << '\n'; } } while (false)
;
1315 uint64_t qp = dividend / v[n-1];
1316 uint64_t rp = dividend % v[n-1];
1317 if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
1318 qp--;
1319 rp += v[n-1];
1320 if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
1321 qp--;
1322 }
1323 DEBUG(dbgs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << "KnuthDiv: qp == " << qp <<
", rp == " << rp << '\n'; } } while (false)
;
1324
1325 // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
1326 // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
1327 // consists of a simple multiplication by a one-place number, combined with
1328 // a subtraction.
1329 // The digits (u[j+n]...u[j]) should be kept positive; if the result of
1330 // this step is actually negative, (u[j+n]...u[j]) should be left as the
1331 // true value plus b**(n+1), namely as the b's complement of
1332 // the true value, and a "borrow" to the left should be remembered.
1333 int64_t borrow = 0;
1334 for (unsigned i = 0; i < n; ++i) {
1335 uint64_t p = uint64_t(qp) * uint64_t(v[i]);
1336 int64_t subres = int64_t(u[j+i]) - borrow - Lo_32(p);
1337 u[j+i] = Lo_32(subres);
1338 borrow = Hi_32(p) - Hi_32(subres);
1339 DEBUG(dbgs() << "KnuthDiv: u[j+i] = " << u[j+i]do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << "KnuthDiv: u[j+i] = " << u
[j+i] << ", borrow = " << borrow << '\n'; }
} while (false)
1340 << ", borrow = " << borrow << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << "KnuthDiv: u[j+i] = " << u
[j+i] << ", borrow = " << borrow << '\n'; }
} while (false)
;
1341 }
1342 bool isNeg = u[j+n] < borrow;
1343 u[j+n] -= Lo_32(borrow);
1344
1345 DEBUG(dbgs() << "KnuthDiv: after subtraction:")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << "KnuthDiv: after subtraction:"; }
} while (false)
;
1346 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i])do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { for (int i = m+n; i >=0; i--) dbgs() <<
" " << u[i]; } } while (false)
;
1347 DEBUG(dbgs() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << '\n'; } } while (false)
;
1348
1349 // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
1350 // negative, go to step D6; otherwise go on to step D7.
1351 q[j] = Lo_32(qp);
1352 if (isNeg) {
1353 // D6. [Add back]. The probability that this step is necessary is very
1354 // small, on the order of only 2/b. Make sure that test data accounts for
1355 // this possibility. Decrease q[j] by 1
1356 q[j]--;
1357 // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
1358 // A carry will occur to the left of u[j+n], and it should be ignored
1359 // since it cancels with the borrow that occurred in D4.
1360 bool carry = false;
1361 for (unsigned i = 0; i < n; i++) {
1362 uint32_t limit = std::min(u[j+i],v[i]);
1363 u[j+i] += v[i] + carry;
1364 carry = u[j+i] < limit || (carry && u[j+i] == limit);
1365 }
1366 u[j+n] += carry;
1367 }
1368 DEBUG(dbgs() << "KnuthDiv: after correction:")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << "KnuthDiv: after correction:"; }
} while (false)
;
1369 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i])do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { for (int i = m+n; i >=0; i--) dbgs() <<
" " << u[i]; } } while (false)
;
1370 DEBUG(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << "\nKnuthDiv: digit result = " <<
q[j] << '\n'; } } while (false)
;
1371
1372 // D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3.
1373 } while (--j >= 0);
1374
1375 DEBUG(dbgs() << "KnuthDiv: quotient:")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << "KnuthDiv: quotient:"; } } while
(false)
;
1376 DEBUG(for (int i = m; i >=0; i--) dbgs() <<" " << q[i])do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { for (int i = m; i >=0; i--) dbgs() <<" "
<< q[i]; } } while (false)
;
1377 DEBUG(dbgs() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << '\n'; } } while (false)
;
1378
1379 // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
1380 // remainder may be obtained by dividing u[...] by d. If r is non-null we
1381 // compute the remainder (urem uses this).
1382 if (r) {
1383 // The value d is expressed by the "shift" value above since we avoided
1384 // multiplication by d by using a shift left. So, all we have to do is
1385 // shift right here.
1386 if (shift) {
1387 uint32_t carry = 0;
1388 DEBUG(dbgs() << "KnuthDiv: remainder:")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << "KnuthDiv: remainder:"; } } while
(false)
;
1389 for (int i = n-1; i >= 0; i--) {
1390 r[i] = (u[i] >> shift) | carry;
1391 carry = u[i] << (32 - shift);
1392 DEBUG(dbgs() << " " << r[i])do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << " " << r[i]; } } while (false
)
;
1393 }
1394 } else {
1395 for (int i = n-1; i >= 0; i--) {
1396 r[i] = u[i];
1397 DEBUG(dbgs() << " " << r[i])do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << " " << r[i]; } } while (false
)
;
1398 }
1399 }
1400 DEBUG(dbgs() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << '\n'; } } while (false)
;
1401 }
1402 DEBUG(dbgs() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << '\n'; } } while (false)
;
1403
1404#pragma pop_macro("DEBUG")
1405}
1406
1407void APInt::divide(const WordType *LHS, unsigned lhsWords, const WordType *RHS,
1408 unsigned rhsWords, WordType *Quotient, WordType *Remainder) {
1409 assert(lhsWords >= rhsWords && "Fractional result")(static_cast <bool> (lhsWords >= rhsWords &&
"Fractional result") ? void (0) : __assert_fail ("lhsWords >= rhsWords && \"Fractional result\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 1409, __extension__ __PRETTY_FUNCTION__))
;
1410
1411 // First, compose the values into an array of 32-bit words instead of
1412 // 64-bit words. This is a necessity of both the "short division" algorithm
1413 // and the Knuth "classical algorithm" which requires there to be native
1414 // operations for +, -, and * on an m bit value with an m*2 bit result. We
1415 // can't use 64-bit operands here because we don't have native results of
1416 // 128-bits. Furthermore, casting the 64-bit values to 32-bit values won't
1417 // work on large-endian machines.
1418 unsigned n = rhsWords * 2;
1419 unsigned m = (lhsWords * 2) - n;
1420
1421 // Allocate space for the temporary values we need either on the stack, if
1422 // it will fit, or on the heap if it won't.
1423 uint32_t SPACE[128];
1424 uint32_t *U = nullptr;
1425 uint32_t *V = nullptr;
1426 uint32_t *Q = nullptr;
1427 uint32_t *R = nullptr;
1428 if ((Remainder?4:3)*n+2*m+1 <= 128) {
1429 U = &SPACE[0];
1430 V = &SPACE[m+n+1];
1431 Q = &SPACE[(m+n+1) + n];
1432 if (Remainder)
1433 R = &SPACE[(m+n+1) + n + (m+n)];
1434 } else {
1435 U = new uint32_t[m + n + 1];
1436 V = new uint32_t[n];
1437 Q = new uint32_t[m+n];
1438 if (Remainder)
1439 R = new uint32_t[n];
1440 }
1441
1442 // Initialize the dividend
1443 memset(U, 0, (m+n+1)*sizeof(uint32_t));
1444 for (unsigned i = 0; i < lhsWords; ++i) {
1445 uint64_t tmp = LHS[i];
1446 U[i * 2] = Lo_32(tmp);
1447 U[i * 2 + 1] = Hi_32(tmp);
1448 }
1449 U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
1450
1451 // Initialize the divisor
1452 memset(V, 0, (n)*sizeof(uint32_t));
1453 for (unsigned i = 0; i < rhsWords; ++i) {
1454 uint64_t tmp = RHS[i];
1455 V[i * 2] = Lo_32(tmp);
1456 V[i * 2 + 1] = Hi_32(tmp);
1457 }
1458
1459 // initialize the quotient and remainder
1460 memset(Q, 0, (m+n) * sizeof(uint32_t));
1461 if (Remainder)
1462 memset(R, 0, n * sizeof(uint32_t));
1463
1464 // Now, adjust m and n for the Knuth division. n is the number of words in
1465 // the divisor. m is the number of words by which the dividend exceeds the
1466 // divisor (i.e. m+n is the length of the dividend). These sizes must not
1467 // contain any zero words or the Knuth algorithm fails.
1468 for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
1469 n--;
1470 m++;
1471 }
1472 for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
1473 m--;
1474
1475 // If we're left with only a single word for the divisor, Knuth doesn't work
1476 // so we implement the short division algorithm here. This is much simpler
1477 // and faster because we are certain that we can divide a 64-bit quantity
1478 // by a 32-bit quantity at hardware speed and short division is simply a
1479 // series of such operations. This is just like doing short division but we
1480 // are using base 2^32 instead of base 10.
1481 assert(n != 0 && "Divide by zero?")(static_cast <bool> (n != 0 && "Divide by zero?"
) ? void (0) : __assert_fail ("n != 0 && \"Divide by zero?\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 1481, __extension__ __PRETTY_FUNCTION__))
;
1482 if (n == 1) {
1483 uint32_t divisor = V[0];
1484 uint32_t remainder = 0;
1485 for (int i = m; i >= 0; i--) {
1486 uint64_t partial_dividend = Make_64(remainder, U[i]);
1487 if (partial_dividend == 0) {
1488 Q[i] = 0;
1489 remainder = 0;
1490 } else if (partial_dividend < divisor) {
1491 Q[i] = 0;
1492 remainder = Lo_32(partial_dividend);
1493 } else if (partial_dividend == divisor) {
1494 Q[i] = 1;
1495 remainder = 0;
1496 } else {
1497 Q[i] = Lo_32(partial_dividend / divisor);
1498 remainder = Lo_32(partial_dividend - (Q[i] * divisor));
1499 }
1500 }
1501 if (R)
1502 R[0] = remainder;
1503 } else {
1504 // Now we're ready to invoke the Knuth classical divide algorithm. In this
1505 // case n > 1.
1506 KnuthDiv(U, V, Q, R, m, n);
1507 }
1508
1509 // If the caller wants the quotient
1510 if (Quotient) {
1511 for (unsigned i = 0; i < lhsWords; ++i)
1512 Quotient[i] = Make_64(Q[i*2+1], Q[i*2]);
1513 }
1514
1515 // If the caller wants the remainder
1516 if (Remainder) {
1517 for (unsigned i = 0; i < rhsWords; ++i)
1518 Remainder[i] = Make_64(R[i*2+1], R[i*2]);
1519 }
1520
1521 // Clean up the memory we allocated.
1522 if (U != &SPACE[0]) {
1523 delete [] U;
1524 delete [] V;
1525 delete [] Q;
1526 delete [] R;
1527 }
1528}
1529
1530APInt APInt::udiv(const APInt &RHS) const {
1531 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")(static_cast <bool> (BitWidth == RHS.BitWidth &&
"Bit widths must be the same") ? void (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 1531, __extension__ __PRETTY_FUNCTION__))
;
1532
1533 // First, deal with the easy case
1534 if (isSingleWord()) {
1535 assert(RHS.U.VAL != 0 && "Divide by zero?")(static_cast <bool> (RHS.U.VAL != 0 && "Divide by zero?"
) ? void (0) : __assert_fail ("RHS.U.VAL != 0 && \"Divide by zero?\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 1535, __extension__ __PRETTY_FUNCTION__))
;
1536 return APInt(BitWidth, U.VAL / RHS.U.VAL);
1537 }
1538
1539 // Get some facts about the LHS and RHS number of bits and words
1540 unsigned lhsWords = getNumWords(getActiveBits());
1541 unsigned rhsBits = RHS.getActiveBits();
1542 unsigned rhsWords = getNumWords(rhsBits);
1543 assert(rhsWords && "Divided by zero???")(static_cast <bool> (rhsWords && "Divided by zero???"
) ? void (0) : __assert_fail ("rhsWords && \"Divided by zero???\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 1543, __extension__ __PRETTY_FUNCTION__))
;
1544
1545 // Deal with some degenerate cases
1546 if (!lhsWords)
1547 // 0 / X ===> 0
1548 return APInt(BitWidth, 0);
1549 if (rhsBits == 1)
1550 // X / 1 ===> X
1551 return *this;
1552 if (lhsWords < rhsWords || this->ult(RHS))
1553 // X / Y ===> 0, iff X < Y
1554 return APInt(BitWidth, 0);
1555 if (*this == RHS)
1556 // X / X ===> 1
1557 return APInt(BitWidth, 1);
1558 if (lhsWords == 1) // rhsWords is 1 if lhsWords is 1.
1559 // All high words are zero, just use native divide
1560 return APInt(BitWidth, this->U.pVal[0] / RHS.U.pVal[0]);
1561
1562 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1563 APInt Quotient(BitWidth, 0); // to hold result.
1564 divide(U.pVal, lhsWords, RHS.U.pVal, rhsWords, Quotient.U.pVal, nullptr);
1565 return Quotient;
1566}
1567
1568APInt APInt::udiv(uint64_t RHS) const {
1569 assert(RHS != 0 && "Divide by zero?")(static_cast <bool> (RHS != 0 && "Divide by zero?"
) ? void (0) : __assert_fail ("RHS != 0 && \"Divide by zero?\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 1569, __extension__ __PRETTY_FUNCTION__))
;
1570
1571 // First, deal with the easy case
1572 if (isSingleWord())
1573 return APInt(BitWidth, U.VAL / RHS);
1574
1575 // Get some facts about the LHS words.
1576 unsigned lhsWords = getNumWords(getActiveBits());
1577
1578 // Deal with some degenerate cases
1579 if (!lhsWords)
1580 // 0 / X ===> 0
1581 return APInt(BitWidth, 0);
1582 if (RHS == 1)
1583 // X / 1 ===> X
1584 return *this;
1585 if (this->ult(RHS))
1586 // X / Y ===> 0, iff X < Y
1587 return APInt(BitWidth, 0);
1588 if (*this == RHS)
1589 // X / X ===> 1
1590 return APInt(BitWidth, 1);
1591 if (lhsWords == 1) // rhsWords is 1 if lhsWords is 1.
1592 // All high words are zero, just use native divide
1593 return APInt(BitWidth, this->U.pVal[0] / RHS);
1594
1595 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1596 APInt Quotient(BitWidth, 0); // to hold result.
1597 divide(U.pVal, lhsWords, &RHS, 1, Quotient.U.pVal, nullptr);
1598 return Quotient;
1599}
1600
1601APInt APInt::sdiv(const APInt &RHS) const {
1602 if (isNegative()) {
1603 if (RHS.isNegative())
1604 return (-(*this)).udiv(-RHS);
1605 return -((-(*this)).udiv(RHS));
1606 }
1607 if (RHS.isNegative())
1608 return -(this->udiv(-RHS));
1609 return this->udiv(RHS);
1610}
1611
1612APInt APInt::sdiv(int64_t RHS) const {
1613 if (isNegative()) {
1614 if (RHS < 0)
1615 return (-(*this)).udiv(-RHS);
1616 return -((-(*this)).udiv(RHS));
1617 }
1618 if (RHS < 0)
1619 return -(this->udiv(-RHS));
1620 return this->udiv(RHS);
1621}
1622
1623APInt APInt::urem(const APInt &RHS) const {
1624 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")(static_cast <bool> (BitWidth == RHS.BitWidth &&
"Bit widths must be the same") ? void (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 1624, __extension__ __PRETTY_FUNCTION__))
;
1625 if (isSingleWord()) {
1626 assert(RHS.U.VAL != 0 && "Remainder by zero?")(static_cast <bool> (RHS.U.VAL != 0 && "Remainder by zero?"
) ? void (0) : __assert_fail ("RHS.U.VAL != 0 && \"Remainder by zero?\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 1626, __extension__ __PRETTY_FUNCTION__))
;
1627 return APInt(BitWidth, U.VAL % RHS.U.VAL);
1628 }
1629
1630 // Get some facts about the LHS
1631 unsigned lhsWords = getNumWords(getActiveBits());
1632
1633 // Get some facts about the RHS
1634 unsigned rhsBits = RHS.getActiveBits();
1635 unsigned rhsWords = getNumWords(rhsBits);
1636 assert(rhsWords && "Performing remainder operation by zero ???")(static_cast <bool> (rhsWords && "Performing remainder operation by zero ???"
) ? void (0) : __assert_fail ("rhsWords && \"Performing remainder operation by zero ???\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 1636, __extension__ __PRETTY_FUNCTION__))
;
1637
1638 // Check the degenerate cases
1639 if (lhsWords == 0)
1640 // 0 % Y ===> 0
1641 return APInt(BitWidth, 0);
1642 if (rhsBits == 1)
1643 // X % 1 ===> 0
1644 return APInt(BitWidth, 0);
1645 if (lhsWords < rhsWords || this->ult(RHS))
1646 // X % Y ===> X, iff X < Y
1647 return *this;
1648 if (*this == RHS)
1649 // X % X == 0;
1650 return APInt(BitWidth, 0);
1651 if (lhsWords == 1)
1652 // All high words are zero, just use native remainder
1653 return APInt(BitWidth, U.pVal[0] % RHS.U.pVal[0]);
1654
1655 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1656 APInt Remainder(BitWidth, 0);
1657 divide(U.pVal, lhsWords, RHS.U.pVal, rhsWords, nullptr, Remainder.U.pVal);
1658 return Remainder;
1659}
1660
1661uint64_t APInt::urem(uint64_t RHS) const {
1662 assert(RHS != 0 && "Remainder by zero?")(static_cast <bool> (RHS != 0 && "Remainder by zero?"
) ? void (0) : __assert_fail ("RHS != 0 && \"Remainder by zero?\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 1662, __extension__ __PRETTY_FUNCTION__))
;
1663
1664 if (isSingleWord())
1665 return U.VAL % RHS;
1666
1667 // Get some facts about the LHS
1668 unsigned lhsWords = getNumWords(getActiveBits());
1669
1670 // Check the degenerate cases
1671 if (lhsWords == 0)
1672 // 0 % Y ===> 0
1673 return 0;
1674 if (RHS == 1)
1675 // X % 1 ===> 0
1676 return 0;
1677 if (this->ult(RHS))
1678 // X % Y ===> X, iff X < Y
1679 return getZExtValue();
1680 if (*this == RHS)
1681 // X % X == 0;
1682 return 0;
1683 if (lhsWords == 1)
1684 // All high words are zero, just use native remainder
1685 return U.pVal[0] % RHS;
1686
1687 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1688 uint64_t Remainder;
1689 divide(U.pVal, lhsWords, &RHS, 1, nullptr, &Remainder);
1690 return Remainder;
1691}
1692
1693APInt APInt::srem(const APInt &RHS) const {
1694 if (isNegative()) {
1695 if (RHS.isNegative())
1696 return -((-(*this)).urem(-RHS));
1697 return -((-(*this)).urem(RHS));
1698 }
1699 if (RHS.isNegative())
1700 return this->urem(-RHS);
1701 return this->urem(RHS);
1702}
1703
1704int64_t APInt::srem(int64_t RHS) const {
1705 if (isNegative()) {
1706 if (RHS < 0)
1707 return -((-(*this)).urem(-RHS));
1708 return -((-(*this)).urem(RHS));
1709 }
1710 if (RHS < 0)
1711 return this->urem(-RHS);
1712 return this->urem(RHS);
1713}
1714
1715void APInt::udivrem(const APInt &LHS, const APInt &RHS,
1716 APInt &Quotient, APInt &Remainder) {
1717 assert(LHS.BitWidth == RHS.BitWidth && "Bit widths must be the same")(static_cast <bool> (LHS.BitWidth == RHS.BitWidth &&
"Bit widths must be the same") ? void (0) : __assert_fail ("LHS.BitWidth == RHS.BitWidth && \"Bit widths must be the same\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 1717, __extension__ __PRETTY_FUNCTION__))
;
1718 unsigned BitWidth = LHS.BitWidth;
1719
1720 // First, deal with the easy case
1721 if (LHS.isSingleWord()) {
1722 assert(RHS.U.VAL != 0 && "Divide by zero?")(static_cast <bool> (RHS.U.VAL != 0 && "Divide by zero?"
) ? void (0) : __assert_fail ("RHS.U.VAL != 0 && \"Divide by zero?\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 1722, __extension__ __PRETTY_FUNCTION__))
;
1723 uint64_t QuotVal = LHS.U.VAL / RHS.U.VAL;
1724 uint64_t RemVal = LHS.U.VAL % RHS.U.VAL;
1725 Quotient = APInt(BitWidth, QuotVal);
1726 Remainder = APInt(BitWidth, RemVal);
1727 return;
1728 }
1729
1730 // Get some size facts about the dividend and divisor
1731 unsigned lhsWords = getNumWords(LHS.getActiveBits());
1732 unsigned rhsBits = RHS.getActiveBits();
1733 unsigned rhsWords = getNumWords(rhsBits);
1734 assert(rhsWords && "Performing divrem operation by zero ???")(static_cast <bool> (rhsWords && "Performing divrem operation by zero ???"
) ? void (0) : __assert_fail ("rhsWords && \"Performing divrem operation by zero ???\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 1734, __extension__ __PRETTY_FUNCTION__))
;
1735
1736 // Check the degenerate cases
1737 if (lhsWords == 0) {
1738 Quotient = 0; // 0 / Y ===> 0
1739 Remainder = 0; // 0 % Y ===> 0
1740 return;
1741 }
1742
1743 if (rhsBits == 1) {
1744 Quotient = LHS; // X / 1 ===> X
1745 Remainder = 0; // X % 1 ===> 0
1746 }
1747
1748 if (lhsWords < rhsWords || LHS.ult(RHS)) {
1749 Remainder = LHS; // X % Y ===> X, iff X < Y
1750 Quotient = 0; // X / Y ===> 0, iff X < Y
1751 return;
1752 }
1753
1754 if (LHS == RHS) {
1755 Quotient = 1; // X / X ===> 1
1756 Remainder = 0; // X % X ===> 0;
1757 return;
1758 }
1759
1760 // Make sure there is enough space to hold the results.
1761 // NOTE: This assumes that reallocate won't affect any bits if it doesn't
1762 // change the size. This is necessary if Quotient or Remainder is aliased
1763 // with LHS or RHS.
1764 Quotient.reallocate(BitWidth);
1765 Remainder.reallocate(BitWidth);
1766
1767 if (lhsWords == 1) { // rhsWords is 1 if lhsWords is 1.
1768 // There is only one word to consider so use the native versions.
1769 uint64_t lhsValue = LHS.U.pVal[0];
1770 uint64_t rhsValue = RHS.U.pVal[0];
1771 Quotient = lhsValue / rhsValue;
1772 Remainder = lhsValue % rhsValue;
1773 return;
1774 }
1775
1776 // Okay, lets do it the long way
1777 divide(LHS.U.pVal, lhsWords, RHS.U.pVal, rhsWords, Quotient.U.pVal,
1778 Remainder.U.pVal);
1779 // Clear the rest of the Quotient and Remainder.
1780 std::memset(Quotient.U.pVal + lhsWords, 0,
1781 (getNumWords(BitWidth) - lhsWords) * APINT_WORD_SIZE);
1782 std::memset(Remainder.U.pVal + rhsWords, 0,
1783 (getNumWords(BitWidth) - rhsWords) * APINT_WORD_SIZE);
1784}
1785
1786void APInt::udivrem(const APInt &LHS, uint64_t RHS, APInt &Quotient,
1787 uint64_t &Remainder) {
1788 assert(RHS != 0 && "Divide by zero?")(static_cast <bool> (RHS != 0 && "Divide by zero?"
) ? void (0) : __assert_fail ("RHS != 0 && \"Divide by zero?\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 1788, __extension__ __PRETTY_FUNCTION__))
;
1789 unsigned BitWidth = LHS.BitWidth;
1790
1791 // First, deal with the easy case
1792 if (LHS.isSingleWord()) {
1793 uint64_t QuotVal = LHS.U.VAL / RHS;
1794 Remainder = LHS.U.VAL % RHS;
1795 Quotient = APInt(BitWidth, QuotVal);
1796 return;
1797 }
1798
1799 // Get some size facts about the dividend and divisor
1800 unsigned lhsWords = getNumWords(LHS.getActiveBits());
1801
1802 // Check the degenerate cases
1803 if (lhsWords == 0) {
1804 Quotient = 0; // 0 / Y ===> 0
1805 Remainder = 0; // 0 % Y ===> 0
1806 return;
1807 }
1808
1809 if (RHS == 1) {
1810 Quotient = LHS; // X / 1 ===> X
1811 Remainder = 0; // X % 1 ===> 0
1812 }
1813
1814 if (LHS.ult(RHS)) {
1815 Remainder = LHS.getZExtValue(); // X % Y ===> X, iff X < Y
1816 Quotient = 0; // X / Y ===> 0, iff X < Y
1817 return;
1818 }
1819
1820 if (LHS == RHS) {
1821 Quotient = 1; // X / X ===> 1
1822 Remainder = 0; // X % X ===> 0;
1823 return;
1824 }
1825
1826 // Make sure there is enough space to hold the results.
1827 // NOTE: This assumes that reallocate won't affect any bits if it doesn't
1828 // change the size. This is necessary if Quotient is aliased with LHS.
1829 Quotient.reallocate(BitWidth);
1830
1831 if (lhsWords == 1) { // rhsWords is 1 if lhsWords is 1.
1832 // There is only one word to consider so use the native versions.
1833 uint64_t lhsValue = LHS.U.pVal[0];
1834 Quotient = lhsValue / RHS;
1835 Remainder = lhsValue % RHS;
1836 return;
1837 }
1838
1839 // Okay, lets do it the long way
1840 divide(LHS.U.pVal, lhsWords, &RHS, 1, Quotient.U.pVal, &Remainder);
1841 // Clear the rest of the Quotient.
1842 std::memset(Quotient.U.pVal + lhsWords, 0,
1843 (getNumWords(BitWidth) - lhsWords) * APINT_WORD_SIZE);
1844}
1845
1846void APInt::sdivrem(const APInt &LHS, const APInt &RHS,
1847 APInt &Quotient, APInt &Remainder) {
1848 if (LHS.isNegative()) {
1849 if (RHS.isNegative())
1850 APInt::udivrem(-LHS, -RHS, Quotient, Remainder);
1851 else {
1852 APInt::udivrem(-LHS, RHS, Quotient, Remainder);
1853 Quotient.negate();
1854 }
1855 Remainder.negate();
1856 } else if (RHS.isNegative()) {
1857 APInt::udivrem(LHS, -RHS, Quotient, Remainder);
1858 Quotient.negate();
1859 } else {
1860 APInt::udivrem(LHS, RHS, Quotient, Remainder);
1861 }
1862}
1863
1864void APInt::sdivrem(const APInt &LHS, int64_t RHS,
1865 APInt &Quotient, int64_t &Remainder) {
1866 uint64_t R = Remainder;
1867 if (LHS.isNegative()) {
1868 if (RHS < 0)
1869 APInt::udivrem(-LHS, -RHS, Quotient, R);
1870 else {
1871 APInt::udivrem(-LHS, RHS, Quotient, R);
1872 Quotient.negate();
1873 }
1874 R = -R;
1875 } else if (RHS < 0) {
1876 APInt::udivrem(LHS, -RHS, Quotient, R);
1877 Quotient.negate();
1878 } else {
1879 APInt::udivrem(LHS, RHS, Quotient, R);
1880 }
1881 Remainder = R;
1882}
1883
1884APInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const {
1885 APInt Res = *this+RHS;
1886 Overflow = isNonNegative() == RHS.isNonNegative() &&
1887 Res.isNonNegative() != isNonNegative();
1888 return Res;
1889}
1890
1891APInt APInt::uadd_ov(const APInt &RHS, bool &Overflow) const {
1892 APInt Res = *this+RHS;
1893 Overflow = Res.ult(RHS);
1894 return Res;
1895}
1896
1897APInt APInt::ssub_ov(const APInt &RHS, bool &Overflow) const {
1898 APInt Res = *this - RHS;
1899 Overflow = isNonNegative() != RHS.isNonNegative() &&
1900 Res.isNonNegative() != isNonNegative();
1901 return Res;
1902}
1903
1904APInt APInt::usub_ov(const APInt &RHS, bool &Overflow) const {
1905 APInt Res = *this-RHS;
1906 Overflow = Res.ugt(*this);
1907 return Res;
1908}
1909
1910APInt APInt::sdiv_ov(const APInt &RHS, bool &Overflow) const {
1911 // MININT/-1 --> overflow.
1912 Overflow = isMinSignedValue() && RHS.isAllOnesValue();
1913 return sdiv(RHS);
1914}
1915
1916APInt APInt::smul_ov(const APInt &RHS, bool &Overflow) const {
1917 APInt Res = *this * RHS;
1918
1919 if (*this != 0 && RHS != 0)
1920 Overflow = Res.sdiv(RHS) != *this || Res.sdiv(*this) != RHS;
1921 else
1922 Overflow = false;
1923 return Res;
1924}
1925
1926APInt APInt::umul_ov(const APInt &RHS, bool &Overflow) const {
1927 APInt Res = *this * RHS;
1928
1929 if (*this != 0 && RHS != 0)
1930 Overflow = Res.udiv(RHS) != *this || Res.udiv(*this) != RHS;
1931 else
1932 Overflow = false;
1933 return Res;
1934}
1935
1936APInt APInt::sshl_ov(const APInt &ShAmt, bool &Overflow) const {
1937 Overflow = ShAmt.uge(getBitWidth());
1938 if (Overflow)
1939 return APInt(BitWidth, 0);
1940
1941 if (isNonNegative()) // Don't allow sign change.
1942 Overflow = ShAmt.uge(countLeadingZeros());
1943 else
1944 Overflow = ShAmt.uge(countLeadingOnes());
1945
1946 return *this << ShAmt;
1947}
1948
1949APInt APInt::ushl_ov(const APInt &ShAmt, bool &Overflow) const {
1950 Overflow = ShAmt.uge(getBitWidth());
1951 if (Overflow)
1952 return APInt(BitWidth, 0);
1953
1954 Overflow = ShAmt.ugt(countLeadingZeros());
1955
1956 return *this << ShAmt;
1957}
1958
1959
1960
1961
1962void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) {
1963 // Check our assumptions here
1964 assert(!str.empty() && "Invalid string length")(static_cast <bool> (!str.empty() && "Invalid string length"
) ? void (0) : __assert_fail ("!str.empty() && \"Invalid string length\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 1964, __extension__ __PRETTY_FUNCTION__))
;
1965 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||(static_cast <bool> ((radix == 10 || radix == 8 || radix
== 16 || radix == 2 || radix == 36) && "Radix should be 2, 8, 10, 16, or 36!"
) ? void (0) : __assert_fail ("(radix == 10 || radix == 8 || radix == 16 || radix == 2 || radix == 36) && \"Radix should be 2, 8, 10, 16, or 36!\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 1967, __extension__ __PRETTY_FUNCTION__))
1966 radix == 36) &&(static_cast <bool> ((radix == 10 || radix == 8 || radix
== 16 || radix == 2 || radix == 36) && "Radix should be 2, 8, 10, 16, or 36!"
) ? void (0) : __assert_fail ("(radix == 10 || radix == 8 || radix == 16 || radix == 2 || radix == 36) && \"Radix should be 2, 8, 10, 16, or 36!\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 1967, __extension__ __PRETTY_FUNCTION__))
1967 "Radix should be 2, 8, 10, 16, or 36!")(static_cast <bool> ((radix == 10 || radix == 8 || radix
== 16 || radix == 2 || radix == 36) && "Radix should be 2, 8, 10, 16, or 36!"
) ? void (0) : __assert_fail ("(radix == 10 || radix == 8 || radix == 16 || radix == 2 || radix == 36) && \"Radix should be 2, 8, 10, 16, or 36!\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 1967, __extension__ __PRETTY_FUNCTION__))
;
1968
1969 StringRef::iterator p = str.begin();
1970 size_t slen = str.size();
1971 bool isNeg = *p == '-';
1972 if (*p == '-' || *p == '+') {
1973 p++;
1974 slen--;
1975 assert(slen && "String is only a sign, needs a value.")(static_cast <bool> (slen && "String is only a sign, needs a value."
) ? void (0) : __assert_fail ("slen && \"String is only a sign, needs a value.\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 1975, __extension__ __PRETTY_FUNCTION__))
;
1976 }
1977 assert((slen <= numbits || radix != 2) && "Insufficient bit width")(static_cast <bool> ((slen <= numbits || radix != 2)
&& "Insufficient bit width") ? void (0) : __assert_fail
("(slen <= numbits || radix != 2) && \"Insufficient bit width\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 1977, __extension__ __PRETTY_FUNCTION__))
;
1978 assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width")(static_cast <bool> (((slen-1)*3 <= numbits || radix
!= 8) && "Insufficient bit width") ? void (0) : __assert_fail
("((slen-1)*3 <= numbits || radix != 8) && \"Insufficient bit width\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 1978, __extension__ __PRETTY_FUNCTION__))
;
1979 assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width")(static_cast <bool> (((slen-1)*4 <= numbits || radix
!= 16) && "Insufficient bit width") ? void (0) : __assert_fail
("((slen-1)*4 <= numbits || radix != 16) && \"Insufficient bit width\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 1979, __extension__ __PRETTY_FUNCTION__))
;
1980 assert((((slen-1)*64)/22 <= numbits || radix != 10) &&(static_cast <bool> ((((slen-1)*64)/22 <= numbits ||
radix != 10) && "Insufficient bit width") ? void (0)
: __assert_fail ("(((slen-1)*64)/22 <= numbits || radix != 10) && \"Insufficient bit width\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 1981, __extension__ __PRETTY_FUNCTION__))
1981 "Insufficient bit width")(static_cast <bool> ((((slen-1)*64)/22 <= numbits ||
radix != 10) && "Insufficient bit width") ? void (0)
: __assert_fail ("(((slen-1)*64)/22 <= numbits || radix != 10) && \"Insufficient bit width\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 1981, __extension__ __PRETTY_FUNCTION__))
;
1982
1983 // Allocate memory if needed
1984 if (isSingleWord())
1985 U.VAL = 0;
1986 else
1987 U.pVal = getClearedMemory(getNumWords());
1988
1989 // Figure out if we can shift instead of multiply
1990 unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
1991
1992 // Enter digit traversal loop
1993 for (StringRef::iterator e = str.end(); p != e; ++p) {
1994 unsigned digit = getDigit(*p, radix);
1995 assert(digit < radix && "Invalid character in digit string")(static_cast <bool> (digit < radix && "Invalid character in digit string"
) ? void (0) : __assert_fail ("digit < radix && \"Invalid character in digit string\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 1995, __extension__ __PRETTY_FUNCTION__))
;
1996
1997 // Shift or multiply the value by the radix
1998 if (slen > 1) {
1999 if (shift)
2000 *this <<= shift;
2001 else
2002 *this *= radix;
2003 }
2004
2005 // Add in the digit we just interpreted
2006 *this += digit;
2007 }
2008 // If its negative, put it in two's complement form
2009 if (isNeg)
2010 this->negate();
2011}
2012
2013void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix,
2014 bool Signed, bool formatAsCLiteral) const {
2015 assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 ||(static_cast <bool> ((Radix == 10 || Radix == 8 || Radix
== 16 || Radix == 2 || Radix == 36) && "Radix should be 2, 8, 10, 16, or 36!"
) ? void (0) : __assert_fail ("(Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 || Radix == 36) && \"Radix should be 2, 8, 10, 16, or 36!\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 2017, __extension__ __PRETTY_FUNCTION__))
2016 Radix == 36) &&(static_cast <bool> ((Radix == 10 || Radix == 8 || Radix
== 16 || Radix == 2 || Radix == 36) && "Radix should be 2, 8, 10, 16, or 36!"
) ? void (0) : __assert_fail ("(Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 || Radix == 36) && \"Radix should be 2, 8, 10, 16, or 36!\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 2017, __extension__ __PRETTY_FUNCTION__))
2017 "Radix should be 2, 8, 10, 16, or 36!")(static_cast <bool> ((Radix == 10 || Radix == 8 || Radix
== 16 || Radix == 2 || Radix == 36) && "Radix should be 2, 8, 10, 16, or 36!"
) ? void (0) : __assert_fail ("(Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 || Radix == 36) && \"Radix should be 2, 8, 10, 16, or 36!\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 2017, __extension__ __PRETTY_FUNCTION__))
;
2018
2019 const char *Prefix = "";
2020 if (formatAsCLiteral) {
2021 switch (Radix) {
2022 case 2:
2023 // Binary literals are a non-standard extension added in gcc 4.3:
2024 // http://gcc.gnu.org/onlinedocs/gcc-4.3.0/gcc/Binary-constants.html
2025 Prefix = "0b";
2026 break;
2027 case 8:
2028 Prefix = "0";
2029 break;
2030 case 10:
2031 break; // No prefix
2032 case 16:
2033 Prefix = "0x";
2034 break;
2035 default:
2036 llvm_unreachable("Invalid radix!")::llvm::llvm_unreachable_internal("Invalid radix!", "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 2036)
;
2037 }
2038 }
2039
2040 // First, check for a zero value and just short circuit the logic below.
2041 if (*this == 0) {
2042 while (*Prefix) {
2043 Str.push_back(*Prefix);
2044 ++Prefix;
2045 };
2046 Str.push_back('0');
2047 return;
2048 }
2049
2050 static const char Digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
2051
2052 if (isSingleWord()) {
2053 char Buffer[65];
2054 char *BufPtr = std::end(Buffer);
2055
2056 uint64_t N;
2057 if (!Signed) {
2058 N = getZExtValue();
2059 } else {
2060 int64_t I = getSExtValue();
2061 if (I >= 0) {
2062 N = I;
2063 } else {
2064 Str.push_back('-');
2065 N = -(uint64_t)I;
2066 }
2067 }
2068
2069 while (*Prefix) {
2070 Str.push_back(*Prefix);
2071 ++Prefix;
2072 };
2073
2074 while (N) {
2075 *--BufPtr = Digits[N % Radix];
2076 N /= Radix;
2077 }
2078 Str.append(BufPtr, std::end(Buffer));
2079 return;
2080 }
2081
2082 APInt Tmp(*this);
2083
2084 if (Signed && isNegative()) {
2085 // They want to print the signed version and it is a negative value
2086 // Flip the bits and add one to turn it into the equivalent positive
2087 // value and put a '-' in the result.
2088 Tmp.negate();
2089 Str.push_back('-');
2090 }
2091
2092 while (*Prefix) {
2093 Str.push_back(*Prefix);
2094 ++Prefix;
2095 };
2096
2097 // We insert the digits backward, then reverse them to get the right order.
2098 unsigned StartDig = Str.size();
2099
2100 // For the 2, 8 and 16 bit cases, we can just shift instead of divide
2101 // because the number of bits per digit (1, 3 and 4 respectively) divides
2102 // equally. We just shift until the value is zero.
2103 if (Radix == 2 || Radix == 8 || Radix == 16) {
2104 // Just shift tmp right for each digit width until it becomes zero
2105 unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
2106 unsigned MaskAmt = Radix - 1;
2107
2108 while (Tmp.getBoolValue()) {
2109 unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;
2110 Str.push_back(Digits[Digit]);
2111 Tmp.lshrInPlace(ShiftAmt);
2112 }
2113 } else {
2114 while (Tmp.getBoolValue()) {
2115 uint64_t Digit;
2116 udivrem(Tmp, Radix, Tmp, Digit);
2117 assert(Digit < Radix && "divide failed")(static_cast <bool> (Digit < Radix && "divide failed"
) ? void (0) : __assert_fail ("Digit < Radix && \"divide failed\""
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 2117, __extension__ __PRETTY_FUNCTION__))
;
2118 Str.push_back(Digits[Digit]);
2119 }
2120 }
2121
2122 // Reverse the digits before returning.
2123 std::reverse(Str.begin()+StartDig, Str.end());
2124}
2125
2126/// Returns the APInt as a std::string. Note that this is an inefficient method.
2127/// It is better to pass in a SmallVector/SmallString to the methods above.
2128std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const {
2129 SmallString<40> S;
2130 toString(S, Radix, Signed, /* formatAsCLiteral = */false);
2131 return S.str();
2132}
2133
2134#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2135LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void APInt::dump() const {
2136 SmallString<40> S, U;
2137 this->toStringUnsigned(U);
2138 this->toStringSigned(S);
2139 dbgs() << "APInt(" << BitWidth << "b, "
2140 << U << "u " << S << "s)\n";
2141}
2142#endif
2143
2144void APInt::print(raw_ostream &OS, bool isSigned) const {
2145 SmallString<40> S;
2146 this->toString(S, 10, isSigned, /* formatAsCLiteral = */false);
2147 OS << S;
2148}
2149
2150// This implements a variety of operations on a representation of
2151// arbitrary precision, two's-complement, bignum integer values.
2152
2153// Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe
2154// and unrestricting assumption.
2155static_assert(APInt::APINT_BITS_PER_WORD % 2 == 0,
2156 "Part width must be divisible by 2!");
2157
2158/* Some handy functions local to this file. */
2159
2160/* Returns the integer part with the least significant BITS set.
2161 BITS cannot be zero. */
2162static inline APInt::WordType lowBitMask(unsigned bits) {
2163 assert(bits != 0 && bits <= APInt::APINT_BITS_PER_WORD)(static_cast <bool> (bits != 0 && bits <= APInt
::APINT_BITS_PER_WORD) ? void (0) : __assert_fail ("bits != 0 && bits <= APInt::APINT_BITS_PER_WORD"
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 2163, __extension__ __PRETTY_FUNCTION__))
;
2164
2165 return ~(APInt::WordType) 0 >> (APInt::APINT_BITS_PER_WORD - bits);
2166}
2167
2168/* Returns the value of the lower half of PART. */
2169static inline APInt::WordType lowHalf(APInt::WordType part) {
2170 return part & lowBitMask(APInt::APINT_BITS_PER_WORD / 2);
2171}
2172
2173/* Returns the value of the upper half of PART. */
2174static inline APInt::WordType highHalf(APInt::WordType part) {
2175 return part >> (APInt::APINT_BITS_PER_WORD / 2);
2176}
2177
2178/* Returns the bit number of the most significant set bit of a part.
2179 If the input number has no bits set -1U is returned. */
2180static unsigned partMSB(APInt::WordType value) {
2181 return findLastSet(value, ZB_Max);
2182}
2183
2184/* Returns the bit number of the least significant set bit of a
2185 part. If the input number has no bits set -1U is returned. */
2186static unsigned partLSB(APInt::WordType value) {
2187 return findFirstSet(value, ZB_Max);
2188}
2189
2190/* Sets the least significant part of a bignum to the input value, and
2191 zeroes out higher parts. */
2192void APInt::tcSet(WordType *dst, WordType part, unsigned parts) {
2193 assert(parts > 0)(static_cast <bool> (parts > 0) ? void (0) : __assert_fail
("parts > 0", "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 2193, __extension__ __PRETTY_FUNCTION__))
;
2194
2195 dst[0] = part;
2196 for (unsigned i = 1; i < parts; i++)
2197 dst[i] = 0;
2198}
2199
2200/* Assign one bignum to another. */
2201void APInt::tcAssign(WordType *dst, const WordType *src, unsigned parts) {
2202 for (unsigned i = 0; i < parts; i++)
2203 dst[i] = src[i];
2204}
2205
2206/* Returns true if a bignum is zero, false otherwise. */
2207bool APInt::tcIsZero(const WordType *src, unsigned parts) {
2208 for (unsigned i = 0; i < parts; i++)
2209 if (src[i])
2210 return false;
2211
2212 return true;
2213}
2214
2215/* Extract the given bit of a bignum; returns 0 or 1. */
2216int APInt::tcExtractBit(const WordType *parts, unsigned bit) {
2217 return (parts[whichWord(bit)] & maskBit(bit)) != 0;
2218}
2219
2220/* Set the given bit of a bignum. */
2221void APInt::tcSetBit(WordType *parts, unsigned bit) {
2222 parts[whichWord(bit)] |= maskBit(bit);
2223}
2224
2225/* Clears the given bit of a bignum. */
2226void APInt::tcClearBit(WordType *parts, unsigned bit) {
2227 parts[whichWord(bit)] &= ~maskBit(bit);
2228}
2229
2230/* Returns the bit number of the least significant set bit of a
2231 number. If the input number has no bits set -1U is returned. */
2232unsigned APInt::tcLSB(const WordType *parts, unsigned n) {
2233 for (unsigned i = 0; i < n; i++) {
2234 if (parts[i] != 0) {
2235 unsigned lsb = partLSB(parts[i]);
2236
2237 return lsb + i * APINT_BITS_PER_WORD;
2238 }
2239 }
2240
2241 return -1U;
2242}
2243
2244/* Returns the bit number of the most significant set bit of a number.
2245 If the input number has no bits set -1U is returned. */
2246unsigned APInt::tcMSB(const WordType *parts, unsigned n) {
2247 do {
2248 --n;
2249
2250 if (parts[n] != 0) {
2251 unsigned msb = partMSB(parts[n]);
2252
2253 return msb + n * APINT_BITS_PER_WORD;
2254 }
2255 } while (n);
2256
2257 return -1U;
2258}
2259
2260/* Copy the bit vector of width srcBITS from SRC, starting at bit
2261 srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
2262 the least significant bit of DST. All high bits above srcBITS in
2263 DST are zero-filled. */
2264void
2265APInt::tcExtract(WordType *dst, unsigned dstCount, const WordType *src,
2266 unsigned srcBits, unsigned srcLSB) {
2267 unsigned dstParts = (srcBits + APINT_BITS_PER_WORD - 1) / APINT_BITS_PER_WORD;
2268 assert(dstParts <= dstCount)(static_cast <bool> (dstParts <= dstCount) ? void (0
) : __assert_fail ("dstParts <= dstCount", "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 2268, __extension__ __PRETTY_FUNCTION__))
;
2269
2270 unsigned firstSrcPart = srcLSB / APINT_BITS_PER_WORD;
2271 tcAssign (dst, src + firstSrcPart, dstParts);
2272
2273 unsigned shift = srcLSB % APINT_BITS_PER_WORD;
2274 tcShiftRight (dst, dstParts, shift);
2275
2276 /* We now have (dstParts * APINT_BITS_PER_WORD - shift) bits from SRC
2277 in DST. If this is less that srcBits, append the rest, else
2278 clear the high bits. */
2279 unsigned n = dstParts * APINT_BITS_PER_WORD - shift;
2280 if (n < srcBits) {
2281 WordType mask = lowBitMask (srcBits - n);
2282 dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
2283 << n % APINT_BITS_PER_WORD);
2284 } else if (n > srcBits) {
2285 if (srcBits % APINT_BITS_PER_WORD)
2286 dst[dstParts - 1] &= lowBitMask (srcBits % APINT_BITS_PER_WORD);
2287 }
2288
2289 /* Clear high parts. */
2290 while (dstParts < dstCount)
2291 dst[dstParts++] = 0;
2292}
2293
2294/* DST += RHS + C where C is zero or one. Returns the carry flag. */
2295APInt::WordType APInt::tcAdd(WordType *dst, const WordType *rhs,
2296 WordType c, unsigned parts) {
2297 assert(c <= 1)(static_cast <bool> (c <= 1) ? void (0) : __assert_fail
("c <= 1", "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 2297, __extension__ __PRETTY_FUNCTION__))
;
2298
2299 for (unsigned i = 0; i < parts; i++) {
2300 WordType l = dst[i];
2301 if (c) {
2302 dst[i] += rhs[i] + 1;
2303 c = (dst[i] <= l);
2304 } else {
2305 dst[i] += rhs[i];
2306 c = (dst[i] < l);
2307 }
2308 }
2309
2310 return c;
2311}
2312
2313/// This function adds a single "word" integer, src, to the multiple
2314/// "word" integer array, dst[]. dst[] is modified to reflect the addition and
2315/// 1 is returned if there is a carry out, otherwise 0 is returned.
2316/// @returns the carry of the addition.
2317APInt::WordType APInt::tcAddPart(WordType *dst, WordType src,
2318 unsigned parts) {
2319 for (unsigned i = 0; i < parts; ++i) {
2320 dst[i] += src;
2321 if (dst[i] >= src)
2322 return 0; // No need to carry so exit early.
2323 src = 1; // Carry one to next digit.
2324 }
2325
2326 return 1;
2327}
2328
2329/* DST -= RHS + C where C is zero or one. Returns the carry flag. */
2330APInt::WordType APInt::tcSubtract(WordType *dst, const WordType *rhs,
2331 WordType c, unsigned parts) {
2332 assert(c <= 1)(static_cast <bool> (c <= 1) ? void (0) : __assert_fail
("c <= 1", "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 2332, __extension__ __PRETTY_FUNCTION__))
;
2333
2334 for (unsigned i = 0; i < parts; i++) {
2335 WordType l = dst[i];
2336 if (c) {
2337 dst[i] -= rhs[i] + 1;
2338 c = (dst[i] >= l);
2339 } else {
2340 dst[i] -= rhs[i];
2341 c = (dst[i] > l);
2342 }
2343 }
2344
2345 return c;
2346}
2347
2348/// This function subtracts a single "word" (64-bit word), src, from
2349/// the multi-word integer array, dst[], propagating the borrowed 1 value until
2350/// no further borrowing is needed or it runs out of "words" in dst. The result
2351/// is 1 if "borrowing" exhausted the digits in dst, or 0 if dst was not
2352/// exhausted. In other words, if src > dst then this function returns 1,
2353/// otherwise 0.
2354/// @returns the borrow out of the subtraction
2355APInt::WordType APInt::tcSubtractPart(WordType *dst, WordType src,
2356 unsigned parts) {
2357 for (unsigned i = 0; i < parts; ++i) {
2358 WordType Dst = dst[i];
2359 dst[i] -= src;
2360 if (src <= Dst)
2361 return 0; // No need to borrow so exit early.
2362 src = 1; // We have to "borrow 1" from next "word"
2363 }
2364
2365 return 1;
2366}
2367
2368/* Negate a bignum in-place. */
2369void APInt::tcNegate(WordType *dst, unsigned parts) {
2370 tcComplement(dst, parts);
2371 tcIncrement(dst, parts);
2372}
2373
2374/* DST += SRC * MULTIPLIER + CARRY if add is true
2375 DST = SRC * MULTIPLIER + CARRY if add is false
2376
2377 Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC
2378 they must start at the same point, i.e. DST == SRC.
2379
2380 If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
2381 returned. Otherwise DST is filled with the least significant
2382 DSTPARTS parts of the result, and if all of the omitted higher
2383 parts were zero return zero, otherwise overflow occurred and
2384 return one. */
2385int APInt::tcMultiplyPart(WordType *dst, const WordType *src,
2386 WordType multiplier, WordType carry,
2387 unsigned srcParts, unsigned dstParts,
2388 bool add) {
2389 /* Otherwise our writes of DST kill our later reads of SRC. */
2390 assert(dst <= src || dst >= src + srcParts)(static_cast <bool> (dst <= src || dst >= src + srcParts
) ? void (0) : __assert_fail ("dst <= src || dst >= src + srcParts"
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 2390, __extension__ __PRETTY_FUNCTION__))
;
2391 assert(dstParts <= srcParts + 1)(static_cast <bool> (dstParts <= srcParts + 1) ? void
(0) : __assert_fail ("dstParts <= srcParts + 1", "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 2391, __extension__ __PRETTY_FUNCTION__))
;
2392
2393 /* N loops; minimum of dstParts and srcParts. */
2394 unsigned n = std::min(dstParts, srcParts);
2395
2396 for (unsigned i = 0; i < n; i++) {
2397 WordType low, mid, high, srcPart;
2398
2399 /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
2400
2401 This cannot overflow, because
2402
2403 (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
2404
2405 which is less than n^2. */
2406
2407 srcPart = src[i];
2408
2409 if (multiplier == 0 || srcPart == 0) {
2410 low = carry;
2411 high = 0;
2412 } else {
2413 low = lowHalf(srcPart) * lowHalf(multiplier);
2414 high = highHalf(srcPart) * highHalf(multiplier);
2415
2416 mid = lowHalf(srcPart) * highHalf(multiplier);
2417 high += highHalf(mid);
2418 mid <<= APINT_BITS_PER_WORD / 2;
2419 if (low + mid < low)
2420 high++;
2421 low += mid;
2422
2423 mid = highHalf(srcPart) * lowHalf(multiplier);
2424 high += highHalf(mid);
2425 mid <<= APINT_BITS_PER_WORD / 2;
2426 if (low + mid < low)
2427 high++;
2428 low += mid;
2429
2430 /* Now add carry. */
2431 if (low + carry < low)
2432 high++;
2433 low += carry;
2434 }
2435
2436 if (add) {
2437 /* And now DST[i], and store the new low part there. */
2438 if (low + dst[i] < low)
2439 high++;
2440 dst[i] += low;
2441 } else
2442 dst[i] = low;
2443
2444 carry = high;
2445 }
2446
2447 if (srcParts < dstParts) {
2448 /* Full multiplication, there is no overflow. */
2449 assert(srcParts + 1 == dstParts)(static_cast <bool> (srcParts + 1 == dstParts) ? void (
0) : __assert_fail ("srcParts + 1 == dstParts", "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 2449, __extension__ __PRETTY_FUNCTION__))
;
2450 dst[srcParts] = carry;
2451 return 0;
2452 }
2453
2454 /* We overflowed if there is carry. */
2455 if (carry)
2456 return 1;
2457
2458 /* We would overflow if any significant unwritten parts would be
2459 non-zero. This is true if any remaining src parts are non-zero
2460 and the multiplier is non-zero. */
2461 if (multiplier)
2462 for (unsigned i = dstParts; i < srcParts; i++)
2463 if (src[i])
2464 return 1;
2465
2466 /* We fitted in the narrow destination. */
2467 return 0;
2468}
2469
2470/* DST = LHS * RHS, where DST has the same width as the operands and
2471 is filled with the least significant parts of the result. Returns
2472 one if overflow occurred, otherwise zero. DST must be disjoint
2473 from both operands. */
2474int APInt::tcMultiply(WordType *dst, const WordType *lhs,
2475 const WordType *rhs, unsigned parts) {
2476 assert(dst != lhs && dst != rhs)(static_cast <bool> (dst != lhs && dst != rhs) ?
void (0) : __assert_fail ("dst != lhs && dst != rhs"
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 2476, __extension__ __PRETTY_FUNCTION__))
;
2477
2478 int overflow = 0;
2479 tcSet(dst, 0, parts);
2480
2481 for (unsigned i = 0; i < parts; i++)
2482 overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
2483 parts - i, true);
2484
2485 return overflow;
2486}
2487
2488/// DST = LHS * RHS, where DST has width the sum of the widths of the
2489/// operands. No overflow occurs. DST must be disjoint from both operands.
2490void APInt::tcFullMultiply(WordType *dst, const WordType *lhs,
2491 const WordType *rhs, unsigned lhsParts,
2492 unsigned rhsParts) {
2493 /* Put the narrower number on the LHS for less loops below. */
2494 if (lhsParts > rhsParts)
2495 return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
2496
2497 assert(dst != lhs && dst != rhs)(static_cast <bool> (dst != lhs && dst != rhs) ?
void (0) : __assert_fail ("dst != lhs && dst != rhs"
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 2497, __extension__ __PRETTY_FUNCTION__))
;
2498
2499 tcSet(dst, 0, rhsParts);
2500
2501 for (unsigned i = 0; i < lhsParts; i++)
2502 tcMultiplyPart(&dst[i], rhs, lhs[i], 0, rhsParts, rhsParts + 1, true);
2503}
2504
2505/* If RHS is zero LHS and REMAINDER are left unchanged, return one.
2506 Otherwise set LHS to LHS / RHS with the fractional part discarded,
2507 set REMAINDER to the remainder, return zero. i.e.
2508
2509 OLD_LHS = RHS * LHS + REMAINDER
2510
2511 SCRATCH is a bignum of the same size as the operands and result for
2512 use by the routine; its contents need not be initialized and are
2513 destroyed. LHS, REMAINDER and SCRATCH must be distinct.
2514*/
2515int APInt::tcDivide(WordType *lhs, const WordType *rhs,
2516 WordType *remainder, WordType *srhs,
2517 unsigned parts) {
2518 assert(lhs != remainder && lhs != srhs && remainder != srhs)(static_cast <bool> (lhs != remainder && lhs !=
srhs && remainder != srhs) ? void (0) : __assert_fail
("lhs != remainder && lhs != srhs && remainder != srhs"
, "/build/llvm-toolchain-snapshot-7~svn326425/lib/Support/APInt.cpp"
, 2518, __extension__ __PRETTY_FUNCTION__))
;
2519
2520 unsigned shiftCount = tcMSB(rhs, parts) + 1;
2521 if (shiftCount == 0)
2522 return true;
2523
2524 shiftCount = parts * APINT_BITS_PER_WORD - shiftCount;
2525 unsigned n = shiftCount / APINT_BITS_PER_WORD;
2526 WordType mask = (WordType) 1 << (shiftCount % APINT_BITS_PER_WORD);
2527
2528 tcAssign(srhs, rhs, parts);
2529 tcShiftLeft(srhs, parts, shiftCount);
2530 tcAssign(remainder, lhs, parts);
2531 tcSet(lhs, 0, parts);
2532
2533 /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
2534 the total. */
2535 for (;;) {
2536 int compare = tcCompare(remainder, srhs, parts);
2537 if (compare >= 0) {
2538 tcSubtract(remainder, srhs, 0, parts);
2539 lhs[n] |= mask;
2540 }
2541
2542 if (shiftCount == 0)
2543 break;
2544 shiftCount--;
2545 tcShiftRight(srhs, parts, 1);
2546 if ((mask >>= 1) == 0) {
2547 mask = (WordType) 1 << (APINT_BITS_PER_WORD - 1);
2548 n--;
2549 }
2550 }
2551
2552 return false;
2553}
2554
2555/// Shift a bignum left Cound bits in-place. Shifted in bits are zero. There are
2556/// no restrictions on Count.
2557void APInt::tcShiftLeft(WordType *Dst, unsigned Words, unsigned Count) {
2558 // Don't bother performing a no-op shift.
2559 if (!Count)
2560 return;
2561
2562 // WordShift is the inter-part shift; BitShift is the intra-part shift.
2563 unsigned WordShift = std::min(Count / APINT_BITS_PER_WORD, Words);
2564 unsigned BitShift = Count % APINT_BITS_PER_WORD;
2565
2566 // Fastpath for moving by whole words.
2567 if (BitShift == 0) {
2568 std::memmove(Dst + WordShift, Dst, (Words - WordShift) * APINT_WORD_SIZE);
2569 } else {
2570 while (Words-- > WordShift) {
2571 Dst[Words] = Dst[Words - WordShift] << BitShift;
2572 if (Words > WordShift)
2573 Dst[Words] |=
2574 Dst[Words - WordShift - 1] >> (APINT_BITS_PER_WORD - BitShift);
2575 }
2576 }
2577
2578 // Fill in the remainder with 0s.
2579 std::memset(Dst, 0, WordShift * APINT_WORD_SIZE);
2580}
2581
2582/// Shift a bignum right Count bits in-place. Shifted in bits are zero. There
2583/// are no restrictions on Count.
2584void APInt::tcShiftRight(WordType *Dst, unsigned Words, unsigned Count) {
2585 // Don't bother performing a no-op shift.
2586 if (!Count)
2587 return;
2588
2589 // WordShift is the inter-part shift; BitShift is the intra-part shift.
2590 unsigned WordShift = std::min(Count / APINT_BITS_PER_WORD, Words);
2591 unsigned BitShift = Count % APINT_BITS_PER_WORD;
2592
2593 unsigned WordsToMove = Words - WordShift;
2594 // Fastpath for moving by whole words.
2595 if (BitShift == 0) {
2596 std::memmove(Dst, Dst + WordShift, WordsToMove * APINT_WORD_SIZE);
2597 } else {
2598 for (unsigned i = 0; i != WordsToMove; ++i) {
2599 Dst[i] = Dst[i + WordShift] >> BitShift;
2600 if (i + 1 != WordsToMove)
2601 Dst[i] |= Dst[i + WordShift + 1] << (APINT_BITS_PER_WORD - BitShift);
2602 }
2603 }
2604
2605 // Fill in the remainder with 0s.
2606 std::memset(Dst + WordsToMove, 0, WordShift * APINT_WORD_SIZE);
2607}
2608
2609/* Bitwise and of two bignums. */
2610void APInt::tcAnd(WordType *dst, const WordType *rhs, unsigned parts) {
2611 for (unsigned i = 0; i < parts; i++)
2612 dst[i] &= rhs[i];
2613}
2614
2615/* Bitwise inclusive or of two bignums. */
2616void APInt::tcOr(WordType *dst, const WordType *rhs, unsigned parts) {
2617 for (unsigned i = 0; i < parts; i++)
2618 dst[i] |= rhs[i];
2619}
2620
2621/* Bitwise exclusive or of two bignums. */
2622void APInt::tcXor(WordType *dst, const WordType *rhs, unsigned parts) {
2623 for (unsigned i = 0; i < parts; i++)
2624 dst[i] ^= rhs[i];
2625}
2626
2627/* Complement a bignum in-place. */
2628void APInt::tcComplement(WordType *dst, unsigned parts) {
2629 for (unsigned i = 0; i < parts; i++)
2630 dst[i] = ~dst[i];
2631}
2632
2633/* Comparison (unsigned) of two bignums. */
2634int APInt::tcCompare(const WordType *lhs, const WordType *rhs,
2635 unsigned parts) {
2636 while (parts) {
2637 parts--;
2638 if (lhs[parts] != rhs[parts])
2639 return (lhs[parts] > rhs[parts]) ? 1 : -1;
2640 }
2641
2642 return 0;
2643}
2644
2645/* Set the least significant BITS bits of a bignum, clear the
2646 rest. */
2647void APInt::tcSetLeastSignificantBits(WordType *dst, unsigned parts,
2648 unsigned bits) {
2649 unsigned i = 0;
2650 while (bits > APINT_BITS_PER_WORD) {
2651 dst[i++] = ~(WordType) 0;
2652 bits -= APINT_BITS_PER_WORD;
2653 }
2654
2655 if (bits)
2656 dst[i++] = ~(WordType) 0 >> (APINT_BITS_PER_WORD - bits);
2657
2658 while (i < parts)
2659 dst[i++] = 0;
2660}

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