Update aosp/master llvm for rebase to r233350

Change-Id: I07d935f8793ee8ec6b7da003f6483046594bca49

22 files changed, 460 insertions, 382 deletions

diff --git a/include/llvm/ADT/APFloat.h b/include/llvm/ADT/APFloat.h
index bf814e0..53b53c5 100644
--- a/include/llvm/ADT/APFloat.h
+++ b/include/llvm/ADT/APFloat.h
@@ -282,12 +282,6 @@ public:
   /// into FoldingSets.
   void Profile(FoldingSetNodeID &NID) const;
 
-  /// \brief Used by the Bitcode serializer to emit APInts to Bitcode.
-  void Emit(Serializer &S) const;
-
-  /// \brief Used by the Bitcode deserializer to deserialize APInts.
-  static APFloat ReadVal(Deserializer &D);
-
   /// \name Arithmetic
   /// @{
 
diff --git a/include/llvm/ADT/APInt.h b/include/llvm/ADT/APInt.h
index c2fe094..36d8159 100644
--- a/include/llvm/ADT/APInt.h
+++ b/include/llvm/ADT/APInt.h
@@ -25,9 +25,7 @@
 #include <string>
 
 namespace llvm {
-class Deserializer;
 class FoldingSetNodeID;
-class Serializer;
 class StringRef;
 class hash_code;
 class raw_ostream;
@@ -409,6 +407,13 @@ public:
                                                             : getZExtValue();
   }
 
+  /// \brief Check if the APInt consists of a repeated bit pattern.
+  ///
+  /// e.g. 0x01010101 satisfies isSplat(8).
+  /// \param SplatSizeInBits The size of the pattern in bits. Must divide bit
+  /// width without remainder.
+  bool isSplat(unsigned SplatSizeInBits) const;
+
   /// @}
   /// \name Value Generators
   /// @{
diff --git a/include/llvm/ADT/ArrayRef.h b/include/llvm/ADT/ArrayRef.h
index 5b7ed9c..f7b055e 100644
--- a/include/llvm/ADT/ArrayRef.h
+++ b/include/llvm/ADT/ArrayRef.h
@@ -11,7 +11,6 @@
 #define LLVM_ADT_ARRAYREF_H
 
 #include "llvm/ADT/None.h"
-#include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
 #include <vector>
 
@@ -44,19 +43,6 @@ namespace llvm {
     /// The number of elements.
     size_type Length;
 
-    /// \brief A dummy "optional" type that is only created by implicit
-    /// conversion from a reference to T.
-    ///
-    /// This type must *only* be used in a function argument or as a copy of
-    /// a function argument, as otherwise it will hold a pointer to a temporary
-    /// past that temporaries' lifetime.
-    struct TRefOrNothing {
-      const T *TPtr;
-
-      TRefOrNothing() : TPtr(nullptr) {}
-      TRefOrNothing(const T &TRef) : TPtr(&TRef) {}
-    };
-
   public:
     /// @name Constructors
     /// @{
@@ -151,13 +137,9 @@ namespace llvm {
     bool equals(ArrayRef RHS) const {
       if (Length != RHS.Length)
         return false;
-      // Don't use std::equal(), since it asserts in MSVC on nullptr iterators.
-      for (auto L = begin(), LE = end(), R = RHS.begin(); L != LE; ++L, ++R)
-        // Match std::equal() in using == (instead of !=) to minimize API
-        // requirements of ArrayRef'ed types.
-        if (!(*L == *R))
-          return false;
-      return true;
+      if (Length == 0)
+        return true;
+      return std::equal(begin(), end(), RHS.begin());
     }
 
     /// slice(n) - Chop off the first N elements of the array.
@@ -202,47 +184,6 @@ namespace llvm {
     }
 
     /// @}
-    /// @{
-    /// @name Convenience methods
-
-    /// @brief Predicate for testing that the array equals the exact sequence of
-    /// arguments.
-    ///
-    /// Will return false if the size is not equal to the exact number of
-    /// arguments given or if the array elements don't equal the argument
-    /// elements in order. Currently supports up to 16 arguments, but can
-    /// easily be extended.
-    bool equals(TRefOrNothing Arg0 = TRefOrNothing(),
-                TRefOrNothing Arg1 = TRefOrNothing(),
-                TRefOrNothing Arg2 = TRefOrNothing(),
-                TRefOrNothing Arg3 = TRefOrNothing(),
-                TRefOrNothing Arg4 = TRefOrNothing(),
-                TRefOrNothing Arg5 = TRefOrNothing(),
-                TRefOrNothing Arg6 = TRefOrNothing(),
-                TRefOrNothing Arg7 = TRefOrNothing(),
-                TRefOrNothing Arg8 = TRefOrNothing(),
-                TRefOrNothing Arg9 = TRefOrNothing(),
-                TRefOrNothing Arg10 = TRefOrNothing(),
-                TRefOrNothing Arg11 = TRefOrNothing(),
-                TRefOrNothing Arg12 = TRefOrNothing(),
-                TRefOrNothing Arg13 = TRefOrNothing(),
-                TRefOrNothing Arg14 = TRefOrNothing(),
-                TRefOrNothing Arg15 = TRefOrNothing()) {
-      TRefOrNothing Args[] = {Arg0,  Arg1,  Arg2,  Arg3, Arg4,  Arg5,
-                              Arg6,  Arg7,  Arg8,  Arg9, Arg10, Arg11,
-                              Arg12, Arg13, Arg14, Arg15};
-      if (size() > array_lengthof(Args))
-        return false;
-
-      for (unsigned i = 0, e = size(); i != e; ++i)
-        if (Args[i].TPtr == nullptr || (*this)[i] != *Args[i].TPtr)
-          return false;
-
-      // Either the size is exactly as many args, or the next arg must be null.
-      return size() == array_lengthof(Args) || Args[size()].TPtr == nullptr;
-    }
-
-    /// @}
   };
 
   /// MutableArrayRef - Represent a mutable reference to an array (0 or more
diff --git a/include/llvm/ADT/BitVector.h b/include/llvm/ADT/BitVector.h
index 0dbe810..f58dd73 100644
--- a/include/llvm/ADT/BitVector.h
+++ b/include/llvm/ADT/BitVector.h
@@ -53,7 +53,7 @@ public:
       BitPos = Idx % BITWORD_SIZE;
     }
 
-    ~reference() {}
+    reference(const reference&) = default;
 
     reference &operator=(reference t) {
       *this = bool(t);
diff --git a/include/llvm/ADT/DeltaAlgorithm.h b/include/llvm/ADT/DeltaAlgorithm.h
index 4d07e04..21bc1e8 100644
--- a/include/llvm/ADT/DeltaAlgorithm.h
+++ b/include/llvm/ADT/DeltaAlgorithm.h
@@ -77,6 +77,8 @@ protected:
   /// ExecuteOneTest - Execute a single test predicate on the change set \p S.
   virtual bool ExecuteOneTest(const changeset_ty &S) = 0;
 
+  DeltaAlgorithm& operator=(const DeltaAlgorithm&) = default;
+
 public:
   virtual ~DeltaAlgorithm();
 
diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h
index 1699ea3..8c65f70 100644
--- a/include/llvm/ADT/DenseMap.h
+++ b/include/llvm/ADT/DenseMap.h
@@ -15,6 +15,7 @@
 #define LLVM_ADT_DENSEMAP_H
 
 #include "llvm/ADT/DenseMapInfo.h"
+#include "llvm/ADT/EpochTracker.h"
 #include "llvm/Support/AlignOf.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/MathExtras.h"
@@ -50,7 +51,7 @@ class DenseMapIterator;
 
 template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT,
           typename BucketT>
-class DenseMapBase {
+class DenseMapBase : public DebugEpochBase {
 public:
   typedef unsigned size_type;
   typedef KeyT key_type;
@@ -62,16 +63,17 @@ public:
       const_iterator;
   inline iterator begin() {
     // When the map is empty, avoid the overhead of AdvancePastEmptyBuckets().
-    return empty() ? end() : iterator(getBuckets(), getBucketsEnd());
+    return empty() ? end() : iterator(getBuckets(), getBucketsEnd(), *this);
   }
   inline iterator end() {
-    return iterator(getBucketsEnd(), getBucketsEnd(), true);
+    return iterator(getBucketsEnd(), getBucketsEnd(), *this, true);
   }
   inline const_iterator begin() const {
-    return empty() ? end() : const_iterator(getBuckets(), getBucketsEnd());
+    return empty() ? end()
+                   : const_iterator(getBuckets(), getBucketsEnd(), *this);
   }
   inline const_iterator end() const {
-    return const_iterator(getBucketsEnd(), getBucketsEnd(), true);
+    return const_iterator(getBucketsEnd(), getBucketsEnd(), *this, true);
   }
 
   bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const {
@@ -81,11 +83,13 @@ public:
 
   /// Grow the densemap so that it has at least Size buckets. Does not shrink
   void resize(size_type Size) {
+    incrementEpoch();
     if (Size > getNumBuckets())
       grow(Size);
   }
 
   void clear() {
+    incrementEpoch();
     if (getNumEntries() == 0 && getNumTombstones() == 0) return;
 
     // If the capacity of the array is huge, and the # elements used is small,
@@ -118,13 +122,13 @@ public:
   iterator find(const KeyT &Val) {
     BucketT *TheBucket;
     if (LookupBucketFor(Val, TheBucket))
-      return iterator(TheBucket, getBucketsEnd(), true);
+      return iterator(TheBucket, getBucketsEnd(), *this, true);
     return end();
   }
   const_iterator find(const KeyT &Val) const {
     const BucketT *TheBucket;
     if (LookupBucketFor(Val, TheBucket))
-      return const_iterator(TheBucket, getBucketsEnd(), true);
+      return const_iterator(TheBucket, getBucketsEnd(), *this, true);
     return end();
   }
 
@@ -137,14 +141,14 @@ public:
   iterator find_as(const LookupKeyT &Val) {
     BucketT *TheBucket;
     if (LookupBucketFor(Val, TheBucket))
-      return iterator(TheBucket, getBucketsEnd(), true);
+      return iterator(TheBucket, getBucketsEnd(), *this, true);
     return end();
   }
   template<class LookupKeyT>
   const_iterator find_as(const LookupKeyT &Val) const {
     const BucketT *TheBucket;
     if (LookupBucketFor(Val, TheBucket))
-      return const_iterator(TheBucket, getBucketsEnd(), true);
+      return const_iterator(TheBucket, getBucketsEnd(), *this, true);
     return end();
   }
 
@@ -163,12 +167,13 @@ public:
   std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {
     BucketT *TheBucket;
     if (LookupBucketFor(KV.first, TheBucket))
-      return std::make_pair(iterator(TheBucket, getBucketsEnd(), true),
+      return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true),
                             false); // Already in map.
 
     // Otherwise, insert the new element.
     TheBucket = InsertIntoBucket(KV.first, KV.second, TheBucket);
-    return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), true);
+    return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true),
+                          true);
   }
 
   // Inserts key,value pair into the map if the key isn't already in the map.
