Bug Summary

File:include/llvm/ADT/APInt.h
Warning:line 1560, column 12
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~svn338205/build-llvm/lib/Support -I /build/llvm-toolchain-snapshot-7~svn338205/lib/Support -I /build/llvm-toolchain-snapshot-7~svn338205/build-llvm/include -I /build/llvm-toolchain-snapshot-7~svn338205/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/x86_64-linux-gnu/c++/8 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/x86_64-linux-gnu/c++/8 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/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/lib/gcc/x86_64-linux-gnu/8/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-class-memaccess -Wno-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-7~svn338205/build-llvm/lib/Support -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-07-29-043837-17923-1 -x c++ /build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp -faddrsig

/build/llvm-toolchain-snapshot-7~svn338205/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/Config/llvm-config.h"
22#include "llvm/Support/Debug.h"
23#include "llvm/Support/ErrorHandling.h"
24#include "llvm/Support/MathExtras.h"
25#include "llvm/Support/raw_ostream.h"
26#include <climits>
27#include <cmath>
28#include <cstdlib>
29#include <cstring>
30using namespace llvm;
31
32#define DEBUG_TYPE"apint" "apint"
33
34/// A utility function for allocating memory, checking for allocation failures,
35/// and ensuring the contents are zeroed.
36inline static uint64_t* getClearedMemory(unsigned numWords) {
37 uint64_t *result = new uint64_t[numWords];
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 return new uint64_t[numWords];
6
Memory is allocated
46}
47
48/// A utility function that converts a character to a digit.
49inline static unsigned getDigit(char cdigit, uint8_t radix) {
50 unsigned r;
51
52 if (radix == 16 || radix == 36) {
53 r = cdigit - '0';
54 if (r <= 9)
55 return r;
56
57 r = cdigit - 'A';
58 if (r <= radix - 11U)
59 return r + 10;
60
61 r = cdigit - 'a';
62 if (r <= radix - 11U)
63 return r + 10;
64
65 radix = 10;
66 }
67
68 r = cdigit - '0';
69 if (r < radix)
70 return r;
71
72 return -1U;
73}
74
75
76void APInt::initSlowCase(uint64_t val, bool isSigned) {
77 U.pVal = getClearedMemory(getNumWords());
78 U.pVal[0] = val;
79 if (isSigned && int64_t(val) < 0)
80 for (unsigned i = 1; i < getNumWords(); ++i)
81 U.pVal[i] = WORD_MAX;
82 clearUnusedBits();
83}
84
85void APInt::initSlowCase(const APInt& that) {
86 U.pVal = getMemory(getNumWords());
5
Calling 'getMemory'
7
Returned allocated memory
87 memcpy(U.pVal, that.U.pVal, getNumWords() * APINT_WORD_SIZE);
88}
89
90void APInt::initFromArray(ArrayRef<uint64_t> bigVal) {
91 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~svn338205/lib/Support/APInt.cpp"
, 91, __extension__ __PRETTY_FUNCTION__))
;
92 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~svn338205/lib/Support/APInt.cpp"
, 92, __extension__ __PRETTY_FUNCTION__))
;
93 if (isSingleWord())
94 U.VAL = bigVal[0];
95 else {
96 // Get memory, cleared to 0
97 U.pVal = getClearedMemory(getNumWords());
98 // Calculate the number of words to copy
99 unsigned words = std::min<unsigned>(bigVal.size(), getNumWords());
100 // Copy the words from bigVal to pVal
101 memcpy(U.pVal, bigVal.data(), words * APINT_WORD_SIZE);
102 }
103 // Make sure unused high bits are cleared
104 clearUnusedBits();
105}
106
107APInt::APInt(unsigned numBits, ArrayRef<uint64_t> bigVal)
108 : BitWidth(numBits) {
109 initFromArray(bigVal);
110}
111
112APInt::APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[])
113 : BitWidth(numBits) {
114 initFromArray(makeArrayRef(bigVal, numWords));
115}
116
117APInt::APInt(unsigned numbits, StringRef Str, uint8_t radix)
118 : BitWidth(numbits) {
119 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~svn338205/lib/Support/APInt.cpp"
, 119, __extension__ __PRETTY_FUNCTION__))
;
120 fromString(numbits, Str, radix);
121}
122
123void APInt::reallocate(unsigned NewBitWidth) {
124 // If the number of words is the same we can just change the width and stop.
125 if (getNumWords() == getNumWords(NewBitWidth)) {
126 BitWidth = NewBitWidth;
127 return;
128 }
129
130 // If we have an allocation, delete it.
131 if (!isSingleWord())
132 delete [] U.pVal;
133
134 // Update BitWidth.
135 BitWidth = NewBitWidth;
136
137 // If we are supposed to have an allocation, create it.
138 if (!isSingleWord())
139 U.pVal = getMemory(getNumWords());
140}
141
142void APInt::AssignSlowCase(const APInt& RHS) {
143 // Don't do anything for X = X
144 if (this == &RHS)
145 return;
146
147 // Adjust the bit width and handle allocations as necessary.
148 reallocate(RHS.getBitWidth());
149
150 // Copy the data.
151 if (isSingleWord())
152 U.VAL = RHS.U.VAL;
153 else
154 memcpy(U.pVal, RHS.U.pVal, getNumWords() * APINT_WORD_SIZE);
155}
156
157/// This method 'profiles' an APInt for use with FoldingSet.
158void APInt::Profile(FoldingSetNodeID& ID) const {
159 ID.AddInteger(BitWidth);
160
161 if (isSingleWord()) {
162 ID.AddInteger(U.VAL);
163 return;
164 }
165
166 unsigned NumWords = getNumWords();
167 for (unsigned i = 0; i < NumWords; ++i)
168 ID.AddInteger(U.pVal[i]);
169}
170
171/// Prefix increment operator. Increments the APInt by one.
172APInt& APInt::operator++() {
173 if (isSingleWord())
174 ++U.VAL;
175 else
176 tcIncrement(U.pVal, getNumWords());
177 return clearUnusedBits();
178}
179
180/// Prefix decrement operator. Decrements the APInt by one.
181APInt& APInt::operator--() {
182 if (isSingleWord())
183 --U.VAL;
184 else
185 tcDecrement(U.pVal, getNumWords());
186 return clearUnusedBits();
187}
188
189/// Adds the RHS APint to this APInt.
190/// @returns this, after addition of RHS.
191/// Addition assignment operator.
192APInt& APInt::operator+=(const APInt& RHS) {
193 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~svn338205/lib/Support/APInt.cpp"
, 193, __extension__ __PRETTY_FUNCTION__))
;
194 if (isSingleWord())
195 U.VAL += RHS.U.VAL;
196 else
197 tcAdd(U.pVal, RHS.U.pVal, 0, getNumWords());
198 return clearUnusedBits();
199}
200
201APInt& APInt::operator+=(uint64_t RHS) {
202 if (isSingleWord())
203 U.VAL += RHS;
204 else
205 tcAddPart(U.pVal, RHS, getNumWords());
206 return clearUnusedBits();
207}
208
209/// Subtracts the RHS APInt from this APInt
210/// @returns this, after subtraction
211/// Subtraction assignment operator.
212APInt& APInt::operator-=(const APInt& RHS) {
213 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~svn338205/lib/Support/APInt.cpp"
, 213, __extension__ __PRETTY_FUNCTION__))
;
214 if (isSingleWord())
215 U.VAL -= RHS.U.VAL;
216 else
217 tcSubtract(U.pVal, RHS.U.pVal, 0, getNumWords());
218 return clearUnusedBits();
219}
220
221APInt& APInt::operator-=(uint64_t RHS) {
222 if (isSingleWord())
223 U.VAL -= RHS;
224 else
225 tcSubtractPart(U.pVal, RHS, getNumWords());
226 return clearUnusedBits();
227}
228
229APInt APInt::operator*(const APInt& RHS) const {
230 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~svn338205/lib/Support/APInt.cpp"
, 230, __extension__ __PRETTY_FUNCTION__))
;
231 if (isSingleWord())
232 return APInt(BitWidth, U.VAL * RHS.U.VAL);
233
234 APInt Result(getMemory(getNumWords()), getBitWidth());
235
236 tcMultiply(Result.U.pVal, U.pVal, RHS.U.pVal, getNumWords());
237
238 Result.clearUnusedBits();
239 return Result;
240}
241
242void APInt::AndAssignSlowCase(const APInt& RHS) {
243 tcAnd(U.pVal, RHS.U.pVal, getNumWords());
244}
245
246void APInt::OrAssignSlowCase(const APInt& RHS) {
247 tcOr(U.pVal, RHS.U.pVal, getNumWords());
248}
249
250void APInt::XorAssignSlowCase(const APInt& RHS) {
251 tcXor(U.pVal, RHS.U.pVal, getNumWords());
252}
253
254APInt& APInt::operator*=(const APInt& RHS) {
255 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~svn338205/lib/Support/APInt.cpp"
, 255, __extension__ __PRETTY_FUNCTION__))
;
256 *this = *this * RHS;
257 return *this;
258}
259
260APInt& APInt::operator*=(uint64_t RHS) {
261 if (isSingleWord()) {
262 U.VAL *= RHS;
263 } else {
264 unsigned NumWords = getNumWords();
265 tcMultiplyPart(U.pVal, U.pVal, RHS, 0, NumWords, NumWords, false);
266 }
267 return clearUnusedBits();
268}
269
270bool APInt::EqualSlowCase(const APInt& RHS) const {
271 return std::equal(U.pVal, U.pVal + getNumWords(), RHS.U.pVal);
272}
273
274int APInt::compare(const APInt& RHS) const {
275 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~svn338205/lib/Support/APInt.cpp"
, 275, __extension__ __PRETTY_FUNCTION__))
;
276 if (isSingleWord())
277 return U.VAL < RHS.U.VAL ? -1 : U.VAL > RHS.U.VAL;
278
279 return tcCompare(U.pVal, RHS.U.pVal, getNumWords());
280}
281
282int APInt::compareSigned(const APInt& RHS) const {
283 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~svn338205/lib/Support/APInt.cpp"
, 283, __extension__ __PRETTY_FUNCTION__))
;
284 if (isSingleWord()) {
285 int64_t lhsSext = SignExtend64(U.VAL, BitWidth);
286 int64_t rhsSext = SignExtend64(RHS.U.VAL, BitWidth);
287 return lhsSext < rhsSext ? -1 : lhsSext > rhsSext;
288 }
289
290 bool lhsNeg = isNegative();
291 bool rhsNeg = RHS.isNegative();
292
293 // If the sign bits don't match, then (LHS < RHS) if LHS is negative
294 if (lhsNeg != rhsNeg)
295 return lhsNeg ? -1 : 1;
296
297 // Otherwise we can just use an unsigned comparison, because even negative
298 // numbers compare correctly this way if both have the same signed-ness.
299 return tcCompare(U.pVal, RHS.U.pVal, getNumWords());
300}
301
302void APInt::setBitsSlowCase(unsigned loBit, unsigned hiBit) {
303 unsigned loWord = whichWord(loBit);
304 unsigned hiWord = whichWord(hiBit);
305
306 // Create an initial mask for the low word with zeros below loBit.
307 uint64_t loMask = WORD_MAX << whichBit(loBit);
308
309 // If hiBit is not aligned, we need a high mask.
310 unsigned hiShiftAmt = whichBit(hiBit);
311 if (hiShiftAmt != 0) {
312 // Create a high mask with zeros above hiBit.
313 uint64_t hiMask = WORD_MAX >> (APINT_BITS_PER_WORD - hiShiftAmt);
314 // If loWord and hiWord are equal, then we combine the masks. Otherwise,
315 // set the bits in hiWord.
316 if (hiWord == loWord)
317 loMask &= hiMask;
318 else
319 U.pVal[hiWord] |= hiMask;
320 }
321 // Apply the mask to the low word.
322 U.pVal[loWord] |= loMask;
323
324 // Fill any words between loWord and hiWord with all ones.
325 for (unsigned word = loWord + 1; word < hiWord; ++word)
326 U.pVal[word] = WORD_MAX;
327}
328
329/// Toggle every bit to its opposite value.
330void APInt::flipAllBitsSlowCase() {
331 tcComplement(U.pVal, getNumWords());
332 clearUnusedBits();
333}
334
335/// Toggle a given bit to its opposite value whose position is given
336/// as "bitPosition".
337/// Toggles a given bit to its opposite value.
338void APInt::flipBit(unsigned bitPosition) {
339 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~svn338205/lib/Support/APInt.cpp"
, 339, __extension__ __PRETTY_FUNCTION__))
;
340 if ((*this)[bitPosition]) clearBit(bitPosition);
341 else setBit(bitPosition);
342}
343
344void APInt::insertBits(const APInt &subBits, unsigned bitPosition) {
345 unsigned subBitWidth = subBits.getBitWidth();
346 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~svn338205/lib/Support/APInt.cpp"
, 347, __extension__ __PRETTY_FUNCTION__))
347 "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~svn338205/lib/Support/APInt.cpp"
, 347, __extension__ __PRETTY_FUNCTION__))
;
348
349 // Insertion is a direct copy.
350 if (subBitWidth == BitWidth) {
351 *this = subBits;
352 return;
353 }
354
355 // Single word result can be done as a direct bitmask.
356 if (isSingleWord()) {
357 uint64_t mask = WORD_MAX >> (APINT_BITS_PER_WORD - subBitWidth);
358 U.VAL &= ~(mask << bitPosition);
359 U.VAL |= (subBits.U.VAL << bitPosition);
360 return;
361 }
362
363 unsigned loBit = whichBit(bitPosition);
364 unsigned loWord = whichWord(bitPosition);
365 unsigned hi1Word = whichWord(bitPosition + subBitWidth - 1);
366
367 // Insertion within a single word can be done as a direct bitmask.
368 if (loWord == hi1Word) {
369 uint64_t mask = WORD_MAX >> (APINT_BITS_PER_WORD - subBitWidth);
370 U.pVal[loWord] &= ~(mask << loBit);
371 U.pVal[loWord] |= (subBits.U.VAL << loBit);
372 return;
373 }
374
375 // Insert on word boundaries.
376 if (loBit == 0) {
377 // Direct copy whole words.
378 unsigned numWholeSubWords = subBitWidth / APINT_BITS_PER_WORD;
379 memcpy(U.pVal + loWord, subBits.getRawData(),
380 numWholeSubWords * APINT_WORD_SIZE);
381
382 // Mask+insert remaining bits.
383 unsigned remainingBits = subBitWidth % APINT_BITS_PER_WORD;
384 if (remainingBits != 0) {
385 uint64_t mask = WORD_MAX >> (APINT_BITS_PER_WORD - remainingBits);
386 U.pVal[hi1Word] &= ~mask;
387 U.pVal[hi1Word] |= subBits.getWord(subBitWidth - 1);
388 }
389 return;
390 }
391
392 // General case - set/clear individual bits in dst based on src.
393 // TODO - there is scope for optimization here, but at the moment this code
394 // path is barely used so prefer readability over performance.
395 for (unsigned i = 0; i != subBitWidth; ++i) {
396 if (subBits[i])
397 setBit(bitPosition + i);
398 else
399 clearBit(bitPosition + i);
400 }
401}
402
403APInt APInt::extractBits(unsigned numBits, unsigned bitPosition) const {
404 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~svn338205/lib/Support/APInt.cpp"
, 404, __extension__ __PRETTY_FUNCTION__))
;
405 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~svn338205/lib/Support/APInt.cpp"
, 406, __extension__ __PRETTY_FUNCTION__))
406 "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~svn338205/lib/Support/APInt.cpp"
, 406, __extension__ __PRETTY_FUNCTION__))
;
407
408 if (isSingleWord())
409 return APInt(numBits, U.VAL >> bitPosition);
410
411 unsigned loBit = whichBit(bitPosition);
412 unsigned loWord = whichWord(bitPosition);
413 unsigned hiWord = whichWord(bitPosition + numBits - 1);
414
415 // Single word result extracting bits from a single word source.
416 if (loWord == hiWord)
417 return APInt(numBits, U.pVal[loWord] >> loBit);
418
419 // Extracting bits that start on a source word boundary can be done
420 // as a fast memory copy.
421 if (loBit == 0)
422 return APInt(numBits, makeArrayRef(U.pVal + loWord, 1 + hiWord - loWord));
423
424 // General case - shift + copy source words directly into place.
425 APInt Result(numBits, 0);
426 unsigned NumSrcWords = getNumWords();
427 unsigned NumDstWords = Result.getNumWords();
428
429 uint64_t *DestPtr = Result.isSingleWord() ? &Result.U.VAL : Result.U.pVal;
430 for (unsigned word = 0; word < NumDstWords; ++word) {
431 uint64_t w0 = U.pVal[loWord + word];
432 uint64_t w1 =
433 (loWord + word + 1) < NumSrcWords ? U.pVal[loWord + word + 1] : 0;
434 DestPtr[word] = (w0 >> loBit) | (w1 << (APINT_BITS_PER_WORD - loBit));
435 }
436
437 return Result.clearUnusedBits();
438}
439
440unsigned APInt::getBitsNeeded(StringRef str, uint8_t radix) {
441 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~svn338205/lib/Support/APInt.cpp"
, 441, __extension__ __PRETTY_FUNCTION__))
;
442 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~svn338205/lib/Support/APInt.cpp"
, 444, __extension__ __PRETTY_FUNCTION__))
443 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~svn338205/lib/Support/APInt.cpp"
, 444, __extension__ __PRETTY_FUNCTION__))
444 "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~svn338205/lib/Support/APInt.cpp"
, 444, __extension__ __PRETTY_FUNCTION__))
;
445
446 size_t slen = str.size();
447
448 // Each computation below needs to know if it's negative.
449 StringRef::iterator p = str.begin();
450 unsigned isNegative = *p == '-';
451 if (*p == '-' || *p == '+') {
452 p++;
453 slen--;
454 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~svn338205/lib/Support/APInt.cpp"
, 454, __extension__ __PRETTY_FUNCTION__))
;
455 }
456
457 // For radixes of power-of-two values, the bits required is accurately and
458 // easily computed
459 if (radix == 2)
460 return slen + isNegative;
461 if (radix == 8)
462 return slen * 3 + isNegative;
463 if (radix == 16)
464 return slen * 4 + isNegative;
465
466 // FIXME: base 36
467
468 // This is grossly inefficient but accurate. We could probably do something
469 // with a computation of roughly slen*64/20 and then adjust by the value of
470 // the first few digits. But, I'm not sure how accurate that could be.
471
472 // Compute a sufficient number of bits that is always large enough but might
473 // be too large. This avoids the assertion in the constructor. This
474 // calculation doesn't work appropriately for the numbers 0-9, so just use 4
475 // bits in that case.
476 unsigned sufficient
477 = radix == 10? (slen == 1 ? 4 : slen * 64/18)
478 : (slen == 1 ? 7 : slen * 16/3);
479
480 // Convert to the actual binary value.
481 APInt tmp(sufficient, StringRef(p, slen), radix);
482
483 // Compute how many bits are required. If the log is infinite, assume we need
484 // just bit.
485 unsigned log = tmp.logBase2();
486 if (log == (unsigned)-1) {
487 return isNegative + 1;
488 } else {
489 return isNegative + log + 1;
490 }
491}
492
493hash_code llvm::hash_value(const APInt &Arg) {
494 if (Arg.isSingleWord())
495 return hash_combine(Arg.U.VAL);
496
497 return hash_combine_range(Arg.U.pVal, Arg.U.pVal + Arg.getNumWords());
498}
499
500bool APInt::isSplat(unsigned SplatSizeInBits) const {
501 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~svn338205/lib/Support/APInt.cpp"
, 502, __extension__ __PRETTY_FUNCTION__))
502 "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~svn338205/lib/Support/APInt.cpp"
, 502, __extension__ __PRETTY_FUNCTION__))
;
503 // We can check that all parts of an integer are equal by making use of a
504 // little trick: rotate and check if it's still the same value.
505 return *this == rotl(SplatSizeInBits);
506}
507
508/// This function returns the high "numBits" bits of this APInt.
509APInt APInt::getHiBits(unsigned numBits) const {
510 return this->lshr(BitWidth - numBits);
511}
512
513/// This function returns the low "numBits" bits of this APInt.
514APInt APInt::getLoBits(unsigned numBits) const {
515 APInt Result(getLowBitsSet(BitWidth, numBits));
516 Result &= *this;
517 return Result;
518}
519
520/// Return a value containing V broadcasted over NewLen bits.
521APInt APInt::getSplat(unsigned NewLen, const APInt &V) {
522 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~svn338205/lib/Support/APInt.cpp"
, 522, __extension__ __PRETTY_FUNCTION__))
;
523
524 APInt Val = V.zextOrSelf(NewLen);
525 for (unsigned I = V.getBitWidth(); I < NewLen; I <<= 1)
526 Val |= Val << I;
527
528 return Val;
529}
530
531unsigned APInt::countLeadingZerosSlowCase() const {
532 unsigned Count = 0;
533 for (int i = getNumWords()-1; i >= 0; --i) {
534 uint64_t V = U.pVal[i];
535 if (V == 0)
536 Count += APINT_BITS_PER_WORD;
537 else {
538 Count += llvm::countLeadingZeros(V);
539 break;
540 }
541 }
542 // Adjust for unused bits in the most significant word (they are zero).
543 unsigned Mod = BitWidth % APINT_BITS_PER_WORD;
544 Count -= Mod > 0 ? APINT_BITS_PER_WORD - Mod : 0;
545 return Count;
546}
547
548unsigned APInt::countLeadingOnesSlowCase() const {
549 unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD;
550 unsigned shift;
551 if (!highWordBits) {
552 highWordBits = APINT_BITS_PER_WORD;
553 shift = 0;
554 } else {
555 shift = APINT_BITS_PER_WORD - highWordBits;
556 }
557 int i = getNumWords() - 1;
558 unsigned Count = llvm::countLeadingOnes(U.pVal[i] << shift);
559 if (Count == highWordBits) {
560 for (i--; i >= 0; --i) {
561 if (U.pVal[i] == WORD_MAX)
562 Count += APINT_BITS_PER_WORD;
563 else {
564 Count += llvm::countLeadingOnes(U.pVal[i]);
565 break;
566 }
567 }
568 }
569 return Count;
570}
571
572unsigned APInt::countTrailingZerosSlowCase() const {
573 unsigned Count = 0;
574 unsigned i = 0;
575 for (; i < getNumWords() && U.pVal[i] == 0; ++i)
576 Count += APINT_BITS_PER_WORD;
577 if (i < getNumWords())
578 Count += llvm::countTrailingZeros(U.pVal[i]);
579 return std::min(Count, BitWidth);
580}
581
582unsigned APInt::countTrailingOnesSlowCase() const {
583 unsigned Count = 0;
584 unsigned i = 0;
585 for (; i < getNumWords() && U.pVal[i] == WORD_MAX; ++i)
586 Count += APINT_BITS_PER_WORD;
587 if (i < getNumWords())
588 Count += llvm::countTrailingOnes(U.pVal[i]);
589 assert(Count <= BitWidth)(static_cast <bool> (Count <= BitWidth) ? void (0) :
__assert_fail ("Count <= BitWidth", "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 589, __extension__ __PRETTY_FUNCTION__))
;
590 return Count;
591}
592
593unsigned APInt::countPopulationSlowCase() const {
594 unsigned Count = 0;
595 for (unsigned i = 0; i < getNumWords(); ++i)
596 Count += llvm::countPopulation(U.pVal[i]);
597 return Count;
598}
599
600bool APInt::intersectsSlowCase(const APInt &RHS) const {
601 for (unsigned i = 0, e = getNumWords(); i != e; ++i)
602 if ((U.pVal[i] & RHS.U.pVal[i]) != 0)
603 return true;
604
605 return false;
606}
607
608bool APInt::isSubsetOfSlowCase(const APInt &RHS) const {
609 for (unsigned i = 0, e = getNumWords(); i != e; ++i)
610 if ((U.pVal[i] & ~RHS.U.pVal[i]) != 0)
611 return false;
612
613 return true;
614}
615
616APInt APInt::byteSwap() const {
617 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~svn338205/lib/Support/APInt.cpp"
, 617, __extension__ __PRETTY_FUNCTION__))
;
618 if (BitWidth == 16)
619 return APInt(BitWidth, ByteSwap_16(uint16_t(U.VAL)));
620 if (BitWidth == 32)
621 return APInt(BitWidth, ByteSwap_32(unsigned(U.VAL)));
622 if (BitWidth == 48) {
623 unsigned Tmp1 = unsigned(U.VAL >> 16);
624 Tmp1 = ByteSwap_32(Tmp1);
625 uint16_t Tmp2 = uint16_t(U.VAL);
626 Tmp2 = ByteSwap_16(Tmp2);
627 return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
628 }
629 if (BitWidth == 64)
630 return APInt(BitWidth, ByteSwap_64(U.VAL));
631
632 APInt Result(getNumWords() * APINT_BITS_PER_WORD, 0);
633 for (unsigned I = 0, N = getNumWords(); I != N; ++I)
634 Result.U.pVal[I] = ByteSwap_64(U.pVal[N - I - 1]);
635 if (Result.BitWidth != BitWidth) {
636 Result.lshrInPlace(Result.BitWidth - BitWidth);
637 Result.BitWidth = BitWidth;
638 }
639 return Result;
640}
641
642APInt APInt::reverseBits() const {
643 switch (BitWidth) {
644 case 64:
645 return APInt(BitWidth, llvm::reverseBits<uint64_t>(U.VAL));
646 case 32:
647 return APInt(BitWidth, llvm::reverseBits<uint32_t>(U.VAL));
648 case 16:
649 return APInt(BitWidth, llvm::reverseBits<uint16_t>(U.VAL));
650 case 8:
651 return APInt(BitWidth, llvm::reverseBits<uint8_t>(U.VAL));
652 default:
653 break;
654 }
655
656 APInt Val(*this);
657 APInt Reversed(BitWidth, 0);
658 unsigned S = BitWidth;
659
660 for (; Val != 0; Val.lshrInPlace(1)) {
661 Reversed <<= 1;
662 Reversed |= Val[0];
663 --S;
664 }
665
666 Reversed <<= S;
667 return Reversed;
668}
669
670APInt llvm::APIntOps::GreatestCommonDivisor(APInt A, APInt B) {
671 // Fast-path a common case.
672 if (A == B) return A;
673
674 // Corner cases: if either operand is zero, the other is the gcd.
675 if (!A) return B;
676 if (!B) return A;
677
678 // Count common powers of 2 and remove all other powers of 2.
679 unsigned Pow2;
680 {
681 unsigned Pow2_A = A.countTrailingZeros();
682 unsigned Pow2_B = B.countTrailingZeros();
683 if (Pow2_A > Pow2_B) {
684 A.lshrInPlace(Pow2_A - Pow2_B);
685 Pow2 = Pow2_B;
686 } else if (Pow2_B > Pow2_A) {
687 B.lshrInPlace(Pow2_B - Pow2_A);
688 Pow2 = Pow2_A;
689 } else {
690 Pow2 = Pow2_A;
691 }
692 }
693
694 // Both operands are odd multiples of 2^Pow_2:
695 //
696 // gcd(a, b) = gcd(|a - b| / 2^i, min(a, b))
697 //
698 // This is a modified version of Stein's algorithm, taking advantage of
699 // efficient countTrailingZeros().
700 while (A != B) {
701 if (A.ugt(B)) {
702 A -= B;
703 A.lshrInPlace(A.countTrailingZeros() - Pow2);
704 } else {
705 B -= A;
706 B.lshrInPlace(B.countTrailingZeros() - Pow2);
707 }
708 }
709
710 return A;
711}
712
713APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) {
714 union {
715 double D;
716 uint64_t I;
717 } T;
718 T.D = Double;
719
720 // Get the sign bit from the highest order bit
721 bool isNeg = T.I >> 63;
722
723 // Get the 11-bit exponent and adjust for the 1023 bit bias
724 int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
725
726 // If the exponent is negative, the value is < 0 so just return 0.
727 if (exp < 0)
728 return APInt(width, 0u);
729
730 // Extract the mantissa by clearing the top 12 bits (sign + exponent).
731 uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
732
733 // If the exponent doesn't shift all bits out of the mantissa
734 if (exp < 52)
735 return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
736 APInt(width, mantissa >> (52 - exp));
737
738 // If the client didn't provide enough bits for us to shift the mantissa into
739 // then the result is undefined, just return 0
740 if (width <= exp - 52)
741 return APInt(width, 0);
742
743 // Otherwise, we have to shift the mantissa bits up to the right location
744 APInt Tmp(width, mantissa);
745 Tmp <<= (unsigned)exp - 52;
746 return isNeg ? -Tmp : Tmp;
747}
748
749/// This function converts this APInt to a double.
750/// The layout for double is as following (IEEE Standard 754):
751/// --------------------------------------
752/// | Sign Exponent Fraction Bias |
753/// |-------------------------------------- |
754/// | 1[63] 11[62-52] 52[51-00] 1023 |
755/// --------------------------------------
756double APInt::roundToDouble(bool isSigned) const {
757
758 // Handle the simple case where the value is contained in one uint64_t.
759 // It is wrong to optimize getWord(0) to VAL; there might be more than one word.
760 if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
761 if (isSigned) {
762 int64_t sext = SignExtend64(getWord(0), BitWidth);
763 return double(sext);
764 } else
765 return double(getWord(0));
766 }
767
768 // Determine if the value is negative.
769 bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
770
771 // Construct the absolute value if we're negative.
772 APInt Tmp(isNeg ? -(*this) : (*this));
773
774 // Figure out how many bits we're using.
775 unsigned n = Tmp.getActiveBits();
776
777 // The exponent (without bias normalization) is just the number of bits
778 // we are using. Note that the sign bit is gone since we constructed the
779 // absolute value.
780 uint64_t exp = n;
781
782 // Return infinity for exponent overflow
783 if (exp > 1023) {
784 if (!isSigned || !isNeg)
785 return std::numeric_limits<double>::infinity();
786 else
787 return -std::numeric_limits<double>::infinity();
788 }
789 exp += 1023; // Increment for 1023 bias
790
791 // Number of bits in mantissa is 52. To obtain the mantissa value, we must
792 // extract the high 52 bits from the correct words in pVal.
793 uint64_t mantissa;
794 unsigned hiWord = whichWord(n-1);
795 if (hiWord == 0) {
796 mantissa = Tmp.U.pVal[0];
797 if (n > 52)
798 mantissa >>= n - 52; // shift down, we want the top 52 bits.
799 } else {
800 assert(hiWord > 0 && "huh?")(static_cast <bool> (hiWord > 0 && "huh?") ?
void (0) : __assert_fail ("hiWord > 0 && \"huh?\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 800, __extension__ __PRETTY_FUNCTION__))
;
801 uint64_t hibits = Tmp.U.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
802 uint64_t lobits = Tmp.U.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
803 mantissa = hibits | lobits;
804 }
805
806 // The leading bit of mantissa is implicit, so get rid of it.
807 uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
808 union {
809 double D;
810 uint64_t I;
811 } T;
812 T.I = sign | (exp << 52) | mantissa;
813 return T.D;
814}
815
816// Truncate to new width.
817APInt APInt::trunc(unsigned width) const {
818 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~svn338205/lib/Support/APInt.cpp"
, 818, __extension__ __PRETTY_FUNCTION__))
;
819 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~svn338205/lib/Support/APInt.cpp"
, 819, __extension__ __PRETTY_FUNCTION__))
;
820
821 if (width <= APINT_BITS_PER_WORD)
822 return APInt(width, getRawData()[0]);
823
824 APInt Result(getMemory(getNumWords(width)), width);
825
826 // Copy full words.
827 unsigned i;
828 for (i = 0; i != width / APINT_BITS_PER_WORD; i++)
829 Result.U.pVal[i] = U.pVal[i];
830
831 // Truncate and copy any partial word.
832 unsigned bits = (0 - width) % APINT_BITS_PER_WORD;
833 if (bits != 0)
834 Result.U.pVal[i] = U.pVal[i] << bits >> bits;
835
836 return Result;
837}
838
839// Sign extend to a new width.
840APInt APInt::sext(unsigned Width) const {
841 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~svn338205/lib/Support/APInt.cpp"
, 841, __extension__ __PRETTY_FUNCTION__))
;
842
843 if (Width <= APINT_BITS_PER_WORD)
844 return APInt(Width, SignExtend64(U.VAL, BitWidth));
845
846 APInt Result(getMemory(getNumWords(Width)), Width);
847
848 // Copy words.
849 std::memcpy(Result.U.pVal, getRawData(), getNumWords() * APINT_WORD_SIZE);
850
851 // Sign extend the last word since there may be unused bits in the input.
852 Result.U.pVal[getNumWords() - 1] =
853 SignExtend64(Result.U.pVal[getNumWords() - 1],
854 ((BitWidth - 1) % APINT_BITS_PER_WORD) + 1);
855
856 // Fill with sign bits.
857 std::memset(Result.U.pVal + getNumWords(), isNegative() ? -1 : 0,
858 (Result.getNumWords() - getNumWords()) * APINT_WORD_SIZE);
859 Result.clearUnusedBits();
860 return Result;
861}
862
863// Zero extend to a new width.
864APInt APInt::zext(unsigned width) const {
865 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~svn338205/lib/Support/APInt.cpp"
, 865, __extension__ __PRETTY_FUNCTION__))
;
866
867 if (width <= APINT_BITS_PER_WORD)
868 return APInt(width, U.VAL);
869
870 APInt Result(getMemory(getNumWords(width)), width);
871
872 // Copy words.
873 std::memcpy(Result.U.pVal, getRawData(), getNumWords() * APINT_WORD_SIZE);
874
875 // Zero remaining words.
876 std::memset(Result.U.pVal + getNumWords(), 0,
877 (Result.getNumWords() - getNumWords()) * APINT_WORD_SIZE);
878
879 return Result;
880}
881
882APInt APInt::zextOrTrunc(unsigned width) const {
883 if (BitWidth < width)
884 return zext(width);
885 if (BitWidth > width)
886 return trunc(width);
887 return *this;
888}
889
890APInt APInt::sextOrTrunc(unsigned width) const {
891 if (BitWidth < width)
892 return sext(width);
893 if (BitWidth > width)
894 return trunc(width);
895 return *this;
896}
897
898APInt APInt::zextOrSelf(unsigned width) const {
899 if (BitWidth < width)
900 return zext(width);
901 return *this;
902}
903
904APInt APInt::sextOrSelf(unsigned width) const {
905 if (BitWidth < width)
906 return sext(width);
907 return *this;
908}
909
910/// Arithmetic right-shift this APInt by shiftAmt.
911/// Arithmetic right-shift function.
912void APInt::ashrInPlace(const APInt &shiftAmt) {
913 ashrInPlace((unsigned)shiftAmt.getLimitedValue(BitWidth));
914}
915
916/// Arithmetic right-shift this APInt by shiftAmt.
917/// Arithmetic right-shift function.
918void APInt::ashrSlowCase(unsigned ShiftAmt) {
919 // Don't bother performing a no-op shift.
920 if (!ShiftAmt)
921 return;
922
923 // Save the original sign bit for later.
924 bool Negative = isNegative();
925
926 // WordShift is the inter-part shift; BitShift is intra-part shift.
927 unsigned WordShift = ShiftAmt / APINT_BITS_PER_WORD;
928 unsigned BitShift = ShiftAmt % APINT_BITS_PER_WORD;
929
930 unsigned WordsToMove = getNumWords() - WordShift;
931 if (WordsToMove != 0) {
932 // Sign extend the last word to fill in the unused bits.
933 U.pVal[getNumWords() - 1] = SignExtend64(
934 U.pVal[getNumWords() - 1], ((BitWidth - 1) % APINT_BITS_PER_WORD) + 1);
935
936 // Fastpath for moving by whole words.
937 if (BitShift == 0) {
938 std::memmove(U.pVal, U.pVal + WordShift, WordsToMove * APINT_WORD_SIZE);
939 } else {
940 // Move the words containing significant bits.
941 for (unsigned i = 0; i != WordsToMove - 1; ++i)
942 U.pVal[i] = (U.pVal[i + WordShift] >> BitShift) |
943 (U.pVal[i + WordShift + 1] << (APINT_BITS_PER_WORD - BitShift));
944
945 // Handle the last word which has no high bits to copy.
946 U.pVal[WordsToMove - 1] = U.pVal[WordShift + WordsToMove - 1] >> BitShift;
947 // Sign extend one more time.
948 U.pVal[WordsToMove - 1] =
949 SignExtend64(U.pVal[WordsToMove - 1], APINT_BITS_PER_WORD - BitShift);
950 }
951 }
952
953 // Fill in the remainder based on the original sign.
954 std::memset(U.pVal + WordsToMove, Negative ? -1 : 0,
955 WordShift * APINT_WORD_SIZE);
956 clearUnusedBits();
957}
958
959/// Logical right-shift this APInt by shiftAmt.
960/// Logical right-shift function.
961void APInt::lshrInPlace(const APInt &shiftAmt) {
962 lshrInPlace((unsigned)shiftAmt.getLimitedValue(BitWidth));
963}
964
965/// Logical right-shift this APInt by shiftAmt.
966/// Logical right-shift function.
967void APInt::lshrSlowCase(unsigned ShiftAmt) {
968 tcShiftRight(U.pVal, getNumWords(), ShiftAmt);
969}
970
971/// Left-shift this APInt by shiftAmt.
972/// Left-shift function.
973APInt &APInt::operator<<=(const APInt &shiftAmt) {
974 // It's undefined behavior in C to shift by BitWidth or greater.
975 *this <<= (unsigned)shiftAmt.getLimitedValue(BitWidth);
976 return *this;
977}
978
979void APInt::shlSlowCase(unsigned ShiftAmt) {
980 tcShiftLeft(U.pVal, getNumWords(), ShiftAmt);
981 clearUnusedBits();
982}
983
984// Calculate the rotate amount modulo the bit width.
985static unsigned rotateModulo(unsigned BitWidth, const APInt &rotateAmt) {
986 unsigned rotBitWidth = rotateAmt.getBitWidth();
987 APInt rot = rotateAmt;
2
Calling copy constructor for 'APInt'
9
Returning from copy constructor for 'APInt'
988 if (rotBitWidth < BitWidth) {
10
Assuming 'rotBitWidth' is >= 'BitWidth'
11
Taking false branch
989 // Extend the rotate APInt, so that the urem doesn't divide by 0.
990 // e.g. APInt(1, 32) would give APInt(1, 0).
991 rot = rotateAmt.zext(BitWidth);
992 }
993 rot = rot.urem(APInt(rot.getBitWidth(), BitWidth));
12
Calling move assignment operator for 'APInt'
15
Returning; memory was released
994 return rot.getLimitedValue(BitWidth);
16
Calling 'APInt::getLimitedValue'
995}
996
997APInt APInt::rotl(const APInt &rotateAmt) const {
998 return rotl(rotateModulo(BitWidth, rotateAmt));
999}
1000
1001APInt APInt::rotl(unsigned rotateAmt) const {
1002 rotateAmt %= BitWidth;
1003 if (rotateAmt == 0)
1004 return *this;
1005 return shl(rotateAmt) | lshr(BitWidth - rotateAmt);
1006}
1007
1008APInt APInt::rotr(const APInt &rotateAmt) const {
1009 return rotr(rotateModulo(BitWidth, rotateAmt));
1
Calling 'rotateModulo'
1010}
1011
1012APInt APInt::rotr(unsigned rotateAmt) const {
1013 rotateAmt %= BitWidth;
1014 if (rotateAmt == 0)
1015 return *this;
1016 return lshr(rotateAmt) | shl(BitWidth - rotateAmt);
1017}
1018
1019// Square Root - this method computes and returns the square root of "this".
1020// Three mechanisms are used for computation. For small values (<= 5 bits),
1021// a table lookup is done. This gets some performance for common cases. For
1022// values using less than 52 bits, the value is converted to double and then
1023// the libc sqrt function is called. The result is rounded and then converted
1024// back to a uint64_t which is then used to construct the result. Finally,
1025// the Babylonian method for computing square roots is used.
1026APInt APInt::sqrt() const {
1027
1028 // Determine the magnitude of the value.
1029 unsigned magnitude = getActiveBits();
1030
1031 // Use a fast table for some small values. This also gets rid of some
1032 // rounding errors in libc sqrt for small values.
1033 if (magnitude <= 5) {
1034 static const uint8_t results[32] = {
1035 /* 0 */ 0,
1036 /* 1- 2 */ 1, 1,
1037 /* 3- 6 */ 2, 2, 2, 2,
1038 /* 7-12 */ 3, 3, 3, 3, 3, 3,
1039 /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
1040 /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1041 /* 31 */ 6
1042 };
1043 return APInt(BitWidth, results[ (isSingleWord() ? U.VAL : U.pVal[0]) ]);
1044 }
1045
1046 // If the magnitude of the value fits in less than 52 bits (the precision of
1047 // an IEEE double precision floating point value), then we can use the
1048 // libc sqrt function which will probably use a hardware sqrt computation.
1049 // This should be faster than the algorithm below.
1050 if (magnitude < 52) {
1051 return APInt(BitWidth,
1052 uint64_t(::round(::sqrt(double(isSingleWord() ? U.VAL
1053 : U.pVal[0])))));
1054 }
1055
1056 // Okay, all the short cuts are exhausted. We must compute it. The following
1057 // is a classical Babylonian method for computing the square root. This code
1058 // was adapted to APInt from a wikipedia article on such computations.
1059 // See http://www.wikipedia.org/ and go to the page named
1060 // Calculate_an_integer_square_root.
1061 unsigned nbits = BitWidth, i = 4;
1062 APInt testy(BitWidth, 16);
1063 APInt x_old(BitWidth, 1);
1064 APInt x_new(BitWidth, 0);
1065 APInt two(BitWidth, 2);
1066
1067 // Select a good starting value using binary logarithms.
1068 for (;; i += 2, testy = testy.shl(2))
1069 if (i >= nbits || this->ule(testy)) {
1070 x_old = x_old.shl(i / 2);
1071 break;
1072 }
1073
1074 // Use the Babylonian method to arrive at the integer square root:
1075 for (;;) {
1076 x_new = (this->udiv(x_old) + x_old).udiv(two);
1077 if (x_old.ule(x_new))
1078 break;
1079 x_old = x_new;
1080 }
1081
1082 // Make sure we return the closest approximation
1083 // NOTE: The rounding calculation below is correct. It will produce an
1084 // off-by-one discrepancy with results from pari/gp. That discrepancy has been
1085 // determined to be a rounding issue with pari/gp as it begins to use a
1086 // floating point representation after 192 bits. There are no discrepancies
1087 // between this algorithm and pari/gp for bit widths < 192 bits.
1088 APInt square(x_old * x_old);
1089 APInt nextSquare((x_old + 1) * (x_old +1));
1090 if (this->ult(square))
1091 return x_old;
1092 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~svn338205/lib/Support/APInt.cpp"
, 1092, __extension__ __PRETTY_FUNCTION__))
;
1093 APInt midpoint((nextSquare - square).udiv(two));
1094 APInt offset(*this - square);
1095 if (offset.ult(midpoint))
1096 return x_old;
1097 return x_old + 1;
1098}
1099
1100/// Computes the multiplicative inverse of this APInt for a given modulo. The
1101/// iterative extended Euclidean algorithm is used to solve for this value,
1102/// however we simplify it to speed up calculating only the inverse, and take
1103/// advantage of div+rem calculations. We also use some tricks to avoid copying
1104/// (potentially large) APInts around.
1105APInt APInt::multiplicativeInverse(const APInt& modulo) const {
1106 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~svn338205/lib/Support/APInt.cpp"
, 1106, __extension__ __PRETTY_FUNCTION__))
;
1107
1108 // Using the properties listed at the following web page (accessed 06/21/08):
1109 // http://www.numbertheory.org/php/euclid.html
1110 // (especially the properties numbered 3, 4 and 9) it can be proved that
1111 // BitWidth bits suffice for all the computations in the algorithm implemented
1112 // below. More precisely, this number of bits suffice if the multiplicative
1113 // inverse exists, but may not suffice for the general extended Euclidean
1114 // algorithm.
1115
1116 APInt r[2] = { modulo, *this };
1117 APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) };
1118 APInt q(BitWidth, 0);
1119
1120 unsigned i;
1121 for (i = 0; r[i^1] != 0; i ^= 1) {
1122 // An overview of the math without the confusing bit-flipping:
1123 // q = r[i-2] / r[i-1]
1124 // r[i] = r[i-2] % r[i-1]
1125 // t[i] = t[i-2] - t[i-1] * q
1126 udivrem(r[i], r[i^1], q, r[i]);
1127 t[i] -= t[i^1] * q;
1128 }
1129
1130 // If this APInt and the modulo are not coprime, there is no multiplicative
1131 // inverse, so return 0. We check this by looking at the next-to-last
1132 // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean
1133 // algorithm.
1134 if (r[i] != 1)
1135 return APInt(BitWidth, 0);
1136
1137 // The next-to-last t is the multiplicative inverse. However, we are
1138 // interested in a positive inverse. Calculate a positive one from a negative
1139 // one if necessary. A simple addition of the modulo suffices because
1140 // abs(t[i]) is known to be less than *this/2 (see the link above).
1141 if (t[i].isNegative())
1142 t[i] += modulo;
1143
1144 return std::move(t[i]);
1145}
1146
1147/// Calculate the magic numbers required to implement a signed integer division
1148/// by a constant as a sequence of multiplies, adds and shifts. Requires that
1149/// the divisor not be 0, 1, or -1. Taken from "Hacker's Delight", Henry S.
1150/// Warren, Jr., chapter 10.
1151APInt::ms APInt::magic() const {
1152 const APInt& d = *this;
1153 unsigned p;
1154 APInt ad, anc, delta, q1, r1, q2, r2, t;
1155 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1156 struct ms mag;
1157
1158 ad = d.abs();
1159 t = signedMin + (d.lshr(d.getBitWidth() - 1));
1160 anc = t - 1 - t.urem(ad); // absolute value of nc
1161 p = d.getBitWidth() - 1; // initialize p
1162 q1 = signedMin.udiv(anc); // initialize q1 = 2p/abs(nc)
1163 r1 = signedMin - q1*anc; // initialize r1 = rem(2p,abs(nc))
1164 q2 = signedMin.udiv(ad); // initialize q2 = 2p/abs(d)
1165 r2 = signedMin - q2*ad; // initialize r2 = rem(2p,abs(d))
1166 do {
1167 p = p + 1;
1168 q1 = q1<<1; // update q1 = 2p/abs(nc)
1169 r1 = r1<<1; // update r1 = rem(2p/abs(nc))
1170 if (r1.uge(anc)) { // must be unsigned comparison
1171 q1 = q1 + 1;
1172 r1 = r1 - anc;
1173 }
1174 q2 = q2<<1; // update q2 = 2p/abs(d)
1175 r2 = r2<<1; // update r2 = rem(2p/abs(d))
1176 if (r2.uge(ad)) { // must be unsigned comparison
1177 q2 = q2 + 1;
1178 r2 = r2 - ad;
1179 }
1180 delta = ad - r2;
1181 } while (q1.ult(delta) || (q1 == delta && r1 == 0));
1182
1183 mag.m = q2 + 1;
1184 if (d.isNegative()) mag.m = -mag.m; // resulting magic number
1185 mag.s = p - d.getBitWidth(); // resulting shift
1186 return mag;
1187}
1188
1189/// Calculate the magic numbers required to implement an unsigned integer
1190/// division by a constant as a sequence of multiplies, adds and shifts.
1191/// Requires that the divisor not be 0. Taken from "Hacker's Delight", Henry
1192/// S. Warren, Jr., chapter 10.
1193/// LeadingZeros can be used to simplify the calculation if the upper bits
1194/// of the divided value are known zero.
1195APInt::mu APInt::magicu(unsigned LeadingZeros) const {
1196 const APInt& d = *this;
1197 unsigned p;
1198 APInt nc, delta, q1, r1, q2, r2;
1199 struct mu magu;
1200 magu.a = 0; // initialize "add" indicator
1201 APInt allOnes = APInt::getAllOnesValue(d.getBitWidth()).lshr(LeadingZeros);
1202 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1203 APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());
1204
1205 nc = allOnes - (allOnes - d).urem(d);
1206 p = d.getBitWidth() - 1; // initialize p
1207 q1 = signedMin.udiv(nc); // initialize q1 = 2p/nc
1208 r1 = signedMin - q1*nc; // initialize r1 = rem(2p,nc)
1209 q2 = signedMax.udiv(d); // initialize q2 = (2p-1)/d
1210 r2 = signedMax - q2*d; // initialize r2 = rem((2p-1),d)
1211 do {
1212 p = p + 1;
1213 if (r1.uge(nc - r1)) {
1214 q1 = q1 + q1 + 1; // update q1
1215 r1 = r1 + r1 - nc; // update r1
1216 }
1217 else {
1218 q1 = q1+q1; // update q1
1219 r1 = r1+r1; // update r1
1220 }
1221 if ((r2 + 1).uge(d - r2)) {
1222 if (q2.uge(signedMax)) magu.a = 1;
1223 q2 = q2+q2 + 1; // update q2
1224 r2 = r2+r2 + 1 - d; // update r2
1225 }
1226 else {
1227 if (q2.uge(signedMin)) magu.a = 1;
1228 q2 = q2+q2; // update q2
1229 r2 = r2+r2 + 1; // update r2
1230 }
1231 delta = d - 1 - r2;
1232 } while (p < d.getBitWidth()*2 &&
1233 (q1.ult(delta) || (q1 == delta && r1 == 0)));
1234 magu.m = q2 + 1; // resulting magic number
1235 magu.s = p - d.getBitWidth(); // resulting shift
1236 return magu;
1237}
1238
1239/// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
1240/// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
1241/// variables here have the same names as in the algorithm. Comments explain
1242/// the algorithm and any deviation from it.
1243static void KnuthDiv(uint32_t *u, uint32_t *v, uint32_t *q, uint32_t* r,
1244 unsigned m, unsigned n) {
1245 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~svn338205/lib/Support/APInt.cpp"
, 1245, __extension__ __PRETTY_FUNCTION__))
;
1246 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~svn338205/lib/Support/APInt.cpp"
, 1246, __extension__ __PRETTY_FUNCTION__))
;
1247 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~svn338205/lib/Support/APInt.cpp"
, 1247, __extension__ __PRETTY_FUNCTION__))
;
1248 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~svn338205/lib/Support/APInt.cpp"
, 1248, __extension__ __PRETTY_FUNCTION__))
;
1249 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~svn338205/lib/Support/APInt.cpp"
, 1249, __extension__ __PRETTY_FUNCTION__))
;
1250
1251 // b denotes the base of the number system. In our case b is 2^32.
1252 const uint64_t b = uint64_t(1) << 32;
1253
1254// The DEBUG macros here tend to be spam in the debug output if you're not
1255// debugging this code. Disable them unless KNUTH_DEBUG is defined.
1256#pragma push_macro("LLVM_DEBUG")
1257#ifndef KNUTH_DEBUG
1258#undef LLVM_DEBUG
1259#define LLVM_DEBUG(X)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { X; } } while (false)
\
1260 do { \
1261 } while (false)
1262#endif
1263
1264 LLVM_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 LLVM_DEBUG(dbgs() << "KnuthDiv: original:")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << "KnuthDiv: original:"; } } while
(false)
;
1266 LLVM_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 LLVM_DEBUG(dbgs() << " by")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << " by"; } } while (false)
;
1268 LLVM_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 LLVM_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 LLVM_DEBUG(dbgs() << "KnuthDiv: normal:")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << "KnuthDiv: normal:"; } } while
(false)
;
1296 LLVM_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 LLVM_DEBUG(dbgs() << " by")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << " by"; } } while (false)
;
1298 LLVM_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 LLVM_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 LLVM_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 LLVM_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 LLVM_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 LLVM_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 LLVM_DEBUG(dbgs() << "KnuthDiv: after subtraction:")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << "KnuthDiv: after subtraction:"; }
} while (false)
;
1346 LLVM_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 LLVM_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 LLVM_DEBUG(dbgs() << "KnuthDiv: after correction:")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << "KnuthDiv: after correction:"; }
} while (false)
;
1369 LLVM_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 LLVM_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 LLVM_DEBUG(dbgs() << "KnuthDiv: quotient:")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << "KnuthDiv: quotient:"; } } while
(false)
;
1376 LLVM_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 LLVM_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 LLVM_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 LLVM_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 LLVM_DEBUG(dbgs() << " " << r[i])do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << " " << r[i]; } } while (false
)
;
1398 }
1399 }
1400 LLVM_DEBUG(dbgs() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << '\n'; } } while (false)
;
1401 }
1402 LLVM_DEBUG(dbgs() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("apint")) { dbgs() << '\n'; } } while (false)
;
1403
1404#pragma pop_macro("LLVM_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~svn338205/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~svn338205/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~svn338205/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~svn338205/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~svn338205/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~svn338205/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~svn338205/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~svn338205/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~svn338205/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~svn338205/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~svn338205/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~svn338205/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~svn338205/lib/Support/APInt.cpp"
, 1734, __extension__ __PRETTY_FUNCTION__))
;
1735
1736 // Check the degenerate cases
1737 if (lhsWords == 0) {
1738 Quotient = APInt(BitWidth, 0); // 0 / Y ===> 0
1739 Remainder = APInt(BitWidth, 0); // 0 % Y ===> 0
1740 return;
1741 }
1742
1743 if (rhsBits == 1) {
1744 Quotient = LHS; // X / 1 ===> X
1745 Remainder = APInt(BitWidth, 0); // X % 1 ===> 0
1746 }
1747
1748 if (lhsWords < rhsWords || LHS.ult(RHS)) {
1749 Remainder = LHS; // X % Y ===> X, iff X < Y
1750 Quotient = APInt(BitWidth, 0); // X / Y ===> 0, iff X < Y
1751 return;
1752 }
1753
1754 if (LHS == RHS) {
1755 Quotient = APInt(BitWidth, 1); // X / X ===> 1
1756 Remainder = APInt(BitWidth, 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~svn338205/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 = APInt(BitWidth, 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 return;
1813 }
1814
1815 if (LHS.ult(RHS)) {
1816 Remainder = LHS.getZExtValue(); // X % Y ===> X, iff X < Y
1817 Quotient = APInt(BitWidth, 0); // X / Y ===> 0, iff X < Y
1818 return;
1819 }
1820
1821 if (LHS == RHS) {
1822 Quotient = APInt(BitWidth, 1); // X / X ===> 1
1823 Remainder = 0; // X % X ===> 0;
1824 return;
1825 }
1826
1827 // Make sure there is enough space to hold the results.
1828 // NOTE: This assumes that reallocate won't affect any bits if it doesn't
1829 // change the size. This is necessary if Quotient is aliased with LHS.
1830 Quotient.reallocate(BitWidth);
1831
1832 if (lhsWords == 1) { // rhsWords is 1 if lhsWords is 1.
1833 // There is only one word to consider so use the native versions.
1834 uint64_t lhsValue = LHS.U.pVal[0];
1835 Quotient = lhsValue / RHS;
1836 Remainder = lhsValue % RHS;
1837 return;
1838 }
1839
1840 // Okay, lets do it the long way
1841 divide(LHS.U.pVal, lhsWords, &RHS, 1, Quotient.U.pVal, &Remainder);
1842 // Clear the rest of the Quotient.
1843 std::memset(Quotient.U.pVal + lhsWords, 0,
1844 (getNumWords(BitWidth) - lhsWords) * APINT_WORD_SIZE);
1845}
1846
1847void APInt::sdivrem(const APInt &LHS, const APInt &RHS,
1848 APInt &Quotient, APInt &Remainder) {
1849 if (LHS.isNegative()) {
1850 if (RHS.isNegative())
1851 APInt::udivrem(-LHS, -RHS, Quotient, Remainder);
1852 else {
1853 APInt::udivrem(-LHS, RHS, Quotient, Remainder);
1854 Quotient.negate();
1855 }
1856 Remainder.negate();
1857 } else if (RHS.isNegative()) {
1858 APInt::udivrem(LHS, -RHS, Quotient, Remainder);
1859 Quotient.negate();
1860 } else {
1861 APInt::udivrem(LHS, RHS, Quotient, Remainder);
1862 }
1863}
1864
1865void APInt::sdivrem(const APInt &LHS, int64_t RHS,
1866 APInt &Quotient, int64_t &Remainder) {
1867 uint64_t R = Remainder;
1868 if (LHS.isNegative()) {
1869 if (RHS < 0)
1870 APInt::udivrem(-LHS, -RHS, Quotient, R);
1871 else {
1872 APInt::udivrem(-LHS, RHS, Quotient, R);
1873 Quotient.negate();
1874 }
1875 R = -R;
1876 } else if (RHS < 0) {
1877 APInt::udivrem(LHS, -RHS, Quotient, R);
1878 Quotient.negate();
1879 } else {
1880 APInt::udivrem(LHS, RHS, Quotient, R);
1881 }
1882 Remainder = R;
1883}
1884
1885APInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const {
1886 APInt Res = *this+RHS;
1887 Overflow = isNonNegative() == RHS.isNonNegative() &&
1888 Res.isNonNegative() != isNonNegative();
1889 return Res;
1890}
1891
1892APInt APInt::uadd_ov(const APInt &RHS, bool &Overflow) const {
1893 APInt Res = *this+RHS;
1894 Overflow = Res.ult(RHS);
1895 return Res;
1896}
1897
1898APInt APInt::ssub_ov(const APInt &RHS, bool &Overflow) const {
1899 APInt Res = *this - RHS;
1900 Overflow = isNonNegative() != RHS.isNonNegative() &&
1901 Res.isNonNegative() != isNonNegative();
1902 return Res;
1903}
1904
1905APInt APInt::usub_ov(const APInt &RHS, bool &Overflow) const {
1906 APInt Res = *this-RHS;
1907 Overflow = Res.ugt(*this);
1908 return Res;
1909}
1910
1911APInt APInt::sdiv_ov(const APInt &RHS, bool &Overflow) const {
1912 // MININT/-1 --> overflow.
1913 Overflow = isMinSignedValue() && RHS.isAllOnesValue();
1914 return sdiv(RHS);
1915}
1916
1917APInt APInt::smul_ov(const APInt &RHS, bool &Overflow) const {
1918 APInt Res = *this * RHS;
1919
1920 if (*this != 0 && RHS != 0)
1921 Overflow = Res.sdiv(RHS) != *this || Res.sdiv(*this) != RHS;
1922 else
1923 Overflow = false;
1924 return Res;
1925}
1926
1927APInt APInt::umul_ov(const APInt &RHS, bool &Overflow) const {
1928 APInt Res = *this * RHS;
1929
1930 if (*this != 0 && RHS != 0)
1931 Overflow = Res.udiv(RHS) != *this || Res.udiv(*this) != RHS;
1932 else
1933 Overflow = false;
1934 return Res;
1935}
1936
1937APInt APInt::sshl_ov(const APInt &ShAmt, bool &Overflow) const {
1938 Overflow = ShAmt.uge(getBitWidth());
1939 if (Overflow)
1940 return APInt(BitWidth, 0);
1941
1942 if (isNonNegative()) // Don't allow sign change.
1943 Overflow = ShAmt.uge(countLeadingZeros());
1944 else
1945 Overflow = ShAmt.uge(countLeadingOnes());
1946
1947 return *this << ShAmt;
1948}
1949
1950APInt APInt::ushl_ov(const APInt &ShAmt, bool &Overflow) const {
1951 Overflow = ShAmt.uge(getBitWidth());
1952 if (Overflow)
1953 return APInt(BitWidth, 0);
1954
1955 Overflow = ShAmt.ugt(countLeadingZeros());
1956
1957 return *this << ShAmt;
1958}
1959
1960
1961
1962
1963void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) {
1964 // Check our assumptions here
1965 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~svn338205/lib/Support/APInt.cpp"
, 1965, __extension__ __PRETTY_FUNCTION__))
;
1966 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~svn338205/lib/Support/APInt.cpp"
, 1968, __extension__ __PRETTY_FUNCTION__))
1967 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~svn338205/lib/Support/APInt.cpp"
, 1968, __extension__ __PRETTY_FUNCTION__))
1968 "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~svn338205/lib/Support/APInt.cpp"
, 1968, __extension__ __PRETTY_FUNCTION__))
;
1969
1970 StringRef::iterator p = str.begin();
1971 size_t slen = str.size();
1972 bool isNeg = *p == '-';
1973 if (*p == '-' || *p == '+') {
1974 p++;
1975 slen--;
1976 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~svn338205/lib/Support/APInt.cpp"
, 1976, __extension__ __PRETTY_FUNCTION__))
;
1977 }
1978 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~svn338205/lib/Support/APInt.cpp"
, 1978, __extension__ __PRETTY_FUNCTION__))
;
1979 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~svn338205/lib/Support/APInt.cpp"
, 1979, __extension__ __PRETTY_FUNCTION__))
;
1980 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~svn338205/lib/Support/APInt.cpp"
, 1980, __extension__ __PRETTY_FUNCTION__))
;
1981 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~svn338205/lib/Support/APInt.cpp"
, 1982, __extension__ __PRETTY_FUNCTION__))
1982 "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~svn338205/lib/Support/APInt.cpp"
, 1982, __extension__ __PRETTY_FUNCTION__))
;
1983
1984 // Allocate memory if needed
1985 if (isSingleWord())
1986 U.VAL = 0;
1987 else
1988 U.pVal = getClearedMemory(getNumWords());
1989
1990 // Figure out if we can shift instead of multiply
1991 unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
1992
1993 // Enter digit traversal loop
1994 for (StringRef::iterator e = str.end(); p != e; ++p) {
1995 unsigned digit = getDigit(*p, radix);
1996 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~svn338205/lib/Support/APInt.cpp"
, 1996, __extension__ __PRETTY_FUNCTION__))
;
1997
1998 // Shift or multiply the value by the radix
1999 if (slen > 1) {
2000 if (shift)
2001 *this <<= shift;
2002 else
2003 *this *= radix;
2004 }
2005
2006 // Add in the digit we just interpreted
2007 *this += digit;
2008 }
2009 // If its negative, put it in two's complement form
2010 if (isNeg)
2011 this->negate();
2012}
2013
2014void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix,
2015 bool Signed, bool formatAsCLiteral) const {
2016 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~svn338205/lib/Support/APInt.cpp"
, 2018, __extension__ __PRETTY_FUNCTION__))
2017 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~svn338205/lib/Support/APInt.cpp"
, 2018, __extension__ __PRETTY_FUNCTION__))
2018 "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~svn338205/lib/Support/APInt.cpp"
, 2018, __extension__ __PRETTY_FUNCTION__))
;
2019
2020 const char *Prefix = "";
2021 if (formatAsCLiteral) {
2022 switch (Radix) {
2023 case 2:
2024 // Binary literals are a non-standard extension added in gcc 4.3:
2025 // http://gcc.gnu.org/onlinedocs/gcc-4.3.0/gcc/Binary-constants.html
2026 Prefix = "0b";
2027 break;
2028 case 8:
2029 Prefix = "0";
2030 break;
2031 case 10:
2032 break; // No prefix
2033 case 16:
2034 Prefix = "0x";
2035 break;
2036 default:
2037 llvm_unreachable("Invalid radix!")::llvm::llvm_unreachable_internal("Invalid radix!", "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 2037)
;
2038 }
2039 }
2040
2041 // First, check for a zero value and just short circuit the logic below.
2042 if (*this == 0) {
2043 while (*Prefix) {
2044 Str.push_back(*Prefix);
2045 ++Prefix;
2046 };
2047 Str.push_back('0');
2048 return;
2049 }
2050
2051 static const char Digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
2052
2053 if (isSingleWord()) {
2054 char Buffer[65];
2055 char *BufPtr = std::end(Buffer);
2056
2057 uint64_t N;
2058 if (!Signed) {
2059 N = getZExtValue();
2060 } else {
2061 int64_t I = getSExtValue();
2062 if (I >= 0) {
2063 N = I;
2064 } else {
2065 Str.push_back('-');
2066 N = -(uint64_t)I;
2067 }
2068 }
2069
2070 while (*Prefix) {
2071 Str.push_back(*Prefix);
2072 ++Prefix;
2073 };
2074
2075 while (N) {
2076 *--BufPtr = Digits[N % Radix];
2077 N /= Radix;
2078 }
2079 Str.append(BufPtr, std::end(Buffer));
2080 return;
2081 }
2082
2083 APInt Tmp(*this);
2084
2085 if (Signed && isNegative()) {
2086 // They want to print the signed version and it is a negative value
2087 // Flip the bits and add one to turn it into the equivalent positive
2088 // value and put a '-' in the result.
2089 Tmp.negate();
2090 Str.push_back('-');
2091 }
2092
2093 while (*Prefix) {
2094 Str.push_back(*Prefix);
2095 ++Prefix;
2096 };
2097
2098 // We insert the digits backward, then reverse them to get the right order.
2099 unsigned StartDig = Str.size();
2100
2101 // For the 2, 8 and 16 bit cases, we can just shift instead of divide
2102 // because the number of bits per digit (1, 3 and 4 respectively) divides
2103 // equally. We just shift until the value is zero.
2104 if (Radix == 2 || Radix == 8 || Radix == 16) {
2105 // Just shift tmp right for each digit width until it becomes zero
2106 unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
2107 unsigned MaskAmt = Radix - 1;
2108
2109 while (Tmp.getBoolValue()) {
2110 unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;
2111 Str.push_back(Digits[Digit]);
2112 Tmp.lshrInPlace(ShiftAmt);
2113 }
2114 } else {
2115 while (Tmp.getBoolValue()) {
2116 uint64_t Digit;
2117 udivrem(Tmp, Radix, Tmp, Digit);
2118 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~svn338205/lib/Support/APInt.cpp"
, 2118, __extension__ __PRETTY_FUNCTION__))
;
2119 Str.push_back(Digits[Digit]);
2120 }
2121 }
2122
2123 // Reverse the digits before returning.
2124 std::reverse(Str.begin()+StartDig, Str.end());
2125}
2126
2127/// Returns the APInt as a std::string. Note that this is an inefficient method.
2128/// It is better to pass in a SmallVector/SmallString to the methods above.
2129std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const {
2130 SmallString<40> S;
2131 toString(S, Radix, Signed, /* formatAsCLiteral = */false);
2132 return S.str();
2133}
2134
2135#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2136LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void APInt::dump() const {
2137 SmallString<40> S, U;
2138 this->toStringUnsigned(U);
2139 this->toStringSigned(S);
2140 dbgs() << "APInt(" << BitWidth << "b, "
2141 << U << "u " << S << "s)\n";
2142}
2143#endif
2144
2145void APInt::print(raw_ostream &OS, bool isSigned) const {
2146 SmallString<40> S;
2147 this->toString(S, 10, isSigned, /* formatAsCLiteral = */false);
2148 OS << S;
2149}
2150
2151// This implements a variety of operations on a representation of
2152// arbitrary precision, two's-complement, bignum integer values.
2153
2154// Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe
2155// and unrestricting assumption.
2156static_assert(APInt::APINT_BITS_PER_WORD % 2 == 0,
2157 "Part width must be divisible by 2!");
2158
2159/* Some handy functions local to this file. */
2160
2161/* Returns the integer part with the least significant BITS set.
2162 BITS cannot be zero. */
2163static inline APInt::WordType lowBitMask(unsigned bits) {
2164 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~svn338205/lib/Support/APInt.cpp"
, 2164, __extension__ __PRETTY_FUNCTION__))
;
2165
2166 return ~(APInt::WordType) 0 >> (APInt::APINT_BITS_PER_WORD - bits);
2167}
2168
2169/* Returns the value of the lower half of PART. */
2170static inline APInt::WordType lowHalf(APInt::WordType part) {
2171 return part & lowBitMask(APInt::APINT_BITS_PER_WORD / 2);
2172}
2173
2174/* Returns the value of the upper half of PART. */
2175static inline APInt::WordType highHalf(APInt::WordType part) {
2176 return part >> (APInt::APINT_BITS_PER_WORD / 2);
2177}
2178
2179/* Returns the bit number of the most significant set bit of a part.
2180 If the input number has no bits set -1U is returned. */
2181static unsigned partMSB(APInt::WordType value) {
2182 return findLastSet(value, ZB_Max);
2183}
2184
2185/* Returns the bit number of the least significant set bit of a
2186 part. If the input number has no bits set -1U is returned. */
2187static unsigned partLSB(APInt::WordType value) {
2188 return findFirstSet(value, ZB_Max);
2189}
2190
2191/* Sets the least significant part of a bignum to the input value, and
2192 zeroes out higher parts. */
2193void APInt::tcSet(WordType *dst, WordType part, unsigned parts) {
2194 assert(parts > 0)(static_cast <bool> (parts > 0) ? void (0) : __assert_fail
("parts > 0", "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 2194, __extension__ __PRETTY_FUNCTION__))
;
2195
2196 dst[0] = part;
2197 for (unsigned i = 1; i < parts; i++)
2198 dst[i] = 0;
2199}
2200
2201/* Assign one bignum to another. */
2202void APInt::tcAssign(WordType *dst, const WordType *src, unsigned parts) {
2203 for (unsigned i = 0; i < parts; i++)
2204 dst[i] = src[i];
2205}
2206
2207/* Returns true if a bignum is zero, false otherwise. */
2208bool APInt::tcIsZero(const WordType *src, unsigned parts) {
2209 for (unsigned i = 0; i < parts; i++)
2210 if (src[i])
2211 return false;
2212
2213 return true;
2214}
2215
2216/* Extract the given bit of a bignum; returns 0 or 1. */
2217int APInt::tcExtractBit(const WordType *parts, unsigned bit) {
2218 return (parts[whichWord(bit)] & maskBit(bit)) != 0;
2219}
2220
2221/* Set the given bit of a bignum. */
2222void APInt::tcSetBit(WordType *parts, unsigned bit) {
2223 parts[whichWord(bit)] |= maskBit(bit);
2224}
2225
2226/* Clears the given bit of a bignum. */
2227void APInt::tcClearBit(WordType *parts, unsigned bit) {
2228 parts[whichWord(bit)] &= ~maskBit(bit);
2229}
2230
2231/* Returns the bit number of the least significant set bit of a
2232 number. If the input number has no bits set -1U is returned. */
2233unsigned APInt::tcLSB(const WordType *parts, unsigned n) {
2234 for (unsigned i = 0; i < n; i++) {
2235 if (parts[i] != 0) {
2236 unsigned lsb = partLSB(parts[i]);
2237
2238 return lsb + i * APINT_BITS_PER_WORD;
2239 }
2240 }
2241
2242 return -1U;
2243}
2244
2245/* Returns the bit number of the most significant set bit of a number.
2246 If the input number has no bits set -1U is returned. */
2247unsigned APInt::tcMSB(const WordType *parts, unsigned n) {
2248 do {
2249 --n;
2250
2251 if (parts[n] != 0) {
2252 unsigned msb = partMSB(parts[n]);
2253
2254 return msb + n * APINT_BITS_PER_WORD;
2255 }
2256 } while (n);
2257
2258 return -1U;
2259}
2260
2261/* Copy the bit vector of width srcBITS from SRC, starting at bit
2262 srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
2263 the least significant bit of DST. All high bits above srcBITS in
2264 DST are zero-filled. */
2265void
2266APInt::tcExtract(WordType *dst, unsigned dstCount, const WordType *src,
2267 unsigned srcBits, unsigned srcLSB) {
2268 unsigned dstParts = (srcBits + APINT_BITS_PER_WORD - 1) / APINT_BITS_PER_WORD;
2269 assert(dstParts <= dstCount)(static_cast <bool> (dstParts <= dstCount) ? void (0
) : __assert_fail ("dstParts <= dstCount", "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 2269, __extension__ __PRETTY_FUNCTION__))
;
2270
2271 unsigned firstSrcPart = srcLSB / APINT_BITS_PER_WORD;
2272 tcAssign (dst, src + firstSrcPart, dstParts);
2273
2274 unsigned shift = srcLSB % APINT_BITS_PER_WORD;
2275 tcShiftRight (dst, dstParts, shift);
2276
2277 /* We now have (dstParts * APINT_BITS_PER_WORD - shift) bits from SRC
2278 in DST. If this is less that srcBits, append the rest, else
2279 clear the high bits. */
2280 unsigned n = dstParts * APINT_BITS_PER_WORD - shift;
2281 if (n < srcBits) {
2282 WordType mask = lowBitMask (srcBits - n);
2283 dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
2284 << n % APINT_BITS_PER_WORD);
2285 } else if (n > srcBits) {
2286 if (srcBits % APINT_BITS_PER_WORD)
2287 dst[dstParts - 1] &= lowBitMask (srcBits % APINT_BITS_PER_WORD);
2288 }
2289
2290 /* Clear high parts. */
2291 while (dstParts < dstCount)
2292 dst[dstParts++] = 0;
2293}
2294
2295/* DST += RHS + C where C is zero or one. Returns the carry flag. */
2296APInt::WordType APInt::tcAdd(WordType *dst, const WordType *rhs,
2297 WordType c, unsigned parts) {
2298 assert(c <= 1)(static_cast <bool> (c <= 1) ? void (0) : __assert_fail
("c <= 1", "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 2298, __extension__ __PRETTY_FUNCTION__))
;
2299
2300 for (unsigned i = 0; i < parts; i++) {
2301 WordType l = dst[i];
2302 if (c) {
2303 dst[i] += rhs[i] + 1;
2304 c = (dst[i] <= l);
2305 } else {
2306 dst[i] += rhs[i];
2307 c = (dst[i] < l);
2308 }
2309 }
2310
2311 return c;
2312}
2313
2314/// This function adds a single "word" integer, src, to the multiple
2315/// "word" integer array, dst[]. dst[] is modified to reflect the addition and
2316/// 1 is returned if there is a carry out, otherwise 0 is returned.
2317/// @returns the carry of the addition.
2318APInt::WordType APInt::tcAddPart(WordType *dst, WordType src,
2319 unsigned parts) {
2320 for (unsigned i = 0; i < parts; ++i) {
2321 dst[i] += src;
2322 if (dst[i] >= src)
2323 return 0; // No need to carry so exit early.
2324 src = 1; // Carry one to next digit.
2325 }
2326
2327 return 1;
2328}
2329
2330/* DST -= RHS + C where C is zero or one. Returns the carry flag. */
2331APInt::WordType APInt::tcSubtract(WordType *dst, const WordType *rhs,
2332 WordType c, unsigned parts) {
2333 assert(c <= 1)(static_cast <bool> (c <= 1) ? void (0) : __assert_fail
("c <= 1", "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 2333, __extension__ __PRETTY_FUNCTION__))
;
2334
2335 for (unsigned i = 0; i < parts; i++) {
2336 WordType l = dst[i];
2337 if (c) {
2338 dst[i] -= rhs[i] + 1;
2339 c = (dst[i] >= l);
2340 } else {
2341 dst[i] -= rhs[i];
2342 c = (dst[i] > l);
2343 }
2344 }
2345
2346 return c;
2347}
2348
2349/// This function subtracts a single "word" (64-bit word), src, from
2350/// the multi-word integer array, dst[], propagating the borrowed 1 value until
2351/// no further borrowing is needed or it runs out of "words" in dst. The result
2352/// is 1 if "borrowing" exhausted the digits in dst, or 0 if dst was not
2353/// exhausted. In other words, if src > dst then this function returns 1,
2354/// otherwise 0.
2355/// @returns the borrow out of the subtraction
2356APInt::WordType APInt::tcSubtractPart(WordType *dst, WordType src,
2357 unsigned parts) {
2358 for (unsigned i = 0; i < parts; ++i) {
2359 WordType Dst = dst[i];
2360 dst[i] -= src;
2361 if (src <= Dst)
2362 return 0; // No need to borrow so exit early.
2363 src = 1; // We have to "borrow 1" from next "word"
2364 }
2365
2366 return 1;
2367}
2368
2369/* Negate a bignum in-place. */
2370void APInt::tcNegate(WordType *dst, unsigned parts) {
2371 tcComplement(dst, parts);
2372 tcIncrement(dst, parts);
2373}
2374
2375/* DST += SRC * MULTIPLIER + CARRY if add is true
2376 DST = SRC * MULTIPLIER + CARRY if add is false
2377
2378 Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC
2379 they must start at the same point, i.e. DST == SRC.
2380
2381 If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
2382 returned. Otherwise DST is filled with the least significant
2383 DSTPARTS parts of the result, and if all of the omitted higher
2384 parts were zero return zero, otherwise overflow occurred and
2385 return one. */
2386int APInt::tcMultiplyPart(WordType *dst, const WordType *src,
2387 WordType multiplier, WordType carry,
2388 unsigned srcParts, unsigned dstParts,
2389 bool add) {
2390 /* Otherwise our writes of DST kill our later reads of SRC. */
2391 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~svn338205/lib/Support/APInt.cpp"
, 2391, __extension__ __PRETTY_FUNCTION__))
;
2392 assert(dstParts <= srcParts + 1)(static_cast <bool> (dstParts <= srcParts + 1) ? void
(0) : __assert_fail ("dstParts <= srcParts + 1", "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 2392, __extension__ __PRETTY_FUNCTION__))
;
2393
2394 /* N loops; minimum of dstParts and srcParts. */
2395 unsigned n = std::min(dstParts, srcParts);
2396
2397 for (unsigned i = 0; i < n; i++) {
2398 WordType low, mid, high, srcPart;
2399
2400 /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
2401
2402 This cannot overflow, because
2403
2404 (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
2405
2406 which is less than n^2. */
2407
2408 srcPart = src[i];
2409
2410 if (multiplier == 0 || srcPart == 0) {
2411 low = carry;
2412 high = 0;
2413 } else {
2414 low = lowHalf(srcPart) * lowHalf(multiplier);
2415 high = highHalf(srcPart) * highHalf(multiplier);
2416
2417 mid = lowHalf(srcPart) * highHalf(multiplier);
2418 high += highHalf(mid);
2419 mid <<= APINT_BITS_PER_WORD / 2;
2420 if (low + mid < low)
2421 high++;
2422 low += mid;
2423
2424 mid = highHalf(srcPart) * lowHalf(multiplier);
2425 high += highHalf(mid);
2426 mid <<= APINT_BITS_PER_WORD / 2;
2427 if (low + mid < low)
2428 high++;
2429 low += mid;
2430
2431 /* Now add carry. */
2432 if (low + carry < low)
2433 high++;
2434 low += carry;
2435 }
2436
2437 if (add) {
2438 /* And now DST[i], and store the new low part there. */
2439 if (low + dst[i] < low)
2440 high++;
2441 dst[i] += low;
2442 } else
2443 dst[i] = low;
2444
2445 carry = high;
2446 }
2447
2448 if (srcParts < dstParts) {
2449 /* Full multiplication, there is no overflow. */
2450 assert(srcParts + 1 == dstParts)(static_cast <bool> (srcParts + 1 == dstParts) ? void (
0) : __assert_fail ("srcParts + 1 == dstParts", "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 2450, __extension__ __PRETTY_FUNCTION__))
;
2451 dst[srcParts] = carry;
2452 return 0;
2453 }
2454
2455 /* We overflowed if there is carry. */
2456 if (carry)
2457 return 1;
2458
2459 /* We would overflow if any significant unwritten parts would be
2460 non-zero. This is true if any remaining src parts are non-zero
2461 and the multiplier is non-zero. */
2462 if (multiplier)
2463 for (unsigned i = dstParts; i < srcParts; i++)
2464 if (src[i])
2465 return 1;
2466
2467 /* We fitted in the narrow destination. */
2468 return 0;
2469}
2470
2471/* DST = LHS * RHS, where DST has the same width as the operands and
2472 is filled with the least significant parts of the result. Returns
2473 one if overflow occurred, otherwise zero. DST must be disjoint
2474 from both operands. */
2475int APInt::tcMultiply(WordType *dst, const WordType *lhs,
2476 const WordType *rhs, unsigned parts) {
2477 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~svn338205/lib/Support/APInt.cpp"
, 2477, __extension__ __PRETTY_FUNCTION__))
;
2478
2479 int overflow = 0;
2480 tcSet(dst, 0, parts);
2481
2482 for (unsigned i = 0; i < parts; i++)
2483 overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
2484 parts - i, true);
2485
2486 return overflow;
2487}
2488
2489/// DST = LHS * RHS, where DST has width the sum of the widths of the
2490/// operands. No overflow occurs. DST must be disjoint from both operands.
2491void APInt::tcFullMultiply(WordType *dst, const WordType *lhs,
2492 const WordType *rhs, unsigned lhsParts,
2493 unsigned rhsParts) {
2494 /* Put the narrower number on the LHS for less loops below. */
2495 if (lhsParts > rhsParts)
2496 return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
2497
2498 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~svn338205/lib/Support/APInt.cpp"
, 2498, __extension__ __PRETTY_FUNCTION__))
;
2499
2500 tcSet(dst, 0, rhsParts);
2501
2502 for (unsigned i = 0; i < lhsParts; i++)
2503 tcMultiplyPart(&dst[i], rhs, lhs[i], 0, rhsParts, rhsParts + 1, true);
2504}
2505
2506/* If RHS is zero LHS and REMAINDER are left unchanged, return one.
2507 Otherwise set LHS to LHS / RHS with the fractional part discarded,
2508 set REMAINDER to the remainder, return zero. i.e.
2509
2510 OLD_LHS = RHS * LHS + REMAINDER
2511
2512 SCRATCH is a bignum of the same size as the operands and result for
2513 use by the routine; its contents need not be initialized and are
2514 destroyed. LHS, REMAINDER and SCRATCH must be distinct.
2515*/
2516int APInt::tcDivide(WordType *lhs, const WordType *rhs,
2517 WordType *remainder, WordType *srhs,
2518 unsigned parts) {
2519 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~svn338205/lib/Support/APInt.cpp"
, 2519, __extension__ __PRETTY_FUNCTION__))
;
2520
2521 unsigned shiftCount = tcMSB(rhs, parts) + 1;
2522 if (shiftCount == 0)
2523 return true;
2524
2525 shiftCount = parts * APINT_BITS_PER_WORD - shiftCount;
2526 unsigned n = shiftCount / APINT_BITS_PER_WORD;
2527 WordType mask = (WordType) 1 << (shiftCount % APINT_BITS_PER_WORD);
2528
2529 tcAssign(srhs, rhs, parts);
2530 tcShiftLeft(srhs, parts, shiftCount);
2531 tcAssign(remainder, lhs, parts);
2532 tcSet(lhs, 0, parts);
2533
2534 /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
2535 the total. */
2536 for (;;) {
2537 int compare = tcCompare(remainder, srhs, parts);
2538 if (compare >= 0) {
2539 tcSubtract(remainder, srhs, 0, parts);
2540 lhs[n] |= mask;
2541 }
2542
2543 if (shiftCount == 0)
2544 break;
2545 shiftCount--;
2546 tcShiftRight(srhs, parts, 1);
2547 if ((mask >>= 1) == 0) {
2548 mask = (WordType) 1 << (APINT_BITS_PER_WORD - 1);
2549 n--;
2550 }
2551 }
2552
2553 return false;
2554}
2555
2556/// Shift a bignum left Cound bits in-place. Shifted in bits are zero. There are
2557/// no restrictions on Count.
2558void APInt::tcShiftLeft(WordType *Dst, unsigned Words, unsigned Count) {
2559 // Don't bother performing a no-op shift.
2560 if (!Count)
2561 return;
2562
2563 // WordShift is the inter-part shift; BitShift is the intra-part shift.
2564 unsigned WordShift = std::min(Count / APINT_BITS_PER_WORD, Words);
2565 unsigned BitShift = Count % APINT_BITS_PER_WORD;
2566
2567 // Fastpath for moving by whole words.
2568 if (BitShift == 0) {
2569 std::memmove(Dst + WordShift, Dst, (Words - WordShift) * APINT_WORD_SIZE);
2570 } else {
2571 while (Words-- > WordShift) {
2572 Dst[Words] = Dst[Words - WordShift] << BitShift;
2573 if (Words > WordShift)
2574 Dst[Words] |=
2575 Dst[Words - WordShift - 1] >> (APINT_BITS_PER_WORD - BitShift);
2576 }
2577 }
2578
2579 // Fill in the remainder with 0s.
2580 std::memset(Dst, 0, WordShift * APINT_WORD_SIZE);
2581}
2582
2583/// Shift a bignum right Count bits in-place. Shifted in bits are zero. There
2584/// are no restrictions on Count.
2585void APInt::tcShiftRight(WordType *Dst, unsigned Words, unsigned Count) {
2586 // Don't bother performing a no-op shift.
2587 if (!Count)
2588 return;
2589
2590 // WordShift is the inter-part shift; BitShift is the intra-part shift.
2591 unsigned WordShift = std::min(Count / APINT_BITS_PER_WORD, Words);
2592 unsigned BitShift = Count % APINT_BITS_PER_WORD;
2593
2594 unsigned WordsToMove = Words - WordShift;
2595 // Fastpath for moving by whole words.
2596 if (BitShift == 0) {
2597 std::memmove(Dst, Dst + WordShift, WordsToMove * APINT_WORD_SIZE);
2598 } else {
2599 for (unsigned i = 0; i != WordsToMove; ++i) {
2600 Dst[i] = Dst[i + WordShift] >> BitShift;
2601 if (i + 1 != WordsToMove)
2602 Dst[i] |= Dst[i + WordShift + 1] << (APINT_BITS_PER_WORD - BitShift);
2603 }
2604 }
2605
2606 // Fill in the remainder with 0s.
2607 std::memset(Dst + WordsToMove, 0, WordShift * APINT_WORD_SIZE);
2608}
2609
2610/* Bitwise and of two bignums. */
2611void APInt::tcAnd(WordType *dst, const WordType *rhs, unsigned parts) {
2612 for (unsigned i = 0; i < parts; i++)
2613 dst[i] &= rhs[i];
2614}
2615
2616/* Bitwise inclusive or of two bignums. */
2617void APInt::tcOr(WordType *dst, const WordType *rhs, unsigned parts) {
2618 for (unsigned i = 0; i < parts; i++)
2619 dst[i] |= rhs[i];
2620}
2621
2622/* Bitwise exclusive or of two bignums. */
2623void APInt::tcXor(WordType *dst, const WordType *rhs, unsigned parts) {
2624 for (unsigned i = 0; i < parts; i++)
2625 dst[i] ^= rhs[i];
2626}
2627
2628/* Complement a bignum in-place. */
2629void APInt::tcComplement(WordType *dst, unsigned parts) {
2630 for (unsigned i = 0; i < parts; i++)
2631 dst[i] = ~dst[i];
2632}
2633
2634/* Comparison (unsigned) of two bignums. */
2635int APInt::tcCompare(const WordType *lhs, const WordType *rhs,
2636 unsigned parts) {
2637 while (parts) {
2638 parts--;
2639 if (lhs[parts] != rhs[parts])
2640 return (lhs[parts] > rhs[parts]) ? 1 : -1;
2641 }
2642
2643 return 0;
2644}
2645
2646/* Set the least significant BITS bits of a bignum, clear the
2647 rest. */
2648void APInt::tcSetLeastSignificantBits(WordType *dst, unsigned parts,
2649 unsigned bits) {
2650 unsigned i = 0;
2651 while (bits > APINT_BITS_PER_WORD) {
2652 dst[i++] = ~(WordType) 0;
2653 bits -= APINT_BITS_PER_WORD;
2654 }
2655
2656 if (bits)
2657 dst[i++] = ~(WordType) 0 >> (APINT_BITS_PER_WORD - bits);
2658
2659 while (i < parts)
2660 dst[i++] = 0;
2661}
2662
2663APInt llvm::APIntOps::RoundingUDiv(const APInt &A, const APInt &B,
2664 APInt::Rounding RM) {
2665 // Currently udivrem always rounds down.
2666 switch (RM) {
2667 case APInt::Rounding::DOWN:
2668 case APInt::Rounding::TOWARD_ZERO:
2669 return A.udiv(B);
2670 case APInt::Rounding::UP: {
2671 APInt Quo, Rem;
2672 APInt::udivrem(A, B, Quo, Rem);
2673 if (Rem == 0)
2674 return Quo;
2675 return Quo + 1;
2676 }
2677 }
2678 llvm_unreachable("Unknown APInt::Rounding enum")::llvm::llvm_unreachable_internal("Unknown APInt::Rounding enum"
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 2678)
;
2679}
2680
2681APInt llvm::APIntOps::RoundingSDiv(const APInt &A, const APInt &B,
2682 APInt::Rounding RM) {
2683 switch (RM) {
2684 case APInt::Rounding::DOWN:
2685 case APInt::Rounding::UP: {
2686 APInt Quo, Rem;
2687 APInt::sdivrem(A, B, Quo, Rem);
2688 if (Rem == 0)
2689 return Quo;
2690 // This algorithm deals with arbitrary rounding mode used by sdivrem.
2691 // We want to check whether the non-integer part of the mathematical value
2692 // is negative or not. If the non-integer part is negative, we need to round
2693 // down from Quo; otherwise, if it's positive or 0, we return Quo, as it's
2694 // already rounded down.
2695 if (RM == APInt::Rounding::DOWN) {
2696 if (Rem.isNegative() != B.isNegative())
2697 return Quo - 1;
2698 return Quo;
2699 }
2700 if (Rem.isNegative() != B.isNegative())
2701 return Quo;
2702 return Quo + 1;
2703 }
2704 // Currently sdiv rounds twards zero.
2705 case APInt::Rounding::TOWARD_ZERO:
2706 return A.sdiv(B);
2707 }
2708 llvm_unreachable("Unknown APInt::Rounding enum")::llvm::llvm_unreachable_internal("Unknown APInt::Rounding enum"
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Support/APInt.cpp"
, 2708)
;
2709}

/build/llvm-toolchain-snapshot-7~svn338205/include/llvm/ADT/APInt.h

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