[IR] AttrBuilder: change TargetDepAttrs to StringMap<SmallString<16>>

[lebedev.ri]

Summary

Looking at memory footprint of unity build of RawSpeed library
(-O3 -g0 -emit-llvm -Xclang -disable-llvm-optzns),
surprisingly AttrBuilder is top-1 in memory allocations,
which is not that surprising since it's a std::map<std::string, std::string>

Let's see what is the baseline memory footprint,
and what happens with just StringMap<std::string>/StringMap<SmallString<N>>:

$ heaptrack_print heaptrack.clang++.baseline.gz | tail -n 6 ; heaptrack_print heaptrack.clang++.proposed.gz | tail -n 6
total runtime: 11.76s.
calls to allocation functions: 2951292 (250981/s)
temporary memory allocations: 608175 (51719/s)
peak heap memory consumption: 231.36MB
peak RSS (including heaptrack overhead): 399.31MB
total memory leaked: 204.39MB

Migrating std::map<std::string, std::string> to StringMap<SmallString<16>> improves things:

total runtime: 11.33s.
calls to allocation functions: 2684647 (236908/s)
temporary memory allocations: 643713 (56804/s)
peak heap memory consumption: 231.44MB
peak RSS (including heaptrack overhead): 397.13MB
total memory leaked: 204.47MB

$ heaptrack_print -d heaptrack.clang++.baseline.gz heaptrack.clang++.proposed.gz | tail -n 6
total runtime: -0.43s.                            # -3.66 %
calls to allocation functions: -266645 (624461/s) # -9.03 % (!)
temporary memory allocations: 35538 (-83227/s)    # +5.84 % (:/)
peak heap memory consumption: 81.71KB
peak RSS (including heaptrack overhead): 0B
total memory leaked: 81.71KB

[lebedev.ri]

Actually ensure that check-llvm/check-clang passes.
Doesn't have any significant impact on results.

[bkramer]

llvm/include/llvm/IR/Attributes.h

727

I'm a bit confused that SmallString gives an improvement in the number of allocations. All modern standard libraries implement std::string with SSO, so std::string should behave identically to SmallString<16>. What standard library did you test this with?

870–871

I don't think this is used anywhere. Can we just delete it?

llvm/lib/IR/Attributes.cpp

888

Just sorting the string attributes would be sufficient. Sorting attributes is expensive.

[nikic]

At least in the current implementation, this looks like a big regression, especially for O0: http://llvm-compile-time-tracker.com/compare.php?from=ff1210edb69ea6e073b9037ad3ecef399e11a1f9&to=5327f42cf609a8a673ee49454210319226f4200a&stat=instructions

[lebedev.ri]

Sort only string attributes.
@nikic how about this one?

llvm/include/llvm/IR/Attributes.h

727

I'm on debian sid, so there's really nothing weird going on here.

$ ldd bin/clang | grep c++
        libstdc++.so.6 => /lib/x86_64-linux-gnu/libstdc++.so.6 (0x00007fe8aa3a0000)
