APInt.cpp

Go to the documentation of this file.

1//===-- APInt.cpp - Implement APInt class ---------------------------------===//

2//

3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

4// See https://llvm.org/LICENSE.txt for license information.

5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

6//

7//===----------------------------------------------------------------------===//

8//

9// This file implements a class to represent arbitrary precision integer

10// constant values and provide a variety of arithmetic operations on them.

11//

12//===----------------------------------------------------------------------===//

13

14#include "llvm/ADT/APInt.h"

15#include "llvm/ADT/ArrayRef.h"

16#include "llvm/ADT/FoldingSet.h"

17#include "llvm/ADT/Hashing.h"

18#include "llvm/ADT/SmallString.h"

19#include "llvm/ADT/StringRef.h"

20#include "llvm/ADT/bit.h"

21#include "llvm/Config/llvm-config.h"

22#include "llvm/Support/Alignment.h"

23#include "llvm/Support/Debug.h"

24#include "llvm/Support/ErrorHandling.h"

25#include "llvm/Support/MathExtras.h"

26#include "llvm/Support/raw_ostream.h"

27#include <cmath>

28#include <optional>

29

30using namespace llvm;

31

32 #define DEBUG_TYPE "apint"

33

34/// A utility function for allocating memory, checking for allocation failures,

35/// and ensuring the contents are zeroed.

36 inline static uint64_t* getClearedMemory(unsigned numWords) {

37 return new uint64_t[numWords]();

38}

39

40/// A utility function for allocating memory and checking for allocation

41/// failure. The content is not zeroed.

42 inline static uint64_t* getMemory(unsigned numWords) {

43 return new uint64_t[numWords];

44}

45

46/// A utility function that converts a character to a digit.

47 inline static unsigned getDigit(char cdigit, uint8_t radix) {

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

74void APInt::initSlowCase(uint64_t val, bool isSigned) {

75 if (isSigned && int64_t(val) < 0) {

76 U.pVal = getMemory(getNumWords());

77 U.pVal[0] = val;

78 memset(&U.pVal[1], 0xFF, APINT_WORD_SIZE * (getNumWords() - 1));

79 clearUnusedBits();

80 } else {

81 U.pVal = getClearedMemory(getNumWords());

82 U.pVal[0] = val;

83 }

84}

85

86void APInt::initSlowCase(const APInt& that) {

87 U.pVal = getMemory(getNumWords());

88 memcpy(U.pVal, that.U.pVal, getNumWords() * APINT_WORD_SIZE);

89}

90

91void APInt::initFromArray(ArrayRef<uint64_t> bigVal) {

92 assert(bigVal.data() && "Null pointer detected!");

93 if (isSingleWord())

94 U.VAL = bigVal[0];

95 else {

96 // Get memory, cleared to 0

97 U.pVal = getClearedMemory(getNumWords());

98 // Calculate the number of words to copy

99 unsigned words = std::min<unsigned>(bigVal.size(), getNumWords());

100 // Copy the words from bigVal to pVal

101 memcpy(U.pVal, bigVal.data(), words * APINT_WORD_SIZE);

102 }

103 // Make sure unused high bits are cleared

104 clearUnusedBits();

105}

106

107 APInt::APInt(unsigned numBits, ArrayRef<uint64_t> bigVal) : BitWidth(numBits) {

108 initFromArray(bigVal);

109}

110

111 APInt::APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[])

112 : BitWidth(numBits) {

113 initFromArray(ArrayRef(bigVal, numWords));

114}

115

116 APInt::APInt(unsigned numbits, StringRef Str, uint8_t radix)

117 : BitWidth(numbits) {

118 fromString(numbits, Str, radix);

119}

120

121void APInt::reallocate(unsigned NewBitWidth) {

122 // If the number of words is the same we can just change the width and stop.

123 if (getNumWords() == getNumWords(NewBitWidth)) {

124 BitWidth = NewBitWidth;

125 return;

126 }

127

128 // If we have an allocation, delete it.

129 if (!isSingleWord())

130 delete [] U.pVal;

131

132 // Update BitWidth.

133 BitWidth = NewBitWidth;

134

135 // If we are supposed to have an allocation, create it.

136 if (!isSingleWord())

137 U.pVal = getMemory(getNumWords());

138}

139

140void APInt::assignSlowCase(const APInt &RHS) {

141 // Don't do anything for X = X

142 if (this == &RHS)

143 return;

144

145 // Adjust the bit width and handle allocations as necessary.

146 reallocate(RHS.getBitWidth());

147

148 // Copy the data.

149 if (isSingleWord())

150 U.VAL = RHS.U.VAL;

151 else

152 memcpy(U.pVal, RHS.U.pVal, getNumWords() * APINT_WORD_SIZE);

153}

154

155/// This method 'profiles' an APInt for use with FoldingSet.

156 void APInt::Profile(FoldingSetNodeID& ID) const {

157 ID.AddInteger(BitWidth);

158

159 if (isSingleWord()) {

160 ID.AddInteger(U.VAL);

161 return;

162 }

163

164 unsigned NumWords = getNumWords();

165 for (unsigned i = 0; i < NumWords; ++i)

166 ID.AddInteger(U.pVal[i]);

167}

168

169 bool APInt::isAligned(Align A) const {

170 if (isZero())

171 return true;

172 const unsigned TrailingZeroes = countr_zero();

173 const unsigned MinimumTrailingZeroes = Log2(A);

174 return TrailingZeroes >= MinimumTrailingZeroes;

175}

176

177/// Prefix increment operator. Increments the APInt by one.

178 APInt& APInt::operator++() {

179 if (isSingleWord())

180 ++U.VAL;

181 else

182 tcIncrement(U.pVal, getNumWords());

183 return clearUnusedBits();

184}

185

186/// Prefix decrement operator. Decrements the APInt by one.

187 APInt& APInt::operator--() {

188 if (isSingleWord())

189 --U.VAL;

190 else

191 tcDecrement(U.pVal, getNumWords());

192 return clearUnusedBits();

193}

194

195/// Adds the RHS APInt to this APInt.

196/// @returns this, after addition of RHS.

197/// Addition assignment operator.

198 APInt& APInt::operator+=(const APInt& RHS) {

199 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");

200 if (isSingleWord())

201 U.VAL += RHS.U.VAL;

202 else

203 tcAdd(U.pVal, RHS.U.pVal, 0, getNumWords());

204 return clearUnusedBits();

205}

206

207 APInt& APInt::operator+=(uint64_t RHS) {

208 if (isSingleWord())

209 U.VAL += RHS;

210 else

211 tcAddPart(U.pVal, RHS, getNumWords());

212 return clearUnusedBits();

213}

214

215/// Subtracts the RHS APInt from this APInt

216/// @returns this, after subtraction

217/// Subtraction assignment operator.

218 APInt& APInt::operator-=(const APInt& RHS) {

219 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");

220 if (isSingleWord())

221 U.VAL -= RHS.U.VAL;

222 else

223 tcSubtract(U.pVal, RHS.U.pVal, 0, getNumWords());

224 return clearUnusedBits();

225}

226

227 APInt& APInt::operator-=(uint64_t RHS) {

228 if (isSingleWord())

229 U.VAL -= RHS;

230 else

231 tcSubtractPart(U.pVal, RHS, getNumWords());

232 return clearUnusedBits();

233}

234

235 APInt APInt::operator*(const APInt& RHS) const {

236 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");

237 if (isSingleWord())

238 return APInt(BitWidth, U.VAL * RHS.U.VAL, /*isSigned=*/false,

239 /*implicitTrunc=*/true);

240

241 APInt Result(getMemory(getNumWords()), getBitWidth());

242 tcMultiply(Result.U.pVal, U.pVal, RHS.U.pVal, getNumWords());

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

265 APInt &APInt::operator*=(const APInt &RHS) {

266 *this = *this * RHS;

267 return *this;

268}

269

270 APInt& APInt::operator*=(uint64_t RHS) {

271 if (isSingleWord()) {

272 U.VAL *= RHS;

273 } else {

274 unsigned NumWords = getNumWords();

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

286 if (isSingleWord())

287 return U.VAL < RHS.U.VAL ? -1 : U.VAL > RHS.U.VAL;

288

289 return tcCompare(U.pVal, RHS.U.pVal, getNumWords());

290}

291

292int APInt::compareSigned(const APInt& RHS) const {

293 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");

294 if (isSingleWord()) {

295 int64_t lhsSext = SignExtend64(U.VAL, BitWidth);

296 int64_t rhsSext = SignExtend64(RHS.U.VAL, BitWidth);

297 return lhsSext < rhsSext ? -1 : lhsSext > rhsSext;

298 }

299

300 bool lhsNeg = isNegative();

301 bool rhsNeg = RHS.isNegative();

302

303 // If the sign bits don't match, then (LHS < RHS) if LHS is negative

304 if (lhsNeg != rhsNeg)

305 return lhsNeg ? -1 : 1;

306

307 // Otherwise we can just use an unsigned comparison, because even negative

308 // numbers compare correctly this way if both have the same signed-ness.

309 return tcCompare(U.pVal, RHS.U.pVal, getNumWords());

310}

311

312void APInt::setBitsSlowCase(unsigned loBit, unsigned hiBit) {

313 unsigned loWord = whichWord(loBit);

314 unsigned hiWord = whichWord(hiBit);

315

316 // Create an initial mask for the low word with zeros below loBit.

317 uint64_t loMask = WORDTYPE_MAX << whichBit(loBit);

318

319 // If hiBit is not aligned, we need a high mask.

320 unsigned hiShiftAmt = whichBit(hiBit);

321 if (hiShiftAmt != 0) {

322 // Create a high mask with zeros above hiBit.

323 uint64_t hiMask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - hiShiftAmt);

324 // If loWord and hiWord are equal, then we combine the masks. Otherwise,

325 // set the bits in hiWord.

326 if (hiWord == loWord)

327 loMask &= hiMask;

328 else

329 U.pVal[hiWord] |= hiMask;

330 }

331 // Apply the mask to the low word.

332 U.pVal[loWord] |= loMask;

333

334 // Fill any words between loWord and hiWord with all ones.

335 for (unsigned word = loWord + 1; word < hiWord; ++word)

336 U.pVal[word] = WORDTYPE_MAX;

337}

338

339void APInt::clearBitsSlowCase(unsigned LoBit, unsigned HiBit) {

340 unsigned LoWord = whichWord(LoBit);

341 unsigned HiWord = whichWord(HiBit);

342

343 // Create an initial mask for the low word with ones below loBit.

344 uint64_t LoMask = ~(WORDTYPE_MAX << whichBit(LoBit));

345

346 // If HiBit is not aligned, we need a high mask.

347 unsigned HiShiftAmt = whichBit(HiBit);

348 if (HiShiftAmt != 0) {

349 // Create a high mask with ones above HiBit.

350 uint64_t HiMask = ~(WORDTYPE_MAX >> (APINT_BITS_PER_WORD - HiShiftAmt));

351 // If LoWord and HiWord are equal, then we combine the masks. Otherwise,

352 // clear the bits in HiWord.

353 if (HiWord == LoWord)

354 LoMask |= HiMask;

355 else

356 U.pVal[HiWord] &= HiMask;

357 }

358 // Apply the mask to the low word.

359 U.pVal[LoWord] &= LoMask;

360

361 // Fill any words between LoWord and HiWord with all zeros.

362 for (unsigned Word = LoWord + 1; Word < HiWord; ++Word)

363 U.pVal[Word] = 0;

364}

365

366// Complement a bignum in-place.

367 static void tcComplement(APInt::WordType *dst, unsigned parts) {

368 for (unsigned i = 0; i < parts; i++)

369 dst[i] = ~dst[i];

370}

371

372/// Toggle every bit to its opposite value.

373void APInt::flipAllBitsSlowCase() {

374 tcComplement(U.pVal, getNumWords());

375 clearUnusedBits();

376}

377

378/// Concatenate the bits from "NewLSB" onto the bottom of *this. This is

379/// equivalent to:

380/// (this->zext(NewWidth) << NewLSB.getBitWidth()) | NewLSB.zext(NewWidth)

381/// In the slow case, we know the result is large.

382APInt APInt::concatSlowCase(const APInt &NewLSB) const {

383 unsigned NewWidth = getBitWidth() + NewLSB.getBitWidth();

384 APInt Result = NewLSB.zext(NewWidth);

385 Result.insertBits(*this, NewLSB.getBitWidth());

386 return Result;

387}

388

389/// Toggle a given bit to its opposite value whose position is given

390/// as "bitPosition".

391/// Toggles a given bit to its opposite value.

392 void APInt::flipBit(unsigned bitPosition) {

393 assert(bitPosition < BitWidth && "Out of the bit-width range!");

394 setBitVal(bitPosition, !(*this)[bitPosition]);

395}

396

397 void APInt::insertBits(const APInt &subBits, unsigned bitPosition) {

398 unsigned subBitWidth = subBits.getBitWidth();

399 assert((subBitWidth + bitPosition) <= BitWidth && "Illegal bit insertion");

400

401 // inserting no bits is a noop.

402 if (subBitWidth == 0)

403 return;

404

405 // Insertion is a direct copy.

406 if (subBitWidth == BitWidth) {

407 *this = subBits;

408 return;

409 }

410

411 // Single word result can be done as a direct bitmask.

412 if (isSingleWord()) {

413 uint64_t mask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - subBitWidth);

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 // Insertion within a single word can be done as a direct bitmask.

424 if (loWord == hi1Word) {

425 uint64_t mask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - subBitWidth);

426 U.pVal[loWord] &= ~(mask << loBit);

427 U.pVal[loWord] |= (subBits.U.VAL << loBit);

428 return;

429 }

430

431 // Insert on word boundaries.

432 if (loBit == 0) {

433 // Direct copy whole words.

434 unsigned numWholeSubWords = subBitWidth / APINT_BITS_PER_WORD;

435 memcpy(U.pVal + loWord, subBits.getRawData(),

436 numWholeSubWords * APINT_WORD_SIZE);

437

438 // Mask+insert remaining bits.

439 unsigned remainingBits = subBitWidth % APINT_BITS_PER_WORD;

440 if (remainingBits != 0) {

441 uint64_t mask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - remainingBits);

442 U.pVal[hi1Word] &= ~mask;

443 U.pVal[hi1Word] |= subBits.getWord(subBitWidth - 1);

444 }

445 return;

446 }

447

448 // General case - set/clear individual bits in dst based on src.

449 // TODO - there is scope for optimization here, but at the moment this code

450 // path is barely used so prefer readability over performance.

451 for (unsigned i = 0; i != subBitWidth; ++i)

452 setBitVal(bitPosition + i, subBits[i]);

453}

454

455 void APInt::insertBits(uint64_t subBits, unsigned bitPosition, unsigned numBits) {

456 uint64_t maskBits = maskTrailingOnes<uint64_t>(numBits);

457 subBits &= maskBits;

458 if (isSingleWord()) {

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

482 APInt APInt::extractBits(unsigned numBits, unsigned bitPosition) const {

483 assert(bitPosition < BitWidth && (numBits + bitPosition) <= BitWidth &&

484 "Illegal bit extraction");

485

486 if (isSingleWord())

487 return APInt(numBits, U.VAL >> bitPosition, /*isSigned=*/false,

488 /*implicitTrunc=*/true);

489

490 unsigned loBit = whichBit(bitPosition);

491 unsigned loWord = whichWord(bitPosition);

492 unsigned hiWord = whichWord(bitPosition + numBits - 1);

493

494 // Single word result extracting bits from a single word source.

495 if (loWord == hiWord)

496 return APInt(numBits, U.pVal[loWord] >> loBit, /*isSigned=*/false,

497 /*implicitTrunc=*/true);

498

499 // Extracting bits that start on a source word boundary can be done

500 // as a fast memory copy.

501 if (loBit == 0)

502 return APInt(numBits, ArrayRef(U.pVal + loWord, 1 + hiWord - loWord));

503

504 // General case - shift + copy source words directly into place.

505 APInt Result(numBits, 0);

506 unsigned NumSrcWords = getNumWords();

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];

512 uint64_t w1 =

513 (loWord + word + 1) < NumSrcWords ? U.pVal[loWord + word + 1] : 0;

514 DestPtr[word] = (w0 >> loBit) | (w1 << (APINT_BITS_PER_WORD - loBit));

515 }

516

517 return Result.clearUnusedBits();

518}

519

