39 files changed, 1243 insertions, 789 deletions

diff --git a/include/llvm/ADT/APFloat.h b/include/llvm/ADT/APFloat.h
index 76615affb253..3fe04060fd59 100644
--- a/include/llvm/ADT/APFloat.h
+++ b/include/llvm/ADT/APFloat.h
@@ -142,6 +142,9 @@ public:
   /// @}
 
   static unsigned int semanticsPrecision(const fltSemantics &);
+  static ExponentType semanticsMinExponent(const fltSemantics &);
+  static ExponentType semanticsMaxExponent(const fltSemantics &);
+  static unsigned int semanticsSizeInBits(const fltSemantics &);
 
   /// IEEE-754R 5.11: Floating Point Comparison Relations.
   enum cmpResult {
@@ -296,7 +299,7 @@ public:
   /// IEEE remainder.
   opStatus remainder(const APFloat &);
   /// C fmod, or llvm frem.
-  opStatus mod(const APFloat &, roundingMode);
+  opStatus mod(const APFloat &);
   opStatus fusedMultiplyAdd(const APFloat &, const APFloat &, roundingMode);
   opStatus roundToIntegral(roundingMode);
   /// IEEE-754R 5.3.1: nextUp/nextDown.
@@ -445,6 +448,9 @@ public:
   /// Returns true if and only if the number has the largest possible finite
   /// magnitude in the current semantics.
   bool isLargest() const;
+  
+  /// Returns true if and only if the number is an exact integer.
+  bool isInteger() const;
 
   /// @}
 
diff --git a/include/llvm/ADT/APInt.h b/include/llvm/ADT/APInt.h
index 5013f295f5c7..e2a0cb5e69dc 100644
--- a/include/llvm/ADT/APInt.h
+++ b/include/llvm/ADT/APInt.h
@@ -294,11 +294,12 @@ public:
       delete[] pVal;
   }
 
-  /// \brief Default constructor that creates an uninitialized APInt.
+  /// \brief Default constructor that creates an uninteresting APInt
+  /// representing a 1-bit zero value.
   ///
   /// This is useful for object deserialization (pair this with the static
   ///  method Read).
-  explicit APInt() : BitWidth(1) {}
+  explicit APInt() : BitWidth(1), VAL(0) {}
 
   /// \brief Returns whether this instance allocated memory.
   bool needsCleanup() const { return !isSingleWord(); }
@@ -1528,7 +1529,7 @@ public:
   /// \returns the nearest log base 2 of this APInt. Ties round up.
   ///
   /// NOTE: When we have a BitWidth of 1, we define:
-  /// 
+  ///
   ///   log2(0) = UINT32_MAX
   ///   log2(1) = 0
   ///
diff --git a/include/llvm/ADT/APSInt.h b/include/llvm/ADT/APSInt.h
index a187515f8592..a6552d0a2f36 100644
--- a/include/llvm/ADT/APSInt.h
+++ b/include/llvm/ADT/APSInt.h
@@ -21,6 +21,7 @@ namespace llvm {
 
 class APSInt : public APInt {
   bool IsUnsigned;
+
 public:
   /// Default constructor that creates an uninitialized APInt.
   explicit APSInt() : IsUnsigned(false) {}
@@ -246,8 +247,7 @@ public:
     return this->operator|(RHS);
   }
 
-
-  APSInt operator^(const APSInt& RHS) const {
+  APSInt operator^(const APSInt &RHS) const {
     assert(IsUnsigned == RHS.IsUnsigned && "Signedness mismatch!");
     return APSInt(static_cast<const APInt&>(*this) ^ RHS, IsUnsigned);
   }
@@ -286,7 +286,7 @@ public:
   }
 
   /// \brief Determine if two APSInts have the same value, zero- or
-  /// sign-extending as needed.  
+  /// sign-extending as needed.
   static bool isSameValue(const APSInt &I1, const APSInt &I2) {
     return !compareValues(I1, I2);
   }
diff --git a/include/llvm/ADT/ArrayRef.h b/include/llvm/ADT/ArrayRef.h
index c8795fd89e33..517ba39849e1 100644
--- a/include/llvm/ADT/ArrayRef.h
+++ b/include/llvm/ADT/ArrayRef.h
@@ -10,6 +10,7 @@
 #ifndef LLVM_ADT_ARRAYREF_H
 #define LLVM_ADT_ARRAYREF_H
 
+#include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/SmallVector.h"
 #include <vector>
@@ -85,7 +86,7 @@ namespace llvm {
 
     /// Construct an ArrayRef from a std::initializer_list.
     /*implicit*/ ArrayRef(const std::initializer_list<T> &Vec)
-    : Data(Vec.begin() == Vec.end() ? (T*)0 : Vec.begin()),
+    : Data(Vec.begin() == Vec.end() ? (T*)nullptr : Vec.begin()),
       Length(Vec.size()) {}
 
     /// Construct an ArrayRef<const T*> from ArrayRef<T*>. This uses SFINAE to
@@ -148,7 +149,7 @@ namespace llvm {
     // copy - Allocate copy in Allocator and return ArrayRef<T> to it.
     template <typename Allocator> ArrayRef<T> copy(Allocator &A) {
       T *Buff = A.template Allocate<T>(Length);
-      std::copy(begin(), end(), Buff);
+      std::uninitialized_copy(begin(), end(), Buff);
       return ArrayRef<T>(Buff, Length);
     }
 
@@ -156,8 +157,6 @@ namespace llvm {
     bool equals(ArrayRef RHS) const {
       if (Length != RHS.Length)
         return false;
-      if (Length == 0)
-        return true;
       return std::equal(begin(), end(), RHS.begin());
     }
 
@@ -339,6 +338,16 @@ namespace llvm {
     return Vec;
   }
 
+  /// Construct an ArrayRef from an ArrayRef (no-op) (const)
+  template <typename T> ArrayRef<T> makeArrayRef(const ArrayRef<T> &Vec) {
+    return Vec;
+  }
+
+  /// Construct an ArrayRef from an ArrayRef (no-op)
+  template <typename T> ArrayRef<T> &makeArrayRef(ArrayRef<T> &Vec) {
+    return Vec;
+  }
+
   /// Construct an ArrayRef from a C array.
   template<typename T, size_t N>
   ArrayRef<T> makeArrayRef(const T (&Arr)[N]) {
@@ -366,6 +375,10 @@ namespace llvm {
   template <typename T> struct isPodLike<ArrayRef<T> > {
     static const bool value = true;
   };
+
+  template <typename T> hash_code hash_value(ArrayRef<T> S) {
+    return hash_combine_range(S.begin(), S.end());
+  }
 }
 
 #endif
diff --git a/include/llvm/ADT/BitVector.h b/include/llvm/ADT/BitVector.h
index f58dd7356c7d..ad00d51f99e9 100644
--- a/include/llvm/ADT/BitVector.h
+++ b/include/llvm/ADT/BitVector.h
@@ -34,7 +34,7 @@ class BitVector {
 
   BitWord  *Bits;        // Actual bits.
   unsigned Size;         // Size of bitvector in bits.
-  unsigned Capacity;     // Size of allocated memory in BitWord.
+  unsigned Capacity;     // Number of BitWords allocated in the Bits array.
 
 public:
   typedef unsigned size_type;
@@ -566,8 +566,16 @@ private:
     if (AddBits)
       clear_unused_bits();
   }
+
+public:
+  /// Return the size (in bytes) of the bit vector.
+  size_t getMemorySize() const { return Capacity * sizeof(BitWord); }
 };
 
+static inline size_t capacity_in_bytes(const BitVector &X) {
+  return X.getMemorySize();
+}
+
 } // End llvm namespace
 
 namespace std {
diff --git a/include/llvm/ADT/DeltaAlgorithm.h b/include/llvm/ADT/DeltaAlgorithm.h
index 21bc1e80c9d8..a26f37dfdc7d 100644
--- a/include/llvm/ADT/DeltaAlgorithm.h
+++ b/include/llvm/ADT/DeltaAlgorithm.h
@@ -68,7 +68,7 @@ private:
   /// \return - True on success.
   bool Search(const changeset_ty &Changes, const changesetlist_ty &Sets,
               changeset_ty &Res);
-              
+
 protected:
   /// UpdatedSearchState - Callback used when the search state changes.
   virtual void UpdatedSearchState(const changeset_ty &Changes,
diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h
index 27f73157a29f..6ee1960b5c82 100644
--- a/include/llvm/ADT/DenseMap.h
+++ b/include/llvm/ADT/DenseMap.h
@@ -282,7 +282,7 @@ protected:
            "# initial buckets must be a power of two!");
     const KeyT EmptyKey = getEmptyKey();
     for (BucketT *B = getBuckets(), *E = getBucketsEnd(); B != E; ++B)
-      new (&B->getFirst()) KeyT(EmptyKey);
+      ::new (&B->getFirst()) KeyT(EmptyKey);
   }
 
   void moveFromOldBuckets(BucketT *OldBucketsBegin, BucketT *OldBucketsEnd) {
@@ -300,7 +300,7 @@ protected:
         (void)FoundVal; // silence warning.
         assert(!FoundVal && "Key already in new map?");
         DestBucket->getFirst() = std::move(B->getFirst());
-        new (&DestBucket->getSecond()) ValueT(std::move(B->getSecond()));
+        ::new (&DestBucket->getSecond()) ValueT(std::move(B->getSecond()));
         incrementNumEntries();
 
         // Free the value.
@@ -324,11 +324,11 @@ protected:
              getNumBuckets() * sizeof(BucketT));
     else
       for (size_t i = 0; i < getNumBuckets(); ++i) {
-        new (&getBuckets()[i].getFirst())
+        ::new (&getBuckets()[i].getFirst())
             KeyT(other.getBuckets()[i].getFirst());
         if (!KeyInfoT::isEqual(getBuckets()[i].getFirst(), getEmptyKey()) &&
             !KeyInfoT::isEqual(getBuckets()[i].getFirst(), getTombstoneKey()))
-          new (&getBuckets()[i].getSecond())
+          ::new (&getBuckets()[i].getSecond())
               ValueT(other.getBuckets()[i].getSecond());
       }
   }
@@ -402,7 +402,7 @@ private:
     TheBucket = InsertIntoBucketImpl(Key, TheBucket);
 
     TheBucket->getFirst() = Key;
-    new (&TheBucket->getSecond()) ValueT(Value);
+    ::new (&TheBucket->getSecond()) ValueT(Value);
     return TheBucket;
   }
 
@@ -411,7 +411,7 @@ private:
     TheBucket = InsertIntoBucketImpl(Key, TheBucket);
 
     TheBucket->getFirst() = Key;
-    new (&TheBucket->getSecond()) ValueT(std::move(Value));
+    ::new (&TheBucket->getSecond()) ValueT(std::move(Value));
     return TheBucket;
   }
 
@@ -419,7 +419,7 @@ private:
     TheBucket = InsertIntoBucketImpl(Key, TheBucket);
 
     TheBucket->getFirst() = std::move(Key);
-    new (&TheBucket->getSecond()) ValueT(std::move(Value));
+    ::new (&TheBucket->getSecond()) ValueT(std::move(Value));
     return TheBucket;
   }
 
@@ -766,10 +766,10 @@ public:
         // Swap separately and handle any assymetry.
         std::swap(LHSB->getFirst(), RHSB->getFirst());
         if (hasLHSValue) {
-          new (&RHSB->getSecond()) ValueT(std::move(LHSB->getSecond()));
+          ::new (&RHSB->getSecond()) ValueT(std::move(LHSB->getSecond()));
           LHSB->getSecond().~ValueT();
         } else if (hasRHSValue) {
-          new (&LHSB->getSecond()) ValueT(std::move(RHSB->getSecond()));
+          ::new (&LHSB->getSecond()) ValueT(std::move(RHSB->getSecond()));
           RHSB->getSecond().~ValueT();
         }
       }
@@ -795,11 +795,11 @@ public:
     for (unsigned i = 0, e = InlineBuckets; i != e; ++i) {
       BucketT *NewB = &LargeSide.getInlineBuckets()[i],
               *OldB = &SmallSide.getInlineBuckets()[i];
-      new (&NewB->getFirst()) KeyT(std::move(OldB->getFirst()));
+      ::new (&NewB->getFirst()) KeyT(std::move(OldB->getFirst()));
       OldB->getFirst().~KeyT();
       if (!KeyInfoT::isEqual(NewB->getFirst(), EmptyKey) &&
           !KeyInfoT::isEqual(NewB->getFirst(), TombstoneKey)) {
-        new (&NewB->getSecond()) ValueT(std::move(OldB->getSecond()));
+        ::new (&NewB->getSecond()) ValueT(std::move(OldB->getSecond()));
         OldB->getSecond().~ValueT();
       }
     }
@@ -866,8 +866,8 @@ public:
             !KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) {
           assert(size_t(TmpEnd - TmpBegin) < InlineBuckets &&
                  "Too many inline buckets!");
-          new (&TmpEnd->getFirst()) KeyT(std::move(P->getFirst()));
-          new (&TmpEnd->getSecond()) ValueT(std::move(P->getSecond()));
+          ::new (&TmpEnd->getFirst()) KeyT(std::move(P->getFirst()));
+          ::new (&TmpEnd->getSecond()) ValueT(std::move(P->getSecond()));
           ++TmpEnd;
           P->getSecond().~ValueT();
         }
diff --git a/include/llvm/ADT/DenseMapInfo.h b/include/llvm/ADT/DenseMapInfo.h
index b0a053072079..a844ebcccf5b 100644
--- a/include/llvm/ADT/DenseMapInfo.h
+++ b/include/llvm/ADT/DenseMapInfo.h
@@ -14,6 +14,7 @@
 #ifndef LLVM_ADT_DENSEMAPINFO_H
 #define LLVM_ADT_DENSEMAPINFO_H
 
+#include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/PointerLikeTypeTraits.h"
@@ -58,7 +59,7 @@ template<> struct DenseMapInfo<char> {
     return LHS == RHS;
   }
 };
-  
+
 // Provide DenseMapInfo for unsigned ints.
 template<> struct DenseMapInfo<unsigned> {
   static inline unsigned getEmptyKey() { return ~0U; }
@@ -190,6 +191,31 @@ template <> struct DenseMapInfo<StringRef> {
   }
 };
 
+// Provide DenseMapInfo for ArrayRefs.
+template <typename T> struct DenseMapInfo<ArrayRef<T>> {
+  static inline ArrayRef<T> getEmptyKey() {
+    return ArrayRef<T>(reinterpret_cast<const T *>(~static_cast<uintptr_t>(0)),
+                       size_t(0));
+  }
+  static inline ArrayRef<T> getTombstoneKey() {
+    return ArrayRef<T>(reinterpret_cast<const T *>(~static_cast<uintptr_t>(1)),
+                       size_t(0));
+  }
+  static unsigned getHashValue(ArrayRef<T> Val) {
+    assert(Val.data() != getEmptyKey().data() && "Cannot hash the empty key!");
+    assert(Val.data() != getTombstoneKey().data() &&
+           "Cannot hash the tombstone key!");
+    return (unsigned)(hash_value(Val));
+  }
+  static bool isEqual(ArrayRef<T> LHS, ArrayRef<T> RHS) {
+    if (RHS.data() == getEmptyKey().data())
+      return LHS.data() == getEmptyKey().data();
+    if (RHS.data() == getTombstoneKey().data())
+      return LHS.data() == getTombstoneKey().data();
+    return LHS == RHS;
+  }
+};
+
 } // end namespace llvm
 
 #endif
diff --git a/include/llvm/ADT/DenseSet.h b/include/llvm/ADT/DenseSet.h
index d34024005dfe..ef09dce37980 100644
--- a/include/llvm/ADT/DenseSet.h
+++ b/include/llvm/ADT/DenseSet.h
@@ -42,6 +42,7 @@ class DenseSet {
   static_assert(sizeof(typename MapTy::value_type) == sizeof(ValueT),
                 "DenseMap buckets unexpectedly large!");
   MapTy TheMap;
+
 public:
   typedef ValueT key_type;
   typedef ValueT value_type;
@@ -79,6 +80,7 @@ public:
   class Iterator {
     typename MapTy::iterator I;
     friend class DenseSet;
+
   public:
     typedef typename MapTy::iterator::difference_type difference_type;
     typedef ValueT value_type;
@@ -99,6 +101,7 @@ public:
   class ConstIterator {
     typename MapTy::const_iterator I;
     friend class DenseSet;
+
   public:
     typedef typename MapTy::const_iterator::difference_type difference_type;
     typedef ValueT value_type;
@@ -148,7 +151,7 @@ public:
     detail::DenseSetEmpty Empty;
     return TheMap.insert(std::make_pair(V, Empty));
   }
-  
+
   // Range insertion of values.
   template<typename InputIt>
   void insert(InputIt I, InputIt E) {
diff --git a/include/llvm/ADT/DepthFirstIterator.h b/include/llvm/ADT/DepthFirstIterator.h
index d79b9acacfa9..c9317b8539b3 100644
--- a/include/llvm/ADT/DepthFirstIterator.h
+++ b/include/llvm/ADT/DepthFirstIterator.h
@@ -58,7 +58,6 @@ public:
   SetType &Visited;
 };
 
-
 // Generic Depth First Iterator
 template<class GraphT,
 class SetType = llvm::SmallPtrSet<typename GraphTraits<GraphT>::NodeType*, 8>,
@@ -76,21 +75,22 @@ class df_iterator : public std::iterator<std::forward_iterator_tag,
   // VisitStack - Used to maintain the ordering.  Top = current block
   // First element is node pointer, second is the 'next child' to visit
   // if the int in PointerIntTy is 0, the 'next child' to visit is invalid
-  std::vector<std::pair<PointerIntTy, ChildItTy> > VisitStack;
+  std::vector<std::pair<PointerIntTy, ChildItTy>> VisitStack;
+
 private:
   inline df_iterator(NodeType *Node) {
     this->Visited.insert(Node);
-    VisitStack.push_back(std::make_pair(PointerIntTy(Node, 0), 
-                                        GT::child_begin(Node)));
+    VisitStack.push_back(
+        std::make_pair(PointerIntTy(Node, 0), GT::child_begin(Node)));
   }
-  inline df_iterator() { 
-    // End is when stack is empty 
+  inline df_iterator() {
+    // End is when stack is empty
   }
   inline df_iterator(NodeType *Node, SetType &S)
     : df_iterator_storage<SetType, ExtStorage>(S) {
     if (!S.count(Node)) {
-      VisitStack.push_back(std::make_pair(PointerIntTy(Node, 0), 
-                                          GT::child_begin(Node)));
+      VisitStack.push_back(
+          std::make_pair(PointerIntTy(Node, 0), GT::child_begin(Node)));
       this->Visited.insert(Node);
     }
   }
@@ -115,8 +115,8 @@ private:
         // Has our next sibling been visited?
         if (Next && this->Visited.insert(Next).second) {
           // No, do it now.
-          VisitStack.push_back(std::make_pair(PointerIntTy(Next, 0), 
-                                              GT::child_begin(Next)));
+          VisitStack.push_back(
+              std::make_pair(PointerIntTy(Next, 0), GT::child_begin(Next)));
           return;
         }
       }
@@ -195,7 +195,6 @@ public:
   }
 };
 
-
 // Provide global constructors that automatically figure out correct types...
 //
 template <class T>
@@ -237,7 +236,6 @@ iterator_range<df_ext_iterator<T, SetTy>> depth_first_ext(const T& G,
   return make_range(df_ext_begin(G, S), df_ext_end(G, S));
 }
 
