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 <optional> 24 #include <utility> 25 26 namespace llvm { 27 class FoldingSetNodeID; 28 class StringRef; 29 class hash_code; 30 class raw_ostream; 31 struct Align; 32 33 template <typename T> class SmallVectorImpl; 34 template <typename T> class ArrayRef; 35 template <typename T, typename Enable> struct DenseMapInfo; 36 37 class APInt; 38 39 inline APInt operator-(APInt); 40 41 //===----------------------------------------------------------------------===// 42 // APInt Class 43 //===----------------------------------------------------------------------===// 44 45 /// Class for arbitrary precision integers. 46 /// 47 /// APInt is a functional replacement for common case unsigned integer type like 48 /// "unsigned", "unsigned long" or "uint64_t", but also allows non-byte-width 49 /// integer sizes and large integer value types such as 3-bits, 15-bits, or more 50 /// than 64-bits of precision. APInt provides a variety of arithmetic operators 51 /// and methods to manipulate integer values of any bit-width. It supports both 52 /// the typical integer arithmetic and comparison operations as well as bitwise 53 /// manipulation. 54 /// 55 /// The class has several invariants worth noting: 56 /// * All bit, byte, and word positions are zero-based. 57 /// * Once the bit width is set, it doesn't change except by the Truncate, 58 /// SignExtend, or ZeroExtend operations. 59 /// * All binary operators must be on APInt instances of the same bit width. 60 /// Attempting to use these operators on instances with different bit 61 /// widths will yield an assertion. 62 /// * The value is stored canonically as an unsigned value. For operations 63 /// where it makes a difference, there are both signed and unsigned variants 64 /// of the operation. For example, sdiv and udiv. However, because the bit 65 /// widths must be the same, operations such as Mul and Add produce the same 66 /// results regardless of whether the values are interpreted as signed or 67 /// not. 68 /// * In general, the class tries to follow the style of computation that LLVM 69 /// uses in its IR. This simplifies its use for LLVM. 70 /// * APInt supports zero-bit-width values, but operations that require bits 71 /// are not defined on it (e.g. you cannot ask for the sign of a zero-bit 72 /// integer). This means that operations like zero extension and logical 73 /// shifts are defined, but sign extension and ashr is not. Zero bit values 74 /// compare and hash equal to themselves, and countLeadingZeros returns 0. 75 /// 76 class [[nodiscard]] APInt { 77 public: 78 typedef uint64_t WordType; 79 80 /// This enum is used to hold the constants we needed for APInt. 81 enum : unsigned { 82 /// Byte size of a word. 83 APINT_WORD_SIZE = sizeof(WordType), 84 /// Bits in a word. 85 APINT_BITS_PER_WORD = APINT_WORD_SIZE * CHAR_BIT 86 }; 87 88 enum class Rounding { 89 DOWN, 90 TOWARD_ZERO, 91 UP, 92 }; 93 94 static constexpr WordType WORDTYPE_MAX = ~WordType(0); 95 96 /// \name Constructors 97 /// @{ 98 99 /// Create a new APInt of numBits width, initialized as val. 100 /// 101 /// If isSigned is true then val is treated as if it were a signed value 102 /// (i.e. as an int64_t) and the appropriate sign extension to the bit width 103 /// will be done. Otherwise, no sign extension occurs (high order bits beyond 104 /// the range of val are zero filled). 105 /// 106 /// \param numBits the bit width of the constructed APInt 107 /// \param val the initial value of the APInt 108 /// \param isSigned how to treat signedness of val 109 APInt(unsigned numBits, uint64_t val, bool isSigned = false) 110 : BitWidth(numBits) { 111 if (isSingleWord()) { 112 U.VAL = val; 113 clearUnusedBits(); 114 } else { 115 initSlowCase(val, isSigned); 116 } 117 } 118 119 /// Construct an APInt of numBits width, initialized as bigVal[]. 120 /// 121 /// Note that bigVal.size() can be smaller or larger than the corresponding 122 /// bit width but any extraneous bits will be dropped. 123 /// 124 /// \param numBits the bit width of the constructed APInt 125 /// \param bigVal a sequence of words to form the initial value of the APInt 126 APInt(unsigned numBits, ArrayRef<uint64_t> bigVal); 127 128 /// Equivalent to APInt(numBits, ArrayRef<uint64_t>(bigVal, numWords)), but 129 /// deprecated because this constructor is prone to ambiguity with the 130 /// APInt(unsigned, uint64_t, bool) constructor. 131 /// 132 /// If this overload is ever deleted, care should be taken to prevent calls 133 /// from being incorrectly captured by the APInt(unsigned, uint64_t, bool) 134 /// constructor. 135 APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[]); 136 137 /// Construct an APInt from a string representation. 138 /// 139 /// This constructor interprets the string \p str in the given radix. The 140 /// interpretation stops when the first character that is not suitable for the 141 /// radix is encountered, or the end of the string. Acceptable radix values 142 /// are 2, 8, 10, 16, and 36. It is an error for the value implied by the 143 /// string to require more bits than numBits. 144 /// 145 /// \param numBits the bit width of the constructed APInt 146 /// \param str the string to be interpreted 147 /// \param radix the radix to use for the conversion 148 APInt(unsigned numBits, StringRef str, uint8_t radix); 149 150 /// Default constructor that creates an APInt with a 1-bit zero value. 151 explicit APInt() { U.VAL = 0; } 152 153 /// Copy Constructor. 154 APInt(const APInt &that) : BitWidth(that.BitWidth) { 155 if (isSingleWord()) 156 U.VAL = that.U.VAL; 157 else 158 initSlowCase(that); 159 } 160 161 /// Move Constructor. 162 APInt(APInt &&that) : BitWidth(that.BitWidth) { 163 memcpy(&U, &that.U, sizeof(U)); 164 that.BitWidth = 0; 165 } 166 167 /// Destructor. 168 ~APInt() { 169 if (needsCleanup()) 170 delete[] U.pVal; 171 } 172 173 /// @} 174 /// \name Value Generators 175 /// @{ 176 177 /// Get the '0' value for the specified bit-width. 178 static APInt getZero(unsigned numBits) { return APInt(numBits, 0); } 179 180 /// Return an APInt zero bits wide. 181 static APInt getZeroWidth() { return getZero(0); } 182 183 /// Gets maximum unsigned value of APInt for specific bit width. 184 static APInt getMaxValue(unsigned numBits) { return getAllOnes(numBits); } 185 186 /// Gets maximum signed value of APInt for a specific bit width. 187 static APInt getSignedMaxValue(unsigned numBits) { 188 APInt API = getAllOnes(numBits); 189 API.clearBit(numBits - 1); 190 return API; 191 } 192 193 /// Gets minimum unsigned value of APInt for a specific bit width. 194 static APInt getMinValue(unsigned numBits) { return APInt(numBits, 0); } 195 196 /// Gets minimum signed value of APInt for a specific bit width. 197 static APInt getSignedMinValue(unsigned numBits) { 198 APInt API(numBits, 0); 199 API.setBit(numBits - 1); 200 return API; 201 } 202 203 /// Get the SignMask for a specific bit width. 204 /// 205 /// This is just a wrapper function of getSignedMinValue(), and it helps code 206 /// readability when we want to get a SignMask. 207 static APInt getSignMask(unsigned BitWidth) { 208 return getSignedMinValue(BitWidth); 209 } 210 211 /// Return an APInt of a specified width with all bits set. 212 static APInt getAllOnes(unsigned numBits) { 213 return APInt(numBits, WORDTYPE_MAX, true); 214 } 215 216 /// Return an APInt with exactly one bit set in the result. 217 static APInt getOneBitSet(unsigned numBits, unsigned BitNo) { 218 APInt Res(numBits, 0); 219 Res.setBit(BitNo); 220 return Res; 221 } 222 223 /// Get a value with a block of bits set. 224 /// 225 /// Constructs an APInt value that has a contiguous range of bits set. The 226 /// bits from loBit (inclusive) to hiBit (exclusive) will be set. All other 227 /// bits will be zero. For example, with parameters(32, 0, 16) you would get 228 /// 0x0000FFFF. Please call getBitsSetWithWrap if \p loBit may be greater than 229 /// \p hiBit. 230 /// 231 /// \param numBits the intended bit width of the result 232 /// \param loBit the index of the lowest bit set. 233 /// \param hiBit the index of the highest bit set. 234 /// 235 /// \returns An APInt value with the requested bits set. 236 static APInt getBitsSet(unsigned numBits, unsigned loBit, unsigned hiBit) { 237 APInt Res(numBits, 0); 238 Res.setBits(loBit, hiBit); 239 return Res; 240 } 241 242 /// Wrap version of getBitsSet. 243 /// If \p hiBit is bigger than \p loBit, this is same with getBitsSet. 244 /// If \p hiBit is not bigger than \p loBit, the set bits "wrap". For example, 245 /// with parameters (32, 28, 4), you would get 0xF000000F. 246 /// If \p hiBit is equal to \p loBit, you would get a result with all bits 247 /// set. 248 static APInt getBitsSetWithWrap(unsigned numBits, unsigned loBit, 249 unsigned hiBit) { 250 APInt Res(numBits, 0); 251 Res.setBitsWithWrap(loBit, hiBit); 252 return Res; 253 } 254 255 /// Constructs an APInt value that has a contiguous range of bits set. The 256 /// bits from loBit (inclusive) to numBits (exclusive) will be set. All other 257 /// bits will be zero. For example, with parameters(32, 12) you would get 258 /// 0xFFFFF000. 259 /// 260 /// \param numBits the intended bit width of the result 261 /// \param loBit the index of the lowest bit to set. 262 /// 263 /// \returns An APInt value with the requested bits set. 264 static APInt getBitsSetFrom(unsigned numBits, unsigned loBit) { 265 APInt Res(numBits, 0); 266 Res.setBitsFrom(loBit); 267 return Res; 268 } 269 270 /// Constructs an APInt value that has the top hiBitsSet bits set. 271 /// 272 /// \param numBits the bitwidth of the result 273 /// \param hiBitsSet the number of high-order bits set in the result. 274 static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet) { 275 APInt Res(numBits, 0); 276 Res.setHighBits(hiBitsSet); 277 return Res; 278 } 279 280 /// Constructs an APInt value that has the bottom loBitsSet bits set. 281 /// 282 /// \param numBits the bitwidth of the result 283 /// \param loBitsSet the number of low-order bits set in the result. 284 static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet) { 285 APInt Res(numBits, 0); 286 Res.setLowBits(loBitsSet); 287 return Res; 288 } 289 290 /// Return a value containing V broadcasted over NewLen bits. 291 static APInt getSplat(unsigned NewLen, const APInt &V); 292 293 /// @} 294 /// \name Value Tests 295 /// @{ 296 297 /// Determine if this APInt just has one word to store value. 298 /// 299 /// \returns true if the number of bits <= 64, false otherwise. 300 bool isSingleWord() const { return BitWidth <= APINT_BITS_PER_WORD; } 301 302 /// Determine sign of this APInt. 303 /// 304 /// This tests the high bit of this APInt to determine if it is set. 305 /// 306 /// \returns true if this APInt is negative, false otherwise 307 bool isNegative() const { return (*this)[BitWidth - 1]; } 308 309 /// Determine if this APInt Value is non-negative (>= 0) 310 /// 311 /// This tests the high bit of the APInt to determine if it is unset. 312 bool isNonNegative() const { return !isNegative(); } 313 314 /// Determine if sign bit of this APInt is set. 315 /// 316 /// This tests the high bit of this APInt to determine if it is set. 317 /// 318 /// \returns true if this APInt has its sign bit set, false otherwise. 319 bool isSignBitSet() const { return (*this)[BitWidth - 1]; } 320 321 /// Determine if sign bit of this APInt is clear. 322 /// 323 /// This tests the high bit of this APInt to determine if it is clear. 324 /// 325 /// \returns true if this APInt has its sign bit clear, false otherwise. 326 bool isSignBitClear() const { return !isSignBitSet(); } 327 328 /// Determine if this APInt Value is positive. 329 /// 330 /// This tests if the value of this APInt is positive (> 0). Note 331 /// that 0 is not a positive value. 332 /// 333 /// \returns true if this APInt is positive. 334 bool isStrictlyPositive() const { return isNonNegative() && !isZero(); } 335 336 /// Determine if this APInt Value is non-positive (<= 0). 337 /// 338 /// \returns true if this APInt is non-positive. 339 bool isNonPositive() const { return !isStrictlyPositive(); } 340 341 /// Determine if this APInt Value only has the specified bit set. 342 /// 343 /// \returns true if this APInt only has the specified bit set. 344 bool isOneBitSet(unsigned BitNo) const { 345 return (*this)[BitNo] && popcount() == 1; 346 } 347 348 /// Determine if all bits are set. This is true for zero-width values. 349 bool isAllOnes() const { 350 if (BitWidth == 0) 351 return true; 352 if (isSingleWord()) 353 return U.VAL == WORDTYPE_MAX >> (APINT_BITS_PER_WORD - BitWidth); 354 return countTrailingOnesSlowCase() == BitWidth; 355 } 356 357 /// Determine if this value is zero, i.e. all bits are clear. 358 bool isZero() const { 359 if (isSingleWord()) 360 return U.VAL == 0; 361 return countLeadingZerosSlowCase() == BitWidth; 362 } 363 364 /// Determine if this is a value of 1. 365 /// 366 /// This checks to see if the value of this APInt is one. 367 bool isOne() const { 368 if (isSingleWord()) 369 return U.VAL == 1; 370 return countLeadingZerosSlowCase() == BitWidth - 1; 371 } 372 373 /// Determine if this is the largest unsigned value. 374 /// 375 /// This checks to see if the value of this APInt is the maximum unsigned 376 /// value for the APInt's bit width. 377 bool isMaxValue() const { return isAllOnes(); } 378 379 /// Determine if this is the largest signed value. 380 /// 381 /// This checks to see if the value of this APInt is the maximum signed 382 /// value for the APInt's bit width. 383 bool isMaxSignedValue() const { 384 if (isSingleWord()) { 385 assert(BitWidth && "zero width values not allowed"); 386 return U.VAL == ((WordType(1) << (BitWidth - 1)) - 1); 387 } 388 return !isNegative() && countTrailingOnesSlowCase() == BitWidth - 1; 389 } 390 391 /// Determine if this is the smallest unsigned value. 392 /// 393 /// This checks to see if the value of this APInt is the minimum unsigned 394 /// value for the APInt's bit width. 395 bool isMinValue() const { return isZero(); } 396 397 /// Determine if this is the smallest signed value. 398 /// 399 /// This checks to see if the value of this APInt is the minimum signed 400 /// value for the APInt's bit width. 401 bool isMinSignedValue() const { 402 if (isSingleWord()) { 403 assert(BitWidth && "zero width values not allowed"); 404 return U.VAL == (WordType(1) << (BitWidth - 1)); 405 } 406 return isNegative() && countTrailingZerosSlowCase() == BitWidth - 1; 407 } 408 409 /// Check if this APInt has an N-bits unsigned integer value. 410 bool isIntN(unsigned N) const { return getActiveBits() <= N; } 411 412 /// Check if this APInt has an N-bits signed integer value. 413 bool isSignedIntN(unsigned N) const { return getSignificantBits() <= N; } 414 415 /// Check if this APInt's value is a power of two greater than zero. 416 /// 417 /// \returns true if the argument APInt value is a power of two > 0. 418 bool isPowerOf2() const { 419 if (isSingleWord()) { 420 assert(BitWidth && "zero width values not allowed"); 421 return isPowerOf2_64(U.VAL); 422 } 423 return countPopulationSlowCase() == 1; 424 } 425 426 /// Check if this APInt's negated value is a power of two greater than zero. 427 bool isNegatedPowerOf2() const { 428 assert(BitWidth && "zero width values not allowed"); 429 if (isNonNegative()) 430 return false; 431 // NegatedPowerOf2 - shifted mask in the top bits. 432 unsigned LO = countl_one(); 433 unsigned TZ = countr_zero(); 434 return (LO + TZ) == BitWidth; 435 } 436 437 /// Checks if this APInt -interpreted as an address- is aligned to the 438 /// provided value. 439 bool isAligned(Align A) const; 440 441 /// Check if the APInt's value is returned by getSignMask. 442 /// 443 /// \returns true if this is the value returned by getSignMask. 444 bool isSignMask() const { return isMinSignedValue(); } 445 446 /// Convert APInt to a boolean value. 447 /// 448 /// This converts the APInt to a boolean value as a test against zero. 449 bool getBoolValue() const { return !isZero(); } 450 451 /// If this value is smaller than the specified limit, return it, otherwise 452 /// return the limit value. This causes the value to saturate to the limit. 453 uint64_t getLimitedValue(uint64_t Limit = UINT64_MAX) const { 454 return ugt(Limit) ? Limit : getZExtValue(); 455 } 456 457 /// Check if the APInt consists of a repeated bit pattern. 458 /// 459 /// e.g. 0x01010101 satisfies isSplat(8). 460 /// \param SplatSizeInBits The size of the pattern in bits. Must divide bit 461 /// width without remainder. 462 bool isSplat(unsigned SplatSizeInBits) const; 463 464 /// \returns true if this APInt value is a sequence of \param numBits ones 465 /// starting at the least significant bit with the remainder zero. 466 bool isMask(unsigned numBits) const { 467 assert(numBits != 0 && "numBits must be non-zero"); 468 assert(numBits <= BitWidth && "numBits out of range"); 469 if (isSingleWord()) 470 return U.VAL == (WORDTYPE_MAX >> (APINT_BITS_PER_WORD - numBits)); 471 unsigned Ones = countTrailingOnesSlowCase(); 472 return (numBits == Ones) && 473 ((Ones + countLeadingZerosSlowCase()) == BitWidth); 474 } 475 476 /// \returns true if this APInt is a non-empty sequence of ones starting at 477 /// the least significant bit with the remainder zero. 478 /// Ex. isMask(0x0000FFFFU) == true. 479 bool isMask() const { 480 if (isSingleWord()) 481 return isMask_64(U.VAL); 482 unsigned Ones = countTrailingOnesSlowCase(); 483 return (Ones > 0) && ((Ones + countLeadingZerosSlowCase()) == BitWidth); 484 } 485 486 /// Return true if this APInt value contains a non-empty sequence of ones with 487 /// the remainder zero. 488 bool isShiftedMask() const { 489 if (isSingleWord()) 490 return isShiftedMask_64(U.VAL); 491 unsigned Ones = countPopulationSlowCase(); 492 unsigned LeadZ = countLeadingZerosSlowCase(); 493 return (Ones + LeadZ + countr_zero()) == BitWidth; 494 } 495 496 /// Return true if this APInt value contains a non-empty sequence of ones with 497 /// the remainder zero. If true, \p MaskIdx will specify the index of the 498 /// lowest set bit and \p MaskLen is updated to specify the length of the 499 /// mask, else neither are updated. 500 bool isShiftedMask(unsigned &MaskIdx, unsigned &MaskLen) const { 501 if (isSingleWord()) 502 return isShiftedMask_64(U.VAL, MaskIdx, MaskLen); 503 unsigned Ones = countPopulationSlowCase(); 504 unsigned LeadZ = countLeadingZerosSlowCase(); 505 unsigned TrailZ = countTrailingZerosSlowCase(); 506 if ((Ones + LeadZ + TrailZ) != BitWidth) 507 return false; 508 MaskLen = Ones; 509 MaskIdx = TrailZ; 510 return true; 511 } 512 513 /// Compute an APInt containing numBits highbits from this APInt. 514 /// 515 /// Get an APInt with the same BitWidth as this APInt, just zero mask the low 516 /// bits and right shift to the least significant bit. 517 /// 518 /// \returns the high "numBits" bits of this APInt. 519 APInt getHiBits(unsigned numBits) const; 520 521 /// Compute an APInt containing numBits lowbits from this APInt. 522 /// 523 /// Get an APInt with the same BitWidth as this APInt, just zero mask the high 524 /// bits. 525 /// 526 /// \returns the low "numBits" bits of this APInt. 527 APInt getLoBits(unsigned numBits) const; 528 529 /// Determine if two APInts have the same value, after zero-extending 530 /// one of them (if needed!) to ensure that the bit-widths match. 531 static bool isSameValue(const APInt &I1, const APInt &I2) { 532 if (I1.getBitWidth() == I2.getBitWidth()) 533 return I1 == I2; 534 535 if (I1.getBitWidth() > I2.getBitWidth()) 536 return I1 == I2.zext(I1.getBitWidth()); 537 538 return I1.zext(I2.getBitWidth()) == I2; 539 } 540 541 /// Overload to compute a hash_code for an APInt value. 542 friend hash_code hash_value(const APInt &Arg); 543 544 /// This function returns a pointer to the internal storage of the APInt. 545 /// This is useful for writing out the APInt in binary form without any 546 /// conversions. 547 const uint64_t *getRawData() const { 548 if (isSingleWord()) 549 return &U.VAL; 550 return &U.pVal[0]; 551 } 552 553 /// @} 554 /// \name Unary Operators 555 /// @{ 556 557 /// Postfix increment operator. Increment *this by 1. 558 /// 559 /// \returns a new APInt value representing the original value of *this. 560 APInt operator++(int) { 561 APInt API(*this); 562 ++(*this); 563 return API; 564 } 565 566 /// Prefix increment operator. 567 /// 568 /// \returns *this incremented by one 569 APInt &operator++(); 570 571 /// Postfix decrement operator. Decrement *this by 1. 572 /// 573 /// \returns a new APInt value representing the original value of *this. 574 APInt operator--(int) { 575 APInt API(*this); 576 --(*this); 577 return API; 578 } 579 580 /// Prefix decrement operator. 581 /// 582 /// \returns *this decremented by one. 583 APInt &operator--(); 584 585 /// Logical negation operation on this APInt returns true if zero, like normal 586 /// integers. 587 bool operator!() const { return isZero(); } 588 589 /// @} 590 /// \name Assignment Operators 591 /// @{ 592 593 /// Copy assignment operator. 594 /// 595 /// \returns *this after assignment of RHS. 596 APInt &operator=(const APInt &RHS) { 597 // The common case (both source or dest being inline) doesn't require 598 // allocation or deallocation. 599 if (isSingleWord() && RHS.isSingleWord()) { 600 U.VAL = RHS.U.VAL; 601 BitWidth = RHS.BitWidth; 602 return *this; 603 } 604 605 assignSlowCase(RHS); 606 return *this; 607 } 608 609 /// Move assignment operator. 610 APInt &operator=(APInt &&that) { 611 #ifdef EXPENSIVE_CHECKS 612 // Some std::shuffle implementations still do self-assignment. 613 if (this == &that) 614 return *this; 615 #endif 616 assert(this != &that && "Self-move not supported"); 617 if (!isSingleWord()) 618 delete[] U.pVal; 619 620 // Use memcpy so that type based alias analysis sees both VAL and pVal 621 // as modified. 622 memcpy(&U, &that.U, sizeof(U)); 623 624 BitWidth = that.BitWidth; 625 that.BitWidth = 0; 626 return *this; 627 } 628 629 /// Assignment operator. 630 /// 631 /// The RHS value is assigned to *this. If the significant bits in RHS exceed 632 /// the bit width, the excess bits are truncated. If the bit width is larger 633 /// than 64, the value is zero filled in the unspecified high order bits. 634 /// 635 /// \returns *this after assignment of RHS value. 636 APInt &operator=(uint64_t RHS) { 637 if (isSingleWord()) { 638 U.VAL = RHS; 639 return clearUnusedBits(); 640 } 641 U.pVal[0] = RHS; 642 memset(U.pVal + 1, 0, (getNumWords() - 1) * APINT_WORD_SIZE); 643 return *this; 644 } 645 646 /// Bitwise AND assignment operator. 647 /// 648 /// Performs a bitwise AND operation on this APInt and RHS. The result is 649 /// assigned to *this. 650 /// 651 /// \returns *this after ANDing with RHS. 652 APInt &operator&=(const APInt &RHS) { 653 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 654 if (isSingleWord()) 655 U.VAL &= RHS.U.VAL; 656 else 657 andAssignSlowCase(RHS); 658 return *this; 659 } 660 661 /// Bitwise AND assignment operator. 662 /// 663 /// Performs a bitwise AND operation on this APInt and RHS. RHS is 664 /// logically zero-extended or truncated to match the bit-width of 665 /// the LHS. 666 APInt &operator&=(uint64_t RHS) { 667 if (isSingleWord()) { 668 U.VAL &= RHS; 669 return *this; 670 } 671 U.pVal[0] &= RHS; 672 memset(U.pVal + 1, 0, (getNumWords() - 1) * APINT_WORD_SIZE); 673 return *this; 674 } 675 676 /// Bitwise OR assignment operator. 677 /// 678 /// Performs a bitwise OR operation on this APInt and RHS. The result is 679 /// assigned *this; 680 /// 681 /// \returns *this after ORing with RHS. 682 APInt &operator|=(const APInt &RHS) { 683 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 684 if (isSingleWord()) 685 U.VAL |= RHS.U.VAL; 686 else 687 orAssignSlowCase(RHS); 688 return *this; 689 } 690 691 /// Bitwise OR assignment operator. 692 /// 693 /// Performs a bitwise OR operation on this APInt and RHS. RHS is 694 /// logically zero-extended or truncated to match the bit-width of 695 /// the LHS. 696 APInt &operator|=(uint64_t RHS) { 697 if (isSingleWord()) { 698 U.VAL |= RHS; 699 return clearUnusedBits(); 700 } 701 U.pVal[0] |= RHS; 702 return *this; 703 } 704 705 /// Bitwise XOR assignment operator. 706 /// 707 /// Performs a bitwise XOR operation on this APInt and RHS. The result is 708 /// assigned to *this. 709 /// 710 /// \returns *this after XORing with RHS. 711 APInt &operator^=(const APInt &RHS) { 712 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 713 if (isSingleWord()) 714 U.VAL ^= RHS.U.VAL; 715 else 716 xorAssignSlowCase(RHS); 717 return *this; 718 } 719 720 /// Bitwise XOR assignment operator. 721 /// 722 /// Performs a bitwise XOR operation on this APInt and RHS. RHS is 723 /// logically zero-extended or truncated to match the bit-width of 724 /// the LHS. 725 APInt &operator^=(uint64_t RHS) { 726 if (isSingleWord()) { 727 U.VAL ^= RHS; 728 return clearUnusedBits(); 729 } 730 U.pVal[0] ^= RHS; 731 return *this; 732 } 733 734 /// Multiplication assignment operator. 735 /// 736 /// Multiplies this APInt by RHS and assigns the result to *this. 737 /// 738 /// \returns *this 739 APInt &operator*=(const APInt &RHS); 740 APInt &operator*=(uint64_t RHS); 741 742 /// Addition assignment operator. 743 /// 744 /// Adds RHS to *this and assigns the result to *this. 745 /// 746 /// \returns *this 747 APInt &operator+=(const APInt &RHS); 748 APInt &operator+=(uint64_t RHS); 749 750 /// Subtraction assignment operator. 751 /// 752 /// Subtracts RHS from *this and assigns the result to *this. 753 /// 754 /// \returns *this 755 APInt &operator-=(const APInt &RHS); 756 APInt &operator-=(uint64_t RHS); 757 758 /// Left-shift assignment function. 759 /// 760 /// Shifts *this left by shiftAmt and assigns the result to *this. 761 /// 762 /// \returns *this after shifting left by ShiftAmt 763 APInt &operator<<=(unsigned ShiftAmt) { 764 assert(ShiftAmt <= BitWidth && "Invalid shift amount"); 765 if (isSingleWord()) { 766 if (ShiftAmt == BitWidth) 767 U.VAL = 0; 768 else 769 U.VAL <<= ShiftAmt; 770 return clearUnusedBits(); 771 } 772 shlSlowCase(ShiftAmt); 773 return *this; 774 } 775 776 /// Left-shift assignment function. 777 /// 778 /// Shifts *this left by shiftAmt and assigns the result to *this. 779 /// 780 /// \returns *this after shifting left by ShiftAmt 781 APInt &operator<<=(const APInt &ShiftAmt); 782 783 /// @} 784 /// \name Binary Operators 785 /// @{ 786 787 /// Multiplication operator. 788 /// 789 /// Multiplies this APInt by RHS and returns the result. 790 APInt operator*(const APInt &RHS) const; 791 792 /// Left logical shift operator. 793 /// 794 /// Shifts this APInt left by \p Bits and returns the result. 795 APInt operator<<(unsigned Bits) const { return shl(Bits); } 796 797 /// Left logical shift operator. 798 /// 799 /// Shifts this APInt left by \p Bits and returns the result. 800 APInt operator<<(const APInt &Bits) const { return shl(Bits); } 801 802 /// Arithmetic right-shift function. 803 /// 804 /// Arithmetic right-shift this APInt by shiftAmt. 805 APInt ashr(unsigned ShiftAmt) const { 806 APInt R(*this); 807 R.ashrInPlace(ShiftAmt); 808 return R; 809 } 810 811 /// Arithmetic right-shift this APInt by ShiftAmt in place. 812 void ashrInPlace(unsigned ShiftAmt) { 813 assert(ShiftAmt <= BitWidth && "Invalid shift amount"); 814 if (isSingleWord()) { 815 int64_t SExtVAL = SignExtend64(U.VAL, BitWidth); 816 if (ShiftAmt == BitWidth) 817 U.VAL = SExtVAL >> (APINT_BITS_PER_WORD - 1); // Fill with sign bit. 818 else 819 U.VAL = SExtVAL >> ShiftAmt; 820 clearUnusedBits(); 821 return; 822 } 823 ashrSlowCase(ShiftAmt); 824 } 825 826 /// Logical right-shift function. 827 /// 828 /// Logical right-shift this APInt by shiftAmt. 829 APInt lshr(unsigned shiftAmt) const { 830 APInt R(*this); 831 R.lshrInPlace(shiftAmt); 832 return R; 833 } 834 835 /// Logical right-shift this APInt by ShiftAmt in place. 836 void lshrInPlace(unsigned ShiftAmt) { 837 assert(ShiftAmt <= BitWidth && "Invalid shift amount"); 838 if (isSingleWord()) { 839 if (ShiftAmt == BitWidth) 840 U.VAL = 0; 841 else 842 U.VAL >>= ShiftAmt; 843 return; 844 } 845 lshrSlowCase(ShiftAmt); 846 } 847 848 /// Left-shift function. 849 /// 850 /// Left-shift this APInt by shiftAmt. 851 APInt shl(unsigned shiftAmt) const { 852 APInt R(*this); 853 R <<= shiftAmt; 854 return R; 855 } 856 857 /// relative logical shift right 858 APInt relativeLShr(int RelativeShift) const { 859 return RelativeShift > 0 ? lshr(RelativeShift) : shl(-RelativeShift); 860 } 861 862 /// relative logical shift left 863 APInt relativeLShl(int RelativeShift) const { 864 return relativeLShr(-RelativeShift); 865 } 866 867 /// relative arithmetic shift right 868 APInt relativeAShr(int RelativeShift) const { 869 return RelativeShift > 0 ? ashr(RelativeShift) : shl(-RelativeShift); 870 } 871 872 /// relative arithmetic shift left 873 APInt relativeAShl(int RelativeShift) const { 874 return relativeAShr(-RelativeShift); 875 } 876 877 /// Rotate left by rotateAmt. 878 APInt rotl(unsigned rotateAmt) const; 879 880 /// Rotate right by rotateAmt. 881 APInt rotr(unsigned rotateAmt) const; 882 883 /// Arithmetic right-shift function. 884 /// 885 /// Arithmetic right-shift this APInt by shiftAmt. 886 APInt ashr(const APInt &ShiftAmt) const { 887 APInt R(*this); 888 R.ashrInPlace(ShiftAmt); 889 return R; 890 } 891 892 /// Arithmetic right-shift this APInt by shiftAmt in place. 893 void ashrInPlace(const APInt &shiftAmt); 894 895 /// Logical right-shift function. 896 /// 897 /// Logical right-shift this APInt by shiftAmt. 898 APInt lshr(const APInt &ShiftAmt) const { 899 APInt R(*this); 900 R.lshrInPlace(ShiftAmt); 901 return R; 902 } 903 904 /// Logical right-shift this APInt by ShiftAmt in place. 905 void lshrInPlace(const APInt &ShiftAmt); 906 907 /// Left-shift function. 908 /// 909 /// Left-shift this APInt by shiftAmt. 910 APInt shl(const APInt &ShiftAmt) const { 911 APInt R(*this); 912 R <<= ShiftAmt; 913 return R; 914 } 915 916 /// Rotate left by rotateAmt. 917 APInt rotl(const APInt &rotateAmt) const; 918 919 /// Rotate right by rotateAmt. 920 APInt rotr(const APInt &rotateAmt) const; 921 922 /// Concatenate the bits from "NewLSB" onto the bottom of *this. This is 923 /// equivalent to: 924 /// (this->zext(NewWidth) << NewLSB.getBitWidth()) | NewLSB.zext(NewWidth) 925 APInt concat(const APInt &NewLSB) const { 926 /// If the result will be small, then both the merged values are small. 927 unsigned NewWidth = getBitWidth() + NewLSB.getBitWidth(); 928 if (NewWidth <= APINT_BITS_PER_WORD) 929 return APInt(NewWidth, (U.VAL << NewLSB.getBitWidth()) | NewLSB.U.VAL); 930 return concatSlowCase(NewLSB); 931 } 932 933 /// Unsigned division operation. 934 /// 935 /// Perform an unsigned divide operation on this APInt by RHS. Both this and 936 /// RHS are treated as unsigned quantities for purposes of this division. 937 /// 938 /// \returns a new APInt value containing the division result, rounded towards 939 /// zero. 940 APInt udiv(const APInt &RHS) const; 941 APInt udiv(uint64_t RHS) const; 942 943 /// Signed division function for APInt. 944 /// 945 /// Signed divide this APInt by APInt RHS. 946 /// 947 /// The result is rounded towards zero. 948 APInt sdiv(const APInt &RHS) const; 949 APInt sdiv(int64_t RHS) const; 950 951 /// Unsigned remainder operation. 952 /// 953 /// Perform an unsigned remainder operation on this APInt with RHS being the 954 /// divisor. Both this and RHS are treated as unsigned quantities for purposes 955 /// of this operation. 956 /// 957 /// \returns a new APInt value containing the remainder result 958 APInt urem(const APInt &RHS) const; 959 uint64_t urem(uint64_t RHS) const; 960 961 /// Function for signed remainder operation. 962 /// 963 /// Signed remainder operation on APInt. 964 /// 965 /// Note that this is a true remainder operation and not a modulo operation 966 /// because the sign follows the sign of the dividend which is *this. 967 APInt srem(const APInt &RHS) const; 968 int64_t srem(int64_t RHS) const; 969 970 /// Dual division/remainder interface. 971 /// 972 /// Sometimes it is convenient to divide two APInt values and obtain both the 973 /// quotient and remainder. This function does both operations in the same 974 /// computation making it a little more efficient. The pair of input arguments 975 /// may overlap with the pair of output arguments. It is safe to call 976 /// udivrem(X, Y, X, Y), for example. 977 static void udivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, 978 APInt &Remainder); 979 static void udivrem(const APInt &LHS, uint64_t RHS, APInt &Quotient, 980 uint64_t &Remainder); 981 982 static void sdivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, 983 APInt &Remainder); 984 static void sdivrem(const APInt &LHS, int64_t RHS, APInt &Quotient, 985 int64_t &Remainder); 986 987 // Operations that return overflow indicators. 988 APInt sadd_ov(const APInt &RHS, bool &Overflow) const; 989 APInt uadd_ov(const APInt &RHS, bool &Overflow) const; 990 APInt ssub_ov(const APInt &RHS, bool &Overflow) const; 991 APInt usub_ov(const APInt &RHS, bool &Overflow) const; 992 APInt sdiv_ov(const APInt &RHS, bool &Overflow) const; 993 APInt smul_ov(const APInt &RHS, bool &Overflow) const; 994 APInt umul_ov(const APInt &RHS, bool &Overflow) const; 995 APInt sshl_ov(const APInt &Amt, bool &Overflow) const; 996 APInt sshl_ov(unsigned Amt, bool &Overflow) const; 997 APInt ushl_ov(const APInt &Amt, bool &Overflow) const; 998 APInt ushl_ov(unsigned Amt, bool &Overflow) const; 999 1000 // Operations that saturate 1001 APInt sadd_sat(const APInt &RHS) const; 1002 APInt uadd_sat(const APInt &RHS) const; 1003 APInt ssub_sat(const APInt &RHS) const; 1004 APInt usub_sat(const APInt &RHS) const; 1005 APInt smul_sat(const APInt &RHS) const; 1006 APInt umul_sat(const APInt &RHS) const; 1007 APInt sshl_sat(const APInt &RHS) const; 1008 APInt sshl_sat(unsigned RHS) const; 1009 APInt ushl_sat(const APInt &RHS) const; 1010 APInt ushl_sat(unsigned RHS) const; 1011 1012 /// Array-indexing support. 1013 /// 1014 /// \returns the bit value at bitPosition 1015 bool operator[](unsigned bitPosition) const { 1016 assert(bitPosition < getBitWidth() && "Bit position out of bounds!"); 1017 return (maskBit(bitPosition) & getWord(bitPosition)) != 0; 1018 } 1019 1020 /// @} 1021 /// \name Comparison Operators 1022 /// @{ 1023 1024 /// Equality operator. 1025 /// 1026 /// Compares this APInt with RHS for the validity of the equality 1027 /// relationship. 1028 bool operator==(const APInt &RHS) const { 1029 assert(BitWidth == RHS.BitWidth && "Comparison requires equal bit widths"); 1030 if (isSingleWord()) 1031 return U.VAL == RHS.U.VAL; 1032 return equalSlowCase(RHS); 1033 } 1034 1035 /// Equality operator. 1036 /// 1037 /// Compares this APInt with a uint64_t for the validity of the equality 1038 /// relationship. 1039 /// 1040 /// \returns true if *this == Val 1041 bool operator==(uint64_t Val) const { 1042 return (isSingleWord() || getActiveBits() <= 64) && getZExtValue() == Val; 1043 } 1044 1045 /// Equality comparison. 1046 /// 1047 /// Compares this APInt with RHS for the validity of the equality 1048 /// relationship. 1049 /// 1050 /// \returns true if *this == Val 1051 bool eq(const APInt &RHS) const { return (*this) == RHS; } 1052 1053 /// Inequality operator. 1054 /// 1055 /// Compares this APInt with RHS for the validity of the inequality 1056 /// relationship. 1057 /// 1058 /// \returns true if *this != Val 1059 bool operator!=(const APInt &RHS) const { return !((*this) == RHS); } 1060 1061 /// Inequality operator. 1062 /// 1063 /// Compares this APInt with a uint64_t for the validity of the inequality 1064 /// relationship. 1065 /// 1066 /// \returns true if *this != Val 1067 bool operator!=(uint64_t Val) const { return !((*this) == Val); } 1068 1069 /// Inequality comparison 1070 /// 1071 /// Compares this APInt with RHS for the validity of the inequality 1072 /// relationship. 1073 /// 1074 /// \returns true if *this != Val 1075 bool ne(const APInt &RHS) const { return !((*this) == RHS); } 1076 1077 /// Unsigned less than comparison 1078 /// 1079 /// Regards both *this and RHS as unsigned quantities and compares them for 1080 /// the validity of the less-than relationship. 1081 /// 1082 /// \returns true if *this < RHS when both are considered unsigned. 1083 bool ult(const APInt &RHS) const { return compare(RHS) < 0; } 1084 1085 /// Unsigned less than comparison 1086 /// 1087 /// Regards both *this as an unsigned quantity and compares it with RHS for 1088 /// the validity of the less-than relationship. 1089 /// 1090 /// \returns true if *this < RHS when considered unsigned. 1091 bool ult(uint64_t RHS) const { 1092 // Only need to check active bits if not a single word. 1093 return (isSingleWord() || getActiveBits() <= 64) && getZExtValue() < RHS; 1094 } 1095 1096 /// Signed less than comparison 1097 /// 1098 /// Regards both *this and RHS as signed quantities and compares them for 1099 /// validity of the less-than relationship. 1100 /// 1101 /// \returns true if *this < RHS when both are considered signed. 1102 bool slt(const APInt &RHS) const { return compareSigned(RHS) < 0; } 1103 1104 /// Signed less than comparison 1105 /// 1106 /// Regards both *this as a signed quantity and compares it with RHS for 1107 /// the validity of the less-than relationship. 1108 /// 1109 /// \returns true if *this < RHS when considered signed. 1110 bool slt(int64_t RHS) const { 1111 return (!isSingleWord() && getSignificantBits() > 64) 1112 ? isNegative() 1113 : getSExtValue() < RHS; 1114 } 1115 1116 /// Unsigned less or equal comparison 1117 /// 1118 /// Regards both *this and RHS as unsigned quantities and compares them for 1119 /// validity of the less-or-equal relationship. 1120 /// 1121 /// \returns true if *this <= RHS when both are considered unsigned. 1122 bool ule(const APInt &RHS) const { return compare(RHS) <= 0; } 1123 1124 /// Unsigned less or equal comparison 1125 /// 1126 /// Regards both *this as an unsigned quantity and compares it with RHS for 1127 /// the validity of the less-or-equal relationship. 1128 /// 1129 /// \returns true if *this <= RHS when considered unsigned. 1130 bool ule(uint64_t RHS) const { return !ugt(RHS); } 1131 1132 /// Signed less or equal comparison 1133 /// 1134 /// Regards both *this and RHS as signed quantities and compares them for 1135 /// validity of the less-or-equal relationship. 1136 /// 1137 /// \returns true if *this <= RHS when both are considered signed. 1138 bool sle(const APInt &RHS) const { return compareSigned(RHS) <= 0; } 1139 1140 /// Signed less or equal comparison 1141 /// 1142 /// Regards both *this as a signed quantity and compares it with RHS for the 1143 /// validity of the less-or-equal relationship. 1144 /// 1145 /// \returns true if *this <= RHS when considered signed. 1146 bool sle(uint64_t RHS) const { return !sgt(RHS); } 1147 1148 /// Unsigned greater than comparison 1149 /// 1150 /// Regards both *this and RHS as unsigned quantities and compares them for 1151 /// the validity of the greater-than relationship. 1152 /// 1153 /// \returns true if *this > RHS when both are considered unsigned. 1154 bool ugt(const APInt &RHS) const { return !ule(RHS); } 1155 1156 /// Unsigned greater than comparison 1157 /// 1158 /// Regards both *this as an unsigned quantity and compares it with RHS for 1159 /// the validity of the greater-than relationship. 1160 /// 1161 /// \returns true if *this > RHS when considered unsigned. 1162 bool ugt(uint64_t RHS) const { 1163 // Only need to check active bits if not a single word. 1164 return (!isSingleWord() && getActiveBits() > 64) || getZExtValue() > RHS; 1165 } 1166 1167 /// Signed greater than comparison 1168 /// 1169 /// Regards both *this and RHS as signed quantities and compares them for the 1170 /// validity of the greater-than relationship. 1171 /// 1172 /// \returns true if *this > RHS when both are considered signed. 1173 bool sgt(const APInt &RHS) const { return !sle(RHS); } 1174 1175 /// Signed greater than comparison 1176 /// 1177 /// Regards both *this as a signed quantity and compares it with RHS for 1178 /// the validity of the greater-than relationship. 1179 /// 1180 /// \returns true if *this > RHS when considered signed. 1181 bool sgt(int64_t RHS) const { 1182 return (!isSingleWord() && getSignificantBits() > 64) 1183 ? !isNegative() 1184 : getSExtValue() > RHS; 1185 } 1186 1187 /// Unsigned greater or equal comparison 1188 /// 1189 /// Regards both *this and RHS as unsigned quantities and compares them for 1190 /// validity of the greater-or-equal relationship. 1191 /// 1192 /// \returns true if *this >= RHS when both are considered unsigned. 1193 bool uge(const APInt &RHS) const { return !ult(RHS); } 1194 1195 /// Unsigned greater or equal comparison 1196 /// 1197 /// Regards both *this as an unsigned quantity and compares it with RHS for 1198 /// the validity of the greater-or-equal relationship. 1199 /// 1200 /// \returns true if *this >= RHS when considered unsigned. 1201 bool uge(uint64_t RHS) const { return !ult(RHS); } 1202 1203 /// Signed greater or equal comparison 1204 /// 1205 /// Regards both *this and RHS as signed quantities and compares them for 1206 /// validity of the greater-or-equal relationship. 1207 /// 1208 /// \returns true if *this >= RHS when both are considered signed. 1209 bool sge(const APInt &RHS) const { return !slt(RHS); } 1210 1211 /// Signed greater or equal comparison 1212 /// 1213 /// Regards both *this as a signed quantity and compares it with RHS for 1214 /// the validity of the greater-or-equal relationship. 1215 /// 1216 /// \returns true if *this >= RHS when considered signed. 1217 bool sge(int64_t RHS) const { return !slt(RHS); } 1218 1219 /// This operation tests if there are any pairs of corresponding bits 1220 /// between this APInt and RHS that are both set. 1221 bool intersects(const APInt &RHS) const { 1222 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 1223 if (isSingleWord()) 1224 return (U.VAL & RHS.U.VAL) != 0; 1225 return intersectsSlowCase(RHS); 1226 } 1227 1228 /// This operation checks that all bits set in this APInt are also set in RHS. 1229 bool isSubsetOf(const APInt &RHS) const { 1230 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 1231 if (isSingleWord()) 1232 return (U.VAL & ~RHS.U.VAL) == 0; 1233 return isSubsetOfSlowCase(RHS); 1234 } 1235 1236 /// @} 1237 /// \name Resizing Operators 1238 /// @{ 1239 1240 /// Truncate to new width. 1241 /// 1242 /// Truncate the APInt to a specified width. It is an error to specify a width 1243 /// that is greater than the current width. 1244 APInt trunc(unsigned width) const; 1245 1246 /// Truncate to new width with unsigned saturation. 1247 /// 1248 /// If the APInt, treated as unsigned integer, can be losslessly truncated to 1249 /// the new bitwidth, then return truncated APInt. Else, return max value. 1250 APInt truncUSat(unsigned width) const; 1251 1252 /// Truncate to new width with signed saturation. 1253 /// 1254 /// If this APInt, treated as signed integer, can be losslessly truncated to 1255 /// the new bitwidth, then return truncated APInt. Else, return either 1256 /// signed min value if the APInt was negative, or signed max value. 1257 APInt truncSSat(unsigned width) const; 1258 1259 /// Sign extend to a new width. 1260 /// 1261 /// This operation sign extends the APInt to a new width. If the high order 1262 /// bit is set, the fill on the left will be done with 1 bits, otherwise zero. 1263 /// It is an error to specify a width that is less than the 1264 /// current width. 1265 APInt sext(unsigned width) const; 1266 1267 /// Zero extend to a new width. 1268 /// 1269 /// This operation zero extends the APInt to a new width. The high order bits 1270 /// are filled with 0 bits. It is an error to specify a width that is less 1271 /// than the current width. 1272 APInt zext(unsigned width) const; 1273 1274 /// Sign extend or truncate to width 1275 /// 1276 /// Make this APInt have the bit width given by \p width. The value is sign 1277 /// extended, truncated, or left alone to make it that width. 1278 APInt sextOrTrunc(unsigned width) const; 1279 1280 /// Zero extend or truncate to width 1281 /// 1282 /// Make this APInt have the bit width given by \p width. The value is zero 1283 /// extended, truncated, or left alone to make it that width. 1284 APInt zextOrTrunc(unsigned width) const; 1285 1286 /// @} 1287 /// \name Bit Manipulation Operators 1288 /// @{ 1289 1290 /// Set every bit to 1. 1291 void setAllBits() { 1292 if (isSingleWord()) 1293 U.VAL = WORDTYPE_MAX; 1294 else 1295 // Set all the bits in all the words. 1296 memset(U.pVal, -1, getNumWords() * APINT_WORD_SIZE); 1297 // Clear the unused ones 1298 clearUnusedBits(); 1299 } 1300 1301 /// Set the given bit to 1 whose position is given as "bitPosition". 1302 void setBit(unsigned BitPosition) { 1303 assert(BitPosition < BitWidth && "BitPosition out of range"); 1304 WordType Mask = maskBit(BitPosition); 1305 if (isSingleWord()) 1306 U.VAL |= Mask; 1307 else 1308 U.pVal[whichWord(BitPosition)] |= Mask; 1309 } 1310 1311 /// Set the sign bit to 1. 1312 void setSignBit() { setBit(BitWidth - 1); } 1313 1314 /// Set a given bit to a given value. 1315 void setBitVal(unsigned BitPosition, bool BitValue) { 1316 if (BitValue) 1317 setBit(BitPosition); 1318 else 1319 clearBit(BitPosition); 1320 } 1321 1322 /// Set the bits from loBit (inclusive) to hiBit (exclusive) to 1. 1323 /// This function handles "wrap" case when \p loBit >= \p hiBit, and calls 1324 /// setBits when \p loBit < \p hiBit. 1325 /// For \p loBit == \p hiBit wrap case, set every bit to 1. 1326 void setBitsWithWrap(unsigned loBit, unsigned hiBit) { 1327 assert(hiBit <= BitWidth && "hiBit out of range"); 1328 assert(loBit <= BitWidth && "loBit out of range"); 1329 if (loBit < hiBit) { 1330 setBits(loBit, hiBit); 1331 return; 1332 } 1333 setLowBits(hiBit); 1334 setHighBits(BitWidth - loBit); 1335 } 1336 1337 /// Set the bits from loBit (inclusive) to hiBit (exclusive) to 1. 1338 /// This function handles case when \p loBit <= \p hiBit. 1339 void setBits(unsigned loBit, unsigned hiBit) { 1340 assert(hiBit <= BitWidth && "hiBit out of range"); 1341 assert(loBit <= BitWidth && "loBit out of range"); 1342 assert(loBit <= hiBit && "loBit greater than hiBit"); 1343 if (loBit == hiBit) 1344 return; 1345 if (loBit < APINT_BITS_PER_WORD && hiBit <= APINT_BITS_PER_WORD) { 1346 uint64_t mask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - (hiBit - loBit)); 1347 mask <<= loBit; 1348 if (isSingleWord()) 1349 U.VAL |= mask; 1350 else 1351 U.pVal[0] |= mask; 1352 } else { 1353 setBitsSlowCase(loBit, hiBit); 1354 } 1355 } 1356 1357 /// Set the top bits starting from loBit. 1358 void setBitsFrom(unsigned loBit) { return setBits(loBit, BitWidth); } 1359 1360 /// Set the bottom loBits bits. 1361 void setLowBits(unsigned loBits) { return setBits(0, loBits); } 1362 1363 /// Set the top hiBits bits. 1364 void setHighBits(unsigned hiBits) { 1365 return setBits(BitWidth - hiBits, BitWidth); 1366 } 1367 1368 /// Set every bit to 0. 1369 void clearAllBits() { 1370 if (isSingleWord()) 1371 U.VAL = 0; 1372 else 1373 memset(U.pVal, 0, getNumWords() * APINT_WORD_SIZE); 1374 } 1375 1376 /// Set a given bit to 0. 1377 /// 1378 /// Set the given bit to 0 whose position is given as "bitPosition". 1379 void clearBit(unsigned BitPosition) { 1380 assert(BitPosition < BitWidth && "BitPosition out of range"); 1381 WordType Mask = ~maskBit(BitPosition); 1382 if (isSingleWord()) 1383 U.VAL &= Mask; 1384 else 1385 U.pVal[whichWord(BitPosition)] &= Mask; 1386 } 1387 1388 /// Set bottom loBits bits to 0. 1389 void clearLowBits(unsigned loBits) { 1390 assert(loBits <= BitWidth && "More bits than bitwidth"); 1391 APInt Keep = getHighBitsSet(BitWidth, BitWidth - loBits); 1392 *this &= Keep; 1393 } 1394 1395 /// Set the sign bit to 0. 1396 void clearSignBit() { clearBit(BitWidth - 1); } 1397 1398 /// Toggle every bit to its opposite value. 1399 void flipAllBits() { 1400 if (isSingleWord()) { 1401 U.VAL ^= WORDTYPE_MAX; 1402 clearUnusedBits(); 1403 } else { 1404 flipAllBitsSlowCase(); 1405 } 1406 } 1407 1408 /// Toggles a given bit to its opposite value. 1409 /// 1410 /// Toggle a given bit to its opposite value whose position is given 1411 /// as "bitPosition". 1412 void flipBit(unsigned bitPosition); 1413 1414 /// Negate this APInt in place. 1415 void negate() { 1416 flipAllBits(); 1417 ++(*this); 1418 } 1419 1420 /// Insert the bits from a smaller APInt starting at bitPosition. 1421 void insertBits(const APInt &SubBits, unsigned bitPosition); 1422 void insertBits(uint64_t SubBits, unsigned bitPosition, unsigned numBits); 1423 1424 /// Return an APInt with the extracted bits [bitPosition,bitPosition+numBits). 1425 APInt extractBits(unsigned numBits, unsigned bitPosition) const; 1426 uint64_t extractBitsAsZExtValue(unsigned numBits, unsigned bitPosition) const; 1427 1428 /// @} 1429 /// \name Value Characterization Functions 1430 /// @{ 1431 1432 /// Return the number of bits in the APInt. 1433 unsigned getBitWidth() const { return BitWidth; } 1434 1435 /// Get the number of words. 1436 /// 1437 /// Here one word's bitwidth equals to that of uint64_t. 1438 /// 1439 /// \returns the number of words to hold the integer value of this APInt. 1440 unsigned getNumWords() const { return getNumWords(BitWidth); } 1441 1442 /// Get the number of words. 1443 /// 1444 /// *NOTE* Here one word's bitwidth equals to that of uint64_t. 1445 /// 1446 /// \returns the number of words to hold the integer value with a given bit 1447 /// width. 1448 static unsigned getNumWords(unsigned BitWidth) { 1449 return ((uint64_t)BitWidth + APINT_BITS_PER_WORD - 1) / APINT_BITS_PER_WORD; 1450 } 1451 1452 /// Compute the number of active bits in the value 1453 /// 1454 /// This function returns the number of active bits which is defined as the 1455 /// bit width minus the number of leading zeros. This is used in several 1456 /// computations to see how "wide" the value is. 1457 unsigned getActiveBits() const { return BitWidth - countl_zero(); } 1458 1459 /// Compute the number of active words in the value of this APInt. 1460 /// 1461 /// This is used in conjunction with getActiveData to extract the raw value of 1462 /// the APInt. 1463 unsigned getActiveWords() const { 1464 unsigned numActiveBits = getActiveBits(); 1465 return numActiveBits ? whichWord(numActiveBits - 1) + 1 : 1; 1466 } 1467 1468 /// Get the minimum bit size for this signed APInt 1469 /// 1470 /// Computes the minimum bit width for this APInt while considering it to be a 1471 /// signed (and probably negative) value. If the value is not negative, this 1472 /// function returns the same value as getActiveBits()+1. Otherwise, it 1473 /// returns the smallest bit width that will retain the negative value. For 1474 /// example, -1 can be written as 0b1 or 0xFFFFFFFFFF. 0b1 is shorter and so 1475 /// for -1, this function will always return 1. 1476 unsigned getSignificantBits() const { 1477 return BitWidth - getNumSignBits() + 1; 1478 } 1479 1480 /// Get zero extended value 1481 /// 1482 /// This method attempts to return the value of this APInt as a zero extended 1483 /// uint64_t. The bitwidth must be <= 64 or the value must fit within a 1484 /// uint64_t. Otherwise an assertion will result. 1485 uint64_t getZExtValue() const { 1486 if (isSingleWord()) 1487 return U.VAL; 1488 assert(getActiveBits() <= 64 && "Too many bits for uint64_t"); 1489 return U.pVal[0]; 1490 } 1491 1492 /// Get zero extended value if possible 1493 /// 1494 /// This method attempts to return the value of this APInt as a zero extended 1495 /// uint64_t. The bitwidth must be <= 64 or the value must fit within a 1496 /// uint64_t. Otherwise no value is returned. 1497 std::optional<uint64_t> tryZExtValue() const { 1498 return (getActiveBits() <= 64) ? std::optional<uint64_t>(getZExtValue()) 1499 : std::nullopt; 1500 }; 1501 1502 /// Get sign extended value 1503 /// 1504 /// This method attempts to return the value of this APInt as a sign extended 1505 /// int64_t. The bit width must be <= 64 or the value must fit within an 1506 /// int64_t. Otherwise an assertion will result. 1507 int64_t getSExtValue() const { 1508 if (isSingleWord()) 1509 return SignExtend64(U.VAL, BitWidth); 1510 assert(getSignificantBits() <= 64 && "Too many bits for int64_t"); 1511 return int64_t(U.pVal[0]); 1512 } 1513 1514 /// Get sign extended value if possible 1515 /// 1516 /// This method attempts to return the value of this APInt as a sign extended 1517 /// int64_t. The bitwidth must be <= 64 or the value must fit within an 1518 /// int64_t. Otherwise no value is returned. 1519 std::optional<int64_t> trySExtValue() const { 1520 return (getSignificantBits() <= 64) ? std::optional<int64_t>(getSExtValue()) 1521 : std::nullopt; 1522 }; 1523 1524 /// Get bits required for string value. 1525 /// 1526 /// This method determines how many bits are required to hold the APInt 1527 /// equivalent of the string given by \p str. 1528 static unsigned getBitsNeeded(StringRef str, uint8_t radix); 1529 1530 /// Get the bits that are sufficient to represent the string value. This may 1531 /// over estimate the amount of bits required, but it does not require 1532 /// parsing the value in the string. 1533 static unsigned getSufficientBitsNeeded(StringRef Str, uint8_t Radix); 1534 1535 /// The APInt version of std::countl_zero. 1536 /// 1537 /// It counts the number of zeros from the most significant bit to the first 1538 /// one bit. 1539 /// 1540 /// \returns BitWidth if the value is zero, otherwise returns the number of 1541 /// zeros from the most significant bit to the first one bits. 1542 unsigned countl_zero() const { 1543 if (isSingleWord()) { 1544 unsigned unusedBits = APINT_BITS_PER_WORD - BitWidth; 1545 return llvm::countl_zero(U.VAL) - unusedBits; 1546 } 1547 return countLeadingZerosSlowCase(); 1548 } 1549 1550 unsigned countLeadingZeros() const { return countl_zero(); } 1551 1552 /// Count the number of leading one bits. 1553 /// 1554 /// This function is an APInt version of std::countl_one. It counts the number 1555 /// of ones from the most significant bit to the first zero bit. 1556 /// 1557 /// \returns 0 if the high order bit is not set, otherwise returns the number 1558 /// of 1 bits from the most significant to the least 1559 unsigned countl_one() const { 1560 if (isSingleWord()) { 1561 if (LLVM_UNLIKELY(BitWidth == 0)) 1562 return 0; 1563 return llvm::countl_one(U.VAL << (APINT_BITS_PER_WORD - BitWidth)); 1564 } 1565 return countLeadingOnesSlowCase(); 1566 } 1567 1568 unsigned countLeadingOnes() const { return countl_one(); } 1569 1570 /// Computes the number of leading bits of this APInt that are equal to its 1571 /// sign bit. 1572 unsigned getNumSignBits() const { 1573 return isNegative() ? countl_one() : countl_zero(); 1574 } 1575 1576 /// Count the number of trailing zero bits. 1577 /// 1578 /// This function is an APInt version of std::countr_zero. It counts the 1579 /// number of zeros from the least significant bit to the first set bit. 1580 /// 1581 /// \returns BitWidth if the value is zero, otherwise returns the number of 1582 /// zeros from the least significant bit to the first one bit. 1583 unsigned countr_zero() const { 1584 if (isSingleWord()) { 1585 unsigned TrailingZeros = llvm::countr_zero(U.VAL); 1586 return (TrailingZeros > BitWidth ? BitWidth : TrailingZeros); 1587 } 1588 return countTrailingZerosSlowCase(); 1589 } 1590 1591 unsigned countTrailingZeros() const { return countr_zero(); } 1592 1593 /// Count the number of trailing one bits. 1594 /// 1595 /// This function is an APInt version of std::countr_one. It counts the number 1596 /// of ones from the least significant bit to the first zero bit. 1597 /// 1598 /// \returns BitWidth if the value is all ones, otherwise returns the number 1599 /// of ones from the least significant bit to the first zero bit. 1600 unsigned countr_one() const { 1601 if (isSingleWord()) 1602 return llvm::countr_one(U.VAL); 1603 return countTrailingOnesSlowCase(); 1604 } 1605 1606 unsigned countTrailingOnes() const { return countr_one(); } 1607 1608 /// Count the number of bits set. 1609 /// 1610 /// This function is an APInt version of std::popcount. It counts the number 1611 /// of 1 bits in the APInt value. 1612 /// 1613 /// \returns 0 if the value is zero, otherwise returns the number of set bits. 1614 unsigned popcount() const { 1615 if (isSingleWord()) 1616 return llvm::popcount(U.VAL); 1617 return countPopulationSlowCase(); 1618 } 1619 1620 /// @} 1621 /// \name Conversion Functions 1622 /// @{ 1623 void print(raw_ostream &OS, bool isSigned) const; 1624 1625 /// Converts an APInt to a string and append it to Str. Str is commonly a 1626 /// SmallString. If Radix > 10, UpperCase determine the case of letter 1627 /// digits. 1628 void toString(SmallVectorImpl<char> &Str, unsigned Radix, bool Signed, 1629 bool formatAsCLiteral = false, bool UpperCase = true) const; 1630 1631 /// Considers the APInt to be unsigned and converts it into a string in the 1632 /// radix given. The radix can be 2, 8, 10 16, or 36. 1633 void toStringUnsigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const { 1634 toString(Str, Radix, false, false); 1635 } 1636 1637 /// Considers the APInt to be signed and converts it into a string in the 1638 /// radix given. The radix can be 2, 8, 10, 16, or 36. 1639 void toStringSigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const { 1640 toString(Str, Radix, true, false); 1641 } 1642 1643 /// \returns a byte-swapped representation of this APInt Value. 1644 APInt byteSwap() const; 1645 1646 /// \returns the value with the bit representation reversed of this APInt 1647 /// Value. 1648 APInt reverseBits() const; 1649 1650 /// Converts this APInt to a double value. 1651 double roundToDouble(bool isSigned) const; 1652 1653 /// Converts this unsigned APInt to a double value. 1654 double roundToDouble() const { return roundToDouble(false); } 1655 1656 /// Converts this signed APInt to a double value. 1657 double signedRoundToDouble() const { return roundToDouble(true); } 1658 1659 /// Converts APInt bits to a double 1660 /// 1661 /// The conversion does not do a translation from integer to double, it just 1662 /// re-interprets the bits as a double. Note that it is valid to do this on 1663 /// any bit width. Exactly 64 bits will be translated. 1664 double bitsToDouble() const { return llvm::bit_cast<double>(getWord(0)); } 1665 1666 /// Converts APInt bits to a float 1667 /// 1668 /// The conversion does not do a translation from integer to float, it just 1669 /// re-interprets the bits as a float. Note that it is valid to do this on 1670 /// any bit width. Exactly 32 bits will be translated. 1671 float bitsToFloat() const { 1672 return llvm::bit_cast<float>(static_cast<uint32_t>(getWord(0))); 1673 } 1674 1675 /// Converts a double to APInt bits. 1676 /// 1677 /// The conversion does not do a translation from double to integer, it just 1678 /// re-interprets the bits of the double. 1679 static APInt doubleToBits(double V) { 1680 return APInt(sizeof(double) * CHAR_BIT, llvm::bit_cast<uint64_t>(V)); 1681 } 1682 1683 /// Converts a float to APInt bits. 1684 /// 1685 /// The conversion does not do a translation from float to integer, it just 1686 /// re-interprets the bits of the float. 1687 static APInt floatToBits(float V) { 1688 return APInt(sizeof(float) * CHAR_BIT, llvm::bit_cast<uint32_t>(V)); 1689 } 1690 1691 /// @} 1692 /// \name Mathematics Operations 1693 /// @{ 1694 1695 /// \returns the floor log base 2 of this APInt. 1696 unsigned logBase2() const { return getActiveBits() - 1; } 1697 1698 /// \returns the ceil log base 2 of this APInt. 1699 unsigned ceilLogBase2() const { 1700 APInt temp(*this); 1701 --temp; 1702 return temp.getActiveBits(); 1703 } 1704 1705 /// \returns the nearest log base 2 of this APInt. Ties round up. 1706 /// 1707 /// NOTE: When we have a BitWidth of 1, we define: 1708 /// 1709 /// log2(0) = UINT32_MAX 1710 /// log2(1) = 0 1711 /// 1712 /// to get around any mathematical concerns resulting from 1713 /// referencing 2 in a space where 2 does no exist. 1714 unsigned nearestLogBase2() const; 1715 1716 /// \returns the log base 2 of this APInt if its an exact power of two, -1 1717 /// otherwise 1718 int32_t exactLogBase2() const { 1719 if (!isPowerOf2()) 1720 return -1; 1721 return logBase2(); 1722 } 1723 1724 /// Compute the square root. 1725 APInt sqrt() const; 1726 1727 /// Get the absolute value. If *this is < 0 then return -(*this), otherwise 1728 /// *this. Note that the "most negative" signed number (e.g. -128 for 8 bit 1729 /// wide APInt) is unchanged due to how negation works. 1730 APInt abs() const { 1731 if (isNegative()) 1732 return -(*this); 1733 return *this; 1734 } 1735 1736 /// \returns the multiplicative inverse for a given modulo. 1737 APInt multiplicativeInverse(const APInt &modulo) const; 1738 1739 /// @} 1740 /// \name Building-block Operations for APInt and APFloat 1741 /// @{ 1742 1743 // These building block operations operate on a representation of arbitrary 1744 // precision, two's-complement, bignum integer values. They should be 1745 // sufficient to implement APInt and APFloat bignum requirements. Inputs are 1746 // generally a pointer to the base of an array of integer parts, representing 1747 // an unsigned bignum, and a count of how many parts there are. 1748 1749 /// Sets the least significant part of a bignum to the input value, and zeroes 1750 /// out higher parts. 1751 static void tcSet(WordType *, WordType, unsigned); 1752 1753 /// Assign one bignum to another. 1754 static void tcAssign(WordType *, const WordType *, unsigned); 1755 1756 /// Returns true if a bignum is zero, false otherwise. 1757 static bool tcIsZero(const WordType *, unsigned); 1758 1759 /// Extract the given bit of a bignum; returns 0 or 1. Zero-based. 1760 static int tcExtractBit(const WordType *, unsigned bit); 1761 1762 /// Copy the bit vector of width srcBITS from SRC, starting at bit srcLSB, to 1763 /// DST, of dstCOUNT parts, such that the bit srcLSB becomes the least 1764 /// significant bit of DST. All high bits above srcBITS in DST are 1765 /// zero-filled. 1766 static void tcExtract(WordType *, unsigned dstCount, const WordType *, 1767 unsigned srcBits, unsigned srcLSB); 1768 1769 /// Set the given bit of a bignum. Zero-based. 1770 static void tcSetBit(WordType *, unsigned bit); 1771 1772 /// Clear the given bit of a bignum. Zero-based. 1773 static void tcClearBit(WordType *, unsigned bit); 1774 1775 /// Returns the bit number of the least or most significant set bit of a 1776 /// number. If the input number has no bits set -1U is returned. 1777 static unsigned tcLSB(const WordType *, unsigned n); 1778 static unsigned tcMSB(const WordType *parts, unsigned n); 1779 1780 /// Negate a bignum in-place. 1781 static void tcNegate(WordType *, unsigned); 1782 1783 /// DST += RHS + CARRY where CARRY is zero or one. Returns the carry flag. 1784 static WordType tcAdd(WordType *, const WordType *, WordType carry, unsigned); 1785 /// DST += RHS. Returns the carry flag. 1786 static WordType tcAddPart(WordType *, WordType, unsigned); 1787 1788 /// DST -= RHS + CARRY where CARRY is zero or one. Returns the carry flag. 1789 static WordType tcSubtract(WordType *, const WordType *, WordType carry, 1790 unsigned); 1791 /// DST -= RHS. Returns the carry flag. 1792 static WordType tcSubtractPart(WordType *, WordType, unsigned); 1793 1794 /// DST += SRC * MULTIPLIER + PART if add is true 1795 /// DST = SRC * MULTIPLIER + PART if add is false 1796 /// 1797 /// Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC they must 1798 /// start at the same point, i.e. DST == SRC. 1799 /// 1800 /// If DSTPARTS == SRC_PARTS + 1 no overflow occurs and zero is returned. 1801 /// Otherwise DST is filled with the least significant DSTPARTS parts of the 1802 /// result, and if all of the omitted higher parts were zero return zero, 1803 /// otherwise overflow occurred and return one. 1804 static int tcMultiplyPart(WordType *dst, const WordType *src, 1805 WordType multiplier, WordType carry, 1806 unsigned srcParts, unsigned dstParts, bool add); 1807 1808 /// DST = LHS * RHS, where DST has the same width as the operands and is 1809 /// filled with the least significant parts of the result. Returns one if 1810 /// overflow occurred, otherwise zero. DST must be disjoint from both 1811 /// operands. 1812 static int tcMultiply(WordType *, const WordType *, const WordType *, 1813 unsigned); 1814 1815 /// DST = LHS * RHS, where DST has width the sum of the widths of the 1816 /// operands. No overflow occurs. DST must be disjoint from both operands. 1817 static void tcFullMultiply(WordType *, const WordType *, const WordType *, 1818 unsigned, unsigned); 1819 1820 /// If RHS is zero LHS and REMAINDER are left unchanged, return one. 1821 /// Otherwise set LHS to LHS / RHS with the fractional part discarded, set 1822 /// REMAINDER to the remainder, return zero. i.e. 1823 /// 1824 /// OLD_LHS = RHS * LHS + REMAINDER 1825 /// 1826 /// SCRATCH is a bignum of the same size as the operands and result for use by 1827 /// the routine; its contents need not be initialized and are destroyed. LHS, 1828 /// REMAINDER and SCRATCH must be distinct. 1829 static int tcDivide(WordType *lhs, const WordType *rhs, WordType *remainder, 1830 WordType *scratch, unsigned parts); 1831 1832 /// Shift a bignum left Count bits. Shifted in bits are zero. There are no 1833 /// restrictions on Count. 1834 static void tcShiftLeft(WordType *, unsigned Words, unsigned Count); 1835 1836 /// Shift a bignum right Count bits. Shifted in bits are zero. There are no 1837 /// restrictions on Count. 1838 static void tcShiftRight(WordType *, unsigned Words, unsigned Count); 1839 1840 /// Comparison (unsigned) of two bignums. 1841 static int tcCompare(const WordType *, const WordType *, unsigned); 1842 1843 /// Increment a bignum in-place. Return the carry flag. 1844 static WordType tcIncrement(WordType *dst, unsigned parts) { 1845 return tcAddPart(dst, 1, parts); 1846 } 1847 1848 /// Decrement a bignum in-place. Return the borrow flag. 1849 static WordType tcDecrement(WordType *dst, unsigned parts) { 1850 return tcSubtractPart(dst, 1, parts); 1851 } 1852 1853 /// Used to insert APInt objects, or objects that contain APInt objects, into 1854 /// FoldingSets. 1855 void Profile(FoldingSetNodeID &id) const; 1856 1857 /// debug method 1858 void dump() const; 1859 1860 /// Returns whether this instance allocated memory. 1861 bool needsCleanup() const { return !isSingleWord(); } 1862 1863 private: 1864 /// This union is used to store the integer value. When the 1865 /// integer bit-width <= 64, it uses VAL, otherwise it uses pVal. 1866 union { 1867 uint64_t VAL; ///< Used to store the <= 64 bits integer value. 1868 uint64_t *pVal; ///< Used to store the >64 bits integer value. 1869 } U; 1870 1871 unsigned BitWidth = 1; ///< The number of bits in this APInt. 1872 1873 friend struct DenseMapInfo<APInt, void>; 1874 friend class APSInt; 1875 1876 /// This constructor is used only internally for speed of construction of 1877 /// temporaries. It is unsafe since it takes ownership of the pointer, so it 1878 /// is not public. 1879 APInt(uint64_t *val, unsigned bits) : BitWidth(bits) { U.pVal = val; } 1880 1881 /// Determine which word a bit is in. 1882 /// 1883 /// \returns the word position for the specified bit position. 1884 static unsigned whichWord(unsigned bitPosition) { 1885 return bitPosition / APINT_BITS_PER_WORD; 1886 } 1887 1888 /// Determine which bit in a word the specified bit position is in. 1889 static unsigned whichBit(unsigned bitPosition) { 1890 return bitPosition % APINT_BITS_PER_WORD; 1891 } 1892 1893 /// Get a single bit mask. 1894 /// 1895 /// \returns a uint64_t with only bit at "whichBit(bitPosition)" set 1896 /// This method generates and returns a uint64_t (word) mask for a single 1897 /// bit at a specific bit position. This is used to mask the bit in the 1898 /// corresponding word. 1899 static uint64_t maskBit(unsigned bitPosition) { 1900 return 1ULL << whichBit(bitPosition); 1901 } 1902 1903 /// Clear unused high order bits 1904 /// 1905 /// This method is used internally to clear the top "N" bits in the high order 1906 /// word that are not used by the APInt. This is needed after the most 1907 /// significant word is assigned a value to ensure that those bits are 1908 /// zero'd out. 1909 APInt &clearUnusedBits() { 1910 // Compute how many bits are used in the final word. 1911 unsigned WordBits = ((BitWidth - 1) % APINT_BITS_PER_WORD) + 1; 1912 1913 // Mask out the high bits. 1914 uint64_t mask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - WordBits); 1915 if (LLVM_UNLIKELY(BitWidth == 0)) 1916 mask = 0; 1917 1918 if (isSingleWord()) 1919 U.VAL &= mask; 1920 else 1921 U.pVal[getNumWords() - 1] &= mask; 1922 return *this; 1923 } 1924 1925 /// Get the word corresponding to a bit position 1926 /// \returns the corresponding word for the specified bit position. 1927 uint64_t getWord(unsigned bitPosition) const { 1928 return isSingleWord() ? U.VAL : U.pVal[whichWord(bitPosition)]; 1929 } 1930 1931 /// Utility method to change the bit width of this APInt to new bit width, 1932 /// allocating and/or deallocating as necessary. There is no guarantee on the 1933 /// value of any bits upon return. Caller should populate the bits after. 1934 void reallocate(unsigned NewBitWidth); 1935 1936 /// Convert a char array into an APInt 1937 /// 1938 /// \param radix 2, 8, 10, 16, or 36 1939 /// Converts a string into a number. The string must be non-empty 1940 /// and well-formed as a number of the given base. The bit-width 1941 /// must be sufficient to hold the result. 1942 /// 1943 /// This is used by the constructors that take string arguments. 1944 /// 1945 /// StringRef::getAsInteger is superficially similar but (1) does 1946 /// not assume that the string is well-formed and (2) grows the 1947 /// result to hold the input. 1948 void fromString(unsigned numBits, StringRef str, uint8_t radix); 1949 1950 /// An internal division function for dividing APInts. 1951 /// 1952 /// This is used by the toString method to divide by the radix. It simply 1953 /// provides a more convenient form of divide for internal use since KnuthDiv 1954 /// has specific constraints on its inputs. If those constraints are not met 1955 /// then it provides a simpler form of divide. 1956 static void divide(const WordType *LHS, unsigned lhsWords, 1957 const WordType *RHS, unsigned rhsWords, WordType *Quotient, 1958 WordType *Remainder); 1959 1960 /// out-of-line slow case for inline constructor 1961 void initSlowCase(uint64_t val, bool isSigned); 1962 1963 /// shared code between two array constructors 1964 void initFromArray(ArrayRef<uint64_t> array); 1965 1966 /// out-of-line slow case for inline copy constructor 1967 void initSlowCase(const APInt &that); 1968 1969 /// out-of-line slow case for shl 1970 void shlSlowCase(unsigned ShiftAmt); 1971 1972 /// out-of-line slow case for lshr. 1973 void lshrSlowCase(unsigned ShiftAmt); 1974 1975 /// out-of-line slow case for ashr. 1976 void ashrSlowCase(unsigned ShiftAmt); 1977 1978 /// out-of-line slow case for operator= 1979 void assignSlowCase(const APInt &RHS); 1980 1981 /// out-of-line slow case for operator== 1982 bool equalSlowCase(const APInt &RHS) const LLVM_READONLY; 1983 1984 /// out-of-line slow case for countLeadingZeros 1985 unsigned countLeadingZerosSlowCase() const LLVM_READONLY; 1986 1987 /// out-of-line slow case for countLeadingOnes. 1988 unsigned countLeadingOnesSlowCase() const LLVM_READONLY; 1989 1990 /// out-of-line slow case for countTrailingZeros. 1991 unsigned countTrailingZerosSlowCase() const LLVM_READONLY; 1992 1993 /// out-of-line slow case for countTrailingOnes 1994 unsigned countTrailingOnesSlowCase() const LLVM_READONLY; 1995 1996 /// out-of-line slow case for countPopulation 1997 unsigned countPopulationSlowCase() const LLVM_READONLY; 1998 1999 /// out-of-line slow case for intersects. 2000 bool intersectsSlowCase(const APInt &RHS) const LLVM_READONLY; 2001 2002 /// out-of-line slow case for isSubsetOf. 2003 bool isSubsetOfSlowCase(const APInt &RHS) const LLVM_READONLY; 2004 2005 /// out-of-line slow case for setBits. 2006 void setBitsSlowCase(unsigned loBit, unsigned hiBit); 2007 2008 /// out-of-line slow case for flipAllBits. 2009 void flipAllBitsSlowCase(); 2010 2011 /// out-of-line slow case for concat. 2012 APInt concatSlowCase(const APInt &NewLSB) const; 2013 2014 /// out-of-line slow case for operator&=. 2015 void andAssignSlowCase(const APInt &RHS); 2016 2017 /// out-of-line slow case for operator|=. 2018 void orAssignSlowCase(const APInt &RHS); 2019 2020 /// out-of-line slow case for operator^=. 2021 void xorAssignSlowCase(const APInt &RHS); 2022 2023 /// Unsigned comparison. Returns -1, 0, or 1 if this APInt is less than, equal 2024 /// to, or greater than RHS. 2025 int compare(const APInt &RHS) const LLVM_READONLY; 2026 2027 /// Signed comparison. Returns -1, 0, or 1 if this APInt is less than, equal 2028 /// to, or greater than RHS. 2029 int compareSigned(const APInt &RHS) const LLVM_READONLY; 2030 2031 /// @} 2032 }; 2033 2034 inline bool operator==(uint64_t V1, const APInt &V2) { return V2 == V1; } 2035 2036 inline bool operator!=(uint64_t V1, const APInt &V2) { return V2 != V1; } 2037 2038 /// Unary bitwise complement operator. 2039 /// 2040 /// \returns an APInt that is the bitwise complement of \p v. 2041 inline APInt operator~(APInt v) { 2042 v.flipAllBits(); 2043 return v; 2044 } 2045 2046 inline APInt operator&(APInt a, const APInt &b) { 2047 a &= b; 2048 return a; 2049 } 2050 2051 inline APInt operator&(const APInt &a, APInt &&b) { 2052 b &= a; 2053 return std::move(b); 2054 } 2055 2056 inline APInt operator&(APInt a, uint64_t RHS) { 2057 a &= RHS; 2058 return a; 2059 } 2060 2061 inline APInt operator&(uint64_t LHS, APInt b) { 2062 b &= LHS; 2063 return b; 2064 } 2065 2066 inline APInt operator|(APInt a, const APInt &b) { 2067 a |= b; 2068 return a; 2069 } 2070 2071 inline APInt operator|(const APInt &a, APInt &&b) { 2072 b |= a; 2073 return std::move(b); 2074 } 2075 2076 inline APInt operator|(APInt a, uint64_t RHS) { 2077 a |= RHS; 2078 return a; 2079 } 2080 2081 inline APInt operator|(uint64_t LHS, APInt b) { 2082 b |= LHS; 2083 return b; 2084 } 2085 2086 inline APInt operator^(APInt a, const APInt &b) { 2087 a ^= b; 2088 return a; 2089 } 2090 2091 inline APInt operator^(const APInt &a, APInt &&b) { 2092 b ^= a; 2093 return std::move(b); 2094 } 2095 2096 inline APInt operator^(APInt a, uint64_t RHS) { 2097 a ^= RHS; 2098 return a; 2099 } 2100 2101 inline APInt operator^(uint64_t LHS, APInt b) { 2102 b ^= LHS; 2103 return b; 2104 } 2105 2106 inline raw_ostream &operator<<(raw_ostream &OS, const APInt &I) { 2107 I.print(OS, true); 2108 return OS; 2109 } 2110 2111 inline APInt operator-(APInt v) { 2112 v.negate(); 2113 return v; 2114 } 2115 2116 inline APInt operator+(APInt a, const APInt &b) { 2117 a += b; 2118 return a; 2119 } 2120 2121 inline APInt operator+(const APInt &a, APInt &&b) { 2122 b += a; 2123 return std::move(b); 2124 } 2125 2126 inline APInt operator+(APInt a, uint64_t RHS) { 2127 a += RHS; 2128 return a; 2129 } 2130 2131 inline APInt operator+(uint64_t LHS, APInt b) { 2132 b += LHS; 2133 return b; 2134 } 2135 2136 inline APInt operator-(APInt a, const APInt &b) { 2137 a -= b; 2138 return a; 2139 } 2140 2141 inline APInt operator-(const APInt &a, APInt &&b) { 2142 b.negate(); 2143 b += a; 2144 return std::move(b); 2145 } 2146 2147 inline APInt operator-(APInt a, uint64_t RHS) { 2148 a -= RHS; 2149 return a; 2150 } 2151 2152 inline APInt operator-(uint64_t LHS, APInt b) { 2153 b.negate(); 2154 b += LHS; 2155 return b; 2156 } 2157 2158 inline APInt operator*(APInt a, uint64_t RHS) { 2159 a *= RHS; 2160 return a; 2161 } 2162 2163 inline APInt operator*(uint64_t LHS, APInt b) { 2164 b *= LHS; 2165 return b; 2166 } 2167 2168 namespace APIntOps { 2169 2170 /// Determine the smaller of two APInts considered to be signed. 2171 inline const APInt &smin(const APInt &A, const APInt &B) { 2172 return A.slt(B) ? A : B; 2173 } 2174 2175 /// Determine the larger of two APInts considered to be signed. 2176 inline const APInt &smax(const APInt &A, const APInt &B) { 2177 return A.sgt(B) ? A : B; 2178 } 2179 2180 /// Determine the smaller of two APInts considered to be unsigned. 2181 inline const APInt &umin(const APInt &A, const APInt &B) { 2182 return A.ult(B) ? A : B; 2183 } 2184 2185 /// Determine the larger of two APInts considered to be unsigned. 2186 inline const APInt &umax(const APInt &A, const APInt &B) { 2187 return A.ugt(B) ? A : B; 2188 } 2189 2190 /// Compute GCD of two unsigned APInt values. 2191 /// 2192 /// This function returns the greatest common divisor of the two APInt values 2193 /// using Stein's algorithm. 2194 /// 2195 /// \returns the greatest common divisor of A and B. 2196 APInt GreatestCommonDivisor(APInt A, APInt B); 2197 2198 /// Converts the given APInt to a double value. 2199 /// 2200 /// Treats the APInt as an unsigned value for conversion purposes. 2201 inline double RoundAPIntToDouble(const APInt &APIVal) { 2202 return APIVal.roundToDouble(); 2203 } 2204 2205 /// Converts the given APInt to a double value. 2206 /// 2207 /// Treats the APInt as a signed value for conversion purposes. 2208 inline double RoundSignedAPIntToDouble(const APInt &APIVal) { 2209 return APIVal.signedRoundToDouble(); 2210 } 2211 2212 /// Converts the given APInt to a float value. 2213 inline float RoundAPIntToFloat(const APInt &APIVal) { 2214 return float(RoundAPIntToDouble(APIVal)); 2215 } 2216 2217 /// Converts the given APInt to a float value. 2218 /// 2219 /// Treats the APInt as a signed value for conversion purposes. 2220 inline float RoundSignedAPIntToFloat(const APInt &APIVal) { 2221 return float(APIVal.signedRoundToDouble()); 2222 } 2223 2224 /// Converts the given double value into a APInt. 2225 /// 2226 /// This function convert a double value to an APInt value. 2227 APInt RoundDoubleToAPInt(double Double, unsigned width); 2228 2229 /// Converts a float value into a APInt. 2230 /// 2231 /// Converts a float value into an APInt value. 2232 inline APInt RoundFloatToAPInt(float Float, unsigned width) { 2233 return RoundDoubleToAPInt(double(Float), width); 2234 } 2235 2236 /// Return A unsign-divided by B, rounded by the given rounding mode. 2237 APInt RoundingUDiv(const APInt &A, const APInt &B, APInt::Rounding RM); 2238 2239 /// Return A sign-divided by B, rounded by the given rounding mode. 2240 APInt RoundingSDiv(const APInt &A, const APInt &B, APInt::Rounding RM); 2241 2242 /// Let q(n) = An^2 + Bn + C, and BW = bit width of the value range 2243 /// (e.g. 32 for i32). 2244 /// This function finds the smallest number n, such that 2245 /// (a) n >= 0 and q(n) = 0, or 2246 /// (b) n >= 1 and q(n-1) and q(n), when evaluated in the set of all 2247 /// integers, belong to two different intervals [Rk, Rk+R), 2248 /// where R = 2^BW, and k is an integer. 2249 /// The idea here is to find when q(n) "overflows" 2^BW, while at the 2250 /// same time "allowing" subtraction. In unsigned modulo arithmetic a 2251 /// subtraction (treated as addition of negated numbers) would always 2252 /// count as an overflow, but here we want to allow values to decrease 2253 /// and increase as long as they are within the same interval. 2254 /// Specifically, adding of two negative numbers should not cause an 2255 /// overflow (as long as the magnitude does not exceed the bit width). 2256 /// On the other hand, given a positive number, adding a negative 2257 /// number to it can give a negative result, which would cause the 2258 /// value to go from [-2^BW, 0) to [0, 2^BW). In that sense, zero is 2259 /// treated as a special case of an overflow. 2260 /// 2261 /// This function returns std::nullopt if after finding k that minimizes the 2262 /// positive solution to q(n) = kR, both solutions are contained between 2263 /// two consecutive integers. 2264 /// 2265 /// There are cases where q(n) > T, and q(n+1) < T (assuming evaluation 2266 /// in arithmetic modulo 2^BW, and treating the values as signed) by the 2267 /// virtue of *signed* overflow. This function will *not* find such an n, 2268 /// however it may find a value of n satisfying the inequalities due to 2269 /// an *unsigned* overflow (if the values are treated as unsigned). 2270 /// To find a solution for a signed overflow, treat it as a problem of 2271 /// finding an unsigned overflow with a range with of BW-1. 2272 /// 2273 /// The returned value may have a different bit width from the input 2274 /// coefficients. 2275 std::optional<APInt> SolveQuadraticEquationWrap(APInt A, APInt B, APInt C, 2276 unsigned RangeWidth); 2277 2278 /// Compare two values, and if they are different, return the position of the 2279 /// most significant bit that is different in the values. 2280 std::optional<unsigned> GetMostSignificantDifferentBit(const APInt &A, 2281 const APInt &B); 2282 2283 /// Splat/Merge neighboring bits to widen/narrow the bitmask represented 2284 /// by \param A to \param NewBitWidth bits. 2285 /// 2286 /// MatchAnyBits: (Default) 2287 /// e.g. ScaleBitMask(0b0101, 8) -> 0b00110011 2288 /// e.g. ScaleBitMask(0b00011011, 4) -> 0b0111 2289 /// 2290 /// MatchAllBits: 2291 /// e.g. ScaleBitMask(0b0101, 8) -> 0b00110011 2292 /// e.g. ScaleBitMask(0b00011011, 4) -> 0b0001 2293 /// A.getBitwidth() or NewBitWidth must be a whole multiples of the other. 2294 APInt ScaleBitMask(const APInt &A, unsigned NewBitWidth, 2295 bool MatchAllBits = false); 2296 } // namespace APIntOps 2297 2298 // See friend declaration above. This additional declaration is required in 2299 // order to compile LLVM with IBM xlC compiler. 2300 hash_code hash_value(const APInt &Arg); 2301 2302 /// StoreIntToMemory - Fills the StoreBytes bytes of memory starting from Dst 2303 /// with the integer held in IntVal. 2304 void StoreIntToMemory(const APInt &IntVal, uint8_t *Dst, unsigned StoreBytes); 2305 2306 /// LoadIntFromMemory - Loads the integer stored in the LoadBytes bytes starting 2307 /// from Src into IntVal, which is assumed to be wide enough and to hold zero. 2308 void LoadIntFromMemory(APInt &IntVal, const uint8_t *Src, unsigned LoadBytes); 2309 2310 /// Provide DenseMapInfo for APInt. 2311 template <> struct DenseMapInfo<APInt, void> { 2312 static inline APInt getEmptyKey() { 2313 APInt V(nullptr, 0); 2314 V.U.VAL = ~0ULL; 2315 return V; 2316 } 2317 2318 static inline APInt getTombstoneKey() { 2319 APInt V(nullptr, 0); 2320 V.U.VAL = ~1ULL; 2321 return V; 2322 } 2323 2324 static unsigned getHashValue(const APInt &Key); 2325 2326 static bool isEqual(const APInt &LHS, const APInt &RHS) { 2327 return LHS.getBitWidth() == RHS.getBitWidth() && LHS == RHS; 2328 } 2329 }; 2330 2331 } // namespace llvm 2332 2333 #endif 2334