Add APInt support for converting to/from hexatridecimal strings
[oota-llvm.git] / include / llvm / ADT / APInt.h
index 388316d20994c82692148e44f6b3fcdaab8b8e82..707e0dbb6b91e5fd5ef821620d652c926e64d571 100644 (file)
@@ -15,7 +15,7 @@
 #ifndef LLVM_APINT_H
 #define LLVM_APINT_H
 
-#include "llvm/Support/DataTypes.h"
+#include "llvm/ADT/ArrayRef.h"
 #include "llvm/Support/MathExtras.h"
 #include <cassert>
 #include <climits>
@@ -27,12 +27,13 @@ namespace llvm {
   class Deserializer;
   class FoldingSetNodeID;
   class raw_ostream;
+  class StringRef;
 
   template<typename T>
   class SmallVectorImpl;
 
-  /* An unsigned host type used as a single part of a multi-part
-     bignum.  */
+  // 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;
@@ -150,10 +151,19 @@ class APInt {
     return isSingleWord() ? VAL : pVal[whichWord(bitPosition)];
   }
 
+  /// 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.
+  ///
   /// This is used by the constructors that take string arguments.
+  ///
+  /// StringRef::getAsInteger is superficially similar but (1) does
+  /// not assume that the string is well-formed and (2) grows the
+  /// result to hold the input.
+  ///
+  /// @param radix 2, 8, 10, 16, or 36
   /// @brief Convert a char array into an APInt
-  void fromString(unsigned numBits, const char *strStart, unsigned slen,
-                  uint8_t radix);
+  void fromString(unsigned numBits, StringRef str, uint8_t radix);
 
   /// This is used by the toString method to divide by the radix. It simply
   /// provides a more convenient form of divide for internal use since KnuthDiv
@@ -167,6 +177,9 @@ class APInt {
   /// out-of-line slow case for inline constructor
   void initSlowCase(unsigned numBits, uint64_t val, bool isSigned);
 
+  /// shared code between two array constructors
+  void initFromArray(ArrayRef<uint64_t> array);
+
   /// out-of-line slow case for inline copy constructor
   void initSlowCase(const APInt& that);
 
@@ -221,25 +234,32 @@ public:
     clearUnusedBits();
   }
 
-  /// Note that numWords can be smaller or larger than the corresponding bit
-  /// width but any extraneous bits will be dropped.
+  /// Note that bigVal.size() can be smaller or larger than the corresponding
+  /// bit width but any extraneous bits will be dropped.
   /// @param numBits the bit width of the constructed APInt
-  /// @param numWords the number of words in bigVal
   /// @param bigVal a sequence of words to form the initial value of the APInt
   /// @brief Construct an APInt of numBits width, initialized as bigVal[].
+  APInt(unsigned numBits, ArrayRef<uint64_t> bigVal);
+  /// Equivalent to APInt(numBits, ArrayRef<uint64_t>(bigVal, numWords)), but
+  /// deprecated because this constructor is prone to ambiguity with the
+  /// APInt(unsigned, uint64_t, bool) constructor.
+  ///
+  /// If this overload is ever deleted, care should be taken to prevent calls
+  /// from being incorrectly captured by the APInt(unsigned, uint64_t, bool)
+  /// constructor.
   APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[]);
 
-  /// This constructor interprets the slen characters starting at StrStart as
-  /// a string in the given radix. The interpretation stops when the first
-  /// character that is not suitable for the radix is encountered. Acceptable
-  /// radix values are 2, 8, 10 and 16. It is an error for the value implied by
-  /// the string to require more bits than numBits.
+  /// This constructor interprets the string \arg str in the given radix. The
+  /// interpretation stops when the first character that is not suitable for the
+  /// radix is encountered, or the end of the string. Acceptable radix values
+  /// are 2, 8, 10, 16, and 36. It is an error for the value implied by the 
+  /// string to require more bits than numBits.
+  ///
   /// @param numBits the bit width of the constructed APInt
-  /// @param strStart the start of the string to be interpreted
-  /// @param slen the maximum number of characters to interpret
-  /// @param radix the radix to use for the conversion
+  /// @param str the string to be interpreted
+  /// @param radix the radix to use for the conversion 
   /// @brief Construct an APInt from a string representation.
