Provide SmallAttrBuilder as a lightweight alternative to AttrBuilder

[serge-sans-paille]

Summary

This class can only add / remove Attributes, but it does it relatively
efficiently compared to existing AttrBuilder, providing a consistent compile-time
speedup according to https://llvm-compile-time-tracker.com/

Internally it maintains two SmallVector of sorted Attributes, which turns out to
be more efficient than temporary hashmap and bitfields as used by AttrBuilder.

[serge-sans-paille]

My plan mid-term plan would be to rename AttrBuilder into AttrQuery at some point, and use SmallAttrBuilder as the actual AttrBuilder in most places.

[serge-sans-paille]

Leverage the fact that AttributeSet nodes are already sorted

[nikic]

I like the general direction. A possible reframing would be SmallAttrBuilder -> MutableAttributeSet. I think my main question here would be in which contexts we still use / want to use the old AttrBuilder?

llvm/include/llvm/IR/Attributes.h

974

Just wondering if storing both in one vector would make sense? Would allow reusing the normal comparison on attributes and generally simplify the code. Or is that noticeably less efficient?

1125

What is uniquify() supposed to mean in this context?

[serge-sans-paille]

Actual benchmarks: https://llvm-compile-time-tracker.com/compare.php?from=7d97678df7f514c14b7611447dad02e9cc5168c9&to=f39a39e09e8f4f3b7dc94e4d23d9acfbf36ab2e5&stat=instructions

[serge-sans-paille]

llvm/include/llvm/IR/Attributes.h

974

