Vendor import of llvm trunk r338150:vendor/llvm/llvm-trunk-r338150

https://llvm.org/svn/llvm-project/llvm/trunk@338150

45 files changed, 1564 insertions, 750 deletions

diff --git a/include/llvm/ADT/APFloat.h b/include/llvm/ADT/APFloat.h
index 6c0b6ae78ae3..5c59af4c04ba 100644
--- a/include/llvm/ADT/APFloat.h
+++ b/include/llvm/ADT/APFloat.h
@@ -1215,7 +1215,7 @@ inline APFloat abs(APFloat X) {
   return X;
 }
 
-/// \brief Returns the negated value of the argument.
+/// Returns the negated value of the argument.
 inline APFloat neg(APFloat X) {
   X.changeSign();
   return X;
diff --git a/include/llvm/ADT/APInt.h b/include/llvm/ADT/APInt.h
index c81363cc16b7..6bf6b22fb010 100644
--- a/include/llvm/ADT/APInt.h
+++ b/include/llvm/ADT/APInt.h
@@ -8,7 +8,7 @@
 //===----------------------------------------------------------------------===//
 ///
 /// \file
-/// \brief This file implements a class to represent arbitrary precision
+/// This file implements a class to represent arbitrary precision
 /// integral constant values and operations on them.
 ///
 //===----------------------------------------------------------------------===//
@@ -40,7 +40,7 @@ inline APInt operator-(APInt);
 //                              APInt Class
 //===----------------------------------------------------------------------===//
 
-/// \brief Class for arbitrary precision integers.
+/// Class for arbitrary precision integers.
 ///
 /// APInt is a functional replacement for common case unsigned integer type like
 /// "unsigned", "unsigned long" or "uint64_t", but also allows non-byte-width
@@ -78,6 +78,12 @@ public:
     APINT_BITS_PER_WORD = APINT_WORD_SIZE * CHAR_BIT
   };
 
+  enum class Rounding {
+    DOWN,
+    TOWARD_ZERO,
+    UP,
+  };
+
   static const WordType WORD_MAX = ~WordType(0);
 
 private:
@@ -94,7 +100,7 @@ private:
 
   friend class APSInt;
 
-  /// \brief Fast internal constructor
+  /// 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.
@@ -102,19 +108,19 @@ private:
     U.pVal = val;
   }
 
-  /// \brief Determine if this APInt just has one word to store value.
+  /// 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 which word a bit is in.
+  /// 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.
+  /// Determine which bit in a word a bit is in.
   ///
   /// \returns the bit position in a word for the specified bit position
   /// in the APInt.
@@ -122,7 +128,7 @@ private:
     return bitPosition % APINT_BITS_PER_WORD;
   }
 
-  /// \brief Get a single bit mask.
+  /// Get a single bit mask.
   ///
   /// \returns a uint64_t with only bit at "whichBit(bitPosition)" set
   /// This method generates and returns a uint64_t (word) mask for a single
@@ -132,7 +138,7 @@ private:
     return 1ULL << whichBit(bitPosition);
   }
 
-  /// \brief Clear unused high order bits
+  /// Clear unused high order bits
   ///
   /// This method is used internally to clear the top "N" bits in the high order
   /// word that are not used by the APInt. This is needed after the most
@@ -151,7 +157,7 @@ private:
     return *this;
   }
 
-  /// \brief Get the word corresponding to a bit position
+  /// 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() ? U.VAL : U.pVal[whichWord(bitPosition)];
@@ -162,7 +168,7 @@ private:
   /// value of any bits upon return. Caller should populate the bits after.
   void reallocate(unsigned NewBitWidth);
 
-  /// \brief Convert a char array into an APInt
+  /// 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
@@ -176,7 +182,7 @@ private:
   /// result to hold the input.
   void fromString(unsigned numBits, StringRef str, uint8_t radix);
 
-  /// \brief An internal division function for dividing APInts.
+  /// An internal division function for dividing APInts.
   ///
   /// 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
@@ -258,7 +264,7 @@ public:
   /// \name Constructors
   /// @{
 
-  /// \brief Create a new APInt of numBits width, initialized as val.
+  /// 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
@@ -279,7 +285,7 @@ public:
     }
   }
 
-  /// \brief Construct an APInt of numBits width, initialized as bigVal[].
+  /// 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.
@@ -297,7 +303,7 @@ public:
   /// constructor.
   APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[]);
 
-  /// \brief Construct an APInt from a string representation.
+  /// Construct an APInt from a string representation.
   ///
   /// This constructor interprets the string \p str in the given radix. The
   /// interpretation stops when the first character that is not suitable for the
@@ -311,7 +317,7 @@ public:
   APInt(unsigned numBits, StringRef str, uint8_t radix);
 
   /// Simply makes *this a copy of that.
-  /// @brief Copy Constructor.
+  /// Copy Constructor.
   APInt(const APInt &that) : BitWidth(that.BitWidth) {
     if (isSingleWord())
       U.VAL = that.U.VAL;
@@ -319,26 +325,26 @@ public:
       initSlowCase(that);
   }
 
-  /// \brief Move Constructor.
+  /// Move Constructor.
   APInt(APInt &&that) : BitWidth(that.BitWidth) {
     memcpy(&U, &that.U, sizeof(U));
     that.BitWidth = 0;
   }
 
-  /// \brief Destructor.
+  /// Destructor.
   ~APInt() {
     if (needsCleanup())
       delete[] U.pVal;
   }
 
-  /// \brief Default constructor that creates an uninteresting APInt
+  /// 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) { U.VAL = 0; }
 
-  /// \brief Returns whether this instance allocated memory.
+  /// Returns whether this instance allocated memory.
   bool needsCleanup() const { return !isSingleWord(); }
 
   /// Used to insert APInt objects, or objects that contain APInt objects, into
@@ -349,33 +355,33 @@ public:
   /// \name Value Tests
   /// @{
 
-  /// \brief Determine sign of this APInt.
+  /// Determine sign of this APInt.
   ///
   /// This tests the high bit of this APInt to determine if it is set.
   ///
   /// \returns true if this APInt is negative, false otherwise
   bool isNegative() const { return (*this)[BitWidth - 1]; }
 
-  /// \brief Determine if this APInt Value is non-negative (>= 0)
+  /// Determine if this APInt Value is non-negative (>= 0)
   ///
   /// This tests the high bit of the APInt to determine if it is unset.
   bool isNonNegative() const { return !isNegative(); }
 
-  /// \brief Determine if sign bit of this APInt is set.
+  /// Determine if sign bit of this APInt is set.
   ///
   /// This tests the high bit of this APInt to determine if it is set.
   ///
   /// \returns true if this APInt has its sign bit set, false otherwise.
   bool isSignBitSet() const { return (*this)[BitWidth-1]; }
 
-  /// \brief Determine if sign bit of this APInt is clear.
+  /// Determine if sign bit of this APInt is clear.
   ///
   /// This tests the high bit of this APInt to determine if it is clear.
   ///
   /// \returns true if this APInt has its sign bit clear, false otherwise.
   bool isSignBitClear() const { return !isSignBitSet(); }
 
-  /// \brief Determine if this APInt Value is positive.
+  /// Determine if this APInt Value is positive.
   ///
   /// This tests if the value of this APInt is positive (> 0). Note
   /// that 0 is not a positive value.
@@ -383,7 +389,7 @@ public:
   /// \returns true if this APInt is positive.
   bool isStrictlyPositive() const { return isNonNegative() && !isNullValue(); }
 
-  /// \brief Determine if all bits are set
+  /// 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 {
@@ -392,13 +398,13 @@ public:
     return countTrailingOnesSlowCase() == BitWidth;
   }
 
-  /// \brief Determine if all bits are clear
+  /// Determine if all bits are clear
   ///
   /// This checks to see if the value has all bits of the APInt are clear or
   /// not.
   bool isNullValue() const { return !*this; }
 
-  /// \brief Determine if this is a value of 1.
+  /// Determine if this is a value of 1.
   ///
   /// This checks to see if the value of this APInt is one.
   bool isOneValue() const {
@@ -407,13 +413,13 @@ public:
     return countLeadingZerosSlowCase() == BitWidth - 1;
   }
 
-  /// \brief Determine if this is the largest unsigned value.
+  /// 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(); }
 
-  /// \brief Determine if this is the largest signed value.
+  /// Determine if this is the largest signed value.
   ///
   /// This checks to see if the value of this APInt is the maximum signed
   /// value for the APInt's bit width.
@@ -423,13 +429,13 @@ public:
     return !isNegative() && countTrailingOnesSlowCase() == BitWidth - 1;
   }
 
-  /// \brief Determine if this is the smallest unsigned value.
+  /// Determine if this is the smallest unsigned value.
   ///
   /// This checks to see if the value of this APInt is the minimum unsigned
   /// value for the APInt's bit width.
   bool isMinValue() const { return isNullValue(); }
 
-  /// \brief Determine if this is the smallest signed value.
+  /// Determine if this is the smallest signed value.
   ///
   /// This checks to see if the value of this APInt is the minimum signed
   /// value for the APInt's bit width.
@@ -439,19 +445,19 @@ public:
     return isNegative() && countTrailingZerosSlowCase() == BitWidth - 1;
   }
 
-  /// \brief Check if this APInt has an N-bits unsigned integer value.
+  /// Check if this APInt has an N-bits unsigned integer value.
   bool isIntN(unsigned N) const {
     assert(N && "N == 0 ???");
     return getActiveBits() <= N;
   }
 
-  /// \brief Check if this APInt has an N-bits signed integer value.
+  /// Check if this APInt has an N-bits signed integer value.
   bool isSignedIntN(unsigned N) const {
     assert(N && "N == 0 ???");
     return getMinSignedBits() <= N;
   }
 
-  /// \brief Check if this APInt's value is a power of two greater than zero.
+  /// 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 {
@@ -460,12 +466,12 @@ public:
     return countPopulationSlowCase() == 1;
   }
 
-  /// \brief Check if the APInt's value is returned by getSignMask.
+  /// Check if the APInt's value is returned by getSignMask.
   ///
   /// \returns true if this is the value returned by getSignMask.
   bool isSignMask() const { return isMinSignedValue(); }
 
-  /// \brief Convert APInt to a boolean value.
+  /// Convert APInt to a boolean value.
   ///
   /// This converts the APInt to a boolean value as a test against zero.
   bool getBoolValue() const { return !!*this; }
@@ -476,7 +482,7 @@ public:
     return ugt(Limit) ? Limit : getZExtValue();
   }
 
-  /// \brief Check if the APInt consists of a repeated bit pattern.
+  /// Check if the APInt consists of a repeated bit pattern.
   ///
   /// e.g. 0x01010101 satisfies isSplat(8).
   /// \param SplatSizeInBits The size of the pattern in bits. Must divide bit
@@ -505,7 +511,7 @@ public:
     return (Ones > 0) && ((Ones + countLeadingZerosSlowCase()) == BitWidth);
   }
 
-  /// \brief Return true if this APInt value contains a sequence of ones with
+  /// Return true if this APInt value contains a sequence of ones with
   /// the remainder zero.
   bool isShiftedMask() const {
     if (isSingleWord())
@@ -519,29 +525,29 @@ public:
   /// \name Value Generators
   /// @{
 
-  /// \brief Gets maximum unsigned value of APInt for specific bit width.
+  /// Gets maximum unsigned value of APInt for specific bit width.
   static APInt getMaxValue(unsigned numBits) {
     return getAllOnesValue(numBits);
   }
 
-  /// \brief Gets maximum signed value of APInt for a specific bit width.
+  /// Gets maximum signed value of APInt for a specific bit width.
   static APInt getSignedMaxValue(unsigned numBits) {
     APInt API = getAllOnesValue(numBits);
     API.clearBit(numBits - 1);
     return API;
   }
 
-  /// \brief Gets minimum unsigned value of APInt for a specific bit width.
+  /// Gets minimum unsigned value of APInt for a specific bit width.
   static APInt getMinValue(unsigned numBits) { return APInt(numBits, 0); }
 
-  /// \brief Gets minimum signed value of APInt for a specific bit width.
+  /// Gets minimum signed value of APInt for a specific bit width.
   static APInt getSignedMinValue(unsigned numBits) {
     APInt API(numBits, 0);
     API.setBit(numBits - 1);
     return API;
   }
 
-  /// \brief Get the SignMask for a specific bit width.
+  /// Get the SignMask for a specific bit width.
   ///
   /// This is just a wrapper function of getSignedMinValue(), and it helps code
   /// readability when we want to get a SignMask.
@@ -549,19 +555,19 @@ public:
     return getSignedMinValue(BitWidth);
   }
 
-  /// \brief Get the all-ones value.
+  /// Get the all-ones value.
   ///
   /// \returns the all-ones value for an APInt of the specified bit-width.
   static APInt getAllOnesValue(unsigned numBits) {
     return APInt(numBits, WORD_MAX, true);
   }
 
-  /// \brief Get the '0' value.
+  /// Get the '0' value.
   ///
   /// \returns the '0' value for an APInt of the specified bit-width.
   static APInt getNullValue(unsigned numBits) { return APInt(numBits, 0); }
 
-  /// \brief Compute an APInt containing numBits highbits from this APInt.
+  /// Compute an APInt containing numBits highbits from this APInt.
   ///
   /// Get an APInt with the same BitWidth as this APInt, just zero mask
   /// the low bits and right shift to the least significant bit.
@@ -569,7 +575,7 @@ public:
   /// \returns the high "numBits" bits of this APInt.
   APInt getHiBits(unsigned numBits) const;
 
-  /// \brief Compute an APInt containing numBits lowbits from this APInt.
+  /// Compute an APInt containing numBits lowbits from this APInt.
   ///
   /// Get an APInt with the same BitWidth as this APInt, just zero mask
   /// the high bits.
@@ -577,14 +583,14 @@ public:
   /// \returns the low "numBits" bits of this APInt.
   APInt getLoBits(unsigned numBits) const;
 
-  /// \brief Return an APInt with exactly one bit set in the result.
+  /// 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;
   }
 
-  /// \brief Get a value with a block of bits set.
+  /// Get a value with a block of bits set.
   ///
   /// 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
@@ -603,7 +609,7 @@ public:
     return Res;
   }
 
-  /// \brief Get a value with upper bits starting at loBit set.
+  /// Get a value with upper bits starting at loBit set.
   ///
   /// Constructs an APInt value that has a contiguous range of bits set. The
   /// bits from loBit (inclusive) to numBits (exclusive) will be set. All other
@@ -620,7 +626,7 @@ public:
     return Res;
   }
 
-  /// \brief Get a value with high bits set
+  /// Get a value with high bits set
   ///
   /// Constructs an APInt value that has the top hiBitsSet bits set.
   ///
@@ -632,7 +638,7 @@ public:
     return Res;
   }
 
-  /// \brief Get a value with low bits set
+  /// Get a value with low bits set
   ///
   /// Constructs an APInt value that has the bottom loBitsSet bits set.
   ///
@@ -644,10 +650,10 @@ public:
     return Res;
   }
 
-  /// \brief Return a value containing V broadcasted over NewLen bits.
+  /// Return a value containing V broadcasted over NewLen bits.
   static APInt getSplat(unsigned NewLen, const APInt &V);
 
-  /// \brief Determine if two APInts have the same value, after zero-extending
+  /// Determine if two APInts have the same value, after zero-extending
   /// one of them (if needed!) to ensure that the bit-widths match.
   static bool isSameValue(const APInt &I1, const APInt &I2) {
     if (I1.getBitWidth() == I2.getBitWidth())
@@ -659,7 +665,7 @@ public:
     return I1.zext(I2.getBitWidth()) == I2;
   }
 
-  /// \brief Overload to compute a hash_code for an APInt value.
+  /// 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.
@@ -675,7 +681,7 @@ public:
   /// \name Unary Operators
   /// @{
 
-  /// \brief Postfix increment operator.
+  /// Postfix increment operator.
   ///
   /// Increments *this by 1.
   ///
@@ -686,12 +692,12 @@ public:
     return API;
   }
 
-  /// \brief Prefix increment operator.
+  /// Prefix increment operator.
   ///
   /// \returns *this incremented by one
   APInt &operator++();
 
-  /// \brief Postfix decrement operator.
+  /// Postfix decrement operator.
   ///
   /// Decrements *this by 1.
   ///
@@ -702,12 +708,12 @@ public:
     return API;
   }
 
-  /// \brief Prefix decrement operator.
+  /// Prefix decrement operator.
   ///
   /// \returns *this decremented by one.
   APInt &operator--();
 
-  /// \brief Logical negation operator.
+  /// Logical negation operator.
   ///
   /// Performs logical negation operation on this APInt.
   ///
@@ -722,7 +728,7 @@ public:
   /// \name Assignment Operators
   /// @{
 
-  /// \brief Copy assignment operator.
+  /// Copy assignment operator.
   ///
   /// \returns *this after assignment of RHS.
   APInt &operator=(const APInt &RHS) {
@@ -737,8 +743,13 @@ public:
     return *this;
   }
 
-  /// @brief Move assignment operator.
+  /// Move assignment operator.
   APInt &operator=(APInt &&that) {
+#ifdef _MSC_VER
+    // The MSVC std::shuffle implementation still does self-assignment.
+    if (this == &that)
+      return *this;
+#endif
     assert(this != &that && "Self-move not supported");
     if (!isSingleWord())
       delete[] U.pVal;
@@ -753,7 +764,7 @@ public:
     return *this;
   }
 
-  /// \brief Assignment operator.
+  /// Assignment operator.
   ///
   /// The RHS value is assigned to *this. If the significant bits in RHS exceed
   /// the bit width, the excess bits are truncated. If the bit width is larger
@@ -771,7 +782,7 @@ public:
     return *this;
   }
 
-  /// \brief Bitwise AND assignment operator.
+  /// Bitwise AND assignment operator.
   ///
   /// Performs a bitwise AND operation on this APInt and RHS. The result is
   /// assigned to *this.
@@ -786,7 +797,7 @@ public:
     return *this;
   }
 
-  /// \brief Bitwise AND assignment operator.
+  /// Bitwise AND assignment operator.
   ///
   /// Performs a bitwise AND operation on this APInt and RHS. RHS is
   /// logically zero-extended or truncated to match the bit-width of
@@ -801,7 +812,7 @@ public:
     return *this;
   }
 
-  /// \brief Bitwise OR assignment operator.
+  /// Bitwise OR assignment operator.
   ///
   /// Performs a bitwise OR operation on this APInt and RHS. The result is
   /// assigned *this;
@@ -816,7 +827,7 @@ public:
     return *this;
   }
 
-  /// \brief Bitwise OR assignment operator.
+  /// 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
@@ -831,7 +842,7 @@ public:
     return *this;
   }
 
-  /// \brief Bitwise XOR assignment operator.
+  /// Bitwise XOR assignment operator.
   ///
   /// Performs a bitwise XOR operation on this APInt and RHS. The result is
   /// assigned to *this.
@@ -846,7 +857,7 @@ public:
     return *this;
   }
 
-  /// \brief Bitwise XOR assignment operator.
+  /// Bitwise XOR assignment operator.
   ///
   /// Performs a bitwise XOR operation on this APInt and RHS. RHS is
   /// logically zero-extended or truncated to match the bit-width of
@@ -861,7 +872,7 @@ public:
     return *this;
   }
 
-  /// \brief Multiplication assignment operator.
+  /// Multiplication assignment operator.
   ///
   /// Multiplies this APInt by RHS and assigns the result to *this.
   ///
@@ -869,7 +880,7 @@ public:
   APInt &operator*=(const APInt &RHS);
   APInt &operator*=(uint64_t RHS);
 
-  /// \brief Addition assignment operator.
+  /// Addition assignment operator.
   ///
   /// Adds RHS to *this and assigns the result to *this.
   ///
@@ -877,7 +888,7 @@ public:
   APInt &operator+=(const APInt &RHS);
   APInt &operator+=(uint64_t RHS);
 
-  /// \brief Subtraction assignment operator.
+  /// Subtraction assignment operator.
   ///
   /// Subtracts RHS from *this and assigns the result to *this.
   ///
@@ -885,7 +896,7 @@ public:
   APInt &operator-=(const APInt &RHS);
   APInt &operator-=(uint64_t RHS);
 
-  /// \brief Left-shift assignment function.
+  /// Left-shift assignment function.
   ///
   /// Shifts *this left by shiftAmt and assigns the result to *this.
   ///
@@ -903,7 +914,7 @@ public:
     return *this;
   }
 
-  /// \brief Left-shift assignment function.
+  /// Left-shift assignment function.
   ///
   /// Shifts *this left by shiftAmt and assigns the result to *this.
   ///
@@ -914,22 +925,22 @@ public:
   /// \name Binary Operators
   /// @{
 
-  /// \brief Multiplication operator.
+  /// Multiplication operator.
   ///
   /// Multiplies this APInt by RHS and returns the result.
   APInt operator*(const APInt &RHS) const;
 
-  /// \brief Left logical shift operator.
+  /// Left logical shift operator.
   ///
   /// Shifts this APInt left by \p Bits and returns the result.
   APInt operator<<(unsigned Bits) const { return shl(Bits); }
 
-  /// \brief Left logical shift operator.
+  /// Left logical shift operator.
   ///
   /// Shifts this APInt left by \p Bits and returns the result.
   APInt operator<<(const APInt &Bits) const { return shl(Bits); }
 
-  /// \brief Arithmetic right-shift function.
+  /// Arithmetic right-shift function.
   ///
   /// Arithmetic right-shift this APInt by shiftAmt.
   APInt ashr(unsigned ShiftAmt) const {
@@ -953,7 +964,7 @@ public:
     ashrSlowCase(ShiftAmt);
   }
 
-  /// \brief Logical right-shift function.
+  /// Logical right-shift function.
   ///
   /// Logical right-shift this APInt by shiftAmt.
   APInt lshr(unsigned shiftAmt) const {
@@ -975,7 +986,7 @@ public:
     lshrSlowCase(ShiftAmt);
   }
 
-  /// \brief Left-shift function.
+  /// Left-shift function.
   ///
   /// Left-shift this APInt by shiftAmt.
   APInt shl(unsigned shiftAmt) const {
@@ -984,13 +995,13 @@ public:
     return R;
   }
 
-  /// \brief Rotate left by rotateAmt.
+  /// Rotate left by rotateAmt.
   APInt rotl(unsigned rotateAmt) const;
 
-  /// \brief Rotate right by rotateAmt.
+  /// Rotate right by rotateAmt.
   APInt rotr(unsigned rotateAmt) const;
 
-  /// \brief Arithmetic right-shift function.
+  /// Arithmetic right-shift function.
   ///
   /// Arithmetic right-shift this APInt by shiftAmt.
   APInt ashr(const APInt &ShiftAmt) const {
@@ -1002,7 +1013,7 @@ public:
   /// Arithmetic right-shift this APInt by shiftAmt in place.
   void ashrInPlace(const APInt &shiftAmt);
 
-  /// \brief Logical right-shift function.
+  /// Logical right-shift function.
   ///
   /// Logical right-shift this APInt by shiftAmt.
   APInt lshr(const APInt &ShiftAmt) const {
@@ -1014,7 +1025,7 @@ public:
   /// Logical right-shift this APInt by ShiftAmt in place.
   void lshrInPlace(const APInt &ShiftAmt);
 
-  /// \brief Left-shift function.
+  /// Left-shift function.
   ///
   /// Left-shift this APInt by shiftAmt.
   APInt shl(const APInt &ShiftAmt) const {
@@ -1023,28 +1034,31 @@ public:
     return R;
   }
 
-  /// \brief Rotate left by rotateAmt.
+  /// Rotate left by rotateAmt.
   APInt rotl(const APInt &rotateAmt) const;
 
-  /// \brief Rotate right by rotateAmt.
+  /// Rotate right by rotateAmt.
   APInt rotr(const APInt &rotateAmt) const;
 
-  /// \brief Unsigned division operation.
+  /// Unsigned division operation.
   ///
   /// Perform an unsigned divide operation on this APInt by RHS. Both this and
   /// RHS are treated as unsigned quantities for purposes of this division.
   ///
-  /// \returns a new APInt value containing the division result
+  /// \returns a new APInt value containing the division result, rounded towards
+  /// zero.
   APInt udiv(const APInt &RHS) const;
   APInt udiv(uint64_t RHS) const;
 
-  /// \brief Signed division function for APInt.
+  /// Signed division function for APInt.
   ///
   /// Signed divide this APInt by APInt RHS.
+  ///
+  /// The result is rounded towards zero.
   APInt sdiv(const APInt &RHS) const;
   APInt sdiv(int64_t RHS) const;
 
-  /// \brief Unsigned remainder operation.
+  /// Unsigned remainder operation.
   ///
   /// Perform an unsigned remainder operation on this APInt with RHS being the
   /// divisor. Both this and RHS are treated as unsigned quantities for purposes
@@ -1056,13 +1070,13 @@ public:
   APInt urem(const APInt &RHS) const;
   uint64_t urem(uint64_t RHS) const;
 
-  /// \brief Function for signed remainder operation.
+  /// Function for signed remainder operation.
   ///
   /// Signed remainder operation on APInt.
   APInt srem(const APInt &RHS) const;
   int64_t srem(int64_t RHS) const;
 
-  /// \brief Dual division/remainder interface.
+  /// Dual division/remainder interface.
   ///
   /// Sometimes it is convenient to divide two APInt values and obtain both the
   /// quotient and remainder. This function does both operations in the same
@@ -1090,7 +1104,7 @@ public:
   APInt sshl_ov(const APInt &Amt, bool &Overflow) const;
   APInt ushl_ov(const APInt &Amt, bool &Overflow) const;
 
-  /// \brief Array-indexing support.
+  /// Array-indexing support.
   ///
   /// \returns the bit value at bitPosition
   bool operator[](unsigned bitPosition) const {
@@ -1102,7 +1116,7 @@ public:
   /// \name Comparison Operators
   /// @{
 
-  /// \brief Equality operator.
+  /// Equality operator.
   ///
   /// Compares this APInt with RHS for the validity of the equality
   /// relationship.
@@ -1113,7 +1127,7 @@ public:
     return EqualSlowCase(RHS);
   }
 
-  /// \brief Equality operator.
+  /// Equality operator.
   ///
   /// Compares this APInt with a uint64_t for the validity of the equality
   /// relationship.
@@ -1123,7 +1137,7 @@ public:
     return (isSingleWord() || getActiveBits() <= 64) && getZExtValue() == Val;
   }
 
-  /// \brief Equality comparison.
+  /// Equality comparison.
   ///
   /// Compares this APInt with RHS for the validity of the equality
   /// relationship.
@@ -1131,7 +1145,7 @@ public:
   /// \returns true if *this == Val
   bool eq(const APInt &RHS) const { return (*this) == RHS; }
 
-  /// \brief Inequality operator.
+  /// Inequality operator.
   ///
   /// Compares this APInt with RHS for the validity of the inequality
   /// relationship.
@@ -1139,7 +1153,7 @@ public:
   /// \returns true if *this != Val
   bool operator!=(const APInt &RHS) const { return !((*this) == RHS); }
 
-  /// \brief Inequality operator.
+  /// Inequality operator.
   ///
   /// Compares this APInt with a uint64_t for the validity of the inequality
   /// relationship.
@@ -1147,7 +1161,7 @@ public:
   /// \returns true if *this != Val
   bool operator!=(uint64_t Val) const { return !((*this) == Val); }
 
-  /// \brief Inequality comparison
+  /// Inequality comparison
   ///
   /// Compares this APInt with RHS for the validity of the inequality
   /// relationship.
@@ -1155,7 +1169,7 @@ public:
   /// \returns true if *this != Val
   bool ne(const APInt &RHS) const { return !((*this) == RHS); }
 
-  /// \brief Unsigned less than comparison
+  /// Unsigned less than comparison
   ///
   /// Regards both *this and RHS as unsigned quantities and compares them for
   /// the validity of the less-than relationship.
@@ -1163,7 +1177,7 @@ public:
   /// \returns true if *this < RHS when both are considered unsigned.
   bool ult(const APInt &RHS) const { return compare(RHS) < 0; }
 
-  /// \brief Unsigned less than comparison
+  /// Unsigned less than comparison
   ///
   /// Regards both *this as an unsigned quantity and compares it with RHS for
   /// the validity of the less-than relationship.
@@ -1174,7 +1188,7 @@ public:
     return (isSingleWord() || getActiveBits() <= 64) && getZExtValue() < RHS;
   }
 
