LLVM API Documentation

Metadata.h
Go to the documentation of this file.
00001 //===- llvm/IR/Metadata.h - Metadata definitions ----------------*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 /// @file
00011 /// This file contains the declarations for metadata subclasses.
00012 /// They represent the different flavors of metadata that live in LLVM.
00013 //
00014 //===----------------------------------------------------------------------===//
00015 
00016 #ifndef LLVM_IR_METADATA_H
00017 #define LLVM_IR_METADATA_H
00018 
00019 #include "llvm/ADT/ArrayRef.h"
00020 #include "llvm/ADT/DenseMap.h"
00021 #include "llvm/ADT/ilist_node.h"
00022 #include "llvm/ADT/iterator_range.h"
00023 #include "llvm/IR/Constant.h"
00024 #include "llvm/IR/MetadataTracking.h"
00025 #include "llvm/IR/Value.h"
00026 #include "llvm/Support/ErrorHandling.h"
00027 #include <type_traits>
00028 
00029 namespace llvm {
00030 class LLVMContext;
00031 class Module;
00032 template<typename ValueSubClass, typename ItemParentClass>
00033   class SymbolTableListTraits;
00034 
00035 
00036 enum LLVMConstants : uint32_t {
00037   DEBUG_METADATA_VERSION = 2  // Current debug info version number.
00038 };
00039 
00040 /// \brief Root of the metadata hierarchy.
00041 ///
00042 /// This is a root class for typeless data in the IR.
00043 class Metadata {
00044   friend class ReplaceableMetadataImpl;
00045 
00046   /// \brief RTTI.
00047   const unsigned char SubclassID;
00048 
00049 protected:
00050   /// \brief Active type of storage.
00051   enum StorageType { Uniqued, Distinct, Temporary };
00052 
00053   /// \brief Storage flag for non-uniqued, otherwise unowned, metadata.
00054   unsigned Storage : 2;
00055   // TODO: expose remaining bits to subclasses.
00056 
00057   unsigned short SubclassData16;
00058   unsigned SubclassData32;
00059 
00060 public:
00061   enum MetadataKind {
00062     MDTupleKind,
00063     MDLocationKind,
00064     GenericDebugNodeKind,
00065     MDSubrangeKind,
00066     MDEnumeratorKind,
00067     MDBasicTypeKind,
00068     MDDerivedTypeKind,
00069     MDCompositeTypeKind,
00070     MDSubroutineTypeKind,
00071     MDFileKind,
00072     MDCompileUnitKind,
00073     MDSubprogramKind,
00074     MDLexicalBlockKind,
00075     MDLexicalBlockFileKind,
00076     MDNamespaceKind,
00077     MDTemplateTypeParameterKind,
00078     MDTemplateValueParameterKind,
00079     MDGlobalVariableKind,
00080     MDLocalVariableKind,
00081     MDExpressionKind,
00082     MDObjCPropertyKind,
00083     MDImportedEntityKind,
00084     ConstantAsMetadataKind,
00085     LocalAsMetadataKind,
00086     MDStringKind
00087   };
00088 
00089 protected:
00090   Metadata(unsigned ID, StorageType Storage)
00091       : SubclassID(ID), Storage(Storage), SubclassData16(0), SubclassData32(0) {
00092   }
00093   ~Metadata() {}
00094 
00095   /// \brief Default handling of a changed operand, which asserts.
00096   ///
00097   /// If subclasses pass themselves in as owners to a tracking node reference,
00098   /// they must provide an implementation of this method.
00099   void handleChangedOperand(void *, Metadata *) {
00100     llvm_unreachable("Unimplemented in Metadata subclass");
00101   }
00102 
00103 public:
00104   unsigned getMetadataID() const { return SubclassID; }
00105 
00106   /// \brief User-friendly dump.
00107   void dump() const;
00108   void print(raw_ostream &OS) const;
00109   void printAsOperand(raw_ostream &OS, bool PrintType = true,
00110                       const Module *M = nullptr) const;
00111 };
00112 
00113 #define HANDLE_METADATA(CLASS) class CLASS;
00114 #include "llvm/IR/Metadata.def"
00115 
00116 inline raw_ostream &operator<<(raw_ostream &OS, const Metadata &MD) {
00117   MD.print(OS);
00118   return OS;
00119 }
00120 
00121 /// \brief Metadata wrapper in the Value hierarchy.
00122 ///
00123 /// A member of the \a Value hierarchy to represent a reference to metadata.
00124 /// This allows, e.g., instrinsics to have metadata as operands.
00125 ///
00126 /// Notably, this is the only thing in either hierarchy that is allowed to
00127 /// reference \a LocalAsMetadata.
00128 class MetadataAsValue : public Value {
00129   friend class ReplaceableMetadataImpl;
00130   friend class LLVMContextImpl;
00131 
00132   Metadata *MD;
00133 
00134   MetadataAsValue(Type *Ty, Metadata *MD);
00135   ~MetadataAsValue();
00136 
00137   /// \brief Drop use of metadata (during teardown).
00138   void dropUse() { MD = nullptr; }
00139 
00140 public:
00141   static MetadataAsValue *get(LLVMContext &Context, Metadata *MD);
00142   static MetadataAsValue *getIfExists(LLVMContext &Context, Metadata *MD);
00143   Metadata *getMetadata() const { return MD; }
00144 
00145   static bool classof(const Value *V) {
00146     return V->getValueID() == MetadataAsValueVal;
00147   }
00148 
00149 private:
00150   void handleChangedMetadata(Metadata *MD);
00151   void track();
00152   void untrack();
00153 };
00154 
00155 /// \brief Shared implementation of use-lists for replaceable metadata.
00156 ///
00157 /// Most metadata cannot be RAUW'ed.  This is a shared implementation of
00158 /// use-lists and associated API for the two that support it (\a ValueAsMetadata
00159 /// and \a TempMDNode).
00160 class ReplaceableMetadataImpl {
00161   friend class MetadataTracking;
00162 
00163 public:
00164   typedef MetadataTracking::OwnerTy OwnerTy;
00165 
00166 private:
00167   LLVMContext &Context;
00168   uint64_t NextIndex;
00169   SmallDenseMap<void *, std::pair<OwnerTy, uint64_t>, 4> UseMap;
00170 
00171 public:
00172   ReplaceableMetadataImpl(LLVMContext &Context)
00173       : Context(Context), NextIndex(0) {}
00174   ~ReplaceableMetadataImpl() {
00175     assert(UseMap.empty() && "Cannot destroy in-use replaceable metadata");
00176   }
00177 
00178   LLVMContext &getContext() const { return Context; }
00179 
00180   /// \brief Replace all uses of this with MD.
00181   ///
00182   /// Replace all uses of this with \c MD, which is allowed to be null.
00183   void replaceAllUsesWith(Metadata *MD);
00184 
00185   /// \brief Resolve all uses of this.
00186   ///
00187   /// Resolve all uses of this, turning off RAUW permanently.  If \c
00188   /// ResolveUsers, call \a MDNode::resolve() on any users whose last operand
00189   /// is resolved.
00190   void resolveAllUses(bool ResolveUsers = true);
00191 
00192 private:
00193   void addRef(void *Ref, OwnerTy Owner);
00194   void dropRef(void *Ref);
00195   void moveRef(void *Ref, void *New, const Metadata &MD);
00196 
00197   static ReplaceableMetadataImpl *get(Metadata &MD);
00198 };
00199 
00200 /// \brief Value wrapper in the Metadata hierarchy.
00201 ///
00202 /// This is a custom value handle that allows other metadata to refer to
00203 /// classes in the Value hierarchy.
00204 ///
00205 /// Because of full uniquing support, each value is only wrapped by a single \a
00206 /// ValueAsMetadata object, so the lookup maps are far more efficient than
00207 /// those using ValueHandleBase.
00208 class ValueAsMetadata : public Metadata, ReplaceableMetadataImpl {
00209   friend class ReplaceableMetadataImpl;
00210   friend class LLVMContextImpl;
00211 
00212   Value *V;
00213 
00214   /// \brief Drop users without RAUW (during teardown).
00215   void dropUsers() {
00216     ReplaceableMetadataImpl::resolveAllUses(/* ResolveUsers */ false);
00217   }
00218 
00219 protected:
00220   ValueAsMetadata(unsigned ID, Value *V)
00221       : Metadata(ID, Uniqued), ReplaceableMetadataImpl(V->getContext()), V(V) {
00222     assert(V && "Expected valid value");
00223   }
00224   ~ValueAsMetadata() {}
00225 
00226 public:
00227   static ValueAsMetadata *get(Value *V);
00228   static ConstantAsMetadata *getConstant(Value *C) {
00229     return cast<ConstantAsMetadata>(get(C));
00230   }
00231   static LocalAsMetadata *getLocal(Value *Local) {
00232     return cast<LocalAsMetadata>(get(Local));
00233   }
00234 
00235   static ValueAsMetadata *getIfExists(Value *V);
00236   static ConstantAsMetadata *getConstantIfExists(Value *C) {
00237     return cast_or_null<ConstantAsMetadata>(getIfExists(C));
00238   }
00239   static LocalAsMetadata *getLocalIfExists(Value *Local) {
00240     return cast_or_null<LocalAsMetadata>(getIfExists(Local));
00241   }
00242 
00243   Value *getValue() const { return V; }
00244   Type *getType() const { return V->getType(); }
00245   LLVMContext &getContext() const { return V->getContext(); }
00246 
00247   static void handleDeletion(Value *V);
00248   static void handleRAUW(Value *From, Value *To);
00249 
00250 protected:
00251   /// \brief Handle collisions after \a Value::replaceAllUsesWith().
00252   ///
00253   /// RAUW isn't supported directly for \a ValueAsMetadata, but if the wrapped
00254   /// \a Value gets RAUW'ed and the target already exists, this is used to
00255   /// merge the two metadata nodes.
00256   void replaceAllUsesWith(Metadata *MD) {
00257     ReplaceableMetadataImpl::replaceAllUsesWith(MD);
00258   }
00259 
00260 public:
00261   static bool classof(const Metadata *MD) {
00262     return MD->getMetadataID() == LocalAsMetadataKind ||
00263            MD->getMetadataID() == ConstantAsMetadataKind;
00264   }
00265 };
00266 
00267 class ConstantAsMetadata : public ValueAsMetadata {
00268   friend class ValueAsMetadata;
00269 
00270   ConstantAsMetadata(Constant *C)
00271       : ValueAsMetadata(ConstantAsMetadataKind, C) {}
00272 
00273 public:
00274   static ConstantAsMetadata *get(Constant *C) {
00275     return ValueAsMetadata::getConstant(C);
00276   }
00277   static ConstantAsMetadata *getIfExists(Constant *C) {
00278     return ValueAsMetadata::getConstantIfExists(C);
00279   }
00280 
00281   Constant *getValue() const {
00282     return cast<Constant>(ValueAsMetadata::getValue());
00283   }
00284 
00285   static bool classof(const Metadata *MD) {
00286     return MD->getMetadataID() == ConstantAsMetadataKind;
00287   }
00288 };
00289 
00290 class LocalAsMetadata : public ValueAsMetadata {
00291   friend class ValueAsMetadata;
00292 
00293   LocalAsMetadata(Value *Local)
00294       : ValueAsMetadata(LocalAsMetadataKind, Local) {
00295     assert(!isa<Constant>(Local) && "Expected local value");
00296   }
00297 
00298 public:
00299   static LocalAsMetadata *get(Value *Local) {
00300     return ValueAsMetadata::getLocal(Local);
00301   }
00302   static LocalAsMetadata *getIfExists(Value *Local) {
00303     return ValueAsMetadata::getLocalIfExists(Local);
00304   }
00305 
00306   static bool classof(const Metadata *MD) {
00307     return MD->getMetadataID() == LocalAsMetadataKind;
00308   }
00309 };
00310 
00311 /// \brief Transitional API for extracting constants from Metadata.
00312 ///
00313 /// This namespace contains transitional functions for metadata that points to
00314 /// \a Constants.
00315 ///
00316 /// In prehistory -- when metadata was a subclass of \a Value -- \a MDNode
00317 /// operands could refer to any \a Value.  There's was a lot of code like this:
00318 ///
00319 /// \code
00320 ///     MDNode *N = ...;
00321 ///     auto *CI = dyn_cast<ConstantInt>(N->getOperand(2));
00322 /// \endcode
00323 ///
00324 /// Now that \a Value and \a Metadata are in separate hierarchies, maintaining
00325 /// the semantics for \a isa(), \a cast(), \a dyn_cast() (etc.) requires three
00326 /// steps: cast in the \a Metadata hierarchy, extraction of the \a Value, and
00327 /// cast in the \a Value hierarchy.  Besides creating boiler-plate, this
00328 /// requires subtle control flow changes.
00329 ///
00330 /// The end-goal is to create a new type of metadata, called (e.g.) \a MDInt,
00331 /// so that metadata can refer to numbers without traversing a bridge to the \a
00332 /// Value hierarchy.  In this final state, the code above would look like this:
00333 ///
00334 /// \code
00335 ///     MDNode *N = ...;
00336 ///     auto *MI = dyn_cast<MDInt>(N->getOperand(2));
00337 /// \endcode
00338 ///
00339 /// The API in this namespace supports the transition.  \a MDInt doesn't exist
00340 /// yet, and even once it does, changing each metadata schema to use it is its
00341 /// own mini-project.  In the meantime this API prevents us from introducing
00342 /// complex and bug-prone control flow that will disappear in the end.  In
00343 /// particular, the above code looks like this:
00344 ///
00345 /// \code
00346 ///     MDNode *N = ...;
00347 ///     auto *CI = mdconst::dyn_extract<ConstantInt>(N->getOperand(2));
00348 /// \endcode
00349 ///
00350 /// The full set of provided functions includes:
00351 ///
00352 ///   mdconst::hasa                <=> isa
00353 ///   mdconst::extract             <=> cast
00354 ///   mdconst::extract_or_null     <=> cast_or_null
00355 ///   mdconst::dyn_extract         <=> dyn_cast
00356 ///   mdconst::dyn_extract_or_null <=> dyn_cast_or_null
00357 ///
00358 /// The target of the cast must be a subclass of \a Constant.
00359 namespace mdconst {
00360 
00361 namespace detail {
00362 template <class T> T &make();
00363 template <class T, class Result> struct HasDereference {
00364   typedef char Yes[1];
00365   typedef char No[2];
00366   template <size_t N> struct SFINAE {};
00367 
00368   template <class U, class V>
00369   static Yes &hasDereference(SFINAE<sizeof(static_cast<V>(*make<U>()))> * = 0);
00370   template <class U, class V> static No &hasDereference(...);
00371 
00372   static const bool value =
00373       sizeof(hasDereference<T, Result>(nullptr)) == sizeof(Yes);
00374 };
00375 template <class V, class M> struct IsValidPointer {
00376   static const bool value = std::is_base_of<Constant, V>::value &&
00377                             HasDereference<M, const Metadata &>::value;
00378 };
00379 template <class V, class M> struct IsValidReference {
00380   static const bool value = std::is_base_of<Constant, V>::value &&
00381                             std::is_convertible<M, const Metadata &>::value;
00382 };
00383 } // end namespace detail
00384 
00385 /// \brief Check whether Metadata has a Value.
00386 ///
00387 /// As an analogue to \a isa(), check whether \c MD has an \a Value inside of
00388 /// type \c X.
00389 template <class X, class Y>
00390 inline typename std::enable_if<detail::IsValidPointer<X, Y>::value, bool>::type
00391 hasa(Y &&MD) {
00392   assert(MD && "Null pointer sent into hasa");
00393   if (auto *V = dyn_cast<ConstantAsMetadata>(MD))
00394     return isa<X>(V->getValue());
00395   return false;
00396 }
00397 template <class X, class Y>
00398 inline
00399     typename std::enable_if<detail::IsValidReference<X, Y &>::value, bool>::type
00400     hasa(Y &MD) {
00401   return hasa(&MD);
00402 }
00403 
00404 /// \brief Extract a Value from Metadata.
00405 ///
00406 /// As an analogue to \a cast(), extract the \a Value subclass \c X from \c MD.
00407 template <class X, class Y>
00408 inline typename std::enable_if<detail::IsValidPointer<X, Y>::value, X *>::type
00409 extract(Y &&MD) {
00410   return cast<X>(cast<ConstantAsMetadata>(MD)->getValue());
00411 }
00412 template <class X, class Y>
00413 inline
00414     typename std::enable_if<detail::IsValidReference<X, Y &>::value, X *>::type
00415     extract(Y &MD) {
00416   return extract(&MD);
00417 }
00418 
00419 /// \brief Extract a Value from Metadata, allowing null.
00420 ///
00421 /// As an analogue to \a cast_or_null(), extract the \a Value subclass \c X
00422 /// from \c MD, allowing \c MD to be null.
00423 template <class X, class Y>
00424 inline typename std::enable_if<detail::IsValidPointer<X, Y>::value, X *>::type
00425 extract_or_null(Y &&MD) {
00426   if (auto *V = cast_or_null<ConstantAsMetadata>(MD))
00427     return cast<X>(V->getValue());
00428   return nullptr;
00429 }
00430 
00431 /// \brief Extract a Value from Metadata, if any.
00432 ///
00433 /// As an analogue to \a dyn_cast_or_null(), extract the \a Value subclass \c X
00434 /// from \c MD, return null if \c MD doesn't contain a \a Value or if the \a
00435 /// Value it does contain is of the wrong subclass.
00436 template <class X, class Y>
00437 inline typename std::enable_if<detail::IsValidPointer<X, Y>::value, X *>::type
00438 dyn_extract(Y &&MD) {
00439   if (auto *V = dyn_cast<ConstantAsMetadata>(MD))
00440     return dyn_cast<X>(V->getValue());
00441   return nullptr;
00442 }
00443 
00444 /// \brief Extract a Value from Metadata, if any, allowing null.
00445 ///
00446 /// As an analogue to \a dyn_cast_or_null(), extract the \a Value subclass \c X
00447 /// from \c MD, return null if \c MD doesn't contain a \a Value or if the \a
00448 /// Value it does contain is of the wrong subclass, allowing \c MD to be null.
00449 template <class X, class Y>
00450 inline typename std::enable_if<detail::IsValidPointer<X, Y>::value, X *>::type
00451 dyn_extract_or_null(Y &&MD) {
00452   if (auto *V = dyn_cast_or_null<ConstantAsMetadata>(MD))
00453     return dyn_cast<X>(V->getValue());
00454   return nullptr;
00455 }
00456 
00457 } // end namespace mdconst
00458 
00459 //===----------------------------------------------------------------------===//
00460 /// \brief A single uniqued string.
00461 ///
00462 /// These are used to efficiently contain a byte sequence for metadata.
00463 /// MDString is always unnamed.
00464 class MDString : public Metadata {
00465   friend class StringMapEntry<MDString>;
00466 
00467   MDString(const MDString &) = delete;
00468   MDString &operator=(MDString &&) = delete;
00469   MDString &operator=(const MDString &) = delete;
00470 
00471   StringMapEntry<MDString> *Entry;
00472   MDString() : Metadata(MDStringKind, Uniqued), Entry(nullptr) {}
00473   MDString(MDString &&) : Metadata(MDStringKind, Uniqued) {}
00474 
00475 public:
00476   static MDString *get(LLVMContext &Context, StringRef Str);
00477   static MDString *get(LLVMContext &Context, const char *Str) {
00478     return get(Context, Str ? StringRef(Str) : StringRef());
00479   }
00480 
00481   StringRef getString() const;
00482 
00483   unsigned getLength() const { return (unsigned)getString().size(); }
00484 
00485   typedef StringRef::iterator iterator;
00486 
00487   /// \brief Pointer to the first byte of the string.
00488   iterator begin() const { return getString().begin(); }
00489 
00490   /// \brief Pointer to one byte past the end of the string.
00491   iterator end() const { return getString().end(); }
00492 
00493   const unsigned char *bytes_begin() const { return getString().bytes_begin(); }
00494   const unsigned char *bytes_end() const { return getString().bytes_end(); }
00495 
00496   /// \brief Methods for support type inquiry through isa, cast, and dyn_cast.
00497   static bool classof(const Metadata *MD) {
00498     return MD->getMetadataID() == MDStringKind;
00499   }
00500 };
00501 
00502 /// \brief A collection of metadata nodes that might be associated with a
00503 /// memory access used by the alias-analysis infrastructure.
00504 struct AAMDNodes {
00505   explicit AAMDNodes(MDNode *T = nullptr, MDNode *S = nullptr,
00506                      MDNode *N = nullptr)
00507       : TBAA(T), Scope(S), NoAlias(N) {}
00508 
00509   bool operator==(const AAMDNodes &A) const {
00510     return TBAA == A.TBAA && Scope == A.Scope && NoAlias == A.NoAlias;
00511   }
00512 
00513   bool operator!=(const AAMDNodes &A) const { return !(*this == A); }
00514 
00515   explicit operator bool() const { return TBAA || Scope || NoAlias; }
00516 
00517   /// \brief The tag for type-based alias analysis.
00518   MDNode *TBAA;
00519 
00520   /// \brief The tag for alias scope specification (used with noalias).
00521   MDNode *Scope;
00522 
00523   /// \brief The tag specifying the noalias scope.
00524   MDNode *NoAlias;
00525 };
00526 
00527 // Specialize DenseMapInfo for AAMDNodes.
00528 template<>
00529 struct DenseMapInfo<AAMDNodes> {
00530   static inline AAMDNodes getEmptyKey() {
00531     return AAMDNodes(DenseMapInfo<MDNode *>::getEmptyKey(), 0, 0);
00532   }
00533   static inline AAMDNodes getTombstoneKey() {
00534     return AAMDNodes(DenseMapInfo<MDNode *>::getTombstoneKey(), 0, 0);
00535   }
00536   static unsigned getHashValue(const AAMDNodes &Val) {
00537     return DenseMapInfo<MDNode *>::getHashValue(Val.TBAA) ^
00538            DenseMapInfo<MDNode *>::getHashValue(Val.Scope) ^
00539            DenseMapInfo<MDNode *>::getHashValue(Val.NoAlias);
00540   }
00541   static bool isEqual(const AAMDNodes &LHS, const AAMDNodes &RHS) {
00542     return LHS == RHS;
00543   }
00544 };
00545 
00546 /// \brief Tracking metadata reference owned by Metadata.
00547 ///
00548 /// Similar to \a TrackingMDRef, but it's expected to be owned by an instance
00549 /// of \a Metadata, which has the option of registering itself for callbacks to
00550 /// re-unique itself.
00551 ///
00552 /// In particular, this is used by \a MDNode.
00553 class MDOperand {
00554   MDOperand(MDOperand &&) = delete;
00555   MDOperand(const MDOperand &) = delete;
00556   MDOperand &operator=(MDOperand &&) = delete;
00557   MDOperand &operator=(const MDOperand &) = delete;
00558 
00559   Metadata *MD;
00560 
00561 public:
00562   MDOperand() : MD(nullptr) {}
00563   ~MDOperand() { untrack(); }
00564 
00565   Metadata *get() const { return MD; }
00566   operator Metadata *() const { return get(); }
00567   Metadata *operator->() const { return get(); }
00568   Metadata &operator*() const { return *get(); }
00569 
00570   void reset() {
00571     untrack();
00572     MD = nullptr;
00573   }
00574   void reset(Metadata *MD, Metadata *Owner) {
00575     untrack();
00576     this->MD = MD;
00577     track(Owner);
00578   }
00579 
00580 private:
00581   void track(Metadata *Owner) {
00582     if (MD) {
00583       if (Owner)
00584         MetadataTracking::track(this, *MD, *Owner);
00585       else
00586         MetadataTracking::track(MD);
00587     }
00588   }
00589   void untrack() {
00590     assert(static_cast<void *>(this) == &MD && "Expected same address");
00591     if (MD)
00592       MetadataTracking::untrack(MD);
00593   }
00594 };
00595 
00596 template <> struct simplify_type<MDOperand> {
00597   typedef Metadata *SimpleType;
00598   static SimpleType getSimplifiedValue(MDOperand &MD) { return MD.get(); }
00599 };
00600 
00601 template <> struct simplify_type<const MDOperand> {
00602   typedef Metadata *SimpleType;
00603   static SimpleType getSimplifiedValue(const MDOperand &MD) { return MD.get(); }
00604 };
00605 
00606 /// \brief Pointer to the context, with optional RAUW support.
00607 ///
00608 /// Either a raw (non-null) pointer to the \a LLVMContext, or an owned pointer
00609 /// to \a ReplaceableMetadataImpl (which has a reference to \a LLVMContext).
00610 class ContextAndReplaceableUses {
00611   PointerUnion<LLVMContext *, ReplaceableMetadataImpl *> Ptr;
00612 
00613   ContextAndReplaceableUses() = delete;
00614   ContextAndReplaceableUses(ContextAndReplaceableUses &&) = delete;
00615   ContextAndReplaceableUses(const ContextAndReplaceableUses &) = delete;
00616   ContextAndReplaceableUses &operator=(ContextAndReplaceableUses &&) = delete;
00617   ContextAndReplaceableUses &
00618   operator=(const ContextAndReplaceableUses &) = delete;
00619 
00620 public:
00621   ContextAndReplaceableUses(LLVMContext &Context) : Ptr(&Context) {}
00622   ContextAndReplaceableUses(
00623       std::unique_ptr<ReplaceableMetadataImpl> ReplaceableUses)
00624       : Ptr(ReplaceableUses.release()) {
00625     assert(getReplaceableUses() && "Expected non-null replaceable uses");
00626   }
00627   ~ContextAndReplaceableUses() { delete getReplaceableUses(); }
00628 
00629   operator LLVMContext &() { return getContext(); }
00630 
00631   /// \brief Whether this contains RAUW support.
00632   bool hasReplaceableUses() const {
00633     return Ptr.is<ReplaceableMetadataImpl *>();
00634   }
00635   LLVMContext &getContext() const {
00636     if (hasReplaceableUses())
00637       return getReplaceableUses()->getContext();
00638     return *Ptr.get<LLVMContext *>();
00639   }
00640   ReplaceableMetadataImpl *getReplaceableUses() const {
00641     if (hasReplaceableUses())
00642       return Ptr.get<ReplaceableMetadataImpl *>();
00643     return nullptr;
00644   }
00645 
00646   /// \brief Assign RAUW support to this.
00647   ///
00648   /// Make this replaceable, taking ownership of \c ReplaceableUses (which must
00649   /// not be null).
00650   void
00651   makeReplaceable(std::unique_ptr<ReplaceableMetadataImpl> ReplaceableUses) {
00652     assert(ReplaceableUses && "Expected non-null replaceable uses");
00653     assert(&ReplaceableUses->getContext() == &getContext() &&
00654            "Expected same context");
00655     delete getReplaceableUses();
00656     Ptr = ReplaceableUses.release();
00657   }
00658 
00659   /// \brief Drop RAUW support.
00660   ///
00661   /// Cede ownership of RAUW support, returning it.
00662   std::unique_ptr<ReplaceableMetadataImpl> takeReplaceableUses() {
00663     assert(hasReplaceableUses() && "Expected to own replaceable uses");
00664     std::unique_ptr<ReplaceableMetadataImpl> ReplaceableUses(
00665         getReplaceableUses());
00666     Ptr = &ReplaceableUses->getContext();
00667     return ReplaceableUses;
00668   }
00669 };
00670 
00671 struct TempMDNodeDeleter {
00672   inline void operator()(MDNode *Node) const;
00673 };
00674 
00675 #define HANDLE_MDNODE_LEAF(CLASS)                                              \
00676   typedef std::unique_ptr<CLASS, TempMDNodeDeleter> Temp##CLASS;
00677 #define HANDLE_MDNODE_BRANCH(CLASS) HANDLE_MDNODE_LEAF(CLASS)
00678 #include "llvm/IR/Metadata.def"
00679 
00680 /// \brief Metadata node.
00681 ///
00682 /// Metadata nodes can be uniqued, like constants, or distinct.  Temporary
00683 /// metadata nodes (with full support for RAUW) can be used to delay uniquing
00684 /// until forward references are known.  The basic metadata node is an \a
00685 /// MDTuple.
00686 ///
00687 /// There is limited support for RAUW at construction time.  At construction
00688 /// time, if any operand is a temporary node (or an unresolved uniqued node,
00689 /// which indicates a transitive temporary operand), the node itself will be
00690 /// unresolved.  As soon as all operands become resolved, it will drop RAUW
00691 /// support permanently.
00692 ///
00693 /// If an unresolved node is part of a cycle, \a resolveCycles() needs
00694 /// to be called on some member of the cycle once all temporary nodes have been
00695 /// replaced.
00696 class MDNode : public Metadata {
00697   friend class ReplaceableMetadataImpl;
00698   friend class LLVMContextImpl;
00699 
00700   MDNode(const MDNode &) = delete;
00701   void operator=(const MDNode &) = delete;
00702   void *operator new(size_t) = delete;
00703 
00704   unsigned NumOperands;
00705   unsigned NumUnresolved;
00706 
00707 protected:
00708   ContextAndReplaceableUses Context;
00709 
00710   void *operator new(size_t Size, unsigned NumOps);
00711   void operator delete(void *Mem);
00712 
00713   /// \brief Required by std, but never called.
00714   void operator delete(void *, unsigned) {
00715     llvm_unreachable("Constructor throws?");
00716   }
00717 
00718   /// \brief Required by std, but never called.
00719   void operator delete(void *, unsigned, bool) {
00720     llvm_unreachable("Constructor throws?");
00721   }
00722 
00723   MDNode(LLVMContext &Context, unsigned ID, StorageType Storage,
00724          ArrayRef<Metadata *> Ops1, ArrayRef<Metadata *> Ops2 = None);
00725   ~MDNode() {}
00726 
00727   void dropAllReferences();
00728 
00729   MDOperand *mutable_begin() { return mutable_end() - NumOperands; }
00730   MDOperand *mutable_end() { return reinterpret_cast<MDOperand *>(this); }
00731 
00732 public:
00733   static inline MDTuple *get(LLVMContext &Context, ArrayRef<Metadata *> MDs);
00734   static inline MDTuple *getIfExists(LLVMContext &Context,
00735                                      ArrayRef<Metadata *> MDs);
00736   static inline MDTuple *getDistinct(LLVMContext &Context,
00737                                      ArrayRef<Metadata *> MDs);
00738   static inline TempMDTuple getTemporary(LLVMContext &Context,
00739                                          ArrayRef<Metadata *> MDs);
00740 
00741   /// \brief Create a (temporary) clone of this.
00742   TempMDNode clone() const;
00743 
00744   /// \brief Deallocate a node created by getTemporary.
00745   ///
00746   /// Calls \c replaceAllUsesWith(nullptr) before deleting, so any remaining
00747   /// references will be reset.
00748   static void deleteTemporary(MDNode *N);
00749 
00750   LLVMContext &getContext() const { return Context.getContext(); }
00751 
00752   /// \brief Replace a specific operand.
00753   void replaceOperandWith(unsigned I, Metadata *New);
00754 
00755   /// \brief Check if node is fully resolved.
00756   ///
00757   /// If \a isTemporary(), this always returns \c false; if \a isDistinct(),
00758   /// this always returns \c true.
00759   ///
00760   /// If \a isUniqued(), returns \c true if this has already dropped RAUW
00761   /// support (because all operands are resolved).
00762   ///
00763   /// As forward declarations are resolved, their containers should get
00764   /// resolved automatically.  However, if this (or one of its operands) is
00765   /// involved in a cycle, \a resolveCycles() needs to be called explicitly.
00766   bool isResolved() const { return !Context.hasReplaceableUses(); }
00767 
00768   bool isUniqued() const { return Storage == Uniqued; }
00769   bool isDistinct() const { return Storage == Distinct; }
00770   bool isTemporary() const { return Storage == Temporary; }
00771 
00772   /// \brief RAUW a temporary.
00773   ///
00774   /// \pre \a isTemporary() must be \c true.
00775   void replaceAllUsesWith(Metadata *MD) {
00776     assert(isTemporary() && "Expected temporary node");
00777     assert(!isResolved() && "Expected RAUW support");
00778     Context.getReplaceableUses()->replaceAllUsesWith(MD);
00779   }
00780 
00781   /// \brief Resolve cycles.
00782   ///
00783   /// Once all forward declarations have been resolved, force cycles to be
00784   /// resolved.
00785   ///
00786   /// \pre No operands (or operands' operands, etc.) have \a isTemporary().
00787   void resolveCycles();
00788 
00789   /// \brief Replace a temporary node with a permanent one.
00790   ///
00791   /// Try to create a uniqued version of \c N -- in place, if possible -- and
00792   /// return it.  If \c N cannot be uniqued, return a distinct node instead.
00793   template <class T>
00794   static typename std::enable_if<std::is_base_of<MDNode, T>::value, T *>::type
00795   replaceWithPermanent(std::unique_ptr<T, TempMDNodeDeleter> N) {
00796     return cast<T>(N.release()->replaceWithPermanentImpl());
00797   }
00798 
00799   /// \brief Replace a temporary node with a uniqued one.
00800   ///
00801   /// Create a uniqued version of \c N -- in place, if possible -- and return
00802   /// it.  Takes ownership of the temporary node.
00803   ///
00804   /// \pre N does not self-reference.
00805   template <class T>
00806   static typename std::enable_if<std::is_base_of<MDNode, T>::value, T *>::type
00807   replaceWithUniqued(std::unique_ptr<T, TempMDNodeDeleter> N) {
00808     return cast<T>(N.release()->replaceWithUniquedImpl());
00809   }
00810 
00811   /// \brief Replace a temporary node with a distinct one.
00812   ///
00813   /// Create a distinct version of \c N -- in place, if possible -- and return
00814   /// it.  Takes ownership of the temporary node.
00815   template <class T>
00816   static typename std::enable_if<std::is_base_of<MDNode, T>::value, T *>::type
00817   replaceWithDistinct(std::unique_ptr<T, TempMDNodeDeleter> N) {
00818     return cast<T>(N.release()->replaceWithDistinctImpl());
00819   }
00820 
00821 private:
00822   MDNode *replaceWithPermanentImpl();
00823   MDNode *replaceWithUniquedImpl();
00824   MDNode *replaceWithDistinctImpl();
00825 
00826 protected:
00827   /// \brief Set an operand.
00828   ///
00829   /// Sets the operand directly, without worrying about uniquing.
00830   void setOperand(unsigned I, Metadata *New);
00831 
00832   void storeDistinctInContext();
00833   template <class T, class StoreT>
00834   static T *storeImpl(T *N, StorageType Storage, StoreT &Store);
00835 
00836 private:
00837   void handleChangedOperand(void *Ref, Metadata *New);
00838 
00839   void resolve();
00840   void resolveAfterOperandChange(Metadata *Old, Metadata *New);
00841   void decrementUnresolvedOperandCount();
00842   unsigned countUnresolvedOperands();
00843 
00844   /// \brief Mutate this to be "uniqued".
00845   ///
00846   /// Mutate this so that \a isUniqued().
00847   /// \pre \a isTemporary().
00848   /// \pre already added to uniquing set.
00849   void makeUniqued();
00850 
00851   /// \brief Mutate this to be "distinct".
00852   ///
00853   /// Mutate this so that \a isDistinct().
00854   /// \pre \a isTemporary().
00855   void makeDistinct();
00856 
00857   void deleteAsSubclass();
00858   MDNode *uniquify();
00859   void eraseFromStore();
00860 
00861   template <class NodeTy> struct HasCachedHash;
00862   template <class NodeTy>
00863   static void dispatchRecalculateHash(NodeTy *N, std::true_type) {
00864     N->recalculateHash();
00865   }
00866   template <class NodeTy>
00867   static void dispatchRecalculateHash(NodeTy *N, std::false_type) {}
00868   template <class NodeTy>
00869   static void dispatchResetHash(NodeTy *N, std::true_type) {
00870     N->setHash(0);
00871   }
00872   template <class NodeTy>
00873   static void dispatchResetHash(NodeTy *N, std::false_type) {}
00874 
00875 public:
00876   typedef const MDOperand *op_iterator;
00877   typedef iterator_range<op_iterator> op_range;
00878 
00879   op_iterator op_begin() const {
00880     return const_cast<MDNode *>(this)->mutable_begin();
00881   }
00882   op_iterator op_end() const {
00883     return const_cast<MDNode *>(this)->mutable_end();
00884   }
00885   op_range operands() const { return op_range(op_begin(), op_end()); }
00886 
00887   const MDOperand &getOperand(unsigned I) const {
00888     assert(I < NumOperands && "Out of range");
00889     return op_begin()[I];
00890   }
00891 
00892   /// \brief Return number of MDNode operands.
00893   unsigned getNumOperands() const { return NumOperands; }
00894 
00895   /// \brief Methods for support type inquiry through isa, cast, and dyn_cast:
00896   static bool classof(const Metadata *MD) {
00897     switch (MD->getMetadataID()) {
00898     default:
00899       return false;
00900 #define HANDLE_MDNODE_LEAF(CLASS)                                              \
00901   case CLASS##Kind:                                                            \
00902     return true;
00903 #include "llvm/IR/Metadata.def"
00904     }
00905   }
00906 
00907   /// \brief Check whether MDNode is a vtable access.
00908   bool isTBAAVtableAccess() const;
00909 
00910   /// \brief Methods for metadata merging.
00911   static MDNode *concatenate(MDNode *A, MDNode *B);
00912   static MDNode *intersect(MDNode *A, MDNode *B);
00913   static MDNode *getMostGenericTBAA(MDNode *A, MDNode *B);
00914   static MDNode *getMostGenericFPMath(MDNode *A, MDNode *B);
00915   static MDNode *getMostGenericRange(MDNode *A, MDNode *B);
00916   static MDNode *getMostGenericAliasScope(MDNode *A, MDNode *B);
00917 };
00918 
00919 /// \brief Tuple of metadata.
00920 ///
00921 /// This is the simple \a MDNode arbitrary tuple.  Nodes are uniqued by
00922 /// default based on their operands.
00923 class MDTuple : public MDNode {
00924   friend class LLVMContextImpl;
00925   friend class MDNode;
00926 
00927   MDTuple(LLVMContext &C, StorageType Storage, unsigned Hash,
00928           ArrayRef<Metadata *> Vals)
00929       : MDNode(C, MDTupleKind, Storage, Vals) {
00930     setHash(Hash);
00931   }
00932   ~MDTuple() { dropAllReferences(); }
00933 
00934   void setHash(unsigned Hash) { SubclassData32 = Hash; }
00935   void recalculateHash();
00936 
00937   static MDTuple *getImpl(LLVMContext &Context, ArrayRef<Metadata *> MDs,
00938                           StorageType Storage, bool ShouldCreate = true);
00939 
00940   TempMDTuple cloneImpl() const {
00941     return getTemporary(getContext(),
00942                         SmallVector<Metadata *, 4>(op_begin(), op_end()));
00943   }
00944 
00945 public:
00946   /// \brief Get the hash, if any.
00947   unsigned getHash() const { return SubclassData32; }
00948 
00949   static MDTuple *get(LLVMContext &Context, ArrayRef<Metadata *> MDs) {
00950     return getImpl(Context, MDs, Uniqued);
00951   }
00952   static MDTuple *getIfExists(LLVMContext &Context, ArrayRef<Metadata *> MDs) {
00953     return getImpl(Context, MDs, Uniqued, /* ShouldCreate */ false);
00954   }
00955 
00956   /// \brief Return a distinct node.
00957   ///
00958   /// Return a distinct node -- i.e., a node that is not uniqued.
00959   static MDTuple *getDistinct(LLVMContext &Context, ArrayRef<Metadata *> MDs) {
00960     return getImpl(Context, MDs, Distinct);
00961   }
00962 
00963   /// \brief Return a temporary node.
00964   ///
00965   /// For use in constructing cyclic MDNode structures. A temporary MDNode is
00966   /// not uniqued, may be RAUW'd, and must be manually deleted with
00967   /// deleteTemporary.
00968   static TempMDTuple getTemporary(LLVMContext &Context,
00969                                   ArrayRef<Metadata *> MDs) {
00970     return TempMDTuple(getImpl(Context, MDs, Temporary));
00971   }
00972 
00973   /// \brief Return a (temporary) clone of this.
00974   TempMDTuple clone() const { return cloneImpl(); }
00975 
00976   static bool classof(const Metadata *MD) {
00977     return MD->getMetadataID() == MDTupleKind;
00978   }
00979 };
00980 
00981 MDTuple *MDNode::get(LLVMContext &Context, ArrayRef<Metadata *> MDs) {
00982   return MDTuple::get(Context, MDs);
00983 }
00984 MDTuple *MDNode::getIfExists(LLVMContext &Context, ArrayRef<Metadata *> MDs) {
00985   return MDTuple::getIfExists(Context, MDs);
00986 }
00987 MDTuple *MDNode::getDistinct(LLVMContext &Context, ArrayRef<Metadata *> MDs) {
00988   return MDTuple::getDistinct(Context, MDs);
00989 }
00990 TempMDTuple MDNode::getTemporary(LLVMContext &Context,
00991                                  ArrayRef<Metadata *> MDs) {
00992   return MDTuple::getTemporary(Context, MDs);
00993 }
00994 
00995 void TempMDNodeDeleter::operator()(MDNode *Node) const {
00996   MDNode::deleteTemporary(Node);
00997 }
00998 
00999 //===----------------------------------------------------------------------===//
01000 /// \brief A tuple of MDNodes.
01001 ///
01002 /// Despite its name, a NamedMDNode isn't itself an MDNode. NamedMDNodes belong
01003 /// to modules, have names, and contain lists of MDNodes.
01004 ///
01005 /// TODO: Inherit from Metadata.
01006 class NamedMDNode : public ilist_node<NamedMDNode> {
01007   friend class SymbolTableListTraits<NamedMDNode, Module>;
01008   friend struct ilist_traits<NamedMDNode>;
01009   friend class LLVMContextImpl;
01010   friend class Module;
01011   NamedMDNode(const NamedMDNode &) = delete;
01012 
01013   std::string Name;
01014   Module *Parent;
01015   void *Operands; // SmallVector<TrackingMDRef, 4>
01016 
01017   void setParent(Module *M) { Parent = M; }
01018 
01019   explicit NamedMDNode(const Twine &N);
01020 
01021   template<class T1, class T2>
01022   class op_iterator_impl :
01023       public std::iterator<std::bidirectional_iterator_tag, T2> {
01024     const NamedMDNode *Node;
01025     unsigned Idx;
01026     op_iterator_impl(const NamedMDNode *N, unsigned i) : Node(N), Idx(i) { }
01027 
01028     friend class NamedMDNode;
01029 
01030   public:
01031     op_iterator_impl() : Node(nullptr), Idx(0) { }
01032 
01033     bool operator==(const op_iterator_impl &o) const { return Idx == o.Idx; }
01034     bool operator!=(const op_iterator_impl &o) const { return Idx != o.Idx; }
01035     op_iterator_impl &operator++() {
01036       ++Idx;
01037       return *this;
01038     }
01039     op_iterator_impl operator++(int) {
01040       op_iterator_impl tmp(*this);
01041       operator++();
01042       return tmp;
01043     }
01044     op_iterator_impl &operator--() {
01045       --Idx;
01046       return *this;
01047     }
01048     op_iterator_impl operator--(int) {
01049       op_iterator_impl tmp(*this);
01050       operator--();
01051       return tmp;
01052     }
01053 
01054     T1 operator*() const { return Node->getOperand(Idx); }
01055   };
01056 
01057 public:
01058   /// \brief Drop all references and remove the node from parent module.
01059   void eraseFromParent();
01060 
01061   /// \brief Remove all uses and clear node vector.
01062   void dropAllReferences();
01063 
01064   ~NamedMDNode();
01065 
01066   /// \brief Get the module that holds this named metadata collection.
01067   inline Module *getParent() { return Parent; }
01068   inline const Module *getParent() const { return Parent; }
01069 
01070   MDNode *getOperand(unsigned i) const;
01071   unsigned getNumOperands() const;
01072   void addOperand(MDNode *M);
01073   void setOperand(unsigned I, MDNode *New);
01074   StringRef getName() const;
01075   void print(raw_ostream &ROS) const;
01076   void dump() const;
01077 
01078   // ---------------------------------------------------------------------------
01079   // Operand Iterator interface...
01080   //
01081   typedef op_iterator_impl<MDNode *, MDNode> op_iterator;
01082   op_iterator op_begin() { return op_iterator(this, 0); }
01083   op_iterator op_end()   { return op_iterator(this, getNumOperands()); }
01084 
01085   typedef op_iterator_impl<const MDNode *, MDNode> const_op_iterator;
01086   const_op_iterator op_begin() const { return const_op_iterator(this, 0); }
01087   const_op_iterator op_end()   const { return const_op_iterator(this, getNumOperands()); }
01088 
01089   inline iterator_range<op_iterator>  operands() {
01090     return iterator_range<op_iterator>(op_begin(), op_end());
01091   }
01092   inline iterator_range<const_op_iterator> operands() const {
01093     return iterator_range<const_op_iterator>(op_begin(), op_end());
01094   }
01095 };
01096 
01097 } // end llvm namespace
01098 
01099 #endif