-
 // Provide global definitions of inverse depth first iterators...
 template <class T,
   class SetTy = llvm::SmallPtrSet<typename GraphTraits<T>::NodeType*, 8>,
diff --git a/include/llvm/ADT/FoldingSet.h b/include/llvm/ADT/FoldingSet.h
index 52d10c1c1245..c9205396591b 100644
--- a/include/llvm/ADT/FoldingSet.h
+++ b/include/llvm/ADT/FoldingSet.h
@@ -122,9 +122,10 @@ protected:
   /// is greater than twice the number of buckets.
   unsigned NumNodes;
 
-  ~FoldingSetImpl();
-
   explicit FoldingSetImpl(unsigned Log2InitSize = 6);
+  FoldingSetImpl(FoldingSetImpl &&Arg);
+  FoldingSetImpl &operator=(FoldingSetImpl &&RHS);
+  ~FoldingSetImpl();
 
 public:
   //===--------------------------------------------------------------------===//
@@ -137,7 +138,6 @@ public:
     void *NextInFoldingSetBucket;
 
   public:
-
     Node() : NextInFoldingSetBucket(nullptr) {}
 
     // Accessors
@@ -182,13 +182,11 @@ public:
   bool empty() const { return NumNodes == 0; }
 
 private:
-
   /// GrowHashTable - Double the size of the hash table and rehash everything.
   ///
   void GrowHashTable();
 
 protected:
-
   /// GetNodeProfile - Instantiations of the FoldingSet template implement
   /// this function to gather data bits for the given node.
   virtual void GetNodeProfile(Node *N, FoldingSetNodeID &ID) const = 0;
