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 using namespace llvm;
00029 
00030 //===----------------------------------------------------------------------===//
00031 // MDString implementation.
00032 //
00033 
00034 void MDString::anchor() { }
00035 
00036 MDString::MDString(LLVMContext &C)
00037   : Value(Type::getMetadataTy(C), Value::MDStringVal) {}
00038 
00039 MDString *MDString::get(LLVMContext &Context, StringRef Str) {
00040   LLVMContextImpl *pImpl = Context.pImpl;
00041   StringMapEntry<Value*> &Entry =
00042     pImpl->MDStringCache.GetOrCreateValue(Str);
00043   Value *&S = Entry.getValue();
00044   if (!S) S = new MDString(Context);
00045   S->setValueName(&Entry);
00046   return cast<MDString>(S);
00047 }
00048 
00049 //===----------------------------------------------------------------------===//
00050 // MDNodeOperand implementation.
00051 //
00052 
00053 // Use CallbackVH to hold MDNode operands.
00054 namespace llvm {
00055 class MDNodeOperand : public CallbackVH {
00056   MDNode *getParent() {
00057     MDNodeOperand *Cur = this;
00058 
00059     while (Cur->getValPtrInt() != 1)
00060       --Cur;
00061 
00062     assert(Cur->getValPtrInt() == 1 &&
00063            "Couldn't find the beginning of the operand list!");
00064     return reinterpret_cast<MDNode*>(Cur) - 1;
00065   }
00066 
00067 public:
00068   MDNodeOperand(Value *V) : CallbackVH(V) {}
00069   virtual ~MDNodeOperand();
00070 
00071   void set(Value *V) {
00072     unsigned IsFirst = this->getValPtrInt();
00073     this->setValPtr(V);
00074     this->setAsFirstOperand(IsFirst);
00075   }
00076 
00077   /// setAsFirstOperand - Accessor method to mark the operand as the first in
00078   /// the list.
00079   void setAsFirstOperand(unsigned V) { this->setValPtrInt(V); }
00080 
00081   void deleted() override;
00082   void allUsesReplacedWith(Value *NV) override;
00083 };
00084 } // end namespace llvm.
00085 
00086 // Provide out-of-line definition to prevent weak vtable.
00087 MDNodeOperand::~MDNodeOperand() {}
00088 
00089 void MDNodeOperand::deleted() {
00090   getParent()->replaceOperand(this, nullptr);
00091 }
00092 
00093 void MDNodeOperand::allUsesReplacedWith(Value *NV) {
00094   getParent()->replaceOperand(this, NV);
00095 }
00096 
00097 //===----------------------------------------------------------------------===//
00098 // MDNode implementation.
00099 //
00100 
00101 /// getOperandPtr - Helper function to get the MDNodeOperand's coallocated on
00102 /// the end of the MDNode.
00103 static MDNodeOperand *getOperandPtr(MDNode *N, unsigned Op) {
00104   // Use <= instead of < to permit a one-past-the-end address.
00105   assert(Op <= N->getNumOperands() && "Invalid operand number");
00106   return reinterpret_cast<MDNodeOperand*>(N + 1) + Op;
00107 }
00108 
00109 void MDNode::replaceOperandWith(unsigned i, Value *Val) {
00110   MDNodeOperand *Op = getOperandPtr(this, i);
00111   replaceOperand(Op, Val);
00112 }
00113 
00114 MDNode::MDNode(LLVMContext &C, ArrayRef<Value*> Vals, bool isFunctionLocal)
00115 : Value(Type::getMetadataTy(C), Value::MDNodeVal) {
00116   NumOperands = Vals.size();
00117 
00118   if (isFunctionLocal)
00119     setValueSubclassData(getSubclassDataFromValue() | FunctionLocalBit);
00120 
00121   // Initialize the operand list, which is co-allocated on the end of the node.
00122   unsigned i = 0;
00123   for (MDNodeOperand *Op = getOperandPtr(this, 0), *E = Op+NumOperands;
00124        Op != E; ++Op, ++i) {
00125     new (Op) MDNodeOperand(Vals[i]);
00126 
00127     // Mark the first MDNodeOperand as being the first in the list of operands.
00128     if (i == 0)
00129       Op->setAsFirstOperand(1);
00130   }
00131 }
00132 
00133 /// ~MDNode - Destroy MDNode.
00134 MDNode::~MDNode() {
00135   assert((getSubclassDataFromValue() & DestroyFlag) != 0 &&
00136          "Not being destroyed through destroy()?");
00137   LLVMContextImpl *pImpl = getType()->getContext().pImpl;
00138   if (isNotUniqued()) {
00139     pImpl->NonUniquedMDNodes.erase(this);
00140   } else {
00141     pImpl->MDNodeSet.RemoveNode(this);
00142   }
00143 
00144   // Destroy the operands.
00145   for (MDNodeOperand *Op = getOperandPtr(this, 0), *E = Op+NumOperands;
00146        Op != E; ++Op)
00147     Op->~MDNodeOperand();
00148 }
00149 
00150 static const Function *getFunctionForValue(Value *V) {
00151   if (!V) return nullptr;
00152   if (Instruction *I = dyn_cast<Instruction>(V)) {
00153     BasicBlock *BB = I->getParent();
00154     return BB ? BB->getParent() : nullptr;
00155   }
00156   if (Argument *A = dyn_cast<Argument>(V))
00157     return A->getParent();
00158   if (BasicBlock *BB = dyn_cast<BasicBlock>(V))
00159     return BB->getParent();
00160   if (MDNode *MD = dyn_cast<MDNode>(V))
00161     return MD->getFunction();
00162   return nullptr;
00163 }
00164 
00165 #ifndef NDEBUG
00166 static const Function *assertLocalFunction(const MDNode *N) {
00167   if (!N->isFunctionLocal()) return nullptr;
00168 
00169   // FIXME: This does not handle cyclic function local metadata.
00170   const Function *F = nullptr, *NewF = nullptr;
00171   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
00172     if (Value *V = N->getOperand(i)) {
00173       if (MDNode *MD = dyn_cast<MDNode>(V))
00174         NewF = assertLocalFunction(MD);
00175       else
00176         NewF = getFunctionForValue(V);
00177     }
00178     if (!F)
00179       F = NewF;
00180     else
00181       assert((NewF == nullptr || F == NewF) &&
00182              "inconsistent function-local metadata");
00183   }
00184   return F;
00185 }
00186 #endif
00187 
00188 // getFunction - If this metadata is function-local and recursively has a
00189 // function-local operand, return the first such operand's parent function.
00190 // Otherwise, return null. getFunction() should not be used for performance-
00191 // critical code because it recursively visits all the MDNode's operands.  
00192 const Function *MDNode::getFunction() const {
00193 #ifndef NDEBUG
00194   return assertLocalFunction(this);
00195 #else
00196   if (!isFunctionLocal()) return nullptr;
00197   for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
00198     if (const Function *F = getFunctionForValue(getOperand(i)))
00199       return F;
00200   return nullptr;
00201 #endif
00202 }
00203 
00204 // destroy - Delete this node.  Only when there are no uses.
00205 void MDNode::destroy() {
00206   setValueSubclassData(getSubclassDataFromValue() | DestroyFlag);
00207   // Placement delete, then free the memory.
00208   this->~MDNode();
00209   free(this);
00210 }
00211 
00212 /// isFunctionLocalValue - Return true if this is a value that would require a
00213 /// function-local MDNode.
00214 static bool isFunctionLocalValue(Value *V) {
00215   return isa<Instruction>(V) || isa<Argument>(V) || isa<BasicBlock>(V) ||
00216          (isa<MDNode>(V) && cast<MDNode>(V)->isFunctionLocal());
00217 }
00218 
00219 MDNode *MDNode::getMDNode(LLVMContext &Context, ArrayRef<Value*> Vals,
00220                           FunctionLocalness FL, bool Insert) {
00221   LLVMContextImpl *pImpl = Context.pImpl;
00222 
00223   // Add all the operand pointers. Note that we don't have to add the
00224   // isFunctionLocal bit because that's implied by the operands.
00225   // Note that if the operands are later nulled out, the node will be
00226   // removed from the uniquing map.
00227   FoldingSetNodeID ID;
00228   for (Value *V : Vals)
00229     ID.AddPointer(V);
00230 
00231   void *InsertPoint;
00232   MDNode *N = pImpl->MDNodeSet.FindNodeOrInsertPos(ID, InsertPoint);
00233 
00234   if (N || !Insert)
00235     return N;
00236 
00237   bool isFunctionLocal = false;
00238   switch (FL) {
00239   case FL_Unknown:
00240     for (Value *V : Vals) {
00241       if (!V) continue;
00242       if (isFunctionLocalValue(V)) {
00243         isFunctionLocal = true;
00244         break;
00245       }
00246     }
00247     break;
00248   case FL_No:
00249     isFunctionLocal = false;
00250     break;
00251   case FL_Yes:
00252     isFunctionLocal = true;
00253     break;
00254   }
00255 
00256   // Coallocate space for the node and Operands together, then placement new.
00257   void *Ptr = malloc(sizeof(MDNode) + Vals.size() * sizeof(MDNodeOperand));
00258   N = new (Ptr) MDNode(Context, Vals, isFunctionLocal);
00259 
00260   // Cache the operand hash.
00261   N->Hash = ID.ComputeHash();
00262 
00263   // InsertPoint will have been set by the FindNodeOrInsertPos call.
00264   pImpl->MDNodeSet.InsertNode(N, InsertPoint);
00265 
00266   return N;
00267 }
00268 
00269 MDNode *MDNode::get(LLVMContext &Context, ArrayRef<Value*> Vals) {
00270   return getMDNode(Context, Vals, FL_Unknown);
00271 }
00272 
00273 MDNode *MDNode::getWhenValsUnresolved(LLVMContext &Context,
00274                                       ArrayRef<Value*> Vals,
00275                                       bool isFunctionLocal) {
00276   return getMDNode(Context, Vals, isFunctionLocal ? FL_Yes : FL_No);
00277 }
00278 
00279 MDNode *MDNode::getIfExists(LLVMContext &Context, ArrayRef<Value*> Vals) {
00280   return getMDNode(Context, Vals, FL_Unknown, false);
00281 }
00282 
00283 MDNode *MDNode::getTemporary(LLVMContext &Context, ArrayRef<Value*> Vals) {
00284   MDNode *N =
00285     (MDNode *)malloc(sizeof(MDNode) + Vals.size() * sizeof(MDNodeOperand));
00286   N = new (N) MDNode(Context, Vals, FL_No);
00287   N->setValueSubclassData(N->getSubclassDataFromValue() |
00288                           NotUniquedBit);
00289   LeakDetector::addGarbageObject(N);
00290   return N;
00291 }
00292 
00293 void MDNode::deleteTemporary(MDNode *N) {
00294   assert(N->use_empty() && "Temporary MDNode has uses!");
00295   assert(!N->getContext().pImpl->MDNodeSet.RemoveNode(N) &&
00296          "Deleting a non-temporary uniqued node!");
00297   assert(!N->getContext().pImpl->NonUniquedMDNodes.erase(N) &&
00298          "Deleting a non-temporary non-uniqued node!");
00299   assert((N->getSubclassDataFromValue() & NotUniquedBit) &&
00300          "Temporary MDNode does not have NotUniquedBit set!");
00301   assert((N->getSubclassDataFromValue() & DestroyFlag) == 0 &&
00302          "Temporary MDNode has DestroyFlag set!");
00303   LeakDetector::removeGarbageObject(N);
00304   N->destroy();
00305 }
00306 
00307 /// getOperand - Return specified operand.
00308 Value *MDNode::getOperand(unsigned i) const {
00309   assert(i < getNumOperands() && "Invalid operand number");
00310   return *getOperandPtr(const_cast<MDNode*>(this), i);
00311 }
00312 
00313 void MDNode::Profile(FoldingSetNodeID &ID) const {
00314   // Add all the operand pointers. Note that we don't have to add the
00315   // isFunctionLocal bit because that's implied by the operands.
00316   // Note that if the operands are later nulled out, the node will be
00317   // removed from the uniquing map.
00318   for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
00319     ID.AddPointer(getOperand(i));
00320 }
00321 
00322 void MDNode::setIsNotUniqued() {
00323   setValueSubclassData(getSubclassDataFromValue() | NotUniquedBit);
00324   LLVMContextImpl *pImpl = getType()->getContext().pImpl;
00325   pImpl->NonUniquedMDNodes.insert(this);
00326 }
00327 
00328 // Replace value from this node's operand list.
00329 void MDNode::replaceOperand(MDNodeOperand *Op, Value *To) {
00330   Value *From = *Op;
00331 
00332   // If is possible that someone did GV->RAUW(inst), replacing a global variable
00333   // with an instruction or some other function-local object.  If this is a
00334   // non-function-local MDNode, it can't point to a function-local object.
00335   // Handle this case by implicitly dropping the MDNode reference to null.
00336   // Likewise if the MDNode is function-local but for a different function.
00337   if (To && isFunctionLocalValue(To)) {
00338     if (!isFunctionLocal())
00339       To = nullptr;
00340     else {
00341       const Function *F = getFunction();
00342       const Function *FV = getFunctionForValue(To);
00343       // Metadata can be function-local without having an associated function.
00344       // So only consider functions to have changed if non-null.
00345       if (F && FV && F != FV)
00346         To = nullptr;
00347     }
00348   }
00349   
00350   if (From == To)
00351     return;
00352 
00353   // Update the operand.
00354   Op->set(To);
00355 
00356   // If this node is already not being uniqued (because one of the operands
00357   // already went to null), then there is nothing else to do here.
00358   if (isNotUniqued()) return;
00359 
00360   LLVMContextImpl *pImpl = getType()->getContext().pImpl;
00361 
00362   // Remove "this" from the context map.  FoldingSet doesn't have to reprofile
00363   // this node to remove it, so we don't care what state the operands are in.
00364   pImpl->MDNodeSet.RemoveNode(this);
00365 
00366   // If we are dropping an argument to null, we choose to not unique the MDNode
00367   // anymore.  This commonly occurs during destruction, and uniquing these
00368   // brings little reuse.  Also, this means we don't need to include
00369   // isFunctionLocal bits in FoldingSetNodeIDs for MDNodes.
00370   if (!To) {
00371     setIsNotUniqued();
00372     return;
00373   }
00374 
00375   // Now that the node is out of the folding set, get ready to reinsert it.
00376   // First, check to see if another node with the same operands already exists
00377   // in the set.  If so, then this node is redundant.
00378   FoldingSetNodeID ID;
00379   Profile(ID);
00380   void *InsertPoint;
00381   if (MDNode *N = pImpl->MDNodeSet.FindNodeOrInsertPos(ID, InsertPoint)) {
00382     replaceAllUsesWith(N);
00383     destroy();
00384     return;
00385   }
00386 
00387   // Cache the operand hash.
00388   Hash = ID.ComputeHash();
00389   // InsertPoint will have been set by the FindNodeOrInsertPos call.
00390   pImpl->MDNodeSet.InsertNode(this, InsertPoint);
00391 
00392   // If this MDValue was previously function-local but no longer is, clear
00393   // its function-local flag.
00394   if (isFunctionLocal() && !isFunctionLocalValue(To)) {
00395     bool isStillFunctionLocal = false;
00396     for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
00397       Value *V = getOperand(i);
00398       if (!V) continue;
00399       if (isFunctionLocalValue(V)) {
00400         isStillFunctionLocal = true;
00401         break;
00402       }
00403     }
00404     if (!isStillFunctionLocal)
00405       setValueSubclassData(getSubclassDataFromValue() & ~FunctionLocalBit);
00406   }
00407 }
00408 
00409 MDNode *MDNode::getMostGenericFPMath(MDNode *A, MDNode *B) {
00410   if (!A || !B)
00411     return nullptr;
00412 
00413   APFloat AVal = cast<ConstantFP>(A->getOperand(0))->getValueAPF();
00414   APFloat BVal = cast<ConstantFP>(B->getOperand(0))->getValueAPF();
00415   if (AVal.compare(BVal) == APFloat::cmpLessThan)
00416     return A;
00417   return B;
00418 }
00419 
00420 static bool isContiguous(const ConstantRange &A, const ConstantRange &B) {
00421   return A.getUpper() == B.getLower() || A.getLower() == B.getUpper();
00422 }
00423 
00424 static bool canBeMerged(const ConstantRange &A, const ConstantRange &B) {
00425   return !A.intersectWith(B).isEmptySet() || isContiguous(A, B);
00426 }
00427 
00428 static bool tryMergeRange(SmallVectorImpl<Value *> &EndPoints, ConstantInt *Low,
00429                           ConstantInt *High) {
00430   ConstantRange NewRange(Low->getValue(), High->getValue());
00431   unsigned Size = EndPoints.size();
00432   APInt LB = cast<ConstantInt>(EndPoints[Size - 2])->getValue();
00433   APInt LE = cast<ConstantInt>(EndPoints[Size - 1])->getValue();
00434   ConstantRange LastRange(LB, LE);
00435   if (canBeMerged(NewRange, LastRange)) {
00436     ConstantRange Union = LastRange.unionWith(NewRange);
00437     Type *Ty = High->getType();
00438     EndPoints[Size - 2] = ConstantInt::get(Ty, Union.getLower());
00439     EndPoints[Size - 1] = ConstantInt::get(Ty, Union.getUpper());
00440     return true;
00441   }
00442   return false;
00443 }
00444 
00445 static void addRange(SmallVectorImpl<Value *> &EndPoints, ConstantInt *Low,
00446                      ConstantInt *High) {
00447   if (!EndPoints.empty())
00448     if (tryMergeRange(EndPoints, Low, High))
00449       return;
00450 
00451   EndPoints.push_back(Low);
00452   EndPoints.push_back(High);
00453 }
00454 
00455 MDNode *MDNode::getMostGenericRange(MDNode *A, MDNode *B) {
00456   // Given two ranges, we want to compute the union of the ranges. This
00457   // is slightly complitade by having to combine the intervals and merge
00458   // the ones that overlap.
00459 
00460   if (!A || !B)
00461     return nullptr;
00462 
00463   if (A == B)
00464     return A;
00465 
00466   // First, walk both lists in older of the lower boundary of each interval.
00467   // At each step, try to merge the new interval to the last one we adedd.
00468   SmallVector<Value*, 4> EndPoints;
00469   int AI = 0;
00470   int BI = 0;
00471   int AN = A->getNumOperands() / 2;
00472   int BN = B->getNumOperands() / 2;
00473   while (AI < AN && BI < BN) {
00474     ConstantInt *ALow = cast<ConstantInt>(A->getOperand(2 * AI));
00475     ConstantInt *BLow = cast<ConstantInt>(B->getOperand(2 * BI));
00476 
00477     if (ALow->getValue().slt(BLow->getValue())) {
00478       addRange(EndPoints, ALow, cast<ConstantInt>(A->getOperand(2 * AI + 1)));
00479       ++AI;
00480     } else {
00481       addRange(EndPoints, BLow, cast<ConstantInt>(B->getOperand(2 * BI + 1)));
00482       ++BI;
00483     }
00484   }
00485   while (AI < AN) {
00486     addRange(EndPoints, cast<ConstantInt>(A->getOperand(2 * AI)),
00487              cast<ConstantInt>(A->getOperand(2 * AI + 1)));
00488     ++AI;
00489   }
00490   while (BI < BN) {
00491     addRange(EndPoints, cast<ConstantInt>(B->getOperand(2 * BI)),
00492              cast<ConstantInt>(B->getOperand(2 * BI + 1)));
00493     ++BI;
00494   }
00495 
00496   // If we have more than 2 ranges (4 endpoints) we have to try to merge
00497   // the last and first ones.
00498   unsigned Size = EndPoints.size();
00499   if (Size > 4) {
00500     ConstantInt *FB = cast<ConstantInt>(EndPoints[0]);
00501     ConstantInt *FE = cast<ConstantInt>(EndPoints[1]);
00502     if (tryMergeRange(EndPoints, FB, FE)) {
00503       for (unsigned i = 0; i < Size - 2; ++i) {
00504         EndPoints[i] = EndPoints[i + 2];
00505       }
00506       EndPoints.resize(Size - 2);
00507     }
00508   }
00509 
00510   // If in the end we have a single range, it is possible that it is now the
00511   // full range. Just drop the metadata in that case.
00512   if (EndPoints.size() == 2) {
00513     ConstantRange Range(cast<ConstantInt>(EndPoints[0])->getValue(),
00514                         cast<ConstantInt>(EndPoints[1])->getValue());
00515     if (Range.isFullSet())
00516       return nullptr;
00517   }
00518 
00519   return MDNode::get(A->getContext(), EndPoints);
00520 }
00521 
00522 //===----------------------------------------------------------------------===//
00523 // NamedMDNode implementation.
00524 //
00525 
00526 static SmallVector<TrackingVH<MDNode>, 4> &getNMDOps(void *Operands) {
00527   return *(SmallVector<TrackingVH<MDNode>, 4>*)Operands;
00528 }
00529 
00530 NamedMDNode::NamedMDNode(const Twine &N)
00531   : Name(N.str()), Parent(nullptr),
00532     Operands(new SmallVector<TrackingVH<MDNode>, 4>()) {
00533 }
00534 
00535 NamedMDNode::~NamedMDNode() {
00536   dropAllReferences();
00537   delete &getNMDOps(Operands);
00538 }
00539 
00540 /// getNumOperands - Return number of NamedMDNode operands.
00541 unsigned NamedMDNode::getNumOperands() const {
00542   return (unsigned)getNMDOps(Operands).size();
00543 }
00544 
00545 /// getOperand - Return specified operand.
00546 MDNode *NamedMDNode::getOperand(unsigned i) const {
00547   assert(i < getNumOperands() && "Invalid Operand number!");
00548   return dyn_cast<MDNode>(&*getNMDOps(Operands)[i]);
00549 }
00550 
00551 /// addOperand - Add metadata Operand.
00552 void NamedMDNode::addOperand(MDNode *M) {
00553   assert(!M->isFunctionLocal() &&
00554          "NamedMDNode operands must not be function-local!");
00555   getNMDOps(Operands).push_back(TrackingVH<MDNode>(M));
00556 }
00557 
00558 /// eraseFromParent - Drop all references and remove the node from parent
00559 /// module.
00560 void NamedMDNode::eraseFromParent() {
00561   getParent()->eraseNamedMetadata(this);
00562 }
00563 
00564 /// dropAllReferences - Remove all uses and clear node vector.
00565 void NamedMDNode::dropAllReferences() {
00566   getNMDOps(Operands).clear();
00567 }
00568 
00569 /// getName - Return a constant reference to this named metadata's name.
00570 StringRef NamedMDNode::getName() const {
00571   return StringRef(Name);
00572 }
00573 
00574 //===----------------------------------------------------------------------===//
00575 // Instruction Metadata method implementations.
00576 //
00577 
00578 void Instruction::setMetadata(StringRef Kind, MDNode *Node) {
00579   if (!Node && !hasMetadata()) return;
00580   setMetadata(getContext().getMDKindID(Kind), Node);
00581 }
00582 
00583 MDNode *Instruction::getMetadataImpl(StringRef Kind) const {
00584   return getMetadataImpl(getContext().getMDKindID(Kind));
00585 }
00586 
00587 void Instruction::dropUnknownMetadata(ArrayRef<unsigned> KnownIDs) {
00588   SmallSet<unsigned, 5> KnownSet;
00589   KnownSet.insert(KnownIDs.begin(), KnownIDs.end());
00590 
00591   // Drop debug if needed
00592   if (KnownSet.erase(LLVMContext::MD_dbg))
00593     DbgLoc = DebugLoc();
00594 
00595   if (!hasMetadataHashEntry())
00596     return; // Nothing to remove!
00597 
00598   DenseMap<const Instruction *, LLVMContextImpl::MDMapTy> &MetadataStore =
00599       getContext().pImpl->MetadataStore;
00600 
00601   if (KnownSet.empty()) {
00602     // Just drop our entry at the store.
00603     MetadataStore.erase(this);
00604     setHasMetadataHashEntry(false);
00605     return;
00606   }
00607 
00608   LLVMContextImpl::MDMapTy &Info = MetadataStore[this];
00609   unsigned I;
00610   unsigned E;
00611   // Walk the array and drop any metadata we don't know.
00612   for (I = 0, E = Info.size(); I != E;) {
00613     if (KnownSet.count(Info[I].first)) {
00614       ++I;
00615       continue;
00616     }
00617 
00618     Info[I] = Info.back();
00619     Info.pop_back();
00620     --E;
00621   }
00622   assert(E == Info.size());
00623 
00624   if (E == 0) {
00625     // Drop our entry at the store.
00626     MetadataStore.erase(this);
00627     setHasMetadataHashEntry(false);
00628   }
00629 }
00630 
00631 /// setMetadata - Set the metadata of of the specified kind to the specified
00632 /// node.  This updates/replaces metadata if already present, or removes it if
00633 /// Node is null.
00634 void Instruction::setMetadata(unsigned KindID, MDNode *Node) {
00635   if (!Node && !hasMetadata()) return;
00636 
00637   // Handle 'dbg' as a special case since it is not stored in the hash table.
00638   if (KindID == LLVMContext::MD_dbg) {
00639     DbgLoc = DebugLoc::getFromDILocation(Node);
00640     return;
00641   }
00642   
00643   // Handle the case when we're adding/updating metadata on an instruction.
00644   if (Node) {
00645     LLVMContextImpl::MDMapTy &Info = getContext().pImpl->MetadataStore[this];
00646     assert(!Info.empty() == hasMetadataHashEntry() &&
00647            "HasMetadata bit is wonked");
00648     if (Info.empty()) {
00649       setHasMetadataHashEntry(true);
00650     } else {
00651       // Handle replacement of an existing value.
00652       for (auto &P : Info)
00653         if (P.first == KindID) {
00654           P.second = Node;
00655           return;
00656         }
00657     }
00658 
00659     // No replacement, just add it to the list.
00660     Info.push_back(std::make_pair(KindID, Node));
00661     return;
00662   }
00663 
00664   // Otherwise, we're removing metadata from an instruction.
00665   assert((hasMetadataHashEntry() ==
00666           getContext().pImpl->MetadataStore.count(this)) &&
00667          "HasMetadata bit out of date!");
00668   if (!hasMetadataHashEntry())
00669     return;  // Nothing to remove!
00670   LLVMContextImpl::MDMapTy &Info = getContext().pImpl->MetadataStore[this];
00671 
00672   // Common case is removing the only entry.
00673   if (Info.size() == 1 && Info[0].first == KindID) {
00674     getContext().pImpl->MetadataStore.erase(this);
00675     setHasMetadataHashEntry(false);
00676     return;
00677   }
00678 
00679   // Handle removal of an existing value.
00680   for (unsigned i = 0, e = Info.size(); i != e; ++i)
00681     if (Info[i].first == KindID) {
00682       Info[i] = Info.back();
00683       Info.pop_back();
00684       assert(!Info.empty() && "Removing last entry should be handled above");
00685       return;
00686     }
00687   // Otherwise, removing an entry that doesn't exist on the instruction.
00688 }
00689 
00690 MDNode *Instruction::getMetadataImpl(unsigned KindID) const {
00691   // Handle 'dbg' as a special case since it is not stored in the hash table.
00692   if (KindID == LLVMContext::MD_dbg)
00693     return DbgLoc.getAsMDNode(getContext());
00694   
00695   if (!hasMetadataHashEntry()) return nullptr;
00696   
00697   LLVMContextImpl::MDMapTy &Info = getContext().pImpl->MetadataStore[this];
00698   assert(!Info.empty() && "bit out of sync with hash table");
00699 
00700   for (const auto &I : Info)
00701     if (I.first == KindID)
00702       return I.second;
00703   return nullptr;
00704 }
00705 
00706 void Instruction::getAllMetadataImpl(SmallVectorImpl<std::pair<unsigned,
00707                                        MDNode*> > &Result) const {
00708   Result.clear();
00709   
00710   // Handle 'dbg' as a special case since it is not stored in the hash table.
00711   if (!DbgLoc.isUnknown()) {
00712     Result.push_back(std::make_pair((unsigned)LLVMContext::MD_dbg,
00713                                     DbgLoc.getAsMDNode(getContext())));
00714     if (!hasMetadataHashEntry()) return;
00715   }
00716   
00717   assert(hasMetadataHashEntry() &&
00718          getContext().pImpl->MetadataStore.count(this) &&
00719          "Shouldn't have called this");
00720   const LLVMContextImpl::MDMapTy &Info =
00721     getContext().pImpl->MetadataStore.find(this)->second;
00722   assert(!Info.empty() && "Shouldn't have called this");
00723 
00724   Result.append(Info.begin(), Info.end());
00725 
00726   // Sort the resulting array so it is stable.
00727   if (Result.size() > 1)
00728     array_pod_sort(Result.begin(), Result.end());
00729 }
00730 
00731 void Instruction::
00732 getAllMetadataOtherThanDebugLocImpl(SmallVectorImpl<std::pair<unsigned,
00733                                     MDNode*> > &Result) const {
00734   Result.clear();
00735   assert(hasMetadataHashEntry() &&
00736          getContext().pImpl->MetadataStore.count(this) &&
00737          "Shouldn't have called this");
00738   const LLVMContextImpl::MDMapTy &Info =
00739     getContext().pImpl->MetadataStore.find(this)->second;
00740   assert(!Info.empty() && "Shouldn't have called this");
00741   Result.append(Info.begin(), Info.end());
00742 
00743   // Sort the resulting array so it is stable.
00744   if (Result.size() > 1)
00745     array_pod_sort(Result.begin(), Result.end());
00746 }
00747 
00748 /// clearMetadataHashEntries - Clear all hashtable-based metadata from
00749 /// this instruction.
00750 void Instruction::clearMetadataHashEntries() {
00751   assert(hasMetadataHashEntry() && "Caller should check");
00752   getContext().pImpl->MetadataStore.erase(this);
00753   setHasMetadataHashEntry(false);
00754 }
00755