include/llvm/ExecutionEngine/Orc/SymbolStringPool.h

   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
  21 namespace llvm {
  22 namespace orc {
  23
  24 class SymbolStringPtr;
  25
  26 /// String pool for symbol names used by the JIT.
  27 class SymbolStringPool {
  28   friend class SymbolStringPtr;
  29 public:
  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;
  41 private:
  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.
  50 class SymbolStringPtr {
  51   friend class SymbolStringPool;
  52   friend struct DenseMapInfo<SymbolStringPtr>;
  53
  54 public:
  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
 105 private:
 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
 143 inline SymbolStringPool::~SymbolStringPool() {
 144 #ifndef NDEBUG
 145   clearDeadEntries();
 146   assert(Pool.empty() && "Dangling references at pool destruction time");
 147 #endif // NDEBUG
 148 }
 149
 150 inline 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
 158 inline 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
 167 inline bool SymbolStringPool::empty() const {
 168   std::lock_guard<std::mutex> Lock(PoolMutex);
 169   return Pool.empty();
 170 }
 171
 172 } // end namespace orc
 173
 174 template <>
 175 struct 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