-  /// \brief Signed less than comparison
+  /// Signed less than comparison
   ///
   /// Regards both *this and RHS as signed quantities and compares them for
   /// validity of the less-than relationship.
@@ -1182,7 +1196,7 @@ public:
   /// \returns true if *this < RHS when both are considered signed.
   bool slt(const APInt &RHS) const { return compareSigned(RHS) < 0; }
 
-  /// \brief Signed less than comparison
+  /// Signed less than comparison
   ///
   /// Regards both *this as a signed quantity and compares it with RHS for
   /// the validity of the less-than relationship.
@@ -1193,7 +1207,7 @@ public:
                                                         : getSExtValue() < RHS;
   }
 
-  /// \brief Unsigned less or equal comparison
+  /// Unsigned less or equal comparison
   ///
   /// Regards both *this and RHS as unsigned quantities and compares them for
   /// validity of the less-or-equal relationship.
@@ -1201,7 +1215,7 @@ public:
   /// \returns true if *this <= RHS when both are considered unsigned.
   bool ule(const APInt &RHS) const { return compare(RHS) <= 0; }
 
-  /// \brief Unsigned less or equal comparison
+  /// Unsigned less or equal comparison
   ///
   /// Regards both *this as an unsigned quantity and compares it with RHS for
   /// the validity of the less-or-equal relationship.
@@ -1209,7 +1223,7 @@ public:
   /// \returns true if *this <= RHS when considered unsigned.
   bool ule(uint64_t RHS) const { return !ugt(RHS); }
 
-  /// \brief Signed less or equal comparison
+  /// Signed less or equal comparison
   ///
   /// Regards both *this and RHS as signed quantities and compares them for
   /// validity of the less-or-equal relationship.
@@ -1217,7 +1231,7 @@ public:
   /// \returns true if *this <= RHS when both are considered signed.
   bool sle(const APInt &RHS) const { return compareSigned(RHS) <= 0; }
 
-  /// \brief Signed less or equal comparison
+  /// Signed less or equal comparison
   ///
   /// Regards both *this as a signed quantity and compares it with RHS for the
   /// validity of the less-or-equal relationship.
@@ -1225,7 +1239,7 @@ public:
   /// \returns true if *this <= RHS when considered signed.
   bool sle(uint64_t RHS) const { return !sgt(RHS); }
 
-  /// \brief Unsigned greather than comparison
+  /// Unsigned greather than comparison
   ///
   /// Regards both *this and RHS as unsigned quantities and compares them for
   /// the validity of the greater-than relationship.
@@ -1233,7 +1247,7 @@ public:
   /// \returns true if *this > RHS when both are considered unsigned.
   bool ugt(const APInt &RHS) const { return !ule(RHS); }
 
-  /// \brief Unsigned greater than comparison
+  /// Unsigned greater than comparison
   ///
   /// Regards both *this as an unsigned quantity and compares it with RHS for
   /// the validity of the greater-than relationship.
@@ -1244,7 +1258,7 @@ public:
     return (!isSingleWord() && getActiveBits() > 64) || getZExtValue() > RHS;
   }
 
-  /// \brief Signed greather than comparison
+  /// Signed greather than comparison
   ///
   /// Regards both *this and RHS as signed quantities and compares them for the
   /// validity of the greater-than relationship.
@@ -1252,7 +1266,7 @@ public:
   /// \returns true if *this > RHS when both are considered signed.
   bool sgt(const APInt &RHS) const { return !sle(RHS); }
 
-  /// \brief Signed greater than comparison
+  /// Signed greater than comparison
   ///
   /// Regards both *this as a signed quantity and compares it with RHS for
   /// the validity of the greater-than relationship.
@@ -1263,7 +1277,7 @@ public:
                                                         : getSExtValue() > RHS;
   }
 
-  /// \brief Unsigned greater or equal comparison
+  /// Unsigned greater or equal comparison
   ///
   /// Regards both *this and RHS as unsigned quantities and compares them for
   /// validity of the greater-or-equal relationship.
@@ -1271,7 +1285,7 @@ public:
   /// \returns true if *this >= RHS when both are considered unsigned.
   bool uge(const APInt &RHS) const { return !ult(RHS); }
 
-  /// \brief Unsigned greater or equal comparison
+  /// Unsigned greater or equal comparison
   ///
   /// Regards both *this as an unsigned quantity and compares it with RHS for
   /// the validity of the greater-or-equal relationship.
@@ -1279,7 +1293,7 @@ public:
   /// \returns true if *this >= RHS when considered unsigned.
   bool uge(uint64_t RHS) const { return !ult(RHS); }
 
-  /// \brief Signed greather or equal comparison
+  /// Signed greater or equal comparison
   ///
   /// Regards both *this and RHS as signed quantities and compares them for
   /// validity of the greater-or-equal relationship.
@@ -1287,7 +1301,7 @@ public:
   /// \returns true if *this >= RHS when both are considered signed.
   bool sge(const APInt &RHS) const { return !slt(RHS); }
 
-  /// \brief Signed greater or equal comparison
+  /// Signed greater or equal comparison
   ///
   /// Regards both *this as a signed quantity and compares it with RHS for
   /// the validity of the greater-or-equal relationship.
@@ -1316,13 +1330,13 @@ public:
   /// \name Resizing Operators
   /// @{
 
-  /// \brief Truncate to new width.
+  /// Truncate to new width.
   ///
   /// 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.
   APInt trunc(unsigned width) const;
 
-  /// \brief Sign extend to a new width.
+  /// Sign extend to a new width.
   ///
   /// 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.
@@ -1330,32 +1344,32 @@ public:
   /// current width.
   APInt sext(unsigned width) const;
 
-  /// \brief Zero extend to a new width.
+  /// Zero extend to a new width.
   ///
   /// 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.
   APInt zext(unsigned width) const;
 
-  /// \brief Sign extend or truncate to width
+  /// Sign extend or truncate to width
   ///
   /// 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.
   APInt sextOrTrunc(unsigned width) const;
 
-  /// \brief Zero extend or truncate to width
+  /// Zero extend or truncate to width
   ///
   /// 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.
   APInt zextOrTrunc(unsigned width) const;
 
-  /// \brief Sign extend or truncate to width
+  /// Sign extend or truncate to width
   ///
   /// Make this APInt have the bit width given by \p width. The value is sign
   /// extended, or left alone to make it that width.
   APInt sextOrSelf(unsigned width) const;
 
-  /// \brief Zero extend or truncate to width
+  /// Zero extend or truncate to width
   ///
   /// Make this APInt have the bit width given by \p width. The value is zero
   /// extended, or left alone to make it that width.
@@ -1365,7 +1379,7 @@ public:
   /// \name Bit Manipulation Operators
   /// @{
 
-  /// \brief Set every bit to 1.
+  /// Set every bit to 1.
   void setAllBits() {
     if (isSingleWord())
       U.VAL = WORD_MAX;
@@ -1376,7 +1390,7 @@ public:
     clearUnusedBits();
   }
 
-  /// \brief Set a given bit to 1.
+  /// Set a given bit to 1.
   ///
   /// Set the given bit to 1 whose position is given as "bitPosition".
   void setBit(unsigned BitPosition) {
@@ -1427,7 +1441,7 @@ public:
     return setBits(BitWidth - hiBits, BitWidth);
   }
 
-  /// \brief Set every bit to 0.
+  /// Set every bit to 0.
   void clearAllBits() {
     if (isSingleWord())
       U.VAL = 0;
@@ -1435,7 +1449,7 @@ public:
       memset(U.pVal, 0, getNumWords() * APINT_WORD_SIZE);
   }
 
-  /// \brief Set a given bit to 0.
+  /// Set a given bit to 0.
   ///
   /// Set the given bit to 0 whose position is given as "bitPosition".
   void clearBit(unsigned BitPosition) {
@@ -1452,7 +1466,7 @@ public:
     clearBit(BitWidth - 1);
   }
 
-  /// \brief Toggle every bit to its opposite value.
+  /// Toggle every bit to its opposite value.
   void flipAllBits() {
     if (isSingleWord()) {
       U.VAL ^= WORD_MAX;
@@ -1462,7 +1476,7 @@ public:
     }
   }
 
-  /// \brief Toggles a given bit to its opposite value.
+  /// Toggles a given bit to its opposite value.
   ///
   /// Toggle a given bit to its opposite value whose position is given
   /// as "bitPosition".
@@ -1484,17 +1498,17 @@ public:
   /// \name Value Characterization Functions
   /// @{
 
-  /// \brief Return the number of bits in the APInt.
+  /// Return the number of bits in the APInt.
   unsigned getBitWidth() const { return BitWidth; }
 
-  /// \brief Get the number of words.
+  /// Get the number of words.
   ///
   /// Here one word's bitwidth equals to that of uint64_t.
   ///
   /// \returns the number of words to hold the integer value of this APInt.
   unsigned getNumWords() const { return getNumWords(BitWidth); }
 
-  /// \brief Get the number of words.
+  /// Get the number of words.
   ///
   /// *NOTE* Here one word's bitwidth equals to that of uint64_t.
   ///
@@ -1504,14 +1518,14 @@ public:
     return ((uint64_t)BitWidth + APINT_BITS_PER_WORD - 1) / APINT_BITS_PER_WORD;
   }
 
-  /// \brief Compute the number of active bits in the value
+  /// Compute the number of active bits in the value
   ///
   /// This function returns the number of active bits which is defined as the
   /// bit width minus the number of leading zeros. This is used in several
   /// computations to see how "wide" the value is.
   unsigned getActiveBits() const { return BitWidth - countLeadingZeros(); }
 
-  /// \brief Compute the number of active words in the value of this APInt.
+  /// Compute the number of active words in the value of this APInt.
   ///
   /// This is used in conjunction with getActiveData to extract the raw value of
   /// the APInt.
@@ -1520,7 +1534,7 @@ public:
     return numActiveBits ? whichWord(numActiveBits - 1) + 1 : 1;
   }
 
-  /// \brief Get the minimum bit size for this signed APInt
+  /// Get the minimum bit size for this signed APInt
   ///
   /// Computes the minimum bit width for this APInt while considering it to be a
   /// signed (and probably negative) value. If the value is not negative, this
@@ -1534,7 +1548,7 @@ public:
     return getActiveBits() + 1;
   }
 
-  /// \brief Get zero extended value
+  /// 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
@@ -1546,7 +1560,7 @@ public:
     return U.pVal[0];
   }
 
-  /// \brief Get sign extended value
+  /// 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
@@ -1558,13 +1572,13 @@ public:
     return int64_t(U.pVal[0]);
   }
 
-  /// \brief Get bits required for string value.
+  /// 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
+  /// The APInt version of the countLeadingZeros functions in
   ///   MathExtras.h.
   ///
   /// It counts the number of zeros from the most significant bit to the first
@@ -1580,7 +1594,7 @@ public:
     return countLeadingZerosSlowCase();
   }
 
-  /// \brief Count the number of leading one bits.
+  /// 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
@@ -1600,7 +1614,7 @@ public:
     return isNegative() ? countLeadingOnes() : countLeadingZeros();
   }
 
-  /// \brief Count the number of trailing zero bits.
+  /// Count the number of trailing zero bits.
   ///
   /// This function is an APInt version of the countTrailingZeros
   /// functions in MathExtras.h. It counts the number of zeros from the least
@@ -1614,7 +1628,7 @@ public:
     return countTrailingZerosSlowCase();
   }
 
-  /// \brief Count the number of trailing one bits.
+  /// Count the number of trailing one bits.
   ///
   /// This function is an APInt version of the countTrailingOnes
   /// functions in MathExtras.h. It counts the number of ones from the least
@@ -1628,7 +1642,7 @@ public:
     return countTrailingOnesSlowCase();
   }
 
-  /// \brief Count the number of bits set.
+  /// 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.
@@ -1662,7 +1676,7 @@ public:
     toString(Str, Radix, true, false);
   }
 
-  /// \brief Return the APInt as a std::string.
+  /// Return the APInt as a std::string.
   ///
   /// Note that this is an inefficient method.  It is better to pass in a
   /// SmallVector/SmallString to the methods above to avoid thrashing the heap
@@ -1676,16 +1690,16 @@ public:
   /// Value.
   APInt reverseBits() const;
 
-  /// \brief Converts this APInt to a double value.
+  /// Converts this APInt to a double value.
   double roundToDouble(bool isSigned) const;
 
-  /// \brief Converts this unsigned APInt to a double value.
+  /// Converts this unsigned APInt to a double value.
   double roundToDouble() const { return roundToDouble(false); }
 
-  /// \brief Converts this signed APInt to a double value.
+  /// Converts this signed APInt to a double value.
   double signedRoundToDouble() const { return roundToDouble(true); }
 
-  /// \brief Converts APInt bits to a double
+  /// Converts APInt bits to a double
   ///
   /// 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
@@ -1694,7 +1708,7 @@ public:
     return BitsToDouble(getWord(0));
   }
 
-  /// \brief Converts APInt bits to a double
+  /// 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
@@ -1703,7 +1717,7 @@ public:
     return BitsToFloat(getWord(0));
   }
 
-  /// \brief Converts a double to APInt bits.
+  /// 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.
@@ -1711,7 +1725,7 @@ public:
     return APInt(sizeof(double) * CHAR_BIT, DoubleToBits(V));
   }
 
-  /// \brief Converts a float to APInt bits.
+  /// Converts a float to APInt bits.
   ///
   /// The conversion does not do a translation from float to integer, it just
   /// re-interprets the bits of the float.
@@ -1770,10 +1784,10 @@ public:
     return logBase2();
   }
 
-  /// \brief Compute the square root
+  /// Compute the square root
   APInt sqrt() const;
 
