1 | //===-- llvm/ADT/APInt.h - For Arbitrary Precision Integer -----*- C++ -*--===// |
---|---|

2 | // |

3 | // The LLVM Compiler Infrastructure |

4 | // |

5 | // This file is distributed under the University of Illinois Open Source |

6 | // License. See LICENSE.TXT for details. |

7 | // |

8 | //===----------------------------------------------------------------------===// |

9 | /// |

10 | /// \file |

11 | /// This file implements a class to represent arbitrary precision |

12 | /// integral constant values and operations on them. |

13 | /// |

14 | //===----------------------------------------------------------------------===// |

15 | |

16 | #ifndef LLVM_ADT_APINT_H |

17 | #define LLVM_ADT_APINT_H |

18 | |

19 | #include "llvm/Support/Compiler.h" |

20 | #include "llvm/Support/MathExtras.h" |

21 | #include <cassert> |

22 | #include <climits> |

23 | #include <cstring> |

24 | #include <string> |

25 | |

26 | namespace llvm { |

27 | class FoldingSetNodeID; |

28 | class StringRef; |

29 | class hash_code; |

30 | class raw_ostream; |

31 | |

32 | template <typename T> class SmallVectorImpl; |

33 | template <typename T> class ArrayRef; |

34 | template <typename T> class Optional; |

35 | |

36 | class APInt; |

37 | |

38 | inline APInt operator-(APInt); |

39 | |

40 | //===----------------------------------------------------------------------===// |

41 | // APInt Class |

42 | //===----------------------------------------------------------------------===// |

43 | |

44 | /// Class for arbitrary precision integers. |

45 | /// |

46 | /// APInt is a functional replacement for common case unsigned integer type like |

47 | /// "unsigned", "unsigned long" or "uint64_t", but also allows non-byte-width |

48 | /// integer sizes and large integer value types such as 3-bits, 15-bits, or more |

49 | /// than 64-bits of precision. APInt provides a variety of arithmetic operators |

50 | /// and methods to manipulate integer values of any bit-width. It supports both |

51 | /// the typical integer arithmetic and comparison operations as well as bitwise |

52 | /// manipulation. |

53 | /// |

54 | /// The class has several invariants worth noting: |

55 | /// * All bit, byte, and word positions are zero-based. |

56 | /// * Once the bit width is set, it doesn't change except by the Truncate, |

57 | /// SignExtend, or ZeroExtend operations. |

58 | /// * All binary operators must be on APInt instances of the same bit width. |

59 | /// Attempting to use these operators on instances with different bit |

60 | /// widths will yield an assertion. |

61 | /// * The value is stored canonically as an unsigned value. For operations |

62 | /// where it makes a difference, there are both signed and unsigned variants |

63 | /// of the operation. For example, sdiv and udiv. However, because the bit |

64 | /// widths must be the same, operations such as Mul and Add produce the same |

65 | /// results regardless of whether the values are interpreted as signed or |

66 | /// not. |

67 | /// * In general, the class tries to follow the style of computation that LLVM |

68 | /// uses in its IR. This simplifies its use for LLVM. |

69 | /// |

70 | class LLVM_NODISCARD APInt { |

71 | public: |

72 | typedef uint64_t WordType; |

73 | |

74 | /// This enum is used to hold the constants we needed for APInt. |

75 | enum : unsigned { |

76 | /// Byte size of a word. |

77 | APINT_WORD_SIZE = sizeof(WordType), |

78 | /// Bits in a word. |

79 | APINT_BITS_PER_WORD = APINT_WORD_SIZE * CHAR_BIT |

80 | }; |

81 | |

82 | enum class Rounding { |

83 | DOWN, |

84 | TOWARD_ZERO, |

85 | UP, |

86 | }; |

87 | |

88 | static const WordType WORDTYPE_MAX = ~WordType(0); |

89 | |

90 | private: |

91 | /// This union is used to store the integer value. When the |

92 | /// integer bit-width <= 64, it uses VAL, otherwise it uses pVal. |

93 | union { |

94 | uint64_t VAL; ///< Used to store the <= 64 bits integer value. |

95 | uint64_t *pVal; ///< Used to store the >64 bits integer value. |

96 | } U; |

97 | |

98 | unsigned BitWidth; ///< The number of bits in this APInt. |

99 | |

100 | friend struct DenseMapAPIntKeyInfo; |

101 | |

102 | friend class APSInt; |

103 | |

104 | /// Fast internal constructor |

105 | /// |

106 | /// This constructor is used only internally for speed of construction of |

107 | /// temporaries. It is unsafe for general use so it is not public. |

108 | APInt(uint64_t *val, unsigned bits) : BitWidth(bits) { |

109 | U.pVal = val; |

110 | } |

111 | |

112 | /// Determine if this APInt just has one word to store value. |

113 | /// |

114 | /// \returns true if the number of bits <= 64, false otherwise. |

115 | bool isSingleWord() const { return BitWidth <= APINT_BITS_PER_WORD; } |

116 | |

117 | /// Determine which word a bit is in. |

118 | /// |

119 | /// \returns the word position for the specified bit position. |

120 | static unsigned whichWord(unsigned bitPosition) { |

121 | return bitPosition / APINT_BITS_PER_WORD; |

122 | } |

123 | |

124 | /// Determine which bit in a word a bit is in. |

125 | /// |

126 | /// \returns the bit position in a word for the specified bit position |

127 | /// in the APInt. |

128 | static unsigned whichBit(unsigned bitPosition) { |

129 | return bitPosition % APINT_BITS_PER_WORD; |

130 | } |

131 | |

132 | /// Get a single bit mask. |

133 | /// |

134 | /// \returns a uint64_t with only bit at "whichBit(bitPosition)" set |

135 | /// This method generates and returns a uint64_t (word) mask for a single |

136 | /// bit at a specific bit position. This is used to mask the bit in the |

137 | /// corresponding word. |

138 | static uint64_t maskBit(unsigned bitPosition) { |

139 | return 1ULL << whichBit(bitPosition); |

140 | } |

141 | |

142 | /// Clear unused high order bits |

143 | /// |

144 | /// This method is used internally to clear the top "N" bits in the high order |

145 | /// word that are not used by the APInt. This is needed after the most |

146 | /// significant word is assigned a value to ensure that those bits are |

147 | /// zero'd out. |

148 | APInt &clearUnusedBits() { |

149 | // Compute how many bits are used in the final word |

150 | unsigned WordBits = ((BitWidth-1) % APINT_BITS_PER_WORD) + 1; |

151 | |

152 | // Mask out the high bits. |

153 | uint64_t mask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - WordBits); |

154 | if (isSingleWord()) |

155 | U.VAL &= mask; |

156 | else |

157 | U.pVal[getNumWords() - 1] &= mask; |

158 | return *this; |

159 | } |

160 | |

161 | /// Get the word corresponding to a bit position |

162 | /// \returns the corresponding word for the specified bit position. |

163 | uint64_t getWord(unsigned bitPosition) const { |

164 | return isSingleWord() ? U.VAL : U.pVal[whichWord(bitPosition)]; |

165 | } |

166 | |

167 | /// Utility method to change the bit width of this APInt to new bit width, |

168 | /// allocating and/or deallocating as necessary. There is no guarantee on the |

169 | /// value of any bits upon return. Caller should populate the bits after. |

170 | void reallocate(unsigned NewBitWidth); |

171 | |

172 | /// Convert a char array into an APInt |

173 | /// |

174 | /// \param radix 2, 8, 10, 16, or 36 |

175 | /// Converts a string into a number. The string must be non-empty |

176 | /// and well-formed as a number of the given base. The bit-width |

177 | /// must be sufficient to hold the result. |

178 | /// |

179 | /// This is used by the constructors that take string arguments. |

180 | /// |

181 | /// StringRef::getAsInteger is superficially similar but (1) does |

182 | /// not assume that the string is well-formed and (2) grows the |

183 | /// result to hold the input. |

184 | void fromString(unsigned numBits, StringRef str, uint8_t radix); |

185 | |

186 | /// An internal division function for dividing APInts. |

187 | /// |

188 | /// This is used by the toString method to divide by the radix. It simply |

189 | /// provides a more convenient form of divide for internal use since KnuthDiv |

190 | /// has specific constraints on its inputs. If those constraints are not met |

191 | /// then it provides a simpler form of divide. |

192 | static void divide(const WordType *LHS, unsigned lhsWords, |

193 | const WordType *RHS, unsigned rhsWords, WordType *Quotient, |

194 | WordType *Remainder); |

195 | |

196 | /// out-of-line slow case for inline constructor |

197 | void initSlowCase(uint64_t val, bool isSigned); |

198 | |

199 | /// shared code between two array constructors |

200 | void initFromArray(ArrayRef<uint64_t> array); |

201 | |

202 | /// out-of-line slow case for inline copy constructor |

203 | void initSlowCase(const APInt &that); |

204 | |

205 | /// out-of-line slow case for shl |

206 | void shlSlowCase(unsigned ShiftAmt); |

207 | |

208 | /// out-of-line slow case for lshr. |

209 | void lshrSlowCase(unsigned ShiftAmt); |

210 | |

211 | /// out-of-line slow case for ashr. |

212 | void ashrSlowCase(unsigned ShiftAmt); |

213 | |

214 | /// out-of-line slow case for operator= |

215 | void AssignSlowCase(const APInt &RHS); |

216 | |

217 | /// out-of-line slow case for operator== |

218 | bool EqualSlowCase(const APInt &RHS) const LLVM_READONLY; |

219 | |

220 | /// out-of-line slow case for countLeadingZeros |

221 | unsigned countLeadingZerosSlowCase() const LLVM_READONLY; |

222 | |

223 | /// out-of-line slow case for countLeadingOnes. |

224 | unsigned countLeadingOnesSlowCase() const LLVM_READONLY; |

225 | |

226 | /// out-of-line slow case for countTrailingZeros. |

227 | unsigned countTrailingZerosSlowCase() const LLVM_READONLY; |

228 | |

229 | /// out-of-line slow case for countTrailingOnes |

230 | unsigned countTrailingOnesSlowCase() const LLVM_READONLY; |

231 | |

232 | /// out-of-line slow case for countPopulation |

233 | unsigned countPopulationSlowCase() const LLVM_READONLY; |

234 | |

235 | /// out-of-line slow case for intersects. |

236 | bool intersectsSlowCase(const APInt &RHS) const LLVM_READONLY; |

237 | |

238 | /// out-of-line slow case for isSubsetOf. |

239 | bool isSubsetOfSlowCase(const APInt &RHS) const LLVM_READONLY; |

240 | |

241 | /// out-of-line slow case for setBits. |

242 | void setBitsSlowCase(unsigned loBit, unsigned hiBit); |

243 | |

244 | /// out-of-line slow case for flipAllBits. |

245 | void flipAllBitsSlowCase(); |

246 | |

247 | /// out-of-line slow case for operator&=. |

248 | void AndAssignSlowCase(const APInt& RHS); |

249 | |

250 | /// out-of-line slow case for operator|=. |

251 | void OrAssignSlowCase(const APInt& RHS); |

252 | |

253 | /// out-of-line slow case for operator^=. |

254 | void XorAssignSlowCase(const APInt& RHS); |

255 | |

256 | /// Unsigned comparison. Returns -1, 0, or 1 if this APInt is less than, equal |

257 | /// to, or greater than RHS. |

258 | int compare(const APInt &RHS) const LLVM_READONLY; |

259 | |

260 | /// Signed comparison. Returns -1, 0, or 1 if this APInt is less than, equal |

261 | /// to, or greater than RHS. |

262 | int compareSigned(const APInt &RHS) const LLVM_READONLY; |

263 | |

264 | public: |

265 | /// \name Constructors |

266 | /// @{ |

267 | |

268 | /// Create a new APInt of numBits width, initialized as val. |

269 | /// |

270 | /// If isSigned is true then val is treated as if it were a signed value |

271 | /// (i.e. as an int64_t) and the appropriate sign extension to the bit width |

272 | /// will be done. Otherwise, no sign extension occurs (high order bits beyond |

273 | /// the range of val are zero filled). |

274 | /// |

275 | /// \param numBits the bit width of the constructed APInt |

276 | /// \param val the initial value of the APInt |

277 | /// \param isSigned how to treat signedness of val |

278 | APInt(unsigned numBits, uint64_t val, bool isSigned = false) |

279 | : BitWidth(numBits) { |

280 | assert(BitWidth && "bitwidth too small"); |

281 | if (isSingleWord()) { |

282 | U.VAL = val; |

283 | clearUnusedBits(); |

284 | } else { |

285 | initSlowCase(val, isSigned); |

286 | } |

287 | } |

288 | |

289 | /// Construct an APInt of numBits width, initialized as bigVal[]. |

290 | /// |

291 | /// Note that bigVal.size() can be smaller or larger than the corresponding |

292 | /// bit width but any extraneous bits will be dropped. |

293 | /// |

294 | /// \param numBits the bit width of the constructed APInt |

295 | /// \param bigVal a sequence of words to form the initial value of the APInt |

296 | APInt(unsigned numBits, ArrayRef<uint64_t> bigVal); |

297 | |

298 | /// Equivalent to APInt(numBits, ArrayRef<uint64_t>(bigVal, numWords)), but |

299 | /// deprecated because this constructor is prone to ambiguity with the |

300 | /// APInt(unsigned, uint64_t, bool) constructor. |

301 | /// |

302 | /// If this overload is ever deleted, care should be taken to prevent calls |

303 | /// from being incorrectly captured by the APInt(unsigned, uint64_t, bool) |

304 | /// constructor. |

305 | APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[]); |

