include/llvm/IR/Metadata.h

   1 //===- llvm/IR/Metadata.h - Metadata definitions ----------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 /// @file
  11 /// This file contains the declarations for metadata subclasses.
  12 /// They represent the different flavors of metadata that live in LLVM.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #ifndef LLVM_IR_METADATA_H
  17 #define LLVM_IR_METADATA_H
  18
  19 #include "llvm/ADT/ArrayRef.h"
  20 #include "llvm/ADT/DenseMap.h"
  21 #include "llvm/ADT/ilist_node.h"
  22 #include "llvm/ADT/iterator_range.h"
  23 #include "llvm/IR/Constant.h"
  24 #include "llvm/IR/MetadataTracking.h"
  25 #include "llvm/IR/Value.h"
  26 #include "llvm/Support/ErrorHandling.h"
  27 #include <type_traits>
  28
  29 namespace llvm {
  30 class LLVMContext;
  31 class Module;
  32 template<typename ValueSubClass, typename ItemParentClass>
  33   class SymbolTableListTraits;
  34
  35
  36 enum LLVMConstants : uint32_t {
  37   DEBUG_METADATA_VERSION = 2  // Current debug info version number.
  38 };
  39
  40 /// \brief Root of the metadata hierarchy.
  41 ///
  42 /// This is a root class for typeless data in the IR.
  43 class Metadata {
  44   friend class ReplaceableMetadataImpl;
  45
  46   /// \brief RTTI.
  47   const unsigned char SubclassID;
  48
  49 protected:
  50   /// \brief Active type of storage.
  51   enum StorageType { Uniqued, Distinct, Temporary };
  52
  53   /// \brief Storage flag for non-uniqued, otherwise unowned, metadata.
  54   unsigned Storage : 2;
  55   // TODO: expose remaining bits to subclasses.
  56
  57   unsigned short SubclassData16;
  58   unsigned SubclassData32;
  59
  60 public:
  61   enum MetadataKind {
  62     MDTupleKind,
  63     MDLocationKind,
  64     GenericDebugNodeKind,
  65     MDSubrangeKind,
  66     MDEnumeratorKind,
  67     MDBasicTypeKind,
  68     MDDerivedTypeKind,
  69     MDCompositeTypeKind,
  70     MDSubroutineTypeKind,
  71     MDFileKind,
  72     MDCompileUnitKind,
  73     MDSubprogramKind,
  74     MDLexicalBlockKind,
  75     MDLexicalBlockFileKind,
  76     MDNamespaceKind,
  77     MDTemplateTypeParameterKind,
  78     MDTemplateValueParameterKind,
  79     MDGlobalVariableKind,
  80     MDLocalVariableKind,
  81     MDExpressionKind,
  82     MDObjCPropertyKind,
  83     MDImportedEntityKind,
  84     ConstantAsMetadataKind,
  85     LocalAsMetadataKind,
  86     MDStringKind
  87   };
  88
  89 protected:
  90   Metadata(unsigned ID, StorageType Storage)
  91       : SubclassID(ID), Storage(Storage), SubclassData16(0), SubclassData32(0) {
  92   }
  93   ~Metadata() {}
  94
  95   /// \brief Default handling of a changed operand, which asserts.
  96   ///
  97   /// If subclasses pass themselves in as owners to a tracking node reference,
  98   /// they must provide an implementation of this method.
  99   void handleChangedOperand(void *, Metadata *) {
 100     llvm_unreachable("Unimplemented in Metadata subclass");
 101   }
 102
 103 public:
 104   unsigned getMetadataID() const { return SubclassID; }
 105
 106   /// \brief User-friendly dump.
 107   void dump() const;
 108   void print(raw_ostream &OS) const;
 109   void printAsOperand(raw_ostream &OS, bool PrintType = true,
 110                       const Module *M = nullptr) const;
 111 };
 112
 113 #define HANDLE_METADATA(CLASS) class CLASS;
 114 #include "llvm/IR/Metadata.def"
 115
 116 inline raw_ostream &operator<<(raw_ostream &OS, const Metadata &MD) {
 117   MD.print(OS);
 118   return OS;
 119 }
 120
 121 /// \brief Metadata wrapper in the Value hierarchy.
 122 ///
 123 /// A member of the \a Value hierarchy to represent a reference to metadata.
 124 /// This allows, e.g., instrinsics to have metadata as operands.
 125 ///
 126 /// Notably, this is the only thing in either hierarchy that is allowed to
 127 /// reference \a LocalAsMetadata.
 128 class MetadataAsValue : public Value {
 129   friend class ReplaceableMetadataImpl;
 130   friend class LLVMContextImpl;
 131
 132   Metadata *MD;
 133
 134   MetadataAsValue(Type *Ty, Metadata *MD);
 135   ~MetadataAsValue();
 136
 137   /// \brief Drop use of metadata (during teardown).
 138   void dropUse() { MD = nullptr; }
 139
 140 public:
 141   static MetadataAsValue *get(LLVMContext &Context, Metadata *MD);
 142   static MetadataAsValue *getIfExists(LLVMContext &Context, Metadata *MD);
 143   Metadata *getMetadata() const { return MD; }
 144
 145   static bool classof(const Value *V) {
 146     return V->getValueID() == MetadataAsValueVal;
 147   }
 148
 149 private:
 150   void handleChangedMetadata(Metadata *MD);
 151   void track();
 152   void untrack();
 153 };
 154
 155 /// \brief Shared implementation of use-lists for replaceable metadata.
 156 ///
 157 /// Most metadata cannot be RAUW'ed.  This is a shared implementation of
 158 /// use-lists and associated API for the two that support it (\a ValueAsMetadata
 159 /// and \a TempMDNode).
 160 class ReplaceableMetadataImpl {
 161   friend class MetadataTracking;
 162
 163 public:
 164   typedef MetadataTracking::OwnerTy OwnerTy;
 165
 166 private:
 167   LLVMContext &Context;
 168   uint64_t NextIndex;
 169   SmallDenseMap<void *, std::pair<OwnerTy, uint64_t>, 4> UseMap;
 170
 171 public:
 172   ReplaceableMetadataImpl(LLVMContext &Context)
 173       : Context(Context), NextIndex(0) {}
 174   ~ReplaceableMetadataImpl() {
 175     assert(UseMap.empty() && "Cannot destroy in-use replaceable metadata");
 176   }
 177
 178   LLVMContext &getContext() const { return Context; }
 179
 180   /// \brief Replace all uses of this with MD.
 181   ///
 182   /// Replace all uses of this with \c MD, which is allowed to be null.
 183   void replaceAllUsesWith(Metadata *MD);
 184
 185   /// \brief Resolve all uses of this.
 186   ///
 187   /// Resolve all uses of this, turning off RAUW permanently.  If \c
 188   /// ResolveUsers, call \a MDNode::resolve() on any users whose last operand
 189   /// is resolved.
 190   void resolveAllUses(bool ResolveUsers = true);
 191
 192 private:
 193   void addRef(void *Ref, OwnerTy Owner);
 194   void dropRef(void *Ref);
 195   void moveRef(void *Ref, void *New, const Metadata &MD);
 196
 197   static ReplaceableMetadataImpl *get(Metadata &MD);
 198 };
 199
 200 /// \brief Value wrapper in the Metadata hierarchy.
 201 ///
 202 /// This is a custom value handle that allows other metadata to refer to
 203 /// classes in the Value hierarchy.
 204 ///
 205 /// Because of full uniquing support, each value is only wrapped by a single \a
 206 /// ValueAsMetadata object, so the lookup maps are far more efficient than
 207 /// those using ValueHandleBase.
 208 class ValueAsMetadata : public Metadata, ReplaceableMetadataImpl {
 209   friend class ReplaceableMetadataImpl;
 210   friend class LLVMContextImpl;
 211
 212   Value *V;
 213
 214   /// \brief Drop users without RAUW (during teardown).
 215   void dropUsers() {
 216     ReplaceableMetadataImpl::resolveAllUses(/* ResolveUsers */ false);
 217   }
 218
 219 protected:
 220   ValueAsMetadata(unsigned ID, Value *V)
 221       : Metadata(ID, Uniqued), ReplaceableMetadataImpl(V->getContext()), V(V) {
 222     assert(V && "Expected valid value");
 223   }
 224   ~ValueAsMetadata() {}
 225
 226 public:
 227   static ValueAsMetadata *get(Value *V);
 228   static ConstantAsMetadata *getConstant(Value *C) {
 229     return cast<ConstantAsMetadata>(get(C));
 230   }
 231   static LocalAsMetadata *getLocal(Value *Local) {
 232     return cast<LocalAsMetadata>(get(Local));
 233   }
 234
 235   static ValueAsMetadata *getIfExists(Value *V);
 236   static ConstantAsMetadata *getConstantIfExists(Value *C) {
 237     return cast_or_null<ConstantAsMetadata>(getIfExists(C));
 238   }
 239   static LocalAsMetadata *getLocalIfExists(Value *Local) {
 240     return cast_or_null<LocalAsMetadata>(getIfExists(Local));
 241   }
 242
 243   Value *getValue() const { return V; }
 244   Type *getType() const { return V->getType(); }
 245   LLVMContext &getContext() const { return V->getContext(); }
 246
 247   static void handleDeletion(Value *V);
 248   static void handleRAUW(Value *From, Value *To);
 249
 250 protected:
 251   /// \brief Handle collisions after \a Value::replaceAllUsesWith().
 252   ///
 253   /// RAUW isn't supported directly for \a ValueAsMetadata, but if the wrapped
 254   /// \a Value gets RAUW'ed and the target already exists, this is used to
 255   /// merge the two metadata nodes.
 256   void replaceAllUsesWith(Metadata *MD) {
 257     ReplaceableMetadataImpl::replaceAllUsesWith(MD);
 258   }
 259
 260 public:
 261   static bool classof(const Metadata *MD) {
 262     return MD->getMetadataID() == LocalAsMetadataKind ||
 263            MD->getMetadataID() == ConstantAsMetadataKind;
 264   }
 265 };
 266
 267 class ConstantAsMetadata : public ValueAsMetadata {
 268   friend class ValueAsMetadata;
 269
 270   ConstantAsMetadata(Constant *C)
 271       : ValueAsMetadata(ConstantAsMetadataKind, C) {}
 272
 273 public:
 274   static ConstantAsMetadata *get(Constant *C) {
 275     return ValueAsMetadata::getConstant(C);
 276   }
 277   static ConstantAsMetadata *getIfExists(Constant *C) {
 278     return ValueAsMetadata::getConstantIfExists(C);
 279   }
 280
 281   Constant *getValue() const {
 282     return cast<Constant>(ValueAsMetadata::getValue());
 283   }
 284
 285   static bool classof(const Metadata *MD) {
 286     return MD->getMetadataID() == ConstantAsMetadataKind;
 287   }
 288 };
 289
 290 class LocalAsMetadata : public ValueAsMetadata {
 291   friend class ValueAsMetadata;
 292
 293   LocalAsMetadata(Value *Local)
 294       : ValueAsMetadata(LocalAsMetadataKind, Local) {
 295     assert(!isa<Constant>(Local) && "Expected local value");
 296   }
 297
 298 public:
 299   static LocalAsMetadata *get(Value *Local) {
 300     return ValueAsMetadata::getLocal(Local);
 301   }
 302   static LocalAsMetadata *getIfExists(Value *Local) {
 303     return ValueAsMetadata::getLocalIfExists(Local);
 304   }
 305
 306   static bool classof(const Metadata *MD) {
 307     return MD->getMetadataID() == LocalAsMetadataKind;
 308   }
 309 };
 310
 311 /// \brief Transitional API for extracting constants from Metadata.
 312 ///
 313 /// This namespace contains transitional functions for metadata that points to
 314 /// \a Constants.
 315 ///
 316 /// In prehistory -- when metadata was a subclass of \a Value -- \a MDNode
 317 /// operands could refer to any \a Value.  There's was a lot of code like this:
 318 ///
 319 /// \code
 320 ///     MDNode *N = ...;
 321 ///     auto *CI = dyn_cast<ConstantInt>(N->getOperand(2));
 322 /// \endcode
 323 ///
 324 /// Now that \a Value and \a Metadata are in separate hierarchies, maintaining
 325 /// the semantics for \a isa(), \a cast(), \a dyn_cast() (etc.) requires three
 326 /// steps: cast in the \a Metadata hierarchy, extraction of the \a Value, and
 327 /// cast in the \a Value hierarchy.  Besides creating boiler-plate, this
 328 /// requires subtle control flow changes.
 329 ///
 330 /// The end-goal is to create a new type of metadata, called (e.g.) \a MDInt,
 331 /// so that metadata can refer to numbers without traversing a bridge to the \a
 332 /// Value hierarchy.  In this final state, the code above would look like this:
 333 ///
 334 /// \code
 335 ///     MDNode *N = ...;
 336 ///     auto *MI = dyn_cast<MDInt>(N->getOperand(2));
 337 /// \endcode
 338 ///
 339 /// The API in this namespace supports the transition.  \a MDInt doesn't exist
 340 /// yet, and even once it does, changing each metadata schema to use it is its
 341 /// own mini-project.  In the meantime this API prevents us from introducing
 342 /// complex and bug-prone control flow that will disappear in the end.  In
 343 /// particular, the above code looks like this:
 344 ///
 345 /// \code
 346 ///     MDNode *N = ...;
 347 ///     auto *CI = mdconst::dyn_extract<ConstantInt>(N->getOperand(2));
 348 /// \endcode
 349 ///
 350 /// The full set of provided functions includes:
 351 ///
 352 ///   mdconst::hasa                <=> isa
 353 ///   mdconst::extract             <=> cast
 354 ///   mdconst::extract_or_null     <=> cast_or_null
 355 ///   mdconst::dyn_extract         <=> dyn_cast
 356 ///   mdconst::dyn_extract_or_null <=> dyn_cast_or_null
 357 ///
 358 /// The target of the cast must be a subclass of \a Constant.
 359 namespace mdconst {
 360
 361 namespace detail {
 362 template <class T> T &make();
 363 template <class T, class Result> struct HasDereference {
 364   typedef char Yes[1];
 365   typedef char No[2];
 366   template <size_t N> struct SFINAE {};
 367
 368   template <class U, class V>
 369   static Yes &hasDereference(SFINAE<sizeof(static_cast<V>(*make<U>()))> * = 0);
 370   template <class U, class V> static No &hasDereference(...);
 371
 372   static const bool value =
 373       sizeof(hasDereference<T, Result>(nullptr)) == sizeof(Yes);
 374 };
 375 template <class V, class M> struct IsValidPointer {
 376   static const bool value = std::is_base_of<Constant, V>::value &&
 377                             HasDereference<M, const Metadata &>::value;
 378 };
 379 template <class V, class M> struct IsValidReference {
 380   static const bool value = std::is_base_of<Constant, V>::value &&
 381                             std::is_convertible<M, const Metadata &>::value;
 382 };
 383 } // end namespace detail
 384
 385 /// \brief Check whether Metadata has a Value.
 386 ///
 387 /// As an analogue to \a isa(), check whether \c MD has an \a Value inside of
 388 /// type \c X.
 389 template <class X, class Y>
 390 inline typename std::enable_if<detail::IsValidPointer<X, Y>::value, bool>::type
 391 hasa(Y &&MD) {
 392   assert(MD && "Null pointer sent into hasa");
 393   if (auto *V = dyn_cast<ConstantAsMetadata>(MD))
 394     return isa<X>(V->getValue());
 395   return false;
 396 }
 397 template <class X, class Y>
 398 inline
 399     typename std::enable_if<detail::IsValidReference<X, Y &>::value, bool>::type
 400     hasa(Y &MD) {
 401   return hasa(&MD);
 402 }
 403
 404 /// \brief Extract a Value from Metadata.
 405 ///
 406 /// As an analogue to \a cast(), extract the \a Value subclass \c X from \c MD.
 407 template <class X, class Y>
 408 inline typename std::enable_if<detail::IsValidPointer<X, Y>::value, X *>::type
 409 extract(Y &&MD) {
 410   return cast<X>(cast<ConstantAsMetadata>(MD)->getValue());
 411 }
 412 template <class X, class Y>
 413 inline
 414     typename std::enable_if<detail::IsValidReference<X, Y &>::value, X *>::type
 415     extract(Y &MD) {
 416   return extract(&MD);
 417 }
 418
 419 /// \brief Extract a Value from Metadata, allowing null.
 420 ///
 421 /// As an analogue to \a cast_or_null(), extract the \a Value subclass \c X
 422 /// from \c MD, allowing \c MD to be null.
 423 template <class X, class Y>
 424 inline typename std::enable_if<detail::IsValidPointer<X, Y>::value, X *>::type
 425 extract_or_null(Y &&MD) {
 426   if (auto *V = cast_or_null<ConstantAsMetadata>(MD))
 427     return cast<X>(V->getValue());
 428   return nullptr;
 429 }
 430
 431 /// \brief Extract a Value from Metadata, if any.
 432 ///
 433 /// As an analogue to \a dyn_cast_or_null(), extract the \a Value subclass \c X
 434 /// from \c MD, return null if \c MD doesn't contain a \a Value or if the \a
 435 /// Value it does contain is of the wrong subclass.
 436 template <class X, class Y>
 437 inline typename std::enable_if<detail::IsValidPointer<X, Y>::value, X *>::type
 438 dyn_extract(Y &&MD) {
 439   if (auto *V = dyn_cast<ConstantAsMetadata>(MD))
 440     return dyn_cast<X>(V->getValue());
 441   return nullptr;
 442 }
 443
 444 /// \brief Extract a Value from Metadata, if any, allowing null.
 445 ///
 446 /// As an analogue to \a dyn_cast_or_null(), extract the \a Value subclass \c X
 447 /// from \c MD, return null if \c MD doesn't contain a \a Value or if the \a
 448 /// Value it does contain is of the wrong subclass, allowing \c MD to be null.
 449 template <class X, class Y>
 450 inline typename std::enable_if<detail::IsValidPointer<X, Y>::value, X *>::type
 451 dyn_extract_or_null(Y &&MD) {
 452   if (auto *V = dyn_cast_or_null<ConstantAsMetadata>(MD))
 453     return dyn_cast<X>(V->getValue());
 454   return nullptr;
 455 }
 456
 457 } // end namespace mdconst
 458
 459 //===----------------------------------------------------------------------===//
 460 /// \brief A single uniqued string.
 461 ///
 462 /// These are used to efficiently contain a byte sequence for metadata.
 463 /// MDString is always unnamed.
 464 class MDString : public Metadata {
 465   friend class StringMapEntry<MDString>;
 466
 467   MDString(const MDString &) LLVM_DELETED_FUNCTION;
 468   MDString &operator=(MDString &&) LLVM_DELETED_FUNCTION;
 469   MDString &operator=(const MDString &) LLVM_DELETED_FUNCTION;
 470
 471   StringMapEntry<MDString> *Entry;
 472   MDString() : Metadata(MDStringKind, Uniqued), Entry(nullptr) {}
 473   MDString(MDString &&) : Metadata(MDStringKind, Uniqued) {}
 474
 475 public:
 476   static MDString *get(LLVMContext &Context, StringRef Str);
 477   static MDString *get(LLVMContext &Context, const char *Str) {
 478     return get(Context, Str ? StringRef(Str) : StringRef());
 479   }
 480
 481   StringRef getString() const;
 482
 483   unsigned getLength() const { return (unsigned)getString().size(); }
 484
 485   typedef StringRef::iterator iterator;
 486
 487   /// \brief Pointer to the first byte of the string.
 488   iterator begin() const { return getString().begin(); }
 489
 490   /// \brief Pointer to one byte past the end of the string.
 491   iterator end() const { return getString().end(); }
 492
 493   const unsigned char *bytes_begin() const { return getString().bytes_begin(); }
 494   const unsigned char *bytes_end() const { return getString().bytes_end(); }
 495
 496   /// \brief Methods for support type inquiry through isa, cast, and dyn_cast.
 497   static bool classof(const Metadata *MD) {
 498     return MD->getMetadataID() == MDStringKind;
 499   }
 500 };
 501
 502 /// \brief A collection of metadata nodes that might be associated with a
 503 /// memory access used by the alias-analysis infrastructure.
 504 struct AAMDNodes {
 505   explicit AAMDNodes(MDNode *T = nullptr, MDNode *S = nullptr,
 506                      MDNode *N = nullptr)
 507       : TBAA(T), Scope(S), NoAlias(N) {}
 508
 509   bool operator==(const AAMDNodes &A) const {
 510     return TBAA == A.TBAA && Scope == A.Scope && NoAlias == A.NoAlias;
 511   }
 512
 513   bool operator!=(const AAMDNodes &A) const { return !(*this == A); }
 514
 515   explicit operator bool() const { return TBAA || Scope || NoAlias; }
 516
 517   /// \brief The tag for type-based alias analysis.
 518   MDNode *TBAA;
 519
 520   /// \brief The tag for alias scope specification (used with noalias).
 521   MDNode *Scope;
 522
 523   /// \brief The tag specifying the noalias scope.
 524   MDNode *NoAlias;
 525 };
 526
 527 // Specialize DenseMapInfo for AAMDNodes.
 528 template<>
 529 struct DenseMapInfo<AAMDNodes> {
 530   static inline AAMDNodes getEmptyKey() {
 531     return AAMDNodes(DenseMapInfo<MDNode *>::getEmptyKey(), 0, 0);
 532   }
 533   static inline AAMDNodes getTombstoneKey() {
 534     return AAMDNodes(DenseMapInfo<MDNode *>::getTombstoneKey(), 0, 0);
 535   }
 536   static unsigned getHashValue(const AAMDNodes &Val) {
 537     return DenseMapInfo<MDNode *>::getHashValue(Val.TBAA) ^
 538            DenseMapInfo<MDNode *>::getHashValue(Val.Scope) ^
 539            DenseMapInfo<MDNode *>::getHashValue(Val.NoAlias);
 540   }
 541   static bool isEqual(const AAMDNodes &LHS, const AAMDNodes &RHS) {
 542     return LHS == RHS;
 543   }
 544 };
 545
 546 /// \brief Tracking metadata reference owned by Metadata.
 547 ///
 548 /// Similar to \a TrackingMDRef, but it's expected to be owned by an instance
 549 /// of \a Metadata, which has the option of registering itself for callbacks to
 550 /// re-unique itself.
 551 ///
 552 /// In particular, this is used by \a MDNode.
 553 class MDOperand {
 554   MDOperand(MDOperand &&) LLVM_DELETED_FUNCTION;
 555   MDOperand(const MDOperand &) LLVM_DELETED_FUNCTION;
 556   MDOperand &operator=(MDOperand &&) LLVM_DELETED_FUNCTION;
 557   MDOperand &operator=(const MDOperand &) LLVM_DELETED_FUNCTION;
 558
 559   Metadata *MD;
 560
 561 public:
 562   MDOperand() : MD(nullptr) {}
 563   ~MDOperand() { untrack(); }
 564
 565   Metadata *get() const { return MD; }
 566   operator Metadata *() const { return get(); }
 567   Metadata *operator->() const { return get(); }
 568   Metadata &operator*() const { return *get(); }
 569
 570   void reset() {
 571     untrack();
 572     MD = nullptr;
 573   }
 574   void reset(Metadata *MD, Metadata *Owner) {
 575     untrack();
 576     this->MD = MD;
 577     track(Owner);
 578   }
 579
 580 private:
 581   void track(Metadata *Owner) {
 582     if (MD) {
 583       if (Owner)
 584         MetadataTracking::track(this, *MD, *Owner);
 585       else
 586         MetadataTracking::track(MD);
 587     }
 588   }
 589   void untrack() {
 590     assert(static_cast<void *>(this) == &MD && "Expected same address");
 591     if (MD)
 592       MetadataTracking::untrack(MD);
 593   }
 594 };
 595
 596 template <> struct simplify_type<MDOperand> {
 597   typedef Metadata *SimpleType;
 598   static SimpleType getSimplifiedValue(MDOperand &MD) { return MD.get(); }
 599 };
 600
 601 template <> struct simplify_type<const MDOperand> {
 602   typedef Metadata *SimpleType;
 603   static SimpleType getSimplifiedValue(const MDOperand &MD) { return MD.get(); }
 604 };
 605
 606 /// \brief Pointer to the context, with optional RAUW support.
 607 ///
 608 /// Either a raw (non-null) pointer to the \a LLVMContext, or an owned pointer
 609 /// to \a ReplaceableMetadataImpl (which has a reference to \a LLVMContext).
 610 class ContextAndReplaceableUses {
 611   PointerUnion<LLVMContext *, ReplaceableMetadataImpl *> Ptr;
 612
 613   ContextAndReplaceableUses() LLVM_DELETED_FUNCTION;
 614   ContextAndReplaceableUses(ContextAndReplaceableUses &&)
 615       LLVM_DELETED_FUNCTION;
 616   ContextAndReplaceableUses(const ContextAndReplaceableUses &)
 617       LLVM_DELETED_FUNCTION;
 618   ContextAndReplaceableUses &
 619   operator=(ContextAndReplaceableUses &&) LLVM_DELETED_FUNCTION;
 620   ContextAndReplaceableUses &
 621   operator=(const ContextAndReplaceableUses &) LLVM_DELETED_FUNCTION;
 622
 623 public:
 624   ContextAndReplaceableUses(LLVMContext &Context) : Ptr(&Context) {}
 625   ContextAndReplaceableUses(
 626       std::unique_ptr<ReplaceableMetadataImpl> ReplaceableUses)
 627       : Ptr(ReplaceableUses.release()) {
 628     assert(getReplaceableUses() && "Expected non-null replaceable uses");
 629   }
 630   ~ContextAndReplaceableUses() { delete getReplaceableUses(); }
 631
 632   operator LLVMContext &() { return getContext(); }
 633
 634   /// \brief Whether this contains RAUW support.
 635   bool hasReplaceableUses() const {
 636     return Ptr.is<ReplaceableMetadataImpl *>();
 637   }
 638   LLVMContext &getContext() const {
 639     if (hasReplaceableUses())
 640       return getReplaceableUses()->getContext();
 641     return *Ptr.get<LLVMContext *>();
 642   }
 643   ReplaceableMetadataImpl *getReplaceableUses() const {
 644     if (hasReplaceableUses())
 645       return Ptr.get<ReplaceableMetadataImpl *>();
 646     return nullptr;
 647   }
 648
 649   /// \brief Assign RAUW support to this.
 650   ///
 651   /// Make this replaceable, taking ownership of \c ReplaceableUses (which must
 652   /// not be null).
 653   void
 654   makeReplaceable(std::unique_ptr<ReplaceableMetadataImpl> ReplaceableUses) {
 655     assert(ReplaceableUses && "Expected non-null replaceable uses");
 656     assert(&ReplaceableUses->getContext() == &getContext() &&
 657            "Expected same context");
 658     delete getReplaceableUses();
 659     Ptr = ReplaceableUses.release();
 660   }
 661
 662   /// \brief Drop RAUW support.
 663   ///
 664   /// Cede ownership of RAUW support, returning it.
 665   std::unique_ptr<ReplaceableMetadataImpl> takeReplaceableUses() {
 666     assert(hasReplaceableUses() && "Expected to own replaceable uses");
 667     std::unique_ptr<ReplaceableMetadataImpl> ReplaceableUses(
 668         getReplaceableUses());
 669     Ptr = &ReplaceableUses->getContext();
 670     return ReplaceableUses;
 671   }
 672 };
 673
 674 struct TempMDNodeDeleter {
 675   inline void operator()(MDNode *Node) const;
 676 };
 677
 678 #define HANDLE_MDNODE_LEAF(CLASS)                                              \
 679   typedef std::unique_ptr<CLASS, TempMDNodeDeleter> Temp##CLASS;
 680 #define HANDLE_MDNODE_BRANCH(CLASS) HANDLE_MDNODE_LEAF(CLASS)
 681 #include "llvm/IR/Metadata.def"
 682
 683 /// \brief Metadata node.
 684 ///
 685 /// Metadata nodes can be uniqued, like constants, or distinct.  Temporary
 686 /// metadata nodes (with full support for RAUW) can be used to delay uniquing
 687 /// until forward references are known.  The basic metadata node is an \a
 688 /// MDTuple.
 689 ///
 690 /// There is limited support for RAUW at construction time.  At construction
 691 /// time, if any operand is a temporary node (or an unresolved uniqued node,
 692 /// which indicates a transitive temporary operand), the node itself will be
 693 /// unresolved.  As soon as all operands become resolved, it will drop RAUW
 694 /// support permanently.
 695 ///
 696 /// If an unresolved node is part of a cycle, \a resolveCycles() needs
 697 /// to be called on some member of the cycle once all temporary nodes have been
 698 /// replaced.
 699 class MDNode : public Metadata {
 700   friend class ReplaceableMetadataImpl;
 701   friend class LLVMContextImpl;
 702
 703   MDNode(const MDNode &) LLVM_DELETED_FUNCTION;
 704   void operator=(const MDNode &) LLVM_DELETED_FUNCTION;
 705   void *operator new(size_t) LLVM_DELETED_FUNCTION;
 706
 707   unsigned NumOperands;
 708   unsigned NumUnresolved;
 709
 710 protected:
 711   ContextAndReplaceableUses Context;
 712
 713   void *operator new(size_t Size, unsigned NumOps);
 714   void operator delete(void *Mem);
 715
 716   /// \brief Required by std, but never called.
 717   void operator delete(void *, unsigned) {
 718     llvm_unreachable("Constructor throws?");
 719   }
 720
 721   /// \brief Required by std, but never called.
 722   void operator delete(void *, unsigned, bool) {
 723     llvm_unreachable("Constructor throws?");
 724   }
 725
 726   MDNode(LLVMContext &Context, unsigned ID, StorageType Storage,
 727          ArrayRef<Metadata *> Ops1, ArrayRef<Metadata *> Ops2 = None);
 728   ~MDNode() {}
 729
 730   void dropAllReferences();
 731
 732   MDOperand *mutable_begin() { return mutable_end() - NumOperands; }
 733   MDOperand *mutable_end() { return reinterpret_cast<MDOperand *>(this); }
 734
 735 public:
 736   static inline MDTuple *get(LLVMContext &Context, ArrayRef<Metadata *> MDs);
 737   static inline MDTuple *getIfExists(LLVMContext &Context,
 738                                      ArrayRef<Metadata *> MDs);
 739   static inline MDTuple *getDistinct(LLVMContext &Context,
 740                                      ArrayRef<Metadata *> MDs);
 741   static inline TempMDTuple getTemporary(LLVMContext &Context,
 742                                          ArrayRef<Metadata *> MDs);
 743
 744   /// \brief Create a (temporary) clone of this.
 745   TempMDNode clone() const;
 746
 747   /// \brief Deallocate a node created by getTemporary.
 748   ///
 749   /// Calls \c replaceAllUsesWith(nullptr) before deleting, so any remaining
 750   /// references will be reset.
 751   static void deleteTemporary(MDNode *N);
 752
 753   LLVMContext &getContext() const { return Context.getContext(); }
 754
 755   /// \brief Replace a specific operand.
 756   void replaceOperandWith(unsigned I, Metadata *New);
 757
 758   /// \brief Check if node is fully resolved.
 759   ///
 760   /// If \a isTemporary(), this always returns \c false; if \a isDistinct(),
 761   /// this always returns \c true.
 762   ///
 763   /// If \a isUniqued(), returns \c true if this has already dropped RAUW
 764   /// support (because all operands are resolved).
 765   ///
 766   /// As forward declarations are resolved, their containers should get
 767   /// resolved automatically.  However, if this (or one of its operands) is
 768   /// involved in a cycle, \a resolveCycles() needs to be called explicitly.
 769   bool isResolved() const { return !Context.hasReplaceableUses(); }
 770
 771   bool isUniqued() const { return Storage == Uniqued; }
 772   bool isDistinct() const { return Storage == Distinct; }
 773   bool isTemporary() const { return Storage == Temporary; }
 774
 775   /// \brief RAUW a temporary.
 776   ///
 777   /// \pre \a isTemporary() must be \c true.
 778   void replaceAllUsesWith(Metadata *MD) {
 779     assert(isTemporary() && "Expected temporary node");
 780     assert(!isResolved() && "Expected RAUW support");
 781     Context.getReplaceableUses()->replaceAllUsesWith(MD);
 782   }
 783
 784   /// \brief Resolve cycles.
 785   ///
 786   /// Once all forward declarations have been resolved, force cycles to be
 787   /// resolved.
 788   ///
 789   /// \pre No operands (or operands' operands, etc.) have \a isTemporary().
 790   void resolveCycles();
 791
 792   /// \brief Replace a temporary node with a permanent one.
 793   ///
 794   /// Try to create a uniqued version of \c N -- in place, if possible -- and
 795   /// return it.  If \c N cannot be uniqued, return a distinct node instead.
 796   template <class T>
 797   static typename std::enable_if<std::is_base_of<MDNode, T>::value, T *>::type
 798   replaceWithPermanent(std::unique_ptr<T, TempMDNodeDeleter> N) {
 799     return cast<T>(N.release()->replaceWithPermanentImpl());
 800   }
 801
 802   /// \brief Replace a temporary node with a uniqued one.
 803   ///
 804   /// Create a uniqued version of \c N -- in place, if possible -- and return
 805   /// it.  Takes ownership of the temporary node.
 806   ///
 807   /// \pre N does not self-reference.
 808   template <class T>
 809   static typename std::enable_if<std::is_base_of<MDNode, T>::value, T *>::type
 810   replaceWithUniqued(std::unique_ptr<T, TempMDNodeDeleter> N) {
 811     return cast<T>(N.release()->replaceWithUniquedImpl());
 812   }
 813
 814   /// \brief Replace a temporary node with a distinct one.
 815   ///
 816   /// Create a distinct version of \c N -- in place, if possible -- and return
 817   /// it.  Takes ownership of the temporary node.
 818   template <class T>
 819   static typename std::enable_if<std::is_base_of<MDNode, T>::value, T *>::type
 820   replaceWithDistinct(std::unique_ptr<T, TempMDNodeDeleter> N) {
 821     return cast<T>(N.release()->replaceWithDistinctImpl());
 822   }
 823
 824 private:
 825   MDNode *replaceWithPermanentImpl();
 826   MDNode *replaceWithUniquedImpl();
 827   MDNode *replaceWithDistinctImpl();
 828
 829 protected:
 830   /// \brief Set an operand.
 831   ///
 832   /// Sets the operand directly, without worrying about uniquing.
 833   void setOperand(unsigned I, Metadata *New);
 834
 835   void storeDistinctInContext();
 836   template <class T, class StoreT>
 837   static T *storeImpl(T *N, StorageType Storage, StoreT &Store);
 838
 839 private:
 840   void handleChangedOperand(void *Ref, Metadata *New);
 841
 842   void resolve();
 843   void resolveAfterOperandChange(Metadata *Old, Metadata *New);
 844   void decrementUnresolvedOperandCount();
 845   unsigned countUnresolvedOperands();
 846
 847   /// \brief Mutate this to be "uniqued".
 848   ///
 849   /// Mutate this so that \a isUniqued().
 850   /// \pre \a isTemporary().
 851   /// \pre already added to uniquing set.
 852   void makeUniqued();
 853
 854   /// \brief Mutate this to be "distinct".
 855   ///
 856   /// Mutate this so that \a isDistinct().
 857   /// \pre \a isTemporary().
 858   void makeDistinct();
 859
 860   void deleteAsSubclass();
 861   MDNode *uniquify();
 862   void eraseFromStore();
 863
 864   template <class NodeTy> struct HasCachedHash;
 865   template <class NodeTy>
 866   static void dispatchRecalculateHash(NodeTy *N, std::true_type) {
 867     N->recalculateHash();
 868   }
 869   template <class NodeTy>
 870   static void dispatchRecalculateHash(NodeTy *N, std::false_type) {}
 871   template <class NodeTy>
 872   static void dispatchResetHash(NodeTy *N, std::true_type) {
 873     N->setHash(0);
 874   }
 875   template <class NodeTy>
 876   static void dispatchResetHash(NodeTy *N, std::false_type) {}
 877
 878 public:
 879   typedef const MDOperand *op_iterator;
 880   typedef iterator_range<op_iterator> op_range;
 881
 882   op_iterator op_begin() const {
 883     return const_cast<MDNode *>(this)->mutable_begin();
 884   }
 885   op_iterator op_end() const {
 886     return const_cast<MDNode *>(this)->mutable_end();
 887   }
 888   op_range operands() const { return op_range(op_begin(), op_end()); }
 889
 890   const MDOperand &getOperand(unsigned I) const {
 891     assert(I < NumOperands && "Out of range");
 892     return op_begin()[I];
 893   }
 894
 895   /// \brief Return number of MDNode operands.
 896   unsigned getNumOperands() const { return NumOperands; }
 897
 898   /// \brief Methods for support type inquiry through isa, cast, and dyn_cast:
 899   static bool classof(const Metadata *MD) {
 900     switch (MD->getMetadataID()) {
 901     default:
 902       return false;
 903 #define HANDLE_MDNODE_LEAF(CLASS)                                              \
 904   case CLASS##Kind:                                                            \
 905     return true;
 906 #include "llvm/IR/Metadata.def"
 907     }
 908   }
 909
 910   /// \brief Check whether MDNode is a vtable access.
 911   bool isTBAAVtableAccess() const;
 912
 913   /// \brief Methods for metadata merging.
 914   static MDNode *concatenate(MDNode *A, MDNode *B);
 915   static MDNode *intersect(MDNode *A, MDNode *B);
 916   static MDNode *getMostGenericTBAA(MDNode *A, MDNode *B);
 917   static MDNode *getMostGenericFPMath(MDNode *A, MDNode *B);
 918   static MDNode *getMostGenericRange(MDNode *A, MDNode *B);
 919   static MDNode *getMostGenericAliasScope(MDNode *A, MDNode *B);
 920 };
 921
 922 /// \brief Tuple of metadata.
 923 ///
 924 /// This is the simple \a MDNode arbitrary tuple.  Nodes are uniqued by
 925 /// default based on their operands.
 926 class MDTuple : public MDNode {
 927   friend class LLVMContextImpl;
 928   friend class MDNode;
 929
 930   MDTuple(LLVMContext &C, StorageType Storage, unsigned Hash,
 931           ArrayRef<Metadata *> Vals)
 932       : MDNode(C, MDTupleKind, Storage, Vals) {
 933     setHash(Hash);
 934   }
 935   ~MDTuple() { dropAllReferences(); }
 936
 937   void setHash(unsigned Hash) { SubclassData32 = Hash; }
 938   void recalculateHash();
 939
 940   static MDTuple *getImpl(LLVMContext &Context, ArrayRef<Metadata *> MDs,
 941                           StorageType Storage, bool ShouldCreate = true);
 942
 943   TempMDTuple cloneImpl() const {
 944     return getTemporary(getContext(),
 945                         SmallVector<Metadata *, 4>(op_begin(), op_end()));
 946   }
 947
 948 public:
 949   /// \brief Get the hash, if any.
 950   unsigned getHash() const { return SubclassData32; }
 951
 952   static MDTuple *get(LLVMContext &Context, ArrayRef<Metadata *> MDs) {
 953     return getImpl(Context, MDs, Uniqued);
 954   }
 955   static MDTuple *getIfExists(LLVMContext &Context, ArrayRef<Metadata *> MDs) {
 956     return getImpl(Context, MDs, Uniqued, /* ShouldCreate */ false);
 957   }
 958
 959   /// \brief Return a distinct node.
 960   ///
 961   /// Return a distinct node -- i.e., a node that is not uniqued.
 962   static MDTuple *getDistinct(LLVMContext &Context, ArrayRef<Metadata *> MDs) {
 963     return getImpl(Context, MDs, Distinct);
 964   }
 965
 966   /// \brief Return a temporary node.
 967   ///
 968   /// For use in constructing cyclic MDNode structures. A temporary MDNode is
 969   /// not uniqued, may be RAUW'd, and must be manually deleted with
 970   /// deleteTemporary.
 971   static TempMDTuple getTemporary(LLVMContext &Context,
 972                                   ArrayRef<Metadata *> MDs) {
 973     return TempMDTuple(getImpl(Context, MDs, Temporary));
 974   }
 975
 976   /// \brief Return a (temporary) clone of this.
 977   TempMDTuple clone() const { return cloneImpl(); }
 978
 979   static bool classof(const Metadata *MD) {
 980     return MD->getMetadataID() == MDTupleKind;
 981   }
 982 };
 983
 984 MDTuple *MDNode::get(LLVMContext &Context, ArrayRef<Metadata *> MDs) {
 985   return MDTuple::get(Context, MDs);
 986 }
 987 MDTuple *MDNode::getIfExists(LLVMContext &Context, ArrayRef<Metadata *> MDs) {
 988   return MDTuple::getIfExists(Context, MDs);
 989 }
 990 MDTuple *MDNode::getDistinct(LLVMContext &Context, ArrayRef<Metadata *> MDs) {
 991   return MDTuple::getDistinct(Context, MDs);
 992 }
 993 TempMDTuple MDNode::getTemporary(LLVMContext &Context,
 994                                  ArrayRef<Metadata *> MDs) {
 995   return MDTuple::getTemporary(Context, MDs);
 996 }
 997
 998 void TempMDNodeDeleter::operator()(MDNode *Node) const {
 999   MDNode::deleteTemporary(Node);
1000 }
1001
1002 //===----------------------------------------------------------------------===//
1003 /// \brief A tuple of MDNodes.
1004 ///
1005 /// Despite its name, a NamedMDNode isn't itself an MDNode. NamedMDNodes belong
1006 /// to modules, have names, and contain lists of MDNodes.
1007 ///
1008 /// TODO: Inherit from Metadata.
1009 class NamedMDNode : public ilist_node<NamedMDNode> {
1010   friend class SymbolTableListTraits<NamedMDNode, Module>;
1011   friend struct ilist_traits<NamedMDNode>;
1012   friend class LLVMContextImpl;
1013   friend class Module;
1014   NamedMDNode(const NamedMDNode &) LLVM_DELETED_FUNCTION;
1015
1016   std::string Name;
1017   Module *Parent;
1018   void *Operands; // SmallVector<TrackingMDRef, 4>
1019
1020   void setParent(Module *M) { Parent = M; }
1021
1022   explicit NamedMDNode(const Twine &N);
1023
1024   template<class T1, class T2>
1025   class op_iterator_impl :
1026       public std::iterator<std::bidirectional_iterator_tag, T2> {
1027     const NamedMDNode *Node;
1028     unsigned Idx;
1029     op_iterator_impl(const NamedMDNode *N, unsigned i) : Node(N), Idx(i) { }
1030
1031     friend class NamedMDNode;
1032
1033   public:
1034     op_iterator_impl() : Node(nullptr), Idx(0) { }
1035
1036     bool operator==(const op_iterator_impl &o) const { return Idx == o.Idx; }
1037     bool operator!=(const op_iterator_impl &o) const { return Idx != o.Idx; }
1038     op_iterator_impl &operator++() {
1039       ++Idx;
1040       return *this;
1041     }
1042     op_iterator_impl operator++(int) {
1043       op_iterator_impl tmp(*this);
1044       operator++();
1045       return tmp;
1046     }
1047     op_iterator_impl &operator--() {
1048       --Idx;
1049       return *this;
1050     }
1051     op_iterator_impl operator--(int) {
1052       op_iterator_impl tmp(*this);
1053       operator--();
1054       return tmp;
1055     }
1056
1057     T1 operator*() const { return Node->getOperand(Idx); }
1058   };
1059
1060 public:
1061   /// \brief Drop all references and remove the node from parent module.
1062   void eraseFromParent();
1063
1064   /// \brief Remove all uses and clear node vector.
1065   void dropAllReferences();
1066
1067   ~NamedMDNode();
1068
1069   /// \brief Get the module that holds this named metadata collection.
1070   inline Module *getParent() { return Parent; }
1071   inline const Module *getParent() const { return Parent; }
1072
1073   MDNode *getOperand(unsigned i) const;
1074   unsigned getNumOperands() const;
1075   void addOperand(MDNode *M);
1076   void setOperand(unsigned I, MDNode *New);
1077   StringRef getName() const;
1078   void print(raw_ostream &ROS) const;
1079   void dump() const;
1080
1081   // ---------------------------------------------------------------------------
1082   // Operand Iterator interface...
1083   //
1084   typedef op_iterator_impl<MDNode *, MDNode> op_iterator;
1085   op_iterator op_begin() { return op_iterator(this, 0); }
1086   op_iterator op_end()   { return op_iterator(this, getNumOperands()); }
1087
1088   typedef op_iterator_impl<const MDNode *, MDNode> const_op_iterator;
1089   const_op_iterator op_begin() const { return const_op_iterator(this, 0); }
1090   const_op_iterator op_end()   const { return const_op_iterator(this, getNumOperands()); }
1091
1092   inline iterator_range<op_iterator>  operands() {
1093     return iterator_range<op_iterator>(op_begin(), op_end());
1094   }
1095   inline iterator_range<const_op_iterator> operands() const {
1096     return iterator_range<const_op_iterator>(op_begin(), op_end());
1097   }
1098 };
1099
1100 } // end llvm namespace
1101
1102 #endif