520 uint64_t APInt::extractBitsAsZExtValue(unsigned numBits,

521 unsigned bitPosition) const {

522 assert(bitPosition < BitWidth && (numBits + bitPosition) <= BitWidth &&

523 "Illegal bit extraction");

524 assert(numBits <= 64 && "Illegal bit extraction");

525

526 uint64_t maskBits = maskTrailingOnes<uint64_t>(numBits);

527 if (isSingleWord())

528 return (U.VAL >> bitPosition) & maskBits;

529

530 static_assert(APINT_BITS_PER_WORD >= 64,

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;

539 retBits |= U.pVal[hiWord] << (APINT_BITS_PER_WORD - loBit);

540 retBits &= maskBits;

541 return retBits;

542}

543

544 unsigned APInt::getSufficientBitsNeeded(StringRef Str, uint8_t Radix) {

545 assert(!Str.empty() && "Invalid string length");

546 size_t StrLen = Str.size();

547

548 // Each computation below needs to know if it's negative.

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 // For radixes of power-of-two values, the bits required is accurately and

557 // easily computed.

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 // Compute a sufficient number of bits that is always large enough but might

566 // be too large. This avoids the assertion in the constructor. This

567 // calculation doesn't work appropriately for the numbers 0-9, so just use 4

568 // bits in that case.

569 if (Radix == 10)

570 return (StrLen == 1 ? 4 : StrLen * 64 / 18) + IsNegative;

571

572 assert(Radix == 36);

573 return (StrLen == 1 ? 7 : StrLen * 16 / 3) + IsNegative;

574}

575

576 unsigned APInt::getBitsNeeded(StringRef str, uint8_t radix) {

577 // Compute a sufficient number of bits that is always large enough but might

578 // be too large.

579 unsigned sufficient = getSufficientBitsNeeded(str, radix);

580

581 // For bases 2, 8, and 16, the sufficient number of bits is exact and we can

582 // return the value directly. For bases 10 and 36, we need to do extra work.

583 if (radix == 2 || radix == 8 || radix == 16)

584 return sufficient;

585

586 // This is grossly inefficient but accurate. We could probably do something

587 // with a computation of roughly slen*64/20 and then adjust by the value of

588 // the first few digits. But, I'm not sure how accurate that could be.

589 size_t slen = str.size();

590

591 // Each computation below needs to know if it's negative.

592 StringRef::iterator p = str.begin();

593 unsigned isNegative = *p == '-';

594 if (*p == '-' || *p == '+') {

595 p++;

596 slen--;

597 assert(slen && "String is only a sign, needs a value.");

598 }

599

600

601 // Convert to the actual binary value.

602 APInt tmp(sufficient, StringRef(p, slen), radix);

603

604 // Compute how many bits are required. If the log is infinite, assume we need

605 // just bit. If the log is exact and value is negative, then the value is

606 // MinSignedValue with (log + 1) bits.

607 unsigned log = tmp.logBase2();

608 if (log == (unsigned)-1) {

609 return isNegative + 1;

610 } else if (isNegative && tmp.isPowerOf2()) {

611 return isNegative + log;

612 } else {

613 return isNegative + log + 1;

614 }

615}

616

617 hash_code llvm::hash_value(const APInt &Arg) {

618 if (Arg.isSingleWord())

619 return hash_combine(Arg.BitWidth, Arg.U.VAL);

620

621 return hash_combine(

622 Arg.BitWidth,

623 hash_combine_range(Arg.U.pVal, Arg.U.pVal + Arg.getNumWords()));

624}

625

626unsigned DenseMapInfo<APInt, void>::getHashValue(const APInt &Key) {

627 return static_cast<unsigned>(hash_value(Key));

628}

629

630 bool APInt::isSplat(unsigned SplatSizeInBits) const {

631 assert(getBitWidth() % SplatSizeInBits == 0 &&

632 "SplatSizeInBits must divide width!");

633 // We can check that all parts of an integer are equal by making use of a

634 // little trick: rotate and check if it's still the same value.

635 return *this == rotl(SplatSizeInBits);

636}

637

638/// This function returns the high "numBits" bits of this APInt.

639 APInt APInt::getHiBits(unsigned numBits) const {

640 return this->lshr(BitWidth - numBits);

641}

642

643/// This function returns the low "numBits" bits of this APInt.

644 APInt APInt::getLoBits(unsigned numBits) const {

645 APInt Result(getLowBitsSet(BitWidth, numBits));

646 Result &= *this;

647 return Result;

648}

649

650/// Return a value containing V broadcasted over NewLen bits.

651 APInt APInt::getSplat(unsigned NewLen, const APInt &V) {

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

664 uint64_t V = U.pVal[i];

665 if (V == 0)

666 Count += APINT_BITS_PER_WORD;

667 else {

668 Count += llvm::countl_zero(V);

669 break;

670 }

671 }

672 // Adjust for unused bits in the most significant word (they are zero).

673 unsigned Mod = BitWidth % APINT_BITS_PER_WORD;

674 Count -= Mod > 0 ? APINT_BITS_PER_WORD - Mod : 0;

675 return Count;

676}

677

678unsigned APInt::countLeadingOnesSlowCase() const {

679 unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD;

680 unsigned shift;

681 if (!highWordBits) {

682 highWordBits = APINT_BITS_PER_WORD;

683 shift = 0;

684 } else {

685 shift = APINT_BITS_PER_WORD - highWordBits;

686 }

687 int i = getNumWords() - 1;

688 unsigned Count = llvm::countl_one(U.pVal[i] << shift);

689 if (Count == highWordBits) {

690 for (i--; i >= 0; --i) {

691 if (U.pVal[i] == WORDTYPE_MAX)

692 Count += APINT_BITS_PER_WORD;

693 else {

694 Count += llvm::countl_one(U.pVal[i]);

695 break;

696 }

697 }

698 }

699 return Count;

700}

701

702unsigned APInt::countTrailingZerosSlowCase() const {

703 unsigned Count = 0;

704 unsigned i = 0;

705 for (; i < getNumWords() && U.pVal[i] == 0; ++i)

706 Count += APINT_BITS_PER_WORD;

707 if (i < getNumWords())

708 Count += llvm::countr_zero(U.pVal[i]);

709 return std::min(Count, BitWidth);

710}

711

712unsigned APInt::countTrailingOnesSlowCase() const {

713 unsigned Count = 0;

714 unsigned i = 0;

715 for (; i < getNumWords() && U.pVal[i] == WORDTYPE_MAX; ++i)

716 Count += APINT_BITS_PER_WORD;

717 if (i < getNumWords())

718 Count += llvm::countr_one(U.pVal[i]);

719 assert(Count <= BitWidth);

720 return Count;

721}

722

723unsigned APInt::countPopulationSlowCase() const {

724 unsigned Count = 0;

725 for (unsigned i = 0; i < getNumWords(); ++i)

726 Count += llvm::popcount(U.pVal[i]);

727 return Count;

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

746 APInt APInt::byteSwap() const {

747 assert(BitWidth >= 16 && BitWidth % 8 == 0 && "Cannot byteswap!");

748 if (BitWidth == 16)

749 return APInt(BitWidth, llvm::byteswap<uint16_t>(U.VAL));

750 if (BitWidth == 32)

751 return APInt(BitWidth, llvm::byteswap<uint32_t>(U.VAL));

752 if (BitWidth <= 64) {

753 uint64_t Tmp1 = llvm::byteswap<uint64_t>(U.VAL);

754 Tmp1 >>= (64 - BitWidth);

755 return APInt(BitWidth, Tmp1);

756 }

757

758 APInt Result(getNumWords() * APINT_BITS_PER_WORD, 0);

759 for (unsigned I = 0, N = getNumWords(); I != N; ++I)

760 Result.U.pVal[I] = llvm::byteswap<uint64_t>(U.pVal[N - I - 1]);

761 if (Result.BitWidth != BitWidth) {

762 Result.lshrInPlace(Result.BitWidth - BitWidth);

763 Result.BitWidth = BitWidth;

764 }

765 return Result;

766}

767

768 APInt APInt::reverseBits() const {

769 switch (BitWidth) {

770 case 64:

771 return APInt(BitWidth, llvm::reverseBits<uint64_t>(U.VAL));

772 case 32:

773 return APInt(BitWidth, llvm::reverseBits<uint32_t>(U.VAL));

774 case 16:

775 return APInt(BitWidth, llvm::reverseBits<uint16_t>(U.VAL));

776 case 8:

777 return APInt(BitWidth, llvm::reverseBits<uint8_t>(U.VAL));

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

788 for (; Val != 0; Val.lshrInPlace(1)) {

789 Reversed <<= 1;

790 Reversed |= Val[0];

791 --S;

792 }

793

794 Reversed <<= S;

795 return Reversed;

796}

797

798 APInt llvm::APIntOps::GreatestCommonDivisor(APInt A, APInt B) {

799 // Fast-path a common case.

800 if (A == B) return A;

801

802 // Corner cases: if either operand is zero, the other is the gcd.

803 if (!A) return B;

804 if (!B) return A;

805

806 // Count common powers of 2 and remove all other powers of 2.

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 // Both operands are odd multiples of 2^Pow_2:

823 //

824 // gcd(a, b) = gcd(|a - b| / 2^i, min(a, b))

825 //

826 // This is a modified version of Stein's algorithm, taking advantage of

827 // efficient countTrailingZeros().

828 while (A != B) {

829 if (A.ugt(B)) {

830 A -= B;

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

832 } else {

833 B -= A;

834 B.lshrInPlace(B.countr_zero() - Pow2);

835 }

836 }

837

838 return A;

839}

840

841 APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) {

842 uint64_t I = bit_cast<uint64_t>(Double);

843

844 // Get the sign bit from the highest order bit

845 bool isNeg = I >> 63;

846

847 // Get the 11-bit exponent and adjust for the 1023 bit bias

848 int64_t exp = ((I >> 52) & 0x7ff) - 1023;

849

850 // If the exponent is negative, the value is < 0 so just return 0.

851 if (exp < 0)

852 return APInt(width, 0u);

853

854 // Extract the mantissa by clearing the top 12 bits (sign + exponent).

855 uint64_t mantissa = (I & (~0ULL >> 12)) | 1ULL << 52;

856

857 // If the exponent doesn't shift all bits out of the mantissa

858 if (exp < 52)

859 return isNeg ? -APInt(width, mantissa >> (52 - exp)) :

860 APInt(width, mantissa >> (52 - exp));

861

862 // If the client didn't provide enough bits for us to shift the mantissa into

863 // then the result is undefined, just return 0

864 if (width <= exp - 52)

865 return APInt(width, 0);

866

867 // Otherwise, we have to shift the mantissa bits up to the right location

868 APInt Tmp(width, mantissa);

869 Tmp <<= (unsigned)exp - 52;

870 return isNeg ? -Tmp : Tmp;

871}

872

873/// This function converts this APInt to a double.

874/// The layout for double is as following (IEEE Standard 754):

875/// --------------------------------------

876/// | Sign Exponent Fraction Bias |

877/// |-------------------------------------- |

878/// | 1[63] 11[62-52] 52[51-00] 1023 |

879/// --------------------------------------

880 double APInt::roundToDouble(bool isSigned) const {

881 // Handle the simple case where the value is contained in one uint64_t.

882 // It is wrong to optimize getWord(0) to VAL; there might be more than one word.

883 if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {

884 if (isSigned) {

885 int64_t sext = SignExtend64(getWord(0), BitWidth);

886 return double(sext);

887 }

888 return double(getWord(0));

889 }

890

891 // Determine if the value is negative.

892 bool isNeg = isSigned ? (*this)[BitWidth-1] : false;

893

894 // Construct the absolute value if we're negative.

895 APInt Tmp(isNeg ? -(*this) : (*this));

896

897 // Figure out how many bits we're using.

898 unsigned n = Tmp.getActiveBits();

899

900 // The exponent (without bias normalization) is just the number of bits

901 // we are using. Note that the sign bit is gone since we constructed the

902 // absolute value.

903 uint64_t exp = n;

904

905 // Return infinity for exponent overflow

906 if (exp > 1023) {

907 if (!isSigned || !isNeg)

908 return std::numeric_limits<double>::infinity();

909 else

910 return -std::numeric_limits<double>::infinity();

911 }

912 exp += 1023; // Increment for 1023 bias

913

914 // Number of bits in mantissa is 52. To obtain the mantissa value, we must

915 // extract the high 52 bits from the correct words in pVal.

916 uint64_t mantissa;

917 unsigned hiWord = whichWord(n-1);

918 if (hiWord == 0) {

919 mantissa = Tmp.U.pVal[0];

920 if (n > 52)

921 mantissa >>= n - 52; // shift down, we want the top 52 bits.

922 } else {

923 assert(hiWord > 0 && "huh?");

924 uint64_t hibits = Tmp.U.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);

925 uint64_t lobits = Tmp.U.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);

926 mantissa = hibits | lobits;

927 }

928

929 // The leading bit of mantissa is implicit, so get rid of it.

930 uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;

931 uint64_t I = sign | (exp << 52) | mantissa;

932 return bit_cast<double>(I);

933}

934

935// Truncate to new width.

936 APInt APInt::trunc(unsigned width) const {

937 assert(width <= BitWidth && "Invalid APInt Truncate request");

938

939 if (width <= APINT_BITS_PER_WORD)

940 return APInt(width, getRawData()[0], /*isSigned=*/false,

941 /*implicitTrunc=*/true);

942

943 if (width == BitWidth)

944 return *this;

945

946 APInt Result(getMemory(getNumWords(width)), width);

947

948 // Copy full words.

949 unsigned i;

950 for (i = 0; i != width / APINT_BITS_PER_WORD; i++)

951 Result.U.pVal[i] = U.pVal[i];

952

953 // Truncate and copy any partial word.

954 unsigned bits = (0 - width) % APINT_BITS_PER_WORD;

955 if (bits != 0)

956 Result.U.pVal[i] = U.pVal[i] << bits >> bits;

957

958 return Result;

959}

960

961// Truncate to new width with unsigned saturation.

962 APInt APInt::truncUSat(unsigned width) const {

963 assert(width <= BitWidth && "Invalid APInt Truncate request");

964

965 // Can we just losslessly truncate it?

966 if (isIntN(width))

967 return trunc(width);

968 // If not, then just return the new limit.

969 return APInt::getMaxValue(width);

970}

971

972// Truncate to new width with signed saturation.

973 APInt APInt::truncSSat(unsigned width) const {

974 assert(width <= BitWidth && "Invalid APInt Truncate request");

975

976 // Can we just losslessly truncate it?

977 if (isSignedIntN(width))

978 return trunc(width);

979 // If not, then just return the new limits.

980 return isNegative() ? APInt::getSignedMinValue(width)

981 : APInt::getSignedMaxValue(width);

982}

983

984// Sign extend to a new width.

985 APInt APInt::sext(unsigned Width) const {

986 assert(Width >= BitWidth && "Invalid APInt SignExtend request");

987

988 if (Width <= APINT_BITS_PER_WORD)

989 return APInt(Width, SignExtend64(U.VAL, BitWidth), /*isSigned=*/true);

990

991 if (Width == BitWidth)

992 return *this;

993

994 APInt Result(getMemory(getNumWords(Width)), Width);

995

996 // Copy words.

997 std::memcpy(Result.U.pVal, getRawData(), getNumWords() * APINT_WORD_SIZE);

998

999 // Sign extend the last word since there may be unused bits in the input.

1000 Result.U.pVal[getNumWords() - 1] =

1001 SignExtend64(Result.U.pVal[getNumWords() - 1],

1002 ((BitWidth - 1) % APINT_BITS_PER_WORD) + 1);

1003

1004 // Fill with sign bits.

1005 std::memset(Result.U.pVal + getNumWords(), isNegative() ? -1 : 0,

1006 (Result.getNumWords() - getNumWords()) * APINT_WORD_SIZE);

1007 Result.clearUnusedBits();

1008 return Result;

1009}

1010

1011// Zero extend to a new width.

1012 APInt APInt::zext(unsigned width) const {

1013 assert(width >= BitWidth && "Invalid APInt ZeroExtend request");

1014

1015 if (width <= APINT_BITS_PER_WORD)

1016 return APInt(width, U.VAL);

1017

1018 if (width == BitWidth)

1019 return *this;

1020

1021 APInt Result(getMemory(getNumWords(width)), width);

1022

1023 // Copy words.

1024 std::memcpy(Result.U.pVal, getRawData(), getNumWords() * APINT_WORD_SIZE);

1025

1026 // Zero remaining words.

1027 std::memset(Result.U.pVal + getNumWords(), 0,

1028 (Result.getNumWords() - getNumWords()) * APINT_WORD_SIZE);

1029

1030 return Result;

1031}

1032

1033 APInt APInt::zextOrTrunc(unsigned width) const {

1034 if (BitWidth < width)

1035 return zext(width);

1036 if (BitWidth > width)

1037 return trunc(width);

1038 return *this;

1039}

1040

1041 APInt APInt::sextOrTrunc(unsigned width) const {

1042 if (BitWidth < width)

1043 return sext(width);

1044 if (BitWidth > width)

1045 return trunc(width);

1046 return *this;

1047}

1048

1049/// Arithmetic right-shift this APInt by shiftAmt.

1050/// Arithmetic right-shift function.

1051 void APInt::ashrInPlace(const APInt &shiftAmt) {

1052 ashrInPlace((unsigned)shiftAmt.getLimitedValue(BitWidth));

1053}

1054

1055/// Arithmetic right-shift this APInt by shiftAmt.

1056/// Arithmetic right-shift function.