306 | |

307 | /// Construct an APInt from a string representation. |

308 | /// |

309 | /// This constructor interprets the string \p str in the given radix. The |

310 | /// interpretation stops when the first character that is not suitable for the |

311 | /// radix is encountered, or the end of the string. Acceptable radix values |

312 | /// are 2, 8, 10, 16, and 36. It is an error for the value implied by the |

313 | /// string to require more bits than numBits. |

314 | /// |

315 | /// \param numBits the bit width of the constructed APInt |

316 | /// \param str the string to be interpreted |

317 | /// \param radix the radix to use for the conversion |

318 | APInt(unsigned numBits, StringRef str, uint8_t radix); |

319 | |

320 | /// Simply makes *this a copy of that. |

321 | /// Copy Constructor. |

322 | APInt(const APInt &that) : BitWidth(that.BitWidth) { |

323 | if (isSingleWord()) |

324 | U.VAL = that.U.VAL; |

325 | else |

326 | initSlowCase(that); |

327 | } |

328 | |

329 | /// Move Constructor. |

330 | APInt(APInt &&that) : BitWidth(that.BitWidth) { |

331 | memcpy(&U, &that.U, sizeof(U)); |

332 | that.BitWidth = 0; |

333 | } |

334 | |

335 | /// Destructor. |

336 | ~APInt() { |

337 | if (needsCleanup()) |

338 | delete[] U.pVal; |

339 | } |

340 | |

341 | /// Default constructor that creates an uninteresting APInt |

342 | /// representing a 1-bit zero value. |

343 | /// |

344 | /// This is useful for object deserialization (pair this with the static |

345 | /// method Read). |

346 | explicit APInt() : BitWidth(1) { U.VAL = 0; } |

347 | |

348 | /// Returns whether this instance allocated memory. |

349 | bool needsCleanup() const { return !isSingleWord(); } |

350 | |

351 | /// Used to insert APInt objects, or objects that contain APInt objects, into |

352 | /// FoldingSets. |

353 | void Profile(FoldingSetNodeID &id) const; |

354 | |

355 | /// @} |

356 | /// \name Value Tests |

357 | /// @{ |

358 | |

359 | /// Determine sign of this APInt. |

360 | /// |

361 | /// This tests the high bit of this APInt to determine if it is set. |

362 | /// |

363 | /// \returns true if this APInt is negative, false otherwise |

364 | bool isNegative() const { return (*this)[BitWidth - 1]; } |

365 | |

366 | /// Determine if this APInt Value is non-negative (>= 0) |

367 | /// |

368 | /// This tests the high bit of the APInt to determine if it is unset. |

369 | bool isNonNegative() const { return !isNegative(); } |

370 | |

371 | /// Determine if sign bit of this APInt is set. |

372 | /// |

373 | /// This tests the high bit of this APInt to determine if it is set. |

374 | /// |

375 | /// \returns true if this APInt has its sign bit set, false otherwise. |

376 | bool isSignBitSet() const { return (*this)[BitWidth-1]; } |

377 | |

378 | /// Determine if sign bit of this APInt is clear. |

379 | /// |

380 | /// This tests the high bit of this APInt to determine if it is clear. |

381 | /// |

382 | /// \returns true if this APInt has its sign bit clear, false otherwise. |

383 | bool isSignBitClear() const { return !isSignBitSet(); } |

384 | |

385 | /// Determine if this APInt Value is positive. |

386 | /// |

387 | /// This tests if the value of this APInt is positive (> 0). Note |

388 | /// that 0 is not a positive value. |

389 | /// |

390 | /// \returns true if this APInt is positive. |

391 | bool isStrictlyPositive() const { return isNonNegative() && !isNullValue(); } |

392 | |

393 | /// Determine if all bits are set |

394 | /// |

395 | /// This checks to see if the value has all bits of the APInt are set or not. |

396 | bool isAllOnesValue() const { |

397 | if (isSingleWord()) |

398 | return U.VAL == WORDTYPE_MAX >> (APINT_BITS_PER_WORD - BitWidth); |

399 | return countTrailingOnesSlowCase() == BitWidth; |

400 | } |

401 | |

402 | /// Determine if all bits are clear |

403 | /// |

404 | /// This checks to see if the value has all bits of the APInt are clear or |

405 | /// not. |

406 | bool isNullValue() const { return !*this; } |

407 | |

408 | /// Determine if this is a value of 1. |

409 | /// |

410 | /// This checks to see if the value of this APInt is one. |

411 | bool isOneValue() const { |

412 | if (isSingleWord()) |

413 | return U.VAL == 1; |

414 | return countLeadingZerosSlowCase() == BitWidth - 1; |

415 | } |

416 | |

417 | /// Determine if this is the largest unsigned value. |

418 | /// |

419 | /// This checks to see if the value of this APInt is the maximum unsigned |

420 | /// value for the APInt's bit width. |

421 | bool isMaxValue() const { return isAllOnesValue(); } |

422 | |

423 | /// Determine if this is the largest signed value. |

424 | /// |

425 | /// This checks to see if the value of this APInt is the maximum signed |

426 | /// value for the APInt's bit width. |

427 | bool isMaxSignedValue() const { |

428 | if (isSingleWord()) |

429 | return U.VAL == ((WordType(1) << (BitWidth - 1)) - 1); |

430 | return !isNegative() && countTrailingOnesSlowCase() == BitWidth - 1; |

431 | } |

432 | |

433 | /// Determine if this is the smallest unsigned value. |

434 | /// |

435 | /// This checks to see if the value of this APInt is the minimum unsigned |

436 | /// value for the APInt's bit width. |

437 | bool isMinValue() const { return isNullValue(); } |

438 | |

439 | /// Determine if this is the smallest signed value. |

440 | /// |

441 | /// This checks to see if the value of this APInt is the minimum signed |

442 | /// value for the APInt's bit width. |

443 | bool isMinSignedValue() const { |

444 | if (isSingleWord()) |

445 | return U.VAL == (WordType(1) << (BitWidth - 1)); |

446 | return isNegative() && countTrailingZerosSlowCase() == BitWidth - 1; |

447 | } |

448 | |

449 | /// Check if this APInt has an N-bits unsigned integer value. |

450 | bool isIntN(unsigned N) const { |

451 | assert(N && "N == 0 ???"); |

452 | return getActiveBits() <= N; |

453 | } |

454 | |

455 | /// Check if this APInt has an N-bits signed integer value. |

456 | bool isSignedIntN(unsigned N) const { |

457 | assert(N && "N == 0 ???"); |

458 | return getMinSignedBits() <= N; |

459 | } |

460 | |

461 | /// Check if this APInt's value is a power of two greater than zero. |

462 | /// |

463 | /// \returns true if the argument APInt value is a power of two > 0. |

464 | bool isPowerOf2() const { |

465 | if (isSingleWord()) |

466 | return isPowerOf2_64(U.VAL); |

467 | return countPopulationSlowCase() == 1; |

468 | } |

469 | |

470 | /// Check if the APInt's value is returned by getSignMask. |

471 | /// |

472 | /// \returns true if this is the value returned by getSignMask. |

473 | bool isSignMask() const { return isMinSignedValue(); } |

474 | |

475 | /// Convert APInt to a boolean value. |

476 | /// |

477 | /// This converts the APInt to a boolean value as a test against zero. |

478 | bool getBoolValue() const { return !!*this; } |

479 | |

480 | /// If this value is smaller than the specified limit, return it, otherwise |

481 | /// return the limit value. This causes the value to saturate to the limit. |

482 | uint64_t getLimitedValue(uint64_t Limit = UINT64_MAX) const { |

483 | return ugt(Limit) ? Limit : getZExtValue(); |

484 | } |

485 | |

486 | /// Check if the APInt consists of a repeated bit pattern. |

487 | /// |

488 | /// e.g. 0x01010101 satisfies isSplat(8). |

489 | /// \param SplatSizeInBits The size of the pattern in bits. Must divide bit |

490 | /// width without remainder. |

491 | bool isSplat(unsigned SplatSizeInBits) const; |

492 | |

493 | /// \returns true if this APInt value is a sequence of \param numBits ones |

494 | /// starting at the least significant bit with the remainder zero. |

495 | bool isMask(unsigned numBits) const { |

496 | assert(numBits != 0 && "numBits must be non-zero"); |

497 | assert(numBits <= BitWidth && "numBits out of range"); |

498 | if (isSingleWord()) |

499 | return U.VAL == (WORDTYPE_MAX >> (APINT_BITS_PER_WORD - numBits)); |

500 | unsigned Ones = countTrailingOnesSlowCase(); |

501 | return (numBits == Ones) && |

502 | ((Ones + countLeadingZerosSlowCase()) == BitWidth); |

503 | } |

504 | |

505 | /// \returns true if this APInt is a non-empty sequence of ones starting at |

506 | /// the least significant bit with the remainder zero. |

507 | /// Ex. isMask(0x0000FFFFU) == true. |

508 | bool isMask() const { |

509 | if (isSingleWord()) |

510 | return isMask_64(U.VAL); |

511 | unsigned Ones = countTrailingOnesSlowCase(); |

512 | return (Ones > 0) && ((Ones + countLeadingZerosSlowCase()) == BitWidth); |

513 | } |

514 | |

515 | /// Return true if this APInt value contains a sequence of ones with |

516 | /// the remainder zero. |

517 | bool isShiftedMask() const { |

518 | if (isSingleWord()) |

519 | return isShiftedMask_64(U.VAL); |

520 | unsigned Ones = countPopulationSlowCase(); |

521 | unsigned LeadZ = countLeadingZerosSlowCase(); |

522 | return (Ones + LeadZ + countTrailingZeros()) == BitWidth; |

523 | } |

524 | |

525 | /// @} |

526 | /// \name Value Generators |

527 | /// @{ |

528 | |

529 | /// Gets maximum unsigned value of APInt for specific bit width. |

530 | static APInt getMaxValue(unsigned numBits) { |

531 | return getAllOnesValue(numBits); |

532 | } |

533 | |

534 | /// Gets maximum signed value of APInt for a specific bit width. |

535 | static APInt getSignedMaxValue(unsigned numBits) { |

536 | APInt API = getAllOnesValue(numBits); |

537 | API.clearBit(numBits - 1); |

538 | return API; |

539 | } |

