[AttrBuilder] Change storage to sorted vector

[nikic]

Summary

This follows up on the work in D116599, which changed AttrBuilder to store string attributes as SmallVector<Attribute>. This patch changes the implementation to store *all* attributes as a sorted vector.

Doing this both makes the implementation simpler, and gives a sizable compile-time improvement: https://llvm-compile-time-tracker.com/compare.php?from=e7bfe83773c000da13a8e2495b6230e846a322c4&to=3668e3d5a34dd713615dce96a5eb7de21b295772&stat=instructions

Depends on D117552.

[aeubanks]

llvm/lib/IR/Attributes.cpp

1526–1528

perhaps a note about string attrs being considered greater than enum attrs would be nice

1704–1705

no longer relevant

1707

could make this O(n) since they're both sorted, maybe a FIXME

[serge-sans-paille]

llvm/lib/IR/Attributes.cpp

1520

could be an assert?

llvm/include/llvm/IR/Attributes.h

 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Config/llvm-config.h"
 #include "llvm/Support/Alignment.h"
 #include "llvm/Support/PointerLikeTypeTraits.h"
 #include <bitset>
 #include <cassert>
 #include <cstdint>
-#include <map>
 #include <set>
 #include <string>
 #include <utility>
 
 namespace llvm {
 
 class AttrBuilder;
 class AttributeMask;
bool contains(Attribute::AttrKind A) const {
     assert((unsigned)A < Attribute::EndAttrKinds && "Attribute out of range!");
     return Attrs[A];
   }
 
   /// Return true if the builder has the specified target-dependent
   /// attribute.
   bool contains(StringRef A) const { return TargetDepAttrs.count(A); }
 
-  using td_const_iterator = decltype(TargetDepAttrs)::const_iterator;
-  using td_const_range = iterator_range<td_const_iterator>;
-  td_const_range td_attrs() const {
-    return {TargetDepAttrs.begin(), TargetDepAttrs.end()};
+  /// Return true if the mask contains the specified attribute.
+  bool contains(Attribute A) const {
+    if (A.isStringAttribute())
+      return contains(A.getKindAsString());
+    return contains(A.getKindAsEnum());
   }
-  auto const &attrs() const { return Attrs; }
 };
 
 //===----------------------------------------------------------------------===//
 /// \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 {
   LLVMContext &Ctx;
-  std::bitset<Attribute::EndAttrKinds> Attrs;
-  SmallVector<Attribute, 8> TargetDepAttrs;
-  std::array<uint64_t, Attribute::NumIntAttrKinds> IntAttrs = {};
-  std::array<Type *, Attribute::NumTypeAttrKinds> TypeAttrs = {};
-
-  Optional<unsigned> kindToIntIndex(Attribute::AttrKind Kind) const;
-  Optional<unsigned> kindToTypeIndex(Attribute::AttrKind Kind) const;
+  SmallVector<Attribute, 8> Attrs;
 
 public:
   AttrBuilder(LLVMContext &Ctx) : Ctx(Ctx) {}
   AttrBuilder(const AttrBuilder &) = delete;
   AttrBuilder(AttrBuilder &&) = default;
 
   AttrBuilder(LLVMContext &Ctx, const Attribute &A) : Ctx(Ctx) {
     addAttribute(A);
   }
 
   AttrBuilder(LLVMContext &Ctx, AttributeSet AS);
 
   void clear();
 
   /// Add an attribute to the builder.
-  AttrBuilder &addAttribute(Attribute::AttrKind Val) {
-    assert((unsigned)Val < Attribute::EndAttrKinds &&
-           "Attribute out of range!");
-    assert(Attribute::isEnumAttrKind(Val) &&
-           "Adding integer/type attribute without an argument!");
-    Attrs[Val] = true;
-    return *this;
-  }
+  AttrBuilder &addAttribute(Attribute::AttrKind Val);
 
   /// Add the Attribute object to the builder.
   AttrBuilder &addAttribute(Attribute A);
 
   /// Add the target-dependent attribute to the builder.
   AttrBuilder &addAttribute(StringRef A, StringRef V = StringRef());
 
   /// Remove an attribute from the builder.
public:
   /// Remove the attributes from the builder.
   AttrBuilder &remove(const AttributeMask &AM);
 
   /// Return true if the builder has any attribute that's in the
   /// specified builder.
   bool overlaps(const AttributeMask &AM) const;
 
   /// Return true if the builder has the specified attribute.
-  bool contains(Attribute::AttrKind A) const {
-    assert((unsigned)A < Attribute::EndAttrKinds && "Attribute out of range!");
-    return Attrs[A];
-  }
+  bool contains(Attribute::AttrKind A) const;
 
   /// Return true if the builder has the specified target-dependent
   /// attribute.
   bool contains(StringRef A) const;
 
   /// Return true if the builder has IR-level attributes.
-  bool hasAttributes() const;
+  bool hasAttributes() const { return !Attrs.empty(); }
 
   /// Return true if the builder has an alignment attribute.
   bool hasAlignmentAttr() const;
 
   /// Return Attribute with the given Kind. The returned attribute will be
   /// invalid if the Kind is not present in the builder.
+  Attribute getAttribute(Attribute::AttrKind Kind) const;
+
+  /// Return Attribute with the given Kind. The returned attribute will be
+  /// invalid if the Kind is not present in the builder.
   Attribute getAttribute(StringRef Kind) const;
 
   /// Return raw (possibly packed/encoded) value of integer attribute or 0 if
   /// not set.
   uint64_t getRawIntAttr(Attribute::AttrKind Kind) const;
 
   /// Retrieve the alignment attribute, if it exists.
   MaybeAlign getAlignment() const {
public:
   /// Add an allocsize attribute, using the representation returned by
   /// Attribute.getIntValue().
   AttrBuilder &addAllocSizeAttrFromRawRepr(uint64_t RawAllocSizeRepr);
 
   /// Add a vscale_range attribute, using the representation returned by
   /// Attribute.getIntValue().
   AttrBuilder &addVScaleRangeAttrFromRawRepr(uint64_t RawVScaleRangeRepr);
 
-  // Iterators for target-dependent attributes.
-  using td_const_iterator = decltype(TargetDepAttrs)::const_iterator;
-  using td_const_range = iterator_range<td_const_iterator>;
-
-  td_const_iterator td_begin() const { return TargetDepAttrs.begin(); }
-  td_const_iterator td_end() const { return TargetDepAttrs.end(); }
-
-  td_const_range td_attrs() const {
-    return td_const_range(td_begin(), td_end());
-  }
+  ArrayRef<Attribute> attrs() const { return Attrs; }
 
   bool operator==(const AttrBuilder &B) const;
   bool operator!=(const AttrBuilder &B) const { return !(*this == B); }
 };
 
 namespace AttributeFuncs {
 
 /// Which attributes cannot be applied to a type.

llvm/lib/IR/Attributes.cpp

if (!PA) {
     pImpl->AttrsSetNodes.InsertNode(PA, InsertPoint);
   }
 
   // Return the AttributeSetNode that we found or created.
   return PA;
 }
 
 AttributeSetNode *AttributeSetNode::get(LLVMContext &C, const AttrBuilder &B) {
-  // Add target-independent attributes.
-  SmallVector<Attribute, 8> Attrs;
-  for (Attribute::AttrKind Kind = Attribute::None;
-       Kind != Attribute::EndAttrKinds; Kind = Attribute::AttrKind(Kind + 1)) {
-    if (!B.contains(Kind))
-      continue;
-
-    Attribute Attr;
-    if (Attribute::isTypeAttrKind(Kind))
-      Attr = Attribute::get(C, Kind, B.getTypeAttr(Kind));
-    else if (Attribute::isIntAttrKind(Kind))
-      Attr = Attribute::get(C, Kind, B.getRawIntAttr(Kind));
-    else
-      Attr = Attribute::get(C, Kind);
-    Attrs.push_back(Attr);
-  }
-
-  // Add target-dependent (string) attributes.
-  for (const auto &TDA : B.td_attrs())
-    Attrs.push_back(TDA);
-
-  return getSorted(C, Attrs);
+  return getSorted(C, B.attrs());
 }
 
 bool AttributeSetNode::hasAttribute(StringRef Kind) const {
   return StringAttrs.count(Kind);
 }
 
 Optional<Attribute>
 AttributeSetNode::findEnumAttribute(Attribute::AttrKind Kind) const {

 LLVM_DUMP_METHOD void AttributeList::dump() const { print(dbgs()); }
 #endif
 
 //===----------------------------------------------------------------------===//
 // AttrBuilder Method Implementations
 //===----------------------------------------------------------------------===//
 
 AttrBuilder::AttrBuilder(LLVMContext &Ctx, AttributeSet AS) : Ctx(Ctx) {
-  for (const auto &A : AS)
-    addAttribute(A);
+  append_range(Attrs, AS);
+  assert(is_sorted(Attrs) && "AttributeSet should be sorted");
 }
 
-void AttrBuilder::clear() {
-  Attrs.reset();
-  TargetDepAttrs.clear();
-  IntAttrs = {};
-  TypeAttrs = {};
-}
-
-Optional<unsigned>
-AttrBuilder::kindToIntIndex(Attribute::AttrKind Kind) const {
-  if (Attribute::isIntAttrKind(Kind))
-    return Kind - Attribute::FirstIntAttr;
-  return None;
-}
-
-Optional<unsigned>
-AttrBuilder::kindToTypeIndex(Attribute::AttrKind Kind) const {
-  if (Attribute::isTypeAttrKind(Kind))
-    return Kind - Attribute::FirstTypeAttr;
-  return None;
-}
+void AttrBuilder::clear() { Attrs.clear(); }
 
-struct StringAttributeComparator {
+/// Attribute comparator that only compares attribute keys. Enum attributes are
+/// sorted before string attributes.
+struct AttributeComparator {
   bool operator()(Attribute A0, Attribute A1) const {
+    bool A0IsString = A0.isStringAttribute();
+    bool A1IsString = A1.isStringAttribute();
+    if (A0IsString) {
+      if (A1IsString)
         return A0.getKindAsString() < A1.getKindAsString();
+      else
+        return false;
+    }
+    if (A1IsString)
+      return true;
+    return A0.getKindAsEnum() < A1.getKindAsEnum();
+  }
+  bool operator()(Attribute A0, Attribute::AttrKind Kind) const {
+    if (A0.isStringAttribute())
+      return false;
+    return A0.getKindAsEnum() < Kind;
   }
   bool operator()(Attribute A0, StringRef Kind) const {
+    if (A0.isStringAttribute())
       return A0.getKindAsString() < Kind;
+    return true;
   }
 };
 
-AttrBuilder &AttrBuilder::addAttribute(Attribute Attr) {
-  if (Attr.isStringAttribute()) {
-    auto It = lower_bound(TargetDepAttrs, Attr, StringAttributeComparator());
-    if (It != TargetDepAttrs.end() && It->hasAttribute(Attr.getKindAsString()))
-      std::swap(*It, Attr);
-    else
-      TargetDepAttrs.insert(It, Attr);
-    return *this;
-  }
+template <typename K>
+static void addAttributeImpl(SmallVectorImpl<Attribute> &Attrs, K Kind,
+                             Attribute Attr) {
+  auto It = lower_bound(Attrs, Kind, AttributeComparator());
+  if (It != Attrs.end() && It->hasAttribute(Kind))
+    Attrs.insert(It, Attr);
 
-  Attribute::AttrKind Kind = Attr.getKindAsEnum();
-  Attrs[Kind] = true;
-
-  if (Optional<unsigned> TypeIndex = kindToTypeIndex(Kind))
-    TypeAttrs[*TypeIndex] = Attr.getValueAsType();
-  else if (Optional<unsigned> IntIndex = kindToIntIndex(Kind))
-    IntAttrs[*IntIndex] = Attr.getValueAsInt();
+AttrBuilder &AttrBuilder::addAttribute(Attribute Attr) {
+  if (Attr.isStringAttribute())
+    addAttributeImpl(Attrs, Attr.getKindAsString(), Attr);
+  else
+    addAttributeImpl(Attrs, Attr.getKindAsEnum(), Attr);
+  return *this;
+}
 
+AttrBuilder &AttrBuilder::addAttribute(Attribute::AttrKind Kind) {
+  addAttributeImpl(Attrs, Kind, Attribute::get(Ctx, Kind));
   return *this;
 }
 
 AttrBuilder &AttrBuilder::addAttribute(StringRef A, StringRef V) {
-  return addAttribute(Attribute::get(Ctx, A, V));
+  addAttributeImpl(Attrs, A, Attribute::get(Ctx, A, V));
+  return *this;
 }
 
 AttrBuilder &AttrBuilder::removeAttribute(Attribute::AttrKind Val) {
   assert((unsigned)Val < Attribute::EndAttrKinds && "Attribute out of range!");
-  Attrs[Val] = false;
-
-  if (Optional<unsigned> TypeIndex = kindToTypeIndex(Val))
-    TypeAttrs[*TypeIndex] = nullptr;
-  else if (Optional<unsigned> IntIndex = kindToIntIndex(Val))
-    IntAttrs[*IntIndex] = 0;
-
+  auto It = lower_bound(Attrs, Val, AttributeComparator());
+  if (It != Attrs.end() && It->hasAttribute(Val))
+    Attrs.erase(It);
   return *this;
 }
 
 AttrBuilder &AttrBuilder::removeAttribute(StringRef A) {
-  auto It = lower_bound(TargetDepAttrs, A, StringAttributeComparator());
-  if (It != TargetDepAttrs.end() && It->hasAttribute(A))
-    TargetDepAttrs.erase(It);
+  auto It = lower_bound(Attrs, A, AttributeComparator());
+  if (It != Attrs.end() && It->hasAttribute(A))
+    Attrs.erase(It);
   return *this;
 }
 
 uint64_t AttrBuilder::getRawIntAttr(Attribute::AttrKind Kind) const {
-  Optional<unsigned> IntIndex = kindToIntIndex(Kind);
-  assert(IntIndex && "Not an int attribute");
-  return IntAttrs[*IntIndex];
+  assert(Attribute::isIntAttrKind(Kind) && "Not an int attribute");
+  Attribute A = getAttribute(Kind);
+  return A.isValid() ? A.getValueAsInt() : 0;
 }
 
 AttrBuilder &AttrBuilder::addRawIntAttr(Attribute::AttrKind Kind,
                                         uint64_t Value) {
-  Optional<unsigned> IntIndex = kindToIntIndex(Kind);
-  assert(IntIndex && "Not an int attribute");
-  assert(Value && "Value cannot be zero");
-  Attrs[Kind] = true;
-  IntAttrs[*IntIndex] = Value;
-  return *this;
+  return addAttribute(Attribute::get(Ctx, Kind, Value));
 }
 
 std::pair<unsigned, Optional<unsigned>> AttrBuilder::getAllocSizeArgs() const {
   return unpackAllocSizeArgs(getRawIntAttr(Attribute::AllocSize));
 }
 
 unsigned AttrBuilder::getVScaleRangeMin() const {
   return unpackVScaleRangeArgs(getRawIntAttr(Attribute::VScaleRange)).first;
AttrBuilder &AttrBuilder::addVScaleRangeAttrFromRawRepr(uint64_t RawArgs) {
   // (0, 0) is not present hence ignore this case
   if (RawArgs == 0)
     return *this;
 
   return addRawIntAttr(Attribute::VScaleRange, RawArgs);
 }
 
 Type *AttrBuilder::getTypeAttr(Attribute::AttrKind Kind) const {
-  Optional<unsigned> TypeIndex = kindToTypeIndex(Kind);
-  assert(TypeIndex && "Not a type attribute");
-  return TypeAttrs[*TypeIndex];
+  assert(Attribute::isTypeAttrKind(Kind) && "Not a type attribute");
+  Attribute A = getAttribute(Kind);
+  return A.isValid() ? A.getValueAsType() : nullptr;
 }
 
 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;
+  return addAttribute(Attribute::get(Ctx, Kind, Ty));
 }
 
 AttrBuilder &AttrBuilder::addByValAttr(Type *Ty) {
   return addTypeAttr(Attribute::ByVal, 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);
 }
 
 AttrBuilder &AttrBuilder::merge(const AttrBuilder &B) {
-  for (unsigned Index = 0; Index < Attribute::NumIntAttrKinds; ++Index)
-    if (B.IntAttrs[Index])
-      IntAttrs[Index] = B.IntAttrs[Index];
-
-  for (unsigned Index = 0; Index < Attribute::NumTypeAttrKinds; ++Index)
-    if (B.TypeAttrs[Index])
-      TypeAttrs[Index] = B.TypeAttrs[Index];
-
-  Attrs |= B.Attrs;
-
-  // TODO: could merge both lists in one loop
-  for (const auto &I : B.td_attrs())
+  // TODO: Could make this O(n) as we're merging two sorted lists.
+  for (const auto &I : B.attrs())
     addAttribute(I);
 
   return *this;
 }
 
 AttrBuilder &AttrBuilder::remove(const AttributeMask &AM) {
-  for (unsigned Index = 0; Index < Attribute::NumIntAttrKinds; ++Index)
-    if (AM.contains((Attribute::AttrKind)Index))
-      IntAttrs[Index] = 0;
-
-  for (unsigned Index = 0; Index < Attribute::NumTypeAttrKinds; ++Index)
-    if (AM.contains((Attribute::AttrKind)Index))
-      TypeAttrs[Index] = nullptr;
-
-  Attrs &= ~AM.attrs();
-
-  erase_if(TargetDepAttrs,
-           [&AM](Attribute A) { return AM.contains(A.getKindAsString()); });
-
+  erase_if(Attrs, [&](Attribute A) { return AM.contains(A); });
   return *this;
 }
 
 bool AttrBuilder::overlaps(const AttributeMask &AM) const {
-  // First check if any of the target independent attributes overlap.
-  if ((Attrs & AM.attrs()).any())
-    return true;
+  return any_of(Attrs, [&](Attribute A) { return AM.contains(A); });
+}
 
-  // Then check if any target dependent ones do.
-  for (const auto &I : td_attrs())
-    if (AM.contains(I.getKindAsString()))
-      return true;
-  return false;
+Attribute AttrBuilder::getAttribute(Attribute::AttrKind A) const {
+  assert((unsigned)A < Attribute::EndAttrKinds && "Attribute out of range!");
+  auto It = lower_bound(Attrs, A, AttributeComparator());
+  if (It != Attrs.end() && It->hasAttribute(A))
+    return *It;
+  return {};
 }
 
 Attribute AttrBuilder::getAttribute(StringRef A) const {
-  auto It = lower_bound(TargetDepAttrs, A, StringAttributeComparator());
-  if (It != TargetDepAttrs.end() && It->hasAttribute(A))
+  auto It = lower_bound(Attrs, A, AttributeComparator());
+  if (It != Attrs.end() && It->hasAttribute(A))
     return *It;
   return {};
 }
 
-bool AttrBuilder::contains(StringRef A) const {
+bool AttrBuilder::contains(Attribute::AttrKind A) const {
   return getAttribute(A).isValid();
 }
 
-bool AttrBuilder::hasAttributes() const {
-  return !Attrs.none() || !TargetDepAttrs.empty();
+bool AttrBuilder::contains(StringRef A) const {
+  return getAttribute(A).isValid();
 }
 
 bool AttrBuilder::hasAlignmentAttr() const {
   return getRawIntAttr(Attribute::Alignment) != 0;
 }
 
 bool AttrBuilder::operator==(const AttrBuilder &B) const {
-  return Attrs == B.Attrs && IntAttrs == B.IntAttrs &&
-         TypeAttrs == B.TypeAttrs && TargetDepAttrs == B.TargetDepAttrs;
+  return Attrs == B.Attrs;
 }
 
 //===----------------------------------------------------------------------===//
 // AttributeFuncs Function Defintions
 //===----------------------------------------------------------------------===//
 
 /// Which attributes cannot be applied to a type.
 AttributeMask AttributeFuncs::typeIncompatible(Type *Ty) {