[ADT] Allocate memory less often by increase inline storage

[majnemer]

Summary

Previously, APInt was a tagged union between a single 64-bit value and a
pointer.

Extensive profiling revealed that an application of LLVM was spending
35% of its time allocating and freeing memory for 65-bit APInts.

This patch proposes to change our representation for APInts by adding an
additional 64-bit value.

On platforms which support 128-bit arithmetic, __u?int128_t is used to
speed up APInt computations for bitwidths between 65 and 128.

I would appreciate help benchmarking this change. It dramatically
speeds up my application of LLVM but more data would be gratefully
appreciated.

[mehdi_amini]

A few quick comments.

include/llvm/ADT/APInt.h

83

If VAL was a pair, or a struct { uint64_t Low, High; }, it'd be copyable directly. Also I'd rather read Val.Low instead of Val[0].

271

Spurious braces for the if?

273

I'd have missed this one :)

276

Remove braces?

322

Same braces as above.

329

Couldn't you just copy VAL as whole all the time?

344

I guess the fact that VAL[1] can be initialized makes explains why you're copying only part of it. Do you expect better code with this? I feel it is easier to think about VAL as a single unit as much as possible.

436

VAL[0] == 0 && isPowerOf2_64(VAL[1]) ?

720

Any risk that you're reading uninitialized memory here? (in line with comment in the default ctor above)

[majnemer]

include/llvm/ADT/APInt.h

83

It might be a little misleading given that High would be uninitialized under certain circumstances.

271

I think its most common to brace all the if/else if if any of them are braced.

329

It might be uninitialized.

344

I prefer not initializing it if it will never be used. This allows tools like valgrind and ubsan find bugs.

436

I think your formulation is wrong if VAL[0] is 1 and VAL[1] is 0.

720

Good point, I'll amend this.

[sanjoy]

I'm not sure if this is the right approach -- I think it is better to avoid a change of this scale if possible.

Have you considered changing the access to pVal in APInt.cpp to go through an accessor that returns &VAL[0] if the bitwidth is <= 128? The union could be changed to:

union {
  uint64_t LocalArray[2];
  uint64_t VAL;
  uint64_t *pVal;
};

to avoid breaking existing uses of VAL, and most of the existing code (except perhaps things like AssignSlowCase) should work as they do now. This approach will also easily generalize to a LocalArray[N].

The downside of what I've suggested above is that the "fast path" for some of the two-word operations will not be visible but a) they may not actually matter, and b) we can change them one by one as needed.

[sanjoy]

"Marking as read".

include/llvm/ADT/APInt.h

 /// \brief This file implements a class to represent arbitrary precision
 /// integral constant values and operations on them.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_APINT_H
 #define LLVM_ADT_APINT_H
 