Yeah, a single container is less efficient: It makes comparison more costly (as you need to check which kind of attribute we're dealing with each time), having two containers also reduces the cost of insert / remove (for low number of elements, we have higher chance to hit the container back). The lower bound alos typically takes less steps when the nature of attribute is known at compile time, which happens a lot.

1125

Woops that's a leftover of a previous attempt when I was not trying to maintain the sorted invariant, I'll rename this.

[rnk]

I would really prefer to avoid adding a new variant of AttrBuilder. What is the main blocker to making AttrBuilder more efficient? It just needs an LLVMContext, right? Would that be feasible instead? Most AttrBuilders are constructed from existing AttributeLists, which have a context.

Internally it maintains two SmallVector of sorted Attributes, which turns out to
be more efficient than temporary hashmap and bitfields as used by AttrBuilder.

Surely the bitset is more efficient than a vector of attributes. I think it's the std::map<SmallString, SmallString> that's slow. I think replacing that with a sorted vector of hashed string attributes would be just as efficient.

[aeubanks]

I agree that we really should only have one attribute builder class.

A SmallVector does seem nicer than having a static array the size of all possible attributes. We should avoid creating copies of AttributeLists/Sets into AttrBuilders and just have AttrBuilder be a list of attribute diffs, basically what you have as SmallAttrBuilder, although I'm not sure if we also want to handle a list of attributes we want to *remove* from an AttributeSet in SmallAttrBuilder as well?

As for querying the AttrBuilder for attributes it contains, IMO we shouldn't need to in most cases, typically we can directly query the AttributeList/Set directly. https://reviews.llvm.org/D115819 shows that a bunch of the query methods in AttrBuilder are easily removed. LLParser::validateEndOfModule() is the last major user of AttributeList functionality we may not want to support but it seems fixable.

[serge-sans-paille]

Obsoleted by https://reviews.llvm.org/D116599

clang/include/clang/CodeGen/CodeGenABITypes.h

 
 #include "clang/AST/CanonicalType.h"
 #include "clang/AST/Type.h"
 #include "clang/Basic/ABI.h"
 #include "clang/CodeGen/CGFunctionInfo.h"
 #include "llvm/IR/BasicBlock.h"
 
 namespace llvm {
-class AttrBuilder;
+class SmallAttrBuilder;
 class Constant;
 class DataLayout;
 class Module;
 class Function;
 class FunctionType;
 class Type;
 }
 

 /// haven't already been added to the builder.  It won't intentionally
 /// displace any existing attributes, but it also won't check to avoid
 /// overwriting them.  Callers should generally apply customizations after
 /// making this call.
 ///
 /// 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`
 /// calling convention, returns void, and takes a single argument that is a
 /// pointer to the address of the struct.
 llvm::Function *getNonTrivialCStructDefaultConstructor(CodeGenModule &GCM,
                                                        CharUnits DstAlignment,
                                                        bool IsVolatile,

clang/lib/CodeGen/CGCall.cpp

llvm::Type *CodeGenTypes::GetFunctionTypeForVTable(GlobalDecl GD) {
   const FunctionProtoType *FPT = MD->getType()->getAs<FunctionProtoType>();
 
   if (!isFuncTypeConvertible(FPT))
     return llvm::StructType::get(getLLVMContext());
 
   return GetFunctionType(GD);
 }
 
-static void AddAttributesFromFunctionProtoType(ASTContext &Ctx,
-                                               llvm::AttrBuilder &FuncAttrs,
-                                               const FunctionProtoType *FPT) {
+static void
+AddAttributesFromFunctionProtoType(ASTContext &Ctx,
+                                   llvm::SmallAttrBuilder &FuncAttrs,
   if (!FPT)
     return;
 
   if (!isUnresolvedExceptionSpec(FPT->getExceptionSpecType()) &&
       FPT->isNothrow())
     FuncAttrs.addAttribute(llvm::Attribute::NoUnwind);
 }
 
-static void AddAttributesFromAssumes(llvm::AttrBuilder &FuncAttrs,
+static void AddAttributesFromAssumes(llvm::SmallAttrBuilder &FuncAttrs,
                                      const Decl *Callee) {
   if (!Callee)
     return;
 
   SmallVector<StringRef, 4> Attrs;
 
   for (const AssumptionAttr *AA : Callee->specific_attrs<AssumptionAttr>())
     AA->getAssumption().split(Attrs, ",");
bool CodeGenModule::MayDropFunctionReturn(const ASTContext &Context,
   if (const RecordType *RT =
           ReturnType.getCanonicalType()->getAs<RecordType>()) {
     if (const auto *ClassDecl = dyn_cast<CXXRecordDecl>(RT->getDecl()))
       return ClassDecl->hasTrivialDestructor();
   }
   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)
       FuncAttrs.addAttribute(llvm::Attribute::OptimizeForSize);
     if (CodeGenOpts.OptimizeSize == 2)
       FuncAttrs.addAttribute(llvm::Attribute::MinSize);
   }
 
void CodeGenModule::getDefaultFunctionAttributes(
   for (StringRef Attr : CodeGenOpts.DefaultFunctionAttrs) {
     StringRef Var, Value;
     std::tie(Var, Value) = Attr.split('=');
     FuncAttrs.addAttribute(Var, Value);
   }
 }
 
 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?
   F.addFnAttrs(FuncAttrs);
 }
 
 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) {
     SmallString<32> AttributeName;
     AttributeName += "no-builtin-";
     AttributeName += BuiltinName;
     FuncAttrs.addAttribute(AttributeName);
   };

 ///     added here rather than getDefaultFunctionAttributes.
 ///
 void CodeGenModule::ConstructAttributeList(StringRef Name,
                                            const CGFunctionInfo &FI,
                                            CGCalleeInfo CalleeInfo,
                                            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.
   CallingConv = FI.getEffectiveCallingConvention();
   if (FI.isNoReturn())
     FuncAttrs.addAttribute(llvm::Attribute::NoReturn);
   if (FI.isCmseNSCall())
     FuncAttrs.addAttribute("cmse_nonsecure_call");

clang/lib/CodeGen/CodeGenABITypes.cpp

 #include "CodeGenModule.h"
 #include "clang/CodeGen/CGFunctionInfo.h"
 #include "clang/Lex/HeaderSearchOptions.h"
 #include "clang/Lex/PreprocessorOptions.h"
 
 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);
 }
 
 const CGFunctionInfo &
 CodeGen::arrangeObjCMessageSendSignature(CodeGenModule &CGM,
                                          const ObjCMethodDecl *MD,
                                          QualType receiverType) {
   return CGM.getTypes().arrangeObjCMessageSendSignature(MD, receiverType);

clang/lib/CodeGen/CodeGenModule.h

public:
   /// With the exception of fast-math attrs, this will only make the attributes
   /// on the function more conservative.  But it's unsafe to call this on a
   /// function which relies on particular fast-math attributes for correctness.
   /// It's up to you to ensure that this is safe.
   void addDefaultFunctionDefinitionAttributes(llvm::Function &F);
 
   /// 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);
 
   void EmitTentativeDefinition(const VarDecl *D);
 
   void EmitExternalDeclaration(const VarDecl *D);
 
private:
   void UpdateMultiVersionNames(GlobalDecl GD, const FunctionDecl *FD);
 
   llvm::Constant *
   GetOrCreateLLVMGlobal(StringRef MangledName, llvm::Type *Ty, LangAS AddrSpace,
                         const VarDecl *D,
                         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.
   void SetFunctionAttributes(GlobalDecl GD, llvm::Function *F,
                              bool IsIncompleteFunction, bool IsThunk);
 
   void EmitGlobalDefinition(GlobalDecl D, llvm::GlobalValue *GV = nullptr);
 
private:
   /// function.
   void SimplifyPersonality();
 
   /// Helper function for ConstructAttributeList and
   /// addDefaultFunctionDefinitionAttributes.  Builds a set of function
   /// 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);
 };
 
 }  // end namespace CodeGen
 }  // end namespace clang
 
 #endif // LLVM_CLANG_LIB_CODEGEN_CODEGENMODULE_H

