LLVM 20.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;
36
37 // Implemented in DebugUtils.h.
39
40public:
41 /// Destroy a SymbolStringPool.
43
44 /// Create a symbol string pointer from the given string.
46
47 /// Remove from the pool any entries that are no longer referenced.
48 void clearDeadEntries();
49
50 /// Returns true if the pool is empty.
51 bool empty() const;
52
53private:
54 size_t getRefCount(const SymbolStringPtrBase &S) const;
55
56 using RefCountType = std::atomic<size_t>;
59 mutable std::mutex PoolMutex;
60 PoolMap Pool;
61};
62
63/// Base class for both owning and non-owning symbol-string ptrs.
64///
65/// All symbol-string ptrs are convertible to bool, dereferenceable and
66/// comparable.
67///
68/// SymbolStringPtrBases are default-constructible and constructible
69/// from nullptr to enable comparison with these values.
71 friend class SymbolStringPool;
72 friend struct DenseMapInfo<SymbolStringPtr>;
74
75public:
77 SymbolStringPtrBase(std::nullptr_t) {}
78
79 explicit operator bool() const { return S; }
80
81 StringRef operator*() const { return S->first(); }
82
84 return LHS.S == RHS.S;
85 }
86
88 return !(LHS == RHS);
89 }
90
92 return LHS.S < RHS.S;
93 }
94
95#ifndef NDEBUG
96 // Returns true if the pool entry's ref count is above zero (or if the entry
97 // is an empty or tombstone value). Useful for debugging and testing -- this
98 // method can be used to identify SymbolStringPtrs and
99 // NonOwningSymbolStringPtrs that are pointing to abandoned pool entries.
100 bool poolEntryIsAlive() const {
101 return isRealPoolEntry(S) ? S->getValue() != 0 : true;
102 }
103#endif
104
105protected:
108
110
111 constexpr static uintptr_t EmptyBitPattern =
112 std::numeric_limits<uintptr_t>::max()
114
115 constexpr static uintptr_t TombstoneBitPattern =
116 (std::numeric_limits<uintptr_t>::max() - 1)
118
119 constexpr static uintptr_t InvalidPtrMask =
120 (std::numeric_limits<uintptr_t>::max() - 3)
122
123 // Returns false for null, empty, and tombstone values, true otherwise.
125 return ((reinterpret_cast<uintptr_t>(P) - 1) & InvalidPtrMask) !=
127 }
128
129 size_t getRefCount() const {
130 return isRealPoolEntry(S) ? size_t(S->getValue()) : size_t(0);
131 }
132
133 PoolEntryPtr S = nullptr;
134};
135
136/// Pointer to a pooled string representing a symbol name.
138 friend class SymbolStringPool;
140 friend struct DenseMapInfo<SymbolStringPtr>;
141
142public:
143 SymbolStringPtr() = default;
144 SymbolStringPtr(std::nullptr_t) {}
146 incRef();
147 }
148
150
152 decRef();
153 S = Other.S;
154 incRef();
155 return *this;
156 }
157
159
161 decRef();
162 S = nullptr;
163 std::swap(S, Other.S);
164 return *this;
165 }
166
167 ~SymbolStringPtr() { decRef(); }
168
169private:
171
172 void incRef() {
173 if (isRealPoolEntry(S))
174 ++S->getValue();
175 }
176
177 void decRef() {
178 if (isRealPoolEntry(S)) {
179 assert(S->getValue() && "Releasing SymbolStringPtr with zero ref count");
180 --S->getValue();
181 }
182 }
183
184 static SymbolStringPtr getEmptyVal() {
185 return SymbolStringPtr(reinterpret_cast<PoolEntryPtr>(EmptyBitPattern));
186 }
187
188 static SymbolStringPtr getTombstoneVal() {
189 return SymbolStringPtr(reinterpret_cast<PoolEntryPtr>(TombstoneBitPattern));
190 }
191};
192
193/// Provides unsafe access to ownership operations on SymbolStringPtr.
194/// This class can be used to manage SymbolStringPtr instances from C.
196public:
198
200
201 /// Create an unsafe pool entry ref without changing the ref-count.
203 return S.S;
204 }
205
206 /// Consumes the given SymbolStringPtr without releasing the pool entry.
208 PoolEntry *E = nullptr;
209 std::swap(E, S.S);
210 return E;
211 }
212
213 PoolEntry *rawPtr() { return E; }
214
215 /// Creates a SymbolStringPtr for this entry, with the SymbolStringPtr
216 /// retaining the entry as usual.
218
219 /// Creates a SymbolStringPtr for this entry *without* performing a retain
220 /// operation during construction.
223 std::swap(S.S, E);
224 return S;
225 }
226
227 void retain() { ++E->getValue(); }
228 void release() { --E->getValue(); }
229
230private:
231 PoolEntry *E = nullptr;
232};
233
234/// Non-owning SymbolStringPool entry pointer. Instances are comparable with
235/// SymbolStringPtr instances and guaranteed to have the same hash, but do not
236/// affect the ref-count of the pooled string (and are therefore cheaper to
237/// copy).
238///
239/// NonOwningSymbolStringPtrs are silently invalidated if the pool entry's
240/// ref-count drops to zero, so they should only be used in contexts where a
241/// corresponding SymbolStringPtr is known to exist (which will guarantee that
242/// the ref-count stays above zero). E.g. in a graph where nodes are
243/// represented by SymbolStringPtrs the edges can be represented by pairs of
244/// NonOwningSymbolStringPtrs and this will make the introduction of deletion
245/// of edges cheaper.
247 friend struct DenseMapInfo<orc::NonOwningSymbolStringPtr>;
248
249public:
251 explicit NonOwningSymbolStringPtr(const SymbolStringPtr &S)
252 : SymbolStringPtrBase(S) {}
253
254 using SymbolStringPtrBase::operator=;
255
256private:
258
259 static NonOwningSymbolStringPtr getEmptyVal() {
261 reinterpret_cast<PoolEntryPtr>(EmptyBitPattern));
262 }
263
264 static NonOwningSymbolStringPtr getTombstoneVal() {
266 reinterpret_cast<PoolEntryPtr>(TombstoneBitPattern));
267 }
268};
269
273 "SymbolStringPtr constructed from invalid non-owning pointer.");
274
275 if (isRealPoolEntry(S))
276 ++S->getValue();
277}
278
280#ifndef NDEBUG
282 assert(Pool.empty() && "Dangling references at pool destruction time");
283#endif // NDEBUG
284}
285
287 std::lock_guard<std::mutex> Lock(PoolMutex);
289 bool Added;
290 std::tie(I, Added) = Pool.try_emplace(S, 0);
291 return SymbolStringPtr(&*I);
292}
293
295 std::lock_guard<std::mutex> Lock(PoolMutex);
296 for (auto I = Pool.begin(), E = Pool.end(); I != E;) {
297 auto Tmp = I++;
298 if (Tmp->second == 0)
299 Pool.erase(Tmp);
300 }
301}
302
303inline bool SymbolStringPool::empty() const {
304 std::lock_guard<std::mutex> Lock(PoolMutex);
305 return Pool.empty();
306}
307
308inline size_t
309SymbolStringPool::getRefCount(const SymbolStringPtrBase &S) const {
310 return S.getRefCount();
311}
312
313} // end namespace orc
314
315template <>
316struct DenseMapInfo<orc::SymbolStringPtr> {
317
319 return orc::SymbolStringPtr::getEmptyVal();
320 }
321
323 return orc::SymbolStringPtr::getTombstoneVal();
324 }
325
326 static unsigned getHashValue(const orc::SymbolStringPtrBase &V) {
328 }
329
332 return LHS.S == RHS.S;
333 }
334};
335
336template <> struct DenseMapInfo<orc::NonOwningSymbolStringPtr> {
337
339 return orc::NonOwningSymbolStringPtr::getEmptyVal();
340 }
341
343 return orc::NonOwningSymbolStringPtr::getTombstoneVal();
344 }
345
346 static unsigned getHashValue(const orc::SymbolStringPtrBase &V) {
347 return DenseMapInfo<
349 }
350
353 return LHS.S == RHS.S;
354 }
355};
356
357} // end namespace llvm
358
359#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:103
iterator end()
Definition: StringMap.h:220
iterator begin()
Definition: StringMap.h:219
void erase(iterator I)
Definition: StringMap.h:416
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:368
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
Non-owning SymbolStringPool entry pointer.
Provides unsafe access to ownership operations on SymbolStringPtr.
static SymbolStringPoolEntryUnsafe from(const SymbolStringPtr &S)
Create an unsafe pool entry ref without changing the ref-count.
SymbolStringPtr copyToSymbolStringPtr()
Creates a SymbolStringPtr for this entry, with the SymbolStringPtr retaining the entry as usual.
static SymbolStringPoolEntryUnsafe take(SymbolStringPtr &&S)
Consumes the given SymbolStringPtr without releasing the pool entry.
SymbolStringPtr moveToSymbolStringPtr()
Creates a SymbolStringPtr for this entry without performing a retain operation during construction.
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:303
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:52
A traits type that is used to handle pointer types and things that are just wrappers for pointers as ...