540 | |

541 | /// Gets minimum unsigned value of APInt for a specific bit width. |

542 | static APInt getMinValue(unsigned numBits) { return APInt(numBits, 0); } |

543 | |

544 | /// Gets minimum signed value of APInt for a specific bit width. |

545 | static APInt getSignedMinValue(unsigned numBits) { |

546 | APInt API(numBits, 0); |

547 | API.setBit(numBits - 1); |

548 | return API; |

549 | } |

550 | |

551 | /// Get the SignMask for a specific bit width. |

552 | /// |

553 | /// This is just a wrapper function of getSignedMinValue(), and it helps code |

554 | /// readability when we want to get a SignMask. |

555 | static APInt getSignMask(unsigned BitWidth) { |

556 | return getSignedMinValue(BitWidth); |

557 | } |

558 | |

559 | /// Get the all-ones value. |

560 | /// |

561 | /// \returns the all-ones value for an APInt of the specified bit-width. |

562 | static APInt getAllOnesValue(unsigned numBits) { |

563 | return APInt(numBits, WORDTYPE_MAX, true); |

564 | } |

565 | |

566 | /// Get the '0' value. |

567 | /// |

568 | /// \returns the '0' value for an APInt of the specified bit-width. |

569 | static APInt getNullValue(unsigned numBits) { return APInt(numBits, 0); } |

570 | |

571 | /// Compute an APInt containing numBits highbits from this APInt. |

572 | /// |

573 | /// Get an APInt with the same BitWidth as this APInt, just zero mask |

574 | /// the low bits and right shift to the least significant bit. |

575 | /// |

576 | /// \returns the high "numBits" bits of this APInt. |

577 | APInt getHiBits(unsigned numBits) const; |

578 | |

579 | /// Compute an APInt containing numBits lowbits from this APInt. |

580 | /// |

581 | /// Get an APInt with the same BitWidth as this APInt, just zero mask |

582 | /// the high bits. |

583 | /// |

584 | /// \returns the low "numBits" bits of this APInt. |

585 | APInt getLoBits(unsigned numBits) const; |

586 | |

587 | /// Return an APInt with exactly one bit set in the result. |

588 | static APInt getOneBitSet(unsigned numBits, unsigned BitNo) { |

589 | APInt Res(numBits, 0); |

590 | Res.setBit(BitNo); |

591 | return Res; |

592 | } |

593 | |

594 | /// Get a value with a block of bits set. |

595 | /// |

596 | /// Constructs an APInt value that has a contiguous range of bits set. The |

597 | /// bits from loBit (inclusive) to hiBit (exclusive) will be set. All other |

598 | /// bits will be zero. For example, with parameters(32, 0, 16) you would get |

599 | /// 0x0000FFFF. If hiBit is less than loBit then the set bits "wrap". For |

600 | /// example, with parameters (32, 28, 4), you would get 0xF000000F. |

601 | /// |

602 | /// \param numBits the intended bit width of the result |

603 | /// \param loBit the index of the lowest bit set. |

604 | /// \param hiBit the index of the highest bit set. |

605 | /// |

606 | /// \returns An APInt value with the requested bits set. |

607 | static APInt getBitsSet(unsigned numBits, unsigned loBit, unsigned hiBit) { |

608 | APInt Res(numBits, 0); |

609 | Res.setBits(loBit, hiBit); |

610 | return Res; |

611 | } |

612 | |

613 | /// Get a value with upper bits starting at loBit set. |

614 | /// |

615 | /// Constructs an APInt value that has a contiguous range of bits set. The |

616 | /// bits from loBit (inclusive) to numBits (exclusive) will be set. All other |

617 | /// bits will be zero. For example, with parameters(32, 12) you would get |

618 | /// 0xFFFFF000. |

619 | /// |

620 | /// \param numBits the intended bit width of the result |

621 | /// \param loBit the index of the lowest bit to set. |

622 | /// |

623 | /// \returns An APInt value with the requested bits set. |

624 | static APInt getBitsSetFrom(unsigned numBits, unsigned loBit) { |

625 | APInt Res(numBits, 0); |

626 | Res.setBitsFrom(loBit); |

627 | return Res; |

628 | } |

629 | |

630 | /// Get a value with high bits set |

631 | /// |

632 | /// Constructs an APInt value that has the top hiBitsSet bits set. |

633 | /// |

634 | /// \param numBits the bitwidth of the result |

635 | /// \param hiBitsSet the number of high-order bits set in the result. |

636 | static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet) { |

637 | APInt Res(numBits, 0); |

638 | Res.setHighBits(hiBitsSet); |

639 | return Res; |

640 | } |

641 | |

642 | /// Get a value with low bits set |

643 | /// |

644 | /// Constructs an APInt value that has the bottom loBitsSet bits set. |

645 | /// |

646 | /// \param numBits the bitwidth of the result |

647 | /// \param loBitsSet the number of low-order bits set in the result. |

648 | static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet) { |

649 | APInt Res(numBits, 0); |

650 | Res.setLowBits(loBitsSet); |

651 | return Res; |

652 | } |

653 | |

654 | /// Return a value containing V broadcasted over NewLen bits. |

655 | static APInt getSplat(unsigned NewLen, const APInt &V); |

656 | |

657 | /// Determine if two APInts have the same value, after zero-extending |

658 | /// one of them (if needed!) to ensure that the bit-widths match. |

659 | static bool isSameValue(const APInt &I1, const APInt &I2) { |

660 | if (I1.getBitWidth() == I2.getBitWidth()) |

661 | return I1 == I2; |

662 | |

663 | if (I1.getBitWidth() > I2.getBitWidth()) |

664 | return I1 == I2.zext(I1.getBitWidth()); |

665 | |

666 | return I1.zext(I2.getBitWidth()) == I2; |

667 | } |

668 | |

669 | /// Overload to compute a hash_code for an APInt value. |

670 | friend hash_code hash_value(const APInt &Arg); |

671 | |

672 | /// This function returns a pointer to the internal storage of the APInt. |

673 | /// This is useful for writing out the APInt in binary form without any |

674 | /// conversions. |

675 | const uint64_t *getRawData() const { |

676 | if (isSingleWord()) |

677 | return &U.VAL; |

678 | return &U.pVal[0]; |

679 | } |

680 | |

681 | /// @} |

682 | /// \name Unary Operators |

683 | /// @{ |

684 | |

685 | /// Postfix increment operator. |

686 | /// |

687 | /// Increments *this by 1. |

688 | /// |

689 | /// \returns a new APInt value representing the original value of *this. |

690 | const APInt operator++(int) { |

691 | APInt API(*this); |

692 | ++(*this); |

693 | return API; |

694 | } |

695 | |

696 | /// Prefix increment operator. |

697 | /// |

698 | /// \returns *this incremented by one |

699 | APInt &operator++(); |

700 | |

701 | /// Postfix decrement operator. |

702 | /// |

703 | /// Decrements *this by 1. |

704 | /// |

705 | /// \returns a new APInt value representing the original value of *this. |

706 | const APInt operator--(int) { |

707 | APInt API(*this); |

708 | --(*this); |

709 | return API; |

710 | } |

711 | |

712 | /// Prefix decrement operator. |

713 | /// |

714 | /// \returns *this decremented by one. |

715 | APInt &operator--(); |

716 | |

717 | /// Logical negation operator. |

718 | /// |

719 | /// Performs logical negation operation on this APInt. |

720 | /// |

721 | /// \returns true if *this is zero, false otherwise. |

722 | bool operator!() const { |

723 | if (isSingleWord()) |

724 | return U.VAL == 0; |

725 | return countLeadingZerosSlowCase() == BitWidth; |

726 | } |

727 | |

728 | /// @} |

729 | /// \name Assignment Operators |

730 | /// @{ |

731 | |

732 | /// Copy assignment operator. |

733 | /// |

734 | /// \returns *this after assignment of RHS. |

735 | APInt &operator=(const APInt &RHS) { |

736 | // If the bitwidths are the same, we can avoid mucking with memory |

737 | if (isSingleWord() && RHS.isSingleWord()) { |

738 | U.VAL = RHS.U.VAL; |

739 | BitWidth = RHS.BitWidth; |

740 | return clearUnusedBits(); |

741 | } |

742 | |

743 | AssignSlowCase(RHS); |

744 | return *this; |

745 | } |

746 | |

747 | /// Move assignment operator. |

748 | APInt &operator=(APInt &&that) { |

749 | #ifdef _MSC_VER |

750 | // The MSVC std::shuffle implementation still does self-assignment. |

751 | if (this == &that) |

752 | return *this; |

753 | #endif |

754 | assert(this != &that && "Self-move not supported"); |

755 | if (!isSingleWord()) |

756 | delete[] U.pVal; |

757 | |

758 | // Use memcpy so that type based alias analysis sees both VAL and pVal |

759 | // as modified. |

760 | memcpy(&U, &that.U, sizeof(U)); |

761 | |

762 | BitWidth = that.BitWidth; |

763 | that.BitWidth = 0; |

764 | |

765 | return *this; |

766 | } |

767 | |

768 | /// Assignment operator. |

769 | /// |

770 | /// The RHS value is assigned to *this. If the significant bits in RHS exceed |

771 | /// the bit width, the excess bits are truncated. If the bit width is larger |

772 | /// than 64, the value is zero filled in the unspecified high order bits. |

773 | /// |

774 | /// \returns *this after assignment of RHS value. |

775 | APInt &operator=(uint64_t RHS) { |

776 | if (isSingleWord()) { |

777 | U.VAL = RHS; |

778 | clearUnusedBits(); |

779 | } else { |

780 | U.pVal[0] = RHS; |

781 | memset(U.pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE); |

782 | } |

783 | return *this; |

784 | } |

785 | |

786 | /// Bitwise AND assignment operator. |

787 | /// |

788 | /// Performs a bitwise AND operation on this APInt and RHS. The result is |

789 | /// assigned to *this. |

790 | /// |

791 | /// \returns *this after ANDing with RHS. |

792 | APInt &operator&=(const APInt &RHS) { |

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

794 | if (isSingleWord()) |

795 | U.VAL &= RHS.U.VAL; |

796 | else |

797 | AndAssignSlowCase(RHS); |

798 | return *this; |

799 | } |

800 | |

801 | /// Bitwise AND assignment operator. |

802 | /// |

803 | /// Performs a bitwise AND operation on this APInt and RHS. RHS is |

804 | /// logically zero-extended or truncated to match the bit-width of |

805 | /// the LHS. |

806 | APInt &operator&=(uint64_t RHS) { |

807 | if (isSingleWord()) { |

808 | U.VAL &= RHS; |

809 | return *this; |

810 | } |

811 | U.pVal[0] &= RHS; |

812 | memset(U.pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE); |

813 | return *this; |

814 | } |

815 | |

816 | /// Bitwise OR assignment operator. |

817 | /// |

818 | /// Performs a bitwise OR operation on this APInt and RHS. The result is |

819 | /// assigned *this; |

820 | /// |

821 | /// \returns *this after ORing with RHS. |

822 | APInt &operator|=(const APInt &RHS) { |

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

824 | if (isSingleWord()) |

825 | U.VAL |= RHS.U.VAL; |

826 | else |

827 | OrAssignSlowCase(RHS); |

828 | return *this; |

829 | } |

830 | |

831 | /// Bitwise OR assignment operator. |

832 | /// |

833 | /// Performs a bitwise OR operation on this APInt and RHS. RHS is |

834 | /// logically zero-extended or truncated to match the bit-width of |

835 | /// the LHS. |

836 | APInt &operator|=(uint64_t RHS) { |

837 | if (isSingleWord()) { |

838 | U.VAL |= RHS; |

839 | clearUnusedBits(); |

840 | } else { |

841 | U.pVal[0] |= RHS; |

842 | } |

843 | return *this; |

844 | } |

