[IR] Store attributes that are available "somewhere" (NFC)

[nikic]

Summary

I noticed that for some benchmarks we spend quite a bit of time inside AttributeList::hasAttrSomewhere(), mainly when checking for the returned attribute. Most of the time the attribute will not be present, in which case this function has to walk through the whole attribute list and check for the attribute at each index.

This patch proposes to add a cache of all "available somewhere" attributes inside AttributeListImpl. This makes the structure 12 bytes larger, but I don't think that's problematic, as attribute lists are uniqued. Compile-time improves by 0.4% on average, but >1% for sqlite.

[nikic]

Ping

[jdoerfert]

LGTM. Thx!

llvm/lib/IR/AttributeImpl.h

: public FoldingSetNode,
       private TrailingObjects<AttributeListImpl, AttributeSet> {
   friend class AttributeList;
   friend TrailingObjects;
 
 private:
   unsigned NumAttrSets; ///< Number of entries in this set.
   /// Available enum function attributes.
   AttributeBitSet AvailableFunctionAttrs;
+  /// Union of enum attributes available at any index.
+  AttributeBitSet AvailableSomewhereAttrs;
 
   // Helper fn for TrailingObjects class.
   size_t numTrailingObjects(OverloadToken<AttributeSet>) { return NumAttrSets; }
 
 public:
   AttributeListImpl(ArrayRef<AttributeSet> Sets);
 
   // AttributesSetImpt is uniqued, these should not be available.
   AttributeListImpl(const AttributeListImpl &) = delete;
   AttributeListImpl &operator=(const AttributeListImpl &) = delete;
 
   /// Return true if the AttributeSet or the FunctionIndex has an
   /// enum attribute of the given kind.
   bool hasFnAttribute(Attribute::AttrKind Kind) const {
     return AvailableFunctionAttrs.hasAttribute(Kind);
   }
 
+  /// Return true if the specified attribute is set for at least one
+  /// parameter or for the return value. If Index is not nullptr, the index
+  /// of a parameter with the specified attribute is provided.
+  bool hasAttrSomewhere(Attribute::AttrKind Kind,
+                        unsigned *Index = nullptr) const;
+
   using iterator = const AttributeSet *;
 
   iterator begin() const { return getTrailingObjects<AttributeSet>(); }
   iterator end() const { return begin() + NumAttrSets; }
 
   void Profile(FoldingSetNodeID &ID) const;
   static void Profile(FoldingSetNodeID &ID, ArrayRef<AttributeSet> Nodes);
 

llvm/lib/IR/Attributes.cpp

 
 AttributeListImpl::AttributeListImpl(ArrayRef<AttributeSet> Sets)
     : NumAttrSets(Sets.size()) {
   assert(!Sets.empty() && "pointless AttributeListImpl");
 
   // There's memory after the node where we can store the entries in.
   llvm::copy(Sets, getTrailingObjects<AttributeSet>());
 
-  // Initialize AvailableFunctionAttrs summary bitset.
+  // Initialize AvailableFunctionAttrs and AvailableSomewhereAttrs
+  // summary bitsets.
   static_assert(attrIdxToArrayIdx(AttributeList::FunctionIndex) == 0U,
                 "function should be stored in slot 0");
-  for (const auto &I : Sets[0]) {
+  for (const auto &I : Sets[0])
     if (!I.isStringAttribute())
       AvailableFunctionAttrs.addAttribute(I.getKindAsEnum());
-  }
+
+  for (const auto &Set : Sets)
+    for (const auto &I : Set)
+      if (!I.isStringAttribute())
+        AvailableSomewhereAttrs.addAttribute(I.getKindAsEnum());
 }
 
 void AttributeListImpl::Profile(FoldingSetNodeID &ID) const {
   Profile(ID, makeArrayRef(begin(), end()));
 }
 
 void AttributeListImpl::Profile(FoldingSetNodeID &ID,
                                 ArrayRef<AttributeSet> Sets) {
   for (const auto &Set : Sets)
     ID.AddPointer(Set.SetNode);
 }
 
+bool AttributeListImpl::hasAttrSomewhere(Attribute::AttrKind Kind,
+                                        unsigned *Index) const {
+  if (!AvailableSomewhereAttrs.hasAttribute(Kind))
+    return false;
+
+  if (Index) {
+    for (unsigned I = 0, E = NumAttrSets; I != E; ++I) {
+      if (begin()[I].hasAttribute(Kind)) {
+        *Index = I - 1;
+        break;
+      }
+    }
+  }
+
+  return true;
+}
+
+
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 LLVM_DUMP_METHOD void AttributeListImpl::dump() const {
   AttributeList(const_cast<AttributeListImpl *>(this)).dump();
 }
 #endif
 
 //===----------------------------------------------------------------------===//
 // AttributeList Construction and Mutation Methods

 
 bool AttributeList::hasParamAttribute(unsigned ArgNo,
                                       Attribute::AttrKind Kind) const {
   return hasAttribute(ArgNo + FirstArgIndex, Kind);
 }
 
 bool AttributeList::hasAttrSomewhere(Attribute::AttrKind Attr,
                                      unsigned *Index) const {
-  if (!pImpl) return false;
-
-  for (unsigned I = index_begin(), E = index_end(); I != E; ++I) {
-    if (hasAttribute(I, Attr)) {
-      if (Index)
-        *Index = I;
-      return true;
-    }
-  }
-
-  return false;
+  return pImpl && pImpl->hasAttrSomewhere(Attr, Index);
 }
 
 Attribute AttributeList::getAttribute(unsigned Index,
                                       Attribute::AttrKind Kind) const {
   return getAttributes(Index).getAttribute(Kind);
 }
 
 Attribute AttributeList::getAttribute(unsigned Index, StringRef Kind) const {