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

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 | /// \file |

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

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

12 | /// |

13 | //===----------------------------------------------------------------------===// |

14 | |

15 | #ifndef LLVM_ADT_APINT_H |

16 | #define LLVM_ADT_APINT_H |

17 | |

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

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

20 | #include <cassert> |

21 | #include <climits> |

22 | #include <cstring> |

23 | #include <string> |

24 | |

25 | namespace llvm { |

26 | class FoldingSetNodeID; |

27 | class StringRef; |

28 | class hash_code; |

29 | class raw_ostream; |

30 | |

31 | template <typename T> class SmallVectorImpl; |

32 | template <typename T> class ArrayRef; |

33 | template <typename T> class Optional; |

34 | |

35 | class APInt; |

36 | |

37 | inline APInt operator-(APInt); |

38 | |

39 | //===----------------------------------------------------------------------===// |

40 | // APInt Class |

41 | //===----------------------------------------------------------------------===// |

42 | |

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

44 | /// |

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

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

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

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

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

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

51 | /// manipulation. |

52 | /// |

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

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

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

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

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

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

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

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

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

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

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

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

65 | /// not. |

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

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

68 | /// |

69 | class LLVM_NODISCARD APInt { |

70 | public: |

71 | typedef uint64_t WordType; |

72 | |

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

74 | enum : unsigned { |

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

76 | APINT_WORD_SIZE = sizeof(WordType), |

77 | /// Bits in a word. |

78 | APINT_BITS_PER_WORD = APINT_WORD_SIZE * CHAR_BIT |

79 | }; |

80 | |

81 | enum class Rounding { |

82 | DOWN, |

83 | TOWARD_ZERO, |

84 | UP, |

85 | }; |

86 | |

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

88 | |

89 | private: |

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

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

92 | union { |

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

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

95 | } U; |

96 | |

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

98 | |

99 | friend struct DenseMapAPIntKeyInfo; |

100 | |

101 | friend class APSInt; |

102 | |

103 | /// Fast internal constructor |

104 | /// |

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

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

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

108 | U.pVal = val; |

109 | } |

110 | |

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

112 | /// |

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

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

115 | |

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

117 | /// |

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

119 | static unsigned whichWord(unsigned bitPosition) { |

120 | return bitPosition / APINT_BITS_PER_WORD; |

121 | } |

122 | |

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

124 | /// |

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

126 | /// in the APInt. |

127 | static unsigned whichBit(unsigned bitPosition) { |

128 | return bitPosition % APINT_BITS_PER_WORD; |

129 | } |

130 | |

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

132 | /// |

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

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

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

136 | /// corresponding word. |

137 | static uint64_t maskBit(unsigned bitPosition) { |

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

139 | } |

140 | |

141 | /// Clear unused high order bits |

142 | /// |

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

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

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

146 | /// zero'd out. |

147 | APInt &clearUnusedBits() { |

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

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

150 | |

151 | // Mask out the high bits. |

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

153 | if (isSingleWord()) |

154 | U.VAL &= mask; |

155 | else |

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

157 | return *this; |

158 | } |

159 | |

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

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

162 | uint64_t getWord(unsigned bitPosition) const { |

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

164 | } |

165 | |

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

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

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

169 | void reallocate(unsigned NewBitWidth); |

170 | |

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

172 | /// |

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

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

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

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

177 | /// |

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

179 | /// |

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

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

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

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

184 | |

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

186 | /// |

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

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

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

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

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

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

193 | WordType *Remainder); |

194 | |

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

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

197 | |

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

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

200 | |

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

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

203 | |

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

205 | void shlSlowCase(unsigned ShiftAmt); |

206 | |

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

208 | void lshrSlowCase(unsigned ShiftAmt); |

209 | |

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

211 | void ashrSlowCase(unsigned ShiftAmt); |

212 | |

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

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

215 | |

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

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

218 | |

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

220 | unsigned countLeadingZerosSlowCase() const LLVM_READONLY; |

221 | |

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

223 | unsigned countLeadingOnesSlowCase() const LLVM_READONLY; |

224 | |

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

226 | unsigned countTrailingZerosSlowCase() const LLVM_READONLY; |

227 | |

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

229 | unsigned countTrailingOnesSlowCase() const LLVM_READONLY; |

230 | |

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

232 | unsigned countPopulationSlowCase() const LLVM_READONLY; |

233 | |

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

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

236 | |

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

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

239 | |

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

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

242 | |

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

244 | void flipAllBitsSlowCase(); |

245 | |

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

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

248 | |

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

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

251 | |

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

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

254 | |

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

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

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

258 | |

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

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

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

262 | |

263 | public: |

264 | /// \name Constructors |

265 | /// @{ |

266 | |

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

268 | /// |

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

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

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

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

273 | /// |

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

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

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

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

278 | : BitWidth(numBits) { |

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

280 | if (isSingleWord()) { |

281 | U.VAL = val; |

282 | clearUnusedBits(); |

283 | } else { |

284 | initSlowCase(val, isSigned); |

285 | } |

286 | } |

287 | |

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

289 | /// |

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

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

292 | /// |

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

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

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

296 | |

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

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

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

300 | /// |

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

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

303 | /// constructor. |

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

305 | |

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

307 | /// |

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

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

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

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

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

313 | /// |

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

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

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

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

318 | |

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

320 | /// Copy Constructor. |

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

322 | if (isSingleWord()) |

323 | U.VAL = that.U.VAL; |

324 | else |

325 | initSlowCase(that); |

326 | } |

327 | |

328 | /// Move Constructor. |

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

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

331 | that.BitWidth = 0; |

332 | } |

333 | |

334 | /// Destructor. |

335 | ~APInt() { |

336 | if (needsCleanup()) |

337 | delete[] U.pVal; |

338 | } |

339 | |

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

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

342 | /// |

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

344 | /// method Read). |

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

346 | |

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

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

349 | |

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

351 | /// FoldingSets. |

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

353 | |

354 | /// @} |

355 | /// \name Value Tests |

356 | /// @{ |

357 | |

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

359 | /// |

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

361 | /// |

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

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

