Query the StringMap only once when creating MDString (NFC)

[mehdi_amini]

Summary

Loading IR with debug info improves MDString::get() from 19ms to 10ms.
This is a rework of D16597 with adding an "emplace" method on the StringMap
to avoid requiring the MDString move ctor to be public.

[dexonsmith]

+dblaikie

If you rename the method emplace_second (since you're only emplacing the
second element, not the full value), then I'm happy with this. However,
David didn't like this patch when I proposed it a year or so ago.

IIRC, at the time David wanted a std::pair-style emplace in
StringMapEntry complete with support for std::piecewise_construct_t. Then

you could call:

auto I = Store.emplace(std::piecewise_construct,
                       std::make_tuple(Str),
                       std::make_tuple());

I still think emplace_second is sufficiently clear since StringMap is so
specialized (and the above looks like boilerplate to me), but this would
be an uncontentious path forward.

[mehdi_amini]

Rename emplace() into emplace_second()

[dblaikie]

Separate unit test for the StringMap changes might be nice.

Could you remind me what the performance problem was that this is saving? Copying the empty MDString into the StringMapEntry? (what's in an MDString that makes it expensive to copy?) Oh it's the extra map lookup, I see.

std::unordered_map::emplace returns the classic <iterator, bool> pair. Perhaps emplace_second should do the same? Rather than relying on being able to detect the invalid default constructed state of the key?

include/llvm/IR/Metadata.h

594–595

Why do we need a move ctor at all if we're supporting emplace? Can we just delete it? (even if we omit it, it should be removed implicitly - same with the move assignment above, I think)

[mehdi_amini]

std::unordered_map::emplace returns the classic <iterator, bool> pair. Perhaps emplace_second should do the same? Rather than relying on being able to detect the invalid default constructed state of the key?

I don't understand what you mean: std::pair<iterator, bool> emplace_second(StringRef Key, ArgsTy &&... Args)

include/llvm/IR/Metadata.h

594–595

StringMap requires movable types (for std::pair I think).

[mehdi_amini]

Add a test for emplace_second

[mehdi_amini]

Remove the need for movable type in StringMap (had to remove an overload for Create())

[dblaikie]

unittests/ADT/StringMapTest.cpp

366

Sign of the parameter doesn't match the sign of the member (& we usually write "unsigned int" as just "unsigned" I think?)

402

Can we do it with a type that cannot be copied or moved? (ie: is this a static property, or a dynamic one?)

[mehdi_amini]

Use a NonMoveableNonCopyableType with the StringMap.

[dexonsmith]

LGTM once David is happy.

[dblaikie]

Looks good - thanks for your patience

[mehdi_amini]

r264386

include/llvm/ADT/StringMap.h

public:
 
   /// 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()); }
 
-  /// Create - Create a StringMapEntry for the specified key and default
-  /// construct the value.
-  template <typename AllocatorTy, typename InitType>
+  /// Create a StringMapEntry for the specified key construct the value using
+  /// \p InitiVals.
+  template <typename AllocatorTy, typename... InitTypes>
   static StringMapEntry *Create(StringRef Key, AllocatorTy &Allocator,
-                                InitType &&InitVal) {
+                                InitTypes &&... InitVals) {
     unsigned KeyLength = Key.size();
 
     // Allocate a new item with space for the string at the end and a null
     // terminator.
     unsigned AllocSize = static_cast<unsigned>(sizeof(StringMapEntry))+
       KeyLength+1;
     unsigned Alignment = alignOf<StringMapEntry>();
 
     StringMapEntry *NewItem =
       static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment));
 
