Index: clang/include/clang/CodeGen/CodeGenABITypes.h
===================================================================
--- clang/include/clang/CodeGen/CodeGenABITypes.h
+++ clang/include/clang/CodeGen/CodeGenABITypes.h
@@ -30,7 +30,7 @@
 #include "llvm/IR/BasicBlock.h"
 
 namespace llvm {
-class AttrBuilder;
+class SmallAttrBuilder;
 class Constant;
 class DataLayout;
 class Module;
@@ -129,7 +129,7 @@
 /// This function assumes that the caller is not defining a function that
 /// requires special no-builtin treatment.
 void addDefaultFunctionDefinitionAttributes(CodeGenModule &CGM,
-                                            llvm::AttrBuilder &attrs);
+                                            llvm::SmallAttrBuilder &attrs);
 
 /// Returns the default constructor for a C struct with non-trivially copyable
 /// fields, generating it if necessary. The returned function uses the `cdecl`
Index: clang/lib/CodeGen/CGCall.cpp
===================================================================
--- clang/lib/CodeGen/CGCall.cpp
+++ clang/lib/CodeGen/CGCall.cpp
@@ -1736,9 +1736,10 @@
   return GetFunctionType(GD);
 }
 
-static void AddAttributesFromFunctionProtoType(ASTContext &Ctx,
-                                               llvm::AttrBuilder &FuncAttrs,
-                                               const FunctionProtoType *FPT) {
+static void
+AddAttributesFromFunctionProtoType(ASTContext &Ctx,
+                                   llvm::SmallAttrBuilder &FuncAttrs,
+                                   const FunctionProtoType *FPT) {
   if (!FPT)
     return;
 
@@ -1747,7 +1748,7 @@
     FuncAttrs.addAttribute(llvm::Attribute::NoUnwind);
 }
 
-static void AddAttributesFromAssumes(llvm::AttrBuilder &FuncAttrs,
+static void AddAttributesFromAssumes(llvm::SmallAttrBuilder &FuncAttrs,
                                      const Decl *Callee) {
   if (!Callee)
     return;
@@ -1774,10 +1775,9 @@
   return ReturnType.isTriviallyCopyableType(Context);
 }
 
-void CodeGenModule::getDefaultFunctionAttributes(StringRef Name,
-                                                 bool HasOptnone,
-                                                 bool AttrOnCallSite,
-                                               llvm::AttrBuilder &FuncAttrs) {
+void CodeGenModule::getDefaultFunctionAttributes(
+    StringRef Name, bool HasOptnone, bool AttrOnCallSite,
+    llvm::SmallAttrBuilder &FuncAttrs) {
   // OptimizeNoneAttr takes precedence over -Os or -Oz. No warning needed.
   if (!HasOptnone) {
     if (CodeGenOpts.OptimizeSize)
@@ -1898,7 +1898,7 @@
 }
 
 void CodeGenModule::addDefaultFunctionDefinitionAttributes(llvm::Function &F) {
-  llvm::AttrBuilder FuncAttrs;
+  llvm::SmallAttrBuilder FuncAttrs(F.getContext());
   getDefaultFunctionAttributes(F.getName(), F.hasOptNone(),
                                /* AttrOnCallSite = */ false, FuncAttrs);
   // TODO: call GetCPUAndFeaturesAttributes?
@@ -1906,13 +1906,13 @@
 }
 
 void CodeGenModule::addDefaultFunctionDefinitionAttributes(
-                                                   llvm::AttrBuilder &attrs) {
+    llvm::SmallAttrBuilder &attrs) {
   getDefaultFunctionAttributes(/*function name*/ "", /*optnone*/ false,
                                /*for call*/ false, attrs);
   GetCPUAndFeaturesAttributes(GlobalDecl(), attrs);
 }
 
-static void addNoBuiltinAttributes(llvm::AttrBuilder &FuncAttrs,
+static void addNoBuiltinAttributes(llvm::SmallAttrBuilder &FuncAttrs,
                                    const LangOptions &LangOpts,
                                    const NoBuiltinAttr *NBA = nullptr) {
   auto AddNoBuiltinAttr = [&FuncAttrs](StringRef BuiltinName) {
@@ -2020,8 +2020,8 @@
                                            llvm::AttributeList &AttrList,
                                            unsigned &CallingConv,
                                            bool AttrOnCallSite, bool IsThunk) {
-  llvm::AttrBuilder FuncAttrs;
-  llvm::AttrBuilder RetAttrs;
+  llvm::SmallAttrBuilder FuncAttrs(getLLVMContext());
+  llvm::SmallAttrBuilder RetAttrs(getLLVMContext());
 
   // Collect function IR attributes from the CC lowering.
   // We'll collect the paramete and result attributes later.
Index: clang/lib/CodeGen/CodeGenABITypes.cpp
===================================================================
--- clang/lib/CodeGen/CodeGenABITypes.cpp
+++ clang/lib/CodeGen/CodeGenABITypes.cpp
@@ -27,8 +27,8 @@
 using namespace clang;
 using namespace CodeGen;
 
-void CodeGen::addDefaultFunctionDefinitionAttributes(CodeGenModule &CGM,
-                                                     llvm::AttrBuilder &attrs) {
+void CodeGen::addDefaultFunctionDefinitionAttributes(
+    CodeGenModule &CGM, llvm::SmallAttrBuilder &attrs) {
   CGM.addDefaultFunctionDefinitionAttributes(attrs);
 }
 
Index: clang/lib/CodeGen/CodeGenModule.h
===================================================================
--- clang/lib/CodeGen/CodeGenModule.h
+++ clang/lib/CodeGen/CodeGenModule.h
@@ -1223,7 +1223,7 @@
 
   /// Like the overload taking a `Function &`, but intended specifically
   /// for frontends that want to build on Clang's target-configuration logic.
-  void addDefaultFunctionDefinitionAttributes(llvm::AttrBuilder &attrs);
+  void addDefaultFunctionDefinitionAttributes(llvm::SmallAttrBuilder &attrs);
 
   StringRef getMangledName(GlobalDecl GD);
   StringRef getBlockMangledName(GlobalDecl GD, const BlockDecl *BD);
@@ -1483,7 +1483,7 @@
                         ForDefinition_t IsForDefinition = NotForDefinition);
 
   bool GetCPUAndFeaturesAttributes(GlobalDecl GD,
-                                   llvm::AttrBuilder &AttrBuilder);
+                                   llvm::SmallAttrBuilder &AttrBuilder);
   void setNonAliasAttributes(GlobalDecl GD, llvm::GlobalObject *GO);
 
   /// Set function attributes for a function declaration.
@@ -1623,7 +1623,7 @@
   /// attributes to add to a function with the given properties.
   void getDefaultFunctionAttributes(StringRef Name, bool HasOptnone,
                                     bool AttrOnCallSite,
-                                    llvm::AttrBuilder &FuncAttrs);
+                                    llvm::SmallAttrBuilder &FuncAttrs);
 
   llvm::Metadata *CreateMetadataIdentifierImpl(QualType T, MetadataTypeMap &Map,
                                                StringRef Suffix);
Index: clang/lib/CodeGen/CodeGenModule.cpp
===================================================================
--- clang/lib/CodeGen/CodeGenModule.cpp
+++ clang/lib/CodeGen/CodeGenModule.cpp
@@ -1819,7 +1819,7 @@
 
 void CodeGenModule::SetLLVMFunctionAttributesForDefinition(const Decl *D,
                                                            llvm::Function *F) {
-  llvm::AttrBuilder B;
+  llvm::SmallAttrBuilder B(getLLVMContext());
 
   if (CodeGenOpts.UnwindTables)
     B.addAttribute(llvm::Attribute::UWTable);
@@ -1982,9 +1982,7 @@
 void CodeGenModule::setLLVMFunctionFEnvAttributes(const FunctionDecl *D,
                                                   llvm::Function *F) {
   if (D->hasAttr<StrictFPAttr>()) {
-    llvm::AttrBuilder FuncAttrs;
-    FuncAttrs.addAttribute("strictfp");
-    F->addFnAttrs(FuncAttrs);
+    F->addFnAttr("strictfp");
   }
 }
 
@@ -2007,7 +2005,7 @@
 }
 
 bool CodeGenModule::GetCPUAndFeaturesAttributes(GlobalDecl GD,
-                                                llvm::AttrBuilder &Attrs) {
+                                                llvm::SmallAttrBuilder &Attrs) {
   // Add target-cpu and target-features attributes to functions. If
   // we have a decl for the function and it has a target attribute then
   // parse that and add it to the feature set.
@@ -2092,12 +2090,12 @@
         if (!D->getAttr<SectionAttr>())
           F->addFnAttr("implicit-section-name", SA->getName());
 
-      llvm::AttrBuilder Attrs;
+      llvm::SmallAttrBuilder Attrs(getLLVMContext());
       if (GetCPUAndFeaturesAttributes(GD, Attrs)) {
         // We know that GetCPUAndFeaturesAttributes will always have the
         // newest set, since it has the newest possible FunctionDecl, so the
         // new ones should replace the old.
-        llvm::AttrBuilder RemoveAttrs;
+        llvm::SmallAttrBuilder RemoveAttrs(getLLVMContext());
         RemoveAttrs.addAttribute("target-cpu");
         RemoveAttrs.addAttribute("target-features");
         RemoveAttrs.addAttribute("tune-cpu");
@@ -3785,7 +3783,8 @@
   if (D)
     SetFunctionAttributes(GD, F, IsIncompleteFunction, IsThunk);
   if (ExtraAttrs.hasFnAttrs()) {
-    llvm::AttrBuilder B(ExtraAttrs, llvm::AttributeList::FunctionIndex);
+    llvm::SmallAttrBuilder B(getLLVMContext(), ExtraAttrs,
+                             llvm::AttributeList::FunctionIndex);
     F->addFnAttrs(B);
   }
 
Index: llvm/include/llvm/IR/Attributes.h
===================================================================
--- llvm/include/llvm/IR/Attributes.h
+++ llvm/include/llvm/IR/Attributes.h
@@ -34,6 +34,7 @@
 namespace llvm {
 
 class AttrBuilder;
+class SmallAttrBuilder;
 class AttributeImpl;
 class AttributeListImpl;
 class AttributeSetNode;
@@ -287,6 +288,7 @@
   ~AttributeSet() = default;
 
   static AttributeSet get(LLVMContext &C, const AttrBuilder &B);
+  static AttributeSet get(LLVMContext &C, const SmallAttrBuilder &B);
   static AttributeSet get(LLVMContext &C, ArrayRef<Attribute> Attrs);
 
   bool operator==(const AttributeSet &O) const { return SetNode == O.SetNode; }
@@ -321,6 +323,8 @@
   /// attribute sets are immutable.
   LLVM_NODISCARD AttributeSet
   removeAttributes(LLVMContext &C, const AttrBuilder &AttrsToRemove) const;
+  LLVM_NODISCARD AttributeSet
+  removeAttributes(LLVMContext &C, const SmallAttrBuilder &AttrsToRemove) const;
 
   /// Return the number of attributes in this set.
   unsigned getNumAttributes() const;
@@ -457,6 +461,8 @@
                            ArrayRef<StringRef> Kind);
   static AttributeList get(LLVMContext &C, unsigned Index,
                            const AttrBuilder &B);
+  static AttributeList get(LLVMContext &C, unsigned Index,
+                           const SmallAttrBuilder &B);
 
   // TODO: remove non-AtIndex versions of these methods.
   /// Add an attribute to the attribute set at the given index.
@@ -481,6 +487,8 @@
   LLVM_NODISCARD AttributeList addAttributesAtIndex(LLVMContext &C,
                                                     unsigned Index,
                                                     const AttrBuilder &B) const;
+  LLVM_NODISCARD AttributeList addAttributesAtIndex(
+      LLVMContext &C, unsigned Index, const SmallAttrBuilder &B) const;
 
   /// Add a function attribute to the list. Returns a new list because
   /// attribute lists are immutable.
@@ -509,6 +517,10 @@
                                                const AttrBuilder &B) const {
     return addAttributesAtIndex(C, FunctionIndex, B);
   }
+  LLVM_NODISCARD AttributeList
+  addFnAttributes(LLVMContext &C, const SmallAttrBuilder &B) const {
+    return addAttributesAtIndex(C, FunctionIndex, B);
+  }
 
   /// Add a return value attribute to the list. Returns a new list because
   /// attribute lists are immutable.
@@ -530,6 +542,10 @@
                                                 const AttrBuilder &B) const {
     return addAttributesAtIndex(C, ReturnIndex, B);
   }
+  LLVM_NODISCARD AttributeList
+  addRetAttributes(LLVMContext &C, const SmallAttrBuilder &B) const {
+    return addAttributesAtIndex(C, ReturnIndex, B);
+  }
 
   /// Add an argument attribute to the list. Returns a new list because
   /// attribute lists are immutable.
@@ -559,6 +575,10 @@
                                                   const AttrBuilder &B) const {
     return addAttributesAtIndex(C, ArgNo + FirstArgIndex, B);
   }
+  LLVM_NODISCARD AttributeList addParamAttributes(
+      LLVMContext &C, unsigned ArgNo, const SmallAttrBuilder &B) const {
+    return addAttributesAtIndex(C, ArgNo + FirstArgIndex, B);
+  }
 
   /// Remove the specified attribute at the specified index from this
   /// attribute list. Returns a new list because attribute lists are immutable.
@@ -579,6 +599,9 @@
   /// attribute list. Returns a new list because attribute lists are immutable.
   LLVM_NODISCARD AttributeList removeAttributesAtIndex(
       LLVMContext &C, unsigned Index, const AttrBuilder &AttrsToRemove) const;
+  LLVM_NODISCARD AttributeList
+  removeAttributesAtIndex(LLVMContext &C, unsigned Index,
+                          const SmallAttrBuilder &AttrsToRemove) const;
 
   /// Remove all attributes at the specified index from this
   /// attribute list. Returns a new list because attribute lists are immutable.
@@ -605,6 +628,10 @@
   removeFnAttributes(LLVMContext &C, const AttrBuilder &AttrsToRemove) const {
     return removeAttributesAtIndex(C, FunctionIndex, AttrsToRemove);
   }
+  LLVM_NODISCARD AttributeList removeFnAttributes(
+      LLVMContext &C, const SmallAttrBuilder &AttrsToRemove) const {
+    return removeAttributesAtIndex(C, FunctionIndex, AttrsToRemove);
+  }
 
   /// Remove the attributes at the function index from this
   /// attribute list. Returns a new list because attribute lists are immutable.
@@ -632,6 +659,10 @@
   removeRetAttributes(LLVMContext &C, const AttrBuilder &AttrsToRemove) const {
     return removeAttributesAtIndex(C, ReturnIndex, AttrsToRemove);
   }
+  LLVM_NODISCARD AttributeList removeRetAttributes(
+      LLVMContext &C, const SmallAttrBuilder &AttrsToRemove) const {
+    return removeAttributesAtIndex(C, ReturnIndex, AttrsToRemove);
+  }
 
   /// Remove the specified attribute at the specified arg index from this
   /// attribute list. Returns a new list because attribute lists are immutable.
@@ -654,6 +685,11 @@
       LLVMContext &C, unsigned ArgNo, const AttrBuilder &AttrsToRemove) const {
     return removeAttributesAtIndex(C, ArgNo + FirstArgIndex, AttrsToRemove);
   }
+  LLVM_NODISCARD AttributeList
+  removeParamAttributes(LLVMContext &C, unsigned ArgNo,
+                        const SmallAttrBuilder &AttrsToRemove) const {
+    return removeAttributesAtIndex(C, ArgNo + FirstArgIndex, AttrsToRemove);
+  }
 
   /// Remove all attributes at the specified arg index from this
   /// attribute list. Returns a new list because attribute lists are immutable.
@@ -927,6 +963,184 @@
 
 //===----------------------------------------------------------------------===//
 /// \class
+/// This class aggregates add/remove attribute requests in order to efficiently
+/// build new AttributeSet. Unlike AttrBuilder, it is not suited to query the
+/// state of attributes.
+
+class SmallAttrBuilder {
+  LLVMContext &Ctxt;
+
+  SmallVector<Attribute> EnumAttrs;
+  SmallVector<Attribute> StringAttrs;
+  using iterator = typename SmallVector<Attribute>::iterator;
+
+  struct StringAttributeComparator {
+    bool operator()(Attribute A0, Attribute A1) const {
+      return A0.getKindAsString() < A1.getKindAsString();
+    }
+    bool operator()(Attribute A0, StringRef Kind) const {
+      return A0.getKindAsString() < Kind;
+    }
+  };
+  struct EnumAttributeComparator {
+    bool operator()(Attribute A0, Attribute A1) const {
+      return A0.getKindAsEnum() < A1.getKindAsEnum();
+    }
+    bool operator()(Attribute A0, Attribute::AttrKind Kind) const {
+      return A0.getKindAsEnum() < Kind;
+    }
+  };
+  iterator addStringAttributeHelper(Attribute A, iterator Iter) {
+    auto R = std::lower_bound(Iter, StringAttrs.end(), A,
+                              StringAttributeComparator{});
+    if (R == StringAttrs.end()) {
+      StringAttrs.push_back(A);
+      return StringAttrs.end();
+    } else if (R->hasAttribute(A.getKindAsString())) {
+      std::swap(*R, A);
+      return R;
+    } else {
+      return StringAttrs.insert(R, A);
+    }
+  }
+  iterator addEnumAttributeHelper(Attribute A, iterator Iter) {
+    auto R =
+        std::lower_bound(Iter, EnumAttrs.end(), A, EnumAttributeComparator{});
+    if (R == EnumAttrs.end()) {
+      EnumAttrs.push_back(A);
+      return EnumAttrs.end();
+    } else if (R->hasAttribute(A.getKindAsEnum()))
+      return R;
+    else {
+      return EnumAttrs.insert(R, A);
+    }
+  }
+  iterator addAttributeHelper(Attribute A, iterator Iter) {
+    if (A.isStringAttribute()) {
+      return addStringAttributeHelper(A, Iter);
+    } else {
+      return addEnumAttributeHelper(A, Iter);
+    }
+  }
+
+public:
+
+  SmallAttrBuilder(LLVMContext &Ctxt) : Ctxt(Ctxt) {}
+  SmallAttrBuilder(LLVMContext &Ctxt, AttributeList AL, unsigned Idx)
+      : SmallAttrBuilder(Ctxt, AL.getAttributes(Idx)) {}
+
+  SmallAttrBuilder(LLVMContext &Ctxt, AttributeSet AS) : Ctxt(Ctxt) {
+    for (Attribute A : AS)
+      if (A.isStringAttribute())
+        StringAttrs.push_back(A);
+      else
+        EnumAttrs.push_back(A);
+    assert(llvm::is_sorted(EnumAttrs) && "Expected sorted attributes!");
+    assert(llvm::is_sorted(StringAttrs) && "Expected sorted attributes!");
+  }
+
+  template <class Range, class _ = std::enable_if_t<!std::is_same<std::decay_t<Range>, AttributeSet>::value, void>>
+  SmallAttrBuilder(LLVMContext &Ctxt, Range &&R) : Ctxt(Ctxt) {
+    for (Attribute A : R)
+      if (A.isStringAttribute())
+        StringAttrs.push_back(A);
+      else
+        EnumAttrs.push_back(A);
+    llvm::sort(StringAttrs, StringAttributeComparator());
+    llvm::sort(EnumAttrs, EnumAttributeComparator());
+  }
+
+  SmallAttrBuilder &addAttribute(Attribute::AttrKind Val) {
+    Attribute A = Attribute::get(Ctxt, Val);
+    auto R = std::lower_bound(EnumAttrs.begin(), EnumAttrs.end(), A,
+                              EnumAttributeComparator{});
+    if (R != EnumAttrs.end() && R->hasAttribute(Val))
+      return *this;
+    else
+      EnumAttrs.insert(R, A);
+    return *this;
+  }
+  SmallAttrBuilder &addAttribute(StringRef K, StringRef V = StringRef()) {
+    Attribute A = Attribute::get(Ctxt, K, V);
+    auto R = std::lower_bound(StringAttrs.begin(), StringAttrs.end(), A,
+                              StringAttributeComparator{});
+    if (R != StringAttrs.end() && R->hasAttribute(K))
+      std::swap(*R, A);
+    else
+      StringAttrs.insert(R, A);
+    return *this;
+  }
+  SmallAttrBuilder &addAttribute(Attribute A) {
+    if (A.isStringAttribute())
+      addStringAttributeHelper(A, StringAttrs.begin());
+    else
+      addEnumAttributeHelper(A, EnumAttrs.begin());
+    return *this;
+  }
+  SmallAttrBuilder &merge(const SmallAttrBuilder &B);
+
+  bool hasAttributes() const {
+    return !EnumAttrs.empty() || !StringAttrs.empty();
+  }
+
+  SmallAttrBuilder &removeAttribute(StringRef Val) {
+    auto R = std::lower_bound(StringAttrs.begin(), StringAttrs.end(), Val,
+                              StringAttributeComparator{});
+    if (R != StringAttrs.end() && R->hasAttribute(Val)) {
+      StringAttrs.erase(R);
+    }
+    return *this;
+  }
+
+  SmallAttrBuilder &removeAttribute(Attribute::AttrKind Val) {
+    auto R = std::lower_bound(EnumAttrs.begin(), EnumAttrs.end(), Val,
+                              EnumAttributeComparator{});
+    if (R != EnumAttrs.end() && R->hasAttribute(Val)) {
+      EnumAttrs.erase(R);
+    }
+    return *this;
+  }
+  SmallAttrBuilder &removeStringAttribute(Attribute A) {
+    return removeAttribute(A.getKindAsString());
+  }
+  SmallAttrBuilder &removeEnumAttribute(Attribute A) {
+    return removeAttribute(A.getKindAsEnum());
+  }
+
+  SmallAttrBuilder &removeAttribute(Attribute A) {
+    if (A.isStringAttribute())
+      return removeStringAttribute(A);
+    else
+      return removeEnumAttribute(A);
+  }
+
+  unsigned size() const { return EnumAttrs.size() + StringAttrs.size(); }
+
+  bool empty() const { return EnumAttrs.empty(); }
+
+  void clear() {
+    EnumAttrs.clear();
+    StringAttrs.clear();
+  }
+  std::pair<ArrayRef<Attribute>, ArrayRef<Attribute>> uniquify() const {
+    return std::make_pair(ArrayRef<Attribute>(EnumAttrs),
+                          ArrayRef<Attribute>(StringAttrs));
+  }
+
+  SmallAttrBuilder &addAllocSizeAttr(unsigned ElemSize,
+                                     const Optional<unsigned> &NumElems);
+  SmallAttrBuilder &addDereferenceableAttr(uint64_t Bytes);
+  SmallAttrBuilder &addDereferenceableOrNullAttr(uint64_t Bytes);
+  SmallAttrBuilder &addAlignmentAttr(MaybeAlign Align);
+  SmallAttrBuilder &addAlignmentAttr(unsigned Align) {
+    return addAlignmentAttr(MaybeAlign(Align));
+  }
+  SmallAttrBuilder &addStructRetAttr(Type *Ty);
+  SmallAttrBuilder &addByValAttr(Type *Ty);
+};
+
+//===----------------------------------------------------------------------===//
+/// \class
 /// This class is used in conjunction with the Attribute::get method to
 /// create an Attribute object. The object itself is uniquified. The Builder's
 /// value, however, is not. So this can be used as a quick way to test for
Index: llvm/include/llvm/IR/Function.h
===================================================================
--- llvm/include/llvm/IR/Function.h
+++ llvm/include/llvm/IR/Function.h
@@ -333,6 +333,7 @@
 
   /// Add function attributes to this function.
   void addFnAttrs(const AttrBuilder &Attrs);
+  void addFnAttrs(const SmallAttrBuilder &Attrs);
 
   /// Add return value attributes to this function.
   void addRetAttr(Attribute::AttrKind Kind);
@@ -365,6 +366,7 @@
   void removeFnAttr(StringRef Kind);
 
   void removeFnAttrs(const AttrBuilder &Attrs);
+  void removeFnAttrs(const SmallAttrBuilder &Attrs);
 
   /// removes the attribute from the return value list of attributes.
   void removeRetAttr(Attribute::AttrKind Kind);
Index: llvm/lib/IR/AttributeImpl.h
===================================================================
--- llvm/lib/IR/AttributeImpl.h
+++ llvm/lib/IR/AttributeImpl.h
@@ -220,10 +220,12 @@
   DenseMap<StringRef, Attribute> StringAttrs;
 
   AttributeSetNode(ArrayRef<Attribute> Attrs);
+  AttributeSetNode(ArrayRef<Attribute> EnumAttrs,
+                   ArrayRef<Attribute> StringAttrs);
 
+  Optional<Attribute> findEnumAttribute(Attribute::AttrKind Kind) const;
   static AttributeSetNode *getSorted(LLVMContext &C,
                                      ArrayRef<Attribute> SortedAttrs);
-  Optional<Attribute> findEnumAttribute(Attribute::AttrKind Kind) const;
 
 public:
   // AttributesSetNode is uniqued, these should not be available.
@@ -233,6 +235,7 @@
   void operator delete(void *p) { ::operator delete(p); }
 
   static AttributeSetNode *get(LLVMContext &C, const AttrBuilder &B);
+  static AttributeSetNode *get(LLVMContext &C, const SmallAttrBuilder &B);
 
   static AttributeSetNode *get(LLVMContext &C, ArrayRef<Attribute> Attrs);
 
Index: llvm/lib/IR/Attributes.cpp
===================================================================
--- llvm/lib/IR/Attributes.cpp
+++ llvm/lib/IR/Attributes.cpp
@@ -600,6 +600,10 @@
   return AttributeSet(AttributeSetNode::get(C, B));
 }
 
+AttributeSet AttributeSet::get(LLVMContext &C, const SmallAttrBuilder &B) {
+  return AttributeSet(AttributeSetNode::get(C, B));
+}
+
 AttributeSet AttributeSet::get(LLVMContext &C, ArrayRef<Attribute> Attrs) {
   return AttributeSet(AttributeSetNode::get(C, Attrs));
 }
@@ -607,14 +611,14 @@
 AttributeSet AttributeSet::addAttribute(LLVMContext &C,
                                         Attribute::AttrKind Kind) const {
   if (hasAttribute(Kind)) return *this;
-  AttrBuilder B;
+  SmallAttrBuilder B(C);
   B.addAttribute(Kind);
   return addAttributes(C, AttributeSet::get(C, B));
 }
 
 AttributeSet AttributeSet::addAttribute(LLVMContext &C, StringRef Kind,
                                         StringRef Value) const {
-  AttrBuilder B;
+  SmallAttrBuilder B(C);
   B.addAttribute(Kind, Value);
   return addAttributes(C, AttributeSet::get(C, B));
 }
@@ -627,7 +631,7 @@
   if (!AS.hasAttributes())
     return *this;
 
-  AttrBuilder B(AS);
+  SmallAttrBuilder B(C, AS);
   for (const auto &I : *this)
     B.addAttribute(I);
 
@@ -637,16 +641,18 @@
 AttributeSet AttributeSet::removeAttribute(LLVMContext &C,
                                              Attribute::AttrKind Kind) const {
   if (!hasAttribute(Kind)) return *this;
-  AttrBuilder B(*this);
-  B.removeAttribute(Kind);
+  SmallAttrBuilder B(C, make_filter_range(*this, [Kind](Attribute Attr) {
+                       return !Attr.hasAttribute(Kind);
+                     }));
   return get(C, B);
 }
 
 AttributeSet AttributeSet::removeAttribute(LLVMContext &C,
-                                             StringRef Kind) const {
+                                           StringRef Kind) const {
   if (!hasAttribute(Kind)) return *this;
-  AttrBuilder B(*this);
-  B.removeAttribute(Kind);
+  SmallAttrBuilder B(C, make_filter_range(*this, [Kind](Attribute Attr) {
+                       return !Attr.hasAttribute(Kind);
+                     }));
   return get(C, B);
 }
 
@@ -661,6 +667,18 @@
   return get(C, B);
 }
 
+AttributeSet
+AttributeSet::removeAttributes(LLVMContext &C,
+                               const SmallAttrBuilder &Attrs) const {
+  SmallAttrBuilder B(C, *this);
+  auto AttrsPair = Attrs.uniquify();
+  for (Attribute A : AttrsPair.first)
+    B.removeEnumAttribute(A);
+  for (Attribute A : AttrsPair.second)
+    B.removeStringAttribute(A);
+  return get(C, B);
+}
+
 unsigned AttributeSet::getNumAttributes() const {
   return SetNode ? SetNode->getNumAttributes() : 0;
 }
@@ -779,6 +797,18 @@
   }
 }
 