364 | |

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

366 | /// |

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

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

369 | |

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

371 | /// |

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

373 | /// |

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

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

376 | |

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

378 | /// |

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

380 | /// |

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

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

383 | |

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

385 | /// |

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

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

388 | /// |

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

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

391 | |

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

393 | /// |

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

395 | bool isAllOnesValue() const { |

396 | if (isSingleWord()) |

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

398 | return countTrailingOnesSlowCase() == BitWidth; |

399 | } |

400 | |

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

402 | /// |

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

404 | /// not. |

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

406 | |

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

408 | /// |

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

410 | bool isOneValue() const { |

411 | if (isSingleWord()) |

412 | return U.VAL == 1; |

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

414 | } |

415 | |

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

417 | /// |

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

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

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

421 | |

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

423 | /// |

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

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

426 | bool isMaxSignedValue() const { |

427 | if (isSingleWord()) |

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

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

430 | } |

431 | |

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

433 | /// |

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

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

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

437 | |

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

439 | /// |

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

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

442 | bool isMinSignedValue() const { |

443 | if (isSingleWord()) |

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

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

446 | } |

447 | |

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

449 | bool isIntN(unsigned N) const { |

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

451 | return getActiveBits() <= N; |

452 | } |

453 | |

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

455 | bool isSignedIntN(unsigned N) const { |

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

457 | return getMinSignedBits() <= N; |

458 | } |

459 | |

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

461 | /// |

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

463 | bool isPowerOf2() const { |

464 | if (isSingleWord()) |

465 | return isPowerOf2_64(U.VAL); |

466 | return countPopulationSlowCase() == 1; |

467 | } |

468 | |

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

470 | /// |

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

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

473 | |

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

475 | /// |

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

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

478 | |

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

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

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

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

483 | } |

484 | |

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

486 | /// |

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

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

489 | /// width without remainder. |

490 | bool isSplat(unsigned SplatSizeInBits) const; |

491 | |

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

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

494 | bool isMask(unsigned numBits) const { |

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

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

497 | if (isSingleWord()) |

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

499 | unsigned Ones = countTrailingOnesSlowCase(); |

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

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

502 | } |

503 | |

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

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

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

507 | bool isMask() const { |

508 | if (isSingleWord()) |

509 | return isMask_64(U.VAL); |

510 | unsigned Ones = countTrailingOnesSlowCase(); |

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

512 | } |

513 | |

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

515 | /// the remainder zero. |

516 | bool isShiftedMask() const { |

517 | if (isSingleWord()) |

518 | return isShiftedMask_64(U.VAL); |

519 | unsigned Ones = countPopulationSlowCase(); |

520 | unsigned LeadZ = countLeadingZerosSlowCase(); |

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

522 | } |

523 | |

524 | /// @} |

525 | /// \name Value Generators |

526 | /// @{ |

527 | |

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

529 | static APInt getMaxValue(unsigned numBits) { |

530 | return getAllOnesValue(numBits); |

531 | } |

532 | |

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

534 | static APInt getSignedMaxValue(unsigned numBits) { |

535 | APInt API = getAllOnesValue(numBits); |

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

537 | return API; |

538 | } |

539 | |

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

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

542 | |

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

544 | static APInt getSignedMinValue(unsigned numBits) { |

545 | APInt API(numBits, 0); |

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

547 | return API; |

548 | } |

549 | |

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

551 | /// |

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

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

554 | static APInt getSignMask(unsigned BitWidth) { |

555 | return getSignedMinValue(BitWidth); |

556 | } |

557 | |

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

559 | /// |

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

561 | static APInt getAllOnesValue(unsigned numBits) { |

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

563 | } |

564 | |

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

566 | /// |

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

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

569 | |

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

571 | /// |

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

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

574 | /// |

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

576 | APInt getHiBits(unsigned numBits) const; |

577 | |

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

579 | /// |

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

581 | /// the high bits. |

582 | /// |

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

584 | APInt getLoBits(unsigned numBits) const; |

585 | |

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

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

588 | APInt Res(numBits, 0); |

589 | Res.setBit(BitNo); |

590 | return Res; |

591 | } |

592 | |

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

594 | /// |

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

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

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

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

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

600 | /// |

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

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

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

604 | /// |

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

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

607 | APInt Res(numBits, 0); |

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

609 | return Res; |

610 | } |

611 | |

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

613 | /// |

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

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

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

617 | /// 0xFFFFF000. |

618 | /// |

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

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

621 | /// |

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

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

624 | APInt Res(numBits, 0); |

625 | Res.setBitsFrom(loBit); |

626 | return Res; |

627 | } |

628 | |

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

630 | /// |

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

632 | /// |

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

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

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

636 | APInt Res(numBits, 0); |

637 | Res.setHighBits(hiBitsSet); |

638 | return Res; |

639 | } |

640 | |

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

642 | /// |

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

644 | /// |

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

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

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

648 | APInt Res(numBits, 0); |

649 | Res.setLowBits(loBitsSet); |

650 | return Res; |

651 | } |

652 | |

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

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

655 | |

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

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

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

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

660 | return I1 == I2; |

661 | |

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

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

664 | |

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

666 | } |

667 | |

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

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

670 | |

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

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

673 | /// conversions. |

674 | const uint64_t *getRawData() const { |

675 | if (isSingleWord()) |

676 | return &U.VAL; |

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

678 | } |

679 | |

680 | /// @} |

681 | /// \name Unary Operators |

682 | /// @{ |

683 | |

684 | /// Postfix increment operator. |

685 | /// |

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

687 | /// |

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

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

690 | APInt API(*this); |

691 | ++(*this); |

692 | return API; |

693 | } |

694 | |

695 | /// Prefix increment operator. |

696 | /// |

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

698 | APInt &operator++(); |

699 | |

700 | /// Postfix decrement operator. |

701 | /// |

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

703 | /// |

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

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

706 | APInt API(*this); |

707 | --(*this); |

708 | return API; |

709 | } |

710 | |

711 | /// Prefix decrement operator. |

712 | /// |

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

714 | APInt &operator--(); |