-    // Default construct the value.
-    new (NewItem) StringMapEntry(KeyLength, std::forward<InitType>(InitVal));
+    // Construct the value.
+    new (NewItem)
+        StringMapEntry(KeyLength, std::forward<InitTypes>(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;
   }
 
-  template<typename AllocatorTy>
-  static StringMapEntry *Create(StringRef Key, AllocatorTy &Allocator) {
-    return Create(Key, Allocator, ValueTy());
-  }
-
   /// Create - Create a StringMapEntry with normal malloc/free.
   template<typename InitType>
   static StringMapEntry *Create(StringRef Key, InitType &&InitVal) {
     MallocAllocator A;
     return Create(Key, A, std::forward<InitType>(InitVal));
   }
 
   static StringMapEntry *Create(StringRef Key) {
public:
   /// constructed value if no such entry exists.
   ValueTy lookup(StringRef Key) const {
     const_iterator it = find(Key);
     if (it != end())
       return it->second;
     return ValueTy();
   }
 
+  /// Lookup the ValueTy for the \p Key, or create a default constructed value
+  /// if the key is not in the map.
   ValueTy &operator[](StringRef Key) {
-    return insert(std::make_pair(Key, ValueTy())).first->second;
+    return emplace_second(Key).first->second;
   }
 
   /// count - Return 1 if the element is in the map, 0 otherwise.
   size_type count(StringRef Key) const {
     return find(Key) == end() ? 0 : 1;
   }
 
   /// insert - Insert the specified key/value pair into the map.  If the key
bool insert(MapEntryTy *KeyValue) {
     return true;
   }
 
   /// insert - Inserts the specified key/value pair into the map if the key
   /// isn't already in the map. The bool component of the returned pair is true
   /// if and only if the insertion takes place, and the iterator component of
   /// the pair points to the element with key equivalent to the key of the pair.
   std::pair<iterator, bool> insert(std::pair<StringRef, ValueTy> KV) {
-    unsigned BucketNo = LookupBucketFor(KV.first);
+    return emplace_second(KV.first, std::move(KV.second));
+  }
+
+  /// Emplace a new element for the specified key into the map if the key isn't
+  /// already in the map. The bool component of the returned pair is true
+  /// if and only if the insertion takes place, and the iterator component of
+  /// the pair points to the element with key equivalent to the key of the pair.
+  template <typename... ArgsTy>
+  std::pair<iterator, bool> emplace_second(StringRef Key, ArgsTy &&... Args) {
+    unsigned BucketNo = LookupBucketFor(Key);
     StringMapEntryBase *&Bucket = TheTable[BucketNo];
     if (Bucket && Bucket != getTombstoneVal())
       return std::make_pair(iterator(TheTable + BucketNo, false),
                             false); // Already exists in map.
 
     if (Bucket == getTombstoneVal())
       --NumTombstones;
-    Bucket =
-        MapEntryTy::Create(KV.first, Allocator, std::move(KV.second));
+    Bucket = MapEntryTy::Create(Key, Allocator, std::forward<ArgsTy>(Args)...);
     ++NumItems;
     assert(NumItems + NumTombstones <= NumBuckets);
 
     BucketNo = RehashTable(BucketNo);
     return std::make_pair(iterator(TheTable + BucketNo, false), true);
   }
 
   // clear - Empties out the StringMap

include/llvm/IR/Metadata.h

 class MDString : public Metadata {
   friend class StringMapEntry<MDString>;
 
   MDString(const MDString &) = delete;
   MDString &operator=(MDString &&) = delete;
   MDString &operator=(const MDString &) = delete;
 
   StringMapEntry<MDString> *Entry;
   MDString() : Metadata(MDStringKind, Uniqued), Entry(nullptr) {}
-  MDString(MDString &&) : Metadata(MDStringKind, Uniqued) {}
 
 public:
   static MDString *get(LLVMContext &Context, StringRef Str);
   static MDString *get(LLVMContext &Context, const char *Str) {
     return get(Context, Str ? StringRef(Str) : StringRef());
   }
 
   StringRef getString() const;
 

lib/IR/Metadata.cpp

 }
 
 //===----------------------------------------------------------------------===//
 // MDString implementation.
 //
 
 MDString *MDString::get(LLVMContext &Context, StringRef Str) {
   auto &Store = Context.pImpl->MDStringCache;
-  auto I = Store.find(Str);
-  if (I != Store.end())
-    return &I->second;
-
-  auto *Entry =
-      StringMapEntry<MDString>::Create(Str, Store.getAllocator(), MDString());
-  bool WasInserted = Store.insert(Entry);
-  (void)WasInserted;
-  assert(WasInserted && "Expected entry to be inserted");
-  Entry->second.Entry = Entry;
-  return &Entry->second;
+  auto I = Store.emplace_second(Str);
+  auto &MapEntry = I.first->getValue();
+  if (!I.second)
+    return &MapEntry;
+  MapEntry.Entry = &*I.first;
+  return &MapEntry;
 }
 
 StringRef MDString::getString() const {
   assert(Entry && "Expected to find string map entry");
   return Entry->first();
 }
 
 //===----------------------------------------------------------------------===//

unittests/ADT/StringMapTest.cpp

TEST_F(StringMapTest, MoveDtor) {
 
   B = StringMap<Countable>();
   ASSERT_EQ(InstanceCount, 0);
   ASSERT_TRUE(B.empty());
 }
 
 namespace {
 // Simple class that counts how many moves and copy happens when growing a map
-struct CountCopyAndMove {
+struct CountCtorCopyAndMove {
+  static unsigned Ctor;
   static unsigned Move;
   static unsigned Copy;
-  CountCopyAndMove() {}
+  int Data = 0;
+  CountCtorCopyAndMove(int Data) : Data(Data) { Ctor++; }
+  CountCtorCopyAndMove() { Ctor++; }
 
-  CountCopyAndMove(const CountCopyAndMove &) { Copy++; }
-  CountCopyAndMove &operator=(const CountCopyAndMove &) {
+  CountCtorCopyAndMove(const CountCtorCopyAndMove &) { Copy++; }
+  CountCtorCopyAndMove &operator=(const CountCtorCopyAndMove &) {
     Copy++;
     return *this;
   }
-  CountCopyAndMove(CountCopyAndMove &&) { Move++; }
-  CountCopyAndMove &operator=(const CountCopyAndMove &&) {
+  CountCtorCopyAndMove(CountCtorCopyAndMove &&) { Move++; }
+  CountCtorCopyAndMove &operator=(const CountCtorCopyAndMove &&) {
     Move++;
     return *this;
   }
 };
-unsigned CountCopyAndMove::Copy = 0;
-unsigned CountCopyAndMove::Move = 0;
+unsigned CountCtorCopyAndMove::Copy = 0;
+unsigned CountCtorCopyAndMove::Move = 0;
+unsigned CountCtorCopyAndMove::Ctor = 0;
 
 } // anonymous namespace
 
 // Make sure creating the map with an initial size of N actually gives us enough
 // buckets to insert N items without increasing allocation size.
 TEST(StringMapCustomTest, InitialSizeTest) {
   // 1 is an "edge value", 32 is an arbitrary power of two, and 67 is an
   // arbitrary prime, picked without any good reason.
   for (auto Size : {1, 32, 67}) {
-    StringMap<CountCopyAndMove> Map(Size);
-    CountCopyAndMove::Copy = 0;
-    CountCopyAndMove::Move = 0;
+    StringMap<CountCtorCopyAndMove> Map(Size);
+    CountCtorCopyAndMove::Move = 0;
+    CountCtorCopyAndMove::Copy = 0;
     for (int i = 0; i < Size; ++i)
-      Map.insert(std::make_pair(Twine(i).str(), CountCopyAndMove()));
-    EXPECT_EQ((unsigned)Size * 3, CountCopyAndMove::Move);
-    EXPECT_EQ(0u, CountCopyAndMove::Copy);
+      Map.insert(std::make_pair(Twine(i).str(), CountCtorCopyAndMove()));
+    EXPECT_EQ((unsigned)Size * 3, CountCtorCopyAndMove::Move);
+    EXPECT_EQ(0u, CountCtorCopyAndMove::Copy);
   }
 }
 
+TEST(StringMapCustomTest, BracketOperatorCtor) {
+  StringMap<CountCtorCopyAndMove> Map;
+  CountCtorCopyAndMove::Ctor = 0;
+  Map["abcd"];
+  EXPECT_EQ(1u, CountCtorCopyAndMove::Ctor);
+  // Test that operator[] does not create a value when it is already in the map
+  CountCtorCopyAndMove::Ctor = 0;
+  Map["abcd"];
+  EXPECT_EQ(0u, CountCtorCopyAndMove::Ctor);
+}
+
+namespace {
+struct NonMoveableNonCopyableType {
+  int Data = 0;
+  NonMoveableNonCopyableType() = default;
+  NonMoveableNonCopyableType(int Data) : Data(Data) {}
+  NonMoveableNonCopyableType(const NonMoveableNonCopyableType &) = delete;
+  NonMoveableNonCopyableType(NonMoveableNonCopyableType &&) = delete;
+};
+}
+
+// Test that we can "emplace" an element in the map without involving map/move
+TEST(StringMapCustomTest, EmplaceTest) {
+  StringMap<NonMoveableNonCopyableType> Map;
+  Map.emplace_second("abcd", 42);
+  EXPECT_EQ(1u, Map.count("abcd"));
+  EXPECT_EQ(42, Map["abcd"].Data);
+}
+
 } // end anonymous namespace