Bug Summary

File:include/llvm/ADT/APInt.h
Warning:line 1573, column 12
Use of memory after it is freed

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name APInt.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mthread-model posix -mframe-pointer=none -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-10/lib/clang/10.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-10~svn372204/build-llvm/lib/Support -I /build/llvm-toolchain-snapshot-10~svn372204/lib/Support -I /build/llvm-toolchain-snapshot-10~svn372204/build-llvm/include -I /build/llvm-toolchain-snapshot-10~svn372204/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-10/lib/clang/10.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-10~svn372204/build-llvm/lib/Support -fdebug-prefix-map=/build/llvm-toolchain-snapshot-10~svn372204=. -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 -faddrsig -o /tmp/scan-build-2019-09-18-161323-42855-1 -x c++ /build/llvm-toolchain-snapshot-10~svn372204/lib/Support/APInt.cpp

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

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

1//===-- llvm/ADT/APInt.h - For Arbitrary Precision Integer -----*- C++ -*--===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8///
9/// \file
10/// This file implements a class to represent arbitrary precision
11/// integral constant values and operations on them.
12///
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_ADT_APINT_H
16#define LLVM_ADT_APINT_H
17
18#include "llvm/Support/Compiler.h"
19#include "llvm/Support/MathExtras.h"
20#include <cassert>
21#include <climits>
22#include <cstring>
23#include <string>
24
25namespace llvm {
26class FoldingSetNodeID;
27class StringRef;
28class hash_code;
29class raw_ostream;
30
31template <typename T> class SmallVectorImpl;
32template <typename T> class ArrayRef;
33template <typename T> class Optional;
34
35class APInt;
36
37inline APInt operator-(APInt);
38
39//===----------------------------------------------------------------------===//
40// APInt Class
41//===----------------------------------------------------------------------===//
42
43/// Class for arbitrary precision integers.
44///
45/// APInt is a functional replacement for common case unsigned integer type like
46/// "unsigned", "unsigned long" or "uint64_t", but also allows non-byte-width
47/// integer sizes and large integer value types such as 3-bits, 15-bits, or more
48/// than 64-bits of precision. APInt provides a variety of arithmetic operators
49/// and methods to manipulate integer values of any bit-width. It supports both
50/// the typical integer arithmetic and comparison operations as well as bitwise
51/// manipulation.
52///
53/// The class has several invariants worth noting:
54/// * All bit, byte, and word positions are zero-based.
55/// * Once the bit width is set, it doesn't change except by the Truncate,
56/// SignExtend, or ZeroExtend operations.
57/// * All binary operators must be on APInt instances of the same bit width.
58/// Attempting to use these operators on instances with different bit
59/// widths will yield an assertion.
60/// * The value is stored canonically as an unsigned value. For operations
61/// where it makes a difference, there are both signed and unsigned variants
62/// of the operation. For example, sdiv and udiv. However, because the bit
63/// widths must be the same, operations such as Mul and Add produce the same
64/// results regardless of whether the values are interpreted as signed or
65/// not.
66/// * In general, the class tries to follow the style of computation that LLVM
67/// uses in its IR. This simplifies its use for LLVM.
68///
69class LLVM_NODISCARD[[clang::warn_unused_result]] APInt {
70public:
71 typedef uint64_t WordType;
72
73 /// This enum is used to hold the constants we needed for APInt.
74 enum : unsigned {
75 /// Byte size of a word.
76 APINT_WORD_SIZE = sizeof(WordType),
77 /// Bits in a word.
78 APINT_BITS_PER_WORD = APINT_WORD_SIZE * CHAR_BIT8
79 };
80
81 enum class Rounding {
82 DOWN,
83 TOWARD_ZERO,
84 UP,
85 };
86
87 static const WordType WORDTYPE_MAX = ~WordType(0);
88
89private:
90 /// This union is used to store the integer value. When the
91 /// integer bit-width <= 64, it uses VAL, otherwise it uses pVal.
92 union {
93 uint64_t VAL; ///< Used to store the <= 64 bits integer value.
94 uint64_t *pVal; ///< Used to store the >64 bits integer value.
95 } U;
96
97 unsigned BitWidth; ///< The number of bits in this APInt.
98
99 friend struct DenseMapAPIntKeyInfo;
100
101 friend class APSInt;
102
103 /// Fast internal constructor
104 ///
105 /// This constructor is used only internally for speed of construction of
106 /// temporaries. It is unsafe for general use so it is not public.
107 APInt(uint64_t *val, unsigned bits) : BitWidth(bits) {
108 U.pVal = val;
109 }
110
111 /// Determine if this APInt just has one word to store value.
112 ///
113 /// \returns true if the number of bits <= 64, false otherwise.
114 bool isSingleWord() const { return BitWidth <= APINT_BITS_PER_WORD; }
115
116 /// Determine which word a bit is in.
117 ///
118 /// \returns the word position for the specified bit position.
119 static unsigned whichWord(unsigned bitPosition) {
120 return bitPosition / APINT_BITS_PER_WORD;
121 }
122
123 /// Determine which bit in a word a bit is in.
124 ///
125 /// \returns the bit position in a word for the specified bit position
126 /// in the APInt.
127 static unsigned whichBit(unsigned bitPosition) {
128 return bitPosition % APINT_BITS_PER_WORD;
129 }
130
131 /// Get a single bit mask.
132 ///
133 /// \returns a uint64_t with only bit at "whichBit(bitPosition)" set
134 /// This method generates and returns a uint64_t (word) mask for a single
135 /// bit at a specific bit position. This is used to mask the bit in the
136 /// corresponding word.
137 static uint64_t maskBit(unsigned bitPosition) {
138 return 1ULL << whichBit(bitPosition);
139 }
140
141 /// Clear unused high order bits
142 ///
143 /// This method is used internally to clear the top "N" bits in the high order
144 /// word that are not used by the APInt. This is needed after the most
145 /// significant word is assigned a value to ensure that those bits are
146 /// zero'd out.
147 APInt &clearUnusedBits() {
148 // Compute how many bits are used in the final word
149 unsigned WordBits = ((BitWidth-1) % APINT_BITS_PER_WORD) + 1;
150
151 // Mask out the high bits.
152 uint64_t mask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - WordBits);
153 if (isSingleWord())
154 U.VAL &= mask;
155 else
156 U.pVal[getNumWords() - 1] &= mask;
157 return *this;
158 }
159
160 /// Get the word corresponding to a bit position
161 /// \returns the corresponding word for the specified bit position.
162 uint64_t getWord(unsigned bitPosition) const {
163 return isSingleWord() ? U.VAL : U.pVal[whichWord(bitPosition)];
164 }
165
166 /// Utility method to change the bit width of this APInt to new bit width,
167 /// allocating and/or deallocating as necessary. There is no guarantee on the
168 /// value of any bits upon return. Caller should populate the bits after.
169 void reallocate(unsigned NewBitWidth);
170
171 /// Convert a char array into an APInt
172 ///
173 /// \param radix 2, 8, 10, 16, or 36
174 /// Converts a string into a number. The string must be non-empty
175 /// and well-formed as a number of the given base. The bit-width
176 /// must be sufficient to hold the result.
177 ///
178 /// This is used by the constructors that take string arguments.
179 ///
180 /// StringRef::getAsInteger is superficially similar but (1) does
181 /// not assume that the string is well-formed and (2) grows the
182 /// result to hold the input.
183 void fromString(unsigned numBits, StringRef str, uint8_t radix);
184
185 /// An internal division function for dividing APInts.
186 ///
187 /// This is used by the toString method to divide by the radix. It simply
188 /// provides a more convenient form of divide for internal use since KnuthDiv
189 /// has specific constraints on its inputs. If those constraints are not met
190 /// then it provides a simpler form of divide.
191 static void divide(const WordType *LHS, unsigned lhsWords,
192 const WordType *RHS, unsigned rhsWords, WordType *Quotient,
193 WordType *Remainder);
194
195 /// out-of-line slow case for inline constructor
196 void initSlowCase(uint64_t val, bool isSigned);
197
198 /// shared code between two array constructors
199 void initFromArray(ArrayRef<uint64_t> array);
200
201 /// out-of-line slow case for inline copy constructor
202 void initSlowCase(const APInt &that);
203
204 /// out-of-line slow case for shl
205 void shlSlowCase(unsigned ShiftAmt);
206
207 /// out-of-line slow case for lshr.
208 void lshrSlowCase(unsigned ShiftAmt);
209
210 /// out-of-line slow case for ashr.
211 void ashrSlowCase(unsigned ShiftAmt);
212
213 /// out-of-line slow case for operator=
214 void AssignSlowCase(const APInt &RHS);
215
216 /// out-of-line slow case for operator==
217 bool EqualSlowCase(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__));
218
219 /// out-of-line slow case for countLeadingZeros
220 unsigned countLeadingZerosSlowCase() const LLVM_READONLY__attribute__((__pure__));
221
222 /// out-of-line slow case for countLeadingOnes.
223 unsigned countLeadingOnesSlowCase() const LLVM_READONLY__attribute__((__pure__));
224
225 /// out-of-line slow case for countTrailingZeros.
226 unsigned countTrailingZerosSlowCase() const LLVM_READONLY__attribute__((__pure__));
227
228 /// out-of-line slow case for countTrailingOnes
229 unsigned countTrailingOnesSlowCase() const LLVM_READONLY__attribute__((__pure__));
230
231 /// out-of-line slow case for countPopulation
232 unsigned countPopulationSlowCase() const LLVM_READONLY__attribute__((__pure__));
233
234 /// out-of-line slow case for intersects.
235 bool intersectsSlowCase(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__));
236
237 /// out-of-line slow case for isSubsetOf.
238 bool isSubsetOfSlowCase(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__));
239
240 /// out-of-line slow case for setBits.
241 void setBitsSlowCase(unsigned loBit, unsigned hiBit);
242
243 /// out-of-line slow case for flipAllBits.
244 void flipAllBitsSlowCase();
245
246 /// out-of-line slow case for operator&=.
247 void AndAssignSlowCase(const APInt& RHS);
248
249 /// out-of-line slow case for operator|=.
250 void OrAssignSlowCase(const APInt& RHS);
251
252 /// out-of-line slow case for operator^=.
253 void XorAssignSlowCase(const APInt& RHS);
254
255 /// Unsigned comparison. Returns -1, 0, or 1 if this APInt is less than, equal
256 /// to, or greater than RHS.
257 int compare(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__));
258
259 /// Signed comparison. Returns -1, 0, or 1 if this APInt is less than, equal
260 /// to, or greater than RHS.
261 int compareSigned(const APInt &RHS) const LLVM_READONLY__attribute__((__pure__));
262
263public:
264 /// \name Constructors
265 /// @{
266
267 /// Create a new APInt of numBits width, initialized as val.
268 ///
269 /// If isSigned is true then val is treated as if it were a signed value
270 /// (i.e. as an int64_t) and the appropriate sign extension to the bit width
271 /// will be done. Otherwise, no sign extension occurs (high order bits beyond
272 /// the range of val are zero filled).
273 ///
274 /// \param numBits the bit width of the constructed APInt
275 /// \param val the initial value of the APInt
276 /// \param isSigned how to treat signedness of val
277 APInt(unsigned numBits, uint64_t val, bool isSigned = false)
278 : BitWidth(numBits) {
279 assert(BitWidth && "bitwidth too small")((BitWidth && "bitwidth too small") ? static_cast<
void> (0) : __assert_fail ("BitWidth && \"bitwidth too small\""
, "/build/llvm-toolchain-snapshot-10~svn372204/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
323 U.VAL = that.U.VAL;
324 else
325 initSlowCase(that);
4
Calling 'APInt::initSlowCase'
8
Returned allocated memory
326 }
327
328 /// Move Constructor.
329 APInt(APInt &&that) : BitWidth(that.BitWidth) {
330 memcpy(&U, &that.U, sizeof(U));
331 that.BitWidth = 0;
332 }
333
334 /// Destructor.
335 ~APInt() {
336 if (needsCleanup())
337 delete[] U.pVal;
338 }
339
340 /// Default constructor that creates an uninteresting APInt
341 /// representing a 1-bit zero value.
342 ///
343 /// This is useful for object deserialization (pair this with the static
344 /// method Read).
345 explicit APInt() : BitWidth(1) { U.VAL = 0; }
346
347 /// Returns whether this instance allocated memory.
348 bool needsCleanup() const { return !isSingleWord(); }
349
350 /// Used to insert APInt objects, or objects that contain APInt objects, into
351 /// FoldingSets.
352 void Profile(FoldingSetNodeID &id) const;
353
354 /// @}
355 /// \name Value Tests
356 /// @{
357
358 /// Determine sign of this APInt.
359 ///
360 /// This tests the high bit of this APInt to determine if it is set.
361 ///
362 /// \returns true if this APInt is negative, false otherwise
363 bool isNegative() const { return (*this)[BitWidth - 1]; }
364
365 /// Determine if this APInt Value is non-negative (>= 0)
366 ///
367 /// This tests the high bit of the APInt to determine if it is unset.
368 bool isNonNegative() const { return !isNegative(); }
369
370 /// Determine if sign bit of this APInt is set.
371 ///
372 /// This tests the high bit of this APInt to determine if it is set.
373 ///
374 /// \returns true if this APInt has its sign bit set, false otherwise.
375 bool isSignBitSet() const { return (*this)[BitWidth-1]; }
376
377 /// Determine if sign bit of this APInt is clear.
378 ///
379 /// This tests the high bit of this APInt to determine if it is clear.
380 ///
381 /// \returns true if this APInt has its sign bit clear, false otherwise.
382 bool isSignBitClear() const { return !isSignBitSet(); }
383
384 /// Determine if this APInt Value is positive.
385 ///
386 /// This tests if the value of this APInt is positive (> 0). Note
387 /// that 0 is not a positive value.
388 ///
389 /// \returns true if this APInt is positive.
390 bool isStrictlyPositive() const { return isNonNegative() && !isNullValue(); }
391
392 /// Determine if all bits are set
393 ///
394 /// This checks to see if the value has all bits of the APInt are set or not.
395 bool isAllOnesValue() const {
396 if (isSingleWord())
397 return U.VAL == WORDTYPE_MAX >> (APINT_BITS_PER_WORD - BitWidth);
398 return countTrailingOnesSlowCase() == BitWidth;
399 }
400
401 /// Determine if all bits are clear
402 ///
403 /// This checks to see if the value has all bits of the APInt are clear or
404 /// not.
405 bool isNullValue() const { return !*this; }
406
407 /// Determine if this is a value of 1.
408 ///
409 /// This checks to see if the value of this APInt is one.
410 bool isOneValue() const {
411 if (isSingleWord())
412 return U.VAL == 1;
413 return countLeadingZerosSlowCase() == BitWidth - 1;
414 }
415
416 /// Determine if this is the largest unsigned value.
417 ///
418 /// This checks to see if the value of this APInt is the maximum unsigned
419 /// value for the APInt's bit width.
420 bool isMaxValue() const { return isAllOnesValue(); }
421
422 /// Determine if this is the largest signed value.
423 ///
424 /// This checks to see if the value of this APInt is the maximum signed
425 /// value for the APInt's bit width.
426 bool isMaxSignedValue() const {
427 if (isSingleWord())
428 return U.VAL == ((WordType(1) << (BitWidth - 1)) - 1);
429 return !isNegative() && countTrailingOnesSlowCase() == BitWidth - 1;
430 }
431
432 /// Determine if this is the smallest unsigned value.
433 ///
434 /// This checks to see if the value of this APInt is the minimum unsigned
435 /// value for the APInt's bit width.
436 bool isMinValue() const { return isNullValue(); }
437
438 /// Determine if this is the smallest signed value.
439 ///
440 /// This checks to see if the value of this APInt is the minimum signed
441 /// value for the APInt's bit width.
442 bool isMinSignedValue() const {
443 if (isSingleWord())
444 return U.VAL == (WordType(1) << (BitWidth - 1));
445 return isNegative() && countTrailingZerosSlowCase() == BitWidth - 1;
446 }
447
448 /// Check if this APInt has an N-bits unsigned integer value.
449 bool isIntN(unsigned N) const {
450 assert(N && "N == 0 ???")((N && "N == 0 ???") ? static_cast<void> (0) : __assert_fail
("N && \"N == 0 ???\"", "/build/llvm-toolchain-snapshot-10~svn372204/include/llvm/ADT/APInt.h"
, 450, __PRETTY_FUNCTION__))
;
451 return getActiveBits() <= N;
452 }
453
454 /// Check if this APInt has an N-bits signed integer value.
455 bool isSignedIntN(unsigned N) const {
456 assert(N && "N == 0 ???")((N && "N == 0 ???") ? static_cast<void> (0) : __assert_fail
("N && \"N == 0 ???\"", "/build/llvm-toolchain-snapshot-10~svn372204/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();
18
Calling 'APInt::ugt'
483 }
484
485 /// Check if the APInt consists of a repeated bit pattern.
486 ///
487 /// e.g. 0x01010101 satisfies isSplat(8).
488 /// \param SplatSizeInBits The size of the pattern in bits. Must divide bit
489 /// width without remainder.
490 bool isSplat(unsigned SplatSizeInBits) const;
491
492 /// \returns true if this APInt value is a sequence of \param numBits ones
493 /// starting at the least significant bit with the remainder zero.
494 bool isMask(unsigned numBits) const {
495 assert(numBits != 0 && "numBits must be non-zero")((numBits != 0 && "numBits must be non-zero") ? static_cast
<void> (0) : __assert_fail ("numBits != 0 && \"numBits must be non-zero\""
, "/build/llvm-toolchain-snapshot-10~svn372204/include/llvm/ADT/APInt.h"
, 495, __PRETTY_FUNCTION__))
;
496 assert(numBits <= BitWidth && "numBits out of range")((numBits <= BitWidth && "numBits out of range") ?
static_cast<void> (0) : __assert_fail ("numBits <= BitWidth && \"numBits out of range\""
, "/build/llvm-toolchain-snapshot-10~svn372204/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-10~svn372204/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-10~svn372204/include/llvm/ADT/APInt.h"
, 792, __PRETTY_FUNCTION__))
;
793 if (isSingleWord())
794 U.VAL &= RHS.U.VAL;
795 else
796 AndAssignSlowCase(RHS);
797 return *this;
798 }
799
800 /// Bitwise AND assignment operator.
801 ///
802 /// Performs a bitwise AND operation on this APInt and RHS. RHS is
803 /// logically zero-extended or truncated to match the bit-width of
804 /// the LHS.
805 APInt &operator&=(uint64_t RHS) {
806 if (isSingleWord()) {
807 U.VAL &= RHS;
808 return *this;
809 }
810 U.pVal[0] &= RHS;
811 memset(U.pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE);
812 return *this;
813 }
814
815 /// Bitwise OR assignment operator.
816 ///
817 /// Performs a bitwise OR operation on this APInt and RHS. The result is
818 /// assigned *this;
819 ///
820 /// \returns *this after ORing with RHS.
821 APInt &operator|=(const APInt &RHS) {
822 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")((BitWidth == RHS.BitWidth && "Bit widths must be the same"
) ? static_cast<void> (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\""
, "/build/llvm-toolchain-snapshot-10~svn372204/include/llvm/ADT/APInt.h"
, 822, __PRETTY_FUNCTION__))
;
823 if (isSingleWord())
824 U.VAL |= RHS.U.VAL;
825 else
826 OrAssignSlowCase(RHS);
827 return *this;
828 }
829
830 /// Bitwise OR assignment operator.
831 ///
832 /// Performs a bitwise OR operation on this APInt and RHS. RHS is
833 /// logically zero-extended or truncated to match the bit-width of
834 /// the LHS.
835 APInt &operator|=(uint64_t RHS) {
836 if (isSingleWord()) {
837 U.VAL |= RHS;
838 clearUnusedBits();
839 } else {
840 U.pVal[0] |= RHS;
841 }
842 return *this;
843 }
844
845 /// Bitwise XOR assignment operator.
846 ///
847 /// Performs a bitwise XOR operation on this APInt and RHS. The result is
848 /// assigned to *this.
849 ///
850 /// \returns *this after XORing with RHS.
851 APInt &operator^=(const APInt &RHS) {
852 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")((BitWidth == RHS.BitWidth && "Bit widths must be the same"
) ? static_cast<void> (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\""
, "/build/llvm-toolchain-snapshot-10~svn372204/include/llvm/ADT/APInt.h"
, 852, __PRETTY_FUNCTION__))
;
853 if (isSingleWord())
854 U.VAL ^= RHS.U.VAL;
855 else
856 XorAssignSlowCase(RHS);
857 return *this;
858 }
859
860 /// Bitwise XOR assignment operator.
861 ///
862 /// Performs a bitwise XOR operation on this APInt and RHS. RHS is
863 /// logically zero-extended or truncated to match the bit-width of
864 /// the LHS.
865 APInt &operator^=(uint64_t RHS) {
866 if (isSingleWord()) {
867 U.VAL ^= RHS;
868 clearUnusedBits();
869 } else {
870 U.pVal[0] ^= RHS;
871 }
872 return *this;
873 }
874
875 /// Multiplication assignment operator.
876 ///
877 /// Multiplies this APInt by RHS and assigns the result to *this.
878 ///
879 /// \returns *this
880 APInt &operator*=(const APInt &RHS);
881 APInt &operator*=(uint64_t RHS);
882
883 /// Addition assignment operator.
884 ///
885 /// Adds RHS to *this and assigns the result to *this.
886 ///
887 /// \returns *this
888 APInt &operator+=(const APInt &RHS);
889 APInt &operator+=(uint64_t RHS);
890
891 /// Subtraction assignment operator.
892 ///
893 /// Subtracts RHS from *this and assigns the result to *this.
894 ///
895 /// \returns *this
896 APInt &operator-=(const APInt &RHS);
897 APInt &operator-=(uint64_t RHS);
898
899 /// Left-shift assignment function.
900 ///
901 /// Shifts *this left by shiftAmt and assigns the result to *this.
902 ///
903 /// \returns *this after shifting left by ShiftAmt
904 APInt &operator<<=(unsigned ShiftAmt) {
905 assert(ShiftAmt <= BitWidth && "Invalid shift amount")((ShiftAmt <= BitWidth && "Invalid shift amount") ?
static_cast<void> (0) : __assert_fail ("ShiftAmt <= BitWidth && \"Invalid shift amount\""
, "/build/llvm-toolchain-snapshot-10~svn372204/include/llvm/ADT/APInt.h"
, 905, __PRETTY_FUNCTION__))
;
906 if (isSingleWord()) {
907 if (ShiftAmt == BitWidth)
908 U.VAL = 0;
909 else
910 U.VAL <<= ShiftAmt;
911 return clearUnusedBits();
912 }
913 shlSlowCase(ShiftAmt);
914 return *this;
915 }
916
917 /// Left-shift assignment function.
918 ///
919 /// Shifts *this left by shiftAmt and assigns the result to *this.
920 ///
921 /// \returns *this after shifting left by ShiftAmt
922 APInt &operator<<=(const APInt &ShiftAmt);
923
924 /// @}
925 /// \name Binary Operators
926 /// @{
927
928 /// Multiplication operator.
929 ///
930 /// Multiplies this APInt by RHS and returns the result.
931 APInt operator*(const APInt &RHS) const;
932
933 /// Left logical shift operator.
934 ///
935 /// Shifts this APInt left by \p Bits and returns the result.
936 APInt operator<<(unsigned Bits) const { return shl(Bits); }
937
938 /// Left logical shift operator.
939 ///
940 /// Shifts this APInt left by \p Bits and returns the result.
941 APInt operator<<(const APInt &Bits) const { return shl(Bits); }
942
943 /// Arithmetic right-shift function.
944 ///
945 /// Arithmetic right-shift this APInt by shiftAmt.
946 APInt ashr(unsigned ShiftAmt) const {
947 APInt R(*this);
948 R.ashrInPlace(ShiftAmt);
949 return R;
950 }
951
952 /// Arithmetic right-shift this APInt by ShiftAmt in place.
953 void ashrInPlace(unsigned ShiftAmt) {
954 assert(ShiftAmt <= BitWidth && "Invalid shift amount")((ShiftAmt <= BitWidth && "Invalid shift amount") ?
static_cast<void> (0) : __assert_fail ("ShiftAmt <= BitWidth && \"Invalid shift amount\""
, "/build/llvm-toolchain-snapshot-10~svn372204/include/llvm/ADT/APInt.h"
, 954, __PRETTY_FUNCTION__))
;
955 if (isSingleWord()) {
956 int64_t SExtVAL = SignExtend64(U.VAL, BitWidth);
957 if (ShiftAmt == BitWidth)
958 U.VAL = SExtVAL >> (APINT_BITS_PER_WORD - 1); // Fill with sign bit.
959 else
960 U.VAL = SExtVAL >> ShiftAmt;
961 clearUnusedBits();
962 return;
963 }
964 ashrSlowCase(ShiftAmt);
965 }
966
967 /// Logical right-shift function.
968 ///
969 /// Logical right-shift this APInt by shiftAmt.
970 APInt lshr(unsigned shiftAmt) const {
971 APInt R(*this);
972 R.lshrInPlace(shiftAmt);
973 return R;
974 }
975
976 /// Logical right-shift this APInt by ShiftAmt in place.
977 void lshrInPlace(unsigned ShiftAmt) {
978 assert(ShiftAmt <= BitWidth && "Invalid shift amount")((ShiftAmt <= BitWidth && "Invalid shift amount") ?
static_cast<void> (0) : __assert_fail ("ShiftAmt <= BitWidth && \"Invalid shift amount\""
, "/build/llvm-toolchain-snapshot-10~svn372204/include/llvm/ADT/APInt.h"
, 978, __PRETTY_FUNCTION__))
;
979 if (isSingleWord()) {
980 if (ShiftAmt == BitWidth)
981 U.VAL = 0;
982 else
983 U.VAL >>= ShiftAmt;
984 return;
985 }
986 lshrSlowCase(ShiftAmt);
987 }
988
989 /// Left-shift function.
990 ///
991 /// Left-shift this APInt by shiftAmt.
992 APInt shl(unsigned shiftAmt) const {
993 APInt R(*this);
994 R <<= shiftAmt;
995 return R;
996 }
997
998 /// Rotate left by rotateAmt.
999 APInt rotl(unsigned rotateAmt) const;
1000
1001 /// Rotate right by rotateAmt.
1002 APInt rotr(unsigned rotateAmt) const;
1003
1004 /// Arithmetic right-shift function.
1005 ///
1006 /// Arithmetic right-shift this APInt by shiftAmt.
1007 APInt ashr(const APInt &ShiftAmt) const {
1008 APInt R(*this);
1009 R.ashrInPlace(ShiftAmt);
1010 return R;
1011 }
1012
1013 /// Arithmetic right-shift this APInt by shiftAmt in place.
1014 void ashrInPlace(const APInt &shiftAmt);
1015
1016 /// Logical right-shift function.
1017 ///
1018 /// Logical right-shift this APInt by shiftAmt.
1019 APInt lshr(const APInt &ShiftAmt) const {
1020 APInt R(*this);
1021 R.lshrInPlace(ShiftAmt);
1022 return R;
1023 }
1024
1025 /// Logical right-shift this APInt by ShiftAmt in place.
1026 void lshrInPlace(const APInt &ShiftAmt);
1027
1028 /// Left-shift function.
1029 ///
1030 /// Left-shift this APInt by shiftAmt.
1031 APInt shl(const APInt &ShiftAmt) const {
1032 APInt R(*this);
1033 R <<= ShiftAmt;
1034 return R;
1035 }
1036
1037 /// Rotate left by rotateAmt.
1038 APInt rotl(const APInt &rotateAmt) const;
1039
1040 /// Rotate right by rotateAmt.
1041 APInt rotr(const APInt &rotateAmt) const;
1042
1043 /// Unsigned division operation.
1044 ///
1045 /// Perform an unsigned divide operation on this APInt by RHS. Both this and
1046 /// RHS are treated as unsigned quantities for purposes of this division.
1047 ///
1048 /// \returns a new APInt value containing the division result, rounded towards
1049 /// zero.
1050 APInt udiv(const APInt &RHS) const;
1051 APInt udiv(uint64_t RHS) const;
1052
1053 /// Signed division function for APInt.
1054 ///
1055 /// Signed divide this APInt by APInt RHS.
1056 ///
1057 /// The result is rounded towards zero.
1058 APInt sdiv(const APInt &RHS) const;
1059 APInt sdiv(int64_t RHS) const;
1060
1061 /// Unsigned remainder operation.
1062 ///
1063 /// Perform an unsigned remainder operation on this APInt with RHS being the
1064 /// divisor. Both this and RHS are treated as unsigned quantities for purposes
1065 /// of this operation. Note that this is a true remainder operation and not a
1066 /// modulo operation because the sign follows the sign of the dividend which
1067 /// is *this.
1068 ///
1069 /// \returns a new APInt value containing the remainder result
1070 APInt urem(const APInt &RHS) const;
1071 uint64_t urem(uint64_t RHS) const;
1072
1073 /// Function for signed remainder operation.
1074 ///
1075 /// Signed remainder operation on APInt.
1076 APInt srem(const APInt &RHS) const;
1077 int64_t srem(int64_t RHS) const;
1078
1079 /// Dual division/remainder interface.
1080 ///
1081 /// Sometimes it is convenient to divide two APInt values and obtain both the
1082 /// quotient and remainder. This function does both operations in the same
1083 /// computation making it a little more efficient. The pair of input arguments
1084 /// may overlap with the pair of output arguments. It is safe to call
1085 /// udivrem(X, Y, X, Y), for example.
1086 static void udivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient,
1087 APInt &Remainder);
1088 static void udivrem(const APInt &LHS, uint64_t RHS, APInt &Quotient,
1089 uint64_t &Remainder);
1090
1091 static void sdivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient,
1092 APInt &Remainder);
1093 static void sdivrem(const APInt &LHS, int64_t RHS, APInt &Quotient,
1094 int64_t &Remainder);
1095
1096 // Operations that return overflow indicators.
1097 APInt sadd_ov(const APInt &RHS, bool &Overflow) const;
1098 APInt uadd_ov(const APInt &RHS, bool &Overflow) const;
1099 APInt ssub_ov(const APInt &RHS, bool &Overflow) const;
1100 APInt usub_ov(const APInt &RHS, bool &Overflow) const;
1101 APInt sdiv_ov(const APInt &RHS, bool &Overflow) const;
1102 APInt smul_ov(const APInt &RHS, bool &Overflow) const;
1103 APInt umul_ov(const APInt &RHS, bool &Overflow) const;
1104 APInt sshl_ov(const APInt &Amt, bool &Overflow) const;
1105 APInt ushl_ov(const APInt &Amt, bool &Overflow) const;
1106
1107 // Operations that saturate
1108 APInt sadd_sat(const APInt &RHS) const;
1109 APInt uadd_sat(const APInt &RHS) const;
1110 APInt ssub_sat(const APInt &RHS) const;
1111 APInt usub_sat(const APInt &RHS) const;
1112
1113 /// Array-indexing support.
1114 ///
1115 /// \returns the bit value at bitPosition
1116 bool operator[](unsigned bitPosition) const {
1117 assert(bitPosition < getBitWidth() && "Bit position out of bounds!")((bitPosition < getBitWidth() && "Bit position out of bounds!"
) ? static_cast<void> (0) : __assert_fail ("bitPosition < getBitWidth() && \"Bit position out of bounds!\""
, "/build/llvm-toolchain-snapshot-10~svn372204/include/llvm/ADT/APInt.h"
, 1117, __PRETTY_FUNCTION__))
;
1118 return (maskBit(bitPosition) & getWord(bitPosition)) != 0;
1119 }
1120
1121 /// @}
1122 /// \name Comparison Operators
1123 /// @{
1124
1125 /// Equality operator.
1126 ///
1127 /// Compares this APInt with RHS for the validity of the equality
1128 /// relationship.
1129 bool operator==(const APInt &RHS) const {
1130 assert(BitWidth == RHS.BitWidth && "Comparison requires equal bit widths")((BitWidth == RHS.BitWidth && "Comparison requires equal bit widths"
) ? static_cast<void> (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Comparison requires equal bit widths\""
, "/build/llvm-toolchain-snapshot-10~svn372204/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;
19
Assuming the condition is false
20
Calling 'APInt::getZExtValue'
1265 }
1266
1267 /// Signed greather than comparison
1268 ///
1269 /// Regards both *this and RHS as signed quantities and compares them for the
1270 /// validity of the greater-than relationship.
1271 ///
1272 /// \returns true if *this > RHS when both are considered signed.
1273 bool sgt(const APInt &RHS) const { return !sle(RHS); }
1274
1275 /// Signed greater than comparison
1276 ///
1277 /// Regards both *this as a signed quantity and compares it with RHS for
1278 /// the validity of the greater-than relationship.
1279 ///
1280 /// \returns true if *this > RHS when considered signed.
1281 bool sgt(int64_t RHS) const {
1282 return (!isSingleWord() && getMinSignedBits() > 64) ? !isNegative()
1283 : getSExtValue() > RHS;
1284 }
1285
1286 /// Unsigned greater or equal comparison
1287 ///
1288 /// Regards both *this and RHS as unsigned quantities and compares them for
1289 /// validity of the greater-or-equal relationship.
1290 ///
1291 /// \returns true if *this >= RHS when both are considered unsigned.
1292 bool uge(const APInt &RHS) const { return !ult(RHS); }
1293
1294 /// Unsigned greater or equal comparison
1295 ///
1296 /// Regards both *this as an unsigned quantity and compares it with RHS for
1297 /// the validity of the greater-or-equal relationship.
1298 ///
1299 /// \returns true if *this >= RHS when considered unsigned.
1300 bool uge(uint64_t RHS) const { return !ult(RHS); }
1301
1302 /// Signed greater or equal comparison
1303 ///
1304 /// Regards both *this and RHS as signed quantities and compares them for
1305 /// validity of the greater-or-equal relationship.
1306 ///
1307 /// \returns true if *this >= RHS when both are considered signed.
1308 bool sge(const APInt &RHS) const { return !slt(RHS); }
1309
1310 /// Signed greater or equal comparison
1311 ///
1312 /// Regards both *this as a signed quantity and compares it with RHS for
1313 /// the validity of the greater-or-equal relationship.
1314 ///
1315 /// \returns true if *this >= RHS when considered signed.
1316 bool sge(int64_t RHS) const { return !slt(RHS); }
1317
1318 /// This operation tests if there are any pairs of corresponding bits
1319 /// between this APInt and RHS that are both set.
1320 bool intersects(const APInt &RHS) const {
1321 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")((BitWidth == RHS.BitWidth && "Bit widths must be the same"
) ? static_cast<void> (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\""
, "/build/llvm-toolchain-snapshot-10~svn372204/include/llvm/ADT/APInt.h"
, 1321, __PRETTY_FUNCTION__))
;
1322 if (isSingleWord())
1323 return (U.VAL & RHS.U.VAL) != 0;
1324 return intersectsSlowCase(RHS);
1325 }
1326
1327 /// This operation checks that all bits set in this APInt are also set in RHS.
1328 bool isSubsetOf(const APInt &RHS) const {
1329 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same")((BitWidth == RHS.BitWidth && "Bit widths must be the same"
) ? static_cast<void> (0) : __assert_fail ("BitWidth == RHS.BitWidth && \"Bit widths must be the same\""
, "/build/llvm-toolchain-snapshot-10~svn372204/include/llvm/ADT/APInt.h"
, 1329, __PRETTY_FUNCTION__))
;
1330 if (isSingleWord())
1331 return (U.VAL & ~RHS.U.VAL) == 0;
1332 return isSubsetOfSlowCase(RHS);
1333 }
1334
1335 /// @}
1336 /// \name Resizing Operators
1337 /// @{
1338
1339 /// Truncate to new width.
1340 ///
1341 /// Truncate the APInt to a specified width. It is an error to specify a width
1342 /// that is greater than or equal to the current width.
1343 APInt trunc(unsigned width) const;
1344
1345 /// Sign extend to a new width.
1346 ///
1347 /// This operation sign extends the APInt to a new width. If the high order
1348 /// bit is set, the fill on the left will be done with 1 bits, otherwise zero.
1349 /// It is an error to specify a width that is less than or equal to the
1350 /// current width.
1351 APInt sext(unsigned width) const;
1352
1353 /// Zero extend to a new width.
1354 ///
1355 /// This operation zero extends the APInt to a new width. The high order bits
1356 /// are filled with 0 bits. It is an error to specify a width that is less
1357 /// than or equal to the current width.
1358 APInt zext(unsigned width) const;
1359
1360 /// Sign extend or truncate to width
1361 ///
1362 /// Make this APInt have the bit width given by \p width. The value is sign
1363 /// extended, truncated, or left alone to make it that width.
1364 APInt sextOrTrunc(unsigned width) const;
1365
1366 /// Zero extend or truncate to width
1367 ///
1368 /// Make this APInt have the bit width given by \p width. The value is zero
1369 /// extended, truncated, or left alone to make it that width.
1370 APInt zextOrTrunc(unsigned width) const;
1371
1372 /// Sign extend or truncate to width
1373 ///
1374 /// Make this APInt have the bit width given by \p width. The value is sign
1375 /// extended, or left alone to make it that width.
1376 APInt sextOrSelf(unsigned width) const;
1377
1378 /// Zero extend or truncate to width
1379 ///
1380 /// Make this APInt have the bit width given by \p width. The value is zero
1381 /// extended, or left alone to make it that width.
1382 APInt zextOrSelf(unsigned width) const;
1383
1384 /// @}
1385 /// \name Bit Manipulation Operators
1386 /// @{
1387
1388 /// Set every bit to 1.
1389 void setAllBits() {
1390 if (isSingleWord())
1391 U.VAL = WORDTYPE_MAX;
1392 else
1393 // Set all the bits in all the words.
1394 memset(U.pVal, -1, getNumWords() * APINT_WORD_SIZE);
1395 // Clear the unused ones
1396 clearUnusedBits();
1397 }
1398
1399 /// Set a given bit to 1.
1400 ///
1401 /// Set the given bit to 1 whose position is given as "bitPosition".
1402 void setBit(unsigned BitPosition) {
1403 assert(BitPosition < BitWidth && "BitPosition out of range")((BitPosition < BitWidth && "BitPosition out of range"
) ? static_cast<void> (0) : __assert_fail ("BitPosition < BitWidth && \"BitPosition out of range\""
, "/build/llvm-toolchain-snapshot-10~svn372204/include/llvm/ADT/APInt.h"
, 1403, __PRETTY_FUNCTION__))
;
1404 WordType Mask = maskBit(BitPosition);
1405 if (isSingleWord())
1406 U.VAL |= Mask;
1407 else
1408 U.pVal[whichWord(BitPosition)] |= Mask;
1409 }
1410
1411 /// Set the sign bit to 1.
1412 void setSignBit() {
1413 setBit(BitWidth - 1);
1414 }
1415
1416 /// Set the bits from loBit (inclusive) to hiBit (exclusive) to 1.
1417 void setBits(unsigned loBit, unsigned hiBit) {
1418 assert(hiBit <= BitWidth && "hiBit out of range")((hiBit <= BitWidth && "hiBit out of range") ? static_cast
<void> (0) : __assert_fail ("hiBit <= BitWidth && \"hiBit out of range\""
, "/build/llvm-toolchain-snapshot-10~svn372204/include/llvm/ADT/APInt.h"
, 1418, __PRETTY_FUNCTION__))
;
1419 assert(loBit <= BitWidth && "loBit out of range")((loBit <= BitWidth && "loBit out of range") ? static_cast
<void> (0) : __assert_fail ("loBit <= BitWidth && \"loBit out of range\""
, "/build/llvm-toolchain-snapshot-10~svn372204/include/llvm/ADT/APInt.h"
, 1419, __PRETTY_FUNCTION__))
;
1420 assert(loBit <= hiBit && "loBit greater than hiBit")((loBit <= hiBit && "loBit greater than hiBit") ? static_cast
<void> (0) : __assert_fail ("loBit <= hiBit && \"loBit greater than hiBit\""
, "/build/llvm-toolchain-snapshot-10~svn372204/include/llvm/ADT/APInt.h"
, 1420, __PRETTY_FUNCTION__))
;
1421 if (loBit == hiBit)
1422 return;
1423 if (loBit < APINT_BITS_PER_WORD && hiBit <= APINT_BITS_PER_WORD) {
1424 uint64_t mask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - (hiBit - loBit));
1425 mask <<= loBit;
1426 if (isSingleWord())
1427 U.VAL |= mask;
1428 else
1429 U.pVal[0] |= mask;
1430 } else {
1431 setBitsSlowCase(loBit, hiBit);
1432 }
1433 }
1434
1435 /// Set the top bits starting from loBit.
1436 void setBitsFrom(unsigned loBit) {
1437 return setBits(loBit, BitWidth);
1438 }
1439
1440 /// Set the bottom loBits bits.
1441 void setLowBits(unsigned loBits) {
1442 return setBits(0, loBits);
1443 }
1444
1445 /// Set the top hiBits bits.
1446 void setHighBits(unsigned hiBits) {
1447 return setBits(BitWidth - hiBits, BitWidth);
1448 }
1449
1450 /// Set every bit to 0.
1451 void clearAllBits() {
1452 if (isSingleWord())
1453 U.VAL = 0;
1454 else
1455 memset(U.pVal, 0, getNumWords() * APINT_WORD_SIZE);
1456 }
1457
1458 /// Set a given bit to 0.
1459 ///
1460 /// Set the given bit to 0 whose position is given as "bitPosition".
1461 void clearBit(unsigned BitPosition) {
1462 assert(BitPosition < BitWidth && "BitPosition out of range")((BitPosition < BitWidth && "BitPosition out of range"
) ? static_cast<void> (0) : __assert_fail ("BitPosition < BitWidth && \"BitPosition out of range\""
, "/build/llvm-toolchain-snapshot-10~svn372204/include/llvm/ADT/APInt.h"
, 1462, __PRETTY_FUNCTION__))
;
1463 WordType Mask = ~maskBit(BitPosition);
1464 if (isSingleWord())
1465 U.VAL &= Mask;
1466 else
1467 U.pVal[whichWord(BitPosition)] &= Mask;
1468 }
1469
1470 /// Set bottom loBits bits to 0.
1471 void clearLowBits(unsigned loBits) {
1472 assert(loBits <= BitWidth && "More bits than bitwidth")((loBits <= BitWidth && "More bits than bitwidth")
? static_cast<void> (0) : __assert_fail ("loBits <= BitWidth && \"More bits than bitwidth\""
, "/build/llvm-toolchain-snapshot-10~svn372204/include/llvm/ADT/APInt.h"
, 1472, __PRETTY_FUNCTION__))
;
1473 APInt Keep = getHighBitsSet(BitWidth, BitWidth - loBits);
1474 *this &= Keep;
1475 }
1476
1477 /// Set the sign bit to 0.
1478 void clearSignBit() {
1479 clearBit(BitWidth - 1);
1480 }
1481
1482 /// Toggle every bit to its opposite value.
1483 void flipAllBits() {
1484 if (isSingleWord()) {
1485 U.VAL ^= WORDTYPE_MAX;
1486 clearUnusedBits();
1487 } else {
1488 flipAllBitsSlowCase();
1489 }
1490 }
1491
1492 /// Toggles a given bit to its opposite value.
1493 ///
1494 /// Toggle a given bit to its opposite value whose position is given
1495 /// as "bitPosition".
1496 void flipBit(unsigned bitPosition);
1497
1498 /// Negate this APInt in place.
1499 void negate() {
1500 flipAllBits();
1501 ++(*this);
1502 }
1503
1504 /// Insert the bits from a smaller APInt starting at bitPosition.
1505 void insertBits(const APInt &SubBits, unsigned bitPosition);
1506
1507 /// Return an APInt with the extracted bits [bitPosition,bitPosition+numBits).
1508 APInt extractBits(unsigned numBits, unsigned bitPosition) const;
1509
1510 /// @}
1511 /// \name Value Characterization Functions
1512 /// @{
1513
1514 /// Return the number of bits in the APInt.
1515 unsigned getBitWidth() const { return BitWidth; }
1516
1517 /// Get the number of words.
1518 ///
1519 /// Here one word's bitwidth equals to that of uint64_t.
1520 ///
1521 /// \returns the number of words to hold the integer value of this APInt.
1522 unsigned getNumWords() const { return getNumWords(BitWidth); }
1523
1524 /// Get the number of words.
1525 ///
1526 /// *NOTE* Here one word's bitwidth equals to that of uint64_t.
1527 ///
1528 /// \returns the number of words to hold the integer value with a given bit
1529 /// width.
1530 static unsigned getNumWords(unsigned BitWidth) {
1531 return ((uint64_t)BitWidth + APINT_BITS_PER_WORD - 1) / APINT_BITS_PER_WORD;
1532 }
1533
1534 /// Compute the number of active bits in the value
1535 ///
1536 /// This function returns the number of active bits which is defined as the
1537 /// bit width minus the number of leading zeros. This is used in several
1538 /// computations to see how "wide" the value is.
1539 unsigned getActiveBits() const { return BitWidth - countLeadingZeros(); }
1540
1541 /// Compute the number of active words in the value of this APInt.
1542 ///
1543 /// This is used in conjunction with getActiveData to extract the raw value of
1544 /// the APInt.
1545 unsigned getActiveWords() const {
1546 unsigned numActiveBits = getActiveBits();
1547 return numActiveBits ? whichWord(numActiveBits - 1) + 1 : 1;
1548 }
1549
1550 /// Get the minimum bit size for this signed APInt
1551 ///
1552 /// Computes the minimum bit width for this APInt while considering it to be a
1553 /// signed (and probably negative) value. If the value is not negative, this
1554 /// function returns the same value as getActiveBits()+1. Otherwise, it
1555 /// returns the smallest bit width that will retain the negative value. For
1556 /// example, -1 can be written as 0b1 or 0xFFFFFFFFFF. 0b1 is shorter and so
1557 /// for -1, this function will always return 1.
1558 unsigned getMinSignedBits() const {
1559 if (isNegative())
1560 return BitWidth - countLeadingOnes() + 1;
1561 return getActiveBits() + 1;
1562 }
1563
1564 /// Get zero extended value
1565 ///
1566 /// This method attempts to return the value of this APInt as a zero extended
1567 /// uint64_t. The bitwidth must be <= 64 or the value must fit within a
1568 /// uint64_t. Otherwise an assertion will result.
1569 uint64_t getZExtValue() const {
1570 if (isSingleWord())
21
Taking false branch
1571 return U.VAL;
1572 assert(getActiveBits() <= 64 && "Too many bits for uint64_t")((getActiveBits() <= 64 && "Too many bits for uint64_t"
) ? static_cast<void> (0) : __assert_fail ("getActiveBits() <= 64 && \"Too many bits for uint64_t\""
, "/build/llvm-toolchain-snapshot-10~svn372204/include/llvm/ADT/APInt.h"
, 1572, __PRETTY_FUNCTION__))
;
22
Assuming the condition is true
23
'?' condition is true
1573 return U.pVal[0];
24
Use of memory after it is freed
1574 }
1575
1576 /// Get sign extended value
1577 ///
1578 /// This method attempts to return the value of this APInt as a sign extended
1579 /// int64_t. The bit width must be <= 64 or the value must fit within an
1580 /// int64_t. Otherwise an assertion will result.
1581 int64_t getSExtValue() const {
1582 if (isSingleWord())
1583 return SignExtend64(U.VAL, BitWidth);
1584 assert(getMinSignedBits() <= 64 && "Too many bits for int64_t")((getMinSignedBits() <= 64 && "Too many bits for int64_t"
) ? static_cast<void> (0) : __assert_fail ("getMinSignedBits() <= 64 && \"Too many bits for int64_t\""
, "/build/llvm-toolchain-snapshot-10~svn372204/include/llvm/ADT/APInt.h"
, 1584, __PRETTY_FUNCTION__))
;
1585 return int64_t(U.pVal[0]);
1586 }
1587
1588 /// Get bits required for string value.
1589 ///
1590 /// This method determines how many bits are required to hold the APInt
1591 /// equivalent of the string given by \p str.
1592 static unsigned getBitsNeeded(StringRef str, uint8_t radix);
1593
1594 /// The APInt version of the countLeadingZeros functions in
1595 /// MathExtras.h.
1596 ///
1597 /// It counts the number of zeros from the most significant bit to the first
1598 /// one bit.
1599 ///
1600 /// \returns BitWidth if the value is zero, otherwise returns the number of
1601 /// zeros from the most significant bit to the first one bits.
1602 unsigned countLeadingZeros() const {
1603 if (isSingleWord()) {
1604 unsigned unusedBits = APINT_BITS_PER_WORD - BitWidth;
1605 return llvm::countLeadingZeros(U.VAL) - unusedBits;
1606 }
1607 return countLeadingZerosSlowCase();
1608 }
1609
1610 /// Count the number of leading one bits.
1611 ///
1612 /// This function is an APInt version of the countLeadingOnes
1613 /// functions in MathExtras.h. It counts the number of ones from the most
1614 /// significant bit to the first zero bit.
1615 ///
1616 /// \returns 0 if the high order bit is not set, otherwise returns the number
1617 /// of 1 bits from the most significant to the least
1618 unsigned countLeadingOnes() const {
1619 if (isSingleWord())
1620 return llvm::countLeadingOnes(U.VAL << (APINT_BITS_PER_WORD - BitWidth));
1621 return countLeadingOnesSlowCase();
1622 }
1623
1624 /// Computes the number of leading bits of this APInt that are equal to its
1625 /// sign bit.
1626 unsigned getNumSignBits() const {
1627 return isNegative() ? countLeadingOnes() : countLeadingZeros();
1628 }
1629
1630 /// Count the number of trailing zero bits.
1631 ///
1632 /// This function is an APInt version of the countTrailingZeros
1633 /// functions in MathExtras.h. It counts the number of zeros from the least
1634 /// significant bit to the first set bit.
1635 ///
1636 /// \returns BitWidth if the value is zero, otherwise returns the number of
1637 /// zeros from the least significant bit to the first one bit.
1638 unsigned countTrailingZeros() const {
1639 if (isSingleWord())
1640 return std::min(unsigned(llvm::countTrailingZeros(U.VAL)), BitWidth);
1641 return countTrailingZerosSlowCase();
1642 }
1643
1644 /// Count the number of trailing one bits.
1645 ///
1646 /// This function is an APInt version of the countTrailingOnes
1647 /// functions in MathExtras.h. It counts the number of ones from the least
1648 /// significant bit to the first zero bit.
1649 ///
1650 /// \returns BitWidth if the value is all ones, otherwise returns the number
1651 /// of ones from the least significant bit to the first zero bit.
1652 unsigned countTrailingOnes() const {
1653 if (isSingleWord())
1654 return llvm::countTrailingOnes(U.VAL);
1655 return countTrailingOnesSlowCase();
1656 }
1657
1658 /// Count the number of bits set.
1659 ///
1660 /// This function is an APInt version of the countPopulation functions
1661 /// in MathExtras.h. It counts the number of 1 bits in the APInt value.
1662 ///
1663 /// \returns 0 if the value is zero, otherwise returns the number of set bits.
1664 unsigned countPopulation() const {
1665 if (isSingleWord())
1666 return llvm::countPopulation(U.VAL);
1667 return countPopulationSlowCase();
1668 }
1669
1670 /// @}
1671 /// \name Conversion Functions
1672 /// @{
1673 void print(raw_ostream &OS, bool isSigned) const;
1674
1675 /// Converts an APInt to a string and append it to Str. Str is commonly a
1676 /// SmallString.
1677 void toString(SmallVectorImpl<char> &Str, unsigned Radix, bool Signed,
1678 bool formatAsCLiteral = false) const;
1679
1680 /// Considers the APInt to be unsigned and converts it into a string in the
1681 /// radix given. The radix can be 2, 8, 10 16, or 36.
1682 void toStringUnsigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const {
1683 toString(Str, Radix, false, false);
1684 }
1685
1686 /// Considers the APInt to be signed and converts it into a string in the
1687 /// radix given. The radix can be 2, 8, 10, 16, or 36.
1688 void toStringSigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const {
1689 toString(Str, Radix, true, false);
1690 }
1691
1692 /// Return the APInt as a std::string.
1693 ///
1694 /// Note that this is an inefficient method. It is better to pass in a
1695 /// SmallVector/SmallString to the methods above to avoid thrashing the heap
1696 /// for the string.
1697 std::string toString(unsigned Radix, bool Signed) const;
1698
1699 /// \returns a byte-swapped representation of this APInt Value.
1700 APInt byteSwap() const;
1701
1702 /// \returns the value with the bit representation reversed of this APInt
1703 /// Value.
1704 APInt reverseBits() const;
1705
1706 /// Converts this APInt to a double value.
1707 double roundToDouble(bool isSigned) const;
1708
1709 /// Converts this unsigned APInt to a double value.
1710 double roundToDouble() const { return roundToDouble(false); }
1711
1712 /// Converts this signed APInt to a double value.
1713 double signedRoundToDouble() const { return roundToDouble(true); }
1714
1715 /// Converts APInt bits to a double
1716 ///
1717 /// The conversion does not do a translation from integer to double, it just
1718 /// re-interprets the bits as a double. Note that it is valid to do this on
1719 /// any bit width. Exactly 64 bits will be translated.
1720 double bitsToDouble() const {
1721 return BitsToDouble(getWord(0));
1722 }
1723
1724 /// Converts APInt bits to a double
1725 ///
1726 /// The conversion does not do a translation from integer to float, it just
1727 /// re-interprets the bits as a float. Note that it is valid to do this on
1728 /// any bit width. Exactly 32 bits will be translated.
1729 float bitsToFloat() const {
1730 return BitsToFloat(getWord(0));
1731 }
1732
1733 /// Converts a double to APInt bits.
1734 ///
1735 /// The conversion does not do a translation from double to integer, it just
1736 /// re-interprets the bits of the double.
1737 static APInt doubleToBits(double V) {
1738 return APInt(sizeof(double) * CHAR_BIT8, DoubleToBits(V));
1739 }
1740
1741 /// Converts a float to APInt bits.
1742 ///
1743 /// The conversion does not do a translation from float to integer, it just
1744 /// re-interprets the bits of the float.
1745 static APInt floatToBits(float V) {
1746 return APInt(sizeof(float) * CHAR_BIT8, FloatToBits(V));
1747 }
1748
1749 /// @}
1750 /// \name Mathematics Operations
1751 /// @{
1752
1753 /// \returns the floor log base 2 of this APInt.
1754 unsigned logBase2() const { return getActiveBits() - 1; }
1755
1756 /// \returns the ceil log base 2 of this APInt.
1757 unsigned ceilLogBase2() const {
1758 APInt temp(*this);
1759 --temp;
1760 return temp.getActiveBits();
1761 }
1762
1763 /// \returns the nearest log base 2 of this APInt. Ties round up.
1764 ///
1765 /// NOTE: When we have a BitWidth of 1, we define:
1766 ///
1767 /// log2(0) = UINT32_MAX
1768 /// log2(1) = 0
1769 ///
1770 /// to get around any mathematical concerns resulting from
1771 /// referencing 2 in a space where 2 does no exist.
1772 unsigned nearestLogBase2() const {
1773 // Special case when we have a bitwidth of 1. If VAL is 1, then we
1774 // get 0. If VAL is 0, we get WORDTYPE_MAX which gets truncated to
1775 // UINT32_MAX.
1776 if (BitWidth == 1)
1777 return U.VAL - 1;
1778
1779 // Handle the zero case.
1780 if (isNullValue())
1781 return UINT32_MAX(4294967295U);
1782
1783 // The non-zero case is handled by computing:
1784 //
1785 // nearestLogBase2(x) = logBase2(x) + x[logBase2(x)-1].
1786 //
1787 // where x[i] is referring to the value of the ith bit of x.
1788 unsigned lg = logBase2();
1789 return lg + unsigned((*this)[lg - 1]);
1790 }
1791
1792 /// \returns the log base 2 of this APInt if its an exact power of two, -1
1793 /// otherwise
1794 int32_t exactLogBase2() const {
1795 if (!isPowerOf2())
1796 return -1;
1797 return logBase2();
1798 }
1799
1800 /// Compute the square root
1801 APInt sqrt() const;
1802
1803 /// Get the absolute value;
1804 ///
1805 /// If *this is < 0 then return -(*this), otherwise *this;
1806 APInt abs() const {
1807 if (isNegative())
1808 return -(*this);
1809 return *this;
1810 }
1811
1812 /// \returns the multiplicative inverse for a given modulo.
1813 APInt multiplicativeInverse(const APInt &modulo) const;
1814
1815 /// @}
1816 /// \name Support for division by constant
1817 /// @{
1818
1819 /// Calculate the magic number for signed division by a constant.
1820 struct ms;
1821 ms magic() const;
1822
1823 /// Calculate the magic number for unsigned division by a constant.
1824 struct mu;
1825 mu magicu(unsigned LeadingZeros = 0) const;
1826
1827 /// @}
1828 /// \name Building-block Operations for APInt and APFloat
1829 /// @{
1830
1831 // These building block operations operate on a representation of arbitrary
1832 // precision, two's-complement, bignum integer values. They should be
1833 // sufficient to implement APInt and APFloat bignum requirements. Inputs are
1834 // generally a pointer to the base of an array of integer parts, representing
1835 // an unsigned bignum, and a count of how many parts there are.
1836
1837 /// Sets the least significant part of a bignum to the input value, and zeroes
1838 /// out higher parts.
1839 static void tcSet(WordType *, WordType, unsigned);
1840
1841 /// Assign one bignum to another.
1842 static void tcAssign(WordType *, const WordType *, unsigned);
1843
1844 /// Returns true if a bignum is zero, false otherwise.
1845 static bool tcIsZero(const WordType *, unsigned);
1846
1847 /// Extract the given bit of a bignum; returns 0 or 1. Zero-based.
1848 static int tcExtractBit(const WordType *, unsigned bit);
1849
1850 /// Copy the bit vector of width srcBITS from SRC, starting at bit srcLSB, to
1851 /// DST, of dstCOUNT parts, such that the bit srcLSB becomes the least
1852 /// significant bit of DST. All high bits above srcBITS in DST are
1853 /// zero-filled.
1854 static void tcExtract(WordType *, unsigned dstCount,
1855 const WordType *, unsigned srcBits,
1856 unsigned srcLSB);
1857
1858 /// Set the given bit of a bignum. Zero-based.
1859 static void tcSetBit(WordType *, unsigned bit);
1860
1861 /// Clear the given bit of a bignum. Zero-based.
1862 static void tcClearBit(WordType *, unsigned bit);
1863
1864 /// Returns the bit number of the least or most significant set bit of a
1865 /// number. If the input number has no bits set -1U is returned.
1866 static unsigned tcLSB(const WordType *, unsigned n);
1867 static unsigned tcMSB(const WordType *parts, unsigned n);
1868
1869 /// Negate a bignum in-place.
1870 static void tcNegate(WordType *, unsigned);
1871
1872 /// DST += RHS + CARRY where CARRY is zero or one. Returns the carry flag.
1873 static WordType tcAdd(WordType *, const WordType *,
1874 WordType carry, unsigned);
1875 /// DST += RHS. Returns the carry flag.
1876 static WordType tcAddPart(WordType *, WordType, unsigned);
1877
1878 /// DST -= RHS + CARRY where CARRY is zero or one. Returns the carry flag.
1879 static WordType tcSubtract(WordType *, const WordType *,
1880 WordType carry, unsigned);
1881 /// DST -= RHS. Returns the carry flag.
1882 static WordType tcSubtractPart(WordType *, WordType, unsigned);
1883
1884 /// DST += SRC * MULTIPLIER + PART if add is true
1885 /// DST = SRC * MULTIPLIER + PART if add is false
1886 ///
1887 /// Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC they must
1888 /// start at the same point, i.e. DST == SRC.
1889 ///
1890 /// If DSTPARTS == SRC_PARTS + 1 no overflow occurs and zero is returned.
1891 /// Otherwise DST is filled with the least significant DSTPARTS parts of the
1892 /// result, and if all of the omitted higher parts were zero return zero,
1893 /// otherwise overflow occurred and return one.
1894 static int tcMultiplyPart(WordType *dst, const WordType *src,
1895 WordType multiplier, WordType carry,
1896 unsigned srcParts, unsigned dstParts,
1897 bool add);
1898
1899 /// DST = LHS * RHS, where DST has the same width as the operands and is
1900 /// filled with the least significant parts of the result. Returns one if
1901 /// overflow occurred, otherwise zero. DST must be disjoint from both
1902 /// operands.
1903 static int tcMultiply(WordType *, const WordType *, const WordType *,
1904 unsigned);
1905
1906 /// DST = LHS * RHS, where DST has width the sum of the widths of the
1907 /// operands. No overflow occurs. DST must be disjoint from both operands.
1908 static void tcFullMultiply(WordType *, const WordType *,
1909 const WordType *, unsigned, unsigned);
1910
1911 /// If RHS is zero LHS and REMAINDER are left unchanged, return one.
1912 /// Otherwise set LHS to LHS / RHS with the fractional part discarded, set
1913 /// REMAINDER to the remainder, return zero. i.e.
1914 ///
1915 /// OLD_LHS = RHS * LHS + REMAINDER
1916 ///
1917 /// SCRATCH is a bignum of the same size as the operands and result for use by
1918 /// the routine; its contents need not be initialized and are destroyed. LHS,
1919 /// REMAINDER and SCRATCH must be distinct.
1920 static int tcDivide(WordType *lhs, const WordType *rhs,
1921 WordType *remainder, WordType *scratch,
1922 unsigned parts);
1923
1924 /// Shift a bignum left Count bits. Shifted in bits are zero. There are no
1925 /// restrictions on Count.
1926 static void tcShiftLeft(WordType *, unsigned Words, unsigned Count);
1927
1928 /// Shift a bignum right Count bits. Shifted in bits are zero. There are no
1929 /// restrictions on Count.
1930 static void tcShiftRight(WordType *, unsigned Words, unsigned Count);
1931
1932 /// The obvious AND, OR and XOR and complement operations.
1933 static void tcAnd(WordType *, const WordType *, unsigned);
1934 static void tcOr(WordType *, const WordType *, unsigned);
1935 static void tcXor(WordType *, const WordType *, unsigned);
1936 static void tcComplement(WordType *, unsigned);
1937
1938 /// Comparison (unsigned) of two bignums.
1939 static int tcCompare(const WordType *, const WordType *, unsigned);
1940
1941 /// Increment a bignum in-place. Return the carry flag.
1942 static WordType tcIncrement(WordType *dst, unsigned parts) {
1943 return tcAddPart(dst, 1, parts);
1944 }
1945
1946 /// Decrement a bignum in-place. Return the borrow flag.
1947 static WordType tcDecrement(WordType *dst, unsigned parts) {
1948 return tcSubtractPart(dst, 1, parts);
1949 }
1950
1951 /// Set the least significant BITS and clear the rest.
1952 static void tcSetLeastSignificantBits(WordType *, unsigned, unsigned bits);
1953
1954 /// debug method
1955 void dump() const;
1956
1957 /// @}
1958};
1959
1960/// Magic data for optimising signed division by a constant.
1961struct APInt::ms {
1962 APInt m; ///< magic number
1963 unsigned s; ///< shift amount
1964};
1965
1966/// Magic data for optimising unsigned division by a constant.
1967struct APInt::mu {
1968 APInt m; ///< magic number
1969 bool a; ///< add indicator
1970 unsigned s; ///< shift amount
1971};
1972
1973inline bool operator==(uint64_t V1, const APInt &V2) { return V2 == V1; }
1974
1975inline bool operator!=(uint64_t V1, const APInt &V2) { return V2 != V1; }
1976
1977/// Unary bitwise complement operator.
1978///
1979/// \returns an APInt that is the bitwise complement of \p v.
1980inline APInt operator~(APInt v) {
1981 v.flipAllBits();
1982 return v;
1983}
1984
1985inline APInt operator&(APInt a, const APInt &b) {
1986 a &= b;
1987 return a;
1988}
1989
1990inline APInt operator&(const APInt &a, APInt &&b) {
1991 b &= a;
1992 return std::move(b);
1993}
1994
1995inline APInt operator&(APInt a, uint64_t RHS) {
1996 a &= RHS;
1997 return a;
1998}
1999
2000inline APInt operator&(uint64_t LHS, APInt b) {
2001 b &= LHS;
2002 return b;
2003}
2004
2005inline APInt operator|(APInt a, const APInt &b) {
2006 a |= b;
2007 return a;
2008}
2009
2010inline APInt operator|(const APInt &a, APInt &&b) {
2011 b |= a;
2012 return std::move(b);
2013}
2014
2015inline APInt operator|(APInt a, uint64_t RHS) {
2016 a |= RHS;
2017 return a;
2018}
2019
2020inline APInt operator|(uint64_t LHS, APInt b) {
2021 b |= LHS;
2022 return b;
2023}
2024
2025inline APInt operator^(APInt a, const APInt &b) {
2026 a ^= b;
2027 return a;
2028}
2029
2030inline APInt operator^(const APInt &a, APInt &&b) {
2031 b ^= a;
2032 return std::move(b);
2033}
2034
2035inline APInt operator^(APInt a, uint64_t RHS) {
2036 a ^= RHS;
2037 return a;
2038}
2039
2040inline APInt operator^(uint64_t LHS, APInt b) {
2041 b ^= LHS;
2042 return b;
2043}
2044
2045inline raw_ostream &operator<<(raw_ostream &OS, const APInt &I) {
2046 I.print(OS, true);
2047 return OS;
2048}
2049
2050inline APInt operator-(APInt v) {
2051 v.negate();
2052 return v;
2053}
2054
2055inline APInt operator+(APInt a, const APInt &b) {
2056 a += b;
2057 return a;
2058}
2059
2060inline APInt operator+(const APInt &a, APInt &&b) {
2061 b += a;
2062 return std::move(b);
2063}
2064
2065inline APInt operator+(APInt a, uint64_t RHS) {
2066 a += RHS;
2067 return a;
2068}
2069
2070inline APInt operator+(uint64_t LHS, APInt b) {
2071 b += LHS;
2072 return b;
2073}
2074
2075inline APInt operator-(APInt a, const APInt &b) {
2076 a -= b;
2077 return a;
2078}
2079
2080inline APInt operator-(const APInt &a, APInt &&b) {
2081 b.negate();
2082 b += a;
2083 return std::move(b);
2084}
2085
2086inline APInt operator-(APInt a, uint64_t RHS) {
2087 a -= RHS;
2088 return a;
2089}
2090
2091inline APInt operator-(uint64_t LHS, APInt b) {
2092 b.negate();
2093 b += LHS;
2094 return b;
2095}
2096
2097inline APInt operator*(APInt a, uint64_t RHS) {
2098 a *= RHS;
2099 return a;
2100}
2101
2102inline APInt operator*(uint64_t LHS, APInt b) {
2103 b *= LHS;
2104 return b;
2105}
2106
2107
2108namespace APIntOps {
2109
2110/// Determine the smaller of two APInts considered to be signed.
2111inline const APInt &smin(const APInt &A, const APInt &B) {
2112 return A.slt(B) ? A : B;
2113}
2114
2115/// Determine the larger of two APInts considered to be signed.
2116inline const APInt &smax(const APInt &A, const APInt &B) {
2117 return A.sgt(B) ? A : B;
2118}
2119
2120/// Determine the smaller of two APInts considered to be signed.
2121inline const APInt &umin(const APInt &A, const APInt &B) {
2122 return A.ult(B) ? A : B;
2123}
2124
2125/// Determine the larger of two APInts considered to be unsigned.
2126inline const APInt &umax(const APInt &A, const APInt &B) {
2127 return A.ugt(B) ? A : B;
2128}
2129
2130/// Compute GCD of two unsigned APInt values.
2131///
2132/// This function returns the greatest common divisor of the two APInt values
2133/// using Stein's algorithm.
2134///
2135/// \returns the greatest common divisor of A and B.
2136APInt GreatestCommonDivisor(APInt A, APInt B);
2137
2138/// Converts the given APInt to a double value.
2139///
2140/// Treats the APInt as an unsigned value for conversion purposes.
2141inline double RoundAPIntToDouble(const APInt &APIVal) {
2142 return APIVal.roundToDouble();
2143}
2144
2145/// Converts the given APInt to a double value.
2146///
2147/// Treats the APInt as a signed value for conversion purposes.
2148inline double RoundSignedAPIntToDouble(const APInt &APIVal) {
2149 return APIVal.signedRoundToDouble();
2150}
2151
2152/// Converts the given APInt to a float vlalue.
2153inline float RoundAPIntToFloat(const APInt &APIVal) {
2154 return float(RoundAPIntToDouble(APIVal));
2155}
2156
2157/// Converts the given APInt to a float value.
2158///
2159/// Treast the APInt as a signed value for conversion purposes.
2160inline float RoundSignedAPIntToFloat(const APInt &APIVal) {
2161 return float(APIVal.signedRoundToDouble());
2162}
2163
2164/// Converts the given double value into a APInt.
2165///
2166/// This function convert a double value to an APInt value.
2167APInt RoundDoubleToAPInt(double Double, unsigned width);
2168
2169/// Converts a float value into a APInt.
2170///
2171/// Converts a float value into an APInt value.
2172inline APInt RoundFloatToAPInt(float Float, unsigned width) {
2173 return RoundDoubleToAPInt(double(Float), width);
2174}
2175
2176/// Return A unsign-divided by B, rounded by the given rounding mode.
2177APInt RoundingUDiv(const APInt &A, const APInt &B, APInt::Rounding RM);
2178
2179/// Return A sign-divided by B, rounded by the given rounding mode.
2180APInt RoundingSDiv(const APInt &A, const APInt &B, APInt::Rounding RM);
2181
2182/// Let q(n) = An^2 + Bn + C, and BW = bit width of the value range
2183/// (e.g. 32 for i32).
2184/// This function finds the smallest number n, such that
2185/// (a) n >= 0 and q(n) = 0, or
2186/// (b) n >= 1 and q(n-1) and q(n), when evaluated in the set of all
2187/// integers, belong to two different intervals [Rk, Rk+R),
2188/// where R = 2^BW, and k is an integer.
2189/// The idea here is to find when q(n) "overflows" 2^BW, while at the
2190/// same time "allowing" subtraction. In unsigned modulo arithmetic a
2191/// subtraction (treated as addition of negated numbers) would always
2192/// count as an overflow, but here we want to allow values to decrease
2193/// and increase as long as they are within the same interval.
2194/// Specifically, adding of two negative numbers should not cause an
2195/// overflow (as long as the magnitude does not exceed the bith width).
2196/// On the other hand, given a positive number, adding a negative
2197/// number to it can give a negative result, which would cause the
2198/// value to go from [-2^BW, 0) to [0, 2^BW). In that sense, zero is
2199/// treated as a special case of an overflow.
2200///
2201/// This function returns None if after finding k that minimizes the
2202/// positive solution to q(n) = kR, both solutions are contained between
2203/// two consecutive integers.
2204///
2205/// There are cases where q(n) > T, and q(n+1) < T (assuming evaluation
2206/// in arithmetic modulo 2^BW, and treating the values as signed) by the
2207/// virtue of *signed* overflow. This function will *not* find such an n,
2208/// however it may find a value of n satisfying the inequalities due to
2209/// an *unsigned* overflow (if the values are treated as unsigned).
2210/// To find a solution for a signed overflow, treat it as a problem of
2211/// finding an unsigned overflow with a range with of BW-1.
2212///
2213/// The returned value may have a different bit width from the input
2214/// coefficients.
2215Optional<APInt> SolveQuadraticEquationWrap(APInt A, APInt B, APInt C,
2216 unsigned RangeWidth);
2217} // End of APIntOps namespace
2218
2219// See friend declaration above. This additional declaration is required in
2220// order to compile LLVM with IBM xlC compiler.
2221hash_code hash_value(const APInt &Arg);
2222
2223/// StoreIntToMemory - Fills the StoreBytes bytes of memory starting from Dst
2224/// with the integer held in IntVal.
2225void StoreIntToMemory(const APInt &IntVal, uint8_t *Dst, unsigned StoreBytes);
2226
2227/// LoadIntFromMemory - Loads the integer stored in the LoadBytes bytes starting
2228/// from Src into IntVal, which is assumed to be wide enough and to hold zero.
2229void LoadIntFromMemory(APInt &IntVal, uint8_t *Src, unsigned LoadBytes);
2230
2231} // namespace llvm
2232
2233#endif