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