715 | |

716 | /// Logical negation operator. |

717 | /// |

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

719 | /// |

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

721 | bool operator!() const { |

722 | if (isSingleWord()) |

723 | return U.VAL == 0; |

724 | return countLeadingZerosSlowCase() == BitWidth; |

725 | } |

726 | |

727 | /// @} |

728 | /// \name Assignment Operators |

729 | /// @{ |

730 | |

731 | /// Copy assignment operator. |

732 | /// |

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

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

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

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

737 | U.VAL = RHS.U.VAL; |

738 | BitWidth = RHS.BitWidth; |

739 | return clearUnusedBits(); |

740 | } |

741 | |

742 | AssignSlowCase(RHS); |

743 | return *this; |

744 | } |

745 | |

746 | /// Move assignment operator. |

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

748 | #ifdef _MSC_VER |

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

750 | if (this == &that) |

751 | return *this; |

752 | #endif |

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

754 | if (!isSingleWord()) |

755 | delete[] U.pVal; |

756 | |

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

758 | // as modified. |

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

760 | |

761 | BitWidth = that.BitWidth; |

762 | that.BitWidth = 0; |

763 | |

764 | return *this; |

765 | } |

766 | |

767 | /// Assignment operator. |

768 | /// |

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

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

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

772 | /// |

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

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

775 | if (isSingleWord()) { |

776 | U.VAL = RHS; |

777 | clearUnusedBits(); |

778 | } else { |

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

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

781 | } |

782 | return *this; |

783 | } |

784 | |

785 | /// Bitwise AND assignment operator. |

786 | /// |

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

788 | /// assigned to *this. |

789 | /// |

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

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

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

793 | if (isSingleWord()) |

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

795 | else |

796 | AndAssignSlowCase(RHS); |

797 | return *this; |

798 | } |

799 | |

800 | /// Bitwise AND assignment operator. |

801 | /// |

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

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

804 | /// the LHS. |

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

806 | if (isSingleWord()) { |

807 | U.VAL &= RHS; |

808 | return *this; |

809 | } |

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

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

812 | return *this; |

813 | } |

814 | |

815 | /// Bitwise OR assignment operator. |

816 | /// |

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

818 | /// assigned *this; |

819 | /// |

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

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

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

823 | if (isSingleWord()) |

824 | U.VAL |= RHS.U.VAL; |

825 | else |

826 | OrAssignSlowCase(RHS); |

827 | return *this; |

828 | } |

829 | |

830 | /// Bitwise OR assignment operator. |

831 | /// |

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

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

834 | /// the LHS. |

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

836 | if (isSingleWord()) { |

837 | U.VAL |= RHS; |

838 | clearUnusedBits(); |

839 | } else { |

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

841 | } |

842 | return *this; |

843 | } |

844 | |

845 | /// Bitwise XOR assignment operator. |

846 | /// |

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

848 | /// assigned to *this. |

849 | /// |

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

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

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

853 | if (isSingleWord()) |

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

855 | else |

856 | XorAssignSlowCase(RHS); |

857 | return *this; |

858 | } |

859 | |

860 | /// Bitwise XOR assignment operator. |

861 | /// |

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

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

864 | /// the LHS. |

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

866 | if (isSingleWord()) { |

867 | U.VAL ^= RHS; |

868 | clearUnusedBits(); |

869 | } else { |

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

871 | } |

872 | return *this; |

873 | } |

874 | |

875 | /// Multiplication assignment operator. |

876 | /// |

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

878 | /// |

879 | /// \returns *this |

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

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

882 | |

883 | /// Addition assignment operator. |

884 | /// |

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

886 | /// |

887 | /// \returns *this |

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

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

890 | |

891 | /// Subtraction assignment operator. |

892 | /// |

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

894 | /// |

895 | /// \returns *this |

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

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

898 | |

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

900 | /// |

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

902 | /// |

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

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

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

906 | if (isSingleWord()) { |

907 | if (ShiftAmt == BitWidth) |

908 | U.VAL = 0; |

909 | else |

910 | U.VAL <<= ShiftAmt; |

911 | return clearUnusedBits(); |

912 | } |

913 | shlSlowCase(ShiftAmt); |

914 | return *this; |

915 | } |

916 | |

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

918 | /// |

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

920 | /// |

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

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

923 | |

924 | /// @} |

925 | /// \name Binary Operators |

926 | /// @{ |

927 | |

928 | /// Multiplication operator. |

929 | /// |

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

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

932 | |

933 | /// Left logical shift operator. |

934 | /// |

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

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

937 | |

938 | /// Left logical shift operator. |

939 | /// |

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

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

942 | |

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

944 | /// |

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

946 | APInt ashr(unsigned ShiftAmt) const { |

947 | APInt R(*this); |

948 | R.ashrInPlace(ShiftAmt); |

949 | return R; |

950 | } |

951 | |

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

953 | void ashrInPlace(unsigned ShiftAmt) { |

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

955 | if (isSingleWord()) { |

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

957 | if (ShiftAmt == BitWidth) |

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

959 | else |

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

961 | clearUnusedBits(); |

962 | return; |

963 | } |

964 | ashrSlowCase(ShiftAmt); |

965 | } |

966 | |

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

968 | /// |

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

970 | APInt lshr(unsigned shiftAmt) const { |

971 | APInt R(*this); |

972 | R.lshrInPlace(shiftAmt); |

973 | return R; |

974 | } |

975 | |

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

977 | void lshrInPlace(unsigned ShiftAmt) { |

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

979 | if (isSingleWord()) { |

980 | if (ShiftAmt == BitWidth) |

981 | U.VAL = 0; |

982 | else |

983 | U.VAL >>= ShiftAmt; |

984 | return; |

985 | } |

986 | lshrSlowCase(ShiftAmt); |

987 | } |

988 | |

989 | /// Left-shift function. |

990 | /// |

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

992 | APInt shl(unsigned shiftAmt) const { |

993 | APInt R(*this); |

994 | R <<= shiftAmt; |

995 | return R; |

996 | } |

997 | |

998 | /// Rotate left by rotateAmt. |

