Bug Summary

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

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name APInt.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mthread-model posix -mframe-pointer=none -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-10/lib/clang/10.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-10~svn374877/build-llvm/lib/Support -I /build/llvm-toolchain-snapshot-10~svn374877/lib/Support -I /build/llvm-toolchain-snapshot-10~svn374877/build-llvm/include -I /build/llvm-toolchain-snapshot-10~svn374877/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-10/lib/clang/10.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-10~svn374877/build-llvm/lib/Support -fdebug-prefix-map=/build/llvm-toolchain-snapshot-10~svn374877=. -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -o /tmp/scan-build-2019-10-15-233810-7101-1 -x c++ /build/llvm-toolchain-snapshot-10~svn374877/lib/Support/APInt.cpp

/build/llvm-toolchain-snapshot-10~svn374877/lib/Support/APInt.cpp

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

/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/APInt.h

1//===-- llvm/ADT/APInt.h - For Arbitrary Precision Integer -----*- C++ -*--===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8///
9/// \file
10/// This file implements a class to represent arbitrary precision
11/// integral constant values and operations on them.
12///
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_ADT_APINT_H
16#define LLVM_ADT_APINT_H
17
18#include "llvm/Support/Compiler.h"
19#include "llvm/Support/MathExtras.h"
20#include <cassert>
21#include <climits>
22#include <cstring>
23#include <string>
24
25namespace llvm {
26class FoldingSetNodeID;
27class StringRef;
28class hash_code;
29class raw_ostream;
30
31template <typename T> class SmallVectorImpl;
32template <typename T> class ArrayRef;
33template <typename T> class Optional;
34
35class APInt;
36
37inline APInt operator-(APInt);
38
39//===----------------------------------------------------------------------===//
40// APInt Class
41//===----------------------------------------------------------------------===//
42
43/// Class for arbitrary precision integers.
44///
45/// APInt is a functional replacement for common case unsigned integer type like
46/// "unsigned", "unsigned long" or "uint64_t", but also allows non-byte-width
47/// integer sizes and large integer value types such as 3-bits, 15-bits, or more
48/// than 64-bits of precision. APInt provides a variety of arithmetic operators
49/// and methods to manipulate integer values of any bit-width. It supports both
50/// the typical integer arithmetic and comparison operations as well as bitwise
51/// manipulation.
52///
53/// The class has several invariants worth noting:
54/// * All bit, byte, and word positions are zero-based.
55/// * Once the bit width is set, it doesn't change except by the Truncate,
56/// SignExtend, or ZeroExtend operations.
57/// * All binary operators must be on APInt instances of the same bit width.
58/// Attempting to use these operators on instances with different bit
59/// widths will yield an assertion.
60/// * The value is stored canonically as an unsigned value. For operations
61/// where it makes a difference, there are both signed and unsigned variants
62/// of the operation. For example, sdiv and udiv. However, because the bit
63/// widths must be the same, operations such as Mul and Add produce the same
64/// results regardless of whether the values are interpreted as signed or
65/// not.
66/// * In general, the class tries to follow the style of computation that LLVM
67/// uses in its IR. This simplifies its use for LLVM.
68///
69class LLVM_NODISCARD[[clang::warn_unused_result]] APInt {
70public:
71 typedef uint64_t WordType;
72
73 /// This enum is used to hold the constants we needed for APInt.
74 enum : unsigned {
75 /// Byte size of a word.
76 APINT_WORD_SIZE = sizeof(WordType),
77 /// Bits in a word.
78 APINT_BITS_PER_WORD = APINT_WORD_SIZE * CHAR_BIT8
79 };
80
81 enum class Rounding {
82 DOWN,
83 TOWARD_ZERO,
84 UP,
85 };
86
87 static const WordType WORDTYPE_MAX = ~WordType(0);
88
89private:
90 /// This union is used to store the integer value. When the
91 /// integer bit-width <= 64, it uses VAL, otherwise it uses pVal.
92 union {
93 uint64_t VAL; ///< Used to store the <= 64 bits integer value.
94 uint64_t *pVal; ///< Used to store the >64 bits integer value.
95 } U;
96
97 unsigned BitWidth; ///< The number of bits in this APInt.
98
99 friend struct DenseMapAPIntKeyInfo;
100
101 friend class APSInt;
102
103 /// Fast internal constructor
104 ///
105 /// This constructor is used only internally for speed of construction of
106 /// temporaries. It is unsafe for general use so it is not public.
107 APInt(uint64_t *val, unsigned bits) : BitWidth(bits) {
108 U.pVal = val;
109 }
110
111 /// Determine if this APInt just has one word to store value.
112 ///
113 /// \returns true if the number of bits <= 64, false otherwise.
114 bool isSingleWord() const { return BitWidth <= APINT_BITS_PER_WORD; }
115
116 /// Determine which word a bit is in.
117 ///
118 /// \returns the word position for the specified bit position.
119 static unsigned whichWord(unsigned bitPosition) {
120 return bitPosition / APINT_BITS_PER_WORD;
121 }
122
123 /// Determine which bit in a word a bit is in.
124 ///
125 /// \returns the bit position in a word for the specified bit position
126 /// in the APInt.
127 static unsigned whichBit(unsigned bitPosition) {
128 return bitPosition % APINT_BITS_PER_WORD;
129 }
130
131 /// Get a single bit mask.
132 ///
133 /// \returns a uint64_t with only bit at "whichBit(bitPosition)" set
134 /// This method generates and returns a uint64_t (word) mask for a single
135 /// bit at a specific bit position. This is used to mask the bit in the
136 /// corresponding word.
137 static uint64_t maskBit(unsigned bitPosition) {
138 return 1ULL << whichBit(bitPosition);
139 }
140
141 /// Clear unused high order bits
142 ///
143 /// This method is used internally to clear the top "N" bits in the high order
144 /// word that are not used by the APInt. This is needed after the most
145 /// significant word is assigned a value to ensure that those bits are
146 /// zero'd out.
147 APInt &clearUnusedBits() {
148 // Compute how many bits are used in the final word
149 unsigned WordBits = ((BitWidth-1) % APINT_BITS_PER_WORD) + 1;
150
151 // Mask out the high bits.
152 uint64_t mask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - WordBits);
153 if (isSingleWord())
154 U.VAL &= mask;
155 else
156 U.pVal[getNumWords() - 1] &= mask;
157 return *this;
158 }
159
160 /// Get the word corresponding to a bit position
161 /// \returns the corresponding word for the specified bit position.
162 uint64_t getWord(unsigned bitPosition) const {
163 return isSingleWord() ? U.VAL : U.pVal[whichWord(bitPosition)];
164 }
165
166 /// Utility method to change the bit width of this APInt to new bit width,
167 /// allocating and/or deallocating as necessary. There is no guarantee on the
168 /// value of any bits upon return. Caller should populate the bits after.
169 void reallocate(unsigned NewBitWidth);
170
171 /// Convert a char array into an APInt
172 ///
173 /// \param radix 2, 8, 10, 16, or 36
174 /// Converts a string into a number. The string must be non-empty
175 /// and well-formed as a number of the given base. The bit-width
176 /// must be sufficient to hold the result.
177 ///
178 /// This is used by the constructors that take string arguments.
179 ///
180 /// StringRef::getAsInteger is superficially similar but (1) does
181 /// not assume that the string is well-formed and (2) grows the
182 /// result to hold the input.
183 void fromString(unsigned numBits, StringRef str, uint8_t radix);
184
185 /// An internal division function for dividing APInts.
186 ///
187 /// This is used by the toString method to divide by the radix. It simply
188 /// provides a more convenient form of divide for internal use since KnuthDiv
189 /// has specific constraints on its inputs. If those constraints are not met
190 /// then it provides a simpler form of divide.
191 static void divide(const WordType *LHS, unsigned lhsWords,
192 const WordType *RHS, unsigned rhsWords, WordType *Quotient,
193 WordType *Remainder);
194
195 /// out-of-line slow case for inline constructor
196 void initSlowCase(uint64_t val, bool isSigned);
197
198 /// shared code between two array constructors
199 void initFromArray(ArrayRef<uint64_t> array);
200
201 /// out-of-line slow case for inline copy constructor
202 void initSlowCase(const APInt &that);
203
204 /// out-of-line slow case for shl
205 void shlSlowCase(unsigned ShiftAmt);
206
207 /// out-of-line slow case for lshr.
208 void lshrSlowCase(unsigned ShiftAmt);
209
210 /// out-of-line slow case for ashr.
211 void ashrSlowCase(unsigned ShiftAmt);
212
213 /// out-of-line slow case for operator=
214 void AssignSlowCase(const APInt &RHS);
215
216 /// out-of-line slow case for operator==
217 bool EqualSlowCase(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__));
218
219 /// out-of-line slow case for countLeadingZeros
220 unsigned countLeadingZerosSlowCase() const LLVM_READONLY__attribute__((__pure__));
221
222 /// out-of-line slow case for countLeadingOnes.
223 unsigned countLeadingOnesSlowCase() const LLVM_READONLY__attribute__((__pure__));
224
225 /// out-of-line slow case for countTrailingZeros.
226 unsigned countTrailingZerosSlowCase() const LLVM_READONLY__attribute__((__pure__));
227
228 /// out-of-line slow case for countTrailingOnes
229 unsigned countTrailingOnesSlowCase() const LLVM_READONLY__attribute__((__pure__));
230
231 /// out-of-line slow case for countPopulation
232 unsigned countPopulationSlowCase() const LLVM_READONLY__attribute__((__pure__));
233
234 /// out-of-line slow case for intersects.
235 bool intersectsSlowCase(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__));
236
237 /// out-of-line slow case for isSubsetOf.
238 bool isSubsetOfSlowCase(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__));
239
240 /// out-of-line slow case for setBits.
241 void setBitsSlowCase(unsigned loBit, unsigned hiBit);
242
243 /// out-of-line slow case for flipAllBits.
244 void flipAllBitsSlowCase();
245
246 /// out-of-line slow case for operator&=.
247 void AndAssignSlowCase(const APInt& RHS);
248
249 /// out-of-line slow case for operator|=.
250 void OrAssignSlowCase(const APInt& RHS);
251
252 /// out-of-line slow case for operator^=.
253 void XorAssignSlowCase(const APInt& RHS);
254
255 /// Unsigned comparison. Returns -1, 0, or 1 if this APInt is less than, equal
256 /// to, or greater than RHS.
257 int compare(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__));
258
259 /// Signed comparison. Returns -1, 0, or 1 if this APInt is less than, equal
260 /// to, or greater than RHS.
261 int compareSigned(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__));
262
263public:
264 /// \name Constructors
265 /// @{
266
267 /// Create a new APInt of numBits width, initialized as val.
268 ///
269 /// If isSigned is true then val is treated as if it were a signed value
270 /// (i.e. as an int64_t) and the appropriate sign extension to the bit width
271 /// will be done. Otherwise, no sign extension occurs (high order bits beyond
272 /// the range of val are zero filled).
273 ///
274 /// \param numBits the bit width of the constructed APInt
275 /// \param val the initial value of the APInt
276 /// \param isSigned how to treat signedness of val
277 APInt(unsigned numBits, uint64_t val, bool isSigned = false)
278 : BitWidth(numBits) {
279 assert(BitWidth && "bitwidth too small")((BitWidth && "bitwidth too small") ? static_cast<
void> (0) : __assert_fail ("BitWidth && \"bitwidth too small\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/APInt.h"
, 279, __PRETTY_FUNCTION__))
;
280 if (isSingleWord()) {
281 U.VAL = val;
282 clearUnusedBits();
283 } else {
284 initSlowCase(val, isSigned);
285 }
286 }
287
288 /// Construct an APInt of numBits width, initialized as bigVal[].
289 ///
290 /// Note that bigVal.size() can be smaller or larger than the corresponding
291 /// bit width but any extraneous bits will be dropped.
292 ///
293 /// \param numBits the bit width of the constructed APInt
294 /// \param bigVal a sequence of words to form the initial value of the APInt
295 APInt(unsigned numBits, ArrayRef<uint64_t> bigVal);
296
297 /// Equivalent to APInt(numBits, ArrayRef<uint64_t>(bigVal, numWords)), but
298 /// deprecated because this constructor is prone to ambiguity with the
299 /// APInt(unsigned, uint64_t, bool) constructor.
300 ///
301 /// If this overload is ever deleted, care should be taken to prevent calls
302 /// from being incorrectly captured by the APInt(unsigned, uint64_t, bool)
303 /// constructor.
304 APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[]);
305
306 /// Construct an APInt from a string representation.
307 ///
308 /// This constructor interprets the string \p str in the given radix. The
309 /// interpretation stops when the first character that is not suitable for the
310 /// radix is encountered, or the end of the string. Acceptable radix values
311 /// are 2, 8, 10, 16, and 36. It is an error for the value implied by the
312 /// string to require more bits than numBits.
313 ///
314 /// \param numBits the bit width of the constructed APInt
315 /// \param str the string to be interpreted
316 /// \param radix the radix to use for the conversion
317 APInt(unsigned numBits, StringRef str, uint8_t radix);
318
319 /// Simply makes *this a copy of that.
320 /// Copy Constructor.
321 APInt(const APInt &that) : BitWidth(that.BitWidth) {
322 if (isSingleWord())
323 U.VAL = that.U.VAL;
324 else
325 initSlowCase(that);
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 == WORDTYPE_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 ???")((N && "N == 0 ???") ? static_cast<void> (0) : __assert_fail
("N && \"N == 0 ???\"", "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/APInt.h"
, 450, __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 ???")((N && "N == 0 ???") ? static_cast<void> (0) : __assert_fail
("N && \"N == 0 ???\"", "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/APInt.h"
, 456, __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();
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")((numBits != 0 && "numBits must be non-zero") ? static_cast
<void> (0) : __assert_fail ("numBits != 0 && \"numBits must be non-zero\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/APInt.h"
, 495, __PRETTY_FUNCTION__))
;
496 assert(numBits <= BitWidth && "numBits out of range")((numBits <= BitWidth && "numBits out of range") ?
static_cast<void> (0) : __assert_fail ("numBits <= BitWidth && \"numBits out of range\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/APInt.h"
, 496, __PRETTY_FUNCTION__))
;
497 if (isSingleWord())
498 return U.VAL == (WORDTYPE_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, WORDTYPE_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);
14
Calling 'APInt::AssignSlowCase'
26
Returned allocated memory
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")((this != &that && "Self-move not supported") ? static_cast
<void> (0) : __assert_fail ("this != &that && \"Self-move not supported\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/APInt.h"
, 753, __PRETTY_FUNCTION__))
;
30
'?' condition is true
754 if (!isSingleWord())
31
Taking true branch
755 delete[] U.pVal;
32
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")((BitWidth == RHS.BitWidth && "Bit widths must be the same"
) ? static_cast<void> (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/APInt.h"
, 792, __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")((BitWidth == RHS.BitWidth && "Bit widths must be the same"
) ? static_cast<void> (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/APInt.h"
, 822, __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")((BitWidth == RHS.BitWidth && "Bit widths must be the same"
) ? static_cast<void> (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/APInt.h"
, 852, __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")((ShiftAmt <= BitWidth && "Invalid shift amount") ?
static_cast<void> (0) : __assert_fail ("ShiftAmt <= BitWidth && \"Invalid shift amount\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/APInt.h"
, 905, __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")((ShiftAmt <= BitWidth && "Invalid shift amount") ?
static_cast<void> (0) : __assert_fail ("ShiftAmt <= BitWidth && \"Invalid shift amount\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/APInt.h"
, 954, __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")((ShiftAmt <= BitWidth && "Invalid shift amount") ?
static_cast<void> (0) : __assert_fail ("ShiftAmt <= BitWidth && \"Invalid shift amount\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/APInt.h"
, 978, __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 // Operations that saturate
1108 APInt sadd_sat(const APInt &RHS) const;
1109 APInt uadd_sat(const APInt &RHS) const;
1110 APInt ssub_sat(const APInt &RHS) const;
1111 APInt usub_sat(const APInt &RHS) const;
1112
1113 /// Array-indexing support.
1114 ///
1115 /// \returns the bit value at bitPosition
1116 bool operator[](unsigned bitPosition) const {
1117 assert(bitPosition < getBitWidth() && "Bit position out of bounds!")((bitPosition < getBitWidth() && "Bit position out of bounds!"
) ? static_cast<void> (0) : __assert_fail ("bitPosition < getBitWidth() && \"Bit position out of bounds!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/APInt.h"
, 1117, __PRETTY_FUNCTION__))
;
1118 return (maskBit(bitPosition) & getWord(bitPosition)) != 0;
1119 }
1120
1121 /// @}
1122 /// \name Comparison Operators
1123 /// @{
1124
1125 /// Equality operator.
1126 ///
1127 /// Compares this APInt with RHS for the validity of the equality
1128 /// relationship.
1129 bool operator==(const APInt &RHS) const {
1130 assert(BitWidth == RHS.BitWidth && "Comparison requires equal bit widths")((BitWidth == RHS.BitWidth && "Comparison requires equal bit widths"
) ? static_cast<void> (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Comparison requires equal bit widths\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/APInt.h"
, 1130, __PRETTY_FUNCTION__))
;
1131 if (isSingleWord())
1132 return U.VAL == RHS.U.VAL;
1133 return EqualSlowCase(RHS);
1134 }
1135
1136 /// Equality operator.
1137 ///
1138 /// Compares this APInt with a uint64_t for the validity of the equality
1139 /// relationship.
1140 ///
1141 /// \returns true if *this == Val
1142 bool operator==(uint64_t Val) const {
1143 return (isSingleWord() || getActiveBits() <= 64) && getZExtValue() == Val;
1144 }
1145
1146 /// Equality comparison.
1147 ///
1148 /// Compares this APInt with RHS for the validity of the equality
1149 /// relationship.
1150 ///
1151 /// \returns true if *this == Val
1152 bool eq(const APInt &RHS) const { return (*this) == RHS; }
1153
1154 /// Inequality operator.
1155 ///
1156 /// Compares this APInt with RHS for the validity of the inequality
1157 /// relationship.
1158 ///
1159 /// \returns true if *this != Val
1160 bool operator!=(const APInt &RHS) const { return !((*this) == RHS); }
1161
1162 /// Inequality operator.
1163 ///
1164 /// Compares this APInt with a uint64_t for the validity of the inequality
1165 /// relationship.
1166 ///
1167 /// \returns true if *this != Val
1168 bool operator!=(uint64_t Val) const { return !((*this) == Val); }
1169
1170 /// Inequality comparison
1171 ///
1172 /// Compares this APInt with RHS for the validity of the inequality
1173 /// relationship.
1174 ///
1175 /// \returns true if *this != Val
1176 bool ne(const APInt &RHS) const { return !((*this) == RHS); }
1177
1178 /// Unsigned less than comparison
1179 ///
1180 /// Regards both *this and RHS as unsigned quantities and compares them for
1181 /// the validity of the less-than relationship.
1182 ///
1183 /// \returns true if *this < RHS when both are considered unsigned.
1184 bool ult(const APInt &RHS) const { return compare(RHS) < 0; }
1185
1186 /// Unsigned less than comparison
1187 ///
1188 /// Regards both *this as an unsigned quantity and compares it with RHS for
1189 /// the validity of the less-than relationship.
1190 ///
1191 /// \returns true if *this < RHS when considered unsigned.
1192 bool ult(uint64_t RHS) const {
1193 // Only need to check active bits if not a single word.
1194 return (isSingleWord() || getActiveBits() <= 64) && getZExtValue() < RHS;
1195 }
1196
1197 /// Signed less than comparison
1198 ///
1199 /// Regards both *this and RHS as signed quantities and compares them for
1200 /// validity of the less-than relationship.
1201 ///
1202 /// \returns true if *this < RHS when both are considered signed.
1203 bool slt(const APInt &RHS) const { return compareSigned(RHS) < 0; }
1204
1205 /// Signed less than comparison
1206 ///
1207 /// Regards both *this as a signed quantity and compares it with RHS for
1208 /// the validity of the less-than relationship.
1209 ///
1210 /// \returns true if *this < RHS when considered signed.
1211 bool slt(int64_t RHS) const {
1212 return (!isSingleWord() && getMinSignedBits() > 64) ? isNegative()
1213 : getSExtValue() < RHS;
1214 }
1215
1216 /// Unsigned less or equal comparison
1217 ///
1218 /// Regards both *this and RHS as unsigned quantities and compares them for
1219 /// validity of the less-or-equal relationship.
1220 ///
1221 /// \returns true if *this <= RHS when both are considered unsigned.
1222 bool ule(const APInt &RHS) const { return compare(RHS) <= 0; }
1223
1224 /// Unsigned less or equal comparison
1225 ///
1226 /// Regards both *this as an unsigned quantity and compares it with RHS for
1227 /// the validity of the less-or-equal relationship.
1228 ///
1229 /// \returns true if *this <= RHS when considered unsigned.
1230 bool ule(uint64_t RHS) const { return !ugt(RHS); }
1231
1232 /// Signed less or equal comparison
1233 ///
1234 /// Regards both *this and RHS as signed quantities and compares them for
1235 /// validity of the less-or-equal relationship.
1236 ///
1237 /// \returns true if *this <= RHS when both are considered signed.
1238 bool sle(const APInt &RHS) const { return compareSigned(RHS) <= 0; }
1239
1240 /// Signed less or equal comparison
1241 ///
1242 /// Regards both *this as a signed quantity and compares it with RHS for the
1243 /// validity of the less-or-equal relationship.
1244 ///
1245 /// \returns true if *this <= RHS when considered signed.
1246 bool sle(uint64_t RHS) const { return !sgt(RHS); }
1247
1248 /// Unsigned greather than comparison
1249 ///
1250 /// Regards both *this and RHS as unsigned quantities and compares them for
1251 /// the validity of the greater-than relationship.
1252 ///
1253 /// \returns true if *this > RHS when both are considered unsigned.
1254 bool ugt(const APInt &RHS) const { return !ule(RHS); }
1255
1256 /// Unsigned greater than comparison
1257 ///
1258 /// Regards both *this as an unsigned quantity and compares it with RHS for
1259 /// the validity of the greater-than relationship.
1260 ///
1261 /// \returns true if *this > RHS when considered unsigned.
1262 bool ugt(uint64_t RHS) const {
1263 // Only need to check active bits if not a single word.
1264 return (!isSingleWord() && getActiveBits() > 64) || getZExtValue() > RHS;
1265 }
1266
1267 /// Signed greather than comparison
1268 ///
1269 /// Regards both *this and RHS as signed quantities and compares them for the
1270 /// validity of the greater-than relationship.
1271 ///
1272 /// \returns true if *this > RHS when both are considered signed.
1273 bool sgt(const APInt &RHS) const { return !sle(RHS); }
1274
1275 /// Signed greater than comparison
1276 ///
1277 /// Regards both *this as a signed quantity and compares it with RHS for
1278 /// the validity of the greater-than relationship.
1279 ///
1280 /// \returns true if *this > RHS when considered signed.
1281 bool sgt(int64_t RHS) const {
1282 return (!isSingleWord() && getMinSignedBits() > 64) ? !isNegative()
1283 : getSExtValue() > RHS;
1284 }
1285
1286 /// Unsigned greater or equal comparison
1287 ///
1288 /// Regards both *this and RHS as unsigned quantities and compares them for
1289 /// validity of the greater-or-equal relationship.
1290 ///
1291 /// \returns true if *this >= RHS when both are considered unsigned.
1292 bool uge(const APInt &RHS) const { return !ult(RHS); }
1293
1294 /// Unsigned greater or equal comparison
1295 ///
1296 /// Regards both *this as an unsigned quantity and compares it with RHS for
1297 /// the validity of the greater-or-equal relationship.
1298 ///
1299 /// \returns true if *this >= RHS when considered unsigned.
1300 bool uge(uint64_t RHS) const { return !ult(RHS); }
1301
1302 /// Signed greater or equal comparison
1303 ///
1304 /// Regards both *this and RHS as signed quantities and compares them for
1305 /// validity of the greater-or-equal relationship.
1306 ///
1307 /// \returns true if *this >= RHS when both are considered signed.
1308 bool sge(const APInt &RHS) const { return !slt(RHS); }
1309
1310 /// Signed greater or equal comparison
1311 ///
1312 /// Regards both *this as a signed quantity and compares it with RHS for
1313 /// the validity of the greater-or-equal relationship.
1314 ///
1315 /// \returns true if *this >= RHS when considered signed.
1316 bool sge(int64_t RHS) const { return !slt(RHS); }
1317
1318 /// This operation tests if there are any pairs of corresponding bits
1319 /// between this APInt and RHS that are both set.
1320 bool intersects(const APInt &RHS) const {
1321 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")((BitWidth == RHS.BitWidth && "Bit widths must be the same"
) ? static_cast<void> (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/APInt.h"
, 1321, __PRETTY_FUNCTION__))
;
1322 if (isSingleWord())
1323 return (U.VAL & RHS.U.VAL) != 0;
1324 return intersectsSlowCase(RHS);
1325 }
1326
1327 /// This operation checks that all bits set in this APInt are also set in RHS.
1328 bool isSubsetOf(const APInt &RHS) const {
1329 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")((BitWidth == RHS.BitWidth && "Bit widths must be the same"
) ? static_cast<void> (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/APInt.h"
, 1329, __PRETTY_FUNCTION__))
;
1330 if (isSingleWord())
1331 return (U.VAL & ~RHS.U.VAL) == 0;
1332 return isSubsetOfSlowCase(RHS);
1333 }
1334
1335 /// @}
1336 /// \name Resizing Operators
1337 /// @{
1338
1339 /// Truncate to new width.
1340 ///
1341 /// Truncate the APInt to a specified width. It is an error to specify a width
1342 /// that is greater than or equal to the current width.
1343 APInt trunc(unsigned width) const;
1344
1345 /// Sign extend to a new width.
1346 ///
1347 /// This operation sign extends the APInt to a new width. If the high order
1348 /// bit is set, the fill on the left will be done with 1 bits, otherwise zero.
1349 /// It is an error to specify a width that is less than or equal to the
1350 /// current width.
1351 APInt sext(unsigned width) const;
1352
1353 /// Zero extend to a new width.
1354 ///
1355 /// This operation zero extends the APInt to a new width. The high order bits
1356 /// are filled with 0 bits. It is an error to specify a width that is less
1357 /// than or equal to the current width.
1358 APInt zext(unsigned width) const;
1359
1360 /// Sign extend or truncate to width
1361 ///
1362 /// Make this APInt have the bit width given by \p width. The value is sign
1363 /// extended, truncated, or left alone to make it that width.
1364 APInt sextOrTrunc(unsigned width) const;
1365
1366 /// Zero extend or truncate to width
1367 ///
1368 /// Make this APInt have the bit width given by \p width. The value is zero
1369 /// extended, truncated, or left alone to make it that width.
1370 APInt zextOrTrunc(unsigned width) const;
1371
1372 /// Sign extend or truncate to width
1373 ///
1374 /// Make this APInt have the bit width given by \p width. The value is sign
1375 /// extended, or left alone to make it that width.
1376 APInt sextOrSelf(unsigned width) const;
1377
1378 /// Zero extend or truncate to width
1379 ///
1380 /// Make this APInt have the bit width given by \p width. The value is zero
1381 /// extended, or left alone to make it that width.
1382 APInt zextOrSelf(unsigned width) const;
1383
1384 /// @}
1385 /// \name Bit Manipulation Operators
1386 /// @{
1387
1388 /// Set every bit to 1.
1389 void setAllBits() {
1390 if (isSingleWord())
1391 U.VAL = WORDTYPE_MAX;
1392 else
1393 // Set all the bits in all the words.
1394 memset(U.pVal, -1, getNumWords() * APINT_WORD_SIZE);
1395 // Clear the unused ones
1396 clearUnusedBits();
1397 }
1398
1399 /// Set a given bit to 1.
1400 ///
1401 /// Set the given bit to 1 whose position is given as "bitPosition".
1402 void setBit(unsigned BitPosition) {
1403 assert(BitPosition < BitWidth && "BitPosition out of range")((BitPosition < BitWidth && "BitPosition out of range"
) ? static_cast<void> (0) : __assert_fail ("BitPosition < BitWidth && \"BitPosition out of range\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/APInt.h"
, 1403, __PRETTY_FUNCTION__))
;
1404 WordType Mask = maskBit(BitPosition);
1405 if (isSingleWord())
1406 U.VAL |= Mask;
1407 else
1408 U.pVal[whichWord(BitPosition)] |= Mask;
1409 }
1410
1411 /// Set the sign bit to 1.
1412 void setSignBit() {
1413 setBit(BitWidth - 1);
1414 }
1415
1416 /// Set the bits from loBit (inclusive) to hiBit (exclusive) to 1.
1417 void setBits(unsigned loBit, unsigned hiBit) {
1418 assert(hiBit <= BitWidth && "hiBit out of range")((hiBit <= BitWidth && "hiBit out of range") ? static_cast
<void> (0) : __assert_fail ("hiBit <= BitWidth && \"hiBit out of range\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/APInt.h"
, 1418, __PRETTY_FUNCTION__))
;
1419 assert(loBit <= BitWidth && "loBit out of range")((loBit <= BitWidth && "loBit out of range") ? static_cast
<void> (0) : __assert_fail ("loBit <= BitWidth && \"loBit out of range\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/APInt.h"
, 1419, __PRETTY_FUNCTION__))
;
1420 assert(loBit <= hiBit && "loBit greater than hiBit")((loBit <= hiBit && "loBit greater than hiBit") ? static_cast
<void> (0) : __assert_fail ("loBit <= hiBit && \"loBit greater than hiBit\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/APInt.h"
, 1420, __PRETTY_FUNCTION__))
;
1421 if (loBit == hiBit)
1422 return;
1423 if (loBit < APINT_BITS_PER_WORD && hiBit <= APINT_BITS_PER_WORD) {
1424 uint64_t mask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - (hiBit - loBit));
1425 mask <<= loBit;
1426 if (isSingleWord())
1427 U.VAL |= mask;
1428 else
1429 U.pVal[0] |= mask;
1430 } else {
1431 setBitsSlowCase(loBit, hiBit);
1432 }
1433 }
1434
1435 /// Set the top bits starting from loBit.
1436 void setBitsFrom(unsigned loBit) {
1437 return setBits(loBit, BitWidth);
1438 }
1439
1440 /// Set the bottom loBits bits.
1441 void setLowBits(unsigned loBits) {
1442 return setBits(0, loBits);
1443 }
1444
1445 /// Set the top hiBits bits.
1446 void setHighBits(unsigned hiBits) {
1447 return setBits(BitWidth - hiBits, BitWidth);
1448 }
1449
1450 /// Set every bit to 0.
1451 void clearAllBits() {
1452 if (isSingleWord())
1453 U.VAL = 0;
1454 else
1455 memset(U.pVal, 0, getNumWords() * APINT_WORD_SIZE);
1456 }
1457
1458 /// Set a given bit to 0.
1459 ///
1460 /// Set the given bit to 0 whose position is given as "bitPosition".
1461 void clearBit(unsigned BitPosition) {
1462 assert(BitPosition < BitWidth && "BitPosition out of range")((BitPosition < BitWidth && "BitPosition out of range"
) ? static_cast<void> (0) : __assert_fail ("BitPosition < BitWidth && \"BitPosition out of range\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/APInt.h"
, 1462, __PRETTY_FUNCTION__))
;
1463 WordType Mask = ~maskBit(BitPosition);
1464 if (isSingleWord())
1465 U.VAL &= Mask;
1466 else
1467 U.pVal[whichWord(BitPosition)] &= Mask;
1468 }
1469
1470 /// Set bottom loBits bits to 0.
1471 void clearLowBits(unsigned loBits) {
1472 assert(loBits <= BitWidth && "More bits than bitwidth")((loBits <= BitWidth && "More bits than bitwidth")
? static_cast<void> (0) : __assert_fail ("loBits <= BitWidth && \"More bits than bitwidth\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/APInt.h"
, 1472, __PRETTY_FUNCTION__))
;
1473 APInt Keep = getHighBitsSet(BitWidth, BitWidth - loBits);
1474 *this &= Keep;
1475 }
1476
1477 /// Set the sign bit to 0.
1478 void clearSignBit() {
1479 clearBit(BitWidth - 1);
1480 }
1481
1482 /// Toggle every bit to its opposite value.
1483 void flipAllBits() {
1484 if (isSingleWord()) {
1485 U.VAL ^= WORDTYPE_MAX;
1486 clearUnusedBits();
1487 } else {
1488 flipAllBitsSlowCase();
1489 }
1490 }
1491
1492 /// Toggles a given bit to its opposite value.
1493 ///
1494 /// Toggle a given bit to its opposite value whose position is given
1495 /// as "bitPosition".
1496 void flipBit(unsigned bitPosition);
1497
1498 /// Negate this APInt in place.
1499 void negate() {
1500 flipAllBits();
1501 ++(*this);
1502 }
1503
1504 /// Insert the bits from a smaller APInt starting at bitPosition.
1505 void insertBits(const APInt &SubBits, unsigned bitPosition);
1506 void insertBits(uint64_t SubBits, unsigned bitPosition, unsigned numBits);
1507
1508 /// Return an APInt with the extracted bits [bitPosition,bitPosition+numBits).
1509 APInt extractBits(unsigned numBits, unsigned bitPosition) const;
1510 uint64_t extractBitsAsZExtValue(unsigned numBits, unsigned bitPosition) const;
1511
1512 /// @}
1513 /// \name Value Characterization Functions
1514 /// @{
1515
1516 /// Return the number of bits in the APInt.
1517 unsigned getBitWidth() const { return BitWidth; }
1518
1519 /// Get the number of words.
1520 ///
1521 /// Here one word's bitwidth equals to that of uint64_t.
1522 ///
1523 /// \returns the number of words to hold the integer value of this APInt.
1524 unsigned getNumWords() const { return getNumWords(BitWidth); }
1525
1526 /// Get the number of words.
1527 ///
1528 /// *NOTE* Here one word's bitwidth equals to that of uint64_t.
1529 ///
1530 /// \returns the number of words to hold the integer value with a given bit
1531 /// width.
1532 static unsigned getNumWords(unsigned BitWidth) {
1533 return ((uint64_t)BitWidth + APINT_BITS_PER_WORD - 1) / APINT_BITS_PER_WORD;
1534 }
1535
1536 /// Compute the number of active bits in the value
1537 ///
1538 /// This function returns the number of active bits which is defined as the
1539 /// bit width minus the number of leading zeros. This is used in several
1540 /// computations to see how "wide" the value is.
1541 unsigned getActiveBits() const { return BitWidth - countLeadingZeros(); }
1542
1543 /// Compute the number of active words in the value of this APInt.
1544 ///
1545 /// This is used in conjunction with getActiveData to extract the raw value of
1546 /// the APInt.
1547 unsigned getActiveWords() const {
1548 unsigned numActiveBits = getActiveBits();
1549 return numActiveBits ? whichWord(numActiveBits - 1) + 1 : 1;
1550 }
1551
1552 /// Get the minimum bit size for this signed APInt
1553 ///
1554 /// Computes the minimum bit width for this APInt while considering it to be a
1555 /// signed (and probably negative) value. If the value is not negative, this
1556 /// function returns the same value as getActiveBits()+1. Otherwise, it
1557 /// returns the smallest bit width that will retain the negative value. For
1558 /// example, -1 can be written as 0b1 or 0xFFFFFFFFFF. 0b1 is shorter and so
1559 /// for -1, this function will always return 1.
1560 unsigned getMinSignedBits() const {
1561 if (isNegative())
1562 return BitWidth - countLeadingOnes() + 1;
1563 return getActiveBits() + 1;
1564 }
1565
1566 /// Get zero extended value
1567 ///
1568 /// This method attempts to return the value of this APInt as a zero extended
1569 /// uint64_t. The bitwidth must be <= 64 or the value must fit within a
1570 /// uint64_t. Otherwise an assertion will result.
1571 uint64_t getZExtValue() const {
1572 if (isSingleWord())
1573 return U.VAL;
1574 assert(getActiveBits() <= 64 && "Too many bits for uint64_t")((getActiveBits() <= 64 && "Too many bits for uint64_t"
) ? static_cast<void> (0) : __assert_fail ("getActiveBits() <= 64 && \"Too many bits for uint64_t\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/APInt.h"
, 1574, __PRETTY_FUNCTION__))
;
1575 return U.pVal[0];
1576 }
1577
1578 /// Get sign extended value
1579 ///
1580 /// This method attempts to return the value of this APInt as a sign extended
1581 /// int64_t. The bit width must be <= 64 or the value must fit within an
1582 /// int64_t. Otherwise an assertion will result.
1583 int64_t getSExtValue() const {
1584 if (isSingleWord())
1585 return SignExtend64(U.VAL, BitWidth);
1586 assert(getMinSignedBits() <= 64 && "Too many bits for int64_t")((getMinSignedBits() <= 64 && "Too many bits for int64_t"
) ? static_cast<void> (0) : __assert_fail ("getMinSignedBits() <= 64 && \"Too many bits for int64_t\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/ADT/APInt.h"
, 1586, __PRETTY_FUNCTION__))
;
1587 return int64_t(U.pVal[0]);
1588 }
1589
1590 /// Get bits required for string value.
1591 ///
1592 /// This method determines how many bits are required to hold the APInt
1593 /// equivalent of the string given by \p str.
1594 static unsigned getBitsNeeded(StringRef str, uint8_t radix);
1595
1596 /// The APInt version of the countLeadingZeros functions in
1597 /// MathExtras.h.
1598 ///
1599 /// It counts the number of zeros from the most significant bit to the first
1600 /// one bit.
1601 ///
1602 /// \returns BitWidth if the value is zero, otherwise returns the number of
1603 /// zeros from the most significant bit to the first one bits.
1604 unsigned countLeadingZeros() const {
1605 if (isSingleWord()) {
1606 unsigned unusedBits = APINT_BITS_PER_WORD - BitWidth;
1607 return llvm::countLeadingZeros(U.VAL) - unusedBits;
1608 }
1609 return countLeadingZerosSlowCase();
1610 }
1611
1612 /// Count the number of leading one bits.
1613 ///
1614 /// This function is an APInt version of the countLeadingOnes
1615 /// functions in MathExtras.h. It counts the number of ones from the most
1616 /// significant bit to the first zero bit.
1617 ///
1618 /// \returns 0 if the high order bit is not set, otherwise returns the number
1619 /// of 1 bits from the most significant to the least
1620 unsigned countLeadingOnes() const {
1621 if (isSingleWord())
1622 return llvm::countLeadingOnes(U.VAL << (APINT_BITS_PER_WORD - BitWidth));
1623 return countLeadingOnesSlowCase();
1624 }
1625
1626 /// Computes the number of leading bits of this APInt that are equal to its
1627 /// sign bit.
1628 unsigned getNumSignBits() const {
1629 return isNegative() ? countLeadingOnes() : countLeadingZeros();
1630 }
1631
1632 /// Count the number of trailing zero bits.
1633 ///
1634 /// This function is an APInt version of the countTrailingZeros
1635 /// functions in MathExtras.h. It counts the number of zeros from the least
1636 /// significant bit to the first set bit.
1637 ///
1638 /// \returns BitWidth if the value is zero, otherwise returns the number of
1639 /// zeros from the least significant bit to the first one bit.
1640 unsigned countTrailingZeros() const {
1641 if (isSingleWord())
1642 return std::min(unsigned(llvm::countTrailingZeros(U.VAL)), BitWidth);
1643 return countTrailingZerosSlowCase();
1644 }
1645
1646 /// Count the number of trailing one bits.
1647 ///
1648 /// This function is an APInt version of the countTrailingOnes
1649 /// functions in MathExtras.h. It counts the number of ones from the least
1650 /// significant bit to the first zero bit.
1651 ///
1652 /// \returns BitWidth if the value is all ones, otherwise returns the number
1653 /// of ones from the least significant bit to the first zero bit.
1654 unsigned countTrailingOnes() const {
1655 if (isSingleWord())
1656 return llvm::countTrailingOnes(U.VAL);
1657 return countTrailingOnesSlowCase();
1658 }
1659
1660 /// Count the number of bits set.
1661 ///
1662 /// This function is an APInt version of the countPopulation functions
1663 /// in MathExtras.h. It counts the number of 1 bits in the APInt value.
1664 ///
1665 /// \returns 0 if the value is zero, otherwise returns the number of set bits.
1666 unsigned countPopulation() const {
1667 if (isSingleWord())
1668 return llvm::countPopulation(U.VAL);
1669 return countPopulationSlowCase();
1670 }
1671
1672 /// @}
1673 /// \name Conversion Functions
1674 /// @{
1675 void print(raw_ostream &OS, bool isSigned) const;
1676
1677 /// Converts an APInt to a string and append it to Str. Str is commonly a
1678 /// SmallString.
1679 void toString(SmallVectorImpl<char> &Str, unsigned Radix, bool Signed,
1680 bool formatAsCLiteral = false) const;
1681
1682 /// Considers the APInt to be unsigned and converts it into a string in the
1683 /// radix given. The radix can be 2, 8, 10 16, or 36.
1684 void toStringUnsigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const {
1685 toString(Str, Radix, false, false);
1686 }
1687
1688 /// Considers the APInt to be signed and converts it into a string in the
1689 /// radix given. The radix can be 2, 8, 10, 16, or 36.
1690 void toStringSigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const {
1691 toString(Str, Radix, true, false);
1692 }
1693
1694 /// Return the APInt as a std::string.
1695 ///
1696 /// Note that this is an inefficient method. It is better to pass in a
1697 /// SmallVector/SmallString to the methods above to avoid thrashing the heap
1698 /// for the string.
1699 std::string toString(unsigned Radix, bool Signed) const;
1700
1701 /// \returns a byte-swapped representation of this APInt Value.
1702 APInt byteSwap() const;
1703
1704 /// \returns the value with the bit representation reversed of this APInt
1705 /// Value.
1706 APInt reverseBits() const;
1707
1708 /// Converts this APInt to a double value.
1709 double roundToDouble(bool isSigned) const;
1710
1711 /// Converts this unsigned APInt to a double value.
1712 double roundToDouble() const { return roundToDouble(false); }
1713
1714 /// Converts this signed APInt to a double value.
1715 double signedRoundToDouble() const { return roundToDouble(true); }
1716
1717 /// Converts APInt bits to a double
1718 ///
1719 /// The conversion does not do a translation from integer to double, it just
1720 /// re-interprets the bits as a double. Note that it is valid to do this on
1721 /// any bit width. Exactly 64 bits will be translated.
1722 double bitsToDouble() const {
1723 return BitsToDouble(getWord(0));
1724 }
1725
1726 /// Converts APInt bits to a double
1727 ///
1728 /// The conversion does not do a translation from integer to float, it just
1729 /// re-interprets the bits as a float. Note that it is valid to do this on
1730 /// any bit width. Exactly 32 bits will be translated.
1731 float bitsToFloat() const {
1732 return BitsToFloat(getWord(0));
1733 }
1734
1735 /// Converts a double to APInt bits.
1736 ///
1737 /// The conversion does not do a translation from double to integer, it just
1738 /// re-interprets the bits of the double.
1739 static APInt doubleToBits(double V) {
1740 return APInt(sizeof(double) * CHAR_BIT8, DoubleToBits(V));
1741 }
1742
1743 /// Converts a float to APInt bits.
1744 ///
1745 /// The conversion does not do a translation from float to integer, it just
1746 /// re-interprets the bits of the float.
1747 static APInt floatToBits(float V) {
1748 return APInt(sizeof(float) * CHAR_BIT8, FloatToBits(V));
1749 }
1750
1751 /// @}
1752 /// \name Mathematics Operations
1753 /// @{
1754
1755 /// \returns the floor log base 2 of this APInt.
1756 unsigned logBase2() const { return getActiveBits() - 1; }
1757
1758 /// \returns the ceil log base 2 of this APInt.
1759 unsigned ceilLogBase2() const {
1760 APInt temp(*this);
1761 --temp;
1762 return temp.getActiveBits();
1763 }
1764
1765 /// \returns the nearest log base 2 of this APInt. Ties round up.
1766 ///
1767 /// NOTE: When we have a BitWidth of 1, we define:
1768 ///
1769 /// log2(0) = UINT32_MAX
1770 /// log2(1) = 0
1771 ///
1772 /// to get around any mathematical concerns resulting from
1773 /// referencing 2 in a space where 2 does no exist.
1774 unsigned nearestLogBase2() const {
1775 // Special case when we have a bitwidth of 1. If VAL is 1, then we
1776 // get 0. If VAL is 0, we get WORDTYPE_MAX which gets truncated to
1777 // UINT32_MAX.
1778 if (BitWidth == 1)
1779 return U.VAL - 1;
1780
1781 // Handle the zero case.
1782 if (isNullValue())
1783 return UINT32_MAX(4294967295U);
1784
1785 // The non-zero case is handled by computing:
1786 //
1787 // nearestLogBase2(x) = logBase2(x) + x[logBase2(x)-1].
1788 //
1789 // where x[i] is referring to the value of the ith bit of x.
1790 unsigned lg = logBase2();
1791 return lg + unsigned((*this)[lg - 1]);
1792 }
1793
1794 /// \returns the log base 2 of this APInt if its an exact power of two, -1
1795 /// otherwise
1796 int32_t exactLogBase2() const {
1797 if (!isPowerOf2())
1798 return -1;
1799 return logBase2();
1800 }
1801
1802 /// Compute the square root
1803 APInt sqrt() const;
1804
1805 /// Get the absolute value;
1806 ///
1807 /// If *this is < 0 then return -(*this), otherwise *this;
1808 APInt abs() const {
1809 if (isNegative())
1810 return -(*this);
1811 return *this;
1812 }
1813
1814 /// \returns the multiplicative inverse for a given modulo.
1815 APInt multiplicativeInverse(const APInt &modulo) const;
1816
1817 /// @}
1818 /// \name Support for division by constant
1819 /// @{
1820
1821 /// Calculate the magic number for signed division by a constant.
1822 struct ms;
1823 ms magic() const;
1824
1825 /// Calculate the magic number for unsigned division by a constant.
1826 struct mu;
1827 mu magicu(unsigned LeadingZeros = 0) const;
1828
1829 /// @}
1830 /// \name Building-block Operations for APInt and APFloat
1831 /// @{
1832
1833 // These building block operations operate on a representation of arbitrary
1834 // precision, two's-complement, bignum integer values. They should be
1835 // sufficient to implement APInt and APFloat bignum requirements. Inputs are
1836 // generally a pointer to the base of an array of integer parts, representing
1837 // an unsigned bignum, and a count of how many parts there are.
1838
1839 /// Sets the least significant part of a bignum to the input value, and zeroes
1840 /// out higher parts.
1841 static void tcSet(WordType *, WordType, unsigned);
1842
1843 /// Assign one bignum to another.
1844 static void tcAssign(WordType *, const WordType *, unsigned);
1845
1846 /// Returns true if a bignum is zero, false otherwise.
1847 static bool tcIsZero(const WordType *, unsigned);
1848
1849 /// Extract the given bit of a bignum; returns 0 or 1. Zero-based.
1850 static int tcExtractBit(const WordType *, unsigned bit);
1851
1852 /// Copy the bit vector of width srcBITS from SRC, starting at bit srcLSB, to
1853 /// DST, of dstCOUNT parts, such that the bit srcLSB becomes the least
1854 /// significant bit of DST. All high bits above srcBITS in DST are
1855 /// zero-filled.
1856 static void tcExtract(WordType *, unsigned dstCount,
1857 const WordType *, unsigned srcBits,
1858 unsigned srcLSB);
1859
1860 /// Set the given bit of a bignum. Zero-based.
1861 static void tcSetBit(WordType *, unsigned bit);
1862
1863 /// Clear the given bit of a bignum. Zero-based.
1864 static void tcClearBit(WordType *, unsigned bit);
1865
1866 /// Returns the bit number of the least or most significant set bit of a
1867 /// number. If the input number has no bits set -1U is returned.
1868 static unsigned tcLSB(const WordType *, unsigned n);
1869 static unsigned tcMSB(const WordType *parts, unsigned n);
1870
1871 /// Negate a bignum in-place.
1872 static void tcNegate(WordType *, unsigned);
1873
1874 /// DST += RHS + CARRY where CARRY is zero or one. Returns the carry flag.
1875 static WordType tcAdd(WordType *, const WordType *,
1876 WordType carry, unsigned);
1877 /// DST += RHS. Returns the carry flag.
1878 static WordType tcAddPart(WordType *, WordType, unsigned);
1879
1880 /// DST -= RHS + CARRY where CARRY is zero or one. Returns the carry flag.
1881 static WordType tcSubtract(WordType *, const WordType *,
1882 WordType carry, unsigned);
1883 /// DST -= RHS. Returns the carry flag.
1884 static WordType tcSubtractPart(WordType *, WordType, unsigned);
1885
1886 /// DST += SRC * MULTIPLIER + PART if add is true
1887 /// DST = SRC * MULTIPLIER + PART if add is false
1888 ///
1889 /// Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC they must
1890 /// start at the same point, i.e. DST == SRC.
1891 ///
1892 /// If DSTPARTS == SRC_PARTS + 1 no overflow occurs and zero is returned.
1893 /// Otherwise DST is filled with the least significant DSTPARTS parts of the
1894 /// result, and if all of the omitted higher parts were zero return zero,
1895 /// otherwise overflow occurred and return one.
1896 static int tcMultiplyPart(WordType *dst, const WordType *src,
1897 WordType multiplier, WordType carry,
1898 unsigned srcParts, unsigned dstParts,
1899 bool add);
1900
1901 /// DST = LHS * RHS, where DST has the same width as the operands and is
1902 /// filled with the least significant parts of the result. Returns one if
1903 /// overflow occurred, otherwise zero. DST must be disjoint from both
1904 /// operands.
1905 static int tcMultiply(WordType *, const WordType *, const WordType *,
1906 unsigned);
1907
1908 /// DST = LHS * RHS, where DST has width the sum of the widths of the
1909 /// operands. No overflow occurs. DST must be disjoint from both operands.
1910 static void tcFullMultiply(WordType *, const WordType *,
1911 const WordType *, unsigned, unsigned);
1912
1913 /// If RHS is zero LHS and REMAINDER are left unchanged, return one.
1914 /// Otherwise set LHS to LHS / RHS with the fractional part discarded, set
1915 /// REMAINDER to the remainder, return zero. i.e.
1916 ///
1917 /// OLD_LHS = RHS * LHS + REMAINDER
1918 ///
1919 /// SCRATCH is a bignum of the same size as the operands and result for use by
1920 /// the routine; its contents need not be initialized and are destroyed. LHS,
1921 /// REMAINDER and SCRATCH must be distinct.
1922 static int tcDivide(WordType *lhs, const WordType *rhs,
1923 WordType *remainder, WordType *scratch,
1924 unsigned parts);
1925
1926 /// Shift a bignum left Count bits. Shifted in bits are zero. There are no
1927 /// restrictions on Count.
1928 static void tcShiftLeft(WordType *, unsigned Words, unsigned Count);
1929
1930 /// Shift a bignum right Count bits. Shifted in bits are zero. There are no
1931 /// restrictions on Count.
1932 static void tcShiftRight(WordType *, unsigned Words, unsigned Count);
1933
1934 /// The obvious AND, OR and XOR and complement operations.
1935 static void tcAnd(WordType *, const WordType *, unsigned);
1936 static void tcOr(WordType *, const WordType *, unsigned);
1937 static void tcXor(WordType *, const WordType *, unsigned);
1938 static void tcComplement(WordType *, unsigned);
1939
1940 /// Comparison (unsigned) of two bignums.
1941 static int tcCompare(const WordType *, const WordType *, unsigned);
1942
1943 /// Increment a bignum in-place. Return the carry flag.
1944 static WordType tcIncrement(WordType *dst, unsigned parts) {
1945 return tcAddPart(dst, 1, parts);
1946 }
1947
1948 /// Decrement a bignum in-place. Return the borrow flag.
1949 static WordType tcDecrement(WordType *dst, unsigned parts) {
1950 return tcSubtractPart(dst, 1, parts);
1951 }
1952
1953 /// Set the least significant BITS and clear the rest.
1954 static void tcSetLeastSignificantBits(WordType *, unsigned, unsigned bits);
1955
1956 /// debug method
1957 void dump() const;
1958
1959 /// @}
1960};
1961
1962/// Magic data for optimising signed division by a constant.
1963struct APInt::ms {
1964 APInt m; ///< magic number
1965 unsigned s; ///< shift amount
1966};
1967
1968/// Magic data for optimising unsigned division by a constant.
1969struct APInt::mu {
1970 APInt m; ///< magic number
1971 bool a; ///< add indicator
1972 unsigned s; ///< shift amount
1973};
1974
1975inline bool operator==(uint64_t V1, const APInt &V2) { return V2 == V1; }
1976
1977inline bool operator!=(uint64_t V1, const APInt &V2) { return V2 != V1; }
1978
1979/// Unary bitwise complement operator.
1980///
1981/// \returns an APInt that is the bitwise complement of \p v.
1982inline APInt operator~(APInt v) {
1983 v.flipAllBits();
1984 return v;
1985}
1986
1987inline APInt operator&(APInt a, const APInt &b) {
1988 a &= b;
1989 return a;
1990}
1991
1992inline APInt operator&(const APInt &a, APInt &&b) {
1993 b &= a;
1994 return std::move(b);
1995}
1996
1997inline APInt operator&(APInt a, uint64_t RHS) {
1998 a &= RHS;
1999 return a;
2000}
2001
2002inline APInt operator&(uint64_t LHS, APInt b) {
2003 b &= LHS;
2004 return b;
2005}
2006
2007inline APInt operator|(APInt a, const APInt &b) {
2008 a |= b;
2009 return a;
2010}
2011
2012inline APInt operator|(const APInt &a, APInt &&b) {
2013 b |= a;
2014 return std::move(b);
2015}
2016
2017inline APInt operator|(APInt a, uint64_t RHS) {
2018 a |= RHS;
2019 return a;
2020}
2021
2022inline APInt operator|(uint64_t LHS, APInt b) {
2023 b |= LHS;
2024 return b;
2025}
2026
2027inline APInt operator^(APInt a, const APInt &b) {
2028 a ^= b;
2029 return a;
2030}
2031
2032inline APInt operator^(const APInt &a, APInt &&b) {
2033 b ^= a;
2034 return std::move(b);
2035}
2036
2037inline APInt operator^(APInt a, uint64_t RHS) {
2038 a ^= RHS;
2039 return a;
2040}
2041
2042inline APInt operator^(uint64_t LHS, APInt b) {
2043 b ^= LHS;
2044 return b;
2045}
2046
2047inline raw_ostream &operator<<(raw_ostream &OS, const APInt &I) {
2048 I.print(OS, true);
2049 return OS;
2050}
2051
2052inline APInt operator-(APInt v) {
2053 v.negate();
2054 return v;
2055}
2056
2057inline APInt operator+(APInt a, const APInt &b) {
2058 a += b;
2059 return a;
2060}
2061
2062inline APInt operator+(const APInt &a, APInt &&b) {
2063 b += a;
2064 return std::move(b);
2065}
2066
2067inline APInt operator+(APInt a, uint64_t RHS) {
2068 a += RHS;
2069 return a;
2070}
2071
2072inline APInt operator+(uint64_t LHS, APInt b) {
2073 b += LHS;
2074 return b;
2075}
2076
2077inline APInt operator-(APInt a, const APInt &b) {
2078 a -= b;
2079 return a;
2080}
2081
2082inline APInt operator-(const APInt &a, APInt &&b) {
2083 b.negate();
2084 b += a;
2085 return std::move(b);
2086}
2087
2088inline APInt operator-(APInt a, uint64_t RHS) {
2089 a -= RHS;
2090 return a;
2091}
2092
2093inline APInt operator-(uint64_t LHS, APInt b) {
2094 b.negate();
2095 b += LHS;
2096 return b;
2097}
2098
2099inline APInt operator*(APInt a, uint64_t RHS) {
2100 a *= RHS;
2101 return a;
2102}
2103
2104inline APInt operator*(uint64_t LHS, APInt b) {
2105 b *= LHS;
2106 return b;
2107}
2108
2109
2110namespace APIntOps {
2111
2112/// Determine the smaller of two APInts considered to be signed.
2113inline const APInt &smin(const APInt &A, const APInt &B) {
2114 return A.slt(B) ? A : B;
2115}
2116
2117/// Determine the larger of two APInts considered to be signed.
2118inline const APInt &smax(const APInt &A, const APInt &B) {
2119 return A.sgt(B) ? A : B;
2120}
2121
2122/// Determine the smaller of two APInts considered to be signed.
2123inline const APInt &umin(const APInt &A, const APInt &B) {
2124 return A.ult(B) ? A : B;
2125}
2126
2127/// Determine the larger of two APInts considered to be unsigned.
2128inline const APInt &umax(const APInt &A, const APInt &B) {
2129 return A.ugt(B) ? A : B;
2130}
2131
2132/// Compute GCD of two unsigned APInt values.
2133///
2134/// This function returns the greatest common divisor of the two APInt values
2135/// using Stein's algorithm.
2136///
2137/// \returns the greatest common divisor of A and B.
2138APInt GreatestCommonDivisor(APInt A, APInt B);
2139
2140/// Converts the given APInt to a double value.
2141///
2142/// Treats the APInt as an unsigned value for conversion purposes.
2143inline double RoundAPIntToDouble(const APInt &APIVal) {
2144 return APIVal.roundToDouble();
2145}
2146
2147/// Converts the given APInt to a double value.
2148///
2149/// Treats the APInt as a signed value for conversion purposes.
2150inline double RoundSignedAPIntToDouble(const APInt &APIVal) {
2151 return APIVal.signedRoundToDouble();
2152}
2153
2154/// Converts the given APInt to a float vlalue.
2155inline float RoundAPIntToFloat(const APInt &APIVal) {
2156 return float(RoundAPIntToDouble(APIVal));
2157}
2158
2159/// Converts the given APInt to a float value.
2160///
2161/// Treast the APInt as a signed value for conversion purposes.
2162inline float RoundSignedAPIntToFloat(const APInt &APIVal) {
2163 return float(APIVal.signedRoundToDouble());
2164}
2165
2166/// Converts the given double value into a APInt.
2167///
2168/// This function convert a double value to an APInt value.
2169APInt RoundDoubleToAPInt(double Double, unsigned width);
2170
2171/// Converts a float value into a APInt.
2172///
2173/// Converts a float value into an APInt value.
2174inline APInt RoundFloatToAPInt(float Float, unsigned width) {
2175 return RoundDoubleToAPInt(double(Float), width);
2176}
2177
2178/// Return A unsign-divided by B, rounded by the given rounding mode.
2179APInt RoundingUDiv(const APInt &A, const APInt &B, APInt::Rounding RM);
2180
2181/// Return A sign-divided by B, rounded by the given rounding mode.
2182APInt RoundingSDiv(const APInt &A, const APInt &B, APInt::Rounding RM);
2183
2184/// Let q(n) = An^2 + Bn + C, and BW = bit width of the value range
2185/// (e.g. 32 for i32).
2186/// This function finds the smallest number n, such that
2187/// (a) n >= 0 and q(n) = 0, or
2188/// (b) n >= 1 and q(n-1) and q(n), when evaluated in the set of all
2189/// integers, belong to two different intervals [Rk, Rk+R),
2190/// where R = 2^BW, and k is an integer.
2191/// The idea here is to find when q(n) "overflows" 2^BW, while at the
2192/// same time "allowing" subtraction. In unsigned modulo arithmetic a
2193/// subtraction (treated as addition of negated numbers) would always
2194/// count as an overflow, but here we want to allow values to decrease
2195/// and increase as long as they are within the same interval.
2196/// Specifically, adding of two negative numbers should not cause an
2197/// overflow (as long as the magnitude does not exceed the bith width).
2198/// On the other hand, given a positive number, adding a negative
2199/// number to it can give a negative result, which would cause the
2200/// value to go from [-2^BW, 0) to [0, 2^BW). In that sense, zero is
2201/// treated as a special case of an overflow.
2202///
2203/// This function returns None if after finding k that minimizes the
2204/// positive solution to q(n) = kR, both solutions are contained between
2205/// two consecutive integers.
2206///
2207/// There are cases where q(n) > T, and q(n+1) < T (assuming evaluation
2208/// in arithmetic modulo 2^BW, and treating the values as signed) by the
2209/// virtue of *signed* overflow. This function will *not* find such an n,
2210/// however it may find a value of n satisfying the inequalities due to
2211/// an *unsigned* overflow (if the values are treated as unsigned).
2212/// To find a solution for a signed overflow, treat it as a problem of
2213/// finding an unsigned overflow with a range with of BW-1.
2214///
2215/// The returned value may have a different bit width from the input
2216/// coefficients.
2217Optional<APInt> SolveQuadraticEquationWrap(APInt A, APInt B, APInt C,
2218 unsigned RangeWidth);
2219} // End of APIntOps namespace
2220
2221// See friend declaration above. This additional declaration is required in
2222// order to compile LLVM with IBM xlC compiler.
2223hash_code hash_value(const APInt &Arg);
2224
2225/// StoreIntToMemory - Fills the StoreBytes bytes of memory starting from Dst
2226/// with the integer held in IntVal.
2227void StoreIntToMemory(const APInt &IntVal, uint8_t *Dst, unsigned StoreBytes);
2228
2229/// LoadIntFromMemory - Loads the integer stored in the LoadBytes bytes starting
2230/// from Src into IntVal, which is assumed to be wide enough and to hold zero.
2231void LoadIntFromMemory(APInt &IntVal, uint8_t *Src, unsigned LoadBytes);
2232
2233} // namespace llvm
2234
2235#endif