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
43namespace llvm {
44
45template<typename KeyT, typename ValueT, typename Config>
46class ValueMapCallbackVH;
47template<typename DenseMapT, typename KeyT>
48class ValueMapIterator;
49template<typename DenseMapT, typename KeyT>
50class 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.
55template<typename KeyT, typename MutexT = sys::Mutex>
56struct 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 ExtraData {};
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.
83template<typename KeyT, typename ValueT, typename Config =ValueMapConfig<KeyT>>
84class 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 ExtraData = typename Config::ExtraData;
91
92 MapT Map;
93 std::optional<MDMapT> MDMap;
94 ExtraData Data;
95
96public:
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 ValueMap(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
224private:
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.
239template <typename KeyT, typename ValueT, typename Config>
240class 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
256public:
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
296template<typename KeyT, typename ValueT, typename Config>
297struct 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
325template <typename DenseMapT, typename KeyT> class ValueMapIterator {
326 using BaseT = typename DenseMapT::iterator;
327 using ValueT = typename DenseMapT::mapped_type;
328
329 BaseT I;
330
331public:
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
379template <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
385public:
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

source code of llvm/include/llvm/IR/ValueMap.h