[ORC] Add a NonOwningSymbolStringPtr utility.

[lhames]

Summary

Introduces a non-owning SymbolStringPool entry pointer. Instances of the new
type can be compared with SymbolStringPtr instances, but do not participate in
ref-counting and are therefore cheaper to copy. This makes it efficient to use
in algorithms that use symbol-strings as ids, e.g. ORC's waiting-on graph. A
future commit will rewrite ORC's waiting-on graph.

[dblaikie]

llvm/include/llvm/ExecutionEngine/Orc/SymbolStringPool.h

51–55

Could this be private and friended to the test class, rather than only in +Asserts? (that way it'd be tested in non-Asserts, and not callable from code/accidentally used in +Asserts builds in the rest of the code)

90–91

If these things are only sizeof(void*) then maybe pass by value, rather than const ref?

[lhames]

llvm/include/llvm/ExecutionEngine/Orc/SymbolStringPool.h

51–55

Ahh -- I was thinking of using this in assertions (and the tests), but wanted to discourage use outside that. To get the best of both worlds I could take your suggestion and make getRefCount private, then introduce a new method:

#ifndef NDEBUG
  bool isPoolEntryValid() const { return getRefCount(); }
#endif

90–91

They could be pass by value. Is there likely to be any benefit on a trivially inline-able method like this? Or is it mostly a style issue?

[lhames]

Address review feedback.

[dblaikie]

llvm/include/llvm/ExecutionEngine/Orc/SymbolStringPool.h

51–55

Ah, fair enough - sounds good :)

Hmm, could the debugging/testing use cases be covered by the private member anyway?

248

Hmm, wouldn't this be non-NDEBUG conditional? (since it's declared unconditionally and called unconditionally from the test code now?)

llvm/unittests/ExecutionEngine/Orc/SymbolStringPoolTest.cpp

25–31

Do you need these locals anymore, now that you have an SP member?

[lhames]

Address latest feedback.

[lhames]

llvm/include/llvm/ExecutionEngine/Orc/SymbolStringPool.h

51–55

Yep -- that's the approach used in the latest patch.

llvm/unittests/ExecutionEngine/Orc/SymbolStringPoolTest.cpp

25–31

Nope -- just missed those lines in the cleanup. Thanks for catching that!

[dblaikie]

Sure, looks good

llvm/include/llvm/ExecutionEngine/Orc/SymbolStringPool.h

90–91

general guideline - maybe makes -O0 builds slightly less bad

llvm/unittests/ExecutionEngine/Orc/SymbolStringPoolTest.cpp

20–22

Awkward to have to wrap the API like this - but I guess the inconvenience of having to touch the class definition for every test to do this http://google.github.io/googletest/reference/testing.html#FRIEND_TEST is annoying too.