+#include "llvm/ADT/ArrayRef.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/MathExtras.h"
 #include <cassert>
 #include <climits>
 #include <cstring>
 #include <string>
 
 namespace llvm {
 class FoldingSetNodeID;
 class StringRef;
 class hash_code;
 class raw_ostream;
 
 template <typename T> class SmallVectorImpl;
-template <typename T> class ArrayRef;
 
 // An unsigned host type used as a single part of a multi-part
 // bignum.
 typedef uint64_t integerPart;
 
 const unsigned int host_char_bit = 8;
 const unsigned int integerPartWidth =
     host_char_bit * static_cast<unsigned int>(sizeof(integerPart));

 ///     not.
 ///   * In general, the class tries to follow the style of computation that LLVM
 ///     uses in its IR. This simplifies its use for LLVM.
 ///
 class APInt {
   unsigned BitWidth; ///< The number of bits in this APInt.
 
   /// This union is used to store the integer value. When the
-  /// integer bit-width <= 64, it uses VAL, otherwise it uses pVal.
+  /// integer bit-width <= 128, it uses VAL, otherwise it uses pVal.
   union {
-    uint64_t VAL;   ///< Used to store the <= 64 bits integer value.
-    uint64_t *pVal; ///< Used to store the >64 bits integer value.
+    uint64_t VAL[2]; ///< Used to store the <= 128 bits integer value.
+    uint64_t *pVal;  ///< Used to store the >128 bits integer value.
   };
 
   /// This enum is used to hold the constants we needed for APInt.
   enum {
     /// Bits in a word
     APINT_BITS_PER_WORD =
         static_cast<unsigned int>(sizeof(uint64_t)) * CHAR_BIT,
     /// Byte size of a word
     APINT_WORD_SIZE = static_cast<unsigned int>(sizeof(uint64_t))
   };
 
   friend struct DenseMapAPIntKeyInfo;
 
   /// \brief Fast internal constructor
   ///
   /// This constructor is used only internally for speed of construction of
   /// temporaries. It is unsafe for general use so it is not public.
   APInt(uint64_t *val, unsigned bits) : BitWidth(bits), pVal(val) {}
 
   /// \brief Determine if this APInt just has one word to store value.
   ///
   /// \returns true if the number of bits <= 64, false otherwise.
   bool isSingleWord() const { return BitWidth <= APINT_BITS_PER_WORD; }
 
+  /// \brief Determine if this APInt just has two words to store value.
+  ///
+  /// \returns true if the number of bits > 64 && <= 128, false otherwise.
+  bool isTwoWords() const {
+    return BitWidth > APINT_BITS_PER_WORD &&
+           BitWidth <= APINT_BITS_PER_WORD * 2;
+  }
+
+  /// \brief Determine if this APInt uses storage allocated in-line.
+  ///
+  /// \returns true if the number of bits <= 128, false otherwise.
+  bool isInline() const { return BitWidth <= APINT_BITS_PER_WORD * 2; }
+
   /// \brief Determine which word a bit is in.
   ///
   /// \returns the word position for the specified bit position.
   static unsigned whichWord(unsigned bitPosition) {
     return bitPosition / APINT_BITS_PER_WORD;
   }
 
   /// \brief Determine which bit in a word a bit is in.
if (wordBits == 0)
       // If all bits are used, we want to leave the value alone. This also
       // avoids the undefined behavior of >> when the shift is the same size as
       // the word size (64).
       return *this;
 
     // Mask out the high bits.
     uint64_t mask = ~uint64_t(0ULL) >> (APINT_BITS_PER_WORD - wordBits);
     if (isSingleWord())
-      VAL &= mask;
+      VAL[0] &= mask;
+    else if (isTwoWords())
+      VAL[1] &= mask;
     else
       pVal[getNumWords() - 1] &= mask;
     return *this;
   }
 
   /// \brief Get the word corresponding to a bit position
   /// \returns the corresponding word for the specified bit position.
   uint64_t getWord(unsigned bitPosition) const {
-    return isSingleWord() ? VAL : pVal[whichWord(bitPosition)];
+    if (isSingleWord())
+      return VAL[0];
+    if (isTwoWords())
+      return VAL[bitPosition >= APINT_BITS_PER_WORD ? 1 : 0];
+    return pVal[whichWord(bitPosition)];
   }
 
   /// \brief Convert a char array into an APInt
   ///
   /// \param radix 2, 8, 10, 16, or 36
   /// Converts a string into a number.  The string must be non-empty
   /// and well-formed as a number of the given base. The bit-width
   /// must be sufficient to hold the result.
class APInt {
   unsigned countLeadingZerosSlowCase() const;
 
   /// out-of-line slow case for countTrailingOnes
   unsigned countTrailingOnesSlowCase() const;
 
   /// out-of-line slow case for countPopulation
   unsigned countPopulationSlowCase() const;
 
+  uint64_t *getMutableRawData() {
+    if (isInline())
+      return &VAL[0];
+    return &pVal[0];
+  }
+
 public:
   /// \name Constructors
   /// @{
 
   /// \brief Create a new APInt of numBits width, initialized as val.
   ///
   /// If isSigned is true then val is treated as if it were a signed value
   /// (i.e. as an int64_t) and the appropriate sign extension to the bit width
   /// will be done. Otherwise, no sign extension occurs (high order bits beyond
   /// the range of val are zero filled).
   ///
   /// \param numBits the bit width of the constructed APInt
   /// \param val the initial value of the APInt
   /// \param isSigned how to treat signedness of val
   APInt(unsigned numBits, uint64_t val, bool isSigned = false)
-      : BitWidth(numBits), VAL(0) {
+      : BitWidth(numBits) {
     assert(BitWidth && "bitwidth too small");
-    if (isSingleWord())
-      VAL = val;
-    else
+    VAL[0] = 0;
+    if (isSingleWord()) {
+      VAL[0] = val;
+    } else if (isTwoWords()) {
+      VAL[0] = val;
+      VAL[1] = isSigned && int64_t(val) < 0 ? -1ULL : 0;
+    } else {
       initSlowCase(val, isSigned);
+    }
     clearUnusedBits();
   }
 
   /// \brief Construct an APInt of numBits width, initialized as bigVal[].
   ///
   /// Note that bigVal.size() can be smaller or larger than the corresponding
   /// bit width but any extraneous bits will be dropped.
   ///
public:
   ///
   /// \param numBits the bit width of the constructed APInt
   /// \param str the string to be interpreted
   /// \param radix the radix to use for the conversion
   APInt(unsigned numBits, StringRef str, uint8_t radix);
 
   /// Simply makes *this a copy of that.
   /// @brief Copy Constructor.
-  APInt(const APInt &that) : BitWidth(that.BitWidth), VAL(0) {
-    if (isSingleWord())
-      VAL = that.VAL;
-    else
+  APInt(const APInt &that) : BitWidth(that.BitWidth) {
+    VAL[0] = 0;
+    if (isSingleWord()) {
+      VAL[0] = that.VAL[0];
+    } else if (isTwoWords()) {
+      VAL[0] = that.VAL[0];
+      VAL[1] = that.VAL[1];
+    } else {
       initSlowCase(that);
     }
+  }
 
   /// \brief Move Constructor.
-  APInt(APInt &&that) : BitWidth(that.BitWidth), VAL(that.VAL) {
+  APInt(APInt &&that) : BitWidth(that.BitWidth) {
+    VAL[0] = that.VAL[0];
+    if (isTwoWords())
+      VAL[1] = that.VAL[1];
     that.BitWidth = 0;
   }
 
   /// \brief Destructor.
   ~APInt() {
     if (needsCleanup())
       delete[] pVal;
   }
 
   /// \brief Default constructor that creates an uninteresting APInt
   /// representing a 1-bit zero value.
   ///
   /// This is useful for object deserialization (pair this with the static
   ///  method Read).
-  explicit APInt() : BitWidth(1), VAL(0) {}
+  explicit APInt() : BitWidth(1) { VAL[0] = 0; }
 
   /// \brief Returns whether this instance allocated memory.
-  bool needsCleanup() const { return !isSingleWord(); }
+  bool needsCleanup() const { return !isInline(); }
 
   /// Used to insert APInt objects, or objects that contain APInt objects, into
   ///  FoldingSets.
   void Profile(FoldingSetNodeID &id) const;
 
   /// @}
   /// \name Value Tests
   /// @{
public:
   /// \returns true if this APInt is positive.
   bool isStrictlyPositive() const { return isNonNegative() && !!*this; }
 
   /// \brief Determine if all bits are set
   ///
   /// This checks to see if the value has all bits of the APInt are set or not.
   bool isAllOnesValue() const {
     if (isSingleWord())
-      return VAL == ~integerPart(0) >> (APINT_BITS_PER_WORD - BitWidth);
+      return VAL[0] == ~integerPart(0) >> (APINT_BITS_PER_WORD - BitWidth);
+    if (isTwoWords())
+      return VAL[0] == ~integerPart(0) &&
+             VAL[1] == ~integerPart(0) >> (APINT_BITS_PER_WORD - BitWidth);
     return countPopulationSlowCase() == BitWidth;
   }
 
   /// \brief Determine if this is the largest unsigned value.
   ///
   /// This checks to see if the value of this APInt is the maximum unsigned
   /// value for the APInt's bit width.
   bool isMaxValue() const { return isAllOnesValue(); }
bool isSignedIntN(unsigned N) const {
     return getMinSignedBits() <= N;
   }
 
   /// \brief Check if this APInt's value is a power of two greater than zero.
   ///
   /// \returns true if the argument APInt value is a power of two > 0.
   bool isPowerOf2() const {
     if (isSingleWord())
-      return isPowerOf2_64(VAL);
+      return isPowerOf2_64(VAL[0]);
+    if (isTwoWords())
+      return VAL[0] != VAL[1] && isPowerOf2_64(VAL[0] | VAL[1]);
     return countPopulationSlowCase() == 1;
   }
 
   /// \brief Check if the APInt's value is returned by getSignBit.
   ///
   /// \returns true if this is the value returned by getSignBit.
   bool isSignBit() const { return isMinSignedValue(); }
 
public:
 
   /// \brief Overload to compute a hash_code for an APInt value.
   friend hash_code hash_value(const APInt &Arg);
 
   /// This function returns a pointer to the internal storage of the APInt.
   /// This is useful for writing out the APInt in binary form without any
   /// conversions.
   const uint64_t *getRawData() const {
-    if (isSingleWord())
-      return &VAL;
+    if (isInline())
+      return &VAL[0];
     return &pVal[0];
   }
 
   /// @}
   /// \name Unary Operators
   /// @{
 
   /// \brief Postfix increment operator.
public:
 
   /// \brief Logical negation operator.
   ///
   /// Performs logical negation operation on this APInt.
   ///
   /// \returns true if *this is zero, false otherwise.
   bool operator!() const {
     if (isSingleWord())
-      return !VAL;
+      return !VAL[0];
+    if (isTwoWords())
+      return !VAL[0] && !VAL[1];
 
     for (unsigned i = 0; i != getNumWords(); ++i)
       if (pVal[i])
         return false;
     return true;
   }
 
   /// @}
   /// \name Assignment Operators
   /// @{
 
   /// \brief Copy assignment operator.
   ///
   /// \returns *this after assignment of RHS.
   APInt &operator=(const APInt &RHS) {
     // If the bitwidths are the same, we can avoid mucking with memory
-    if (isSingleWord() && RHS.isSingleWord()) {
-      VAL = RHS.VAL;
+    if (isInline() && RHS.isInline()) {
+      VAL[0] = RHS.VAL[0];
+      if (RHS.isTwoWords())
+        VAL[1] = RHS.VAL[1];
       BitWidth = RHS.BitWidth;
       return clearUnusedBits();
     }
 
     return AssignSlowCase(RHS);
   }
 
   /// @brief Move assignment operator.
   APInt &operator=(APInt &&that) {
-    if (!isSingleWord()) {
+    if (!isInline()) {
       // The MSVC STL shipped in 2013 requires that self move assignment be a
       // no-op.  Otherwise algorithms like stable_sort will produce answers
       // where half of the output is left in a moved-from state.
       if (this == &that)
         return *this;
       delete[] pVal;
     }
 
     // Use memcpy so that type based alias analysis sees both VAL and pVal
     // as modified.
-    memcpy(&VAL, &that.VAL, sizeof(uint64_t));
+    memcpy(&VAL, &that.VAL, sizeof(uint64_t) * 2);
 
     // If 'this == &that', avoid zeroing our own bitwidth by storing to 'that'
     // first.
     unsigned ThatBitWidth = that.BitWidth;
     that.BitWidth = 0;
     BitWidth = ThatBitWidth;
 
     return *this;
public:
   APInt &operator|=(const APInt &RHS);
 
   /// \brief Bitwise OR assignment operator.
   ///
   /// Performs a bitwise OR operation on this APInt and RHS. RHS is
   /// logically zero-extended or truncated to match the bit-width of
   /// the LHS.
   APInt &operator|=(uint64_t RHS) {
-    if (isSingleWord()) {
-      VAL |= RHS;
+    if (isInline()) {
+      VAL[0] |= RHS;
       clearUnusedBits();
     } else {
       pVal[0] |= RHS;
     }
     return *this;
   }
 
   /// \brief Bitwise XOR assignment operator.
public:
   /// \brief Bitwise AND operator.
   ///
   /// Performs a bitwise AND operation on *this and RHS.
   ///
   /// \returns An APInt value representing the bitwise AND of *this and RHS.
   APInt operator&(const APInt &RHS) const {
     assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
     if (isSingleWord())
-      return APInt(getBitWidth(), VAL & RHS.VAL);
+      return APInt(getBitWidth(), VAL[0] & RHS.VAL[0]);
+    if (isTwoWords()) {
+      uint64_t Lo = VAL[0] & RHS.VAL[0];
+      uint64_t Hi = VAL[1] & RHS.VAL[1];
+      return APInt(getBitWidth(), {Lo, Hi});
+    }
     return AndSlowCase(RHS);
   }
   APInt LLVM_ATTRIBUTE_UNUSED_RESULT And(const APInt &RHS) const {
     return this->operator&(RHS);
   }
 
   /// \brief Bitwise OR operator.
   ///
   /// Performs a bitwise OR operation on *this and RHS.
   ///
   /// \returns An APInt value representing the bitwise OR of *this and RHS.
   APInt operator|(const APInt &RHS) const {
     assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
     if (isSingleWord())
-      return APInt(getBitWidth(), VAL | RHS.VAL);
+      return APInt(getBitWidth(), VAL[0] | RHS.VAL[0]);
+    if (isTwoWords()) {
+      uint64_t Lo = VAL[0] | RHS.VAL[0];
+      uint64_t Hi = VAL[1] | RHS.VAL[1];
+      return APInt(getBitWidth(), {Lo, Hi});
+    }
     return OrSlowCase(RHS);
   }
 
   /// \brief Bitwise OR function.
   ///
   /// Performs a bitwise or on *this and RHS. This is implemented by simply
   /// calling operator|.
   ///
   /// \returns An APInt value representing the bitwise OR of *this and RHS.
   APInt LLVM_ATTRIBUTE_UNUSED_RESULT Or(const APInt &RHS) const {
     return this->operator|(RHS);
   }
 
   /// \brief Bitwise XOR operator.
   ///
   /// Performs a bitwise XOR operation on *this and RHS.
   ///
   /// \returns An APInt value representing the bitwise XOR of *this and RHS.
   APInt operator^(const APInt &RHS) const {
     assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
     if (isSingleWord())
-      return APInt(BitWidth, VAL ^ RHS.VAL);
+      return APInt(BitWidth, VAL[0] ^ RHS.VAL[0]);
+    if (isTwoWords()) {
+      uint64_t Lo = VAL[0] ^ RHS.VAL[0];
+      uint64_t Hi = VAL[1] ^ RHS.VAL[1];
+      return APInt(getBitWidth(), {Lo, Hi});
+    }
     return XorSlowCase(RHS);
   }
 
   /// \brief Bitwise XOR function.
   ///
   /// Performs a bitwise XOR operation on *this and RHS. This is implemented
   /// through the usage of operator^.
   ///
public:
   /// Logical right-shift this APInt by shiftAmt.
   APInt LLVM_ATTRIBUTE_UNUSED_RESULT lshr(unsigned shiftAmt) const;
 
   /// \brief Left-shift function.
   ///
   /// Left-shift this APInt by shiftAmt.
   APInt LLVM_ATTRIBUTE_UNUSED_RESULT shl(unsigned shiftAmt) const {
     assert(shiftAmt <= BitWidth && "Invalid shift amount");
-    if (isSingleWord()) {
-      if (shiftAmt >= BitWidth)
-        return APInt(BitWidth, 0); // avoid undefined shift results
-      return APInt(BitWidth, VAL << shiftAmt);
+    if (isSingleWord())
+      return APInt(BitWidth, VAL[0] << shiftAmt);
+    if (isTwoWords()) {
+      if (shiftAmt == 0)
+        return *this;
+
+      uint64_t Hi;
+      uint64_t Lo;
+      if (shiftAmt < APINT_BITS_PER_WORD) {
+        Hi =
+            (VAL[1] << shiftAmt) | (VAL[0] >> (APINT_BITS_PER_WORD - shiftAmt));
+        Lo = VAL[0] << shiftAmt;
+      } else {
+        Hi = VAL[0] << (shiftAmt - APINT_BITS_PER_WORD);
+        Lo = 0;
+      }
+      return APInt(BitWidth, {Lo, Hi});
     }
     return shlSlowCase(shiftAmt);
   }
 
   /// \brief Rotate left by rotateAmt.
   APInt LLVM_ATTRIBUTE_UNUSED_RESULT rotl(unsigned rotateAmt) const;
 
   /// \brief Rotate right by rotateAmt.
public:
   APInt sshl_ov(const APInt &Amt, bool &Overflow) const;
   APInt ushl_ov(const APInt &Amt, bool &Overflow) const;
 
   /// \brief Array-indexing support.
   ///
   /// \returns the bit value at bitPosition
   bool operator[](unsigned bitPosition) const {
     assert(bitPosition < getBitWidth() && "Bit position out of bounds!");
-    return (maskBit(bitPosition) &
-            (isSingleWord() ? VAL : pVal[whichWord(bitPosition)])) !=
-           0;
+    uint64_t MaskBit = maskBit(bitPosition);
+    uint64_t Word = getWord(bitPosition);
+    return (MaskBit & Word) != 0;
   }
 
   /// @}
   /// \name Comparison Operators
   /// @{
 
   /// \brief Equality operator.
   ///
   /// Compares this APInt with RHS for the validity of the equality
   /// relationship.
   bool operator==(const APInt &RHS) const {
     assert(BitWidth == RHS.BitWidth && "Comparison requires equal bit widths");
     if (isSingleWord())
-      return VAL == RHS.VAL;
+      return VAL[0] == RHS.VAL[0];
+    if (isTwoWords())
+      return VAL[0] == RHS.VAL[0] && VAL[1] == RHS.VAL[1];
     return EqualSlowCase(RHS);
   }
 
   /// \brief Equality operator.
   ///
   /// Compares this APInt with a uint64_t for the validity of the equality
   /// relationship.
   ///
   /// \returns true if *this == Val
   bool operator==(uint64_t Val) const {
     if (isSingleWord())
-      return VAL == Val;
+      return VAL[0] == Val;
+    if (isTwoWords())
+      return VAL[0] == Val && VAL[1] == 0;
     return EqualSlowCase(Val);
   }
 
   /// \brief Equality comparison.
   ///
   /// Compares this APInt with RHS for the validity of the equality
   /// relationship.
   ///

   APInt LLVM_ATTRIBUTE_UNUSED_RESULT zextOrSelf(unsigned width) const;
 
   /// @}
   /// \name Bit Manipulation Operators
   /// @{
 
   /// \brief Set every bit to 1.
   void setAllBits() {
-    if (isSingleWord())
-      VAL = UINT64_MAX;
-    else {
+    if (isSingleWord()) {
+      VAL[0] = UINT64_MAX;
+    } else if (isTwoWords()) {
+      VAL[0] = UINT64_MAX;
+      VAL[1] = UINT64_MAX;
+    } else {
       // Set all the bits in all the words.
       for (unsigned i = 0; i < getNumWords(); ++i)
         pVal[i] = UINT64_MAX;
     }
     // Clear the unused ones
     clearUnusedBits();
   }
 
   /// \brief Set a given bit to 1.
   ///
   /// Set the given bit to 1 whose position is given as "bitPosition".
   void setBit(unsigned bitPosition);
 
   /// \brief Set every bit to 0.
   void clearAllBits() {
-    if (isSingleWord())
-      VAL = 0;
-    else
+    if (isSingleWord()) {
+      VAL[0] = 0;
+    } else if (isTwoWords()) {
+      VAL[0] = 0;
+      VAL[1] = 0;
+    } else {
       memset(pVal, 0, getNumWords() * APINT_WORD_SIZE);
     }
+  }
 
   /// \brief Set a given bit to 0.
   ///
   /// Set the given bit to 0 whose position is given as "bitPosition".
   void clearBit(unsigned bitPosition);
 
   /// \brief Toggle every bit to its opposite value.
   void flipAllBits() {
-    if (isSingleWord())
-      VAL ^= UINT64_MAX;
-    else {
+    if (isSingleWord()) {
+      VAL[0] ^= UINT64_MAX;
+    } else if (isTwoWords()) {
+      VAL[0] ^= UINT64_MAX;
+      VAL[1] ^= UINT64_MAX;
+    } else {
       for (unsigned i = 0; i < getNumWords(); ++i)
         pVal[i] ^= UINT64_MAX;
     }
     clearUnusedBits();
   }
 
   /// \brief Toggles a given bit to its opposite value.
   ///

 
   /// \brief Get zero extended value
   ///
   /// This method attempts to return the value of this APInt as a zero extended
   /// uint64_t. The bitwidth must be <= 64 or the value must fit within a
   /// uint64_t. Otherwise an assertion will result.
   uint64_t getZExtValue() const {
     if (isSingleWord())
-      return VAL;
+      return VAL[0];
+    if (isTwoWords()) {
+      assert(VAL[1] == 0 && "Too many bits for uint64_t");
+      return VAL[0];
+    }
     assert(getActiveBits() <= 64 && "Too many bits for uint64_t");
     return pVal[0];
   }
 
   /// \brief Get sign extended value
   ///
   /// This method attempts to return the value of this APInt as a sign extended
   /// int64_t. The bit width must be <= 64 or the value must fit within an
   /// int64_t. Otherwise an assertion will result.
   int64_t getSExtValue() const {
     if (isSingleWord())
-      return int64_t(VAL << (APINT_BITS_PER_WORD - BitWidth)) >>
+      return int64_t(VAL[0] << (APINT_BITS_PER_WORD - BitWidth)) >>
              (APINT_BITS_PER_WORD - BitWidth);
+    if (isTwoWords()) {
+      int64_t Sext = int64_t(VAL[0]);
+      assert((Sext < 0
+                  ? SignExtend64(VAL[1], BitWidth - APINT_BITS_PER_WORD) == -1
+                  : VAL[1] == 0) &&
+             "Too many bits for int64_t");
+      return Sext;
+    }
     assert(getMinSignedBits() <= 64 && "Too many bits for int64_t");
     return int64_t(pVal[0]);
   }
 
   /// \brief Get bits required for string value.
   ///
   /// This method determines how many bits are required to hold the APInt
   /// equivalent of the string given by \p str.
   static unsigned getBitsNeeded(StringRef str, uint8_t radix);
 
   /// \brief The APInt version of the countLeadingZeros functions in
   ///   MathExtras.h.
   ///
   /// It counts the number of zeros from the most significant bit to the first
   /// one bit.
   ///
   /// \returns BitWidth if the value is zero, otherwise returns the number of
   ///   zeros from the most significant bit to the first one bits.
   unsigned countLeadingZeros() const {
     if (isSingleWord()) {
       unsigned unusedBits = APINT_BITS_PER_WORD - BitWidth;
-      return llvm::countLeadingZeros(VAL) - unusedBits;
+      return llvm::countLeadingZeros(VAL[0]) - unusedBits;
+    }
+    if (isTwoWords()) {
+      if (VAL[1] == 0)
+        return llvm::countLeadingZeros(VAL[0]) +
+               (BitWidth - APINT_BITS_PER_WORD);
+      unsigned unusedBits = APINT_BITS_PER_WORD * 2 - BitWidth;
+      return llvm::countLeadingZeros(VAL[1]) - unusedBits;
     }
     return countLeadingZerosSlowCase();
   }
 
   /// \brief Count the number of leading one bits.
   ///
   /// This function is an APInt version of the countLeadingOnes
   /// functions in MathExtras.h. It counts the number of ones from the most

   /// This function is an APInt version of the countTrailingOnes
   /// functions in MathExtras.h. It counts the number of ones from the least
   /// significant bit to the first zero bit.
   ///
   /// \returns BitWidth if the value is all ones, otherwise returns the number
   /// of ones from the least significant bit to the first zero bit.
   unsigned countTrailingOnes() const {
     if (isSingleWord())
-      return llvm::countTrailingOnes(VAL);
+      return llvm::countTrailingOnes(VAL[0]);
+    if (isTwoWords())
+      return VAL[0] == -1ULL
+                 ? APINT_BITS_PER_WORD + llvm::countTrailingOnes(VAL[1])
+                 : llvm::countTrailingOnes(VAL[0]);
     return countTrailingOnesSlowCase();
   }
 
   /// \brief Count the number of bits set.
   ///
   /// This function is an APInt version of the countPopulation functions
   /// in MathExtras.h. It counts the number of 1 bits in the APInt value.
   ///
   /// \returns 0 if the value is zero, otherwise returns the number of set bits.
   unsigned countPopulation() const {
     if (isSingleWord())
-      return llvm::countPopulation(VAL);
+      return llvm::countPopulation(VAL[0]);
+    if (isTwoWords())
+      return llvm::countPopulation(VAL[0]) + llvm::countPopulation(VAL[1]);
     return countPopulationSlowCase();
   }
 
   /// @}
   /// \name Conversion Functions
   /// @{
   void print(raw_ostream &OS, bool isSigned) const;
 

   /// The conversion does not do a translation from integer to double, it just
   /// re-interprets the bits as a double. Note that it is valid to do this on
   /// any bit width. Exactly 64 bits will be translated.
   double bitsToDouble() const {
     union {
       uint64_t I;
       double D;
     } T;
-    T.I = (isSingleWord() ? VAL : pVal[0]);
+    T.I = (isInline() ? VAL[0] : pVal[0]);
     return T.D;
   }
 
   /// \brief Converts APInt bits to a double
   ///
   /// The conversion does not do a translation from integer to float, it just
   /// re-interprets the bits as a float. Note that it is valid to do this on
   /// any bit width. Exactly 32 bits will be translated.
   float bitsToFloat() const {
     union {
       unsigned I;
       float F;
     } T;
-    T.I = unsigned((isSingleWord() ? VAL : pVal[0]));
+    T.I = unsigned((isInline() ? VAL[0] : pVal[0]));
     return T.F;
   }
 
   /// \brief Converts a double to APInt bits.
   ///
   /// The conversion does not do a translation from double to integer, it just
   /// re-interprets the bits of the double.
   static APInt LLVM_ATTRIBUTE_UNUSED_RESULT doubleToBits(double V) {

   ///
   /// to get around any mathematical concerns resulting from
   /// referencing 2 in a space where 2 does no exist.
   unsigned nearestLogBase2() const {
     // Special case when we have a bitwidth of 1. If VAL is 1, then we
     // get 0. If VAL is 0, we get UINT64_MAX which gets truncated to
     // UINT32_MAX.
     if (BitWidth == 1)
-      return VAL - 1;
+      return VAL[0] - 1;
 
     // Handle the zero case.
     if (!getBoolValue())
       return UINT32_MAX;
 
     // The non-zero case is handled by computing:
     //
     //   nearestLogBase2(x) = logBase2(x) + x[logBase2(x)-1].

lib/IR/LLVMContextImpl.h

 class GCStrategy;
 class LLVMContext;
 class Type;
 class Value;
 
 struct DenseMapAPIntKeyInfo {
   static inline APInt getEmptyKey() {
     APInt V(nullptr, 0);
-    V.VAL = 0;
+    V.VAL[0] = 0;
     return V;
   }
   static inline APInt getTombstoneKey() {
     APInt V(nullptr, 0);
-    V.VAL = 1;
+    V.VAL[0] = 1;
     return V;
   }
   static unsigned getHashValue(const APInt &Key) {
     return static_cast<unsigned>(hash_value(Key));
   }
   static bool isEqual(const APInt &LHS, const APInt &RHS) {
     return LHS.getBitWidth() == RHS.getBitWidth() && LHS == RHS;
   }

lib/Support/APInt.cpp

 void APInt::initSlowCase(const APInt& that) {
   pVal = getMemory(getNumWords());
   memcpy(pVal, that.pVal, getNumWords() * APINT_WORD_SIZE);
 }
 
 void APInt::initFromArray(ArrayRef<uint64_t> bigVal) {
   assert(BitWidth && "Bitwidth too small");
   assert(bigVal.data() && "Null pointer detected!");
-  if (isSingleWord())
-    VAL = bigVal[0];
-  else {
+  if (isSingleWord()) {
+    VAL[0] = bigVal[0];
+  } else if (isTwoWords()) {
+    VAL[0] = bigVal[0];
+    if (bigVal.size() > 1)
+      VAL[1] = bigVal[1];
+    else
+      VAL[1] = 0;
+  } else {
     // Get memory, cleared to 0
     pVal = getClearedMemory(getNumWords());
     // Calculate the number of words to copy
     unsigned words = std::min<unsigned>(bigVal.size(), getNumWords());
     // Copy the words from bigVal to pVal
     memcpy(pVal, bigVal.data(), words * APINT_WORD_SIZE);
   }
   // Make sure unused high bits are cleared
   clearUnusedBits();
 }
 
 APInt::APInt(unsigned numBits, ArrayRef<uint64_t> bigVal)
-  : BitWidth(numBits), VAL(0) {
+  : BitWidth(numBits) {
+  VAL[0] = 0;
   initFromArray(bigVal);
 }
 
 APInt::APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[])
-  : BitWidth(numBits), VAL(0) {
+  : BitWidth(numBits) {
+  VAL[0] = 0;
   initFromArray(makeArrayRef(bigVal, numWords));
 }
 
 APInt::APInt(unsigned numbits, StringRef Str, uint8_t radix)
-  : BitWidth(numbits), VAL(0) {
+  : BitWidth(numbits) {
   assert(BitWidth && "Bitwidth too small");
+  VAL[0] = 0;
+  if (isTwoWords())
+    VAL[1] = 0;
   fromString(numbits, Str, radix);
 }
 
 APInt& APInt::AssignSlowCase(const APInt& RHS) {
   // Don't do anything for X = X
   if (this == &RHS)
     return *this;
 
   if (BitWidth == RHS.getBitWidth()) {
     // assume same bit-width single-word case is already handled
-    assert(!isSingleWord());
+    assert(!isInline());
     memcpy(pVal, RHS.pVal, getNumWords() * APINT_WORD_SIZE);
     return *this;
   }
 
-  if (isSingleWord()) {
+  if (isInline()) {
     // assume case where both are single words is already handled
-    assert(!RHS.isSingleWord());
-    VAL = 0;
+    assert(!RHS.isInline());
+    VAL[0] = 0;
     pVal = getMemory(RHS.getNumWords());
     memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
   } else if (getNumWords() == RHS.getNumWords())
     memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
-  else if (RHS.isSingleWord()) {
+  else if (RHS.isInline()) {
     delete [] pVal;
-    VAL = RHS.VAL;
+    VAL[0] = RHS.VAL[0];
+    if (RHS.isTwoWords())
+      VAL[1] = RHS.VAL[1];
   } else {
     delete [] pVal;
     pVal = getMemory(RHS.getNumWords());
     memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
   }
   BitWidth = RHS.BitWidth;
   return clearUnusedBits();
 }
 
 APInt& APInt::operator=(uint64_t RHS) {
-  if (isSingleWord())
-    VAL = RHS;
-  else {
+  if (isInline()) {
+    VAL[0] = RHS;
+    if (isTwoWords())
+      VAL[1] = 0;
+  } else {
     pVal[0] = RHS;
     memset(pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE);
   }
   return clearUnusedBits();
 }
 
 /// This method 'profiles' an APInt for use with FoldingSet.
 void APInt::Profile(FoldingSetNodeID& ID) const {
   ID.AddInteger(BitWidth);
 
   if (isSingleWord()) {
-    ID.AddInteger(VAL);
+    ID.AddInteger(VAL[0]);
+    return;
+  }
+
+  if (isTwoWords()) {
+    ID.AddInteger(VAL[0]);
+    ID.AddInteger(VAL[1]);
     return;
   }
 
   unsigned NumWords = getNumWords();
   for (unsigned i = 0; i < NumWords; ++i)
     ID.AddInteger(pVal[i]);
 }
 
for (unsigned i = 0; i < len; ++i) {
     }
   }
   return y;
 }
 
 /// @brief Prefix increment operator. Increments the APInt by one.
 APInt& APInt::operator++() {
   if (isSingleWord())
-    ++VAL;
+    ++VAL[0];
+  else if (isTwoWords())
+    add_1(VAL, VAL, /*len=*/2, 1);
   else
     add_1(pVal, pVal, getNumWords(), 1);
   return clearUnusedBits();
 }
 
 /// This function subtracts a single "digit" (64-bit word), y, from
 /// the multi-digit integer array, x[], propagating the borrowed 1 value until
 /// no further borrowing is neeeded or it runs out of "digits" in x.  The result
for (unsigned i = 0; i < len; ++i) {
     }
   }
   return bool(y);
 }
 
 /// @brief Prefix decrement operator. Decrements the APInt by one.
 APInt& APInt::operator--() {
   if (isSingleWord())
-    --VAL;
+    --VAL[0];
+  else if (isTwoWords())
+    sub_1(VAL, /*len=*/2, 1);
   else
     sub_1(pVal, getNumWords(), 1);
   return clearUnusedBits();
 }
 
 /// This function adds the integer array x to the integer array Y and
 /// places the result in dest.
 /// @returns the carry out from the addition
static bool add(uint64_t *dest, const uint64_t *x, const uint64_t *y,
   return carry;
 }
 
 /// Adds the RHS APint to this APInt.
 /// @returns this, after addition of RHS.
 /// @brief Addition assignment operator.
 APInt& APInt::operator+=(const APInt& RHS) {
   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
-  if (isSingleWord())
-    VAL += RHS.VAL;
-  else {
+  if (isSingleWord()){
+    VAL[0] += RHS.VAL[0];
+  } else if (isTwoWords()) {
+    add(VAL, VAL, RHS.VAL, /*len=*/2);
+  } else {
     add(pVal, pVal, RHS.pVal, getNumWords());
   }
   return clearUnusedBits();
 }
 
 APInt& APInt::operator+=(uint64_t RHS) {
   if (isSingleWord())
-    VAL += RHS;
+    VAL[0] += RHS;
+  else if (isTwoWords())
+    add_1(VAL, VAL, /*len=*/2, RHS);
   else
     add_1(pVal, pVal, getNumWords(), RHS);
   return clearUnusedBits();
 }
 
 /// Subtracts the integer array y from the integer array x
 /// @returns returns the borrow out.
 /// @brief Generalized subtraction of 64-bit integer arrays.

 }
 
 /// Subtracts the RHS APInt from this APInt
 /// @returns this, after subtraction
 /// @brief Subtraction assignment operator.
 APInt& APInt::operator-=(const APInt& RHS) {
   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
   if (isSingleWord())
-    VAL -= RHS.VAL;
+    VAL[0] -= RHS.VAL[0];
+  else if (isTwoWords())
+    sub(VAL, VAL, RHS.VAL, /*len=*/2);
   else
     sub(pVal, pVal, RHS.pVal, getNumWords());
   return clearUnusedBits();
 }
 
 APInt& APInt::operator-=(uint64_t RHS) {
   if (isSingleWord())
-    VAL -= RHS;
+    VAL[0] -= RHS;
+  else if (isTwoWords())
+    sub_1(VAL, /*len=*/2, RHS);
   else
     sub_1(pVal, getNumWords(), RHS);
   return clearUnusedBits();
 }
 
 /// Multiplies an integer array, x, by a uint64_t integer and places the result
 /// into dest.
 /// @returns the carry out of the multiplication.
for (unsigned i = 1; i < ylen; ++i) {
     }
     dest[i+xlen] = carry;
   }
 }
 
 APInt& APInt::operator*=(const APInt& RHS) {
   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
   if (isSingleWord()) {
-    VAL *= RHS.VAL;
+    VAL[0] *= RHS.VAL[0];
+    clearUnusedBits();
+    return *this;
+  }
+  if (isTwoWords()) {
+#ifdef __SIZEOF_INT128__
+    __uint128_t LHSVal = (((__uint128_t)VAL[1]) << 64) | VAL[0];
+    __uint128_t RHSVal = (((__uint128_t)RHS.VAL[1]) << 64) | RHS.VAL[0];
+    __uint128_t Result = LHSVal * RHSVal;
+    VAL[0] = Result;
+    VAL[1] = Result >> 64;
+    clearUnusedBits();
+    return *this;
+#else
+    // https://chromium.googlesource.com/chromium/src/net/+/master/base/int128.h
+    uint64_t hi = VAL[1];
+    uint64_t lo = VAL[0];
+    uint64_t rhs_hi = RHS.VAL[1];
+    uint64_t rhs_lo = RHS.VAL[0];
+    uint64_t a96 = hi >> 32;
+    uint64_t a64 = hi & 0xffffffffu;
+    uint64_t a32 = lo >> 32;
+    uint64_t a00 = lo & 0xffffffffu;
+    uint64_t b96 = rhs_hi >> 32;
+    uint64_t b64 = rhs_hi & 0xffffffffu;
+    uint64_t b32 = rhs_lo >> 32;
+    uint64_t b00 = rhs_lo & 0xffffffffu;
+    // multiply [a96 .. a00] x [b96 .. b00]
+    // terms higher than c96 disappear off the high side
+    // terms c96 and c64 are safe to ignore carry bit
+    uint64_t c96 = a96 * b00 + a64 * b32 + a32 * b64 + a00 * b96;
+    uint64_t c64 = a64 * b00 + a32 * b32 + a00 * b64;
+    VAL[1] = (c96 << 32) + c64;
+    VAL[0] = 0;
     clearUnusedBits();
+    // add terms after this one at a time to capture carry
+    *this += APInt(BitWidth, a32 * b00) << 32;
+    *this += APInt(BitWidth, a00 * b32) << 32;
+    *this += a00 * b00;
     return *this;
+#endif
   }
 
   // Get some bit facts about LHS and check for zero
   unsigned lhsBits = getActiveBits();
   unsigned lhsWords = !lhsBits ? 0 : whichWord(lhsBits - 1) + 1;
   if (!lhsWords)
     // 0 * X ===> 0
     return *this;
#endif
   // delete dest array and return
   delete[] dest;
   return *this;
 }
 
 APInt& APInt::operator&=(const APInt& RHS) {
   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
   if (isSingleWord()) {
-    VAL &= RHS.VAL;
+    VAL[0] &= RHS.VAL[0];
+    return *this;
+  }
+  if (isTwoWords()) {
+    VAL[0] &= RHS.VAL[0];
+    VAL[1] &= RHS.VAL[1];
     return *this;
   }
   unsigned numWords = getNumWords();
   for (unsigned i = 0; i < numWords; ++i)
     pVal[i] &= RHS.pVal[i];
   return *this;
 }
 
 APInt& APInt::operator|=(const APInt& RHS) {
   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
   if (isSingleWord()) {
-    VAL |= RHS.VAL;
+    VAL[0] |= RHS.VAL[0];
+    return *this;
+  }
+  if (isTwoWords()) {
+    VAL[0] |= RHS.VAL[0];
+    VAL[1] |= RHS.VAL[1];
     return *this;
   }
   unsigned numWords = getNumWords();
   for (unsigned i = 0; i < numWords; ++i)
     pVal[i] |= RHS.pVal[i];
   return *this;
 }
 
 APInt& APInt::operator^=(const APInt& RHS) {
   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
   if (isSingleWord()) {
-    VAL ^= RHS.VAL;
+    VAL[0] ^= RHS.VAL[0];
+    this->clearUnusedBits();
+    return *this;
+  }
+  if (isTwoWords()) {
+    VAL[0] ^= RHS.VAL[0];
+    VAL[1] ^= RHS.VAL[1];
     this->clearUnusedBits();
     return *this;
   }
   unsigned numWords = getNumWords();
   for (unsigned i = 0; i < numWords; ++i)
     pVal[i] ^= RHS.pVal[i];
   return clearUnusedBits();
 }
APInt APInt::XorSlowCase(const APInt& RHS) const {
   // 0^0==1 so clear the high bits in case they got set.
   Result.clearUnusedBits();
   return Result;
 }
 
 APInt APInt::operator*(const APInt& RHS) const {
   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
   if (isSingleWord())
-    return APInt(BitWidth, VAL * RHS.VAL);
+    return APInt(BitWidth, VAL[0] * RHS.VAL[0]);
   APInt Result(*this);
   Result *= RHS;
   return Result;
 }
 
 bool APInt::EqualSlowCase(const APInt& RHS) const {
   return std::equal(pVal, pVal + getNumWords(), RHS.pVal);
 }
 
 bool APInt::EqualSlowCase(uint64_t Val) const {
   unsigned n = getActiveBits();
   if (n <= APINT_BITS_PER_WORD)
     return pVal[0] == Val;
   else
     return false;
 }
 
 bool APInt::ult(const APInt& RHS) const {
   assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
   if (isSingleWord())
-    return VAL < RHS.VAL;
+    return VAL[0] < RHS.VAL[0];
+  if (isTwoWords())
+    return VAL[1] == RHS.VAL[1] ? VAL[0] < RHS.VAL[0] : VAL[1] < RHS.VAL[1];
 
   // Get active bit length of both operands
   unsigned n1 = getActiveBits();
   unsigned n2 = RHS.getActiveBits();
 
   // If magnitude of LHS is less than RHS, return true.
   if (n1 < n2)
     return true;
if (pVal[i] < RHS.pVal[i])
       return true;
   }
   return false;
 }
 
 bool APInt::slt(const APInt& RHS) const {
   assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
   if (isSingleWord()) {
-    int64_t lhsSext = SignExtend64(VAL, BitWidth);
-    int64_t rhsSext = SignExtend64(RHS.VAL, BitWidth);
+    int64_t lhsSext = SignExtend64(VAL[0], BitWidth);
+    int64_t rhsSext = SignExtend64(RHS.VAL[0], BitWidth);
+    return lhsSext < rhsSext;
+  }
+  if (isTwoWords()) {
+    if (VAL[1] == RHS.VAL[1])
+      return VAL[0] < RHS.VAL[0];
+    unsigned HighBits = BitWidth - APINT_BITS_PER_WORD;
+    int64_t lhsSext = SignExtend64(VAL[1], HighBits);
+    int64_t rhsSext = SignExtend64(RHS.VAL[1], HighBits);
     return lhsSext < rhsSext;
   }
 
   bool lhsNeg = isNegative();
   bool rhsNeg = RHS.isNegative();
 
   // If the sign bits don't match, then (LHS < RHS) if LHS is negative
   if (lhsNeg != rhsNeg)
     return lhsNeg;
 
   // Otherwise we can just use an unsigned comparision, because even negative
   // numbers compare correctly this way if both have the same signed-ness.
   return ult(RHS);
 }
 
 void APInt::setBit(unsigned bitPosition) {
   if (isSingleWord())
-    VAL |= maskBit(bitPosition);
+    VAL[0] |= maskBit(bitPosition);
+  else if (isTwoWords())
+    VAL[whichWord(bitPosition)] |= maskBit(bitPosition);
   else
     pVal[whichWord(bitPosition)] |= maskBit(bitPosition);
 }
 
 /// Set the given bit to 0 whose position is given as "bitPosition".
 /// @brief Set a given bit to 0.
 void APInt::clearBit(unsigned bitPosition) {
   if (isSingleWord())
-    VAL &= ~maskBit(bitPosition);
+    VAL[0] &= ~maskBit(bitPosition);
+  else if (isTwoWords())
+    VAL[whichWord(bitPosition)] &= ~maskBit(bitPosition);
   else
     pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition);
 }
 
 /// @brief Toggle every bit to its opposite value.
 
 /// Toggle a given bit to its opposite value whose position is given
 /// as "bitPosition".
if (log == (unsigned)-1) {
     return isNegative + 1;
   } else {
     return isNegative + log + 1;
   }
 }
 
 hash_code llvm::hash_value(const APInt &Arg) {
   if (Arg.isSingleWord())
-    return hash_combine(Arg.VAL);
+    return hash_combine(Arg.VAL[0]);
+  if (Arg.isTwoWords())
+    return hash_combine(Arg.VAL[0], Arg.VAL[1]);
 
   return hash_combine_range(Arg.pVal, Arg.pVal + Arg.getNumWords());
 }
 
 bool APInt::isSplat(unsigned SplatSizeInBits) const {
   assert(getBitWidth() % SplatSizeInBits == 0 &&
          "SplatSizeInBits must divide width!");
   // We can check that all parts of an integer are equal by making use of a
unsigned APInt::countLeadingZerosSlowCase() const {
   // Adjust for unused bits in the most significant word (they are zero).
   unsigned Mod = BitWidth % APINT_BITS_PER_WORD;
   Count -= Mod > 0 ? APINT_BITS_PER_WORD - Mod : 0;
   return Count;
 }
 
 unsigned APInt::countLeadingOnes() const {
   if (isSingleWord())
-    return llvm::countLeadingOnes(VAL << (APINT_BITS_PER_WORD - BitWidth));
+    return llvm::countLeadingOnes(VAL[0] << (APINT_BITS_PER_WORD - BitWidth));
+  if (isTwoWords()) {
+    unsigned Count =
+        llvm::countLeadingOnes(VAL[1] << (APINT_BITS_PER_WORD * 2 - BitWidth));
+    if (Count == BitWidth - APINT_BITS_PER_WORD)
+      Count += llvm::countLeadingOnes(VAL[0]);
+    return Count;
+  }
 
   unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD;
   unsigned shift;
   if (!highWordBits) {
     highWordBits = APINT_BITS_PER_WORD;
     shift = 0;
   } else {
     shift = APINT_BITS_PER_WORD - highWordBits;
for (i--; i >= 0; --i) {
       }
     }
   }
   return Count;
 }
 
 unsigned APInt::countTrailingZeros() const {
   if (isSingleWord())
-    return std::min(unsigned(llvm::countTrailingZeros(VAL)), BitWidth);
+    return std::min(unsigned(llvm::countTrailingZeros(VAL[0])), BitWidth);
+  if (isTwoWords()) {
+    size_t Count = llvm::countTrailingZeros(VAL[0]);
+    if (Count == APINT_BITS_PER_WORD)
+      Count += std::min(unsigned(llvm::countTrailingZeros(VAL[1])),
+                        BitWidth - APINT_BITS_PER_WORD);
+    return Count;
+  }
   unsigned Count = 0;
   unsigned i = 0;
   for (; i < getNumWords() && pVal[i] == 0; ++i)
     Count += APINT_BITS_PER_WORD;
   if (i < getNumWords())
     Count += llvm::countTrailingZeros(pVal[i]);
   return std::min(Count, BitWidth);
 }
unsigned APInt::countPopulationSlowCase() const {
   unsigned Count = 0;
   for (unsigned i = 0; i < getNumWords(); ++i)
     Count += llvm::countPopulation(pVal[i]);
   return Count;
 }
 
 /// Perform a logical right-shift from Src to Dst, which must be equal or
 /// non-overlapping, of Words words, by Shift, which must be less than 64.
-static void lshrNear(uint64_t *Dst, uint64_t *Src, unsigned Words,
+static void lshrNear(uint64_t *Dst, const uint64_t *Src, unsigned Words,
                      unsigned Shift) {
   uint64_t Carry = 0;
   for (int I = Words - 1; I >= 0; --I) {
     uint64_t Tmp = Src[I];
     Dst[I] = (Tmp >> Shift) | Carry;
     Carry = Tmp << (64 - Shift);
   }
 }
 
 APInt APInt::byteSwap() const {
   assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
   if (BitWidth == 16)
-    return APInt(BitWidth, ByteSwap_16(uint16_t(VAL)));
+    return APInt(BitWidth, ByteSwap_16(uint16_t(VAL[0])));
   if (BitWidth == 32)
-    return APInt(BitWidth, ByteSwap_32(unsigned(VAL)));
+    return APInt(BitWidth, ByteSwap_32(unsigned(VAL[0])));
   if (BitWidth == 48) {
-    unsigned Tmp1 = unsigned(VAL >> 16);
+    unsigned Tmp1 = unsigned(VAL[0] >> 16);
     Tmp1 = ByteSwap_32(Tmp1);
-    uint16_t Tmp2 = uint16_t(VAL);
+    uint16_t Tmp2 = uint16_t(VAL[0]);
     Tmp2 = ByteSwap_16(Tmp2);
     return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
   }
   if (BitWidth == 64)
-    return APInt(BitWidth, ByteSwap_64(VAL));
+    return APInt(BitWidth, ByteSwap_64(VAL[0]));
 
   APInt Result(getNumWords() * APINT_BITS_PER_WORD, 0);
   for (unsigned I = 0, N = getNumWords(); I != N; ++I)
-    Result.pVal[I] = ByteSwap_64(pVal[N - I - 1]);
+    Result.getMutableRawData()[I] = ByteSwap_64(getRawData()[N - I - 1]);
   if (Result.BitWidth != BitWidth) {
-    lshrNear(Result.pVal, Result.pVal, getNumWords(),
+    lshrNear(Result.getMutableRawData(), Result.getRawData(), getNumWords(),
              Result.BitWidth - BitWidth);
     Result.BitWidth = BitWidth;
   }
   return Result;
 }
 
 APInt APInt::reverseBits() const {
   switch (BitWidth) {
   case 64:
-    return APInt(BitWidth, llvm::reverseBits<uint64_t>(VAL));
+    return APInt(BitWidth, llvm::reverseBits<uint64_t>(VAL[0]));
   case 32:
-    return APInt(BitWidth, llvm::reverseBits<uint32_t>(VAL));
+    return APInt(BitWidth, llvm::reverseBits<uint32_t>(VAL[0]));
   case 16:
-    return APInt(BitWidth, llvm::reverseBits<uint16_t>(VAL));
+    return APInt(BitWidth, llvm::reverseBits<uint16_t>(VAL[0]));
   case 8:
-    return APInt(BitWidth, llvm::reverseBits<uint8_t>(VAL));
+    return APInt(BitWidth, llvm::reverseBits<uint8_t>(VAL[0]));
   default:
     break;
   }
 
   APInt Val(*this);
   APInt Reversed(*this);
   int S = BitWidth - 1;
 
double APInt::roundToDouble(bool isSigned) const {
   }
   exp += 1023; // Increment for 1023 bias
 
   // Number of bits in mantissa is 52. To obtain the mantissa value, we must
   // extract the high 52 bits from the correct words in pVal.
   uint64_t mantissa;
   unsigned hiWord = whichWord(n-1);
   if (hiWord == 0) {
-    mantissa = Tmp.pVal[0];
+    mantissa = Tmp.getRawData()[0];
     if (n > 52)
       mantissa >>= n - 52; // shift down, we want the top 52 bits.
   } else {
     assert(hiWord > 0 && "huh?");
-    uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
-    uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
+    uint64_t hibits = Tmp.getRawData()[hiWord]
+                      << (52 - n % APINT_BITS_PER_WORD);
+    uint64_t lobits =
+        Tmp.getRawData()[hiWord - 1] >> (11 + n % APINT_BITS_PER_WORD);
     mantissa = hibits | lobits;
   }
 
   // The leading bit of mantissa is implicit, so get rid of it.
   uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
   union {
     double D;
     uint64_t I;
   } T;
   T.I = sign | (exp << 52) | mantissa;
   return T.D;
 }
 
 // Truncate to new width.
 APInt APInt::trunc(unsigned width) const {
   assert(width < BitWidth && "Invalid APInt Truncate request");
   assert(width && "Can't truncate to 0 bits");
 
   if (width <= APINT_BITS_PER_WORD)
     return APInt(width, getRawData()[0]);
+  if (width <= APINT_BITS_PER_WORD * 2) {
+    uint64_t Lo = getRawData()[0];
+    uint64_t Hi = getRawData()[1];
+    return APInt(width, {Lo, Hi});
+  }
 
   APInt Result(getMemory(getNumWords(width)), width);
 
   // Copy full words.
   unsigned i;
   for (i = 0; i != width / APINT_BITS_PER_WORD; i++)
     Result.pVal[i] = pVal[i];
 
   // Truncate and copy any partial word.
   unsigned bits = (0 - width) % APINT_BITS_PER_WORD;
   if (bits != 0)
     Result.pVal[i] = pVal[i] << bits >> bits;
 
   return Result;
 }
 
 // Sign extend to a new width.
 APInt APInt::sext(unsigned width) const {
   assert(width > BitWidth && "Invalid APInt SignExtend request");
 
   if (width <= APINT_BITS_PER_WORD) {
-    uint64_t val = VAL << (APINT_BITS_PER_WORD - BitWidth);
+    uint64_t val = VAL[0] << (APINT_BITS_PER_WORD - BitWidth);
     val = (int64_t)val >> (width - BitWidth);
     return APInt(width, val >> (APINT_BITS_PER_WORD - width));
   }
+  if (width <= APINT_BITS_PER_WORD * 2) {
+    uint64_t Lo;
+    uint64_t Hi;
+    if (BitWidth > APINT_BITS_PER_WORD) {
+      Lo = VAL[0];
+      Hi = SignExtend64(VAL[1], BitWidth - APINT_BITS_PER_WORD);
+    } else {
+      Lo = SignExtend64(VAL[0], BitWidth);
+      Hi = static_cast<int64_t>(Lo) < 0 ? -1ULL : 0;
+    }
+    return APInt(width, {Lo, Hi});
+  }
 
   APInt Result(getMemory(getNumWords(width)), width);
 
   // Copy full words.
   unsigned i;
   uint64_t word = 0;
   for (i = 0; i != BitWidth / APINT_BITS_PER_WORD; i++) {
     word = getRawData()[i];
APInt APInt::sext(unsigned width) const {
   return Result;
 }
 
 //  Zero extend to a new width.
 APInt APInt::zext(unsigned width) const {
   assert(width > BitWidth && "Invalid APInt ZeroExtend request");
 
   if (width <= APINT_BITS_PER_WORD)
-    return APInt(width, VAL);
+    return APInt(width, VAL[0]);
+  if (width <= APINT_BITS_PER_WORD * 2) {
+    uint64_t Lo = VAL[0];
+    uint64_t Hi = BitWidth > APINT_BITS_PER_WORD ? VAL[1] : 0;
+    return APInt(width, {Lo, Hi});
+  }
 
   APInt Result(getMemory(getNumWords(width)), width);
 
   // Copy words.
   unsigned i;
   for (i = 0; i != getNumWords(); i++)
     Result.pVal[i] = getRawData()[i];
 

 /// Arithmetic right-shift this APInt by shiftAmt.
 /// @brief Arithmetic right-shift function.
 APInt APInt::ashr(unsigned shiftAmt) const {
   assert(shiftAmt <= BitWidth && "Invalid shift amount");
   // Handle a degenerate case
   if (shiftAmt == 0)
     return *this;
 
-  // Handle single word shifts with built-in ashr
-  if (isSingleWord()) {
-    if (shiftAmt == BitWidth)
-      return APInt(BitWidth, 0); // undefined
-    return APInt(BitWidth, SignExtend64(VAL, BitWidth) >> shiftAmt);
-  }
-
   // If all the bits were shifted out, the result is, technically, undefined.
   // We return -1 if it was negative, 0 otherwise. We check this early to avoid
   // issues in the algorithm below.
   if (shiftAmt == BitWidth) {
     if (isNegative())
       return APInt(BitWidth, -1ULL, true);
     else
       return APInt(BitWidth, 0);
   }
 
+  // Handle single word shifts with built-in ashr
+  if (isSingleWord())
+    return APInt(BitWidth, SignExtend64(VAL[0], BitWidth) >> shiftAmt);
+  if (isTwoWords()) {
+    uint64_t Hi;
+    uint64_t Lo;
+    unsigned HighBits = BitWidth - APINT_BITS_PER_WORD;
+    int64_t HighSext = SignExtend64(VAL[1], HighBits);
+#ifdef __SIZEOF_INT128__
+    __int128_t Val = (((__uint128_t)HighSext) << 64) | VAL[0];
+    __int128_t Result = Val >> shiftAmt;
+    Lo = Result;
+    Hi = Result >> 64;
+#else
+    if (shiftAmt < 64) {
+      Lo = (VAL[0] >> shiftAmt) | (HighSext << (64 - shiftAmt));
+      Hi = HighSext >> shiftAmt;
+    } else {
+      Lo = HighSext >> (shiftAmt - 64);
+      Hi = HighSext < 0 ? -1ULL : 0ULL;
+    }
+#endif
+    return APInt(BitWidth, {Lo, Hi});
+  }
+
   // Create some space for the result.
   uint64_t * val = new uint64_t[getNumWords()];
 
   // Compute some values needed by the following shift algorithms
   unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word
   unsigned offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift
   unsigned breakWord = getNumWords() - 1 - offset; // last word affected
   unsigned bitsInWord = whichBit(BitWidth); // how many bits in last word?

 /// @brief Logical right-shift function.
 APInt APInt::lshr(const APInt &shiftAmt) const {
   return lshr((unsigned)shiftAmt.getLimitedValue(BitWidth));
 }
 
 /// Logical right-shift this APInt by shiftAmt.
 /// @brief Logical right-shift function.
 APInt APInt::lshr(unsigned shiftAmt) const {
-  if (isSingleWord()) {
-    if (shiftAmt >= BitWidth)
-      return APInt(BitWidth, 0);
-    else
-      return APInt(BitWidth, this->VAL >> shiftAmt);
-  }
-
   // If all the bits were shifted out, the result is 0. This avoids issues
   // with shifting by the size of the integer type, which produces undefined
   // results. We define these "undefined results" to always be 0.
   if (shiftAmt >= BitWidth)
     return APInt(BitWidth, 0);
 
+  if (isSingleWord())
+    return APInt(BitWidth, this->VAL[0] >> shiftAmt);
+  if (isTwoWords()) {
+    if (shiftAmt == 0)
+      return *this;
+    uint64_t Hi;
+    uint64_t Lo;
+#ifdef __SIZEOF_INT128__
+    __uint128_t Val = (((__uint128_t)VAL[1]) << 64) | VAL[0];
+    __uint128_t Result = Val >> shiftAmt;
+    Lo = Result;
+    Hi = Result >> 64;
+#else
+    if (shiftAmt < 64) {
+      Lo = (VAL[0] >> shiftAmt) | (VAL[1] << (64 - shiftAmt));
+      Hi = VAL[1] >> shiftAmt;
+    } else {
+      Lo = VAL[1] >> (shiftAmt - 64);
+      Hi = 0;
+    }
+#endif
+    return APInt(BitWidth, {Lo, Hi});
+  }
+
   // If none of the bits are shifted out, the result is *this. This avoids
   // issues with shifting by the size of the integer type, which produces
   // undefined results in the code below. This is also an optimization.
   if (shiftAmt == 0)
     return *this;
 
   // Create some space for the result.
   uint64_t * val = new uint64_t[getNumWords()];

 /// Left-shift this APInt by shiftAmt.
 /// @brief Left-shift function.
 APInt APInt::shl(const APInt &shiftAmt) const {
   // It's undefined behavior in C to shift by BitWidth or greater.
   return shl((unsigned)shiftAmt.getLimitedValue(BitWidth));
 }
 
 APInt APInt::shlSlowCase(unsigned shiftAmt) const {
-  // If all the bits were shifted out, the result is 0. This avoids issues
-  // with shifting by the size of the integer type, which produces undefined
-  // results. We define these "undefined results" to always be 0.
-  if (shiftAmt == BitWidth)
-    return APInt(BitWidth, 0);
+  assert(shiftAmt <= BitWidth && "Invalid shift amount");
 
   // If none of the bits are shifted out, the result is *this. This avoids a
   // lshr by the words size in the loop below which can produce incorrect
   // results. It also avoids the expensive computation below for a common case.
   if (shiftAmt == 0)
     return *this;
 
   // Create some space for the result.
static const uint8_t results[32] = {
       /*     0 */ 0,
       /*  1- 2 */ 1, 1,
       /*  3- 6 */ 2, 2, 2, 2,
       /*  7-12 */ 3, 3, 3, 3, 3, 3,
       /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
       /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
       /*    31 */ 6
     };
-    return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]);
+    return APInt(BitWidth, results[getRawData()[0]]);
   }
 
   // If the magnitude of the value fits in less than 52 bits (the precision of
   // an IEEE double precision floating point value), then we can use the
   // libc sqrt function which will probably use a hardware sqrt computation.
   // This should be faster than the algorithm below.
   if (magnitude < 52) {
-    return APInt(BitWidth,
-                 uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0])))));
+    return APInt(BitWidth, uint64_t(::round(::sqrt(double(getRawData()[0])))));
   }
 
   // Okay, all the short cuts are exhausted. We must compute it. The following
   // is a classical Babylonian method for computing the square root. This code
   // was adapted to APInt from a wikipedia article on such computations.
   // See http://www.wikipedia.org/ and go to the page named
   // Calculate_an_integer_square_root.
   unsigned nbits = BitWidth, i = 4;
if ((Remainder?4:3)*n+2*m+1 <= 128) {
     Q = new unsigned[m+n];
     if (Remainder)
       R = new unsigned[n];
   }
 
   // Initialize the dividend
   memset(U, 0, (m+n+1)*sizeof(unsigned));
   for (unsigned i = 0; i < lhsWords; ++i) {
-    uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]);
+    uint64_t tmp = LHS.getRawData()[i];
     U[i * 2] = (unsigned)(tmp & mask);
     U[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
   }
   U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
 
   // Initialize the divisor
   memset(V, 0, (n)*sizeof(unsigned));
   for (unsigned i = 0; i < rhsWords; ++i) {
-    uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]);
+    uint64_t tmp = RHS.getRawData()[i];
     V[i * 2] = (unsigned)(tmp & mask);
     V[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
   }
 
   // initialize the quotient and remainder
   memset(Q, 0, (m+n) * sizeof(unsigned));
   if (Remainder)
     memset(R, 0, n * sizeof(unsigned));
if (n == 1) {
     // case n > 1.
     KnuthDiv(U, V, Q, R, m, n);
   }
 
   // If the caller wants the quotient
   if (Quotient) {
     // Set up the Quotient value's memory.
     if (Quotient->BitWidth != LHS.BitWidth) {
-      if (Quotient->isSingleWord())
-        Quotient->VAL = 0;
-      else
+      if (Quotient->isSingleWord()) {
+        Quotient->VAL[0] = 0;
+      } else if (Quotient->isTwoWords()) {
+        Quotient->VAL[0] = 0;
+        Quotient->VAL[1] = 0;
+      } else {
         delete [] Quotient->pVal;
+      }
       Quotient->BitWidth = LHS.BitWidth;
-      if (!Quotient->isSingleWord())
+      if (!Quotient->isInline())
         Quotient->pVal = getClearedMemory(Quotient->getNumWords());
     } else
       Quotient->clearAllBits();
 
     // The quotient is in Q. Reconstitute the quotient into Quotient's low
     // order words.
     // This case is currently dead as all users of divide() handle trivial cases
     // earlier.
     if (lhsWords == 1) {
       uint64_t tmp =
         uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2));
-      if (Quotient->isSingleWord())
-        Quotient->VAL = tmp;
-      else
-        Quotient->pVal[0] = tmp;
+      Quotient->getMutableRawData()[0] = tmp;
     } else {
-      assert(!Quotient->isSingleWord() && "Quotient APInt not large enough");
       for (unsigned i = 0; i < lhsWords; ++i)
-        Quotient->pVal[i] =
-          uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2));
+        Quotient->getMutableRawData()[i] =
+            uint64_t(Q[i * 2]) |
+            (uint64_t(Q[i * 2 + 1]) << (APINT_BITS_PER_WORD / 2));
     }
   }
 
   // If the caller wants the remainder
   if (Remainder) {
     // Set up the Remainder value's memory.
     if (Remainder->BitWidth != RHS.BitWidth) {
-      if (Remainder->isSingleWord())
-        Remainder->VAL = 0;
-      else
+      if (Remainder->isSingleWord()) {
+        Remainder->VAL[0] = 0;
+      } else if (Remainder->isTwoWords()) {
+        Remainder->VAL[0] = 0;
+        Remainder->VAL[1] = 0;
+      } else {
         delete [] Remainder->pVal;
+      }
       Remainder->BitWidth = RHS.BitWidth;
-      if (!Remainder->isSingleWord())
+      if (!Remainder->isInline())
         Remainder->pVal = getClearedMemory(Remainder->getNumWords());
     } else
       Remainder->clearAllBits();
 
     // The remainder is in R. Reconstitute the remainder into Remainder's low
     // order words.
     if (rhsWords == 1) {
       uint64_t tmp =
         uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2));
-      if (Remainder->isSingleWord())
-        Remainder->VAL = tmp;
-      else
-        Remainder->pVal[0] = tmp;
+      Remainder->getMutableRawData()[0] = tmp;
     } else {
-      assert(!Remainder->isSingleWord() && "Remainder APInt not large enough");
       for (unsigned i = 0; i < rhsWords; ++i)
-        Remainder->pVal[i] =
-          uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2));
+        Remainder->getMutableRawData()[i] =
+            uint64_t(R[i * 2]) |
+            (uint64_t(R[i * 2 + 1]) << (APINT_BITS_PER_WORD / 2));
     }
   }
 
   // Clean up the memory we allocated.
   if (U != &SPACE[0]) {
     delete [] U;
     delete [] V;
     delete [] Q;
     delete [] R;
   }
 }
 
 APInt APInt::udiv(const APInt& RHS) const {
   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
 
   // First, deal with the easy case
   if (isSingleWord()) {
-    assert(RHS.VAL != 0 && "Divide by zero?");
-    return APInt(BitWidth, VAL / RHS.VAL);
+    assert(RHS.VAL[0] != 0 && "Divide by zero?");
+    return APInt(BitWidth, VAL[0] / RHS.VAL[0]);
   }
+#ifdef __SIZEOF_INT128__
+  if (isTwoWords()) {
+    __uint128_t LHSVal = (((__uint128_t)VAL[1]) << 64) | VAL[0];
+    __uint128_t RHSVal = (((__uint128_t)RHS.VAL[1]) << 64) | RHS.VAL[0];
+    __uint128_t Result = LHSVal / RHSVal;
+    uint64_t Lo = Result;
+    uint64_t Hi = Result >> 64;
+    return APInt(BitWidth, {Lo, Hi});
+  }
+#endif
 
   // Get some facts about the LHS and RHS number of bits and words
   unsigned rhsBits = RHS.getActiveBits();
   unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
   assert(rhsWords && "Divided by zero???");
   unsigned lhsBits = this->getActiveBits();
   unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
 
APInt APInt::sdiv(const APInt &RHS) const {
   if (RHS.isNegative())
     return -(this->udiv(-RHS));
   return this->udiv(RHS);
 }
 
 APInt APInt::urem(const APInt& RHS) const {
   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
   if (isSingleWord()) {
-    assert(RHS.VAL != 0 && "Remainder by zero?");
-    return APInt(BitWidth, VAL % RHS.VAL);
+    assert(RHS.VAL[0] != 0 && "Remainder by zero?");
+    return APInt(BitWidth, VAL[0] % RHS.VAL[0]);
+  }
+#ifdef __SIZEOF_INT128__
+  if (isTwoWords()) {
+    __uint128_t LHSVal = (((__uint128_t)VAL[1]) << 64) | VAL[0];
+    __uint128_t RHSVal = (((__uint128_t)RHS.VAL[1]) << 64) | RHS.VAL[0];
+    __uint128_t Result = LHSVal % RHSVal;
+    uint64_t Lo = Result;
+    uint64_t Hi = Result >> 64;
+    return APInt(BitWidth, {Lo, Hi});
   }
+#endif
 
   // Get some facts about the LHS
   unsigned lhsBits = getActiveBits();
   unsigned lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1);
 
   // Get some facts about the RHS
   unsigned rhsBits = RHS.getActiveBits();
   unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);

 }
 
 void APInt::udivrem(const APInt &LHS, const APInt &RHS,
                     APInt &Quotient, APInt &Remainder) {
   assert(LHS.BitWidth == RHS.BitWidth && "Bit widths must be the same");
 
   // First, deal with the easy case
   if (LHS.isSingleWord()) {
-    assert(RHS.VAL != 0 && "Divide by zero?");
-    uint64_t QuotVal = LHS.VAL / RHS.VAL;
-    uint64_t RemVal = LHS.VAL % RHS.VAL;
+    assert(RHS.VAL[0] != 0 && "Divide by zero?");
+    uint64_t QuotVal = LHS.VAL[0] / RHS.VAL[0];
+    uint64_t RemVal = LHS.VAL[0] % RHS.VAL[0];
     Quotient = APInt(LHS.BitWidth, QuotVal);
     Remainder = APInt(LHS.BitWidth, RemVal);
     return;
   }
+#ifdef __SIZEOF_INT128__
+  if (LHS.isTwoWords()) {
+    __uint128_t LHSVal = (((__uint128_t)LHS.VAL[1]) << 64) | LHS.VAL[0];
+    __uint128_t RHSVal = (((__uint128_t)RHS.VAL[1]) << 64) | RHS.VAL[0];
+    __uint128_t QuotVal = LHSVal / RHSVal;
+    __uint128_t RemVal = LHSVal % RHSVal;
+    Quotient.VAL[0] = QuotVal;
+    Quotient.VAL[1] = QuotVal >> 64;
+    Quotient.clearUnusedBits();
+    Remainder.VAL[0] = RemVal;
+    Remainder.VAL[1] = RemVal >> 64;
+    Remainder.clearUnusedBits();
+    return;
+  }
+#endif
 
   // Get some size facts about the dividend and divisor
   unsigned lhsBits  = LHS.getActiveBits();
   unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
   unsigned rhsBits  = RHS.getActiveBits();
   unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
 
   // Check the degenerate cases
#endif
   if (LHS == RHS) {
     Quotient  = 1;              // X / X ===> 1
     Remainder = 0;              // X % X ===> 0;
     return;
   }
 
   if (lhsWords == 1 && rhsWords == 1) {
     // There is only one word to consider so use the native versions.
-    uint64_t lhsValue = LHS.isSingleWord() ? LHS.VAL : LHS.pVal[0];
-    uint64_t rhsValue = RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
+    uint64_t lhsValue = LHS.getRawData()[0];
+    uint64_t rhsValue = RHS.getRawData()[0];
     Quotient = APInt(LHS.getBitWidth(), lhsValue / rhsValue);
     Remainder = APInt(LHS.getBitWidth(), lhsValue % rhsValue);
     return;
   }
 
   // Okay, lets do it the long way
   divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder);
 }
