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