Bug Summary

File:lib/Support/APInt.cpp
Warning:line 88, 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 -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-9/lib/clang/9.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/lib/Support -I /build/llvm-toolchain-snapshot-9~svn362543/lib/Support -I /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/include -I /build/llvm-toolchain-snapshot-9~svn362543/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/include/clang/9.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-9/lib/clang/9.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/lib/Support -fdebug-prefix-map=/build/llvm-toolchain-snapshot-9~svn362543=. -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -stack-protector 2 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2019-06-05-060531-1271-1 -x c++ /build/llvm-toolchain-snapshot-9~svn362543/lib/Support/APInt.cpp -faddrsig

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

/build/llvm-toolchain-snapshot-9~svn362543/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-9~svn362543/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())
3
Taking false branch
29
Taking false branch
323 U.VAL = that.U.VAL;
324 else
325 initSlowCase(that);
4
Calling 'APInt::initSlowCase'
8
Returned allocated memory
30
Calling 'APInt::initSlowCase'
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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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);
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-9~svn362543/include/llvm/ADT/APInt.h"
, 753, __PRETTY_FUNCTION__))
;
13
'?' condition is true
754 if (!isSingleWord())
14
Taking true branch
755 delete[] U.pVal;
15
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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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 the sign bit to 0.
1471 void clearSignBit() {
1472 clearBit(BitWidth - 1);
1473 }
1474
1475 /// Toggle every bit to its opposite value.
1476 void flipAllBits() {
1477 if (isSingleWord()) {
1478 U.VAL ^= WORDTYPE_MAX;
1479 clearUnusedBits();
1480 } else {
1481 flipAllBitsSlowCase();
1482 }
1483 }
1484
1485 /// Toggles a given bit to its opposite value.
1486 ///
1487 /// Toggle a given bit to its opposite value whose position is given
1488 /// as "bitPosition".
1489 void flipBit(unsigned bitPosition);
1490
1491 /// Negate this APInt in place.
1492 void negate() {
1493 flipAllBits();
1494 ++(*this);
1495 }
1496
1497 /// Insert the bits from a smaller APInt starting at bitPosition.
1498 void insertBits(const APInt &SubBits, unsigned bitPosition);
1499
1500 /// Return an APInt with the extracted bits [bitPosition,bitPosition+numBits).
1501 APInt extractBits(unsigned numBits, unsigned bitPosition) const;
1502
1503 /// @}
1504 /// \name Value Characterization Functions
1505 /// @{
1506
1507 /// Return the number of bits in the APInt.
1508 unsigned getBitWidth() const { return BitWidth; }
1509
1510 /// Get the number of words.
1511 ///
1512 /// Here one word's bitwidth equals to that of uint64_t.
1513 ///
1514 /// \returns the number of words to hold the integer value of this APInt.
1515 unsigned getNumWords() const { return getNumWords(BitWidth); }
1516
1517 /// Get the number of words.
1518 ///
1519 /// *NOTE* Here one word's bitwidth equals to that of uint64_t.
1520 ///
1521 /// \returns the number of words to hold the integer value with a given bit
1522 /// width.
1523 static unsigned getNumWords(unsigned BitWidth) {
1524 return ((uint64_t)BitWidth + APINT_BITS_PER_WORD - 1) / APINT_BITS_PER_WORD;
1525 }
1526
1527 /// Compute the number of active bits in the value
1528 ///
1529 /// This function returns the number of active bits which is defined as the
1530 /// bit width minus the number of leading zeros. This is used in several
1531 /// computations to see how "wide" the value is.
1532 unsigned getActiveBits() const { return BitWidth - countLeadingZeros(); }
1533
1534 /// Compute the number of active words in the value of this APInt.
1535 ///
1536 /// This is used in conjunction with getActiveData to extract the raw value of
1537 /// the APInt.
1538 unsigned getActiveWords() const {
1539 unsigned numActiveBits = getActiveBits();
1540 return numActiveBits ? whichWord(numActiveBits - 1) + 1 : 1;
1541 }
1542
1543 /// Get the minimum bit size for this signed APInt
1544 ///
1545 /// Computes the minimum bit width for this APInt while considering it to be a
1546 /// signed (and probably negative) value. If the value is not negative, this
1547 /// function returns the same value as getActiveBits()+1. Otherwise, it
1548 /// returns the smallest bit width that will retain the negative value. For
1549 /// example, -1 can be written as 0b1 or 0xFFFFFFFFFF. 0b1 is shorter and so
1550 /// for -1, this function will always return 1.
1551 unsigned getMinSignedBits() const {
1552 if (isNegative())
1553 return BitWidth - countLeadingOnes() + 1;
1554 return getActiveBits() + 1;
1555 }
1556
1557 /// Get zero extended value
1558 ///
1559 /// This method attempts to return the value of this APInt as a zero extended
1560 /// uint64_t. The bitwidth must be <= 64 or the value must fit within a
1561 /// uint64_t. Otherwise an assertion will result.
1562 uint64_t getZExtValue() const {
1563 if (isSingleWord())
1564 return U.VAL;
1565 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-9~svn362543/include/llvm/ADT/APInt.h"
, 1565, __PRETTY_FUNCTION__))
;
1566 return U.pVal[0];
1567 }
1568
1569 /// Get sign extended value
1570 ///
1571 /// This method attempts to return the value of this APInt as a sign extended
1572 /// int64_t. The bit width must be <= 64 or the value must fit within an
1573 /// int64_t. Otherwise an assertion will result.
1574 int64_t getSExtValue() const {
1575 if (isSingleWord())
1576 return SignExtend64(U.VAL, BitWidth);
1577 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-9~svn362543/include/llvm/ADT/APInt.h"
, 1577, __PRETTY_FUNCTION__))
;
1578 return int64_t(U.pVal[0]);
1579 }
1580
1581 /// Get bits required for string value.
1582 ///
1583 /// This method determines how many bits are required to hold the APInt
1584 /// equivalent of the string given by \p str.
1585 static unsigned getBitsNeeded(StringRef str, uint8_t radix);
1586
1587 /// The APInt version of the countLeadingZeros functions in
1588 /// MathExtras.h.
1589 ///
1590 /// It counts the number of zeros from the most significant bit to the first
1591 /// one bit.
1592 ///
1593 /// \returns BitWidth if the value is zero, otherwise returns the number of
1594 /// zeros from the most significant bit to the first one bits.
1595 unsigned countLeadingZeros() const {
1596 if (isSingleWord()) {
1597 unsigned unusedBits = APINT_BITS_PER_WORD - BitWidth;
1598 return llvm::countLeadingZeros(U.VAL) - unusedBits;
1599 }
1600 return countLeadingZerosSlowCase();
1601 }
1602
1603 /// Count the number of leading one bits.
1604 ///
1605 /// This function is an APInt version of the countLeadingOnes
1606 /// functions in MathExtras.h. It counts the number of ones from the most
1607 /// significant bit to the first zero bit.
1608 ///
1609 /// \returns 0 if the high order bit is not set, otherwise returns the number
1610 /// of 1 bits from the most significant to the least
1611 unsigned countLeadingOnes() const {
1612 if (isSingleWord())
1613 return llvm::countLeadingOnes(U.VAL << (APINT_BITS_PER_WORD - BitWidth));
1614 return countLeadingOnesSlowCase();
1615 }
1616
1617 /// Computes the number of leading bits of this APInt that are equal to its
1618 /// sign bit.
1619 unsigned getNumSignBits() const {
1620 return isNegative() ? countLeadingOnes() : countLeadingZeros();
1621 }
1622
1623 /// Count the number of trailing zero bits.
1624 ///
1625 /// This function is an APInt version of the countTrailingZeros
1626 /// functions in MathExtras.h. It counts the number of zeros from the least
1627 /// significant bit to the first set bit.
1628 ///
1629 /// \returns BitWidth if the value is zero, otherwise returns the number of
1630 /// zeros from the least significant bit to the first one bit.
1631 unsigned countTrailingZeros() const {
1632 if (isSingleWord())
1633 return std::min(unsigned(llvm::countTrailingZeros(U.VAL)), BitWidth);
1634 return countTrailingZerosSlowCase();
1635 }
1636
1637 /// Count the number of trailing one bits.
1638 ///
1639 /// This function is an APInt version of the countTrailingOnes
1640 /// functions in MathExtras.h. It counts the number of ones from the least
1641 /// significant bit to the first zero bit.
1642 ///
1643 /// \returns BitWidth if the value is all ones, otherwise returns the number
1644 /// of ones from the least significant bit to the first zero bit.
1645 unsigned countTrailingOnes() const {
1646 if (isSingleWord())
1647 return llvm::countTrailingOnes(U.VAL);
1648 return countTrailingOnesSlowCase();
1649 }
1650
1651 /// Count the number of bits set.
1652 ///
1653 /// This function is an APInt version of the countPopulation functions
1654 /// in MathExtras.h. It counts the number of 1 bits in the APInt value.
1655 ///
1656 /// \returns 0 if the value is zero, otherwise returns the number of set bits.
1657 unsigned countPopulation() const {
1658 if (isSingleWord())
1659 return llvm::countPopulation(U.VAL);
1660 return countPopulationSlowCase();
1661 }
1662
1663 /// @}
1664 /// \name Conversion Functions
1665 /// @{
1666 void print(raw_ostream &OS, bool isSigned) const;
1667
1668 /// Converts an APInt to a string and append it to Str. Str is commonly a
1669 /// SmallString.
1670 void toString(SmallVectorImpl<char> &Str, unsigned Radix, bool Signed,
1671 bool formatAsCLiteral = false) const;
1672
1673 /// Considers the APInt to be unsigned and converts it into a string in the
1674 /// radix given. The radix can be 2, 8, 10 16, or 36.
1675 void toStringUnsigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const {
1676 toString(Str, Radix, false, false);
1677 }
1678
1679 /// Considers the APInt to be signed and converts it into a string in the
1680 /// radix given. The radix can be 2, 8, 10, 16, or 36.
1681 void toStringSigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const {
1682 toString(Str, Radix, true, false);
1683 }
1684
1685 /// Return the APInt as a std::string.
1686 ///
1687 /// Note that this is an inefficient method. It is better to pass in a
1688 /// SmallVector/SmallString to the methods above to avoid thrashing the heap
1689 /// for the string.
1690 std::string toString(unsigned Radix, bool Signed) const;
1691
1692 /// \returns a byte-swapped representation of this APInt Value.
1693 APInt byteSwap() const;
1694
1695 /// \returns the value with the bit representation reversed of this APInt
1696 /// Value.
1697 APInt reverseBits() const;
1698
1699 /// Converts this APInt to a double value.
1700 double roundToDouble(bool isSigned) const;
1701
1702 /// Converts this unsigned APInt to a double value.
1703 double roundToDouble() const { return roundToDouble(false); }
1704
1705 /// Converts this signed APInt to a double value.
1706 double signedRoundToDouble() const { return roundToDouble(true); }
1707
1708 /// Converts APInt bits to a double
1709 ///
1710 /// The conversion does not do a translation from integer to double, it just
1711 /// re-interprets the bits as a double. Note that it is valid to do this on
1712 /// any bit width. Exactly 64 bits will be translated.
1713 double bitsToDouble() const {
1714 return BitsToDouble(getWord(0));
1715 }
1716
1717 /// Converts APInt bits to a double
1718 ///
1719 /// The conversion does not do a translation from integer to float, it just
1720 /// re-interprets the bits as a float. Note that it is valid to do this on
1721 /// any bit width. Exactly 32 bits will be translated.
1722 float bitsToFloat() const {
1723 return BitsToFloat(getWord(0));
1724 }
1725
1726 /// Converts a double to APInt bits.
1727 ///
1728 /// The conversion does not do a translation from double to integer, it just
1729 /// re-interprets the bits of the double.
1730 static APInt doubleToBits(double V) {
1731 return APInt(sizeof(double) * CHAR_BIT8, DoubleToBits(V));
1732 }
1733
1734 /// Converts a float to APInt bits.
1735 ///
1736 /// The conversion does not do a translation from float to integer, it just
1737 /// re-interprets the bits of the float.
1738 static APInt floatToBits(float V) {
1739 return APInt(sizeof(float) * CHAR_BIT8, FloatToBits(V));
1740 }
1741
1742 /// @}
1743 /// \name Mathematics Operations
1744 /// @{
1745
1746 /// \returns the floor log base 2 of this APInt.
1747 unsigned logBase2() const { return getActiveBits() - 1; }
1748
1749 /// \returns the ceil log base 2 of this APInt.
1750 unsigned ceilLogBase2() const {
1751 APInt temp(*this);
1752 --temp;
1753 return temp.getActiveBits();
1754 }
1755
1756 /// \returns the nearest log base 2 of this APInt. Ties round up.
1757 ///
1758 /// NOTE: When we have a BitWidth of 1, we define:
1759 ///
1760 /// log2(0) = UINT32_MAX
1761 /// log2(1) = 0
1762 ///
1763 /// to get around any mathematical concerns resulting from
1764 /// referencing 2 in a space where 2 does no exist.
1765 unsigned nearestLogBase2() const {
1766 // Special case when we have a bitwidth of 1. If VAL is 1, then we
1767 // get 0. If VAL is 0, we get WORDTYPE_MAX which gets truncated to
1768 // UINT32_MAX.
1769 if (BitWidth == 1)
1770 return U.VAL - 1;
1771
1772 // Handle the zero case.
1773 if (isNullValue())
1774 return UINT32_MAX(4294967295U);
1775
1776 // The non-zero case is handled by computing:
1777 //
1778 // nearestLogBase2(x) = logBase2(x) + x[logBase2(x)-1].
1779 //
1780 // where x[i] is referring to the value of the ith bit of x.
1781 unsigned lg = logBase2();
1782 return lg + unsigned((*this)[lg - 1]);
1783 }
1784
1785 /// \returns the log base 2 of this APInt if its an exact power of two, -1
1786 /// otherwise
1787 int32_t exactLogBase2() const {
1788 if (!isPowerOf2())
1789 return -1;
1790 return logBase2();
1791 }
1792
1793 /// Compute the square root
1794 APInt sqrt() const;
1795
1796 /// Get the absolute value;
1797 ///
1798 /// If *this is < 0 then return -(*this), otherwise *this;
1799 APInt abs() const {
1800 if (isNegative())
1801 return -(*this);
1802 return *this;
1803 }
1804
1805 /// \returns the multiplicative inverse for a given modulo.
1806 APInt multiplicativeInverse(const APInt &modulo) const;
1807
1808 /// @}
1809 /// \name Support for division by constant
1810 /// @{
1811
1812 /// Calculate the magic number for signed division by a constant.
1813 struct ms;
1814 ms magic() const;
1815
1816 /// Calculate the magic number for unsigned division by a constant.
1817 struct mu;
1818 mu magicu(unsigned LeadingZeros = 0) const;
1819
1820 /// @}
1821 /// \name Building-block Operations for APInt and APFloat
1822 /// @{
1823
1824 // These building block operations operate on a representation of arbitrary
1825 // precision, two's-complement, bignum integer values. They should be
1826 // sufficient to implement APInt and APFloat bignum requirements. Inputs are
1827 // generally a pointer to the base of an array of integer parts, representing
1828 // an unsigned bignum, and a count of how many parts there are.
1829
1830 /// Sets the least significant part of a bignum to the input value, and zeroes
1831 /// out higher parts.
1832 static void tcSet(WordType *, WordType, unsigned);
1833
1834 /// Assign one bignum to another.
1835 static void tcAssign(WordType *, const WordType *, unsigned);
1836
1837 /// Returns true if a bignum is zero, false otherwise.
1838 static bool tcIsZero(const WordType *, unsigned);
1839
1840 /// Extract the given bit of a bignum; returns 0 or 1. Zero-based.
1841 static int tcExtractBit(const WordType *, unsigned bit);
1842
1843 /// Copy the bit vector of width srcBITS from SRC, starting at bit srcLSB, to
1844 /// DST, of dstCOUNT parts, such that the bit srcLSB becomes the least
1845 /// significant bit of DST. All high bits above srcBITS in DST are
1846 /// zero-filled.
1847 static void tcExtract(WordType *, unsigned dstCount,
1848 const WordType *, unsigned srcBits,
1849 unsigned srcLSB);
1850
1851 /// Set the given bit of a bignum. Zero-based.
1852 static void tcSetBit(WordType *, unsigned bit);
1853
1854 /// Clear the given bit of a bignum. Zero-based.
1855 static void tcClearBit(WordType *, unsigned bit);
1856
1857 /// Returns the bit number of the least or most significant set bit of a
1858 /// number. If the input number has no bits set -1U is returned.
1859 static unsigned tcLSB(const WordType *, unsigned n);
1860 static unsigned tcMSB(const WordType *parts, unsigned n);
1861
1862 /// Negate a bignum in-place.
1863 static void tcNegate(WordType *, unsigned);
1864
1865 /// DST += RHS + CARRY where CARRY is zero or one. Returns the carry flag.
1866 static WordType tcAdd(WordType *, const WordType *,
1867 WordType carry, unsigned);
1868 /// DST += RHS. Returns the carry flag.
1869 static WordType tcAddPart(WordType *, WordType, unsigned);
1870
1871 /// DST -= RHS + CARRY where CARRY is zero or one. Returns the carry flag.
1872 static WordType tcSubtract(WordType *, const WordType *,
1873 WordType carry, unsigned);
1874 /// DST -= RHS. Returns the carry flag.
1875 static WordType tcSubtractPart(WordType *, WordType, unsigned);
1876
1877 /// DST += SRC * MULTIPLIER + PART if add is true
1878 /// DST = SRC * MULTIPLIER + PART if add is false
1879 ///
1880 /// Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC they must
1881 /// start at the same point, i.e. DST == SRC.
1882 ///
1883 /// If DSTPARTS == SRC_PARTS + 1 no overflow occurs and zero is returned.
1884 /// Otherwise DST is filled with the least significant DSTPARTS parts of the
1885 /// result, and if all of the omitted higher parts were zero return zero,
1886 /// otherwise overflow occurred and return one.
1887 static int tcMultiplyPart(WordType *dst, const WordType *src,
1888 WordType multiplier, WordType carry,
1889 unsigned srcParts, unsigned dstParts,
1890 bool add);
1891
1892 /// DST = LHS * RHS, where DST has the same width as the operands and is
1893 /// filled with the least significant parts of the result. Returns one if
1894 /// overflow occurred, otherwise zero. DST must be disjoint from both
1895 /// operands.
1896 static int tcMultiply(WordType *, const WordType *, const WordType *,
1897 unsigned);
1898
1899 /// DST = LHS * RHS, where DST has width the sum of the widths of the
1900 /// operands. No overflow occurs. DST must be disjoint from both operands.
1901 static void tcFullMultiply(WordType *, const WordType *,
1902 const WordType *, unsigned, unsigned);
1903
1904 /// If RHS is zero LHS and REMAINDER are left unchanged, return one.
1905 /// Otherwise set LHS to LHS / RHS with the fractional part discarded, set
1906 /// REMAINDER to the remainder, return zero. i.e.
1907 ///
1908 /// OLD_LHS = RHS * LHS + REMAINDER
1909 ///
1910 /// SCRATCH is a bignum of the same size as the operands and result for use by
1911 /// the routine; its contents need not be initialized and are destroyed. LHS,
1912 /// REMAINDER and SCRATCH must be distinct.
1913 static int tcDivide(WordType *lhs, const WordType *rhs,
1914 WordType *remainder, WordType *scratch,
1915 unsigned parts);
1916
1917 /// Shift a bignum left Count bits. Shifted in bits are zero. There are no
1918 /// restrictions on Count.
1919 static void tcShiftLeft(WordType *, unsigned Words, unsigned Count);
1920
1921 /// Shift a bignum right Count bits. Shifted in bits are zero. There are no
1922 /// restrictions on Count.
1923 static void tcShiftRight(WordType *, unsigned Words, unsigned Count);
1924
1925 /// The obvious AND, OR and XOR and complement operations.
1926 static void tcAnd(WordType *, const WordType *, unsigned);
1927 static void tcOr(WordType *, const WordType *, unsigned);
1928 static void tcXor(WordType *, const WordType *, unsigned);
1929 static void tcComplement(WordType *, unsigned);
1930
1931 /// Comparison (unsigned) of two bignums.
1932 static int tcCompare(const WordType *, const WordType *, unsigned);
1933
1934 /// Increment a bignum in-place. Return the carry flag.
1935 static WordType tcIncrement(WordType *dst, unsigned parts) {
1936 return tcAddPart(dst, 1, parts);
1937 }
1938
1939 /// Decrement a bignum in-place. Return the borrow flag.
1940 static WordType tcDecrement(WordType *dst, unsigned parts) {
1941 return tcSubtractPart(dst, 1, parts);
1942 }
1943
1944 /// Set the least significant BITS and clear the rest.
1945 static void tcSetLeastSignificantBits(WordType *, unsigned, unsigned bits);
1946
1947 /// debug method
1948 void dump() const;
1949
1950 /// @}
1951};
1952
1953/// Magic data for optimising signed division by a constant.
1954struct APInt::ms {
1955 APInt m; ///< magic number
1956 unsigned s; ///< shift amount
1957};
1958
1959/// Magic data for optimising unsigned division by a constant.
1960struct APInt::mu {
1961 APInt m; ///< magic number
1962 bool a; ///< add indicator
1963 unsigned s; ///< shift amount
1964};
1965
1966inline bool operator==(uint64_t V1, const APInt &V2) { return V2 == V1; }
1967
1968inline bool operator!=(uint64_t V1, const APInt &V2) { return V2 != V1; }
1969
1970/// Unary bitwise complement operator.
1971///
1972/// \returns an APInt that is the bitwise complement of \p v.
1973inline APInt operator~(APInt v) {
1974 v.flipAllBits();
1975 return v;
1976}
1977
1978inline APInt operator&(APInt a, const APInt &b) {
1979 a &= b;
1980 return a;
1981}
1982
1983inline APInt operator&(const APInt &a, APInt &&b) {
1984 b &= a;
1985 return std::move(b);
1986}
1987
1988inline APInt operator&(APInt a, uint64_t RHS) {
1989 a &= RHS;
1990 return a;
1991}
1992
1993inline APInt operator&(uint64_t LHS, APInt b) {
1994 b &= LHS;
1995 return b;
1996}
1997
1998inline APInt operator|(APInt a, const APInt &b) {
1999 a |= b;
2000 return a;
2001}
2002
2003inline APInt operator|(const APInt &a, APInt &&b) {
2004 b |= a;
2005 return std::move(b);
2006}
2007
2008inline APInt operator|(APInt a, uint64_t RHS) {
2009 a |= RHS;
2010 return a;
2011}
2012
2013inline APInt operator|(uint64_t LHS, APInt b) {
2014 b |= LHS;
2015 return b;
2016}
2017
2018inline APInt operator^(APInt a, const APInt &b) {
2019 a ^= b;
2020 return a;
2021}
2022
2023inline APInt operator^(const APInt &a, APInt &&b) {
2024 b ^= a;
2025 return std::move(b);
2026}
2027
2028inline APInt operator^(APInt a, uint64_t RHS) {
2029 a ^= RHS;
2030 return a;
2031}
2032
2033inline APInt operator^(uint64_t LHS, APInt b) {
2034 b ^= LHS;
2035 return b;
2036}
2037
2038inline raw_ostream &operator<<(raw_ostream &OS, const APInt &I) {
2039 I.print(OS, true);
2040 return OS;
2041}
2042
2043inline APInt operator-(APInt v) {
2044 v.negate();
2045 return v;
2046}
2047
2048inline APInt operator+(APInt a, const APInt &b) {
2049 a += b;
2050 return a;
2051}
2052
2053inline APInt operator+(const APInt &a, APInt &&b) {
2054 b += a;
2055 return std::move(b);
2056}
2057
2058inline APInt operator+(APInt a, uint64_t RHS) {
2059 a += RHS;
2060 return a;
2061}
2062
2063inline APInt operator+(uint64_t LHS, APInt b) {
2064 b += LHS;
2065 return b;
2066}
2067
2068inline APInt operator-(APInt a, const APInt &b) {
2069 a -= b;
2070 return a;
2071}
2072
2073inline APInt operator-(const APInt &a, APInt &&b) {
2074 b.negate();
2075 b += a;
2076 return std::move(b);
2077}
2078
2079inline APInt operator-(APInt a, uint64_t RHS) {
2080 a -= RHS;
2081 return a;
2082}
2083
2084inline APInt operator-(uint64_t LHS, APInt b) {
2085 b.negate();
2086 b += LHS;
2087 return b;
2088}
2089
2090inline APInt operator*(APInt a, uint64_t RHS) {
2091 a *= RHS;
2092 return a;
2093}
2094
2095inline APInt operator*(uint64_t LHS, APInt b) {
2096 b *= LHS;
2097 return b;
2098}
2099
2100
2101namespace APIntOps {
2102
2103/// Determine the smaller of two APInts considered to be signed.
2104inline const APInt &smin(const APInt &A, const APInt &B) {
2105 return A.slt(B) ? A : B;
2106}
2107
2108/// Determine the larger of two APInts considered to be signed.
2109inline const APInt &smax(const APInt &A, const APInt &B) {
2110 return A.sgt(B) ? A : B;
2111}
2112
2113/// Determine the smaller of two APInts considered to be signed.
2114inline const APInt &umin(const APInt &A, const APInt &B) {
2115 return A.ult(B) ? A : B;
2116}
2117
2118/// Determine the larger of two APInts considered to be unsigned.
2119inline const APInt &umax(const APInt &A, const APInt &B) {
2120 return A.ugt(B) ? A : B;
2121}
2122
2123/// Compute GCD of two unsigned APInt values.
2124///
2125/// This function returns the greatest common divisor of the two APInt values
2126/// using Stein's algorithm.
2127///
2128/// \returns the greatest common divisor of A and B.
2129APInt GreatestCommonDivisor(APInt A, APInt B);
2130
2131/// Converts the given APInt to a double value.
2132///
2133/// Treats the APInt as an unsigned value for conversion purposes.
2134inline double RoundAPIntToDouble(const APInt &APIVal) {
2135 return APIVal.roundToDouble();
2136}
2137
2138/// Converts the given APInt to a double value.
2139///
2140/// Treats the APInt as a signed value for conversion purposes.
2141inline double RoundSignedAPIntToDouble(const APInt &APIVal) {
2142 return APIVal.signedRoundToDouble();
2143}
2144
2145/// Converts the given APInt to a float vlalue.
2146inline float RoundAPIntToFloat(const APInt &APIVal) {
2147 return float(RoundAPIntToDouble(APIVal));
2148}
2149
2150/// Converts the given APInt to a float value.
2151///
2152/// Treast the APInt as a signed value for conversion purposes.
2153inline float RoundSignedAPIntToFloat(const APInt &APIVal) {
2154 return float(APIVal.signedRoundToDouble());
2155}
2156
2157/// Converts the given double value into a APInt.
2158///
2159/// This function convert a double value to an APInt value.
2160APInt RoundDoubleToAPInt(double Double, unsigned width);
2161
2162/// Converts a float value into a APInt.
2163///
2164/// Converts a float value into an APInt value.
2165inline APInt RoundFloatToAPInt(float Float, unsigned width) {
2166 return RoundDoubleToAPInt(double(Float), width);
2167}
2168
2169/// Return A unsign-divided by B, rounded by the given rounding mode.
2170APInt RoundingUDiv(const APInt &A, const APInt &B, APInt::Rounding RM);
2171
2172/// Return A sign-divided by B, rounded by the given rounding mode.
2173APInt RoundingSDiv(const APInt &A, const APInt &B, APInt::Rounding RM);
2174
2175/// Let q(n) = An^2 + Bn + C, and BW = bit width of the value range
2176/// (e.g. 32 for i32).
2177/// This function finds the smallest number n, such that
2178/// (a) n >= 0 and q(n) = 0, or
2179/// (b) n >= 1 and q(n-1) and q(n), when evaluated in the set of all
2180/// integers, belong to two different intervals [Rk, Rk+R),
2181/// where R = 2^BW, and k is an integer.
2182/// The idea here is to find when q(n) "overflows" 2^BW, while at the
2183/// same time "allowing" subtraction. In unsigned modulo arithmetic a
2184/// subtraction (treated as addition of negated numbers) would always
2185/// count as an overflow, but here we want to allow values to decrease
2186/// and increase as long as they are within the same interval.
2187/// Specifically, adding of two negative numbers should not cause an
2188/// overflow (as long as the magnitude does not exceed the bith width).
2189/// On the other hand, given a positive number, adding a negative
2190/// number to it can give a negative result, which would cause the
2191/// value to go from [-2^BW, 0) to [0, 2^BW). In that sense, zero is
2192/// treated as a special case of an overflow.
2193///
2194/// This function returns None if after finding k that minimizes the
2195/// positive solution to q(n) = kR, both solutions are contained between
2196/// two consecutive integers.
2197///
2198/// There are cases where q(n) > T, and q(n+1) < T (assuming evaluation
2199/// in arithmetic modulo 2^BW, and treating the values as signed) by the
2200/// virtue of *signed* overflow. This function will *not* find such an n,
2201/// however it may find a value of n satisfying the inequalities due to
2202/// an *unsigned* overflow (if the values are treated as unsigned).
2203/// To find a solution for a signed overflow, treat it as a problem of
2204/// finding an unsigned overflow with a range with of BW-1.
2205///
2206/// The returned value may have a different bit width from the input
2207/// coefficients.
2208Optional<APInt> SolveQuadraticEquationWrap(APInt A, APInt B, APInt C,
2209 unsigned RangeWidth);
2210} // End of APIntOps namespace
2211
2212// See friend declaration above. This additional declaration is required in
2213// order to compile LLVM with IBM xlC compiler.
2214hash_code hash_value(const APInt &Arg);
2215} // End of llvm namespace
2216
2217#endif