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