845 | |

846 | /// Bitwise XOR assignment operator. |

847 | /// |

848 | /// Performs a bitwise XOR operation on this APInt and RHS. The result is |

849 | /// assigned to *this. |

850 | /// |

851 | /// \returns *this after XORing with RHS. |

852 | APInt &operator^=(const APInt &RHS) { |

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

854 | if (isSingleWord()) |

855 | U.VAL ^= RHS.U.VAL; |

856 | else |

857 | XorAssignSlowCase(RHS); |

858 | return *this; |

859 | } |

860 | |

861 | /// Bitwise XOR assignment operator. |

862 | /// |

863 | /// Performs a bitwise XOR operation on this APInt and RHS. RHS is |

864 | /// logically zero-extended or truncated to match the bit-width of |

865 | /// the LHS. |

866 | APInt &operator^=(uint64_t RHS) { |

867 | if (isSingleWord()) { |

868 | U.VAL ^= RHS; |

869 | clearUnusedBits(); |

870 | } else { |

871 | U.pVal[0] ^= RHS; |

872 | } |

873 | return *this; |

874 | } |

875 | |

876 | /// Multiplication assignment operator. |

877 | /// |

878 | /// Multiplies this APInt by RHS and assigns the result to *this. |

879 | /// |

880 | /// \returns *this |

881 | APInt &operator*=(const APInt &RHS); |

882 | APInt &operator*=(uint64_t RHS); |

883 | |

884 | /// Addition assignment operator. |

885 | /// |

886 | /// Adds RHS to *this and assigns the result to *this. |

887 | /// |

888 | /// \returns *this |

889 | APInt &operator+=(const APInt &RHS); |

890 | APInt &operator+=(uint64_t RHS); |

891 | |

892 | /// Subtraction assignment operator. |

893 | /// |

894 | /// Subtracts RHS from *this and assigns the result to *this. |

895 | /// |

896 | /// \returns *this |

897 | APInt &operator-=(const APInt &RHS); |

898 | APInt &operator-=(uint64_t RHS); |

899 | |

900 | /// Left-shift assignment function. |

901 | /// |

902 | /// Shifts *this left by shiftAmt and assigns the result to *this. |

903 | /// |

904 | /// \returns *this after shifting left by ShiftAmt |

905 | APInt &operator<<=(unsigned ShiftAmt) { |

906 | assert(ShiftAmt <= BitWidth && "Invalid shift amount"); |

907 | if (isSingleWord()) { |

908 | if (ShiftAmt == BitWidth) |

909 | U.VAL = 0; |

910 | else |

911 | U.VAL <<= ShiftAmt; |

912 | return clearUnusedBits(); |

913 | } |

914 | shlSlowCase(ShiftAmt); |

915 | return *this; |

916 | } |

917 | |

918 | /// Left-shift assignment function. |

919 | /// |

920 | /// Shifts *this left by shiftAmt and assigns the result to *this. |

921 | /// |

922 | /// \returns *this after shifting left by ShiftAmt |

923 | APInt &operator<<=(const APInt &ShiftAmt); |

924 | |

925 | /// @} |

926 | /// \name Binary Operators |

927 | /// @{ |

928 | |

929 | /// Multiplication operator. |

930 | /// |

931 | /// Multiplies this APInt by RHS and returns the result. |

932 | APInt operator*(const APInt &RHS) const; |

933 | |

934 | /// Left logical shift operator. |

935 | /// |

936 | /// Shifts this APInt left by \p Bits and returns the result. |

937 | APInt operator<<(unsigned Bits) const { return shl(Bits); } |

938 | |

939 | /// Left logical shift operator. |

940 | /// |

941 | /// Shifts this APInt left by \p Bits and returns the result. |

942 | APInt operator<<(const APInt &Bits) const { return shl(Bits); } |

943 | |

944 | /// Arithmetic right-shift function. |

945 | /// |

946 | /// Arithmetic right-shift this APInt by shiftAmt. |

947 | APInt ashr(unsigned ShiftAmt) const { |

948 | APInt R(*this); |

949 | R.ashrInPlace(ShiftAmt); |

950 | return R; |

951 | } |

952 | |

953 | /// Arithmetic right-shift this APInt by ShiftAmt in place. |

954 | void ashrInPlace(unsigned ShiftAmt) { |

955 | assert(ShiftAmt <= BitWidth && "Invalid shift amount"); |

956 | if (isSingleWord()) { |

957 | int64_t SExtVAL = SignExtend64(U.VAL, BitWidth); |

958 | if (ShiftAmt == BitWidth) |

959 | U.VAL = SExtVAL >> (APINT_BITS_PER_WORD - 1); // Fill with sign bit. |

960 | else |

961 | U.VAL = SExtVAL >> ShiftAmt; |

962 | clearUnusedBits(); |

963 | return; |

964 | } |

965 | ashrSlowCase(ShiftAmt); |

966 | } |

967 | |

968 | /// Logical right-shift function. |

969 | /// |

970 | /// Logical right-shift this APInt by shiftAmt. |

971 | APInt lshr(unsigned shiftAmt) const { |

972 | APInt R(*this); |

973 | R.lshrInPlace(shiftAmt); |

974 | return R; |

975 | } |

976 | |

977 | /// Logical right-shift this APInt by ShiftAmt in place. |

978 | void lshrInPlace(unsigned ShiftAmt) { |

979 | assert(ShiftAmt <= BitWidth && "Invalid shift amount"); |

980 | if (isSingleWord()) { |

981 | if (ShiftAmt == BitWidth) |

982 | U.VAL = 0; |

983 | else |

984 | U.VAL >>= ShiftAmt; |

985 | return; |

986 | } |

987 | lshrSlowCase(ShiftAmt); |

988 | } |

989 | |

990 | /// Left-shift function. |

991 | /// |

992 | /// Left-shift this APInt by shiftAmt. |

993 | APInt shl(unsigned shiftAmt) const { |

994 | APInt R(*this); |

995 | R <<= shiftAmt; |

996 | return R; |

997 | } |

998 | |

999 | /// Rotate left by rotateAmt. |

1000 | APInt rotl(unsigned rotateAmt) const; |

1001 | |

1002 | /// Rotate right by rotateAmt. |

1003 | APInt rotr(unsigned rotateAmt) const; |

1004 | |

1005 | /// Arithmetic right-shift function. |

1006 | /// |

1007 | /// Arithmetic right-shift this APInt by shiftAmt. |

1008 | APInt ashr(const APInt &ShiftAmt) const { |

1009 | APInt R(*this); |

1010 | R.ashrInPlace(ShiftAmt); |

1011 | return R; |

1012 | } |

1013 | |

1014 | /// Arithmetic right-shift this APInt by shiftAmt in place. |

1015 | void ashrInPlace(const APInt &shiftAmt); |

1016 | |

1017 | /// Logical right-shift function. |

1018 | /// |

1019 | /// Logical right-shift this APInt by shiftAmt. |

1020 | APInt lshr(const APInt &ShiftAmt) const { |

1021 | APInt R(*this); |

1022 | R.lshrInPlace(ShiftAmt); |

1023 | return R; |

1024 | } |

1025 | |

1026 | /// Logical right-shift this APInt by ShiftAmt in place. |

1027 | void lshrInPlace(const APInt &ShiftAmt); |

1028 | |

1029 | /// Left-shift function. |

1030 | /// |

1031 | /// Left-shift this APInt by shiftAmt. |

1032 | APInt shl(const APInt &ShiftAmt) const { |

1033 | APInt R(*this); |

1034 | R <<= ShiftAmt; |

1035 | return R; |

1036 | } |

1037 | |

1038 | /// Rotate left by rotateAmt. |

1039 | APInt rotl(const APInt &rotateAmt) const; |

1040 | |

1041 | /// Rotate right by rotateAmt. |

1042 | APInt rotr(const APInt &rotateAmt) const; |

1043 | |

1044 | /// Unsigned division operation. |

1045 | /// |

1046 | /// Perform an unsigned divide operation on this APInt by RHS. Both this and |

1047 | /// RHS are treated as unsigned quantities for purposes of this division. |

1048 | /// |

1049 | /// \returns a new APInt value containing the division result, rounded towards |

1050 | /// zero. |

1051 | APInt udiv(const APInt &RHS) const; |

1052 | APInt udiv(uint64_t RHS) const; |

1053 | |

1054 | /// Signed division function for APInt. |

1055 | /// |

1056 | /// Signed divide this APInt by APInt RHS. |

1057 | /// |

1058 | /// The result is rounded towards zero. |

1059 | APInt sdiv(const APInt &RHS) const; |

1060 | APInt sdiv(int64_t RHS) const; |

1061 | |

1062 | /// Unsigned remainder operation. |

1063 | /// |

1064 | /// Perform an unsigned remainder operation on this APInt with RHS being the |

1065 | /// divisor. Both this and RHS are treated as unsigned quantities for purposes |

1066 | /// of this operation. Note that this is a true remainder operation and not a |

1067 | /// modulo operation because the sign follows the sign of the dividend which |

1068 | /// is *this. |

1069 | /// |

1070 | /// \returns a new APInt value containing the remainder result |

1071 | APInt urem(const APInt &RHS) const; |

1072 | uint64_t urem(uint64_t RHS) const; |

1073 | |

1074 | /// Function for signed remainder operation. |

1075 | /// |

1076 | /// Signed remainder operation on APInt. |

1077 | APInt srem(const APInt &RHS) const; |

1078 | int64_t srem(int64_t RHS) const; |

1079 | |

1080 | /// Dual division/remainder interface. |

1081 | /// |

1082 | /// Sometimes it is convenient to divide two APInt values and obtain both the |

1083 | /// quotient and remainder. This function does both operations in the same |

1084 | /// computation making it a little more efficient. The pair of input arguments |

1085 | /// may overlap with the pair of output arguments. It is safe to call |

1086 | /// udivrem(X, Y, X, Y), for example. |

1087 | static void udivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, |

1088 | APInt &Remainder); |

1089 | static void udivrem(const APInt &LHS, uint64_t RHS, APInt &Quotient, |

1090 | uint64_t &Remainder); |

1091 | |

1092 | static void sdivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, |

1093 | APInt &Remainder); |

1094 | static void sdivrem(const APInt &LHS, int64_t RHS, APInt &Quotient, |

1095 | int64_t &Remainder); |

1096 | |

1097 | // Operations that return overflow indicators. |

1098 | APInt sadd_ov(const APInt &RHS, bool &Overflow) const; |

1099 | APInt uadd_ov(const APInt &RHS, bool &Overflow) const; |

1100 | APInt ssub_ov(const APInt &RHS, bool &Overflow) const; |

1101 | APInt usub_ov(const APInt &RHS, bool &Overflow) const; |

1102 | APInt sdiv_ov(const APInt &RHS, bool &Overflow) const; |

1103 | APInt smul_ov(const APInt &RHS, bool &Overflow) const; |

1104 | APInt umul_ov(const APInt &RHS, bool &Overflow) const; |

1105 | APInt sshl_ov(const APInt &Amt, bool &Overflow) const; |

1106 | APInt ushl_ov(const APInt &Amt, bool &Overflow) const; |

1107 | |

1108 | /// Array-indexing support. |

1109 | /// |

1110 | /// \returns the bit value at bitPosition |

1111 | bool operator[](unsigned bitPosition) const { |

1112 | assert(bitPosition < getBitWidth() && "Bit position out of bounds!"); |

1113 | return (maskBit(bitPosition) & getWord(bitPosition)) != 0; |

1114 | } |

1115 | |

1116 | /// @} |

1117 | /// \name Comparison Operators |

1118 | /// @{ |

1119 | |

1120 | /// Equality operator. |

1121 | /// |

1122 | /// Compares this APInt with RHS for the validity of the equality |

1123 | /// relationship. |

