1//===- ValueMap.h - Safe map from Values to data ----------------*- 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// This file defines the ValueMap class. ValueMap maps Value* or any subclass 11// to an arbitrary other type. It provides the DenseMap interface but updates 12// itself to remain safe when keys are RAUWed or deleted. By default, when a 13// key is RAUWed from V1 to V2, the old mapping V1->target is removed, and a new 14// mapping V2->target is added. If V2 already existed, its old target is 15// overwritten. When a key is deleted, its mapping is removed. 16// 17// You can override a ValueMap's Config parameter to control exactly what 18// happens on RAUW and destruction and to get called back on each event. It's 19// legal to call back into the ValueMap from a Config's callbacks. Config 20// parameters should inherit from ValueMapConfig<KeyT> to get default 21// implementations of all the methods ValueMap uses. See ValueMapConfig for 22// documentation of the functions you can override. 23// 24//===----------------------------------------------------------------------===// 25 26#ifndef LLVM_IR_VALUEMAP_H 27#define LLVM_IR_VALUEMAP_H 28 29#include "llvm/ADT/DenseMap.h" 30#include "llvm/ADT/DenseMapInfo.h" 31#include "llvm/ADT/None.h" 32#include "llvm/ADT/Optional.h" 33#include "llvm/IR/TrackingMDRef.h" 34#include "llvm/IR/ValueHandle.h" 35#include "llvm/Support/Casting.h" 36#include "llvm/Support/Mutex.h" 37#include "llvm/Support/UniqueLock.h" 38#include <algorithm> 39#include <cassert> 40#include <cstddef> 41#include <iterator> 42#include <type_traits> 43#include <utility> 44 45namespace llvm { 46 47template<typename KeyT, typename ValueT, typename Config> 48class ValueMapCallbackVH; 49template<typename DenseMapT, typename KeyT> 50class ValueMapIterator; 51template<typename DenseMapT, typename KeyT> 52class ValueMapConstIterator; 53 54/// This class defines the default behavior for configurable aspects of 55/// ValueMap<>. User Configs should inherit from this class to be as compatible 56/// as possible with future versions of ValueMap. 57template<typename KeyT, typename MutexT = sys::Mutex> 58struct ValueMapConfig { 59 using mutex_type = MutexT; 60 61 /// If FollowRAUW is true, the ValueMap will update mappings on RAUW. If it's 62 /// false, the ValueMap will leave the original mapping in place. 63 enum { FollowRAUW = true }; 64 65 // All methods will be called with a first argument of type ExtraData. The 66 // default implementations in this class take a templated first argument so 67 // that users' subclasses can use any type they want without having to 68 // override all the defaults. 69 struct ExtraData {}; 70 71 template<typename ExtraDataT> 72 static void onRAUW(const ExtraDataT & /*Data*/, KeyT /*Old*/, KeyT /*New*/) {} 73 template<typename ExtraDataT> 74 static void onDelete(const ExtraDataT &/*Data*/, KeyT /*Old*/) {} 75 76 /// Returns a mutex that should be acquired around any changes to the map. 77 /// This is only acquired from the CallbackVH (and held around calls to onRAUW 78 /// and onDelete) and not inside other ValueMap methods. NULL means that no 79 /// mutex is necessary. 80 template<typename ExtraDataT> 81 static mutex_type *getMutex(const ExtraDataT &/*Data*/) { return nullptr; } 82}; 83 84/// See the file comment. 85template<typename KeyT, typename ValueT, typename Config =ValueMapConfig<KeyT>> 86class ValueMap { 87 friend class ValueMapCallbackVH<KeyT, ValueT, Config>; 88 89 using ValueMapCVH = ValueMapCallbackVH<KeyT, ValueT, Config>; 90 using MapT = DenseMap<ValueMapCVH, ValueT, DenseMapInfo<ValueMapCVH>>; 91 using MDMapT = DenseMap<const Metadata *, TrackingMDRef>; 92 using ExtraData = typename Config::ExtraData; 93 94 MapT Map; 95 Optional<MDMapT> MDMap; 96 ExtraData Data; 97 bool MayMapMetadata = true; 98 99public: 100 using key_type = KeyT; 101 using mapped_type = ValueT; 102 using value_type = std::pair<KeyT, ValueT>; 103 using size_type = unsigned; 104 105 explicit ValueMap(unsigned NumInitBuckets = 64) 106 : Map(NumInitBuckets), Data() {} 107 explicit ValueMap(const ExtraData &Data, unsigned NumInitBuckets = 64) 108 : Map(NumInitBuckets), Data(Data) {} 109 ValueMap(const ValueMap &) = delete; 110 ValueMap &operator=(const ValueMap &) = delete; 111 112 bool hasMD() const { return bool(MDMap); } 113 MDMapT &MD() { 114 if (!MDMap) 115 MDMap.emplace(); 116 return *MDMap; 117 } 118 Optional<MDMapT> &getMDMap() { return MDMap; } 119 120 bool mayMapMetadata() const { return MayMapMetadata; } 121 void enableMapMetadata() { MayMapMetadata = true; } 122 void disableMapMetadata() { MayMapMetadata = false; } 123 124 /// Get the mapped metadata, if it's in the map. 125 Optional<Metadata *> getMappedMD(const Metadata *MD) const { 126 if (!MDMap) 127 return None; 128 auto Where = MDMap->find(MD); 129 if (Where == MDMap->end()) 130 return None; 131 return Where->second.get(); 132 } 133 134 using iterator = ValueMapIterator<MapT, KeyT>; 135 using const_iterator = ValueMapConstIterator<MapT, KeyT>; 136 137 inline iterator begin() { return iterator(Map.begin()); } 138 inline iterator end() { return iterator(Map.end()); } 139 inline const_iterator begin() const { return const_iterator(Map.begin()); } 140 inline const_iterator end() const { return const_iterator(Map.end()); } 141 142 bool empty() const { return Map.empty(); } 143 size_type size() const { return Map.size(); } 144 145 /// Grow the map so that it has at least Size buckets. Does not shrink 146 void resize(size_t Size) { Map.resize(Size); } 147 148 void clear() { 149 Map.clear(); 150 MDMap.reset(); 151 } 152 153 /// Return 1 if the specified key is in the map, 0 otherwise. 154 size_type count(const KeyT &Val) const { 155 return Map.find_as(Val) == Map.end() ? 0 : 1; 156 } 157 158 iterator find(const KeyT &Val) { 159 return iterator(Map.find_as(Val)); 160 } 161 const_iterator find(const KeyT &Val) const { 162 return const_iterator(Map.find_as(Val)); 163 } 164 165 /// lookup - Return the entry for the specified key, or a default 166 /// constructed value if no such entry exists. 167 ValueT lookup(const KeyT &Val) const { 168 typename MapT::const_iterator I = Map.find_as(Val); 169 return I != Map.end() ? I->second : ValueT(); 170 } 171 172 // Inserts key,value pair into the map if the key isn't already in the map. 173 // If the key is already in the map, it returns false and doesn't update the 174 // value. 175 std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { 176 auto MapResult = Map.insert(std::make_pair(Wrap(KV.first), KV.second)); 177 return std::make_pair(iterator(MapResult.first), MapResult.second); 178 } 179 180 std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) { 181 auto MapResult = 182 Map.insert(std::make_pair(Wrap(KV.first), std::move(KV.second))); 183 return std::make_pair(iterator(MapResult.first), MapResult.second); 184 } 185 186 /// insert - Range insertion of pairs. 187 template<typename InputIt> 188 void insert(InputIt I, InputIt E) { 189 for (; I != E; ++I) 190 insert(*I); 191 } 192 193 bool erase(const KeyT &Val) { 194 typename MapT::iterator I = Map.find_as(Val); 195 if (I == Map.end()) 196 return false; 197 198 Map.erase(I); 199 return true; 200 } 201 void erase(iterator I) { 202 return Map.erase(I.base()); 203 } 204 205 value_type& FindAndConstruct(const KeyT &Key) { 206 return Map.FindAndConstruct(Wrap(Key)); 207 } 208 209 ValueT &operator[](const KeyT &Key) { 210 return Map[Wrap(Key)]; 211 } 212 213 /// isPointerIntoBucketsArray - Return true if the specified pointer points 214 /// somewhere into the ValueMap's array of buckets (i.e. either to a key or 215 /// value in the ValueMap). 216 bool isPointerIntoBucketsArray(const void *Ptr) const { 217 return Map.isPointerIntoBucketsArray(Ptr); 218 } 219 220 /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets 221 /// array. In conjunction with the previous method, this can be used to 222 /// determine whether an insertion caused the ValueMap to reallocate. 223 const void *getPointerIntoBucketsArray() const { 224 return Map.getPointerIntoBucketsArray(); 225 } 226 227private: 228 // Takes a key being looked up in the map and wraps it into a 229 // ValueMapCallbackVH, the actual key type of the map. We use a helper 230 // function because ValueMapCVH is constructed with a second parameter. 231 ValueMapCVH Wrap(KeyT key) const { 232 // The only way the resulting CallbackVH could try to modify *this (making 233 // the const_cast incorrect) is if it gets inserted into the map. But then 234 // this function must have been called from a non-const method, making the 235 // const_cast ok. 236 return ValueMapCVH(key, const_cast<ValueMap*>(this)); 237 } 238}; 239 240// This CallbackVH updates its ValueMap when the contained Value changes, 241// according to the user's preferences expressed through the Config object. 242template <typename KeyT, typename ValueT, typename Config> 243class ValueMapCallbackVH final : public CallbackVH { 244 friend class ValueMap<KeyT, ValueT, Config>; 245 friend struct DenseMapInfo<ValueMapCallbackVH>; 246 247 using ValueMapT = ValueMap<KeyT, ValueT, Config>; 248 using KeySansPointerT = typename std::remove_pointer<KeyT>::type; 249 250 ValueMapT *Map; 251 252 ValueMapCallbackVH(KeyT Key, ValueMapT *Map) 253 : CallbackVH(const_cast<Value*>(static_cast<const Value*>(Key))), 254 Map(Map) {} 255 256 // Private constructor used to create empty/tombstone DenseMap keys. 257 ValueMapCallbackVH(Value *V) : CallbackVH(V), Map(nullptr) {} 258 259public: 260 KeyT Unwrap() const { return cast_or_null<KeySansPointerT>(getValPtr()); } 261 262 void deleted() override { 263 // Make a copy that won't get changed even when *this is destroyed. 264 ValueMapCallbackVH Copy(*this); 265 typename Config::mutex_type *M = Config::getMutex(Copy.Map->Data); 266 unique_lock<typename Config::mutex_type> Guard; 267 if (M) 268 Guard = unique_lock<typename Config::mutex_type>(*M); 269 Config::onDelete(Copy.Map->Data, Copy.Unwrap()); // May destroy *this. 270 Copy.Map->Map.erase(Copy); // Definitely destroys *this. 271 } 272 273 void allUsesReplacedWith(Value *new_key) override { 274 assert(isa<KeySansPointerT>(new_key) && 275 "Invalid RAUW on key of ValueMap<>"); 276 // Make a copy that won't get changed even when *this is destroyed. 277 ValueMapCallbackVH Copy(*this); 278 typename Config::mutex_type *M = Config::getMutex(Copy.Map->Data); 279 unique_lock<typename Config::mutex_type> Guard; 280 if (M) 281 Guard = unique_lock<typename Config::mutex_type>(*M); 282 283 KeyT typed_new_key = cast<KeySansPointerT>(new_key); 284 // Can destroy *this: 285 Config::onRAUW(Copy.Map->Data, Copy.Unwrap(), typed_new_key); 286 if (Config::FollowRAUW) { 287 typename ValueMapT::MapT::iterator I = Copy.Map->Map.find(Copy); 288 // I could == Copy.Map->Map.end() if the onRAUW callback already 289 // removed the old mapping. 290 if (I != Copy.Map->Map.end()) { 291 ValueT Target(std::move(I->second)); 292 Copy.Map->Map.erase(I); // Definitely destroys *this. 293 Copy.Map->insert(std::make_pair(typed_new_key, std::move(Target))); 294 } 295 } 296 } 297}; 298 299template<typename KeyT, typename ValueT, typename Config> 300struct DenseMapInfo<ValueMapCallbackVH<KeyT, ValueT, Config>> { 301 using VH = ValueMapCallbackVH<KeyT, ValueT, Config>; 302 303 static inline VH getEmptyKey() { 304 return VH(DenseMapInfo<Value *>::getEmptyKey()); 305 } 306 307 static inline VH getTombstoneKey() { 308 return VH(DenseMapInfo<Value *>::getTombstoneKey()); 309 } 310 311 static unsigned getHashValue(const VH &Val) { 312 return DenseMapInfo<KeyT>::getHashValue(Val.Unwrap()); 313 } 314 315 static unsigned getHashValue(const KeyT &Val) { 316 return DenseMapInfo<KeyT>::getHashValue(Val); 317 } 318 319 static bool isEqual(const VH &LHS, const VH &RHS) { 320 return LHS == RHS; 321 } 322 323 static bool isEqual(const KeyT &LHS, const VH &RHS) { 324 return LHS == RHS.getValPtr(); 325 } 326}; 327 328template<typename DenseMapT, typename KeyT> 329class ValueMapIterator : 330 public std::iterator<std::forward_iterator_tag, 331 std::pair<KeyT, typename DenseMapT::mapped_type>, 332 ptrdiff_t> { 333 using BaseT = typename DenseMapT::iterator; 334 using ValueT = typename DenseMapT::mapped_type; 335 336 BaseT I; 337 338public: 339 ValueMapIterator() : I() {} 340 ValueMapIterator(BaseT I) : I(I) {} 341 342 BaseT base() const { return I; } 343 344 struct ValueTypeProxy { 345 const KeyT first; 346 ValueT& second; 347 348 ValueTypeProxy *operator->() { return this; } 349 350 operator std::pair<KeyT, ValueT>() const { 351 return std::make_pair(first, second); 352 } 353 }; 354 355 ValueTypeProxy operator*() const { 356 ValueTypeProxy Result = {I->first.Unwrap(), I->second}; 357 return Result; 358 } 359 360 ValueTypeProxy operator->() const { 361 return operator*(); 362 } 363 364 bool operator==(const ValueMapIterator &RHS) const { 365 return I == RHS.I; 366 } 367 bool operator!=(const ValueMapIterator &RHS) const { 368 return I != RHS.I; 369 } 370 371 inline ValueMapIterator& operator++() { // Preincrement 372 ++I; 373 return *this; 374 } 375 ValueMapIterator operator++(int) { // Postincrement 376 ValueMapIterator tmp = *this; ++*this; return tmp; 377 } 378}; 379 380template<typename DenseMapT, typename KeyT> 381class ValueMapConstIterator : 382 public std::iterator<std::forward_iterator_tag, 383 std::pair<KeyT, typename DenseMapT::mapped_type>, 384 ptrdiff_t> { 385 using BaseT = typename DenseMapT::const_iterator; 386 using ValueT = typename DenseMapT::mapped_type; 387 388 BaseT I; 389 390public: 391 ValueMapConstIterator() : I() {} 392 ValueMapConstIterator(BaseT I) : I(I) {} 393 ValueMapConstIterator(ValueMapIterator<DenseMapT, KeyT> Other) 394 : I(Other.base()) {} 395 396 BaseT base() const { return I; } 397 398 struct ValueTypeProxy { 399 const KeyT first; 400 const ValueT& second; 401 ValueTypeProxy *operator->() { return this; } 402 operator std::pair<KeyT, ValueT>() const { 403 return std::make_pair(first, second); 404 } 405 }; 406 407 ValueTypeProxy operator*() const { 408 ValueTypeProxy Result = {I->first.Unwrap(), I->second}; 409 return Result; 410 } 411 412 ValueTypeProxy operator->() const { 413 return operator*(); 414 } 415 416 bool operator==(const ValueMapConstIterator &RHS) const { 417 return I == RHS.I; 418 } 419 bool operator!=(const ValueMapConstIterator &RHS) const { 420 return I != RHS.I; 421 } 422 423 inline ValueMapConstIterator& operator++() { // Preincrement 424 ++I; 425 return *this; 426 } 427 ValueMapConstIterator operator++(int) { // Postincrement 428 ValueMapConstIterator tmp = *this; ++*this; return tmp; 429 } 430}; 431 432} // end namespace llvm 433 434#endif // LLVM_IR_VALUEMAP_H 435