1 //===- SymbolStringPool.h - Multi-threaded pool for JIT symbols -*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // Contains a multi-threaded string pool suitable for use with ORC.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_EXECUTIONENGINE_ORC_SYMBOLSTRINGPOOL_H
15 #define LLVM_EXECUTIONENGINE_ORC_SYMBOLSTRINGPOOL_H
16 
17 #include "llvm/ADT/DenseMap.h"
18 #include "llvm/ADT/StringMap.h"
19 #include <atomic>
20 #include <mutex>
21 
22 namespace llvm {
23 namespace orc {
24 
25 class SymbolStringPtr;
26 
27 /// String pool for symbol names used by the JIT.
28 class SymbolStringPool {
29   friend class SymbolStringPtr;
30 public:
31   /// Destroy a SymbolStringPool.
32   ~SymbolStringPool();
33 
34   /// Create a symbol string pointer from the given string.
35   SymbolStringPtr intern(StringRef S);
36 
37   /// Remove from the pool any entries that are no longer referenced.
38   void clearDeadEntries();
39 
40   /// Returns true if the pool is empty.
41   bool empty() const;
42 private:
43   using RefCountType = std::atomic<size_t>;
44   using PoolMap = StringMap<RefCountType>;
45   using PoolMapEntry = StringMapEntry<RefCountType>;
46   mutable std::mutex PoolMutex;
47   PoolMap Pool;
48 };
49 
50 /// Pointer to a pooled string representing a symbol name.
51 class SymbolStringPtr {
52   friend class SymbolStringPool;
53   friend struct DenseMapInfo<SymbolStringPtr>;
54   friend bool operator==(const SymbolStringPtr &LHS,
55                          const SymbolStringPtr &RHS);
56   friend bool operator<(const SymbolStringPtr &LHS, const SymbolStringPtr &RHS);
57 
58   static SymbolStringPool::PoolMapEntry Tombstone;
59 
60 public:
61   SymbolStringPtr() = default;
62   SymbolStringPtr(const SymbolStringPtr &Other)
63     : S(Other.S) {
64     if (S)
65       ++S->getValue();
66   }
67 
68   SymbolStringPtr& operator=(const SymbolStringPtr &Other) {
69     if (S)
70       --S->getValue();
71     S = Other.S;
72     if (S)
73       ++S->getValue();
74     return *this;
75   }
76 
77   SymbolStringPtr(SymbolStringPtr &&Other) : S(nullptr) {
78     std::swap(S, Other.S);
79   }
80 
81   SymbolStringPtr& operator=(SymbolStringPtr &&Other) {
82     if (S)
83       --S->getValue();
84     S = nullptr;
85     std::swap(S, Other.S);
86     return *this;
87   }
88 
89   ~SymbolStringPtr() {
90     if (S)
91       --S->getValue();
92   }
93 
94   StringRef operator*() const { return S->first(); }
95 
96 private:
97 
98   SymbolStringPtr(SymbolStringPool::PoolMapEntry *S)
99       : S(S) {
100     if (S)
101       ++S->getValue();
102   }
103 
104   SymbolStringPool::PoolMapEntry *S = nullptr;
105 };
106 
107 inline bool operator==(const SymbolStringPtr &LHS, const SymbolStringPtr &RHS) {
108   return LHS.S == RHS.S;
109 }
110 
111 inline bool operator!=(const SymbolStringPtr &LHS, const SymbolStringPtr &RHS) {
112   return !(LHS == RHS);
113 }
114 
115 inline bool operator<(const SymbolStringPtr &LHS, const SymbolStringPtr &RHS) {
116   return LHS.S < RHS.S;
117 }
118 
119 inline SymbolStringPool::~SymbolStringPool() {
120 #ifndef NDEBUG
121   clearDeadEntries();
122   assert(Pool.empty() && "Dangling references at pool destruction time");
123 #endif // NDEBUG
124 }
125 
126 inline SymbolStringPtr SymbolStringPool::intern(StringRef S) {
127   std::lock_guard<std::mutex> Lock(PoolMutex);
128   PoolMap::iterator I;
129   bool Added;
130   std::tie(I, Added) = Pool.try_emplace(S, 0);
131   return SymbolStringPtr(&*I);
132 }
133 
134 inline void SymbolStringPool::clearDeadEntries() {
135   std::lock_guard<std::mutex> Lock(PoolMutex);
136   for (auto I = Pool.begin(), E = Pool.end(); I != E;) {
137     auto Tmp = I++;
138     if (Tmp->second == 0)
139       Pool.erase(Tmp);
140   }
141 }
142 
143 inline bool SymbolStringPool::empty() const {
144   std::lock_guard<std::mutex> Lock(PoolMutex);
145   return Pool.empty();
146 }
147 
148 } // end namespace orc
149 
150 template <>
151 struct DenseMapInfo<orc::SymbolStringPtr> {
152 
153   static orc::SymbolStringPtr getEmptyKey() {
154     return orc::SymbolStringPtr();
155   }
156 
157   static orc::SymbolStringPtr getTombstoneKey() {
158     return orc::SymbolStringPtr(&orc::SymbolStringPtr::Tombstone);
159   }
160 
161   static unsigned getHashValue(orc::SymbolStringPtr V) {
162     uintptr_t IV = reinterpret_cast<uintptr_t>(V.S);
163     return unsigned(IV) ^ unsigned(IV >> 9);
164   }
165 
166   static bool isEqual(const orc::SymbolStringPtr &LHS,
167                       const orc::SymbolStringPtr &RHS) {
168     return LHS.S == RHS.S;
169   }
170 };
171 
172 } // end namespace llvm
173 
174 #endif // LLVM_EXECUTIONENGINE_ORC_SYMBOLSTRINGPOOL_H
175