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

773 if (A == B) return A;

774

775

776 if (A) return B;

777 if (B) 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

801 while (A != B) {

802 if (A.ugt(B)) {

803 A -= B;

804 A.lshrInPlace(A.countr_zero() - Pow2);

805 } else {

806 B -= A;

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

818 bool isNeg = I >> 63;

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) {

1463 U[i * 2] = Lo_32(tmp);

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) {

1472 V[i * 2] = Lo_32(tmp);

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))

1663

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

1911 Overflow = Res.ult(RHS);

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) {

2193 N = I;

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) {

2742 return A.udiv(B);

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

2779 return A.sdiv(B);

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;

2817 A = A.sext(CoeffWidth);

2818 B = B.sext(CoeffWidth);

2819 C = C.sext(CoeffWidth);

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

2871 C = C.srem(R);

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

2893 C -= -RoundUp(-C, R);

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");

2915 APInt SQ = D.sqrt();

2916

2917 APInt Q = SQ * SQ;

2918 bool InexactSQ = Q != D;

2919

2920

2921 if (Q.sgt(D))

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");

2977 if (A == B)

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 (A.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)