LLVM: lib/Support/APInt.cpp Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
13
21#include "llvm/Config/llvm-config.h"
27#include
28#include
29
30using namespace llvm;
31
32#define DEBUG_TYPE "apint"
33
34
35
37 return new uint64_t[numWords]();
38}
39
40
41
43 return new uint64_t[numWords];
44}
45
46
48 unsigned r;
49
50 if (radix == 16 || radix == 36) {
51 r = cdigit - '0';
52 if (r <= 9)
53 return r;
54
55 r = cdigit - 'A';
56 if (r <= radix - 11U)
57 return r + 10;
58
59 r = cdigit - 'a';
60 if (r <= radix - 11U)
61 return r + 10;
62
63 radix = 10;
64 }
65
66 r = cdigit - '0';
67 if (r < radix)
68 return r;
69
70 return UINT_MAX;
71}
72
73
75 if (isSigned && int64_t(val) < 0) {
77 U.pVal[0] = val;
79 clearUnusedBits();
80 } else {
82 U.pVal[0] = val;
83 }
84}
85
86void APInt::initSlowCase(const APInt& that) {
89}
90
92 assert(bigVal.data() && "Null pointer detected!");
94 U.VAL = bigVal[0];
95 else {
96
98
99 unsigned words = std::min(bigVal.size(), getNumWords());
100
102 }
103
104 clearUnusedBits();
105}
106
108 initFromArray(bigVal);
109}
110
113 initFromArray(ArrayRef(bigVal, numWords));
114}
115
118 fromString(numbits, Str, radix);
119}
120
121void APInt::reallocate(unsigned NewBitWidth) {
122
124 BitWidth = NewBitWidth;
125 return;
126 }
127
128
130 delete [] U.pVal;
131
132
133 BitWidth = NewBitWidth;
134
135
138}
139
140void APInt::assignSlowCase(const APInt &RHS) {
141
142 if (this == &RHS)
143 return;
144
145
146 reallocate(RHS.getBitWidth());
147
148
150 U.VAL = RHS.U.VAL;
151 else
153}
154
155
157 ID.AddInteger(BitWidth);
158
160 ID.AddInteger(U.VAL);
161 return;
162 }
163
165 for (unsigned i = 0; i < NumWords; ++i)
166 ID.AddInteger(U.pVal[i]);
167}
168
171 return true;
172 const unsigned TrailingZeroes = countr_zero();
173 const unsigned MinimumTrailingZeroes = Log2(A);
174 return TrailingZeroes >= MinimumTrailingZeroes;
175}
176
177
180 ++U.VAL;
181 else
183 return clearUnusedBits();
184}
185
186
189 --U.VAL;
190 else
192 return clearUnusedBits();
193}
194
195
196
197
199 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
201 U.VAL += RHS.U.VAL;
202 else
204 return clearUnusedBits();
205}
206
209 U.VAL += RHS;
210 else
212 return clearUnusedBits();
213}
214
215
216
217
219 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
221 U.VAL -= RHS.U.VAL;
222 else
224 return clearUnusedBits();
225}
226
229 U.VAL -= RHS;
230 else
232 return clearUnusedBits();
233}
234
236 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
238 return APInt(BitWidth, U.VAL * RHS.U.VAL, false,
239 true);
240
243 Result.clearUnusedBits();
244 return Result;
245}
246
247void APInt::andAssignSlowCase(const APInt &RHS) {
248 WordType *dst = U.pVal, *rhs = RHS.U.pVal;
249 for (size_t i = 0, e = getNumWords(); i != e; ++i)
250 dst[i] &= rhs[i];
251}
252
253void APInt::orAssignSlowCase(const APInt &RHS) {
254 WordType *dst = U.pVal, *rhs = RHS.U.pVal;
255 for (size_t i = 0, e = getNumWords(); i != e; ++i)
256 dst[i] |= rhs[i];
257}
258
259void APInt::xorAssignSlowCase(const APInt &RHS) {
260 WordType *dst = U.pVal, *rhs = RHS.U.pVal;
261 for (size_t i = 0, e = getNumWords(); i != e; ++i)
262 dst[i] ^= rhs[i];
263}
264
266 *this = *this * RHS;
267 return *this;
268}
269
272 U.VAL *= RHS;
273 } else {
275 tcMultiplyPart(U.pVal, U.pVal, RHS, 0, NumWords, NumWords, false);
276 }
277 return clearUnusedBits();
278}
279
280bool APInt::equalSlowCase(const APInt &RHS) const {
281 return std::equal(U.pVal, U.pVal + getNumWords(), RHS.U.pVal);
282}
283
284int APInt::compare(const APInt& RHS) const {
285 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
287 return U.VAL < RHS.U.VAL ? -1 : U.VAL > RHS.U.VAL;
288
290}
291
292int APInt::compareSigned(const APInt& RHS) const {
293 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
295 int64_t lhsSext = SignExtend64(U.VAL, BitWidth);
297 return lhsSext < rhsSext ? -1 : lhsSext > rhsSext;
298 }
299
301 bool rhsNeg = RHS.isNegative();
302
303
304 if (lhsNeg != rhsNeg)
305 return lhsNeg ? -1 : 1;
306
307
308
310}
311
312void APInt::setBitsSlowCase(unsigned loBit, unsigned hiBit) {
313 unsigned loWord = whichWord(loBit);
314 unsigned hiWord = whichWord(hiBit);
315
316
318
319
320 unsigned hiShiftAmt = whichBit(hiBit);
321 if (hiShiftAmt != 0) {
322
324
325
326 if (hiWord == loWord)
327 loMask &= hiMask;
328 else
329 U.pVal[hiWord] |= hiMask;
330 }
331
332 U.pVal[loWord] |= loMask;
333
334
335 for (unsigned word = loWord + 1; word < hiWord; ++word)
337}
338
339
341 for (unsigned i = 0; i < parts; i++)
342 dst[i] = ~dst[i];
343}
344
345
346void APInt::flipAllBitsSlowCase() {
348 clearUnusedBits();
349}
350
351
352
353
354
355APInt APInt::concatSlowCase(const APInt &NewLSB) const {
360}
361
362
363
364
366 assert(bitPosition < BitWidth && "Out of the bit-width range!");
367 setBitVal(bitPosition, !(*this)[bitPosition]);
368}
369
371 unsigned subBitWidth = subBits.getBitWidth();
372 assert((subBitWidth + bitPosition) <= BitWidth && "Illegal bit insertion");
373
374
375 if (subBitWidth == 0)
376 return;
377
378
379 if (subBitWidth == BitWidth) {
380 *this = subBits;
381 return;
382 }
383
384
387 U.VAL &= ~(mask << bitPosition);
388 U.VAL |= (subBits.U.VAL << bitPosition);
389 return;
390 }
391
392 unsigned loBit = whichBit(bitPosition);
393 unsigned loWord = whichWord(bitPosition);
394 unsigned hi1Word = whichWord(bitPosition + subBitWidth - 1);
395
396
397 if (loWord == hi1Word) {
399 U.pVal[loWord] &= ~(mask << loBit);
400 U.pVal[loWord] |= (subBits.U.VAL << loBit);
401 return;
402 }
403
404
405 if (loBit == 0) {
406
408 memcpy(U.pVal + loWord, subBits.getRawData(),
410
411
413 if (remainingBits != 0) {
415 U.pVal[hi1Word] &= ~mask;
416 U.pVal[hi1Word] |= subBits.getWord(subBitWidth - 1);
417 }
418 return;
419 }
420
421
422
423
424 for (unsigned i = 0; i != subBitWidth; ++i)
425 setBitVal(bitPosition + i, subBits[i]);
426}
427
429 uint64_t maskBits = maskTrailingOnes<uint64_t>(numBits);
430 subBits &= maskBits;
432 U.VAL &= ~(maskBits << bitPosition);
433 U.VAL |= subBits << bitPosition;
434 return;
435 }
436
437 unsigned loBit = whichBit(bitPosition);
438 unsigned loWord = whichWord(bitPosition);
439 unsigned hiWord = whichWord(bitPosition + numBits - 1);
440 if (loWord == hiWord) {
441 U.pVal[loWord] &= ~(maskBits << loBit);
442 U.pVal[loWord] |= subBits << loBit;
443 return;
444 }
445
446 static_assert(8 * sizeof(WordType) <= 64, "This code assumes only two words affected");
447 unsigned wordBits = 8 * sizeof(WordType);
448 U.pVal[loWord] &= ~(maskBits << loBit);
449 U.pVal[loWord] |= subBits << loBit;
450
451 U.pVal[hiWord] &= ~(maskBits >> (wordBits - loBit));
452 U.pVal[hiWord] |= subBits >> (wordBits - loBit);
453}
454
456 assert(bitPosition < BitWidth && (numBits + bitPosition) <= BitWidth &&
457 "Illegal bit extraction");
458
460 return APInt(numBits, U.VAL >> bitPosition, false,
461 true);
462
463 unsigned loBit = whichBit(bitPosition);
464 unsigned loWord = whichWord(bitPosition);
465 unsigned hiWord = whichWord(bitPosition + numBits - 1);
466
467
468 if (loWord == hiWord)
469 return APInt(numBits, U.pVal[loWord] >> loBit, false,
470 true);
471
472
473
474 if (loBit == 0)
475 return APInt(numBits, ArrayRef(U.pVal + loWord, 1 + hiWord - loWord));
476
477
478 APInt Result(numBits, 0);
480 unsigned NumDstWords = Result.getNumWords();
481
482 uint64_t *DestPtr = Result.isSingleWord() ? &Result.U.VAL : Result.U.pVal;
483 for (unsigned word = 0; word < NumDstWords; ++word) {
484 uint64_t w0 = U.pVal[loWord + word];
486 (loWord + word + 1) < NumSrcWords ? U.pVal[loWord + word + 1] : 0;
488 }
489
490 return Result.clearUnusedBits();
491}
492
494 unsigned bitPosition) const {
495 assert(bitPosition < BitWidth && (numBits + bitPosition) <= BitWidth &&
496 "Illegal bit extraction");
497 assert(numBits <= 64 && "Illegal bit extraction");
498
499 uint64_t maskBits = maskTrailingOnes<uint64_t>(numBits);
501 return (U.VAL >> bitPosition) & maskBits;
502
504 "This code assumes only two words affected");
505 unsigned loBit = whichBit(bitPosition);
506 unsigned loWord = whichWord(bitPosition);
507 unsigned hiWord = whichWord(bitPosition + numBits - 1);
508 if (loWord == hiWord)
509 return (U.pVal[loWord] >> loBit) & maskBits;
510
511 uint64_t retBits = U.pVal[loWord] >> loBit;
513 retBits &= maskBits;
514 return retBits;
515}
516
518 assert(!Str.empty() && "Invalid string length");
519 size_t StrLen = Str.size();
520
521
522 unsigned IsNegative = false;
523 if (Str[0] == '-' || Str[0] == '+') {
524 IsNegative = Str[0] == '-';
525 StrLen--;
526 assert(StrLen && "String is only a sign, needs a value.");
527 }
528
529
530
531 if (Radix == 2)
532 return StrLen + IsNegative;
533 if (Radix == 8)
534 return StrLen * 3 + IsNegative;
535 if (Radix == 16)
536 return StrLen * 4 + IsNegative;
537
538
539
540
541
542 if (Radix == 10)
543 return (StrLen == 1 ? 4 : StrLen * 64 / 18) + IsNegative;
544
546 return (StrLen == 1 ? 7 : StrLen * 16 / 3) + IsNegative;
547}
548
550
551
553
554
555
556 if (radix == 2 || radix == 8 || radix == 16)
557 return sufficient;
558
559
560
561
562 size_t slen = str.size();
563
564
567 if (*p == '-' || *p == '+') {
568 p++;
569 slen--;
570 assert(slen && "String is only a sign, needs a value.");
571 }
572
573
574
576
577
578
579
580 unsigned log = tmp.logBase2();
581 if (log == (unsigned)-1) {
585 } else {
587 }
588}
589
593
595 Arg.BitWidth,
597}
598
600 return static_cast<unsigned>(hash_value(Key));
601}
602
605 "SplatSizeInBits must divide width!");
606
607
608 return *this == rotl(SplatSizeInBits);
609}
610
611
613 return this->lshr(BitWidth - numBits);
614}
615
616
619 Result &= *this;
620 return Result;
621}
622
623
625 assert(NewLen >= V.getBitWidth() && "Can't splat to smaller bit width!");
626
627 APInt Val = V.zext(NewLen);
628 for (unsigned I = V.getBitWidth(); I < NewLen; I <<= 1)
629 Val |= Val << I;
630
631 return Val;
632}
633
634unsigned APInt::countLeadingZerosSlowCase() const {
635 unsigned Count = 0;
636 for (int i = getNumWords()-1; i >= 0; --i) {
638 if (V == 0)
640 else {
642 break;
643 }
644 }
645
648 return Count;
649}
650
651unsigned APInt::countLeadingOnesSlowCase() const {
653 unsigned shift;
654 if (!highWordBits) {
656 shift = 0;
657 } else {
659 }
662 if (Count == highWordBits) {
663 for (i--; i >= 0; --i) {
666 else {
668 break;
669 }
670 }
671 }
672 return Count;
673}
674
675unsigned APInt::countTrailingZerosSlowCase() const {
676 unsigned Count = 0;
677 unsigned i = 0;
678 for (; i < getNumWords() && U.pVal[i] == 0; ++i)
682 return std::min(Count, BitWidth);
683}
684
685unsigned APInt::countTrailingOnesSlowCase() const {
686 unsigned Count = 0;
687 unsigned i = 0;
692 assert(Count <= BitWidth);
693 return Count;
694}
695
696unsigned APInt::countPopulationSlowCase() const {
697 unsigned Count = 0;
698 for (unsigned i = 0; i < getNumWords(); ++i)
700 return Count;
701}
702
703bool APInt::intersectsSlowCase(const APInt &RHS) const {
704 for (unsigned i = 0, e = getNumWords(); i != e; ++i)
705 if ((U.pVal[i] & RHS.U.pVal[i]) != 0)
706 return true;
707
708 return false;
709}
710
711bool APInt::isSubsetOfSlowCase(const APInt &RHS) const {
712 for (unsigned i = 0, e = getNumWords(); i != e; ++i)
713 if ((U.pVal[i] & ~RHS.U.pVal[i]) != 0)
714 return false;
715
716 return true;
717}
718
720 assert(BitWidth >= 16 && BitWidth % 8 == 0 && "Cannot byteswap!");
721 if (BitWidth == 16)
722 return APInt(BitWidth, llvm::byteswap<uint16_t>(U.VAL));
723 if (BitWidth == 32)
724 return APInt(BitWidth, llvm::byteswap<uint32_t>(U.VAL));
725 if (BitWidth <= 64) {
726 uint64_t Tmp1 = llvm::byteswap<uint64_t>(U.VAL);
727 Tmp1 >>= (64 - BitWidth);
728 return APInt(BitWidth, Tmp1);
729 }
730
733 Result.U.pVal[I] = llvm::byteswap<uint64_t>(U.pVal[N - I - 1]);
734 if (Result.BitWidth != BitWidth) {
735 Result.lshrInPlace(Result.BitWidth - BitWidth);
736 Result.BitWidth = BitWidth;
737 }
738 return Result;
739}
740
742 switch (BitWidth) {
743 case 64:
744 return APInt(BitWidth, llvm::reverseBits<uint64_t>(U.VAL));
745 case 32:
746 return APInt(BitWidth, llvm::reverseBits<uint32_t>(U.VAL));
747 case 16:
748 return APInt(BitWidth, llvm::reverseBits<uint16_t>(U.VAL));
749 case 8:
750 return APInt(BitWidth, llvm::reverseBits<uint8_t>(U.VAL));
751 case 0:
752 return *this;
753 default:
754 break;
755 }
756
757 APInt Val(*this);
758 APInt Reversed(BitWidth, 0);
759 unsigned S = BitWidth;
760
762 Reversed <<= 1;
763 Reversed |= Val[0];
764 --S;
765 }
766
767 Reversed <<= S;
768 return Reversed;
769}
770
772
774
775
776 if () return B;
777 if () return A;
778
779
780 unsigned Pow2;
781 {
782 unsigned Pow2_A = A.countr_zero();
783 unsigned Pow2_B = B.countr_zero();
784 if (Pow2_A > Pow2_B) {
785 A.lshrInPlace(Pow2_A - Pow2_B);
786 Pow2 = Pow2_B;
787 } else if (Pow2_B > Pow2_A) {
788 B.lshrInPlace(Pow2_B - Pow2_A);
789 Pow2 = Pow2_A;
790 } else {
791 Pow2 = Pow2_A;
792 }
793 }
794
795
796
797
798
799
800
804 A.lshrInPlace(A.countr_zero() - Pow2);
805 } else {
807 B.lshrInPlace(B.countr_zero() - Pow2);
808 }
809 }
810
811 return A;
812}
813
815 uint64_t I = bit_cast<uint64_t>(Double);
816
817
819
820
821 int64_t exp = ((I >> 52) & 0x7ff) - 1023;
822
823
824 if (exp < 0)
825 return APInt(width, 0u);
826
827
828 uint64_t mantissa = (I & (~0ULL >> 12)) | 1ULL << 52;
829
830
831 if (exp < 52)
832 return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
833 APInt(width, mantissa >> (52 - exp));
834
835
836
837 if (width <= exp - 52)
838 return APInt(width, 0);
839
840
841 APInt Tmp(width, mantissa);
843 return isNeg ? -Tmp : Tmp;
844}
845
846
847
848
849
850
851
852
854
855
856
860 return double(sext);
861 } else
862 return double(getWord(0));
863 }
864
865
866 bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
867
868
869 APInt Tmp(isNeg ? -(*this) : (*this));
870
871
873
874
875
876
878
879
880 if (exp > 1023) {
882 return std::numeric_limits::infinity();
883 else
884 return -std::numeric_limits::infinity();
885 }
886 exp += 1023;
887
888
889
891 unsigned hiWord = whichWord(n-1);
892 if (hiWord == 0) {
893 mantissa = Tmp.U.pVal[0];
894 if (n > 52)
895 mantissa >>= n - 52;
896 } else {
897 assert(hiWord > 0 && "huh?");
900 mantissa = hibits | lobits;
901 }
902
903
905 uint64_t I = sign | (exp << 52) | mantissa;
906 return bit_cast(I);
907}
908
909
911 assert(width <= BitWidth && "Invalid APInt Truncate request");
912
915 true);
916
917 if (width == BitWidth)
918 return *this;
919
921
922
923 unsigned i;
925 Result.U.pVal[i] = U.pVal[i];
926
927
929 if (bits != 0)
930 Result.U.pVal[i] = U.pVal[i] << bits >> bits;
931
932 return Result;
933}
934
935
937 assert(width <= BitWidth && "Invalid APInt Truncate request");
938
939
941 return trunc(width);
942
944}
945
946
948 assert(width <= BitWidth && "Invalid APInt Truncate request");
949
950
952 return trunc(width);
953
956}
957
958
960 assert(Width >= BitWidth && "Invalid APInt SignExtend request");
961
963 return APInt(Width, SignExtend64(U.VAL, BitWidth), true);
964
965 if (Width == BitWidth)
966 return *this;
967
969
970
972
973
977
978
981 Result.clearUnusedBits();
982 return Result;
983}
984
985
987 assert(width >= BitWidth && "Invalid APInt ZeroExtend request");
988
990 return APInt(width, U.VAL);
991
992 if (width == BitWidth)
993 return *this;
994
996
997
999
1000
1001 std::memset(Result.U.pVal + getNumWords(), 0,
1003
1004 return Result;
1005}
1006
1008 if (BitWidth < width)
1009 return zext(width);
1010 if (BitWidth > width)
1011 return trunc(width);
1012 return *this;
1013}
1014
1016 if (BitWidth < width)
1017 return sext(width);
1018 if (BitWidth > width)
1019 return trunc(width);
1020 return *this;
1021}
1022
1023
1024
1027}
1028
1029
1030
1031void APInt::ashrSlowCase(unsigned ShiftAmt) {
1032
1033 if (!ShiftAmt)
1034 return;
1035
1036
1038
1039
1042
1043 unsigned WordsToMove = getNumWords() - WordShift;
1044 if (WordsToMove != 0) {
1045
1048
1049
1050 if (BitShift == 0) {
1051 std::memmove(U.pVal, U.pVal + WordShift, WordsToMove * APINT_WORD_SIZE);
1052 } else {
1053
1054 for (unsigned i = 0; i != WordsToMove - 1; ++i)
1055 U.pVal[i] = (U.pVal[i + WordShift] >> BitShift) |
1057
1058
1059
1060 U.pVal[WordsToMove - 1] =
1061 (int64_t)U.pVal[WordShift + WordsToMove - 1] >> BitShift;
1062 }
1063 }
1064
1065
1066 std::memset(U.pVal + WordsToMove, Negative ? -1 : 0,
1068 clearUnusedBits();
1069}
1070
1071
1072
1075}
1076
1077
1078
1079void APInt::lshrSlowCase(unsigned ShiftAmt) {
1081}
1082
1083
1084
1086
1088 return *this;
1089}
1090
1091void APInt::shlSlowCase(unsigned ShiftAmt) {
1093 clearUnusedBits();
1094}
1095
1096
1099 return 0;
1100 unsigned rotBitWidth = rotateAmt.getBitWidth();
1101 APInt rot = rotateAmt;
1102 if (rotBitWidth < BitWidth) {
1103
1104
1106 }
1109}
1110
1113}
1114
1117 return *this;
1118 rotateAmt %= BitWidth;
1119 if (rotateAmt == 0)
1120 return *this;
1121 return shl(rotateAmt) | lshr(BitWidth - rotateAmt);
1122}
1123
1126}
1127
1129 if (BitWidth == 0)
1130 return *this;
1131 rotateAmt %= BitWidth;
1132 if (rotateAmt == 0)
1133 return *this;
1134 return lshr(rotateAmt) | shl(BitWidth - rotateAmt);
1135}
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1147
1148
1149
1150 if (BitWidth == 1)
1151 return U.VAL - 1;
1152
1153
1155 return UINT32_MAX;
1156
1157
1158
1159
1160
1161
1163 return lg + unsigned((*this)[lg - 1]);
1164}
1165
1166
1167
1168
1169
1170
1171
1172
1174
1175
1177
1178
1179
1180 if (magnitude <= 5) {
1181 static const uint8_t results[32] = {
1182 0,
1183 1, 1,
1184 2, 2, 2, 2,
1185 3, 3, 3, 3, 3, 3,
1186 4, 4, 4, 4, 4, 4, 4, 4,
1187 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1188 6
1189 };
1190 return APInt(BitWidth, results[ (isSingleWord() ? U.VAL : U.pVal[0]) ]);
1191 }
1192
1193
1194
1195
1196
1197 if (magnitude < 52) {
1198 return APInt(BitWidth,
1200 : U.pVal[0])))));
1201 }
1202
1203
1204
1205
1206
1207
1208 unsigned nbits = BitWidth, i = 4;
1209 APInt testy(BitWidth, 16);
1210 APInt x_old(BitWidth, 1);
1211 APInt x_new(BitWidth, 0);
1212 APInt two(BitWidth, 2);
1213
1214
1215 for (;; i += 2, testy = testy.shl(2))
1216 if (i >= nbits || this->ule(testy)) {
1217 x_old = x_old.shl(i / 2);
1218 break;
1219 }
1220
1221
1222 for (;;) {
1223 x_new = (this->udiv(x_old) + x_old).udiv(two);
1224 if (x_old.ule(x_new))
1225 break;
1226 x_old = x_new;
1227 }
1228
1229
1230
1231
1232
1233
1234
1235 APInt square(x_old * x_old);
1236 APInt nextSquare((x_old + 1) * (x_old +1));
1237 if (this->ult(square))
1238 return x_old;
1239 assert(this->ule(nextSquare) && "Error in APInt::sqrt computation");
1240 APInt midpoint((nextSquare - square).udiv(two));
1241 APInt offset(*this - square);
1242 if (offset.ult(midpoint))
1243 return x_old;
1244 return x_old + 1;
1245}
1246
1247
1249 assert((*this)[0] &&
1250 "multiplicative inverse is only defined for odd numbers!");
1251
1252
1253 APInt Factor = *this;
1255 while (!(T = *this * Factor).isOne())
1256 Factor *= 2 - std::move(T);
1257 return Factor;
1258}
1259
1260
1261
1262
1263
1265 unsigned m, unsigned n) {
1266 assert(u && "Must provide dividend");
1267 assert(v && "Must provide divisor");
1268 assert(q && "Must provide quotient");
1269 assert(u != v && u != q && v != q && "Must use different memory");
1270 assert(n>1 && "n must be > 1");
1271
1272
1274
1275
1276
1277#ifdef KNUTH_DEBUG
1278#define DEBUG_KNUTH(X) LLVM_DEBUG(X)
1279#else
1280#define DEBUG_KNUTH(X) do {} while(false)
1281#endif
1282
1283 DEBUG_KNUTH(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n');
1285 DEBUG_KNUTH(for (int i = m + n; i >= 0; i--) dbgs() << " " << u[i]);
1287 DEBUG_KNUTH(for (int i = n; i > 0; i--) dbgs() << " " << v[i - 1]);
1289
1290
1291
1292
1293
1294
1295
1296
1300 if (shift) {
1301 for (unsigned i = 0; i < m+n; ++i) {
1302 uint32_t u_tmp = u[i] >> (32 - shift);
1303 u[i] = (u[i] << shift) | u_carry;
1304 u_carry = u_tmp;
1305 }
1306 for (unsigned i = 0; i < n; ++i) {
1307 uint32_t v_tmp = v[i] >> (32 - shift);
1308 v[i] = (v[i] << shift) | v_carry;
1309 v_carry = v_tmp;
1310 }
1311 }
1312 u[m+n] = u_carry;
1313
1315 DEBUG_KNUTH(for (int i = m + n; i >= 0; i--) dbgs() << " " << u[i]);
1317 DEBUG_KNUTH(for (int i = n; i > 0; i--) dbgs() << " " << v[i - 1]);
1319
1320
1321 int j = m;
1322 do {
1323 DEBUG_KNUTH(dbgs() << "KnuthDiv: quotient digit #" << j << '\n');
1324
1325
1326
1327
1328
1329
1330
1331
1333 DEBUG_KNUTH(dbgs() << "KnuthDiv: dividend == " << dividend << '\n');
1334 uint64_t qp = dividend / v[n-1];
1335 uint64_t rp = dividend % v[n-1];
1336 if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
1337 qp--;
1338 rp += v[n-1];
1339 if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
1340 qp--;
1341 }
1342 DEBUG_KNUTH(dbgs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352 int64_t borrow = 0;
1353 for (unsigned i = 0; i < n; ++i) {
1355 int64_t subres = int64_t(u[j+i]) - borrow - Lo_32(p);
1356 u[j+i] = Lo_32(subres);
1359 << ", borrow = " << borrow << '\n');
1360 }
1361 bool isNeg = u[j+n] < borrow;
1362 u[j+n] -= Lo_32(borrow);
1363
1365 DEBUG_KNUTH(for (int i = m + n; i >= 0; i--) dbgs() << " " << u[i]);
1367
1368
1369
1370 q[j] = Lo_32(qp);
1372
1373
1374
1375 q[j]--;
1376
1377
1378
1379 bool carry = false;
1380 for (unsigned i = 0; i < n; i++) {
1381 uint32_t limit = std::min(u[j+i],v[i]);
1382 u[j+i] += v[i] + carry;
1383 carry = u[j+i] < limit || (carry && u[j+i] == limit);
1384 }
1385 u[j+n] += carry;
1386 }
1388 DEBUG_KNUTH(for (int i = m + n; i >= 0; i--) dbgs() << " " << u[i]);
1389 DEBUG_KNUTH(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n');
1390
1391
1392 } while (--j >= 0);
1393
1395 DEBUG_KNUTH(for (int i = m; i >= 0; i--) dbgs() << " " << q[i]);
1397
1398
1399
1400
1401 if (r) {
1402
1403
1404
1405 if (shift) {
1408 for (int i = n-1; i >= 0; i--) {
1409 r[i] = (u[i] >> shift) | carry;
1410 carry = u[i] << (32 - shift);
1412 }
1413 } else {
1414 for (int i = n-1; i >= 0; i--) {
1415 r[i] = u[i];
1417 }
1418 }
1420 }
1422}
1423
1424void APInt::divide(const WordType *LHS, unsigned lhsWords, const WordType *RHS,
1425 unsigned rhsWords, WordType *Quotient, WordType *Remainder) {
1426 assert(lhsWords >= rhsWords && "Fractional result");
1427
1428
1429
1430
1431
1432
1433
1434
1435 unsigned n = rhsWords * 2;
1436 unsigned m = (lhsWords * 2) - n;
1437
1438
1439
1445 if ((Remainder?4:3)*n+2*m+1 <= 128) {
1446 U = &SPACE[0];
1447 V = &SPACE[m+n+1];
1448 Q = &SPACE[(m+n+1) + n];
1449 if (Remainder)
1450 R = &SPACE[(m+n+1) + n + (m+n)];
1451 } else {
1455 if (Remainder)
1457 }
1458
1459
1460 memset(U, 0, (m+n+1)*sizeof(uint32_t));
1461 for (unsigned i = 0; i < lhsWords; ++i) {
1464 U[i * 2 + 1] = Hi_32(tmp);
1465 }
1466 U[m+n] = 0;
1467
1468
1469 memset(V, 0, (n)*sizeof(uint32_t));
1470 for (unsigned i = 0; i < rhsWords; ++i) {
1473 V[i * 2 + 1] = Hi_32(tmp);
1474 }
1475
1476
1477 memset(Q, 0, (m+n) * sizeof(uint32_t));
1478 if (Remainder)
1479 memset(R, 0, n * sizeof(uint32_t));
1480
1481
1482
1483
1484
1485 for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
1486 n--;
1487 m++;
1488 }
1489 for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
1490 m--;
1491
1492
1493
1494
1495
1496
1497
1498 assert(n != 0 && "Divide by zero?");
1499 if (n == 1) {
1502 for (int i = m; i >= 0; i--) {
1504 if (partial_dividend == 0) {
1505 Q[i] = 0;
1506 remainder = 0;
1507 } else if (partial_dividend < divisor) {
1508 Q[i] = 0;
1509 remainder = Lo_32(partial_dividend);
1510 } else if (partial_dividend == divisor) {
1511 Q[i] = 1;
1512 remainder = 0;
1513 } else {
1514 Q[i] = Lo_32(partial_dividend / divisor);
1515 remainder = Lo_32(partial_dividend - (Q[i] * divisor));
1516 }
1517 }
1518 if (R)
1519 R[0] = remainder;
1520 } else {
1521
1522
1524 }
1525
1526
1527 if (Quotient) {
1528 for (unsigned i = 0; i < lhsWords; ++i)
1529 Quotient[i] = Make_64(Q[i*2+1], Q[i*2]);
1530 }
1531
1532
1533 if (Remainder) {
1534 for (unsigned i = 0; i < rhsWords; ++i)
1535 Remainder[i] = Make_64(R[i*2+1], R[i*2]);
1536 }
1537
1538
1539 if (U != &SPACE[0]) {
1540 delete [] U;
1541 delete [] V;
1542 delete [] Q;
1543 delete [] R;
1544 }
1545}
1546
1548 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1549
1550
1552 assert(RHS.U.VAL != 0 && "Divide by zero?");
1553 return APInt(BitWidth, U.VAL / RHS.U.VAL);
1554 }
1555
1556
1558 unsigned rhsBits = RHS.getActiveBits();
1559 unsigned rhsWords = getNumWords(rhsBits);
1560 assert(rhsWords && "Divided by zero???");
1561
1562
1563 if (!lhsWords)
1564
1565 return APInt(BitWidth, 0);
1566 if (rhsBits == 1)
1567
1568 return *this;
1569 if (lhsWords < rhsWords || this->ult(RHS))
1570
1571 return APInt(BitWidth, 0);
1572 if (*this == RHS)
1573
1574 return APInt(BitWidth, 1);
1575 if (lhsWords == 1)
1576
1577 return APInt(BitWidth, this->U.pVal[0] / RHS.U.pVal[0]);
1578
1579
1580 APInt Quotient(BitWidth, 0);
1581 divide(U.pVal, lhsWords, RHS.U.pVal, rhsWords, Quotient.U.pVal, nullptr);
1582 return Quotient;
1583}
1584
1586 assert(RHS != 0 && "Divide by zero?");
1587
1588
1590 return APInt(BitWidth, U.VAL / RHS);
1591
1592
1594
1595
1596 if (!lhsWords)
1597
1598 return APInt(BitWidth, 0);
1599 if (RHS == 1)
1600
1601 return *this;
1602 if (this->ult(RHS))
1603
1604 return APInt(BitWidth, 0);
1605 if (*this == RHS)
1606
1607 return APInt(BitWidth, 1);
1608 if (lhsWords == 1)
1609
1610 return APInt(BitWidth, this->U.pVal[0] / RHS);
1611
1612
1613 APInt Quotient(BitWidth, 0);
1614 divide(U.pVal, lhsWords, &RHS, 1, Quotient.U.pVal, nullptr);
1615 return Quotient;
1616}
1617
1620 if (RHS.isNegative())
1621 return (-(*this)).udiv(-RHS);
1622 return -((-(*this)).udiv(RHS));
1623 }
1624 if (RHS.isNegative())
1625 return -(this->udiv(-RHS));
1626 return this->udiv(RHS);
1627}
1628
1631 if (RHS < 0)
1632 return (-(*this)).udiv(-RHS);
1633 return -((-(*this)).udiv(RHS));
1634 }
1635 if (RHS < 0)
1636 return -(this->udiv(-RHS));
1637 return this->udiv(RHS);
1638}
1639
1641 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1643 assert(RHS.U.VAL != 0 && "Remainder by zero?");
1644 return APInt(BitWidth, U.VAL % RHS.U.VAL);
1645 }
1646
1647
1649
1650
1651 unsigned rhsBits = RHS.getActiveBits();
1652 unsigned rhsWords = getNumWords(rhsBits);
1653 assert(rhsWords && "Performing remainder operation by zero ???");
1654
1655
1656 if (lhsWords == 0)
1657
1658 return APInt(BitWidth, 0);
1659 if (rhsBits == 1)
1660
1661 return APInt(BitWidth, 0);
1662 if (lhsWords < rhsWords || this->ult(RHS))
1664 return *this;
1665 if (*this == RHS)
1666
1667 return APInt(BitWidth, 0);
1668 if (lhsWords == 1)
1669
1670 return APInt(BitWidth, U.pVal[0] % RHS.U.pVal[0]);
1671
1672
1673 APInt Remainder(BitWidth, 0);
1674 divide(U.pVal, lhsWords, RHS.U.pVal, rhsWords, nullptr, Remainder.U.pVal);
1675 return Remainder;
1676}
1677
1679 assert(RHS != 0 && "Remainder by zero?");
1680
1682 return U.VAL % RHS;
1683
1684
1686
1687
1688 if (lhsWords == 0)
1689
1690 return 0;
1691 if (RHS == 1)
1692
1693 return 0;
1694 if (this->ult(RHS))
1695
1697 if (*this == RHS)
1698
1699 return 0;
1700 if (lhsWords == 1)
1701
1702 return U.pVal[0] % RHS;
1703
1704
1706 divide(U.pVal, lhsWords, &RHS, 1, nullptr, &Remainder);
1707 return Remainder;
1708}
1709
1712 if (RHS.isNegative())
1713 return -((-(*this)).urem(-RHS));
1714 return -((-(*this)).urem(RHS));
1715 }
1716 if (RHS.isNegative())
1717 return this->urem(-RHS);
1718 return this->urem(RHS);
1719}
1720
1723 if (RHS < 0)
1724 return -((-(*this)).urem(-RHS));
1725 return -((-(*this)).urem(RHS));
1726 }
1727 if (RHS < 0)
1728 return this->urem(-RHS);
1729 return this->urem(RHS);
1730}
1731
1733 APInt &Quotient, APInt &Remainder) {
1734 assert(LHS.BitWidth == RHS.BitWidth && "Bit widths must be the same");
1735 unsigned BitWidth = LHS.BitWidth;
1736
1737
1738 if (LHS.isSingleWord()) {
1739 assert(RHS.U.VAL != 0 && "Divide by zero?");
1744 return;
1745 }
1746
1747
1748 unsigned lhsWords = getNumWords(LHS.getActiveBits());
1749 unsigned rhsBits = RHS.getActiveBits();
1750 unsigned rhsWords = getNumWords(rhsBits);
1751 assert(rhsWords && "Performing divrem operation by zero ???");
1752
1753
1754 if (lhsWords == 0) {
1757 return;
1758 }
1759
1760 if (rhsBits == 1) {
1761 Quotient = LHS;
1763 }
1764
1765 if (lhsWords < rhsWords || LHS.ult(RHS)) {
1766 Remainder = LHS;
1767 Quotient = APInt(BitWidth, 0);
1768 return;
1769 }
1770
1773 Remainder = APInt(BitWidth, 0);
1774 return;
1775 }
1776
1777
1778
1779
1780
1781 Quotient.reallocate(BitWidth);
1782 Remainder.reallocate(BitWidth);
1783
1784 if (lhsWords == 1) {
1785
1788 Quotient = lhsValue / rhsValue;
1789 Remainder = lhsValue % rhsValue;
1790 return;
1791 }
1792
1793
1794 divide(LHS.U.pVal, lhsWords, RHS.U.pVal, rhsWords, Quotient.U.pVal,
1795 Remainder.U.pVal);
1796
1797 std::memset(Quotient.U.pVal + lhsWords, 0,
1799 std::memset(Remainder.U.pVal + rhsWords, 0,
1801}
1802
1805 assert(RHS != 0 && "Divide by zero?");
1806 unsigned BitWidth = LHS.BitWidth;
1807
1808
1809 if (LHS.isSingleWord()) {
1811 Remainder = LHS.U.VAL % RHS;
1813 return;
1814 }
1815
1816
1817 unsigned lhsWords = getNumWords(LHS.getActiveBits());
1818
1819
1820 if (lhsWords == 0) {
1822 Remainder = 0;
1823 return;
1824 }
1825
1826 if (RHS == 1) {
1827 Quotient = LHS;
1828 Remainder = 0;
1829 return;
1830 }
1831
1833 Remainder = LHS.getZExtValue();
1834 Quotient = APInt(BitWidth, 0);
1835 return;
1836 }
1837
1840 Remainder = 0;
1841 return;
1842 }
1843
1844
1845
1846
1847 Quotient.reallocate(BitWidth);
1848
1849 if (lhsWords == 1) {
1850
1852 Quotient = lhsValue / RHS;
1853 Remainder = lhsValue % RHS;
1854 return;
1855 }
1856
1857
1858 divide(LHS.U.pVal, lhsWords, &RHS, 1, Quotient.U.pVal, &Remainder);
1859
1860 std::memset(Quotient.U.pVal + lhsWords, 0,
1862}
1863
1865 APInt &Quotient, APInt &Remainder) {
1866 if (LHS.isNegative()) {
1867 if (RHS.isNegative())
1869 else {
1872 }
1874 } else if (RHS.isNegative()) {
1877 } else {
1879 }
1880}
1881
1883 APInt &Quotient, int64_t &Remainder) {
1885 if (LHS.isNegative()) {
1886 if (RHS < 0)
1888 else {
1891 }
1892 R = -R;
1893 } else if (RHS < 0) {
1896 } else {
1898 }
1899 Remainder = R;
1900}
1901
1906 return Res;
1907}
1908
1912 return Res;
1913}
1914
1919 return Res;
1920}
1921
1924 Overflow = Res.ugt(*this);
1925 return Res;
1926}
1927
1929
1932}
1933
1936
1937 if (RHS != 0)
1938 Overflow = Res.sdiv(RHS) != *this ||
1940 else
1941 Overflow = false;
1942 return Res;
1943}
1944
1946 if (countl_zero() + RHS.countl_zero() + 2 <= BitWidth) {
1947 Overflow = true;
1948 return *this * RHS;
1949 }
1950
1953 Res <<= 1;
1954 if ((*this)[0]) {
1955 Res += RHS;
1957 Overflow = true;
1958 }
1959 return Res;
1960}
1961
1964}
1965
1968 if (Overflow)
1969 return APInt(BitWidth, 0);
1970
1971 if (isNonNegative())
1973 else
1975
1976 return *this << ShAmt;
1977}
1978
1981}
1982
1985 if (Overflow)
1986 return APInt(BitWidth, 0);
1987
1989
1990 return *this << ShAmt;
1991}
1992
1995 if ((quotient * RHS != *this) && (isNegative() != RHS.isNegative()))
1996 return quotient - 1;
1997 return quotient;
1998}
1999
2001 bool Overflow;
2003 if (!Overflow)
2004 return Res;
2005
2008}
2009
2011 bool Overflow;
2013 if (!Overflow)
2014 return Res;
2015
2017}
2018
2020 bool Overflow;
2022 if (!Overflow)
2023 return Res;
2024
2027}
2028
2030 bool Overflow;
2032 if (!Overflow)
2033 return Res;
2034
2035 return APInt(BitWidth, 0);
2036}
2037
2039 bool Overflow;
2041 if (!Overflow)
2042 return Res;
2043
2044
2045 bool ResIsNegative = isNegative() ^ RHS.isNegative();
2046
2049}
2050
2052 bool Overflow;
2054 if (!Overflow)
2055 return Res;
2056
2058}
2059
2062}
2063
2065 bool Overflow;
2067 if (!Overflow)
2068 return Res;
2069
2072}
2073
2076}
2077
2079 bool Overflow;
2081 if (!Overflow)
2082 return Res;
2083
2085}
2086
2087void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) {
2088
2089 assert(!str.empty() && "Invalid string length");
2090 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
2091 radix == 36) &&
2092 "Radix should be 2, 8, 10, 16, or 36!");
2093
2095 size_t slen = str.size();
2096 bool isNeg = *p == '-';
2097 if (*p == '-' || *p == '+') {
2098 p++;
2099 slen--;
2100 assert(slen && "String is only a sign, needs a value.");
2101 }
2102 assert((slen <= numbits || radix != 2) && "Insufficient bit width");
2103 assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width");
2104 assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width");
2105 assert((((slen-1)*64)/22 <= numbits || radix != 10) &&
2106 "Insufficient bit width");
2107
2108
2110 U.VAL = 0;
2111 else
2113
2114
2115 unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
2116
2117
2119 unsigned digit = getDigit(*p, radix);
2120 assert(digit < radix && "Invalid character in digit string");
2121
2122
2123 if (slen > 1) {
2124 if (shift)
2125 *this <<= shift;
2126 else
2127 *this *= radix;
2128 }
2129
2130
2131 *this += digit;
2132 }
2133
2136}
2137
2139 bool formatAsCLiteral, bool UpperCase,
2140 bool InsertSeparators) const {
2141 assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 ||
2142 Radix == 36) &&
2143 "Radix should be 2, 8, 10, 16, or 36!");
2144
2145 const char *Prefix = "";
2146 if (formatAsCLiteral) {
2147 switch (Radix) {
2148 case 2:
2149
2150
2151 Prefix = "0b";
2152 break;
2153 case 8:
2154 Prefix = "0";
2155 break;
2156 case 10:
2157 break;
2158 case 16:
2159 Prefix = "0x";
2160 break;
2161 default:
2163 }
2164 }
2165
2166
2167 unsigned Grouping = (Radix == 8 || Radix == 10) ? 3 : 4;
2168
2169
2171 while (*Prefix) {
2172 Str.push_back(*Prefix);
2173 ++Prefix;
2174 };
2175 Str.push_back('0');
2176 return;
2177 }
2178
2179 static const char BothDigits[] = "0123456789abcdefghijklmnopqrstuvwxyz"
2180 "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
2181 const char *Digits = BothDigits + (UpperCase ? 36 : 0);
2182
2184 char Buffer[65];
2185 char *BufPtr = std::end(Buffer);
2186
2190 } else {
2192 if (I >= 0) {
2194 } else {
2195 Str.push_back('-');
2197 }
2198 }
2199
2200 while (*Prefix) {
2201 Str.push_back(*Prefix);
2202 ++Prefix;
2203 };
2204
2205 int Pos = 0;
2206 while (N) {
2207 if (InsertSeparators && Pos % Grouping == 0 && Pos > 0)
2208 *--BufPtr = '\'';
2209 *--BufPtr = Digits[N % Radix];
2210 N /= Radix;
2211 Pos++;
2212 }
2213 Str.append(BufPtr, std::end(Buffer));
2214 return;
2215 }
2216
2217 APInt Tmp(*this);
2218
2220
2221
2222
2224 Str.push_back('-');
2225 }
2226
2227 while (*Prefix) {
2228 Str.push_back(*Prefix);
2229 ++Prefix;
2230 }
2231
2232
2233 unsigned StartDig = Str.size();
2234
2235
2236
2237
2238 if (Radix == 2 || Radix == 8 || Radix == 16) {
2239
2240 unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
2241 unsigned MaskAmt = Radix - 1;
2242
2243 int Pos = 0;
2246 if (InsertSeparators && Pos % Grouping == 0 && Pos > 0)
2247 Str.push_back('\'');
2248
2249 Str.push_back(Digits[Digit]);
2251 Pos++;
2252 }
2253 } else {
2254 int Pos = 0;
2257 udivrem(Tmp, Radix, Tmp, Digit);
2258 assert(Digit < Radix && "divide failed");
2259 if (InsertSeparators && Pos % Grouping == 0 && Pos > 0)
2260 Str.push_back('\'');
2261
2262 Str.push_back(Digits[Digit]);
2263 Pos++;
2264 }
2265 }
2266
2267
2268 std::reverse(Str.begin()+StartDig, Str.end());
2269}
2270
2271#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2276 dbgs() << "APInt(" << BitWidth << "b, "
2277 << U << "u " << S << "s)\n";
2278}
2279#endif
2280
2283 this->toString(S, 10, isSigned, false);
2284 OS << S;
2285}
2286
2287
2288
2289
2290
2291
2293 "Part width must be divisible by 2!");
2294
2295
2296
2300}
2301
2302
2305}
2306
2307
2310}
2311
2312
2313
2316 dst[0] = part;
2317 for (unsigned i = 1; i < parts; i++)
2318 dst[i] = 0;
2319}
2320
2321
2323 for (unsigned i = 0; i < parts; i++)
2324 dst[i] = src[i];
2325}
2326
2327
2329 for (unsigned i = 0; i < parts; i++)
2330 if (src[i])
2331 return false;
2332
2333 return true;
2334}
2335
2336
2338 return (parts[whichWord(bit)] & maskBit(bit)) != 0;
2339}
2340
2341
2343 parts[whichWord(bit)] |= maskBit(bit);
2344}
2345
2346
2348 parts[whichWord(bit)] &= ~maskBit(bit);
2349}
2350
2351
2352
2354 for (unsigned i = 0; i < n; i++) {
2355 if (parts[i] != 0) {
2358 }
2359 }
2360
2361 return UINT_MAX;
2362}
2363
2364
2365
2367 do {
2368 --n;
2369
2370 if (parts[n] != 0) {
2371 static_assert(sizeof(parts[n]) <= sizeof(uint64_t));
2373
2375 }
2376 } while (n);
2377
2378 return UINT_MAX;
2379}
2380
2381
2382
2383
2384
2385void
2387 unsigned srcBits, unsigned srcLSB) {
2389 assert(dstParts <= dstCount);
2390
2392 tcAssign(dst, src + firstSrcPart, dstParts);
2393
2396
2397
2398
2399
2401 if (n < srcBits) {
2403 dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
2405 } else if (n > srcBits) {
2408 }
2409
2410
2411 while (dstParts < dstCount)
2412 dst[dstParts++] = 0;
2413}
2414
2415
2417 WordType c, unsigned parts) {
2419
2420 for (unsigned i = 0; i < parts; i++) {
2422 if (c) {
2423 dst[i] += rhs[i] + 1;
2424 c = (dst[i] <= l);
2425 } else {
2426 dst[i] += rhs[i];
2427 c = (dst[i] < l);
2428 }
2429 }
2430
2431 return c;
2432}
2433
2434
2435
2436
2437
2439 unsigned parts) {
2440 for (unsigned i = 0; i < parts; ++i) {
2441 dst[i] += src;
2442 if (dst[i] >= src)
2443 return 0;
2444 src = 1;
2445 }
2446
2447 return 1;
2448}
2449
2450
2452 WordType c, unsigned parts) {
2454
2455 for (unsigned i = 0; i < parts; i++) {
2457 if (c) {
2458 dst[i] -= rhs[i] + 1;
2459 c = (dst[i] >= l);
2460 } else {
2461 dst[i] -= rhs[i];
2462 c = (dst[i] > l);
2463 }
2464 }
2465
2466 return c;
2467}
2468
2469
2470
2471
2472
2473
2474
2475
2477 unsigned parts) {
2478 for (unsigned i = 0; i < parts; ++i) {
2480 dst[i] -= src;
2481 if (src <= Dst)
2482 return 0;
2483 src = 1;
2484 }
2485
2486 return 1;
2487}
2488
2489
2493}
2494
2495
2496
2497
2498
2499
2500
2501
2502
2503
2506 unsigned srcParts, unsigned dstParts,
2507 bool add) {
2508
2509 assert(dst <= src || dst >= src + srcParts);
2510 assert(dstParts <= srcParts + 1);
2511
2512
2513 unsigned n = std::min(dstParts, srcParts);
2514
2515 for (unsigned i = 0; i < n; i++) {
2516
2517
2518
2519
2522 if (multiplier == 0 || srcPart == 0) {
2523 low = carry;
2524 high = 0;
2525 } else {
2528
2532 if (low + mid < low)
2533 high++;
2534 low += mid;
2535
2539 if (low + mid < low)
2540 high++;
2541 low += mid;
2542
2543
2544 if (low + carry < low)
2545 high++;
2546 low += carry;
2547 }
2548
2549 if (add) {
2550
2551 if (low + dst[i] < low)
2552 high++;
2553 dst[i] += low;
2554 } else
2555 dst[i] = low;
2556
2557 carry = high;
2558 }
2559
2560 if (srcParts < dstParts) {
2561
2562 assert(srcParts + 1 == dstParts);
2563 dst[srcParts] = carry;
2564 return 0;
2565 }
2566
2567
2568 if (carry)
2569 return 1;
2570
2571
2572
2573
2574 if (multiplier)
2575 for (unsigned i = dstParts; i < srcParts; i++)
2576 if (src[i])
2577 return 1;
2578
2579
2580 return 0;
2581}
2582
2583
2584
2585
2586
2588 const WordType *rhs, unsigned parts) {
2589 assert(dst != lhs && dst != rhs);
2590
2591 int overflow = 0;
2592
2593 for (unsigned i = 0; i < parts; i++) {
2594
2595
2596 overflow |=
2597 tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts, parts - i, i != 0);
2598 }
2599
2600 return overflow;
2601}
2602
2603
2604
2606 const WordType *rhs, unsigned lhsParts,
2607 unsigned rhsParts) {
2608
2609 if (lhsParts > rhsParts)
2610 return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
2611
2612 assert(dst != lhs && dst != rhs);
2613
2614 for (unsigned i = 0; i < lhsParts; i++) {
2615
2616
2617 tcMultiplyPart(&dst[i], rhs, lhs[i], 0, rhsParts, rhsParts + 1, i != 0);
2618 }
2619}
2620
2621
2622
2623
2624
2625
2626
2627
2628
2629
2632 unsigned parts) {
2633 assert(lhs != remainder && lhs != srhs && remainder != srhs);
2634
2635 unsigned shiftCount = tcMSB(rhs, parts) + 1;
2636 if (shiftCount == 0)
2637 return true;
2638
2642
2645 tcAssign(remainder, lhs, parts);
2646 tcSet(lhs, 0, parts);
2647
2648
2649
2650 for (;;) {
2651 int compare = tcCompare(remainder, srhs, parts);
2652 if (compare >= 0) {
2653 tcSubtract(remainder, srhs, 0, parts);
2654 lhs[n] |= mask;
2655 }
2656
2657 if (shiftCount == 0)
2658 break;
2659 shiftCount--;
2661 if ((mask >>= 1) == 0) {
2663 n--;
2664 }
2665 }
2666
2667 return false;
2668}
2669
2670
2671
2673
2674 if (!Count)
2675 return;
2676
2677
2680
2681
2682 if (BitShift == 0) {
2683 std::memmove(Dst + WordShift, Dst, (Words - WordShift) * APINT_WORD_SIZE);
2684 } else {
2685 while (Words-- > WordShift) {
2686 Dst[Words] = Dst[Words - WordShift] << BitShift;
2687 if (Words > WordShift)
2688 Dst[Words] |=
2690 }
2691 }
2692
2693
2695}
2696
2697
2698
2700
2701 if (!Count)
2702 return;
2703
2704
2707
2708 unsigned WordsToMove = Words - WordShift;
2709
2710 if (BitShift == 0) {
2711 std::memmove(Dst, Dst + WordShift, WordsToMove * APINT_WORD_SIZE);
2712 } else {
2713 for (unsigned i = 0; i != WordsToMove; ++i) {
2714 Dst[i] = Dst[i + WordShift] >> BitShift;
2715 if (i + 1 != WordsToMove)
2717 }
2718 }
2719
2720
2721 std::memset(Dst + WordsToMove, 0, WordShift * APINT_WORD_SIZE);
2722}
2723
2724
2726 unsigned parts) {
2727 while (parts) {
2728 parts--;
2729 if (lhs[parts] != rhs[parts])
2730 return (lhs[parts] > rhs[parts]) ? 1 : -1;
2731 }
2732
2733 return 0;
2734}
2735
2738
2739 switch (RM) {
2747 return Quo;
2748 return Quo + 1;
2749 }
2750 }
2752}
2753
2756 switch (RM) {
2762 return Quo;
2763
2764
2765
2766
2767
2770 return Quo - 1;
2771 return Quo;
2772 }
2774 return Quo;
2775 return Quo + 1;
2776 }
2777
2780 }
2782}
2783
2784std::optional
2786 unsigned RangeWidth) {
2787 unsigned CoeffWidth = A.getBitWidth();
2788 assert(CoeffWidth == B.getBitWidth() && CoeffWidth == C.getBitWidth());
2789 assert(RangeWidth <= CoeffWidth &&
2790 "Value range width should be less than coefficient width");
2791 assert(RangeWidth > 1 && "Value range bit width should be > 1");
2792
2793 LLVM_DEBUG(dbgs() << __func__ << ": solving " << A << "x^2 + " << B
2794 << "x + " << C << ", rw:" << RangeWidth << '\n');
2795
2796
2797 if (C.sextOrTrunc(RangeWidth).isZero()) {
2798 LLVM_DEBUG(dbgs() << __func__ << ": zero solution\n");
2799 return APInt(CoeffWidth, 0);
2800 }
2801
2802
2803
2804
2805
2806
2807
2808
2809
2810
2811
2812
2813
2814
2815
2816 CoeffWidth *= 3;
2820
2821
2822
2823 if (A.isNegative()) {
2824 A.negate();
2825 B.negate();
2826 C.negate();
2827 }
2828
2829
2830
2831
2832
2833
2834
2835
2836
2837
2838
2839
2840
2841
2842
2843
2844
2845
2846
2847
2848
2849
2850
2854 bool PickLow;
2855
2856 auto RoundUp = [] (const APInt &V, const APInt &A) -> APInt {
2857 assert(A.isStrictlyPositive());
2858 APInt T = V.abs().urem(A);
2859 if (T.isZero())
2860 return V;
2861 return V.isNegative() ? V+T : V+(A-T);
2862 };
2863
2864
2865
2866 if (B.isNonNegative()) {
2867
2868
2869
2870
2872 if (C.isStrictlyPositive())
2873 C -= R;
2874
2875 PickLow = false;
2876 } else {
2877
2878
2879
2880
2881 APInt LowkR = C - SqrB.udiv(2*TwoA);
2882
2883 LowkR = RoundUp(LowkR, R);
2884
2885
2886
2887
2888
2889
2890 if (C.sgt(LowkR)) {
2891
2892
2894
2895 PickLow = true;
2896 } else {
2897
2898
2899
2900
2901
2902
2903
2904 C -= LowkR;
2905
2906 PickLow = false;
2907 }
2908 }
2909
2910 LLVM_DEBUG(dbgs() << __func__ << ": updated coefficients " << A << "x^2 + "
2911 << B << "x + " << C << ", rw:" << RangeWidth << '\n');
2912
2914 assert(D.isNonNegative() && "Negative discriminant");
2916
2917 APInt Q = SQ * SQ;
2918 bool InexactSQ = Q != D;
2919
2920
2922 SQ -= 1;
2923
2926
2927
2928
2929
2930
2931
2932
2933 if (PickLow)
2935 else
2937
2938
2939
2940
2941 assert(X.isNonNegative() && "Solution should be non-negative");
2942
2943 if (!InexactSQ && Rem.isZero()) {
2944 LLVM_DEBUG(dbgs() << __func__ << ": solution (root): " << X << '\n');
2945 return X;
2946 }
2947
2948 assert((SQ*SQ).sle(D) && "SQ = |_sqrt(D)_|, so SQ*SQ <= D");
2949
2950
2951
2952
2953
2954
2955
2956
2958 APInt VY = VX + TwoA*X + A + B;
2959 bool SignChange =
2961
2962
2963
2964 if (!SignChange) {
2965 LLVM_DEBUG(dbgs() << __func__ << ": no valid solution\n");
2966 return std::nullopt;
2967 }
2968
2969 X += 1;
2970 LLVM_DEBUG(dbgs() << __func__ << ": solution (wrap): " << X << '\n');
2971 return X;
2972}
2973
2974std::optional
2976 assert(A.getBitWidth() == B.getBitWidth() && "Must have the same bitwidth");
2978 return std::nullopt;
2979 return A.getBitWidth() - ((A ^ B).countl_zero() + 1);
2980}
2981
2983 bool MatchAllBits) {
2984 unsigned OldBitWidth = A.getBitWidth();
2985 assert((((OldBitWidth % NewBitWidth) == 0) ||
2986 ((NewBitWidth % OldBitWidth) == 0)) &&
2987 "One size should be a multiple of the other one. "
2988 "Can't do fractional scaling.");
2989
2990
2991 if (OldBitWidth == NewBitWidth)
2992 return A;
2993
2995
2996
2997 if (A.isZero())
2998 return NewA;
2999
3000 if (NewBitWidth > OldBitWidth) {
3001
3002 unsigned Scale = NewBitWidth / OldBitWidth;
3003 for (unsigned i = 0; i != OldBitWidth; ++i)
3004 if (A[i])
3005 NewA.setBits(i * Scale, (i + 1) * Scale);
3006 } else {
3007 unsigned Scale = OldBitWidth / NewBitWidth;
3008 for (unsigned i = 0; i != NewBitWidth; ++i) {
3009 if (MatchAllBits) {
3010 if (A.extractBits(Scale, i * Scale).isAllOnes())
3012 } else {
3013 if (.extractBits(Scale, i * Scale).isZero())
3015 }
3016 }
3017 }
3018
3019 return NewA;
3020}
3021
3022
3023
3025 unsigned StoreBytes) {
3026 assert((IntVal.getBitWidth()+7)/8 >= StoreBytes && "Integer too small!");
3027 const uint8_t *Src = (const uint8_t *)IntVal.getRawData();
3028
3030
3031
3032 memcpy(Dst, Src, StoreBytes);
3033 } else {
3034
3035
3036
3037 while (StoreBytes > sizeof(uint64_t)) {
3038 StoreBytes -= sizeof(uint64_t);
3039
3040 memcpy(Dst + StoreBytes, Src, sizeof(uint64_t));
3042 }
3043
3044 memcpy(Dst, Src + sizeof(uint64_t) - StoreBytes, StoreBytes);
3045 }
3046}
3047
3048
3049
3051 unsigned LoadBytes) {
3052 assert((IntVal.getBitWidth()+7)/8 >= LoadBytes && "Integer too small!");
3054 const_cast<uint64_t *>(IntVal.getRawData()));
3055
3057
3058
3059 memcpy(Dst, Src, LoadBytes);
3060 else {
3061
3062
3063
3064
3065 while (LoadBytes > sizeof(uint64_t)) {
3066 LoadBytes -= sizeof(uint64_t);
3067
3068 memcpy(Dst, Src + LoadBytes, sizeof(uint64_t));
3070 }
3071
3072 memcpy(Dst + sizeof(uint64_t) - LoadBytes, Src, LoadBytes);
3073 }
3074}
3075
3077
3078 return (C1 & C2) + (C1 ^ C2).ashr(1);
3079}
3080
3082
3083 return (C1 & C2) + (C1 ^ C2).lshr(1);
3084}
3085
3087
3088 return (C1 | C2) - (C1 ^ C2).ashr(1);
3089}
3090
3092
3093 return (C1 | C2) - (C1 ^ C2).lshr(1);
3094}
3095
3098 unsigned FullWidth = C1.getBitWidth() * 2;
3099 APInt C1Ext = C1.sext(FullWidth);
3100 APInt C2Ext = C2.sext(FullWidth);
3102}
3103
3106 unsigned FullWidth = C1.getBitWidth() * 2;
3107 APInt C1Ext = C1.zext(FullWidth);
3108 APInt C2Ext = C2.zext(FullWidth);
3110}
3111
3113 assert(N >= 0 && "negative exponents not supported.");
3115 if (N == 0)
3116 return Acc;
3118 int64_t RemainingExponent = N;
3119 while (RemainingExponent > 0) {
3120 while (RemainingExponent % 2 == 0) {
3122 RemainingExponent /= 2;
3123 }
3124 --RemainingExponent;
3125 Acc *= Base;
3126 }
3127 return Acc;
3128}
static APInt::WordType lowHalf(APInt::WordType part)
Returns the value of the lower half of PART.
static unsigned rotateModulo(unsigned BitWidth, const APInt &rotateAmt)
static APInt::WordType highHalf(APInt::WordType part)
Returns the value of the upper half of PART.
static void tcComplement(APInt::WordType *dst, unsigned parts)
static unsigned getDigit(char cdigit, uint8_t radix)
A utility function that converts a character to a digit.
static APInt::WordType lowBitMask(unsigned bits)
static uint64_t * getMemory(unsigned numWords)
A utility function for allocating memory and checking for allocation failure.
static void KnuthDiv(uint32_t *u, uint32_t *v, uint32_t *q, uint32_t *r, unsigned m, unsigned n)
Implementation of Knuth's Algorithm D (Division of nonnegative integers) from "Art of Computer Progra...
static uint64_t * getClearedMemory(unsigned numWords)
A utility function for allocating memory, checking for allocation failures, and ensuring the contents...
This file implements a class to represent arbitrary precision integral constant values and operations...
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
#define LLVM_UNLIKELY(EXPR)
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
static bool isNeg(Value *V)
Returns true if the operation is a negation of V, and it works for both integers and floats.
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
static bool isSigned(unsigned int Opcode)
This file defines a hash set that can be used to remove duplication of nodes in a graph.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallString class.
This file implements the C++20 header.
Class for arbitrary precision integers.
APInt umul_ov(const APInt &RHS, bool &Overflow) const
APInt usub_sat(const APInt &RHS) const
APInt udiv(const APInt &RHS) const
Unsigned division operation.
static void tcSetBit(WordType *, unsigned bit)
Set the given bit of a bignum. Zero-based.
static void tcSet(WordType *, WordType, unsigned)
Sets the least significant part of a bignum to the input value, and zeroes out higher parts.
unsigned nearestLogBase2() const
static void udivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, APInt &Remainder)
Dual division/remainder interface.
APInt getLoBits(unsigned numBits) const
Compute an APInt containing numBits lowbits from this APInt.
static int tcExtractBit(const WordType *, unsigned bit)
Extract the given bit of a bignum; returns 0 or 1. Zero-based.
bool isAligned(Align A) const
Checks if this APInt -interpreted as an address- is aligned to the provided value.
APInt zext(unsigned width) const
Zero extend to a new width.
bool isMinSignedValue() const
Determine if this is the smallest signed value.
uint64_t getZExtValue() const
Get zero extended value.
APInt truncUSat(unsigned width) const
Truncate to new width with unsigned saturation.
uint64_t * pVal
Used to store the >64 bits integer value.
static void sdivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, APInt &Remainder)
static WordType tcAdd(WordType *, const WordType *, WordType carry, unsigned)
DST += RHS + CARRY where CARRY is zero or one. Returns the carry flag.
static void tcExtract(WordType *, unsigned dstCount, const WordType *, unsigned srcBits, unsigned srcLSB)
Copy the bit vector of width srcBITS from SRC, starting at bit srcLSB, to DST, of dstCOUNT parts,...
uint64_t extractBitsAsZExtValue(unsigned numBits, unsigned bitPosition) const
APInt getHiBits(unsigned numBits) const
Compute an APInt containing numBits highbits from this APInt.
APInt zextOrTrunc(unsigned width) const
Zero extend or truncate to width.
unsigned getActiveBits() const
Compute the number of active bits in the value.
static unsigned getSufficientBitsNeeded(StringRef Str, uint8_t Radix)
Get the bits that are sufficient to represent the string value.
APInt trunc(unsigned width) const
Truncate to new width.
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
void setBit(unsigned BitPosition)
Set the given bit to 1 whose position is given as "bitPosition".
void toStringUnsigned(SmallVectorImpl< char > &Str, unsigned Radix=10) const
Considers the APInt to be unsigned and converts it into a string in the radix given.
APInt sshl_ov(const APInt &Amt, bool &Overflow) const
APInt smul_sat(const APInt &RHS) const
APInt sadd_sat(const APInt &RHS) const
bool sgt(const APInt &RHS) const
Signed greater than comparison.
static int tcCompare(const WordType *, const WordType *, unsigned)
Comparison (unsigned) of two bignums.
APInt & operator++()
Prefix increment operator.
APInt usub_ov(const APInt &RHS, bool &Overflow) const
bool ugt(const APInt &RHS) const
Unsigned greater than comparison.
void print(raw_ostream &OS, bool isSigned) const
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
APInt urem(const APInt &RHS) const
Unsigned remainder operation.
static void tcAssign(WordType *, const WordType *, unsigned)
Assign one bignum to another.
static constexpr unsigned APINT_WORD_SIZE
Byte size of a word.
unsigned getBitWidth() const
Return the number of bits in the APInt.
static void tcShiftRight(WordType *, unsigned Words, unsigned Count)
Shift a bignum right Count bits.
static void tcFullMultiply(WordType *, const WordType *, const WordType *, unsigned, unsigned)
DST = LHS * RHS, where DST has width the sum of the widths of the operands.
bool ult(const APInt &RHS) const
Unsigned less than comparison.
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
APInt sfloordiv_ov(const APInt &RHS, bool &Overflow) const
Signed integer floor division operation.
bool isSingleWord() const
Determine if this APInt just has one word to store value.
unsigned getNumWords() const
Get the number of words.
APInt()
Default constructor that creates an APInt with a 1-bit zero value.
bool isNegative() const
Determine sign of this APInt.
APInt sadd_ov(const APInt &RHS, bool &Overflow) const
APInt & operator<<=(unsigned ShiftAmt)
Left-shift assignment function.
APInt sdiv(const APInt &RHS) const
Signed division function for APInt.
double roundToDouble() const
Converts this unsigned APInt to a double value.
APInt rotr(unsigned rotateAmt) const
Rotate right by rotateAmt.
APInt reverseBits() const
void ashrInPlace(unsigned ShiftAmt)
Arithmetic right-shift this APInt by ShiftAmt in place.
APInt uadd_ov(const APInt &RHS, bool &Overflow) const
static void tcClearBit(WordType *, unsigned bit)
Clear the given bit of a bignum. Zero-based.
void negate()
Negate this APInt in place.
static WordType tcDecrement(WordType *dst, unsigned parts)
Decrement a bignum in-place. Return the borrow flag.
unsigned countr_zero() const
Count the number of trailing zero bits.
bool isSplat(unsigned SplatSizeInBits) const
Check if the APInt consists of a repeated bit pattern.
APInt & operator-=(const APInt &RHS)
Subtraction assignment operator.
bool isSignedIntN(unsigned N) const
Check if this APInt has an N-bits signed integer value.
APInt sdiv_ov(const APInt &RHS, bool &Overflow) const
APInt operator*(const APInt &RHS) const
Multiplication operator.
static unsigned tcLSB(const WordType *, unsigned n)
Returns the bit number of the least or most significant set bit of a number.
unsigned countl_zero() const
The APInt version of std::countl_zero.
static void tcShiftLeft(WordType *, unsigned Words, unsigned Count)
Shift a bignum left Count bits.
static APInt getSplat(unsigned NewLen, const APInt &V)
Return a value containing V broadcasted over NewLen bits.
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
APInt sshl_sat(const APInt &RHS) const
static constexpr WordType WORDTYPE_MAX
APInt ushl_sat(const APInt &RHS) const
APInt ushl_ov(const APInt &Amt, bool &Overflow) const
static WordType tcSubtractPart(WordType *, WordType, unsigned)
DST -= RHS. Returns the carry flag.
static bool tcIsZero(const WordType *, unsigned)
Returns true if a bignum is zero, false otherwise.
APInt sextOrTrunc(unsigned width) const
Sign extend or truncate to width.
static unsigned tcMSB(const WordType *parts, unsigned n)
Returns the bit number of the most significant set bit of a number.
static int tcDivide(WordType *lhs, const WordType *rhs, WordType *remainder, WordType *scratch, unsigned parts)
If RHS is zero LHS and REMAINDER are left unchanged, return one.
void dump() const
debug method
APInt rotl(unsigned rotateAmt) const
Rotate left by rotateAmt.
unsigned countl_one() const
Count the number of leading one bits.
void insertBits(const APInt &SubBits, unsigned bitPosition)
Insert the bits from a smaller APInt starting at bitPosition.
unsigned logBase2() const
static int tcMultiplyPart(WordType *dst, const WordType *src, WordType multiplier, WordType carry, unsigned srcParts, unsigned dstParts, bool add)
DST += SRC * MULTIPLIER + PART if add is true DST = SRC * MULTIPLIER + PART if add is false.
static constexpr unsigned APINT_BITS_PER_WORD
Bits in a word.
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
static int tcMultiply(WordType *, const WordType *, const WordType *, unsigned)
DST = LHS * RHS, where DST has the same width as the operands and is filled with the least significan...
APInt uadd_sat(const APInt &RHS) const
APInt & operator*=(const APInt &RHS)
Multiplication assignment operator.
uint64_t VAL
Used to store the <= 64 bits integer value.
static unsigned getBitsNeeded(StringRef str, uint8_t radix)
Get bits required for string value.
static WordType tcSubtract(WordType *, const WordType *, WordType carry, unsigned)
DST -= RHS + CARRY where CARRY is zero or one. Returns the carry flag.
APInt multiplicativeInverse() const
static void tcNegate(WordType *, unsigned)
Negate a bignum in-place.
bool getBoolValue() const
Convert APInt to a boolean value.
APInt srem(const APInt &RHS) const
Function for signed remainder operation.
APInt smul_ov(const APInt &RHS, bool &Overflow) const
static WordType tcIncrement(WordType *dst, unsigned parts)
Increment a bignum in-place. Return the carry flag.
bool isNonNegative() const
Determine if this APInt Value is non-negative (>= 0)
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
APInt sext(unsigned width) const
Sign extend to a new width.
void setBits(unsigned loBit, unsigned hiBit)
Set the bits from loBit (inclusive) to hiBit (exclusive) to 1.
APInt shl(unsigned shiftAmt) const
Left-shift function.
APInt umul_sat(const APInt &RHS) const
bool isPowerOf2() const
Check if this APInt's value is a power of two greater than zero.
APInt & operator+=(const APInt &RHS)
Addition assignment operator.
void flipBit(unsigned bitPosition)
Toggles a given bit to its opposite value.
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
static WordType tcAddPart(WordType *, WordType, unsigned)
DST += RHS. Returns the carry flag.
const uint64_t * getRawData() const
This function returns a pointer to the internal storage of the APInt.
void Profile(FoldingSetNodeID &id) const
Used to insert APInt objects, or objects that contain APInt objects, into FoldingSets.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
APInt extractBits(unsigned numBits, unsigned bitPosition) const
Return an APInt with the extracted bits [bitPosition,bitPosition+numBits).
bool isIntN(unsigned N) const
Check if this APInt has an N-bits unsigned integer value.
APInt ssub_ov(const APInt &RHS, bool &Overflow) const
APInt & operator--()
Prefix decrement operator.
bool isOne() const
Determine if this is a value of 1.
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
int64_t getSExtValue() const
Get sign extended value.
void lshrInPlace(unsigned ShiftAmt)
Logical right-shift this APInt by ShiftAmt in place.
APInt lshr(unsigned shiftAmt) const
Logical right-shift function.
APInt sqrt() const
Compute the square root.
void setBitVal(unsigned BitPosition, bool BitValue)
Set a given bit to a given value.
APInt ssub_sat(const APInt &RHS) const
void toStringSigned(SmallVectorImpl< char > &Str, unsigned Radix=10) const
Considers the APInt to be signed and converts it into a string in the radix given.
APInt truncSSat(unsigned width) const
Truncate to new width with signed saturation.
void toString(SmallVectorImpl< char > &Str, unsigned Radix, bool Signed, bool formatAsCLiteral=false, bool UpperCase=true, bool InsertSeparators=false) const
Converts an APInt to a string and append it to Str.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
size_t size() const
size - Get the array size.
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
SmallString - A SmallString is just a SmallVector with methods and accessors that make it work better...
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
StringRef - Represent a constant reference to a string, i.e.
constexpr bool empty() const
empty - Check if the string is empty.
constexpr size_t size() const
size - Get the string size.
An opaque object representing a hash code.
This class implements an extremely fast bulk output stream that can only output to a stream.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
std::optional< unsigned > GetMostSignificantDifferentBit(const APInt &A, const APInt &B)
Compare two values, and if they are different, return the position of the most significant bit that i...
APInt mulhu(const APInt &C1, const APInt &C2)
Performs (2*N)-bit multiplication on zero-extended operands.
APInt RoundingUDiv(const APInt &A, const APInt &B, APInt::Rounding RM)
Return A unsign-divided by B, rounded by the given rounding mode.
APInt avgCeilU(const APInt &C1, const APInt &C2)
Compute the ceil of the unsigned average of C1 and C2.
APInt avgFloorU(const APInt &C1, const APInt &C2)
Compute the floor of the unsigned average of C1 and C2.
APInt mulhs(const APInt &C1, const APInt &C2)
Performs (2*N)-bit multiplication on sign-extended operands.
APInt RoundingSDiv(const APInt &A, const APInt &B, APInt::Rounding RM)
Return A sign-divided by B, rounded by the given rounding mode.
APInt pow(const APInt &X, int64_t N)
Compute X^N for N>=0.
APInt RoundDoubleToAPInt(double Double, unsigned width)
Converts the given double value into a APInt.
APInt ScaleBitMask(const APInt &A, unsigned NewBitWidth, bool MatchAllBits=false)
Splat/Merge neighboring bits to widen/narrow the bitmask represented by.
std::optional< APInt > SolveQuadraticEquationWrap(APInt A, APInt B, APInt C, unsigned RangeWidth)
Let q(n) = An^2 + Bn + C, and BW = bit width of the value range (e.g.
APInt avgFloorS(const APInt &C1, const APInt &C2)
Compute the floor of the signed average of C1 and C2.
APInt avgCeilS(const APInt &C1, const APInt &C2)
Compute the ceil of the signed average of C1 and C2.
APInt GreatestCommonDivisor(APInt A, APInt B)
Compute GCD of two unsigned APInt values.
@ C
The default llvm calling convention, compatible with C.
static const bool IsLittleEndianHost
This is an optimization pass for GlobalISel generic memory operations.
hash_code hash_value(const FixedPointSemantics &Val)
int popcount(T Value) noexcept
Count the number of set bits in a value.
void StoreIntToMemory(const APInt &IntVal, uint8_t *Dst, unsigned StoreBytes)
StoreIntToMemory - Fills the StoreBytes bytes of memory starting from Dst with the integer held in In...
int countr_one(T Value)
Count the number of ones from the least significant bit to the first zero bit.
unsigned Log2_64(uint64_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
int countl_zero(T Val)
Count number of 0's from the most significant bit to the least stopping at the first 1.
constexpr uint32_t Hi_32(uint64_t Value)
Return the high 32 bits of a 64 bit value.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
int countl_one(T Value)
Count the number of ones from the most significant bit to the first zero bit.
constexpr uint32_t Lo_32(uint64_t Value)
Return the low 32 bits of a 64 bit value.
@ Mod
The access may modify the value stored in memory.
constexpr unsigned BitWidth
constexpr int64_t SignExtend64(uint64_t x)
Sign-extend the number in the bottom B bits of X to a 64-bit integer.
unsigned Log2(Align A)
Returns the log2 of the alignment.
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
constexpr uint64_t Make_64(uint32_t High, uint32_t Low)
Make a 64-bit integer from a high / low pair of 32-bit integers.
void LoadIntFromMemory(APInt &IntVal, const uint8_t *Src, unsigned LoadBytes)
LoadIntFromMemory - Loads the integer stored in the LoadBytes bytes starting from Src into IntVal,...
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
This struct is a compact representation of a valid (non-zero power of two) alignment.
An information struct used to provide DenseMap with the various necessary components for a given valu...
static uint64_t round(uint64_t Acc, uint64_t Input)