1124 | bool operator==(const APInt &RHS) const { |

1125 | assert(BitWidth == RHS.BitWidth && "Comparison requires equal bit widths"); |

1126 | if (isSingleWord()) |

1127 | return U.VAL == RHS.U.VAL; |

1128 | return EqualSlowCase(RHS); |

1129 | } |

1130 | |

1131 | /// Equality operator. |

1132 | /// |

1133 | /// Compares this APInt with a uint64_t for the validity of the equality |

1134 | /// relationship. |

1135 | /// |

1136 | /// \returns true if *this == Val |

1137 | bool operator==(uint64_t Val) const { |

1138 | return (isSingleWord() || getActiveBits() <= 64) && getZExtValue() == Val; |

1139 | } |

1140 | |

1141 | /// Equality comparison. |

1142 | /// |

1143 | /// Compares this APInt with RHS for the validity of the equality |

1144 | /// relationship. |

1145 | /// |

1146 | /// \returns true if *this == Val |

1147 | bool eq(const APInt &RHS) const { return (*this) == RHS; } |

1148 | |

1149 | /// Inequality operator. |

1150 | /// |

1151 | /// Compares this APInt with RHS for the validity of the inequality |

1152 | /// relationship. |

1153 | /// |

1154 | /// \returns true if *this != Val |

1155 | bool operator!=(const APInt &RHS) const { return !((*this) == RHS); } |

1156 | |

1157 | /// Inequality operator. |

1158 | /// |

1159 | /// Compares this APInt with a uint64_t for the validity of the inequality |

1160 | /// relationship. |

1161 | /// |

1162 | /// \returns true if *this != Val |

1163 | bool operator!=(uint64_t Val) const { return !((*this) == Val); } |

1164 | |

1165 | /// Inequality comparison |

1166 | /// |

1167 | /// Compares this APInt with RHS for the validity of the inequality |

1168 | /// relationship. |

1169 | /// |

1170 | /// \returns true if *this != Val |

1171 | bool ne(const APInt &RHS) const { return !((*this) == RHS); } |

1172 | |

1173 | /// Unsigned less than comparison |

1174 | /// |

1175 | /// Regards both *this and RHS as unsigned quantities and compares them for |

1176 | /// the validity of the less-than relationship. |

1177 | /// |

1178 | /// \returns true if *this < RHS when both are considered unsigned. |

1179 | bool ult(const APInt &RHS) const { return compare(RHS) < 0; } |

1180 | |

1181 | /// Unsigned less than comparison |

1182 | /// |

1183 | /// Regards both *this as an unsigned quantity and compares it with RHS for |

1184 | /// the validity of the less-than relationship. |

1185 | /// |

1186 | /// \returns true if *this < RHS when considered unsigned. |

1187 | bool ult(uint64_t RHS) const { |

1188 | // Only need to check active bits if not a single word. |

1189 | return (isSingleWord() || getActiveBits() <= 64) && getZExtValue() < RHS; |

1190 | } |

1191 | |

1192 | /// Signed less than comparison |

1193 | /// |

1194 | /// Regards both *this and RHS as signed quantities and compares them for |

1195 | /// validity of the less-than relationship. |

1196 | /// |

1197 | /// \returns true if *this < RHS when both are considered signed. |

1198 | bool slt(const APInt &RHS) const { return compareSigned(RHS) < 0; } |

1199 | |

1200 | /// Signed less than comparison |

1201 | /// |

1202 | /// Regards both *this as a signed quantity and compares it with RHS for |

1203 | /// the validity of the less-than relationship. |

1204 | /// |

1205 | /// \returns true if *this < RHS when considered signed. |

1206 | bool slt(int64_t RHS) const { |

1207 | return (!isSingleWord() && getMinSignedBits() > 64) ? isNegative() |

1208 | : getSExtValue() < RHS; |

1209 | } |

1210 | |

1211 | /// Unsigned less or equal comparison |

1212 | /// |

1213 | /// Regards both *this and RHS as unsigned quantities and compares them for |

1214 | /// validity of the less-or-equal relationship. |

1215 | /// |

1216 | /// \returns true if *this <= RHS when both are considered unsigned. |

1217 | bool ule(const APInt &RHS) const { return compare(RHS) <= 0; } |

1218 | |

1219 | /// Unsigned less or equal comparison |

1220 | /// |

1221 | /// Regards both *this as an unsigned quantity and compares it with RHS for |

1222 | /// the validity of the less-or-equal relationship. |

1223 | /// |

1224 | /// \returns true if *this <= RHS when considered unsigned. |

1225 | bool ule(uint64_t RHS) const { return !ugt(RHS); } |

1226 | |

1227 | /// Signed less or equal comparison |

1228 | /// |

1229 | /// Regards both *this and RHS as signed quantities and compares them for |

1230 | /// validity of the less-or-equal relationship. |

1231 | /// |

1232 | /// \returns true if *this <= RHS when both are considered signed. |

1233 | bool sle(const APInt &RHS) const { return compareSigned(RHS) <= 0; } |

1234 | |

1235 | /// Signed less or equal comparison |

1236 | /// |

1237 | /// Regards both *this as a signed quantity and compares it with RHS for the |

1238 | /// validity of the less-or-equal relationship. |

1239 | /// |

1240 | /// \returns true if *this <= RHS when considered signed. |

1241 | bool sle(uint64_t RHS) const { return !sgt(RHS); } |

1242 | |

1243 | /// Unsigned greather than comparison |

1244 | /// |

1245 | /// Regards both *this and RHS as unsigned quantities and compares them for |

1246 | /// the validity of the greater-than relationship. |

1247 | /// |

1248 | /// \returns true if *this > RHS when both are considered unsigned. |

1249 | bool ugt(const APInt &RHS) const { return !ule(RHS); } |

1250 | |

1251 | /// Unsigned greater than comparison |

1252 | /// |

1253 | /// Regards both *this as an unsigned quantity and compares it with RHS for |

1254 | /// the validity of the greater-than relationship. |

1255 | /// |

1256 | /// \returns true if *this > RHS when considered unsigned. |

1257 | bool ugt(uint64_t RHS) const { |

1258 | // Only need to check active bits if not a single word. |

1259 | return (!isSingleWord() && getActiveBits() > 64) || getZExtValue() > RHS; |

1260 | } |

1261 | |

1262 | /// Signed greather than comparison |

1263 | /// |

1264 | /// Regards both *this and RHS as signed quantities and compares them for the |

1265 | /// validity of the greater-than relationship. |

1266 | /// |

1267 | /// \returns true if *this > RHS when both are considered signed. |

1268 | bool sgt(const APInt &RHS) const { return !sle(RHS); } |

1269 | |

1270 | /// Signed greater than comparison |

1271 | /// |

1272 | /// Regards both *this as a signed quantity and compares it with RHS for |

1273 | /// the validity of the greater-than relationship. |

1274 | /// |

1275 | /// \returns true if *this > RHS when considered signed. |

1276 | bool sgt(int64_t RHS) const { |

1277 | return (!isSingleWord() && getMinSignedBits() > 64) ? !isNegative() |

1278 | : getSExtValue() > RHS; |

1279 | } |

1280 | |

1281 | /// Unsigned greater or equal comparison |

1282 | /// |

1283 | /// Regards both *this and RHS as unsigned quantities and compares them for |

1284 | /// validity of the greater-or-equal relationship. |

1285 | /// |

1286 | /// \returns true if *this >= RHS when both are considered unsigned. |

1287 | bool uge(const APInt &RHS) const { return !ult(RHS); } |

1288 | |

1289 | /// Unsigned greater or equal comparison |

1290 | /// |

1291 | /// Regards both *this as an unsigned quantity and compares it with RHS for |

1292 | /// the validity of the greater-or-equal relationship. |

1293 | /// |

1294 | /// \returns true if *this >= RHS when considered unsigned. |

1295 | bool uge(uint64_t RHS) const { return !ult(RHS); } |

1296 | |

1297 | /// Signed greater or equal comparison |

1298 | /// |

1299 | /// Regards both *this and RHS as signed quantities and compares them for |

1300 | /// validity of the greater-or-equal relationship. |

1301 | /// |

1302 | /// \returns true if *this >= RHS when both are considered signed. |

1303 | bool sge(const APInt &RHS) const { return !slt(RHS); } |

1304 | |

1305 | /// Signed greater or equal comparison |

1306 | /// |

1307 | /// Regards both *this as a signed quantity and compares it with RHS for |

1308 | /// the validity of the greater-or-equal relationship. |

1309 | /// |

1310 | /// \returns true if *this >= RHS when considered signed. |

1311 | bool sge(int64_t RHS) const { return !slt(RHS); } |

1312 | |

1313 | /// This operation tests if there are any pairs of corresponding bits |

1314 | /// between this APInt and RHS that are both set. |

1315 | bool intersects(const APInt &RHS) const { |

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

1317 | if (isSingleWord()) |

1318 | return (U.VAL & RHS.U.VAL) != 0; |

1319 | return intersectsSlowCase(RHS); |

1320 | } |

1321 | |

1322 | /// This operation checks that all bits set in this APInt are also set in RHS. |

1323 | bool isSubsetOf(const APInt &RHS) const { |

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

1325 | if (isSingleWord()) |

1326 | return (U.VAL & ~RHS.U.VAL) == 0; |

1327 | return isSubsetOfSlowCase(RHS); |

1328 | } |

1329 | |

1330 | /// @} |

1331 | /// \name Resizing Operators |

1332 | /// @{ |

1333 | |

1334 | /// Truncate to new width. |

1335 | /// |

1336 | /// Truncate the APInt to a specified width. It is an error to specify a width |

1337 | /// that is greater than or equal to the current width. |

1338 | APInt trunc(unsigned width) const; |

1339 | |

1340 | /// Sign extend to a new width. |

1341 | /// |

1342 | /// This operation sign extends the APInt to a new width. If the high order |

1343 | /// bit is set, the fill on the left will be done with 1 bits, otherwise zero. |

1344 | /// It is an error to specify a width that is less than or equal to the |

1345 | /// current width. |

1346 | APInt sext(unsigned width) const; |

1347 | |

1348 | /// Zero extend to a new width. |

1349 | /// |

1350 | /// This operation zero extends the APInt to a new width. The high order bits |

1351 | /// are filled with 0 bits. It is an error to specify a width that is less |

1352 | /// than or equal to the current width. |

1353 | APInt zext(unsigned width) const; |

1354 | |

1355 | /// Sign extend or truncate to width |

1356 | /// |

1357 | /// Make this APInt have the bit width given by \p width. The value is sign |

1358 | /// extended, truncated, or left alone to make it that width. |

1359 | APInt sextOrTrunc(unsigned width) const; |

1360 | |

1361 | /// Zero extend or truncate to width |

1362 | /// |

1363 | /// Make this APInt have the bit width given by \p width. The value is zero |

1364 | /// extended, truncated, or left alone to make it that width. |

1365 | APInt zextOrTrunc(unsigned width) const; |

1366 | |

1367 | /// Sign extend or truncate to width |

1368 | /// |

1369 | /// Make this APInt have the bit width given by \p width. The value is sign |

1370 | /// extended, or left alone to make it that width. |

1371 | APInt sextOrSelf(unsigned width) const; |

1372 | |

1373 | /// Zero extend or truncate to width |

1374 | /// |

1375 | /// Make this APInt have the bit width given by \p width. The value is zero |

1376 | /// extended, or left alone to make it that width. |

1377 | APInt zextOrSelf(unsigned width) const; |

1378 | |

1379 | /// @} |

1380 | /// \name Bit Manipulation Operators |

1381 | /// @{ |

1382 | |

1383 | /// Set every bit to 1. |

1384 | void setAllBits() { |

1385 | if (isSingleWord()) |

1386 | U.VAL = WORDTYPE_MAX; |

1387 | else |

1388 | // Set all the bits in all the words. |

1389 | memset(U.pVal, -1, getNumWords() * APINT_WORD_SIZE); |

1390 | // Clear the unused ones |

1391 | clearUnusedBits(); |

1392 | } |