+AttributeSetNode::AttributeSetNode(ArrayRef<Attribute> EAttrs,
+                                   ArrayRef<Attribute> SAttrs)
+    : NumAttrs(EAttrs.size() + SAttrs.size()) {
+  // There's memory after the node where we can store the entries in.
+  llvm::copy(SAttrs, llvm::copy(EAttrs, getTrailingObjects<Attribute>()));
+
+  for (const auto &A : SAttrs)
+    StringAttrs.insert({A.getKindAsString(), A});
+  for (const auto &A : EAttrs)
+    AvailableAttrs.addAttribute(A.getKindAsEnum());
+}
+
 AttributeSetNode *AttributeSetNode::get(LLVMContext &C,
                                         ArrayRef<Attribute> Attrs) {
   SmallVector<Attribute, 8> SortedAttrs(Attrs.begin(), Attrs.end());
@@ -841,6 +871,41 @@
   return getSorted(C, Attrs);
 }
 
+AttributeSetNode *AttributeSetNode::get(LLVMContext &C,
+                                        const SmallAttrBuilder &B) {
+  if (!B.hasAttributes())
+    return nullptr;
+
+  // Build a key to look up the existing attributes.
+  LLVMContextImpl *pImpl = C.pImpl;
+  FoldingSetNodeID ID;
+
+  auto AttrsPair = B.uniquify();
+
+  assert(llvm::is_sorted(AttrsPair.first) && "Expected sorted attributes!");
+  for (const auto &Attr : AttrsPair.first)
+    Attr.Profile(ID);
+  assert(llvm::is_sorted(AttrsPair.second) && "Expected sorted attributes!");
+  for (const auto &Attr : AttrsPair.second)
+    Attr.Profile(ID);
+
+  void *InsertPoint;
+  AttributeSetNode *PA =
+      pImpl->AttrsSetNodes.FindNodeOrInsertPos(ID, InsertPoint);
+
+  // If we didn't find any existing attributes of the same shape then create a
+  // new one and insert it.
+  if (!PA) {
+    // Coallocate entries after the AttributeSetNode itself.
+    void *Mem = ::operator new(totalSizeToAlloc<Attribute>(B.size()));
+    PA = new (Mem) AttributeSetNode(AttrsPair.first, AttrsPair.second);
+    pImpl->AttrsSetNodes.InsertNode(PA, InsertPoint);
+  }
+
+  // Return the AttributeSetNode that we found or created.
+  return PA;
+}
+
 bool AttributeSetNode::hasAttribute(StringRef Kind) const {
   return StringAttrs.count(Kind);
 }