clang/lib/CodeGen/CodeGenModule.cpp

for (const CXXBaseSpecifier &B : RD->bases())
       CollectMostBases(B.getType()->getAsCXXRecordDecl());
   };
   CollectMostBases(RD);
   return MostBases.takeVector();
 }
 
 void CodeGenModule::SetLLVMFunctionAttributesForDefinition(const Decl *D,
                                                            llvm::Function *F) {
-  llvm::AttrBuilder B;
+  llvm::SmallAttrBuilder B(getLLVMContext());
 
   if (CodeGenOpts.UnwindTables)
     B.addAttribute(llvm::Attribute::UWTable);
 
   if (CodeGenOpts.StackClashProtector)
     B.addAttribute("probe-stack", "inline-asm");
 
   if (!hasUnwindExceptions(LangOpts))
for (const CXXRecordDecl *Base : getMostBaseClasses(MD->getParent())) {
       F->addTypeMetadata(0, Id);
     }
   }
 }
 
 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");
   }
 }
 
 void CodeGenModule::SetCommonAttributes(GlobalDecl GD, llvm::GlobalValue *GV) {
   const Decl *D = GD.getDecl();
   if (isa_and_nonnull<NamedDecl>(D))
     setGVProperties(GV, GD);
   else
     GV->setVisibility(llvm::GlobalValue::DefaultVisibility);
 
   if (D && D->hasAttr<UsedAttr>())
     addUsedOrCompilerUsedGlobal(GV);
 
   if (CodeGenOpts.KeepStaticConsts && D && isa<VarDecl>(D)) {
     const auto *VD = cast<VarDecl>(D);
     if (VD->getType().isConstQualified() &&
         VD->getStorageDuration() == SD_Static)
       addUsedOrCompilerUsedGlobal(GV);
   }
 }
 
 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.
   StringRef TargetCPU = getTarget().getTargetOpts().CPU;
   StringRef TuneCPU = getTarget().getTargetOpts().TuneCPU;
   std::vector<std::string> Features;
   const auto *FD = dyn_cast_or_null<FunctionDecl>(GD.getDecl());
   FD = FD ? FD->getMostRecentDecl() : FD;