1393 | |

1394 | /// Set a given bit to 1. |

1395 | /// |

1396 | /// Set the given bit to 1 whose position is given as "bitPosition". |

1397 | void setBit(unsigned BitPosition) { |

1398 | assert(BitPosition <= BitWidth && "BitPosition out of range"); |

1399 | WordType Mask = maskBit(BitPosition); |

1400 | if (isSingleWord()) |

1401 | U.VAL |= Mask; |

1402 | else |

1403 | U.pVal[whichWord(BitPosition)] |= Mask; |

1404 | } |

1405 | |

1406 | /// Set the sign bit to 1. |

1407 | void setSignBit() { |

1408 | setBit(BitWidth - 1); |

1409 | } |

1410 | |

1411 | /// Set the bits from loBit (inclusive) to hiBit (exclusive) to 1. |

1412 | void setBits(unsigned loBit, unsigned hiBit) { |

1413 | assert(hiBit <= BitWidth && "hiBit out of range"); |

1414 | assert(loBit <= BitWidth && "loBit out of range"); |

1415 | assert(loBit <= hiBit && "loBit greater than hiBit"); |

1416 | if (loBit == hiBit) |

1417 | return; |

1418 | if (loBit < APINT_BITS_PER_WORD && hiBit <= APINT_BITS_PER_WORD) { |

1419 | uint64_t mask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - (hiBit - loBit)); |

1420 | mask <<= loBit; |

1421 | if (isSingleWord()) |

1422 | U.VAL |= mask; |

1423 | else |

1424 | U.pVal[0] |= mask; |

1425 | } else { |

1426 | setBitsSlowCase(loBit, hiBit); |

1427 | } |

1428 | } |

1429 | |

1430 | /// Set the top bits starting from loBit. |

1431 | void setBitsFrom(unsigned loBit) { |

1432 | return setBits(loBit, BitWidth); |

1433 | } |

1434 | |

1435 | /// Set the bottom loBits bits. |

1436 | void setLowBits(unsigned loBits) { |

1437 | return setBits(0, loBits); |

1438 | } |

1439 | |

1440 | /// Set the top hiBits bits. |

1441 | void setHighBits(unsigned hiBits) { |

1442 | return setBits(BitWidth - hiBits, BitWidth); |

1443 | } |

1444 | |

1445 | /// Set every bit to 0. |

1446 | void clearAllBits() { |

1447 | if (isSingleWord()) |

1448 | U.VAL = 0; |

1449 | else |

1450 | memset(U.pVal, 0, getNumWords() * APINT_WORD_SIZE); |

1451 | } |

1452 | |

1453 | /// Set a given bit to 0. |

1454 | /// |

1455 | /// Set the given bit to 0 whose position is given as "bitPosition". |

1456 | void clearBit(unsigned BitPosition) { |

1457 | assert(BitPosition <= BitWidth && "BitPosition out of range"); |

1458 | WordType Mask = ~maskBit(BitPosition); |

1459 | if (isSingleWord()) |

1460 | U.VAL &= Mask; |

1461 | else |

1462 | U.pVal[whichWord(BitPosition)] &= Mask; |

1463 | } |

1464 | |

1465 | /// Set the sign bit to 0. |

1466 | void clearSignBit() { |

1467 | clearBit(BitWidth - 1); |

1468 | } |

1469 | |

1470 | /// Toggle every bit to its opposite value. |

1471 | void flipAllBits() { |

1472 | if (isSingleWord()) { |

1473 | U.VAL ^= WORDTYPE_MAX; |

1474 | clearUnusedBits(); |

1475 | } else { |

1476 | flipAllBitsSlowCase(); |

1477 | } |

1478 | } |

1479 | |

1480 | /// Toggles a given bit to its opposite value. |

1481 | /// |

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

1483 | /// as "bitPosition". |

1484 | void flipBit(unsigned bitPosition); |

1485 | |

1486 | /// Negate this APInt in place. |

1487 | void negate() { |

1488 | flipAllBits(); |

1489 | ++(*this); |

1490 | } |

1491 | |

1492 | /// Insert the bits from a smaller APInt starting at bitPosition. |

1493 | void insertBits(const APInt &SubBits, unsigned bitPosition); |

1494 | |

1495 | /// Return an APInt with the extracted bits [bitPosition,bitPosition+numBits). |

1496 | APInt extractBits(unsigned numBits, unsigned bitPosition) const; |

1497 | |

1498 | /// @} |

1499 | /// \name Value Characterization Functions |

1500 | /// @{ |

1501 | |

1502 | /// Return the number of bits in the APInt. |

1503 | unsigned getBitWidth() const { return BitWidth; } |

1504 | |

1505 | /// Get the number of words. |

1506 | /// |

1507 | /// Here one word's bitwidth equals to that of uint64_t. |

1508 | /// |

1509 | /// \returns the number of words to hold the integer value of this APInt. |

1510 | unsigned getNumWords() const { return getNumWords(BitWidth); } |

1511 | |

1512 | /// Get the number of words. |

1513 | /// |

1514 | /// *NOTE* Here one word's bitwidth equals to that of uint64_t. |

1515 | /// |

1516 | /// \returns the number of words to hold the integer value with a given bit |

1517 | /// width. |

1518 | static unsigned getNumWords(unsigned BitWidth) { |

1519 | return ((uint64_t)BitWidth + APINT_BITS_PER_WORD - 1) / APINT_BITS_PER_WORD; |

1520 | } |

1521 | |

1522 | /// Compute the number of active bits in the value |

1523 | /// |

1524 | /// This function returns the number of active bits which is defined as the |

1525 | /// bit width minus the number of leading zeros. This is used in several |

1526 | /// computations to see how "wide" the value is. |

1527 | unsigned getActiveBits() const { return BitWidth - countLeadingZeros(); } |

1528 | |

1529 | /// Compute the number of active words in the value of this APInt. |

1530 | /// |

1531 | /// This is used in conjunction with getActiveData to extract the raw value of |

1532 | /// the APInt. |

1533 | unsigned getActiveWords() const { |

1534 | unsigned numActiveBits = getActiveBits(); |

1535 | return numActiveBits ? whichWord(numActiveBits - 1) + 1 : 1; |

1536 | } |

1537 | |

1538 | /// Get the minimum bit size for this signed APInt |

1539 | /// |

1540 | /// Computes the minimum bit width for this APInt while considering it to be a |

1541 | /// signed (and probably negative) value. If the value is not negative, this |

1542 | /// function returns the same value as getActiveBits()+1. Otherwise, it |

1543 | /// returns the smallest bit width that will retain the negative value. For |

1544 | /// example, -1 can be written as 0b1 or 0xFFFFFFFFFF. 0b1 is shorter and so |

1545 | /// for -1, this function will always return 1. |

1546 | unsigned getMinSignedBits() const { |

1547 | if (isNegative()) |

1548 | return BitWidth - countLeadingOnes() + 1; |

1549 | return getActiveBits() + 1; |

1550 | } |

1551 | |

1552 | /// Get zero extended value |

1553 | /// |

1554 | /// This method attempts to return the value of this APInt as a zero extended |

1555 | /// uint64_t. The bitwidth must be <= 64 or the value must fit within a |

1556 | /// uint64_t. Otherwise an assertion will result. |

1557 | uint64_t getZExtValue() const { |

1558 | if (isSingleWord()) |

1559 | return U.VAL; |

1560 | assert(getActiveBits() <= 64 && "Too many bits for uint64_t"); |

1561 | return U.pVal[0]; |

1562 | } |

1563 | |

1564 | /// Get sign extended value |

1565 | /// |

1566 | /// This method attempts to return the value of this APInt as a sign extended |

1567 | /// int64_t. The bit width must be <= 64 or the value must fit within an |

1568 | /// int64_t. Otherwise an assertion will result. |

1569 | int64_t getSExtValue() const { |

1570 | if (isSingleWord()) |

1571 | return SignExtend64(U.VAL, BitWidth); |

1572 | assert(getMinSignedBits() <= 64 && "Too many bits for int64_t"); |

1573 | return int64_t(U.pVal[0]); |

1574 | } |

1575 | |

1576 | /// Get bits required for string value. |

1577 | /// |

1578 | /// This method determines how many bits are required to hold the APInt |

1579 | /// equivalent of the string given by \p str. |

1580 | static unsigned getBitsNeeded(StringRef str, uint8_t radix); |

1581 | |

1582 | /// The APInt version of the countLeadingZeros functions in |

1583 | /// MathExtras.h. |

1584 | /// |

1585 | /// It counts the number of zeros from the most significant bit to the first |

1586 | /// one bit. |

1587 | /// |

1588 | /// \returns BitWidth if the value is zero, otherwise returns the number of |

1589 | /// zeros from the most significant bit to the first one bits. |

1590 | unsigned countLeadingZeros() const { |

1591 | if (isSingleWord()) { |

1592 | unsigned unusedBits = APINT_BITS_PER_WORD - BitWidth; |

1593 | return llvm::countLeadingZeros(U.VAL) - unusedBits; |

1594 | } |

1595 | return countLeadingZerosSlowCase(); |

1596 | } |

1597 | |

1598 | /// Count the number of leading one bits. |

1599 | /// |

1600 | /// This function is an APInt version of the countLeadingOnes |

1601 | /// functions in MathExtras.h. It counts the number of ones from the most |

1602 | /// significant bit to the first zero bit. |

1603 | /// |

1604 | /// \returns 0 if the high order bit is not set, otherwise returns the number |

1605 | /// of 1 bits from the most significant to the least |

1606 | unsigned countLeadingOnes() const { |

1607 | if (isSingleWord()) |

1608 | return llvm::countLeadingOnes(U.VAL << (APINT_BITS_PER_WORD - BitWidth)); |

1609 | return countLeadingOnesSlowCase(); |

1610 | } |

1611 | |

1612 | /// Computes the number of leading bits of this APInt that are equal to its |

1613 | /// sign bit. |

1614 | unsigned getNumSignBits() const { |

1615 | return isNegative() ? countLeadingOnes() : countLeadingZeros(); |

1616 | } |

1617 | |

1618 | /// Count the number of trailing zero bits. |

1619 | /// |

1620 | /// This function is an APInt version of the countTrailingZeros |

1621 | /// functions in MathExtras.h. It counts the number of zeros from the least |

1622 | /// significant bit to the first set bit. |

1623 | /// |

1624 | /// \returns BitWidth if the value is zero, otherwise returns the number of |

1625 | /// zeros from the least significant bit to the first one bit. |

1626 | unsigned countTrailingZeros() const { |

1627 | if (isSingleWord()) |

1628 | return std::min(unsigned(llvm::countTrailingZeros(U.VAL)), BitWidth); |

1629 | return countTrailingZerosSlowCase(); |

1630 | } |

1631 | |

1632 | /// Count the number of trailing one bits. |

1633 | /// |

1634 | /// This function is an APInt version of the countTrailingOnes |

1635 | /// functions in MathExtras.h. It counts the number of ones from the least |

1636 | /// significant bit to the first zero bit. |

1637 | /// |

1638 | /// \returns BitWidth if the value is all ones, otherwise returns the number |

1639 | /// of ones from the least significant bit to the first zero bit. |

1640 | unsigned countTrailingOnes() const { |

1641 | if (isSingleWord()) |

1642 | return llvm::countTrailingOnes(U.VAL); |

1643 | return countTrailingOnesSlowCase(); |

1644 | } |

1645 | |

1646 | /// Count the number of bits set. |

1647 | /// |

1648 | /// This function is an APInt version of the countPopulation functions |

1649 | /// in MathExtras.h. It counts the number of 1 bits in the APInt value. |

1650 | /// |

1651 | /// \returns 0 if the value is zero, otherwise returns the number of set bits. |

1652 | unsigned countPopulation() const { |

1653 | if (isSingleWord()) |

1654 | return llvm::countPopulation(U.VAL); |

1655 | return countPopulationSlowCase(); |

1656 | } |