999 | APInt rotl(unsigned rotateAmt) const; |

1000 | |

1001 | /// Rotate right by rotateAmt. |

1002 | APInt rotr(unsigned rotateAmt) const; |

1003 | |

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

1005 | /// |

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

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

1008 | APInt R(*this); |

1009 | R.ashrInPlace(ShiftAmt); |

1010 | return R; |

1011 | } |

1012 | |

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

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

1015 | |

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

1017 | /// |

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

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

1020 | APInt R(*this); |

1021 | R.lshrInPlace(ShiftAmt); |

1022 | return R; |

1023 | } |

1024 | |

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

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

1027 | |

1028 | /// Left-shift function. |

1029 | /// |

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

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

1032 | APInt R(*this); |

1033 | R <<= ShiftAmt; |

1034 | return R; |

1035 | } |

1036 | |

1037 | /// Rotate left by rotateAmt. |

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

1039 | |

1040 | /// Rotate right by rotateAmt. |

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

1042 | |

1043 | /// Unsigned division operation. |

1044 | /// |

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

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

1047 | /// |

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

1049 | /// zero. |

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

1051 | APInt udiv(uint64_t RHS) const; |

1052 | |

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

1054 | /// |

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

1056 | /// |

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

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

1059 | APInt sdiv(int64_t RHS) const; |

1060 | |

1061 | /// Unsigned remainder operation. |

1062 | /// |

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

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

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

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

1067 | /// is *this. |

1068 | /// |

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

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

1071 | uint64_t urem(uint64_t RHS) const; |

1072 | |

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

1074 | /// |

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

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

1077 | int64_t srem(int64_t RHS) const; |

1078 | |

1079 | /// Dual division/remainder interface. |

1080 | /// |

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

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

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

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

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

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

1087 | APInt &Remainder); |

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

1089 | uint64_t &Remainder); |

1090 | |

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

1092 | APInt &Remainder); |

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

1094 | int64_t &Remainder); |

1095 | |

1096 | // Operations that return overflow indicators. |

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

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

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

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

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

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

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

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

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

1106 | |

1107 | // Operations that saturate |

1108 | APInt sadd_sat(const APInt &RHS) const; |

1109 | APInt uadd_sat(const APInt &RHS) const; |

1110 | APInt ssub_sat(const APInt &RHS) const; |

1111 | APInt usub_sat(const APInt &RHS) const; |

1112 | |

1113 | /// Array-indexing support. |

1114 | /// |

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

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

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

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

1119 | } |

1120 | |

1121 | /// @} |

1122 | /// \name Comparison Operators |

1123 | /// @{ |

1124 | |

1125 | /// Equality operator. |

1126 | /// |

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

1128 | /// relationship. |

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

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

1131 | if (isSingleWord()) |

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

1133 | return EqualSlowCase(RHS); |

1134 | } |

1135 | |

1136 | /// Equality operator. |

1137 | /// |

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

1139 | /// relationship. |

1140 | /// |

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

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

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

1144 | } |

1145 | |

1146 | /// Equality comparison. |

1147 | /// |

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

1149 | /// relationship. |

1150 | /// |

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

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

1153 | |

1154 | /// Inequality operator. |

1155 | /// |

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

1157 | /// relationship. |

1158 | /// |

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

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

1161 | |

1162 | /// Inequality operator. |

1163 | /// |

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

1165 | /// relationship. |

1166 | /// |

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

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

1169 | |

1170 | /// Inequality comparison |

1171 | /// |

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

1173 | /// relationship. |

1174 | /// |

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

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

1177 | |

1178 | /// Unsigned less than comparison |

1179 | /// |

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

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

1182 | /// |

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

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

1185 | |

1186 | /// Unsigned less than comparison |

1187 | /// |

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

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

1190 | /// |

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

1192 | bool ult(uint64_t RHS) const { |

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

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

1195 | } |

1196 | |

1197 | /// Signed less than comparison |

1198 | /// |

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

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

1201 | /// |

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

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

1204 | |

1205 | /// Signed less than comparison |

1206 | /// |

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

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

1209 | /// |

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

1211 | bool slt(int64_t RHS) const { |

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

1213 | : getSExtValue() < RHS; |

1214 | } |

1215 | |

1216 | /// Unsigned less or equal comparison |

1217 | /// |

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

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

1220 | /// |

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

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

1223 | |

1224 | /// Unsigned less or equal comparison |

1225 | /// |

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

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

1228 | /// |

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

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

1231 | |

1232 | /// Signed less or equal comparison |

1233 | /// |

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

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

1236 | /// |

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

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

1239 | |

1240 | /// Signed less or equal comparison |

1241 | /// |

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

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

1244 | /// |

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

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

1247 | |

1248 | /// Unsigned greather than comparison |

1249 | /// |

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

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

1252 | /// |

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

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

1255 | |

1256 | /// Unsigned greater than comparison |

1257 | /// |

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

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

1260 | /// |

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

1262 | bool ugt(uint64_t RHS) const { |

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

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

1265 | } |

1266 | |

1267 | /// Signed greather than comparison |

1268 | /// |

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

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

1271 | /// |

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

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

1274 | |

1275 | /// Signed greater than comparison |

1276 | /// |

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

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

1279 | /// |

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

1281 | bool sgt(int64_t RHS) const { |

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

1283 | : getSExtValue() > RHS; |

1284 | } |

1285 | |

1286 | /// Unsigned greater or equal comparison |

1287 | /// |

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

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

1290 | /// |

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

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

1293 | |

1294 | /// Unsigned greater or equal comparison |

1295 | /// |

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

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

1298 | /// |

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

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

1301 | |

1302 | /// Signed greater or equal comparison |

1303 | /// |

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

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

1306 | /// |

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

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

1309 | |

1310 | /// Signed greater or equal comparison |

1311 | /// |

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

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

1314 | /// |

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

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

1317 | |

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

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

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

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

1322 | if (isSingleWord()) |

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

1324 | return intersectsSlowCase(RHS); |

1325 | } |

1326 | |

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

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

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

1330 | if (isSingleWord()) |

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

