ADT: Sink the guts of StringMapEntry::Create into StringMapEntryBase

[dexonsmith]

Summary

Sink the interesting parts of StringMapEntry::Create into a new function
StringMapEntryBase::allocateWithKey that's only templated on the
allocator, taking the entry size and alignment as parameters.

I double-checked this doesn't impact clang's compile time performance here:
https://llvm-compile-time-tracker.com/compare.php?from=2d430f902d72b8a1d3bc036a80273ca80af1e338&to=63e5ea3bf2a2b59508e452aee6a9dc0eb369f527&stat=instructions

[dblaikie]

Sounds good - some idle optional thoughts.

llvm/include/llvm/ADT/StringMapEntry.h

30–34

Took me a minute to figure out why this was a member function - since it doesn't need access to any members, etc. Perhaps it could be a free function in a detail or implementation namespace? Not sure if we have a strong convention of how that's done in LLVM.

51–58

Guess this half could be pulled out into a non-template function, but maybe that doesn't tilt the inliner enough & hurts performance?

[dexonsmith]

llvm/include/llvm/ADT/StringMapEntry.h

30–34

I have a tendency to hide things as static class members to avoid having to think of good generic names (the context of StringMapEntryBase makes allocateWithKey clear enough).

I'll think for a bit about the name for the detail/implementation namespace; feel free to recommend one; if I don't find one after a bit of thought I'll probably commit as-is.

One thought is that this could be done in a mnore generic way; MemoryBuffer.cpp has some similar code (it tail allocates the null-terminated identifier, and then also the buffer contents if owned).

51–58

Good point; I bet it's worth it.

Along similar lines, we could add a MallocAllocator overload (unlike BumpPtrAllocator::Allocate, inlining MallocAllocator::Allocate doesn't seem valuable) and define it in StringMap.cpp. I *think* this wouldn't require writing the code twice, since the overload could explicitly call the template:

void *StringMapEntryBase::allocateWithKey(
    size_t EntrySize, size_t EntryAlign, SringRef Key,
    MallocAllocator &Allocator) {
  // Reuse the templated code but instantiate it in the .cpp to avoid code
  // duplication.
  return allocateWithKey<MallocAllocator>(
      EntrySize, EntryAlign, Key, Allocator);
}

I'll look at these as follow ups.

llvm/include/llvm/ADT/StringMapEntry.h

 /// StringMapEntryBase - Shared base class of StringMapEntry instances.
 class StringMapEntryBase {
   size_t keyLength;
 
 public:
   explicit StringMapEntryBase(size_t keyLength) : keyLength(keyLength) {}
 
   size_t getKeyLength() const { return keyLength; }
+
+protected:
+  /// Helper to tail-allocate \p Key. It'd be nice to generalize this so it
+  /// could be reused elsewhere, maybe even taking an llvm::function_ref to
+  /// type-erase the allocator and put it in a source file.
+  template <typename AllocatorTy>
+  static void *allocateWithKey(size_t EntrySize, size_t EntryAlign,
+                               StringRef Key, AllocatorTy &Allocator);
 };
 
+// Define out-of-line to dissuade inlining.
+template <typename AllocatorTy>
+void *StringMapEntryBase::allocateWithKey(size_t EntrySize, size_t EntryAlign,
+                                          StringRef Key,
+                                          AllocatorTy &Allocator) {
+  size_t KeyLength = Key.size();
+
+  // Allocate a new item with space for the string at the end and a null
+  // terminator.
+  size_t AllocSize = EntrySize + KeyLength + 1;
+  void *Allocation = Allocator.Allocate(AllocSize, EntryAlign);
+  assert(Allocation && "Unhandled out-of-memory");
+
+  // Copy the string information.
+  char *Buffer = reinterpret_cast<char *>(Allocation) + EntrySize;
+  if (KeyLength > 0)
+    ::memcpy(Buffer, Key.data(), KeyLength);
+  Buffer[KeyLength] = 0; // Null terminate for convenience of clients.
+  return Allocation;
+}
+
 /// 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 StringMapEntryStorage : public StringMapEntryBase {
 public:
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();
-
-    // Allocate a new item with space for the string at the end and a null
-    // terminator.
-    size_t allocSize = sizeof(StringMapEntry) + keyLength + 1;
-    size_t alignment = alignof(StringMapEntry);
-
-    StringMapEntry *newItem =
-        static_cast<StringMapEntry *>(allocator.Allocate(allocSize, alignment));
-    assert(newItem && "Unhandled out-of-memory");
-
-    // Construct the value.
-    new (newItem) StringMapEntry(keyLength, std::forward<InitTy>(initVals)...);
-
-    // Copy the string information.
-    char *strBuffer = const_cast<char *>(newItem->getKeyData());
-    if (keyLength > 0)
-      memcpy(strBuffer, key.data(), keyLength);
-    strBuffer[keyLength] = 0; // Null terminate for convenience of clients.
-    return newItem;
+    return new (StringMapEntryBase::allocateWithKey(
+        sizeof(StringMapEntry), alignof(StringMapEntry), key, allocator))
+        StringMapEntry(key.size(), std::forward<InitTy>(initVals)...);
   }
 
   /// GetStringMapEntryFromKeyData - Given key data that is known to be embedded
   /// into a StringMapEntry, return the StringMapEntry itself.
   static StringMapEntry &GetStringMapEntryFromKeyData(const char *keyData) {
     char *ptr = const_cast<char *>(keyData) - sizeof(StringMapEntry<ValueTy>);
     return *reinterpret_cast<StringMapEntry *>(ptr);
   }