LLVM API Documentation

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 "SymbolTableListTraitsImpl.h"
00017 #include "llvm/ADT/DenseMap.h"
00018 #include "llvm/ADT/STLExtras.h"
00019 #include "llvm/ADT/SmallSet.h"
00020 #include "llvm/ADT/SmallString.h"
00021 #include "llvm/ADT/StringMap.h"
00022 #include "llvm/IR/ConstantRange.h"
00023 #include "llvm/IR/Instruction.h"
00024 #include "llvm/IR/LLVMContext.h"
00025 #include "llvm/IR/LeakDetector.h"
00026 #include "llvm/IR/Module.h"
00027 #include "llvm/IR/ValueHandle.h"
00028 
00029 using namespace llvm;
00030 
00031 MetadataAsValue::MetadataAsValue(Type *Ty, Metadata *MD)
00032     : Value(Ty, MetadataAsValueVal), MD(MD) {
00033   track();
00034 }
00035 
00036 MetadataAsValue::~MetadataAsValue() {
00037   getType()->getContext().pImpl->MetadataAsValues.erase(MD);
00038   untrack();
00039 }
00040 
00041 /// \brief Canonicalize metadata arguments to intrinsics.
00042 ///
00043 /// To support bitcode upgrades (and assembly semantic sugar) for \a
00044 /// MetadataAsValue, we need to canonicalize certain metadata.
00045 ///
00046 ///   - nullptr is replaced by an empty MDNode.
00047 ///   - An MDNode with a single null operand is replaced by an empty MDNode.
00048 ///   - An MDNode whose only operand is a \a ConstantAsMetadata gets skipped.
00049 ///
00050 /// This maintains readability of bitcode from when metadata was a type of
00051 /// value, and these bridges were unnecessary.
00052 static Metadata *canonicalizeMetadataForValue(LLVMContext &Context,
00053                                               Metadata *MD) {
00054   if (!MD)
00055     // !{}
00056     return MDNode::get(Context, None);
00057 
00058   // Return early if this isn't a single-operand MDNode.
00059   auto *N = dyn_cast<MDNode>(MD);
00060   if (!N || N->getNumOperands() != 1)
00061     return MD;
00062 
00063   if (!N->getOperand(0))
00064     // !{}
00065     return MDNode::get(Context, None);
00066 
00067   if (auto *C = dyn_cast<ConstantAsMetadata>(N->getOperand(0)))
00068     // Look through the MDNode.
00069     return C;
00070 
00071   return MD;
00072 }
00073 
00074 MetadataAsValue *MetadataAsValue::get(LLVMContext &Context, Metadata *MD) {
00075   MD = canonicalizeMetadataForValue(Context, MD);
00076   auto *&Entry = Context.pImpl->MetadataAsValues[MD];
00077   if (!Entry)
00078     Entry = new MetadataAsValue(Type::getMetadataTy(Context), MD);
00079   return Entry;
00080 }
00081 
00082 MetadataAsValue *MetadataAsValue::getIfExists(LLVMContext &Context,
00083                                               Metadata *MD) {
00084   MD = canonicalizeMetadataForValue(Context, MD);
00085   auto &Store = Context.pImpl->MetadataAsValues;
00086   auto I = Store.find(MD);
00087   return I == Store.end() ? nullptr : I->second;
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<MDNodeFwdDecl>(MD)) && "Expected non-temp node");
00160 
00161   if (UseMap.empty())
00162     return;
00163 
00164   // Copy out uses since UseMap will get touched below.
00165   typedef std::pair<void *, std::pair<OwnerTy, uint64_t>> UseTy;
00166   SmallVector<UseTy, 8> Uses(UseMap.begin(), UseMap.end());
00167   std::sort(Uses.begin(), Uses.end(), [](const UseTy &L, const UseTy &R) {
00168     return L.second.second < R.second.second;
00169   });
00170   for (const auto &Pair : Uses) {
00171     OwnerTy Owner = Pair.second.first;
00172     if (!Owner) {
00173       // Update unowned tracking references directly.
00174       Metadata *&Ref = *static_cast<Metadata **>(Pair.first);
00175       Ref = MD;
00176       if (MD)
00177         MetadataTracking::track(Ref);
00178       UseMap.erase(Pair.first);
00179       continue;
00180     }
00181 
00182     // Check for MetadataAsValue.
00183     if (Owner.is<MetadataAsValue *>()) {
00184       Owner.get<MetadataAsValue *>()->handleChangedMetadata(MD);
00185       continue;
00186     }
00187 
00188     // There's a Metadata owner -- dispatch.
00189     Metadata *OwnerMD = Owner.get<Metadata *>();
00190     switch (OwnerMD->getMetadataID()) {
00191 #define HANDLE_METADATA_LEAF(CLASS)                                            \
00192   case Metadata::CLASS##Kind:                                                  \
00193     cast<CLASS>(OwnerMD)->handleChangedOperand(Pair.first, MD);                \
00194     continue;
00195 #include "llvm/IR/Metadata.def"
00196     default:
00197       llvm_unreachable("Invalid metadata subclass");
00198     }
00199   }
00200   assert(UseMap.empty() && "Expected all uses to be replaced");
00201 }
00202 
00203 void ReplaceableMetadataImpl::resolveAllUses(bool ResolveUsers) {
00204   if (UseMap.empty())
00205     return;
00206 
00207   if (!ResolveUsers) {
00208     UseMap.clear();
00209     return;
00210   }
00211 
00212   // Copy out uses since UseMap could get touched below.
00213   typedef std::pair<void *, std::pair<OwnerTy, uint64_t>> UseTy;
00214   SmallVector<UseTy, 8> Uses(UseMap.begin(), UseMap.end());
00215   std::sort(Uses.begin(), Uses.end(), [](const UseTy &L, const UseTy &R) {
00216     return L.second.second < R.second.second;
00217   });
00218   UseMap.clear();
00219   for (const auto &Pair : Uses) {
00220     auto Owner = Pair.second.first;
00221     if (!Owner)
00222       continue;
00223     if (Owner.is<MetadataAsValue *>())
00224       continue;
00225 
00226     // Resolve GenericMDNodes that point at this.
00227     auto *OwnerMD = dyn_cast<GenericMDNode>(Owner.get<Metadata *>());
00228     if (!OwnerMD)
00229       continue;
00230     if (OwnerMD->isResolved())
00231       continue;
00232     OwnerMD->decrementUnresolvedOperands();
00233     if (!OwnerMD->hasUnresolvedOperands())
00234       OwnerMD->resolve();
00235   }
00236 }
00237 
00238 static Function *getLocalFunction(Value *V) {
00239   assert(V && "Expected value");
00240   if (auto *A = dyn_cast<Argument>(V))
00241     return A->getParent();
00242   if (BasicBlock *BB = cast<Instruction>(V)->getParent())
00243     return BB->getParent();
00244   return nullptr;
00245 }
00246 
00247 ValueAsMetadata *ValueAsMetadata::get(Value *V) {
00248   assert(V && "Unexpected null Value");
00249 
00250   auto &Context = V->getContext();
00251   auto *&Entry = Context.pImpl->ValuesAsMetadata[V];
00252   if (!Entry) {
00253     assert((isa<Constant>(V) || isa<Argument>(V) || isa<Instruction>(V)) &&
00254            "Expected constant or function-local value");
00255     assert(!V->NameAndIsUsedByMD.getInt() &&
00256            "Expected this to be the only metadata use");
00257     V->NameAndIsUsedByMD.setInt(true);
00258     if (auto *C = dyn_cast<Constant>(V))
00259       Entry = new ConstantAsMetadata(Context, C);
00260     else
00261       Entry = new LocalAsMetadata(Context, V);
00262   }
00263 
00264   return Entry;
00265 }
00266 
00267 ValueAsMetadata *ValueAsMetadata::getIfExists(Value *V) {
00268   assert(V && "Unexpected null Value");
00269   return V->getContext().pImpl->ValuesAsMetadata.lookup(V);
00270 }
00271 
00272 void ValueAsMetadata::handleDeletion(Value *V) {
00273   assert(V && "Expected valid value");
00274 
00275   auto &Store = V->getType()->getContext().pImpl->ValuesAsMetadata;
00276   auto I = Store.find(V);
00277   if (I == Store.end())
00278     return;
00279 
00280   // Remove old entry from the map.
00281   ValueAsMetadata *MD = I->second;
00282   assert(MD && "Expected valid metadata");
00283   assert(MD->getValue() == V && "Expected valid mapping");
00284   Store.erase(I);
00285 
00286   // Delete the metadata.
00287   MD->replaceAllUsesWith(nullptr);
00288   delete MD;
00289 }
00290 
00291 void ValueAsMetadata::handleRAUW(Value *From, Value *To) {
00292   assert(From && "Expected valid value");
00293   assert(To && "Expected valid value");
00294   assert(From != To && "Expected changed value");
00295   assert(From->getType() == To->getType() && "Unexpected type change");
00296 
00297   LLVMContext &Context = From->getType()->getContext();
00298   auto &Store = Context.pImpl->ValuesAsMetadata;
00299   auto I = Store.find(From);
00300   if (I == Store.end()) {
00301     assert(!From->NameAndIsUsedByMD.getInt() &&
00302            "Expected From not to be used by metadata");
00303     return;
00304   }
00305 
00306   // Remove old entry from the map.
00307   assert(From->NameAndIsUsedByMD.getInt() &&
00308          "Expected From to be used by metadata");
00309   From->NameAndIsUsedByMD.setInt(false);
00310   ValueAsMetadata *MD = I->second;
00311   assert(MD && "Expected valid metadata");
00312   assert(MD->getValue() == From && "Expected valid mapping");
00313   Store.erase(I);
00314 
00315   if (isa<LocalAsMetadata>(MD)) {
00316     if (auto *C = dyn_cast<Constant>(To)) {
00317       // Local became a constant.
00318       MD->replaceAllUsesWith(ConstantAsMetadata::get(C));
00319       delete MD;
00320       return;
00321     }
00322     if (getLocalFunction(From) && getLocalFunction(To) &&
00323         getLocalFunction(From) != getLocalFunction(To)) {
00324       // Function changed.
00325       MD->replaceAllUsesWith(nullptr);
00326       delete MD;
00327       return;
00328     }
00329   } else if (!isa<Constant>(To)) {
00330     // Changed to function-local value.
00331     MD->replaceAllUsesWith(nullptr);
00332     delete MD;
00333     return;
00334   }
00335 
00336   auto *&Entry = Store[To];
00337   if (Entry) {
00338     // The target already exists.
00339     MD->replaceAllUsesWith(Entry);
00340     delete MD;
00341     return;
00342   }
00343 
00344   // Update MD in place (and update the map entry).
00345   assert(!To->NameAndIsUsedByMD.getInt() &&
00346          "Expected this to be the only metadata use");
00347   To->NameAndIsUsedByMD.setInt(true);
00348   MD->V = To;
00349   Entry = MD;
00350 }
00351 
00352 //===----------------------------------------------------------------------===//
00353 // MDString implementation.
00354 //
00355 
00356 MDString *MDString::get(LLVMContext &Context, StringRef Str) {
00357   auto &Store = Context.pImpl->MDStringCache;
00358   auto I = Store.find(Str);
00359   if (I != Store.end())
00360     return &I->second;
00361 
00362   auto *Entry =
00363       StringMapEntry<MDString>::Create(Str, Store.getAllocator(), MDString());
00364   bool WasInserted = Store.insert(Entry);
00365   (void)WasInserted;
00366   assert(WasInserted && "Expected entry to be inserted");
00367   Entry->second.Entry = Entry;
00368   return &Entry->second;
00369 }
00370 
00371 StringRef MDString::getString() const {
00372   assert(Entry && "Expected to find string map entry");
00373   return Entry->first();
00374 }
00375 
00376 //===----------------------------------------------------------------------===//
00377 // MDNode implementation.
00378 //
00379 
00380 void *MDNode::operator new(size_t Size, unsigned NumOps) {
00381   void *Ptr = ::operator new(Size + NumOps * sizeof(MDOperand));
00382   MDOperand *O = static_cast<MDOperand *>(Ptr);
00383   for (MDOperand *E = O + NumOps; O != E; ++O)
00384     (void)new (O) MDOperand;
00385   return O;
00386 }
00387 
00388 void MDNode::operator delete(void *Mem) {
00389   MDNode *N = static_cast<MDNode *>(Mem);
00390   MDOperand *O = static_cast<MDOperand *>(Mem);
00391   for (MDOperand *E = O - N->NumOperands; O != E; --O)
00392     (O - 1)->~MDOperand();
00393   ::operator delete(O);
00394 }
00395 
00396 MDNode::MDNode(LLVMContext &Context, unsigned ID, ArrayRef<Metadata *> MDs)
00397     : Metadata(ID), Context(Context), NumOperands(MDs.size()),
00398       MDNodeSubclassData(0) {
00399   for (unsigned I = 0, E = MDs.size(); I != E; ++I)
00400     setOperand(I, MDs[I]);
00401 }
00402 
00403 bool MDNode::isResolved() const {
00404   if (isa<MDNodeFwdDecl>(this))
00405     return false;
00406   return cast<GenericMDNode>(this)->isResolved();
00407 }
00408 
00409 static bool isOperandUnresolved(Metadata *Op) {
00410   if (auto *N = dyn_cast_or_null<MDNode>(Op))
00411     return !N->isResolved();
00412   return false;
00413 }
00414 
00415 GenericMDNode::GenericMDNode(LLVMContext &C, ArrayRef<Metadata *> Vals)
00416     : MDNode(C, GenericMDNodeKind, Vals) {
00417   // Check whether any operands are unresolved, requiring re-uniquing.
00418   for (const auto &Op : operands())
00419     if (isOperandUnresolved(Op))
00420       incrementUnresolvedOperands();
00421 
00422   if (hasUnresolvedOperands())
00423     ReplaceableUses.reset(new ReplaceableMetadataImpl);
00424 }
00425 
00426 GenericMDNode::~GenericMDNode() {
00427   LLVMContextImpl *pImpl = getContext().pImpl;
00428   if (isStoredDistinctInContext())
00429     pImpl->NonUniquedMDNodes.erase(this);
00430   else
00431     pImpl->MDNodeSet.erase(this);
00432   dropAllReferences();
00433 }
00434 
00435 void GenericMDNode::resolve() {
00436   assert(!isResolved() && "Expected this to be unresolved");
00437 
00438   // Move the map, so that this immediately looks resolved.
00439   auto Uses = std::move(ReplaceableUses);
00440   SubclassData32 = 0;
00441   assert(isResolved() && "Expected this to be resolved");
00442 
00443   // Drop RAUW support.
00444   Uses->resolveAllUses();
00445 }
00446 
00447 void GenericMDNode::resolveCycles() {
00448   if (isResolved())
00449     return;
00450 
00451   // Resolve this node immediately.
00452   resolve();
00453 
00454   // Resolve all operands.
00455   for (const auto &Op : operands()) {
00456     if (!Op)
00457       continue;
00458     assert(!isa<MDNodeFwdDecl>(Op) &&
00459            "Expected all forward declarations to be resolved");
00460     if (auto *N = dyn_cast<GenericMDNode>(Op))
00461       if (!N->isResolved())
00462         N->resolveCycles();
00463   }
00464 }
00465 
00466 void MDNode::dropAllReferences() {
00467   for (unsigned I = 0, E = NumOperands; I != E; ++I)
00468     setOperand(I, nullptr);
00469   if (auto *G = dyn_cast<GenericMDNode>(this))
00470     if (!G->isResolved()) {
00471       G->ReplaceableUses->resolveAllUses(/* ResolveUsers */ false);
00472       G->ReplaceableUses.reset();
00473     }
00474 }
00475 
00476 namespace llvm {
00477 /// \brief Make MDOperand transparent for hashing.
00478 ///
00479 /// This overload of an implementation detail of the hashing library makes
00480 /// MDOperand hash to the same value as a \a Metadata pointer.
00481 ///
00482 /// Note that overloading \a hash_value() as follows:
00483 ///
00484 /// \code
00485 ///     size_t hash_value(const MDOperand &X) { return hash_value(X.get()); }
00486 /// \endcode
00487 ///
00488 /// does not cause MDOperand to be transparent.  In particular, a bare pointer
00489 /// doesn't get hashed before it's combined, whereas \a MDOperand would.
00490 static const Metadata *get_hashable_data(const MDOperand &X) { return X.get(); }
00491 }
00492 
00493 void GenericMDNode::handleChangedOperand(void *Ref, Metadata *New) {
00494   unsigned Op = static_cast<MDOperand *>(Ref) - op_begin();
00495   assert(Op < getNumOperands() && "Expected valid operand");
00496 
00497   if (isStoredDistinctInContext()) {
00498     assert(isResolved() && "Expected distinct node to be resolved");
00499 
00500     // This node is not uniqued.  Just set the operand and be done with it.
00501     setOperand(Op, New);
00502     return;
00503   }
00504   if (InRAUW) {
00505     // We just hit a recursion due to RAUW.  Set the operand and move on, since
00506     // we're about to be deleted.
00507     //
00508     // FIXME: Can this cycle really happen?
00509     setOperand(Op, New);
00510     return;
00511   }
00512 
00513   auto &Store = getContext().pImpl->MDNodeSet;
00514   Store.erase(this);
00515 
00516   Metadata *Old = getOperand(Op);
00517   setOperand(Op, New);
00518 
00519   // Drop uniquing for self-reference cycles or if an operand drops to null.
00520   //
00521   // FIXME: Stop dropping uniquing when an operand drops to null.  The original
00522   // motivation was to prevent madness during teardown of LLVMContextImpl, but
00523   // dropAllReferences() fixes that problem in a better way.  (It's just here
00524   // now for better staging of semantic changes.)
00525   if (New == this || !New) {
00526     storeDistinctInContext();
00527     setHash(0);
00528     if (!isResolved())
00529       resolve();
00530     return;
00531   }
00532 
00533   // Re-calculate the hash.
00534   setHash(hash_combine_range(op_begin(), op_end()));
00535 #ifndef NDEBUG
00536   {
00537     SmallVector<Metadata *, 8> MDs(op_begin(), op_end());
00538     unsigned RawHash = hash_combine_range(MDs.begin(), MDs.end());
00539     assert(getHash() == RawHash &&
00540            "Expected hash of MDOperand to equal hash of Metadata*");
00541   }
00542 #endif
00543 
00544   // Re-unique the node.
00545   GenericMDNodeInfo::KeyTy Key(this);
00546   auto I = Store.find_as(Key);
00547   if (I == Store.end()) {
00548     Store.insert(this);
00549 
00550     if (!isResolved()) {
00551       // Check if the last unresolved operand has just been resolved; if so,
00552       // resolve this as well.
00553       if (isOperandUnresolved(Old))
00554         decrementUnresolvedOperands();
00555       if (isOperandUnresolved(New))
00556         incrementUnresolvedOperands();
00557       if (!hasUnresolvedOperands())
00558         resolve();
00559     }
00560 
00561     return;
00562   }
00563 
00564   // Collision.
00565   if (!isResolved()) {
00566     // Still unresolved, so RAUW.
00567     InRAUW = true;
00568     ReplaceableUses->replaceAllUsesWith(*I);
00569     delete this;
00570     return;
00571   }
00572 
00573   // Store in non-uniqued form if this node has already been resolved.
00574   setHash(0);
00575   storeDistinctInContext();
00576 }
00577 
00578 MDNode *MDNode::getMDNode(LLVMContext &Context, ArrayRef<Metadata *> MDs,
00579                           bool Insert) {
00580   auto &Store = Context.pImpl->MDNodeSet;
00581 
00582   GenericMDNodeInfo::KeyTy Key(MDs);
00583   auto I = Store.find_as(Key);
00584   if (I != Store.end())
00585     return *I;
00586   if (!Insert)
00587     return nullptr;
00588 
00589   // Coallocate space for the node and Operands together, then placement new.
00590   GenericMDNode *N = new (MDs.size()) GenericMDNode(Context, MDs);
00591   N->setHash(Key.Hash);
00592   Store.insert(N);
00593   return N;
00594 }
00595 
00596 MDNodeFwdDecl *MDNode::getTemporary(LLVMContext &Context,
00597                                     ArrayRef<Metadata *> MDs) {
00598   MDNodeFwdDecl *N = new (MDs.size()) MDNodeFwdDecl(Context, MDs);
00599   LeakDetector::addGarbageObject(N);
00600   return N;
00601 }
00602 
00603 void MDNode::deleteTemporary(MDNode *N) {
00604   assert(isa<MDNodeFwdDecl>(N) && "Expected forward declaration");
00605   LeakDetector::removeGarbageObject(N);
00606   delete cast<MDNodeFwdDecl>(N);
00607 }
00608 
00609 void MDNode::storeDistinctInContext() {
00610   assert(!IsDistinctInContext && "Expected newly distinct metadata");
00611   IsDistinctInContext = true;
00612   auto *G = cast<GenericMDNode>(this);
00613   G->setHash(0);
00614   getContext().pImpl->NonUniquedMDNodes.insert(G);
00615 }
00616 
00617 // Replace value from this node's operand list.
00618 void MDNode::replaceOperandWith(unsigned I, Metadata *New) {
00619   if (getOperand(I) == New)
00620     return;
00621 
00622   if (auto *N = dyn_cast<GenericMDNode>(this)) {
00623     N->handleChangedOperand(mutable_begin() + I, New);
00624     return;
00625   }
00626 
00627   assert(isa<MDNodeFwdDecl>(this) && "Expected an MDNode");
00628   setOperand(I, New);
00629 }
00630 
00631 void MDNode::setOperand(unsigned I, Metadata *New) {
00632   assert(I < NumOperands);
00633   if (isStoredDistinctInContext() || isa<MDNodeFwdDecl>(this))
00634     // No need for a callback, this isn't uniqued.
00635     mutable_begin()[I].reset(New, nullptr);
00636   else
00637     mutable_begin()[I].reset(New, this);
00638 }
00639 
00640 /// \brief Get a node, or a self-reference that looks like it.
00641 ///
00642 /// Special handling for finding self-references, for use by \a
00643 /// MDNode::concatenate() and \a MDNode::intersect() to maintain behaviour from
00644 /// when self-referencing nodes were still uniqued.  If the first operand has
00645 /// the same operands as \c Ops, return the first operand instead.
00646 static MDNode *getOrSelfReference(LLVMContext &Context,
00647                                   ArrayRef<Metadata *> Ops) {
00648   if (!Ops.empty())
00649     if (MDNode *N = dyn_cast_or_null<MDNode>(Ops[0]))
00650       if (N->getNumOperands() == Ops.size() && N == N->getOperand(0)) {
00651         for (unsigned I = 1, E = Ops.size(); I != E; ++I)
00652           if (Ops[I] != N->getOperand(I))
00653             return MDNode::get(Context, Ops);
00654         return N;
00655       }
00656 
00657   return MDNode::get(Context, Ops);
00658 }
00659 
00660 MDNode *MDNode::concatenate(MDNode *A, MDNode *B) {
00661   if (!A)
00662     return B;
00663   if (!B)
00664     return A;
00665 
00666   SmallVector<Metadata *, 4> MDs(A->getNumOperands() + B->getNumOperands());
00667 
00668   unsigned j = 0;
00669   for (unsigned i = 0, ie = A->getNumOperands(); i != ie; ++i)
00670     MDs[j++] = A->getOperand(i);
00671   for (unsigned i = 0, ie = B->getNumOperands(); i != ie; ++i)
00672     MDs[j++] = B->getOperand(i);
00673 
00674   // FIXME: This preserves long-standing behaviour, but is it really the right
00675   // behaviour?  Or was that an unintended side-effect of node uniquing?
00676   return getOrSelfReference(A->getContext(), MDs);
00677 }
00678 
00679 MDNode *MDNode::intersect(MDNode *A, MDNode *B) {
00680   if (!A || !B)
00681     return nullptr;
00682 
00683   SmallVector<Metadata *, 4> MDs;
00684   for (unsigned i = 0, ie = A->getNumOperands(); i != ie; ++i) {
00685     Metadata *MD = A->getOperand(i);
00686     for (unsigned j = 0, je = B->getNumOperands(); j != je; ++j)
00687       if (MD == B->getOperand(j)) {
00688         MDs.push_back(MD);
00689         break;
00690       }
00691   }
00692 
00693   // FIXME: This preserves long-standing behaviour, but is it really the right
00694   // behaviour?  Or was that an unintended side-effect of node uniquing?
00695   return getOrSelfReference(A->getContext(), MDs);
00696 }
00697 
00698 MDNode *MDNode::getMostGenericFPMath(MDNode *A, MDNode *B) {
00699   if (!A || !B)
00700     return nullptr;
00701 
00702   APFloat AVal = mdconst::extract<ConstantFP>(A->getOperand(0))->getValueAPF();
00703   APFloat BVal = mdconst::extract<ConstantFP>(B->getOperand(0))->getValueAPF();
00704   if (AVal.compare(BVal) == APFloat::cmpLessThan)
00705     return A;
00706   return B;
00707 }
00708 
00709 static bool isContiguous(const ConstantRange &A, const ConstantRange &B) {
00710   return A.getUpper() == B.getLower() || A.getLower() == B.getUpper();
00711 }
00712 
00713 static bool canBeMerged(const ConstantRange &A, const ConstantRange &B) {
00714   return !A.intersectWith(B).isEmptySet() || isContiguous(A, B);
00715 }
00716 
00717 static bool tryMergeRange(SmallVectorImpl<ConstantInt *> &EndPoints,
00718                           ConstantInt *Low, ConstantInt *High) {
00719   ConstantRange NewRange(Low->getValue(), High->getValue());
00720   unsigned Size = EndPoints.size();
00721   APInt LB = EndPoints[Size - 2]->getValue();
00722   APInt LE = EndPoints[Size - 1]->getValue();
00723   ConstantRange LastRange(LB, LE);
00724   if (canBeMerged(NewRange, LastRange)) {
00725     ConstantRange Union = LastRange.unionWith(NewRange);
00726     Type *Ty = High->getType();
00727     EndPoints[Size - 2] =
00728         cast<ConstantInt>(ConstantInt::get(Ty, Union.getLower()));
00729     EndPoints[Size - 1] =
00730         cast<ConstantInt>(ConstantInt::get(Ty, Union.getUpper()));
00731     return true;
00732   }
00733   return false;
00734 }
00735 
00736 static void addRange(SmallVectorImpl<ConstantInt *> &EndPoints,
00737                      ConstantInt *Low, ConstantInt *High) {
00738   if (!EndPoints.empty())
00739     if (tryMergeRange(EndPoints, Low, High))
00740       return;
00741 
00742   EndPoints.push_back(Low);
00743   EndPoints.push_back(High);
00744 }
00745 
00746 MDNode *MDNode::getMostGenericRange(MDNode *A, MDNode *B) {
00747   // Given two ranges, we want to compute the union of the ranges. This
00748   // is slightly complitade by having to combine the intervals and merge
00749   // the ones that overlap.
00750 
00751   if (!A || !B)
00752     return nullptr;
00753 
00754   if (A == B)
00755     return A;
00756 
00757   // First, walk both lists in older of the lower boundary of each interval.
00758   // At each step, try to merge the new interval to the last one we adedd.
00759   SmallVector<ConstantInt *, 4> EndPoints;
00760   int AI = 0;
00761   int BI = 0;
00762   int AN = A->getNumOperands() / 2;
00763   int BN = B->getNumOperands() / 2;
00764   while (AI < AN && BI < BN) {
00765     ConstantInt *ALow = mdconst::extract<ConstantInt>(A->getOperand(2 * AI));
00766     ConstantInt *BLow = mdconst::extract<ConstantInt>(B->getOperand(2 * BI));
00767 
00768     if (ALow->getValue().slt(BLow->getValue())) {
00769       addRange(EndPoints, ALow,
00770                mdconst::extract<ConstantInt>(A->getOperand(2 * AI + 1)));
00771       ++AI;
00772     } else {
00773       addRange(EndPoints, BLow,
00774                mdconst::extract<ConstantInt>(B->getOperand(2 * BI + 1)));
00775       ++BI;
00776     }
00777   }
00778   while (AI < AN) {
00779     addRange(EndPoints, mdconst::extract<ConstantInt>(A->getOperand(2 * AI)),
00780              mdconst::extract<ConstantInt>(A->getOperand(2 * AI + 1)));
00781     ++AI;
00782   }
00783   while (BI < BN) {
00784     addRange(EndPoints, mdconst::extract<ConstantInt>(B->getOperand(2 * BI)),
00785              mdconst::extract<ConstantInt>(B->getOperand(2 * BI + 1)));
00786     ++BI;
00787   }
00788 
00789   // If we have more than 2 ranges (4 endpoints) we have to try to merge
00790   // the last and first ones.
00791   unsigned Size = EndPoints.size();
00792   if (Size > 4) {
00793     ConstantInt *FB = EndPoints[0];
00794     ConstantInt *FE = EndPoints[1];
00795     if (tryMergeRange(EndPoints, FB, FE)) {
00796       for (unsigned i = 0; i < Size - 2; ++i) {
00797         EndPoints[i] = EndPoints[i + 2];
00798       }
00799       EndPoints.resize(Size - 2);
00800     }
00801   }
00802 
00803   // If in the end we have a single range, it is possible that it is now the
00804   // full range. Just drop the metadata in that case.
00805   if (EndPoints.size() == 2) {
00806     ConstantRange Range(EndPoints[0]->getValue(), EndPoints[1]->getValue());
00807     if (Range.isFullSet())
00808       return nullptr;
00809   }
00810 
00811   SmallVector<Metadata *, 4> MDs;
00812   MDs.reserve(EndPoints.size());
00813   for (auto *I : EndPoints)
00814     MDs.push_back(ConstantAsMetadata::get(I));
00815   return MDNode::get(A->getContext(), MDs);
00816 }
00817 
00818 //===----------------------------------------------------------------------===//
00819 // NamedMDNode implementation.
00820 //
00821 
00822 static SmallVector<TrackingMDRef, 4> &getNMDOps(void *Operands) {
00823   return *(SmallVector<TrackingMDRef, 4> *)Operands;
00824 }
00825 
00826 NamedMDNode::NamedMDNode(const Twine &N)
00827     : Name(N.str()), Parent(nullptr),
00828       Operands(new SmallVector<TrackingMDRef, 4>()) {}
00829 
00830 NamedMDNode::~NamedMDNode() {
00831   dropAllReferences();
00832   delete &getNMDOps(Operands);
00833 }
00834 
00835 unsigned NamedMDNode::getNumOperands() const {
00836   return (unsigned)getNMDOps(Operands).size();
00837 }
00838 
00839 MDNode *NamedMDNode::getOperand(unsigned i) const {
00840   assert(i < getNumOperands() && "Invalid Operand number!");
00841   auto *N = getNMDOps(Operands)[i].get();
00842   return cast_or_null<MDNode>(N);
00843 }
00844 
00845 void NamedMDNode::addOperand(MDNode *M) { getNMDOps(Operands).emplace_back(M); }
00846 
00847 void NamedMDNode::eraseFromParent() {
00848   getParent()->eraseNamedMetadata(this);
00849 }
00850 
00851 void NamedMDNode::dropAllReferences() {
00852   getNMDOps(Operands).clear();
00853 }
00854 
00855 StringRef NamedMDNode::getName() const {
00856   return StringRef(Name);
00857 }
00858 
00859 //===----------------------------------------------------------------------===//
00860 // Instruction Metadata method implementations.
00861 //
00862 
00863 void Instruction::setMetadata(StringRef Kind, MDNode *Node) {
00864   if (!Node && !hasMetadata())
00865     return;
00866   setMetadata(getContext().getMDKindID(Kind), Node);
00867 }
00868 
00869 MDNode *Instruction::getMetadataImpl(StringRef Kind) const {
00870   return getMetadataImpl(getContext().getMDKindID(Kind));
00871 }
00872 
00873 void Instruction::dropUnknownMetadata(ArrayRef<unsigned> KnownIDs) {
00874   SmallSet<unsigned, 5> KnownSet;
00875   KnownSet.insert(KnownIDs.begin(), KnownIDs.end());
00876 
00877   // Drop debug if needed
00878   if (KnownSet.erase(LLVMContext::MD_dbg))
00879     DbgLoc = DebugLoc();
00880 
00881   if (!hasMetadataHashEntry())
00882     return; // Nothing to remove!
00883 
00884   DenseMap<const Instruction *, LLVMContextImpl::MDMapTy> &MetadataStore =
00885       getContext().pImpl->MetadataStore;
00886 
00887   if (KnownSet.empty()) {
00888     // Just drop our entry at the store.
00889     MetadataStore.erase(this);
00890     setHasMetadataHashEntry(false);
00891     return;
00892   }
00893 
00894   LLVMContextImpl::MDMapTy &Info = MetadataStore[this];
00895   unsigned I;
00896   unsigned E;
00897   // Walk the array and drop any metadata we don't know.
00898   for (I = 0, E = Info.size(); I != E;) {
00899     if (KnownSet.count(Info[I].first)) {
00900       ++I;
00901       continue;
00902     }
00903 
00904     Info[I] = std::move(Info.back());
00905     Info.pop_back();
00906     --E;
00907   }
00908   assert(E == Info.size());
00909 
00910   if (E == 0) {
00911     // Drop our entry at the store.
00912     MetadataStore.erase(this);
00913     setHasMetadataHashEntry(false);
00914   }
00915 }
00916 
00917 /// setMetadata - Set the metadata of of the specified kind to the specified
00918 /// node.  This updates/replaces metadata if already present, or removes it if
00919 /// Node is null.
00920 void Instruction::setMetadata(unsigned KindID, MDNode *Node) {
00921   if (!Node && !hasMetadata())
00922     return;
00923 
00924   // Handle 'dbg' as a special case since it is not stored in the hash table.
00925   if (KindID == LLVMContext::MD_dbg) {
00926     DbgLoc = DebugLoc::getFromDILocation(Node);
00927     return;
00928   }
00929   
00930   // Handle the case when we're adding/updating metadata on an instruction.
00931   if (Node) {
00932     LLVMContextImpl::MDMapTy &Info = getContext().pImpl->MetadataStore[this];
00933     assert(!Info.empty() == hasMetadataHashEntry() &&
00934            "HasMetadata bit is wonked");
00935     if (Info.empty()) {
00936       setHasMetadataHashEntry(true);
00937     } else {
00938       // Handle replacement of an existing value.
00939       for (auto &P : Info)
00940         if (P.first == KindID) {
00941           P.second.reset(Node);
00942           return;
00943         }
00944     }
00945 
00946     // No replacement, just add it to the list.
00947     Info.emplace_back(std::piecewise_construct, std::make_tuple(KindID),
00948                       std::make_tuple(Node));
00949     return;
00950   }
00951 
00952   // Otherwise, we're removing metadata from an instruction.
00953   assert((hasMetadataHashEntry() ==
00954           (getContext().pImpl->MetadataStore.count(this) > 0)) &&
00955          "HasMetadata bit out of date!");
00956   if (!hasMetadataHashEntry())
00957     return;  // Nothing to remove!
00958   LLVMContextImpl::MDMapTy &Info = getContext().pImpl->MetadataStore[this];
00959 
00960   // Common case is removing the only entry.
00961   if (Info.size() == 1 && Info[0].first == KindID) {
00962     getContext().pImpl->MetadataStore.erase(this);
00963     setHasMetadataHashEntry(false);
00964     return;
00965   }
00966 
00967   // Handle removal of an existing value.
00968   for (unsigned i = 0, e = Info.size(); i != e; ++i)
00969     if (Info[i].first == KindID) {
00970       Info[i] = std::move(Info.back());
00971       Info.pop_back();
00972       assert(!Info.empty() && "Removing last entry should be handled above");
00973       return;
00974     }
00975   // Otherwise, removing an entry that doesn't exist on the instruction.
00976 }
00977 
00978 void Instruction::setAAMetadata(const AAMDNodes &N) {
00979   setMetadata(LLVMContext::MD_tbaa, N.TBAA);
00980   setMetadata(LLVMContext::MD_alias_scope, N.Scope);
00981   setMetadata(LLVMContext::MD_noalias, N.NoAlias);
00982 }
00983 
00984 MDNode *Instruction::getMetadataImpl(unsigned KindID) const {
00985   // Handle 'dbg' as a special case since it is not stored in the hash table.
00986   if (KindID == LLVMContext::MD_dbg)
00987     return DbgLoc.getAsMDNode();
00988 
00989   if (!hasMetadataHashEntry()) return nullptr;
00990   
00991   LLVMContextImpl::MDMapTy &Info = getContext().pImpl->MetadataStore[this];
00992   assert(!Info.empty() && "bit out of sync with hash table");
00993 
00994   for (const auto &I : Info)
00995     if (I.first == KindID)
00996       return I.second;
00997   return nullptr;
00998 }
00999 
01000 void Instruction::getAllMetadataImpl(
01001     SmallVectorImpl<std::pair<unsigned, MDNode *>> &Result) const {
01002   Result.clear();
01003   
01004   // Handle 'dbg' as a special case since it is not stored in the hash table.
01005   if (!DbgLoc.isUnknown()) {
01006     Result.push_back(
01007         std::make_pair((unsigned)LLVMContext::MD_dbg, DbgLoc.getAsMDNode()));
01008     if (!hasMetadataHashEntry()) return;
01009   }
01010   
01011   assert(hasMetadataHashEntry() &&
01012          getContext().pImpl->MetadataStore.count(this) &&
01013          "Shouldn't have called this");
01014   const LLVMContextImpl::MDMapTy &Info =
01015     getContext().pImpl->MetadataStore.find(this)->second;
01016   assert(!Info.empty() && "Shouldn't have called this");
01017 
01018   Result.reserve(Result.size() + Info.size());
01019   for (auto &I : Info)
01020     Result.push_back(std::make_pair(I.first, cast<MDNode>(I.second.get())));
01021 
01022   // Sort the resulting array so it is stable.
01023   if (Result.size() > 1)
01024     array_pod_sort(Result.begin(), Result.end());
01025 }
01026 
01027 void Instruction::getAllMetadataOtherThanDebugLocImpl(
01028     SmallVectorImpl<std::pair<unsigned, MDNode *>> &Result) const {
01029   Result.clear();
01030   assert(hasMetadataHashEntry() &&
01031          getContext().pImpl->MetadataStore.count(this) &&
01032          "Shouldn't have called this");
01033   const LLVMContextImpl::MDMapTy &Info =
01034     getContext().pImpl->MetadataStore.find(this)->second;
01035   assert(!Info.empty() && "Shouldn't have called this");
01036   Result.reserve(Result.size() + Info.size());
01037   for (auto &I : Info)
01038     Result.push_back(std::make_pair(I.first, cast<MDNode>(I.second.get())));
01039 
01040   // Sort the resulting array so it is stable.
01041   if (Result.size() > 1)
01042     array_pod_sort(Result.begin(), Result.end());
01043 }
01044 
01045 /// clearMetadataHashEntries - Clear all hashtable-based metadata from
01046 /// this instruction.
01047 void Instruction::clearMetadataHashEntries() {
01048   assert(hasMetadataHashEntry() && "Caller should check");
01049   getContext().pImpl->MetadataStore.erase(this);
01050   setHasMetadataHashEntry(false);
01051 }