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 {
22
23class raw_ostream;
24
25namespace orc {
26
27class SymbolStringPtr;
28
29/// String pool for symbol names used by the JIT.
30class SymbolStringPool {
31 friend class SymbolStringPtr;
32
33 // Implemented in DebugUtils.h.
34 friend raw_ostream &operator<<(raw_ostream &OS, const SymbolStringPool &SSP);
35
36public:
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;
48private:
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.
57class SymbolStringPtr {
58 friend class OrcV2CAPIHelper;
59 friend class SymbolStringPool;
60 friend struct DenseMapInfo<SymbolStringPtr>;
61
62public:
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
122private:
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
161inline SymbolStringPool::~SymbolStringPool() {
162#ifndef NDEBUG
163 clearDeadEntries();
164 assert(Pool.empty() && "Dangling references at pool destruction time");
165#endif // NDEBUG
166}
167
168inline 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
176inline 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
185inline bool SymbolStringPool::empty() const {
186 std::lock_guard<std::mutex> Lock(PoolMutex);
187 return Pool.empty();
188}
189
190} // end namespace orc
191
192template <>
193struct 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

source code of llvm/include/llvm/ExecutionEngine/Orc/SymbolStringPool.h