LLVM: lib/Support/APInt.cpp Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
13
27#include
28#include
29
30using namespace llvm;
31
32#define DEBUG_TYPE "apint"
33
34
35
39
40
41
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
112 : BitWidth(numBits) {
113 initFromArray(ArrayRef(bigVal, numWords));
114}
115
117 : BitWidth(numbits) {
118 fromString(numbits, Str, radix);
119}
120
121void APInt::reallocate(unsigned NewBitWidth) {
122
125 return;
126 }
127
128
130 delete [] U.pVal;
131
132
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
181 else
183 return clearUnusedBits();
184}
185
186
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
317 uint64_t loMask = WORDTYPE_MAX << whichBit(loBit);
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
339void APInt::clearBitsSlowCase(unsigned LoBit, unsigned HiBit) {
340 unsigned LoWord = whichWord(LoBit);
341 unsigned HiWord = whichWord(HiBit);
342
343
344 uint64_t LoMask = ~(WORDTYPE_MAX << whichBit(LoBit));
345
346
347 unsigned HiShiftAmt = whichBit(HiBit);
348 if (HiShiftAmt != 0) {
349
351
352
353 if (HiWord == LoWord)
354 LoMask |= HiMask;
355 else
356 U.pVal[HiWord] &= HiMask;
357 }
358
359 U.pVal[LoWord] &= LoMask;
360
361
362 for (unsigned Word = LoWord + 1; Word < HiWord; ++Word)
363 U.pVal[Word] = 0;
364}
365
366
368 for (unsigned i = 0; i < parts; i++)
369 dst[i] = ~dst[i];
370}
371
372
373void APInt::flipAllBitsSlowCase() {
375 clearUnusedBits();
376}
377
378
379
380
381
382APInt APInt::concatSlowCase(const APInt &NewLSB) const {
387}
388
389
390
391
393 assert(bitPosition < BitWidth && "Out of the bit-width range!");
394 setBitVal(bitPosition, !(*this)[bitPosition]);
395}
396
398 unsigned subBitWidth = subBits.getBitWidth();
399 assert((subBitWidth + bitPosition) <= BitWidth && "Illegal bit insertion");
400
401
402 if (subBitWidth == 0)
403 return;
404
405
406 if (subBitWidth == BitWidth) {
407 *this = subBits;
408 return;
409 }
410
411
414 U.VAL &= ~(mask << bitPosition);
415 U.VAL |= (subBits.U.VAL << bitPosition);
416 return;
417 }
418
419 unsigned loBit = whichBit(bitPosition);
420 unsigned loWord = whichWord(bitPosition);
421 unsigned hi1Word = whichWord(bitPosition + subBitWidth - 1);
422
423
424 if (loWord == hi1Word) {
426 U.pVal[loWord] &= ~(mask << loBit);
427 U.pVal[loWord] |= (subBits.U.VAL << loBit);
428 return;
429 }
430
431
432 if (loBit == 0) {
433
435 memcpy(U.pVal + loWord, subBits.getRawData(),
437
438
440 if (remainingBits != 0) {
442 U.pVal[hi1Word] &= ~mask;
443 U.pVal[hi1Word] |= subBits.getWord(subBitWidth - 1);
444 }
445 return;
446 }
447
448
449
450
451 for (unsigned i = 0; i != subBitWidth; ++i)
452 setBitVal(bitPosition + i, subBits[i]);
453}
454
457 subBits &= maskBits;
459 U.VAL &= ~(maskBits << bitPosition);
460 U.VAL |= subBits << bitPosition;
461 return;
462 }
463
464 unsigned loBit = whichBit(bitPosition);
465 unsigned loWord = whichWord(bitPosition);
466 unsigned hiWord = whichWord(bitPosition + numBits - 1);
467 if (loWord == hiWord) {
468 U.pVal[loWord] &= ~(maskBits << loBit);
469 U.pVal[loWord] |= subBits << loBit;
470 return;
471 }
472
473 static_assert(8 * sizeof(WordType) <= 64, "This code assumes only two words affected");
474 unsigned wordBits = 8 * sizeof(WordType);
475 U.pVal[loWord] &= ~(maskBits << loBit);
476 U.pVal[loWord] |= subBits << loBit;
477
478 U.pVal[hiWord] &= ~(maskBits >> (wordBits - loBit));
479 U.pVal[hiWord] |= subBits >> (wordBits - loBit);
480}
481
483 assert(bitPosition < BitWidth && (numBits + bitPosition) <= BitWidth &&
484 "Illegal bit extraction");
485
487 return APInt(numBits, U.VAL >> bitPosition, false,
488 true);
489
490 unsigned loBit = whichBit(bitPosition);
491 unsigned loWord = whichWord(bitPosition);
492 unsigned hiWord = whichWord(bitPosition + numBits - 1);
493
494
495 if (loWord == hiWord)
496 return APInt(numBits, U.pVal[loWord] >> loBit, false,
497 true);
498
499
500
501 if (loBit == 0)
502 return APInt(numBits, ArrayRef(U.pVal + loWord, 1 + hiWord - loWord));
503
504
505 APInt Result(numBits, 0);
507 unsigned NumDstWords = Result.getNumWords();
508
509 uint64_t *DestPtr = Result.isSingleWord() ? &Result.U.VAL : Result.U.pVal;
510 for (unsigned word = 0; word < NumDstWords; ++word) {
511 uint64_t w0 = U.pVal[loWord + word];
513 (loWord + word + 1) < NumSrcWords ? U.pVal[loWord + word + 1] : 0;
515 }
516
517 return Result.clearUnusedBits();
518}
519
521 unsigned bitPosition) const {
522 assert(bitPosition < BitWidth && (numBits + bitPosition) <= BitWidth &&
523 "Illegal bit extraction");
524 assert(numBits <= 64 && "Illegal bit extraction");
525
528 return (U.VAL >> bitPosition) & maskBits;
529
531 "This code assumes only two words affected");
532 unsigned loBit = whichBit(bitPosition);
533 unsigned loWord = whichWord(bitPosition);
534 unsigned hiWord = whichWord(bitPosition + numBits - 1);
535 if (loWord == hiWord)
536 return (U.pVal[loWord] >> loBit) & maskBits;
537
538 uint64_t retBits = U.pVal[loWord] >> loBit;
540 retBits &= maskBits;
541 return retBits;
542}
543
545 assert(!Str.empty() && "Invalid string length");
546 size_t StrLen = Str.size();
547
548
549 unsigned IsNegative = false;
550 if (Str[0] == '-' || Str[0] == '+') {
551 IsNegative = Str[0] == '-';
552 StrLen--;
553 assert(StrLen && "String is only a sign, needs a value.");
554 }
555
556
557
558 if (Radix == 2)
559 return StrLen + IsNegative;
560 if (Radix == 8)
561 return StrLen * 3 + IsNegative;
562 if (Radix == 16)
563 return StrLen * 4 + IsNegative;
564
565
566
567
568
569 if (Radix == 10)
570 return (StrLen == 1 ? 4 : StrLen * 64 / 18) + IsNegative;
571
573 return (StrLen == 1 ? 7 : StrLen * 16 / 3) + IsNegative;
574}
575
577
578
580
581
582
583 if (radix == 2 || radix == 8 || radix == 16)
584 return sufficient;
585
586
587
588
589 size_t slen = str.size();
590
591
594 if (*p == '-' || *p == '+') {
595 p++;
596 slen--;
597 assert(slen && "String is only a sign, needs a value.");
598 }
599
600
601
603
604
605
606
607 unsigned log = tmp.logBase2();
608 if (log == (unsigned)-1) {
612 } else {
614 }
615}
616
620
622 Arg.BitWidth,
624}
625
628}
629
632 "SplatSizeInBits must divide width!");
633
634
635 return *this == rotl(SplatSizeInBits);
636}
637
638
640 return this->lshr(BitWidth - numBits);
641}
642
643
646 Result &= *this;
647 return Result;
648}
649
650
652 assert(NewLen >= V.getBitWidth() && "Can't splat to smaller bit width!");
653
654 APInt Val = V.zext(NewLen);
655 for (unsigned I = V.getBitWidth(); I < NewLen; I <<= 1)
656 Val |= Val << I;
657
658 return Val;
659}
660
661unsigned APInt::countLeadingZerosSlowCase() const {
662 unsigned Count = 0;
663 for (int i = getNumWords()-1; i >= 0; --i) {
665 if (V == 0)
667 else {
669 break;
670 }
671 }
672
676}
677
678unsigned APInt::countLeadingOnesSlowCase() const {
680 unsigned shift;
681 if (!highWordBits) {
683 shift = 0;
684 } else {
686 }
689 if (Count == highWordBits) {
690 for (i--; i >= 0; --i) {
693 else {
695 break;
696 }
697 }
698 }
700}
701
702unsigned APInt::countTrailingZerosSlowCase() const {
703 unsigned Count = 0;
704 unsigned i = 0;
705 for (; i < getNumWords() && U.pVal[i] == 0; ++i)
709 return std::min(Count, BitWidth);
710}
711
712unsigned APInt::countTrailingOnesSlowCase() const {
713 unsigned Count = 0;
714 unsigned i = 0;
721}
722
723unsigned APInt::countPopulationSlowCase() const {
724 unsigned Count = 0;
725 for (unsigned i = 0; i < getNumWords(); ++i)
728}
729
730bool APInt::intersectsSlowCase(const APInt &RHS) const {
731 for (unsigned i = 0, e = getNumWords(); i != e; ++i)
732 if ((U.pVal[i] & RHS.U.pVal[i]) != 0)
733 return true;
734
735 return false;
736}
737
738bool APInt::isSubsetOfSlowCase(const APInt &RHS) const {
739 for (unsigned i = 0, e = getNumWords(); i != e; ++i)
740 if ((U.pVal[i] & ~RHS.U.pVal[i]) != 0)
741 return false;
742
743 return true;
744}
745
747 assert(BitWidth >= 16 && BitWidth % 8 == 0 && "Cannot byteswap!");
748 if (BitWidth == 16)
750 if (BitWidth == 32)
752 if (BitWidth <= 64) {
754 Tmp1 >>= (64 - BitWidth);
755 return APInt(BitWidth, Tmp1);
756 }
757
761 if (Result.BitWidth != BitWidth) {
762 Result.lshrInPlace(Result.BitWidth - BitWidth);
763 Result.BitWidth = BitWidth;
764 }
765 return Result;
766}
767
769 switch (BitWidth) {
770 case 64:
772 case 32:
774 case 16:
776 case 8:
778 case 0:
779 return *this;
780 default:
781 break;
782 }
783
784 APInt Val(*this);
785 APInt Reversed(BitWidth, 0);
786 unsigned S = BitWidth;
787
789 Reversed <<= 1;
790 Reversed |= Val[0];
791 --S;
792 }
793
794 Reversed <<= S;
795 return Reversed;
796}
797
799
801
802
803 if () return B;
804 if () return A;
805
806
807 unsigned Pow2;
808 {
809 unsigned Pow2_A = A.countr_zero();
810 unsigned Pow2_B = B.countr_zero();
811 if (Pow2_A > Pow2_B) {
812 A.lshrInPlace(Pow2_A - Pow2_B);
813 Pow2 = Pow2_B;
814 } else if (Pow2_B > Pow2_A) {
815 B.lshrInPlace(Pow2_B - Pow2_A);
816 Pow2 = Pow2_A;
817 } else {
818 Pow2 = Pow2_A;
819 }
820 }
821
822
823
824
825
826
827
831 A.lshrInPlace(A.countr_zero() - Pow2);
832 } else {
834 B.lshrInPlace(B.countr_zero() - Pow2);
835 }
836 }
837
838 return A;
839}
840
843
844
846
847
848 int64_t exp = ((I >> 52) & 0x7ff) - 1023;
849
850
851 if (exp < 0)
852 return APInt(width, 0u);
853
854
855 uint64_t mantissa = (I & (~0ULL >> 12)) | 1ULL << 52;
856
857
858 if (exp < 52)
859 return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
860 APInt(width, mantissa >> (52 - exp));
861
862
863
864 if (width <= exp - 52)
865 return APInt(width, 0);
866
867
868 APInt Tmp(width, mantissa);
870 return isNeg ? -Tmp : Tmp;
871}
872
873
874
875
876
877
878
879
881
882
886 return double(sext);
887 }
888 return double(getWord(0));
889 }
890
891
892 bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
893
894
895 APInt Tmp(isNeg ? -(*this) : (*this));
896
897
899
900
901
902
904
905
906 if (exp > 1023) {
908 return std::numeric_limits::infinity();
909 else
910 return -std::numeric_limits::infinity();
911 }
912 exp += 1023;
913
914
915
917 unsigned hiWord = whichWord(n-1);
918 if (hiWord == 0) {
919 mantissa = Tmp.U.pVal[0];
920 if (n > 52)
921 mantissa >>= n - 52;
922 } else {
923 assert(hiWord > 0 && "huh?");
926 mantissa = hibits | lobits;
927 }
928
929
931 uint64_t I = sign | (exp << 52) | mantissa;
933}
934
935
937 assert(width <= BitWidth && "Invalid APInt Truncate request");
938
941 true);
942
943 if (width == BitWidth)
944 return *this;
945
947
948
949 unsigned i;
951 Result.U.pVal[i] = U.pVal[i];
952
953
955 if (bits != 0)
956 Result.U.pVal[i] = U.pVal[i] << bits >> bits;
957
958 return Result;
959}
960
961
963 assert(width <= BitWidth && "Invalid APInt Truncate request");
964
965
967 return trunc(width);
968
970}
971
972
974 assert(width <= BitWidth && "Invalid APInt Truncate request");
975
976
978 return trunc(width);
979
982}
983
984
986 assert(Width >= BitWidth && "Invalid APInt SignExtend request");
987
989 return APInt(Width, SignExtend64(U.VAL, BitWidth), true);
990
991 if (Width == BitWidth)
992 return *this;
993
995
996
998
999
1003
1004
1007 Result.clearUnusedBits();
1008 return Result;
1009}
1010
1011
1013 assert(width >= BitWidth && "Invalid APInt ZeroExtend request");
1014
1016 return APInt(width, U.VAL);
1017
1018 if (width == BitWidth)
1019 return *this;
1020
1022
1023
1025
1026
1027 std::memset(Result.U.pVal + getNumWords(), 0,
1029
1030 return Result;
1031}
1032
1034 if (BitWidth < width)
1035 return zext(width);
1036 if (BitWidth > width)
1037 return trunc(width);
1038 return *this;
1039}
1040
1042 if (BitWidth < width)
1043 return sext(width);
1044 if (BitWidth > width)
1045 return trunc(width);
1046 return *this;
1047}
1048
1049
1050
1054
1055
1056
1057void APInt::ashrSlowCase(unsigned ShiftAmt) {
1058
1059 if (!ShiftAmt)
1060 return;
1061
1062
1064
1065
1068
1069 unsigned WordsToMove = getNumWords() - WordShift;
1070 if (WordsToMove != 0) {
1071
1074
1075
1076 if (BitShift == 0) {
1077 std::memmove(U.pVal, U.pVal + WordShift, WordsToMove * APINT_WORD_SIZE);
1078 } else {
1079
1080 for (unsigned i = 0; i != WordsToMove - 1; ++i)
1081 U.pVal[i] = (U.pVal[i + WordShift] >> BitShift) |
1083
1084
1085
1086 U.pVal[WordsToMove - 1] =
1087 (int64_t)U.pVal[WordShift + WordsToMove - 1] >> BitShift;
1088 }
1089 }
1090
1091
1092 std::memset(U.pVal + WordsToMove, Negative ? -1 : 0,
1094 clearUnusedBits();
1095}
1096
1097
1098
1102
1103
1104
1105void APInt::lshrSlowCase(unsigned ShiftAmt) {
1107}
1108
1109
1110
1112
1114 return *this;
1115}
1116
1117void APInt::shlSlowCase(unsigned ShiftAmt) {
1120}
1121
1122
1125 return 0;
1126 unsigned rotBitWidth = rotateAmt.getBitWidth();
1127 APInt rot = rotateAmt;
1128 if (rotBitWidth < BitWidth) {
1129
1130
1132 }
1135}
1136
1140
1143 return *this;
1144 rotateAmt %= BitWidth;
1145 if (rotateAmt == 0)
1146 return *this;
1147 return shl(rotateAmt) | lshr(BitWidth - rotateAmt);
1148}
1149
1153
1155 if (BitWidth == 0)
1156 return *this;
1157 rotateAmt %= BitWidth;
1158 if (rotateAmt == 0)
1159 return *this;
1160 return lshr(rotateAmt) | shl(BitWidth - rotateAmt);
1161}
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1173
1174
1175
1176 if (BitWidth == 1)
1177 return U.VAL - 1;
1178
1179
1181 return UINT32_MAX;
1182
1183
1184
1185
1186
1187
1189 return lg + unsigned((*this)[lg - 1]);
1190}
1191
1192
1193
1194
1195
1196
1197
1198
1200
1201
1203
1204
1205
1206 if (magnitude <= 5) {
1207 static const uint8_t results[32] = {
1208 0,
1209 1, 1,
1210 2, 2, 2, 2,
1211 3, 3, 3, 3, 3, 3,
1212 4, 4, 4, 4, 4, 4, 4, 4,
1213 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1214 6
1215 };
1216 return APInt(BitWidth, results[ (isSingleWord() ? U.VAL : U.pVal[0]) ]);
1217 }
1218
1219
1220
1221
1222
1223 if (magnitude < 52) {
1224 return APInt(BitWidth,
1226 : U.pVal[0])))));
1227 }
1228
1229
1230
1231
1232
1233
1234 unsigned nbits = BitWidth, i = 4;
1235 APInt testy(BitWidth, 16);
1236 APInt x_old(BitWidth, 1);
1237 APInt x_new(BitWidth, 0);
1238 APInt two(BitWidth, 2);
1239
1240
1241 for (;; i += 2, testy = testy.shl(2))
1242 if (i >= nbits || this->ule(testy)) {
1243 x_old = x_old.shl(i / 2);
1244 break;
1245 }
1246
1247
1248 for (;;) {
1249 x_new = (this->udiv(x_old) + x_old).udiv(two);
1250 if (x_old.ule(x_new))
1251 break;
1252 x_old = x_new;
1253 }
1254
1255
1256
1257
1258
1259
1260
1261 APInt square(x_old * x_old);
1262 APInt nextSquare((x_old + 1) * (x_old +1));
1263 if (this->ult(square))
1264 return x_old;
1265 assert(this->ule(nextSquare) && "Error in APInt::sqrt computation");
1266 APInt midpoint((nextSquare - square).udiv(two));
1267 APInt offset(*this - square);
1268 if (offset.ult(midpoint))
1269 return x_old;
1270 return x_old + 1;
1271}
1272
1273
1275 assert((*this)[0] &&
1276 "multiplicative inverse is only defined for odd numbers!");
1277
1278
1279 APInt Factor = *this;
1281 while (!(T = *this * Factor).isOne())
1282 Factor *= 2 - std::move(T);
1283 return Factor;
1284}
1285
1286
1287
1288
1289
1291 unsigned m, unsigned n) {
1292 assert(u && "Must provide dividend");
1293 assert(v && "Must provide divisor");
1294 assert(q && "Must provide quotient");
1295 assert(u != v && u != q && v != q && "Must use different memory");
1296 assert(n>1 && "n must be > 1");
1297
1298
1300
1301
1302
1303#ifdef KNUTH_DEBUG
1304#define DEBUG_KNUTH(X) LLVM_DEBUG(X)
1305#else
1306#define DEBUG_KNUTH(X) do {} while(false)
1307#endif
1308
1309 DEBUG_KNUTH(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n');
1311 DEBUG_KNUTH(for (int i = m + n; i >= 0; i--) dbgs() << " " << u[i]);
1313 DEBUG_KNUTH(for (int i = n; i > 0; i--) dbgs() << " " << v[i - 1]);
1315
1316
1317
1318
1319
1320
1321
1322
1326 if (shift) {
1327 for (unsigned i = 0; i < m+n; ++i) {
1328 uint32_t u_tmp = u[i] >> (32 - shift);
1329 u[i] = (u[i] << shift) | u_carry;
1330 u_carry = u_tmp;
1331 }
1332 for (unsigned i = 0; i < n; ++i) {
1333 uint32_t v_tmp = v[i] >> (32 - shift);
1334 v[i] = (v[i] << shift) | v_carry;
1335 v_carry = v_tmp;
1336 }
1337 }
1338 u[m+n] = u_carry;
1339
1341 DEBUG_KNUTH(for (int i = m + n; i >= 0; i--) dbgs() << " " << u[i]);
1343 DEBUG_KNUTH(for (int i = n; i > 0; i--) dbgs() << " " << v[i - 1]);
1345
1346
1347 int j = m;
1348 do {
1349 DEBUG_KNUTH(dbgs() << "KnuthDiv: quotient digit #" << j << '\n');
1350
1351
1352
1353
1354
1355
1356
1357
1359 DEBUG_KNUTH(dbgs() << "KnuthDiv: dividend == " << dividend << '\n');
1360 uint64_t qp = dividend / v[n-1];
1361 uint64_t rp = dividend % v[n-1];
1362 if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
1363 qp--;
1364 rp += v[n-1];
1365 if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
1366 qp--;
1367 }
1368 DEBUG_KNUTH(dbgs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378 int64_t borrow = 0;
1379 for (unsigned i = 0; i < n; ++i) {
1381 int64_t subres = int64_t(u[j+i]) - borrow - Lo_32(p);
1382 u[j+i] = Lo_32(subres);
1385 << ", borrow = " << borrow << '\n');
1386 }
1387 bool isNeg = u[j+n] < borrow;
1388 u[j+n] -= Lo_32(borrow);
1389
1391 DEBUG_KNUTH(for (int i = m + n; i >= 0; i--) dbgs() << " " << u[i]);
1393
1394
1395
1396 q[j] = Lo_32(qp);
1398
1399
1400
1401 q[j]--;
1402
1403
1404
1405 bool carry = false;
1406 for (unsigned i = 0; i < n; i++) {
1407 uint32_t limit = std::min(u[j+i],v[i]);
1408 u[j+i] += v[i] + carry;
1409 carry = u[j+i] < limit || (carry && u[j+i] == limit);
1410 }
1411 u[j+n] += carry;
1412 }
1414 DEBUG_KNUTH(for (int i = m + n; i >= 0; i--) dbgs() << " " << u[i]);
1415 DEBUG_KNUTH(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n');
1416
1417
1418 } while (--j >= 0);
1419
1421 DEBUG_KNUTH(for (int i = m; i >= 0; i--) dbgs() << " " << q[i]);
1423
1424
1425
1426
1427 if (r) {
1428
1429
1430
1431 if (shift) {
1434 for (int i = n-1; i >= 0; i--) {
1435 r[i] = (u[i] >> shift) | carry;
1436 carry = u[i] << (32 - shift);
1438 }
1439 } else {
1440 for (int i = n-1; i >= 0; i--) {
1441 r[i] = u[i];
1443 }
1444 }
1446 }
1448}
1449
1450void APInt::divide(const WordType *LHS, unsigned lhsWords, const WordType *RHS,
1451 unsigned rhsWords, WordType *Quotient, WordType *Remainder) {
1452 assert(lhsWords >= rhsWords && "Fractional result");
1453
1454
1455
1456
1457
1458
1459
1460
1461 unsigned n = rhsWords * 2;
1462 unsigned m = (lhsWords * 2) - n;
1463
1464
1465
1466 uint32_t SPACE[128];
1467 uint32_t *U = nullptr;
1468 uint32_t *V = nullptr;
1469 uint32_t *Q = nullptr;
1470 uint32_t *R = nullptr;
1471 if ((Remainder?4:3)*n+2*m+1 <= 128) {
1472 U = &SPACE[0];
1473 V = &SPACE[m+n+1];
1474 Q = &SPACE[(m+n+1) + n];
1475 if (Remainder)
1476 R = &SPACE[(m+n+1) + n + (m+n)];
1477 } else {
1478 U = new uint32_t[m + n + 1];
1479 V = new uint32_t[n];
1480 Q = new uint32_t[m+n];
1481 if (Remainder)
1482 R = new uint32_t[n];
1483 }
1484
1485
1486 memset(U, 0, (m+n+1)*sizeof(uint32_t));
1487 for (unsigned i = 0; i < lhsWords; ++i) {
1488 uint64_t tmp = LHS[i];
1489 U[i * 2] = Lo_32(tmp);
1490 U[i * 2 + 1] = Hi_32(tmp);
1491 }
1492 U[m+n] = 0;
1493
1494
1495 memset(V, 0, (n)*sizeof(uint32_t));
1496 for (unsigned i = 0; i < rhsWords; ++i) {
1497 uint64_t tmp = RHS[i];
1499 V[i * 2 + 1] = Hi_32(tmp);
1500 }
1501
1502
1503 memset(Q, 0, (m+n) * sizeof(uint32_t));
1504 if (Remainder)
1505 memset(R, 0, n * sizeof(uint32_t));
1506
1507
1508
1509
1510
1511 for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
1512 n--;
1513 m++;
1514 }
1515 for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
1516 m--;
1517
1518
1519
1520
1521
1522
1523
1524 assert(n != 0 && "Divide by zero?");
1525 if (n == 1) {
1526 uint32_t divisor = V[0];
1527 uint32_t remainder = 0;
1528 for (int i = m; i >= 0; i--) {
1529 uint64_t partial_dividend = Make_64(remainder, U[i]);
1530 if (partial_dividend == 0) {
1531 Q[i] = 0;
1532 remainder = 0;
1533 } else if (partial_dividend < divisor) {
1534 Q[i] = 0;
1535 remainder = Lo_32(partial_dividend);
1536 } else if (partial_dividend == divisor) {
1537 Q[i] = 1;
1538 remainder = 0;
1539 } else {
1540 Q[i] = Lo_32(partial_dividend / divisor);
1541 remainder = Lo_32(partial_dividend - (Q[i] * divisor));
1542 }
1543 }
1544 if (R)
1545 R[0] = remainder;
1546 } else {
1547
1548
1550 }
1551
1552
1553 if (Quotient) {
1554 for (unsigned i = 0; i < lhsWords; ++i)
1555 Quotient[i] = Make_64(Q[i*2+1], Q[i*2]);
1556 }
1557
1558
1559 if (Remainder) {
1560 for (unsigned i = 0; i < rhsWords; ++i)
1561 Remainder[i] = Make_64(R[i*2+1], R[i*2]);
1562 }
1563
1564
1565 if (U != &SPACE[0]) {
1566 delete [] U;
1567 delete [] V;
1568 delete [] Q;
1569 delete [] R;
1570 }
1571}
1572
1574 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1575
1576
1578 assert(RHS.U.VAL != 0 && "Divide by zero?");
1579 return APInt(BitWidth, U.VAL / RHS.U.VAL);
1580 }
1581
1582
1584 unsigned rhsBits = RHS.getActiveBits();
1585 unsigned rhsWords = getNumWords(rhsBits);
1586 assert(rhsWords && "Divided by zero???");
1587
1588
1589 if (!lhsWords)
1590
1591 return APInt(BitWidth, 0);
1592 if (rhsBits == 1)
1593
1594 return *this;
1595 if (lhsWords < rhsWords || this->ult(RHS))
1596
1597 return APInt(BitWidth, 0);
1598 if (*this == RHS)
1599
1600 return APInt(BitWidth, 1);
1601 if (lhsWords == 1)
1602
1603 return APInt(BitWidth, this->U.pVal[0] / RHS.U.pVal[0]);
1604
1605
1606 APInt Quotient(BitWidth, 0);
1607 divide(U.pVal, lhsWords, RHS.U.pVal, rhsWords, Quotient.U.pVal, nullptr);
1608 return Quotient;
1609}
1610
1612 assert(RHS != 0 && "Divide by zero?");
1613
1614
1616 return APInt(BitWidth, U.VAL / RHS);
1617
1618
1620
1621
1622 if (!lhsWords)
1623
1624 return APInt(BitWidth, 0);
1625 if (RHS == 1)
1626
1627 return *this;
1628 if (this->ult(RHS))
1629
1630 return APInt(BitWidth, 0);
1631 if (*this == RHS)
1632
1633 return APInt(BitWidth, 1);
1634 if (lhsWords == 1)
1635
1636 return APInt(BitWidth, this->U.pVal[0] / RHS);
1637
1638
1639 APInt Quotient(BitWidth, 0);
1640 divide(U.pVal, lhsWords, &RHS, 1, Quotient.U.pVal, nullptr);
1641 return Quotient;
1642}
1643
1646 if (RHS.isNegative())
1647 return (-(*this)).udiv(-RHS);
1648 return -((-(*this)).udiv(RHS));
1649 }
1650 if (RHS.isNegative())
1651 return -(this->udiv(-RHS));
1652 return this->udiv(RHS);
1653}
1654
1657 if (RHS < 0)
1658 return (-(*this)).udiv(-RHS);
1659 return -((-(*this)).udiv(RHS));
1660 }
1661 if (RHS < 0)
1662 return -(this->udiv(-RHS));
1663 return this->udiv(RHS);
1664}
1665
1667 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1669 assert(RHS.U.VAL != 0 && "Remainder by zero?");
1670 return APInt(BitWidth, U.VAL % RHS.U.VAL);
1671 }
1672
1673
1675
1676
1677 unsigned rhsBits = RHS.getActiveBits();
1678 unsigned rhsWords = getNumWords(rhsBits);
1679 assert(rhsWords && "Performing remainder operation by zero ???");
1680
1681
1682 if (lhsWords == 0)
1683
1684 return APInt(BitWidth, 0);
1685 if (rhsBits == 1)
1686
1687 return APInt(BitWidth, 0);
1688 if (lhsWords < rhsWords || this->ult(RHS))
1689
1690 return *this;
1691 if (*this == RHS)
1692
1693 return APInt(BitWidth, 0);
1694 if (lhsWords == 1)
1695
1696 return APInt(BitWidth, U.pVal[0] % RHS.U.pVal[0]);
1697
1698
1699 APInt Remainder(BitWidth, 0);
1700 divide(U.pVal, lhsWords, RHS.U.pVal, rhsWords, nullptr, Remainder.U.pVal);
1701 return Remainder;
1702}
1703
1705 assert(RHS != 0 && "Remainder by zero?");
1706
1708 return U.VAL % RHS;
1709
1710
1712
1713
1714 if (lhsWords == 0)
1715
1716 return 0;
1717 if (RHS == 1)
1718
1719 return 0;
1720 if (this->ult(RHS))
1721
1723 if (*this == RHS)
1724
1725 return 0;
1726 if (lhsWords == 1)
1727
1728 return U.pVal[0] % RHS;
1729
1730
1732 divide(U.pVal, lhsWords, &RHS, 1, nullptr, &Remainder);
1733 return Remainder;
1734}
1735
1738 if (RHS.isNegative())
1739 return -((-(*this)).urem(-RHS));
1740 return -((-(*this)).urem(RHS));
1741 }
1742 if (RHS.isNegative())
1743 return this->urem(-RHS);
1744 return this->urem(RHS);
1745}
1746
1749 if (RHS < 0)
1750 return -((-(*this)).urem(-RHS));
1751 return -((-(*this)).urem(RHS));
1752 }
1753 if (RHS < 0)
1754 return this->urem(-RHS);
1755 return this->urem(RHS);
1756}
1757
1759 APInt &Quotient, APInt &Remainder) {
1760 assert(LHS.BitWidth == RHS.BitWidth && "Bit widths must be the same");
1761 unsigned BitWidth = LHS.BitWidth;
1762
1763
1764 if (LHS.isSingleWord()) {
1765 assert(RHS.U.VAL != 0 && "Divide by zero?");
1766 uint64_t QuotVal = LHS.U.VAL / RHS.U.VAL;
1767 uint64_t RemVal = LHS.U.VAL % RHS.U.VAL;
1768 Quotient = APInt(BitWidth, QuotVal);
1769 Remainder = APInt(BitWidth, RemVal);
1770 return;
1771 }
1772
1773
1774 unsigned lhsWords = getNumWords(LHS.getActiveBits());
1775 unsigned rhsBits = RHS.getActiveBits();
1776 unsigned rhsWords = getNumWords(rhsBits);
1777 assert(rhsWords && "Performing divrem operation by zero ???");
1778
1779
1780 if (lhsWords == 0) {
1781 Quotient = APInt(BitWidth, 0);
1782 Remainder = APInt(BitWidth, 0);
1783 return;
1784 }
1785
1786 if (rhsBits == 1) {
1787 Quotient = LHS;
1788 Remainder = APInt(BitWidth, 0);
1789 }
1790
1791 if (lhsWords < rhsWords || LHS.ult(RHS)) {
1792 Remainder = LHS;
1793 Quotient = APInt(BitWidth, 0);
1794 return;
1795 }
1796
1797 if (LHS == RHS) {
1798 Quotient = APInt(BitWidth, 1);
1799 Remainder = APInt(BitWidth, 0);
1800 return;
1801 }
1802
1803
1804
1805
1806
1807 Quotient.reallocate(BitWidth);
1808 Remainder.reallocate(BitWidth);
1809
1810 if (lhsWords == 1) {
1811
1812 uint64_t lhsValue = LHS.U.pVal[0];
1813 uint64_t rhsValue = RHS.U.pVal[0];
1814 Quotient = lhsValue / rhsValue;
1815 Remainder = lhsValue % rhsValue;
1816 return;
1817 }
1818
1819
1820 divide(LHS.U.pVal, lhsWords, RHS.U.pVal, rhsWords, Quotient.U.pVal,
1821 Remainder.U.pVal);
1822
1823 std::memset(Quotient.U.pVal + lhsWords, 0,
1825 std::memset(Remainder.U.pVal + rhsWords, 0,
1827}
1828
1831 assert(RHS != 0 && "Divide by zero?");
1832 unsigned BitWidth = LHS.BitWidth;
1833
1834
1835 if (LHS.isSingleWord()) {
1836 uint64_t QuotVal = LHS.U.VAL / RHS;
1837 Remainder = LHS.U.VAL % RHS;
1838 Quotient = APInt(BitWidth, QuotVal);
1839 return;
1840 }
1841
1842
1843 unsigned lhsWords = getNumWords(LHS.getActiveBits());
1844
1845
1846 if (lhsWords == 0) {
1847 Quotient = APInt(BitWidth, 0);
1848 Remainder = 0;
1849 return;
1850 }
1851
1852 if (RHS == 1) {
1853 Quotient = LHS;
1854 Remainder = 0;
1855 return;
1856 }
1857
1858 if (LHS.ult(RHS)) {
1859 Remainder = LHS.getZExtValue();
1860 Quotient = APInt(BitWidth, 0);
1861 return;
1862 }
1863
1864 if (LHS == RHS) {
1865 Quotient = APInt(BitWidth, 1);
1866 Remainder = 0;
1867 return;
1868 }
1869
1870
1871
1872
1873 Quotient.reallocate(BitWidth);
1874
1875 if (lhsWords == 1) {
1876
1877 uint64_t lhsValue = LHS.U.pVal[0];
1878 Quotient = lhsValue / RHS;
1879 Remainder = lhsValue % RHS;
1880 return;
1881 }
1882
1883
1884 divide(LHS.U.pVal, lhsWords, &RHS, 1, Quotient.U.pVal, &Remainder);
1885
1886 std::memset(Quotient.U.pVal + lhsWords, 0,
1888}
1889
1891 APInt &Quotient, APInt &Remainder) {
1892 if (LHS.isNegative()) {
1893 if (RHS.isNegative())
1895 else {
1898 }
1900 } else if (RHS.isNegative()) {
1903 } else {
1905 }
1906}
1907
1909 APInt &Quotient, int64_t &Remainder) {
1911 if (LHS.isNegative()) {
1912 if (RHS < 0)
1914 else {
1917 }
1918 R = -R;
1919 } else if (RHS < 0) {
1922 } else {
1924 }
1925 Remainder = R;
1926}
1927
1929 APInt Res = *this+RHS;
1930 Overflow = isNonNegative() == RHS.isNonNegative() &&
1932 return Res;
1933}
1934
1936 APInt Res = *this+RHS;
1937 Overflow = Res.ult(RHS);
1938 return Res;
1939}
1940
1942 APInt Res = *this - RHS;
1943 Overflow = isNonNegative() != RHS.isNonNegative() &&
1945 return Res;
1946}
1947
1949 APInt Res = *this-RHS;
1950 Overflow = Res.ugt(*this);
1951 return Res;
1952}
1953
1955
1957 return sdiv(RHS);
1958}
1959
1961 APInt Res = *this * RHS;
1962
1963 if (RHS != 0)
1964 Overflow = Res.sdiv(RHS) != *this ||
1966 else
1967 Overflow = false;
1968 return Res;
1969}
1970
1972 if (countl_zero() + RHS.countl_zero() + 2 <= BitWidth) {
1973 Overflow = true;
1974 return *this * RHS;
1975 }
1976
1979 Res <<= 1;
1980 if ((*this)[0]) {
1981 Res += RHS;
1982 if (Res.ult(RHS))
1983 Overflow = true;
1984 }
1985 return Res;
1986}
1987
1991
1994 if (Overflow)
1995 return APInt(BitWidth, 0);
1996
1997 if (isNonNegative())
1999 else
2001
2002 return *this << ShAmt;
2003}
2004
2008
2011 if (Overflow)
2012 return APInt(BitWidth, 0);
2013
2015
2016 return *this << ShAmt;
2017}
2018
2021 if ((quotient * RHS != *this) && (isNegative() != RHS.isNegative()))
2022 return quotient - 1;
2023 return quotient;
2024}
2025
2027 bool Overflow;
2029 if (!Overflow)
2030 return Res;
2031
2034}
2035
2037 bool Overflow;
2039 if (!Overflow)
2040 return Res;
2041
2043}
2044
2046 bool Overflow;
2048 if (!Overflow)
2049 return Res;
2050
2053}
2054
2056 bool Overflow;
2058 if (!Overflow)
2059 return Res;
2060
2061 return APInt(BitWidth, 0);
2062}
2063
2065 bool Overflow;
2067 if (!Overflow)
2068 return Res;
2069
2070
2071 bool ResIsNegative = isNegative() ^ RHS.isNegative();
2072
2075}
2076
2078 bool Overflow;
2080 if (!Overflow)
2081 return Res;
2082
2084}
2085
2089
2091 bool Overflow;
2093 if (!Overflow)
2094 return Res;
2095
2098}
2099
2103
2105 bool Overflow;
2107 if (!Overflow)
2108 return Res;
2109
2111}
2112
2113void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) {
2114
2115 assert(!str.empty() && "Invalid string length");
2116 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
2117 radix == 36) &&
2118 "Radix should be 2, 8, 10, 16, or 36!");
2119
2121 size_t slen = str.size();
2122 bool isNeg = *p == '-';
2123 if (*p == '-' || *p == '+') {
2124 p++;
2125 slen--;
2126 assert(slen && "String is only a sign, needs a value.");
2127 }
2128 assert((slen <= numbits || radix != 2) && "Insufficient bit width");
2129 assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width");
2130 assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width");
2131 assert((((slen-1)*64)/22 <= numbits || radix != 10) &&
2132 "Insufficient bit width");
2133
2134
2136 U.VAL = 0;
2137 else
2139
2140
2141 unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
2142
2143
2145 unsigned digit = getDigit(*p, radix);
2146 assert(digit < radix && "Invalid character in digit string");
2147
2148
2149 if (slen > 1) {
2150 if (shift)
2151 *this <<= shift;
2152 else
2153 *this *= radix;
2154 }
2155
2156
2157 *this += digit;
2158 }
2159
2162}
2163
2165 bool formatAsCLiteral, bool UpperCase,
2166 bool InsertSeparators) const {
2167 assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 ||
2168 Radix == 36) &&
2169 "Radix should be 2, 8, 10, 16, or 36!");
2170
2171 const char *Prefix = "";
2172 if (formatAsCLiteral) {
2173 switch (Radix) {
2174 case 2:
2175
2176
2177 Prefix = "0b";
2178 break;
2179 case 8:
2180 Prefix = "0";
2181 break;
2182 case 10:
2183 break;
2184 case 16:
2185 Prefix = "0x";
2186 break;
2187 default:
2189 }
2190 }
2191
2192
2193 unsigned Grouping = (Radix == 8 || Radix == 10) ? 3 : 4;
2194
2195
2197 while (*Prefix) {
2198 Str.push_back(*Prefix);
2199 ++Prefix;
2200 };
2201 Str.push_back('0');
2202 return;
2203 }
2204
2205 static const char BothDigits[] = "0123456789abcdefghijklmnopqrstuvwxyz"
2206 "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
2207 const char *Digits = BothDigits + (UpperCase ? 36 : 0);
2208
2210 char Buffer[65];
2211 char *BufPtr = std::end(Buffer);
2212
2216 } else {
2218 if (I >= 0) {
2220 } else {
2221 Str.push_back('-');
2223 }
2224 }
2225
2226 while (*Prefix) {
2227 Str.push_back(*Prefix);
2228 ++Prefix;
2229 };
2230
2231 int Pos = 0;
2232 while (N) {
2233 if (InsertSeparators && Pos % Grouping == 0 && Pos > 0)
2234 *--BufPtr = '\'';
2235 *--BufPtr = Digits[N % Radix];
2236 N /= Radix;
2237 Pos++;
2238 }
2239 Str.append(BufPtr, std::end(Buffer));
2240 return;
2241 }
2242
2243 APInt Tmp(*this);
2244
2246
2247
2248
2250 Str.push_back('-');
2251 }
2252
2253 while (*Prefix) {
2254 Str.push_back(*Prefix);
2255 ++Prefix;
2256 }
2257
2258
2259 unsigned StartDig = Str.size();
2260
2261
2262
2263
2264 if (Radix == 2 || Radix == 8 || Radix == 16) {
2265
2266 unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
2267 unsigned MaskAmt = Radix - 1;
2268
2269 int Pos = 0;
2272 if (InsertSeparators && Pos % Grouping == 0 && Pos > 0)
2273 Str.push_back('\'');
2274
2275 Str.push_back(Digits[Digit]);
2277 Pos++;
2278 }
2279 } else {
2280 int Pos = 0;
2283 udivrem(Tmp, Radix, Tmp, Digit);
2284 assert(Digit < Radix && "divide failed");
2285 if (InsertSeparators && Pos % Grouping == 0 && Pos > 0)
2286 Str.push_back('\'');
2287
2288 Str.push_back(Digits[Digit]);
2289 Pos++;
2290 }
2291 }
2292
2293
2294 std::reverse(Str.begin()+StartDig, Str.end());
2295}
2296
2297#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2302 dbgs() << "APInt(" << BitWidth << "b, "
2303 << U << "u " << S << "s)\n";
2304}
2305#endif
2306
2312
2313
2314
2315
2316
2317
2319 "Part width must be divisible by 2!");
2320
2321
2322
2327
2328
2332
2333
2337
2338
2339
2342 dst[0] = part;
2343 for (unsigned i = 1; i < parts; i++)
2344 dst[i] = 0;
2345}
2346
2347
2349 for (unsigned i = 0; i < parts; i++)
2350 dst[i] = src[i];
2351}
2352
2353
2355 for (unsigned i = 0; i < parts; i++)
2356 if (src[i])
2357 return false;
2358
2359 return true;
2360}
2361
2362
2364 return (parts[whichWord(bit)] & maskBit(bit)) != 0;
2365}
2366
2367
2369 parts[whichWord(bit)] |= maskBit(bit);
2370}
2371
2372
2374 parts[whichWord(bit)] &= ~maskBit(bit);
2375}
2376
2377
2378
2380 for (unsigned i = 0; i < n; i++) {
2381 if (parts[i] != 0) {
2384 }
2385 }
2386
2387 return UINT_MAX;
2388}
2389
2390
2391
2393 do {
2394 --n;
2395
2396 if (parts[n] != 0) {
2397 static_assert(sizeof(parts[n]) <= sizeof(uint64_t));
2399
2401 }
2402 } while (n);
2403
2404 return UINT_MAX;
2405}
2406
2407
2408
2409
2410
2411void
2413 unsigned srcBits, unsigned srcLSB) {
2415 assert(dstParts <= dstCount);
2416
2418 tcAssign(dst, src + firstSrcPart, dstParts);
2419
2422
2423
2424
2425
2427 if (n < srcBits) {
2429 dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
2431 } else if (n > srcBits) {
2434 }
2435
2436
2437 while (dstParts < dstCount)
2438 dst[dstParts++] = 0;
2439}
2440
2441
2443 WordType c, unsigned parts) {
2445
2446 for (unsigned i = 0; i < parts; i++) {
2448 if (c) {
2449 dst[i] += rhs[i] + 1;
2450 c = (dst[i] <= l);
2451 } else {
2452 dst[i] += rhs[i];
2453 c = (dst[i] < l);
2454 }
2455 }
2456
2457 return c;
2458}
2459
2460
2461
2462
2463
2465 unsigned parts) {
2466 for (unsigned i = 0; i < parts; ++i) {
2467 dst[i] += src;
2468 if (dst[i] >= src)
2469 return 0;
2470 src = 1;
2471 }
2472
2473 return 1;
2474}
2475
2476
2478 WordType c, unsigned parts) {
2480
2481 for (unsigned i = 0; i < parts; i++) {
2483 if (c) {
2484 dst[i] -= rhs[i] + 1;
2485 c = (dst[i] >= l);
2486 } else {
2487 dst[i] -= rhs[i];
2488 c = (dst[i] > l);
2489 }
2490 }
2491
2492 return c;
2493}
2494
2495
2496
2497
2498
2499
2500
2501
2503 unsigned parts) {
2504 for (unsigned i = 0; i < parts; ++i) {
2506 dst[i] -= src;
2507 if (src <= Dst)
2508 return 0;
2509 src = 1;
2510 }
2511
2512 return 1;
2513}
2514
2515
2520
2521
2522
2523
2524
2525
2526
2527
2528
2529
2532 unsigned srcParts, unsigned dstParts,
2533 bool add) {
2534
2535 assert(dst <= src || dst >= src + srcParts);
2536 assert(dstParts <= srcParts + 1);
2537
2538
2539 unsigned n = std::min(dstParts, srcParts);
2540
2541 for (unsigned i = 0; i < n; i++) {
2542
2543
2544
2545
2548 if (multiplier == 0 || srcPart == 0) {
2549 low = carry;
2550 high = 0;
2551 } else {
2554
2558 if (low + mid < low)
2559 high++;
2560 low += mid;
2561
2565 if (low + mid < low)
2566 high++;
2567 low += mid;
2568
2569
2570 if (low + carry < low)
2571 high++;
2572 low += carry;
2573 }
2574
2575 if (add) {
2576
2577 if (low + dst[i] < low)
2578 high++;
2579 dst[i] += low;
2580 } else {
2581 dst[i] = low;
2582 }
2583
2584 carry = high;
2585 }
2586
2587 if (srcParts < dstParts) {
2588
2589 assert(srcParts + 1 == dstParts);
2590 dst[srcParts] = carry;
2591 return 0;
2592 }
2593
2594
2595 if (carry)
2596 return 1;
2597
2598
2599
2600
2601 if (multiplier)
2602 for (unsigned i = dstParts; i < srcParts; i++)
2603 if (src[i])
2604 return 1;
2605
2606
2607 return 0;
2608}
2609
2610
2611
2612
2613
2615 const WordType *rhs, unsigned parts) {
2616 assert(dst != lhs && dst != rhs);
2617
2618 int overflow = 0;
2619
2620 for (unsigned i = 0; i < parts; i++) {
2621
2622
2623 overflow |=
2624 tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts, parts - i, i != 0);
2625 }
2626
2627 return overflow;
2628}
2629
2630
2631
2633 const WordType *rhs, unsigned lhsParts,
2634 unsigned rhsParts) {
2635
2636 if (lhsParts > rhsParts)
2637 return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
2638
2639 assert(dst != lhs && dst != rhs);
2640
2641 for (unsigned i = 0; i < lhsParts; i++) {
2642
2643
2644 tcMultiplyPart(&dst[i], rhs, lhs[i], 0, rhsParts, rhsParts + 1, i != 0);
2645 }
2646}
2647
2648
2649
2650
2651
2652
2653
2654
2655
2656
2659 unsigned parts) {
2660 assert(lhs != remainder && lhs != srhs && remainder != srhs);
2661
2662 unsigned shiftCount = tcMSB(rhs, parts) + 1;
2663 if (shiftCount == 0)
2664 return true;
2665
2669
2672 tcAssign(remainder, lhs, parts);
2673 tcSet(lhs, 0, parts);
2674
2675
2676
2677 for (;;) {
2678 int compare = tcCompare(remainder, srhs, parts);
2679 if (compare >= 0) {
2680 tcSubtract(remainder, srhs, 0, parts);
2681 lhs[n] |= mask;
2682 }
2683
2684 if (shiftCount == 0)
2685 break;
2686 shiftCount--;
2688 if ((mask >>= 1) == 0) {
2690 n--;
2691 }
2692 }
2693
2694 return false;
2695}
2696
2697
2698
2700
2702 return;
2703
2704
2707
2708
2709 if (BitShift == 0) {
2710 std::memmove(Dst + WordShift, Dst, (Words - WordShift) * APINT_WORD_SIZE);
2711 } else {
2712 while (Words-- > WordShift) {
2713 Dst[Words] = Dst[Words - WordShift] << BitShift;
2714 if (Words > WordShift)
2715 Dst[Words] |=
2717 }
2718 }
2719
2720
2722}
2723
2724
2725
2727
2729 return;
2730
2731
2734
2735 unsigned WordsToMove = Words - WordShift;
2736
2737 if (BitShift == 0) {
2738 std::memmove(Dst, Dst + WordShift, WordsToMove * APINT_WORD_SIZE);
2739 } else {
2740 for (unsigned i = 0; i != WordsToMove; ++i) {
2741 Dst[i] = Dst[i + WordShift] >> BitShift;
2742 if (i + 1 != WordsToMove)
2744 }
2745 }
2746
2747
2748 std::memset(Dst + WordsToMove, 0, WordShift * APINT_WORD_SIZE);
2749}
2750
2751
2753 unsigned parts) {
2754 while (parts) {
2755 parts--;
2756 if (lhs[parts] != rhs[parts])
2757 return (lhs[parts] > rhs[parts]) ? 1 : -1;
2758 }
2759
2760 return 0;
2761}
2762
2765
2766 switch (RM) {
2774 return Quo;
2775 return Quo + 1;
2776 }
2777 }
2779}
2780
2783 switch (RM) {
2789 return Quo;
2790
2791
2792
2793
2794
2797 return Quo - 1;
2798 return Quo;
2799 }
2801 return Quo;
2802 return Quo + 1;
2803 }
2804
2807 }
2809}
2810
2811std::optional
2813 unsigned RangeWidth) {
2814 unsigned CoeffWidth = A.getBitWidth();
2815 assert(CoeffWidth == B.getBitWidth() && CoeffWidth == C.getBitWidth());
2816 assert(RangeWidth <= CoeffWidth &&
2817 "Value range width should be less than coefficient width");
2818 assert(RangeWidth > 1 && "Value range bit width should be > 1");
2819
2820 LLVM_DEBUG(dbgs() << __func__ << ": solving " << A << "x^2 + " << B
2821 << "x + " << C << ", rw:" << RangeWidth << '\n');
2822
2823
2824 if (C.sextOrTrunc(RangeWidth).isZero()) {
2825 LLVM_DEBUG(dbgs() << __func__ << ": zero solution\n");
2826 return APInt(CoeffWidth, 0);
2827 }
2828
2829
2830
2831
2832
2833
2834
2835
2836
2837
2838
2839
2840
2841
2842
2843 CoeffWidth *= 3;
2847
2848
2849
2850 if (A.isNegative()) {
2851 A.negate();
2852 B.negate();
2853 C.negate();
2854 }
2855
2856
2857
2858
2859
2860
2861
2862
2863
2864
2865
2866
2867
2868
2869
2870
2871
2872
2873
2874
2875
2876
2877
2881 bool PickLow;
2882
2883 auto RoundUp = [] (const APInt &V, const APInt &A) -> APInt {
2884 assert(A.isStrictlyPositive());
2885 APInt T = V.abs().urem(A);
2886 if (T.isZero())
2887 return V;
2888 return V.isNegative() ? V+T : V+(A-T);
2889 };
2890
2891
2892
2893 if (B.isNonNegative()) {
2894
2895
2896
2897
2899 if (C.isStrictlyPositive())
2900 C -= R;
2901
2902 PickLow = false;
2903 } else {
2904
2905
2906
2907
2908 APInt LowkR = C - SqrB.udiv(2*TwoA);
2909
2910 LowkR = RoundUp(LowkR, R);
2911
2912
2913
2914
2915
2916
2917 if (C.sgt(LowkR)) {
2918
2919
2921
2922 PickLow = true;
2923 } else {
2924
2925
2926
2927
2928
2929
2930
2931 C -= LowkR;
2932
2933 PickLow = false;
2934 }
2935 }
2936
2937 LLVM_DEBUG(dbgs() << __func__ << ": updated coefficients " << A << "x^2 + "
2938 << B << "x + " << C << ", rw:" << RangeWidth << '\n');
2939
2941 assert(D.isNonNegative() && "Negative discriminant");
2943
2944 APInt Q = SQ * SQ;
2945 bool InexactSQ = Q != D;
2946
2947
2949 SQ -= 1;
2950
2953
2954
2955
2956
2957
2958
2959
2960 if (PickLow)
2962 else
2964
2965
2966
2967
2968 assert(X.isNonNegative() && "Solution should be non-negative");
2969
2970 if (!InexactSQ && Rem.isZero()) {
2971 LLVM_DEBUG(dbgs() << __func__ << ": solution (root): " << X << '\n');
2972 return X;
2973 }
2974
2975 assert((SQ*SQ).sle(D) && "SQ = |_sqrt(D)_|, so SQ*SQ <= D");
2976
2977
2978
2979
2980
2981
2982
2983
2985 APInt VY = VX + TwoA*X + A + B;
2986 bool SignChange =
2988
2989
2990
2991 if (!SignChange) {
2992 LLVM_DEBUG(dbgs() << __func__ << ": no valid solution\n");
2993 return std::nullopt;
2994 }
2995
2996 X += 1;
2997 LLVM_DEBUG(dbgs() << __func__ << ": solution (wrap): " << X << '\n');
2998 return X;
2999}
3000
3001std::optional
3003 assert(A.getBitWidth() == B.getBitWidth() && "Must have the same bitwidth");
3005 return std::nullopt;
3006 return A.getBitWidth() - ((A ^ B).countl_zero() + 1);
3007}
3008
3010 bool MatchAllBits) {
3011 unsigned OldBitWidth = A.getBitWidth();
3012 assert((((OldBitWidth % NewBitWidth) == 0) ||
3013 ((NewBitWidth % OldBitWidth) == 0)) &&
3014 "One size should be a multiple of the other one. "
3015 "Can't do fractional scaling.");
3016
3017
3018 if (OldBitWidth == NewBitWidth)
3019 return A;
3020
3022
3023
3024 if (A.isZero())
3025 return NewA;
3026
3027 if (NewBitWidth > OldBitWidth) {
3028
3029 unsigned Scale = NewBitWidth / OldBitWidth;
3030 for (unsigned i = 0; i != OldBitWidth; ++i)
3031 if (A[i])
3032 NewA.setBits(i * Scale, (i + 1) * Scale);
3033 } else {
3034 unsigned Scale = OldBitWidth / NewBitWidth;
3035 for (unsigned i = 0; i != NewBitWidth; ++i) {
3036 if (MatchAllBits) {
3037 if (A.extractBits(Scale, i * Scale).isAllOnes())
3039 } else {
3040 if (.extractBits(Scale, i * Scale).isZero())
3042 }
3043 }
3044 }
3045
3046 return NewA;
3047}
3048
3049
3050
3052 unsigned StoreBytes) {
3053 assert((IntVal.getBitWidth()+7)/8 >= StoreBytes && "Integer too small!");
3054 const uint8_t *Src = (const uint8_t *)IntVal.getRawData();
3055
3057
3058
3059 memcpy(Dst, Src, StoreBytes);
3060 } else {
3061
3062
3063
3064 while (StoreBytes > sizeof(uint64_t)) {
3065 StoreBytes -= sizeof(uint64_t);
3066
3067 memcpy(Dst + StoreBytes, Src, sizeof(uint64_t));
3069 }
3070
3071 memcpy(Dst, Src + sizeof(uint64_t) - StoreBytes, StoreBytes);
3072 }
3073}
3074
3075
3076
3078 unsigned LoadBytes) {
3079 assert((IntVal.getBitWidth()+7)/8 >= LoadBytes && "Integer too small!");
3081 const_cast<uint64_t *>(IntVal.getRawData()));
3082
3084
3085
3086 memcpy(Dst, Src, LoadBytes);
3087 else {
3088
3089
3090
3091
3092 while (LoadBytes > sizeof(uint64_t)) {
3093 LoadBytes -= sizeof(uint64_t);
3094
3095 memcpy(Dst, Src + LoadBytes, sizeof(uint64_t));
3097 }
3098
3099 memcpy(Dst + sizeof(uint64_t) - LoadBytes, Src, LoadBytes);
3100 }
3101}
3102
3104
3105 return (C1 & C2) + (C1 ^ C2).ashr(1);
3106}
3107
3109
3110 return (C1 & C2) + (C1 ^ C2).lshr(1);
3111}
3112
3114
3115 return (C1 | C2) - (C1 ^ C2).ashr(1);
3116}
3117
3119
3120 return (C1 | C2) - (C1 ^ C2).lshr(1);
3121}
3122
3130
3138
3141 unsigned FullWidth = C1.getBitWidth() * 2;
3142 APInt C1Ext = C1.sext(FullWidth);
3143 APInt C2Ext = C2.sext(FullWidth);
3144 return C1Ext * C2Ext;
3145}
3146
3149 unsigned FullWidth = C1.getBitWidth() * 2;
3150 APInt C1Ext = C1.zext(FullWidth);
3151 APInt C2Ext = C2.zext(FullWidth);
3152 return C1Ext * C2Ext;
3153}
3154
3156 assert(N >= 0 && "negative exponents not supported.");
3158 if (N == 0)
3159 return Acc;
3161 int64_t RemainingExponent = N;
3162 while (RemainingExponent > 0) {
3163 while (RemainingExponent % 2 == 0) {
3165 RemainingExponent /= 2;
3166 }
3167 --RemainingExponent;
3168 Acc *= Base;
3169 }
3170 return Acc;
3171}
3172
3174 const APInt &Shift) {
3175 assert(Hi.getBitWidth() == Lo.getBitWidth());
3176 unsigned ShiftAmt = rotateModulo(Hi.getBitWidth(), Shift);
3177 if (ShiftAmt == 0)
3178 return Hi;
3179 return Hi.shl(ShiftAmt) | Lo.lshr(Hi.getBitWidth() - ShiftAmt);
3180}
3181
3183 const APInt &Shift) {
3184 assert(Hi.getBitWidth() == Lo.getBitWidth());
3185 unsigned ShiftAmt = rotateModulo(Hi.getBitWidth(), Shift);
3186 if (ShiftAmt == 0)
3187 return Lo;
3188 return Hi.shl(Hi.getBitWidth() - ShiftAmt) | Lo.lshr(ShiftAmt);
3189}
3190
3192 assert(LHS.getBitWidth() == RHS.getBitWidth());
3193 unsigned BW = LHS.getBitWidth();
3194 APInt Result(BW, 0);
3196 if (RHS[I])
3197 Result ^= LHS.shl(I);
3198 return Result;
3199}
3200
3202 assert(LHS.getBitWidth() == RHS.getBitWidth());
3203 return clmul(LHS.reverseBits(), RHS.reverseBits()).reverseBits();
3204}
3205
3207 assert(LHS.getBitWidth() == RHS.getBitWidth());
3208 return clmulr(LHS, RHS).lshr(1);
3209}
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
static APInt::WordType lowHalf(APInt::WordType part)
Returns the value of the lower half of PART.
Definition APInt.cpp:2329
static unsigned rotateModulo(unsigned BitWidth, const APInt &rotateAmt)
Definition APInt.cpp:1123
static APInt::WordType highHalf(APInt::WordType part)
Returns the value of the upper half of PART.
Definition APInt.cpp:2334
static void tcComplement(APInt::WordType *dst, unsigned parts)
Definition APInt.cpp:367
static unsigned getDigit(char cdigit, uint8_t radix)
A utility function that converts a character to a digit.
Definition APInt.cpp:47
static APInt::WordType lowBitMask(unsigned bits)
Definition APInt.cpp:2323
static uint64_t * getMemory(unsigned numWords)
A utility function for allocating memory and checking for allocation failure.
Definition APInt.cpp:42
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...
Definition APInt.cpp:1290
static uint64_t * getClearedMemory(unsigned numWords)
A utility function for allocating memory, checking for allocation failures, and ensuring the contents...
Definition APInt.cpp:36
This file implements a class to represent arbitrary precision integral constant values and operations...
static constexpr unsigned long long mask(BlockVerifier::State S)
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#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 bool isSigned(unsigned int Opcode)
This file defines a hash set that can be used to remove duplication of nodes in a graph.
static uint64_t clearUnusedBits(uint64_t Val, unsigned Size)
Provides some synthesis utilities to produce sequences of values.
This file defines the SmallString class.
static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")
This file implements the C++20 header.
Class for arbitrary precision integers.
LLVM_ABI APInt umul_ov(const APInt &RHS, bool &Overflow) const
Definition APInt.cpp:1971
LLVM_ABI APInt usub_sat(const APInt &RHS) const
Definition APInt.cpp:2055
LLVM_ABI APInt udiv(const APInt &RHS) const
Unsigned division operation.
Definition APInt.cpp:1573
static LLVM_ABI void tcSetBit(WordType *, unsigned bit)
Set the given bit of a bignum. Zero-based.
Definition APInt.cpp:2368
static LLVM_ABI void tcSet(WordType *, WordType, unsigned)
Sets the least significant part of a bignum to the input value, and zeroes out higher parts.
Definition APInt.cpp:2340
LLVM_ABI unsigned nearestLogBase2() const
Definition APInt.cpp:1172
static LLVM_ABI void udivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, APInt &Remainder)
Dual division/remainder interface.
Definition APInt.cpp:1758
LLVM_ABI APInt getLoBits(unsigned numBits) const
Compute an APInt containing numBits lowbits from this APInt.
Definition APInt.cpp:644
static LLVM_ABI int tcExtractBit(const WordType *, unsigned bit)
Extract the given bit of a bignum; returns 0 or 1. Zero-based.
Definition APInt.cpp:2363
LLVM_ABI bool isAligned(Align A) const
Checks if this APInt -interpreted as an address- is aligned to the provided value.
Definition APInt.cpp:169
LLVM_ABI APInt zext(unsigned width) const
Zero extend to a new width.
Definition APInt.cpp:1012
bool isMinSignedValue() const
Determine if this is the smallest signed value.
uint64_t getZExtValue() const
Get zero extended value.
LLVM_ABI APInt truncUSat(unsigned width) const
Truncate to new width with unsigned saturation.
Definition APInt.cpp:962
uint64_t * pVal
Used to store the >64 bits integer value.
static LLVM_ABI void sdivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, APInt &Remainder)
Definition APInt.cpp:1890
static LLVM_ABI WordType tcAdd(WordType *, const WordType *, WordType carry, unsigned)
DST += RHS + CARRY where CARRY is zero or one. Returns the carry flag.
Definition APInt.cpp:2442
static LLVM_ABI 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,...
Definition APInt.cpp:2412
LLVM_ABI uint64_t extractBitsAsZExtValue(unsigned numBits, unsigned bitPosition) const
Definition APInt.cpp:520
LLVM_ABI APInt getHiBits(unsigned numBits) const
Compute an APInt containing numBits highbits from this APInt.
Definition APInt.cpp:639
LLVM_ABI APInt zextOrTrunc(unsigned width) const
Zero extend or truncate to width.
Definition APInt.cpp:1033
unsigned getActiveBits() const
Compute the number of active bits in the value.
static LLVM_ABI unsigned getSufficientBitsNeeded(StringRef Str, uint8_t Radix)
Get the bits that are sufficient to represent the string value.
Definition APInt.cpp:544
LLVM_ABI APInt trunc(unsigned width) const
Truncate to new width.
Definition APInt.cpp:936
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.
LLVM_ABI APInt sshl_ov(const APInt &Amt, bool &Overflow) const
Definition APInt.cpp:1988
LLVM_ABI APInt smul_sat(const APInt &RHS) const
Definition APInt.cpp:2064
LLVM_ABI APInt sadd_sat(const APInt &RHS) const
Definition APInt.cpp:2026
bool sgt(const APInt &RHS) const
Signed greater than comparison.
static LLVM_ABI int tcCompare(const WordType *, const WordType *, unsigned)
Comparison (unsigned) of two bignums.
Definition APInt.cpp:2752
LLVM_ABI APInt & operator++()
Prefix increment operator.
Definition APInt.cpp:178
LLVM_ABI APInt usub_ov(const APInt &RHS, bool &Overflow) const
Definition APInt.cpp:1948
APInt(unsigned numBits, uint64_t val, bool isSigned=false, bool implicitTrunc=false)
Create a new APInt of numBits width, initialized as val.
bool ugt(const APInt &RHS) const
Unsigned greater than comparison.
LLVM_ABI void print(raw_ostream &OS, bool isSigned) const
Definition APInt.cpp:2307
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
LLVM_ABI APInt urem(const APInt &RHS) const
Unsigned remainder operation.
Definition APInt.cpp:1666
static LLVM_ABI void tcAssign(WordType *, const WordType *, unsigned)
Assign one bignum to another.
Definition APInt.cpp:2348
static constexpr unsigned APINT_WORD_SIZE
Byte size of a word.
unsigned getBitWidth() const
Return the number of bits in the APInt.
static LLVM_ABI void tcShiftRight(WordType *, unsigned Words, unsigned Count)
Shift a bignum right Count bits.
Definition APInt.cpp:2726
static LLVM_ABI void tcFullMultiply(WordType *, const WordType *, const WordType *, unsigned, unsigned)
DST = LHS * RHS, where DST has width the sum of the widths of the operands.
Definition APInt.cpp:2632
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.
LLVM_ABI APInt sfloordiv_ov(const APInt &RHS, bool &Overflow) const
Signed integer floor division operation.
Definition APInt.cpp:2019
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.
LLVM_ABI APInt sadd_ov(const APInt &RHS, bool &Overflow) const
Definition APInt.cpp:1928
APInt & operator<<=(unsigned ShiftAmt)
Left-shift assignment function.
LLVM_ABI APInt sdiv(const APInt &RHS) const
Signed division function for APInt.
Definition APInt.cpp:1644
double roundToDouble() const
Converts this unsigned APInt to a double value.
LLVM_ABI APInt rotr(unsigned rotateAmt) const
Rotate right by rotateAmt.
Definition APInt.cpp:1154
LLVM_ABI APInt reverseBits() const
Definition APInt.cpp:768
void ashrInPlace(unsigned ShiftAmt)
Arithmetic right-shift this APInt by ShiftAmt in place.
LLVM_ABI APInt uadd_ov(const APInt &RHS, bool &Overflow) const
Definition APInt.cpp:1935
static LLVM_ABI void tcClearBit(WordType *, unsigned bit)
Clear the given bit of a bignum. Zero-based.
Definition APInt.cpp:2373
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.
LLVM_ABI bool isSplat(unsigned SplatSizeInBits) const
Check if the APInt consists of a repeated bit pattern.
Definition APInt.cpp:630
LLVM_ABI APInt & operator-=(const APInt &RHS)
Subtraction assignment operator.
Definition APInt.cpp:218
bool isSignedIntN(unsigned N) const
Check if this APInt has an N-bits signed integer value.
LLVM_ABI APInt sdiv_ov(const APInt &RHS, bool &Overflow) const
Definition APInt.cpp:1954
LLVM_ABI APInt operator*(const APInt &RHS) const
Multiplication operator.
Definition APInt.cpp:235
static LLVM_ABI unsigned tcLSB(const WordType *, unsigned n)
Returns the bit number of the least or most significant set bit of a number.
Definition APInt.cpp:2379
unsigned countl_zero() const
The APInt version of std::countl_zero.
static LLVM_ABI void tcShiftLeft(WordType *, unsigned Words, unsigned Count)
Shift a bignum left Count bits.
Definition APInt.cpp:2699
static LLVM_ABI APInt getSplat(unsigned NewLen, const APInt &V)
Return a value containing V broadcasted over NewLen bits.
Definition APInt.cpp:651
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
LLVM_ABI APInt sshl_sat(const APInt &RHS) const
Definition APInt.cpp:2086
static constexpr WordType WORDTYPE_MAX
LLVM_ABI APInt ushl_sat(const APInt &RHS) const
Definition APInt.cpp:2100
LLVM_ABI APInt ushl_ov(const APInt &Amt, bool &Overflow) const
Definition APInt.cpp:2005
static LLVM_ABI WordType tcSubtractPart(WordType *, WordType, unsigned)
DST -= RHS. Returns the carry flag.
Definition APInt.cpp:2502
static LLVM_ABI bool tcIsZero(const WordType *, unsigned)
Returns true if a bignum is zero, false otherwise.
Definition APInt.cpp:2354
LLVM_ABI APInt sextOrTrunc(unsigned width) const
Sign extend or truncate to width.
Definition APInt.cpp:1041
static LLVM_ABI unsigned tcMSB(const WordType *parts, unsigned n)
Returns the bit number of the most significant set bit of a number.
Definition APInt.cpp:2392
static LLVM_ABI 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.
Definition APInt.cpp:2657
LLVM_DUMP_METHOD void dump() const
debug method
Definition APInt.cpp:2298
LLVM_ABI APInt rotl(unsigned rotateAmt) const
Rotate left by rotateAmt.
Definition APInt.cpp:1141
unsigned countl_one() const
Count the number of leading one bits.
LLVM_ABI void insertBits(const APInt &SubBits, unsigned bitPosition)
Insert the bits from a smaller APInt starting at bitPosition.
Definition APInt.cpp:397
unsigned logBase2() const
static LLVM_ABI 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.
Definition APInt.cpp:2530
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 LLVM_ABI 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...
Definition APInt.cpp:2614
LLVM_ABI APInt uadd_sat(const APInt &RHS) const
Definition APInt.cpp:2036
LLVM_ABI APInt & operator*=(const APInt &RHS)
Multiplication assignment operator.
Definition APInt.cpp:265
uint64_t VAL
Used to store the <= 64 bits integer value.
static LLVM_ABI unsigned getBitsNeeded(StringRef str, uint8_t radix)
Get bits required for string value.
Definition APInt.cpp:576
static LLVM_ABI WordType tcSubtract(WordType *, const WordType *, WordType carry, unsigned)
DST -= RHS + CARRY where CARRY is zero or one. Returns the carry flag.
Definition APInt.cpp:2477
LLVM_ABI APInt multiplicativeInverse() const
Definition APInt.cpp:1274
static LLVM_ABI void tcNegate(WordType *, unsigned)
Negate a bignum in-place.
Definition APInt.cpp:2516
bool getBoolValue() const
Convert APInt to a boolean value.
LLVM_ABI APInt srem(const APInt &RHS) const
Function for signed remainder operation.
Definition APInt.cpp:1736
LLVM_ABI APInt smul_ov(const APInt &RHS, bool &Overflow) const
Definition APInt.cpp:1960
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.
LLVM_ABI APInt sext(unsigned width) const
Sign extend to a new width.
Definition APInt.cpp:985
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.
LLVM_ABI APInt byteSwap() const
Definition APInt.cpp:746
LLVM_ABI APInt umul_sat(const APInt &RHS) const
Definition APInt.cpp:2077
bool isPowerOf2() const
Check if this APInt's value is a power of two greater than zero.
LLVM_ABI APInt & operator+=(const APInt &RHS)
Addition assignment operator.
Definition APInt.cpp:198
LLVM_ABI void flipBit(unsigned bitPosition)
Toggles a given bit to its opposite value.
Definition APInt.cpp:392
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
static LLVM_ABI WordType tcAddPart(WordType *, WordType, unsigned)
DST += RHS. Returns the carry flag.
Definition APInt.cpp:2464
const uint64_t * getRawData() const
This function returns a pointer to the internal storage of the APInt.
LLVM_ABI void Profile(FoldingSetNodeID &id) const
Used to insert APInt objects, or objects that contain APInt objects, into FoldingSets.
Definition APInt.cpp:156
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
LLVM_ABI APInt extractBits(unsigned numBits, unsigned bitPosition) const
Return an APInt with the extracted bits [bitPosition,bitPosition+numBits).
Definition APInt.cpp:482
bool isIntN(unsigned N) const
Check if this APInt has an N-bits unsigned integer value.
LLVM_ABI APInt ssub_ov(const APInt &RHS, bool &Overflow) const
Definition APInt.cpp:1941
LLVM_ABI APInt & operator--()
Prefix decrement operator.
Definition APInt.cpp:187
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.
LLVM_ABI APInt sqrt() const
Compute the square root.
Definition APInt.cpp:1199
void setBitVal(unsigned BitPosition, bool BitValue)
Set a given bit to a given value.
LLVM_ABI APInt ssub_sat(const APInt &RHS) const
Definition APInt.cpp:2045
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.
LLVM_ABI APInt truncSSat(unsigned width) const
Truncate to new width with signed saturation.
Definition APInt.cpp:973
LLVM_ABI 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.
Definition APInt.cpp:2164
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.
LLVM_ABI 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...
Definition APInt.cpp:3002
LLVM_ABI APInt clmulr(const APInt &LHS, const APInt &RHS)
Perform a reversed carry-less multiply.
Definition APInt.cpp:3201
LLVM_ABI APInt mulhu(const APInt &C1, const APInt &C2)
Performs (2*N)-bit multiplication on zero-extended operands.
Definition APInt.cpp:3131
LLVM_ABI APInt RoundingUDiv(const APInt &A, const APInt &B, APInt::Rounding RM)
Return A unsign-divided by B, rounded by the given rounding mode.
Definition APInt.cpp:2763
LLVM_ABI APInt avgCeilU(const APInt &C1, const APInt &C2)
Compute the ceil of the unsigned average of C1 and C2.
Definition APInt.cpp:3118
LLVM_ABI APInt muluExtended(const APInt &C1, const APInt &C2)
Performs (2*N)-bit multiplication on zero-extended operands.
Definition APInt.cpp:3147
LLVM_ABI APInt mulsExtended(const APInt &C1, const APInt &C2)
Performs (2*N)-bit multiplication on sign-extended operands.
Definition APInt.cpp:3139
LLVM_ABI APInt avgFloorU(const APInt &C1, const APInt &C2)
Compute the floor of the unsigned average of C1 and C2.
Definition APInt.cpp:3108
LLVM_ABI APInt fshr(const APInt &Hi, const APInt &Lo, const APInt &Shift)
Perform a funnel shift right.
Definition APInt.cpp:3182
LLVM_ABI APInt mulhs(const APInt &C1, const APInt &C2)
Performs (2*N)-bit multiplication on sign-extended operands.
Definition APInt.cpp:3123
LLVM_ABI APInt RoundingSDiv(const APInt &A, const APInt &B, APInt::Rounding RM)
Return A sign-divided by B, rounded by the given rounding mode.
Definition APInt.cpp:2781
LLVM_ABI APInt clmul(const APInt &LHS, const APInt &RHS)
Perform a carry-less multiply, also known as XOR multiplication, and return low-bits.
Definition APInt.cpp:3191
LLVM_ABI APInt pow(const APInt &X, int64_t N)
Compute X^N for N>=0.
Definition APInt.cpp:3155
LLVM_ABI APInt RoundDoubleToAPInt(double Double, unsigned width)
Converts the given double value into a APInt.
Definition APInt.cpp:841
LLVM_ABI APInt fshl(const APInt &Hi, const APInt &Lo, const APInt &Shift)
Perform a funnel shift left.
Definition APInt.cpp:3173
LLVM_ABI APInt ScaleBitMask(const APInt &A, unsigned NewBitWidth, bool MatchAllBits=false)
Splat/Merge neighboring bits to widen/narrow the bitmask represented by.
Definition APInt.cpp:3009
LLVM_ABI 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.
Definition APInt.cpp:2812
LLVM_ABI APInt clmulh(const APInt &LHS, const APInt &RHS)
Perform a carry-less multiply, and return high-bits.
Definition APInt.cpp:3206
LLVM_ABI APInt avgFloorS(const APInt &C1, const APInt &C2)
Compute the floor of the signed average of C1 and C2.
Definition APInt.cpp:3103
LLVM_ABI APInt avgCeilS(const APInt &C1, const APInt &C2)
Compute the ceil of the signed average of C1 and C2.
Definition APInt.cpp:3113
LLVM_ABI APInt GreatestCommonDivisor(APInt A, APInt B)
Compute GCD of two unsigned APInt values.
Definition APInt.cpp:798
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ C
The default llvm calling convention, compatible with C.
support::ulittle32_t Word
constexpr bool IsLittleEndianHost
This is an optimization pass for GlobalISel generic memory operations.
hash_code hash_value(const FixedPointSemantics &Val)
LLVM_ABI 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...
Definition APInt.cpp:3051
int countr_one(T Value)
Count the number of ones from the least significant bit to the first zero bit.
constexpr T byteswap(T V) noexcept
Reverses the bytes in the given integer value V.
constexpr int popcount(T Value) noexcept
Count the number of set bits in a value.
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.
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
FunctionAddr VTableAddr Count
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.
LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key
@ Mod
The access may modify the value stored in memory.
To bit_cast(const From &from) noexcept
ArrayRef(const T &OneElt) -> ArrayRef< T >
constexpr unsigned BitWidth
constexpr T reverseBits(T Val)
Reverse the bits in Val.
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.
auto seq(T Begin, T End)
Iterate over an integral type from Begin up to - but not including - End.
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
constexpr T maskTrailingOnes(unsigned N)
Create a bitmask with the N right-most bits set to 1, and all other bits set to 0.
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.
LLVM_ABI void LoadIntFromMemory(APInt &IntVal, const uint8_t *Src, unsigned LoadBytes)
LoadIntFromMemory - Loads the integer stored in the LoadBytes bytes starting from Src into IntVal,...
Definition APInt.cpp:3077
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)