1332 | return isSubsetOfSlowCase(RHS); |

1333 | } |

1334 | |

1335 | /// @} |

1336 | /// \name Resizing Operators |

1337 | /// @{ |

1338 | |

1339 | /// Truncate to new width. |

1340 | /// |

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

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

1343 | APInt trunc(unsigned width) const; |

1344 | |

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

1346 | /// |

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

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

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

1350 | /// current width. |

1351 | APInt sext(unsigned width) const; |

1352 | |

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

1354 | /// |

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

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

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

1358 | APInt zext(unsigned width) const; |

1359 | |

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

1361 | /// |

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

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

1364 | APInt sextOrTrunc(unsigned width) const; |

1365 | |

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

1367 | /// |

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

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

1370 | APInt zextOrTrunc(unsigned width) const; |

1371 | |

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

1373 | /// |

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

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

1376 | APInt sextOrSelf(unsigned width) const; |

1377 | |

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

1379 | /// |

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

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

1382 | APInt zextOrSelf(unsigned width) const; |

1383 | |

1384 | /// @} |

1385 | /// \name Bit Manipulation Operators |

1386 | /// @{ |

1387 | |

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

1389 | void setAllBits() { |

1390 | if (isSingleWord()) |

1391 | U.VAL = WORDTYPE_MAX; |

1392 | else |

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

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

1395 | // Clear the unused ones |

1396 | clearUnusedBits(); |

1397 | } |

1398 | |

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

1400 | /// |

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

1402 | void setBit(unsigned BitPosition) { |

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

1404 | WordType Mask = maskBit(BitPosition); |

1405 | if (isSingleWord()) |

1406 | U.VAL |= Mask; |

1407 | else |

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

1409 | } |

1410 | |

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

1412 | void setSignBit() { |

1413 | setBit(BitWidth - 1); |

1414 | } |

1415 | |

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

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

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

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

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

1421 | if (loBit == hiBit) |

1422 | return; |

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

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

1425 | mask <<= loBit; |

1426 | if (isSingleWord()) |

1427 | U.VAL |= mask; |

1428 | else |

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

1430 | } else { |

1431 | setBitsSlowCase(loBit, hiBit); |

1432 | } |

1433 | } |

1434 | |

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

1436 | void setBitsFrom(unsigned loBit) { |

1437 | return setBits(loBit, BitWidth); |

1438 | } |

1439 | |

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

1441 | void setLowBits(unsigned loBits) { |

1442 | return setBits(0, loBits); |

1443 | } |

1444 | |

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

1446 | void setHighBits(unsigned hiBits) { |

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

1448 | } |

1449 | |

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

1451 | void clearAllBits() { |

1452 | if (isSingleWord()) |

1453 | U.VAL = 0; |

1454 | else |

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

1456 | } |

1457 | |

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

1459 | /// |

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

1461 | void clearBit(unsigned BitPosition) { |

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

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

1464 | if (isSingleWord()) |

1465 | U.VAL &= Mask; |

1466 | else |

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

1468 | } |

1469 | |

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

1471 | void clearSignBit() { |

1472 | clearBit(BitWidth - 1); |

1473 | } |

1474 | |

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

1476 | void flipAllBits() { |

1477 | if (isSingleWord()) { |

1478 | U.VAL ^= WORDTYPE_MAX; |

1479 | clearUnusedBits(); |

1480 | } else { |

1481 | flipAllBitsSlowCase(); |

1482 | } |

1483 | } |

1484 | |

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

1486 | /// |

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

1488 | /// as "bitPosition". |

1489 | void flipBit(unsigned bitPosition); |

1490 | |

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

1492 | void negate() { |

1493 | flipAllBits(); |

1494 | ++(*this); |

1495 | } |

1496 | |

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

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

1499 | |

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

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

1502 | |

1503 | /// @} |

1504 | /// \name Value Characterization Functions |

1505 | /// @{ |

1506 | |

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

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

1509 | |

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

1511 | /// |

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

1513 | /// |

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

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

1516 | |

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

1518 | /// |

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

1520 | /// |

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

1522 | /// width. |

1523 | static unsigned getNumWords(unsigned BitWidth) { |

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

1525 | } |

1526 | |

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

1528 | /// |

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

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

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

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

1533 | |

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

1535 | /// |

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

1537 | /// the APInt. |

1538 | unsigned getActiveWords() const { |

1539 | unsigned numActiveBits = getActiveBits(); |

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

1541 | } |

1542 | |

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

1544 | /// |

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

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

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

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

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

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

1551 | unsigned getMinSignedBits() const { |

1552 | if (isNegative()) |

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

1554 | return getActiveBits() + 1; |

1555 | } |

1556 | |

1557 | /// Get zero extended value |

1558 | /// |

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

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

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

1562 | uint64_t getZExtValue() const { |

1563 | if (isSingleWord()) |

1564 | return U.VAL; |

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

1566 | return U.pVal[0]; |

1567 | } |

1568 | |

1569 | /// Get sign extended value |

1570 | /// |

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

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

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

1574 | int64_t getSExtValue() const { |

1575 | if (isSingleWord()) |

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

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

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

1579 | } |

1580 | |

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

1582 | /// |

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

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

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

1586 | |

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

1588 | /// MathExtras.h. |

1589 | /// |

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

1591 | /// one bit. |

1592 | /// |

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

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

1595 | unsigned countLeadingZeros() const { |

1596 | if (isSingleWord()) { |

1597 | unsigned unusedBits = APINT_BITS_PER_WORD - BitWidth; |

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

1599 | } |

1600 | return countLeadingZerosSlowCase(); |

1601 | } |

1602 | |

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

1604 | /// |

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

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

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

1608 | /// |

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

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

1611 | unsigned countLeadingOnes() const { |

1612 | if (isSingleWord()) |

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

1614 | return countLeadingOnesSlowCase(); |

1615 | } |

1616 | |

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

1618 | /// sign bit. |

1619 | unsigned getNumSignBits() const { |

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

1621 | } |

1622 | |

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

1624 | /// |

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

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

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

1628 | /// |

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

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

