Bug Summary

File:build/source/llvm/lib/Support/APInt.cpp
Warning:line 1433, column 22
The result of the right shift is undefined due to shifting by '32', which is greater or equal to the width of type 'uint32_t'

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name APInt.cpp -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 -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/source/build-llvm -resource-dir /usr/lib/llvm-16/lib/clang/16.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I lib/Support -I /build/source/llvm/lib/Support -I include -I /build/source/llvm/include -D _FORTIFY_SOURCE=2 -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-16/lib/clang/16.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -fmacro-prefix-map=/build/source/build-llvm=build-llvm -fmacro-prefix-map=/build/source/= -fcoverage-prefix-map=/build/source/build-llvm=build-llvm -fcoverage-prefix-map=/build/source/= -source-date-epoch 1668078801 -O3 -Wno-unused-command-line-argument -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -Wno-misleading-indentation -std=c++17 -fdeprecated-macro -fdebug-compilation-dir=/build/source/build-llvm -fdebug-prefix-map=/build/source/build-llvm=build-llvm -fdebug-prefix-map=/build/source/= -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcolor-diagnostics -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2022-11-10-135928-647445-1 -x c++ /build/source/llvm/lib/Support/APInt.cpp

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

/build/source/llvm/include/llvm/Support/MathExtras.h