@@ -1144,6 +1209,15 @@
   AttrSets[Index] = AttributeSet::get(C, B);
   return getImpl(C, AttrSets);
 }
+AttributeList AttributeList::get(LLVMContext &C, unsigned Index,
+                                 const SmallAttrBuilder &B) {
+  if (!B.hasAttributes())
+    return {};
+  Index = attrIdxToArrayIdx(Index);
+  SmallVector<AttributeSet, 8> AttrSets(Index + 1);
+  AttrSets[Index] = AttributeSet::get(C, B);
+  return getImpl(C, AttrSets);
+}
 
 AttributeList AttributeList::get(LLVMContext &C, unsigned Index,
                                  ArrayRef<Attribute::AttrKind> Kinds) {
@@ -1213,14 +1287,14 @@
 AttributeList AttributeList::addAttributeAtIndex(LLVMContext &C, unsigned Index,
                                                  StringRef Kind,
                                                  StringRef Value) const {
-  AttrBuilder B;
+  SmallAttrBuilder B(C);
   B.addAttribute(Kind, Value);
   return addAttributesAtIndex(C, Index, B);
 }
 
 AttributeList AttributeList::addAttributeAtIndex(LLVMContext &C, unsigned Index,
                                                  Attribute A) const {
-  AttrBuilder B;
+  SmallAttrBuilder B(C);
   B.addAttribute(A);
   return addAttributesAtIndex(C, Index, B);
 }
@@ -1259,6 +1333,20 @@
   return setAttributesAtIndex(C, Index, AttributeSet::get(C, Merged));
 }
 
