1//===- SymbolStringPool.h - Multi-threaded pool for JIT symbols -*- C++ -*-===// 2// 3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4// See https://llvm.org/LICENSE.txt for license information. 5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6// 7//===----------------------------------------------------------------------===// 8// 9// Contains a multi-threaded string pool suitable for use with ORC. 10// 11//===----------------------------------------------------------------------===// 12 13#ifndef LLVM_EXECUTIONENGINE_ORC_SYMBOLSTRINGPOOL_H 14#define LLVM_EXECUTIONENGINE_ORC_SYMBOLSTRINGPOOL_H 15 16#include "llvm/ADT/DenseMap.h" 17#include "llvm/ADT/StringMap.h" 18#include <atomic> 19#include <mutex> 20 21namespace llvm { 22namespace orc { 23 24class SymbolStringPtr; 25 26/// String pool for symbol names used by the JIT. 27class SymbolStringPool { 28 friend class SymbolStringPtr; 29public: 30 /// Destroy a SymbolStringPool. 31 ~SymbolStringPool(); 32 33 /// Create a symbol string pointer from the given string. 34 SymbolStringPtr intern(StringRef S); 35 36 /// Remove from the pool any entries that are no longer referenced. 37 void clearDeadEntries(); 38 39 /// Returns true if the pool is empty. 40 bool empty() const; 41private: 42 using RefCountType = std::atomic<size_t>; 43 using PoolMap = StringMap<RefCountType>; 44 using PoolMapEntry = StringMapEntry<RefCountType>; 45 mutable std::mutex PoolMutex; 46 PoolMap Pool; 47}; 48 49/// Pointer to a pooled string representing a symbol name. 50class SymbolStringPtr { 51 friend class SymbolStringPool; 52 friend struct DenseMapInfo<SymbolStringPtr>; 53 54public: 55 SymbolStringPtr() = default; 56 SymbolStringPtr(const SymbolStringPtr &Other) 57 : S(Other.S) { 58 if (isRealPoolEntry(S)) 59 ++S->getValue(); 60 } 61 62 SymbolStringPtr& operator=(const SymbolStringPtr &Other) { 63 if (isRealPoolEntry(S)) 64 --S->getValue(); 65 S = Other.S; 66 if (isRealPoolEntry(S)) 67 ++S->getValue(); 68 return *this; 69 } 70 71 SymbolStringPtr(SymbolStringPtr &&Other) : S(nullptr) { 72 std::swap(S, Other.S); 73 } 74 75 SymbolStringPtr& operator=(SymbolStringPtr &&Other) { 76 if (isRealPoolEntry(S)) 77 --S->getValue(); 78 S = nullptr; 79 std::swap(S, Other.S); 80 return *this; 81 } 82 83 ~SymbolStringPtr() { 84 if (isRealPoolEntry(S)) 85 --S->getValue(); 86 } 87 88 StringRef operator*() const { return S->first(); } 89 90 friend bool operator==(const SymbolStringPtr &LHS, 91 const SymbolStringPtr &RHS) { 92 return LHS.S == RHS.S; 93 } 94 95 friend bool operator!=(const SymbolStringPtr &LHS, 96 const SymbolStringPtr &RHS) { 97 return !(LHS == RHS); 98 } 99 100 friend bool operator<(const SymbolStringPtr &LHS, 101 const SymbolStringPtr &RHS) { 102 return LHS.S < RHS.S; 103 } 104 105private: 106 using PoolEntryPtr = SymbolStringPool::PoolMapEntry *; 107 108 SymbolStringPtr(SymbolStringPool::PoolMapEntry *S) 109 : S(S) { 110 if (isRealPoolEntry(S)) 111 ++S->getValue(); 112 } 113 114 // Returns false for null, empty, and tombstone values, true otherwise. 115 bool isRealPoolEntry(PoolEntryPtr P) { 116 return ((reinterpret_cast<uintptr_t>(P) - 1) & InvalidPtrMask) != 117 InvalidPtrMask; 118 } 119 120 static SymbolStringPtr getEmptyVal() { 121 return SymbolStringPtr(reinterpret_cast<PoolEntryPtr>(EmptyBitPattern)); 122 } 123 124 static SymbolStringPtr getTombstoneVal() { 125 return SymbolStringPtr(reinterpret_cast<PoolEntryPtr>(TombstoneBitPattern)); 126 } 127 128 constexpr static uintptr_t EmptyBitPattern = 129 std::numeric_limits<uintptr_t>::max() 130 << PointerLikeTypeTraits<PoolEntryPtr>::NumLowBitsAvailable; 131 132 constexpr static uintptr_t TombstoneBitPattern = 133 (std::numeric_limits<uintptr_t>::max() - 1) 134 << PointerLikeTypeTraits<PoolEntryPtr>::NumLowBitsAvailable; 135 136 constexpr static uintptr_t InvalidPtrMask = 137 (std::numeric_limits<uintptr_t>::max() - 3) 138 << PointerLikeTypeTraits<PoolEntryPtr>::NumLowBitsAvailable; 139 140 PoolEntryPtr S = nullptr; 141}; 142 143inline SymbolStringPool::~SymbolStringPool() { 144#ifndef NDEBUG 145 clearDeadEntries(); 146 assert(Pool.empty() && "Dangling references at pool destruction time"); 147#endif // NDEBUG 148} 149 150inline SymbolStringPtr SymbolStringPool::intern(StringRef S) { 151 std::lock_guard<std::mutex> Lock(PoolMutex); 152 PoolMap::iterator I; 153 bool Added; 154 std::tie(I, Added) = Pool.try_emplace(S, 0); 155 return SymbolStringPtr(&*I); 156} 157 158inline void SymbolStringPool::clearDeadEntries() { 159 std::lock_guard<std::mutex> Lock(PoolMutex); 160 for (auto I = Pool.begin(), E = Pool.end(); I != E;) { 161 auto Tmp = I++; 162 if (Tmp->second == 0) 163 Pool.erase(Tmp); 164 } 165} 166 167inline bool SymbolStringPool::empty() const { 168 std::lock_guard<std::mutex> Lock(PoolMutex); 169 return Pool.empty(); 170} 171 172} // end namespace orc 173 174template <> 175struct DenseMapInfo<orc::SymbolStringPtr> { 176 177 static orc::SymbolStringPtr getEmptyKey() { 178 return orc::SymbolStringPtr::getEmptyVal(); 179 } 180 181 static orc::SymbolStringPtr getTombstoneKey() { 182 return orc::SymbolStringPtr::getTombstoneVal(); 183 } 184 185 static unsigned getHashValue(const orc::SymbolStringPtr &V) { 186 return DenseMapInfo<orc::SymbolStringPtr::PoolEntryPtr>::getHashValue(V.S); 187 } 188 189 static bool isEqual(const orc::SymbolStringPtr &LHS, 190 const orc::SymbolStringPtr &RHS) { 191 return LHS.S == RHS.S; 192 } 193}; 194 195} // end namespace llvm 196 197#endif // LLVM_EXECUTIONENGINE_ORC_SYMBOLSTRINGPOOL_H 198