$ dpkg -S libstdc++.so
libx32stdc++6: /usr/libx32/libstdc++.so.6.0.28
libstdc++6:amd64: /usr/share/gdb/auto-load/usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.28-gdb.py
libx32stdc++6: /usr/libx32/libstdc++.so.6
libx32stdc++6: /usr/share/gdb/auto-load/usr/libx32/libstdc++.so.6.0.28-gdb.py
lib32stdc++6: /usr/lib32/libstdc++.so.6.0.28
libstdc++-10-dev:amd64: /usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.so
libstdc++-8-dev:amd64: /usr/lib/gcc/x86_64-linux-gnu/8/libstdc++.so
libstdc++-9-dev:amd64: /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.so
libstdc++6:amd64: /usr/lib/x86_64-linux-gnu/libstdc++.so.6
lib32stdc++6: /usr/lib32/libstdc++.so.6
lib32stdc++6: /usr/share/gdb/auto-load/usr/lib32/libstdc++.so.6.0.28-gdb.py
libstdc++6:amd64: /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.28
$ apt-cache show libstdc++6:amd64
Package: libstdc++6
Source: gcc-10
Version: 10.1.0-3
Installed-Size: 2351
Maintainer: Debian GCC Maintainers <[e-mail]>
Architecture: amd64
Replaces: libstdc++6-10-dbg (<< 4.9.0-3)
Depends: gcc-10-base (= 10.1.0-3), libc6 (>= 2.18), libgcc-s1 (>= 4.2)
Conflicts: scim (<< 1.4.2-1)
Breaks: gcc-4.3 (<< 4.3.6-1), gcc-4.4 (<< 4.4.6-4), gcc-4.5 (<< 4.5.3-2)
Description-en: GNU Standard C++ Library v3
 This package contains an additional runtime library for C++ programs
 built with the GNU compiler.
 .
 libstdc++-v3 is a complete rewrite from the previous libstdc++-v2, which
 was included up to g++-2.95. The first version of libstdc++-v3 appeared
 in g++-3.0.
Description-md5: 724ab84919e0e220afb960e36463914d
Multi-Arch: same
Homepage: http://gcc.gnu.org/
Tag: role::shared-lib
Section: libs
Priority: optional
Filename: pool/main/g/gcc-10/libstdc++6_10.1.0-3_amd64.deb
Size: 491824
MD5sum: b3c01846fda0d56a0ec15e24935a0da6
SHA256: 7349532219fbc71a211954dc0a7ca136343c14769cb71c9c4cabe032d6cc9c38

All modern standard libraries implement std::string with SSO, so std::string should behave identically to SmallString<16>.

I see:

      enum { _S_local_capacity = 15 / sizeof(_CharT) };

      union
      {
	_CharT           _M_local_buf[_S_local_capacity + 1];
	size_type        _M_allocated_capacity;
      };

So i would say it's one char less.
Also, here

static_assert(sizeof(SmallString<16>) == 40);
static_assert(sizeof(std::string) == 32);

which means that given same buffer size, we'll fit less SmallStrings in it,
causing new allocation sooner. How does StringMap grow?
I'd guess by consuming memory more aggressively, we end up growing less times.
At least that would be my guess.

llvm/lib/IR/Attributes.cpp

888

Right.

[lebedev.ri]

Let's not bother.

llvm/lib/IR/Attributes.cpp

884–886

Hm, that doesn't do it.

llvm/include/llvm/IR/Attributes.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_IR_ATTRIBUTES_H
 #define LLVM_IR_ATTRIBUTES_H
 
 #include "llvm-c/Types.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/Optional.h"
+#include "llvm/ADT/SmallString.h"
+#include "llvm/ADT/StringMap.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>

 //===----------------------------------------------------------------------===//
 /// \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<std::string, std::string, std::less<>> TargetDepAttrs;
+  StringMap<SmallString<16>> TargetDepAttrs;
   MaybeAlign Alignment;
   MaybeAlign StackAlignment;
   uint64_t DerefBytes = 0;
   uint64_t DerefOrNullBytes = 0;
   uint64_t AllocSizeArgs = 0;
   Type *ByValType = nullptr;
   Type *PreallocatedType = nullptr;
 
public:
   /// Add an allocsize attribute, using the representation returned by
   /// Attribute.getIntValue().
   AttrBuilder &addAllocSizeAttrFromRawRepr(uint64_t RawAllocSizeRepr);
 
   /// Return true if the builder contains no target-independent
   /// attributes.
   bool empty() const { return Attrs.none(); }
 
   // Iterators for target-dependent attributes.