void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) {
   }
   assert((slen <= numbits || radix != 2) && "Insufficient bit width");
   assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width");
   assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width");
   assert((((slen-1)*64)/22 <= numbits || radix != 10) &&
          "Insufficient bit width");
 
   // Allocate memory
-  if (!isSingleWord())
+  if (!isInline())
     pVal = getClearedMemory(getNumWords());
 
   // Figure out if we can shift instead of multiply
   unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
 
   // Set up an APInt for the digit to add outside the loop so we don't
   // constantly construct/destruct it.
   APInt apdigit(getBitWidth(), 0);
   APInt apradix(getBitWidth(), radix);
 
   // Enter digit traversal loop
   for (StringRef::iterator e = str.end(); p != e; ++p) {
     unsigned digit = getDigit(*p, radix);
     assert(digit < radix && "Invalid character in digit string");
 
     // Shift or multiply the value by the radix
     if (slen > 1) {
       if (shift)
         *this <<= shift;
       else
         *this *= apradix;
     }
 
     // Add in the digit we just interpreted
-    if (apdigit.isSingleWord())
-      apdigit.VAL = digit;
-    else
-      apdigit.pVal[0] = digit;
+    apdigit.getMutableRawData()[0] = digit;
     *this += apdigit;
   }
   // If its negative, put it in two's complement form
   if (isNeg) {
     --(*this);
     this->flipAllBits();
   }
 }

