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