LLVM 17.0.0git
ValueMap.h
Go to the documentation of this file.
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"
31#include "llvm/IR/ValueHandle.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>
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
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;
99 using value_type = std::pair<KeyT, ValueT>;
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;
112
113 bool hasMD() const { return bool(MDMap); }
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(MD);
126 if (Where == MDMap->end())
127 return std::nullopt;
128 return Where->second.get();
129 }
130
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(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(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 }
199 return Map.erase(I.base());
200 }
201
203 return Map.FindAndConstruct(Wrap(Key));
204 }
205
206 ValueT &operator[](const KeyT &Key) {
207 return Map[Wrap(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
245 using KeySansPointerT = std::remove_pointer_t<KeyT>;
246
247 ValueMapT *Map;
248
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>
299
300 static inline VH getEmptyKey() {
302 }
303
304 static inline VH getTombstoneKey() {
306 }
307
308 static unsigned getHashValue(const VH &Val) {
310 }
311
312 static unsigned getHashValue(const KeyT &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;
337
339 ValueMapIterator(BaseT I) : I(I) {}
340
341 BaseT base() const { return I; }
342
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
355 ValueTypeProxy Result = {I->first.Unwrap(), I->second};
356 return Result;
357 }
358
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;
391
393 ValueMapConstIterator(BaseT I) : I(I) {}
395 : I(Other.base()) {}
396
397 BaseT base() const { return I; }
398
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
409 ValueTypeProxy Result = {I->first.Unwrap(), I->second};
410 return Result;
411 }
412
414 return operator*();
415 }
416
418 return I == RHS.I;
419 }
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
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file defines DenseMapInfo traits for DenseMap.
This file defines the DenseMap class.
uint64_t Size
#define I(x, y, z)
Definition: MD5.cpp:58
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Value * RHS
Value * LHS
Value handle with callbacks on RAUW and destruction.
Definition: ValueHandle.h:383
Root of the metadata hierarchy.
Definition: Metadata.h:61
Target - Wrapper for Target specific information.
Value * getValPtr() const
Definition: ValueHandle.h:99
KeyT Unwrap() const
Definition: ValueMap.h:257
void allUsesReplacedWith(Value *new_key) override
Callback for Value RAUW.
Definition: ValueMap.h:270
void deleted() override
Callback for Value destruction.
Definition: ValueMap.h:259
ValueMapConstIterator operator++(int)
Definition: ValueMap.h:428
std::ptrdiff_t difference_type
Definition: ValueMap.h:388
ValueMapConstIterator & operator++()
Definition: ValueMap.h:424
bool operator!=(const ValueMapConstIterator &RHS) const
Definition: ValueMap.h:420
ValueTypeProxy operator*() const
Definition: ValueMap.h:408
std::pair< KeyT, typename DenseMapT::mapped_type > value_type
Definition: ValueMap.h:387
bool operator==(const ValueMapConstIterator &RHS) const
Definition: ValueMap.h:417
ValueMapConstIterator(ValueMapIterator< DenseMapT, KeyT > Other)
Definition: ValueMap.h:394
std::forward_iterator_tag iterator_category
Definition: ValueMap.h:386
ValueTypeProxy operator->() const
Definition: ValueMap.h:413
ValueTypeProxy operator*() const
Definition: ValueMap.h:354
ValueMapIterator(BaseT I)
Definition: ValueMap.h:339
std::forward_iterator_tag iterator_category
Definition: ValueMap.h:332
value_type & reference
Definition: ValueMap.h:336
std::ptrdiff_t difference_type
Definition: ValueMap.h:334
BaseT base() const
Definition: ValueMap.h:341
ValueMapIterator & operator++()
Definition: ValueMap.h:370
std::pair< KeyT, typename DenseMapT::mapped_type > value_type
Definition: ValueMap.h:333
bool operator!=(const ValueMapIterator &RHS) const
Definition: ValueMap.h:366
bool operator==(const ValueMapIterator &RHS) const
Definition: ValueMap.h:363
ValueTypeProxy operator->() const
Definition: ValueMap.h:359
ValueMapIterator operator++(int)
Definition: ValueMap.h:374
value_type * pointer
Definition: ValueMap.h:335
See the file comment.
Definition: ValueMap.h:84
void insert(InputIt I, InputIt E)
insert - Range insertion of pairs.
Definition: ValueMap.h:185
ValueT lookup(const KeyT &Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: ValueMap.h:164
ValueMapIterator< MapT, KeyT > iterator
Definition: ValueMap.h:131
bool isPointerIntoBucketsArray(const void *Ptr) const
isPointerIntoBucketsArray - Return true if the specified pointer points somewhere into the ValueMap's...
Definition: ValueMap.h:213
size_type count(const KeyT &Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: ValueMap.h:151
bool empty() const
Definition: ValueMap.h:139
std::pair< KeyT, ValueT > value_type
Definition: ValueMap.h:99
void clear()
Definition: ValueMap.h:145
std::optional< MDMapT > & getMDMap()
Definition: ValueMap.h:119
ValueMap & operator=(ValueMap &&)=delete
value_type & FindAndConstruct(const KeyT &Key)
Definition: ValueMap.h:202
bool hasMD() const
Definition: ValueMap.h:113
iterator find(const KeyT &Val)
Definition: ValueMap.h:155
iterator begin()
Definition: ValueMap.h:134
std::optional< Metadata * > getMappedMD(const Metadata *MD) const
Get the mapped metadata, if it's in the map.
Definition: ValueMap.h:122
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: ValueMap.h:172
const void * getPointerIntoBucketsArray() const
getPointerIntoBucketsArray() - Return an opaque pointer into the buckets array.
Definition: ValueMap.h:220
MDMapT & MD()
Definition: ValueMap.h:114
std::pair< iterator, bool > insert(std::pair< KeyT, ValueT > &&KV)
Definition: ValueMap.h:177
size_type size() const
Definition: ValueMap.h:140
ValueMapConstIterator< MapT, KeyT > const_iterator
Definition: ValueMap.h:132
const_iterator find(const KeyT &Val) const
Definition: ValueMap.h:158
ValueMap(unsigned NumInitBuckets=64)
Definition: ValueMap.h:102
ValueT & operator[](const KeyT &Key)
Definition: ValueMap.h:206
iterator end()
Definition: ValueMap.h:135
void reserve(size_t Size)
Grow the map so that it has at least Size buckets. Does not shrink.
Definition: ValueMap.h:143
ValueMap(const ExtraData &Data, unsigned NumInitBuckets=64)
Definition: ValueMap.h:104
const_iterator end() const
Definition: ValueMap.h:137
void erase(iterator I)
Definition: ValueMap.h:198
const_iterator begin() const
Definition: ValueMap.h:136
bool erase(const KeyT &Val)
Definition: ValueMap.h:190
ValueMap & operator=(const ValueMap &)=delete
ValueMap(const ValueMap &)=delete
ValueMap(ValueMap &&)=delete
LLVM Value Representation.
Definition: Value.h:74
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
static bool isEqual(const KeyT &LHS, const VH &RHS)
Definition: ValueMap.h:320
static bool isEqual(const VH &LHS, const VH &RHS)
Definition: ValueMap.h:316
An information struct used to provide DenseMap with the various necessary components for a given valu...
Definition: DenseMapInfo.h:51
This class defines the default behavior for configurable aspects of ValueMap<>.
Definition: ValueMap.h:56
static mutex_type * getMutex(const ExtraDataT &)
Returns a mutex that should be acquired around any changes to the map.
Definition: ValueMap.h:79
static void onDelete(const ExtraDataT &, KeyT)
Definition: ValueMap.h:72
static void onRAUW(const ExtraDataT &, KeyT, KeyT)
Definition: ValueMap.h:70