1631 | unsigned countTrailingZeros() const { |

1632 | if (isSingleWord()) |

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

1634 | return countTrailingZerosSlowCase(); |

1635 | } |

1636 | |

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

1638 | /// |

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

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

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

1642 | /// |

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

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

1645 | unsigned countTrailingOnes() const { |

1646 | if (isSingleWord()) |

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

1648 | return countTrailingOnesSlowCase(); |

1649 | } |

1650 | |

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

1652 | /// |

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

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

1655 | /// |

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

1657 | unsigned countPopulation() const { |

1658 | if (isSingleWord()) |

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

1660 | return countPopulationSlowCase(); |

1661 | } |

1662 | |

1663 | /// @} |

1664 | /// \name Conversion Functions |

1665 | /// @{ |

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

1667 | |

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

1669 | /// SmallString. |

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

1671 | bool formatAsCLiteral = false) const; |

1672 | |

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

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

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

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

1677 | } |

1678 | |

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

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

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

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

1683 | } |

1684 | |

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

1686 | /// |

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

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

1689 | /// for the string. |

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

1691 | |

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

1693 | APInt byteSwap() const; |

1694 | |

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

1696 | /// Value. |

1697 | APInt reverseBits() const; |

1698 | |

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

1700 | double roundToDouble(bool isSigned) const; |

1701 | |

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

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

1704 | |

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

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

1707 | |

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

1709 | /// |

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

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

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

1713 | double bitsToDouble() const { |

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

1715 | } |

1716 | |

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

1718 | /// |

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

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

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

1722 | float bitsToFloat() const { |

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

1724 | } |

1725 | |

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

1727 | /// |

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

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

1730 | static APInt doubleToBits(double V) { |

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

1732 | } |

1733 | |

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

1735 | /// |

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

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

1738 | static APInt floatToBits(float V) { |

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

1740 | } |

1741 | |

1742 | /// @} |

1743 | /// \name Mathematics Operations |

1744 | /// @{ |

1745 | |

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

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

1748 | |

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

1750 | unsigned ceilLogBase2() const { |

1751 | APInt temp(*this); |

1752 | --temp; |

1753 | return temp.getActiveBits(); |

1754 | } |

1755 | |

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

1757 | /// |

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

1759 | /// |

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

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

1762 | /// |

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

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

1765 | unsigned nearestLogBase2() const { |

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

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

1768 | // UINT32_MAX. |

1769 | if (BitWidth == 1) |

1770 | return U.VAL - 1; |

1771 | |

1772 | // Handle the zero case. |

1773 | if (isNullValue()) |

1774 | return UINT32_MAX; |

1775 | |

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

1777 | // |

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

1779 | // |

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

1781 | unsigned lg = logBase2(); |

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

1783 | } |

1784 | |

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

1786 | /// otherwise |

1787 | int32_t exactLogBase2() const { |

1788 | if (!isPowerOf2()) |

1789 | return -1; |

1790 | return logBase2(); |

1791 | } |

1792 | |

1793 | /// Compute the square root |

1794 | APInt sqrt() const; |

1795 | |

1796 | /// Get the absolute value; |

1797 | /// |

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

1799 | APInt abs() const { |

1800 | if (isNegative()) |

1801 | return -(*this); |

1802 | return *this; |

1803 | } |

1804 | |

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

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

1807 | |

1808 | /// @} |

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

1810 | /// @{ |

1811 | |

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

1813 | struct ms; |

1814 | ms magic() const; |

1815 | |

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

1817 | struct mu; |

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

1819 | |

1820 | /// @} |

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

1822 | /// @{ |

1823 | |

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

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

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

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

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

1829 | |

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

1831 | /// out higher parts. |

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

1833 | |

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

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

1836 | |

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

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

1839 | |

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

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

1842 | |

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

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

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

1846 | /// zero-filled. |

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

1848 | const WordType *, unsigned srcBits, |

1849 | unsigned srcLSB); |

1850 | |

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

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

1853 | |

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

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

1856 | |

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

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

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

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

1861 | |

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

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

1864 | |

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

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

1867 | WordType carry, unsigned); |

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

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

1870 | |

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

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

1873 | WordType carry, unsigned); |

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

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

1876 | |

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

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

1879 | /// |

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

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

1882 | /// |

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

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

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

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

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

1888 | WordType multiplier, WordType carry, |

1889 | unsigned srcParts, unsigned dstParts, |

1890 | bool add); |

1891 | |

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

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

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

1895 | /// operands. |

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

1897 | unsigned); |

1898 | |

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

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

1901 | static void tcFullMultiply(WordType *, const WordType *, |

1902 | const WordType *, unsigned, unsigned); |

1903 | |

1904 | /// If RHS is zero LHS and REMAINDER are left unchanged, return one. |

1905 | /// Otherwise set LHS to LHS / RHS with the fractional part discarded, set |

1906 | /// REMAINDER to the remainder, return zero. i.e. |

1907 | /// |

1908 | /// OLD_LHS = RHS * LHS + REMAINDER |

1909 | /// |

1910 | /// SCRATCH is a bignum of the same size as the operands and result for use by |

1911 | /// the routine; its contents need not be initialized and are destroyed. LHS, |

1912 | /// REMAINDER and SCRATCH must be distinct. |

1913 | static int tcDivide(WordType *lhs, const WordType *rhs, |

1914 | WordType *remainder, WordType *scratch, |

1915 | unsigned parts); |

1916 | |

1917 | /// Shift a bignum left Count bits. Shifted in bits are zero. There are no |

1918 | /// restrictions on Count. |

1919 | static void tcShiftLeft(WordType *, unsigned Words, unsigned Count); |

1920 | |

1921 | /// Shift a bignum right Count bits. Shifted in bits are zero. There are no |

1922 | /// restrictions on Count. |

1923 | static void tcShiftRight(WordType *, unsigned Words, unsigned Count); |

1924 | |

1925 | /// The obvious AND, OR and XOR and complement operations. |

1926 | static void tcAnd(WordType *, const WordType *, unsigned); |

1927 | static void tcOr(WordType *, const WordType *, unsigned); |

