diff options
Diffstat (limited to 'clang-r353983/include/llvm/IR/ValueMap.h')
| -rw-r--r-- | clang-r353983/include/llvm/IR/ValueMap.h | 437 |
1 files changed, 437 insertions, 0 deletions
diff --git a/clang-r353983/include/llvm/IR/ValueMap.h b/clang-r353983/include/llvm/IR/ValueMap.h new file mode 100644 index 00000000..6a79b1d3 --- /dev/null +++ b/clang-r353983/include/llvm/IR/ValueMap.h @@ -0,0 +1,437 @@ +//===- ValueMap.h - Safe map from Values to data ----------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file defines the ValueMap class. ValueMap maps Value* or any subclass +// to an arbitrary other type. It provides the DenseMap interface but updates +// itself to remain safe when keys are RAUWed or deleted. By default, when a +// key is RAUWed from V1 to V2, the old mapping V1->target is removed, and a new +// mapping V2->target is added. If V2 already existed, its old target is +// overwritten. When a key is deleted, its mapping is removed. +// +// You can override a ValueMap's Config parameter to control exactly what +// happens on RAUW and destruction and to get called back on each event. It's +// legal to call back into the ValueMap from a Config's callbacks. Config +// parameters should inherit from ValueMapConfig<KeyT> to get default +// implementations of all the methods ValueMap uses. See ValueMapConfig for +// documentation of the functions you can override. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_IR_VALUEMAP_H +#define LLVM_IR_VALUEMAP_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseMapInfo.h" +#include "llvm/ADT/None.h" +#include "llvm/ADT/Optional.h" +#include "llvm/IR/TrackingMDRef.h" +#include "llvm/IR/ValueHandle.h" +#include "llvm/Support/Casting.h" +#include "llvm/Support/Mutex.h" +#include "llvm/Support/UniqueLock.h" +#include <algorithm> +#include <cassert> +#include <cstddef> +#include <iterator> +#include <type_traits> +#include <utility> + +namespace llvm { + +template<typename KeyT, typename ValueT, typename Config> +class ValueMapCallbackVH; +template<typename DenseMapT, typename KeyT> +class ValueMapIterator; +template<typename DenseMapT, typename KeyT> +class ValueMapConstIterator; + +/// This class defines the default behavior for configurable aspects of +/// ValueMap<>. User Configs should inherit from this class to be as compatible +/// as possible with future versions of ValueMap. +template<typename KeyT, typename MutexT = sys::Mutex> +struct ValueMapConfig { + using mutex_type = MutexT; + + /// If FollowRAUW is true, the ValueMap will update mappings on RAUW. If it's + /// false, the ValueMap will leave the original mapping in place. + enum { FollowRAUW = true }; + + // All methods will be called with a first argument of type ExtraData. The + // default implementations in this class take a templated first argument so + // that users' subclasses can use any type they want without having to + // override all the defaults. + struct ExtraData {}; + + template<typename ExtraDataT> + static void onRAUW(const ExtraDataT & /*Data*/, KeyT /*Old*/, KeyT /*New*/) {} + template<typename ExtraDataT> + static void onDelete(const ExtraDataT &/*Data*/, KeyT /*Old*/) {} + + /// Returns a mutex that should be acquired around any changes to the map. + /// This is only acquired from the CallbackVH (and held around calls to onRAUW + /// and onDelete) and not inside other ValueMap methods. NULL means that no + /// mutex is necessary. + template<typename ExtraDataT> + static mutex_type *getMutex(const ExtraDataT &/*Data*/) { return nullptr; } +}; + +/// See the file comment. +template<typename KeyT, typename ValueT, typename Config =ValueMapConfig<KeyT>> +class ValueMap { + friend class ValueMapCallbackVH<KeyT, ValueT, Config>; + + using ValueMapCVH = ValueMapCallbackVH<KeyT, ValueT, Config>; + using MapT = DenseMap<ValueMapCVH, ValueT, DenseMapInfo<ValueMapCVH>>; + using MDMapT = DenseMap<const Metadata *, TrackingMDRef>; + using ExtraData = typename Config::ExtraData; + + MapT Map; + Optional<MDMapT> MDMap; + ExtraData Data; + bool MayMapMetadata = true; + +public: + using key_type = KeyT; + using mapped_type = ValueT; + using value_type = std::pair<KeyT, ValueT>; + using size_type = unsigned; + + explicit ValueMap(unsigned NumInitBuckets = 64) + : Map(NumInitBuckets), Data() {} + explicit ValueMap(const ExtraData &Data, unsigned NumInitBuckets = 64) + : Map(NumInitBuckets), Data(Data) {} + // ValueMap can't be copied nor moved, beucase the callbacks store pointer + // to it. + ValueMap(const ValueMap &) = delete; + ValueMap(ValueMap &&) = delete; + ValueMap &operator=(const ValueMap &) = delete; + ValueMap &operator=(ValueMap &&) = delete; + + bool hasMD() const { return bool(MDMap); } + MDMapT &MD() { + if (!MDMap) + MDMap.emplace(); + return *MDMap; + } + Optional<MDMapT> &getMDMap() { return MDMap; } + + bool mayMapMetadata() const { return MayMapMetadata; } + void enableMapMetadata() { MayMapMetadata = true; } + void disableMapMetadata() { MayMapMetadata = false; } + + /// Get the mapped metadata, if it's in the map. + Optional<Metadata *> getMappedMD(const Metadata *MD) const { + if (!MDMap) + return None; + auto Where = MDMap->find(MD); + if (Where == MDMap->end()) + return None; + return Where->second.get(); + } + + using iterator = ValueMapIterator<MapT, KeyT>; + using const_iterator = ValueMapConstIterator<MapT, KeyT>; + + inline iterator begin() { return iterator(Map.begin()); } + inline iterator end() { return iterator(Map.end()); } + inline const_iterator begin() const { return const_iterator(Map.begin()); } + inline const_iterator end() const { return const_iterator(Map.end()); } + + bool empty() const { return Map.empty(); } + size_type size() const { return Map.size(); } + + /// Grow the map so that it has at least Size buckets. Does not shrink + void resize(size_t Size) { Map.resize(Size); } + + void clear() { + Map.clear(); + MDMap.reset(); + } + + /// Return 1 if the specified key is in the map, 0 otherwise. + size_type count(const KeyT &Val) const { + return Map.find_as(Val) == Map.end() ? 0 : 1; + } + + iterator find(const KeyT &Val) { + return iterator(Map.find_as(Val)); + } + const_iterator find(const KeyT &Val) const { + return const_iterator(Map.find_as(Val)); + } + + /// lookup - Return the entry for the specified key, or a default + /// constructed value if no such entry exists. + ValueT lookup(const KeyT &Val) const { + typename MapT::const_iterator I = Map.find_as(Val); + return I != Map.end() ? I->second : ValueT(); + } + + // Inserts key,value pair into the map if the key isn't already in the map. + // If the key is already in the map, it returns false and doesn't update the + // value. + std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { + auto MapResult = Map.insert(std::make_pair(Wrap(KV.first), KV.second)); + return std::make_pair(iterator(MapResult.first), MapResult.second); + } + + std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) { + auto MapResult = + Map.insert(std::make_pair(Wrap(KV.first), std::move(KV.second))); + return std::make_pair(iterator(MapResult.first), MapResult.second); + } + + /// insert - Range insertion of pairs. + template<typename InputIt> + void insert(InputIt I, InputIt E) { + for (; I != E; ++I) + insert(*I); + } + + bool erase(const KeyT &Val) { + typename MapT::iterator I = Map.find_as(Val); + if (I == Map.end()) + return false; + + Map.erase(I); + return true; + } + void erase(iterator I) { + return Map.erase(I.base()); + } + + value_type& FindAndConstruct(const KeyT &Key) { + return Map.FindAndConstruct(Wrap(Key)); + } + + ValueT &operator[](const KeyT &Key) { + return Map[Wrap(Key)]; + } + + /// isPointerIntoBucketsArray - Return true if the specified pointer points + /// somewhere into the ValueMap's array of buckets (i.e. either to a key or + /// value in the ValueMap). + bool isPointerIntoBucketsArray(const void *Ptr) const { + return Map.isPointerIntoBucketsArray(Ptr); + } + + /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets + /// array. In conjunction with the previous method, this can be used to + /// determine whether an insertion caused the ValueMap to reallocate. + const void *getPointerIntoBucketsArray() const { + return Map.getPointerIntoBucketsArray(); + } + +private: + // Takes a key being looked up in the map and wraps it into a + // ValueMapCallbackVH, the actual key type of the map. We use a helper + // function because ValueMapCVH is constructed with a second parameter. + ValueMapCVH Wrap(KeyT key) const { + // The only way the resulting CallbackVH could try to modify *this (making + // the const_cast incorrect) is if it gets inserted into the map. But then + // this function must have been called from a non-const method, making the + // const_cast ok. + return ValueMapCVH(key, const_cast<ValueMap*>(this)); + } +}; + +// This CallbackVH updates its ValueMap when the contained Value changes, +// according to the user's preferences expressed through the Config object. +template <typename KeyT, typename ValueT, typename Config> +class ValueMapCallbackVH final : public CallbackVH { + friend class ValueMap<KeyT, ValueT, Config>; + friend struct DenseMapInfo<ValueMapCallbackVH>; + + using ValueMapT = ValueMap<KeyT, ValueT, Config>; + using KeySansPointerT = typename std::remove_pointer<KeyT>::type; + + ValueMapT *Map; + + ValueMapCallbackVH(KeyT Key, ValueMapT *Map) + : CallbackVH(const_cast<Value*>(static_cast<const Value*>(Key))), + Map(Map) {} + + // Private constructor used to create empty/tombstone DenseMap keys. + ValueMapCallbackVH(Value *V) : CallbackVH(V), Map(nullptr) {} + +public: + KeyT Unwrap() const { return cast_or_null<KeySansPointerT>(getValPtr()); } + + void deleted() override { + // Make a copy that won't get changed even when *this is destroyed. + ValueMapCallbackVH Copy(*this); + typename Config::mutex_type *M = Config::getMutex(Copy.Map->Data); + unique_lock<typename Config::mutex_type> Guard; + if (M) + Guard = unique_lock<typename Config::mutex_type>(*M); + Config::onDelete(Copy.Map->Data, Copy.Unwrap()); // May destroy *this. + Copy.Map->Map.erase(Copy); // Definitely destroys *this. + } + + void allUsesReplacedWith(Value *new_key) override { + assert(isa<KeySansPointerT>(new_key) && + "Invalid RAUW on key of ValueMap<>"); + // Make a copy that won't get changed even when *this is destroyed. + ValueMapCallbackVH Copy(*this); + typename Config::mutex_type *M = Config::getMutex(Copy.Map->Data); + unique_lock<typename Config::mutex_type> Guard; + if (M) + Guard = unique_lock<typename Config::mutex_type>(*M); + + KeyT typed_new_key = cast<KeySansPointerT>(new_key); + // Can destroy *this: + Config::onRAUW(Copy.Map->Data, Copy.Unwrap(), typed_new_key); + if (Config::FollowRAUW) { + typename ValueMapT::MapT::iterator I = Copy.Map->Map.find(Copy); + // I could == Copy.Map->Map.end() if the onRAUW callback already + // removed the old mapping. + if (I != Copy.Map->Map.end()) { + ValueT Target(std::move(I->second)); + Copy.Map->Map.erase(I); // Definitely destroys *this. + Copy.Map->insert(std::make_pair(typed_new_key, std::move(Target))); + } + } + } +}; + +template<typename KeyT, typename ValueT, typename Config> +struct DenseMapInfo<ValueMapCallbackVH<KeyT, ValueT, Config>> { + using VH = ValueMapCallbackVH<KeyT, ValueT, Config>; + + static inline VH getEmptyKey() { + return VH(DenseMapInfo<Value *>::getEmptyKey()); + } + + static inline VH getTombstoneKey() { + return VH(DenseMapInfo<Value *>::getTombstoneKey()); + } + + static unsigned getHashValue(const VH &Val) { + return DenseMapInfo<KeyT>::getHashValue(Val.Unwrap()); + } + + static unsigned getHashValue(const KeyT &Val) { + return DenseMapInfo<KeyT>::getHashValue(Val); + } + + static bool isEqual(const VH &LHS, const VH &RHS) { + return LHS == RHS; + } + + static bool isEqual(const KeyT &LHS, const VH &RHS) { + return LHS == RHS.getValPtr(); + } +}; + +template<typename DenseMapT, typename KeyT> +class ValueMapIterator : + public std::iterator<std::forward_iterator_tag, + std::pair<KeyT, typename DenseMapT::mapped_type>, + ptrdiff_t> { + using BaseT = typename DenseMapT::iterator; + using ValueT = typename DenseMapT::mapped_type; + + BaseT I; + +public: + ValueMapIterator() : I() {} + ValueMapIterator(BaseT I) : I(I) {} + + BaseT base() const { return I; } + + struct ValueTypeProxy { + const KeyT first; + ValueT& second; + + ValueTypeProxy *operator->() { return this; } + + operator std::pair<KeyT, ValueT>() const { + return std::make_pair(first, second); + } + }; + + ValueTypeProxy operator*() const { + ValueTypeProxy Result = {I->first.Unwrap(), I->second}; + return Result; + } + + ValueTypeProxy operator->() const { + return operator*(); + } + + bool operator==(const ValueMapIterator &RHS) const { + return I == RHS.I; + } + bool operator!=(const ValueMapIterator &RHS) const { + return I != RHS.I; + } + + inline ValueMapIterator& operator++() { // Preincrement + ++I; + return *this; + } + ValueMapIterator operator++(int) { // Postincrement + ValueMapIterator tmp = *this; ++*this; return tmp; + } +}; + +template<typename DenseMapT, typename KeyT> +class ValueMapConstIterator : + public std::iterator<std::forward_iterator_tag, + std::pair<KeyT, typename DenseMapT::mapped_type>, + ptrdiff_t> { + using BaseT = typename DenseMapT::const_iterator; + using ValueT = typename DenseMapT::mapped_type; + + BaseT I; + +public: + ValueMapConstIterator() : I() {} + ValueMapConstIterator(BaseT I) : I(I) {} + ValueMapConstIterator(ValueMapIterator<DenseMapT, KeyT> Other) + : I(Other.base()) {} + + BaseT base() const { return I; } + + struct ValueTypeProxy { + const KeyT first; + const ValueT& second; + ValueTypeProxy *operator->() { return this; } + operator std::pair<KeyT, ValueT>() const { + return std::make_pair(first, second); + } + }; + + ValueTypeProxy operator*() const { + ValueTypeProxy Result = {I->first.Unwrap(), I->second}; + return Result; + } + + ValueTypeProxy operator->() const { + return operator*(); + } + + bool operator==(const ValueMapConstIterator &RHS) const { + return I == RHS.I; + } + bool operator!=(const ValueMapConstIterator &RHS) const { + return I != RHS.I; + } + + inline ValueMapConstIterator& operator++() { // Preincrement + ++I; + return *this; + } + ValueMapConstIterator operator++(int) { // Postincrement + ValueMapConstIterator tmp = *this; ++*this; return tmp; + } +}; + +} // end namespace llvm + +#endif // LLVM_IR_VALUEMAP_H |