1657 | |

1658 | /// @} |

1659 | /// \name Conversion Functions |

1660 | /// @{ |

1661 | void print(raw_ostream &OS, bool isSigned) const; |

1662 | |

1663 | /// Converts an APInt to a string and append it to Str. Str is commonly a |

1664 | /// SmallString. |

1665 | void toString(SmallVectorImpl<char> &Str, unsigned Radix, bool Signed, |

1666 | bool formatAsCLiteral = false) const; |

1667 | |

1668 | /// Considers the APInt to be unsigned and converts it into a string in the |

1669 | /// radix given. The radix can be 2, 8, 10 16, or 36. |

1670 | void toStringUnsigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const { |

1671 | toString(Str, Radix, false, false); |

1672 | } |

1673 | |

1674 | /// Considers the APInt to be signed and converts it into a string in the |

1675 | /// radix given. The radix can be 2, 8, 10, 16, or 36. |

1676 | void toStringSigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const { |

1677 | toString(Str, Radix, true, false); |

1678 | } |

1679 | |

1680 | /// Return the APInt as a std::string. |

1681 | /// |

1682 | /// Note that this is an inefficient method. It is better to pass in a |

1683 | /// SmallVector/SmallString to the methods above to avoid thrashing the heap |

1684 | /// for the string. |

1685 | std::string toString(unsigned Radix, bool Signed) const; |

1686 | |

1687 | /// \returns a byte-swapped representation of this APInt Value. |

1688 | APInt byteSwap() const; |

1689 | |

1690 | /// \returns the value with the bit representation reversed of this APInt |

1691 | /// Value. |

1692 | APInt reverseBits() const; |

1693 | |

1694 | /// Converts this APInt to a double value. |

1695 | double roundToDouble(bool isSigned) const; |

1696 | |

1697 | /// Converts this unsigned APInt to a double value. |

1698 | double roundToDouble() const { return roundToDouble(false); } |

1699 | |

1700 | /// Converts this signed APInt to a double value. |

1701 | double signedRoundToDouble() const { return roundToDouble(true); } |

1702 | |

1703 | /// Converts APInt bits to a double |

1704 | /// |

1705 | /// The conversion does not do a translation from integer to double, it just |

1706 | /// re-interprets the bits as a double. Note that it is valid to do this on |

1707 | /// any bit width. Exactly 64 bits will be translated. |

1708 | double bitsToDouble() const { |

1709 | return BitsToDouble(getWord(0)); |

1710 | } |

1711 | |

1712 | /// Converts APInt bits to a double |

1713 | /// |

1714 | /// The conversion does not do a translation from integer to float, it just |

1715 | /// re-interprets the bits as a float. Note that it is valid to do this on |

1716 | /// any bit width. Exactly 32 bits will be translated. |

1717 | float bitsToFloat() const { |

1718 | return BitsToFloat(getWord(0)); |

1719 | } |

1720 | |

1721 | /// Converts a double to APInt bits. |

1722 | /// |

1723 | /// The conversion does not do a translation from double to integer, it just |

1724 | /// re-interprets the bits of the double. |

1725 | static APInt doubleToBits(double V) { |

1726 | return APInt(sizeof(double) * CHAR_BIT, DoubleToBits(V)); |

1727 | } |

1728 | |

1729 | /// Converts a float to APInt bits. |

1730 | /// |

1731 | /// The conversion does not do a translation from float to integer, it just |

1732 | /// re-interprets the bits of the float. |

1733 | static APInt floatToBits(float V) { |

1734 | return APInt(sizeof(float) * CHAR_BIT, FloatToBits(V)); |

1735 | } |

1736 | |

1737 | /// @} |

1738 | /// \name Mathematics Operations |

1739 | /// @{ |

1740 | |

1741 | /// \returns the floor log base 2 of this APInt. |

1742 | unsigned logBase2() const { return getActiveBits() - 1; } |

1743 | |

1744 | /// \returns the ceil log base 2 of this APInt. |

1745 | unsigned ceilLogBase2() const { |

1746 | APInt temp(*this); |

1747 | --temp; |

1748 | return temp.getActiveBits(); |

1749 | } |

1750 | |

1751 | /// \returns the nearest log base 2 of this APInt. Ties round up. |

1752 | /// |

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

1754 | /// |

1755 | /// log2(0) = UINT32_MAX |

1756 | /// log2(1) = 0 |

1757 | /// |

1758 | /// to get around any mathematical concerns resulting from |

1759 | /// referencing 2 in a space where 2 does no exist. |

1760 | unsigned nearestLogBase2() const { |

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

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

1763 | // UINT32_MAX. |

1764 | if (BitWidth == 1) |

1765 | return U.VAL - 1; |

1766 | |

1767 | // Handle the zero case. |

1768 | if (isNullValue()) |

1769 | return UINT32_MAX; |

1770 | |

1771 | // The non-zero case is handled by computing: |

1772 | // |

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

1774 | // |

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

1776 | unsigned lg = logBase2(); |

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

1778 | } |

1779 | |

1780 | /// \returns the log base 2 of this APInt if its an exact power of two, -1 |

1781 | /// otherwise |

1782 | int32_t exactLogBase2() const { |

1783 | if (!isPowerOf2()) |

1784 | return -1; |

1785 | return logBase2(); |

1786 | } |

1787 | |

1788 | /// Compute the square root |

1789 | APInt sqrt() const; |

1790 | |

1791 | /// Get the absolute value; |

1792 | /// |

1793 | /// If *this is < 0 then return -(*this), otherwise *this; |

1794 | APInt abs() const { |

1795 | if (isNegative()) |

1796 | return -(*this); |

1797 | return *this; |

1798 | } |

1799 | |

1800 | /// \returns the multiplicative inverse for a given modulo. |

1801 | APInt multiplicativeInverse(const APInt &modulo) const; |

1802 | |

1803 | /// @} |

1804 | /// \name Support for division by constant |

1805 | /// @{ |

1806 | |

1807 | /// Calculate the magic number for signed division by a constant. |

1808 | struct ms; |

1809 | ms magic() const; |

1810 | |

1811 | /// Calculate the magic number for unsigned division by a constant. |

1812 | struct mu; |

1813 | mu magicu(unsigned LeadingZeros = 0) const; |

1814 | |

1815 | /// @} |

1816 | /// \name Building-block Operations for APInt and APFloat |

1817 | /// @{ |

1818 | |

1819 | // These building block operations operate on a representation of arbitrary |

1820 | // precision, two's-complement, bignum integer values. They should be |

1821 | // sufficient to implement APInt and APFloat bignum requirements. Inputs are |

1822 | // generally a pointer to the base of an array of integer parts, representing |

1823 | // an unsigned bignum, and a count of how many parts there are. |

1824 | |

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

1826 | /// out higher parts. |

1827 | static void tcSet(WordType *, WordType, unsigned); |

1828 | |

1829 | /// Assign one bignum to another. |

1830 | static void tcAssign(WordType *, const WordType *, unsigned); |

1831 | |

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

1833 | static bool tcIsZero(const WordType *, unsigned); |

1834 | |

1835 | /// Extract the given bit of a bignum; returns 0 or 1. Zero-based. |

1836 | static int tcExtractBit(const WordType *, unsigned bit); |

1837 | |

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

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

1840 | /// significant bit of DST. All high bits above srcBITS in DST are |

1841 | /// zero-filled. |

1842 | static void tcExtract(WordType *, unsigned dstCount, |

1843 | const WordType *, unsigned srcBits, |

1844 | unsigned srcLSB); |

1845 | |

1846 | /// Set the given bit of a bignum. Zero-based. |

1847 | static void tcSetBit(WordType *, unsigned bit); |

1848 | |

1849 | /// Clear the given bit of a bignum. Zero-based. |

1850 | static void tcClearBit(WordType *, unsigned bit); |

1851 | |

1852 | /// Returns the bit number of the least or most significant set bit of a |

1853 | /// number. If the input number has no bits set -1U is returned. |

1854 | static unsigned tcLSB(const WordType *, unsigned n); |

1855 | static unsigned tcMSB(const WordType *parts, unsigned n); |

1856 | |

1857 | /// Negate a bignum in-place. |

1858 | static void tcNegate(WordType *, unsigned); |

1859 | |

1860 | /// DST += RHS + CARRY where CARRY is zero or one. Returns the carry flag. |

1861 | static WordType tcAdd(WordType *, const WordType *, |

1862 | WordType carry, unsigned); |

1863 | /// DST += RHS. Returns the carry flag. |

1864 | static WordType tcAddPart(WordType *, WordType, unsigned); |

1865 | |

1866 | /// DST -= RHS + CARRY where CARRY is zero or one. Returns the carry flag. |

1867 | static WordType tcSubtract(WordType *, const WordType *, |

1868 | WordType carry, unsigned); |

1869 | /// DST -= RHS. Returns the carry flag. |

1870 | static WordType tcSubtractPart(WordType *, WordType, unsigned); |

1871 | |

1872 | /// DST += SRC * MULTIPLIER + PART if add is true |

1873 | /// DST = SRC * MULTIPLIER + PART if add is false |

1874 | /// |

1875 | /// Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC they must |

1876 | /// start at the same point, i.e. DST == SRC. |

1877 | /// |

1878 | /// If DSTPARTS == SRC_PARTS + 1 no overflow occurs and zero is returned. |

1879 | /// Otherwise DST is filled with the least significant DSTPARTS parts of the |

1880 | /// result, and if all of the omitted higher parts were zero return zero, |

1881 | /// otherwise overflow occurred and return one. |

1882 | static int tcMultiplyPart(WordType *dst, const WordType *src, |

1883 | WordType multiplier, WordType carry, |

1884 | unsigned srcParts, unsigned dstParts, |

1885 | bool add); |

1886 | |

1887 | /// DST = LHS * RHS, where DST has the same width as the operands and is |

1888 | /// filled with the least significant parts of the result. Returns one if |

1889 | /// overflow occurred, otherwise zero. DST must be disjoint from both |

1890 | /// operands. |

1891 | static int tcMultiply(WordType *, const WordType *, const WordType *, |

1892 | unsigned); |

1893 | |

1894 | /// DST = LHS * RHS, where DST has width the sum of the widths of the |

1895 | /// operands. No overflow occurs. DST must be disjoint from both operands. |

1896 | static void tcFullMultiply(WordType *, const WordType *, |

1897 | const WordType *, unsigned, unsigned); |

1898 | |

1899 | /// If RHS is zero LHS and REMAINDER are left unchanged, return one. |

1900 | /// Otherwise set LHS to LHS / RHS with the fractional part discarded, set |

1901 | /// REMAINDER to the remainder, return zero. i.e. |

1902 | /// |

1903 | /// OLD_LHS = RHS * LHS + REMAINDER |

1904 | /// |

1905 | /// SCRATCH is a bignum of the same size as the operands and result for use by |

1906 | /// the routine; its contents need not be initialized and are destroyed. LHS, |

1907 | /// REMAINDER and SCRATCH must be distinct. |

1908 | static int tcDivide(WordType *lhs, const WordType *rhs, |

1909 | WordType *remainder, WordType *scratch, |

1910 | unsigned parts); |

1911 | |

1912 | /// Shift a bignum left Count bits. Shifted in bits are zero. There are no |

1913 | /// restrictions on Count. |

1914 | static void tcShiftLeft(WordType *, unsigned Words, unsigned Count); |

1915 | |

1916 | /// Shift a bignum right Count bits. Shifted in bits are zero. There are no |

1917 | /// restrictions on Count. |

1918 | static void tcShiftRight(WordType *, unsigned Words, unsigned Count); |

1919 | |

1920 | /// The obvious AND, OR and XOR and complement operations. |

1921 | static void tcAnd(WordType *, const WordType *, unsigned); |

1922 | static void tcOr(WordType *, const WordType *, unsigned); |

1923 | static void tcXor(WordType *, const WordType *, unsigned); |