+AttributeList
+AttributeList::addAttributesAtIndex(LLVMContext &C, unsigned Index,
+                                    const SmallAttrBuilder &B) const {
+  if (!B.hasAttributes())
+    return *this;
+
+  if (!pImpl)
+    return AttributeList::get(C, {{Index, AttributeSet::get(C, B)}});
+
+  SmallAttrBuilder Merged(C, getAttributes(Index));
+  Merged.merge(B);
+  return setAttributesAtIndex(C, Index, AttributeSet::get(C, Merged));
+}
+
 AttributeList AttributeList::addParamAttribute(LLVMContext &C,
                                                ArrayRef<unsigned> ArgNos,
                                                Attribute A) const {
@@ -1320,6 +1408,17 @@
   return setAttributesAtIndex(C, Index, NewAttrs);
 }
 
+AttributeList AttributeList::removeAttributesAtIndex(
+    LLVMContext &C, unsigned Index,
+    const SmallAttrBuilder &AttrsToRemove) const {
+  AttributeSet Attrs = getAttributes(Index);
+  AttributeSet NewAttrs = Attrs.removeAttributes(C, AttrsToRemove);
+  // If nothing was removed, return the original list.
+  if (Attrs == NewAttrs)
+    return *this;
+  return setAttributesAtIndex(C, Index, NewAttrs);
+}
+
 AttributeList
 AttributeList::removeAttributesAtIndex(LLVMContext &C,
                                        unsigned WithoutIndex) const {
@@ -1649,6 +1748,15 @@
   return unpackVScaleRangeArgs(getRawIntAttr(Attribute::VScaleRange)).second;
 }
 