-  using td_type = std::pair<std::string, std::string>;
   using td_iterator = decltype(TargetDepAttrs)::iterator;
   using td_const_iterator = decltype(TargetDepAttrs)::const_iterator;
   using td_range = iterator_range<td_iterator>;
   using td_const_range = iterator_range<td_const_iterator>;
 
   td_iterator td_begin() { return TargetDepAttrs.begin(); }
   td_iterator td_end() { return TargetDepAttrs.end(); }
 
   td_const_iterator td_begin() const { return TargetDepAttrs.begin(); }
   td_const_iterator td_end() const { return TargetDepAttrs.end(); }
 
   td_range td_attrs() { return td_range(td_begin(), td_end()); }
 
   td_const_range td_attrs() const {
     return td_const_range(td_begin(), td_end());
   }
 
   bool td_empty() const { return TargetDepAttrs.empty(); }
 
+  bool td_size() const { return TargetDepAttrs.size(); }
+
   bool operator==(const AttrBuilder &B);
   bool operator!=(const AttrBuilder &B) {
     return !(*this == B);
   }
 };
 
 namespace AttributeFuncs {
 

llvm/lib/IR/Attributes.cpp

for (Attribute::AttrKind Kind = Attribute::None;
     }
     default:
       Attr = Attribute::get(C, Kind);
     }
     Attrs.push_back(Attr);
   }
 
   // Add target-dependent (string) attributes.
+  unsigned NumStringAttrs = B.td_size();
+  Attrs.reserve(Attrs.size() + NumStringAttrs);
   for (const auto &TDA : B.td_attrs())
