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