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