@@ -269,6 +267,7 @@ template<typename T, typename Ctx> struct ContextualFoldingSetTrait
 class FoldingSetNodeIDRef {
   const unsigned *Data;
   size_t Size;
+
 public:
   FoldingSetNodeIDRef() : Data(nullptr), Size(0) {}
   FoldingSetNodeIDRef(const unsigned *D, size_t S) : Data(D), Size(S) {}
@@ -393,6 +392,10 @@ DefaultContextualFoldingSetTrait<T, Ctx>::ComputeHash(T &X,
 /// implementation of the folding set to the node class T.  T must be a
 /// subclass of FoldingSetNode and implement a Profile function.
 ///
+/// Note that this set type is movable and move-assignable. However, its
+/// moved-from state is not a valid state for anything other than
+/// move-assigning and destroying. This is primarily to enable movable APIs
+/// that incorporate these objects.
 template <class T> class FoldingSet final : public FoldingSetImpl {
 private:
   /// GetNodeProfile - Each instantiatation of the FoldingSet needs to provide a
@@ -417,8 +420,13 @@ private:
 
 public:
   explicit FoldingSet(unsigned Log2InitSize = 6)
-  : FoldingSetImpl(Log2InitSize)
-  {}
+      : FoldingSetImpl(Log2InitSize) {}
+
+  FoldingSet(FoldingSet &&Arg) : FoldingSetImpl(std::move(Arg)) {}
+  FoldingSet &operator=(FoldingSet &&RHS) {
+    (void)FoldingSetImpl::operator=(std::move(RHS));
+    return *this;
+  }
 
   typedef FoldingSetIterator<T> iterator;
   iterator begin() { return iterator(Buckets); }
@@ -498,7 +506,6 @@ public:
 
   Ctx getContext() const { return Context; }
 
-
   typedef FoldingSetIterator<T> iterator;
   iterator begin() { return iterator(Buckets); }
   iterator end() { return iterator(Buckets+NumBuckets); }
@@ -614,9 +621,7 @@ public:
   }
 };
 
-
-template<class T>
-class FoldingSetIterator : public FoldingSetIteratorImpl {
+template <class T> class FoldingSetIterator : public FoldingSetIteratorImpl {
 public:
   explicit FoldingSetIterator(void **Bucket) : FoldingSetIteratorImpl(Bucket) {}
 
@@ -666,8 +671,7 @@ public:
   }
 };
 
-
-template<class T>
+template <class T>
 class FoldingSetBucketIterator : public FoldingSetBucketIteratorImpl {
 public:
   explicit FoldingSetBucketIterator(void **Bucket) :
@@ -694,6 +698,7 @@ public:
 template <typename T>
 class FoldingSetNodeWrapper : public FoldingSetNode {
   T data;
+
 public:
   template <typename... Ts>
   explicit FoldingSetNodeWrapper(Ts &&... Args)
@@ -716,12 +721,12 @@ public:
 /// information that would otherwise only be required for recomputing an ID.
 class FastFoldingSetNode : public FoldingSetNode {
   FoldingSetNodeID FastID;
+
 protected:
   explicit FastFoldingSetNode(const FoldingSetNodeID &ID) : FastID(ID) {}
+
 public:
-  void Profile(FoldingSetNodeID &ID) const { 
-    ID.AddNodeID(FastID); 
-  }
+  void Profile(FoldingSetNodeID &ID) const { ID.AddNodeID(FastID); }
 };
 
 //===----------------------------------------------------------------------===//
diff --git a/include/llvm/ADT/ImmutableList.h b/include/llvm/ADT/ImmutableList.h
index 748d3e4bf9ff..a1d26bd97045 100644
--- a/include/llvm/ADT/ImmutableList.h
+++ b/include/llvm/ADT/ImmutableList.h
@@ -28,7 +28,7 @@ class ImmutableListImpl : public FoldingSetNode {
   T Head;
   const ImmutableListImpl* Tail;
 
-  ImmutableListImpl(const T& head, const ImmutableListImpl* tail = 0)
+  ImmutableListImpl(const T& head, const ImmutableListImpl* tail = nullptr)
     : Head(head), Tail(tail) {}
 
   friend class ImmutableListFactory<T>;
@@ -72,7 +72,7 @@ public:
   // This constructor should normally only be called by ImmutableListFactory<T>.
   // There may be cases, however, when one needs to extract the internal pointer
   // and reconstruct a list object from that pointer.
-  ImmutableList(const ImmutableListImpl<T>* x = 0) : X(x) {}
+  ImmutableList(const ImmutableListImpl<T>* x = nullptr) : X(x) {}
 
   const ImmutableListImpl<T>* getInternalPointer() const {
     return X;
@@ -81,7 +81,7 @@ public:
   class iterator {
     const ImmutableListImpl<T>* L;
   public:
-    iterator() : L(0) {}
+    iterator() : L(nullptr) {}
     iterator(ImmutableList l) : L(l.getInternalPointer()) {}
 
     iterator& operator++() { L = L->getTail(); return *this; }
@@ -128,7 +128,7 @@ public:
   /// getTail - Returns the tail of the list, which is another (possibly empty)
   ///  ImmutableList.
   ImmutableList getTail() {
-    return X ? X->getTail() : 0;
+    return X ? X->getTail() : nullptr;
   }
 
   void Profile(FoldingSetNodeID& ID) const {
@@ -190,7 +190,7 @@ public:
   }
 
   ImmutableList<T> getEmptyList() const {
-    return ImmutableList<T>(0);
+    return ImmutableList<T>(nullptr);
   }
 
   ImmutableList<T> create(const T& X) {
@@ -226,4 +226,4 @@ struct isPodLike<ImmutableList<T> > { static const bool value = true; };
 
 } // end llvm namespace
 
-#endif
+#endif // LLVM_ADT_IMMUTABLELIST_H
diff --git a/include/llvm/ADT/ImmutableMap.h b/include/llvm/ADT/ImmutableMap.h
index 438dec2333c5..7480cd73da61 100644
--- a/include/llvm/ADT/ImmutableMap.h
+++ b/include/llvm/ADT/ImmutableMap.h
@@ -55,7 +55,6 @@ struct ImutKeyValueInfo {
   }
 };
 
-
 template <typename KeyT, typename ValT,
           typename ValInfo = ImutKeyValueInfo<KeyT,ValT> >
 class ImmutableMap {
@@ -79,9 +78,11 @@ public:
   explicit ImmutableMap(const TreeTy* R) : Root(const_cast<TreeTy*>(R)) {
     if (Root) { Root->retain(); }
   }
+
   ImmutableMap(const ImmutableMap &X) : Root(X.Root) {
     if (Root) { Root->retain(); }
   }
+
   ImmutableMap &operator=(const ImmutableMap &X) {
     if (Root != X.Root) {
       if (X.Root) { X.Root->retain(); }
@@ -90,6 +91,7 @@ public:
     }
     return *this;
   }
+
   ~ImmutableMap() {
     if (Root) { Root->release(); }
   }
@@ -99,11 +101,10 @@ public:
     const bool Canonicalize;
 
   public:
-    Factory(bool canonicalize = true)
-      : Canonicalize(canonicalize) {}
-    
-    Factory(BumpPtrAllocator& Alloc, bool canonicalize = true)
-      : F(Alloc), Canonicalize(canonicalize) {}
+    Factory(bool canonicalize = true) : Canonicalize(canonicalize) {}
+
+    Factory(BumpPtrAllocator &Alloc, bool canonicalize = true)
+        : F(Alloc), Canonicalize(canonicalize) {}
 
     ImmutableMap getEmptyMap() { return ImmutableMap(F.getEmptyTree()); }
 
@@ -143,14 +144,12 @@ public:
     return Root;
   }
 
-  TreeTy *getRootWithoutRetain() const {
-    return Root;
-  }
-  
+  TreeTy *getRootWithoutRetain() const { return Root; }
+
   void manualRetain() {
     if (Root) Root->retain();
   }
-  
+
   void manualRelease() {
     if (Root) Root->release();
   }
@@ -224,7 +223,7 @@ public:
 
     return nullptr;
   }
-  
+
   /// getMaxElement - Returns the <key,value> pair in the ImmutableMap for
   ///  which key is the highest in the ordering of keys in the map.  This
   ///  method returns NULL if the map is empty.
@@ -260,20 +259,21 @@ public:
   typedef typename ValInfo::data_type_ref   data_type_ref;
   typedef ImutAVLTree<ValInfo>              TreeTy;
   typedef typename TreeTy::Factory          FactoryTy;
-  
+
 protected:
   TreeTy *Root;
   FactoryTy *Factory;
-  
+
 public:
   /// Constructs a map from a pointer to a tree root.  In general one
   /// should use a Factory object to create maps instead of directly
   /// invoking the constructor, but there are cases where make this
   /// constructor public is useful.
-  explicit ImmutableMapRef(const TreeTy* R, FactoryTy *F) 
-    : Root(const_cast<TreeTy*>(R)),
-      Factory(F) {
-    if (Root) { Root->retain(); }
+  explicit ImmutableMapRef(const TreeTy *R, FactoryTy *F)
+      : Root(const_cast<TreeTy *>(R)), Factory(F) {
+    if (Root) {
+      Root->retain();
+    }
   }
 
   explicit ImmutableMapRef(const ImmutableMap<KeyT, ValT> &X,
@@ -282,21 +282,21 @@ public:
       Factory(F.getTreeFactory()) {
     if (Root) { Root->retain(); }
   }
-  
-  ImmutableMapRef(const ImmutableMapRef &X)
-    : Root(X.Root),
-      Factory(X.Factory) {
-    if (Root) { Root->retain(); }
+
+  ImmutableMapRef(const ImmutableMapRef &X) : Root(X.Root), Factory(X.Factory) {
+    if (Root) {
+      Root->retain();
+    }
   }
 
   ImmutableMapRef &operator=(const ImmutableMapRef &X) {
     if (Root != X.Root) {
       if (X.Root)
         X.Root->retain();
-      
+
       if (Root)
         Root->release();
-      
+
       Root = X.Root;
       Factory = X.Factory;
     }
@@ -307,7 +307,7 @@ public:
     if (Root)
       Root->release();
   }
-  
+
   static inline ImmutableMapRef getEmptyMap(FactoryTy *F) {
     return ImmutableMapRef(0, F);
   }
@@ -329,31 +329,34 @@ public:
     TreeTy *NewT = Factory->remove(Root, K);
     return ImmutableMapRef(NewT, Factory);
   }
-  
+
   bool contains(key_type_ref K) const {
     return Root ? Root->contains(K) : false;
   }
-  
+
   ImmutableMap<KeyT, ValT> asImmutableMap() const {
     return ImmutableMap<KeyT, ValT>(Factory->getCanonicalTree(Root));
   }
-  
+
   bool operator==(const ImmutableMapRef &RHS) const {
     return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root;
   }
-  
+
   bool operator!=(const ImmutableMapRef &RHS) const {
     return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;
   }
-    
+
   bool isEmpty() const { return !Root; }
-    
+
   //===--------------------------------------------------===//
   // For testing.
   //===--------------------------------------------------===//
-  
-  void verify() const { if (Root) Root->verify(); }
-  
+
+  void verify() const {
+    if (Root)
+      Root->verify();
+  }
+
   //===--------------------------------------------------===//
   // Iterators.
   //===--------------------------------------------------===//
@@ -370,38 +373,36 @@ public:
 
   iterator begin() const { return iterator(Root); }
   iterator end() const { return iterator(); }
-  
-  data_type* lookup(key_type_ref K) const {
+
+  data_type *lookup(key_type_ref K) const {
     if (Root) {
       TreeTy* T = Root->find(K);
       if (T) return &T->getValue().second;
     }
-    
-    return 0;
+
+    return nullptr;
   }
-  
+
   /// getMaxElement - Returns the <key,value> pair in the ImmutableMap for
   ///  which key is the highest in the ordering of keys in the map.  This
   ///  method returns NULL if the map is empty.
   value_type* getMaxElement() const {
     return Root ? &(Root->getMaxElement()->getValue()) : 0;
   }
-  
+
   //===--------------------------------------------------===//
   // Utility methods.
   //===--------------------------------------------------===//
-  
+
   unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
-  
-  static inline void Profile(FoldingSetNodeID& ID, const ImmutableMapRef &M) {
+
+  static inline void Profile(FoldingSetNodeID &ID, const ImmutableMapRef &M) {
     ID.AddPointer(M.Root);
   }
-  
-  inline void Profile(FoldingSetNodeID& ID) const {
-    return Profile(ID, *this);
-  }
+
+  inline void Profile(FoldingSetNodeID &ID) const { return Profile(ID, *this); }
 };
-  
+
 } // end namespace llvm
 
-#endif
+#endif // LLVM_ADT_IMMUTABLEMAP_H
diff --git a/include/llvm/ADT/IntrusiveRefCntPtr.h b/include/llvm/ADT/IntrusiveRefCntPtr.h
index 65b2da793d7c..8057ec10be00 100644
--- a/include/llvm/ADT/IntrusiveRefCntPtr.h
+++ b/include/llvm/ADT/IntrusiveRefCntPtr.h
@@ -154,7 +154,7 @@ public:
 
     template <class X>
     IntrusiveRefCntPtr(IntrusiveRefCntPtr<X>&& S) : Obj(S.get()) {
-      S.Obj = 0;
+      S.Obj = nullptr;
     }
 
     template <class X>
@@ -190,7 +190,7 @@ public:
     }
 
     void resetWithoutRelease() {
-      Obj = 0;
+      Obj = nullptr;
     }
 
   private:
diff --git a/include/llvm/ADT/Optional.h b/include/llvm/ADT/Optional.h
index 855ab890392e..d9acaf6d23b0 100644
--- a/include/llvm/ADT/Optional.h
+++ b/include/llvm/ADT/Optional.h
@@ -159,6 +159,25 @@ template <typename T> struct isPodLike<Optional<T> > {
 template<typename T, typename U>
 void operator==(const Optional<T> &X, const Optional<U> &Y);
 
+template<typename T>
+bool operator==(const Optional<T> &X, NoneType) {
+  return !X.hasValue();
+}
+
+template<typename T>
+bool operator==(NoneType, const Optional<T> &X) {
+  return X == None;
+}
+
+template<typename T>
+bool operator!=(const Optional<T> &X, NoneType) {
+  return !(X == None);
+}
+
+template<typename T>
+bool operator!=(NoneType, const Optional<T> &X) {
+  return X != None;
+}
 /// \brief Poison comparison between two \c Optional objects. Clients needs to
 /// explicitly compare the underlying values and account for empty \c Optional
 /// objects.
diff --git a/include/llvm/ADT/PackedVector.h b/include/llvm/ADT/PackedVector.h
index 1ae2a77e7eaf..09267173fd77 100644
--- a/include/llvm/ADT/PackedVector.h
+++ b/include/llvm/ADT/PackedVector.h
@@ -83,9 +83,9 @@ public:
     PackedVector &Vec;
     const unsigned Idx;
 
-    reference();  // Undefined    
+    reference(); // Undefined
   public:
-    reference(PackedVector &vec, unsigned idx) : Vec(vec), Idx(idx) { }    
+    reference(PackedVector &vec, unsigned idx) : Vec(vec), Idx(idx) {}
 
     reference &operator=(T val) {
       Vec.setValue(Vec.Bits, Idx, val);
@@ -96,16 +96,16 @@ public:
     }
   };
 
-  PackedVector() { }
+  PackedVector() = default;
   explicit PackedVector(unsigned size) : Bits(size << (BitNum-1)) { }
 
   bool empty() const { return Bits.empty(); }
 
-  unsigned size() const { return Bits.size() >> (BitNum-1); }
-  
+  unsigned size() const { return Bits.size() >> (BitNum - 1); }
+
   void clear() { Bits.clear(); }
-  
-  void resize(unsigned N) { Bits.resize(N << (BitNum-1)); }
+
+  void resize(unsigned N) { Bits.resize(N << (BitNum - 1)); }
 
   void reserve(unsigned N) { Bits.reserve(N << (BitNum-1)); }
 
@@ -135,24 +135,14 @@ public:
     return Bits != RHS.Bits;
   }
 
-  const PackedVector &operator=(const PackedVector &RHS) {
-    Bits = RHS.Bits;
-    return *this;
-  }
-
   PackedVector &operator|=(const PackedVector &RHS) {
     Bits |= RHS.Bits;
     return *this;
   }
-
-  void swap(PackedVector &RHS) {
-    Bits.swap(RHS.Bits);
-  }
 };
 
-// Leave BitNum=0 undefined. 
-template <typename T>
-class PackedVector<T, 0>;
+// Leave BitNum=0 undefined.
+template <typename T> class PackedVector<T, 0>;
 
 } // end llvm namespace
 
diff --git a/include/llvm/ADT/PointerIntPair.h b/include/llvm/ADT/PointerIntPair.h
index 45a40db85c04..0058d85d1ae4 100644
--- a/include/llvm/ADT/PointerIntPair.h
+++ b/include/llvm/ADT/PointerIntPair.h
@@ -21,8 +21,10 @@
 
 namespace llvm {
 
-template<typename T>
-struct DenseMapInfo;
+template <typename T> struct DenseMapInfo;
+
+template <typename PointerT, unsigned IntBits, typename PtrTraits>
+struct PointerIntPairInfo;
 
 /// PointerIntPair - This class implements a pair of a pointer and small
 /// integer.  It is designed to represent this in the space required by one
@@ -38,83 +40,35 @@ struct DenseMapInfo;
 ///   PointerIntPair<PointerIntPair<void*, 1, bool>, 1, bool>
 /// ... and the two bools will land in different bits.
 ///
-template <typename PointerTy, unsigned IntBits, typename IntType=unsigned,
-          typename PtrTraits = PointerLikeTypeTraits<PointerTy> >
+template <typename PointerTy, unsigned IntBits, typename IntType = unsigned,
+          typename PtrTraits = PointerLikeTypeTraits<PointerTy>,
+          typename Info = PointerIntPairInfo<PointerTy, IntBits, PtrTraits>>
 class PointerIntPair {
   intptr_t Value;
-  static_assert(PtrTraits::NumLowBitsAvailable <
-                std::numeric_limits<uintptr_t>::digits,
-                "cannot use a pointer type that has all bits free");
-  static_assert(IntBits <= PtrTraits::NumLowBitsAvailable,
-                "PointerIntPair with integer size too large for pointer");
-  enum : uintptr_t {
-    /// PointerBitMask - The bits that come from the pointer.
-    PointerBitMask =
-      ~(uintptr_t)(((intptr_t)1 << PtrTraits::NumLowBitsAvailable)-1),
 
-    /// IntShift - The number of low bits that we reserve for other uses, and
-    /// keep zero.
-    IntShift = (uintptr_t)PtrTraits::NumLowBitsAvailable-IntBits,
-    
-    /// IntMask - This is the unshifted mask for valid bits of the int type.
-    IntMask = (uintptr_t)(((intptr_t)1 << IntBits)-1),
-    
-    // ShiftedIntMask - This is the bits for the integer shifted in place.
-    ShiftedIntMask = (uintptr_t)(IntMask << IntShift)
-  };
 public:
   PointerIntPair() : Value(0) {}
   PointerIntPair(PointerTy PtrVal, IntType IntVal) {
     setPointerAndInt(PtrVal, IntVal);
   }
-  explicit PointerIntPair(PointerTy PtrVal) {
-    initWithPointer(PtrVal);
-  }
+  explicit PointerIntPair(PointerTy PtrVal) { initWithPointer(PtrVal); }
 
-  PointerTy getPointer() const {
-    return PtrTraits::getFromVoidPointer(
-                         reinterpret_cast<void*>(Value & PointerBitMask));
-  }
+  PointerTy getPointer() const { return Info::getPointer(Value); }
 
-  IntType getInt() const {
-    return (IntType)((Value >> IntShift) & IntMask);
-  }
+  IntType getInt() const { return (IntType)Info::getInt(Value); }
 
   void setPointer(PointerTy PtrVal) {
-    intptr_t PtrWord
-      = reinterpret_cast<intptr_t>(PtrTraits::getAsVoidPointer(PtrVal));
-    assert((PtrWord & ~PointerBitMask) == 0 &&
-           "Pointer is not sufficiently aligned");
-    // Preserve all low bits, just update the pointer.
-    Value = PtrWord | (Value & ~PointerBitMask);
+    Value = Info::updatePointer(Value, PtrVal);
   }
 
-  void setInt(IntType IntVal) {
-    intptr_t IntWord = static_cast<intptr_t>(IntVal);
-    assert((IntWord & ~IntMask) == 0 && "Integer too large for field");
-    
-    // Preserve all bits other than the ones we are updating.
-    Value &= ~ShiftedIntMask;     // Remove integer field.
-    Value |= IntWord << IntShift;  // Set new integer.
-  }
+  void setInt(IntType IntVal) { Value = Info::updateInt(Value, IntVal); }
 
   void initWithPointer(PointerTy PtrVal) {
-    intptr_t PtrWord
-      = reinterpret_cast<intptr_t>(PtrTraits::getAsVoidPointer(PtrVal));
-    assert((PtrWord & ~PointerBitMask) == 0 &&
-           "Pointer is not sufficiently aligned");
-    Value = PtrWord;
+    Value = Info::updatePointer(0, PtrVal);
   }
 
   void setPointerAndInt(PointerTy PtrVal, IntType IntVal) {
-    intptr_t PtrWord
-      = reinterpret_cast<intptr_t>(PtrTraits::getAsVoidPointer(PtrVal));
-    assert((PtrWord & ~PointerBitMask) == 0 &&
-           "Pointer is not sufficiently aligned");
-    intptr_t IntWord = static_cast<intptr_t>(IntVal);
-    assert((IntWord & ~IntMask) == 0 && "Integer too large for field");
-
-    Value = PtrWord | (IntWord << IntShift);
+    Value = Info::updateInt(Info::updatePointer(0, PtrVal), IntVal);
   }
 
   PointerTy const *getAddrOfPointer() const {
@@ -128,11 +82,15 @@ public:
     return reinterpret_cast<PointerTy *>(&Value);
   }
 
-  void *getOpaqueValue() const { return reinterpret_cast<void*>(Value); }
-  void setFromOpaqueValue(void *Val) { Value = reinterpret_cast<intptr_t>(Val);}
+  void *getOpaqueValue() const { return reinterpret_cast<void *>(Value); }
+  void setFromOpaqueValue(void *Val) {
+    Value = reinterpret_cast<intptr_t>(Val);
+  }
 
   static PointerIntPair getFromOpaqueValue(void *V) {
-    PointerIntPair P; P.setFromOpaqueValue(V); return P; 
+    PointerIntPair P;
+    P.setFromOpaqueValue(V);
+    return P;
   }
 
   // Allow PointerIntPairs to be created from const void * if and only if the
@@ -142,23 +100,81 @@ public:
     return getFromOpaqueValue(const_cast<void *>(V));
   }
 
-  bool operator==(const PointerIntPair &RHS) const {return Value == RHS.Value;}
-  bool operator!=(const PointerIntPair &RHS) const {return Value != RHS.Value;}
-  bool operator<(const PointerIntPair &RHS) const {return Value < RHS.Value;}
-  bool operator>(const PointerIntPair &RHS) const {return Value > RHS.Value;}
-  bool operator<=(const PointerIntPair &RHS) const {return Value <= RHS.Value;}
-  bool operator>=(const PointerIntPair &RHS) const {return Value >= RHS.Value;}
+  bool operator==(const PointerIntPair &RHS) const {
+    return Value == RHS.Value;
+  }
+  bool operator!=(const PointerIntPair &RHS) const {
+    return Value != RHS.Value;
+  }
+  bool operator<(const PointerIntPair &RHS) const { return Value < RHS.Value; }
+  bool operator>(const PointerIntPair &RHS) const { return Value > RHS.Value; }
+  bool operator<=(const PointerIntPair &RHS) const {
+    return Value <= RHS.Value;
+  }
+  bool operator>=(const PointerIntPair &RHS) const {
+    return Value >= RHS.Value;
+  }
+};
+
+template <typename PointerT, unsigned IntBits, typename PtrTraits>
+struct PointerIntPairInfo {
+  static_assert(PtrTraits::NumLowBitsAvailable <
+                    std::numeric_limits<uintptr_t>::digits,
+                "cannot use a pointer type that has all bits free");
+  static_assert(IntBits <= PtrTraits::NumLowBitsAvailable,
+                "PointerIntPair with integer size too large for pointer");
+  enum : uintptr_t {
+    /// PointerBitMask - The bits that come from the pointer.
+    PointerBitMask =
+        ~(uintptr_t)(((intptr_t)1 << PtrTraits::NumLowBitsAvailable) - 1),
+
+    /// IntShift - The number of low bits that we reserve for other uses, and
+    /// keep zero.
+    IntShift = (uintptr_t)PtrTraits::NumLowBitsAvailable - IntBits,
+
+    /// IntMask - This is the unshifted mask for valid bits of the int type.
+    IntMask = (uintptr_t)(((intptr_t)1 << IntBits) - 1),
+
+    // ShiftedIntMask - This is the bits for the integer shifted in place.
+    ShiftedIntMask = (uintptr_t)(IntMask << IntShift)
+  };
+
+  static PointerT getPointer(intptr_t Value) {
+    return PtrTraits::getFromVoidPointer(
+        reinterpret_cast<void *>(Value & PointerBitMask));
+  }
+
+  static intptr_t getInt(intptr_t Value) {
+    return (Value >> IntShift) & IntMask;
+  }
+
+  static intptr_t updatePointer(intptr_t OrigValue, PointerT Ptr) {
+    intptr_t PtrWord =
+        reinterpret_cast<intptr_t>(PtrTraits::getAsVoidPointer(Ptr));
+    assert((PtrWord & ~PointerBitMask) == 0 &&
+           "Pointer is not sufficiently aligned");
+    // Preserve all low bits, just update the pointer.
+    return PtrWord | (OrigValue & ~PointerBitMask);
+  }
+
+  static intptr_t updateInt(intptr_t OrigValue, intptr_t Int) {
+    intptr_t IntWord = static_cast<intptr_t>(Int);
+    assert((IntWord & ~IntMask) == 0 && "Integer too large for field");
+
+    // Preserve all bits other than the ones we are updating.
+    return (OrigValue & ~ShiftedIntMask) | IntWord << IntShift;
+  }
 };
 
 template <typename T> struct isPodLike;
-template<typename PointerTy, unsigned IntBits, typename IntType>
-struct isPodLike<PointerIntPair<PointerTy, IntBits, IntType> > {
-   static const bool value = true;
+template <typename PointerTy, unsigned IntBits, typename IntType>
+struct isPodLike<PointerIntPair<PointerTy, IntBits, IntType>> {
+  static const bool value = true;
 };
-  
+
 // Provide specialization of DenseMapInfo for PointerIntPair.
-template<typename PointerTy, unsigned IntBits, typename IntType>
-struct DenseMapInfo<PointerIntPair<PointerTy, IntBits, IntType> > {
+template <typename PointerTy, unsigned IntBits, typename IntType>
+struct DenseMapInfo<PointerIntPair<PointerTy, IntBits, IntType>> {
   typedef PointerIntPair<PointerTy, IntBits, IntType> Ty;
   static Ty getEmptyKey() {
     uintptr_t Val = static_cast<uintptr_t>(-1);
@@ -178,10 +194,10 @@ struct DenseMapInfo<PointerIntPair<PointerTy, IntBits, IntType> > {
 };
 
 // Teach SmallPtrSet that PointerIntPair is "basically a pointer".
-template<typename PointerTy, unsigned IntBits, typename IntType,
-         typename PtrTraits>
-class PointerLikeTypeTraits<PointerIntPair<PointerTy, IntBits, IntType,
-                                           PtrTraits> > {
+template <typename PointerTy, unsigned IntBits, typename IntType,
+          typename PtrTraits>
+class PointerLikeTypeTraits<
+    PointerIntPair<PointerTy, IntBits, IntType, PtrTraits>> {
 public:
   static inline void *
   getAsVoidPointer(const PointerIntPair<PointerTy, IntBits, IntType> &P) {
@@ -195,9 +211,7 @@ public:
   getFromVoidPointer(const void *P) {
     return PointerIntPair<PointerTy, IntBits, IntType>::getFromOpaqueValue(P);
   }
-  enum {
-    NumLowBitsAvailable = PtrTraits::NumLowBitsAvailable - IntBits
-  };
+  enum { NumLowBitsAvailable = PtrTraits::NumLowBitsAvailable - IntBits };
 };
 
 } // end namespace llvm
diff --git a/include/llvm/ADT/PointerUnion.h b/include/llvm/ADT/PointerUnion.h
index f27b81113ec5..6b3fe5749ad5 100644
--- a/include/llvm/ADT/PointerUnion.h
+++ b/include/llvm/ADT/PointerUnion.h
@@ -21,492 +21,454 @@
 
 namespace llvm {
 
-  template <typename T>
-  struct PointerUnionTypeSelectorReturn {
-    typedef T Return;
-  };
+template <typename T> struct PointerUnionTypeSelectorReturn {
+  typedef T Return;
+};
 
-  /// \brief Get a type based on whether two types are the same or not. For:
-  /// @code
-  /// typedef typename PointerUnionTypeSelector<T1, T2, EQ, NE>::Return Ret;
-  /// @endcode
-  /// Ret will be EQ type if T1 is same as T2 or NE type otherwise.
-  template <typename T1, typename T2, typename RET_EQ, typename RET_NE>
-  struct PointerUnionTypeSelector {
-    typedef typename PointerUnionTypeSelectorReturn<RET_NE>::Return Return;
-  };
+/// Get a type based on whether two types are the same or not.
+///
+/// For:
+/// 
+/// \code
+///   typedef typename PointerUnionTypeSelector<T1, T2, EQ, NE>::Return Ret;
+/// \endcode
+///
+/// Ret will be EQ type if T1 is same as T2 or NE type otherwise.
+template <typename T1, typename T2, typename RET_EQ, typename RET_NE>
+struct PointerUnionTypeSelector {
+  typedef typename PointerUnionTypeSelectorReturn<RET_NE>::Return Return;
+};
 
-  template <typename T, typename RET_EQ, typename RET_NE>
-  struct PointerUnionTypeSelector<T, T, RET_EQ, RET_NE> {
-    typedef typename PointerUnionTypeSelectorReturn<RET_EQ>::Return Return;
-  };
+template <typename T, typename RET_EQ, typename RET_NE>
+struct PointerUnionTypeSelector<T, T, RET_EQ, RET_NE> {
+  typedef typename PointerUnionTypeSelectorReturn<RET_EQ>::Return Return;
+};
 
-  template <typename T1, typename T2, typename RET_EQ, typename RET_NE>
-  struct PointerUnionTypeSelectorReturn<
-                            PointerUnionTypeSelector<T1, T2, RET_EQ, RET_NE> > {
-    typedef typename PointerUnionTypeSelector<T1, T2, RET_EQ, RET_NE>::Return
-        Return;
-  };
+template <typename T1, typename T2, typename RET_EQ, typename RET_NE>
+struct PointerUnionTypeSelectorReturn<
+    PointerUnionTypeSelector<T1, T2, RET_EQ, RET_NE>> {
+  typedef
+      typename PointerUnionTypeSelector<T1, T2, RET_EQ, RET_NE>::Return Return;
+};
 
-  /// Provide PointerLikeTypeTraits for void* that is used by PointerUnion
-  /// for the two template arguments.
-  template <typename PT1, typename PT2>
-  class PointerUnionUIntTraits {
-  public:
-    static inline void *getAsVoidPointer(void *P) { return P; }
-    static inline void *getFromVoidPointer(void *P) { return P; }
-    enum {
-      PT1BitsAv = (int)(PointerLikeTypeTraits<PT1>::NumLowBitsAvailable),
-      PT2BitsAv = (int)(PointerLikeTypeTraits<PT2>::NumLowBitsAvailable),
-      NumLowBitsAvailable = PT1BitsAv < PT2BitsAv ? PT1BitsAv : PT2BitsAv
-    };
+/// Provide PointerLikeTypeTraits for void* that is used by PointerUnion
+/// for the two template arguments.
+template <typename PT1, typename PT2> class PointerUnionUIntTraits {
+public:
+  static inline void *getAsVoidPointer(void *P) { return P; }
+  static inline void *getFromVoidPointer(void *P) { return P; }
+  enum {
+    PT1BitsAv = (int)(PointerLikeTypeTraits<PT1>::NumLowBitsAvailable),
+    PT2BitsAv = (int)(PointerLikeTypeTraits<PT2>::NumLowBitsAvailable),
+    NumLowBitsAvailable = PT1BitsAv < PT2BitsAv ? PT1BitsAv : PT2BitsAv
   };
+};
 
-  /// PointerUnion - This implements a discriminated union of two pointer types,
-  /// and keeps the discriminator bit-mangled into the low bits of the pointer.
-  /// This allows the implementation to be extremely efficient in space, but
-  /// permits a very natural and type-safe API.
-  ///
-  /// Common use patterns would be something like this:
-  ///    PointerUnion<int*, float*> P;
-  ///    P = (int*)0;
-  ///    printf("%d %d", P.is<int*>(), P.is<float*>());  // prints "1 0"
-  ///    X = P.get<int*>();     // ok.
-  ///    Y = P.get<float*>();   // runtime assertion failure.
-  ///    Z = P.get<double*>();  // compile time failure.
-  ///    P = (float*)0;
-  ///    Y = P.get<float*>();   // ok.
-  ///    X = P.get<int*>();     // runtime assertion failure.
-  template <typename PT1, typename PT2>
-  class PointerUnion {
-  public:
-    typedef PointerIntPair<void*, 1, bool,
-                           PointerUnionUIntTraits<PT1,PT2> > ValTy;
-  private:
-    ValTy Val;
+/// A discriminated union of two pointer types, with the discriminator in the
+/// low bit of the pointer.
+///
+/// This implementation is extremely efficient in space due to leveraging the
+/// low bits of the pointer, while exposing a natural and type-safe API.
+///
+/// Common use patterns would be something like this:
+///    PointerUnion<int*, float*> P;
+///    P = (int*)0;
+///    printf("%d %d", P.is<int*>(), P.is<float*>());  // prints "1 0"
+///    X = P.get<int*>();     // ok.
+///    Y = P.get<float*>();   // runtime assertion failure.
+///    Z = P.get<double*>();  // compile time failure.
+///    P = (float*)0;
+///    Y = P.get<float*>();   // ok.
+///    X = P.get<int*>();     // runtime assertion failure.
+template <typename PT1, typename PT2> class PointerUnion {
+public:
+  typedef PointerIntPair<void *, 1, bool, PointerUnionUIntTraits<PT1, PT2>>
+      ValTy;
 
-    struct IsPT1 {
-      static const int Num = 0;
-    };
-    struct IsPT2 {
-      static const int Num = 1;
-    };
-    template <typename T>
-    struct UNION_DOESNT_CONTAIN_TYPE { };
+private:
+  ValTy Val;
 
-  public:
-    PointerUnion() {}
+  struct IsPT1 {
+    static const int Num = 0;
+  };
+  struct IsPT2 {
+    static const int Num = 1;
+  };
+  template <typename T> struct UNION_DOESNT_CONTAIN_TYPE {};
 
-    PointerUnion(PT1 V) : Val(
-      const_cast<void *>(PointerLikeTypeTraits<PT1>::getAsVoidPointer(V))) {
-    }
-    PointerUnion(PT2 V) : Val(
-      const_cast<void *>(PointerLikeTypeTraits<PT2>::getAsVoidPointer(V)), 1) {
-    }
+public:
+  PointerUnion() {}
 
-    /// isNull - Return true if the pointer held in the union is null,
-    /// regardless of which type it is.
-    bool isNull() const {
-      // Convert from the void* to one of the pointer types, to make sure that
-      // we recursively strip off low bits if we have a nested PointerUnion.
-      return !PointerLikeTypeTraits<PT1>::getFromVoidPointer(Val.getPointer());
-    }
-    explicit operator bool() const { return !isNull(); }
+  PointerUnion(PT1 V)
+      : Val(const_cast<void *>(
+            PointerLikeTypeTraits<PT1>::getAsVoidPointer(V))) {}
+  PointerUnion(PT2 V)
+      : Val(const_cast<void *>(PointerLikeTypeTraits<PT2>::getAsVoidPointer(V)),
+            1) {}
 
-    /// is<T>() return true if the Union currently holds the type matching T.
-    template<typename T>
-    int is() const {
-      typedef typename
-        ::llvm::PointerUnionTypeSelector<PT1, T, IsPT1,
-          ::llvm::PointerUnionTypeSelector<PT2, T, IsPT2,
-                                    UNION_DOESNT_CONTAIN_TYPE<T> > >::Return Ty;
-      int TyNo = Ty::Num;
-      return static_cast<int>(Val.getInt()) == TyNo;
-    }
+  /// Test if the pointer held in the union is null, regardless of
+  /// which type it is.
+  bool isNull() const {
+    // Convert from the void* to one of the pointer types, to make sure that
+    // we recursively strip off low bits if we have a nested PointerUnion.
+    return !PointerLikeTypeTraits<PT1>::getFromVoidPointer(Val.getPointer());
+  }
+  explicit operator bool() const { return !isNull(); }
 
-    /// get<T>() - Return the value of the specified pointer type. If the
-    /// specified pointer type is incorrect, assert.
-    template<typename T>
-    T get() const {
-      assert(is<T>() && "Invalid accessor called");
-      return PointerLikeTypeTraits<T>::getFromVoidPointer(Val.getPointer());
-    }
+  /// Test if the Union currently holds the type matching T.
+  template <typename T> int is() const {
+    typedef typename ::llvm::PointerUnionTypeSelector<
+        PT1, T, IsPT1, ::llvm::PointerUnionTypeSelector<
+                           PT2, T, IsPT2, UNION_DOESNT_CONTAIN_TYPE<T>>>::Return
+        Ty;
+    int TyNo = Ty::Num;
+    return static_cast<int>(Val.getInt()) == TyNo;
+  }
 
-    /// dyn_cast<T>() - If the current value is of the specified pointer type,
-    /// return it, otherwise return null.
-    template<typename T>
-    T dyn_cast() const {
-      if (is<T>()) return get<T>();
-      return T();
-    }
+  /// Returns the value of the specified pointer type.
+  ///
+  /// If the specified pointer type is incorrect, assert.
+  template <typename T> T get() const {
+    assert(is<T>() && "Invalid accessor called");
+    return PointerLikeTypeTraits<T>::getFromVoidPointer(Val.getPointer());
+  }
 
-    /// \brief If the union is set to the first pointer type get an address
-    /// pointing to it.
-    PT1 const *getAddrOfPtr1() const {
-      return const_cast<PointerUnion *>(this)->getAddrOfPtr1();
-    }
+  /// Returns the current pointer if it is of the specified pointer type,
+  /// otherwises returns null.
+  template <typename T> T dyn_cast() const {
+    if (is<T>())
+      return get<T>();
+    return T();
+  }
 
-    /// \brief If the union is set to the first pointer type get an address
-    /// pointing to it.
-    PT1 *getAddrOfPtr1() {
-      assert(is<PT1>() && "Val is not the first pointer");
-      assert(get<PT1>() == Val.getPointer() &&
-         "Can't get the address because PointerLikeTypeTraits changes the ptr");
-      return (PT1 *)Val.getAddrOfPointer();
-    }
+  /// If the union is set to the first pointer type get an address pointing to
+  /// it.
+  PT1 const *getAddrOfPtr1() const {
+    return const_cast<PointerUnion *>(this)->getAddrOfPtr1();
+  }
 
-    /// \brief Assignment from nullptr which just clears the union.
-    const PointerUnion &operator=(std::nullptr_t) {
-      Val.initWithPointer(nullptr);
-      return *this;
-    }
+  /// If the union is set to the first pointer type get an address pointing to
+  /// it.
+  PT1 *getAddrOfPtr1() {
+    assert(is<PT1>() && "Val is not the first pointer");
+    assert(
+        get<PT1>() == Val.getPointer() &&
+        "Can't get the address because PointerLikeTypeTraits changes the ptr");
+    return (PT1 *)Val.getAddrOfPointer();
+  }
 
-    /// Assignment operators - Allow assigning into this union from either
-    /// pointer type, setting the discriminator to remember what it came from.
-    const PointerUnion &operator=(const PT1 &RHS) {
-      Val.initWithPointer(
-         const_cast<void *>(PointerLikeTypeTraits<PT1>::getAsVoidPointer(RHS)));
-      return *this;
-    }
-    const PointerUnion &operator=(const PT2 &RHS) {
-      Val.setPointerAndInt(
+  /// Assignment from nullptr which just clears the union.
+  const PointerUnion &operator=(std::nullptr_t) {
+    Val.initWithPointer(nullptr);
+    return *this;
+  }
+
+  /// Assignment operators - Allow assigning into this union from either
+  /// pointer type, setting the discriminator to remember what it came from.
+  const PointerUnion &operator=(const PT1 &RHS) {
+    Val.initWithPointer(
+        const_cast<void *>(PointerLikeTypeTraits<PT1>::getAsVoidPointer(RHS)));
+    return *this;
+  }
+  const PointerUnion &operator=(const PT2 &RHS) {
+    Val.setPointerAndInt(
         const_cast<void *>(PointerLikeTypeTraits<PT2>::getAsVoidPointer(RHS)),
         1);
-      return *this;
-    }
-
-    void *getOpaqueValue() const { return Val.getOpaqueValue(); }
-    static inline PointerUnion getFromOpaqueValue(void *VP) {
-      PointerUnion V;
-      V.Val = ValTy::getFromOpaqueValue(VP);
-      return V;
-    }
-  };
-
-  template<typename PT1, typename PT2>
-  static bool operator==(PointerUnion<PT1, PT2> lhs,
-                         PointerUnion<PT1, PT2> rhs) {
-    return lhs.getOpaqueValue() == rhs.getOpaqueValue();
+    return *this;
   }
 
-  template<typename PT1, typename PT2>
-  static bool operator!=(PointerUnion<PT1, PT2> lhs,
-                         PointerUnion<PT1, PT2> rhs) {
-    return lhs.getOpaqueValue() != rhs.getOpaqueValue();
+  void *getOpaqueValue() const { return Val.getOpaqueValue(); }
+  static inline PointerUnion getFromOpaqueValue(void *VP) {
+    PointerUnion V;
+    V.Val = ValTy::getFromOpaqueValue(VP);
+    return V;
   }
+};
+
+template <typename PT1, typename PT2>
+static bool operator==(PointerUnion<PT1, PT2> lhs, PointerUnion<PT1, PT2> rhs) {
+  return lhs.getOpaqueValue() == rhs.getOpaqueValue();
+}
 
-  template<typename PT1, typename PT2>
-  static bool operator<(PointerUnion<PT1, PT2> lhs,
-                        PointerUnion<PT1, PT2> rhs) {
-    return lhs.getOpaqueValue() < rhs.getOpaqueValue();
+template <typename PT1, typename PT2>
+static bool operator!=(PointerUnion<PT1, PT2> lhs, PointerUnion<PT1, PT2> rhs) {
+  return lhs.getOpaqueValue() != rhs.getOpaqueValue();
+}
+
+template <typename PT1, typename PT2>
+static bool operator<(PointerUnion<PT1, PT2> lhs, PointerUnion<PT1, PT2> rhs) {
+  return lhs.getOpaqueValue() < rhs.getOpaqueValue();
+}
+
+// Teach SmallPtrSet that PointerUnion is "basically a pointer", that has
+// # low bits available = min(PT1bits,PT2bits)-1.
+template <typename PT1, typename PT2>
+class PointerLikeTypeTraits<PointerUnion<PT1, PT2>> {
+public:
+  static inline void *getAsVoidPointer(const PointerUnion<PT1, PT2> &P) {
+    return P.getOpaqueValue();
   }
+  static inline PointerUnion<PT1, PT2> getFromVoidPointer(void *P) {
+    return PointerUnion<PT1, PT2>::getFromOpaqueValue(P);
+  }
+
+  // The number of bits available are the min of the two pointer types.
+  enum {
+    NumLowBitsAvailable = PointerLikeTypeTraits<
+        typename PointerUnion<PT1, PT2>::ValTy>::NumLowBitsAvailable
+  };
+};
 
-  // Teach SmallPtrSet that PointerUnion is "basically a pointer", that has
-  // # low bits available = min(PT1bits,PT2bits)-1.
-  template<typename PT1, typename PT2>
-  class PointerLikeTypeTraits<PointerUnion<PT1, PT2> > {
-  public:
-    static inline void *
-    getAsVoidPointer(const PointerUnion<PT1, PT2> &P) {
-      return P.getOpaqueValue();
+/// A pointer union of three pointer types. See documentation for PointerUnion
+/// for usage.
+template <typename PT1, typename PT2, typename PT3> class PointerUnion3 {
+public:
+  typedef PointerUnion<PT1, PT2> InnerUnion;
+  typedef PointerUnion<InnerUnion, PT3> ValTy;
+
+private:
+  ValTy Val;
+
+  struct IsInnerUnion {
+    ValTy Val;
+    IsInnerUnion(ValTy val) : Val(val) {}
+    template <typename T> int is() const {
+      return Val.template is<InnerUnion>() &&
+             Val.template get<InnerUnion>().template is<T>();
     }
-    static inline PointerUnion<PT1, PT2>
-    getFromVoidPointer(void *P) {
-      return PointerUnion<PT1, PT2>::getFromOpaqueValue(P);
+    template <typename T> T get() const {
+      return Val.template get<InnerUnion>().template get<T>();
     }
-
-    // The number of bits available are the min of the two pointer types.
-    enum {
-      NumLowBitsAvailable =
-        PointerLikeTypeTraits<typename PointerUnion<PT1,PT2>::ValTy>
-          ::NumLowBitsAvailable
-    };
   };
 
-
-  /// PointerUnion3 - This is a pointer union of three pointer types.  See
-  /// documentation for PointerUnion for usage.
-  template <typename PT1, typename PT2, typename PT3>
-  class PointerUnion3 {
-  public:
-    typedef PointerUnion<PT1, PT2> InnerUnion;
-    typedef PointerUnion<InnerUnion, PT3> ValTy;
-  private:
+  struct IsPT3 {
     ValTy Val;
+    IsPT3(ValTy val) : Val(val) {}
+    template <typename T> int is() const { return Val.template is<T>(); }
+    template <typename T> T get() const { return Val.template get<T>(); }
+  };
 
-    struct IsInnerUnion {
-      ValTy Val;
-      IsInnerUnion(ValTy val) : Val(val) { }
-      template<typename T>
-      int is() const {
-        return Val.template is<InnerUnion>() &&
-               Val.template get<InnerUnion>().template is<T>();
-      }
-      template<typename T>
-      T get() const {
-        return Val.template get<InnerUnion>().template get<T>();
-      }
-    };
+public:
+  PointerUnion3() {}
 
-    struct IsPT3 {
-      ValTy Val;
-      IsPT3(ValTy val) : Val(val) { }
-      template<typename T>
-      int is() const {
-        return Val.template is<T>();
-      }
-      template<typename T>
-      T get() const {
-        return Val.template get<T>();
-      }
-    };
+  PointerUnion3(PT1 V) { Val = InnerUnion(V); }
+  PointerUnion3(PT2 V) { Val = InnerUnion(V); }
+  PointerUnion3(PT3 V) { Val = V; }
 
-  public:
-    PointerUnion3() {}
+  /// Test if the pointer held in the union is null, regardless of
+  /// which type it is.
+  bool isNull() const { return Val.isNull(); }
+  explicit operator bool() const { return !isNull(); }
 
-    PointerUnion3(PT1 V) {
-      Val = InnerUnion(V);
-    }
-    PointerUnion3(PT2 V) {
-      Val = InnerUnion(V);
-    }
-    PointerUnion3(PT3 V) {
-      Val = V;
-    }
+  /// Test if the Union currently holds the type matching T.
+  template <typename T> int is() const {
+    // If T is PT1/PT2 choose IsInnerUnion otherwise choose IsPT3.
+    typedef typename ::llvm::PointerUnionTypeSelector<
+        PT1, T, IsInnerUnion,
+        ::llvm::PointerUnionTypeSelector<PT2, T, IsInnerUnion, IsPT3>>::Return
+        Ty;
+    return Ty(Val).template is<T>();
+  }
 
-    /// isNull - Return true if the pointer held in the union is null,
-    /// regardless of which type it is.
-    bool isNull() const { return Val.isNull(); }
-    explicit operator bool() const { return !isNull(); }
+  /// Returns the value of the specified pointer type.
+  ///
+  /// If the specified pointer type is incorrect, assert.
+  template <typename T> T get() const {
+    assert(is<T>() && "Invalid accessor called");
+    // If T is PT1/PT2 choose IsInnerUnion otherwise choose IsPT3.
+    typedef typename ::llvm::PointerUnionTypeSelector<
+        PT1, T, IsInnerUnion,
+        ::llvm::PointerUnionTypeSelector<PT2, T, IsInnerUnion, IsPT3>>::Return
+        Ty;
+    return Ty(Val).template get<T>();
+  }
 
-    /// is<T>() return true if the Union currently holds the type matching T.
-    template<typename T>
-    int is() const {
-      // If T is PT1/PT2 choose IsInnerUnion otherwise choose IsPT3.
-      typedef typename
-        ::llvm::PointerUnionTypeSelector<PT1, T, IsInnerUnion,
-          ::llvm::PointerUnionTypeSelector<PT2, T, IsInnerUnion, IsPT3 >
-                                                                   >::Return Ty;
-      return Ty(Val).template is<T>();
-    }
+  /// Returns the current pointer if it is of the specified pointer type,
+  /// otherwises returns null.
+  template <typename T> T dyn_cast() const {
+    if (is<T>())
+      return get<T>();
+    return T();
+  }
 
-    /// get<T>() - Return the value of the specified pointer type. If the
-    /// specified pointer type is incorrect, assert.
-    template<typename T>
-    T get() const {
-      assert(is<T>() && "Invalid accessor called");
-      // If T is PT1/PT2 choose IsInnerUnion otherwise choose IsPT3.
-      typedef typename
-        ::llvm::PointerUnionTypeSelector<PT1, T, IsInnerUnion,
-          ::llvm::PointerUnionTypeSelector<PT2, T, IsInnerUnion, IsPT3 >
-                                                                   >::Return Ty;
-      return Ty(Val).template get<T>();
-    }
+  /// Assignment from nullptr which just clears the union.
+  const PointerUnion3 &operator=(std::nullptr_t) {
+    Val = nullptr;
+    return *this;
+  }
 
-    /// dyn_cast<T>() - If the current value is of the specified pointer type,
-    /// return it, otherwise return null.
-    template<typename T>
-    T dyn_cast() const {
-      if (is<T>()) return get<T>();
-      return T();
-    }
+  /// Assignment operators - Allow assigning into this union from either
+  /// pointer type, setting the discriminator to remember what it came from.
+  const PointerUnion3 &operator=(const PT1 &RHS) {
+    Val = InnerUnion(RHS);
+    return *this;
+  }
+  const PointerUnion3 &operator=(const PT2 &RHS) {
+    Val = InnerUnion(RHS);
+    return *this;
+  }
+  const PointerUnion3 &operator=(const PT3 &RHS) {
+    Val = RHS;
+    return *this;
+  }
 
-    /// \brief Assignment from nullptr which just clears the union.
-    const PointerUnion3 &operator=(std::nullptr_t) {
-      Val = nullptr;
-      return *this;
-    }
+  void *getOpaqueValue() const { return Val.getOpaqueValue(); }
+  static inline PointerUnion3 getFromOpaqueValue(void *VP) {
+    PointerUnion3 V;
+    V.Val = ValTy::getFromOpaqueValue(VP);
+    return V;
+  }
+};
 
-    /// Assignment operators - Allow assigning into this union from either
-    /// pointer type, setting the discriminator to remember what it came from.
-    const PointerUnion3 &operator=(const PT1 &RHS) {
-      Val = InnerUnion(RHS);
-      return *this;
-    }
-    const PointerUnion3 &operator=(const PT2 &RHS) {
-      Val = InnerUnion(RHS);
-      return *this;
-    }
-    const PointerUnion3 &operator=(const PT3 &RHS) {
-      Val = RHS;
-      return *this;
-    }
+// Teach SmallPtrSet that PointerUnion3 is "basically a pointer", that has
+// # low bits available = min(PT1bits,PT2bits,PT2bits)-2.
+template <typename PT1, typename PT2, typename PT3>
+class PointerLikeTypeTraits<PointerUnion3<PT1, PT2, PT3>> {
+public:
+  static inline void *getAsVoidPointer(const PointerUnion3<PT1, PT2, PT3> &P) {
+    return P.getOpaqueValue();
+  }
+  static inline PointerUnion3<PT1, PT2, PT3> getFromVoidPointer(void *P) {
+    return PointerUnion3<PT1, PT2, PT3>::getFromOpaqueValue(P);
+  }
 
-    void *getOpaqueValue() const { return Val.getOpaqueValue(); }
-    static inline PointerUnion3 getFromOpaqueValue(void *VP) {
-      PointerUnion3 V;
-      V.Val = ValTy::getFromOpaqueValue(VP);
-      return V;
-    }
+  // The number of bits available are the min of the two pointer types.
+  enum {
+    NumLowBitsAvailable = PointerLikeTypeTraits<
+        typename PointerUnion3<PT1, PT2, PT3>::ValTy>::NumLowBitsAvailable
   };
+};
 
-  // Teach SmallPtrSet that PointerUnion3 is "basically a pointer", that has
-  // # low bits available = min(PT1bits,PT2bits,PT2bits)-2.
-  template<typename PT1, typename PT2, typename PT3>
-  class PointerLikeTypeTraits<PointerUnion3<PT1, PT2, PT3> > {
-  public:
-    static inline void *
-    getAsVoidPointer(const PointerUnion3<PT1, PT2, PT3> &P) {
-      return P.getOpaqueValue();
-    }
-    static inline PointerUnion3<PT1, PT2, PT3>
-    getFromVoidPointer(void *P) {
-      return PointerUnion3<PT1, PT2, PT3>::getFromOpaqueValue(P);
-    }
+/// A pointer union of four pointer types. See documentation for PointerUnion
+/// for usage.
+template <typename PT1, typename PT2, typename PT3, typename PT4>
+class PointerUnion4 {
+public:
+  typedef PointerUnion<PT1, PT2> InnerUnion1;
+  typedef PointerUnion<PT3, PT4> InnerUnion2;
+  typedef PointerUnion<InnerUnion1, InnerUnion2> ValTy;
 
-    // The number of bits available are the min of the two pointer types.
-    enum {
-      NumLowBitsAvailable =
-        PointerLikeTypeTraits<typename PointerUnion3<PT1, PT2, PT3>::ValTy>
-          ::NumLowBitsAvailable
-    };
-  };
+private:
+  ValTy Val;
 
-  /// PointerUnion4 - This is a pointer union of four pointer types.  See
-  /// documentation for PointerUnion for usage.
-  template <typename PT1, typename PT2, typename PT3, typename PT4>
-  class PointerUnion4 {
-  public:
-    typedef PointerUnion<PT1, PT2> InnerUnion1;
-    typedef PointerUnion<PT3, PT4> InnerUnion2;
-    typedef PointerUnion<InnerUnion1, InnerUnion2> ValTy;
-  private:
-    ValTy Val;
-  public:
-    PointerUnion4() {}
+public:
+  PointerUnion4() {}
 
-    PointerUnion4(PT1 V) {
-      Val = InnerUnion1(V);
-    }
-    PointerUnion4(PT2 V) {
-      Val = InnerUnion1(V);
-    }
-    PointerUnion4(PT3 V) {
-      Val = InnerUnion2(V);
-    }
-    PointerUnion4(PT4 V) {
-      Val = InnerUnion2(V);
-    }
+  PointerUnion4(PT1 V) { Val = InnerUnion1(V); }
+  PointerUnion4(PT2 V) { Val = InnerUnion1(V); }
+  PointerUnion4(PT3 V) { Val = InnerUnion2(V); }
+  PointerUnion4(PT4 V) { Val = InnerUnion2(V); }
 
-    /// isNull - Return true if the pointer held in the union is null,
-    /// regardless of which type it is.
-    bool isNull() const { return Val.isNull(); }
-    explicit operator bool() const { return !isNull(); }
+  /// Test if the pointer held in the union is null, regardless of
+  /// which type it is.
+  bool isNull() const { return Val.isNull(); }
+  explicit operator bool() const { return !isNull(); }
 
-    /// is<T>() return true if the Union currently holds the type matching T.
-    template<typename T>
-    int is() const {
-      // If T is PT1/PT2 choose InnerUnion1 otherwise choose InnerUnion2.
-      typedef typename
-        ::llvm::PointerUnionTypeSelector<PT1, T, InnerUnion1,
-          ::llvm::PointerUnionTypeSelector<PT2, T, InnerUnion1, InnerUnion2 >
-                                                                   >::Return Ty;
-      return Val.template is<Ty>() &&
-             Val.template get<Ty>().template is<T>();
-    }
+  /// Test if the Union currently holds the type matching T.
+  template <typename T> int is() const {
+    // If T is PT1/PT2 choose InnerUnion1 otherwise choose InnerUnion2.
+    typedef typename ::llvm::PointerUnionTypeSelector<
+        PT1, T, InnerUnion1, ::llvm::PointerUnionTypeSelector<
+                                 PT2, T, InnerUnion1, InnerUnion2>>::Return Ty;
+    return Val.template is<Ty>() && Val.template get<Ty>().template is<T>();
+  }
 
-    /// get<T>() - Return the value of the specified pointer type. If the
-    /// specified pointer type is incorrect, assert.
-    template<typename T>
-    T get() const {
-      assert(is<T>() && "Invalid accessor called");
-      // If T is PT1/PT2 choose InnerUnion1 otherwise choose InnerUnion2.
-      typedef typename
-        ::llvm::PointerUnionTypeSelector<PT1, T, InnerUnion1,
-          ::llvm::PointerUnionTypeSelector<PT2, T, InnerUnion1, InnerUnion2 >
-                                                                   >::Return Ty;
-      return Val.template get<Ty>().template get<T>();
-    }
+  /// Returns the value of the specified pointer type.
+  ///
+  /// If the specified pointer type is incorrect, assert.
+  template <typename T> T get() const {
+    assert(is<T>() && "Invalid accessor called");
+    // If T is PT1/PT2 choose InnerUnion1 otherwise choose InnerUnion2.
+    typedef typename ::llvm::PointerUnionTypeSelector<
+        PT1, T, InnerUnion1, ::llvm::PointerUnionTypeSelector<
+                                 PT2, T, InnerUnion1, InnerUnion2>>::Return Ty;
+    return Val.template get<Ty>().template get<T>();
+  }
 
-    /// dyn_cast<T>() - If the current value is of the specified pointer type,
-    /// return it, otherwise return null.
-    template<typename T>
-    T dyn_cast() const {
-      if (is<T>()) return get<T>();
-      return T();
-    }
+  /// Returns the current pointer if it is of the specified pointer type,
+  /// otherwises returns null.
+  template <typename T> T dyn_cast() const {
+    if (is<T>())
+      return get<T>();
+    return T();
+  }
 
-    /// \brief Assignment from nullptr which just clears the union.
-    const PointerUnion4 &operator=(std::nullptr_t) {
-      Val = nullptr;
-      return *this;
-    }
+  /// Assignment from nullptr which just clears the union.
+  const PointerUnion4 &operator=(std::nullptr_t) {
+    Val = nullptr;
+    return *this;
+  }
 
-    /// Assignment operators - Allow assigning into this union from either
-    /// pointer type, setting the discriminator to remember what it came from.
-    const PointerUnion4 &operator=(const PT1 &RHS) {
-      Val = InnerUnion1(RHS);
-      return *this;
-    }
-    const PointerUnion4 &operator=(const PT2 &RHS) {
-      Val = InnerUnion1(RHS);
-      return *this;
-    }
-    const PointerUnion4 &operator=(const PT3 &RHS) {
-      Val = InnerUnion2(RHS);
-      return *this;
-    }
-    const PointerUnion4 &operator=(const PT4 &RHS) {
-      Val = InnerUnion2(RHS);
-      return *this;
-    }
+  /// Assignment operators - Allow assigning into this union from either
+  /// pointer type, setting the discriminator to remember what it came from.
+  const PointerUnion4 &operator=(const PT1 &RHS) {
+    Val = InnerUnion1(RHS);
+    return *this;
+  }
+  const PointerUnion4 &operator=(const PT2 &RHS) {
+    Val = InnerUnion1(RHS);
+    return *this;
+  }
+  const PointerUnion4 &operator=(const PT3 &RHS) {
+    Val = InnerUnion2(RHS);
+    return *this;
+  }
+  const PointerUnion4 &operator=(const PT4 &RHS) {
+    Val = InnerUnion2(RHS);
+    return *this;
+  }
 
-    void *getOpaqueValue() const { return Val.getOpaqueValue(); }
-    static inline PointerUnion4 getFromOpaqueValue(void *VP) {
-      PointerUnion4 V;
-      V.Val = ValTy::getFromOpaqueValue(VP);
-      return V;
-    }
-  };
+  void *getOpaqueValue() const { return Val.getOpaqueValue(); }
+  static inline PointerUnion4 getFromOpaqueValue(void *VP) {
+    PointerUnion4 V;
+    V.Val = ValTy::getFromOpaqueValue(VP);
+    return V;
+  }
+};
 
-  // Teach SmallPtrSet that PointerUnion4 is "basically a pointer", that has
-  // # low bits available = min(PT1bits,PT2bits,PT2bits)-2.
-  template<typename PT1, typename PT2, typename PT3, typename PT4>
-  class PointerLikeTypeTraits<PointerUnion4<PT1, PT2, PT3, PT4> > {
-  public:
-    static inline void *
-    getAsVoidPointer(const PointerUnion4<PT1, PT2, PT3, PT4> &P) {
-      return P.getOpaqueValue();
-    }
-    static inline PointerUnion4<PT1, PT2, PT3, PT4>
-    getFromVoidPointer(void *P) {
-      return PointerUnion4<PT1, PT2, PT3, PT4>::getFromOpaqueValue(P);
-    }
+// Teach SmallPtrSet that PointerUnion4 is "basically a pointer", that has
+// # low bits available = min(PT1bits,PT2bits,PT2bits)-2.
+template <typename PT1, typename PT2, typename PT3, typename PT4>
+class PointerLikeTypeTraits<PointerUnion4<PT1, PT2, PT3, PT4>> {
+public:
+  static inline void *
+  getAsVoidPointer(const PointerUnion4<PT1, PT2, PT3, PT4> &P) {
+    return P.getOpaqueValue();
+  }
+  static inline PointerUnion4<PT1, PT2, PT3, PT4> getFromVoidPointer(void *P) {
+    return PointerUnion4<PT1, PT2, PT3, PT4>::getFromOpaqueValue(P);
+  }
 
-    // The number of bits available are the min of the two pointer types.
-    enum {
-      NumLowBitsAvailable =
-        PointerLikeTypeTraits<typename PointerUnion4<PT1, PT2, PT3, PT4>::ValTy>
-          ::NumLowBitsAvailable
-    };
+  // The number of bits available are the min of the two pointer types.
+  enum {
+    NumLowBitsAvailable = PointerLikeTypeTraits<
+        typename PointerUnion4<PT1, PT2, PT3, PT4>::ValTy>::NumLowBitsAvailable
   };
+};
 
-  // Teach DenseMap how to use PointerUnions as keys.
-  template<typename T, typename U>
-  struct DenseMapInfo<PointerUnion<T, U> > {
-    typedef PointerUnion<T, U> Pair;
-    typedef DenseMapInfo<T> FirstInfo;
-    typedef DenseMapInfo<U> SecondInfo;
+// Teach DenseMap how to use PointerUnions as keys.
+template <typename T, typename U> struct DenseMapInfo<PointerUnion<T, U>> {
+  typedef PointerUnion<T, U> Pair;
+  typedef DenseMapInfo<T> FirstInfo;
+  typedef DenseMapInfo<U> SecondInfo;
+
+  static inline Pair getEmptyKey() { return Pair(FirstInfo::getEmptyKey()); }
+  static inline Pair getTombstoneKey() {
+    return Pair(FirstInfo::getTombstoneKey());
+  }
+  static unsigned getHashValue(const Pair &PairVal) {
+    intptr_t key = (intptr_t)PairVal.getOpaqueValue();
+    return DenseMapInfo<intptr_t>::getHashValue(key);
+  }
+  static bool isEqual(const Pair &LHS, const Pair &RHS) {
+    return LHS.template is<T>() == RHS.template is<T>() &&
+           (LHS.template is<T>() ? FirstInfo::isEqual(LHS.template get<T>(),
+                                                      RHS.template get<T>())
+                                 : SecondInfo::isEqual(LHS.template get<U>(),
+                                                       RHS.template get<U>()));
+  }
+};
 
-    static inline Pair getEmptyKey() {
-      return Pair(FirstInfo::getEmptyKey());
-    }
-    static inline Pair getTombstoneKey() {
-      return Pair(FirstInfo::getTombstoneKey());
-    }
-    static unsigned getHashValue(const Pair &PairVal) {
-      intptr_t key = (intptr_t)PairVal.getOpaqueValue();
-      return DenseMapInfo<intptr_t>::getHashValue(key);
-    }
-    static bool isEqual(const Pair &LHS, const Pair &RHS) {
-      return LHS.template is<T>() == RHS.template is<T>() &&
-             (LHS.template is<T>() ?
-              FirstInfo::isEqual(LHS.template get<T>(),
-                                 RHS.template get<T>()) :
-              SecondInfo::isEqual(LHS.template get<U>(),
-                                  RHS.template get<U>()));
-    }
-  };
 }
 
 #endif
diff --git a/include/llvm/ADT/PostOrderIterator.h b/include/llvm/ADT/PostOrderIterator.h
index 759a2db24f2a..ce343a161b7b 100644
--- a/include/llvm/ADT/PostOrderIterator.h
+++ b/include/llvm/ADT/PostOrderIterator.h
@@ -215,8 +215,8 @@ struct ipo_iterator : public po_iterator<Inverse<T>, SetType, External > {
 };
 
 template <class T>
-ipo_iterator<T> ipo_begin(const T &G, bool Reverse = false) {
-  return ipo_iterator<T>::begin(G, Reverse);
+ipo_iterator<T> ipo_begin(const T &G) {
+  return ipo_iterator<T>::begin(G);
 }
 
 template <class T>
@@ -225,8 +225,8 @@ ipo_iterator<T> ipo_end(const T &G){
 }
 
 template <class T>
-iterator_range<ipo_iterator<T>> inverse_post_order(const T &G, bool Reverse = false) {
-  return make_range(ipo_begin(G, Reverse), ipo_end(G));
+iterator_range<ipo_iterator<T>> inverse_post_order(const T &G) {
+  return make_range(ipo_begin(G), ipo_end(G));
 }
 
 // Provide global definitions of external inverse postorder iterators...
diff --git a/include/llvm/ADT/STLExtras.h b/include/llvm/ADT/STLExtras.h
index b68345a1dcf6..d4360fa8d218 100644
--- a/include/llvm/ADT/STLExtras.h
+++ b/include/llvm/ADT/STLExtras.h
@@ -196,6 +196,41 @@ inline mapped_iterator<ItTy, FuncTy> map_iterator(const ItTy &I, FuncTy F) {
   return mapped_iterator<ItTy, FuncTy>(I, F);
 }
 
+/// \brief Metafunction to determine if type T has a member called rbegin().
+template <typename T> struct has_rbegin {
+  template <typename U> static char(&f(const U &, decltype(&U::rbegin)))[1];
+  static char(&f(...))[2];
+  const static bool value = sizeof(f(std::declval<T>(), nullptr)) == 1;
+};
+
+// Returns an iterator_range over the given container which iterates in reverse.
+// Note that the container must have rbegin()/rend() methods for this to work.
+template <typename ContainerTy>
+auto reverse(ContainerTy &&C,
+             typename std::enable_if<has_rbegin<ContainerTy>::value>::type * =
+                 nullptr) -> decltype(make_range(C.rbegin(), C.rend())) {
+  return make_range(C.rbegin(), C.rend());
+}
+
+// Returns a std::reverse_iterator wrapped around the given iterator.
+template <typename IteratorTy>
+std::reverse_iterator<IteratorTy> make_reverse_iterator(IteratorTy It) {
+  return std::reverse_iterator<IteratorTy>(It);
+}
+
+// Returns an iterator_range over the given container which iterates in reverse.
+// Note that the container must have begin()/end() methods which return
+// bidirectional iterators for this to work.
+template <typename ContainerTy>
+auto reverse(
+    ContainerTy &&C,
+    typename std::enable_if<!has_rbegin<ContainerTy>::value>::type * = nullptr)
+    -> decltype(make_range(llvm::make_reverse_iterator(std::end(C)),
+                           llvm::make_reverse_iterator(std::begin(C)))) {
+  return make_range(llvm::make_reverse_iterator(std::end(C)),
+                    llvm::make_reverse_iterator(std::begin(C)));
+}
+
 //===----------------------------------------------------------------------===//
 //     Extra additions to <utility>
 //===----------------------------------------------------------------------===//
@@ -329,13 +364,28 @@ void DeleteContainerSeconds(Container &C) {
 }
 
 /// Provide wrappers to std::all_of which take ranges instead of having to pass
-/// being/end explicitly.
+/// begin/end explicitly.
 template<typename R, class UnaryPredicate>
 bool all_of(R &&Range, UnaryPredicate &&P) {
   return std::all_of(Range.begin(), Range.end(),
                      std::forward<UnaryPredicate>(P));
 }
 
+/// Provide wrappers to std::any_of which take ranges instead of having to pass
+/// begin/end explicitly.
+template <typename R, class UnaryPredicate>
+bool any_of(R &&Range, UnaryPredicate &&P) {
+  return std::any_of(Range.begin(), Range.end(),
+                     std::forward<UnaryPredicate>(P));
+}
+
+/// Provide wrappers to std::find which take ranges instead of having to pass
+/// begin/end explicitly.
+template<typename R, class T>
+auto find(R &&Range, const T &val) -> decltype(Range.begin()) {
+  return std::find(Range.begin(), Range.end(), val);
+}
+
 //===----------------------------------------------------------------------===//
 //     Extra additions to <memory>
 //===----------------------------------------------------------------------===//
diff --git a/include/llvm/ADT/ScopedHashTable.h b/include/llvm/ADT/ScopedHashTable.h
index 5abe76c12259..4af3d6d37e33 100644
--- a/include/llvm/ADT/ScopedHashTable.h
+++ b/include/llvm/ADT/ScopedHashTable.h
@@ -1,4 +1,4 @@
-//===- ScopedHashTable.h - A simple scoped hash table ---------------------===//
+//===- ScopedHashTable.h - A simple scoped hash table -----------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -47,8 +47,8 @@ class ScopedHashTableVal {
   K Key;
   V Val;
   ScopedHashTableVal(const K &key, const V &val) : Key(key), Val(val) {}
-public:
 
+public:
   const K &getKey() const { return Key; }
   const V &getValue() const { return Val; }
   V &getValue() { return Val; }
@@ -56,7 +56,7 @@ public:
   ScopedHashTableVal *getNextForKey() { return NextForKey; }
   const ScopedHashTableVal *getNextForKey() const { return NextForKey; }
   ScopedHashTableVal *getNextInScope() { return NextInScope; }
-  
+
   template <typename AllocatorTy>
   static ScopedHashTableVal *Create(ScopedHashTableVal *nextInScope,
                                     ScopedHashTableVal *nextForKey,
@@ -66,12 +66,11 @@ public:
     // Set up the value.
     new (New) ScopedHashTableVal(key, val);
     New->NextInScope = nextInScope;
-    New->NextForKey = nextForKey; 
+    New->NextForKey = nextForKey;
     return New;
   }
-  
-  template <typename AllocatorTy>
-  void Destroy(AllocatorTy &Allocator) {
+
+  template <typename AllocatorTy> void Destroy(AllocatorTy &Allocator) {
     // Free memory referenced by the item.
     this->~ScopedHashTableVal();
     Allocator.Deallocate(this);
@@ -90,15 +89,16 @@ class ScopedHashTableScope {
   /// LastValInScope - This is the last value that was inserted for this scope
   /// or null if none have been inserted yet.
   ScopedHashTableVal<K, V> *LastValInScope;
-  void operator=(ScopedHashTableScope&) = delete;
-  ScopedHashTableScope(ScopedHashTableScope&) = delete;
+  void operator=(ScopedHashTableScope &) = delete;
+  ScopedHashTableScope(ScopedHashTableScope &) = delete;
+
 public:
   ScopedHashTableScope(ScopedHashTable<K, V, KInfo, AllocatorTy> &HT);
   ~ScopedHashTableScope();
 
   ScopedHashTableScope *getParentScope() { return PrevScope; }
   const ScopedHashTableScope *getParentScope() const { return PrevScope; }
-  
+
 private:
   friend class ScopedHashTable<K, V, KInfo, AllocatorTy>;
   ScopedHashTableVal<K, V> *getLastValInScope() {
@@ -109,10 +109,10 @@ private:
   }
 };
 
-
-template <typename K, typename V, typename KInfo = DenseMapInfo<K> >
+template <typename K, typename V, typename KInfo = DenseMapInfo<K>>
 class ScopedHashTableIterator {
   ScopedHashTableVal<K, V> *Node;
+
 public:
   ScopedHashTableIterator(ScopedHashTableVal<K, V> *node) : Node(node) {}
 
@@ -141,7 +141,6 @@ public:
   }
 };
 
-
 template <typename K, typename V, typename KInfo, typename AllocatorTy>
 class ScopedHashTable {
 public:
@@ -149,23 +148,24 @@ public:
   /// to the name of the scope for this hash table.
   typedef ScopedHashTableScope<K, V, KInfo, AllocatorTy> ScopeTy;
   typedef unsigned size_type;
+
 private:
   typedef ScopedHashTableVal<K, V> ValTy;
   DenseMap<K, ValTy*, KInfo> TopLevelMap;
   ScopeTy *CurScope;
-  
+
   AllocatorTy Allocator;
-  
-  ScopedHashTable(const ScopedHashTable&); // NOT YET IMPLEMENTED
-  void operator=(const ScopedHashTable&);  // NOT YET IMPLEMENTED
+
+  ScopedHashTable(const ScopedHashTable &); // NOT YET IMPLEMENTED
+  void operator=(const ScopedHashTable &);  // NOT YET IMPLEMENTED
   friend class ScopedHashTableScope<K, V, KInfo, AllocatorTy>;
+
 public:
   ScopedHashTable() : CurScope(nullptr) {}
   ScopedHashTable(AllocatorTy A) : CurScope(0), Allocator(A) {}
   ~ScopedHashTable() {
     assert(!CurScope && TopLevelMap.empty() && "Scope imbalance!");
   }
-  
 
   /// Access to the allocator.
   AllocatorTy &getAllocator() { return Allocator; }
@@ -180,7 +180,7 @@ public:
     typename DenseMap<K, ValTy*, KInfo>::iterator I = TopLevelMap.find(Key);
     if (I != TopLevelMap.end())
       return I->second->getValue();
-      
+
     return V();
   }
 
@@ -198,7 +198,7 @@ public:
     if (I == TopLevelMap.end()) return end();
     return iterator(I->second);
   }
-  
+
   ScopeTy *getCurScope() { return CurScope; }
   const ScopeTy *getCurScope() const { return CurScope; }
 
diff --git a/include/llvm/ADT/SetOperations.h b/include/llvm/ADT/SetOperations.h
index 71f5db380f6e..7c9f2fbe066e 100644
--- a/include/llvm/ADT/SetOperations.h
+++ b/include/llvm/ADT/SetOperations.h
@@ -39,7 +39,7 @@ bool set_union(S1Ty &S1, const S2Ty &S2) {
 template <class S1Ty, class S2Ty>
 void set_intersect(S1Ty &S1, const S2Ty &S2) {
    for (typename S1Ty::iterator I = S1.begin(); I != S1.end();) {
-     const typename S1Ty::key_type &E = *I;
+     const auto &E = *I;
      ++I;
      if (!S2.count(E)) S1.erase(E);   // Erase element if not in S2
    }
diff --git a/include/llvm/ADT/SetVector.h b/include/llvm/ADT/SetVector.h
index a7fd408c854a..bc563570c203 100644
--- a/include/llvm/ADT/SetVector.h
+++ b/include/llvm/ADT/SetVector.h
@@ -20,6 +20,7 @@
 #ifndef LLVM_ADT_SETVECTOR_H
 #define LLVM_ADT_SETVECTOR_H
 
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include <algorithm>
 #include <cassert>
@@ -33,7 +34,7 @@ namespace llvm {
 /// property of a deterministic iteration order. The order of iteration is the
 /// order of insertion.
 template <typename T, typename Vector = std::vector<T>,
-                      typename Set = SmallSet<T, 16> >
+          typename Set = DenseSet<T>>
 class SetVector {
 public:
   typedef T value_type;
@@ -44,6 +45,8 @@ public:
   typedef Vector vector_type;
   typedef typename vector_type::const_iterator iterator;
   typedef typename vector_type::const_iterator const_iterator;
+  typedef typename vector_type::const_reverse_iterator reverse_iterator;
+  typedef typename vector_type::const_reverse_iterator const_reverse_iterator;
   typedef typename vector_type::size_type size_type;
 
   /// \brief Construct an empty SetVector
@@ -55,6 +58,8 @@ public:
     insert(Start, End);
   }
 
+  ArrayRef<T> getArrayRef() const { return vector_; }
+
   /// \brief Determine if the SetVector is empty or not.
   bool empty() const {
     return vector_.empty();
@@ -85,6 +90,26 @@ public:
     return vector_.end();
   }
 
+  /// \brief 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.
+  const_reverse_iterator rbegin() const {
+    return vector_.rbegin();
+  }
+
+  /// \brief 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.
+  const_reverse_iterator rend() const {
+    return vector_.rend();
+  }
+
   /// \brief Return the last element of the SetVector.
   const T &back() const {
     assert(!empty() && "Cannot call back() on empty SetVector!");
@@ -150,7 +175,6 @@ public:
     return true;
   }
 
-
   /// \brief 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 {
@@ -169,7 +193,7 @@ public:
     set_.erase(back());
     vector_.pop_back();
   }
-  
+
   T LLVM_ATTRIBUTE_UNUSED_RESULT pop_back_val() {
     T Ret = back();
     pop_back();
diff --git a/include/llvm/ADT/SmallBitVector.h b/include/llvm/ADT/SmallBitVector.h
index ae3d645396fd..4aa3bc217f41 100644
--- a/include/llvm/ADT/SmallBitVector.h
+++ b/include/llvm/ADT/SmallBitVector.h
@@ -551,19 +551,18 @@ public:
   }
 
 private:
-  template<bool AddBits, bool InvertMask>
+  template <bool AddBits, bool InvertMask>
   void applyMask(const uint32_t *Mask, unsigned MaskWords) {
-    if (NumBaseBits == 64 && MaskWords >= 2) {
-      uint64_t M = Mask[0] | (uint64_t(Mask[1]) << 32);
-      if (InvertMask) M = ~M;
-      if (AddBits) setSmallBits(getSmallBits() | M);
-      else         setSmallBits(getSmallBits() & ~M);
-    } else {
-      uint32_t M = Mask[0];
-      if (InvertMask) M = ~M;
-      if (AddBits) setSmallBits(getSmallBits() | M);
-      else         setSmallBits(getSmallBits() & ~M);
-    }
+    assert(MaskWords <= sizeof(uintptr_t) && "Mask is larger than base!");
+    uintptr_t M = Mask[0];
+    if (NumBaseBits == 64)
+      M |= uint64_t(Mask[1]) << 32;
+    if (InvertMask)
+      M = ~M;
+    if (AddBits)
+      setSmallBits(getSmallBits() | M);
+    else
+      setSmallBits(getSmallBits() & ~M);
   }
 };
 
diff --git a/include/llvm/ADT/SmallPtrSet.h b/include/llvm/ADT/SmallPtrSet.h
index 3e3c9c154ef4..3d98e8fac43b 100644
--- a/include/llvm/ADT/SmallPtrSet.h
+++ b/include/llvm/ADT/SmallPtrSet.h
@@ -48,6 +48,7 @@ class SmallPtrSetIteratorImpl;
 ///
 class SmallPtrSetImplBase {
   friend class SmallPtrSetIteratorImpl;
+
 protected:
   /// SmallArray - Points to a fixed size set of buckets, used in 'small mode'.
   const void **SmallArray;
@@ -133,6 +134,7 @@ private:
   void Grow(unsigned NewSize);
 
   void operator=(const SmallPtrSetImplBase &RHS) = delete;
+
 protected:
   /// swap - Swaps the elements of two sets.
   /// Note: This method assumes that both sets have the same small size.
@@ -148,6 +150,7 @@ class SmallPtrSetIteratorImpl {
 protected:
   const void *const *Bucket;
   const void *const *End;
+
 public:
   explicit SmallPtrSetIteratorImpl(const void *const *BP, const void*const *E)
     : Bucket(BP), End(E) {
@@ -178,14 +181,14 @@ protected:
 template<typename PtrTy>
 class SmallPtrSetIterator : public SmallPtrSetIteratorImpl {
   typedef PointerLikeTypeTraits<PtrTy> PtrTraits;
-  
+
 public:
   typedef PtrTy                     value_type;
   typedef PtrTy                     reference;
   typedef PtrTy                     pointer;
   typedef std::ptrdiff_t            difference_type;
   typedef std::forward_iterator_tag iterator_category;
-  
+
   explicit SmallPtrSetIterator(const void *const *BP, const void *const *E)
     : SmallPtrSetIteratorImpl(BP, E) {}
 
@@ -231,7 +234,6 @@ template<unsigned N>
 struct RoundUpToPowerOfTwo {
   enum { Val = RoundUpToPowerOfTwoH<N, (N&(N-1)) == 0>::Val };
 };
-  
 
 /// \brief A templated base class for \c SmallPtrSet which provides the
 /// typesafe interface that is common across all small sizes.
@@ -242,7 +244,8 @@ template <typename PtrType>
 class SmallPtrSetImpl : public SmallPtrSetImplBase {
   typedef PointerLikeTypeTraits<PtrType> PtrTraits;
 
-  SmallPtrSetImpl(const SmallPtrSetImpl&) = delete;
+  SmallPtrSetImpl(const SmallPtrSetImpl &) = delete;
+
 protected:
   // Constructors that forward to the base.
   SmallPtrSetImpl(const void **SmallStorage, const SmallPtrSetImpl &that)
@@ -303,6 +306,7 @@ class SmallPtrSet : public SmallPtrSetImpl<PtrType> {
   enum { SmallSizePowTwo = RoundUpToPowerOfTwo<SmallSize>::Val };
   /// SmallStorage - Fixed size storage used in 'small mode'.
   const void *SmallStorage[SmallSizePowTwo];
+
 public:
   SmallPtrSet() : BaseT(SmallStorage, SmallSizePowTwo) {}
   SmallPtrSet(const SmallPtrSet &that) : BaseT(SmallStorage, that) {}
@@ -333,7 +337,6 @@ public:
     SmallPtrSetImplBase::swap(RHS);
   }
 };
-
 }
 
 namespace std {
diff --git a/include/llvm/ADT/SmallSet.h b/include/llvm/ADT/SmallSet.h
index bc6493554c8b..39a57b87b2a7 100644
--- a/include/llvm/ADT/SmallSet.h
+++ b/include/llvm/ADT/SmallSet.h
@@ -37,6 +37,7 @@ class SmallSet {
   std::set<T, C> Set;
   typedef typename SmallVector<T, N>::const_iterator VIterator;
   typedef typename SmallVector<T, N>::iterator mutable_iterator;
+
 public:
   typedef size_t size_type;
   SmallSet() {}
@@ -92,7 +93,7 @@ public:
     for (; I != E; ++I)
       insert(*I);
   }
-  
+
   bool erase(const T &V) {
     if (!isSmall())
       return Set.erase(V);
@@ -108,6 +109,7 @@ public:
     Vector.clear();
     Set.clear();
   }
+
 private:
   bool isSmall() const { return Set.empty(); }
 
diff --git a/include/llvm/ADT/SmallVector.h b/include/llvm/ADT/SmallVector.h
index b9384702c3ba..d1062acbbb61 100644
--- a/include/llvm/ADT/SmallVector.h
+++ b/include/llvm/ADT/SmallVector.h
@@ -109,9 +109,13 @@ public:
   typedef const T *const_pointer;
 
   // forward iterator creation methods.
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
   iterator begin() { return (iterator)this->BeginX; }
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
   const_iterator begin() const { return (const_iterator)this->BeginX; }
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
   iterator end() { return (iterator)this->EndX; }
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
   const_iterator end() const { return (const_iterator)this->EndX; }
 protected:
   iterator capacity_ptr() { return (iterator)this->CapacityX; }
@@ -124,6 +128,7 @@ public:
   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 max_size() const { return size_type(-1) / sizeof(T); }
 
@@ -135,10 +140,12 @@ public:
   /// Return a pointer to the vector's buffer, even if empty().
   const_pointer data() const { return const_pointer(begin()); }
 
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
   reference operator[](size_type idx) {
     assert(idx < size());
     return begin()[idx];
   }
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
   const_reference operator[](size_type idx) const {
     assert(idx < size());
     return begin()[idx];
diff --git a/include/llvm/ADT/SparseBitVector.h b/include/llvm/ADT/SparseBitVector.h
index 20cbe2cddfc2..e6e72413da4e 100644
--- a/include/llvm/ADT/SparseBitVector.h
+++ b/include/llvm/ADT/SparseBitVector.h
@@ -39,7 +39,6 @@ namespace llvm {
 /// etc) do not perform as well in practice as a linked list with this iterator
 /// kept up to date.  They are also significantly more memory intensive.
 
-
 template <unsigned ElementSize = 128>
 struct SparseBitVectorElement
   : public ilist_node<SparseBitVectorElement<ElementSize> > {
@@ -204,6 +203,7 @@ public:
     BecameZero = allzero;
     return changed;
   }
+
   // Intersect this Element with the complement of RHS and return true if this
   // one changed.  BecameZero is set to true if this element became all-zero
   // bits.
@@ -226,6 +226,7 @@ public:
     BecameZero = allzero;
     return changed;
   }
+
   // Three argument version of intersectWithComplement that intersects
   // RHS1 & ~RHS2 into this element
   void intersectWithComplement(const SparseBitVectorElement &RHS1,
@@ -408,12 +409,13 @@ class SparseBitVector {
       // bitmap.
       return AtEnd == RHS.AtEnd && RHS.BitNumber == BitNumber;
     }
+
     bool operator!=(const SparseBitVectorIterator &RHS) const {
       return !(*this == RHS);
     }
-    SparseBitVectorIterator(): BitVector(NULL) {
-    }
 
+    SparseBitVectorIterator(): BitVector(nullptr) {
+    }
 
     SparseBitVectorIterator(const SparseBitVector<ElementSize> *RHS,
                             bool end = false):BitVector(RHS) {
@@ -453,6 +455,9 @@ public:
 
   // Assignment
   SparseBitVector& operator=(const SparseBitVector& RHS) {
+    if (this == &RHS)
+      return *this;
+
     Elements.clear();
 
     ElementListConstIter ElementIter = RHS.Elements.begin();
@@ -559,6 +564,9 @@ public:
 
   // Union our bitmap with the RHS and return true if we changed.
   bool operator|=(const SparseBitVector &RHS) {
+    if (this == &RHS)
+      return false;
+
     bool changed = false;
     ElementListIter Iter1 = Elements.begin();
     ElementListConstIter Iter2 = RHS.Elements.begin();
@@ -587,6 +595,9 @@ public:
 
   // Intersect our bitmap with the RHS and return true if ours changed.
   bool operator&=(const SparseBitVector &RHS) {
+    if (this == &RHS)
+      return false;
+
     bool changed = false;
     ElementListIter Iter1 = Elements.begin();
     ElementListConstIter Iter2 = RHS.Elements.begin();
@@ -619,9 +630,13 @@ public:
         ElementListIter IterTmp = Iter1;
         ++Iter1;
         Elements.erase(IterTmp);
+        changed = true;
       }
     }
-    Elements.erase(Iter1, Elements.end());
+    if (Iter1 != Elements.end()) {
+      Elements.erase(Iter1, Elements.end());
+      changed = true;
+    }
     CurrElementIter = Elements.begin();
     return changed;
   }
@@ -629,6 +644,14 @@ public:
   // Intersect our bitmap with the complement of the RHS and return true
   // if ours changed.
   bool intersectWithComplement(const SparseBitVector &RHS) {
+    if (this == &RHS) {
+      if (!empty()) {
+        clear();
+        return true;
+      }
+      return false;
+    }
+
     bool changed = false;
     ElementListIter Iter1 = Elements.begin();
     ElementListConstIter Iter2 = RHS.Elements.begin();
@@ -669,12 +692,20 @@ public:
     return intersectWithComplement(*RHS);
   }
 
-
   //  Three argument version of intersectWithComplement.
   //  Result of RHS1 & ~RHS2 is stored into this bitmap.
   void intersectWithComplement(const SparseBitVector<ElementSize> &RHS1,
                                const SparseBitVector<ElementSize> &RHS2)
   {
+    if (this == &RHS1) {
+      intersectWithComplement(RHS2);
+      return;
+    } else if (this == &RHS2) {
+      SparseBitVector RHS2Copy(RHS2);
+      intersectWithComplement(RHS1, RHS2Copy);
+      return;
+    }
+
     Elements.clear();
     CurrElementIter = Elements.begin();
     ElementListConstIter Iter1 = RHS1.Elements.begin();
@@ -719,8 +750,6 @@ public:
         Elements.push_back(NewElement);
         ++Iter1;
       }
-
-    return;
   }
 
   void intersectWithComplement(const SparseBitVector<ElementSize> *RHS1,
@@ -855,9 +884,6 @@ operator-(const SparseBitVector<ElementSize> &LHS,
   return Result;
 }
 
-
-
-
 // Dump a SparseBitVector to a stream
 template <unsigned ElementSize>
 void dump(const SparseBitVector<ElementSize> &LHS, raw_ostream &out) {
@@ -875,4 +901,4 @@ void dump(const SparseBitVector<ElementSize> &LHS, raw_ostream &out) {
 }
 } // end namespace llvm
 
-#endif
+#endif // LLVM_ADT_SPARSEBITVECTOR_H
diff --git a/include/llvm/ADT/Statistic.h b/include/llvm/ADT/Statistic.h
index d98abc375e8a..7c84e3ef6b4d 100644
--- a/include/llvm/ADT/Statistic.h
+++ b/include/llvm/ADT/Statistic.h
@@ -28,9 +28,11 @@
 
 #include "llvm/Support/Atomic.h"
 #include "llvm/Support/Valgrind.h"
+#include <memory>
 
 namespace llvm {
 class raw_ostream;
+class raw_fd_ostream;
 
 class Statistic {
 public:
@@ -170,6 +172,9 @@ void EnableStatistics();
 /// \brief Check if statistics are enabled.
 bool AreStatisticsEnabled();
 
+/// \brief 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().
 void PrintStatistics();
 
diff --git a/include/llvm/ADT/StringMap.h b/include/llvm/ADT/StringMap.h
index 9d038560bf92..700bb9e10ef7 100644
--- a/include/llvm/ADT/StringMap.h
+++ b/include/llvm/ADT/StringMap.h
@@ -30,6 +30,7 @@ namespace llvm {
 /// StringMapEntryBase - Shared base class of StringMapEntry instances.
 class StringMapEntryBase {
   unsigned StrLen;
+
 public:
   explicit StringMapEntryBase(unsigned Len) : StrLen(Len) {}
 
@@ -48,6 +49,7 @@ protected:
   unsigned NumItems;
   unsigned NumTombstones;
   unsigned ItemSize;
+
 protected:
   explicit StringMapImpl(unsigned itemSize)
       : TheTable(nullptr),
@@ -85,8 +87,10 @@ protected:
   /// RemoveKey - Remove the StringMapEntry for the specified key from the
   /// table, returning it.  If the key is not in the table, this returns null.
   StringMapEntryBase *RemoveKey(StringRef Key);
+
 private:
   void init(unsigned Size);
+
 public:
   static StringMapEntryBase *getTombstoneVal() {
     return (StringMapEntryBase*)-1;
@@ -112,6 +116,7 @@ public:
 template<typename ValueTy>
 class StringMapEntry : public StringMapEntryBase {
   StringMapEntry(StringMapEntry &E) = delete;
+
 public:
   ValueTy second;
 
@@ -205,7 +210,6 @@ public:
   }
 };
 
-
 /// StringMap - This is an unconventional map that is specialized for handling
 /// keys that are "strings", which are basically ranges of bytes. This does some
 /// funky memory allocation and hashing things to make it extremely efficient,
@@ -213,9 +217,10 @@ public:
 template<typename ValueTy, typename AllocatorTy = MallocAllocator>
 class StringMap : public StringMapImpl {
   AllocatorTy Allocator;
+
 public:
   typedef StringMapEntry<ValueTy> MapEntryTy;
-  
+
   StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {}
   explicit StringMap(unsigned InitialSize)
     : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {}
@@ -227,6 +232,13 @@ public:
     : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))),
       Allocator(A) {}
 
+  StringMap(std::initializer_list<std::pair<StringRef, ValueTy>> List)
+      : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {
+    for (const auto &P : List) {
+      insert(P);
+    }
+  }
+
   StringMap(StringMap &&RHS)
       : StringMapImpl(std::move(RHS)), Allocator(std::move(RHS.Allocator)) {}
 
@@ -386,11 +398,10 @@ public:
   }
 };
 
-
-template<typename ValueTy>
-class StringMapConstIterator {
+template <typename ValueTy> class StringMapConstIterator {
 protected:
   StringMapEntryBase **Ptr;
+
 public:
   typedef StringMapEntry<ValueTy> value_type;
 
@@ -447,7 +458,6 @@ public:
     return static_cast<StringMapEntry<ValueTy>*>(*this->Ptr);
   }
 };
-
 }
 
 #endif
diff --git a/include/llvm/ADT/StringRef.h b/include/llvm/ADT/StringRef.h
index 95660a49f1f1..350032b8c4e7 100644
--- a/include/llvm/ADT/StringRef.h
+++ b/include/llvm/ADT/StringRef.h
@@ -10,6 +10,7 @@
 #ifndef LLVM_ADT_STRINGREF_H
 #define LLVM_ADT_STRINGREF_H
 
+#include "llvm/Support/Compiler.h"
 #include <algorithm>
 #include <cassert>
 #include <cstring>
@@ -53,6 +54,7 @@ namespace llvm {
 
     // Workaround memcmp issue with null pointers (undefined behavior)
     // by providing a specialized version
+    LLVM_ATTRIBUTE_ALWAYS_INLINE
     static int compareMemory(const char *Lhs, const char *Rhs, size_t Length) {
       if (Length == 0) { return 0; }
       return ::memcmp(Lhs,Rhs,Length);
@@ -73,6 +75,7 @@ namespace llvm {
       }
 
     /// Construct a string ref from a pointer and length.
+    LLVM_ATTRIBUTE_ALWAYS_INLINE
     /*implicit*/ StringRef(const char *data, size_t length)
       : Data(data), Length(length) {
         assert((data || length == 0) &&
@@ -80,6 +83,7 @@ namespace llvm {
       }
 
     /// Construct a string ref from an std::string.
+    LLVM_ATTRIBUTE_ALWAYS_INLINE
     /*implicit*/ StringRef(const std::string &Str)
       : Data(Str.data()), Length(Str.length()) {}
 
@@ -104,12 +108,15 @@ namespace llvm {
 
     /// data - Get a pointer to the start of the string (which may not be null
     /// terminated).
+    LLVM_ATTRIBUTE_ALWAYS_INLINE
     const char *data() const { return Data; }
 
     /// empty - Check if the string is empty.
+    LLVM_ATTRIBUTE_ALWAYS_INLINE
     bool empty() const { return Length == 0; }
 
     /// size - Get the string size.
+    LLVM_ATTRIBUTE_ALWAYS_INLINE
     size_t size() const { return Length; }
 
     /// front - Get the first character in the string.
@@ -133,6 +140,7 @@ namespace llvm {
 
     /// equals - Check for string equality, this is more efficient than
     /// compare() when the relative ordering of inequal strings isn't needed.
+    LLVM_ATTRIBUTE_ALWAYS_INLINE
     bool equals(StringRef RHS) const {
       return (Length == RHS.Length &&
               compareMemory(Data, RHS.Data, RHS.Length) == 0);
@@ -145,6 +153,7 @@ namespace llvm {
 
     /// compare - Compare two strings; the result is -1, 0, or 1 if this string
     /// is lexicographically less than, equal to, or greater than the \p RHS.
+    LLVM_ATTRIBUTE_ALWAYS_INLINE
     int compare(StringRef RHS) const {
       // Check the prefix for a mismatch.
       if (int Res = compareMemory(Data, RHS.Data, std::min(Length, RHS.Length)))
@@ -212,6 +221,7 @@ namespace llvm {
     /// @{
 
     /// Check if this string starts with the given \p Prefix.
+    LLVM_ATTRIBUTE_ALWAYS_INLINE
     bool startswith(StringRef Prefix) const {
       return Length >= Prefix.Length &&
              compareMemory(Data, Prefix.Data, Prefix.Length) == 0;
@@ -221,6 +231,7 @@ namespace llvm {
     bool startswith_lower(StringRef Prefix) const;
 
     /// Check if this string ends with the given \p Suffix.
+    LLVM_ATTRIBUTE_ALWAYS_INLINE
     bool endswith(StringRef Suffix) const {
       return Length >= Suffix.Length &&
         compareMemory(end() - Suffix.Length, Suffix.Data, Suffix.Length) == 0;
@@ -237,6 +248,7 @@ namespace llvm {
     ///
     /// \returns The index of the first occurrence of \p C, or npos if not
     /// found.
+    LLVM_ATTRIBUTE_ALWAYS_INLINE
     size_t find(char C, size_t From = 0) const {
       size_t FindBegin = std::min(From, Length);
       if (FindBegin < Length) { // Avoid calling memchr with nullptr.
@@ -402,6 +414,7 @@ namespace llvm {
     /// \param N The number of characters to included in the substring. If N
     /// exceeds the number of characters remaining in the string, the string
     /// suffix (starting with \p Start) will be returned.
+    LLVM_ATTRIBUTE_ALWAYS_INLINE
     StringRef substr(size_t Start, size_t N = npos) const {
       Start = std::min(Start, Length);
       return StringRef(Data + Start, std::min(N, Length - Start));
@@ -409,6 +422,7 @@ namespace llvm {
 
     /// Return a StringRef equal to 'this' but with the first \p N elements
     /// dropped.
+    LLVM_ATTRIBUTE_ALWAYS_INLINE
     StringRef drop_front(size_t N = 1) const {
       assert(size() >= N && "Dropping more elements than exist");
       return substr(N);
@@ -416,6 +430,7 @@ namespace llvm {
 
     /// Return a StringRef equal to 'this' but with the last \p N elements
     /// dropped.
+    LLVM_ATTRIBUTE_ALWAYS_INLINE
     StringRef drop_back(size_t N = 1) const {
       assert(size() >= N && "Dropping more elements than exist");
       return substr(0, size()-N);
@@ -431,6 +446,7 @@ namespace llvm {
     /// substring. If this is npos, or less than \p Start, or exceeds the
     /// number of characters remaining in the string, the string suffix
     /// (starting with \p Start) will be returned.
+    LLVM_ATTRIBUTE_ALWAYS_INLINE
     StringRef slice(size_t Start, size_t End) const {
       Start = std::min(Start, Length);
       End = std::min(std::max(Start, End), Length);
@@ -474,7 +490,7 @@ namespace llvm {
     /// Split into substrings around the occurrences of a separator string.
     ///
     /// Each substring is stored in \p A. If \p MaxSplit is >= 0, at most
-    /// \p MaxSplit splits are done and consequently <= \p MaxSplit
+    /// \p MaxSplit splits are done and consequently <= \p MaxSplit + 1
     /// elements are added to A.
     /// If \p KeepEmpty is false, empty strings are not added to \p A. They
     /// still count when considering \p MaxSplit
@@ -489,6 +505,23 @@ namespace llvm {
                StringRef Separator, int MaxSplit = -1,
                bool KeepEmpty = true) const;
 
+    /// Split into substrings around the occurrences of a separator character.
+    ///
+    /// Each substring is stored in \p A. If \p MaxSplit is >= 0, at most
+    /// \p MaxSplit splits are done and consequently <= \p MaxSplit + 1
+    /// elements are added to A.
+    /// If \p KeepEmpty is false, empty strings are not added to \p A. They
+    /// still count when considering \p MaxSplit
+    /// An useful invariant is that
+    /// Separator.join(A) == *this if MaxSplit == -1 and KeepEmpty == true
+    ///
+    /// \param A - Where to put the substrings.
+    /// \param Separator - The string to split on.
+    /// \param MaxSplit - The maximum number of times the string is split.
+    /// \param KeepEmpty - True if empty substring should be added.
+    void split(SmallVectorImpl<StringRef> &A, char Separator, int MaxSplit = -1,
+               bool KeepEmpty = true) const;
+
     /// Split into two substrings around the last occurrence of a separator
     /// character.
     ///
@@ -530,10 +563,12 @@ namespace llvm {
   /// @name StringRef Comparison Operators
   /// @{
 
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
   inline bool operator==(StringRef LHS, StringRef RHS) {
     return LHS.equals(RHS);
   }
 
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
   inline bool operator!=(StringRef LHS, StringRef RHS) {
     return !(LHS == RHS);
   }
diff --git a/include/llvm/ADT/StringSet.h b/include/llvm/ADT/StringSet.h
index 3e0cc200b6dd..08626dc7af84 100644
--- a/include/llvm/ADT/StringSet.h
+++ b/include/llvm/ADT/StringSet.h
@@ -23,6 +23,11 @@ namespace llvm {
   class StringSet : public llvm::StringMap<char, AllocatorTy> {
     typedef llvm::StringMap<char, AllocatorTy> base;
   public:
+    StringSet() = default;
+    StringSet(std::initializer_list<StringRef> S) {
+      for (StringRef X : S)
+        insert(X);
+    }
 
     std::pair<typename base::iterator, bool> insert(StringRef Key) {
       assert(!Key.empty());
diff --git a/include/llvm/ADT/StringSwitch.h b/include/llvm/ADT/StringSwitch.h
index 0393a0c373ef..42b0fc4bc441 100644
--- a/include/llvm/ADT/StringSwitch.h
+++ b/include/llvm/ADT/StringSwitch.h
@@ -14,6 +14,7 @@
 #define LLVM_ADT_STRINGSWITCH_H
 
 #include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Compiler.h"
 #include <cassert>
 #include <cstring>
 
@@ -48,10 +49,12 @@ class StringSwitch {
   const T *Result;
 
 public:
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
   explicit StringSwitch(StringRef S)
   : Str(S), Result(nullptr) { }
 
   template<unsigned N>
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
   StringSwitch& Case(const char (&S)[N], const T& Value) {
     if (!Result && N-1 == Str.size() &&
         (std::memcmp(S, Str.data(), N-1) == 0)) {
@@ -62,6 +65,7 @@ public:
   }
 
   template<unsigned N>
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
   StringSwitch& EndsWith(const char (&S)[N], const T &Value) {
     if (!Result && Str.size() >= N-1 &&
         std::memcmp(S, Str.data() + Str.size() + 1 - N, N-1) == 0) {
@@ -72,6 +76,7 @@ public:
   }
 
   template<unsigned N>
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
   StringSwitch& StartsWith(const char (&S)[N], const T &Value) {
     if (!Result && Str.size() >= N-1 &&
         std::memcmp(S, Str.data(), N-1) == 0) {
@@ -82,32 +87,66 @@ public:
   }
 
   template<unsigned N0, unsigned N1>
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
   StringSwitch& Cases(const char (&S0)[N0], const char (&S1)[N1],
                       const T& Value) {
-    return Case(S0, Value).Case(S1, Value);
+    if (!Result && (
+        (N0-1 == Str.size() && std::memcmp(S0, Str.data(), N0-1) == 0) ||
+        (N1-1 == Str.size() && std::memcmp(S1, Str.data(), N1-1) == 0))) {
+      Result = &Value;
+    }
+
+    return *this;
   }
 
   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) {
-    return Case(S0, Value).Case(S1, Value).Case(S2, Value);
+    if (!Result && (
+        (N0-1 == Str.size() && std::memcmp(S0, Str.data(), N0-1) == 0) ||
+        (N1-1 == Str.size() && std::memcmp(S1, Str.data(), N1-1) == 0) ||
+        (N2-1 == Str.size() && std::memcmp(S2, Str.data(), N2-1) == 0))) {
+      Result = &Value;
+    }
+
+    return *this;
   }
 
   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) {
-    return Case(S0, Value).Case(S1, Value).Case(S2, Value).Case(S3, Value);
+    if (!Result && (
+        (N0-1 == Str.size() && std::memcmp(S0, Str.data(), N0-1) == 0) ||
+        (N1-1 == Str.size() && std::memcmp(S1, Str.data(), N1-1) == 0) ||
+        (N2-1 == Str.size() && std::memcmp(S2, Str.data(), N2-1) == 0) ||
+        (N3-1 == Str.size() && std::memcmp(S3, Str.data(), N3-1) == 0))) {
+      Result = &Value;
+    }
+
+    return *this;
   }
 
   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) {
-    return Case(S0, Value).Case(S1, Value).Case(S2, Value).Case(S3, Value)
-      .Case(S4, Value);
+    if (!Result && (
+        (N0-1 == Str.size() && std::memcmp(S0, Str.data(), N0-1) == 0) ||
+        (N1-1 == Str.size() && std::memcmp(S1, Str.data(), N1-1) == 0) ||
+        (N2-1 == Str.size() && std::memcmp(S2, Str.data(), N2-1) == 0) ||
+        (N3-1 == Str.size() && std::memcmp(S3, Str.data(), N3-1) == 0) ||
+        (N4-1 == Str.size() && std::memcmp(S4, Str.data(), N4-1) == 0))) {
+      Result = &Value;
+    }
+
+    return *this;
   }
 
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
   R Default(const T& Value) const {
     if (Result)
       return *Result;
@@ -115,6 +154,7 @@ public:
     return Value;
   }
 
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
   operator R() const {
     assert(Result && "Fell off the end of a string-switch");
     return *Result;
diff --git a/include/llvm/ADT/TinyPtrVector.h b/include/llvm/ADT/TinyPtrVector.h
index f29608f3d3d1..487aa46cf642 100644
--- a/include/llvm/ADT/TinyPtrVector.h
+++ b/include/llvm/ADT/TinyPtrVector.h
@@ -15,7 +15,7 @@
 #include "llvm/ADT/SmallVector.h"
 
 namespace llvm {
-  
+
 /// TinyPtrVector - This class is specialized for cases where there are
 /// normally 0 or 1 element in a vector, but is general enough to go beyond that
 /// when required.
@@ -150,7 +150,6 @@ public:
       return Val.getAddrOfPtr1();
 
     return Val.template get<VecTy *>()->begin();
-
   }
   iterator end() {
     if (Val.template is<EltTy>())
diff --git a/include/llvm/ADT/Triple.h b/include/llvm/ADT/Triple.h
index 947812d94ecb..e01db0a61fd5 100644
--- a/include/llvm/ADT/Triple.h
+++ b/include/llvm/ADT/Triple.h
@@ -50,6 +50,7 @@ public:
     armeb,      // ARM (big endian): armeb
     aarch64,    // AArch64 (little endian): aarch64
     aarch64_be, // AArch64 (big endian): aarch64_be
+    avr,        // AVR: Atmel AVR microcontroller
     bpfel,      // eBPF or extended BPF or 64-bit BPF (little endian)
     bpfeb,      // eBPF or extended BPF or 64-bit BPF (big endian)
     hexagon,    // Hexagon: hexagon
@@ -75,8 +76,8 @@ public:
     xcore,      // XCore: xcore
     nvptx,      // NVPTX: 32-bit
     nvptx64,    // NVPTX: 64-bit
-    le32,       // le32: generic little-endian 32-bit CPU (PNaCl / Emscripten)
-    le64,       // le64: generic little-endian 64-bit CPU (PNaCl / Emscripten)
+    le32,       // le32: generic little-endian 32-bit CPU (PNaCl)
+    le64,       // le64: generic little-endian 64-bit CPU (PNaCl)
     amdil,      // AMDIL
     amdil64,    // AMDIL with 64-bit pointers
     hsail,      // AMD HSAIL
@@ -92,12 +93,14 @@ public:
   enum SubArchType {
     NoSubArch,
 
+    ARMSubArch_v8_2a,
     ARMSubArch_v8_1a,
     ARMSubArch_v8,
     ARMSubArch_v7,
     ARMSubArch_v7em,
     ARMSubArch_v7m,
     ARMSubArch_v7s,
+    ARMSubArch_v7k,
     ARMSubArch_v6,
     ARMSubArch_v6m,
     ARMSubArch_v6k,
@@ -124,7 +127,8 @@ public:
     MipsTechnologies,
     NVIDIA,
     CSR,
-    LastVendorType = CSR
+    Myriad,
+    LastVendorType = Myriad
   };
   enum OSType {
     UnknownOS,
@@ -153,7 +157,10 @@ public:
     NVCL,       // NVIDIA OpenCL
     AMDHSA,     // AMD HSA Runtime
     PS4,
-    LastOSType = PS4
+    ELFIAMCU,
+    TvOS,       // Apple tvOS
+    WatchOS,    // Apple watchOS
+    LastOSType = WatchOS
   };
   enum EnvironmentType {
     UnknownEnvironment,
@@ -170,7 +177,9 @@ public:
     MSVC,
     Itanium,
     Cygnus,
-    LastEnvironmentType = Cygnus
+    AMDOpenCL,
+    CoreCLR,
+    LastEnvironmentType = CoreCLR
   };
   enum ObjectFormatType {
     UnknownObjectFormat,
@@ -205,7 +214,7 @@ public:
   /// @name Constructors
   /// @{
 
-  /// \brief Default constructor is the same as an empty string and leaves all
+  /// Default constructor is the same as an empty string and leaves all
   /// triple fields unknown.
   Triple() : Data(), Arch(), Vendor(), OS(), Environment(), ObjectFormat() {}
 
@@ -231,7 +240,7 @@ public:
   /// common case in which otherwise valid components are in the wrong order.
   static std::string normalize(StringRef Str);
 
-  /// \brief Return the normalized form of this triple's string.
+  /// Return the normalized form of this triple's string.
   std::string normalize() const { return normalize(Data); }
 
   /// @}
@@ -259,7 +268,7 @@ public:
   /// getEnvironment - Get the parsed environment type of this triple.
   EnvironmentType getEnvironment() const { return Environment; }
 
-  /// \brief Parse the version number from the OS name component of the
+  /// Parse the version number from the OS name component of the
   /// triple, if present.
   ///
   /// For example, "fooos1.2.3" would return (1, 2, 3).
@@ -295,10 +304,15 @@ public:
                         unsigned &Micro) const;
 
   /// getiOSVersion - Parse the version number as with getOSVersion.  This should
-  /// only be called with IOS triples.
+  /// only be called with IOS or generic triples.
   void getiOSVersion(unsigned &Major, unsigned &Minor,
                      unsigned &Micro) const;
 
+  /// getWatchOSVersion - Parse the version number as with getOSVersion.  This
+  /// should only be called with WatchOS or generic triples.
+  void getWatchOSVersion(unsigned &Major, unsigned &Minor,
+                         unsigned &Micro) const;
+
   /// @}
   /// @name Direct Component Access
   /// @{
@@ -331,7 +345,7 @@ public:
   /// @name Convenience Predicates
   /// @{
 
-  /// \brief Test whether the architecture is 64-bit
+  /// Test whether the architecture is 64-bit
   ///
   /// Note that this tests for 64-bit pointer width, and nothing else. Note
   /// that we intentionally expose only three predicates, 64-bit, 32-bit, and
@@ -340,12 +354,12 @@ public:
   /// system is provided.
   bool isArch64Bit() const;
 
-  /// \brief Test whether the architecture is 32-bit
+  /// Test whether the architecture is 32-bit
   ///
   /// Note that this tests for 32-bit pointer width, and nothing else.
   bool isArch32Bit() const;
 
-  /// \brief Test whether the architecture is 16-bit
+  /// Test whether the architecture is 16-bit
   ///
   /// Note that this tests for 16-bit pointer width, and nothing else.
   bool isArch16Bit() const;
@@ -396,13 +410,27 @@ public:
   }
 
   /// Is this an iOS triple.
+  /// Note: This identifies tvOS as a variant of iOS. If that ever
+  /// changes, i.e., if the two operating systems diverge or their version
+  /// numbers get out of sync, that will need to be changed.
+  /// watchOS has completely different version numbers so it is not included.
   bool isiOS() const {
-    return getOS() == Triple::IOS;
+    return getOS() == Triple::IOS || isTvOS();
+  }
+
+  /// Is this an Apple tvOS triple.
+  bool isTvOS() const {
+    return getOS() == Triple::TvOS;
+  }
+
+  /// Is this an Apple watchOS triple.
+  bool isWatchOS() const {
+    return getOS() == Triple::WatchOS;
   }
 
-  /// isOSDarwin - Is this a "Darwin" OS (OS X or iOS).
+  /// isOSDarwin - Is this a "Darwin" OS (OS X, iOS, or watchOS).
   bool isOSDarwin() const {
-    return isMacOSX() || isiOS();
+    return isMacOSX() || isiOS() || isWatchOS();
   }
 
   bool isOSNetBSD() const {
@@ -427,16 +455,26 @@ public:
     return getOS() == Triple::Bitrig;
   }
 
+  bool isOSIAMCU() const {
+    return getOS() == Triple::ELFIAMCU;
+  }
+
+  /// Checks if the environment could be MSVC.
   bool isWindowsMSVCEnvironment() const {
     return getOS() == Triple::Win32 &&
            (getEnvironment() == Triple::UnknownEnvironment ||
             getEnvironment() == Triple::MSVC);
   }
 
+  /// Checks if the environment is MSVC.
   bool isKnownWindowsMSVCEnvironment() const {
     return getOS() == Triple::Win32 && getEnvironment() == Triple::MSVC;
   }
 
+  bool isWindowsCoreCLREnvironment() const {
+    return getOS() == Triple::Win32 && getEnvironment() == Triple::CoreCLR;
+  }
+
   bool isWindowsItaniumEnvironment() const {
     return getOS() == Triple::Win32 && getEnvironment() == Triple::Itanium;
   }
@@ -449,60 +487,63 @@ public:
     return getOS() == Triple::Win32 && getEnvironment() == Triple::GNU;
   }
 
-  /// \brief Tests for either Cygwin or MinGW OS
+  /// Tests for either Cygwin or MinGW OS
   bool isOSCygMing() const {
     return isWindowsCygwinEnvironment() || isWindowsGNUEnvironment();
   }
 
-  /// \brief Is this a "Windows" OS targeting a "MSVCRT.dll" environment.
+  /// Is this a "Windows" OS targeting a "MSVCRT.dll" environment.
   bool isOSMSVCRT() const {
     return isWindowsMSVCEnvironment() || isWindowsGNUEnvironment() ||
            isWindowsItaniumEnvironment();
   }
 
-  /// \brief Tests whether the OS is Windows.
+  /// Tests whether the OS is Windows.
   bool isOSWindows() const {
     return getOS() == Triple::Win32;
   }
 
-  /// \brief Tests whether the OS is NaCl (Native Client)
+  /// Tests whether the OS is NaCl (Native Client)
   bool isOSNaCl() const {
     return getOS() == Triple::NaCl;
   }
 
-  /// \brief Tests whether the OS is Linux.
+  /// Tests whether the OS is Linux.
   bool isOSLinux() const {
     return getOS() == Triple::Linux;
   }
 
-  /// \brief Tests whether the OS uses the ELF binary format.
+  /// Tests whether the OS uses the ELF binary format.
   bool isOSBinFormatELF() const {
     return getObjectFormat() == Triple::ELF;
   }
 
-  /// \brief Tests whether the OS uses the COFF binary format.
+  /// Tests whether the OS uses the COFF binary format.
   bool isOSBinFormatCOFF() const {
     return getObjectFormat() == Triple::COFF;
   }
 
-  /// \brief Tests whether the environment is MachO.
+  /// Tests whether the environment is MachO.
   bool isOSBinFormatMachO() const {
     return getObjectFormat() == Triple::MachO;
   }
 
-  /// \brief Tests whether the target is the PS4 CPU
+  /// Tests whether the target is the PS4 CPU
   bool isPS4CPU() const {
     return getArch() == Triple::x86_64 &&
            getVendor() == Triple::SCEI &&
            getOS() == Triple::PS4;
   }
 
-  /// \brief Tests whether the target is the PS4 platform
+  /// Tests whether the target is the PS4 platform
   bool isPS4() const {
     return getVendor() == Triple::SCEI &&
            getOS() == Triple::PS4;
   }
 
+  /// Tests whether the target is Android
+  bool isAndroid() const { return getEnvironment() == Triple::Android; }
+
   /// @}
   /// @name Mutators
   /// @{
@@ -553,7 +594,7 @@ public:
   /// @name Helpers to build variants of a particular triple.
   /// @{
 
-  /// \brief Form a triple with a 32-bit variant of the current architecture.
+  /// Form a triple with a 32-bit variant of the current architecture.
   ///
   /// This can be used to move across "families" of architectures where useful.
   ///
@@ -561,7 +602,7 @@ public:
   ///          architecture if no such variant can be found.
   llvm::Triple get32BitArchVariant() const;
 
-  /// \brief Form a triple with a 64-bit variant of the current architecture.
+  /// Form a triple with a 64-bit variant of the current architecture.
   ///
   /// This can be used to move across "families" of architectures where useful.
   ///
@@ -589,7 +630,7 @@ public:
   ///
   /// \param Arch the architecture name (e.g., "armv7s"). If it is an empty
   /// string then the triple's arch name is used.
-  const char* getARMCPUForArch(StringRef Arch = StringRef()) const;
+  StringRef getARMCPUForArch(StringRef Arch = StringRef()) const;
 
   /// @}
   /// @name Static helpers for IDs.
diff --git a/include/llvm/ADT/UniqueVector.h b/include/llvm/ADT/UniqueVector.h
index a9cb2f5709eb..e1ab4b56023f 100644
--- a/include/llvm/ADT/UniqueVector.h
+++ b/include/llvm/ADT/UniqueVector.h
@@ -11,6 +11,7 @@
 #define LLVM_ADT_UNIQUEVECTOR_H
 
 #include <cassert>
+#include <cstddef>
 #include <map>
 #include <vector>
 
diff --git a/include/llvm/ADT/ilist.h b/include/llvm/ADT/ilist.h
index a7b9306b3a73..3044a6c435f1 100644
--- a/include/llvm/ADT/ilist.h
+++ b/include/llvm/ADT/ilist.h
@@ -104,6 +104,53 @@ struct ilist_sentinel_traits {
   }
 };
 
+template <typename NodeTy> class ilist_half_node;
+template <typename NodeTy> class ilist_node;
+
+/// Traits with an embedded ilist_node as a sentinel.
+///
+/// FIXME: The downcast in createSentinel() is UB.
+template <typename NodeTy> struct ilist_embedded_sentinel_traits {
+  /// Get hold of the node that marks the end of the list.
+  NodeTy *createSentinel() const {
+    // Since i(p)lists always publicly derive from their corresponding traits,
+    // placing a data member in this class will augment the i(p)list.  But since
+    // the NodeTy is expected to be publicly derive from ilist_node<NodeTy>,
+    // there is a legal viable downcast from it to NodeTy. We use this trick to
+    // superimpose an i(p)list with a "ghostly" NodeTy, which becomes the
+    // sentinel. Dereferencing the sentinel is forbidden (save the
+    // ilist_node<NodeTy>), so no one will ever notice the superposition.
+    return static_cast<NodeTy *>(&Sentinel);
+  }
+  static void destroySentinel(NodeTy *) {}
+
+  NodeTy *provideInitialHead() const { return createSentinel(); }
+  NodeTy *ensureHead(NodeTy *) const { return createSentinel(); }
+  static void noteHead(NodeTy *, NodeTy *) {}
+
+private:
+  mutable ilist_node<NodeTy> Sentinel;
+};
+
+/// Trait with an embedded ilist_half_node as a sentinel.
+///
+/// FIXME: The downcast in createSentinel() is UB.
+template <typename NodeTy> struct ilist_half_embedded_sentinel_traits {
+  /// Get hold of the node that marks the end of the list.
+  NodeTy *createSentinel() const {
+    // See comment in ilist_embedded_sentinel_traits::createSentinel().
+    return static_cast<NodeTy *>(&Sentinel);
+  }
+  static void destroySentinel(NodeTy *) {}
+
+  NodeTy *provideInitialHead() const { return createSentinel(); }
+  NodeTy *ensureHead(NodeTy *) const { return createSentinel(); }
+  static void noteHead(NodeTy *, NodeTy *) {}
+
+private:
+  mutable ilist_half_node<NodeTy> Sentinel;
+};
+
 /// ilist_node_traits - A fragment for template traits for intrusive list
 /// that provides default node related operations.
 ///
@@ -173,8 +220,8 @@ private:
   template<class T> void operator-(T) const;
 public:
 
-  ilist_iterator(pointer NP) : NodePtr(NP) {}
-  ilist_iterator(reference NR) : NodePtr(&NR) {}
+  explicit ilist_iterator(pointer NP) : NodePtr(NP) {}
+  explicit ilist_iterator(reference NR) : NodePtr(&NR) {}
   ilist_iterator() : NodePtr(nullptr) {}
 
   // This is templated so that we can allow constructing a const iterator from
@@ -191,8 +238,10 @@ public:
     return *this;
   }
 
+  void reset(pointer NP) { NodePtr = NP; }
+
   // Accessors...
-  operator pointer() const {
+  explicit operator pointer() const {
     return NodePtr;
   }
 
@@ -202,11 +251,11 @@ public:
   pointer operator->() const { return &operator*(); }
 
   // Comparison operators
-  bool operator==(const ilist_iterator &RHS) const {
-    return NodePtr == RHS.NodePtr;
+  template <class Y> bool operator==(const ilist_iterator<Y> &RHS) const {
+    return NodePtr == RHS.getNodePtrUnchecked();
   }
-  bool operator!=(const ilist_iterator &RHS) const {
-    return NodePtr != RHS.NodePtr;
+  template <class Y> bool operator!=(const ilist_iterator<Y> &RHS) const {
+    return NodePtr != RHS.getNodePtrUnchecked();
   }
 
   // Increment and decrement operators...
@@ -422,7 +471,7 @@ public:
     this->setPrev(CurNode, New);
 
     this->addNodeToList(New);  // Notify traits that we added a node...
-    return New;
+    return iterator(New);
   }
 
   iterator insertAfter(iterator where, NodeTy *New) {
@@ -443,7 +492,7 @@ public:
     else
       Head = NextNode;
     this->setPrev(NextNode, PrevNode);
-    IT = NextNode;
+    IT.reset(NextNode);
     this->removeNodeFromList(Node);  // Notify traits that we removed a node...
 
     // Set the next/prev pointers of the current node to null.  This isn't
@@ -461,12 +510,18 @@ public:
     return remove(MutIt);
   }
 
+  NodeTy *remove(NodeTy *IT) { return remove(iterator(IT)); }
+  NodeTy *remove(NodeTy &IT) { return remove(iterator(IT)); }
+
   // erase - remove a node from the controlled sequence... and delete it.
   iterator erase(iterator where) {
     this->deleteNode(remove(where));
     return where;
   }
 
+  iterator erase(NodeTy *IT) { return erase(iterator(IT)); }
+  iterator erase(NodeTy &IT) { return erase(iterator(IT)); }
+
   /// Remove all nodes from the list like clear(), but do not call
   /// removeNodeFromList() or deleteNode().
   ///
@@ -522,7 +577,7 @@ private:
       this->setNext(Last, PosNext);
       this->setPrev(PosNext, Last);
 
-      this->transferNodesFromList(L2, First, PosNext);
+      this->transferNodesFromList(L2, iterator(First), iterator(PosNext));
 
       // Now that everything is set, restore the pointers to the list sentinels.
       L2.setTail(L2Sentinel);
@@ -579,6 +634,83 @@ public:
   void splice(iterator where, iplist &L2, iterator first, iterator last) {
     if (first != last) transfer(where, L2, first, last);
   }
+  void splice(iterator where, iplist &L2, NodeTy &N) {
+    splice(where, L2, iterator(N));
+  }
+  void splice(iterator where, iplist &L2, NodeTy *N) {
+    splice(where, L2, iterator(N));
+  }
+
+  template <class Compare>
+  void merge(iplist &Right, Compare comp) {
+    if (this == &Right)
+      return;
+    iterator First1 = begin(), Last1 = end();
+    iterator First2 = Right.begin(), Last2 = Right.end();
+    while (First1 != Last1 && First2 != Last2) {
+      if (comp(*First2, *First1)) {
+        iterator Next = First2;
+        transfer(First1, Right, First2, ++Next);
+        First2 = Next;
+      } else {
+        ++First1;
+      }
+    }
+    if (First2 != Last2)
+      transfer(Last1, Right, First2, Last2);
+  }
+  void merge(iplist &Right) { return merge(Right, op_less); }
+
+  template <class Compare>
+  void sort(Compare comp) {
+    // The list is empty, vacuously sorted.
+    if (empty())
+      return;
+    // The list has a single element, vacuously sorted.
+    if (std::next(begin()) == end())
+      return;
+    // Find the split point for the list.
+    iterator Center = begin(), End = begin();
+    while (End != end() && std::next(End) != end()) {
+      Center = std::next(Center);
+      End = std::next(std::next(End));
+    }
+    // Split the list into two.
+    iplist RightHalf;
+    RightHalf.splice(RightHalf.begin(), *this, Center, end());
+
+    // Sort the two sublists.
+    sort(comp);
+    RightHalf.sort(comp);
+
+    // Merge the two sublists back together.
+    merge(RightHalf, comp);
+  }
+  void sort() { sort(op_less); }
+
+  /// \brief Get the previous node, or \c nullptr for the list head.
+  NodeTy *getPrevNode(NodeTy &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.
+  const NodeTy *getPrevNode(const NodeTy &N) const {
+    return getPrevNode(const_cast<NodeTy &>(N));
+  }
+
+  /// \brief Get the next node, or \c nullptr for the list tail.
+  NodeTy *getNextNode(NodeTy &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.
+  const NodeTy *getNextNode(const NodeTy &N) const {
+    return getNextNode(const_cast<NodeTy &>(N));
+  }
 };
 
 
diff --git a/include/llvm/ADT/ilist_node.h b/include/llvm/ADT/ilist_node.h
index 26d0b55e4093..7e5a0e0e5ad8 100644
--- a/include/llvm/ADT/ilist_node.h
+++ b/include/llvm/ADT/ilist_node.h
@@ -19,12 +19,15 @@ namespace llvm {
 
 template<typename NodeTy>
 struct ilist_traits;
+template <typename NodeTy> struct ilist_embedded_sentinel_traits;
+template <typename NodeTy> struct ilist_half_embedded_sentinel_traits;
 
 /// ilist_half_node - Base class that provides prev services for sentinels.
 ///
 template<typename NodeTy>
 class ilist_half_node {
   friend struct ilist_traits<NodeTy>;
+  friend struct ilist_half_embedded_sentinel_traits<NodeTy>;
   NodeTy *Prev;
 protected:
   NodeTy *getPrev() { return Prev; }
@@ -36,6 +39,8 @@ protected:
 template<typename NodeTy>
 struct ilist_nextprev_traits;
 
+template <typename NodeTy> class ilist_iterator;
+
 /// ilist_node - Base class that provides next/prev services for nodes
 /// that use ilist_nextprev_traits or ilist_default_traits.
 ///
@@ -43,6 +48,8 @@ template<typename NodeTy>
 class ilist_node : private ilist_half_node<NodeTy> {
   friend struct ilist_nextprev_traits<NodeTy>;
   friend struct ilist_traits<NodeTy>;
+  friend struct ilist_half_embedded_sentinel_traits<NodeTy>;
+  friend struct ilist_embedded_sentinel_traits<NodeTy>;
   NodeTy *Next;
   NodeTy *getNext() { return Next; }
   const NodeTy *getNext() const { return Next; }
@@ -51,53 +58,63 @@ protected:
   ilist_node() : Next(nullptr) {}
 
 public:
-  /// @name Adjacent Node Accessors
-  /// @{
-
-  /// \brief Get the previous node, or 0 for the list head.
-  NodeTy *getPrevNode() {
-    NodeTy *Prev = this->getPrev();
+  ilist_iterator<NodeTy> getIterator() {
+    // FIXME: Stop downcasting to create the iterator (potential UB).
+    return ilist_iterator<NodeTy>(static_cast<NodeTy *>(this));
+  }
+  ilist_iterator<const NodeTy> getIterator() const {
+    // FIXME: Stop downcasting to create the iterator (potential UB).
+    return ilist_iterator<const NodeTy>(static_cast<const NodeTy *>(this));
+  }
+};
 
-    // Check for sentinel.
-    if (!Prev->getNext())
-      return nullptr;
+/// An ilist node that can access its parent list.
+///
+/// Requires \c NodeTy to have \a getParent() to find the parent node, and the
+/// \c ParentTy to have \a getSublistAccess() to get a reference to the list.
+template <typename NodeTy, typename ParentTy>
+class ilist_node_with_parent : public ilist_node<NodeTy> {
+protected:
+  ilist_node_with_parent() = default;
 
-    return Prev;
+private:
+  /// Forward to NodeTy::getParent().
+  ///
+  /// Note: do not use the name "getParent()".  We want a compile error
+  /// (instead of recursion) when the subclass fails to implement \a
+  /// getParent().
+  const ParentTy *getNodeParent() const {
+    return static_cast<const NodeTy *>(this)->getParent();
   }
 
-  /// \brief Get the previous node, or 0 for the list head.
+public:
+  /// @name Adjacent Node Accessors
+  /// @{
+  /// \brief 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).
+    const auto &List =
+        getNodeParent()->*(ParentTy::getSublistAccess((NodeTy *)nullptr));
+    return List.getPrevNode(*static_cast<NodeTy *>(this));
+  }
+  /// \brief Get the previous node, or \c nullptr for the list head.
   const NodeTy *getPrevNode() const {
-    const NodeTy *Prev = this->getPrev();
-
-    // Check for sentinel.
-    if (!Prev->getNext())
-      return nullptr;
-
-    return Prev;
+    return const_cast<ilist_node_with_parent *>(this)->getPrevNode();
   }
 
-  /// \brief Get the next node, or 0 for the list tail.
+  /// \brief Get the next node, or \c nullptr for the list tail.
   NodeTy *getNextNode() {
-    NodeTy *Next = getNext();
-
-    // Check for sentinel.
-    if (!Next->getNext())
-      return nullptr;
-
-    return Next;
+    // Should be separated to a reused function, but then we couldn't use auto
+    // (and would need the type of the list).
+    const auto &List =
+        getNodeParent()->*(ParentTy::getSublistAccess((NodeTy *)nullptr));
+    return List.getNextNode(*static_cast<NodeTy *>(this));
   }
-
-  /// \brief Get the next node, or 0 for the list tail.
+  /// \brief Get the next node, or \c nullptr for the list tail.
   const NodeTy *getNextNode() const {
-    const NodeTy *Next = getNext();
-
-    // Check for sentinel.
-    if (!Next->getNext())
-      return nullptr;
-
-    return Next;
+    return const_cast<ilist_node_with_parent *>(this)->getNextNode();
   }
-
   /// @}
 };
 
diff --git a/include/llvm/ADT/iterator_range.h b/include/llvm/ADT/iterator_range.h
index 523a86f02e08..3dd679bd9b79 100644
--- a/include/llvm/ADT/iterator_range.h
+++ b/include/llvm/ADT/iterator_range.h
@@ -20,6 +20,7 @@
 #define LLVM_ADT_ITERATOR_RANGE_H
 
 #include <utility>
+#include <iterator>
 
 namespace llvm {
 
@@ -32,6 +33,12 @@ class iterator_range {
   IteratorT begin_iterator, end_iterator;
 
 public:
+  //TODO: Add SFINAE to test that the Container's iterators match the range's
+  //      iterators.
+  template <typename Container>
+  iterator_range(Container &&c)
+  //TODO: Consider ADL/non-member begin/end calls.
+      : begin_iterator(c.begin()), end_iterator(c.end()) {}
   iterator_range(IteratorT begin_iterator, IteratorT end_iterator)
       : begin_iterator(std::move(begin_iterator)),
         end_iterator(std::move(end_iterator)) {}
@@ -51,6 +58,11 @@ template <class T> iterator_range<T> make_range(T x, T y) {
 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));
+}
 }
 
 #endif