include/llvm/ADT/APInt.h

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