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