if (D) {
 
     if (auto *F = dyn_cast<llvm::Function>(GO)) {
       if (D->hasAttr<RetainAttr>())
         addUsedGlobal(F);
       if (auto *SA = D->getAttr<PragmaClangTextSectionAttr>())
         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");
         F->removeFnAttrs(RemoveAttrs);
         F->addFnAttrs(Attrs);
       }
     }
 
llvm::Constant *BC = llvm::ConstantExpr::getBitCast(
         F, Entry->getValueType()->getPointerTo());
     addGlobalValReplacement(Entry, BC);
   }
 
   assert(F->getName() == MangledName && "name was uniqued!");
   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);
   }
 
   if (!DontDefer) {
     // All MSVC dtors other than the base dtor are linkonce_odr and delegate to
     // each other bottoming out with the base dtor.  Therefore we emit non-base
     // dtors on usage, even if there is no dtor definition in the TU.
     if (D && isa<CXXDestructorDecl>(D) &&

llvm/include/llvm/IR/Attributes.h

 #include <cstdint>
 #include <map>
 #include <string>
 #include <utility>
 
 namespace llvm {
 
 class AttrBuilder;
+class SmallAttrBuilder;
 class AttributeImpl;
 class AttributeListImpl;
 class AttributeSetNode;
 class FoldingSetNodeID;
 class Function;
 class LLVMContext;
 class Type;
 

 
 public:
   /// AttributeSet is a trivially copyable value type.
   AttributeSet() = default;
   AttributeSet(const AttributeSet &) = default;
   ~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; }
   bool operator!=(const AttributeSet &O) const { return !(*this == O); }
 
   /// Add an argument attribute. Returns a new set because attribute sets are
   /// immutable.
   LLVM_NODISCARD AttributeSet addAttribute(LLVMContext &C,
public:
   /// attribute sets are immutable.
   LLVM_NODISCARD AttributeSet removeAttribute(LLVMContext &C,
                                               StringRef Kind) const;
 
   /// Remove the specified attributes from this set. Returns a new set because
   /// 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;
 
   /// Return true if attributes exists in this set.
   bool hasAttributes() const { return SetNode != nullptr; }
 
   /// Return true if the attribute exists in this set.
static AttributeList get(LLVMContext &C, unsigned Index,
                            ArrayRef<Attribute::AttrKind> Kinds);
   static AttributeList get(LLVMContext &C, unsigned Index,
                            ArrayRef<Attribute::AttrKind> Kinds,
                            ArrayRef<uint64_t> Values);
   static AttributeList get(LLVMContext &C, unsigned Index,
                            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.
   /// Returns a new list because attribute lists are immutable.
   LLVM_NODISCARD AttributeList addAttributeAtIndex(
       LLVMContext &C, unsigned Index, Attribute::AttrKind Kind) const;
 
   /// Add an attribute to the attribute set at the given index.
   /// Returns a new list because attribute lists are immutable.
   LLVM_NODISCARD AttributeList
   addAttributeAtIndex(LLVMContext &C, unsigned Index, StringRef Kind,
                       StringRef Value = StringRef()) const;
 
   /// Add an attribute to the attribute set at the given index.
   /// Returns a new list because attribute lists are immutable.
   LLVM_NODISCARD AttributeList addAttributeAtIndex(LLVMContext &C,
                                                    unsigned Index,
                                                    Attribute A) const;
 
   /// Add attributes to the attribute set at the given index.
   /// Returns a new list because attribute lists are immutable.
   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.
   LLVM_NODISCARD AttributeList addFnAttribute(LLVMContext &C,
                                               Attribute::AttrKind Kind) const {
     return addAttributeAtIndex(C, FunctionIndex, Kind);
   }
 
public:
   }
 
   /// Add function attribute to the list. Returns a new list because
   /// attribute lists are immutable.
   LLVM_NODISCARD AttributeList addFnAttributes(LLVMContext &C,
                                                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.
   LLVM_NODISCARD AttributeList addRetAttribute(LLVMContext &C,
                                                Attribute::AttrKind Kind) const {
     return addAttributeAtIndex(C, ReturnIndex, Kind);
   }
 
   /// Add a return value attribute to the list. Returns a new list because
   /// attribute lists are immutable.
   LLVM_NODISCARD AttributeList addRetAttribute(LLVMContext &C,
                                                Attribute Attr) const {
     return addAttributeAtIndex(C, ReturnIndex, Attr);
   }
 
   /// Add a return value attribute to the list. Returns a new list because
   /// attribute lists are immutable.
   LLVM_NODISCARD AttributeList addRetAttributes(LLVMContext &C,
                                                 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.
   LLVM_NODISCARD AttributeList addParamAttribute(
       LLVMContext &C, unsigned ArgNo, Attribute::AttrKind Kind) const {
     return addAttributeAtIndex(C, ArgNo + FirstArgIndex, Kind);
   }
 
public:
 
   /// Add an argument attribute to the list. Returns a new list because
   /// attribute lists are immutable.
   LLVM_NODISCARD AttributeList addParamAttributes(LLVMContext &C,
                                                   unsigned ArgNo,
                                                   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.
   LLVM_NODISCARD AttributeList removeAttributeAtIndex(
       LLVMContext &C, unsigned Index, Attribute::AttrKind Kind) const;
 
   /// Remove the specified attribute at the specified index from this
   /// attribute list. Returns a new list because attribute lists are immutable.
   LLVM_NODISCARD AttributeList removeAttributeAtIndex(LLVMContext &C,
                                                       unsigned Index,
                                                       StringRef Kind) const;
   LLVM_NODISCARD AttributeList removeAttribute(LLVMContext &C, unsigned Index,
                                                StringRef Kind) const {
     return removeAttributeAtIndex(C, Index, Kind);
   }
 
   /// Remove the specified attributes at the specified index from this
   /// 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.
   LLVM_NODISCARD AttributeList removeAttributesAtIndex(LLVMContext &C,
                                                        unsigned Index) const;
 
   /// Remove the specified attribute at the function index from this
   /// attribute list. Returns a new list because attribute lists are immutable.
public:
   }
 
   /// Remove the specified attribute at the function index from this
   /// attribute list. Returns a new list because attribute lists are immutable.
   LLVM_NODISCARD AttributeList
   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.
   LLVM_NODISCARD AttributeList removeFnAttributes(LLVMContext &C) const {
     return removeAttributesAtIndex(C, FunctionIndex);
   }
 
   /// Remove the specified attribute at the return value index from this
public:
   }
 
   /// Remove the specified attribute at the return value index from this
   /// attribute list. Returns a new list because attribute lists are immutable.
   LLVM_NODISCARD AttributeList
   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.
   LLVM_NODISCARD AttributeList removeParamAttribute(
       LLVMContext &C, unsigned ArgNo, Attribute::AttrKind Kind) const {
     return removeAttributeAtIndex(C, ArgNo + FirstArgIndex, Kind);
   }
 
   /// Remove the specified attribute at the specified arg index from this
   /// attribute list. Returns a new list because attribute lists are immutable.
   LLVM_NODISCARD AttributeList removeParamAttribute(LLVMContext &C,
                                                     unsigned ArgNo,
                                                     StringRef Kind) const {
     return removeAttributeAtIndex(C, ArgNo + FirstArgIndex, Kind);
   }
 
   /// Remove the specified attribute at the specified arg index from this
   /// attribute list. Returns a new list because attribute lists are immutable.
   LLVM_NODISCARD AttributeList removeParamAttributes(
       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.
   LLVM_NODISCARD AttributeList removeParamAttributes(LLVMContext &C,
                                                      unsigned ArgNo) const {
     return removeAttributesAtIndex(C, ArgNo + FirstArgIndex);
   }
 
template <> struct DenseMapInfo<AttributeList, void> {
 
   static bool isEqual(AttributeList LHS, AttributeList RHS) {
     return LHS == RHS;
   }
 };
 
 //===----------------------------------------------------------------------===//
 /// \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;
+
+  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:
+  using iterator = typename SmallVector<Attribute>::iterator;
+
+  SmallAttrBuilder(LLVMContext &Ctxt) : Ctxt(Ctxt) {}
+  SmallAttrBuilder(LLVMContext &Ctxt, AttributeList AL, unsigned Idx)
+      : SmallAttrBuilder(Ctxt, AL.getAttributes(Idx)) {}
+  template <class Range>
+  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
 /// equality, presence of attributes, etc.
 class AttrBuilder {
   std::bitset<Attribute::EndAttrKinds> Attrs;
   std::map<SmallString<32>, SmallString<32>, std::less<>> TargetDepAttrs;
   std::array<uint64_t, Attribute::NumIntAttrKinds> IntAttrs = {};

llvm/include/llvm/IR/Function.h

public:
   /// Add function attributes to this function.
   void addFnAttr(StringRef Kind, StringRef Val = StringRef());
 
   /// Add function attributes to this function.
   void addFnAttr(Attribute Attr);
 
   /// 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);
 
   /// Add return value attributes to this function.
   void addRetAttr(Attribute Attr);
 
   /// Add return value attributes to this function.
public:
 
   /// Remove function attributes from this function.
   void removeFnAttr(Attribute::AttrKind Kind);
 
   /// Remove function attribute from this function.
   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);
 
   /// removes the attribute from the return value list of attributes.
   void removeRetAttr(StringRef Kind);
 
   /// removes the attributes from the return value list of attributes.

llvm/lib/IR/AttributeImpl.h

class AttributeSetNode final
   friend TrailingObjects;
 
   unsigned NumAttrs; ///< Number of attributes in this node.
   AttributeBitSet AvailableAttrs; ///< Available enum attributes.
 
   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.
   AttributeSetNode(const AttributeSetNode &) = delete;
   AttributeSetNode &operator=(const AttributeSetNode &) = delete;
 
   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);
 
   /// Return the number of attributes this AttributeList contains.
   unsigned getNumAttributes() const { return NumAttrs; }
 
   bool hasAttribute(Attribute::AttrKind Kind) const {
     return AvailableAttrs.hasAttribute(Kind);

llvm/lib/IR/Attributes.cpp

 //===----------------------------------------------------------------------===//
 // AttributeSet Definition
 //===----------------------------------------------------------------------===//
 
 AttributeSet AttributeSet::get(LLVMContext &C, const AttrBuilder &B) {
   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));
 }
 
 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));
 }
 
 AttributeSet AttributeSet::addAttributes(LLVMContext &C,
                                          const AttributeSet AS) const {
   if (!hasAttributes())
     return AS;
 
   if (!AS.hasAttributes())
     return *this;
 
-  AttrBuilder B(AS);
+  SmallAttrBuilder B(C, AS);
   for (const auto &I : *this)
     B.addAttribute(I);
 
  return get(C, B);
 }
 
 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 {
   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::removeAttributes(LLVMContext &C,
                                             const AttrBuilder &Attrs) const {
   AttrBuilder B(*this);
   // If there is nothing to remove, directly return the original set.
   if (!B.overlaps(Attrs))
     return *this;
 
   B.remove(Attrs);
   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;
 }
 
 bool AttributeSet::hasAttribute(Attribute::AttrKind Kind) const {
   return SetNode ? SetNode->hasAttribute(Kind) : false;
 }
 
AttributeSetNode::AttributeSetNode(ArrayRef<Attribute> Attrs)
   for (const auto &I : *this) {
     if (I.isStringAttribute())
       StringAttrs.insert({ I.getKindAsString(), I });
     else
       AvailableAttrs.addAttribute(I.getKindAsEnum());
   }
 }
 