-  APInt(unsigned numBits, const char strStart[], unsigned slen, uint8_t radix);
+  APInt(unsigned numBits, StringRef str, uint8_t radix);
 
   /// Simply makes *this a copy of that.
   /// @brief Copy Constructor.
@@ -266,12 +286,6 @@ public:
   ///  objects, into FoldingSets.
   void Profile(FoldingSetNodeID& id) const;
 
-  /// @brief Used by the Bitcode serializer to emit APInts to Bitcode.
-  void Emit(Serializer& S) const;
-
-  /// @brief Used by the Bitcode deserializer to deserialize APInts.
-  void Read(Deserializer& D);
-
   /// @}
   /// @name Value Tests
   /// @{
@@ -293,7 +307,7 @@ public:
   /// @returns true if this APInt is positive.
   /// @brief Determine if this APInt Value is positive.
   bool isStrictlyPositive() const {
-    return isNonNegative() && (*this) != 0;
+    return isNonNegative() && !!*this;
   }
 
   /// This checks to see if the value has all bits of the APInt are set or not.
@@ -321,15 +335,14 @@ public:
   /// value for the APInt's bit width.
   /// @brief Determine if this is the smallest unsigned value.
   bool isMinValue() const {
-    return countPopulation() == 0;
+    return !*this;
   }
 
   /// This checks to see if the value of this APInt is the minimum signed
   /// value for the APInt's bit width.
   /// @brief Determine if this is the smallest signed value.
   bool isMinSignedValue() const {
-    return BitWidth == 1 ? VAL == 1 :
-                           isNegative() && countPopulation() == 1;
+    return BitWidth == 1 ? VAL == 1 : isNegative() && isPowerOf2();
   }
 
   /// @brief Check if this APInt has an N-bits unsigned integer value.
@@ -339,10 +352,9 @@ public:
       return true;
 
     if (isSingleWord())
-      return VAL == (VAL & (~0ULL >> (64 - N)));
-    APInt Tmp(N, getNumWords(), pVal);
-    Tmp.zext(getBitWidth());
-    return Tmp == (*this);
+      return isUIntN(N, VAL);
+    return APInt(N, makeArrayRef(pVal, getNumWords())).zext(getBitWidth())
+      == (*this);
   }
 
   /// @brief Check if this APInt has an N-bits signed integer value.
@@ -352,7 +364,11 @@ public:
   }
 
   /// @returns true if the argument APInt value is a power of two > 0.
-  bool isPowerOf2() const;
+  bool isPowerOf2() const {
+    if (isSingleWord())
+      return isPowerOf2_64(VAL);
+    return countPopulationSlowCase() == 1;
+  }
 
   /// isSignBit - Return true if this is the value returned by getSignBit.
   bool isSignBit() const { return isMinSignedValue(); }
@@ -360,7 +376,7 @@ public:
   /// This converts the APInt to a boolean value as a test against zero.
   /// @brief Boolean conversion function.
   bool getBoolValue() const {
-    return *this != 0;
+    return !!*this;
   }
 
   /// getLimitedValue - If this value is smaller than the specified limit,
@@ -376,12 +392,14 @@ public:
   /// @{
   /// @brief Gets maximum unsigned value of APInt for specific bit width.
   static APInt getMaxValue(unsigned numBits) {
-    return APInt(numBits, 0).set();
+    return getAllOnesValue(numBits);
   }
 
   /// @brief Gets maximum signed value of APInt for a specific bit width.
   static APInt getSignedMaxValue(unsigned numBits) {
-    return APInt(numBits, 0).set().clear(numBits - 1);
+    APInt API = getAllOnesValue(numBits);
+    API.clearBit(numBits - 1);
+    return API;
   }
 
   /// @brief Gets minimum unsigned value of APInt for a specific bit width.
@@ -391,7 +409,9 @@ public:
 
   /// @brief Gets minimum signed value of APInt for a specific bit width.
   static APInt getSignedMinValue(unsigned numBits) {
-    return APInt(numBits, 0).set(numBits - 1);
+    APInt API(numBits, 0);
+    API.setBit(numBits - 1);
+    return API;
   }
 
   /// getSignBit - This is just a wrapper function of getSignedMinValue(), and
