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 {}; |
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 = 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 (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 | |