diff --git a/llvm/include/llvm/IR/Attributes.h b/llvm/include/llvm/IR/Attributes.h
--- a/llvm/include/llvm/IR/Attributes.h
+++ b/llvm/include/llvm/IR/Attributes.h
@@ -18,6 +18,8 @@
 #include "llvm-c/Types.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/Optional.h"
+#include "llvm/ADT/SmallString.h"
+#include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Config/llvm-config.h"
@@ -722,7 +724,7 @@
 /// equality, presence of attributes, etc.
 class AttrBuilder {
   std::bitset<Attribute::EndAttrKinds> Attrs;
-  std::map<std::string, std::string, std::less<>> TargetDepAttrs;
+  StringMap<SmallString<16>> TargetDepAttrs;
   MaybeAlign Alignment;
   MaybeAlign StackAlignment;
   uint64_t DerefBytes = 0;
@@ -866,7 +868,6 @@
   bool empty() const { return Attrs.none(); }
 
   // Iterators for target-dependent attributes.
-  using td_type = std::pair<std::string, std::string>;
   using td_iterator = decltype(TargetDepAttrs)::iterator;
   using td_const_iterator = decltype(TargetDepAttrs)::const_iterator;
   using td_range = iterator_range<td_iterator>;
@@ -886,6 +887,8 @@
 
   bool td_empty() const { return TargetDepAttrs.empty(); }
 
+  bool td_size() const { return TargetDepAttrs.size(); }
+
   bool operator==(const AttrBuilder &B);
   bool operator!=(const AttrBuilder &B) {
     return !(*this == B);
diff --git a/llvm/lib/IR/Attributes.cpp b/llvm/lib/IR/Attributes.cpp
--- a/llvm/lib/IR/Attributes.cpp
+++ b/llvm/lib/IR/Attributes.cpp
@@ -875,8 +875,15 @@
   }
 
   // Add target-dependent (string) attributes.
+  unsigned NumStringAttrs = B.td_size();
+  Attrs.reserve(Attrs.size() + NumStringAttrs);
   for (const auto &TDA : B.td_attrs())
-    Attrs.emplace_back(Attribute::get(C, TDA.first, TDA.second));
+    Attrs.emplace_back(Attribute::get(C, TDA.first(), TDA.second));
+
+  // And sort string attributes only.
+  auto StringAttrs =
+      MutableArrayRef<Attribute>(Attrs).take_back(NumStringAttrs);
+  llvm::sort(StringAttrs.begin(), StringAttrs.end());
 
   return getSorted(C, Attrs);
 }
@@ -1571,7 +1578,7 @@
 }
 
 AttrBuilder &AttrBuilder::addAttribute(StringRef A, StringRef V) {
-  TargetDepAttrs[std::string(A)] = std::string(V);
+  TargetDepAttrs[A] = V;
   return *this;
 }
 
@@ -1603,9 +1610,7 @@
 }
 
 AttrBuilder &AttrBuilder::removeAttribute(StringRef A) {
-  auto I = TargetDepAttrs.find(A);
-  if (I != TargetDepAttrs.end())
-    TargetDepAttrs.erase(I);
+  TargetDepAttrs.erase(A);
   return *this;
 }
 
@@ -1706,8 +1711,8 @@
 
   Attrs |= B.Attrs;
 
-  for (auto I : B.td_attrs())
-    TargetDepAttrs[I.first] = I.second;
+  for (auto &I : B.td_attrs())
+    TargetDepAttrs[I.first()] = I.second;
 
   return *this;
 }
@@ -1737,8 +1742,8 @@
 
   Attrs &= ~B.Attrs;
 
-  for (auto I : B.td_attrs())
-    TargetDepAttrs.erase(I.first);
+  for (auto &I : B.td_attrs())
+    TargetDepAttrs.erase(I.first());
 
   return *this;
 }
@@ -1750,14 +1755,14 @@
 
   // Then check if any target dependent ones do.
   for (const auto &I : td_attrs())
-    if (B.contains(I.first))
+    if (B.contains(I.first()))
       return true;
 
   return false;
 }
 
 bool AttrBuilder::contains(StringRef A) const {
-  return TargetDepAttrs.find(A) != TargetDepAttrs.end();
+  return TargetDepAttrs.count(A);
 }
 
 bool AttrBuilder::hasAttributes() const {
@@ -1790,7 +1795,7 @@
 
   for (td_const_iterator I = TargetDepAttrs.begin(),
          E = TargetDepAttrs.end(); I != E; ++I)
-    if (B.TargetDepAttrs.find(I->first) == B.TargetDepAttrs.end())
+    if (!B.contains(I->first()))
       return false;
 
   return Alignment == B.Alignment && StackAlignment == B.StackAlignment &&
diff --git a/llvm/lib/IR/AutoUpgrade.cpp b/llvm/lib/IR/AutoUpgrade.cpp
--- a/llvm/lib/IR/AutoUpgrade.cpp
+++ b/llvm/lib/IR/AutoUpgrade.cpp
@@ -4251,7 +4251,7 @@
   if (B.contains("no-frame-pointer-elim")) {
     // The value can be "true" or "false".
     for (const auto &I : B.td_attrs())
-      if (I.first == "no-frame-pointer-elim")
+      if (I.first() == "no-frame-pointer-elim")
         FramePointer = I.second == "true" ? "all" : "none";
     B.removeAttribute("no-frame-pointer-elim");
   }
@@ -4268,7 +4268,7 @@
     // The value can be "true" or "false".
     bool NullPointerIsValid = false;
     for (const auto &I : B.td_attrs())
-      if (I.first == "null-pointer-is-valid")
+      if (I.first() == "null-pointer-is-valid")
         NullPointerIsValid = I.second == "true";
     B.removeAttribute("null-pointer-is-valid");
     if (NullPointerIsValid)