@@ -404,7 +424,7 @@ public:
   /// @returns the all-ones value for an APInt of the specified bit-width.
   /// @brief Get the all-ones value.
   static APInt getAllOnesValue(unsigned numBits) {
-    return APInt(numBits, 0).set();
+    return APInt(numBits, -1ULL, true);
   }
 
   /// @returns the '0' value for an APInt of the specified bit-width.
@@ -423,6 +443,13 @@ public:
   /// @returns the low "numBits" bits of this APInt.
   APInt getLoBits(unsigned numBits) const;
 
+  /// getOneBitSet - Return an APInt with exactly one bit set in the result.
+  static APInt getOneBitSet(unsigned numBits, unsigned BitNo) {
+    APInt Res(numBits, 0);
+    Res.setBit(BitNo);
+    return Res;
+  }
+  
   /// Constructs an APInt value that has a contiguous range of bits set. The
   /// bits from loBit (inclusive) to hiBit (exclusive) will be set. All other
   /// bits will be zero. For example, with parameters(32, 0, 16) you would get
@@ -455,7 +482,7 @@ public:
     // For small values, return quickly
     if (numBits <= APINT_BITS_PER_WORD)
       return APInt(numBits, ~0ULL << shiftAmt);
-    return (~APInt(numBits, 0)).shl(shiftAmt);
+    return getAllOnesValue(numBits).shl(shiftAmt);
   }
 
   /// Constructs an APInt value that has the bottom loBitsSet bits set.
@@ -472,7 +499,7 @@ public:
     // For small values, return quickly.
     if (numBits < APINT_BITS_PER_WORD)
       return APInt(numBits, (1ULL << loBitsSet) - 1);
-    return (~APInt(numBits, 0)).lshr(numBits - loBitsSet);
+    return getAllOnesValue(numBits).lshr(numBits - loBitsSet);
   }
 
   /// The hash value is computed as the sum of the words and the bit width.
@@ -521,7 +548,7 @@ public:
   /// @brief Unary bitwise complement operator.
   APInt operator~() const {
     APInt Result(*this);
-    Result.flip();
+    Result.flipAllBits();
     return Result;
   }
 
@@ -572,6 +599,21 @@ public:
   /// @brief Bitwise OR assignment operator.
   APInt& operator|=(const APInt& RHS);
 
+  /// 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.
+  /// 
+  /// @brief Bitwise OR assignment operator.
+  APInt& operator|=(uint64_t RHS) {
+    if (isSingleWord()) {
+      VAL |= RHS;
+      clearUnusedBits();
+    } else {
+      pVal[0] |= RHS;
+    }
+    return *this;
+  }
+
   /// Performs a bitwise XOR operation on this APInt and RHS. The result is
   /// assigned to *this.
   /// @returns *this after XORing with RHS.
@@ -717,11 +759,11 @@ public:
   /// RHS are treated as unsigned quantities for purposes of this division.
   /// @returns a new APInt value containing the division result
   /// @brief Unsigned division operation.
-  APInt udiv(const APIntRHS) const;
+  APInt udiv(const APInt &RHS) const;
 
   /// Signed divide this APInt by APInt RHS.
   /// @brief Signed division function for APInt.
