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