[IR] Use map for string attributes (NFC)

[nikic]

Summary

Attributes (whether enum or string) are currently stored as a simple list. Enum attributes additionally use a bitset to allow quickly determining whether an attribute is set. String attributes on the other hand require a scan of the full list. As functions tend to have a lot of string attributes (at least when clang is used), this is a noticeable performance issue.

This patch adds an additional name => attribute map to the AttributeSetNode, which allows querying string attributes quickly. This results in a 3% reduction in instructions retired. Changes to memory usage seem to be in the noise (attribute sets are uniqued, and we don't tend to have more than a few dozen or hundred unique attribute sets, so adding an extra map does not have a visible cost.)

[arsenm]

lib/IR/AttributeImpl.h

185 ↗

(On Diff #260079)

Is StringMap any better?

[nikic]

lib/IR/AttributeImpl.h

185 ↗

(On Diff #260079)

I believe StringMap is only useful if the map needs to own the string. In this case the string is already owned by the Attribute. (StringMap allocates each map entry separately, as strings are variable-length.)

There's also CachedHashStringRef that can be used here, but I don't think that's useful either, because the map is immutable, so we do not need to worry about rehashing overhead.

[tejohnson]

lib/IR/AttributeImpl.h

185 ↗

(On Diff #260079)

Won't this store the Attributes twice (once in the TrailingObjects base class and once in the DenseMap)? Would it be better to just use a StringMap here to subsume the TrailingObjects and not duplicate the Attributes? Or store a pointer to the const * value returned by the iterator?

[nikic]

lib/IR/AttributeImpl.h

185 ↗

(On Diff #260079)

Attribute is a pointer-like type, the actual attribute objects are allocated separately and globally uniqued. So we're only duplicating pointers here.

It would in theory be possible to remove string attributes from the trailing objects and only store them in the map, but I think this would cause many complications for little benefit, as AttributeSet is not particularly memory-critical. In particular this would make it hard to iterate over all attributes, and no longer provide a fixed ordering for attributes. Possibly it would cause issues with folding set profiling as well, I'm not sure whether that depends on the ordering or not.

[wenlei]

Nice change - thanks!

lib/IR/AttributeImpl.h

185 ↗

(On Diff #260079)

While StringMap would duplicate the underlying string, the DJB hash used by StringMap should be more efficient than the generic hash for StringRef - see djbHash vs hash_combine_range_impl. Given this is a hot spot, the speed/size trade-off may favor StringMap.

[nikic]

lib/IR/AttributeImpl.h

185 ↗

(On Diff #260079)

I gave StringMap a try, but the numbers are markedly worse: http://llvm-compile-time-tracker.com/compare.php?from=0cc4958dd2dda646abda6a7b01aeb6b50b601e6b&to=5655d81e5dd2e753248b47f26d09e86171f732d0&stat=instructions This is relative to using DenseMap of StringRef.

[wenlei]

lib/IR/AttributeImpl.h

185 ↗

(On Diff #260079)

Ok, thanks for measuring.

[tejohnson]

Lgtm as well

llvm/lib/IR/AttributeImpl.h

 /// LLVMContextImpl for creating and managing attributes.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_LIB_IR_ATTRIBUTEIMPL_H
 #define LLVM_LIB_IR_ATTRIBUTEIMPL_H
 
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/Support/TrailingObjects.h"
 #include <cassert>
 #include <cstddef>
 #include <cstdint>
 #include <string>
class AttributeSetNode final
     : public FoldingSetNode,
       private TrailingObjects<AttributeSetNode, Attribute> {
   friend TrailingObjects;
 
   unsigned NumAttrs; ///< Number of attributes in this node.
   /// Bitset with a bit for each available attribute Attribute::AttrKind.
   uint8_t AvailableAttrs[12] = {};
 
+  DenseMap<StringRef, Attribute> StringAttrs;
+
   AttributeSetNode(ArrayRef<Attribute> Attrs);
 
 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); }

llvm/lib/IR/Attributes.cpp

AttributeSetNode::AttributeSetNode(ArrayRef<Attribute> Attrs)
   // There's memory after the node where we can store the entries in.
   llvm::copy(Attrs, getTrailingObjects<Attribute>());
 
   static_assert(Attribute::EndAttrKinds <=
                     sizeof(AvailableAttrs) * CHAR_BIT,
                 "Too many attributes");
 
   for (const auto &I : *this) {
-    if (!I.isStringAttribute()) {
+    if (I.isStringAttribute()) {
+      StringAttrs.insert({ I.getKindAsString(), I });
+    } else {
       Attribute::AttrKind Kind = I.getKindAsEnum();
       AvailableAttrs[Kind / 8] |= 1ULL << (Kind % 8);
     }
   }
 }
 
 AttributeSetNode *AttributeSetNode::get(LLVMContext &C,
                                         ArrayRef<Attribute> Attrs) {
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 get(C, Attrs);
 }
 
 bool AttributeSetNode::hasAttribute(StringRef Kind) const {
-  for (const auto &I : *this)
-    if (I.hasAttribute(Kind))
-      return true;
-  return false;
+  return StringAttrs.count(Kind);
 }
 
 Attribute AttributeSetNode::getAttribute(Attribute::AttrKind Kind) const {
   if (hasAttribute(Kind)) {
     for (const auto &I : *this)
       if (I.hasAttribute(Kind))
         return I;
   }
   return {};
 }
 
 Attribute AttributeSetNode::getAttribute(StringRef Kind) const {
-  for (const auto &I : *this)
-    if (I.hasAttribute(Kind))
-      return I;
-  return {};
+  return StringAttrs.lookup(Kind);
 }
 
 MaybeAlign AttributeSetNode::getAlignment() const {
   for (const auto &I : *this)
     if (I.hasAttribute(Attribute::Alignment))
       return I.getAlignment();
   return None;
 }