-  APInt sdiv(const APIntRHS) const {
+  APInt sdiv(const APInt &RHS) const {
     if (isNegative())
       if (RHS.isNegative())
         return (-(*this)).udiv(-RHS);
@@ -739,11 +781,11 @@ public:
   /// which is *this.
   /// @returns a new APInt value containing the remainder result
   /// @brief Unsigned remainder operation.
-  APInt urem(const APIntRHS) const;
+  APInt urem(const APInt &RHS) const;
 
   /// Signed remainder operation on APInt.
   /// @brief Function for signed remainder operation.
-  APInt srem(const APIntRHS) const {
+  APInt srem(const APInt &RHS) const {
     if (isNegative())
       if (RHS.isNegative())
         return -((-(*this)).urem(-RHS));
@@ -764,8 +806,7 @@ public:
                       APInt &Quotient, APInt &Remainder);
 
   static void sdivrem(const APInt &LHS, const APInt &RHS,
-                      APInt &Quotient, APInt &Remainder)
-  {
+                      APInt &Quotient, APInt &Remainder) {
     if (LHS.isNegative()) {
       if (RHS.isNegative())
         APInt::udivrem(-LHS, -RHS, Quotient, Remainder);
@@ -780,6 +821,17 @@ public:
       APInt::udivrem(LHS, RHS, Quotient, Remainder);
     }
   }
+  
+  
+  // Operations that return overflow indicators.
+  APInt sadd_ov(const APInt &RHS, bool &Overflow) const;
+  APInt uadd_ov(const APInt &RHS, bool &Overflow) const;
+  APInt ssub_ov(const APInt &RHS, bool &Overflow) const;
+  APInt usub_ov(const APInt &RHS, bool &Overflow) const;
+  APInt sdiv_ov(const APInt &RHS, bool &Overflow) const;
+  APInt smul_ov(const APInt &RHS, bool &Overflow) const;
+  APInt umul_ov(const APInt &RHS, bool &Overflow) const;
+  APInt sshl_ov(unsigned Amt, bool &Overflow) const;
 
   /// @returns the bit value at bitPosition
   /// @brief Array-indexing support.
@@ -844,7 +896,15 @@ public:
   /// the validity of the less-than relationship.
   /// @returns true if *this < RHS when both are considered unsigned.
   /// @brief Unsigned less than comparison
-  bool ult(const APInt& RHS) const;
+  bool ult(const APInt &RHS) const;
+
+  /// Regards both *this as an unsigned quantity and compares it with RHS for
+  /// the validity of the less-than relationship.
+  /// @returns true if *this < RHS when considered unsigned.
+  /// @brief Unsigned less than comparison
+  bool ult(uint64_t RHS) const {
+    return ult(APInt(getBitWidth(), RHS));
+  }
 
   /// Regards both *this and RHS as signed quantities and compares them for
   /// validity of the less-than relationship.
@@ -852,6 +912,14 @@ public:
   /// @brief Signed less than comparison
   bool slt(const APInt& RHS) const;
 
+  /// Regards both *this as a signed quantity and compares it with RHS for
+  /// the validity of the less-than relationship.
+  /// @returns true if *this < RHS when considered signed.
+  /// @brief Signed less than comparison
+  bool slt(uint64_t RHS) const {
+    return slt(APInt(getBitWidth(), RHS));
+  }
+
   /// Regards both *this and RHS as unsigned quantities and compares them for
   /// validity of the less-or-equal relationship.
   /// @returns true if *this <= RHS when both are considered unsigned.
@@ -860,6 +928,14 @@ public:
     return ult(RHS) || eq(RHS);
   }
 
+  /// Regards both *this as an unsigned quantity and compares it with RHS for
+  /// the validity of the less-or-equal relationship.
+  /// @returns true if *this <= RHS when considered unsigned.
+  /// @brief Unsigned less or equal comparison
+  bool ule(uint64_t RHS) const {
+    return ule(APInt(getBitWidth(), RHS));
+  }
+
   /// Regards both *this and RHS as signed quantities and compares them for
   /// validity of the less-or-equal relationship.
   /// @returns true if *this <= RHS when both are considered signed.
@@ -868,6 +944,14 @@ public:
     return slt(RHS) || eq(RHS);
   }
 
+  /// Regards both *this as a signed quantity and compares it with RHS for
+  /// the validity of the less-or-equal relationship.
+  /// @returns true if *this <= RHS when considered signed.
+  /// @brief Signed less or equal comparison
+  bool sle(uint64_t RHS) const {
+    return sle(APInt(getBitWidth(), RHS));
+  }
+
   /// Regards both *this and RHS as unsigned quantities and compares them for
   /// the validity of the greater-than relationship.
   /// @returns true if *this > RHS when both are considered unsigned.
@@ -876,6 +960,14 @@ public:
     return !ult(RHS) && !eq(RHS);
   }
 
