Update aosp/master LLVM for rebase to r222494.

Change-Id: Ic787f5e0124df789bd26f3f24680f45e678eef2d

32 files changed, 543 insertions, 242 deletions

diff --git a/include/llvm/ADT/APFloat.h b/include/llvm/ADT/APFloat.h
index 50f1463..26aae77 100644
--- a/include/llvm/ADT/APFloat.h
+++ b/include/llvm/ADT/APFloat.h
@@ -304,6 +304,38 @@ public:
   /// IEEE-754R 5.3.1: nextUp/nextDown.
   opStatus next(bool nextDown);
 
+  /// \brief Operator+ overload which provides the default
+  /// \c nmNearestTiesToEven rounding mode and *no* error checking.
+  APFloat operator+(const APFloat &RHS) const {
+    APFloat Result = *this;
+    Result.add(RHS, rmNearestTiesToEven);
+    return Result;
+  }
+
+  /// \brief Operator- overload which provides the default
+  /// \c nmNearestTiesToEven rounding mode and *no* error checking.
+  APFloat operator-(const APFloat &RHS) const {
+    APFloat Result = *this;
+    Result.subtract(RHS, rmNearestTiesToEven);
+    return Result;
+  }
+
+  /// \brief Operator* overload which provides the default
+  /// \c nmNearestTiesToEven rounding mode and *no* error checking.
+  APFloat operator*(const APFloat &RHS) const {
+    APFloat Result = *this;
+    Result.multiply(RHS, rmNearestTiesToEven);
+    return Result;
+  }
+
+  /// \brief Operator/ overload which provides the default
+  /// \c nmNearestTiesToEven rounding mode and *no* error checking.
+  APFloat operator/(const APFloat &RHS) const {
+    APFloat Result = *this;
+    Result.divide(RHS, rmNearestTiesToEven);
+    return Result;
+  }
+
   /// @}
 
   /// \name Sign operations.
@@ -313,6 +345,13 @@ public:
   void clearSign();
   void copySign(const APFloat &);
 
+  /// \brief A static helper to produce a copy of an APFloat value with its sign
+  /// copied from some other APFloat.
+  static APFloat copySign(APFloat Value, const APFloat &Sign) {
+    Value.copySign(Sign);
+    return std::move(Value);
+  }
+
   /// @}
 
   /// \name Conversions
@@ -452,6 +491,36 @@ public:
   /// return true.
   bool getExactInverse(APFloat *inv) const;
 
+  /// \brief Enumeration of \c ilogb error results.
+  enum IlogbErrorKinds {
+    IEK_Zero = INT_MIN+1,
+    IEK_NaN = INT_MIN,
+    IEK_Inf = INT_MAX
+  };
+
+  /// \brief Returns the exponent of the internal representation of the APFloat.
+  ///
+  /// Because the radix of APFloat is 2, this is equivalent to floor(log2(x)).
+  /// For special APFloat values, this returns special error codes:
+  ///
+  ///   NaN -> \c IEK_NaN
+  ///   0   -> \c IEK_Zero
+  ///   Inf -> \c IEK_Inf
+  ///
+  friend int ilogb(const APFloat &Arg) {
+    if (Arg.isNaN())
+      return IEK_NaN;
+    if (Arg.isZero())
+      return IEK_Zero;
+    if (Arg.isInfinity())
+      return IEK_Inf;
+
+    return Arg.exponent;
+  }
+
+  /// \brief Returns: X * 2^Exp for integral exponents.
+  friend APFloat scalbn(APFloat X, int Exp);
+
 private:
 
   /// \name Simple Queries
@@ -573,11 +642,41 @@ private:
   unsigned int sign : 1;
 };
 
-/// See friend declaration above.
+/// See friend declarations above.
 ///
-/// This additional declaration is required in order to compile LLVM with IBM
+/// These additional declarations are required in order to compile LLVM with IBM
 /// xlC compiler.
 hash_code hash_value(const APFloat &Arg);
+APFloat scalbn(APFloat X, int Exp);
+
+/// \brief Returns the absolute value of the argument.
+inline APFloat abs(APFloat X) {
+  X.clearSign();
+  return X;
+}
+
+/// Implements IEEE minNum semantics. Returns the smaller of the 2 arguments if
+/// both are not NaN. If either argument is a NaN, returns the other argument.
+LLVM_READONLY
+inline APFloat minnum(const APFloat &A, const APFloat &B) {
+  if (A.isNaN())
+    return B;
+  if (B.isNaN())
+    return A;
+  return (B.compare(A) == APFloat::cmpLessThan) ? B : A;
+}
+
+/// Implements IEEE maxNum semantics. Returns the larger of the 2 arguments if
+/// both are not NaN. If either argument is a NaN, returns the other argument.
+LLVM_READONLY
+inline APFloat maxnum(const APFloat &A, const APFloat &B) {
+  if (A.isNaN())
+    return B;
+  if (B.isNaN())
+    return A;
+  return (A.compare(B) == APFloat::cmpLessThan) ? B : A;
+}
+
 } // namespace llvm
 
 #endif // LLVM_ADT_APFLOAT_H
diff --git a/include/llvm/ADT/APInt.h b/include/llvm/ADT/APInt.h
index aa3c3f6..f4e7e3c 100644
--- a/include/llvm/ADT/APInt.h
+++ b/include/llvm/ADT/APInt.h
@@ -656,13 +656,24 @@ public:
 
   /// @brief Move assignment operator.
   APInt &operator=(APInt &&that) {
-    if (!isSingleWord())
+    if (!isSingleWord()) {
+      // The MSVC STL shipped in 2013 requires that self move assignment be a
+      // no-op.  Otherwise algorithms like stable_sort will produce answers
+      // where half of the output is left in a moved-from state.
+      if (this == &that)
+        return *this;
       delete[] pVal;
+    }
 
-    BitWidth = that.BitWidth;
-    VAL = that.VAL;
+    // Use memcpy so that type based alias analysis sees both VAL and pVal
+    // as modified.
+    memcpy(&VAL, &that.VAL, sizeof(uint64_t));
 
+    // If 'this == &that', avoid zeroing our own bitwidth by storing to 'that'
+    // first.
+    unsigned ThatBitWidth = that.BitWidth;
     that.BitWidth = 0;
+    BitWidth = ThatBitWidth;
 
     return *this;
   }
@@ -936,7 +947,8 @@ public:
   APInt sdiv_ov(const APInt &RHS, bool &Overflow) const;
   APInt smul_ov(const APInt &RHS, bool &Overflow) const;
   APInt umul_ov(const APInt &RHS, bool &Overflow) const;
-  APInt sshl_ov(unsigned Amt, bool &Overflow) const;
+  APInt sshl_ov(const APInt &Amt, bool &Overflow) const;
+  APInt ushl_ov(const APInt &Amt, bool &Overflow) const;
 
   /// \brief Array-indexing support.
   ///
diff --git a/include/llvm/ADT/APSInt.h b/include/llvm/ADT/APSInt.h
index ee34e9b..a6693f7 100644
--- a/include/llvm/ADT/APSInt.h
+++ b/include/llvm/ADT/APSInt.h
@@ -269,19 +269,15 @@ public:
     else if (I2.getBitWidth() > I1.getBitWidth())
       return isSameValue(I1.extend(I2.getBitWidth()), I2);
 
-    // We have a signedness mismatch. Turn the signed value into an unsigned
-    // value.
-    if (I1.isSigned()) {
-      if (I1.isNegative())
-        return false;
+    assert(I1.isSigned() != I2.isSigned());
 
-      return APSInt(I1, true) == I2;
-    }
-
-    if (I2.isNegative())
+    // We have a signedness mismatch. Check for negative values and do an
+    // unsigned compare if signs match.
+    if ((I1.isSigned() && I1.isNegative()) ||
+        (!I1.isSigned() && I2.isNegative()))
       return false;
 
-    return I1 == APSInt(I2, true);
+    return I1.eq(I2);
   }
 
   /// Profile - Used to insert APSInt objects, or objects that contain APSInt
diff --git a/include/llvm/ADT/ArrayRef.h b/include/llvm/ADT/ArrayRef.h
index 0fff505..8c14a42 100644
--- a/include/llvm/ADT/ArrayRef.h
+++ b/include/llvm/ADT/ArrayRef.h
@@ -11,6 +11,7 @@
 #define LLVM_ADT_ARRAYREF_H
 
 #include "llvm/ADT/None.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
 #include <vector>
 
