diff --git a/llvm/include/llvm/ExecutionEngine/Orc/SymbolStringPool.h b/llvm/include/llvm/ExecutionEngine/Orc/SymbolStringPool.h --- a/llvm/include/llvm/ExecutionEngine/Orc/SymbolStringPool.h +++ b/llvm/include/llvm/ExecutionEngine/Orc/SymbolStringPool.h @@ -24,11 +24,13 @@ 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); @@ -45,7 +47,16 @@ /// 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; using PoolMap = StringMap; using PoolMapEntry = StringMapEntry; @@ -53,8 +64,59 @@ 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::max() + << PointerLikeTypeTraits::NumLowBitsAvailable; + + constexpr static uintptr_t TombstoneBitPattern = + (std::numeric_limits::max() - 1) + << PointerLikeTypeTraits::NumLowBitsAvailable; + + constexpr static uintptr_t InvalidPtrMask = + (std::numeric_limits::max() - 3) + << PointerLikeTypeTraits::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; @@ -62,8 +124,7 @@ 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(); } @@ -79,9 +140,7 @@ 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)) { @@ -100,31 +159,8 @@ } } - 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(); } @@ -142,20 +178,42 @@ static SymbolStringPtr getTombstoneVal() { return SymbolStringPtr(reinterpret_cast(TombstoneBitPattern)); } +}; - constexpr static uintptr_t EmptyBitPattern = - std::numeric_limits::max() - << PointerLikeTypeTraits::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; - constexpr static uintptr_t TombstoneBitPattern = - (std::numeric_limits::max() - 1) - << PointerLikeTypeTraits::NumLowBitsAvailable; +public: + NonOwningSymbolStringPtr() = default; + explicit NonOwningSymbolStringPtr(const SymbolStringPtr &S) + : SymbolStringPtrBase(S) {} - constexpr static uintptr_t InvalidPtrMask = - (std::numeric_limits::max() - 3) - << PointerLikeTypeTraits::NumLowBitsAvailable; + using SymbolStringPtrBase::operator=; - PoolEntryPtr S = nullptr; +private: + NonOwningSymbolStringPtr(PoolEntryPtr S) : SymbolStringPtrBase(S) {} + + static NonOwningSymbolStringPtr getEmptyVal() { + return NonOwningSymbolStringPtr( + reinterpret_cast(EmptyBitPattern)); + } + + static NonOwningSymbolStringPtr getTombstoneVal() { + return NonOwningSymbolStringPtr( + reinterpret_cast(TombstoneBitPattern)); + } }; inline SymbolStringPool::~SymbolStringPool() { @@ -187,6 +245,11 @@ return Pool.empty(); } +inline size_t +SymbolStringPool::getRefCount(const SymbolStringPtrBase &S) const { + return S.S->second; +} + } // end namespace orc template <> @@ -210,6 +273,27 @@ } }; +template <> struct DenseMapInfo { + + 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 diff --git a/llvm/unittests/ExecutionEngine/Orc/SymbolStringPoolTest.cpp b/llvm/unittests/ExecutionEngine/Orc/SymbolStringPoolTest.cpp --- a/llvm/unittests/ExecutionEngine/Orc/SymbolStringPoolTest.cpp +++ b/llvm/unittests/ExecutionEngine/Orc/SymbolStringPoolTest.cpp @@ -13,10 +13,22 @@ 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"); @@ -34,14 +46,12 @@ (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(); @@ -51,8 +61,7 @@ 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"); @@ -62,4 +71,67 @@ 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