-    Attrs.emplace_back(Attribute::get(C, TDA.first, TDA.second));
+    Attrs.emplace_back(Attribute::get(C, TDA.first(), TDA.second));
+
+  // And sort string attributes only.
+  auto StringAttrs =
+      MutableArrayRef<Attribute>(Attrs).take_back(NumStringAttrs);
+  llvm::sort(StringAttrs.begin(), StringAttrs.end());
 
   return getSorted(C, Attrs);
 }
 
 bool AttributeSetNode::hasAttribute(StringRef Kind) const {
   return StringAttrs.count(Kind);
 }
 
 Optional<Attribute>
 AttributeSetNode::findEnumAttribute(Attribute::AttrKind Kind) const {
AttrBuilder &AttrBuilder::addAttribute(Attribute Attr) {
   else if (Kind == Attribute::DereferenceableOrNull)
     DerefOrNullBytes = Attr.getDereferenceableOrNullBytes();
   else if (Kind == Attribute::AllocSize)
     AllocSizeArgs = Attr.getValueAsInt();
   return *this;
 }
 
 AttrBuilder &AttrBuilder::addAttribute(StringRef A, StringRef V) {
-  TargetDepAttrs[std::string(A)] = std::string(V);
+  TargetDepAttrs[A] = V;
   return *this;
 }
 
 AttrBuilder &AttrBuilder::removeAttribute(Attribute::AttrKind Val) {
   assert((unsigned)Val < Attribute::EndAttrKinds && "Attribute out of range!");
   Attrs[Val] = false;
 
   if (Val == Attribute::Alignment)

 }
 
 AttrBuilder &AttrBuilder::removeAttributes(AttributeList A, uint64_t Index) {
   remove(A.getAttributes(Index));
   return *this;
 }
 
 AttrBuilder &AttrBuilder::removeAttribute(StringRef A) {
-  auto I = TargetDepAttrs.find(A);
-  if (I != TargetDepAttrs.end())
-    TargetDepAttrs.erase(I);
+  TargetDepAttrs.erase(A);
   return *this;
 }
 
 std::pair<unsigned, Optional<unsigned>> AttrBuilder::getAllocSizeArgs() const {
   return unpackAllocSizeArgs(AllocSizeArgs);
 }
 
 AttrBuilder &AttrBuilder::addAlignmentAttr(MaybeAlign Align) {
AttrBuilder &AttrBuilder::merge(const AttrBuilder &B) {
   if (!ByValType)
     ByValType = B.ByValType;
 
   if (!PreallocatedType)
     PreallocatedType = B.PreallocatedType;
 
   Attrs |= B.Attrs;
 
-  for (auto I : B.td_attrs())
-    TargetDepAttrs[I.first] = I.second;
+  for (auto &I : B.td_attrs())
+    TargetDepAttrs[I.first()] = I.second;
 
   return *this;
 }
 
 AttrBuilder &AttrBuilder::remove(const AttrBuilder &B) {
   // FIXME: What if both have alignments, but they don't match?!
   if (B.Alignment)
     Alignment.reset();
AttrBuilder &AttrBuilder::remove(const AttrBuilder &B) {
   if (B.ByValType)
     ByValType = nullptr;
 
   if (B.PreallocatedType)
     PreallocatedType = nullptr;
 
   Attrs &= ~B.Attrs;
 
-  for (auto I : B.td_attrs())
-    TargetDepAttrs.erase(I.first);
+  for (auto &I : B.td_attrs())
+    TargetDepAttrs.erase(I.first());
 
   return *this;
 }
 
 bool AttrBuilder::overlaps(const AttrBuilder &B) const {
   // First check if any of the target independent attributes overlap.
   if ((Attrs & B.Attrs).any())
     return true;
 
   // Then check if any target dependent ones do.
   for (const auto &I : td_attrs())
-    if (B.contains(I.first))
+    if (B.contains(I.first()))
       return true;
 
   return false;
 }
 
 bool AttrBuilder::contains(StringRef A) const {
-  return TargetDepAttrs.find(A) != TargetDepAttrs.end();
+  return TargetDepAttrs.count(A);
 }
 
 bool AttrBuilder::hasAttributes() const {
   return !Attrs.none() || !TargetDepAttrs.empty();
 }
 
 bool AttrBuilder::hasAttributes(AttributeList AL, uint64_t Index) const {
   AttributeSet AS = AL.getAttributes(Index);

 }
 
 bool AttrBuilder::operator==(const AttrBuilder &B) {
   if (Attrs != B.Attrs)
     return false;
 
   for (td_const_iterator I = TargetDepAttrs.begin(),
          E = TargetDepAttrs.end(); I != E; ++I)
-    if (B.TargetDepAttrs.find(I->first) == B.TargetDepAttrs.end())
+    if (!B.contains(I->first()))
       return false;
 
   return Alignment == B.Alignment && StackAlignment == B.StackAlignment &&
          DerefBytes == B.DerefBytes && ByValType == B.ByValType &&
          PreallocatedType == B.PreallocatedType;
 }
 
 //===----------------------------------------------------------------------===//

llvm/lib/IR/AutoUpgrade.cpp

std::string llvm::UpgradeDataLayoutString(StringRef DL, StringRef TT) {
   return Res;
 }
 
 void llvm::UpgradeAttributes(AttrBuilder &B) {
   StringRef FramePointer;
   if (B.contains("no-frame-pointer-elim")) {
     // The value can be "true" or "false".
     for (const auto &I : B.td_attrs())
-      if (I.first == "no-frame-pointer-elim")
+      if (I.first() == "no-frame-pointer-elim")
         FramePointer = I.second == "true" ? "all" : "none";
     B.removeAttribute("no-frame-pointer-elim");
   }
   if (B.contains("no-frame-pointer-elim-non-leaf")) {
     // The value is ignored. "no-frame-pointer-elim"="true" takes priority.
     if (FramePointer != "all")
       FramePointer = "non-leaf";
     B.removeAttribute("no-frame-pointer-elim-non-leaf");
   }
   if (!FramePointer.empty())
     B.addAttribute("frame-pointer", FramePointer);
 
   if (B.contains("null-pointer-is-valid")) {
     // The value can be "true" or "false".
     bool NullPointerIsValid = false;
     for (const auto &I : B.td_attrs())
-      if (I.first == "null-pointer-is-valid")
+      if (I.first() == "null-pointer-is-valid")
         NullPointerIsValid = I.second == "true";
     B.removeAttribute("null-pointer-is-valid");
     if (NullPointerIsValid)
       B.addAttribute(Attribute::NullPointerIsValid);
   }
 }