1928 | static void tcXor(WordType *, const WordType *, unsigned); |

1929 | static void tcComplement(WordType *, unsigned); |

1930 | |

1931 | /// Comparison (unsigned) of two bignums. |

1932 | static int tcCompare(const WordType *, const WordType *, unsigned); |

1933 | |

1934 | /// Increment a bignum in-place. Return the carry flag. |

1935 | static WordType tcIncrement(WordType *dst, unsigned parts) { |

1936 | return tcAddPart(dst, 1, parts); |

1937 | } |

1938 | |

1939 | /// Decrement a bignum in-place. Return the borrow flag. |

1940 | static WordType tcDecrement(WordType *dst, unsigned parts) { |

1941 | return tcSubtractPart(dst, 1, parts); |

1942 | } |

1943 | |

1944 | /// Set the least significant BITS and clear the rest. |

1945 | static void tcSetLeastSignificantBits(WordType *, unsigned, unsigned bits); |

1946 | |

1947 | /// debug method |

1948 | void dump() const; |

1949 | |

1950 | /// @} |

1951 | }; |

1952 | |

1953 | /// Magic data for optimising signed division by a constant. |

1954 | struct APInt::ms { |

1955 | APInt m; ///< magic number |

1956 | unsigned s; ///< shift amount |

1957 | }; |

1958 | |

1959 | /// Magic data for optimising unsigned division by a constant. |

1960 | struct APInt::mu { |

1961 | APInt m; ///< magic number |

1962 | bool a; ///< add indicator |

1963 | unsigned s; ///< shift amount |

1964 | }; |

1965 | |

1966 | inline bool operator==(uint64_t V1, const APInt &V2) { return V2 == V1; } |

1967 | |

1968 | inline bool operator!=(uint64_t V1, const APInt &V2) { return V2 != V1; } |

1969 | |

1970 | /// Unary bitwise complement operator. |

1971 | /// |

1972 | /// \returns an APInt that is the bitwise complement of \p v. |

1973 | inline APInt operator~(APInt v) { |

1974 | v.flipAllBits(); |

1975 | return v; |

1976 | } |

1977 | |

1978 | inline APInt operator&(APInt a, const APInt &b) { |

1979 | a &= b; |

1980 | return a; |

1981 | } |

1982 | |

1983 | inline APInt operator&(const APInt &a, APInt &&b) { |

1984 | b &= a; |

1985 | return std::move(b); |

1986 | } |

1987 | |

1988 | inline APInt operator&(APInt a, uint64_t RHS) { |

1989 | a &= RHS; |

1990 | return a; |

1991 | } |

1992 | |

1993 | inline APInt operator&(uint64_t LHS, APInt b) { |

1994 | b &= LHS; |

1995 | return b; |

1996 | } |

1997 | |

1998 | inline APInt operator|(APInt a, const APInt &b) { |

1999 | a |= b; |

2000 | return a; |

2001 | } |

2002 | |

2003 | inline APInt operator|(const APInt &a, APInt &&b) { |

2004 | b |= a; |

2005 | return std::move(b); |

2006 | } |

2007 | |

2008 | inline APInt operator|(APInt a, uint64_t RHS) { |

2009 | a |= RHS; |

2010 | return a; |

2011 | } |

2012 | |

2013 | inline APInt operator|(uint64_t LHS, APInt b) { |

2014 | b |= LHS; |

2015 | return b; |

2016 | } |

2017 | |

2018 | inline APInt operator^(APInt a, const APInt &b) { |

2019 | a ^= b; |

2020 | return a; |

2021 | } |

2022 | |

2023 | inline APInt operator^(const APInt &a, APInt &&b) { |

2024 | b ^= a; |

2025 | return std::move(b); |

2026 | } |

2027 | |

2028 | inline APInt operator^(APInt a, uint64_t RHS) { |

2029 | a ^= RHS; |

2030 | return a; |

2031 | } |

2032 | |

2033 | inline APInt operator^(uint64_t LHS, APInt b) { |

2034 | b ^= LHS; |

2035 | return b; |

2036 | } |

2037 | |

2038 | inline raw_ostream &operator<<(raw_ostream &OS, const APInt &I) { |

2039 | I.print(OS, true); |

2040 | return OS; |

2041 | } |

2042 | |

2043 | inline APInt operator-(APInt v) { |

2044 | v.negate(); |

2045 | return v; |

2046 | } |

2047 | |

2048 | inline APInt operator+(APInt a, const APInt &b) { |

2049 | a += b; |

2050 | return a; |

2051 | } |

2052 | |

2053 | inline APInt operator+(const APInt &a, APInt &&b) { |

2054 | b += a; |

2055 | return std::move(b); |

2056 | } |

2057 | |

2058 | inline APInt operator+(APInt a, uint64_t RHS) { |

2059 | a += RHS; |

2060 | return a; |

2061 | } |

2062 | |

2063 | inline APInt operator+(uint64_t LHS, APInt b) { |

2064 | b += LHS; |

2065 | return b; |

2066 | } |

2067 | |

2068 | inline APInt operator-(APInt a, const APInt &b) { |

2069 | a -= b; |

2070 | return a; |

2071 | } |

2072 | |

2073 | inline APInt operator-(const APInt &a, APInt &&b) { |

2074 | b.negate(); |

2075 | b += a; |

2076 | return std::move(b); |

2077 | } |

2078 | |

2079 | inline APInt operator-(APInt a, uint64_t RHS) { |

2080 | a -= RHS; |

2081 | return a; |

2082 | } |

2083 | |

2084 | inline APInt operator-(uint64_t LHS, APInt b) { |

2085 | b.negate(); |

2086 | b += LHS; |

2087 | return b; |

2088 | } |

2089 | |

2090 | inline APInt operator*(APInt a, uint64_t RHS) { |

2091 | a *= RHS; |

2092 | return a; |

2093 | } |

2094 | |

2095 | inline APInt operator*(uint64_t LHS, APInt b) { |

2096 | b *= LHS; |

2097 | return b; |

2098 | } |

2099 | |

2100 | |