+SmallAttrBuilder &SmallAttrBuilder::addAlignmentAttr(MaybeAlign Align) {
+  if (!Align)
+    return *this;
+
+  assert(*Align <= llvm::Value::MaximumAlignment && "Alignment too large.");
+  return addAttribute(
+      Attribute::get(Ctxt, Attribute::Alignment, Align->value()));
+}
+
 AttrBuilder &AttrBuilder::addAlignmentAttr(MaybeAlign Align) {
   if (!Align)
     return *this;
@@ -1666,11 +1774,25 @@
   return addRawIntAttr(Attribute::StackAlignment, Align->value());
 }
 
+SmallAttrBuilder &SmallAttrBuilder::addDereferenceableAttr(uint64_t Bytes) {
+  if (Bytes == 0)
+    return *this;
+  return addAttribute(Attribute::get(Ctxt, Attribute::Dereferenceable, Bytes));
+}
+
 AttrBuilder &AttrBuilder::addDereferenceableAttr(uint64_t Bytes) {
   if (Bytes == 0) return *this;
 
   return addRawIntAttr(Attribute::Dereferenceable, Bytes);
 }
+SmallAttrBuilder &
+SmallAttrBuilder::addDereferenceableOrNullAttr(uint64_t Bytes) {
+  if (Bytes == 0)
+    return *this;
+
+  return addAttribute(
+      Attribute::get(Ctxt, Attribute::DereferenceableOrNull, Bytes));
+}
 
 AttrBuilder &AttrBuilder::addDereferenceableOrNullAttr(uint64_t Bytes) {
   if (Bytes == 0)
@@ -1679,6 +1801,13 @@
   return addRawIntAttr(Attribute::DereferenceableOrNull, Bytes);
 }
 