+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());
   llvm::sort(SortedAttrs);
   return getSorted(C, SortedAttrs);
 }
 
 AttributeSetNode *AttributeSetNode::getSorted(LLVMContext &C,
AttributeSetNode *AttributeSetNode::get(LLVMContext &C, const AttrBuilder &B) {
 
   // Add target-dependent (string) attributes.
   for (const auto &TDA : B.td_attrs())
     Attrs.emplace_back(Attribute::get(C, TDA.first, TDA.second));
 
   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);
 }
 
 Optional<Attribute>
 AttributeSetNode::findEnumAttribute(Attribute::AttrKind Kind) const {
   // Do a quick presence check.
   if (!hasAttribute(Kind))
AttributeList AttributeList::get(LLVMContext &C, unsigned Index,
                                  const AttrBuilder &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,
+                                 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) {
   SmallVector<std::pair<unsigned, Attribute>, 8> Attrs;
   for (const auto K : Kinds)
     Attrs.emplace_back(Index, Attribute::get(C, K));
   return get(C, Attrs);
 }
AttributeList::addAttributeAtIndex(LLVMContext &C, unsigned Index,
   SmallVector<Attribute, 8> NewAttrs(Attrs.begin(), Attrs.end());
   NewAttrs.push_back(Attribute::get(C, Kind));
   return setAttributesAtIndex(C, Index, AttributeSet::get(C, NewAttrs));
 }
 
 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);
 }
 
 AttributeList AttributeList::setAttributesAtIndex(LLVMContext &C,
                                                   unsigned Index,
                                                   AttributeSet Attrs) const {
   Index = attrIdxToArrayIdx(Index);
assert((!OldAlign || !NewAlign || OldAlign == NewAlign) &&
          "Attempt to change alignment!");
 #endif
 
   AttrBuilder Merged(getAttributes(Index));
   Merged.merge(B);
   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 {
   assert(llvm::is_sorted(ArgNos));
 
   SmallVector<AttributeSet, 4> AttrSets(this->begin(), this->end());
   unsigned MaxIndex = attrIdxToArrayIdx(ArgNos.back() + FirstArgIndex);
   if (MaxIndex >= AttrSets.size())
AttributeList::removeAttributesAtIndex(LLVMContext &C, unsigned Index,
   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 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 {
   if (!pImpl)
     return {};
   WithoutIndex = attrIdxToArrayIdx(WithoutIndex);
   if (WithoutIndex >= getNumAttrSets())
     return *this;

 unsigned AttrBuilder::getVScaleRangeMin() const {
   return unpackVScaleRangeArgs(getRawIntAttr(Attribute::VScaleRange)).first;
 }
 
 Optional<unsigned> AttrBuilder::getVScaleRangeMax() const {
   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;
 
   assert(*Align <= llvm::Value::MaximumAlignment && "Alignment too large.");
   return addRawIntAttr(Attribute::Alignment, Align->value());
 }
 
 AttrBuilder &AttrBuilder::addStackAlignmentAttr(MaybeAlign Align) {
   // Default alignment, allow the target to define how to align it.
   if (!Align)
     return *this;
 
   assert(*Align <= 0x100 && "Alignment too large.");
   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)
     return *this;
 
   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));
 }
 
 AttrBuilder &AttrBuilder::addAllocSizeAttrFromRawRepr(uint64_t RawArgs) {
   // (0, 0) is our "not present" value, so we need to check for it here.
   assert(RawArgs && "Invalid allocsize arguments -- given allocsize(0, 0)");

 
 AttrBuilder &AttrBuilder::addTypeAttr(Attribute::AttrKind Kind, Type *Ty) {
   Optional<unsigned> TypeIndex = kindToTypeIndex(Kind);
   assert(TypeIndex && "Not a type attribute");
   Attrs[Kind] = true;
   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);
 }
 
 AttrBuilder &AttrBuilder::addByRefAttr(Type *Ty) {
   return addTypeAttr(Attribute::ByRef, Ty);
 }
 
 AttrBuilder &AttrBuilder::addPreallocatedAttr(Type *Ty) {
   return addTypeAttr(Attribute::Preallocated, Ty);
 }
 
 AttrBuilder &AttrBuilder::addInAllocaAttr(Type *Ty) {
   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)
     if (!IntAttrs[Index])
       IntAttrs[Index] = B.IntAttrs[Index];
 
   for (unsigned Index = 0; Index < Attribute::NumTypeAttrKinds; ++Index)
     if (!TypeAttrs[Index])

llvm/lib/IR/Function.cpp

 void Function::addFnAttr(Attribute Attr) {
   AttributeSets = AttributeSets.addFnAttribute(getContext(), Attr);
 }
 
 void Function::addFnAttrs(const AttrBuilder &Attrs) {
   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);
 }
 
 void Function::addRetAttr(Attribute Attr) {
   AttributeSets = AttributeSets.addRetAttribute(getContext(), Attr);
 }
 

 void Function::removeFnAttr(StringRef Kind) {
   AttributeSets = AttributeSets.removeFnAttribute(getContext(), Kind);
 }
 
 void Function::removeFnAttrs(const AttrBuilder &Attrs) {
   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);
 }
 
 void Function::removeRetAttr(StringRef Kind) {
   AttributeSets = AttributeSets.removeRetAttribute(getContext(), Kind);
 }
 

