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 45 namespace llvm { 46 47 template<typename KeyT, typename ValueT, typename Config> 48 class ValueMapCallbackVH; 49 template<typename DenseMapT, typename KeyT> 50 class ValueMapIterator; 51 template<typename DenseMapT, typename KeyT> 52 class 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. 57 template<typename KeyT, typename MutexT = sys::Mutex> 58 struct 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. 85 template<typename KeyT, typename ValueT, typename Config =ValueMapConfig<KeyT>> 86 class 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 99 public: 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 can't be copied nor moved, beucase the callbacks store pointer 110 // to it. 111 ValueMap(const ValueMap &) = delete; 112 ValueMap(ValueMap &&) = delete; 113 ValueMap &operator=(const ValueMap &) = delete; 114 ValueMap &operator=(ValueMap &&) = delete; 115 116 bool hasMD() const { return bool(MDMap); } 117 MDMapT &MD() { 118 if (!MDMap) 119 MDMap.emplace(); 120 return *MDMap; 121 } 122 Optional<MDMapT> &getMDMap() { return MDMap; } 123 124 bool mayMapMetadata() const { return MayMapMetadata; } 125 void enableMapMetadata() { MayMapMetadata = true; } 126 void disableMapMetadata() { MayMapMetadata = false; } 127 128 /// Get the mapped metadata, if it's in the map. 129 Optional<Metadata *> getMappedMD(const Metadata *MD) const { 130 if (!MDMap) 131 return None; 132 auto Where = MDMap->find(MD); 133 if (Where == MDMap->end()) 134 return None; 135 return Where->second.get(); 136 } 137 138 using iterator = ValueMapIterator<MapT, KeyT>; 139 using const_iterator = ValueMapConstIterator<MapT, KeyT>; 140 141 inline iterator begin() { return iterator(Map.begin()); } 142 inline iterator end() { return iterator(Map.end()); } 143 inline const_iterator begin() const { return const_iterator(Map.begin()); } 144 inline const_iterator end() const { return const_iterator(Map.end()); } 145 146 bool empty() const { return Map.empty(); } 147 size_type size() const { return Map.size(); } 148 149 /// Grow the map so that it has at least Size buckets. Does not shrink 150 void resize(size_t Size) { Map.resize(Size); } 151 152 void clear() { 153 Map.clear(); 154 MDMap.reset(); 155 } 156 157 /// Return 1 if the specified key is in the map, 0 otherwise. 158 size_type count(const KeyT &Val) const { 159 return Map.find_as(Val) == Map.end() ? 0 : 1; 160 } 161 162 iterator find(const KeyT &Val) { 163 return iterator(Map.find_as(Val)); 164 } 165 const_iterator find(const KeyT &Val) const { 166 return const_iterator(Map.find_as(Val)); 167 } 168 169 /// lookup - Return the entry for the specified key, or a default 170 /// constructed value if no such entry exists. 171 ValueT lookup(const KeyT &Val) const { 172 typename MapT::const_iterator I = Map.find_as(Val); 173 return I != Map.end() ? I->second : ValueT(); 174 } 175 176 // Inserts key,value pair into the map if the key isn't already in the map. 177 // If the key is already in the map, it returns false and doesn't update the 178 // value. 179 std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { 180 auto MapResult = Map.insert(std::make_pair(Wrap(KV.first), KV.second)); 181 return std::make_pair(iterator(MapResult.first), MapResult.second); 182 } 183 184 std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) { 185 auto MapResult = 186 Map.insert(std::make_pair(Wrap(KV.first), std::move(KV.second))); 187 return std::make_pair(iterator(MapResult.first), MapResult.second); 188 } 189 190 /// insert - Range insertion of pairs. 191 template<typename InputIt> 192 void insert(InputIt I, InputIt E) { 193 for (; I != E; ++I) 194 insert(*I); 195 } 196 197 bool erase(const KeyT &Val) { 198 typename MapT::iterator I = Map.find_as(Val); 199 if (I == Map.end()) 200 return false; 201 202 Map.erase(I); 203 return true; 204 } 205 void erase(iterator I) { 206 return Map.erase(I.base()); 207 } 208 209 value_type& FindAndConstruct(const KeyT &Key) { 210 return Map.FindAndConstruct(Wrap(Key)); 211 } 212 213 ValueT &operator[](const KeyT &Key) { 214 return Map[Wrap(Key)]; 215 } 216 217 /// isPointerIntoBucketsArray - Return true if the specified pointer points 218 /// somewhere into the ValueMap's array of buckets (i.e. either to a key or 219 /// value in the ValueMap). 220 bool isPointerIntoBucketsArray(const void *Ptr) const { 221 return Map.isPointerIntoBucketsArray(Ptr); 222 } 223 224 /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets 225 /// array. In conjunction with the previous method, this can be used to 226 /// determine whether an insertion caused the ValueMap to reallocate. 227 const void *getPointerIntoBucketsArray() const { 228 return Map.getPointerIntoBucketsArray(); 229 } 230 231 private: 232 // Takes a key being looked up in the map and wraps it into a 233 // ValueMapCallbackVH, the actual key type of the map. We use a helper 234 // function because ValueMapCVH is constructed with a second parameter. 235 ValueMapCVH Wrap(KeyT key) const { 236 // The only way the resulting CallbackVH could try to modify *this (making 237 // the const_cast incorrect) is if it gets inserted into the map. But then 238 // this function must have been called from a non-const method, making the 239 // const_cast ok. 240 return ValueMapCVH(key, const_cast<ValueMap*>(this)); 241 } 242 }; 243 244 // This CallbackVH updates its ValueMap when the contained Value changes, 245 // according to the user's preferences expressed through the Config object. 246 template <typename KeyT, typename ValueT, typename Config> 247 class ValueMapCallbackVH final : public CallbackVH { 248 friend class ValueMap<KeyT, ValueT, Config>; 249 friend struct DenseMapInfo<ValueMapCallbackVH>; 250 251 using ValueMapT = ValueMap<KeyT, ValueT, Config>; 252 using KeySansPointerT = typename std::remove_pointer<KeyT>::type; 253 254 ValueMapT *Map; 255 256 ValueMapCallbackVH(KeyT Key, ValueMapT *Map) 257 : CallbackVH(const_cast<Value*>(static_cast<const Value*>(Key))), 258 Map(Map) {} 259 260 // Private constructor used to create empty/tombstone DenseMap keys. 261 ValueMapCallbackVH(Value *V) : CallbackVH(V), Map(nullptr) {} 262 263 public: 264 KeyT Unwrap() const { return cast_or_null<KeySansPointerT>(getValPtr()); } 265 266 void deleted() override { 267 // Make a copy that won't get changed even when *this is destroyed. 268 ValueMapCallbackVH Copy(*this); 269 typename Config::mutex_type *M = Config::getMutex(Copy.Map->Data); 270 unique_lock<typename Config::mutex_type> Guard; 271 if (M) 272 Guard = unique_lock<typename Config::mutex_type>(*M); 273 Config::onDelete(Copy.Map->Data, Copy.Unwrap()); // May destroy *this. 274 Copy.Map->Map.erase(Copy); // Definitely destroys *this. 275 } 276 277 void allUsesReplacedWith(Value *new_key) override { 278 assert(isa<KeySansPointerT>(new_key) && 279 "Invalid RAUW on key of ValueMap<>"); 280 // Make a copy that won't get changed even when *this is destroyed. 281 ValueMapCallbackVH Copy(*this); 282 typename Config::mutex_type *M = Config::getMutex(Copy.Map->Data); 283 unique_lock<typename Config::mutex_type> Guard; 284 if (M) 285 Guard = unique_lock<typename Config::mutex_type>(*M); 286 287 KeyT typed_new_key = cast<KeySansPointerT>(new_key); 288 // Can destroy *this: 289 Config::onRAUW(Copy.Map->Data, Copy.Unwrap(), typed_new_key); 290 if (Config::FollowRAUW) { 291 typename ValueMapT::MapT::iterator I = Copy.Map->Map.find(Copy); 292 // I could == Copy.Map->Map.end() if the onRAUW callback already 293 // removed the old mapping. 294 if (I != Copy.Map->Map.end()) { 295 ValueT Target(std::move(I->second)); 296 Copy.Map->Map.erase(I); // Definitely destroys *this. 297 Copy.Map->insert(std::make_pair(typed_new_key, std::move(Target))); 298 } 299 } 300 } 301 }; 302 303 template<typename KeyT, typename ValueT, typename Config> 304 struct DenseMapInfo<ValueMapCallbackVH<KeyT, ValueT, Config>> { 305 using VH = ValueMapCallbackVH<KeyT, ValueT, Config>; 306 307 static inline VH getEmptyKey() { 308 return VH(DenseMapInfo<Value *>::getEmptyKey()); 309 } 310 311 static inline VH getTombstoneKey() { 312 return VH(DenseMapInfo<Value *>::getTombstoneKey()); 313 } 314 315 static unsigned getHashValue(const VH &Val) { 316 return DenseMapInfo<KeyT>::getHashValue(Val.Unwrap()); 317 } 318 319 static unsigned getHashValue(const KeyT &Val) { 320 return DenseMapInfo<KeyT>::getHashValue(Val); 321 } 322 323 static bool isEqual(const VH &LHS, const VH &RHS) { 324 return LHS == RHS; 325 } 326 327 static bool isEqual(const KeyT &LHS, const VH &RHS) { 328 return LHS == RHS.getValPtr(); 329 } 330 }; 331 332 template<typename DenseMapT, typename KeyT> 333 class ValueMapIterator : 334 public std::iterator<std::forward_iterator_tag, 335 std::pair<KeyT, typename DenseMapT::mapped_type>, 336 ptrdiff_t> { 337 using BaseT = typename DenseMapT::iterator; 338 using ValueT = typename DenseMapT::mapped_type; 339 340 BaseT I; 341 342 public: 343 ValueMapIterator() : I() {} 344 ValueMapIterator(BaseT I) : I(I) {} 345 346 BaseT base() const { return I; } 347 348 struct ValueTypeProxy { 349 const KeyT first; 350 ValueT& second; 351 352 ValueTypeProxy *operator->() { return this; } 353 354 operator std::pair<KeyT, ValueT>() const { 355 return std::make_pair(first, second); 356 } 357 }; 358 359 ValueTypeProxy operator*() const { 360 ValueTypeProxy Result = {I->first.Unwrap(), I->second}; 361 return Result; 362 } 363 364 ValueTypeProxy operator->() const { 365 return operator*(); 366 } 367 368 bool operator==(const ValueMapIterator &RHS) const { 369 return I == RHS.I; 370 } 371 bool operator!=(const ValueMapIterator &RHS) const { 372 return I != RHS.I; 373 } 374 375 inline ValueMapIterator& operator++() { // Preincrement 376 ++I; 377 return *this; 378 } 379 ValueMapIterator operator++(int) { // Postincrement 380 ValueMapIterator tmp = *this; ++*this; return tmp; 381 } 382 }; 383 384 template<typename DenseMapT, typename KeyT> 385 class ValueMapConstIterator : 386 public std::iterator<std::forward_iterator_tag, 387 std::pair<KeyT, typename DenseMapT::mapped_type>, 388 ptrdiff_t> { 389 using BaseT = typename DenseMapT::const_iterator; 390 using ValueT = typename DenseMapT::mapped_type; 391 392 BaseT I; 393 394 public: 395 ValueMapConstIterator() : I() {} 396 ValueMapConstIterator(BaseT I) : I(I) {} 397 ValueMapConstIterator(ValueMapIterator<DenseMapT, KeyT> Other) 398 : I(Other.base()) {} 399 400 BaseT base() const { return I; } 401 402 struct ValueTypeProxy { 403 const KeyT first; 404 const ValueT& second; 405 ValueTypeProxy *operator->() { return this; } 406 operator std::pair<KeyT, ValueT>() const { 407 return std::make_pair(first, second); 408 } 409 }; 410 411 ValueTypeProxy operator*() const { 412 ValueTypeProxy Result = {I->first.Unwrap(), I->second}; 413 return Result; 414 } 415 416 ValueTypeProxy operator->() const { 417 return operator*(); 418 } 419 420 bool operator==(const ValueMapConstIterator &RHS) const { 421 return I == RHS.I; 422 } 423 bool operator!=(const ValueMapConstIterator &RHS) const { 424 return I != RHS.I; 425 } 426 427 inline ValueMapConstIterator& operator++() { // Preincrement 428 ++I; 429 return *this; 430 } 431 ValueMapConstIterator operator++(int) { // Postincrement 432 ValueMapConstIterator tmp = *this; ++*this; return tmp; 433 } 434 }; 435 436 } // end namespace llvm 437 438 #endif // LLVM_IR_VALUEMAP_H 439