@@ -43,6 +44,19 @@ 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
     /// @{
@@ -90,6 +104,14 @@ namespace llvm {
       Length(Vec.size()) {}
 #endif
 
+    /// Construct an ArrayRef<const T*> from ArrayRef<T*>. This uses SFINAE to
+    /// ensure that only ArrayRefs of pointers can be converted.
+    template <typename U>
+    ArrayRef(const ArrayRef<U *> &A,
+             typename std::enable_if<
+                 std::is_convertible<U *const *, T const *>::value>::type* = 0)
+      : Data(A.data()), Length(A.size()) {}
+
     /// @}
     /// @name Simple Operations
     /// @{
@@ -131,7 +153,13 @@ namespace llvm {
     bool equals(ArrayRef RHS) const {
       if (Length != RHS.Length)
         return false;
-      return std::equal(begin(), end(), RHS.begin());
+      // 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;
     }
 
     /// slice(n) - Chop off the first N elements of the array.
@@ -176,6 +204,47 @@ 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/DenseMap.h b/include/llvm/ADT/DenseMap.h
index 85f37b9..c44b67a 100644
--- a/include/llvm/ADT/DenseMap.h
+++ b/include/llvm/ADT/DenseMap.h
@@ -305,6 +305,7 @@ protected:
 
   template <typename OtherBaseT>
   void copyFrom(const DenseMapBase<OtherBaseT, KeyT, ValueT, KeyInfoT>& other) {
+    assert(&other != this);
     assert(getNumBuckets() == other.getNumBuckets());
 
     setNumEntries(other.getNumEntries());
@@ -574,7 +575,8 @@ public:
   }
 
   DenseMap& operator=(const DenseMap& other) {
-    copyFrom(other);
+    if (&other != this)
+      copyFrom(other);
     return *this;
   }
 
@@ -799,7 +801,8 @@ public:
   }
 
   SmallDenseMap& operator=(const SmallDenseMap& other) {
-    copyFrom(other);
+    if (&other != this)
+      copyFrom(other);
     return *this;
   }
 
diff --git a/include/llvm/ADT/DenseSet.h b/include/llvm/ADT/DenseSet.h
index 37a81b0..9ab1be2 100644
--- a/include/llvm/ADT/DenseSet.h
+++ b/include/llvm/ADT/DenseSet.h
@@ -29,7 +29,7 @@ class DenseSet {
 public:
   typedef ValueT key_type;
   typedef ValueT value_type;
-  typedef unsigned size_type;

+  typedef unsigned size_type;
 
   explicit DenseSet(unsigned NumInitBuckets = 0) : TheMap(NumInitBuckets) {}
 
@@ -45,7 +45,7 @@ public:
     TheMap.clear();
   }
 
-  /// Return 1 if the specified key is in the set, 0 otherwise.

+  /// Return 1 if the specified key is in the set, 0 otherwise.
   size_type count(const ValueT &V) const {
     return TheMap.count(V);
   }
@@ -110,6 +110,21 @@ public:
   const_iterator end() const { return ConstIterator(TheMap.end()); }
 
   iterator find(const ValueT &V) { return Iterator(TheMap.find(V)); }
+
+  /// Alternative version of find() which allows a different, and possibly less
+  /// expensive, key type.
+  /// The DenseMapInfo is responsible for supplying methods
+  /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key type
+  /// used.
+  template <class LookupKeyT>
+  iterator find_as(const LookupKeyT &Val) {
+    return Iterator(TheMap.find_as(Val));
+  }
+  template <class LookupKeyT>
+  const_iterator find_as(const LookupKeyT &Val) const {
+    return ConstIterator(TheMap.find_as(Val));
+  }
+
   void erase(Iterator I) { return TheMap.erase(I.I); }
   void erase(ConstIterator CI) { return TheMap.erase(CI.I); }
 
diff --git a/include/llvm/ADT/DepthFirstIterator.h b/include/llvm/ADT/DepthFirstIterator.h
index dfba43f..0f69146 100644
--- a/include/llvm/ADT/DepthFirstIterator.h
+++ b/include/llvm/ADT/DepthFirstIterator.h
@@ -231,6 +231,13 @@ df_ext_iterator<T, SetTy> df_ext_end(const T& G, SetTy &S) {
   return df_ext_iterator<T, SetTy>::end(G, S);
 }
 
+template <class T, class SetTy>
+iterator_range<df_ext_iterator<T, SetTy>> depth_first_ext(const T& G,
+                                                          SetTy &S) {
+  return iterator_range<df_ext_iterator<T, SetTy>>(df_ext_begin(G, S),
+                                                   df_ext_end(G, S));
+}
+
 
 // Provide global definitions of inverse depth first iterators...
 template <class T,
@@ -276,6 +283,13 @@ idf_ext_iterator<T, SetTy> idf_ext_end(const T& G, SetTy &S) {
   return idf_ext_iterator<T, SetTy>::end(Inverse<T>(G), S);
 }
 
+template <class T, class SetTy>
+iterator_range<idf_ext_iterator<T, SetTy>> inverse_depth_first_ext(const T& G,
+                                                                   SetTy &S) {
+  return iterator_range<idf_ext_iterator<T, SetTy>>(idf_ext_begin(G, S),
+                                                    idf_ext_end(G, S));
+}
+
 } // End llvm namespace
 
 #endif
diff --git a/include/llvm/ADT/IntrusiveRefCntPtr.h b/include/llvm/ADT/IntrusiveRefCntPtr.h
index f9df378..c859c98 100644
--- a/include/llvm/ADT/IntrusiveRefCntPtr.h
+++ b/include/llvm/ADT/IntrusiveRefCntPtr.h
@@ -197,6 +197,9 @@ public:
   private:
     void retain() { if (Obj) IntrusiveRefCntPtrInfo<T>::retain(Obj); }
     void release() { if (Obj) IntrusiveRefCntPtrInfo<T>::release(Obj); }
+
+    template <typename X>
+    friend class IntrusiveRefCntPtr;
   };
 
   template<class T, class U>
diff --git a/include/llvm/ADT/MapVector.h b/include/llvm/ADT/MapVector.h
index 2eae22c..14c49c5 100644
--- a/include/llvm/ADT/MapVector.h
+++ b/include/llvm/ADT/MapVector.h
@@ -37,26 +37,20 @@ class MapVector {
 public:
   typedef typename VectorType::iterator iterator;
   typedef typename VectorType::const_iterator const_iterator;
+  typedef typename VectorType::reverse_iterator reverse_iterator;
+  typedef typename VectorType::const_reverse_iterator const_reverse_iterator;
 
-  size_type size() const {
-    return Vector.size();
-  }
-
-  iterator begin() {
-    return Vector.begin();
-  }
-
-  const_iterator begin() const {
-    return Vector.begin();
-  }
+  size_type size() const { return Vector.size(); }
 
-  iterator end() {
-    return Vector.end();
-  }
+  iterator begin() { return Vector.begin(); }
+  const_iterator begin() const { return Vector.begin(); }
+  iterator end() { return Vector.end(); }
+  const_iterator end() const { return Vector.end(); }
 
-  const_iterator end() const {
-    return Vector.end();
-  }
+  reverse_iterator rbegin() { return Vector.rbegin(); }
+  const_reverse_iterator rbegin() const { return Vector.rbegin(); }
+  reverse_iterator rend() { return Vector.rend(); }
+  const_reverse_iterator rend() const { return Vector.rend(); }
 
   bool empty() const {
     return Vector.empty();
@@ -125,15 +119,68 @@ public:
   }
 
   /// \brief Remove the element given by Iterator.
+  ///
   /// Returns an iterator to the element following the one which was removed,
   /// which may be end().
+  ///
+  /// \note This is a deceivingly expensive operation (linear time).  It's
+  /// usually better to use \a remove_if() if possible.
   typename VectorType::iterator erase(typename VectorType::iterator Iterator) {
-    typename MapType::iterator MapIterator = Map.find(Iterator->first);
-    Map.erase(MapIterator);
-    return Vector.erase(Iterator);
+    Map.erase(Iterator->first);
+    auto Next = Vector.erase(Iterator);
+    if (Next == Vector.end())
+      return Next;
+
+    // Update indices in the map.
+    size_t Index = Next - Vector.begin();
+    for (auto &I : Map) {
+      assert(I.second != Index && "Index was already erased!");
+      if (I.second > Index)
+        --I.second;
+    }
+    return Next;
   }
+
+  /// \brief Remove all elements with the key value Key.
+  ///
+  /// Returns the number of elements removed.
+  size_type erase(const KeyT &Key) {
+    auto Iterator = find(Key);
+    if (Iterator == end())
+      return 0;
+    erase(Iterator);
+    return 1;
+  }
+
+  /// \brief Remove the elements that match the predicate.
+  ///
+  /// Erase all elements that match \c Pred in a single pass.  Takes linear
+  /// time.
+  template <class Predicate> void remove_if(Predicate Pred);
 };
 