@@ -177,14 +182,15 @@ public:
   std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) {
     BucketT *TheBucket;
     if (LookupBucketFor(KV.first, TheBucket))
-      return std::make_pair(iterator(TheBucket, getBucketsEnd(), true),
+      return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true),
                             false); // Already in map.
-    
+
     // Otherwise, insert the new element.
     TheBucket = InsertIntoBucket(std::move(KV.first),
                                  std::move(KV.second),
                                  TheBucket);
-    return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), true);
+    return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true),
+                          true);
   }
 
   /// insert - Range insertion of pairs.
@@ -431,6 +437,8 @@ private:
   }
 
   BucketT *InsertIntoBucketImpl(const KeyT &Key, BucketT *TheBucket) {
+    incrementEpoch();
+
     // If the load of the hash table is more than 3/4, or if fewer than 1/8 of
     // the buckets are empty (meaning that many are filled with tombstones),
     // grow the table.
@@ -987,9 +995,10 @@ private:
 
 template <typename KeyT, typename ValueT, typename KeyInfoT, typename Bucket,
           bool IsConst>
-class DenseMapIterator {
+class DenseMapIterator : DebugEpochBase::HandleBase {
   typedef DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, true> ConstIterator;
   friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, true>;
+  friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, false>;
 
 public:
   typedef ptrdiff_t difference_type;
@@ -1003,38 +1012,54 @@ private:
 public:
   DenseMapIterator() : Ptr(nullptr), End(nullptr) {}
 
-  DenseMapIterator(pointer Pos, pointer E, bool NoAdvance = false)
-    : Ptr(Pos), End(E) {
+  DenseMapIterator(pointer Pos, pointer E, const DebugEpochBase &Epoch,
+                   bool NoAdvance = false)
+      : DebugEpochBase::HandleBase(&Epoch), Ptr(Pos), End(E) {
+    assert(isHandleInSync() && "invalid construction!");
     if (!NoAdvance) AdvancePastEmptyBuckets();
   }
 
-  // If IsConst is true this is a converting constructor from iterator to
-  // const_iterator and the default copy constructor is used.
-  // Otherwise this is a copy constructor for iterator.
+  // Converting ctor from non-const iterators to const iterators. SFINAE'd out
+  // for const iterator destinations so it doesn't end up as a user defined copy
+  // constructor.
+  template <bool IsConstSrc,
+            typename = typename std::enable_if<!IsConstSrc && IsConst>::type>
   DenseMapIterator(
-      const DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, false> &I)
-      : Ptr(I.Ptr), End(I.End) {}
+      const DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, IsConstSrc> &I)
+      : DebugEpochBase::HandleBase(I), Ptr(I.Ptr), End(I.End) {}
 
   reference operator*() const {
+    assert(isHandleInSync() && "invalid iterator access!");
     return *Ptr;
   }
   pointer operator->() const {
+    assert(isHandleInSync() && "invalid iterator access!");
     return Ptr;
   }
 
   bool operator==(const ConstIterator &RHS) const {
-    return Ptr == RHS.operator->();
+    assert((!Ptr || isHandleInSync()) && "handle not in sync!");
+    assert((!RHS.Ptr || RHS.isHandleInSync()) && "handle not in sync!");
+    assert(getEpochAddress() == RHS.getEpochAddress() &&
+           "comparing incomparable iterators!");
+    return Ptr == RHS.Ptr;
   }
   bool operator!=(const ConstIterator &RHS) const {
-    return Ptr != RHS.operator->();
+    assert((!Ptr || isHandleInSync()) && "handle not in sync!");
+    assert((!RHS.Ptr || RHS.isHandleInSync()) && "handle not in sync!");
+    assert(getEpochAddress() == RHS.getEpochAddress() &&
+           "comparing incomparable iterators!");
+    return Ptr != RHS.Ptr;
   }
 
   inline DenseMapIterator& operator++() {  // Preincrement
+    assert(isHandleInSync() && "invalid iterator access!");
     ++Ptr;
     AdvancePastEmptyBuckets();
     return *this;
   }
   DenseMapIterator operator++(int) {  // Postincrement
+    assert(isHandleInSync() && "invalid iterator access!");
     DenseMapIterator tmp = *this; ++*this; return tmp;
   }
 
diff --git a/include/llvm/ADT/DepthFirstIterator.h b/include/llvm/ADT/DepthFirstIterator.h
index 6cd9e68..5186333 100644
--- a/include/llvm/ADT/DepthFirstIterator.h
+++ b/include/llvm/ADT/DepthFirstIterator.h
@@ -113,9 +113,8 @@ private:
       while (It != GT::child_end(Node)) {
         NodeType *Next = *It++;
         // Has our next sibling been visited?
-        if (Next && !this->Visited.count(Next)) {  
+        if (Next && this->Visited.insert(Next).second) {
           // No, do it now.
-          this->Visited.insert(Next);
           VisitStack.push_back(std::make_pair(PointerIntTy(Next, 0), 
                                               GT::child_begin(Next)));
           return;
@@ -129,58 +128,57 @@ private:
 
 public:
   typedef typename super::pointer pointer;
-  typedef df_iterator<GraphT, SetType, ExtStorage, GT> _Self;
 
   // Provide static begin and end methods as our public "constructors"
-  static inline _Self begin(const GraphT& G) {
-    return _Self(GT::getEntryNode(G));
+  static df_iterator begin(const GraphT &G) {
+    return df_iterator(GT::getEntryNode(G));
   }
-  static inline _Self end(const GraphT& G) { return _Self(); }
+  static df_iterator end(const GraphT &G) { return df_iterator(); }
 
   // Static begin and end methods as our public ctors for external iterators
-  static inline _Self begin(const GraphT& G, SetType &S) {
-    return _Self(GT::getEntryNode(G), S);
+  static df_iterator begin(const GraphT &G, SetType &S) {
+    return df_iterator(GT::getEntryNode(G), S);
   }
-  static inline _Self end(const GraphT& G, SetType &S) { return _Self(S); }
+  static df_iterator end(const GraphT &G, SetType &S) { return df_iterator(S); }
 
-  inline bool operator==(const _Self& x) const {
+  bool operator==(const df_iterator &x) const {
     return VisitStack == x.VisitStack;
   }
-  inline bool operator!=(const _Self& x) const { return !operator==(x); }
+  bool operator!=(const df_iterator &x) const { return !(*this == x); }
 
-  inline pointer operator*() const {
-    return VisitStack.back().first.getPointer();
-  }
+  pointer operator*() const { return VisitStack.back().first.getPointer(); }
 
   // This is a nonstandard operator-> that dereferences the pointer an extra
   // time... so that you can actually call methods ON the Node, because
   // the contained type is a pointer.  This allows BBIt->getTerminator() f.e.
   //
-  inline NodeType *operator->() const { return operator*(); }
+  NodeType *operator->() const { return **this; }
 
-  inline _Self& operator++() {   // Preincrement
+  df_iterator &operator++() { // Preincrement
     toNext();
     return *this;
   }
 
   // skips all children of the current node and traverses to next node
   //
-  inline _Self& skipChildren() {  
+  df_iterator &skipChildren() {
     VisitStack.pop_back();
     if (!VisitStack.empty())
       toNext();
     return *this;
   }
 
-  inline _Self operator++(int) { // Postincrement
-    _Self tmp = *this; ++*this; return tmp;
+  df_iterator operator++(int) { // Postincrement
+    df_iterator tmp = *this;
+    ++*this;
+    return tmp;
   }
 
   // nodeVisited - return true if this iterator has already visited the
   // specified node.  This is public, and will probably be used to iterate over
   // nodes that a depth first iteration did not find: ie unreachable nodes.
   //
-  inline bool nodeVisited(NodeType *Node) const {
+  bool nodeVisited(NodeType *Node) const {
     return this->Visited.count(Node) != 0;
   }
 
diff --git a/include/llvm/ADT/EpochTracker.h b/include/llvm/ADT/EpochTracker.h
new file mode 100644
index 0000000..d593073
--- /dev/null
+++ b/include/llvm/ADT/EpochTracker.h
@@ -0,0 +1,99 @@
+//===- llvm/ADT/EpochTracker.h - ADT epoch tracking --------------*- C++ -*-==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the DebugEpochBase and DebugEpochBase::HandleBase classes.
+// These can be used to write iterators that are fail-fast when LLVM is built
+// with asserts enabled.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_EPOCH_TRACKER_H
+#define LLVM_ADT_EPOCH_TRACKER_H
+
+#include "llvm/Config/llvm-config.h"
+
+#include <cstdint>
+
+namespace llvm {
+
+#ifndef LLVM_ENABLE_ABI_BREAKING_CHECKS
+
+class DebugEpochBase {
+public:
+  void incrementEpoch() {}
+
+  class HandleBase {
+  public:
+    HandleBase() {}
+    explicit HandleBase(const DebugEpochBase *) {}
+    bool isHandleInSync() const { return true; }
+    const void *getEpochAddress() const { return nullptr; }
+  };
+};
+
+#else
+
+/// \brief A base class for data structure classes wishing to make iterators
+/// ("handles") pointing into themselves fail-fast.  When building without
+/// asserts, this class is empty and does nothing.
+///
+/// DebugEpochBase does not by itself track handles pointing into itself.  The
+/// expectation is that routines touching the handles will poll on
+/// isHandleInSync at appropriate points to assert that the handle they're using
+/// is still valid.
+///
+class DebugEpochBase {
+  uint64_t Epoch;
+
+public:
+  DebugEpochBase() : Epoch(0) {}
+
+  /// \brief Calling incrementEpoch invalidates all handles pointing into the
+  /// calling instance.
+  void incrementEpoch() { ++Epoch; }
+
+  /// \brief The destructor calls incrementEpoch to make use-after-free bugs
+  /// more likely to crash deterministically.
+  ~DebugEpochBase() { incrementEpoch(); }
+
+  /// \brief A base class for iterator classes ("handles") that wish to poll for
+  /// iterator invalidating modifications in the underlying data structure.
+  /// When LLVM is built without asserts, this class is empty and does nothing.
+  ///
+  /// HandleBase does not track the parent data structure by itself.  It expects
+  /// the routines modifying the data structure to call incrementEpoch when they
+  /// make an iterator-invalidating modification.
+  ///
+  class HandleBase {
+    const uint64_t *EpochAddress;
+    uint64_t EpochAtCreation;
+
+  public:
+    HandleBase() : EpochAddress(nullptr), EpochAtCreation(UINT64_MAX) {}
+
+    explicit HandleBase(const DebugEpochBase *Parent)
+        : EpochAddress(&Parent->Epoch), EpochAtCreation(Parent->Epoch) {}
+
+    /// \brief Returns true if the DebugEpochBase this Handle is linked to has
+    /// not called incrementEpoch on itself since the creation of this
+    /// HandleBase instance.
+    bool isHandleInSync() const { return *EpochAddress == EpochAtCreation; }
+
+    /// \brief Returns a pointer to the epoch word stored in the data structure
+    /// this handle points into.  Can be used to check if two iterators point
+    /// into the same data structure.
+    const void *getEpochAddress() const { return EpochAddress; }
+  };
+};
+
+#endif // LLVM_ENABLE_ABI_BREAKING_CHECKS
+
+} // namespace llvm
+
+#endif
diff --git a/include/llvm/ADT/FoldingSet.h b/include/llvm/ADT/FoldingSet.h
index 7ade167..52d10c1 100644
--- a/include/llvm/ADT/FoldingSet.h
+++ b/include/llvm/ADT/FoldingSet.h
@@ -23,9 +23,6 @@
 #include "llvm/Support/DataTypes.h"
 
 namespace llvm {
-  class APFloat;
-  class APInt;
-
 /// This folding set used for two purposes:
 ///   1. Given information about a node we want to create, look up the unique
 ///      instance of the node in the set.  If the node already exists, return
@@ -110,6 +107,8 @@ class FoldingSetNodeID;
 /// back to the bucket to facilitate node removal.
 ///
 class FoldingSetImpl {
+  virtual void anchor(); // Out of line virtual method.
+
 protected:
   /// Buckets - Array of bucket chains.
   ///
@@ -123,10 +122,11 @@ protected:
   /// is greater than twice the number of buckets.
   unsigned NumNodes;
 
-public:
+  ~FoldingSetImpl();
+
   explicit FoldingSetImpl(unsigned Log2InitSize = 6);
-  virtual ~FoldingSetImpl();
 
+public:
   //===--------------------------------------------------------------------===//
   /// Node - This class is used to maintain the singly linked bucket list in
   /// a folding set.
@@ -393,7 +393,7 @@ 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.
 ///
-template<class T> class FoldingSet : public FoldingSetImpl {
+template <class T> class FoldingSet final : public FoldingSetImpl {
 private:
   /// GetNodeProfile - Each instantiatation of the FoldingSet needs to provide a
   /// way to convert nodes into a unique specifier.
@@ -463,7 +463,7 @@ public:
 /// function with signature
 ///   void Profile(llvm::FoldingSetNodeID &, Ctx);
 template <class T, class Ctx>
-class ContextualFoldingSet : public FoldingSetImpl {
+class ContextualFoldingSet final : public FoldingSetImpl {
   // Unfortunately, this can't derive from FoldingSet<T> because the
   // construction vtable for FoldingSet<T> requires
   // FoldingSet<T>::GetNodeProfile to be instantiated, which in turn
diff --git a/include/llvm/ADT/ImmutableMap.h b/include/llvm/ADT/ImmutableMap.h
index 75fee90..438dec2 100644
--- a/include/llvm/ADT/ImmutableMap.h
+++ b/include/llvm/ADT/ImmutableMap.h
@@ -203,33 +203,14 @@ public:
   // Iterators.
   //===--------------------------------------------------===//
 
-  class iterator {
-    typename TreeTy::iterator itr;
-
-    iterator() {}
-    iterator(TreeTy* t) : itr(t) {}
+  class iterator : public ImutAVLValueIterator<ImmutableMap> {
+    iterator() = default;
+    explicit iterator(TreeTy *Tree) : iterator::ImutAVLValueIterator(Tree) {}
     friend class ImmutableMap;
 
   public:
-    typedef ptrdiff_t difference_type;
-    typedef typename ImmutableMap<KeyT,ValT,ValInfo>::value_type value_type;
-    typedef typename ImmutableMap<KeyT,ValT,ValInfo>::value_type_ref reference;
-    typedef typename iterator::value_type *pointer;
-    typedef std::bidirectional_iterator_tag iterator_category;
-
-    typename iterator::reference operator*() const { return itr->getValue(); }
-    typename iterator::pointer   operator->() const { return &itr->getValue(); }
-
-    key_type_ref getKey() const { return itr->getValue().first; }
-    data_type_ref getData() const { return itr->getValue().second; }
-
-    iterator& operator++() { ++itr; return *this; }
-    iterator  operator++(int) { iterator tmp(*this); ++itr; return tmp; }
-    iterator& operator--() { --itr; return *this; }
-    iterator  operator--(int) { iterator tmp(*this); --itr; return tmp; }
-
-    bool operator==(const iterator& RHS) const { return RHS.itr == itr; }
-    bool operator!=(const iterator& RHS) const { return RHS.itr != itr; }
+    key_type_ref getKey() const { return (*this)->first; }
+    data_type_ref getData() const { return (*this)->second; }
   };
 
   iterator begin() const { return iterator(Root); }
@@ -376,30 +357,17 @@ public:
   //===--------------------------------------------------===//
   // Iterators.
   //===--------------------------------------------------===//
-  
-  class iterator {
-    typename TreeTy::iterator itr;
-    
-    iterator() {}
-    iterator(TreeTy* t) : itr(t) {}
+
+  class iterator : public ImutAVLValueIterator<ImmutableMapRef> {
+    iterator() = default;
+    explicit iterator(TreeTy *Tree) : iterator::ImutAVLValueIterator(Tree) {}
     friend class ImmutableMapRef;
-    
+
   public:
-    value_type_ref operator*() const { return itr->getValue(); }
-    value_type*    operator->() const { return &itr->getValue(); }
-    
-    key_type_ref getKey() const { return itr->getValue().first; }
-    data_type_ref getData() const { return itr->getValue().second; }
-    
-    
-    iterator& operator++() { ++itr; return *this; }
-    iterator  operator++(int) { iterator tmp(*this); ++itr; return tmp; }
-    iterator& operator--() { --itr; return *this; }
-    iterator  operator--(int) { iterator tmp(*this); --itr; return tmp; }
-    bool operator==(const iterator& RHS) const { return RHS.itr == itr; }
-    bool operator!=(const iterator& RHS) const { return RHS.itr != itr; }
+    key_type_ref getKey() const { return (*this)->first; }
+    data_type_ref getData() const { return (*this)->second; }
   };
-  
+
   iterator begin() const { return iterator(Root); }
   iterator end() const { return iterator(); }
   
diff --git a/include/llvm/ADT/ImmutableSet.h b/include/llvm/ADT/ImmutableSet.h
index 3c6f58c..87026f0 100644
--- a/include/llvm/ADT/ImmutableSet.h
+++ b/include/llvm/ADT/ImmutableSet.h
@@ -142,13 +142,13 @@ public:
     iterator RItr = RHS.begin(), REnd = RHS.end();
 
     while (LItr != LEnd && RItr != REnd) {
-      if (*LItr == *RItr) {
+      if (&*LItr == &*RItr) {
         LItr.skipSubTree();
         RItr.skipSubTree();
         continue;
       }
 
-      if (!LItr->isElementEqual(*RItr))
+      if (!LItr->isElementEqual(&*RItr))
         return false;
 
       ++LItr;
@@ -293,8 +293,8 @@ private:
     height = h;
   }
 
-  static inline
-  uint32_t computeDigest(ImutAVLTree* L, ImutAVLTree* R, value_type_ref V) {
+  static uint32_t computeDigest(ImutAVLTree *L, ImutAVLTree *R,
+                                value_type_ref V) {
     uint32_t digest = 0;
 
     if (L)
@@ -311,7 +311,7 @@ private:
     return digest;
   }
 
-  inline uint32_t computeDigest() {
+  uint32_t computeDigest() {
     // Check the lowest bit to determine if digest has actually been
     // pre-computed.
     if (hasCachedDigest())
@@ -429,9 +429,7 @@ protected:
   value_type_ref  getValue(TreeTy* T) const { return T->value; }
 
   // Make sure the index is not the Tombstone or Entry key of the DenseMap.
-  static inline unsigned maskCacheIndex(unsigned I) {
-    return (I & ~0x02);
-  }
+  static unsigned maskCacheIndex(unsigned I) { return (I & ~0x02); }
 
   unsigned incrementHeight(TreeTy* L, TreeTy* R) const {
     unsigned hl = getHeight(L);
@@ -444,7 +442,7 @@ protected:
                                      typename TreeTy::iterator& TE) {
     typename TreeTy::iterator I = T->begin(), E = T->end();
     for ( ; I!=E ; ++I, ++TI) {
-      if (TI == TE || !I->isElementEqual(*TI))
+      if (TI == TE || !I->isElementEqual(&*TI))
         return false;
     }
     return true;
@@ -647,24 +645,26 @@ public:
 //===----------------------------------------------------------------------===//
 
 template <typename ImutInfo>
-class ImutAVLTreeGenericIterator {
+class ImutAVLTreeGenericIterator
+    : public std::iterator<std::bidirectional_iterator_tag,
+                           ImutAVLTree<ImutInfo>> {
   SmallVector<uintptr_t,20> stack;
 public:
   enum VisitFlag { VisitedNone=0x0, VisitedLeft=0x1, VisitedRight=0x3,
                    Flags=0x3 };
 
   typedef ImutAVLTree<ImutInfo> TreeTy;
-  typedef ImutAVLTreeGenericIterator<ImutInfo> _Self;
 
-  inline ImutAVLTreeGenericIterator() {}
-  inline ImutAVLTreeGenericIterator(const TreeTy* Root) {
+  ImutAVLTreeGenericIterator() {}
+  ImutAVLTreeGenericIterator(const TreeTy *Root) {
     if (Root) stack.push_back(reinterpret_cast<uintptr_t>(Root));
   }
 
-  TreeTy* operator*() const {
+  TreeTy &operator*() const {
     assert(!stack.empty());
-    return reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
+    return *reinterpret_cast<TreeTy *>(stack.back() & ~Flags);
   }
+  TreeTy *operator->() const { return &*this; }
 
   uintptr_t getVisitState() const {
     assert(!stack.empty());
@@ -695,13 +695,15 @@ public:
     }
   }
 
-  inline bool operator==(const _Self& x) const {
+  bool operator==(const ImutAVLTreeGenericIterator &x) const {
     return stack == x.stack;
   }
 
-  inline bool operator!=(const _Self& x) const { return !operator==(x); }
+  bool operator!=(const ImutAVLTreeGenericIterator &x) const {
+    return !(*this == x);
+  }
 
-  _Self& operator++() {
+  ImutAVLTreeGenericIterator &operator++() {
     assert(!stack.empty());
     TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
     assert(Current);
@@ -727,7 +729,7 @@ public:
     return *this;
   }
 
-  _Self& operator--() {
+  ImutAVLTreeGenericIterator &operator--() {
     assert(!stack.empty());
     TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
     assert(Current);
@@ -754,30 +756,34 @@ public:
 };
 
 template <typename ImutInfo>
-class ImutAVLTreeInOrderIterator {
+class ImutAVLTreeInOrderIterator
+    : public std::iterator<std::bidirectional_iterator_tag,
+                           ImutAVLTree<ImutInfo>> {
   typedef ImutAVLTreeGenericIterator<ImutInfo> InternalIteratorTy;
   InternalIteratorTy InternalItr;
 
 public:
   typedef ImutAVLTree<ImutInfo> TreeTy;
-  typedef ImutAVLTreeInOrderIterator<ImutInfo> _Self;
 
   ImutAVLTreeInOrderIterator(const TreeTy* Root) : InternalItr(Root) {
-    if (Root) operator++(); // Advance to first element.
+    if (Root)
+      ++*this; // Advance to first element.
   }
 
   ImutAVLTreeInOrderIterator() : InternalItr() {}
 
-  inline bool operator==(const _Self& x) const {
+  bool operator==(const ImutAVLTreeInOrderIterator &x) const {
     return InternalItr == x.InternalItr;
   }
 
-  inline bool operator!=(const _Self& x) const { return !operator==(x); }
+  bool operator!=(const ImutAVLTreeInOrderIterator &x) const {
+    return !(*this == x);
+  }
 
-  inline TreeTy* operator*() const { return *InternalItr; }
-  inline TreeTy* operator->() const { return *InternalItr; }
+  TreeTy &operator*() const { return *InternalItr; }
+  TreeTy *operator->() const { return &*InternalItr; }
 
-  inline _Self& operator++() {
+  ImutAVLTreeInOrderIterator &operator++() {
     do ++InternalItr;
     while (!InternalItr.atEnd() &&
            InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
@@ -785,7 +791,7 @@ public:
     return *this;
   }
 
-  inline _Self& operator--() {
+  ImutAVLTreeInOrderIterator &operator--() {
     do --InternalItr;
     while (!InternalItr.atBeginning() &&
            InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
@@ -793,7 +799,7 @@ public:
     return *this;
   }
 
-  inline void skipSubTree() {
+  void skipSubTree() {
     InternalItr.skipToParent();
 
     while (!InternalItr.atEnd() &&
@@ -802,6 +808,24 @@ public:
   }
 };
 
+/// Generic iterator that wraps a T::TreeTy::iterator and exposes
+/// iterator::getValue() on dereference.
+template <typename T>
+struct ImutAVLValueIterator
+    : iterator_adaptor_base<
+          ImutAVLValueIterator<T>, typename T::TreeTy::iterator,
+          typename std::iterator_traits<
+              typename T::TreeTy::iterator>::iterator_category,
+          const typename T::value_type> {
+  ImutAVLValueIterator() = default;
+  explicit ImutAVLValueIterator(typename T::TreeTy *Tree)
+      : ImutAVLValueIterator::iterator_adaptor_base(Tree) {}
+
+  typename ImutAVLValueIterator::reference operator*() const {
+    return this->I->getValue();
+  }
+};
+
 //===----------------------------------------------------------------------===//
 // Trait classes for Profile information.
 //===----------------------------------------------------------------------===//
@@ -814,7 +838,7 @@ struct ImutProfileInfo {
   typedef const T  value_type;
   typedef const T& value_type_ref;
 
-  static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) {
+  static void Profile(FoldingSetNodeID &ID, value_type_ref X) {
     FoldingSetTrait<T>::Profile(X,ID);
   }
 };
@@ -825,7 +849,7 @@ struct ImutProfileInteger {
   typedef const T  value_type;
   typedef const T& value_type_ref;
 
-  static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) {
+  static void Profile(FoldingSetNodeID &ID, value_type_ref X) {
     ID.AddInteger(X);
   }
 };
@@ -852,7 +876,7 @@ struct ImutProfileInfo<bool> {
   typedef const bool  value_type;
   typedef const bool& value_type_ref;
 
-  static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) {
+  static void Profile(FoldingSetNodeID &ID, value_type_ref X) {
     ID.AddBoolean(X);
   }
 };
@@ -865,7 +889,7 @@ struct ImutProfileInfo<T*> {
   typedef const T*   value_type;
   typedef value_type value_type_ref;
 
-  static inline void Profile(FoldingSetNodeID &ID, value_type_ref X) {
+  static void Profile(FoldingSetNodeID &ID, value_type_ref X) {
     ID.AddPointer(X);
   }
 };
@@ -890,18 +914,18 @@ struct ImutContainerInfo : public ImutProfileInfo<T> {
   typedef bool            data_type;
   typedef bool            data_type_ref;
 
-  static inline key_type_ref KeyOfValue(value_type_ref D) { return D; }
-  static inline data_type_ref DataOfValue(value_type_ref) { return true; }
+  static key_type_ref KeyOfValue(value_type_ref D) { return D; }
+  static data_type_ref DataOfValue(value_type_ref) { return true; }
 
-  static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) {
+  static bool isEqual(key_type_ref LHS, key_type_ref RHS) {
     return std::equal_to<key_type>()(LHS,RHS);
   }
 
-  static inline bool isLess(key_type_ref LHS, key_type_ref RHS) {
+  static bool isLess(key_type_ref LHS, key_type_ref RHS) {
     return std::less<key_type>()(LHS,RHS);
   }
 
-  static inline bool isDataEqual(data_type_ref,data_type_ref) { return true; }
+  static bool isDataEqual(data_type_ref, data_type_ref) { return true; }
 };
 
 /// ImutContainerInfo - Specialization for pointer values to treat pointers
@@ -916,18 +940,14 @@ struct ImutContainerInfo<T*> : public ImutProfileInfo<T*> {
   typedef bool            data_type;
   typedef bool            data_type_ref;
 
-  static inline key_type_ref KeyOfValue(value_type_ref D) { return D; }
-  static inline data_type_ref DataOfValue(value_type_ref) { return true; }
+  static key_type_ref KeyOfValue(value_type_ref D) { return D; }
+  static data_type_ref DataOfValue(value_type_ref) { return true; }
 
-  static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) {
-    return LHS == RHS;
-  }
+  static bool isEqual(key_type_ref LHS, key_type_ref RHS) { return LHS == RHS; }
 
-  static inline bool isLess(key_type_ref LHS, key_type_ref RHS) {
-    return LHS < RHS;
-  }
+  static bool isLess(key_type_ref LHS, key_type_ref RHS) { return LHS < RHS; }
 
-  static inline bool isDataEqual(data_type_ref,data_type_ref) { return true; }
+  static bool isDataEqual(data_type_ref, data_type_ref) { return true; }
 };
 
 //===----------------------------------------------------------------------===//
@@ -1059,31 +1079,7 @@ public:
   // Iterators.
   //===--------------------------------------------------===//
 
-  class iterator {
-    typename TreeTy::iterator itr;
-
-    iterator() {}
-    iterator(TreeTy* t) : itr(t) {}
-    friend class ImmutableSet<ValT,ValInfo>;
-
-  public:
-    typedef ptrdiff_t difference_type;
-    typedef typename ImmutableSet<ValT,ValInfo>::value_type value_type;
-    typedef typename ImmutableSet<ValT,ValInfo>::value_type_ref reference;
-    typedef typename iterator::value_type *pointer;
-    typedef std::bidirectional_iterator_tag iterator_category;
-
-    typename iterator::reference operator*() const { return itr->getValue(); }
-    typename iterator::pointer   operator->() const { return &(operator*()); }
-
-    iterator& operator++() { ++itr; return *this; }
-    iterator  operator++(int) { iterator tmp(*this); ++itr; return tmp; }
-    iterator& operator--() { --itr; return *this; }
-    iterator  operator--(int) { iterator tmp(*this); --itr; return tmp; }
-
-    bool operator==(const iterator& RHS) const { return RHS.itr == itr; }
-    bool operator!=(const iterator& RHS) const { return RHS.itr != itr; }
-  };
+  typedef ImutAVLValueIterator<ImmutableSet> iterator;
 
   iterator begin() const { return iterator(Root); }
   iterator end() const { return iterator(); }
@@ -1094,13 +1090,11 @@ public:
 
   unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
 
-  static inline void Profile(FoldingSetNodeID& ID, const ImmutableSet& S) {
+  static void Profile(FoldingSetNodeID &ID, const ImmutableSet &S) {
     ID.AddPointer(S.Root);
   }
 
-  inline void Profile(FoldingSetNodeID& ID) const {
-    return Profile(ID,*this);
-  }
+  void Profile(FoldingSetNodeID &ID) const { return Profile(ID, *this); }
 
   //===--------------------------------------------------===//
   // For testing.
@@ -1150,7 +1144,7 @@ public:
     if (Root) { Root->release(); }
   }
 
-  static inline ImmutableSetRef getEmptySet(FactoryTy *F) {
+  static ImmutableSetRef getEmptySet(FactoryTy *F) {
     return ImmutableSetRef(0, F);
   }
 
@@ -1195,21 +1189,7 @@ public:
   // Iterators.
   //===--------------------------------------------------===//
 
-  class iterator {
-    typename TreeTy::iterator itr;
-    iterator(TreeTy* t) : itr(t) {}
-    friend class ImmutableSetRef<ValT,ValInfo>;
-  public:
-    iterator() {}
-    inline value_type_ref operator*() const { return itr->getValue(); }
-    inline iterator& operator++() { ++itr; return *this; }
-    inline iterator  operator++(int) { iterator tmp(*this); ++itr; return tmp; }
-    inline iterator& operator--() { --itr; return *this; }
-    inline iterator  operator--(int) { iterator tmp(*this); --itr; return tmp; }
-    inline bool operator==(const iterator& RHS) const { return RHS.itr == itr; }
-    inline bool operator!=(const iterator& RHS) const { return RHS.itr != itr; }
-    inline value_type *operator->() const { return &(operator*()); }
-  };
+  typedef ImutAVLValueIterator<ImmutableSetRef> iterator;
 
   iterator begin() const { return iterator(Root); }
   iterator end() const { return iterator(); }
@@ -1220,13 +1200,11 @@ public:
 
   unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
 
-  static inline void Profile(FoldingSetNodeID& ID, const ImmutableSetRef& S) {
+  static void Profile(FoldingSetNodeID &ID, const ImmutableSetRef &S) {
     ID.AddPointer(S.Root);
   }
 
-  inline void Profile(FoldingSetNodeID& ID) const {
-    return Profile(ID,*this);
-  }
+  void Profile(FoldingSetNodeID &ID) const { return Profile(ID, *this); }
 
   //===--------------------------------------------------===//
   // For testing.
diff --git a/include/llvm/ADT/IndexedMap.h b/include/llvm/ADT/IndexedMap.h
index 2ffb505..5ba85c0 100644
--- a/include/llvm/ADT/IndexedMap.h
+++ b/include/llvm/ADT/IndexedMap.h
@@ -21,16 +21,19 @@
 #define LLVM_ADT_INDEXEDMAP_H
 
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallVector.h"
 #include <cassert>
 #include <functional>
-#include <vector>
 
 namespace llvm {
 
 template <typename T, typename ToIndexT = llvm::identity<unsigned> >
   class IndexedMap {
     typedef typename ToIndexT::argument_type IndexT;
-    typedef std::vector<T> StorageT;
+    // Prefer SmallVector with zero inline storage over std::vector. IndexedMaps
+    // can grow very large and SmallVector grows more efficiently as long as T
+    // is trivially copyable.
+    typedef SmallVector<T, 0> StorageT;
     StorageT storage_;
     T nullVal_;
     ToIndexT toIndex_;
diff --git a/include/llvm/ADT/IntervalMap.h b/include/llvm/ADT/IntervalMap.h
index 99be38f..f8843b2 100644
--- a/include/llvm/ADT/IntervalMap.h
+++ b/include/llvm/ADT/IntervalMap.h
@@ -101,6 +101,7 @@
 
 #include "llvm/ADT/PointerIntPair.h"
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/Support/AlignOf.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/RecyclingAllocator.h"
 #include <iterator>
@@ -953,11 +954,6 @@ class IntervalMap {
     RootBranch node;
   };
 
-  enum {
-    RootDataSize = sizeof(RootBranchData) > sizeof(RootLeaf) ?
-                   sizeof(RootBranchData) : sizeof(RootLeaf)
-  };
-
 public:
   typedef typename Sizer::Allocator Allocator;
   typedef KeyT KeyType;
@@ -966,13 +962,7 @@ public:
 
 private:
   // The root data is either a RootLeaf or a RootBranchData instance.
-  // We can't put them in a union since C++03 doesn't allow non-trivial
-  // constructors in unions.
-  // Instead, we use a char array with pointer alignment. The alignment is
-  // ensured by the allocator member in the class, but still verified in the
-  // constructor. We don't support keys or values that are more aligned than a
-  // pointer.
-  char data[RootDataSize];
+  AlignedCharArrayUnion<RootLeaf, RootBranchData> data;
 
   // Tree height.
   // 0: Leaves in root.
@@ -993,7 +983,7 @@ private:
       const char *d;
       T *t;
     } u;
-    u.d = data;
+    u.d = data.buffer;
     return *u.t;
   }
 
@@ -1051,7 +1041,7 @@ private:
 
 public:
   explicit IntervalMap(Allocator &a) : height(0), rootSize(0), allocator(a) {
-    assert((uintptr_t(data) & (alignOf<RootLeaf>() - 1)) == 0 &&
+    assert((uintptr_t(data.buffer) & (alignOf<RootLeaf>() - 1)) == 0 &&
            "Insufficient alignment");
     new(&rootLeaf()) RootLeaf();
   }
diff --git a/include/llvm/ADT/IntrusiveRefCntPtr.h b/include/llvm/ADT/IntrusiveRefCntPtr.h
index 9b12d04..65b2da7 100644
--- a/include/llvm/ADT/IntrusiveRefCntPtr.h
+++ b/include/llvm/ADT/IntrusiveRefCntPtr.h
@@ -21,10 +21,9 @@
 #ifndef LLVM_ADT_INTRUSIVEREFCNTPTR_H
 #define LLVM_ADT_INTRUSIVEREFCNTPTR_H
 
-#include "llvm/Support/Casting.h"
-#include "llvm/Support/Compiler.h"
 #include <atomic>
-#include <memory>
+#include <cassert>
+#include <cstddef>
 
 namespace llvm {
 
@@ -268,6 +267,8 @@ public:
 // LLVM-style downcasting support for IntrusiveRefCntPtr objects
 //===----------------------------------------------------------------------===//
 
+  template <typename From> struct simplify_type;
+
   template<class T> struct simplify_type<IntrusiveRefCntPtr<T> > {
     typedef T* SimpleType;
     static SimpleType getSimplifiedValue(IntrusiveRefCntPtr<T>& Val) {
diff --git a/include/llvm/ADT/MapVector.h b/include/llvm/ADT/MapVector.h
index 1331b15..f19a50b 100644
--- a/include/llvm/ADT/MapVector.h
+++ b/include/llvm/ADT/MapVector.h
@@ -67,6 +67,11 @@ public:
     Vector.clear();
   }
 
+  void swap(MapVector &RHS) {
+    std::swap(Map, RHS.Map);
+    std::swap(Vector, RHS.Vector);
+  }
+
   ValueT &operator[](const KeyT &Key) {
     std::pair<KeyT, unsigned> Pair = std::make_pair(Key, 0);
     std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
diff --git a/include/llvm/ADT/PostOrderIterator.h b/include/llvm/ADT/PostOrderIterator.h
index dfadc3b..fa337e9 100644
--- a/include/llvm/ADT/PostOrderIterator.h
+++ b/include/llvm/ADT/PostOrderIterator.h
@@ -111,53 +111,52 @@ class po_iterator : public std::iterator<std::forward_iterator_tag,
     }
   }
 
-  inline po_iterator(NodeType *BB) {
+  po_iterator(NodeType *BB) {
     this->insertEdge((NodeType*)nullptr, BB);
     VisitStack.push_back(std::make_pair(BB, GT::child_begin(BB)));
     traverseChild();
   }
-  inline po_iterator() {} // End is when stack is empty.
+  po_iterator() {} // End is when stack is empty.
 
-  inline po_iterator(NodeType *BB, SetType &S) :
-    po_iterator_storage<SetType, ExtStorage>(S) {
+  po_iterator(NodeType *BB, SetType &S)
+      : po_iterator_storage<SetType, ExtStorage>(S) {
     if (this->insertEdge((NodeType*)nullptr, BB)) {
       VisitStack.push_back(std::make_pair(BB, GT::child_begin(BB)));
       traverseChild();
     }
   }
 
-  inline po_iterator(SetType &S) :
-      po_iterator_storage<SetType, ExtStorage>(S) {
+  po_iterator(SetType &S)
+      : po_iterator_storage<SetType, ExtStorage>(S) {
   } // End is when stack is empty.
 public:
   typedef typename super::pointer pointer;
-  typedef po_iterator<GraphT, SetType, ExtStorage, GT> _Self;
 
   // Provide static "constructors"...
-  static inline _Self begin(GraphT G) { return _Self(GT::getEntryNode(G)); }
-  static inline _Self end  (GraphT G) { return _Self(); }
+  static po_iterator begin(GraphT G) {
+    return po_iterator(GT::getEntryNode(G));
+  }
+  static po_iterator end(GraphT G) { return po_iterator(); }
 
-  static inline _Self begin(GraphT G, SetType &S) {
-    return _Self(GT::getEntryNode(G), S);
+  static po_iterator begin(GraphT G, SetType &S) {
+    return po_iterator(GT::getEntryNode(G), S);
   }
-  static inline _Self end  (GraphT G, SetType &S) { return _Self(S); }
+  static po_iterator end(GraphT G, SetType &S) { return po_iterator(S); }
 
-  inline bool operator==(const _Self& x) const {
+  bool operator==(const po_iterator &x) const {
     return VisitStack == x.VisitStack;
   }
-  inline bool operator!=(const _Self& x) const { return !operator==(x); }
+  bool operator!=(const po_iterator &x) const { return !(*this == x); }
 
-  inline pointer operator*() const {
-    return VisitStack.back().first;
-  }
+  pointer operator*() const { return VisitStack.back().first; }
 
   // This is a nonstandard operator-> that dereferences the pointer an extra
   // time... so that you can actually call methods ON the BasicBlock, because
   // the contained type is a pointer.  This allows BBIt->getTerminator() f.e.
   //
-  inline NodeType *operator->() const { return operator*(); }
+  NodeType *operator->() const { return **this; }
 
-  inline _Self& operator++() {   // Preincrement
+  po_iterator &operator++() { // Preincrement
     this->finishPostorder(VisitStack.back().first);
     VisitStack.pop_back();
     if (!VisitStack.empty())
@@ -165,8 +164,10 @@ public:
     return *this;
   }
 
-  inline _Self operator++(int) { // Postincrement
-    _Self tmp = *this; ++*this; return tmp;
+  po_iterator operator++(int) { // Postincrement
+    po_iterator tmp = *this;
+    ++*this;
+    return tmp;
   }
 };
 
@@ -260,19 +261,17 @@ template<class GraphT, class GT = GraphTraits<GraphT> >
 class ReversePostOrderTraversal {
   typedef typename GT::NodeType NodeType;
   std::vector<NodeType*> Blocks;       // Block list in normal PO order
-  inline void Initialize(NodeType *BB) {
+  void Initialize(NodeType *BB) {
     std::copy(po_begin(BB), po_end(BB), std::back_inserter(Blocks));
   }
 public:
   typedef typename std::vector<NodeType*>::reverse_iterator rpo_iterator;
 
-  inline ReversePostOrderTraversal(GraphT G) {
-    Initialize(GT::getEntryNode(G));
-  }
+  ReversePostOrderTraversal(GraphT G) { Initialize(GT::getEntryNode(G)); }
 
   // Because we want a reverse post order, use reverse iterators from the vector
-  inline rpo_iterator begin() { return Blocks.rbegin(); }
-  inline rpo_iterator end()   { return Blocks.rend(); }
+  rpo_iterator begin() { return Blocks.rbegin(); }
+  rpo_iterator end() { return Blocks.rend(); }
 };
 
 } // End llvm namespace
diff --git a/include/llvm/ADT/STLExtras.h b/include/llvm/ADT/STLExtras.h
index 57af18e..921bd82 100644
--- a/include/llvm/ADT/STLExtras.h
+++ b/include/llvm/ADT/STLExtras.h
@@ -123,7 +123,6 @@ public:
   typedef void reference;        // Can't modify value returned by fn
 
   typedef RootIt iterator_type;
-  typedef mapped_iterator<RootIt, UnaryFunc> _Self;
 
   inline const RootIt &getCurrent() const { return current; }
   inline const UnaryFunc &getFunc() const { return Fn; }
@@ -135,34 +134,56 @@ public:
     return Fn(*current);         // little change
   }
 
-  _Self& operator++() { ++current; return *this; }
-  _Self& operator--() { --current; return *this; }
-  _Self  operator++(int) { _Self __tmp = *this; ++current; return __tmp; }
-  _Self  operator--(int) { _Self __tmp = *this; --current; return __tmp; }
-  _Self  operator+    (difference_type n) const {
-    return _Self(current + n, Fn);
+  mapped_iterator &operator++() {
+    ++current;
+    return *this;
   }
-  _Self& operator+=   (difference_type n) { current += n; return *this; }
-  _Self  operator-    (difference_type n) const {
-    return _Self(current - n, Fn);
+  mapped_iterator &operator--() {
+    --current;
+    return *this;
+  }
+  mapped_iterator operator++(int) {
+    mapped_iterator __tmp = *this;
+    ++current;
+    return __tmp;
+  }
+  mapped_iterator operator--(int) {
+    mapped_iterator __tmp = *this;
+    --current;
+    return __tmp;
+  }
+  mapped_iterator operator+(difference_type n) const {
+    return mapped_iterator(current + n, Fn);
+  }
+  mapped_iterator &operator+=(difference_type n) {
+    current += n;
+    return *this;
+  }
+  mapped_iterator operator-(difference_type n) const {
+    return mapped_iterator(current - n, Fn);
+  }
+  mapped_iterator &operator-=(difference_type n) {
+    current -= n;
+    return *this;
   }
-  _Self& operator-=   (difference_type n) { current -= n; return *this; }
   reference operator[](difference_type n) const { return *(*this + n); }
 
-  inline bool operator!=(const _Self &X) const { return !operator==(X); }
-  inline bool operator==(const _Self &X) const { return current == X.current; }
-  inline bool operator< (const _Self &X) const { return current <  X.current; }
+  bool operator!=(const mapped_iterator &X) const { return !operator==(X); }
+  bool operator==(const mapped_iterator &X) const {
+    return current == X.current;
+  }
+  bool operator<(const mapped_iterator &X) const { return current < X.current; }
 
-  inline difference_type operator-(const _Self &X) const {
+  difference_type operator-(const mapped_iterator &X) const {
     return current - X.current;
   }
 };
 
-template <class _Iterator, class Func>
-inline mapped_iterator<_Iterator, Func>
-operator+(typename mapped_iterator<_Iterator, Func>::difference_type N,
-          const mapped_iterator<_Iterator, Func>& X) {
-  return mapped_iterator<_Iterator, Func>(X.getCurrent() - N, X.getFunc());
+template <class Iterator, class Func>
+inline mapped_iterator<Iterator, Func>
+operator+(typename mapped_iterator<Iterator, Func>::difference_type N,
+          const mapped_iterator<Iterator, Func> &X) {
+  return mapped_iterator<Iterator, Func>(X.getCurrent() - N, X.getFunc());
 }
 
 
@@ -263,10 +284,11 @@ inline int (*get_array_pod_sort_comparator(const T &))
 /// default to std::less.
 template<class IteratorTy>
 inline void array_pod_sort(IteratorTy Start, IteratorTy End) {
-  // Don't dereference start iterator of empty sequence.
-  if (Start == End) return;
-  qsort(&*Start, End-Start, sizeof(*Start),
-        get_array_pod_sort_comparator(*Start));
+  // Don't inefficiently call qsort with one element or trigger undefined
+  // behavior with an empty sequence.
+  auto NElts = End - Start;
+  if (NElts <= 1) return;
+  qsort(&*Start, NElts, sizeof(*Start), get_array_pod_sort_comparator(*Start));
 }
 
 template <class IteratorTy>
@@ -275,9 +297,11 @@ inline void array_pod_sort(
     int (*Compare)(
         const typename std::iterator_traits<IteratorTy>::value_type *,
         const typename std::iterator_traits<IteratorTy>::value_type *)) {
-  // Don't dereference start iterator of empty sequence.
-  if (Start == End) return;
-  qsort(&*Start, End - Start, sizeof(*Start),
+  // Don't inefficiently call qsort with one element or trigger undefined
+  // behavior with an empty sequence.
+  auto NElts = End - Start;
+  if (NElts <= 1) return;
+  qsort(&*Start, NElts, sizeof(*Start),
         reinterpret_cast<int (*)(const void *, const void *)>(Compare));
 }
 
diff --git a/include/llvm/ADT/SmallBitVector.h b/include/llvm/ADT/SmallBitVector.h
index 22e8ccd..ae3d645 100644
--- a/include/llvm/ADT/SmallBitVector.h
+++ b/include/llvm/ADT/SmallBitVector.h
@@ -66,6 +66,8 @@ public:
   public:
     reference(SmallBitVector &b, unsigned Idx) : TheVector(b), BitPos(Idx) {}
 
+    reference(const reference&) = default;
+
     reference& operator=(reference t) {
       *this = bool(t);
       return *this;
diff --git a/include/llvm/ADT/SmallVector.h b/include/llvm/ADT/SmallVector.h
index 14e2c7b..5b208b7 100644
--- a/include/llvm/ADT/SmallVector.h
+++ b/include/llvm/ADT/SmallVector.h
@@ -24,6 +24,7 @@
 #include <cstddef>
 #include <cstdlib>
 #include <cstring>
+#include <initializer_list>
 #include <iterator>
 #include <memory>
 
@@ -432,6 +433,10 @@ public:
     this->setEnd(this->end() + NumInputs);
   }
 
+  void append(std::initializer_list<T> IL) {
+    append(IL.begin(), IL.end());
+  }
+
   void assign(size_type NumElts, const T &Elt) {
     clear();
     if (this->capacity() < NumElts)
@@ -440,6 +445,11 @@ public:
     std::uninitialized_fill(this->begin(), this->end(), Elt);
   }
 
+  void assign(std::initializer_list<T> IL) {
+    clear();
+    append(IL);
+  }
+
   iterator erase(iterator I) {
     assert(I >= this->begin() && "Iterator to erase is out of bounds.");
     assert(I < this->end() && "Erasing at past-the-end iterator.");
@@ -633,6 +643,10 @@ public:
     return I;
   }
 
+  void insert(iterator I, std::initializer_list<T> IL) {
+    insert(I, IL.begin(), IL.end());
+  }
+
   template <typename... ArgTypes> void emplace_back(ArgTypes &&... Args) {
     if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
       this->grow();
@@ -865,6 +879,10 @@ public:
     this->append(R.begin(), R.end());
   }
 
+  SmallVector(std::initializer_list<T> IL) : SmallVectorImpl<T>(N) {
+    this->assign(IL);
+  }
+
   SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(N) {
     if (!RHS.empty())
       SmallVectorImpl<T>::operator=(RHS);
@@ -895,6 +913,10 @@ public:
     return *this;
   }
 
+  const SmallVector &operator=(std::initializer_list<T> IL) {
+    this->assign(IL);
+    return *this;
+  }
 };
 
 template<typename T, unsigned N>
diff --git a/include/llvm/ADT/StringRef.h b/include/llvm/ADT/StringRef.h
index 6111c42..95660a4 100644
--- a/include/llvm/ADT/StringRef.h
+++ b/include/llvm/ADT/StringRef.h
@@ -238,9 +238,12 @@ namespace llvm {
     /// \returns The index of the first occurrence of \p C, or npos if not
     /// found.
     size_t find(char C, size_t From = 0) const {
-      for (size_t i = std::min(From, Length), e = Length; i != e; ++i)
-        if (Data[i] == C)
-          return i;
+      size_t FindBegin = std::min(From, Length);
+      if (FindBegin < Length) { // Avoid calling memchr with nullptr.
+        // Just forward to memchr, which is faster than a hand-rolled loop.
+        if (const void *P = ::memchr(Data + FindBegin, C, Length - FindBegin))
+          return static_cast<const char *>(P) - Data;
+      }
       return npos;
     }
 
diff --git a/include/llvm/ADT/Triple.h b/include/llvm/ADT/Triple.h
index 886f6fb..5fda775 100644
--- a/include/llvm/ADT/Triple.h
+++ b/include/llvm/ADT/Triple.h
@@ -86,6 +86,7 @@ public:
   enum SubArchType {
     NoSubArch,
 
+    ARMSubArch_v8_1a,
     ARMSubArch_v8,
     ARMSubArch_v7,
     ARMSubArch_v7em,
@@ -93,6 +94,7 @@ public:
     ARMSubArch_v7s,
     ARMSubArch_v6,
     ARMSubArch_v6m,
+    ARMSubArch_v6k,
     ARMSubArch_v6t2,
     ARMSubArch_v5,
     ARMSubArch_v5te,
@@ -120,6 +122,7 @@ public:
   enum OSType {
     UnknownOS,
 
+    CloudABI,
     Darwin,
     DragonFly,
     FreeBSD,
diff --git a/include/llvm/ADT/Twine.h b/include/llvm/ADT/Twine.h
index 9e9a4e1..51bb18d 100644
--- a/include/llvm/ADT/Twine.h
+++ b/include/llvm/ADT/Twine.h
@@ -10,6 +10,7 @@
 #ifndef LLVM_ADT_TWINE_H
 #define LLVM_ADT_TWINE_H
 
+#include "llvm/ADT/SmallVector.h"

 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/DataTypes.h"
 #include "llvm/Support/ErrorHandling.h"
@@ -17,9 +18,6 @@
 #include <string>
 
 namespace llvm {
-  template <typename T>
-  class SmallVectorImpl;
-  class StringRef;
   class raw_ostream;
 
   /// Twine - A lightweight data structure for efficiently representing the
@@ -100,6 +98,9 @@ namespace llvm {
       /// A pointer to a StringRef instance.
       StringRefKind,
 
+      /// A pointer to a SmallString instance.
+      SmallStringKind,
+
       /// A char value reinterpreted as a pointer, to render as a character.
       CharKind,
 
@@ -136,6 +137,7 @@ namespace llvm {
       const char *cString;
       const std::string *stdString;
       const StringRef *stringRef;
+      const SmallVectorImpl<char> *smallString;

       char character;
       unsigned int decUI;
       int decI;
@@ -166,17 +168,16 @@ namespace llvm {
     }
 
     /// Construct a binary twine.
-    explicit Twine(const Twine &_LHS, const Twine &_RHS)
-      : LHSKind(TwineKind), RHSKind(TwineKind) {
-      LHS.twine = &_LHS;
-      RHS.twine = &_RHS;
+    explicit Twine(const Twine &LHS, const Twine &RHS)
+        : LHSKind(TwineKind), RHSKind(TwineKind) {
+      this->LHS.twine = &LHS;
+      this->RHS.twine = &RHS;
       assert(isValid() && "Invalid twine!");
     }
 
     /// Construct a twine from explicit values.
-    explicit Twine(Child _LHS, NodeKind _LHSKind,
-                   Child _RHS, NodeKind _RHSKind)
-      : LHS(_LHS), RHS(_RHS), LHSKind(_LHSKind), RHSKind(_RHSKind) {
+    explicit Twine(Child LHS, NodeKind LHSKind, Child RHS, NodeKind RHSKind)
+        : LHS(LHS), RHS(RHS), LHSKind(LHSKind), RHSKind(RHSKind) {
       assert(isValid() && "Invalid twine!");
     }
 
@@ -184,32 +185,32 @@ namespace llvm {
     /// when concatenating might cause undefined behavior or stack corruptions
     Twine &operator=(const Twine &Other) = delete;
 
-    /// isNull - Check for the null twine.
+    /// Check for the null twine.
     bool isNull() const {
       return getLHSKind() == NullKind;
     }
 
-    /// isEmpty - Check for the empty twine.
+    /// Check for the empty twine.
     bool isEmpty() const {
       return getLHSKind() == EmptyKind;
     }
 
-    /// isNullary - Check if this is a nullary twine (null or empty).
+    /// Check if this is a nullary twine (null or empty).
     bool isNullary() const {
       return isNull() || isEmpty();
     }
 
-    /// isUnary - Check if this is a unary twine.
+    /// Check if this is a unary twine.
     bool isUnary() const {
       return getRHSKind() == EmptyKind && !isNullary();
     }
 
-    /// isBinary - Check if this is a binary twine.
+    /// Check if this is a binary twine.
     bool isBinary() const {
       return getLHSKind() != NullKind && getRHSKind() != EmptyKind;
     }
 
-    /// isValid - Check if this is a valid twine (satisfying the invariants on
+    /// Check if this is a valid twine (satisfying the invariants on
     /// order and number of arguments).
     bool isValid() const {
       // Nullary twines always have Empty on the RHS.
@@ -235,16 +236,16 @@ namespace llvm {
       return true;
     }
 
-    /// getLHSKind - Get the NodeKind of the left-hand side.
+    /// Get the NodeKind of the left-hand side.
     NodeKind getLHSKind() const { return LHSKind; }
 
-    /// getRHSKind - Get the NodeKind of the right-hand side.
+    /// Get the NodeKind of the right-hand side.
     NodeKind getRHSKind() const { return RHSKind; }
 
-    /// printOneChild - Print one child from a twine.
+    /// Print one child from a twine.
     void printOneChild(raw_ostream &OS, Child Ptr, NodeKind Kind) const;
 
-    /// printOneChildRepr - Print the representation of one child from a twine.
+    /// Print the representation of one child from a twine.
     void printOneChildRepr(raw_ostream &OS, Child Ptr,
                            NodeKind Kind) const;
 
@@ -257,6 +258,8 @@ namespace llvm {
       assert(isValid() && "Invalid twine!");
     }
 
+    Twine(const Twine &) = default;
+
     /// Construct from a C string.
     ///
     /// We take care here to optimize "" into the empty twine -- this will be
@@ -287,6 +290,13 @@ namespace llvm {
       assert(isValid() && "Invalid twine!");
     }
 
+    /// Construct from a SmallString.
+    /*implicit*/ Twine(const SmallVectorImpl<char> &Str)
+      : LHSKind(SmallStringKind), RHSKind(EmptyKind) {
+      LHS.smallString = &Str;
+      assert(isValid() && "Invalid twine!");
+    }
+
     /// Construct from a char.
     explicit Twine(char Val)
       : LHSKind(CharKind), RHSKind(EmptyKind) {
@@ -347,18 +357,18 @@ namespace llvm {
     // right thing. Yet.
 
     /// Construct as the concatenation of a C string and a StringRef.
-    /*implicit*/ Twine(const char *_LHS, const StringRef &_RHS)
-      : LHSKind(CStringKind), RHSKind(StringRefKind) {
-      LHS.cString = _LHS;
-      RHS.stringRef = &_RHS;
+    /*implicit*/ Twine(const char *LHS, const StringRef &RHS)
+        : LHSKind(CStringKind), RHSKind(StringRefKind) {
+      this->LHS.cString = LHS;
+      this->RHS.stringRef = &RHS;
       assert(isValid() && "Invalid twine!");
     }
 
     /// Construct as the concatenation of a StringRef and a C string.
-    /*implicit*/ Twine(const StringRef &_LHS, const char *_RHS)
-      : LHSKind(StringRefKind), RHSKind(CStringKind) {
-      LHS.stringRef = &_LHS;
-      RHS.cString = _RHS;
+    /*implicit*/ Twine(const StringRef &LHS, const char *RHS)
+        : LHSKind(StringRefKind), RHSKind(CStringKind) {
+      this->LHS.stringRef = &LHS;
+      this->RHS.cString = RHS;
       assert(isValid() && "Invalid twine!");
     }
 
@@ -384,14 +394,14 @@ namespace llvm {
     /// @name Predicate Operations
     /// @{
 
-    /// isTriviallyEmpty - Check if this twine is trivially empty; a false
-    /// return value does not necessarily mean the twine is empty.
+    /// Check if this twine is trivially empty; a false return value does not
+    /// necessarily mean the twine is empty.
     bool isTriviallyEmpty() const {
       return isNullary();
     }
 
-    /// isSingleStringRef - Return true if this twine can be dynamically
-    /// accessed as a single StringRef value with getSingleStringRef().
+    /// Return true if this twine can be dynamically accessed as a single
+    /// StringRef value with getSingleStringRef().
     bool isSingleStringRef() const {
       if (getRHSKind() != EmptyKind) return false;
 
@@ -400,6 +410,7 @@ namespace llvm {
       case CStringKind:
       case StdStringKind:
       case StringRefKind:
+      case SmallStringKind:

         return true;
       default:
         return false;
@@ -416,15 +427,14 @@ namespace llvm {
     /// @name Output & Conversion.
     /// @{
 
-    /// str - Return the twine contents as a std::string.
+    /// Return the twine contents as a std::string.
     std::string str() const;
 
-    /// toVector - Write the concatenated string into the given SmallString or
-    /// SmallVector.
+    /// Write the concatenated string into the given SmallString or SmallVector.
     void toVector(SmallVectorImpl<char> &Out) const;
 
-    /// getSingleStringRef - This returns the twine as a single StringRef.  This
-    /// method is only valid if isSingleStringRef() is true.
+    /// This returns the twine as a single StringRef.  This method is only valid
+    /// if isSingleStringRef() is true.
     StringRef getSingleStringRef() const {
       assert(isSingleStringRef() &&"This cannot be had as a single stringref!");
       switch (getLHSKind()) {
@@ -433,18 +443,24 @@ namespace llvm {
       case CStringKind:    return StringRef(LHS.cString);
       case StdStringKind:  return StringRef(*LHS.stdString);
       case StringRefKind:  return *LHS.stringRef;
+      case SmallStringKind:
+        return StringRef(LHS.smallString->data(), LHS.smallString->size());
       }
     }
 
-    /// toStringRef - This returns the twine as a single StringRef if it can be
+    /// This returns the twine as a single StringRef if it can be
     /// represented as such. Otherwise the twine is written into the given
     /// SmallVector and a StringRef to the SmallVector's data is returned.
-    StringRef toStringRef(SmallVectorImpl<char> &Out) const;
+    StringRef toStringRef(SmallVectorImpl<char> &Out) const {
+      if (isSingleStringRef())
+        return getSingleStringRef();
+      toVector(Out);
+      return StringRef(Out.data(), Out.size());
+    }
 
-    /// toNullTerminatedStringRef - This returns the twine as a single null
-    /// terminated StringRef if it can be represented as such. Otherwise the
-    /// twine is written into the given SmallVector and a StringRef to the
-    /// SmallVector's data is returned.
+    /// This returns the twine as a single null terminated StringRef if it
+    /// can be represented as such. Otherwise the twine is written into the
+    /// given SmallVector and a StringRef to the SmallVector's data is returned.
     ///
     /// The returned StringRef's size does not include the null terminator.
     StringRef toNullTerminatedStringRef(SmallVectorImpl<char> &Out) const;