unittests/ADT/APIntTest.cpp

TEST(APIntTest, i1) {
   EXPECT_EQ(zero, one - one);
 
   // Shifts.
   EXPECT_EQ(zero, one << one);
   EXPECT_EQ(one, one << zero);
   EXPECT_EQ(zero, one.shl(1));
   EXPECT_EQ(one, one.shl(0));
   EXPECT_EQ(zero, one.lshr(1));
-  EXPECT_EQ(zero, one.ashr(1));
+  EXPECT_EQ(neg_one, one.ashr(1));
 
   // Rotates.
   EXPECT_EQ(one, one.rotl(0));
   EXPECT_EQ(one, one.rotl(1));
   EXPECT_EQ(one, one.rotr(0));
   EXPECT_EQ(one, one.rotr(1));
 
   // Multiplies.

unittests/ADT/APSIntTest.cpp

TEST(APSIntTest, MoveTest) {
   const uint64_t *Bits = Wide.getRawData();
   APSInt D(std::move(Wide));
   EXPECT_TRUE(D.isUnsigned());
   EXPECT_EQ(Bits, D.getRawData()); // Verify that "Wide" was really moved.
 
   A = APSInt(64, true);
   EXPECT_TRUE(A.isUnsigned());
 
-  Wide = APInt(128, 1);
+  Wide = APInt(129, 1);
   Bits = Wide.getRawData();
   A = std::move(Wide);
   EXPECT_TRUE(A.isUnsigned());
   EXPECT_EQ(Bits, A.getRawData()); // Verify that "Wide" was really moved.
 }
 
 TEST(APSIntTest, get) {
   EXPECT_TRUE(APSInt::get(7).isSigned());