+  /// Regards both *this as an unsigned quantity and compares it with RHS for
+  /// the validity of the greater-than relationship.
+  /// @returns true if *this > RHS when considered unsigned.
+  /// @brief Unsigned greater than comparison
+  bool ugt(uint64_t RHS) const {
+    return ugt(APInt(getBitWidth(), RHS));
+  }
+
   /// Regards both *this and RHS as signed quantities and compares them for
   /// the validity of the greater-than relationship.
   /// @returns true if *this > RHS when both are considered signed.
@@ -884,6 +976,14 @@ public:
     return !slt(RHS) && !eq(RHS);
   }
 
+  /// Regards both *this as a signed quantity and compares it with RHS for
+  /// the validity of the greater-than relationship.
+  /// @returns true if *this > RHS when considered signed.
+  /// @brief Signed greater than comparison
+  bool sgt(uint64_t RHS) const {
+    return sgt(APInt(getBitWidth(), RHS));
+  }
+
   /// Regards both *this and RHS as unsigned quantities and compares them for
   /// validity of the greater-or-equal relationship.
   /// @returns true if *this >= RHS when both are considered unsigned.
@@ -892,6 +992,14 @@ public:
     return !ult(RHS);
   }
 
+  /// Regards both *this as an unsigned quantity and compares it with RHS for
+  /// the validity of the greater-or-equal relationship.
+  /// @returns true if *this >= RHS when considered unsigned.
+  /// @brief Unsigned greater or equal comparison
+  bool uge(uint64_t RHS) const {
+    return uge(APInt(getBitWidth(), RHS));
+  }
+
   /// Regards both *this and RHS as signed quantities and compares them for
   /// validity of the greater-or-equal relationship.
   /// @returns true if *this >= RHS when both are considered signed.
@@ -900,6 +1008,17 @@ public:
     return !slt(RHS);
   }
 