1//===-- llvm/Support/MathExtras.h - Useful math functions -------*- 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// This file contains some functions that are useful for math stuff.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_SUPPORT_MATHEXTRAS_H
14#define LLVM_SUPPORT_MATHEXTRAS_H
15
16#include "llvm/ADT/bit.h"
17#include "llvm/Support/Compiler.h"
18#include <cassert>
19#include <climits>
20#include <cstdint>
21#include <cstring>
22#include <limits>
23#include <type_traits>
24
25#ifdef _MSC_VER
26// Declare these intrinsics manually rather including intrin.h. It's very
27// expensive, and MathExtras.h is popular.
28// #include <intrin.h>
29extern "C" {
30unsigned char _BitScanForward(unsigned long *_Index, unsigned long _Mask);
31unsigned char _BitScanForward64(unsigned long *_Index, unsigned __int64 _Mask);
32unsigned char _BitScanReverse(unsigned long *_Index, unsigned long _Mask);
33unsigned char _BitScanReverse64(unsigned long *_Index, unsigned __int64 _Mask);
34}
35#endif
36
37namespace llvm {
38
39/// The behavior an operation has on an input of 0.
40enum ZeroBehavior {
41 /// The returned value is undefined.
42 ZB_Undefined,
43 /// The returned value is numeric_limits<T>::max()
44 ZB_Max,
45 /// The returned value is numeric_limits<T>::digits
46 ZB_Width
47};
48
49/// Mathematical constants.
50namespace numbers {
51// TODO: Track C++20 std::numbers.
52// TODO: Favor using the hexadecimal FP constants (requires C++17).
53constexpr double e = 2.7182818284590452354, // (0x1.5bf0a8b145749P+1) https://oeis.org/A001113
54 egamma = .57721566490153286061, // (0x1.2788cfc6fb619P-1) https://oeis.org/A001620
55 ln2 = .69314718055994530942, // (0x1.62e42fefa39efP-1) https://oeis.org/A002162
56 ln10 = 2.3025850929940456840, // (0x1.24bb1bbb55516P+1) https://oeis.org/A002392
57 log2e = 1.4426950408889634074, // (0x1.71547652b82feP+0)
58 log10e = .43429448190325182765, // (0x1.bcb7b1526e50eP-2)
59 pi = 3.1415926535897932385, // (0x1.921fb54442d18P+1) https://oeis.org/A000796
60 inv_pi = .31830988618379067154, // (0x1.45f306bc9c883P-2) https://oeis.org/A049541
61 sqrtpi = 1.7724538509055160273, // (0x1.c5bf891b4ef6bP+0) https://oeis.org/A002161
62 inv_sqrtpi = .56418958354775628695, // (0x1.20dd750429b6dP-1) https://oeis.org/A087197
63 sqrt2 = 1.4142135623730950488, // (0x1.6a09e667f3bcdP+0) https://oeis.org/A00219
64 inv_sqrt2 = .70710678118654752440, // (0x1.6a09e667f3bcdP-1)
65 sqrt3 = 1.7320508075688772935, // (0x1.bb67ae8584caaP+0) https://oeis.org/A002194
66 inv_sqrt3 = .57735026918962576451, // (0x1.279a74590331cP-1)
67 phi = 1.6180339887498948482; // (0x1.9e3779b97f4a8P+0) https://oeis.org/A001622
68constexpr float ef = 2.71828183F, // (0x1.5bf0a8P+1) https://oeis.org/A001113
69 egammaf = .577215665F, // (0x1.2788d0P-1) https://oeis.org/A001620
70 ln2f = .693147181F, // (0x1.62e430P-1) https://oeis.org/A002162
71 ln10f = 2.30258509F, // (0x1.26bb1cP+1) https://oeis.org/A002392
72 log2ef = 1.44269504F, // (0x1.715476P+0)
73 log10ef = .434294482F, // (0x1.bcb7b2P-2)
74 pif = 3.14159265F, // (0x1.921fb6P+1) https://oeis.org/A000796
75 inv_pif = .318309886F, // (0x1.45f306P-2) https://oeis.org/A049541
76 sqrtpif = 1.77245385F, // (0x1.c5bf8aP+0) https://oeis.org/A002161
77 inv_sqrtpif = .564189584F, // (0x1.20dd76P-1) https://oeis.org/A087197
78 sqrt2f = 1.41421356F, // (0x1.6a09e6P+0) https://oeis.org/A002193
79 inv_sqrt2f = .707106781F, // (0x1.6a09e6P-1)
80 sqrt3f = 1.73205081F, // (0x1.bb67aeP+0) https://oeis.org/A002194
81 inv_sqrt3f = .577350269F, // (0x1.279a74P-1)
82 phif = 1.61803399F; // (0x1.9e377aP+0) https://oeis.org/A001622
83} // namespace numbers
84
85namespace detail {
86template <typename T, std::size_t SizeOfT> struct TrailingZerosCounter {
87 static unsigned count(T Val, ZeroBehavior) {
88 if (!Val)
89 return std::numeric_limits<T>::digits;
90 if (Val & 0x1)
91 return 0;
92
93 // Bisection method.
94 unsigned ZeroBits = 0;
95 T Shift = std::numeric_limits<T>::digits >> 1;
96 T Mask = std::numeric_limits<T>::max() >> Shift;
97 while (Shift) {
98 if ((Val & Mask) == 0) {
99 Val >>= Shift;
100 ZeroBits |= Shift;
101 }
102 Shift >>= 1;
103 Mask >>= Shift;
104 }
105 return ZeroBits;
106 }
107};
108
109#if defined(__GNUC__4) || defined(_MSC_VER)
110template <typename T> struct TrailingZerosCounter<T, 4> {
111 static unsigned count(T Val, ZeroBehavior ZB) {
112 if (ZB != ZB_Undefined && Val == 0)
113 return 32;
114
115#if __has_builtin(__builtin_ctz)1 || defined(__GNUC__4)
116 return __builtin_ctz(Val);
117#elif defined(_MSC_VER)
118 unsigned long Index;
119 _BitScanForward(&Index, Val);
120 return Index;
121#endif
122 }
123};
124
125#if !defined(_MSC_VER) || defined(_M_X64)
126template <typename T> struct TrailingZerosCounter<T, 8> {
127 static unsigned count(T Val, ZeroBehavior ZB) {
128 if (ZB != ZB_Undefined && Val == 0)
129 return 64;
130
131#if __has_builtin(__builtin_ctzll)1 || defined(__GNUC__4)
132 return __builtin_ctzll(Val);
133#elif defined(_MSC_VER)
134 unsigned long Index;
135 _BitScanForward64(&Index, Val);
136 return Index;
137#endif
138 }
139};
140#endif
141#endif
142} // namespace detail
143
144/// Count number of 0's from the least significant bit to the most
145/// stopping at the first 1.
146///
147/// Only unsigned integral types are allowed.
148///
149/// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are
150/// valid arguments.
151template <typename T>
152unsigned countTrailingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
153 static_assert(std::is_unsigned_v<T>,
154 "Only unsigned integral types are allowed.");
155 return llvm::detail::TrailingZerosCounter<T, sizeof(T)>::count(Val, ZB);
156}
157
158namespace detail {
159template <typename T, std::size_t SizeOfT> struct LeadingZerosCounter {
160 static unsigned count(T Val, ZeroBehavior) {
161 if (!Val)
162 return std::numeric_limits<T>::digits;
163
164 // Bisection method.
165 unsigned ZeroBits = 0;
166 for (T Shift = std::numeric_limits<T>::digits >> 1; Shift; Shift >>= 1) {
167 T Tmp = Val >> Shift;
168 if (Tmp)
169 Val = Tmp;
170 else
171 ZeroBits |= Shift;
172 }
173 return ZeroBits;
174 }
175};
176
177#if defined(__GNUC__4) || defined(_MSC_VER)
178template <typename T> struct LeadingZerosCounter<T, 4> {
179 static unsigned count(T Val, ZeroBehavior ZB) {
180 if (ZB
20.1
'ZB' is not equal to ZB_Undefined
20.1
'ZB' is not equal to ZB_Undefined
!= ZB_Undefined && Val == 0)
21
Assuming 'Val' is equal to 0
22
Taking true branch
181 return 32;
23
Returning the value 32, which participates in a condition later
24
Returning the value 32
182
183#if __has_builtin(__builtin_clz)1 || defined(__GNUC__4)
184 return __builtin_clz(Val);
185#elif defined(_MSC_VER)
186 unsigned long Index;
187 _BitScanReverse(&Index, Val);
188 return Index ^ 31;
189#endif
190 }
191};
192
193#if !defined(_MSC_VER) || defined(_M_X64)
194template <typename T> struct LeadingZerosCounter<T, 8> {
195 static unsigned count(T Val, ZeroBehavior ZB) {
196 if (ZB != ZB_Undefined && Val == 0)
197 return 64;
198
199#if __has_builtin(__builtin_clzll)1 || defined(__GNUC__4)
200 return __builtin_clzll(Val);
201#elif defined(_MSC_VER)
202 unsigned long Index;
203 _BitScanReverse64(&Index, Val);
204 return Index ^ 63;
205#endif
206 }
207};
208#endif
209#endif
210} // namespace detail
211
212/// Count number of 0's from the most significant bit to the least
213/// stopping at the first 1.
214///
215/// Only unsigned integral types are allowed.
216///
217/// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are
218/// valid arguments.
219template <typename T>
220unsigned countLeadingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
221 static_assert(std::is_unsigned_v<T>,
222 "Only unsigned integral types are allowed.");
223 return llvm::detail::LeadingZerosCounter<T, sizeof(T)>::count(Val, ZB);
20
Calling 'LeadingZerosCounter::count'
25
Returning from 'LeadingZerosCounter::count'
26
Returning the value 32, which participates in a condition later
27
Returning the value 32
224}
225
226/// Get the index of the first set bit starting from the least
227/// significant bit.
228///
229/// Only unsigned integral types are allowed.
230///
231/// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are
232/// valid arguments.
233template <typename T> T findFirstSet(T Val, ZeroBehavior ZB = ZB_Max) {
234 if (ZB == ZB_Max && Val == 0)
235 return std::numeric_limits<T>::max();
236
237 return countTrailingZeros(Val, ZB_Undefined);
238}
239
240/// Create a bitmask with the N right-most bits set to 1, and all other
241/// bits set to 0. Only unsigned types are allowed.
242template <typename T> T maskTrailingOnes(unsigned N) {
243 static_assert(std::is_unsigned<T>::value, "Invalid type!");
244 const unsigned Bits = CHAR_BIT8 * sizeof(T);
245 assert(N <= Bits && "Invalid bit index")(static_cast <bool> (N <= Bits && "Invalid bit index"
) ? void (0) : __assert_fail ("N <= Bits && \"Invalid bit index\""
, "llvm/include/llvm/Support/MathExtras.h", 245, __extension__
__PRETTY_FUNCTION__))
;
246 return N == 0 ? 0 : (T(-1) >> (Bits - N));
247}
248
249/// Create a bitmask with the N left-most bits set to 1, and all other
250/// bits set to 0. Only unsigned types are allowed.
251template <typename T> T maskLeadingOnes(unsigned N) {
252 return ~maskTrailingOnes<T>(CHAR_BIT8 * sizeof(T) - N);
253}
254
255/// Create a bitmask with the N right-most bits set to 0, and all other
256/// bits set to 1. Only unsigned types are allowed.
257template <typename T> T maskTrailingZeros(unsigned N) {
258 return maskLeadingOnes<T>(CHAR_BIT8 * sizeof(T) - N);
259}
260
261/// Create a bitmask with the N left-most bits set to 0, and all other
262/// bits set to 1. Only unsigned types are allowed.
263template <typename T> T maskLeadingZeros(unsigned N) {
264 return maskTrailingOnes<T>(CHAR_BIT8 * sizeof(T) - N);
265}
266
267/// Get the index of the last set bit starting from the least
268/// significant bit.
269///
270/// Only unsigned integral types are allowed.
271///
272/// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are
273/// valid arguments.
274template <typename T> T findLastSet(T Val, ZeroBehavior ZB = ZB_Max) {
275 if (ZB == ZB_Max && Val == 0)
276 return std::numeric_limits<T>::max();
277
278 // Use ^ instead of - because both gcc and llvm can remove the associated ^
279 // in the __builtin_clz intrinsic on x86.
280 return countLeadingZeros(Val, ZB_Undefined) ^
281 (std::numeric_limits<T>::digits - 1);
282}
283
284/// Macro compressed bit reversal table for 256 bits.
285///
286/// http://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable
287static const unsigned char BitReverseTable256[256] = {
288#define R2(n) n, n + 2 * 64, n + 1 * 64, n + 3 * 64
289#define R4(n) R2(n), R2(n + 2 * 16), R2(n + 1 * 16), R2(n + 3 * 16)
290#define R6(n) R4(n), R4(n + 2 * 4), R4(n + 1 * 4), R4(n + 3 * 4)
291 R6(0), R6(2), R6(1), R6(3)
292#undef R2
293#undef R4
294#undef R6
295};
296
297/// Reverse the bits in \p Val.
298template <typename T> T reverseBits(T Val) {
299#if __has_builtin(__builtin_bitreverse8)1
300 if constexpr (std::is_same_v<T, uint8_t>)
301 return __builtin_bitreverse8(Val);
302#endif
303#if __has_builtin(__builtin_bitreverse16)1
304 if constexpr (std::is_same_v<T, uint16_t>)
305 return __builtin_bitreverse16(Val);
306#endif
307#if __has_builtin(__builtin_bitreverse32)1
308 if constexpr (std::is_same_v<T, uint32_t>)
309 return __builtin_bitreverse32(Val);
310#endif
311#if __has_builtin(__builtin_bitreverse64)1
312 if constexpr (std::is_same_v<T, uint64_t>)
313 return __builtin_bitreverse64(Val);
314#endif
315
316 unsigned char in[sizeof(Val)];
317 unsigned char out[sizeof(Val)];
318 std::memcpy(in, &Val, sizeof(Val));
319 for (unsigned i = 0; i < sizeof(Val); ++i)
320 out[(sizeof(Val) - i) - 1] = BitReverseTable256[in[i]];
321 std::memcpy(&Val, out, sizeof(Val));
322 return Val;
323}
324
325// NOTE: The following support functions use the _32/_64 extensions instead of
326// type overloading so that signed and unsigned integers can be used without
327// ambiguity.
328
329/// Return the high 32 bits of a 64 bit value.
330constexpr inline uint32_t Hi_32(uint64_t Value) {
331 return static_cast<uint32_t>(Value >> 32);
332}
333
334/// Return the low 32 bits of a 64 bit value.
335constexpr inline uint32_t Lo_32(uint64_t Value) {
336 return static_cast<uint32_t>(Value);
337}
338
339/// Make a 64-bit integer from a high / low pair of 32-bit integers.
340constexpr inline uint64_t Make_64(uint32_t High, uint32_t Low) {
341 return ((uint64_t)High << 32) | (uint64_t)Low;
342}
343
344/// Checks if an integer fits into the given bit width.
345template <unsigned N> constexpr inline bool isInt(int64_t x) {
346 if constexpr (N == 8)
347 return static_cast<int8_t>(x) == x;
348 if constexpr (N == 16)
349 return static_cast<int16_t>(x) == x;
350 if constexpr (N == 32)
351 return static_cast<int32_t>(x) == x;
352 if constexpr (N < 64)
353 return -(INT64_C(1)1L << (N - 1)) <= x && x < (INT64_C(1)1L << (N - 1));
354 (void)x; // MSVC v19.25 warns that x is unused.
355 return true;
356}
357
358/// Checks if a signed integer is an N bit number shifted left by S.
359template <unsigned N, unsigned S>
360constexpr inline bool isShiftedInt(int64_t x) {
361 static_assert(
362 N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
363 static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
364 return isInt<N + S>(x) && (x % (UINT64_C(1)1UL << S) == 0);
365}
366
367/// Checks if an unsigned integer fits into the given bit width.
368template <unsigned N> constexpr inline bool isUInt(uint64_t x) {
369 static_assert(N > 0, "isUInt<0> doesn't make sense");
370 if constexpr (N == 8)
371 return static_cast<uint8_t>(x) == x;
372 if constexpr (N == 16)
373 return static_cast<uint16_t>(x) == x;
374 if constexpr (N == 32)
375 return static_cast<uint32_t>(x) == x;
376 if constexpr (N < 64)
377 return x < (UINT64_C(1)1UL << (N));
378 (void)x; // MSVC v19.25 warns that x is unused.
379 return true;
380}
381
382/// Checks if a unsigned integer is an N bit number shifted left by S.
383template <unsigned N, unsigned S>
384constexpr inline bool isShiftedUInt(uint64_t x) {
385 static_assert(
386 N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
387 static_assert(N + S <= 64,
388 "isShiftedUInt<N, S> with N + S > 64 is too wide.");
389 // Per the two static_asserts above, S must be strictly less than 64. So
390 // 1 << S is not undefined behavior.
391 return isUInt<N + S>(x) && (x % (UINT64_C(1)1UL << S) == 0);
392}
393
394/// Gets the maximum value for a N-bit unsigned integer.
395inline uint64_t maxUIntN(uint64_t N) {
396 assert(N > 0 && N <= 64 && "integer width out of range")(static_cast <bool> (N > 0 && N <= 64 &&
"integer width out of range") ? void (0) : __assert_fail ("N > 0 && N <= 64 && \"integer width out of range\""
, "llvm/include/llvm/Support/MathExtras.h", 396, __extension__
__PRETTY_FUNCTION__))
;
397
398 // uint64_t(1) << 64 is undefined behavior, so we can't do
399 // (uint64_t(1) << N) - 1
400 // without checking first that N != 64. But this works and doesn't have a
401 // branch.
402 return UINT64_MAX(18446744073709551615UL) >> (64 - N);
403}
404
405/// Gets the minimum value for a N-bit signed integer.
406inline int64_t minIntN(int64_t N) {
407 assert(N > 0 && N <= 64 && "integer width out of range")(static_cast <bool> (N > 0 && N <= 64 &&
"integer width out of range") ? void (0) : __assert_fail ("N > 0 && N <= 64 && \"integer width out of range\""
, "llvm/include/llvm/Support/MathExtras.h", 407, __extension__
__PRETTY_FUNCTION__))
;
408
409 return UINT64_C(1)1UL + ~(UINT64_C(1)1UL << (N - 1));
410}
411
412/// Gets the maximum value for a N-bit signed integer.
413inline int64_t maxIntN(int64_t N) {
414 assert(N > 0 && N <= 64 && "integer width out of range")(static_cast <bool> (N > 0 && N <= 64 &&
"integer width out of range") ? void (0) : __assert_fail ("N > 0 && N <= 64 && \"integer width out of range\""
, "llvm/include/llvm/Support/MathExtras.h", 414, __extension__
__PRETTY_FUNCTION__))
;
415
416 // This relies on two's complement wraparound when N == 64, so we convert to
417 // int64_t only at the very end to avoid UB.
418 return (UINT64_C(1)1UL << (N - 1)) - 1;
419}
420
421/// Checks if an unsigned integer fits into the given (dynamic) bit width.
422inline bool isUIntN(unsigned N, uint64_t x) {
423 return N >= 64 || x <= maxUIntN(N);
424}
425
426/// Checks if an signed integer fits into the given (dynamic) bit width.
427inline bool isIntN(unsigned N, int64_t x) {
428 return N >= 64 || (minIntN(N) <= x && x <= maxIntN(N));
429}
430
431/// Return true if the argument is a non-empty sequence of ones starting at the
432/// least significant bit with the remainder zero (32 bit version).
433/// Ex. isMask_32(0x0000FFFFU) == true.
434constexpr inline bool isMask_32(uint32_t Value) {
435 return Value && ((Value + 1) & Value) == 0;
436}
437
438/// Return true if the argument is a non-empty sequence of ones starting at the
439/// least significant bit with the remainder zero (64 bit version).
440constexpr inline bool isMask_64(uint64_t Value) {
441 return Value && ((Value + 1) & Value) == 0;
442}
443
444/// Return true if the argument contains a non-empty sequence of ones with the
445/// remainder zero (32 bit version.) Ex. isShiftedMask_32(0x0000FF00U) == true.
446constexpr inline bool isShiftedMask_32(uint32_t Value) {
447 return Value && isMask_32((Value - 1) | Value);
448}
449
450/// Return true if the argument contains a non-empty sequence of ones with the
451/// remainder zero (64 bit version.)
452constexpr inline bool isShiftedMask_64(uint64_t Value) {
453 return Value && isMask_64((Value - 1) | Value);
454}
455
456/// Return true if the argument is a power of two > 0.
457/// Ex. isPowerOf2_32(0x00100000U) == true (32 bit edition.)
458constexpr inline bool isPowerOf2_32(uint32_t Value) {
459 return llvm::has_single_bit(Value);
460}
461
462/// Return true if the argument is a power of two > 0 (64 bit edition.)
463constexpr inline bool isPowerOf2_64(uint64_t Value) {
464 return llvm::has_single_bit(Value);
465}
466
467/// Count the number of ones from the most significant bit to the first
468/// zero bit.
469///
470/// Ex. countLeadingOnes(0xFF0FFF00) == 8.
471/// Only unsigned integral types are allowed.
472///
473/// \param ZB the behavior on an input of all ones. Only ZB_Width and
474/// ZB_Undefined are valid arguments.
475template <typename T>
476unsigned countLeadingOnes(T Value, ZeroBehavior ZB = ZB_Width) {
477 static_assert(std::is_unsigned_v<T>,
478 "Only unsigned integral types are allowed.");
479 return countLeadingZeros<T>(~Value, ZB);
480}
481
482/// Count the number of ones from the least significant bit to the first
483/// zero bit.
484///
485/// Ex. countTrailingOnes(0x00FF00FF) == 8.
486/// Only unsigned integral types are allowed.
487///
488/// \param ZB the behavior on an input of all ones. Only ZB_Width and
489/// ZB_Undefined are valid arguments.
490template <typename T>
491unsigned countTrailingOnes(T Value, ZeroBehavior ZB = ZB_Width) {
492 static_assert(std::is_unsigned_v<T>,
493 "Only unsigned integral types are allowed.");
494 return countTrailingZeros<T>(~Value, ZB);
495}
496
497/// Count the number of set bits in a value.
498/// Ex. countPopulation(0xF000F000) = 8
499/// Returns 0 if the word is zero.
500template <typename T>
501inline unsigned countPopulation(T Value) {
502 static_assert(std::is_unsigned_v<T>,
503 "Only unsigned integral types are allowed.");
504 return (unsigned)llvm::popcount(Value);
505}
506
507/// Return true if the argument contains a non-empty sequence of ones with the
508/// remainder zero (32 bit version.) Ex. isShiftedMask_32(0x0000FF00U) == true.
509/// If true, \p MaskIdx will specify the index of the lowest set bit and \p
510/// MaskLen is updated to specify the length of the mask, else neither are
511/// updated.
512inline bool isShiftedMask_32(uint32_t Value, unsigned &MaskIdx,
513 unsigned &MaskLen) {
514 if (!isShiftedMask_32(Value))
515 return false;
516 MaskIdx = countTrailingZeros(Value);
517 MaskLen = countPopulation(Value);
518 return true;
519}
520
521/// Return true if the argument contains a non-empty sequence of ones with the
522/// remainder zero (64 bit version.) If true, \p MaskIdx will specify the index
523/// of the lowest set bit and \p MaskLen is updated to specify the length of the
524/// mask, else neither are updated.
525inline bool isShiftedMask_64(uint64_t Value, unsigned &MaskIdx,
526 unsigned &MaskLen) {
527 if (!isShiftedMask_64(Value))
528 return false;
529 MaskIdx = countTrailingZeros(Value);
530 MaskLen = countPopulation(Value);
531 return true;
532}
533
534/// Compile time Log2.
535/// Valid only for positive powers of two.
536template <size_t kValue> constexpr inline size_t CTLog2() {
537 static_assert(kValue > 0 && llvm::isPowerOf2_64(kValue),
538 "Value is not a valid power of 2");
539 return 1 + CTLog2<kValue / 2>();
540}
541
542template <> constexpr inline size_t CTLog2<1>() { return 0; }
543
544/// Return the floor log base 2 of the specified value, -1 if the value is zero.
545/// (32 bit edition.)
546/// Ex. Log2_32(32) == 5, Log2_32(1) == 0, Log2_32(0) == -1, Log2_32(6) == 2
547inline unsigned Log2_32(uint32_t Value) {
548 return 31 - countLeadingZeros(Value);
549}
550
551/// Return the floor log base 2 of the specified value, -1 if the value is zero.
552/// (64 bit edition.)
553inline unsigned Log2_64(uint64_t Value) {
554 return 63 - countLeadingZeros(Value);
555}
556
557/// Return the ceil log base 2 of the specified value, 32 if the value is zero.
558/// (32 bit edition).
559/// Ex. Log2_32_Ceil(32) == 5, Log2_32_Ceil(1) == 0, Log2_32_Ceil(6) == 3
560inline unsigned Log2_32_Ceil(uint32_t Value) {
561 return 32 - countLeadingZeros(Value - 1);
562}
563
564/// Return the ceil log base 2 of the specified value, 64 if the value is zero.
565/// (64 bit edition.)
566inline unsigned Log2_64_Ceil(uint64_t Value) {
567 return 64 - countLeadingZeros(Value - 1);
568}
569
570/// This function takes a 64-bit integer and returns the bit equivalent double.
571inline double BitsToDouble(uint64_t Bits) {
572 static_assert(sizeof(uint64_t) == sizeof(double), "Unexpected type sizes");
573 return llvm::bit_cast<double>(Bits);
574}
575
576/// This function takes a 32-bit integer and returns the bit equivalent float.
577inline float BitsToFloat(uint32_t Bits) {
578 static_assert(sizeof(uint32_t) == sizeof(float), "Unexpected type sizes");
579 return llvm::bit_cast<float>(Bits);
580}
581
582/// This function takes a double and returns the bit equivalent 64-bit integer.
583/// Note that copying doubles around changes the bits of NaNs on some hosts,
584/// notably x86, so this routine cannot be used if these bits are needed.
585inline uint64_t DoubleToBits(double Double) {
586 static_assert(sizeof(uint64_t) == sizeof(double), "Unexpected type sizes");
587 return llvm::bit_cast<uint64_t>(Double);
588}
589
590/// This function takes a float and returns the bit equivalent 32-bit integer.
591/// Note that copying floats around changes the bits of NaNs on some hosts,
592/// notably x86, so this routine cannot be used if these bits are needed.
593inline uint32_t FloatToBits(float Float) {
594 static_assert(sizeof(uint32_t) == sizeof(float), "Unexpected type sizes");
595 return llvm::bit_cast<uint32_t>(Float);
596}
597
598/// A and B are either alignments or offsets. Return the minimum alignment that
599/// may be assumed after adding the two together.
600constexpr inline uint64_t MinAlign(uint64_t A, uint64_t B) {
601 // The largest power of 2 that divides both A and B.
602 //
603 // Replace "-Value" by "1+~Value" in the following commented code to avoid
604 // MSVC warning C4146
605 // return (A | B) & -(A | B);
606 return (A | B) & (1 + ~(A | B));
607}
608
609/// Returns the next power of two (in 64-bits) that is strictly greater than A.
610/// Returns zero on overflow.
611constexpr inline uint64_t NextPowerOf2(uint64_t A) {
612 A |= (A >> 1);
613 A |= (A >> 2);
614 A |= (A >> 4);
615 A |= (A >> 8);
616 A |= (A >> 16);
617 A |= (A >> 32);
618 return A + 1;
619}
620
621/// Returns the power of two which is less than or equal to the given value.
622/// Essentially, it is a floor operation across the domain of powers of two.
623inline uint64_t PowerOf2Floor(uint64_t A) {
624 if (!A) return 0;
625 return 1ull << (63 - countLeadingZeros(A, ZB_Undefined));
626}
627
628/// Returns the power of two which is greater than or equal to the given value.
629/// Essentially, it is a ceil operation across the domain of powers of two.
630inline uint64_t PowerOf2Ceil(uint64_t A) {
631 if (!A)
632 return 0;
633 return NextPowerOf2(A - 1);
634}
635
636/// Returns the next integer (mod 2**64) that is greater than or equal to
637/// \p Value and is a multiple of \p Align. \p Align must be non-zero.
638///
639/// Examples:
640/// \code
641/// alignTo(5, 8) = 8
642/// alignTo(17, 8) = 24
643/// alignTo(~0LL, 8) = 0
644/// alignTo(321, 255) = 510
645/// \endcode
646inline uint64_t alignTo(uint64_t Value, uint64_t Align) {
647 assert(Align != 0u && "Align can't be 0.")(static_cast <bool> (Align != 0u && "Align can't be 0."
) ? void (0) : __assert_fail ("Align != 0u && \"Align can't be 0.\""
, "llvm/include/llvm/Support/MathExtras.h", 647, __extension__
__PRETTY_FUNCTION__))
;
648 return (Value + Align - 1) / Align * Align;
649}
650
651inline uint64_t alignToPowerOf2(uint64_t Value, uint64_t Align) {
652 assert(Align != 0 && (Align & (Align - 1)) == 0 &&(static_cast <bool> (Align != 0 && (Align &
(Align - 1)) == 0 && "Align must be a power of 2") ?
void (0) : __assert_fail ("Align != 0 && (Align & (Align - 1)) == 0 && \"Align must be a power of 2\""
, "llvm/include/llvm/Support/MathExtras.h", 653, __extension__
__PRETTY_FUNCTION__))
653 "Align must be a power of 2")(static_cast <bool> (Align != 0 && (Align &
(Align - 1)) == 0 && "Align must be a power of 2") ?
void (0) : __assert_fail ("Align != 0 && (Align & (Align - 1)) == 0 && \"Align must be a power of 2\""
, "llvm/include/llvm/Support/MathExtras.h", 653, __extension__
__PRETTY_FUNCTION__))
;
654 return (Value + Align - 1) & -Align;
655}
656
657/// If non-zero \p Skew is specified, the return value will be a minimal integer
658/// that is greater than or equal to \p Size and equal to \p A * N + \p Skew for
659/// some integer N. If \p Skew is larger than \p A, its value is adjusted to '\p
660/// Skew mod \p A'. \p Align must be non-zero.
661///
662/// Examples:
663/// \code
664/// alignTo(5, 8, 7) = 7
665/// alignTo(17, 8, 1) = 17
666/// alignTo(~0LL, 8, 3) = 3
667/// alignTo(321, 255, 42) = 552
668/// \endcode
669inline uint64_t alignTo(uint64_t Value, uint64_t Align, uint64_t Skew) {
670 assert(Align != 0u && "Align can't be 0.")(static_cast <bool> (Align != 0u && "Align can't be 0."
) ? void (0) : __assert_fail ("Align != 0u && \"Align can't be 0.\""
, "llvm/include/llvm/Support/MathExtras.h", 670, __extension__
__PRETTY_FUNCTION__))
;
671 Skew %= Align;
672 return alignTo(Value - Skew, Align) + Skew;
673}
674
675/// Returns the next integer (mod 2**64) that is greater than or equal to
676/// \p Value and is a multiple of \c Align. \c Align must be non-zero.
677template <uint64_t Align> constexpr inline uint64_t alignTo(uint64_t Value) {
678 static_assert(Align != 0u, "Align must be non-zero");
679 return (Value + Align - 1) / Align * Align;
680}
681
682/// Returns the integer ceil(Numerator / Denominator).
683inline uint64_t divideCeil(uint64_t Numerator, uint64_t Denominator) {
684 return alignTo(Numerator, Denominator) / Denominator;
685}
686
687/// Returns the integer nearest(Numerator / Denominator).
688inline uint64_t divideNearest(uint64_t Numerator, uint64_t Denominator) {
689 return (Numerator + (Denominator / 2)) / Denominator;
690}
691
692/// Returns the largest uint64_t less than or equal to \p Value and is
693/// \p Skew mod \p Align. \p Align must be non-zero
694inline uint64_t alignDown(uint64_t Value, uint64_t Align, uint64_t Skew = 0) {
695 assert(Align != 0u && "Align can't be 0.")(static_cast <bool> (Align != 0u && "Align can't be 0."
) ? void (0) : __assert_fail ("Align != 0u && \"Align can't be 0.\""
, "llvm/include/llvm/Support/MathExtras.h", 695, __extension__
__PRETTY_FUNCTION__))
;
696 Skew %= Align;
697 return (Value - Skew) / Align * Align + Skew;
698}
699
700/// Sign-extend the number in the bottom B bits of X to a 32-bit integer.
701/// Requires 0 < B <= 32.
702template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) {
703 static_assert(B > 0, "Bit width can't be 0.");
704 static_assert(B <= 32, "Bit width out of range.");
705 return int32_t(X << (32 - B)) >> (32 - B);
706}
707
708/// Sign-extend the number in the bottom B bits of X to a 32-bit integer.
709/// Requires 0 < B <= 32.
710inline int32_t SignExtend32(uint32_t X, unsigned B) {
711 assert(B > 0 && "Bit width can't be 0.")(static_cast <bool> (B > 0 && "Bit width can't be 0."
) ? void (0) : __assert_fail ("B > 0 && \"Bit width can't be 0.\""
, "llvm/include/llvm/Support/MathExtras.h", 711, __extension__
__PRETTY_FUNCTION__))
;
712 assert(B <= 32 && "Bit width out of range.")(static_cast <bool> (B <= 32 && "Bit width out of range."
) ? void (0) : __assert_fail ("B <= 32 && \"Bit width out of range.\""
, "llvm/include/llvm/Support/MathExtras.h", 712, __extension__
__PRETTY_FUNCTION__))
;
713 return int32_t(X << (32 - B)) >> (32 - B);
714}
715
716/// Sign-extend the number in the bottom B bits of X to a 64-bit integer.
717/// Requires 0 < B <= 64.
718template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
719 static_assert(B > 0, "Bit width can't be 0.");
720 static_assert(B <= 64, "Bit width out of range.");
721 return int64_t(x << (64 - B)) >> (64 - B);
722}
723
724/// Sign-extend the number in the bottom B bits of X to a 64-bit integer.
725/// Requires 0 < B <= 64.
726inline int64_t SignExtend64(uint64_t X, unsigned B) {
727 assert(B > 0 && "Bit width can't be 0.")(static_cast <bool> (B > 0 && "Bit width can't be 0."
) ? void (0) : __assert_fail ("B > 0 && \"Bit width can't be 0.\""
, "llvm/include/llvm/Support/MathExtras.h", 727, __extension__
__PRETTY_FUNCTION__))
;
728 assert(B <= 64 && "Bit width out of range.")(static_cast <bool> (B <= 64 && "Bit width out of range."
) ? void (0) : __assert_fail ("B <= 64 && \"Bit width out of range.\""
, "llvm/include/llvm/Support/MathExtras.h", 728, __extension__
__PRETTY_FUNCTION__))
;
729 return int64_t(X << (64 - B)) >> (64 - B);
730}
731
732/// Subtract two unsigned integers, X and Y, of type T and return the absolute
733/// value of the result.
734template <typename T>
735std::enable_if_t<std::is_unsigned<T>::value, T> AbsoluteDifference(T X, T Y) {
736 return X > Y ? (X - Y) : (Y - X);
737}
738
739/// Add two unsigned integers, X and Y, of type T. Clamp the result to the
740/// maximum representable value of T on overflow. ResultOverflowed indicates if
741/// the result is larger than the maximum representable value of type T.
742template <typename T>
743std::enable_if_t<std::is_unsigned<T>::value, T>
744SaturatingAdd(T X, T Y, bool *ResultOverflowed = nullptr) {
745 bool Dummy;
746 bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
747 // Hacker's Delight, p. 29
748 T Z = X + Y;
749 Overflowed = (Z < X || Z < Y);
750 if (Overflowed)
751 return std::numeric_limits<T>::max();
752 else
753 return Z;
754}
755
756/// Multiply two unsigned integers, X and Y, of type T. Clamp the result to the
757/// maximum representable value of T on overflow. ResultOverflowed indicates if
758/// the result is larger than the maximum representable value of type T.
759template <typename T>
760std::enable_if_t<std::is_unsigned<T>::value, T>
761SaturatingMultiply(T X, T Y, bool *ResultOverflowed = nullptr) {
762 bool Dummy;
763 bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
764
765 // Hacker's Delight, p. 30 has a different algorithm, but we don't use that
766 // because it fails for uint16_t (where multiplication can have undefined
767 // behavior due to promotion to int), and requires a division in addition
768 // to the multiplication.
769
770 Overflowed = false;
771
772 // Log2(Z) would be either Log2Z or Log2Z + 1.
773 // Special case: if X or Y is 0, Log2_64 gives -1, and Log2Z
774 // will necessarily be less than Log2Max as desired.
775 int Log2Z = Log2_64(X) + Log2_64(Y);
776 const T Max = std::numeric_limits<T>::max();
777 int Log2Max = Log2_64(Max);
778 if (Log2Z < Log2Max) {
779 return X * Y;
780 }
781 if (Log2Z > Log2Max) {
782 Overflowed = true;
783 return Max;
784 }
785
786 // We're going to use the top bit, and maybe overflow one
787 // bit past it. Multiply all but the bottom bit then add
788 // that on at the end.
789 T Z = (X >> 1) * Y;
790 if (Z & ~(Max >> 1)) {
791 Overflowed = true;
792 return Max;
793 }
794 Z <<= 1;
795 if (X & 1)
796 return SaturatingAdd(Z, Y, ResultOverflowed);
797
798 return Z;
799}
800
801/// Multiply two unsigned integers, X and Y, and add the unsigned integer, A to
802/// the product. Clamp the result to the maximum representable value of T on
803/// overflow. ResultOverflowed indicates if the result is larger than the
804/// maximum representable value of type T.
805template <typename T>
806std::enable_if_t<std::is_unsigned<T>::value, T>
807SaturatingMultiplyAdd(T X, T Y, T A, bool *ResultOverflowed = nullptr) {
808 bool Dummy;
809 bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
810
811 T Product = SaturatingMultiply(X, Y, &Overflowed);
812 if (Overflowed)
813 return Product;
814
815 return SaturatingAdd(A, Product, &Overflowed);
816}
817
818/// Use this rather than HUGE_VALF; the latter causes warnings on MSVC.
819extern const float huge_valf;
820
821
822/// Add two signed integers, computing the two's complement truncated result,
823/// returning true if overflow occurred.
824template <typename T>
825std::enable_if_t<std::is_signed<T>::value, T> AddOverflow(T X, T Y, T &Result) {
826#if __has_builtin(__builtin_add_overflow)1
827 return __builtin_add_overflow(X, Y, &Result);
828#else
829 // Perform the unsigned addition.
830 using U = std::make_unsigned_t<T>;
831 const U UX = static_cast<U>(X);
832 const U UY = static_cast<U>(Y);
833 const U UResult = UX + UY;
834
835 // Convert to signed.
836 Result = static_cast<T>(UResult);
837
838 // Adding two positive numbers should result in a positive number.
839 if (X > 0 && Y > 0)
840 return Result <= 0;
841 // Adding two negatives should result in a negative number.
842 if (X < 0 && Y < 0)
843 return Result >= 0;
844 return false;
845#endif
846}
847
848/// Subtract two signed integers, computing the two's complement truncated
849/// result, returning true if an overflow ocurred.
850template <typename T>
851std::enable_if_t<std::is_signed<T>::value, T> SubOverflow(T X, T Y, T &Result) {
852#if __has_builtin(__builtin_sub_overflow)1
853 return __builtin_sub_overflow(X, Y, &Result);
854#else
855 // Perform the unsigned addition.
856 using U = std::make_unsigned_t<T>;
857 const U UX = static_cast<U>(X);
858 const U UY = static_cast<U>(Y);
859 const U UResult = UX - UY;
860
861 // Convert to signed.
862 Result = static_cast<T>(UResult);
863
864 // Subtracting a positive number from a negative results in a negative number.
865 if (X <= 0 && Y > 0)
866 return Result >= 0;
867 // Subtracting a negative number from a positive results in a positive number.
868 if (X >= 0 && Y < 0)
869 return Result <= 0;
870 return false;
871#endif
872}
873
874/// Multiply two signed integers, computing the two's complement truncated
875/// result, returning true if an overflow ocurred.
876template <typename T>
877std::enable_if_t<std::is_signed<T>::value, T> MulOverflow(T X, T Y, T &Result) {
878 // Perform the unsigned multiplication on absolute values.
879 using U = std::make_unsigned_t<T>;
880 const U UX = X < 0 ? (0 - static_cast<U>(X)) : static_cast<U>(X);
881 const U UY = Y < 0 ? (0 - static_cast<U>(Y)) : static_cast<U>(Y);
882 const U UResult = UX * UY;
883
884 // Convert to signed.
885 const bool IsNegative = (X < 0) ^ (Y < 0);
886 Result = IsNegative ? (0 - UResult) : UResult;
887
888 // If any of the args was 0, result is 0 and no overflow occurs.
889 if (UX == 0 || UY == 0)
890 return false;
891
892 // UX and UY are in [1, 2^n], where n is the number of digits.
893 // Check how the max allowed absolute value (2^n for negative, 2^(n-1) for
894 // positive) divided by an argument compares to the other.
895 if (IsNegative)
896 return UX > (static_cast<U>(std::numeric_limits<T>::max()) + U(1)) / UY;
897 else
898 return UX > (static_cast<U>(std::numeric_limits<T>::max())) / UY;
899}
900
901} // End llvm namespace
902
903#endif