LLVM 18.0.0git
SymbolStringPool.h
Go to the documentation of this file.
1//===-- SymbolStringPool.h -- Thread-safe 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 thread-safe 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 {
22
23class raw_ostream;
24
25namespace orc {
26
27class SymbolStringPtrBase;
28class SymbolStringPtr;
29class NonOwningSymbolStringPtr;
30
31/// String pool for symbol names used by the JIT.
34 friend class SymbolStringPtrBase;
35
36 // Implemented in DebugUtils.h.
38
39public:
40 /// Destroy a SymbolStringPool.
42
43 /// Create a symbol string pointer from the given string.
45
46 /// Remove from the pool any entries that are no longer referenced.
47 void clearDeadEntries();
48
49 /// Returns true if the pool is empty.
50 bool empty() const;
51
52private:
53 size_t getRefCount(const SymbolStringPtrBase &S) const;
54
55 using RefCountType = std::atomic<size_t>;
58 mutable std::mutex PoolMutex;
59 PoolMap Pool;
60};
61
62/// Base class for both owning and non-owning symbol-string ptrs.
63///
64/// All symbol-string ptrs are convertible to bool, dereferenceable and
65/// comparable.
66///
67/// SymbolStringPtrBases are default-constructible and constructible
68/// from nullptr to enable comparison with these values.
70 friend class SymbolStringPool;
71 friend struct DenseMapInfo<SymbolStringPtr>;
73
74public:
76 SymbolStringPtrBase(std::nullptr_t) {}
77
78 explicit operator bool() const { return S; }
79
80 StringRef operator*() const { return S->first(); }
81
83 return LHS.S == RHS.S;
84 }
85
87 return !(LHS == RHS);
88 }
89
91 return LHS.S < RHS.S;
92 }
93
94#ifndef NDEBUG
95 // Returns true if the pool entry's ref count is above zero (or if the entry
96 // is an empty or tombstone value). Useful for debugging and testing -- this
97 // method can be used to identify SymbolStringPtrs and
98 // NonOwningSymbolStringPtrs that are pointing to abandoned pool entries.
99 bool poolEntryIsAlive() const {
100 return isRealPoolEntry(S) ? S->getValue() != 0 : true;
101 }
102#endif
103
104protected:
107
109
110 constexpr static uintptr_t EmptyBitPattern =
111 std::numeric_limits<uintptr_t>::max()
113
114 constexpr static uintptr_t TombstoneBitPattern =
115 (std::numeric_limits<uintptr_t>::max() - 1)
117
118 constexpr static uintptr_t InvalidPtrMask =
119 (std::numeric_limits<uintptr_t>::max() - 3)
121
122 // Returns false for null, empty, and tombstone values, true otherwise.
124 return ((reinterpret_cast<uintptr_t>(P) - 1) & InvalidPtrMask) !=
126 }
127
128 size_t getRefCount() const {
129 return isRealPoolEntry(S) ? size_t(S->getValue()) : size_t(0);
130 }
131
132 PoolEntryPtr S = nullptr;
133};
134
135/// Pointer to a pooled string representing a symbol name.
137 friend class OrcV2CAPIHelper;
138 friend class SymbolStringPool;
139 friend struct DenseMapInfo<SymbolStringPtr>;
140
141public:
142 SymbolStringPtr() = default;
143 SymbolStringPtr(std::nullptr_t) {}
145 incRef();
146 }
147
149
151 decRef();
152 S = Other.S;
153 incRef();
154 return *this;
155 }
156
158
160 decRef();
161 S = nullptr;
162 std::swap(S, Other.S);
163 return *this;
164 }
165
166 ~SymbolStringPtr() { decRef(); }
167
168private:
170
171 void incRef() {
172 if (isRealPoolEntry(S))
173 ++S->getValue();
174 }
175
176 void decRef() {
177 if (isRealPoolEntry(S)) {
178 assert(S->getValue() && "Releasing SymbolStringPtr with zero ref count");
179 --S->getValue();
180 }
181 }
182
183 static SymbolStringPtr getEmptyVal() {
184 return SymbolStringPtr(reinterpret_cast<PoolEntryPtr>(EmptyBitPattern));
185 }
186
187 static SymbolStringPtr getTombstoneVal() {
188 return SymbolStringPtr(reinterpret_cast<PoolEntryPtr>(TombstoneBitPattern));
189 }
190};
191
192/// Non-owning SymbolStringPool entry pointer. Instances are comparable with
193/// SymbolStringPtr instances and guaranteed to have the same hash, but do not
194/// affect the ref-count of the pooled string (and are therefore cheaper to
195/// copy).
196///
197/// NonOwningSymbolStringPtrs are silently invalidated if the pool entry's
198/// ref-count drops to zero, so they should only be used in contexts where a
199/// corresponding SymbolStringPtr is known to exist (which will guarantee that
200/// the ref-count stays above zero). E.g. in a graph where nodes are
201/// represented by SymbolStringPtrs the edges can be represented by pairs of
202/// NonOwningSymbolStringPtrs and this will make the introduction of deletion
203/// of edges cheaper.
205 friend struct DenseMapInfo<orc::NonOwningSymbolStringPtr>;
206
207public:
209 explicit NonOwningSymbolStringPtr(const SymbolStringPtr &S)
210 : SymbolStringPtrBase(S) {}
211
212 using SymbolStringPtrBase::operator=;
213
214private:
216
217 static NonOwningSymbolStringPtr getEmptyVal() {
219 reinterpret_cast<PoolEntryPtr>(EmptyBitPattern));
220 }
221
222 static NonOwningSymbolStringPtr getTombstoneVal() {
224 reinterpret_cast<PoolEntryPtr>(TombstoneBitPattern));
225 }
226};
227
231 "SymbolStringPtr constructed from invalid non-owning pointer.");
232
233 if (isRealPoolEntry(S))
234 ++S->getValue();
235}
236
238#ifndef NDEBUG
240 assert(Pool.empty() && "Dangling references at pool destruction time");
241#endif // NDEBUG
242}
243
245 std::lock_guard<std::mutex> Lock(PoolMutex);
247 bool Added;
248 std::tie(I, Added) = Pool.try_emplace(S, 0);
249 return SymbolStringPtr(&*I);
250}
251
253 std::lock_guard<std::mutex> Lock(PoolMutex);
254 for (auto I = Pool.begin(), E = Pool.end(); I != E;) {
255 auto Tmp = I++;
256 if (Tmp->second == 0)
257 Pool.erase(Tmp);
258 }
259}
260
261inline bool SymbolStringPool::empty() const {
262 std::lock_guard<std::mutex> Lock(PoolMutex);
263 return Pool.empty();
264}
265
266inline size_t
267SymbolStringPool::getRefCount(const SymbolStringPtrBase &S) const {
268 return S.getRefCount();
269}
270
271} // end namespace orc
272
273template <>
274struct DenseMapInfo<orc::SymbolStringPtr> {
275
277 return orc::SymbolStringPtr::getEmptyVal();
278 }
279
281 return orc::SymbolStringPtr::getTombstoneVal();
282 }
283
284 static unsigned getHashValue(const orc::SymbolStringPtrBase &V) {
286 }
287
290 return LHS.S == RHS.S;
291 }
292};
293
294template <> struct DenseMapInfo<orc::NonOwningSymbolStringPtr> {
295
297 return orc::NonOwningSymbolStringPtr::getEmptyVal();
298 }
299
301 return orc::NonOwningSymbolStringPtr::getTombstoneVal();
302 }
303
304 static unsigned getHashValue(const orc::SymbolStringPtrBase &V) {
305 return DenseMapInfo<
307 }
308
311 return LHS.S == RHS.S;
312 }
313};
314
315} // end namespace llvm
316
317#endif // LLVM_EXECUTIONENGINE_ORC_SYMBOLSTRINGPOOL_H
This file defines the StringMap class.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file defines the DenseMap class.
#define I(x, y, z)
Definition: MD5.cpp:58
#define P(N)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
Value * RHS
Value * LHS
const ValueTy & getValue() const
StringMapEntry - This is used to represent one value that is inserted into a StringMap.
StringRef first() const
bool empty() const
Definition: StringMap.h:94
iterator end()
Definition: StringMap.h:205
iterator begin()
Definition: StringMap.h:204
void erase(iterator I)
Definition: StringMap.h:382
std::pair< iterator, bool > try_emplace(StringRef Key, ArgsTy &&...Args)
Emplace a new element for the specified key into the map if the key isn't already in the map.
Definition: StringMap.h:341
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
Non-owning SymbolStringPool entry pointer.
String pool for symbol names used by the JIT.
friend raw_ostream & operator<<(raw_ostream &OS, const SymbolStringPool &SSP)
Dump a SymbolStringPool. Useful for debugging dangling-pointer crashes.
Definition: DebugUtils.cpp:299
SymbolStringPtr intern(StringRef S)
Create a symbol string pointer from the given string.
bool empty() const
Returns true if the pool is empty.
~SymbolStringPool()
Destroy a SymbolStringPool.
void clearDeadEntries()
Remove from the pool any entries that are no longer referenced.
Base class for both owning and non-owning symbol-string ptrs.
static bool isRealPoolEntry(PoolEntryPtr P)
friend bool operator!=(SymbolStringPtrBase LHS, SymbolStringPtrBase RHS)
friend bool operator<(SymbolStringPtrBase LHS, SymbolStringPtrBase RHS)
friend bool operator==(SymbolStringPtrBase LHS, SymbolStringPtrBase RHS)
static constexpr uintptr_t InvalidPtrMask
static constexpr uintptr_t EmptyBitPattern
static constexpr uintptr_t TombstoneBitPattern
Pointer to a pooled string representing a symbol name.
SymbolStringPtr(const SymbolStringPtr &Other)
SymbolStringPtr & operator=(SymbolStringPtr &&Other)
SymbolStringPtr & operator=(const SymbolStringPtr &Other)
SymbolStringPtr(SymbolStringPtr &&Other)
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Other
Any other memory.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:860
static orc::NonOwningSymbolStringPtr getEmptyKey()
static bool isEqual(const orc::SymbolStringPtrBase &LHS, const orc::SymbolStringPtrBase &RHS)
static unsigned getHashValue(const orc::SymbolStringPtrBase &V)
static orc::NonOwningSymbolStringPtr getTombstoneKey()
static orc::SymbolStringPtr getEmptyKey()
static bool isEqual(const orc::SymbolStringPtrBase &LHS, const orc::SymbolStringPtrBase &RHS)
static unsigned getHashValue(const orc::SymbolStringPtrBase &V)
static orc::SymbolStringPtr getTombstoneKey()
An information struct used to provide DenseMap with the various necessary components for a given valu...
Definition: DenseMapInfo.h:50
A traits type that is used to handle pointer types and things that are just wrappers for pointers as ...