X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=include%2Fllvm%2FIR%2FMetadata.h;h=6f02ee1e70403f54d5584a8c09bbbd1fe205cbac;hp=9b044a37298dbdb4576c029e4512268843893c84;hb=8ec0aee3b4a0b038732f30226999145d666186f2;hpb=aa3d8b2d6cffba317e5b2fac86c741255fed0187 diff --git a/include/llvm/IR/Metadata.h b/include/llvm/IR/Metadata.h index 9b044a37298..6f02ee1e704 100644 --- a/include/llvm/IR/Metadata.h +++ b/include/llvm/IR/Metadata.h @@ -17,10 +17,14 @@ #define LLVM_IR_METADATA_H #include "llvm/ADT/ArrayRef.h" -#include "llvm/ADT/FoldingSet.h" +#include "llvm/ADT/DenseMap.h" #include "llvm/ADT/ilist_node.h" #include "llvm/ADT/iterator_range.h" +#include "llvm/IR/Constant.h" +#include "llvm/IR/MetadataTracking.h" #include "llvm/IR/Value.h" +#include "llvm/Support/ErrorHandling.h" +#include namespace llvm { class LLVMContext; @@ -30,169 +34,943 @@ template enum LLVMConstants : uint32_t { - DEBUG_METADATA_VERSION = 1 // Current debug info version number. + DEBUG_METADATA_VERSION = 2 // Current debug info version number. }; +/// \brief Root of the metadata hierarchy. +/// +/// This is a root class for typeless data in the IR. +class Metadata { + friend class ReplaceableMetadataImpl; + + /// \brief RTTI. + const unsigned char SubclassID; + +protected: + /// \brief Active type of storage. + enum StorageType { Uniqued, Distinct, Temporary }; + + /// \brief Storage flag for non-uniqued, otherwise unowned, metadata. + StorageType Storage : 2; + // TODO: expose remaining bits to subclasses. + + unsigned short SubclassData16; + unsigned SubclassData32; + +public: + enum MetadataKind { + MDTupleKind, + MDLocationKind, + ConstantAsMetadataKind, + LocalAsMetadataKind, + MDStringKind + }; + +protected: + Metadata(unsigned ID, StorageType Storage) + : SubclassID(ID), Storage(Storage), SubclassData16(0), SubclassData32(0) { + } + ~Metadata() {} + + /// \brief Default handling of a changed operand, which asserts. + /// + /// If subclasses pass themselves in as owners to a tracking node reference, + /// they must provide an implementation of this method. + void handleChangedOperand(void *, Metadata *) { + llvm_unreachable("Unimplemented in Metadata subclass"); + } + +public: + unsigned getMetadataID() const { return SubclassID; } + + /// \brief User-friendly dump. + void dump() const; + void print(raw_ostream &OS) const; + void printAsOperand(raw_ostream &OS, bool PrintType = true, + const Module *M = nullptr) const; +}; + +#define HANDLE_METADATA(CLASS) class CLASS; +#include "llvm/IR/Metadata.def" + +inline raw_ostream &operator<<(raw_ostream &OS, const Metadata &MD) { + MD.print(OS); + return OS; +} + +/// \brief Metadata wrapper in the Value hierarchy. +/// +/// A member of the \a Value hierarchy to represent a reference to metadata. +/// This allows, e.g., instrinsics to have metadata as operands. +/// +/// Notably, this is the only thing in either hierarchy that is allowed to +/// reference \a LocalAsMetadata. +class MetadataAsValue : public Value { + friend class ReplaceableMetadataImpl; + friend class LLVMContextImpl; + + Metadata *MD; + + MetadataAsValue(Type *Ty, Metadata *MD); + ~MetadataAsValue(); + + /// \brief Drop use of metadata (during teardown). + void dropUse() { MD = nullptr; } + +public: + static MetadataAsValue *get(LLVMContext &Context, Metadata *MD); + static MetadataAsValue *getIfExists(LLVMContext &Context, Metadata *MD); + Metadata *getMetadata() const { return MD; } + + static bool classof(const Value *V) { + return V->getValueID() == MetadataAsValueVal; + } + +private: + void handleChangedMetadata(Metadata *MD); + void track(); + void untrack(); +}; + +/// \brief Shared implementation of use-lists for replaceable metadata. +/// +/// Most metadata cannot be RAUW'ed. This is a shared implementation of +/// use-lists and associated API for the two that support it (\a ValueAsMetadata +/// and \a TempMDNode). +class ReplaceableMetadataImpl { + friend class MetadataTracking; + +public: + typedef MetadataTracking::OwnerTy OwnerTy; + +private: + LLVMContext &Context; + uint64_t NextIndex; + SmallDenseMap, 4> UseMap; + +public: + ReplaceableMetadataImpl(LLVMContext &Context) + : Context(Context), NextIndex(0) {} + ~ReplaceableMetadataImpl() { + assert(UseMap.empty() && "Cannot destroy in-use replaceable metadata"); + } + + LLVMContext &getContext() const { return Context; } + + /// \brief Replace all uses of this with MD. + /// + /// Replace all uses of this with \c MD, which is allowed to be null. + void replaceAllUsesWith(Metadata *MD); + + /// \brief Resolve all uses of this. + /// + /// Resolve all uses of this, turning off RAUW permanently. If \c + /// ResolveUsers, call \a UniquableMDNode::resolve() on any users whose last + /// operand is resolved. + void resolveAllUses(bool ResolveUsers = true); + +private: + void addRef(void *Ref, OwnerTy Owner); + void dropRef(void *Ref); + void moveRef(void *Ref, void *New, const Metadata &MD); + + static ReplaceableMetadataImpl *get(Metadata &MD); +}; + +/// \brief Value wrapper in the Metadata hierarchy. +/// +/// This is a custom value handle that allows other metadata to refer to +/// classes in the Value hierarchy. +/// +/// Because of full uniquing support, each value is only wrapped by a single \a +/// ValueAsMetadata object, so the lookup maps are far more efficient than +/// those using ValueHandleBase. +class ValueAsMetadata : public Metadata, ReplaceableMetadataImpl { + friend class ReplaceableMetadataImpl; + friend class LLVMContextImpl; + + Value *V; + + /// \brief Drop users without RAUW (during teardown). + void dropUsers() { + ReplaceableMetadataImpl::resolveAllUses(/* ResolveUsers */ false); + } + +protected: + ValueAsMetadata(unsigned ID, Value *V) + : Metadata(ID, Uniqued), ReplaceableMetadataImpl(V->getContext()), V(V) { + assert(V && "Expected valid value"); + } + ~ValueAsMetadata() {} + +public: + static ValueAsMetadata *get(Value *V); + static ConstantAsMetadata *getConstant(Value *C) { + return cast(get(C)); + } + static LocalAsMetadata *getLocal(Value *Local) { + return cast(get(Local)); + } + + static ValueAsMetadata *getIfExists(Value *V); + static ConstantAsMetadata *getConstantIfExists(Value *C) { + return cast_or_null(getIfExists(C)); + } + static LocalAsMetadata *getLocalIfExists(Value *Local) { + return cast_or_null(getIfExists(Local)); + } + + Value *getValue() const { return V; } + Type *getType() const { return V->getType(); } + LLVMContext &getContext() const { return V->getContext(); } + + static void handleDeletion(Value *V); + static void handleRAUW(Value *From, Value *To); + +protected: + /// \brief Handle collisions after \a Value::replaceAllUsesWith(). + /// + /// RAUW isn't supported directly for \a ValueAsMetadata, but if the wrapped + /// \a Value gets RAUW'ed and the target already exists, this is used to + /// merge the two metadata nodes. + void replaceAllUsesWith(Metadata *MD) { + ReplaceableMetadataImpl::replaceAllUsesWith(MD); + } + +public: + static bool classof(const Metadata *MD) { + return MD->getMetadataID() == LocalAsMetadataKind || + MD->getMetadataID() == ConstantAsMetadataKind; + } +}; + +class ConstantAsMetadata : public ValueAsMetadata { + friend class ValueAsMetadata; + + ConstantAsMetadata(Constant *C) + : ValueAsMetadata(ConstantAsMetadataKind, C) {} + +public: + static ConstantAsMetadata *get(Constant *C) { + return ValueAsMetadata::getConstant(C); + } + static ConstantAsMetadata *getIfExists(Constant *C) { + return ValueAsMetadata::getConstantIfExists(C); + } + + Constant *getValue() const { + return cast(ValueAsMetadata::getValue()); + } + + static bool classof(const Metadata *MD) { + return MD->getMetadataID() == ConstantAsMetadataKind; + } +}; + +class LocalAsMetadata : public ValueAsMetadata { + friend class ValueAsMetadata; + + LocalAsMetadata(Value *Local) + : ValueAsMetadata(LocalAsMetadataKind, Local) { + assert(!isa(Local) && "Expected local value"); + } + +public: + static LocalAsMetadata *get(Value *Local) { + return ValueAsMetadata::getLocal(Local); + } + static LocalAsMetadata *getIfExists(Value *Local) { + return ValueAsMetadata::getLocalIfExists(Local); + } + + static bool classof(const Metadata *MD) { + return MD->getMetadataID() == LocalAsMetadataKind; + } +}; + +/// \brief Transitional API for extracting constants from Metadata. +/// +/// This namespace contains transitional functions for metadata that points to +/// \a Constants. +/// +/// In prehistory -- when metadata was a subclass of \a Value -- \a MDNode +/// operands could refer to any \a Value. There's was a lot of code like this: +/// +/// \code +/// MDNode *N = ...; +/// auto *CI = dyn_cast(N->getOperand(2)); +/// \endcode +/// +/// Now that \a Value and \a Metadata are in separate hierarchies, maintaining +/// the semantics for \a isa(), \a cast(), \a dyn_cast() (etc.) requires three +/// steps: cast in the \a Metadata hierarchy, extraction of the \a Value, and +/// cast in the \a Value hierarchy. Besides creating boiler-plate, this +/// requires subtle control flow changes. +/// +/// The end-goal is to create a new type of metadata, called (e.g.) \a MDInt, +/// so that metadata can refer to numbers without traversing a bridge to the \a +/// Value hierarchy. In this final state, the code above would look like this: +/// +/// \code +/// MDNode *N = ...; +/// auto *MI = dyn_cast(N->getOperand(2)); +/// \endcode +/// +/// The API in this namespace supports the transition. \a MDInt doesn't exist +/// yet, and even once it does, changing each metadata schema to use it is its +/// own mini-project. In the meantime this API prevents us from introducing +/// complex and bug-prone control flow that will disappear in the end. In +/// particular, the above code looks like this: +/// +/// \code +/// MDNode *N = ...; +/// auto *CI = mdconst::dyn_extract(N->getOperand(2)); +/// \endcode +/// +/// The full set of provided functions includes: +/// +/// mdconst::hasa <=> isa +/// mdconst::extract <=> cast +/// mdconst::extract_or_null <=> cast_or_null +/// mdconst::dyn_extract <=> dyn_cast +/// mdconst::dyn_extract_or_null <=> dyn_cast_or_null +/// +/// The target of the cast must be a subclass of \a Constant. +namespace mdconst { + +namespace detail { +template T &make(); +template struct HasDereference { + typedef char Yes[1]; + typedef char No[2]; + template struct SFINAE {}; + + template + static Yes &hasDereference(SFINAE(*make()))> * = 0); + template static No &hasDereference(...); + + static const bool value = + sizeof(hasDereference(nullptr)) == sizeof(Yes); +}; +template struct IsValidPointer { + static const bool value = std::is_base_of::value && + HasDereference::value; +}; +template struct IsValidReference { + static const bool value = std::is_base_of::value && + std::is_convertible::value; +}; +} // end namespace detail + +/// \brief Check whether Metadata has a Value. +/// +/// As an analogue to \a isa(), check whether \c MD has an \a Value inside of +/// type \c X. +template +inline typename std::enable_if::value, bool>::type +hasa(Y &&MD) { + assert(MD && "Null pointer sent into hasa"); + if (auto *V = dyn_cast(MD)) + return isa(V->getValue()); + return false; +} +template +inline + typename std::enable_if::value, bool>::type + hasa(Y &MD) { + return hasa(&MD); +} + +/// \brief Extract a Value from Metadata. +/// +/// As an analogue to \a cast(), extract the \a Value subclass \c X from \c MD. +template +inline typename std::enable_if::value, X *>::type +extract(Y &&MD) { + return cast(cast(MD)->getValue()); +} +template +inline + typename std::enable_if::value, X *>::type + extract(Y &MD) { + return extract(&MD); +} + +/// \brief Extract a Value from Metadata, allowing null. +/// +/// As an analogue to \a cast_or_null(), extract the \a Value subclass \c X +/// from \c MD, allowing \c MD to be null. +template +inline typename std::enable_if::value, X *>::type +extract_or_null(Y &&MD) { + if (auto *V = cast_or_null(MD)) + return cast(V->getValue()); + return nullptr; +} + +/// \brief Extract a Value from Metadata, if any. +/// +/// As an analogue to \a dyn_cast_or_null(), extract the \a Value subclass \c X +/// from \c MD, return null if \c MD doesn't contain a \a Value or if the \a +/// Value it does contain is of the wrong subclass. +template +inline typename std::enable_if::value, X *>::type +dyn_extract(Y &&MD) { + if (auto *V = dyn_cast(MD)) + return dyn_cast(V->getValue()); + return nullptr; +} + +/// \brief Extract a Value from Metadata, if any, allowing null. +/// +/// As an analogue to \a dyn_cast_or_null(), extract the \a Value subclass \c X +/// from \c MD, return null if \c MD doesn't contain a \a Value or if the \a +/// Value it does contain is of the wrong subclass, allowing \c MD to be null. +template +inline typename std::enable_if::value, X *>::type +dyn_extract_or_null(Y &&MD) { + if (auto *V = dyn_cast_or_null(MD)) + return dyn_cast(V->getValue()); + return nullptr; +} + +} // end namespace mdconst + //===----------------------------------------------------------------------===// -/// MDString - a single uniqued string. +/// \brief A single uniqued string. +/// /// These are used to efficiently contain a byte sequence for metadata. /// MDString is always unnamed. -class MDString : public Value { - virtual void anchor(); +class MDString : public Metadata { + friend class StringMapEntry; + MDString(const MDString &) LLVM_DELETED_FUNCTION; + MDString &operator=(MDString &&) LLVM_DELETED_FUNCTION; + MDString &operator=(const MDString &) LLVM_DELETED_FUNCTION; + + StringMapEntry *Entry; + MDString() : Metadata(MDStringKind, Uniqued), Entry(nullptr) {} + MDString(MDString &&) : Metadata(MDStringKind, Uniqued) {} - explicit MDString(LLVMContext &C); public: static MDString *get(LLVMContext &Context, StringRef Str); static MDString *get(LLVMContext &Context, const char *Str) { return get(Context, Str ? StringRef(Str) : StringRef()); } - StringRef getString() const { return getName(); } + StringRef getString() const; - unsigned getLength() const { return (unsigned)getName().size(); } + unsigned getLength() const { return (unsigned)getString().size(); } typedef StringRef::iterator iterator; - /// begin() - Pointer to the first byte of the string. - iterator begin() const { return getName().begin(); } + /// \brief Pointer to the first byte of the string. + iterator begin() const { return getString().begin(); } - /// end() - Pointer to one byte past the end of the string. - iterator end() const { return getName().end(); } + /// \brief Pointer to one byte past the end of the string. + iterator end() const { return getString().end(); } - /// Methods for support type inquiry through isa, cast, and dyn_cast: - static bool classof(const Value *V) { - return V->getValueID() == MDStringVal; + const unsigned char *bytes_begin() const { return getString().bytes_begin(); } + const unsigned char *bytes_end() const { return getString().bytes_end(); } + + /// \brief Methods for support type inquiry through isa, cast, and dyn_cast. + static bool classof(const Metadata *MD) { + return MD->getMetadataID() == MDStringKind; } }; +/// \brief A collection of metadata nodes that might be associated with a +/// memory access used by the alias-analysis infrastructure. +struct AAMDNodes { + explicit AAMDNodes(MDNode *T = nullptr, MDNode *S = nullptr, + MDNode *N = nullptr) + : TBAA(T), Scope(S), NoAlias(N) {} -class MDNodeOperand; + bool operator==(const AAMDNodes &A) const { + return TBAA == A.TBAA && Scope == A.Scope && NoAlias == A.NoAlias; + } + + bool operator!=(const AAMDNodes &A) const { return !(*this == A); } + + LLVM_EXPLICIT operator bool() const { return TBAA || Scope || NoAlias; } + + /// \brief The tag for type-based alias analysis. + MDNode *TBAA; + + /// \brief The tag for alias scope specification (used with noalias). + MDNode *Scope; + + /// \brief The tag specifying the noalias scope. + MDNode *NoAlias; +}; + +// Specialize DenseMapInfo for AAMDNodes. +template<> +struct DenseMapInfo { + static inline AAMDNodes getEmptyKey() { + return AAMDNodes(DenseMapInfo::getEmptyKey(), 0, 0); + } + static inline AAMDNodes getTombstoneKey() { + return AAMDNodes(DenseMapInfo::getTombstoneKey(), 0, 0); + } + static unsigned getHashValue(const AAMDNodes &Val) { + return DenseMapInfo::getHashValue(Val.TBAA) ^ + DenseMapInfo::getHashValue(Val.Scope) ^ + DenseMapInfo::getHashValue(Val.NoAlias); + } + static bool isEqual(const AAMDNodes &LHS, const AAMDNodes &RHS) { + return LHS == RHS; + } +}; + +/// \brief Tracking metadata reference owned by Metadata. +/// +/// Similar to \a TrackingMDRef, but it's expected to be owned by an instance +/// of \a Metadata, which has the option of registering itself for callbacks to +/// re-unique itself. +/// +/// In particular, this is used by \a MDNode. +class MDOperand { + MDOperand(MDOperand &&) LLVM_DELETED_FUNCTION; + MDOperand(const MDOperand &) LLVM_DELETED_FUNCTION; + MDOperand &operator=(MDOperand &&) LLVM_DELETED_FUNCTION; + MDOperand &operator=(const MDOperand &) LLVM_DELETED_FUNCTION; + + Metadata *MD; + +public: + MDOperand() : MD(nullptr) {} + ~MDOperand() { untrack(); } + + Metadata *get() const { return MD; } + operator Metadata *() const { return get(); } + Metadata *operator->() const { return get(); } + Metadata &operator*() const { return *get(); } + + void reset() { + untrack(); + MD = nullptr; + } + void reset(Metadata *MD, Metadata *Owner) { + untrack(); + this->MD = MD; + track(Owner); + } + +private: + void track(Metadata *Owner) { + if (MD) { + if (Owner) + MetadataTracking::track(this, *MD, *Owner); + else + MetadataTracking::track(MD); + } + } + void untrack() { + assert(static_cast(this) == &MD && "Expected same address"); + if (MD) + MetadataTracking::untrack(MD); + } +}; + +template <> struct simplify_type { + typedef Metadata *SimpleType; + static SimpleType getSimplifiedValue(MDOperand &MD) { return MD.get(); } +}; + +template <> struct simplify_type { + typedef Metadata *SimpleType; + static SimpleType getSimplifiedValue(const MDOperand &MD) { return MD.get(); } +}; + +/// \brief Pointer to the context, with optional RAUW support. +/// +/// Either a raw (non-null) pointer to the \a LLVMContext, or an owned pointer +/// to \a ReplaceableMetadataImpl (which has a reference to \a LLVMContext). +class ContextAndReplaceableUses { + PointerUnion Ptr; + + ContextAndReplaceableUses() LLVM_DELETED_FUNCTION; + ContextAndReplaceableUses(ContextAndReplaceableUses &&) + LLVM_DELETED_FUNCTION; + ContextAndReplaceableUses(const ContextAndReplaceableUses &) + LLVM_DELETED_FUNCTION; + ContextAndReplaceableUses & + operator=(ContextAndReplaceableUses &&) LLVM_DELETED_FUNCTION; + ContextAndReplaceableUses & + operator=(const ContextAndReplaceableUses &) LLVM_DELETED_FUNCTION; + +public: + ContextAndReplaceableUses(LLVMContext &Context) : Ptr(&Context) {} + ContextAndReplaceableUses( + std::unique_ptr ReplaceableUses) + : Ptr(ReplaceableUses.release()) { + assert(getReplaceableUses() && "Expected non-null replaceable uses"); + } + ~ContextAndReplaceableUses() { delete getReplaceableUses(); } + + operator LLVMContext &() { return getContext(); } + + /// \brief Whether this contains RAUW support. + bool hasReplaceableUses() const { + return Ptr.is(); + } + LLVMContext &getContext() const { + if (hasReplaceableUses()) + return getReplaceableUses()->getContext(); + return *Ptr.get(); + } + ReplaceableMetadataImpl *getReplaceableUses() const { + if (hasReplaceableUses()) + return Ptr.get(); + return nullptr; + } + + /// \brief Assign RAUW support to this. + /// + /// Make this replaceable, taking ownership of \c ReplaceableUses (which must + /// not be null). + void + makeReplaceable(std::unique_ptr ReplaceableUses) { + assert(ReplaceableUses && "Expected non-null replaceable uses"); + assert(&ReplaceableUses->getContext() == &getContext() && + "Expected same context"); + delete getReplaceableUses(); + Ptr = ReplaceableUses.release(); + } + + /// \brief Drop RAUW support. + /// + /// Cede ownership of RAUW support, returning it. + std::unique_ptr takeReplaceableUses() { + assert(hasReplaceableUses() && "Expected to own replaceable uses"); + std::unique_ptr ReplaceableUses( + getReplaceableUses()); + Ptr = &ReplaceableUses->getContext(); + return ReplaceableUses; + } +}; //===----------------------------------------------------------------------===// -/// MDNode - a tuple of other values. -class MDNode : public Value, public FoldingSetNode { +/// \brief Tuple of metadata. +class MDNode : public Metadata { + friend class ReplaceableMetadataImpl; + MDNode(const MDNode &) LLVM_DELETED_FUNCTION; void operator=(const MDNode &) LLVM_DELETED_FUNCTION; - friend class MDNodeOperand; - friend class LLVMContextImpl; - friend struct FoldingSetTrait; + void *operator new(size_t) LLVM_DELETED_FUNCTION; - /// Hash - If the MDNode is uniqued cache the hash to speed up lookup. - unsigned Hash; +protected: + ContextAndReplaceableUses Context; - /// NumOperands - This many 'MDNodeOperand' items are co-allocated onto the - /// end of this MDNode. +private: unsigned NumOperands; - // Subclass data enums. - enum { - /// FunctionLocalBit - This bit is set if this MDNode is function local. - /// This is true when it (potentially transitively) contains a reference to - /// something in a function, like an argument, basicblock, or instruction. - FunctionLocalBit = 1 << 0, +protected: + unsigned MDNodeSubclassData; - /// NotUniquedBit - This is set on MDNodes that are not uniqued because they - /// have a null operand. - NotUniquedBit = 1 << 1, + void *operator new(size_t Size, unsigned NumOps); + void operator delete(void *Mem); - /// DestroyFlag - This bit is set by destroy() so the destructor can assert - /// that the node isn't being destroyed with a plain 'delete'. - DestroyFlag = 1 << 2 - }; + /// \brief Required by std, but never called. + void operator delete(void *, unsigned) { + llvm_unreachable("Constructor throws?"); + } - // FunctionLocal enums. - enum FunctionLocalness { - FL_Unknown = -1, - FL_No = 0, - FL_Yes = 1 - }; + /// \brief Required by std, but never called. + void operator delete(void *, unsigned, bool) { + llvm_unreachable("Constructor throws?"); + } - /// replaceOperand - Replace each instance of F from the operand list of this - /// node with T. - void replaceOperand(MDNodeOperand *Op, Value *NewVal); - ~MDNode(); + MDNode(LLVMContext &Context, unsigned ID, StorageType Storage, + ArrayRef MDs); + ~MDNode() {} - MDNode(LLVMContext &C, ArrayRef Vals, bool isFunctionLocal); + void dropAllReferences(); + + MDOperand *mutable_begin() { return mutable_end() - NumOperands; } + MDOperand *mutable_end() { return reinterpret_cast(this); } - static MDNode *getMDNode(LLVMContext &C, ArrayRef Vals, - FunctionLocalness FL, bool Insert = true); public: - // Constructors and destructors. - static MDNode *get(LLVMContext &Context, ArrayRef Vals); - // getWhenValsUnresolved - Construct MDNode determining function-localness - // from isFunctionLocal argument, not by analyzing Vals. - static MDNode *getWhenValsUnresolved(LLVMContext &Context, - ArrayRef Vals, - bool isFunctionLocal); - - static MDNode *getIfExists(LLVMContext &Context, ArrayRef Vals); - - /// getTemporary - Return a temporary MDNode, for use in constructing - /// cyclic MDNode structures. A temporary MDNode is not uniqued, - /// may be RAUW'd, and must be manually deleted with deleteTemporary. - static MDNode *getTemporary(LLVMContext &Context, ArrayRef Vals); - - /// deleteTemporary - Deallocate a node created by getTemporary. The - /// node must not have any users. + static inline MDTuple *get(LLVMContext &Context, ArrayRef MDs); + static inline MDTuple *getIfExists(LLVMContext &Context, + ArrayRef MDs); + static inline MDTuple *getDistinct(LLVMContext &Context, + ArrayRef MDs); + static inline MDTuple *getTemporary(LLVMContext &Context, + ArrayRef MDs); + + /// \brief Deallocate a node created by getTemporary. + /// + /// The node must not have any users. static void deleteTemporary(MDNode *N); - /// replaceOperandWith - Replace a specific operand. - void replaceOperandWith(unsigned i, Value *NewVal); + LLVMContext &getContext() const { return Context.getContext(); } - /// getOperand - Return specified operand. - Value *getOperand(unsigned i) const LLVM_READONLY; + /// \brief Replace a specific operand. + void replaceOperandWith(unsigned I, Metadata *New); - /// getNumOperands - Return number of MDNode operands. - unsigned getNumOperands() const { return NumOperands; } + /// \brief Check if node is fully resolved. + /// + /// If \a isTemporary(), this always returns \c false; if \a isDistinct(), + /// this always returns \c true. + /// + /// If \a isUniqued(), returns \c true if this has already dropped RAUW + /// support (because all operands are resolved). + /// + /// As forward declarations are resolved, their containers should get + /// resolved automatically. However, if this (or one of its operands) is + /// involved in a cycle, \a resolveCycles() needs to be called explicitly. + bool isResolved() const { return !Context.hasReplaceableUses(); } - /// isFunctionLocal - Return whether MDNode is local to a function. - bool isFunctionLocal() const { - return (getSubclassDataFromValue() & FunctionLocalBit) != 0; + bool isUniqued() const { return Storage == Uniqued; } + bool isDistinct() const { return Storage == Distinct; } + bool isTemporary() const { return Storage == Temporary; } + + /// \brief RAUW a temporary. + /// + /// \pre \a isTemporary() must be \c true. + void replaceAllUsesWith(Metadata *MD) { + assert(isTemporary() && "Expected temporary node"); + assert(!isResolved() && "Expected RAUW support"); + Context.getReplaceableUses()->replaceAllUsesWith(MD); } - // getFunction - If this metadata is function-local and recursively has a - // function-local operand, return the first such operand's parent function. - // Otherwise, return null. getFunction() should not be used for performance- - // critical code because it recursively visits all the MDNode's operands. - const Function *getFunction() const; +protected: + /// \brief Set an operand. + /// + /// Sets the operand directly, without worrying about uniquing. + void setOperand(unsigned I, Metadata *New); - /// Profile - calculate a unique identifier for this MDNode to collapse - /// duplicates - void Profile(FoldingSetNodeID &ID) const; +public: + typedef const MDOperand *op_iterator; + typedef iterator_range op_range; - /// Methods for support type inquiry through isa, cast, and dyn_cast: - static bool classof(const Value *V) { - return V->getValueID() == MDNodeVal; + op_iterator op_begin() const { + return const_cast(this)->mutable_begin(); + } + op_iterator op_end() const { + return const_cast(this)->mutable_end(); } + op_range operands() const { return op_range(op_begin(), op_end()); } - /// Check whether MDNode is a vtable access. + const MDOperand &getOperand(unsigned I) const { + assert(I < NumOperands && "Out of range"); + return op_begin()[I]; + } + + /// \brief Return number of MDNode operands. + unsigned getNumOperands() const { return NumOperands; } + + /// \brief Methods for support type inquiry through isa, cast, and dyn_cast: + static bool classof(const Metadata *MD) { + return MD->getMetadataID() == MDTupleKind || + MD->getMetadataID() == MDLocationKind; + } + + /// \brief Check whether MDNode is a vtable access. bool isTBAAVtableAccess() const; - /// Methods for metadata merging. + /// \brief Methods for metadata merging. + static MDNode *concatenate(MDNode *A, MDNode *B); + static MDNode *intersect(MDNode *A, MDNode *B); static MDNode *getMostGenericTBAA(MDNode *A, MDNode *B); + static AAMDNodes getMostGenericAA(const AAMDNodes &A, const AAMDNodes &B); static MDNode *getMostGenericFPMath(MDNode *A, MDNode *B); static MDNode *getMostGenericRange(MDNode *A, MDNode *B); +}; + +/// \brief Uniquable metadata node. +/// +/// A uniquable metadata node. This contains the basic functionality +/// for implementing sub-types of \a MDNode that can be uniqued like +/// constants. +/// +/// There is limited support for RAUW at construction time. At construction +/// time, if any operand is a temporary node (or an unresolved uniqued node, +/// which indicates a transitive temporary operand), the node itself will be +/// unresolved. As soon as all operands become resolved, it will drop RAUW +/// support permanently. +/// +/// If an unresolved node is part of a cycle, \a resolveCycles() needs +/// to be called on some member of the cycle once all temporary nodes have been +/// replaced. +class UniquableMDNode : public MDNode { + friend class ReplaceableMetadataImpl; + friend class MDNode; + friend class LLVMContextImpl; + +protected: + /// \brief Create a new node. + /// + /// If \c AllowRAUW, then if any operands are unresolved support RAUW. RAUW + /// will be dropped once all operands have been resolved (or if \a + /// resolveCycles() is called). + UniquableMDNode(LLVMContext &C, unsigned ID, StorageType Storage, + ArrayRef Vals); + ~UniquableMDNode() {} + + void storeDistinctInContext(); + template + static T *storeImpl(T *N, StorageType Storage, StoreT &Store); + +public: + static bool classof(const Metadata *MD) { + return MD->getMetadataID() == MDTupleKind || + MD->getMetadataID() == MDLocationKind; + } + + /// \brief Resolve cycles. + /// + /// Once all forward declarations have been resolved, force cycles to be + /// resolved. + /// + /// \pre No operands (or operands' operands, etc.) have \a isTemporary(). + void resolveCycles(); + +private: + void handleChangedOperand(void *Ref, Metadata *New); + + void resolve(); + void resolveAfterOperandChange(Metadata *Old, Metadata *New); + void decrementUnresolvedOperandCount(); + + void deleteAsSubclass(); + UniquableMDNode *uniquify(); + void eraseFromStore(); +}; + +/// \brief Tuple of metadata. +/// +/// This is the simple \a MDNode arbitrary tuple. Nodes are uniqued by +/// default based on their operands. +class MDTuple : public UniquableMDNode { + friend class LLVMContextImpl; + friend class UniquableMDNode; + + MDTuple(LLVMContext &C, StorageType Storage, unsigned Hash, + ArrayRef Vals) + : UniquableMDNode(C, MDTupleKind, Storage, Vals) { + setHash(Hash); + } + ~MDTuple() { dropAllReferences(); } + + void setHash(unsigned Hash) { MDNodeSubclassData = Hash; } + void recalculateHash(); + + static MDTuple *getImpl(LLVMContext &Context, ArrayRef MDs, + StorageType Storage, bool ShouldCreate = true); + +public: + /// \brief Get the hash, if any. + unsigned getHash() const { return MDNodeSubclassData; } + + static MDTuple *get(LLVMContext &Context, ArrayRef MDs) { + return getImpl(Context, MDs, Uniqued); + } + static MDTuple *getIfExists(LLVMContext &Context, ArrayRef MDs) { + return getImpl(Context, MDs, Uniqued, /* ShouldCreate */ false); + } + + /// \brief Return a distinct node. + /// + /// Return a distinct node -- i.e., a node that is not uniqued. + static MDTuple *getDistinct(LLVMContext &Context, ArrayRef MDs) { + return getImpl(Context, MDs, Distinct); + } + + /// \brief Return a temporary node. + /// + /// For use in constructing cyclic MDNode structures. A temporary MDNode is + /// not uniqued, may be RAUW'd, and must be manually deleted with + /// deleteTemporary. + static MDTuple *getTemporary(LLVMContext &Context, ArrayRef MDs) { + return getImpl(Context, MDs, Temporary); + } + + static bool classof(const Metadata *MD) { + return MD->getMetadataID() == MDTupleKind; + } + private: - // destroy - Delete this node. Only when there are no uses. - void destroy(); + MDTuple *uniquifyImpl(); + void eraseFromStoreImpl(); +}; + +MDTuple *MDNode::get(LLVMContext &Context, ArrayRef MDs) { + return MDTuple::get(Context, MDs); +} +MDTuple *MDNode::getIfExists(LLVMContext &Context, ArrayRef MDs) { + return MDTuple::getIfExists(Context, MDs); +} +MDTuple *MDNode::getDistinct(LLVMContext &Context, ArrayRef MDs) { + return MDTuple::getDistinct(Context, MDs); +} +MDTuple *MDNode::getTemporary(LLVMContext &Context, ArrayRef MDs) { + return MDTuple::getTemporary(Context, MDs); +} + +/// \brief Debug location. +/// +/// A debug location in source code, used for debug info and otherwise. +class MDLocation : public UniquableMDNode { + friend class LLVMContextImpl; + friend class UniquableMDNode; + + MDLocation(LLVMContext &C, StorageType Storage, unsigned Line, + unsigned Column, ArrayRef MDs); + ~MDLocation() { dropAllReferences(); } + + static MDLocation *getImpl(LLVMContext &Context, unsigned Line, + unsigned Column, Metadata *Scope, + Metadata *InlinedAt, StorageType Storage, + bool ShouldCreate = true); + + // Disallow replacing operands. + void replaceOperandWith(unsigned I, Metadata *New) LLVM_DELETED_FUNCTION; - bool isNotUniqued() const { - return (getSubclassDataFromValue() & NotUniquedBit) != 0; +public: + static MDLocation *get(LLVMContext &Context, unsigned Line, unsigned Column, + Metadata *Scope, Metadata *InlinedAt = nullptr) { + return getImpl(Context, Line, Column, Scope, InlinedAt, Uniqued); + } + static MDLocation *getIfExists(LLVMContext &Context, unsigned Line, + unsigned Column, Metadata *Scope, + Metadata *InlinedAt = nullptr) { + return getImpl(Context, Line, Column, Scope, InlinedAt, Uniqued, + /* ShouldCreate */ false); + } + static MDLocation *getDistinct(LLVMContext &Context, unsigned Line, + unsigned Column, Metadata *Scope, + Metadata *InlinedAt = nullptr) { + return getImpl(Context, Line, Column, Scope, InlinedAt, Distinct); } - void setIsNotUniqued(); - // Shadow Value::setValueSubclassData with a private forwarding method so that - // any future subclasses cannot accidentally use it. - void setValueSubclassData(unsigned short D) { - Value::setValueSubclassData(D); + unsigned getLine() const { return MDNodeSubclassData; } + unsigned getColumn() const { return SubclassData16; } + Metadata *getScope() const { return getOperand(0); } + Metadata *getInlinedAt() const { + if (getNumOperands() == 2) + return getOperand(1); + return nullptr; } + + static bool classof(const Metadata *MD) { + return MD->getMetadataID() == MDLocationKind; + } + +private: + MDLocation *uniquifyImpl(); + void eraseFromStoreImpl(); }; //===----------------------------------------------------------------------===// -/// NamedMDNode - a tuple of MDNodes. Despite its name, a NamedMDNode isn't -/// itself an MDNode. NamedMDNodes belong to modules, have names, and contain -/// lists of MDNodes. +/// \brief A tuple of MDNodes. +/// +/// Despite its name, a NamedMDNode isn't itself an MDNode. NamedMDNodes belong +/// to modules, have names, and contain lists of MDNodes. +/// +/// TODO: Inherit from Metadata. class NamedMDNode : public ilist_node { friend class SymbolTableListTraits; friend struct ilist_traits; @@ -202,7 +980,7 @@ class NamedMDNode : public ilist_node { std::string Name; Module *Parent; - void *Operands; // SmallVector, 4> + void *Operands; // SmallVector void setParent(Module *M) { Parent = M; } @@ -218,8 +996,7 @@ class NamedMDNode : public ilist_node { friend class NamedMDNode; public: - op_iterator_impl() : Node(0), Idx(0) { } - op_iterator_impl(const op_iterator_impl &o) : Node(o.Node), Idx(o.Idx) { } + op_iterator_impl() : Node(nullptr), Idx(0) { } bool operator==(const op_iterator_impl &o) const { return Idx == o.Idx; } bool operator!=(const op_iterator_impl &o) const { return Idx != o.Idx; } @@ -242,55 +1019,38 @@ class NamedMDNode : public ilist_node { return tmp; } - op_iterator_impl &operator=(const op_iterator_impl &o) { - Node = o.Node; - Idx = o.Idx; - return *this; - } T1 operator*() const { return Node->getOperand(Idx); } }; public: - /// eraseFromParent - Drop all references and remove the node from parent - /// module. + /// \brief Drop all references and remove the node from parent module. void eraseFromParent(); - /// dropAllReferences - Remove all uses and clear node vector. + /// \brief Remove all uses and clear node vector. void dropAllReferences(); - /// ~NamedMDNode - Destroy NamedMDNode. ~NamedMDNode(); - /// getParent - Get the module that holds this named metadata collection. + /// \brief Get the module that holds this named metadata collection. inline Module *getParent() { return Parent; } inline const Module *getParent() const { return Parent; } - /// getOperand - Return specified operand. MDNode *getOperand(unsigned i) const; - - /// getNumOperands - Return the number of NamedMDNode operands. unsigned getNumOperands() const; - - /// addOperand - Add metadata operand. void addOperand(MDNode *M); - - /// getName - Return a constant reference to this named metadata's name. + void setOperand(unsigned I, MDNode *New); StringRef getName() const; - - /// print - Implement operator<< on NamedMDNode. - void print(raw_ostream &ROS, AssemblyAnnotationWriter *AAW = 0) const; - - /// dump() - Allow printing of NamedMDNodes from the debugger. + void print(raw_ostream &ROS) const; void dump() const; // --------------------------------------------------------------------------- // Operand Iterator interface... // - typedef op_iterator_impl op_iterator; + typedef op_iterator_impl op_iterator; op_iterator op_begin() { return op_iterator(this, 0); } op_iterator op_end() { return op_iterator(this, getNumOperands()); } - typedef op_iterator_impl const_op_iterator; + typedef op_iterator_impl const_op_iterator; const_op_iterator op_begin() const { return const_op_iterator(this, 0); } const_op_iterator op_end() const { return const_op_iterator(this, getNumOperands()); }