2101 | namespace APIntOps { |

2102 | |

2103 | /// Determine the smaller of two APInts considered to be signed. |

2104 | inline const APInt &smin(const APInt &A, const APInt &B) { |

2105 | return A.slt(B) ? A : B; |

2106 | } |

2107 | |

2108 | /// Determine the larger of two APInts considered to be signed. |

2109 | inline const APInt &smax(const APInt &A, const APInt &B) { |

2110 | return A.sgt(B) ? A : B; |

2111 | } |

2112 | |

2113 | /// Determine the smaller of two APInts considered to be signed. |

2114 | inline const APInt &umin(const APInt &A, const APInt &B) { |

2115 | return A.ult(B) ? A : B; |

2116 | } |

2117 | |

2118 | /// Determine the larger of two APInts considered to be unsigned. |

2119 | inline const APInt &umax(const APInt &A, const APInt &B) { |

2120 | return A.ugt(B) ? A : B; |

2121 | } |

2122 | |

2123 | /// Compute GCD of two unsigned APInt values. |

2124 | /// |

2125 | /// This function returns the greatest common divisor of the two APInt values |

2126 | /// using Stein's algorithm. |

2127 | /// |

2128 | /// \returns the greatest common divisor of A and B. |

2129 | APInt GreatestCommonDivisor(APInt A, APInt B); |

2130 | |

2131 | /// Converts the given APInt to a double value. |

2132 | /// |

2133 | /// Treats the APInt as an unsigned value for conversion purposes. |

2134 | inline double RoundAPIntToDouble(const APInt &APIVal) { |

2135 | return APIVal.roundToDouble(); |

2136 | } |

2137 | |

2138 | /// Converts the given APInt to a double value. |

2139 | /// |

2140 | /// Treats the APInt as a signed value for conversion purposes. |

2141 | inline double RoundSignedAPIntToDouble(const APInt &APIVal) { |

2142 | return APIVal.signedRoundToDouble(); |

2143 | } |

2144 | |

2145 | /// Converts the given APInt to a float vlalue. |

2146 | inline float RoundAPIntToFloat(const APInt &APIVal) { |

2147 | return float(RoundAPIntToDouble(APIVal)); |

2148 | } |

2149 | |

2150 | /// Converts the given APInt to a float value. |

2151 | /// |

2152 | /// Treast the APInt as a signed value for conversion purposes. |

2153 | inline float RoundSignedAPIntToFloat(const APInt &APIVal) { |

2154 | return float(APIVal.signedRoundToDouble()); |

2155 | } |

2156 | |

2157 | /// Converts the given double value into a APInt. |

2158 | /// |

2159 | /// This function convert a double value to an APInt value. |

2160 | APInt RoundDoubleToAPInt(double Double, unsigned width); |

2161 | |

2162 | /// Converts a float value into a APInt. |

2163 | /// |

2164 | /// Converts a float value into an APInt value. |

2165 | inline APInt RoundFloatToAPInt(float Float, unsigned width) { |

2166 | return RoundDoubleToAPInt(double(Float), width); |

2167 | } |

2168 | |

2169 | /// Return A unsign-divided by B, rounded by the given rounding mode. |

2170 | APInt RoundingUDiv(const APInt &A, const APInt &B, APInt::Rounding RM); |

2171 | |

2172 | /// Return A sign-divided by B, rounded by the given rounding mode. |

2173 | APInt RoundingSDiv(const APInt &A, const APInt &B, APInt::Rounding RM); |

2174 | |

2175 | /// Let q(n) = An^2 + Bn + C, and BW = bit width of the value range |

2176 | /// (e.g. 32 for i32). |

2177 | /// This function finds the smallest number n, such that |

2178 | /// (a) n >= 0 and q(n) = 0, or |

2179 | /// (b) n >= 1 and q(n-1) and q(n), when evaluated in the set of all |

2180 | /// integers, belong to two different intervals [Rk, Rk+R), |

2181 | /// where R = 2^BW, and k is an integer. |

2182 | /// The idea here is to find when q(n) "overflows" 2^BW, while at the |

2183 | /// same time "allowing" subtraction. In unsigned modulo arithmetic a |

2184 | /// subtraction (treated as addition of negated numbers) would always |

2185 | /// count as an overflow, but here we want to allow values to decrease |

2186 | /// and increase as long as they are within the same interval. |

2187 | /// Specifically, adding of two negative numbers should not cause an |

2188 | /// overflow (as long as the magnitude does not exceed the bith width). |

2189 | /// On the other hand, given a positive number, adding a negative |

2190 | /// number to it can give a negative result, which would cause the |

2191 | /// value to go from [-2^BW, 0) to [0, 2^BW). In that sense, zero is |

2192 | /// treated as a special case of an overflow. |

2193 | /// |

2194 | /// This function returns None if after finding k that minimizes the |

2195 | /// positive solution to q(n) = kR, both solutions are contained between |

2196 | /// two consecutive integers. |

2197 | /// |

2198 | /// There are cases where q(n) > T, and q(n+1) < T (assuming evaluation |

2199 | /// in arithmetic modulo 2^BW, and treating the values as signed) by the |

2200 | /// virtue of *signed* overflow. This function will *not* find such an n, |

2201 | /// however it may find a value of n satisfying the inequalities due to |

2202 | /// an *unsigned* overflow (if the values are treated as unsigned). |

2203 | /// To find a solution for a signed overflow, treat it as a problem of |

2204 | /// finding an unsigned overflow with a range with of BW-1. |

2205 | /// |

2206 | /// The returned value may have a different bit width from the input |

2207 | /// coefficients. |

2208 | Optional<APInt> SolveQuadraticEquationWrap(APInt A, APInt B, APInt C, |

2209 | unsigned RangeWidth); |

2210 | } // End of APIntOps namespace |

2211 | |

2212 | // See friend declaration above. This additional declaration is required in |

2213 | // order to compile LLVM with IBM xlC compiler. |

2214 | hash_code hash_value(const APInt &Arg); |

2215 | } // End of llvm namespace |

2216 | |

2217 | #endif |

2218 |