1 //===-- llvm/ADT/APInt.h - For Arbitrary Precision Integer -----*- C++ -*--===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file implements a class to represent arbitrary precision integral 11 // 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/ADT/ArrayRef.h" 19 #include "llvm/Support/Compiler.h" 20 #include "llvm/Support/MathExtras.h" 21 #include <cassert> 22 #include <climits> 23 #include <cstring> 24 #include <string> 25 26 namespace llvm { 27 class Deserializer; 28 class FoldingSetNodeID; 29 class Serializer; 30 class StringRef; 31 class hash_code; 32 class raw_ostream; 33 34 template<typename T> 35 class SmallVectorImpl; 36 37 // An unsigned host type used as a single part of a multi-part 38 // bignum. 39 typedef uint64_t integerPart; 40 41 const unsigned int host_char_bit = 8; 42 const unsigned int integerPartWidth = host_char_bit * 43 static_cast<unsigned int>(sizeof(integerPart)); 44 45 //===----------------------------------------------------------------------===// 46 // APInt Class 47 //===----------------------------------------------------------------------===// 48 49 /// APInt - This class represents arbitrary precision constant integral values. 50 /// It is a functional replacement for common case unsigned integer type like 51 /// "unsigned", "unsigned long" or "uint64_t", but also allows non-byte-width 52 /// integer sizes and large integer value types such as 3-bits, 15-bits, or more 53 /// than 64-bits of precision. APInt provides a variety of arithmetic operators 54 /// and methods to manipulate integer values of any bit-width. It supports both 55 /// the typical integer arithmetic and comparison operations as well as bitwise 56 /// manipulation. 57 /// 58 /// The class has several invariants worth noting: 59 /// * All bit, byte, and word positions are zero-based. 60 /// * Once the bit width is set, it doesn't change except by the Truncate, 61 /// SignExtend, or ZeroExtend operations. 62 /// * All binary operators must be on APInt instances of the same bit width. 63 /// Attempting to use these operators on instances with different bit 64 /// widths will yield an assertion. 65 /// * The value is stored canonically as an unsigned value. For operations 66 /// where it makes a difference, there are both signed and unsigned variants 67 /// of the operation. For example, sdiv and udiv. However, because the bit 68 /// widths must be the same, operations such as Mul and Add produce the same 69 /// results regardless of whether the values are interpreted as signed or 70 /// not. 71 /// * In general, the class tries to follow the style of computation that LLVM 72 /// uses in its IR. This simplifies its use for LLVM. 73 /// 74 /// @brief Class for arbitrary precision integers. 75 class APInt { 76 unsigned BitWidth; ///< The number of bits in this APInt. 77 78 /// This union is used to store the integer value. When the 79 /// integer bit-width <= 64, it uses VAL, otherwise it uses pVal. 80 union { 81 uint64_t VAL; ///< Used to store the <= 64 bits integer value. 82 uint64_t *pVal; ///< Used to store the >64 bits integer value. 83 }; 84 85 /// This enum is used to hold the constants we needed for APInt. 86 enum { 87 /// Bits in a word 88 APINT_BITS_PER_WORD = static_cast<unsigned int>(sizeof(uint64_t)) * 89 CHAR_BIT, 90 /// Byte size of a word 91 APINT_WORD_SIZE = static_cast<unsigned int>(sizeof(uint64_t)) 92 }; 93 94 /// This constructor is used only internally for speed of construction of 95 /// temporaries. It is unsafe for general use so it is not public. 96 /// @brief Fast internal constructor 97 APInt(uint64_t* val, unsigned bits) : BitWidth(bits), pVal(val) { } 98 99 /// @returns true if the number of bits <= 64, false otherwise. 100 /// @brief Determine if this APInt just has one word to store value. 101 bool isSingleWord() const { 102 return BitWidth <= APINT_BITS_PER_WORD; 103 } 104 105 /// @returns the word position for the specified bit position. 106 /// @brief Determine which word a bit is in. 107 static unsigned whichWord(unsigned bitPosition) { 108 return bitPosition / APINT_BITS_PER_WORD; 109 } 110 111 /// @returns the bit position in a word for the specified bit position 112 /// in the APInt. 113 /// @brief Determine which bit in a word a bit is in. 114 static unsigned whichBit(unsigned bitPosition) { 115 return bitPosition % APINT_BITS_PER_WORD; 116 } 117 118 /// This method generates and returns a uint64_t (word) mask for a single 119 /// bit at a specific bit position. This is used to mask the bit in the 120 /// corresponding word. 121 /// @returns a uint64_t with only bit at "whichBit(bitPosition)" set 122 /// @brief Get a single bit mask. 123 static uint64_t maskBit(unsigned bitPosition) { 124 return 1ULL << whichBit(bitPosition); 125 } 126 127 /// This method is used internally to clear the to "N" bits in the high order 128 /// word that are not used by the APInt. This is needed after the most 129 /// significant word is assigned a value to ensure that those bits are 130 /// zero'd out. 131 /// @brief Clear unused high order bits 132 APInt& clearUnusedBits() { 133 // Compute how many bits are used in the final word 134 unsigned wordBits = BitWidth % APINT_BITS_PER_WORD; 135 if (wordBits == 0) 136 // If all bits are used, we want to leave the value alone. This also 137 // avoids the undefined behavior of >> when the shift is the same size as 138 // the word size (64). 139 return *this; 140 141 // Mask out the high bits. 142 uint64_t mask = ~uint64_t(0ULL) >> (APINT_BITS_PER_WORD - wordBits); 143 if (isSingleWord()) 144 VAL &= mask; 145 else 146 pVal[getNumWords() - 1] &= mask; 147 return *this; 148 } 149 150 /// @returns the corresponding word for the specified bit position. 151 /// @brief Get the word corresponding to a bit position 152 uint64_t getWord(unsigned bitPosition) const { 153 return isSingleWord() ? VAL : pVal[whichWord(bitPosition)]; 154 } 155 156 /// Converts a string into a number. The string must be non-empty 157 /// and well-formed as a number of the given base. The bit-width 158 /// must be sufficient to hold the result. 159 /// 160 /// This is used by the constructors that take string arguments. 161 /// 162 /// StringRef::getAsInteger is superficially similar but (1) does 163 /// not assume that the string is well-formed and (2) grows the 164 /// result to hold the input. 165 /// 166 /// @param radix 2, 8, 10, 16, or 36 167 /// @brief Convert a char array into an APInt 168 void fromString(unsigned numBits, StringRef str, uint8_t radix); 169 170 /// This is used by the toString method to divide by the radix. It simply 171 /// provides a more convenient form of divide for internal use since KnuthDiv 172 /// has specific constraints on its inputs. If those constraints are not met 173 /// then it provides a simpler form of divide. 174 /// @brief An internal division function for dividing APInts. 175 static void divide(const APInt LHS, unsigned lhsWords, 176 const APInt &RHS, unsigned rhsWords, 177 APInt *Quotient, APInt *Remainder); 178 179 /// out-of-line slow case for inline constructor 180 void initSlowCase(unsigned numBits, uint64_t val, bool isSigned); 181 182 /// shared code between two array constructors 183 void initFromArray(ArrayRef<uint64_t> array); 184 185 /// out-of-line slow case for inline copy constructor 186 void initSlowCase(const APInt& that); 187 188 /// out-of-line slow case for shl 189 APInt shlSlowCase(unsigned shiftAmt) const; 190 191 /// out-of-line slow case for operator& 192 APInt AndSlowCase(const APInt& RHS) const; 193 194 /// out-of-line slow case for operator| 195 APInt OrSlowCase(const APInt& RHS) const; 196 197 /// out-of-line slow case for operator^ 198 APInt XorSlowCase(const APInt& RHS) const; 199 200 /// out-of-line slow case for operator= 201 APInt& AssignSlowCase(const APInt& RHS); 202 203 /// out-of-line slow case for operator== 204 bool EqualSlowCase(const APInt& RHS) const; 205 206 /// out-of-line slow case for operator== 207 bool EqualSlowCase(uint64_t Val) const; 208 209 /// out-of-line slow case for countLeadingZeros 210 unsigned countLeadingZerosSlowCase() const; 211 212 /// out-of-line slow case for countTrailingOnes 213 unsigned countTrailingOnesSlowCase() const; 214 215 /// out-of-line slow case for countPopulation 216 unsigned countPopulationSlowCase() const; 217 218 public: 219 /// @name Constructors 220 /// @{ 221 /// If isSigned is true then val is treated as if it were a signed value 222 /// (i.e. as an int64_t) and the appropriate sign extension to the bit width 223 /// will be done. Otherwise, no sign extension occurs (high order bits beyond 224 /// the range of val are zero filled). 225 /// @param numBits the bit width of the constructed APInt 226 /// @param val the initial value of the APInt 227 /// @param isSigned how to treat signedness of val 228 /// @brief Create a new APInt of numBits width, initialized as val. 229 APInt(unsigned numBits, uint64_t val, bool isSigned = false) 230 : BitWidth(numBits), VAL(0) { 231 assert(BitWidth && "bitwidth too small"); 232 if (isSingleWord()) 233 VAL = val; 234 else 235 initSlowCase(numBits, val, isSigned); 236 clearUnusedBits(); 237 } 238 239 /// Note that bigVal.size() can be smaller or larger than the corresponding 240 /// bit width but any extraneous bits will be dropped. 241 /// @param numBits the bit width of the constructed APInt 242 /// @param bigVal a sequence of words to form the initial value of the APInt 243 /// @brief Construct an APInt of numBits width, initialized as bigVal[]. 244 APInt(unsigned numBits, ArrayRef<uint64_t> bigVal); 245 /// Equivalent to APInt(numBits, ArrayRef<uint64_t>(bigVal, numWords)), but 246 /// deprecated because this constructor is prone to ambiguity with the 247 /// APInt(unsigned, uint64_t, bool) constructor. 248 /// 249 /// If this overload is ever deleted, care should be taken to prevent calls 250 /// from being incorrectly captured by the APInt(unsigned, uint64_t, bool) 251 /// constructor. 252 APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[]); 253 254 /// This constructor interprets the string \p str in the given radix. The 255 /// interpretation stops when the first character that is not suitable for the 256 /// radix is encountered, or the end of the string. Acceptable radix values 257 /// are 2, 8, 10, 16, and 36. It is an error for the value implied by the 258 /// string to require more bits than numBits. 259 /// 260 /// @param numBits the bit width of the constructed APInt 261 /// @param str the string to be interpreted 262 /// @param radix the radix to use for the conversion 263 /// @brief Construct an APInt from a string representation. 264 APInt(unsigned numBits, StringRef str, uint8_t radix); 265 266 /// Simply makes *this a copy of that. 267 /// @brief Copy Constructor. 268 APInt(const APInt& that) 269 : BitWidth(that.BitWidth), VAL(0) { 270 assert(BitWidth && "bitwidth too small"); 271 if (isSingleWord()) 272 VAL = that.VAL; 273 else 274 initSlowCase(that); 275 } 276 277 #if LLVM_HAS_RVALUE_REFERENCES 278 /// @brief Move Constructor. 279 APInt(APInt&& that) : BitWidth(that.BitWidth), VAL(that.VAL) { 280 that.BitWidth = 0; 281 } 282 #endif 283 284 /// @brief Destructor. 285 ~APInt() { 286 if (!isSingleWord()) 287 delete [] pVal; 288 } 289 290 /// Default constructor that creates an uninitialized APInt. This is useful 291 /// for object deserialization (pair this with the static method Read). 292 explicit APInt() : BitWidth(1) {} 293 294 /// Profile - Used to insert APInt objects, or objects that contain APInt 295 /// objects, into FoldingSets. 296 void Profile(FoldingSetNodeID& id) const; 297 298 /// @} 299 /// @name Value Tests 300 /// @{ 301 /// This tests the high bit of this APInt to determine if it is set. 302 /// @returns true if this APInt is negative, false otherwise 303 /// @brief Determine sign of this APInt. 304 bool isNegative() const { 305 return (*this)[BitWidth - 1]; 306 } 307 308 /// This tests the high bit of the APInt to determine if it is unset. 309 /// @brief Determine if this APInt Value is non-negative (>= 0) 310 bool isNonNegative() const { 311 return !isNegative(); 312 } 313 314 /// This tests if the value of this APInt is positive (> 0). Note 315 /// that 0 is not a positive value. 316 /// @returns true if this APInt is positive. 317 /// @brief Determine if this APInt Value is positive. 318 bool isStrictlyPositive() const { 319 return isNonNegative() && !!*this; 320 } 321 322 /// This checks to see if the value has all bits of the APInt are set or not. 323 /// @brief Determine if all bits are set 324 bool isAllOnesValue() const { 325 return countPopulation() == BitWidth; 326 } 327 328 /// This checks to see if the value of this APInt is the maximum unsigned 329 /// value for the APInt's bit width. 330 /// @brief Determine if this is the largest unsigned value. 331 bool isMaxValue() const { 332 return countPopulation() == BitWidth; 333 } 334 335 /// This checks to see if the value of this APInt is the maximum signed 336 /// value for the APInt's bit width. 337 /// @brief Determine if this is the largest signed value. 338 bool isMaxSignedValue() const { 339 return BitWidth == 1 ? VAL == 0 : 340 !isNegative() && countPopulation() == BitWidth - 1; 341 } 342 343 /// This checks to see if the value of this APInt is the minimum unsigned 344 /// value for the APInt's bit width. 345 /// @brief Determine if this is the smallest unsigned value. 346 bool isMinValue() const { 347 return !*this; 348 } 349 350 /// This checks to see if the value of this APInt is the minimum signed 351 /// value for the APInt's bit width. 352 /// @brief Determine if this is the smallest signed value. 353 bool isMinSignedValue() const { 354 return BitWidth == 1 ? VAL == 1 : isNegative() && isPowerOf2(); 355 } 356 357 /// @brief Check if this APInt has an N-bits unsigned integer value. 358 bool isIntN(unsigned N) const { 359 assert(N && "N == 0 ???"); 360 return getActiveBits() <= N; 361 } 362 363 /// @brief Check if this APInt has an N-bits signed integer value. 364 bool isSignedIntN(unsigned N) const { 365 assert(N && "N == 0 ???"); 366 return getMinSignedBits() <= N; 367 } 368 369 /// @returns true if the argument APInt value is a power of two > 0. 370 bool isPowerOf2() const { 371 if (isSingleWord()) 372 return isPowerOf2_64(VAL); 373 return countPopulationSlowCase() == 1; 374 } 375 376 /// isSignBit - Return true if this is the value returned by getSignBit. 377 bool isSignBit() const { return isMinSignedValue(); } 378 379 /// This converts the APInt to a boolean value as a test against zero. 380 /// @brief Boolean conversion function. 381 bool getBoolValue() const { 382 return !!*this; 383 } 384 385 /// getLimitedValue - If this value is smaller than the specified limit, 386 /// return it, otherwise return the limit value. This causes the value 387 /// to saturate to the limit. 388 uint64_t getLimitedValue(uint64_t Limit = ~0ULL) const { 389 return (getActiveBits() > 64 || getZExtValue() > Limit) ? 390 Limit : getZExtValue(); 391 } 392 393 /// @} 394 /// @name Value Generators 395 /// @{ 396 /// @brief Gets maximum unsigned value of APInt for specific bit width. 397 static APInt getMaxValue(unsigned numBits) { 398 return getAllOnesValue(numBits); 399 } 400 401 /// @brief Gets maximum signed value of APInt for a specific bit width. 402 static APInt getSignedMaxValue(unsigned numBits) { 403 APInt API = getAllOnesValue(numBits); 404 API.clearBit(numBits - 1); 405 return API; 406 } 407 408 /// @brief Gets minimum unsigned value of APInt for a specific bit width. 409 static APInt getMinValue(unsigned numBits) { 410 return APInt(numBits, 0); 411 } 412 413 /// @brief Gets minimum signed value of APInt for a specific bit width. 414 static APInt getSignedMinValue(unsigned numBits) { 415 APInt API(numBits, 0); 416 API.setBit(numBits - 1); 417 return API; 418 } 419 420 /// getSignBit - This is just a wrapper function of getSignedMinValue(), and 421 /// it helps code readability when we want to get a SignBit. 422 /// @brief Get the SignBit for a specific bit width. 423 static APInt getSignBit(unsigned BitWidth) { 424 return getSignedMinValue(BitWidth); 425 } 426 427 /// @returns the all-ones value for an APInt of the specified bit-width. 428 /// @brief Get the all-ones value. 429 static APInt getAllOnesValue(unsigned numBits) { 430 return APInt(numBits, UINT64_MAX, true); 431 } 432 433 /// @returns the '0' value for an APInt of the specified bit-width. 434 /// @brief Get the '0' value. 435 static APInt getNullValue(unsigned numBits) { 436 return APInt(numBits, 0); 437 } 438 439 /// Get an APInt with the same BitWidth as this APInt, just zero mask 440 /// the low bits and right shift to the least significant bit. 441 /// @returns the high "numBits" bits of this APInt. 442 APInt getHiBits(unsigned numBits) const; 443 444 /// Get an APInt with the same BitWidth as this APInt, just zero mask 445 /// the high bits. 446 /// @returns the low "numBits" bits of this APInt. 447 APInt getLoBits(unsigned numBits) const; 448 449 /// getOneBitSet - Return an APInt with exactly one bit set in the result. 450 static APInt getOneBitSet(unsigned numBits, unsigned BitNo) { 451 APInt Res(numBits, 0); 452 Res.setBit(BitNo); 453 return Res; 454 } 455 456 /// Constructs an APInt value that has a contiguous range of bits set. The 457 /// bits from loBit (inclusive) to hiBit (exclusive) will be set. All other 458 /// bits will be zero. For example, with parameters(32, 0, 16) you would get 459 /// 0x0000FFFF. If hiBit is less than loBit then the set bits "wrap". For 460 /// example, with parameters (32, 28, 4), you would get 0xF000000F. 461 /// @param numBits the intended bit width of the result 462 /// @param loBit the index of the lowest bit set. 463 /// @param hiBit the index of the highest bit set. 464 /// @returns An APInt value with the requested bits set. 465 /// @brief Get a value with a block of bits set. 466 static APInt getBitsSet(unsigned numBits, unsigned loBit, unsigned hiBit) { 467 assert(hiBit <= numBits && "hiBit out of range"); 468 assert(loBit < numBits && "loBit out of range"); 469 if (hiBit < loBit) 470 return getLowBitsSet(numBits, hiBit) | 471 getHighBitsSet(numBits, numBits-loBit); 472 return getLowBitsSet(numBits, hiBit-loBit).shl(loBit); 473 } 474 475 /// Constructs an APInt value that has the top hiBitsSet bits set. 476 /// @param numBits the bitwidth of the result 477 /// @param hiBitsSet the number of high-order bits set in the result. 478 /// @brief Get a value with high bits set 479 static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet) { 480 assert(hiBitsSet <= numBits && "Too many bits to set!"); 481 // Handle a degenerate case, to avoid shifting by word size 482 if (hiBitsSet == 0) 483 return APInt(numBits, 0); 484 unsigned shiftAmt = numBits - hiBitsSet; 485 // For small values, return quickly 486 if (numBits <= APINT_BITS_PER_WORD) 487 return APInt(numBits, ~0ULL << shiftAmt); 488 return getAllOnesValue(numBits).shl(shiftAmt); 489 } 490 491 /// Constructs an APInt value that has the bottom loBitsSet bits set. 492 /// @param numBits the bitwidth of the result 493 /// @param loBitsSet the number of low-order bits set in the result. 494 /// @brief Get a value with low bits set 495 static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet) { 496 assert(loBitsSet <= numBits && "Too many bits to set!"); 497 // Handle a degenerate case, to avoid shifting by word size 498 if (loBitsSet == 0) 499 return APInt(numBits, 0); 500 if (loBitsSet == APINT_BITS_PER_WORD) 501 return APInt(numBits, UINT64_MAX); 502 // For small values, return quickly. 503 if (loBitsSet <= APINT_BITS_PER_WORD) 504 return APInt(numBits, UINT64_MAX >> (APINT_BITS_PER_WORD - loBitsSet)); 505 return getAllOnesValue(numBits).lshr(numBits - loBitsSet); 506 } 507 508 /// \brief Return a value containing V broadcasted over NewLen bits. 509 static APInt getSplat(unsigned NewLen, const APInt &V) { 510 assert(NewLen >= V.getBitWidth() && "Can't splat to smaller bit width!"); 511 512 APInt Val = V.zextOrSelf(NewLen); 513 for (unsigned I = V.getBitWidth(); I < NewLen; I <<= 1) 514 Val |= Val << I; 515 516 return Val; 517 } 518 519 /// \brief Determine if two APInts have the same value, after zero-extending 520 /// one of them (if needed!) to ensure that the bit-widths match. 521 static bool isSameValue(const APInt &I1, const APInt &I2) { 522 if (I1.getBitWidth() == I2.getBitWidth()) 523 return I1 == I2; 524 525 if (I1.getBitWidth() > I2.getBitWidth()) 526 return I1 == I2.zext(I1.getBitWidth()); 527 528 return I1.zext(I2.getBitWidth()) == I2; 529 } 530 531 /// \brief Overload to compute a hash_code for an APInt value. 532 friend hash_code hash_value(const APInt &Arg); 533 534 /// This function returns a pointer to the internal storage of the APInt. 535 /// This is useful for writing out the APInt in binary form without any 536 /// conversions. 537 const uint64_t* getRawData() const { 538 if (isSingleWord()) 539 return &VAL; 540 return &pVal[0]; 541 } 542 543 /// @} 544 /// @name Unary Operators 545 /// @{ 546 /// @returns a new APInt value representing *this incremented by one 547 /// @brief Postfix increment operator. 548 const APInt operator++(int) { 549 APInt API(*this); 550 ++(*this); 551 return API; 552 } 553 554 /// @returns *this incremented by one 555 /// @brief Prefix increment operator. 556 APInt& operator++(); 557 558 /// @returns a new APInt representing *this decremented by one. 559 /// @brief Postfix decrement operator. 560 const APInt operator--(int) { 561 APInt API(*this); 562 --(*this); 563 return API; 564 } 565 566 /// @returns *this decremented by one. 567 /// @brief Prefix decrement operator. 568 APInt& operator--(); 569 570 /// Performs a bitwise complement operation on this APInt. 571 /// @returns an APInt that is the bitwise complement of *this 572 /// @brief Unary bitwise complement operator. 573 APInt operator~() const { 574 APInt Result(*this); 575 Result.flipAllBits(); 576 return Result; 577 } 578 579 /// Negates *this using two's complement logic. 580 /// @returns An APInt value representing the negation of *this. 581 /// @brief Unary negation operator 582 APInt operator-() const { 583 return APInt(BitWidth, 0) - (*this); 584 } 585 586 /// Performs logical negation operation on this APInt. 587 /// @returns true if *this is zero, false otherwise. 588 /// @brief Logical negation operator. 589 bool operator!() const { 590 if (isSingleWord()) 591 return !VAL; 592 593 for (unsigned i = 0; i != getNumWords(); ++i) 594 if (pVal[i]) 595 return false; 596 return true; 597 } 598 599 /// @} 600 /// @name Assignment Operators 601 /// @{ 602 /// @returns *this after assignment of RHS. 603 /// @brief Copy assignment operator. 604 APInt& operator=(const APInt& RHS) { 605 // If the bitwidths are the same, we can avoid mucking with memory 606 if (isSingleWord() && RHS.isSingleWord()) { 607 VAL = RHS.VAL; 608 BitWidth = RHS.BitWidth; 609 return clearUnusedBits(); 610 } 611 612 return AssignSlowCase(RHS); 613 } 614 615 #if LLVM_HAS_RVALUE_REFERENCES 616 /// @brief Move assignment operator. 617 APInt& operator=(APInt&& that) { 618 if (!isSingleWord()) 619 delete [] pVal; 620 621 BitWidth = that.BitWidth; 622 VAL = that.VAL; 623 624 that.BitWidth = 0; 625 626 return *this; 627 } 628 #endif 629 630 /// The RHS value is assigned to *this. If the significant bits in RHS exceed 631 /// the bit width, the excess bits are truncated. If the bit width is larger 632 /// than 64, the value is zero filled in the unspecified high order bits. 633 /// @returns *this after assignment of RHS value. 634 /// @brief Assignment operator. 635 APInt& operator=(uint64_t RHS); 636 637 /// Performs a bitwise AND operation on this APInt and RHS. The result is 638 /// assigned to *this. 639 /// @returns *this after ANDing with RHS. 640 /// @brief Bitwise AND assignment operator. 641 APInt& operator&=(const APInt& RHS); 642 643 /// Performs a bitwise OR operation on this APInt and RHS. The result is 644 /// assigned *this; 645 /// @returns *this after ORing with RHS. 646 /// @brief Bitwise OR assignment operator. 647 APInt& operator|=(const APInt& RHS); 648 649 /// Performs a bitwise OR operation on this APInt and RHS. RHS is 650 /// logically zero-extended or truncated to match the bit-width of 651 /// the LHS. 652 /// 653 /// @brief Bitwise OR assignment operator. 654 APInt& operator|=(uint64_t RHS) { 655 if (isSingleWord()) { 656 VAL |= RHS; 657 clearUnusedBits(); 658 } else { 659 pVal[0] |= RHS; 660 } 661 return *this; 662 } 663 664 /// Performs a bitwise XOR operation on this APInt and RHS. The result is 665 /// assigned to *this. 666 /// @returns *this after XORing with RHS. 667 /// @brief Bitwise XOR assignment operator. 668 APInt& operator^=(const APInt& RHS); 669 670 /// Multiplies this APInt by RHS and assigns the result to *this. 671 /// @returns *this 672 /// @brief Multiplication assignment operator. 673 APInt& operator*=(const APInt& RHS); 674 675 /// Adds RHS to *this and assigns the result to *this. 676 /// @returns *this 677 /// @brief Addition assignment operator. 678 APInt& operator+=(const APInt& RHS); 679 680 /// Subtracts RHS from *this and assigns the result to *this. 681 /// @returns *this 682 /// @brief Subtraction assignment operator. 683 APInt& operator-=(const APInt& RHS); 684 685 /// Shifts *this left by shiftAmt and assigns the result to *this. 686 /// @returns *this after shifting left by shiftAmt 687 /// @brief Left-shift assignment function. 688 APInt& operator<<=(unsigned shiftAmt) { 689 *this = shl(shiftAmt); 690 return *this; 691 } 692 693 /// @} 694 /// @name Binary Operators 695 /// @{ 696 /// Performs a bitwise AND operation on *this and RHS. 697 /// @returns An APInt value representing the bitwise AND of *this and RHS. 698 /// @brief Bitwise AND operator. 699 APInt operator&(const APInt& RHS) const { 700 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 701 if (isSingleWord()) 702 return APInt(getBitWidth(), VAL & RHS.VAL); 703 return AndSlowCase(RHS); 704 } 705 APInt And(const APInt& RHS) const { 706 return this->operator&(RHS); 707 } 708 709 /// Performs a bitwise OR operation on *this and RHS. 710 /// @returns An APInt value representing the bitwise OR of *this and RHS. 711 /// @brief Bitwise OR operator. 712 APInt operator|(const APInt& RHS) const { 713 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 714 if (isSingleWord()) 715 return APInt(getBitWidth(), VAL | RHS.VAL); 716 return OrSlowCase(RHS); 717 } 718 APInt Or(const APInt& RHS) const { 719 return this->operator|(RHS); 720 } 721 722 /// Performs a bitwise XOR operation on *this and RHS. 723 /// @returns An APInt value representing the bitwise XOR of *this and RHS. 724 /// @brief Bitwise XOR operator. 725 APInt operator^(const APInt& RHS) const { 726 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 727 if (isSingleWord()) 728 return APInt(BitWidth, VAL ^ RHS.VAL); 729 return XorSlowCase(RHS); 730 } 731 APInt Xor(const APInt& RHS) const { 732 return this->operator^(RHS); 733 } 734 735 /// Multiplies this APInt by RHS and returns the result. 736 /// @brief Multiplication operator. 737 APInt operator*(const APInt& RHS) const; 738 739 /// Adds RHS to this APInt and returns the result. 740 /// @brief Addition operator. 741 APInt operator+(const APInt& RHS) const; 742 APInt operator+(uint64_t RHS) const { 743 return (*this) + APInt(BitWidth, RHS); 744 } 745 746 /// Subtracts RHS from this APInt and returns the result. 747 /// @brief Subtraction operator. 748 APInt operator-(const APInt& RHS) const; 749 APInt operator-(uint64_t RHS) const { 750 return (*this) - APInt(BitWidth, RHS); 751 } 752 753 APInt operator<<(unsigned Bits) const { 754 return shl(Bits); 755 } 756 757 APInt operator<<(const APInt &Bits) const { 758 return shl(Bits); 759 } 760 761 /// Arithmetic right-shift this APInt by shiftAmt. 762 /// @brief Arithmetic right-shift function. 763 APInt ashr(unsigned shiftAmt) const; 764 765 /// Logical right-shift this APInt by shiftAmt. 766 /// @brief Logical right-shift function. 767 APInt lshr(unsigned shiftAmt) const; 768 769 /// Left-shift this APInt by shiftAmt. 770 /// @brief Left-shift function. 771 APInt shl(unsigned shiftAmt) const { 772 assert(shiftAmt <= BitWidth && "Invalid shift amount"); 773 if (isSingleWord()) { 774 if (shiftAmt >= BitWidth) 775 return APInt(BitWidth, 0); // avoid undefined shift results 776 return APInt(BitWidth, VAL << shiftAmt); 777 } 778 return shlSlowCase(shiftAmt); 779 } 780 781 /// @brief Rotate left by rotateAmt. 782 APInt rotl(unsigned rotateAmt) const; 783 784 /// @brief Rotate right by rotateAmt. 785 APInt rotr(unsigned rotateAmt) const; 786 787 /// Arithmetic right-shift this APInt by shiftAmt. 788 /// @brief Arithmetic right-shift function. 789 APInt ashr(const APInt &shiftAmt) const; 790 791 /// Logical right-shift this APInt by shiftAmt. 792 /// @brief Logical right-shift function. 793 APInt lshr(const APInt &shiftAmt) const; 794 795 /// Left-shift this APInt by shiftAmt. 796 /// @brief Left-shift function. 797 APInt shl(const APInt &shiftAmt) const; 798 799 /// @brief Rotate left by rotateAmt. 800 APInt rotl(const APInt &rotateAmt) const; 801 802 /// @brief Rotate right by rotateAmt. 803 APInt rotr(const APInt &rotateAmt) const; 804 805 /// Perform an unsigned divide operation on this APInt by RHS. Both this and 806 /// RHS are treated as unsigned quantities for purposes of this division. 807 /// @returns a new APInt value containing the division result 808 /// @brief Unsigned division operation. 809 APInt udiv(const APInt &RHS) const; 810 811 /// Signed divide this APInt by APInt RHS. 812 /// @brief Signed division function for APInt. 813 APInt sdiv(const APInt &RHS) const; 814 815 /// Perform an unsigned remainder operation on this APInt with RHS being the 816 /// divisor. Both this and RHS are treated as unsigned quantities for purposes 817 /// of this operation. Note that this is a true remainder operation and not 818 /// a modulo operation because the sign follows the sign of the dividend 819 /// which is *this. 820 /// @returns a new APInt value containing the remainder result 821 /// @brief Unsigned remainder operation. 822 APInt urem(const APInt &RHS) const; 823 824 /// Signed remainder operation on APInt. 825 /// @brief Function for signed remainder operation. 826 APInt srem(const APInt &RHS) const; 827 828 /// Sometimes it is convenient to divide two APInt values and obtain both the 829 /// quotient and remainder. This function does both operations in the same 830 /// computation making it a little more efficient. The pair of input arguments 831 /// may overlap with the pair of output arguments. It is safe to call 832 /// udivrem(X, Y, X, Y), for example. 833 /// @brief Dual division/remainder interface. 834 static void udivrem(const APInt &LHS, const APInt &RHS, 835 APInt &Quotient, APInt &Remainder); 836 837 static void sdivrem(const APInt &LHS, const APInt &RHS, 838 APInt &Quotient, APInt &Remainder); 839 840 841 // Operations that return overflow indicators. 842 APInt sadd_ov(const APInt &RHS, bool &Overflow) const; 843 APInt uadd_ov(const APInt &RHS, bool &Overflow) const; 844 APInt ssub_ov(const APInt &RHS, bool &Overflow) const; 845 APInt usub_ov(const APInt &RHS, bool &Overflow) const; 846 APInt sdiv_ov(const APInt &RHS, bool &Overflow) const; 847 APInt smul_ov(const APInt &RHS, bool &Overflow) const; 848 APInt umul_ov(const APInt &RHS, bool &Overflow) const; 849 APInt sshl_ov(unsigned Amt, bool &Overflow) const; 850 851 /// @returns the bit value at bitPosition 852 /// @brief Array-indexing support. 853 bool operator[](unsigned bitPosition) const { 854 assert(bitPosition < getBitWidth() && "Bit position out of bounds!"); 855 return (maskBit(bitPosition) & 856 (isSingleWord() ? VAL : pVal[whichWord(bitPosition)])) != 0; 857 } 858 859 /// @} 860 /// @name Comparison Operators 861 /// @{ 862 /// Compares this APInt with RHS for the validity of the equality 863 /// relationship. 864 /// @brief Equality operator. 865 bool operator==(const APInt& RHS) const { 866 assert(BitWidth == RHS.BitWidth && "Comparison requires equal bit widths"); 867 if (isSingleWord()) 868 return VAL == RHS.VAL; 869 return EqualSlowCase(RHS); 870 } 871 872 /// Compares this APInt with a uint64_t for the validity of the equality 873 /// relationship. 874 /// @returns true if *this == Val 875 /// @brief Equality operator. 876 bool operator==(uint64_t Val) const { 877 if (isSingleWord()) 878 return VAL == Val; 879 return EqualSlowCase(Val); 880 } 881 882 /// Compares this APInt with RHS for the validity of the equality 883 /// relationship. 884 /// @returns true if *this == Val 885 /// @brief Equality comparison. 886 bool eq(const APInt &RHS) const { 887 return (*this) == RHS; 888 } 889 890 /// Compares this APInt with RHS for the validity of the inequality 891 /// relationship. 892 /// @returns true if *this != Val 893 /// @brief Inequality operator. 894 bool operator!=(const APInt& RHS) const { 895 return !((*this) == RHS); 896 } 897 898 /// Compares this APInt with a uint64_t for the validity of the inequality 899 /// relationship. 900 /// @returns true if *this != Val 901 /// @brief Inequality operator. 902 bool operator!=(uint64_t Val) const { 903 return !((*this) == Val); 904 } 905 906 /// Compares this APInt with RHS for the validity of the inequality 907 /// relationship. 908 /// @returns true if *this != Val 909 /// @brief Inequality comparison 910 bool ne(const APInt &RHS) const { 911 return !((*this) == RHS); 912 } 913 914 /// Regards both *this and RHS as unsigned quantities and compares them for 915 /// the validity of the less-than relationship. 916 /// @returns true if *this < RHS when both are considered unsigned. 917 /// @brief Unsigned less than comparison 918 bool ult(const APInt &RHS) const; 919 920 /// Regards both *this as an unsigned quantity and compares it with RHS for 921 /// the validity of the less-than relationship. 922 /// @returns true if *this < RHS when considered unsigned. 923 /// @brief Unsigned less than comparison 924 bool ult(uint64_t RHS) const { 925 return ult(APInt(getBitWidth(), RHS)); 926 } 927 928 /// Regards both *this and RHS as signed quantities and compares them for 929 /// validity of the less-than relationship. 930 /// @returns true if *this < RHS when both are considered signed. 931 /// @brief Signed less than comparison 932 bool slt(const APInt& RHS) const; 933 934 /// Regards both *this as a signed quantity and compares it with RHS for 935 /// the validity of the less-than relationship. 936 /// @returns true if *this < RHS when considered signed. 937 /// @brief Signed less than comparison 938 bool slt(uint64_t RHS) const { 939 return slt(APInt(getBitWidth(), RHS)); 940 } 941 942 /// Regards both *this and RHS as unsigned quantities and compares them for 943 /// validity of the less-or-equal relationship. 944 /// @returns true if *this <= RHS when both are considered unsigned. 945 /// @brief Unsigned less or equal comparison 946 bool ule(const APInt& RHS) const { 947 return ult(RHS) || eq(RHS); 948 } 949 950 /// Regards both *this as an unsigned quantity and compares it with RHS for 951 /// the validity of the less-or-equal relationship. 952 /// @returns true if *this <= RHS when considered unsigned. 953 /// @brief Unsigned less or equal comparison 954 bool ule(uint64_t RHS) const { 955 return ule(APInt(getBitWidth(), RHS)); 956 } 957 958 /// Regards both *this and RHS as signed quantities and compares them for 959 /// validity of the less-or-equal relationship. 960 /// @returns true if *this <= RHS when both are considered signed. 961 /// @brief Signed less or equal comparison 962 bool sle(const APInt& RHS) const { 963 return slt(RHS) || eq(RHS); 964 } 965 966 /// Regards both *this as a signed quantity and compares it with RHS for 967 /// the validity of the less-or-equal relationship. 968 /// @returns true if *this <= RHS when considered signed. 969 /// @brief Signed less or equal comparison 970 bool sle(uint64_t RHS) const { 971 return sle(APInt(getBitWidth(), RHS)); 972 } 973 974 /// Regards both *this and RHS as unsigned quantities and compares them for 975 /// the validity of the greater-than relationship. 976 /// @returns true if *this > RHS when both are considered unsigned. 977 /// @brief Unsigned greather than comparison 978 bool ugt(const APInt& RHS) const { 979 return !ult(RHS) && !eq(RHS); 980 } 981 982 /// Regards both *this as an unsigned quantity and compares it with RHS for 983 /// the validity of the greater-than relationship. 984 /// @returns true if *this > RHS when considered unsigned. 985 /// @brief Unsigned greater than comparison 986 bool ugt(uint64_t RHS) const { 987 return ugt(APInt(getBitWidth(), RHS)); 988 } 989 990 /// Regards both *this and RHS as signed quantities and compares them for 991 /// the validity of the greater-than relationship. 992 /// @returns true if *this > RHS when both are considered signed. 993 /// @brief Signed greather than comparison 994 bool sgt(const APInt& RHS) const { 995 return !slt(RHS) && !eq(RHS); 996 } 997 998 /// Regards both *this as a signed quantity and compares it with RHS for 999 /// the validity of the greater-than relationship. 1000 /// @returns true if *this > RHS when considered signed. 1001 /// @brief Signed greater than comparison 1002 bool sgt(uint64_t RHS) const { 1003 return sgt(APInt(getBitWidth(), RHS)); 1004 } 1005 1006 /// Regards both *this and RHS as unsigned quantities and compares them for 1007 /// validity of the greater-or-equal relationship. 1008 /// @returns true if *this >= RHS when both are considered unsigned. 1009 /// @brief Unsigned greater or equal comparison 1010 bool uge(const APInt& RHS) const { 1011 return !ult(RHS); 1012 } 1013 1014 /// Regards both *this as an unsigned quantity and compares it with RHS for 1015 /// the validity of the greater-or-equal relationship. 1016 /// @returns true if *this >= RHS when considered unsigned. 1017 /// @brief Unsigned greater or equal comparison 1018 bool uge(uint64_t RHS) const { 1019 return uge(APInt(getBitWidth(), RHS)); 1020 } 1021 1022 /// Regards both *this and RHS as signed quantities and compares them for 1023 /// validity of the greater-or-equal relationship. 1024 /// @returns true if *this >= RHS when both are considered signed. 1025 /// @brief Signed greather or equal comparison 1026 bool sge(const APInt& RHS) const { 1027 return !slt(RHS); 1028 } 1029 1030 /// Regards both *this as a signed quantity and compares it with RHS for 1031 /// the validity of the greater-or-equal relationship. 1032 /// @returns true if *this >= RHS when considered signed. 1033 /// @brief Signed greater or equal comparison 1034 bool sge(uint64_t RHS) const { 1035 return sge(APInt(getBitWidth(), RHS)); 1036 } 1037 1038 1039 1040 1041 /// This operation tests if there are any pairs of corresponding bits 1042 /// between this APInt and RHS that are both set. 1043 bool intersects(const APInt &RHS) const { 1044 return (*this & RHS) != 0; 1045 } 1046 1047 /// @} 1048 /// @name Resizing Operators 1049 /// @{ 1050 /// Truncate the APInt to a specified width. It is an error to specify a width 1051 /// that is greater than or equal to the current width. 1052 /// @brief Truncate to new width. 1053 APInt trunc(unsigned width) const; 1054 1055 /// This operation sign extends the APInt to a new width. If the high order 1056 /// bit is set, the fill on the left will be done with 1 bits, otherwise zero. 1057 /// It is an error to specify a width that is less than or equal to the 1058 /// current width. 1059 /// @brief Sign extend to a new width. 1060 APInt sext(unsigned width) const; 1061 1062 /// This operation zero extends the APInt to a new width. The high order bits 1063 /// are filled with 0 bits. It is an error to specify a width that is less 1064 /// than or equal to the current width. 1065 /// @brief Zero extend to a new width. 1066 APInt zext(unsigned width) const; 1067 1068 /// Make this APInt have the bit width given by \p width. The value is sign 1069 /// extended, truncated, or left alone to make it that width. 1070 /// @brief Sign extend or truncate to width 1071 APInt sextOrTrunc(unsigned width) const; 1072 1073 /// Make this APInt have the bit width given by \p width. The value is zero 1074 /// extended, truncated, or left alone to make it that width. 1075 /// @brief Zero extend or truncate to width 1076 APInt zextOrTrunc(unsigned width) const; 1077 1078 /// Make this APInt have the bit width given by \p width. The value is sign 1079 /// extended, or left alone to make it that width. 1080 /// @brief Sign extend or truncate to width 1081 APInt sextOrSelf(unsigned width) const; 1082 1083 /// Make this APInt have the bit width given by \p width. The value is zero 1084 /// extended, or left alone to make it that width. 1085 /// @brief Zero extend or truncate to width 1086 APInt zextOrSelf(unsigned width) const; 1087 1088 /// @} 1089 /// @name Bit Manipulation Operators 1090 /// @{ 1091 /// @brief Set every bit to 1. 1092 void setAllBits() { 1093 if (isSingleWord()) 1094 VAL = UINT64_MAX; 1095 else { 1096 // Set all the bits in all the words. 1097 for (unsigned i = 0; i < getNumWords(); ++i) 1098 pVal[i] = UINT64_MAX; 1099 } 1100 // Clear the unused ones 1101 clearUnusedBits(); 1102 } 1103 1104 /// Set the given bit to 1 whose position is given as "bitPosition". 1105 /// @brief Set a given bit to 1. 1106 void setBit(unsigned bitPosition); 1107 1108 /// @brief Set every bit to 0. 1109 void clearAllBits() { 1110 if (isSingleWord()) 1111 VAL = 0; 1112 else 1113 memset(pVal, 0, getNumWords() * APINT_WORD_SIZE); 1114 } 1115 1116 /// Set the given bit to 0 whose position is given as "bitPosition". 1117 /// @brief Set a given bit to 0. 1118 void clearBit(unsigned bitPosition); 1119 1120 /// @brief Toggle every bit to its opposite value. 1121 void flipAllBits() { 1122 if (isSingleWord()) 1123 VAL ^= UINT64_MAX; 1124 else { 1125 for (unsigned i = 0; i < getNumWords(); ++i) 1126 pVal[i] ^= UINT64_MAX; 1127 } 1128 clearUnusedBits(); 1129 } 1130 1131 /// Toggle a given bit to its opposite value whose position is given 1132 /// as "bitPosition". 1133 /// @brief Toggles a given bit to its opposite value. 1134 void flipBit(unsigned bitPosition); 1135 1136 /// @} 1137 /// @name Value Characterization Functions 1138 /// @{ 1139 1140 /// @returns the total number of bits. 1141 unsigned getBitWidth() const { 1142 return BitWidth; 1143 } 1144 1145 /// Here one word's bitwidth equals to that of uint64_t. 1146 /// @returns the number of words to hold the integer value of this APInt. 1147 /// @brief Get the number of words. 1148 unsigned getNumWords() const { 1149 return getNumWords(BitWidth); 1150 } 1151 1152 /// Here one word's bitwidth equals to that of uint64_t. 1153 /// @returns the number of words to hold the integer value with a 1154 /// given bit width. 1155 /// @brief Get the number of words. 1156 static unsigned getNumWords(unsigned BitWidth) { 1157 return (BitWidth + APINT_BITS_PER_WORD - 1) / APINT_BITS_PER_WORD; 1158 } 1159 1160 /// This function returns the number of active bits which is defined as the 1161 /// bit width minus the number of leading zeros. This is used in several 1162 /// computations to see how "wide" the value is. 1163 /// @brief Compute the number of active bits in the value 1164 unsigned getActiveBits() const { 1165 return BitWidth - countLeadingZeros(); 1166 } 1167 1168 /// This function returns the number of active words in the value of this 1169 /// APInt. This is used in conjunction with getActiveData to extract the raw 1170 /// value of the APInt. 1171 unsigned getActiveWords() const { 1172 unsigned numActiveBits = getActiveBits(); 1173 return numActiveBits ? whichWord(numActiveBits - 1) + 1 : 1; 1174 } 1175 1176 /// Computes the minimum bit width for this APInt while considering it to be 1177 /// a signed (and probably negative) value. If the value is not negative, 1178 /// this function returns the same value as getActiveBits()+1. Otherwise, it 1179 /// returns the smallest bit width that will retain the negative value. For 1180 /// example, -1 can be written as 0b1 or 0xFFFFFFFFFF. 0b1 is shorter and so 1181 /// for -1, this function will always return 1. 1182 /// @brief Get the minimum bit size for this signed APInt 1183 unsigned getMinSignedBits() const { 1184 if (isNegative()) 1185 return BitWidth - countLeadingOnes() + 1; 1186 return getActiveBits()+1; 1187 } 1188 1189 /// This method attempts to return the value of this APInt as a zero extended 1190 /// uint64_t. The bitwidth must be <= 64 or the value must fit within a 1191 /// uint64_t. Otherwise an assertion will result. 1192 /// @brief Get zero extended value 1193 uint64_t getZExtValue() const { 1194 if (isSingleWord()) 1195 return VAL; 1196 assert(getActiveBits() <= 64 && "Too many bits for uint64_t"); 1197 return pVal[0]; 1198 } 1199 1200 /// This method attempts to return the value of this APInt as a sign extended 1201 /// int64_t. The bit width must be <= 64 or the value must fit within an 1202 /// int64_t. Otherwise an assertion will result. 1203 /// @brief Get sign extended value 1204 int64_t getSExtValue() const { 1205 if (isSingleWord()) 1206 return int64_t(VAL << (APINT_BITS_PER_WORD - BitWidth)) >> 1207 (APINT_BITS_PER_WORD - BitWidth); 1208 assert(getMinSignedBits() <= 64 && "Too many bits for int64_t"); 1209 return int64_t(pVal[0]); 1210 } 1211 1212 /// This method determines how many bits are required to hold the APInt 1213 /// equivalent of the string given by \p str. 1214 /// @brief Get bits required for string value. 1215 static unsigned getBitsNeeded(StringRef str, uint8_t radix); 1216 1217 /// countLeadingZeros - This function is an APInt version of the 1218 /// countLeadingZeros_{32,64} functions in MathExtras.h. It counts the number 1219 /// of zeros from the most significant bit to the first one bit. 1220 /// @returns BitWidth if the value is zero, otherwise 1221 /// returns the number of zeros from the most significant bit to the first 1222 /// one bits. 1223 unsigned countLeadingZeros() const { 1224 if (isSingleWord()) { 1225 unsigned unusedBits = APINT_BITS_PER_WORD - BitWidth; 1226 return CountLeadingZeros_64(VAL) - unusedBits; 1227 } 1228 return countLeadingZerosSlowCase(); 1229 } 1230 1231 /// countLeadingOnes - This function is an APInt version of the 1232 /// countLeadingOnes_{32,64} functions in MathExtras.h. It counts the number 1233 /// of ones from the most significant bit to the first zero bit. 1234 /// @returns 0 if the high order bit is not set, otherwise 1235 /// returns the number of 1 bits from the most significant to the least 1236 /// @brief Count the number of leading one bits. 1237 unsigned countLeadingOnes() const; 1238 1239 /// Computes the number of leading bits of this APInt that are equal to its 1240 /// sign bit. 1241 unsigned getNumSignBits() const { 1242 return isNegative() ? countLeadingOnes() : countLeadingZeros(); 1243 } 1244 1245 /// countTrailingZeros - This function is an APInt version of the 1246 /// countTrailingZeros_{32,64} functions in MathExtras.h. It counts 1247 /// the number of zeros from the least significant bit to the first set bit. 1248 /// @returns BitWidth if the value is zero, otherwise 1249 /// returns the number of zeros from the least significant bit to the first 1250 /// one bit. 1251 /// @brief Count the number of trailing zero bits. 1252 unsigned countTrailingZeros() const; 1253 1254 /// countTrailingOnes - This function is an APInt version of the 1255 /// countTrailingOnes_{32,64} functions in MathExtras.h. It counts 1256 /// the number of ones from the least significant bit to the first zero bit. 1257 /// @returns BitWidth if the value is all ones, otherwise 1258 /// returns the number of ones from the least significant bit to the first 1259 /// zero bit. 1260 /// @brief Count the number of trailing one bits. 1261 unsigned countTrailingOnes() const { 1262 if (isSingleWord()) 1263 return CountTrailingOnes_64(VAL); 1264 return countTrailingOnesSlowCase(); 1265 } 1266 1267 /// countPopulation - This function is an APInt version of the 1268 /// countPopulation_{32,64} functions in MathExtras.h. It counts the number 1269 /// of 1 bits in the APInt value. 1270 /// @returns 0 if the value is zero, otherwise returns the number of set 1271 /// bits. 1272 /// @brief Count the number of bits set. 1273 unsigned countPopulation() const { 1274 if (isSingleWord()) 1275 return CountPopulation_64(VAL); 1276 return countPopulationSlowCase(); 1277 } 1278 1279 /// @} 1280 /// @name Conversion Functions 1281 /// @{ 1282 void print(raw_ostream &OS, bool isSigned) const; 1283 1284 /// toString - Converts an APInt to a string and append it to Str. Str is 1285 /// commonly a SmallString. 1286 void toString(SmallVectorImpl<char> &Str, unsigned Radix, bool Signed, 1287 bool formatAsCLiteral = false) const; 1288 1289 /// Considers the APInt to be unsigned and converts it into a string in the 1290 /// radix given. The radix can be 2, 8, 10 16, or 36. 1291 void toStringUnsigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const { 1292 toString(Str, Radix, false, false); 1293 } 1294 1295 /// Considers the APInt to be signed and converts it into a string in the 1296 /// radix given. The radix can be 2, 8, 10, 16, or 36. 1297 void toStringSigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const { 1298 toString(Str, Radix, true, false); 1299 } 1300 1301 /// toString - This returns the APInt as a std::string. Note that this is an 1302 /// inefficient method. It is better to pass in a SmallVector/SmallString 1303 /// to the methods above to avoid thrashing the heap for the string. 1304 std::string toString(unsigned Radix, bool Signed) const; 1305 1306 1307 /// @returns a byte-swapped representation of this APInt Value. 1308 APInt byteSwap() const; 1309 1310 /// @brief Converts this APInt to a double value. 1311 double roundToDouble(bool isSigned) const; 1312 1313 /// @brief Converts this unsigned APInt to a double value. 1314 double roundToDouble() const { 1315 return roundToDouble(false); 1316 } 1317 1318 /// @brief Converts this signed APInt to a double value. 1319 double signedRoundToDouble() const { 1320 return roundToDouble(true); 1321 } 1322 1323 /// The conversion does not do a translation from integer to double, it just 1324 /// re-interprets the bits as a double. Note that it is valid to do this on 1325 /// any bit width. Exactly 64 bits will be translated. 1326 /// @brief Converts APInt bits to a double 1327 double bitsToDouble() const { 1328 union { 1329 uint64_t I; 1330 double D; 1331 } T; 1332 T.I = (isSingleWord() ? VAL : pVal[0]); 1333 return T.D; 1334 } 1335 1336 /// The conversion does not do a translation from integer to float, it just 1337 /// re-interprets the bits as a float. Note that it is valid to do this on 1338 /// any bit width. Exactly 32 bits will be translated. 1339 /// @brief Converts APInt bits to a double 1340 float bitsToFloat() const { 1341 union { 1342 unsigned I; 1343 float F; 1344 } T; 1345 T.I = unsigned((isSingleWord() ? VAL : pVal[0])); 1346 return T.F; 1347 } 1348 1349 /// The conversion does not do a translation from double to integer, it just 1350 /// re-interprets the bits of the double. 1351 /// @brief Converts a double to APInt bits. 1352 static APInt doubleToBits(double V) { 1353 union { 1354 uint64_t I; 1355 double D; 1356 } T; 1357 T.D = V; 1358 return APInt(sizeof T * CHAR_BIT, T.I); 1359 } 1360 1361 /// The conversion does not do a translation from float to integer, it just 1362 /// re-interprets the bits of the float. 1363 /// @brief Converts a float to APInt bits. 1364 static APInt floatToBits(float V) { 1365 union { 1366 unsigned I; 1367 float F; 1368 } T; 1369 T.F = V; 1370 return APInt(sizeof T * CHAR_BIT, T.I); 1371 } 1372 1373 /// @} 1374 /// @name Mathematics Operations 1375 /// @{ 1376 1377 /// @returns the floor log base 2 of this APInt. 1378 unsigned logBase2() const { 1379 return BitWidth - 1 - countLeadingZeros(); 1380 } 1381 1382 /// @returns the ceil log base 2 of this APInt. 1383 unsigned ceilLogBase2() const { 1384 return BitWidth - (*this - 1).countLeadingZeros(); 1385 } 1386 1387 /// @returns the log base 2 of this APInt if its an exact power of two, -1 1388 /// otherwise 1389 int32_t exactLogBase2() const { 1390 if (!isPowerOf2()) 1391 return -1; 1392 return logBase2(); 1393 } 1394 1395 /// @brief Compute the square root 1396 APInt sqrt() const; 1397 1398 /// If *this is < 0 then return -(*this), otherwise *this; 1399 /// @brief Get the absolute value; 1400 APInt abs() const { 1401 if (isNegative()) 1402 return -(*this); 1403 return *this; 1404 } 1405 1406 /// @returns the multiplicative inverse for a given modulo. 1407 APInt multiplicativeInverse(const APInt& modulo) const; 1408 1409 /// @} 1410 /// @name Support for division by constant 1411 /// @{ 1412 1413 /// Calculate the magic number for signed division by a constant. 1414 struct ms; 1415 ms magic() const; 1416 1417 /// Calculate the magic number for unsigned division by a constant. 1418 struct mu; 1419 mu magicu(unsigned LeadingZeros = 0) const; 1420 1421 /// @} 1422 /// @name Building-block Operations for APInt and APFloat 1423 /// @{ 1424 1425 // These building block operations operate on a representation of 1426 // arbitrary precision, two's-complement, bignum integer values. 1427 // They should be sufficient to implement APInt and APFloat bignum 1428 // requirements. Inputs are generally a pointer to the base of an 1429 // array of integer parts, representing an unsigned bignum, and a 1430 // count of how many parts there are. 1431 1432 /// Sets the least significant part of a bignum to the input value, 1433 /// and zeroes out higher parts. */ 1434 static void tcSet(integerPart *, integerPart, unsigned int); 1435 1436 /// Assign one bignum to another. 1437 static void tcAssign(integerPart *, const integerPart *, unsigned int); 1438 1439 /// Returns true if a bignum is zero, false otherwise. 1440 static bool tcIsZero(const integerPart *, unsigned int); 1441 1442 /// Extract the given bit of a bignum; returns 0 or 1. Zero-based. 1443 static int tcExtractBit(const integerPart *, unsigned int bit); 1444 1445 /// Copy the bit vector of width srcBITS from SRC, starting at bit 1446 /// srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB 1447 /// becomes the least significant bit of DST. All high bits above 1448 /// srcBITS in DST are zero-filled. 1449 static void tcExtract(integerPart *, unsigned int dstCount, 1450 const integerPart *, 1451 unsigned int srcBits, unsigned int srcLSB); 1452 1453 /// Set the given bit of a bignum. Zero-based. 1454 static void tcSetBit(integerPart *, unsigned int bit); 1455 1456 /// Clear the given bit of a bignum. Zero-based. 1457 static void tcClearBit(integerPart *, unsigned int bit); 1458 1459 /// Returns the bit number of the least or most significant set bit 1460 /// of a number. If the input number has no bits set -1U is 1461 /// returned. 1462 static unsigned int tcLSB(const integerPart *, unsigned int); 1463 static unsigned int tcMSB(const integerPart *parts, unsigned int n); 1464 1465 /// Negate a bignum in-place. 1466 static void tcNegate(integerPart *, unsigned int); 1467 1468 /// DST += RHS + CARRY where CARRY is zero or one. Returns the 1469 /// carry flag. 1470 static integerPart tcAdd(integerPart *, const integerPart *, 1471 integerPart carry, unsigned); 1472 1473 /// DST -= RHS + CARRY where CARRY is zero or one. Returns the 1474 /// carry flag. 1475 static integerPart tcSubtract(integerPart *, const integerPart *, 1476 integerPart carry, unsigned); 1477 1478 /// DST += SRC * MULTIPLIER + PART if add is true 1479 /// DST = SRC * MULTIPLIER + PART if add is false 1480 /// 1481 /// Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC 1482 /// they must start at the same point, i.e. DST == SRC. 1483 /// 1484 /// If DSTPARTS == SRC_PARTS + 1 no overflow occurs and zero is 1485 /// returned. Otherwise DST is filled with the least significant 1486 /// DSTPARTS parts of the result, and if all of the omitted higher 1487 /// parts were zero return zero, otherwise overflow occurred and 1488 /// return one. 1489 static int tcMultiplyPart(integerPart *dst, const integerPart *src, 1490 integerPart multiplier, integerPart carry, 1491 unsigned int srcParts, unsigned int dstParts, 1492 bool add); 1493 1494 /// DST = LHS * RHS, where DST has the same width as the operands 1495 /// and is filled with the least significant parts of the result. 1496 /// Returns one if overflow occurred, otherwise zero. DST must be 1497 /// disjoint from both operands. 1498 static int tcMultiply(integerPart *, const integerPart *, 1499 const integerPart *, unsigned); 1500 1501 /// DST = LHS * RHS, where DST has width the sum of the widths of 1502 /// the operands. No overflow occurs. DST must be disjoint from 1503 /// both operands. Returns the number of parts required to hold the 1504 /// result. 1505 static unsigned int tcFullMultiply(integerPart *, const integerPart *, 1506 const integerPart *, unsigned, unsigned); 1507 1508 /// If RHS is zero LHS and REMAINDER are left unchanged, return one. 1509 /// Otherwise set LHS to LHS / RHS with the fractional part 1510 /// discarded, set REMAINDER to the remainder, return zero. i.e. 1511 /// 1512 /// OLD_LHS = RHS * LHS + REMAINDER 1513 /// 1514 /// SCRATCH is a bignum of the same size as the operands and result 1515 /// for use by the routine; its contents need not be initialized 1516 /// and are destroyed. LHS, REMAINDER and SCRATCH must be 1517 /// distinct. 1518 static int tcDivide(integerPart *lhs, const integerPart *rhs, 1519 integerPart *remainder, integerPart *scratch, 1520 unsigned int parts); 1521 1522 /// Shift a bignum left COUNT bits. Shifted in bits are zero. 1523 /// There are no restrictions on COUNT. 1524 static void tcShiftLeft(integerPart *, unsigned int parts, 1525 unsigned int count); 1526 1527 /// Shift a bignum right COUNT bits. Shifted in bits are zero. 1528 /// There are no restrictions on COUNT. 1529 static void tcShiftRight(integerPart *, unsigned int parts, 1530 unsigned int count); 1531 1532 /// The obvious AND, OR and XOR and complement operations. 1533 static void tcAnd(integerPart *, const integerPart *, unsigned int); 1534 static void tcOr(integerPart *, const integerPart *, unsigned int); 1535 static void tcXor(integerPart *, const integerPart *, unsigned int); 1536 static void tcComplement(integerPart *, unsigned int); 1537 1538 /// Comparison (unsigned) of two bignums. 1539 static int tcCompare(const integerPart *, const integerPart *, 1540 unsigned int); 1541 1542 /// Increment a bignum in-place. Return the carry flag. 1543 static integerPart tcIncrement(integerPart *, unsigned int); 1544 1545 /// Set the least significant BITS and clear the rest. 1546 static void tcSetLeastSignificantBits(integerPart *, unsigned int, 1547 unsigned int bits); 1548 1549 /// @brief debug method 1550 void dump() const; 1551 1552 /// @} 1553 }; 1554 1555 /// Magic data for optimising signed division by a constant. 1556 struct APInt::ms { 1557 APInt m; ///< magic number 1558 unsigned s; ///< shift amount 1559 }; 1560 1561 /// Magic data for optimising unsigned division by a constant. 1562 struct APInt::mu { 1563 APInt m; ///< magic number 1564 bool a; ///< add indicator 1565 unsigned s; ///< shift amount 1566 }; 1567 1568 inline bool operator==(uint64_t V1, const APInt& V2) { 1569 return V2 == V1; 1570 } 1571 1572 inline bool operator!=(uint64_t V1, const APInt& V2) { 1573 return V2 != V1; 1574 } 1575 1576 inline raw_ostream &operator<<(raw_ostream &OS, const APInt &I) { 1577 I.print(OS, true); 1578 return OS; 1579 } 1580 1581 namespace APIntOps { 1582 1583 /// @brief Determine the smaller of two APInts considered to be signed. 1584 inline APInt smin(const APInt &A, const APInt &B) { 1585 return A.slt(B) ? A : B; 1586 } 1587 1588 /// @brief Determine the larger of two APInts considered to be signed. 1589 inline APInt smax(const APInt &A, const APInt &B) { 1590 return A.sgt(B) ? A : B; 1591 } 1592 1593 /// @brief Determine the smaller of two APInts considered to be signed. 1594 inline APInt umin(const APInt &A, const APInt &B) { 1595 return A.ult(B) ? A : B; 1596 } 1597 1598 /// @brief Determine the larger of two APInts considered to be unsigned. 1599 inline APInt umax(const APInt &A, const APInt &B) { 1600 return A.ugt(B) ? A : B; 1601 } 1602 1603 /// @brief Check if the specified APInt has a N-bits unsigned integer value. 1604 inline bool isIntN(unsigned N, const APInt& APIVal) { 1605 return APIVal.isIntN(N); 1606 } 1607 1608 /// @brief Check if the specified APInt has a N-bits signed integer value. 1609 inline bool isSignedIntN(unsigned N, const APInt& APIVal) { 1610 return APIVal.isSignedIntN(N); 1611 } 1612 1613 /// @returns true if the argument APInt value is a sequence of ones 1614 /// starting at the least significant bit with the remainder zero. 1615 inline bool isMask(unsigned numBits, const APInt& APIVal) { 1616 return numBits <= APIVal.getBitWidth() && 1617 APIVal == APInt::getLowBitsSet(APIVal.getBitWidth(), numBits); 1618 } 1619 1620 /// @returns true if the argument APInt value contains a sequence of ones 1621 /// with the remainder zero. 1622 inline bool isShiftedMask(unsigned numBits, const APInt& APIVal) { 1623 return isMask(numBits, (APIVal - APInt(numBits,1)) | APIVal); 1624 } 1625 1626 /// @returns a byte-swapped representation of the specified APInt Value. 1627 inline APInt byteSwap(const APInt& APIVal) { 1628 return APIVal.byteSwap(); 1629 } 1630 1631 /// @returns the floor log base 2 of the specified APInt value. 1632 inline unsigned logBase2(const APInt& APIVal) { 1633 return APIVal.logBase2(); 1634 } 1635 1636 /// GreatestCommonDivisor - This function returns the greatest common 1637 /// divisor of the two APInt values using Euclid's algorithm. 1638 /// @returns the greatest common divisor of Val1 and Val2 1639 /// @brief Compute GCD of two APInt values. 1640 APInt GreatestCommonDivisor(const APInt& Val1, const APInt& Val2); 1641 1642 /// Treats the APInt as an unsigned value for conversion purposes. 1643 /// @brief Converts the given APInt to a double value. 1644 inline double RoundAPIntToDouble(const APInt& APIVal) { 1645 return APIVal.roundToDouble(); 1646 } 1647 1648 /// Treats the APInt as a signed value for conversion purposes. 1649 /// @brief Converts the given APInt to a double value. 1650 inline double RoundSignedAPIntToDouble(const APInt& APIVal) { 1651 return APIVal.signedRoundToDouble(); 1652 } 1653 1654 /// @brief Converts the given APInt to a float vlalue. 1655 inline float RoundAPIntToFloat(const APInt& APIVal) { 1656 return float(RoundAPIntToDouble(APIVal)); 1657 } 1658 1659 /// Treast the APInt as a signed value for conversion purposes. 1660 /// @brief Converts the given APInt to a float value. 1661 inline float RoundSignedAPIntToFloat(const APInt& APIVal) { 1662 return float(APIVal.signedRoundToDouble()); 1663 } 1664 1665 /// RoundDoubleToAPInt - This function convert a double value to an APInt value. 1666 /// @brief Converts the given double value into a APInt. 1667 APInt RoundDoubleToAPInt(double Double, unsigned width); 1668 1669 /// RoundFloatToAPInt - Converts a float value into an APInt value. 1670 /// @brief Converts a float value into a APInt. 1671 inline APInt RoundFloatToAPInt(float Float, unsigned width) { 1672 return RoundDoubleToAPInt(double(Float), width); 1673 } 1674 1675 /// Arithmetic right-shift the APInt by shiftAmt. 1676 /// @brief Arithmetic right-shift function. 1677 inline APInt ashr(const APInt& LHS, unsigned shiftAmt) { 1678 return LHS.ashr(shiftAmt); 1679 } 1680 1681 /// Logical right-shift the APInt by shiftAmt. 1682 /// @brief Logical right-shift function. 1683 inline APInt lshr(const APInt& LHS, unsigned shiftAmt) { 1684 return LHS.lshr(shiftAmt); 1685 } 1686 1687 /// Left-shift the APInt by shiftAmt. 1688 /// @brief Left-shift function. 1689 inline APInt shl(const APInt& LHS, unsigned shiftAmt) { 1690 return LHS.shl(shiftAmt); 1691 } 1692 1693 /// Signed divide APInt LHS by APInt RHS. 1694 /// @brief Signed division function for APInt. 1695 inline APInt sdiv(const APInt& LHS, const APInt& RHS) { 1696 return LHS.sdiv(RHS); 1697 } 1698 1699 /// Unsigned divide APInt LHS by APInt RHS. 1700 /// @brief Unsigned division function for APInt. 1701 inline APInt udiv(const APInt& LHS, const APInt& RHS) { 1702 return LHS.udiv(RHS); 1703 } 1704 1705 /// Signed remainder operation on APInt. 1706 /// @brief Function for signed remainder operation. 1707 inline APInt srem(const APInt& LHS, const APInt& RHS) { 1708 return LHS.srem(RHS); 1709 } 1710 1711 /// Unsigned remainder operation on APInt. 1712 /// @brief Function for unsigned remainder operation. 1713 inline APInt urem(const APInt& LHS, const APInt& RHS) { 1714 return LHS.urem(RHS); 1715 } 1716 1717 /// Performs multiplication on APInt values. 1718 /// @brief Function for multiplication operation. 1719 inline APInt mul(const APInt& LHS, const APInt& RHS) { 1720 return LHS * RHS; 1721 } 1722 1723 /// Performs addition on APInt values. 1724 /// @brief Function for addition operation. 1725 inline APInt add(const APInt& LHS, const APInt& RHS) { 1726 return LHS + RHS; 1727 } 1728 1729 /// Performs subtraction on APInt values. 1730 /// @brief Function for subtraction operation. 1731 inline APInt sub(const APInt& LHS, const APInt& RHS) { 1732 return LHS - RHS; 1733 } 1734 1735 /// Performs bitwise AND operation on APInt LHS and 1736 /// APInt RHS. 1737 /// @brief Bitwise AND function for APInt. 1738 inline APInt And(const APInt& LHS, const APInt& RHS) { 1739 return LHS & RHS; 1740 } 1741 1742 /// Performs bitwise OR operation on APInt LHS and APInt RHS. 1743 /// @brief Bitwise OR function for APInt. 1744 inline APInt Or(const APInt& LHS, const APInt& RHS) { 1745 return LHS | RHS; 1746 } 1747 1748 /// Performs bitwise XOR operation on APInt. 1749 /// @brief Bitwise XOR function for APInt. 1750 inline APInt Xor(const APInt& LHS, const APInt& RHS) { 1751 return LHS ^ RHS; 1752 } 1753 1754 /// Performs a bitwise complement operation on APInt. 1755 /// @brief Bitwise complement function. 1756 inline APInt Not(const APInt& APIVal) { 1757 return ~APIVal; 1758 } 1759 1760 } // End of APIntOps namespace 1761 1762 // See friend declaration above. This additional declaration is required in 1763 // order to compile LLVM with IBM xlC compiler. 1764 hash_code hash_value(const APInt &Arg); 1765 } // End of llvm namespace 1766 1767 #endif 1768