-  /// \brief Get the absolute value;
+  /// Get the absolute value;
   ///
   /// If *this is < 0 then return -(*this), otherwise *this;
   APInt abs() const {
@@ -1924,7 +1938,7 @@ public:
   /// Set the least significant BITS and clear the rest.
   static void tcSetLeastSignificantBits(WordType *, unsigned, unsigned bits);
 
-  /// \brief debug method
+  /// debug method
   void dump() const;
 
   /// @}
@@ -1947,7 +1961,7 @@ inline bool operator==(uint64_t V1, const APInt &V2) { return V2 == V1; }
 
 inline bool operator!=(uint64_t V1, const APInt &V2) { return V2 != V1; }
 
-/// \brief Unary bitwise complement operator.
+/// Unary bitwise complement operator.
 ///
 /// \returns an APInt that is the bitwise complement of \p v.
 inline APInt operator~(APInt v) {
@@ -2080,27 +2094,27 @@ inline APInt operator*(uint64_t LHS, APInt b) {
 
 namespace APIntOps {
 
-/// \brief Determine the smaller of two APInts considered to be signed.
+/// Determine the smaller of two APInts considered to be signed.
 inline const APInt &smin(const APInt &A, const APInt &B) {
   return A.slt(B) ? A : B;
 }
 
-/// \brief Determine the larger of two APInts considered to be signed.
+/// Determine the larger of two APInts considered to be signed.
 inline const APInt &smax(const APInt &A, const APInt &B) {
   return A.sgt(B) ? A : B;
 }
 
-/// \brief Determine the smaller of two APInts considered to be signed.
+/// Determine the smaller of two APInts considered to be signed.
 inline const APInt &umin(const APInt &A, const APInt &B) {
   return A.ult(B) ? A : B;
 }
 
-/// \brief Determine the larger of two APInts considered to be unsigned.
+/// Determine the larger of two APInts considered to be unsigned.
 inline const APInt &umax(const APInt &A, const APInt &B) {
   return A.ugt(B) ? A : B;
 }
 
-/// \brief Compute GCD of two unsigned APInt values.
+/// Compute GCD of two unsigned APInt values.
 ///
 /// This function returns the greatest common divisor of the two APInt values
 /// using Stein's algorithm.
@@ -2108,44 +2122,50 @@ inline const APInt &umax(const APInt &A, const APInt &B) {
 /// \returns the greatest common divisor of A and B.
 APInt GreatestCommonDivisor(APInt A, APInt B);
 
-/// \brief Converts the given APInt to a double value.
+/// Converts the given APInt to a double value.
 ///
 /// Treats the APInt as an unsigned value for conversion purposes.
 inline double RoundAPIntToDouble(const APInt &APIVal) {
   return APIVal.roundToDouble();
 }
 
-/// \brief Converts the given APInt to a double value.
+/// Converts the given APInt to a double value.
 ///
 /// Treats the APInt as a signed value for conversion purposes.
 inline double RoundSignedAPIntToDouble(const APInt &APIVal) {
   return APIVal.signedRoundToDouble();
 }
 
-/// \brief Converts the given APInt to a float vlalue.
+/// Converts the given APInt to a float vlalue.
 inline float RoundAPIntToFloat(const APInt &APIVal) {
   return float(RoundAPIntToDouble(APIVal));
 }
 
-/// \brief Converts the given APInt to a float value.
+/// Converts the given APInt to a float value.
 ///
 /// Treast the APInt as a signed value for conversion purposes.
 inline float RoundSignedAPIntToFloat(const APInt &APIVal) {
   return float(APIVal.signedRoundToDouble());
 }
 
-/// \brief Converts the given double value into a APInt.
+/// Converts the given double value into a APInt.
 ///
 /// This function convert a double value to an APInt value.
 APInt RoundDoubleToAPInt(double Double, unsigned width);
 
-/// \brief Converts a float value into a APInt.
+/// Converts a float value into a APInt.
 ///
 /// Converts a float value into an APInt value.
 inline APInt RoundFloatToAPInt(float Float, unsigned width) {
   return RoundDoubleToAPInt(double(Float), width);
 }
 
+/// Return A unsign-divided by B, rounded by the given rounding mode.
+APInt RoundingUDiv(const APInt &A, const APInt &B, APInt::Rounding RM);
+
+/// Return A sign-divided by B, rounded by the given rounding mode.
+APInt RoundingSDiv(const APInt &A, const APInt &B, APInt::Rounding RM);
+
 } // End of APIntOps namespace
 
 // See friend declaration above. This additional declaration is required in
diff --git a/include/llvm/ADT/APSInt.h b/include/llvm/ADT/APSInt.h
index dabbf3314bd0..7ee2c4c62fce 100644
--- a/include/llvm/ADT/APSInt.h
+++ b/include/llvm/ADT/APSInt.h
@@ -72,7 +72,7 @@ public:
   }
   using APInt::toString;
 
-  /// \brief Get the correctly-extended \c int64_t value.
+  /// Get the correctly-extended \c int64_t value.
   int64_t getExtValue() const {
     assert(getMinSignedBits() <= 64 && "Too many bits for int64_t");
     return isSigned() ? getSExtValue() : getZExtValue();
@@ -279,13 +279,13 @@ public:
                            : APInt::getSignedMinValue(numBits), Unsigned);
   }
 
-  /// \brief Determine if two APSInts have the same value, zero- or
+  /// Determine if two APSInts have the same value, zero- or
   /// sign-extending as needed.
   static bool isSameValue(const APSInt &I1, const APSInt &I2) {
     return !compareValues(I1, I2);
   }
 
-  /// \brief Compare underlying values of two numbers.
+  /// Compare underlying values of two numbers.
   static int compareValues(const APSInt &I1, const APSInt &I2) {
     if (I1.getBitWidth() == I2.getBitWidth() && I1.isSigned() == I2.isSigned())
       return I1.IsUnsigned ? I1.compare(I2) : I1.compareSigned(I2);
diff --git a/include/llvm/ADT/Any.h b/include/llvm/ADT/Any.h
new file mode 100644
index 000000000000..c64c39987542
--- /dev/null
+++ b/include/llvm/ADT/Any.h
@@ -0,0 +1,150 @@
+//===- Any.h - Generic type erased holder of any type -----------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file provides Any, a non-template class modeled in the spirit of
+//  std::any.  The idea is to provide a type-safe replacement for C's void*.
+//  It can hold a value of any copy-constructible copy-assignable type
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_ANY_H
+#define LLVM_ADT_ANY_H
+
+#include "llvm/ADT/STLExtras.h"
+
+#include <cassert>
+#include <memory>
+#include <type_traits>
+
+namespace llvm {
+
+class Any {
+  template <typename T> struct TypeId { static const char Id; };
+
+  struct StorageBase {
+    virtual ~StorageBase() = default;
+    virtual std::unique_ptr<StorageBase> clone() const = 0;
+    virtual const void *id() const = 0;
+  };
+
+  template <typename T> struct StorageImpl : public StorageBase {
+    explicit StorageImpl(const T &Value) : Value(Value) {}
+
+    explicit StorageImpl(T &&Value) : Value(std::move(Value)) {}
+
+    std::unique_ptr<StorageBase> clone() const override {
+      return llvm::make_unique<StorageImpl<T>>(Value);
+    }
+
+    const void *id() const override { return &TypeId<T>::Id; }
+
+    T Value;
+
+  private:
+    StorageImpl &operator=(const StorageImpl &Other) = delete;
+    StorageImpl(const StorageImpl &Other) = delete;
+  };
+
+public:
+  Any() = default;
+
+  Any(const Any &Other)
+      : Storage(Other.Storage ? Other.Storage->clone() : nullptr) {}
+
+  // When T is Any or T is not copy-constructible we need to explicitly disable
+  // the forwarding constructor so that the copy constructor gets selected
+  // instead.
+  template <
+      typename T,
+      typename std::enable_if<
+          llvm::conjunction<
+              llvm::negation<std::is_same<typename std::decay<T>::type, Any>>,
+              std::is_copy_constructible<typename std::decay<T>::type>>::value,
+          int>::type = 0>
+  Any(T &&Value) {
+    using U = typename std::decay<T>::type;
+    Storage = llvm::make_unique<StorageImpl<U>>(std::forward<T>(Value));
+  }
+
+  Any(Any &&Other) : Storage(std::move(Other.Storage)) {}
+
+  Any &swap(Any &Other) {
+    std::swap(Storage, Other.Storage);
+    return *this;
+  }
+
+  Any &operator=(Any Other) {
+    Storage = std::move(Other.Storage);
+    return *this;
+  }
+
+  bool hasValue() const { return !!Storage; }
+
+  void reset() { Storage.reset(); }
+
+private:
+  template <class T> friend T any_cast(const Any &Value);
+  template <class T> friend T any_cast(Any &Value);
+  template <class T> friend T any_cast(Any &&Value);
+  template <class T> friend const T *any_cast(const Any *Value);
+  template <class T> friend T *any_cast(Any *Value);
+  template <typename T> friend bool any_isa(const Any &Value);
+
+  std::unique_ptr<StorageBase> Storage;
+};
+
+template <typename T> const char Any::TypeId<T>::Id = 0;
+
+
+template <typename T> bool any_isa(const Any &Value) {
+  if (!Value.Storage)
+    return false;
+  using U =
+      typename std::remove_cv<typename std::remove_reference<T>::type>::type;
+  return Value.Storage->id() == &Any::TypeId<U>::Id;
+}
+
+template <class T> T any_cast(const Any &Value) {
+  using U =
+      typename std::remove_cv<typename std::remove_reference<T>::type>::type;
+  return static_cast<T>(*any_cast<U>(&Value));
+}
+
+template <class T> T any_cast(Any &Value) {
+  using U =
+      typename std::remove_cv<typename std::remove_reference<T>::type>::type;
+  return static_cast<T>(*any_cast<U>(&Value));
+}
+
+template <class T> T any_cast(Any &&Value) {
+  using U =
+      typename std::remove_cv<typename std::remove_reference<T>::type>::type;
+  return static_cast<T>(std::move(*any_cast<U>(&Value)));
+}
+
+template <class T> const T *any_cast(const Any *Value) {
+  using U =
+      typename std::remove_cv<typename std::remove_reference<T>::type>::type;
+  assert(Value && any_isa<T>(*Value) && "Bad any cast!");
+  if (!Value || !any_isa<U>(*Value))
+    return nullptr;
+  return &static_cast<Any::StorageImpl<U> &>(*Value->Storage).Value;
+}
+
+template <class T> T *any_cast(Any *Value) {
+  using U = typename std::decay<T>::type;
+  assert(Value && any_isa<U>(*Value) && "Bad any cast!");
+  if (!Value || !any_isa<U>(*Value))
+    return nullptr;
+  return &static_cast<Any::StorageImpl<U> &>(*Value->Storage).Value;
+}
+
+} // end namespace llvm
+
+#endif // LLVM_ADT_ANY_H
diff --git a/include/llvm/ADT/ArrayRef.h b/include/llvm/ADT/ArrayRef.h
index 5f7a769ddac4..9cb25b09c6cb 100644
--- a/include/llvm/ADT/ArrayRef.h
+++ b/include/llvm/ADT/ArrayRef.h
@@ -184,51 +184,51 @@ namespace llvm {
     /// slice(n) - Chop off the first N elements of the array.
     ArrayRef<T> slice(size_t N) const { return slice(N, size() - N); }
 
-    /// \brief Drop the first \p N elements of the array.
+    /// Drop the first \p N elements of the array.
     ArrayRef<T> drop_front(size_t N = 1) const {
       assert(size() >= N && "Dropping more elements than exist");
       return slice(N, size() - N);
     }
 
-    /// \brief Drop the last \p N elements of the array.
+    /// Drop the last \p N elements of the array.
     ArrayRef<T> drop_back(size_t N = 1) const {
       assert(size() >= N && "Dropping more elements than exist");
       return slice(0, size() - N);
     }
 
-    /// \brief Return a copy of *this with the first N elements satisfying the
+    /// Return a copy of *this with the first N elements satisfying the
     /// given predicate removed.
     template <class PredicateT> ArrayRef<T> drop_while(PredicateT Pred) const {
       return ArrayRef<T>(find_if_not(*this, Pred), end());
     }
 
-    /// \brief Return a copy of *this with the first N elements not satisfying
+    /// Return a copy of *this with the first N elements not satisfying
     /// the given predicate removed.
     template <class PredicateT> ArrayRef<T> drop_until(PredicateT Pred) const {
       return ArrayRef<T>(find_if(*this, Pred), end());
     }
 
-    /// \brief Return a copy of *this with only the first \p N elements.
+    /// Return a copy of *this with only the first \p N elements.
     ArrayRef<T> take_front(size_t N = 1) const {
       if (N >= size())
         return *this;
       return drop_back(size() - N);
     }
 
-    /// \brief Return a copy of *this with only the last \p N elements.
+    /// Return a copy of *this with only the last \p N elements.
     ArrayRef<T> take_back(size_t N = 1) const {
       if (N >= size())
         return *this;
       return drop_front(size() - N);
     }
 
-    /// \brief Return the first N elements of this Array that satisfy the given
+    /// Return the first N elements of this Array that satisfy the given
     /// predicate.
     template <class PredicateT> ArrayRef<T> take_while(PredicateT Pred) const {
       return ArrayRef<T>(begin(), find_if_not(*this, Pred));
     }
 
-    /// \brief Return the first N elements of this Array that don't satisfy the
+    /// Return the first N elements of this Array that don't satisfy the
     /// given predicate.
     template <class PredicateT> ArrayRef<T> take_until(PredicateT Pred) const {
       return ArrayRef<T>(begin(), find_if(*this, Pred));
@@ -358,7 +358,7 @@ namespace llvm {
       return slice(N, this->size() - N);
     }
 
-    /// \brief Drop the first \p N elements of the array.
+    /// Drop the first \p N elements of the array.
     MutableArrayRef<T> drop_front(size_t N = 1) const {
       assert(this->size() >= N && "Dropping more elements than exist");
       return slice(N, this->size() - N);
@@ -369,42 +369,42 @@ namespace llvm {
       return slice(0, this->size() - N);
     }
 
-    /// \brief Return a copy of *this with the first N elements satisfying the
+    /// Return a copy of *this with the first N elements satisfying the
     /// given predicate removed.
     template <class PredicateT>
     MutableArrayRef<T> drop_while(PredicateT Pred) const {
       return MutableArrayRef<T>(find_if_not(*this, Pred), end());
     }
 
-    /// \brief Return a copy of *this with the first N elements not satisfying
+    /// Return a copy of *this with the first N elements not satisfying
     /// the given predicate removed.
     template <class PredicateT>
     MutableArrayRef<T> drop_until(PredicateT Pred) const {
       return MutableArrayRef<T>(find_if(*this, Pred), end());
     }
 
-    /// \brief Return a copy of *this with only the first \p N elements.
+    /// Return a copy of *this with only the first \p N elements.
     MutableArrayRef<T> take_front(size_t N = 1) const {
       if (N >= this->size())
         return *this;
       return drop_back(this->size() - N);
     }
 
-    /// \brief Return a copy of *this with only the last \p N elements.
+    /// Return a copy of *this with only the last \p N elements.
     MutableArrayRef<T> take_back(size_t N = 1) const {
       if (N >= this->size())
         return *this;
       return drop_front(this->size() - N);
     }
 
-    /// \brief Return the first N elements of this Array that satisfy the given
+    /// Return the first N elements of this Array that satisfy the given
     /// predicate.
     template <class PredicateT>
     MutableArrayRef<T> take_while(PredicateT Pred) const {
       return MutableArrayRef<T>(begin(), find_if_not(*this, Pred));
     }
 
-    /// \brief Return the first N elements of this Array that don't satisfy the
+    /// Return the first N elements of this Array that don't satisfy the
     /// given predicate.
     template <class PredicateT>
     MutableArrayRef<T> take_until(PredicateT Pred) const {
diff --git a/include/llvm/ADT/BitVector.h b/include/llvm/ADT/BitVector.h
index 99147fec4d4c..438c7d84c581 100644
--- a/include/llvm/ADT/BitVector.h
+++ b/include/llvm/ADT/BitVector.h
@@ -779,7 +779,7 @@ public:
   }
 
 private:
-  /// \brief Perform a logical left shift of \p Count words by moving everything
+  /// Perform a logical left shift of \p Count words by moving everything
   /// \p Count words to the right in memory.
   ///
   /// While confusing, words are stored from least significant at Bits[0] to
@@ -810,7 +810,7 @@ private:
     clear_unused_bits();
   }
 
-  /// \brief Perform a logical right shift of \p Count words by moving those
+  /// Perform a logical right shift of \p Count words by moving those
   /// words to the left in memory.  See wordShl for more information.
   ///
   void wordShr(uint32_t Count) {
@@ -828,7 +828,8 @@ private:
   }
 
   MutableArrayRef<BitWord> allocate(size_t NumWords) {
-    BitWord *RawBits = (BitWord *)std::malloc(NumWords * sizeof(BitWord));
+    BitWord *RawBits = static_cast<BitWord *>(
+        safe_malloc(NumWords * sizeof(BitWord)));
     return MutableArrayRef<BitWord>(RawBits, NumWords);
   }
 
@@ -867,8 +868,8 @@ private:
   void grow(unsigned NewSize) {
     size_t NewCapacity = std::max<size_t>(NumBitWords(NewSize), Bits.size() * 2);
     assert(NewCapacity > 0 && "realloc-ing zero space");
-    BitWord *NewBits =
-        (BitWord *)std::realloc(Bits.data(), NewCapacity * sizeof(BitWord));
+    BitWord *NewBits = static_cast<BitWord *>(
+        safe_realloc(Bits.data(), NewCapacity * sizeof(BitWord)));
     Bits = MutableArrayRef<BitWord>(NewBits, NewCapacity);
     clear_unused_bits();
   }
diff --git a/include/llvm/ADT/CachedHashString.h b/include/llvm/ADT/CachedHashString.h
index a56a6213a073..d8f0e7afdd49 100644
--- a/include/llvm/ADT/CachedHashString.h
+++ b/include/llvm/ADT/CachedHashString.h
@@ -43,6 +43,7 @@ public:
   }
 
   StringRef val() const { return StringRef(P, Size); }
+  const char *data() const { return P; }
   uint32_t size() const { return Size; }
   uint32_t hash() const { return Hash; }
 };
diff --git a/include/llvm/ADT/DenseMapInfo.h b/include/llvm/ADT/DenseMapInfo.h
index a96904c7dbbf..5d12b424fb37 100644
--- a/include/llvm/ADT/DenseMapInfo.h
+++ b/include/llvm/ADT/DenseMapInfo.h
@@ -262,6 +262,13 @@ template <typename T> struct DenseMapInfo<ArrayRef<T>> {
   }
 };
 
+template <> struct DenseMapInfo<hash_code> {
+  static inline hash_code getEmptyKey() { return hash_code(-1); }
+  static inline hash_code getTombstoneKey() { return hash_code(-2); }
+  static unsigned getHashValue(hash_code val) { return val; }
+  static bool isEqual(hash_code LHS, hash_code RHS) { return LHS == RHS; }
+};
+
 } // end namespace llvm
 
 #endif // LLVM_ADT_DENSEMAPINFO_H
diff --git a/include/llvm/ADT/DepthFirstIterator.h b/include/llvm/ADT/DepthFirstIterator.h
index e964d7fa2391..1f3766d3c9de 100644
--- a/include/llvm/ADT/DepthFirstIterator.h
+++ b/include/llvm/ADT/DepthFirstIterator.h
@@ -177,7 +177,7 @@ public:
     return *this;
   }
 
-  /// \brief Skips all children of the current node and traverses to next node
+  /// Skips all children of the current node and traverses to next node
   ///
   /// Note: This function takes care of incrementing the iterator. If you
   /// always increment and call this function, you risk walking off the end.
diff --git a/include/llvm/ADT/EpochTracker.h b/include/llvm/ADT/EpochTracker.h
index db39ba4e0c50..49ef192364e8 100644
--- a/include/llvm/ADT/EpochTracker.h
+++ b/include/llvm/ADT/EpochTracker.h
@@ -17,7 +17,6 @@
 #define LLVM_ADT_EPOCH_TRACKER_H
 
 #include "llvm/Config/abi-breaking.h"
-#include "llvm/Config/llvm-config.h"
 
 #include <cstdint>
 
