From 96cfeb34745e61ec68d8835c83b9a93a0ddaf8aa Mon Sep 17 00:00:00 2001 From: Lang Hames Date: Tue, 5 Dec 2017 21:44:56 +0000 Subject: [PATCH] [Orc] Add a SymbolStringPool data structure for efficient storage and fast comparison of symbol names. SymbolStringPool is a thread-safe string pool that will be used in upcoming Orc APIs to facilitate efficient storage and fast comparison of symbol name strings. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@319839 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../ExecutionEngine/Orc/SymbolStringPool.h | 133 ++++++++++++++++++ unittests/ExecutionEngine/Orc/CMakeLists.txt | 1 + .../Orc/SymbolStringPoolTest.cpp | 43 ++++++ 3 files changed, 177 insertions(+) create mode 100644 include/llvm/ExecutionEngine/Orc/SymbolStringPool.h create mode 100644 unittests/ExecutionEngine/Orc/SymbolStringPoolTest.cpp diff --git a/include/llvm/ExecutionEngine/Orc/SymbolStringPool.h b/include/llvm/ExecutionEngine/Orc/SymbolStringPool.h new file mode 100644 index 00000000000..185e098497e --- /dev/null +++ b/include/llvm/ExecutionEngine/Orc/SymbolStringPool.h @@ -0,0 +1,133 @@ +//===- SymbolStringPool.h - Multi-threaded pool for JIT symbols -*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Contains a multi-threaded string pool suitable for use with ORC. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_EXECUTIONENGINE_ORC_SYMBOLSTRINGPOOL_H +#define LLVM_EXECUTIONENGINE_ORC_SYMBOLSTRINGPOOL_H + +#include "llvm/ADT/StringMap.h" +#include +#include + +namespace llvm { +namespace orc { + +class SymbolStringPtr; + +/// @brief String pool for symbol names used by the JIT. +class SymbolStringPool { + friend class SymbolStringPtr; +public: + /// @brief Create a symbol string pointer from the given string. + SymbolStringPtr intern(StringRef S); + + /// @brief Remove from the pool any entries that are no longer referenced. + void clearDeadEntries(); + + /// @brief Returns true if the pool is empty. + bool empty() const; +private: + using RefCountType = std::atomic_uint64_t; + using PoolMap = StringMap; + using PoolMapEntry = StringMapEntry; + mutable std::mutex PoolMutex; + PoolMap Pool; +}; + +/// @brief Pointer to a pooled string representing a symbol name. +class SymbolStringPtr { + friend class SymbolStringPool; +public: + SymbolStringPtr() = default; + SymbolStringPtr(const SymbolStringPtr &Other) + : S(Other.S) { + if (S) + ++S->getValue(); + } + + SymbolStringPtr& operator=(const SymbolStringPtr &Other) { + if (S) + --S->getValue(); + S = Other.S; + if (S) + ++S->getValue(); + return *this; + } + + SymbolStringPtr(SymbolStringPtr &&Other) : S(nullptr) { + std::swap(S, Other.S); + } + + SymbolStringPtr& operator=(SymbolStringPtr &&Other) { + if (S) + --S->getValue(); + S = nullptr; + std::swap(S, Other.S); + return *this; + } + + ~SymbolStringPtr() { + if (S) + --S->getValue(); + } + + bool operator==(const SymbolStringPtr &Other) const { + return S == Other.S; + } + + bool operator!=(const SymbolStringPtr &Other) const { + return !(*this == Other); + } + +private: + + SymbolStringPtr(SymbolStringPool::PoolMapEntry *S) + : S(S) { + if (S) + ++S->getValue(); + } + + SymbolStringPool::PoolMapEntry *S = nullptr; +}; + +SymbolStringPtr SymbolStringPool::intern(StringRef S) { + std::lock_guard Lock(PoolMutex); + auto I = Pool.find(S); + if (I != Pool.end()) + return SymbolStringPtr(&*I); + + bool Added; + std::tie(I, Added) = Pool.try_emplace(S, 0); + assert(Added && "Insert should always succeed here"); + return SymbolStringPtr(&*I); +} + +void SymbolStringPool::clearDeadEntries() { + std::lock_guard Lock(PoolMutex); + for (auto I = Pool.begin(), E = Pool.end(); I != E;) { + auto Tmp = std::next(I); + if (I->second == 0) + Pool.erase(I); + I = Tmp; + } +} + +bool SymbolStringPool::empty() const { + std::lock_guard Lock(PoolMutex); + return Pool.empty(); +} + +} // end namespace orc + +} // end namespace llvm + +#endif // LLVM_EXECUTIONENGINE_ORC_SYMBOLSTRINGPOOL_H diff --git a/unittests/ExecutionEngine/Orc/CMakeLists.txt b/unittests/ExecutionEngine/Orc/CMakeLists.txt index e7e3034905e..b6937982313 100644 --- a/unittests/ExecutionEngine/Orc/CMakeLists.txt +++ b/unittests/ExecutionEngine/Orc/CMakeLists.txt @@ -21,6 +21,7 @@ add_llvm_unittest(OrcJITTests RemoteObjectLayerTest.cpp RPCUtilsTest.cpp RTDyldObjectLinkingLayerTest.cpp + SymbolStringPoolTest.cpp ) target_link_libraries(OrcJITTests ${LLVM_PTHREAD_LIB}) diff --git a/unittests/ExecutionEngine/Orc/SymbolStringPoolTest.cpp b/unittests/ExecutionEngine/Orc/SymbolStringPoolTest.cpp new file mode 100644 index 00000000000..ac79541d50c --- /dev/null +++ b/unittests/ExecutionEngine/Orc/SymbolStringPoolTest.cpp @@ -0,0 +1,43 @@ +//===----- SymbolStringPoolTest.cpp - Unit tests for SymbolStringPool -----===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "llvm/ExecutionEngine/Orc/SymbolStringPool.h" +#include "gtest/gtest.h" + +using namespace llvm; +using namespace llvm::orc; + +namespace { + +TEST(SymbolStringPool, UniquingAndEquality) { + SymbolStringPool SP; + 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) << "Inequal pooled symbol strings comparing equal"; +} + +TEST(SymbolStringPool, ClearDeadEntries) { + SymbolStringPool SP; + { + 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"; +} + +} -- 2.50.1