lib/IR/Metadata.cpp

   1 //===-- Metadata.cpp - Implement Metadata classes -------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the Metadata classes.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/IR/Metadata.h"
  15 #include "LLVMContextImpl.h"
  16 #include "SymbolTableListTraitsImpl.h"
  17 #include "llvm/ADT/DenseMap.h"
  18 #include "llvm/ADT/STLExtras.h"
  19 #include "llvm/ADT/SmallSet.h"
  20 #include "llvm/ADT/SmallString.h"
  21 #include "llvm/ADT/StringMap.h"
  22 #include "llvm/IR/ConstantRange.h"
  23 #include "llvm/IR/Instruction.h"
  24 #include "llvm/IR/LLVMContext.h"
  25 #include "llvm/IR/LeakDetector.h"
  26 #include "llvm/IR/Module.h"
  27 #include "llvm/IR/ValueHandle.h"
  28
  29 using namespace llvm;
  30
  31 Metadata::Metadata(LLVMContext &Context, unsigned ID)
  32     : Value(Type::getMetadataTy(Context), ID) {}
  33
  34 //===----------------------------------------------------------------------===//
  35 // MDString implementation.
  36 //
  37
  38 void MDString::anchor() { }
  39
  40 MDString *MDString::get(LLVMContext &Context, StringRef Str) {
  41   auto &Store = Context.pImpl->MDStringCache;
  42   auto I = Store.find(Str);
  43   if (I != Store.end())
  44     return &I->second;
  45
  46   auto *Entry =
  47       StringMapEntry<MDString>::Create(Str, Store.getAllocator(), Context);
  48   bool WasInserted = Store.insert(Entry);
  49   (void)WasInserted;
  50   assert(WasInserted && "Expected entry to be inserted");
  51   return &Entry->second;
  52 }
  53
  54 StringRef MDString::getString() const {
  55   return StringMapEntry<MDString>::GetStringMapEntryFromValue(*this).first();
  56 }
  57
  58 //===----------------------------------------------------------------------===//
  59 // MDNodeOperand implementation.
  60 //
  61
  62 // Use CallbackVH to hold MDNode operands.
  63 namespace llvm {
  64 class MDNodeOperand : public CallbackVH {
  65   MDNode *getParent() {
  66     MDNodeOperand *Cur = this;
  67
  68     while (Cur->getValPtrInt() != 1)
  69       ++Cur;
  70
  71     assert(Cur->getValPtrInt() == 1 &&
  72            "Couldn't find the end of the operand list!");
  73     return reinterpret_cast<MDNode *>(Cur + 1);
  74   }
  75
  76 public:
  77   MDNodeOperand() {}
  78   virtual ~MDNodeOperand();
  79
  80   void set(Value *V) {
  81     unsigned IsLast = this->getValPtrInt();
  82     this->setValPtr(V);
  83     this->setAsLastOperand(IsLast);
  84   }
  85
  86   /// \brief Accessor method to mark the operand as the first in the list.
  87   void setAsLastOperand(unsigned I) { this->setValPtrInt(I); }
  88
  89   void deleted() override;
  90   void allUsesReplacedWith(Value *NV) override;
  91 };
  92 } // end namespace llvm.
  93
  94 // Provide out-of-line definition to prevent weak vtable.
  95 MDNodeOperand::~MDNodeOperand() {}
  96
  97 void MDNodeOperand::deleted() {
  98   getParent()->replaceOperand(this, nullptr);
  99 }
 100
 101 void MDNodeOperand::allUsesReplacedWith(Value *NV) {
 102   getParent()->replaceOperand(this, NV);
 103 }
 104
 105 //===----------------------------------------------------------------------===//
 106 // MDNode implementation.
 107 //
 108
 109 /// \brief Get the MDNodeOperand's coallocated on the end of the MDNode.
 110 static MDNodeOperand *getOperandPtr(MDNode *N, unsigned Op) {
 111   // Use <= instead of < to permit a one-past-the-end address.
 112   assert(Op <= N->getNumOperands() && "Invalid operand number");
 113   return reinterpret_cast<MDNodeOperand *>(N) - N->getNumOperands() + Op;
 114 }
 115
 116 void MDNode::replaceOperandWith(unsigned i, Value *Val) {
 117   MDNodeOperand *Op = getOperandPtr(this, i);
 118   replaceOperand(Op, Val);
 119 }
 120
 121 void *MDNode::operator new(size_t Size, unsigned NumOps) {
 122   void *Ptr = ::operator new(Size + NumOps * sizeof(MDNodeOperand));
 123   MDNodeOperand *Op = static_cast<MDNodeOperand *>(Ptr);
 124   if (NumOps) {
 125     MDNodeOperand *Last = Op + NumOps;
 126     for (; Op != Last; ++Op)
 127       new (Op) MDNodeOperand();
 128     (Op - 1)->setAsLastOperand(1);
 129   }
 130   return Op;
 131 }
 132
 133 void MDNode::operator delete(void *Mem) {
 134   MDNode *N = static_cast<MDNode *>(Mem);
 135   MDNodeOperand *Op = static_cast<MDNodeOperand *>(Mem);
 136   for (unsigned I = 0, E = N->NumOperands; I != E; ++I)
 137     (--Op)->~MDNodeOperand();
 138   ::operator delete(Op);
 139 }
 140
 141 MDNode::MDNode(LLVMContext &C, unsigned ID, ArrayRef<Value *> Vals,
 142                bool isFunctionLocal)
 143     : Metadata(C, ID), Hash(0) {
 144   NumOperands = Vals.size();
 145
 146   if (isFunctionLocal)
 147     setValueSubclassData(getSubclassDataFromValue() | FunctionLocalBit);
 148
 149   // Initialize the operand list.
 150   unsigned i = 0;
 151   for (MDNodeOperand *Op = getOperandPtr(this, 0), *E = Op + NumOperands;
 152        Op != E; ++Op, ++i)
 153     Op->set(Vals[i]);
 154 }
 155
 156 GenericMDNode::~GenericMDNode() {
 157   LLVMContextImpl *pImpl = getType()->getContext().pImpl;
 158   if (isNotUniqued()) {
 159     pImpl->NonUniquedMDNodes.erase(this);
 160   } else {
 161     pImpl->MDNodeSet.erase(this);
 162   }
 163 }
 164
 165 void GenericMDNode::dropAllReferences() {
 166   for (MDNodeOperand *Op = getOperandPtr(this, 0), *E = Op + NumOperands;
 167        Op != E; ++Op)
 168     Op->set(nullptr);
 169 }
 170
 171 static const Function *getFunctionForValue(Value *V) {
 172   if (!V) return nullptr;
 173   if (Instruction *I = dyn_cast<Instruction>(V)) {
 174     BasicBlock *BB = I->getParent();
 175     return BB ? BB->getParent() : nullptr;
 176   }
 177   if (Argument *A = dyn_cast<Argument>(V))
 178     return A->getParent();
 179   if (BasicBlock *BB = dyn_cast<BasicBlock>(V))
 180     return BB->getParent();
 181   if (MDNode *MD = dyn_cast<MDNode>(V))
 182     return MD->getFunction();
 183   return nullptr;
 184 }
 185
 186 #ifndef NDEBUG
 187 static const Function *assertLocalFunction(const MDNode *N) {
 188   if (!N->isFunctionLocal()) return nullptr;
 189
 190   // FIXME: This does not handle cyclic function local metadata.
 191   const Function *F = nullptr, *NewF = nullptr;
 192   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
 193     if (Value *V = N->getOperand(i)) {
 194       if (MDNode *MD = dyn_cast<MDNode>(V))
 195         NewF = assertLocalFunction(MD);
 196       else
 197         NewF = getFunctionForValue(V);
 198     }
 199     if (!F)
 200       F = NewF;
 201     else
 202       assert((NewF == nullptr || F == NewF) &&
 203              "inconsistent function-local metadata");
 204   }
 205   return F;
 206 }
 207 #endif
 208
 209 // getFunction - If this metadata is function-local and recursively has a
 210 // function-local operand, return the first such operand's parent function.
 211 // Otherwise, return null. getFunction() should not be used for performance-
 212 // critical code because it recursively visits all the MDNode's operands.
 213 const Function *MDNode::getFunction() const {
 214 #ifndef NDEBUG
 215   return assertLocalFunction(this);
 216 #else
 217   if (!isFunctionLocal()) return nullptr;
 218   for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
 219     if (const Function *F = getFunctionForValue(getOperand(i)))
 220       return F;
 221   return nullptr;
 222 #endif
 223 }
 224
 225 /// \brief Check if the Value  would require a function-local MDNode.
 226 static bool isFunctionLocalValue(Value *V) {
 227   return isa<Instruction>(V) || isa<Argument>(V) || isa<BasicBlock>(V) ||
 228          (isa<MDNode>(V) && cast<MDNode>(V)->isFunctionLocal());
 229 }
 230
 231 MDNode *MDNode::getMDNode(LLVMContext &Context, ArrayRef<Value*> Vals,
 232                           FunctionLocalness FL, bool Insert) {
 233   auto &Store = Context.pImpl->MDNodeSet;
 234
 235   GenericMDNodeInfo::KeyTy Key(Vals);
 236   auto I = Store.find_as(Key);
 237   if (I != Store.end())
 238     return *I;
 239   if (!Insert)
 240     return nullptr;
 241
 242   bool isFunctionLocal = false;
 243   switch (FL) {
 244   case FL_Unknown:
 245     for (Value *V : Vals) {
 246       if (!V) continue;
 247       if (isFunctionLocalValue(V)) {
 248         isFunctionLocal = true;
 249         break;
 250       }
 251     }
 252     break;
 253   case FL_No:
 254     isFunctionLocal = false;
 255     break;
 256   case FL_Yes:
 257     isFunctionLocal = true;
 258     break;
 259   }
 260
 261   // Coallocate space for the node and Operands together, then placement new.
 262   GenericMDNode *N =
 263       new (Vals.size()) GenericMDNode(Context, Vals, isFunctionLocal);
 264
 265   N->Hash = Key.Hash;
 266   Store.insert(N);
 267   return N;
 268 }
 269
 270 MDNode *MDNode::get(LLVMContext &Context, ArrayRef<Value*> Vals) {
 271   return getMDNode(Context, Vals, FL_Unknown);
 272 }
 273
 274 MDNode *MDNode::getWhenValsUnresolved(LLVMContext &Context,
 275                                       ArrayRef<Value*> Vals,
 276                                       bool isFunctionLocal) {
 277   return getMDNode(Context, Vals, isFunctionLocal ? FL_Yes : FL_No);
 278 }
 279
 280 MDNode *MDNode::getIfExists(LLVMContext &Context, ArrayRef<Value*> Vals) {
 281   return getMDNode(Context, Vals, FL_Unknown, false);
 282 }
 283
 284 MDNode *MDNode::getTemporary(LLVMContext &Context, ArrayRef<Value*> Vals) {
 285   MDNode *N = new (Vals.size()) MDNodeFwdDecl(Context, Vals, FL_No);
 286   N->setValueSubclassData(N->getSubclassDataFromValue() | NotUniquedBit);
 287   LeakDetector::addGarbageObject(N);
 288   return N;
 289 }
 290
 291 void MDNode::deleteTemporary(MDNode *N) {
 292   assert(N->use_empty() && "Temporary MDNode has uses!");
 293   assert(isa<MDNodeFwdDecl>(N) && "Expected forward declaration");
 294   assert((N->getSubclassDataFromValue() & NotUniquedBit) &&
 295          "Temporary MDNode does not have NotUniquedBit set!");
 296   LeakDetector::removeGarbageObject(N);
 297   delete cast<MDNodeFwdDecl>(N);
 298 }
 299
 300 /// \brief Return specified operand.
 301 Value *MDNode::getOperand(unsigned i) const {
 302   assert(i < getNumOperands() && "Invalid operand number");
 303   return *getOperandPtr(const_cast<MDNode*>(this), i);
 304 }
 305
 306 void MDNode::setIsNotUniqued() {
 307   setValueSubclassData(getSubclassDataFromValue() | NotUniquedBit);
 308   LLVMContextImpl *pImpl = getType()->getContext().pImpl;
 309   auto *G = cast<GenericMDNode>(this);
 310   G->Hash = 0;
 311   pImpl->NonUniquedMDNodes.insert(G);
 312 }
 313
 314 // Replace value from this node's operand list.
 315 void MDNode::replaceOperand(MDNodeOperand *Op, Value *To) {
 316   Value *From = *Op;
 317
 318   // If is possible that someone did GV->RAUW(inst), replacing a global variable
 319   // with an instruction or some other function-local object.  If this is a
 320   // non-function-local MDNode, it can't point to a function-local object.
 321   // Handle this case by implicitly dropping the MDNode reference to null.
 322   // Likewise if the MDNode is function-local but for a different function.
 323   if (To && isFunctionLocalValue(To)) {
 324     if (!isFunctionLocal())
 325       To = nullptr;
 326     else {
 327       const Function *F = getFunction();
 328       const Function *FV = getFunctionForValue(To);
 329       // Metadata can be function-local without having an associated function.
 330       // So only consider functions to have changed if non-null.
 331       if (F && FV && F != FV)
 332         To = nullptr;
 333     }
 334   }
 335
 336   if (From == To)
 337     return;
 338
 339   // If this node is already not being uniqued (because one of the operands
 340   // already went to null), then there is nothing else to do here.
 341   if (isNotUniqued()) {
 342     Op->set(To);
 343     return;
 344   }
 345
 346   auto &Store = getContext().pImpl->MDNodeSet;
 347   auto *N = cast<GenericMDNode>(this);
 348
 349   // Remove "this" from the context map.
 350   Store.erase(N);
 351
 352   // Update the operand.
 353   Op->set(To);
 354
 355   // If we are dropping an argument to null, we choose to not unique the MDNode
 356   // anymore.  This commonly occurs during destruction, and uniquing these
 357   // brings little reuse.  Also, this means we don't need to include
 358   // isFunctionLocal bits in the hash for MDNodes.
 359   if (!To) {
 360     setIsNotUniqued();
 361     return;
 362   }
 363
 364   // Now that the node is out of the table, get ready to reinsert it.  First,
 365   // check to see if another node with the same operands already exists in the
 366   // set.  If so, then this node is redundant.
 367   SmallVector<Value *, 8> Vals;
 368   GenericMDNodeInfo::KeyTy Key(N, Vals);
 369   auto I = Store.find_as(Key);
 370   if (I != Store.end()) {
 371     N->replaceAllUsesWith(*I);
 372     delete N;
 373     return;
 374   }
 375
 376   N->Hash = Key.Hash;
 377   Store.insert(N);
 378
 379   // If this MDValue was previously function-local but no longer is, clear
 380   // its function-local flag.
 381   if (isFunctionLocal() && !isFunctionLocalValue(To)) {
 382     bool isStillFunctionLocal = false;
 383     for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
 384       Value *V = getOperand(i);
 385       if (!V) continue;
 386       if (isFunctionLocalValue(V)) {
 387         isStillFunctionLocal = true;
 388         break;
 389       }
 390     }
 391     if (!isStillFunctionLocal)
 392       setValueSubclassData(getSubclassDataFromValue() & ~FunctionLocalBit);
 393   }
 394 }
 395
 396 MDNode *MDNode::concatenate(MDNode *A, MDNode *B) {
 397   if (!A)
 398     return B;
 399   if (!B)
 400     return A;
 401
 402   SmallVector<Value *, 4> Vals(A->getNumOperands() +
 403                                B->getNumOperands());
 404
 405   unsigned j = 0;
 406   for (unsigned i = 0, ie = A->getNumOperands(); i != ie; ++i)
 407     Vals[j++] = A->getOperand(i);
 408   for (unsigned i = 0, ie = B->getNumOperands(); i != ie; ++i)
 409     Vals[j++] = B->getOperand(i);
 410
 411   return MDNode::get(A->getContext(), Vals);
 412 }
 413
 414 MDNode *MDNode::intersect(MDNode *A, MDNode *B) {
 415   if (!A || !B)
 416     return nullptr;
 417
 418   SmallVector<Value *, 4> Vals;
 419   for (unsigned i = 0, ie = A->getNumOperands(); i != ie; ++i) {
 420     Value *V = A->getOperand(i);
 421     for (unsigned j = 0, je = B->getNumOperands(); j != je; ++j)
 422       if (V == B->getOperand(j)) {
 423         Vals.push_back(V);
 424         break;
 425       }
 426   }
 427
 428   return MDNode::get(A->getContext(), Vals);
 429 }
 430
 431 MDNode *MDNode::getMostGenericFPMath(MDNode *A, MDNode *B) {
 432   if (!A || !B)
 433     return nullptr;
 434
 435   APFloat AVal = cast<ConstantFP>(A->getOperand(0))->getValueAPF();
 436   APFloat BVal = cast<ConstantFP>(B->getOperand(0))->getValueAPF();
 437   if (AVal.compare(BVal) == APFloat::cmpLessThan)
 438     return A;
 439   return B;
 440 }
 441
 442 static bool isContiguous(const ConstantRange &A, const ConstantRange &B) {
 443   return A.getUpper() == B.getLower() || A.getLower() == B.getUpper();
 444 }
 445
 446 static bool canBeMerged(const ConstantRange &A, const ConstantRange &B) {
 447   return !A.intersectWith(B).isEmptySet() || isContiguous(A, B);
 448 }
 449
 450 static bool tryMergeRange(SmallVectorImpl<Value *> &EndPoints, ConstantInt *Low,
 451                           ConstantInt *High) {
 452   ConstantRange NewRange(Low->getValue(), High->getValue());
 453   unsigned Size = EndPoints.size();
 454   APInt LB = cast<ConstantInt>(EndPoints[Size - 2])->getValue();
 455   APInt LE = cast<ConstantInt>(EndPoints[Size - 1])->getValue();
 456   ConstantRange LastRange(LB, LE);
 457   if (canBeMerged(NewRange, LastRange)) {
 458     ConstantRange Union = LastRange.unionWith(NewRange);
 459     Type *Ty = High->getType();
 460     EndPoints[Size - 2] = ConstantInt::get(Ty, Union.getLower());
 461     EndPoints[Size - 1] = ConstantInt::get(Ty, Union.getUpper());
 462     return true;
 463   }
 464   return false;
 465 }
 466
 467 static void addRange(SmallVectorImpl<Value *> &EndPoints, ConstantInt *Low,
 468                      ConstantInt *High) {
 469   if (!EndPoints.empty())
 470     if (tryMergeRange(EndPoints, Low, High))
 471       return;
 472
 473   EndPoints.push_back(Low);
 474   EndPoints.push_back(High);
 475 }
 476
 477 MDNode *MDNode::getMostGenericRange(MDNode *A, MDNode *B) {
 478   // Given two ranges, we want to compute the union of the ranges. This
 479   // is slightly complitade by having to combine the intervals and merge
 480   // the ones that overlap.
 481
 482   if (!A || !B)
 483     return nullptr;
 484
 485   if (A == B)
 486     return A;
 487
 488   // First, walk both lists in older of the lower boundary of each interval.
 489   // At each step, try to merge the new interval to the last one we adedd.
 490   SmallVector<Value*, 4> EndPoints;
 491   int AI = 0;
 492   int BI = 0;
 493   int AN = A->getNumOperands() / 2;
 494   int BN = B->getNumOperands() / 2;
 495   while (AI < AN && BI < BN) {
 496     ConstantInt *ALow = cast<ConstantInt>(A->getOperand(2 * AI));
 497     ConstantInt *BLow = cast<ConstantInt>(B->getOperand(2 * BI));
 498
 499     if (ALow->getValue().slt(BLow->getValue())) {
 500       addRange(EndPoints, ALow, cast<ConstantInt>(A->getOperand(2 * AI + 1)));
 501       ++AI;
 502     } else {
 503       addRange(EndPoints, BLow, cast<ConstantInt>(B->getOperand(2 * BI + 1)));
 504       ++BI;
 505     }
 506   }
 507   while (AI < AN) {
 508     addRange(EndPoints, cast<ConstantInt>(A->getOperand(2 * AI)),
 509              cast<ConstantInt>(A->getOperand(2 * AI + 1)));
 510     ++AI;
 511   }
 512   while (BI < BN) {
 513     addRange(EndPoints, cast<ConstantInt>(B->getOperand(2 * BI)),
 514              cast<ConstantInt>(B->getOperand(2 * BI + 1)));
 515     ++BI;
 516   }
 517
 518   // If we have more than 2 ranges (4 endpoints) we have to try to merge
 519   // the last and first ones.
 520   unsigned Size = EndPoints.size();
 521   if (Size > 4) {
 522     ConstantInt *FB = cast<ConstantInt>(EndPoints[0]);
 523     ConstantInt *FE = cast<ConstantInt>(EndPoints[1]);
 524     if (tryMergeRange(EndPoints, FB, FE)) {
 525       for (unsigned i = 0; i < Size - 2; ++i) {
 526         EndPoints[i] = EndPoints[i + 2];
 527       }
 528       EndPoints.resize(Size - 2);
 529     }
 530   }
 531
 532   // If in the end we have a single range, it is possible that it is now the
 533   // full range. Just drop the metadata in that case.
 534   if (EndPoints.size() == 2) {
 535     ConstantRange Range(cast<ConstantInt>(EndPoints[0])->getValue(),
 536                         cast<ConstantInt>(EndPoints[1])->getValue());
 537     if (Range.isFullSet())
 538       return nullptr;
 539   }
 540
 541   return MDNode::get(A->getContext(), EndPoints);
 542 }
 543
 544 //===----------------------------------------------------------------------===//
 545 // NamedMDNode implementation.
 546 //
 547
 548 static SmallVector<TrackingVH<MDNode>, 4> &getNMDOps(void *Operands) {
 549   return *(SmallVector<TrackingVH<MDNode>, 4> *)Operands;
 550 }
 551
 552 NamedMDNode::NamedMDNode(const Twine &N)
 553     : Name(N.str()), Parent(nullptr),
 554       Operands(new SmallVector<TrackingVH<MDNode>, 4>()) {}
 555
 556 NamedMDNode::~NamedMDNode() {
 557   dropAllReferences();
 558   delete &getNMDOps(Operands);
 559 }
 560
 561 unsigned NamedMDNode::getNumOperands() const {
 562   return (unsigned)getNMDOps(Operands).size();
 563 }
 564
 565 MDNode *NamedMDNode::getOperand(unsigned i) const {
 566   assert(i < getNumOperands() && "Invalid Operand number!");
 567   return &*getNMDOps(Operands)[i];
 568 }
 569
 570 void NamedMDNode::addOperand(MDNode *M) {
 571   assert(!M->isFunctionLocal() &&
 572          "NamedMDNode operands must not be function-local!");
 573   getNMDOps(Operands).push_back(TrackingVH<MDNode>(M));
 574 }
 575
 576 void NamedMDNode::eraseFromParent() {
 577   getParent()->eraseNamedMetadata(this);
 578 }
 579
 580 void NamedMDNode::dropAllReferences() {
 581   getNMDOps(Operands).clear();
 582 }
 583
 584 StringRef NamedMDNode::getName() const {
 585   return StringRef(Name);
 586 }
 587
 588 //===----------------------------------------------------------------------===//
 589 // Instruction Metadata method implementations.
 590 //
 591
 592 void Instruction::setMetadata(StringRef Kind, MDNode *Node) {
 593   if (!Node && !hasMetadata())
 594     return;
 595   setMetadata(getContext().getMDKindID(Kind), Node);
 596 }
 597
 598 MDNode *Instruction::getMetadataImpl(StringRef Kind) const {
 599   return getMetadataImpl(getContext().getMDKindID(Kind));
 600 }
 601
 602 void Instruction::dropUnknownMetadata(ArrayRef<unsigned> KnownIDs) {
 603   SmallSet<unsigned, 5> KnownSet;
 604   KnownSet.insert(KnownIDs.begin(), KnownIDs.end());
 605
 606   // Drop debug if needed
 607   if (KnownSet.erase(LLVMContext::MD_dbg))
 608     DbgLoc = DebugLoc();
 609
 610   if (!hasMetadataHashEntry())
 611     return; // Nothing to remove!
 612
 613   DenseMap<const Instruction *, LLVMContextImpl::MDMapTy> &MetadataStore =
 614       getContext().pImpl->MetadataStore;
 615
 616   if (KnownSet.empty()) {
 617     // Just drop our entry at the store.
 618     MetadataStore.erase(this);
 619     setHasMetadataHashEntry(false);
 620     return;
 621   }
 622
 623   LLVMContextImpl::MDMapTy &Info = MetadataStore[this];
 624   unsigned I;
 625   unsigned E;
 626   // Walk the array and drop any metadata we don't know.
 627   for (I = 0, E = Info.size(); I != E;) {
 628     if (KnownSet.count(Info[I].first)) {
 629       ++I;
 630       continue;
 631     }
 632
 633     Info[I] = Info.back();
 634     Info.pop_back();
 635     --E;
 636   }
 637   assert(E == Info.size());
 638
 639   if (E == 0) {
 640     // Drop our entry at the store.
 641     MetadataStore.erase(this);
 642     setHasMetadataHashEntry(false);
 643   }
 644 }
 645
 646 /// setMetadata - Set the metadata of of the specified kind to the specified
 647 /// node.  This updates/replaces metadata if already present, or removes it if
 648 /// Node is null.
 649 void Instruction::setMetadata(unsigned KindID, MDNode *Node) {
 650   if (!Node && !hasMetadata())
 651     return;
 652
 653   // Handle 'dbg' as a special case since it is not stored in the hash table.
 654   if (KindID == LLVMContext::MD_dbg) {
 655     DbgLoc = DebugLoc::getFromDILocation(Node);
 656     return;
 657   }
 658
 659   // Handle the case when we're adding/updating metadata on an instruction.
 660   if (Node) {
 661     LLVMContextImpl::MDMapTy &Info = getContext().pImpl->MetadataStore[this];
 662     assert(!Info.empty() == hasMetadataHashEntry() &&
 663            "HasMetadata bit is wonked");
 664     if (Info.empty()) {
 665       setHasMetadataHashEntry(true);
 666     } else {
 667       // Handle replacement of an existing value.
 668       for (auto &P : Info)
 669         if (P.first == KindID) {
 670           P.second = Node;
 671           return;
 672         }
 673     }
 674
 675     // No replacement, just add it to the list.
 676     Info.push_back(std::make_pair(KindID, Node));
 677     return;
 678   }
 679
 680   // Otherwise, we're removing metadata from an instruction.
 681   assert((hasMetadataHashEntry() ==
 682           (getContext().pImpl->MetadataStore.count(this) > 0)) &&
 683          "HasMetadata bit out of date!");
 684   if (!hasMetadataHashEntry())
 685     return;  // Nothing to remove!
 686   LLVMContextImpl::MDMapTy &Info = getContext().pImpl->MetadataStore[this];
 687
 688   // Common case is removing the only entry.
 689   if (Info.size() == 1 && Info[0].first == KindID) {
 690     getContext().pImpl->MetadataStore.erase(this);
 691     setHasMetadataHashEntry(false);
 692     return;
 693   }
 694
 695   // Handle removal of an existing value.
 696   for (unsigned i = 0, e = Info.size(); i != e; ++i)
 697     if (Info[i].first == KindID) {
 698       Info[i] = Info.back();
 699       Info.pop_back();
 700       assert(!Info.empty() && "Removing last entry should be handled above");
 701       return;
 702     }
 703   // Otherwise, removing an entry that doesn't exist on the instruction.
 704 }
 705
 706 void Instruction::setAAMetadata(const AAMDNodes &N) {
 707   setMetadata(LLVMContext::MD_tbaa, N.TBAA);
 708   setMetadata(LLVMContext::MD_alias_scope, N.Scope);
 709   setMetadata(LLVMContext::MD_noalias, N.NoAlias);
 710 }
 711
 712 MDNode *Instruction::getMetadataImpl(unsigned KindID) const {
 713   // Handle 'dbg' as a special case since it is not stored in the hash table.
 714   if (KindID == LLVMContext::MD_dbg)
 715     return DbgLoc.getAsMDNode(getContext());
 716
 717   if (!hasMetadataHashEntry()) return nullptr;
 718
 719   LLVMContextImpl::MDMapTy &Info = getContext().pImpl->MetadataStore[this];
 720   assert(!Info.empty() && "bit out of sync with hash table");
 721
 722   for (const auto &I : Info)
 723     if (I.first == KindID)
 724       return I.second;
 725   return nullptr;
 726 }
 727
 728 void Instruction::getAllMetadataImpl(
 729     SmallVectorImpl<std::pair<unsigned, MDNode *>> &Result) const {
 730   Result.clear();
 731
 732   // Handle 'dbg' as a special case since it is not stored in the hash table.
 733   if (!DbgLoc.isUnknown()) {
 734     Result.push_back(std::make_pair((unsigned)LLVMContext::MD_dbg,
 735                                     DbgLoc.getAsMDNode(getContext())));
 736     if (!hasMetadataHashEntry()) return;
 737   }
 738
 739   assert(hasMetadataHashEntry() &&
 740          getContext().pImpl->MetadataStore.count(this) &&
 741          "Shouldn't have called this");
 742   const LLVMContextImpl::MDMapTy &Info =
 743     getContext().pImpl->MetadataStore.find(this)->second;
 744   assert(!Info.empty() && "Shouldn't have called this");
 745
 746   Result.append(Info.begin(), Info.end());
 747
 748   // Sort the resulting array so it is stable.
 749   if (Result.size() > 1)
 750     array_pod_sort(Result.begin(), Result.end());
 751 }
 752
 753 void Instruction::getAllMetadataOtherThanDebugLocImpl(
 754     SmallVectorImpl<std::pair<unsigned, MDNode *>> &Result) const {
 755   Result.clear();
 756   assert(hasMetadataHashEntry() &&
 757          getContext().pImpl->MetadataStore.count(this) &&
 758          "Shouldn't have called this");
 759   const LLVMContextImpl::MDMapTy &Info =
 760     getContext().pImpl->MetadataStore.find(this)->second;
 761   assert(!Info.empty() && "Shouldn't have called this");
 762   Result.append(Info.begin(), Info.end());
 763
 764   // Sort the resulting array so it is stable.
 765   if (Result.size() > 1)
 766     array_pod_sort(Result.begin(), Result.end());
 767 }
 768
 769 /// clearMetadataHashEntries - Clear all hashtable-based metadata from
 770 /// this instruction.
 771 void Instruction::clearMetadataHashEntries() {
 772   assert(hasMetadataHashEntry() && "Caller should check");
 773   getContext().pImpl->MetadataStore.erase(this);
 774   setHasMetadataHashEntry(false);
 775 }
 776