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