+  /// Regards both *this as a signed quantity and compares it with RHS for
+  /// the validity of the greater-or-equal relationship.
+  /// @returns true if *this >= RHS when considered signed.
+  /// @brief Signed greater or equal comparison
+  bool sge(uint64_t RHS) const {
+    return sge(APInt(getBitWidth(), RHS));
+  }
+
+  
+  
+  
   /// This operation tests if there are any pairs of corresponding bits
   /// between this APInt and RHS that are both set.
   bool intersects(const APInt &RHS) const {
@@ -912,80 +1031,78 @@ public:
   /// Truncate the APInt to a specified width. It is an error to specify a width
   /// that is greater than or equal to the current width.
   /// @brief Truncate to new width.
-  APInt &trunc(unsigned width);
+  APInt trunc(unsigned width) const;
 
   /// This operation sign extends the APInt to a new width. If the high order
   /// bit is set, the fill on the left will be done with 1 bits, otherwise zero.
   /// It is an error to specify a width that is less than or equal to the
   /// current width.
   /// @brief Sign extend to a new width.
-  APInt &sext(unsigned width);
+  APInt sext(unsigned width) const;
 
   /// This operation zero extends the APInt to a new width. The high order bits
   /// are filled with 0 bits.  It is an error to specify a width that is less
   /// than or equal to the current width.
   /// @brief Zero extend to a new width.
-  APInt &zext(unsigned width);
+  APInt zext(unsigned width) const;
 
   /// Make this APInt have the bit width given by \p width. The value is sign
   /// extended, truncated, or left alone to make it that width.
   /// @brief Sign extend or truncate to width
-  APInt &sextOrTrunc(unsigned width);
+  APInt sextOrTrunc(unsigned width) const;
 
   /// Make this APInt have the bit width given by \p width. The value is zero
   /// extended, truncated, or left alone to make it that width.
   /// @brief Zero extend or truncate to width
-  APInt &zextOrTrunc(unsigned width);
+  APInt zextOrTrunc(unsigned width) const;
 
   /// @}
   /// @name Bit Manipulation Operators
   /// @{
   /// @brief Set every bit to 1.
-  APInt& set() {
-    if (isSingleWord()) {
+  void setAllBits() {
+    if (isSingleWord())
       VAL = -1ULL;
-      return clearUnusedBits();
+    else {
+      // Set all the bits in all the words.
+      for (unsigned i = 0; i < getNumWords(); ++i)
+       pVal[i] = -1ULL;
     }
-
-    // Set all the bits in all the words.
-    for (unsigned i = 0; i < getNumWords(); ++i)
-      pVal[i] = -1ULL;
     // Clear the unused ones
-    return clearUnusedBits();
+    clearUnusedBits();
   }
 
   /// Set the given bit to 1 whose position is given as "bitPosition".
   /// @brief Set a given bit to 1.
-  APInt& set(unsigned bitPosition);
+  void setBit(unsigned bitPosition);
 
   /// @brief Set every bit to 0.
-  APInt& clear() {
+  void clearAllBits() {
     if (isSingleWord())
       VAL = 0;
     else
       memset(pVal, 0, getNumWords() * APINT_WORD_SIZE);
-    return *this;
   }
 
   /// Set the given bit to 0 whose position is given as "bitPosition".
   /// @brief Set a given bit to 0.
-  APInt& clear(unsigned bitPosition);
+  void clearBit(unsigned bitPosition);
 
   /// @brief Toggle every bit to its opposite value.
-  APInt& flip() {
-    if (isSingleWord()) {
+  void flipAllBits() {
+    if (isSingleWord())
       VAL ^= -1ULL;
-      return clearUnusedBits();
+    else {
+      for (unsigned i = 0; i < getNumWords(); ++i)
+        pVal[i] ^= -1ULL;
     }
-    for (unsigned i = 0; i < getNumWords(); ++i)
-      pVal[i] ^= -1ULL;
-    return clearUnusedBits();
+    clearUnusedBits();
   }
 
   /// Toggle a given bit to its opposite value whose position is given
   /// as "bitPosition".
   /// @brief Toggles a given bit to its opposite value.
-  APInt& flip(unsigned bitPosition);
+  void flipBit(unsigned bitPosition);
 
   /// @}
   /// @name Value Characterization Functions
@@ -1000,6 +1117,14 @@ public:
   /// @returns the number of words to hold the integer value of this APInt.
   /// @brief Get the number of words.
   unsigned getNumWords() const {
+    return getNumWords(BitWidth);
+  }
+
+  /// Here one word's bitwidth equals to that of uint64_t.
+  /// @returns the number of words to hold the integer value with a
+  /// given bit width.
+  /// @brief Get the number of words.
+  static unsigned getNumWords(unsigned BitWidth) {
     return (BitWidth + APINT_BITS_PER_WORD - 1) / APINT_BITS_PER_WORD;
   }
 
@@ -1055,9 +1180,9 @@ public:
   }
 
   /// This method determines how many bits are required to hold the APInt
-  /// equivalent of the string given by \p str of length \p slen.
+  /// equivalent of the string given by \arg str.
   /// @brief Get bits required for string value.
-  static unsigned getBitsNeeded(const char* str, unsigned slen, uint8_t radix);
+  static unsigned getBitsNeeded(StringRef str, uint8_t radix);
 
   /// countLeadingZeros - This function is an APInt version of the
   /// countLeadingZeros_{32,64} functions in MathExtras.h. It counts the number
@@ -1081,6 +1206,12 @@ public:
   /// @brief Count the number of leading one bits.
   unsigned countLeadingOnes() const;
 
+  /// Computes the number of leading bits of this APInt that are equal to its
+  /// sign bit.
+  unsigned getNumSignBits() const {
+    return isNegative() ? countLeadingOnes() : countLeadingZeros();
+  }
+
   /// countTrailingZeros - This function is an APInt version of the
   /// countTrailingZeros_{32,64} functions in MathExtras.h. It counts
   /// the number of zeros from the least significant bit to the first set bit.
@@ -1122,18 +1253,19 @@ public:
 
   /// toString - Converts an APInt to a string and append it to Str.  Str is
   /// commonly a SmallString.
-  void toString(SmallVectorImpl<char> &Str, unsigned Radix, bool Signed) const;
+  void toString(SmallVectorImpl<char> &Str, unsigned Radix, bool Signed,
+                bool formatAsCLiteral = false) const;
 
   /// Considers the APInt to be unsigned and converts it into a string in the
-  /// radix given. The radix can be 2, 8, 10 or 16.
+  /// radix given. The radix can be 2, 8, 10 16, or 36.
   void toStringUnsigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const {
-    toString(Str, Radix, false);
+    toString(Str, Radix, false, false);
   }
 
   /// Considers the APInt to be signed and converts it into a string in the
-  /// radix given. The radix can be 2, 8, 10 or 16.
+  /// radix given. The radix can be 2, 8, 10, 16, or 36.
   void toStringSigned(SmallVectorImpl<char> &Str, unsigned Radix = 10) const {
-    toString(Str, Radix, true);
+    toString(Str, Radix, true, false);
   }
 
   /// toString - This returns the APInt as a std::string.  Note that this is an
@@ -1185,37 +1317,27 @@ public:
   }
 
   /// The conversion does not do a translation from double to integer, it just
-  /// re-interprets the bits of the double. Note that it is valid to do this on
-  /// any bit width but bits from V may get truncated.
+  /// re-interprets the bits of the double.
   /// @brief Converts a double to APInt bits.
-  APInt& doubleToBits(double V) {
+  static APInt doubleToBits(double V) {
     union {
       uint64_t I;
       double D;
     } T;
     T.D = V;
-    if (isSingleWord())
-      VAL = T.I;
-    else
-      pVal[0] = T.I;
-    return clearUnusedBits();
+    return APInt(sizeof T * CHAR_BIT, T.I);
   }
 
   /// The conversion does not do a translation from float to integer, it just
-  /// re-interprets the bits of the float. Note that it is valid to do this on
-  /// any bit width but bits from V may get truncated.
+  /// re-interprets the bits of the float.
   /// @brief Converts a float to APInt bits.
-  APInt& floatToBits(float V) {
+  static APInt floatToBits(float V) {
     union {
       unsigned I;
       float F;
     } T;
     T.F = V;
-    if (isSingleWord())
-      VAL = T.I;
-    else
-      pVal[0] = T.I;
-    return clearUnusedBits();
+    return APInt(sizeof T * CHAR_BIT, T.I);
   }
 
   /// @}
@@ -1227,6 +1349,11 @@ public:
     return BitWidth - 1 - countLeadingZeros();
   }
 
+  /// @returns the ceil log base 2 of this APInt.
+  unsigned ceilLogBase2() const {
+    return BitWidth - (*this - 1).countLeadingZeros();
+  }
+
   /// @returns the log base 2 of this APInt if its an exact power of two, -1
   /// otherwise
   int32_t exactLogBase2() const {
@@ -1249,6 +1376,18 @@ public:
   /// @returns the multiplicative inverse for a given modulo.
   APInt multiplicativeInverse(const APInt& modulo) const;
 
+  /// @}
+  /// @name Support for division by constant
+  /// @{
+
+  /// Calculate the magic number for signed division by a constant.
+  struct ms;
+  ms magic() const;
+
+  /// Calculate the magic number for unsigned division by a constant.
+  struct mu;
+  mu magicu(unsigned LeadingZeros = 0) const;
+
   /// @}
   /// @name Building-block Operations for APInt and APFloat
   /// @{
@@ -1284,6 +1423,9 @@ public:
   /// Set the given bit of a bignum.  Zero-based.
   static void tcSetBit(integerPart *, unsigned int bit);
 
+  /// Clear the given bit of a bignum.  Zero-based.
+  static void tcClearBit(integerPart *, unsigned int bit);
+
   /// Returns the bit number of the least or most significant set bit
   /// of a number.  If the input number has no bits set -1U is
   /// returned.
@@ -1380,6 +1522,19 @@ public:
   /// @}
 };
 
+/// Magic data for optimising signed division by a constant.
+struct APInt::ms {
+  APInt m;  ///< magic number
+  unsigned s;  ///< shift amount
+};
+
+/// Magic data for optimising unsigned division by a constant.
+struct APInt::mu {
+  APInt m;     ///< magic number
+  bool a;      ///< add indicator
+  unsigned s;  ///< shift amount
+};
+
 inline bool operator==(uint64_t V1, const APInt& V2) {
   return V2 == V1;
 }