+SmallAttrBuilder &
+SmallAttrBuilder::addAllocSizeAttr(unsigned ElemSize,
+                                   const Optional<unsigned> &NumElems) {
+  return addAttribute(Attribute::get(Ctxt, Attribute::AllocSize,
+                                     packAllocSizeArgs(ElemSize, NumElems)));
+}
+
 AttrBuilder &AttrBuilder::addAllocSizeAttr(unsigned ElemSize,
                                            const Optional<unsigned> &NumElems) {
   return addAllocSizeAttrFromRawRepr(packAllocSizeArgs(ElemSize, NumElems));
@@ -1716,11 +1845,17 @@
   TypeAttrs[*TypeIndex] = Ty;
   return *this;
 }
+SmallAttrBuilder &SmallAttrBuilder::addByValAttr(Type *Ty) {
+  return addAttribute(Attribute::get(Ctxt, Attribute::ByVal, Ty));
+}
 
 AttrBuilder &AttrBuilder::addByValAttr(Type *Ty) {
   return addTypeAttr(Attribute::ByVal, Ty);
 }
 
+SmallAttrBuilder &SmallAttrBuilder::addStructRetAttr(Type *Ty) {
+  return addAttribute(Attribute::get(Ctxt, Attribute::StructRet, Ty));
+}
 AttrBuilder &AttrBuilder::addStructRetAttr(Type *Ty) {
   return addTypeAttr(Attribute::StructRet, Ty);
 }