1057void APInt::ashrSlowCase(unsigned ShiftAmt) {

1058 // Don't bother performing a no-op shift.

1059 if (!ShiftAmt)

1060 return;

1061

1062 // Save the original sign bit for later.

1063 bool Negative = isNegative();

1064

1065 // WordShift is the inter-part shift; BitShift is intra-part shift.

1066 unsigned WordShift = ShiftAmt / APINT_BITS_PER_WORD;

1067 unsigned BitShift = ShiftAmt % APINT_BITS_PER_WORD;

1068

1069 unsigned WordsToMove = getNumWords() - WordShift;

1070 if (WordsToMove != 0) {

1071 // Sign extend the last word to fill in the unused bits.

1072 U.pVal[getNumWords() - 1] = SignExtend64(

1073 U.pVal[getNumWords() - 1], ((BitWidth - 1) % APINT_BITS_PER_WORD) + 1);

1074

1075 // Fastpath for moving by whole words.

1076 if (BitShift == 0) {

1077 std::memmove(U.pVal, U.pVal + WordShift, WordsToMove * APINT_WORD_SIZE);

1078 } else {

1079 // Move the words containing significant bits.

1080 for (unsigned i = 0; i != WordsToMove - 1; ++i)

1081 U.pVal[i] = (U.pVal[i + WordShift] >> BitShift) |

1082 (U.pVal[i + WordShift + 1] << (APINT_BITS_PER_WORD - BitShift));

1083

1084 // Handle the last word which has no high bits to copy. Use an arithmetic

1085 // shift to preserve the sign bit.

1086 U.pVal[WordsToMove - 1] =

1087 (int64_t)U.pVal[WordShift + WordsToMove - 1] >> BitShift;

1088 }

1089 }

1090

1091 // Fill in the remainder based on the original sign.

1092 std::memset(U.pVal + WordsToMove, Negative ? -1 : 0,

1093 WordShift * APINT_WORD_SIZE);

1094 clearUnusedBits();

1095}

1096

1097/// Logical right-shift this APInt by shiftAmt.

1098/// Logical right-shift function.

1099 void APInt::lshrInPlace(const APInt &shiftAmt) {

1100 lshrInPlace((unsigned)shiftAmt.getLimitedValue(BitWidth));

1101}

1102

1103/// Logical right-shift this APInt by shiftAmt.

1104/// Logical right-shift function.

1105void APInt::lshrSlowCase(unsigned ShiftAmt) {

1106 tcShiftRight(U.pVal, getNumWords(), ShiftAmt);

1107}

1108

1109/// Left-shift this APInt by shiftAmt.

1110/// Left-shift function.

1111 APInt &APInt::operator<<=(const APInt &shiftAmt) {

1112 // It's undefined behavior in C to shift by BitWidth or greater.

1113 *this <<= (unsigned)shiftAmt.getLimitedValue(BitWidth);

1114 return *this;

1115}

1116

1117void APInt::shlSlowCase(unsigned ShiftAmt) {

1118 tcShiftLeft(U.pVal, getNumWords(), ShiftAmt);

1119 clearUnusedBits();

1120}

1121

1122// Calculate the rotate amount modulo the bit width.

1123 static unsigned rotateModulo(unsigned BitWidth, const APInt &rotateAmt) {

1124 if (LLVM_UNLIKELY(BitWidth == 0))

1125 return 0;

1126 unsigned rotBitWidth = rotateAmt.getBitWidth();

1127 APInt rot = rotateAmt;

1128 if (rotBitWidth < BitWidth) {

1129 // Extend the rotate APInt, so that the urem doesn't divide by 0.

1130 // e.g. APInt(1, 32) would give APInt(1, 0).

1131 rot = rotateAmt.zext(BitWidth);

1132 }

1133 rot = rot.urem(APInt(rot.getBitWidth(), BitWidth));

1134 return rot.getLimitedValue(BitWidth);

1135}

1136

1137 APInt APInt::rotl(const APInt &rotateAmt) const {

1138 return rotl(rotateModulo(BitWidth, rotateAmt));

1139}

1140

1141 APInt APInt::rotl(unsigned rotateAmt) const {

1142 if (LLVM_UNLIKELY(BitWidth == 0))

1143 return *this;

1144 rotateAmt %= BitWidth;

1145 if (rotateAmt == 0)

1146 return *this;

1147 return shl(rotateAmt) | lshr(BitWidth - rotateAmt);

1148}

1149

1150 APInt APInt::rotr(const APInt &rotateAmt) const {

1151 return rotr(rotateModulo(BitWidth, rotateAmt));

1152}

1153

