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 21 namespace llvm { 22 23 class raw_ostream; 24 25 namespace orc { 26 27 class SymbolStringPtr; 28 29 /// String pool for symbol names used by the JIT. 30 class SymbolStringPool { 31 friend class SymbolStringPtr; 32 33 // Implemented in DebugUtils.h. 34 friend raw_ostream &operator<<(raw_ostream &OS, const SymbolStringPool &SSP); 35 36 public: 37 /// Destroy a SymbolStringPool. 38 ~SymbolStringPool(); 39 40 /// Create a symbol string pointer from the given string. 41 SymbolStringPtr intern(StringRef S); 42 43 /// Remove from the pool any entries that are no longer referenced. 44 void clearDeadEntries(); 45 46 /// Returns true if the pool is empty. 47 bool empty() const; 48 private: 49 using RefCountType = std::atomic<size_t>; 50 using PoolMap = StringMap<RefCountType>; 51 using PoolMapEntry = StringMapEntry<RefCountType>; 52 mutable std::mutex PoolMutex; 53 PoolMap Pool; 54 }; 55 56 /// Pointer to a pooled string representing a symbol name. 57 class SymbolStringPtr { 58 friend class OrcV2CAPIHelper; 59 friend class SymbolStringPool; 60 friend struct DenseMapInfo<SymbolStringPtr>; 61 62 public: 63 SymbolStringPtr() = default; 64 SymbolStringPtr(std::nullptr_t) {} 65 SymbolStringPtr(const SymbolStringPtr &Other) 66 : S(Other.S) { 67 if (isRealPoolEntry(S)) 68 ++S->getValue(); 69 } 70 71 SymbolStringPtr& operator=(const SymbolStringPtr &Other) { 72 if (isRealPoolEntry(S)) { 73 assert(S->getValue() && "Releasing SymbolStringPtr with zero ref count"); 74 --S->getValue(); 75 } 76 S = Other.S; 77 if (isRealPoolEntry(S)) 78 ++S->getValue(); 79 return *this; 80 } 81 82 SymbolStringPtr(SymbolStringPtr &&Other) : S(nullptr) { 83 std::swap(S, Other.S); 84 } 85 86 SymbolStringPtr& operator=(SymbolStringPtr &&Other) { 87 if (isRealPoolEntry(S)) { 88 assert(S->getValue() && "Releasing SymbolStringPtr with zero ref count"); 89 --S->getValue(); 90 } 91 S = nullptr; 92 std::swap(S, Other.S); 93 return *this; 94 } 95 96 ~SymbolStringPtr() { 97 if (isRealPoolEntry(S)) { 98 assert(S->getValue() && "Releasing SymbolStringPtr with zero ref count"); 99 --S->getValue(); 100 } 101 } 102 103 explicit operator bool() const { return S; } 104 105 StringRef operator*() const { return S->first(); } 106 107 friend bool operator==(const SymbolStringPtr &LHS, 108 const SymbolStringPtr &RHS) { 109 return LHS.S == RHS.S; 110 } 111 112 friend bool operator!=(const SymbolStringPtr &LHS, 113 const SymbolStringPtr &RHS) { 114 return !(LHS == RHS); 115 } 116 117 friend bool operator<(const SymbolStringPtr &LHS, 118 const SymbolStringPtr &RHS) { 119 return LHS.S < RHS.S; 120 } 121 122 private: 123 using PoolEntry = SymbolStringPool::PoolMapEntry; 124 using PoolEntryPtr = PoolEntry *; 125 126 SymbolStringPtr(SymbolStringPool::PoolMapEntry *S) 127 : S(S) { 128 if (isRealPoolEntry(S)) 129 ++S->getValue(); 130 } 131 132 // Returns false for null, empty, and tombstone values, true otherwise. 133 bool isRealPoolEntry(PoolEntryPtr P) { 134 return ((reinterpret_cast<uintptr_t>(P) - 1) & InvalidPtrMask) != 135 InvalidPtrMask; 136 } 137 138 static SymbolStringPtr getEmptyVal() { 139 return SymbolStringPtr(reinterpret_cast<PoolEntryPtr>(EmptyBitPattern)); 140 } 141 142 static SymbolStringPtr getTombstoneVal() { 143 return SymbolStringPtr(reinterpret_cast<PoolEntryPtr>(TombstoneBitPattern)); 144 } 145 146 constexpr static uintptr_t EmptyBitPattern = 147 std::numeric_limits<uintptr_t>::max() 148 << PointerLikeTypeTraits<PoolEntryPtr>::NumLowBitsAvailable; 149 150 constexpr static uintptr_t TombstoneBitPattern = 151 (std::numeric_limits<uintptr_t>::max() - 1) 152 << PointerLikeTypeTraits<PoolEntryPtr>::NumLowBitsAvailable; 153 154 constexpr static uintptr_t InvalidPtrMask = 155 (std::numeric_limits<uintptr_t>::max() - 3) 156 << PointerLikeTypeTraits<PoolEntryPtr>::NumLowBitsAvailable; 157 158 PoolEntryPtr S = nullptr; 159 }; 160 161 inline SymbolStringPool::~SymbolStringPool() { 162 #ifndef NDEBUG 163 clearDeadEntries(); 164 assert(Pool.empty() && "Dangling references at pool destruction time"); 165 #endif // NDEBUG 166 } 167 168 inline SymbolStringPtr SymbolStringPool::intern(StringRef S) { 169 std::lock_guard<std::mutex> Lock(PoolMutex); 170 PoolMap::iterator I; 171 bool Added; 172 std::tie(I, Added) = Pool.try_emplace(S, 0); 173 return SymbolStringPtr(&*I); 174 } 175 176 inline void SymbolStringPool::clearDeadEntries() { 177 std::lock_guard<std::mutex> Lock(PoolMutex); 178 for (auto I = Pool.begin(), E = Pool.end(); I != E;) { 179 auto Tmp = I++; 180 if (Tmp->second == 0) 181 Pool.erase(Tmp); 182 } 183 } 184 185 inline bool SymbolStringPool::empty() const { 186 std::lock_guard<std::mutex> Lock(PoolMutex); 187 return Pool.empty(); 188 } 189 190 } // end namespace orc 191 192 template <> 193 struct DenseMapInfo<orc::SymbolStringPtr> { 194 195 static orc::SymbolStringPtr getEmptyKey() { 196 return orc::SymbolStringPtr::getEmptyVal(); 197 } 198 199 static orc::SymbolStringPtr getTombstoneKey() { 200 return orc::SymbolStringPtr::getTombstoneVal(); 201 } 202 203 static unsigned getHashValue(const orc::SymbolStringPtr &V) { 204 return DenseMapInfo<orc::SymbolStringPtr::PoolEntryPtr>::getHashValue(V.S); 205 } 206 207 static bool isEqual(const orc::SymbolStringPtr &LHS, 208 const orc::SymbolStringPtr &RHS) { 209 return LHS.S == RHS.S; 210 } 211 }; 212 213 } // end namespace llvm 214 215 #endif // LLVM_EXECUTIONENGINE_ORC_SYMBOLSTRINGPOOL_H 216