@@ -1737,6 +1872,20 @@
   return addTypeAttr(Attribute::InAlloca, Ty);
 }
 
+SmallAttrBuilder &SmallAttrBuilder::merge(const SmallAttrBuilder &B) {
+  {
+    auto Start = EnumAttrs.begin();
+    for (auto A : B.EnumAttrs)
+      Start = addEnumAttributeHelper(A, Start);
+  }
+  {
+    auto Start = StringAttrs.begin();
+    for (auto A : B.StringAttrs)
+      Start = addStringAttributeHelper(A, Start);
+  }
+
+  return *this;
+}
 AttrBuilder &AttrBuilder::merge(const AttrBuilder &B) {
   // FIXME: What if both have an int/type attribute, but they don't match?!
   for (unsigned Index = 0; Index < Attribute::NumIntAttrKinds; ++Index)
Index: llvm/lib/IR/Function.cpp
===================================================================
--- llvm/lib/IR/Function.cpp
+++ llvm/lib/IR/Function.cpp
@@ -549,6 +549,10 @@
   AttributeSets = AttributeSets.addFnAttributes(getContext(), Attrs);
 }
 
+void Function::addFnAttrs(const SmallAttrBuilder &Attrs) {
+  AttributeSets = AttributeSets.addFnAttributes(getContext(), Attrs);
+}
+
 void Function::addRetAttr(Attribute::AttrKind Kind) {
   AttributeSets = AttributeSets.addRetAttribute(getContext(), Kind);
 }