+template <typename KeyT, typename ValueT, typename MapType, typename VectorType>
+template <class Function>
+void MapVector<KeyT, ValueT, MapType, VectorType>::remove_if(Function Pred) {
+  auto O = Vector.begin();
+  for (auto I = O, E = Vector.end(); I != E; ++I) {
+    if (Pred(*I)) {
+      // Erase from the map.
+      Map.erase(I->first);
+      continue;
+    }
+
+    if (I != O) {
+      // Move the value and update the index in the map.
+      *O = std::move(*I);
+      Map[O->first] = O - Vector.begin();
+    }
+    ++O;
+  }
+  // Erase trailing entries in the vector.
+  Vector.erase(O, Vector.end());
 }
 
+} // end namespace llvm
+
 #endif
diff --git a/include/llvm/ADT/Optional.h b/include/llvm/ADT/Optional.h
index ae8344d..591872e 100644
--- a/include/llvm/ADT/Optional.h
+++ b/include/llvm/ADT/Optional.h
@@ -20,6 +20,7 @@
 #include "llvm/Support/AlignOf.h"
 #include "llvm/Support/Compiler.h"
 #include <cassert>
+#include <new>
 #include <utility>
 
 namespace llvm {
@@ -29,6 +30,8 @@ class Optional {
   AlignedCharArrayUnion<T> storage;
   bool hasVal;
 public:
+  typedef T value_type;
+
   Optional(NoneType) : hasVal(false) {}
   explicit Optional() : hasVal(false) {}
   Optional(const T &y) : hasVal(true) {
@@ -67,6 +70,61 @@ public:
     return *this;
   }
 
+#if LLVM_HAS_VARIADIC_TEMPLATES
+
+  /// Create a new object by constructing it in place with the given arguments.
+  template<typename ...ArgTypes>
+  void emplace(ArgTypes &&...Args) {
+    reset();
+    hasVal = true;
+    new (storage.buffer) T(std::forward<ArgTypes>(Args)...);
+  }
+
+#else
+  
+  /// Create a new object by default-constructing it in place.
+  void emplace() {
+    reset();
+    hasVal = true;
+    new (storage.buffer) T();
+  }
+  
+  /// Create a new object by constructing it in place with the given arguments.
+  template<typename T1>
+  void emplace(T1 &&A1) {
+    reset();
+    hasVal = true;
+    new (storage.buffer) T(std::forward<T1>(A1));
+  }
+  
+  /// Create a new object by constructing it in place with the given arguments.
+  template<typename T1, typename T2>
+  void emplace(T1 &&A1, T2 &&A2) {
+    reset();
+    hasVal = true;
+    new (storage.buffer) T(std::forward<T1>(A1), std::forward<T2>(A2));
+  }
+  
+  /// Create a new object by constructing it in place with the given arguments.
+  template<typename T1, typename T2, typename T3>
+  void emplace(T1 &&A1, T2 &&A2, T3 &&A3) {
+    reset();
+    hasVal = true;
+    new (storage.buffer) T(std::forward<T1>(A1), std::forward<T2>(A2),
+        std::forward<T3>(A3));
+  }
+  
+  /// Create a new object by constructing it in place with the given arguments.
+  template<typename T1, typename T2, typename T3, typename T4>
+  void emplace(T1 &&A1, T2 &&A2, T3 &&A3, T4 &&A4) {
+    reset();
+    hasVal = true;
+    new (storage.buffer) T(std::forward<T1>(A1), std::forward<T2>(A2),
+        std::forward<T3>(A3), std::forward<T4>(A4));
+  }
+
+#endif // LLVM_HAS_VARIADIC_TEMPLATES
+
   static inline Optional create(const T* y) {
     return y ? Optional(*y) : Optional();
   }
@@ -117,9 +175,19 @@ public:
   const T& operator*() const LLVM_LVALUE_FUNCTION { assert(hasVal); return *getPointer(); }
   T& operator*() LLVM_LVALUE_FUNCTION { assert(hasVal); return *getPointer(); }
 
+  template <typename U>
+  LLVM_CONSTEXPR T getValueOr(U &&value) const LLVM_LVALUE_FUNCTION {
+    return hasValue() ? getValue() : std::forward<U>(value);
+  }
+
 #if LLVM_HAS_RVALUE_REFERENCE_THIS
   T&& getValue() && { assert(hasVal); return std::move(*getPointer()); }
   T&& operator*() && { assert(hasVal); return std::move(*getPointer()); }
+
+  template <typename U>
+  T getValueOr(U &&value) && {
+    return hasValue() ? std::move(getValue()) : std::forward<U>(value);
+  }
 #endif
 };
 
diff --git a/include/llvm/ADT/PostOrderIterator.h b/include/llvm/ADT/PostOrderIterator.h
index dd8cc74..dfadc3b 100644
--- a/include/llvm/ADT/PostOrderIterator.h
+++ b/include/llvm/ADT/PostOrderIterator.h
@@ -57,7 +57,7 @@ public:
   // Return true if edge destination should be visited.
   template<typename NodeType>
   bool insertEdge(NodeType *From, NodeType *To) {
-    return Visited.insert(To);
+    return Visited.insert(To).second;
   }
 
   // Called after all children of BB have been visited.
@@ -76,8 +76,9 @@ public:
   // Return true if edge destination should be visited, called with From = 0 for
   // the root node.
   // Graph edges can be pruned by specializing this function.
-  template<class NodeType>
-  bool insertEdge(NodeType *From, NodeType *To) { return Visited.insert(To); }
+  template <class NodeType> bool insertEdge(NodeType *From, NodeType *To) {
+    return Visited.insert(To).second;
+  }
 
   // Called after all children of BB have been visited.
   template<class NodeType>
diff --git a/include/llvm/ADT/STLExtras.h b/include/llvm/ADT/STLExtras.h
index 1cef393..4e56e4d 100644
--- a/include/llvm/ADT/STLExtras.h
+++ b/include/llvm/ADT/STLExtras.h
@@ -77,8 +77,11 @@ class function_ref<Ret(Params...)> {
   }
 
 public:
-  template<typename Callable>
-  function_ref(Callable &&callable)
+  template <typename Callable>
+  function_ref(Callable &&callable,
+               typename std::enable_if<
+                   !std::is_same<typename std::remove_reference<Callable>::type,
+                                 function_ref>::value>::type * = nullptr)
       : callback(callback_fn<typename std::remove_reference<Callable>::type>),
         callable(reinterpret_cast<intptr_t>(&callable)) {}
   Ret operator()(Params ...params) const {
@@ -100,7 +103,10 @@ class function_ref<Ret()> {
 
 public:
   template<typename Callable>
-  function_ref(Callable &&callable)
+  function_ref(Callable &&callable,
+               typename std::enable_if<
+                   !std::is_same<typename std::remove_reference<Callable>::type,
+                                 function_ref>::value>::type * = nullptr)
       : callback(callback_fn<typename std::remove_reference<Callable>::type>),
         callable(reinterpret_cast<intptr_t>(&callable)) {}
   Ret operator()() const { return callback(callable); }
@@ -119,7 +125,10 @@ class function_ref<Ret(Param1)> {
 
 public:
   template<typename Callable>
-  function_ref(Callable &&callable)
+  function_ref(Callable &&callable,
+               typename std::enable_if<
+                   !std::is_same<typename std::remove_reference<Callable>::type,
+                                 function_ref>::value>::type * = nullptr)
       : callback(callback_fn<typename std::remove_reference<Callable>::type>),
         callable(reinterpret_cast<intptr_t>(&callable)) {}
   Ret operator()(Param1 param1) {
@@ -141,7 +150,10 @@ class function_ref<Ret(Param1, Param2)> {
 
 public:
   template<typename Callable>
-  function_ref(Callable &&callable)
+  function_ref(Callable &&callable,
+               typename std::enable_if<
+                   !std::is_same<typename std::remove_reference<Callable>::type,
+                                 function_ref>::value>::type * = nullptr)
       : callback(callback_fn<typename std::remove_reference<Callable>::type>),
         callable(reinterpret_cast<intptr_t>(&callable)) {}
   Ret operator()(Param1 param1, Param2 param2) {
@@ -167,7 +179,10 @@ class function_ref<Ret(Param1, Param2, Param3)> {
 
 public:
   template<typename Callable>
-  function_ref(Callable &&callable)
+  function_ref(Callable &&callable,
+               typename std::enable_if<
+                   !std::is_same<typename std::remove_reference<Callable>::type,
+                                 function_ref>::value>::type * = nullptr)
       : callback(callback_fn<typename std::remove_reference<Callable>::type>),
         callable(reinterpret_cast<intptr_t>(&callable)) {}
   Ret operator()(Param1 param1, Param2 param2, Param3 param3) {
@@ -530,6 +545,12 @@ make_unique(size_t n) {
 
 #endif
 
+struct FreeDeleter {
+  void operator()(void* v) {
+    ::free(v);
+  }
+};
+
 template<typename First, typename Second>
 struct pair_hash {
   size_t operator()(const std::pair<First, Second> &P) const {
diff --git a/include/llvm/ADT/ScopedHashTable.h b/include/llvm/ADT/ScopedHashTable.h
index 02a6ea3..2f60ecc 100644
--- a/include/llvm/ADT/ScopedHashTable.h
+++ b/include/llvm/ADT/ScopedHashTable.h
@@ -148,7 +148,7 @@ public:
   /// ScopeTy - This is a helpful typedef that allows clients to get easy access
   /// to the name of the scope for this hash table.
   typedef ScopedHashTableScope<K, V, KInfo, AllocatorTy> ScopeTy;
-  typedef unsigned size_type;

+  typedef unsigned size_type;
 private:
   typedef ScopedHashTableVal<K, V> ValTy;
   DenseMap<K, ValTy*, KInfo> TopLevelMap;
@@ -171,7 +171,7 @@ public:
   AllocatorTy &getAllocator() { return Allocator; }
   const AllocatorTy &getAllocator() const { return Allocator; }
 
-  /// Return 1 if the specified key is in the table, 0 otherwise.

+  /// Return 1 if the specified key is in the table, 0 otherwise.
   size_type count(const K &Key) const {
     return TopLevelMap.count(Key);
   }
diff --git a/include/llvm/ADT/SetVector.h b/include/llvm/ADT/SetVector.h
index 1e7d237..a7fd408 100644
--- a/include/llvm/ADT/SetVector.h
+++ b/include/llvm/ADT/SetVector.h
@@ -100,7 +100,7 @@ public:
   /// \brief Insert a new element into the SetVector.
   /// \returns true iff the element was inserted into the SetVector.
   bool insert(const value_type &X) {
-    bool result = set_.insert(X);
+    bool result = set_.insert(X).second;
     if (result)
       vector_.push_back(X);
     return result;
@@ -110,7 +110,7 @@ public:
   template<typename It>
   void insert(It Start, It End) {
     for (; Start != End; ++Start)
-      if (set_.insert(*Start))
+      if (set_.insert(*Start).second)
         vector_.push_back(*Start);
   }
 
diff --git a/include/llvm/ADT/SmallBitVector.h b/include/llvm/ADT/SmallBitVector.h
index 0922017..ababf0f 100644
--- a/include/llvm/ADT/SmallBitVector.h
+++ b/include/llvm/ADT/SmallBitVector.h
@@ -54,7 +54,7 @@ class SmallBitVector {
   };
 
 public:
-  typedef unsigned size_type;

+  typedef unsigned size_type;
   // Encapsulation of a single bit.
   class reference {
     SmallBitVector &TheVector;
diff --git a/include/llvm/ADT/SmallPtrSet.h b/include/llvm/ADT/SmallPtrSet.h
index 74f3fd4..b8977fa 100644
--- a/include/llvm/ADT/SmallPtrSet.h
+++ b/include/llvm/ADT/SmallPtrSet.h
@@ -22,6 +22,7 @@
 #include <cstddef>
 #include <cstring>
 #include <iterator>
+#include <utility>
 
 namespace llvm {
 
@@ -100,7 +101,7 @@ protected:
   /// insert_imp - This returns true if the pointer was new to the set, false if
   /// it was already in the set.  This is hidden from the client so that the
   /// derived class can check that the right type of pointer is passed in.
-  bool insert_imp(const void * Ptr);
+  std::pair<const void *const *, bool> insert_imp(const void *Ptr);
 
   /// erase_imp - If the set contains the specified pointer, remove it and
   /// return true, otherwise return false.  This is hidden from the client so
@@ -240,6 +241,8 @@ struct RoundUpToPowerOfTwo {
 template <typename PtrType>
 class SmallPtrSetImpl : public SmallPtrSetImplBase {
   typedef PointerLikeTypeTraits<PtrType> PtrTraits;
+
+  SmallPtrSetImpl(const SmallPtrSetImpl&) LLVM_DELETED_FUNCTION;
 protected:
   // Constructors that forward to the base.
   SmallPtrSetImpl(const void **SmallStorage, const SmallPtrSetImpl &that)
@@ -251,10 +254,14 @@ protected:
       : SmallPtrSetImplBase(SmallStorage, SmallSize) {}
 
 public:
+  typedef SmallPtrSetIterator<PtrType> iterator;
+  typedef SmallPtrSetIterator<PtrType> const_iterator;
+
   /// insert - This returns true if the pointer was new to the set, false if it
   /// was already in the set.
-  bool insert(PtrType Ptr) {
-    return insert_imp(PtrTraits::getAsVoidPointer(Ptr));
+  std::pair<iterator, bool> insert(PtrType Ptr) {
+    auto p = insert_imp(PtrTraits::getAsVoidPointer(Ptr));
+    return std::make_pair(iterator(p.first, CurArray + CurArraySize), p.second);
   }
 
   /// erase - If the set contains the specified pointer, remove it and return
@@ -274,8 +281,6 @@ public:
       insert(*I);
   }
 
-  typedef SmallPtrSetIterator<PtrType> iterator;
-  typedef SmallPtrSetIterator<PtrType> const_iterator;
   inline iterator begin() const {
     return iterator(CurArray, CurArray+CurArraySize);
   }
diff --git a/include/llvm/ADT/SmallSet.h b/include/llvm/ADT/SmallSet.h
index bb1971e..bc64935 100644
--- a/include/llvm/ADT/SmallSet.h
+++ b/include/llvm/ADT/SmallSet.h
@@ -14,6 +14,7 @@
 #ifndef LLVM_ADT_SMALLSET_H
 #define LLVM_ADT_SMALLSET_H
 
+#include "llvm/ADT/None.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include <set>
@@ -60,16 +61,21 @@ public:
 
   /// insert - Insert an element into the set if it isn't already there.
   /// Returns true if the element is inserted (it was not in the set before).
-  bool insert(const T &V) {
+  /// The first value of the returned pair is unused and provided for
+  /// partial compatibility with the standard library self-associative container
+  /// concept.
+  // FIXME: Add iterators that abstract over the small and large form, and then
+  // return those here.
+  std::pair<NoneType, bool> insert(const T &V) {
     if (!isSmall())
-      return Set.insert(V).second;
+      return std::make_pair(None, Set.insert(V).second);
 
     VIterator I = vfind(V);
     if (I != Vector.end())    // Don't reinsert if it already exists.
-      return false;
+      return std::make_pair(None, false);
     if (Vector.size() < N) {
       Vector.push_back(V);
-      return true;
+      return std::make_pair(None, true);
     }
 
     // Otherwise, grow from vector to set.
@@ -78,7 +84,7 @@ public:
       Vector.pop_back();
     }
     Set.insert(V);
-    return true;
+    return std::make_pair(None, true);
   }
 
   template <typename IterT>
diff --git a/include/llvm/ADT/SmallVector.h b/include/llvm/ADT/SmallVector.h
index 82538e9..2117541 100644
--- a/include/llvm/ADT/SmallVector.h
+++ b/include/llvm/ADT/SmallVector.h
@@ -29,8 +29,7 @@
 
 namespace llvm {
 
-/// SmallVectorBase - This is all the non-templated stuff common to all
-/// SmallVectors.
+/// This is all the non-templated stuff common to all SmallVectors.
 class SmallVectorBase {
 protected:
   void *BeginX, *EndX, *CapacityX;
@@ -39,12 +38,12 @@ protected:
   SmallVectorBase(void *FirstEl, size_t Size)
     : BeginX(FirstEl), EndX(FirstEl), CapacityX((char*)FirstEl+Size) {}
 
-  /// grow_pod - This is an implementation of the grow() method which only works
+  /// This is an implementation of the grow() method which only works
   /// on POD-like data types and is out of line to reduce code duplication.
   void grow_pod(void *FirstEl, size_t MinSizeInBytes, size_t TSize);
 
 public:
-  /// size_in_bytes - This returns size()*sizeof(T).
+  /// This returns size()*sizeof(T).
   size_t size_in_bytes() const {
     return size_t((char*)EndX - (char*)BeginX);
   }
@@ -59,10 +58,9 @@ public:
 
 template <typename T, unsigned N> struct SmallVectorStorage;
 
-/// SmallVectorTemplateCommon - This is the part of SmallVectorTemplateBase
-/// which does not depend on whether the type T is a POD. The extra dummy
-/// template argument is used by ArrayRef to avoid unnecessarily requiring T
-/// to be complete.
+/// This is the part of SmallVectorTemplateBase which does not depend on whether
+/// the type T is a POD. The extra dummy template argument is used by ArrayRef
+/// to avoid unnecessarily requiring T to be complete.
 template <typename T, typename = void>
 class SmallVectorTemplateCommon : public SmallVectorBase {
 private:
@@ -82,13 +80,13 @@ protected:
     SmallVectorBase::grow_pod(&FirstEl, MinSizeInBytes, TSize);
   }
 
-  /// isSmall - Return true if this is a smallvector which has not had dynamic
+  /// Return true if this is a smallvector which has not had dynamic
   /// memory allocated for it.
   bool isSmall() const {
     return BeginX == static_cast<const void*>(&FirstEl);
   }
 
-  /// resetToSmall - Put this vector in a state of being small.
+  /// Put this vector in a state of being small.
   void resetToSmall() {
     BeginX = EndX = CapacityX = &FirstEl;
   }
@@ -128,20 +126,19 @@ public:
   size_type size() const { return end()-begin(); }
   size_type max_size() const { return size_type(-1) / sizeof(T); }
 
-  /// capacity - Return the total number of elements in the currently allocated
-  /// buffer.
+  /// Return the total number of elements in the currently allocated buffer.
   size_t capacity() const { return capacity_ptr() - begin(); }
 
-  /// data - Return a pointer to the vector's buffer, even if empty().
+  /// Return a pointer to the vector's buffer, even if empty().
   pointer data() { return pointer(begin()); }
-  /// data - Return a pointer to the vector's buffer, even if empty().
+  /// Return a pointer to the vector's buffer, even if empty().
   const_pointer data() const { return const_pointer(begin()); }
 
-  reference operator[](unsigned idx) {
+  reference operator[](size_type idx) {
     assert(begin() + idx < end());
     return begin()[idx];
   }
-  const_reference operator[](unsigned idx) const {
+  const_reference operator[](size_type idx) const {
     assert(begin() + idx < end());
     return begin()[idx];
   }
@@ -179,7 +176,7 @@ protected:
     }
   }
 
-  /// move - Use move-assignment to move the range [I, E) onto the
+  /// Use move-assignment to move the range [I, E) onto the
   /// objects starting with "Dest".  This is just <memory>'s
   /// std::move, but not all stdlibs actually provide that.
   template<typename It1, typename It2>
@@ -189,7 +186,7 @@ protected:
     return Dest;
   }
 
-  /// move_backward - Use move-assignment to move the range
+  /// Use move-assignment to move the range
   /// [I, E) onto the objects ending at "Dest", moving objects
   /// in reverse order.  This is just <algorithm>'s
   /// std::move_backward, but not all stdlibs actually provide that.
@@ -200,25 +197,24 @@ protected:
     return Dest;
   }
 
-  /// uninitialized_move - Move the range [I, E) into the uninitialized
-  /// memory starting with "Dest", constructing elements as needed.
+  /// Move the range [I, E) into the uninitialized memory starting with "Dest",
+  /// constructing elements as needed.
   template<typename It1, typename It2>
   static void uninitialized_move(It1 I, It1 E, It2 Dest) {
     for (; I != E; ++I, ++Dest)
       ::new ((void*) &*Dest) T(::std::move(*I));
   }
 
-  /// uninitialized_copy - Copy the range [I, E) onto the uninitialized
-  /// memory starting with "Dest", constructing elements as needed.
+  /// Copy the range [I, E) onto the uninitialized memory starting with "Dest",
+  /// constructing elements as needed.
   template<typename It1, typename It2>
   static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
     std::uninitialized_copy(I, E, Dest);
   }
 
-  /// grow - Grow the allocated memory (without initializing new
-  /// elements), doubling the size of the allocated memory.
-  /// Guarantees space for at least one more element, or MinSize more
-  /// elements if specified.
+  /// Grow the allocated memory (without initializing new elements), doubling
+  /// the size of the allocated memory. Guarantees space for at least one more
+  /// element, or MinSize more elements if specified.
   void grow(size_t MinSize = 0);
 
 public:
@@ -279,22 +275,21 @@ protected:
   // No need to do a destroy loop for POD's.
   static void destroy_range(T *, T *) {}
 
-  /// move - Use move-assignment to move the range [I, E) onto the
+  /// Use move-assignment to move the range [I, E) onto the
   /// objects starting with "Dest".  For PODs, this is just memcpy.
   template<typename It1, typename It2>
   static It2 move(It1 I, It1 E, It2 Dest) {
     return ::std::copy(I, E, Dest);
   }
 
-  /// move_backward - Use move-assignment to move the range
-  /// [I, E) onto the objects ending at "Dest", moving objects
-  /// in reverse order.
+  /// Use move-assignment to move the range [I, E) onto the objects ending at
+  /// "Dest", moving objects in reverse order.
   template<typename It1, typename It2>
   static It2 move_backward(It1 I, It1 E, It2 Dest) {
     return ::std::copy_backward(I, E, Dest);
   }
 
-  /// uninitialized_move - Move the range [I, E) onto the uninitialized memory
+  /// Move the range [I, E) onto the uninitialized memory
   /// starting with "Dest", constructing elements into it as needed.
   template<typename It1, typename It2>
   static void uninitialized_move(It1 I, It1 E, It2 Dest) {
@@ -302,7 +297,7 @@ protected:
     uninitialized_copy(I, E, Dest);
   }
 
-  /// uninitialized_copy - Copy the range [I, E) onto the uninitialized memory
+  /// Copy the range [I, E) onto the uninitialized memory
   /// starting with "Dest", constructing elements into it as needed.
   template<typename It1, typename It2>
   static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
@@ -310,7 +305,7 @@ protected:
     std::uninitialized_copy(I, E, Dest);
   }
 
-  /// uninitialized_copy - Copy the range [I, E) onto the uninitialized memory
+  /// Copy the range [I, E) onto the uninitialized memory
   /// starting with "Dest", constructing elements into it as needed.
   template<typename T1, typename T2>
   static void uninitialized_copy(T1 *I, T1 *E, T2 *Dest) {
@@ -320,7 +315,7 @@ protected:
     memcpy(Dest, I, (E-I)*sizeof(T));
   }
 
-  /// grow - double the size of the allocated memory, guaranteeing space for at
+  /// Double the size of the allocated memory, guaranteeing space for at
   /// least one more element or MinSize if specified.
   void grow(size_t MinSize = 0) {
     this->grow_pod(MinSize*sizeof(T), sizeof(T));
@@ -339,9 +334,8 @@ public:
 };
 
 
-/// SmallVectorImpl - This class consists of common code factored out of the
-/// SmallVector class to reduce code duplication based on the SmallVector 'N'
-/// template parameter.
+/// This class consists of common code factored out of the SmallVector class to
+/// reduce code duplication based on the SmallVector 'N' template parameter.
 template <typename T>
 class SmallVectorImpl : public SmallVectorTemplateBase<T, isPodLike<T>::value> {
   typedef SmallVectorTemplateBase<T, isPodLike<T>::value > SuperClass;
@@ -411,8 +405,7 @@ public:
 
   void swap(SmallVectorImpl &RHS);
 
-  /// append - Add the specified range to the end of the SmallVector.
-  ///
+  /// Add the specified range to the end of the SmallVector.
   template<typename in_iter>
   void append(in_iter in_start, in_iter in_end) {
     size_type NumInputs = std::distance(in_start, in_end);
@@ -427,8 +420,7 @@ public:
     this->setEnd(this->end() + NumInputs);
   }
 
-  /// append - Add the specified range to the end of the SmallVector.
-  ///
+  /// Add the specified range to the end of the SmallVector.
   void append(size_type NumInputs, const T &Elt) {
     // Grow allocated space if needed.
     if (NumInputs > size_type(this->capacity_ptr()-this->end()))
@@ -833,7 +825,7 @@ struct SmallVectorStorage {
 template <typename T> struct SmallVectorStorage<T, 1> {};
 template <typename T> struct SmallVectorStorage<T, 0> {};
 
-/// SmallVector - This is a 'vector' (really, a variable-sized array), optimized
+/// This is a 'vector' (really, a variable-sized array), optimized
 /// for the case when the array is small.  It contains some number of elements
 /// in-place, which allows it to avoid heap allocation when the actual number of
 /// elements is below that threshold.  This allows normal "small" cases to be
@@ -843,7 +835,7 @@ template <typename T> struct SmallVectorStorage<T, 0> {};
 ///
 template <typename T, unsigned N>
 class SmallVector : public SmallVectorImpl<T> {
-  /// Storage - Inline space for elements which aren't stored in the base class.
+  /// Inline space for elements which aren't stored in the base class.
   SmallVectorStorage<T, N> Storage;
 public:
   SmallVector() : SmallVectorImpl<T>(N) {
diff --git a/include/llvm/ADT/SparseBitVector.h b/include/llvm/ADT/SparseBitVector.h
index 36754d6..d5bde29 100644
--- a/include/llvm/ADT/SparseBitVector.h
+++ b/include/llvm/ADT/SparseBitVector.h
@@ -45,7 +45,7 @@ struct SparseBitVectorElement
   : public ilist_node<SparseBitVectorElement<ElementSize> > {
 public:
   typedef unsigned long BitWord;
-  typedef unsigned size_type;

+  typedef unsigned size_type;
   enum {
     BITWORD_SIZE = sizeof(BitWord) * CHAR_BIT,
     BITWORDS_PER_ELEMENT = (ElementSize + BITWORD_SIZE - 1) / BITWORD_SIZE,
diff --git a/include/llvm/ADT/SparseMultiSet.h b/include/llvm/ADT/SparseMultiSet.h
index dc1273e..f858536 100644
--- a/include/llvm/ADT/SparseMultiSet.h
+++ b/include/llvm/ADT/SparseMultiSet.h
@@ -185,7 +185,7 @@ public:
   typedef const ValueT &const_reference;
   typedef ValueT *pointer;
   typedef const ValueT *const_pointer;
-  typedef unsigned size_type;

+  typedef unsigned size_type;
 
   SparseMultiSet()
     : Sparse(nullptr), Universe(0), FreelistIdx(SMSNode::INVALID), NumFree(0) {}
diff --git a/include/llvm/ADT/SparseSet.h b/include/llvm/ADT/SparseSet.h
index 632d52a..9a13440 100644
--- a/include/llvm/ADT/SparseSet.h
+++ b/include/llvm/ADT/SparseSet.h
@@ -124,7 +124,7 @@ class SparseSet {
 
   typedef typename KeyFunctorT::argument_type KeyT;
   typedef SmallVector<ValueT, 8> DenseT;
-  typedef unsigned size_type;

+  typedef unsigned size_type;
   DenseT Dense;
   SparseT *Sparse;
   unsigned Universe;
diff --git a/include/llvm/ADT/StringExtras.h b/include/llvm/ADT/StringExtras.h
index a152f4d..0992f5d 100644
--- a/include/llvm/ADT/StringExtras.h
+++ b/include/llvm/ADT/StringExtras.h
@@ -53,7 +53,7 @@ static inline unsigned hexDigitValue(char C) {
 /// This should only be used with unsigned types.
 ///
 template<typename IntTy>
-static inline char *utohex_buffer(IntTy X, char *BufferEnd) {
+static inline char *utohex_buffer(IntTy X, char *BufferEnd, bool LowerCase = false) {
   char *BufPtr = BufferEnd;
   *--BufPtr = 0;      // Null terminate buffer.
   if (X == 0) {
@@ -63,15 +63,15 @@ static inline char *utohex_buffer(IntTy X, char *BufferEnd) {
 
   while (X) {
     unsigned char Mod = static_cast<unsigned char>(X) & 15;
-    *--BufPtr = hexdigit(Mod);
+    *--BufPtr = hexdigit(Mod, LowerCase);
     X >>= 4;
   }
   return BufPtr;
 }
 
-static inline std::string utohexstr(uint64_t X) {
+static inline std::string utohexstr(uint64_t X, bool LowerCase = false) {
   char Buffer[17];
-  return utohex_buffer(X, Buffer+17);
+  return utohex_buffer(X, Buffer+17, LowerCase);
 }
 
 static inline std::string utostr_32(uint32_t X, bool isNeg = false) {
diff --git a/include/llvm/ADT/StringMap.h b/include/llvm/ADT/StringMap.h
index c40e5e2..2feb2ab 100644
--- a/include/llvm/ADT/StringMap.h
+++ b/include/llvm/ADT/StringMap.h
@@ -117,8 +117,9 @@ public:
 
   explicit StringMapEntry(unsigned strLen)
     : StringMapEntryBase(strLen), second() {}
-  StringMapEntry(unsigned strLen, ValueTy V)
-      : StringMapEntryBase(strLen), second(std::move(V)) {}
+  template <class InitTy>
+  StringMapEntry(unsigned strLen, InitTy &&V)
+      : StringMapEntryBase(strLen), second(std::forward<InitTy>(V)) {}
 
   StringRef getKey() const {
     return StringRef(getKeyData(), getKeyLength());
@@ -138,10 +139,9 @@ public:
 
   /// Create - Create a StringMapEntry for the specified key and default
   /// construct the value.
-  template<typename AllocatorTy, typename InitType>
-  static StringMapEntry *Create(StringRef Key,
-                                AllocatorTy &Allocator,
-                                InitType InitVal) {
+  template <typename AllocatorTy, typename InitType>
+  static StringMapEntry *Create(StringRef Key, AllocatorTy &Allocator,
+                                InitType &&InitVal) {
     unsigned KeyLength = Key.size();
 
     // Allocate a new item with space for the string at the end and a null
@@ -154,7 +154,7 @@ public:
       static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment));
 
     // Default construct the value.
-    new (NewItem) StringMapEntry(KeyLength, std::move(InitVal));
+    new (NewItem) StringMapEntry(KeyLength, std::forward<InitType>(InitVal));
 
     // Copy the string information.
     char *StrBuffer = const_cast<char*>(NewItem->getKeyData());
@@ -170,9 +170,9 @@ public:
 
   /// Create - Create a StringMapEntry with normal malloc/free.
   template<typename InitType>
-  static StringMapEntry *Create(StringRef Key, InitType InitVal) {
+  static StringMapEntry *Create(StringRef Key, InitType &&InitVal) {
     MallocAllocator A;
-    return Create(Key, A, std::move(InitVal));
+    return Create(Key, A, std::forward<InitType>(InitVal));
   }
 
   static StringMapEntry *Create(StringRef Key) {
@@ -296,7 +296,7 @@ public:
   }
 
   ValueTy &operator[](StringRef Key) {
-    return GetOrCreateValue(Key).getValue();
+    return insert(std::make_pair(Key, ValueTy())).first->second;
   }
 
   /// count - Return 1 if the element is in the map, 0 otherwise.
@@ -363,18 +363,6 @@ public:
     NumTombstones = 0;
   }
 
-  /// GetOrCreateValue - Look up the specified key in the table.  If a value
-  /// exists, return it.  Otherwise, default construct a value, insert it, and
-  /// return.
-  template <typename InitTy>
-  MapEntryTy &GetOrCreateValue(StringRef Key, InitTy Val) {
-    return *insert(std::make_pair(Key, std::move(Val))).first;
-  }
-
-  MapEntryTy &GetOrCreateValue(StringRef Key) {
-    return GetOrCreateValue(Key, ValueTy());
-  }
-
   /// remove - Remove the specified key/value pair from the map, but do not
   /// erase it.  This aborts if the key is not in the map.
   void remove(MapEntryTy *KeyValue) {
diff --git a/include/llvm/ADT/StringRef.h b/include/llvm/ADT/StringRef.h
index 1f413e8..778fa10 100644
--- a/include/llvm/ADT/StringRef.h
+++ b/include/llvm/ADT/StringRef.h
@@ -51,12 +51,6 @@ namespace llvm {
     /// The length of the string.
     size_t Length;
 
-    // Workaround PR5482: nearly all gcc 4.x miscompile StringRef and std::min()
-    // Changing the arg of min to be an integer, instead of a reference to an
-    // integer works around this bug.
-    static size_t min(size_t a, size_t b) { return a < b ? a : b; }
-    static size_t max(size_t a, size_t b) { return a > b ? a : b; }
-
     // Workaround memcmp issue with null pointers (undefined behavior)
     // by providing a specialized version
     static int compareMemory(const char *Lhs, const char *Rhs, size_t Length) {
@@ -124,7 +118,7 @@ namespace llvm {
     }
 
     // copy - Allocate copy in Allocator and return StringRef to it.
-    template <typename Allocator> StringRef copy(Allocator &A) {
+    template <typename Allocator> StringRef copy(Allocator &A) const {
       char *S = A.template Allocate<char>(Length);
       std::copy(begin(), end(), S);
       return StringRef(S, Length);
@@ -146,7 +140,7 @@ namespace llvm {
     /// is lexicographically less than, equal to, or greater than the \p RHS.
     int compare(StringRef RHS) const {
       // Check the prefix for a mismatch.
-      if (int Res = compareMemory(Data, RHS.Data, min(Length, RHS.Length)))
+      if (int Res = compareMemory(Data, RHS.Data, std::min(Length, RHS.Length)))
         return Res < 0 ? -1 : 1;
 
       // Otherwise the prefixes match, so we only need to check the lengths.
@@ -237,7 +231,7 @@ 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 = min(From, Length), e = Length; i != e; ++i)
+      for (size_t i = std::min(From, Length), e = Length; i != e; ++i)
         if (Data[i] == C)
           return i;
       return npos;
@@ -254,7 +248,7 @@ namespace llvm {
     /// \returns The index of the last occurrence of \p C, or npos if not
     /// found.
     size_t rfind(char C, size_t From = npos) const {
-      From = min(From, Length);
+      From = std::min(From, Length);
       size_t i = From;
       while (i != 0) {
         --i;
@@ -353,8 +347,11 @@ namespace llvm {
     typename std::enable_if<!std::numeric_limits<T>::is_signed, bool>::type
     getAsInteger(unsigned Radix, T &Result) const {
       unsigned long long ULLVal;
+      // The additional cast to unsigned long long is required to avoid the
+      // Visual C++ warning C4805: '!=' : unsafe mix of type 'bool' and type
+      // 'unsigned __int64' when instantiating getAsInteger with T = bool.
       if (getAsUnsignedInteger(*this, Radix, ULLVal) ||
-            static_cast<T>(ULLVal) != ULLVal)
+          static_cast<unsigned long long>(static_cast<T>(ULLVal)) != ULLVal)
         return true;
       Result = ULLVal;
       return false;
@@ -396,8 +393,8 @@ namespace llvm {
     /// exceeds the number of characters remaining in the string, the string
     /// suffix (starting with \p Start) will be returned.
     StringRef substr(size_t Start, size_t N = npos) const {
-      Start = min(Start, Length);
-      return StringRef(Data + Start, min(N, Length - Start));
+      Start = std::min(Start, Length);
+      return StringRef(Data + Start, std::min(N, Length - Start));
     }
 
     /// Return a StringRef equal to 'this' but with the first \p N elements
@@ -425,8 +422,8 @@ namespace llvm {
     /// number of characters remaining in the string, the string suffix
     /// (starting with \p Start) will be returned.
     StringRef slice(size_t Start, size_t End) const {
-      Start = min(Start, Length);
-      End = min(max(Start, End), Length);
+      Start = std::min(Start, Length);
+      End = std::min(std::max(Start, End), Length);
       return StringRef(Data + Start, End - Start);
     }
 
diff --git a/include/llvm/ADT/StringSet.h b/include/llvm/ADT/StringSet.h
index 7bea577..3e0cc20 100644
--- a/include/llvm/ADT/StringSet.h
+++ b/include/llvm/ADT/StringSet.h
@@ -24,20 +24,9 @@ namespace llvm {
     typedef llvm::StringMap<char, AllocatorTy> base;
   public:
 
-    /// insert - Insert the specified key into the set.  If the key already
-    /// exists in the set, return false and ignore the request, otherwise insert
-    /// it and return true.
-    bool insert(StringRef Key) {
-      // Get or create the map entry for the key; if it doesn't exist the value
-      // type will be default constructed which we use to detect insert.
-      //
-      // We use '+' as the sentinel value in the map.
+    std::pair<typename base::iterator, bool> insert(StringRef Key) {
       assert(!Key.empty());
-      StringMapEntry<char> &Entry = this->GetOrCreateValue(Key);
-      if (Entry.getValue() == '+')
-        return false;
-      Entry.setValue('+');
-      return true;
+      return base::insert(std::make_pair(Key, '\0'));
     }
   };
 }
diff --git a/include/llvm/ADT/TinyPtrVector.h b/include/llvm/ADT/TinyPtrVector.h
index 5669b2a..e158f9d 100644
--- a/include/llvm/ADT/TinyPtrVector.h
+++ b/include/llvm/ADT/TinyPtrVector.h
@@ -99,7 +99,7 @@ public:
   // implicit conversion operator to ArrayRef.
   operator ArrayRef<EltTy>() const {
     if (Val.isNull())
-      return ArrayRef<EltTy>();
+      return None;
     if (Val.template is<EltTy>())
       return *Val.getAddrOfPtr1();
     return *Val.template get<VecTy*>();
diff --git a/include/llvm/ADT/Triple.h b/include/llvm/ADT/Triple.h
index 2867a0e..fbc19f8 100644
--- a/include/llvm/ADT/Triple.h
+++ b/include/llvm/ADT/Triple.h
@@ -48,8 +48,6 @@ public:
 
     arm,        // ARM (little endian): arm, armv.*, xscale
     armeb,      // ARM (big endian): armeb
-    arm64,      // ARM64 (little endian): arm64
-    arm64_be,   // ARM64 (big endian): arm64_be
     aarch64,    // AArch64 (little endian): aarch64
     aarch64_be, // AArch64 (big endian): aarch64_be
     hexagon,    // Hexagon: hexagon
@@ -74,11 +72,34 @@ public:
     nvptx,      // NVPTX: 32-bit
     nvptx64,    // NVPTX: 64-bit
     le32,       // le32: generic little-endian 32-bit CPU (PNaCl / Emscripten)
-    amdil,      // amdil: amd IL
+    le64,       // le64: generic little-endian 64-bit CPU (PNaCl / Emscripten)
+    amdil,      // AMDIL
+    amdil64,    // AMDIL with 64-bit pointers
+    hsail,      // AMD HSAIL
+    hsail64,    // AMD HSAIL with 64-bit pointers
     spir,       // SPIR: standard portable IR for OpenCL 32-bit version
     spir64,     // SPIR: standard portable IR for OpenCL 64-bit version
     kalimba     // Kalimba: generic kalimba
   };
+  enum SubArchType {
+    NoSubArch,
+
+    ARMSubArch_v8,
+    ARMSubArch_v7,
+    ARMSubArch_v7em,
+    ARMSubArch_v7m,
+    ARMSubArch_v7s,
+    ARMSubArch_v6,
+    ARMSubArch_v6m,
+    ARMSubArch_v6t2,
+    ARMSubArch_v5,
+    ARMSubArch_v5te,
+    ARMSubArch_v4t,
+
+    KalimbaSubArch_v3,
+    KalimbaSubArch_v4,
+    KalimbaSubArch_v5
+  };
   enum VendorType {
     UnknownVendor,
 
@@ -90,14 +111,13 @@ public:
     Freescale,
     IBM,
     ImaginationTechnologies,
+    MipsTechnologies,
     NVIDIA,
     CSR
   };
   enum OSType {
     UnknownOS,
 
-    AuroraUX,
-    Cygwin,
     Darwin,
     DragonFly,
     FreeBSD,
@@ -106,7 +126,6 @@ public:
     Linux,
     Lv2,        // PS3
     MacOSX,
-    MinGW32,    // i*86-pc-mingw32, *-w64-mingw32
     NetBSD,
     OpenBSD,
     Solaris,
@@ -151,6 +170,9 @@ private:
   /// The parsed arch type.
   ArchType Arch;
 
+  /// The parsed subarchitecture type.
+  SubArchType SubArch;
+
   /// The parsed vendor type.
   VendorType Vendor;
 
@@ -193,6 +215,9 @@ public:
   /// getArch - Get the parsed architecture type of this triple.
   ArchType getArch() const { return Arch; }
 
+  /// getSubArch - get the parsed subarchitecture type for this triple.
+  SubArchType getSubArch() const { return SubArch; }
+
   /// getVendor - Get the parsed vendor type of this triple.
   VendorType getVendor() const { return Vendor; }
 
@@ -358,13 +383,11 @@ public:
   }
 
   bool isWindowsCygwinEnvironment() const {
-    return getOS() == Triple::Cygwin ||
-           (getOS() == Triple::Win32 && getEnvironment() == Triple::Cygnus);
+    return getOS() == Triple::Win32 && getEnvironment() == Triple::Cygnus;
   }
 
   bool isWindowsGNUEnvironment() const {
-    return getOS() == Triple::MinGW32 ||
-           (getOS() == Triple::Win32 && getEnvironment() == Triple::GNU);
+    return getOS() == Triple::Win32 && getEnvironment() == Triple::GNU;
   }
 
   /// \brief Tests for either Cygwin or MinGW OS
@@ -374,7 +397,8 @@ public:
 
   /// \brief Is this a "Windows" OS targeting a "MSVCRT.dll" environment.
   bool isOSMSVCRT() const {
-    return isWindowsMSVCEnvironment() || isWindowsGNUEnvironment();
+    return isWindowsMSVCEnvironment() || isWindowsGNUEnvironment() ||
+           isWindowsItaniumEnvironment();
   }
 
   /// \brief Tests whether the OS is Windows.
@@ -453,10 +477,6 @@ public:
   /// environment components with a single string.
   void setOSAndEnvironmentName(StringRef Str);
 
-  /// getArchNameForAssembler - Get an architecture name that is understood by
-  /// the target assembler.
-  const char *getArchNameForAssembler();
-
   /// @}
   /// @name Helpers to build variants of a particular triple.
   /// @{
@@ -477,6 +497,12 @@ public:
   ///          architecture if no such variant can be found.
   llvm::Triple get64BitArchVariant() const;
 
+  /// Get the (LLVM) name of the minimum ARM CPU for the arch we are targeting.
+  ///
+  /// \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;
+
   /// @}
   /// @name Static helpers for IDs.
   /// @{
diff --git a/include/llvm/ADT/Twine.h b/include/llvm/ADT/Twine.h
index 4be3ee6..77d92b4 100644
--- a/include/llvm/ADT/Twine.h
+++ b/include/llvm/ADT/Twine.h
@@ -157,7 +157,7 @@ namespace llvm {
     // don't support specifying the backing type for an enum
     /// LHSKind - The NodeKind of the left hand side, \see getLHSKind().
     unsigned char LHSKind;
-    /// RHSKind - The NodeKind of the left hand side, \see getLHSKind().
+    /// RHSKind - The NodeKind of the right hand side, \see getRHSKind().
     unsigned char RHSKind;
 
   private:
diff --git a/include/llvm/ADT/VariadicFunction.h b/include/llvm/ADT/VariadicFunction.h
index 0497aa7..403130c 100644
--- a/include/llvm/ADT/VariadicFunction.h
+++ b/include/llvm/ADT/VariadicFunction.h
@@ -105,7 +105,7 @@ template <typename ResultT, typename ArgT,
           ResultT (*Func)(ArrayRef<const ArgT *>)>
 struct VariadicFunction {
   ResultT operator()() const {
-    return Func(ArrayRef<const ArgT *>());
+    return Func(None);
   }
 
 #define LLVM_DEFINE_OVERLOAD(N) \
@@ -152,7 +152,7 @@ template <typename ResultT, typename Param0T, typename ArgT,
           ResultT (*Func)(Param0T, ArrayRef<const ArgT *>)>
 struct VariadicFunction1 {
   ResultT operator()(Param0T P0) const {
-    return Func(P0, ArrayRef<const ArgT *>());
+    return Func(P0, None);
   }
 
 #define LLVM_DEFINE_OVERLOAD(N) \
@@ -199,7 +199,7 @@ template <typename ResultT, typename Param0T, typename Param1T, typename ArgT,
           ResultT (*Func)(Param0T, Param1T, ArrayRef<const ArgT *>)>
 struct VariadicFunction2 {
   ResultT operator()(Param0T P0, Param1T P1) const {
-    return Func(P0, P1, ArrayRef<const ArgT *>());
+    return Func(P0, P1, None);
   }
 
 #define LLVM_DEFINE_OVERLOAD(N) \
@@ -248,7 +248,7 @@ template <typename ResultT, typename Param0T, typename Param1T,
           ResultT (*Func)(Param0T, Param1T, Param2T, ArrayRef<const ArgT *>)>
 struct VariadicFunction3 {
   ResultT operator()(Param0T P0, Param1T P1, Param2T P2) const {
-    return Func(P0, P1, P2, ArrayRef<const ArgT *>());
+    return Func(P0, P1, P2, None);
   }
 
 #define LLVM_DEFINE_OVERLOAD(N) \
diff --git a/include/llvm/ADT/ilist.h b/include/llvm/ADT/ilist.h
index bc14845..8c19a6f 100644
--- a/include/llvm/ADT/ilist.h
+++ b/include/llvm/ADT/ilist.h
@@ -579,60 +579,6 @@ public:
   void splice(iterator where, iplist &L2, iterator first, iterator last) {
     if (first != last) transfer(where, L2, first, last);
   }
-
-
-
-  //===----------------------------------------------------------------------===
-  // High-Level Functionality that shouldn't really be here, but is part of list
-  //
-
-  // These two functions are actually called remove/remove_if in list<>, but
-  // they actually do the job of erase, rename them accordingly.
-  //
-  void erase(const NodeTy &val) {
-    for (iterator I = begin(), E = end(); I != E; ) {
-      iterator next = I; ++next;
-      if (*I == val) erase(I);
-      I = next;
-    }
-  }
-  template<class Pr1> void erase_if(Pr1 pred) {
-    for (iterator I = begin(), E = end(); I != E; ) {
-      iterator next = I; ++next;
-      if (pred(*I)) erase(I);
-      I = next;
-    }
-  }
-
-  template<class Pr2> void unique(Pr2 pred) {
-    if (empty()) return;
-    for (iterator I = begin(), E = end(), Next = begin(); ++Next != E;) {
-      if (pred(*I))
-        erase(Next);
-      else
-        I = Next;
-      Next = I;
-    }
-  }
-  void unique() { unique(op_equal); }
-
-  template<class Pr3> void merge(iplist &right, Pr3 pred) {
-    iterator first1 = begin(), last1 = end();
-    iterator first2 = right.begin(), last2 = right.end();
-    while (first1 != last1 && first2 != last2)
-      if (pred(*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 Pr3> void sort(Pr3 pred);
-  void sort() { sort(op_less); }
 };
 
 
diff --git a/include/llvm/ADT/ilist_node.h b/include/llvm/ADT/ilist_node.h
index 85aa7a4..26d0b55 100644
--- a/include/llvm/ADT/ilist_node.h
+++ b/include/llvm/ADT/ilist_node.h
@@ -12,8 +12,8 @@
 //
 //===----------------------------------------------------------------------===//
 
-#ifndef LLVM_ADT_ILISTNODE_H
-#define LLVM_ADT_ILISTNODE_H
+#ifndef LLVM_ADT_ILIST_NODE_H
+#define LLVM_ADT_ILIST_NODE_H
 
 namespace llvm {
 
diff --git a/include/llvm/ADT/iterator_range.h b/include/llvm/ADT/iterator_range.h
index dd17d6c..ecaf4a2 100644
--- a/include/llvm/ADT/iterator_range.h
+++ b/include/llvm/ADT/iterator_range.h
@@ -48,6 +48,10 @@ public:
 template <class T> iterator_range<T> make_range(T x, T y) {
   return iterator_range<T>(std::move(x), std::move(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));
+}
 }
 
 #endif