1154 APInt APInt::rotr(unsigned rotateAmt) const {

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/// \returns the nearest log base 2 of this APInt. Ties round up.

1164///

1165/// NOTE: When we have a BitWidth of 1, we define:

1166///

1167/// log2(0) = UINT32_MAX

1168/// log2(1) = 0

1169///

1170/// to get around any mathematical concerns resulting from

1171/// referencing 2 in a space where 2 does no exist.

1172 unsigned APInt::nearestLogBase2() const {

1173 // Special case when we have a bitwidth of 1. If VAL is 1, then we

1174 // get 0. If VAL is 0, we get WORDTYPE_MAX which gets truncated to

1175 // UINT32_MAX.

1176 if (BitWidth == 1)

1177 return U.VAL - 1;

1178

1179 // Handle the zero case.

1180 if (isZero())

1181 return UINT32_MAX;

1182

1183 // The non-zero case is handled by computing:

1184 //

1185 // nearestLogBase2(x) = logBase2(x) + x[logBase2(x)-1].

1186 //

1187 // where x[i] is referring to the value of the ith bit of x.

1188 unsigned lg = logBase2();

1189 return lg + unsigned((*this)[lg - 1]);

1190}

1191

1192// Square Root - this method computes and returns the square root of "this".

1193// Three mechanisms are used for computation. For small values (<= 5 bits),

1194// a table lookup is done. This gets some performance for common cases. For

1195// values using less than 52 bits, the value is converted to double and then

1196// the libc sqrt function is called. The result is rounded and then converted

1197// back to a uint64_t which is then used to construct the result. Finally,

1198// the Babylonian method for computing square roots is used.

1199 APInt APInt::sqrt() const {

1200

1201 // Determine the magnitude of the value.

1202 unsigned magnitude = getActiveBits();

1203

1204 // Use a fast table for some small values. This also gets rid of some

1205 // rounding errors in libc sqrt for small values.

1206 if (magnitude <= 5) {

1207 static const uint8_t results[32] = {

1208 /* 0 */ 0,

1209 /* 1- 2 */ 1, 1,

1210 /* 3- 6 */ 2, 2, 2, 2,

1211 /* 7-12 */ 3, 3, 3, 3, 3, 3,

1212 /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,

1213 /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,

1214 /* 31 */ 6

1215 };

1216 return APInt(BitWidth, results[ (isSingleWord() ? U.VAL : U.pVal[0]) ]);

1217 }

1218

1219 // If the magnitude of the value fits in less than 52 bits (the precision of

1220 // an IEEE double precision floating point value), then we can use the

1221 // libc sqrt function which will probably use a hardware sqrt computation.

1222 // This should be faster than the algorithm below.

1223 if (magnitude < 52) {

1224 return APInt(BitWidth,

1225 uint64_t(::round(::sqrt(double(isSingleWord() ? U.VAL

1226 : U.pVal[0])))));

1227 }

1228

1229 // Okay, all the short cuts are exhausted. We must compute it. The following

1230 // is a classical Babylonian method for computing the square root. This code

1231 // was adapted to APInt from a wikipedia article on such computations.

1232 // See http://www.wikipedia.org/ and go to the page named

1233 // Calculate_an_integer_square_root.

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 // Select a good starting value using binary logarithms.

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 // Use the Babylonian method to arrive at the integer square root:

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 // Make sure we return the closest approximation

1256 // NOTE: The rounding calculation below is correct. It will produce an

1257 // off-by-one discrepancy with results from pari/gp. That discrepancy has been

1258 // determined to be a rounding issue with pari/gp as it begins to use a

1259 // floating point representation after 192 bits. There are no discrepancies

1260 // between this algorithm and pari/gp for bit widths < 192 bits.

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/// \returns the multiplicative inverse of an odd APInt modulo 2^BitWidth.

1274 APInt APInt::multiplicativeInverse() const {

1275 assert((*this)[0] &&

1276 "multiplicative inverse is only defined for odd numbers!");

1277

1278 // Use Newton's method.

1279 APInt Factor = *this;

1280 APInt T;

1281 while (!(T = *this * Factor).isOne())

1282 Factor *= 2 - std::move(T);

1283 return Factor;

1284}

1285

1286/// Implementation of Knuth's Algorithm D (Division of nonnegative integers)

1287/// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The

1288/// variables here have the same names as in the algorithm. Comments explain

1289/// the algorithm and any deviation from it.

1290 static void KnuthDiv(uint32_t *u, uint32_t *v, uint32_t *q, uint32_t* r,

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 // b denotes the base of the number system. In our case b is 2^32.

1299 const uint64_t b = uint64_t(1) << 32;

1300

1301// The DEBUG macros here tend to be spam in the debug output if you're not

1302// debugging this code. Disable them unless KNUTH_DEBUG is defined.

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

1310 DEBUG_KNUTH(dbgs() << "KnuthDiv: original:");

1311 DEBUG_KNUTH(for (int i = m + n; i >= 0; i--) dbgs() << " " << u[i]);

1312 DEBUG_KNUTH(dbgs() << " by");

1313 DEBUG_KNUTH(for (int i = n; i > 0; i--) dbgs() << " " << v[i - 1]);

1314 DEBUG_KNUTH(dbgs() << '\n');

1315 // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of

1316 // u and v by d. Note that we have taken Knuth's advice here to use a power

1317 // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of

1318 // 2 allows us to shift instead of multiply and it is easy to determine the

1319 // shift amount from the leading zeros. We are basically normalizing the u

1320 // and v so that its high bits are shifted to the top of v's range without

1321 // overflow. Note that this can require an extra word in u so that u must

1322 // be of length m+n+1.

1323 unsigned shift = llvm::countl_zero(v[n - 1]);

1324 uint32_t v_carry = 0;

1325 uint32_t u_carry = 0;

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

1340 DEBUG_KNUTH(dbgs() << "KnuthDiv: normal:");

1341 DEBUG_KNUTH(for (int i = m + n; i >= 0; i--) dbgs() << " " << u[i]);

1342 DEBUG_KNUTH(dbgs() << " by");

1343 DEBUG_KNUTH(for (int i = n; i > 0; i--) dbgs() << " " << v[i - 1]);

1344 DEBUG_KNUTH(dbgs() << '\n');

1345

1346 // D2. [Initialize j.] Set j to m. This is the loop counter over the places.

1347 int j = m;

1348 do {

1349 DEBUG_KNUTH(dbgs() << "KnuthDiv: quotient digit #" << j << '\n');

1350 // D3. [Calculate q'.].

1351 // Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')

1352 // Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')

1353 // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease

1354 // qp by 1, increase rp by v[n-1], and repeat this test if rp < b. The test

1355 // on v[n-2] determines at high speed most of the cases in which the trial

1356 // value qp is one too large, and it eliminates all cases where qp is two

1357 // too large.

1358 uint64_t dividend = Make_64(u[j+n], u[j+n-1]);

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 // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with

1371 // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation

1372 // consists of a simple multiplication by a one-place number, combined with

1373 // a subtraction.

1374 // The digits (u[j+n]...u[j]) should be kept positive; if the result of

1375 // this step is actually negative, (u[j+n]...u[j]) should be left as the

1376 // true value plus b**(n+1), namely as the b's complement of

1377 // the true value, and a "borrow" to the left should be remembered.

1378 int64_t borrow = 0;

1379 for (unsigned i = 0; i < n; ++i) {

1380 uint64_t p = qp * uint64_t(v[i]);

1381 int64_t subres = int64_t(u[j+i]) - borrow - Lo_32(p);

1382 u[j+i] = Lo_32(subres);

1383 borrow = Hi_32(p) - Hi_32(subres);

1384 DEBUG_KNUTH(dbgs() << "KnuthDiv: u[j+i] = " << u[j + i]

1385 << ", borrow = " << borrow << '\n');

1386 }

1387 bool isNeg = u[j+n] < borrow;

1388 u[j+n] -= Lo_32(borrow);

1389

1390 DEBUG_KNUTH(dbgs() << "KnuthDiv: after subtraction:");

1391 DEBUG_KNUTH(for (int i = m + n; i >= 0; i--) dbgs() << " " << u[i]);

1392 DEBUG_KNUTH(dbgs() << '\n');

1393

1394 // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was

1395 // negative, go to step D6; otherwise go on to step D7.

1396 q[j] = Lo_32(qp);

1397 if (isNeg) {

1398 // D6. [Add back]. The probability that this step is necessary is very

1399 // small, on the order of only 2/b. Make sure that test data accounts for

1400 // this possibility. Decrease q[j] by 1

1401 q[j]--;

1402 // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).

1403 // A carry will occur to the left of u[j+n], and it should be ignored

1404 // since it cancels with the borrow that occurred in D4.

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 }

1413 DEBUG_KNUTH(dbgs() << "KnuthDiv: after correction:");

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 // D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3.

1418 } while (--j >= 0);

1419

1420 DEBUG_KNUTH(dbgs() << "KnuthDiv: quotient:");

1421 DEBUG_KNUTH(for (int i = m; i >= 0; i--) dbgs() << " " << q[i]);

1422 DEBUG_KNUTH(dbgs() << '\n');

1423

1424 // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired

1425 // remainder may be obtained by dividing u[...] by d. If r is non-null we

1426 // compute the remainder (urem uses this).

1427 if (r) {

1428 // The value d is expressed by the "shift" value above since we avoided

1429 // multiplication by d by using a shift left. So, all we have to do is

1430 // shift right here.

1431 if (shift) {

1432 uint32_t carry = 0;

1433 DEBUG_KNUTH(dbgs() << "KnuthDiv: remainder:");

1434 for (int i = n-1; i >= 0; i--) {

1435 r[i] = (u[i] >> shift) | carry;

1436 carry = u[i] << (32 - shift);

1437 DEBUG_KNUTH(dbgs() << " " << r[i]);

1438 }

1439 } else {

1440 for (int i = n-1; i >= 0; i--) {

1441 r[i] = u[i];

1442 DEBUG_KNUTH(dbgs() << " " << r[i]);

1443 }

1444 }

1445 DEBUG_KNUTH(dbgs() << '\n');

1446 }

1447 DEBUG_KNUTH(dbgs() << '\n');

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 // First, compose the values into an array of 32-bit words instead of

1455 // 64-bit words. This is a necessity of both the "short division" algorithm

1456 // and the Knuth "classical algorithm" which requires there to be native

1457 // operations for +, -, and * on an m bit value with an m*2 bit result. We

1458 // can't use 64-bit operands here because we don't have native results of

1459 // 128-bits. Furthermore, casting the 64-bit values to 32-bit values won't

1460 // work on large-endian machines.

1461 unsigned n = rhsWords * 2;

1462 unsigned m = (lhsWords * 2) - n;

1463

1464 // Allocate space for the temporary values we need either on the stack, if

1465 // it will fit, or on the heap if it won't.

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 // Initialize the dividend

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; // this extra word is for "spill" in the Knuth algorithm.

1493

1494 // Initialize the divisor

1495 memset(V, 0, (n)*sizeof(uint32_t));

1496 for (unsigned i = 0; i < rhsWords; ++i) {

1497 uint64_t tmp = RHS[i];

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

1499 V[i * 2 + 1] = Hi_32(tmp);

1500 }

1501

1502 // initialize the quotient and remainder

1503 memset(Q, 0, (m+n) * sizeof(uint32_t));

1504 if (Remainder)

1505 memset(R, 0, n * sizeof(uint32_t));

1506

1507 // Now, adjust m and n for the Knuth division. n is the number of words in

1508 // the divisor. m is the number of words by which the dividend exceeds the

1509 // divisor (i.e. m+n is the length of the dividend). These sizes must not

1510 // contain any zero words or the Knuth algorithm fails.

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 // If we're left with only a single word for the divisor, Knuth doesn't work

1519 // so we implement the short division algorithm here. This is much simpler

1520 // and faster because we are certain that we can divide a 64-bit quantity

1521 // by a 32-bit quantity at hardware speed and short division is simply a

1522 // series of such operations. This is just like doing short division but we

1523 // are using base 2^32 instead of base 10.

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 // Now we're ready to invoke the Knuth classical divide algorithm. In this

1548 // case n > 1.

1549 KnuthDiv(U, V, Q, R, m, n);

1550 }

1551

1552 // If the caller wants the quotient

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 // If the caller wants the remainder

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 // Clean up the memory we allocated.

1565 if (U != &SPACE[0]) {

1566 delete [] U;

1567 delete [] V;

1568 delete [] Q;

1569 delete [] R;

1570 }

1571}

1572

1573 APInt APInt::udiv(const APInt &RHS) const {

1574 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");

1575

1576 // First, deal with the easy case

1577 if (isSingleWord()) {

1578 assert(RHS.U.VAL != 0 && "Divide by zero?");

1579 return APInt(BitWidth, U.VAL / RHS.U.VAL);

1580 }

1581

1582 // Get some facts about the LHS and RHS number of bits and words

1583 unsigned lhsWords = getNumWords(getActiveBits());

1584 unsigned rhsBits = RHS.getActiveBits();

1585 unsigned rhsWords = getNumWords(rhsBits);

1586 assert(rhsWords && "Divided by zero???");

1587

1588 // Deal with some degenerate cases

1589 if (!lhsWords)

1590 // 0 / X ===> 0

1591 return APInt(BitWidth, 0);

1592 if (rhsBits == 1)

1593 // X / 1 ===> X

1594 return *this;

1595 if (lhsWords < rhsWords || this->ult(RHS))

1596 // X / Y ===> 0, iff X < Y

1597 return APInt(BitWidth, 0);

1598 if (*this == RHS)

1599 // X / X ===> 1

1600 return APInt(BitWidth, 1);

1601 if (lhsWords == 1) // rhsWords is 1 if lhsWords is 1.

1602 // All high words are zero, just use native divide

1603 return APInt(BitWidth, this->U.pVal[0] / RHS.U.pVal[0]);

1604

1605 // We have to compute it the hard way. Invoke the Knuth divide algorithm.

1606 APInt Quotient(BitWidth, 0); // to hold result.

1607 divide(U.pVal, lhsWords, RHS.U.pVal, rhsWords, Quotient.U.pVal, nullptr);

1608 return Quotient;

1609}

1610

1611 APInt APInt::udiv(uint64_t RHS) const {

1612 assert(RHS != 0 && "Divide by zero?");

1613

1614 // First, deal with the easy case

1615 if (isSingleWord())

1616 return APInt(BitWidth, U.VAL / RHS);

1617

1618 // Get some facts about the LHS words.

1619 unsigned lhsWords = getNumWords(getActiveBits());

1620

1621 // Deal with some degenerate cases

1622 if (!lhsWords)

1623 // 0 / X ===> 0

1624 return APInt(BitWidth, 0);

1625 if (RHS == 1)

1626 // X / 1 ===> X

1627 return *this;

1628 if (this->ult(RHS))

1629 // X / Y ===> 0, iff X < Y

1630 return APInt(BitWidth, 0);

1631 if (*this == RHS)

1632 // X / X ===> 1

1633 return APInt(BitWidth, 1);

1634 if (lhsWords == 1) // rhsWords is 1 if lhsWords is 1.

1635 // All high words are zero, just use native divide

1636 return APInt(BitWidth, this->U.pVal[0] / RHS);

1637

1638 // We have to compute it the hard way. Invoke the Knuth divide algorithm.

1639 APInt Quotient(BitWidth, 0); // to hold result.

1640 divide(U.pVal, lhsWords, &RHS, 1, Quotient.U.pVal, nullptr);

1641 return Quotient;

1642}

1643

1644 APInt APInt::sdiv(const APInt &RHS) const {

1645 if (isNegative()) {

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

1655 APInt APInt::sdiv(int64_t RHS) const {

1656 if (isNegative()) {

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

1666 APInt APInt::urem(const APInt &RHS) const {

1667 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");

1668 if (isSingleWord()) {

1669 assert(RHS.U.VAL != 0 && "Remainder by zero?");

1670 return APInt(BitWidth, U.VAL % RHS.U.VAL);

1671 }

1672

1673 // Get some facts about the LHS

1674 unsigned lhsWords = getNumWords(getActiveBits());

1675

1676 // Get some facts about the RHS

1677 unsigned rhsBits = RHS.getActiveBits();

1678 unsigned rhsWords = getNumWords(rhsBits);

1679 assert(rhsWords && "Performing remainder operation by zero ???");

1680

1681 // Check the degenerate cases

1682 if (lhsWords == 0)

1683 // 0 % Y ===> 0

1684 return APInt(BitWidth, 0);

1685 if (rhsBits == 1)

1686 // X % 1 ===> 0

1687 return APInt(BitWidth, 0);

1688 if (lhsWords < rhsWords || this->ult(RHS))

1689 // X % Y ===> X, iff X < Y

1690 return *this;

1691 if (*this == RHS)

1692 // X % X == 0;

1693 return APInt(BitWidth, 0);

1694 if (lhsWords == 1)

1695 // All high words are zero, just use native remainder

1696 return APInt(BitWidth, U.pVal[0] % RHS.U.pVal[0]);

1697

1698 // We have to compute it the hard way. Invoke the Knuth divide algorithm.

1699 APInt Remainder(BitWidth, 0);

1700 divide(U.pVal, lhsWords, RHS.U.pVal, rhsWords, nullptr, Remainder.U.pVal);

1701 return Remainder;

1702}

1703

1704 uint64_t APInt::urem(uint64_t RHS) const {

1705 assert(RHS != 0 && "Remainder by zero?");

1706

1707 if (isSingleWord())

1708 return U.VAL % RHS;

1709

1710 // Get some facts about the LHS

1711 unsigned lhsWords = getNumWords(getActiveBits());

1712

1713 // Check the degenerate cases

1714 if (lhsWords == 0)

1715 // 0 % Y ===> 0

1716 return 0;

1717 if (RHS == 1)

1718 // X % 1 ===> 0

1719 return 0;

1720 if (this->ult(RHS))

1721 // X % Y ===> X, iff X < Y

1722 return getZExtValue();

1723 if (*this == RHS)

1724 // X % X == 0;

1725 return 0;

1726 if (lhsWords == 1)

1727 // All high words are zero, just use native remainder

1728 return U.pVal[0] % RHS;

1729

1730 // We have to compute it the hard way. Invoke the Knuth divide algorithm.

1731 uint64_t Remainder;

1732 divide(U.pVal, lhsWords, &RHS, 1, nullptr, &Remainder);

1733 return Remainder;

1734}

1735

1736 APInt APInt::srem(const APInt &RHS) const {

1737 if (isNegative()) {

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

1747 int64_t APInt::srem(int64_t RHS) const {

1748 if (isNegative()) {

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

1758 void APInt::udivrem(const APInt &LHS, const APInt &RHS,

1759 APInt &Quotient, APInt &Remainder) {

1760 assert(LHS.BitWidth == RHS.BitWidth && "Bit widths must be the same");

1761 unsigned BitWidth = LHS.BitWidth;

1762

1763 // First, deal with the easy case

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 // Get some size facts about the dividend and divisor

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 // Check the degenerate cases

1780 if (lhsWords == 0) {

1781 Quotient = APInt(BitWidth, 0); // 0 / Y ===> 0

1782 Remainder = APInt(BitWidth, 0); // 0 % Y ===> 0

1783 return;

1784 }

1785

1786 if (rhsBits == 1) {

1787 Quotient = LHS; // X / 1 ===> X

1788 Remainder = APInt(BitWidth, 0); // X % 1 ===> 0

1789 }

1790

1791 if (lhsWords < rhsWords || LHS.ult(RHS)) {

1792 Remainder = LHS; // X % Y ===> X, iff X < Y

1793 Quotient = APInt(BitWidth, 0); // X / Y ===> 0, iff X < Y

1794 return;

1795 }

1796

1797 if (LHS == RHS) {

1798 Quotient = APInt(BitWidth, 1); // X / X ===> 1

1799 Remainder = APInt(BitWidth, 0); // X % X ===> 0;

1800 return;

1801 }

1802

1803 // Make sure there is enough space to hold the results.

1804 // NOTE: This assumes that reallocate won't affect any bits if it doesn't

1805 // change the size. This is necessary if Quotient or Remainder is aliased

1806 // with LHS or RHS.

1807 Quotient.reallocate(BitWidth);

1808 Remainder.reallocate(BitWidth);

1809

1810 if (lhsWords == 1) { // rhsWords is 1 if lhsWords is 1.

1811 // There is only one word to consider so use the native versions.

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 // Okay, lets do it the long way

1820 divide(LHS.U.pVal, lhsWords, RHS.U.pVal, rhsWords, Quotient.U.pVal,

1821 Remainder.U.pVal);

1822 // Clear the rest of the Quotient and Remainder.

1823 std::memset(Quotient.U.pVal + lhsWords, 0,

1824 (getNumWords(BitWidth) - lhsWords) * APINT_WORD_SIZE);

1825 std::memset(Remainder.U.pVal + rhsWords, 0,

1826 (getNumWords(BitWidth) - rhsWords) * APINT_WORD_SIZE);

1827}

1828

1829 void APInt::udivrem(const APInt &LHS, uint64_t RHS, APInt &Quotient,

1830 uint64_t &Remainder) {

1831 assert(RHS != 0 && "Divide by zero?");

1832 unsigned BitWidth = LHS.BitWidth;

1833

1834 // First, deal with the easy case

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 // Get some size facts about the dividend and divisor

1843 unsigned lhsWords = getNumWords(LHS.getActiveBits());

1844

1845 // Check the degenerate cases

1846 if (lhsWords == 0) {

1847 Quotient = APInt(BitWidth, 0); // 0 / Y ===> 0

1848 Remainder = 0; // 0 % Y ===> 0

1849 return;

1850 }

1851

1852 if (RHS == 1) {

1853 Quotient = LHS; // X / 1 ===> X

1854 Remainder = 0; // X % 1 ===> 0

1855 return;

1856 }

1857

1858 if (LHS.ult(RHS)) {

1859 Remainder = LHS.getZExtValue(); // X % Y ===> X, iff X < Y

1860 Quotient = APInt(BitWidth, 0); // X / Y ===> 0, iff X < Y

1861 return;

1862 }

1863

1864 if (LHS == RHS) {

1865 Quotient = APInt(BitWidth, 1); // X / X ===> 1

1866 Remainder = 0; // X % X ===> 0;

1867 return;

1868 }

1869

1870 // Make sure there is enough space to hold the results.

1871 // NOTE: This assumes that reallocate won't affect any bits if it doesn't

1872 // change the size. This is necessary if Quotient is aliased with LHS.

1873 Quotient.reallocate(BitWidth);

1874

1875 if (lhsWords == 1) { // rhsWords is 1 if lhsWords is 1.

1876 // There is only one word to consider so use the native versions.

1877 uint64_t lhsValue = LHS.U.pVal[0];

1878 Quotient = lhsValue / RHS;

1879 Remainder = lhsValue % RHS;

1880 return;

1881 }

1882

1883 // Okay, lets do it the long way

1884 divide(LHS.U.pVal, lhsWords, &RHS, 1, Quotient.U.pVal, &Remainder);

1885 // Clear the rest of the Quotient.

1886 std::memset(Quotient.U.pVal + lhsWords, 0,

1887 (getNumWords(BitWidth) - lhsWords) * APINT_WORD_SIZE);

1888}

1889

1890 void APInt::sdivrem(const APInt &LHS, const APInt &RHS,

1891 APInt &Quotient, APInt &Remainder) {

1892 if (LHS.isNegative()) {

1893 if (RHS.isNegative())

1894 APInt::udivrem(-LHS, -RHS, Quotient, Remainder);

1895 else {

1896 APInt::udivrem(-LHS, RHS, Quotient, Remainder);

1897 Quotient.negate();

1898 }

1899 Remainder.negate();

1900 } else if (RHS.isNegative()) {

1901 APInt::udivrem(LHS, -RHS, Quotient, Remainder);

1902 Quotient.negate();

1903 } else {

1904 APInt::udivrem(LHS, RHS, Quotient, Remainder);

1905 }

1906}

1907

1908 void APInt::sdivrem(const APInt &LHS, int64_t RHS,

1909 APInt &Quotient, int64_t &Remainder) {

1910 uint64_t R = Remainder;

1911 if (LHS.isNegative()) {

1912 if (RHS < 0)

1913 APInt::udivrem(-LHS, -RHS, Quotient, R);

1914 else {

1915 APInt::udivrem(-LHS, RHS, Quotient, R);

1916 Quotient.negate();

1917 }

1918 R = -R;

1919 } else if (RHS < 0) {

1920 APInt::udivrem(LHS, -RHS, Quotient, R);

1921 Quotient.negate();

1922 } else {

1923 APInt::udivrem(LHS, RHS, Quotient, R);

1924 }

1925 Remainder = R;

1926}

1927

1928 APInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const {

1929 APInt Res = *this+RHS;

1930 Overflow = isNonNegative() == RHS.isNonNegative() &&

1931 Res.isNonNegative() != isNonNegative();

1932 return Res;

1933}

1934

1935 APInt APInt::uadd_ov(const APInt &RHS, bool &Overflow) const {

1936 APInt Res = *this+RHS;

1937 Overflow = Res.ult(RHS);

1938 return Res;

1939}

1940

1941 APInt APInt::ssub_ov(const APInt &RHS, bool &Overflow) const {

1942 APInt Res = *this - RHS;

1943 Overflow = isNonNegative() != RHS.isNonNegative() &&

1944 Res.isNonNegative() != isNonNegative();

1945 return Res;

1946}

1947

1948 APInt APInt::usub_ov(const APInt &RHS, bool &Overflow) const {

1949 APInt Res = *this-RHS;

1950 Overflow = Res.ugt(*this);

1951 return Res;

1952}

1953

1954 APInt APInt::sdiv_ov(const APInt &RHS, bool &Overflow) const {

1955 // MININT/-1 --> overflow.

1956 Overflow = isMinSignedValue() && RHS.isAllOnes();

1957 return sdiv(RHS);

1958}

1959

1960 APInt APInt::smul_ov(const APInt &RHS, bool &Overflow) const {

1961 APInt Res = *this * RHS;

1962

1963 if (RHS != 0)

1964 Overflow = Res.sdiv(RHS) != *this ||

1965 (isMinSignedValue() && RHS.isAllOnes());

1966 else

1967 Overflow = false;

1968 return Res;

1969}

1970

1971 APInt APInt::umul_ov(const APInt &RHS, bool &Overflow) const {

1972 if (countl_zero() + RHS.countl_zero() + 2 <= BitWidth) {

1973 Overflow = true;

1974 return *this * RHS;

1975 }

1976

1977 APInt Res = lshr(1) * RHS;

1978 Overflow = Res.isNegative();

1979 Res <<= 1;

1980 if ((*this)[0]) {

1981 Res += RHS;

1982 if (Res.ult(RHS))

1983 Overflow = true;

1984 }

1985 return Res;

1986}

1987

1988 APInt APInt::sshl_ov(const APInt &ShAmt, bool &Overflow) const {

1989 return sshl_ov(ShAmt.getLimitedValue(getBitWidth()), Overflow);

1990}

1991

1992 APInt APInt::sshl_ov(unsigned ShAmt, bool &Overflow) const {

1993 Overflow = ShAmt >= getBitWidth();

1994 if (Overflow)

1995 return APInt(BitWidth, 0);

1996

1997 if (isNonNegative()) // Don't allow sign change.

1998 Overflow = ShAmt >= countl_zero();

1999 else

2000 Overflow = ShAmt >= countl_one();

2001

2002 return *this << ShAmt;

2003}

2004

2005 APInt APInt::ushl_ov(const APInt &ShAmt, bool &Overflow) const {

2006 return ushl_ov(ShAmt.getLimitedValue(getBitWidth()), Overflow);

2007}

2008

2009 APInt APInt::ushl_ov(unsigned ShAmt, bool &Overflow) const {

2010 Overflow = ShAmt >= getBitWidth();

2011 if (Overflow)

2012 return APInt(BitWidth, 0);

2013

2014 Overflow = ShAmt > countl_zero();

2015

2016 return *this << ShAmt;

2017}

2018

2019 APInt APInt::sfloordiv_ov(const APInt &RHS, bool &Overflow) const {

2020 APInt quotient = sdiv_ov(RHS, Overflow);

2021 if ((quotient * RHS != *this) && (isNegative() != RHS.isNegative()))

2022 return quotient - 1;

2023 return quotient;

2024}

2025

2026 APInt APInt::sadd_sat(const APInt &RHS) const {

2027 bool Overflow;

2028 APInt Res = sadd_ov(RHS, Overflow);

2029 if (!Overflow)

2030 return Res;

2031

2032 return isNegative() ? APInt::getSignedMinValue(BitWidth)

2033 : APInt::getSignedMaxValue(BitWidth);

2034}

2035

2036 APInt APInt::uadd_sat(const APInt &RHS) const {

2037 bool Overflow;

2038 APInt Res = uadd_ov(RHS, Overflow);

2039 if (!Overflow)

2040 return Res;

2041

2042 return APInt::getMaxValue(BitWidth);

2043}

2044

2045 APInt APInt::ssub_sat(const APInt &RHS) const {

2046 bool Overflow;

2047 APInt Res = ssub_ov(RHS, Overflow);

2048 if (!Overflow)

2049 return Res;

2050

2051 return isNegative() ? APInt::getSignedMinValue(BitWidth)

2052 : APInt::getSignedMaxValue(BitWidth);

2053}

2054

2055 APInt APInt::usub_sat(const APInt &RHS) const {

2056 bool Overflow;

2057 APInt Res = usub_ov(RHS, Overflow);

2058 if (!Overflow)

2059 return Res;

2060

2061 return APInt(BitWidth, 0);

2062}

2063

2064 APInt APInt::smul_sat(const APInt &RHS) const {

2065 bool Overflow;

2066 APInt Res = smul_ov(RHS, Overflow);

2067 if (!Overflow)

2068 return Res;

2069

2070 // The result is negative if one and only one of inputs is negative.

2071 bool ResIsNegative = isNegative() ^ RHS.isNegative();

2072

2073 return ResIsNegative ? APInt::getSignedMinValue(BitWidth)

2074 : APInt::getSignedMaxValue(BitWidth);

2075}

2076

2077 APInt APInt::umul_sat(const APInt &RHS) const {

2078 bool Overflow;

2079 APInt Res = umul_ov(RHS, Overflow);

2080 if (!Overflow)

2081 return Res;

2082

2083 return APInt::getMaxValue(BitWidth);

2084}

2085

2086 APInt APInt::sshl_sat(const APInt &RHS) const {

2087 return sshl_sat(RHS.getLimitedValue(getBitWidth()));

2088}

2089

2090 APInt APInt::sshl_sat(unsigned RHS) const {

2091 bool Overflow;

2092 APInt Res = sshl_ov(RHS, Overflow);

2093 if (!Overflow)

2094 return Res;

2095

2096 return isNegative() ? APInt::getSignedMinValue(BitWidth)

2097 : APInt::getSignedMaxValue(BitWidth);

2098}

2099

2100 APInt APInt::ushl_sat(const APInt &RHS) const {

2101 return ushl_sat(RHS.getLimitedValue(getBitWidth()));

2102}

2103

2104 APInt APInt::ushl_sat(unsigned RHS) const {

2105 bool Overflow;

2106 APInt Res = ushl_ov(RHS, Overflow);

2107 if (!Overflow)

2108 return Res;

2109

2110 return APInt::getMaxValue(BitWidth);

2111}

2112

2113void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) {

2114 // Check our assumptions here

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

2120 StringRef::iterator p = str.begin();

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 // Allocate memory if needed

2135 if (isSingleWord())

2136 U.VAL = 0;

2137 else

2138 U.pVal = getClearedMemory(getNumWords());

2139

2140 // Figure out if we can shift instead of multiply

2141 unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);

2142

2143 // Enter digit traversal loop

2144 for (StringRef::iterator e = str.end(); p != e; ++p) {

2145 unsigned digit = getDigit(*p, radix);

2146 assert(digit < radix && "Invalid character in digit string");

2147

2148 // Shift or multiply the value by the radix

2149 if (slen > 1) {

2150 if (shift)

2151 *this <<= shift;

2152 else

2153 *this *= radix;

2154 }

2155

2156 // Add in the digit we just interpreted

2157 *this += digit;

2158 }

2159 // If its negative, put it in two's complement form

2160 if (isNeg)

2161 this->negate();

2162}

2163

2164 void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix, bool Signed,

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 // Binary literals are a non-standard extension added in gcc 4.3:

2176 // http://gcc.gnu.org/onlinedocs/gcc-4.3.0/gcc/Binary-constants.html

2177 Prefix = "0b";

2178 break;

2179 case 8:

2180 Prefix = "0";

2181 break;

2182 case 10:

2183 break; // No prefix

2184 case 16:

2185 Prefix = "0x";

2186 break;

2187 default:

2188 llvm_unreachable("Invalid radix!");

2189 }

2190 }

2191

2192 // Number of digits in a group between separators.

2193 unsigned Grouping = (Radix == 8 || Radix == 10) ? 3 : 4;

2194

2195 // First, check for a zero value and just short circuit the logic below.

2196 if (isZero()) {

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

2209 if (isSingleWord()) {

2210 char Buffer[65];

2211 char *BufPtr = std::end(Buffer);

2212

2213 uint64_t N;

2214 if (!Signed) {

2215 N = getZExtValue();

2216 } else {

2217 int64_t I = getSExtValue();

2218 if (I >= 0) {

2219 N = I;

2220 } else {

2221 Str.push_back('-');

2222 N = -(uint64_t)I;

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

2245 if (Signed && isNegative()) {

2246 // They want to print the signed version and it is a negative value

2247 // Flip the bits and add one to turn it into the equivalent positive

2248 // value and put a '-' in the result.

2249 Tmp.negate();

2250 Str.push_back('-');

2251 }

2252

2253 while (*Prefix) {

2254 Str.push_back(*Prefix);

2255 ++Prefix;

2256 }

2257

2258 // We insert the digits backward, then reverse them to get the right order.

2259 unsigned StartDig = Str.size();

2260

2261 // For the 2, 8 and 16 bit cases, we can just shift instead of divide

2262 // because the number of bits per digit (1, 3 and 4 respectively) divides

2263 // equally. We just shift until the value is zero.

2264 if (Radix == 2 || Radix == 8 || Radix == 16) {

2265 // Just shift tmp right for each digit width until it becomes zero

2266 unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));

2267 unsigned MaskAmt = Radix - 1;

2268

2269 int Pos = 0;

2270 while (Tmp.getBoolValue()) {

2271 unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;

2272 if (InsertSeparators && Pos % Grouping == 0 && Pos > 0)

2273 Str.push_back('\'');

2274

2275 Str.push_back(Digits[Digit]);

2276 Tmp.lshrInPlace(ShiftAmt);

2277 Pos++;

2278 }

2279 } else {

2280 int Pos = 0;

2281 while (Tmp.getBoolValue()) {

2282 uint64_t Digit;

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 // Reverse the digits before returning.

2294 std::reverse(Str.begin()+StartDig, Str.end());

2295}

2296

2297#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

2298 LLVM_DUMP_METHOD void APInt::dump() const {

2299 SmallString<40> S, U;

2300 this->toStringUnsigned(U);

2301 this->toStringSigned(S);

2302 dbgs() << "APInt(" << BitWidth << "b, "

2303 << U << "u " << S << "s)\n";

2304}

2305#endif

2306

2307 void APInt::print(raw_ostream &OS, bool isSigned) const {

2308 SmallString<40> S;

2309 this->toString(S, 10, isSigned, /* formatAsCLiteral = */false);

2310 OS << S;

2311}

2312

2313// This implements a variety of operations on a representation of

2314// arbitrary precision, two's-complement, bignum integer values.

2315

2316// Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe

2317// and unrestricting assumption.

2318static_assert(APInt::APINT_BITS_PER_WORD % 2 == 0,

2319 "Part width must be divisible by 2!");

2320

2321// Returns the integer part with the least significant BITS set.

2322// BITS cannot be zero.

2323 static inline APInt::WordType lowBitMask(unsigned bits) {

2324 assert(bits != 0 && bits <= APInt::APINT_BITS_PER_WORD);

2325 return ~(APInt::WordType) 0 >> (APInt::APINT_BITS_PER_WORD - bits);

2326}

2327

2328/// Returns the value of the lower half of PART.

2329 static inline APInt::WordType lowHalf(APInt::WordType part) {

2330 return part & lowBitMask(APInt::APINT_BITS_PER_WORD / 2);

2331}

2332

2333/// Returns the value of the upper half of PART.

2334 static inline APInt::WordType highHalf(APInt::WordType part) {

2335 return part >> (APInt::APINT_BITS_PER_WORD / 2);

2336}

2337

2338/// Sets the least significant part of a bignum to the input value, and zeroes

2339/// out higher parts.

2340 void APInt::tcSet(WordType *dst, WordType part, unsigned parts) {

2341 assert(parts > 0);

2342 dst[0] = part;

2343 for (unsigned i = 1; i < parts; i++)

2344 dst[i] = 0;

2345}

2346

2347/// Assign one bignum to another.

2348 void APInt::tcAssign(WordType *dst, const WordType *src, unsigned parts) {

2349 for (unsigned i = 0; i < parts; i++)

2350 dst[i] = src[i];

2351}

2352

2353/// Returns true if a bignum is zero, false otherwise.

2354 bool APInt::tcIsZero(const WordType *src, unsigned parts) {

2355 for (unsigned i = 0; i < parts; i++)

2356 if (src[i])

2357 return false;

2358

2359 return true;

2360}

2361

2362/// Extract the given bit of a bignum; returns 0 or 1.

2363 int APInt::tcExtractBit(const WordType *parts, unsigned bit) {

2364 return (parts[whichWord(bit)] & maskBit(bit)) != 0;

2365}

2366

2367/// Set the given bit of a bignum.

2368 void APInt::tcSetBit(WordType *parts, unsigned bit) {

2369 parts[whichWord(bit)] |= maskBit(bit);

2370}

2371

2372/// Clears the given bit of a bignum.

2373 void APInt::tcClearBit(WordType *parts, unsigned bit) {

2374 parts[whichWord(bit)] &= ~maskBit(bit);

2375}

2376

2377/// Returns the bit number of the least significant set bit of a number. If the

2378/// input number has no bits set UINT_MAX is returned.

2379 unsigned APInt::tcLSB(const WordType *parts, unsigned n) {

2380 for (unsigned i = 0; i < n; i++) {

2381 if (parts[i] != 0) {

2382 unsigned lsb = llvm::countr_zero(parts[i]);

2383 return lsb + i * APINT_BITS_PER_WORD;

2384 }

2385 }

2386

2387 return UINT_MAX;

2388}

2389

2390/// Returns the bit number of the most significant set bit of a number.

2391/// If the input number has no bits set UINT_MAX is returned.

2392 unsigned APInt::tcMSB(const WordType *parts, unsigned n) {

2393 do {

2394 --n;

2395

2396 if (parts[n] != 0) {

2397 static_assert(sizeof(parts[n]) <= sizeof(uint64_t));

2398 unsigned msb = llvm::Log2_64(parts[n]);

2399

2400 return msb + n * APINT_BITS_PER_WORD;

2401 }

2402 } while (n);

2403

2404 return UINT_MAX;

2405}

2406

2407/// Copy the bit vector of width srcBITS from SRC, starting at bit srcLSB, to

2408/// DST, of dstCOUNT parts, such that the bit srcLSB becomes the least

2409/// significant bit of DST. All high bits above srcBITS in DST are zero-filled.

2410/// */

2411void

2412 APInt::tcExtract(WordType *dst, unsigned dstCount, const WordType *src,

2413 unsigned srcBits, unsigned srcLSB) {

2414 unsigned dstParts = (srcBits + APINT_BITS_PER_WORD - 1) / APINT_BITS_PER_WORD;

2415 assert(dstParts <= dstCount);

2416

2417 unsigned firstSrcPart = srcLSB / APINT_BITS_PER_WORD;

2418 tcAssign(dst, src + firstSrcPart, dstParts);

2419

2420 unsigned shift = srcLSB % APINT_BITS_PER_WORD;

2421 tcShiftRight(dst, dstParts, shift);

2422

2423 // We now have (dstParts * APINT_BITS_PER_WORD - shift) bits from SRC

2424 // in DST. If this is less that srcBits, append the rest, else

2425 // clear the high bits.

2426 unsigned n = dstParts * APINT_BITS_PER_WORD - shift;

2427 if (n < srcBits) {

2428 WordType mask = lowBitMask (srcBits - n);

2429 dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)

2430 << n % APINT_BITS_PER_WORD);

2431 } else if (n > srcBits) {

2432 if (srcBits % APINT_BITS_PER_WORD)

2433 dst[dstParts - 1] &= lowBitMask (srcBits % APINT_BITS_PER_WORD);

2434 }

2435

2436 // Clear high parts.

2437 while (dstParts < dstCount)

2438 dst[dstParts++] = 0;

2439}

2440

2441//// DST += RHS + C where C is zero or one. Returns the carry flag.

2442 APInt::WordType APInt::tcAdd(WordType *dst, const WordType *rhs,

2443 WordType c, unsigned parts) {

2444 assert(c <= 1);

2445

2446 for (unsigned i = 0; i < parts; i++) {

2447 WordType l = dst[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/// This function adds a single "word" integer, src, to the multiple

2461/// "word" integer array, dst[]. dst[] is modified to reflect the addition and

2462/// 1 is returned if there is a carry out, otherwise 0 is returned.

2463/// @returns the carry of the addition.

2464 APInt::WordType APInt::tcAddPart(WordType *dst, WordType src,

2465 unsigned parts) {

2466 for (unsigned i = 0; i < parts; ++i) {

2467 dst[i] += src;

2468 if (dst[i] >= src)

2469 return 0; // No need to carry so exit early.

2470 src = 1; // Carry one to next digit.

2471 }

2472

2473 return 1;

2474}

2475

2476/// DST -= RHS + C where C is zero or one. Returns the carry flag.

2477 APInt::WordType APInt::tcSubtract(WordType *dst, const WordType *rhs,

2478 WordType c, unsigned parts) {

2479 assert(c <= 1);

2480

2481 for (unsigned i = 0; i < parts; i++) {

2482 WordType l = dst[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/// This function subtracts a single "word" (64-bit word), src, from

2496/// the multi-word integer array, dst[], propagating the borrowed 1 value until

2497/// no further borrowing is needed or it runs out of "words" in dst. The result

2498/// is 1 if "borrowing" exhausted the digits in dst, or 0 if dst was not

2499/// exhausted. In other words, if src > dst then this function returns 1,

2500/// otherwise 0.

2501/// @returns the borrow out of the subtraction

2502 APInt::WordType APInt::tcSubtractPart(WordType *dst, WordType src,

2503 unsigned parts) {

2504 for (unsigned i = 0; i < parts; ++i) {

2505 WordType Dst = dst[i];

2506 dst[i] -= src;

2507 if (src <= Dst)

2508 return 0; // No need to borrow so exit early.

2509 src = 1; // We have to "borrow 1" from next "word"

2510 }

2511

2512 return 1;

2513}

2514

2515/// Negate a bignum in-place.

2516 void APInt::tcNegate(WordType *dst, unsigned parts) {

2517 tcComplement(dst, parts);

2518 tcIncrement(dst, parts);

2519}

2520

2521/// DST += SRC * MULTIPLIER + CARRY if add is true

2522/// DST = SRC * MULTIPLIER + CARRY if add is false

2523/// Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC

2524/// they must start at the same point, i.e. DST == SRC.

2525/// If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is

2526/// returned. Otherwise DST is filled with the least significant

2527/// DSTPARTS parts of the result, and if all of the omitted higher

2528/// parts were zero return zero, otherwise overflow occurred and

2529/// return one.

2530 int APInt::tcMultiplyPart(WordType *dst, const WordType *src,

2531 WordType multiplier, WordType carry,

2532 unsigned srcParts, unsigned dstParts,

2533 bool add) {

2534 // Otherwise our writes of DST kill our later reads of SRC.

2535 assert(dst <= src || dst >= src + srcParts);

2536 assert(dstParts <= srcParts + 1);

2537

2538 // N loops; minimum of dstParts and srcParts.

2539 unsigned n = std::min(dstParts, srcParts);

2540

2541 for (unsigned i = 0; i < n; i++) {

2542 // [LOW, HIGH] = MULTIPLIER * SRC[i] + DST[i] + CARRY.

2543 // This cannot overflow, because:

2544 // (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)

2545 // which is less than n^2.

2546 WordType srcPart = src[i];

2547 WordType low, mid, high;

2548 if (multiplier == 0 || srcPart == 0) {

2549 low = carry;

2550 high = 0;

2551 } else {

2552 low = lowHalf(srcPart) * lowHalf(multiplier);

2553 high = highHalf(srcPart) * highHalf(multiplier);

2554

2555 mid = lowHalf(srcPart) * highHalf(multiplier);

2556 high += highHalf(mid);

2557 mid <<= APINT_BITS_PER_WORD / 2;

2558 if (low + mid < low)

2559 high++;

2560 low += mid;

2561

2562 mid = highHalf(srcPart) * lowHalf(multiplier);

2563 high += highHalf(mid);

2564 mid <<= APINT_BITS_PER_WORD / 2;

2565 if (low + mid < low)

2566 high++;

2567 low += mid;

2568

2569 // Now add carry.

2570 if (low + carry < low)

2571 high++;

2572 low += carry;

2573 }

2574

2575 if (add) {

2576 // And now DST[i], and store the new low part there.

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 // Full multiplication, there is no overflow.

2589 assert(srcParts + 1 == dstParts);

2590 dst[srcParts] = carry;

2591 return 0;

2592 }

2593

2594 // We overflowed if there is carry.

2595 if (carry)

2596 return 1;

2597

2598 // We would overflow if any significant unwritten parts would be

2599 // non-zero. This is true if any remaining src parts are non-zero

2600 // and the multiplier is non-zero.

2601 if (multiplier)

2602 for (unsigned i = dstParts; i < srcParts; i++)

2603 if (src[i])

2604 return 1;

2605

2606 // We fitted in the narrow destination.

2607 return 0;

2608}

2609

2610/// DST = LHS * RHS, where DST has the same width as the operands and

2611/// is filled with the least significant parts of the result. Returns

2612/// one if overflow occurred, otherwise zero. DST must be disjoint

2613/// from both operands.

2614 int APInt::tcMultiply(WordType *dst, const WordType *lhs,

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 // Don't accumulate on the first iteration so we don't need to initalize

2622 // dst to 0.

2623 overflow |=

2624 tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts, parts - i, i != 0);

2625 }

2626

2627 return overflow;

2628}

2629

2630/// DST = LHS * RHS, where DST has width the sum of the widths of the

2631/// operands. No overflow occurs. DST must be disjoint from both operands.

2632 void APInt::tcFullMultiply(WordType *dst, const WordType *lhs,

2633 const WordType *rhs, unsigned lhsParts,

2634 unsigned rhsParts) {

2635 // Put the narrower number on the LHS for less loops below.

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 // Don't accumulate on the first iteration so we don't need to initalize

2643 // dst to 0.

2644 tcMultiplyPart(&dst[i], rhs, lhs[i], 0, rhsParts, rhsParts + 1, i != 0);

2645 }

2646}

2647

2648// If RHS is zero LHS and REMAINDER are left unchanged, return one.

2649// Otherwise set LHS to LHS / RHS with the fractional part discarded,

2650// set REMAINDER to the remainder, return zero. i.e.

2651//

2652// OLD_LHS = RHS * LHS + REMAINDER

2653//

2654// SCRATCH is a bignum of the same size as the operands and result for

2655// use by the routine; its contents need not be initialized and are

2656// destroyed. LHS, REMAINDER and SCRATCH must be distinct.

2657 int APInt::tcDivide(WordType *lhs, const WordType *rhs,

2658 WordType *remainder, WordType *srhs,

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

2666 shiftCount = parts * APINT_BITS_PER_WORD - shiftCount;

2667 unsigned n = shiftCount / APINT_BITS_PER_WORD;

2668 WordType mask = (WordType) 1 << (shiftCount % APINT_BITS_PER_WORD);

2669

2670 tcAssign(srhs, rhs, parts);

2671 tcShiftLeft(srhs, parts, shiftCount);

2672 tcAssign(remainder, lhs, parts);

2673 tcSet(lhs, 0, parts);

2674

2675 // Loop, subtracting SRHS if REMAINDER is greater and adding that to the

2676 // total.

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

2687 tcShiftRight(srhs, parts, 1);

2688 if ((mask >>= 1) == 0) {

2689 mask = (WordType) 1 << (APINT_BITS_PER_WORD - 1);

2690 n--;

2691 }

2692 }

2693

2694 return false;

2695}

2696

2697/// Shift a bignum left Count bits in-place. Shifted in bits are zero. There are

2698/// no restrictions on Count.

2699 void APInt::tcShiftLeft(WordType *Dst, unsigned Words, unsigned Count) {

2700 // Don't bother performing a no-op shift.

2701 if (!Count)

2702 return;

2703

2704 // WordShift is the inter-part shift; BitShift is the intra-part shift.

2705 unsigned WordShift = std::min(Count / APINT_BITS_PER_WORD, Words);

2706 unsigned BitShift = Count % APINT_BITS_PER_WORD;

2707

2708 // Fastpath for moving by whole words.

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] |=

2716 Dst[Words - WordShift - 1] >> (APINT_BITS_PER_WORD - BitShift);

2717 }

2718 }

2719

2720 // Fill in the remainder with 0s.

2721 std::memset(Dst, 0, WordShift * APINT_WORD_SIZE);

2722}

2723

2724/// Shift a bignum right Count bits in-place. Shifted in bits are zero. There

2725/// are no restrictions on Count.

2726 void APInt::tcShiftRight(WordType *Dst, unsigned Words, unsigned Count) {

2727 // Don't bother performing a no-op shift.

2728 if (!Count)

2729 return;

2730

2731 // WordShift is the inter-part shift; BitShift is the intra-part shift.

2732 unsigned WordShift = std::min(Count / APINT_BITS_PER_WORD, Words);

2733 unsigned BitShift = Count % APINT_BITS_PER_WORD;

2734

2735 unsigned WordsToMove = Words - WordShift;

2736 // Fastpath for moving by whole words.

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)

2743 Dst[i] |= Dst[i + WordShift + 1] << (APINT_BITS_PER_WORD - BitShift);

2744 }

2745 }

2746

2747 // Fill in the remainder with 0s.

2748 std::memset(Dst + WordsToMove, 0, WordShift * APINT_WORD_SIZE);

2749}

2750

2751// Comparison (unsigned) of two bignums.

2752 int APInt::tcCompare(const WordType *lhs, const WordType *rhs,

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

2763 APInt llvm::APIntOps::RoundingUDiv(const APInt &A, const APInt &B,

2764 APInt::Rounding RM) {

2765 // Currently udivrem always rounds down.

2766 switch (RM) {

2767 case APInt::Rounding::DOWN:

2768 case APInt::Rounding::TOWARD_ZERO:

2769 return A.udiv(B);

2770 case APInt::Rounding::UP: {

2771 APInt Quo, Rem;

2772 APInt::udivrem(A, B, Quo, Rem);

2773 if (Rem.isZero())

2774 return Quo;

2775 return Quo + 1;

2776 }

2777 }

2778 llvm_unreachable("Unknown APInt::Rounding enum");

2779}

2780

2781 APInt llvm::APIntOps::RoundingSDiv(const APInt &A, const APInt &B,

2782 APInt::Rounding RM) {

2783 switch (RM) {

2784 case APInt::Rounding::DOWN:

2785 case APInt::Rounding::UP: {

2786 APInt Quo, Rem;

2787 APInt::sdivrem(A, B, Quo, Rem);

2788 if (Rem.isZero())

2789 return Quo;

2790 // This algorithm deals with arbitrary rounding mode used by sdivrem.

2791 // We want to check whether the non-integer part of the mathematical value

2792 // is negative or not. If the non-integer part is negative, we need to round

2793 // down from Quo; otherwise, if it's positive or 0, we return Quo, as it's

2794 // already rounded down.

2795 if (RM == APInt::Rounding::DOWN) {

2796 if (Rem.isNegative() != B.isNegative())

2797 return Quo - 1;

2798 return Quo;

2799 }

2800 if (Rem.isNegative() != B.isNegative())

2801 return Quo;

2802 return Quo + 1;

2803 }

2804 // Currently sdiv rounds towards zero.

2805 case APInt::Rounding::TOWARD_ZERO:

2806 return A.sdiv(B);

2807 }

2808 llvm_unreachable("Unknown APInt::Rounding enum");

2809}

2810

2811std::optional<APInt>

2812 llvm::APIntOps::SolveQuadraticEquationWrap(APInt A, APInt B, APInt C,

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 // Identify 0 as a (non)solution immediately.

2824 if (C.sextOrTrunc(RangeWidth).isZero()) {

2825 LLVM_DEBUG(dbgs() << __func__ << ": zero solution\n");

2826 return APInt(CoeffWidth, 0);

2827 }

2828

2829 // The result of APInt arithmetic has the same bit width as the operands,

2830 // so it can actually lose high bits. A product of two n-bit integers needs

2831 // 2n-1 bits to represent the full value.

2832 // The operation done below (on quadratic coefficients) that can produce

2833 // the largest value is the evaluation of the equation during bisection,

2834 // which needs 3 times the bitwidth of the coefficient, so the total number

2835 // of required bits is 3n.

2836 //

2837 // The purpose of this extension is to simulate the set Z of all integers,

2838 // where n+1 > n for all n in Z. In Z it makes sense to talk about positive

2839 // and negative numbers (not so much in a modulo arithmetic). The method

2840 // used to solve the equation is based on the standard formula for real

2841 // numbers, and uses the concepts of "positive" and "negative" with their

2842 // usual meanings.

2843 CoeffWidth *= 3;

2844 A = A.sext(CoeffWidth);

2845 B = B.sext(CoeffWidth);

2846 C = C.sext(CoeffWidth);

2847

2848 // Make A > 0 for simplicity. Negate cannot overflow at this point because

2849 // the bit width has increased.

2850 if (A.isNegative()) {

2851 A.negate();

2852 B.negate();

2853 C.negate();

2854 }

2855

2856 // Solving an equation q(x) = 0 with coefficients in modular arithmetic

2857 // is really solving a set of equations q(x) = kR for k = 0, 1, 2, ...,

2858 // and R = 2^BitWidth.

2859 // Since we're trying not only to find exact solutions, but also values

2860 // that "wrap around", such a set will always have a solution, i.e. an x

2861 // that satisfies at least one of the equations, or such that |q(x)|

2862 // exceeds kR, while |q(x-1)| for the same k does not.

2863 //

2864 // We need to find a value k, such that Ax^2 + Bx + C = kR will have a

2865 // positive solution n (in the above sense), and also such that the n

2866 // will be the least among all solutions corresponding to k = 0, 1, ...

2867 // (more precisely, the least element in the set

2868 // { n(k) | k is such that a solution n(k) exists }).

2869 //

2870 // Consider the parabola (over real numbers) that corresponds to the

2871 // quadratic equation. Since A > 0, the arms of the parabola will point

2872 // up. Picking different values of k will shift it up and down by R.

2873 //

2874 // We want to shift the parabola in such a way as to reduce the problem

2875 // of solving q(x) = kR to solving shifted_q(x) = 0.

2876 // (The interesting solutions are the ceilings of the real number

2877 // solutions.)

2878 APInt R = APInt::getOneBitSet(CoeffWidth, RangeWidth);

2879 APInt TwoA = 2 * A;

2880 APInt SqrB = B * B;

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 // The vertex of the parabola is at -B/2A, but since A > 0, it's negative

2892 // iff B is positive.

2893 if (B.isNonNegative()) {

2894 // If B >= 0, the vertex it at a negative location (or at 0), so in

2895 // order to have a non-negative solution we need to pick k that makes

2896 // C-kR negative. To satisfy all the requirements for the solution

2897 // that we are looking for, it needs to be closest to 0 of all k.

2898 C = C.srem(R);

2899 if (C.isStrictlyPositive())

2900 C -= R;

2901 // Pick the greater solution.

2902 PickLow = false;

2903 } else {

2904 // If B < 0, the vertex is at a positive location. For any solution

2905 // to exist, the discriminant must be non-negative. This means that

2906 // C-kR <= B^2/4A is a necessary condition for k, i.e. there is a

2907 // lower bound on values of k: kR >= C - B^2/4A.

2908 APInt LowkR = C - SqrB.udiv(2*TwoA); // udiv because all values > 0.

2909 // Round LowkR up (towards +inf) to the nearest kR.

2910 LowkR = RoundUp(LowkR, R);

2911

2912 // If there exists k meeting the condition above, and such that

2913 // C-kR > 0, there will be two positive real number solutions of

2914 // q(x) = kR. Out of all such values of k, pick the one that makes

2915 // C-kR closest to 0, (i.e. pick maximum k such that C-kR > 0).

2916 // In other words, find maximum k such that LowkR <= kR < C.

2917 if (C.sgt(LowkR)) {

2918 // If LowkR < C, then such a k is guaranteed to exist because

2919 // LowkR itself is a multiple of R.

2920 C -= -RoundUp(-C, R); // C = C - RoundDown(C, R)

2921 // Pick the smaller solution.

2922 PickLow = true;

2923 } else {

2924 // If C-kR < 0 for all potential k's, it means that one solution

2925 // will be negative, while the other will be positive. The positive

2926 // solution will shift towards 0 if the parabola is moved up.

2927 // Pick the kR closest to the lower bound (i.e. make C-kR closest

2928 // to 0, or in other words, out of all parabolas that have solutions,

2929 // pick the one that is the farthest "up").

2930 // Since LowkR is itself a multiple of R, simply take C-LowkR.

2931 C -= LowkR;

2932 // Pick the greater solution.

2933 PickLow = false;

2934 }

2935 }

2936

2937 LLVM_DEBUG(dbgs() << __func__ << ": updated coefficients " << A << "x^2 + "

2938 << B << "x + " << C << ", rw:" << RangeWidth << '\n');

2939

2940 APInt D = SqrB - 4*A*C;

2941 assert(D.isNonNegative() && "Negative discriminant");

2942 APInt SQ = D.sqrt();

2943

2944 APInt Q = SQ * SQ;

2945 bool InexactSQ = Q != D;

2946 // The calculated SQ may actually be greater than the exact (non-integer)

2947 // value. If that's the case, decrement SQ to get a value that is lower.

2948 if (Q.sgt(D))

2949 SQ -= 1;

2950

2951 APInt X;

2952 APInt Rem;

2953

2954 // SQ is rounded down (i.e SQ * SQ <= D), so the roots may be inexact.

2955 // When using the quadratic formula directly, the calculated low root

2956 // may be greater than the exact one, since we would be subtracting SQ.

2957 // To make sure that the calculated root is not greater than the exact

2958 // one, subtract SQ+1 when calculating the low root (for inexact value

2959 // of SQ).

2960 if (PickLow)

2961 APInt::sdivrem(-B - (SQ+InexactSQ), TwoA, X, Rem);

2962 else

2963 APInt::sdivrem(-B + SQ, TwoA, X, Rem);

2964

2965 // The updated coefficients should be such that the (exact) solution is

2966 // positive. Since APInt division rounds towards 0, the calculated one

2967 // can be 0, but cannot be negative.

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 // The exact value of the square root of D should be between SQ and SQ+1.

2977 // This implies that the solution should be between that corresponding to

2978 // SQ (i.e. X) and that corresponding to SQ+1.

2979 //

2980 // The calculated X cannot be greater than the exact (real) solution.

2981 // Actually it must be strictly less than the exact solution, while

2982 // X+1 will be greater than or equal to it.

2983

2984 APInt VX = (A*X + B)*X + C;

2985 APInt VY = VX + TwoA*X + A + B;

2986 bool SignChange =

2987 VX.isNegative() != VY.isNegative() || VX.isZero() != VY.isZero();

2988 // If the sign did not change between X and X+1, X is not a valid solution.

2989 // This could happen when the actual (exact) roots don't have an integer

2990 // between them, so they would both be contained between X and X+1.

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

3002 llvm::APIntOps::GetMostSignificantDifferentBit(const APInt &A, const APInt &B) {

3003 assert(A.getBitWidth() == B.getBitWidth() && "Must have the same bitwidth");

3004 if (A == B)

3005 return std::nullopt;

3006 return A.getBitWidth() - ((A ^ B).countl_zero() + 1);

3007}

3008

3009 APInt llvm::APIntOps::ScaleBitMask(const APInt &A, unsigned NewBitWidth,

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 // Check for matching bitwidths.

3018 if (OldBitWidth == NewBitWidth)

3019 return A;

3020

3021 APInt NewA = APInt::getZero(NewBitWidth);

3022

3023 // Check for null input.

3024 if (A.isZero())

3025 return NewA;

3026

3027 if (NewBitWidth > OldBitWidth) {

3028 // Repeat bits.

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

3038 NewA.setBit(i);

3039 } else {

3040 if (!A.extractBits(Scale, i * Scale).isZero())

3041 NewA.setBit(i);

3042 }

3043 }

3044 }

3045

3046 return NewA;

3047}

3048

3049/// StoreIntToMemory - Fills the StoreBytes bytes of memory starting from Dst

3050/// with the integer held in IntVal.

3051 void llvm::StoreIntToMemory(const APInt &IntVal, uint8_t *Dst,

3052 unsigned StoreBytes) {

3053 assert((IntVal.getBitWidth()+7)/8 >= StoreBytes && "Integer too small!");

3054 const uint8_t *Src = (const uint8_t *)IntVal.getRawData();

3055

3056 if (sys::IsLittleEndianHost) {

3057 // Little-endian host - the source is ordered from LSB to MSB. Order the

3058 // destination from LSB to MSB: Do a straight copy.

3059 memcpy(Dst, Src, StoreBytes);

3060 } else {

3061 // Big-endian host - the source is an array of 64 bit words ordered from

3062 // LSW to MSW. Each word is ordered from MSB to LSB. Order the destination

3063 // from MSB to LSB: Reverse the word order, but not the bytes in a word.

3064 while (StoreBytes > sizeof(uint64_t)) {

3065 StoreBytes -= sizeof(uint64_t);

3066 // May not be aligned so use memcpy.

3067 memcpy(Dst + StoreBytes, Src, sizeof(uint64_t));

3068 Src += sizeof(uint64_t);

3069 }

3070

3071 memcpy(Dst, Src + sizeof(uint64_t) - StoreBytes, StoreBytes);

3072 }

3073}

3074

3075/// LoadIntFromMemory - Loads the integer stored in the LoadBytes bytes starting

3076/// from Src into IntVal, which is assumed to be wide enough and to hold zero.

3077 void llvm::LoadIntFromMemory(APInt &IntVal, const uint8_t *Src,

3078 unsigned LoadBytes) {

3079 assert((IntVal.getBitWidth()+7)/8 >= LoadBytes && "Integer too small!");

3080 uint8_t *Dst = reinterpret_cast<uint8_t *>(

3081 const_cast<uint64_t *>(IntVal.getRawData()));

3082

3083 if (sys::IsLittleEndianHost)

3084 // Little-endian host - the destination must be ordered from LSB to MSB.

3085 // The source is ordered from LSB to MSB: Do a straight copy.

3086 memcpy(Dst, Src, LoadBytes);

3087 else {

3088 // Big-endian - the destination is an array of 64 bit words ordered from

3089 // LSW to MSW. Each word must be ordered from MSB to LSB. The source is

3090 // ordered from MSB to LSB: Reverse the word order, but not the bytes in

3091 // a word.

3092 while (LoadBytes > sizeof(uint64_t)) {

3093 LoadBytes -= sizeof(uint64_t);

3094 // May not be aligned so use memcpy.

3095 memcpy(Dst, Src + LoadBytes, sizeof(uint64_t));

3096 Dst += sizeof(uint64_t);

3097 }

3098

3099 memcpy(Dst + sizeof(uint64_t) - LoadBytes, Src, LoadBytes);

3100 }

3101}

3102

3103 APInt APIntOps::avgFloorS(const APInt &C1, const APInt &C2) {

3104 // Return floor((C1 + C2) / 2)

3105 return (C1 & C2) + (C1 ^ C2).ashr(1);

3106}

3107

3108 APInt APIntOps::avgFloorU(const APInt &C1, const APInt &C2) {

3109 // Return floor((C1 + C2) / 2)

3110 return (C1 & C2) + (C1 ^ C2).lshr(1);

3111}

3112

3113 APInt APIntOps::avgCeilS(const APInt &C1, const APInt &C2) {

3114 // Return ceil((C1 + C2) / 2)

3115 return (C1 | C2) - (C1 ^ C2).ashr(1);

3116}

3117

3118 APInt APIntOps::avgCeilU(const APInt &C1, const APInt &C2) {

3119 // Return ceil((C1 + C2) / 2)

3120 return (C1 | C2) - (C1 ^ C2).lshr(1);

3121}

3122

3123 APInt APIntOps::mulhs(const APInt &C1, const APInt &C2) {

3124 assert(C1.getBitWidth() == C2.getBitWidth() && "Unequal bitwidths");

3125 unsigned FullWidth = C1.getBitWidth() * 2;

3126 APInt C1Ext = C1.sext(FullWidth);

3127 APInt C2Ext = C2.sext(FullWidth);

3128 return (C1Ext * C2Ext).extractBits(C1.getBitWidth(), C1.getBitWidth());

3129}

3130

3131 APInt APIntOps::mulhu(const APInt &C1, const APInt &C2) {

3132 assert(C1.getBitWidth() == C2.getBitWidth() && "Unequal bitwidths");

3133 unsigned FullWidth = C1.getBitWidth() * 2;

3134 APInt C1Ext = C1.zext(FullWidth);

3135 APInt C2Ext = C2.zext(FullWidth);

3136 return (C1Ext * C2Ext).extractBits(C1.getBitWidth(), C1.getBitWidth());

3137}

3138

3139 APInt APIntOps::mulsExtended(const APInt &C1, const APInt &C2) {

3140 assert(C1.getBitWidth() == C2.getBitWidth() && "Unequal bitwidths");

3141 unsigned FullWidth = C1.getBitWidth() * 2;

3142 APInt C1Ext = C1.sext(FullWidth);

3143 APInt C2Ext = C2.sext(FullWidth);

3144 return C1Ext * C2Ext;

3145}

3146

3147 APInt APIntOps::muluExtended(const APInt &C1, const APInt &C2) {

3148 assert(C1.getBitWidth() == C2.getBitWidth() && "Unequal bitwidths");

3149 unsigned FullWidth = C1.getBitWidth() * 2;

3150 APInt C1Ext = C1.zext(FullWidth);

3151 APInt C2Ext = C2.zext(FullWidth);

3152 return C1Ext * C2Ext;

3153}

3154

3155 APInt APIntOps::pow(const APInt &X, int64_t N) {

3156 assert(N >= 0 && "negative exponents not supported.");

3157 APInt Acc = APInt(X.getBitWidth(), 1);

3158 if (N == 0)

3159 return Acc;

3160 APInt Base = X;

3161 int64_t RemainingExponent = N;

3162 while (RemainingExponent > 0) {

3163 while (RemainingExponent % 2 == 0) {

3164 Base *= Base;

3165 RemainingExponent /= 2;

3166 }

3167 --RemainingExponent;

3168 Acc *= Base;

3169 }

3170 return Acc;

3171}

3172

3173 APInt llvm::APIntOps::fshl(const APInt &Hi, const APInt &Lo,

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

3182 APInt llvm::APIntOps::fshr(const APInt &Hi, const APInt &Lo,

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}

assert

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

lowHalf

static APInt::WordType lowHalf(APInt::WordType part)

Returns the value of the lower half of PART.

Definition APInt.cpp:2329

rotateModulo

static unsigned rotateModulo(unsigned BitWidth, const APInt &rotateAmt)

Definition APInt.cpp:1123

highHalf

static APInt::WordType highHalf(APInt::WordType part)

Returns the value of the upper half of PART.

Definition APInt.cpp:2334

tcComplement

static void tcComplement(APInt::WordType *dst, unsigned parts)

Definition APInt.cpp:367

DEBUG_KNUTH

#define DEBUG_KNUTH(X)

getDigit

static unsigned getDigit(char cdigit, uint8_t radix)

A utility function that converts a character to a digit.

Definition APInt.cpp:47

lowBitMask

static APInt::WordType lowBitMask(unsigned bits)

Definition APInt.cpp:2323

getMemory

static uint64_t * getMemory(unsigned numWords)

A utility function for allocating memory and checking for allocation failure.

Definition APInt.cpp:42

KnuthDiv

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

getClearedMemory

static uint64_t * getClearedMemory(unsigned numWords)

A utility function for allocating memory, checking for allocation failures, and ensuring the contents...

Definition APInt.cpp:36

APInt.h

This file implements a class to represent arbitrary precision integral constant values and operations...

Alignment.h

ArrayRef.h

mask

static constexpr unsigned long long mask(BlockVerifier::State S)

Definition BlockVerifier.cpp:16

A

static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")

D

static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")

B

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

LLVM_UNLIKELY

#define LLVM_UNLIKELY(EXPR)

Definition Compiler.h:336

LLVM_DUMP_METHOD

#define LLVM_DUMP_METHOD

Mark debug helper function definitions like dump() that should not be stripped from debug builds.

Definition Compiler.h:638

isNeg

static bool isNeg(Value *V)

Returns true if the operation is a negation of V, and it works for both integers and floats.

Definition ComplexDeinterleavingPass.cpp:612

isSigned

static bool isSigned(unsigned int Opcode)

Definition ExpandLargeDivRem.cpp:52

FoldingSet.h

This file defines a hash set that can be used to remove duplication of nodes in a graph.

Hashing.h

I

#define I(x, y, z)

Definition MD5.cpp:58

MathExtras.h

T

#define T

Definition Mips16ISelLowering.cpp:353

clearUnusedBits

static uint64_t clearUnusedBits(uint64_t Val, unsigned Size)

Definition SIISelLowering.cpp:17702

SmallString.h

This file defines the SmallString class.

StringRef.h

Debug.h

LLVM_DEBUG

#define LLVM_DEBUG(...)

Definition Debug.h:114

X

static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")

RHS

Value * RHS

Definition X86PartialReduction.cpp:81

LHS

Value * LHS

Definition X86PartialReduction.cpp:80

bit.h

This file implements the C++20 <bit> header.

llvm::APInt

Class for arbitrary precision integers.

Definition APInt.h:78

llvm::APInt::umul_ov

LLVM_ABI APInt umul_ov(const APInt &RHS, bool &Overflow) const

Definition APInt.cpp:1971

llvm::APInt::usub_sat

LLVM_ABI APInt usub_sat(const APInt &RHS) const

Definition APInt.cpp:2055

llvm::APInt::udiv

LLVM_ABI APInt udiv(const APInt &RHS) const

Unsigned division operation.

Definition APInt.cpp:1573

llvm::APInt::tcSetBit

static LLVM_ABI void tcSetBit(WordType *, unsigned bit)

Set the given bit of a bignum. Zero-based.

Definition APInt.cpp:2368

llvm::APInt::tcSet

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::APInt::nearestLogBase2

LLVM_ABI unsigned nearestLogBase2() const

Definition APInt.cpp:1172

llvm::APInt::udivrem

static LLVM_ABI void udivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, APInt &Remainder)

Dual division/remainder interface.

Definition APInt.cpp:1758

llvm::APInt::getLoBits

LLVM_ABI APInt getLoBits(unsigned numBits) const

Compute an APInt containing numBits lowbits from this APInt.

Definition APInt.cpp:644

llvm::APInt::tcExtractBit

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::APInt::isAligned

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::APInt::zext

LLVM_ABI APInt zext(unsigned width) const

Zero extend to a new width.

Definition APInt.cpp:1012

llvm::APInt::isMinSignedValue

bool isMinSignedValue() const

Determine if this is the smallest signed value.

Definition APInt.h:424

llvm::APInt::getZExtValue

uint64_t getZExtValue() const

Get zero extended value.

Definition APInt.h:1541

llvm::APInt::truncUSat

LLVM_ABI APInt truncUSat(unsigned width) const

Truncate to new width with unsigned saturation.

Definition APInt.cpp:962

llvm::APInt::pVal

uint64_t * pVal

Used to store the >64 bits integer value.

Definition APInt.h:1940

llvm::APInt::sdivrem

static LLVM_ABI void sdivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, APInt &Remainder)

Definition APInt.cpp:1890

llvm::APInt::tcAdd

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

llvm::APInt::tcExtract

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::APInt::extractBitsAsZExtValue

LLVM_ABI uint64_t extractBitsAsZExtValue(unsigned numBits, unsigned bitPosition) const

Definition APInt.cpp:520

llvm::APInt::getHiBits

LLVM_ABI APInt getHiBits(unsigned numBits) const

Compute an APInt containing numBits highbits from this APInt.

Definition APInt.cpp:639

llvm::APInt::zextOrTrunc

LLVM_ABI APInt zextOrTrunc(unsigned width) const

Zero extend or truncate to width.

Definition APInt.cpp:1033

llvm::APInt::getActiveBits

unsigned getActiveBits() const

Compute the number of active bits in the value.

Definition APInt.h:1513

llvm::APInt::getSufficientBitsNeeded

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::APInt::trunc

LLVM_ABI APInt trunc(unsigned width) const

Truncate to new width.

Definition APInt.cpp:936

llvm::APInt::getMaxValue

static APInt getMaxValue(unsigned numBits)

Gets maximum unsigned value of APInt for specific bit width.

Definition APInt.h:207

llvm::APInt::setBit

void setBit(unsigned BitPosition)

Set the given bit to 1 whose position is given as "bitPosition".

Definition APInt.h:1331

llvm::APInt::toStringUnsigned

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.

Definition APInt.h:1692

llvm::APInt::sshl_ov

LLVM_ABI APInt sshl_ov(const APInt &Amt, bool &Overflow) const

Definition APInt.cpp:1988

llvm::APInt::smul_sat

LLVM_ABI APInt smul_sat(const APInt &RHS) const

Definition APInt.cpp:2064

llvm::APInt::Rounding

Rounding

Definition APInt.h:88

llvm::APInt::Rounding::TOWARD_ZERO

@ TOWARD_ZERO

Definition APInt.h:90

llvm::APInt::Rounding::DOWN

@ DOWN

Definition APInt.h:89

llvm::APInt::Rounding::UP

@ UP

Definition APInt.h:91

llvm::APInt::sadd_sat

LLVM_ABI APInt sadd_sat(const APInt &RHS) const

Definition APInt.cpp:2026

llvm::APInt::sgt

bool sgt(const APInt &RHS) const

Signed greater than comparison.

Definition APInt.h:1202

llvm::APInt::tcCompare

static LLVM_ABI int tcCompare(const WordType *, const WordType *, unsigned)

Comparison (unsigned) of two bignums.

Definition APInt.cpp:2752

llvm::APInt::operator++

LLVM_ABI APInt & operator++()

Prefix increment operator.

Definition APInt.cpp:178

llvm::APInt::usub_ov

LLVM_ABI APInt usub_ov(const APInt &RHS, bool &Overflow) const

Definition APInt.cpp:1948

llvm::APInt::APInt

APInt(unsigned numBits, uint64_t val, bool isSigned=false, bool implicitTrunc=false)

Create a new APInt of numBits width, initialized as val.

Definition APInt.h:111

llvm::APInt::ugt

bool ugt(const APInt &RHS) const

Unsigned greater than comparison.

Definition APInt.h:1183

llvm::APInt::print

LLVM_ABI void print(raw_ostream &OS, bool isSigned) const

Definition APInt.cpp:2307

llvm::APInt::isZero

bool isZero() const

Determine if this value is zero, i.e. all bits are clear.

Definition APInt.h:381

llvm::APInt::urem

LLVM_ABI APInt urem(const APInt &RHS) const

Unsigned remainder operation.

Definition APInt.cpp:1666

llvm::APInt::WordType

uint64_t WordType

Definition APInt.h:80

llvm::APInt::tcAssign

static LLVM_ABI void tcAssign(WordType *, const WordType *, unsigned)

Assign one bignum to another.

Definition APInt.cpp:2348

llvm::APInt::APINT_WORD_SIZE

static constexpr unsigned APINT_WORD_SIZE

Byte size of a word.

Definition APInt.h:83

llvm::APInt::getBitWidth

unsigned getBitWidth() const

Return the number of bits in the APInt.

Definition APInt.h:1489

llvm::APInt::tcShiftRight

static LLVM_ABI void tcShiftRight(WordType *, unsigned Words, unsigned Count)

Shift a bignum right Count bits.

Definition APInt.cpp:2726

llvm::APInt::tcFullMultiply

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

llvm::APInt::ult

bool ult(const APInt &RHS) const

Unsigned less than comparison.

Definition APInt.h:1112

llvm::APInt::getSignedMaxValue

static APInt getSignedMaxValue(unsigned numBits)

Gets maximum signed value of APInt for a specific bit width.

Definition APInt.h:210

llvm::APInt::sfloordiv_ov

LLVM_ABI APInt sfloordiv_ov(const APInt &RHS, bool &Overflow) const

Signed integer floor division operation.

Definition APInt.cpp:2019

llvm::APInt::isSingleWord

bool isSingleWord() const

Determine if this APInt just has one word to store value.

Definition APInt.h:323

llvm::APInt::getNumWords

unsigned getNumWords() const

Get the number of words.

Definition APInt.h:1496

llvm::APInt::APInt

APInt()

Default constructor that creates an APInt with a 1-bit zero value.

Definition APInt.h:174

llvm::APInt::isNegative

bool isNegative() const

Determine sign of this APInt.

Definition APInt.h:330

llvm::APInt::sadd_ov

LLVM_ABI APInt sadd_ov(const APInt &RHS, bool &Overflow) const

Definition APInt.cpp:1928

llvm::APInt::operator<<=

APInt & operator<<=(unsigned ShiftAmt)

Left-shift assignment function.

Definition APInt.h:786

llvm::APInt::sdiv

LLVM_ABI APInt sdiv(const APInt &RHS) const

Signed division function for APInt.

Definition APInt.cpp:1644

llvm::APInt::roundToDouble

double roundToDouble() const

Converts this unsigned APInt to a double value.

Definition APInt.h:1713

llvm::APInt::rotr

LLVM_ABI APInt rotr(unsigned rotateAmt) const

Rotate right by rotateAmt.

Definition APInt.cpp:1154

llvm::APInt::reverseBits

LLVM_ABI APInt reverseBits() const

Definition APInt.cpp:768

llvm::APInt::ashrInPlace

void ashrInPlace(unsigned ShiftAmt)

Arithmetic right-shift this APInt by ShiftAmt in place.

Definition APInt.h:835

llvm::APInt::uadd_ov

LLVM_ABI APInt uadd_ov(const APInt &RHS, bool &Overflow) const

Definition APInt.cpp:1935

llvm::APInt::tcClearBit

static LLVM_ABI void tcClearBit(WordType *, unsigned bit)

Clear the given bit of a bignum. Zero-based.

Definition APInt.cpp:2373

llvm::APInt::negate

void negate()

Negate this APInt in place.

Definition APInt.h:1469

llvm::APInt::tcDecrement

static WordType tcDecrement(WordType *dst, unsigned parts)

Decrement a bignum in-place. Return the borrow flag.

Definition APInt.h:1919

llvm::APInt::countr_zero

unsigned countr_zero() const

Count the number of trailing zero bits.

Definition APInt.h:1640

llvm::APInt::isSplat

LLVM_ABI bool isSplat(unsigned SplatSizeInBits) const

Check if the APInt consists of a repeated bit pattern.

Definition APInt.cpp:630

llvm::APInt::operator-=

LLVM_ABI APInt & operator-=(const APInt &RHS)

Subtraction assignment operator.

Definition APInt.cpp:218

llvm::APInt::isSignedIntN

bool isSignedIntN(unsigned N) const

Check if this APInt has an N-bits signed integer value.

Definition APInt.h:436

llvm::APInt::sdiv_ov

LLVM_ABI APInt sdiv_ov(const APInt &RHS, bool &Overflow) const

Definition APInt.cpp:1954

llvm::APInt::operator*

LLVM_ABI APInt operator*(const APInt &RHS) const

Multiplication operator.

Definition APInt.cpp:235

llvm::APInt::tcLSB

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

llvm::APInt::countl_zero

unsigned countl_zero() const

The APInt version of std::countl_zero.

Definition APInt.h:1599

llvm::APInt::tcShiftLeft

static LLVM_ABI void tcShiftLeft(WordType *, unsigned Words, unsigned Count)

Shift a bignum left Count bits.

Definition APInt.cpp:2699

llvm::APInt::getSplat

static LLVM_ABI APInt getSplat(unsigned NewLen, const APInt &V)

Return a value containing V broadcasted over NewLen bits.

Definition APInt.cpp:651

llvm::APInt::getSignedMinValue

static APInt getSignedMinValue(unsigned numBits)

Gets minimum signed value of APInt for a specific bit width.

Definition APInt.h:220

llvm::APInt::sshl_sat

LLVM_ABI APInt sshl_sat(const APInt &RHS) const

Definition APInt.cpp:2086

llvm::APInt::WORDTYPE_MAX

static constexpr WordType WORDTYPE_MAX

Definition APInt.h:94

llvm::APInt::ushl_sat

LLVM_ABI APInt ushl_sat(const APInt &RHS) const

Definition APInt.cpp:2100

llvm::APInt::ushl_ov

LLVM_ABI APInt ushl_ov(const APInt &Amt, bool &Overflow) const

Definition APInt.cpp:2005

llvm::APInt::tcSubtractPart

static LLVM_ABI WordType tcSubtractPart(WordType *, WordType, unsigned)

DST -= RHS. Returns the carry flag.

Definition APInt.cpp:2502

llvm::APInt::tcIsZero

static LLVM_ABI bool tcIsZero(const WordType *, unsigned)

Returns true if a bignum is zero, false otherwise.

Definition APInt.cpp:2354

llvm::APInt::sextOrTrunc

LLVM_ABI APInt sextOrTrunc(unsigned width) const

Sign extend or truncate to width.

Definition APInt.cpp:1041

llvm::APInt::tcMSB

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

llvm::APInt::tcDivide

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::APInt::dump

LLVM_DUMP_METHOD void dump() const

debug method

Definition APInt.cpp:2298

llvm::APInt::rotl

LLVM_ABI APInt rotl(unsigned rotateAmt) const

Rotate left by rotateAmt.

Definition APInt.cpp:1141

llvm::APInt::countl_one

unsigned countl_one() const

Count the number of leading one bits.

Definition APInt.h:1616

llvm::APInt::insertBits

LLVM_ABI void insertBits(const APInt &SubBits, unsigned bitPosition)

Insert the bits from a smaller APInt starting at bitPosition.

Definition APInt.cpp:397

llvm::APInt::logBase2

unsigned logBase2() const

Definition APInt.h:1762

llvm::APInt::tcMultiplyPart

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

llvm::APInt::APINT_BITS_PER_WORD

static constexpr unsigned APINT_BITS_PER_WORD

Bits in a word.

Definition APInt.h:86

llvm::APInt::getLimitedValue

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.

Definition APInt.h:476

llvm::APInt::tcMultiply

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::APInt::uadd_sat

LLVM_ABI APInt uadd_sat(const APInt &RHS) const

Definition APInt.cpp:2036

llvm::APInt::operator*=

LLVM_ABI APInt & operator*=(const APInt &RHS)

Multiplication assignment operator.

Definition APInt.cpp:265

llvm::APInt::VAL

uint64_t VAL

Used to store the <= 64 bits integer value.

Definition APInt.h:1939

llvm::APInt::getBitsNeeded

static LLVM_ABI unsigned getBitsNeeded(StringRef str, uint8_t radix)

Get bits required for string value.

Definition APInt.cpp:576

llvm::APInt::tcSubtract

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::APInt::multiplicativeInverse

LLVM_ABI APInt multiplicativeInverse() const

Definition APInt.cpp:1274

llvm::APInt::tcNegate

static LLVM_ABI void tcNegate(WordType *, unsigned)

Negate a bignum in-place.

Definition APInt.cpp:2516

llvm::APInt::getBoolValue

bool getBoolValue() const

Convert APInt to a boolean value.

Definition APInt.h:472

llvm::APInt::srem

LLVM_ABI APInt srem(const APInt &RHS) const

Function for signed remainder operation.

Definition APInt.cpp:1736

llvm::APInt::smul_ov

LLVM_ABI APInt smul_ov(const APInt &RHS, bool &Overflow) const

Definition APInt.cpp:1960

llvm::APInt::tcIncrement

static WordType tcIncrement(WordType *dst, unsigned parts)

Increment a bignum in-place. Return the carry flag.

Definition APInt.h:1914

llvm::APInt::isNonNegative

bool isNonNegative() const

Determine if this APInt Value is non-negative (>= 0)

Definition APInt.h:335

llvm::APInt::ule

bool ule(const APInt &RHS) const

Unsigned less or equal comparison.

Definition APInt.h:1151

llvm::APInt::sext

LLVM_ABI APInt sext(unsigned width) const

Sign extend to a new width.

Definition APInt.cpp:985

llvm::APInt::setBits

void setBits(unsigned loBit, unsigned hiBit)

Set the bits from loBit (inclusive) to hiBit (exclusive) to 1.

Definition APInt.h:1368

llvm::APInt::shl

APInt shl(unsigned shiftAmt) const

Left-shift function.

Definition APInt.h:874

llvm::APInt::byteSwap

LLVM_ABI APInt byteSwap() const

Definition APInt.cpp:746

llvm::APInt::umul_sat

LLVM_ABI APInt umul_sat(const APInt &RHS) const

Definition APInt.cpp:2077

llvm::APInt::isPowerOf2

bool isPowerOf2() const

Check if this APInt's value is a power of two greater than zero.

Definition APInt.h:441

llvm::APInt::operator+=

LLVM_ABI APInt & operator+=(const APInt &RHS)

Addition assignment operator.

Definition APInt.cpp:198

llvm::APInt::flipBit

LLVM_ABI void flipBit(unsigned bitPosition)

Toggles a given bit to its opposite value.

Definition APInt.cpp:392

llvm::APInt::getLowBitsSet

static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)

Constructs an APInt value that has the bottom loBitsSet bits set.

Definition APInt.h:307

llvm::APInt::tcAddPart

static LLVM_ABI WordType tcAddPart(WordType *, WordType, unsigned)

DST += RHS. Returns the carry flag.

Definition APInt.cpp:2464

llvm::APInt::getRawData

const uint64_t * getRawData() const

This function returns a pointer to the internal storage of the APInt.

Definition APInt.h:570

llvm::APInt::Profile

LLVM_ABI void Profile(FoldingSetNodeID &id) const

Used to insert APInt objects, or objects that contain APInt objects, into FoldingSets.

Definition APInt.cpp:156

llvm::APInt::getZero

static APInt getZero(unsigned numBits)

Get the '0' value for the specified bit-width.

Definition APInt.h:201

llvm::APInt::extractBits

LLVM_ABI APInt extractBits(unsigned numBits, unsigned bitPosition) const

Return an APInt with the extracted bits [bitPosition,bitPosition+numBits).

Definition APInt.cpp:482

llvm::APInt::isIntN

bool isIntN(unsigned N) const

Check if this APInt has an N-bits unsigned integer value.

Definition APInt.h:433

llvm::APInt::ssub_ov

LLVM_ABI APInt ssub_ov(const APInt &RHS, bool &Overflow) const

Definition APInt.cpp:1941

llvm::APInt::operator--

LLVM_ABI APInt & operator--()

Prefix decrement operator.

Definition APInt.cpp:187

llvm::APInt::isOne

bool isOne() const

Determine if this is a value of 1.

Definition APInt.h:390

llvm::APInt::getOneBitSet

static APInt getOneBitSet(unsigned numBits, unsigned BitNo)

Return an APInt with exactly one bit set in the result.

Definition APInt.h:240

llvm::APInt::getSExtValue

int64_t getSExtValue() const

Get sign extended value.

Definition APInt.h:1563

llvm::APInt::lshrInPlace

void lshrInPlace(unsigned ShiftAmt)

Logical right-shift this APInt by ShiftAmt in place.

Definition APInt.h:859

llvm::APInt::lshr

APInt lshr(unsigned shiftAmt) const

Logical right-shift function.

Definition APInt.h:852

llvm::APInt::sqrt

LLVM_ABI APInt sqrt() const

Compute the square root.

Definition APInt.cpp:1199

llvm::APInt::setBitVal

void setBitVal(unsigned BitPosition, bool BitValue)

Set a given bit to a given value.

Definition APInt.h:1344

llvm::APInt::ssub_sat

LLVM_ABI APInt ssub_sat(const APInt &RHS) const

Definition APInt.cpp:2045

llvm::APInt::toStringSigned

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.

Definition APInt.h:1698

llvm::APInt::truncSSat

LLVM_ABI APInt truncSSat(unsigned width) const

Truncate to new width with signed saturation.

Definition APInt.cpp:973

llvm::APInt::toString

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

llvm::ArrayRef

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

Definition ArrayRef.h:41

llvm::ArrayRef::size

size_t size() const

size - Get the array size.

Definition ArrayRef.h:143

llvm::ArrayRef::data

const T * data() const

Definition ArrayRef.h:140

llvm::FoldingSetNodeID

FoldingSetNodeID - This class is used to gather all the unique data bits of a node.

Definition FoldingSet.h:330

llvm::SmallString

SmallString - A SmallString is just a SmallVector with methods and accessors that make it work better...

Definition SmallString.h:26

llvm::SmallVectorImpl

This class consists of common code factored out of the SmallVector class to reduce code duplication b...

Definition SmallVector.h:574

llvm::StringRef

StringRef - Represent a constant reference to a string, i.e.

Definition StringRef.h:55

llvm::StringRef::iterator

const char * iterator

Definition StringRef.h:59

llvm::StringRef::empty

constexpr bool empty() const

empty - Check if the string is empty.

Definition StringRef.h:143

llvm::StringRef::begin

iterator begin() const

Definition StringRef.h:112

llvm::StringRef::size

constexpr size_t size() const

size - Get the string size.

Definition StringRef.h:146

llvm::StringRef::end

iterator end() const

Definition StringRef.h:114

llvm::hash_code

An opaque object representing a hash code.

Definition Hashing.h:76

llvm::raw_ostream

This class implements an extremely fast bulk output stream that can only output to a stream.

Definition raw_ostream.h:53

#define llvm_unreachable(msg)

Marks that the current location is not supposed to be reachable.

Definition ErrorHandling.h:164

llvm::APIntOps::GetMostSignificantDifferentBit

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::APIntOps::mulhu

LLVM_ABI APInt mulhu(const APInt &C1, const APInt &C2)

Performs (2*N)-bit multiplication on zero-extended operands.

Definition APInt.cpp:3131

llvm::APIntOps::RoundingUDiv

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::APIntOps::avgCeilU

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::APIntOps::muluExtended

LLVM_ABI APInt muluExtended(const APInt &C1, const APInt &C2)

Performs (2*N)-bit multiplication on zero-extended operands.

Definition APInt.cpp:3147

llvm::APIntOps::mulsExtended

LLVM_ABI APInt mulsExtended(const APInt &C1, const APInt &C2)

Performs (2*N)-bit multiplication on sign-extended operands.

Definition APInt.cpp:3139

llvm::APIntOps::avgFloorU

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::APIntOps::fshr

LLVM_ABI APInt fshr(const APInt &Hi, const APInt &Lo, const APInt &Shift)

Perform a funnel shift right.

Definition APInt.cpp:3182

llvm::APIntOps::mulhs

LLVM_ABI APInt mulhs(const APInt &C1, const APInt &C2)

Performs (2*N)-bit multiplication on sign-extended operands.

Definition APInt.cpp:3123

llvm::APIntOps::RoundingSDiv

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::APIntOps::pow

LLVM_ABI APInt pow(const APInt &X, int64_t N)

Compute X^N for N>=0.

Definition APInt.cpp:3155

llvm::APIntOps::RoundDoubleToAPInt

LLVM_ABI APInt RoundDoubleToAPInt(double Double, unsigned width)

Converts the given double value into a APInt.

Definition APInt.cpp:841

llvm::APIntOps::fshl

LLVM_ABI APInt fshl(const APInt &Hi, const APInt &Lo, const APInt &Shift)

Perform a funnel shift left.

Definition APInt.cpp:3173

llvm::APIntOps::ScaleBitMask

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::APIntOps::SolveQuadraticEquationWrap

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::APIntOps::avgFloorS

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::APIntOps::avgCeilS

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::APIntOps::GreatestCommonDivisor

LLVM_ABI APInt GreatestCommonDivisor(APInt A, APInt B)

Compute GCD of two unsigned APInt values.

Definition APInt.cpp:798

llvm::CallingConv::ID

unsigned ID

LLVM IR allows to use arbitrary numbers as calling convention identifiers.

Definition CallingConv.h:24

llvm::CallingConv::C

@ C

The default llvm calling convention, compatible with C.

Definition CallingConv.h:34

llvm::M68k::MemAddrModeKind::V

@ V

Definition M68kBaseInfo.h:63

llvm::RISCVFenceField::R

@ R

Definition RISCVBaseInfo.h:462

llvm::irsymtab::storage::Word

support::ulittle32_t Word

Definition IRSymtab.h:53

llvm::ms_demangle::QualifierMangleMode::Result

@ Result

Definition MicrosoftDemangle.h:132

llvm::numbers::e

constexpr double e

Definition STLForwardCompat.h:61

llvm::sampleprof::Base

@ Base

Definition Discriminator.h:58

llvm::sys::IsLittleEndianHost

constexpr bool IsLittleEndianHost

Definition SwapByteOrder.h:29

llvm

This is an optimization pass for GlobalISel generic memory operations.

Definition AddressRanges.h:18

llvm::hash_value

hash_code hash_value(const FixedPointSemantics &Val)

Definition APFixedPoint.h:137

llvm::StoreIntToMemory

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

llvm::countr_one

int countr_one(T Value)

Count the number of ones from the least significant bit to the first zero bit.

Definition bit.h:293

llvm::byteswap

constexpr T byteswap(T V) noexcept

Reverses the bytes in the given integer value V.

Definition bit.h:102

llvm::popcount

constexpr int popcount(T Value) noexcept

Count the number of set bits in a value.

Definition bit.h:154

llvm::Log2_64

unsigned Log2_64(uint64_t Value)

Return the floor log base 2 of the specified value, -1 if the value is zero.

Definition MathExtras.h:337

llvm::countr_zero

int countr_zero(T Val)

Count number of 0's from the least significant bit to the most stopping at the first 1.

Definition bit.h:202

llvm::countl_zero

int countl_zero(T Val)

Count number of 0's from the most significant bit to the least stopping at the first 1.

Definition bit.h:236

llvm::Hi_32

constexpr uint32_t Hi_32(uint64_t Value)

Return the high 32 bits of a 64 bit value.

Definition MathExtras.h:150

llvm::dbgs

LLVM_ABI raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

Definition Debug.cpp:207

llvm::Count

FunctionAddr VTableAddr Count

Definition InstrProf.h:139

llvm::countl_one

int countl_one(T Value)

Count the number of ones from the most significant bit to the first zero bit.

Definition bit.h:280

llvm::Lo_32

constexpr uint32_t Lo_32(uint64_t Value)

Return the low 32 bits of a 64 bit value.

Definition MathExtras.h:155

llvm::Key

LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key

Definition PassManager.h:668

llvm::PackElem::Hi

@ Hi

Definition VECustomDAG.h:132

llvm::PackElem::Lo

@ Lo

Definition VECustomDAG.h:131

llvm::ModRefInfo::Mod

@ Mod

The access may modify the value stored in memory.

Definition ModRef.h:34

llvm::LEB128Sign::Signed

@ Signed

Definition LEB128.h:232

llvm::bit_cast

To bit_cast(const From &from) noexcept

Definition bit.h:90

llvm::ArrayRef

ArrayRef(const T &OneElt) -> ArrayRef< T >

llvm::BitWidth

constexpr unsigned BitWidth

Definition BitmaskEnum.h:220

llvm::reverseBits

constexpr T reverseBits(T Val)

Reverse the bits in Val.

Definition MathExtras.h:118

llvm::SignExtend64

constexpr int64_t SignExtend64(uint64_t x)

Sign-extend the number in the bottom B bits of X to a 64-bit integer.

Definition MathExtras.h:572

llvm::Log2

unsigned Log2(Align A)

Returns the log2 of the alignment.

Definition Alignment.h:197

llvm::hash_combine

hash_code hash_combine(const Ts &...args)

Combine values into a single hash_code.

Definition Hashing.h:592

llvm::maskTrailingOnes

constexpr T maskTrailingOnes(unsigned N)

Create a bitmask with the N right-most bits set to 1, and all other bits set to 0.

Definition MathExtras.h:77

llvm::Make_64

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.

Definition MathExtras.h:160

llvm::LoadIntFromMemory

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

llvm::hash_combine_range

hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)

Compute a hash_code for a sequence of values.

Definition Hashing.h:466

raw_ostream.h

N

#define N

llvm::Align

This struct is a compact representation of a valid (non-zero power of two) alignment.

Definition Alignment.h:39

llvm::DenseMapInfo

An information struct used to provide DenseMap with the various necessary components for a given valu...

Definition DenseMapInfo.h:54

round

static uint64_t round(uint64_t Acc, uint64_t Input)

Definition xxhash.cpp:80

Generated on for LLVM by doxygen 1.14.0

LLVM: lib/Support/APInt.cpp Source File