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 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
231private:
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.
246template <typename KeyT, typename ValueT, typename Config>
247class 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
263public:
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
303template<typename KeyT, typename ValueT, typename Config>
304struct 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
332template<typename DenseMapT, typename KeyT>
333class 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
342public:
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
384template<typename DenseMapT, typename KeyT>
385class 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
394public:
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