Save a word in every StringSet entry

[jordan_rose]

Summary

Add a specialization to StringMap (actually StringMapEntry) for a value type of NoneType (the type of llvm::None), and use it for StringSet. This'll save us a word from every entry in a StringSet, used for alignment with the size_t that stores the string length.

I could have gone all the way to some kind of empty base class optimization, but that seemed like overkill.

[jordan_rose]

Hm, doesn't quite work yet but I'll get there.

[jordan_rose]

Fixed bad uses of StringSet, changed a friend from StringMapEntry to StringMapEntryStorage. The fact that I only had to do this in one place (and that one place is definitely doing something tricky) makes me still feel confident enough to make this change.

[dblaikie]

Looks good to me - thanks!

If you like, maybe leave a comment/hint that this could be generalized to a full EBO if someone has a need in the future.

Any idea why MDString is friending an implementation detail like this? Should it be? Could we make it an actual private implementation detail so people can't do this?

[jordan_rose]

In D68586#1704530, @dblaikie wrote:

Any idea why MDString is friending an implementation detail like this? Should it be? Could we make it an actual private implementation detail so people can't do this?

It's funky but I think reasonable: MDString is a move-none type since there will be direct pointers to it, and the canonical instance lives in the StringMap. Disallowing this friending would mean making MDString move-only and just assuming it'll never be misused.

[jordan_rose]

Committed in rL374440. I split the difference and put the EBO comment in the commit message.

[dblaikie]

In D68586#1704684, @jordan_rose wrote:

In D68586#1704530, @dblaikie wrote:

Any idea why MDString is friending an implementation detail like this? Should it be? Could we make it an actual private implementation detail so people can't do this?

It's funky but I think reasonable: MDString is a move-none type since there will be direct pointers to it, and the canonical instance lives in the StringMap. Disallowing this friending would mean making MDString move-only and just assuming it'll never be misused.

Figured something like that. I think for standard containers, at least, that can now be achieved through a custom allocator ( https://en.cppreference.com/w/cpp/memory/allocator/construct - not sure why the non-default version was deprecated... well, one possible reason (below))

The other way to do it is with a private tagged parameter - have a private type in MDString, have a public ctor that takes an instance of that type as a parameter, and then no public user can call it because they can't name the type, but MDString's implementation can call into other code including templates that can handle that.

llvm/include/llvm/ADT/StringMap.h

public:
   void swap(StringMapImpl &Other) {
     std::swap(TheTable, Other.TheTable);
     std::swap(NumBuckets, Other.NumBuckets);
     std::swap(NumItems, Other.NumItems);
     std::swap(NumTombstones, Other.NumTombstones);
   }
 };
 
-/// StringMapEntry - This is used to represent one value that is inserted into
-/// a StringMap.  It contains the Value itself and the key: the string length
-/// and data.
+/// StringMapEntryStorage - Holds the value in a StringMapEntry.
+///
+/// Factored out into a separate base class to make it easier to specialize.
+/// This is primarily intended to support StringSet, which doesn't need a value
+/// stored at all.
 template<typename ValueTy>