1924 | static void tcComplement(WordType *, unsigned); |

1925 | |

1926 | /// Comparison (unsigned) of two bignums. |

1927 | static int tcCompare(const WordType *, const WordType *, unsigned); |

1928 | |

1929 | /// Increment a bignum in-place. Return the carry flag. |

1930 | static WordType tcIncrement(WordType *dst, unsigned parts) { |

1931 | return tcAddPart(dst, 1, parts); |

1932 | } |

1933 | |

1934 | /// Decrement a bignum in-place. Return the borrow flag. |

1935 | static WordType tcDecrement(WordType *dst, unsigned parts) { |

1936 | return tcSubtractPart(dst, 1, parts); |

1937 | } |

1938 | |

1939 | /// Set the least significant BITS and clear the rest. |

1940 | static void tcSetLeastSignificantBits(WordType *, unsigned, unsigned bits); |

1941 | |

1942 | /// debug method |

1943 | void dump() const; |

1944 | |

1945 | /// @} |

1946 | }; |

1947 | |

1948 | /// Magic data for optimising signed division by a constant. |

1949 | struct APInt::ms { |

1950 | APInt m; ///< magic number |

1951 | unsigned s; ///< shift amount |

1952 | }; |

1953 | |

1954 | /// Magic data for optimising unsigned division by a constant. |

1955 | struct APInt::mu { |

1956 | APInt m; ///< magic number |

1957 | bool a; ///< add indicator |

1958 | unsigned s; ///< shift amount |

1959 | }; |

1960 | |

1961 | inline bool operator==(uint64_t V1, const APInt &V2) { return V2 == V1; } |

1962 | |

1963 | inline bool operator!=(uint64_t V1, const APInt &V2) { return V2 != V1; } |

1964 | |

1965 | /// Unary bitwise complement operator. |

1966 | /// |

1967 | /// \returns an APInt that is the bitwise complement of \p v. |

1968 | inline APInt operator~(APInt v) { |

1969 | v.flipAllBits(); |

1970 | return v; |

1971 | } |

1972 | |

1973 | inline APInt operator&(APInt a, const APInt &b) { |

1974 | a &= b; |

1975 | return a; |

1976 | } |

1977 | |

1978 | inline APInt operator&(const APInt &a, APInt &&b) { |

1979 | b &= a; |

1980 | return std::move(b); |

1981 | } |

1982 | |

1983 | inline APInt operator&(APInt a, uint64_t RHS) { |

1984 | a &= RHS; |

1985 | return a; |

1986 | } |

1987 | |

1988 | inline APInt operator&(uint64_t LHS, APInt b) { |

1989 | b &= LHS; |

1990 | return b; |

1991 | } |

1992 | |

1993 | inline APInt operator|(APInt a, const APInt &b) { |

1994 | a |= b; |

1995 | return a; |

1996 | } |

1997 | |

1998 | inline APInt operator|(const APInt &a, APInt &&b) { |

1999 | b |= a; |

2000 | return std::move(b); |

2001 | } |

2002 | |

2003 | inline APInt operator|(APInt a, uint64_t RHS) { |

2004 | a |= RHS; |

2005 | return a; |

2006 | } |

2007 | |

2008 | inline APInt operator|(uint64_t LHS, APInt b) { |

2009 | b |= LHS; |

2010 | return b; |

2011 | } |

2012 | |

2013 | inline APInt operator^(APInt a, const APInt &b) { |

2014 | a ^= b; |

2015 | return a; |

2016 | } |

2017 | |

2018 | inline APInt operator^(const APInt &a, APInt &&b) { |

2019 | b ^= a; |

2020 | return std::move(b); |

2021 | } |

2022 | |

2023 | inline APInt operator^(APInt a, uint64_t RHS) { |

2024 | a ^= RHS; |

2025 | return a; |

2026 | } |

2027 | |

2028 | inline APInt operator^(uint64_t LHS, APInt b) { |

2029 | b ^= LHS; |

2030 | return b; |

2031 | } |

2032 | |

2033 | inline raw_ostream &operator<<(raw_ostream &OS, const APInt &I) { |

2034 | I.print(OS, true); |

2035 | return OS; |

2036 | } |

2037 | |

2038 | inline APInt operator-(APInt v) { |

2039 | v.negate(); |

2040 | return v; |

2041 | } |

2042 | |

2043 | inline APInt operator+(APInt a, const APInt &b) { |

2044 | a += b; |

2045 | return a; |

2046 | } |

2047 | |

2048 | inline APInt operator+(const APInt &a, APInt &&b) { |

2049 | b += a; |

2050 | return std::move(b); |

2051 | } |

2052 | |

2053 | inline APInt operator+(APInt a, uint64_t RHS) { |

2054 | a += RHS; |

2055 | return a; |

2056 | } |

2057 | |

2058 | inline APInt operator+(uint64_t LHS, APInt b) { |

2059 | b += LHS; |

2060 | return b; |

2061 | } |

2062 | |

2063 | inline APInt operator-(APInt a, const APInt &b) { |

2064 | a -= b; |

2065 | return a; |

2066 | } |

2067 | |

2068 | inline APInt operator-(const APInt &a, APInt &&b) { |

2069 | b.negate(); |

2070 | b += a; |

2071 | return std::move(b); |

2072 | } |

2073 | |

2074 | inline APInt operator-(APInt a, uint64_t RHS) { |

2075 | a -= RHS; |

2076 | return a; |

2077 | } |

2078 | |

2079 | inline APInt operator-(uint64_t LHS, APInt b) { |

2080 | b.negate(); |

2081 | b += LHS; |

2082 | return b; |

2083 | } |

2084 | |

2085 | inline APInt operator*(APInt a, uint64_t RHS) { |

2086 | a *= RHS; |

2087 | return a; |

2088 | } |

2089 | |

2090 | inline APInt operator*(uint64_t LHS, APInt b) { |

2091 | b *= LHS; |

2092 | return b; |

2093 | } |

2094 | |

2095 | |

2096 | namespace APIntOps { |

2097 | |

2098 | /// Determine the smaller of two APInts considered to be signed. |

2099 | inline const APInt &smin(const APInt &A, const APInt &B) { |

2100 | return A.slt(B) ? A : B; |

2101 | } |

2102 | |

2103 | /// Determine the larger of two APInts considered to be signed. |

2104 | inline const APInt &smax(const APInt &A, const APInt &B) { |

2105 | return A.sgt(B) ? A : B; |

2106 | } |

2107 | |

2108 | /// Determine the smaller of two APInts considered to be signed. |

2109 | inline const APInt &umin(const APInt &A, const APInt &B) { |

2110 | return A.ult(B) ? A : B; |

2111 | } |

2112 | |

2113 | /// Determine the larger of two APInts considered to be unsigned. |

2114 | inline const APInt &umax(const APInt &A, const APInt &B) { |

2115 | return A.ugt(B) ? A : B; |

2116 | } |

2117 | |

2118 | /// Compute GCD of two unsigned APInt values. |

2119 | /// |

2120 | /// This function returns the greatest common divisor of the two APInt values |

2121 | /// using Stein's algorithm. |

2122 | /// |

2123 | /// \returns the greatest common divisor of A and B. |

2124 | APInt GreatestCommonDivisor(APInt A, APInt B); |

2125 | |

2126 | /// Converts the given APInt to a double value. |

2127 | /// |

2128 | /// Treats the APInt as an unsigned value for conversion purposes. |

2129 | inline double RoundAPIntToDouble(const APInt &APIVal) { |

2130 | return APIVal.roundToDouble(); |

2131 | } |

2132 | |

2133 | /// Converts the given APInt to a double value. |

2134 | /// |

2135 | /// Treats the APInt as a signed value for conversion purposes. |

2136 | inline double RoundSignedAPIntToDouble(const APInt &APIVal) { |

2137 | return APIVal.signedRoundToDouble(); |

2138 | } |

2139 | |

2140 | /// Converts the given APInt to a float vlalue. |

2141 | inline float RoundAPIntToFloat(const APInt &APIVal) { |

2142 | return float(RoundAPIntToDouble(APIVal)); |

2143 | } |

2144 | |

2145 | /// Converts the given APInt to a float value. |

2146 | /// |

2147 | /// Treast the APInt as a signed value for conversion purposes. |

2148 | inline float RoundSignedAPIntToFloat(const APInt &APIVal) { |

2149 | return float(APIVal.signedRoundToDouble()); |

2150 | } |

2151 | |

2152 | /// Converts the given double value into a APInt. |

2153 | /// |

2154 | /// This function convert a double value to an APInt value. |

2155 | APInt RoundDoubleToAPInt(double Double, unsigned width); |

2156 | |

2157 | /// Converts a float value into a APInt. |

2158 | /// |

2159 | /// Converts a float value into an APInt value. |

2160 | inline APInt RoundFloatToAPInt(float Float, unsigned width) { |

2161 | return RoundDoubleToAPInt(double(Float), width); |

2162 | } |

2163 | |

2164 | /// Return A unsign-divided by B, rounded by the given rounding mode. |

2165 | APInt RoundingUDiv(const APInt &A, const APInt &B, APInt::Rounding RM); |

2166 | |

2167 | /// Return A sign-divided by B, rounded by the given rounding mode. |

2168 | APInt RoundingSDiv(const APInt &A, const APInt &B, APInt::Rounding RM); |

2169 | |

2170 | /// Let q(n) = An^2 + Bn + C, and BW = bit width of the value range |

2171 | /// (e.g. 32 for i32). |

2172 | /// This function finds the smallest number n, such that |

2173 | /// (a) n >= 0 and q(n) = 0, or |

2174 | /// (b) n >= 1 and q(n-1) and q(n), when evaluated in the set of all |

2175 | /// integers, belong to two different intervals [Rk, Rk+R), |

2176 | /// where R = 2^BW, and k is an integer. |

2177 | /// The idea here is to find when q(n) "overflows" 2^BW, while at the |

2178 | /// same time "allowing" subtraction. In unsigned modulo arithmetic a |

2179 | /// subtraction (treated as addition of negated numbers) would always |

2180 | /// count as an overflow, but here we want to allow values to decrease |

2181 | /// and increase as long as they are within the same interval. |

2182 | /// Specifically, adding of two negative numbers should not cause an |

2183 | /// overflow (as long as the magnitude does not exceed the bith width). |

2184 | /// On the other hand, given a positive number, adding a negative |

2185 | /// number to it can give a negative result, which would cause the |

2186 | /// value to go from [-2^BW, 0) to [0, 2^BW). In that sense, zero is |

2187 | /// treated as a special case of an overflow. |

2188 | /// |

2189 | /// This function returns None if after finding k that minimizes the |

2190 | /// positive solution to q(n) = kR, both solutions are contained between |

2191 | /// two consecutive integers. |

2192 | /// |

2193 | /// There are cases where q(n) > T, and q(n+1) < T (assuming evaluation |

2194 | /// in arithmetic modulo 2^BW, and treating the values as signed) by the |

2195 | /// virtue of *signed* overflow. This function will *not* find such an n, |

2196 | /// however it may find a value of n satisfying the inequalities due to |

2197 | /// an *unsigned* overflow (if the values are treated as unsigned). |

2198 | /// To find a solution for a signed overflow, treat it as a problem of |

2199 | /// finding an unsigned overflow with a range with of BW-1. |

2200 | /// |

2201 | /// The returned value may have a different bit width from the input |

2202 | /// coefficients. |

2203 | Optional<APInt> SolveQuadraticEquationWrap(APInt A, APInt B, APInt C, |

2204 | unsigned RangeWidth); |

2205 | } // End of APIntOps namespace |

2206 | |

2207 | // See friend declaration above. This additional declaration is required in |

2208 | // order to compile LLVM with IBM xlC compiler. |

2209 | hash_code hash_value(const APInt &Arg); |

2210 | } // End of llvm namespace |

2211 | |

2212 | #endif |

2213 |