llvm/lib/Transforms/Utils/InlineFunction.cpp

static bool MayContainThrowingOrExitingCall(Instruction *Begin,
                                             Instruction *End) {
 
   assert(Begin->getParent() == End->getParent() &&
          "Expected to be in same basic block!");
   return !llvm::isGuaranteedToTransferExecutionToSuccessor(
       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.
   if (auto DerefBytes = AB.getDereferenceableBytes())
     Valid.addDereferenceableAttr(DerefBytes);
   if (auto DerefOrNullBytes = AB.getDereferenceableOrNullBytes())
     Valid.addDereferenceableOrNullAttr(DerefOrNullBytes);
   if (AB.contains(Attribute::NoAlias))
     Valid.addAttribute(Attribute::NoAlias);
   if (AB.contains(Attribute::NonNull))
     Valid.addAttribute(Attribute::NonNull);
   return Valid;
 }
 
 static void AddReturnAttributes(CallBase &CB, ValueToValueMapTy &VMap) {
   if (!UpdateReturnAttributes)
     return;
 
-  AttrBuilder Valid = IdentifyValidAttributes(CB);
+  SmallAttrBuilder Valid = IdentifyValidAttributes(CB);
   if (Valid.empty())
     return;
   auto *CalledFunction = CB.getCalledFunction();
   auto &Context = CalledFunction->getContext();
 
   for (auto &BB : *CalledFunction) {
     auto *RI = dyn_cast<ReturnInst>(BB.getTerminator());
     if (!RI || !isa<CallBase>(RI->getOperand(0)))
if (RI->getParent() != RetVal->getParent() ||
       continue;
     // Add to the existing attributes of NewRetVal, i.e. the cloned call
     // instruction.
     // NB! When we have the same attribute already existing on NewRetVal, but
     // with a differing value, the AttributeList's merge API honours the already
     // 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);
   }
 }
 
 /// If the inlined function has non-byval align arguments, then
 /// add @llvm.assume-based alignment assumptions to preserve this information.
 static void AddAlignmentAssumptions(CallBase &CB, InlineFunctionInfo &IFI) {

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp

if (SrcLen) {
     return nullptr;
   }
 
   if (SrcLen == 0) {
     // strncpy(x, "", y) -> memset(x, '\0', y)
     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);
     return Dst;
   }
 
   // strncpy(a, "a", 4) - > memcpy(a, "a\0\0\0", 4)
   if (Len > SrcLen + 1) {