llvm/include/llvm/ExecutionEngine/Orc/SymbolStringPool.h

 #include <mutex>
 
 namespace llvm {
 
 class raw_ostream;
 
 namespace orc {
 
+class SymbolStringPtrBase;
 class SymbolStringPtr;
 
 /// String pool for symbol names used by the JIT.
 class SymbolStringPool {
-  friend class SymbolStringPtr;
+  friend class SymbolStringPoolTest;
+  friend class SymbolStringPtrBase;
 
   // Implemented in DebugUtils.h.
   friend raw_ostream &operator<<(raw_ostream &OS, const SymbolStringPool &SSP);
 
 public:
   /// Destroy a SymbolStringPool.
   ~SymbolStringPool();
 
   /// Create a symbol string pointer from the given string.
   SymbolStringPtr intern(StringRef S);
 
   /// Remove from the pool any entries that are no longer referenced.
   void clearDeadEntries();
 
   /// Returns true if the pool is empty.
   bool empty() const;
+
+#ifndef NDEBUG
+  // Useful for debugging and testing: This method can be used to identify
+  // non-owning pointers pointing to unowned pool entries.
+  bool isValid(const SymbolStringPtrBase &S) const { return getRefCount(S); }
+#endif
+
 private:
+  size_t getRefCount(const SymbolStringPtrBase &S) const;
+
   using RefCountType = std::atomic<size_t>;
   using PoolMap = StringMap<RefCountType>;
   using PoolMapEntry = StringMapEntry<RefCountType>;
   mutable std::mutex PoolMutex;
   PoolMap Pool;
 };
 
+/// Base class for both owning and non-owning symbol-string ptrs.
+///
+/// All symbol-string ptrs are convertible to bool, dereferenceable and
+/// comparable.
+///
+/// SymbolStringPtrBases are default-constructible and constructible
+/// from nullptr to enable comparison with these values.
+class SymbolStringPtrBase {
+  friend class SymbolStringPool;
+
+public:
+  SymbolStringPtrBase() = default;
+  SymbolStringPtrBase(std::nullptr_t) {}
+
+  explicit operator bool() const { return S; }
+
+  StringRef operator*() const { return S->first(); }
+
+  friend bool operator==(SymbolStringPtrBase LHS, SymbolStringPtrBase RHS) {
+    return LHS.S == RHS.S;
+  }
+
+  friend bool operator!=(SymbolStringPtrBase LHS, SymbolStringPtrBase RHS) {
+    return !(LHS == RHS);
+  }
+
+  friend bool operator<(SymbolStringPtrBase LHS, SymbolStringPtrBase RHS) {
+    return LHS.S < RHS.S;
+  }
+
+protected:
+  using PoolEntry = SymbolStringPool::PoolMapEntry;
+  using PoolEntryPtr = PoolEntry *;
+
+  SymbolStringPtrBase(PoolEntryPtr S) : S(S) {}
+
+  constexpr static uintptr_t EmptyBitPattern =
+      std::numeric_limits<uintptr_t>::max()
+      << PointerLikeTypeTraits<PoolEntryPtr>::NumLowBitsAvailable;
+
+  constexpr static uintptr_t TombstoneBitPattern =
+      (std::numeric_limits<uintptr_t>::max() - 1)
+      << PointerLikeTypeTraits<PoolEntryPtr>::NumLowBitsAvailable;
+
+  constexpr static uintptr_t InvalidPtrMask =
+      (std::numeric_limits<uintptr_t>::max() - 3)
+      << PointerLikeTypeTraits<PoolEntryPtr>::NumLowBitsAvailable;
+
+  PoolEntryPtr S = nullptr;
+};
+
 /// Pointer to a pooled string representing a symbol name.
-class SymbolStringPtr {
+class SymbolStringPtr : public SymbolStringPtrBase {
   friend class OrcV2CAPIHelper;
   friend class SymbolStringPool;
   friend struct DenseMapInfo<SymbolStringPtr>;
 
 public:
   SymbolStringPtr() = default;
   SymbolStringPtr(std::nullptr_t) {}
-  SymbolStringPtr(const SymbolStringPtr &Other)
-    : S(Other.S) {
+  SymbolStringPtr(const SymbolStringPtr &Other) : SymbolStringPtrBase(Other.S) {
     if (isRealPoolEntry(S))
       ++S->getValue();
   }
 
   SymbolStringPtr& operator=(const SymbolStringPtr &Other) {
     if (isRealPoolEntry(S)) {
       assert(S->getValue() && "Releasing SymbolStringPtr with zero ref count");
       --S->getValue();
     }
     S = Other.S;
     if (isRealPoolEntry(S))
       ++S->getValue();
     return *this;
   }
 
-  SymbolStringPtr(SymbolStringPtr &&Other) : S(nullptr) {
-    std::swap(S, Other.S);
-  }
+  SymbolStringPtr(SymbolStringPtr &&Other) { std::swap(S, Other.S); }
 
   SymbolStringPtr& operator=(SymbolStringPtr &&Other) {
     if (isRealPoolEntry(S)) {
       assert(S->getValue() && "Releasing SymbolStringPtr with zero ref count");
       --S->getValue();
     }
     S = nullptr;
     std::swap(S, Other.S);
     return *this;
   }
 
   ~SymbolStringPtr() {
     if (isRealPoolEntry(S)) {
       assert(S->getValue() && "Releasing SymbolStringPtr with zero ref count");
       --S->getValue();
     }
   }
 
-  explicit operator bool() const { return S; }
-
-  StringRef operator*() const { return S->first(); }
-
-  friend bool operator==(const SymbolStringPtr &LHS,
-                         const SymbolStringPtr &RHS) {
-    return LHS.S == RHS.S;
-  }
-
-  friend bool operator!=(const SymbolStringPtr &LHS,
-                         const SymbolStringPtr &RHS) {
-    return !(LHS == RHS);
-  }
-
-  friend bool operator<(const SymbolStringPtr &LHS,
-                        const SymbolStringPtr &RHS) {
-    return LHS.S < RHS.S;
-  }
-
 private:
-  using PoolEntry = SymbolStringPool::PoolMapEntry;
-  using PoolEntryPtr = PoolEntry *;
-
-  SymbolStringPtr(SymbolStringPool::PoolMapEntry *S)
-      : S(S) {
+  SymbolStringPtr(PoolEntryPtr S) : SymbolStringPtrBase(S) {
     if (isRealPoolEntry(S))
       ++S->getValue();
   }
 
   // Returns false for null, empty, and tombstone values, true otherwise.
   bool isRealPoolEntry(PoolEntryPtr P) {
     return ((reinterpret_cast<uintptr_t>(P) - 1) & InvalidPtrMask) !=
            InvalidPtrMask;
   }
 
   static SymbolStringPtr getEmptyVal() {
     return SymbolStringPtr(reinterpret_cast<PoolEntryPtr>(EmptyBitPattern));
   }
 
   static SymbolStringPtr getTombstoneVal() {
     return SymbolStringPtr(reinterpret_cast<PoolEntryPtr>(TombstoneBitPattern));
   }
+};
 
-  constexpr static uintptr_t EmptyBitPattern =
-      std::numeric_limits<uintptr_t>::max()
-      << PointerLikeTypeTraits<PoolEntryPtr>::NumLowBitsAvailable;
+/// Non-owning SymbolStringPool entry pointer. Instances are comparable with
+/// SymbolStringPtr instances and guaranteed to have the same hash, but do not
+/// affect the ref-count of the pooled string (and are therefore cheaper to
+/// copy).
+///
+/// NonOwningSymbolStringPtrs are silently invalidated if the pool entry's
+/// ref-count drops to zero, so they should only be used in contexts where a
+/// corresponding SymbolStringPtr is known to exist (which will guarantee that
+/// the ref-count stays above zero). E.g. in a graph where nodes are
+/// represented by SymbolStringPtrs the edges can be represented by pairs of
+/// NonOwningSymbolStringPtrs and this will make the introduction of deletion
+/// of edges cheaper.
+class NonOwningSymbolStringPtr : public SymbolStringPtrBase {
+  friend struct DenseMapInfo<orc::NonOwningSymbolStringPtr>;
 
-  constexpr static uintptr_t TombstoneBitPattern =
-      (std::numeric_limits<uintptr_t>::max() - 1)
-      << PointerLikeTypeTraits<PoolEntryPtr>::NumLowBitsAvailable;
+public:
+  NonOwningSymbolStringPtr() = default;
+  explicit NonOwningSymbolStringPtr(const SymbolStringPtr &S)
+      : SymbolStringPtrBase(S) {}
 
-  constexpr static uintptr_t InvalidPtrMask =
-      (std::numeric_limits<uintptr_t>::max() - 3)
-      << PointerLikeTypeTraits<PoolEntryPtr>::NumLowBitsAvailable;
+  using SymbolStringPtrBase::operator=;
 
-  PoolEntryPtr S = nullptr;
+private:
+  NonOwningSymbolStringPtr(PoolEntryPtr S) : SymbolStringPtrBase(S) {}
+
+  static NonOwningSymbolStringPtr getEmptyVal() {
+    return NonOwningSymbolStringPtr(
+        reinterpret_cast<PoolEntryPtr>(EmptyBitPattern));
+  }
+
+  static NonOwningSymbolStringPtr getTombstoneVal() {
+    return NonOwningSymbolStringPtr(
+        reinterpret_cast<PoolEntryPtr>(TombstoneBitPattern));
+  }
 };
 
 inline SymbolStringPool::~SymbolStringPool() {
 #ifndef NDEBUG
   clearDeadEntries();
   assert(Pool.empty() && "Dangling references at pool destruction time");
 #endif // NDEBUG
 }
inline void SymbolStringPool::clearDeadEntries() {
   }
 }
 
 inline bool SymbolStringPool::empty() const {
   std::lock_guard<std::mutex> Lock(PoolMutex);
   return Pool.empty();
 }
 
+inline size_t
+SymbolStringPool::getRefCount(const SymbolStringPtrBase &S) const {
+  return S.S->second;
+}
+
 } // end namespace orc
 
 template <>
 struct DenseMapInfo<orc::SymbolStringPtr> {
 
   static orc::SymbolStringPtr getEmptyKey() {
     return orc::SymbolStringPtr::getEmptyVal();
   }
 
   static orc::SymbolStringPtr getTombstoneKey() {
     return orc::SymbolStringPtr::getTombstoneVal();
   }
 
   static unsigned getHashValue(const orc::SymbolStringPtr &V) {
     return DenseMapInfo<orc::SymbolStringPtr::PoolEntryPtr>::getHashValue(V.S);
   }
 
   static bool isEqual(const orc::SymbolStringPtr &LHS,
                       const orc::SymbolStringPtr &RHS) {
     return LHS.S == RHS.S;
   }
 };
 
+template <> struct DenseMapInfo<orc::NonOwningSymbolStringPtr> {
+
+  static orc::NonOwningSymbolStringPtr getEmptyKey() {
+    return orc::NonOwningSymbolStringPtr::getEmptyVal();
+  }
+
+  static orc::NonOwningSymbolStringPtr getTombstoneKey() {
+    return orc::NonOwningSymbolStringPtr::getTombstoneVal();
+  }
+
+  static unsigned getHashValue(const orc::NonOwningSymbolStringPtr &V) {
+    return DenseMapInfo<
+        orc::NonOwningSymbolStringPtr::PoolEntryPtr>::getHashValue(V.S);
+  }
+
+  static bool isEqual(const orc::NonOwningSymbolStringPtr &LHS,
+                      const orc::NonOwningSymbolStringPtr &RHS) {
+    return LHS.S == RHS.S;
+  }
+};
+
 } // end namespace llvm
 
 #endif // LLVM_EXECUTIONENGINE_ORC_SYMBOLSTRINGPOOL_H

llvm/unittests/ExecutionEngine/Orc/SymbolStringPoolTest.cpp

 //===----- SymbolStringPoolTest.cpp - Unit tests for SymbolStringPool -----===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ExecutionEngine/Orc/SymbolStringPool.h"
 #include "llvm/ExecutionEngine/Orc/DebugUtils.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
 using namespace llvm::orc;
 
-namespace {
+namespace llvm::orc {
+
+class SymbolStringPoolTest : public testing::Test {
+public:
+  size_t getRefCount(const SymbolStringPtrBase &S) const {
+    return SP.getRefCount(S);
+  }
 
-TEST(SymbolStringPool, UniquingAndComparisons) {
+protected:
   SymbolStringPool SP;
+};
+} // namespace llvm::orc
+
+namespace {
+
+TEST_F(SymbolStringPoolTest, UniquingAndComparisons) {
   auto P1 = SP.intern("hello");
 
   std::string S("hel");
   S += "lo";
   auto P2 = SP.intern(S);
 
   auto P3 = SP.intern("goodbye");
 
   EXPECT_EQ(P1, P2) << "Failed to unique entries";
   EXPECT_NE(P1, P3) << "Unequal pooled symbol strings comparing equal";
 
   // We want to test that less-than comparison of SymbolStringPtrs compiles,
   // however we can't test the actual result as this is a pointer comparison and
   // SymbolStringPtr doesn't expose the underlying address of the string.
   (void)(P1 < P3);
 }
 
-TEST(SymbolStringPool, Dereference) {
-  SymbolStringPool SP;
+TEST_F(SymbolStringPoolTest, Dereference) {
   auto Foo = SP.intern("foo");
   EXPECT_EQ(*Foo, "foo") << "Equality on dereferenced string failed";
 }
 
-TEST(SymbolStringPool, ClearDeadEntries) {
-  SymbolStringPool SP;
+TEST_F(SymbolStringPoolTest, ClearDeadEntries) {
   {
     auto P1 = SP.intern("s1");
     SP.clearDeadEntries();
     EXPECT_FALSE(SP.empty()) << "\"s1\" entry in pool should still be retained";
   }
   SP.clearDeadEntries();
   EXPECT_TRUE(SP.empty()) << "pool should be empty";
 }
 
-TEST(SymbolStringPool, DebugDump) {
-  SymbolStringPool SP;
+TEST_F(SymbolStringPoolTest, DebugDump) {
   auto A1 = SP.intern("a");
   auto A2 = A1;
   auto B = SP.intern("b");
 
   std::string DumpString;
   raw_string_ostream(DumpString) << SP;
 
   EXPECT_EQ(DumpString, "a: 2\nb: 1\n");
 }
+
+TEST_F(SymbolStringPoolTest, NonOwningPointerBasics) {
+  auto A = SP.intern("a");
+  auto B = SP.intern("b");
+
+  NonOwningSymbolStringPtr ANP1(A);    // Constuct from SymbolStringPtr.
+  NonOwningSymbolStringPtr ANP2(ANP1); // Copy-construct.
+  NonOwningSymbolStringPtr BNP(B);
+
+  // Equality comparisons.
+  EXPECT_EQ(A, ANP1);
+  EXPECT_EQ(ANP1, ANP2);
+  EXPECT_NE(ANP1, BNP);
+
+  EXPECT_EQ(*ANP1, "a"); // Dereference.
+
+  // Assignment.
+  ANP2 = ANP1;
+  ANP2 = A;
+}
+
+TEST_F(SymbolStringPoolTest, NonOwningPointerRefCounts) {
+  // Check that creating and destroying non-owning pointers doesn't affect
+  // ref-counts.
+  auto A = SP.intern("a");
+  EXPECT_EQ(getRefCount(A), 1U);
+
+  NonOwningSymbolStringPtr ANP(A);
+  EXPECT_EQ(getRefCount(ANP), 1U)
+      << "Construction of NonOwningSymbolStringPtr from SymbolStringPtr "
+         "changed ref-count";
+
+  {
+    NonOwningSymbolStringPtr ANP2(ANP);
+    EXPECT_EQ(getRefCount(ANP2), 1U)
+        << "Copy-construction of NonOwningSymbolStringPtr changed ref-count";
+  }
+
+  EXPECT_EQ(getRefCount(ANP), 1U)
+      << "Destruction of NonOwningSymbolStringPtr changed ref-count";
+
+  {
+    NonOwningSymbolStringPtr ANP2;
+    ANP2 = ANP;
+    EXPECT_EQ(getRefCount(ANP2), 1U)
+        << "Copy-assignment of NonOwningSymbolStringPtr changed ref-count";
+  }
+
+  {
+    NonOwningSymbolStringPtr ANP2(ANP);
+    NonOwningSymbolStringPtr ANP3(std::move(ANP2));
+    EXPECT_EQ(getRefCount(ANP3), 1U)
+        << "Move-construction of NonOwningSymbolStringPtr changed ref-count";
+  }
+
+  {
+    NonOwningSymbolStringPtr ANP2(ANP);
+    NonOwningSymbolStringPtr ANP3;
+    ANP3 = std::move(ANP2);
+    EXPECT_EQ(getRefCount(ANP3), 1U)
+        << "Copy-assignment of NonOwningSymbolStringPtr changed ref-count";
+  }
 }
+} // namespace