@@ -25,7 +24,7 @@ namespace llvm {
 
 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
 
-/// \brief A base class for data structure classes wishing to make iterators
+/// A base class for data structure classes wishing to make iterators
 /// ("handles") pointing into themselves fail-fast.  When building without
 /// asserts, this class is empty and does nothing.
 ///
@@ -40,15 +39,15 @@ class DebugEpochBase {
 public:
   DebugEpochBase() : Epoch(0) {}
 
-  /// \brief Calling incrementEpoch invalidates all handles pointing into the
+  /// Calling incrementEpoch invalidates all handles pointing into the
   /// calling instance.
   void incrementEpoch() { ++Epoch; }
 
-  /// \brief The destructor calls incrementEpoch to make use-after-free bugs
+  /// The destructor calls incrementEpoch to make use-after-free bugs
   /// more likely to crash deterministically.
   ~DebugEpochBase() { incrementEpoch(); }
 
-  /// \brief A base class for iterator classes ("handles") that wish to poll for
+  /// A base class for iterator classes ("handles") that wish to poll for
   /// iterator invalidating modifications in the underlying data structure.
   /// When LLVM is built without asserts, this class is empty and does nothing.
   ///
@@ -66,12 +65,12 @@ public:
     explicit HandleBase(const DebugEpochBase *Parent)
         : EpochAddress(&Parent->Epoch), EpochAtCreation(Parent->Epoch) {}
 
-    /// \brief Returns true if the DebugEpochBase this Handle is linked to has
+    /// Returns true if the DebugEpochBase this Handle is linked to has
     /// not called incrementEpoch on itself since the creation of this
     /// HandleBase instance.
     bool isHandleInSync() const { return *EpochAddress == EpochAtCreation; }
 
-    /// \brief Returns a pointer to the epoch word stored in the data structure
+    /// Returns a pointer to the epoch word stored in the data structure
     /// this handle points into.  Can be used to check if two iterators point
     /// into the same data structure.
     const void *getEpochAddress() const { return EpochAddress; }
diff --git a/include/llvm/ADT/FunctionExtras.h b/include/llvm/ADT/FunctionExtras.h
new file mode 100644
index 000000000000..2b75dc6ac219
--- /dev/null
+++ b/include/llvm/ADT/FunctionExtras.h
@@ -0,0 +1,293 @@
+//===- FunctionExtras.h - Function type erasure utilities -------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+/// \file
+/// This file provides a collection of function (or more generally, callable)
+/// type erasure utilities supplementing those provided by the standard library
+/// in `<function>`.
+///
+/// It provides `unique_function`, which works like `std::function` but supports
+/// move-only callable objects.
+///
+/// Future plans:
+/// - Add a `function` that provides const, volatile, and ref-qualified support,
+///   which doesn't work with `std::function`.
+/// - Provide support for specifying multiple signatures to type erase callable
+///   objects with an overload set, such as those produced by generic lambdas.
+/// - Expand to include a copyable utility that directly replaces std::function
+///   but brings the above improvements.
+///
+/// Note that LLVM's utilities are greatly simplified by not supporting
+/// allocators.
+///
+/// If the standard library ever begins to provide comparable facilities we can
+/// consider switching to those.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_FUNCTION_EXTRAS_H
+#define LLVM_ADT_FUNCTION_EXTRAS_H
+
+#include "llvm/ADT/PointerIntPair.h"
+#include "llvm/ADT/PointerUnion.h"
+#include "llvm/Support/type_traits.h"
+#include <memory>
+
+namespace llvm {
+
+template <typename FunctionT> class unique_function;
+
+template <typename ReturnT, typename... ParamTs>
+class unique_function<ReturnT(ParamTs...)> {
+  static constexpr size_t InlineStorageSize = sizeof(void *) * 3;
+
+  // MSVC has a bug and ICEs if we give it a particular dependent value
+  // expression as part of the `std::conditional` below. To work around this,
+  // we build that into a template struct's constexpr bool.
+  template <typename T> struct IsSizeLessThanThresholdT {
+    static constexpr bool value = sizeof(T) <= (2 * sizeof(void *));
+  };
+
+  // Provide a type function to map parameters that won't observe extra copies
+  // or moves and which are small enough to likely pass in register to values
+  // and all other types to l-value reference types. We use this to compute the
+  // types used in our erased call utility to minimize copies and moves unless
+  // doing so would force things unnecessarily into memory.
+  //
+  // The heuristic used is related to common ABI register passing conventions.
+  // It doesn't have to be exact though, and in one way it is more strict
+  // because we want to still be able to observe either moves *or* copies.
+  template <typename T>
+  using AdjustedParamT = typename std::conditional<
+      !std::is_reference<T>::value &&
+          llvm::is_trivially_copy_constructible<T>::value &&
+          llvm::is_trivially_move_constructible<T>::value &&
+          IsSizeLessThanThresholdT<T>::value,
+      T, T &>::type;
+
+  // The type of the erased function pointer we use as a callback to dispatch to
+  // the stored callable when it is trivial to move and destroy.
+  using CallPtrT = ReturnT (*)(void *CallableAddr,
+                               AdjustedParamT<ParamTs>... Params);
+  using MovePtrT = void (*)(void *LHSCallableAddr, void *RHSCallableAddr);
+  using DestroyPtrT = void (*)(void *CallableAddr);
+
+  /// A struct to hold a single trivial callback with sufficient alignment for
+  /// our bitpacking.
+  struct alignas(8) TrivialCallback {
+    CallPtrT CallPtr;
+  };
+
+  /// A struct we use to aggregate three callbacks when we need full set of
+  /// operations.
+  struct alignas(8) NonTrivialCallbacks {
+    CallPtrT CallPtr;
+    MovePtrT MovePtr;
+    DestroyPtrT DestroyPtr;
+  };
+
+  // Create a pointer union between either a pointer to a static trivial call
+  // pointer in a struct or a pointer to a static struct of the call, move, and
+  // destroy pointers.
+  using CallbackPointerUnionT =
+      PointerUnion<TrivialCallback *, NonTrivialCallbacks *>;
+
+  // The main storage buffer. This will either have a pointer to out-of-line
+  // storage or an inline buffer storing the callable.
+  union StorageUnionT {
+    // For out-of-line storage we keep a pointer to the underlying storage and
+    // the size. This is enough to deallocate the memory.
+    struct OutOfLineStorageT {
+      void *StoragePtr;
+      size_t Size;
+      size_t Alignment;
+    } OutOfLineStorage;
+    static_assert(
+        sizeof(OutOfLineStorageT) <= InlineStorageSize,
+        "Should always use all of the out-of-line storage for inline storage!");
+
+    // For in-line storage, we just provide an aligned character buffer. We
+    // provide three pointers worth of storage here.
+    typename std::aligned_storage<InlineStorageSize, alignof(void *)>::type
+        InlineStorage;
+  } StorageUnion;
+
+  // A compressed pointer to either our dispatching callback or our table of
+  // dispatching callbacks and the flag for whether the callable itself is
+  // stored inline or not.
+  PointerIntPair<CallbackPointerUnionT, 1, bool> CallbackAndInlineFlag;
+
+  bool isInlineStorage() const { return CallbackAndInlineFlag.getInt(); }
+
+  bool isTrivialCallback() const {
+    return CallbackAndInlineFlag.getPointer().template is<TrivialCallback *>();
+  }
+
+  CallPtrT getTrivialCallback() const {
+    return CallbackAndInlineFlag.getPointer().template get<TrivialCallback *>()->CallPtr;
+  }
+
+  NonTrivialCallbacks *getNonTrivialCallbacks() const {
+    return CallbackAndInlineFlag.getPointer()
+        .template get<NonTrivialCallbacks *>();
+  }
+
+  void *getInlineStorage() { return &StorageUnion.InlineStorage; }
+
+  void *getOutOfLineStorage() {
+    return StorageUnion.OutOfLineStorage.StoragePtr;
+  }
+  size_t getOutOfLineStorageSize() const {
+    return StorageUnion.OutOfLineStorage.Size;
+  }
+  size_t getOutOfLineStorageAlignment() const {
+    return StorageUnion.OutOfLineStorage.Alignment;
+  }
+
+  void setOutOfLineStorage(void *Ptr, size_t Size, size_t Alignment) {
+    StorageUnion.OutOfLineStorage = {Ptr, Size, Alignment};
+  }
+
+  template <typename CallableT>
+  static ReturnT CallImpl(void *CallableAddr, AdjustedParamT<ParamTs>... Params) {
+    return (*reinterpret_cast<CallableT *>(CallableAddr))(
+        std::forward<ParamTs>(Params)...);
+  }
+
+  template <typename CallableT>
+  static void MoveImpl(void *LHSCallableAddr, void *RHSCallableAddr) noexcept {
+    new (LHSCallableAddr)
+        CallableT(std::move(*reinterpret_cast<CallableT *>(RHSCallableAddr)));
+  }
+
+  template <typename CallableT>
+  static void DestroyImpl(void *CallableAddr) noexcept {
+    reinterpret_cast<CallableT *>(CallableAddr)->~CallableT();
+  }
+
+public:
+  unique_function() = default;
+  unique_function(std::nullptr_t /*null_callable*/) {}
+
+  ~unique_function() {
+    if (!CallbackAndInlineFlag.getPointer())
+      return;
+
+    // Cache this value so we don't re-check it after type-erased operations.
+    bool IsInlineStorage = isInlineStorage();
+
+    if (!isTrivialCallback())
+      getNonTrivialCallbacks()->DestroyPtr(
+          IsInlineStorage ? getInlineStorage() : getOutOfLineStorage());
+
+    if (!IsInlineStorage)
+      deallocate_buffer(getOutOfLineStorage(), getOutOfLineStorageSize(),
+                        getOutOfLineStorageAlignment());
+  }
+
+  unique_function(unique_function &&RHS) noexcept {
+    // Copy the callback and inline flag.
+    CallbackAndInlineFlag = RHS.CallbackAndInlineFlag;
+
+    // If the RHS is empty, just copying the above is sufficient.
+    if (!RHS)
+      return;
+
+    if (!isInlineStorage()) {
+      // The out-of-line case is easiest to move.
+      StorageUnion.OutOfLineStorage = RHS.StorageUnion.OutOfLineStorage;
+    } else if (isTrivialCallback()) {
+      // Move is trivial, just memcpy the bytes across.
+      memcpy(getInlineStorage(), RHS.getInlineStorage(), InlineStorageSize);
+    } else {
+      // Non-trivial move, so dispatch to a type-erased implementation.
+      getNonTrivialCallbacks()->MovePtr(getInlineStorage(),
+                                        RHS.getInlineStorage());
+    }
+
+    // Clear the old callback and inline flag to get back to as-if-null.
+    RHS.CallbackAndInlineFlag = {};
+
+#ifndef NDEBUG
+    // In debug builds, we also scribble across the rest of the storage.
+    memset(RHS.getInlineStorage(), 0xAD, InlineStorageSize);
+#endif
+  }
+
+  unique_function &operator=(unique_function &&RHS) noexcept {
+    if (this == &RHS)
+      return *this;
+
+    // Because we don't try to provide any exception safety guarantees we can
+    // implement move assignment very simply by first destroying the current
+    // object and then move-constructing over top of it.
+    this->~unique_function();
+    new (this) unique_function(std::move(RHS));
+    return *this;
+  }
+
+  template <typename CallableT> unique_function(CallableT Callable) {
+    bool IsInlineStorage = true;
+    void *CallableAddr = getInlineStorage();
+    if (sizeof(CallableT) > InlineStorageSize ||
+        alignof(CallableT) > alignof(decltype(StorageUnion.InlineStorage))) {
+      IsInlineStorage = false;
+      // Allocate out-of-line storage. FIXME: Use an explicit alignment
+      // parameter in C++17 mode.
+      auto Size = sizeof(CallableT);
+      auto Alignment = alignof(CallableT);
+      CallableAddr = allocate_buffer(Size, Alignment);
+      setOutOfLineStorage(CallableAddr, Size, Alignment);
+    }
+
+    // Now move into the storage.
+    new (CallableAddr) CallableT(std::move(Callable));
+
+    // See if we can create a trivial callback. We need the callable to be
+    // trivially moved and trivially destroyed so that we don't have to store
+    // type erased callbacks for those operations.
+    //
+    // FIXME: We should use constexpr if here and below to avoid instantiating
+    // the non-trivial static objects when unnecessary. While the linker should
+    // remove them, it is still wasteful.
+    if (llvm::is_trivially_move_constructible<CallableT>::value &&
+        std::is_trivially_destructible<CallableT>::value) {
+      // We need to create a nicely aligned object. We use a static variable
+      // for this because it is a trivial struct.
+      static TrivialCallback Callback = { &CallImpl<CallableT> };
+
+      CallbackAndInlineFlag = {&Callback, IsInlineStorage};
+      return;
+    }
+
+    // Otherwise, we need to point at an object that contains all the different
+    // type erased behaviors needed. Create a static instance of the struct type
+    // here and then use a pointer to that.
+    static NonTrivialCallbacks Callbacks = {
+        &CallImpl<CallableT>, &MoveImpl<CallableT>, &DestroyImpl<CallableT>};
+
+    CallbackAndInlineFlag = {&Callbacks, IsInlineStorage};
+  }
+
+  ReturnT operator()(ParamTs... Params) {
+    void *CallableAddr =
+        isInlineStorage() ? getInlineStorage() : getOutOfLineStorage();
+
+    return (isTrivialCallback()
+                ? getTrivialCallback()
+                : getNonTrivialCallbacks()->CallPtr)(CallableAddr, Params...);
+  }
+
+  explicit operator bool() const {
+    return (bool)CallbackAndInlineFlag.getPointer();
+  }
+};
+
+} // end namespace llvm
+
+#endif // LLVM_ADT_FUNCTION_H
diff --git a/include/llvm/ADT/GraphTraits.h b/include/llvm/ADT/GraphTraits.h
index 225d9eb847f0..27c647f4bbbd 100644
--- a/include/llvm/ADT/GraphTraits.h
+++ b/include/llvm/ADT/GraphTraits.h
@@ -47,6 +47,19 @@ struct GraphTraits {
   // static nodes_iterator nodes_end  (GraphType *G)
   //    nodes_iterator/begin/end - Allow iteration over all nodes in the graph
 
+  // typedef EdgeRef           - Type of Edge token in the graph, which should
+  //                             be cheap to copy.
+  // typedef ChildEdgeIteratorType - Type used to iterate over children edges in
+  //                             graph, dereference to a EdgeRef.
+
+  // static ChildEdgeIteratorType child_edge_begin(NodeRef)
+  // static ChildEdgeIteratorType child_edge_end(NodeRef)
+  //     Return iterators that point to the beginning and ending of the
+  //     edge list for the given callgraph node.
+  //
+  // static NodeRef edge_dest(EdgeRef)
+  //     Return the destination node of an edge.
+
   // static unsigned       size       (GraphType *G)
   //    Return total number of nodes in the graph
 
@@ -111,6 +124,13 @@ inverse_children(const typename GraphTraits<GraphType>::NodeRef &G) {
                     GraphTraits<Inverse<GraphType>>::child_end(G));
 }
 
+template <class GraphType>
+iterator_range<typename GraphTraits<GraphType>::ChildEdgeIteratorType>
+children_edges(const typename GraphTraits<GraphType>::NodeRef &G) {
+  return make_range(GraphTraits<GraphType>::child_edge_begin(G),
+                    GraphTraits<GraphType>::child_edge_end(G));
+}
+
 } // end namespace llvm
 
 #endif // LLVM_ADT_GRAPHTRAITS_H
diff --git a/include/llvm/ADT/Hashing.h b/include/llvm/ADT/Hashing.h
index c3b574102f69..9f830baa4243 100644
--- a/include/llvm/ADT/Hashing.h
+++ b/include/llvm/ADT/Hashing.h
@@ -57,7 +57,7 @@
 
 namespace llvm {
 
-/// \brief An opaque object representing a hash code.
+/// An opaque object representing a hash code.
 ///
 /// This object represents the result of hashing some entity. It is intended to
 /// be used to implement hashtables or other hashing-based data structures.
@@ -73,14 +73,14 @@ class hash_code {
   size_t value;
 
 public:
-  /// \brief Default construct a hash_code.
+  /// Default construct a hash_code.
   /// Note that this leaves the value uninitialized.
   hash_code() = default;
 
-  /// \brief Form a hash code directly from a numerical value.
+  /// Form a hash code directly from a numerical value.
   hash_code(size_t value) : value(value) {}
 
-  /// \brief Convert the hash code to its numerical value for use.
+  /// Convert the hash code to its numerical value for use.
   /*explicit*/ operator size_t() const { return value; }
 
   friend bool operator==(const hash_code &lhs, const hash_code &rhs) {
@@ -90,11 +90,11 @@ public:
     return lhs.value != rhs.value;
   }
 
-  /// \brief Allow a hash_code to be directly run through hash_value.
+  /// Allow a hash_code to be directly run through hash_value.
   friend size_t hash_value(const hash_code &code) { return code.value; }
 };
 
-/// \brief Compute a hash_code for any integer value.
+/// Compute a hash_code for any integer value.
 ///
 /// Note that this function is intended to compute the same hash_code for
 /// a particular value without regard to the pre-promotion type. This is in
@@ -105,21 +105,21 @@ template <typename T>
 typename std::enable_if<is_integral_or_enum<T>::value, hash_code>::type
 hash_value(T value);
 
-/// \brief Compute a hash_code for a pointer's address.
+/// Compute a hash_code for a pointer's address.
 ///
 /// N.B.: This hashes the *address*. Not the value and not the type.
 template <typename T> hash_code hash_value(const T *ptr);
 
-/// \brief Compute a hash_code for a pair of objects.
+/// Compute a hash_code for a pair of objects.
 template <typename T, typename U>
 hash_code hash_value(const std::pair<T, U> &arg);
 
-/// \brief Compute a hash_code for a standard string.
+/// Compute a hash_code for a standard string.
 template <typename T>
 hash_code hash_value(const std::basic_string<T> &arg);
 
 
-/// \brief Override the execution seed with a fixed value.
+/// Override the execution seed with a fixed value.
 ///
 /// This hashing library uses a per-execution seed designed to change on each
 /// run with high probability in order to ensure that the hash codes are not
@@ -164,7 +164,7 @@ static const uint64_t k1 = 0xb492b66fbe98f273ULL;
 static const uint64_t k2 = 0x9ae16a3b2f90404fULL;
 static const uint64_t k3 = 0xc949d7c7509e6557ULL;
 
-/// \brief Bitwise right rotate.
+/// Bitwise right rotate.
 /// Normally this will compile to a single instruction, especially if the
 /// shift is a manifest constant.
 inline uint64_t rotate(uint64_t val, size_t shift) {
@@ -254,13 +254,13 @@ inline uint64_t hash_short(const char *s, size_t length, uint64_t seed) {
   return k2 ^ seed;
 }
 
-/// \brief The intermediate state used during hashing.
+/// The intermediate state used during hashing.
 /// Currently, the algorithm for computing hash codes is based on CityHash and
 /// keeps 56 bytes of arbitrary state.
 struct hash_state {
   uint64_t h0, h1, h2, h3, h4, h5, h6;
 
-  /// \brief Create a new hash_state structure and initialize it based on the
+  /// Create a new hash_state structure and initialize it based on the
   /// seed and the first 64-byte chunk.
   /// This effectively performs the initial mix.
   static hash_state create(const char *s, uint64_t seed) {
@@ -272,7 +272,7 @@ struct hash_state {
     return state;
   }
 
-  /// \brief Mix 32-bytes from the input sequence into the 16-bytes of 'a'
+  /// Mix 32-bytes from the input sequence into the 16-bytes of 'a'
   /// and 'b', including whatever is already in 'a' and 'b'.
   static void mix_32_bytes(const char *s, uint64_t &a, uint64_t &b) {
     a += fetch64(s);
@@ -284,7 +284,7 @@ struct hash_state {
     a += c;
   }
 
-  /// \brief Mix in a 64-byte buffer of data.
+  /// Mix in a 64-byte buffer of data.
   /// We mix all 64 bytes even when the chunk length is smaller, but we
   /// record the actual length.
   void mix(const char *s) {
@@ -302,7 +302,7 @@ struct hash_state {
     std::swap(h2, h0);
   }
 
-  /// \brief Compute the final 64-bit hash code value based on the current
+  /// Compute the final 64-bit hash code value based on the current
   /// state and the length of bytes hashed.
   uint64_t finalize(size_t length) {
     return hash_16_bytes(hash_16_bytes(h3, h5) + shift_mix(h1) * k1 + h2,
@@ -311,7 +311,7 @@ struct hash_state {
 };
 
 
-/// \brief A global, fixed seed-override variable.
+/// A global, fixed seed-override variable.
 ///
 /// This variable can be set using the \see llvm::set_fixed_execution_seed
 /// function. See that function for details. Do not, under any circumstances,
@@ -332,7 +332,7 @@ inline size_t get_execution_seed() {
 }
 
 
-/// \brief Trait to indicate whether a type's bits can be hashed directly.
+/// Trait to indicate whether a type's bits can be hashed directly.
 ///
 /// A type trait which is true if we want to combine values for hashing by
 /// reading the underlying data. It is false if values of this type must
@@ -359,14 +359,14 @@ template <typename T, typename U> struct is_hashable_data<std::pair<T, U> >
                                   (sizeof(T) + sizeof(U)) ==
                                    sizeof(std::pair<T, U>))> {};
 
-/// \brief Helper to get the hashable data representation for a type.
+/// Helper to get the hashable data representation for a type.
 /// This variant is enabled when the type itself can be used.
 template <typename T>
 typename std::enable_if<is_hashable_data<T>::value, T>::type
 get_hashable_data(const T &value) {
   return value;
 }
-/// \brief Helper to get the hashable data representation for a type.
+/// Helper to get the hashable data representation for a type.
 /// This variant is enabled when we must first call hash_value and use the
 /// result as our data.
 template <typename T>
@@ -376,7 +376,7 @@ get_hashable_data(const T &value) {
   return hash_value(value);
 }
 
-/// \brief Helper to store data from a value into a buffer and advance the
+/// Helper to store data from a value into a buffer and advance the
 /// pointer into that buffer.
 ///
 /// This routine first checks whether there is enough space in the provided
@@ -395,7 +395,7 @@ bool store_and_advance(char *&buffer_ptr, char *buffer_end, const T& value,
   return true;
 }
 
-/// \brief Implement the combining of integral values into a hash_code.
+/// Implement the combining of integral values into a hash_code.
 ///
 /// This overload is selected when the value type of the iterator is
 /// integral. Rather than computing a hash_code for each object and then
@@ -435,7 +435,7 @@ hash_code hash_combine_range_impl(InputIteratorT first, InputIteratorT last) {
   return state.finalize(length);
 }
 
-/// \brief Implement the combining of integral values into a hash_code.
+/// Implement the combining of integral values into a hash_code.
 ///
 /// This overload is selected when the value type of the iterator is integral
 /// and when the input iterator is actually a pointer. Rather than computing
@@ -470,7 +470,7 @@ hash_combine_range_impl(ValueT *first, ValueT *last) {
 } // namespace hashing
 
 
-/// \brief Compute a hash_code for a sequence of values.
+/// Compute a hash_code for a sequence of values.
 ///
 /// This hashes a sequence of values. It produces the same hash_code as
 /// 'hash_combine(a, b, c, ...)', but can run over arbitrary sized sequences
@@ -486,7 +486,7 @@ hash_code hash_combine_range(InputIteratorT first, InputIteratorT last) {
 namespace hashing {
 namespace detail {
 
-/// \brief Helper class to manage the recursive combining of hash_combine
+/// Helper class to manage the recursive combining of hash_combine
 /// arguments.
 ///
 /// This class exists to manage the state and various calls involved in the
@@ -499,14 +499,14 @@ struct hash_combine_recursive_helper {
   const size_t seed;
 
 public:
-  /// \brief Construct a recursive hash combining helper.
+  /// Construct a recursive hash combining helper.
   ///
   /// This sets up the state for a recursive hash combine, including getting
   /// the seed and buffer setup.
   hash_combine_recursive_helper()
     : seed(get_execution_seed()) {}
 
-  /// \brief Combine one chunk of data into the current in-flight hash.
+  /// Combine one chunk of data into the current in-flight hash.
   ///
   /// This merges one chunk of data into the hash. First it tries to buffer
   /// the data. If the buffer is full, it hashes the buffer into its
@@ -547,7 +547,7 @@ public:
     return buffer_ptr;
   }
 
-  /// \brief Recursive, variadic combining method.
+  /// Recursive, variadic combining method.
   ///
   /// This function recurses through each argument, combining that argument
   /// into a single hash.
@@ -560,7 +560,7 @@ public:
     return combine(length, buffer_ptr, buffer_end, args...);
   }
 
-  /// \brief Base case for recursive, variadic combining.
+  /// Base case for recursive, variadic combining.
   ///
   /// The base case when combining arguments recursively is reached when all
   /// arguments have been handled. It flushes the remaining buffer and
@@ -588,7 +588,7 @@ public:
 } // namespace detail
 } // namespace hashing
 
-/// \brief Combine values into a single hash_code.
+/// Combine values into a single hash_code.
 ///
 /// This routine accepts a varying number of arguments of any type. It will
 /// attempt to combine them into a single hash_code. For user-defined types it
@@ -610,7 +610,7 @@ template <typename ...Ts> hash_code hash_combine(const Ts &...args) {
 namespace hashing {
 namespace detail {
 
-/// \brief Helper to hash the value of a single integer.
+/// Helper to hash the value of a single integer.
 ///
 /// Overloads for smaller integer types are not provided to ensure consistent
 /// behavior in the presence of integral promotions. Essentially,
diff --git a/include/llvm/ADT/ImmutableList.h b/include/llvm/ADT/ImmutableList.h
index 60d63e09d426..1f5e9813798d 100644
--- a/include/llvm/ADT/ImmutableList.h
+++ b/include/llvm/ADT/ImmutableList.h
@@ -166,7 +166,7 @@ public:
     if (ownsAllocator()) delete &getAllocator();
   }
 
-  ImmutableList<T> concat(const T& Head, ImmutableList<T> Tail) {
+  LLVM_NODISCARD ImmutableList<T> concat(const T &Head, ImmutableList<T> Tail) {
     // Profile the new list to see if it already exists in our cache.
     FoldingSetNodeID ID;
     void* InsertPos;
@@ -188,7 +188,7 @@ public:
     return L;
   }
 
-  ImmutableList<T> add(const T& D, ImmutableList<T> L) {
+  LLVM_NODISCARD ImmutableList<T> add(const T& D, ImmutableList<T> L) {
     return concat(D, L);
   }
 
diff --git a/include/llvm/ADT/ImmutableMap.h b/include/llvm/ADT/ImmutableMap.h
index 10d1e1f0139b..cbc27ff17ccf 100644
--- a/include/llvm/ADT/ImmutableMap.h
+++ b/include/llvm/ADT/ImmutableMap.h
@@ -114,12 +114,13 @@ public:
 
     ImmutableMap getEmptyMap() { return ImmutableMap(F.getEmptyTree()); }
 
-    ImmutableMap add(ImmutableMap Old, key_type_ref K, data_type_ref D) {
+    LLVM_NODISCARD ImmutableMap add(ImmutableMap Old, key_type_ref K,
+                                    data_type_ref D) {
       TreeTy *T = F.add(Old.Root, std::pair<key_type,data_type>(K,D));
       return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T);
     }
 
-    ImmutableMap remove(ImmutableMap Old, key_type_ref K) {
+    LLVM_NODISCARD ImmutableMap remove(ImmutableMap Old, key_type_ref K) {
       TreeTy *T = F.remove(Old.Root,K);
       return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T);
     }
diff --git a/include/llvm/ADT/ImmutableSet.h b/include/llvm/ADT/ImmutableSet.h
index 9d580c5a3d41..b1d5f4ac42e4 100644
--- a/include/llvm/ADT/ImmutableSet.h
+++ b/include/llvm/ADT/ImmutableSet.h
@@ -1017,7 +1017,7 @@ public:
     ///  of this operation is logarithmic in the size of the original set.
     ///  The memory allocated to represent the set is released when the
     ///  factory object that created the set is destroyed.
-    ImmutableSet add(ImmutableSet Old, value_type_ref V) {
+    LLVM_NODISCARD ImmutableSet add(ImmutableSet Old, value_type_ref V) {
       TreeTy *NewT = F.add(Old.Root, V);
       return ImmutableSet(Canonicalize ? F.getCanonicalTree(NewT) : NewT);
     }
@@ -1029,7 +1029,7 @@ public:
     ///  of this operation is logarithmic in the size of the original set.
     ///  The memory allocated to represent the set is released when the
     ///  factory object that created the set is destroyed.
-    ImmutableSet remove(ImmutableSet Old, value_type_ref V) {
+    LLVM_NODISCARD ImmutableSet remove(ImmutableSet Old, value_type_ref V) {
       TreeTy *NewT = F.remove(Old.Root, V);
       return ImmutableSet(Canonicalize ? F.getCanonicalTree(NewT) : NewT);
     }
diff --git a/include/llvm/ADT/MapVector.h b/include/llvm/ADT/MapVector.h
index 3d78f4b203c8..47b4987f210a 100644
--- a/include/llvm/ADT/MapVector.h
+++ b/include/llvm/ADT/MapVector.h
@@ -36,13 +36,17 @@ template<typename KeyT, typename ValueT,
          typename MapType = DenseMap<KeyT, unsigned>,
          typename VectorType = std::vector<std::pair<KeyT, ValueT>>>
 class MapVector {
-  using value_type = typename VectorType::value_type;
-  using size_type = typename VectorType::size_type;
-
   MapType Map;
   VectorType Vector;
 
+  static_assert(
+      std::is_integral<typename MapType::mapped_type>::value,
+      "The mapped_type of the specified Map must be an integral type");
+
 public:
+  using value_type = typename VectorType::value_type;
+  using size_type = typename VectorType::size_type;
+
   using iterator = typename VectorType::iterator;
   using const_iterator = typename VectorType::const_iterator;
   using reverse_iterator = typename VectorType::reverse_iterator;
@@ -93,9 +97,9 @@ public:
   }
 
   ValueT &operator[](const KeyT &Key) {
-    std::pair<KeyT, unsigned> Pair = std::make_pair(Key, 0);
+    std::pair<KeyT, typename MapType::mapped_type> Pair = std::make_pair(Key, 0);
     std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
-    unsigned &I = Result.first->second;
+    auto &I = Result.first->second;
     if (Result.second) {
       Vector.push_back(std::make_pair(Key, ValueT()));
       I = Vector.size() - 1;
@@ -112,9 +116,9 @@ public:
   }
 
   std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {
-    std::pair<KeyT, unsigned> Pair = std::make_pair(KV.first, 0);
+    std::pair<KeyT, typename MapType::mapped_type> Pair = std::make_pair(KV.first, 0);
     std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
-    unsigned &I = Result.first->second;
+    auto &I = Result.first->second;
     if (Result.second) {
       Vector.push_back(std::make_pair(KV.first, KV.second));
       I = Vector.size() - 1;
@@ -125,9 +129,9 @@ public:
 
   std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) {
     // Copy KV.first into the map, then move it into the vector.
-    std::pair<KeyT, unsigned> Pair = std::make_pair(KV.first, 0);
+    std::pair<KeyT, typename MapType::mapped_type> Pair = std::make_pair(KV.first, 0);
     std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
-    unsigned &I = Result.first->second;
+    auto &I = Result.first->second;
     if (Result.second) {
       Vector.push_back(std::move(KV));
       I = Vector.size() - 1;
@@ -153,14 +157,14 @@ public:
                             (Vector.begin() + Pos->second);
   }
 
-  /// \brief Remove the last element from the vector.
+  /// Remove the last element from the vector.
   void pop_back() {
     typename MapType::iterator Pos = Map.find(Vector.back().first);
     Map.erase(Pos);
     Vector.pop_back();
   }
 
-  /// \brief Remove the element given by Iterator.
+  /// Remove the element given by Iterator.
   ///
   /// Returns an iterator to the element following the one which was removed,
   /// which may be end().
@@ -183,7 +187,7 @@ public:
     return Next;
   }
 
-  /// \brief Remove all elements with the key value Key.
+  /// Remove all elements with the key value Key.
   ///
   /// Returns the number of elements removed.
   size_type erase(const KeyT &Key) {
@@ -194,7 +198,7 @@ public:
     return 1;
   }
 
-  /// \brief Remove the elements that match the predicate.
+  /// Remove the elements that match the predicate.
   ///
   /// Erase all elements that match \c Pred in a single pass.  Takes linear
   /// time.
@@ -223,7 +227,7 @@ void MapVector<KeyT, ValueT, MapType, VectorType>::remove_if(Function Pred) {
   Vector.erase(O, Vector.end());
 }
 
-/// \brief A MapVector that performs no allocations if smaller than a certain
+/// A MapVector that performs no allocations if smaller than a certain
 /// size.
 template <typename KeyT, typename ValueT, unsigned N>
 struct SmallMapVector
diff --git a/include/llvm/ADT/None.h b/include/llvm/ADT/None.h
index c7a99c61994e..4b6bc1e005b5 100644
--- a/include/llvm/ADT/None.h
+++ b/include/llvm/ADT/None.h
@@ -17,7 +17,7 @@
 #define LLVM_ADT_NONE_H
 
 namespace llvm {
-/// \brief A simple null object to allow implicit construction of Optional<T>
+/// A simple null object to allow implicit construction of Optional<T>
 /// and similar types without having to spell out the specialization's name.
 // (constant value 1 in an attempt to workaround MSVC build issue... )
 enum class NoneType { None = 1 };
diff --git a/include/llvm/ADT/Optional.h b/include/llvm/ADT/Optional.h
index 2811d5c1e21b..353e5d0ec9df 100644
--- a/include/llvm/ADT/Optional.h
+++ b/include/llvm/ADT/Optional.h
@@ -27,124 +27,164 @@
 
 namespace llvm {
 
-template <typename T> class Optional {
+namespace optional_detail {
+/// Storage for any type.
+template <typename T, bool IsPodLike> struct OptionalStorage {
   AlignedCharArrayUnion<T> storage;
   bool hasVal = false;
 
-public:
-  using value_type = T;
-
-  Optional(NoneType) {}
-  explicit Optional() {}
-
-  Optional(const T &y) : hasVal(true) { new (storage.buffer) T(y); }
+  OptionalStorage() = default;
 
-  Optional(const Optional &O) : hasVal(O.hasVal) {
+  OptionalStorage(const T &y) : hasVal(true) { new (storage.buffer) T(y); }
+  OptionalStorage(const OptionalStorage &O) : hasVal(O.hasVal) {
     if (hasVal)
-      new (storage.buffer) T(*O);
+      new (storage.buffer) T(*O.getPointer());
   }
-
-  Optional(T &&y) : hasVal(true) { new (storage.buffer) T(std::forward<T>(y)); }
-
-  Optional(Optional<T> &&O) : hasVal(O) {
-    if (O) {
-      new (storage.buffer) T(std::move(*O));
-      O.reset();
+  OptionalStorage(T &&y) : hasVal(true) {
+    new (storage.buffer) T(std::forward<T>(y));
+  }
+  OptionalStorage(OptionalStorage &&O) : hasVal(O.hasVal) {
+    if (O.hasVal) {
+      new (storage.buffer) T(std::move(*O.getPointer()));
     }
   }
 
-  ~Optional() { reset(); }
-
-  Optional &operator=(T &&y) {
+  OptionalStorage &operator=(T &&y) {
     if (hasVal)
-      **this = std::move(y);
+      *getPointer() = std::move(y);
     else {
       new (storage.buffer) T(std::move(y));
       hasVal = true;
     }
     return *this;
   }
-
-  Optional &operator=(Optional &&O) {
-    if (!O)
+  OptionalStorage &operator=(OptionalStorage &&O) {
+    if (!O.hasVal)
       reset();
     else {
-      *this = std::move(*O);
-      O.reset();
+      *this = std::move(*O.getPointer());
     }
     return *this;
   }
 
-  /// Create a new object by constructing it in place with the given arguments.
-  template <typename... ArgTypes> void emplace(ArgTypes &&... Args) {
-    reset();
-    hasVal = true;
-    new (storage.buffer) T(std::forward<ArgTypes>(Args)...);
-  }
-
-  static inline Optional create(const T *y) {
-    return y ? Optional(*y) : Optional();
-  }
-
   // FIXME: these assignments (& the equivalent const T&/const Optional& ctors)
   // could be made more efficient by passing by value, possibly unifying them
   // with the rvalue versions above - but this could place a different set of
   // requirements (notably: the existence of a default ctor) when implemented
   // in that way. Careful SFINAE to avoid such pitfalls would be required.
-  Optional &operator=(const T &y) {
+  OptionalStorage &operator=(const T &y) {
     if (hasVal)
-      **this = y;
+      *getPointer() = y;
     else {
       new (storage.buffer) T(y);
       hasVal = true;
     }
     return *this;
   }
-
-  Optional &operator=(const Optional &O) {
-    if (!O)
+  OptionalStorage &operator=(const OptionalStorage &O) {
+    if (!O.hasVal)
       reset();
     else
-      *this = *O;
+      *this = *O.getPointer();
     return *this;
   }
 
+  ~OptionalStorage() { reset(); }
+
   void reset() {
     if (hasVal) {
-      (**this).~T();
+      (*getPointer()).~T();
       hasVal = false;
     }
   }
 
-  const T *getPointer() const {
-    assert(hasVal);
-    return reinterpret_cast<const T *>(storage.buffer);
-  }
   T *getPointer() {
     assert(hasVal);
     return reinterpret_cast<T *>(storage.buffer);
   }
-  const T &getValue() const LLVM_LVALUE_FUNCTION {
+  const T *getPointer() const {
     assert(hasVal);
-    return *getPointer();
+    return reinterpret_cast<const T *>(storage.buffer);
   }
-  T &getValue() LLVM_LVALUE_FUNCTION {
-    assert(hasVal);
-    return *getPointer();
+};
+
+#if !defined(__GNUC__) || defined(__clang__) // GCC up to GCC7 miscompiles this.
+/// Storage for trivially copyable types only.
+template <typename T> struct OptionalStorage<T, true> {
+  AlignedCharArrayUnion<T> storage;
+  bool hasVal = false;
+
+  OptionalStorage() = default;
+
+  OptionalStorage(const T &y) : hasVal(true) { new (storage.buffer) T(y); }
+  OptionalStorage &operator=(const T &y) {
+    *reinterpret_cast<T *>(storage.buffer) = y;
+    hasVal = true;
+    return *this;
   }
 
-  explicit operator bool() const { return hasVal; }
-  bool hasValue() const { return hasVal; }
-  const T *operator->() const { return getPointer(); }
-  T *operator->() { return getPointer(); }
-  const T &operator*() const LLVM_LVALUE_FUNCTION {
-    assert(hasVal);
-    return *getPointer();
+  void reset() { hasVal = false; }
+};
+#endif
+} // namespace optional_detail
+
+template <typename T> class Optional {
+  optional_detail::OptionalStorage<T, isPodLike<T>::value> Storage;
+
+public:
+  using value_type = T;
+
+  constexpr Optional() {}
+  constexpr Optional(NoneType) {}
+
+  Optional(const T &y) : Storage(y) {}
+  Optional(const Optional &O) = default;
+
+  Optional(T &&y) : Storage(std::forward<T>(y)) {}
+  Optional(Optional &&O) = default;
+
+  Optional &operator=(T &&y) {
+    Storage = std::move(y);
+    return *this;
   }
-  T &operator*() LLVM_LVALUE_FUNCTION {
-    assert(hasVal);
-    return *getPointer();
+  Optional &operator=(Optional &&O) = default;
+
+  /// Create a new object by constructing it in place with the given arguments.
+  template <typename... ArgTypes> void emplace(ArgTypes &&... Args) {
+    reset();
+    Storage.hasVal = true;
+    new (getPointer()) T(std::forward<ArgTypes>(Args)...);
+  }
+
+  static inline Optional create(const T *y) {
+    return y ? Optional(*y) : Optional();
+  }
+
+  Optional &operator=(const T &y) {
+    Storage = y;
+    return *this;
+  }
+  Optional &operator=(const Optional &O) = default;
+
+  void reset() { Storage.reset(); }
+
+  const T *getPointer() const {
+    assert(Storage.hasVal);
+    return reinterpret_cast<const T *>(Storage.storage.buffer);
+  }
+  T *getPointer() {
+    assert(Storage.hasVal);
+    return reinterpret_cast<T *>(Storage.storage.buffer);
   }
+  const T &getValue() const LLVM_LVALUE_FUNCTION { return *getPointer(); }
+  T &getValue() LLVM_LVALUE_FUNCTION { return *getPointer(); }
+
+  explicit operator bool() const { return Storage.hasVal; }
+  bool hasValue() const { return Storage.hasVal; }
+  const T *operator->() const { return getPointer(); }
+  T *operator->() { return getPointer(); }
+  const T &operator*() const LLVM_LVALUE_FUNCTION { return *getPointer(); }
+  T &operator*() LLVM_LVALUE_FUNCTION { return *getPointer(); }
 
   template <typename U>
   constexpr T getValueOr(U &&value) const LLVM_LVALUE_FUNCTION {
@@ -152,14 +192,8 @@ public:
   }
 
 #if LLVM_HAS_RVALUE_REFERENCE_THIS
-  T &&getValue() && {
-    assert(hasVal);
-    return std::move(*getPointer());
-  }
-  T &&operator*() && {
-    assert(hasVal);
-    return std::move(*getPointer());
-  }
+  T &&getValue() && { return std::move(*getPointer()); }
+  T &&operator*() && { return std::move(*getPointer()); }
 
   template <typename U>
   T getValueOr(U &&value) && {
diff --git a/include/llvm/ADT/PackedVector.h b/include/llvm/ADT/PackedVector.h
index 95adc2926813..3d53c49536d0 100644
--- a/include/llvm/ADT/PackedVector.h
+++ b/include/llvm/ADT/PackedVector.h
@@ -65,7 +65,7 @@ protected:
   }
 };
 
-/// \brief Store a vector of values using a specific number of bits for each
+/// Store a vector of values using a specific number of bits for each
 /// value. Both signed and unsigned types can be used, e.g
 /// @code
 ///   PackedVector<signed, 2> vec;
diff --git a/include/llvm/ADT/PointerUnion.h b/include/llvm/ADT/PointerUnion.h
index 4276859e9254..315e58336cba 100644
--- a/include/llvm/ADT/PointerUnion.h
+++ b/include/llvm/ADT/PointerUnion.h
@@ -346,6 +346,12 @@ struct PointerLikeTypeTraits<PointerUnion3<PT1, PT2, PT3>> {
   };
 };
 
+template <typename PT1, typename PT2, typename PT3>
+bool operator<(PointerUnion3<PT1, PT2, PT3> lhs,
+               PointerUnion3<PT1, PT2, PT3> rhs) {
+  return lhs.getOpaqueValue() < rhs.getOpaqueValue();
+}
+
 /// A pointer union of four pointer types. See documentation for PointerUnion
 /// for usage.
 template <typename PT1, typename PT2, typename PT3, typename PT4>
diff --git a/include/llvm/ADT/SCCIterator.h b/include/llvm/ADT/SCCIterator.h
index 784a58dc002f..ab1dc4613be0 100644
--- a/include/llvm/ADT/SCCIterator.h
+++ b/include/llvm/ADT/SCCIterator.h
@@ -33,7 +33,7 @@
 
 namespace llvm {
 
-/// \brief Enumerate the SCCs of a directed graph in reverse topological order
+/// Enumerate the SCCs of a directed graph in reverse topological order
 /// of the SCC DAG.
 ///
 /// This is implemented using Tarjan's DFS algorithm using an internal stack to
@@ -104,7 +104,7 @@ public:
   }
   static scc_iterator end(const GraphT &) { return scc_iterator(); }
 
-  /// \brief Direct loop termination test which is more efficient than
+  /// Direct loop termination test which is more efficient than
   /// comparison with \c end().
   bool isAtEnd() const {
     assert(!CurrentSCC.empty() || VisitStack.empty());
@@ -125,7 +125,7 @@ public:
     return CurrentSCC;
   }
 
-  /// \brief Test if the current SCC has a loop.
+  /// Test if the current SCC has a loop.
   ///
   /// If the SCC has more than one node, this is trivially true.  If not, it may
   /// still contain a loop if the node has an edge back to itself.
@@ -222,12 +222,12 @@ bool scc_iterator<GraphT, GT>::hasLoop() const {
     return false;
   }
 
-/// \brief Construct the begin iterator for a deduced graph type T.
+/// Construct the begin iterator for a deduced graph type T.
 template <class T> scc_iterator<T> scc_begin(const T &G) {
   return scc_iterator<T>::begin(G);
 }
 
-/// \brief Construct the end iterator for a deduced graph type T.
+/// Construct the end iterator for a deduced graph type T.
 template <class T> scc_iterator<T> scc_end(const T &G) {
   return scc_iterator<T>::end(G);
 }
diff --git a/include/llvm/ADT/STLExtras.h b/include/llvm/ADT/STLExtras.h
index bcd992b4a716..94365dd9ced1 100644
--- a/include/llvm/ADT/STLExtras.h
+++ b/include/llvm/ADT/STLExtras.h
@@ -36,6 +36,10 @@
 #include <type_traits>
 #include <utility>
 
+#ifdef EXPENSIVE_CHECKS
+#include <random> // for std::mt19937
+#endif
+
 namespace llvm {
 
 // Only used by compiler if both template types are the same.  Useful when
@@ -54,6 +58,19 @@ using ValueOfRange = typename std::remove_reference<decltype(
 } // end namespace detail
 
 //===----------------------------------------------------------------------===//
+//     Extra additions to <type_traits>
+//===----------------------------------------------------------------------===//
+
+template <typename T>
+struct negation : std::integral_constant<bool, !bool(T::value)> {};
+
+template <typename...> struct conjunction : std::true_type {};
+template <typename B1> struct conjunction<B1> : B1 {};
+template <typename B1, typename... Bn>
+struct conjunction<B1, Bn...>
+    : std::conditional<bool(B1::value), conjunction<Bn...>, B1>::type {};
+
+//===----------------------------------------------------------------------===//
 //     Extra additions to <functional>
 //===----------------------------------------------------------------------===//
 
@@ -101,6 +118,7 @@ class function_ref<Ret(Params...)> {
 
 public:
   function_ref() = default;
+  function_ref(std::nullptr_t) {}
 
   template <typename Callable>
   function_ref(Callable &&callable,
@@ -266,60 +284,121 @@ auto reverse(
 ///   auto R = make_filter_range(A, [](int N) { return N % 2 == 1; });
 ///   // R contains { 1, 3 }.
 /// \endcode
-template <typename WrappedIteratorT, typename PredicateT>
-class filter_iterator
+///
+/// Note: filter_iterator_base implements support for forward iteration.
+/// filter_iterator_impl exists to provide support for bidirectional iteration,
+/// conditional on whether the wrapped iterator supports it.
+template <typename WrappedIteratorT, typename PredicateT, typename IterTag>
+class filter_iterator_base
     : public iterator_adaptor_base<
-          filter_iterator<WrappedIteratorT, PredicateT>, WrappedIteratorT,
+          filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>,
+          WrappedIteratorT,
           typename std::common_type<
-              std::forward_iterator_tag,
-              typename std::iterator_traits<
-                  WrappedIteratorT>::iterator_category>::type> {
+              IterTag, typename std::iterator_traits<
+                           WrappedIteratorT>::iterator_category>::type> {
   using BaseT = iterator_adaptor_base<
-      filter_iterator<WrappedIteratorT, PredicateT>, WrappedIteratorT,
+      filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>,
+      WrappedIteratorT,
       typename std::common_type<
-          std::forward_iterator_tag,
-          typename std::iterator_traits<WrappedIteratorT>::iterator_category>::
-          type>;
+          IterTag, typename std::iterator_traits<
+                       WrappedIteratorT>::iterator_category>::type>;
 
-  struct PayloadType {
-    WrappedIteratorT End;
-    PredicateT Pred;
-  };
-
-  Optional<PayloadType> Payload;
+protected:
+  WrappedIteratorT End;
+  PredicateT Pred;
 
   void findNextValid() {
-    assert(Payload && "Payload should be engaged when findNextValid is called");
-    while (this->I != Payload->End && !Payload->Pred(*this->I))
+    while (this->I != End && !Pred(*this->I))
       BaseT::operator++();
   }
 
-  // Construct the begin iterator. The begin iterator requires to know where end
-  // is, so that it can properly stop when it hits end.
-  filter_iterator(WrappedIteratorT Begin, WrappedIteratorT End, PredicateT Pred)
-      : BaseT(std::move(Begin)),
-        Payload(PayloadType{std::move(End), std::move(Pred)}) {
+  // Construct the iterator. The begin iterator needs to know where the end
+  // is, so that it can properly stop when it gets there. The end iterator only
+  // needs the predicate to support bidirectional iteration.
+  filter_iterator_base(WrappedIteratorT Begin, WrappedIteratorT End,
+                       PredicateT Pred)
+      : BaseT(Begin), End(End), Pred(Pred) {
     findNextValid();
   }
 
-  // Construct the end iterator. It's not incrementable, so Payload doesn't
-  // have to be engaged.
-  filter_iterator(WrappedIteratorT End) : BaseT(End) {}
-
 public:
   using BaseT::operator++;
 
-  filter_iterator &operator++() {
+  filter_iterator_base &operator++() {
     BaseT::operator++();
     findNextValid();
     return *this;
   }
+};
+
+/// Specialization of filter_iterator_base for forward iteration only.
+template <typename WrappedIteratorT, typename PredicateT,
+          typename IterTag = std::forward_iterator_tag>
+class filter_iterator_impl
+    : public filter_iterator_base<WrappedIteratorT, PredicateT, IterTag> {
+  using BaseT = filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>;
+
+public:
+  filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End,
+                       PredicateT Pred)
+      : BaseT(Begin, End, Pred) {}
+};
+
+/// Specialization of filter_iterator_base for bidirectional iteration.
+template <typename WrappedIteratorT, typename PredicateT>
+class filter_iterator_impl<WrappedIteratorT, PredicateT,
+                           std::bidirectional_iterator_tag>
+    : public filter_iterator_base<WrappedIteratorT, PredicateT,
+                                  std::bidirectional_iterator_tag> {
+  using BaseT = filter_iterator_base<WrappedIteratorT, PredicateT,
+                                     std::bidirectional_iterator_tag>;
+  void findPrevValid() {
+    while (!this->Pred(*this->I))
+      BaseT::operator--();
+  }
+
+public:
+  using BaseT::operator--;
+
+  filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End,
+                       PredicateT Pred)
+      : BaseT(Begin, End, Pred) {}
+
+  filter_iterator_impl &operator--() {
+    BaseT::operator--();
+    findPrevValid();
+    return *this;
+  }
+};
+
+namespace detail {
 
-  template <typename RT, typename PT>
-  friend iterator_range<filter_iterator<detail::IterOfRange<RT>, PT>>
-  make_filter_range(RT &&, PT);
+template <bool is_bidirectional> struct fwd_or_bidi_tag_impl {
+  using type = std::forward_iterator_tag;
 };
 
+template <> struct fwd_or_bidi_tag_impl<true> {
+  using type = std::bidirectional_iterator_tag;
+};
+
+/// Helper which sets its type member to forward_iterator_tag if the category
+/// of \p IterT does not derive from bidirectional_iterator_tag, and to
+/// bidirectional_iterator_tag otherwise.
+template <typename IterT> struct fwd_or_bidi_tag {
+  using type = typename fwd_or_bidi_tag_impl<std::is_base_of<
+      std::bidirectional_iterator_tag,
+      typename std::iterator_traits<IterT>::iterator_category>::value>::type;
+};
+
+} // namespace detail
+
+/// Defines filter_iterator to a suitable specialization of
+/// filter_iterator_impl, based on the underlying iterator's category.
+template <typename WrappedIteratorT, typename PredicateT>
+using filter_iterator = filter_iterator_impl<
+    WrappedIteratorT, PredicateT,
+    typename detail::fwd_or_bidi_tag<WrappedIteratorT>::type>;
+
 /// Convenience function that takes a range of elements and a predicate,
 /// and return a new filter_iterator range.
 ///
@@ -332,10 +411,11 @@ iterator_range<filter_iterator<detail::IterOfRange<RangeT>, PredicateT>>
 make_filter_range(RangeT &&Range, PredicateT Pred) {
   using FilterIteratorT =
       filter_iterator<detail::IterOfRange<RangeT>, PredicateT>;
-  return make_range(FilterIteratorT(std::begin(std::forward<RangeT>(Range)),
-                                    std::end(std::forward<RangeT>(Range)),
-                                    std::move(Pred)),
-                    FilterIteratorT(std::end(std::forward<RangeT>(Range))));
+  return make_range(
+      FilterIteratorT(std::begin(std::forward<RangeT>(Range)),
+                      std::end(std::forward<RangeT>(Range)), Pred),
+      FilterIteratorT(std::end(std::forward<RangeT>(Range)),
+                      std::end(std::forward<RangeT>(Range)), Pred));
 }
 
 // forward declarations required by zip_shortest/zip_first
@@ -644,7 +724,7 @@ detail::concat_range<ValueT, RangeTs...> concat(RangeTs &&... Ranges) {
 //     Extra additions to <utility>
 //===----------------------------------------------------------------------===//
 
-/// \brief Function object to check whether the first component of a std::pair
+/// Function object to check whether the first component of a std::pair
 /// compares less than the first component of another std::pair.
 struct less_first {
   template <typename T> bool operator()(const T &lhs, const T &rhs) const {
@@ -652,7 +732,7 @@ struct less_first {
   }
 };
 
-/// \brief Function object to check whether the second component of a std::pair
+/// Function object to check whether the second component of a std::pair
 /// compares less than the second component of another std::pair.
 struct less_second {
   template <typename T> bool operator()(const T &lhs, const T &rhs) const {
@@ -662,14 +742,14 @@ struct less_second {
 
 // A subset of N3658. More stuff can be added as-needed.
 
-/// \brief Represents a compile-time sequence of integers.
+/// Represents a compile-time sequence of integers.
 template <class T, T... I> struct integer_sequence {
   using value_type = T;
 
   static constexpr size_t size() { return sizeof...(I); }
 };
 
-/// \brief Alias for the common case of a sequence of size_ts.
+/// Alias for the common case of a sequence of size_ts.
 template <size_t... I>
 struct index_sequence : integer_sequence<std::size_t, I...> {};
 
@@ -678,7 +758,7 @@ struct build_index_impl : build_index_impl<N - 1, N - 1, I...> {};
 template <std::size_t... I>
 struct build_index_impl<0, I...> : index_sequence<I...> {};
 
-/// \brief Creates a compile-time integer sequence for a parameter pack.
+/// Creates a compile-time integer sequence for a parameter pack.
 template <class... Ts>
 struct index_sequence_for : build_index_impl<sizeof...(Ts)> {};
 
@@ -687,7 +767,7 @@ struct index_sequence_for : build_index_impl<sizeof...(Ts)> {};
 template <int N> struct rank : rank<N - 1> {};
 template <> struct rank<0> {};
 
-/// \brief traits class for checking whether type T is one of any of the given
+/// traits class for checking whether type T is one of any of the given
 /// types in the variadic list.
 template <typename T, typename... Ts> struct is_one_of {
   static const bool value = false;
@@ -699,7 +779,7 @@ struct is_one_of<T, U, Ts...> {
       std::is_same<T, U>::value || is_one_of<T, Ts...>::value;
 };
 
-/// \brief traits class for checking whether type T is a base class for all
+/// traits class for checking whether type T is a base class for all
 ///  the given types in the variadic list.
 template <typename T, typename... Ts> struct are_base_of {
   static const bool value = true;
@@ -761,6 +841,10 @@ inline void array_pod_sort(IteratorTy Start, IteratorTy End) {
   // behavior with an empty sequence.
   auto NElts = End - Start;
   if (NElts <= 1) return;
+#ifdef EXPENSIVE_CHECKS
+  std::mt19937 Generator(std::random_device{}());
+  std::shuffle(Start, End, Generator);
+#endif
   qsort(&*Start, NElts, sizeof(*Start), get_array_pod_sort_comparator(*Start));
 }
 
@@ -774,10 +858,34 @@ inline void array_pod_sort(
   // behavior with an empty sequence.
   auto NElts = End - Start;
   if (NElts <= 1) return;
+#ifdef EXPENSIVE_CHECKS
+  std::mt19937 Generator(std::random_device{}());
+  std::shuffle(Start, End, Generator);
+#endif
   qsort(&*Start, NElts, sizeof(*Start),
         reinterpret_cast<int (*)(const void *, const void *)>(Compare));
 }
 
+// Provide wrappers to std::sort which shuffle the elements before sorting
+// to help uncover non-deterministic behavior (PR35135).
+template <typename IteratorTy>
+inline void sort(IteratorTy Start, IteratorTy End) {
+#ifdef EXPENSIVE_CHECKS
+  std::mt19937 Generator(std::random_device{}());
+  std::shuffle(Start, End, Generator);
+#endif
+  std::sort(Start, End);
+}
+
+template <typename IteratorTy, typename Compare>
+inline void sort(IteratorTy Start, IteratorTy End, Compare Comp) {
+#ifdef EXPENSIVE_CHECKS
+  std::mt19937 Generator(std::random_device{}());
+  std::shuffle(Start, End, Generator);
+#endif
+  std::sort(Start, End, Comp);
+}
+
 //===----------------------------------------------------------------------===//
 //     Extra additions to <algorithm>
 //===----------------------------------------------------------------------===//
@@ -861,6 +969,11 @@ OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P) {
   return std::copy_if(adl_begin(Range), adl_end(Range), Out, P);
 }
 
+template <typename R, typename OutputIt>
+OutputIt copy(R &&Range, OutputIt Out) {
+  return std::copy(adl_begin(Range), adl_end(Range), Out);
+}
+
 /// Wrapper function around std::find to detect if an element exists
 /// in a container.
 template <typename R, typename E>
@@ -905,7 +1018,7 @@ auto lower_bound(R &&Range, ForwardIt I) -> decltype(adl_begin(Range)) {
   return std::lower_bound(adl_begin(Range), adl_end(Range), I);
 }
 
-/// \brief Given a range of type R, iterate the entire range and return a
+/// Given a range of type R, iterate the entire range and return a
 /// SmallVector with elements of the vector.  This is useful, for example,
 /// when you want to iterate a range and then sort the results.
 template <unsigned Size, typename R>
@@ -926,13 +1039,25 @@ void erase_if(Container &C, UnaryPredicate P) {
   C.erase(remove_if(C, P), C.end());
 }
 
+/// Get the size of a range. This is a wrapper function around std::distance
+/// which is only enabled when the operation is O(1).
+template <typename R>
+auto size(R &&Range, typename std::enable_if<
+                         std::is_same<typename std::iterator_traits<decltype(
+                                          Range.begin())>::iterator_category,
+                                      std::random_access_iterator_tag>::value,
+                         void>::type * = nullptr)
+    -> decltype(std::distance(Range.begin(), Range.end())) {
+  return std::distance(Range.begin(), Range.end());
+}
+
 //===----------------------------------------------------------------------===//
 //     Extra additions to <memory>
 //===----------------------------------------------------------------------===//
 
 // Implement make_unique according to N3656.
 
-/// \brief Constructs a `new T()` with the given args and returns a
+/// Constructs a `new T()` with the given args and returns a
 ///        `unique_ptr<T>` which owns the object.
 ///
 /// Example:
@@ -945,7 +1070,7 @@ make_unique(Args &&... args) {
   return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
 }
 
-/// \brief Constructs a `new T[n]` with the given args and returns a
+/// Constructs a `new T[n]` with the given args and returns a
 ///        `unique_ptr<T[]>` which owns the object.
 ///
 /// \param n size of the new array.
diff --git a/include/llvm/ADT/ScopeExit.h b/include/llvm/ADT/ScopeExit.h
index 4e64352c77df..bd13755fa999 100644
--- a/include/llvm/ADT/ScopeExit.h
+++ b/include/llvm/ADT/ScopeExit.h
@@ -25,14 +25,26 @@ namespace detail {
 
 template <typename Callable> class scope_exit {
   Callable ExitFunction;
+  bool Engaged = true; // False once moved-from or release()d.
 
 public:
   template <typename Fp>
   explicit scope_exit(Fp &&F) : ExitFunction(std::forward<Fp>(F)) {}
 
-  scope_exit(scope_exit &&Rhs) : ExitFunction(std::move(Rhs.ExitFunction)) {}
+  scope_exit(scope_exit &&Rhs)
+      : ExitFunction(std::move(Rhs.ExitFunction)), Engaged(Rhs.Engaged) {
+    Rhs.release();
+  }
+  scope_exit(const scope_exit &) = delete;
+  scope_exit &operator=(scope_exit &&) = delete;
+  scope_exit &operator=(const scope_exit &) = delete;
 
-  ~scope_exit() { ExitFunction(); }
+  void release() { Engaged = false; }
+
+  ~scope_exit() {
+    if (Engaged)
+      ExitFunction();
+  }
 };
 
 } // end namespace detail
diff --git a/include/llvm/ADT/SetVector.h b/include/llvm/ADT/SetVector.h
index 04ed52fc543f..3d6781041320 100644
--- a/include/llvm/ADT/SetVector.h
+++ b/include/llvm/ADT/SetVector.h
@@ -31,7 +31,7 @@
 
 namespace llvm {
 
-/// \brief A vector that has set insertion semantics.
+/// A vector that has set insertion semantics.
 ///
 /// This adapter class provides a way to keep a set of things that also has the
 /// property of a deterministic iteration order. The order of iteration is the
@@ -52,10 +52,10 @@ public:
   using const_reverse_iterator = typename vector_type::const_reverse_iterator;
   using size_type = typename vector_type::size_type;
 
-  /// \brief Construct an empty SetVector
+  /// Construct an empty SetVector
   SetVector() = default;
 
-  /// \brief Initialize a SetVector with a range of elements
+  /// Initialize a SetVector with a range of elements
   template<typename It>
   SetVector(It Start, It End) {
     insert(Start, End);
@@ -69,75 +69,75 @@ public:
     return std::move(vector_);
   }
 
-  /// \brief Determine if the SetVector is empty or not.
+  /// Determine if the SetVector is empty or not.
   bool empty() const {
     return vector_.empty();
   }
 
-  /// \brief Determine the number of elements in the SetVector.
+  /// Determine the number of elements in the SetVector.
   size_type size() const {
     return vector_.size();
   }
 
-  /// \brief Get an iterator to the beginning of the SetVector.
+  /// Get an iterator to the beginning of the SetVector.
   iterator begin() {
     return vector_.begin();
   }
 
-  /// \brief Get a const_iterator to the beginning of the SetVector.
+  /// Get a const_iterator to the beginning of the SetVector.
   const_iterator begin() const {
     return vector_.begin();
   }
 
-  /// \brief Get an iterator to the end of the SetVector.
+  /// Get an iterator to the end of the SetVector.
   iterator end() {
     return vector_.end();
   }
 
-  /// \brief Get a const_iterator to the end of the SetVector.
+  /// Get a const_iterator to the end of the SetVector.
   const_iterator end() const {
     return vector_.end();
   }
 
-  /// \brief Get an reverse_iterator to the end of the SetVector.
+  /// Get an reverse_iterator to the end of the SetVector.
   reverse_iterator rbegin() {
     return vector_.rbegin();
   }
 
-  /// \brief Get a const_reverse_iterator to the end of the SetVector.
+  /// Get a const_reverse_iterator to the end of the SetVector.
   const_reverse_iterator rbegin() const {
     return vector_.rbegin();
   }
 
-  /// \brief Get a reverse_iterator to the beginning of the SetVector.
+  /// Get a reverse_iterator to the beginning of the SetVector.
   reverse_iterator rend() {
     return vector_.rend();
   }
 
-  /// \brief Get a const_reverse_iterator to the beginning of the SetVector.
+  /// Get a const_reverse_iterator to the beginning of the SetVector.
   const_reverse_iterator rend() const {
     return vector_.rend();
   }
 
-  /// \brief Return the first element of the SetVector.
+  /// Return the first element of the SetVector.
   const T &front() const {
     assert(!empty() && "Cannot call front() on empty SetVector!");
     return vector_.front();
   }
 
-  /// \brief Return the last element of the SetVector.
+  /// Return the last element of the SetVector.
   const T &back() const {
     assert(!empty() && "Cannot call back() on empty SetVector!");
     return vector_.back();
   }
 
-  /// \brief Index into the SetVector.
+  /// Index into the SetVector.
   const_reference operator[](size_type n) const {
     assert(n < vector_.size() && "SetVector access out of range!");
     return vector_[n];
   }
 
-  /// \brief Insert a new element into the SetVector.
+  /// Insert a new element into the SetVector.
   /// \returns true if the element was inserted into the SetVector.
   bool insert(const value_type &X) {
     bool result = set_.insert(X).second;
@@ -146,7 +146,7 @@ public:
     return result;
   }
 
-  /// \brief Insert a range of elements into the SetVector.
+  /// Insert a range of elements into the SetVector.
   template<typename It>
   void insert(It Start, It End) {
     for (; Start != End; ++Start)
@@ -154,7 +154,7 @@ public:
         vector_.push_back(*Start);
   }
 
-  /// \brief Remove an item from the set vector.
+  /// Remove an item from the set vector.
   bool remove(const value_type& X) {
     if (set_.erase(X)) {
       typename vector_type::iterator I = find(vector_, X);
@@ -183,7 +183,7 @@ public:
     return vector_.erase(NI);
   }
 
-  /// \brief Remove items from the set vector based on a predicate function.
+  /// Remove items from the set vector based on a predicate function.
   ///
   /// This is intended to be equivalent to the following code, if we could
   /// write it:
@@ -206,19 +206,19 @@ public:
     return true;
   }
 
-  /// \brief Count the number of elements of a given key in the SetVector.
+  /// Count the number of elements of a given key in the SetVector.
   /// \returns 0 if the element is not in the SetVector, 1 if it is.
   size_type count(const key_type &key) const {
     return set_.count(key);
   }
 
-  /// \brief Completely clear the SetVector
+  /// Completely clear the SetVector
   void clear() {
     set_.clear();
     vector_.clear();
   }
 
-  /// \brief Remove the last element of the SetVector.
+  /// Remove the last element of the SetVector.
   void pop_back() {
     assert(!empty() && "Cannot remove an element from an empty SetVector!");
     set_.erase(back());
@@ -239,7 +239,7 @@ public:
     return vector_ != that.vector_;
   }
 
-  /// \brief Compute This := This u S, return whether 'This' changed.
+  /// Compute This := This u S, return whether 'This' changed.
   /// TODO: We should be able to use set_union from SetOperations.h, but
   ///       SetVector interface is inconsistent with DenseSet.
   template <class STy>
@@ -254,7 +254,7 @@ public:
     return Changed;
   }
 
-  /// \brief Compute This := This - B
+  /// Compute This := This - B
   /// TODO: We should be able to use set_subtract from SetOperations.h, but
   ///       SetVector interface is inconsistent with DenseSet.
   template <class STy>
@@ -265,7 +265,7 @@ public:
   }
 
 private:
-  /// \brief A wrapper predicate designed for use with std::remove_if.
+  /// A wrapper predicate designed for use with std::remove_if.
   ///
   /// This predicate wraps a predicate suitable for use with std::remove_if to
   /// call set_.erase(x) on each element which is slated for removal.
@@ -292,7 +292,7 @@ private:
   vector_type vector_;   ///< The vector.
 };
 
-/// \brief A SetVector that performs no allocations if smaller than
+/// A SetVector that performs no allocations if smaller than
 /// a certain size.
 template <typename T, unsigned N>
 class SmallSetVector
@@ -300,7 +300,7 @@ class SmallSetVector
 public:
   SmallSetVector() = default;
 
-  /// \brief Initialize a SmallSetVector with a range of elements
+  /// Initialize a SmallSetVector with a range of elements
   template<typename It>
   SmallSetVector(It Start, It End) {
     this->insert(Start, End);
diff --git a/include/llvm/ADT/SmallPtrSet.h b/include/llvm/ADT/SmallPtrSet.h
index 78ea613af693..db08e40257ba 100644
--- a/include/llvm/ADT/SmallPtrSet.h
+++ b/include/llvm/ADT/SmallPtrSet.h
@@ -335,7 +335,7 @@ struct RoundUpToPowerOfTwo {
   enum { Val = RoundUpToPowerOfTwoH<N, (N&(N-1)) == 0>::Val };
 };
 
-/// \brief A templated base class for \c SmallPtrSet which provides the
+/// A templated base class for \c SmallPtrSet which provides the
 /// typesafe interface that is common across all small sizes.
 ///
 /// This is particularly useful for passing around between interface boundaries
diff --git a/include/llvm/ADT/SmallSet.h b/include/llvm/ADT/SmallSet.h
index d52d0f07f9a6..5d84627714bc 100644
--- a/include/llvm/ADT/SmallSet.h
+++ b/include/llvm/ADT/SmallSet.h
@@ -17,21 +17,120 @@
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/iterator.h"
 #include "llvm/Support/Compiler.h"
+#include "llvm/Support/type_traits.h"
 #include <cstddef>
 #include <functional>
 #include <set>
+#include <type_traits>
 #include <utility>
 
 namespace llvm {
 
+/// SmallSetIterator - This class implements a const_iterator for SmallSet by
+/// delegating to the underlying SmallVector or Set iterators.
+template <typename T, unsigned N, typename C>
+class SmallSetIterator
+    : public iterator_facade_base<SmallSetIterator<T, N, C>,
+                                  std::forward_iterator_tag, T> {
+private:
+  using SetIterTy = typename std::set<T, C>::const_iterator;
+  using VecIterTy = typename SmallVector<T, N>::const_iterator;
+  using SelfTy = SmallSetIterator<T, N, C>;
+
+  /// Iterators to the parts of the SmallSet containing the data. They are set
+  /// depending on isSmall.
+  union {
+    SetIterTy SetIter;
+    VecIterTy VecIter;
+  };
+
+  bool isSmall;
+
+public:
+  SmallSetIterator(SetIterTy SetIter) : SetIter(SetIter), isSmall(false) {}
+
+  SmallSetIterator(VecIterTy VecIter) : VecIter(VecIter), isSmall(true) {}
+
+  // Spell out destructor, copy/move constructor and assignment operators for
+  // MSVC STL, where set<T>::const_iterator is not trivially copy constructible.
+  ~SmallSetIterator() {
+    if (isSmall)
+      VecIter.~VecIterTy();
+    else
+      SetIter.~SetIterTy();
+  }
+
+  SmallSetIterator(const SmallSetIterator &Other) : isSmall(Other.isSmall) {
+    if (isSmall)
+      VecIter = Other.VecIter;
+    else
+      // Use placement new, to make sure SetIter is properly constructed, even
+      // if it is not trivially copy-able (e.g. in MSVC).
+      new (&SetIter) SetIterTy(Other.SetIter);
+  }
+
+  SmallSetIterator(SmallSetIterator &&Other) : isSmall(Other.isSmall) {
+    if (isSmall)
+      VecIter = std::move(Other.VecIter);
+    else
+      // Use placement new, to make sure SetIter is properly constructed, even
+      // if it is not trivially copy-able (e.g. in MSVC).
+      new (&SetIter) SetIterTy(std::move(Other.SetIter));
+  }
+
+  SmallSetIterator& operator=(const SmallSetIterator& Other) {
+    // Call destructor for SetIter, so it gets properly destroyed if it is
+    // not trivially destructible in case we are setting VecIter.
+    if (!isSmall)
+      SetIter.~SetIterTy();
+
+    isSmall = Other.isSmall;
+    if (isSmall)
+      VecIter = Other.VecIter;
+    else
+      new (&SetIter) SetIterTy(Other.SetIter);
+    return *this;
+  }
+
+  SmallSetIterator& operator=(SmallSetIterator&& Other) {
+    // Call destructor for SetIter, so it gets properly destroyed if it is
+    // not trivially destructible in case we are setting VecIter.
+    if (!isSmall)
+      SetIter.~SetIterTy();
+
+    isSmall = Other.isSmall;
+    if (isSmall)
+      VecIter = std::move(Other.VecIter);
+    else
+      new (&SetIter) SetIterTy(std::move(Other.SetIter));
+    return *this;
+  }
+
+  bool operator==(const SmallSetIterator &RHS) const {
+    if (isSmall != RHS.isSmall)
+      return false;
+    if (isSmall)
+      return VecIter == RHS.VecIter;
+    return SetIter == RHS.SetIter;
+  }
+
+  SmallSetIterator &operator++() { // Preincrement
+    if (isSmall)
+      VecIter++;
+    else
+      SetIter++;
+    return *this;
+  }
+
+  const T &operator*() const { return isSmall ? *VecIter : *SetIter; }
+};
+
 /// SmallSet - This maintains a set of unique values, optimizing for the case
 /// when the set is small (less than N).  In this case, the set can be
 /// maintained with no mallocs.  If the set gets large, we expand to using an
 /// std::set to maintain reasonable lookup times.
-///
-/// Note that this set does not provide a way to iterate over members in the
-/// set.
 template <typename T, unsigned N, typename C = std::less<T>>
 class SmallSet {
   /// Use a SmallVector to hold the elements here (even though it will never
@@ -50,6 +149,7 @@ class SmallSet {
 
 public:
   using size_type = size_t;
+  using const_iterator = SmallSetIterator<T, N, C>;
 
   SmallSet() = default;
 
@@ -121,6 +221,18 @@ public:
     Set.clear();
   }
 
+  const_iterator begin() const {
+    if (isSmall())
+      return {Vector.begin()};
+    return {Set.begin()};
+  }
+
+  const_iterator end() const {
+    if (isSmall())
+      return {Vector.end()};
+    return {Set.end()};
+  }
+
 private:
   bool isSmall() const { return Set.empty(); }
 
diff --git a/include/llvm/ADT/SmallVector.h b/include/llvm/ADT/SmallVector.h
index a9ac98d1ad4c..acb4426b4f45 100644
--- a/include/llvm/ADT/SmallVector.h
+++ b/include/llvm/ADT/SmallVector.h
@@ -18,6 +18,7 @@
 #include "llvm/Support/AlignOf.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/MathExtras.h"
+#include "llvm/Support/MemAlloc.h"
 #include "llvm/Support/type_traits.h"
 #include "llvm/Support/ErrorHandling.h"
 #include <algorithm>
@@ -37,28 +38,42 @@ namespace llvm {
 /// This is all the non-templated stuff common to all SmallVectors.
 class SmallVectorBase {
 protected:
-  void *BeginX, *EndX, *CapacityX;
+  void *BeginX;
+  unsigned Size = 0, Capacity;
 
-protected:
-  SmallVectorBase(void *FirstEl, size_t Size)
-    : BeginX(FirstEl), EndX(FirstEl), CapacityX((char*)FirstEl+Size) {}
+  SmallVectorBase() = delete;
+  SmallVectorBase(void *FirstEl, size_t Capacity)
+      : BeginX(FirstEl), Capacity(Capacity) {}
 
   /// This is an implementation of the grow() method which only works
   /// on POD-like data types and is out of line to reduce code duplication.
-  void grow_pod(void *FirstEl, size_t MinSizeInBytes, size_t TSize);
+  void grow_pod(void *FirstEl, size_t MinCapacity, size_t TSize);
 
 public:
-  /// This returns size()*sizeof(T).
-  size_t size_in_bytes() const {
-    return size_t((char*)EndX - (char*)BeginX);
-  }
+  size_t size() const { return Size; }
+  size_t capacity() const { return Capacity; }
+
+  LLVM_NODISCARD bool empty() const { return !Size; }
 
-  /// capacity_in_bytes - This returns capacity()*sizeof(T).
-  size_t capacity_in_bytes() const {
-    return size_t((char*)CapacityX - (char*)BeginX);
+  /// Set the array size to \p N, which the current array must have enough
+  /// capacity for.
+  ///
+  /// This does not construct or destroy any elements in the vector.
+  ///
+  /// Clients can use this in conjunction with capacity() to write past the end
+  /// of the buffer when they know that more elements are available, and only
+  /// update the size later. This avoids the cost of value initializing elements
+  /// which will only be overwritten.
+  void set_size(size_t Size) {
+    assert(Size <= capacity());
+    this->Size = Size;
   }
+};
 
-  LLVM_NODISCARD bool empty() const { return BeginX == EndX; }
+/// Figure out the offset of the first element.
+template <class T, typename = void> struct SmallVectorAlignmentAndSize {
+  AlignedCharArrayUnion<SmallVectorBase> Base;
+  AlignedCharArrayUnion<T> FirstEl;
 };
 
 /// This is the part of SmallVectorTemplateBase which does not depend on whether
@@ -66,36 +81,34 @@ public:
 /// to avoid unnecessarily requiring T to be complete.
 template <typename T, typename = void>
 class SmallVectorTemplateCommon : public SmallVectorBase {
-private:
-  template <typename, unsigned> friend struct SmallVectorStorage;
-
-  // Allocate raw space for N elements of type T.  If T has a ctor or dtor, we
-  // don't want it to be automatically run, so we need to represent the space as
-  // something else.  Use an array of char of sufficient alignment.
-  using U = AlignedCharArrayUnion<T>;
-  U FirstEl;
+  /// Find the address of the first element.  For this pointer math to be valid
+  /// with small-size of 0 for T with lots of alignment, it's important that
+  /// SmallVectorStorage is properly-aligned even for small-size of 0.
+  void *getFirstEl() const {
+    return const_cast<void *>(reinterpret_cast<const void *>(
+        reinterpret_cast<const char *>(this) +
+        offsetof(SmallVectorAlignmentAndSize<T>, FirstEl)));
+  }
   // Space after 'FirstEl' is clobbered, do not add any instance vars after it.
 
 protected:
-  SmallVectorTemplateCommon(size_t Size) : SmallVectorBase(&FirstEl, Size) {}
+  SmallVectorTemplateCommon(size_t Size)
+      : SmallVectorBase(getFirstEl(), Size) {}
 
-  void grow_pod(size_t MinSizeInBytes, size_t TSize) {
-    SmallVectorBase::grow_pod(&FirstEl, MinSizeInBytes, TSize);
+  void grow_pod(size_t MinCapacity, size_t TSize) {
+    SmallVectorBase::grow_pod(getFirstEl(), MinCapacity, TSize);
   }
 
   /// Return true if this is a smallvector which has not had dynamic
   /// memory allocated for it.
-  bool isSmall() const {
-    return BeginX == static_cast<const void*>(&FirstEl);
-  }
+  bool isSmall() const { return BeginX == getFirstEl(); }
 
   /// Put this vector in a state of being small.
   void resetToSmall() {
-    BeginX = EndX = CapacityX = &FirstEl;
+    BeginX = getFirstEl();
+    Size = Capacity = 0; // FIXME: Setting Capacity to 0 is suspect.
   }
 
-  void setEnd(T *P) { this->EndX = P; }
-
 public:
   using size_type = size_t;
   using difference_type = ptrdiff_t;
@@ -117,27 +130,20 @@ public:
   LLVM_ATTRIBUTE_ALWAYS_INLINE
   const_iterator begin() const { return (const_iterator)this->BeginX; }
   LLVM_ATTRIBUTE_ALWAYS_INLINE
-  iterator end() { return (iterator)this->EndX; }
+  iterator end() { return begin() + size(); }
   LLVM_ATTRIBUTE_ALWAYS_INLINE
-  const_iterator end() const { return (const_iterator)this->EndX; }
-
-protected:
-  iterator capacity_ptr() { return (iterator)this->CapacityX; }
-  const_iterator capacity_ptr() const { return (const_iterator)this->CapacityX;}
+  const_iterator end() const { return begin() + size(); }
 
-public:
   // reverse iterator creation methods.
   reverse_iterator rbegin()            { return reverse_iterator(end()); }
   const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); }
   reverse_iterator rend()              { return reverse_iterator(begin()); }
   const_reverse_iterator rend() const { return const_reverse_iterator(begin());}
 
-  LLVM_ATTRIBUTE_ALWAYS_INLINE
-  size_type size() const { return end()-begin(); }
+  size_type size_in_bytes() const { return size() * sizeof(T); }
   size_type max_size() const { return size_type(-1) / sizeof(T); }
 
-  /// Return the total number of elements in the currently allocated buffer.
-  size_t capacity() const { return capacity_ptr() - begin(); }
+  size_t capacity_in_bytes() const { return capacity() * sizeof(T); }
 
   /// Return a pointer to the vector's buffer, even if empty().
   pointer data() { return pointer(begin()); }
@@ -210,21 +216,21 @@ protected:
 
 public:
   void push_back(const T &Elt) {
-    if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
+    if (LLVM_UNLIKELY(this->size() >= this->capacity()))
       this->grow();
     ::new ((void*) this->end()) T(Elt);
-    this->setEnd(this->end()+1);
+    this->set_size(this->size() + 1);
   }
 
   void push_back(T &&Elt) {
-    if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
+    if (LLVM_UNLIKELY(this->size() >= this->capacity()))
       this->grow();
     ::new ((void*) this->end()) T(::std::move(Elt));
-    this->setEnd(this->end()+1);
+    this->set_size(this->size() + 1);
   }
 
   void pop_back() {
-    this->setEnd(this->end()-1);
+    this->set_size(this->size() - 1);
     this->end()->~T();
   }
 };
@@ -232,15 +238,13 @@ public:
 // Define this out-of-line to dissuade the C++ compiler from inlining it.
 template <typename T, bool isPodLike>
 void SmallVectorTemplateBase<T, isPodLike>::grow(size_t MinSize) {
-  size_t CurCapacity = this->capacity();
-  size_t CurSize = this->size();
+  if (MinSize > UINT32_MAX)
+    report_bad_alloc_error("SmallVector capacity overflow during allocation");
+
   // Always grow, even from zero.
-  size_t NewCapacity = size_t(NextPowerOf2(CurCapacity+2));
-  if (NewCapacity < MinSize)
-    NewCapacity = MinSize;
-  T *NewElts = static_cast<T*>(malloc(NewCapacity*sizeof(T)));
-  if (NewElts == nullptr)
-    report_bad_alloc_error("Allocation of SmallVector element failed.");
+  size_t NewCapacity = size_t(NextPowerOf2(this->capacity() + 2));
+  NewCapacity = std::min(std::max(NewCapacity, MinSize), size_t(UINT32_MAX));
+  T *NewElts = static_cast<T*>(llvm::safe_malloc(NewCapacity*sizeof(T)));
 
   // Move the elements over.
   this->uninitialized_move(this->begin(), this->end(), NewElts);
@@ -252,9 +256,8 @@ void SmallVectorTemplateBase<T, isPodLike>::grow(size_t MinSize) {
   if (!this->isSmall())
     free(this->begin());
 
-  this->setEnd(NewElts+CurSize);
   this->BeginX = NewElts;
-  this->CapacityX = this->begin()+NewCapacity;
+  this->Capacity = NewCapacity;
 }
 
 
@@ -301,21 +304,17 @@ protected:
 
   /// Double the size of the allocated memory, guaranteeing space for at
   /// least one more element or MinSize if specified.
-  void grow(size_t MinSize = 0) {
-    this->grow_pod(MinSize*sizeof(T), sizeof(T));
-  }
+  void grow(size_t MinSize = 0) { this->grow_pod(MinSize, sizeof(T)); }
 
 public:
   void push_back(const T &Elt) {
-    if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
+    if (LLVM_UNLIKELY(this->size() >= this->capacity()))
       this->grow();
     memcpy(this->end(), &Elt, sizeof(T));
-    this->setEnd(this->end()+1);
+    this->set_size(this->size() + 1);
   }
 
-  void pop_back() {
-    this->setEnd(this->end()-1);
-  }
+  void pop_back() { this->set_size(this->size() - 1); }
 };
 
 /// This class consists of common code factored out of the SmallVector class to
@@ -332,16 +331,13 @@ public:
 protected:
   // Default ctor - Initialize to empty.
   explicit SmallVectorImpl(unsigned N)
-    : SmallVectorTemplateBase<T, isPodLike<T>::value>(N*sizeof(T)) {
-  }
+      : SmallVectorTemplateBase<T, isPodLike<T>::value>(N) {}
 
 public:
   SmallVectorImpl(const SmallVectorImpl &) = delete;
 
   ~SmallVectorImpl() {
-    // Destroy the constructed elements in the vector.
-    this->destroy_range(this->begin(), this->end());
-
+    // Subclass has already destructed this vector's elements.
     // If this wasn't grown from the inline copy, deallocate the old space.
     if (!this->isSmall())
       free(this->begin());
@@ -349,31 +345,31 @@ public:
 
   void clear() {
     this->destroy_range(this->begin(), this->end());
-    this->EndX = this->BeginX;
+    this->Size = 0;
   }
 
   void resize(size_type N) {
     if (N < this->size()) {
       this->destroy_range(this->begin()+N, this->end());
-      this->setEnd(this->begin()+N);
+      this->set_size(N);
     } else if (N > this->size()) {
       if (this->capacity() < N)
         this->grow(N);
       for (auto I = this->end(), E = this->begin() + N; I != E; ++I)
         new (&*I) T();
-      this->setEnd(this->begin()+N);
+      this->set_size(N);
     }
   }
 
   void resize(size_type N, const T &NV) {
     if (N < this->size()) {
       this->destroy_range(this->begin()+N, this->end());
-      this->setEnd(this->begin()+N);
+      this->set_size(N);
     } else if (N > this->size()) {
       if (this->capacity() < N)
         this->grow(N);
       std::uninitialized_fill(this->end(), this->begin()+N, NV);
-      this->setEnd(this->begin()+N);
+      this->set_size(N);
     }
   }
 
@@ -398,23 +394,23 @@ public:
   void append(in_iter in_start, in_iter in_end) {
     size_type NumInputs = std::distance(in_start, in_end);
     // Grow allocated space if needed.
-    if (NumInputs > size_type(this->capacity_ptr()-this->end()))
+    if (NumInputs > this->capacity() - this->size())
       this->grow(this->size()+NumInputs);
 
     // Copy the new elements over.
     this->uninitialized_copy(in_start, in_end, this->end());
-    this->setEnd(this->end() + NumInputs);
+    this->set_size(this->size() + NumInputs);
   }
 
   /// Add the specified range to the end of the SmallVector.
   void append(size_type NumInputs, const T &Elt) {
     // Grow allocated space if needed.
-    if (NumInputs > size_type(this->capacity_ptr()-this->end()))
+    if (NumInputs > this->capacity() - this->size())
       this->grow(this->size()+NumInputs);
 
     // Copy the new elements over.
     std::uninitialized_fill_n(this->end(), NumInputs, Elt);
-    this->setEnd(this->end() + NumInputs);
+    this->set_size(this->size() + NumInputs);
   }
 
   void append(std::initializer_list<T> IL) {
@@ -428,7 +424,7 @@ public:
     clear();
     if (this->capacity() < NumElts)
       this->grow(NumElts);
-    this->setEnd(this->begin()+NumElts);
+    this->set_size(NumElts);
     std::uninitialized_fill(this->begin(), this->end(), Elt);
   }
 
@@ -475,7 +471,7 @@ public:
     iterator I = std::move(E, this->end(), S);
     // Drop the last elts.
     this->destroy_range(I, this->end());
-    this->setEnd(I);
+    this->set_size(I - this->begin());
     return(N);
   }
 
@@ -488,7 +484,7 @@ public:
     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
     assert(I <= this->end() && "Inserting past the end of the vector.");
 
-    if (this->EndX >= this->CapacityX) {
+    if (this->size() >= this->capacity()) {
       size_t EltNo = I-this->begin();
       this->grow();
       I = this->begin()+EltNo;
@@ -497,12 +493,12 @@ public:
     ::new ((void*) this->end()) T(::std::move(this->back()));
     // Push everything else over.
     std::move_backward(I, this->end()-1, this->end());
-    this->setEnd(this->end()+1);
+    this->set_size(this->size() + 1);
 
     // If we just moved the element we're inserting, be sure to update
     // the reference.
     T *EltPtr = &Elt;
-    if (I <= EltPtr && EltPtr < this->EndX)
+    if (I <= EltPtr && EltPtr < this->end())
       ++EltPtr;
 
     *I = ::std::move(*EltPtr);
@@ -518,7 +514,7 @@ public:
     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
     assert(I <= this->end() && "Inserting past the end of the vector.");
 
-    if (this->EndX >= this->CapacityX) {
+    if (this->size() >= this->capacity()) {
       size_t EltNo = I-this->begin();
       this->grow();
       I = this->begin()+EltNo;
@@ -526,12 +522,12 @@ public:
     ::new ((void*) this->end()) T(std::move(this->back()));
     // Push everything else over.
     std::move_backward(I, this->end()-1, this->end());
-    this->setEnd(this->end()+1);
+    this->set_size(this->size() + 1);
 
     // If we just moved the element we're inserting, be sure to update
     // the reference.
     const T *EltPtr = &Elt;
-    if (I <= EltPtr && EltPtr < this->EndX)
+    if (I <= EltPtr && EltPtr < this->end())
       ++EltPtr;
 
     *I = *EltPtr;
@@ -577,7 +573,7 @@ public:
 
     // Move over the elements that we're about to overwrite.
     T *OldEnd = this->end();
-    this->setEnd(this->end() + NumToInsert);
+    this->set_size(this->size() + NumToInsert);
     size_t NumOverwritten = OldEnd-I;
     this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
 
@@ -634,7 +630,7 @@ public:
 
     // Move over the elements that we're about to overwrite.
     T *OldEnd = this->end();
-    this->setEnd(this->end() + NumToInsert);
+    this->set_size(this->size() + NumToInsert);
     size_t NumOverwritten = OldEnd-I;
     this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
 
@@ -654,10 +650,10 @@ public:
   }
 
   template <typename... ArgTypes> void emplace_back(ArgTypes &&... Args) {
-    if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
+    if (LLVM_UNLIKELY(this->size() >= this->capacity()))
       this->grow();
     ::new ((void *)this->end()) T(std::forward<ArgTypes>(Args)...);
-    this->setEnd(this->end() + 1);
+    this->set_size(this->size() + 1);
   }
 
   SmallVectorImpl &operator=(const SmallVectorImpl &RHS);
@@ -676,20 +672,6 @@ public:
     return std::lexicographical_compare(this->begin(), this->end(),
                                         RHS.begin(), RHS.end());
   }
-
-  /// Set the array size to \p N, which the current array must have enough
-  /// capacity for.
-  ///
-  /// This does not construct or destroy any elements in the vector.
-  ///
-  /// Clients can use this in conjunction with capacity() to write past the end
-  /// of the buffer when they know that more elements are available, and only
-  /// update the size later. This avoids the cost of value initializing elements
-  /// which will only be overwritten.
-  void set_size(size_type N) {
-    assert(N <= this->capacity());
-    this->setEnd(this->begin() + N);
-  }
 };
 
 template <typename T>
@@ -699,8 +681,8 @@ void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) {
   // We can only avoid copying elements if neither vector is small.
   if (!this->isSmall() && !RHS.isSmall()) {
     std::swap(this->BeginX, RHS.BeginX);
-    std::swap(this->EndX, RHS.EndX);
-    std::swap(this->CapacityX, RHS.CapacityX);
+    std::swap(this->Size, RHS.Size);
+    std::swap(this->Capacity, RHS.Capacity);
     return;
   }
   if (RHS.size() > this->capacity())
@@ -718,15 +700,15 @@ void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) {
   if (this->size() > RHS.size()) {
     size_t EltDiff = this->size() - RHS.size();
     this->uninitialized_copy(this->begin()+NumShared, this->end(), RHS.end());
-    RHS.setEnd(RHS.end()+EltDiff);
+    RHS.set_size(RHS.size() + EltDiff);
     this->destroy_range(this->begin()+NumShared, this->end());
-    this->setEnd(this->begin()+NumShared);
+    this->set_size(NumShared);
   } else if (RHS.size() > this->size()) {
     size_t EltDiff = RHS.size() - this->size();
     this->uninitialized_copy(RHS.begin()+NumShared, RHS.end(), this->end());
-    this->setEnd(this->end() + EltDiff);
+    this->set_size(this->size() + EltDiff);
     this->destroy_range(RHS.begin()+NumShared, RHS.end());
-    RHS.setEnd(RHS.begin()+NumShared);
+    RHS.set_size(NumShared);
   }
 }
 
@@ -752,7 +734,7 @@ SmallVectorImpl<T> &SmallVectorImpl<T>::
     this->destroy_range(NewEnd, this->end());
 
     // Trim.
-    this->setEnd(NewEnd);
+    this->set_size(RHSSize);
     return *this;
   }
 
@@ -762,7 +744,7 @@ SmallVectorImpl<T> &SmallVectorImpl<T>::
   if (this->capacity() < RHSSize) {
     // Destroy current elements.
     this->destroy_range(this->begin(), this->end());
-    this->setEnd(this->begin());
+    this->set_size(0);
     CurSize = 0;
     this->grow(RHSSize);
   } else if (CurSize) {
@@ -775,7 +757,7 @@ SmallVectorImpl<T> &SmallVectorImpl<T>::
                            this->begin()+CurSize);
 
   // Set end.
-  this->setEnd(this->begin()+RHSSize);
+  this->set_size(RHSSize);
   return *this;
 }
 
@@ -789,8 +771,8 @@ SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) {
     this->destroy_range(this->begin(), this->end());
     if (!this->isSmall()) free(this->begin());
     this->BeginX = RHS.BeginX;
-    this->EndX = RHS.EndX;
-    this->CapacityX = RHS.CapacityX;
+    this->Size = RHS.Size;
+    this->Capacity = RHS.Capacity;
     RHS.resetToSmall();
     return *this;
   }
@@ -807,7 +789,7 @@ SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) {
 
     // Destroy excess elements and trim the bounds.
     this->destroy_range(NewEnd, this->end());
-    this->setEnd(NewEnd);
+    this->set_size(RHSSize);
 
     // Clear the RHS.
     RHS.clear();
@@ -822,7 +804,7 @@ SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) {
   if (this->capacity() < RHSSize) {
     // Destroy current elements.
     this->destroy_range(this->begin(), this->end());
-    this->setEnd(this->begin());
+    this->set_size(0);
     CurSize = 0;
     this->grow(RHSSize);
   } else if (CurSize) {
@@ -835,22 +817,23 @@ SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) {
                            this->begin()+CurSize);
 
   // Set end.
-  this->setEnd(this->begin()+RHSSize);
+  this->set_size(RHSSize);
 
   RHS.clear();
   return *this;
 }
 
-/// Storage for the SmallVector elements which aren't contained in
-/// SmallVectorTemplateCommon. There are 'N-1' elements here. The remaining '1'
-/// element is in the base class. This is specialized for the N=1 and N=0 cases
+/// Storage for the SmallVector elements.  This is specialized for the N=0 case
 /// to avoid allocating unnecessary storage.
 template <typename T, unsigned N>
 struct SmallVectorStorage {
-  typename SmallVectorTemplateCommon<T>::U InlineElts[N - 1];
+  AlignedCharArrayUnion<T> InlineElts[N];
 };
-template <typename T> struct SmallVectorStorage<T, 1> {};
-template <typename T> struct SmallVectorStorage<T, 0> {};
+
+/// We need the storage to be properly aligned even for small-size of 0 so that
+/// the pointer math in \a SmallVectorTemplateCommon::getFirstEl() is
+/// well-defined.
+template <typename T> struct alignas(alignof(T)) SmallVectorStorage<T, 0> {};
 
 /// This is a 'vector' (really, a variable-sized array), optimized
 /// for the case when the array is small.  It contains some number of elements
@@ -861,13 +844,15 @@ template <typename T> struct SmallVectorStorage<T, 0> {};
 /// Note that this does not attempt to be exception safe.
 ///
 template <typename T, unsigned N>
-class SmallVector : public SmallVectorImpl<T> {
-  /// Inline space for elements which aren't stored in the base class.
-  SmallVectorStorage<T, N> Storage;
-
+class SmallVector : public SmallVectorImpl<T>, SmallVectorStorage<T, N> {
 public:
   SmallVector() : SmallVectorImpl<T>(N) {}
 
+  ~SmallVector() {
+    // Destroy the constructed elements in the vector.
+    this->destroy_range(this->begin(), this->end());
+  }
+
   explicit SmallVector(size_t Size, const T &Value = T())
     : SmallVectorImpl<T>(N) {
     this->assign(Size, Value);
diff --git a/include/llvm/ADT/SparseMultiSet.h b/include/llvm/ADT/SparseMultiSet.h
index c91e0d70f65a..3c8637621510 100644
--- a/include/llvm/ADT/SparseMultiSet.h
+++ b/include/llvm/ADT/SparseMultiSet.h
@@ -211,7 +211,7 @@ public:
     // The Sparse array doesn't actually need to be initialized, so malloc
     // would be enough here, but that will cause tools like valgrind to
     // complain about branching on uninitialized data.
-    Sparse = reinterpret_cast<SparseT*>(calloc(U, sizeof(SparseT)));
+    Sparse = static_cast<SparseT*>(safe_calloc(U, sizeof(SparseT)));
     Universe = U;
   }
 
diff --git a/include/llvm/ADT/SparseSet.h b/include/llvm/ADT/SparseSet.h
index 25ade8831922..74cc6dab8c74 100644
--- a/include/llvm/ADT/SparseSet.h
+++ b/include/llvm/ADT/SparseSet.h
@@ -22,6 +22,7 @@
 
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/Support/Allocator.h"
 #include <cassert>
 #include <cstdint>
 #include <cstdlib>
@@ -163,7 +164,7 @@ public:
     // The Sparse array doesn't actually need to be initialized, so malloc
     // would be enough here, but that will cause tools like valgrind to
     // complain about branching on uninitialized data.
-    Sparse = reinterpret_cast<SparseT*>(calloc(U, sizeof(SparseT)));
+    Sparse = static_cast<SparseT*>(safe_calloc(U, sizeof(SparseT)));
     Universe = U;
   }
 
diff --git a/include/llvm/ADT/Statistic.h b/include/llvm/ADT/Statistic.h
index d5ebba409c3d..90c2eefceb6c 100644
--- a/include/llvm/ADT/Statistic.h
+++ b/include/llvm/ADT/Statistic.h
@@ -26,15 +26,24 @@
 #ifndef LLVM_ADT_STATISTIC_H
 #define LLVM_ADT_STATISTIC_H
 
-#include "llvm/Support/Atomic.h"
+#include "llvm/Config/llvm-config.h"
 #include "llvm/Support/Compiler.h"
 #include <atomic>
 #include <memory>
+#include <vector>
+
+// Determine whether statistics should be enabled. We must do it here rather
+// than in CMake because multi-config generators cannot determine this at
+// configure time.
+#if !defined(NDEBUG) || LLVM_FORCE_ENABLE_STATS
+#define LLVM_ENABLE_STATS 1
+#endif
 
 namespace llvm {
 
 class raw_ostream;
 class raw_fd_ostream;
+class StringRef;
 
 class Statistic {
 public:
@@ -42,7 +51,7 @@ public:
   const char *Name;
   const char *Desc;
   std::atomic<unsigned> Value;
-  bool Initialized;
+  std::atomic<bool> Initialized;
 
   unsigned getValue() const { return Value.load(std::memory_order_relaxed); }
   const char *getDebugType() const { return DebugType; }
@@ -61,7 +70,7 @@ public:
   // Allow use of this class as the value itself.
   operator unsigned() const { return getValue(); }
 
-#if !defined(NDEBUG) || defined(LLVM_ENABLE_STATS)
+#if LLVM_ENABLE_STATS
    const Statistic &operator=(unsigned Val) {
     Value.store(Val, std::memory_order_relaxed);
     return init();
@@ -143,14 +152,12 @@ public:
 
   void updateMax(unsigned V) {}
 
-#endif  // !defined(NDEBUG) || defined(LLVM_ENABLE_STATS)
+#endif  // LLVM_ENABLE_STATS
 
 protected:
   Statistic &init() {
-    bool tmp = Initialized;
-    sys::MemoryFence();
-    if (!tmp) RegisterStatistic();
-    TsanHappensAfter(this);
+    if (!Initialized.load(std::memory_order_acquire))
+      RegisterStatistic();
     return *this;
   }
 
@@ -160,21 +167,21 @@ protected:
 // STATISTIC - A macro to make definition of statistics really simple.  This
 // automatically passes the DEBUG_TYPE of the file into the statistic.
 #define STATISTIC(VARNAME, DESC)                                               \
-  static llvm::Statistic VARNAME = {DEBUG_TYPE, #VARNAME, DESC, {0}, false}
+  static llvm::Statistic VARNAME = {DEBUG_TYPE, #VARNAME, DESC, {0}, {false}}
 
-/// \brief Enable the collection and printing of statistics.
+/// Enable the collection and printing of statistics.
 void EnableStatistics(bool PrintOnExit = true);
 
-/// \brief Check if statistics are enabled.
+/// Check if statistics are enabled.
 bool AreStatisticsEnabled();
 
-/// \brief Return a file stream to print our output on.
+/// Return a file stream to print our output on.
 std::unique_ptr<raw_fd_ostream> CreateInfoOutputFile();
 
-/// \brief Print statistics to the file returned by CreateInfoOutputFile().
+/// Print statistics to the file returned by CreateInfoOutputFile().
 void PrintStatistics();
 
-/// \brief Print statistics to the given output stream.
+/// Print statistics to the given output stream.
 void PrintStatistics(raw_ostream &OS);
 
 /// Print statistics in JSON format. This does include all global timers (\see
@@ -183,6 +190,30 @@ void PrintStatistics(raw_ostream &OS);
 /// PrintStatisticsJSON().
 void PrintStatisticsJSON(raw_ostream &OS);
 
+/// Get the statistics. This can be used to look up the value of
+/// statistics without needing to parse JSON.
+///
+/// This function does not prevent statistics being updated by other threads
+/// during it's execution. It will return the value at the point that it is
+/// read. However, it will prevent new statistics from registering until it
+/// completes.
+const std::vector<std::pair<StringRef, unsigned>> GetStatistics();
+
+/// Reset the statistics. This can be used to zero and de-register the
+/// statistics in order to measure a compilation.
+///
+/// When this function begins to call destructors prior to returning, all
+/// statistics will be zero and unregistered. However, that might not remain the
+/// case by the time this function finishes returning. Whether update from other
+/// threads are lost or merely deferred until during the function return is
+/// timing sensitive.
+///
+/// Callers who intend to use this to measure statistics for a single
+/// compilation should ensure that no compilations are in progress at the point
+/// this function is called and that only one compilation executes until calling
+/// GetStatistics().
+void ResetStatistics();
+
 } // end namespace llvm
 
 #endif // LLVM_ADT_STATISTIC_H
diff --git a/include/llvm/ADT/StringExtras.h b/include/llvm/ADT/StringExtras.h
index 60652f8c55c5..71b0e7527cb7 100644
--- a/include/llvm/ADT/StringExtras.h
+++ b/include/llvm/ADT/StringExtras.h
@@ -39,6 +39,16 @@ inline char hexdigit(unsigned X, bool LowerCase = false) {
   return X < 10 ? '0' + X : HexChar + X - 10;
 }
 
+/// Given an array of c-style strings terminated by a null pointer, construct
+/// a vector of StringRefs representing the same strings without the terminating
+/// null string.
+inline std::vector<StringRef> toStringRefArray(const char *const *Strings) {
+  std::vector<StringRef> Result;
+  while (*Strings)
+    Result.push_back(*Strings++);
+  return Result;
+}
+
 /// Construct a string ref from a boolean.
 inline StringRef toStringRef(bool B) { return StringRef(B ? "true" : "false"); }
 
@@ -78,6 +88,26 @@ inline bool isAlpha(char C) {
 /// lowercase letter as classified by "C" locale.
 inline bool isAlnum(char C) { return isAlpha(C) || isDigit(C); }
 
+/// Checks whether character \p C is valid ASCII (high bit is zero).
+inline bool isASCII(char C) { return static_cast<unsigned char>(C) <= 127; }
+
+/// Checks whether all characters in S are ASCII.
+inline bool isASCII(llvm::StringRef S) {
+  for (char C : S)
+    if (LLVM_UNLIKELY(!isASCII(C)))
+      return false;
+  return true;
+}
+
+/// Checks whether character \p C is printable.
+///
+/// Locale-independent version of the C standard library isprint whose results
+/// may differ on different platforms.
+inline bool isPrint(char C) {
+  unsigned char UC = static_cast<unsigned char>(C);
+  return (0x20 <= UC) && (UC <= 0x7E);
+}
+
 /// Returns the corresponding lowercase character if \p x is uppercase.
 inline char toLower(char x) {
   if (x >= 'A' && x <= 'Z')
@@ -157,7 +187,7 @@ inline std::string fromHex(StringRef Input) {
   return Output;
 }
 
-/// \brief Convert the string \p S to an integer of the specified type using
+/// Convert the string \p S to an integer of the specified type using
 /// the radix \p Base.  If \p Base is 0, auto-detects the radix.
 /// Returns true if the number was successfully converted, false otherwise.
 template <typename N> bool to_integer(StringRef S, N &Num, unsigned Base = 0) {
@@ -232,19 +262,6 @@ void SplitString(StringRef Source,
                  SmallVectorImpl<StringRef> &OutFragments,
                  StringRef Delimiters = " \t\n\v\f\r");
 
-/// HashString - Hash function for strings.
-///
-/// This is the Bernstein hash function.
-//
-// FIXME: Investigate whether a modified bernstein hash function performs
-// better: http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx
-//   X*33+c -> X*33^c
-inline unsigned HashString(StringRef Str, unsigned Result = 0) {
-  for (StringRef::size_type i = 0, e = Str.size(); i != e; ++i)
-    Result = Result * 33 + (unsigned char)Str[i];
-  return Result;
-}
-
 /// Returns the English suffix for an ordinal integer (-st, -nd, -rd, -th).
 inline StringRef getOrdinalSuffix(unsigned Val) {
   // It is critically important that we do this perfectly for
@@ -264,9 +281,13 @@ inline StringRef getOrdinalSuffix(unsigned Val) {
   }
 }
 
-/// PrintEscapedString - Print each character of the specified string, escaping
-/// it if it is not printable or if it is an escape char.
-void PrintEscapedString(StringRef Name, raw_ostream &Out);
+/// Print each character of the specified string, escaping it if it is not
+/// printable or if it is an escape char.
+void printEscapedString(StringRef Name, raw_ostream &Out);
+
+/// Print each character of the specified string, escaping HTML special
+/// characters.
+void printHTMLEscaped(StringRef String, raw_ostream &Out);
 
 /// printLowerCase - Print each character as lowercase if it is uppercase.
 void printLowerCase(StringRef String, raw_ostream &Out);
diff --git a/include/llvm/ADT/StringMap.h b/include/llvm/ADT/StringMap.h
index 6c2830b44914..a9f83d3f5091 100644
--- a/include/llvm/ADT/StringMap.h
+++ b/include/llvm/ADT/StringMap.h
@@ -37,12 +37,12 @@ template<typename ValueTy> class StringMapKeyIterator;
 
 /// StringMapEntryBase - Shared base class of StringMapEntry instances.
 class StringMapEntryBase {
-  unsigned StrLen;
+  size_t StrLen;
 
 public:
-  explicit StringMapEntryBase(unsigned Len) : StrLen(Len) {}
+  explicit StringMapEntryBase(size_t Len) : StrLen(Len) {}
 
-  unsigned getKeyLength() const { return StrLen; }
+  size_t getKeyLength() const { return StrLen; }
 };
 
 /// StringMapImpl - This is the base class of StringMap that is shared among
@@ -127,10 +127,10 @@ class StringMapEntry : public StringMapEntryBase {
 public:
   ValueTy second;
 
-  explicit StringMapEntry(unsigned strLen)
+  explicit StringMapEntry(size_t strLen)
     : StringMapEntryBase(strLen), second() {}
   template <typename... InitTy>
-  StringMapEntry(unsigned strLen, InitTy &&... InitVals)
+  StringMapEntry(size_t strLen, InitTy &&... InitVals)
       : StringMapEntryBase(strLen), second(std::forward<InitTy>(InitVals)...) {}
   StringMapEntry(StringMapEntry &E) = delete;
 
@@ -155,19 +155,16 @@ public:
   template <typename AllocatorTy, typename... InitTy>
   static StringMapEntry *Create(StringRef Key, AllocatorTy &Allocator,
                                 InitTy &&... InitVals) {
-    unsigned KeyLength = Key.size();
+    size_t KeyLength = Key.size();
 
     // Allocate a new item with space for the string at the end and a null
     // terminator.
-    unsigned AllocSize = static_cast<unsigned>(sizeof(StringMapEntry))+
-      KeyLength+1;
-    unsigned Alignment = alignof(StringMapEntry);
+    size_t AllocSize = sizeof(StringMapEntry) + KeyLength + 1;
+    size_t Alignment = alignof(StringMapEntry);
 
     StringMapEntry *NewItem =
       static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment));
-
-    if (NewItem == nullptr)
-      report_bad_alloc_error("Allocation of StringMap entry failed.");
+    assert(NewItem && "Unhandled out-of-memory");
 
     // Construct the value.
     new (NewItem) StringMapEntry(KeyLength, std::forward<InitTy>(InitVals)...);
@@ -203,8 +200,7 @@ public:
   template<typename AllocatorTy>
   void Destroy(AllocatorTy &Allocator) {
     // Free memory referenced by the item.
-    unsigned AllocSize =
-        static_cast<unsigned>(sizeof(StringMapEntry)) + getKeyLength() + 1;
+    size_t AllocSize = sizeof(StringMapEntry) + getKeyLength() + 1;
     this->~StringMapEntry();
     Allocator.Deallocate(static_cast<void *>(this), AllocSize);
   }
diff --git a/include/llvm/ADT/StringRef.h b/include/llvm/ADT/StringRef.h
index f6c93a858db1..a5ba5b59b5a3 100644
--- a/include/llvm/ADT/StringRef.h
+++ b/include/llvm/ADT/StringRef.h
@@ -201,7 +201,7 @@ namespace llvm {
     LLVM_NODISCARD
     int compare_numeric(StringRef RHS) const;
 
-    /// \brief Determine the edit distance between this string and another
+    /// Determine the edit distance between this string and another
     /// string.
     ///
     /// \param Other the string to compare this string against.
@@ -725,10 +725,7 @@ namespace llvm {
     /// \returns The split substrings.
     LLVM_NODISCARD
     std::pair<StringRef, StringRef> split(char Separator) const {
-      size_t Idx = find(Separator);
-      if (Idx == npos)
-        return std::make_pair(*this, StringRef());
-      return std::make_pair(slice(0, Idx), slice(Idx+1, npos));
+      return split(StringRef(&Separator, 1));
     }
 
     /// Split into two substrings around the first occurrence of a separator
@@ -749,6 +746,24 @@ namespace llvm {
       return std::make_pair(slice(0, Idx), slice(Idx + Separator.size(), npos));
     }
 
+    /// Split into two substrings around the last occurrence of a separator
+    /// string.
+    ///
+    /// If \p Separator is in the string, then the result is a pair (LHS, RHS)
+    /// such that (*this == LHS + Separator + RHS) is true and RHS is
+    /// minimal. If \p Separator is not in the string, then the result is a
+    /// pair (LHS, RHS) where (*this == LHS) and (RHS == "").
+    ///
+    /// \param Separator - The string to split on.
+    /// \return - The split substrings.
+    LLVM_NODISCARD
+    std::pair<StringRef, StringRef> rsplit(StringRef Separator) const {
+      size_t Idx = rfind(Separator);
+      if (Idx == npos)
+        return std::make_pair(*this, StringRef());
+      return std::make_pair(slice(0, Idx), slice(Idx + Separator.size(), npos));
+    }
+
     /// Split into substrings around the occurrences of a separator string.
     ///
     /// Each substring is stored in \p A. If \p MaxSplit is >= 0, at most
@@ -796,10 +811,7 @@ namespace llvm {
     /// \return - The split substrings.
     LLVM_NODISCARD
     std::pair<StringRef, StringRef> rsplit(char Separator) const {
-      size_t Idx = rfind(Separator);
-      if (Idx == npos)
-        return std::make_pair(*this, StringRef());
-      return std::make_pair(slice(0, Idx), slice(Idx+1, npos));
+      return rsplit(StringRef(&Separator, 1));
     }
 
     /// Return string with consecutive \p Char characters starting from the
@@ -855,6 +867,10 @@ namespace llvm {
   /// constexpr StringLiteral S("test");
   ///
   class StringLiteral : public StringRef {
+  private:
+    constexpr StringLiteral(const char *Str, size_t N) : StringRef(Str, N) {
+    }
+
   public:
     template <size_t N>
     constexpr StringLiteral(const char (&Str)[N])
@@ -867,6 +883,12 @@ namespace llvm {
 #endif
         : StringRef(Str, N - 1) {
     }
+
+    // Explicit construction for strings like "foo\0bar".
+    template <size_t N>
+    static constexpr StringLiteral withInnerNUL(const char (&Str)[N]) {
+      return StringLiteral(Str, N - 1);
+    }
   };
 
   /// @name StringRef Comparison Operators
@@ -902,7 +924,7 @@ namespace llvm {
 
   /// @}
 
-  /// \brief Compute a hash_code for a StringRef.
+  /// Compute a hash_code for a StringRef.
   LLVM_NODISCARD
   hash_code hash_value(StringRef S);
 
diff --git a/include/llvm/ADT/StringSwitch.h b/include/llvm/ADT/StringSwitch.h
index 75577b7738ba..b7860b98ce5d 100644
--- a/include/llvm/ADT/StringSwitch.h
+++ b/include/llvm/ADT/StringSwitch.h
@@ -20,7 +20,7 @@
 
 namespace llvm {
 
-/// \brief A switch()-like statement whose cases are string literals.
+/// A switch()-like statement whose cases are string literals.
 ///
 /// The StringSwitch class is a simple form of a switch() statement that
 /// determines whether the given string matches one of the given string
@@ -41,216 +41,176 @@ namespace llvm {
 /// \endcode
 template<typename T, typename R = T>
 class StringSwitch {
-  /// \brief The string we are matching.
-  StringRef Str;
+  /// The string we are matching.
+  const StringRef Str;
 
-  /// \brief The pointer to the result of this switch statement, once known,
+  /// The pointer to the result of this switch statement, once known,
   /// null before that.
-  const T *Result;
+  Optional<T> Result;
 
 public:
   LLVM_ATTRIBUTE_ALWAYS_INLINE
   explicit StringSwitch(StringRef S)
-  : Str(S), Result(nullptr) { }
+  : Str(S), Result() { }
 
   // StringSwitch is not copyable.
   StringSwitch(const StringSwitch &) = delete;
+
+  // StringSwitch is not assignable due to 'Str' being 'const'.
   void operator=(const StringSwitch &) = delete;
+  void operator=(StringSwitch &&other) = delete;
 
-  StringSwitch(StringSwitch &&other) {
-    *this = std::move(other);
-  }
-  StringSwitch &operator=(StringSwitch &&other) {
-    Str = other.Str;
-    Result = other.Result;
-    return *this;
-  }
+  StringSwitch(StringSwitch &&other)
+    : Str(other.Str), Result(std::move(other.Result)) { }
 
   ~StringSwitch() = default;
 
   // Case-sensitive case matchers
-  template<unsigned N>
   LLVM_ATTRIBUTE_ALWAYS_INLINE
-  StringSwitch& Case(const char (&S)[N], const T& Value) {
-    assert(N);
-    if (!Result && N-1 == Str.size() &&
-        (N == 1 || std::memcmp(S, Str.data(), N-1) == 0)) {
-      Result = &Value;
+  StringSwitch &Case(StringLiteral S, T Value) {
+    if (!Result && Str == S) {
+      Result = std::move(Value);
     }
     return *this;
   }
 
-  template<unsigned N>
   LLVM_ATTRIBUTE_ALWAYS_INLINE
-  StringSwitch& EndsWith(const char (&S)[N], const T &Value) {
-    assert(N);
-    if (!Result && Str.size() >= N-1 &&
-        (N == 1 || std::memcmp(S, Str.data() + Str.size() + 1 - N, N-1) == 0)) {
-      Result = &Value;
+  StringSwitch& EndsWith(StringLiteral S, T Value) {
+    if (!Result && Str.endswith(S)) {
+      Result = std::move(Value);
     }
     return *this;
   }
 
-  template<unsigned N>
   LLVM_ATTRIBUTE_ALWAYS_INLINE
-  StringSwitch& StartsWith(const char (&S)[N], const T &Value) {
-    assert(N);
-    if (!Result && Str.size() >= N-1 &&
-        (N == 1 || std::memcmp(S, Str.data(), N-1) == 0)) {
-      Result = &Value;
+  StringSwitch& StartsWith(StringLiteral S, T Value) {
+    if (!Result && Str.startswith(S)) {
+      Result = std::move(Value);
     }
     return *this;
   }
 
-  template<unsigned N0, unsigned N1>
   LLVM_ATTRIBUTE_ALWAYS_INLINE
-  StringSwitch &Cases(const char (&S0)[N0], const char (&S1)[N1],
-                      const T& Value) {
+  StringSwitch &Cases(StringLiteral S0, StringLiteral S1, T Value) {
     return Case(S0, Value).Case(S1, Value);
   }
 
-  template<unsigned N0, unsigned N1, unsigned N2>
   LLVM_ATTRIBUTE_ALWAYS_INLINE
-  StringSwitch &Cases(const char (&S0)[N0], const char (&S1)[N1],
-                      const char (&S2)[N2], const T& Value) {
+  StringSwitch &Cases(StringLiteral S0, StringLiteral S1, StringLiteral S2,
+                      T Value) {
     return Case(S0, Value).Cases(S1, S2, Value);
   }
 
-  template<unsigned N0, unsigned N1, unsigned N2, unsigned N3>
   LLVM_ATTRIBUTE_ALWAYS_INLINE
-  StringSwitch &Cases(const char (&S0)[N0], const char (&S1)[N1],
-                      const char (&S2)[N2], const char (&S3)[N3],
-                      const T& Value) {
+  StringSwitch &Cases(StringLiteral S0, StringLiteral S1, StringLiteral S2,
+                      StringLiteral S3, T Value) {
     return Case(S0, Value).Cases(S1, S2, S3, Value);
   }
 
-  template<unsigned N0, unsigned N1, unsigned N2, unsigned N3, unsigned N4>
   LLVM_ATTRIBUTE_ALWAYS_INLINE
-  StringSwitch &Cases(const char (&S0)[N0], const char (&S1)[N1],
-                      const char (&S2)[N2], const char (&S3)[N3],
-                      const char (&S4)[N4], const T& Value) {
+  StringSwitch &Cases(StringLiteral S0, StringLiteral S1, StringLiteral S2,
+                      StringLiteral S3, StringLiteral S4, T Value) {
     return Case(S0, Value).Cases(S1, S2, S3, S4, Value);
   }
 
-  template <unsigned N0, unsigned N1, unsigned N2, unsigned N3, unsigned N4,
-            unsigned N5>
   LLVM_ATTRIBUTE_ALWAYS_INLINE
-  StringSwitch &Cases(const char (&S0)[N0], const char (&S1)[N1],
-                      const char (&S2)[N2], const char (&S3)[N3],
-                      const char (&S4)[N4], const char (&S5)[N5],
-                      const T &Value) {
+  StringSwitch &Cases(StringLiteral S0, StringLiteral S1, StringLiteral S2,
+                      StringLiteral S3, StringLiteral S4, StringLiteral S5,
+                      T Value) {
     return Case(S0, Value).Cases(S1, S2, S3, S4, S5, Value);
   }
 
-  template <unsigned N0, unsigned N1, unsigned N2, unsigned N3, unsigned N4,
-            unsigned N5, unsigned N6>
   LLVM_ATTRIBUTE_ALWAYS_INLINE
-  StringSwitch &Cases(const char (&S0)[N0], const char (&S1)[N1],
-                      const char (&S2)[N2], const char (&S3)[N3],
-                      const char (&S4)[N4], const char (&S5)[N5],
-                      const char (&S6)[N6], const T &Value) {
+  StringSwitch &Cases(StringLiteral S0, StringLiteral S1, StringLiteral S2,
+                      StringLiteral S3, StringLiteral S4, StringLiteral S5,
+                      StringLiteral S6, T Value) {
     return Case(S0, Value).Cases(S1, S2, S3, S4, S5, S6, Value);
   }
 
-  template <unsigned N0, unsigned N1, unsigned N2, unsigned N3, unsigned N4,
-            unsigned N5, unsigned N6, unsigned N7>
   LLVM_ATTRIBUTE_ALWAYS_INLINE
-  StringSwitch &Cases(const char (&S0)[N0], const char (&S1)[N1],
-                      const char (&S2)[N2], const char (&S3)[N3],
-                      const char (&S4)[N4], const char (&S5)[N5],
-                      const char (&S6)[N6], const char (&S7)[N7],
-                      const T &Value) {
+  StringSwitch &Cases(StringLiteral S0, StringLiteral S1, StringLiteral S2,
+                      StringLiteral S3, StringLiteral S4, StringLiteral S5,
+                      StringLiteral S6, StringLiteral S7, T Value) {
     return Case(S0, Value).Cases(S1, S2, S3, S4, S5, S6, S7, Value);
   }
 
-  template <unsigned N0, unsigned N1, unsigned N2, unsigned N3, unsigned N4,
-            unsigned N5, unsigned N6, unsigned N7, unsigned N8>
   LLVM_ATTRIBUTE_ALWAYS_INLINE
-  StringSwitch &Cases(const char (&S0)[N0], const char (&S1)[N1],
-                      const char (&S2)[N2], const char (&S3)[N3],
-                      const char (&S4)[N4], const char (&S5)[N5],
-                      const char (&S6)[N6], const char (&S7)[N7],
-                      const char (&S8)[N8], const T &Value) {
+  StringSwitch &Cases(StringLiteral S0, StringLiteral S1, StringLiteral S2,
+                      StringLiteral S3, StringLiteral S4, StringLiteral S5,
+                      StringLiteral S6, StringLiteral S7, StringLiteral S8,
+                      T Value) {
     return Case(S0, Value).Cases(S1, S2, S3, S4, S5, S6, S7, S8, Value);
   }
 
-  template <unsigned N0, unsigned N1, unsigned N2, unsigned N3, unsigned N4,
-            unsigned N5, unsigned N6, unsigned N7, unsigned N8, unsigned N9>
   LLVM_ATTRIBUTE_ALWAYS_INLINE
-  StringSwitch &Cases(const char (&S0)[N0], const char (&S1)[N1],
-                      const char (&S2)[N2], const char (&S3)[N3],
-                      const char (&S4)[N4], const char (&S5)[N5],
-                      const char (&S6)[N6], const char (&S7)[N7],
-                      const char (&S8)[N8], const char (&S9)[N9],
-                      const T &Value) {
+  StringSwitch &Cases(StringLiteral S0, StringLiteral S1, StringLiteral S2,
+                      StringLiteral S3, StringLiteral S4, StringLiteral S5,
+                      StringLiteral S6, StringLiteral S7, StringLiteral S8,
+                      StringLiteral S9, T Value) {
     return Case(S0, Value).Cases(S1, S2, S3, S4, S5, S6, S7, S8, S9, Value);
   }
 
   // Case-insensitive case matchers.
-  template <unsigned N>
-  LLVM_ATTRIBUTE_ALWAYS_INLINE StringSwitch &CaseLower(const char (&S)[N],
-                                                       const T &Value) {
-    if (!Result && Str.equals_lower(StringRef(S, N - 1)))
-      Result = &Value;
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
+  StringSwitch &CaseLower(StringLiteral S, T Value) {
+    if (!Result && Str.equals_lower(S))
+      Result = std::move(Value);
 
     return *this;
   }
 
-  template <unsigned N>
-  LLVM_ATTRIBUTE_ALWAYS_INLINE StringSwitch &EndsWithLower(const char (&S)[N],
-                                                           const T &Value) {
-    if (!Result && Str.endswith_lower(StringRef(S, N - 1)))
-      Result = &Value;
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
+  StringSwitch &EndsWithLower(StringLiteral S, T Value) {
+    if (!Result && Str.endswith_lower(S))
+      Result = Value;
 
     return *this;
   }
 
-  template <unsigned N>
-  LLVM_ATTRIBUTE_ALWAYS_INLINE StringSwitch &StartsWithLower(const char (&S)[N],
-                                                             const T &Value) {
-    if (!Result && Str.startswith_lower(StringRef(S, N - 1)))
-      Result = &Value;
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
+  StringSwitch &StartsWithLower(StringLiteral S, T Value) {
+    if (!Result && Str.startswith_lower(S))
+      Result = std::move(Value);
 
     return *this;
   }
-  template <unsigned N0, unsigned N1>
-  LLVM_ATTRIBUTE_ALWAYS_INLINE StringSwitch &
-  CasesLower(const char (&S0)[N0], const char (&S1)[N1], const T &Value) {
+
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
+  StringSwitch &CasesLower(StringLiteral S0, StringLiteral S1, T Value) {
     return CaseLower(S0, Value).CaseLower(S1, Value);
   }
 
-  template <unsigned N0, unsigned N1, unsigned N2>
-  LLVM_ATTRIBUTE_ALWAYS_INLINE StringSwitch &
-  CasesLower(const char (&S0)[N0], const char (&S1)[N1], const char (&S2)[N2],
-             const T &Value) {
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
+  StringSwitch &CasesLower(StringLiteral S0, StringLiteral S1, StringLiteral S2,
+                           T Value) {
     return CaseLower(S0, Value).CasesLower(S1, S2, Value);
   }
 
-  template <unsigned N0, unsigned N1, unsigned N2, unsigned N3>
-  LLVM_ATTRIBUTE_ALWAYS_INLINE StringSwitch &
-  CasesLower(const char (&S0)[N0], const char (&S1)[N1], const char (&S2)[N2],
-             const char (&S3)[N3], const T &Value) {
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
+  StringSwitch &CasesLower(StringLiteral S0, StringLiteral S1, StringLiteral S2,
+                           StringLiteral S3, T Value) {
     return CaseLower(S0, Value).CasesLower(S1, S2, S3, Value);
   }
 
-  template <unsigned N0, unsigned N1, unsigned N2, unsigned N3, unsigned N4>
-  LLVM_ATTRIBUTE_ALWAYS_INLINE StringSwitch &
-  CasesLower(const char (&S0)[N0], const char (&S1)[N1], const char (&S2)[N2],
-             const char (&S3)[N3], const char (&S4)[N4], const T &Value) {
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
+  StringSwitch &CasesLower(StringLiteral S0, StringLiteral S1, StringLiteral S2,
+                           StringLiteral S3, StringLiteral S4, T Value) {
     return CaseLower(S0, Value).CasesLower(S1, S2, S3, S4, Value);
   }
 
+  LLVM_NODISCARD
   LLVM_ATTRIBUTE_ALWAYS_INLINE
-  R Default(const T &Value) const {
+  R Default(T Value) {
     if (Result)
-      return *Result;
+      return std::move(*Result);
     return Value;
   }
 
+  LLVM_NODISCARD
   LLVM_ATTRIBUTE_ALWAYS_INLINE
-  operator R() const {
+  operator R() {
     assert(Result && "Fell off the end of a string-switch");
-    return *Result;
+    return std::move(*Result);
   }
 };
 
diff --git a/include/llvm/ADT/TinyPtrVector.h b/include/llvm/ADT/TinyPtrVector.h
index 73573d65e2b3..1b8e9aa658c3 100644
--- a/include/llvm/ADT/TinyPtrVector.h
+++ b/include/llvm/ADT/TinyPtrVector.h
@@ -108,6 +108,12 @@ public:
     return *this;
   }
 
+  TinyPtrVector(std::initializer_list<EltTy> IL)
+      : Val(IL.size() == 0
+                ? PtrUnion()
+                : IL.size() == 1 ? PtrUnion(*IL.begin())
+                                 : PtrUnion(new VecTy(IL.begin(), IL.end()))) {}
+
   /// Constructor from an ArrayRef.
   ///
   /// This also is a constructor for individual array elements due to the single
diff --git a/include/llvm/ADT/Triple.h b/include/llvm/ADT/Triple.h
index 74fc8eb8ccbf..c95b16dd4e8c 100644
--- a/include/llvm/ADT/Triple.h
+++ b/include/llvm/ADT/Triple.h
@@ -101,6 +101,7 @@ public:
   enum SubArchType {
     NoSubArch,
 
+    ARMSubArch_v8_4a,
     ARMSubArch_v8_3a,
     ARMSubArch_v8_2a,
     ARMSubArch_v8_1a,
@@ -144,7 +145,8 @@ public:
     AMD,
     Mesa,
     SUSE,
-    LastVendorType = SUSE
+    OpenEmbedded,
+    LastVendorType = OpenEmbedded
   };
   enum OSType {
     UnknownOS,
@@ -202,9 +204,7 @@ public:
     MSVC,
     Itanium,
     Cygnus,
-    AMDOpenCL,
     CoreCLR,
-    OpenCL,
     Simulator,  // Simulator variants of other systems, e.g., Apple's iOS
     LastEnvironmentType = Simulator
   };
@@ -660,9 +660,29 @@ public:
     return getArch() == Triple::aarch64 || getArch() == Triple::aarch64_be;
   }
 
-  /// Tests wether the target supports comdat
+  /// Tests whether the target is MIPS 32-bit (little and big endian).
+  bool isMIPS32() const {
+    return getArch() == Triple::mips || getArch() == Triple::mipsel;
+  }
+
+  /// Tests whether the target is MIPS 64-bit (little and big endian).
+  bool isMIPS64() const {
+    return getArch() == Triple::mips64 || getArch() == Triple::mips64el;
+  }
+
+  /// Tests whether the target is MIPS (little and big endian, 32- or 64-bit).
+  bool isMIPS() const {
+    return isMIPS32() || isMIPS64();
+  }
+
+  /// Tests whether the target supports comdat
   bool supportsCOMDAT() const {
-    return !isOSBinFormatMachO() && !isOSBinFormatWasm();
+    return !isOSBinFormatMachO();
+  }
+
+  /// Tests whether the target uses emulated TLS as default.
+  bool hasDefaultEmulatedTLS() const {
+    return isAndroid() || isOSOpenBSD() || isWindowsCygwinEnvironment();
   }
 
   /// @}
diff --git a/include/llvm/ADT/UniqueVector.h b/include/llvm/ADT/UniqueVector.h
index b17fb2392baf..c86bedd07687 100644
--- a/include/llvm/ADT/UniqueVector.h
+++ b/include/llvm/ADT/UniqueVector.h
@@ -72,16 +72,16 @@ public:
     return Vector[ID - 1];
   }
 
-  /// \brief Return an iterator to the start of the vector.
+  /// Return an iterator to the start of the vector.
   iterator begin() { return Vector.begin(); }
 
-  /// \brief Return an iterator to the start of the vector.
+  /// Return an iterator to the start of the vector.
   const_iterator begin() const { return Vector.begin(); }
 
-  /// \brief Return an iterator to the end of the vector.
+  /// Return an iterator to the end of the vector.
   iterator end() { return Vector.end(); }
 
-  /// \brief Return an iterator to the end of the vector.
+  /// Return an iterator to the end of the vector.
   const_iterator end() const { return Vector.end(); }
 
   /// size - Returns the number of entries in the vector.
diff --git a/include/llvm/ADT/VariadicFunction.h b/include/llvm/ADT/VariadicFunction.h
index 403130c623eb..9028abe4c72c 100644
--- a/include/llvm/ADT/VariadicFunction.h
+++ b/include/llvm/ADT/VariadicFunction.h
@@ -53,7 +53,7 @@ namespace llvm {
 #define LLVM_COMMA_JOIN31(x) LLVM_COMMA_JOIN30(x), x ## 30
 #define LLVM_COMMA_JOIN32(x) LLVM_COMMA_JOIN31(x), x ## 31
 
-/// \brief Class which can simulate a type-safe variadic function.
+/// Class which can simulate a type-safe variadic function.
 ///
 /// The VariadicFunction class template makes it easy to define
 /// type-safe variadic functions where all arguments have the same
diff --git a/include/llvm/ADT/edit_distance.h b/include/llvm/ADT/edit_distance.h
index 06a01b18a9fb..b2e8ec5c3f6d 100644
--- a/include/llvm/ADT/edit_distance.h
+++ b/include/llvm/ADT/edit_distance.h
@@ -22,7 +22,7 @@
 
 namespace llvm {
 
-/// \brief Determine the edit distance between two sequences.
+/// Determine the edit distance between two sequences.
 ///
 /// \param FromArray the first sequence to compare.
 ///
diff --git a/include/llvm/ADT/ilist.h b/include/llvm/ADT/ilist.h
index a788f811e4c6..00bb6d528175 100644
--- a/include/llvm/ADT/ilist.h
+++ b/include/llvm/ADT/ilist.h
@@ -84,21 +84,11 @@ template <typename NodeTy>
 struct ilist_node_traits : ilist_alloc_traits<NodeTy>,
                            ilist_callback_traits<NodeTy> {};
 
-/// Default template traits for intrusive list.
-///
-/// By inheriting from this, you can easily use default implementations for all
-/// common operations.
-///
-/// TODO: Remove this customization point.  Specializing ilist_traits is
-/// already fully general.
-template <typename NodeTy>
-struct ilist_default_traits : public ilist_node_traits<NodeTy> {};
-
 /// Template traits for intrusive list.
 ///
 /// Customize callbacks and allocation semantics.
 template <typename NodeTy>
-struct ilist_traits : public ilist_default_traits<NodeTy> {};
+struct ilist_traits : public ilist_node_traits<NodeTy> {};
 
 /// Const traits should never be instantiated.
 template <typename Ty> struct ilist_traits<const Ty> {};
@@ -178,9 +168,6 @@ template <class IntrusiveListT, class TraitsT>
 class iplist_impl : public TraitsT, IntrusiveListT {
   typedef IntrusiveListT base_list_type;
 
-protected:
-  typedef iplist_impl iplist_impl_type;
-
 public:
   typedef typename base_list_type::pointer pointer;
   typedef typename base_list_type::const_pointer const_pointer;
@@ -369,26 +356,26 @@ public:
 
   using base_list_type::sort;
 
-  /// \brief Get the previous node, or \c nullptr for the list head.
+  /// Get the previous node, or \c nullptr for the list head.
   pointer getPrevNode(reference N) const {
     auto I = N.getIterator();
     if (I == begin())
       return nullptr;
     return &*std::prev(I);
   }
-  /// \brief Get the previous node, or \c nullptr for the list head.
+  /// Get the previous node, or \c nullptr for the list head.
   const_pointer getPrevNode(const_reference N) const {
     return getPrevNode(const_cast<reference >(N));
   }
 
-  /// \brief Get the next node, or \c nullptr for the list tail.
+  /// Get the next node, or \c nullptr for the list tail.
   pointer getNextNode(reference N) const {
     auto Next = std::next(N.getIterator());
     if (Next == end())
       return nullptr;
     return &*Next;
   }
-  /// \brief Get the next node, or \c nullptr for the list tail.
+  /// Get the next node, or \c nullptr for the list tail.
   const_pointer getNextNode(const_reference N) const {
     return getNextNode(const_cast<reference >(N));
   }
@@ -402,7 +389,7 @@ public:
 template <class T, class... Options>
 class iplist
     : public iplist_impl<simple_ilist<T, Options...>, ilist_traits<T>> {
-  typedef typename iplist::iplist_impl_type iplist_impl_type;
+  using iplist_impl_type = typename iplist::iplist_impl;
 
 public:
   iplist() = default;
diff --git a/include/llvm/ADT/ilist_node.h b/include/llvm/ADT/ilist_node.h
index 3362611697cb..dd0e6b4ec2b9 100644
--- a/include/llvm/ADT/ilist_node.h
+++ b/include/llvm/ADT/ilist_node.h
@@ -271,7 +271,7 @@ private:
 public:
   /// @name Adjacent Node Accessors
   /// @{
-  /// \brief Get the previous node, or \c nullptr for the list head.
+  /// Get the previous node, or \c nullptr for the list head.
   NodeTy *getPrevNode() {
     // Should be separated to a reused function, but then we couldn't use auto
     // (and would need the type of the list).
@@ -280,12 +280,12 @@ public:
     return List.getPrevNode(*static_cast<NodeTy *>(this));
   }
 
-  /// \brief Get the previous node, or \c nullptr for the list head.
+  /// Get the previous node, or \c nullptr for the list head.
   const NodeTy *getPrevNode() const {
     return const_cast<ilist_node_with_parent *>(this)->getPrevNode();
   }
 
-  /// \brief Get the next node, or \c nullptr for the list tail.
+  /// Get the next node, or \c nullptr for the list tail.
   NodeTy *getNextNode() {
     // Should be separated to a reused function, but then we couldn't use auto
     // (and would need the type of the list).
@@ -294,7 +294,7 @@ public:
     return List.getNextNode(*static_cast<NodeTy *>(this));
   }
 
-  /// \brief Get the next node, or \c nullptr for the list tail.
+  /// Get the next node, or \c nullptr for the list tail.
   const NodeTy *getNextNode() const {
     return const_cast<ilist_node_with_parent *>(this)->getNextNode();
   }
diff --git a/include/llvm/ADT/ilist_node_options.h b/include/llvm/ADT/ilist_node_options.h
index c33df1eeb819..7ff4005f6757 100644
--- a/include/llvm/ADT/ilist_node_options.h
+++ b/include/llvm/ADT/ilist_node_options.h
@@ -11,7 +11,6 @@
 #define LLVM_ADT_ILIST_NODE_OPTIONS_H
 
 #include "llvm/Config/abi-breaking.h"
-#include "llvm/Config/llvm-config.h"
 
 #include <type_traits>
 
diff --git a/include/llvm/ADT/iterator.h b/include/llvm/ADT/iterator.h
index 711f8f221620..549c5221173d 100644
--- a/include/llvm/ADT/iterator.h
+++ b/include/llvm/ADT/iterator.h
@@ -19,7 +19,7 @@
 
 namespace llvm {
 
-/// \brief CRTP base class which implements the entire standard iterator facade
+/// CRTP base class which implements the entire standard iterator facade
 /// in terms of a minimal subset of the interface.
 ///
 /// Use this when it is reasonable to implement most of the iterator
@@ -183,7 +183,7 @@ public:
   }
 };
 
-/// \brief CRTP base class for adapting an iterator to a different type.
+/// CRTP base class for adapting an iterator to a different type.
 ///
 /// This class can be used through CRTP to adapt one iterator into another.
 /// Typically this is done through providing in the derived class a custom \c
@@ -274,7 +274,7 @@ public:
   ReferenceT operator*() const { return *I; }
 };
 
-/// \brief An iterator type that allows iterating over the pointees via some
+/// An iterator type that allows iterating over the pointees via some
 /// other iterator.
 ///
 /// The typical usage of this is to expose a type that iterates over Ts, but
@@ -288,7 +288,7 @@ template <typename WrappedIteratorT,
               decltype(**std::declval<WrappedIteratorT>())>::type>
 struct pointee_iterator
     : iterator_adaptor_base<
-          pointee_iterator<WrappedIteratorT>, WrappedIteratorT,
+          pointee_iterator<WrappedIteratorT, T>, WrappedIteratorT,
           typename std::iterator_traits<WrappedIteratorT>::iterator_category,
           T> {
   pointee_iterator() = default;
@@ -311,7 +311,7 @@ make_pointee_range(RangeT &&Range) {
 template <typename WrappedIteratorT,
           typename T = decltype(&*std::declval<WrappedIteratorT>())>
 class pointer_iterator
-    : public iterator_adaptor_base<pointer_iterator<WrappedIteratorT>,
+    : public iterator_adaptor_base<pointer_iterator<WrappedIteratorT, T>,
                                    WrappedIteratorT, T> {
   mutable T Ptr;
 
diff --git a/include/llvm/ADT/iterator_range.h b/include/llvm/ADT/iterator_range.h
index 3cbf6198eb60..2ba12866ecf3 100644
--- a/include/llvm/ADT/iterator_range.h
+++ b/include/llvm/ADT/iterator_range.h
@@ -24,7 +24,7 @@
 
 namespace llvm {
 
-/// \brief A range adaptor for a pair of iterators.
+/// A range adaptor for a pair of iterators.
 ///
 /// This just wraps two iterators into a range-compatible interface. Nothing
 /// fancy at all.
@@ -47,7 +47,7 @@ public:
   IteratorT end() const { return end_iterator; }
 };
 
-/// \brief Convenience function for iterating over sub-ranges.
+/// Convenience function for iterating over sub-ranges.
 ///
 /// This provides a bit of syntactic sugar to make using sub-ranges
 /// in for loops a bit easier. Analogous to std::make_pair().
@@ -59,9 +59,10 @@ template <typename T> iterator_range<T> make_range(std::pair<T, T> p) {
   return iterator_range<T>(std::move(p.first), std::move(p.second));
 }
 
-template<typename T>
-iterator_range<decltype(begin(std::declval<T>()))> drop_begin(T &&t, int n) {
-  return make_range(std::next(begin(t), n), end(t));
+template <typename T>
+iterator_range<decltype(adl_begin(std::declval<T>()))> drop_begin(T &&t,
+                                                                  int n) {
+  return make_range(std::next(adl_begin(t), n), adl_end(t));
 }
 }