-class StringMapEntry : public StringMapEntryBase {
+class StringMapEntryStorage : public StringMapEntryBase {
 public:
   ValueTy second;
 
-  explicit StringMapEntry(size_t strLen)
+  explicit StringMapEntryStorage(size_t strLen)
     : StringMapEntryBase(strLen), second() {}
   template <typename... InitTy>
-  StringMapEntry(size_t strLen, InitTy &&... InitVals)
+  StringMapEntryStorage(size_t strLen, InitTy &&... InitVals)
       : StringMapEntryBase(strLen), second(std::forward<InitTy>(InitVals)...) {}
-  StringMapEntry(StringMapEntry &E) = delete;
-
-  StringRef getKey() const {
-    return StringRef(getKeyData(), getKeyLength());
-  }
+  StringMapEntryStorage(StringMapEntryStorage &E) = delete;
 
   const ValueTy &getValue() const { return second; }
   ValueTy &getValue() { return second; }
 
   void setValue(const ValueTy &V) { second = V; }
+};
+
+template<>
+class StringMapEntryStorage<NoneType> : public StringMapEntryBase {
+public:
+  explicit StringMapEntryStorage(size_t strLen, NoneType none = None)
+    : StringMapEntryBase(strLen) {}
+  StringMapEntryStorage(StringMapEntryStorage &E) = delete;
+
+  NoneType getValue() const { return None; }
+};
+
+/// StringMapEntry - This is used to represent one value that is inserted into
+/// a StringMap.  It contains the Value itself and the key: the string length
+/// and data.
+template<typename ValueTy>
+class StringMapEntry final : public StringMapEntryStorage<ValueTy> {
+public:
+  using StringMapEntryStorage<ValueTy>::StringMapEntryStorage;
+
+  StringRef getKey() const {
+    return StringRef(getKeyData(), this->getKeyLength());
+  }
 
   /// getKeyData - Return the start of the string data that is the key for this
   /// value.  The string data is always stored immediately after the
   /// StringMapEntry object.
   const char *getKeyData() const {return reinterpret_cast<const char*>(this+1);}
 
-  StringRef first() const { return StringRef(getKeyData(), getKeyLength()); }
+  StringRef first() const {
+    return StringRef(getKeyData(), this->getKeyLength());
+  }
 
   /// Create a StringMapEntry for the specified key construct the value using
   /// \p InitiVals.
   template <typename AllocatorTy, typename... InitTy>
   static StringMapEntry *Create(StringRef Key, AllocatorTy &Allocator,
                                 InitTy &&... InitVals) {
     size_t KeyLength = Key.size();
 
static StringMapEntry &GetStringMapEntryFromKeyData(const char *KeyData) {
     return *reinterpret_cast<StringMapEntry*>(Ptr);
   }
 
   /// Destroy - Destroy this StringMapEntry, releasing memory back to the
   /// specified allocator.
   template<typename AllocatorTy>
   void Destroy(AllocatorTy &Allocator) {
     // Free memory referenced by the item.
-    size_t AllocSize = sizeof(StringMapEntry) + getKeyLength() + 1;
+    size_t AllocSize = sizeof(StringMapEntry) + this->getKeyLength() + 1;
     this->~StringMapEntry();
     Allocator.Deallocate(static_cast<void *>(this), AllocSize);
   }
 
   /// Destroy this object, releasing memory back to the malloc allocator.
   void Destroy() {
     MallocAllocator A;
     Destroy(A);

llvm/include/llvm/ADT/StringSet.h

 #include <cassert>
 #include <initializer_list>
 #include <utility>
 
 namespace llvm {
 
   /// StringSet - A wrapper for StringMap that provides set-like functionality.
   template <class AllocatorTy = MallocAllocator>
-  class StringSet : public StringMap<char, AllocatorTy> {
-    using base = StringMap<char, AllocatorTy>;
+  class StringSet : public StringMap<NoneType, AllocatorTy> {
+    using base = StringMap<NoneType, AllocatorTy>;
 
   public:
     StringSet() = default;
     StringSet(std::initializer_list<StringRef> S) {
       for (StringRef X : S)
         insert(X);
     }
     explicit StringSet(AllocatorTy A) : base(A) {}
 
     std::pair<typename base::iterator, bool> insert(StringRef Key) {
       assert(!Key.empty());
-      return base::insert(std::make_pair(Key, '\0'));
+      return base::insert(std::make_pair(Key, None));
     }
 
     template <typename InputIt>
     void insert(const InputIt &Begin, const InputIt &End) {
       for (auto It = Begin; It != End; ++It)
-        base::insert(std::make_pair(*It, '\0'));
+        base::insert(std::make_pair(*It, None));
     }
 
     template <typename ValueTy>
     std::pair<typename base::iterator, bool>
     insert(const StringMapEntry<ValueTy> &MapEntry) {
       return insert(MapEntry.getKey());
     }
   };
 
 } // end namespace llvm
 
 #endif // LLVM_ADT_STRINGSET_H

llvm/include/llvm/IR/Metadata.h

 } // end namespace mdconst
 
 //===----------------------------------------------------------------------===//
 /// A single uniqued string.
 ///
 /// These are used to efficiently contain a byte sequence for metadata.
 /// MDString is always unnamed.
 class MDString : public Metadata {
-  friend class StringMapEntry<MDString>;
+  friend class StringMapEntryStorage<MDString>;
 
   StringMapEntry<MDString> *Entry = nullptr;
 
   MDString() : Metadata(MDStringKind, Uniqued) {}
 
 public:
   MDString(const MDString &) = delete;
   MDString &operator=(MDString &&) = delete;

llvm/include/llvm/LTO/legacy/LTOCodeGenerator.h

struct LTOCodeGenerator {
   ///
   /// The default behavior will internalize globals (unless on the preserve
   /// list) and, if parallel code generation is enabled, will externalize
   /// all locals.
   void setShouldRestoreGlobalsLinkage(bool Value) {
     ShouldRestoreGlobalsLinkage = Value;
   }
 
-  void addMustPreserveSymbol(StringRef Sym) { MustPreserveSymbols[Sym] = 1; }
+  void addMustPreserveSymbol(StringRef Sym) { MustPreserveSymbols.insert(Sym); }
 
   /// Pass options to the driver and optimization passes.
   ///
   /// These options are not necessarily for debugging purpose (the function
   /// name is misleading).  This function should be called before
   /// LTOCodeGenerator::compilexxx(), and
   /// LTOCodeGenerator::writeMergedModules().
   void setCodeGenDebugOptions(StringRef Opts);

llvm/lib/LTO/LTOCodeGenerator.cpp

void LTOCodeGenerator::initializeLTOPasses() {
   initializeMemCpyOptLegacyPassPass(R);
   initializeDCELegacyPassPass(R);
   initializeCFGSimplifyPassPass(R);
 }
 
 void LTOCodeGenerator::setAsmUndefinedRefs(LTOModule *Mod) {
   const std::vector<StringRef> &undefs = Mod->getAsmUndefinedRefs();
   for (int i = 0, e = undefs.size(); i != e; ++i)
-    AsmUndefinedRefs[undefs[i]] = 1;
+    AsmUndefinedRefs.insert(undefs[i]);
 }
 
 bool LTOCodeGenerator::addModule(LTOModule *Mod) {
   assert(&Mod->getModule().getContext() == &Context &&
          "Expected module in same context");
 
   bool ret = TheLinker->linkInModule(Mod->takeModule());
   setAsmUndefinedRefs(Mod);