@@ -593,6 +597,10 @@
   AttributeSets = AttributeSets.removeFnAttributes(getContext(), Attrs);
 }
 
+void Function::removeFnAttrs(const SmallAttrBuilder &Attrs) {
+  AttributeSets = AttributeSets.removeFnAttributes(getContext(), Attrs);
+}
+
 void Function::removeRetAttr(Attribute::AttrKind Kind) {
   AttributeSets = AttributeSets.removeRetAttribute(getContext(), Kind);
 }
Index: llvm/lib/Transforms/Utils/InlineFunction.cpp
===================================================================
--- llvm/lib/Transforms/Utils/InlineFunction.cpp
+++ llvm/lib/Transforms/Utils/InlineFunction.cpp
@@ -1183,12 +1183,13 @@
       Begin->getIterator(), End->getIterator(), InlinerAttributeWindow + 1);
 }
 
-static AttrBuilder IdentifyValidAttributes(CallBase &CB) {
+static SmallAttrBuilder IdentifyValidAttributes(CallBase &CB) {
 
   AttrBuilder AB(CB.getAttributes(), AttributeList::ReturnIndex);
-  if (AB.empty())
-    return AB;
-  AttrBuilder Valid;
+  SmallAttrBuilder Valid(CB.getContext());
+  if (AB.empty()) {
+    return Valid;
+  }
   // Only allow these white listed attributes to be propagated back to the
   // callee. This is because other attributes may only be valid on the call
   // itself, i.e. attributes such as signext and zeroext.
@@ -1207,7 +1208,7 @@
   if (!UpdateReturnAttributes)
     return;
 
-  AttrBuilder Valid = IdentifyValidAttributes(CB);
+  SmallAttrBuilder Valid = IdentifyValidAttributes(CB);
   if (Valid.empty())
     return;
   auto *CalledFunction = CB.getCalledFunction();
@@ -1252,6 +1253,7 @@
     // existing attribute value (i.e. attributes such as dereferenceable,
     // dereferenceable_or_null etc). See AttrBuilder::merge for more details.
     AttributeList AL = NewRetVal->getAttributes();
+
     AttributeList NewAL = AL.addRetAttributes(Context, Valid);
     NewRetVal->setAttributes(NewAL);
   }
Index: llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp
===================================================================
--- llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp
+++ llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp
@@ -602,7 +602,8 @@
     Align MemSetAlign =
         CI->getAttributes().getParamAttrs(0).getAlignment().valueOrOne();
     CallInst *NewCI = B.CreateMemSet(Dst, B.getInt8('\0'), Size, MemSetAlign);
-    AttrBuilder ArgAttrs(CI->getAttributes().getParamAttrs(0));
+    SmallAttrBuilder ArgAttrs(CI->getContext(),
+                              CI->getAttributes().getParamAttrs(0));
     NewCI->setAttributes(NewCI->getAttributes().addParamAttributes(
         CI->getContext(), 0, ArgAttrs));
     copyFlags(*CI, NewCI);