llvm/IR/ValueMap.h

0001 //===- ValueMap.h - Safe map from Values to data ----------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // This file defines the ValueMap class.  ValueMap maps Value* or any subclass
0010 // to an arbitrary other type.  It provides the DenseMap interface but updates
0011 // itself to remain safe when keys are RAUWed or deleted.  By default, when a
0012 // key is RAUWed from V1 to V2, the old mapping V1->target is removed, and a new
0013 // mapping V2->target is added.  If V2 already existed, its old target is
0014 // overwritten.  When a key is deleted, its mapping is removed.
0015 //
0016 // You can override a ValueMap's Config parameter to control exactly what
0017 // happens on RAUW and destruction and to get called back on each event.  It's
0018 // legal to call back into the ValueMap from a Config's callbacks.  Config
0019 // parameters should inherit from ValueMapConfig<KeyT> to get default
0020 // implementations of all the methods ValueMap uses.  See ValueMapConfig for
0021 // documentation of the functions you can override.
0022 //
0023 //===----------------------------------------------------------------------===//
0024
0025 #ifndef LLVM_IR_VALUEMAP_H
0026 #define LLVM_IR_VALUEMAP_H
0027
0028 #include "llvm/ADT/DenseMap.h"
0029 #include "llvm/ADT/DenseMapInfo.h"
0030 #include "llvm/IR/TrackingMDRef.h"
0031 #include "llvm/IR/ValueHandle.h"
0032 #include "llvm/Support/Casting.h"
0033 #include "llvm/Support/Mutex.h"
0034 #include <algorithm>
0035 #include <cassert>
0036 #include <cstddef>
0037 #include <iterator>
0038 #include <mutex>
0039 #include <optional>
0040 #include <type_traits>
0041 #include <utility>
0042
0043 namespace llvm {
0044
0045 template<typename KeyT, typename ValueT, typename Config>
0046 class ValueMapCallbackVH;
0047 template<typename DenseMapT, typename KeyT>
0048 class ValueMapIterator;
0049 template<typename DenseMapT, typename KeyT>
0050 class ValueMapConstIterator;
0051
0052 /// This class defines the default behavior for configurable aspects of
0053 /// ValueMap<>.  User Configs should inherit from this class to be as compatible
0054 /// as possible with future versions of ValueMap.
0055 template<typename KeyT, typename MutexT = sys::Mutex>
0056 struct ValueMapConfig {
0057   using mutex_type = MutexT;
0058
0059   /// If FollowRAUW is true, the ValueMap will update mappings on RAUW. If it's
0060   /// false, the ValueMap will leave the original mapping in place.
0061   enum { FollowRAUW = true };
0062
0063   // All methods will be called with a first argument of type ExtraData.  The
0064   // default implementations in this class take a templated first argument so
0065   // that users' subclasses can use any type they want without having to
0066   // override all the defaults.
0067   struct ExtraData {};
0068
0069   template<typename ExtraDataT>
0070   static void onRAUW(const ExtraDataT & /*Data*/, KeyT /*Old*/, KeyT /*New*/) {}
0071   template<typename ExtraDataT>
0072   static void onDelete(const ExtraDataT &/*Data*/, KeyT /*Old*/) {}
0073
0074   /// Returns a mutex that should be acquired around any changes to the map.
0075   /// This is only acquired from the CallbackVH (and held around calls to onRAUW
0076   /// and onDelete) and not inside other ValueMap methods.  NULL means that no
0077   /// mutex is necessary.
0078   template<typename ExtraDataT>
0079   static mutex_type *getMutex(const ExtraDataT &/*Data*/) { return nullptr; }
0080 };
0081
0082 /// See the file comment.
0083 template<typename KeyT, typename ValueT, typename Config =ValueMapConfig<KeyT>>
0084 class ValueMap {
0085   friend class ValueMapCallbackVH<KeyT, ValueT, Config>;
0086
0087   using ValueMapCVH = ValueMapCallbackVH<KeyT, ValueT, Config>;
0088   using MapT = DenseMap<ValueMapCVH, ValueT, DenseMapInfo<ValueMapCVH>>;
0089   using MDMapT = DenseMap<const Metadata *, TrackingMDRef>;
0090   using ExtraData = typename Config::ExtraData;
0091
0092   MapT Map;
0093   std::optional<MDMapT> MDMap;
0094   ExtraData Data;
0095
0096 public:
0097   using key_type = KeyT;
0098   using mapped_type = ValueT;
0099   using value_type = std::pair<KeyT, ValueT>;
0100   using size_type = unsigned;
0101
0102   explicit ValueMap(unsigned NumInitBuckets = 64)
0103       : Map(NumInitBuckets), Data() {}
0104   explicit ValueMap(const ExtraData &Data, unsigned NumInitBuckets = 64)
0105       : Map(NumInitBuckets), Data(Data) {}
0106   // ValueMap can't be copied nor moved, because the callbacks store pointer to
0107   // it.
0108   ValueMap(const ValueMap &) = delete;
0109   ValueMap(ValueMap &&) = delete;
0110   ValueMap &operator=(const ValueMap &) = delete;
0111   ValueMap &operator=(ValueMap &&) = delete;
0112
0113   bool hasMD() const { return bool(MDMap); }
0114   MDMapT &MD() {
0115     if (!MDMap)
0116       MDMap.emplace();
0117     return *MDMap;
0118   }
0119   std::optional<MDMapT> &getMDMap() { return MDMap; }
0120
0121   /// Get the mapped metadata, if it's in the map.
0122   std::optional<Metadata *> getMappedMD(const Metadata *MD) const {
0123     if (!MDMap)
0124       return std::nullopt;
0125     auto Where = MDMap->find(MD);
0126     if (Where == MDMap->end())
0127       return std::nullopt;
0128     return Where->second.get();
0129   }
0130
0131   using iterator = ValueMapIterator<MapT, KeyT>;
0132   using const_iterator = ValueMapConstIterator<MapT, KeyT>;
0133
0134   inline iterator begin() { return iterator(Map.begin()); }
0135   inline iterator end() { return iterator(Map.end()); }
0136   inline const_iterator begin() const { return const_iterator(Map.begin()); }
0137   inline const_iterator end() const { return const_iterator(Map.end()); }
0138
0139   bool empty() const { return Map.empty(); }
0140   size_type size() const { return Map.size(); }
0141
0142   /// Grow the map so that it has at least Size buckets. Does not shrink
0143   void reserve(size_t Size) { Map.reserve(Size); }
0144
0145   void clear() {
0146     Map.clear();
0147     MDMap.reset();
0148   }
0149
0150   /// Return 1 if the specified key is in the map, 0 otherwise.
0151   size_type count(const KeyT &Val) const {
0152     return Map.find_as(Val) == Map.end() ? 0 : 1;
0153   }
0154
0155   iterator find(const KeyT &Val) {
0156     return iterator(Map.find_as(Val));
0157   }
0158   const_iterator find(const KeyT &Val) const {
0159     return const_iterator(Map.find_as(Val));
0160   }
0161
0162   /// lookup - Return the entry for the specified key, or a default
0163   /// constructed value if no such entry exists.
0164   ValueT lookup(const KeyT &Val) const {
0165     typename MapT::const_iterator I = Map.find_as(Val);
0166     return I != Map.end() ? I->second : ValueT();
0167   }
0168
0169   // Inserts key,value pair into the map if the key isn't already in the map.
0170   // If the key is already in the map, it returns false and doesn't update the
0171   // value.
0172   std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {
0173     auto MapResult = Map.insert(std::make_pair(Wrap(KV.first), KV.second));
0174     return std::make_pair(iterator(MapResult.first), MapResult.second);
0175   }
0176
0177   std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) {
0178     auto MapResult =
0179         Map.insert(std::make_pair(Wrap(KV.first), std::move(KV.second)));
0180     return std::make_pair(iterator(MapResult.first), MapResult.second);
0181   }
0182
0183   /// insert - Range insertion of pairs.
0184   template<typename InputIt>
0185   void insert(InputIt I, InputIt E) {
0186     for (; I != E; ++I)
0187       insert(*I);
0188   }
0189
0190   bool erase(const KeyT &Val) {
0191     typename MapT::iterator I = Map.find_as(Val);
0192     if (I == Map.end())
0193       return false;
0194
0195     Map.erase(I);
0196     return true;
0197   }
0198   void erase(iterator I) {
0199     return Map.erase(I.base());
0200   }
0201
0202   value_type& FindAndConstruct(const KeyT &Key) {
0203     return Map.FindAndConstruct(Wrap(Key));
0204   }
0205
0206   ValueT &operator[](const KeyT &Key) {
0207     return Map[Wrap(Key)];
0208   }
0209
0210   /// isPointerIntoBucketsArray - Return true if the specified pointer points
0211   /// somewhere into the ValueMap's array of buckets (i.e. either to a key or
0212   /// value in the ValueMap).
0213   bool isPointerIntoBucketsArray(const void *Ptr) const {
0214     return Map.isPointerIntoBucketsArray(Ptr);
0215   }
0216
0217   /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets
0218   /// array.  In conjunction with the previous method, this can be used to
0219   /// determine whether an insertion caused the ValueMap to reallocate.
0220   const void *getPointerIntoBucketsArray() const {
0221     return Map.getPointerIntoBucketsArray();
0222   }
0223
0224 private:
0225   // Takes a key being looked up in the map and wraps it into a
0226   // ValueMapCallbackVH, the actual key type of the map.  We use a helper
0227   // function because ValueMapCVH is constructed with a second parameter.
0228   ValueMapCVH Wrap(KeyT key) const {
0229     // The only way the resulting CallbackVH could try to modify *this (making
0230     // the const_cast incorrect) is if it gets inserted into the map.  But then
0231     // this function must have been called from a non-const method, making the
0232     // const_cast ok.
0233     return ValueMapCVH(key, const_cast<ValueMap*>(this));
0234   }
0235 };
0236
0237 // This CallbackVH updates its ValueMap when the contained Value changes,
0238 // according to the user's preferences expressed through the Config object.
0239 template <typename KeyT, typename ValueT, typename Config>
0240 class ValueMapCallbackVH final : public CallbackVH {
0241   friend class ValueMap<KeyT, ValueT, Config>;
0242   friend struct DenseMapInfo<ValueMapCallbackVH>;
0243
0244   using ValueMapT = ValueMap<KeyT, ValueT, Config>;
0245   using KeySansPointerT = std::remove_pointer_t<KeyT>;
0246
0247   ValueMapT *Map;
0248
0249   ValueMapCallbackVH(KeyT Key, ValueMapT *Map)
0250       : CallbackVH(const_cast<Value*>(static_cast<const Value*>(Key))),
0251         Map(Map) {}
0252
0253   // Private constructor used to create empty/tombstone DenseMap keys.
0254   ValueMapCallbackVH(Value *V) : CallbackVH(V), Map(nullptr) {}
0255
0256 public:
0257   KeyT Unwrap() const { return cast_or_null<KeySansPointerT>(getValPtr()); }
0258
0259   void deleted() override {
0260     // Make a copy that won't get changed even when *this is destroyed.
0261     ValueMapCallbackVH Copy(*this);
0262     typename Config::mutex_type *M = Config::getMutex(Copy.Map->Data);
0263     std::unique_lock<typename Config::mutex_type> Guard;
0264     if (M)
0265       Guard = std::unique_lock<typename Config::mutex_type>(*M);
0266     Config::onDelete(Copy.Map->Data, Copy.Unwrap());  // May destroy *this.
0267     Copy.Map->Map.erase(Copy);  // Definitely destroys *this.
0268   }
0269
0270   void allUsesReplacedWith(Value *new_key) override {
0271     assert(isa<KeySansPointerT>(new_key) &&
0272            "Invalid RAUW on key of ValueMap<>");
0273     // Make a copy that won't get changed even when *this is destroyed.
0274     ValueMapCallbackVH Copy(*this);
0275     typename Config::mutex_type *M = Config::getMutex(Copy.Map->Data);
0276     std::unique_lock<typename Config::mutex_type> Guard;
0277     if (M)
0278       Guard = std::unique_lock<typename Config::mutex_type>(*M);
0279
0280     KeyT typed_new_key = cast<KeySansPointerT>(new_key);
0281     // Can destroy *this:
0282     Config::onRAUW(Copy.Map->Data, Copy.Unwrap(), typed_new_key);
0283     if (Config::FollowRAUW) {
0284       typename ValueMapT::MapT::iterator I = Copy.Map->Map.find(Copy);
0285       // I could == Copy.Map->Map.end() if the onRAUW callback already
0286       // removed the old mapping.
0287       if (I != Copy.Map->Map.end()) {
0288         ValueT Target(std::move(I->second));
0289         Copy.Map->Map.erase(I);  // Definitely destroys *this.
0290         Copy.Map->insert(std::make_pair(typed_new_key, std::move(Target)));
0291       }
0292     }
0293   }
0294 };
0295
0296 template<typename KeyT, typename ValueT, typename Config>
0297 struct DenseMapInfo<ValueMapCallbackVH<KeyT, ValueT, Config>> {
0298   using VH = ValueMapCallbackVH<KeyT, ValueT, Config>;
0299
0300   static inline VH getEmptyKey() {
0301     return VH(DenseMapInfo<Value *>::getEmptyKey());
0302   }
0303
0304   static inline VH getTombstoneKey() {
0305     return VH(DenseMapInfo<Value *>::getTombstoneKey());
0306   }
0307
0308   static unsigned getHashValue(const VH &Val) {
0309     return DenseMapInfo<KeyT>::getHashValue(Val.Unwrap());
0310   }
0311
0312   static unsigned getHashValue(const KeyT &Val) {
0313     return DenseMapInfo<KeyT>::getHashValue(Val);
0314   }
0315
0316   static bool isEqual(const VH &LHS, const VH &RHS) {
0317     return LHS == RHS;
0318   }
0319
0320   static bool isEqual(const KeyT &LHS, const VH &RHS) {
0321     return LHS == RHS.getValPtr();
0322   }
0323 };
0324
0325 template <typename DenseMapT, typename KeyT> class ValueMapIterator {
0326   using BaseT = typename DenseMapT::iterator;
0327   using ValueT = typename DenseMapT::mapped_type;
0328
0329   BaseT I;
0330
0331 public:
0332   using iterator_category = std::forward_iterator_tag;
0333   using value_type = std::pair<KeyT, typename DenseMapT::mapped_type>;
0334   using difference_type = std::ptrdiff_t;
0335   using pointer = value_type *;
0336   using reference = value_type &;
0337
0338   ValueMapIterator() : I() {}
0339   ValueMapIterator(BaseT I) : I(I) {}
0340
0341   BaseT base() const { return I; }
0342
0343   struct ValueTypeProxy {
0344     const KeyT first;
0345     ValueT& second;
0346
0347     ValueTypeProxy *operator->() { return this; }
0348
0349     operator std::pair<KeyT, ValueT>() const {
0350       return std::make_pair(first, second);
0351     }
0352   };
0353
0354   ValueTypeProxy operator*() const {
0355     ValueTypeProxy Result = {I->first.Unwrap(), I->second};
0356     return Result;
0357   }
0358
0359   ValueTypeProxy operator->() const {
0360     return operator*();
0361   }
0362
0363   bool operator==(const ValueMapIterator &RHS) const {
0364     return I == RHS.I;
0365   }
0366   bool operator!=(const ValueMapIterator &RHS) const {
0367     return I != RHS.I;
0368   }
0369
0370   inline ValueMapIterator& operator++() {  // Preincrement
0371     ++I;
0372     return *this;
0373   }
0374   ValueMapIterator operator++(int) {  // Postincrement
0375     ValueMapIterator tmp = *this; ++*this; return tmp;
0376   }
0377 };
0378
0379 template <typename DenseMapT, typename KeyT> class ValueMapConstIterator {
0380   using BaseT = typename DenseMapT::const_iterator;
0381   using ValueT = typename DenseMapT::mapped_type;
0382
0383   BaseT I;
0384
0385 public:
0386   using iterator_category = std::forward_iterator_tag;
0387   using value_type = std::pair<KeyT, typename DenseMapT::mapped_type>;
0388   using difference_type = std::ptrdiff_t;
0389   using pointer = value_type *;
0390   using reference = value_type &;
0391
0392   ValueMapConstIterator() : I() {}
0393   ValueMapConstIterator(BaseT I) : I(I) {}
0394   ValueMapConstIterator(ValueMapIterator<DenseMapT, KeyT> Other)
0395     : I(Other.base()) {}
0396
0397   BaseT base() const { return I; }
0398
0399   struct ValueTypeProxy {
0400     const KeyT first;
0401     const ValueT& second;
0402     ValueTypeProxy *operator->() { return this; }
0403     operator std::pair<KeyT, ValueT>() const {
0404       return std::make_pair(first, second);
0405     }
0406   };
0407
0408   ValueTypeProxy operator*() const {
0409     ValueTypeProxy Result = {I->first.Unwrap(), I->second};
0410     return Result;
0411   }
0412
0413   ValueTypeProxy operator->() const {
0414     return operator*();
0415   }
0416
0417   bool operator==(const ValueMapConstIterator &RHS) const {
0418     return I == RHS.I;
0419   }
0420   bool operator!=(const ValueMapConstIterator &RHS) const {
0421     return I != RHS.I;
0422   }
0423
0424   inline ValueMapConstIterator& operator++() {  // Preincrement
0425     ++I;
0426     return *this;
0427   }
0428   ValueMapConstIterator operator++(int) {  // Postincrement
0429     ValueMapConstIterator tmp = *this; ++*this; return tmp;
0430   }
0431 };
0432
0433 } // end namespace llvm
0434
0435 #endif // LLVM_IR_VALUEMAP_H