LLVM  mainline
Metadata.cpp
Go to the documentation of this file.
00001 //===- Metadata.cpp - Implement Metadata classes --------------------------===//
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 // This file implements the Metadata classes.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #include "llvm/IR/Metadata.h"
00015 #include "LLVMContextImpl.h"
00016 #include "MetadataImpl.h"
00017 #include "SymbolTableListTraitsImpl.h"
00018 #include "llvm/ADT/DenseMap.h"
00019 #include "llvm/ADT/STLExtras.h"
00020 #include "llvm/ADT/SmallSet.h"
00021 #include "llvm/ADT/SmallString.h"
00022 #include "llvm/ADT/StringMap.h"
00023 #include "llvm/IR/ConstantRange.h"
00024 #include "llvm/IR/DebugInfoMetadata.h"
00025 #include "llvm/IR/Instruction.h"
00026 #include "llvm/IR/LLVMContext.h"
00027 #include "llvm/IR/Module.h"
00028 #include "llvm/IR/ValueHandle.h"
00029 
00030 using namespace llvm;
00031 
00032 MetadataAsValue::MetadataAsValue(Type *Ty, Metadata *MD)
00033     : Value(Ty, MetadataAsValueVal), MD(MD) {
00034   track();
00035 }
00036 
00037 MetadataAsValue::~MetadataAsValue() {
00038   getType()->getContext().pImpl->MetadataAsValues.erase(MD);
00039   untrack();
00040 }
00041 
00042 /// \brief Canonicalize metadata arguments to intrinsics.
00043 ///
00044 /// To support bitcode upgrades (and assembly semantic sugar) for \a
00045 /// MetadataAsValue, we need to canonicalize certain metadata.
00046 ///
00047 ///   - nullptr is replaced by an empty MDNode.
00048 ///   - An MDNode with a single null operand is replaced by an empty MDNode.
00049 ///   - An MDNode whose only operand is a \a ConstantAsMetadata gets skipped.
00050 ///
00051 /// This maintains readability of bitcode from when metadata was a type of
00052 /// value, and these bridges were unnecessary.
00053 static Metadata *canonicalizeMetadataForValue(LLVMContext &Context,
00054                                               Metadata *MD) {
00055   if (!MD)
00056     // !{}
00057     return MDNode::get(Context, None);
00058 
00059   // Return early if this isn't a single-operand MDNode.
00060   auto *N = dyn_cast<MDNode>(MD);
00061   if (!N || N->getNumOperands() != 1)
00062     return MD;
00063 
00064   if (!N->getOperand(0))
00065     // !{}
00066     return MDNode::get(Context, None);
00067 
00068   if (auto *C = dyn_cast<ConstantAsMetadata>(N->getOperand(0)))
00069     // Look through the MDNode.
00070     return C;
00071 
00072   return MD;
00073 }
00074 
00075 MetadataAsValue *MetadataAsValue::get(LLVMContext &Context, Metadata *MD) {
00076   MD = canonicalizeMetadataForValue(Context, MD);
00077   auto *&Entry = Context.pImpl->MetadataAsValues[MD];
00078   if (!Entry)
00079     Entry = new MetadataAsValue(Type::getMetadataTy(Context), MD);
00080   return Entry;
00081 }
00082 
00083 MetadataAsValue *MetadataAsValue::getIfExists(LLVMContext &Context,
00084                                               Metadata *MD) {
00085   MD = canonicalizeMetadataForValue(Context, MD);
00086   auto &Store = Context.pImpl->MetadataAsValues;
00087   return Store.lookup(MD);
00088 }
00089 
00090 void MetadataAsValue::handleChangedMetadata(Metadata *MD) {
00091   LLVMContext &Context = getContext();
00092   MD = canonicalizeMetadataForValue(Context, MD);
00093   auto &Store = Context.pImpl->MetadataAsValues;
00094 
00095   // Stop tracking the old metadata.
00096   Store.erase(this->MD);
00097   untrack();
00098   this->MD = nullptr;
00099 
00100   // Start tracking MD, or RAUW if necessary.
00101   auto *&Entry = Store[MD];
00102   if (Entry) {
00103     replaceAllUsesWith(Entry);
00104     delete this;
00105     return;
00106   }
00107 
00108   this->MD = MD;
00109   track();
00110   Entry = this;
00111 }
00112 
00113 void MetadataAsValue::track() {
00114   if (MD)
00115     MetadataTracking::track(&MD, *MD, *this);
00116 }
00117 
00118 void MetadataAsValue::untrack() {
00119   if (MD)
00120     MetadataTracking::untrack(MD);
00121 }
00122 
00123 void ReplaceableMetadataImpl::addRef(void *Ref, OwnerTy Owner) {
00124   bool WasInserted =
00125       UseMap.insert(std::make_pair(Ref, std::make_pair(Owner, NextIndex)))
00126           .second;
00127   (void)WasInserted;
00128   assert(WasInserted && "Expected to add a reference");
00129 
00130   ++NextIndex;
00131   assert(NextIndex != 0 && "Unexpected overflow");
00132 }
00133 
00134 void ReplaceableMetadataImpl::dropRef(void *Ref) {
00135   bool WasErased = UseMap.erase(Ref);
00136   (void)WasErased;
00137   assert(WasErased && "Expected to drop a reference");
00138 }
00139 
00140 void ReplaceableMetadataImpl::moveRef(void *Ref, void *New,
00141                                       const Metadata &MD) {
00142   auto I = UseMap.find(Ref);
00143   assert(I != UseMap.end() && "Expected to move a reference");
00144   auto OwnerAndIndex = I->second;
00145   UseMap.erase(I);
00146   bool WasInserted = UseMap.insert(std::make_pair(New, OwnerAndIndex)).second;
00147   (void)WasInserted;
00148   assert(WasInserted && "Expected to add a reference");
00149 
00150   // Check that the references are direct if there's no owner.
00151   (void)MD;
00152   assert((OwnerAndIndex.first || *static_cast<Metadata **>(Ref) == &MD) &&
00153          "Reference without owner must be direct");
00154   assert((OwnerAndIndex.first || *static_cast<Metadata **>(New) == &MD) &&
00155          "Reference without owner must be direct");
00156 }
00157 
00158 void ReplaceableMetadataImpl::replaceAllUsesWith(Metadata *MD) {
00159   assert(!(MD && isa<MDNode>(MD) && cast<MDNode>(MD)->isTemporary()) &&
00160          "Expected non-temp node");
00161 
00162   if (UseMap.empty())
00163     return;
00164 
00165   // Copy out uses since UseMap will get touched below.
00166   typedef std::pair<void *, std::pair<OwnerTy, uint64_t>> UseTy;
00167   SmallVector<UseTy, 8> Uses(UseMap.begin(), UseMap.end());
00168   std::sort(Uses.begin(), Uses.end(), [](const UseTy &L, const UseTy &R) {
00169     return L.second.second < R.second.second;
00170   });
00171   for (const auto &Pair : Uses) {
00172     // Check that this Ref hasn't disappeared after RAUW (when updating a
00173     // previous Ref).
00174     if (!UseMap.count(Pair.first))
00175       continue;
00176 
00177     OwnerTy Owner = Pair.second.first;
00178     if (!Owner) {
00179       // Update unowned tracking references directly.
00180       Metadata *&Ref = *static_cast<Metadata **>(Pair.first);
00181       Ref = MD;
00182       if (MD)
00183         MetadataTracking::track(Ref);
00184       UseMap.erase(Pair.first);
00185       continue;
00186     }
00187 
00188     // Check for MetadataAsValue.
00189     if (Owner.is<MetadataAsValue *>()) {
00190       Owner.get<MetadataAsValue *>()->handleChangedMetadata(MD);
00191       continue;
00192     }
00193 
00194     // There's a Metadata owner -- dispatch.
00195     Metadata *OwnerMD = Owner.get<Metadata *>();
00196     switch (OwnerMD->getMetadataID()) {
00197 #define HANDLE_METADATA_LEAF(CLASS)                                            \
00198   case Metadata::CLASS##Kind:                                                  \
00199     cast<CLASS>(OwnerMD)->handleChangedOperand(Pair.first, MD);                \
00200     continue;
00201 #include "llvm/IR/Metadata.def"
00202     default:
00203       llvm_unreachable("Invalid metadata subclass");
00204     }
00205   }
00206   assert(UseMap.empty() && "Expected all uses to be replaced");
00207 }
00208 
00209 void ReplaceableMetadataImpl::resolveAllUses(bool ResolveUsers) {
00210   if (UseMap.empty())
00211     return;
00212 
00213   if (!ResolveUsers) {
00214     UseMap.clear();
00215     return;
00216   }
00217 
00218   // Copy out uses since UseMap could get touched below.
00219   typedef std::pair<void *, std::pair<OwnerTy, uint64_t>> UseTy;
00220   SmallVector<UseTy, 8> Uses(UseMap.begin(), UseMap.end());
00221   std::sort(Uses.begin(), Uses.end(), [](const UseTy &L, const UseTy &R) {
00222     return L.second.second < R.second.second;
00223   });
00224   UseMap.clear();
00225   for (const auto &Pair : Uses) {
00226     auto Owner = Pair.second.first;
00227     if (!Owner)
00228       continue;
00229     if (Owner.is<MetadataAsValue *>())
00230       continue;
00231 
00232     // Resolve MDNodes that point at this.
00233     auto *OwnerMD = dyn_cast<MDNode>(Owner.get<Metadata *>());
00234     if (!OwnerMD)
00235       continue;
00236     if (OwnerMD->isResolved())
00237       continue;
00238     OwnerMD->decrementUnresolvedOperandCount();
00239   }
00240 }
00241 
00242 static Function *getLocalFunction(Value *V) {
00243   assert(V && "Expected value");
00244   if (auto *A = dyn_cast<Argument>(V))
00245     return A->getParent();
00246   if (BasicBlock *BB = cast<Instruction>(V)->getParent())
00247     return BB->getParent();
00248   return nullptr;
00249 }
00250 
00251 ValueAsMetadata *ValueAsMetadata::get(Value *V) {
00252   assert(V && "Unexpected null Value");
00253 
00254   auto &Context = V->getContext();
00255   auto *&Entry = Context.pImpl->ValuesAsMetadata[V];
00256   if (!Entry) {
00257     assert((isa<Constant>(V) || isa<Argument>(V) || isa<Instruction>(V)) &&
00258            "Expected constant or function-local value");
00259     assert(!V->NameAndIsUsedByMD.getInt() &&
00260            "Expected this to be the only metadata use");
00261     V->NameAndIsUsedByMD.setInt(true);
00262     if (auto *C = dyn_cast<Constant>(V))
00263       Entry = new ConstantAsMetadata(C);
00264     else
00265       Entry = new LocalAsMetadata(V);
00266   }
00267 
00268   return Entry;
00269 }
00270 
00271 ValueAsMetadata *ValueAsMetadata::getIfExists(Value *V) {
00272   assert(V && "Unexpected null Value");
00273   return V->getContext().pImpl->ValuesAsMetadata.lookup(V);
00274 }
00275 
00276 void ValueAsMetadata::handleDeletion(Value *V) {
00277   assert(V && "Expected valid value");
00278 
00279   auto &Store = V->getType()->getContext().pImpl->ValuesAsMetadata;
00280   auto I = Store.find(V);
00281   if (I == Store.end())
00282     return;
00283 
00284   // Remove old entry from the map.
00285   ValueAsMetadata *MD = I->second;
00286   assert(MD && "Expected valid metadata");
00287   assert(MD->getValue() == V && "Expected valid mapping");
00288   Store.erase(I);
00289 
00290   // Delete the metadata.
00291   MD->replaceAllUsesWith(nullptr);
00292   delete MD;
00293 }
00294 
00295 void ValueAsMetadata::handleRAUW(Value *From, Value *To) {
00296   assert(From && "Expected valid value");
00297   assert(To && "Expected valid value");
00298   assert(From != To && "Expected changed value");
00299   assert(From->getType() == To->getType() && "Unexpected type change");
00300 
00301   LLVMContext &Context = From->getType()->getContext();
00302   auto &Store = Context.pImpl->ValuesAsMetadata;
00303   auto I = Store.find(From);
00304   if (I == Store.end()) {
00305     assert(!From->NameAndIsUsedByMD.getInt() &&
00306            "Expected From not to be used by metadata");
00307     return;
00308   }
00309 
00310   // Remove old entry from the map.
00311   assert(From->NameAndIsUsedByMD.getInt() &&
00312          "Expected From to be used by metadata");
00313   From->NameAndIsUsedByMD.setInt(false);
00314   ValueAsMetadata *MD = I->second;
00315   assert(MD && "Expected valid metadata");
00316   assert(MD->getValue() == From && "Expected valid mapping");
00317   Store.erase(I);
00318 
00319   if (isa<LocalAsMetadata>(MD)) {
00320     if (auto *C = dyn_cast<Constant>(To)) {
00321       // Local became a constant.
00322       MD->replaceAllUsesWith(ConstantAsMetadata::get(C));
00323       delete MD;
00324       return;
00325     }
00326     if (getLocalFunction(From) && getLocalFunction(To) &&
00327         getLocalFunction(From) != getLocalFunction(To)) {
00328       // Function changed.
00329       MD->replaceAllUsesWith(nullptr);
00330       delete MD;
00331       return;
00332     }
00333   } else if (!isa<Constant>(To)) {
00334     // Changed to function-local value.
00335     MD->replaceAllUsesWith(nullptr);
00336     delete MD;
00337     return;
00338   }
00339 
00340   auto *&Entry = Store[To];
00341   if (Entry) {
00342     // The target already exists.
00343     MD->replaceAllUsesWith(Entry);
00344     delete MD;
00345     return;
00346   }
00347 
00348   // Update MD in place (and update the map entry).
00349   assert(!To->NameAndIsUsedByMD.getInt() &&
00350          "Expected this to be the only metadata use");
00351   To->NameAndIsUsedByMD.setInt(true);
00352   MD->V = To;
00353   Entry = MD;
00354 }
00355 
00356 //===----------------------------------------------------------------------===//
00357 // MDString implementation.
00358 //
00359 
00360 MDString *MDString::get(LLVMContext &Context, StringRef Str) {
00361   auto &Store = Context.pImpl->MDStringCache;
00362   auto I = Store.find(Str);
00363   if (I != Store.end())
00364     return &I->second;
00365 
00366   auto *Entry =
00367       StringMapEntry<MDString>::Create(Str, Store.getAllocator(), MDString());
00368   bool WasInserted = Store.insert(Entry);
00369   (void)WasInserted;
00370   assert(WasInserted && "Expected entry to be inserted");
00371   Entry->second.Entry = Entry;
00372   return &Entry->second;
00373 }
00374 
00375 StringRef MDString::getString() const {
00376   assert(Entry && "Expected to find string map entry");
00377   return Entry->first();
00378 }
00379 
00380 //===----------------------------------------------------------------------===//
00381 // MDNode implementation.
00382 //
00383 
00384 void *MDNode::operator new(size_t Size, unsigned NumOps) {
00385   void *Ptr = ::operator new(Size + NumOps * sizeof(MDOperand));
00386   MDOperand *O = static_cast<MDOperand *>(Ptr);
00387   for (MDOperand *E = O + NumOps; O != E; ++O)
00388     (void)new (O) MDOperand;
00389   return O;
00390 }
00391 
00392 void MDNode::operator delete(void *Mem) {
00393   MDNode *N = static_cast<MDNode *>(Mem);
00394   MDOperand *O = static_cast<MDOperand *>(Mem);
00395   for (MDOperand *E = O - N->NumOperands; O != E; --O)
00396     (O - 1)->~MDOperand();
00397   ::operator delete(O);
00398 }
00399 
00400 MDNode::MDNode(LLVMContext &Context, unsigned ID, StorageType Storage,
00401                ArrayRef<Metadata *> Ops1, ArrayRef<Metadata *> Ops2)
00402     : Metadata(ID, Storage), NumOperands(Ops1.size() + Ops2.size()),
00403       NumUnresolved(0), Context(Context) {
00404   unsigned Op = 0;
00405   for (Metadata *MD : Ops1)
00406     setOperand(Op++, MD);
00407   for (Metadata *MD : Ops2)
00408     setOperand(Op++, MD);
00409 
00410   if (isDistinct())
00411     return;
00412 
00413   if (isUniqued())
00414     // Check whether any operands are unresolved, requiring re-uniquing.  If
00415     // not, don't support RAUW.
00416     if (!countUnresolvedOperands())
00417       return;
00418 
00419   this->Context.makeReplaceable(make_unique<ReplaceableMetadataImpl>(Context));
00420 }
00421 
00422 TempMDNode MDNode::clone() const {
00423   switch (getMetadataID()) {
00424   default:
00425     llvm_unreachable("Invalid MDNode subclass");
00426 #define HANDLE_MDNODE_LEAF(CLASS)                                              \
00427   case CLASS##Kind:                                                            \
00428     return cast<CLASS>(this)->cloneImpl();
00429 #include "llvm/IR/Metadata.def"
00430   }
00431 }
00432 
00433 static bool isOperandUnresolved(Metadata *Op) {
00434   if (auto *N = dyn_cast_or_null<MDNode>(Op))
00435     return !N->isResolved();
00436   return false;
00437 }
00438 
00439 unsigned MDNode::countUnresolvedOperands() {
00440   assert(NumUnresolved == 0 && "Expected unresolved ops to be uncounted");
00441   NumUnresolved = std::count_if(op_begin(), op_end(), isOperandUnresolved);
00442   return NumUnresolved;
00443 }
00444 
00445 void MDNode::makeUniqued() {
00446   assert(isTemporary() && "Expected this to be temporary");
00447   assert(!isResolved() && "Expected this to be unresolved");
00448 
00449   // Enable uniquing callbacks.
00450   for (auto &Op : mutable_operands())
00451     Op.reset(Op.get(), this);
00452 
00453   // Make this 'uniqued'.
00454   Storage = Uniqued;
00455   if (!countUnresolvedOperands())
00456     resolve();
00457 
00458   assert(isUniqued() && "Expected this to be uniqued");
00459 }
00460 
00461 void MDNode::makeDistinct() {
00462   assert(isTemporary() && "Expected this to be temporary");
00463   assert(!isResolved() && "Expected this to be unresolved");
00464 
00465   // Pretend to be uniqued, resolve the node, and then store in distinct table.
00466   Storage = Uniqued;
00467   resolve();
00468   storeDistinctInContext();
00469 
00470   assert(isDistinct() && "Expected this to be distinct");
00471   assert(isResolved() && "Expected this to be resolved");
00472 }
00473 
00474 void MDNode::resolve() {
00475   assert(isUniqued() && "Expected this to be uniqued");
00476   assert(!isResolved() && "Expected this to be unresolved");
00477 
00478   // Move the map, so that this immediately looks resolved.
00479   auto Uses = Context.takeReplaceableUses();
00480   NumUnresolved = 0;
00481   assert(isResolved() && "Expected this to be resolved");
00482 
00483   // Drop RAUW support.
00484   Uses->resolveAllUses();
00485 }
00486 
00487 void MDNode::resolveAfterOperandChange(Metadata *Old, Metadata *New) {
00488   assert(NumUnresolved != 0 && "Expected unresolved operands");
00489 
00490   // Check if an operand was resolved.
00491   if (!isOperandUnresolved(Old)) {
00492     if (isOperandUnresolved(New))
00493       // An operand was un-resolved!
00494       ++NumUnresolved;
00495   } else if (!isOperandUnresolved(New))
00496     decrementUnresolvedOperandCount();
00497 }
00498 
00499 void MDNode::decrementUnresolvedOperandCount() {
00500   if (!--NumUnresolved)
00501     // Last unresolved operand has just been resolved.
00502     resolve();
00503 }
00504 
00505 void MDNode::resolveCycles() {
00506   if (isResolved())
00507     return;
00508 
00509   // Resolve this node immediately.
00510   resolve();
00511 
00512   // Resolve all operands.
00513   for (const auto &Op : operands()) {
00514     auto *N = dyn_cast_or_null<MDNode>(Op);
00515     if (!N)
00516       continue;
00517 
00518     assert(!N->isTemporary() &&
00519            "Expected all forward declarations to be resolved");
00520     if (!N->isResolved())
00521       N->resolveCycles();
00522   }
00523 }
00524 
00525 static bool hasSelfReference(MDNode *N) {
00526   for (Metadata *MD : N->operands())
00527     if (MD == N)
00528       return true;
00529   return false;
00530 }
00531 
00532 MDNode *MDNode::replaceWithPermanentImpl() {
00533   if (hasSelfReference(this))
00534     return replaceWithDistinctImpl();
00535   return replaceWithUniquedImpl();
00536 }
00537 
00538 MDNode *MDNode::replaceWithUniquedImpl() {
00539   // Try to uniquify in place.
00540   MDNode *UniquedNode = uniquify();
00541 
00542   if (UniquedNode == this) {
00543     makeUniqued();
00544     return this;
00545   }
00546 
00547   // Collision, so RAUW instead.
00548   replaceAllUsesWith(UniquedNode);
00549   deleteAsSubclass();
00550   return UniquedNode;
00551 }
00552 
00553 MDNode *MDNode::replaceWithDistinctImpl() {
00554   makeDistinct();
00555   return this;
00556 }
00557 
00558 void MDTuple::recalculateHash() {
00559   setHash(MDTupleInfo::KeyTy::calculateHash(this));
00560 }
00561 
00562 void MDNode::dropAllReferences() {
00563   for (unsigned I = 0, E = NumOperands; I != E; ++I)
00564     setOperand(I, nullptr);
00565   if (!isResolved()) {
00566     Context.getReplaceableUses()->resolveAllUses(/* ResolveUsers */ false);
00567     (void)Context.takeReplaceableUses();
00568   }
00569 }
00570 
00571 void MDNode::handleChangedOperand(void *Ref, Metadata *New) {
00572   unsigned Op = static_cast<MDOperand *>(Ref) - op_begin();
00573   assert(Op < getNumOperands() && "Expected valid operand");
00574 
00575   if (!isUniqued()) {
00576     // This node is not uniqued.  Just set the operand and be done with it.
00577     setOperand(Op, New);
00578     return;
00579   }
00580 
00581   // This node is uniqued.
00582   eraseFromStore();
00583 
00584   Metadata *Old = getOperand(Op);
00585   setOperand(Op, New);
00586 
00587   // Drop uniquing for self-reference cycles.
00588   if (New == this) {
00589     if (!isResolved())
00590       resolve();
00591     storeDistinctInContext();
00592     return;
00593   }
00594 
00595   // Re-unique the node.
00596   auto *Uniqued = uniquify();
00597   if (Uniqued == this) {
00598     if (!isResolved())
00599       resolveAfterOperandChange(Old, New);
00600     return;
00601   }
00602 
00603   // Collision.
00604   if (!isResolved()) {
00605     // Still unresolved, so RAUW.
00606     //
00607     // First, clear out all operands to prevent any recursion (similar to
00608     // dropAllReferences(), but we still need the use-list).
00609     for (unsigned O = 0, E = getNumOperands(); O != E; ++O)
00610       setOperand(O, nullptr);
00611     Context.getReplaceableUses()->replaceAllUsesWith(Uniqued);
00612     deleteAsSubclass();
00613     return;
00614   }
00615 
00616   // Store in non-uniqued form if RAUW isn't possible.
00617   storeDistinctInContext();
00618 }
00619 
00620 void MDNode::deleteAsSubclass() {
00621   switch (getMetadataID()) {
00622   default:
00623     llvm_unreachable("Invalid subclass of MDNode");
00624 #define HANDLE_MDNODE_LEAF(CLASS)                                              \
00625   case CLASS##Kind:                                                            \
00626     delete cast<CLASS>(this);                                                  \
00627     break;
00628 #include "llvm/IR/Metadata.def"
00629   }
00630 }
00631 
00632 template <class T, class InfoT>
00633 static T *uniquifyImpl(T *N, DenseSet<T *, InfoT> &Store) {
00634   if (T *U = getUniqued(Store, N))
00635     return U;
00636 
00637   Store.insert(N);
00638   return N;
00639 }
00640 
00641 template <class NodeTy> struct MDNode::HasCachedHash {
00642   typedef char Yes[1];
00643   typedef char No[2];
00644   template <class U, U Val> struct SFINAE {};
00645 
00646   template <class U>
00647   static Yes &check(SFINAE<void (U::*)(unsigned), &U::setHash> *);
00648   template <class U> static No &check(...);
00649 
00650   static const bool value = sizeof(check<NodeTy>(nullptr)) == sizeof(Yes);
00651 };
00652 
00653 MDNode *MDNode::uniquify() {
00654   assert(!hasSelfReference(this) && "Cannot uniquify a self-referencing node");
00655 
00656   // Try to insert into uniquing store.
00657   switch (getMetadataID()) {
00658   default:
00659     llvm_unreachable("Invalid subclass of MDNode");
00660 #define HANDLE_MDNODE_LEAF(CLASS)                                              \
00661   case CLASS##Kind: {                                                          \
00662     CLASS *SubclassThis = cast<CLASS>(this);                                   \
00663     std::integral_constant<bool, HasCachedHash<CLASS>::value>                  \
00664         ShouldRecalculateHash;                                                 \
00665     dispatchRecalculateHash(SubclassThis, ShouldRecalculateHash);              \
00666     return uniquifyImpl(SubclassThis, getContext().pImpl->CLASS##s);           \
00667   }
00668 #include "llvm/IR/Metadata.def"
00669   }
00670 }
00671 
00672 void MDNode::eraseFromStore() {
00673   switch (getMetadataID()) {
00674   default:
00675     llvm_unreachable("Invalid subclass of MDNode");
00676 #define HANDLE_MDNODE_LEAF(CLASS)                                              \
00677   case CLASS##Kind:                                                            \
00678     getContext().pImpl->CLASS##s.erase(cast<CLASS>(this));                     \
00679     break;
00680 #include "llvm/IR/Metadata.def"
00681   }
00682 }
00683 
00684 MDTuple *MDTuple::getImpl(LLVMContext &Context, ArrayRef<Metadata *> MDs,
00685                           StorageType Storage, bool ShouldCreate) {
00686   unsigned Hash = 0;
00687   if (Storage == Uniqued) {
00688     MDTupleInfo::KeyTy Key(MDs);
00689     if (auto *N = getUniqued(Context.pImpl->MDTuples, Key))
00690       return N;
00691     if (!ShouldCreate)
00692       return nullptr;
00693     Hash = Key.getHash();
00694   } else {
00695     assert(ShouldCreate && "Expected non-uniqued nodes to always be created");
00696   }
00697 
00698   return storeImpl(new (MDs.size()) MDTuple(Context, Storage, Hash, MDs),
00699                    Storage, Context.pImpl->MDTuples);
00700 }
00701 
00702 void MDNode::deleteTemporary(MDNode *N) {
00703   assert(N->isTemporary() && "Expected temporary node");
00704   N->replaceAllUsesWith(nullptr);
00705   N->deleteAsSubclass();
00706 }
00707 
00708 void MDNode::storeDistinctInContext() {
00709   assert(isResolved() && "Expected resolved nodes");
00710   Storage = Distinct;
00711 
00712   // Reset the hash.
00713   switch (getMetadataID()) {
00714   default:
00715     llvm_unreachable("Invalid subclass of MDNode");
00716 #define HANDLE_MDNODE_LEAF(CLASS)                                              \
00717   case CLASS##Kind: {                                                          \
00718     std::integral_constant<bool, HasCachedHash<CLASS>::value> ShouldResetHash; \
00719     dispatchResetHash(cast<CLASS>(this), ShouldResetHash);                     \
00720     break;                                                                     \
00721   }
00722 #include "llvm/IR/Metadata.def"
00723   }
00724 
00725   getContext().pImpl->DistinctMDNodes.insert(this);
00726 }
00727 
00728 void MDNode::replaceOperandWith(unsigned I, Metadata *New) {
00729   if (getOperand(I) == New)
00730     return;
00731 
00732   if (!isUniqued()) {
00733     setOperand(I, New);
00734     return;
00735   }
00736 
00737   handleChangedOperand(mutable_begin() + I, New);
00738 }
00739 
00740 void MDNode::setOperand(unsigned I, Metadata *New) {
00741   assert(I < NumOperands);
00742   mutable_begin()[I].reset(New, isUniqued() ? this : nullptr);
00743 }
00744 
00745 /// \brief Get a node, or a self-reference that looks like it.
00746 ///
00747 /// Special handling for finding self-references, for use by \a
00748 /// MDNode::concatenate() and \a MDNode::intersect() to maintain behaviour from
00749 /// when self-referencing nodes were still uniqued.  If the first operand has
00750 /// the same operands as \c Ops, return the first operand instead.
00751 static MDNode *getOrSelfReference(LLVMContext &Context,
00752                                   ArrayRef<Metadata *> Ops) {
00753   if (!Ops.empty())
00754     if (MDNode *N = dyn_cast_or_null<MDNode>(Ops[0]))
00755       if (N->getNumOperands() == Ops.size() && N == N->getOperand(0)) {
00756         for (unsigned I = 1, E = Ops.size(); I != E; ++I)
00757           if (Ops[I] != N->getOperand(I))
00758             return MDNode::get(Context, Ops);
00759         return N;
00760       }
00761 
00762   return MDNode::get(Context, Ops);
00763 }
00764 
00765 MDNode *MDNode::concatenate(MDNode *A, MDNode *B) {
00766   if (!A)
00767     return B;
00768   if (!B)
00769     return A;
00770 
00771   SmallVector<Metadata *, 4> MDs;
00772   MDs.reserve(A->getNumOperands() + B->getNumOperands());
00773   MDs.append(A->op_begin(), A->op_end());
00774   MDs.append(B->op_begin(), B->op_end());
00775 
00776   // FIXME: This preserves long-standing behaviour, but is it really the right
00777   // behaviour?  Or was that an unintended side-effect of node uniquing?
00778   return getOrSelfReference(A->getContext(), MDs);
00779 }
00780 
00781 MDNode *MDNode::intersect(MDNode *A, MDNode *B) {
00782   if (!A || !B)
00783     return nullptr;
00784 
00785   SmallVector<Metadata *, 4> MDs;
00786   for (Metadata *MD : A->operands())
00787     if (std::find(B->op_begin(), B->op_end(), MD) != B->op_end())
00788       MDs.push_back(MD);
00789 
00790   // FIXME: This preserves long-standing behaviour, but is it really the right
00791   // behaviour?  Or was that an unintended side-effect of node uniquing?
00792   return getOrSelfReference(A->getContext(), MDs);
00793 }
00794 
00795 MDNode *MDNode::getMostGenericAliasScope(MDNode *A, MDNode *B) {
00796   if (!A || !B)
00797     return nullptr;
00798 
00799   SmallVector<Metadata *, 4> MDs(B->op_begin(), B->op_end());
00800   for (Metadata *MD : A->operands())
00801     if (std::find(B->op_begin(), B->op_end(), MD) == B->op_end())
00802       MDs.push_back(MD);
00803 
00804   // FIXME: This preserves long-standing behaviour, but is it really the right
00805   // behaviour?  Or was that an unintended side-effect of node uniquing?
00806   return getOrSelfReference(A->getContext(), MDs);
00807 }
00808 
00809 MDNode *MDNode::getMostGenericFPMath(MDNode *A, MDNode *B) {
00810   if (!A || !B)
00811     return nullptr;
00812 
00813   APFloat AVal = mdconst::extract<ConstantFP>(A->getOperand(0))->getValueAPF();
00814   APFloat BVal = mdconst::extract<ConstantFP>(B->getOperand(0))->getValueAPF();
00815   if (AVal.compare(BVal) == APFloat::cmpLessThan)
00816     return A;
00817   return B;
00818 }
00819 
00820 static bool isContiguous(const ConstantRange &A, const ConstantRange &B) {
00821   return A.getUpper() == B.getLower() || A.getLower() == B.getUpper();
00822 }
00823 
00824 static bool canBeMerged(const ConstantRange &A, const ConstantRange &B) {
00825   return !A.intersectWith(B).isEmptySet() || isContiguous(A, B);
00826 }
00827 
00828 static bool tryMergeRange(SmallVectorImpl<ConstantInt *> &EndPoints,
00829                           ConstantInt *Low, ConstantInt *High) {
00830   ConstantRange NewRange(Low->getValue(), High->getValue());
00831   unsigned Size = EndPoints.size();
00832   APInt LB = EndPoints[Size - 2]->getValue();
00833   APInt LE = EndPoints[Size - 1]->getValue();
00834   ConstantRange LastRange(LB, LE);
00835   if (canBeMerged(NewRange, LastRange)) {
00836     ConstantRange Union = LastRange.unionWith(NewRange);
00837     Type *Ty = High->getType();
00838     EndPoints[Size - 2] =
00839         cast<ConstantInt>(ConstantInt::get(Ty, Union.getLower()));
00840     EndPoints[Size - 1] =
00841         cast<ConstantInt>(ConstantInt::get(Ty, Union.getUpper()));
00842     return true;
00843   }
00844   return false;
00845 }
00846 
00847 static void addRange(SmallVectorImpl<ConstantInt *> &EndPoints,
00848                      ConstantInt *Low, ConstantInt *High) {
00849   if (!EndPoints.empty())
00850     if (tryMergeRange(EndPoints, Low, High))
00851       return;
00852 
00853   EndPoints.push_back(Low);
00854   EndPoints.push_back(High);
00855 }
00856 
00857 MDNode *MDNode::getMostGenericRange(MDNode *A, MDNode *B) {
00858   // Given two ranges, we want to compute the union of the ranges. This
00859   // is slightly complitade by having to combine the intervals and merge
00860   // the ones that overlap.
00861 
00862   if (!A || !B)
00863     return nullptr;
00864 
00865   if (A == B)
00866     return A;
00867 
00868   // First, walk both lists in older of the lower boundary of each interval.
00869   // At each step, try to merge the new interval to the last one we adedd.
00870   SmallVector<ConstantInt *, 4> EndPoints;
00871   int AI = 0;
00872   int BI = 0;
00873   int AN = A->getNumOperands() / 2;
00874   int BN = B->getNumOperands() / 2;
00875   while (AI < AN && BI < BN) {
00876     ConstantInt *ALow = mdconst::extract<ConstantInt>(A->getOperand(2 * AI));
00877     ConstantInt *BLow = mdconst::extract<ConstantInt>(B->getOperand(2 * BI));
00878 
00879     if (ALow->getValue().slt(BLow->getValue())) {
00880       addRange(EndPoints, ALow,
00881                mdconst::extract<ConstantInt>(A->getOperand(2 * AI + 1)));
00882       ++AI;
00883     } else {
00884       addRange(EndPoints, BLow,
00885                mdconst::extract<ConstantInt>(B->getOperand(2 * BI + 1)));
00886       ++BI;
00887     }
00888   }
00889   while (AI < AN) {
00890     addRange(EndPoints, mdconst::extract<ConstantInt>(A->getOperand(2 * AI)),
00891              mdconst::extract<ConstantInt>(A->getOperand(2 * AI + 1)));
00892     ++AI;
00893   }
00894   while (BI < BN) {
00895     addRange(EndPoints, mdconst::extract<ConstantInt>(B->getOperand(2 * BI)),
00896              mdconst::extract<ConstantInt>(B->getOperand(2 * BI + 1)));
00897     ++BI;
00898   }
00899 
00900   // If we have more than 2 ranges (4 endpoints) we have to try to merge
00901   // the last and first ones.
00902   unsigned Size = EndPoints.size();
00903   if (Size > 4) {
00904     ConstantInt *FB = EndPoints[0];
00905     ConstantInt *FE = EndPoints[1];
00906     if (tryMergeRange(EndPoints, FB, FE)) {
00907       for (unsigned i = 0; i < Size - 2; ++i) {
00908         EndPoints[i] = EndPoints[i + 2];
00909       }
00910       EndPoints.resize(Size - 2);
00911     }
00912   }
00913 
00914   // If in the end we have a single range, it is possible that it is now the
00915   // full range. Just drop the metadata in that case.
00916   if (EndPoints.size() == 2) {
00917     ConstantRange Range(EndPoints[0]->getValue(), EndPoints[1]->getValue());
00918     if (Range.isFullSet())
00919       return nullptr;
00920   }
00921 
00922   SmallVector<Metadata *, 4> MDs;
00923   MDs.reserve(EndPoints.size());
00924   for (auto *I : EndPoints)
00925     MDs.push_back(ConstantAsMetadata::get(I));
00926   return MDNode::get(A->getContext(), MDs);
00927 }
00928 
00929 //===----------------------------------------------------------------------===//
00930 // NamedMDNode implementation.
00931 //
00932 
00933 static SmallVector<TrackingMDRef, 4> &getNMDOps(void *Operands) {
00934   return *(SmallVector<TrackingMDRef, 4> *)Operands;
00935 }
00936 
00937 NamedMDNode::NamedMDNode(const Twine &N)
00938     : Name(N.str()), Parent(nullptr),
00939       Operands(new SmallVector<TrackingMDRef, 4>()) {}
00940 
00941 NamedMDNode::~NamedMDNode() {
00942   dropAllReferences();
00943   delete &getNMDOps(Operands);
00944 }
00945 
00946 unsigned NamedMDNode::getNumOperands() const {
00947   return (unsigned)getNMDOps(Operands).size();
00948 }
00949 
00950 MDNode *NamedMDNode::getOperand(unsigned i) const {
00951   assert(i < getNumOperands() && "Invalid Operand number!");
00952   auto *N = getNMDOps(Operands)[i].get();
00953   return cast_or_null<MDNode>(N);
00954 }
00955 
00956 void NamedMDNode::addOperand(MDNode *M) { getNMDOps(Operands).emplace_back(M); }
00957 
00958 void NamedMDNode::setOperand(unsigned I, MDNode *New) {
00959   assert(I < getNumOperands() && "Invalid operand number");
00960   getNMDOps(Operands)[I].reset(New);
00961 }
00962 
00963 void NamedMDNode::eraseFromParent() {
00964   getParent()->eraseNamedMetadata(this);
00965 }
00966 
00967 void NamedMDNode::dropAllReferences() {
00968   getNMDOps(Operands).clear();
00969 }
00970 
00971 StringRef NamedMDNode::getName() const {
00972   return StringRef(Name);
00973 }
00974 
00975 //===----------------------------------------------------------------------===//
00976 // Instruction Metadata method implementations.
00977 //
00978 void MDAttachmentMap::set(unsigned ID, MDNode &MD) {
00979   for (auto &I : Attachments)
00980     if (I.first == ID) {
00981       I.second.reset(&MD);
00982       return;
00983     }
00984   Attachments.emplace_back(std::piecewise_construct, std::make_tuple(ID),
00985                            std::make_tuple(&MD));
00986 }
00987 
00988 void MDAttachmentMap::erase(unsigned ID) {
00989   if (empty())
00990     return;
00991 
00992   // Common case is one/last value.
00993   if (Attachments.back().first == ID) {
00994     Attachments.pop_back();
00995     return;
00996   }
00997 
00998   for (auto I = Attachments.begin(), E = std::prev(Attachments.end()); I != E;
00999        ++I)
01000     if (I->first == ID) {
01001       *I = std::move(Attachments.back());
01002       Attachments.pop_back();
01003       return;
01004     }
01005 }
01006 
01007 MDNode *MDAttachmentMap::lookup(unsigned ID) const {
01008   for (const auto &I : Attachments)
01009     if (I.first == ID)
01010       return I.second;
01011   return nullptr;
01012 }
01013 
01014 void MDAttachmentMap::getAll(
01015     SmallVectorImpl<std::pair<unsigned, MDNode *>> &Result) const {
01016   Result.append(Attachments.begin(), Attachments.end());
01017 
01018   // Sort the resulting array so it is stable.
01019   if (Result.size() > 1)
01020     array_pod_sort(Result.begin(), Result.end());
01021 }
01022 
01023 void Instruction::setMetadata(StringRef Kind, MDNode *Node) {
01024   if (!Node && !hasMetadata())
01025     return;
01026   setMetadata(getContext().getMDKindID(Kind), Node);
01027 }
01028 
01029 MDNode *Instruction::getMetadataImpl(StringRef Kind) const {
01030   return getMetadataImpl(getContext().getMDKindID(Kind));
01031 }
01032 
01033 void Instruction::dropUnknownMetadata(ArrayRef<unsigned> KnownIDs) {
01034   SmallSet<unsigned, 5> KnownSet;
01035   KnownSet.insert(KnownIDs.begin(), KnownIDs.end());
01036 
01037   // Drop debug if needed
01038   if (KnownSet.erase(LLVMContext::MD_dbg))
01039     DbgLoc = DebugLoc();
01040 
01041   if (!hasMetadataHashEntry())
01042     return; // Nothing to remove!
01043 
01044   auto &InstructionMetadata = getContext().pImpl->InstructionMetadata;
01045 
01046   if (KnownSet.empty()) {
01047     // Just drop our entry at the store.
01048     InstructionMetadata.erase(this);
01049     setHasMetadataHashEntry(false);
01050     return;
01051   }
01052 
01053   auto &Info = InstructionMetadata[this];
01054   Info.remove_if([&KnownSet](const std::pair<unsigned, TrackingMDNodeRef> &I) {
01055     return !KnownSet.count(I.first);
01056   });
01057 
01058   if (Info.empty()) {
01059     // Drop our entry at the store.
01060     InstructionMetadata.erase(this);
01061     setHasMetadataHashEntry(false);
01062   }
01063 }
01064 
01065 /// setMetadata - Set the metadata of of the specified kind to the specified
01066 /// node.  This updates/replaces metadata if already present, or removes it if
01067 /// Node is null.
01068 void Instruction::setMetadata(unsigned KindID, MDNode *Node) {
01069   if (!Node && !hasMetadata())
01070     return;
01071 
01072   // Handle 'dbg' as a special case since it is not stored in the hash table.
01073   if (KindID == LLVMContext::MD_dbg) {
01074     DbgLoc = DebugLoc(Node);
01075     return;
01076   }
01077   
01078   // Handle the case when we're adding/updating metadata on an instruction.
01079   if (Node) {
01080     auto &Info = getContext().pImpl->InstructionMetadata[this];
01081     assert(!Info.empty() == hasMetadataHashEntry() &&
01082            "HasMetadata bit is wonked");
01083     if (Info.empty())
01084       setHasMetadataHashEntry(true);
01085     Info.set(KindID, *Node);
01086     return;
01087   }
01088 
01089   // Otherwise, we're removing metadata from an instruction.
01090   assert((hasMetadataHashEntry() ==
01091           (getContext().pImpl->InstructionMetadata.count(this) > 0)) &&
01092          "HasMetadata bit out of date!");
01093   if (!hasMetadataHashEntry())
01094     return;  // Nothing to remove!
01095   auto &Info = getContext().pImpl->InstructionMetadata[this];
01096 
01097   // Handle removal of an existing value.
01098   Info.erase(KindID);
01099 
01100   if (!Info.empty())
01101     return;
01102 
01103   getContext().pImpl->InstructionMetadata.erase(this);
01104   setHasMetadataHashEntry(false);
01105 }
01106 
01107 void Instruction::setAAMetadata(const AAMDNodes &N) {
01108   setMetadata(LLVMContext::MD_tbaa, N.TBAA);
01109   setMetadata(LLVMContext::MD_alias_scope, N.Scope);
01110   setMetadata(LLVMContext::MD_noalias, N.NoAlias);
01111 }
01112 
01113 MDNode *Instruction::getMetadataImpl(unsigned KindID) const {
01114   // Handle 'dbg' as a special case since it is not stored in the hash table.
01115   if (KindID == LLVMContext::MD_dbg)
01116     return DbgLoc.getAsMDNode();
01117 
01118   if (!hasMetadataHashEntry())
01119     return nullptr;
01120   auto &Info = getContext().pImpl->InstructionMetadata[this];
01121   assert(!Info.empty() && "bit out of sync with hash table");
01122 
01123   return Info.lookup(KindID);
01124 }
01125 
01126 void Instruction::getAllMetadataImpl(
01127     SmallVectorImpl<std::pair<unsigned, MDNode *>> &Result) const {
01128   Result.clear();
01129   
01130   // Handle 'dbg' as a special case since it is not stored in the hash table.
01131   if (DbgLoc) {
01132     Result.push_back(
01133         std::make_pair((unsigned)LLVMContext::MD_dbg, DbgLoc.getAsMDNode()));
01134     if (!hasMetadataHashEntry()) return;
01135   }
01136 
01137   assert(hasMetadataHashEntry() &&
01138          getContext().pImpl->InstructionMetadata.count(this) &&
01139          "Shouldn't have called this");
01140   const auto &Info = getContext().pImpl->InstructionMetadata.find(this)->second;
01141   assert(!Info.empty() && "Shouldn't have called this");
01142   Info.getAll(Result);
01143 }
01144 
01145 void Instruction::getAllMetadataOtherThanDebugLocImpl(
01146     SmallVectorImpl<std::pair<unsigned, MDNode *>> &Result) const {
01147   Result.clear();
01148   assert(hasMetadataHashEntry() &&
01149          getContext().pImpl->InstructionMetadata.count(this) &&
01150          "Shouldn't have called this");
01151   const auto &Info = getContext().pImpl->InstructionMetadata.find(this)->second;
01152   assert(!Info.empty() && "Shouldn't have called this");
01153   Info.getAll(Result);
01154 }
01155 
01156 /// clearMetadataHashEntries - Clear all hashtable-based metadata from
01157 /// this instruction.
01158 void Instruction::clearMetadataHashEntries() {
01159   assert(hasMetadataHashEntry() && "Caller should check");
01160   getContext().pImpl->InstructionMetadata.erase(this);
01161   setHasMetadataHashEntry(false);
01162 }
01163 
01164 MDNode *Function::getMetadata(unsigned KindID) const {
01165   if (!hasMetadata())
01166     return nullptr;
01167   return getContext().pImpl->FunctionMetadata[this].lookup(KindID);
01168 }
01169 
01170 MDNode *Function::getMetadata(StringRef Kind) const {
01171   if (!hasMetadata())
01172     return nullptr;
01173   return getMetadata(getContext().getMDKindID(Kind));
01174 }
01175 
01176 void Function::setMetadata(unsigned KindID, MDNode *MD) {
01177   if (MD) {
01178     if (!hasMetadata())
01179       setHasMetadataHashEntry(true);
01180 
01181     getContext().pImpl->FunctionMetadata[this].set(KindID, *MD);
01182     return;
01183   }
01184 
01185   // Nothing to unset.
01186   if (!hasMetadata())
01187     return;
01188 
01189   auto &Store = getContext().pImpl->FunctionMetadata[this];
01190   Store.erase(KindID);
01191   if (Store.empty())
01192     clearMetadata();
01193 }
01194 
01195 void Function::setMetadata(StringRef Kind, MDNode *MD) {
01196   if (!MD && !hasMetadata())
01197     return;
01198   setMetadata(getContext().getMDKindID(Kind), MD);
01199 }
01200 
01201 void Function::getAllMetadata(
01202     SmallVectorImpl<std::pair<unsigned, MDNode *>> &MDs) const {
01203   MDs.clear();
01204 
01205   if (!hasMetadata())
01206     return;
01207 
01208   getContext().pImpl->FunctionMetadata[this].getAll(MDs);
01209 }
01210 
01211 void Function::dropUnknownMetadata(ArrayRef<unsigned> KnownIDs) {
01212   if (!hasMetadata())
01213     return;
01214   if (KnownIDs.empty()) {
01215     clearMetadata();
01216     return;
01217   }
01218 
01219   SmallSet<unsigned, 5> KnownSet;
01220   KnownSet.insert(KnownIDs.begin(), KnownIDs.end());
01221 
01222   auto &Store = getContext().pImpl->FunctionMetadata[this];
01223   assert(!Store.empty());
01224 
01225   Store.remove_if([&KnownSet](const std::pair<unsigned, TrackingMDNodeRef> &I) {
01226     return !KnownSet.count(I.first);
01227   });
01228 
01229   if (Store.empty())
01230     clearMetadata();
01231 }
01232 
01233 void Function::clearMetadata() {
01234   if (!hasMetadata())
01235     return;
01236   getContext().pImpl->FunctionMetadata.erase(this);
01237   setHasMetadataHashEntry(false);
01238 }